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

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

（安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥230039）

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

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

（安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥230039）

傳統(tǒng)容滯網(wǎng)絡(luò)散發(fā)等待路由算法的節(jié)點(diǎn)副本數(shù)是確定的，使得獲得節(jié)點(diǎn)的轉(zhuǎn)發(fā)次數(shù)具有一定的盲目性，不能很好地適應(yīng)網(wǎng)絡(luò)環(huán)境，降低了遞交率。針對(duì)該問題，研究節(jié)點(diǎn)的最終平均緩沖區(qū)占用率和副本數(shù)的關(guān)系，提出一種基于緩沖區(qū)占用率的路由算法。該算法由節(jié)點(diǎn)的最終平均緩沖區(qū)占用率動(dòng)態(tài)調(diào)整初始化副本數(shù)。在節(jié)點(diǎn)的最終平均緩沖區(qū)占用率較低的情況下，增大報(bào)文的初始化副本數(shù)，以提高遞交率，在節(jié)點(diǎn)的最終平均緩沖區(qū)占用率較高的情況下，減小報(bào)文的初始化副本數(shù)，以避免擁塞的發(fā)生。仿真結(jié)果表明，與二分法散發(fā)等待路由算法相比，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均緩存占用率較低時(shí)，該算法能改善遞交率和降低網(wǎng)絡(luò)平均延時(shí)。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均緩存占用率較高時(shí)，在改進(jìn)遞交率的同時(shí)，能降低整個(gè)網(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ò)采用存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)［5］的方式來進(jìn)行報(bào)文的轉(zhuǎn)發(fā)。在這個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)是稀疏的，因此，節(jié)點(diǎn)在遞交報(bào)文之前需要將報(bào)文存儲(chǔ)一段時(shí)間，通過節(jié)點(diǎn)的移動(dòng)將報(bào)文轉(zhuǎn)發(fā)給其他中繼節(jié)點(diǎn)［6］或信宿節(jié)點(diǎn)。

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

（2）計(jì)算當(dāng)前節(jié)點(diǎn)的最終平均緩沖區(qū)占用率。

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

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

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

當(dāng)每次節(jié)點(diǎn)相遇時(shí)，節(jié)點(diǎn)根據(jù)以下 3步更新記錄：

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

（2）當(dāng)兩節(jié)點(diǎn) A，B相遇，則比較兩節(jié)點(diǎn)的節(jié)點(diǎn)列表：

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

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

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

3.2 參數(shù)計(jì)算

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

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

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

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

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

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

最終平均緩沖區(qū)占用率是更新當(dāng)前節(jié)點(diǎn)的生成報(bào)文的初始化拷貝份數(shù)的重要指標(biāo)。在最終平均緩沖區(qū)占用率低時(shí)，認(rèn)為當(dāng)前節(jié)點(diǎn)緩沖區(qū)空閑。

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

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

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

圖1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 結(jié)果分析

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

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

圖2 報(bào)文生成間隔為30 s時(shí)遞交率隨時(shí)間的變化

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

圖3 報(bào)文生成間隔為30 s時(shí)平均延遲隨時(shí)間的變化

從圖4可以看出，報(bào)文生成間隔為30 s時(shí)，本文算法的開銷率介于Epidemic與BSW之間。因?yàn)檫@

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

圖4 報(bào)文生成間隔為30 s時(shí)開銷率隨時(shí)間的變化

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

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

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

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

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

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

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

圖8 報(bào)文生成間隔為30 s時(shí)遞交率隨分布比例1的變化

圖9 報(bào)文生成間隔為30 s時(shí)平均時(shí)延隨分布比例1的變化

圖10 報(bào)文生成間隔為30 s時(shí)開銷率隨分布比例1的變化

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

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

圖11 報(bào)文生成間隔為1 s時(shí)遞交率隨時(shí)間變化

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

圖12 報(bào)文生成間隔為1 s時(shí)平均延遲隨時(shí)間的變化

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

圖13 報(bào)文生成間隔為1 s時(shí)開銷率隨時(shí)間的變化

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

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

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

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

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

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

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

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

圖17 報(bào)文生成間隔為1 s時(shí)遞交率隨分布比例2的變化

圖18 報(bào)文生成間隔為1 s時(shí)平均延遲隨分布比例2的變化

圖19 報(bào)文生成間隔為1 s時(shí)開銷率隨分布比例2的變化

5 結(jié)束語

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

［1］ 林 闖，董揚(yáng)威，單志廣.基于DTN的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］.計(jì)算機(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］.電子學(xué)報(bào)，2008，36（1）：161-170.

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

［7］ 熊永平，孫利民，牛建偉，等.機(jī)會(huì)網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，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é)議的綜合評(píng)估模型［J］.計(jì)算機(jī)工程，2010，36（9）：14-16.

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

［11］ 王貴竹，盧華庭，徐 亮.容遲網(wǎng)絡(luò)中基于節(jié)點(diǎn)能量考慮的混合散發(fā)與等待路由算法［J］.計(jì)算機(jī)工程與科學(xué)，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］.計(jì)算機(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