胡 桐，郭忠文，Bernd－Ludwig Wenning，Carmelita G9rg

（1.中國海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島266100；

2.Nimbus Centre for Embedded Systems Research，Cork Institute of Technology，Cork，Ireland；3.Communications Networks，TZI，University of Bremen，Bremen，Germany）

隨著微電子與通信技術(shù)的發(fā)展，具備短距無線通信能力的手持設(shè)備（如智能手機、平板電腦等）得到普及，利用數(shù)量龐大的手持設(shè)備組成分布式網(wǎng)絡(luò)（Pocket Switched Network，PSN[1]）并提供不依賴于網(wǎng)絡(luò)基礎(chǔ)設(shè)施的網(wǎng)絡(luò)服務(wù)成為了移動容遲網(wǎng)絡(luò)的1個新的應(yīng)用場景。

在由手持設(shè)備組成的移動容遲網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點（即手持設(shè)備）由人隨身攜帶，節(jié)點間利用移動相遇帶來的通信機會轉(zhuǎn)發(fā)消息。設(shè)備攜帶者之間的社團（Community）關(guān)系對消息的轉(zhuǎn)發(fā)過程影響較大。一方面，相對于不斷變化的網(wǎng)絡(luò)拓撲，設(shè)備攜帶者間的社團關(guān)系較為穩(wěn)定，屬于相同社團的節(jié)點相遇的概率遠遠大于屬于不同社團的節(jié)點相遇的概率。另一方面，設(shè)備攜帶者在網(wǎng)絡(luò)中的活躍程度存在差異，造成了節(jié)點具有不同的中心度（Centrality），具有較高中心度的節(jié)點具有更多的消息轉(zhuǎn)發(fā)機會。基于社會網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法（Social－based forwarding algorithm）[2－5]利用上述特性輔助轉(zhuǎn)發(fā)決策，因而更加適用于手持設(shè)備網(wǎng)絡(luò)環(huán)境。

在基于社會網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)算法基礎(chǔ)上建立的數(shù)據(jù)共享服務(wù)通常采用發(fā)布/訂閱（Publish/Subscribe）方式[6－8]。節(jié)點間的發(fā)布/訂閱關(guān)系由代理節(jié)點（Broker）維護，共享數(shù)據(jù)在Broker節(jié)點之間進行轉(zhuǎn)發(fā)，因而Broker節(jié)點失效將造成數(shù)據(jù)無法共享。此外，節(jié)點間共享的數(shù)據(jù)容量較大（例如包含圖片或音視頻的消息），通過增加冗余消息副本來提高傳輸成功率的方法將造成較高的消息傳輸代價。

針對上述問題，本文提出了基于社團的源路由算法（Social－based Source Routing，SSR）。該算法利用節(jié)點間相對穩(wěn)定的社團結(jié)構(gòu)對連接共享數(shù)據(jù)的節(jié)點（Content source）與需要數(shù)據(jù)的節(jié)點（Content consumer）的社團路徑（Community path）進行構(gòu)建，然后采用基于單消息副本的源路由方式轉(zhuǎn)發(fā)消息，從而顯著降低消息傳輸代價。另外，該算法假設(shè)節(jié)點間不存在固定的發(fā)布/訂閱關(guān)系，Content source與 Content consumer之間的關(guān)系只針對當(dāng)前共享的數(shù)據(jù)而臨時建立。在消息轉(zhuǎn)發(fā)過程中，中繼節(jié)點的選取不固定，從而避免了因Broker節(jié)點失效造成的數(shù)據(jù)無法共享問題。

1 相關(guān)工作

1.1 移動節(jié)點相遇規(guī)律分析

Chaintreau等[9]利用實驗數(shù)據(jù)對移動節(jié)點間的相遇間隔時間進行了分析，指出手持設(shè)備網(wǎng)絡(luò)中所有節(jié)點間的相遇間隔時間在10min～1d范圍內(nèi)服從冪律分布（Power law）而且不存在有限的均值，網(wǎng)絡(luò)中的平均消息傳輸時延為無限大。Karagiannis等[10]指出網(wǎng)絡(luò)中所有節(jié)點的相遇間隔時間的分布具有類似趨勢：存在某一閾值（約12h），相遇間隔時間小于該閾值時服從冪律分布而大于該閾值時則服從指數(shù)分布，并且網(wǎng)絡(luò)中的平均消息傳輸時延與該閾值具有相同數(shù)量級。Tian等[11]對實驗數(shù)據(jù)中每一對節(jié)點的相遇間隔時間進行排序分組并分析了各組之間的差異，指出了各節(jié)點的相遇規(guī)律存在異構(gòu)性。

1.2 分布式社團檢測

Hui等[12]針對手持設(shè)備網(wǎng)絡(luò)提出了3個分布式社團檢測算法：SIMPLE、k－CLIQUE和 MODULARITY算法。Li等[6]利用緊密關(guān)系度（Closeness centrality）對節(jié)點間聯(lián)系的緊密程度進行量化，將各節(jié)點與其他節(jié)點的關(guān)系表示為帶權(quán)圖的形式（Neighboring graph），圖中直接相連或至少存在一條長度為k的路徑的節(jié)點集合即社團結(jié)構(gòu)。Herbiet等[13]提出了SHARC算法，各節(jié)點在相遇時計算彼此的相似度，并且將與其相似度最高的節(jié)點的社團標簽作為自己的社團標簽（即被社團成員同化），重復(fù)該過程則網(wǎng)絡(luò)中各節(jié)點將檢測到各自的社團結(jié)構(gòu)。

1.3 基于社會網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)

Daly等[2]提出了SimBet算法，該算法利用介數(shù)中心度（Betweenness centrality）與相似度（Similarity）計算各節(jié)點向目的節(jié)點轉(zhuǎn)發(fā)消息的效用值，并選擇效用值較高的節(jié)點作為中繼節(jié)點。Bulut等[5]提出了基于朋友關(guān)系的路由算法（Friendship based routing），該算法利用與目的節(jié)點屬于同一社團或者與目的節(jié)點具有更強朋友關(guān)系的節(jié)點進行消息轉(zhuǎn)發(fā)。Li等[4]提出了基于社團的傳染路由算法（Community－based epidemic forwarding algorithm）。Hui等[3]提出了基于全局中心度（Global centrality）與本地中心度（Local centrality）的Bubble rap算法，該算法中消息在送達目的節(jié)點所屬社團之前沿著全局中心度增大的方向進行轉(zhuǎn)發(fā)，而當(dāng)消息送達目的節(jié)點所屬社團之后則沿著本地中心度增大的方向進行轉(zhuǎn)發(fā)。

1.4 移動容遲網(wǎng)絡(luò)中的數(shù)據(jù)共享

Yoneki等[8]提出了一種基于社會網(wǎng)絡(luò)覆蓋（Social－aware overlay）的發(fā)布/訂閱機制，該機制利用分布式社團檢測算法將動態(tài)網(wǎng)絡(luò)拓撲映射為節(jié)點間的社團關(guān)系，并選擇各社團中具有較高中心度的節(jié)點作為Broker節(jié)點。Li等[6]將基于內(nèi)容的服務(wù)（Contentbased service）應(yīng)用到發(fā)布/訂閱方式中并提出了MOPS（Mobile community－based Pub/Sub scheme）機制。Kangasharju等[15]提出了Floating Content機制，通過指定共享數(shù)據(jù)的復(fù)制范圍（Replication range）與有效范圍（Avalability range）控制數(shù)據(jù)在網(wǎng)絡(luò)中的傳播。Gao等[14]提出了以用戶為中心（User－centric）的數(shù)據(jù)分發(fā)機制。

2 移動節(jié)點相遇規(guī)律分析

本文利用統(tǒng)計方法[16]對 MIT Reality Mining數(shù)據(jù)集[17]中的移動節(jié)點相遇規(guī)律進行分析，包括網(wǎng)絡(luò)中所有節(jié)點的相遇間隔時間、單個節(jié)點與其他節(jié)點的相遇間隔時間、單個節(jié)點與其他節(jié)點的相遇次數(shù)。該方法首先對樣本數(shù)據(jù)可能的分布函數(shù)形式（如冪律分布、對數(shù)正態(tài)分布等）進行最大似然估計，然后利用對數(shù)似然比檢驗（Log－likelihood ratio test）選擇與樣本數(shù)據(jù)經(jīng)驗分布更為接近的分布函數(shù)形式。

2.1 網(wǎng)絡(luò)中所有節(jié)點的相遇間隔時間

網(wǎng)絡(luò)中所有節(jié)點的相遇間隔時間的物理含義為消息轉(zhuǎn)發(fā)過程中每一跳所需的傳輸時延。對該隨機變量分布函數(shù)形式的分析結(jié)果如圖1所示，可以看出相對于其他分布函數(shù)形式，指數(shù)截斷的冪律分布（Power law with exponential cutoff）與樣本數(shù)據(jù)的經(jīng)驗分布最為接近。

2.2 單個節(jié)點與其他節(jié)點的相遇間隔時間

網(wǎng)絡(luò)中各節(jié)點可能同時與多個節(jié)點相遇，因此各相遇過程可能存在重合（見圖2）。合并重合的相遇過程后，單個節(jié)點與其他節(jié)點的相遇間隔時間的物理含義為下一次通信機會到來之前的最短等待時間。本文通過MIT Reality Mining數(shù)據(jù)集中82個節(jié)點的相遇記錄數(shù)據(jù)對該隨機變量的分布函數(shù)形式進行分析，其余節(jié)點因樣本數(shù)量較少而被忽略。

結(jié)合對數(shù)似然比值的符號與檢驗p值的大小，本文對該隨機變量的分析結(jié)果進行了分類：（1）服從指數(shù)截斷的冪律分布；（2）服從其他分布；（3）不能判定的情況，即不能通過檢驗p值對數(shù)似然比值的符號進行判定。結(jié)果見表1。在所分析的82個節(jié)點中，48個節(jié)點服從指數(shù)截斷的冪律分布，7個節(jié)點服從其他分布，其余27個節(jié)點不能判定。由于服從指數(shù)截斷的冪律分布的節(jié)點數(shù)量較多，因此本文認為各節(jié)點與其他節(jié)點的相遇間隔時間服從指數(shù)截斷的冪律分布。

2.3 單個節(jié)點與其他節(jié)點的相遇次數(shù)

各節(jié)點與其他節(jié)點的相遇次數(shù)反映了該節(jié)點在網(wǎng)絡(luò)中的活躍程度。各節(jié)點在一定時間內(nèi)與其他節(jié)點的相遇次數(shù)成為對該節(jié)點中心度（Centrality）的一種度量方式[3]。

本文利用 MIT Reality Mining數(shù)據(jù)集中自2004年9～12月的節(jié)點相遇記錄對該隨機變量的分布函數(shù)形式進行分析，其中有65個節(jié)點有足夠多的樣本數(shù)據(jù)。與上一分析過程類似，本文將該隨機變量的分析結(jié)果分為：服從指數(shù)截斷的冪律分布、服從其他分布與不能判定的情況。如表2所示，在所分析的65個節(jié)點中，38個節(jié)點服從指數(shù)截斷的冪律分布，7個節(jié)點服從其他分布，其余27個節(jié)點不能判定。因此本文認為各節(jié)點與其他節(jié)點的相遇次數(shù)同樣服從指數(shù)截斷的冪律分布。

表2 單個節(jié)點與其他節(jié)點的相遇次數(shù)分布Table 2 Analysis results of contact times distribution between each single node and any other encountered nodes

3 分布式社團檢測

本文在移動節(jié)點相遇規(guī)律分析結(jié)論的基礎(chǔ)上，提出了動態(tài)分布式社團檢測算法，利用各節(jié)點的相遇歷史記錄對一定時間內(nèi)該節(jié)點與其他節(jié)點的累積相遇持續(xù)時間與相遇次數(shù)的均值進行計算，并作為動態(tài)閾值確定該節(jié)點的朋友集合（Familiar Set）。各節(jié)點在相遇時交換朋友集合的信息從而構(gòu)建本地關(guān)系圖，然后對各節(jié)點的本地關(guān)系圖進行多社團檢測。

3.1 確定朋友集合

本文對移動節(jié)點相遇規(guī)律分析結(jié)論指出：單個節(jié)點與其他節(jié)點的相遇間隔時間與相遇次數(shù)均服從指數(shù)截斷的冪律分布（Power law with exponential cutoff）的結(jié)論。指數(shù)截斷的冪律分布的一般形式為：

其中：C為標準化系數(shù)，可通過數(shù)值計算進行求解；函數(shù)Γ為不完全伽瑪函數(shù)；xmin為隨機變量的最小值。指數(shù)截斷的冪律分布的均值為：

本文分別對比了MIT Reality Mining數(shù)據(jù)集中各節(jié)點與其他節(jié)點的相遇間隔時間、相遇次數(shù)的理論均值與樣本均值（見圖3）。因推導(dǎo)隨機變量大于均值的概率較為復(fù)雜，本文對相遇次數(shù)大于樣本均值的節(jié)點所占的比例進行統(tǒng)計，研究指數(shù)截斷的冪律分布的均值對移動節(jié)點相遇規(guī)律的影響。

圖3 理論均值與樣本均值對比結(jié)果Fig.3 Comparison of theoretical and sample mean values

由圖4可以看出，相遇次數(shù)大于樣本均值的節(jié)點所占比例較小，而與這部分節(jié)點的相遇次數(shù)所占的比例則較高。

圖4 指數(shù)截斷的冪律分布均值對節(jié)點關(guān)系的影響Fig.4 Impact of mean value on node closeness

在固定長度的時間窗口中，各節(jié)點與其他節(jié)點的相遇間隔時間與累計相遇持續(xù)時間存在線性關(guān)系。結(jié)合對移動節(jié)點相遇規(guī)律分析的結(jié)論，本文提出利用一定時間內(nèi)各節(jié)點與其他節(jié)點的累積相遇持續(xù)時間、相遇次數(shù)的均值分別作為閾值，將累積相遇持續(xù)時間、相遇次數(shù)分別大于各自閾值的節(jié)點加入到朋友集合中。例如，節(jié)點vi的朋友集合Fi（T）定義如下：

其中：T是當(dāng)前滑動時間窗口長度；Fi（T）是節(jié)點vi在時間窗口T中的朋友集合；cij（T）是節(jié)點vi與節(jié)點vj在時間窗口T中的累積相遇持續(xù)時間；dij（T）是節(jié)點vi與節(jié)點vj在時間窗口T中的相遇次數(shù)。因此，各節(jié)點選擇累積相遇持續(xù)時間長并且相遇頻繁的節(jié)點作為朋友節(jié)點。

3.2 構(gòu)建節(jié)點關(guān)系圖

各節(jié)點在相遇時對各自的朋友集合進行交換，并構(gòu)建本地關(guān)系圖（Local social graph）。如圖5所示，各節(jié)點的本地關(guān)系圖是一個兩跳的自我中心網(wǎng)絡(luò)（Ego network）：圖的中心為各節(jié)點本身，第一跳節(jié)點（即與中心直接相連的節(jié)點）為該節(jié)點的朋友節(jié)點，而第二跳節(jié)點為各朋友節(jié)點的朋友節(jié)點。在關(guān)系圖中，每條邊表示所連接的兩個節(jié)點互為朋友關(guān)系。

3.3 分布式多社團檢測

圖5 節(jié)點本地關(guān)系圖Fig.5 Local Social Graph

在各節(jié)點的本地關(guān)系圖基礎(chǔ)上，本文利用FOCS算法[18]對本地關(guān)系圖中可能存在的一個或多個社團結(jié)構(gòu)進行檢測。圖6顯示了圖5中的中心節(jié)點所具有的多個社團結(jié)構(gòu)。

區(qū)別各節(jié)點的不同社團結(jié)構(gòu)有助于在消息轉(zhuǎn)發(fā)過程中提高傳輸成功率并縮短傳輸時延。例如，某學(xué)生屬于某個班級的同時又是某個研究室的成員。當(dāng)該學(xué)生向同班同學(xué)共享文件時，通過其研究室成員進行轉(zhuǎn)發(fā)的成功率通常比通過其他同班同學(xué)進行轉(zhuǎn)發(fā)的成功率低，而且消息經(jīng)過更多次轉(zhuǎn)發(fā)之后將引入額外的傳輸時延。

4 基于社團的源路由

圖6 多社團檢測結(jié)果Fig.6 Result of overlapped community detection

降低移動容遲網(wǎng)絡(luò)中的消息傳輸代價需要避免不必要的消息復(fù)制。消息在由源節(jié)點向目的節(jié)點的轉(zhuǎn)發(fā)過程中將經(jīng)過不同的社團結(jié)構(gòu)。社團內(nèi)部成員之間關(guān)系較為穩(wěn)定，而社團之間的關(guān)系體現(xiàn)為共同的社團成員。各節(jié)點具有相對穩(wěn)定的社團結(jié)構(gòu)也決定了社團之間的關(guān)系較為穩(wěn)定。利用社團之間的穩(wěn)定性，本文針對移動容遲網(wǎng)絡(luò)中的數(shù)據(jù)共享服務(wù)提出了基于社團的源路由算法（Social－based source routing，SSR）。

SSR算法將移動容遲網(wǎng)絡(luò)中的數(shù)據(jù)共享過程分為3個階段，包括：摘要消息廣播、興趣消息回傳與內(nèi)容數(shù)據(jù)轉(zhuǎn)發(fā)（見圖7），并且在各階段使用不同的消息格式以便降低數(shù)據(jù)共享過程中對節(jié)點資源的消耗。消息格式見圖8。

圖7 數(shù)據(jù)共享的3個階段Fig.7 Three phases of content sharing

4.1 摘要消息廣播

在摘要消息廣播階段，Content source針對每個共享數(shù)據(jù)生成摘要消息（Abstract message）并通知相遇節(jié)點。其中元數(shù)據(jù)描述字段的作用是提供基于內(nèi)容的服務(wù)[20]。Content source將當(dāng)前的社團成員列表作為社團路徑上的第一“跳”（Community－h(huán)op）添加到社團路徑字段。若Content source同時具有多個社團結(jié)構(gòu)，則該節(jié)點隨機選擇其中一個社團并添加到社團路徑字段中。

收到摘要消息的節(jié)點計算其當(dāng)前社團與社團路徑字段中的各社團之間的Jaccard相似度，從而判斷摘要消息是否已在社團中進行廣播。

若相似度大于或等于預(yù)先給定的閾值，說明已經(jīng)有社團成員收到該摘要消息，并且開始通知其他節(jié)點。為避免社團路徑產(chǎn)生環(huán)路（Loop），當(dāng)前節(jié)點保留從Content source到當(dāng)前節(jié)點所在社團的社團路徑，并將社團路徑上的其余部分刪除。若相似度小于預(yù)先給定的閾值，則該節(jié)點將其當(dāng)前社團追加到摘要消息中社團路徑字段的末尾。若當(dāng)前節(jié)點具有多個社團結(jié)構(gòu)，則該節(jié)點選擇其中的一個社團追加到社團路徑末尾。當(dāng)前節(jié)點將更新后的摘要消息通知其他相遇節(jié)點。

4.2 興趣消息回傳

隨著各節(jié)點在相遇時對摘要消息進行轉(zhuǎn)發(fā)，更多節(jié)點將獲得共享數(shù)據(jù)的摘要消息。另外，各節(jié)點收到針對同一共享數(shù)據(jù)的摘要消息數(shù)量也逐漸增多，使得Content consumer能夠從收到的摘要消息中選擇合適的社團路徑向Content source發(fā)送興趣消息（Interest message）。這一過程中，Content source與 Content consumer之間的關(guān)系僅針對當(dāng)前的共享數(shù)據(jù)而臨時建立。

Content consumer可以采用不同策略對連接Con－tent source的社團路徑進行選擇。當(dāng) Content consumer與其他節(jié)點相遇時，若相遇節(jié)點屬于社團路徑上的某個離Content source距離更近（即跳數(shù)更少）的社團，則Content consumer將興趣消息轉(zhuǎn)發(fā)給該節(jié)點，并將當(dāng)前社團標記設(shè)置為該相遇節(jié)點所屬社團在社團路徑上的跳數(shù)。因此興趣消息中的當(dāng)前社團標記字段始終指向當(dāng)前攜帶興趣消息的節(jié)點所在的社團。之后的各中繼節(jié)點重復(fù)以上過程，最終將興趣消息送達Content source。

在興趣消息回傳過程中，各中繼節(jié)點采用單副本轉(zhuǎn)發(fā)方式。盡管興趣消息中的社團路徑來自于之前收到的摘要消息，2個消息在實際轉(zhuǎn)發(fā)過程中可能由不同的中繼節(jié)點進行轉(zhuǎn)發(fā)（見圖7a與7b）。

4.3 內(nèi)容數(shù)據(jù)轉(zhuǎn)發(fā)

Content source收到興趣消息后利用其中包含的社團路徑將容量較大的內(nèi)容數(shù)據(jù)消息（Content message）發(fā)送至Content consumer。內(nèi)容數(shù)據(jù)消息的轉(zhuǎn)發(fā)過程與興趣消息的回傳過程類似，當(dāng)Content source與其他節(jié)點相遇時，若相遇節(jié)點屬于社團路徑上某個離Content consumer距離更近的社團，則 Content source將內(nèi)容數(shù)據(jù)消息轉(zhuǎn)發(fā)給該節(jié)點，并將內(nèi)容數(shù)據(jù)消息中的當(dāng)前社團標記設(shè)置為該節(jié)點所屬社團在社團路徑上的跳數(shù)。因此內(nèi)容數(shù)據(jù)消息中的當(dāng)前社團標記字段仍然指向當(dāng)前攜帶該消息的節(jié)點所屬的社團在社團路徑上的位置。各中繼節(jié)點重復(fù)該過程從而將內(nèi)容數(shù)據(jù)消息發(fā)送至Content consumer。

消息傳輸代價為網(wǎng)絡(luò)中消息副本總數(shù)與成功送達目的節(jié)點的消息總數(shù)的比值。通常，網(wǎng)絡(luò)中消息副本越多，傳輸代價則越高。相對于多副本轉(zhuǎn)發(fā)算法，SSR算法采用單副本方式對內(nèi)容數(shù)據(jù)消息進行轉(zhuǎn)發(fā)，從而降低消息復(fù)制對節(jié)點資源的需求與傳輸代價。各中繼節(jié)點在一定時間內(nèi)對內(nèi)容數(shù)據(jù)消息進行緩存，以便于其他Content consumer在請求該共享數(shù)據(jù)時縮短傳輸時延。

5 仿真結(jié)果與分析

本文利用基于實驗數(shù)據(jù)的仿真對SSR算法的性能進行驗證，主要從內(nèi)容數(shù)據(jù)消息的平均傳輸成功率、傳輸代價與傳輸時延3個方面與基于多副本轉(zhuǎn)發(fā)的Bubble rap算法[3]進行比較。

5.1 仿真環(huán)境

本文在The ONE模擬器[19]中實現(xiàn)了SSR算法，然后由MIT Reality Mining數(shù)據(jù)集中選取了時間跨度為1個月的數(shù)據(jù)段用于SSR算法與Bubble rap算法的仿真。該段數(shù)據(jù)包含有96個節(jié)點的19 440次相遇記錄。

對于SSR算法的仿真過程中，動態(tài)分布式社團檢測算法的滑動時間窗口長度設(shè)置為5d，滑動距離設(shè)置為1d。仿真過程中每隔1～2h從網(wǎng)絡(luò)中隨機選取一個節(jié)點作為Content source并生成共享數(shù)據(jù)，然后由Content source向其他相遇節(jié)點進行摘要消息廣播。摘要消息的容量設(shè)置為1kB，內(nèi)容數(shù)據(jù)的容量設(shè)置為2～6MB（服從均勻分布）。在每次仿真過程中總共約有500個內(nèi)容數(shù)據(jù)在網(wǎng)絡(luò)中被共享。根據(jù)收到摘要消息的節(jié)點對獲取共享數(shù)據(jù)的不同需求，收到摘要消息的節(jié)點以概率p向Content source回傳興趣消息（即成為該共享數(shù)據(jù)的Content consumer）。概率p的值越高則網(wǎng)絡(luò)中其他節(jié)點對共享數(shù)據(jù)的請求越多，網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量也越大，通過這種方式檢驗SSR算法在不同條件下的性能變化。另外，中繼節(jié)點緩存內(nèi)容數(shù)據(jù)消息的時間設(shè)置為6h。

在Bubble rap算法的仿真過程中，本文使用k－CLIQUE算法[12]對各節(jié)點進行分布式社團檢測，節(jié)點間相遇持續(xù)時間的閾值設(shè)為12h，參數(shù)k設(shè)置為5。對于節(jié)點中心度的計算使用C－Window中心度[3]，時間窗口長度為6h，時間窗口數(shù)設(shè)置為5。

由于Bubble rap算法中沒有摘要消息廣播過程，本文將SSR算法中生成的內(nèi)容數(shù)據(jù)消息（Content message）直接導(dǎo)入到Bubble rap算法的仿真過程中，即：將Content source作為Bubble rap算法中消息的源節(jié)點，而Content consumer作為消息的目的節(jié)點。對于SSR算法中由中繼節(jié)點緩存的內(nèi)容數(shù)據(jù)消息則將中繼節(jié)點作為Bubble rap算法中消息的源節(jié)點，從而保證了對比的公平性。

本文針對SSR算法使用不同的隨機數(shù)種子分別進行了10次仿真，相應(yīng)地對Bubble rap算法也進行了10次仿真。在2個算法的仿真過程中，各網(wǎng)絡(luò)節(jié)點的緩存容量均設(shè)置為100MB，無線傳輸速度均設(shè)置為250kb/s。

5.2 結(jié)果分析

5.2.1 傳輸成功率 消息傳輸成功率定義為成功送達目的節(jié)點的消息數(shù)量與網(wǎng)絡(luò)中生成的消息總數(shù)的比值。對比結(jié)果見圖9?？梢钥闯鯯SR算法在不同條件下具有相對穩(wěn)定的消息傳輸成功率。

對于Bubble rap算法，當(dāng)概率p較小時，各節(jié)點對共享數(shù)據(jù)的請求較少，因而網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量較小，使得各節(jié)點能夠利用可用緩存進行消息復(fù)制，從而能夠達到相對較高的消息傳輸成功率。當(dāng)概率p為0.1，消息生存時間為1d時，Bubble rap算法比SSR算法的消息傳輸成功率提高18%。

圖9 消息傳輸成功率對比結(jié)果Fig.9 Comparisons of message delivery rate

然而隨著概率p值的增大，各節(jié)點對共享數(shù)據(jù)的請求增多，網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量增大。對于多副本轉(zhuǎn)發(fā)算法，大量消息副本很快耗盡節(jié)點緩存，造成節(jié)點原先攜帶的消息失效。因此Bubble rap算法的消息傳輸成功率下降較為明顯。當(dāng)概率p為0.9，TTL為7d時，SSR算法比Bubble rap算法的消息傳輸成功率提高8%。

5.2.2 傳輸代價 消息傳輸代價定義為網(wǎng)絡(luò)中傳輸?shù)南⒏北究倲?shù)與成功送達目的節(jié)點的消息總數(shù)的比值。SSR算法采用基于單消息副本的轉(zhuǎn)發(fā)方式，消息傳輸代價等價于各消息在傳輸過程中的轉(zhuǎn)發(fā)次數(shù)。從圖10中可以看出SSR算法顯著降低了傳輸代價。當(dāng)概率p為0.9時，SSR算法的平均消息傳輸代價僅為Bubble rap算法的20%。

圖10 消息傳輸代價對比結(jié)果Fig.10 Comparisons of message delivery cost

從Bubble rap算法在不同條件下消息傳輸代價的變化可以看出：隨著概率p值的增大，各節(jié)點對共享數(shù)據(jù)的請求增多，同時緩存內(nèi)容數(shù)據(jù)消息的節(jié)點也相應(yīng)增多，使得更多的Content consumer可以從社團路徑上的中間節(jié)點獲得共享數(shù)據(jù)，從而降低了消息傳輸代價。

圖11 消息傳輸時延對比結(jié)果Fig.11 Comparisons of message delivery delay

5.2.3 傳輸時延 消息傳輸時延定義為消息在源節(jié)點的生成時間與在目的節(jié)點的接收時間之間的差值。對比結(jié)果如圖11所示。隨著概率p的增大，各節(jié)點對共享數(shù)據(jù)的請求增多，緩存內(nèi)容數(shù)據(jù)消息的節(jié)點也隨之增多。當(dāng)其他Content consumer請求相同的內(nèi)容數(shù)據(jù)時，緩存消息的中繼節(jié)點能夠直接將共享數(shù)據(jù)沿社團路徑發(fā)回Content consumer，因此縮短了消息傳輸時延。

相對于Bubble rap算法，SSR算法的消息傳輸時延較小。當(dāng)概率p值為0.1時，SSR算法的平均消息傳輸時延縮短了5.8h；當(dāng)概率p值為0.3時，SSR算法的平均消息傳輸時延縮短了3.7h。隨著概率p值繼續(xù)增大，2個算法的平均消息傳輸時延則逐漸接近。

6 結(jié)語

本文針對移動容遲網(wǎng)絡(luò)中的數(shù)據(jù)共享服務(wù)，提出了基于社團的源路由算法（Social－based Source Routing，SSR）。該算法避免了發(fā)布/訂閱模式中因Broker

節(jié)點失效而造成的數(shù)據(jù)無法共享問題。仿真結(jié)果表明該算法在一定條件下能夠達到與多副本轉(zhuǎn)發(fā)算法類似的消息傳輸成功率。由于對興趣消息與內(nèi)容數(shù)據(jù)消息的轉(zhuǎn)發(fā)采用了單副本轉(zhuǎn)發(fā)方式，該算法顯著降低了消息傳輸代價。今后將對社團路徑的選擇與優(yōu)化問題展開更深入的研究。

[1]Hui P，Chaintreau A，Gass R，et al.Pocket switched networks and human mobility in conference environments[C].Proceedings of the 2005ACM SIGCOMM workshop on Delay－tolerant networking（WDTN’05）.Philadelphia：ACM，2005：244－251.

[2]Daly E，Haahr M.Social network analysis for routing in disconnected delay－tolerant MANETs[C].Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing（MobiHoc’07）.Montreal：ACM，2007：32－40.

[3]Hui P，Crowcroft J，Yoneki E.Bubble rap：social－based forwarding in delay tolerant networks[J].IEEE Transactions on Mobile Computing，2011，10（11）：1576－1589.

[4]Li F，Wu J.LocalCom：a community－based epidemic forwarding scheme in disruption－tolerant networks[C].Proceedings of the 6th Annual IEEE communications society conference on Sensor，Mesh and Ad Hoc Communications and Networks（SECON’09）.Rome：IEEE Press，2009：574－582.

[5]Bulut E，Szymanski B K.Friendship Based Routing in Delay Tolerant Mobile Social Networks[C].Proceedings of the 2010Global Telecommunications Conference （GLOBECOM 2010），Miami：IEEE Press，2010：1－5.

[6]Li F，Wu J.MOPS：Providing Content－Based Service in Disruption－Tolerant Networks[C].Proceedings of the 2009 29th IEEE International Conference on Distributed Computing Systems（ICDCS’09）.Washington：IEEE Computer Society，2009：526－533.

[7]Boldrini C，Conti M，Passarella A.ContentPlace：social－aware data dissemination in opportunistic networks[C].Proceedings of the 11th international symposium on Modeling，analysis and simulation of wireless and mobile systems（MSWiM ’08）.Vancouver：ACM，2008：203－210.

[8]Yoneki E，Hui P，Chan S，et al.A socio－aware overlay for publish/subscribe communication in delay tolerant networks[C].Proceedings of the 10th ACM Symposium on Modeling，analysis，and simulation of wireless and mobile systems（MSWiM’07）.Chania：ACM，2007：225－234.

[9]Chaintreau A，Hui P，Crowcroft J，et al.Impact of Human Mobility on Opportunistic Forwarding Algorithms[J].IEEE Transactions on Mobile Computing，2007，6（6）：606－620.

[10]Karagiannis T，Boudec J Y L，Vojnovi M.Power law and exponential decay of inter contact times between mobile devices[C].Proceedings of the 13th annual ACM international conference on Mobile computing and networking （MobiCom ’07）.Montreal：ACM，2007：183－194.

[11]Tian Y，Li J.Heterogeneity of device contact process in pocket switched networks[C].Proceedings of the 5th international conference on Wireless algorithms，systems，and applications（WASA’10）.Beijing：Springer－Verlag，2010：157－166.

[12]Hui P，Yoneki E，Chan S，et al.Distributed community detection in delay tolerant networks[C].Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture（MobiArch’07）.Kyoto：ACM，2007：1－8.

[13]Herbiet G H，Bouvry P.SHARC：Community－based partitioning for mobile ad hoc networks using neighborhood similarity[C].Proceedings of the 2010IEEE International Symposium on A World of Wireless，Mobile and Multimedia Networks （WOWMOM’10）.Washington：IEEE Computer Society，2010：1－9.

[14]Gao W，Guohong Cao G.User－centric data dissemination in disruption tolerant networks[C].Proceedings of the 30th IEEE International Conference on Computer Communications（IEEE INFOCOM 2011）.Shanghai：IEEE Communications Society，2011：3119－3127.

[15]Kangasharju J，Ott J，Karkulahti O.Floating content：Information availability in urban environments[C].Proceedings of the 8th Fifth Annual IEEE International Conference on Pervasive Computing and Communications－Workshops（PerCom Workshops’10）.Mannheim：IEEE Computer Society，2010：804－808.

[16]Clauset A，Shalizi C R，Newman M E J.Power－Law Distributions in Empirical Data[J].SIAM Review，2009，51（4）：661－703.

[17]Eagle N，Pentland A.Reality mining：sensing complex social systems[J].Personal and Ubiquitous Computing，2006，10（4）：255－268.

[18]Nguyen N P，Dinh T N，Tokala S，et al.Overlapping communities in dynamic networks：their detection and mobile applications[C].Proceedings of the 17th annual international conference on Mobile computing and networking （MobiCom’11）.Las Vegas：ACM，2010：85－96.

[19]Ker－nen A，Ott J，K－rkk－inen T.The ONE simulator for DTN protocol evaluation[C].Proceedings of the 2nd International Conference on Simulation Tools and Techniques （Simutools’09）.Rome：ICST，2009：1－10.

[20]Jacobson V，Smetters D K，Thornton J D，et al.Networking named content[C].Proceedings of the 5th international conference on Emerging networking experiments and technologies（CoNEXT’09）.Rome：ACM，2012：1－12.