基于空間信息與梯度的WSN分簇路由算法

廖惜春，楊志高，任敬哲

(五邑大學信息與通信工程學院，廣東江門529020)

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)是物聯(lián)網(wǎng)應用系統(tǒng)中的關(guān)鍵技術(shù)之一。它由部署在監(jiān)測區(qū)域內(nèi)大量的傳感器節(jié)點組成，所有節(jié)點采用能量同構(gòu)、具有一定計算能力的模塊組成，采集環(huán)境中的數(shù)據(jù)，并通過無線的方式將信息傳播給Sink節(jié)點。最早提出的分簇路由算法是LEACH(Low－Energy Adaptive Clustering Hierarchy)［1］。

經(jīng)過國內(nèi)外研究人員多年的努力，已經(jīng)在LEACH算法的基礎(chǔ)上做出了多種路由改進算法。文獻［2］提出了一種由節(jié)點剩余能量與睡眠控制的改進算法，該算法通過在網(wǎng)絡成簇階段降低能量低的節(jié)點被選為簇頭的概率，在穩(wěn)定階段使簇頭盡可能多地保持睡眠狀態(tài)，從而降低網(wǎng)絡能耗。但是該算法對于網(wǎng)絡聲明周期的延長不太明顯。文獻［3］中針對熱區(qū)問題進行改進，提出一種非均勻的分簇方式，即離Sink節(jié)點近的簇不斷縮小，該算法可均衡網(wǎng)絡能耗，但算法過于復雜，控制開銷大。文獻［4］中提出一種雙簇頭的路由算法，算法主要由主簇頭收集簇內(nèi)成員信息，再將數(shù)據(jù)發(fā)送給副簇頭，待數(shù)據(jù)融合后將數(shù)據(jù)傳給Sink節(jié)點，此算法將接收與融合的步驟分開，避免了單個簇頭大信息量傳輸?shù)呢摀?，但?shù)據(jù)從主簇頭到副簇頭的傳輸，造成額外的耗能較大。文獻［5］提出了一種節(jié)點定位的雙Sink節(jié)點算法，算法有效地提高了網(wǎng)絡的性能，延長了整個網(wǎng)絡的生命周期。但是該算法使用的雙Sink節(jié)點，加大了網(wǎng)絡的硬件開銷，且需實現(xiàn)網(wǎng)絡粗定位，增加了算法的復雜度。最主要的是該算法的檢測區(qū)域限于正方形區(qū)域，實用性較低。

綜上所述，LEACH分簇算法目前仍然需要廣大學者做出相應的研究與改進。本文在研究和分析LEACH算法以及后續(xù)研究人員的改進算法的基礎(chǔ)上提出了基于空間信息與梯度的WSN分簇路由算法。

1 LEACH算法

1.1 LEACH算法的原理

LEACH分層路由算法的目的是最小化網(wǎng)絡能耗［3］。該算法通過隨機選擇簇頭節(jié)點收集網(wǎng)絡中的數(shù)據(jù)信息，從而使節(jié)點平均分擔網(wǎng)絡中數(shù)據(jù)傳輸和能量消耗，延長網(wǎng)絡的生命周期，其網(wǎng)絡拓撲結(jié)構(gòu)如圖1所示。

LEACH算法分為準備階段和數(shù)據(jù)傳輸階段，這兩個階段構(gòu)成一個輪回。在準備階段，檢測區(qū)域中節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)，并將這個隨機數(shù)同每輪的閾值T(n)作比較，如果節(jié)點產(chǎn)生的隨機數(shù)小于此閾值T(n)，該節(jié)點就被選為簇頭。閾值的大小為

圖1 LEACH算法網(wǎng)絡拓撲結(jié)構(gòu)

式中:p是檢測區(qū)域中簇頭所占的比例;r是指當前網(wǎng)絡進行簇頭選舉的輪數(shù);G是指在本輪之前的1/p輪中沒有被選為簇頭的節(jié)點集合;mod是求模運算符號。這樣就保證了監(jiān)測區(qū)域中所有節(jié)點都有當選簇頭的機會。簇頭節(jié)點選定后，簇頭節(jié)點全網(wǎng)廣播，告知網(wǎng)絡中其他節(jié)點此消息。網(wǎng)絡中的非簇頭節(jié)點根據(jù)接收到信息的信號強度來加入最近的簇頭組成簇。

在數(shù)據(jù)傳輸階段，簇頭節(jié)點采用TDMA方式，為簇內(nèi)的節(jié)點分配時隙，簇內(nèi)節(jié)點在時隙到來時，向簇頭發(fā)送數(shù)據(jù)消息。簇頭節(jié)點將收到的數(shù)據(jù)進行融合后，再傳輸給Sink匯聚節(jié)點。一段時間后，網(wǎng)絡就進入下一輪的簇重構(gòu)過程，不斷地循環(huán)，直到網(wǎng)絡中的所有節(jié)點能量耗盡。

1.2 LEACH算法的不足

1.2.1 簇頭分布不均勻

采用LEACH算法產(chǎn)生的簇頭如圖2所示。圖中“○”表示普通節(jié)點，“⊙”表示簇頭節(jié)點，“×”表示Sink節(jié)點。監(jiān)測區(qū)域中簇頭分布明顯不均勻。

圖2 LEACH算法產(chǎn)生的簇頭

1.2.2 簇間能量負載不均衡

從圖2中可見，由于簇頭分布不均勻，對擁有較多節(jié)點數(shù)的簇頭，收發(fā)數(shù)據(jù)的能耗相對較大;而對于擁有較少節(jié)點數(shù)的簇頭，數(shù)據(jù)傳輸過程中，能耗相對較少。可見，由于簇間能量負載不均衡，導致部分簇頭過早消亡。

1.2.3 監(jiān)測區(qū)域受限

由于LEACH算法的條件是:假定監(jiān)測區(qū)域所有的節(jié)點都能與Sink匯聚節(jié)點直接通信。所以該算法難以應用于大規(guī)模網(wǎng)絡。

以上所提及的LEACH算法存在的不足之處，是影響網(wǎng)絡生命周期以及簇間負載均衡的主要原因。為了行之有效地解決上述問題，本文研究了一種基于空間信息和梯度的分簇路由算法。

2 基于空間信息和梯度的分簇路由算法

2.1 系統(tǒng)描述

2.1.1 網(wǎng)絡模型

傳感器網(wǎng)絡中的節(jié)點隨機部署在一個N×N的正方形區(qū)域內(nèi)，節(jié)點周期性地采集區(qū)域內(nèi)的信息。同時對無線傳感器網(wǎng)絡作如下假設(shè):

1)傳感器網(wǎng)絡中有固定的Sink節(jié)點，能量不受限制;

2)所有節(jié)點同構(gòu)，具有相同的初始能量和有限的能源;

3)節(jié)點處于靜止態(tài)，等待發(fā)送信息;

4)節(jié)點能感知自身能量，并且可根據(jù)接收者的距離改變數(shù)據(jù)發(fā)送的功率;

5)節(jié)點可以根據(jù)接收的信號強度，計算與發(fā)射節(jié)點之間的距離。

2.1.2 能量模型

本文采用無線傳感器網(wǎng)絡中常用的一階無線通信模型［3］。根據(jù)網(wǎng)絡的實際情況，模型給出了節(jié)點間的距離閾值d0，d0的大小為

當發(fā)送節(jié)點到目標節(jié)點間的距離d＜d0時，采用自由空間模型;當d≥d0時，則采用多徑衰落模型。

節(jié)點i向節(jié)點j發(fā)送kbit數(shù)據(jù)的能耗為

而節(jié)點j接收節(jié)點i發(fā)送的kbit數(shù)據(jù)能耗為

式中:Eelec代表無線收發(fā)電路的能耗;Eamp代表放大器消耗的能量;εfs和εmp分別為兩種模型中功率放大所消耗的能量。

2.2 改進算法描述

2.2.1 相關(guān)定義

1)節(jié)點的空間信息:在傳感器網(wǎng)絡中，節(jié)點根據(jù)RSSI確定節(jié)點自身到鄰近節(jié)點以及Sink節(jié)點的距離，將此距離作為節(jié)點的空間信息。

2)梯度:Sink節(jié)點廣播消息在網(wǎng)絡傳遞中，記錄經(jīng)歷的跳數(shù)，每個節(jié)點獲得自身到Sink節(jié)點的最少跳數(shù)，稱之為高度，而節(jié)點自身與鄰居節(jié)點之間的高度差就定義為梯度。當數(shù)據(jù)沿著梯度最大鏈路給Sink節(jié)點發(fā)送數(shù)據(jù)時，就選擇最小跳數(shù)，即節(jié)點沿最短路徑進行數(shù)據(jù)傳遞［4］。

3)能耗最優(yōu)簇原則:根據(jù)簇內(nèi)成員和簇的數(shù)量以及能耗關(guān)系，簇頭所占檢測區(qū)域總節(jié)點數(shù)為5%時，傳感器網(wǎng)絡的能耗最優(yōu)［5］。也就是說簇內(nèi)成員數(shù)和簇頭數(shù)的比值是19∶1。每個簇內(nèi)成員最大數(shù)是Nmax=19(1+α)，其中α∈［0，1］。本文假設(shè)在α =0.5時，能夠保證簇內(nèi)節(jié)點數(shù)的整體分布是均勻的，Nmax取30。簇內(nèi)成員最小數(shù)目是Nmin=19(1－ β)，β∈［0，1］。本文假設(shè)β =0.8時，能夠滿足全網(wǎng)簇頭節(jié)點能耗均衡，則Nmin取4。簇內(nèi)節(jié)點數(shù)滿足以上閾值時，將形成的簇稱為能耗最優(yōu)簇。

2.2.2 算法實現(xiàn)

1)網(wǎng)絡初始化階段

將Sink節(jié)點的梯度G(n0)和空間信息P(n0)初始化為0，其余節(jié)點的梯度和空間信息P(ni)初始化為無窮。從Sink匯聚節(jié)點開始向鄰居節(jié)點廣播自己的梯度值以及空間信息:在廣播過程中，當節(jié)點i收到節(jié)點j廣播梯度和空間信息的消息時，節(jié)點i首先檢查自身的鄰居表中是否已經(jīng)有了節(jié)點j的信息:若沒有，則將節(jié)點j加入到節(jié)點i的鄰居表NT(ni)，鄰居表也同時保存鄰居節(jié)點的梯度信息;若已經(jīng)有了節(jié)點j的信息，則更新節(jié)點j的梯度。當節(jié)點i收到節(jié)點j發(fā)送的信號時，節(jié)點i根據(jù)收到信號的強度來確定節(jié)點j到自身的距離，將信息設(shè)置為某一具體的值P(ni)，并將這個值存儲在節(jié)點i的空間信息表中;如此類推，直到網(wǎng)絡中的所有節(jié)點都獲得梯度和空間信息。P(ni)表達式為

式中:xm和ym分別是監(jiān)測區(qū)域的長度和寬度;dBi是指節(jié)點i接收到Sink節(jié)點發(fā)出廣播信號時的強度;f是指節(jié)點i將此信號強度值轉(zhuǎn)換為與空間距離同等數(shù)量級的函數(shù)。

2)簇頭選舉

本文的簇頭選舉采用與LEACH類似的概念“輪”。網(wǎng)絡初始化完畢后，監(jiān)控區(qū)域的所有傳感器節(jié)點，在每輪開始時，根據(jù)

生成初始值。將這個值代入

生成一個d－c+1個元素的數(shù)組，并將自己的空間信息P(ni)與此數(shù)組中的值作比較，相等的節(jié)點標記為候選簇頭。

式(6)和式(7)中的參數(shù)根據(jù)網(wǎng)絡監(jiān)控區(qū)域的大小、形狀、節(jié)點數(shù)量設(shè)置。本文中取d11=30，f=1，e=30，c=1，d=4，r代表當前輪數(shù)，mod是求余運算。式(6)中，當di1=d11+e－1時，就將di1的值重新賦為d11。

候選簇頭節(jié)點向鄰居節(jié)點廣播自己成為候選節(jié)點的信息。相鄰的候選簇頭比較梯度信息以及剩余能量值，候選簇頭當選簇頭的概率為

式中:pi是候選簇頭節(jié)點i當選簇頭的概率;G(ni)和E(ni)分別指候選簇頭的梯度信息值和剩余能量值;a和b根據(jù)具體的網(wǎng)絡環(huán)境來設(shè)置不同的值;φ是調(diào)節(jié)梯度在簇頭選舉中的比重;φ調(diào)節(jié)節(jié)點剩余能量在簇頭選舉中占的比重。相鄰的候選簇頭重復進行此淘汰過程，直到網(wǎng)絡中的候選簇頭數(shù)目等于能耗最優(yōu)簇原則要求的簇頭數(shù)目，或者候選簇頭的鄰居節(jié)點里沒有候選簇頭為止。剩下的候選簇頭節(jié)點選為簇頭。

3)簇的規(guī)?？刂?/p>

為了實現(xiàn)簇規(guī)模的控制，本文采用分簇規(guī)模約束機制。根據(jù)能耗最優(yōu)簇原則，控制每個簇的規(guī)模。將簇的大小控制在Nmax和Nmin之間。當簇內(nèi)節(jié)點數(shù)大于Nmax時，有節(jié)點要申請加入簇頭時，簇頭就發(fā)出拒絕消息，節(jié)點收到拒絕消息后，就尋找能量強度次弱的簇頭重新申請加入，以此類推。如果簇內(nèi)節(jié)點數(shù)目小于值Nmin，將放棄這個簇，這個簇內(nèi)的節(jié)點選擇能量次弱的簇頭加入，此時，簇頭不考慮最大數(shù)目限制，由于放棄的簇內(nèi)節(jié)點并不多，所以對其他簇的影響不大。

4)數(shù)據(jù)傳輸階段

簇內(nèi)通信方式采用TDMA的方式，簇頭給每個簇內(nèi)節(jié)點分配一個時隙，簇內(nèi)節(jié)點在時隙到來時，發(fā)信息給簇頭，其余時間處于休眠狀態(tài)，降低能耗。簇內(nèi)節(jié)點在向簇頭節(jié)點發(fā)送數(shù)據(jù)之前，先判斷通信距離，如果通信距離大于d0，就采取多跳通信的方式，將信息沿簇內(nèi)梯度最大的方向傳輸。否則采用單跳傳輸信息給簇頭。對于某些到Sink節(jié)點的距離小于或等于到簇頭距離的特殊節(jié)點，則選擇直接傳輸數(shù)據(jù)給Sink節(jié)點。

3 仿真結(jié)果分析

設(shè)定檢測區(qū)的范圍是200 m×200 m的正方形區(qū)域，隨機播撒200個節(jié)點，并且將Sink節(jié)點設(shè)置在監(jiān)控區(qū)域的中心，坐標為(100，100)。監(jiān)測區(qū)域節(jié)點能量值初始化為0.5 J，Eelec設(shè)為50 nJ/bit，數(shù)據(jù)融合消耗能量EEDA設(shè)為5 nJ/(bit·signal)，兩種模型中的功率放大能耗根據(jù)距離和環(huán)境因素設(shè)置εfs為10 pJ/(bit·m2)，εmp為0.001 3 pJ/(bit·m4)，數(shù)據(jù)包的長度L設(shè)置為4 000 bit。參數(shù) α，β，a，b，φ，φ 分別設(shè)置為 0.5，0.8，0.5，0.5，0.01，0.5。下文分別對LEACH算法、文獻［5］算法以及本文的算法進行了仿真。

圖3和圖4中，虛點線、虛劃線、細實線、點劃線分別代表LEACH算法、文獻［5］單Sink算法、本文改進算法、文獻［5］雙Sink算法各自的仿真結(jié)果。圖3是每輪的存活節(jié)點數(shù)目，圖4是每輪簇頭數(shù)目。

圖3 各算法每輪存活節(jié)點數(shù)

圖4 各算法每輪簇頭的數(shù)目

圖3中可以看出LEACH算法在第286輪的時候，網(wǎng)絡中出現(xiàn)第1個消亡節(jié)點，在1 507輪的時候，整個網(wǎng)絡中節(jié)點全部消亡;文獻［5］算法，在監(jiān)測區(qū)域含有單個Sink節(jié)點和兩個Sink節(jié)點情況時進行仿真，結(jié)果表明:在監(jiān)測區(qū)域含有單個Sink節(jié)點時，網(wǎng)絡中第1個消亡節(jié)點是在350輪左右出現(xiàn)，較LEACH算法有一定的提高;在網(wǎng)絡中含有2個Sink節(jié)點時，第1個消亡節(jié)點在640輪左右出現(xiàn)，雖然延長了網(wǎng)絡的壽命，但是網(wǎng)絡的硬件成本較高。本文改進后的算法中，網(wǎng)絡出現(xiàn)第1個消亡節(jié)點是在560輪左右，直到2 550輪左右節(jié)點才全部消亡。

由于每次實驗節(jié)點分布是隨機生成的，所以本文進行多次仿真，結(jié)果表明:LEACH算法出現(xiàn)第1個消亡節(jié)點大都是在280輪左右。而在第1 500輪左右，網(wǎng)絡中節(jié)點能量全部耗盡;采用文獻［5］算法的雙Sink節(jié)點仿真，第1個消亡節(jié)點在640輪出現(xiàn);采用本文改進的算法仿真時，第1個消亡節(jié)點出現(xiàn)的時間是在550輪左右，全部節(jié)點能量耗盡的時間大約在第2 500輪。

在無線傳感器網(wǎng)絡中，每增加一個信標節(jié)點，網(wǎng)絡的硬件成本將提高10%。文獻［5］通過雙Sink節(jié)點和ABC算法獲取區(qū)域中所有節(jié)點坐標，雖然提高了網(wǎng)絡性能，但是網(wǎng)絡的硬件成本卻增加了。雖然本文中的第1個消亡節(jié)點出現(xiàn)的輪數(shù)較文獻［5］中的雙Sink節(jié)點算法較早，但是本文提出的算法無需額外的硬件成本，算法較簡單。且文獻［5］提出的算法限于在正方形網(wǎng)絡中使用，需要借助多種算法進行資源分配。而在實際應用中傳感器網(wǎng)絡布置區(qū)域很少有此規(guī)則。因此本文算法較文獻［5］算法有更高的實用性。

同時，本文又對兩種算法在不同檢測區(qū)域進行多次仿真求均值的方法，驗證兩種算法的有效性。

表1 LEACH算法仿真結(jié)果列表

表2 改進算法仿真結(jié)果列表

表1和表2分別是采用LEACH算法和本文改進算法，在形狀不同、面積近似相等的的檢測區(qū)域，進行20輪仿真求平均值后的結(jié)果。

由表1看出，LEACH算法在不同的檢測區(qū)域的仿真結(jié)果相近;出現(xiàn)第1個消亡節(jié)點的輪數(shù)大約為279輪，在1 493輪后，網(wǎng)絡中的節(jié)點全部消亡。由表2看出，改進后的算法在圓形區(qū)域和正方形區(qū)域的網(wǎng)絡性能明顯優(yōu)于橢圓形區(qū)域和長方形區(qū)域，但是算法結(jié)果所受監(jiān)測區(qū)域的形狀影響較小。綜上所述:改進后的算法較LEACH算法以及文獻［5］算法有一定的提高且實用性更好。

4 結(jié)束語

本文針對LEACH算法的簇頭選舉不均勻，導致網(wǎng)絡能耗不均衡，部分節(jié)點過早死亡，從而使網(wǎng)絡性能降低等不足方面進行相應改進，提出了將節(jié)點空間信息與梯度、節(jié)點剩余能量等因素綜合考慮到簇頭選舉中，使簇頭分布更加均勻。在網(wǎng)絡分簇階段又對簇的大小進行限制和調(diào)整，使得網(wǎng)絡的能耗更加均衡。并在數(shù)據(jù)傳輸階段采用先判斷再傳輸?shù)姆椒ǎ瑢崿F(xiàn)了數(shù)據(jù)傳輸中根據(jù)傳輸?shù)木嚯x而采用多跳或單跳通信的方式，增強了數(shù)據(jù)傳輸?shù)闹悄苄?，改善了LEACH算法中節(jié)點由于通信距離遠，造成能耗大的問題，不僅節(jié)約了能量，而且實現(xiàn)了長距離的多跳通信。從而使算法能夠應用于大面積檢測區(qū)域，克服了LEACH算法在這一點上的不足。且對文獻中部分算法進行仿真，結(jié)果表明本文算法具有更高的實用價值。

［1］ HEINZELMANW，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wirelessmicro sensor networks［C］//Proc.the33rd AnnualHawaii InternationalConferenceon System Sciences.Maui:IEEE Press，2000:3005－3014.

［2］韓媛萍.基于剩余能量和睡眠控制的改進LEACH算法［J］.現(xiàn)代電子技術(shù)，2012，35(22):97－100.

［3］吳振華，尹志軍.基于優(yōu)化簇半徑的WSNs分均勻分簇路由［J］.計算機工程與設(shè)計，2010，31(15):3374－3378.

［4］李輝，李臘元，李方云.一種基于低能量的雙簇首WSN路由算法［J］.武漢理工大學學報，2009，33(3):450－453.

［5］ 鄒虹，彭國龍.一種基于LEACH改進的均勻分簇路由算法［J］.電視技術(shù)，2013，37(3):133－140.