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

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

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

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

1 機(jī)會(huì)網(wǎng)絡(luò)中路由算法

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

2 仿真實(shí)驗(yàn)

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

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

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

2.2 機(jī)會(huì)網(wǎng)絡(luò)路由算法性能評(píng)價(jià)指標(biāo)

在以上仿真環(huán)境下，我們選取傳輸成功率、平均傳輸延遲和路由開銷比率三個(gè)主要的指標(biāo)來(lái)評(píng)價(jià)和分析機(jī)會(huì)網(wǎng)絡(luò)路由算法性能.

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

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

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

2.3 仿真結(jié)果分析

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

2.3.1 移動(dòng)模型對(duì)路由算法影響

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

圖1 移動(dòng)模型對(duì)傳輸成功率的影響Fig.1 Impact of the movement model on delivery ratio

圖2 移動(dòng)模型對(duì)平均傳輸延遲的影響Fig.2 Impact of the movement model on average delivery delay

圖3 移動(dòng)模型對(duì)路由開銷比率的影響Fig.3 Impact of the movement model on routing overhead ratio

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

2.3.2 節(jié)點(diǎn)密度對(duì)路由算法的影響

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

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

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

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

圖6 節(jié)點(diǎn)密度對(duì)路由開銷比率的影響Fig.6 Impact of the density of nodes on routing overhead ratio

2.3.3 報(bào)文傳輸速率對(duì)路由算法的影響

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

圖7 報(bào)文傳輸速率對(duì)傳輸成功率的影響Fig.7 Impact of the packet transmit speed on delivery ratio

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

從圖7中可以看出，隨著報(bào)文傳輸速率的增加，各路由算法的傳輸成功率也隨之增加，原因在于機(jī)會(huì)網(wǎng)絡(luò)通過節(jié)點(diǎn)相遇帶來(lái)的機(jī)會(huì)進(jìn)行報(bào)文轉(zhuǎn)發(fā)，而兩個(gè)節(jié)點(diǎn)的相遇時(shí)間是有限的，節(jié)點(diǎn)報(bào)文傳輸速率越快，成功轉(zhuǎn)發(fā)的報(bào)文也越多，報(bào)文到達(dá)目的節(jié)點(diǎn)的概率增大，因此傳輸成功率增加.當(dāng)報(bào)文傳輸速率較小時(shí)，報(bào)文傳輸速率對(duì)各個(gè)路由算法傳輸成功率的影響較為顯著，當(dāng)報(bào)文傳輸速率趨于較大值時(shí)，各路由算法的傳輸成功率逐漸趨于穩(wěn)定.從圖8中可以看出，Direct Delivery算法在報(bào)文傳輸速率較低時(shí)，平均傳輸延遲隨著報(bào)文傳輸速率的增加而有所增加，其他幾種算法的平均傳輸延遲均隨著報(bào)文傳輸速率的增加而減少.從圖9 中可以看出，F(xiàn)irst Contact、Epidemic、PRoPHET和MaxProp算法的路由開銷比率均隨著報(bào)文傳輸速率的增加而增加，Spray and Wait算法的路由開銷比率則有所下降.

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

2.3.4 報(bào)文TTL值對(duì)路由算法的影響

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

圖10 報(bào)文TTL值對(duì)傳輸成功率的影響Fig.10 Impact of the value of packet TTL on delivery ratio

圖11 報(bào)文TTL值對(duì)平均傳輸延遲的影響Fig.11 Impact of the value of packet TTL on average delivery delay

圖12 報(bào)文TTL值對(duì)路由開銷比率的影響Fig.12 Impact of the value of packet TTL on routing overhead ratio

TTL值指的是報(bào)文生存時(shí)間，在節(jié)點(diǎn)緩存空間充足的情況下，報(bào)文TTL值的增加使得在一定時(shí)間內(nèi)網(wǎng)絡(luò)中被丟棄的報(bào)文減少，成功到達(dá)目的節(jié)點(diǎn)的報(bào)文增加，報(bào)文傳輸成功率也隨之增加，如圖10所示，其中MaxProp和Spray and Wait算法傳輸成功率遠(yuǎn)大于其他算法.但是，當(dāng)報(bào)文TTL值過大時(shí)，也會(huì)使得節(jié)點(diǎn)緩存隊(duì)列中的報(bào)文太多而導(dǎo)致?lián)砣覀兛梢钥吹紼pidemic和PRoPHET算法在TTL值大于120min時(shí)，傳輸成功率有所下降.從圖11可以看出，各路由算法的平均傳輸延遲均隨著TTL的增大而增大.圖12表明，TTL 值對(duì) Direct Delivery、First Contact、MaxProp 和Spray and Wait算法的路由開銷比率影響不明顯.而Epidemic和PRoPHET算法的路由開銷比率隨著TTL的增大而增大.

3 結(jié)束語(yǔ)

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

［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ī)會(huì)網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2009，20(1):124－137.

［3］胡四泉，汪紅兵，王俊峰.機(jī)會(huì)型網(wǎng)絡(luò)研究綜述［J］.計(jì)算機(jī)科學(xué)，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］孫踐知.機(jī)會(huì)網(wǎng)絡(luò)路由算法［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.