移動社交網絡中一種基于社交關系的自適應路由算法?

黃嘉玲 李建波 李 英

（青島大學計算機科學技術學院 青島 266071）

1 引言

容遲網絡（Delay Tolerant Network，DTN）最初是為星際網絡（InterPlanetary Network，IPN）通信而提出來的，其主要目標是針對時延長、鏈路連接間歇性等特點的網絡，進行互聯和互操作［1］。現在，IPN的研究者將其架構應用在其他的挑戰性網絡中，如移動社交網絡（MSNs）［2～3］、車載自組網絡［4～5］、軍事網絡［6］等。移動社交網絡作為容遲網絡應用中的一種，一直是國內外研究的主要趨勢，隨著移動智能終端的迅速發展和普及，社交網絡已將其業務擴展到移動終端，其主要由無線便攜式設備形成，例如由人類攜帶的iPad、PDA、智能手機等。由于節點的隨機移動性，任何兩個節點之間不存在持久連接，因此數據傳輸通常采用“存儲—攜帶—轉發”通信模式：節點向相遇節點發送消息，接收消息的節點攜帶該消息直到遇到可發送的其他節點，以便該消息到達目的節點，這是MSNs中數據傳輸和路由的基本原理。但從源節點到目的地的路徑是間歇性連接的，導致常規路由協議通常不適用，因此路由成為MSNs中極具挑戰性的一個問題［7］。

早期 Vahdat和 Becker提出了 Epidemic［8］算法，一種針對在間歇性連接網絡中進行的路由協議，該算法是最簡單的復制路由協議。每個用戶維護一個數據隊列，當兩個用戶相遇時只傳輸對方沒有存儲的數據，顯然Epidemic Routing在路由算法中具有較高的數據傳輸成功率，但是這種不受限制的復制消息策略也帶來了極大的網絡開銷。為了克服Epidemic算法帶來的過量副本問題，T.Spyropoulos等人提出了經典的 Spray and Wait算法［9］，首先，在Spray階段該算法將復制副本折半傳輸給所有相遇鄰居節點來改進傳統傳輸機制；其次，在消息副本僅剩一個時候，進入等待階段，此時節點僅將消息傳遞于目的節點。Lindgren等［10］使用節點相遇和傳輸的歷史數據，計算節點之間的轉發概率，并提出了基于轉發概率的路由協議Prophet。在文獻［11］中，普通節點采用隨機運動，輪渡節點協助普通節點沿著恒定路徑傳遞消息。這解決了傳統DTN中的許多問題，但輪渡節點的路徑選擇對研究人員來說仍然是一個難題。因此這激發了DTN中社交網絡［12］應用的想法。

當人類參與網絡活動時，移動節點的行為表現出一定的社會關系與屬性。一些研究［13］表明，節點之間的社會關系與屬性對節點相遇事件有著重要影響，有助于減少路由開銷和提高數據傳輸的成功率。因此，許多研究人員充分利用節點的社會屬性來設計數據轉發機制，并取得了良好的效果。從長遠來看，基于節點間社會關系的數據傳輸機制比其他轉發模式更穩定［13］。

在基于社會屬性的路由算法中，關鍵點在于發現和測量節點之間的社會關系，這取決于對節點相遇歷史數據的分析［14～15］。許多研究使用歷史數據來預測節點相遇概率，從而設計出最佳的消息轉發算法。SimBet［16］借鑒社交網絡的想法，基于節點社會相似性、中介性和聯系強度分析到達目的地的路徑，提高了交付率和時間。在文獻［17～18］中，作者利用機會主義和預期接觸節點等效用函數決定是否將消息轉發給機會接觸的節點或預期接觸的節點，該算法利用節點屬性評估其消息傳遞的有效性。Bubble Rap［19］通過對社交網絡的理解，利用節點的中心性來確保消息成功傳遞。在整個網絡和局部社區為每個節點分別設定兩個索引等級：全局等級（Global Rankness）和局部等級（Local Rank?ness）。發送消息時，節點重復將消息傳遞于網絡中全局等級更高的節點直到遇到目標節點社區節點。在目標節點所在的社區中，該消息進一步被轉發到具有更高局部等級的節點，直至到達目的節點。但該路由方法并未考慮如果目標節點屬于全局中心性較低社區的可能性，因此該路由方法容易造成較長延遲。

為克服移動社交網絡中源節點與目的節點之間連通路徑不穩定的情況，本文提出了一種基于社交關系的自適應路由算法（ARASR）。受移動社交網絡中人類社會行為的啟發，我們針對移動用戶經常傳遞消息于社交關系密切的用戶，提出了目標區域加權中心度和有效傳輸能力，并根據副本的數量選擇不同策略傳輸數據。其中，目標區域加權中心度主要針對目的區域節點，具有較大目標區域加權中心度的節點遇到目的社區中節點的頻率也越高，而有效傳輸能力通過節點活躍度和節點轉發意愿度定義。該算法一方面考慮當攜帶消息節點副本數量僅剩一個時，為將消息盡可能傳遞到目的節點區域，ARASR算法選擇用戶與目標區域加權中心度較高的節點實現消息傳輸，提高消息到達目的區域可能性。另一方面，當消息副本大于一個時，由于有效傳輸能力能夠反映節點在社區間與其他節點的交互情況，因此根據有效傳輸能力自適應地平衡每對節點之間的消息副本的數量，允許具有較高傳輸能力的用戶可獲得更多消息副本促進消息有效傳播，提高數據傳輸率。

2 ARASR算法

本節將主要介紹ARASR算法中提出的節點有效傳輸能力以及目標區域加權中心度的計算，并詳細解釋如何通過節點活躍度以及節點轉發意愿度評估節點的有效傳輸能力，最后說明如何實現消息副本控制機制。算法實現具體流程如圖1所示，其中Vd表示目的節點，與傳統路由算法不同的是，我們首先判斷攜帶消息節點與目的節點是否屬于同一社區，如果屬于同一社區，則將消息直接傳遞給目標節點。其次，根據判定消息副本數量是否大于1選擇不同策略確定中繼節點，加速消息傳播到目標節點區域。因此ARASR算法的主要工作是在第二部分路由策略的選擇，根據所提出的兩種指標（目標區域加權中心度和有效傳輸能力）選擇下一跳節點，并自適應的調整每對節點之間的消息副本數量，該方法不僅有助于盡可能快地傳播消息副本，而且還能確保與目標區域接觸頻繁的節點可以攜帶更多的消息副本。

圖1 ARASR流程圖

2.1 目標區域加權中心度

由于本文的主要工作是在移動社交網絡背景下設計路由方法提高信息投遞率，并不主要探討社區劃分算法，因此本文根據現有算法中針對沒有明確社區結構的網絡環境提出的社區檢測算法［20～21］，將節點輕松劃分到不同社區，并且假設網絡中源節點已知目的節點所在區域。

為權衡多社區內節點的中心度，提出針對目的社區的目標區域加權中心度。眾所周知，網絡中任意一對節點Vi與Vj之間的相遇時間間隔遵循具有參數的指數分布［22］，換句話說，其他節點Vj到達給定節點 Vi的到達率遵循泊松過程。因此，是每對節點Vi和Vj之間的接觸頻率，值越大，Vi和Vj相遇的頻率越高。由此可得，節點Vi遇到其他節點來自子集Z?V的相遇時間間隔也遵循指數分布，即鑒于以上考慮，節點Vi與其他節點來自目標社區D的相遇時間間隔通過加權中心度定義如式（1）所示：

節點Vi與目標節點所在區域D內節點的參數λVi，D越大表示目標區域加權中心度越高。因此，具有較大目標區域加權中心度的節點遇到目的社區中節點的頻率越高。

2.2 節點有效傳輸能力計算

本節根據節點活躍度（Activeness Degree）和節點轉發意愿度評估節點的有效傳輸能力，這是由于節點活躍度可以有效反映當前節點在移動社交網絡中的受歡迎程度，而節點的轉發意愿度能夠體現節點在網絡中的合群性。

圖2 節點活躍時間示意圖

因此，為評估節點活躍度我們分別計算了節點在不同時間段里的相遇次數：總時間段tnow-t_initial以及最近時間段tnow-t1，如圖2所示。由于總時間里的平均相遇數能夠反映整個過程中節點大體的活動狀態，而最近一段時間內的平均相遇次數能夠反映當前節點狀態。所以在計算節點活躍度時，為避免忽略節點長時間里的活動起伏和當前活動行為，本文將兩個時間段相結合定義節點活躍性。節點活躍度ADVi計算公式如式（2）所示。

其 中 ，EVi，Vj表示一對節點的接觸次數，表示最近時間段內與其他節點的平均相遇次數，表示總時間內與其他節點的平均相遇次數，參數?為初始化常量，用于反映節點活動中兩段時間的權重。

移動社交網絡中，活躍度更高的節點接觸其他節點的概率越高，則更有可能將消息副本擴散到網絡中，但節點轉發意愿度同樣不可忽略。本文通過式（3）使用節點的出度定義轉發意愿度，其定義如下：

種子節點的選擇不但要考慮節點在網絡中與其他節點的連接緊密程度，也要考慮節點是否可以有效傳遞消息。為了加速消息傳遞到目的區域D，最終通過結合節點活躍度和節點轉發意愿程度評估節點Vi的有效傳輸能力QVi，由式（4）表示。

2.3 消息副本控制機制

ARASR算法通過每對接觸節點之間定義的度量指標進行不對稱分配消息副本數量。由于網絡中節點內存大小固定，經常存在一部分節點不能快速有效傳遞消息。因此我們考慮針對不同節點分配不同數量的消息副本，即將攜帶消息節點Vi與相遇節點Vj的副本數量利用式（5）進行分配，該方法有效減少了丟包率并且提高消息的投遞概率。

時選擇Vj作為下一跳中繼節點并根據節點有效傳輸能力重新分配副本數量。最后，節點Vi將分配的消息副本發送到相應節點后并更新自身的副本數量如式（6）所示。

當副本數量超過一個的節點仍將不對稱的分發消息副本，直到該節點遇到目的節點或僅剩一個消息副本。該方案有助于縮短消息在整個網絡中傳播的時間。

2.4 ARASR算法實現

本節將主要介紹ARASR路由算法的實現，根據現有的社區檢測算法，我們假設網絡中源節點已知目的節點所在區域，并且消息m的副本的初始數量為固定值h。綜合上述方案，我們最終實現ARASR算法，其具體算法實現策略見算法1。算法1 ARASR路由算法

input：

n：current node

v：encounter node

d：destination node

m：message carried by n

Num_n：number of copies of n

if n∈D then

n forwards m to d，finishes the transmission

else

when n encounters v

for（Num_n＞1）

if（Qv＞Qn）then

n forwards the calculated number of message m that v

could be assigned

else

n still carries the replica of message m

for（Num_n ≤ 1）

if Wv＞Wnthen

n forwards a copy of m to v

3 仿真實驗

3.1 仿真環境

本節采用ONE仿真模擬器（Opportunistic Net?work Environment）［23］仿 真 評 估 ARASR 算法 的性能，并同時加入Prophet、Epidemic和First Contact算法與本文提出算法比較，First Contact路由協議只考慮消息在一跳范圍內時進行轉發消息，Epidemic路由協議通過簡單復制方法將消息分發給每個可能遇到的節點，Prophet算法在相遇節點中權衡轉發到目的節點概率更高的節點投遞消息。

為模擬現實生活中移動社交網絡場景，本文選取Helsinki City作為仿真場景進行實驗，該模型更能體現人類真實社會的交互情況。赫爾辛基城市場景的網絡覆蓋范圍設定為4500×3400m2，其中包括126個移動節點被分為80個運動速度為0.5m/s～1.5m/s的行人，6個7m/s～10m/s的電車以及 40個2.7m/s～13.9m/s的汽車，緩存區大小設置足夠大，因此消息不會由于緩存區過早耗盡而丟失。通訊設備使用傳輸速度和半徑分別為250KBps和20m的藍牙設備作為標準。為考慮到MSNs間歇性連接和頻繁斷開的特性，我們設置每條消息的默認生存周期設定為2個小時，默認時間間隔為30s。在這次模擬實驗中，我們使用四種評估指標來評估算法的性能，即投遞率、網絡負載率、平均時延和平均跳數，并且通過改變緩存空間大小，消息生成時間間隔和消息的生存時間來查看這些度量的變化。仿真結果表明，我們提出的方案顯著提高了路由性能，表1總結了模擬中使用的其他仿真參數。

表1 仿真參數設置

3.2 仿真結果分析

在這次模擬實驗中，我們使用四種評估指標來評估算法的性能，即投遞率、網絡負載率、平均時延和平均跳數，并且通過改變緩存空間大小，消息生成時間間隔和消息的生存時間來查看這些度量的變化。

3.2.1 改變節點緩存空間

我們通過不同路由方案在不同節點緩存空間大小下的性能比較得出，ARASR相比較其他三個算法在消息投遞率、平均時延、平均跳數等方面都取得明顯優勢。這是由于ARASR算法充分考慮節點在移動社交網絡中的社會屬性，根據目標區域加權中心度和有效傳輸能力等指標選擇下一跳中繼節點，減少了消息丟包的概率。圖3為節點緩沖區從4MB增加到18MB的模擬結果。

圖3 不同緩存空間下四種算法的性能表現

從結果可以看出，ARASR算法在各方面明顯優于其他算法，與Prophet和Epidemic路由策略相比，ARASR的投遞率增加約29%和32%，平均時延分別降低約10%和15%。其中，Epidemic路由協議的網絡負載率最高，主要由于該算法沒有限制網絡中消息副本數量，從而造成網絡負擔嚴重，而本文提出的路由方法在最初就限定了副本數量，而且提出了副本控制機制，有效地限制了消息在網絡中的擴散。由此可見本文提出的算法相比其他算法具有更好的表現。

3.2.2 改變消息生存時間

消息生存時間長短與緩存空間大小密切相關。現實生活中每條消息都會受到消息生存時間TTL（Time to live）的限制，而隨著生存周期的延長，消息則會長時間活動并占用大量緩存區空間。本次仿真模擬中設定消息生存周期從2小時增長到5.5小時，觀察TTL的變化對路由性能帶來的影響，其結果如圖4所示。

從圖中可以看出，Epidemic、Prophet算法隨著消息生存時間的增長投遞率逐漸下降，而具有自適應副本分配的ARASR算法提供了最大傳輸率和最低平均跳數，并且ARASR的網絡負載率也遠低于其余三種算法。這是由于隨著消息生存周期的增長導致節點緩存空間不足，而ARASR為避免緩存空間過度消耗，針對緩存空間內消息副本數量不同采取不同的衡量指標投遞消息，First Contact路由算法在網絡中轉發消息的副本數量僅有一個，所以投遞率呈現增長趨勢，但在其他方面表現遠不如ARASR算法。因此結果顯示ARASR與Epidemic、Prophet算法在平均時延方面雖然基本持平，但各方面性能比其他算法更加優秀。

圖4 不同消息生存期下四種算法的性能表現

3.2.3 改變消息生成時間間隔

圖5 不同消息生成時間間隔下四種算法的性能表現

圖5 描述在Helsinki City模型中不同消息生成時間間隔對四種路由算法的性能影響結果，可以觀察到ARASR穩定運行。我們設置消息生存時間間隔以10s為增量增加到90s，從圖5的結果來看，ARASR在消息投遞率、開銷率、平均時延和平均跳數等方面表現都優于對比的其他三種算法，進一步證明我們提出的路由算法可以提高網絡傳輸性能。由于隨著消息生成時間間隔的增長，移動社交網絡中生成大量消息，可以看出除First Contact算法以外其他算法的網絡負載率呈上升趨勢，但First Contact算法消息投遞率始終低于0.4，原因在于該路由方法雖然是基于轉發路由策略中的代表算法之一，但攜帶消息的源節點隨機選擇任意鄰居節點轉發消息，并且副本數量只有一個，從而造成傳輸延遲長且投遞率低。Prophet算法雖然根據與目標節點的接觸概率選擇中繼節點，但并未考慮節點轉發意愿度等社會屬性，因此不可避免產生較高負載率。從圖5可以明顯看出ARASR和Prophet算法的平均跳數和時延一直保持最低，這是因為其余算法沒有對中繼節點的性能進行評估，從而導致盲目選擇下一跳節點增加了傳輸時延和跳數。而ARASR的網絡負載只有Epidemic和Prophet算法的24%、34%。簡而言之，所提出的方法顯著提高了在移動社交網絡上的路由性能，并且利用多種衡量指標篩選下一跳節點進行消息傳遞，綜合各方面表現優于其他算法。

4 結語

在本文中，我們提出了一種針對移動社交網絡的自適應路由協議ARASR，根據節點攜帶消息副本數量的不同，通過分析路由中兩個關鍵屬性解決優化問題，分別是有效傳輸能力和目標區域加權中心度。為優化選擇中繼節點，ARASR在社交網絡場景中引入節點加權中心度，利用任何節點對之間的接觸時間間隔遵循指數分布來評估節點與目標社區間的關系。此外，基于有效傳輸能力提出了消息副本控制機制，避免網絡中生成過多冗余消息。最后我們將本文提出的算法在ONE模擬器上進行評估，并通過Helsinki City模型的廣泛仿真演示了ARASR算法如何顯著優于Prophet、Epidemic和First Contact路由算法。對于路由算法來說，較低的路由開銷可以減少中繼消息的數量和不必要的緩存空間占用，并且提高節點的有效投遞率，而ARASR實現了較低的路由開銷并在消息傳輸率方面表現優異，更加適用于MSNs中的消息傳輸。未來工作將集中在進一步降低開銷率增加ARASR的投遞，并考慮通過額外約束條件來優化下一跳中繼節點的選擇。