劉永廣

DTN基于位置的RAPID路由算法

劉永廣

(廣東輕工職業(yè)技術(shù)學(xué)院 廣州 510300; 中國電子科技集團(tuán)公司第七研究所 廣州 510310)

面向意向容遲網(wǎng)絡(luò)的資源分配協(xié)議(RAPID)路由算法通過引入效能函數(shù)避免其他容遲網(wǎng)絡(luò)(DTN)路由算法對某一性能指標(biāo)的影響。然而算法中的相遇時(shí)間分布問題增加了算法的不確定性和應(yīng)用局限性。針對這一問題，該文設(shè)計(jì)了新的基于位置信息的效能函數(shù)計(jì)算方法。新方法通過元數(shù)據(jù)交換獲得各個(gè)節(jié)點(diǎn)的位置信息，采用灰色系統(tǒng)預(yù)測算法獲得較長時(shí)間沒有消息的目的節(jié)點(diǎn)的位置信息。通過最小化到達(dá)目的節(jié)點(diǎn)的時(shí)間，設(shè)計(jì)了更詳細(xì)的消息復(fù)制優(yōu)先級及復(fù)制規(guī)則。仿真表明，新算法能有效克服RAPID算法的問題，降低了消息復(fù)制數(shù)和平均時(shí)延，提高了消息成功遞交率，網(wǎng)絡(luò)的整體性能得到進(jìn)一步提升。

容遲網(wǎng)絡(luò); 位置; RAPID; 路由; 效能

DTN是一種特殊的無線網(wǎng)絡(luò)，這種網(wǎng)絡(luò)往往具有以下部分或全部特征：通信節(jié)點(diǎn)運(yùn)動(dòng)劇烈、通信鏈路帶寬受限、通信環(huán)境條件惡劣、通信過程容易被遮擋和受到干擾，存在多種通信模式的異構(gòu)子網(wǎng)等[1]。DTN在實(shí)際中具有廣泛的應(yīng)用，主要應(yīng)用在軍事上的戰(zhàn)術(shù)互聯(lián)網(wǎng)[2]、城市中的車輛網(wǎng)[3]、各種各樣復(fù)雜環(huán)境下的傳感網(wǎng)[4]等領(lǐng)域。

DTN的特點(diǎn)最終表現(xiàn)為整個(gè)網(wǎng)絡(luò)不能維持穩(wěn)定的基于TCP/IP的通信，傳統(tǒng)路由協(xié)議性能下降，無法完成拓?fù)渚S護(hù)和組網(wǎng)要求。針對DTN的特點(diǎn)，文獻(xiàn)[5-8]提出了一些新的路由算法和機(jī)制，并均采用了存儲(chǔ)轉(zhuǎn)發(fā)技術(shù)和多副本路由。這些算法盡管提高了性能，但是在提高某一性能指標(biāo)上存在較大的偶然性[9]。為了提高算法對某度量的確定性，文獻(xiàn)[9]提出的RAPID算法通過構(gòu)造針對某度量的優(yōu)化函數(shù)，優(yōu)先保證效能函數(shù)最優(yōu)的報(bào)文的遞交和復(fù)制，并在實(shí)踐中進(jìn)行了成功應(yīng)用。然而該算法采用指數(shù)分布作為節(jié)點(diǎn)間的相遇時(shí)間，只是為了計(jì)算方便，沒有理論依據(jù)，在其他場景下是否足夠和可行尚未可知。一些研究把位置信息應(yīng)用到DTN的路由中來，文獻(xiàn)[10]中的節(jié)點(diǎn)通過從錨節(jié)點(diǎn)周期性的接收信標(biāo)報(bào)文獲得節(jié)點(diǎn)的定位和移動(dòng)信息，提高遞交成功率，其實(shí)質(zhì)是一種有中心的拓?fù)浣Y(jié)構(gòu)，當(dāng)錨節(jié)點(diǎn)失效時(shí)網(wǎng)絡(luò)將陷于癱瘓。文獻(xiàn)[11]中僅預(yù)測了目標(biāo)節(jié)點(diǎn)的位置，且當(dāng)副本數(shù)為1時(shí)采用貪婪轉(zhuǎn)發(fā)，導(dǎo)致副本數(shù)量增加，影響了算法的性能。文獻(xiàn)[12]中利用了獨(dú)立的general packet radio service(GPRS)網(wǎng)絡(luò)模塊獲取各節(jié)點(diǎn)的位置信息，形成全局拓?fù)?，但需要額外GPRS網(wǎng)絡(luò)的支持，增加了系統(tǒng)的復(fù)雜性和費(fèi)用，對于GPRS網(wǎng)絡(luò)覆蓋不到的地方無法應(yīng)用，不適用于獨(dú)立DTN的部署。文獻(xiàn)[13]提出了一種基于位置信息的DTN城域公交網(wǎng)絡(luò)，該網(wǎng)絡(luò)借助于bus information system(BIS)數(shù)據(jù)庫的支持獲得精確的目的節(jié)點(diǎn)方向，并在該方向轉(zhuǎn)發(fā)數(shù)據(jù)，獲得良好的性能，但對于BIS的依賴限制了其應(yīng)用范圍。文獻(xiàn)[14]利用了節(jié)點(diǎn)的位置信息、速度和移動(dòng)方向，通過計(jì)算更容易接近目的節(jié)點(diǎn)的中間節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)，獲得較好的性能，但算法中采用最近一次和目的節(jié)點(diǎn)相遇的節(jié)點(diǎn)的信息來決定轉(zhuǎn)發(fā)方向，若相遇后經(jīng)過時(shí)間太長，其所采用的位置信息已經(jīng)失去參考價(jià)值，算法性能急劇下降。

針對以上算法的優(yōu)缺點(diǎn)，借鑒文獻(xiàn)[9]的思路，本文研究僅繼承了RAPID的流程，完全拋棄了其最核心的效能函數(shù)計(jì)算方法，重新設(shè)計(jì)了基于位置信息的效能函數(shù)模型，該模型的設(shè)計(jì)思路是盡可能把報(bào)文復(fù)制給向目的節(jié)點(diǎn)方向移動(dòng)的中間節(jié)點(diǎn)，隨著向目的節(jié)點(diǎn)方向的移動(dòng)，目的節(jié)點(diǎn)的信息越來越精確，報(bào)文就更容易被遞交。

1 基于位置的RAPID路由(PRR)

當(dāng)節(jié)點(diǎn)X和Y相遇時(shí)，協(xié)議流程如圖1所示。

圖1 PRR協(xié)議流程圖

圖中，iP為第i個(gè)報(bào)文；,iiXY UU分別為節(jié)點(diǎn)X和Y對應(yīng)的效能函數(shù)值；iS為報(bào)文i的大??；Dest(iP)為獲取報(bào)文iP的目的地址。

2 算法關(guān)鍵技術(shù)

2.1 效能函數(shù)

對于圖1中任意節(jié)點(diǎn)V，其報(bào)文i的效能函數(shù)定義為：

式中，xV,yV是節(jié)點(diǎn)V的橫縱坐標(biāo)；xD,yD是報(bào)文i的目的節(jié)點(diǎn)D的橫縱坐標(biāo)；R是目的節(jié)點(diǎn)D的傳輸半徑。

在式(1)中，當(dāng)節(jié)點(diǎn)V在目的節(jié)點(diǎn)D的傳輸范圍內(nèi)時(shí)，可以直接傳輸?shù)侥康墓?jié)點(diǎn)，設(shè)置其效能函數(shù)為負(fù)無窮大，這樣就能保證δUi足夠大，從而使該目的的報(bào)文優(yōu)先被復(fù)制。當(dāng)節(jié)點(diǎn)V不在節(jié)點(diǎn)D的傳輸范圍時(shí)，設(shè)置效能函數(shù)為節(jié)點(diǎn)V預(yù)期達(dá)到目的節(jié)點(diǎn)D傳輸范圍內(nèi)的時(shí)間，該時(shí)間t計(jì)算方法如圖2所示，圖中V1、D1分別節(jié)點(diǎn)V和目的節(jié)點(diǎn)D的移動(dòng)方向矢量。

圖2 效能函數(shù)計(jì)算示意

節(jié)點(diǎn)V到點(diǎn)(,)x y的時(shí)間t由以下方程組求出：

式中，αV,βV是矢量V1的方向角；αD,βD是矢量D1的方向角；vD,vV是節(jié)點(diǎn)D和節(jié)點(diǎn)V的移動(dòng)速度。

由式(2)可獲得關(guān)于t的二元一次方程，若方程有解，則選取最小的一個(gè)值作為t值；若方程無解，選取+∞作為t值。在應(yīng)用中，根據(jù)應(yīng)用場景設(shè)置一個(gè)足夠大的數(shù)U_MAX作為+∞，則?U_MAX 作為?∞，當(dāng)節(jié)點(diǎn)X和Y相遇時(shí)，在同等大小報(bào)文條件下，會(huì)產(chǎn)生以下報(bào)文復(fù)制優(yōu)先級情況，如表1所示。

需要說明的是，UYi為?U_MAX 時(shí)，節(jié)點(diǎn)Y位于到目的節(jié)點(diǎn)的最后一跳，不管UXi的值如何，此時(shí)的優(yōu)先級都是最高。此外，UXi的值不可能為?U_MAX，(若為該值，表示節(jié)點(diǎn)X在目的節(jié)點(diǎn)D的傳輸范圍之內(nèi)，按照協(xié)議設(shè)計(jì)，報(bào)文已直接被遞交，不需要復(fù)制)。

表1 報(bào)文復(fù)制優(yōu)先級分布

2.2 元數(shù)據(jù)交換

為了實(shí)現(xiàn)上述效能函數(shù)的計(jì)算，節(jié)點(diǎn)之間在相遇時(shí)需要交換足夠的信息，節(jié)點(diǎn)在運(yùn)動(dòng)中通過不斷收集這些元數(shù)據(jù)，完成效能函數(shù)的計(jì)算，節(jié)點(diǎn)X需要從節(jié)點(diǎn)Y獲得的元數(shù)據(jù)(反之亦然)包括：1) 節(jié)點(diǎn)Y的平均速度，由節(jié)點(diǎn)在運(yùn)動(dòng)過程中周期性測定；2) 節(jié)點(diǎn)Y的當(dāng)前位置坐標(biāo)，由節(jié)點(diǎn)內(nèi)的內(nèi)置GPS模塊提供；3) 節(jié)點(diǎn)Y緩存的報(bào)文的編號；4) 節(jié)點(diǎn)Y的鄰居節(jié)點(diǎn)位置列表，該列表包括節(jié)點(diǎn)Y經(jīng)歷過的所有鄰居的最近N個(gè)采樣周期內(nèi)的位置信息，若采樣數(shù)量不足N，則Y中存儲(chǔ)實(shí)際次數(shù)；若采樣數(shù)量大于N，則Y中存儲(chǔ)最近的N次。對于每個(gè)鄰居的位置信息，其數(shù)據(jù)結(jié)構(gòu)如圖3所示。

圖3 節(jié)點(diǎn)位置數(shù)據(jù)結(jié)構(gòu)

2.3 目的節(jié)點(diǎn)運(yùn)動(dòng)方向計(jì)算

在圖2對效能函數(shù)的計(jì)算中，需要知道節(jié)點(diǎn)的移動(dòng)矢量，即要獲得節(jié)點(diǎn)的Vα和Vβ。對于相遇的兩個(gè)節(jié)點(diǎn)X和Y，由于有實(shí)時(shí)的運(yùn)動(dòng)數(shù)據(jù)，可以通過最近的兩次位置采樣數(shù)據(jù)計(jì)算出來。然而對于某個(gè)報(bào)文的目的節(jié)點(diǎn)D的運(yùn)動(dòng)方向Dα和Dβ，如果有其最近的兩次采樣時(shí)間的位置信息，則可以直接計(jì)算，否則需要預(yù)測其最近兩次采樣時(shí)間的位置信息來完成計(jì)算。

每個(gè)節(jié)點(diǎn)在加電啟動(dòng)后，都會(huì)每隔T時(shí)間對本節(jié)點(diǎn)的位置信息采樣一次，每個(gè)節(jié)點(diǎn)在緩存中保存最近的N次采樣，如果節(jié)點(diǎn)X中保存的節(jié)點(diǎn)D的最新位置信息的時(shí)間戳是TD，當(dāng)前時(shí)間為TC，則需要預(yù)測節(jié)點(diǎn)D的(TC?TD)/T個(gè)位置信息，并利用最新的兩個(gè)信息來確定節(jié)點(diǎn)D的移動(dòng)矢量。

本研究中采用灰色預(yù)測方法來預(yù)測目的節(jié)點(diǎn)的位置信息?；疑A(yù)測法是一種對含有不確定因素的系統(tǒng)進(jìn)行預(yù)測的方法，對在一定范圍內(nèi)變化的、與實(shí)踐有關(guān)的灰色過程進(jìn)行預(yù)測，具有寬廣的應(yīng)用領(lǐng)域[15]。采用該方法主要是因?yàn)槭腔疑A(yù)測方法簡單易行，適用于在一定范圍內(nèi)波動(dòng)的數(shù)據(jù)預(yù)測，對數(shù)據(jù)分布沒有具體的要求。

為了評估本研究中用到的仿真模型對灰色預(yù)測的適用情況，對研究中采用的random waypoint移動(dòng)模型產(chǎn)生的數(shù)據(jù)進(jìn)行了灰色預(yù)測分析，來觀察灰色預(yù)測對random waypoint移動(dòng)模型坐標(biāo)的預(yù)測情況。在NS仿真工具下，放置一個(gè)節(jié)點(diǎn)按照random waypoint模型進(jìn)行運(yùn)動(dòng)，在500 m×500 m區(qū)域內(nèi)，節(jié)點(diǎn)運(yùn)動(dòng)速度10 m/s，暫停時(shí)間1 s，每隔40 s記錄一次節(jié)點(diǎn)的X軸坐標(biāo)，如表2所示。

表2 random waypoint坐標(biāo)數(shù)據(jù)

根據(jù)上述數(shù)據(jù)，采用GM(1,1)模型，獲得預(yù)測方程：

方差比C=0.574＜0.65，殘差概率P=1。

由結(jié)果可知，模型精度基本合格，所以采用灰色預(yù)測模型對節(jié)點(diǎn)的運(yùn)動(dòng)方向進(jìn)行預(yù)測是可行的。

3 仿真和性能分析

本文采用NS網(wǎng)絡(luò)仿真工具對本文提出的PRR算法和RAPID算法的性能進(jìn)行比較，仿真主要用到的參數(shù)如表3所示，其他沒有列出的參數(shù)同文獻(xiàn)[9]。

表3 仿真參數(shù)表

圖4～圖6是在20個(gè)節(jié)點(diǎn)情況下的仿真結(jié)果，節(jié)點(diǎn)移動(dòng)速度為10 m/s，橫軸為每50 s源和目的節(jié)點(diǎn)產(chǎn)生的報(bào)文數(shù)。每個(gè)成功到達(dá)報(bào)文的平均延遲的比較結(jié)果如圖4所示，可看出隨著報(bào)文產(chǎn)生數(shù)量的增加，在節(jié)點(diǎn)密度不變的情況下，緩存中等待的報(bào)文數(shù)增加，延遲增加。RAPID算法由于無法較為準(zhǔn)確的估計(jì)節(jié)點(diǎn)間的相遇時(shí)間，而本文的算法直接向節(jié)點(diǎn)的移動(dòng)方向發(fā)送報(bào)文而獲得更少的延遲。兩種算法成功遞交率的比較效果如圖5所示，可看出本文的算法由于在大概方位上的確切計(jì)算，使得報(bào)文在被丟棄前更容易在某個(gè)方向上到達(dá)目標(biāo)節(jié)點(diǎn)，但隨著報(bào)文數(shù)的增加，成功遞交率下降。

圖4 平均延遲的比較(產(chǎn)生報(bào)文數(shù)變化的情況)

圖5 成功遞交率的比較(產(chǎn)生報(bào)文數(shù)變化的情況)

圖6 顯示了本文的算法在保證性能的情況下具有更小的消息復(fù)制數(shù)，這主要基于兩個(gè)原因：1) 本文算法消息的傳播具有方向性，在一定時(shí)間內(nèi)沿某一方向復(fù)制；2) 制定了更詳盡的消息復(fù)制規(guī)則，對報(bào)文復(fù)制有了更詳細(xì)的限定，可以有效減少消息的復(fù)制數(shù)量。

圖7和圖8是在移動(dòng)速度為10 m/s，每個(gè)源和目的節(jié)點(diǎn)對每秒產(chǎn)生1個(gè)CBR流的情況下的仿真結(jié)果，橫軸是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。和圖4、圖5相比，在網(wǎng)絡(luò)產(chǎn)生報(bào)文數(shù)不變的情況下，隨著節(jié)點(diǎn)的增多，每個(gè)節(jié)點(diǎn)獲得更多的到目的節(jié)點(diǎn)的信息，效能函數(shù)的計(jì)算值更精確，到目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)路徑更多，這些均導(dǎo)致到達(dá)目的節(jié)點(diǎn)的延遲更少，報(bào)文被成功遞交的概率更高，如圖7和圖8所示。

圖6 消息復(fù)制個(gè)數(shù)的比較(產(chǎn)生報(bào)文數(shù)變化的情況)

圖7 平均延遲的比較(節(jié)點(diǎn)數(shù)變化的情況)

圖8 遞交率的比較(節(jié)點(diǎn)數(shù)變化的情況)

圖9 復(fù)制消息數(shù)的比較(節(jié)點(diǎn)數(shù)變化的情況)

圖9描述了當(dāng)前仿真條件下消息復(fù)制數(shù)量的變化情況，由于節(jié)點(diǎn)數(shù)增加，參加消息復(fù)制的節(jié)點(diǎn)數(shù)增加，消息被復(fù)制的數(shù)量增大。但當(dāng)節(jié)點(diǎn)密度增加到一定程度后，由于有更精確的到達(dá)目的節(jié)點(diǎn)的路徑信息，此時(shí)有些節(jié)點(diǎn)就不需要做無用的復(fù)制，所以盡管節(jié)點(diǎn)數(shù)增加，但消息的復(fù)制數(shù)量反而有所下降。

4 結(jié) 論

本文在RAPID的算法的基礎(chǔ)上，借鑒了原算法的效能函數(shù)的概念克服DTN路由算法的偶然性問題，通過引入位置信息預(yù)測和設(shè)計(jì)新的效能函數(shù)計(jì)算方法改進(jìn)RAPID算法中的效能函數(shù)的不確定性。仿真表明，本文提出的算法在提高網(wǎng)絡(luò)性能的同時(shí)，減少了消息復(fù)制的數(shù)據(jù)量，獲得較滿意的效果。

[1] KHABBAZ M, ASSI C M, FAWAZ W F. Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges[J]. IEEE Communications Surveys & Tutorials, 2012, 14(2): 607-640.

[2] GREEN J, SCHULTZ J. Collaborative applications at the tactical edge through resilent group dissemination in DTN [C]//The IEEE Military Communications Conference. New York: IEEE, 2012.

[3] AGARWAL A, STAROBINSKI D, LITTLE T D C. Phase transition of message propagation speed in delay-tolerant vehicular networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 249-263.

[4] EHASAN S, BRADFORD K, BRUGGER M, et al. Design and analysis of delay-tolerant sensor networks for monitoring and tracking free-roaming animals[J]. IEEE Transactions on Wireless Communications, 2012, 11(3): 1220-1227.

[5] XIAO M, WU J, LIU C, et al. Tour: Time-sensitive opportunistic utility-based routing in delay tolerant networks[C]//INFOCOM 2013. New York: IEEE, 2013.

[6] SOK P, KIM K. Distance-based PRoPHET routing protocol in disruption tolerant network[C]//The 2013 International Conference on ICT Convergence (ICTC). New York: IEEE, 2013.

[7] KHABBAZ M J, FAWAZ W F, ASSI C M. A probabilistic and traffic-aware bundle release scheme for vehicular intermittently connected networks[J]. IEEE Transactions on Communications, 2012, 60(11): 3396-3406.

[8] TOURNOUX P, LEGUAY J, BENBADIS F, et al. Density-aware routing in highly dynamic DTNs: The RollerNet case[J]. IEEE Transactions on Mobile Computing, 2012, 10(12): 1755-1768.

[9] BALASUBRAMANIAN A, LEVINE B N, VENKATARAMANI A. DTN routing as a resource allocation problem[C]//SIGCOMM’07. New York: IEEE, 2007.

[10] SHEN J, MOH S, CHUNG I. A priority routing protocol based on location and moving direction in delay tolerant networks[J]. IEICE Transaction on Information and Systems, 2010(10): 2763-2775.

[11] 黨斐, 陽小龍, 隆克平. 噴射轉(zhuǎn)發(fā)算法: 一種基于Markov位置預(yù)測模型的DTN路由算法[J]. 中國科學(xué): 信息科學(xué), 2010, 40(10): 1312-1320. DANG Fei, YANG Xiao-long, LONG Ke-ping. Spray and forward: a DTN routing algorithm based on Markov position prediction[J]. Scientia Sinica Informationis, 2010, 40(10): 1312-1320.

[12] 郭航，王興偉，黃敏, 等. DTN中基于位置信息的噴射路由算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(11): 2481-2484. GUO Hang, WANG Xing-wei, HUANG Min, et al. Spay routing algorithm based on location information in DTN[J]. Journal of Chinese Computer Systems, 2012, 33(11): 2481-2484.

[13] PARK H S, JANG J H, KIM J D. Position-based DTN routing in metropolitan bus network[C]//The 2012 International Conference on Systems and Informatics (ICSAI). New York: IEEE, 2012.

[14] DE ANDRADE G E, DE PAULA LIMA L A, CALSAVARA A. Routing protocol based on the position, velocity, and direction of nodes[C]//The 2013 27th International Conference on Advanced Information Networking and Applications Workshops (WAINA). New York: IEEE, 2013.

[15] 王大鵬.灰色預(yù)測模型及中長期電力負(fù)荷預(yù)測應(yīng)用研究[D]. 武漢: 華中科技大學(xué), 2013. WANG Da-peng. Research on grey prediction models and their applications in medium and long term power load forecasting[D]. Wuhan: Huazhong University of Science and Technology, 2013.

編 輯 葉 芳

Position-Based RAPID Routing Algorithm for Delay Tolerant Networks

LIU Yong-guang

(Guangdong Industry Technical College Guangzhou 510300; China Electronics Technology Group Corporation NO.7 Research Institute Guangzhou 510310)

The resource allocation protocol for intentional delay (RAPID) routing algorithm applied for delay tolerant networks (DTN) adopts the utility function to avoid accidental effect on some metrics occurred in other DTN routing algorithms did. However, the problem of inter-meeting time distribution between nodes brings the algorithm’s uncertainty and the limitation for applications. For this problem, a new method for computing utility function is designed based on position information. In the new method, every node acquires other node’s position information by metadata exchange. The position information of a long-time-lost destination node is predicted by the gray system prediction algorithm. By minimizing messages arriving time to destination, the more detailed priority and rules of message duplication are designed. Simulations show that the new algorithm can overcome the problem in the RAPID algorithm effectively, decrease the number of message duplicate and average delay, increase message successive delivery ratio and improve the performance of the entire network further.

delay tolerant networks; position; RAPID; routing; utility

TP393.4

A

10.3969/j.issn.1001-0548.2015.06.008

2014 ? 06 ? 13；

2014 ? 12 ? 02

國家自然科學(xué)基金(61001113)；國防預(yù)研項(xiàng)目(Y226)

劉永廣(1972 ? )，男，博士，主要從事信息網(wǎng)絡(luò)理論與技術(shù)、路由算法及優(yōu)化等方面的研究.