一種新的基于部分網(wǎng)絡(luò)編碼的機(jī)會(huì)路由機(jī)制

鄔 晨，何加銘，曾興斌，樊玲慧

(1.寧波大學(xué)通信技術(shù)研究所，浙江寧波315211;2.浙江省移動(dòng)網(wǎng)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，浙江寧波315211;3.寧波新然電子信息科技發(fā)展有限公司，浙江寧波315211)

0 引言

近年來，網(wǎng)絡(luò)編碼逐漸成為研究熱點(diǎn)。網(wǎng)絡(luò)編碼［1－4］不僅能夠提高網(wǎng)絡(luò)的吞吐量，而且還能降低協(xié)議設(shè)計(jì)的復(fù)雜性。與有線網(wǎng)絡(luò)相比，因其具有的廣播特性和不依賴性，無線網(wǎng)絡(luò)更適合使用網(wǎng)絡(luò)編碼。

機(jī)會(huì)路由的概念首先是在文獻(xiàn)［5］中提出的，它與傳統(tǒng)的主動(dòng)路由完全不同。主動(dòng)路由在數(shù)據(jù)包達(dá)到之前建立起相應(yīng)的路由表，而機(jī)會(huì)路由則是在收到數(shù)據(jù)包之后選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)建立相應(yīng)的路由表。文獻(xiàn)［6］中綜合運(yùn)用了網(wǎng)絡(luò)編碼和機(jī)會(huì)路由。盡管無線網(wǎng)絡(luò)發(fā)送的冗余數(shù)據(jù)得到了降低，但相應(yīng)的算法變得更為復(fù)雜，同時(shí)也只適用于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目較少且節(jié)點(diǎn)位置幾乎不變的情況。

文獻(xiàn)［7］中提出了一種機(jī)會(huì)路由選擇的轉(zhuǎn)發(fā)策略——Expected Transmission Count(ETX)。ETX 數(shù)值越小，則傳輸數(shù)據(jù)包所需的轉(zhuǎn)發(fā)時(shí)間就越少，所消耗的能量就越少，傳輸成功的概率也就越高。但ETX不適用于拓?fù)浣Y(jié)構(gòu)不斷變化的網(wǎng)絡(luò)。此外，ETX值并沒有考慮鏈路負(fù)擔(dān)、數(shù)據(jù)傳輸速率和節(jié)點(diǎn)能量的消耗。

提出了一種機(jī)會(huì)路由協(xié)議(ORoPNC)，這一協(xié)議將部分網(wǎng)絡(luò)編碼引入到機(jī)會(huì)路由。同時(shí)，設(shè)計(jì)了一種新的ETXoEC轉(zhuǎn)發(fā)策略。在該協(xié)議下，前向節(jié)點(diǎn)的選擇基于當(dāng)前鏈路狀態(tài)以及節(jié)點(diǎn)的剩余能量。

1 部分網(wǎng)絡(luò)編碼

1．1 部分網(wǎng)絡(luò)編碼思想

部分網(wǎng)絡(luò)編碼(PNC)的思想是由Wang等提出的［8］。源節(jié)點(diǎn)僅僅廣播原始數(shù)據(jù)，不對這些數(shù)據(jù)進(jìn)行編碼。中間節(jié)點(diǎn)采用任意長度的編碼方式，目的是為了解決由數(shù)據(jù)等待而造成的網(wǎng)絡(luò)延遲。目的節(jié)點(diǎn)對獲得的數(shù)據(jù)進(jìn)行高斯消元，然后判斷是否能夠解碼。如果能夠進(jìn)行解碼，則將解碼后的數(shù)據(jù)發(fā)送至上一層;如果不能進(jìn)行解碼，則將數(shù)據(jù)壓入等待隊(duì)列。全網(wǎng)絡(luò)編碼的結(jié)構(gòu)如圖1所示，圖1解釋了部分編碼的基本思想，以及全網(wǎng)絡(luò)編碼和部分網(wǎng)絡(luò)編碼對網(wǎng)絡(luò)延遲的影響。

圖1 全網(wǎng)絡(luò)編碼

源節(jié)點(diǎn)S有4個(gè)數(shù)據(jù)包要傳輸?shù)侥康墓?jié)點(diǎn)D。S對原始數(shù)據(jù)進(jìn)行編碼，然后進(jìn)行傳輸。中間節(jié)點(diǎn)收到數(shù)據(jù)后再進(jìn)行編碼，最終將數(shù)據(jù)傳遞到目的節(jié)點(diǎn)D。假設(shè)數(shù)據(jù)包達(dá)到的時(shí)間間隔是t，即數(shù)據(jù)包p'1、p'2、p'3和 p'4達(dá)到節(jié)點(diǎn) D 的時(shí)間分別為 t、2t、3t和4t，原始數(shù)據(jù)p1、p2、p3和p4只有在D收到全部數(shù)據(jù)包之后才能進(jìn)行解碼，網(wǎng)絡(luò)的平均延遲為(4t*4)/4=4t。

部分網(wǎng)絡(luò)編碼如圖2所示。源節(jié)點(diǎn)S向外廣播數(shù)據(jù)包，中間節(jié)點(diǎn)對收到的數(shù)據(jù)包進(jìn)行任意長度的部分網(wǎng)絡(luò)編碼，然后將數(shù)據(jù)傳輸出去。假設(shè)節(jié)點(diǎn)2首先發(fā)送數(shù)據(jù)包3r1p1+3r2p2+3r3p3，節(jié)點(diǎn)D在t時(shí)刻收到數(shù)據(jù)包，但無法解碼;假設(shè)節(jié)點(diǎn)D在2t時(shí)刻從節(jié)點(diǎn)4收到數(shù)據(jù)包r1p1+r2p2+r3p3+r4p4，這個(gè)數(shù)據(jù)包與上個(gè)數(shù)據(jù)包線性相關(guān)，故可以解碼出數(shù)據(jù)p4;假設(shè)在3t時(shí)刻，節(jié)點(diǎn)D從節(jié)點(diǎn)3收到r5p3+r6p4，由于p4已知，所以可以解出p3;在最后時(shí)刻4t，節(jié)點(diǎn)D從節(jié)點(diǎn)1處收到r7p1+r8p2+r9p4，這樣可以解出p1和p2。這時(shí)平均網(wǎng)絡(luò)延遲為(2t+3t+2*4t)/4=3.25t。

圖2 部分網(wǎng)絡(luò)編碼

1．2 節(jié)點(diǎn)轉(zhuǎn)發(fā)

部分網(wǎng)絡(luò)編碼策略可以加快節(jié)點(diǎn)編碼開始時(shí)間，同時(shí)降低節(jié)點(diǎn)編碼操作的消耗。原始數(shù)據(jù)被分成幾塊，每個(gè)塊包含k的數(shù)據(jù)包。部分采用網(wǎng)絡(luò)編碼的中間節(jié)點(diǎn)使用隨機(jī)選擇策略，即節(jié)點(diǎn)從緩存中隨機(jī)地選擇若干個(gè)屬于同一個(gè)塊的數(shù)據(jù)包進(jìn)行編碼操作，而不是選擇全部或一定數(shù)量的數(shù)據(jù)包進(jìn)行編碼。在獲得信道之后，節(jié)點(diǎn)隨機(jī)地產(chǎn)生一個(gè)整數(shù)M(1≤M≤存儲(chǔ)的數(shù)據(jù)包個(gè)數(shù))，然后從緩存對列中隨機(jī)地選取M個(gè)數(shù)據(jù)包進(jìn)行編碼和轉(zhuǎn)發(fā)［9］。

由于中間節(jié)點(diǎn)采用了隨機(jī)部分網(wǎng)絡(luò)編碼方式，未被選取的數(shù)據(jù)塊的系數(shù)可以認(rèn)為是0，而編碼系數(shù)矩陣可以看作一個(gè)稀疏矩陣。稀疏矩陣的取逆相對較為簡單，解碼率較高。如果接收節(jié)點(diǎn)的稀疏編碼系數(shù)矩陣是滿秩矩陣，就可以完成解碼過程。文獻(xiàn)［10］給出了稀疏矩陣的詳細(xì)描述。

2 基于部分網(wǎng)絡(luò)編碼的機(jī)會(huì)路由

網(wǎng)絡(luò)編碼與機(jī)會(huì)路由的結(jié)合能夠有效地解決重復(fù)發(fā)送冗余數(shù)據(jù)的問題，但是這方面的研究目前主要集中在全網(wǎng)絡(luò)編碼之上。假設(shè)需要編碼的數(shù)據(jù)包的數(shù)目是N，源節(jié)點(diǎn)對原始數(shù)據(jù)進(jìn)行等長度的編碼，則目的節(jié)點(diǎn)只有在收到全部N個(gè)線性無關(guān)的數(shù)據(jù)包之后才能解碼出原始數(shù)據(jù)。全網(wǎng)絡(luò)編碼增加了數(shù)據(jù)包的等待延遲，而且有時(shí)數(shù)據(jù)包的到達(dá)是不平衡的，這不利于數(shù)據(jù)的解碼。將部分網(wǎng)絡(luò)編碼引入機(jī)會(huì)路由當(dāng)中，在考慮了成功轉(zhuǎn)發(fā)傳輸數(shù)據(jù)的時(shí)間和節(jié)點(diǎn)的能量消耗后，提出了一種新的轉(zhuǎn)發(fā)協(xié)議ETXoEC(Expected Transmission Count Based on Energy Consumption)和基于部分網(wǎng)絡(luò)編碼的機(jī)會(huì)路由(ORoPNC)。

2．1 節(jié)點(diǎn)前向時(shí)間的計(jì)算

為了避免廣播冗余，離目的節(jié)點(diǎn)最近的接收節(jié)點(diǎn)應(yīng)當(dāng)用于轉(zhuǎn)發(fā)傳輸數(shù)據(jù)包，這樣總的傳輸時(shí)間將會(huì)最少。中間節(jié)點(diǎn)不需要傳輸其收到的所有數(shù)據(jù)包，只需要傳輸下游節(jié)點(diǎn)未收到的數(shù)據(jù)。轉(zhuǎn)發(fā)時(shí)間應(yīng)當(dāng)足夠長，以保證至少一個(gè)下游節(jié)點(diǎn)收到數(shù)據(jù)包。

假設(shè)i和j是網(wǎng)絡(luò)的2個(gè)節(jié)點(diǎn)，i＜j意味著i比j更靠近目的節(jié)點(diǎn)，或者說i的ETX值小于j的ETX值。Ti是節(jié)點(diǎn)i所需的機(jī)會(huì)傳輸時(shí)間。節(jié)點(diǎn)j從上游節(jié)點(diǎn)處收到的總的數(shù)據(jù)包的數(shù)目為∑i＞jTi(1－pij)，如果j的所有下游節(jié)點(diǎn)沒有收到這一數(shù)據(jù)包，則節(jié)點(diǎn)j將此數(shù)據(jù)包前向傳輸。其他節(jié)點(diǎn)未收到此數(shù)據(jù)包的概率為∏k＜jpjk，因此，節(jié)點(diǎn)j的總傳輸機(jī)會(huì)為:

傳輸時(shí)間為:

Ci和Ti的計(jì)算基于實(shí)時(shí)的鏈路損失率，因此，為了使用當(dāng)前鏈路狀態(tài)保證數(shù)據(jù)的可靠性，pij需要進(jìn)行周期性更新。

2．2 ETXoEC轉(zhuǎn)發(fā)候選集的選擇策略

在設(shè)計(jì)轉(zhuǎn)發(fā)候選集時(shí)，ETXoEC轉(zhuǎn)發(fā)策略根據(jù)當(dāng)前鏈路狀態(tài)和節(jié)點(diǎn)剩余能量來選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。對于網(wǎng)絡(luò)節(jié)點(diǎn)，轉(zhuǎn)發(fā)機(jī)會(huì)值(OP)可以通過下面的公式計(jì)算得到:

3 性能分析

使用NS2軟件對ORoPNC協(xié)議進(jìn)行仿真和性能分析。仿真分析了ETXoEC和ETX這2種協(xié)議下的效果值K。仿真模型范圍1 000 m*1 000 m，其中隨機(jī)分布100個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的初始能量、傳輸能量和接收能量分別為10 J、3×10－4J和1.5×10－4J。源節(jié)點(diǎn)數(shù)據(jù)比特率保持不變，傳輸帶寬250 KB/s。數(shù)據(jù)包大小為256 B，MAC層協(xié)議使用802.11。

3．1 不同k值下的延遲情況

實(shí)驗(yàn)分別比較了ORoPNC和基于全網(wǎng)絡(luò)編碼的機(jī)會(huì)路由(NCOR)在使用ETXoEC作為轉(zhuǎn)發(fā)策略時(shí)的K值，其中α和β均為0.5。平均網(wǎng)絡(luò)延遲的比較結(jié)果如圖3所示。

圖3 延遲比較

當(dāng)k＜10時(shí)，ORoPNC的平均網(wǎng)絡(luò)延遲小于NCOR。當(dāng)k為5、6或者7時(shí)，平均網(wǎng)絡(luò)延遲下降約25%。隨著k的增大，網(wǎng)絡(luò)延遲的提升效果開始變得不明顯，甚至在k＞10時(shí)，ORoPNC的延遲大于NCOR。這主要是因?yàn)镹COR采用了全網(wǎng)絡(luò)編碼，所以只有當(dāng)接收到k個(gè)線性獨(dú)立的數(shù)據(jù)包后才能進(jìn)行解碼。部分網(wǎng)絡(luò)編碼在轉(zhuǎn)發(fā)過程中隨機(jī)選擇數(shù)據(jù)包用于解碼，而且編碼過程可能會(huì)重復(fù)進(jìn)行。因此，數(shù)據(jù)包之間的線性獨(dú)立關(guān)系會(huì)被降低，從而導(dǎo)致加大網(wǎng)絡(luò)延遲。

3．2 轉(zhuǎn)發(fā)策略分析

ETXoEC轉(zhuǎn)發(fā)策略綜合考慮了鏈路狀態(tài)和節(jié)點(diǎn)能量消耗。仿真分析了ETX和ETXoEC這2種采用了網(wǎng)絡(luò)編碼的轉(zhuǎn)發(fā)策略，比較了2種策略節(jié)點(diǎn)剩余能量的均方差和損失率。

3．2．1 節(jié)點(diǎn)剩余能量均方差

在仿真開始階段，ETX和ETXoEC這2種策略的節(jié)點(diǎn)剩余能量均方差幾乎相同，如圖4所示。仿真開始大約38 s以后，ExOR的節(jié)點(diǎn)剩余能量均方差大于ETXoEC轉(zhuǎn)發(fā)策略，幾秒鐘后，ExOR的節(jié)點(diǎn)剩余能量迅速下降到0。但是對于ETXoEC，網(wǎng)絡(luò)節(jié)點(diǎn)的生命周期得到增加，因?yàn)楣?jié)點(diǎn)能量消耗被考慮在內(nèi)，而且在傳輸可靠性得到確認(rèn)后，能量較低的節(jié)點(diǎn)被排除在外，不用于數(shù)據(jù)轉(zhuǎn)發(fā)。仿真結(jié)果表明，ETXoEC轉(zhuǎn)發(fā)策略應(yīng)用于ORoPNC之后，可以較好地平衡網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗，從而提升網(wǎng)絡(luò)可靠性。

圖4 節(jié)點(diǎn)剩余能量均方差

3．2．2 下降速率

由于充分考慮了鏈路可靠性，同時(shí)ETX值的計(jì)算式基于路徑測量的累積，所以ETX和ETXoEC的下降速率都相對較低。但是，從圖5中可以看出，ETXoEC的損失率要高于ETX，這主要是因?yàn)镋TX-oEC中加入了能量控制機(jī)制。在鏈路選擇的過程中考慮了能量的消耗，這也對傳輸?shù)目煽啃援a(chǎn)生了一定的作用。

圖5 下降速率

4 結(jié)束語

機(jī)會(huì)路由利用無線信道的廣播特性，可以極大地提升網(wǎng)絡(luò)的吞吐量。在綜合運(yùn)用了網(wǎng)絡(luò)編碼和機(jī)會(huì)路由之后，網(wǎng)絡(luò)的整體性能能夠得到很大改善。但是，傳統(tǒng)的基于網(wǎng)絡(luò)邊編碼的機(jī)會(huì)路由均采用了全網(wǎng)絡(luò)編碼的方式，只有在收到k個(gè)數(shù)據(jù)包之后才能進(jìn)行解碼操作，這無疑增加了數(shù)據(jù)包的等待延遲。因此提出了部分網(wǎng)絡(luò)編碼算法ORoPNC，來降低由于網(wǎng)絡(luò)編碼造成的延遲。

ORoPNC協(xié)議采用了部分網(wǎng)絡(luò)編碼的思想。源節(jié)點(diǎn)只廣播數(shù)據(jù)包而不進(jìn)行編碼，中間節(jié)點(diǎn)在收到若干個(gè)數(shù)據(jù)包后，隨機(jī)選擇數(shù)據(jù)包進(jìn)行編碼，再將數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，從而減少了等待延遲。ORoPNC協(xié)議使用的ETXoEC轉(zhuǎn)發(fā)策略不僅考慮了當(dāng)前鏈路的狀態(tài)，還有節(jié)點(diǎn)的能量消耗。在保證傳輸可靠性的前提下，擁有更多剩余能量的節(jié)點(diǎn)被用來參與數(shù)據(jù)轉(zhuǎn)發(fā)，因此網(wǎng)絡(luò)的整體可靠性得到提升。

［1］ AHLSWEDE R，CAI N，LI S Y R，et al．Network Information Flow［J］．Information Theory，IEEE Transactions on，2000，46(4)：1204 －1216．

［2］ YAN Y，ZHANG B，MOUFTAH H T，et al．Practical Coding-aware Mechanism for Opportunistic Routing in Wireless Mesh Networks［C］∥Communications，2008．ICC＇08．IEEE International Conference on．IEEE，2008：2871 －2876．

［3］ BISWAS S，MORRIS R．ExOR：Opportunistic Multi-hop Routing for Wireless Networks［C］∥ACM SIGCOMM Computer Communication Review．ACM，2005，35(4)：133－144．

［4］ HO T，MEDARD M，KOETTER R，et al．A Random Linear Network Coding Approach to Multicast［J］．Information Theory，IEEE Transactions on，2006，52(10)：4413 －4430．

［5］ LI S Y R，YEUNG R W，CAI N．Linear Network Coding［J］．Information Theory，IEEE Transactions on，2003，49(2)：371 －381．

［6］ CHACHULSKI S，JENNINGS M，KATTI S，et al．Trading Structure for Randomness in Wireless Opportunistic Routing［M］．ACM，2007：200 －205．

［7］ WANG Y，GARCIA-ACEVES J J．Collision Avoidance in Mmulti-hop Ad hoc Networks［C］∥Modeling，Analysis and Simulation of Computer and Telecommunications Systems，2002．MASCOTS 2002．Proceedings．10th IEEE International Symposium on．IEEE，2002：145 －154．

［8］ WANG D，ZHANG Q，LIU J．Partial Network Coding：Theory and Application for Continuous Sensor Data Collection［C］∥Quality of Service，2006．IWQoS 2006．14th IEEE International Workshop on．IEEE，2006：93 －101．

［9］ WANG X D，HUO G C，SUN H Y，et al．An Opportunistic Routing for MANET Based on Partial Network Coding［J］．Dianzi Xuebao(Acta Electronica Sinica)，2010，38(8)：1736 －1740．

［10］ COOPER C．On the Distribution of Rank of a Random Matrix over a Finite Field［J］．Random Structures and Algorithms，2000，17(3 －4)：197 －212．