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

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

?

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

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

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

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)大多采用電池供電，讓節(jié)點(diǎn)以低能耗將采集的數(shù)據(jù)傳遞到信宿，對(duì)無(wú)線傳感器網(wǎng)絡(luò)有效運(yùn)行極為重要.該文提出了能量有效的可靠機(jī)會(huì)路由EROR(Energy-efficient Reliable Opportunistic Routing)，它利用結(jié)合節(jié)點(diǎn)剩余能量和鏈路上收發(fā)雙方的總能耗的轉(zhuǎn)發(fā)代價(jià)，選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)集合(簡(jiǎn)稱(chēng)“轉(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ò)生存時(shí)間和能耗方面，EROR比已有路由策略CodePower更優(yōu).

無(wú)線傳感器網(wǎng)絡(luò);機(jī)會(huì)路由;節(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).頻繁的重傳會(huì)導(dǎo)致節(jié)點(diǎn)過(guò)多消耗能量.而且，節(jié)點(diǎn)重傳需要競(jìng)爭(zhēng)信道，從而導(dǎo)致帶寬利用率不高[1,2].

無(wú)線信道的廣播特性可以在某一程度上克服上述不足.當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)，其鄰居節(jié)點(diǎn)可以監(jiān)聽(tīng)到該數(shù)據(jù)包.機(jī)會(huì)路由[3]利用了無(wú)線信道的這一廣播特性，它需要在正確接收數(shù)據(jù)包的節(jié)點(diǎn)中選擇到目地節(jié)點(diǎn)的一個(gè)節(jié)點(diǎn)來(lái)轉(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ù)包的條件下，需要重傳.由于無(wú)線鏈路的廣播特性，在節(jié)點(diǎn)S向節(jié)點(diǎn)1發(fā)送數(shù)據(jù)包時(shí)，節(jié)點(diǎn)2和3分別以0.7和0.5的概率監(jiān)聽(tīng)數(shù)據(jù)包.也就是說(shuō)，在節(jié)點(diǎn)1收到數(shù)據(jù)包的同時(shí)，節(jié)點(diǎn)2和(或)節(jié)點(diǎn)3可能均收到該數(shù)據(jù)包.傳統(tǒng)路由忽視了這一現(xiàn)象，只是簡(jiǎ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ī)會(huì)路由并非這樣做，而是直接讓節(jié)點(diǎn)3把數(shù)據(jù)包發(fā)送給其下游節(jié)點(diǎn)甚至于目的節(jié)點(diǎn)D.由這個(gè)例子可見(jiàn)，機(jī)會(huì)路由可以減小數(shù)據(jù)包的傳遞次數(shù).

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

(3)若f?Fu∪Fs，則不偵聽(tīng)也不轉(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ā)送編碼包.

上述過(guò)程逐步推進(jìn)，直到Sink收到m個(gè)線性無(wú)關(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à)

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

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

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

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

(1)

我們?nèi)?/p>

(2)

接下來(lái)，我們確定式(2)右邊兩個(gè)代價(jià)的表達(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(shuí)比特?cái)?shù)據(jù)消耗的能量Erx(l)可以表示為[13]：

(3)

(4)

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

我們考慮瑞利衰落無(wú)線信道，節(jié)點(diǎn)u以功率ε發(fā)送信號(hào)給節(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)及對(duì)應(yīng)概率

(9)

上式中，右邊分式是在集合F中至少有一個(gè)節(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ā)代價(jià)的算法及其復(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ā)送的編碼包的最大個(gè)數(shù).假設(shè)節(jié)點(diǎn)f為主轉(zhuǎn)發(fā)節(jié)點(diǎn)u的一個(gè)協(xié)助轉(zhuǎn)發(fā)節(jié)點(diǎn).我們引入符號(hào)

(10)

(11)

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

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

轉(zhuǎn)發(fā)集合中的節(jié)點(diǎn)在偵聽(tīng)數(shù)據(jù)時(shí)，可能在同一時(shí)刻有多個(gè)節(jié)點(diǎn)緩存的編碼包個(gè)數(shù)同達(dá)到m.這時(shí)，如果這些節(jié)點(diǎn)同時(shí)發(fā)送確認(rèn)包，可能會(huì)導(dǎo)致確認(rèn)包的碰撞，也可能產(chǎn)生多個(gè)主轉(zhuǎn)發(fā)節(jié)點(diǎn).為了避免這種情況發(fā)生，在節(jié)點(diǎn)f收齊m個(gè)編碼包時(shí)，我們讓節(jié)點(diǎn)延緩Tf符號(hào)周期(Symbol Period)發(fā)送確認(rèn)包，而且，在延緩的Tf符號(hào)周期內(nèi)，若該節(jié)點(diǎn)監(jiān)聽(tīng)到其它節(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)包的延遲時(shí)間在[12,32]這個(gè)區(qū)間內(nèi)，我們定義：

(12)

4 仿真分析

由于節(jié)點(diǎn)可以調(diào)整發(fā)射功率，因此若節(jié)點(diǎn)增大發(fā)送功率，那么可能有更多節(jié)點(diǎn)能夠收到數(shù)據(jù)包，這樣節(jié)點(diǎn)的鄰居會(huì)隨功率增大而增多.在仿真中，我們使用與文獻(xiàn)[13]類(lèi)似的方法確定式(6)中的g1/εN：我們?nèi)1/εN的值滿足節(jié)點(diǎn)u以最大功率發(fā)送長(zhǎng)度為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)活躍時(shí)總功率為41mW.因此，我們?nèi)∈?4)中B=38mW，發(fā)送功率E中最大值為35mW，式(3)中A=5mW.其它仿真參數(shù)如表2所示.我們采用C++程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)仿真程序.

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

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

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

5 總結(jié)

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

[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ú)線傳感器網(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ú)線網(wǎng)絡(luò)編碼增益感知的低時(shí)延路由協(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).移動(dòng)自組網(wǎng)中基于部分網(wǎng)絡(luò)編碼的機(jī)會(huì)主義路由[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ú)線網(wǎng)狀網(wǎng)中的機(jī)會(huì)路由算法[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ú)線傳感器網(wǎng)絡(luò).

朱藝華(通信作者) 男，1961年生于浙江玉環(huán)，博士，教授，研究方向?yàn)闊o(wú)線網(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é)任編輯：諸葉梅

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(No.61432015);國(guó)家自然科學(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