龔丁海，黃曉航，譚松鶴

(河池學(xué)院 1.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院;2.計(jì)算機(jī)與信息工程學(xué)院，廣西 宜州 546300)

0 引言

機(jī)會(huì)網(wǎng)絡(luò)［1］是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)網(wǎng)絡(luò)通信的、時(shí)延和分裂可容忍的自組織網(wǎng)絡(luò)［1－2］。機(jī)會(huì)網(wǎng)絡(luò)以“存儲(chǔ)－攜帶－轉(zhuǎn)發(fā)”的機(jī)制進(jìn)行消息的傳送，主要應(yīng)用于缺少通信基礎(chǔ)設(shè)施、網(wǎng)絡(luò)環(huán)境惡劣等場(chǎng)合，如袖珍型交換網(wǎng)絡(luò)，偏遠(yuǎn)地區(qū)互聯(lián)網(wǎng)無(wú)線接入等［2］。DakNet項(xiàng)目［3］是在印度偏遠(yuǎn)地區(qū)部署機(jī)會(huì)網(wǎng)絡(luò)，以便為鄉(xiāng)村地區(qū)提供通信連接;類似的還有Saami-NetworkConnectivity項(xiàng)目［4］，Tier項(xiàng)目［5］和 Wizzy系統(tǒng)［6］?；跈C(jī)會(huì)網(wǎng)絡(luò)的特性和機(jī)會(huì)網(wǎng)絡(luò)在偏遠(yuǎn)地區(qū)應(yīng)用的潛力，本文通過(guò)設(shè)定一個(gè)類似于偏遠(yuǎn)地區(qū)特性的網(wǎng)絡(luò)場(chǎng)景，對(duì)機(jī)會(huì)網(wǎng)絡(luò)幾種典型的路由協(xié)議在該場(chǎng)景中的性能、特點(diǎn)進(jìn)行分析比較，以評(píng)價(jià)各路由算法在該場(chǎng)景的應(yīng)用。

1 機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議

1.1 直接傳輸協(xié)議(DirectDelivery)

DirectDelivery［7］是典型的單副本路由協(xié)議，也是最簡(jiǎn)單的路由機(jī)制。該路由協(xié)議由源節(jié)點(diǎn)攜帶消息移動(dòng)，直到遇到目的節(jié)點(diǎn)，將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。

1.2 傳染轉(zhuǎn)發(fā)協(xié)議(Epidemic)

Epidemic［8］本質(zhì)上是一種洪泛，其基本思想是網(wǎng)絡(luò)中兩個(gè)相遇的節(jié)點(diǎn)均會(huì)交換相互沒(méi)有的消息。節(jié)點(diǎn)間足夠的交換，理論上讓每個(gè)非孤立的節(jié)點(diǎn)將收到所有的數(shù)據(jù)包，能最大化數(shù)據(jù)包傳輸?shù)某晒β剩瑴p少傳輸延遲［8］。但在網(wǎng)絡(luò)資源受限的實(shí)際網(wǎng)絡(luò)中，會(huì)由于洪泛而導(dǎo)致網(wǎng)絡(luò)中消息副本數(shù)量增多而消耗網(wǎng)絡(luò)資源。

1.3 FirstContact協(xié)議

FirstContact［9］是一種單副本路由協(xié)議，源節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給第一個(gè)遇到的節(jié)點(diǎn)，攜帶該消息的節(jié)點(diǎn)繼續(xù)將消息轉(zhuǎn)發(fā)給它第一個(gè)遇到的節(jié)點(diǎn)，如此反復(fù)，直到消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。

1.4 MaxProp算法

Maxprop［10］協(xié)議在Epidemic的基礎(chǔ)上進(jìn)行了改進(jìn)，改進(jìn)之處在于:源節(jié)點(diǎn)為消息設(shè)定有效期TTL，在轉(zhuǎn)發(fā)過(guò)程中，當(dāng)消息的有效期到了，或者節(jié)點(diǎn)收到一個(gè)ack消息，或者節(jié)點(diǎn)的數(shù)據(jù)緩存區(qū)被裝滿時(shí)，節(jié)點(diǎn)將丟棄該消息。Maxprop能夠避免每個(gè)消息都被泛洪到全網(wǎng)，減少了開(kāi)銷;但消息有效期的合理設(shè)置有一定難度［2］。

1.5 Prophet協(xié)議

Prophet［11］是基于概率的路由協(xié)議，每個(gè)節(jié)點(diǎn)估計(jì)到達(dá)其他節(jié)點(diǎn)的相遇概率，概率值隨節(jié)點(diǎn)間相遇而升高，不相遇時(shí)則隨時(shí)間遞減，節(jié)點(diǎn)利用概率傳遞性來(lái)更新與其他節(jié)點(diǎn)之間的可達(dá)概率，從而獲取與目標(biāo)節(jié)點(diǎn)的相遇概率。

1.6 SprayAndWait協(xié)議

SprayAndWait［12］協(xié)議通過(guò)設(shè)定每個(gè)消息在網(wǎng)絡(luò)中的副本數(shù)來(lái)控制洪泛的程度。該協(xié)議分為兩個(gè)階段，在Spray階段，源節(jié)點(diǎn)將在網(wǎng)絡(luò)中產(chǎn)生L份副本擴(kuò)散到L(L＞1)個(gè)中繼節(jié)點(diǎn);在Wait階段，若在Spray階段沒(méi)有發(fā)現(xiàn)目的節(jié)點(diǎn)，那么包含消息的節(jié)點(diǎn)通過(guò)直接傳輸?shù)姆绞桨研畔魉偷侥康墓?jié)點(diǎn)。SprayAndWait協(xié)議包含有Binary模式和非Binary模式。在Binary模式下，源節(jié)點(diǎn)將一半數(shù)據(jù)包發(fā)送給遇到的中繼節(jié)點(diǎn)，自己留下一半數(shù)據(jù)包;隨后源節(jié)點(diǎn)和中繼節(jié)點(diǎn)重復(fù)進(jìn)行上述過(guò)程，直到所有節(jié)點(diǎn)中只有一個(gè)數(shù)據(jù)包時(shí)，節(jié)點(diǎn)轉(zhuǎn)入Wait階段，采用直接傳輸給目的節(jié)點(diǎn)。

2 仿真場(chǎng)景設(shè)置

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

表1 各移動(dòng)節(jié)點(diǎn)特征

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

3 仿真結(jié)果分析

仿真以網(wǎng)絡(luò)中消息的生存期和消息數(shù)量即網(wǎng)絡(luò)流量為可變參數(shù)，分析以上兩個(gè)可變參數(shù)對(duì)各路由算法傳輸成功率、路由開(kāi)銷、傳輸延遲和緩存時(shí)間等4個(gè)特性。

3.1 消息生存期對(duì)路由協(xié)議的影響

3.1.1 傳輸成功率

圖1顯示，當(dāng)消息TTL較小時(shí)，各協(xié)議傳輸成功率較低，隨著消息TTL的增長(zhǎng)，各路由算法的傳輸成功率均有增長(zhǎng)，其中MaxProp和SprayAndWait協(xié)議增加尤為顯著，而DirectDelivery和FirstContact由于是單副本消息傳遞，消息TTL對(duì)傳輸成功率的影響不大，且消息傳輸成功率不高［15］。當(dāng)消息TTL增長(zhǎng)到一定程度后，各路由協(xié)議傳輸成功率增長(zhǎng)趨緩，這說(shuō)明在一定場(chǎng)景下，提高消息TTL到一定值后并不能顯著提高消息的傳輸成功率。當(dāng)消息TTL到300 min后，Epidemic和Prophet協(xié)議隨消息TTL值增長(zhǎng)，其傳輸成功率呈現(xiàn)下降趨勢(shì)，這是因?yàn)楫?dāng)消息TTL增長(zhǎng)到一定值時(shí)，由洪泛引起冗余的消息副本長(zhǎng)時(shí)間占據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的內(nèi)存空間，使節(jié)點(diǎn)無(wú)法存儲(chǔ)自身生成的或從其他節(jié)點(diǎn)接收到的消息，導(dǎo)致消息傳輸成功率開(kāi)始下降［16］。

3.1.2 路由開(kāi)銷

路由開(kāi)銷反映了消息轉(zhuǎn)發(fā)過(guò)程中對(duì)網(wǎng)絡(luò)的負(fù)擔(dān)，開(kāi)銷率越大越容易造成網(wǎng)絡(luò)擁塞［17］。圖2顯示了各路由協(xié)議消息TTL對(duì)路由開(kāi)銷的影響。由于DirectDelivery協(xié)議，只有當(dāng)攜帶消息的源節(jié)點(diǎn)遇到目的節(jié)點(diǎn)時(shí)，消息才會(huì)的轉(zhuǎn)發(fā)，因此其開(kāi)銷率總是為0。除此外，隨著消息TTL的變化，各協(xié)議中的路由開(kāi)銷也隨之發(fā)生變化。其中MaxProp和Spray And Wait協(xié)議的路由開(kāi)銷會(huì)隨消息TTL的增加而降低并趨向于維持一個(gè)相對(duì)穩(wěn)定的范圍。當(dāng)消息TTL到達(dá)300min后，Epidemic和Prophet協(xié)議由于消息副本數(shù)的增加導(dǎo)致開(kāi)銷顯著增加。

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

圖2 消息生存期對(duì)路由開(kāi)銷的影響

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

3.1.3 平均傳輸延遲

圖3表明消息的TTL對(duì)消息的平均傳輸延遲產(chǎn)生的影響較大。當(dāng)消息的TTL達(dá)到一定值后，消息傳輸延遲的增長(zhǎng)趨于緩和，以MaxProp為例，當(dāng)消息的TTL值達(dá)到500 min時(shí)，其消息平均傳輸延遲基本上沒(méi)有變化，已經(jīng)保持相對(duì)穩(wěn)定的平均傳輸延遲。因?yàn)镸axProp協(xié)議在消息的TTL到了，或者節(jié)點(diǎn)收到一個(gè)ack消息，或者節(jié)點(diǎn)的數(shù)據(jù)緩存區(qū)被裝滿時(shí)，節(jié)點(diǎn)將丟棄該消息。因此當(dāng)消息的TTL值到達(dá)一定值后，其對(duì)Max-Prop協(xié)議中的消息傳輸延遲影響很小。

3.1.4 平均緩存時(shí)間

圖4表明，消息的TTL對(duì)各路由協(xié)議中消息的平均緩存時(shí)間影響各異。其中影響較大的是 DirectDelivery和SprayAndWait，后者是因?yàn)樵赪ait階段會(huì)采取與前者一致的轉(zhuǎn)發(fā)策略，攜帶消息的節(jié)點(diǎn)會(huì)等待目的節(jié)點(diǎn)的出現(xiàn)，直到遇到目的節(jié)點(diǎn)。Epidemic和Prophet協(xié)議中，當(dāng)消息的TTL增加時(shí)，消息在節(jié)點(diǎn)上的存儲(chǔ)時(shí)間也相應(yīng)地增加。但當(dāng)消息的TTL繼續(xù)增加時(shí)，由于洪泛產(chǎn)生的消息副本增多，節(jié)點(diǎn)因存儲(chǔ)空間不足而刪除大量的數(shù)據(jù)報(bào)文，使得數(shù)據(jù)報(bào)文平均存儲(chǔ)時(shí)間下降。FirstContact協(xié)議總是將消息轉(zhuǎn)發(fā)給第一個(gè)遇到的節(jié)點(diǎn)，因此其消息的平均緩存時(shí)間維持在一個(gè)相對(duì)較低且穩(wěn)定的范圍，消息的TTL對(duì)其平均緩存時(shí)間影響不顯著。

3.2 網(wǎng)絡(luò)流量對(duì)路由協(xié)議的影響

在表1設(shè)定的場(chǎng)景中，以不同的網(wǎng)絡(luò)流量進(jìn)行仿真，分析網(wǎng)絡(luò)流量對(duì)各路由協(xié)議的影響。根據(jù)消息生存期對(duì)各路由算法影響的分析，仿真中選定300 min作為消息的生存期。仿真表明，網(wǎng)絡(luò)流量的增大對(duì)各路由算法的4個(gè)特性的影響各異。

網(wǎng)絡(luò)流量對(duì)單副本機(jī)制路由算法的傳輸成功率DirectDelivery和FirstContact影響不大;而對(duì)其他算法影響較大。網(wǎng)絡(luò)流量較小時(shí)，MaxProp的傳輸成功率要好于其他協(xié)議;當(dāng)網(wǎng)絡(luò)流量增大時(shí)，Epidemic、MaxProp、Prophet和SprayAndWait的傳輸成功率逐漸降低，網(wǎng)絡(luò)流量增大到一定程度時(shí)，四個(gè)協(xié)議的傳輸成功率的差距逐漸縮小。

SprayAndWait和DirectDelivery的路由開(kāi)銷保持在一個(gè)相對(duì)穩(wěn)定的范圍，變化不大，這說(shuō)明以上兩個(gè)協(xié)議的路由開(kāi)銷與網(wǎng)絡(luò)流量基本無(wú)關(guān)，這是因?yàn)镾prayAndWait協(xié)議在Wait階段采取與DirectDelivery類似的轉(zhuǎn)發(fā)機(jī)制:等待與目的節(jié)點(diǎn)相遇，然后轉(zhuǎn)發(fā)消息。Prophet由于采用的是有限制的多路由復(fù)制，網(wǎng)絡(luò)流量增大時(shí)，消息轉(zhuǎn)發(fā)的次數(shù)會(huì)增大，其路由開(kāi)銷與Epidemic協(xié)議逐漸接近。

網(wǎng)絡(luò)中的流量對(duì)各路由協(xié)議平均延遲均有影響，但影響不明顯。協(xié)議中是采用多副本的復(fù)制轉(zhuǎn)發(fā)還是單副本的轉(zhuǎn)發(fā)影響消息的傳輸延遲。

DirectDelivery和FirstContact算法的平均緩存時(shí)間與網(wǎng)絡(luò)流量無(wú)關(guān)，其他算法隨網(wǎng)絡(luò)流量增大而逐漸趨于穩(wěn)定。

以網(wǎng)絡(luò)流量為可變因素的仿真說(shuō)明:是否采用多副本的路由轉(zhuǎn)發(fā)，對(duì)傳輸成功率和傳輸延遲的影響較大;是采用單跳轉(zhuǎn)發(fā)和還是多跳的轉(zhuǎn)發(fā)策略，會(huì)對(duì)路由開(kāi)銷有影響。

圖4 消息生存期對(duì)平均緩存時(shí)間的影響

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

為探索機(jī)會(huì)網(wǎng)絡(luò)在偏遠(yuǎn)地區(qū)的應(yīng)用，本文通過(guò)設(shè)定特定的網(wǎng)絡(luò)場(chǎng)景，對(duì)機(jī)會(huì)網(wǎng)絡(luò)中幾種典型的路由協(xié)議進(jìn)行仿真，分析各路由協(xié)議在該場(chǎng)景中隨消息TTL和網(wǎng)絡(luò)流量的變化情況，綜合各路由算法在消息傳輸成功率、路由開(kāi)銷、平均傳輸延遲、平均緩存時(shí)間的表現(xiàn)，得出如下結(jié)論:

(1)MaxProp和SprayAndWait協(xié)議隨消息生存期的增加具有較高的傳輸成功率和較低的路由開(kāi)銷;網(wǎng)絡(luò)流量較大時(shí)，SprayAndWait協(xié)議要優(yōu)于MaxProp協(xié)議;當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的緩存空間有限時(shí)，則MaxProp協(xié)議要優(yōu)于SprayAndWait協(xié)議。

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

在以后工作中，將深入研究對(duì)SprayAndWait協(xié)議和MaxProp協(xié)議的改進(jìn)，進(jìn)一步提高機(jī)會(huì)網(wǎng)絡(luò)在該類場(chǎng)景中的傳輸成功率、減少消息傳輸?shù)难舆t。

［1］熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，2009，20(1):124－137.

［2］任智，黃勇，陳前斌.機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用，2010，30(3):723－728.

［3］Pentland A，F(xiàn)letcher 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］吳大鵬，楊正川，劉喬壽，等.帶有相遇預(yù)測(cè)的自適應(yīng)路由機(jī)制［J］.重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，25(3):368－371.

［16］王蓬.機(jī)會(huì)網(wǎng)絡(luò)中帶有確認(rèn)機(jī)制的多副本路由協(xié)議的研究與實(shí)現(xiàn)［D］.上海:華東師范大學(xué)，2010.

［17］錢景輝.一種機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)轉(zhuǎn)發(fā)策略的改進(jìn)［J］.微電子學(xué)與計(jì)算機(jī).2013，30(1):5－7.