趙蘊(yùn)龍， 王博識(shí)， 張 凱， 董 釗， 張 磊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Reception report;//節(jié)點(diǎn)x收到y(tǒng)節(jié)點(diǎn)的報(bào)告

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;//對(duì)進(jìn)行編碼，獲得編碼包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;

}

}

//下一次編碼機(jī)會(huì)的判斷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;//進(jìn)行編碼，得到編碼包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;

}

}

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

...

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

Total coding chances in y=count;}

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

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

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

5 實(shí)驗(yàn)仿真與結(jié)果分析

5.1 仿真參數(shù)

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

5.2 評(píng)價(jià)指標(biāo)

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

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

分組投遞率的計(jì)算公式為

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

編碼包比例的計(jì)算公式為

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

5.3 仿真結(jié)果

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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