劉永廣

DTN基于位置的RAPID路由算法

劉永廣

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

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

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

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

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

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

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

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

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

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

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

2.1 效能函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

2.3 目的節(jié)點運動方向計算

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

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

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

為了評估本研究中用到的仿真模型對灰色預(yù)測的適用情況，對研究中采用的random waypoint移動模型產(chǎn)生的數(shù)據(jù)進(jìn)行了灰色預(yù)測分析，來觀察灰色預(yù)測對random waypoint移動模型坐標(biāo)的預(yù)測情況。在NS仿真工具下，放置一個節(jié)點按照random waypoint模型進(jìn)行運動，在500 m×500 m區(qū)域內(nèi)，節(jié)點運動速度10 m/s，暫停時間1 s，每隔40 s記錄一次節(jié)點的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é)點的運動方向進(jìn)行預(yù)測是可行的。

3 仿真和性能分析

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

表3 仿真參數(shù)表

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

本文在RAPID的算法的基礎(chǔ)上，借鑒了原算法的效能函數(shù)的概念克服DTN路由算法的偶然性問題，通過引入位置信息預(yù)測和設(shè)計新的效能函數(shù)計算方法改進(jìn)RAPID算法中的效能函數(shù)的不確定性。仿真表明，本文提出的算法在提高網(wǎng)絡(luò)性能的同時，減少了消息復(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]. 小型微型計算機系統(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ù)研項目(Y226)

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