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

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

機會網(wǎng)絡中一種低緩存占用的Epidemic路由算法

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

（重慶郵電大學移動通信技術重慶市重點實驗室，重慶 400065）

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

機會網(wǎng)絡；路由算法；緩存；清理

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

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

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

1 相關工作

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

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

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

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

2 Epidemic路由算法

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

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

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

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

通過上述運算，節(jié)點Y獲得節(jié)點X緩存中有而本身沒有的數(shù)據(jù)分組信息，并向節(jié)點X發(fā)送RequestX控制分組來請求這些數(shù)據(jù)分組。

（3）節(jié)點X收到RequestX后，向節(jié)點Y發(fā)送對應的請求分組。

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

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

3 RBER路由算法

RBER算法通過對SV信息運算進行節(jié)點緩存清理的具體操作如下。

當節(jié)點X收到節(jié)點Y發(fā)送的SVY，進行如下位運算：

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

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

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

（1）當節(jié)點X收到節(jié)點Y發(fā)送的SVY，進行如下位運算：

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

（2）節(jié)點X之后做如下位運算：

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

4 仿真結果及分析

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

4.1 仿真場景設置

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

4.2 仿真結果分析

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

4.2.1 網(wǎng)絡開銷

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

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

圖2 網(wǎng)絡開銷對比

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

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

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

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

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

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

圖4 平均緩存占用對比

4.2.3 平均緩存占用

仿真結果如圖4所示。

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

[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