機(jī)會(huì)網(wǎng)絡(luò)中一種低緩存占用的Epidemic路由算法

左成章，劉智虎，孫希勝，索建偉

（重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

機(jī)會(huì)網(wǎng)絡(luò)中一種低緩存占用的Epidemic路由算法

左成章，劉智虎，孫希勝，索建偉

（重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

由于機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的緩存空間有限，容易導(dǎo)致數(shù)據(jù)分組丟失和時(shí)延增加。針對(duì)部分?jǐn)?shù)據(jù)分組已經(jīng)到達(dá)目的節(jié)點(diǎn)，但是該類分組仍在網(wǎng)絡(luò)中其它節(jié)點(diǎn)存儲(chǔ)、傳輸問(wèn)題，提出一種低緩存占用的Epidemic路由算法（RBER）。該算法通過(guò)SV運(yùn)算進(jìn)行節(jié)點(diǎn)緩存清理，從而避免這類冗余數(shù)據(jù)分組對(duì)緩存的占用。理論分析和仿真結(jié)果表明，該機(jī)制能夠降低網(wǎng)絡(luò)開(kāi)銷、數(shù)據(jù)分組的發(fā)送和緩存占用。

機(jī)會(huì)網(wǎng)絡(luò)；路由算法；緩存；清理

機(jī)會(huì)網(wǎng)絡(luò)(Opportunistic Networks)[1]是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完整路徑，利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)網(wǎng)絡(luò)通信的自組織網(wǎng)絡(luò)。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁改變，不能保證連通性，信息源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間不一定存在傳輸路徑。在機(jī)會(huì)網(wǎng)絡(luò)路由算法中，應(yīng)用和研究較為廣泛的是基于復(fù)制的路由算法。在機(jī)會(huì)網(wǎng)絡(luò)中為了能夠有效的進(jìn)行數(shù)據(jù)的傳輸，“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的路由模式成為優(yōu)先考慮的一種機(jī)制。在這種機(jī)制中，節(jié)點(diǎn)在收到數(shù)據(jù)分組時(shí)，通常將數(shù)據(jù)分組存儲(chǔ)到本節(jié)點(diǎn)，攜帶著數(shù)據(jù)分組一起移動(dòng)，當(dāng)遇到合適的節(jié)點(diǎn)時(shí)再將數(shù)據(jù)分組轉(zhuǎn)發(fā)出去。數(shù)據(jù)分組在節(jié)點(diǎn)相遇時(shí)被多次的轉(zhuǎn)發(fā)，網(wǎng)絡(luò)中存在多個(gè)數(shù)據(jù)分組的副本。

其中，最為典型的算法就是Epidemic路由算法[2]。該算法因其較高的投遞率和較低的時(shí)延特性而備受關(guān)注。但是，該算法類似于泛洪機(jī)制，對(duì)網(wǎng)絡(luò)資源的要求比較高，在苛刻的機(jī)會(huì)網(wǎng)絡(luò)環(huán)境中，算法性能的提升受到限制。

為此，本文提出一種低緩存占用的Epidemic路由（RBER，Reduce Buffer overhead based Epidemic Routing）算法，通過(guò)優(yōu)先刪除目的地址為對(duì)方節(jié)點(diǎn)的數(shù)據(jù)分組，減少了網(wǎng)絡(luò)中數(shù)據(jù)分組副本的擴(kuò)散，降低網(wǎng)絡(luò)資源開(kāi)銷，提高緩存利用率。

1 相關(guān)工作

Harras等提出了Controlled Flooding路由算法[3]。該算法假定每個(gè)節(jié)點(diǎn)只知道自身以及自己攜帶的消息信息，并且能夠完全自主作出轉(zhuǎn)發(fā)決策。該算法通過(guò)意愿概率、生存時(shí)間 (TTS，Time-To-Send)和死亡時(shí)間(TTL，Time-To-Live)3個(gè)參數(shù)來(lái)控制消息泛洪。此外，通過(guò)廣播免疫信息來(lái)及時(shí)刪除已達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組。該算法在保證可靠投遞的同時(shí)減少了網(wǎng)絡(luò)開(kāi)銷。

Epidemic路由算法是一種基于洪泛策略和復(fù)制的路由協(xié)議。每一個(gè)攜帶數(shù)據(jù)的節(jié)點(diǎn)都將數(shù)據(jù)的副本傳遞給它所遇到的未帶有該消息節(jié)點(diǎn)，通過(guò)“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”逐跳傳遞將消息送達(dá)目的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)摘要矢量(SV，Summary Vector)，當(dāng)兩個(gè)節(jié)點(diǎn)能夠連接時(shí)通過(guò)交換消息向量來(lái)彼此交換較少的消息。經(jīng)過(guò)一段時(shí)間，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)將接收到所有的消息。優(yōu)點(diǎn)是不需要額外的拓?fù)淇刂菩畔ⅲ瑫r(shí)可以取得高的消息投遞率和低的端到端時(shí)延，無(wú)需對(duì)鏈路狀態(tài)進(jìn)行預(yù)測(cè)與估計(jì)，實(shí)施起來(lái)較為簡(jiǎn)單。缺點(diǎn)是網(wǎng)絡(luò)中存在大量的冗余副本將導(dǎo)致節(jié)點(diǎn)能耗增加和緩存溢出，進(jìn)而導(dǎo)致網(wǎng)絡(luò)的資源利用率低和網(wǎng)絡(luò)性能下降。

MRRMR(Message Redundancy Removal of Multi-copy Routing)算法[4]在ER算法的基礎(chǔ)上為每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)增加一個(gè)相遇計(jì)數(shù)器。該計(jì)數(shù)器記錄節(jié)點(diǎn)遇到的帶有相同消息拷貝的不同節(jié)點(diǎn)的數(shù)目。如果計(jì)數(shù)器的值達(dá)到了所設(shè)置的門限值，則節(jié)點(diǎn)將該消息拷貝從緩存中移除，并且之后不再接收該消息拷貝。通過(guò)設(shè)置合理的門限值，可以在保證消息投遞成功率和不增加控制分組開(kāi)銷的同時(shí)，將冗余拷貝高效的控制在一個(gè)相對(duì)低的水平并且可以顯著減少節(jié)點(diǎn)緩存占用。但是，由于節(jié)點(diǎn)移動(dòng)的隨機(jī)性，合理門限值的選定比較困難。并且，消息拷貝的過(guò)早移除，還會(huì)導(dǎo)致傳輸時(shí)延的增加。

文獻(xiàn)[5]提出n-epidemic路由算法，僅當(dāng)節(jié)點(diǎn)當(dāng)前擁有的鄰居節(jié)點(diǎn)個(gè)數(shù)達(dá)到一個(gè)特定的門限值時(shí)，才進(jìn)行數(shù)據(jù)傳輸，這就可以使用較少的傳輸次數(shù)獲取較多的接收，減少數(shù)據(jù)傳輸次數(shù)。但是，由于未能充分利用節(jié)點(diǎn)之間短暫的相遇機(jī)會(huì)，導(dǎo)致數(shù)據(jù)分組不能及時(shí)傳遞，投遞時(shí)延增加。

2 Epidemic路由算法

Epidemic算法中，每個(gè)移動(dòng)節(jié)點(diǎn)都設(shè)有一個(gè)緩存區(qū)用于存儲(chǔ)數(shù)據(jù)。注入網(wǎng)絡(luò)中的每一個(gè)數(shù)據(jù)分組都有一個(gè)全局標(biāo)識(shí)符，節(jié)點(diǎn)以該標(biāo)識(shí)符為鍵值，為緩存中所有的數(shù)據(jù)分組建立了一張哈希索引表。同時(shí)，節(jié)點(diǎn)還維護(hù)一個(gè)一維比特?cái)?shù)組，即SV用于標(biāo)示該節(jié)點(diǎn)當(dāng)前緩存中的數(shù)據(jù)分組存儲(chǔ)情況。節(jié)點(diǎn)周期性的廣播Hello消息進(jìn)行鄰居發(fā)現(xiàn)，某一時(shí)刻，節(jié)點(diǎn)X和節(jié)點(diǎn)Y相遇，其數(shù)據(jù)交互過(guò)程如圖1所示。

圖1 Epidemic算法數(shù)據(jù)交互過(guò)程

（1）節(jié)點(diǎn)X向節(jié)點(diǎn)Y發(fā)送摘要矢量SVX，告知節(jié)點(diǎn)Y節(jié)點(diǎn)X當(dāng)前緩存中存有的數(shù)據(jù)分組。

（2）節(jié)點(diǎn)Y收到SVX后，通過(guò)與自己保存的SVY作如下位運(yùn)算：

通過(guò)上述運(yùn)算，節(jié)點(diǎn)Y獲得節(jié)點(diǎn)X緩存中有而本身沒(méi)有的數(shù)據(jù)分組信息，并向節(jié)點(diǎn)X發(fā)送RequestX控制分組來(lái)請(qǐng)求這些數(shù)據(jù)分組。

（3）節(jié)點(diǎn)X收到RequestX后，向節(jié)點(diǎn)Y發(fā)送對(duì)應(yīng)的請(qǐng)求分組。

（4）節(jié)點(diǎn)Y收到數(shù)據(jù)分組后，更新自己的SVY。此外，若該數(shù)據(jù)分組的目的地址為自己，則將其上傳至應(yīng)用層；否則，放入自己的緩存中，進(jìn)行存儲(chǔ)、轉(zhuǎn)發(fā)。

上述4個(gè)過(guò)程以X、Y兩個(gè)節(jié)點(diǎn)為例，描述了網(wǎng)絡(luò)中節(jié)點(diǎn)間數(shù)據(jù)分組的傳輸過(guò)程。

3 RBER路由算法

RBER算法通過(guò)對(duì)SV信息運(yùn)算進(jìn)行節(jié)點(diǎn)緩存清理的具體操作如下。

當(dāng)節(jié)點(diǎn)X收到節(jié)點(diǎn)Y發(fā)送的SVY，進(jìn)行如下位運(yùn)算：

矢量SVZ顯示的是節(jié)點(diǎn)X、Y都存有的數(shù)據(jù)分組。

節(jié)點(diǎn)X遍歷SVZ中顯示的數(shù)據(jù)分組，查詢各數(shù)據(jù)分組所對(duì)應(yīng)的目的節(jié)點(diǎn)是否為Y，如果是，則刪除該數(shù)據(jù)分組（節(jié)點(diǎn)Y中已存有該分組副本，即該分組已達(dá)目的節(jié)點(diǎn)Y，無(wú)需在網(wǎng)絡(luò)中繼續(xù)擴(kuò)散）并且更新其分組已達(dá)信息列表ReachX；從而達(dá)到清理節(jié)點(diǎn)緩存、減少存儲(chǔ)開(kāi)銷和資源消耗的效果。

RBER算法通過(guò)Request控制分組實(shí)現(xiàn)分組已達(dá)信息通告的具體操作如下：

（1）當(dāng)節(jié)點(diǎn)X收到節(jié)點(diǎn)Y發(fā)送的SVY，進(jìn)行如下位運(yùn)算：

比特矢量RequestX顯示的是節(jié)點(diǎn)Y中存有而節(jié)點(diǎn)X中沒(méi)有的數(shù)據(jù)分組信息。

（2）節(jié)點(diǎn)X之后做如下位運(yùn)算：

節(jié)點(diǎn)X發(fā)送RequestX’，其中包含了待請(qǐng)求的數(shù)據(jù)分組信息以及部分分組到達(dá)信息。該機(jī)制能夠在未增加控制開(kāi)銷的條件下，實(shí)現(xiàn)分組已達(dá)信息的通告，提高緩存管理效率，降低網(wǎng)絡(luò)開(kāi)銷和緩存占用。

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

采用OPNET 14.5軟件進(jìn)行建模和仿真，在相同的仿真條件下，從網(wǎng)絡(luò)開(kāi)銷、數(shù)據(jù)分組發(fā)送次數(shù)以及平均緩存占用等方面，將RBER算法與Epidemic算法進(jìn)行性能比較與分析。

4.1 仿真場(chǎng)景設(shè)置

設(shè)置100個(gè)節(jié)點(diǎn)在1 500 m×600 m的矩形范圍內(nèi)采用Random Waypoint運(yùn)動(dòng)模型移動(dòng)。隨機(jī)選擇其中的55個(gè)節(jié)點(diǎn)作為中間轉(zhuǎn)發(fā)節(jié)點(diǎn)，其余的45個(gè)節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)分組，其中每個(gè)節(jié)點(diǎn)產(chǎn)生44個(gè)數(shù)據(jù)分組分別發(fā)往其它44個(gè)節(jié)點(diǎn)，總計(jì)1 980個(gè)數(shù)據(jù)分組。每個(gè)數(shù)據(jù)分組大小為1 KB，數(shù)據(jù)分組產(chǎn)生間隔為1 s。節(jié)點(diǎn)通信半徑為10 m、25 m、50 m、75 m、100 m，仿真時(shí)間為3 000 s。節(jié)點(diǎn)緩存大小為3 000 KB，最大數(shù)據(jù)速率為54 Mbit/s，移動(dòng)速度v∈[1，19](m/s)。

4.2 仿真結(jié)果分析

仿真中主要從網(wǎng)絡(luò)開(kāi)銷、數(shù)據(jù)分組發(fā)送次數(shù)、平均緩存占用率等3個(gè)性能參數(shù)對(duì)所提算法的性能進(jìn)行評(píng)估。

4.2.1 網(wǎng)絡(luò)開(kāi)銷

網(wǎng)絡(luò)開(kāi)銷是指網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)，所有節(jié)點(diǎn)發(fā)送的分組（Hello分組、SV分組、Request分組和數(shù)據(jù)分組）所包含的總比特?cái)?shù)。其值為：

其中，Ctotal為總的網(wǎng)絡(luò)開(kāi)銷，SH和NH分別對(duì)應(yīng)Hello分組的長(zhǎng)度和總的發(fā)送個(gè)數(shù)。同樣，SSV和NSV分別對(duì)應(yīng)SV分組的長(zhǎng)度和總的發(fā)送個(gè)數(shù)；SR和NR分別對(duì)應(yīng)Request分組的長(zhǎng)度和總的發(fā)送個(gè)數(shù)；SD和ND分別對(duì)應(yīng)數(shù)據(jù)分組的長(zhǎng)度和總的發(fā)送個(gè)數(shù)。仿真結(jié)果如圖2所示。

圖2 網(wǎng)絡(luò)開(kāi)銷對(duì)比

由圖2可知，隨著通信范圍的增大，節(jié)點(diǎn)相遇機(jī)會(huì)和相遇持續(xù)時(shí)間都會(huì)增加，導(dǎo)致各算法中相應(yīng)的操作和網(wǎng)絡(luò)開(kāi)銷增加。RBER算法的網(wǎng)絡(luò)開(kāi)銷在各個(gè)場(chǎng)景都略低于Epidemic算法，這是由于RBER算法引入節(jié)點(diǎn)緩存清理機(jī)制，刪除本地緩存中已經(jīng)到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組，減少了不必要的數(shù)據(jù)分組在網(wǎng)絡(luò)中的發(fā)送。

4.2.2 數(shù)據(jù)分組發(fā)送次數(shù)

節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組包括節(jié)點(diǎn)自身產(chǎn)生并發(fā)送的數(shù)據(jù)分組以及為其它節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組。數(shù)據(jù)分組發(fā)送次數(shù)是指在網(wǎng)絡(luò)運(yùn)行時(shí)間內(nèi)，所有節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組總次數(shù)。其值為：

其中，Ntotal為總的數(shù)據(jù)分組發(fā)送次數(shù)，NS和NT分別對(duì)應(yīng)節(jié)點(diǎn)自身產(chǎn)生并發(fā)送的數(shù)據(jù)分組次數(shù)和節(jié)點(diǎn)為其它節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組次數(shù)。仿真結(jié)果如圖3所示。

圖3 數(shù)據(jù)分組發(fā)送次數(shù)對(duì)比

由圖3可知，RBER算法的數(shù)據(jù)分組發(fā)送次數(shù)在各個(gè)場(chǎng)景低于ER算法，這是由于RBER算法引入節(jié)點(diǎn)緩存清理機(jī)制，刪除本地緩存中已經(jīng)到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組，減少了不必要的數(shù)據(jù)分組在網(wǎng)絡(luò)中的發(fā)送。

圖4 平均緩存占用對(duì)比

4.2.3 平均緩存占用

仿真結(jié)果如圖4所示。

由圖4可知，RBER算法的平均緩存占用在各個(gè)場(chǎng)景下都低于Epidemic算法。這是由于RBER算法引入節(jié)點(diǎn)緩存清理機(jī)制，刪除本地緩存中已經(jīng)到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)分組，減少了不必要的數(shù)據(jù)分組在網(wǎng)絡(luò)中的發(fā)送，減少這類分組在網(wǎng)絡(luò)中的傳播和其它節(jié)點(diǎn)的緩存占用。

[1] PELUSI L, PASSARELLA A, CONTI M, et al. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine, 2006, 44(11): 134-141.

[2] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Technical Report CS-200006, Duke University, 2000.

[3] Harras K A, Almeroth K C, Belding-royer E M. Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding in Sparse Mobile Networks[C]. Proceedings of the 4th International conference on networking. Waterloo: IEEE Press, 2005: 1180-1192.

[4] Yu H Z, Ma J F, Bian H. Message redundancy removal of multicopy routing in delay tolerant MANET[J]. The Journal of China Universities of Posts and Telecommunications, 2011, 18(1): 42-48.

[5] Lu X F, Hui P. An Energy-Efficient n-Epidemic Routing Protocol for Delay Tolerant Networks[A]. 2010 Fifth IEEE International Conference on Networking, Architecture, and Storage[C]. Macau, China, 2010: 341-347.

Kind of reduce buffer overhead Epidemic routing algorithm for opportunistic networks

ZUO Cheng-zhang, LIU Zhi-hu, SUN Xi-sheng, SUO Jian-wei
(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

To address the problem in opportunistic network that the existing epidemic-mechanism-based routing algorithms incur redundant communication overhead during the transmission of data packets, which is part of the data packets have already arrived at the destination nodes, but the data is still in the network storage and transmission, a kind of reduce buffer overhead Epidemic routing algorithm for opportunistic networks, called RBER was proposed. The algorithm based on SV information operation, to avoid redundant data takes up the cache. Theoretical analysis and simulation results show that the mechanism can reduce network overhead, redundant data packet sending and cache usage.

opportunistic networks; routing algorithm; buffer; clean

TP393

A

1008-5599（2014）02-0085-04

2014-01-01