摘  要： 針對機會網絡主流路由協議沒有考慮到節點的社區特性，提出了一種基于社區的冗余效用混合轉發機制。該算法從合理降低洪泛度和準確預測效用值方面出發，通過消息篩選、消息優先級和活躍節點機制對消息進行有效處理和轉發。與經典的Epidemic和Prophet算法相比，該算法具有消息傳達率較高、傳輸延時小和網絡開銷低的特點。

　　關鍵詞： 機會網絡；社區；冗余效用

0 引言

　　機會網絡是一種不需要源節點和目標節點之間存在完整鏈路，利用節點移動帶來的相遇機會實現通信的自組織網絡，其主要應用集中在野生動物追蹤、車載網絡、偏遠地區網絡傳輸等場合[1]。隨著大量智能手機等手持設備的出現，以人為載體的移動節點的數據交換頻繁，逐漸出現以人為主體的機會網絡。由于人們之間社會關系相對穩定且存在一定的依賴性，網絡中會出現節點的聚集現象，從而形成不同的社區。社區內的節點移動緩慢，相遇概率高，不同社區內的節點相遇概率低，往往需要通過一些活躍節點來增加社區之間的聯系，與以節點移動快速、網絡拓撲變化頻繁的普通機會網絡相比有明顯的區別[2]。

1 相關工作

　　2006年，MUSOLESI M等人提出了基于人類社會關系的移動自組織網絡移動模型，引起了人們的廣泛關注[3]。2007年，Pan Hui等人提出為每個消息包貼上社區標簽，轉發時只需進行簡單的標簽號比較就能判斷是否允許發送，進而提高了消息的投遞成功率[4]。2009年，牛建偉根據節點之間的通信頻繁程度，自動將節點劃分成不同的社區，自適應地控制消息的拷貝數量并依靠活躍節點將消息傳輸到目標社區[2]。2013年，劉亞翃等人根據節點間的社會關系強度，動態自適應地將節點劃分為不同的社區，通過限制消息副本數來減少網絡中消息的冗余，并利用活躍性高的節點帶動消息的轉發[5]。2014年，周軍海等人提出一種基于社區的低功耗消息路由算法，能自適應地控制消息拷貝數量并能自動調整節點的活躍度，依靠活躍度較高的節點來完成消息傳輸[6]。針對社區機會網絡的特點，本文提出一種基于社區的冗余效用混合轉發機制，該算法根據現實社會節點的移動特性在傳染路由的基礎上對消息路由做改進，對社區內消息包進行優先級分類和消息篩選，通過活躍節點進行社區間消息傳遞，具有傳達率高、網絡資源消耗低、傳輸延時小的特點。

2 基于社區的冗余效用混合路由算法

　　機會網絡路由技術從不同的角度可分為不同的種類。根據路由策略來分，可以分為基于復制的路由和基于效用的路由[7]。基于復制的路由通過洪泛的方式進行轉發，但資源占用率高。基于效用的路由能有效減少過多的消息復制，但傳達率較低，延時較大。由于社區內節點相對聚集，不同社區之間節點聯系較少，普通機會網絡路由算法在社區網絡內效率不高。綜合以上兩種算法優點的冗余效用混合路由在降低資源消耗的前提下有利于消息轉發率的提高，在社區機會網絡的消息轉發機制中使用尤為合適。算法主要包括消息篩選、優先級和活躍節點3種機制。

　　2.1 消息篩選機制

　　當社區中節點攜帶有以本社區內其他節點為目的節點的消息包時，一方面，由于有社區歸屬的節點很大概率是在本社區內部活動，且社區內節點間相遇頻繁，消息包可以通過本社區的中繼節點經過多跳很快傳達到目的節點；另一方面，外部社區的節點到本社區活動的概率很低，假如把上述消息轉發給外部社區節點，消息很有可能只會在外部社區擴散，很難回傳到本社區，不僅不能提高傳達率，反而盲目地增加了網絡中消息的副本數，增加網絡資源的消耗。因此，本社區內的消息沒有必要擴散至其他社區。算法中加入消息篩選機制，當該機制檢測到相遇節點歸屬于不同社區且自身節點存儲有以同一社區內節點為目的節點的消息包時，把該類消息包從轉發隊列中過濾掉。

　　2.2 消息優先級機制

　　由于節點移動的不確定性，節點間從建立連接到斷開，中間的持續時間可能只是一瞬間。考慮到網絡連通時間的不確定性，為了讓消息的轉發更具有效用性，可以提前判斷消息的效用值，按效用值由高到低順序轉發。算法加入了消息優先級機制，優先級高的一類消息包優先轉發，同類的按順序轉發。優先級分類如下：

　　（1）第一優先級。轉發節點的消息緩沖區中可能存儲有以對方節點為目的節點的消息包，這類消息包只需要再經過一跳就能傳達到目的節點。

　　（2）第二優先級。在消息篩選機制中已分析到社區內部的消息包在本社區中繼節點的協助下可以經過多跳以較快的速度傳達，在本社區消息不外傳的前提下，該類消息的副本僅僅在本社區內擴散，實現以較低的消息副本數獲得較小的傳達延時，因而該類效用值較高的消息以第二優先級被轉發。

　　（3）第三優先級。轉發節點的消息緩沖區可能存儲有對方節點社區內的消息包，由于對方節點與消息目的節點歸屬社區相同，那么兩節點很大概率在本社區內活動，通過直接相遇或者本社區其他中繼節點轉發，消息可以較快傳達。

　　2.3 活躍節點機制

　　在現實社會，有一些人經常穿梭于各大社區之間，比如快遞員、送餐員和上下班的職員等。社區間的消息可以利用這些活躍的人群進行傳送。這種機制讓網絡中的活躍節點承擔社區間的副本擴散任務。其優點有兩方面：一方面，控制了網絡中消息的洪泛程度，避免了副本盲目、過度地增加；另一方面，減少不必要的傳輸，使網絡資源的利用更加充分有效。

　　2.4 轉發策略

　　開始時，消息發送方遇到對方節點，雙方建立連接。逐個遍歷緩沖區的消息，如果滿足來自不同社區且為社區內的消息則被篩選機制過濾掉不加入發送隊列，否則依次經過優先級一、二、三以及活躍節點機制進行判斷，符合條件則加入對應隊列，都不符合則放棄轉發。直到完成遍歷，把消息依次按隊列一、二、三和普通發送隊列給接收方，最后結束本次任務。具體流程如圖1所示。

3 仿真實驗和結果分析

　　3.1 模擬環境設置

　　本文采用ONE模擬器為仿真平臺實現算法，采用Epidemic和Prophet算法在本文設計的江門市蓬江區運動場景中進行對比測試。

　　3.1.1 地圖場景

　　現實生活中，人們的移動性強，社會關系復雜，移動特性各異。為真實還原機會網絡的社區特性，以江門市蓬江區16個主要社區作為仿真場景，實現了對真實世界移動模型的模擬，采用OpenJUMP軟件繪制地圖，如圖2所示。

　　3.1.2 線路規劃

　　人類社會中不同移動節點具有不同的偏好位置和有效活動范圍，本文設計了機動車線路、公交線路和社區線路，控制各類節點的運動。機動車線路限制了汽車節點的有效活動范圍，公交線路上不定距離設有站點。

　　3.1.3 節點規劃

　　網絡中有人、汽車等可以攜帶無線通信設備的移動節點，根據節點的不同移動特性設有5類節點，具體如下：

　　（1）普通行人節點：只參與消息包的轉發和接收，但不加入任何社區。

　　（2）有社區歸屬行人節點：大部分在本社區內活動。

　　（3）普通汽車節點：在機動車線路上活動，速度快，活動性強。

　　（4）公交汽車節點：在公交線路上移動，緩存大，線路固定，盡可能不調頭。

　　（5）動態社區歸屬節點：在仿真范圍內隨機活動，當進入某一社區就加入該社區，離開則退出該社區，用以模擬社區內部節點構成的動態變化。

　　活躍節點來自上述部分節點，其中包括有社區歸屬且經常活動于其他社區的節點、汽車節點、公交節點和動態社區歸屬行人節點。

　　3.1.4 仿真參數

　　根據以上的規劃，本文采用的仿真主要參數如表1所示。

　　3.2 緩存對網絡性能的影響

　　與路由算法Epidemic和Prophet相比，基于社區的冗余效用混合算法（用Community表示）在緩存大小不同的情況下，對消息傳達率、平均延時和路由開銷比率3種性能指標下影響分析如下。

　　3.2.1 消息傳遞成功率

　　當緩存較小時，網絡中由于消息副本量大而不能滿足消息的緩存要求，舊的消息包會較快被新接收的擠掉，造成大量包被丟棄，因而3種路由算法傳達率都不高。隨著緩存容量的增大，傳達率都有不同程度的上升。Epidemic以高傳輸延時為代價，因而傳達率比Prophet高。本文算法對消息副本洪泛程度控制有效，轉發效率較高，因此傳達率較高。具體如圖3所示。

　　3.2.2 消息傳遞平均延時

　　對于消息傳遞平均延時，Epidemic明顯高于其他兩種算法，由于向網絡中洪泛消息副本，有限的網絡資源會使消息包被大量丟棄，很難找到較短傳輸路徑把消息傳到目的節點，傳輸延時大。Prophet和本文算法都提前對消息轉發效用值做預測，更容易找到較短路徑，延時較低。具體如圖4所示。

　　3.2.3 路由開銷比率

　　從總體上看，隨著緩存的增大，網絡中節點的丟包量減小，更多的消息被成功傳輸，開銷越來越低。本文算法明顯低于Epidemic和Prophet，這是因為：一方面，洪泛程度低，網絡中消息副本較少；另一方面，消息轉發效用高，傳達率高，因此開銷低。Prophet也對消息洪泛做了控制，但由于傳達率低，在開銷上與Epidemic相比并沒有明顯優勢。具體如圖5所示。

4 結論

　　本文提出了一種基于社區的冗余效用混合傳輸機制，目標是解決普通機會網絡路由算法在社區網絡中性能不高的問題。本文首先分析了目前社區機會網絡的研究現狀，針對基于復制的路由和基于效用的路由存在的問題，提出將冗余效用混合算法應用于基于社區的機會網絡中。以江門市蓬江區為主要場景進行了模擬，并與Epidemic和Prophet算法進行了比較。實驗結果表明，冗余效用混合轉發機制在消息投遞成功率、傳遞平均延時和路由開銷比上均有明顯改善。

參考文獻

　　[1] 熊永平，孫利民，牛建偉.機會網絡[J].軟件學報，2009，20（1）：124-137.

　　[2] 牛建偉，周興，劉燕.一種基于社區機會網絡的消息傳輸算法[J].計算機研究與發展，2009，46（12）：2068-2075.

　　[3] MUSOLESI M， MASCOLO C. A community based mobility model for ad hoc network research[C]. Proceedings of the 2nd International Workshop on Multi-hop ad Hoc Networks： from Theory to Reality， New York： ACM， 2006： 31-38.

　　[4] Pan Hui， CROWCROFT J． How small labels create big improvements[C]. Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops，New York，2007：65-70.

　　[5] 劉亞翃，高媛，喬晉龍.機會社會網絡中基于社區的消息傳輸算法[J].計算機應用，2013，33（5）：1212-1216.

　　[6] 周軍海，林亞平，周四望.一種低功耗的社區機會網絡消息路由算法[J].計算機科學，2014，41（1）：178-182.

　　[7] 徐佳，王汝傳，徐杰.基于效用的容遲網絡路由技術研究[J].計算機應用研究，2011，28（4）：1211-1215.