基于區(qū)域控制的低功耗自適應(yīng)聚類路由協(xié)議

陳錫劍，程良倫

(廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣州 510006)

1 概述

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)是由部署在監(jiān)測(cè)區(qū)的大量微型、低成本、低功耗的傳感器節(jié)點(diǎn)組成的無(wú)線網(wǎng)絡(luò)。由于在無(wú)線傳感器網(wǎng)絡(luò)中硬件節(jié)點(diǎn)一般采用能量有限的電池供電，其計(jì)算能力和通信能力往往十分有限，因此除了要求有低功耗的硬件系統(tǒng)，還需要有效節(jié)能的路由協(xié)議。一個(gè)好的路由協(xié)議能降低單個(gè)節(jié)點(diǎn)的能量消耗，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)能量的均衡消耗，從而延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存期。

目前，研究人員根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)、路由協(xié)議自身特點(diǎn)和應(yīng)用類型，將路由協(xié)議分為以下4大類型[1]：以數(shù)據(jù)為中心的路由協(xié)議，基于層次結(jié)構(gòu)的路由協(xié)議，基于地理信息的路由協(xié)議和基于多路徑的路由協(xié)議。低功耗自適應(yīng)集簇分層型(Low Energy Adaptive Clustering Hierarchy,LEACH)路由協(xié)議是基于能量有效、層次結(jié)構(gòu)路由協(xié)議的典型代表，是在文獻(xiàn)[2]中提出的一種基于概率的低功耗自適應(yīng)分簇協(xié)議，其最大優(yōu)點(diǎn)在于它是一種完全分布式的路由，無(wú)需網(wǎng)絡(luò)全局信息。但也有不足之處，如不能保證簇首的均勻分布，簇首節(jié)點(diǎn)與匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))的單跳通信方式限制網(wǎng)絡(luò)規(guī)模。針對(duì) LEACH的不足，國(guó)內(nèi)外研究人員對(duì)其進(jìn)行了各種改進(jìn)，如傳感信息系統(tǒng)高效聚集協(xié)議(Power-efficient Gathering in Sensor Information System,PEGASIS)[3-4]、改進(jìn) LEACH協(xié)議(Advanced LEACH,ALEACH)[5]、分區(qū)自治的多跳路由協(xié)議(Autonomous Zonebased Multi-hop Routing Protocol, AZM-LEACH)[6]、備用管理的 LEACH協(xié)議(LEACH-SM)[7-8]等。其中，大部分算法是對(duì)簇首選擇方法和簇間數(shù)據(jù)通信方式進(jìn)行研究，而對(duì)簇首的選擇方法依然是單純地沿用 LEACH的基于概率的選擇方法，對(duì)整個(gè)區(qū)域能量的空間分布以及能量中心的遷移欠乏考慮，未能從空間上保證網(wǎng)絡(luò)能量的均勻分布。

本文引入能量中心的概念，提出一種基于區(qū)域控制的低功耗自適應(yīng)聚類路由協(xié)議(Low Energy Consumption Adaptive Clustering Routing Protocol Based on Zone Control,ZC-LEACH)。該協(xié)議通過(guò)基于能量中心的區(qū)域劃分和控制，建立簇首間多跳與單跳相結(jié)合的通信路由，在擴(kuò)大網(wǎng)絡(luò)規(guī)模的同時(shí)，解決網(wǎng)絡(luò)節(jié)點(diǎn)能耗不均衡問(wèn)題。

2 LEACH協(xié)議分析

LEACH是第一個(gè)被提出的聚類路由協(xié)議。它打破了原有成簇算法中固定簇頭的思想，采用簇首隨機(jī)輪循機(jī)制，將能量負(fù)載均勻分布到網(wǎng)絡(luò)的節(jié)點(diǎn)，從而提升簇狀無(wú)線傳感器網(wǎng)絡(luò)的性能。圖1為L(zhǎng)EACH路由協(xié)議拓?fù)浣Y(jié)構(gòu)。

圖1 LEACH路由協(xié)議拓?fù)浣Y(jié)構(gòu)

LEACH的執(zhí)行過(guò)程是周期性的，每一個(gè)周期成為輪，每輪循環(huán)分為簇建立階段和穩(wěn)定狀態(tài)階段。在簇的建立階段，節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇首；在穩(wěn)定狀態(tài)階段，簇頭節(jié)點(diǎn)接收簇內(nèi)非簇首節(jié)點(diǎn)的數(shù)據(jù)，并進(jìn)行數(shù)據(jù)融合，然后把融合后的結(jié)果發(fā)送到Sink節(jié)點(diǎn)。

LEACH協(xié)議能夠保證各節(jié)點(diǎn)等概率的擔(dān)任簇首節(jié)點(diǎn)，使網(wǎng)絡(luò)的節(jié)點(diǎn)相對(duì)均勻地消耗能量，從而降低能量消耗，提高網(wǎng)絡(luò)整體生存時(shí)間。但是，LEACH有以下2點(diǎn)不足：

(1)沒有考慮全網(wǎng)絡(luò)區(qū)域能量的密集程度和能量中心的偏移，在某些輪中，存在分簇不合理情況。

(2)簇首在傳輸數(shù)據(jù)時(shí)采用單跳傳輸方式，即各個(gè)簇首之間沒有通信，而是各自直接將數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)，導(dǎo)致距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇頭消耗較大的能量，部分簇頭過(guò)早死亡。

3 ZC-LEACH協(xié)議

3.1 區(qū)域控制方法

ZC-LEACH協(xié)議引入的區(qū)域概念，不同于簇的概念。這里的區(qū)域是空間幾何區(qū)域和能量分布區(qū)域的統(tǒng)稱。從空間幾何角度，節(jié)點(diǎn)離散分布在監(jiān)測(cè)區(qū)中，可根據(jù)研究的問(wèn)題對(duì)其進(jìn)行劃分，形成幾何空間；從能量分布角度，節(jié)點(diǎn)在網(wǎng)絡(luò)中的能量并非一致，因?yàn)闀r(shí)間和監(jiān)測(cè)區(qū)性質(zhì)而有大差異，所以就存在空間能量密度的不均，構(gòu)成能量區(qū)域(即能量區(qū)域內(nèi)各個(gè)節(jié)點(diǎn)能量相同或接近)。所謂區(qū)域控制，就是根據(jù)節(jié)點(diǎn)能量在空間的動(dòng)態(tài)分布情況確定能量中心，并通過(guò)能量中心來(lái)控制區(qū)域的劃分。

3.1.1 能量中心

設(shè)在 M×M 區(qū)域內(nèi)節(jié)點(diǎn)分布，即能量中心偏移情況如圖2所示。

圖2 能量中心偏移情況

設(shè)節(jié)點(diǎn)(xi, yi)的能量為Ei，區(qū)域內(nèi)所有節(jié)點(diǎn)的總能量大小為E。類比于物體質(zhì)心，定義能量中心：

其中， E=∑Ei。坐標(biāo)(x,y)即為能量中心。能量中心可以是某一實(shí)際節(jié)點(diǎn)，也可以是假設(shè)想象的點(diǎn)，它反映的是該區(qū)域能量最集中處。由于節(jié)點(diǎn)能量是隨機(jī)分布的，因此可近似認(rèn)為區(qū)域的能量從能量中心向外徑向遞減。

能量中心位置不是固定不變的，會(huì)隨著節(jié)點(diǎn)能量的衰減或死亡而發(fā)生偏移，如圖2所示，能量中心從C1轉(zhuǎn)移到C2。這反映了整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)密度和能量重心的遷移。

3.1.2 區(qū)域劃分

設(shè)M×M區(qū)域的能量中心為C(x,y)，區(qū)域劃分的個(gè)數(shù)為N。以C為圓心，做半徑為ε的圓，表示為(C,ε)。所有區(qū)域劃分線都經(jīng)過(guò)能量中心C，起始劃分線與x軸的夾角可任意選取。這樣，圓(C,ε)均等地劃分為N份，每份圓心角為2π/N。若延長(zhǎng)劃分線，則對(duì)整個(gè)區(qū)域劃分為 N份，區(qū)域劃分如圖3所示。

圖3 區(qū)域劃分

由于網(wǎng)絡(luò)節(jié)點(diǎn)及其能量隨機(jī)分布，基于能量中心的區(qū)域劃分將整個(gè)網(wǎng)絡(luò)區(qū)域劃分為能量分布近似的N個(gè)區(qū)域，即每個(gè)區(qū)域的能量平均值滿足：

3.2 簇首選擇和分簇

在LEACH協(xié)議中，簇首的選擇和分簇是針對(duì)整個(gè)網(wǎng)絡(luò)區(qū)域的，而這里簇首選擇和分簇則是在劃分區(qū)域中相對(duì)獨(dú)立完成。

3.2.1 簇首選擇

在傳統(tǒng)的LEACH協(xié)議中，每輪選擇約為PoptN個(gè)簇首，其中，N為節(jié)點(diǎn)個(gè)數(shù)；Popt為簇首在所有節(jié)點(diǎn)中所占的比例。每個(gè)節(jié)點(diǎn)Si由閾值T(Si)來(lái)決定是否成為簇首節(jié)點(diǎn)，即對(duì)節(jié)點(diǎn)Si，隨機(jī)產(chǎn)生[0, 1]隨機(jī)數(shù)，與閾值T(Si)比較，若該隨機(jī)數(shù)小于T(n)，則節(jié)點(diǎn)Si在當(dāng)前輪成為簇首。閾值T(Si)計(jì)算公式如下：

其中，r為當(dāng)前輪數(shù)；G為候選簇首頭集(前r?1輪內(nèi)未擔(dān)任過(guò)簇首的節(jié)點(diǎn)集)。

考慮節(jié)點(diǎn)當(dāng)前的剩余能量、節(jié)點(diǎn)臨近數(shù)目(通信半徑內(nèi)節(jié)點(diǎn))及節(jié)點(diǎn)有未充當(dāng)簇首的次數(shù)[9]，式(3)做以下改進(jìn)：

其中：

其中， E si_cuttent表示當(dāng)前節(jié)點(diǎn)剩余能量； E si_max表示節(jié)點(diǎn)初始能量。

3.2.2 分簇

分簇的方法與傳統(tǒng)的LEACH協(xié)議基本相同，只是這里分簇是在以劃分區(qū)域{I, II,…}中分別進(jìn)行，即在每個(gè)已劃分的區(qū)域內(nèi)采用LEACH協(xié)議分簇。基于區(qū)域劃分的分簇結(jié)果如圖4所示。

圖4 基于區(qū)域劃分的分簇結(jié)果

3.3 簇間數(shù)據(jù)傳輸

在LEACH協(xié)議中，簇首節(jié)點(diǎn)融合簇內(nèi)非簇首節(jié)點(diǎn)的數(shù)據(jù)后，將結(jié)果直接發(fā)送到Sink節(jié)點(diǎn)，即采用單跳通信方式。這樣，距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇首節(jié)點(diǎn)則消耗較多能量。另外，目前的節(jié)點(diǎn)覆蓋能力一般為200 m左右[10]，這個(gè)距離會(huì)限制傳感節(jié)點(diǎn)的部署范圍，不能進(jìn)行大規(guī)模的監(jiān)測(cè)。據(jù)于此，ZC-LEACH協(xié)議提供簇間通信傳輸機(jī)制。

ZC-LEACH簇間數(shù)據(jù)傳輸機(jī)制采用多跳通信方式，選取能量中心或者附近簇首作為所有的簇首匯聚節(jié)點(diǎn)。因?yàn)榇厥讌R聚節(jié)點(diǎn)能量消耗較多，所以必須由能量充足的簇首節(jié)點(diǎn)擔(dān)任。顯然，能量中心或者其附近能量最大者能擔(dān)任簇首匯聚節(jié)點(diǎn)。

簇間多跳路由通信如圖5所示。

圖5 簇間多跳路由通信

設(shè)在圓(C,ε)內(nèi)有 3個(gè)簇首節(jié)點(diǎn)，依次為 CH1、CH2、CH3。不妨設(shè)CH3的剩余能量最大，則推舉CH3作為簇首匯聚節(jié)點(diǎn)，其他簇首數(shù)據(jù)通過(guò)多跳路由傳送到 CH3，最后由CH3將數(shù)據(jù)發(fā)送到Sink節(jié)點(diǎn)。簇首節(jié)點(diǎn)分布區(qū)域被分為A區(qū)、B區(qū)和C區(qū)，路由原則是從最低區(qū)向最高區(qū)跳轉(zhuǎn)，且遵循最近原則。如簇首 1屬于 C區(qū)，則其數(shù)據(jù)只能向B區(qū)簇首傳輸，而不能向同屬于B區(qū)的a點(diǎn)傳輸；另外，因?yàn)榇厥?比簇首b更接近簇首1，所以簇首1數(shù)據(jù)向簇首2傳輸。

3.4 協(xié)議描述

根據(jù)以上分析，對(duì)ZC-LEACH協(xié)議描述如下：

(1)每個(gè)節(jié)點(diǎn)廣播自己的地理位置和能量，并根據(jù)式(1)來(lái)確定能量中心C。

(2)根據(jù)預(yù)定的半徑 ε和區(qū)域劃分個(gè)數(shù) N，結(jié)合能量中心坐標(biāo)，按逆時(shí)針依次給劃分的子區(qū)域編號(hào)1,2,…,N。該編號(hào)作為區(qū)域識(shí)別碼。

(3)在每個(gè)子區(qū)域中采用 LEACH協(xié)議進(jìn)行簇首選擇和分簇。

(4)以能量中心C為圓心，以半徑RA、RB、RC為半徑，劃分A區(qū)、B區(qū)和C區(qū)，建立簇間路由。

(5)進(jìn)入數(shù)據(jù)傳輸階段，非簇首采集數(shù)據(jù)發(fā)送到對(duì)應(yīng)的簇首節(jié)點(diǎn)，簇首對(duì)數(shù)據(jù)進(jìn)行融合處理后交給下一跳節(jié)點(diǎn)，直至到達(dá)簇首匯聚節(jié)點(diǎn)，最后到達(dá)Sink節(jié)點(diǎn)。循環(huán)步驟(1)～步驟(5)，進(jìn)入下一輪通信。

4 節(jié)點(diǎn)能量消耗模型

在ZC-LEACH協(xié)議中，使用第一順序節(jié)點(diǎn)收發(fā)數(shù)據(jù)包能耗模型[11]，如圖 6所示。該模型對(duì)無(wú)線傳感器網(wǎng)絡(luò)環(huán)境假設(shè)如下：

(1)基站(Base Station, BS)位置和其他傳感器節(jié)點(diǎn)位置固定。

(2)網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)地位完全平等，并且初始能量相等。

(3)無(wú)線電信號(hào)在各個(gè)方向上消耗的能量相同，通信的半徑可以動(dòng)態(tài)調(diào)整。

圖6 節(jié)點(diǎn)收發(fā)數(shù)據(jù)包能耗模型

節(jié)點(diǎn)之間依靠RF信號(hào)進(jìn)行無(wú)線通信，發(fā)送數(shù)據(jù)包的功能包括發(fā)射電路能耗 ETx-elec(l)和放大電路能耗 ETx-amp(l, d )兩部分，由文獻(xiàn)[12]可知，節(jié)點(diǎn)將長(zhǎng)度為l的數(shù)據(jù)包發(fā)送給距離為d處的節(jié)點(diǎn)能耗為：

其中，d0為閾值距離，且?。?/p>

其中，Eelec、εfs、εamp由實(shí)際節(jié)點(diǎn)性能決定。

接收數(shù)據(jù)包能耗為：

簇首將 n個(gè)長(zhǎng)度為l的成員節(jié)點(diǎn)數(shù)據(jù)包融合為一個(gè)長(zhǎng)度為l的數(shù)據(jù)包的能耗為：

其中，EDA為融合l數(shù)據(jù)包的能耗。

5 仿真實(shí)驗(yàn)

為了評(píng)估 ZC-LEACH協(xié)議的性能，本文通過(guò) Matlab仿真平臺(tái)下的模擬實(shí)驗(yàn)將其與現(xiàn)有的 LEACH協(xié)議進(jìn)行比較分析。

5.1 仿真環(huán)境

設(shè)監(jiān)測(cè)區(qū)域?yàn)?00 m×100 m的矩形區(qū)域，仿真實(shí)驗(yàn)的網(wǎng)絡(luò)參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)的網(wǎng)絡(luò)參數(shù)

5.2 算法性能評(píng)價(jià)指標(biāo)

在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的能量是有限的，路由協(xié)議性能的好與壞關(guān)鍵在于是否能夠延長(zhǎng)網(wǎng)絡(luò)生命周期。本文從網(wǎng)絡(luò)的存活時(shí)間和網(wǎng)絡(luò)節(jié)點(diǎn)能量分布 2個(gè)指標(biāo)來(lái)評(píng)價(jià)算法性能優(yōu)劣。

5.3 仿真結(jié)果與分析

在相同的實(shí)驗(yàn)環(huán)境下，對(duì)LEACH協(xié)議和本文協(xié)議進(jìn)行仿真，網(wǎng)絡(luò)存活時(shí)間比較如圖7所示。在LEACH協(xié)議下，網(wǎng)絡(luò)節(jié)點(diǎn)在第500 s時(shí)開始衰減，且衰減率較大，而在本文協(xié)議下的網(wǎng)絡(luò)節(jié)點(diǎn)開始衰減時(shí)間為第700 s左右，且節(jié)點(diǎn)死亡速率相對(duì)平緩，其網(wǎng)絡(luò)存活時(shí)間比LEACH協(xié)議的網(wǎng)絡(luò)存活時(shí)間明顯增加。

圖7 網(wǎng)絡(luò)存活時(shí)間比較

圖8為整個(gè)區(qū)域剩余能量在第40輪將開始時(shí)的分布。由圖8可知，網(wǎng)絡(luò)平均能量為0.8 J左右(節(jié)點(diǎn)初始能量為2 J，見表1)。而在能量中心附近，出現(xiàn)一小部分剩余能量較多的節(jié)點(diǎn)，能量最多者達(dá)到1.5 J，這些節(jié)點(diǎn)正是該輪簇首匯聚節(jié)點(diǎn)的候選節(jié)點(diǎn)?？梢?，基于能量中心的區(qū)域劃分能夠使整個(gè)區(qū)域能量達(dá)到均衡。

圖8 第40輪區(qū)域剩余能量分布

本文協(xié)議不僅考慮節(jié)點(diǎn)能量消耗的均衡，還考慮整個(gè)網(wǎng)絡(luò)區(qū)域節(jié)點(diǎn)剩余能量的分布。而簇首間多跳路由通信方式正是通過(guò)能量中心合理地利用這種分布，由剩余能量大的節(jié)點(diǎn)充當(dāng)簇首的匯聚節(jié)點(diǎn)，既保證通信的可靠，又保證了整個(gè)網(wǎng)絡(luò)區(qū)域的能量分布均衡。2種協(xié)議網(wǎng)絡(luò)剩余能量的變化曲線如圖9所示。

圖9 網(wǎng)絡(luò)剩余能量對(duì)比

由圖9可知，與LEACH協(xié)議相對(duì)比，本文協(xié)議的網(wǎng)絡(luò)能量衰減速率更加緩慢，從而能夠有效地延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間。

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

本文提出一種基于區(qū)域控制的低功耗自適應(yīng)聚類路由協(xié)議。該路由協(xié)議不是以單純的概率方法選擇簇首，而是先根據(jù)網(wǎng)絡(luò)區(qū)域能量的分布來(lái)確定能量中心，然后采取區(qū)域劃分控制方法，且簇間多跳通信方式能合理利用這種劃分，保證整個(gè)網(wǎng)絡(luò)區(qū)域的能量均衡且衰減緩慢。在相同的實(shí)驗(yàn)環(huán)境下，利用Matlab對(duì)傳統(tǒng)LEACH協(xié)議和本文協(xié)議進(jìn)行仿真，結(jié)果表明，該協(xié)議在均衡網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間等方面更具有優(yōu)越性。

本文協(xié)議僅通過(guò)仿真手段驗(yàn)證其可行性和優(yōu)越性，而尚未在物理節(jié)點(diǎn)所組成的網(wǎng)絡(luò)中實(shí)現(xiàn)。在實(shí)際網(wǎng)絡(luò)中，節(jié)點(diǎn)能量消耗模型、節(jié)點(diǎn)分布規(guī)模、環(huán)境等都需要考慮。因此，今后的研究方向是將該協(xié)議應(yīng)用于實(shí)際無(wú)線傳感器網(wǎng)絡(luò)中，并分析仿真環(huán)境下尚未考慮的影響因素。

[1]黃海平, 沙 超, 蔣凌云, 等.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用[M].北京: 人民郵電出版社, 2011.

[2]Heinzelman W, Chandrakasan A, Balakerishnan H.Energyefficient Communication Protocol for Wireless Microsensor Networks[C]//Proc.of the 33rd Hawaii Inernational Conference on Systems Science.[S.l.]: IEEE Press, 2000.

[3]Liu Tao, Li Feng.Power-efficient Clustering Routing Protocol Based on Applications in Wireless Sensor Networks[C]//Proc.of the 5th Inernational Conference on Wireless Communications Networking and Mobile Computing.Beijing, China:[s.n.], 2009.

[4]Aliouat Z, Aliouat M.Efficient Management of Energy Budget for PEGASIS Routing Protocol[C]//Proc.of the 6th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications.[S.l.]: IEEE Press, 2012.

[5]Ali M S, Tanay D, Rahul B.ALEACH: Advanced LEACH Routing Protocol for Wireless Microsensor Networks[C]//Proc.of the 5th International Conference on Electrical and Computer Engineering.Dhaka, Bangladesh: [s.n.], 2008.

[6]顧躍躍, 白光偉, 陶金晶.AZM-LEACH: 一種分區(qū)自治的多跳路由協(xié)議機(jī)制[J].計(jì)算機(jī)工程與應(yīng)用, 2011, 47(20):58-61.

[7]Bakr B A, Lilien L.LEACH-SM: A Protocol for Extending Wireless Sensor Network Lifetime by Management of Spare Nodes[C]//Proc.of Modeling and Optimization in Mobile Ad Hoc and Wireless Networks.Princeton, USA: [s.n.], 2011.

[8]Bakr B A, Lilien L.Extending Wireless Sensor Network Lifetime in the LEACH-SM Protocol by Spare Selection[C]//Proc.of the 5th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing.[S.l.]:IEEE Press, 2011.

[9]馬艷紅, 鄒學(xué)玉.對(duì)無(wú)線傳感器網(wǎng)絡(luò)的LEACH協(xié)議的改進(jìn)研究[J].長(zhǎng)江大學(xué)學(xué)報(bào): 自然科學(xué)版, 2011, 8(8): 94-97.

[10]張吉贊.WSN中節(jié)點(diǎn)覆蓋分層下的多路徑路由協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用, 2010, 46(8): 87-91.

[11]顧明霞.一種新的基于LEACH的WSN路由算法[J].計(jì)算機(jī)仿真, 2011, 28(8): 129-133.

[12]Wendi B H, Anantha P C, Balakrishnan H.An Applicationspecific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communicaitons,2002, 1(4): 660-670.