0 引言

    2000年,，AHLSWEDE R等人首次提出了網(wǎng)絡(luò)編碼^[1]的理論。網(wǎng)絡(luò)編碼允許中間節(jié)點對數(shù)據(jù)進行編碼后轉(zhuǎn)發(fā),，增加了單次轉(zhuǎn)發(fā)的信息量。相比于傳統(tǒng)的傳輸方式可以減少信息的傳輸次數(shù),，提高網(wǎng)絡(luò)吞吐量,，實現(xiàn)理論上的最大傳輸容量。

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

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

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

1 ExCAR協(xié)議問題描述

    經(jīng)深入研究，發(fā)現(xiàn)ExCAR協(xié)議存在以下缺陷：

    （1）原協(xié)議為了判斷數(shù)據(jù)包在中間節(jié)點的編碼機會時,，將發(fā)送節(jié)點的所有一跳鄰居節(jié)點的ID全部附加到即將發(fā)送的數(shù)據(jù)包上,，沒有考慮實際的無線網(wǎng)絡(luò)鏈路存在不穩(wěn)定性，在判斷編碼機會時可能會造成誤判,，導(dǎo)致到達的編碼包不能成功解碼,，浪費網(wǎng)絡(luò)資源。

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

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

2 NAOFP協(xié)議

    本文提出的NAOFP協(xié)議通過引入基于偵聽概率的附加ID信息添加、最優(yōu)轉(zhuǎn)發(fā)節(jié)點選擇,、數(shù)據(jù)包的高效緩存3個新的機制來解決ExCAR協(xié)議存在的上述3個問題。下面對NAOFP協(xié)議的編碼機會的判斷,、提出的新機制以及該協(xié)議的具體執(zhí)行步驟進行詳細(xì)介紹,。

2.1 編碼機會的判斷

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

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

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

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

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

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

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

    在數(shù)據(jù)包相遇時,，可由packet holders信息得知哪些節(jié)點已緩存了該數(shù)據(jù)包的備份,。

2.1.2 編碼機會判斷規(guī)則

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

2.2 最優(yōu)轉(zhuǎn)發(fā)節(jié)點選擇機制

    轉(zhuǎn)發(fā)節(jié)點集內(nèi)的節(jié)點各自計算本節(jié)點的編碼機會，然后各節(jié)點間只需通過交換各自的編碼機會次數(shù)選擇出次數(shù)最多的節(jié)點,。

    假設(shè)轉(zhuǎn)發(fā)節(jié)點集內(nèi)有x,、y兩個節(jié)點,，當(dāng)收到帶有附加ID信息的數(shù)據(jù)包p時,，從轉(zhuǎn)發(fā)節(jié)點集內(nèi)選擇出最優(yōu)轉(zhuǎn)發(fā)節(jié)點的具體步驟如下：

    第一步：轉(zhuǎn)發(fā)節(jié)點集內(nèi)的每個節(jié)點各自計算編碼機會次數(shù)count，即節(jié)點x,、y的發(fā)送隊列中能與數(shù)據(jù)包p一起編碼發(fā)送的數(shù)據(jù)包個數(shù),。以節(jié)點x為例,，具體計算過程如下所示,。

輸入：p ； //節(jié)點x收到帶有附加ID的數(shù)據(jù)包p

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

Procedure：

count(x)=0,；

    while(node x output queue !=Null)   {

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

     //判斷是否滿足編碼機會判斷規(guī)則,，其中pi表示節(jié)點

       x的輸出隊列中的第i個數(shù)據(jù)包

    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),； }

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

    第二步：轉(zhuǎn)發(fā)集內(nèi)節(jié)點交換各自的編碼機會,。此時，節(jié)點x知道count(y)的值,，節(jié)點y知道count(x)的值,；

    第三步：轉(zhuǎn)發(fā)節(jié)點集內(nèi)的節(jié)點通過與其他節(jié)點的count值比較，如果發(fā)現(xiàn)自己的count值最大,，則選為最優(yōu)轉(zhuǎn)發(fā)節(jié)點,。

2.3 數(shù)據(jù)包高效緩存機制

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

2.4 NAOFP協(xié)議的執(zhí)行步驟

    NAOFP協(xié)議各階段的具體執(zhí)行步驟如下,。

    （1）附加ID信息的添加

    當(dāng)網(wǎng)絡(luò)中的節(jié)點有數(shù)據(jù)包要發(fā)送時，按照2.1.1節(jié)所述的基于偵聽概率的附加ID信息添加機制將該發(fā)送節(jié)點的ID和符合要求的鄰居節(jié)點ID添加在即將發(fā)送的數(shù)據(jù)包的頭部,，用于編碼機會的判斷,。

    （2）轉(zhuǎn)發(fā)節(jié)點集的選取

    在NAOFP協(xié)議中不預(yù)先使用指定的節(jié)點對數(shù)據(jù)包轉(zhuǎn)發(fā)，而是在數(shù)據(jù)包發(fā)送前預(yù)先選取多個節(jié)點作為數(shù)據(jù)包的潛在轉(zhuǎn)發(fā)節(jié)點,，這些節(jié)點的集合即為轉(zhuǎn)發(fā)節(jié)點集,。以下為轉(zhuǎn)發(fā)節(jié)點集內(nèi)節(jié)點選取所必須滿足的條件：

    ①該節(jié)點必須是發(fā)送節(jié)點的下一跳鄰居節(jié)點；

    ②為了避免數(shù)據(jù)包的轉(zhuǎn)發(fā)遠離目的節(jié)點,，該節(jié)點必須距離目的節(jié)點更近。本文使用ETX度量值來衡量,，即轉(zhuǎn)發(fā)節(jié)點集內(nèi)節(jié)點的ETX度量值要小于發(fā)送節(jié)點的ETX度量值,；

    ③在轉(zhuǎn)發(fā)節(jié)點集內(nèi)的節(jié)點必須能夠相互偵聽；

    ④轉(zhuǎn)發(fā)節(jié)點集選取節(jié)點的個數(shù)不應(yīng)超過6個,。

    （3）最優(yōu)轉(zhuǎn)發(fā)節(jié)點的選擇

    將帶有附加ID信息的數(shù)據(jù)包發(fā)送到轉(zhuǎn)發(fā)節(jié)點集內(nèi)的節(jié)點后,，按照2.2節(jié)所述的最優(yōu)轉(zhuǎn)發(fā)節(jié)點選擇機制，選擇出具有編碼機會數(shù)量最大的節(jié)點選作該數(shù)據(jù)包的下一跳轉(zhuǎn)發(fā)節(jié)點,。如果轉(zhuǎn)發(fā)節(jié)點集內(nèi)出現(xiàn)具有相同編碼機會次數(shù)的多個節(jié)點時,，應(yīng)選擇ETX度量值最小的節(jié)點來進行數(shù)據(jù)包的轉(zhuǎn)發(fā),。轉(zhuǎn)發(fā)集內(nèi)的其他節(jié)點偵聽到該數(shù)據(jù)包被成功發(fā)送后，將該數(shù)據(jù)包從發(fā)送隊列中刪除,。

    網(wǎng)絡(luò)中的節(jié)點偵聽到的數(shù)據(jù)包按照2.3節(jié)所述的數(shù)據(jù)包高效緩存機制進行處理,。

3 仿真實驗及結(jié)果分析

3.1 仿真場景及參數(shù)設(shè)置

    本文采用網(wǎng)絡(luò)仿真軟件OPNET 14.5版本搭建仿真平臺，對NAOFP協(xié)議與ExCAR協(xié)議的性能進行分析與比較,。實驗場景是在500 m×500 m的區(qū)域范圍內(nèi)隨機分布15個無線節(jié)點,，其中MAC層使用較為普遍的IEEE 802.11b標(biāo)準(zhǔn)協(xié)議。具體的仿真參數(shù)設(shè)置如表1所示,。

3.2 仿真結(jié)果分析

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

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

3.2.2 平均端到端時延

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

3.2.3 編碼包的解碼成功率

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

4 結(jié)論

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

參考文獻

[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] 王汝言,，樓芃雯，樊思龍,，等.容遲網(wǎng)絡(luò)編碼節(jié)點狀態(tài)感知的數(shù)據(jù)轉(zhuǎn)發(fā)策略[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版),，2013，25(2)：215-220.

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

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

作者信息：

姚玉坤,，王  宇,，呂盼成

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