丁安平　馬蓓蕾　王炳庭

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

?

DTN中基于節(jié)點相遇規(guī)律的自適應散發(fā)等待路由

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

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

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

關鍵詞容滯網(wǎng)絡路由二維矩陣H相遇規(guī)律散發(fā)等待

0引言

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

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

1相關工作

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

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

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

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

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

目前，針對散發(fā)等待路由如何選擇中繼節(jié)點以及散發(fā)的副本數(shù)，國內(nèi)外研究者做了大量的研究，并取得了較好的結(jié)果?？墒侨绻麅蓚€相遇的節(jié)點，其與信宿節(jié)點相遇的概率均較低，就很難提高報文的遞交率。這時我們將每個節(jié)點維護的路由信息從傳統(tǒng)的一維拓展到二維，建立一個二維矩陣H，并在此基礎上研究節(jié)點的相遇規(guī)律。

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

2一種自適應散發(fā)等待路由

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

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

2.1矩陣H的建立和更新

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

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

2.2中繼能力的計算

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

(1)

(2)

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

(3)

2.3路由過程

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

隨著節(jié)點在網(wǎng)絡中不斷散發(fā)報文，報文的拷貝數(shù)將不斷減小。當報文的拷貝數(shù)為1時，節(jié)點將轉(zhuǎn)換為直接傳輸模式。

3仿真

3.1仿真參數(shù)設置

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

表1　仿真參數(shù)設置

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

3.2結(jié)果與分析

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

圖1　遞交率隨時間的變化

從圖2可以看出，BSW和ASW-H的平均延遲明顯低于Epidemic和Prophet，而ASW-H的平均延遲略低于BSW。這是由于ASW-H根據(jù)節(jié)點的相遇規(guī)律，動態(tài)地調(diào)整報文轉(zhuǎn)發(fā)的方向及副本數(shù)，使得報文快速到達目的節(jié)點。

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

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

圖3　開銷率隨時間的變化

4結(jié)語

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

在算法復雜度方面，本文的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] 劉唐,彭艦,楊進.異構(gòu)延遲容忍移動傳感器網(wǎng)絡中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[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的地震緊急救援通信系統(tǒng)研究[J].計算機應用與軟件,2014,31(1):111-116.

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

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

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

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

[11] 任偉,董育寧,趙海濤.一種改進的基于地理位置的無線Mesh網(wǎng)絡路由協(xié)議[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。丁安平，碩士生，主研領域：容滯網(wǎng)絡路由算法。馬蓓蕾，碩士生。王炳庭，講師。

中圖分類號TP3

文獻標識碼A

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