基于优化簇头选举的WSN分簇路由协议研究

梁 壮，李 刚,2,3，雷丽婷

(1.兰州交通大学机电技术研究所，甘肃兰州 730070；2.甘肃省物流及运输装备信息化工程技术研究中心，甘肃兰州 730070；3.甘肃省物流与运输装备行业技术中心，甘肃兰州 730070)

随着电子学、无线通讯以及传感器等相关技术的快速进步，传感器网络也在朝着大规模、自组织、高可靠性的方向发展[1].传感器从早期只具有点到点的传输功能，逐步发展到当代的智能无线传感器网络.无线传感器网络应用极为广泛，其技术也是物联网工程的核心要素，已经被公认为是仅次于互联网的又一重要网络[2].无线传感器网络（Wireless Sensor Network, WSN）运行方式是由各个传感器的相互协调完成对监测区域相关信息的采集和融合，最后将整合后的数据发送给管理人[3].关于无线传感器网络研究的内容也很丰富，但是由于节点具有能源、存储容量和功率制约的明显缺点，因而耗能依然是WSN研究的重要部分.

无线传感器网络路由协议根据网络结构可以分为平面路由协议和层次路由协议，后者也称为分簇路由协议.分簇路由协议相比于平面路由协议的不同之处在于整个网络包含几种不同类型的传感器，分别来完成各自的功能，网络性能优良[4].LEACH[5]（Low Energy Adaptive Clustering Hierarch）协议是Heinzelman等人提出最早的分簇路由协议，首次引入“轮”的概念，并赋予其含义.在网络运行的每一轮都选举新的簇头，规避某些节点能量持续消耗情况的出现，实现网络能耗尽可能均衡的目标.其在网络寿命方面的突出表现，使得层次路由协议逐步成为学者们研究的热点.

LEACH类协议簇头选举的过程中，由于推选簇头的随机性相对较大，忽视了各个节点的特异性，就会导致每一轮选举出的簇头数相差甚远，即不能产生稳定的最佳簇头数量.甚至在WSN运行的最后阶段，将不会产生一个簇头.按照网络性能的优良可将整个无线传感器网络周期划分为三个时期 ：稳定周期[6]（Stable Period, SP）、半数死亡节点期[7]（Half Surviving nodes, HSN）和弱感知周期①Liu J J, Hu Y J. A balanced andenergy-efficient clustering algorithm for heterogeneous wireless sensornetworks [C] //Proceedings of the 6th International Conference on Wireless Communications and Signal Processing. Hefei, China: IEEE,2014: 1-6.（Weak Perception Cycle, WPC）.在无线传感器网络运行的早期，没有节点的死亡，所有节点都稳定运行，这段时间网络具有很强的感知能力，称之为稳定期.从网络运行开始直到有一半节点死亡或者存活时，此阶段为半数死亡节点期，该阶段网络的感知能力逐步降低但仍能维持网络的正常运行.从死亡半数节点开始到无线传感器网络运行结束，称为弱感知周期，整个网络的感知能力逐渐下降到一个很低的水平，尤其在弱感知后期，大多数的节点处于死亡状态，网络的感知能力极差，网络基本处于瘫痪状态以致无法正常工作.因此，保持网络运行的前两个时期（SP和HSN）越长，网络性能越好.

在许多WSN分层路由协议研究中，众多学者[8-10]将网络寿命作为首要目标，而忽略了WSN性能的其它重要指标，比如稳定期、有效轮数等.对此，本文在WSN簇头选举阶段进行了改进，提出一种基于优化簇头选举的分层路由协议（Cluster Routing Protocol Based on Optimized Cluster Head Election, CBOCHE）.目的是为了提高簇头选举的的稳定性，并在更大程度延长无线传感器网络的稳定期和半数死亡节点周期，并不仅仅是一味追求网络的绝对寿命.

1 网络模型

1.1 无线传感器结构

假设WSN的监测区域为正方形，边长为M，传感器的总个数为N，随机部署在监测范围内，网络的成簇数量与簇头数目相对应.组成网络的节点类型分为三种，按照数据传输的路径依次分别是普通传感器节点、簇头节点、汇聚节点.汇聚节点的下一级传输到达的是管理节点，管理节点是用户和网络的交互平台.图1为典型的WSN结构（不包括管理节点）示意图.

1.2 异构网络模型

选用多级异构传感器中的两级异构传感器，按照原有能量的多少分成普通传感器节点和高级传感器节点.假设高级节点在传感器总数中占比为m，普通节点的初始能量较低，为Es，高级节点的初始能量为Es(1 + a)，a表示高级节点超过普通节点能量的倍数.

图1 WSN结构示意图

1.3 能量消耗模型

传感器操作和存储器访问所消耗的能量相对于无线电传输而言非常小并且可以被忽略.因此，分层无线传感器网络的能量消耗主要来自于数据传输和簇头节点对数据的分析融合两大部分.本文采用文献[11]能量消耗模型，公式如（1）式.

其中，ETx(k,d)和ERx(k)分别表示传感器节点发送接收k-bit数据包的能耗；ECH和EDA分别表示簇头节点发送和融合数据的能耗；Eelec表示发射电路或接收电路每bit数据的消耗能量，Efs为自由空间模型的传输系数，Eamp为多径衰落模型传输系数；d 表示传输距离，d＜d0是自由空间能耗模型，d ≥ d0是多径衰落能耗模型.

2 基于优化簇头选举的分簇路由协议（CBOCHE）

2.1 簇头选举算法流程

在分层路由算法中，Gnode来标识节点是否属于候选簇头集G.若一个节点在最近1/Popt（Popt为簇头比例）轮内做过簇头，令Gnode=0，此节点不能用作簇头的候选节点；若一个节点在1/Popt内没有做过簇头，令Gnode=1，此节点就可以作为簇头的候选节点.在每1/Popt轮后，重置1/Popt前当选簇头节点的值Gnode值为1.

这种更新规则在网络运行前期，由于没有死亡节点的出现，簇头的候选节点数目大于最佳簇头数目，可以选举出最佳簇头数.随着网络的运行，节点数目将会不断减少，就会出现候选簇头数目等于甚至小于最优簇头数目的情况.当二者相等时，所有的候选簇头数都会被选举为簇头，当候选簇头的数量小于最佳簇头数目时，不能选出合理数量的簇头，导致簇头选举数目不稳定问题的出现.

为改善簇头数目选举不稳定的缺陷，本文提出的CBOCHE协议在簇头选举流程中Gnode的跟新策略进行优化.G值含义仍然为是否属于候选簇头集，当出现候选簇头数等于最佳簇头数时，直接跳过阈值比较的过程，将所有的候选簇头全部当选为簇头节点.当候选簇头数小于最佳簇头数时，即将所有的候选节点全部成为簇头时，仍不能选举出足够的簇头数，本文采取的方法是立即更新节点Gnode的值，通过提前值更新Gnode时间来补充足够的候选节点数目，直到候选簇头数目等于或者大于最佳簇头数.这样就可以保证每一轮选举出合理稳定的簇首数目，改进后的流程图如2所示.

图2 CBOCHE协议簇头选举流程

2.2 节点阈值修正

经典的LEACH协议中，簇头的选举是通过产生的随机数与设定的阈值比较来确定节点是否担任簇头，随机数的取值范围为0 - 1，当随机数小于阈值时，节点被选为簇头，反之为普通节点.阈值的公式如下[12]：

其中，p=k/n；n和k表示网络中的节点和簇首数，p和r分别是节点中簇头所占比例和网络正在运作的轮数，G是近来1/p轮内未担任过簇首的一个集合.LEACH协议由于运行过程产生随机数带来的随机性，会使整个网络的负载不均匀.

DEEC（Distribute Energy-Efficient Clustering）是在LEACH协议基础上进一步修改后的又一种分簇路由协议[13]，其阈值公式与LEACH协议的阈值公式基本相同，但原式子中的簇头占比P改变为节点当选为簇头的几率Pi，Pi的计算公式为：

其中，Popt为簇头占比，Er(i)为节点i运行到r轮时的剩余能量，整个网络的平均剩余能量.

与LEACH协议相比，DEEC路由协议引入了两个因子，即节点的剩余能量和网络的平均剩余能量，相对增加了WSN的网络寿命.但在每一轮的簇头选举中仍然会出现选举出的簇头数不稳定的情况，簇头数目过多或者过少都会造成节点能耗增加.同时，DEEC协议也忽略了节点间相互距离这一重要因子，因为传输距离也是影响能耗的一个关键因素.

TSEP①Kashaf A, Javaid N, Khan Z A, et al. TSEP: Thresh-old-Sensitive Stable Election Protocol for WSNs [C] //International Conference on Frontiers of Information Technology. IEEE, 2012: 164-168.（Threshold-sensitive Stable Election Protocol）协议是LEACH基础上改进的一种协议，但它的着重点不同于LEACH和DEEC两种协议，它更加关注数据的传输而非簇的形成.TSEP中阈值包括硬门限和软门限俩个参数，当感测值达到硬阈值时，发射机被打开，数据传输到簇头，该感测值被储存在节点的变量中，这是第一次满足条件.之后，当且仅当感测值大于硬阈值或者当前感测值与储存的感测值之间的差等于或大于软阈值时，节点将发送数据.通过考虑这两个阈值来调节数据传输的时机，可以有效减少数据传输的次数，某些方面网络性能得到显著提升.因此，本文将TSEP也作为结果对比分析的一种协议，其阈值具体计算见本页脚注①.

在簇头选举中，本文既将节点的初始能量和剩余能量纳入考量，也兼顾到节点到基站的距离,来避免因二者距离较大而造成负载增加的情况.修正后的阈值公式如式（4）.

式中：r是网络正在运行的轮次，G是近来1/pi轮没有担任簇头的节点集，α和β为调节参数，α、β具有相同的取值范围[0,1]，且满足α + β = 1，Eres和Eini分别是节点的剩余能量和节点的初始能别是全网的剩余能量和全网的初始能量，Si表示节点i，davg和di分别表示全部节点到基站的平均距离和节点i与基站的距离，pi是节点i成为簇头的概率.

由于网络包含不同能量类型的节点，故不同类型节点成为簇头的机率并不相同，具体计算公式如下：

其中Popt是簇头比例，m表示高级节点在全部节点中的占比.

3 实验仿真及分析

本文选用 MATLAB2016a软件为仿真实验平台，在两级异构网络环境下验证算法的网络性能.在边长为100的方形平坦区域中随机布置100个节点，网络的范围为（0,0）～（100,100），基站的位置为（50, 50），详细的实验参数如表1所示.与TSEP、LEACH、DEEC协议作对比，分析改进协议CBOCHE的性能，图3为CBOCHE协议运行示意图.

表1 实验参数

3.1 簇头的选举稳定性分析

本文研究和分析了LEACH类协议中簇头选举的不稳定性，并改进和优化了其缺陷，以确保在WSN运行早期阶段产生更稳定的簇头数.本文实验总节点数是100，最优簇头数目是5，故在不受任何干扰因素条件下每轮产生的簇头数都应该为5.表2为几种协议在网络运行不同时期簇头数目的均值和方差.图4为簇头稳定性柱状对比图.

由表2和图4可知，CBOCHE协议在稳定期选举出的簇头数目均值为5，方差为0，表明协议在WSN运行前期簇头数目非常稳定.同时，在相同时期，新算法在半数死亡点和网络寿命期间簇头数的均值相比于其它协议更高，并且方差较低.表明在网络运行的整个生命周期内，产生稳定簇头数的性能均得到全面显著改善.

图3 CBOCHE运行示意图

表2 各协议产生簇头数分析

3.2 网络有效生命周期对比分析

本协议在调整Gnode值的更新规则来优化簇头选举数目的同时，也对阈值进行了修订.考虑了节点的初始能量和剩余能量、全网的初始能量和剩余能量、节点到基站的距离等因素，延长了WSN网络有效生命周期.利用MATLAB对协议进行仿真实验，统计不同协议的各个运行时期的运行情况，结果如表3所示.

图4 簇头稳定性对比图

表3 各协议在不同阶段的运行轮数

通过对表3数据分析可得，改进后的CBOCHE协议在稳定期以及半数存活节点期的运行轮数和有效轮数明显优于其它几种协议.在稳定期的有效运作轮数相对于LEACH、DEEC和TSEP分别增加了36.35%、28.77%、23.25%，在半数存活点也分别增加了 41.72%、29.63%、15.16%.改进后的协议在簇头稳定性方面有较大提高，几乎避免了零簇头情况的出现，故网络的整体寿命下降较大，但生命周期的有效轮数仍然明显提高，相对于 LEACH、DEEC和 TSEP分别提升了75.54%、71.05%、53.19%.

图5 不同时期网络生命周期对比图

图5 为表3部分数据绘制的柱状图，更加直观地显示了改进算法延长了网络的稳定期和半数存活点期，同时网络生命周期有效轮数的提高使得其在整个网络寿命的占比几乎达到100%.

4 结 论

本文针对无线传感器网络簇头数目选举不稳定以及稳定期、半数节点存活期不够长的缺点进行研究，提出了一种新的基于簇头选举阶段路由算法.仿真验证表明，新协议CBOCHE相关性能明显改善.

1）通过修改簇头选举流程中的Gnode值与新策略来保证网络运行的每一轮都可以产生合理的簇头数，尽量规避出现没有簇头的状况，并且显著增加了网络运行有效轮数.

2）阈值修正过程中，兼顾节点的初始能量和剩余能量、全网的初始能量和剩余能量、节点到基站的距离等与能耗相关的因素，扩展的WSN性能表现出更佳的稳定期和半数存活节点期.