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

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

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

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

1 機會網(wǎng)絡中路由算法

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

2 仿真實驗

2.1 仿真環(huán)境設置

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

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

2.2 機會網(wǎng)絡路由算法性能評價指標

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

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

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

(3)路由開銷比率，是指網(wǎng)絡中成功轉(zhuǎn)發(fā)報文數(shù)量與目的節(jié)點接收報文數(shù)量的差值同目的節(jié)點接收報文數(shù)量的比值，路由開銷比率說明了網(wǎng)絡中一個報文成功傳輸?shù)侥康墓?jié)點所需的平均傳輸次數(shù).

2.3 仿真結果分析

本文分別對 Direct Delivery、First Contact、Epidemic、PRoPHET、MaxProp、Spray and Wait等路由算法進行仿真，并分析比較了這些算法在不同的移動模型、節(jié)點密度、報文傳輸速率、報文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是隨機移動模型，節(jié)點隨機選擇移動的方向、目的地，這將導致節(jié)點相遇概率低，網(wǎng)絡中轉(zhuǎn)發(fā)的報文總數(shù)少，同時這種隨機性使得多數(shù)報文沒有在消息生存時間(TTL)內(nèi)達到目的節(jié)點而被丟棄，因此報文傳輸成功率低.MBM是基于地圖的移動模型，節(jié)點隨機選擇地圖中的路徑進行移動，節(jié)點相遇概率高于RWP移動模型.SPMBM是基于地圖的最短路徑移動模型，該模型使用Dijkstra算法依據(jù)地圖中點和路徑信息計算出源節(jié)點和目標節(jié)點之間的最短路徑，并令節(jié)點沿該路徑移動，因此使得成功到達目的節(jié)點報文增加，報文傳輸成功率提高.從圖2可以看出，除Direct Delivery算法外，其他算法在SPMBM移動模型下的平均傳輸延遲最低，在MBM下略高，在RWP下最高.圖3表明，節(jié)點移動模型對Direct Delivery、First Contact和MaxProp算法的路由開銷比率影響較小，Epidemic和PRoPHET算法的路由開銷比率明顯上升，Spray and Wait算法的路由開銷比率明顯下降.

2.3.2 節(jié)點密度對路由算法的影響

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

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

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

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

圖6 節(jié)點密度對路由開銷比率的影響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中可以看出，隨著報文傳輸速率的增加，各路由算法的傳輸成功率也隨之增加，原因在于機會網(wǎng)絡通過節(jié)點相遇帶來的機會進行報文轉(zhuǎn)發(fā)，而兩個節(jié)點的相遇時間是有限的，節(jié)點報文傳輸速率越快，成功轉(zhuǎn)發(fā)的報文也越多，報文到達目的節(jié)點的概率增大，因此傳輸成功率增加.當報文傳輸速率較小時，報文傳輸速率對各個路由算法傳輸成功率的影響較為顯著，當報文傳輸速率趨于較大值時，各路由算法的傳輸成功率逐漸趨于穩(wěn)定.從圖8中可以看出，Direct Delivery算法在報文傳輸速率較低時，平均傳輸延遲隨著報文傳輸速率的增加而有所增加，其他幾種算法的平均傳輸延遲均隨著報文傳輸速率的增加而減少.從圖9 中可以看出，F(xiàn)irst 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值指的是報文生存時間，在節(jié)點緩存空間充足的情況下，報文TTL值的增加使得在一定時間內(nèi)網(wǎng)絡中被丟棄的報文減少，成功到達目的節(jié)點的報文增加，報文傳輸成功率也隨之增加，如圖10所示，其中MaxProp和Spray and Wait算法傳輸成功率遠大于其他算法.但是，當報文TTL值過大時，也會使得節(jié)點緩存隊列中的報文太多而導致?lián)砣?，我們可以看到Epidemic和PRoPHET算法在TTL值大于120min時，傳輸成功率有所下降.從圖11可以看出，各路由算法的平均傳輸延遲均隨著TTL的增大而增大.圖12表明，TTL 值對 Direct Delivery、First Contact、MaxProp 和Spray and Wait算法的路由開銷比率影響不明顯.而Epidemic和PRoPHET算法的路由開銷比率隨著TTL的增大而增大.

3 結束語

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

［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］熊永平，孫利民，牛建偉，等.機會網(wǎng)絡［J］.軟件學報，2009，20(1):124－137.

［3］胡四泉，汪紅兵，王俊峰.機會型網(wǎng)絡研究綜述［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］孫踐知.機會網(wǎng)絡路由算法［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，F(xiàn)all 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.