DTN中基于節點相遇規律的自適應散發等待路由

丁安平　馬蓓蕾　王炳庭

1(安徽大學計算智能與信號處理教育部重點實驗室　安徽 合肥 230000)2(滁州學院電子電氣工程學院　安徽 滁州 239000)

?

DTN中基于節點相遇規律的自適應散發等待路由

丁安平1馬蓓蕾1王炳庭2

1(安徽大學計算智能與信號處理教育部重點實驗室安徽 合肥 230000)2(滁州學院電子電氣工程學院安徽 滁州 239000)

摘要在容滯網絡中，針對散發等待BSW(Binary Spray and Wait)路由協議在轉發報文時具有一定的盲目性。提出將每個節點維護的路由信息由一維拓展到二維，并在該基礎上研究節點的相遇規律，動態地調整報文轉發策略，從而解決當前節點與信宿節點相遇概率較低的問題。實驗結果表明，該算法與散發等待路由相比，在降低平均延遲的基礎上，能有效改善報文的遞交率。

關鍵詞容滯網絡路由二維矩陣H相遇規律散發等待

0引言

DTN[1]是一種面向報文的、可靠的、通用的覆蓋網絡[2]。它由若干區域網絡組成，能夠實現受限網絡之間的通信。與存儲-轉發的交換方式不同，DTN中報文的交換采用存儲-攜帶-轉發[3]的方式進行。中繼節點可以攜帶報文移動，在合適的時刻選擇合理的方式轉發報文，最終將報文遞交到信宿節點。在傳統的無線網絡傳輸中，通信的實現要求信源節點和信宿節點之間至少建立一條穩定的連接。而在DTN中，節點無規則地移動，網絡拓撲結構動態變化，節點呈現稀疏性分布，彼此之間無法建立穩定的端到端連接，這給DTN路由協議的設計帶來了巨大的挑戰。

在DTN中，由于節點具有差異性[4,5]，某些節點會頻繁相遇，而有些節點較長時間內都不會相遇。因此某些報文能夠快速傳輸到目的節點，而有的還需要通過很多跳的中繼轉發才能到達目的節點。每個報文均有一個生命周期，中繼轉發的次數越多，延遲越大，報文因超出生命周期被丟棄的可能性越大。在這期間開銷必然也消耗更多，這時合理選擇一個中繼節點[6]顯得尤為重要。尤其是在自然災害時期，時間就是生命[7]，延遲越大，付出的代價就越大。針對節點的這種特性，本文提出節點的中繼能力的概念，建立了一個二維矩陣H來研究節點間的相遇規律，并在此基礎上提出了ASW-H路由算法。該路由算法根據節點中繼能力的大小來轉發報文拷貝數及選擇下一跳節點。這種自適應性的散發和轉發策略更能夠適應網絡的動態拓撲結構，從而能夠顯著提高報文的遞交率，降低延遲。

1相關工作

由于DTN中節點通過機會連接最終將報文遞交到信宿節點，因此報文被遞交到信宿節點的概率較低、延遲較大。為了改善DTN的網絡性能，DTN常采用多拷貝機制來增加報文到達信宿節點的概率，減小遞交延遲。DTN多拷貝路由中最具代表性的路由協議有：蔓延路由(Epidemic)[8]、概率路由(Prophet)[9]及散發等待路由(Spray and Wait)[10]。

蔓延路由采用洪泛機制，源節點對報文的下一跳節點不做任何限制，而直接將報文轉發復制給相遇的節點，提高了遞交率，降低了延遲，其代價是網絡中存在大量的冗余拷貝，易導致網絡擁塞[11]。

在概率路由協議中，每個節點根據歷史相遇信息維護一張到網絡中其他任何節點的概率表，再根據概率的大小關系來轉發報文。該協議能明顯減小開銷, 但報文的遞交率隨之降低、延遲增大。

為了更有效地控制開銷，有人提出了采用配額的方式對報文拷貝數進行控制的散發等待路由算法。它包括源端散發等待和二分法散發等待。

在源端散發等待路由中，源節點將產生的每個報文的拷貝數初始化為L，每次轉發后該報文的拷貝數將減少1。當拷貝數減至1時，源節點將轉換為直接傳輸模式。即所有攜帶該報文拷貝的節點只有遇到報文的目的節點時才將報文轉發出去。而在二分散發等待路由算法中，節點A只要與節點B相遇就會轉發n/2個副本。這種算法在保證遞交率的同時，有效地降低了開銷，但是在中繼節點的選擇上具有一定的盲目性。

目前，針對散發等待路由如何選擇中繼節點以及散發的副本數，國內外研究者做了大量的研究，并取得了較好的結果。可是如果兩個相遇的節點，其與信宿節點相遇的概率均較低，就很難提高報文的遞交率。這時我們將每個節點維護的路由信息從傳統的一維拓展到二維，建立一個二維矩陣H，并在此基礎上研究節點的相遇規律。

在現實世界中，網絡內節點的相遇均有一定的規律性[11]。有些節點會頻繁相遇，而有些節點可能很長一段時間內都不會相遇，這時合理選擇一個中繼節點顯得尤為重要。本文提出了一種基于節點相遇規律的自適應散發等待路由算法(ASW-H)。該算法充分利用節點的相遇規律來動態地調整報文轉發的方向及副本數，更能夠適應網絡的動態拓撲結構，從而解決當前節點與信宿節點相遇概率較低的難題。在降低平均延遲的基礎上，有效改善報文的遞交率。

2一種自適應散發等待路由

在DTN中，節點的相遇均呈現一定的規律性。一個節點在最近一段時間內可能會遇到若干個節點，而這若干個節點又會分別與其他節點相遇，因此可以利用一個二維矩陣來反映節點間的這種相遇規律。該二維矩陣比傳統協議中的一維路由表更能反映節點間的相遇規律。當節點運動時，實時更新該矩陣以反映最新的相遇信息。通過該二維矩陣分析兩兩節點之間直接相遇與間接相遇的可能性，以期解決當前節點與信宿節點相遇概率較低時的路由選擇難題。

定義節點中繼能力的大小為Pr，它由兩個參數來衡量，一個是直接相遇能力值，即本節點直接與目的節點相遇的能力值Prd；另一個是間接相遇能力值，即此節點與目的節點通過一跳中轉間接相遇的能力值Pri。本文利用每個節點維護的一個二維矩陣H來反映節點間的相遇規律，計算節點中繼能力值，選擇最優中繼節點及具體的散發份數。

2.1矩陣H的建立和更新

節點A建立一個m+1行m列的矩陣HA，如下所示。第一行表示最近與A相遇的m個節點的ID號，刪去矩陣HA第一行后的每一列分別用來記錄與第一行每個節點最近相遇的其他m個節點的ID號。如A11最近遇到的m個節點為A21，A31,…,Am+1m。

為了維持最新的節點分布狀態，每個節點需要實時地更新矩陣。例如節點A更新過程如下：首先，假設節點A1j是最早與節點A相遇的節點，節點A將從矩陣HA中刪除節點A1j(1≤j≤m)所在的那一列。其次，假設節點B在最近分別遇到節點B11，B12,…,.B1m，節點A獲得節點B的這些信息，并將B的這些信息添加到矩陣HA中，更新后的矩陣如下所示。

2.2中繼能力的計算

假設目的節點D在矩陣HA的第一行中出現的次數為n，而出現在刪去矩陣HA第一行后的矩陣的每一列的次數為ni。節點A的Prd和Pri分別計算如下：

(1)

(2)

結合式(1)、式(2)，可以得到節點中繼能力的計算公式，如式(3)所示，其中參數a用來平衡Prd與Pri在Pr中所占的比例。

(3)

2.3路由過程

當兩個節點相遇時，節點首先更新各自維護的矩陣和節點中繼能力的大小，然后彼此交換各自的節點中繼能力值，最后根據中繼能力大小的比值關系來動態地散發報文拷貝數。

隨著節點在網絡中不斷散發報文，報文的拷貝數將不斷減小。當報文的拷貝數為1時，節點將轉換為直接傳輸模式。

3仿真

3.1仿真參數設置

本文使用開源仿真工具ONE進行仿真。仿真場景為芬蘭首都赫爾辛基地圖，大小為4500 m×3400 m，共放置了126個節點，這些節點被分成了6個組。報文產生間隔為10到20秒，報文的大小為50 k到100 k之間。具體參數如表1所示。

表1　仿真參數設置

在上述仿真環境下，比較Epidemic、BSW、Prophet及本文所提出的ASW-H路由算法在報文遞交率、網絡開銷率及平均延遲上隨時間的變化情況。

3.2結果與分析

從圖1可以明顯地看出ASW-H路由算法在整個仿真期間的遞交率一直高于其他三種路由算法。這是因為ASW-H算法將傳統的一維路由表拓展成二維的矩陣，不僅考慮了兩個節點直接相遇的可能性，還分析了兩個節點間是否存在更好的中間節點。這種協議算法更能夠適應現實網絡狀況的變化，從而避免了BSW散發報文的盲目性。

圖1　遞交率隨時間的變化

從圖2可以看出，BSW和ASW-H的平均延遲明顯低于Epidemic和Prophet，而ASW-H的平均延遲略低于BSW。這是由于ASW-H根據節點的相遇規律，動態地調整報文轉發的方向及副本數，使得報文快速到達目的節點。

圖2　平均延遲隨時間的變化

從圖3可以看出,在前9 ks的時間里，ASW-H的平均開銷率略高于Prophet，但到了9 ks以后，ASW-H的平均開銷率逐漸低于Prophet。這是因為ASW-H更能動態適應網絡的現狀來轉發報文拷貝數及選擇下一跳節點。ASW-H的平均開銷率高于二分散發等待路由算法，這是因為ASW-H通過了更多的中繼節點的轉發，犧牲開銷以換取遞交率的提升。

圖3　開銷率隨時間的變化

4結語

本文將每個節點維護的路由信息由一維拓展到二維，通過二維矩陣來反映節點之間的關系，動態地調整報文轉發的方向及副本數，從而解決了當前節點與信宿節點相遇概率較低的難題。仿真結果顯示，本文提出的ASW-H算法更能動態地適應現實的網絡狀況，從而提高了遞交率，降低了延遲。

在算法復雜度方面，本文的ASW-H算法跟其他路由相比要復雜一些。未來的工作主要考慮在降低復雜度的同時能夠更進一步提高報文遞交率，降低延遲和開銷。

參考文獻

[1] Hisamatsu Tsuyoshi,Asaeda Hitoshi.Adaptive Overlay Network for High-Bandwidth Streaming[J].Journal of Information Processing,2012,20(1):154-166.

[2] Ryohei Dou,Akihiro Fujihara,Hiroyoshi Miwa.Algorithms for the Base Node Location Problem in the Virtual Segment Method in Store-carry-forward Routing Schemes[C]//Intelligent Networking and Collaborative Systems,Thessaloniki,2010:374-379.

[3] Yahui Wu,Su Deng,Hongbin Huang.Information spreading in Delay Tolerant Networks based on nodes’ behaviors[C]//Communications in Nonlinear Science and Numerical Simulation,2014:2406-2413.

[4] 劉唐,彭艦,楊進.異構延遲容忍移動傳感器網絡中基于轉發概率的數據傳輸[J].軟件學報,2013,24(2):215-229.

[5] Rong Geng,Meisi Tang,Xianghong Jiang.Spray and Wait Routing Based on Relay-Probability in DTN[J].Journal of Northeastern University,2012,33(12):1698-1701.

[6] 段卓君,王小明,李成博.基于DTN的地震緊急救援通信系統研究[J].計算機應用與軟件,2014,31(1):111-116.

[7] 竇飛,高永智.DTN中蔓延路由協議擁塞控制方案研究[J].現代電子技術,2010,327(16):169-171.

[8] 朱桂明,郭得科,金士堯.基于副本復制Bloom Filter的P2P概率路由算法[J].軟件學報,2011,22(4):773-781.

[9] 張迪,王貴竹.DTN中概率選擇的散發等待路由[J].通信技術,2010,43(5):145-147.

[10] 王朕,王新華.ISM:新一代綠色機會網絡設備的緩存管理策略[J].計算機應用與軟件,2011,28(11):193-198.

[11] 任偉,董育寧,趙海濤.一種改進的基于地理位置的無線Mesh網絡路由協議[J].南京郵電大學學報,2012,32(1):75-83.

AN ADAPTIVE BINARY SPRAY AND WAIT ROUTING ALGORITHM BASED ON NODE ENCOUNTER LAW IN DTN

Ding Anping1Ma Beilei1Wang Bingting2

1(MinistryofEducationKeyLabofIC&SP,AnhuiUniversity,Hefei230000,Anhui,China)2(SchoolofElectronicandElectricalEngineering,ChuzhouUniversity,Chuzhou239000,Anhui,China)

AbstractIn delay-tolerant networking (DTN), Binary Spray and Wait (BSW) routing protocol has a certain blindness when forwarding messages. To deal with this issue, we propose to expand the routing information maintained by each node from one dimension to two dimensions, and study on this basis the encounter law of nodes as well as adjust dynamically the messages forwarding strategy, thereby solve the problem of low encounter possibility of current nodes and the destination nodes. Experimental results show that the proposed algorithm can effectively enhance message delivery rate on the basis of reducing the average latency compared with BSW routing.

KeywordsDelay-tolerant networkingRoutingTwo-dimensional matrix HEncounter lawBSW

收稿日期：2014-09-13。丁安平，碩士生，主研領域：容滯網絡路由算法。馬蓓蕾，碩士生。王炳庭，講師。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.031