一種基于網絡編碼的無線網絡機會路由算法*

田賢忠，劉 強，胡同森

(浙江工業大學計算機科學與技術學院，杭州 310023)

傳統無線自組織網絡和傳感器網絡的路由協議都采用確定性路由［1－3］方式，即:在端到端的數據傳輸過程中，首先建立一條端到端的節點序列，然后在每次分組轉發時，首先確定一個下一跳節點，再執行鏈路層轉發。如果傳輸過程中發生分組丟失或差錯，則啟動鏈路層重傳。在鏈路質量和穩定性較差的環境下，頻繁的鏈路層數據重傳將消耗大量的帶寬資源。因此，盡管確定性路由方式邏輯簡單，但未能充分考慮無線信道的廣播特性、時變特性和干擾不規則性等特點。無線信道的廣播特性使得一次分組轉發可能被多個節點收到，且接收概率各不相同；無線鏈路的時變特性導致網絡中鏈路的狀態隨時間而改變。路由協議設計過程中如果缺乏對信道廣播和丟失特性的充分考慮，必將導致大量網絡資源無謂浪費，這將嚴重影響網絡的吞吐量及其它性能。

針對無線信道的廣播、時變、丟失特性和確定性路由策略的不足，麻省理工學院(MIT)的Biswas等人于2004年率先提出了機會路由［4－5］的概念。機會路由通過多個潛在中繼節點競爭、自主智能進行下一跳節點選擇。它充分利用了信道廣播特性，提高了網絡的吞吐量和傳輸可靠性。研究機會路由算法［6－8］來提升無線多跳網絡的性能，已成為當前無線自組織網絡與傳感器網絡組網協議研究中的一個重要方向。

網絡 編 碼［9－12］(Network Coding) 技 術 由 R.Ahlswede等人在2000年首次提出的。該技術可以極大地提高網絡的吞吐量和可靠性。如何同時發揮機會路由和網絡編碼的優勢，文獻［13］中的MORE協議對此進行了嘗試。MORE是一個MAC無關的協議，它通過引入網絡編碼解決了數據傳輸過程中節點協作難的問題，即:轉發節點可以不管其他節點發送的是什么數據，而只需要將自己緩存下來的數據進行編碼后轉發出去即可，目的節點收到一定數量的編碼包后解出相應的原數據包。同時它充分利用了網絡的空間關系，通過多個節點的協作轉發數據包，而不是某一個節點轉發。但是它有一個致命的缺陷就是“停止－等待”機制，即網絡中只能存在一段數據，源節點只有收到目的節點的ACK確認信息后才開始發送下一段數據，這樣就影響了網絡的吞吐量。為此，Lin Y［14－15］等人給出了兩種不同的解決方案:文獻［14］同樣是采用分段的形式傳輸，但能夠同時傳輸多個段，效率有一定的提高，但是存在ACK數量較多的問題，它在一定程度上占用了網絡帶寬資源；文獻［15］則從另一個方面入手來解決MORE的問題，它摒棄了段的概念，將數據看成一個很長的流，采用“滑動窗口”的形式進行傳輸，也在一定程度上解決了MORE的問題。文獻［16］則從另一個角度發揮機會路由與網絡編碼的優勢，它用個一種新的確認機制來壓縮傳統ACK確認機制帶來的開銷，在一定程度上改善了網絡的性能。

從上面的分析可以看出，提高網絡的吞吐量需從兩個方面著手:(1)發送ACK確認信息要及時；(2)發的ACK確認信息要少。為此，本文提出一種最大限度的壓縮ACK的機制，我們稱之為MinACK算法。它較為及時地發送ACK，從而允許同時在網絡中傳輸多個數據段；同時每發送一段數據只需回一個ACK，減少了ACK的發送。另外，它還與MAC無關，省去了許多節點之間協作的開銷，從而進一步提高網絡的吞吐量。我們在仿真實驗中也充分證明了MinACK的優勢所在。

1 MinACK基本思想與算法

如圖1所示，在MORE算法中，源節點S首先把要發送的數據包分成相同大小的數據段，每一數據段由K個數據包組成，然后把同一段的K個數據包線性網絡編碼后發送。節點A、B、C在收到源節點S發送過來的編碼包后，與各自之前已收到的同一數據段的編碼包重新編碼后再發送。目的節點D收到K個線性無關的編碼包后解出原始數據包，并發送一個確認信息ACK給源節點S。源節點S在收到ACK后發送下一段數據包。這樣有一個問題，目的節點D在能解碼時，源節點S不能馬上發送下一段的數據包，必須等到收到ACK后才開始發送，這樣造成源節點S延遲發送，影響網絡的吞吐量，在跳數比較多的情況下，這種影響尤為嚴重。

圖1 MinACK原理圖

MinACK的基本思想是:當源節點S向下一跳節點廣播編碼包時，下一跳節點A、B、C由于丟包可能各自只收到部分編碼包，但當節點A、B、C總共收到足夠多(大于等于K個)的線性無關的編碼包后，其中一個節點發送一個確認信息ACK給源節點。源節點在收到ACK確認信息后馬上可以發送下一數據段的數據包。因為這時節點A、B、C中含有足夠多的線性無關編碼包可以發送給目的節點D。這樣源節點不需要等目的節點發送ACK，只需下一跳的節點發送的ACK，節省等待時延。而下一跳的A、B、C三個節點中只有一個節點在它們收到同一數據段的K個線性無關編碼包后才發送一個ACK，這樣ACK的數量也會盡可能的少。

MinACK算法針對源節點、中繼節點和目的節點分三部分:

(1)源節點

①源節點S首先把要發送的數據包分成相同大小的數據段，每個數據段由K個數據包組成，然后把同一段的K個數據包線性編碼產生編碼包。當源節點S競爭獲得信道后向下一跳節點廣播(發送編碼包的個數根據§2.3確定)。

②當源節點S接收到下一跳節點的ACK后，發送下一段的數據包。

(2)中繼節點

①中繼節點v在收到前一跳節點u發送的編碼包后，就與其之前已收到的同一段的編碼包重新編碼后向其下一跳節點廣播(發送編碼包的個數也根據§2.3確定)。這時如果節點v已收到同一段的K個編碼包，就向上一跳節點廣播一個確認信息ACK。

②節點v向下一跳廣播發送編碼包時，其前一跳節點u的其它下一跳節點w也收到了，也就是說節點w不但收到上一跳節點u的編碼包，也收到同層節點v的編碼包。不管哪種情況，節點w對收到的編碼包也判斷是否與之前收到的同一段的編碼包線性相關，如果線性無關就編碼后向其下一跳節點廣播(發送編碼包的個數也根據§2.3確定)。同時判斷如果節點w收到同一段的編碼包個數為K個，就向上一跳節點廣播一個ACK。

③如果節點u收到的是節點v向上一跳節點發送的確認信息ACK，則停止本段編碼包的接收，等待接收下一段編碼包。

(3)目的節點

目的節點D在收到K個編碼包后，解出原始數據包，同時向前一跳節點發送確認信息ACK。

2 MinACK具體實現

上面的算法中，有幾個問題必須明確:(1)如何確定下一跳節點；(2)編碼解碼策略；(3)節點轉發編碼包數目；(4)ACK確認包的格式。

2.1 下一跳節點與上一跳節點

MinACK算法中節點v的下一跳節點是指到目的節點的ETX［17］值比自己小的鄰居節點，即Next(v)={u|ETX(u)＜ETX(v)且u∈Neighbour(v)}其中Neighbour(v)表示節點v的一跳鄰居節點；同樣，節點v的上一跳節點是指到目的節點的ETX值比自己大的鄰居節點，即

網絡中的節點通過周期性的互相探測來獲得每條鏈路的成功傳輸率，ETX值是對應鏈路的成功傳輸率的倒數，表示發送成功一個數據包平均需要發送的次數。節點到目的節點的ETX值等于其路徑上每一跳的ETX之和。每個節點都計算并記錄自己到目的節點的ETX值。根據ETX值可以找到節點的下一跳與上一跳節點。

2.2 編碼解碼策略

編碼包在轉發節點處被重新編碼，易得重新編碼后的包仍然是原始包的線性組合，因為

目的節點一旦接收到同一段的K個線性獨立的編碼包，它就可以用以下方式解碼:

其中PCi'是目的節點接收的編碼包，Pi是原始包，i=(ci1，…，ciK)是編碼包PC'i對應的編碼向量，通過高斯消元即可解碼出原始包。

2.3 節點發送數據包的數目

當一個節點收到一個編碼包后，會觸發其重新編碼后向下一跳節點發送編碼包。那么應該發送多少個編碼包?按傳統方法每收到一個發送一個會帶來兩個問題:①由于丟包，只發送一個包下游節點可能會收不到；②因為節點是廣播編碼包的，所以可能會有多個下一跳節點收到此編碼包，每個收到的節點都發一個包會造成重復發送。其實多個下一跳節點中只需要一個節點發送就可以了。

首先考慮源節點需發送一個數據包時，每個節點需發送的數據包個數。根據文獻［13］，設puv表示節點u到節點v的丟包率，nu表示節點u發送數據包的次數，則節點v收到編碼包的個數為:

實際操作時，在每個節點v中設置一個計數器Countv。首選設Countv=0；每當節點v收到一個編碼包，則 Countv=Countv+npv；這時，如果 Countv＞0，節點v發送一個編碼包，同時Countv=Countv－1。當節點v發送下一數據段時Countv清零。

2.4 ACK 確認包

當節點i知道自己的下一跳節點中已接收到同一數據段的K個編碼包時，節點i就向其上游節點發送一個ACK確認信息。上游節點在收到ACK后刪除緩存中這一段的編碼包，開始發送下一段數據的編碼包。如圖2所示，ACK數據包主要包含三個域:發送節點ID是指發送ACK節點的編號，接收節點ID列表為發送節點的上一跳節點的編號列表，數據段ID告訴接收節點哪一數據段已被其下游節點收到，可以清除緩存中的這段編碼包。

圖2 ACK包格式

3 性能分析

MinACK能在網絡中同時傳輸多個數據段，從而提高網絡的吞吐量。這里分析網絡中能同時傳輸的數據段數以及網絡的吞吐量。

3.1 網絡中能同步傳輸的段數

從MinACK算法中我們可以知道，當某個中繼節點回了一個ACK后，其上一跳節點可以發送下一數據段。我們可以從第二跳節點(和源節點直接相連的節點)發送的ACK數量來判斷網絡中同時傳輸的數據段數:

其中nseg表示網絡中同時存在的數據段數，nack表示第二跳節點回ACK數量，ndestACK是目的節點回的ACK數量。

發送ACK的數量nack和ndestACK仿真實驗與實際傳輸中很容易記錄下來，但理論計算比較難。我們用另一種思路來計算網絡中同時傳輸的數據段數。其實，段數與傳輸一個數據包的跳數有關。如圖3所示，如果數據包從源節點S經節點B發送給目的節點D(下面稱“路徑P1”)，只需兩跳。這時，節點B收到數據包回ACK后，源節點S可以發送下一數據包，網絡中存在兩個數據段。如果源節點S經節點A、B發送給目的節點D(下面稱“路徑P2”)，則數據包發送需要三跳。這時，節點A、B都可以回ACK，網絡中同時存在三段數據段。所以數據段數與傳輸一個數據包的跳數相對應，即

圖3 跳數與段數關系

而傳輸一個數據包的跳數就是傳輸這個數據包時各個節點所要傳輸的次數之和。如圖3，如果采用“路徑P1”節點S需傳輸1次，節點B需傳輸1次，共兩次，與跳數相等；同樣，如果采用“路徑P2”，節點S、A、B各傳輸1次，共3次，也與跳數相等。當傳輸一個數據包，采用“路徑P1”和“路徑P2”的概率都為0.5，則平均跳數為:0.5×2+0.5×3=2.5。而每個節點的傳輸次數分別為S=1，A=0.5，B=1，共2.5次，與平均跳數相等。

在實際網絡中源節點傳輸一個數據包，節點v需傳輸的數據包個數為Lv，根據式(2)，可以求出所有節點的發送次數，即網絡中同時傳輸的數據段數為:

3.2 網絡的吞吐量

網絡的吞吐量是網絡性能的一項重要標志。假設一個數據包發送一次所需時間為t。這里我們忽略計算時間(包括編碼與解碼所需要的時間)，因為計算時間比傳輸時間要小得多，可以忽略不計。首選計算目的節點收到一段數據包(K個編碼包)所需的時間Ttotal。Ttotal包括兩部分:第一個編碼包從源節點傳輸到目的節點的時延T1和目的節點從收到第一個編碼包后到收完其余K－1個編碼包所用的時間T2，即:

因為一個包從源節點傳輸到目的節點的時延為其傳輸次數×t，同時考慮MinACK可以在網絡中同時傳輸多段數據包，得T1值為:

其中ntotal是從源節點傳輸一個數據包到目的節點所有節點傳輸次數，根據式(3)，其值為:

根據式(8)、式(9)、式(11)計算出Ttotal。

網絡吞吐量是單位時間內傳輸的數據量。由前面分析可知，傳輸K個編碼包的時間為Ttotal，假設每個編碼包的大小是M，則吞吐量

4 仿真實驗

本文使用Matlab語言對MinACK協議進行仿真模擬，以觀察在傳輸相同數量的數據包的情況下ExOR、MORE以及MinACK傳輸次數，網絡中存在的段數以及網絡的吞吐量等性能。我們在50 m×50 m的范圍內隨機分布30個節點，每個節點的通信范圍為20 m，節點之間的傳輸概率是根據距離大小隨機產生的(圖4的仿真除外)，每個數據包的大小為M=1000 byte，數據包傳輸一次用時為t=0.1 s。

理論上我們的MinACK和MORE傳輸相同數量的數據包的情況下，他們的傳輸次數是相同的，圖3、圖4均證明了這一點。我們的優勢主要在于MinACK能夠幾段同步傳輸。圖4我們是通過傳輸50個包，改變節點間的傳輸成功率(從0.1到0.9變化)統計三者的傳輸次數得到的。從仿真結果看節點間的傳輸成功率越低，MinACK和MORE的優勢較之ExOR就越明顯；圖5我們是通過改變傳輸包的個數，而節點間的傳輸概率不變得到的。總體上都是隨著數據包的增多，傳輸次數相應的平穩增加，但在相同條件下MinACK、MORE需要的傳輸次數比ExOR要少。

圖4 MinACK、MORE和ExOR的傳輸次數隨節點間的傳輸成功的概率的變化對比

圖5 MinACK、MORE和ExOR的傳輸次數隨傳輸的包的個數變化對比

另外，網絡中多段數據包同步傳輸是MinACK協議的最重要的特征，因此我們對網絡中存在的段數進行了仿真測試。我們將每段數據包的個數設為10到100之間，分別測試網絡中平均存在的段數，并與理論值做了對比，效果如圖6所示，從仿真結果看，MinACK網絡中平均存在3段左右的數據包在同步發送，而我們知道MORE網絡中始終只存在一段數據包，因此MinACK應該比MORE的吞吐量性能好，接下來的吞吐量仿真也充分證明了這一點。

圖6 MinACK在網絡中存在的段數與理論值對比

最后，吞吐量性能是所有網絡協議要考慮的重要特性之一，因此我們也對吞吐量性能進行了仿真實驗，仿真結果如圖7和圖8所示。

圖7 MinACK、MORE和ExOR的吞吐量隨每段中數據包的個數變化對比

圖8 MinACK、MORE和ExOR的吞吐量隨傳輸的包的個數的變化對比

圖7是我們通過傳輸500個數據包，讓K(每段中數據包的個數)從10到100之間變化得到的，從仿真結果看隨著K的增大，三者的吞吐量相差越來越小；圖8中K固定為50，通過改變傳輸數據包的個數得到的，從仿真結果可以看出，三者的吞吐量隨傳輸包的個數變化不大。在K較小的新情況下，MORE的吞吐量大概是ExOR的1.2倍左右，MinACK的吞吐量大概是MORE的1.2倍左右，是ExOR的的1.45倍左右，可見吞吐量性能有了不少的提高。

5 小結

本文提出了一種基于網絡編碼的機會路由算法－MinACK，它結合了網絡編碼與機會路由的優點，通過在網絡中同時傳輸多個數據段，提高了網絡的吞吐量。同時分析了網絡中同時傳輸的數據段數和網絡吞吐量等性能。

不同的網絡中數據流有自己的特點，比如數據包的到達服從某種分布。如何利用網絡編碼，結合數據流的特點定量化地研究無線網絡的傳輸機制是作者下一步要研究的內容。

［1］程大偉，趙海，張希元，等.基于EWMA的無線傳感器網絡路由度量性研究［J］.傳感技術學報，2008，21(1):103－108.

［2］Garcia P J，Duato J，Flich J，et al.Cost-Effective Congestionmanagement for Interconnection Networks Using Distributed Deterministic Routing［C］//IEEE，International Conference on，Parallel and Distributed Systems，Univ of Castilla-La Mancha，Albacete，Spain，Dec 2010:355－364.

［3］程遠國，李國徽.一種面向目標跟蹤應用的傳感器網絡路由協議［J］.傳感技術學報，2008，21(10):1744－1749.

［4］Biswas S，Morris R.Opportunistic Routing in Multi-Hop Wireless Networks［J］.In ACM SIGCOMM Computer ommunications Review，Jan 2004，34(1):69－74.

［5］Biswas S，Morris R.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks［J］.ACM SIGCOMM Computer Communication Review，Aug 2005，35(4):133－144.

［6］Koetter R，M’edard M.An Algebraic Approach to Network Coding［J］.IEEE/ACM Transactionson on Networking，2003，11(5):782－795.

［7］Rozner E，Seshadri J，Mehta Y，et al.Simple Opportunistic Routing Protocol for Wireless Mesh Networks［C］//Proc IEEE Workshop on，Wireless Mesh Networks，Univ of Texas，Austin，Sept 2006:48－54.

［8］Rozner E，Seshadri J，Mebta Y，et al.SOAR:Simple Opportunistic Adaptive Routing Protocol for Wireless Mesh Networks［J］.In IEEE Transactions on Mobile Computing，Dec 2009，8(12):1622－1635.

［9］Jaggi S，Sanders P，Chou P A，et al.Polynomial Time Algorithms for Multicast Network Code Construction［J］.IEEE Transaction on Information Theory，2005，51(6):1973－1982.

［10］Li S Y，Yeung R W，Cai N.Linear Network Coding［J］.IEEE Transactions on Information Theory，2003，49(2):371－381.

［11］Ahlswede R，Cai N，Yeung R W，et al.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［12］熊志強，劉威，程文青，等.基于網絡編碼的傳感器網絡信息交換算法研究［J］.傳感技術學報，2008，21(1):141－146.

［13］Chachulski S，Jennings M，Katti S，et al.Trading Structure for Randomness in Wireless Opportunistic Routing［J］.ACM SIGCOMM Computer Communication Review，2007，37(4):169－180.

［14］Lin Y F，Li B C，Liang B.CodeOR:Opportunistic Routing in Wireless Mesh Networks with Segmented Network Coding［C］//Proc of IEEE International Conference on，Network Protocols，Univ of Toronto，Canada，Dec 2008:13－22.

［15］Lin Y F，Li B C，Liang B.Slideor:Online Opportunistic Network Coding in Wireless Mesh Networks［C］//IEEE INFOCOM International Conference on，Computer Communications，Univ of Toronto，Toronto，Canada，2010:171－175.

［16］Koutsonikolas D，Wang C C，Hu Y.CCACK:Efficient Network Coding Based Opportunistic Routing Through Cumulative Coded Acknowledgments［C］//IEEE INFOCOM Conference on，Computer Communications，Purdue Univ，West Lafayette，USA，Mar 2010:1－9.

［17］Couto D De，Aguayo D，Bicket J，et al.A High-Throughput Path Metric for Multi-Hop Wireless Routing［J］.ACM/IEEE MobiCom，2003，11(4):419－434.