基于緩沖區(qū)占用率的DTN散發(fā)等待路由算法

馬蓓蕾，王貴竹，朱妍娟，丁安平

（安徽大學計算智能與信號處理教育部重點實驗室，合肥230039）

基于緩沖區(qū)占用率的DTN散發(fā)等待路由算法

馬蓓蕾，王貴竹，朱妍娟，丁安平

（安徽大學計算智能與信號處理教育部重點實驗室，合肥230039）

傳統(tǒng)容滯網(wǎng)絡(luò)散發(fā)等待路由算法的節(jié)點副本數(shù)是確定的，使得獲得節(jié)點的轉(zhuǎn)發(fā)次數(shù)具有一定的盲目性，不能很好地適應網(wǎng)絡(luò)環(huán)境，降低了遞交率。針對該問題，研究節(jié)點的最終平均緩沖區(qū)占用率和副本數(shù)的關(guān)系，提出一種基于緩沖區(qū)占用率的路由算法。該算法由節(jié)點的最終平均緩沖區(qū)占用率動態(tài)調(diào)整初始化副本數(shù)。在節(jié)點的最終平均緩沖區(qū)占用率較低的情況下，增大報文的初始化副本數(shù)，以提高遞交率，在節(jié)點的最終平均緩沖區(qū)占用率較高的情況下，減小報文的初始化副本數(shù)，以避免擁塞的發(fā)生。仿真結(jié)果表明，與二分法散發(fā)等待路由算法相比，當網(wǎng)絡(luò)中節(jié)點的平均緩存占用率較低時，該算法能改善遞交率和降低網(wǎng)絡(luò)平均延時。當網(wǎng)絡(luò)中節(jié)點的平均緩存占用率較高時，在改進遞交率的同時，能降低整個網(wǎng)絡(luò)的開銷。

容滯網(wǎng)絡(luò)；路由；散發(fā)等待；緩沖區(qū)占用率；副本數(shù)

1 概述

容滯網(wǎng)絡(luò)（Delay Tolerant Network，DTN）［1-2］，是一種位于區(qū)域網(wǎng)絡(luò)（各種不同類型的網(wǎng)絡(luò)，包括因特網(wǎng)）之上的覆蓋網(wǎng)［3］，以克服受限網(wǎng)絡(luò)環(huán)境下頻繁的網(wǎng)絡(luò)斷開、高延遲和異構(gòu)性［4］等問題。由于容滯網(wǎng)絡(luò)中端到端的路徑可能是不存在的，傳統(tǒng)的路由算法將不再適合這種新型的網(wǎng)絡(luò)結(jié)構(gòu)。容滯網(wǎng)絡(luò)采用存儲-攜帶-轉(zhuǎn)發(fā)［5］的方式來進行報文的轉(zhuǎn)發(fā)。在這個網(wǎng)絡(luò)中節(jié)點是稀疏的，因此，節(jié)點在遞交報文之前需要將報文存儲一段時間，通過節(jié)點的移動將報文轉(zhuǎn)發(fā)給其他中繼節(jié)點［6］或信宿節(jié)點。

本文根據(jù)節(jié)點移動模式和活動性的差異，提出一種基于緩沖區(qū)占用率的自適應散發(fā)等待路由算

法，動態(tài)更新初始化副本數(shù)。

2 相關(guān)工作

DTN中節(jié)點是隨機移動的，節(jié)點間的連接是不可預知的，因此，DTN是一個機會網(wǎng)絡(luò)［7］。節(jié)點間將通過機會連接來實現(xiàn)報文的轉(zhuǎn)發(fā)。DTN采用多拷貝路由機制［8］來增加報文被遞交到信宿節(jié)點的概率及減小延遲。其中，DTN多拷貝路由中最具代表性的路由協(xié)議有：蔓延（Epidemic）路由［9］，概率路由［10］及散發(fā)等待（Spray and Wait，SAW）路由［11］。

二分散發(fā)等待（Binary Spray and Wait，BSW）路由協(xié)議中，節(jié)點每次轉(zhuǎn)發(fā)自身報文副本數(shù)的一半給相遇節(jié)點，只有遇到信宿節(jié)點時才會轉(zhuǎn)發(fā)此報文。

但二分散發(fā)等待路由協(xié)議報文的初始化副本數(shù)是一定的，具有盲目性。本文提出最終平均緩沖區(qū)占用率的概念，并提出基于緩沖區(qū)占用率的散發(fā)等待路由算法，與二分法散發(fā)等待路由算法相比更能夠適應網(wǎng)絡(luò)環(huán)境的變化。

3 散發(fā)等待路由算法

散發(fā)等待路由中的初始化副本數(shù)都是確定的，所以，節(jié)點在生成報文時有一定的盲目性。首先要通過當前節(jié)點與歷史相遇節(jié)點的緩沖區(qū)占用率來計算當前節(jié)點的最終平均緩沖區(qū)占用率。然后根據(jù)節(jié)點的最終平均緩沖區(qū)占用率調(diào)節(jié)報文的初始化副本數(shù)：當節(jié)點的最終平均緩沖區(qū)占用率比較低時，應該增加報文的初始化副本數(shù)，以提高整個網(wǎng)絡(luò)的遞交率，降低平均時延；而在節(jié)點的最終平均緩沖區(qū)占用率比較高時，應該減少此節(jié)點生成的報文的初始化副本數(shù)，提高網(wǎng)絡(luò)的遞交率，減少網(wǎng)絡(luò)開銷率。

基于緩沖區(qū)占用率的散發(fā)等待路由（Spray and Wait Routing Concerned on Buffer Occupancy，SAWBO）算法分為3步：

（1）每次相遇時，節(jié)點更新列表。

（2）計算當前節(jié)點的最終平均緩沖區(qū)占用率。

（3）根據(jù)節(jié)點的最終平均緩沖區(qū)利用率，計算節(jié)點的生成報文的初始化副本數(shù)散發(fā)報文。

3.1 節(jié)點記錄相遇節(jié)點的列表

每個節(jié)點都有一個記錄，每個記錄有很多列表，這個列表里面有3個屬性值：節(jié)點ID，節(jié)點的平均緩沖區(qū)利用率和相遇時間。

當每次節(jié)點相遇時，節(jié)點根據(jù)以下 3步更新記錄：

（1）在初始化時，每一節(jié)點的列表中為空。每次節(jié)點相遇，計算當前節(jié)點最終緩沖區(qū)占用率并更新到列表中。

（2）當兩節(jié)點 A，B相遇，則比較兩節(jié)點的節(jié)點列表：

1）A，B節(jié)點列表中，節(jié)點ID不同的，分別補充到A，B節(jié)點列表中。

2）A，B節(jié)點列表中，節(jié)點ID相同的，保留更新時間較近的節(jié)點信息。

（3）節(jié)點會丟棄超時的節(jié)點信息（例如2 h外），因此，每個節(jié)點就記錄著在一段時間內(nèi)相遇的所有節(jié)點的列表。

3.2 參數(shù)計算

在每次相遇時，首先把相遇節(jié)點的列表更新到當前節(jié)點的記錄中，丟棄相遇時間在2 h之外的節(jié)點列表。列表中的平均緩沖區(qū)占用率的計算如下：

（1）相遇時間在2 h～0.5 h之內(nèi)的列表個數(shù)為m，緩沖區(qū)占用率為 β′，那么計算2 h內(nèi)節(jié)點的平均緩沖區(qū)占用率Aνgm，如式（1）所示：

（2）相遇時間在0.5 h之內(nèi)的列表個數(shù) n，緩沖區(qū)占用率為β″，那么計算2 h內(nèi)節(jié)點的平均緩沖區(qū)占用率Aνgn，如式（2）所示：

（3）計算當前節(jié)點的最終平均緩沖區(qū)占用率Aνg，如式（3）所示：

其中，0.5＜α＜1，把0.5 h內(nèi)的記錄作為著重的參考指標來考慮。

每次相遇當前節(jié)點計算最終平均緩沖區(qū)占用率，把當前節(jié)點相遇時間和最終平均緩沖區(qū)占用率更新到相遇節(jié)點的記錄中，相遇節(jié)點也是如此更新記錄。

最終平均緩沖區(qū)占用率是更新當前節(jié)點的生成報文的初始化拷貝份數(shù)的重要指標。在最終平均緩沖區(qū)占用率低時，認為當前節(jié)點緩沖區(qū)空閑。

3.3 參數(shù)之間的關(guān)系

在緩沖區(qū)空閑時，應該迅速增加二分法散發(fā)等待路由的初始化副本數(shù)，使得緩沖區(qū)得到充分利用，則在節(jié)點的最終平均緩沖區(qū)占用率低時，快速增大初始化副本數(shù)。在緩沖區(qū)忙碌時，應該減少二分法散發(fā)等待路由的初始化副本數(shù)，釋放緩沖區(qū)的空間，于是在節(jié)點的平均緩沖區(qū)利用率低時，使得初始化副本數(shù)快速減少來減少擁塞。在緩沖區(qū)占用率極高時，副本數(shù)減少到一定程度就不再減少了，以保持報文的遞交率。

假設(shè)節(jié)點的報文的初始化副本數(shù)為L，關(guān)系圖如

圖1所示。

圖1 初始化副本數(shù)與節(jié)點平均緩沖區(qū)占用率的關(guān)系

由圖1可知（0＜P＜q＜1）：

（1）當節(jié)點的最終平均緩沖區(qū)占用率 Aνg≤P時，節(jié)點的初始化副本數(shù)迅速增加到 a×L（a＞1），這時緩沖區(qū)占用率比較低，需要增加副本數(shù)會提高遞交率，并且降低平均延遲。

（2）當節(jié)點的最終平均緩沖區(qū)占用率P≤Aνg＜q時，節(jié)點的初始化副本數(shù)迅速降低到b×L，這時緩沖區(qū)占用率比較高，減少副本數(shù)會提高遞交率，且降低網(wǎng)絡(luò)開銷。

（3）當節(jié)點的最終平均緩沖區(qū)占用率q≤Aνg＜1時，這時緩沖區(qū)占用率極高，為了保證遞交率，同時在一定程度上抑制報文數(shù)，把節(jié)點的報文生成的初始化副本數(shù)穩(wěn)定在b×L（0＜b＜1）。

4 仿真結(jié)果與分析

4.1 仿真參數(shù)設(shè)置

本文使用THE ONE（The Opportunistic Network Environment Simulator）［12］仿真器對方案進行仿真。其中，通過仿真發(fā)現(xiàn)，BSW中在副本數(shù)L=16仿真效果最好，SAW-BO中在P=0.8，q=0.95，a=4，b=0.25，仿真效果最優(yōu)。本文采用的是的隨機路點（Random Waypoint）模型。地圖大小為1 000 m× 1 000 m，共放置了100個節(jié)點，這些節(jié)點只有1個組。在報文生成間隔為1 s和30 s時分別做了仿真。具體參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)

在上述仿真環(huán)境下，分別比較報文生成間隔為30 s和1 s時，Epidem ic，BSW及本文算法在報文遞交率、平均延遲及網(wǎng)絡(luò)開銷率上隨時間的變化情況：

（1）遞交率：遞交成功的報文數(shù)量與總的投遞報文數(shù)量的比值。

（2）平均延遲：遞交成功的所有報文從源節(jié)點到信宿節(jié)點的時間之和與總的報文個數(shù)之比。

（3）開銷率：被中繼的報文與成功遞交的報文之差再與成功遞交的報文之比。

4.2 結(jié)果分析

4.2.1 報文生成間隔為30 s的仿真結(jié)果

從圖2可以看出，報文生成間隔為30 s時，本文算法的遞交率最高。由于報文生成的慢，緩沖區(qū)比較空閑，因此本文算法增加報文的副本數(shù)，從而使報文在節(jié)點之間傳輸?shù)拇螖?shù)變高，提高了遞交率。

圖2 報文生成間隔為30 s時遞交率隨時間的變化

從圖3可以看出，報文生成間隔為30 s時，本文算法的平均時延最低。此時大部分節(jié)點的最終緩沖區(qū)占用率較低，本文算法會增加報文的副本數(shù)，此時，報文轉(zhuǎn)發(fā)的可能性增加，導致網(wǎng)絡(luò)中報文遞交的平均延遲比較小。

圖3 報文生成間隔為30 s時平均延遲隨時間的變化

從圖4可以看出，報文生成間隔為30 s時，本文算法的開銷率介于Epidemic與BSW之間。因為這

時網(wǎng)絡(luò)中大部分節(jié)點的緩沖區(qū)比較空閑，本文算法會增加報文的副本數(shù)，增大了開銷率，但報文轉(zhuǎn)發(fā)次數(shù)比Epidemic少，所以本文算法的開銷率比BSW大，比Epidemic小。

圖4 報文生成間隔為30 s時開銷率隨時間的變化

在網(wǎng)絡(luò)中節(jié)點分布均勻時，本文算法通過更改節(jié)點的緩沖區(qū)大小來比較系統(tǒng)性能，此時，設(shè)置仿真時間為 40 000 s，圖 5將遞交率增大為原來的1 000倍，開銷率增大為20倍后作圖。由圖5～圖7可知，在報文生成間隔為30 s時，隨著緩沖區(qū)的增大，遞交率明顯提高，平均延遲先上升后下降并趨于穩(wěn)定，開銷率增大。在報文生成間隔為30 s時，緩沖區(qū)相對空閑，本文算法增加報文的初始化副本數(shù)，增加報文的轉(zhuǎn)發(fā)次數(shù)，當緩沖區(qū)增大到一定程度，由于報文副本上限一定，延遲穩(wěn)定。

圖5 報文生成間隔為30 s時遞交率隨緩沖區(qū)的變化

圖6 報文生成間隔為30 s時平均延遲隨緩沖區(qū)變化

圖7 報文生成間隔為30 s時開銷率隨緩沖區(qū)變化

在報文生成間隔為30 s的仿真情況下，且網(wǎng)絡(luò)中節(jié)點分布不均勻時，通過節(jié)點的分布比例1來比較系統(tǒng)性能，此時設(shè)置仿真時間為40 000 s。分布比例1的計算公式如下：

其中，m為緩沖區(qū)為50 MB的節(jié)點個數(shù)；n為緩沖區(qū)為10 MB的節(jié)點個數(shù)。

由圖8～圖10可知，本文算法在報文生成間隔為30 s時，隨著緩沖區(qū)大的節(jié)點分布比例1的增大，網(wǎng)絡(luò)中緩沖區(qū)相對空閑的節(jié)點變多，增加的文的初始化副本數(shù)的節(jié)點，增加了報文的轉(zhuǎn)發(fā)次數(shù)，從而遞交率增大，平均延遲降低，開銷率增大。

圖8 報文生成間隔為30 s時遞交率隨分布比例1的變化

圖9 報文生成間隔為30 s時平均時延隨分布比例1的變化

圖10 報文生成間隔為30 s時開銷率隨分布比例1的變化

4.2.2 報文生成間隔為1 s的仿真結(jié)果

從圖11可以出，當報文生成間隔為1 s時，在8 000 s之后，本文算法的遞交率高于另2種路由算法。在8 000 s之后，隨著報文生成的越來越多，節(jié)點緩沖區(qū)溢出，網(wǎng)絡(luò)擁塞嚴重，本文算法減少報文的初始化副本數(shù)，進而緩解了網(wǎng)絡(luò)擁塞，提高了遞交率。

圖11 報文生成間隔為1 s時遞交率隨時間變化

從圖12可以看出，當報文生成間隔為1 s時，本文算法的開銷率介于Epidemic與BSW之間。此時，大部分節(jié)點的最終緩沖區(qū)占用率較高，本文算法會減少報文的初始化副本數(shù)，從而使報文在節(jié)點之間傳輸?shù)拇螖?shù)變少導致網(wǎng)絡(luò)中報文遞交的平均延遲比較大。

圖12 報文生成間隔為1 s時平均延遲隨時間的變化

從圖13可以看出，報文生成間隔為1 s時，在4 000 s之后，本文算法的開銷率比Epidem ic與BSW都要低。在4 000 s之前，仿真剛剛開始，緩沖區(qū)比較空閑，本文算法會增加報文的初始化副本數(shù)，從而增大開銷；在4 000 s之后，隨著仿真的進行，網(wǎng)絡(luò)極度擁塞，本文算法會減少報文的初始化副本數(shù)，與BSW相比減少了開銷率。

圖13 報文生成間隔為1 s時開銷率隨時間的變化

在網(wǎng)絡(luò)中節(jié)點分布均勻時，本文算法通過節(jié)點的緩沖區(qū)大小來比較系統(tǒng)性能，此時設(shè)置仿真時間為40 000 s。

由圖14～圖16可知，在報文生成間隔為1 s時，隨著緩沖區(qū)的增大，緩沖區(qū)相對空閑，增加報文的初始化副本數(shù)的節(jié)點，增加了報文的轉(zhuǎn)發(fā)次數(shù)，從而遞交率增大，平均延遲降低并趨于穩(wěn)定，開銷率增大。

圖14 報文生成間隔為1 s時遞交率隨緩沖區(qū)變化

圖15 報文生成間隔為1 s時平均延遲隨緩沖區(qū)變化

圖16 報文生成間隔為1 s時開銷率隨緩沖區(qū)變化

在報文生成間隔為1 s的仿真情況下，且網(wǎng)絡(luò)中節(jié)點分布不均勻時，通過節(jié)點的分布比例2來比較系統(tǒng)性能，此時設(shè)置仿真時間為40 000 s。分布比例2的計算公式如下：

其中，m′為緩沖區(qū)為400 MB的節(jié)點個數(shù)；n′為緩沖區(qū)為50 MB的節(jié)點個數(shù)。

由圖17～圖19可知，在報文生成間隔為1 s時，隨著緩沖區(qū)大的節(jié)點分布比例2的增大，網(wǎng)絡(luò)中緩沖區(qū)相對空閑的節(jié)點變多，增加報文的初始化副本數(shù)的節(jié)點，增加了報文的轉(zhuǎn)發(fā)次數(shù)，從而遞交率增大，平均延遲降低，開銷率增大。

圖17 報文生成間隔為1 s時遞交率隨分布比例2的變化

圖18 報文生成間隔為1 s時平均延遲隨分布比例2的變化

圖19 報文生成間隔為1 s時開銷率隨分布比例2的變化

5 結(jié)束語

本文提出一種基于緩沖區(qū)占用率的散發(fā)等待路由算法。該算法利用節(jié)點的最終平均緩沖區(qū)預測周圍網(wǎng)絡(luò)環(huán)境，然后計算報文的初始化副本數(shù)。仿真結(jié)果表明，該算法在緩沖區(qū)空閑的情況下改善了遞交率和平均延遲。今后將結(jié)合報文的其他特性，比如節(jié)點的能量、移動速度、運動規(guī)律，進一步完善此算法。

［1］ 林 闖，董揚威，單志廣.基于DTN的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］.計算機研究與發(fā)展，2014，51（5）：931-943.

［2］ Samaras C V.Adjusting Transport Segmentation Policy of DTN Bundle Protocol Under Synergy with Lower Layers［J］.Journal of System s&Software，2011，84（2）：226-237.

［3］ Hisamatsu T，Asaeda H.Adaptive Overlay Network for High-bandwidth Streaming［J］.Information and Media Technologies，2012，7（1）：435-447.

［4］ Chaithanya M.Performance Modeling of DTN Routing with Heterogeneous and Selfish Nodes［J］.Wireless Networks，2014，20（1）：25-40.

［5］ 樊秀梅，單志廣，張寶賢，等.容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究［J］.電子學報，2008，36（1）：161-170.

［6］ 裴澤艮，肖明軍，黃劉生.位置關(guān)聯(lián)的延遲容忍網(wǎng)絡(luò)路由算法［J］.計算機工程，2012，38（2）：123-125.

［7］ 熊永平，孫利民，牛建偉，等.機會網(wǎng)絡(luò)［J］.軟件學報，2009，20（1）：124-137.

［8］ Bulut E，Szymanski B.Secure Multi-copy Routing in Com promised Delay Tolerant Networks［J］.Wireless Personal Communications，2013，73（1）：149-168.

［9］ 張 龍，周賢偉，吳啟武.容遲與容斷網(wǎng)絡(luò)路由協(xié)議的綜合評估模型［J］.計算機工程，2010，36（9）：14-16.

［10］ 宋 鑫，王炳庭，胡 勇，等.基于蟻群算法的容遲網(wǎng)絡(luò)概率路由算法［J］.計算機工程，2013，39（4）：90-93.

［11］ 王貴竹，盧華庭，徐 亮.容遲網(wǎng)絡(luò)中基于節(jié)點能量考慮的混合散發(fā)與等待路由算法［J］.計算機工程與科學，2010，32（12）：8-11.

［12］ John W，Vania C.HYMAD：Hybrid DTN-MANET Routing for Dense and Highly Dynamic Wireless Networks［J］. Journal of Computer Communications，2010，33（13）：1483-1492.

編輯 劉 冰

Spray and Wait Routing Algorithm in in DTN Based on Buffer Occupancy Rate

MA Beilei，WANG Guizhu，ZHU Yanjuan，DING Anping
（Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China）

In traditional Spray and Wait（SAW）routing algorithm in Delay Tolerant Network（DTN），the number of copies of the message is certain，which results in some blindness about the forwarding number of the message.It causes the routing algorithm can not adapt to the network environment and cuts down the delivery ratio.To deal with this issue，it gives the relationship between the final average buffer occupancy of the node and the initial number of copies，and proposes a Spray and Wait Routing Concerned on Buffer Occupancy（SAW-BO）in DTN.The algorithm adjusts the initial number of copies dynamically based on the average buffer occupancy rate of the node.It ought to increase the initial number of copies to increase the delivery ratio when the average buffer occupancy of the node is relatively low and it should decrease the initial number of copies when the average buffer occupancy of the node is relatively high to avoid the occurrence of congestion.Simulation results show that compared with BSW routing，the proposed algorithm can significantly improve the delivery ratio and increases the average latency when the average buffer occupancy of the node is low in the network，it can also enhance the delivery ratio and reduce the network overhead when the average buffer occupancy of the node is high in the network.

Delay Tolerant Network（DTN）；routing；Spray and Wait（SAW）；buffer occupancy rate；number of copiesDO I：10.3969/j.issn.1000-3428.2015.10.017

馬蓓蕾，王貴竹，朱妍娟，等.基于緩沖區(qū)占用率的 DTN散發(fā)等待路由算法［J］.計算機工程，2015，41（10）：88-93.

英文引用格式：Ma Beilei，Wang Guizhu，Zhu Yanjuan，et al.Spray and Wait Routing Algorithm in DTN Based on Buffer Occupancy Rate［J］.Computer Engineering，2015，41（10）：88-93.

1000-3428（2015）10-0088-06

A

TP393

馬蓓蕾（1991-），女，碩士研究生，主研方向：無線通信；王貴竹，副教授；朱妍娟、丁安平，碩士研究生。

2014-09-15

2014-11-10E-m ail：m abeileiok@gmail.com