基于能量均衡的WSNs固定分區(qū)路由算法*

李秋巒， 詹國(guó)華， 李志華

(杭州師范大學(xué) 信息科學(xué)與工程學(xué)院,浙江 杭州 311121)

0 引 言

隨著無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)被越發(fā)廣泛地應(yīng)用到軍事、環(huán)境監(jiān)測(cè)、醫(yī)療救護(hù)等領(lǐng)域，作為其關(guān)鍵技術(shù)之一的路由算法也開始成為人們關(guān)注的焦點(diǎn)。

WSNs能量有限，故低能耗與負(fù)載均衡是其路由算法設(shè)計(jì)的首要目標(biāo)[1]。分簇路由可以提高能量利用率、均衡網(wǎng)絡(luò)負(fù)載，是一種有效的WSNs拓?fù)涔芾矸绞絒2]。其主要思想是選擇部分節(jié)點(diǎn)作為簇首，簇內(nèi)成員將數(shù)據(jù)發(fā)送給簇首，簇首將數(shù)據(jù)融合后發(fā)送給信宿。Heinzelman W等人提出的LEACH協(xié)議[3](low energy adaptive clustering hierarchy)是早期的一種專為WSNs設(shè)計(jì)的經(jīng)典協(xié)議。其中定義了“輪(round)”的概念，并創(chuàng)建了時(shí)分多址時(shí)刻表以記錄成員節(jié)點(diǎn)的數(shù)據(jù)傳輸時(shí)隙。

繼承LEACH協(xié)議分簇思想的改進(jìn)協(xié)議有很多。DEEC(distributed energy-efficient clustering)算法對(duì)簇間通信算法進(jìn)行了優(yōu)化，但未解決簇首數(shù)量波動(dòng)大和分布不均勻的問(wèn)題[4]。鄧仲芬等人提出的EUCR(energy-efficient uniform tree-clustering routing)協(xié)議均勻了簇首分布，但未考慮網(wǎng)絡(luò)的控制開銷[5]。李成法等人提出的EEUC(energy-efficient uneven cluster)算法基于地理位置對(duì)網(wǎng)絡(luò)進(jìn)行規(guī)模不等的分簇[6]，平衡了不同位置節(jié)點(diǎn)的能耗，但沒(méi)有對(duì)相關(guān)參數(shù)進(jìn)行優(yōu)化取值。

本文在LEACH算法的基礎(chǔ)上，提出一種基于能量均衡的固定分區(qū)路由算法(fixed partition routing algorithm basedon energy balance,FRAEB)。通過(guò)計(jì)算最優(yōu)簇半徑進(jìn)行非均勻分簇以避免“熱區(qū)”[7]問(wèn)題，采用固定分區(qū)策略，限制簇首的范圍與數(shù)量，引入簇首能量自檢機(jī)制，避免過(guò)大的控制開銷，同時(shí)充分利用節(jié)點(diǎn)剩余能量和位置信息，選取最優(yōu)節(jié)點(diǎn)成為簇首。

1 FRAEB流程

本算法包括模型假設(shè)、網(wǎng)絡(luò)劃分、分區(qū)成簇、簇首輪換、數(shù)據(jù)傳輸五部分，算法流程如圖1所示。

圖1 FRAEB流程圖

在本算法中，首先對(duì)網(wǎng)絡(luò)結(jié)構(gòu)作出假設(shè)，確定網(wǎng)絡(luò)能耗模型。然后計(jì)算最優(yōu)簇半徑以解決“熱區(qū)”問(wèn)題，同時(shí)采用固定分區(qū)策略，限制簇首的范圍與數(shù)量，在簇首輪換階段引入簇首能量自檢機(jī)制，并將節(jié)點(diǎn)能量與位置對(duì)簇首選舉的影響進(jìn)行量化，得到簇首競(jìng)爭(zhēng)力計(jì)算公式。下面將對(duì)各部分逐一詳述。

2 模型假設(shè)

2.1 網(wǎng)絡(luò)模型

本文對(duì)WSNs結(jié)構(gòu)作如下假設(shè)：

1)信宿節(jié)點(diǎn)計(jì)算與存儲(chǔ)能力較強(qiáng)，能量不受限。

2)所有傳感器節(jié)點(diǎn)結(jié)構(gòu)相同，具有一定的計(jì)算和存儲(chǔ)能力，能量受限且初始能量相同，可以感知自身能量和位置信息，發(fā)射功率可調(diào)。

3)不考慮環(huán)境因素對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響。

2.2 能耗模型

本文采用常見(jiàn)的一階能耗模型，如圖2所示。

圖2 一階能耗模型

該模型的通信能耗計(jì)算公式如下所示

(1)

ERx(k)=Eelec·k.

(2)

其中,ETx(k,d)為向距離dm的節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)的能耗；ERx(k)為節(jié)點(diǎn)接收kbit數(shù)據(jù)的能耗；Eelec為節(jié)點(diǎn)發(fā)送電路和接收電路處理單位數(shù)據(jù)的能耗；εfs,εmp分別為自由空間模型和多徑衰落模型中放大單位數(shù)據(jù)并傳輸單位距離所需的能量，可統(tǒng)一用Eamp表示；dcrossover為距離門限值，若傳輸距離d比距離門限值小，則采用自由空間模型，放大能量消耗與d2呈正比；否則，采用多徑衰落模型，能耗與d4呈正比。此外，融合單位數(shù)據(jù)的能耗為Eda。

3 網(wǎng)絡(luò)劃分

在FRAEB中，首先計(jì)算最優(yōu)簇半徑，對(duì)網(wǎng)絡(luò)進(jìn)行非均勻劃分，為之后的分區(qū)成簇做準(zhǔn)備。

當(dāng)所有節(jié)點(diǎn)都部署完畢后，信宿向監(jiān)測(cè)區(qū)域廣播消息收集節(jié)點(diǎn)位置信息，并由此創(chuàng)建和維護(hù)一個(gè)傳感器節(jié)點(diǎn)信息表，記錄節(jié)點(diǎn)標(biāo)識(shí)、位置信息及活躍狀態(tài)。之后信宿計(jì)算出監(jiān)測(cè)區(qū)域面積，并據(jù)此將其分為L(zhǎng)層，離信宿最近的為第L層，最遠(yuǎn)的為第1層。FRAEB網(wǎng)絡(luò)結(jié)構(gòu)圖如圖3所示。

圖3 FRAEB網(wǎng)絡(luò)結(jié)構(gòu)

計(jì)算簇半徑是為了平衡不同簇層能耗，所以，簇半徑的計(jì)算應(yīng)從能量消耗角度出發(fā)。根據(jù)通信能耗計(jì)算公式和Eda可計(jì)算出各層簇在一輪數(shù)據(jù)收集過(guò)程中消耗的能量Etotal(i)。本文假設(shè)簇首將各成員上傳的kbit數(shù)據(jù)融合成kbit的數(shù)據(jù)包轉(zhuǎn)發(fā)給中繼簇首，而中繼簇首只負(fù)責(zé)轉(zhuǎn)發(fā)此數(shù)據(jù)包，如圖3所示。

若已知各層簇半徑ri，則可得各層簇個(gè)數(shù)N(i)

(3)

其中,M為監(jiān)測(cè)區(qū)域邊長(zhǎng)，并由此得各層的成員節(jié)點(diǎn)個(gè)數(shù)Nnon-CH(i)

(4)

式中N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)。各層簇的能耗來(lái)自4個(gè)方面：成員節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗Enon-CH(i)，簇首接收并融合簇內(nèi)數(shù)據(jù)的能耗ER&D(i)，簇首接收上級(jí)簇首的能耗ER-Sup(i)和簇首將數(shù)據(jù)轉(zhuǎn)發(fā)給內(nèi)層簇首的能耗ERelay(i)。由通信能耗公式得Enon-CH(i)

(5)

(6)

同樣，根據(jù)通信能耗公式，得到ER&D(i)算式

ER&D(i)=k[Eelec(Nnon-CH(i))+Eda(Nnon-CH(i)+

N(i))].

(7)

簇首接收外層數(shù)據(jù)能耗ER-Sup(i)算式

ER-Sup(i)=kEelecN(i-1),2≤i≤L,

(8)

式中i=1時(shí)ER-Sup(i)=0。ERelay(i)的算式如下

ERela(i)=

(9)

式中h為最內(nèi)層簇首到信宿的距離。文中令兩層簇首間的距離約等于兩層半徑之和，最內(nèi)層簇首到信宿距離約等于rL與h之和。至此可求出各簇層總能耗Etotal(i)，其值涉及的變量只有各層簇半徑ri。當(dāng)各層總能耗相等時(shí)，各層簇半徑為最佳簇半徑，故可根據(jù)各層總能耗之間的關(guān)系，以及各層半徑之和與網(wǎng)絡(luò)邊長(zhǎng)M的關(guān)系列出方程組

(10)

解此方程組即可求得各層最佳簇半徑ri。

4 分區(qū)成簇

FRAEB采用固定分區(qū)策略，其分區(qū)成簇的具體過(guò)程分為初始簇首選舉和簇的建立2個(gè)步驟。

4.1 簇首選舉

計(jì)算出各層簇半徑后，信宿將監(jiān)測(cè)區(qū)域進(jìn)行分層，并將各層劃分成大小相等的區(qū)塊(允許每層有個(gè)別區(qū)塊大小不同)。由于各節(jié)點(diǎn)初始能量相同，信宿在各分區(qū)選擇離中心最近的節(jié)點(diǎn)做為初始簇首。

4.2 簇的建立

信宿選出簇首后，為各節(jié)點(diǎn)選擇一個(gè)最近的簇首加入，并創(chuàng)建一個(gè)簇信息表，包含簇標(biāo)識(shí)、簇首信息和成員信息。其中簇首信息包含自身標(biāo)識(shí)、位置及能量；而成員信息還包含自身數(shù)據(jù)傳輸時(shí)隙。

之后信宿將簇信息廣播到監(jiān)測(cè)區(qū)域。傳感器節(jié)點(diǎn)查詢自身所屬簇并判斷是否為簇首，若是，則需要?jiǎng)?chuàng)建并維護(hù)一個(gè)成員節(jié)點(diǎn)信息表和一個(gè)數(shù)據(jù)傳輸超時(shí)定時(shí)器；否則，只需要記錄對(duì)應(yīng)的簇首。之后簇首和使用第一時(shí)隙的成員節(jié)點(diǎn)切換到正常通信狀態(tài)，其他成員節(jié)點(diǎn)切換到休眠狀態(tài)。

5 簇首輪換

不同于周期性簇首選舉，F(xiàn)RAEB中僅當(dāng)簇首的剩余能量低于閾值ET時(shí)重新進(jìn)行簇首選舉，該過(guò)程充分考慮了節(jié)點(diǎn)的能量與位置，具體機(jī)制如下。

當(dāng)前簇首感知自身能量信息，若低于閾值ET，則判定自身失效，并選取剩余能量大于ET的節(jié)點(diǎn)作為候選簇首集合，若集合為空，則調(diào)整ET并重復(fù)上述步驟。ET調(diào)整機(jī)制由公式(11)表示

(11)

式中ET(i)為第i次閾值調(diào)整后的能量閾值，ET(0)為能量閾值的初始值。E0為節(jié)點(diǎn)初始能量，c0為迭代因子。當(dāng)前簇首計(jì)算出活躍節(jié)點(diǎn)的中心位置，并選取距離中心位置較近且剩余能量較多的節(jié)點(diǎn)為新簇首。將節(jié)點(diǎn)位置和能量2個(gè)因素對(duì)簇首選舉的影響進(jìn)行量化，得到簇首競(jìng)爭(zhēng)力計(jì)算公式

(12)

式中P(i)為候選簇首i的競(jìng)爭(zhēng)力量化值；dmax為候選簇首與簇中心的最遠(yuǎn)距離，di為候選簇首i與簇中心的距離；ER(i)為候選簇首i的剩余能量，ERmax和ERmin代表其中的最大值與最小值；c1,c2分別為候選簇首的位置和能量在簇首競(jìng)爭(zhēng)力計(jì)算公式中的權(quán)重。要求c1,c2的取值范圍都為[0,1],且求和為1。

在選舉結(jié)束后，若當(dāng)前簇首當(dāng)選，則該簇開始工作；否則，當(dāng)前簇首廣播新簇首消息，并與新簇首完成角色交換，之后該簇開始工作。

6 數(shù)據(jù)傳輸

6.1 簇內(nèi)通信

在簇內(nèi)通信階段，F(xiàn)RAEB除了采用LEACH協(xié)議的休眠機(jī)制外，還令成員節(jié)點(diǎn)根據(jù)與簇首的距離來(lái)降低發(fā)射功率；成員節(jié)點(diǎn)將能量信息加在發(fā)送數(shù)據(jù)中，使簇首更新成員節(jié)點(diǎn)信息；引入數(shù)據(jù)傳輸超時(shí)定時(shí)器，供簇首判定成員節(jié)點(diǎn)是否死亡。

6.2 簇間通信

FRAEB在簇間通信階段采用了多跳思想，并結(jié)合自身特點(diǎn)加以改善：分簇階段，節(jié)點(diǎn)根據(jù)所屬簇標(biāo)識(shí)計(jì)算下一跳簇層；簇首輪換階段，新簇首調(diào)整發(fā)射功率以覆蓋將自身作為下一跳簇首的所有簇，這些簇的簇首收到新簇首消息后查看新簇首所屬簇是否屬于下一跳簇集合，若是,則更改該集合相應(yīng)項(xiàng)，并重新計(jì)算最短距離，選擇下一跳簇首。

7 算法仿真

本文采用Matlab對(duì)FRAEB算法進(jìn)行仿真，并與LEACH和DEEC做比較。500個(gè)節(jié)點(diǎn)均勻部署在250 m×250 m的正方形區(qū)域內(nèi)，信宿節(jié)點(diǎn)坐標(biāo)為(125,300)m?？刂瓢L(zhǎng)度和DATA包長(zhǎng)度分別為25 bytes和500 bytes。網(wǎng)絡(luò)環(huán)境仿真參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)表

首先分析網(wǎng)絡(luò)的整體能耗，3種協(xié)議下的網(wǎng)絡(luò)整體能耗曲線如圖4所示。

圖4 各協(xié)議的網(wǎng)絡(luò)整體能量消耗

從圖中可見(jiàn)，使用FRAEB的網(wǎng)絡(luò)其能耗曲線位于最下方，即經(jīng)歷相同輪數(shù)的情況下能耗最小。接下來(lái)分析簇首能耗方差，以判斷簇首能耗是否均衡。取簇首節(jié)點(diǎn)能耗的最大值和最小值，按照方差公式進(jìn)行計(jì)算。連續(xù)隨機(jī)抽取10輪樣本,得出3種協(xié)議的簇首能耗方差曲線如圖5所示。

圖5 各協(xié)議的簇首能耗方差

圖5顯示了使用FRAEB的網(wǎng)絡(luò)中簇首能耗方差最小，且沒(méi)有明顯的波動(dòng)，表明該算法可以較好地均衡網(wǎng)絡(luò)中不同區(qū)域的能量消耗。節(jié)點(diǎn)能耗均衡是延長(zhǎng)網(wǎng)絡(luò)生命周期最主要的因素，各協(xié)議生命周期曲線如圖6所示。

圖6 各協(xié)議的網(wǎng)絡(luò)生命周期

圖6表明：相比使用其他兩種的網(wǎng)絡(luò)，使用FRAEB的網(wǎng)絡(luò)所經(jīng)歷的輪數(shù)最多，表明其生命周期最長(zhǎng)。很大程度上，這得益于FRAEB基于能耗均衡而設(shè)計(jì)的特點(diǎn)。

8 結(jié)束語(yǔ)

本文在詳細(xì)分析以往分簇路由協(xié)議的基礎(chǔ)上，創(chuàng)新地將固定分區(qū)思想與非均勻分簇思想進(jìn)行融合，并結(jié)合以往協(xié)議的優(yōu)點(diǎn)，提出了一種FRAEB。仿真結(jié)果表明：FRAEB有效降低了網(wǎng)絡(luò)總體能耗，同時(shí)均衡了網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載，使網(wǎng)絡(luò)生命周期得到了較好的延長(zhǎng)。

參考文獻(xiàn):

[1] Olutayo B,Hanh L,Audrey M.A survey on clustering algorithm for wireless sensor networks[C]∥Proceedings of the 13th International Conference on Network-based Information System,IEEE Computer Society,2010:358-364.

[2] 李洪兵,熊慶宇,石為人.無(wú)線傳感器網(wǎng)絡(luò)非均勻等級(jí)分簇拓?fù)浣Y(jié)構(gòu)研究[J].計(jì)算機(jī)科學(xué),2013,40(2):49-52,77.

[3] Heinzelman W,Chandrakasan A,Balakrishman H.Energy-efficient communication protocol for wireless sensor networks[C]∥Proceedings of Hawaii International Conference on System Science,Hawaii,USA,2000: 3005-3014.

[4] 魏春娟,楊俊杰,張志美.一種分布式能量有效的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),2013,26(7):1014-1019.

[5] 鄧仲芬,石為人,黃 河,等.一種基于樹均勻分簇的WSNs節(jié)能路由協(xié)議[J].傳感器與微系統(tǒng),2011,30(5):47-50.

[6] 李成法,陳貴海,葉 懋,等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007,30(1):27-36.

[7] Soro S,Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering[C]∥Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,Co,USA,2005.

[8] Heinzelman W,Chandrakasan A P,Balakrishnan H.An application specific protocol architecture for wireless micro-sensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):1536-1276.