無線傳感器網(wǎng)絡(luò)最大生命期聚合樹路由算法*

薛 明， 高德民

(1.南京郵電大學 計算機學院，江蘇 南京 210003;

2.南京林業(yè)大學 信息科學技術(shù)學院，江蘇 南京 210037)

0 引 言

無線傳感器網(wǎng)絡(luò)生命期通常被定義為最先因為電池能量耗盡而失效的傳感器節(jié)點的生命期[1]。網(wǎng)絡(luò)最大生命期問題可以被歸結(jié)為一棵最小Steiner生成樹的問題[2]，其中, MEGA(minimum energy gathering algorithm)[3]是基于最小功率生成樹模型，算法通過編碼樹選擇數(shù)據(jù)融合點，采用了有向圖中的最短生成樹獲取問題的解。為達到負載均衡，可以將負載過重節(jié)點的能耗因素均衡到其它節(jié)點上以達到延長節(jié)點壽命的目的。LEACH算法[4]利用節(jié)點周期性輪流擔任簇頭策略，將節(jié)點的數(shù)據(jù)集中到鄰近的簇頭進行融合轉(zhuǎn)發(fā)，雖然沒有考慮功率調(diào)節(jié)作用，但是使全簇節(jié)點能耗消耗均衡。在以網(wǎng)絡(luò)生命期為最優(yōu)化模型中，根據(jù)數(shù)據(jù)能耗限制和數(shù)據(jù)流量不變性建立以生命期為最優(yōu)值的線性規(guī)劃模型[1]得到廣泛應用，將網(wǎng)絡(luò)最小能耗作為次優(yōu)化因素[5]，既考慮了生命期問題，也考慮了網(wǎng)絡(luò)能耗因素。該類模型通常是基于最優(yōu)化理論模型，最終可以收斂到網(wǎng)絡(luò)生命期的上界。文獻[6,7]在多物流線性規(guī)劃模型上提出一個啟發(fā)式算法，從節(jié)點容量限制角度考慮數(shù)據(jù)流在節(jié)點處匯聚情況，通過數(shù)據(jù)流權(quán)函數(shù)模型，網(wǎng)絡(luò)流延權(quán)函數(shù)梯度層向下游轉(zhuǎn)發(fā)，節(jié)點可以實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)最大化。在數(shù)據(jù)融合算法中，MLR算法[8]采用地理位置路由，數(shù)據(jù)被分類為原始數(shù)據(jù)和融合數(shù)據(jù)，2種數(shù)據(jù)都按照一定比例被分發(fā)到鄰居節(jié)點，并通過最優(yōu)化方法對最優(yōu)比例進行求解以最大化網(wǎng)絡(luò)生命期。該類算法可以平衡節(jié)點能量消耗，將負載過重節(jié)點能耗均衡到整個網(wǎng)絡(luò)中，延長網(wǎng)絡(luò)的生命期。研究實驗表明:上述路由算法在一定程度提高了無線傳感器網(wǎng)絡(luò)的傳輸性能，但當網(wǎng)絡(luò)規(guī)模不斷擴大和傳感器的分布更加復雜時，傳感器節(jié)點有限的計算能力遠不能滿足復雜路由計算的需求。

本文根據(jù)能量等限制條件建立線性規(guī)劃模型，考慮到網(wǎng)絡(luò)最大生命期是NP難問題，將網(wǎng)絡(luò)最大生命期問題轉(zhuǎn)化為網(wǎng)絡(luò)最小歸一化負載問題，建立一棵最優(yōu)網(wǎng)絡(luò)歸一化負載數(shù)據(jù)融合樹，數(shù)據(jù)以較低能耗延融合樹向基站轉(zhuǎn)發(fā)，最終實現(xiàn)網(wǎng)絡(luò)生命期最大化。

1 系統(tǒng)模型

1.1 系統(tǒng)模型

網(wǎng)絡(luò)被抽象為一個無向圖G(V,A)，其中，V表示節(jié)點和基站的集合，A表示鏈路集合。節(jié)點i∈V的鄰居節(jié)點集合記為Si，鏈路集合為{(i,j)∈A|i,j∈V,j∈Si}。假設(shè)節(jié)點i平均在t時間內(nèi)產(chǎn)生的數(shù)據(jù)字節(jié)數(shù)為Gt，產(chǎn)生速率為Gi=Gt/t，在每隔1/Gi時間內(nèi)產(chǎn)生一個數(shù)據(jù)字節(jié)，假設(shè)一個數(shù)據(jù)包的大小為k個字節(jié)，新字節(jié)被附在數(shù)據(jù)包末端以不大于包容量被傳送。時間間隔為τ=k/Gi，本文以τ作為系統(tǒng)的單位時間。

1.2 問題描述

假設(shè)網(wǎng)絡(luò)生命期為Tτ，如果τ作為網(wǎng)絡(luò)系統(tǒng)單位時間，網(wǎng)絡(luò)生命期可以看作為T,T為所有節(jié)點的最小生命期,則節(jié)點i在T時間內(nèi)的能量消耗不會超過當前能量Ei

(1)

源節(jié)點s發(fā)送到基站的數(shù)據(jù)經(jīng)過邊(i,j)的數(shù)據(jù)量為fs(i,j)，本文為網(wǎng)絡(luò)中每一個s-t通信建立線性規(guī)劃數(shù)學模型為

maxT

?i=1,2,…,nandi≠t,

0≤fs(i,j)≤U(i,j),

?i=1,2,…,nand ?j=1,2,…,n,t,

(2)

其中，f(i,k)表示節(jié)點i在T時間內(nèi)發(fā)送給下游節(jié)點的數(shù)據(jù)流總量。

式(2)中條件1表示節(jié)點i的能量消耗也不會超過當前能量E，條件2表示源節(jié)點轉(zhuǎn)發(fā)的流量等于接收到的融合數(shù)據(jù)流量；條件3表示源節(jié)點s的本身產(chǎn)生的生命期為T，s在傳輸數(shù)據(jù)流時，發(fā)送的數(shù)據(jù)流為接收數(shù)據(jù)流和自身數(shù)據(jù)流的融合；條件4表示源節(jié)點s在某一鏈路中的數(shù)據(jù)流量不超過網(wǎng)絡(luò)最大吞吐量；條件5表示為源節(jié)點s產(chǎn)生的數(shù)據(jù)流總和一定為T。

2 最大生命期數(shù)據(jù)融合樹生成算法

2.1 算法描述

根據(jù)式(2)限制，本文在每一次迭代中建立一棵融合樹。網(wǎng)絡(luò)在每個τ時間單位內(nèi)，形成一棵網(wǎng)絡(luò)數(shù)據(jù)融合樹，以基站t為根節(jié)點，向下延伸到所有的傳感器節(jié)點，融合樹表示為H。數(shù)據(jù)從葉子節(jié)點經(jīng)中間節(jié)點融合后最終到達基站。無線傳感器網(wǎng)絡(luò)最大生命期為T，即一定存在T棵融合樹。假設(shè)在網(wǎng)絡(luò)中總共可能存在Ω棵融合樹，則無線傳感器網(wǎng)絡(luò)最大生命期算法即尋找生命期最大T棵樹。

2.2 節(jié)點負載量化模型

在某τ時間單位內(nèi)，存在數(shù)據(jù)融合樹集合為Ω，其中一棵數(shù)據(jù)融合樹表示為H，歸一化負載為W(H)，H*為最大歸一化負載融合樹,H*∈Ω，歸一化負載為W(H*)。因為H*為最大歸一化負載融合樹，所以，|S(H*)|≥|S(H)|。根據(jù)二叉樹算法

亦即

(3)

定義1 在τ時間單位內(nèi)，存在1棵數(shù)據(jù)融合樹H，歸一化負載為W(H)，定義滿足式(4)的節(jié)點為負載較重節(jié)點

(4)

由式(3),式(4)可以得到

定義滿足式(5)的節(jié)點為負載合理節(jié)點

(5)

2.3 融合樹生成算法實現(xiàn)

在建立的數(shù)據(jù)融合樹中，需要從樹中移走節(jié)點集合R，使得負載較重節(jié)點成為孤立離散節(jié)點集合S(H)，重新選擇其他路徑將孤立節(jié)點再次鏈接到樹中，直到使得節(jié)點負載滿足式(5)。數(shù)據(jù)融合樹生成算法如下

Start:H:Initial an aggregate data tree

Executive:

fori=1 toNdo

Calculate every node’s load:Wi(H)

end for

i=1

whilei≤Ndo

then

The nodeiis removed fromHand

create a set of disconnected componentsS(H),j=1,Li(H)

forj≤Li(H) do

end for

else break;

end if

end while

2.4 最大生命期數(shù)據(jù)融合樹生成算法實現(xiàn)

按照2.3節(jié)融合樹生成算法，在某τ時間開始，網(wǎng)絡(luò)產(chǎn)生一棵以Sink為根的H*樹，樹中節(jié)點均滿足式(5)要求，假設(shè)該樹穩(wěn)定工作時間T1(H*)后，樹中存在不再滿足式(5)要求的節(jié)點，稱該樹的生命期為T1(H*)，也即產(chǎn)生的數(shù)據(jù)流f1=T1(H*)。

定義2： 如果網(wǎng)絡(luò)G存在m棵獨立的H*樹，生命期分別為T1(H*),T2(H*),…,Tm(H*)，那么網(wǎng)絡(luò)的最大流量為fmax=T1(H*)+T2(H*)+…+Tm(H*) ，網(wǎng)絡(luò)的最大生命期為Tmax=fmax。

圖1 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合樹結(jié)構(gòu)調(diào)整模型

當樹結(jié)構(gòu)負載不符合式(5)時，樹結(jié)構(gòu)進行調(diào)整，調(diào)整模型如圖1所示，圖1(a)中，融合樹在工作T1(H*)時間后，出現(xiàn)2個負載過重節(jié)點，節(jié)點i從樹中去除，形成離散孤立節(jié)點集合S(H)={x}，x鏈接到j(luò)后。樹結(jié)構(gòu)調(diào)整到下一個樹結(jié)構(gòu)，網(wǎng)絡(luò)重新在合理負載下運行。

當運行T2(H*)時間后，圖1(b)樹結(jié)構(gòu)出現(xiàn)其它負載過重節(jié)點。節(jié)點k從網(wǎng)絡(luò)中斷開，形成孤立節(jié)點集合S(H)={i,j}，節(jié)點i,j,k可以經(jīng)過3條鏈路鏈接，如圖2(a)所示，圖2(b)為當前鏈接負載過重情形，節(jié)點鏈接經(jīng)過調(diào)整后存在圖2(c),(d)2種情況。經(jīng)過重新調(diào)整后，網(wǎng)絡(luò)到達狀態(tài)如圖1(c)。從圖中可以看出：經(jīng)過調(diào)整后，個別節(jié)點負載過重的部分被轉(zhuǎn)移到其它節(jié)點上，負載在一定程度上得到平衡。

圖2 節(jié)點負載調(diào)整模型

3 仿 真

仿真在NS—2環(huán)境中實現(xiàn)，隨機產(chǎn)生40～120個普通傳感器節(jié)點，節(jié)點隨機分布在100 m×100 m的平面區(qū)域，節(jié)點最大傳輸距離半徑R=15 m，在傳輸距離內(nèi)的任意2個節(jié)點可以互相直接通信，傳感器節(jié)點的初始能量Estart=1 kJ，接收單位數(shù)據(jù)能耗系數(shù)ρ=50 nJ/b，m=4。本文采用高斯隨機場模型作為數(shù)據(jù)相關(guān)模型,其中,參數(shù)α的取值范圍為0.01/m2≤α≤0.01/m2(α越小,數(shù)據(jù)相關(guān)程度越高)。

本文將所提算法ML—MFA(maximum lifetime and maximum flow algorithm)與MEGA和MLR算法進行比較。圖3為3種對比算法中網(wǎng)絡(luò)數(shù)據(jù)流與時間的關(guān)系。節(jié)點數(shù)量分別為40，80，從圖3中可以明顯看出：本文所提算法在數(shù)據(jù)量采集量上明顯優(yōu)于其它2種算法。本文所提算法由于不斷調(diào)整節(jié)點負載，相當于在所有節(jié)點上均衡負載壓力，節(jié)點生命期得到延長，τ的倍數(shù)也最大，MEGA雖然沒有考慮相關(guān)性，數(shù)據(jù)字節(jié)數(shù)會比MLR稍大，但是節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)時，將耗費更多的資源，生命期會小于MLR。

圖3 數(shù)據(jù)流與時間的關(guān)系

圖4顯示了在不同節(jié)點數(shù)量、不同α值情況中網(wǎng)絡(luò)生命期的對比情況。α取值分別為0.001，0.01/m2。從圖4中可以看出:ML—MFA隨著網(wǎng)絡(luò)規(guī)模的增大，網(wǎng)絡(luò)生命期呈現(xiàn)逐漸上升的趨勢，而MEGA和MLR算法的網(wǎng)絡(luò)生命期緩慢下降。這是因為網(wǎng)絡(luò)的數(shù)據(jù)負載與節(jié)點數(shù)量呈正比，節(jié)點數(shù)量越多，產(chǎn)生的數(shù)據(jù)量越大，造成了網(wǎng)絡(luò)整體能耗增加，網(wǎng)絡(luò)生命期下降。但是，節(jié)點數(shù)據(jù)增多使得網(wǎng)絡(luò)節(jié)點密度加大，節(jié)點與鄰居節(jié)點通信能耗下降，同時節(jié)點密度變大后，數(shù)據(jù)相關(guān)性增大，更多的冗余數(shù)據(jù)被清除。

圖4 網(wǎng)絡(luò)生命期

4 結(jié) 論

本文的目標是在實現(xiàn)網(wǎng)絡(luò)最大生命期的同時達到采集數(shù)據(jù)的最大化，根據(jù)能量等限制條件建立線性規(guī)劃模型，考慮到網(wǎng)絡(luò)最大生命期是NP難問題，本文將網(wǎng)絡(luò)最大生命期問題轉(zhuǎn)化為網(wǎng)絡(luò)最小歸一化負載問題，通過重新安排負載較重節(jié)點的鏈路邊集合，調(diào)整負載較重節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)壓力，最終建立一棵最優(yōu)網(wǎng)絡(luò)歸一化負載數(shù)據(jù)融合樹,實現(xiàn)了網(wǎng)絡(luò)生命周期的最大化。仿真實驗對所提路由算法的性能進行了驗證和分析，結(jié)果表明:該算法可以使得網(wǎng)絡(luò)達到網(wǎng)絡(luò)最大數(shù)據(jù)流,并可以有效地提高了網(wǎng)絡(luò)節(jié)點的生命期。

參考文獻:

[1]Xu Ning.On maximum lifetime routing in wireless sensor networks[C]∥IEEE Conference on Decision and Control and 28th Chinese Control Conference, Shanghai, 2009:3757-3762.

[2]Krishnamachari B,Estrin D,Wicker S.The impact of data aggregation in wireless sensor networks[C]∥Proc of the Int’l Conf on Distributed Computing Systems Workshops,Vienna: IEEE Computer Society,2002:575-578.

[3]Rickenbach Von P,Wattenhofer R.Gathering correlated data in sensor networks[C]∥Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC’04:New York, NY, USA:ACM Press, 2004：60-66.

[4]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor network-s[C]∥Proc of the Conf on System Science, Istanbul: IEEE Communications Society,2000: 223-228.

[5]Madan R,Lall S.Distributed algorithms for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Wireless Communications, 2006, 8:2185- 2193.

[6]Liu Z Sankar.Maximum lifetime routing in wireless Ad Hoc networks[C]∥IEEE Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies,INFOCOM 2004: Hongkong,2004:1089-1097.

[7]Padmanabh Kumar.Multicommodity flow based maximum lifetime routing in wireless sensor network[C]∥IEEE Conference on Parallel and Distributed Systems,Minneapolis,MN,US，2006:187-194.

[8]Hua C,Yum T P.Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks[J].IEEE Trans on Networking, 2008, 16(4):892-903.