基于混合天线的能量有效异构WSN 分簇算法

孙宝霞，王卫星，雷 刚，郑少雄

（1.华南农业大学 工程学院，广东 广州510642；2.广东工程职业技术学院 电梯技术学院，广东 广州510520；3.华南农业大学 南方农业机械与装备关键技术省部共建教育部重点实验室，广东 广州510642）

0 引 言

无线传感器网络的能量主要消耗在路由上［1，2］，与平面路由算法相比，分簇路由算法具有明显优势，如能量有效、扩展性强等，因此更适合于无线传感器网络的应用特点［3－5］。LEACH （Low－energy adaptive clustering hierarchy）协议是典型的分布式分簇算法［6］，但在簇头选取过程中没有考虑节点剩余能量，以至远离基站sink的节点过早死亡，网络能量消耗不均衡。在此基础上进行改进，根据节点剩余能量选举簇头，并采用模拟退火算法对网络进行分簇，提出了LEACH－C协议［7］。

WSN 可分为同构网和异构网2种，同构网中所有传感器节点的硬件和参数配置均相同，反之则构成异构网。当前有关WSN 路由算法研究大多考虑同构网，上述LEACH和LEACH－C协议均适用于同构网络。但在实际应用中，同构网则极少存在［8］。SEP 协议［9］提出了一个二级异构网络模型，网络中包含高级节点和普通节点，高级节点具有高初始能量，通过加权概率的设置提高高级节点当选为簇头的机率，从而有效延长了网络的稳定周期。将二级异构网络扩展为多级，文献 ［10］提出了一个分布式能量有效分簇算法DEEC （distributed energy－efficient clustering algorithm），在加权概率设置时考虑平均能量和节点剩余能量以均衡节点能量消耗。但文献 ［9，10］只考虑了节点剩余能量，没有考虑距离因素，因此不能保证良好的簇头布局。

目前大部分算法都是基于全向天线技术的，近年来，在无线传感器网络中使用定向天线的研究也逐渐被关注［11］。与全向天线相比，定向天线具有提高网络空间复用率、增大网络覆盖区域、节约能量消耗等优点［12］。

本文提出了一种基于混合天线能量有效的异构WSN 分簇算法ECHH （energy－efficient clustering algorithm based on the hybrid antenna for heterogeneous wireless sensor networks），传感器节点同时配置全向天线和定向天线，簇头与基站通信时自动切换至定向模式以提高通信距离，在初始簇结构基础上基于能量和距离选取新簇头，当死亡节点比例超过设定阈值时，存活节点自动切换至定向模式与sink直接进行通信。仿真结果表明，ECHH 算法能有效均衡网络能量消耗，提高网络稳定周期及稳定周期比例。

1 算法设计

1.1 网络模型

假定N 个传感器节点随机散布在一个M×M 的正方形区域内，且该区域网络内具有以下特性：

（1）静态部署网络，各节点具有唯一ID 号，具备实时感知自身位置信息和能量信息功能；

（2）多级异构节点能量，根据位置信息设置各节点初始能量，且能量不能补充；

（3）基站 （sink节点）部署在网络覆盖区域的中心位置，且具有充足的能量；

（4）节点具有对称的无线信道，且发射功率固定。

（5）所有节点具有相同的计算处理能力，且可根据应用需要进行全向天线和定向天线的自由切换；

无线传感器网络中，因发送端与接收端的距离d不同，则采用的能量消耗模型就不同［13］，其能量损耗模型如图1所示。

图1 无线传感器网络能量损耗模型

当节点a向距离为d 的节点b发送lbit的数据包时，节点a消耗的能量为

式中：Eelec——节点发射电路的损耗，当传输距离小于阈值d0时，能量损耗采用自由空间 （free space）传播模型，否则采用多路径衰减 （multi－path fading）模型［13］。Efs、Emp分别表示2种模型功率放大的能量损耗。节点b接收来自节点a 的lbit的数据包时消耗的能量为

簇头在分簇算法中起着关键作用，收集簇内节点信息并进行数据融合，再将融合后数据发送至基站，故簇头在一次数据传递过程中所消耗的能量为

式中：k——一簇内节点数，dBS——簇头到基站的距离，EBS——簇头进行数据融合消耗的能量。

ECHH 算法中当簇头与sink 通信时会切换至定向模式，故需对式 （3）进行改进

式中：m——全向天线向定向天线切换的能量消耗转换系数。

在同样的通信距离下，全天天线需要提高天线增益，以克服路径损耗，但使用定向天线可使发射功率明显降低［14］，此外，发射功率Pdir∝2πr （1－cos（θ／ 2） ），波束角度θ越小，能量消耗就越少。因此，定向天线减少了与波束角度外节点通信的可能性，增加了与波束角度内较远节点通信的概率。本算法设定定向天线和全向天线在水平方向上的波束角度分别为60°和360°。

1.2 ECHH 算法描述

分簇路由算法分为竞选簇头、成簇以及簇间通信3个阶段，科学合理的选取簇头是提高网络性能的有效途径。先前提到的分簇算法 （如LEACH、LEACH－C）只适用于WSN 节点均匀分布的情况，然而，在实际应用中，传感器节点通常是随机布置的，其分布并不均匀，从而导致拓扑结构不均衡，部分节点因能量消耗过快而死亡。本文主要从节点剩余能量和位置的角度出发，避免能量低和远离基站的节点当选为簇头，初始网络条件下，设定簇头均匀分布于网络区域内以均衡网络能量消耗，同时，当簇头向基站发送数据时，自动切换至定向天线模式以减少能量消耗。算法主要分为以下3个阶段：

第一阶段：形成初始的簇结构阶段。

首先对整个网络设定初始的簇头比例 （如8%），为实现簇头的均匀分布，初始网络条件下，设定初始簇头均匀分布于网络区域内，在节点通信半径内完成簇建立阶段，节点选择距离自己最近的初始簇头并加入该簇，sink节点位于网络正中心，设定sink节点附近的节点将直接与其进行通信，初始网络条件下 （r＝0）簇结构如图2 （a）所示。当簇头向基站发送数据时，自动由全向天线模式切换至定向天线模式，其余节点均工作于全向天线模式。

本算法节点能量为多级异构，根据位置信息设置各节点初始能量，各节点初始能量分配如下所示

式中：S（i）·E——节点i的初始能量，i——节点ID 号，di－sink——节点i到sink 节点的距离，E0——节点初始能量基本值，各节点初始能量在 （0.5～2.6）E0范围内随di－sink大小而变化。由式 （4）可知：S（i）·E 正比于di－sink，距离sink越远的节点，其初始能量越高，从而有效地避免了远离sink的节点过早的死亡。

第二阶段：形成轮换簇头的簇结构阶段。

当初始簇头剩余能量低于设定阈值时，网络簇结构发生变化，在以初始簇头为圆心，R 为半径的圆形区域内选取剩余能量最大的节点成为新簇头，在新簇头通信半径内完成簇建立阶段，节点选择距离自己最近的新簇头并加入该簇。当网络中死亡节点比例大于60%时，R 值增大为原来的1.5倍。在原簇头附近选取能量最大的节点成为新簇头，保证了网络的簇头比例及簇头分布的均匀性，从而均衡了网络的能量消耗，有效地提高了网络的稳定周期，不同轮数下的网络簇结构如图2所示。

图2 不同轮数下网络簇结构

第三阶段：节点与基站直接通信的网络结构阶段。

当大部分节点死亡时，网络已很难形成合理的簇结构。本文设定当死亡节点比例达到85%时，此时存活节点由全向天线模式切换至定向天线模式，并与sink直接进行通信，直至死亡节点比例达到95%，此时认为网络死亡。此阶段存活节点向sink发送lbit数据时能量消耗为

2 仿真与分析

本文主要从网络的适应性、能量消耗均衡性两方面对算法的网络性能进行评价分析。在Matlab R2009a下对该算法进行模拟仿真，并与LEACH、LEACH－E及DEEC 算法进行比较分析，仿真实验中各参数设置见表1。

表1 仿真实验参数设置

2.1 网络能量消耗均衡性

本文主要从稳定周期，不稳定周期及稳定周期比例等几方面来分析评价网络的能量消耗均衡性。网络寿命分稳定周期 （stability period，SP）和不稳定周期 （instability period，ISP）2个阶段。稳定周期是指从网络仿真开始到第一个节点死亡的轮数，不稳定周期是指从第一个节点死亡到死亡节点比例达95%的轮数。

图3、图4分别是稳定周期及稳定周期比例和死亡节点变化情况，由图可知：与LEACH、LEACH－E 及DEEC 算法相比，ECHH 算法的稳定周期分别提高了216%、198%和129%，不稳定周期分别降低了153%、136 和102%，稳定周期比例分别提高了164%、142%和86%。当死亡节点比例分别为20%、50%和80%时，ECHH 算法中相应轮数都远远大于其它3种算法，由此可知，ECHH 算法在均衡网络能量损耗，延长了网络的稳定周期和网络寿命等方面具有显著优势。

图3 稳定周期及稳定周期比例

图4 死亡节点变化情况

2.2 网络的适应性

改变网络内节点个数n，对比分析以上4种算法的稳定周期比例，如图5所示，由图可知，改变网络中节点数量，ECHH 算法依然具有良好的稳定周期比例，由此可得，该算法具有良好的网络适应性。

图5 稳定周期比例随节点数量变化情况

3 结束语

本文提出一种基于混合天线的能量有效异构WSN 分簇算法ECHH，传感器节点同时配置全向天线和定向天线，簇头与基站通信时自动切换至定向模式以提高通信距离，减少能量损耗，在初始簇结构基础上基于能量和距离选取新簇头，当死亡节点比例超过设定阈值时，存活节点自动切换至定向模式与sink 直接进行通信。仿真结果表明，ECHH 算法有效地延长网络的稳定周期，缩短不稳定周期，在均衡网络能量消耗方面效果显著，同时具有良好的网络适应性。

［1］SUN Liming，LI Jianzhong，CHEN Yu.Wireless sensor network ［M］.Beijing：Tsinghua University Press，2005：3－24（in Chinese）. ［孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版社，2005：3－24.］

［2］LI Shuhua，LIU Zhenyu，LI Yingqiu.Energy adaptive clustering in wireless sensor network routing protocol［J］.Computer Engineering and Design，2010，31 （3）：504－507 （in Chinese）.［李树华，刘振宇，李迎秋.能量自适应的无线传感器网络分簇路由协议 ［J］.计算机工程与设计，2010，31 （3）：504－507.］

［3］Li Fangmin，Xu Wenjun，Liu Xinhua，et al.A real－time energy－aware cluster－based routing protocol for wireless sensor and actor networks ［J］.Journal of Computer Research and Development，2008，45 （1）：26－33.

［4］SHEN Bo，ZHANG Shiyong，ZHONG Yiping.Cluster－based routing protocols for wireless sensor networks［J］.Journal of Software，2006，17 （7）：1588－1600 （in Chinese）. ［沈波，张世永，钟亦平.无线传感器网络分簇路由协议 ［J］.软件学报，2006，17 （7）：1588－1600.］

［5］ZHENG Zenwei，WU Zhaohui.Some wireless sensor network routing protocols in the comparative study ［J］.Computer Engineering and Design，2003，24 （9）：28－31 （in Chinese）.［郑增威，吴朝晖.若干无线传感器网络路由协议比较研究［J］.计算机工程与设计，2003，24 （9）：28－31.］

［6］SHEN Bo，ZHANG Shiyong.Wireless sensor network clumping routing protocol［J］.Journal of Software，2006，17 （7）：1588－1600 （in Chinese）.［沈波，张世永.无线传感器网络分簇路由协议［J］.软件学报，2006，17 （7）：1588－1600.］

［7］NIU Weiwei，GAO Tiegang.Improvement algorithm for simulated annealing in LEACH－C protocol［J］.Computer Engineering and Design，2011，32 （6）：1869－1917 （in Chinese）.［牛伟伟，高铁杠.LEACH－C 协议中模拟退火算法的改进 ［J］.计算机工程与设计，2011，32 （6）：1869－1917.］

［8］Li Xiaoya，Huang Daopin，Sun Zonghai.A routing protocol for balancing energy consumption in heterogeneous wireless sensor networks［C］／／The 3rd International Conference on Mobile Ad－hoc and Sensor Networks.Beijing：Springer Verlag，2007：79－88.

［9］CHEN Aibin，ZHANG Luyong，XIA Xinlan，et al.Study on energy－heterogeneous clustering algorithm in wireless sensor network［J］.Radio Engineering，2012，42 （1）：7－10（in Chinese）.［陈爱斌，张陆勇，夏新兰，等.无线传感器网络能量异构分簇算法的研究［J］.无线电工程，2012，42 （1）：7－10.］

［10］HUANG Xiaofeng，LIU Guangzhong.The improvement of DEEC protocol in wireless network ［J］.Microcomputer and Its Applications，2013，32 （10）：51－53 （in Chinese）. ［黄晓峰，刘广钟.无线网络中DEEC 协议的改进 ［J］.微型机与应用，2013，32 （10）：51－53.］

［11］LIU Jun，SUN Qian，LI Shaohua，et al.Topology control algorithm based on directional antenna in wireless ad hoc networks［J］.Journal of Northeastern University （Natural Science），2012，33 （9）：1257－1260（in Chinese）. ［刘军，孙茜，李少华，等.基于定向天线的无线自组网拓扑控制算法 ［J］.东北大学学报（自然科学版），2012，33 （9）：1257－1260.］

［12］DING Yanrong.Media access control protocol in hybrid wireless Ad Hoc network based on directional and omni－directional antennas［D］.Changsha：National University of Defense Technology，2010：1－5 （in Chinese）.［丁艳荣.基于定向和全向天线的混合式无线Ad Hoc网络中MAC 协议的研究［D］.长沙：国防科学技术大学，2010：1－5.］

［13］Doshi S，Bhandare S，Brown T.An on demand minimum energy routing protocol for a wireless ad hoc network ［J］.ACM SIGMOBIL E Mobile Computing and Communications Review，2002，6 （3）：50－66.

［14］YANG Guangsong，GENG Xu.Energy－efficient route finding mechanism based on directional antenna in wireless sensor network ［J］.Computer Engineering，2010，36 （22）：91－93（in Chinese）.［杨光松，耿旭.WSN 中基于定向天线的节能寻路机制 ［J］.计算机工程，2010，36 （22）：91－93.］