基于最优化的能耗均衡分簇路由协议
2020-06-22赵东方施伟斌
赵东方 施伟斌
摘 要：为了均衡传统分簇路由算法中的簇间传输能耗，减少簇首更换开销，提出基于最优化模型的能耗均衡分簇路由协议opt_leach。将区域节点划分成大小相同的簇，均衡不同簇的簇内通信开销;簇间通信采用多种路由组合的方式通信，均衡簇间通信开销;簇内节点可以连续充当簇首，减少簇首更换开销。实验结果表明，与传统分簇路由算法相比，该算法可更好地实现能耗均衡，延长网络生存时间。
关键词：无线传感器网络;分簇路由协议;能耗均衡;最优化;线性规划
DOI：10. 11907/rjdk. 191936 开放科学（资源服务）标识码（OSID）：
中图分类号：TP393文献标识码：A 文章编号：1672-7800（2020）005-0204-05
0 引言
无线传感器网络（WSN）广泛应用于医疗保健、污染监测和目标跟踪系统等领域[1]。WSN由大量节点组成，其计算、传感和无线通信能力有限，能效是一个重要问题，直接影响到WSN的网络寿命[2]。与非聚类协议相比，聚类通常可以减少冲突和空闲侦听造成的能量耗散。因为在每个集群中，簇首都会为每个节点分配一个独占的时间槽，从而避免冲突。此外，节点不需要在每个时分多址（TDMA）帧中保持清醒，只需要在其特定的时隙中保持清醒[3]。因此，集群是延长WSN网络生存期的常用策略。
为解决WSN中能量均衡高效问题，Heinzelman等[4]提出了最早的分簇路由协议。该协议充分利用数据融合技术，是分簇路由协议的代表;HEED[5]协议采用迭代的方式选取簇首，并考虑了节点的剩余能量、通信代价和网络中簇首的分布，避免能量少的节点过早死亡，延长了网络生存时间;李成法等[6]提出EEUC协议，将网络组织成大小非均匀的簇，以解决多跳路由传感器网络中常见的“热区”问题，但未说明多跳路由路径的建立过程;黄利晓等[7]提出通过加入间距因子、剩余能量因子和节点密度因子改进簇首选择概率函数的阈值计算式，综合考虑节点剩余能量和地理位置选择簇首，取得了一些改进效果;胡源等[8]通过对监测区域的等间距环形划分和等夹角扇形划分，选择同一扇形区域内的下一跳节点以保证源节点与基站的通信距离最短;UCF[9]协议提出一种基于模糊逻辑的不等聚类方法，改进了非均匀成簇的半径确定，进一步均衡了簇间通信;Peyman Neamatollahi等[10]提出了一种基于动态超循环策略（DHRP）的能量感知集群算法SEDC，通过减少频繁重新聚类的开销延长集群WSN中的网络生存期，但是没有对簇首持续轮数进行理论推导。
传统的分簇方法采用概率竞争的方式选择簇首，每一轮簇首分布情况未知，因此难以对簇间通信建立能耗均衡路由规划，导致不同区域的簇首传输能耗不均衡;同时，每个节点当选簇首的持续时间较短，增加了更换簇首的开销。为此，本文提出一种基于最优化模型的能耗均衡分簇路由协议opt_leach。首先将区域节点均匀划分成大小相同的簇，保证网络各个簇的簇内通信消耗均衡;其次簇间通信采用多种路由组合方式，使用线性规划求解每种路由方式的最优比例。在每一个簇内，使用线性规划求解每个节点充当簇首的最优轮数，使得节点可以连续充当簇首，从而减少了重新聚类的频率和开销。仿真实验表明，与传统分簇路由算法相比，本文提出的opt_leach算法可以更好地实现能耗均衡并延长网络生存时间。
1 分簇路由模型介绍
为便于比较，本文采用分簇路由协议研究中的典型分析模型[4，7，10-12]，对网络模型和硬件能耗模型作出假设与约束。
1.1 传感器节点模型
（1）传感器节点随机、相对均匀分布在规则图形的监测区域中。
（2）所有的传感器节点具有相同的数据处理能力和通信能力，初始能量相同。
（3）传感器节点被随机分散后位置固定，网络部署后不再进行人为干涉。
（4）传感器节点可以知悉自身剩余能量，位置可被知悉。
（5）节点部署具有冗余度，一定区域范围内节点间的数据可以进行数据融合。
（6）节点可以根据数据需要发送的距离调整发射功率。
1.2 硬件能耗模型
（1）发送l bit数据能耗。当l bit的数据需要传输时，节点所消耗的能量主要由两部分组成：发送l bit数据的基本能量耗损以及功率放大电路的能量耗损;同时，针对不同的发射距离d选择不同的发送功率。
当传输距离为d时，功率放大器所消耗的能量需要依据发送器与接收器的距离d与阈值d0进行比较。其中，[d0=εfsεamp]是区分两种消耗的阈值。当传输间距d
（2）接收l bit数据能耗：Erv（l，d）=l×Eelec。
（3）数据融合l bit数据能耗：Eag（l，d）=l×Eelec。
2 协议及算法介绍
Opt_leach协议是一种集中式和分布式相结合的并行成簇算法。
初始阶段：sink收集节点的位置信息和能量信息：①将节点均匀分簇，每个节点分配一个固定的簇编号，此后节点所属的簇编号不再改变;②计算不同编号的簇间通信路由组合最佳比例，写入路由表;③计算每个簇内节点充当簇首的顺序和最优持续轮数，写入簇首顺序表;④sink节点将以上结果分发至每个节点。初始阶段只执行一次。
分布式階段：①每个初始簇首为簇首顺序表的第一个节点，相同簇编号的节点加入同一个簇，簇首为每个成员分配TDMA时隙;②簇首更换：簇首轮数若达到最优轮数，则指定簇首顺序表的下一个节点在下一轮成为簇首，并使用该节点的TDMA时隙，簇内其它节点TDMA时隙不变;③簇间通信：簇首节点按照事先分配的路由表中的路由路径传输数据至sink节点。
2.1 均匀分簇
因为节点位置固定，所以可对节点进行区域划分[6，9，13-16]。本文对节点区域均匀划分，首先将节点按照相对于汇聚节点在垂直方向上划分成Y个区域，再将水平方向划分成X个区域，这样一共得到X×Y个区域。每个区域的节点获得相同的簇编号，即每个区域的节点将始终在同一个簇内。图1展示了100m×100m区域内在随机均匀分布100节点情况下，节点被均匀分成4个簇的情形。
2.2 簇间通信方式确定
在LEACH协议中，每个簇首采用单跳直接与汇聚节点通信。当节点分布区域逐渐增大时，靠近汇聚节点的簇和远离汇聚节点的簇能耗差异明显，距sink节点较远的簇节点能量会先耗尽。若簇首采用多跳方式往往会导致靠近sink节点的簇节点能量先耗尽[17-18]。因此，本文簇首间通信采用多种路由组合的方式传输数据，并计算最优比例。
假设一共有n个簇首节点，每个节点用于簇首传输的能量为Ei，则簇首节点共有m（m=2n（n-1）/2）种可能路径。图2为当n=3时的路由情况，c节点有4种路径选择（c→b→a→sink，c→b→sink，c→a→sink，c→sink），b节点有两种路径选择（b→a→sink，b→sink），a节点有一种路径选择（a→sink），则根据乘法规则，n=3时一共有4*2*1=8种路由方式。
在每一轮中，簇首会从所有路由路径中选择一种作为簇首通信方式。若第i（1≤i≤n）个簇首在第k（1≤k≤m）种路由方式中传输一轮数据的能耗为CHcostik，则第k种路由方式的使用次数为lk轮。在每个簇首i用于传输数据的能量不超过Ei前提下，通过确定不同路由最优比例获得簇首可传输数据的最大轮数lmax，可使用最优化模型中的线性规划求解。
当n逐渐增大时，求解出的路由组合可能有很多种。实际应用中可以忽略占比低于阈值Routeth的路由路径，保留占比较大且切换较容易的几种路由，再作一次线性规划得到最优比例，具体阈值和路由数量可根据实际情况作相应调整。
2.3 簇内节点成为簇首的轮数和顺序
在均衡每个簇的簇首能耗后，区域中每个簇可以看成近似等价。在每个固定的簇中，不同位置节点当选簇首时节点能耗分布不同。为了均衡簇内每个节点的消耗，分析每个节点当选簇首的最优轮数。
2.3.1 节点成为簇首的轮数确定
假设某个簇内一共有n个节点，每个节点的初始能量为E。由于单个簇内同时只有一个簇首，所以一共有n种成簇情况，即每个节点轮流当一次簇首。第j个节点在第i个节点当选簇首时的能耗 costij可由式（4）计算，其中i=j时，为节点当选簇首时使用多种路由组合的加权平均消耗。
2.3.2 簇首顺序确定
当簇内节点i成为簇首的最优轮数已知后，节点i在第k种路由方式下充当簇首的次数在没有达到Rik之前的任何一轮都可以成为簇首。当节点i在第k种路由方式下成为簇首的次数达到Rik时，在第k种路由方式下不再成为簇首，所以簇首的顺序确定可依据实际应用灵活变化。
本文将簇内节点i到sink的距离di作为簇首节点的顺序指标。在第k种路由方式下，di小的节点先成为簇首，并且连续充当簇首Rik轮，即节点连续充当簇首的轮数为当前路由方式的最优轮数。这样做的好处是簇首不必频繁切换，有利于路由的稳定并降低控制信息的能耗。当整个簇内节点执行完当前路由方式的轮数后，整体切换成路由表中的下一种路由方式。
3 仿真分析
本文在Matlab平台上对LEACH、HEED、SEDC和本文的opt_leach协议分别进行仿真。假设100个节点随机均匀分布在从（0，0）到（100m，100m）的网络区域内[4，7，11-12]，汇聚节点部署在网络区域之外的坐标（50m，175m）。为了保证区域的连通性[5]，本文假设每间隔10m×10m方形区域内至少有一个节点，因为连通性是保障节点可以通过多跳的方式传输数据的重要条件，在实际应用中这个假设也是合理且易于实现的。表1列出了实验参数。
3.1 opt_leach参数计算
区域划分的参数为x=2，y=2，即簇首的最大跳数为2，节点共有两种路由选择。通过计算得到两种路由方式的最佳比例为单跳Route1=0.401 9，多跳Route2=0.598 1。4个簇计算出的多跳轮数分别为577、580、580、576，单跳轮数分别为385、387、385、386。将不同区域的轮数统一为计算出的最小值，得到最终每个区域的节点将以576轮簇首多跳路由和385轮簇首單跳通信，共持续961轮。单个簇内每个节点的轮数如图3所示。
在到达最大可持续轮数后，节点会相继死亡，opt_leach协议着重于节点全部存活时传输数据的能耗均衡最优化，所以未对节点相继失效时的分簇进行讨论。为了便于与其它协议进行对比，在节点到达最大可持续轮数后，采用SEDC[10]协议对剩余节点进行分簇。
3.2 协议对比与分析
通过比较执行完opt_leach的最大轮数后，将每个协议的节点存活数量和每一轮能耗速率作为评估opt_leach协议性能指标，并对opt_leach协议的能耗均衡性和可预测性展开分析。
3.2.1 节能性对比
由图4可知，当轮数达到961时，opt_leach协议的节点全部存活，符合最大可持续轮数的计算结果。opt_leach的第一个节点死亡（FND）出现在第962轮，而SEDC、HEED和LEACH的FND分别出现在915、709和624轮;SEDC、HEED和LEACH的最后一个节点死亡（LND）分别在1016、935、941和1126轮。从图5可知，opt_leach协议能量衰减曲线一直保持较小的斜率，这是因为在opt_leach协议算法中，节点在选择簇间路由方式比例和簇内节点充当簇首的轮数都是线性规划的最优解，且固定簇首可以减少因为频繁更换簇首而带来的控制消息能耗。
3.2.2 opt_leach协议能耗均衡性分析
图6是961轮之后每个节点的剩余能量，100个节点中大部分节点的剩余能量在0.02J左右，具有高度的能量均衡性。只有2个节点剩余能量较高，其中最高的约为0.06J。这是因为即使将区域节点均匀分成4个固定簇，每个簇的内部节点位置也不可能完全相同，最终每个簇计算出的最大可持续轮数会有微小差异。最终统一将轮数设置为不同区域中计算出的最小值，此时个别节点依然可以充当几轮簇首，最终这些节点能量会略高于其它节点。
4 结语
本文针对分簇路由协议提出一种改进算法——opt_leach协议，其思想是使用最优化模型中的线性规划计算簇间不同路由组合的最优比例，以及簇内节点充当簇首的最优轮数。实验结果表明，使用最优化方法确定分簇路由协议中的簇间传输路径和选择簇首，可以降低网络总能耗，延长网络整体寿命。
参考文献：
[1] LIU X X. Atypical hierarchical routing protocols for wireless sensor networks： a review[J]. IEEE Sensors Journal， 2015， 15（10）： 5372-5383.
[2] KHAN I， BELQASMI F，GLITHO R， et al. Wireless sensor network virtualization： a survey[J]. IEEE Communications Surveys and Tutorials， 2016， 18（1）： 553-576.
[3] FADEL， ETIMAD， GUNGOR V C， et al. A survey on wireless sensor networks for smart grid[J]. Computer Communications， 2015， 71（1）： 22-33.
[4] 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.
[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-379.
[6] 李成法，陈贵海，叶懋，等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报，2007，30（1）：27-36.
[7] 黄利晓，王晖，袁利永，等. 基于能量均衡高效WSN的LEACH协议改进算法[J]. 通信学报，2017，38（Z2）：164-169.
[8] 胡源，牛玉刚，邹媛媛. 基于区域划分的WSN非均匀多跳分簇路由算法[J]. 控制与决策，2017，32（9）：1695-1700.
[9] NEAMATOLLAHI P，NAGHIBZADEH M. Distributed unequal clustering algorithm in large-scale wireless sensor networks using fuzzy logic[J]. Journal of Supercomputing， 2018， 74（6）： 2329-2352.
[10] NEAMATOLLAHI， PEYMAN， NAGHIBZADEH， et al. Distributed clustering-task scheduling for wireless sensor networks using dynamic hyper round policy[J]. IEEE Transactions on Mobile Computing， 2018， 17（2）： 334-347.
[11] WANG A M，YANG D L，SUN D Y. A clustering algorithm based on energy information and cluster heads expectation for wireless sensor networks[J]. Computers & Electrical Engineering， 2012， 38（3）： 662-671.
[12] ZHU X R，SHEN L F，YUM TAK-SHING PETER. Hausdorff clustering and minimum energy routing for wireless sensor networks[J]. IEEE Transactions on Vehicular Technology，2009，58（2）： 990-997.
[13] GOU H S，YOO Y W. An energy balancing leach algorithm for wireless sensor networks[C]. Information Technology： New Generations （ITNG），2010 Seventh International Conference on，2010：822-827.
[14] 孫彦清，彭舰，刘唐，等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报，2014，35（1）：198-206.
[15] 余秀雅，刘东平，杨军. 基于K-means++的无线传感网分簇算法研究[J]. 计算机应用研究，2017，34（1）：181-185.
[16] 张雅琼. 基于K-Means的无线传感网均匀分簇路由算法研究[J]. 控制工程，2015，22（6）：1181-1185.
[17] 刘述钢，刘宏立，詹杰，等. 无线传感网络中能耗均衡的混合通信算法研究[J]. 通信学报，2009，30（1）：12-17.
[18] 孙勇，景博，张宗麟，等. 分簇路由的无线传感器网络通信模式与能量有效性研究[J]. 电子与信息学报，2007，29（9）：2262-2264.
（责任编辑：杜能钢）
