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

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

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

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

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

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

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

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

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

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

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

1　能量效益

1.1能量消耗特征

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

圖1　無(wú)線傳感器節(jié)點(diǎn)能耗分布

從圖1可以看出，節(jié)點(diǎn)絕大部分能量消耗在無(wú)線通信模塊上。該模塊有四種狀態(tài)，在空閑狀態(tài)時(shí)一直監(jiān)聽(tīng)無(wú)線信道的使用情況，檢查是否有數(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é)點(diǎn)總能耗：

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

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

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

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

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

2　路徑選擇概率

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

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

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

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

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

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

3　解碼反饋

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

圖2　解碼反饋算法流程圖

4　編碼策略

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

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

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

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

同理針對(duì)信宿節(jié)點(diǎn)R2，則收到下面兩個(gè)方程

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

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

4.2節(jié)點(diǎn)編碼方案

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

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

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

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

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

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

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

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

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

5　性能仿真與分析

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

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

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

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

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

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

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

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

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

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

6　結(jié)　論

與傳統(tǒng)的多路徑算法（TD-MR）和基于網(wǎng)絡(luò)編碼的多路徑算法 （NC-MR）相比，本文提出的基于隨機(jī)網(wǎng)絡(luò)編碼的WSN多徑傳輸自適應(yīng)節(jié)能算法（RNC-ESMP）通過(guò)建立節(jié)點(diǎn)能耗模型，結(jié)合自適應(yīng)反饋機(jī)制并采用合適的中間節(jié)點(diǎn)編碼策略，在保證數(shù)據(jù)傳輸可靠性的同時(shí)能有效地降低網(wǎng)絡(luò)平均能耗，延長(zhǎng)網(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］李?yuàn)檴?，廖湘克，朱培?基于網(wǎng)絡(luò)編碼的無(wú)線傳感器網(wǎng)絡(luò)多路徑傳輸方法［J］.軟件學(xué)報(bào)，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稿件編號(hào)：201505243

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