基于不均等環(huán)帶分區(qū)的WSN能耗均衡路由協(xié)議

鄭文軍，韓 波

（1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001；2.阜陽(yáng)師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，安徽 阜陽(yáng) 236037）

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)是由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量微型傳感器節(jié)點(diǎn)組成，可用于各種場(chǎng)景，如環(huán)境監(jiān)測(cè)[1]、目標(biāo)跟蹤[2]、健康監(jiān)測(cè)[3]、軍事[4]、農(nóng)業(yè)[5]和其他許多應(yīng)用[6-7]。WSN具有能量、處理能力、存儲(chǔ)和傳輸范圍等多種資源約束的特點(diǎn)。在這些因素中，傳感器的能量一直是無(wú)線傳感器網(wǎng)絡(luò)的主要資源約束[8]。為了應(yīng)對(duì)這個(gè)挑戰(zhàn)，國(guó)內(nèi)外很多研究人員都提出不同的解決方案。

分層或基于成簇的路由算法是眾所周知的技術(shù)，在伸縮性和高效性方面具有特殊的優(yōu)勢(shì)。低能耗自適應(yīng)分簇協(xié)議LEACH[9]是一種流行的機(jī)制，它能動(dòng)態(tài)地形成集群并分配簇頭，然后將聚集的數(shù)據(jù)發(fā)送到基站，能夠有效緩解節(jié)點(diǎn)的能量損失。但是LEACH未能考慮到簇頭的剩余能量并采用隨機(jī)選舉簇頭的方式導(dǎo)致簇頭分布隨機(jī)，最終形成“能量空洞”現(xiàn)象[10-11]。文獻(xiàn)[12-13]針對(duì)LEACH的缺點(diǎn)提出了改進(jìn)，文獻(xiàn)[12]在LEACH的基礎(chǔ)上提出通過(guò)雙簇頭來(lái)均衡簇頭之間的傳輸能耗，但是采用基于LEACH協(xié)議中的簇頭選擇方式，未能考慮到簇頭分布的隨機(jī)性問(wèn)題；文獻(xiàn)[13]則在選舉簇頭時(shí)充分考慮了簇頭能量并建立簇頭與基站之間的多跳傳輸路徑來(lái)減少能耗的損失，但是采用均勻分簇的方法，基站附近的節(jié)點(diǎn)會(huì)因中繼數(shù)據(jù)導(dǎo)致負(fù)載過(guò)重提前死亡。相對(duì)而言，非均勻分簇算法在節(jié)點(diǎn)負(fù)載均衡與克服“能量空洞”現(xiàn)象方面效果更佳。文獻(xiàn)[14]提出了一種能量高效的非均勻分簇算法，基站附近節(jié)點(diǎn)直接與基站通信，遠(yuǎn)距離節(jié)點(diǎn)則通過(guò)改進(jìn)的LEACH簇頭選擇方式建立規(guī)模大小不等的簇，有效提高了節(jié)點(diǎn)的能量利用率，但是簇頭的個(gè)數(shù)仍舊根據(jù)經(jīng)驗(yàn)來(lái)選擇，未能尋找出網(wǎng)絡(luò)中的最優(yōu)簇首個(gè)數(shù)。文獻(xiàn)[15-17]提出了基于分區(qū)思想的路由算法，根據(jù)距離基站的遠(yuǎn)近將網(wǎng)絡(luò)劃分不同的層次，通過(guò)合理的分區(qū)來(lái)達(dá)到降低網(wǎng)絡(luò)能耗的目的；但是文獻(xiàn)[15-16]均未能考慮到每層節(jié)點(diǎn)的能耗均衡問(wèn)題，同時(shí)基站附近節(jié)點(diǎn)成簇會(huì)更加損耗能量；文獻(xiàn)[17]中首環(huán)半徑選擇過(guò)大，會(huì)是得原本負(fù)載較重的內(nèi)環(huán)節(jié)點(diǎn)在中繼數(shù)據(jù)時(shí)過(guò)快死亡，不利于網(wǎng)絡(luò)能耗均衡。文獻(xiàn)[18]提出一種能量異構(gòu)的分簇方案，根據(jù)節(jié)點(diǎn)與基站的距離，在不同的地理位置布置初始能量不同的節(jié)點(diǎn)來(lái)克服“能量空洞”，達(dá)到均衡網(wǎng)絡(luò)能耗的目的，但是該方法實(shí)際操作起來(lái)很難實(shí)現(xiàn)。

本文借鑒上述算法的優(yōu)點(diǎn)提出了一種基于不均等環(huán)帶分區(qū)的能耗均衡路由算法UREC，通過(guò)對(duì)網(wǎng)絡(luò)進(jìn)行不均等劃分來(lái)實(shí)現(xiàn)非均勻分簇，并對(duì)各環(huán)帶內(nèi)節(jié)點(diǎn)總能耗進(jìn)行分析計(jì)算得出最佳的區(qū)域劃分方案，能夠有效均衡網(wǎng)絡(luò)的整體能耗。

1 網(wǎng)絡(luò)模型與能耗模型

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

本文首先假設(shè)無(wú)線傳感器網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)隨機(jī)均勻的分布在以基站為中心，半徑為R的圓形網(wǎng)絡(luò)區(qū)域中。網(wǎng)絡(luò)模型具有以下性質(zhì)：

1)節(jié)點(diǎn)都是靜止不變的，一旦部署完成便不再變化；

2)基站能量不受限，其余節(jié)點(diǎn)初始能量均為E0；

3)節(jié)點(diǎn)位置已知，可獲取自身的坐標(biāo)信息，且發(fā)射功率可調(diào)；

4)每個(gè)節(jié)點(diǎn)都有唯一的ID號(hào)。

1.2 能耗模型

采用與文獻(xiàn)[19]相同的能耗模型，僅考慮節(jié)點(diǎn)的通信能耗，忽略節(jié)點(diǎn)存儲(chǔ)與計(jì)算等能量消耗。

如圖1，節(jié)點(diǎn)發(fā)送lb數(shù)據(jù)給相距dm處的另一個(gè)節(jié)點(diǎn)所消耗的能量為

節(jié)點(diǎn)接收l(shuí)b數(shù)據(jù)的能耗為

其中Eelec為發(fā)送和接收1 b數(shù)據(jù)時(shí)電路的能量損耗。d0為通信閾值，且有εfs和εmp表示相應(yīng)的衰落系數(shù)）。當(dāng)d＜d0時(shí)，采用自由空間模型；當(dāng)d≥d0時(shí)，采用多路徑衰減模型。

圖1 網(wǎng)絡(luò)能耗模型

1.3 數(shù)據(jù)融合模型

本文采用數(shù)據(jù)融合技術(shù)來(lái)減少網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，達(dá)到節(jié)約網(wǎng)絡(luò)能耗的目的。由于簇頭與簇頭間距離相對(duì)較遠(yuǎn)，本文只考慮簇內(nèi)數(shù)據(jù)融合。數(shù)據(jù)融合的模型為：簇頭接收到簇內(nèi)n個(gè)成員節(jié)點(diǎn)發(fā)送的lb數(shù)據(jù)，最終都會(huì)壓縮為1個(gè)lb數(shù)據(jù)發(fā)送給下一跳簇頭，數(shù)據(jù)融合能耗為EDA。融合lb數(shù)據(jù)所消耗的能耗為：

2 基于不均等環(huán)帶的能耗均衡路由協(xié)議

2.1UREC算法簡(jiǎn)述

本文提出的UREC算法能夠?qū)⒐?jié)點(diǎn)基于位置劃分，建立若干位置分布均勻簇規(guī)模大小不等的簇，有效解決了簇頭分布隨機(jī)性大，簇群分布不均勻而導(dǎo)致節(jié)點(diǎn)能耗不均衡問(wèn)題。本文主要分為3個(gè)階段：

1)區(qū)域劃分階段。將監(jiān)測(cè)區(qū)域劃分成若干層圓環(huán)，首先計(jì)算各環(huán)帶內(nèi)的節(jié)點(diǎn)總能耗，以各環(huán)帶能耗均衡為目標(biāo)來(lái)確定每層環(huán)帶的寬度；其次是將網(wǎng)絡(luò)進(jìn)一步劃分，每層都劃分成相等的若干個(gè)分區(qū)，分區(qū)的面積與距離基站的距離成正比，最終構(gòu)建出若干面積大小不等的簇，從而實(shí)現(xiàn)網(wǎng)絡(luò)的非均勻分簇，有效緩解了“能量空洞”問(wèn)題。

2)簇的形成階段。每個(gè)分區(qū)內(nèi)進(jìn)行非均勻成簇，簇頭選擇時(shí)綜合簇內(nèi)能耗與簇間傳輸能耗，保證數(shù)據(jù)傳輸時(shí)簇內(nèi)能耗與簇間能耗最優(yōu)；同時(shí)在競(jìng)爭(zhēng)簇頭的過(guò)程中參考節(jié)點(diǎn)自身的剩余能量，確保所選舉的簇頭能量較高。

3)簇間傳輸階段。經(jīng)過(guò)區(qū)域劃分之后，整個(gè)網(wǎng)絡(luò)在縱向上被劃分成若干個(gè)扇形區(qū)域，每個(gè)分區(qū)內(nèi)成員節(jié)點(diǎn)通過(guò)單跳方式將數(shù)據(jù)發(fā)送給所在簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)再將數(shù)據(jù)進(jìn)行融合之后發(fā)送給同一扇形區(qū)域的下一層環(huán)帶內(nèi)的簇頭節(jié)點(diǎn)，以多跳的方式建立合理的簇間路由。

2.2 區(qū)域劃分

區(qū)域劃分的基本思想：假設(shè)網(wǎng)絡(luò)以基站為中心被劃分成若干環(huán)帶，每層環(huán)帶又被劃分成相同數(shù)量的分區(qū)，以環(huán)帶間能耗均衡為目的確定各個(gè)環(huán)帶的寬度。如圖2，將監(jiān)測(cè)區(qū)域劃分成H層寬度不等的環(huán)帶，再將每層環(huán)帶均勻的劃分成K個(gè)分區(qū)，同一層環(huán)帶內(nèi)的各個(gè)分區(qū)面積相等，距離基站越遠(yuǎn)，分區(qū)面積越大，最終形成的簇的面積越大。為了降低網(wǎng)絡(luò)能耗的損失，應(yīng)保證簇內(nèi)成員節(jié)點(diǎn)與簇頭的距離、簇頭與簇頭的距離、簇頭與基站的距離均符合自由空間模型，區(qū)域劃分需遵守3個(gè)約束條件：

1)第1層環(huán)帶的寬度小于d0；

2）相鄰2層環(huán)帶的寬度之和應(yīng)小于d0；

3)任意分區(qū)內(nèi)的任意兩個(gè)節(jié)點(diǎn)之間的最大距離小于d0。圖中Ri表示第i個(gè)同心圓的半徑，ri表示第i個(gè)環(huán)帶的寬度，Ci表示第i個(gè)環(huán)帶區(qū)域且R1=r1,Ri=Ri-1+ri。

1)首環(huán)半徑的確定。已知距離基站較近的節(jié)點(diǎn)除了自身的任務(wù)外，還需中繼距離基站較遠(yuǎn)的節(jié)點(diǎn)的數(shù)據(jù)任務(wù)，這些節(jié)點(diǎn)會(huì)因負(fù)載過(guò)重而提前死亡，形成“能量空洞”，影響整個(gè)網(wǎng)絡(luò)的壽命。根據(jù)文獻(xiàn)[20]可知，在一定距離范圍內(nèi)，相比于通過(guò)簇頭的轉(zhuǎn)發(fā)，節(jié)點(diǎn)直接與基站通信的能耗損失會(huì)更低。通過(guò)改進(jìn)文獻(xiàn)[17]中的首環(huán)半徑公式，我們可以得到

其中，α為調(diào)節(jié)系數(shù)。

當(dāng)α=1時(shí)，首環(huán)半徑r1取得最大值，環(huán)帶內(nèi)節(jié)點(diǎn)直接與基站的通信能耗更少，但是由于范圍較大，不利于節(jié)點(diǎn)負(fù)載均衡。仿真發(fā)現(xiàn)，當(dāng)α=0.5時(shí)，網(wǎng)絡(luò)壽命最長(zhǎng)。

圖2 區(qū)域劃分

2)各環(huán)帶寬度的確定。在理想的網(wǎng)絡(luò)能耗均衡情況下，各環(huán)內(nèi)的總能耗相同。本文首先計(jì)算出各環(huán)的節(jié)點(diǎn)能耗，然后以理想情況下的網(wǎng)絡(luò)能耗均衡為目標(biāo)推導(dǎo)出各環(huán)帶的最佳寬度的表達(dá)式。每個(gè)數(shù)據(jù)采集周期內(nèi)，各環(huán)帶內(nèi)的能耗主要分為2部分：

（?。┐貎?nèi)成員節(jié)點(diǎn)的數(shù)據(jù)發(fā)送能耗和簇頭的接收、融合能耗，稱之為簇內(nèi)能耗。

（ⅱ）簇頭接收上游簇頭數(shù)據(jù)的接收能耗和簇頭轉(zhuǎn)發(fā)給下游簇頭的轉(zhuǎn)發(fā)能耗，稱之為簇間能耗。

已知監(jiān)測(cè)區(qū)域被劃分成了H層環(huán)帶且節(jié)點(diǎn)均勻分布在網(wǎng)絡(luò)中，那么第i層環(huán)帶內(nèi)的節(jié)點(diǎn)數(shù)Ni

每一輪數(shù)據(jù)采集周期內(nèi)，第i(2≤i≤H)層環(huán)帶內(nèi)的簇內(nèi)傳輸總能耗的期望為：

其中，Ri-cluster為第i(2≤i≤H)層環(huán)帶內(nèi)簇半徑的近似值，有

當(dāng)i=1時(shí)，將整個(gè)第1環(huán)看成一個(gè)以基站為簇頭的簇，簇內(nèi)其余節(jié)點(diǎn)直接將數(shù)據(jù)發(fā)送至基站，那么，第1環(huán)內(nèi)的簇內(nèi)傳輸總能耗期望為：

外層環(huán)帶內(nèi)的簇頭節(jié)點(diǎn)需要以內(nèi)層環(huán)帶內(nèi)簇頭作為中繼節(jié)點(diǎn)，最終將感知的數(shù)據(jù)發(fā)送到基站。那么，第i層環(huán)帶內(nèi)的每個(gè)簇頭節(jié)點(diǎn)在一輪數(shù)據(jù)采集周期中接收來(lái)自外層簇頭的數(shù)據(jù)總量為(H-i)l，第2～i層內(nèi)每個(gè)簇頭轉(zhuǎn)發(fā)給下一層簇頭的數(shù)據(jù)總量為(H-i+1)l，第1層簇頭轉(zhuǎn)發(fā)的數(shù)據(jù)總量為(H-1)l。那么，第1層環(huán)節(jié)點(diǎn)將外層數(shù)據(jù)發(fā)送給基站的能耗模型

第2層環(huán)帶內(nèi)簇頭數(shù)據(jù)通過(guò)首環(huán)內(nèi)成員節(jié)點(diǎn)轉(zhuǎn)發(fā)給基站。第2層簇頭節(jié)點(diǎn)到首環(huán)轉(zhuǎn)發(fā)節(jié)點(diǎn)的距離服從均勻分布其平方的期望值為則第2層簇間傳輸總能耗的期望為：

其中

為減少簇內(nèi)能量的損耗，簇內(nèi)能耗最小的理想情況下是各環(huán)帶內(nèi)簇頭位于環(huán)帶的幾何中心位置，此時(shí)同一扇形區(qū)域的相鄰簇頭間的距離滿足

則第i(3≤i≤H)層環(huán)內(nèi)簇間傳輸?shù)哪芎?/p>

故一個(gè)數(shù)據(jù)采集周期內(nèi)，每層環(huán)帶內(nèi)的總的能量消耗為：

根據(jù)各層環(huán)帶內(nèi)能耗均衡的準(zhǔn)則，可得到各環(huán)帶寬度的關(guān)系式

2.3 簇的形成

2.3.1 構(gòu)建簇頭競(jìng)爭(zhēng)簇

當(dāng)節(jié)點(diǎn)部署到監(jiān)測(cè)區(qū)域之后，基站向全網(wǎng)廣播消息通知所有節(jié)點(diǎn)開始工作，每個(gè)節(jié)點(diǎn)根據(jù)自己的位置信息判斷自己所處分區(qū)，同一分區(qū)內(nèi)節(jié)點(diǎn)構(gòu)建成一個(gè)簇頭競(jìng)爭(zhēng)簇，參與簇頭的競(jìng)爭(zhēng)。每個(gè)節(jié)點(diǎn)都在通信范圍內(nèi)廣播消息，根據(jù)接收到的信息確定處于同一分區(qū)內(nèi)節(jié)點(diǎn)的個(gè)數(shù)、距離及能量信息。

如圖2區(qū)域劃分圖所示，整個(gè)網(wǎng)絡(luò)共被分成H×K個(gè)分區(qū)，其中有H層環(huán)帶區(qū)域和K個(gè)扇形區(qū)域，每個(gè)分區(qū)(第1環(huán)除外)即一個(gè)簇頭競(jìng)爭(zhēng)簇，從中選舉出一個(gè)簇頭節(jié)點(diǎn)。

2.3.2 簇頭選舉

競(jìng)爭(zhēng)簇內(nèi)競(jìng)選簇頭時(shí)應(yīng)該考慮三個(gè)因素，首先我們所選出的簇頭應(yīng)該保證簇內(nèi)能耗較小，其次是簇頭能量充足，最后是簇間傳輸能耗較小。針對(duì)這三個(gè)影響因素構(gòu)建相關(guān)通信損失函數(shù)作為簇頭選舉時(shí)的參考依據(jù)，有

網(wǎng)絡(luò)中所有節(jié)點(diǎn)根據(jù)公式(17)計(jì)算自身的損失函數(shù)并廣播給分區(qū)內(nèi)其他節(jié)點(diǎn)，同一分區(qū)內(nèi)選擇損失函數(shù)最小的節(jié)點(diǎn)最為簇頭節(jié)點(diǎn)，分區(qū)內(nèi)其他節(jié)點(diǎn)作為成員節(jié)點(diǎn)向簇頭發(fā)送數(shù)據(jù)。

2.4 簇間傳輸

簇群形成之后，首先簇內(nèi)成員節(jié)點(diǎn)將感知數(shù)據(jù)發(fā)送給所在簇簇頭，其次外層簇頭需要通過(guò)內(nèi)層簇頭中繼轉(zhuǎn)發(fā)，最終數(shù)據(jù)被發(fā)送到基站。已知整個(gè)監(jiān)測(cè)區(qū)域被劃分成了H層環(huán)帶和K個(gè)扇形區(qū)域，為了保證簇間多跳的通信路徑最短，以扇形區(qū)域?yàn)閱挝?，處于同一扇形區(qū)域內(nèi)的各層簇頭節(jié)點(diǎn)由外向內(nèi)傳輸數(shù)據(jù)，最終將數(shù)據(jù)發(fā)送到基站。

假設(shè) CH(h,k)是第h(1≤h≤H)環(huán)中第k(1≤k≤K)個(gè)分區(qū)內(nèi)的簇頭節(jié)點(diǎn)，那么，簇頭CH(h,k)的下一跳簇頭節(jié)點(diǎn)Next(CH)的具體選擇規(guī)則如下：

3 仿真與分析

為了驗(yàn)證UREC的性能，我們使用MATLAB作為仿真工具，通過(guò)與LEACH和EEUC進(jìn)行性能比較，從網(wǎng)絡(luò)中節(jié)點(diǎn)存活個(gè)數(shù)、網(wǎng)絡(luò)剩余能量以及節(jié)點(diǎn)死亡率三個(gè)方面評(píng)估本文提出的UREC算法的性能。根據(jù)能耗影響的主次因素，α、β和γ的取值分別為0.5、0.3和0.2，其余實(shí)驗(yàn)參數(shù)設(shè)置如表1。

根據(jù)不同的區(qū)間數(shù)設(shè)置，可計(jì)算出網(wǎng)絡(luò)中總的分區(qū)數(shù)量以及相應(yīng)的環(huán)帶寬度，如表2。隨著K的取值不同，網(wǎng)絡(luò)中的簇的數(shù)量也不同，分簇?cái)?shù)目過(guò)少會(huì)加快簇頭的能耗損失，分簇?cái)?shù)目過(guò)多則會(huì)增加簇間傳輸?shù)哪芰繐p失。如圖3，以網(wǎng)絡(luò)中10%節(jié)點(diǎn)死亡時(shí)間為參考依據(jù)，可以得出，當(dāng)K=10時(shí)，此時(shí)網(wǎng)絡(luò)生存時(shí)間最長(zhǎng)。

表1 實(shí)驗(yàn)仿真參數(shù)

表2 各環(huán)半徑的確定

圖4顯示了3種算法的存活節(jié)點(diǎn)數(shù)量的變化曲線，從圖中可以看出UREC運(yùn)行到約1 600輪時(shí)才出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，而LEACH和EEUC的第一個(gè)節(jié)點(diǎn)死亡出現(xiàn)在600輪和1 500左右。LEACH首個(gè)死亡節(jié)點(diǎn)出現(xiàn)最早，可能是由于LEACH選舉簇頭時(shí)未能考慮到簇頭的能量問(wèn)題，而本文在選舉簇頭時(shí)則綜合考慮了簇頭能量和簇內(nèi)能耗因素。同時(shí)UREC算法下的網(wǎng)絡(luò)中總的節(jié)點(diǎn)存活個(gè)數(shù)也要明顯多于LEACH和EEUC。這表明UREC能夠有效均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗，推遲了網(wǎng)絡(luò)中首個(gè)節(jié)點(diǎn)死亡出現(xiàn)的時(shí)間。

圖5是LEACH、EEUC和UREC三種算法下網(wǎng)絡(luò)剩余能量關(guān)系對(duì)比圖。在整個(gè)網(wǎng)絡(luò)周期中，本文提出的UREC的網(wǎng)絡(luò)剩余能量要大于LEACH和EEUC，這說(shuō)明UREC在節(jié)省網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命方面要優(yōu)于LEACH和EEUC。

圖3 不同區(qū)間數(shù)下的網(wǎng)絡(luò)生存時(shí)間

圖4 網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)與生命周期的關(guān)系

圖5 網(wǎng)絡(luò)剩余能量與生命周期的關(guān)系

4 小結(jié)

本文提出了一種基于不均等環(huán)帶分區(qū)的能耗均衡路由算法UREC，該算法通過(guò)均衡各環(huán)帶內(nèi)的能耗負(fù)載來(lái)達(dá)到延長(zhǎng)網(wǎng)絡(luò)壽命的目的，同時(shí)在選擇簇頭時(shí)綜合考慮到節(jié)點(diǎn)的剩余能量與簇內(nèi)能耗最小等因素，保證了簇首選擇的合理性，在同一扇形區(qū)域內(nèi)構(gòu)建簇間路由樹，保證了源節(jié)點(diǎn)到基站的距離最短，有效提高了無(wú)線傳感器網(wǎng)絡(luò)的可靠性。