基于区域控制的低功耗自适应聚类路由协议

陈锡剑，程良伦

(广东工业大学自动化学院，广州 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.