無線傳感器網(wǎng)絡(luò)中利用隨機(jī)網(wǎng)絡(luò)編碼的低能耗可靠機(jī)會

徐 驥,朱藝華,田賢忠,池凱凱

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江杭州 310023)

?

無線傳感器網(wǎng)絡(luò)中利用隨機(jī)網(wǎng)絡(luò)編碼的低能耗可靠機(jī)會

徐 驥,朱藝華,田賢忠,池凱凱

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江杭州 310023)

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)大多采用電池供電，讓節(jié)點(diǎn)以低能耗將采集的數(shù)據(jù)傳遞到信宿，對無線傳感器網(wǎng)絡(luò)有效運(yùn)行極為重要.該文提出了能量有效的可靠機(jī)會路由EROR(Energy-efficient Reliable Opportunistic Routing)，它利用結(jié)合節(jié)點(diǎn)剩余能量和鏈路上收發(fā)雙方的總能耗的轉(zhuǎn)發(fā)代價，選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(簡稱“轉(zhuǎn)發(fā)集”)、主轉(zhuǎn)發(fā)節(jié)點(diǎn)和協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)，讓節(jié)點(diǎn)調(diào)節(jié)發(fā)射功率并利用隨機(jī)線性編碼把數(shù)據(jù)包分片編碼發(fā)送到轉(zhuǎn)發(fā)集，進(jìn)而以多跳方式把數(shù)據(jù)可靠低能耗地傳遞到信宿.仿真結(jié)果表明：在網(wǎng)絡(luò)生存時間和能耗方面，EROR比已有路由策略CodePower更優(yōu).

無線傳感器網(wǎng)絡(luò);機(jī)會路由;節(jié)能;功率控制;網(wǎng)絡(luò)編碼

1 引言

傳統(tǒng)的路由協(xié)議需要節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前建立一條或多條端到端的數(shù)據(jù)傳輸路徑，以將數(shù)據(jù)逐跳發(fā)送到目的節(jié)點(diǎn).為了提高可靠性，路徑上節(jié)點(diǎn)通常采用重傳和確認(rèn)機(jī)制傳遞數(shù)據(jù).在通信鏈路質(zhì)量比較差的情況下，節(jié)點(diǎn)需要重傳多次才能將數(shù)據(jù)包發(fā)送給下一跳節(jié)點(diǎn).頻繁的重傳會導(dǎo)致節(jié)點(diǎn)過多消耗能量.而且，節(jié)點(diǎn)重傳需要競爭信道，從而導(dǎo)致帶寬利用率不高[1,2].

無線信道的廣播特性可以在某一程度上克服上述不足.當(dāng)一個節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時，其鄰居節(jié)點(diǎn)可以監(jiān)聽到該數(shù)據(jù)包.機(jī)會路由[3]利用了無線信道的這一廣播特性，它需要在正確接收數(shù)據(jù)包的節(jié)點(diǎn)中選擇到目地節(jié)點(diǎn)的一個節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)包，從而提高轉(zhuǎn)發(fā)數(shù)據(jù)包的可靠性以提高吞吐率.如圖1，設(shè)源節(jié)點(diǎn)S到目地節(jié)點(diǎn)D存在一條路徑S→1→2→3→4→D，其中，S到節(jié)點(diǎn)1，2，3的數(shù)據(jù)包傳輸成功率分別為0.9，0.7，0.5，且節(jié)點(diǎn)2和3到D的數(shù)據(jù)包傳輸成功率分別為0.6和0.85.按照傳統(tǒng)路由，節(jié)點(diǎn)S將數(shù)據(jù)包發(fā)送到節(jié)點(diǎn)1，且在節(jié)點(diǎn)1未能成功收到數(shù)據(jù)包的條件下，需要重傳.由于無線鏈路的廣播特性，在節(jié)點(diǎn)S向節(jié)點(diǎn)1發(fā)送數(shù)據(jù)包時，節(jié)點(diǎn)2和3分別以0.7和0.5的概率監(jiān)聽數(shù)據(jù)包.也就是說，在節(jié)點(diǎn)1收到數(shù)據(jù)包的同時，節(jié)點(diǎn)2和(或)節(jié)點(diǎn)3可能均收到該數(shù)據(jù)包.傳統(tǒng)路由忽視了這一現(xiàn)象，只是簡單地逐跳轉(zhuǎn)發(fā)：把數(shù)據(jù)包從節(jié)點(diǎn)1轉(zhuǎn)發(fā)到節(jié)點(diǎn)2，再轉(zhuǎn)發(fā)到節(jié)點(diǎn)3，最終到達(dá)目的節(jié)點(diǎn)D.但機(jī)會路由并非這樣做，而是直接讓節(jié)點(diǎn)3把數(shù)據(jù)包發(fā)送給其下游節(jié)點(diǎn)甚至于目的節(jié)點(diǎn)D.由這個例子可見，機(jī)會路由可以減小數(shù)據(jù)包的傳遞次數(shù).

在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)通常由能量有限的電池供電，因此，機(jī)會路由需要考慮節(jié)點(diǎn)的能耗.若節(jié)點(diǎn)選擇較大的發(fā)生功率，那么數(shù)據(jù)包能夠被更遠(yuǎn)更多的節(jié)點(diǎn)監(jiān)聽到，但會增加網(wǎng)絡(luò)的能耗開銷；若減少發(fā)送的功率，鏈路質(zhì)量越差，數(shù)據(jù)包可能要經(jīng)過更多節(jié)點(diǎn)轉(zhuǎn)發(fā)才能到達(dá)Sink，可靠性降低.因此在無線傳感器網(wǎng)絡(luò)中，我們需要設(shè)計(jì)一個能量高效的可靠機(jī)會路由，此乃本文的研究動機(jī).本文的貢獻(xiàn)如下：

(1)給出了結(jié)合節(jié)點(diǎn)剩余能量和收發(fā)雙方能耗的數(shù)據(jù)包轉(zhuǎn)發(fā)代價計(jì)算公式，設(shè)計(jì)了能夠讓節(jié)點(diǎn)在數(shù)據(jù)傳輸過程中動態(tài)地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(下稱“轉(zhuǎn)發(fā)集”)、發(fā)送功率和轉(zhuǎn)發(fā)代價的算法.

(2)提出了基于編碼的低能耗機(jī)會路由策略EROR(Energy-efficient Reliable Opportunistic Routing).EROR利用隨機(jī)線性編碼，讓節(jié)點(diǎn)將編碼包發(fā)送到下游節(jié)點(diǎn)，以提高傳輸可靠性.在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，EROR可以讓節(jié)點(diǎn)根據(jù)轉(zhuǎn)發(fā)代價在轉(zhuǎn)發(fā)集中動態(tài)選擇一個主轉(zhuǎn)發(fā)節(jié)點(diǎn)，使數(shù)據(jù)傳遞到Sink節(jié)點(diǎn).此外，EROR允許主轉(zhuǎn)發(fā)節(jié)點(diǎn)選取若干協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)，并且每個協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)可以根據(jù)其所在轉(zhuǎn)發(fā)集的代價、鏈路質(zhì)量和緩存的編碼包個數(shù)來確定自己需要發(fā)送的最大編碼包個數(shù)，以降低和平衡各轉(zhuǎn)發(fā)節(jié)點(diǎn)的消耗，從而延長網(wǎng)絡(luò)的生存時間.

2 相關(guān)工作

目前，已經(jīng)有一些機(jī)會路由在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時考慮了能耗問題，但這些研究還存在不足.在文獻(xiàn)[4]中作者提出的EEOR每個節(jié)點(diǎn)可在調(diào)發(fā)送能量和不可調(diào)發(fā)送能量模型下計(jì)算路由代價和選擇最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)集合，從而使得數(shù)據(jù)通過這些節(jié)點(diǎn)轉(zhuǎn)發(fā)到Sink時總能耗最小.EEOR中節(jié)點(diǎn)根據(jù)優(yōu)先級轉(zhuǎn)發(fā)數(shù)據(jù)，若高優(yōu)先級的轉(zhuǎn)發(fā)了數(shù)據(jù)，那么低優(yōu)先級的節(jié)點(diǎn)需要丟棄監(jiān)聽到的數(shù)據(jù)包，造成節(jié)點(diǎn)能量的浪費(fèi).AsOR[5]設(shè)計(jì)了分段路由的方法，通過選擇最優(yōu)的段內(nèi)節(jié)點(diǎn)個數(shù)使得平均能耗最小化，但AsOR是從全局角度優(yōu)化能耗，是集中式的路由算.一些研究將網(wǎng)絡(luò)編碼用于路由，如基于網(wǎng)絡(luò)編碼的無重傳路由[6]和編碼增益感知的路由[7].MORE[8]將機(jī)會路由和流內(nèi)隨機(jī)線性編碼相結(jié)合，解決了節(jié)點(diǎn)轉(zhuǎn)發(fā)調(diào)度困難的問題.CodeOR[9]用滑動窗口提高M(jìn)ORE數(shù)據(jù)傳輸?shù)男?，但CodeOR沒有考慮能耗.CodePower[10]通過分布式算法選擇了最優(yōu)的發(fā)送功率和對應(yīng)的最優(yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)，將結(jié)合流內(nèi)隨機(jī)線性編碼的機(jī)會路由用于無線傳感器網(wǎng)絡(luò)，但CodePower不能保證數(shù)據(jù)可靠傳遞，節(jié)點(diǎn)只轉(zhuǎn)發(fā)確定數(shù)量的編碼包，不能保證數(shù)據(jù)可靠傳遞.本文提出的EROR通過選擇主轉(zhuǎn)發(fā)節(jié)點(diǎn)和協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)來解決了上述能量浪費(fèi)和可靠性問題.文獻(xiàn)[11]提出基于部分網(wǎng)絡(luò)編碼的機(jī)會路由.文獻(xiàn)[12]提出分布式聯(lián)合候選節(jié)點(diǎn)選擇和速率分配的多流機(jī)會路由算法.文獻(xiàn)[13]結(jié)合端到端的可靠性與能耗，針對自組織網(wǎng)絡(luò)，提出兩個路由策略：RMECR(Reliable Minimum Energy Cost Routing)和RMER(Reliable Minimum Energy Routing).前者的鏈路權(quán)重考慮了鏈路兩端節(jié)點(diǎn)的收發(fā)能耗和剩余能量，后者的鏈路權(quán)重僅考慮鏈路兩端節(jié)點(diǎn)的收發(fā)能耗；兩者均利用Dijkstra算法找到能耗最小的路徑.文獻(xiàn)[13]的作者指出：上述兩種路由需要網(wǎng)絡(luò)中每個節(jié)點(diǎn)知道整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，可以采用諸如洪泛(flooding)等方法獲得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息；兩者在采用Dijkstra方法求最小能耗時，均需要采用集中計(jì)算.事實(shí)上，文獻(xiàn)[13]提出的RMECR和RMER路由均不適用無線傳感器網(wǎng)絡(luò)，其理由如下所述:(1)當(dāng)代無線傳感器網(wǎng)絡(luò)大多基于IEEE 802.15.4標(biāo)準(zhǔn)，節(jié)點(diǎn)的處理能力、無線電覆蓋范圍、可以通信的數(shù)據(jù)包長度、內(nèi)存空間等均為捉襟見肘.IEEE 802.15.4標(biāo)準(zhǔn)針對低數(shù)據(jù)率、低功耗的無線個域網(wǎng)絡(luò)，其物理層可以攜帶的來自數(shù)據(jù)鏈路層數(shù)據(jù)幀的最大長度只有127字節(jié)[14].目前，CrossBow公司生產(chǎn)的TelosB傳感器節(jié)點(diǎn)，其射頻收發(fā)器兼容IEEE 802.15.4標(biāo)準(zhǔn)，通信距離僅為數(shù)十米，而且只有10kB內(nèi)存；(2)在低功耗的無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的鏈路時斷時續(xù)，這會導(dǎo)致采用集中方式計(jì)算出來的最優(yōu)路徑在傳遞數(shù)據(jù)包時可能因某個鏈路中斷而失效，而且存在最優(yōu)路徑未使用就失效的可能，這是因?yàn)樽顑?yōu)路徑在計(jì)算出來之后，計(jì)算路徑的節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包通知各相關(guān)節(jié)點(diǎn)，而且包含該通知的數(shù)據(jù)包在發(fā)送過程中可能丟失.本文提出的EROR路由方案，可以克服上述缺陷.本文的EROR的主要異同之處在于：EROR采用分布式算法，節(jié)點(diǎn)在選路時只需獲取鄰居的狀態(tài)信息，無須知道整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，也不需要計(jì)算從信源到信宿的路徑.而且，EROR適用于資源極度受限的、鏈路時斷時續(xù)的、基于IEEE 802.15.4標(biāo)準(zhǔn)的無線傳感器網(wǎng)絡(luò).

3 基于編碼的低能耗可靠機(jī)會路由

3.1 EROR的轉(zhuǎn)發(fā)策略

與MORE[8]類似，本文提出的EROR協(xié)議利用流內(nèi)隨機(jī)線性網(wǎng)絡(luò)編碼來傳遞數(shù)據(jù)，關(guān)鍵在于：利用轉(zhuǎn)發(fā)代價確定轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(簡稱“轉(zhuǎn)發(fā)集”).我們將在下一節(jié)給出轉(zhuǎn)發(fā)代價的定義.

轉(zhuǎn)發(fā)集Fs中的節(jié)點(diǎn)，每偵聽到一個來自節(jié)點(diǎn)s的編碼包，就檢查收到的編碼包與緩存的編碼包是否線性無關(guān).若是，則放入緩存，否則，棄之.當(dāng)一個節(jié)點(diǎn)緩存的編碼包的個數(shù)達(dá)到m時，該節(jié)點(diǎn)就向節(jié)點(diǎn)s回復(fù)一個ACK，使節(jié)點(diǎn)s停止生成和發(fā)送編碼包.

我們稱轉(zhuǎn)發(fā)集中第一個收足m個編碼包的節(jié)點(diǎn)為“主轉(zhuǎn)發(fā)節(jié)點(diǎn)”.設(shè)節(jié)點(diǎn)u是Fs的主轉(zhuǎn)發(fā)節(jié)點(diǎn).由于節(jié)點(diǎn)u的m個編碼包系數(shù)形成一個滿秩矩陣，它可以通過解碼得到節(jié)點(diǎn)s發(fā)送的原始數(shù)據(jù).此時，F(xiàn)s中其余節(jié)點(diǎn)收到的編碼包個數(shù)不足m，雖然這些節(jié)點(diǎn)不能通過解碼獲得原始數(shù)據(jù)，但其收到的編碼包或許對下游節(jié)點(diǎn)的解碼有用.因此，下述方案可以在Fs中篩選一些節(jié)點(diǎn)(稱為“協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)”)讓其轉(zhuǎn)發(fā)所收到的編碼包給下游節(jié)點(diǎn).

(1)若f∈Fu，則f偵聽Fs中的節(jié)點(diǎn)廣播的編碼包；

(3)若f?Fu∪Fs，則不偵聽也不轉(zhuǎn)發(fā)數(shù)據(jù).

主轉(zhuǎn)發(fā)節(jié)點(diǎn)u和協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)將各自緩存的編碼包進(jìn)行隨機(jī)編碼不斷產(chǎn)生新的編碼包，再把編碼包廣播給Fu內(nèi)的下游節(jié)點(diǎn)，直到收到Fu內(nèi)主轉(zhuǎn)發(fā)節(jié)點(diǎn)的ACK為止.在圖2中，v是Fu的主轉(zhuǎn)發(fā)節(jié)點(diǎn).節(jié)點(diǎn)v采用廣播的形式發(fā)送ACK，使得Fs中節(jié)點(diǎn)收到確認(rèn)后就停止發(fā)送編碼包.

上述過程逐步推進(jìn)，直到Sink收到m個線性無關(guān)的編碼包，進(jìn)而解出源數(shù)據(jù).之后，Sink發(fā)送ACK給其上游轉(zhuǎn)發(fā)節(jié)點(diǎn)，使其停止發(fā)送編碼包.

3.2 EROR的數(shù)據(jù)轉(zhuǎn)發(fā)代價

由上節(jié)可知，EROR協(xié)議是根據(jù)轉(zhuǎn)發(fā)代價選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的.因此，在設(shè)計(jì)轉(zhuǎn)發(fā)代價時，需要考慮以下因素：

(1)轉(zhuǎn)發(fā)代價應(yīng)能夠根據(jù)節(jié)點(diǎn)的能量狀態(tài)和鏈路質(zhì)量狀態(tài)來影響數(shù)據(jù)的轉(zhuǎn)發(fā)路徑.

(2)由于節(jié)點(diǎn)的發(fā)射功率影響著節(jié)點(diǎn)的鄰居集合，高發(fā)射功率使節(jié)點(diǎn)的鄰居多，但耗能大，因此，轉(zhuǎn)發(fā)代價需要反映節(jié)點(diǎn)的發(fā)射功率.

(3)為了使網(wǎng)絡(luò)有更長的工作時間，轉(zhuǎn)發(fā)代價應(yīng)該分擔(dān)給剩余能量小的節(jié)點(diǎn)更小的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù).

(1)

我們?nèi)?/p>

(2)

接下來，我們確定式(2)右邊兩個代價的表達(dá)式.本文采用文獻(xiàn)[13]的能耗模型.用A表示節(jié)點(diǎn)計(jì)算和處理調(diào)制數(shù)據(jù)的平均功率，用B表示接收方接收數(shù)據(jù)的平均功率.于是，在功率ε下發(fā)送l比特?cái)?shù)據(jù)消耗的能量Etx(l,ε)和接收l比特?cái)?shù)據(jù)消耗的能量Erx(l)可以表示為[13]：

(3)

(4)

其中0<β<1是放大器的效率，R是物理層的速率(單位：bps).

我們考慮瑞利衰落無線信道，節(jié)點(diǎn)u以功率ε發(fā)送信號給節(jié)點(diǎn)v的誤碼概率為[13]

(5)

(6)

式中，g1是與傳輸和接收天線有關(guān)的常數(shù)，εN是噪聲和干擾的功率，η為路徑衰減指數(shù)，du,v為節(jié)點(diǎn)u和v之間的距離.因而，

(7)

(8)

其中，REu和REv分別為節(jié)點(diǎn)u和v的剩余能量.

表1 集合F的主轉(zhuǎn)發(fā)節(jié)點(diǎn)及對應(yīng)概率

(9)

上式中，右邊分式是在集合F中至少有一個節(jié)點(diǎn)接收到節(jié)點(diǎn)u所廣播的數(shù)據(jù)包這一條件下，節(jié)點(diǎn)fi成為主轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率.

3.3 確定轉(zhuǎn)發(fā)集、發(fā)射功率和轉(zhuǎn)發(fā)代價的算法及其復(fù)雜度

3.4 轉(zhuǎn)發(fā)數(shù)據(jù)量的確定

考慮到協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)需要協(xié)助主轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送編碼包給下游轉(zhuǎn)發(fā)集，為了節(jié)省能量，我們需要限制協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送的編碼包的最大個數(shù).假設(shè)節(jié)點(diǎn)f為主轉(zhuǎn)發(fā)節(jié)點(diǎn)u的一個協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn).我們引入符號

(10)

(11)

其中Γf是節(jié)點(diǎn)f緩存的編碼包的個數(shù).每個協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)一旦發(fā)送的數(shù)據(jù)包個數(shù)達(dá)到Af或者收到確認(rèn)包時，就停止發(fā)送.

3.5 主轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇

轉(zhuǎn)發(fā)集合中的節(jié)點(diǎn)在偵聽數(shù)據(jù)時，可能在同一時刻有多個節(jié)點(diǎn)緩存的編碼包個數(shù)同達(dá)到m.這時，如果這些節(jié)點(diǎn)同時發(fā)送確認(rèn)包，可能會導(dǎo)致確認(rèn)包的碰撞，也可能產(chǎn)生多個主轉(zhuǎn)發(fā)節(jié)點(diǎn).為了避免這種情況發(fā)生，在節(jié)點(diǎn)f收齊m個編碼包時，我們讓節(jié)點(diǎn)延緩Tf符號周期(Symbol Period)發(fā)送確認(rèn)包，而且，在延緩的Tf符號周期內(nèi)，若該節(jié)點(diǎn)監(jiān)聽到其它節(jié)點(diǎn)已經(jīng)發(fā)送了確認(rèn)包，則它取消發(fā)送確認(rèn)包(即放棄成為主轉(zhuǎn)發(fā)節(jié)點(diǎn)).考慮到IEEE 802.15.4標(biāo)準(zhǔn)要求發(fā)送確認(rèn)包的延遲時間在[12,32]這個區(qū)間內(nèi)，我們定義：

(12)

4 仿真分析

由于節(jié)點(diǎn)可以調(diào)整發(fā)射功率，因此若節(jié)點(diǎn)增大發(fā)送功率，那么可能有更多節(jié)點(diǎn)能夠收到數(shù)據(jù)包，這樣節(jié)點(diǎn)的鄰居會隨功率增大而增多.在仿真中，我們使用與文獻(xiàn)[13]類似的方法確定式(6)中的g1/εN：我們?nèi)1/εN的值滿足節(jié)點(diǎn)u以最大功率發(fā)送長度為800比特的數(shù)據(jù)包給相距50米遠(yuǎn)的節(jié)點(diǎn)v收到的概率為0.5.利用文獻(xiàn)[13]的方法，可得：g1/εN=2058314.我們參考Telos節(jié)點(diǎn)的參數(shù)[16]：接收功率為38mW，發(fā)送功率為35mW，節(jié)點(diǎn)活躍時總功率為41mW.因此，我們?nèi)∈?4)中B=38mW，發(fā)送功率E中最大值為35mW，式(3)中A=5mW.其它仿真參數(shù)如表2所示.我們采用C++程序設(shè)計(jì)語言設(shè)計(jì)仿真程序.

表2 其它仿真參數(shù)

考慮到RMECR和RMER[13]不適合于無線傳感器網(wǎng)絡(luò)(見第2節(jié))，而CodePower與EROR均屬于機(jī)會路由，采用類似的機(jī)制，我們對EROR和CodePower的性能進(jìn)行對比.由于EROR保證每跳可靠傳輸，源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包都到達(dá)sink節(jié)點(diǎn)，因此，以下僅對兩者的網(wǎng)絡(luò)生存時間和能耗進(jìn)行對比.網(wǎng)絡(luò)生存時間定義為從發(fā)送第一個數(shù)據(jù)包開始到出現(xiàn)第一個剩余能量為0的節(jié)點(diǎn)為止這段時間，并且采用源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包個數(shù)進(jìn)行度量.平均能耗定義為網(wǎng)絡(luò)生存時間內(nèi)平均每個到達(dá)Sink的數(shù)據(jù)包消耗的能量.仿真區(qū)域大小為1000×1000m2，Sink節(jié)點(diǎn)位于區(qū)域左下角，在區(qū)域中隨機(jī)產(chǎn)生節(jié)點(diǎn).Sink的代價為0，其余節(jié)點(diǎn)初始代價取為無窮大.我們假設(shè)Sink節(jié)點(diǎn)能耗不受限制并且有足夠的計(jì)算能力，因而忽略Sink的接收能耗.圖3和圖4是不同網(wǎng)絡(luò)規(guī)模下1000次仿真運(yùn)行的平均結(jié)果.由圖3可見：本文提出的EROR的生存時間大于CodePower.這是因?yàn)镋ROR在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)時，考慮了節(jié)點(diǎn)的剩余能量.剩余能量少的節(jié)點(diǎn)代價比較大，EROR避免將這些節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，而是選擇其它能量比較充足的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包.然而，CodePower在計(jì)算代價時未能考慮節(jié)點(diǎn)的剩余能量，導(dǎo)致能耗不均.從圖3(a)可以看出：兩者的生存時間都隨著網(wǎng)絡(luò)規(guī)模的增大呈先增大后減小的趨勢.這是因?yàn)榫W(wǎng)絡(luò)中節(jié)點(diǎn)密度增大，每個節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個數(shù)隨著增加，使得一個節(jié)點(diǎn)有更多機(jī)會從鄰居中選擇代價更小的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，從而使得生存時間增大.但當(dāng)節(jié)點(diǎn)個數(shù)進(jìn)一步增大時，主轉(zhuǎn)發(fā)節(jié)點(diǎn)的轉(zhuǎn)發(fā)集也隨著增大，即參與轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)個數(shù)增大，相互轉(zhuǎn)發(fā)的數(shù)據(jù)包增多，從而引起生存時間減小.從圖3(b)可以看出，網(wǎng)絡(luò)生存時間都隨分片增多而減小，這是因?yàn)榉制瑪?shù)越多，節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包個數(shù)就越多，耗能越大.

由圖4可見：EROR的平均能耗低于CodePower，且兩者的能耗均隨著節(jié)點(diǎn)數(shù)和分片數(shù)的增大而增大.但隨著節(jié)點(diǎn)數(shù)的增大，EROR的能耗比CodePower增大緩慢(見圖4(a)).這是因?yàn)镋ROR的主轉(zhuǎn)發(fā)節(jié)點(diǎn)使得編碼包逐跳可靠傳輸，而且，它通過選擇適當(dāng)?shù)膮f(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)來協(xié)同主轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)部分編碼包.然而，CodePower采用端到端確認(rèn)以保證可靠傳輸.因此，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，CodePower的數(shù)據(jù)包可能因中途夭折而重傳，這時夭折的數(shù)據(jù)包可能走過了很多跳，從而導(dǎo)致平均能耗的上升.從圖4(b)可以看出，平均能耗都隨分片增多而增加，這與直觀是吻合的.

5 總結(jié)

本文提出了一種基于隨機(jī)線性編碼并且發(fā)送功率可調(diào)的低能耗機(jī)會路由EROR.這種路由策略利用隨機(jī)線性網(wǎng)絡(luò)編碼，并利用結(jié)合節(jié)點(diǎn)剩余能量和鏈路上收發(fā)雙方總能耗的轉(zhuǎn)發(fā)代價，選擇主轉(zhuǎn)發(fā)節(jié)點(diǎn)、協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn)和轉(zhuǎn)發(fā)集，使數(shù)據(jù)可靠地從信源傳遞到信宿，降低和均衡了節(jié)點(diǎn)的能耗，在保證可靠性的同時，延長了網(wǎng)絡(luò)生存時間.

[1]Poonguzharselvi B,Vetriselvi V.Survey on routing algorithms in opportunistic networks[A].Proceedings of the 2013 International Conference on Computer Communication and Informatics(ICCCI)[C].Coimbatore:IEEE,2013.1-5.

[2]Zhang Z,Krishnan R.An overview of opportunistic routing in mobile ad hoc networks[A].Proceedings of the 2013-2013 IEEE Military Communications Conference[C].San Diego:IEEE,2013.119-124.

[3]Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM SIGCOMM Computer Communication Review,2005,35(4):133-144.

[4]Mao Xufei,Tang Shaojie,Xu Xiahua,Li Xiangyang,Ma Huadong.Energy-efficient opportunistic routing in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(11):1934-1942.

[5]Wei Chen,Zhi Chen,Fan Pingyi,et al.AsOR:an energy efficient multi-hop opportunistic routing protocol for wireless sensor networks over Rayleigh fading channels[J].IEEE Transactions on Wireless Communications,2009,8(5):2452-2463.

[6]盧文偉，朱藝華，陳貴海.無線傳感器網(wǎng)絡(luò)中基于線性網(wǎng)絡(luò)編碼的節(jié)能路由算法[J].電子學(xué)報(bào)，2010,38(10):2309-2314.

Lu Wenwei,Zhu Yihua,Chen Guihai.Energy-efficient routing algorithms based on linear network coding in wireless sensor networks[J].Acta Electronica Sinaca,2010,38(10):2309-2314.(in Chinese)

[7]田賢忠，朱藝華，繆得志.無線網(wǎng)絡(luò)編碼增益感知的低時延路由協(xié)議[J].電子學(xué)報(bào)，2013，41(4):652-658.

Tian Xianzhong,Zhu Yihua,Miao Dezhi.Wireless network coding gain aware routing protocol with low delay[J].Acta Electronica Sinaca,2013,41(4):652-658.(in Chinese)

[8]Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing[J].ACM SIGCOMM Computer Communication Review,2007,37(4):169-180.

[9]Lin Y,Li B,Liang B.CodOR:opportunistic routing in wireless mesh networks with segmented network coding[A].Proceedings of the 2008 IEEE International Conference on Network Protocols(ICNP 2008)[C].Orlando:IEEE,2008.13-22.

[10]Tong J,Qian D,Du Z,et al.Energy-efficient coded routing with selective transmission power for wireless sensor networks[A].Proceedings of the 2010 IEEE 72nd Vehicular Technology Conference Fall(VTC 2010-Fall)[C].Ottawa:IEEE,2010.1-5.

[11]王曉東，霍廣城，孫海燕，孟祥旭，孫言強(qiáng).移動自組網(wǎng)中基于部分網(wǎng)絡(luò)編碼的機(jī)會主義路由[J].電子學(xué)報(bào)，2010,38(8):1736-1740.

Wang Xiaodong,Huo Guangcheng,Sun Haiyan,Meng Xiangxu,Sun Yangqiang.An opportunistic routing for MANET based on partial network coding[J].Acta Electronica Sinaca,2010,38(8):1736-1740.(in Chinese)

[12]何施茗，張大方，謝鯤，張繼，喬宏.多并發(fā)流無線網(wǎng)狀網(wǎng)中的機(jī)會路由算法[J].電子學(xué)報(bào)，2014,42(5):1004-1008.

He Shiming,Zhang Dafang,Xie Kun,Zhang Ji,Qiao Hong.Opportunistic routing for multi-flow in wireless mesh networks[J].Acta Electronica Sinaca,2014,42(5):1004-1008.(in Chinese)

[13]Vazifehdan J,Prasad R V,Niemegeers I.Energy-efficient reliable routing considering residual energy in wireless ad hoc networks[J].IEEE Transactions on Mobile Computing,2013,13(2):434-447.

[14]IEEE Computer Society.IEEE 802.15.4 Standard for Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specifications for Low-Rate Wireless Personal Area Networks(WPANs)[S].2011.

[15]Ho T,M′edard M,Koetter R,Karger D,Effros M,Shi J,Leong B.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[16]Polastre J,Szewczyk R,Culler D.Telos:enabling ultra-low power wireless research[A].Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks[C].IEEE,2005.364-369.

徐 驥 男，1990年生于浙江紹興.碩士研究生,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò).

朱藝華(通信作者) 男，1961年生于浙江玉環(huán)，博士，教授，研究方向?yàn)闊o線網(wǎng)絡(luò)、物聯(lián)網(wǎng)、網(wǎng)絡(luò)編碼等.

E-mailyhzhu@zjut.edu.cn

Energy-Efficient Reliable Opportunistic Routing Applying Random Network Coding for Wireless Sensor Network

XU Ji,ZHU Yi-hua,TIAN Xian-zhong,CHI Kai-kai

(SchoolofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou，Zhejiang310023,China)

The nodes in Wireless Sensor Networks(WSNs)are usually powered by battery.It is extremely important to let the nodes deliver data to the destination in an energy-efficient manner such that the WSNs have longer runtime.In this paper,the Energy-efficient Reliable Opportunistic Routing(EROR)is presented.The EROR uses the forwarding cost,which takes into account node’s residual energy and the total energy consumption expended by the nodes over a wireless link;chooses the forwarding set consisting of forwarding nodes(FNs),the main FN,and the assistant FNs;and allows a node to change its transmission power to transmit the encoded packets,which are generated by randomly linear network coding,to the forwarding set such that the data are delivered to the destination in a multi-hop,reliable,and energy-efficient way.Simulation results indicate that the EROR outperforms the existing CodePower routing in terms of network lifetime and energy consumption.

wireless sensor network;opportunistic routing;energy conservation;transmit power control;network coding

2015-02-08;

2015-04-08；責(zé)任編輯：諸葉梅

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(No.61432015);國家自然科學(xué)基金(No.61472367，No.61379124)

TP393

A

0372-2112 (2016)08-1799-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.08.004