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

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

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

0 引言

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

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

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

1 無(wú)線通信能量消耗模型

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

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

圖2 無(wú)線通信能量消耗模型

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

2 LEACH_C算法能耗模型分析

LEACH_C算法根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)把網(wǎng)絡(luò)分成兩個(gè)層次，傳感器節(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é)采集融合各個(gè)傳感器節(jié)點(diǎn)收集到的信息；路由轉(zhuǎn)發(fā)節(jié)點(diǎn)到基站為上層網(wǎng)絡(luò)，負(fù)責(zé)把底層網(wǎng)絡(luò)收集到的信息轉(zhuǎn)發(fā)到基站，該過(guò)程由于信息量比較大，轉(zhuǎn)發(fā)次數(shù)比較多，因此該層網(wǎng)絡(luò)能量消耗占整個(gè)網(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)通過(guò)單跳的方式把采集到的數(shù)據(jù)直接發(fā)送到路由轉(zhuǎn)發(fā)節(jié)點(diǎn)。假設(shè)該簇的傳感器節(jié)點(diǎn)的個(gè)數(shù)為i，則底層網(wǎng)絡(luò)的一輪數(shù)據(jù)傳輸?shù)哪芰肯臑椋?/p>

其中ETX，ERX分別為單個(gè)節(jié)點(diǎn)發(fā)送和接收k比特?cái)?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ī)性比較大，若簡(jiǎn)單的采用單跳分簇路由算法，當(dāng)網(wǎng)絡(luò)范圍變大時(shí)，遠(yuǎn)離基站的節(jié)點(diǎn)能量消耗變大，并且各簇頭之間單次通信的能量消耗差別也會(huì)變大。其他LEACH相關(guān)多跳算法中，由于每個(gè)簇成員個(gè)數(shù)不同就造成網(wǎng)絡(luò)中能量消耗不均勻，并且各簇頭與基站進(jìn)行通信時(shí)，也沒(méi)有限制多跳的次數(shù)，這就使得基站周?chē)拇仡^由于參與較多的數(shù)據(jù)轉(zhuǎn)發(fā)而能量消耗過(guò)快，存在嚴(yán)重的“熱點(diǎn)問(wèn)題”。

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

LEACH_C算法中最重要的是各路由轉(zhuǎn)發(fā)節(jié)點(diǎn)多跳次數(shù)的確定，不僅要考慮到各路由節(jié)點(diǎn)簇中簇頭和簇內(nèi)節(jié)點(diǎn)的平均剩余能量，同時(shí)還要考慮各路由節(jié)點(diǎn)到基站的距離?，F(xiàn)在我們假設(shè)有N個(gè)路由節(jié)點(diǎn)隨機(jī)分配在半徑為R的一個(gè)區(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個(gè)簇頭，平均分布在整個(gè)區(qū)域中，位于rn區(qū)域的簇頭節(jié)點(diǎn)和基站的通信需要rn-1區(qū)域內(nèi)的簇頭節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，并且每次通信的距離都在自由衰減通信模型的范圍d0內(nèi)。為了便于研究，假設(shè)每個(gè)簇頭節(jié)點(diǎn)都位于各自區(qū)域的中部，并且每個(gè)區(qū)域的環(huán)寬度都是r，即r1區(qū)域的簇頭處于r/2處，r2區(qū)域的簇頭位于3r/2處，r2區(qū)域的簇頭與基站進(jìn)行通信時(shí)時(shí)通過(guò)r1區(qū)域的簇頭進(jìn)行轉(zhuǎn)發(fā)的，以此類(lèi)推，則當(dāng)處于rj區(qū)域的簇頭向基站發(fā)送k bit數(shù)據(jù)時(shí)，網(wǎng)絡(luò)中單個(gè)簇頭節(jié)點(diǎn)的能耗為：

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

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

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

由式(8)可得：

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

2.3 剩余能量均衡化

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

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

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

3 LEACH_C算法仿真

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

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

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

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

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

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

4 結(jié)論

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

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

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