一種能量均衡化分層式分簇單跳和多跳混合的WSN路由算法研究

史振興，范秀娟，姜 瑩，趙 婧

(1. 北京服裝學(xué)院，北京 100029；2. 北京交通大學(xué)，北京 100044)

0 引言

現(xiàn)在大部分無線傳感器網(wǎng)路路由算法都是從能量消耗的角度來進(jìn)行研究的。在多數(shù)多跳路由算法中，大量節(jié)點(diǎn)所采集的數(shù)據(jù)通過多跳的方式流向少數(shù)基站，會造成距離基站較近的節(jié)點(diǎn)較早的“死亡”，并且由于節(jié)點(diǎn)分布不均勻，也會導(dǎo)致一些節(jié)點(diǎn)由于轉(zhuǎn)發(fā)數(shù)據(jù)次數(shù)過多而過早的“死亡”。同樣，在一些單跳分簇算法中，由于簇頭融合數(shù)據(jù)之后直接與基站進(jìn)行通信，在小范圍內(nèi)能保證大部分簇頭和節(jié)點(diǎn)間的通信滿足自由空間模型。當(dāng)范圍變大時，由于簇頭節(jié)點(diǎn)間單次通信的能耗差別變得很大，造成距離基站較遠(yuǎn)的節(jié)點(diǎn)過早的“死亡”同樣影響網(wǎng)絡(luò)的性能[1,2]。

在無線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)通信是系統(tǒng)最重要的操作之一，并占用很大一部分的能量消耗。事實(shí)上，在傳感器網(wǎng)絡(luò)中數(shù)據(jù)通信需要的能量遠(yuǎn)大于數(shù)據(jù)處理所需要的能量[3]。通過對各種無線傳感器網(wǎng)絡(luò)路由算法的研究，本文提出一種能量均衡化分層式分簇單跳+多跳路由算法（LEACH_C），引入了平均能量因素。該路由算法分為兩級結(jié)構(gòu)，底層為傳感器數(shù)據(jù)采集網(wǎng)絡(luò)，上層為數(shù)據(jù)融合轉(zhuǎn)發(fā)網(wǎng)絡(luò)。網(wǎng)絡(luò)簇頭分級結(jié)構(gòu)如圖1所示。

圖1 分級式網(wǎng)絡(luò)簇頭結(jié)構(gòu)

1 無線通信能量消耗模型

本文采用如圖2所示的一種無線通信能量消耗模型。節(jié)點(diǎn)發(fā)送K比特的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路的損耗和發(fā)射部分的功率放大器的損耗，即：

其中Eelect表示發(fā)射電路的功耗，當(dāng)節(jié)點(diǎn)于節(jié)點(diǎn)之間傳輸數(shù)據(jù)時，若傳輸距離小于閥值d0時，采用自由空間傳輸模型；若傳輸距離大于d0時，采用多路徑衰減傳輸模型。εfs、εmp分別為兩種數(shù)據(jù)傳輸模型中發(fā)射數(shù)據(jù)時功率放大器的功耗。

圖2 無線通信能量消耗模型

由式（1）可以看出，在傳感器節(jié)點(diǎn)之間進(jìn)行無線通信時，各節(jié)點(diǎn)之間的距離d是影響網(wǎng)絡(luò)通信能耗的最主要的因素。

2 LEACH_C算法能耗模型分析

LEACH_C算法根據(jù)無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)把網(wǎng)絡(luò)分成兩個層次，傳感器節(jié)點(diǎn)到路由轉(zhuǎn)發(fā)節(jié)點(diǎn)和路由轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站。傳感器節(jié)點(diǎn)到路由轉(zhuǎn)發(fā)節(jié)點(diǎn)作為底層數(shù)據(jù)采集網(wǎng)絡(luò)，主要負(fù)責(zé)采集融合各個傳感器節(jié)點(diǎn)收集到的信息；路由轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站為上層網(wǎng)絡(luò)，負(fù)責(zé)把底層網(wǎng)絡(luò)收集到的信息轉(zhuǎn)發(fā)到基站，該過程由于信息量比較大，轉(zhuǎn)發(fā)次數(shù)比較多，因此該層網(wǎng)絡(luò)能量消耗占整個網(wǎng)絡(luò)能耗的比重比較大。

2.1 傳感器節(jié)點(diǎn)到路由節(jié)點(diǎn)

傳感器節(jié)點(diǎn)到路由節(jié)點(diǎn)作為底層網(wǎng)絡(luò)負(fù)責(zé)把傳感器采集到的數(shù)據(jù)集中到路由設(shè)備。由于該層網(wǎng)絡(luò)負(fù)責(zé)采集融合各傳感器收集到的信息，且分布比較均勻，各節(jié)點(diǎn)之間的距離也比較小，因此底層網(wǎng)絡(luò)采用單跳固定分簇路由算法。路由轉(zhuǎn)發(fā)節(jié)點(diǎn)作為底層網(wǎng)絡(luò)的簇頭，負(fù)責(zé)融合數(shù)據(jù)并轉(zhuǎn)發(fā)到上層網(wǎng)絡(luò)，各傳感器采集節(jié)點(diǎn)通過單跳的方式把采集到的數(shù)據(jù)直接發(fā)送到路由轉(zhuǎn)發(fā)節(jié)點(diǎn)。假設(shè)該簇的傳感器節(jié)點(diǎn)的個數(shù)為i，則底層網(wǎng)絡(luò)的一輪數(shù)據(jù)傳輸?shù)哪芰肯臑椋?/p>

其中ETX，ERX分別為單個節(jié)點(diǎn)發(fā)送和接收k比特數(shù)據(jù)消耗的能量。d為各傳感器到路由節(jié)點(diǎn)的平均距離。由于底層網(wǎng)絡(luò)各節(jié)點(diǎn)之間的距離比較小，因此采用自由空間傳輸模型，ETX，ERX分別為：

把式（3）帶入到式（2）中，則底層網(wǎng)絡(luò)一輪數(shù)據(jù)傳輸?shù)哪芎臑椋?/p>

2.2 路由節(jié)點(diǎn)到基站

路由節(jié)點(diǎn)到基站作為上層網(wǎng)絡(luò)負(fù)責(zé)把采集到的數(shù)據(jù)轉(zhuǎn)發(fā)到基站，由于路由節(jié)點(diǎn)的位置的不確定性，也就是各路由節(jié)點(diǎn)間的距離d隨機(jī)性比較大，若簡單的采用單跳分簇路由算法，當(dāng)網(wǎng)絡(luò)范圍變大時，遠(yuǎn)離基站的節(jié)點(diǎn)能量消耗變大，并且各簇頭之間單次通信的能量消耗差別也會變大。其他LEACH相關(guān)多跳算法中，由于每個簇成員個數(shù)不同就造成網(wǎng)絡(luò)中能量消耗不均勻，并且各簇頭與基站進(jìn)行通信時，也沒有限制多跳的次數(shù)，這就使得基站周圍的簇頭由于參與較多的數(shù)據(jù)轉(zhuǎn)發(fā)而能量消耗過快，存在嚴(yán)重的“熱點(diǎn)問題”。

綜合以上各種問題，LEACH_C算法中采用不定長幀間隔的方式，讓簇成員比較少的簇內(nèi)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的間隔增大，反之，簇成員比較多的簇向基站發(fā)送數(shù)據(jù)的間隔減小，這樣在相同的時間內(nèi)，網(wǎng)絡(luò)中大小不同的簇向基站發(fā)送數(shù)據(jù)的次數(shù)就基本一致，很好的解決了網(wǎng)絡(luò)中能耗不均的問題。同時，LEACH_C算法根據(jù)簇節(jié)點(diǎn)距離基站的距離d以及自己的平均剩余能量E(i)residual來決定該區(qū)域內(nèi)的最優(yōu)轉(zhuǎn)發(fā)跳數(shù)，并且在選擇下一跳路由時，充分考慮到路由節(jié)點(diǎn)的剩余能量狀況，這樣不僅均衡了全網(wǎng)的能量，同時也減少“熱點(diǎn)問題”對網(wǎng)絡(luò)生命周期的影響。

LEACH_C算法中最重要的是各路由轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳次數(shù)的確定，不僅要考慮到各路由節(jié)點(diǎn)簇中簇頭和簇內(nèi)節(jié)點(diǎn)的平均剩余能量，同時還要考慮各路由節(jié)點(diǎn)到基站的距離。現(xiàn)在我們假設(shè)有N個路由節(jié)點(diǎn)隨機(jī)分配在半徑為R的一個區(qū)域內(nèi)，基站位于該區(qū)域的中心，根據(jù)路由節(jié)點(diǎn)到基站的距離遠(yuǎn)近把節(jié)點(diǎn)分成不同的區(qū)域，分別為r1，r2，r3，.....rn，如圖3所示。

圖3 節(jié)點(diǎn)分布區(qū)域劃分

假設(shè)在區(qū)域R中有M個簇頭，平均分布在整個區(qū)域中，位于rn區(qū)域的簇頭節(jié)點(diǎn)和基站的通信需要rn-1區(qū)域內(nèi)的簇頭節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，并且每次通信的距離都在自由衰減通信模型的范圍d0內(nèi)。為了便于研究，假設(shè)每個簇頭節(jié)點(diǎn)都位于各自區(qū)域的中部，并且每個區(qū)域的環(huán)寬度都是r，即r1區(qū)域的簇頭處于r/2處，r2區(qū)域的簇頭位于3r/2處，r2區(qū)域的簇頭與基站進(jìn)行通信時時通過r1區(qū)域的簇頭進(jìn)行轉(zhuǎn)發(fā)的，以此類推，則當(dāng)處于rj區(qū)域的簇頭向基站發(fā)送k bit數(shù)據(jù)時，網(wǎng)絡(luò)中單個簇頭節(jié)點(diǎn)的能耗為：

其中l(wèi)是區(qū)域rj內(nèi)簇頭與基站通信時經(jīng)過的跳數(shù)，則經(jīng)過一輪數(shù)據(jù)傳輸網(wǎng)絡(luò)的整體能量消耗為：

把式(4)，(5)代入式(6)中有：

因此最優(yōu)跳數(shù)即為使式(7)取得最小值時l的值，這樣就可以通過對Eall求關(guān)于l的導(dǎo)數(shù)來得出：

由式(8)可得：

由式(9)可知，當(dāng)(i-1/2)r小于d0時，也就是路由轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站的距離處于自由衰減模型范圍內(nèi)時，采用單跳的方式進(jìn)行數(shù)據(jù)傳輸，反之，則采用多跳的傳輸方式進(jìn)行數(shù)據(jù)傳輸，多跳的次數(shù)通過式(9)可以得出。這樣，上層網(wǎng)絡(luò)的整體能量消耗就達(dá)到了最小狀態(tài)，但是一些“熱點(diǎn)問題”還是沒有得到很好的解決。

2.3 剩余能量均衡化

由以上分析可知，單跳+多跳的路由方式雖然使整個網(wǎng)絡(luò)的能耗降到了最低狀態(tài)，可是還是存在一定的“熱點(diǎn)問題”會導(dǎo)致某些路由節(jié)點(diǎn)過早的“死亡”。LEACH_C算法中引入了節(jié)點(diǎn)剩余能量的因素，即每個路由節(jié)點(diǎn)在向基站進(jìn)行通信時，把自身剩余能量同樣發(fā)送給基站，由基站進(jìn)行分析統(tǒng)計出剩余能量比較大的路由節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)或者作為多跳路由的中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。

假設(shè)每個路由轉(zhuǎn)發(fā)節(jié)點(diǎn)的初始能量為E0，則一輪數(shù)據(jù)傳輸結(jié)束之后，每個節(jié)點(diǎn)的剩余能量為：

其中m，n分別為節(jié)點(diǎn)i接收和發(fā)送k比特數(shù)據(jù)次數(shù)。每個路由轉(zhuǎn)發(fā)節(jié)點(diǎn)在最后一次發(fā)送數(shù)據(jù)時根據(jù)式(10)計算出自己的剩余能量Ei，和數(shù)據(jù)一起發(fā)送出去，基站接收到各個節(jié)點(diǎn)的能量信息之后進(jìn)行分析，統(tǒng)計出各個區(qū)域內(nèi)Ei的最大值，然后根據(jù)LEACH_C路由算法對各區(qū)域廣播信息。這就很好的解決了一些轉(zhuǎn)發(fā)節(jié)點(diǎn)的受到“熱點(diǎn)問題”的影響而過早死亡的問題。

3 LEACH_C算法仿真

如圖4所示，通過MATLAB進(jìn)行LEACH_C算法的仿真，并同LEACH以及DEEC算法從網(wǎng)絡(luò)生命周期以及數(shù)據(jù)傳輸數(shù)量上進(jìn)行了比較。仿真場景為100*100的環(huán)境中，基站位于（50,50），節(jié)點(diǎn)個數(shù)為100個。通過時間周期輪數(shù)和死亡的節(jié)點(diǎn)數(shù)量來描述網(wǎng)絡(luò)的生命周期。圖4顯示了LEACH_C算法和LEACH算法網(wǎng)絡(luò)生命周期的對比。

圖4 LEACH_C算法和LEACH算法生命周期比較

同樣，把LEACH_C算法和DEEC算法也進(jìn)行比較，如圖5所示。

圖5 LEACH_C算法和DEEC算法生命周期比較

由圖4，圖5可以看出，LEACH_C算法生命周期明顯優(yōu)于LEACH算法和DEEC算法。其第一個死亡節(jié)點(diǎn)出現(xiàn)在800輪數(shù)據(jù)傳輸之后，說明整個網(wǎng)絡(luò)的能量均衡性能取得了比較理想的效果。LEACH_C算法仿真到1200輪左右時，其死亡節(jié)點(diǎn)分布如圖6所示。其中紅色節(jié)點(diǎn)表示死亡的節(jié)點(diǎn)，由圖中可以看到死亡節(jié)點(diǎn)的分布還是比較均勻的，并沒有出現(xiàn)死亡節(jié)點(diǎn)扎堆的情況，這就說明LEACH_C算法對“熱點(diǎn)問題”的解決也是比較理想的。

圖6 LEACH_C算法仿真1200輪左右死亡節(jié)點(diǎn)的分布情況

4 結(jié)論

綜上所述，LEACH_C算法中傳感器節(jié)點(diǎn)到路由節(jié)點(diǎn)網(wǎng)絡(luò)通過固定的單跳分簇結(jié)構(gòu)進(jìn)行傳感器信息采集；路由節(jié)點(diǎn)到基站網(wǎng)絡(luò)根據(jù)他們與基站的距離劃分為不同的區(qū)域，根據(jù)式(9)以及式(10)的策略確定數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù)，以減輕基站周圍區(qū)域的節(jié)點(diǎn)能量的負(fù)載。并且LEACH_C算法使用不定長幀間隔，進(jìn)行每輪數(shù)據(jù)收集時，單個路由轉(zhuǎn)發(fā)數(shù)據(jù)的次數(shù)大致相同，解決了因簇成員不同引起的負(fù)載分布不均衡的問題；另外，在路由選擇過程中，也充分考慮路由下一跳的節(jié)點(diǎn)能量消耗和剩余能量的情況。因此，LEACH_C算法能夠使網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)的負(fù)載趨于均衡，有效的減弱了“熱點(diǎn)問題”，同時也降低了離基站較遠(yuǎn)的簇頭的通信能耗；同時該算法還限制路由轉(zhuǎn)發(fā)時的距離，降低了中間節(jié)點(diǎn)的電路開銷，使離基站較近的區(qū)域的路由簇頭節(jié)點(diǎn)和基站通信，再由基站將路由信息傳遞給緊鄰的下一區(qū)域的簇頭節(jié)點(diǎn)，避免了路由選擇時產(chǎn)生的能量浪費(fèi)。LEACH_C算法很適合應(yīng)用于智能服裝、智能環(huán)境監(jiān)測，礦井下監(jiān)測等低能耗分層網(wǎng)絡(luò)，具有很好的研究價值。

[1] W.Heinzelman,A.P.Chand rakasan,H.Balak rishnan.Application-specific protocol architecture for w ire-less microsensor networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2] G.Pottie and W.Kaiser, W ireless integrated netw ork sensors, Communications of the ACM,43,(2000),51-58.

[3] J.C.Zhao, A.T.Erdogan, T.A rslan. A Novel Application Specific Network Protocol for Wireless Sensor Network[J].Circuits and Systems, 2005:5894-5897.

[4] 任東海,尚鳳軍,王寅.一種基于時間延遲機(jī)制的無線傳感器網(wǎng)絡(luò)分簇算法[J].傳感技術(shù)學(xué)報,2009,22(11)：1645-1649.

[5] 劉志,裘正定.基于分環(huán)多跳的無線傳感器網(wǎng)絡(luò)分簇路由算法[J].通信學(xué)報，2008,29(3):104-112.