基于LEACH协议的簇头辅助路由算法

张继荣，王文斌，苗国防

（西安邮电大学 通信与信息工程学院，陕西 西安710121）

无线传感器网络节点的能量、计算能力、存储容量非常有限，在大型传感器网络中，无线传感器节点的数量众多，布置密集，受电能制约，路由易于失效，设计满足要求的无线传感器网络路由算法极具挑战性［1］。

传感器节点部署在物理环境中，需要一定的工作寿命，节能是无线传感器网络设计的重要考虑因素。基于分簇的无线传感器网络路由协议凭借良好的扩展性和更高的能量效率受到广泛的关注［2］。分簇是指把整个传感器网络划分为若干个簇，每个簇有一个簇头，簇内非簇头节点把数据发送给簇头，然后由簇头进行数据融合后转发给基站［3］。

低能量自适应分簇分层协议（Low Energy A－daptive Clustering Hierarchy，LEACH）是经典的无线传感器网络分簇路由协议［4］，通过等概率地随机循环选择簇头，将与基站通信的高能耗平均分配到网络的所有节点中，从而延长网络的寿命，但是簇头的负载大于普通节点，扩展性差，不适合大规模网络。混合高效节能分布式分簇（Hybrid Energy Efficient Distributed Clustering，HEED）算法［5］在簇头选择过程中考虑了能量因素，选用剩余能量大的作为簇头，但该算法没有考虑簇头负载过重的问题。多簇头的自适应成簇算法（Self－Adaptive Algorithm Based on Multi－Cluster Head，SABMH）［6］，在数据的采集过程中选出的多个簇头节点轮流担当簇头，均衡簇头负载，但是簇头频繁更换，带来额外的控制开销。能量有效的多副簇头层次型路由协议（Energy Efficient Hierarchical Multiple Vice－cluster－head Algorithm，EHMVA）［7］，选举多副簇头分担主簇头能耗，均衡簇内能耗，降低簇头的负载，但是主副簇头功能交叠，造成能量浪费。

针对分簇路由算法一般存在的簇头负载过重的问题，本文拟提出一种基于LEACH协议的簇头辅助路由算法，通过控制信息与数据信息分离的办法来平衡网络的负载，延长网络的寿命，改进算法的性能将通过仿真进行验证。

1 问题描述和系统模型

无线传感器网络路由算法必须解决两个问题，其一是寻找去往目的节点的最佳路径，对于无线传感器网络，所有传感器节点的目的节点都是基站，其二是转发传感数据分组。无线传感器网络不同于传统无线网络，大量的传感器节点可以提供传感数据的冗余，传感器网络路由可以通过数据融合取得良好的性能［8］。根据无线传感器的特点，解决这两个问题，一般都要设定网络模型和能量模型。

1.1 网络模型

（1）在观测区域内，传感器节点和基站在部署后均不发生位置移动。

（3）为了节约能量，传感器节点可以根据接收者的距离远近调整其发射功率10］。

（4）考虑节点的连通度，至少有一个节点可以与基站通信，所有节点都可以收到基站的信息。为了保证无线传感器网络覆盖集是连通的，节点的无线通信半径大于等于其2倍感知半径。

1.2 能量模型

传感器节点的能耗分为：感知能耗、通信能耗、数据处理能耗。其中传感器在通信方面的能耗最大［1］。路由算法与通信能耗有着密切的关系，好的路由算法，可以选择最优的路径，降低通信能耗，从而延长网络的寿命。

采用与文献［4，11］相同的能耗模型，假设通信节点之间的距离为d，d0代表节点的覆盖半径。无线传感器节点发送l（bit）的数据需要消耗的能量

接收l（bit）的数据需要消耗的能量

传感器节点聚合能耗

其中Eelec代表无线收发电路处理单位数据所消耗能量，EDA代表单位数据融合能耗，εfs与εmp分别表示两种能耗模型的功率放大系数。

2 簇头辅助路由算法

2.1 算法基本思想

簇头辅助路由算法是一种分布式、自组织、自适应的分簇多跳路由协议。簇头辅助路由算法和LEACH算法类似，也是采用“轮”的方式运行。每轮分为簇建立阶段和数据稳定传输阶段。簇建立阶段分为簇头的选举、簇的形成，数据稳定传输阶段分为数据融合、数据发送。

不同的是在簇头辅助路由算法中簇头不再承担传感数据的融合以及转发功能。簇头节点（cluster head，CH）只实现对整个簇的控制以及簇间的协同，也就是只处理控制信息。簇头根据节点的剩余能量以及位置等信息从本簇中选择簇内聚合节点（Aggregation node，AN）、簇间转发节点（Transmission node，TN），簇内聚合节点负责传感数据的融合，簇间转发节点是下一跳节点的候选集，负责传感数据的转发。

这样簇头辅助路由算法中传感数据的传输路径有很大的不同。在LEACH协议中，普通节点（GN）把感知的数据发送给簇头，簇头经过数据融合后转发给基站（BS），而在簇头辅助路由算法中普通节点把感知的数据发送给簇内聚合节点，簇内聚合节点进行数据融合后，发送给下一跳节点（从簇间转发节点中选择），经过几次转发后，传感数据传送到了基站。

2.2 功能节点的选择

簇头辅助路由算法采用减少簇头功能的办法平衡网络的能耗，下面是不同功能节点的具体选择。

（1）簇头的选择

簇头辅助路由算法采用了控制信息与数据信息的传送分离的思想，LEACH算法中簇头在传感数据方面的能耗被簇内聚合节点、簇间转发节点分担。簇头的能量消耗大大减少，簇头的选择更加灵活，只要满足一定的剩余能量要求，就可以被选为簇头。为了满足大规模无线传感器网络的需求，簇头的选择不能由基站决定。也就是簇头的选择应该是分布式的。基于LEACH协议簇头的选择方面的改进很多，在此不做探讨，为了算法结果的比较，仍旧使用LEACH协议簇头的选择方法。

（2）簇内聚合节点

主要负责簇内节点数据的收集聚合。假设簇内聚合节点的坐标为（xi，yi），每一个簇内节点到簇内聚合节点的距离为dk，其小于无线传感器节点覆盖范围，最优的簇头聚合节点应该是簇内所有节点发送数据到簇内聚合节点的消耗的能量总和最小，即求

其中

也就是求

通过计算可得［12］

这说明在传感器节点均匀分布的情况下，一个簇内，最优的簇内聚合节点的位置为该簇的几何中心点，由于簇内聚合节点可以使用轮换的策略，簇头需要选择距离簇的几何中心最近的节点作为簇内聚合节点。

（3）簇间转发节点

簇间转发节点负责把收到的数据转发给本簇的下一跳节点或者是基站。假设簇间转发节点的坐标是（xTN，yTN），簇间转发节点与基站的距离dTN大于无线传感器节点覆盖范围，簇间转发节点可能需要把数据转发给基站，为了简单，最优的簇间转发节点是本簇内发送数据到基站能量消耗ETN最少的节点。由于

其中

可见在可以与基站直接通信的情况下，簇间转发节点为簇内离基站最近的节点，因此对于每个簇，簇头选择簇内给基站发送数据耗能最少的并且剩余能量较大的节点作为簇间转发节点。

（4）簇的下一跳节点

簇的下一跳节点从簇间转发节点中选出。簇头选择本簇的簇内聚合节点通过本簇周围（包含本簇）的簇间转发节点中到基站发送数据消耗能量最少的作为本簇的下一跳节点。如果是本簇的下一跳节点是本簇的簇间转发节点，那么本簇转发节点的下一跳就是基站。为了避免距离基站近的节点出现能量空洞问题，可以通过设置传感数据跳数的最大值，如果传感数据的跳数等于最大值，簇间转发节点应该将其直接发送到基站。

无线传感器节点部署在一些特殊环境下，节点可能失效。对于普通节点失效后，簇头应以最少的代价回收该节点所占用的时隙。对于簇内聚合节点和下一跳节点的失效，簇头重新选择合适的节点代替失效的节点。对于簇头节点的失效可以由簇内聚合节点代替或选择。

在一轮周期内，簇头可以根据簇的实际情况，簇内聚合节点以及簇间转发节点的能量如果低于阈值，簇头选择新的簇内聚合节点以及簇间转发节点，或者重新分簇。当簇头的能量小于某个阈值或者簇头在本轮的能量消耗大于设定阈值，以及簇内有大于设定阈值的节点死亡，应进行重新分簇。

2.3 算法能耗比较

LEACH算法每一簇的能耗Ecluster1等于簇头发送能耗ECH与所有非簇头节点发送能耗Enon－CH之和，即

簇头辅助路由算法的能耗Ecluster2等于簇间聚合节点的能耗EAN、通过所有下一跳的能耗Enext、所有普通节点的能耗EGN之和，即

根据簇间聚合节点和下一跳节点的选择原则有

其中ENext为在本簇的第一个下一跳耗费的能量，Enext为数据发送到基站经过的下一跳耗费的能量。可以得出

也就是簇头辅助路由算法的能耗低于LEACH算法的能耗。

3 仿真实验

由于分簇算法每一轮形成得到的簇各不相同，从理论上准确分析分簇的网络性能几乎是不可能的，通常的做法是用计算机模拟或仿真，获得分簇路由算法在不同的网络环境下的性能指标。在实际中又是很难测得大量的样本，因此采用有限次的仿真来研究算法的性能。

3.1 仿真场景

传感器节点随机均匀分布在200m×200m的检测区域内，基站的坐标为（100，100），传感器节点数量设为100、1 000。节点数100随机生成的拓扑图如图1所示。

图1 节点数100的拓扑图

3.2 仿真参数设置

［13］，对仿真过程中将要使用到的参数进行设置，如表1所示。

表1 仿真参数设置

3.3 仿真结果

（1）无线传感器网络的存活时间

定义为网络从开始运行到所有的传感器网络节点全部死亡的时间。其中比较重要的指标：第一个节点死亡的时间、10%的节点死亡的时间、最后一个节点死亡的时间。图2和图3分别为场景基站的坐标为（100，100），传感器节点数量设为100、1 000下死亡个数与时间的关系，表2和表3分别为两种场景下网络第一个节点死亡的时间、10%的节点死亡的时间、最后一个节点死亡的时间，从中可以看出簇头辅助路由算法在节点数1 000场景下，第一个死亡时间小于LEACH算法，这是由于簇头辅助路由算法是多跳的，靠近基站的节点承担了较多的数据传输，因为明显的延长了整体的寿命，少量节点死亡是可以接受的。上述结果验证簇头辅助路由算法比LEACH算法网络存活时间明显延长。

表2 节点数n＝100时网络存活指标对比

表3 节点数n＝1 000时网络存活指标对比

图2 节点数100场景下网络生命周期对比

图3 节点数1 000场景下网络生命周期对比

（2）数据接收总量

定义为基站接收到的簇间转发节点发送的经过簇内聚合节点进行数据聚合过的数据总量。数据接收总量越多，说明传感器网络对环境的检测越精确。图4和图5分别为场景基站的坐标为（100，100），传感器节点数量设为100、1 000下数据接收与时间的关系。可以看出簇头辅助路由算法与节点的数量有密切的关系，节点数量越大，簇头辅助路由算法相对于LEACH有比较明显的优势。这是由于簇头辅助路由算法比LEACH协议的生命周期长，簇头辅助路由算法在LEACH协议的网络已经死亡后，继续发送的数据超过了LEACH网络发送数据的总量。

图4 节点数100场景下网络数据接收对比

图5 节点数1000场景下网络数据接收对比

4 结语

针对LEACH算法的簇头负载过重的问题，提出了簇头辅助路由算法，让簇内聚合节点承担簇头的数据融合功能，让簇间转发节点承担簇头的数据发送功能，实现了簇的控制信息与数据发送分离，新算法以增加节点的计算量的代价换来整个网络灵活性的提高。仿真结果显示，网络的寿命有明显的提高。每一种路由算法各有特点，没有哪一种算法是绝对最优的，应根据具体情况选择合适的路由算法。簇头辅助路由算法适用于大规模的无线传感器网络。

参考文献

［1］陈林星.无线传感器网络技术与应用［M］.北京：电子工业出版社，2009：11－17.

［2］Naeimi S，Ghafghazi H，Chow C O，et al.A survey on the taxonomy of cluster－based routing protocols for homogeneous wireless sensor networks［J］.Sensors，2012，12（6）：7350－409.

［3］郑娟毅，石明卫.基于ZigBee技术的无线传感器网络树型路由的研究［J］.西安邮电学院学报，2010，15（1）：23－26.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless micro－sensor networks［C］／／Proceedings of 33rd Hawaii International Conference on System Sciences（HICSS）.Washington DC：IEEE computer Society，2000：3005－3014.

［5］Younis O，Fahmy S.HEED：a hybrid，energy－efficient，distributed clustering approach for ad hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366－79.

［6］杨坤.无线传感网络中多簇头算法研究与仿真［D］.成都：电子科技大学，2010：31－52.

［7］吕金鹏.无线传感器网络的路由协议研究［D］.杭州：杭州电子科技大学，2012：32－53.

［8］张德干，张晓丹，李光.无线传感与路由技术［M］.北京：科学出版社，2013：8－41.

［9］邬春学，肖丽.基于蚁群算法的低能耗LEACH协议分析［J］.上海理工大学学报，2010，32（1）：99－102.

［10］林力伟，许力，黄榕宁，等.能量均衡的无线传感器网络容错分簇优化策略［J］.福建师范大学学报：自然科学版，2009，25（5）：41－44.

［11］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［12］牛伟伟，高铁杠.LEACH－C协议中模拟退火算法的改进［J］.计算机工程与设计，2011，32（6）：1869－1872.

［13］邓亚平，唐骏.基于控制的低能耗多跳分簇路由协议［J］.计算机应用，2013，33（1）：108－111.