袁利永， 林飛龍， 王 暉, 曾令國

(1.浙江師范大學(xué) 行知學(xué)院,浙江 金華 321004；2.浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSN)由許多傳感器節(jié)點(diǎn)組成，用于收集數(shù)據(jù)，已經(jīng)在諸多領(lǐng)域得到了廣泛應(yīng)用.在傳統(tǒng)的WSN中，節(jié)點(diǎn)一般采用能量有限的電池供電，其工作時(shí)間和數(shù)據(jù)速率都受到節(jié)點(diǎn)電池能量的制約，這給WSN應(yīng)用于數(shù)據(jù)速率較高的領(lǐng)域帶來許多困難.最近，能量捕獲無線傳感器網(wǎng)絡(luò)(EH-WSN)受到了越來越多的關(guān)注.EH-WSN中的節(jié)點(diǎn)裝備了能量捕獲模塊和可充電電池，能夠從環(huán)境中獲取能量，使得傳感器節(jié)點(diǎn)可以免受電池能量的制約，大幅度延長節(jié)點(diǎn)及其網(wǎng)絡(luò)的工作時(shí)間.在一些EH-WSN應(yīng)用中(如環(huán)境、建筑等監(jiān)測應(yīng)用)，所有節(jié)點(diǎn)都被要求以相同的收集速率向sink節(jié)點(diǎn)匯報(bào)感知數(shù)據(jù)[1].把網(wǎng)絡(luò)中所有節(jié)點(diǎn)能夠共同支持的最大數(shù)據(jù)采集速率稱為網(wǎng)絡(luò)共同收集速率.提高網(wǎng)絡(luò)共同收集速率有助于提高傳感器網(wǎng)絡(luò)的監(jiān)測精度，因此，高速率的數(shù)據(jù)收集方案是許多EH-WSN應(yīng)用者(如多媒體傳感器網(wǎng)絡(luò))的追求目標(biāo)之一.

人們對EH-WSN網(wǎng)絡(luò)共同收集速率最大化問題進(jìn)行了不少研究.文獻(xiàn)[2-4]研究了使用移動(dòng)sink節(jié)點(diǎn)場景下的網(wǎng)絡(luò)共同收集速率最大化問題，但它們的研究成果并不適用于sink節(jié)點(diǎn)不能移動(dòng)的網(wǎng)絡(luò)場景;文獻(xiàn)[1,5-7]研究了EH-WSN中非樹型數(shù)據(jù)收集策略下的網(wǎng)絡(luò)共同收集速率最大化問題，其研究成果也不能直接應(yīng)用于基于收集樹的網(wǎng)絡(luò).收集樹路由因具有計(jì)算簡單、無需路由表等優(yōu)點(diǎn)，能夠適應(yīng)傳感器節(jié)點(diǎn)計(jì)算能力弱、存儲空間少的特點(diǎn)[8]，被廣泛地應(yīng)用于EH-WSN中.

目前，專門研究基于收集樹的EH-WSN網(wǎng)絡(luò)共同收集速率最大化問題的文獻(xiàn)還很少.文獻(xiàn)[1]研究了收集樹給定情況下的網(wǎng)絡(luò)共同收集速率最大化問題，并提出了一種名為DLEX的分布式算法來求解網(wǎng)絡(luò)的最大共同收集速率.然而，給定一個(gè)EH-WSN網(wǎng)絡(luò)拓?fù)?，可以生成很多棵不同的?shù)據(jù)收集樹，不同的收集樹將導(dǎo)致不同的網(wǎng)絡(luò)共同收集速率.所以，根據(jù)EH-WSN中節(jié)點(diǎn)的捕獲能量情況尋找一棵最優(yōu)數(shù)據(jù)收集樹是提高網(wǎng)絡(luò)共同收集速率的有效手段.然而，這方面的研究也非常少.文獻(xiàn)[9]提出了基于馬爾可夫決策過程的父節(jié)點(diǎn)切換方法來平衡節(jié)點(diǎn)的能量消耗，從而保持EH-WSN收集樹能量的可持續(xù)性，然而其優(yōu)化目標(biāo)不是最大化網(wǎng)絡(luò)共同收集速率.

當(dāng)節(jié)點(diǎn)在某一時(shí)段內(nèi)捕獲的能量具有高可預(yù)測性時(shí)，EH-WSN網(wǎng)絡(luò)共同收集速率最大化問題等價(jià)于傳統(tǒng)WSN在節(jié)點(diǎn)數(shù)據(jù)采集速率相同情況下的網(wǎng)絡(luò)壽命最大化問題.人們對基于收集樹優(yōu)化的WSN網(wǎng)絡(luò)壽命最大化問題進(jìn)行了很多研究.絕大多數(shù)文獻(xiàn)將WSN的壽命定義為第一個(gè)失效節(jié)點(diǎn)的生命周期.文獻(xiàn)[10-13]研究了收集樹節(jié)點(diǎn)具有數(shù)據(jù)融合能力的WSN網(wǎng)絡(luò)壽命最大化問題;文獻(xiàn)[14]提出了基于能耗最小生成樹和信息擺渡相結(jié)合的方法來延長網(wǎng)絡(luò)生命周期;文獻(xiàn)[15]證明了在節(jié)點(diǎn)無數(shù)據(jù)融合功能的WSN中構(gòu)建最大網(wǎng)絡(luò)壽命收集樹是一個(gè)NP難問題，提出了優(yōu)化網(wǎng)絡(luò)壽命的啟發(fā)式收集樹構(gòu)建方法MNL;文獻(xiàn)[16]把WSN的最大網(wǎng)絡(luò)壽命收集樹問題表示為最小最大權(quán)重生成樹問題，并提出了構(gòu)建最大網(wǎng)絡(luò)壽命收集樹的迭代算法MITT.實(shí)驗(yàn)結(jié)果顯示,基于迭代優(yōu)化思想的MITT算法優(yōu)于PEDAP-PA[17]、MNL等啟發(fā)式構(gòu)造算法.文獻(xiàn)[18]提出了名為RaSMaLai的最大網(wǎng)絡(luò)壽命收集樹尋找算法，但它對網(wǎng)絡(luò)規(guī)模和拓?fù)涞倪m應(yīng)性不如MITT算法;文獻(xiàn)[19]把最大網(wǎng)絡(luò)壽命收集樹的構(gòu)建問題建模為混合整數(shù)線性規(guī)劃問題，但該方法僅適合于小規(guī)模網(wǎng)絡(luò).

顯然，借鑒上述算法的思想可以設(shè)計(jì)出相應(yīng)算法來尋找具有最大網(wǎng)絡(luò)共同收集速率的收集樹.然而，收集樹路由存在一個(gè)比較大的缺點(diǎn)，那就是某個(gè)節(jié)點(diǎn)的失效會導(dǎo)致其子樹無法向sink節(jié)點(diǎn)傳輸數(shù)據(jù).為了解決這一問題，人們提出了IEEE 802.15.5標(biāo)準(zhǔn)[20].IEEE 802.15.5標(biāo)準(zhǔn)讓每個(gè)節(jié)點(diǎn)在保存收集樹信息的基礎(chǔ)上維護(hù)若干跳鄰居的鏈路信息，從而形成mesh網(wǎng)絡(luò).mesh網(wǎng)絡(luò)不僅保留了樹路由的優(yōu)點(diǎn)，而且節(jié)點(diǎn)之間存在多條路徑,提高了網(wǎng)絡(luò)的可靠性，使得部分?jǐn)?shù)據(jù)能夠繞過收集樹中的瓶頸節(jié)點(diǎn)，從而提高了整個(gè)網(wǎng)絡(luò)的最大共同收集速率.遺憾的是，目前還沒有文獻(xiàn)對基于mesh路由優(yōu)化的網(wǎng)絡(luò)共同收集速率最大化問題進(jìn)行研究.

本文針對節(jié)點(diǎn)無數(shù)據(jù)融合功能的EH-WSN網(wǎng)絡(luò)共同收集速率最大化問題，研究基于收集樹優(yōu)化和mesh路由優(yōu)化的EH-WSN網(wǎng)絡(luò)共同收集速率最大化方法，主要貢獻(xiàn)如下：

1)提出了一種啟發(fā)式構(gòu)造和迭代優(yōu)化相結(jié)合的最大網(wǎng)絡(luò)共同收集速率收集樹尋找算法hybridMCRT.

2)針對收集樹中存在的瓶頸節(jié)點(diǎn)問題，提出了以最大網(wǎng)絡(luò)共同收集速率收集樹為導(dǎo)向的mesh路由算法MCRToMesh.

3)提出了基于MCRToMesh路由算法的網(wǎng)絡(luò)共同收集速率最大化方法，通過把基于MCRToMesh路由的網(wǎng)絡(luò)共同收集速率最大化問題建模為線性規(guī)劃問題，求解出最大網(wǎng)絡(luò)共同收集速率及每個(gè)節(jié)點(diǎn)最優(yōu)的mesh路由轉(zhuǎn)發(fā)目標(biāo)及轉(zhuǎn)發(fā)比率.

4)通過大量實(shí)驗(yàn)仿真驗(yàn)證了本文算法的有效性.

1 基于mesh路由的高速率數(shù)據(jù)收集方案

1.1 網(wǎng)絡(luò)模型

本文對研究的網(wǎng)絡(luò)作如下假設(shè)：傳感器節(jié)點(diǎn)一旦部署，其位置不會發(fā)生改變；sink節(jié)點(diǎn)具有充足的能量，其他節(jié)點(diǎn)從環(huán)境中捕獲能量，并配備有較大容量可充電電池，且其在某一時(shí)段的捕獲能量具有高可預(yù)測性；每個(gè)傳感器節(jié)點(diǎn)與sink節(jié)點(diǎn)之間至少存在一條路徑，即網(wǎng)絡(luò)中不存在孤立節(jié)點(diǎn).

用無向圖G(V,A)表示能量捕獲傳感器網(wǎng)絡(luò)，其中V是節(jié)點(diǎn)集合，包括sink節(jié)點(diǎn)(以s0表示)，A是鏈路集合.d0表示節(jié)點(diǎn)的無線電覆蓋半徑，〈u,v〉和d(u,v)分別表示節(jié)點(diǎn)u,v之間的通信鏈路和距離.于是，A={〈u,v〉|d(u,v)≤d0,u,v∈V}.此外，用N(u)表示節(jié)點(diǎn)u的一跳鄰居;T(VT,AT)表示圖G(V,A)中一棵以s0為根的生成樹;VT表示生成樹T中的節(jié)點(diǎn)集合;AT表示生成樹T中的鏈路集合;用pv表示節(jié)點(diǎn)v的父節(jié)點(diǎn);TL(v)表示節(jié)點(diǎn)v在樹T中的層數(shù)，并設(shè)s0位于第0層，即TL(s0)=0.另外，分別用DNv和ANv表示節(jié)點(diǎn)v的子孫節(jié)點(diǎn)集和祖先節(jié)點(diǎn)集;以mv表示DNv的元素個(gè)數(shù).

(1)

(2)

給定一個(gè)網(wǎng)絡(luò)拓?fù)?，可以生成很多棵不同的收集樹，而不同的收集樹具有不同的網(wǎng)絡(luò)共同收集速率，筆者把網(wǎng)絡(luò)共同收集速率最大的那一棵收集樹稱為最大網(wǎng)絡(luò)共同收集速率收集樹.由文獻(xiàn)[15]可知，尋找最大網(wǎng)絡(luò)共同收集速率收集樹是一個(gè)NP難問題.筆者提出啟發(fā)式構(gòu)造和迭代調(diào)整優(yōu)化相結(jié)合的最大網(wǎng)絡(luò)共同收集速率收集樹尋找算法hybridMCRT.

1.2 hybridMCRT算法

hybridMCRT算法的基本思想如下：首先利用啟發(fā)式方法構(gòu)造一棵最大網(wǎng)絡(luò)共同收集速率收集樹，然后再利用迭代調(diào)整方法不斷對該收集樹進(jìn)行優(yōu)化，最后對收集樹進(jìn)行調(diào)整以消除“路由繞行”問題.

通過借鑒和改進(jìn)MNL算法思想，提出了名為iMNL-based MCRT的最大網(wǎng)絡(luò)共同收集速率收集樹啟發(fā)式構(gòu)造算法，其算法思想如下：從sink節(jié)點(diǎn)(s0)開始，每次選擇一個(gè)使網(wǎng)絡(luò)共同收集速率下降最小的節(jié)點(diǎn)加入到收集樹中，直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)加入收集樹.在此過程中，當(dāng)有多個(gè)節(jié)點(diǎn)能使網(wǎng)絡(luò)共同收集速率下降最小時(shí)，優(yōu)先選擇捕獲能量多的節(jié)點(diǎn)加入收集樹，這就是iMNL-based MCRT算法對MNL算法思想的改進(jìn)之處.iMNL-based MCRT算法的詳細(xì)步驟如下：

算法1iMNL-based MCRT(G){

VT={s0},AT=?,VL=V-{s0},TL(s0)=0

WhileVL≠? Do

maxR=0

For eachu∈VLDo //遍歷剩余節(jié)點(diǎn)

For eachv∈VTDo //遍歷樹中節(jié)點(diǎn)

If (〈u,v〉∈A){

Ttemp=(VT∪{u},AT∪{〈u,v〉})

If(NCR(Ttemp)>maxR)

maxR=NCR(Ttemp),〈u*,v*〉=〈u,v〉

Else If(NCR(Ttemp)=maxR&&

〈u*,v*〉=〈u,v〉

EndIf

EndIf

EndFor

EndFor

VT=VT∪{u*},AT=AT∪{〈u*,v*〉}

VL=VL-{u*},TL(u*)=TL(v*)+1

EndWhile

ReturnT(VT,AT)

}

用iMNL-based MCRT算法生成最大網(wǎng)絡(luò)共同收集速率收集樹后，hybridMCRT算法需要再用迭代調(diào)整算法對該收集樹進(jìn)行優(yōu)化.文獻(xiàn)[16]把WSN的最大網(wǎng)絡(luò)壽命收集樹問題表示為最小最大權(quán)重生成樹問題，并提出了通過迭代調(diào)整收集樹來優(yōu)化網(wǎng)絡(luò)壽命的MITT算法，該算法從任意一棵收集樹開始，迭代地讓最大權(quán)重節(jié)點(diǎn)的子孫節(jié)點(diǎn)關(guān)聯(lián)至具有更小權(quán)重的鄰居節(jié)點(diǎn)來不斷降低收集樹的權(quán)重，從而不斷優(yōu)化網(wǎng)絡(luò)壽命.在EH-WSN中，當(dāng)節(jié)點(diǎn)在某一時(shí)段內(nèi)捕獲的能量具有高可預(yù)測性時(shí)，網(wǎng)絡(luò)共同收集速率最大化問題等價(jià)于傳統(tǒng)WSN在節(jié)點(diǎn)采集速率相同情況下的網(wǎng)絡(luò)壽命最大化問題.因此，筆者提出了基于MITT算法思想的最大網(wǎng)絡(luò)共同收集速率收集樹迭代優(yōu)化算法MITT-based MCRT.MITT-based MCRT算法與MITT算法基本相同，唯一的差異就是MITT-based MCRT算法賦予了節(jié)點(diǎn)權(quán)重和收集樹權(quán)重不同的含義.下面給出MITT-based MCRT算法中用到的節(jié)點(diǎn)權(quán)重和收集樹權(quán)重的定義.

定義1節(jié)點(diǎn)權(quán)重：收集樹T中的節(jié)點(diǎn)v(v∈VT-{s0})的權(quán)重定義為

(3)

式(3)中，w(T,v)表示節(jié)點(diǎn)v為每個(gè)子樹節(jié)點(diǎn)轉(zhuǎn)發(fā)1比特?cái)?shù)據(jù)所消耗的能量之和與其捕獲能量的比值.比值越大，表明它能夠?yàn)槊總€(gè)子樹節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)量越少.

定義2收集樹T的權(quán)重定義為

(4)

收集樹的權(quán)重越大，意味著在t時(shí)段內(nèi)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)能夠共同支持的最大數(shù)據(jù)采集量越小，即網(wǎng)絡(luò)共同收集速率越小.為了提高基于收集樹T的網(wǎng)絡(luò)共同收集速率，需要不斷降低收集樹的權(quán)重w(T)，即收集樹中瓶頸節(jié)點(diǎn)的權(quán)重.MITT-based MCRT算法的總體策略與MITT算法一樣，就是迭代地把瓶頸節(jié)點(diǎn)的子孫節(jié)點(diǎn)關(guān)聯(lián)至具有較小權(quán)重的其他子樹節(jié)點(diǎn)來逐漸降低收集樹的權(quán)重.因此，只需用式(3)和式(4)分別代替MITT算法中的節(jié)點(diǎn)權(quán)重和收集樹權(quán)重，即可得到MITT-based MCRT算法.MITT算法的詳細(xì)介紹可參閱文獻(xiàn)[16]，在此不再贅述.

通過實(shí)驗(yàn)發(fā)現(xiàn)，基于hybridMCRT算法得到的收集樹存在如圖1(a)所示的“路由繞行”問題.例如：節(jié)點(diǎn)F基于收集樹路由向sink節(jié)點(diǎn)傳遞數(shù)據(jù)的路徑為F→A→B→sink，而實(shí)際上，節(jié)點(diǎn)B既是節(jié)點(diǎn)F的祖先節(jié)點(diǎn)，又是它的一跳鄰居，因此，節(jié)點(diǎn)F的數(shù)據(jù)不必繞行節(jié)點(diǎn)A，可以直接通過節(jié)點(diǎn)B流向sink節(jié)點(diǎn).節(jié)點(diǎn)E也存在類似的問題.

圖1 收集樹“路由繞行”問題

“路由繞行”問題不僅浪費(fèi)節(jié)點(diǎn)能量，而且會增加數(shù)據(jù)傳輸跳數(shù)，從而影響端到端的通信時(shí)延.為了解決“路由繞行”問題，筆者提出了收集樹調(diào)整算法RegulateRoutingTree來消除“路由繞行”問題，其步驟如算法2所示.

算法2RegulateRoutingTree(T){

For eachvinVT-{s0} do

If (u≠pv)

pv=u,TL(v)=TL(u)+1

updateTreeLevelinSubTree(v)

EndIf

EndFor

ReturnT

}

其中，函數(shù)updateTreeLevelinSubTree(v)用于更新節(jié)點(diǎn)v所有子孫節(jié)點(diǎn)的樹層，其代碼如下：

Function updateTreeLevelinSubTree (v){

For eachxin {x|px=v,x∈N(v)} do

TL(x)=TL(v)+1

updateTreeLevelinSubTree(x)

EndFor

}

不難證明，在經(jīng)算法2調(diào)整的收集樹中，任意節(jié)點(diǎn)在其一跳鄰居中的最早祖先節(jié)點(diǎn)就是其父節(jié)點(diǎn).圖1(b)是經(jīng)算法2調(diào)整后的收集樹.

1.3 以收集樹為導(dǎo)向的mesh路由算法

為了進(jìn)一步提高基于收集樹的網(wǎng)絡(luò)共同收集速率，提出了以收集樹為導(dǎo)向的mesh路由算法MCRT-oriented mesh(簡稱MCRToMesh).其基本思想是通過mesh路由讓部分?jǐn)?shù)據(jù)有機(jī)會繞開瓶頸節(jié)點(diǎn)并最終到達(dá)sink節(jié)點(diǎn)，從而提高整個(gè)網(wǎng)絡(luò)的最大共同采集速率.mesh網(wǎng)絡(luò)的形成過程與IEEE 802.15.5類似，即節(jié)點(diǎn)在保存收集樹拓?fù)湫畔⒌幕A(chǔ)上，維護(hù)兩跳鄰居的相關(guān)信息，從而形成mesh網(wǎng)絡(luò).

步驟1：若當(dāng)前節(jié)點(diǎn)c是sink節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，則直接把數(shù)據(jù)包轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)；否則轉(zhuǎn)步驟2；

步驟2：在當(dāng)前節(jié)點(diǎn)c的一跳鄰居中找出數(shù)據(jù)包源節(jié)點(diǎn)s的最早祖先節(jié)點(diǎn)，然后將該祖先節(jié)點(diǎn)的父節(jié)點(diǎn)指定為錨節(jié)點(diǎn)(用anchor表示)，轉(zhuǎn)步驟3；

步驟3：在當(dāng)前節(jié)點(diǎn)c和錨節(jié)點(diǎn)anchor的共同鄰居集CN(c,anchor)中，根據(jù)在當(dāng)前節(jié)點(diǎn)c中存儲的數(shù)據(jù)轉(zhuǎn)發(fā)比率{φ(c,x,anchor)|x∈CN(c,anchor)}選擇一個(gè)節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，并把數(shù)據(jù)包轉(zhuǎn)發(fā)給中繼節(jié)點(diǎn).

MCRToMesh路由與IEEE 802.15.5 mesh路由的區(qū)別主要有兩點(diǎn)：IEEE 802.15.5mesh路由總是選擇與目標(biāo)節(jié)點(diǎn)樹路由距離最近的兩跳鄰居節(jié)點(diǎn)作為錨節(jié)點(diǎn)，而MCRToMesh則是選擇數(shù)據(jù)包源節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)一跳鄰居中的最早祖先節(jié)點(diǎn)的父節(jié)點(diǎn)作為錨節(jié)點(diǎn)；IEEE 802.15.5 mesh路由從當(dāng)前節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的共同鄰居中隨機(jī)選擇某一節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，而MCRToMesh路由則根據(jù)優(yōu)化的轉(zhuǎn)發(fā)比率選擇中繼節(jié)點(diǎn)(每個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)目標(biāo)和轉(zhuǎn)發(fā)比率通過1.4節(jié)的方法進(jìn)行識別和優(yōu)化).

下面通過一個(gè)例子說明MCRToMesh路由采用上述錨節(jié)點(diǎn)選擇策略的原因.在圖2所示的網(wǎng)絡(luò)中，節(jié)點(diǎn)的大小代表捕獲能量的多少，黑色箭頭線表示收集樹路由，虛線表示節(jié)點(diǎn)之間的鄰接關(guān)系.以節(jié)點(diǎn)I把源自節(jié)點(diǎn)H的數(shù)據(jù)傳遞給sink節(jié)點(diǎn)為例進(jìn)行說明.如圖2(a)所示，若采用IEEE 802.15.5 mesh路由，則節(jié)點(diǎn)I會選擇sink節(jié)點(diǎn)作為錨節(jié)點(diǎn)，從而選擇節(jié)點(diǎn)F作為中繼節(jié)點(diǎn)，也就是說來自節(jié)點(diǎn)H的數(shù)據(jù)都將沿著曲線箭頭所示的路徑流向sink節(jié)點(diǎn)，這就加重了節(jié)點(diǎn)F的流量負(fù)擔(dān)，有可能導(dǎo)致它所捕獲的能量不能支持相應(yīng)的流量負(fù)載，從而降低整個(gè)網(wǎng)絡(luò)的最大共同采集速率.而在圖2(b)所示的MCRToMesh路由過程中，數(shù)據(jù)總是有機(jī)會沿著收集樹路由到達(dá)sink節(jié)點(diǎn)，即在最壞情況下，基于MCRToMesh路由的網(wǎng)絡(luò)共同收集速率不會低于基于收集樹路由的網(wǎng)絡(luò)共同收集速率.

圖2 IEEE 802.15.5 mesh路由和MCRToMesh路由

1.4 基于MCRToMesh路由的網(wǎng)絡(luò)共同收集速率最大化方法

根據(jù)MCRToMesh路由機(jī)制，當(dāng)前節(jié)點(diǎn)首先根據(jù)數(shù)據(jù)包的源地址確定錨節(jié)點(diǎn)，然而通過它們的共同鄰居向錨節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù).當(dāng)錨節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)之間有多個(gè)共同鄰居(稱為中繼節(jié)點(diǎn))時(shí)，當(dāng)前節(jié)點(diǎn)按一定的比率(稱為轉(zhuǎn)發(fā)比率)選擇中繼節(jié)點(diǎn).顯然，節(jié)點(diǎn)不同的轉(zhuǎn)發(fā)比率分配方案將導(dǎo)致中繼節(jié)點(diǎn)具有不同的數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)載，這會影響整個(gè)網(wǎng)絡(luò)的最大共同采集速率.因此，提出對網(wǎng)絡(luò)中所有樹層大于1的節(jié)點(diǎn)的轉(zhuǎn)發(fā)比率進(jìn)行優(yōu)化來最大化網(wǎng)絡(luò)共同收集速率(樹層為1的節(jié)點(diǎn)直接把數(shù)據(jù)轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)，無需其他節(jié)點(diǎn)進(jìn)行中繼轉(zhuǎn)發(fā)).

設(shè)kt(u,x,v)表示節(jié)點(diǎn)u在t時(shí)段內(nèi)選擇節(jié)點(diǎn)x作為中繼節(jié)點(diǎn)向節(jié)點(diǎn)v轉(zhuǎn)發(fā)的數(shù)據(jù)量，則在t時(shí)段內(nèi)節(jié)點(diǎn)u選擇節(jié)點(diǎn)x作為中繼節(jié)點(diǎn)向節(jié)點(diǎn)v轉(zhuǎn)發(fā)數(shù)據(jù)的比率可表示為

因此，在t時(shí)段內(nèi)，基于節(jié)點(diǎn)轉(zhuǎn)發(fā)比率優(yōu)化的網(wǎng)絡(luò)共同收集速率最大化問題等價(jià)于基于節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)量優(yōu)化的網(wǎng)絡(luò)共同收集速率最大化問題.

為了實(shí)現(xiàn)對網(wǎng)絡(luò)共同收集速率的優(yōu)化，首先需要根據(jù)MCRToMesh路由機(jī)制識別出網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)(除sink節(jié)點(diǎn))的轉(zhuǎn)發(fā)流，它們是網(wǎng)絡(luò)共同收集速率最大化問題的優(yōu)化變量，筆者稱之為轉(zhuǎn)發(fā)流變量.sink節(jié)點(diǎn)的鄰居節(jié)點(diǎn)收到數(shù)據(jù)后，直接把數(shù)據(jù)轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)，無需其他節(jié)點(diǎn)進(jìn)行中繼轉(zhuǎn)發(fā).把所有樹層為1的節(jié)點(diǎn)的轉(zhuǎn)發(fā)流變量集合表示為Ft={ft(x,s0)|x∈N(s0)}，其中ft(x,s0) 表示節(jié)點(diǎn)x在t時(shí)段內(nèi)發(fā)送給s0的數(shù)據(jù)變量.

當(dāng)樹層大于1的節(jié)點(diǎn)收到數(shù)據(jù)時(shí)，首先根據(jù)數(shù)據(jù)包的源地址確定錨節(jié)點(diǎn)，然后向當(dāng)前節(jié)點(diǎn)與錨節(jié)點(diǎn)的共同鄰居轉(zhuǎn)發(fā)數(shù)據(jù).根據(jù)MCRToMesh路由策略，節(jié)點(diǎn)需要轉(zhuǎn)發(fā)的數(shù)據(jù)有2類：一類是自己產(chǎn)生的數(shù)據(jù)和源自子孫節(jié)點(diǎn)的數(shù)據(jù);另一類則源自其他節(jié)點(diǎn)并需要它進(jìn)行中繼轉(zhuǎn)發(fā)的數(shù)據(jù).任意節(jié)點(diǎn)u為轉(zhuǎn)發(fā)自己產(chǎn)生的數(shù)據(jù)和源自子孫節(jié)點(diǎn)的數(shù)據(jù)，會選擇其祖父節(jié)點(diǎn)(即父節(jié)點(diǎn)的父節(jié)點(diǎn)，用g(u)表示)作為錨節(jié)點(diǎn).因此，需要通過節(jié)點(diǎn)u進(jìn)行中繼轉(zhuǎn)發(fā)的鄰居節(jié)點(diǎn)集可表示為Nin(u)={v|v∈N(u),g(v)∈N(u)}.根據(jù)MCRToMesh路由策略，節(jié)點(diǎn)u為轉(zhuǎn)發(fā)源自x∈Nin(u)及其子孫節(jié)點(diǎn)的數(shù)據(jù)，會在其一跳鄰居中找到節(jié)點(diǎn)x的最早祖先節(jié)點(diǎn)，然后將該祖先節(jié)點(diǎn)的父節(jié)點(diǎn)作為錨節(jié)點(diǎn).因此，節(jié)點(diǎn)u為轉(zhuǎn)發(fā)數(shù)據(jù)所要用到的全部錨節(jié)點(diǎn)可表示為

Λ(u)=g(u)∪

根據(jù)MCRToMesh路由策略，節(jié)點(diǎn)u的所有轉(zhuǎn)發(fā)流變量表示為Kt(u)={kt(u,x,v)|x∈CN(u,v),v∈Λ(u)}.所有樹層大于1的節(jié)點(diǎn)的全部轉(zhuǎn)發(fā)流變量用Kt表示，即

下面說明圖3所示實(shí)例中各節(jié)點(diǎn)的轉(zhuǎn)發(fā)流變量(用帶箭頭虛曲線表示).節(jié)點(diǎn)H唯一的錨節(jié)點(diǎn)是C，而節(jié)點(diǎn)E和節(jié)點(diǎn)F是節(jié)點(diǎn)H和節(jié)點(diǎn)C的共同鄰居，因此節(jié)點(diǎn)H會把一部分?jǐn)?shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點(diǎn)E(用轉(zhuǎn)發(fā)流變量kt(H,E,C)表示)，把另一部分?jǐn)?shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點(diǎn)F(用轉(zhuǎn)發(fā)流變量kt(H,F,C)表示).節(jié)點(diǎn)F為了轉(zhuǎn)發(fā)源自節(jié)點(diǎn)H和節(jié)點(diǎn)E的數(shù)據(jù)會選擇sink作為錨節(jié)點(diǎn)，由于節(jié)點(diǎn)F與sink節(jié)點(diǎn)之間只有一個(gè)共同鄰居(即節(jié)點(diǎn)A)，節(jié)點(diǎn)F將源自節(jié)點(diǎn)H和節(jié)點(diǎn)E的數(shù)據(jù)全部轉(zhuǎn)發(fā)給A(用轉(zhuǎn)發(fā)流變量kt(F,A,S)表示)；另外，節(jié)點(diǎn)F為了轉(zhuǎn)發(fā)源自節(jié)點(diǎn)J的數(shù)據(jù)會選擇節(jié)點(diǎn)B作為錨節(jié)點(diǎn)，由于節(jié)點(diǎn)F與節(jié)點(diǎn)B之間只有一個(gè)共同鄰居(即節(jié)點(diǎn)D)，所以節(jié)點(diǎn)F將源自節(jié)點(diǎn)J的數(shù)據(jù)全部轉(zhuǎn)發(fā)給節(jié)點(diǎn)D(用轉(zhuǎn)發(fā)流變量kt(F,D,B)表示).

圖3 MCRToMesh路由實(shí)例

以網(wǎng)絡(luò)共同收集速率最大化為目標(biāo)，對所有的轉(zhuǎn)發(fā)流變量進(jìn)行優(yōu)化時(shí)，必須服從下面2個(gè)約束：能量約束，即每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)消耗的能量不能超過它所捕獲的能量；流量平衡約束，即流出節(jié)點(diǎn)的數(shù)據(jù)量應(yīng)等于流入節(jié)點(diǎn)的數(shù)據(jù)量加上它自己產(chǎn)生的數(shù)據(jù)量.根據(jù)上述分析，基于MCRToMesh路由的網(wǎng)絡(luò)共同收集速率最大化問題可表示為如下優(yōu)化問題：

maximizeσ;

w.r.t.σ,Ft,Kt

s.t.:

σ≥0;

(5)

kt(u,v,w)≥0, ?kt(u,v,w)∈Kt;

(6)

ft(v,s0)≥0, ?v∈N(s0);

(7)

?v∈VT-{s0};

(8)

?y∈Λ(v), ?v∈VT,TL(v)>1;

(9)

?v∈VT,TL(v)=1.

(10)

式(9)中,bv,y表示為

式(5)表示每個(gè)節(jié)點(diǎn)的數(shù)據(jù)采集量不能小于0，式(6)和式(7)表示每個(gè)流變量不能小于0；式(8)表示節(jié)點(diǎn)的能量約束，本文只考慮節(jié)點(diǎn)的數(shù)據(jù)收發(fā)能耗，而忽略計(jì)算、數(shù)據(jù)感知等能耗[1]；式(9)和式(10)表示節(jié)點(diǎn)流量平衡約束，式(9)適用于樹層大于1的節(jié)點(diǎn)，表示節(jié)點(diǎn)指向某一錨節(jié)點(diǎn)的流出數(shù)據(jù)量應(yīng)等于流入該節(jié)點(diǎn)并指向同一錨節(jié)點(diǎn)的流入數(shù)據(jù)量(若錨節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)，則流出數(shù)據(jù)量=流入數(shù)據(jù)量+采集數(shù)據(jù)量σ)，而式(10)適用于樹層為1的節(jié)點(diǎn)，表示所有流入節(jié)點(diǎn)的數(shù)據(jù)量加上自己的采集數(shù)據(jù)量σ應(yīng)等于流向sink節(jié)點(diǎn)的數(shù)據(jù)量.

?u∈VT,TL(u)>1.

(11)

2 實(shí)驗(yàn)仿真及結(jié)果分析

為了驗(yàn)證本文提出的相關(guān)算法，筆者模擬了節(jié)點(diǎn)密度相同但節(jié)點(diǎn)數(shù)量不同、以及節(jié)點(diǎn)數(shù)量相同但節(jié)點(diǎn)密度不同的多種網(wǎng)絡(luò)設(shè)置(節(jié)點(diǎn)密度定義為鄰居節(jié)點(diǎn)的數(shù)量).對于每種網(wǎng)絡(luò)設(shè)置隨機(jī)產(chǎn)生200個(gè)網(wǎng)絡(luò)拓?fù)?下面所示結(jié)果均為200個(gè)網(wǎng)絡(luò)拓?fù)鋵?shí)驗(yàn)結(jié)果的平均值)，并隨機(jī)設(shè)置sink節(jié)點(diǎn)的位置.對于每一個(gè)網(wǎng)絡(luò)拓?fù)浞謩e實(shí)現(xiàn)了以下5種最大網(wǎng)絡(luò)共同收集速率收集樹尋找算法：MNL-based MCRT算法(借鑒MNL算法思想的算法，簡稱MNL)、iMNL-based MCRT算法(借鑒和改進(jìn)MNL算法思想的算法，簡稱iMNL)、MITT-based MCRT算法(借鑒MITT算法思想的算法，簡稱MITT)、MITT-based MCRT with MNL算法(NML和MITT相結(jié)合的算法，簡稱hybrid MCRT1)、MITT-based MCRT with iMNL(iNML和MITT相結(jié)合的算法，簡稱hybrid MCRT2).仿真實(shí)驗(yàn)所用相關(guān)參數(shù)如表1所示.

表1 仿真實(shí)驗(yàn)所用參數(shù)

首先，對基于iMNL算法和MNL算法的網(wǎng)絡(luò)共同收集速率進(jìn)行了比較，比較結(jié)果如圖4所示.從圖4不難發(fā)現(xiàn)，iMNL算法優(yōu)于MNL算法，且其性能隨著網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)密度的增大而提高.這是因?yàn)殡S著網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)密度的增大，在收集樹的生長過程中，就有更多的機(jī)會出現(xiàn)存在多個(gè)候選生長節(jié)點(diǎn)使得收集樹最大共同采集速率具有最小下降量的情況，與MNL不同，iMNL總是從多個(gè)候選生長節(jié)點(diǎn)中選擇能量最多的節(jié)點(diǎn)加入收集樹，使得新得到的收集樹具有更多的能量，從而增加后續(xù)生成的收集樹具有更大共同采集速率的可能性.

然后，對hybrid MCRT1算法、hybrid MCRT2算法和MITT算法的性能進(jìn)行比較，比較結(jié)果如圖5所示.從圖5不難發(fā)現(xiàn)，hybrid MCRT1算法、hybrid MCRT2算法均優(yōu)于MITT算法，hybrid MCRT2算法又優(yōu)于hybrid MCRT1算法，這一實(shí)驗(yàn)結(jié)果表明：初始收集樹的好壞對MITT算法的性能具有十分重要的影響，同時(shí)也驗(yàn)證了hybird MCRT算法的有效性.

MCRToMesh方法和hybrid MCRT2算法的性能比較如圖6所示.從圖6(a)可以看出，在節(jié)點(diǎn)密度相同的情況下，MCRToMesh方法的性能隨著網(wǎng)絡(luò)規(guī)模的增大而變小，這是因?yàn)殡S著網(wǎng)絡(luò)規(guī)模的增大，其瓶頸節(jié)點(diǎn)的個(gè)數(shù)也會隨之增多，至少存在一個(gè)瓶頸節(jié)點(diǎn)得不到鄰居節(jié)點(diǎn)幫助(或得到較少幫助)的概率也會增加，從而使得MCRToMesh方法的性能也隨之下降.從對圖6(b)的觀察可知，在網(wǎng)絡(luò)規(guī)模相同節(jié)點(diǎn)密度不同的情況下，MCRToMesh方法的性能隨著節(jié)點(diǎn)密度的增大而提高，這是因?yàn)殡S著鄰居節(jié)點(diǎn)的增多，使得瓶頸節(jié)點(diǎn)得到鄰居節(jié)點(diǎn)幫助的概率也隨之增加，從而使得MCRToMesh方法的性能也隨之提高.

(a)不同網(wǎng)絡(luò)規(guī)模 (b)不同節(jié)點(diǎn)密度

3 結(jié) 語

本文研究了基于mesh路由的能量捕獲傳感器網(wǎng)絡(luò)高速率數(shù)據(jù)收集方案，首先提出了一種啟發(fā)式構(gòu)造和迭代優(yōu)化相結(jié)合的最大網(wǎng)絡(luò)共同收集速率收集樹尋找算法，并以此為基礎(chǔ)提出了收集樹導(dǎo)向的mesh路由算法MCRToMesh，采用線性規(guī)劃技術(shù)優(yōu)化了基于MCRToMesh路由的網(wǎng)絡(luò)共同收集速率.本文所提方法不僅可用于求解EH-WSN網(wǎng)絡(luò)共同收集速率最大化問題，也同樣適用于WSN在節(jié)點(diǎn)采集速率相同情況下的網(wǎng)絡(luò)壽命最大化問題.