基于隨機(jī)線性網(wǎng)絡(luò)編碼的改善無線網(wǎng)絡(luò)廣播能量效率的方法

摘 要：提出了一種應(yīng)用網(wǎng)絡(luò)編碼技術(shù)改善無線網(wǎng)絡(luò)廣播能量效率的分布式完全編碼廣播策略（DAEBNC），其核心思想是發(fā)送節(jié)點(diǎn)通過獲得鄰居節(jié)點(diǎn)記錄數(shù)據(jù)的情況，應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼選擇多個(gè)源數(shù)據(jù)包生成編碼組合包，依次發(fā)送；接收節(jié)點(diǎn)使用線性運(yùn)算解碼編碼包獲得源數(shù)據(jù)包。理論分析表明，該方法編碼包在所有接收節(jié)點(diǎn)具有可解性，有效地減少了數(shù)據(jù)廣播次數(shù)。仿真結(jié)果證實(shí)，與普通泛洪方法相比，DAEBNC可以有效地提高能量利用效率，改善無線網(wǎng)絡(luò)性能。

關(guān)鍵詞：隨機(jī)線性網(wǎng)絡(luò)編碼； 無線網(wǎng)絡(luò)廣播； 能量效率

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)06-2244-04

doi:10.3969/j.issn.1001-3695.2009.06.074

Random linear network coding approach to improve energyefficiency in wireless networks broadcasting

ZHANG Shuai， YANG Lu-ming， XIAO Xiao， PU Bao-xing

(Dept. of Computer， Institute of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:

This paper presented a distributed always encoded broadcasting based on network coding (DAEBNC) algorithm to improve energy efficiency in wireless networks. Its main idea was that based on which packets its neighbors had， the sent node chose source packets to generate several linearly independent combinations based on random linear network coding and broadcasts in turn. Then received nodes solved a system of linear equations to decode combined packets and retrieved source packets. Theoretic analysis revealed that encoded packets based on the approach could be decoded in all received nodes， which effectively reduced the number of transmissions. Simulation results indicate that comparing with existing flooding algorithm， this approach can effectively improve energy efficiency and consequently improve the performance of wireless networks.

Key words：random linear network coding; wireless networks broadcasting; energy efficiency

廣播通信是無線網(wǎng)絡(luò)的一種常用通信方式，在尋找到達(dá)某一指定節(jié)點(diǎn)的路徑、向全網(wǎng)發(fā)送報(bào)警信號(hào)、分布式計(jì)算等方面得到廣泛的應(yīng)用。由于無線網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)特性，使得節(jié)點(diǎn)很難獲得整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔ⅲ蚨鴱V播操作通常采用泛洪（flooding algorithm）方法。然而，泛洪方法會(huì)導(dǎo)致巨大的能量開銷，直接影響到無線節(jié)點(diǎn)電池的壽命，因此如何利用現(xiàn)有的網(wǎng)絡(luò)資源、減少廣播開銷、提高能量利用效率成為研究的熱點(diǎn)之一。

2002年，Zagalj等人^[1]證明，最小化能量廣播問題是NP完全問題。在該問題的研究中，很多發(fā)送算法或方法上改進(jìn)的思想被提出。通常，這些算法或方法或以一定的概率轉(zhuǎn)發(fā)信息^[2，3]，或基于某種形式的拓?fù)淇刂苼韺?shí)現(xiàn)^[4~6]。2000年，Ahlswede等人^[7]基于網(wǎng)絡(luò)信息流的概念提出了網(wǎng)絡(luò)編碼的思想，允許節(jié)點(diǎn)對信息進(jìn)行編碼，從而提高網(wǎng)絡(luò)傳輸性能。之后，網(wǎng)絡(luò)編碼被應(yīng)用于各個(gè)方面的研究，用于提高網(wǎng)絡(luò)吞吐量、安全性等。

無線鏈路的不可靠性和物理層的廣播特性使得網(wǎng)絡(luò)編碼在能量利用效率方面有著很好的應(yīng)用，也為最小化能量廣播問題提供了一種新的途徑。Wu等人^[8，9]證明在無線Ad hoc網(wǎng)絡(luò)組播時(shí)應(yīng)用網(wǎng)絡(luò)編碼，可以將最小化每位數(shù)據(jù)能量消耗問題歸結(jié)為線性問題，同時(shí)提出了動(dòng)態(tài)拓?fù)浣M播的最小化能量解決方法。Lun等人^[10，11]提出了選擇最小能量多播樹的分布式算法，并提出了固定拓?fù)涞臒o線組播網(wǎng)絡(luò)編碼最小化能量解決方法。Katti等人^[12]構(gòu)造了無線Mesh網(wǎng)使用網(wǎng)絡(luò)編碼體系COPE，并利用29個(gè)802.11b節(jié)點(diǎn)的實(shí)驗(yàn)平臺(tái)證實(shí)能顯著減少平均傳輸次數(shù)。

1 隨機(jī)線性網(wǎng)絡(luò)編碼的基本原理

隨機(jī)線性網(wǎng)絡(luò)編碼方法的核心思想是利用節(jié)點(diǎn)的運(yùn)算能力，在發(fā)送節(jié)點(diǎn)線性編碼組合不同的信息包，在接收節(jié)點(diǎn)獲得足夠的線性編碼組合后，通過運(yùn)算得到原始信息包，其可用性推廣了網(wǎng)絡(luò)編碼理論的應(yīng)用范圍^[13]。

圖1給出了傳統(tǒng)傳輸和隨機(jī)線性網(wǎng)絡(luò)編碼傳輸?shù)谋容^。如圖1所示，無線節(jié)點(diǎn)R1需要發(fā)送信息包X、Y、Z。圖1(a)表示了傳統(tǒng)傳輸?shù)那闆r，發(fā)送節(jié)點(diǎn)逐一廣播發(fā)送信息包X、Y、Z；圖1(b)表示了隨機(jī)線性網(wǎng)絡(luò)編碼傳輸?shù)那闆r。當(dāng)節(jié)點(diǎn)具有編碼能力，可以選取隨機(jī)參數(shù)編碼組合1X+2Y+3Z、β1X+β２Y+β3Z、γ1X+γ2X+γ3Z（其中的參數(shù)隨機(jī)獲得，參數(shù)值寫入編碼組合包中發(fā)送），廣播逐一發(fā)送編碼組合包，接收節(jié)點(diǎn)接收到三個(gè)編碼組合包以后，通過線性運(yùn)算可以解出原始信息包X、Y、Z，完成數(shù)據(jù)傳輸。

采用隨機(jī)線性網(wǎng)絡(luò)編碼方法，接收節(jié)點(diǎn)處理的問題從是否收到完整信息包，轉(zhuǎn)換為是否收到足夠多的滿足可解性條件的編碼包。通過研究發(fā)現(xiàn)，隨機(jī)線性編碼組合發(fā)送可以帶來良好的吞吐量、魯棒性、安全性等方面的增益，為網(wǎng)絡(luò)性能的改善提供了一種新的途徑。

2 DAEBNC方法

2.1 無線網(wǎng)絡(luò)廣播模型

考慮一個(gè)具有n個(gè)相同節(jié)點(diǎn)的無線網(wǎng)絡(luò)，傳輸信道存在一定損耗，所有節(jié)點(diǎn)均具有相同的傳輸半徑，發(fā)送的數(shù)據(jù)包可以被傳輸半徑內(nèi)所有的無線節(jié)點(diǎn)接收。存在如下的假設(shè)：

假設(shè)1 網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均可以是發(fā)送節(jié)點(diǎn)，并可以接收來自網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的數(shù)據(jù)，傳輸數(shù)據(jù)的大小均相同，且通過數(shù)據(jù)包來傳輸。

假設(shè)2 節(jié)點(diǎn)每發(fā)送一個(gè)數(shù)據(jù)包占用一個(gè)單位時(shí)間，且在一個(gè)單位時(shí)間內(nèi)，每個(gè)節(jié)點(diǎn)只能發(fā)送或接收一個(gè)數(shù)據(jù)包。

假設(shè)3 節(jié)點(diǎn)存在一個(gè)鄰居信息表來記錄其鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包的情況。表的行表示鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包的情況，列表示源數(shù)據(jù)包接收情況。若某個(gè)鄰居節(jié)點(diǎn)獲得了某個(gè)源數(shù)據(jù)包，其對應(yīng)位置賦值為1，否則賦值為0。

直觀地看，發(fā)送數(shù)據(jù)包所消耗的能量與數(shù)據(jù)包的發(fā)送次數(shù)在一定程度上是成比例的。提高能量利用效率的目標(biāo)可以通過減少數(shù)據(jù)包的傳輸次數(shù)來進(jìn)行衡量。

2.2 DAEBNC的基本思想

DAEBNC的核心思想是將隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于無線網(wǎng)絡(luò)廣播通信中，減少數(shù)據(jù)包的傳輸次數(shù)，節(jié)省能量消耗。圖2給出了一個(gè)廣播源和三個(gè)接收節(jié)點(diǎn)的示例。

如圖2所示，廣播源A要將四個(gè)源數(shù)據(jù)包p1、p2、p3和p4發(fā)送給其所有的鄰居節(jié)點(diǎn)B、C和D，同時(shí)假設(shè)B已經(jīng)獲得了p2，C已經(jīng)獲得了p1，D已經(jīng)獲得了p3和p4。按照傳統(tǒng)的廣播發(fā)送方法，節(jié)點(diǎn)A逐一廣播p1、p2、p3和p4，最少需要廣播四次。

使用DAEBNC方法，如圖2所示，廣播源A通過鄰居信息表記錄其鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包的情況。節(jié)點(diǎn)A根據(jù)鄰居信息表比較各個(gè)鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包的數(shù)目面獲得最小值。在如圖2所示的表中，節(jié)點(diǎn)B和C各獲得一個(gè)源數(shù)據(jù)包，節(jié)點(diǎn)D獲得兩個(gè)源數(shù)據(jù)包，所以節(jié)點(diǎn)A的鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包數(shù)目的最小值是1。由于節(jié)點(diǎn)A有四個(gè)待發(fā)送的源數(shù)據(jù)包，于是A應(yīng)用隨機(jī)線性網(wǎng)絡(luò)編碼生成三個(gè)編碼組合包：y1=a1p1+b1p2+c1p3+d1p4、y2=a2p1+b2p2+c2p3+d2p4和y3=a3p1+b3p2+c3p3+d3p4并發(fā)送。節(jié)點(diǎn)B收到三個(gè)編碼包后，與已獲得的源數(shù)據(jù)包p2組成解碼矩陣，三個(gè)方程三個(gè)未知數(shù)就可解出p1、p3和p4。同理，節(jié)點(diǎn)C可得到p2、p3和p4，節(jié)點(diǎn)D可得到p1和p2。這樣節(jié)點(diǎn)A最少只需廣播三次就可以將所有的源數(shù)據(jù)包發(fā)送給其所有的鄰居節(jié)點(diǎn)，與傳統(tǒng)方法相比減少了傳輸次數(shù)，提高了能量利用效率。

2.3 DAEBNC的編碼策略分析

DAEBNC采用隨機(jī)線性網(wǎng)絡(luò)編碼技術(shù)，總是發(fā)送編碼數(shù)據(jù)包，根據(jù)線性方程組的求解方法，只有在方程組中方程的數(shù)目等于或大于未知數(shù)的數(shù)目時(shí)，方程組才有惟一解。換句話說，只有接收節(jié)點(diǎn)用于解碼的編碼向量矩陣的秩，即線性無關(guān)的編碼向量數(shù)目等于或大于組成編碼包的源數(shù)據(jù)包的數(shù)目時(shí)，才能保證接收節(jié)點(diǎn)的可解性。

定理1 設(shè)某廣播源節(jié)點(diǎn)S有n個(gè)待發(fā)送源數(shù)據(jù)包p1，p2，…，pn，同時(shí)S有m個(gè)鄰居節(jié)點(diǎn)r1，r2，…，rm，各個(gè)鄰居節(jié)點(diǎn)已獲得的源數(shù)據(jù)包數(shù)目分別為t1，t2，…，tm。其中0≤ti≤n，1≤i≤m，則S可以發(fā)送n-tmin個(gè)由n個(gè)源數(shù)據(jù)包p1，p2，…，pn組成的線性編碼組合包，并且在所有鄰居節(jié)點(diǎn)均具有可解性，其中對于任意的ti，1≤i≤m，有tmin≤ti。

證明 設(shè)獲得tmin個(gè)源數(shù)據(jù)包的節(jié)點(diǎn)為rj，1≤j≤m，則當(dāng)rj獲得了S發(fā)送的n-tmin個(gè)編碼包后，就可以將編碼包和已獲得的源數(shù)據(jù)包組成有n個(gè)方程和n個(gè)未知數(shù)的線性方程組，通過高斯消元可以解出未得到的n-tmin個(gè)源數(shù)據(jù)包。對于其他任意的鄰居節(jié)點(diǎn)ri，1≤i≤m且i≠j，由于其已獲得的源數(shù)據(jù)包數(shù)目ti≥tmin，在獲得S發(fā)送的n-tmin個(gè)編碼包后，ri用于解碼的線性方程組中方程的數(shù)目為ti+n-tmin≥n，也可以解出未得到的n-ti個(gè)源數(shù)據(jù)包。所以S發(fā)送的n-tmin個(gè)編碼包在所有鄰居節(jié)點(diǎn)均具有可解性。

上述定理保證了每個(gè)接收節(jié)點(diǎn)均可以解碼編碼組合包，獲得所需的源數(shù)據(jù)包。下面給出DAEBNC的編碼策略：

算法：Packets coding strategy

輸入：鄰居信息表neighborList

輸出：隨機(jī)線性網(wǎng)絡(luò)編碼組合包

begin

1.n←鄰居信息表行數(shù)；m←鄰居信息表列數(shù)

neighborList[i，j]=1←鄰居i獲得源數(shù)據(jù)包j

neighborList[i，j]=0←鄰居i沒有獲得源數(shù)據(jù)包j

outputbuffer←輸出緩沖區(qū)

M←outputbuffer中待發(fā)送的源數(shù)據(jù)包數(shù)目

count←計(jì)數(shù)某個(gè)鄰居獲得的源數(shù)據(jù)包數(shù)目

min←鄰居獲得源數(shù)據(jù)包數(shù)目的最小值

a←編碼向量；x←源數(shù)據(jù)包；y←編碼組合包

2.min=10000

3.for i=1 to n do

// 在所有鄰居中查詢獲得源數(shù)據(jù)包的情況

4. count=0；

5. for j=1 to M do

// 查詢某個(gè)鄰居獲得M個(gè)源數(shù)據(jù)包的情況

6.if neighborList[i，j]=1 then

7.count++；

// 計(jì)算某個(gè)鄰居獲得源數(shù)據(jù)包的個(gè)數(shù)

8.end if

9.end for

10.if min≥count then

11.min=count；

//尋找鄰居節(jié)點(diǎn)中獲得源數(shù)據(jù)包數(shù)目的最小值

12.end if

13.end for

14.get x1，x2，…，xM from outputbuffer；

//從outputbuffer中取出待發(fā)送的M個(gè)源數(shù)據(jù)包

15.for i=1 to m-min do

// 使用隨機(jī)線性網(wǎng)絡(luò)編碼生成m-min個(gè)編碼包

16.yi=ax=a1x1+a2x2+…+aMxM

17.end for

18.end

在2.2節(jié)圖2給出的例子中，可以將源數(shù)據(jù)包視為編碼向量為單位向量的編碼包，其編碼運(yùn)算結(jié)果就是源數(shù)據(jù)包本身的信息內(nèi)容。節(jié)點(diǎn)B接收到A發(fā)送的三個(gè)編碼包后，與已獲得的源數(shù)據(jù)包p2一起組成編碼向量矩陣。對矩陣進(jìn)行高斯消元后，就可以得到p1、p3和p4。節(jié)點(diǎn)B的編碼向量矩陣如下:

0100p2a1b1c1d1y1a2b2c2d2y2a3b3c3d3y31000p10100p20010p30001p4

在以上矩陣中，節(jié)點(diǎn)除了要獲得足夠的編碼包保證解碼之外，組成矩陣的編碼向量還要滿足線性無關(guān)，這就需要發(fā)送節(jié)點(diǎn)在足夠大的限定域內(nèi)隨機(jī)選取編碼系數(shù)。文獻(xiàn)[14]中給出在選取范圍為限定域GF（216）且網(wǎng)絡(luò)中鏈路數(shù)目不超過28的條件下，n階編碼向量矩陣為滿秩的概率是1-2-8=0.996，這就基本可以保證矩陣的編碼向量線性無關(guān)。

2.4 DAEBNC

為在實(shí)際應(yīng)用中實(shí)現(xiàn)DAEBNC，圖3給出了DAEBNC的數(shù)據(jù)包格式定義。

neighbor IDencodingvectornativepackets IDpayloadneighborpackets ID

圖3 DAEBNC的數(shù)據(jù)包格式

其中數(shù)據(jù)包的各個(gè)字段定義如下：neighbor ID域?yàn)榘l(fā)送數(shù)據(jù)包的節(jié)點(diǎn)的ID；encoding vector域?yàn)殡S機(jī)線性網(wǎng)絡(luò)編碼系數(shù)值，即隨機(jī)編碼向量值；native packets ID域?yàn)榻M成編碼包的源數(shù)據(jù)包的ID，源數(shù)據(jù)包的ID由數(shù)據(jù)包源節(jié)點(diǎn)的ID號(hào)和數(shù)據(jù)包的序列號(hào)組成，可以惟一標(biāo)志源數(shù)據(jù)包；payload域?yàn)閿?shù)據(jù)包中的信息內(nèi)容，即多個(gè)源數(shù)據(jù)包信息內(nèi)容的線性運(yùn)算結(jié)果；neighbor packets ID域?yàn)榘l(fā)送節(jié)點(diǎn)擁有的源數(shù)據(jù)包的ID。

實(shí)際應(yīng)用中，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)維護(hù)如下五種數(shù)據(jù)結(jié)構(gòu)：

a）鄰居信息表neighborList，記錄鄰居節(jié)點(diǎn)獲得的源數(shù)據(jù)包的情況。

b）輸出緩沖區(qū)outputBuffer，存放待發(fā)送的源數(shù)據(jù)包。

c）接收緩沖區(qū)receivedBuffer，存放從接收到的編碼包中解出的源數(shù)據(jù)包。

d）發(fā)送緩沖區(qū)sentBuffer，存放已經(jīng)編碼發(fā)送過的源數(shù)據(jù)包。

e）解碼矩陣decodeMatrix。矩陣的最后一列記錄編碼包的編碼信息內(nèi)容，其他各列為編碼向量的分量值；矩陣每一行記錄某個(gè)編碼包的編碼向量分量值和編碼信息內(nèi)容。

DAEBNC接收數(shù)據(jù)包的具體步驟如下：

a)節(jié)點(diǎn)接收到數(shù)據(jù)包后，首先根據(jù)neighbor ID、native packets ID和neighbor packets ID的記錄在neighborList中尋找相應(yīng)的行和列，更新鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包的記錄。

b)節(jié)點(diǎn)將encoding vector和payload的記錄放入decodeMatrix中，并根據(jù)native packets ID的記錄從outputBuffer、receivedBuffer和sentBuffer取出相應(yīng)的源數(shù)據(jù)包也放入DecodeMatrix中。

c)若decodeMatrix為滿秩，節(jié)點(diǎn)對其進(jìn)行高斯消元就得到native packets ID記錄的源數(shù)據(jù)包的信息內(nèi)容。

d)步驟c)解碼完成后，節(jié)點(diǎn)將native packets ID的記錄與receivedBuffer中的記錄比較，丟棄重復(fù)的包，將新的源數(shù)據(jù)包放入receivedBuffer中。

DAEBNC發(fā)送數(shù)據(jù)包的具體步驟如下：

a)節(jié)點(diǎn)在限定域GF（216）中隨機(jī)選取編碼向量，根據(jù)DAEBNC的編碼策略得到若干個(gè)隨機(jī)線性網(wǎng)絡(luò)編碼運(yùn)算結(jié)果。

b)節(jié)點(diǎn)根據(jù)得到的編碼運(yùn)算結(jié)果生成相應(yīng)的若干編碼組合包，將節(jié)點(diǎn)ID記錄到neighbor ID域；將編碼向量記錄到encoding vector域；將組成編碼包的源數(shù)據(jù)包ID記錄到native packets ID域；將編碼運(yùn)算結(jié)果記錄到payload域；將outputBuffer、receivedBuffer和sentBuffer中源數(shù)據(jù)包的ID記錄到neighbor packets ID域。

c)節(jié)點(diǎn)將組成編碼包的源數(shù)據(jù)包同時(shí)記錄到sentBuffer。

d)節(jié)點(diǎn)依次廣播發(fā)送編碼組合包。

3 仿真測試與分析

本文在OMNeT++中將DAEBNC方法與普通泛洪方法在不同源節(jié)點(diǎn)數(shù)目和不同節(jié)點(diǎn)發(fā)送延遲時(shí)間下的節(jié)點(diǎn)平均傳輸次數(shù)的仿真測試值進(jìn)行了比較。本文模擬在1 725 m×1 725 m的區(qū)域內(nèi)，隨機(jī)放置200個(gè)無線節(jié)點(diǎn)，節(jié)點(diǎn)發(fā)射功率為3 mW。網(wǎng)絡(luò)鏈路丟包率設(shè)置為10%，MAC子層使用標(biāo)準(zhǔn)802.11協(xié)議。令網(wǎng)絡(luò)中指定的若干節(jié)點(diǎn)各自生成一個(gè)源數(shù)據(jù)包，并將其發(fā)送到其他所有的節(jié)點(diǎn)。

圖4(a)為固定節(jié)點(diǎn)發(fā)送延遲時(shí)間為0.5 ms，通過改變發(fā)送節(jié)點(diǎn)的數(shù)目來比較DAEBNC方法和普通泛洪方法的節(jié)點(diǎn)平均傳輸次數(shù)；圖4(b)為固定發(fā)送節(jié)點(diǎn)數(shù)目為100，取不同的節(jié)點(diǎn)發(fā)送延遲時(shí)間對DAEBNC方法和普通泛洪方法的節(jié)點(diǎn)平均傳輸次數(shù)進(jìn)行比較。



由圖4(a)可以看出，兩種方法的節(jié)點(diǎn)平均傳輸次數(shù)隨著源節(jié)點(diǎn)數(shù)目的增大均有所增加。可以看到DAEBNC方法相比普通泛洪方法，對節(jié)點(diǎn)平均傳輸次數(shù)有明顯改善，這可以解釋為隨著源數(shù)據(jù)包的增多，節(jié)點(diǎn)有機(jī)會(huì)使用DAEBNC方法，根據(jù)鄰居節(jié)點(diǎn)獲得源數(shù)據(jù)包數(shù)目的最小值與待轉(zhuǎn)發(fā)源數(shù)據(jù)包數(shù)目的差值，將多個(gè)源數(shù)據(jù)包編碼發(fā)送，從而降低了數(shù)據(jù)傳輸次數(shù)。

從圖4(b)可以看出，隨著節(jié)點(diǎn)發(fā)送延遲時(shí)間的增大，普通泛洪方法在平均傳輸次數(shù)上幾乎沒有變化，而DAEBNC方法變化明顯，且平均傳輸次數(shù)仍然優(yōu)于普通泛洪方法。這是由于各個(gè)節(jié)點(diǎn)獲取和轉(zhuǎn)發(fā)數(shù)據(jù)包受發(fā)送延遲時(shí)間以及分布式模式影響而各有不同，并且隨著延遲時(shí)間的增大而更加顯著。DAEBNC方法使用節(jié)點(diǎn)與其鄰居獲取源數(shù)據(jù)包的差異決定發(fā)送次數(shù)的思想，更加有效地利用節(jié)點(diǎn)間獲取數(shù)據(jù)包情況的不同，達(dá)到改善數(shù)據(jù)傳輸次數(shù)的目的。

由不同發(fā)送節(jié)點(diǎn)數(shù)目和不同節(jié)點(diǎn)發(fā)送延遲時(shí)間下的仿真測試值可以看出，DAEBNC方法與普通泛洪方法相比，在一定的鏈路丟包率下，可以有效地減少數(shù)據(jù)的傳輸次數(shù)，從而提高能量的利用效率。

4 結(jié)束語

本文利用無線網(wǎng)絡(luò)編碼改善能量利用效率的特性，提出了一種基于隨機(jī)線性網(wǎng)絡(luò)編碼的分布式完全編碼廣播策略——DAEBNC。仿真測試結(jié)果表明，與普通泛洪方法相比，DAEBNC使用隨機(jī)線性網(wǎng)絡(luò)編碼，有效地減少了數(shù)據(jù)的廣播次數(shù)，從而提高了能量利用效率。下一步工作中需要考慮網(wǎng)絡(luò)鏈路丟包率和節(jié)點(diǎn)存放數(shù)據(jù)包的緩沖區(qū)的大小對于DAEBNC方法的影響，進(jìn)一步討論DAEBNC的應(yīng)用情況。

參考文獻(xiàn)：

[1]ZAGALJ M， HUBAUX J P， ENZ C. Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues[C]//Proc of International Conference on Mobile Computing and Networking. New York: ACM Press， 2002: 172-182.

[2]SASSON Y， CAVIN D， SCHIPER A. Probabilistic broadcast for flooding in wireless mobile Ad hoc networks[C]//Proc of IEEE Wire-less Mobile Computing and Networking. New Orleans: IEEE Press， 2003: 1124-1130.

[3]HAAS Z J， HALPERN J Y， LI L. Gossip-based Ad hoc routing[J]. IEEE/ACM Trans on Networking， 2006，14(3): 479-491.

[4]CHEN Ben-jie， JAMIESON K， BALAKRISHNAN H， et al. Span: an energy-efficient coordination algorithm for topology maintenance in Ad hoc wireless networks[J]. ACM Wireless Networks Journal， 2002， 8(5): 481-494.

[5]STOJMENOVIC I， SEDDIGH M， ZUNIC J. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[J]. IEEE Trans on Parallel and Distributed Systems， 2002， 13(1): 14-25.

[6]WU Jie， DAI Fei. A generic distributed broadcast scheme in Ad hoc wireless networks[J]. IEEE Trans on Computers， 2004， 53(10): 1343-1354.

[7]AHLSWEDE R， CAI Ning， LI S Y R， et al. Network information flow[J]. IEEE Trans on Information Theory， 2000， 46(4): 1204-1216.

[8]WU Yun-nan， CHOU P A， JAIN K. A comparison of network coding and tree packing[C]//Proc of IEEE International Symposium on Information Theory. Piscataway: IEEE Press， 2004.

[9]WU Yun-nan， CHOU P A， KUNG S Y. Minimum-energy multicast in mobile Ad hoc networks using network coding[J]. IEEE Trans on Communication， 2005， 53(11): 1906-1918.

[10]LUN D S， RATNAKAR N， KOETTER R， et al. Achieving minimum-cost multicast: a decentralized approach based on network co-ding[C]//Proc of the 24th IEEE Conference on Computer Communications. Washington DC:IEEE Computer Society， 2005: 1607-1617.

[11]LUN D S， HO T， KOETTER R. Network coding with a cost criterion[C]//Proc of Interational Symposium on Information Theory and Its Applications. 2004:1232-1237.

[12]KATTI S， RAHUL H， HU Wen-jun， et al. XORS in the air: practical wireless network coding[J]. IEEE/ACM Trans on Networking， 2008，16(3):497-510.

[13]HO T， MEDARD M. On randomized network coding[C]//Proc of the 41st Annual Allerton Conference on Communication Control and Computing. 2003.

[14]JAGGI S， SANDERS P， CHOU P A， et al. Polynomial time algorithms for multicast network code construction[J]. IEEE Trans on Information Theory， 2005， 51(6): 1973-1982.