陳志剛，沈小建,，劉立

?

無(wú)線mesh網(wǎng)中最小編碼代價(jià)低時(shí)延多播路由

陳志剛1，沈小建1,2，劉立2

（1. 中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長(zhǎng)沙410083；2. 湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院，湖南株洲412007）

提出了一種無(wú)線mesh網(wǎng)中最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由協(xié)議(MNCLDMR, minimal network coding and low delay multicast routing)。MNCLDMR的目標(biāo)是選擇合適的網(wǎng)絡(luò)編碼節(jié)點(diǎn)，最小化網(wǎng)絡(luò)編碼代價(jià)，降低網(wǎng)絡(luò)時(shí)延。MNCLDMR主要思想是引入拓?fù)潢P(guān)鍵節(jié)點(diǎn)和網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)的概念，以下一跳的節(jié)點(diǎn)是否是網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)或拓?fù)潢P(guān)鍵節(jié)點(diǎn)作為路由判據(jù)，采用MNCLD算法構(gòu)造多播樹(shù)。仿真結(jié)果表明，MNCLDMR可以達(dá)到預(yù)定目標(biāo)，合理形成網(wǎng)絡(luò)編碼機(jī)會(huì)，能實(shí)現(xiàn)最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由。

無(wú)線mesh網(wǎng)；最小代價(jià)；網(wǎng)絡(luò)編碼；低時(shí)延；多播路由

1 引言

在傳統(tǒng)的網(wǎng)絡(luò)中，中繼節(jié)點(diǎn)只存儲(chǔ)轉(zhuǎn)發(fā)接收到的信息，這有時(shí)會(huì)造成網(wǎng)絡(luò)資源的浪費(fèi)。網(wǎng)絡(luò)編碼允許網(wǎng)絡(luò)中的中繼節(jié)點(diǎn)將接收到的信息重新組合，然后多播轉(zhuǎn)發(fā)出去[1]。因此，網(wǎng)絡(luò)編碼突破了中繼節(jié)點(diǎn)只存儲(chǔ)轉(zhuǎn)發(fā)的限制，能更好地利用網(wǎng)絡(luò)資源。無(wú)線mesh網(wǎng)中引入網(wǎng)絡(luò)編碼的作用[2]是提高網(wǎng)絡(luò)吞吐量和安全性，減小傳輸延遲，增強(qiáng)網(wǎng)絡(luò)健壯性等。

網(wǎng)絡(luò)編碼感知的無(wú)線mesh網(wǎng)路由的研究是現(xiàn)在研究的熱點(diǎn)[3~6]。有關(guān)基于網(wǎng)絡(luò)編碼最小代價(jià)路由的研究不少[7~11]。文獻(xiàn)[7]提出了一個(gè)基于最小網(wǎng)絡(luò)編碼次數(shù)的多播路由算法來(lái)改善多播性能。提出了2個(gè)啟發(fā)式準(zhǔn)則，旨在建立具有較低的網(wǎng)絡(luò)編碼代價(jià)和較高的多播性能的多播路由。文獻(xiàn)[8]從編碼節(jié)點(diǎn)數(shù)的角度來(lái)解決復(fù)雜性問(wèn)題，通過(guò)減少編碼節(jié)點(diǎn)的數(shù)目來(lái)減少?gòu)?fù)雜性。文獻(xiàn)[9]在靜態(tài)多播中將網(wǎng)絡(luò)編碼最小代價(jià)問(wèn)題簡(jiǎn)化為一個(gè)多項(xiàng)式時(shí)間內(nèi)可解的優(yōu)化問(wèn)題，提出了用分散算法來(lái)解決。對(duì)于動(dòng)態(tài)多播，Desmond等將網(wǎng)絡(luò)編碼最小代價(jià)問(wèn)題簡(jiǎn)化為一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，并用動(dòng)態(tài)規(guī)劃理論來(lái)解決。文獻(xiàn)[10]提出了一種基于關(guān)鍵鏈路的最小代價(jià)網(wǎng)絡(luò)編碼算法，能有效降低網(wǎng)絡(luò)編碼的代價(jià)。文獻(xiàn)[11]提出了一種基于動(dòng)態(tài)冗余控制的無(wú)線mesh網(wǎng)絡(luò)編碼機(jī)會(huì)路由協(xié)議，與經(jīng)典的MORE協(xié)議相比，該協(xié)議能提高30%~100%的網(wǎng)絡(luò)吞吐量，同時(shí)降低20%~45%的歸一化開(kāi)銷。

利用網(wǎng)絡(luò)編碼減少傳輸時(shí)延的研究也是現(xiàn)在研究的熱點(diǎn)[12~19]。盧冀等[12]提出了一種基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的廣播傳輸算法，有效地提高了廣播傳輸效率并降低了傳輸時(shí)延。Sameh等[13]提出了一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)選擇算法，有效地減少了一幀廣播數(shù)據(jù)分組的平均完成延遲，其計(jì)算復(fù)雜度與隨機(jī)性和貪婪選擇算法的計(jì)算復(fù)雜度一樣。文獻(xiàn)[14]提出了適用于無(wú)線單跳網(wǎng)絡(luò)的倒序搜索網(wǎng)絡(luò)編碼(RSNC)算法和二分搜索網(wǎng)絡(luò)編碼(BSNC)算法。在編碼增益保持不變的前提下能夠有效地減少分組判斷次數(shù)，提高編碼搜索效率，降低數(shù)據(jù)分組的平均端到端時(shí)延。楊奎武等[15]提出一種基于網(wǎng)絡(luò)編碼的廣播傳輸機(jī)制(NBT)，與目前廣播時(shí)延最小的泛洪機(jī)制相比，NBT能有效降低廣播傳輸時(shí)延。張健等[16]研究了隨機(jī)網(wǎng)絡(luò)編碼下的數(shù)據(jù)塊時(shí)延特性，采用梯度法進(jìn)行網(wǎng)絡(luò)時(shí)延預(yù)測(cè)。文獻(xiàn)[17]提出了一種編碼增益的計(jì)算方法和編碼圖的簡(jiǎn)化方法，并基于此提出了編碼增益感知的路由協(xié)議CGAR。仿真實(shí)驗(yàn)表明，CGAR的時(shí)延優(yōu)于COPE和DCAR協(xié)議。文獻(xiàn)[18]提出了基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)中端到端的延遲分析的一種分析方法，目的是分析網(wǎng)絡(luò)中的每個(gè)數(shù)據(jù)流的延遲，以網(wǎng)絡(luò)演算為理論基礎(chǔ)。文獻(xiàn)[19] 使用機(jī)會(huì)網(wǎng)絡(luò)編碼(ONC)研究了雙向中繼網(wǎng)絡(luò)的基本流量延遲。通過(guò)最優(yōu)ONC策略在平均分組延遲約束的網(wǎng)絡(luò)中最大化網(wǎng)絡(luò)吞吐量。

以上都是單獨(dú)針對(duì)網(wǎng)絡(luò)編碼代價(jià)或時(shí)延的研究。經(jīng)查閱相關(guān)文獻(xiàn)，目前，同時(shí)針對(duì)無(wú)線mesh網(wǎng)中網(wǎng)絡(luò)編碼代價(jià)和時(shí)延的研究還沒(méi)有，本文是首次提出了一個(gè)無(wú)線mesh網(wǎng)中最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由協(xié)議MNCLDMR。MNCLDMR的目標(biāo)是選擇合適的網(wǎng)絡(luò)編碼節(jié)點(diǎn)，最小化網(wǎng)絡(luò)編碼代價(jià)，降低網(wǎng)絡(luò)時(shí)延。

本文創(chuàng)新點(diǎn)如下：1)MNCLDMR協(xié)議引入了拓?fù)潢P(guān)鍵節(jié)點(diǎn)和網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)的概念，以下一跳的節(jié)點(diǎn)是否是網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)或拓?fù)潢P(guān)鍵節(jié)點(diǎn)作為路由判據(jù)；2)采用算法MNCLD構(gòu)造多播樹(shù)。舉例和仿真結(jié)果表明MNCLDMR可以達(dá)到預(yù)定目標(biāo)，合理形成網(wǎng)絡(luò)編碼機(jī)會(huì)，能實(shí)現(xiàn)最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由。

2 相關(guān)知識(shí)

2.1 網(wǎng)絡(luò)編碼代價(jià)衡量標(biāo)準(zhǔn)

1) 網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)

由于節(jié)點(diǎn)執(zhí)行網(wǎng)絡(luò)編碼需要額外的編碼功能，那么最小化網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)是有潛在的利益。在采用相同網(wǎng)絡(luò)編碼方法和相同路由方式的前提下，編碼節(jié)點(diǎn)越多，網(wǎng)絡(luò)編碼的復(fù)雜度就越大。不是所有的中間節(jié)點(diǎn)都需要進(jìn)行網(wǎng)絡(luò)編碼，而只需選取其中有必要編碼的節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼。

2) 網(wǎng)絡(luò)編碼操作次數(shù)

與傳統(tǒng)的路由不同，網(wǎng)絡(luò)編碼需要在節(jié)點(diǎn)進(jìn)行編碼或解碼操作，增加了運(yùn)算成本，提高了信息的傳輸延遲，這不僅影響了信息的傳輸速度，并且使宿點(diǎn)接收信息延遲。控制網(wǎng)絡(luò)編碼的操作次數(shù)對(duì)控制網(wǎng)絡(luò)編碼代價(jià)具有重要的意義。

3) 網(wǎng)絡(luò)編碼中的數(shù)據(jù)分組個(gè)數(shù)

單次網(wǎng)絡(luò)編碼中數(shù)據(jù)分組的個(gè)數(shù)也是影響網(wǎng)絡(luò)編碼代價(jià)的一個(gè)重要因素。要進(jìn)行網(wǎng)絡(luò)編碼，相應(yīng)的編碼節(jié)點(diǎn)需要較大的緩存空間，單次網(wǎng)絡(luò)編碼中數(shù)據(jù)分組個(gè)數(shù)越多，目標(biāo)節(jié)點(diǎn)解碼的成功率相對(duì)就越低，相應(yīng)的網(wǎng)絡(luò)編碼代價(jià)會(huì)增加。

4) 消耗的資源

編碼節(jié)點(diǎn)需要進(jìn)行編碼運(yùn)算，目的節(jié)點(diǎn)需要進(jìn)行相應(yīng)的解碼操作，這些都需要消耗一定的CPU資源和內(nèi)存資源。這與編碼算法關(guān)系很大，編碼算法越復(fù)雜，所消耗的資源就越多，相應(yīng)的編碼算法越簡(jiǎn)單，所消耗的資源就越少。

本文主要考慮網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)編碼次數(shù)，編碼算法采用簡(jiǎn)單的異或算法（XOR），因此消耗的計(jì)算資源是比較小的。

2.2 時(shí)延

在傳統(tǒng)的網(wǎng)絡(luò)中，網(wǎng)絡(luò)時(shí)延主要是傳輸時(shí)延，引入網(wǎng)絡(luò)編碼后，將增加編碼、解碼時(shí)延。網(wǎng)絡(luò)中源節(jié)點(diǎn)的數(shù)據(jù)分組到達(dá)目的節(jié)點(diǎn)的傳輸時(shí)間就是傳輸時(shí)延。傳輸時(shí)延的大小取決于傳輸速率和傳輸距離。編碼、解碼時(shí)延與編碼算法相關(guān)，選擇一個(gè)簡(jiǎn)單的編碼算法(如XOR)，編碼、解碼時(shí)延就會(huì)很低。相對(duì)于傳輸時(shí)延，編碼、解碼時(shí)延是很少的。因此，本文主要考慮傳輸時(shí)延。

假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都具有相同的性能，那么時(shí)延跟跳數(shù)成正比。假設(shè)網(wǎng)絡(luò)中有對(duì)源節(jié)點(diǎn)和目的節(jié)點(diǎn)進(jìn)行通信，那么整個(gè)網(wǎng)絡(luò)的平均時(shí)延[end?end]為這個(gè)端到端時(shí)延的平均值，即

其中，[end?end]與網(wǎng)絡(luò)中的總跳數(shù)成正比。

3 最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由

3.1 網(wǎng)絡(luò)模型

本文主要考慮在無(wú)線mesh網(wǎng)的mesh骨干層中如何實(shí)現(xiàn)最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由，mesh骨干層的拓?fù)浣Y(jié)構(gòu)是比較穩(wěn)定的。無(wú)線mesh網(wǎng)可以建模為無(wú)向圖(,)，其中，表示節(jié)點(diǎn)的集合，表示無(wú)線鏈路的集合。每個(gè)節(jié)點(diǎn)v∈均存在一個(gè)通信距離T和一個(gè)干擾距離I。通常是3TIT，本文假設(shè)I=2T。γ=(S, D, b)為無(wú)線業(yè)務(wù)集合，其中，S表示無(wú)線多播γ的源點(diǎn)，D表示γ的目的節(jié)點(diǎn)集合，b表示γ需要的帶寬約束。()表示為無(wú)線業(yè)務(wù)γ構(gòu)造的多播樹(shù)。()中的節(jié)點(diǎn)有3類：源點(diǎn)、中間節(jié)點(diǎn)以及目的節(jié)點(diǎn)。(())表示中間節(jié)點(diǎn)集合。

3.2 拓?fù)潢P(guān)鍵節(jié)點(diǎn)與網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)

用λ表示節(jié)點(diǎn)的入度，初始設(shè)定λ=0。I表示從鏈路輸入的信息，I(1,2,…,λ)表示所獲得的不同輸入信息(相同的舍棄)。

定義1 拓?fù)潢P(guān)鍵節(jié)點(diǎn)。輸入鏈路數(shù)λ≥2的中間節(jié)點(diǎn)。

定義2 網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)。輸入鏈路數(shù)λ≥2，且I(1,2,…,λ)中的≥2的中間節(jié)點(diǎn)。

相對(duì)于路由選擇來(lái)說(shuō)，拓?fù)潢P(guān)鍵節(jié)點(diǎn)是靜態(tài)的而網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)是動(dòng)態(tài)的，一個(gè)節(jié)點(diǎn)是否為網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)不僅要考慮節(jié)點(diǎn)的入度數(shù)量，還需要考慮經(jīng)過(guò)節(jié)點(diǎn)的數(shù)據(jù)流條數(shù)以及節(jié)點(diǎn)緩存隊(duì)列中信息數(shù)量。

在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼的條件：I(1,2,…,λ)中的≥2，且編碼形成的數(shù)據(jù)分組的目的節(jié)點(diǎn)數(shù)不少于編碼到一起的原數(shù)據(jù)分組個(gè)數(shù)。

3.3 最小編碼代價(jià)低時(shí)延多播路由

MNCLDMR的基本思想如下：首先，初始化網(wǎng)絡(luò)(,)，初始化多播樹(shù)()只包含源點(diǎn)S；然后運(yùn)用Dijkstra算法計(jì)算多播源節(jié)點(diǎn)S到目的節(jié)點(diǎn)集合D中所有目的節(jié)點(diǎn)的最短路徑，(S,d)表示多播源節(jié)點(diǎn)S到目的節(jié)點(diǎn)d的最短路徑；最后引入拓?fù)潢P(guān)鍵節(jié)點(diǎn)和網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)，下一跳的路由節(jié)點(diǎn)優(yōu)先選擇網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)，其次選拓?fù)潢P(guān)鍵節(jié)點(diǎn)，最后才選普通節(jié)點(diǎn)，采用MNCLD算法構(gòu)造多播樹(shù)。形成多播樹(shù)的具體算法如下。

算法1 MNCLD算法

輸入(,),γ=(S, D, b)

輸出()

1)()←{S},←D;

2) while≠0 do {

3) whiled∈Ddo {

4)(S, d)←Dijkstra(S, d);//Dijkstra算法求最短路徑并確定中間節(jié)點(diǎn)的入度

5) }

6) ifλ≥2&&I(1,2,…,λ)中的≥2{//節(jié)點(diǎn)為S任意一個(gè)鄰居節(jié)點(diǎn)，下同

7)()←;//節(jié)點(diǎn)為網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)，根據(jù)編碼條件進(jìn)行網(wǎng)絡(luò)編碼

8) }else //S的所有鄰居節(jié)點(diǎn)中沒(méi)有網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)

9) ifλ≥2{

10)()←; //節(jié)點(diǎn)為拓?fù)潢P(guān)鍵節(jié)點(diǎn)

11) }else//S的所有鄰居節(jié)點(diǎn)中沒(méi)有拓?fù)潢P(guān)鍵節(jié)點(diǎn)

12)()←; //節(jié)點(diǎn)為普通節(jié)點(diǎn)

13)(())←(()));

14)D←D?d,←?1,S←;

15) }

16) return [()]

MNCLD算法說(shuō)明：運(yùn)用Dijkstra算法計(jì)算多播源節(jié)點(diǎn)S到目的節(jié)點(diǎn)集合D中所有目的節(jié)點(diǎn)的最短路徑并確定中間節(jié)點(diǎn)的入度，引入拓?fù)潢P(guān)鍵節(jié)點(diǎn)和網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)，并且在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)根據(jù)編碼條件進(jìn)行網(wǎng)絡(luò)編碼，在計(jì)算下一個(gè)新的多播樹(shù)節(jié)點(diǎn)時(shí)，將已算出的()作為中間節(jié)點(diǎn)集合來(lái)實(shí)施Dijkstra算法。由于只在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼，這樣在整個(gè)網(wǎng)絡(luò)通信中網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)編碼次數(shù)都將非常有限，從而能實(shí)現(xiàn)最小網(wǎng)絡(luò)編碼代價(jià)。也由于在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)引入網(wǎng)絡(luò)編碼，在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)發(fā)送信息時(shí)可以將多個(gè)數(shù)據(jù)分組編碼成一個(gè)數(shù)據(jù)分組發(fā)送，這樣可以減少發(fā)送次數(shù)，提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)時(shí)延。

3.4 復(fù)雜度分析

MNCLDMR算法是以Dijkstra算法為基礎(chǔ)的，因而MNCLDMR算法的復(fù)雜度與Dijkstra算法的復(fù)雜度是一致的。設(shè)網(wǎng)絡(luò)的邊數(shù)為，頂點(diǎn)數(shù)為，那么該算法的復(fù)雜度為(2)。如果邊數(shù)遠(yuǎn)小于2，可以考慮用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，該算法的復(fù)雜度降為(() log)。

3.5 實(shí)例說(shuō)明

下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明MNCLDMR的優(yōu)越性。如圖1所示12個(gè)節(jié)點(diǎn)的無(wú)線mesh網(wǎng)中，節(jié)點(diǎn)之間的實(shí)線表示可以直接無(wú)線通信，沒(méi)有實(shí)線直接相連的節(jié)點(diǎn)則必須通過(guò)其他節(jié)點(diǎn)間接無(wú)線通信。源節(jié)點(diǎn)為1234，分別發(fā)送數(shù)據(jù)分組1234，目的節(jié)點(diǎn)為，最終要使所有目的節(jié)點(diǎn)都接收到數(shù)據(jù)分組1234。假設(shè)每條鏈路的傳輸時(shí)間為單位時(shí)間，節(jié)點(diǎn)處理數(shù)據(jù)分組的時(shí)間忽略不計(jì)。假設(shè)每個(gè)節(jié)點(diǎn)的發(fā)送和接收可以同時(shí)進(jìn)行，每條鏈路可以同時(shí)雙向通信(比如采用頻分雙工FDD模式)。

圖2為單位時(shí)間之后，無(wú)線mesh網(wǎng)中各節(jié)點(diǎn)擁有的數(shù)據(jù)分組。根據(jù)定義2，和是網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)，根據(jù)在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)進(jìn)行編碼的條件，只需在節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼。

節(jié)點(diǎn)將數(shù)據(jù)分組134進(jìn)行編碼4，然后多播到節(jié)點(diǎn)。節(jié)點(diǎn)根據(jù)已有的數(shù)據(jù)分組可分別解碼出134。在此同時(shí)，節(jié)點(diǎn)將4發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將2發(fā)送到節(jié)點(diǎn)和，節(jié)點(diǎn)3將2發(fā)送到節(jié)點(diǎn)。那么經(jīng)過(guò)2時(shí)間之后，無(wú)線mesh網(wǎng)中各節(jié)點(diǎn)的數(shù)據(jù)分組如圖3所示。

根據(jù)編碼條件，這時(shí)不需進(jìn)行任何編碼，節(jié)點(diǎn)將2發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將3發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將3發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將2發(fā)送到節(jié)點(diǎn)和，節(jié)點(diǎn)將4發(fā)送到節(jié)點(diǎn)和。經(jīng)過(guò)3時(shí)間之后，無(wú)線mesh網(wǎng)中各節(jié)點(diǎn)的數(shù)據(jù)分組如圖4所示。

根據(jù)編碼條件，這時(shí)也不需進(jìn)行任何編碼，節(jié)點(diǎn)將3發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將2發(fā)送到節(jié)點(diǎn)，節(jié)點(diǎn)將3發(fā)送到節(jié)點(diǎn)。經(jīng)過(guò)4時(shí)間之后，無(wú)線mesh網(wǎng)中各節(jié)點(diǎn)的數(shù)據(jù)分組如圖5所示。這時(shí)所有目的節(jié)點(diǎn)都接收到數(shù)據(jù)分組1234，完成傳輸。

在網(wǎng)絡(luò)數(shù)據(jù)分組傳輸全過(guò)程中網(wǎng)絡(luò)編碼僅有一次，而且網(wǎng)絡(luò)時(shí)延僅有4。如果在所有拓?fù)潢P(guān)鍵節(jié)點(diǎn)都進(jìn)行網(wǎng)絡(luò)編碼或不進(jìn)行網(wǎng)絡(luò)編碼，顯然達(dá)不到這種效果。

用d()表示目的節(jié)點(diǎn)D(1≤≤)成功收到第個(gè)數(shù)據(jù)分組P(1≤≤)的時(shí)延。其中，為網(wǎng)絡(luò)中目的節(jié)點(diǎn)總個(gè)數(shù)，此例中為8；為所有源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組個(gè)數(shù)，此例中為4。假設(shè)MNCLDMR的目的節(jié)點(diǎn)D(1≤≤)在最后都能收到所有數(shù)據(jù)分組，則目的節(jié)點(diǎn)D(1≤≤)收到所有數(shù)據(jù)分組的平均傳輸時(shí)延[d()]可以表示為

在上面所舉例子中，采用MNCLDMR路由算法計(jì)算如下

(3)

(5)

(6)

(8)

(9)

成功傳輸數(shù)據(jù)分組P(1≤≤)的平均時(shí)延為。在上面所舉例子中，采用MNCLDMR路由算法計(jì)算如下

(11)

(13)

(14)

4 仿真分析

使用NS2(network simulator version 2)產(chǎn)生具有實(shí)際網(wǎng)絡(luò)特性的無(wú)線mesh網(wǎng)拓?fù)鋄20]。個(gè)節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m矩形區(qū)域內(nèi)。在微機(jī)上使用NS2仿真工具分4組進(jìn)行，分別仿真AODV、COPE[21]、CGAR[17]和MNCLDMR。AODV協(xié)議是典型的按需路由協(xié)議，AODV支持多播功能，支持QoS，只支持雙向鏈路。AODV協(xié)議在NS2中有完整源代碼，可以直接調(diào)用。COPE協(xié)議是基于網(wǎng)絡(luò)編碼的適合無(wú)線mesh網(wǎng)絡(luò)的路由，但沒(méi)有考慮時(shí)延。COPE協(xié)議在NS2中也已具體實(shí)現(xiàn)。

仿真參數(shù)如下：數(shù)據(jù)分組大小為512 byte，節(jié)點(diǎn)傳輸范圍為200 m，節(jié)點(diǎn)干擾半徑為400 m，節(jié)點(diǎn)帶寬為10 Mbit/s，工作模式為混雜模式，節(jié)點(diǎn)隊(duì)列長(zhǎng)度為80個(gè)數(shù)據(jù)分組。分別對(duì)節(jié)點(diǎn)數(shù)為20、30、40、50、60的網(wǎng)絡(luò)進(jìn)行了路由時(shí)延、吞吐量、編碼節(jié)點(diǎn)數(shù)、編碼次數(shù)和解碼出錯(cuò)次數(shù)的統(tǒng)計(jì)。

仿真場(chǎng)景：當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為20、30、40、50、60時(shí)，分別設(shè)置2、3、4、5、6個(gè)多播通信，每個(gè)多播通信有1個(gè)源節(jié)點(diǎn)和6個(gè)目的節(jié)點(diǎn)，每個(gè)源節(jié)點(diǎn)的數(shù)據(jù)發(fā)送速率為50 kbit/s。每個(gè)場(chǎng)景仿真20次后取平均值。

圖6所示為網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)規(guī)模之間的關(guān)系。如圖6所示，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)網(wǎng)絡(luò)編碼節(jié)點(diǎn)數(shù)隨著增加，但是COPE和CGAR的曲線比較陡峭，而MNCLDMR的曲線增加比較平緩。原因是當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，可用的鏈路增加，網(wǎng)絡(luò)編碼的機(jī)會(huì)就更多，而MNCLDMR只在網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼，因而比COPE和CGAR增加緩慢些。

圖7所示為路由時(shí)延與網(wǎng)絡(luò)規(guī)模之間的關(guān)系。如圖7所示，時(shí)延隨著網(wǎng)絡(luò)規(guī)模增大而增加，但是AODV時(shí)延曲線比較陡峭，而COPE、CGAR和MNCLDMR的曲線比較平緩。原因是當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，網(wǎng)絡(luò)中間鏈路數(shù)增加，因而路由時(shí)延會(huì)隨之增加，但COPE、CGAR和MNCLDMR都考慮了網(wǎng)絡(luò)編碼，隨網(wǎng)絡(luò)規(guī)模增大而增多的數(shù)據(jù)分組經(jīng)過(guò)網(wǎng)絡(luò)編碼后能夠得到有效地控制，網(wǎng)絡(luò)中路由的總鏈路數(shù)也會(huì)得到有效地控制，因而路由時(shí)延增長(zhǎng)緩慢。

圖8表示吞吐量與網(wǎng)絡(luò)規(guī)模之間的關(guān)系。如圖8所示，吞吐量隨著網(wǎng)絡(luò)規(guī)模增大而增加，但是AODV的吞吐量增加緩慢，而COPE、CGAR和MNCLDMR的吞吐量增加更快，COPE、CGAR和MNCLDMR都可以明顯的提升吞吐量。因?yàn)榫W(wǎng)絡(luò)編碼可以組合多個(gè)數(shù)據(jù)分組成一個(gè)再發(fā)送，這樣相當(dāng)于一次發(fā)送了多個(gè)數(shù)據(jù)分組，所以能明顯的提升吞吐量。

圖9和圖10顯示了不同網(wǎng)絡(luò)規(guī)模下節(jié)點(diǎn)編碼數(shù)量和解碼出錯(cuò)數(shù)量的變化。從圖9和圖10中可以看出MNCLDMR、COPE和CGAR這3種編碼傳輸方式的編碼次數(shù)和解碼出錯(cuò)次數(shù)均維持在一個(gè)比較大的范圍內(nèi)，且MNCLDMR的編碼次數(shù)和解碼出錯(cuò)次數(shù)均略小于COPE和CGAR。從總體來(lái)看，MNCLDMR解碼出錯(cuò)被丟棄的數(shù)據(jù)分組的數(shù)量平均占編碼數(shù)據(jù)分組數(shù)量的4.5％左右，COPE解碼出錯(cuò)被丟棄的數(shù)據(jù)分組的數(shù)量平均占編碼數(shù)據(jù)分組數(shù)量的5％左右，CGAR解碼出錯(cuò)被丟棄的數(shù)據(jù)分組的數(shù)量平均占編碼數(shù)據(jù)分組數(shù)量的5.5％左右。

5 結(jié)束語(yǔ)

本文提出了一種無(wú)線mesh網(wǎng)中最小網(wǎng)絡(luò)編碼代價(jià)低時(shí)延多播路由協(xié)議MNCLDMR。MNCLDMR協(xié)議引入了拓?fù)潢P(guān)鍵節(jié)點(diǎn)和網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)的概念，以下一跳的節(jié)點(diǎn)是否是網(wǎng)絡(luò)編碼關(guān)鍵節(jié)點(diǎn)或拓?fù)潢P(guān)鍵節(jié)點(diǎn)作為路由判據(jù)，采用算法MNCLD構(gòu)造多播樹(shù)。舉例和仿真實(shí)驗(yàn)表明，該協(xié)議能選擇合適的網(wǎng)絡(luò)編碼節(jié)點(diǎn)，減少網(wǎng)絡(luò)編碼代價(jià)，降低網(wǎng)絡(luò)時(shí)延。在后續(xù)的研究工作中，需對(duì)該多播路由協(xié)議的具體實(shí)現(xiàn)做更深入的研究。

[1] AHLSWEDE R, CAI N, LI S R. Network information flow[J]. IEEE Transactions Information Theory, 2000, 46(4): 1204-1216.

[2] ANWAR A H, CHADI B, THIERRY T. Network coding for wireless mesh networks: a case study[C]//IEEE Communication Society. San Francisco, CA, USA, c2006: 173-182.

[3] 陳晨, 董超, 茅婭菲. 無(wú)線網(wǎng)絡(luò)編碼感知路由綜述[J]. 軟件學(xué)報(bào), 2015, 26(1): 82-97.

CHEN C, DONG C, MAO Y F. Survey on network-coding-aware routing in wireless network[J]. Journal of Software, 2015, 26(1): 82-97.

[4] 王偉平,陳小專,魯鳴鳴. 應(yīng)用累積系數(shù)確認(rèn)的網(wǎng)絡(luò)編碼機(jī)會(huì)路由協(xié)議[J]. 軟件學(xué)報(bào), 2014, 25(7):1541-1556.

WANG W P, CHEN X Z, LU M M. Network coding based opportun-istic routing using cumulative coding coefficient feedback acknowl-edgments[J]. Journal of Software, 2014, 25(7):1541-1556.

[5] 沈小建,陳志剛,劉立. 無(wú)線mesh網(wǎng)絡(luò)中編碼感知且負(fù)載均衡的多播路由[J]. 通信學(xué)報(bào), 2015, 36(4):2015134.

SHEN X J, CHEN Z G, LIU L. Load balancing multicast routing based on network coding in wireless mesh network[J]. Journal on Communications, 2015, 36(4):2015134.

[6] CHEN J, HE K, DU R. Dominating set and network coding-based routing in wireless mesh networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(2):423-433.

[7] LIU H L, SHEN Q R, CHEN Y. An optical multicast routing with minimal network coding operations in WDM networks[J/OL]. Interna-tional Journal of Optics, http://dx.doi.org/10.1155/2014/693807.

[8] RAMI S Y, CHENG W Q. Cost minimization for multi-source mul-ti-sink network coding[C]//The 9th International Conference for Young Computer Scientists. Hunan, China, c2008: 253-258.

[9] DESMOND S L, NIRANJAN R, MURIEL M. Minimum-cost mul-ticast over coded packet networks[J]. IEEE Transactions on Informa-tion Theory, 2006, 52(6): 2608-2623.

[10] 陶少國(guó), 黃佳慶, 楊宗凱. 一種改進(jìn)的最小代價(jià)網(wǎng)絡(luò)編碼算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 36(5): 1-4.

TAO S G, HUANG J Q, YANG Z K. An improved algorithm for minimal cost network coding[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2008, 36(5): 1-4.

[11] 吳強(qiáng), 范建華, 闞寶強(qiáng). 低開(kāi)銷的無(wú)線網(wǎng)絡(luò)編碼機(jī)會(huì)路由協(xié)議設(shè)計(jì)[J]. 計(jì)算機(jī)工程, 2014, 40(2): 21-25.

WU Q, FAN J H, KAN B Q. Design of low overhead opportunistic routing protocol for wireless network coding[J]. Computer Engineering, 2014, 40(2): 21-25.

[12] 盧冀,肖嵩,吳成柯. 基于機(jī)會(huì)式網(wǎng)絡(luò)編碼的低時(shí)延廣播傳輸算法[J]. 電子學(xué)報(bào), 2011, 39(5): 1214-1219.

LU J, XIAO S, WU C K. Opportunistic network coding based de-lay-sensitive broadcast transmission algorithm[J]. Acta Electronica Sinica, 2011, 39(5): 1214-1219.

[13] SAMEH S, SHAHROKH V. On minimizing broadcast completion delay for instantly decodable network coding[C]//IEEE ICC. South Africa, c2010: 1871-1875.

[14] 姚玉坤, 易建瓊, 溫亞迪. 無(wú)線單跳網(wǎng)絡(luò)中的高效低時(shí)延網(wǎng)絡(luò)編碼算法[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 24(5): 577-584.

YAO Y K, YI J Q, WEN Y D. Efficient low-delay algorithm for network coding in wireless single-hop networks[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012, 24(5): 577-584.

[15] 楊奎武, 郭淵博, 馬駿. 基于網(wǎng)絡(luò)編碼的延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)低時(shí)延廣播傳輸機(jī)制[J]. 電子與信息學(xué)報(bào), 2012, 34(5): 1239-1245.

YANG K W, GUO Y B, MA J. A netcoding-based delay-sensitive broadcast transmission scheme for delay tolerant mobile sensor net-works[J]. Journal of Electronics & Information Technology, 2012, 34(5): 1239-1245.

[16] 張健, 余純武, 梅峰. 網(wǎng)絡(luò)編碼塊時(shí)延預(yù)測(cè)與控制[J]. 武漢大學(xué)學(xué)報(bào)(理學(xué)版), 2012, 58(4): 366-369.

ZHANG J, YU C W, MEI F. The prediction and control of block delay under network coding[J]. Journal Wuhan University(Natural Science Edition), 2012, 58(4): 366-369.

[17] 田賢忠, 朱藝華, 繆得志. 無(wú)線網(wǎng)絡(luò)編碼增益感知的低時(shí)延路由協(xié)議[J]. 電子學(xué)報(bào), 2013, 41(4): 652-658.

TIAN X Z, ZHU Y H, MIAO D Z. Wireless network coding gain aware routing protocol with low delay[J]. Acta Electronica Sinica, 2013, 41(4): 652-658.

[18] LI H Z, LIU X, HE W B. Delay analysis in practical wireless net-work coding[J]. Wireless Communications and Mobile Computing, 2014, 14:497-515.

[19] ZOHDY M, ELBATT T, NAFIE M. Maximum throughput opportun-istic network coding in two-way relay networks[J]. arXiv cs.IT, 2015, 12(3): 67-73.

[20] 于斌,孫斌,溫暖. NS2與網(wǎng)絡(luò)模擬[M]. 北京:人民郵電出版社, 2007.

YU B, SUN B, WEN N. NS2 and Network Simulation[M]. Beijing: Posts & Telecom Press, 2007.

[21] KATTI S, RAHUL H S, HU W. XORs in the air: practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

Minimal coding cost and low delay multicast routing of wireless mesh networks

CHEN Zhi-gang1, SHEN Xiao-jian1,2, LIU Li2

(1. College of Information Science and Engineering, Central South University, Changsha 410083, China; 2. College of Computer and Communication, Hunan University of Technology, Zhuzhou 412007, China)

A minimal network coding cost and low delay multicast routing (MNCLDMR) of wireless mesh networks was presented. The goal of MNCLDMR was to select the appropriate network coding nodes, minimize network coding and reduce network delay. MNCLDMR protocol introduces the concept of topology key nodes and network coding key nodes, serving as the routing metric whether the next hop nodes were network coding key nodes or topology key nodes, using MNCLD algorithm construct multicast tree. Simulation results show that MNCLDMR can achieve expectation goal, form reasonable network coding opportunity and achieve minimal network coding and low delay multicast routing.

wireless mesh networks, minimum cost, network coding, low delay, multicast routing

TP393

A

10.11959/j.issn.1000-436x.2016002

2015-07-02；

2015-11-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.60902044, No.60873082, No.60903058)；湖南省教育廳科研基金資助項(xiàng)目(No.12C0070)

The National Natural Science Foundation of China (No.60902044, No.60873082, No.60903058), The Hunan Provincial Education Department Research Projects (No.12C0070)

陳志剛（1964-），男，湖南益陽(yáng)人，博士，中南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)計(jì)算與分布式處理、計(jì)算機(jī)網(wǎng)絡(luò)。

沈小建（1976-），男，湖南永州人，中南大學(xué)博士生，主要研究方向?yàn)闊o(wú)線mesh網(wǎng)絡(luò)與網(wǎng)絡(luò)編碼。

劉立（1970-），男，湖北廣水人，湖南工業(yè)大學(xué)副教授，主要研究方向?yàn)榉?wù)計(jì)算、可信計(jì)算、網(wǎng)絡(luò)安全。