基于區域控制的低功耗自適應聚類路由協議

陳錫劍，程良倫

(廣東工業大學自動化學院，廣州 510006)

1 概述

無線傳感器網絡(Wireless Sensor Network, WSN)是由部署在監測區的大量微型、低成本、低功耗的傳感器節點組成的無線網絡。由于在無線傳感器網絡中硬件節點一般采用能量有限的電池供電，其計算能力和通信能力往往十分有限，因此除了要求有低功耗的硬件系統，還需要有效節能的路由協議。一個好的路由協議能降低單個節點的能量消耗，實現整個網絡能量的均衡消耗，從而延長整個網絡的生存期。

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

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

2 LEACH協議分析

LEACH是第一個被提出的聚類路由協議。它打破了原有成簇算法中固定簇頭的思想，采用簇首隨機輪循機制，將能量負載均勻分布到網絡的節點，從而提升簇狀無線傳感器網絡的性能。圖1為LEACH路由協議拓撲結構。

圖1 LEACH路由協議拓撲結構

LEACH的執行過程是周期性的，每一個周期成為輪，每輪循環分為簇建立階段和穩定狀態階段。在簇的建立階段，節點動態地形成簇，隨機產生簇首；在穩定狀態階段，簇頭節點接收簇內非簇首節點的數據，并進行數據融合，然后把融合后的結果發送到Sink節點。

LEACH協議能夠保證各節點等概率的擔任簇首節點，使網絡的節點相對均勻地消耗能量，從而降低能量消耗，提高網絡整體生存時間。但是，LEACH有以下2點不足：

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

(2)簇首在傳輸數據時采用單跳傳輸方式，即各個簇首之間沒有通信，而是各自直接將數據發送到Sink節點，導致距離Sink節點較遠的簇頭消耗較大的能量，部分簇頭過早死亡。

3 ZC-LEACH協議

3.1 區域控制方法

ZC-LEACH協議引入的區域概念，不同于簇的概念。這里的區域是空間幾何區域和能量分布區域的統稱。從空間幾何角度，節點離散分布在監測區中，可根據研究的問題對其進行劃分，形成幾何空間；從能量分布角度，節點在網絡中的能量并非一致，因為時間和監測區性質而有大差異，所以就存在空間能量密度的不均，構成能量區域(即能量區域內各個節點能量相同或接近)。所謂區域控制，就是根據節點能量在空間的動態分布情況確定能量中心，并通過能量中心來控制區域的劃分。

3.1.1 能量中心

設在 M×M 區域內節點分布，即能量中心偏移情況如圖2所示。

圖2 能量中心偏移情況

設節點(xi, yi)的能量為Ei，區域內所有節點的總能量大小為E。類比于物體質心，定義能量中心：

其中， E=∑Ei。坐標(x,y)即為能量中心。能量中心可以是某一實際節點，也可以是假設想象的點，它反映的是該區域能量最集中處。由于節點能量是隨機分布的，因此可近似認為區域的能量從能量中心向外徑向遞減。

能量中心位置不是固定不變的，會隨著節點能量的衰減或死亡而發生偏移，如圖2所示，能量中心從C1轉移到C2。這反映了整個網絡節點密度和能量重心的遷移。

3.1.2 區域劃分

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

圖3 區域劃分

由于網絡節點及其能量隨機分布，基于能量中心的區域劃分將整個網絡區域劃分為能量分布近似的N個區域，即每個區域的能量平均值滿足：

3.2 簇首選擇和分簇

在LEACH協議中，簇首的選擇和分簇是針對整個網絡區域的，而這里簇首選擇和分簇則是在劃分區域中相對獨立完成。

3.2.1 簇首選擇

在傳統的LEACH協議中，每輪選擇約為PoptN個簇首，其中，N為節點個數；Popt為簇首在所有節點中所占的比例。每個節點Si由閾值T(Si)來決定是否成為簇首節點，即對節點Si，隨機產生[0, 1]隨機數，與閾值T(Si)比較，若該隨機數小于T(n)，則節點Si在當前輪成為簇首。閾值T(Si)計算公式如下：

其中，r為當前輪數；G為候選簇首頭集(前r?1輪內未擔任過簇首的節點集)。

考慮節點當前的剩余能量、節點臨近數目(通信半徑內節點)及節點有未充當簇首的次數[9]，式(3)做以下改進：

其中：

其中， E si_cuttent表示當前節點剩余能量； E si_max表示節點初始能量。

3.2.2 分簇

分簇的方法與傳統的LEACH協議基本相同，只是這里分簇是在以劃分區域{I, II,…}中分別進行，即在每個已劃分的區域內采用LEACH協議分簇。基于區域劃分的分簇結果如圖4所示。

圖4 基于區域劃分的分簇結果

3.3 簇間數據傳輸

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

ZC-LEACH簇間數據傳輸機制采用多跳通信方式，選取能量中心或者附近簇首作為所有的簇首匯聚節點。因為簇首匯聚節點能量消耗較多，所以必須由能量充足的簇首節點擔任。顯然，能量中心或者其附近能量最大者能擔任簇首匯聚節點。

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

圖5 簇間多跳路由通信

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

3.4 協議描述

根據以上分析，對ZC-LEACH協議描述如下：

(1)每個節點廣播自己的地理位置和能量，并根據式(1)來確定能量中心C。

(2)根據預定的半徑 ε和區域劃分個數 N，結合能量中心坐標，按逆時針依次給劃分的子區域編號1,2,…,N。該編號作為區域識別碼。

(3)在每個子區域中采用 LEACH協議進行簇首選擇和分簇。

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

(5)進入數據傳輸階段，非簇首采集數據發送到對應的簇首節點，簇首對數據進行融合處理后交給下一跳節點，直至到達簇首匯聚節點，最后到達Sink節點。循環步驟(1)～步驟(5)，進入下一輪通信。

4 節點能量消耗模型

在ZC-LEACH協議中，使用第一順序節點收發數據包能耗模型[11]，如圖 6所示。該模型對無線傳感器網絡環境假設如下：

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

(2)網絡中所有傳感器節點地位完全平等，并且初始能量相等。

(3)無線電信號在各個方向上消耗的能量相同，通信的半徑可以動態調整。

圖6 節點收發數據包能耗模型

節點之間依靠RF信號進行無線通信，發送數據包的功能包括發射電路能耗 ETx-elec(l)和放大電路能耗 ETx-amp(l, d )兩部分，由文獻[12]可知，節點將長度為l的數據包發送給距離為d處的節點能耗為：

其中，d0為閾值距離，且取：

其中，Eelec、εfs、εamp由實際節點性能決定。

接收數據包能耗為：

簇首將 n個長度為l的成員節點數據包融合為一個長度為l的數據包的能耗為：

其中，EDA為融合l數據包的能耗。

5 仿真實驗

為了評估 ZC-LEACH協議的性能，本文通過 Matlab仿真平臺下的模擬實驗將其與現有的 LEACH協議進行比較分析。

5.1 仿真環境

設監測區域為100 m×100 m的矩形區域，仿真實驗的網絡參數如表1所示。

表1 仿真實驗的網絡參數

5.2 算法性能評價指標

在無線傳感器網絡中，節點的能量是有限的，路由協議性能的好與壞關鍵在于是否能夠延長網絡生命周期。本文從網絡的存活時間和網絡節點能量分布 2個指標來評價算法性能優劣。

5.3 仿真結果與分析

在相同的實驗環境下，對LEACH協議和本文協議進行仿真，網絡存活時間比較如圖7所示。在LEACH協議下，網絡節點在第500 s時開始衰減，且衰減率較大，而在本文協議下的網絡節點開始衰減時間為第700 s左右，且節點死亡速率相對平緩，其網絡存活時間比LEACH協議的網絡存活時間明顯增加。

圖7 網絡存活時間比較

圖8為整個區域剩余能量在第40輪將開始時的分布。由圖8可知，網絡平均能量為0.8 J左右(節點初始能量為2 J，見表1)。而在能量中心附近，出現一小部分剩余能量較多的節點，能量最多者達到1.5 J，這些節點正是該輪簇首匯聚節點的候選節點。可見，基于能量中心的區域劃分能夠使整個區域能量達到均衡。

圖8 第40輪區域剩余能量分布

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

圖9 網絡剩余能量對比

由圖9可知，與LEACH協議相對比，本文協議的網絡能量衰減速率更加緩慢，從而能夠有效地延長網絡存活時間。

6 結束語

本文提出一種基于區域控制的低功耗自適應聚類路由協議。該路由協議不是以單純的概率方法選擇簇首，而是先根據網絡區域能量的分布來確定能量中心，然后采取區域劃分控制方法，且簇間多跳通信方式能合理利用這種劃分，保證整個網絡區域的能量均衡且衰減緩慢。在相同的實驗環境下，利用Matlab對傳統LEACH協議和本文協議進行仿真，結果表明，該協議在均衡網絡能耗、延長網絡存活時間等方面更具有優越性。

本文協議僅通過仿真手段驗證其可行性和優越性，而尚未在物理節點所組成的網絡中實現。在實際網絡中，節點能量消耗模型、節點分布規模、環境等都需要考慮。因此，今后的研究方向是將該協議應用于實際無線傳感器網絡中，并分析仿真環境下尚未考慮的影響因素。

[1]黃海平, 沙 超, 蔣凌云, 等.無線傳感器網絡技術及其應用[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: 一種分區自治的多跳路由協議機制[J].計算機工程與應用, 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]馬艷紅, 鄒學玉.對無線傳感器網絡的LEACH協議的改進研究[J].長江大學學報: 自然科學版, 2011, 8(8): 94-97.

[10]張吉贊.WSN中節點覆蓋分層下的多路徑路由協議[J].計算機工程與應用, 2010, 46(8): 87-91.

[11]顧明霞.一種新的基于LEACH的WSN路由算法[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.