主動編碼的機會網(wǎng)絡(luò)高效路由算法

孫建飛，高 媛，王淑敏

(中北大學(xué) 計算機與控制工程學(xué)院,太原 030051)

0 引言

機會網(wǎng)絡(luò)是不需要源節(jié)點和目的節(jié)點之間存在完整路徑，利用節(jié)點移動帶來的機會相遇實現(xiàn)網(wǎng)絡(luò)通信、時延和分裂可容忍的自組織網(wǎng)絡(luò)。網(wǎng)絡(luò)編碼是2000年由Ahlswed等提出，2005年之后許多國外學(xué)者開始研究無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼。COPE[1]利用機會偵聽和接收報告的方式最大化一次傳輸?shù)臄?shù)據(jù)包數(shù)量，但被動的編碼機制限制了網(wǎng)絡(luò)編碼提升網(wǎng)絡(luò)吞吐量的能力；CORE[2]中提出了轉(zhuǎn)發(fā)集的概念，每個節(jié)點單獨計算數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)先級，可同時得到網(wǎng)絡(luò)編碼和機會路由對無線網(wǎng)絡(luò)所帶來的增益；MORE[3]采用隨機線性編碼的方式提高投遞率，但提升網(wǎng)絡(luò)吞吐量能力有限，網(wǎng)絡(luò)延時大；PACE[4]中節(jié)點每次都著眼于提升節(jié)點附近區(qū)域中的編碼增益，并增加了轉(zhuǎn)發(fā)延時有效的控制了碰撞的發(fā)生。王少園[5]等提出COPE改進(jìn)算法，以鏈路質(zhì)量度量作為備選轉(zhuǎn)發(fā)節(jié)點集的選擇標(biāo)準(zhǔn)，在一定程度上提高了整體網(wǎng)絡(luò)的吞吐量，降低了數(shù)據(jù)端到端的時延。基于上述分析提出了ANCBCR算法。

1 ANCBCR算法

下面是算法的描述。

1.1 主動異或編碼

與COPE不同，節(jié)點Vi每次轉(zhuǎn)發(fā)數(shù)據(jù)時不是立即計算將符合條件的數(shù)據(jù)編碼后轉(zhuǎn)發(fā)給相應(yīng)的鄰居節(jié)點，而是通過等待一個時間段T，若在T內(nèi)偵聽到了新的鄰居節(jié)點，并將此節(jié)點加入本次計算，知道時間T到達(dá)將滿足條件數(shù)據(jù)包編碼轉(zhuǎn)發(fā)。編碼包計算方式如下：

（1）節(jié)點Vi要轉(zhuǎn)發(fā)數(shù)據(jù)時，通過偵聽到的鄰居信息計算出鄰居Vj的請求矢量Requestji，如式（1）：

假設(shè)Vi的緩存中儲存有n個數(shù)據(jù)包，且Vi的鄰居個數(shù)為m個，則可以得到一個m行n列請求矢量組成的矩陣M（如式（2）其中列為節(jié)點Vi中數(shù)據(jù)包的ID，行為Vi的鄰居節(jié)點ID）。

（2）計算符合編碼條件的數(shù)據(jù)包。

將B中值不為0的個數(shù)記為b，C中值不為0的個數(shù)記為c，分三種情況：

所以最大編碼包數(shù)為b-max(B)。

接著將B中值大于1的位置對應(yīng)的列的值全部置為0，重新計算B、C，利用B、C得到滿足編碼條件的數(shù)據(jù)包進(jìn)行異或編碼后多播給相應(yīng)的鄰居節(jié)點。

1.2 數(shù)據(jù)包發(fā)送順序優(yōu)化

在時間T到達(dá)之后，轉(zhuǎn)發(fā)節(jié)點Vi首先查找自己緩存中是否存在目的節(jié)點為鄰居的數(shù)據(jù)包，若存在則優(yōu)先轉(zhuǎn)發(fā)；接著將多個節(jié)點要求轉(zhuǎn)發(fā)的數(shù)據(jù)包多播給相應(yīng)節(jié)點；最后，計算得到滿足條件的數(shù)據(jù)包編碼后多播給相應(yīng)節(jié)點。至此，一次完整轉(zhuǎn)發(fā)結(jié)束。

1.3 節(jié)點數(shù)據(jù)緩存管理

節(jié)點Vi收到鄰居Vj發(fā)來的SVj后計算出Vi和鄰居Vj都存在的數(shù)據(jù)分組Commonji，計算方法如式（6）：

接下來節(jié)點Vi遍歷Commonji，查找目的節(jié)點為Vj的數(shù)據(jù)分組，存在則從本地緩存中將其刪除，并將其寫入已到達(dá)目的節(jié)點數(shù)據(jù)索引中，達(dá)到清理緩存和減少網(wǎng)絡(luò)開銷的目的。

1.4 閾值T的確定

T為延遲編碼計算的最長時間，如式（7）：

其中Ti(i=1,2,....m)為Vi的m個鄰居與Vi處于通信范圍內(nèi)的時間，如式（8）：

其中R為通信半徑，d為節(jié)點間距，V為節(jié)點速度，m鄰居個數(shù)，t為發(fā)送單個數(shù)據(jù)包所用的時間，如式（9）：

其中M為數(shù)據(jù)包大小，V0為數(shù)據(jù)傳輸速率，t0為傳輸數(shù)據(jù)包Head字段所需的時間。

2 仿真與分析

2.1 實驗平臺搭建與參數(shù)設(shè)置

本文采用ONE(Opportunistic Network Environment)仿真軟件平臺，采用(Shortest Path Map Based Movement)為移動模型。

2.2 仿真結(jié)果分析

為了驗證本文算法的性能，通過數(shù)據(jù)分組端到端平均時延和網(wǎng)絡(luò)吞吐量這些指標(biāo)與COPE算法和COPE改進(jìn)算法進(jìn)行比較，通過實驗數(shù)據(jù)對網(wǎng)絡(luò)性能進(jìn)行分析。

圖1 端到端數(shù)據(jù)傳輸時延

（1）端到端數(shù)據(jù)傳輸時延。由圖1可知，隨著網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)的增加，3種算法的時延均呈現(xiàn)下降趨勢，這是因為網(wǎng)絡(luò)中數(shù)據(jù)流的增加使網(wǎng)絡(luò)中的數(shù)據(jù)包有了更多的轉(zhuǎn)發(fā)機會。尤其，本算法較另外兩種算法的時延有明顯下降，平均下降1200s，這是因為數(shù)據(jù)包發(fā)送順序優(yōu)化機制有益于增加數(shù)據(jù)轉(zhuǎn)發(fā)機會。另外，COPE和COPE的改進(jìn)算法分別在數(shù)據(jù)流個數(shù)為70和60的時候端到端時延有上升趨勢，而本算法卻保持在了接近2500s的穩(wěn)定狀態(tài)，這是因為本算法引入了緩存清理機制克服了因緩存資源不足而造成丟包進(jìn)而引發(fā)數(shù)據(jù)分組延遲接收的問題。

圖2 網(wǎng)絡(luò)吞吐量

（2）網(wǎng)絡(luò)吞吐量。網(wǎng)絡(luò)吞吐量是指單位時間內(nèi)流經(jīng)整個網(wǎng)絡(luò)的數(shù)據(jù)量。從圖2可以看出，在發(fā)送數(shù)據(jù)流小于60kb/s時，三種算法的網(wǎng)絡(luò)吞吐量均有所提升，兩種改進(jìn)算法均大于COPE算法，這是因為COPE改進(jìn)算法增加了新的判斷機制，而本算法引入了主動編碼機制并又花了數(shù)據(jù)的轉(zhuǎn)發(fā)順序，增加了轉(zhuǎn)發(fā)機會。在發(fā)送數(shù)據(jù)流大于60kb/s后，由于網(wǎng)絡(luò)擁塞，三種算法的吞吐量均有下降趨勢，但由于本算法引入了SV緩存清理機制，所以吞吐量下降趨勢較另外兩種算法明顯平緩的多，并且在發(fā)送數(shù)據(jù)流為200kb/s時仍能保持在25kb/s以上。

3 結(jié)束語

本文提出的基于主動編碼的機會路由算法引入了主動異或編碼和多播，充分利用節(jié)點的每次相遇機會，提高了整體網(wǎng)絡(luò)吞吐量和數(shù)據(jù)分組平均端到端時延，同時增加了緩存清理機制進(jìn)一步提升了該算法的性能。接下來的工作將致力通過機會網(wǎng)絡(luò)中節(jié)點間相互協(xié)作，合理的調(diào)度數(shù)據(jù)的傳輸順序來提升區(qū)域網(wǎng)絡(luò)吞吐量的問題。

[1]KATTI S, RAHUL H, HU W, et al. XORs in the air: Practical wireless network coding [C]. Protocols for Computer Communications , 2006:243-254.

[2]YAN Y, ZHANG B, MOUFLAH H T, et al.Practical codingaware mechanism for oppor- tunistic routing in wireless mesh networks[C]. Proceedings of IEEE International Conference on Communications, 2008: 2871-2876

[3]CHACHULSKI S, JENNINGS M, KATTI S, etal. Trading structure for randomness in wireless opportunistic routing[C].Proceedings of Conference on Applications,2007: 169-180

[4]YAN Y, ZHAO Z, ZHANG B, et al. Mechanism for maximizing area-centric coding gains in wireless multihop networks[C].Proceedings of IEEE International Conference on Commun-ications, 2009, 14-18

[5]王少園，吳蒙.基于COPE協(xié)議改進(jìn)的網(wǎng)絡(luò)編碼感知機會路由算法[J].電信快報,2013:41-44.