基于社團(tuán)的移動(dòng)容遲網(wǎng)絡(luò)源路由算法＊

胡 桐，郭忠文，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è)備（如智能手機(jī)、平板電腦等）得到普及，利用數(shù)量龐大的手持設(shè)備組成分布式網(wǎng)絡(luò)（Pocket Switched Network，PSN[1]）并提供不依賴于網(wǎng)絡(luò)基礎(chǔ)設(shè)施的網(wǎng)絡(luò)服務(wù)成為了移動(dòng)容遲網(wǎng)絡(luò)的1個(gè)新的應(yīng)用場景。

在由手持設(shè)備組成的移動(dòng)容遲網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)（即手持設(shè)備）由人隨身攜帶，節(jié)點(diǎn)間利用移動(dòng)相遇帶來的通信機(jī)會轉(zhuǎn)發(fā)消息。設(shè)備攜帶者之間的社團(tuán)（Community）關(guān)系對消息的轉(zhuǎn)發(fā)過程影響較大。一方面，相對于不斷變化的網(wǎng)絡(luò)拓?fù)洌O(shè)備攜帶者間的社團(tuán)關(guān)系較為穩(wěn)定，屬于相同社團(tuán)的節(jié)點(diǎn)相遇的概率遠(yuǎn)遠(yuǎn)大于屬于不同社團(tuán)的節(jié)點(diǎn)相遇的概率。另一方面，設(shè)備攜帶者在網(wǎng)絡(luò)中的活躍程度存在差異，造成了節(jié)點(diǎn)具有不同的中心度（Centrality），具有較高中心度的節(jié)點(diǎn)具有更多的消息轉(zhuǎn)發(fā)機(jī)會?；谏鐣W(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é)點(diǎn)間的發(fā)布/訂閱關(guān)系由代理節(jié)點(diǎn)（Broker）維護(hù)，共享數(shù)據(jù)在Broker節(jié)點(diǎn)之間進(jìn)行轉(zhuǎn)發(fā)，因而Broker節(jié)點(diǎn)失效將造成數(shù)據(jù)無法共享。此外，節(jié)點(diǎn)間共享的數(shù)據(jù)容量較大（例如包含圖片或音視頻的消息），通過增加冗余消息副本來提高傳輸成功率的方法將造成較高的消息傳輸代價(jià)。

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

1 相關(guān)工作

1.1 移動(dòng)節(jié)點(diǎn)相遇規(guī)律分析

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

1.2 分布式社團(tuán)檢測

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

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

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

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

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

2 移動(dòng)節(jié)點(diǎn)相遇規(guī)律分析

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

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

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

2.2 單個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇間隔時(shí)間

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

結(jié)合對數(shù)似然比值的符號與檢驗(yàn)p值的大小，本文對該隨機(jī)變量的分析結(jié)果進(jìn)行了分類：（1）服從指數(shù)截?cái)嗟膬缏煞植?；?）服從其他分布；（3）不能判定的情況，即不能通過檢驗(yàn)p值對數(shù)似然比值的符號進(jìn)行判定。結(jié)果見表1。在所分析的82個(gè)節(jié)點(diǎn)中，48個(gè)節(jié)點(diǎn)服從指數(shù)截?cái)嗟膬缏煞植迹?個(gè)節(jié)點(diǎn)服從其他分布，其余27個(gè)節(jié)點(diǎn)不能判定。由于服從指數(shù)截?cái)嗟膬缏煞植嫉墓?jié)點(diǎn)數(shù)量較多，因此本文認(rèn)為各節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇間隔時(shí)間服從指數(shù)截?cái)嗟膬缏煞植肌?/p>

2.3 單個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇次數(shù)

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

本文利用 MIT Reality Mining數(shù)據(jù)集中自2004年9～12月的節(jié)點(diǎn)相遇記錄對該隨機(jī)變量的分布函數(shù)形式進(jìn)行分析，其中有65個(gè)節(jié)點(diǎn)有足夠多的樣本數(shù)據(jù)。與上一分析過程類似，本文將該隨機(jī)變量的分析結(jié)果分為：服從指數(shù)截?cái)嗟膬缏煞植?、服從其他分布與不能判定的情況。如表2所示，在所分析的65個(gè)節(jié)點(diǎn)中，38個(gè)節(jié)點(diǎn)服從指數(shù)截?cái)嗟膬缏煞植迹?個(gè)節(jié)點(diǎn)服從其他分布，其余27個(gè)節(jié)點(diǎn)不能判定。因此本文認(rèn)為各節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇次數(shù)同樣服從指數(shù)截?cái)嗟膬缏煞植肌?/p>

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

3 分布式社團(tuán)檢測

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

3.1 確定朋友集合

本文對移動(dòng)節(jié)點(diǎn)相遇規(guī)律分析結(jié)論指出：單個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇間隔時(shí)間與相遇次數(shù)均服從指數(shù)截?cái)嗟膬缏煞植迹≒ower law with exponential cutoff）的結(jié)論。指數(shù)截?cái)嗟膬缏煞植嫉囊话阈问綖椋?/p>

其中：C為標(biāo)準(zhǔn)化系數(shù)，可通過數(shù)值計(jì)算進(jìn)行求解；函數(shù)Γ為不完全伽瑪函數(shù)；xmin為隨機(jī)變量的最小值。指數(shù)截?cái)嗟膬缏煞植嫉木禐椋?/p>

本文分別對比了MIT Reality Mining數(shù)據(jù)集中各節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇間隔時(shí)間、相遇次數(shù)的理論均值與樣本均值（見圖3）。因推導(dǎo)隨機(jī)變量大于均值的概率較為復(fù)雜，本文對相遇次數(shù)大于樣本均值的節(jié)點(diǎn)所占的比例進(jìn)行統(tǒng)計(jì)，研究指數(shù)截?cái)嗟膬缏煞植嫉木祵σ苿?dòng)節(jié)點(diǎn)相遇規(guī)律的影響。

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

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

圖4 指數(shù)截?cái)嗟膬缏煞植季祵?jié)點(diǎn)關(guān)系的影響Fig.4 Impact of mean value on node closeness

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

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

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

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

3.3 分布式多社團(tuán)檢測

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

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

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

4 基于社團(tuán)的源路由

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

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

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

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

4.1 摘要消息廣播

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

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

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

4.2 興趣消息回傳

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

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

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

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

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

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

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

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

5.1 仿真環(huán)境

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

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

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

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

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

5.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

6 結(jié)語

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

節(jié)點(diǎn)失效而造成的數(shù)據(jù)無法共享問題。仿真結(jié)果表明該算法在一定條件下能夠達(dá)到與多副本轉(zhuǎn)發(fā)算法類似的消息傳輸成功率。由于對興趣消息與內(nèi)容數(shù)據(jù)消息的轉(zhuǎn)發(fā)采用了單副本轉(zhuǎn)發(fā)方式，該算法顯著降低了消息傳輸代價(jià)。今后將對社團(tuán)路徑的選擇與優(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.