基于多維特征分析的移動社會網絡消息傳輸

朱子青 曹玖新 周 濤 胥 帥 馬 卓 劉 波

(東南大學計算機科學與工程學院 南京 211189) (計算機網絡和信息集成教育部重點實驗室(東南大學) 南京 211189) (zzqxztc@seu.edu.cn)

基于多維特征分析的移動社會網絡消息傳輸

朱子青 曹玖新 周 濤 胥 帥 馬 卓 劉 波

(東南大學計算機科學與工程學院 南京 211189) (計算機網絡和信息集成教育部重點實驗室(東南大學) 南京 211189) (zzqxztc@seu.edu.cn)

基于延遲容忍特征，移動社會網絡采用“存儲—運載—轉發(fā)”模式在節(jié)點之間進行消息傳輸.如何選定合適的中繼節(jié)點進行消息的高效傳輸是當前研究中備受關注的熱點問題.從不同的角度對網絡中的多維社會特征展開分析.首先，根據節(jié)點間的交互關系，確定節(jié)點間社會關系模型；其次，依據網絡拓撲給出了鄰居集合和本地社區(qū)的定義，提出了一種移動社會網絡的本地社區(qū)劃分方法，進而建立了節(jié)點間的社區(qū)關系；然后，基于節(jié)點間的行為特征給出了節(jié)點活躍度定義，通過PageRank算法獲得節(jié)點的多維屬性特征PR值，并利用PR值給出節(jié)點間傳輸值，從而獲得節(jié)點的不同傳輸效用值.在此基礎之上，綜合考慮節(jié)點社區(qū)關系和節(jié)點的不同傳輸效用值，設計并實現了移動社會網絡的消息傳輸算法.實驗表明，算法在傳輸成功率、傳輸冗余率、平均延時等多個方面具有優(yōu)勢.

移動社會網絡；延遲容忍網絡；社區(qū)劃分；PageRank算法；動態(tài)網絡

隨著手機等移動設備的大量普及，利用移動設備建立的連接進行設備之間的直接信息傳輸引起了廣泛的關注.移動社會網絡(mobile social network, MSN)是由人隨身攜帶的移動設備構成，具有社會網絡的社會性和移動通信網絡的移動性.如何解決MSN網絡中的消息傳輸和共享一直是人們研究的熱點問題.在網絡中，設備會隨著人移動，由于人的移動性，即人們之間的相遇時間間隔與相遇頻率等因素會影響設備間消息的傳輸成功率或者傳輸延時.當前大量的研究表明，隨著人移動的設備在移動過程中存在著明顯的移動規(guī)律.文獻[1]通過對大量的實驗數據進行分析，得出網絡中的移動設備之間相遇間隔時間服從冪律分布的結論.文獻[2]則指出人們所攜帶的網絡節(jié)點之間的相遇間隔時間在某時間閾值范圍內服從冪律分布，而超過該閾值則服從指數分布.文獻[3-4]也對隨著人移動的設備間相遇規(guī)律開展了研究，表明網絡中的節(jié)點移動行為確實存在基于社會行為的移動規(guī)律.

如何利用移動社會網絡中的社會規(guī)律，分析節(jié)點之間的社會關系特征，從而設計消息傳輸算法是一個重要的研究問題.

本文綜合考慮移動社會網絡中節(jié)點所存在的多維社會特征.基于網絡的局部拓撲和交互關系設計了本地社區(qū)算法；根據節(jié)點的移動行為規(guī)律提出了節(jié)點的社會活躍度概念；利用PageRank算法使節(jié)點之間根據傳輸狀況特征的不同進行相互評價，從而獲得節(jié)點的多屬性特征PR特征值，并給出節(jié)點間傳輸值的定義；最終，設計實現了移動社會網絡消息傳輸算法.

1 相關工作

近年來，業(yè)界對延遲容忍網絡(delay tolerant network, DTN)[5]消息傳輸已經開展了大量研究工作.有基于傳統路由轉發(fā)策略擴展改進的MED，EDAQ，LP，PLSR路由[6]；基于多副本傳染型傳輸策略改進的Spray系列路由[7-8]、利用路由節(jié)點概率效用值進行傳輸的Prophet路由[9]；結合新型智能優(yōu)化算法[10-11]的路由.傳統DTN路由算法的設計都沒有涉及網絡中存在的社會規(guī)律.因而在移動社會網絡環(huán)境下，開展了很多結合社會網絡規(guī)律設計的基于社會屬性(social based)的路由算法的研究.

Daly等人[12]利用復雜網絡中度(degree)、接近中心度(closeness centrality)、介數中心度(betweenness centrality)、節(jié)點間相似性(similarity)等特性對網絡中的社會特征進行分析，提出了SimBet算法，實現路由消息傳輸.Pan等人[13-14]分析了網絡中存在的社區(qū)結構，提出了BubbleRap算法，消息依據節(jié)點間的社區(qū)關系進行傳播，提高了網絡中消息的傳輸性能.Wu等人[15]依據網絡中移動節(jié)點所存在的“Home”屬性，提出了類似Spray路由機制的Homing Spread算法，可以有效提高消息傳輸性能.Li等人[16]分析了節(jié)點之間的相遇頻率、每次平均通信時間、歷史通信總時間和平均最短分離時間對節(jié)點之間交互緊密程度的影響，進而從中選擇合適的指標建立節(jié)點間社會關系.而Gao等人[17]則著重研究了節(jié)點之間的瞬時連接對消息傳輸的作用.

以上研究所具有的共同特點在于網絡中消息傳輸算法所利用的網絡社會關系特征都是通過節(jié)點之間的移動交互“探索”得到的，被稱為探索型社會網絡(detected social networks)[18].也有一部分研究不通過節(jié)點之間的“探索”獲得社會關系.而是直接利用網絡中節(jié)點之間已經存在的社會連接關系分析節(jié)點間社會特征，此類型的移動社會網絡被稱為自我宣稱型社會網絡(self-reported social networks)[18].在移動社會網絡中，有文獻利用社會關系問卷調查、社交網絡朋友關注等已知的社會關系來分析網絡中的社會特征，進而設計消息傳輸算法.如文獻[19-20]利用了用戶線上Facebook的社交關系建立了社會關系拓撲，而文獻[21]則是利用INFOCOM2006的與會人員填寫的問卷調查建立已知的社會關系網絡.

然而現有的相關研究工作仍然存在一些不足：

1) 當前一些研究[21]是建立在整個網絡中節(jié)點之間社會關系已經確定的基礎之上，對全局網絡的社會屬性特征進行分析，進而設計中繼節(jié)點選擇算法.而移動網絡的特性決定了網絡中各節(jié)點只能動態(tài)地獲得局部的網絡拓撲結構或部分節(jié)點之間的關系，因此應該更注重節(jié)點的局部動態(tài)連接關系分析.

2) 很多學者[14]對網絡中存在的社區(qū)關系展開了研究.然而社區(qū)之間的劃分是建立在網絡中節(jié)點全局關系已完全建立的基礎之上.這不適用于移動社會網絡的局部動態(tài)連接情況.在移動社會網絡中，節(jié)點動態(tài)地獲取周圍節(jié)點的連接信息，通過局部的網絡信息，和周圍節(jié)點建立社區(qū)關系.一部分學者[16,21]在移動社會網絡的環(huán)境下，對局部社區(qū)探測進行了探討.但是通過局部信息建立的本地社區(qū)(local community)只關注社區(qū)關系形成的過程，沒有關注時間流逝之后節(jié)點社區(qū)的老化問題.

3) 社會網絡中存在的冪律性特征，例如網絡中度數小的節(jié)點要比度數大的節(jié)點數量高很多，所以在傳輸時，只考慮節(jié)點自身的度指標會產生傳輸數據向某些節(jié)點過度集中的問題.這造成了消息傳輸的不公平性，個別節(jié)點上的消息負載相對過高.社會網絡領域的研究中就發(fā)現小度數節(jié)點或者弱連接對信息在網絡中的傳播有重要作用[22].Ioannidis等人[23]便研究過如何利用網絡中弱社會關系對消息進行路由傳輸.節(jié)點自身不活躍而鄰居很活躍，節(jié)點也可以將持有的消息擴散出去.因此，應該應用一種更科學的指標來使消息向“非中心性”節(jié)點傳輸.考慮節(jié)點在傳輸時，節(jié)點自身的傳輸狀況對周圍節(jié)點的影響.

2 節(jié)點社會關系模型

由于節(jié)點間相遇的間斷性，移動社會網絡的網絡拓撲會不斷改變.本文將節(jié)點間不斷變化的節(jié)點移動相遇關系轉變?yōu)橄鄬Ψ€(wěn)定的社會關系.然后對網絡中存在的社會特征展開分析.

在移動社會網絡中，社會關系緊密的節(jié)點，節(jié)點之間也會進行頻繁的通信，因而可以用節(jié)點間的通信累計時間表示節(jié)點間的社會關系.本文將移動社會網絡建模為具有多屬性的節(jié)點無向網絡圖，其形式化描述如下：

給定Gt(V,E),其中V是網絡中的節(jié)點集合，E為網絡中2個節(jié)點之間社會關系連接邊的集合，t表示網絡在一段時期的狀態(tài).網絡中節(jié)點u，v之間的邊關系權重表示為wt(u,v)，表示為節(jié)點u，v之間在一段時期t的累計通信時間.每個節(jié)點與其他節(jié)點的相遇頻率、相遇時間間隔等特征，作為節(jié)點集合V中節(jié)點所具有的自身屬性.

3 本地社區(qū)發(fā)現

攜帶消息的節(jié)點在網絡中根據和其相遇節(jié)點的社區(qū)關系，選擇不同的消息路由策略.因此本文參考文獻[24]的思想提出改進的本地社區(qū)探測算法LAC(local aging community).

3.1 鄰居集合和本地社區(qū)

為便于描述，本文定義相關的概念.

定義1. 節(jié)點直接鄰居關系.是指兩相遇節(jié)點之間的累積相遇時間超過設定的閾值，則這2個節(jié)點之間形成直接鄰居關系，體現了節(jié)點之間通信連接的緊密性.

對于一個給定的節(jié)點u，其直接鄰居的節(jié)點集合可形式化表示為：

Nu={v|wt(u，v)>Tth,v∈Mu}，

其中，wt(u,v)表示u與v之間的邊權重；Tth表示鄰居關系時間閾值；Mu表示和節(jié)點u相遇過的節(jié)點集合.

定義2. 節(jié)點間接鄰居關系.是指兩相遇節(jié)點沒有形成直接鄰居關系，但是2節(jié)點之間的直接鄰居重合程度超過設定閾值，則這2個節(jié)點之間形成間接鄰居關系，體現了節(jié)點之間再通信的可能性.

對于一個給定的節(jié)點u，其間接鄰居的節(jié)點集合可形式化表示為：

其中，Tth為設定的時間閾值；Nu和Nv分別表示u與v的直接鄰居節(jié)點集合；Mu表示和節(jié)點u相遇過的節(jié)點集合；λ為重合度設定閾值.

定義3. 節(jié)點本地社區(qū).是指和節(jié)點同處一個社區(qū)的節(jié)點組成的集合.其包括所有直接鄰居節(jié)點和間接鄰居節(jié)點的集合，以及節(jié)點本地社區(qū)在形成過程中，兩相遇節(jié)點互相合并本地社區(qū)時，不存在直接鄰居和間接鄰居關系的節(jié)點.

對于一個給定的節(jié)點u，其本地社區(qū)的成員集合可形式化表示為：

定義4. 節(jié)點間接社區(qū)關系.是指兩相遇節(jié)點之間的本地社區(qū)滿足條件合并后，新本地社區(qū)中不屬于2個節(jié)點原本地社區(qū)的節(jié)點.2個節(jié)點分別和不屬于原本地社區(qū)的節(jié)點形成節(jié)點間接社區(qū)關系.節(jié)點間接社區(qū)關系，體現了節(jié)點之間形成社區(qū)或者相遇通信的可能性.

對于一個給定的節(jié)點u，其節(jié)點間接社區(qū)成員集合可形式化表示為：

3.2 本地社區(qū)發(fā)現算法

本文給出適用于移動社會網絡的本地社區(qū)劃分算法LAC，其基本思想是：

1) 本地社區(qū)形成過程.節(jié)點的直接鄰居關系和間接關系節(jié)點首先成為其本地社區(qū)成員；然后節(jié)點間在每次相遇過程中，通過本地社區(qū)的重合條件進行合并，產生新的本地社區(qū)成員.

2) 本地社區(qū)維護過程.節(jié)點首先檢測其直接鄰居關系節(jié)點是否老化，如果節(jié)點的直接鄰居關系節(jié)點出現老化，則檢測節(jié)點的間接鄰居關系節(jié)點；最后檢測和節(jié)點存在間接社區(qū)關系節(jié)點是否老化.因而算法流程包括本地形成和社區(qū)維護2個過程.

過程1. LAC本地社區(qū)形成.

過程1和過程2分別表示LAC算法中本地社區(qū)形成和隨時間流逝的維護過程.其中，過程1的行⑤～⑦表示節(jié)點間的直接鄰居關系形成.行⑧～表示節(jié)點間的間接鄰居關系形成.行～表示節(jié)點的本地社區(qū)合并，并產生存在間接社區(qū)關系的節(jié)點.而過程2中，行④～⑧表示隨時間流逝，節(jié)點之間的邊權重改變，引起節(jié)點間的直接鄰居關系老化；行⑨～表示隨時間流逝節(jié)點間的間接鄰居關系老化；行～表示節(jié)點的本地社區(qū)中間接社區(qū)關系節(jié)點被刪除；行～進行DO WHILE循環(huán)檢測，是因為間接社區(qū)關系節(jié)點在每次社區(qū)合并過程中，會使新的間接社區(qū)關系節(jié)點加入，因而每次本地社區(qū)成員改變了，要循環(huán)檢測其余存在間接社區(qū)關系的節(jié)點是否應該被刪除.

對于LAC的算法時間復雜度，過程1的時間消耗主要集中在行④、行⑧和行，即節(jié)點u判斷相遇節(jié)點v是否存在于其本地社區(qū)以及判斷鄰居或者社區(qū)的重合度.節(jié)點u本地社區(qū)成員數目為|Cu|，顯然都要比節(jié)點的鄰居數目要大，因而算法時間復雜度為O(|Cu|).而過程2的時間消耗主要集中在行①、行④、行⑨和行的節(jié)點集合遍歷，和行⑩和行，檢測原先條件滿足時所記錄的重合集合Nu∩Nv，Cu∩Cv的狀態(tài).而存在間接社區(qū)關系的節(jié)點，在每輪維護中，某種情況下可以通過DO WHILE循環(huán)檢測依次全部刪除，假設節(jié)點u的間接社區(qū)成員數目為，則其為遞減數列因而最壞情況下，算法時間復雜度為，一般情況下相遇過的節(jié)點數量|Mu|要比都要大，因而時間復雜度為O(|Mu|).

4 節(jié)點傳輸效用值

進行消息傳輸時，節(jié)點在判斷和相遇節(jié)點的社區(qū)關系基礎上，通過考慮相遇節(jié)點的傳輸效用值，在社區(qū)間和社區(qū)內選擇合適的中繼節(jié)點.

4.1 節(jié)點社會活躍度

在網絡中相遇節(jié)點數量多的節(jié)點，其本身具有更高的消息傳播可能性.同時，節(jié)點和周圍節(jié)點相遇比較頻繁，也能增加節(jié)點傳播消息的能力.本文利用節(jié)點的相遇節(jié)點數目和與其他節(jié)點相遇時間間隔來描述節(jié)點的活躍程度，即社會活躍度(social activity, SA)，其定義為：

SA(u)=|Mu|a-δTu，

(1)

其中,|Mu|表示節(jié)點u在網絡中相遇過的節(jié)點數量,而Tu為一段時間內節(jié)點u和所有相遇過節(jié)點的最近相遇間隔時間的平均值,δ為平滑因子.

如文獻[1-2]所指出的，基于節(jié)點之間相遇時間間隔的冪指特性分布，只有很少一部分節(jié)點的相遇時間間隔會很大.所以本文將節(jié)點社會活躍度定義為關于時間的冪函數形式，當和其他節(jié)點相遇時間間隔變大，其社會活躍度也會快速下降.

4.2 節(jié)點多維屬性特征PR值

當消息在節(jié)點之間進行傳輸時，為了避免消息向個別中心節(jié)點過度聚集現象，本文使用新的指標來改進消息的傳輸性能.網頁排名的PageRank算法[25]使網站的重要度得分由自身和其他網站共同決定.

4.2.1 多維屬性特征分析

本文采用PageRank算法的思想建立節(jié)點的傳輸評分特征值.綜合網絡中節(jié)點的3種屬性特征展開分析.

1) 節(jié)點的社會活躍度屬性

對于節(jié)點的社會活躍度屬性，本文規(guī)定低活躍度的節(jié)點向周邊高活躍度的直接鄰居節(jié)點給予評分，反之，不評分.因而可以抽象為如圖1所示的有向圖.

Fig. 1 Node social activity relations圖1 節(jié)點社會活躍度關系

節(jié)點間的評分函數為：

A(v,u)×PR(v)，

(2)

其中，PR(v)為節(jié)點v的PageRank值，A(v,u)為節(jié)點v對直接鄰居節(jié)點u活躍度權重比例分配計算函數：

(3)

Fig. 2 Node interaction frequency relations圖2 節(jié)點交互頻率關系

節(jié)點依據周圍直接鄰居節(jié)點的社會活躍度和其自身的社會活躍度關系給予不同的評價權重.得分比較高的節(jié)點，表示其周圍直接鄰居都認為此節(jié)點有更高的社會活躍度.

2) 節(jié)點之間的相遇頻率屬性

對于節(jié)點和其他節(jié)點的相遇頻率屬性，可以抽象為如圖2所示的有向圖.

每個節(jié)點通過與周邊節(jié)點的交互頻率向直接鄰居給予評分，周圍鄰居出現頻率越高，則對其評分權重越大.本文給出節(jié)點按照相遇頻率得到的周圍鄰居評分函數：

Pv(u)×PR(v)，

(4)

其中，Pv(u)為節(jié)點v相遇其鄰居節(jié)點u的頻率.

依照節(jié)點周圍直接鄰居出現的頻率，節(jié)點對周圍直接鄰居節(jié)點出現的不同頻率，給予不同的評分權重.評分比較高的節(jié)點，表示其周圍鄰居節(jié)點都認為該節(jié)點經常出現，或者節(jié)點本身和某一評分較高的節(jié)點經常相遇.

3) 節(jié)點的直接鄰居數屬性

對于節(jié)點在網絡中的鄰居數屬性，即指節(jié)點的周圍的直接鄰居數量，如圖3所示.本文給出節(jié)點評分函數：

(5)

其中，Nv表示節(jié)點v的直接鄰居.

Fig. 3 Node direct neighbor relations圖3 節(jié)點的直接鄰居關系

依照節(jié)點周圍直接鄰居的數量，節(jié)點對每個鄰居均等地給予評分.評分高的節(jié)點，表示獲得了很多節(jié)點的評分，或者此節(jié)點和高評分的節(jié)點存在直接鄰居關系.

最后，本文綜合考慮不同方面的特征分析，給出基于PageRank算法的節(jié)點u得分特征值函數：

(6)

其中，α+β+γ=1，d為PageRank中的衰減因子.

4.2.2 節(jié)點PR值計算流程

對于PR值的計算迭代簡單實例如圖4所示.計算過程中，節(jié)點A需要接收節(jié)點B和C傳來的PR值分量才進行迭代計算.同理，節(jié)點B，C也要分別接收和傳輸鄰居的PR值分量才能完成自己的PR值計算.

Fig. 4 Simple network topology圖4 簡單網絡拓撲示意圖

因此，本文給出移動社會網絡下的PR值計算規(guī)則：

1) 每一個節(jié)點在傳輸完成自己的所有出度邊PR值分量和接收其他鄰居節(jié)點PR值分量后，更新自己的PR值.

2) 如果相遇節(jié)點之間的PR值和上次相遇時相同，則不進行節(jié)點之間的PR分量值傳輸.

在移動網絡的環(huán)境下，節(jié)點和直接鄰居關系節(jié)點在已經建立連接情況下，可以完成PR值每一輪計算，而每個節(jié)點PR值和網絡拓撲有關.因而當網絡拓撲越穩(wěn)定，節(jié)點之間相遇越頻繁，連接越持續(xù)，則會向節(jié)點PR值的收斂穩(wěn)定值趨近得越快.

4.3 節(jié)點間的傳輸值

為了使消息在網絡中的消息路由傳輸過程中具有目的性和方向性，減少傳輸開銷，本文分析PageRank算法分量的傳輸過程.如圖4所示，本文假定節(jié)點A，B，C的PR值當前都為1，因子d=0.85.出度邊的權重都為1.

假定節(jié)點B和節(jié)點A，C經常相遇，而節(jié)點C又經常和節(jié)點A經常相遇，本文分析節(jié)點B的PR值傳輸過程.

那么當節(jié)點B和節(jié)點A相遇時，節(jié)點A依據出邊權重向節(jié)點B傳輸PR值分量0.425.

當節(jié)點B和節(jié)點C相遇時，節(jié)點C獲得B傳來的PR值分量0.425.然后，節(jié)點C再和節(jié)點A相遇，節(jié)點C會依據自身出邊權重向節(jié)點A傳輸節(jié)點B的PR值分量0.361.

節(jié)點A將保留每次獲得的更大的傳輸值，作為節(jié)點對其的傳輸值.

因而在原始PageRank公式上定義節(jié)點u獲得節(jié)點v的傳輸值函數為：

(7)

其中，path(v,u)表示節(jié)點v對節(jié)點u的所有可能的傳輸路徑，m表示傳輸路徑上的一點，O(m)表示節(jié)點m的出度邊的集合，|L|表示其中一條路徑的長度.

式(7)中O(m)出度邊集合在本文中由有向評分權重函數代替,所以本文的基于PageRank算法的節(jié)點v對節(jié)點u的傳輸值函數為：

(8)

在移動網絡環(huán)境下，節(jié)點v每次將自己當前的PR值按照評分權重傳輸給周圍的直接鄰居，直接鄰居記錄這些節(jié)點v的PR值分量，然后再將這些分量繼續(xù)傳輸給自己的直接鄰居.因而任意一個節(jié)點會比較所有從鄰居節(jié)點獲得的節(jié)點v傳輸值，選取最大的值作為節(jié)點v對其的傳輸值.

5 移動社會網絡的消息傳輸算法

本文消息傳輸算法的基本思想是通過節(jié)點之間的社區(qū)關系選擇不同的傳輸策略，利用網絡的社會特征，在節(jié)點社區(qū)內和社區(qū)間選擇合適的中繼節(jié)點.從而防止社區(qū)內部消息在社區(qū)間的傳輸以及減少跨社區(qū)的消息在非目的節(jié)點社區(qū)內部的傳輸，使消息傳輸更有方向性、減少冗余的消息傳輸.

5.1 傳輸策略的選擇

本文算法根據消息傳輸的目的地節(jié)點和相遇節(jié)點之間的社區(qū)關系，選擇不同的路由策略.當節(jié)點u攜帶目的地為節(jié)點d的消息，和節(jié)點v相遇時，節(jié)點u會根據和相遇節(jié)點v的不同社區(qū)關系，同時考慮節(jié)點u，v之間的社會活躍度、消息目標節(jié)點的傳輸值等特征選擇不同的路由傳輸策略.具體策略如下：

1) 如果消息攜帶節(jié)點u及相遇節(jié)點v都不和消息目的地節(jié)點d處于同一社區(qū)，那么將消息傳輸到社會活躍度高的節(jié)點或者PR值和消息目標節(jié)點d的傳輸值都很高的節(jié)點，從而增大發(fā)現和目的地節(jié)點d處于同一社區(qū)的節(jié)點機會.

這里PR值仍然需要和傳輸值組合在一起作為節(jié)點選擇的依據，這是因為節(jié)點的PR值可以由直接鄰居節(jié)點的傳輸值組成，如對于節(jié)點u：

(9)

那么：

(10)

因而，節(jié)點傳輸值無法完全體現出節(jié)點自身的PR值特征.

2) 當消息攜帶節(jié)點u及相遇節(jié)點v都和目的地節(jié)點d處于同一社區(qū)，表明消息已經很接近目的地節(jié)點，則將消息向PR值和傳輸值都很高的節(jié)點傳輸.

3) 當消息攜帶節(jié)點u不和目的地節(jié)點d節(jié)點在同一社區(qū)，而相遇節(jié)點v和目的地節(jié)點d處于同一社區(qū)，那么就將消息傳輸給節(jié)點相遇節(jié)點v.

4) 當消息攜帶節(jié)點u不和目的地節(jié)點d節(jié)點處于同一社區(qū)，而相遇節(jié)點v和目的地節(jié)點d也不處于同一社區(qū)，那么就不進行消息傳輸.

5.2 算法流程

消息傳輸算法綜合考慮節(jié)點社區(qū)關系和節(jié)點的傳輸效用值，從而實現消息傳輸.其具體算法實現如下：

算法1. 消息傳輸算法.

算法1中，行③～⑦表示節(jié)點攜帶消息和相遇節(jié)點以及目標節(jié)點在同一社區(qū)內的傳輸情況;行～表示節(jié)點攜帶消息和相遇節(jié)點都不處于同一個社區(qū)的傳輸情況;而其他行，則表示消息優(yōu)先將消息傳輸給和目標節(jié)點同屬一個社區(qū)的相遇節(jié)點，否則不進行傳輸.

對于算法1的時間復雜度，其時間消耗主要集中在行③、行⑧和行，即節(jié)點u和相遇節(jié)點v消息目的節(jié)點d是否處于同一社區(qū).假設節(jié)點u和節(jié)點v的本地社區(qū)成員數目分別為|Cu|和|Cv|，因而算法時間復雜度為O(|Cu|+|Cv|).

顯然算法的有效工作依賴于節(jié)點相關特征屬性的計算和本地社區(qū)的發(fā)現.因此在網絡當中，每當2個節(jié)點相遇時，都要優(yōu)先互相交換自身特征屬性信息和獲得的其他節(jié)點特征屬性信息.

6 實驗與分析

為了評估算法的性能，本文實驗采用仿真工具ONE[26]，此仿真工具是專門為評估DTN網絡路由和算法協議設計的.本文將所提出的消息傳輸算法與Epidemic算法、Prophet算法、BubbleRap算法、Simbet算法在相同實驗環(huán)境下的傳輸性能進行了比較.其中,Epidemic算法對任何相遇的節(jié)點都進行消息傳輸,在不考慮緩存大小的理想情況下，能夠獲得最好的傳輸效果，本文把Epidemic算法作為一個性能比較的上界;Prophet算法是依照節(jié)點相遇概率進行消息傳輸的方法.而BubblRap算法和Simbet算法都是典型的帶有社會屬性的消息傳輸方法.

6.1 實驗數據

本文使用INFOCOM2005和INFOCOM2006數據集驗證算法在真實場景中的性能.

1) INFOCOM2005.該數據集采集自分發(fā)給2005年參與INFOCOM學生研討會的大概50名學生的移動設備.這些參與者屬于不同的國家、區(qū)域或者研究課題組.

2) INFOCOM2006.該數據集采集自分發(fā)給2006年參與INFOCOM會議的與會人員攜帶的移動設備.人數相比INFOCOM2005更多，超過80人.2組數據集的一些基本特征如表1所示.數據集的用戶活動范圍小、記錄周期短，但是相比其他的數據集，INFOCOM2005和INFOCOM2006都具有節(jié)點連接發(fā)生頻率高的特點.

Table 1 Data Basic Information表1 數據基本信息

6.2 參數設置

本文對算法1中的每個閾值參數進行選擇.根據人類生活規(guī)律，人們會在一段時間內進行周期性的活動，這一段時間可以是以每周(7 d)作為基礎單元，按照每月(約4周)、每年(約48周)進行一段時期的固定規(guī)律活動，而在這一段時間之后人的行為可能會改變.而INFOCOM2005和INFOCOM2006數據集的數據記錄只有3 d左右，所以本文把每天人們的日?；顒臃譃樯衔?、下午、夜晚、午夜4個時段[13](各6 h).以每個時段作為基礎單元，以每個基礎單元的倍數作為一段時期活動的周期時間單元.

對于INFOCOM2005和INFOCOM2006數據集，本文認為如果2個節(jié)點同時出席聽取同一場學術報告，這2個節(jié)點更有可能具有“社會鄰居”關系[13].考慮在進行學術報告時大家基本是不動的，所以本文把上午或下午時段內，學術報告會時長10 800 s(3 h)作為INFOCOM2005和INFOCOM2006數據集的鄰居關系建立閾值.

本文觀察INFOCOM2005和INFOCOM2006數據集的節(jié)點對通信間隔的累積分布log-log圖像，如圖5所示.可以發(fā)現，在43 200 s(2×6 h)之前呈現明顯的冪率分布特征.通過如圖6的log-line圖像可知，43 200 s(2×6 h)之后，節(jié)點對的通信間隔大小分布由冪率分布特征轉變?yōu)橹笖捣植继卣?也就是說，固定的活動規(guī)律有所改變.所以對于算法1在實驗中的參數，鄰居關系移除的時間閾值和平滑因子都以12 h作為選取點.

Fig. 5 Node contact interval time of log-log complementary cumulative distribution圖5 節(jié)點通信時間間隔互補累計分布log-log圖

Fig. 6 Node interval time of log-line complementary cumulative distribution圖6 節(jié)點時間間隔互補累計分布log-line圖

本文認為節(jié)點屬性的多個方面是同等重要的，因而PR特征值中的參數α,β,γ分別取為13.對本地社區(qū)發(fā)現算法中的相關參數λ、σ則參考文獻[24]中的實驗選取0.8.因而本文采用如表2所示的實驗參數.

Table 2 Selection of Threshold Parameter表2 閾值參數的選取

6.3 仿真場景

本文在實驗中采用50 MB大小的緩存，每45～150 s隨機產生一個5 KB左右大小的信息數據包，由網絡中某一節(jié)點隨機向另外一個節(jié)點發(fā)送.

6.4 算法評估

本文用以下指標來評估相關算法的性能.

1) 傳輸成功率(delivery ratio).算法的首要目標就是獲得更高的傳輸成功率.消息成功率就是在消息整個傳輸的過程中目標節(jié)點成功接收到消息數與在源節(jié)點所傳輸的所有消息數比值，反映了傳輸成功率.

2) 傳輸冗余率(overhead ratio).冗余率定義為每當成功接收一個消息數據包所需要的額外傳輸次數.此參數反映了消息的冗余傳輸次數.節(jié)點在移動社會網絡中進行間歇性通信，節(jié)點之間的相遇機會有限，能以越少冗余傳輸次數完成消息傳輸，說明算法性能越好.同時，對于復制型的算法，節(jié)點會在每次傳輸時創(chuàng)建消息副本，冗余傳輸次數過多，會產生更多的消息副本，影響網絡傳輸性能.

傳輸冗余率=

3) 平均延時(average delay).消息延時是指節(jié)點發(fā)送的消息從源節(jié)點成功到達目標節(jié)點所需的時間.平均消息延時體現了網絡的實時性，同時也間接反映了整個網絡的消息流通是否正常.雖然在延遲容忍網絡環(huán)境下，無法像傳統網絡那樣要求消息的傳輸延時，但是消息的傳輸延時比較低時，節(jié)點可以盡早釋放緩存中的數據，提升網絡的傳輸性能.

Fig. 7 Message delivery ratio圖7 消息傳輸成功率

6.5 結果分析

在仿真過程當中，本文通過改變每次實驗的不同生存時間(time to live, TTL)來比較各個路由算法的消息傳輸成功率、網絡傳輸冗余率、傳輸平均延時.

本文首先對比每一個算法的消息傳輸成功率.如圖7所示，隨著TTL增加，消息傳輸的成功率開始提高.這是因為消息的TTL增大使數據信息在緩存中駐留的時間更長了.因此攜帶消息的節(jié)點更有可能和目的地節(jié)點相遇.

Fig. 8 Message overhead ratio圖8 消息傳輸冗余率

很明顯，相比帶有社會屬性的SimBet算法和同樣使用社區(qū)發(fā)現策略的BubbleRap算法，本文提出的SocialEvalution算法的傳輸成功率要更好.相比SimBet在INFOCOM2005和INFOCOM2006數據集中，最高的成功率提升了約6.8%和29.3%，相比BubbleRap算法提升了約3%和4%.從實驗可知，SimBet算法非常不適應現實稀疏特征的數據集，其傳輸成功率很低.而本文算法和Prophet算法的傳輸成功率比較接近，甚至在INFOCOM2005的數據集中，本文的SocialEvalution算法和Prophet算法都非常逼近Epidemic算法的發(fā)送成功率.

對于實驗中每個算法的傳輸冗余率，從圖8中可以觀察到，因為Epidemic算法的無差異洪泛性傳輸，節(jié)點之間的冗余中繼傳輸次數很多.在消息的傳輸過程中，網絡中的大多數節(jié)點都對消息進行了傳輸.因而2個數據集中，Epidemic算法的消息冗余中繼傳輸次數非常高，而SimBet算法的傳輸冗余率在2個數據集的仿真實驗中都比較小，但是實驗結果表明其相比其他算法的傳輸成功率要低.Bubble算法的傳輸冗余率要比本文的算法和Prophet算法的傳輸冗余率要小，但是其傳輸成功率相比本文算法要低.

對于算法的傳輸冗余率，顯然攜帶消息的節(jié)點直接等待消息傳輸的目的節(jié)點出現的傳輸冗余率是最低的，但是這種模式的傳輸效果顯然是最差的.如果消息通過一些中繼節(jié)點更快地被傳輸到目的節(jié)點，那么消息在傳輸過程中的中繼節(jié)點很多會造成其傳輸次數增多，這將導致算法的冗余率升高，但是卻可以保證消息傳輸的延時和傳輸成功率.因而還需要比較各個算法的平均延時.

Fig. 9 Message average delay圖9 網絡傳輸平均延時

本文的SocialEvalution算法避免消息向個別節(jié)點過于集中傳輸，節(jié)點會選擇其他的候選節(jié)點作為消息中繼節(jié)點，因而這會造成消息的冗余傳輸次數增加.所以SocialEvalutio算法的冗余率比SimBet和Bubble都要高，但是本文的SocialEvalution算法顯然要比Prophet算法冗余率要低，而且算法的傳輸成功率和Prophet相比沒有下降.

如圖9所示，實驗表明SimBet算法和BubbleRap算法的平均傳輸延時很高，而Epidemic算法的消息傳輸的洪泛策略使消息的平均延時最低.INFOCOM2005數據集中，本文SocialEvalution算法的發(fā)送延時和Prophet算法很接近.而在2個數據集中，當消息的TTL大于12 h時，SocialEvalution算法的消息平均延時相比Prophet算法的平均延時出現升高.

這種結果的出現是由于SocialEvalution中如6.2節(jié)實驗設置部分所述，將鄰居關系移除閾值設定為12 h，而12 h之后社區(qū)算法刪除了一些老化的社區(qū)成員節(jié)點.在實驗中，這些被刪除的節(jié)點可能依然會偶爾和消息攜帶節(jié)點產生相遇，進而有機會獲得消息，并將消息傳輸給目的節(jié)點，這種情況降低了Prophet算法的傳輸平均延時.

7 總結與展望

本文基于建立的網絡拓撲設計了本地社區(qū)算法；根據節(jié)點的移動行為規(guī)律提出了節(jié)點的社會活躍度概念；利用PageRank算法計算節(jié)點的多屬性特征PR特征值，并給出節(jié)點間傳輸值的定義；在此基礎之上，設計和實現了移動社會網絡消息傳輸算法；最后在真實數據集合上驗證本文消息傳輸算法的性能.實驗表明本文的路由算法相比其他算法具有更好的傳輸效果.

在實際環(huán)境中，網絡中的移動節(jié)點移動方式復雜多變.移動社會網絡的消息傳輸研究難點，便在于如何挖掘和利用節(jié)點之間潛在的行為模式信息，進而實現消息的路由傳輸.因為網絡本身所具有的社會性特征，利用網絡中存在的社會特性可以預測節(jié)點的移動行為，改善網絡傳輸性能.

未來計劃更加深入地分析消息在節(jié)點間的傳輸特性，研究節(jié)點之間存在的社會關系，從而探索更好的社區(qū)發(fā)現算法和深入挖掘節(jié)點的社會特征.

[1]Chaintreau A, Pan Hui, Crowcroft J, et al. Impact of human mobility on opportunistic forwarding algorithms [J]. IEEE Trans on Mobile Computing, 2007, 6(6): 606-620

[2]Karagiannis T, Boudec L J Y, Vojnovic＇ M, et al. Power law and exponential decay of inter contact times between mobile devices[C] //Proc of the 13th Annual ACM Int Conf on Mobile Computing and Networking (MobiCom’07). New York: ACM, 2007: 183-194

[3]Passarella A, Conti M, Boldrini C, et al. Modelling inter-contact times in social pervasive networks[C] //Proc of the 14th ACM Int Conf on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWi M’11). New York: ACM, 2011: 333-340

[4]Tian Ye, Li Jiang. Heterogeneity of device contact process in pocket switched networks[C] //Proc of the 5th Int Conf on Wireless Algorithms, Systems and Applications(WASA’10). New York: ACM, 2010: 157-166

[5]Fall K. A delay-tolerant network architecture for challenged Internets[C] //Proc of the 2003 Applications, Technologies, Architectures and Protocols for Computer Communications (SIGCOMM’03). New York: ACM, 2003: 27-34

[6]Jain S, Fall K, Patra R. Routing in a delay tolerant network[C] //Proc of the 2004 Applications, Technologies, Architectures and Protocols for Computer Communications(SIGCOMM’04). New York: ACM, 2004: 145-158

[7]Spyropoulos T, Psounis K, Raghavendra C S. Efficient routing in intermittently connected mobile networks: The single-copy case [J]. IEEE/ACM Trans on Network, 2008, 16(1): 63-76

[8]Spyropoulos T, INRIA, Psounis K, et al. Efficient routing in intermittently connected mobile networks: The multiple-copy case[J]. IEEE/ACM Trans on Network, 2008, 16(1): 77-90

[9]Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20

[10]Yang Zhenguo, Huang Liusheng, Xiao Mingjun, et al. ACR: An ant-colony-based routing in delay tolerant networks[J]. Journal of Computer Research and Development, 2012, 49(12): 2501-2514 (in Chinese)(楊振國, 黃劉生, 肖明軍, 等.一種基于蟻群算法的容遲網絡路由策略[J]. 計算機研究與發(fā)展, 2012, 49 (12): 2501-2514)

[11]Wang En, Yang Yongjian, Li Li. Game of life based congestion control strategy in delay tolerant networks[J]. Journal of Computer Research and Development, 2014, 51(11): 2393-2407 (in Chinese)(王恩, 楊永健, 李蒞. DTN中基于生命游戲的擁塞控制策略[J]. 計算機研究與發(fā)展, 2014, 51 (11): 2393-2407)

[12]Daly E M, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs[C] //Proc of the 8th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’07). New York: ACM, 2007: 32-40

[13]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay tolerant networks[C] //Proc of the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc’08). New York: ACM, 2008: 241-250

[14]Pan Hui, Crowcroft J, Yoneki E. Bubble rap: Social-based forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2011, 10(11): 1576-1589

[15]Wu Jie, Xiao Mingjun, Huang Liusheng. Homing spread: Community home-based multi-copy routing in mobile social networks[C] //Proc of the 2003 Int Conf on Computer Communications (INFOCOM’03).Piscataway, NJ: IEEE, 2013: 2319-2327

[16]Li Feng, Wu Jie. LocalCom: A community-based epidemic forwarding scheme in disruption-tolerant networks[C] //Proc of the 2009 Society Conf on Mesh and Ad Hoc Communications and Networks (SECON’09).Piscataway, NJ: IEEE, 2009: 1-9

[17]Gao Wei, Cao Guohong, Porta L T, et al. On exploiting transient social contact patterns for data forwarding in delay-tolerant networks[J]. IEEE Trans on Mobile Computing, 2013, 12 (1): 151-165

[18]Wei Kaimin, Liang Xiao, Xu Ke. A survey of social-aware routing protocols in delay tolerant networks: Applications, taxonomy and design-related issues[J]. Communications Surveys & Tutorials, 2014, 16(1): 556-578

[19]Socievole A, Yoneki E, Rango F D, et al. Opportunistic message routing using multi-layer social networks[C] //Proc of the 2nd ACM Workshop on High Performance Mobile Opportunistic Systems(HP-MOSys’13). New York: ACM, 2013: 39-46

[20]Pietil?inen AK, Oliver E, LeBrun J, et al. Mobiclique: Middleware for mobile social networking[C] //Proc of the 2nd ACM Workshop on Online Social Networks(WOSN’09). New York: ACM, 2009: 49-54

[21]Mtibaa A, May M, Diot C, et al. PeopleRank: Social opportunistic forwarding[C] //Proc of the 2010 Int Conf on Computer Communications (INFOCOM’10).Piscataway, NJ: IEEE, 2010: 1-5

[22]Granovetter M S. The strength of weak ties [J]. American Journal of Sociology, 1973, 78(6): 1360-1380

[23]Ioannidis S, Chaintreau A. On the strength of weak ties in mobile social networks[C] //Proc of the 2nd ACM EuroSys Workshop on Social Network Systems (SNS’09). New York: ACM, 2009: 19-25

[24]Pan Hui, Yoneki E, Chan Shuyan, et al. Distributed community detection in delay tolerant networks[C] //Proc of the 2nd ACM/IEEE Int Workshop on Mobility in The Evolving Internet Architecture(MobiArch’07). New York: ACM, 2007: No.7

[25]Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1): 107-117

[26]Helsinki University of Technology. ONE: Opportunistic network environment[CP]. 2009 [2015-12-03]. http://www.netlab.tkk.fi/tutkimus/dtn/theone

Zhu Ziqing, born in 1990. PhD candidate of Southeast University. His current research interests include social computing and computer network.

Cao Jiuxin, born in 1967. Professor and PhD supervisor of Southeast University. His current research interests include social computing, computer network and complex network.

Zhou Tao, born in 1989. PhD candidate of Southeast University. His current research interests include social computing and complex network.

Xu Shuai, born in 1991. PhD candidate of Southeast University. His current research interests include social computing.

Ma Zhuo, born in 1993. Master candidate of Southeast University. Her current research interests include social computing.

Liu Bo, born in 1975. Professor and master supervisor of Southeast University. Her current research interests include social computing and distributed network management.

Multi-Feature Based Message Transmitting in Mobile Social Network

Zhu Ziqing, Cao Jiuxin, Zhou Tao, Xu Shuai, Ma Zhuo, and Liu Bo

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189) (KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)

Based on the features of delay tolerant network (DTN), mobile social network (MSN) uses “storage-carry-forwards” approach for message transmission between nodes. How to select a suitable relay node for efficient message transmission is an urgent issue in the current research fields. This paper focuses on the problem by analyzing the social characteristics of network in different perspectives. Firstly, based on the interaction between nodes, the model of social relations between nodes is constructed. Secondly, this paper gives the definition of neighbor set and local community based on the network topology and establishes the community relationship between the nodes. Furthermore, this paper defines the social activity based on the behavior of nodes and takes advantage of the PageRank algorithm to obtainPRvalues on the basis of multiple features of nodes. Then, transmission values of nodes is defined by usingPRvalues and different utility values of nodes can be obtained. On this basis, considering community relations of nodes and different transmission utility values of nodes, this paper designs and implements a message transmission algorithm in mobile social network. Finally, experiments show that the algorithm has advantages in delivery ratio, overhead ratio and average delay.

mobile social network (MSN); delay tolerant network (DTN); community detection; PageRank algorithm; dynamic network

2015-12-03；

2016-03-22

國家“九七三”重點基礎研究發(fā)展計劃基金項目(2010CB328104)；國家“八六三”高技術研究發(fā)展計劃基金項目(2013AA013503)；國家自然科學基金項目(61272531，61202449，61272054，61370207，61370208，61300024，61320106007，61472081)；江蘇省網絡與信息安全重點實驗室基金項目(BM2003201)；江蘇省科技計劃基金資助項目(SBY2014021039-10) This work was supported by the National Basic Research Program of China (973 Program) (2010CB328104), the National High Technology Research and Development Program of China (863 Program) (2013AA013503), the National Natural Science Foundation of China (61272531, 61202449, 61272054, 61370207, 61370208, 61300024, 61320106007, 61472081), the Jiangsu Provincial Key Laboratory of Network and Information Security Foundation (BM2003201), and the Science and Technology Planning Project of Jiangsu Province (SBY2014021039-10).

曹玖新(jx.cao@seu.edu.cn)

TP393