李 豪，陳志剛，吳 嘉

（1．中南大學軟件學院，長沙410075；2．“移動醫(yī)療”教育部－中國移動聯(lián)合實驗室，長沙410083）

1 概述

機會網(wǎng)絡源于容忍延遲網(wǎng)絡與移動自組網(wǎng)［1］。在機會網(wǎng)絡中，網(wǎng)絡規(guī)模沒有進行事先設置，節(jié)點位置不固定，節(jié)點間不要求有確定的鏈路，依靠節(jié)點運動創(chuàng)造的通信條件逐跳地傳輸消息，采用“存儲－攜帶－轉(zhuǎn)發(fā)”的方式完成消息傳輸［2］。機會網(wǎng)絡不要求存在貫穿始終的端到端連接，不依賴基礎設施，可以滿足惡劣條件下的網(wǎng)絡通信需要，其典型應用包括野生動物研究、手持設備組網(wǎng)、車載網(wǎng)絡、偏遠地區(qū)網(wǎng)絡覆蓋等。

在機會網(wǎng)絡特定應用環(huán)境中，由于終端攜帶者為社會成員，網(wǎng)絡表現(xiàn)出社會特性，稱這種網(wǎng)絡為機會社會網(wǎng)絡［3］。與一般的機會網(wǎng)絡中節(jié)點迅速運動、網(wǎng)絡拓撲結(jié)構(gòu)快速改變不同，在機會社會網(wǎng)絡中，人與人之間的社會關系比較穩(wěn)定，并且表現(xiàn)出關聯(lián)性。網(wǎng)絡中關系密切的節(jié)點聚集在一起，進而產(chǎn)生社區(qū)。同一社區(qū)中節(jié)點間的交互次數(shù)較多，來自不同社區(qū)的節(jié)點間交互次數(shù)較少，有的節(jié)點比較活躍，與較多的節(jié)點接觸，體現(xiàn)了較高的社會性［4］。

針對目前廣泛分布的由人持有通信機器構(gòu)成的機會社會網(wǎng)絡，本文提出一種基于社區(qū)和社會性［5］的機會網(wǎng)絡路由算法（Opportunistic Network routing algorithm based on Community and Sociality，ONCS）。該算法周期性地統(tǒng)計節(jié)點間的相遇頻繁程度，把機會社會網(wǎng)絡中的節(jié)點動態(tài)劃分為多個社區(qū)，使用目標社區(qū)的節(jié)點充當中介節(jié)點，提高消息傳輸成功率；使用社會性高的節(jié)點充當中繼節(jié)點，驅(qū)動消息的轉(zhuǎn)發(fā)。

2 相關工作

在機會網(wǎng)絡中，信息轉(zhuǎn)發(fā)是指信息由源節(jié)點經(jīng)過一跳或者多跳傳輸?shù)侥繕斯?jié)點的過程。如何有效地進行信息轉(zhuǎn)發(fā)是目前機會網(wǎng)絡研究的重要領域。

文獻［6］提出了Spray and Wait（SW）算法，該算法分為2個過程：Spray和 Wait。在Spray過程中，源節(jié)點中每個數(shù)據(jù)分組向網(wǎng)絡中注入固定數(shù)目L的數(shù)據(jù)分組副本，L是算法參數(shù)，可以設定。然后進入Wait過程，假如數(shù)據(jù)分組副本在上一過程未找到目標節(jié)點，則帶有數(shù)據(jù)分組副本的L個節(jié)點采用直接傳輸?shù)牟呗詫?shù)據(jù)分組副本傳輸?shù)侥繕斯?jié)點。

文獻［7］提出的PRoPHET算法則基于概率策略，該算法定義了一系列公式預測消息成功傳輸?shù)母怕?。當?jié)點相遇時，節(jié)點重新計算彼此的預測成功傳輸概率，根據(jù)更新后的概率選擇性地復制數(shù)據(jù)分組。實驗結(jié)果表明，PRoPHET算法在社區(qū)場景中的性能較優(yōu)。

文獻［8］提出了一種基于社區(qū)的機會網(wǎng)絡消息傳輸算法（Community－based Message Transmission Scheme，CMTS），該算法按節(jié)點間的相遇頻率將網(wǎng)絡劃分為許多個社區(qū)，自適應地控制消息的副本數(shù)目，并通過活躍節(jié)點把消息轉(zhuǎn)發(fā)到目標社區(qū)。算法嚴格控制消息拷貝數(shù)量與轉(zhuǎn)發(fā)條件，在提高投遞率的同時減小了路由開銷。

文獻［9］提出了機會網(wǎng)絡中基于社區(qū)的轉(zhuǎn)發(fā)算法Bubble Rap，根據(jù)節(jié)點間的交互次數(shù)記錄得到節(jié)點的活躍度，體現(xiàn)節(jié)點作為潛在報文轉(zhuǎn)發(fā)中繼節(jié)點的概率。該算法將所有節(jié)點按照活躍度排序，得到2個排名：全局排名與社區(qū)排名。算法路由策略如下：節(jié)點把報文發(fā)送至全局排名比自己大的節(jié)點，直至把報文發(fā)送至目標社區(qū)節(jié)點。此節(jié)點再把報文發(fā)送至社區(qū)排名比自己大的節(jié)點，直至和目標節(jié)點相遇。該算法考慮活躍度高的節(jié)點與更多其他節(jié)點交互的特點，通過活躍度高的節(jié)點驅(qū)動報文轉(zhuǎn)發(fā)，其采用一個副本的策略，投遞率低，轉(zhuǎn)發(fā)延遲高。

3 ONCS算法

3．1 社區(qū)的動態(tài)劃分策略

由于人與人之間的社會關系，人類表現(xiàn)出聚集現(xiàn)象，整個社會被分割為許多個社區(qū)。同一社區(qū)的節(jié)點間比不同社區(qū)的節(jié)點間交流更加密切。社區(qū)內(nèi)所有節(jié)點能夠通過直接連接或間接連接到達。

同一社區(qū)中節(jié)點間的交互次數(shù)較多。來自不同社區(qū)的節(jié)點間的交互次數(shù)較少。所以，根據(jù)節(jié)點的相遇頻率把網(wǎng)絡劃分成許多個社區(qū)。

定義1 數(shù)據(jù)分組平均傳輸時間t—，表示節(jié)點完整傳輸數(shù)據(jù)分組所需平均時間，等于數(shù)據(jù)分組平均大小除以數(shù)據(jù)傳輸速率。

定義2 穩(wěn)定連接。每個節(jié)點記錄和其他節(jié)點的相遇情況，若節(jié)點a與節(jié)點b連接時間t大于等于數(shù)據(jù)分組平均傳輸時間t—，則節(jié)點a與節(jié)點b穩(wěn)定連接次數(shù)加1。

定義3 強連接。在指定的統(tǒng)計周期T內(nèi)，若節(jié)點a與節(jié)點b穩(wěn)定連接次數(shù)大于閾值λ，則認為節(jié)點a與節(jié)點b之間存在強連接。

在指定的統(tǒng)計周期T內(nèi)，節(jié)點之間存在強連接，即節(jié)點之間穩(wěn)定連接次數(shù)大于閾值λ，節(jié)點對之間才可以用邊連接。本文使用8個節(jié)點圖示說明社區(qū)劃分算法，示例取穩(wěn)定連接次數(shù)閾值λ為3。當節(jié)點穩(wěn)定連接次數(shù)矩陣表示為式（1）時，社區(qū)劃分結(jié)構(gòu)表示如圖1所示。在式（1）中，矩陣中第i行j列元素表示節(jié)點i與節(jié)點j之間的穩(wěn)定連接次數(shù)，對角線上第i行i列元素值為∞，表示節(jié)點與自身不會存在穩(wěn)定連接。在圖1中，左邊節(jié)點1～節(jié)點4劃分為一個社區(qū)，右邊節(jié)點5～節(jié)點8劃分為一個社區(qū)。

圖1 社區(qū)劃分結(jié)果

社區(qū)結(jié)構(gòu)在短周期中保持不變，經(jīng)過一段時間，因為節(jié)點運動、節(jié)點動態(tài)加入或離開（比如節(jié)點能量耗盡），節(jié)點間的社會關系將發(fā)生改變，社區(qū)結(jié)構(gòu)也將相應發(fā)生改變。所以，本文周期性地對節(jié)點對的穩(wěn)定連接次數(shù)進行統(tǒng)計，相應地，周期性地劃分網(wǎng)絡社區(qū)結(jié)構(gòu)。

考慮到社區(qū)內(nèi)節(jié)點交互次數(shù)較多的特點，假如把消息發(fā)送至目標社區(qū)的其他節(jié)點，則它和目標節(jié)點相遇的概率很大，使消息傳輸?shù)侥繕斯?jié)點的概率增大。如果源節(jié)點與目標節(jié)點處于同一社區(qū)，由社區(qū)內(nèi)其他節(jié)點中繼轉(zhuǎn)發(fā)消息，則消息就能高效地傳輸?shù)竭_。把消息限制在社區(qū)內(nèi)轉(zhuǎn)發(fā)，不需要傳輸?shù)缴鐓^(qū)外相遇不頻繁的節(jié)點。同樣地，在社區(qū)間進行消息傳輸時，使用社會性高的節(jié)點充當中繼節(jié)點，通過它們把消息發(fā)送至目標社區(qū)，進而完成消息的高效轉(zhuǎn)發(fā)。

3．2 節(jié)點社會性度量

在機會社會網(wǎng)絡中，節(jié)點的社會性表現(xiàn)為節(jié)點的通信能力和中繼能力。文獻［10］提出選擇介數(shù)中心性與相似性作為社會性度量的2個考慮因素。介數(shù)中心性是節(jié)點連接其他節(jié)點路徑能力的度量，它測量節(jié)點落在2個其他節(jié)點的最短路徑上的次數(shù)，能夠體現(xiàn)節(jié)點作為消息轉(zhuǎn)發(fā)中繼節(jié)點的重要性。相似性度量節(jié)點和目標節(jié)點的共同鄰居數(shù)，體現(xiàn)節(jié)點和目標節(jié)點相遇的概率。節(jié)點的社會性由介數(shù)中心性和相似性構(gòu)成。

節(jié)點N的介數(shù)中心性表示為BetN，節(jié)點N所遇到的節(jié)點之間的連接能夠用一個K×K的對稱矩陣A來表示，其中，K代表節(jié)點N遇到的節(jié)點數(shù)目。假如矩陣行與列所表示的節(jié)點之間存在連接，那么矩陣A中元素Aij的值為1，否則為0。BetN值的計算公式為：

對式（2）計算進行圖示說明。當網(wǎng)絡連接如圖2所示時，節(jié)點 w8的對稱矩陣A 如式（3）所示，A2［1－A］計算結(jié)果如式（4）所示，其中，A與A 進行矩陣相乘，得到的矩陣再與［1－A］得到的矩陣進行點乘（矩陣對應的元素相乘），得到結(jié)果矩陣。

圖2 網(wǎng)絡連接圖

由于A2［1－A］是對稱的，因此只需要考慮對角線上的非零元素。A2［1－A］對角線上剩余的非零元素為3，倒數(shù)為0．33，即節(jié)點w8的介數(shù)中心性為0．33。

節(jié)點N與目標節(jié)點D的相似性表示為：

其中，NN與ND分別表示節(jié)點N與節(jié)點D遇到的節(jié)點的集合。

本文假定節(jié)點N需要將消息傳輸給目標節(jié)點D。當節(jié)點N遇到M時，節(jié)點N相對于節(jié)點M的介數(shù)中心性效用和相似性效用的計算公式如下：

節(jié)點N把消息傳輸給目標節(jié)點D，社會性的整體效用計算如下：

其中，α與β是可變參數(shù)，分別表示介數(shù)中心性效用與相似性效用在社會性計算中的權(quán)重，α＋β＝1。

通過以上公式可以計算節(jié)點N到目標節(jié)點D的社會性效用。當節(jié)點在社區(qū)中移動時，選擇社會性效用大于自己的節(jié)點充當消息轉(zhuǎn)發(fā)的中繼節(jié)點。

3．3 算法設計

本文算法的設計思路如下：

鄭君之死，是我從有關他的訃告上得知的。本來，死亡的原因是訃告的一個要件，然那個訃告沒有他死亡的原因。后來，我得知他是死于其逆子的刀下。

（1）人們在社會中有不同的受歡迎程度，機會社會網(wǎng)絡中的節(jié)點也一樣，轉(zhuǎn)發(fā)策略的第1部分是將消息轉(zhuǎn)發(fā)給比當前節(jié)點更受歡迎（社會性更高）的節(jié)點。

（2）人們在社會生活中形成社區(qū)，機會社會網(wǎng)絡中的節(jié)點也一樣，轉(zhuǎn)發(fā)策略的第2部分是動態(tài)劃分社區(qū)，將消息往目標節(jié)點社區(qū)轉(zhuǎn)發(fā)。

對于本文算法，做出如下假定：（1）節(jié)點屬于一個或多個社區(qū)；（2）節(jié)點有一個到達目標節(jié)點的社會性效用。

轉(zhuǎn)發(fā)的具體實現(xiàn)步驟如下：在社區(qū)外，節(jié)點首先按照社會性排行，將消息轉(zhuǎn)發(fā)給社會性更高的節(jié)點，直至和目標社區(qū)節(jié)點相遇，將消息轉(zhuǎn)發(fā)給目標社區(qū)節(jié)點；然后在社區(qū)內(nèi)使用社會性排行，將消息發(fā)送至社會性更高的節(jié)點，直至遇到目標節(jié)點。節(jié)點不需要了解系統(tǒng)中所有其他節(jié)點的排名，只要求和相遇節(jié)點的排名進行比較，使用貪心策略轉(zhuǎn)發(fā)消息。為了降低路由開銷，本文規(guī)定，當消息由社區(qū)外傳入社區(qū)內(nèi)時，之前的消息攜帶者將消息從緩存中刪除，阻止繼續(xù)在社區(qū)外轉(zhuǎn)發(fā)。

對于每個相遇節(jié)點，滿足以下4種情況則進行消息轉(zhuǎn)發(fā)：

（1）如果相遇節(jié)點為目標節(jié)點，目標節(jié)點復制消息，當前節(jié)點刪除消息。全局廣播消息成功到達確認消息，在網(wǎng)絡中刪除指定源節(jié)點和目標節(jié)點的消息，結(jié)束消息轉(zhuǎn)發(fā)。

（2）如果當前節(jié)點和目標節(jié)點社區(qū)相同，并且相遇節(jié)點和目標節(jié)點社區(qū)相同并且相遇節(jié)點社會性大于當前節(jié)點，相遇節(jié)點復制消息。

（3）如果當前節(jié)點和目標節(jié)點社區(qū)不同，并且相遇節(jié)點和目標節(jié)點社區(qū)相同，相遇節(jié)點復制消息，當前節(jié)點刪除消息。

（4）如果當前節(jié)點和目標節(jié)點社區(qū)不同，并且相遇節(jié)點社會性大于當前節(jié)點，相遇節(jié)點復制消息。

消息由社區(qū)外傳入社區(qū)內(nèi)時，中繼節(jié)點復制消息，當前節(jié)點刪除消息，把消息限制在社區(qū)內(nèi)轉(zhuǎn)發(fā)，減小路由開銷。

算法偽代碼如下：

算法 基于社區(qū)和社會性的機會網(wǎng)絡路由算法ONCS

其中，ETNode表示相遇節(jié)點；CNode表示當前節(jié)點；DNode表示目標節(jié)點；Community（Node）表示節(jié)點的社區(qū)；SimBetUtil（Node）表示節(jié)點的社會性。

由ONCS算法可知，在由人攜帶的移動設備組成的機會社會網(wǎng)絡場景中，當社區(qū)結(jié)構(gòu)劃分合理時，消息進入目標社區(qū)后，將消息限制在目標社區(qū)內(nèi)轉(zhuǎn)發(fā)，效率相對未考慮節(jié)點社區(qū)性質(zhì)的算法將有很大提升。當節(jié)點社會性梯度明顯時，消息不停由社會性低的節(jié)點發(fā)送至社會性高的節(jié)點，最終轉(zhuǎn)發(fā)到目標節(jié)點，效率相對沒有考慮社會性的算法將有很大提升。但該算法可能存在不足：當節(jié)點與其他節(jié)點穩(wěn)定連接次數(shù)都較少時，節(jié)點自身將成為離群點，形成孤立社區(qū)，路由算法效率會有所降低。

4 仿真實驗與結(jié)果分析

4．1 仿真場景及算法參數(shù)

本文 使 用 ONE（Opportunistic Network Environ－ment）［11］仿真環(huán)境模擬持有智能藍牙設備的行人于真實城市步行的場景，實現(xiàn)算法ONCS，并與Spray and Wait和PRoPHET算法進行性能比較。選用傳輸成功率、傳輸延遲、路由開銷3個性能指標［12］對算法進行分析。仿真場景設置如表1所示，算法參數(shù)設置如表2所示。

表1 仿真場景設置

表2 算法參數(shù)設置

通過實驗表明，當λ＝3，α＝0．5，β＝0．5時，ONCS算法性能綜合最優(yōu)。

4．2 實驗結(jié)果分析

4．2．1 社區(qū)劃分周期對消息傳輸成功率的影響

社區(qū)劃分周期對消息傳輸成功率的影響如圖3所示（本文算法結(jié)果），該圖表明，當選取較小的社區(qū)劃分周期時，由于社區(qū)結(jié)構(gòu)仍不穩(wěn)定，造成社區(qū)劃分對路由算法指導效果不佳，傳輸成功率較低。隨著劃分周期增大，傳輸成功率相應提高。周期選取為900 s時，算法取得最高的傳輸成功率82%。隨著劃分周期繼續(xù)增大，傳輸成功率下降。周期選取為2 700 s時，傳輸成功率是62%，算法性能比周期選取為900 s時的算法性能差。由于社區(qū)劃分周期過大，節(jié)點間的社會關系發(fā)生變化，之前的社區(qū)劃分結(jié)果不能很好地表示最新的社區(qū)結(jié)構(gòu)。

圖3 社區(qū)劃分周期對消息傳輸成功率的影響

4．2．2 節(jié)點緩存對路由算法的影響

Spray and Wait算法、PRoPHET算法和ONCS算法在不同節(jié)點緩存大小下的消息傳輸成功率如圖4所示。該圖表明，節(jié)點緩存較小時傳輸成功率都較低，這是因為節(jié)點緩存有限，丟棄消息。從趨勢上看，增大節(jié)點緩存，傳輸成功率相應提高。ONCS算法利用網(wǎng)絡中的強連接把網(wǎng)絡劃分成許多個社區(qū)，通過社會性高的節(jié)點驅(qū)動消息轉(zhuǎn)發(fā)，將消息逐漸向更接近目標節(jié)點的中繼節(jié)點轉(zhuǎn)發(fā)，與目標社區(qū)節(jié)點相遇后將消息限制在目標社區(qū)內(nèi)轉(zhuǎn)發(fā)，相對于Spray and Wait算法被動等待與目標節(jié)點相遇、PRoPHET算法利用傳輸概率選擇性地復制數(shù)據(jù)分組策略更優(yōu)，傳輸成功率也高于上述2種算法。

圖4 節(jié)點緩存對消息傳輸成功率的影響

節(jié)點緩存對消息傳輸延遲的影響如圖5所示。該圖表明，隨著節(jié)點緩存增大，各算法傳輸延遲增大。PRoPHET算法基于簡單概率策略，節(jié)點與目標節(jié)點遇到的可能性相對較小，傳輸延遲最大；ONCS算法利用社會性高的節(jié)點轉(zhuǎn)發(fā)消息，即同時考慮節(jié)點的介數(shù)中心性和與目標節(jié)點的相似性，將消息逐漸向更接近目標節(jié)點的中繼節(jié)點轉(zhuǎn)發(fā)，與目標社區(qū)節(jié)點相遇后將消息限制在目標社區(qū)內(nèi)轉(zhuǎn)發(fā)，限制消息的傳輸范圍，進而減少消息的傳輸延遲，傳輸延遲最??；Spray and Wait算法復制完消息后通過Direct Delivery的方式將消息傳輸?shù)侥繕斯?jié)點，等待與目標節(jié)點相遇，傳輸延遲也較大。

圖5 節(jié)點緩存對消息傳輸延遲的影響

節(jié)點緩存對路由開銷的影響如圖6所示。該圖表明，ONCS算法和PRoPHET算法隨著節(jié)點緩存的增加路由開銷會顯著減少。SW算法受節(jié)點緩存影響不大。Spray and Wait算法在Spray階段復制消息，在 Wait階段通過Direct Delivery的方式，遇到目標節(jié)點才轉(zhuǎn)發(fā)消息，路由開銷穩(wěn)定，在3種算法中也最小。PRoPHET算法簡單地利用概率策略轉(zhuǎn)發(fā)消息，路由開銷最大。ONCS算法把消息選擇性地發(fā)送至目標社區(qū)節(jié)點或社會性更高的節(jié)點，利用具有社會特性的轉(zhuǎn)發(fā)策略有效降低路由開銷，路由開銷適中，在路由開銷指標可接受的情況下能有效提高消息傳輸成功率，降低傳輸延遲。

圖6 節(jié)點緩存對路由開銷的影響

5 結(jié)束語

本文提出一種基于社區(qū)和社會性的機會網(wǎng)絡路由算法（ONCS）。按照節(jié)點間的穩(wěn)定連接次數(shù)選取節(jié)點間的強連接，將網(wǎng)絡動態(tài)劃分成多個社區(qū)，根據(jù)介數(shù)中心性和相似性定義社會性，選取社會性高的節(jié)點作為中繼節(jié)點，帶動消息轉(zhuǎn)發(fā)，將消息逐漸向與目標節(jié)點相同社區(qū)的節(jié)點或社會性高的節(jié)點轉(zhuǎn)發(fā)，最后傳輸?shù)侥繕斯?jié)點。

仿真結(jié)果表明，ONCS算法通過選擇性復制消息，在路由開銷指標適中的情況下，具有較高的傳輸成功率和較低的傳輸延遲，適用于由人持有移動設備構(gòu)成的機會社會網(wǎng)絡場景。下一步將繼續(xù)優(yōu)化社區(qū)動態(tài)劃分策略，使ONCS算法適用于實際場景。

［1］熊永平，孫利民，牛建偉，等．機會網(wǎng)絡［J］．軟件學報，2009，20（1）：124－137．

［2］劉亞翃，高 媛，喬晉龍，等．機會社會網(wǎng)絡中基于社區(qū)的消息傳輸算法［J］．計算機應用，2013，33（5）：1212－1216．

［3］Pietil?nen A K，Diot C．Dissemination in Opportunistic Social Networks：The Role of Temporal Communities［C］／／Proceedings of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing．New York，USA：ACM Press，2012：165－174．

［4］蔡青松，牛建偉，劉 暢．一種機會網(wǎng)絡中的消息發(fā)布／訂閱算法［J］．計算機工程，2011，37（12）：19－22，25．

［5］Nguyen H A，Giordano S．Context Information Prediction for Social－based Routing in Opportunistic Networks［J］．Ad Hoc Networks，2012，10（8）：1557－1569．

［6］Spyropoulos T，Psounis K，Raghavendra C S．Spray and Wait：An Efficient Routing Scheme for Intermittently Connected Mobile Networks ［C］／／Proceedings of ACM SIGCOMM Workshop on Delaytolerant Networking．New York，USA：ACM Press，2005：252－259．

［7］Lindgren A，Doria A，Schelén O．Probabilistic Routing in Intermittently Connected Networks ［J］． ACM SIGMOBILE：Mobile Computing and Communications Review，2003，7（3）：19－20．

［8］牛建偉，周 興，劉 燕，等．一種基于社區(qū)機會網(wǎng)絡的消息傳輸算法［J］．計算機研究與發(fā)展，2009，46（12）：2068－2075．

［9］Hui P，Crowcroft J，Yoneki E．BUBBLE Rap：Socialbased Forwarding in Delay－tolerant Networks［J］．IEEE Transactions on Mobile Computing，2011，10（11）：1576－1589．

［10］Daly E M，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．New York，USA：ACM Press，2007：32－40．

［11］王 朕，王新華，隋敬麒．機會網(wǎng)絡模擬器ONE及其擴展研究［J］．計算機應用研究，2012，29（1）：272－277．

［12］孫踐知，劉乃瑞，張迎新，等．機會網(wǎng)絡典型路由算法性能分析［J］．計算機工程，2011，37（16）：86－89．