主動編碼的機會網絡高效路由算法

孫建飛，高 媛，王淑敏

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

0 引言

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

1 ANCBCR算法

下面是算法的描述。

1.1 主動異或編碼

與COPE不同，節點Vi每次轉發數據時不是立即計算將符合條件的數據編碼后轉發給相應的鄰居節點，而是通過等待一個時間段T，若在T內偵聽到了新的鄰居節點，并將此節點加入本次計算，知道時間T到達將滿足條件數據包編碼轉發。編碼包計算方式如下：

（1）節點Vi要轉發數據時，通過偵聽到的鄰居信息計算出鄰居Vj的請求矢量Requestji，如式（1）：

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

（2）計算符合編碼條件的數據包。

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

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

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

1.2 數據包發送順序優化

在時間T到達之后，轉發節點Vi首先查找自己緩存中是否存在目的節點為鄰居的數據包，若存在則優先轉發；接著將多個節點要求轉發的數據包多播給相應節點；最后，計算得到滿足條件的數據包編碼后多播給相應節點。至此，一次完整轉發結束。

1.3 節點數據緩存管理

節點Vi收到鄰居Vj發來的SVj后計算出Vi和鄰居Vj都存在的數據分組Commonji，計算方法如式（6）：

接下來節點Vi遍歷Commonji，查找目的節點為Vj的數據分組，存在則從本地緩存中將其刪除，并將其寫入已到達目的節點數據索引中，達到清理緩存和減少網絡開銷的目的。

1.4 閾值T的確定

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

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

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

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

2 仿真與分析

2.1 實驗平臺搭建與參數設置

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

2.2 仿真結果分析

為了驗證本文算法的性能，通過數據分組端到端平均時延和網絡吞吐量這些指標與COPE算法和COPE改進算法進行比較，通過實驗數據對網絡性能進行分析。

圖1 端到端數據傳輸時延

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

圖2 網絡吞吐量

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

3 結束語

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

[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協議改進的網絡編碼感知機會路由算法[J].電信快報,2013:41-44.