一種移動Ad Hoc網絡的冗余網絡編碼方法*

(廣西大學 計算機與電子信息學院，南寧 530004)

1 引 言

移動Ad Hoc網絡(MANET)由一組無線移動節點組成，網絡中的各個節點互相協作,通過無線鏈路進行通信、交換信息，實現信息和服務的共享。網絡編碼是進入21世紀后通信領域的一項重大突破,是Ahlswede等人[1]于2000年提出的，融合了編碼和路由的概念，允許節點對來自不同鏈路的數據分組進行編碼組合，使得網絡性能可以達到最大流傳輸的理論極限。網絡編碼已經被成功地引入到了移動Ad Hoc網絡的應用中。Katti等[2]提出的基于機會的網絡編碼方案COPE，則是首次研究網絡編碼在無線環境中的協議面上具體實現的問題。文獻[3]在COPE的基礎上，提出了一種以條件鏈路消耗作為路由判據,支持網絡編碼的無線Mesh路由協議，網絡中的節點對數據編碼組合后，選擇條件消耗值最小的路徑傳輸編碼后的分組。文獻[4]中闡述了網絡編碼在移動Ad Hoc網絡中對傳輸可靠性的影響。文獻[5]提供了一種編碼在移動Ad Hoc網絡更加有效的方案，在采用文獻[4]隨機網絡編碼方案的基礎上，加入了對網絡中編碼包的在插入時間及位置的優化選取。但是在目前的研究中，很少考慮到鏈路丟失的情況。網絡編碼能夠使無線網絡的吞吐量獲得較大的提高，基本上是基于網絡環境較好的條件下得出的。在傳輸鏈路存在較高的丟失率的情況下，網絡編碼相對傳統路由的優勢不能完全體現。

本文提出一種基于移動Ad Hoc網絡的冗余編碼方法，采用二元編碼方式，通過增加傳輸冗余度，使得存在鏈路丟包率的條件下，能夠保證網絡編碼傳輸的可靠性，最大化網絡編碼效率。

2 冗余傳輸及二元網絡編碼

2.1 網絡編碼傳輸冗余度舉例

基于機會的網絡編碼方案COPE[2]，則是首次研究網絡編碼在無線環境中的協議面上具體實現的問題。在COPE方案中，每個節點編碼組合數據后，進行基于機會的路由。在網絡中，若是采用異或方式進行編碼，而減輕全局協作和信息集合所帶來的網絡負載，相對于無編碼的網絡，毫無疑問COPE方案在有損無線環境中的傳輸效果是最佳的。如果不考慮傳輸的冗余度，那么傳輸次數也是最少的。我們稱這樣的傳輸方式為最簡化網絡編碼方式(Minimalist Network Coding)。但是，無線鏈路往往是有損鏈路，在Ad Hoc或Mesh網絡中的無線鏈路的丟包率在不太理想的環境下可能達到30%甚至更高[6]。

在下面的一個簡單的二元碼流傳輸例子中，我們將會看到增加傳輸次數的冗余度所帶來的效果。

假設節點A和節點B是無線網絡中的兩個節點，節點A要將數據包Pa傳給節點B，同樣地，節點B將數據包Pb傳給節點A。它們都在對方的通信范圍之外，所以需要一個中繼節點R來轉播數據包(如圖1)。

圖1 二元傳輸模型Fig.1 Two-flow transmission model

方案一：采用COPE協議傳輸，即中繼節點R接收到節點A和節點B傳送的數據包Pa和Pb后，對兩個數據包進行編碼操作，得到Pc=Pa⊕Pb，然后將數據包Pc廣播至A和B兩個目的節點。假設鏈路R→A,R→B為有損鏈路，丟包率為p，則整個傳輸過程的傳輸成功率為(1-p)。

方案二：采用COPE-duplication方式(簡稱COPE-dup)。這種傳輸方式前面的操作與方案一相同，不同的地方在于將編碼后的數據包Pc重復傳送。若傳輸Pc兩次，則傳輸成功率為(1-p2)。

如圖2所示，在鏈路丟包率逐漸升高的情況下，COPE-dup的傳輸成功率高于COPE的傳輸成功率。它通過增加傳輸冗余度(或編碼冗余度)來提升網絡的傳輸質量，保證了更穩定的傳輸率。

圖2 有損鏈路中兩種傳輸方式丟包率的比較Fig.2 Packet loss rate of two transmission schemes in lossy-link

2.2 二元網絡編碼的引入

移動Ad Hoc網絡的無線傳輸鏈路為有損鏈路，因此每個編碼包或者原始數據包能被傳輸到達下一跳節點Ni存在一定的概率。由于接收到的數據包不同，Ni會存在一定的解碼率(即成功解出所需包，也稱作傳輸成功率)，這個概率與鏈路丟包率和編碼方法有關。在最初的編碼方法中，只考慮機會編碼的思想，即通過增加編碼機會來獲取吞吐量的提高。但如果僅僅依靠機會編碼的單個編碼包的獲得進行解碼，就會使得解碼率依賴于編碼包的傳輸率。所以本文提出一種通過增加編碼包冗余度的優化編碼方法，使得目的節點能通過至少兩種解碼方式來提高傳輸成功率。

在Ad Hoc網絡中，我們首先關心的是傳輸的吞吐量。應用適當的網絡編碼方法，能使網絡的吞吐量得到相應提高。而傳輸吞吐量的計算可以表示為每單位時間成功解碼數據包的平均數，也就是∑qi(S)/|S|。因此，獲得最佳性能的編碼方法就是求得∑qi(S)/|S|的最大值。

但是，求解上述最大值的問題是一個十分復雜的非線性方程組，現行的網絡節點沒有足夠的計算能力來解決這樣的問題。所以我們考慮一個最簡單的編碼方法，將最多可編碼數據包的數量限定為2個(即1個編碼包中只含有2個原始數據包)。我們稱這種編碼形式為二元編碼。

假設n個數據包P={P1,P2,…,Pn}將通過中繼節點σ傳送至目的節點D={D1,D2,…,Dn}。建立圖H(V,E)，圖H的頂點集定義為V(H)=P∪D∪{σ}。圖H的邊集E(H)可以分為以下4種類型：

類型1——(Pi,Pj)：表示數據包Pi和Pj的雙向鏈路,且該鏈路存在編碼包Pi⊕Pj的傳輸;

類型2——(Pi,σ)：表示Pi至節點σ的有向鏈路,且該鏈路存在原始數據包Pi的傳輸;

類型3——(σ,Nj)：表示中繼節點σ至每個接收節點Nj之間有向鏈路;

類型4——(Pi,Nj)：表示節點Nj能接收到數據包Pi的鏈路。

一個有效的編碼方法可以表示為以P∪{σ}為頂點集的圖H的誘導子圖的邊集,邊(Pi,Pj)代表編碼分組Pi⊕Pj的傳輸,邊(Pi,σ)代表原始數據包的傳輸。

由于傳輸鏈路存在丟包率，目的節點Ni不可能接收到所有的數據包。因此,目的節點Ni通過接收到的編碼包能解出所需包Pi的概率(即傳輸成功率)由鏈路丟包率和編碼方法決定。

我們建立一個有關下一跳節點Ni的子圖H(i)，它應該表示為：

(1)類型3和類型4的所有邊集；

(2)以成功發送或接收的P∪{σ}為頂點集的邊誘導子集。

那么，只要滿足定理1，節點Ni就能解碼出所需數據包Pi。

定理1：若編碼包只含有兩個原始數據包，則下一跳節點Ni當且僅當圖H(i)中Pi至節點Ni之間存在一條有向鏈路時能解碼出數據包Pi。[7]

在設計有效編碼方法的時候，我們必須遵循上述定理才能獲得最優的編碼方案。同時，可以得出推論1。

推論1：如果每個接收節點都存在傳送或者“偵聽獲得”一個原始數據包，那么就能夠設計出一個有效的編碼方案[8]。

2.3 二元網絡編碼問題的轉化

若想要解決鏈路丟失的二元編碼問題，即找到∑qi(S)/|S|的最大值是很難的。因此，我們把最值問題轉化為另外一種表達形式，來找到最優的編碼方法[8]。

假設S是理想的編碼方法，它是頂點集P∪{s}的誘導子圖的邊子集。對于每個i，數據包Pi能被節點Ni成功解碼的概率計算方式如下：給定S中每條邊的ri(ri為中繼節點至下一跳節點Ni的路徑的傳輸成功率)。給S中每條邊ri設定一個權重。對于邊(Pi,Nj)，權重為節點Ni已經存在數據包Pj的概率(如果確定存在，該值為1)。類型4的邊權重值為1,其它類型的值為0。數據包Pi在編碼方法S下能被節點Ni成功解碼的概率qi(S)可以表示為在圖中擁有一條從節點Pi到節點Ni傳輸路徑的概率。因此問題可以表述為minS|S|，約束條件是qi(S)≥p，?i=1,2,…,n，其中p是預先設定的傳輸成功率。

選擇的路徑必須包括S∪{(σ,Ni)}，不過ki條不相交路徑可以有共用邊(σ,Nj)，那么設計冗余編碼方法問題轉化成為minS|S|，同時滿足以下條件：

3 冗余網絡編碼方法

3.1 編碼方法描述

通過上述問題的轉化，本文提出一種冗余編碼方法。假設(Pi,Ni)表示將數據包Pi傳送到節點Ni的路徑。我們創建圖H，并根據(Pi,Ni)的每條傳輸路徑的傳輸成功率ri由小到大排序。對于每條(Pi,Ni)，我們根據連續最短路徑算法[9]得到圖H的互不相交的最小成本路徑。單條路徑成本的計算方法為：若之前已存在有(Pj,Nj)的傳輸，則路徑成本值為0；否則，成本值為1。每增加一條路徑，我們就計算傳輸成功率qi(S)。當qi(S)達到或超過我們所設定的傳輸率閾值p，或者沒有新的路徑加入，則停止計算。冗余編碼方法為在所得到的互不相交的最小成本路徑中選擇類型1的路徑，然后根據所選路徑(Pi,Pj)得出編碼包Pi⊕Pj進行傳輸。

3.2 冗余編碼方法舉例

為了能更好地說明冗余編碼方法對網絡傳輸和編碼的性能改善，下面通過一個簡單的例子來闡述。

如圖3所示，中繼節點R被6個鄰居節點N1,N2,…,N6所包圍。每個節點都在其相鄰節點的通信范圍內，同時又在除相鄰節點的其它節點范圍之外，所以非相鄰節點的數據要進行傳輸或交換，則必須通過中繼節點。并假設各條傳輸鏈路中只有中繼節點R到下一跳節點Ni的鏈路存在丟包率p，其余鏈路均為無損鏈路。

下面假設節點相互間數據包的傳輸為以下情況：P1,N5→N1;P2,N6→N2;P3,N1→N3;P4,N2→N4;P5,N3→N5;P6,N4→N6。

在圖3中還描述了每個節點擁有的數據包。例如，節點N1擁有數據包{P2,P3,P4}。因為節點N1是數據包P3的源節點，另外兩個數據包是節點N1在節點N2和N6分別傳輸數據包P4和P2時“偵聽獲得”得到。其它節點的情況類似。

圖3 編碼傳輸模型Fig.3 Network coding transmission model

如果通過傳統路由傳輸，即不通過網絡編碼進行傳輸，則需要進行6次原始數據包的傳送完成整個傳輸過程(即節點收到所需數據包)。如果通過一般網絡編碼方式傳輸，則編碼方法為根據交換數據包的兩個節點得出編碼包，因此編碼方案為(P1⊕P3,P3⊕P5,P5⊕P1,P2⊕P4,P4⊕P6,P6⊕P2)，共需要6次傳輸來完成。顯然，節點Ni接收到數據包后能夠有2種途徑解碼出所需包?？紤]鏈路丟包率p，則一般的編碼傳輸數據包的傳輸成功率為qi(S)=1-p·[1-(1-p)k-1]，其中k為發送的編碼包數。

根據提出的冗余編碼方法，我們設定所選用于計算的傳輸路徑的最小成本路徑數為2，那么，計算后得出發送編碼包組為(P3⊕P4,P5⊕P3,P1⊕P4,P1⊕P5,P6⊕P1,P2⊕P6,P3⊕P2)。很明顯，在冗余編碼方法中，我們需要傳輸7組編碼包，相比一般的編碼算法多了一次冗余包傳輸。節點得到編碼包后，可以通過至少2種解碼方式解出所需數據包。

3.3 仿真實驗分析

本文的仿真實驗環境采用圖3所示的編碼傳輸模型，節點傳輸要求與前述例子中一致，實驗結果通過Matlab進行模擬計算。

圖4表明了傳統路由傳輸、網絡編碼傳輸和冗余網絡編碼傳輸3種傳輸方式在仿真模型中關于傳輸成功率的比較。顯然，無編碼的傳統路由方式傳輸成功率最低,冗余傳輸編碼方法的傳輸成功率最高。這是因為我們設定了只選擇所有滿足條件的傳輸路徑中的2條不相交路徑作計算，但可能還存在其它的不相交路徑，這就使得節點可以通過不少于2種解碼方式獲取到所需數據包，有效降低了鏈路丟包率對傳輸質量的影響。例如，節點N1可以通過以下3種方式解碼出數據包P1：P1⊕P4；P1⊕P6,P6⊕P2；P1⊕P6,P6⊕P5,P5⊕P3。而對于一般網絡編碼方式，節點N1最多能通過兩種方式解碼出數據包P1：P1⊕P3；P3⊕P5,P5⊕P1。

圖4 不同鏈路丟包率下3種傳輸方式的傳輸成功率比較Fig.4 Transmission success rate of three transmission schemes versus link loss rate

圖5表示N個信息交換節點采用冗余編碼方法的傳輸成功率的比較?？梢钥吹?，接收節點越少，傳輸成功率越高。這是由于傳輸節點越多，就存在越多的傳輸路徑，也就存在更多的最小成本路徑，由于傳輸成功率是有關多條不相交最小成本路徑連乘的函數，鏈路丟包率的增加會使傳輸成功率呈指數下降。盡管如此，冗余編碼方法相對一般網絡編碼方法而言，受制于鏈路丟包率的影響更小。

圖5 采用冗余編碼方法，N個不同接收節點的傳輸成功率比較Fig.5 Transmission success rate of N different receiving nodes in post-redundancy coding strategy

圖6表示鄰居節點偵聽獲取數據包的不同概率條件下，選取不同k值(即傳輸路徑的最小成本路徑數)所得到的編碼包數量。根據冗余編碼方法可以得出，選取的k值越大，編碼傳輸的可靠性就越高。但同時在圖中可以看出，選取的k值越大，所需的編碼包，即需要傳輸的編碼包數量也隨之增加。所以，如何選擇合適的k值，要根據網絡負載和鄰居節點偵聽獲取原始數據包的概率來綜合考慮。

圖6 編碼方法采用不同k值的傳輸次數比較Fig.6 Transmission times for different values of k

4 結 論

本文針對現存的移動Ad Hoc網絡的網絡編碼方法傳輸成功率不穩定的問題，利用圖論中邊-集的概念及相關理論，引出傳輸冗余度，提出一種基于冗余傳輸的網絡編碼方法。仿真結果表明，在網絡存在較高丟包率的情況下，冗余網絡編碼方法的傳輸成功率比一般網絡編碼方法高出5個百分點，同時網絡的吞吐量不受任何影響，仍能使網絡傳輸成功率保持較高水平。在信息交換的節點數目增加的情況下，信息包的冗余度稍有增加，但傳輸成功率基本保持穩定。

參考文獻：

[1] Ahlswede R,Cai N,Yeung R.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.

[2] Katti S,Hu W,Medard M.The importance of being opportunistic: Practical network coding for wireless environments[C]//Proceedings of the 43rd Annual Allerton Conference on Communication, Control, and Computing Monticello.2005:134-144.

[3] 覃團發,廖素蕓,羅會平,等.支持網絡編碼的無線Mesh網絡路由協議[J].北京郵電大學學報，2009，32(1):14-18.

QIN Tuan-fa, LIAO Su-yun,LUO Hui-ping,et al.A network coding aware routing protocol in wireless mesh network[J]. Journal of Beijing University of Posts and Telecommunications,2009,32(1):14-18.(in Chinese)

[4] Lun D S, M′edard M，Effros M.On coding for reliable communication over packet networks[C]//Proceedings of the 42nd Annual Allerton Conference on Communication,Control,and Computing.2004:3-20.

[5] Lun D S,Ratnaker N,Medard M,et al.Minimum-cost multicast over coded packet networks[J].IEEE Transactions on Information Theory,2006,52(6):2608-2623.

[6] Aguayo D,Bicket J,Biswas S,et al.Link-level measurements from an 802.11b mesh network[C]//Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications.[S.l.]:[s.n.],2004:121-132.

[7] Katti S，Hu W，Medard M.XORs in the air: Practical network coding [C]//Proceedings of ACM SIGCOMM.[S.l.]:[s.n.],2006:243-254.

[8] Shravan Rayanchu,Sen Sayandeep,Wu Jianming,et al.Loss-aware network coding for unicast wireless sessions: Design, Implementation, and Performance Evaluation [J].SIGMETRICS Perform. Eval.Rev,2008,36(1):85-96.

[9] Ahuja R K,Magnanti T L,Orlin J B.Network Flows:Theory,Algorithms,and Applications[M].Newyork:Prentice-Hall,1993.