DTN基于位置的RAPID路由算法

劉永廣

DTN基于位置的RAPID路由算法

劉永廣

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

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

容遲網絡; 位置; RAPID; 路由; 效能

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

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

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

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

當節點X和Y相遇時，協議流程如圖1所示。

圖1 PRR協議流程圖

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

2 算法關鍵技術

2.1 效能函數

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

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

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

圖2 效能函數計算示意

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

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

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

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

表1 報文復制優先級分布

2.2 元數據交換

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

圖3 節點位置數據結構

2.3 目的節點運動方向計算

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

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

本研究中采用灰色預測方法來預測目的節點的位置信息。灰色預測法是一種對含有不確定因素的系統進行預測的方法，對在一定范圍內變化的、與實踐有關的灰色過程進行預測，具有寬廣的應用領域[15]。采用該方法主要是因為是灰色預測方法簡單易行，適用于在一定范圍內波動的數據預測，對數據分布沒有具體的要求。

為了評估本研究中用到的仿真模型對灰色預測的適用情況，對研究中采用的random waypoint移動模型產生的數據進行了灰色預測分析，來觀察灰色預測對random waypoint移動模型坐標的預測情況。在NS仿真工具下，放置一個節點按照random waypoint模型進行運動，在500 m×500 m區域內，節點運動速度10 m/s，暫停時間1 s，每隔40 s記錄一次節點的X軸坐標，如表2所示。

表2 random waypoint坐標數據

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

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

由結果可知，模型精度基本合格，所以采用灰色預測模型對節點的運動方向進行預測是可行的。

3 仿真和性能分析

本文采用NS網絡仿真工具對本文提出的PRR算法和RAPID算法的性能進行比較，仿真主要用到的參數如表3所示，其他沒有列出的參數同文獻[9]。

表3 仿真參數表

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

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

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

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

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

圖6 消息復制個數的比較(產生報文數變化的情況)

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

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

圖9 復制消息數的比較(節點數變化的情況)

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

4 結 論

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

[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] 黨斐, 陽小龍, 隆克平. 噴射轉發算法: 一種基于Markov位置預測模型的DTN路由算法[J]. 中國科學: 信息科學, 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]. 小型微型計算機系統, 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] 王大鵬.灰色預測模型及中長期電力負荷預測應用研究[D]. 武漢: 華中科技大學, 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

國家自然科學基金(61001113)；國防預研項目(Y226)

劉永廣(1972 ? )，男，博士，主要從事信息網絡理論與技術、路由算法及優化等方面的研究.