無線網(wǎng)絡(luò)中最小延遲代價網(wǎng)絡(luò)編碼的研究

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

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

0 引言

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

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

1 COPE原理

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

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

表1 圖1的路由表

2 MDCNC基本思想

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

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

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

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

表2 圖2的路由表

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

3 MDCNC實現(xiàn)

3.1 可編碼條件

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

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

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

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

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

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

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

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

3.3 MDCNC實施方案

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

圖3 MDCNC編碼實施方案

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

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

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

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

4 仿真分析

4.1 評價指標(biāo)確定

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

針對COPE會受數(shù)據(jù)包數(shù)量不公平性的影響，提出了一種可以應(yīng)用在無線多跳網(wǎng)絡(luò)中的最小延遲代價網(wǎng)絡(luò)編碼方法MDCNC。該方法的主要特點是只有在可編碼節(jié)點處才會采取延時策略，這樣做的目的是盡可能少地增加端到端延遲時間。從仿真結(jié)果可以看出雖然MDCNC的平均端到端延遲大部分情況下會略微高出COPE，但是卻比沒有網(wǎng)絡(luò)編碼的AODV低，所以這樣的延遲時間在網(wǎng)絡(luò)容忍范圍之內(nèi)，對于網(wǎng)絡(luò)性能并無太大影響。而該方法所制造的編碼機會卻是不可忽視的，與COPE相比較，MDCNC的編碼機會約為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］樊凱，李令雄，龍冬陽.無線mesh網(wǎng)中網(wǎng)絡(luò)編碼感知的按需無線路由協(xié)議的研究［J］.通信學(xué)報，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.