機會網絡應用在偏遠地區的仿真研究

龔丁海，黃曉航，譚松鶴

(河池學院 1.數學與統計學院;2.計算機與信息工程學院，廣西 宜州 546300)

0 引言

機會網絡［1］是一種不需要源節點和目的節點之間存在完整路徑，利用節點移動帶來的相遇機會實現網絡通信的、時延和分裂可容忍的自組織網絡［1－2］。機會網絡以“存儲－攜帶－轉發”的機制進行消息的傳送，主要應用于缺少通信基礎設施、網絡環境惡劣等場合，如袖珍型交換網絡，偏遠地區互聯網無線接入等［2］。DakNet項目［3］是在印度偏遠地區部署機會網絡，以便為鄉村地區提供通信連接;類似的還有Saami-NetworkConnectivity項目［4］，Tier項目［5］和 Wizzy系統［6］。基于機會網絡的特性和機會網絡在偏遠地區應用的潛力，本文通過設定一個類似于偏遠地區特性的網絡場景，對機會網絡幾種典型的路由協議在該場景中的性能、特點進行分析比較，以評價各路由算法在該場景的應用。

1 機會網絡路由協議

1.1 直接傳輸協議(DirectDelivery)

DirectDelivery［7］是典型的單副本路由協議，也是最簡單的路由機制。該路由協議由源節點攜帶消息移動，直到遇到目的節點，將消息轉發給目的節點。

1.2 傳染轉發協議(Epidemic)

Epidemic［8］本質上是一種洪泛，其基本思想是網絡中兩個相遇的節點均會交換相互沒有的消息。節點間足夠的交換，理論上讓每個非孤立的節點將收到所有的數據包，能最大化數據包傳輸的成功率，減少傳輸延遲［8］。但在網絡資源受限的實際網絡中，會由于洪泛而導致網絡中消息副本數量增多而消耗網絡資源。

1.3 FirstContact協議

FirstContact［9］是一種單副本路由協議，源節點將消息轉發給第一個遇到的節點，攜帶該消息的節點繼續將消息轉發給它第一個遇到的節點，如此反復，直到消息轉發給目的節點。

1.4 MaxProp算法

Maxprop［10］協議在Epidemic的基礎上進行了改進，改進之處在于:源節點為消息設定有效期TTL，在轉發過程中，當消息的有效期到了，或者節點收到一個ack消息，或者節點的數據緩存區被裝滿時，節點將丟棄該消息。Maxprop能夠避免每個消息都被泛洪到全網，減少了開銷;但消息有效期的合理設置有一定難度［2］。

1.5 Prophet協議

Prophet［11］是基于概率的路由協議，每個節點估計到達其他節點的相遇概率，概率值隨節點間相遇而升高，不相遇時則隨時間遞減，節點利用概率傳遞性來更新與其他節點之間的可達概率，從而獲取與目標節點的相遇概率。

1.6 SprayAndWait協議

SprayAndWait［12］協議通過設定每個消息在網絡中的副本數來控制洪泛的程度。該協議分為兩個階段，在Spray階段，源節點將在網絡中產生L份副本擴散到L(L＞1)個中繼節點;在Wait階段，若在Spray階段沒有發現目的節點，那么包含消息的節點通過直接傳輸的方式把信息傳送到目的節點。SprayAndWait協議包含有Binary模式和非Binary模式。在Binary模式下，源節點將一半數據包發送給遇到的中繼節點，自己留下一半數據包;隨后源節點和中繼節點重復進行上述過程，直到所有節點中只有一個數據包時，節點轉入Wait階段，采用直接傳輸給目的節點。

2 仿真場景設置

本文選用ONE仿真器(The Opportunistic Network Environment Simulator)［13］進行仿真。在仿真過程中使用ONE仿真器自帶的芬蘭首都赫爾辛基地圖場景［14］。仿真時間為12 h，區域范圍為4 500×3 400，數據包大小為(10 kB，1 MB)，數據包產生頻率為(25，35)s。仿真模擬攜帶藍牙設備的行人、摩托車、小汽車和公共汽車等四種類型共310個節點的移動場景，其中行人270，摩托車20，小汽車8，公共汽車12。各移動節點的特征如表1所示。

表1 各移動節點特征

各移動節點的移動模型中，行人1的移動選擇RWP(Random Waypoint)模型隨機生成目標位置坐標;摩托車、小汽車、公共汽車使用基于地圖的MRM(Map Route Movement)模型;行人2使用基于地圖的最短路徑移動模型SPMBM(Shortest Path Map－BasedMovement)模型。

3 仿真結果分析

仿真以網絡中消息的生存期和消息數量即網絡流量為可變參數，分析以上兩個可變參數對各路由算法傳輸成功率、路由開銷、傳輸延遲和緩存時間等4個特性。

3.1 消息生存期對路由協議的影響

3.1.1 傳輸成功率

圖1顯示，當消息TTL較小時，各協議傳輸成功率較低，隨著消息TTL的增長，各路由算法的傳輸成功率均有增長，其中MaxProp和SprayAndWait協議增加尤為顯著，而DirectDelivery和FirstContact由于是單副本消息傳遞，消息TTL對傳輸成功率的影響不大，且消息傳輸成功率不高［15］。當消息TTL增長到一定程度后，各路由協議傳輸成功率增長趨緩，這說明在一定場景下，提高消息TTL到一定值后并不能顯著提高消息的傳輸成功率。當消息TTL到300 min后，Epidemic和Prophet協議隨消息TTL值增長，其傳輸成功率呈現下降趨勢，這是因為當消息TTL增長到一定值時，由洪泛引起冗余的消息副本長時間占據網絡節點的內存空間，使節點無法存儲自身生成的或從其他節點接收到的消息，導致消息傳輸成功率開始下降［16］。

3.1.2 路由開銷

路由開銷反映了消息轉發過程中對網絡的負擔，開銷率越大越容易造成網絡擁塞［17］。圖2顯示了各路由協議消息TTL對路由開銷的影響。由于DirectDelivery協議，只有當攜帶消息的源節點遇到目的節點時，消息才會的轉發，因此其開銷率總是為0。除此外，隨著消息TTL的變化，各協議中的路由開銷也隨之發生變化。其中MaxProp和Spray And Wait協議的路由開銷會隨消息TTL的增加而降低并趨向于維持一個相對穩定的范圍。當消息TTL到達300min后，Epidemic和Prophet協議由于消息副本數的增加導致開銷顯著增加。

圖1 消息生存期對傳輸成功率的影響

圖2 消息生存期對路由開銷的影響

圖3 消息生存期對平均傳輸延遲的影響

3.1.3 平均傳輸延遲

圖3表明消息的TTL對消息的平均傳輸延遲產生的影響較大。當消息的TTL達到一定值后，消息傳輸延遲的增長趨于緩和，以MaxProp為例，當消息的TTL值達到500 min時，其消息平均傳輸延遲基本上沒有變化，已經保持相對穩定的平均傳輸延遲。因為MaxProp協議在消息的TTL到了，或者節點收到一個ack消息，或者節點的數據緩存區被裝滿時，節點將丟棄該消息。因此當消息的TTL值到達一定值后，其對Max-Prop協議中的消息傳輸延遲影響很小。

3.1.4 平均緩存時間

圖4表明，消息的TTL對各路由協議中消息的平均緩存時間影響各異。其中影響較大的是 DirectDelivery和SprayAndWait，后者是因為在Wait階段會采取與前者一致的轉發策略，攜帶消息的節點會等待目的節點的出現，直到遇到目的節點。Epidemic和Prophet協議中，當消息的TTL增加時，消息在節點上的存儲時間也相應地增加。但當消息的TTL繼續增加時，由于洪泛產生的消息副本增多，節點因存儲空間不足而刪除大量的數據報文，使得數據報文平均存儲時間下降。FirstContact協議總是將消息轉發給第一個遇到的節點，因此其消息的平均緩存時間維持在一個相對較低且穩定的范圍，消息的TTL對其平均緩存時間影響不顯著。

3.2 網絡流量對路由協議的影響

在表1設定的場景中，以不同的網絡流量進行仿真，分析網絡流量對各路由協議的影響。根據消息生存期對各路由算法影響的分析，仿真中選定300 min作為消息的生存期。仿真表明，網絡流量的增大對各路由算法的4個特性的影響各異。

網絡流量對單副本機制路由算法的傳輸成功率DirectDelivery和FirstContact影響不大;而對其他算法影響較大。網絡流量較小時，MaxProp的傳輸成功率要好于其他協議;當網絡流量增大時，Epidemic、MaxProp、Prophet和SprayAndWait的傳輸成功率逐漸降低，網絡流量增大到一定程度時，四個協議的傳輸成功率的差距逐漸縮小。

SprayAndWait和DirectDelivery的路由開銷保持在一個相對穩定的范圍，變化不大，這說明以上兩個協議的路由開銷與網絡流量基本無關，這是因為SprayAndWait協議在Wait階段采取與DirectDelivery類似的轉發機制:等待與目的節點相遇，然后轉發消息。Prophet由于采用的是有限制的多路由復制，網絡流量增大時，消息轉發的次數會增大，其路由開銷與Epidemic協議逐漸接近。

網絡中的流量對各路由協議平均延遲均有影響，但影響不明顯。協議中是采用多副本的復制轉發還是單副本的轉發影響消息的傳輸延遲。

DirectDelivery和FirstContact算法的平均緩存時間與網絡流量無關，其他算法隨網絡流量增大而逐漸趨于穩定。

以網絡流量為可變因素的仿真說明:是否采用多副本的路由轉發，對傳輸成功率和傳輸延遲的影響較大;是采用單跳轉發和還是多跳的轉發策略，會對路由開銷有影響。

圖4 消息生存期對平均緩存時間的影響

4 結束語

為探索機會網絡在偏遠地區的應用，本文通過設定特定的網絡場景，對機會網絡中幾種典型的路由協議進行仿真，分析各路由協議在該場景中隨消息TTL和網絡流量的變化情況，綜合各路由算法在消息傳輸成功率、路由開銷、平均傳輸延遲、平均緩存時間的表現，得出如下結論:

(1)MaxProp和SprayAndWait協議隨消息生存期的增加具有較高的傳輸成功率和較低的路由開銷;網絡流量較大時，SprayAndWait協議要優于MaxProp協議;當網絡中節點的緩存空間有限時，則MaxProp協議要優于SprayAndWait協議。

(2)多副本的路由機制在傳輸成功率和傳輸延遲方面要優于單副本的路由機制。

在以后工作中，將深入研究對SprayAndWait協議和MaxProp協議的改進，進一步提高機會網絡在該類場景中的傳輸成功率、減少消息傳輸的延遲。

［1］熊永平，孫利民，牛建偉，等.機會網絡［J］.軟件學報，2009，20(1):124－137.

［2］任智，黃勇，陳前斌.機會網絡路由協議［J］.計算機應用，2010，30(3):723－728.

［3］Pentland A，Fletcher R，Hasson A.DakNet:Rethinking c0nnectivity in developing nations［J］.Computer，2004，37(1):78 －83.

［4］Avri D，Mana U，Durga PP.Providing connectivity to the Saami nomadic community［C］//In Proc.of the 2nd Int＇l Conf on Open Collaborative Design for Sustainable Innovation，Bangalore:IEEE press，2002.

［5］Brewer E Tier project.2006.［DB/OL］［2014 －05 －10］http://tier.cs.berkeley.edu/wiki/Home.

［6］Wizzy Project.［EB/OL］［2014 －08 －01］http://www.wizzy.org.za/.

［7］PELUSI L，PASSARELLA A，CONTI M.Opportunistic netuorking:data fornarding in disconnected mobile Ad Hecnetworks［J］.Communicatins，2006，44(1):134 －141.

［8］Apoorva J，Konstantinos P.Perfomance Analysis of Epidemic Routing Under Contention［C］//Proc.of the 2006 International Conference on Wireless Communications and Mobile Computing，Vancouver:ACM Press，2006:539 －544.

［9］Sushant Jain，Kevin Fall，Rabin Patra.Routing in a delay tolerant network［C］//In SIGCOMM ＇04:Proceedings of the 2004 conference on Applications，technologies，architectures，and protocols for computer communications，New York:ACM，2004:145－ 158.

［10］Burgess J，Gallagher B，Jensen D，et al.Maxprop:routing for vehicle－ based disruption tolerant networks［C］.Washington:Proc IEEE Infocom，2006:1－11.

［11］Lindgren，Doria A，Schelèn O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications，2003，7(3):19 －20.

［12］Spyropoulos T，Psounis K，Raghavendra C S.Spray and Wait:An Efficient Routing Scheme for Intermittently Connected Mobile Networks［C］//Proc.of the 2005 ACM SIGCOMM Workshop on Delay Tolerant Networking，Phiatelphia:ACM Press，2005:252 －259.

［13］KER NEN A，OTT J，K RKK INEN T.The ONE simulator for DTN protocol evaluation［C］ //Simutools ＇09:Proceedings of the 2nd International Conference on Simulation Tools and Techniques，Rome:Acm Press，2009:1 －10.

［14］CAO Y，SUN Z L，AHMAD N，et al.A mobility vector based routing algorithm for delay tolerant networks using history geographic information［C］//Proceedings of the International Conference on Wireless Communications and Networking.Washington DC:IEEE Communications Society，2012:2 757 －2 762.

［15］吳大鵬，楊正川，劉喬壽，等.帶有相遇預測的自適應路由機制［J］.重慶郵電大學學報(自然科學版)，2013，25(3):368－371.

［16］王蓬.機會網絡中帶有確認機制的多副本路由協議的研究與實現［D］.上海:華東師范大學，2010.

［17］錢景輝.一種機會網絡中節點轉發策略的改進［J］.微電子學與計算機.2013，30(1):5－7.