基于社區等量交換的移動機會網絡路由算法

劉麗 張岳 黃衛東 錢斌 劉蘭風

摘要：針對移動機會網絡數據轉發效率低下的問題，提出了一種基于社區等量交換的路由算法。首先衡量節點對社區的貢獻和從該社區獲得的收益，采用等量交換的原則來決定節點的合作策略，然后采用資源分配策略對節點為社區分配的數據轉發資源進行優化分配，接著進行轉發數據的選擇，最后對節點的貢獻和收益進行更新。所提算法充分利用社區內外的節點，合理分配轉發資源，從而達到提高數據轉發性能的目的。仿真結果表明，與其他經典算法Direct，LABEL和ProPHET相比，該算法能夠顯著優化數據轉發資源，提高數據轉發效率，獲得了更高的數據傳遞率、更低的轉發延遲和負載。

關鍵詞： 移動機會網絡；社區；路由轉發

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）10-0032-03

開放科學（資源服務）標識碼（OSID）：

1 引言

移動機會網絡（Mobile Opportunistic Network）利用移動設備在移動過程中偶然的相遇機會，采用“存儲-攜帶-轉發”的模式完成不依賴于基礎設施的數據傳輸[1]。普遍存在的移動設備使得移動機會網絡成為未來社會生活中移動應用的重要通訊模式。

近年來，社交因素對移動機會網絡數據傳輸的影響逐漸被人們所關注，涌現了很多基于社交因素的路由算法。社區是指具有直接或間接社交聯系的人組成的關系緊密的群體。社區中的成員之間，與社區外的成員相比，具有更頻繁的接觸和相遇機會[2]。節點間的社區特性在移動機會網絡路由協議設計中具有積極的作用，能夠在一定程度上提高數據傳輸效率。然而，在眾多的移動節點中，社區外的節點的數量遠遠多于同社區的節點數量。而社區外的弱聯系節點這一重大資源卻常常被忽略。

本文提出了一種基于社區等量交換的數據路由算法（Community based Equal Exchanged Routing Algorithm， 簡稱CEERA），合理利用社區和弱聯系節點這兩種資源，考察節點與社區之間的貢獻和收益平衡，采取等量交換的原則，優化轉發資源，從而達到提高數據轉發性能的目的。仿真結果表明，本文提出的算法能夠有效地提高數據轉發效率，降低網絡負載。

2 算法的提出

2.1 系統模型

假設系統中有N個節點，按照一定的社交聯系組成M個社區[C1，C2，...Ci，...CM]，其中i=1..M。同一社區中的節點具有較高的社交強度，從而具有更加頻繁的相遇概率，常被用來指導路由轉發。CEERA算法中，節點綜合考慮與所有社區的社交強度和關聯，從節點與社區之間的社交強度、未來相遇概率、節點對社區的貢獻，以及節點從該社區的收益四個方面衡量，以實現優化分配數據轉發資源，提高數據轉發效率的目的。

2.2 衡量要素

節點與社區之間社交強度[ST（Ci）]。節點與社區之間的社交強度用來衡量節點與各個社區的接觸程度。某節點與社區[Ci]的社交強度[ST（Ci）]采用單位時間T內遇到的該社區的節點數量來衡量，即公式（1）。

2.3 CEERA的工作流程

當兩個節點如A和B進入彼此的通信范圍，首先交換彼此的社區信息，更新相應的社區社交強度信息。然后，根據節點的貢獻收益情況，采用等量交換的原則決定是否為對方節點轉發數據（合作策略）。接著，根據數據轉發策略決定轉發列表，進行數據傳輸。如果決定不進行數據轉發，轉發列表為空。最后，根據本次的轉發行為，更新各自的貢獻收益情況（更新策略）。

3 算法的實現

3.1 合作策略的實現

移動機會網絡數據傳輸的基礎是節點之間的合作轉發，即節點愿意為相遇節點轉發數據。CEERA算法的合作策略采取基于社區等量交換的原則，依據節點對社區的貢獻和節點從社區獲得的收益兩個指標來決定節點采取合作轉發行為還是拒絕轉發的行為。

節點一方面為各個社區轉發數據做出貢獻，另一方面也接受各個社區節點的轉發幫助獲得收益。對于節點來說，精簡轉發操作減少頻繁替換的前提是自身得到最大的收益。假設單位時間T內，節點為各個社區做的貢獻為[CON（Ci）]，則其在單位時間內總的貢獻為[i=1MCON（Ci）]。假設節點從各個社區得到的收益為[BEN（Ci）]，則其在單位時間內總的貢獻為[i=1MBEN（Ci）]。在節點有限的傳輸帶寬資源下，節點要得到最大收益需要滿足公式（3），即節點以最少的轉發貢獻獲得最大的轉發收益。這個問題可以轉換為0-1背包問題，從而得到公式（4）。

由于每個節點都想獲得最優的收益，因此，當[BEN（Ci）CON（Ci）]接近1時，可以得到接近于最優的收益，即節點對社區[Ci]的轉發貢獻與其從該社區得到的收益基本持平。由此可知，節點對社區采取等量交換的原則，可以最大限度地利用其轉發資源，有效地減少替換操作，從而提高數據轉發效率。

由于節點的貢獻和收益不是同時發生的，兩者之間往往存在一定的時間差，因此設立一個閾值[minSize，maxSize]來進行調節。從節點A的角度來說明具體的合作策略如下：

3.2 更新策略的實現

當數據轉發成功后，要及時更新對應節點的貢獻值和收益值。仍以節點A為例來說明更新策略。假設節點A為節點B轉發了若干數據。則對于每個轉發的數據，根據數據的源節點、目的節點與轉發節點三者之間的關系，更新策略可以分為下面四種情況進行處理：

（1） A、B都是中間轉發節點。這時節點A幫助節點B轉發了若干數據，節點B得到了節點A的轉發服務，則節點B從節點A所在社區[Ci]所得的收益值將會增加。

（2） 節點A是中間轉發節點，而節點B是源節點（產生數據的節點）。這種情況的處理與（1）類似，節點A對B所在社區[Cj]的貢獻將會增加，節點B從A所在社區[Ci]所得到的收益將會增加。

（3） 節點A是目的節點（數據的接收節點），而節點B是中間轉發節點。這種情況下，節點A接收了所需要的數據，從節點B所在社區[Cj]中獲益。因此，節點A從社區[Cj]得到的收益將會增加。而節點B因為幫助了節點A，其對社區[Ci]的貢獻也將會相應增加。

（4） 節點A是目的節點，節點B是源節點。這種情況下，節點A和節點B互相為對方社區做了貢獻，其貢獻和收益相抵。節點A、B的貢獻收益將保持不變，不做更新操作。

4 算法性能評價

4.1 仿真環境及設置

本文中使用仿真工具ONE Simulator[10]，實驗數據采用INFOCOM2006實際數據集進行仿真實驗。實驗中，將CEERA與經典路由算法直接轉發路由算法（Direct）、基于社區的轉發路由算法LABEL以及ProPHET路由算法進行性能對比和分析。

4.2 仿真結果及分析

通過以上仿真比較可知，CEERA具有最高的數據交付率，較低的網絡負載，最少的平均延遲，以及最多的平均跳數，獲得了最優的數據轉發效率。從而證明CEERA使得移動機會網絡中的數據轉發性能得到明顯提升。

5 結語

本文中提出了基于社區等量交換的數據轉發路由算法CEERA，以節點與社區之間的貢獻和收益的等量交換為原則，優化分配節點的轉發資源，合理分配節點的存儲空間，以實現優化數據轉發性能的目的。基于實際數據集INFOCOM2006的仿真實驗表明，與傳統經典算法相比，CEERA可以有效地提高移動機會網絡中的數據轉發效率。

參考文獻：

[1] 馬東華， 袁培燕， 趙東. 移動機會網絡路由問題研究進展[J]. 軟件學報， 2015， 26（3）：600-616.

[2] 姚玉坤， 楊及開， 劉文輝. 機會網絡中基于社區的高效消息傳輸算法[J]. 計算機應用， 2015，35（9）：2447-2452.

[3] Lindgren A， Doria A， Schelén O. Probabilistic routing in intermittently connected networks[J].Service Assurance with Partial and Intermittent Resources， ser. Lecture Notes in Computer Science，2004，3126：239-254.

[4] Ker?nen A， K?rkk?inen T， Ott J. Simulating Mobility and DTNs with the ONE[J]. Journal of Communications，2010，5（2）：92-105.

【通聯編輯：王力】