一種新的基于部分網絡編碼的機會路由機制

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

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

0 引言

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

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

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

提出了一種機會路由協議(ORoPNC)，這一協議將部分網絡編碼引入到機會路由。同時，設計了一種新的ETXoEC轉發策略。在該協議下，前向節點的選擇基于當前鏈路狀態以及節點的剩余能量。

1 部分網絡編碼

1．1 部分網絡編碼思想

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

圖1 全網絡編碼

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

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

圖2 部分網絡編碼

1．2 節點轉發

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

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

2 基于部分網絡編碼的機會路由

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

2．1 節點前向時間的計算

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

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

傳輸時間為:

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

2．2 ETXoEC轉發候選集的選擇策略

在設計轉發候選集時，ETXoEC轉發策略根據當前鏈路狀態和節點剩余能量來選擇轉發節點。對于網絡節點，轉發機會值(OP)可以通過下面的公式計算得到:

3 性能分析

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

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

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

圖3 延遲比較

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

3．2 轉發策略分析

ETXoEC轉發策略綜合考慮了鏈路狀態和節點能量消耗。仿真分析了ETX和ETXoEC這2種采用了網絡編碼的轉發策略，比較了2種策略節點剩余能量的均方差和損失率。

3．2．1 節點剩余能量均方差

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

圖4 節點剩余能量均方差

3．2．2 下降速率

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

圖5 下降速率

4 結束語

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

ORoPNC協議采用了部分網絡編碼的思想。源節點只廣播數據包而不進行編碼，中間節點在收到若干個數據包后，隨機選擇數據包進行編碼，再將數據包進行轉發，從而減少了等待延遲。ORoPNC協議使用的ETXoEC轉發策略不僅考慮了當前鏈路的狀態，還有節點的能量消耗。在保證傳輸可靠性的前提下，擁有更多剩余能量的節點被用來參與數據轉發，因此網絡的整體可靠性得到提升。

［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．