無線傳感網使用網絡編碼的新型數據傳輸方法

楊 波，徐建波

湖南科技大學 計算機科學與工程學院，湖南 湘潭 411201

無線傳感網使用網絡編碼的新型數據傳輸方法

楊 波，徐建波

湖南科技大學 計算機科學與工程學院，湖南 湘潭 411201

1 概述

無線傳感器網絡是一種以數據為中心的網絡，許多應用需要很高的數據傳輸可靠性，要求數據從源節點可靠地傳輸到目的節點。

傳統提高數據傳輸可靠性的方法通過增加數據冗余傳輸實現，主要有重傳和多路徑兩種方式[1-2]。重傳中，為了保證數據可靠傳輸，每跳信息傳輸都需要確認機制，以保轉發成功；多路徑方法事先根據所需的信息傳輸可靠性計算出路徑數，將信息沿著多條路徑傳輸，該方法不需要確認消息，但需要維護多條路徑，控制復雜。增加數據冗余傳輸的思想以消耗傳感器節點大量額外能量為代價，而且控制信息量大。由于傳感器節點能量非常有限，大量的冗余數據傳輸很容易使節點能量消耗殆盡，縮短網絡壽命。

2000年，Ahlswede等人[3]提出網絡編碼理論，其初衷是為了提升組播傳輸的網絡吞吐量。伴隨著研究不斷深入，網絡編碼其他方面的優點也體現了出來[4-5]，如均衡網絡負載、節省網絡帶寬、減少網絡能耗等。在提高無線傳感器網絡數據傳輸可靠性方面，文獻[6]提出了一種基于網絡編碼的無線傳感網多路徑傳輸方法；文獻[7]借助網絡編碼為傳感器網絡提出了一個數據收集協議SenseCode；文獻[8]在無線網絡中將基于簇的協作通信與網絡編碼結合起來研究；文獻[9]提出了一種無線傳感器網絡基于網絡編碼的機會路由機制。這些方法都采用類似的隨機線性編碼策略，需攜帶編碼向量傳輸，附帶信息量大；而且許多策略都需要構建固定傳輸路徑，網絡各節點能量消耗不夠均衡。

本文首先設計了一個新的編碼矩陣構造方法，它能提高解碼效率且不用傳輸編碼向量；隨后提出了一種新的數據包轉發策略，通過“區域推進”機制，實現數據的可靠傳輸與各節點的均衡能耗，并極大地減少不必要的冗余傳輸。新的數據傳輸策略簡單易行，可提高數據傳輸可靠性，提升網絡整體性能。

2 實用網絡編碼思想

實用的基于網絡編碼的數據傳輸方法的基本思想是，源節點將要傳輸的多份數據編碼成許多彼此無關的數據，目的端只要接受到一部分編碼數據就能恢復出原始數據。具體的過程如下。

源節點S具有k份數據，記為 x1，x2，…，xk，需要發送給目的節點D。發送前，源節點S隨機產生n個(n＞k)k維（每個向量含有k個分量）向量，記為v1，v2，…，vn，即

各向量稱作編碼向量。

將這n個向量與k份數據進行式（3）的編碼運算，得到n份編碼數據，記為 y1，y2，…，yn，即

這些編碼向量組成的矩陣稱為編碼矩陣。

源節點S將每個編碼后的數據 yj(j=1，2，…，n)與其對應的編碼向量打包，得到n個編碼數據包，記為 pj(j=1，2，…，n)，將這n個編碼數據包發往目的節點D。目的節點收到足夠的編碼包后，當有k個編碼向量線性無關時，就能解碼出原始數據x1，x2，…，xk，如式（4）所示。

需要說明的是，為便于計算機存儲和計算，編碼、解碼運算均是指有限域GF(2q)中運算。

3 新的編碼矩陣構造方法

現有方法中，編碼矩陣都是通過在有限域中隨機生成各編碼向量得到，這不利于解碼甚至造成解碼失敗；而且需要攜帶各編碼向量傳輸，以便目的節點獲得解碼向量。傳感器節點能量有限，應盡量節能，減少額外信息傳輸，延長網絡壽命。

雖然有文獻指出增大有限域、或者讓中間節點對接受到的數據包再次編碼以增加編碼向量之間線性無關的機會，但都無法使解碼得到最終保證。而且，有限域越大，傳輸編碼向量的負擔也越大。

下面提出一種新的編碼矩陣構造方法，它能保證任意的k個編碼向量線性無關，且不用攜帶編碼系數傳輸，目的節點只要收到任意k個編碼包即可推導出k個編碼向量并成功解碼。

3.1 構造編碼矩陣

定理1構造如下的矩陣M，其中k＜n，ai≠aj(i≠j)，ai≠0 (i=1，2，…，n)，則M中的任意k個列向量線性無關。

證明 如下所示構建范德蒙行列式A，矩陣B是A對應的矩陣：

由范德蒙行列式的性質，當ai(i=1，2，…，n)互不相等時，行列式A≠0，因此，矩陣B的秩R(B)=n，所以矩陣B 的n個列向量線性無關。

從矩陣M中任意取k個列向量，由于每個列向量有k個分量，則這k個列向量可構成一個行列式，記為C，設行列式C對應的矩陣記為D。由矩陣M可知，行列式C仍是一個范德蒙行列式，所以C≠0，因此行列式C對應的矩陣D的秩R(D)=k，即滿秩，因此D中的k個列向量線性無關。證畢。

3.2 編碼實現與解碼

使用新的編碼矩陣對原始數據編碼過程如式（5）所示。其中，D=(d1d2…dk)，表示由k份原始數據d1，d2，…，dk組成的數據行向量。編碼矩陣M的每個列向量即為編碼向量，編碼向量的第二個分量即ai稱為編碼向量標識，只需攜帶編碼向量標識傳輸即可。

每當sink收到一個編碼包，就可獲得該包的編碼數據yi和對應的編碼向量標識ai，從而可導出該編碼包的編碼向量，即

當sink收到源節點S的任意k個編碼包后，即可推導出對應的k個編碼向量和編碼數據。由定理1可知，這任意k個編碼向量是線性無關的。因此，收到任意k個編碼包即可成功解碼。

4 新型數據傳輸策略

現有基于網絡編碼的數據傳輸方法中，數據傳輸需要構建固定傳輸路徑，構建和維護多條路徑控制復雜。數據包只能沿著固定的路徑傳輸到sink節點，當一路徑上的某個節點失效會造成數據鏈路的中斷，不能保證每跳轉發成功。

下面提出一種新的數據轉發策略，不用構建固定傳輸路徑，使用區域推進機制，把數據可靠地向sink推進，能保證每跳可靠轉發和節點間均衡能耗。

4.1 區域推進機制

該策略中，數據傳輸不使用傳統的圖1所示的固定路徑模式，而是使用圖2的模式，本文稱之為區域推進。

圖1 固定路徑

圖2 區域推進

區域推進的基本思想是，在遠區（如區域A）使用一種簡單的策略自動選擇最佳代表節點將數據“推向”近區（如區域B）。

區域推進充分利用無線通信的廣播優勢，受到廣播信息的節點都具有轉發信息的可能性，動態地自動選取某些最佳節點轉發數據，將數據向前推進；而固定路徑只有特定的節點才會轉發數據。區域推進不用建立固定的傳輸路徑；與分簇相比，不用周期性地選擇簇頭，不用構建和維護簇，也不用只由簇頭將數據傳送給下一個簇頭。

4.2 策略實現

使用如圖3的網絡模型，網絡以sink為中心被劃分成許多圓環，每個圓環的寬度為r/4，r為傳感器節點的最大輻射半徑。每個圓環內的節點都有一個相同的圓環ID號，不同圓環內的節點的圓環ID號不同，圓環ID號從里向外依次為1，2，…，n。圓環ID號代表節點到sink的跳數，也代表節點到sink的距離。這樣，每個圓環就代表了一個區域，數據沿著圓環由外往里向sink推進。

圖3 網絡模型示意

數據傳輸之前，源節點S需要對每個編碼數據打包，數據包由包頭和包體組成。包體即為一個編碼數據；包頭有三部分：編碼向量標識、源節點S的ID號和當前節點圓環ID號。數據包傳輸過程中，當前節點圓環ID號會逐步被修改。

當某個節點收到（receive）一個數據包后，若該節點的圓環ID號小于收到包的包頭中的圓環ID號，則接受（accept）該包，否則丟棄（discard）該包。為便于討論，下面使用示意圖進行說明，該討論具有一般性。

如圖4所示，假設在某時刻，節點1為轉發節點，則稱區域C為轉發節點的后向區域，區域D為轉發節點的所在區域，區域E、F為轉發節點的前向區域。本文中，節點轉發數據包的輻射半徑設為r/2。因此，當節點1轉發數據包時，只有區域E、F中的節點才會接受包，區域C、D中的節點不接受包。

圖4 數據轉發

當節點a接受一個包 pj時，便計算出其對該包的轉發概率 pa(pj)和轉發等待時間ta(pj)。pa(pj)計算方法如式（7）所示：

其中，ERes(a)表示節點a的當前剩余能量，EIni(Const)為統一設定的初始能量參考值，是個常量，各節點中該值都相同。

由于區域的寬度為r/4，數據包的轉發半徑為r/2，因此，節點1轉發數據包時會跨越覆蓋其前向(0，r/4)區域E，但只部分覆蓋(r/4，2r/4)區域F。所以，若F中有節點接收到轉發包，則應從F中選取轉發節點，否則從E中選取下一輪轉發節點，目的是讓每次轉發都將數據推進的更遠。據此設計ta(pj)如式（8）所示：

其中，T為一個事先約定時間系數。于是，所有F中的接受節點的轉發等待時間均小于T，而E中的所有接受節點的轉發等待時間都大于T但小于2T。下面討論如何自動確定下一次的轉發節點。

某個接受節點在其轉發等待時間內，若沒有偵聽到“抑制”信號，則表示還沒有節點轉發該包，該節點a就獲得該包的轉發權。獲得轉發權的節點立即發送一個該包的“抑制”信號，抑制信號發射半徑為r，用于抑制所有其他接受節點再次轉發該包。所以，ta(pj)最小的節點就被自動選取為最佳轉發節點。

如圖5，節點1廣播后，節點2、3、4都將收到，由于數據包發射半徑為r/2，所以兩個接受節點如2、3之間的距離可能會大于r/2，但一定不超過r。因此，選取抑制信號發射半徑為r，這樣，所有其他接受節點都將收到抑制信號，從而放棄轉發。

圖5 抑制信號

選取出的轉發節點廣播抑制信號后，立即將包頭的當前節點圓環ID號更新為自身的圓環ID號，并進行下一步的數據推進。

另一方面，某個接受節點在其轉發等待時間內，若偵聽到了“抑制”信號，則表明已有節點轉發該包，因此收到抑制信號的節點將該包丟棄不再轉發。

本文網絡模型中，數據包的轉發半徑為r/2，抑制信號發射半徑為r，這樣，數據包在往sink方向的“推進”過程中，每次推進一定會選出一個最佳轉發節點，保證了向前推進的可靠性。使用抑制信號機制，所有其他接受節點不再重復轉發，避免了不必要的冗余傳輸，節約節點能量，也降低了沖突和干擾。

從上述轉發節點的產生過程可以看出，在所有接受節點，當前剩余能量最多的節點轉發概率越大，轉發等待時間越短，從而越容易獲得轉發權，這樣每次獲得的轉發節點都是最優的。數據包以這種方式傳輸，不僅保證了每跳傳輸的可靠性，而且實現了各節點間能耗的均衡，避免了某些節點由于能耗過快而過早死亡。

5 性能分析

無線傳感器網絡現有基于網絡編碼的數據傳輸方法需要攜帶編碼向量傳輸，需要構建固定的多條路徑，這些固定路徑上的節點能量消耗快，沒有實現網絡的均衡能耗。本文新策略具有如下優點：不用構造和維護固定路徑，路由簡便且有效；不用攜帶編碼系數，節約傳輸系數的能量消耗；使用“區域推進”機制轉發數據包，保證了每跳可靠傳輸；充分利用無線通信廣播特性，實現節點間能耗的均衡使用；sink只要收到任意k個編碼包就可以成功解碼出原始k份數據。

表1對基于網絡編碼的多路徑傳輸（記為NCM）和本文新方法（記為NCDT）進行了對比分析，其中的sink解碼成功率是指sink收到k個編碼包的解碼成功率。

仿真關鍵參數設置如下，網絡大小為200 m×200 m，傳感器節點個數為400，各節點在網絡中隨機均勻分布，能量不可補充，sink位于網絡中心位置，傳感器節點的最大輻射半徑r設為20 m，以下結果為重復運行100次仿真的平均性能。

表1 NCM和NCDT性能對比

（1）為比較數據傳輸的可靠性，定義冗余系數為發送的編碼包數量與實際應發送的原始數據數量的比率。如某源點S有5份原始數據需要傳輸給sink節點，當冗余系數取2時，則S對源數據編碼后往外發送編碼包個數為5×2=10。圖6比較了NCDT和NCM在不同冗余系數下的傳輸成功率，可以看到，在較小冗余系數時NCDT優勢較大。這是由于當傳輸的編碼包較少時，新策略能保證sink收到任意k個編碼包即成功解碼。

圖6 數據傳輸可靠性分析

（2）網絡的生存周期可以用存活節點的數量間接反映出來。圖7是網絡中存活節點百分比隨網絡運行時間的變化，可以看出，NCM節點存活數量下降較快，因為NCM使用多條固定路徑且攜帶編碼向量傳輸會造成路徑上節點的能量快速消耗，網絡沒有實現均衡能耗。

圖7 網絡節點的生命周期

6 結束語

本文設計了一種新的編碼矩陣生成方法，提出了一種新的基于網絡編碼的可靠數據傳輸策略。該策略不用傳輸編碼系數，充分利用了無線通信廣播特性，使用“區域推進”機制實現數據的可靠傳輸。sink節點根據收到的編碼包可推導出編碼系數，且只要收到任意k個編碼包就可解碼出k個原始數據，而以前的方法很難做到這一點。與傳統的冗余傳輸、基于網絡編碼的多路徑數據傳輸等思想相比，新的數據傳輸策略控制簡單，能提高數據傳輸可靠性，并實現節點之間能量的均衡利用。

[1]Deb B，Bhatnagar S，Nath B.ReInForm：reliable information forwarding using multiple paths in sensor networks[C]// Proc of the 28th Annual IEEE Conf on Local Computer Networks.Los Alamitos：IEEE Computer Society，2003：406-415.

[2]Popa L，Raiciu C，Stoica I，et al.Reducing congestion effects in wireless networks by multipath routing[C]//Proc of the ICNP.Santa Barbara：IEEE Press，2006：96-105.

[3]Ahlswede R，Cai N，Li S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000，46 （4）：1204-1216.

[4]Noguchi T，Matsuda T，Yamamoto M.Performance evaluation of new multicast architecture with network coding[J]. IEICE Trans on Comm，2003.

[5]康巧燕，孟相如，王建峰.網絡編碼對組播通信的性能改善[J].計算機工程與應用，2007，43（3）：150-152.

[6]李珊珊，廖湘科，朱培棟，等.基于網絡編碼的無線傳感網多路徑傳輸方法[J].軟件學報，2008，19(10）：2638-2647.

[7]Lorenzo K，Emre A，Katerina A，et al.SenseCode：network coding forreliable sensornetworks[R].Lausanne，Switzerland：EPFL，2009.

[8]Haas Z J，Chen T C.Cluster-based cooperative communication with network coding in wirelessnetworks[C]//IEEE MILCOM.[S.l.]：IEEE Press，2010：596-603.

[9]Rout R R，Ghosh S K，Chakrabarti S.A network coding based probabilistic routing scheme for wireless sensor networks[C]//Wireless Communication and SensorNetworks （WCSN）.Allahabad：[s.n.]，2010：1-6.

YANG Bo,XU Jianbo

School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China

Recent researches show network coding can improve data transmission reliability in wireless sensor networks,existing network coding-based data transmission strategies select encoding vectors randomly and use fixed paths to transmit packets, which causes performance deficiencies.This paper designs a new scheme for constructing encoding matrix,and proposes a novel reliable data transmission method.Any k encoding vectors of the new encoding matrix are linearly independent and encoding vectors are not need to be transmitted to sink.Data forwarding uses“region pushing”mechanism,which automatically selects the best forwarding nodes to“push”packets from one area to another area closer to sink.Analysis and simulation results illustrate that the new proposed method can improve data transmission reliability and reduce network energy consumption.

wireless sensor network;network coding;data transmission;encoding matrix;reliability

網絡編碼能提高無線傳感器網絡數據傳輸可靠性，針對現有基于網絡編碼的數據傳輸策略隨機選取編碼向量和使用固定路徑所帶來的缺陷，設計了一個新的編碼矩陣構造方法，并提出了一種新型的基于網絡編碼的可靠數據傳輸方法。該編碼方案能保證任意k個編碼向量線性無關，且不用傳輸編碼向量。數據轉發使用“區域推進”機制，自動選取最佳轉發節點，將數據包可靠地向sink“推進”，并實現了最少冗余傳輸和網絡均衡能耗。分析與仿真表明，新的數據傳輸策略能消除現有方法的缺陷，提高數據傳輸可靠性，降低能耗。

無線傳感器網絡；網絡編碼；數據傳輸；編碼矩陣；可靠性

A

TP393

10.3778/j.issn.1002-8331.1108-0371

YANG Bo,XU Jianbo.Novel data transmission method in wireless sensor network using network coding.Computer Engineering and Applications,2013,49（5）：99-102.

湖南省教育廳科學研究重點項目（No.09A027）；湖南省自然科學基金項目（No.09JJ9006）；湖南科技大學研究生創新基金（No.S100117）。

楊波（1986—），男，碩士研究生，主要研究領域為無線傳感器網絡；徐建波（1963—），男，博士，教授。E-mail：bozyyang@126.com

2011-08-25

2011-10-08

1002-8331（2013）05-0099-04

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1000.015.html