基于隨機網絡編碼的WSN多徑傳輸自適應節(jié)能算法

孫玲芳，候志魯，許 鋒，周家波

（1.泰州學院數理信息學院，江蘇 泰州　225300；2.江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江　212003；3.江蘇科技大學 經濟管理學院，江蘇 鎮(zhèn)江　212003）

基于隨機網絡編碼的WSN多徑傳輸自適應節(jié)能算法

孫玲芳1，2，候志魯2，許 鋒3，周家波3

（1.泰州學院數理信息學院，江蘇 泰州225300；2.江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江212003；3.江蘇科技大學 經濟管理學院，江蘇 鎮(zhèn)江212003）

提出一種多路徑的無線傳感器網絡（WSN）自適應節(jié)能算法，該算法的實現(xiàn)基于隨機網絡編碼 （RNC-ESMP）。其基本思想是：首先，該算法以WSN節(jié)點能量為考量，將數據經由節(jié)點能量最多的路徑傳輸；其次，以目的節(jié)點解碼成功率為反饋因子，構建目的節(jié)點到源節(jié)點的反饋機制，實現(xiàn)自適應；再次，選擇合適的編碼策略對數據包進行編碼。最后在MATLAB環(huán)境下搭建仿真平臺進行模擬仿真。實驗結果表明，相比于傳統(tǒng)的多路徑算法，RNC-ESMP算法能夠有效降低網絡平均能耗，延長網絡生命周期。

隨機網絡編碼；無線傳感器網絡；多徑傳輸；節(jié)能算法

無線傳感器網絡中，網絡拓撲結構的時變性、傳感器節(jié)點能量有限的特點已成為制約數據傳輸可靠性的主要瓶頸。為提高信息傳遞率，多徑傳輸成為主要實現(xiàn)方式之一［1-2］，即構建多條源節(jié)點到信宿節(jié)點路徑，將網絡能耗平均分配給這些路徑，這樣的策略能有效延長網絡生命周期。

網絡編碼（NC）理論最先由Ahlswede等人提出［3］，指出網絡中間節(jié)點能夠對接收的數據包進行編碼融合并轉發(fā)，提升了網絡吞吐量。Ho等人［4］提出了隨機網絡編碼（RNC），這是一種分布式的碼構造算法，比較適用于WSN這類網絡拓撲結構不斷變化的網絡環(huán)境。文獻［5］從能量的角度出發(fā)，將RNC應用于無線傳感器網絡，證明了隨機網絡編碼的能量效益。文獻［6］將網絡編碼應用于WSN多徑傳輸中，從傳輸路徑數的角度提高了數據傳輸可靠性，降低了網絡能耗。文獻［7］分析了多路徑之間的相互干擾并提出一種低干擾能量有效多路徑建立算法，該算法能夠提高數據包的傳遞效率，延長網絡壽命。

然而現(xiàn)有的多徑傳輸都缺乏自適應，沒有建立反饋機制，即數據傳輸過程中一旦因某種故障而影響信息傳遞時，信源節(jié)點不能對傳輸路徑數作出及時有效的調整。此外現(xiàn)有研究對于網絡中間節(jié)點采用全部編碼的策略，在產生編碼冗余的同時消耗了過多能量，網絡生命周期也會相應縮短。

基于上述考慮，文中提出一種基于隨機網絡編碼的無線傳感器網絡多徑傳輸自適應節(jié)能算法（RNC-ESMP）。該算法從節(jié)點能量的角度出發(fā)，優(yōu)先選擇節(jié)點剩余能量最多的路徑進行數據傳輸；其次，以目的節(jié)點解碼成功率為反饋因子構建反饋機制，源節(jié)點對傳輸路徑數作出有效調整以實現(xiàn)算法的自適應；再次，提出中間節(jié)點編碼選擇方案和節(jié)點編碼概率，有效減少了冗余數據的編碼，降低了編碼復雜性。最后通過實驗驗證了該算法在降低網絡平均能耗和延長網絡生命周期方面的優(yōu)越性。

1　能量效益

1.1能量消耗特征

概括的說，一個典型的無線傳感器節(jié)點由兩部分構成：能量消耗模塊以及能量供應模塊。其中，能量消耗模塊具體又包括傳感器模塊、微處理器模塊和無線通信模塊。節(jié)點各模塊消耗能量的比重如圖1所示。

圖1　無線傳感器節(jié)點能耗分布

從圖1可以看出，節(jié)點絕大部分能量消耗在無線通信模塊上。該模塊有四種狀態(tài)，在空閑狀態(tài)時一直監(jiān)聽無線信道的使用情況，檢查是否有數據發(fā)送給自己，在睡眠狀態(tài)則關閉通信模塊。在發(fā)送狀態(tài)的能量消耗最大，空閑狀態(tài)和接收狀態(tài)的能耗接近，比發(fā)送狀態(tài)的能耗少一些，在睡眠狀態(tài)的能量消耗最小。

1.2能耗模型

從1.1節(jié)可知，WSN節(jié)點總能耗：

式中 ERX、ETX、EFR、EST分別為無線通信在接受、發(fā)送、空閑、睡眠狀態(tài)能耗。當傳感器節(jié)點正常工作時，此時有

根據文獻［8］建立能耗模型

式中EEN為節(jié)點發(fā)送（或接受）1 bit數據能耗，d為發(fā)送、接收節(jié)點間距，Eamp表示將信號放大所消耗的能量，γ表示路徑的損耗因子。節(jié)點剩余能量

式中EINIT為節(jié)點初始能量，N為總的傳輸數據量。算法考慮編碼數據消耗的能量ECODE，綜合以上三式，可得節(jié)點剩余能量

式中PCODE為節(jié)點平均編碼概率。

2　路徑選擇概率

WSN多徑傳輸中，因節(jié)點位置和節(jié)點間距的不同，導致數據傳輸時節(jié)點的剩余能量也不同。為此本節(jié)引入條件傳輸價值比的概念并提出以此為依賴的多路徑算法。

建立有向圖G（V，E），V為節(jié)點集，E為邊集，In（i）、Out （i）表示節(jié)點的入度和出度。Vpm（S，D）為路徑P除S、D外的節(jié)點集。Vps（S，D）為路徑P所有節(jié)點集。Eij為節(jié)點i到j的信息傳遞消耗能量。

定義：條件傳輸價值比：節(jié)點剩余能量與節(jié)點消耗能量的比值。由式（5）可得路徑的條件傳輸價值比為

可見路徑被選擇的概率與該路徑的條件傳輸價值比成正比。在多路徑傳輸中，冗余路徑是經常存在的，當條件傳輸價值比小于1時，冗余路徑無法傳遞信息。為降低計算復雜度應將這些冗余路徑丟棄，建立傳輸路徑集合

根據公式（6）和公式（7）建立路徑的選擇概率

在路徑選擇概率確定的情況下，依據傳遞信息需要的路徑數，將信息在最高的條路徑傳輸，將其他路徑中的節(jié)點置于睡眠狀態(tài)，路徑被選中時，再喚醒這些節(jié)點，使系統(tǒng)始終處在低功耗狀態(tài)。

3　解碼反饋

節(jié)點收發(fā)能耗、傳輸數據量和路徑總數決定了多徑傳輸的總能耗，其中路徑總數對系統(tǒng)總能耗的影響最大。為了能夠對傳輸所需路徑數作出合理調整，本節(jié)以目的節(jié)點解碼成功率P為反饋因子，構建從目的節(jié)點到源節(jié)點的反饋機制，將P 經Dijkstra算法求得的目的節(jié)點到源節(jié)點的最短路徑反饋給源節(jié)點。源節(jié)點通過將P與其期望的解碼成功率PEXP比較，以對路徑數作出合理調整。具體的算法流程圖如圖2所示。

圖2　解碼反饋算法流程圖

4　編碼策略

4.1隨機網絡編碼

由于WSN拓撲結構的不斷變化，本文采用隨機網絡編碼對數據進行編解碼。本節(jié)首先結合圖3說明隨機網絡編碼的編解碼原理。如圖3所示，信源節(jié)點S將消息X1和X2傳輸給信宿節(jié)點R1和R2。

1）編碼原理。在有限域F上選取各鏈路上的系數（ξ1，ξ2，…，ξn），且系數與該鏈路上所有信息的線性組合均傳遞至下個節(jié)點。例如，S將C1=ξ1X1+ξ2X2和系數ξ1、ξ2傳輸到節(jié)點A，A將之傳輸給U和信宿節(jié)點R1。同理，S將C2=ξ3X1+ξ4X2和系數ξ3、ξ4傳輸到節(jié)點B，節(jié)點B將之傳輸給U和信宿節(jié)點R2。接著U將其收到的C1和C2，再次線性組合C3=ξ5（ξ1X1+ξ2X2）+ξ6（ξ3X1+ξ4X2）=（ξ5ξ1+ξ6ξ3）X1+（ξ5ξ2+ξ6ξ4）X2，并將系數 ξ5ξ1+ξ6ξ3和ξ5ξ2+ξ6ξ4傳遞給節(jié)點V，節(jié)點V將其傳遞給信宿節(jié)點R1和R2。

2）解碼原理。例如，針對信宿節(jié)點R1，收到下面兩個方程

同理針對信宿節(jié)點R2，則收到下面兩個方程

只要X1和X2的系數矩陣滿秩，利用高斯消元法，信宿節(jié)點R1、R2就能正確譯碼出消息X1和X2，于是譯碼過程就轉化成了求解線性方程組的問題。

圖3　隨機網絡編碼原理圖

4.2節(jié)點編碼方案

在真實環(huán)境中，編碼節(jié)點并不能總是同時收到源節(jié)點發(fā)送的數據。若某編碼節(jié)點先收到某條鏈路的數據，此時若該節(jié)點等收到全部鏈路的數據后再執(zhí)行編碼操作，則消耗大量能量并增大了時延。本文將中間節(jié)點對數據的處理劃分為接收、編碼與發(fā)送3個步驟。若節(jié)點最大緩存為，則編碼節(jié)點緩存模型如圖4所示。

圖4　編碼節(jié)點緩存模型

節(jié)點緩存數據有兩種情況：直接轉發(fā)和編碼轉發(fā)。假定接收數據A的鏈路優(yōu)先級別較高，比接收數據B提前到達編碼節(jié)點，緩存數據記A為｛A1，A2，…，Aw｝，緩存數據B記為｛B1，B2，…，Bw｝。節(jié)點編碼考慮如下3種方案：

1）：緩存為FIFO模式，當B到達編碼節(jié)點時緩存空，則A繼續(xù)向緩存寫入數據；

2）：當B到達編碼節(jié)點，執(zhí)行A1⊕B1，若A標示到Aw，則A的緩存已寫滿，A1直接被轉發(fā)，A的緩存表示符也會相應改變；

3）：若B的優(yōu)先級別較高，則采用與（1）和（2）相似的編碼選擇方案。

假設數據Ai被直接轉發(fā)的概率為θ，則編碼執(zhí)行概率為

對整個網絡而言，節(jié)點平均編碼概率為：

式中m為所有具有編碼能力的節(jié)點集合。

5　性能仿真與分析

本章首先針對WSN可變的拓撲結構，在路徑總數情況下，對比不同有限域和丟包率時的解碼成功率，結果如圖5所示。

圖5　受不同有限域和丟包率影響的解碼成功率

5.1仿真參數與性能指標

為了評估文中所提出的算法（RNC-ESMP）的優(yōu)越性，在MATLAB環(huán)境下搭建仿真平臺。實驗中，配置3種方案比對：方案A：傳統(tǒng)多路徑算法（TD-MR）；方案B：基于NC的多路徑算法（NC-MR）；方案C：基于RNC的WSN多徑傳輸自適應節(jié)能算法（RNC-ESMP）。實驗仿真中各參數取值如表1。

表1　性能仿真參數列表

為了評估3種方案的性能，文中以網絡平均能耗和網絡生命周期為性能指標。

定義 網絡平均能耗：參與數據傳輸節(jié)點的總能耗與節(jié)點個數的比值；

定義 網絡生命周期：網絡從開始運行到因節(jié)點能量耗盡導致無法形成一條有效鏈路用以傳輸數據的時間。

5.2仿真結果與分析

設傳輸200 bit數據量，比較了3種方案的網絡平均能耗和網絡生命周期受丟包率變化的影響，仿真結果分別如圖6、7。

圖6　不同算法下網絡平均能耗受丟包率的影響

圖7　不同算法下網絡生命周期受丟包率的影響

從圖5可以看出，伴隨丟包率的不斷增長，3種方案下的平均網絡能耗也在逐漸增加，增幅也逐漸變大。相比方案B 和C，方案A的網絡平均能耗遠遠大出許多。由圖5可知，在丟包率ρ=0.5點，方案B和C的平均網絡能耗約為方案A的一半。相比多徑傳輸策略，網絡能耗會隨著路徑數量的增加而呈正比的增長。網絡編碼和多徑傳輸的應用，即使是少量的丟包，只要信宿節(jié)點收到的向量組合線性無關，就能正確解碼。與方案B相比，方案C的網絡平均能耗有小幅度降低，這是由于在方案C引入了反饋機制，減少了部分能量消耗。但相對通信節(jié)點的收發(fā)能耗，這部分能耗顯得比較小。因而方案C在比方案B略能節(jié)省網絡耗能，方案C的優(yōu)勢也得以體現(xiàn)。

網絡生命周期的長短是衡量WSN性能的重要參數。仿真過程中，發(fā)送每個新數據包的時間間隔設為t=10 s。當某節(jié)點剩余能量為0，則該節(jié)點所在的路徑失效；當失效路徑過多造成信息傳輸失敗時，則網絡失效。從圖6可以看出，當丟包率相同時，方案C的網絡生命周期最長，在ρ=0.30點體現(xiàn)的最為明顯。

6　結　論

與傳統(tǒng)的多路徑算法（TD-MR）和基于網絡編碼的多路徑算法 （NC-MR）相比，本文提出的基于隨機網絡編碼的WSN多徑傳輸自適應節(jié)能算法（RNC-ESMP）通過建立節(jié)點能耗模型，結合自適應反饋機制并采用合適的中間節(jié)點編碼策略，在保證數據傳輸可靠性的同時能有效地降低網絡平均能耗，延長網絡生命周期，大大提升了WSN性能。

［1］GANESAND D，GOVIDAN R，SHENKER S，et al.Highlyresilient，energy-efficient multi-pathroutinginwireless sensor networks［J］.Mobile Computing and Communications Review，2001，5（4）：251-254

［2］DJUKIC P，VALAEE S.Reliable packet transmissions in multi-path routed wireless networks［J］.IEEE Transactions on Mobile Computing，2006，5（5）：548-559.

［3］Ahlswede R，Cai N，LIS Y R，et al.Yeung.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

［4］Ho T，Medard M，Shi J，et al.On Randomized Network Coding［C］.Allerton Conference On Communication，Control and Computing，2003.

［5］PLATZ D，WOLDEGEBREAL D H，KARL H.Random network coding in wireless sensor networks：energy efficiency via cross-layer approach［C］//Proceedings of 10 th International Symposium on Spread Spectrum Techniques and Application（ISSSTA）.Bologna，Italy：IEEE，2008：654-660.

［6］WANG L，WANG Y，ZHAO W.Network coding-based multipath routing for energy efficiency in wireless sensor networks ［J］.EURASIP Journal on Wireless Communications and Networking，2012（1）：1-15.

［7］李姍姍，廖湘克，朱培棟.基于網絡編碼的無線傳感器網絡多路徑傳輸方法［J］.軟件學報，2008，19（10）：2638-2647.

［8］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless micro-sensor networks［J］.IEEE Transactions on Wireless Communications，2010，1（4）：660-670.

An energy-saving multi-path adaptive algorithm based on random network coding in wireless sensor networks

SUN Ling-fang1，2，HOU Zhi-lu2，XU Feng3，ZHOU Jia-bo3
（1.Department of Mathematics and Information Engineering，Taizhou College，Taizhou 225300，China；2.School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212003，China；3.School of Economic and Management，Jiangsu University of Science and Technology，Zhenjiang 212003，China）

The paper proposes an energy-saving multi-path adaptive algorithm based on random network coding in wireless sensor networks（RNC-ESMP）.First of all，This algorithm considers the nodes'energy，let the data packets transmitted on the paths which have least energy consumption during data transferring.Second，considering the decoding probability of the sink nodes as the feedback factor，the algorithm builds a feedback mechanism from the sink nodes to the source nodes to make selfadaptive impossible.Then the algorithm proposes the encoding options and probability of the intermediate nodes so as to reduce the complexity of encoding.At last，it builds the platform on MATLAB to simulate the algorithm.The results of the experiment shows that this algorithm not only can reduce the average energy consumption of networks efficiently but also can extend the networks'life-time.

random network coding；wireless sensor networks；multi-path transmission；energy-saving algorithm

TN919.72

A

1674－6236（2016）09-0081-04

2015-05-27稿件編號：201505243

孫玲芳（1963—），男，江蘇鎮(zhèn)江人，博士，教授。研究方向：電子商務、信息安全。