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

薛 明， 高德民

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003;

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

0 引 言

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

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

1 系統(tǒng)模型

1.1 系統(tǒng)模型

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

1.2 問題描述

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

(1)

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

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é)點(diǎn)i在T時(shí)間內(nèi)發(fā)送給下游節(jié)點(diǎn)的數(shù)據(jù)流總量。

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

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

2.1 算法描述

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

2.2 節(jié)點(diǎn)負(fù)載量化模型

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

亦即

(3)

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

(4)

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

定義滿足式(5)的節(jié)點(diǎn)為負(fù)載合理節(jié)點(diǎn)

(5)

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

在建立的數(shù)據(jù)融合樹中，需要從樹中移走節(jié)點(diǎn)集合R，使得負(fù)載較重節(jié)點(diǎn)成為孤立離散節(jié)點(diǎn)集合S(H)，重新選擇其他路徑將孤立節(jié)點(diǎn)再次鏈接到樹中，直到使得節(jié)點(diǎn)負(fù)載滿足式(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ù)融合樹生成算法實(shí)現(xiàn)

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

定義2： 如果網(wǎng)絡(luò)G存在m棵獨(dú)立的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)整模型

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

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

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

3 仿 真

仿真在NS—2環(huán)境中實(shí)現(xiàn)，隨機(jī)產(chǎn)生40～120個(gè)普通傳感器節(jié)點(diǎn)，節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的平面區(qū)域，節(jié)點(diǎn)最大傳輸距離半徑R=15 m，在傳輸距離內(nèi)的任意2個(gè)節(jié)點(diǎn)可以互相直接通信，傳感器節(jié)點(diǎn)的初始能量Estart=1 kJ，接收單位數(shù)據(jù)能耗系數(shù)ρ=50 nJ/b，m=4。本文采用高斯隨機(jī)場模型作為數(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算法進(jìn)行比較。圖3為3種對比算法中網(wǎng)絡(luò)數(shù)據(jù)流與時(shí)間的關(guān)系。節(jié)點(diǎn)數(shù)量分別為40，80，從圖3中可以明顯看出：本文所提算法在數(shù)據(jù)量采集量上明顯優(yōu)于其它2種算法。本文所提算法由于不斷調(diào)整節(jié)點(diǎn)負(fù)載，相當(dāng)于在所有節(jié)點(diǎn)上均衡負(fù)載壓力，節(jié)點(diǎn)生命期得到延長，τ的倍數(shù)也最大，MEGA雖然沒有考慮相關(guān)性，數(shù)據(jù)字節(jié)數(shù)會比MLR稍大，但是節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，將耗費(fèi)更多的資源，生命期會小于MLR。

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

圖4顯示了在不同節(jié)點(diǎn)數(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ò)生命期緩慢下降。這是因?yàn)榫W(wǎng)絡(luò)的數(shù)據(jù)負(fù)載與節(jié)點(diǎn)數(shù)量呈正比，節(jié)點(diǎn)數(shù)量越多，產(chǎn)生的數(shù)據(jù)量越大，造成了網(wǎng)絡(luò)整體能耗增加，網(wǎng)絡(luò)生命期下降。但是，節(jié)點(diǎn)數(shù)據(jù)增多使得網(wǎng)絡(luò)節(jié)點(diǎn)密度加大，節(jié)點(diǎn)與鄰居節(jié)點(diǎn)通信能耗下降，同時(shí)節(jié)點(diǎn)密度變大后，數(shù)據(jù)相關(guān)性增大，更多的冗余數(shù)據(jù)被清除。

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

4 結(jié) 論

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

參考文獻(xiàn):

[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.