代 思，何加銘，鄭紫微，馮 波

(1.寧波大學(xué)通信技術(shù)研究所，浙江寧波 315211;2.浙江省移動(dòng)網(wǎng)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，浙江寧波 315211;3.中國(guó)移動(dòng)通信集團(tuán)浙江有限公司，浙江寧波 315042)

0 引言

在傳統(tǒng)的網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)的作用僅僅是完成對(duì)數(shù)據(jù)包的存儲(chǔ)和轉(zhuǎn)發(fā)。直到2000年網(wǎng)絡(luò)編碼［1］概念的提出，網(wǎng)絡(luò)節(jié)點(diǎn)擔(dān)任的角色才得以發(fā)生改變:網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)接收到的多個(gè)數(shù)據(jù)包編碼后再發(fā)送出去。這樣可以大大提高單次傳輸攜帶的信息量、減少傳輸次數(shù)、緩解網(wǎng)絡(luò)擁塞以及提高網(wǎng)絡(luò)吞吐量。

無(wú)線網(wǎng)絡(luò)與生俱來(lái)的廣播特性和偵聽(tīng)能力使得它非常適合網(wǎng)絡(luò)編碼的應(yīng)用。Kitti等［2］在20個(gè)節(jié)點(diǎn)的無(wú)線網(wǎng)絡(luò)試驗(yàn)床上實(shí)現(xiàn)了基于機(jī)會(huì)路由和異或操作網(wǎng)絡(luò)編碼的無(wú)線協(xié)議COPE。然而數(shù)據(jù)包在數(shù)量上的不公平性對(duì)編碼機(jī)會(huì)的產(chǎn)生帶來(lái)了巨大的影響。文獻(xiàn)［3］提出了人為地延遲網(wǎng)絡(luò)節(jié)點(diǎn)中暫時(shí)不能編碼的數(shù)據(jù)包的發(fā)送時(shí)間，以制造更多的編碼機(jī)會(huì)。但是該方法是針對(duì)TCP流提出的，并不適用在UDP 流上。Seferoglu等人［4－6］提出了基于丟包策略的編碼感知算法用于調(diào)節(jié)各個(gè)數(shù)據(jù)流的發(fā)送速率，用來(lái)均衡不同流中的數(shù)據(jù)包以達(dá)到增加編碼機(jī)會(huì)的目的。文獻(xiàn)［7－8］對(duì)具有編碼感知能力的路由協(xié)議展開(kāi)了研究，針對(duì)COPE較被動(dòng)的編碼方式，在路由選擇過(guò)程當(dāng)中適當(dāng)?shù)剡x擇編碼機(jī)會(huì)較高的路由。

1 COPE原理

COPE的基本工作原理可以用圖1所示的X型拓?fù)鋪?lái)說(shuō)明。假設(shè)該拓?fù)渲写嬖?條數(shù)據(jù)流如表1所示，節(jié)點(diǎn)1要向節(jié)點(diǎn)3發(fā)送數(shù)據(jù)包a，節(jié)點(diǎn)4要向節(jié)點(diǎn)5發(fā)送數(shù)據(jù)包b。在某一時(shí)刻，中間節(jié)點(diǎn)2同時(shí)獲得了數(shù)據(jù)包a和數(shù)據(jù)包b，節(jié)點(diǎn)5偵聽(tīng)到數(shù)據(jù)包a，節(jié)點(diǎn)3偵聽(tīng)到數(shù)據(jù)包b，并且節(jié)點(diǎn)2可以獲知到它的鄰居節(jié)點(diǎn)所存數(shù)據(jù)包信息。此時(shí)在節(jié)點(diǎn)2處采取異或編碼方式得到a⊕b，然后將該編碼包廣播發(fā)送出去。在節(jié)點(diǎn)5和節(jié)點(diǎn)3處利用本地的數(shù)據(jù)包信息可以分別從編碼包a⊕b中解碼出自己想要的數(shù)據(jù)包。由此可見(jiàn)，COPE通過(guò)3次發(fā)送達(dá)到了原來(lái)發(fā)送4次的效果，使得網(wǎng)絡(luò)的吞吐量提高了33.3%。

圖1 COPE應(yīng)用的X型拓?fù)?/p>

表1 圖1的路由表

2 MDCNC基本思想

從增加編碼機(jī)會(huì)的角度出發(fā)，對(duì)采用COPE編碼機(jī)制的UDP流無(wú)線網(wǎng)絡(luò)展開(kāi)研究，提出一種基于最小延遲代價(jià)的網(wǎng)絡(luò)編碼方法——(Minimum Delay Cost Network Coding ，MDCNC)。

在圖2中，假設(shè)有3條數(shù)據(jù)流分別記做f1、f2和f3，各條流的路徑如表2所示;則對(duì)于f1和f2，節(jié)點(diǎn)2是它們的可編碼節(jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)1向節(jié)點(diǎn)2發(fā)送來(lái)自于f1的數(shù)據(jù)包可以被節(jié)點(diǎn)5偵聽(tīng)到，節(jié)點(diǎn)4向節(jié)點(diǎn)5發(fā)送的來(lái)自于f2的數(shù)據(jù)包可以被節(jié)點(diǎn)3偵聽(tīng)到，此時(shí)如果將來(lái)自于2條數(shù)據(jù)流的數(shù)據(jù)包在節(jié)點(diǎn)2處編碼后再發(fā)送出去，那么在節(jié)點(diǎn)5和節(jié)點(diǎn)3處分別可以解碼出各自所需要的數(shù)據(jù)包。但是對(duì)于f3，在節(jié)點(diǎn)2處無(wú)法找到可以同它編碼的數(shù)據(jù)流。因?yàn)楣?jié)點(diǎn)7無(wú)法偵聽(tīng)到節(jié)點(diǎn)1或者節(jié)點(diǎn)4發(fā)送的數(shù)據(jù)包，因此若來(lái)自于f3的數(shù)據(jù)包在節(jié)點(diǎn)2處同f1或f2中任何一個(gè)編碼后都不能在節(jié)點(diǎn)7處完成解碼。我們稱(chēng)這種情況為節(jié)點(diǎn)2是f3的非可編碼節(jié)點(diǎn)。

以上情況是針對(duì)UDP流展開(kāi)討論的，如果是TCP流則不會(huì)有這種情況發(fā)生，因?yàn)門(mén)CP流與UDP流的不同之處在于TCP流存在一個(gè)ACK確認(rèn)機(jī)制，文獻(xiàn)［3］正是有效利用了ACK的確認(rèn)機(jī)制，將路徑相同但是方向相反的ACK包同要傳輸?shù)臄?shù)據(jù)包編碼，使得網(wǎng)絡(luò)編碼有可能發(fā)生在沿途任何一個(gè)中繼節(jié)點(diǎn)上。而對(duì)于UDP數(shù)據(jù)流來(lái)說(shuō)不是在每個(gè)節(jié)點(diǎn)處都存在網(wǎng)絡(luò)編碼的機(jī)會(huì)。圖2中如果采用文獻(xiàn)［3］的延遲策略，則當(dāng)節(jié)點(diǎn)2獲得發(fā)送數(shù)據(jù)的機(jī)會(huì)且剛好待發(fā)送數(shù)據(jù)包是來(lái)自于f3時(shí)，為了等待可能到來(lái)的編碼機(jī)會(huì)，會(huì)暫時(shí)不發(fā)送該數(shù)據(jù)包。但是該編碼機(jī)會(huì)是不存在的，稱(chēng)這種延遲為非必要延遲。

圖2 MDCNC應(yīng)用的輪拓?fù)?/p>

表2 圖2的路由表

MDCNC的基本思想就是減少不必要延遲次數(shù)、降低必要延遲時(shí)間，用犧牲很小的端到端延遲時(shí)間來(lái)獲取更多的編碼機(jī)會(huì)，相比原有的COPE協(xié)議，MDCNC可以帶來(lái)更高的吞吐量。

3 MDCNC實(shí)現(xiàn)

3.1 可編碼條件

在給出MDCNC的實(shí)現(xiàn)方法之前，首先給出確定可編碼節(jié)點(diǎn)的算法。文獻(xiàn)［2］指出，節(jié)點(diǎn)v要向n個(gè)下一跳節(jié)點(diǎn) r1，...，rn分別發(fā)送 n 個(gè)數(shù)據(jù)包p1，...，pn，節(jié)點(diǎn) v處可以將這 n個(gè)數(shù)據(jù)包異或編碼的充分必要條件是每個(gè)下一跳節(jié)點(diǎn)ri都已經(jīng)擁有n－1個(gè)數(shù)據(jù)包pj，其中 j≠i。文中仍然考慮2跳以內(nèi)的網(wǎng)絡(luò)編碼情況，給出可編碼節(jié)點(diǎn)要滿足的條件:

式中，c表示待判定節(jié)點(diǎn)，F(xiàn)表示新增加的一條數(shù)據(jù)流，用Fi標(biāo)識(shí) c處已經(jīng)存在的其中一條數(shù)據(jù)流。N(c)表示c的一跳鄰居節(jié)點(diǎn)集合。U(c，F(xiàn))表示F上c的上一跳節(jié)點(diǎn)，D(c，F(xiàn))表示F上c的下一跳節(jié)點(diǎn)。若要判斷節(jié)點(diǎn)c是否為新增數(shù)據(jù)流F的可編碼節(jié)點(diǎn)，只要滿足式(1)和式(2)，就能說(shuō)明節(jié)點(diǎn)c為新增數(shù)據(jù)流F的可編碼節(jié)點(diǎn)。

3.2 路由發(fā)現(xiàn)過(guò)程

當(dāng)節(jié)點(diǎn)Vsrc準(zhǔn)備向節(jié)點(diǎn)Vdest發(fā)送數(shù)據(jù)并發(fā)現(xiàn)路由表中沒(méi)有相應(yīng)路由項(xiàng)時(shí)，Vsrc啟動(dòng)路由請(qǐng)求過(guò)程。

步驟1:Vsrc生成一個(gè)RREQ包并向自己的鄰居節(jié)點(diǎn)廣播出去，在被廣播之前需要初始化RREQ包中的一系列參數(shù)。每個(gè)中間節(jié)點(diǎn)Vi將首先丟棄路徑記錄中已經(jīng)包含Vi的地址的RREQ包，以防止出現(xiàn)路由環(huán)路。否則，RREQ包中的信息被更新后廣播出去。

步驟2:RREQ到達(dá)目的節(jié)點(diǎn)Vdest之后，目的節(jié)點(diǎn)會(huì)選擇一條最優(yōu)路徑，然后生成一個(gè)路由回復(fù)RREP包，將其沿著與來(lái)時(shí)相反的方向發(fā)送至源節(jié)點(diǎn)Vsrc。每個(gè)中間節(jié)點(diǎn)Vi首先根據(jù)RREP包中的信息更新路由表以建立到目的節(jié)點(diǎn)的正向路由。然后，Vi根據(jù)鄰居信息應(yīng)用式(1)來(lái)判斷本身是否為該路由的可編碼節(jié)點(diǎn)，Vi將該判斷結(jié)果記錄下來(lái)。Vi繼續(xù)轉(zhuǎn)發(fā)RREP包。

步驟3:源節(jié)點(diǎn)Vsrc接收到RREP后，開(kāi)始根據(jù)選定的路徑發(fā)送數(shù)據(jù)包。

路由發(fā)現(xiàn)過(guò)程是在現(xiàn)有的AODV路由協(xié)議上做的改進(jìn)，只需要加入步驟2中可編碼節(jié)點(diǎn)的判斷，這樣做的好處是實(shí)現(xiàn)了網(wǎng)絡(luò)的平滑過(guò)度。

3.3 MDCNC實(shí)施方案

圖3中的算法流程圖描述了MDCNC編碼的具體實(shí)現(xiàn)方案，整個(gè)過(guò)程可以分為發(fā)送和接收兩部分。在每個(gè)節(jié)點(diǎn)Vi處都維護(hù)了3個(gè)FIFO隊(duì)列(Q1、Q2、Q3)，Q1用于存放將該節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)發(fā)送過(guò)來(lái)的數(shù)據(jù)包，Q2用于存放該節(jié)點(diǎn)偵聽(tīng)到的數(shù)據(jù)包，Q3用于存放等待編碼機(jī)會(huì)的數(shù)據(jù)包。

圖3 MDCNC編碼實(shí)施方案

當(dāng)節(jié)點(diǎn)Vi接收到一個(gè)數(shù)據(jù)包后，首先判斷該數(shù)據(jù)包是不是編碼數(shù)據(jù)包，能不能完成解碼。接下來(lái)檢查該數(shù)據(jù)包下一跳節(jié)點(diǎn)列表中是否包含Vi節(jié)點(diǎn)，如果沒(méi)有則說(shuō)明Vi不是該數(shù)據(jù)包的下一跳節(jié)點(diǎn)，將其保存在Q2中;如果是下一跳節(jié)點(diǎn)，還要判斷Vi是否為目的節(jié)點(diǎn)。

節(jié)點(diǎn)Vi獲得一次發(fā)送數(shù)據(jù)包的機(jī)會(huì)后，先處理Q3中的數(shù)據(jù)包，再處理Q1中的數(shù)據(jù)包。

對(duì)于Q1中的數(shù)據(jù)包，根據(jù)先進(jìn)先出原則，首先對(duì)放在隊(duì)首的p1進(jìn)行編碼能力的判斷，判斷Vi是否為它的可編碼節(jié)點(diǎn)。如果是可編碼節(jié)點(diǎn)再接著查看編碼機(jī)會(huì)，存在編碼機(jī)會(huì)則編碼后發(fā)送編碼包;假如是可編碼節(jié)點(diǎn)，但此時(shí)卻沒(méi)有編碼機(jī)會(huì)，則將p1移動(dòng)到Q3中等待可能到來(lái)的編碼機(jī)會(huì)。

對(duì)于Q3中的數(shù)據(jù)包，如果沒(méi)有超過(guò)設(shè)定的延遲等待時(shí)間，則繼續(xù)等待，如果超過(guò)了延遲等待時(shí)間，則檢查此時(shí)是否有編碼機(jī)會(huì)到來(lái)，有編碼機(jī)會(huì)則編碼后發(fā)送出去，沒(méi)有編碼機(jī)會(huì)則不編碼直接發(fā)送。

4 仿真分析

4.1 評(píng)價(jià)指標(biāo)確定

MDCNC的設(shè)計(jì)目的在于增加數(shù)據(jù)傳輸過(guò)程中的編碼機(jī)會(huì)，因此選取吞吐量、平均端到端延遲和編碼次數(shù)作為性能好壞的評(píng)價(jià)指標(biāo)。

4.2 仿真環(huán)境設(shè)置

仿真環(huán)境為 NS2［9］，MAC層協(xié)議采用 IEEE 802.11 DCF，信道容量為2 Mbit/s，節(jié)點(diǎn)的數(shù)據(jù)發(fā)送隊(duì)列大小為50，節(jié)點(diǎn)的傳輸范圍為250 m，數(shù)據(jù)源采用的是CBR流，數(shù)據(jù)包大小為512 byte，MDCNC中數(shù)據(jù)包延遲發(fā)送時(shí)間設(shè)置為1.5 s。分別對(duì)AODV、AODV+COPE和AODV+MDCNC這3種傳輸方式進(jìn)行比較。

4.3 仿真結(jié)果及分析

4.3.1 固定網(wǎng)絡(luò)拓?fù)?/p>

為了直觀地說(shuō)明MDCNC的優(yōu)點(diǎn)，首先在圖2所示的輪拓?fù)渲斜容^上述3種傳輸方式的性能，數(shù)據(jù)發(fā)送速率設(shè)定在0～1400 kbit/s之間，選取其中的19個(gè)采樣點(diǎn)作為性能分析的參考數(shù)據(jù)，f1和f2采用不同的數(shù)據(jù)發(fā)送速率:

圖4和圖5展示了在不同速率下3種傳輸方式的網(wǎng)絡(luò)吞吐量和平均端到端延遲的變化情況。從折線對(duì)比圖中可以看出在速率非常小的情況下3種傳輸方式對(duì)網(wǎng)絡(luò)吞吐量影響差異不是很大，而MDCNC的平均端到端延遲略微高于其他兩種情況。但是隨著數(shù)據(jù)發(fā)送速率的逐漸增大，大概從180 kbit/s開(kāi)始，可以編碼的COPE和MDCNC的吞吐量逐漸超出了不能編碼的AODV和AODV的端到端延遲時(shí)間也迅速增大，COPE和MDCNC的端到端延遲均沒(méi)有什么變化。由于采用了延時(shí)機(jī)制，MDCNC的端到端延遲時(shí)間會(huì)略微高于COPE，此時(shí)MDCNC相對(duì)于COPE的優(yōu)勢(shì)并沒(méi)有明顯表現(xiàn)出來(lái)。但是隨著速率的繼續(xù)增長(zhǎng)，COPE的網(wǎng)絡(luò)吞吐量上升開(kāi)始變緩，MDCNC迅速超過(guò)了COPE。在400 kbit/s左右時(shí)，由于可編碼的2條流速率不匹配問(wèn)題以及發(fā)送隊(duì)列的容量問(wèn)題，使得COPE的編碼機(jī)會(huì)出現(xiàn)減少的趨勢(shì)，網(wǎng)絡(luò)吞吐量開(kāi)始下降，端到端延遲迅速上升。而MDCNC所特有的延遲機(jī)制以及更大的隊(duì)列空間使得它的編碼機(jī)會(huì)還在增加，吞吐量仍然保持上升，MDCNC的端到端延遲也略低于COPE，MDCNC的吞吐量?jī)?yōu)勢(shì)顯現(xiàn)出來(lái)。當(dāng)速率達(dá)到900 kbit/s時(shí)，由于嚴(yán)重的網(wǎng)絡(luò)擁塞，3種方式的吞吐量變化都趨于平緩狀態(tài)，端到端延遲也達(dá)到最大。

圖4 3種傳輸方式的網(wǎng)絡(luò)吞吐量變化

圖5 3種傳輸方式平均端到端延遲變化

圖6表示的是在不同速率下COPE和MDCNC編碼次數(shù)的變化情況。在數(shù)據(jù)發(fā)送速率非常小的時(shí)候，兩者的編碼次數(shù)相差不大，隨著數(shù)據(jù)發(fā)送速率的增加，MDCNC的編碼次數(shù)要明顯高于COPE。

圖6 MDCNC與COPE編碼次數(shù)對(duì)比

4.3.2 隨機(jī)網(wǎng)絡(luò)拓?fù)?/p>

為了使MDCNC協(xié)議的評(píng)價(jià)更具普遍性，在一個(gè)隨機(jī)拓?fù)渚W(wǎng)絡(luò)模型下進(jìn)行多次實(shí)驗(yàn)。主要評(píng)價(jià)指標(biāo)為不同數(shù)據(jù)流數(shù)目下MDCNC與COPE編碼次數(shù)的變化。實(shí)驗(yàn)環(huán)境為利用NS2中setdest工具創(chuàng)建一個(gè)長(zhǎng)、寬各1000 m，擁有50個(gè)節(jié)點(diǎn)的移動(dòng)場(chǎng)景。節(jié)點(diǎn)的移動(dòng)速度最大為2 m/s，仿真時(shí)長(zhǎng)為150 s，選取數(shù)據(jù)流數(shù)目為2～20之間的10個(gè)數(shù)值，每個(gè)數(shù)值下進(jìn)行100次實(shí)驗(yàn)，取平均值。

由圖7可以看出，MDCNC中的編碼次數(shù)明顯高于COPE，這說(shuō)明MNCNC能夠制造更多的編碼機(jī)會(huì)，進(jìn)一步提高網(wǎng)絡(luò)吞吐量。

圖7 隨機(jī)拓?fù)渲蠱DCNC與COPE編碼次數(shù)對(duì)比圖

5 結(jié)束語(yǔ)

針對(duì)COPE會(huì)受數(shù)據(jù)包數(shù)量不公平性的影響，提出了一種可以應(yīng)用在無(wú)線多跳網(wǎng)絡(luò)中的最小延遲代價(jià)網(wǎng)絡(luò)編碼方法MDCNC。該方法的主要特點(diǎn)是只有在可編碼節(jié)點(diǎn)處才會(huì)采取延時(shí)策略，這樣做的目的是盡可能少地增加端到端延遲時(shí)間。從仿真結(jié)果可以看出雖然MDCNC的平均端到端延遲大部分情況下會(huì)略微高出COPE，但是卻比沒(méi)有網(wǎng)絡(luò)編碼的AODV低，所以這樣的延遲時(shí)間在網(wǎng)絡(luò)容忍范圍之內(nèi)，對(duì)于網(wǎng)絡(luò)性能并無(wú)太大影響。而該方法所制造的編碼機(jī)會(huì)卻是不可忽視的，與COPE相比較，MDCNC的編碼機(jī)會(huì)約為COPE的1.5倍，能夠有效地緩解網(wǎng)絡(luò)擁塞和提高網(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］KATTI S，RAHUL H，HU W，et al.XORs in the Air:Practical Wireless Network Coding［C］∥SIGCOMM ＇06 Proceedings of the 2006 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，ACM，36(4):243 －254.

［3］HUANG Y，GHADERI M，TOWSLEY D，et al.TCP Performance in Coded Wireless Mesh Networks［C］∥Proc.Of IEEE SECON，2008:179 －187.

［4］SEFEROGLU H，MARKOPOULOU A.Network Codingaware Queue Management for Unicast Flows over Coded Wireless Networks［C］∥IEEE International Symposium on Network Coding(NetCod)，Toronto，Canada，June 2010:1－6.

［5］SEFEROGLU H，MARKOPOULOUA，MEDARDM.NCAPQ:Network Coding-Aware Priority Queueing for UDP Folws over COPE［C］∥International Symposium on Network Coding(NetCod)，Beijing，China，July 2011:1 －8.

［6］COPPI N D，NING J X，PAPAGEORGIOU G，et al.Network Coding Aware Queue Management in Multi-Rate Wireless Networks［C］∥ The 21stInternational Conference on Computer Communications and Networks(ICCCN)，Munich，GER，July 2012:1 －7.

［7］樊凱，李令雄，龍冬陽(yáng).無(wú)線mesh網(wǎng)中網(wǎng)絡(luò)編碼感知的按需無(wú)線路由協(xié)議的研究［J］.通信學(xué)報(bào)，2009，30(1):128－134.

［8］LE J L，LUI J，CHIU D M.DCAR:Distributed Codingaware Routing in Wireless Networks［J］.IEEE Transactions on Mobile Computing，2010，9(4):596－608.

［9］徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)模擬［M］.北京:人民郵電出版社，2003:10－174.