摘 要： 針對機會網絡主流路由協(xié)議沒有考慮到節(jié)點的社區(qū)特性,，提出了一種基于社區(qū)的冗余效用混合轉發(fā)機制。該算法從合理降低洪泛度和準確預測效用值方面出發(fā)，通過消息篩選,、消息優(yōu)先級和活躍節(jié)點機制對消息進行有效處理和轉發(fā),。與經典的Epidemic和Prophet算法相比，該算法具有消息傳達率較高,、傳輸延時小和網絡開銷低的特點,。
關鍵詞： 機會網絡；社區(qū),；冗余效用
0 引言
機會網絡是一種不需要源節(jié)點和目標節(jié)點之間存在完整鏈路,，利用節(jié)點移動帶來的相遇機會實現(xiàn)通信的自組織網絡，其主要應用集中在野生動物追蹤,、車載網絡,、偏遠地區(qū)網絡傳輸?shù)葓龊蟍1]。隨著大量智能手機等手持設備的出現(xiàn),，以人為載體的移動節(jié)點的數(shù)據(jù)交換頻繁,，逐漸出現(xiàn)以人為主體的機會網絡。由于人們之間社會關系相對穩(wěn)定且存在一定的依賴性,，網絡中會出現(xiàn)節(jié)點的聚集現(xiàn)象,，從而形成不同的社區(qū)。社區(qū)內的節(jié)點移動緩慢,，相遇概率高,，不同社區(qū)內的節(jié)點相遇概率低，往往需要通過一些活躍節(jié)點來增加社區(qū)之間的聯(lián)系,，與以節(jié)點移動快速,、網絡拓撲變化頻繁的普通機會網絡相比有明顯的區(qū)別[2]。
1 相關工作
2006年,，MUSOLESI M等人提出了基于人類社會關系的移動自組織網絡移動模型,，引起了人們的廣泛關注[3]。2007年,，Pan Hui等人提出為每個消息包貼上社區(qū)標簽,，轉發(fā)時只需進行簡單的標簽號比較就能判斷是否允許發(fā)送，進而提高了消息的投遞成功率[4],。2009年,，牛建偉根據(jù)節(jié)點之間的通信頻繁程度，自動將節(jié)點劃分成不同的社區(qū),，自適應地控制消息的拷貝數(shù)量并依靠活躍節(jié)點將消息傳輸?shù)侥繕松鐓^(qū)[2],。2013年，劉亞翃等人根據(jù)節(jié)點間的社會關系強度,，動態(tài)自適應地將節(jié)點劃分為不同的社區(qū),，通過限制消息副本數(shù)來減少網絡中消息的冗余,，并利用活躍性高的節(jié)點帶動消息的轉發(fā)[5]。2014年,，周軍海等人提出一種基于社區(qū)的低功耗消息路由算法,，能自適應地控制消息拷貝數(shù)量并能自動調整節(jié)點的活躍度，依靠活躍度較高的節(jié)點來完成消息傳輸[6],。針對社區(qū)機會網絡的特點,，本文提出一種基于社區(qū)的冗余效用混合轉發(fā)機制，該算法根據(jù)現(xiàn)實社會節(jié)點的移動特性在傳染路由的基礎上對消息路由做改進,，對社區(qū)內消息包進行優(yōu)先級分類和消息篩選,，通過活躍節(jié)點進行社區(qū)間消息傳遞，具有傳達率高,、網絡資源消耗低,、傳輸延時小的特點。
2 基于社區(qū)的冗余效用混合路由算法
機會網絡路由技術從不同的角度可分為不同的種類,。根據(jù)路由策略來分,，可以分為基于復制的路由和基于效用的路由[7]?；趶椭频穆酚赏ㄟ^洪泛的方式進行轉發(fā),，但資源占用率高?；谛в玫穆酚赡苡行p少過多的消息復制,，但傳達率較低，延時較大,。由于社區(qū)內節(jié)點相對聚集,，不同社區(qū)之間節(jié)點聯(lián)系較少，普通機會網絡路由算法在社區(qū)網絡內效率不高,。綜合以上兩種算法優(yōu)點的冗余效用混合路由在降低資源消耗的前提下有利于消息轉發(fā)率的提高,，在社區(qū)機會網絡的消息轉發(fā)機制中使用尤為合適。算法主要包括消息篩選,、優(yōu)先級和活躍節(jié)點3種機制,。
2.1 消息篩選機制
當社區(qū)中節(jié)點攜帶有以本社區(qū)內其他節(jié)點為目的節(jié)點的消息包時，一方面,，由于有社區(qū)歸屬的節(jié)點很大概率是在本社區(qū)內部活動,，且社區(qū)內節(jié)點間相遇頻繁，消息包可以通過本社區(qū)的中繼節(jié)點經過多跳很快傳達到目的節(jié)點,；另一方面,，外部社區(qū)的節(jié)點到本社區(qū)活動的概率很低，假如把上述消息轉發(fā)給外部社區(qū)節(jié)點,，消息很有可能只會在外部社區(qū)擴散,，很難回傳到本社區(qū),，不僅不能提高傳達率,，反而盲目地增加了網絡中消息的副本數(shù),，增加網絡資源的消耗。因此,，本社區(qū)內的消息沒有必要擴散至其他社區(qū),。算法中加入消息篩選機制，當該機制檢測到相遇節(jié)點歸屬于不同社區(qū)且自身節(jié)點存儲有以同一社區(qū)內節(jié)點為目的節(jié)點的消息包時,，把該類消息包從轉發(fā)隊列中過濾掉,。
2.2 消息優(yōu)先級機制
由于節(jié)點移動的不確定性，節(jié)點間從建立連接到斷開,，中間的持續(xù)時間可能只是一瞬間,。考慮到網絡連通時間的不確定性,，為了讓消息的轉發(fā)更具有效用性,，可以提前判斷消息的效用值，按效用值由高到低順序轉發(fā),。算法加入了消息優(yōu)先級機制,，優(yōu)先級高的一類消息包優(yōu)先轉發(fā)，同類的按順序轉發(fā),。優(yōu)先級分類如下：
?。?）第一優(yōu)先級。轉發(fā)節(jié)點的消息緩沖區(qū)中可能存儲有以對方節(jié)點為目的節(jié)點的消息包,，這類消息包只需要再經過一跳就能傳達到目的節(jié)點,。
（2）第二優(yōu)先級,。在消息篩選機制中已分析到社區(qū)內部的消息包在本社區(qū)中繼節(jié)點的協(xié)助下可以經過多跳以較快的速度傳達,，在本社區(qū)消息不外傳的前提下，該類消息的副本僅僅在本社區(qū)內擴散,，實現(xiàn)以較低的消息副本數(shù)獲得較小的傳達延時,，因而該類效用值較高的消息以第二優(yōu)先級被轉發(fā)。
?。?）第三優(yōu)先級,。轉發(fā)節(jié)點的消息緩沖區(qū)可能存儲有對方節(jié)點社區(qū)內的消息包，由于對方節(jié)點與消息目的節(jié)點歸屬社區(qū)相同,，那么兩節(jié)點很大概率在本社區(qū)內活動,，通過直接相遇或者本社區(qū)其他中繼節(jié)點轉發(fā)，消息可以較快傳達,。
2.3 活躍節(jié)點機制
在現(xiàn)實社會,，有一些人經常穿梭于各大社區(qū)之間,，比如快遞員、送餐員和上下班的職員等,。社區(qū)間的消息可以利用這些活躍的人群進行傳送,。這種機制讓網絡中的活躍節(jié)點承擔社區(qū)間的副本擴散任務。其優(yōu)點有兩方面：一方面,，控制了網絡中消息的洪泛程度,，避免了副本盲目、過度地增加,；另一方面,，減少不必要的傳輸，使網絡資源的利用更加充分有效,。
2.4 轉發(fā)策略
開始時,，消息發(fā)送方遇到對方節(jié)點，雙方建立連接,。逐個遍歷緩沖區(qū)的消息,，如果滿足來自不同社區(qū)且為社區(qū)內的消息則被篩選機制過濾掉不加入發(fā)送隊列，否則依次經過優(yōu)先級一,、二,、三以及活躍節(jié)點機制進行判斷，符合條件則加入對應隊列,，都不符合則放棄轉發(fā),。直到完成遍歷，把消息依次按隊列一,、二,、三和普通發(fā)送隊列給接收方，最后結束本次任務,。具體流程如圖1所示,。
3 仿真實驗和結果分析
3.1 模擬環(huán)境設置
本文采用ONE模擬器為仿真平臺實現(xiàn)算法，采用Epidemic和Prophet算法在本文設計的江門市蓬江區(qū)運動場景中進行對比測試,。
3.1.1 地圖場景
現(xiàn)實生活中,，人們的移動性強，社會關系復雜,，移動特性各異,。為真實還原機會網絡的社區(qū)特性，以江門市蓬江區(qū)16個主要社區(qū)作為仿真場景,，實現(xiàn)了對真實世界移動模型的模擬,，采用OpenJUMP軟件繪制地圖，如圖2所示。
3.1.2 線路規(guī)劃
人類社會中不同移動節(jié)點具有不同的偏好位置和有效活動范圍,，本文設計了機動車線路,、公交線路和社區(qū)線路，控制各類節(jié)點的運動,。機動車線路限制了汽車節(jié)點的有效活動范圍,，公交線路上不定距離設有站點。
3.1.3 節(jié)點規(guī)劃
網絡中有人,、汽車等可以攜帶無線通信設備的移動節(jié)點,，根據(jù)節(jié)點的不同移動特性設有5類節(jié)點，具體如下：
?。?）普通行人節(jié)點：只參與消息包的轉發(fā)和接收，但不加入任何社區(qū),。
?。?）有社區(qū)歸屬行人節(jié)點：大部分在本社區(qū)內活動。
?。?）普通汽車節(jié)點：在機動車線路上活動,，速度快，活動性強,。
?。?）公交汽車節(jié)點：在公交線路上移動，緩存大,，線路固定,，盡可能不調頭。
?。?）動態(tài)社區(qū)歸屬節(jié)點：在仿真范圍內隨機活動,，當進入某一社區(qū)就加入該社區(qū)，離開則退出該社區(qū),，用以模擬社區(qū)內部節(jié)點構成的動態(tài)變化,。
活躍節(jié)點來自上述部分節(jié)點，其中包括有社區(qū)歸屬且經?；顒佑谄渌鐓^(qū)的節(jié)點,、汽車節(jié)點、公交節(jié)點和動態(tài)社區(qū)歸屬行人節(jié)點,。
3.1.4 仿真參數(shù)
根據(jù)以上的規(guī)劃,，本文采用的仿真主要參數(shù)如表1所示。
3.2 緩存對網絡性能的影響
與路由算法Epidemic和Prophet相比,，基于社區(qū)的冗余效用混合算法（用Community表示）在緩存大小不同的情況下,，對消息傳達率、平均延時和路由開銷比率3種性能指標下影響分析如下,。
3.2.1 消息傳遞成功率
當緩存較小時,，網絡中由于消息副本量大而不能滿足消息的緩存要求,，舊的消息包會較快被新接收的擠掉，造成大量包被丟棄,，因而3種路由算法傳達率都不高,。隨著緩存容量的增大，傳達率都有不同程度的上升,。Epidemic以高傳輸延時為代價,，因而傳達率比Prophet高。本文算法對消息副本洪泛程度控制有效,，轉發(fā)效率較高,，因此傳達率較高。具體如圖3所示,。
3.2.2 消息傳遞平均延時
對于消息傳遞平均延時,，Epidemic明顯高于其他兩種算法，由于向網絡中洪泛消息副本,，有限的網絡資源會使消息包被大量丟棄,，很難找到較短傳輸路徑把消息傳到目的節(jié)點，傳輸延時大,。Prophet和本文算法都提前對消息轉發(fā)效用值做預測,，更容易找到較短路徑，延時較低,。具體如圖4所示,。
3.2.3 路由開銷比率
從總體上看，隨著緩存的增大,，網絡中節(jié)點的丟包量減小,，更多的消息被成功傳輸，開銷越來越低,。本文算法明顯低于Epidemic和Prophet,，這是因為：一方面，洪泛程度低,，網絡中消息副本較少,；另一方面，消息轉發(fā)效用高,，傳達率高,，因此開銷低。Prophet也對消息洪泛做了控制,，但由于傳達率低,，在開銷上與Epidemic相比并沒有明顯優(yōu)勢。具體如圖5所示。
4 結論
本文提出了一種基于社區(qū)的冗余效用混合傳輸機制,，目標是解決普通機會網絡路由算法在社區(qū)網絡中性能不高的問題,。本文首先分析了目前社區(qū)機會網絡的研究現(xiàn)狀，針對基于復制的路由和基于效用的路由存在的問題,，提出將冗余效用混合算法應用于基于社區(qū)的機會網絡中,。以江門市蓬江區(qū)為主要場景進行了模擬，并與Epidemic和Prophet算法進行了比較,。實驗結果表明,，冗余效用混合轉發(fā)機制在消息投遞成功率、傳遞平均延時和路由開銷比上均有明顯改善,。
參考文獻
[1] 熊永平,，孫利民，牛建偉.機會網絡[J].軟件學報,，2009,，20（1）：124-137.
[2] 牛建偉，周興,，劉燕.一種基于社區(qū)機會網絡的消息傳輸算法[J].計算機研究與發(fā)展，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] 劉亞翃,，高媛，喬晉龍.機會社會網絡中基于社區(qū)的消息傳輸算法[J].計算機應用,，2013,，33（5）：1212-1216.
[6] 周軍海，林亞平,，周四望.一種低功耗的社區(qū)機會網絡消息路由算法[J].計算機科學,，2014，41（1）：178-182.
[7] 徐佳,，王汝傳,，徐杰.基于效用的容遲網絡路由技術研究[J].計算機應用研究，2011,，28（4）：1211-1215.