0 引言

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

    編碼感知^[2]是指在路由建立過程中把編碼機會考慮進(jìn)去，通過主動探索、創(chuàng)造并利用網(wǎng)絡(luò)中潛在的編碼機會，使網(wǎng)絡(luò)的吞吐量得到進(jìn)一步的提高。將編碼感知與路由算法相結(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)并利用更多的編碼機會已成為科研人員研究的重點。

    文獻(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，但它需要維護(hù)兩跳范圍內(nèi)所有節(jié)點緩存隊列中的數(shù)據(jù)包信息，編碼帶來的網(wǎng)絡(luò)開銷較大。文獻(xiàn)[6]根據(jù)節(jié)點間的社會屬性設(shè)計了一種編碼節(jié)點狀態(tài)感知的容遲網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)機制，該機制減少了網(wǎng)絡(luò)資源開銷，改善了網(wǎng)絡(luò)資源利用率。文獻(xiàn)[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é)議的性能進(jìn)行了理論分析和仿真驗證。

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)致到達(dá)的編碼包不能成功解碼，浪費網(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í)行步驟進(jìn)行詳細(xì)介紹。

2.1 編碼機會的判斷

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

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

    (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可進(jìn)行編碼發(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；//進(jìn)行編碼，獲得編碼包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ù)包用于解碼，提高了編碼包的解碼成功率，進(jìn)而提高了網(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ā)遠(yuǎn)離目的節(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é)點來進(jìn)行數(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ù)包高效緩存機制進(jìn)行處理。

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

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

    本文采用網(wǎng)絡(luò)仿真軟件OPNET 14.5版本搭建仿真平臺，對NAOFP協(xié)議與ExCAR協(xié)議的性能進(jìn)行分析與比較。實驗場景是在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é)議在進(jìn)行數(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ò)吞吐量、平均端到端時延、編碼包的解碼成功率等方面的性能均得到了有效的改善。

參考文獻(xiàn)

[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)