一種移動(dòng)Ad Hoc網(wǎng)絡(luò)的冗余網(wǎng)絡(luò)編碼方法*

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004)

1 引 言

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

本文提出一種基于移動(dòng)Ad Hoc網(wǎng)絡(luò)的冗余編碼方法，采用二元編碼方式，通過增加傳輸冗余度，使得存在鏈路丟包率的條件下，能夠保證網(wǎng)絡(luò)編碼傳輸?shù)目煽啃?，最大化網(wǎng)絡(luò)編碼效率。

2 冗余傳輸及二元網(wǎng)絡(luò)編碼

2.1 網(wǎng)絡(luò)編碼傳輸冗余度舉例

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

在下面的一個(gè)簡(jiǎn)單的二元碼流傳輸例子中，我們將會(huì)看到增加傳輸次數(shù)的冗余度所帶來的效果。

假設(shè)節(jié)點(diǎn)A和節(jié)點(diǎn)B是無線網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)A要將數(shù)據(jù)包Pa傳給節(jié)點(diǎn)B，同樣地，節(jié)點(diǎn)B將數(shù)據(jù)包Pb傳給節(jié)點(diǎn)A。它們都在對(duì)方的通信范圍之外，所以需要一個(gè)中繼節(jié)點(diǎn)R來轉(zhuǎn)播數(shù)據(jù)包(如圖1)。

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

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

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

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

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

2.2 二元網(wǎng)絡(luò)編碼的引入

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

在Ad Hoc網(wǎng)絡(luò)中，我們首先關(guān)心的是傳輸?shù)耐掏铝?。?yīng)用適當(dāng)?shù)木W(wǎng)絡(luò)編碼方法，能使網(wǎng)絡(luò)的吞吐量得到相應(yīng)提高。而傳輸吞吐量的計(jì)算可以表示為每單位時(shí)間成功解碼數(shù)據(jù)包的平均數(shù)，也就是∑qi(S)/|S|。因此，獲得最佳性能的編碼方法就是求得∑qi(S)/|S|的最大值。

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

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

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

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

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

類型4——(Pi,Nj)：表示節(jié)點(diǎn)Nj能接收到數(shù)據(jù)包Pi的鏈路。

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

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

我們建立一個(gè)有關(guān)下一跳節(jié)點(diǎn)Ni的子圖H(i)，它應(yīng)該表示為：

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

(2)以成功發(fā)送或接收的P∪{σ}為頂點(diǎn)集的邊誘導(dǎo)子集。

那么，只要滿足定理1，節(jié)點(diǎn)Ni就能解碼出所需數(shù)據(jù)包Pi。

定理1：若編碼包只含有兩個(gè)原始數(shù)據(jù)包，則下一跳節(jié)點(diǎn)Ni當(dāng)且僅當(dāng)圖H(i)中Pi至節(jié)點(diǎn)Ni之間存在一條有向鏈路時(shí)能解碼出數(shù)據(jù)包Pi。[7]

在設(shè)計(jì)有效編碼方法的時(shí)候，我們必須遵循上述定理才能獲得最優(yōu)的編碼方案。同時(shí)，可以得出推論1。

推論1：如果每個(gè)接收節(jié)點(diǎn)都存在傳送或者“偵聽獲得”一個(gè)原始數(shù)據(jù)包，那么就能夠設(shè)計(jì)出一個(gè)有效的編碼方案[8]。

2.3 二元網(wǎng)絡(luò)編碼問題的轉(zhuǎn)化

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

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

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

3 冗余網(wǎng)絡(luò)編碼方法

3.1 編碼方法描述

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

3.2 冗余編碼方法舉例

為了能更好地說明冗余編碼方法對(duì)網(wǎng)絡(luò)傳輸和編碼的性能改善，下面通過一個(gè)簡(jiǎn)單的例子來闡述。

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

下面假設(shè)節(jié)點(diǎn)相互間數(shù)據(jù)包的傳輸為以下情況：P1,N5→N1;P2,N6→N2;P3,N1→N3;P4,N2→N4;P5,N3→N5;P6,N4→N6。

在圖3中還描述了每個(gè)節(jié)點(diǎn)擁有的數(shù)據(jù)包。例如，節(jié)點(diǎn)N1擁有數(shù)據(jù)包{P2,P3,P4}。因?yàn)楣?jié)點(diǎn)N1是數(shù)據(jù)包P3的源節(jié)點(diǎn)，另外兩個(gè)數(shù)據(jù)包是節(jié)點(diǎn)N1在節(jié)點(diǎn)N2和N6分別傳輸數(shù)據(jù)包P4和P2時(shí)“偵聽獲得”得到。其它節(jié)點(diǎn)的情況類似。

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

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

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

3.3 仿真實(shí)驗(yàn)分析

本文的仿真實(shí)驗(yàn)環(huán)境采用圖3所示的編碼傳輸模型，節(jié)點(diǎn)傳輸要求與前述例子中一致，實(shí)驗(yàn)結(jié)果通過Matlab進(jìn)行模擬計(jì)算。

圖4表明了傳統(tǒng)路由傳輸、網(wǎng)絡(luò)編碼傳輸和冗余網(wǎng)絡(luò)編碼傳輸3種傳輸方式在仿真模型中關(guān)于傳輸成功率的比較。顯然，無編碼的傳統(tǒng)路由方式傳輸成功率最低,冗余傳輸編碼方法的傳輸成功率最高。這是因?yàn)槲覀冊(cè)O(shè)定了只選擇所有滿足條件的傳輸路徑中的2條不相交路徑作計(jì)算，但可能還存在其它的不相交路徑，這就使得節(jié)點(diǎn)可以通過不少于2種解碼方式獲取到所需數(shù)據(jù)包，有效降低了鏈路丟包率對(duì)傳輸質(zhì)量的影響。例如，節(jié)點(diǎn)N1可以通過以下3種方式解碼出數(shù)據(jù)包P1：P1⊕P4；P1⊕P6,P6⊕P2；P1⊕P6,P6⊕P5,P5⊕P3。而對(duì)于一般網(wǎng)絡(luò)編碼方式，節(jié)點(diǎn)N1最多能通過兩種方式解碼出數(shù)據(jù)包P1：P1⊕P3；P3⊕P5,P5⊕P1。

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

圖5表示N個(gè)信息交換節(jié)點(diǎn)采用冗余編碼方法的傳輸成功率的比較。可以看到，接收節(jié)點(diǎn)越少，傳輸成功率越高。這是由于傳輸節(jié)點(diǎn)越多，就存在越多的傳輸路徑，也就存在更多的最小成本路徑，由于傳輸成功率是有關(guān)多條不相交最小成本路徑連乘的函數(shù)，鏈路丟包率的增加會(huì)使傳輸成功率呈指數(shù)下降。盡管如此，冗余編碼方法相對(duì)一般網(wǎng)絡(luò)編碼方法而言，受制于鏈路丟包率的影響更小。

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

圖6表示鄰居節(jié)點(diǎn)偵聽獲取數(shù)據(jù)包的不同概率條件下，選取不同k值(即傳輸路徑的最小成本路徑數(shù))所得到的編碼包數(shù)量。根據(jù)冗余編碼方法可以得出，選取的k值越大，編碼傳輸?shù)目煽啃跃驮礁?。但同時(shí)在圖中可以看出，選取的k值越大，所需的編碼包，即需要傳輸?shù)木幋a包數(shù)量也隨之增加。所以，如何選擇合適的k值，要根據(jù)網(wǎng)絡(luò)負(fù)載和鄰居節(jié)點(diǎn)偵聽獲取原始數(shù)據(jù)包的概率來綜合考慮。

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

4 結(jié) 論

本文針對(duì)現(xiàn)存的移動(dòng)Ad Hoc網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼方法傳輸成功率不穩(wěn)定的問題，利用圖論中邊-集的概念及相關(guān)理論，引出傳輸冗余度，提出一種基于冗余傳輸?shù)木W(wǎng)絡(luò)編碼方法。仿真結(jié)果表明，在網(wǎng)絡(luò)存在較高丟包率的情況下，冗余網(wǎng)絡(luò)編碼方法的傳輸成功率比一般網(wǎng)絡(luò)編碼方法高出5個(gè)百分點(diǎn)，同時(shí)網(wǎng)絡(luò)的吞吐量不受任何影響，仍能使網(wǎng)絡(luò)傳輸成功率保持較高水平。在信息交換的節(jié)點(diǎn)數(shù)目增加的情況下，信息包的冗余度稍有增加，但傳輸成功率基本保持穩(wěn)定。

參考文獻(xiàn)：

[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] 覃團(tuán)發(fā),廖素蕓,羅會(huì)平,等.支持網(wǎng)絡(luò)編碼的無線Mesh網(wǎng)絡(luò)路由協(xié)議[J].北京郵電大學(xué)學(xué)報(bào)，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.