提出了一种基于死亡节点与半径调度的低功耗自适应集簇分层型（LEACH）覆盖保持协议，对簇头的随机选择机制进行了阈值的联合优化，采用泰森多边形对簇头节点进行Voronoi图划分，并根据簇头节点和簇内节点覆盖半径的不同进行分簇.在增大簇头节点通信半径及减小簇内节点的通信半径时，同时考虑网络中死亡节点数目，修正簇头节点的阈值选择公式，根据该阈值对网络的簇数重新选择和分簇.仿真结果表明，该算法对网络的覆盖度可保持在1 700轮左右，提高了网络的数据传输能力，延长了生命周期.
A low energy adaptive clustering hierarchy (LEACH) coverage preserving protocol based on dead nodes and radius scheduling (LEACH_DNA) was proposed. The selection of the cluster head adopts the optimized random selection mechanism in the algorithm. The cluster head nodes are divided by Voronoi diagram. And there are several clusters divided by the coverage radiuses of the cluster head nodes and the coverage radiuses of the clusters inter nodes. When the radiuses of cluster nodes increases, the radiuses of cluster nodes and considered the number of dead nodes in the network reduces. The function of the executive thereafter chooses a certain number of clusters nodes and renews the LEACH clustering. Simulation shows that the LEACH_DNA algorithm for network coverage has maintained at 1 700 round, the function of the network data transmission capacity is improved, and the network life time is extended.
无线传感网在军事监控、环境监测、医疗卫生、建筑物监测、智能城市交通等领域有着广泛的应用前景，是由大量能量有限的移动或固定传感器节点组成，节点可能由于能量的无法补充而失去其覆盖监测功能.因此，无线传感网覆盖保持协议设计的主要目标是既能保持网络的覆盖率又能尽量节约节点的能耗，以延长网络的生存时间[1].笔者提出了一种基于死亡节点数与节点半径调度的覆盖保持协议(LEACH_DNA，low energy adaptive clustering hierarchy coverage preserving protocol based on dead nodes and radius scheduling)，既有效延长了网络高覆盖率的保持时间，又提高了数据传输能力和网络生存时间.
1 WSN的覆盖保持协议近年来，随着无线传感网的发展，覆盖保持协议的研究及其改进也越来越多[2-8].对于随机抛散节点的无线传感网，由于节点并不知道自身的位置信息，其覆盖问题可以归结为随机覆盖问题.Tsai[2]提出一种随机分布的覆盖保持路由协议，根据节点的标准化有效覆盖率选举簇头，总能耗与低功耗自适应集簇分层型协议(LEACH，low energy adaptive clustering hierarchy) 协议基本相同，但簇头选举具有一定的随机性，因此网络覆盖率受到影响.Khedikar等[3]提出了一种能量有效的目标算法，虽然提高了网络的连通度，但是网络的整体覆盖率受到很大限制.为提高网络的整体覆盖率，Sharawi等[4]提出了一种基于多目标优化的无线传感器能量感知与覆盖保持体系的分簇路由模型MOB，但由于未考虑网络的运行导致死亡节点数目增加对覆盖性能的影响，因此其保持性能并不好.Deepak等[5]提出了一种随机拓扑框架，未考虑节点因能量消耗而对通信半径的影响，因此覆盖率受到很大影响.Nie等[6]提出了一种全定位区域划分机制RDM以避免网络因节点失效产生的覆盖空洞问题.Shunnan等[7]提出了一种能量有效覆盖感知的分簇机制，通过根据节点的剩余能量来选取簇头的方法来优化网络的生存时间，保证网络的最大覆盖.由以上分析可见，无线传感网的随机覆盖问题既要考虑节点由于角色不同具有不同的通信半径对网络覆盖率的影响，又要尽可能延长网络高覆盖率的保持时间和网络的整体生存时间.
研究创新点如下：
1) 簇头节点的选择，对簇头节点采用优化的随机选择机制，并利用Voronoi多边形进行分簇；
2) 根据节点类型选择不同的覆盖半径，即簇内节点选择较小的覆盖半径，簇头节点选择较大的覆盖半径；
3) 对承担簇头任务的节点采用轮换机制，当簇头节点能量即将耗尽时，即向所在Voronoi多边形中距离其最近且未担任过簇头的邻居节点发送消息，令其接替成为簇头节点，并重新分簇以完成数据搜集任务.
最后通过仿真证明该算法可保证网络在较高覆盖率下长时间的保持工作状态，且网络的数据传输能力和网络的健全性等也较好.
2 信道模型 2.1 路径损耗模型无线电能量的消耗很大程度与路径的传播模型相关，笔者选用一种常用的传播路径损耗模型[8]为
| $ L\left(d \right)=L({{d}_{0}})+10\text{lg}~(d/{{d}_{0}}) $ | (1) |
其中：d为发射机和接收机之间的距离，L(d) 为在距离为d时的传播损耗，单位为dB，L(d0) 为在距离为d0时的传播损耗，单位为dB.
2.2 通信能耗模型笔者采用简单且通用的一阶无线电通信能耗模型计算网络总能量损耗E.该模型包括发射能耗和接收能耗，表示为
| $ E={{E}_{\text{Rx}}}\left(k \right)+{{E}_{\text{Tx}}}\left(k, d \right)=k{{E}_{\text{elec}}}+{{E}_{\text{Tx}}}\left(k, d \right) $ | (2) |
发送k bit数据到距离为d的接收机时，发射机的能量损耗可表示为
| $ \begin{array}{l} {E_{{\rm{Tx}}}}\left( {k,d} \right) = {E_{{\rm{Tx - elec}}}} + {E_{{\rm{Tx - amp}}}} = \\ \;\;\;\;\left\{ \begin{array}{l} k({E_{{\rm{elec}}}} + {\varepsilon _{{\rm{fs}}}}{d^2}),{\rm{ }}\;\;\;d \le {d_0}\\ k({E_{{\rm{elec}}}} + {\varepsilon _{{\rm{amp}}}}{d^4}),{\rm{ }}\;\;\;\;d > {d_0} \end{array} \right. \end{array} $ | (3) |
| $ {{d}_{0}}=\frac{4\text{ }\!\!\pi\!\!\text{ }{{H}_{\text{R}}}{{H}_{\text{T}}}\sqrt{L}}{\text{ }\!\!\lambda\!\!\text{ }} $ | (4) |
其中：ERx(k) 为接收机接收k bit数据消耗的能量；ETx(k, d) 为发射机发射k bit数据所消耗的能量；k为传输k bit数据；Eelec为发射机或接收机每处理1 bit数据所需要消耗的能量；d为发射机到接收机的距离；ETx-elec为发射机的发射电路在发射数据时所消耗的能量；ETx-amp为发射机的发射放大器在放大数据时所消耗的能量；εfs为自由空间信道模型下发送功率放大器向单位面积发射1 bit数据消耗的能量；εamp为多径衰落信道模型下发送功率放大器向单位面积发射1 bit数据消耗的能量；d0为自由空间信道模型和多径衰落信道模型的临界值，其计算方法如式(4) 所示；HR为接收天线高度；HT为发送天线高度；L为路径传播损耗；λ为波长.
3 LEACH_DNA覆盖保持协议 3.1 网络模型网络内随机布置N个初始能量相同的传感器节点，节点间相互独立且可自动调节其覆盖半径.每个节点都采用圆盘模型覆盖，如果某节点的覆盖半径为R，则其覆盖区域的面积就为πR2.图 1所示为建立的无线传感网模型，应满足以下条件：
|
图 1 无线传感网体系结构 |
1) 网络中每个簇头节点和簇内节点都可进行通信，且节点并不具有移动性，即位置固定.
2) 所有节点具有有限的、相等的初始能量，节点可以感知周围节点的死亡与生存状况.
3) 节点间的通信信道相同，节点间相互通信发射端和接收端的选取不影响能量消耗.
4) 每个节点的覆盖半径可在一定范围内变化.任一节点无论是被选为簇头节点还是只充当簇内节点，他们都具有在相同变化范围内的通信半径.
3.2 LEACH算法当无线传感网中节点较多时，分簇路由协议在节省能耗方面的优势非常明显.对于典型的分簇路由协议LEACH，所有节点自组织分簇且每个节点可随机当选为簇头节点.簇内节点首先传输数据给所在簇的簇头节点，当所有由簇内节点发送的信息都被簇头节点接收后，簇头节点对信息进行融合并传输到汇聚节点，汇聚节点再将数据传输到基站.簇头节点由于承担的工作量较大而能耗也相对较大.
簇头节点的选择方法是在每一轮由节点m产生一个0~1之间的随机数，并与其所对应的阈值T(m)(由式(5) 得出) 进行比较.如果这个随机数小于T(m)，则在当前轮该节点就被选为簇头节点；否则，就充当簇内节点.该阈值在每一轮都将更新.
| $ T\left(m \right)=\left\{ \begin{align} &\frac{p}{1-p[r~\text{mod}~\left(1/p \right)]}, \text{ }m\in G \\ &0, 其他\\ \end{align} \right. $ | (5) |
其中：p为簇头的百分比；r为当前的轮数，且0≤r≤∞；G为当前轮没有被选为簇头节点的节点集合.
3.3 簇头选择的优化LEACH_DNA协议联合考虑死亡节点数与节点的覆盖半径对簇头节点选择的影响，使用Voronoi多边形分簇以保证网络的覆盖率.由于Voronoi多边形表示空间中点集合之间具有位置的邻近关系，即在每个Voronoi多边形内形成一个簇，簇内节点间可相互通信，并把消息传递给簇头节点.根据Voronoi多边形的性质，簇内一定且只存在一个样点，该样点到簇内其他节点的距离最短，即选择该节点为簇头节点.此时，簇头节点与簇内节点间通信的距离相对较短，能量消耗也相对较少.为提高网络的覆盖率，该模型根据节点在网络中承担的作用不同选择不同的通信覆盖半径.网络中的簇头节点和簇内节点分别选取不同的覆盖半径Ra和Rb，且Ra>Rb，并对节点m的簇头选择阈值T(m) 修正，可得
| $ T\left(m \right)=\left\{ \begin{align} &\frac{p\left(i \right)}{1-p\left(i \right)[r~\text{mod}~\left(1/p\left(i \right)\right)]}, \text{ }m\in G \\ &0, 其他\\ \end{align} \right. $ | (6) |
| $ p\left(i \right)=\frac{(n-M-{{n}_{1}}){{R}_{b}}+{{n}_{1}}{{R}_{a}}}{\left(n-M \right)R}p\frac{n-M}{n} $ | (7) |
其中：p(i) 为该模型的簇头百分比；r为轮数，且0≤r≤∞；n为节点总数；M为当前轮死亡节点数；n1为簇头节点数；Ra为簇头节点覆盖半径；Rb为簇内节点覆盖半径；p为起始簇头百分比；R为LEACH协议节点覆盖半径.
由式(6) 和式(7) 可以看出，在网络运行的初始状态，由于没有死亡节点，采用Voronoi多边形进行簇划分并按当前T(m) 值选择簇头节点.由于簇头节点的通信能耗相对较大，当簇头节点的能量消耗至初始能量的5%时，定义其为濒临死亡状态.此时，该簇头节点即从簇内其他未做过簇头的节点中挑选出最邻近的节点，并向其发送信息，告知该簇头节点濒临死亡并选择该节点为临时簇头节点，等待下一次簇头的选择，从而实现了簇头节点的轮换.该濒临死亡节点已经由簇头节点变为簇内节点，因此下一次簇头选择时它的覆盖半径将发生变化，即由Ra变为Rb.
随着网络的运行必然会出现死亡节点，M的值开始非0，为保证网络的覆盖率，需要更多的节点充当簇头节点.由式(7) 可见，随着M值的变大，簇头节点半径集合占的比重逐渐增加，簇内半径集合占的比重逐渐减少，p(i) 值也就逐渐变大，阈值T(m) 也随之增大，当前节点担任簇头节点的概率随之增大，网络中的节点开始轮流当选簇头节点，网络的覆盖率得到保障.当网络继续运行，死亡的节点越来越多时，节点更多的充当簇头节点，其覆盖半径Ra>Rb，网络的覆盖率实现了长时间的保持.
3.4 簇内节点工作机制采用Voronoi多边形对网络进行分簇划分，在每个Voronoi多边形内形成一个簇，根据每个簇内节点角色的不同选择不同的覆盖半径.在该Voronoi多边形内取其样点，将距离该样点最近的点设为簇头节点.由于簇内节点到簇头节点的距离是最近的，通信传输所消耗的能量也相对较小.簇内节点发送收集的数据给簇头节点，簇头节点融合处理并转发到汇聚节点，最后由汇聚节点转发到基站，从而发送给用户完成数据的通信任务.
随着网络的不断运行，簇头节点由于承担较多的通信任务而能耗较大，会比其他节点更早死亡，导致网络的覆盖率迅速下降.该协议对簇头节点和簇内节点选取不同的覆盖半径以节省簇内节点的能耗；且在簇内对簇头节点采取轮换机制，以均衡节点的能耗，达到延长网络生命周期的目的.
图 2为Voronoi起始分簇图形，图 2中黑色节点为簇内节点，黑色圆圈节点为簇头节点，总共计200个节点，其中20个簇头节点，180个簇内节点.从图 2中可以看出，由于节点的随机分布导致网络内节点分布不均，一般每个簇内约有5~15个节点.但也存在个别较小的簇，簇内只有簇头节点而没有簇内节点，此时簇头节点单独完成其覆盖和通信任务.
|
图 2 Voronoi分簇圆盘覆盖图 |
采用Matlab软件系统进行仿真，具体参数的设置如表 1所示.
|
表 1 仿真参数设置 |
初始网络总节点数设为200个；网络区域为100 m×100 m的范围；LEACH协议设每个节点的初始探测半径为6 m；汇聚节点位于网络所覆盖区域的中心位置，即(50, 50)；每个节点的起始能量为0.6 J；设每节点对发送数据进行处理(包括数据的融合和压缩等) 时所消耗的能量是50 nJ/bit；发射电路在自由空间放大处理数据时的能耗为9 pJ/bit/m2；发送电路在多径衰落下对数据进行放大处理时所消耗的能量为0.001 2 pJ/bit/m4；调整后簇头节点探测半径Ra为7 m和8 m，簇内节点探测半径Rb为5 m和4 m.为简化仿真，设系统中每个节点每次所发送的数据均为4 000 bit；设系统运行轮数为4 000轮.
4.2 实验结果分析图 2为未填充颜色Voronoi分簇圆盘覆盖图，簇头节点的覆盖半径为7 m，簇内节点的覆盖半径为5 m，从图 2中能明显观察到网络的覆盖性能.为评价该算法的性能，对LEACH_DNA和LEACH算法进行了仿真比较，并对网络的生存时间、数据传输能力和网络的覆盖率等评价指标进行了分析.
4.2.1 网络生存时间图 3描述的是网络生存时间指标.
|
图 3 LEACH_DNA协议的网络生存时间 |
从图 3中可以看出，LEACH协议在1 200轮左右时出现第1个死亡节点，大约90%的节点在1 700轮之内死亡，2 100轮左右节点全部死亡.而LEACH_DNA协议在Ra=7 m，Rb=5 m第1个死亡节点出现在1 200轮左右，大约90%的节点在2 000轮左右死亡，2 600轮左右全部节点死亡；当Ra=8 m和Rb=4 m时，第1个死亡节点出现在1 700轮左右，90%左右的节点在2 700轮左右死亡，2 800轮左右全部节点死亡.当以全部节点的死亡作为网络的生存时间指标时，可知与LEACH协议相比，LEACH_DNA协议在Ra=7 m，Rb=5 m时网络生存时间延长了约500轮，大约为23.8%；当Ra=8 m，Rb=4 m时，网络生存时间延长了约700轮，大约为33.3%.
4.2.2 数据传输能力图 4描述的是改进协议的数据传输能力.
|
图 4 LEACH_DNA协议的数据传输能力 |
从图 4中可见，随着时间的增加，汇聚节点接收到的数据包的总量在逐渐增加，在运行相同轮数的情况下LEACH_DNA协议的数据传输能力要远远好于LEACH协议.LEACH协议在1 900轮左右数据接收能力达到饱和，大约为0.5×105.而LEACH_DNA协议在Ra=7 m，Rb=5 m时约2 200轮左右数据传输达到饱和，接收数据为1.7×105，与LEACH协议相比数据传输能力提高了约2.4倍；在Ra=8 m，Rb=4 m时约2 700轮数据传输达到饱和，接收数据为3.5×105，其传输能力与LEACH协议相比提高了约6倍.由此可见，LEACH_DNA网络的数据传输能力提高很大.
4.2.3 网络覆盖率图 5为LEACH_DNA协议随着运行轮数的增加网整体覆盖率的变化比较图.
|
图 5 LEACH_DNA协议的覆盖率 |
从图 5中可以看出，在开始的前1 500轮左右LEACH协议的网络覆盖率达到近0.9，明显好于LEACH_DNA协议，这是因为LEACH_DNA协议在第1轮之后即调整了网络中簇头和簇间节点覆盖半径的大小，增大簇头节点的覆盖半径，减小簇内节点的覆盖半径，这样网络的实际覆盖率一定是下降的.但是，随着网络的持续运行，1 500轮以后LEACH协议的覆盖率急剧下降，到2 000轮时已经近似于0覆盖了.
结合图 3的仿真结果可以看出，LEACH协议在1 200轮左右出现第1个死亡节点，在1 200轮至1 500轮之间，网络的覆盖率缓慢下降，而当运行至1 500轮之后，网络的覆盖率随着死亡节点的增多而迅速下降，至2 100轮时网络中全部节点死亡，这说明1 500轮之后网络的功能已经受到很大影响.而LEACH_DNA协议在Ra=7 m和Rb=5 m时，当网络运行稳定之后，其平均覆盖率大约为0.82，低于LEACH协议的覆盖率.但是，当网络持续运行1 500轮之后其覆盖率已经超过了LEACH协议的网络覆盖率，而在2 600轮时节点才全部死亡.结合图 4的仿真结果可以看出，网络第1个死亡节点出现在1 200轮左右，2 600轮左右全部节点死亡，网络覆盖率下降得明显比较缓慢，要远低于LEACH协议网络覆盖率的下降速度，这说明网络的均衡性较好.LEACH_DNA协议在Ra=8 m和Rb=4 m时，经过一段时间的运行，网络覆盖率稳定在0.72左右.结合图 4的仿真结果，网络第1个节点的死亡出现在1 700轮左右，当网络运行到2 000轮时网络的覆盖率才开始出现下降的趋势，且下降的速度更为缓慢，最后在网络运行至2 800轮时达到0覆盖.由此可以看出，LEACH_DNA协议相比较LEACH协议而言具有更好的均衡性，同时也可更好地保持网络的覆盖率.在实际应用中，可通过增加一定量的冗余节点来增大LEACH_DNA协议的网络起始覆盖率，从而达到均衡网络的目的.
5 结束语提出了一种基于死亡节点与半径调度的LEACH覆盖保持协议.通过对簇头节点选择机制进行阈值的优化，节点根据角色的不同(簇内节点或簇头节点) 采取不同的通信覆盖半径，并对无线传感网进行Voronoi分簇划分.在簇头节点的轮换机制中考虑网络的死亡节点数目和半径调度的变化，对簇头节点增大覆盖半径，簇内节点缩小覆盖半径，调整节点当选为簇头节点的概率.该改进协议与原有的LEACH协议相比较，在网络生存时间、数据传输能力和网络覆盖率的保持时间等性能指标上均有很大的提高.
| [1] | Fortino G, Giannantonio R, Gravina R, et al. Enabling effective programming and flexible management of efficient body sensor network applications[J]. IEEE Transactions on Human-Machine Systems, 2013, 43(1): 115–133. doi: 10.1109/TSMCC.2012.2215852 |
| [2] | Tsai Y R. Coverage-preserving routing protocols for randomly distributed wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(4): 1240–1245. doi: 10.1109/TWC.2007.348320 |
| [3] | Khedikar R, Kapur A. Energy effective target coverage WSNs[C]//2014 International Conference on Issues and Challenges in Intelligent Computing Techniques. Ghaziabad:ICIC, 2014:388-392. |
| [4] | Sharawi M, Emary E, Saroit I A, et al. WSN's energy-aware coverage preserving optimization model based on multi-objective bat algorithm[C]//IEEE Congress on Evolutionary Computation. Sendai:IEEE, 2015:472-479. |
| [5] | Deepak S S, Basavaraju T G. GCCT:a graph-based coverage and connectivity technique for enhanced quality of service in WSN[J]. Wireless Personal Communication, 2015, 85(3): 1295–1315. doi: 10.1007/s11277-015-2841-0 |
| [6] | Nie Chunkai, Chen Xi. Robust percentage coverage mechanisms in wireless sensor networks[C]//2012 International Symposium on Communications and Information Technologies. Hammamet:ICCIT, 2012:348-353. |
| [7] | Shunnan M M, Ai-Mistarihi M F, Harb S. An energy-efficient coverage aware clustering mechanism for wireless sensor network[C]//The 5th International Conference on Communications, Computers and Applications. Istanbul:MIC-CCA, 2012:154-158. |
| [8] | 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. doi: 10.1109/TWC.2002.804190 |