基于节点休眠机制的WSN路由优化

李英磊+吴韶波+黄茂源

摘 要：为了有效延长无线传感网的生存时间，科研人员提出将节点休眠机制应用于分簇路由的优化算法。文中根据传感器节点采集到信息所属范围的不同，将节点分入不同的组内，按照一定比例休眠组内节点，并根据组内节点的数量利用k均值算法将本组节点分入不同的簇中，节点采集到的信息通过簇头采用单跳与多跳相结合的方式向基站发送数据，在保证对区域可靠监控的基础上，可有效延长网络的生存周期。结果表明，在选择休眠节点时，根据节点在网络中所处地位选择休眠节点，具有使较大比例节点进入休眠状态保存能量的优点与不影响对监控区域高覆盖率的特点。

关键词：无线传感网；路由协议；分簇；能量有效

中图分类号：TP212 文献标识码：A 文章编号：2095-1302（2017）04-00-04

0 引 言

由能源受限的传感器节点组成的WSN是部署在监控范围内的用于感知和监测环境参数的新一代传感器网络，通过无线通信的方式将数据进行传递处理，从而监控某个区域内的情况[1]。

目前能最大程度降低能耗的有效方法之一是引入节点休眠机制[2]，本文提出将采集到的信息类别与节点休眠机制相结合的优化算法，在分簇组网阶段，不但考虑节点之间的距离，还根据传感器节点采集到的信息所属类别的不同将节点进行分组，之后再进行分簇算法（Information Type and K_means of WSN Routing Algorithm，IT_kmeans）。分簇算法采用经典的k均值算法。在众多路由协议设计理念中，分簇路由协议具有独特的优越性，它在高效便捷传送数据的基础上，能够对数据进行一定的数据融合处理，在很大程度上降低了网络的能量消耗。

将睡眠机制引入分簇路由算法是一种有效的节能方式，现阶段开展了大量的研究工作[3-6]。文献[3]提出了离簇头距离越远节点进入休眠状态概率越高的算法，并将其应用于分簇路由算法。文献[4]对基于距离的休眠算法进行了检验，指出由于节点间距离和能量消耗的差异，会导致这些节点过早死亡的不足。文献[5]提出了一种基于节点剩余能量的多少来调整节点是否进入休眠状态概率的算法。文献[6]针对节点随机休眠算法进行了研究。上述4种方法从不同的角度对休眠机制进行了对比和验证，其共同的不足在于無法保证网络的覆盖质量。

将路由协议与节点休眠机制相结合是无线传感网研究的重点之一，根据应用的不同，科研人员提出了多种有效的路由机制[7]。PEGSIS是将每个sensor node能耗最小化的基于链路的路由协议；APTEEN是将增强后的TDMA调用加入到处理调查阶段的路由协议[8]；除上述协议外，LEACH协议[9]针对如何解决数据融合的问题提出了不错的想法，将传感器节点分到不同的簇内，并指定一个簇首节点，此节点用于将本簇内其他节点采集到的信息进行汇总并传输到Sink节点，从而完成信息传递过程[10]。LEACH路由算法是比较经典的路由算法，针对LEACH算法的改进有很多不同的方法，如改进簇首的选择，使能量高的节点有更高的概率成为簇头[11]，或对分簇形式进行改进[12]。在文献[13]中作者在分簇、分层方面提出了新的改进，优化路由算法。文献[14]通过几何算法来优化路径，使得节点都达到最优路径。在此基础上也可结合簇首选择，分簇和传输三方面对算法进行优化[15]。

此外，研究者针对节点休眠机制和k均值算法应用于WSN进行了大量研究。针对异步睡眠机制导致通信延迟增大的问题，文献[16]提出了基于Dual- Radio动态调节节点占空比的算法，通过调节占空比预测链路通信过程中可能存在的冲突状况，有效减少了冲突对数据发送或接收的干扰。文献[17]提出了结合远程数据采集和移动端近距离数据采集两种模式，采用混合监听周期的低功耗休眠方法。文献[18]中将k_means聚类算法引入无线传感网的异常数据检测中，提高对异常数据的检测率。考虑到WSN的能量均衡问题，提出了动态轮换簇头算法[19]和网络动态k值簇头选择算法[20]，可在一定程度上改进通过簇头选择增加WSN生存时间的问题，优化了某些节点因为担任簇头而过早死亡的问题。在此基础上，又提出了网络分簇与节点休眠机制相结合的优化算法[21]，从而有效提升了网络的生存性，但对休眠节点的选择与不同节点之间交替休眠以保证能量均衡未提出较好的解决方案。

1 问题描述

现阶段针对节点休眠的算法主要有两类。一是根据节点所处位置的不同，随机选择一定比例的节点休眠；二是在节点分簇模型中，根据传感器节点距离簇头的远近选择不同比例的节点休眠。其他休眠算法大多以这两种思想为基础进行优化。此两种休眠算法在保证区域覆盖率的基础上使部分节点进行休眠。但在监控区域内，不同分区面积差别较大会导致某些有价值的信息区域内的节点进行较大比例休眠，甚至某些分区内全部节点进入休眠状态，从而使监控区域中有价值的部分信息丢失。针对这种问题，本文提出在节点分簇阶段，先将传感器节点根据信息类别进行分组，之后按照组内节点的数量划分不同的类型：

（1）当组内节点数目大于阈值L时，此组内节点按照比例N休眠，之后对活跃节点根据k均值算法进行分簇路由；

（2）若组内节点数目小于阈值L，则此组被当作一个簇处理，不再对本组内节点进行休眠，使得在区域分类的小分区内，保证节点数目足够多，使信息的采集更为全面准确。阈值L的选择根据实际情况可动态设定与修改。分组节点休眠模型示意图如图1所示。

考虑某矩形区域内随机分布着一定数目的传感器节点，故取节点休眠比例N=40%，阈值L=6。为进行对比说明，在分簇路由阶段首先将节点根据所属信息类别的不同划入不同组中（图中标出了所有分组中的区域1，2和3），在区域1和2中节点数目为10，大于阈值L，因此对这两个簇内的节点按比例M休眠；而在区域3内，由于节点数目为5，小于阈值L=6，因此该组内节点不休眠，全部处于活跃状态。根据算法的规定，区域1和2中节点数目较多，会在完成部分节点休眠操作后，按照k均值算法在组内进行分簇路由；而区域3内的节点不再进行分簇操作，全部节点即为一个簇。具体流程如下：

（1）首次分簇组网前，由Sink节点（汇聚节点）向所有传感器节点以广播形式发送消息，告知网络内的所有传感器节点下次重新分组的轮数rd，每个组激活的传感器节点占此簇所有节点的比例N，以及数据分类阈值L。

（2）传感器节点在首次分簇组网时，将自身采集到的信息类型以广播形式发送给周围的传感器节点，距离为投放的传感器节点间两个最近节点之间的理论最大距离。当其他传感器节点接收到此节点发送的信息后，将自己采集的信息与接收到的信息进行比较，若两者属于相同的数据范围，则两者建立连接，加入同一组。以此类推，所有传感器节点就和与自己周围环境相似的节点加入了同一个组。

（3）针对每个组，若节点数目大于阈值L，按照Sink节点之前发送的休眠比例N，随机选择本组内m个传感器节点进入休眠状态，其他节点保持活跃。其中：

m=W×L

式中，W为本组内的全部传感器节点的数目，L为由Sink节点指定的组内处于休眠状态的sensor节点比例。

（4）对所有处于活跃状态的传感器节点，根据预先约定好的组内节点数目与分簇数目的关系，利用k-means算法将本组内的节点分成k个簇。按多跳与单跳相结合的路由方式，将采集到的信息传送至Sink节点，Sink节点再将信息传送回数据处理中心，由数据处理中心对接收到的信息进行存储、分析。

（5）经过rd轮后，所有处于睡眠状态的传感器节点苏醒，再按照以上步骤重新组网分簇。

2 分簇模型

2.1 分簇策略

分簇分为两个时间段，即簇结构建立和采集数据的传输阶段。为了降低分簇阶段能源的消耗，数据传输阶段的保持时间应大于簇结构建立所消耗的时间。在首次组网之前，由Sink节点向所有传感器节点发出信息分类模型。比如要采集某区域内的雾霾浓度，将污染物浓度0～50定义为优，用数字1表示；将浓度50～100定义为良，用数字2表示；将浓度100以上定义为污染，以数字3表示。分组步骤完成后，节点数目大于阈值L的组，通过预先定义好的休眠比例使一部分传感器节点进入休眠状态，再根据k_means算法将本组内激活状态的节点进行分簇。如何选择k值是一个难点，本文通过综合考虑传感器性能与信息采集精确度，提出了一种通过规定簇内节点最少节点数目的方式来求出k值，进行簇结构的构建。其过程如下：

（1）选择一个组，将组中激活节点的个数N与预先定义的簇节点最小值C对比，如果N≤C，则本组所有激活节点即为一簇，不再进行分簇操作；如果N>C，求出N/C并向上取整，即为本组分簇数量k。

（2）k即为k_means算法中要分成的簇个数，通过k均值算法对本组内所有激活状态的节点进行分簇操作。

（3）重复以上步骤，每个组中所有活跃节点都成功分配进簇内，完成本次分簇过程，进入信息采集和传输阶段。

（4）进过rd轮后，所有睡眠状态的节点苏醒，整个网络按照（1）～（4）重新分簇组网，进入下一分组阶段。

以上过程中，节点通过采集到的信息类型的不同进行分组，如果某些节点由于信号干扰或通信错误等问题未能加入到任何组内，则此节点随机选择一个附近的組加入。在实际应用中还可以考虑加入针对每个簇最多和最少数目节点的动态调节，从而使簇规模在可控的范围内能耗更加均衡。完成分簇操作后，簇头为簇内传感器节点调配信息传输时间表，在信息传输时，簇内节点根据时间表向簇头发送信息，簇头将收到的信息进行整理后发送给Sink节点。运行rd轮次后，网络重新进入簇结构建设阶段，从而进入下一次组网的循环中。

2.2 簇内节点的能量均衡

为了分析节点采用多跳模式与簇头通信的能量消耗，首先将簇内节点单跳通信方式的能量消耗，然后推广到n跳。规定距离簇头小于R 区域内的传感器节点采用单跳方式，称该区域为单跳区域，此环内的节点为单跳节点，而单跳区域外的节点采用多跳方式传输信息。因传感器节点在监控区域内服从均匀分布，单跳区域中转发数据包的平均个数为：

在一个数据采集周期（轮）内，能得到临界节点多跳时的能量消耗为：

如果 R = a，则mπR2=A2，此时簇内节点与簇头直接通信，即为一个单跳簇，消除上式中的R，得到单跳通信的能量消耗为：

可见，单跳方式是多跳方式的一种简化。

现在分析簇区域中多跳时的能量消耗，采用多跳通信时，簇内n跳节点在一轮的采集周期内平均转发的数据包数为：

上式第 n 跳中临界节点在一轮的数据采集周期内的转发数据包的平均能量消耗为：

因此，多跳通信时簇中单个节点的平均能量消耗为：

由式（4）可知，当利用单跳方式进行通信时，节点的能耗随nR呈现出单调递增的趋势，而根据式（6）可知节点的能耗随nR的减小单调递减。

3 能量模型

假设数据采集阶段，传感器节点只将自己采集到的信息类型发送给所在簇的簇头节点，而不与其他簇中节点进行任何通信。簇头对本簇的传感器节点进行管理，将接收到的数据进行有效数据融合，融合后的信息由簇头节点以数据包的形式发送给Sink节点。为计算方便，作出能耗的假设模型： e1为节点接收或者发送一个数据包需要消耗的能量；udk为RF 功放及信息无线信道上传输所消耗的能量。u为传感器节点发送信息的功放系数，d为信息传输的距离，k为传输路径上的能量损失因子，为2～4。

在信息传输过程中，设簇头在独立的 MAC寻址和处理路由选择时，不考虑数据包之间的碰撞和时间上空闲监听时消耗的能量。传感器节点每发送一个数据包所消耗的能量为：

其他节点进行数据包转发所需的能量为：

其中：e1=100 mJ，u1=20 nJ/m2，。式（7）表明，当两节点之间的距离较远时，直接传输信息所消耗的能量比较大，而采用多跳通信的方式进行传输，则可在一定程度上节省能量。

4 仿真与性能分析

4.1 仿真结果

节点能源的高效使用是无线传感器网络能量有限特点的首要设计目标，因而，最大化网络生命周期是评价一个算法优劣的重要参数。仿真时用Matlab生成随机放在 100 m×100 m范围内的500个节点，所有节点的初始能量为0.5 J，每个数据包长2 000 bit，节点能量为零时死亡。

为验证本文所提IT_kmeans算法的性能，本节选择k_means算法进行性能对比。算法的性能通过两个指标来描述，一是网络剩余能量，一是剩余的存活节点数目。其中，IT_kmeans算法中，设置参数为重新分簇的轮次rd=50；每个簇激活的传感器节点占此簇所有节点的比例N=0.4；分簇类别假设有4个；数据包长度packet_length=4 000；控制包长度ctr_Packet_length=100；节点发送与接受一个字节的信息能耗为ETX=ERX=50×0.000 000 001 J。

发送放大器类型为Efs=10×0.000 000 000 001 J；Emp=0.001 3×0.000 000 000 001 J；

数据聚集能量为EDA=5×0.000 000 001 J。

图2展示了k_means算法的分簇结构和IT_kmeans某轮中所有激活节点的分簇结构，图2（a）所示为k_means算法，图2（b）所示为IT_kmeans算法。

图3展示了两种算法进行2 000轮信息采集的剩余能量曲线对比，图4展示了以两种算法进行2 000轮信息采集的剩余存活节点数目曲线对比。通过对比可以看出，网络剩余能量与存活节点数目均有较大优化。

4.2 性能分析

此次仿真以激活每个簇中40%的节点为条件，根据以上结果可知，由于休眠机制的加入，网络剩余能量与存活节点的数目都有较大程度的提升。原因是k_means算法中所有节点都一直处于激活状态，并且不计信息冗余的将自身采集到的信息通过簇头节点传送给Sink节点，而其中存在许多没有必要的信息冗余。通过IT_kmeans算法的改进，分簇阶段不再单纯以传感器节点位置来决定其属于哪个簇，而是加入了根据每个传感器节点采集到的信息进行分类，从而可以在休眠一部分节点的情况下保证对监控区域信息判断的准确性，不影响对监控区域的覆盖率，大大增加了系统的持久性。结果显示，当休眠节点比例较低时，网络剩余总能量与存活节点数目都有较大比例的提升。而随着休眠节点比例的变化，剩余能量曲线和存活节点数目曲线也会相应的进行调整。根据不同监控区域的要求，可以动态调整激活的节点比例，从而使系统更加持久与高效。

5 结 语

本文提出一种基于采集到的信息所属类别不同对传感器节点进行分簇路由的算法，在算法的实现过程中，考虑了实际应用中会出现的可能情况，从而以节点采集的信息作为主要分簇路由的依据。在此基础上，由于处于同一类别信息区域的传感器节点已经在同一个簇内，所以利用了传感器节点的休眠机制，在每一轮的信息传递过程中，使一部分节点处于休眠状态，从而在保证信息监控精确性的基础上达到了延长网络寿命的效果。

參考文献

[1] Akyildiz， W Su， Y Sankarasubramaniam， et al. Wireless sensor networks： a survey[J].Computer Networks， 2002， 38（4）：393-422.

[2] Dousse O， Mannersalo P， Thiran P. Latency of Wireless Sensor Networks with Uncoordinated Power Saving Mechanisms[C].Proc of the 5th ACM International Symposium on Mobile Ad Hoc Network and Compute. Tokyo， japan，2004：109-120.

[3] Deng J，Han Y S， Heinzelman W B，et al. Scheduling Sleeping Nodes in High Density Cluster-Based Sensor Networks[J]. Mobile Networks and Applications，2005， 10（6）：825-835.

[4] Duarte-Melo E J， Liu M Y. Analysis of Energy Consumption and Lifetime of Heterogeneous Wireless Sensor Network [C].Proc of the IEEE Global Tele- communication Conference. Taipei ， China， 2002：21-25.

[5] Pearlman M R， Deng J， Liang B， et al.Elective Participation in Ad Hoc Networks Based on Energy Consumption [C].Proc of the IEEE Global Tele- communications Conference. Taipei， China， 2002：26-31.

[6] Shi Gaotao， Liao Minghong. Stochastic Sleeping for Energy-Conserving in Large Wireless Sensor Networks[J].Journal of Computer Research and Development， 2006，43（4）：579-585.

[7] 王达山，黄刘生，徐宏力，等.基于矢量的无线传感网络能量有效配置算法[J].计算机研究与发展，2008，45（4）：626-635.

[8] Shaobo Mao，Man Hon Cheung，Wong V.W.S. An optimal energy allocation algorithm for energy harvesting wireless sensor networks[J]. IEEE International Conference on Communications，2012，11（8）：265-270.

[9] W. Heinzelman， A. Chandrakasan， H. Balakrishnan. Energy efficient Communication Protocols for Wireless Sensor Networks[C]. in IEEE Proceedings of the Hawaii International Conference System Sciences， Hawaii， USA，2000： 3005-3014.

[10] 陳楠.无线传感器网络LEACH算法的研究与改进[D].北京：北京邮电大学，2008.

[11] 余静涛，胡同森，钟明霞.无线传感器网络路由协议LEACH的研究与改进[J].计算机系统应用，2009，18（2）：30-34.

[12] 房晓菲，沈永增，姚俊杰.一种基于LEACH的新型WSN路由算法[J].机电工程，2008，25（5）：100-103.

[13] 吕涛，朱清新，张路桥.一种基于LEACH协议的改进算法[J].电子学报，2011，39（6）：1405-1409.

[14] Ningbo Wang， Hao Zhu.An Energy Efficient Algrithm Based on LEACH Protocol[C].in International Conference on Computer Science and Electronics Engineeing（ICCSEE）， Hangzhou， China，2012： 339-342.

[15] Jia Xu， Ning Jin， Xi zhong Lou.Improvement of LEACH protocol for WSN[C].in International Conference on Fuzzy Systems and Knowledge Discovery（FSKD）， Sichuan， China，2012：2174-2177.

[16] 杨健，李金宝，郭龙江，等.Dual-Radio 无线传感器网络睡眠调度机制[J].软件学报，2011， 22 （S1）： 62-72.

[17] 张昱，曹伟，邵世祥.低功耗无线传感网节点的混合监听休眠方法[J].计算机技术与发展，2016，26（10）：196-199.

[18] 费欢，李光辉.基于K-means聚类的WSN异常数据检测算法[J].计算机工程，2015，41（7）：124-128.

[19] 张亚楠，马世欢.基于能量均衡的无线传感器网络分簇路由协议[J].计算机与现代化，2015（7）：90-93.

[20] 吴黎兵，杜锦，聂雷，等.无线传感器网络动态k值簇头选择方法[J].华中科技大学学报（自然科学版），2015，43（10）：37-41.

[21] 陈龙，刘莉平，赵明，等.无线传感器网络分簇和节点休眠综合性策略研究[J].计算机与现代化，2015（4）：1-5.