一种能量有效的无线传感器网络分簇及簇间路由算法

李灯熬 郝海龙 郭锦龙 赵菊敏

(太原理工大学信息工程学院1，山西 太原 030024;国网山西省电力公司电力科学研究院2，山西 太原 030001)

0 引言

无线传感器网络是由大量传感器节点通过无线通信方式组成的多跳自组织网络。在网络中，传感器节点感知并收集监视区域的监测数据。无线传感器网络具有广泛的应用领域，如地震监测、环境检测、战场监视等。

传感器节点只能携带有限的能量，且一般情况下难以补充，因此如何有效利用有限能源是现在无线传感器网络研究的重点之一［1］。网络的能量消耗主要和通信距离有关，因此为了减少能量消耗，应该尽可能地减小通信距离。解决这些问题比较有效的方法是层次型路由算法，这种算法有利于网络的扩展和简化，也不需要建立和维护路由信息，而且将进一步减少长距离通信的能量消耗［2］。簇大小和传输范围分配(arranging cluster sizes and transmission range，ACT)协议分簇复杂，而且没有优化簇间路由［3］。分布式能量均衡非均匀分簇(distributed energy-balanced unequal clustering，DEBUC)协议在簇头竞争阶段采用计时广播机制，但没有优化簇间路由引入代价函数来降低控制消息开销，节约单个节点的能量［4］。LEACH 算法周期性、等概率地选择簇头，簇头收集邻居节点的数据来分簇，对簇首的选择具有很大的随机性，且没有考虑簇间路由，与基站单跳通信［5-6］。在LEACH 改进算法中，LEACH-C 基站计算出一个能量阈值，将高于能量阈值的节点设为候选簇头，选择簇头也具有随机性，与基站单跳通信［7］。在节能非均匀分簇(energy-efficient uneven clustering，EEUC)协议中，设定门限值来设定候选簇头，然后根据簇头与基站的信号强度计算来选择簇头，但在簇间路由中没有考虑与基站距离，达不到全局优化的目的［8］。

为了改善传感器节点分簇时的不均匀，均衡能耗现象，本文基于节点能量剩余和簇头间的距离等因素来选择簇头;分簇后，综合考虑簇头与基站的距离、簇头能量以及簇内成员节点数量三种因素，计算代价值，选择下一跳簇头节点。这样通过簇间距离可均匀分簇，簇间路由通过选择最小代价值来减少并均衡能耗。

1 网络与能耗模型

1.1 网络模型

假设在无线传感器网络中，N 个传感器节点随机部署到M×M 的矩形区域中。无线传感器网络具有如下性质:①所有节点能量有限，基站位置固定，能量不受限;②节点具有唯一ID，均匀分布在监测区域;③所有节点具有相同能力(计算、储存、通信)，且地位同等;④节点通信功率可调;⑤节点具有位置感知能力;⑥每个节点可进行数据融合。

1.2 无线传输能量模型

本文采用文献［9］中的能耗模型来构建簇内通信能耗和簇间通信能耗。簇内能耗Ein包括节点数据传递和簇头节点接收数据的能耗。

式中:m 为簇的成员节点数;di为第i 个成员节点和簇头的距离;Eelec为发送或接收每bit 数据消耗的能量;εamp为多径衰减信道的功率放大器能耗。

簇间能耗Einter是簇头节点发送数据的能耗和以跳级模式将数据信息传递到汇聚节点的能耗。

式中:k 为跳数;q 为第i 个簇头的邻居簇头数;di为第i个簇头距下一级跳簇头的距离。

2 网络分簇

分簇算法在基站中进行，在分簇过程中综合考虑节点剩余能量和节点距离等因素来进行簇头选择以及分簇。

2.1 簇头距离限值

如图1 所示的无线传感器网络，簇区域为等边六角形，簇头源节点和基站之间最优的通信路径为直线多跳路由，通信距离最短。在簇头多跳路由中，簇的半径是影响能耗的关键因素，由于dlimit的值和簇头数目以及簇区域面积有关，因此通过取合适的dlimit，可减小较小区域内簇头太多或较大区域内没有簇头的概率，从而均匀部署簇头。如果dlimit太小，可能会在较小区域内出现多个簇头，形成多个簇，簇头收集到簇内成员节点的数据后，传输给基站时可能导致碰撞或者数据传输冗余等情况。如果dlimit太大，那么在较大区域内簇头会减少，簇区域面积会增大，簇内成员节点和簇头的通信能耗更多。在无线传感器网络中，取定合适的dlimit可均衡网络能耗。文献［10］基于六角簇区域，求得最优的簇半径r 如式(3)所示，距离限值如式(4)所示。

图1 基于簇间多跳的网络分簇结构Fig.1 The clustering structure of network based on multiple hops between the clusters

式中:ee为信号发射机发射每比特数据的能量消耗;λ为载波波长;dR为节点数据传输率;β 为损耗因子;pthr为能耗阈值。

2.2 分簇流程

在每轮分簇过程中，首先计算所有节点Ni(i =n)的剩余平均能量，设定能量阈值，设剩余能量高于能量阈值的节点为候选簇头Mi(i=1，2，…，m)。依次为节点M1～Mm分配簇内成员节点，每次为一个Mi分配簇内成员节点，若Mi与M1，M2，…，Mi-1中至少一个的距离小于距离限值dlimit，则不为Mi分配簇内成员节点并将Mi作为成员节点分配给M1，M2，…，Mi-1中距离最近的簇头。设最终的簇头集合为CHi(i =1，2，…，c)。由于成员节点数与簇头的能耗有关，为了均衡能耗，将当前簇头的成员节点数和与簇头的距离作为参数定义一个代价函数(5)，网络中其余节点Nj选择代价值S(CHi，Nj)值最小的簇头CHi作为成员节点加入。这样成员节点不仅可以选择相对较小距离的簇头加入，而且使得簇内的成员节点数更加均衡。直到遍历完所有候选簇头Mi(i=1，2，…，m)，分簇完成后，基站向全网络广播簇头节点ID 和各簇内成员节点的ID。

式中:dCHi，Ni为簇头CHi和节点Nj的距离;dmax为网络中两个节点之间的最大距离;mh为簇头CHi的当前成员节点数;N 为网络中所有传感器节点的总数;α 和β 为权重因子，且α+β=1;f 为路径损耗指数。

3 簇间路由

当与基站距离较远的簇头将数据传输到基站时，如果簇头单跳将数据传输到基站，簇头容易耗完能量成为死亡节点。若簇头与基站通信采用多跳路由可均衡能耗，并减少由于长距离通信的路径损耗而浪费的能量。在分簇阶段，基站根据收集到的网络内节点的位置信息，计算簇头与基站的距离，然后反馈给每个节点。当簇头与基站通信时，若簇头与基站的距离小于或等于dlimit，簇头与基站直接单跳通信。若簇头与基站的距离大于dlimit，则建立簇间多跳路由与基站进行通信。多跳路由建立流程如下。

(1)与基站进行通信的簇头源节点向邻居簇头节点发送询问数据包，询问信息包括簇头ID、簇头与基站的距离以及簇头的剩余能量。邻居簇头节点收到询问数据包后，向簇头源节点发送应答数据包。

(2)簇头源节点根据应答数据包中的信息，基于式(6)计算所有邻居簇头节点的簇间权重值WCHi，j，选择权重值WCHi，j最小的邻居簇头节点作为下一跳簇头节点，簇间权重值包括簇头与基站距离、簇头剩余能量和簇内成员节点数这三个因素。

式中:i≠j，dCHi，j为簇头i 与簇头j 的距离;dm为网络中簇头与基站的最远距离;f 为路劲损耗因子;Ej为簇头j的剩余能量;Emaxj 为节点初始化的最大能量;mj为簇头所属簇内成员节点个数;α、β 和γ 为权重因子，且α +β+γ=1。

(3)基于步骤(2)，选择下一跳簇头，直到出现一个簇头与基站的距离比其他所有邻居簇头与基站的距离小时，这个簇头直接与基站进行通信，簇头与基站的多跳通信完成。

4 仿真与结论

本文采用Matlab 进行仿真实验。为了证明该算法的有效性，将本文算法与LEACH-C 和EEUC 算法进行仿真实验对比。模拟实验场景为1 000 m×1 000 m，随机部署节点总数为1 000，基站的坐标为(1 100，500)，其他仿真参数如表1 所示。

表1 仿真参数表Tab.1 The simulation parameters

通过仿真比较网络的生命周期、接收数据包和能量消耗来观察本文算法性能。图2 为本文算法与LEACH-C 以及EEUC 算法的生命周期对比图。

图2 网络生命周期对比图Fig.2 Comparison of network life cycle

从图2 可以看出，本文算法与LEACH-C 以及EEUC 分别在900 轮、750 轮以及600 轮节点全部死亡，与其他两种算法相比生命周期延长了91%以及20%。LEACH-C 选择簇头具有随机性，导致分簇不均匀，而且簇头与基站间单跳通信;而EEUC 中临时簇头未考虑能量，并且所有节点都要做竞争半径等更多计算，簇头较容易死亡，且分簇更加频繁;本文算法根据簇头间的合理距离限值均匀分簇，并且簇头间根据路径权值选择最佳路径，减小了能耗。

基站接收数据量对比如图3 所示。

由图3 所示，本文算法的基站接收数据量均高于LEACH-C 以及EEUC 算法。本文算法不仅根据最优距离限值均匀分簇，而且簇头间的路径权值可减少能耗;而LEACH-C 未考虑簇头间路由，EEUC 未考虑临时簇头的能量以及节点计算耗能。因此本文算法在节点全部死亡前可进行更长时间的运行，即消耗相同的能量传送更多的数据到基站。

图4 为三种算法的网络剩余能量仿真图。

图4 剩余能量对比图Fig.4 Comparison of the remaining energy

图4 显示，随着仿真时间的推移，本文算法的剩余能量均高于其他两种算法。本文算法的分簇是基于最优距离限值，并且选择了最优的簇头间路由，而LEACH-C 随机选择簇头，且单跳与基站进行通信;EEUC 算法忽略了临时簇头的能量，且节点的计算能耗也更大。因此，和其他两种算法相比，本文算法更加节省能耗。

5 结束语

通过对无线传感器网络节点路由能量优化模型、分簇模型以及簇间路由的研究，提出了基于簇头距离限值的分簇算法以及基于路径权值的簇间路由算法。通过合理配置簇头距离限值，能够均匀分簇，使得在一定区域内有数量合理的簇头。在簇间路由选择中，综合考虑簇头与基站距离、簇头能量以及簇内节点数量计算路径权值，在保证节点数据传递的同时，均衡能耗，提高能量利用率，最终延长网络的生存周期。

［1］ 孙利民.无线传感器网络［M］. 北京:清华大学出版社有限公司，2005.

［2］ Latif K，Jaffar M，Javaid N，et al.Performance analysis of hierarchical routing protocols in wireless sensor networks［J］. International Conference on Broadband，Wireless Computing，Communication Applications，2012，49(1):620-625.

［3］ Lai W K，Fan C S，Lin L Y.Arranging cluster sizes and transmission ranges for wireless sensor networks［J］.Information Sciences，2012，183(1):117 -131.

［4］ Wan M，Zhu Y. An energy efficient routing protocol for wireless sensor networks［C］//International Conference on Computational Intelligence and Communication Networks，2012:95 -97.

［5］ 沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588 -1600.

［6］ Chen X，Wang Z，Wu J.The improved wireless sensor network routing algorithm based on LEACH［J］. Chinese Journal of Sensors and Actuators，2013(1):025.

［7］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An applicationspecific protocol architecture for wireless microsensor networks［J］.Wireless Communications，IEEE Transactions on，2002，1(4):660-670.

［8］ Kim D H. Tuning of a PID controller using an artificial immune network model and local fuzzy set［C］//IFSA World Congress and 20th NAFIPS International Conference，2001. Joint 9th. IEEE，2001:2698 -2703.

［9］ Ibrahim R，Ho Q D，Le-Ngoc T. An energy-efficient and loadbalancing cluster-based routing algorithm for CSMA-based wireless sensor networks［C］//Vehicular Technology Conference (VTC Spring)，2013 IEEE 77th，2013:1 -5.