基于mesh路由的EH-WSN高速率數據收集方案

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

(1.浙江師范大學 行知學院,浙江 金華 321004；2.浙江師范大學 數學與計算機科學學院,浙江 金華 321004)

0 引 言

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

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

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

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

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

本文針對節點無數據融合功能的EH-WSN網絡共同收集速率最大化問題，研究基于收集樹優化和mesh路由優化的EH-WSN網絡共同收集速率最大化方法，主要貢獻如下：

1)提出了一種啟發式構造和迭代優化相結合的最大網絡共同收集速率收集樹尋找算法hybridMCRT.

2)針對收集樹中存在的瓶頸節點問題，提出了以最大網絡共同收集速率收集樹為導向的mesh路由算法MCRToMesh.

3)提出了基于MCRToMesh路由算法的網絡共同收集速率最大化方法，通過把基于MCRToMesh路由的網絡共同收集速率最大化問題建模為線性規劃問題，求解出最大網絡共同收集速率及每個節點最優的mesh路由轉發目標及轉發比率.

4)通過大量實驗仿真驗證了本文算法的有效性.

1 基于mesh路由的高速率數據收集方案

1.1 網絡模型

本文對研究的網絡作如下假設：傳感器節點一旦部署，其位置不會發生改變；sink節點具有充足的能量，其他節點從環境中捕獲能量，并配備有較大容量可充電電池，且其在某一時段的捕獲能量具有高可預測性；每個傳感器節點與sink節點之間至少存在一條路徑，即網絡中不存在孤立節點.

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

(1)

(2)

給定一個網絡拓撲，可以生成很多棵不同的收集樹，而不同的收集樹具有不同的網絡共同收集速率，筆者把網絡共同收集速率最大的那一棵收集樹稱為最大網絡共同收集速率收集樹.由文獻[15]可知，尋找最大網絡共同收集速率收集樹是一個NP難問題.筆者提出啟發式構造和迭代調整優化相結合的最大網絡共同收集速率收集樹尋找算法hybridMCRT.

1.2 hybridMCRT算法

hybridMCRT算法的基本思想如下：首先利用啟發式方法構造一棵最大網絡共同收集速率收集樹，然后再利用迭代調整方法不斷對該收集樹進行優化，最后對收集樹進行調整以消除“路由繞行”問題.

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

算法1iMNL-based MCRT(G){

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

WhileVL≠? Do

maxR=0

For eachu∈VLDo //遍歷剩余節點

For eachv∈VTDo //遍歷樹中節點

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算法生成最大網絡共同收集速率收集樹后，hybridMCRT算法需要再用迭代調整算法對該收集樹進行優化.文獻[16]把WSN的最大網絡壽命收集樹問題表示為最小最大權重生成樹問題，并提出了通過迭代調整收集樹來優化網絡壽命的MITT算法，該算法從任意一棵收集樹開始，迭代地讓最大權重節點的子孫節點關聯至具有更小權重的鄰居節點來不斷降低收集樹的權重，從而不斷優化網絡壽命.在EH-WSN中，當節點在某一時段內捕獲的能量具有高可預測性時，網絡共同收集速率最大化問題等價于傳統WSN在節點采集速率相同情況下的網絡壽命最大化問題.因此，筆者提出了基于MITT算法思想的最大網絡共同收集速率收集樹迭代優化算法MITT-based MCRT.MITT-based MCRT算法與MITT算法基本相同，唯一的差異就是MITT-based MCRT算法賦予了節點權重和收集樹權重不同的含義.下面給出MITT-based MCRT算法中用到的節點權重和收集樹權重的定義.

定義1節點權重：收集樹T中的節點v(v∈VT-{s0})的權重定義為

(3)

式(3)中，w(T,v)表示節點v為每個子樹節點轉發1比特數據所消耗的能量之和與其捕獲能量的比值.比值越大，表明它能夠為每個子樹節點轉發的數據量越少.

定義2收集樹T的權重定義為

(4)

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

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

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

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

算法2RegulateRoutingTree(T){

For eachvinVT-{s0} do

If (u≠pv)

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

updateTreeLevelinSubTree(v)

EndIf

EndFor

ReturnT

}

其中，函數updateTreeLevelinSubTree(v)用于更新節點v所有子孫節點的樹層，其代碼如下：

Function updateTreeLevelinSubTree (v){

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

TL(x)=TL(v)+1

updateTreeLevelinSubTree(x)

EndFor

}

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

1.3 以收集樹為導向的mesh路由算法

為了進一步提高基于收集樹的網絡共同收集速率，提出了以收集樹為導向的mesh路由算法MCRT-oriented mesh(簡稱MCRToMesh).其基本思想是通過mesh路由讓部分數據有機會繞開瓶頸節點并最終到達sink節點，從而提高整個網絡的最大共同采集速率.mesh網絡的形成過程與IEEE 802.15.5類似，即節點在保存收集樹拓撲信息的基礎上，維護兩跳鄰居的相關信息，從而形成mesh網絡.

步驟1：若當前節點c是sink節點的鄰居節點，則直接把數據包轉發給sink節點；否則轉步驟2；

步驟2：在當前節點c的一跳鄰居中找出數據包源節點s的最早祖先節點，然后將該祖先節點的父節點指定為錨節點(用anchor表示)，轉步驟3；

步驟3：在當前節點c和錨節點anchor的共同鄰居集CN(c,anchor)中，根據在當前節點c中存儲的數據轉發比率{φ(c,x,anchor)|x∈CN(c,anchor)}選擇一個節點作為中繼節點，并把數據包轉發給中繼節點.

MCRToMesh路由與IEEE 802.15.5 mesh路由的區別主要有兩點：IEEE 802.15.5mesh路由總是選擇與目標節點樹路由距離最近的兩跳鄰居節點作為錨節點，而MCRToMesh則是選擇數據包源節點在當前節點一跳鄰居中的最早祖先節點的父節點作為錨節點；IEEE 802.15.5 mesh路由從當前節點和錨節點之間的共同鄰居中隨機選擇某一節點作為中繼節點，而MCRToMesh路由則根據優化的轉發比率選擇中繼節點(每個節點的轉發目標和轉發比率通過1.4節的方法進行識別和優化).

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

圖2 IEEE 802.15.5 mesh路由和MCRToMesh路由

1.4 基于MCRToMesh路由的網絡共同收集速率最大化方法

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

設kt(u,x,v)表示節點u在t時段內選擇節點x作為中繼節點向節點v轉發的數據量，則在t時段內節點u選擇節點x作為中繼節點向節點v轉發數據的比率可表示為

因此，在t時段內，基于節點轉發比率優化的網絡共同收集速率最大化問題等價于基于節點轉發數據量優化的網絡共同收集速率最大化問題.

為了實現對網絡共同收集速率的優化，首先需要根據MCRToMesh路由機制識別出網絡中每個節點(除sink節點)的轉發流，它們是網絡共同收集速率最大化問題的優化變量，筆者稱之為轉發流變量.sink節點的鄰居節點收到數據后，直接把數據轉發給sink節點，無需其他節點進行中繼轉發.把所有樹層為1的節點的轉發流變量集合表示為Ft={ft(x,s0)|x∈N(s0)}，其中ft(x,s0) 表示節點x在t時段內發送給s0的數據變量.

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

Λ(u)=g(u)∪

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

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

圖3 MCRToMesh路由實例

以網絡共同收集速率最大化為目標，對所有的轉發流變量進行優化時，必須服從下面2個約束：能量約束，即每個節點轉發數據消耗的能量不能超過它所捕獲的能量；流量平衡約束，即流出節點的數據量應等于流入節點的數據量加上它自己產生的數據量.根據上述分析，基于MCRToMesh路由的網絡共同收集速率最大化問題可表示為如下優化問題：

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)表示每個節點的數據采集量不能小于0，式(6)和式(7)表示每個流變量不能小于0；式(8)表示節點的能量約束，本文只考慮節點的數據收發能耗，而忽略計算、數據感知等能耗[1]；式(9)和式(10)表示節點流量平衡約束，式(9)適用于樹層大于1的節點，表示節點指向某一錨節點的流出數據量應等于流入該節點并指向同一錨節點的流入數據量(若錨節點是當前節點的祖父節點，則流出數據量=流入數據量+采集數據量σ)，而式(10)適用于樹層為1的節點，表示所有流入節點的數據量加上自己的采集數據量σ應等于流向sink節點的數據量.

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

(11)

2 實驗仿真及結果分析

為了驗證本文提出的相關算法，筆者模擬了節點密度相同但節點數量不同、以及節點數量相同但節點密度不同的多種網絡設置(節點密度定義為鄰居節點的數量).對于每種網絡設置隨機產生200個網絡拓撲(下面所示結果均為200個網絡拓撲實驗結果的平均值)，并隨機設置sink節點的位置.對于每一個網絡拓撲分別實現了以下5種最大網絡共同收集速率收集樹尋找算法：MNL-based MCRT算法(借鑒MNL算法思想的算法，簡稱MNL)、iMNL-based MCRT算法(借鑒和改進MNL算法思想的算法，簡稱iMNL)、MITT-based MCRT算法(借鑒MITT算法思想的算法，簡稱MITT)、MITT-based MCRT with MNL算法(NML和MITT相結合的算法，簡稱hybrid MCRT1)、MITT-based MCRT with iMNL(iNML和MITT相結合的算法，簡稱hybrid MCRT2).仿真實驗所用相關參數如表1所示.

表1 仿真實驗所用參數

首先，對基于iMNL算法和MNL算法的網絡共同收集速率進行了比較，比較結果如圖4所示.從圖4不難發現，iMNL算法優于MNL算法，且其性能隨著網絡規模和節點密度的增大而提高.這是因為隨著網絡規模和節點密度的增大，在收集樹的生長過程中，就有更多的機會出現存在多個候選生長節點使得收集樹最大共同采集速率具有最小下降量的情況，與MNL不同，iMNL總是從多個候選生長節點中選擇能量最多的節點加入收集樹，使得新得到的收集樹具有更多的能量，從而增加后續生成的收集樹具有更大共同采集速率的可能性.

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

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

(a)不同網絡規模 (b)不同節點密度

3 結 語

本文研究了基于mesh路由的能量捕獲傳感器網絡高速率數據收集方案，首先提出了一種啟發式構造和迭代優化相結合的最大網絡共同收集速率收集樹尋找算法，并以此為基礎提出了收集樹導向的mesh路由算法MCRToMesh，采用線性規劃技術優化了基于MCRToMesh路由的網絡共同收集速率.本文所提方法不僅可用于求解EH-WSN網絡共同收集速率最大化問題，也同樣適用于WSN在節點采集速率相同情況下的網絡壽命最大化問題.