0 引言

    2000年，AHLSWEDE R等人首次提出了網絡編碼^[1]的理論。網絡編碼允許中間節點對數據進行編碼后轉發，增加了單次轉發的信息量。相比于傳統的傳輸方式可以減少信息的傳輸次數，提高網絡吞吐量，實現理論上的最大傳輸容量。

    編碼感知^[2]是指在路由建立過程中把編碼機會考慮進去，通過主動探索、創造并利用網絡中潛在的編碼機會，使網絡的吞吐量得到進一步的提高。將編碼感知與路由算法相結合已成為數據轉發策略的一個重要研究方向。隨著對無線多跳網絡中網絡編碼路由協議研究的不斷深入，學者們發現現有的路由協議中編碼機會得不到充分的利用，并沒有讓網絡編碼的性能得到最大限度的利用。在數據轉發過程中，如何發現并利用更多的編碼機會已成為科研人員研究的重點。

    文獻[3]由KATTI S等人首次提出了適用于無線 mesh的網絡編碼路由協議COPE。在COPE協議中節點利用機會監聽和網絡編碼減少了數據傳輸次數，提高了網絡吞吐量。但節點需要周期性地廣播控制報文信息，且只能探索兩跳范圍內的編碼機會，限制了網絡編碼的性能。CORE^[4]與CORMEN^[5]是將編碼感知與機會式路由相結合，規定在轉發節點集內選擇具有更多編碼機會的節點優先轉發數據包，這樣在一次傳輸過程中更加有效地利用網絡中的編碼機會。該類協議采用的編碼機制也是COPE，但它需要維護兩跳范圍內所有節點緩存隊列中的數據包信息，編碼帶來的網絡開銷較大。文獻[6]根據節點間的社會屬性設計了一種編碼節點狀態感知的容遲網絡數據轉發機制，該機制減少了網絡資源開銷，改善了網絡資源利用率。文獻[7]提出了一種適用于無線mesh網絡的編碼感知且負載均衡的多播路由，在編碼感知的基礎上增加了對路徑上所有節點通信密集程度與網絡擁塞程度的考慮。

    充分考慮節點編碼機會的編碼感知路由協議^[8] ExCAR能有效地發現多跳范圍的編碼機會，但該協議在節點編碼機會計算時可能存在誤判以及在轉發節點集內選擇最優編碼節點時需要交換大量的數據包緩存信息，會導致較大的時延和網絡開銷。為解決ExCAR協議存在的問題，本文提出了一種適用于多跳無線網絡的節點編碼感知機會轉發路由協議——NAOFP，并對該路由協議的性能進行了理論分析和仿真驗證。

1 ExCAR協議問題描述

    經深入研究，發現ExCAR協議存在以下缺陷：

    （1）原協議為了判斷數據包在中間節點的編碼機會時，將發送節點的所有一跳鄰居節點的ID全部附加到即將發送的數據包上，沒有考慮實際的無線網絡鏈路存在不穩定性，在判斷編碼機會時可能會造成誤判，導致到達的編碼包不能成功解碼，浪費網絡資源。

    （2）原協議在轉發節點集內選擇轉發節點時，需要節點計算自己的編碼機會，而且集合內的各個節點周期性地轉發各自擁有的數據包信息和偵聽緩存的數據包信息來計算其他節點的編碼機會，最后通過與其他節點的比較選擇出最佳轉發節點。在此過程中，每個節點的傳輸開銷和計算開銷比較大，同時由于計算轉發集內其他節點的編碼機會也會增加數據包的處理時延。

    （3）原協議在偵聽緩存時把附加信息packet holders也一并放入緩存中，但這些packet holders附加信息對解碼不起作用，且占據了一定的緩存空間。

2 NAOFP協議

    本文提出的NAOFP協議通過引入基于偵聽概率的附加ID信息添加、最優轉發節點選擇、數據包的高效緩存3個新的機制來解決ExCAR協議存在的上述3個問題。下面對NAOFP協議的編碼機會的判斷、提出的新機制以及該協議的具體執行步驟進行詳細介紹。

2.1 編碼機會的判斷

2.1.1 基于偵聽概率的附加ID信息添加機制

    節點轉發數據包時，將該節點的ID和一跳鄰居節點的ID添加在即將發送的數據包頭部。為保證編碼包的解碼成功率，在添加附加ID時需要將發送節點與其鄰居節點的鏈路情況考慮進來。該機制具體步驟如下：

    (1)計算。依次計算發送節點S與其各個一跳鄰居節點n_i的偵聽概率P(s，n_i)：

其中，P(s，n_i)為鄰居節點n_i成功偵聽到節點S發送數據包的概率，n_i為發送節點S的第i個鄰居節點，P_f(s，n_i)為節點S到其鄰居節點n_i的鏈路正向丟包率；

    (2)判斷。依次判斷每個鄰居節點的偵聽概率P(s，n_i)與閾值P_th的大小；

    (3)添加。如果某一鄰居節點的P(s，n_i)比閾值P_th大，說明S到該鄰居節點n_i的鏈路狀況良好，則將此鄰居節點的ID附加到待發數據包p的頭部。

    如圖1所示，節點S₁需發送數據包p到目的節點D₁，節點S₂需發送數據包q到目的節點D₂。當S₁在發送數據包p前，利用基于偵聽概率的附加ID信息添加機制將符合要求的節點ID添加到數據包P的頭部，假設其鄰居節點R₁、R₂、D₂的偵聽概率均滿足上述要求，則數據包p的附加ID信息的添加情況如圖2所示。

    在數據包相遇時，可由packet holders信息得知哪些節點已緩存了該數據包的備份。

2.1.2 編碼機會判斷規則

    數據包能在一起編碼的前提是目的節點已緩存了能用于解碼的數據包，保證編碼包在目的節點能成功解碼。本文利用附加ID信息來判斷數據包在編碼前目的節點是否已緩存了用于解碼的數據包。假設中間節點收到來自不同數據流的兩個數據包p、q，若同時滿足式(2)和式(3)成立，則數據包p、q可進行編碼發送。

2.2 最優轉發節點選擇機制

    轉發節點集內的節點各自計算本節點的編碼機會，然后各節點間只需通過交換各自的編碼機會次數選擇出次數最多的節點。

    假設轉發節點集內有x、y兩個節點，當收到帶有附加ID信息的數據包p時，從轉發節點集內選擇出最優轉發節點的具體步驟如下：

    第一步：轉發節點集內的每個節點各自計算編碼機會次數count，即節點x、y的發送隊列中能與數據包p一起編碼發送的數據包個數。以節點x為例，具體計算過程如下所示。

輸入：p ； //節點x收到帶有附加ID的數據包p

輸出：count(x) ； //節點x的輸出隊列中能與P一起編碼的數據包個數

Procedure：

count(x)=0；

    while(node x output queue !=Null)   {

    for(i=1；i<n；i++)   {

     //判斷是否滿足編碼機會判斷規則，其中pi表示節點

       x的輸出隊列中的第i個數據包

    If(Dest_p∈Setpi && Dest_pi∈Setp)   {

    pcode1=p⊕pi；//進行編碼，獲得編碼包pcode1

    Count(x) ++；//更新編碼包pcode1的附加信息

    Setpcode1=Setp∩Setpi；

    Dest_pcode1=Dest_p∪Dest_pi；

    pcode1 is stored to the buffer；

    remove pi from output queue；

    p=pcode1； }

    continue； }

    return  count(x)； }

    同理，節點y也可以通過上述過程計算出能與p一起編碼的數據包個數count(y)。

    第二步：轉發集內節點交換各自的編碼機會。此時，節點x知道count(y)的值，節點y知道count(x)的值；

    第三步：轉發節點集內的節點通過與其他節點的count值比較，如果發現自己的count值最大，則選為最優轉發節點。

2.3 數據包高效緩存機制

    由于無線鏈路的廣播特性，網絡中有數據發送時，位于該節點的鄰居節點能夠以一定的概率偵聽到該數據包并放入緩存中，用于編碼數據包的解碼。在NAOFP協議中，網絡中的節點偵聽到數據包時，去掉附加在數據包上的packet holders信息后放入緩存。由于去掉了packet holders附加信息，在節點緩存大小相同的情況下能夠緩存更多數量的數據包用于解碼，提高了編碼包的解碼成功率，進而提高了網絡的實際吞吐量。

2.4 NAOFP協議的執行步驟

    NAOFP協議各階段的具體執行步驟如下。

    （1）附加ID信息的添加

    當網絡中的節點有數據包要發送時，按照2.1.1節所述的基于偵聽概率的附加ID信息添加機制將該發送節點的ID和符合要求的鄰居節點ID添加在即將發送的數據包的頭部，用于編碼機會的判斷。

    （2）轉發節點集的選取

    在NAOFP協議中不預先使用指定的節點對數據包轉發，而是在數據包發送前預先選取多個節點作為數據包的潛在轉發節點，這些節點的集合即為轉發節點集。以下為轉發節點集內節點選取所必須滿足的條件：

    ①該節點必須是發送節點的下一跳鄰居節點；

    ②為了避免數據包的轉發遠離目的節點，該節點必須距離目的節點更近。本文使用ETX度量值來衡量，即轉發節點集內節點的ETX度量值要小于發送節點的ETX度量值；

    ③在轉發節點集內的節點必須能夠相互偵聽；

    ④轉發節點集選取節點的個數不應超過6個。

    （3）最優轉發節點的選擇

    將帶有附加ID信息的數據包發送到轉發節點集內的節點后，按照2.2節所述的最優轉發節點選擇機制，選擇出具有編碼機會數量最大的節點選作該數據包的下一跳轉發節點。如果轉發節點集內出現具有相同編碼機會次數的多個節點時，應選擇ETX度量值最小的節點來進行數據包的轉發。轉發集內的其他節點偵聽到該數據包被成功發送后，將該數據包從發送隊列中刪除。

    網絡中的節點偵聽到的數據包按照2.3節所述的數據包高效緩存機制進行處理。

3 仿真實驗及結果分析

3.1 仿真場景及參數設置

    本文采用網絡仿真軟件OPNET 14.5版本搭建仿真平臺，對NAOFP協議與ExCAR協議的性能進行分析與比較。實驗場景是在500 m×500 m的區域范圍內隨機分布15個無線節點，其中MAC層使用較為普遍的IEEE 802.11b標準協議。具體的仿真參數設置如表1所示。

3.2 仿真結果分析

3.2.1 網絡吞吐量

    如圖3所示，NAOFP協議的網絡吞吐量在不同的網絡負載下均高于ExCAR協議。這是由于NAOFP協議在進行數據包附加ID信息添加的過程中考慮了無線鏈路的不穩定性，發送節點與其鄰居節點的偵聽概率P(s，n_i)小于閾值P_th，則不將此鄰居節點的ID添加，這樣在目的節點保障了較高的解碼率，避免了編碼包不能成功解碼而造成的網絡資源浪費，從而使網絡吞吐量得到了有效的提高。

3.2.2 平均端到端時延

    如圖4所示，NAOFP協議的數據包平均端到端時延在不同的網絡負載下均低于ExCAR協議。這是因為NAOFP協議在轉發節點集內選擇編碼機會數量最大的節點時，并不需要節點間相互交換各自的數據包信息，也不需要計算其他節點的編碼機會次數，這樣減少了數據包在轉發節點的處理和等待時間，從而使網絡中的平均端到端時延得到明顯的降低。

3.2.3 編碼包的解碼成功率

    如圖5所示，NAOFP協議的編碼包的解碼成功率在不同的網絡負載下均高于ExCAR協議。這是因為在NAOFP協議的步驟一中采用了基于偵聽概率的附加ID信息添加機制，保障了編碼包的可解性。另外，節點在偵聽緩存網絡中的數據包時，將數據包的附加信息去掉后緩存，這樣在緩存大小一定的情況下可以緩存更多的數據包用于解碼，從而使網絡中編碼包的解碼成功率得到有效的提高。

4 結論

    本文針對ExCAR路由協議在無線鏈路不穩定的情況下，節點在計算編碼機會時存在誤判，以及在選擇最佳編碼節點時需要交換大量的數據包緩存信息，提出了一種節點編碼感知的機會轉發路由協議NAOFP，且在該協議中引入了基于偵聽概率的附加ID信息添加機制和最優轉發節點選擇機制。仿真實驗結果表明，與ExCAR路由協議相比，NAOFP協議在網絡吞吐量、平均端到端時延、編碼包的解碼成功率等方面的性能均得到了有效的改善。

參考文獻

[1] AHLSWEDE R，CAI N，LI S，et al.Network information flow[J].IEEE Transactions on Information Theory，2000，46(4)：1204-1216.

[2] CHEN C，DONG C，MAO Y F，et al.Survey on network-coding-aware routing in wireless network[J].Journal of Software，2015，26(1)：82-97.

[3] KATTI S，RAHUL H，HU W J，et al.XORs in the air: practical wireless network coding[C].ACM SIGCOMM，Pisa，Italy，2006：243-254.

[4] YAN Y，ZHANG B X，ZHENG J.CORE：A coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEE Wireless Communications，2010，17(3)：96-103.

[5] ISLAM J，SINGH P K.CORMEN：Coding-aware opportunistic routing in wireless mesh network[J].Journal of Computing，2010，2(6)：71-77.

[6] 王汝言，樓芃雯，樊思龍，等.容遲網絡編碼節點狀態感知的數據轉發策略[J].重慶郵電大學學報(自然科學版)，2013，25(2)：215-220.

[7] 沈小建，陳志剛，劉立.無線mesh網絡中編碼感知且負載均衡的多播路由[J].通信學報，2015，36(4)：89-95.

[8] 趙蘊龍，王博識，張凱，等.充分考慮節點編碼機會的編碼感知路由協議[J].應用科學學報，2014，32(1)：7-12.

作者信息：

姚玉坤，王  宇，呂盼成

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