基于隨機網(wǎng)絡(luò)編碼的WSN多徑傳輸自適應(yīng)節(jié)能算法

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

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

基于隨機網(wǎng)絡(luò)編碼的WSN多徑傳輸自適應(yīng)節(jié)能算法

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

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

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

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

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

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

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

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

1　能量效益

1.1能量消耗特征

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

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

從圖1可以看出，節(jié)點絕大部分能量消耗在無線通信模塊上。該模塊有四種狀態(tài)，在空閑狀態(tài)時一直監(jiān)聽無線信道的使用情況，檢查是否有數(shù)據(jù)發(fā)送給自己，在睡眠狀態(tài)則關(guān)閉通信模塊。在發(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)能耗。當(dāng)傳感器節(jié)點正常工作時，此時有

根據(jù)文獻［8］建立能耗模型

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

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

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

2　路徑選擇概率

WSN多徑傳輸中，因節(jié)點位置和節(jié)點間距的不同，導(dǎo)致數(shù)據(jù)傳輸時節(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(luò)的信息傳遞消耗能量。

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

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

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

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

3　解碼反饋

節(jié)點收發(fā)能耗、傳輸數(shù)據(jù)量和路徑總數(shù)決定了多徑傳輸?shù)目偰芎模渲新窂娇倲?shù)對系統(tǒng)總能耗的影響最大。為了能夠?qū)鬏斔杪窂綌?shù)作出合理調(diào)整，本節(jié)以目的節(jié)點解碼成功率P為反饋因子，構(gòu)建從目的節(jié)點到源節(jié)點的反饋機制，將P 經(jīng)Dijkstra算法求得的目的節(jié)點到源節(jié)點的最短路徑反饋給源節(jié)點。源節(jié)點通過將P與其期望的解碼成功率PEXP比較，以對路徑數(shù)作出合理調(diào)整。具體的算法流程圖如圖2所示。

圖2　解碼反饋算法流程圖

4　編碼策略

4.1隨機網(wǎng)絡(luò)編碼

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

1）編碼原理。在有限域F上選取各鏈路上的系數(shù)（ξ1，ξ2，…，ξn），且系數(shù)與該鏈路上所有信息的線性組合均傳遞至下個節(jié)點。例如，S將C1=ξ1X1+ξ2X2和系數(shù)ξ1、ξ2傳輸?shù)焦?jié)點A，A將之傳輸給U和信宿節(jié)點R1。同理，S將C2=ξ3X1+ξ4X2和系數(shù)ξ3、ξ4傳輸?shù)焦?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，并將系數(shù) ξ5ξ1+ξ6ξ3和ξ5ξ2+ξ6ξ4傳遞給節(jié)點V，節(jié)點V將其傳遞給信宿節(jié)點R1和R2。

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

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

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

圖3　隨機網(wǎng)絡(luò)編碼原理圖

4.2節(jié)點編碼方案

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

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

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

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

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

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

假設(shè)數(shù)據(jù)Ai被直接轉(zhuǎn)發(fā)的概率為θ，則編碼執(zhí)行概率為

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

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

5　性能仿真與分析

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

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

5.1仿真參數(shù)與性能指標

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

表1　性能仿真參數(shù)列表

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

定義 網(wǎng)絡(luò)平均能耗：參與數(shù)據(jù)傳輸節(jié)點的總能耗與節(jié)點個數(shù)的比值；

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

5.2仿真結(jié)果與分析

設(shè)傳輸200 bit數(shù)據(jù)量，比較了3種方案的網(wǎng)絡(luò)平均能耗和網(wǎng)絡(luò)生命周期受丟包率變化的影響，仿真結(jié)果分別如圖6、7。

圖6　不同算法下網(wǎng)絡(luò)平均能耗受丟包率的影響

圖7　不同算法下網(wǎng)絡(luò)生命周期受丟包率的影響

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

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

6　結(jié)　論

與傳統(tǒng)的多路徑算法（TD-MR）和基于網(wǎng)絡(luò)編碼的多路徑算法 （NC-MR）相比，本文提出的基于隨機網(wǎng)絡(luò)編碼的WSN多徑傳輸自適應(yīng)節(jié)能算法（RNC-ESMP）通過建立節(jié)點能耗模型，結(jié)合自適應(yīng)反饋機制并采用合適的中間節(jié)點編碼策略，在保證數(shù)據(jù)傳輸可靠性的同時能有效地降低網(wǎng)絡(luò)平均能耗，延長網(wǎng)絡(luò)生命周期，大大提升了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］李姍姍，廖湘克，朱培棟.基于網(wǎng)絡(luò)編碼的無線傳感器網(wǎng)絡(luò)多路徑傳輸方法［J］.軟件學(xué)報，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)江人，博士，教授。研究方向：電子商務(wù)、信息安全。