充分考慮節(jié)點編碼機會的編碼感知路由協(xié)議

趙蘊龍， 王博識， 張 凱， 董 釗， 張 磊

1.哈爾濱工程大學計算機科學與技術(shù)學院，哈爾濱150001

2.哈爾濱工程大學信息與通信工程學院，哈爾濱150001

網(wǎng)絡編碼理論[1]被譽為21世紀信息傳輸領(lǐng)域的重大突破，它打破了對網(wǎng)絡中的數(shù)據(jù)處理只能通過傳統(tǒng)的“存儲-轉(zhuǎn)發(fā)”的方式，挖掘數(shù)據(jù)流的編碼機會并對數(shù)據(jù)進行編碼，從而達到了提升網(wǎng)絡吞吐量及均衡網(wǎng)絡負載等目的.

網(wǎng)絡中目的節(jié)點能成功地將發(fā)送給它的已編碼的數(shù)據(jù)包解碼是實際應用網(wǎng)絡編碼理論的先決條件，因為只有可以解碼的編碼操作才具有意義.作為網(wǎng)絡編碼技術(shù)在通信網(wǎng)絡中應用的不可或缺的條件，編碼機會是指在某一節(jié)點處可對兩條或多條數(shù)據(jù)流進行編碼操作的可能性.編碼機會越多則表明對數(shù)據(jù)流進行編碼的操作就越多.在網(wǎng)絡編碼理論研究中，在多大程度上使用網(wǎng)絡編碼技術(shù)提高網(wǎng)絡性能的問題最終也可歸結(jié)為在多大程度上發(fā)現(xiàn)網(wǎng)絡編碼機會的問題.

文獻[2]提出了一種可以發(fā)現(xiàn)更多網(wǎng)絡編碼機會的算法ExCODE，充分利用了無線鏈路鄰居節(jié)點間互相共享信道這一性質(zhì)和無線鏈路的廣播特性，通過在傳輸?shù)臄?shù)據(jù)包中添加一些額外的數(shù)據(jù)包歷經(jīng)的路徑信息，使得下游路徑中的所有節(jié)點可以得知網(wǎng)絡中哪些節(jié)點暫存著當前數(shù)據(jù)包的備份.利用這些信息可發(fā)現(xiàn)存在于節(jié)點中數(shù)據(jù)流間的所有編碼機會.該算法將節(jié)點編碼機會的尋找范圍擴大到n跳網(wǎng)絡，突破了文獻[3]提出的COPE協(xié)議所能探知的編碼機會范圍，且在網(wǎng)絡節(jié)點間不必進行信息交換，因為所有的網(wǎng)絡節(jié)點只需隨時探測信道通信狀況緩存?zhèn)陕牭降臄?shù)據(jù)即可.

文獻[3]提出了一種可以獲取無線網(wǎng)絡的某個節(jié)點在其一跳距離內(nèi)所有編碼機會的COPE協(xié)議.該協(xié)議對傳統(tǒng)的網(wǎng)絡體系結(jié)構(gòu)進行重新定義，并在網(wǎng)絡層和數(shù)據(jù)鏈路層之間增加編碼層進行網(wǎng)絡編碼服務.網(wǎng)絡中每個節(jié)點及其一跳鄰居節(jié)點各自分享自己所接收到的數(shù)據(jù)分組信息.節(jié)點根據(jù)這些數(shù)據(jù)信息對那些可以編碼的數(shù)據(jù)包進行編碼處理，以確定被編碼數(shù)據(jù)包的轉(zhuǎn)發(fā)路徑.

文獻[4]提出的CORE協(xié)議要求多跳無線網(wǎng)絡中的節(jié)點必須先獲得所有可能的下一跳節(jié)點作為多播傳輸選擇的節(jié)點集合，并傳輸數(shù)據(jù)分組；接著由轉(zhuǎn)發(fā)集里的節(jié)點根據(jù)本地獲取的信息計算編碼機會數(shù)量，挑選編碼機會數(shù)量最高的節(jié)點對數(shù)據(jù)進行編碼并轉(zhuǎn)發(fā)編碼后的數(shù)據(jù).文獻[5]提出了一個按需的分布式編碼感知多播路由協(xié)議DCAR，在源節(jié)點與目的節(jié)點之間發(fā)現(xiàn)有效路徑的同時考慮了網(wǎng)絡阻塞狀況和編碼機會等諸多因素，并檢測這些路徑潛在的編碼可能性，從而選擇最佳的轉(zhuǎn)發(fā)路徑進行數(shù)據(jù)傳輸.

文獻[6]提出了基于多跳模型編碼結(jié)構(gòu)數(shù)據(jù)流間的一般性編碼條件，包括兩數(shù)據(jù)流和多數(shù)據(jù)流的情況，并證明了其有效性.文獻[7]進一步分析了確保目的節(jié)點可解碼的一般性編碼條件，并提出了一種新穎的編碼感知路由算法FORM(ride-oriented routing metric).

本文將文獻[2]的研究成果與現(xiàn)有的編碼感知路由協(xié)議相結(jié)合，并對后者進行改進，使得數(shù)據(jù)包轉(zhuǎn)發(fā)節(jié)點集中的節(jié)點能夠計算出其他節(jié)點中的所有編碼機會，進而判定最佳轉(zhuǎn)發(fā)節(jié)點，提高網(wǎng)絡性能.

現(xiàn)有的編碼感知路由協(xié)議并沒有充分考慮節(jié)點中的所有編碼機會，于是本文提出一種基于ExCODE算法[2]的編碼感知路由協(xié)議ExCAR，將數(shù)據(jù)包的路由選擇過程分為以下4個步驟：

步驟1 數(shù)據(jù)包額外信息的追加.在到來的所有數(shù)據(jù)包中添加額外的路徑節(jié)點ID信息.

步驟2 轉(zhuǎn)發(fā)節(jié)點集的選擇，為到來的數(shù)據(jù)包選擇可能的下一跳轉(zhuǎn)發(fā)節(jié)點集合.

步驟3 最佳編碼節(jié)點選擇.從轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點集合中選取一個最佳編碼節(jié)點.

步驟4 基于優(yōu)先級的轉(zhuǎn)發(fā).首先依次詳細敘述算法執(zhí)行的各個步驟，然后分析其特點和吞吐量性能，最后利用網(wǎng)絡仿真工具NS2對所提出的算法進行仿真.

1 數(shù)據(jù)包額外信息的添加

ExCAR協(xié)議首先將網(wǎng)絡中的某些節(jié)點ID信息增添到即將發(fā)送的數(shù)據(jù)包內(nèi)，分別為信源節(jié)點ID、信源節(jié)點下一跳節(jié)點ID、數(shù)據(jù)傳輸路徑上的所有中間節(jié)點ID、所有數(shù)據(jù)包轉(zhuǎn)發(fā)路徑的節(jié)點的一跳鄰居節(jié)點ID.在此假定網(wǎng)絡中的所有鏈路是理想態(tài)的，每個節(jié)點都能以概率1偵聽到所有其一跳鄰居節(jié)點發(fā)出的數(shù)據(jù)，且在一定時間內(nèi)緩存它所偵聽到的數(shù)據(jù)包.

假如源節(jié)點E產(chǎn)生原始數(shù)據(jù)包q，并將q發(fā)送到目的節(jié)點F.同時，數(shù)據(jù)包p將從源節(jié)點A發(fā)送到目的節(jié)點C.當這兩個節(jié)點分別將其所發(fā)送數(shù)據(jù)包轉(zhuǎn)發(fā)給下一跳節(jié)點時，無線網(wǎng)絡以廣播的方式傳輸數(shù)據(jù)，使得原始數(shù)據(jù)包p和q分別被A節(jié)點和E節(jié)點的下一跳節(jié)點偵聽并暫存，成為數(shù)據(jù)包備份信息的擁有者.這些節(jié)點組成了一個集合，見表1.ExCAR算法執(zhí)行的第1步是將表1所示的信息分別追加到數(shù)據(jù)包p和q中，使傳輸路徑的下游節(jié)點知曉在哪些節(jié)點中暫存著當前數(shù)據(jù)包的備份，為下一步的編碼機會計算和最佳編碼節(jié)點選擇提供依據(jù).

表1 可偵聽到當前數(shù)據(jù)包的節(jié)點列表Table 1 Node list that can overhear the packet

為了使數(shù)據(jù)包接收節(jié)點獲取哪些節(jié)點已經(jīng)監(jiān)聽了此包，當網(wǎng)絡中一個節(jié)點接收到某數(shù)據(jù)包時，ExCAR協(xié)議就將這個節(jié)點的ID信息增添到數(shù)據(jù)包內(nèi)，以便其他節(jié)點再接收到這個數(shù)據(jù)包時可以獲取已經(jīng)保存了這個數(shù)據(jù)包的節(jié)點編號.數(shù)據(jù)包的傳輸每經(jīng)過一個節(jié)點，就會將該節(jié)點及其所有一跳鄰居節(jié)點的信息添加至該數(shù)據(jù)包中，如圖1所示.

圖1 多節(jié)點網(wǎng)絡模型Figur e 1 Network model with multi-node

額外信息僅僅包括轉(zhuǎn)發(fā)節(jié)點及其鄰居節(jié)點的ID信息，故信息量非常小，所產(chǎn)生的額外存儲開銷和傳輸帶寬開銷也非常小，故與所傳輸數(shù)據(jù)包的信息量相比幾乎可以忽略不計；另外，關(guān)于額外增加的計算開銷方面，由于常規(guī)協(xié)議中每個節(jié)點都會維護一張簡單的鄰居節(jié)點列表，本文算法僅將已有的鄰居節(jié)點信息追加到轉(zhuǎn)發(fā)數(shù)據(jù)包中，而不涉及其他任何額外的復雜計算和處理過程，故額外計算開銷也可以忽略.

2 轉(zhuǎn)發(fā)節(jié)點集選擇

當無線網(wǎng)絡中的節(jié)點發(fā)送數(shù)據(jù)時，先根據(jù)當前網(wǎng)絡的實際情況挑選一些節(jié)點作為數(shù)據(jù)的下一個轉(zhuǎn)發(fā)節(jié)點.因為無線網(wǎng)絡以廣播方式傳播數(shù)據(jù)，距離當前節(jié)點為一跳的鄰居節(jié)點均能轉(zhuǎn)發(fā)數(shù)據(jù)，所以可將這些節(jié)點作為當前數(shù)據(jù)流可能的下一跳轉(zhuǎn)發(fā)節(jié)點集.

轉(zhuǎn)發(fā)節(jié)點集的選擇是當前節(jié)點在發(fā)送數(shù)據(jù)之前最先開始進行的工作.首先，當前節(jié)點的下一跳轉(zhuǎn)發(fā)節(jié)點集合中的節(jié)點必須是當前節(jié)點直達的下一跳節(jié)點；其次，為了使后續(xù)轉(zhuǎn)發(fā)節(jié)點集合中每個節(jié)點分別計算其余轉(zhuǎn)發(fā)節(jié)點的編碼機會，需要集合中節(jié)點相互交換彼此已經(jīng)緩存的報文信息，所以被選入集合的節(jié)點必須滿足能監(jiān)聽到集合中其他節(jié)點的條件.除此之外，可以根據(jù)不同策略需要，增加轉(zhuǎn)發(fā)節(jié)點選擇的額外條件，如轉(zhuǎn)發(fā)節(jié)點距離目標節(jié)點的距離、節(jié)點剩余能量、鏈路狀態(tài)等.

在如圖2所示的網(wǎng)絡中，數(shù)據(jù)包p為源節(jié)點A將要發(fā)送到目的節(jié)點C的數(shù)據(jù)包，q為源節(jié)點E準備發(fā)送到目的節(jié)點F的數(shù)據(jù)包.在發(fā)送數(shù)據(jù)包p和q前，首先要確定轉(zhuǎn)發(fā)節(jié)點集合.從圖2中可以看到，G、C、D三個節(jié)點都為E節(jié)點可直達的下一跳節(jié)點，B、D、F三個節(jié)點均為A可直達的下一跳節(jié)點.G、C、D彼此之間互通互聯(lián)，可以相互交換信息，構(gòu)成了節(jié)點E的轉(zhuǎn)發(fā)節(jié)點集.同理，節(jié)點B、D、F構(gòu)成了節(jié)點A的轉(zhuǎn)發(fā)節(jié)點集.為了進一步縮小轉(zhuǎn)發(fā)節(jié)點集，數(shù)據(jù)包p和q的源節(jié)點A和E分別從它們的下一跳節(jié)點集中去掉部分節(jié)點，如根據(jù)傳統(tǒng)的最短路徑優(yōu)先策略，D是節(jié)點E的一跳鄰居中距離目的節(jié)點F最近的節(jié)點，則節(jié)點D優(yōu)先加入轉(zhuǎn)發(fā)集里；G和C節(jié)點距離目的節(jié)點F較遠，故加入轉(zhuǎn)發(fā)集的優(yōu)先順序較低.

圖2 數(shù)據(jù)包額外信息添加Figure 2 Appending additional information to the packet

3 選擇最優(yōu)編碼節(jié)點

轉(zhuǎn)發(fā)節(jié)點集合選擇完成后，就從這個轉(zhuǎn)發(fā)集中挑選出一個最佳轉(zhuǎn)發(fā)節(jié)點，最后將數(shù)據(jù)流進行編碼轉(zhuǎn)發(fā).ExCAR協(xié)議根據(jù)節(jié)點編碼機會的數(shù)量最終確定由轉(zhuǎn)發(fā)節(jié)點中集哪個節(jié)點進行編碼，并將編碼機會數(shù)量最多的節(jié)點選為最優(yōu)轉(zhuǎn)發(fā)節(jié)點.網(wǎng)絡中某個節(jié)點的編碼機會次數(shù)越多，在一次編碼傳輸中被發(fā)送的原始數(shù)據(jù)報文就越多，在單次傳輸中攜帶的信息量也越多，從而提升了自然網(wǎng)絡的整體吞吐量.

如何使轉(zhuǎn)發(fā)集中的所有節(jié)點認同它們中的某個節(jié)點擁有最多的編碼機會，是選擇最佳編碼節(jié)點的關(guān)鍵.ExCAR協(xié)議根據(jù)數(shù)據(jù)包信息交換機制，以固定的時間間隔使轉(zhuǎn)發(fā)集中每個節(jié)點所擁有的數(shù)據(jù)包信息轉(zhuǎn)發(fā)給集合中的其他節(jié)點，并告知其他所有節(jié)點當前緩存了哪些數(shù)據(jù)包，同時將每個數(shù)據(jù)報文中的packet holders信息也一同發(fā)送到鄰居節(jié)點.節(jié)點集中的節(jié)點通過各節(jié)點交換來的數(shù)據(jù)信息計算出編碼機會次數(shù)，從而選出最佳編碼節(jié)點.

上述計算都是由轉(zhuǎn)發(fā)集里的各個節(jié)點在本地計算完成的.對于某一特定數(shù)據(jù)包來說，如果某節(jié)點有最多的編碼機會，那么不必等待其他節(jié)點傳送來的信息就可以直接對數(shù)據(jù)包進行編碼.相反，如果節(jié)點編碼機會并不是最多的，那么該節(jié)點存儲這個數(shù)據(jù)包后不再進行任何操作，直接等待下一次編碼機會計算.

圖3 使用Ex CAR協(xié)議的網(wǎng)絡模型Figure 3 Ex CAR-based network model

表2 可偵聽到當前數(shù)據(jù)包的節(jié)點列表Table 2 Node list that can overhear the packet

如圖3所示，若節(jié)點A要將數(shù)據(jù)包p發(fā)送到節(jié)點G，節(jié)點E要將數(shù)據(jù)包q發(fā)送到節(jié)點B，節(jié)點G要將數(shù)據(jù)包r發(fā)送到節(jié)點F，它們各自的轉(zhuǎn)發(fā)集分別為節(jié)點集合B、C、D、F，集合G、C、D、F和集合B、C、E.表2分別列出了數(shù)據(jù)包p、q、r中各自攜帶的packet holders信息.在這3個轉(zhuǎn)發(fā)集中，節(jié)點B、D、F都有兩條數(shù)據(jù)流交匯，且都符合編碼的一般性條件[6]，說明這兩個節(jié)點可以對各自收到的兩條數(shù)據(jù)流進行編碼后轉(zhuǎn)發(fā).節(jié)點C相繼收到了3個數(shù)據(jù)包，且都符合多數(shù)據(jù)流編碼的一般條件[6]，于是節(jié)點C可以對這3個數(shù)據(jù)包同時進行編碼，在單次編碼轉(zhuǎn)發(fā)中發(fā)送最多的數(shù)據(jù)信息.比較節(jié)點間編碼機會數(shù)量可知，節(jié)點B和D可以編碼的數(shù)據(jù)流只有2條，而不是3條，說明節(jié)點C擁著最多的編碼機會，即為該轉(zhuǎn)發(fā)集中的最佳編碼節(jié)點.且經(jīng)C編碼后得到的編碼包p⊕q⊕r發(fā)送至3個目的節(jié)點后，都可以被成功解碼.

ExCAR算法的偽代碼如下所述.首先給出兩個假設：當收到一個網(wǎng)絡中的數(shù)據(jù)包p時，假設節(jié)點x和y為同一轉(zhuǎn)發(fā)集中的節(jié)點，且兩個節(jié)點相互交換各自的狀態(tài)信息；假設節(jié)點y的輸入隊列里已存在的原始數(shù)據(jù)包的數(shù)量為n.節(jié)點x計算節(jié)點y編碼機會次數(shù)的過程如下：

Input：p;//原始數(shù)據(jù)包

Reception report;//節(jié)點x收到y(tǒng)節(jié)點的報告

Output：the number of coding chances in y;

Algorithm:

count=0;

while(node y′input queue!=null)

{

for(i=1;i＜n;i++){

if(the destination ID packet of p is in the packet holders of pi&&the destination ID of piis in

the packet holders of p){

count++;

pcod1=ppi;//對進行編碼，獲得編碼包pcod1;the packet holders of pcod1=(the packet holders of p)∩(the holders set of pi);

the destination IDs of pcod1=(the destination ID of p)∪(the destination ID of pi);pcod1is stored to the buffer;remove pifrom input queue;break;

}

}

//下一次編碼機會的判斷for(j=1;j＜n-2;j++){

if(the destination ID of pjis in the packet hold ers of pcod1&&the destination ID of the pcod1is in the packet holders of pj){

count++;

pcod2=pcod1pj;//進行編碼，得到編碼包pcod2;the destination ID of pcod2=(the destination IDs of pcod1)∪(the destination ID of pj);

the packet holders of the pcod2=(the packet hold-ers of pcod1)∩(the packet holders of pj);

pcod2is stored to the buffer;

piis removed from input queue;

break;

}

}

//判斷下一次編碼機會，檢查節(jié)點y的輸入隊列是否還存在別的原始數(shù)據(jù)包可以與pcod2進行編碼.

...

//如果沒有任何原始數(shù)據(jù)包可與現(xiàn)有的編碼包進行編碼，則結(jié)束操作.

Total coding chances in y=count;}

上述計算過程完整地描述了ExCAR協(xié)議是如何選擇數(shù)據(jù)包p的最佳轉(zhuǎn)發(fā)節(jié)點的.ExCAR協(xié)議將檢測數(shù)據(jù)包p與節(jié)點輸入緩存的每個數(shù)據(jù)包是否存在編碼機會，如存在則編碼機會次數(shù)增加一次，直至沒有數(shù)據(jù)包能與現(xiàn)有的編碼包進行編碼為止.轉(zhuǎn)發(fā)集中的所有節(jié)點都要執(zhí)行完成上述過程，并將編碼機會次數(shù)最多的節(jié)點選為最佳轉(zhuǎn)發(fā)節(jié)點.數(shù)據(jù)包在此點編碼后進行轉(zhuǎn)發(fā)，能保證在一次數(shù)據(jù)傳輸中發(fā)送最多的數(shù)據(jù)量.

4 基于優(yōu)先級的轉(zhuǎn)發(fā)

由于存在某個數(shù)據(jù)包會同時獲得多個具有相同編碼機會數(shù)量的節(jié)點的情況，可根據(jù)轉(zhuǎn)發(fā)集中的節(jié)點與數(shù)據(jù)包目的節(jié)點之間的距離設置轉(zhuǎn)發(fā)集中每個節(jié)點的轉(zhuǎn)發(fā)優(yōu)先級.節(jié)點與數(shù)據(jù)包要傳送的目的節(jié)點之間的距離決定此節(jié)點優(yōu)先級的大小，跳數(shù)越少，節(jié)點的優(yōu)先級越高；反之，跳數(shù)越多，則優(yōu)先級越低.當上述情況發(fā)生時，就會根據(jù)節(jié)點的轉(zhuǎn)發(fā)優(yōu)先級進行數(shù)據(jù)包的編碼和轉(zhuǎn)發(fā).網(wǎng)絡中每個節(jié)點設置一個倒計時時鐘，當一個節(jié)點收到新的數(shù)據(jù)包時，其倒計時時鐘開始倒計時工作.當這個節(jié)點倒計時結(jié)束時，如果節(jié)點剛才所接收到的數(shù)據(jù)包還未傳送出去，則強制將此數(shù)據(jù)包轉(zhuǎn)發(fā)出去.轉(zhuǎn)發(fā)集中的其他節(jié)點在監(jiān)聽到這個數(shù)據(jù)包已被轉(zhuǎn)發(fā)后，也將結(jié)束時鐘的倒計時工作.當此數(shù)據(jù)包已被轉(zhuǎn)發(fā)出去，但該節(jié)點的轉(zhuǎn)發(fā)時鐘計時仍未結(jié)束時，停止所有轉(zhuǎn)發(fā)集中節(jié)點的倒計時工作，準備接收新的數(shù)據(jù)包.

5 實驗仿真與結(jié)果分析

5.1 仿真參數(shù)

利用網(wǎng)絡仿真工具NS2對算法性能進行仿真，仿真區(qū)域大小為800m×800m.在區(qū)域內(nèi)隨機分布16個節(jié)點，隨機生成網(wǎng)絡的拓撲結(jié)構(gòu)，并將各節(jié)點的初始狀態(tài)設置為靜止態(tài).仿真采用IEEE802.11作為MAC層協(xié)議，鏈路帶寬為2 Mbit/s.仿真區(qū)域內(nèi)的節(jié)點間采用無線鏈路進行連接，各節(jié)點的通信半徑設置為200m，每個節(jié)點產(chǎn)生CBR數(shù)據(jù)流的速率恒定，并且CBR數(shù)據(jù)流中每個封包的大小固定為512 B，仿真時間設置為120 s.仿真算法如下：1)COPE協(xié)議是第1個考慮網(wǎng)絡編碼實際應用的協(xié)議，能夠發(fā)現(xiàn)當前節(jié)點一跳范圍內(nèi)的編碼機會，此時網(wǎng)絡層使用的路由協(xié)議為AODV協(xié)議；2)ExCAR算法可根據(jù)節(jié)點中的編碼機會數(shù)量計算為數(shù)據(jù)包選擇一個最佳編碼轉(zhuǎn)發(fā)節(jié)點.設置好一組場景參數(shù)后，反復進行10次仿真，并將計算出的平均值作為仿真得到的結(jié)果.

5.2 評價指標

網(wǎng)絡吞吐量是分析網(wǎng)絡性能優(yōu)劣的有效手段之一，其計算公式為

式中，p為一定時間內(nèi)所有目的節(jié)點接收到的數(shù)據(jù)量，t為測試的時間長度.

分組投遞率的計算公式為

式中，信源節(jié)點所傳送數(shù)據(jù)包的數(shù)量以pf表示，網(wǎng)絡中目的節(jié)點收到來自信源節(jié)點所發(fā)送的且不包括重復數(shù)據(jù)包的數(shù)量以pr來表示.

編碼包比例的計算公式為

式中，pcode為網(wǎng)絡中傳輸?shù)木幋a包總數(shù)，pall為網(wǎng)絡中傳輸?shù)乃袛?shù)據(jù)包總數(shù).該指標越高表明網(wǎng)絡中傳輸?shù)木幋a包越多，即節(jié)點中對傳輸?shù)臄?shù)據(jù)流進行編碼的次數(shù)越多.

5.3 仿真結(jié)果

為了使網(wǎng)絡應用層每秒生成大小不同的數(shù)據(jù)流量，在仿真過程中將節(jié)點產(chǎn)生的CBR數(shù)據(jù)流量設置多個數(shù)值.根據(jù)參數(shù)設置的不同，統(tǒng)計從源節(jié)點成功到達目的節(jié)點的數(shù)據(jù)量.圖4繪出了COPE協(xié)議和ExCAR協(xié)議在不同網(wǎng)絡負載情況下的網(wǎng)絡吞吐量.由圖4可以看出，當網(wǎng)絡中的數(shù)據(jù)流量相對小時，使用ExCAR和COPE協(xié)議時所獲得的吞吐量趨近相同.然而，當這兩種協(xié)議擁有等量的數(shù)據(jù)流并且逐漸增加網(wǎng)絡負載時，使用ExCAR協(xié)議不但可以比COPE協(xié)議獲取更高的網(wǎng)絡吞吐量，而且可以穩(wěn)定在10%左右的范圍內(nèi).原因在于ExCAR協(xié)議可以發(fā)現(xiàn)網(wǎng)絡中更多的編碼機會，也可以選取到最合適的那個節(jié)點作為數(shù)據(jù)包的下一跳轉(zhuǎn)發(fā)節(jié)點，從而更多地使用網(wǎng)絡編碼，提升網(wǎng)絡吞吐量.

圖4 網(wǎng)絡吞吐量仿真結(jié)果Figur e 4 Network throughput vs.offered load

在所分配的時間內(nèi)，目的節(jié)點成功接收到信源節(jié)點所發(fā)送的數(shù)據(jù)包的概率為分組投遞率.圖5同樣對比了在不同網(wǎng)絡負載情況下的COPE協(xié)議和ExCAR協(xié)議.從圖5中可以看出，當網(wǎng)絡負載很輕時，網(wǎng)絡的分組投遞率總能保持在一個較高的水平；隨著網(wǎng)絡數(shù)據(jù)流量的逐漸增加，分組投遞率則開始逐漸下降.與COPE協(xié)議相比，運用ExCAR協(xié)議總能獲得更高的分組投遞率，這是因為ExCAR協(xié)議可以更多地發(fā)現(xiàn)編碼機會.

圖5分組投遞率仿真結(jié)果Figure 5 Packet delivery rate vs.offered load

圖6 給出了采用ExCAR與COPE兩種算法時被編碼數(shù)據(jù)包的數(shù)量占網(wǎng)絡中數(shù)據(jù)包總數(shù)量的百分比.從圖6中可以看到，無論網(wǎng)絡負載量如何變化，應用ExCAR協(xié)議時總有更多的編碼包.運用ExCAR協(xié)議網(wǎng)絡中的編碼包所占比例的最高值達36%，大約比使用COPE協(xié)議時高15%.原因是ExCAR協(xié)議可以發(fā)現(xiàn)更多的編碼機會，使更多的網(wǎng)絡數(shù)據(jù)包進行編碼操作，于是網(wǎng)絡中編碼包的數(shù)量也隨之增加，自然編碼包的數(shù)量也隨之增加.

圖6 網(wǎng)絡編碼包比例統(tǒng)計結(jié)果Figure 6 Encoded packet rate vs.offered load

6 結(jié)語

本文將最大化編碼機會發(fā)現(xiàn)策略ExCODE與現(xiàn)有的編碼感知路由協(xié)議相結(jié)合，當網(wǎng)絡節(jié)點為將要轉(zhuǎn)送的數(shù)據(jù)流選擇下一跳轉(zhuǎn)發(fā)節(jié)點時考慮轉(zhuǎn)發(fā)集中節(jié)點的所有編碼機會，并以各節(jié)點編碼機會數(shù)量的多少決定最終由哪個節(jié)點進行編碼轉(zhuǎn)發(fā).在網(wǎng)絡中盡可能多地使用網(wǎng)絡編碼技術(shù)，以提高網(wǎng)絡性能.NS-2仿真結(jié)果表明：ExCAR協(xié)議是一種高效的編碼感知路由協(xié)議，根據(jù)節(jié)點的編碼機會計算來選擇出最佳的編碼節(jié)點，使得這一協(xié)議在網(wǎng)絡吞吐量、分組投遞率等方面都有所提高.為了在實際網(wǎng)絡環(huán)境中測試ExCAR協(xié)議的性能，我們計劃將這一協(xié)議部署在由ORACLE公司開發(fā)的Sun SPOT節(jié)點組成的無線傳感器網(wǎng)絡.

[1]AHLSw EDE R,CAI N,LI S Y R,YEUNG R W.Network information f low[J].IEEE Transaction on Information Theory,2000,46(4):1204-1216.

[2]ZHAO Y L,DONG Z,IwAI M,SEZAKI K,TOBE Y.An extended network coding opportunity discovery scheme in wireless networks[J].International Journal of Computer Networks&Communications,2012,4(1):63-77.

[3]KATTIS,RAHULH,HUW J,KATABID,M′EDARDM,CROw CROFT J.XORs in the air:practical wireless network coding[C]//Special Interest Group on Data Communication(SIGCOMM),New York,2006:243-254.

[4]YAN Yan,ZHANG baoxian,ZHENG Jun,MA Jian.CORE:a coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEE Wireless Communications,2010,17:96-103.

[5]LE J L,LUI J C S,CHIUD M.DCAR:distributed coding-aware routing in wireless networks[J].IEEE Transantion on Mobile Computing,2008,9(4):463-469.

[6]GUO B,LI H K,ZHOU C,CHENG Y.General network coding conditions in multihop wireless networks[C]//IEEE International Conference on Communications(ICC),Chicago,IL,2010:1-5.

[7]GUOB,LIH K,ZHOUC,CHENGY.Analysis of general network coding conditions and design of a freeride-oriented routing metric[J].IEEE Transactions on Vehicular Technology,2011:1714-1727.