基于ONE平臺的機會網絡路由協議仿真分析

王文濤，鄭 芳，王奇楓，郭 峰

(中南民族大學計算機科學學院，武漢430074)

機會網絡是移動自組織網絡(MANET)的一個子類［1］，但又具有不同于傳統移動自組織網絡的特點.傳統的MANET在傳輸用戶數據之前，需要預先建立完整的端到端的通信鏈路.這種路由機制隱含了一個重要的假設:網絡大部分時候是連通的，任一節點對之間存在至少一條完整的通信鏈路.然而在實際自組織網絡應用中，例如用來實時監測道路交通狀況的車載網絡、由手機等大量移動通信設備組成的手持設備自組織網絡、安裝無線傳感器節點于野生動物身上的野生動物追蹤網絡等，節點的移動性、節點稀疏分布、射頻信號關閉以及障礙物的存在等因素都會導致網絡部分通信連接處于斷開狀態［2］.為解決這個問題，機會網絡應運而生，其許多概念源于早期的延遲容忍網絡(DTN)［3］，它不需要源節點和目的節點之間存在完整鏈路，而是利用節點移動帶來的相遇機會實現網絡通信.

機會網絡以“存儲－攜帶－轉發”的路由機制實現節點間的通信［4］.這種路由機制不同于傳統的“存儲－轉發”路由機制，它增加了數據攜帶部分，在節點需要發送報文或是接收到來自其它節點的報文后，由于節點連接的間歇性特點，節點不能立即將報文轉發出去，于是存儲在緩存隊列中，并且攜帶這些報文信息移動，若遇到在彼此通信范圍的節點，則將其轉發，直到目的節點接收到該報文.正是由于這種不需要事先建立轉發路徑的路由機制的特點，機會網絡能夠滿足惡劣條件下的網絡通信需要，處理網絡中通信斷裂和延時等問題［5］.基于這種路由機制特點的路由協議也相繼被提出.本文通過ONE仿真平臺設計適合于機會網絡的仿真場景，并且對機會網絡中典型路由協議進行了仿真分析，通過傳輸成功率、平均傳輸延遲和路由開銷比率等3個路由性能指標比較并分析了不同網絡環境因素對路由算法的影響、各種路由算法的優缺點及適用場景.

1 機會網絡中路由算法

隨著機會網絡的不斷發展，人們提出許多機會網絡路由算法.文獻［2，3］分別從不同角度對機會網絡路由算法進行了分類.根據每個消息在網絡中傳播的副本數量，機會網絡路由算法可分為單副本路由和多副本路由兩類.單副本路由算法有Direct Delivery［6，7］、First Contact［8］等，該類路由協議在網絡中僅存在一個消息副本.單副本路由算法的開銷很小，但通常交付延遲較高，可靠性相對較低.多副本路由算法很多，如 Epidemic［9］、Spray and Wait［10］、PRoPHET［11］、MaxProp［12］等.多副本路由算法在同一時間網絡中有多個節點攜帶同一消息的副本.由于機會網絡動態變化，多副本路由算法增加了消息到達目標節點的概率，降低了交付延遲，但消耗了大量網絡資源.多副本路由算法主要包括基于復制的路由算法、基于社會屬性的路由算法和基于編碼的路由算法.可參見文獻［13］.

2 仿真實驗

2.1 仿真環境設置

本文使用機會網絡環境仿真器(ONE)［14］模擬行人攜帶藍牙通信設備行走于城市場景中，模擬實驗地圖選擇ONE自帶的赫爾辛基城市地圖.仿真默認參數設置如表1所示.在未加說明情況下，采用默認參數設置.

表1 仿真默認參數設置Tab.1 Simulation default parameter configuration

2.2 機會網絡路由算法性能評價指標

在以上仿真環境下，我們選取傳輸成功率、平均傳輸延遲和路由開銷比率三個主要的指標來評價和分析機會網絡路由算法性能.

(1)傳輸成功率，是指在一定時間內成功到達目的節點報文數量總數與源節點發出的報文總數之比.傳輸成功率標志著路由算法成功轉發報文到目的節點的能力，是重要的性能評價指標.

(2)平均傳輸延遲，是指報文從產生到被目的節點接收所需的平均時間.平均傳輸延遲小意味著路由算法傳輸能力強，傳輸效率高，網絡資源占用少，網絡資源利用率高.

(3)路由開銷比率，是指網絡中成功轉發報文數量與目的節點接收報文數量的差值同目的節點接收報文數量的比值，路由開銷比率說明了網絡中一個報文成功傳輸到目的節點所需的平均傳輸次數.

2.3 仿真結果分析

本文分別對 Direct Delivery、First Contact、Epidemic、PRoPHET、MaxProp、Spray and Wait等路由算法進行仿真，并分析比較了這些算法在不同的移動模型、節點密度、報文傳輸速率、報文TTL值下報文傳輸成功率、報文平均傳輸延遲、報文路由開銷比率的變化情況.

2.3.1 移動模型對路由算法影響

圖1、圖2和圖3分別給出了在隨機路徑移動模型(RWP)、基于地圖的隨機移動模型(MBM)、基于地圖的最短路徑移動模型(SPMBM)三種不同移動模型下，各路由算法傳輸成功率、平均傳輸延遲、路由開銷比率的變化情況.

圖1 移動模型對傳輸成功率的影響Fig.1 Impact of the movement model on delivery ratio

圖2 移動模型對平均傳輸延遲的影響Fig.2 Impact of the movement model on average delivery delay

圖3 移動模型對路由開銷比率的影響Fig.3 Impact of the movement model on routing overhead ratio

從圖1可以看出，在SPMBM移動模型下，各路由算法傳輸成功率最高，MBM次之，RWP最低.原因在于RWP是隨機移動模型，節點隨機選擇移動的方向、目的地，這將導致節點相遇概率低，網絡中轉發的報文總數少，同時這種隨機性使得多數報文沒有在消息生存時間(TTL)內達到目的節點而被丟棄，因此報文傳輸成功率低.MBM是基于地圖的移動模型，節點隨機選擇地圖中的路徑進行移動，節點相遇概率高于RWP移動模型.SPMBM是基于地圖的最短路徑移動模型，該模型使用Dijkstra算法依據地圖中點和路徑信息計算出源節點和目標節點之間的最短路徑，并令節點沿該路徑移動，因此使得成功到達目的節點報文增加，報文傳輸成功率提高.從圖2可以看出，除Direct Delivery算法外，其他算法在SPMBM移動模型下的平均傳輸延遲最低，在MBM下略高，在RWP下最高.圖3表明，節點移動模型對Direct Delivery、First Contact和MaxProp算法的路由開銷比率影響較小，Epidemic和PRoPHET算法的路由開銷比率明顯上升，Spray and Wait算法的路由開銷比率明顯下降.

2.3.2 節點密度對路由算法的影響

圖4、圖5和圖6分別給出了在節點數為20，40，60，100，200，400，600 個時，各路由算法傳輸成功率、平均傳輸延遲、路由開銷比率的變化情況.

由圖4可以看出，節點密度較低時，各路由算法傳輸成功率差別不大，隨著節點密度的增大，節點間的通信機會也相應增加，各路由算法的傳輸成功率均有所增大.其中MaxProp和Spray and Wait算法傳輸成功率增加較為顯著，且傳輸成功率明顯高于其他路由算法，當節點數為600個時，二者傳輸成功率均在80%左右.其他路由算法的傳輸成功率均在30%以下.由圖5可知，MaxProp算法節點密度較大時，傳輸延遲有所下降，而其他路由算法的傳輸延遲均隨著節點密度的增大而增大.由圖6可知，節點密度較小時，各路由算法路由開銷比率較小且無明顯差別，當節點數超過200個時，Epidemic算法和PRoPHET算法路由開銷比率急劇增加，而Direct Delivery算法、Spray and Wait算法基本沒有變化.

圖4 節點密度對傳輸成功率的影響Fig.4 Impact of the density of nodes on delivery ratio

圖5 節點密度對平均傳輸延遲的影響Fig.5 Impact of the density of nodes on average delivery delay

圖6 節點密度對路由開銷比率的影響Fig.6 Impact of the density of nodes on routing overhead ratio

2.3.3 報文傳輸速率對路由算法的影響

圖7、圖8和圖9分別給出了在報文傳輸速率為20，50，100，150，200，250 kbit/s時，各路由算法傳輸成功率、平均傳輸延遲、路由開銷比率的變化情況.

圖7 報文傳輸速率對傳輸成功率的影響Fig.7 Impact of the packet transmit speed on delivery ratio

圖8 報文傳輸速率對平均傳輸延遲的影響Fig.8 Impact of the packet transmit speed on average delivery delay

從圖7中可以看出，隨著報文傳輸速率的增加，各路由算法的傳輸成功率也隨之增加，原因在于機會網絡通過節點相遇帶來的機會進行報文轉發，而兩個節點的相遇時間是有限的，節點報文傳輸速率越快，成功轉發的報文也越多，報文到達目的節點的概率增大，因此傳輸成功率增加.當報文傳輸速率較小時，報文傳輸速率對各個路由算法傳輸成功率的影響較為顯著，當報文傳輸速率趨于較大值時，各路由算法的傳輸成功率逐漸趨于穩定.從圖8中可以看出，Direct Delivery算法在報文傳輸速率較低時，平均傳輸延遲隨著報文傳輸速率的增加而有所增加，其他幾種算法的平均傳輸延遲均隨著報文傳輸速率的增加而減少.從圖9 中可以看出，First Contact、Epidemic、PRoPHET和MaxProp算法的路由開銷比率均隨著報文傳輸速率的增加而增加，Spray and Wait算法的路由開銷比率則有所下降.

圖9 報文傳輸速率對路由開銷比率的影響Fig.9 Impact of the packet transmit speed on routing overhead ratio

2.3.4 報文TTL值對路由算法的影響

圖10、圖11和圖12分別給出了在報文TTL值為30，60，120，180，240，300min 時，各路由算法的傳輸成功率、平均傳輸延遲、路由開銷比率的變化情況.

圖10 報文TTL值對傳輸成功率的影響Fig.10 Impact of the value of packet TTL on delivery ratio

圖11 報文TTL值對平均傳輸延遲的影響Fig.11 Impact of the value of packet TTL on average delivery delay

圖12 報文TTL值對路由開銷比率的影響Fig.12 Impact of the value of packet TTL on routing overhead ratio

TTL值指的是報文生存時間，在節點緩存空間充足的情況下，報文TTL值的增加使得在一定時間內網絡中被丟棄的報文減少，成功到達目的節點的報文增加，報文傳輸成功率也隨之增加，如圖10所示，其中MaxProp和Spray and Wait算法傳輸成功率遠大于其他算法.但是，當報文TTL值過大時，也會使得節點緩存隊列中的報文太多而導致擁塞，我們可以看到Epidemic和PRoPHET算法在TTL值大于120min時，傳輸成功率有所下降.從圖11可以看出，各路由算法的平均傳輸延遲均隨著TTL的增大而增大.圖12表明，TTL 值對 Direct Delivery、First Contact、MaxProp 和Spray and Wait算法的路由開銷比率影響不明顯.而Epidemic和PRoPHET算法的路由開銷比率隨著TTL的增大而增大.

3 結束語

本文利用ONE仿真平臺，從傳輸成功率、平均傳輸延遲和路由開銷比率三個路由性能評價指標入手，仿真并分析了節點移動模型、節點密度、報文傳輸速率、報文TTL值對6種機會網絡路由算法的影響.實驗結果表明:節點移動模型、節點密度、節點報文傳輸速率和報文TTL值對各路由算法均產生顯著影響.相比于RWP和MBM，SPMBM移動模型下各算法的傳輸成功率最高.當節點密度稀疏時，各路由算法性能差異不大;但當節點密度較大時，Spray and Wait和MaxProp算法傳輸成功率明顯高于其他算法，說明Spray and Wait和MaxProp算法更能適應節點密集的網絡環境.在節點報文傳輸速率增大的情況下，各路由算法的傳輸成功率增大，平均傳輸延遲減小.當報文傳輸速率增大到一定值時，各路由算法性能趨于穩定.報文TTL值的增大使得各算法的傳輸成功率增大，但對于Epidemic和PRoPHET算法，在TTL值較大時，傳輸成功率有所下降.在各個仿真環境下，Spray and Wait和MaxProp算法都具有較高的傳輸成功率，但Spray and Wait的路由開銷遠低于MaxProp算法.PRoPHET算法相對于Epidemic算法做了改進，通過估計節點間的傳輸概率值來判斷是否轉發報文，而在本文的仿真場景下，兩個路由算法性能表現差異不大，PRoPHET算法并沒有表現出明顯的優勢.Direct Delivery算法傳輸成功率不高，但其路由開銷比率始終為零.First Contact傳輸成功率在各仿真環境下傳輸成功率最低，且路由開銷比率較大.通過上述分析，Spray and Wait算法在多數仿真場景下具有傳輸成功率高和路由開銷低的特點，但節點密度大時傳輸延遲高，而MaxProp算法的傳輸延遲不會隨節點密度的增加而增加，進一步研究工作將結合Spray and Wait算法和MaxProp算法的優點，提出一種適合各種節點密度的高效路由算法.

［1］Soelistijanto B，Howarth M P.Transfer reliability and congestion control strategies in opportunistic networks:a survey［J］.Communications Surveys ＆ Tutorials，IEEE，2014，16(1):538－555.

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

［3］胡四泉，汪紅兵，王俊峰.機會型網絡研究綜述［J］.計算機科學，2009，36(10):32－37.

［4］Poonguzharselvi B，Vetriselvi V.Survey on routing algorithms in opportunistic networks［C］//IEEE.ICCCI.Piscataway，NJ:IEEE，2013:1－5.

［5］孫踐知.機會網絡路由算法［M］.北京:人民郵電出版社，2013:1－2.

［6］Spyropoulos T，Psounis K，Raghavendra C S.Single－copy routing in intermittently connected mobile network［C］//IEEE.Sensor and Ad Hoc Communications and Network.Piscataway，NJ:IEEE，2004:235－244.

［7］Spyropoulos T，Psounis K，Raghavendra C S.Efficient routing in intermittently connected mobile networks:the single－copy case［J］.IEEE/ACM Transactionson Networking，2008，16(1):63－76.

［8］Jain S，Fall K，Patra R.Routing in a delay tolerant network［C］//ACM.SIGCOMM.New York:ACM，2004:145－158.

［9］Vahdat A，Becker D.Epidemic routing for partiallyconnected Ad Hoc networks［R］.Technical Report CS－200006，Durham:Duke University，2000.

［10］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait:an efficientrouting scheme forintermittently connected mobile networks［C］//ACM.SIGCOMM.New York:ACM，2005:252－259.

［11］Lindgren A，Doria A，Schel'en O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE MobileComputingandCommunications Review，2003，7(3):19－20.

［12］Burgess J，Gallagher B，Jensen D，et al.MaxProp:routing for vehicle－based disruption－tolerant networks［C］//IEEE.INFOCOM.Piscataway，NJ:IEEE，2006:1－11.

［13］Socievole A，De Rango F.Evaluation of routing schemes in opportunistic networks considering energy consumption［C］//IEEE.Performance Evaluation of Computer and Telecommunication Systems.Piscataway，NJ:IEEE，2012:41－47.

［14］Ari K，J?rg O，Teemu K.The ONE simulator for DTN protocol evaluation［C］//ICST.Proceedings of the 2nd InternationalConference on Simulation Tools and Techniques.Brussels:ICST，2009:55－64.