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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2．1 節(jié)點前向時間的計算

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

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

傳輸時間為:

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

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

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

3 性能分析

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

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

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

圖3 延遲比較

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

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

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

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

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

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

3．2．2 下降速率

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

圖5 下降速率

4 結(jié)束語

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

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