DTN中基于Epidemic路由的擁塞控制策略研究

汪佩佩 李 濤 王汝傳

1(南京郵電大學(xué)通信與信息工程學(xué)院 江蘇 南京 210003)2(南京郵電大學(xué)計(jì)算機(jī)學(xué)院 江蘇 南京 210003)

0 引 言

DTN，即延遲容忍網(wǎng)絡(luò)，源自于對(duì)行星際通信網(wǎng)絡(luò)[1]的描述，現(xiàn)在通常指在消息傳輸過程中不能確保端到端路徑的無線網(wǎng)絡(luò)。DTN網(wǎng)絡(luò)主要有生態(tài)環(huán)境監(jiān)控網(wǎng)絡(luò)[2]、無線車載自組織網(wǎng)絡(luò)[3]、PeopleNet[4]等。

DTN網(wǎng)絡(luò)具有連接間斷、節(jié)點(diǎn)移動(dòng)頻繁、延遲大、遞交率低、存儲(chǔ)容量有限等特點(diǎn)[5]，又因?yàn)槠涮厥獾膫鬏敱９軝C(jī)制，使得該網(wǎng)絡(luò)極易產(chǎn)生擁塞。因此，有必要針對(duì)現(xiàn)有的路由算法，改進(jìn)相應(yīng)的擁塞控制策略，從而實(shí)現(xiàn)消息更高效率的轉(zhuǎn)發(fā)，避免擁塞的產(chǎn)生，以及在擁塞發(fā)生后采取合理的緩存管理策略，選擇合適的消息丟棄以使擁塞節(jié)點(diǎn)獲得足夠容納新消息的空間，緩解網(wǎng)絡(luò)擁塞。

本文在Epidemic路由算法[6]的基礎(chǔ)上，給出一種擁塞控制策略RBCCS，從下一跳節(jié)點(diǎn)選擇和緩存管理策略兩個(gè)方面入手，避免和緩解網(wǎng)絡(luò)的擁塞狀況。仿真結(jié)果顯示，RBCCS使DTN網(wǎng)絡(luò)在消息遞交率、平均時(shí)延和開銷率等網(wǎng)絡(luò)性能方面的表現(xiàn)均有所提高。

1 相關(guān)工作

DTN網(wǎng)絡(luò)中關(guān)于擁塞控制策略的研究可大致分為主動(dòng)、被動(dòng)和混合型三類[7]：

主動(dòng)擁塞控制策略：主動(dòng)擁塞控制指通過特定的策略控制消息的傳輸，預(yù)防網(wǎng)絡(luò)發(fā)生擁塞。如文獻(xiàn)[8]根據(jù)節(jié)點(diǎn)的的剩余緩存和能量將節(jié)點(diǎn)劃分為不同的級(jí)別，接收消息時(shí)根據(jù)不同級(jí)別采取不同的接收策略,避免節(jié)點(diǎn)陷入擁塞。文獻(xiàn)[9]則將網(wǎng)絡(luò)中的消息分為普通消息和特殊消息,其中特殊消息要求更高的傳輸率。然后根據(jù)節(jié)點(diǎn)的擁塞程度將節(jié)點(diǎn)狀態(tài)分為三個(gè)等級(jí),每個(gè)節(jié)點(diǎn)根據(jù)自己所處的等級(jí)和消息的情況自主決策消息的接收行為，實(shí)現(xiàn)了更好的網(wǎng)絡(luò)性能。

被動(dòng)擁塞控制策略：當(dāng)擁塞發(fā)生時(shí)采取一定的丟包策略來減輕節(jié)點(diǎn)負(fù)載，緩解或消除網(wǎng)絡(luò)的擁塞情況。如文獻(xiàn)[10]提出了一種基于效用值的緩沖管理策略(UBM)，UBM根據(jù)節(jié)點(diǎn)的興趣和消息的投遞概率計(jì)算出消息的效用值，然后基于該效用值提出整體緩沖管理策略， 實(shí)現(xiàn)通過較小的網(wǎng)絡(luò)成本獲得更高的傳輸率和更低的延遲。文獻(xiàn)[11]提出根據(jù)節(jié)點(diǎn)的本地知識(shí)，計(jì)算出消息的權(quán)重，基于消息權(quán)重的丟包策略。文獻(xiàn)[12]針對(duì)多播類型的DTN網(wǎng)絡(luò)提出的基于效用函數(shù)的丟棄和調(diào)度策略。

混合型擁塞控制策略：混合型擁塞控制將主動(dòng)與被動(dòng)型擁塞控制相結(jié)合。如文獻(xiàn)[13]根據(jù)節(jié)點(diǎn)在運(yùn)動(dòng)過程中所獲得的一些歷史信息,以直接獲取及間接推薦的方式準(zhǔn)確地感知網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的擁塞狀態(tài),進(jìn)而以分布式的方式動(dòng)態(tài)地為數(shù)據(jù)選擇中繼節(jié)點(diǎn),達(dá)到更加合理地利用有限的網(wǎng)絡(luò)資源以及避免和緩解網(wǎng)絡(luò)的擁塞情況的目的。文獻(xiàn)[14]提出一種采用機(jī)器學(xué)習(xí)技術(shù)的框架Smart-DTN-CC，該框架中節(jié)點(diǎn)從環(huán)境獲得輸入(例如其緩存占用，鄰居集等)，并且基于這些信息，從一組將要執(zhí)行的行動(dòng)集中選擇要采取的行動(dòng)。然后根據(jù)采取的行動(dòng)在擁塞控制方面的有效性給予該動(dòng)作相應(yīng)激勵(lì)，以期最大限度地提高整體激勵(lì)，從而最大限度地減少擁塞。

2 Epidemic路由

Epidemic路由算法是由Vahdat等首次提出的。在Epidemic路由中，節(jié)點(diǎn)通過周期性地廣播Hello消息來發(fā)現(xiàn)在其通信范圍內(nèi)的鄰居節(jié)點(diǎn)，在與鄰居節(jié)點(diǎn)通信時(shí)，節(jié)點(diǎn)不進(jìn)行路由決策，而是將消息副本洪泛至所有的鄰居節(jié)點(diǎn)。該路由算法為網(wǎng)絡(luò)中的每一個(gè)消息維持一個(gè)全局標(biāo)識(shí)符(ID)，用于在整個(gè)網(wǎng)絡(luò)中唯一標(biāo)識(shí)該消息。節(jié)點(diǎn)以消息ID為鍵，對(duì)消息進(jìn)行哈希運(yùn)算后以鍵值對(duì)的形式存儲(chǔ)，并用一個(gè)摘要矢量SV(summary vector)標(biāo)識(shí)哈希表中每一個(gè)消息的“有”或“無”。若節(jié)點(diǎn)有某消息，則SV對(duì)應(yīng)位置為1，否則為0。某一時(shí)刻，節(jié)點(diǎn)A和節(jié)點(diǎn)B進(jìn)行通信的過程如圖1所示。

圖1 Epidemic路由數(shù)據(jù)通信過程

(1) 節(jié)點(diǎn)A向節(jié)點(diǎn)B發(fā)送A的摘要矢量SVA，告訴B自己緩存中有哪些消息；

(2) B收到SVA后執(zhí)行運(yùn)算:

Request=SVA&(～SVB)

(1)

Request為節(jié)點(diǎn)A緩存中有而節(jié)點(diǎn)B緩存中沒有的消息的矢量，然后B將Request發(fā)往A；

(3) 節(jié)點(diǎn)A收到Request后，按要求逐個(gè)發(fā)送消息給節(jié)點(diǎn)B；

(4) 節(jié)點(diǎn)B收到請(qǐng)求的消息后，更新SVB。若B收到的消息中有目的節(jié)點(diǎn)是自己的，就將其上傳應(yīng)用層并從緩存中丟棄。

3 擁塞控制策略RBCCS

3.1 下一跳節(jié)點(diǎn)的選擇策略

Epidemic 路由沒有對(duì)下一跳節(jié)點(diǎn)加以選擇，而是向所有在傳播范圍內(nèi)的鄰居節(jié)點(diǎn)洪泛消息副本。但是由于DTN網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性強(qiáng)、通信范圍有限以及消息發(fā)送時(shí)延大等特點(diǎn)，導(dǎo)致發(fā)送機(jī)會(huì)十分寶貴，盲目洪泛會(huì)浪費(fèi)有限的網(wǎng)絡(luò)資源。另外，DTN網(wǎng)絡(luò)的節(jié)點(diǎn)緩存空間通常是有限的，一旦緩存被占滿后就會(huì)產(chǎn)生擁塞，網(wǎng)絡(luò)中較多節(jié)點(diǎn)陷入擁塞將使網(wǎng)絡(luò)陷入傳輸瓶頸，大大降低網(wǎng)絡(luò)性能。

因此，RBCCS提出一種下一跳節(jié)點(diǎn)的選擇策略。該策略采用一個(gè)參數(shù)緩存空閑率BC作為下一跳節(jié)點(diǎn)選擇的依據(jù)，其定義如下：

(2)

式中：Bfree表示節(jié)點(diǎn)的剩余緩存大小，Binit表示節(jié)點(diǎn)初始化時(shí)的緩存大小。緩存空閑率大，則表示該節(jié)點(diǎn)在擁塞前能接收的消息越多。在選擇下一跳節(jié)點(diǎn)時(shí)以本節(jié)點(diǎn)BC為選擇閾值，只將消息發(fā)送到BC值大于該閾值的鄰居節(jié)點(diǎn)，若鄰居節(jié)點(diǎn)的BC均小于該閾值，就放棄本次機(jī)會(huì)。

3.2 緩存管理策略

傳統(tǒng)的緩存管理策略主要有以下幾種：DLA(Drop-Largest)，丟棄緩存中最大的消息；DLR(Drop-Least-Recently-Received)，丟棄在緩存中存在時(shí)間最長的消息；DO(Drop-Oldest)，丟棄緩存中在網(wǎng)絡(luò)中存在時(shí)間最久的消息；DY(Drop-Youn- gest)，丟棄剩余生存時(shí)間最長的消息。它們大都只考慮到消息的單一屬性，簡單而片面,具有一定的局限性。

RBCCS提出的緩存管理策略則綜合考慮消息的生存時(shí)間TTL、已轉(zhuǎn)發(fā)次數(shù)和被當(dāng)前節(jié)點(diǎn)接收的時(shí)刻，給出綜合度量三者的一種歸一化參數(shù)，即消息冗余度MR：

(3)

式中：TTL表示消息的生存時(shí)間，TTLinit表示消息的初始化生存時(shí)間,Fc表示消息M已經(jīng)被轉(zhuǎn)發(fā)的次數(shù)，F(xiàn)max是網(wǎng)絡(luò)中消息被轉(zhuǎn)發(fā)的最大次數(shù)，Tr為消息被當(dāng)前節(jié)點(diǎn)接收的時(shí)刻，Ts為仿真的總時(shí)長。w1、w2和w3分別表示上述三個(gè)元素對(duì)于MR的權(quán)重大小，w1+w2+w3=1。TTL和Tr越小、Fc越大的消息在網(wǎng)絡(luò)中存在的時(shí)間越長，已被傳送給網(wǎng)絡(luò)中較多的節(jié)點(diǎn)，則其在網(wǎng)絡(luò)中的副本數(shù)也越多，已被成功遞交到目的節(jié)點(diǎn)的概率也越高，因此該消息的冗余度也越大。當(dāng)節(jié)點(diǎn)陷入擁塞時(shí)，RBCCS策略會(huì)率先丟棄冗余度大的消息，以釋放節(jié)點(diǎn)緩存。

權(quán)重的大小決定了消息各屬性在決定冗余度時(shí)所占的比例，為權(quán)衡各屬性的利弊，經(jīng)大量仿真實(shí)驗(yàn)確定，當(dāng)w1=0.15、w2=0.35、w3=0.50時(shí)，所得效果最好。

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

4.1 仿真環(huán)境設(shè)置

ONE[15-16](Opportunistic Network Environment) 是基于Java語言的一款專門用于DTN網(wǎng)絡(luò)路由仿真的工具。本文采用ONE分別在Epidemic路由算法基礎(chǔ)上對(duì)DLA、DLR、DO和RBCCS擁塞控制策略進(jìn)行仿真，以評(píng)估各種擁塞控制策略對(duì)DTN網(wǎng)絡(luò)性能指標(biāo)的影響。仿真采用自帶的赫爾辛基市地圖，節(jié)點(diǎn)類型全部為行人，運(yùn)動(dòng)模型采用基于地圖最短路徑模型。具體參數(shù)設(shè)置如表1所示。

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

4.2 結(jié)果分析

為了能更好地分析上述幾種擁塞控制策略對(duì)DTN網(wǎng)絡(luò)的影響，需要采用一些合理的網(wǎng)絡(luò)性能指標(biāo)進(jìn)行評(píng)估。本文主要采用消息遞交率、開銷率和平均時(shí)延三個(gè)指標(biāo)來判斷應(yīng)用各種擁塞控制策略時(shí)DTN網(wǎng)絡(luò)的性能。

(1) 消息遞交率:

(4)

消息遞交率表示網(wǎng)絡(luò)中成功遞交的消息總數(shù)與生成的消息總數(shù)的比值。式(4)中，Delivered為成功遞交到目的節(jié)點(diǎn)的消息總數(shù)，Created為網(wǎng)絡(luò)中生成的消息總數(shù)。圖2顯示當(dāng)仿真時(shí)間固定為12 h，節(jié)點(diǎn)數(shù)固定為100，節(jié)點(diǎn)緩存大小從5～50 MB不等時(shí)幾種策略的消息遞交率。

圖2 不同緩存大小時(shí)的消息遞交率

由圖2可知，RBCCS和DO策略在遞交率上的表現(xiàn)優(yōu)于另外兩種傳統(tǒng)策略。當(dāng)緩存小于15 MB時(shí)，RBCCS與DO策略差別不大，這是因?yàn)榫彺孑^小時(shí)，節(jié)點(diǎn)能攜帶的消息個(gè)數(shù)較少，RBCCS的緩存管理策略效果有限。緩存較大時(shí)，節(jié)點(diǎn)能存儲(chǔ)攜帶的消息數(shù)增加，擁塞時(shí)如何從緩存中選擇合適的消息丟棄更加重要。當(dāng)緩存為50 MB時(shí)，RBCCS的遞交率相對(duì)最好的DO策略提升了15.8%。這是因?yàn)镽BCCS綜合考慮了消息的生存時(shí)間、接收時(shí)刻和已轉(zhuǎn)發(fā)次數(shù)這三個(gè)屬性，給出了消息冗余度的概念，更加合理地評(píng)估了消息在網(wǎng)絡(luò)中冗余的程度。優(yōu)先丟棄冗余度高的消息，可以得到更好地消息遞交率。另外，RBCCS增加了下一跳節(jié)點(diǎn)選擇策略，優(yōu)先將消息發(fā)送到緩存空閑率較大的鄰居節(jié)點(diǎn)上，也能有效避免節(jié)點(diǎn)的擁塞。

(2) 開銷率：

(5)

開銷率表示網(wǎng)絡(luò)中為了成功遞交消息而額外轉(zhuǎn)發(fā)的消息總數(shù)與成功遞交的消息總數(shù)的比值，該參數(shù)越小則消息轉(zhuǎn)發(fā)效率越高。式(5)中，Relayed表示消息被中間節(jié)點(diǎn)轉(zhuǎn)發(fā)的總轉(zhuǎn)發(fā)次數(shù)，Delivered表示網(wǎng)絡(luò)中被成功遞交到目的節(jié)點(diǎn)的消息總數(shù)。

圖3表示不同節(jié)點(diǎn)數(shù)時(shí)的網(wǎng)絡(luò)開銷率。從圖中可以看出，RBCCS策略的總體表現(xiàn)更好，緩存為50M時(shí)，相對(duì)表現(xiàn)最好的DO策略更是降低了14.4%。 這是因?yàn)镽BCCS對(duì)下一跳節(jié)點(diǎn)加以決策，避免盲目地洪泛消息副本，減少了消息總體的轉(zhuǎn)發(fā)次數(shù)。又在緩存管理策略上加入對(duì)消息已轉(zhuǎn)發(fā)次數(shù)的考慮，已轉(zhuǎn)發(fā)次數(shù)越多的消息冗余度越大，越優(yōu)先被丟棄，所以網(wǎng)絡(luò)整體的開銷率有所下降。

圖3 不同緩存大小時(shí)的網(wǎng)絡(luò)開銷率

(3) 平均時(shí)延：

(6)

平均時(shí)延表示所有成功遞交的消息從源節(jié)點(diǎn)到目的節(jié)點(diǎn)花費(fèi)的平均時(shí)間。式(6)中,tid為消息i被目的節(jié)點(diǎn)接收到的時(shí)刻，tis為消息i在源節(jié)點(diǎn)生成的時(shí)刻，n為網(wǎng)絡(luò)中成功遞交到目的節(jié)點(diǎn)的消息總數(shù)。

由圖4可知，RBCCS的平均時(shí)延較另外幾種傳統(tǒng)策略也有所下降，相對(duì)表現(xiàn)最佳的DLA策略仍能下降6.8%左右。這是因?yàn)镽BCCS加入的下一跳節(jié)點(diǎn)選擇策略會(huì)將消息遞交給緩存空閑率更大的節(jié)點(diǎn)，避免了一些可能發(fā)生的擁塞情況，所以因擁塞產(chǎn)生的排隊(duì)消息數(shù)會(huì)減少，從而減少了消息的排隊(duì)時(shí)延。而且RBCCS在擁塞發(fā)生后的緩存管理策略中，會(huì)將消息生存時(shí)間小、接收時(shí)刻早以及已轉(zhuǎn)發(fā)次數(shù)較多的消息優(yōu)先丟棄。這類消息在緩存中排隊(duì)的時(shí)間往往更長，故而RBCCS在平均時(shí)延方面也頗具優(yōu)勢(shì)。

圖4 不同緩存大小時(shí)的平均時(shí)延

5 結(jié) 語

本文基于Epidemic路由算法給出一種擁塞控制策略RBCCS，從消息下一跳節(jié)點(diǎn)選擇和緩存管理策略兩方面進(jìn)行改進(jìn)。節(jié)點(diǎn)與鄰居節(jié)點(diǎn)進(jìn)行通信時(shí)，只將消息投遞給緩存空閑率大于自身的鄰居節(jié)點(diǎn)，不再盲目地洪泛。 當(dāng)節(jié)點(diǎn)發(fā)生擁塞時(shí)，綜合考慮消息的生存時(shí)間、已轉(zhuǎn)發(fā)次數(shù)和被節(jié)點(diǎn)接收時(shí)刻計(jì)算出消息冗余度，優(yōu)先丟棄冗余度大的消息，緩解擁塞情況。仿真結(jié)果表明，相較于幾種傳統(tǒng)的擁塞控制策略，RBCSS能使消息遞交率提升15.8%，平均時(shí)延降低6.8%，網(wǎng)絡(luò)開銷降低14.4%。但該策略在計(jì)算消息各屬性對(duì)于消息冗余度的權(quán)重時(shí)，采用的是從大量仿真結(jié)果中篩選的方法，工作量較大，因此下一步的研究工作是采用一種合理的分析方法，用理論分析計(jì)算和仿真實(shí)驗(yàn)相結(jié)合的方法得出權(quán)重的取值比例。