论文部分内容阅读
摘 要： 根据经典的低功耗自适应集簇分层（LEACH）协议，提出了一种新型的簇首节点选择机制，通过加权思想综合考虑了节点的剩余能量和密度参数来优化簇首节点的选择，权衡簇首节点负载均衡和网络生存时间之间的关系，以得到较为理想的加权因子.仿真结果表明：在仿真区域面积为100 m×100 m、节点数目为100的条件下，相比于LEACH算法，该算法将第一个节点的死亡时间延长了19.6%，并且500轮后，网络中的剩余节点数是LEACH算法的5倍多，改善了节点能耗，有效提高了整个网络的生命周期.
关键词： 无线传感网（WSN）; 低功耗自适应集簇分层（LEACH）算法; 网络寿命; 簇首节点选取
中图分类号： TN929.5文献标志码： A文章编号： 1000-5137（2019）01-0001-06
Abstract： A new cluster head selection mechanism was proposed according to the classical low energy adaptive clustering hierarchy（LEACH） protocol.In the new algorithm，the cluster head selection was optimized by considering residual energy of nodes and density parameters of nodes comprehensively.Meanwhile，the relationship between cluster head load balancing and network lifetime was weighed to get an optimum weighting factor.The simulation results showed that，compared with LEACH algorithm，the proposed algorithm prolonged the death time of the first node by 19.6% when the simulation area was 100 m×100 m and the number of nodes was 100.The number of remaining nodes in the network after 500 rounds was more than 5 times that of LEACH algorithm，which improved the energy consumption of nodes and the whole network lifetime effectively.
0 引 言
無线传感器网络（WSN）是一种将传感测控技术、通信技术、嵌入式技术有机整合形成的一个新式协同系统[1].它由大量的传感器节点组成，通常用来检测一个区域的环境参数，并将收集到的数据发送给基站.由于其功耗低、无线传输、无线传感等特点，常常被应用于目标跟踪、环境检测等领域[2].但WSN电池能量有限且不易补充，有生存时间较短的问题，限制了其推广应用[3].
低功耗自适应集簇分层（LEACH）算法[4]是为了延长网络的生命周期而提出的一种分簇算法，分簇的基础是在网络中，将所有的节点划分为多个簇，每个簇中均有一个簇首节点，簇中的其他节点称为簇成员，簇首节点接收簇成员送来的采集信息，进行数据融合，并送到基站节点.由于LEACH算法在选取簇首节点时存在随机性，使得分簇不均，造成节点能量分布不均，影响网络寿命.杜超[5]提出低功耗自适应集中分层型（LEACH-C）算法，在选择簇首节点时，考虑了节点间的通信距离以及节点的剩余能量，解决了LEACH算法中通信方式和簇首节点选择的随机性.但是，LEACH-C算法过于依赖基站，增加了基站的能量消耗，降低了网络的稳定性.张辉等[6]提出了一种基于权值的LEACH改进算法，以权值作为选取簇首节点的一种数学度量，考虑了节点的能量、地理位置以及邻居节点数.该算法有效地提高了网络的生存时间，但簇首节点与基站之间的通信能耗过大.柴宝杰等[7]在非均匀分簇（EEUC）算法的基础上针对“空洞”节点（即某些节点并未加入任何一个簇）进行改进，但未考虑基站最优位置，影响节点的传输距离和消耗的能量.
本文作者结合了LEACH-C算法的优势，针对LEACH算法对簇首节点选择的随机性，提出了一种基于能量和密度的LEACH（LEACH-ED）改进算法.其基本思想是在簇首节点的选取中引入权值，综合考虑候选簇首节点的能量及位置信息，保证每轮都选取最佳节点做为簇首节点，同时根据节点的剩余能量确定进入下一轮大循环周期的条件，以期有效提高节点的生存时间，延长网络的生命周期.
1 LEACH算法
1.1 簇的建立
LEACH算法工作过程分为初始化阶段和稳定阶段.为了节省资源开销，稳定阶段的持续时间大于初始化阶段的持续时间.簇的建立过程可分成4个阶段：簇首节点的选择、广播、建立，和调度机制的生成.
1.1.1 初始化阶段
在簇首节点选取准备阶段开始时，每个节点产生一个值为0～1之间的随机数，并与阈值T（n） 进行比较，若随机值小于阈值则该节点当选为簇首节点，T（n）的计算公式如下：
其中，p为成为簇首节点的期望百分比，r为轮数，G为1p轮还没有当选簇首节点的节点集合，·为向下取整运算.
节点成为簇首节点后，向网络中广播自己成为簇首节点的消息，非簇首节点根据收到信号的强弱程度决定是否加入该簇，并向加入簇的簇首节点发送申请信息.当簇首节点收到申请加入信息后，通过时分多址（TDMA）建立通信时间表，并向簇内广播，至此，初始化阶段完成. 1.1.2 稳定阶段
簇内非簇首节点按照之前分配好的通信时间表，将采集到的数据发给簇首节点，随后进入休眠状态.簇首节点将接收到的数据进行融合后，转发给基站.稳定阶段的时间远远大于初始化阶段的时间.
1.2 LEACH算法的不足
LEACH 算法中，簇首节点的选举完全是随机的，易出现簇首节点分布不均的问题.而在智能家居应用中，传感器节点往往分布在由许多小区域组成的空间里，造成有的区域里有多个簇首节点，而有的区域里没有簇首节点，严重影响整个网络的寿命.此外，由于没有考虑到节点剩余能量因素，可能出现剩余能量低的节点重复当选簇首节点的问题，加速该节点的死亡速度，影响网络的寿命.
2 LEACH-ED算法
2.1 网络模型的假设
提出几点假设：1） 基站始终具备充足的能量，其余节点同构且初始能量相同;2） 所有节点一旦生成，位置不变，有唯一的ID标识;3） 接收节点可以根据接收到的信号强度计算与发射节点之间的距离，控制发射功率;4） 信道采取两种不同的工作模式——自由空间传输模式和多路径损耗模式.
2.2 无线通信能量消耗模型
2.3 LEACH-ED算法描述
利用加权思想对LEACH算法进行改进，使节点产生一个基于能量和密度的权值，通过这个权值概率阈值选择簇首节点，进而生成整个簇.该权值综合考虑了节点所处的网络环境和本身状态，节点的邻居节点越多，成为簇首节点的概率就越大，成为簇首节点的概率越大.
改进后的阈值其中，Eres为节点的剩余能量，E0为节点的初始能量，nneb为邻居节点数量，Ncnum为簇内成员数量，γ1与γ2分别为权值影响因子，且γ1+γ2=1.
改进后的算法流程图如图1所示.首先初始化节点，然后节点产生一个0～1之间的随机数，并与改进后的阈值进行比较，若小于阈值，则当选为簇首节点.考虑节点的剩余能量及密度所选取的簇首节点更为均匀合理.当节点的剩余能量低于网络的平均能量时，再重新选取簇首节点，减少了选取簇首节点的循环次数，进而减少了网络能耗.节点被选为簇首节点后，广播成簇消息，收到普通节点的加入请求后，簇首节点以TDMA方式为簇内成员分配时隙，进入稳定阶段.
3 仿真结果与分析
3.1 仿真环境以及模型配置
实验设置网络中有100个节点随机地分布在长宽为100 m×100 m的仿真场景内，基站位于坐标（50，50）处，网络拓扑图如图2所示.每帧数据为500 B，并假定各节点总有数据向基站发送[11].每个节点的初始能量设为0.02 J，Eda为0.02 nJ·bit-1·m-2，控制信息大小CM为32 bit，数据信息大小DM为 4000 bit，權值影响因子为0.55，网络中簇首节点个数所占比例p=0.1，Eelec=10 nJ·bit-1[12].
3.2 仿真波形及分析
通过Matlab仿真软件对传统LEACH算法以及LEACH-ED算法进行仿真，轮数-节点死亡数关系曲线如图3所示.由图3可知，随着轮数的不断上升，LEACH-ED算法的优势逐渐体现出来，与传统LEACH算法相比，提高了网络的生命周期.
4 结 论
在传统LEACH算法的基础上，考虑了节点的能量以及密度因素，提出改进的LEACH-ED算法，根据节点的剩余能量选取簇首节点，避免能量较低的节点再次当选簇首节点的情况，使网络中节点的剩余能量趋于平均.仿真实验结果表明：与LEACH算法相比，LEACH-ED算法延长了网络的生命寿命，降低了网络的平均能耗.但是该算法未考虑稳定阶段的传输问题，有待后续开展进一步的研究工作.
参考文献：
[1] 梁度，刘梦璐，章成驹.一种LEACH的分簇优化策略 [J].北京联合大学学报，2017，31（1）：75-80.
LIANG D，LIU M L，ZHANG C J.A clustering optimization strategy for LEACH [J].Journal of Beijing Union University，2017，31（1）：75-80.
[2] ARUMUGAM G S，PONNUCHAMY T.EE-LEACH：development of energy-efficient LEACH protocol for data gathering in WSN [J].Eurasip Journal on Wireless Communications and Networking，2015（1）：1-9.
[3] 韩广辉，张丽翠.基于LEACH协议的无线传感网能效分簇算法 [J].吉林大学学报（信息科学版），2017，35（1）：26-31.
HAN G H，ZHANG L C.Energy efficiency clustering in wireless sensor networks based on LEACH protocol [J].Journal of Jilin University （Information Science Edition），2017，35（1）：26-31
[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] 杜超.基于NS2的LEACH-C协议分析与仿真 [J].电子测量技术，2011，34（9）：121-123.
DU C.Analysis and simulation of LEACH-C protocol based on NS2 [J].Electronic Measurement Technology，2011，34（9）：121-123.
[6] 张辉，许峰.WSN中基于权值的LEACH协议的研究与改进 [J].微计算机信息，2010，26：199-201.
ZHANG H，XU F.Research and improvement of LEACH protocol for WSN based on weight value [J].Microcomputer Information，2010，26：199-201.
[7] 柴宝杰，马宝英，范书平，等.无线传感器网络中改进的EEUC路由算法 [J].微计算机信息，2012（9）：366-368.
CHAI B J，MA B Y，FAN S P，et al.Improved EEUC routing algorithms in wireless sensor networks [J].Microcomputer Information，2012（9）：366-368.
[8] 馮永亮，雷伟军.无线传感器网络LEACH协议的研究与改进 [J].信息技术，2016（2）：145-148.
FENG Y L，LEI W J.Research and improvement of LEACH protocol in wireless sensor networks [J].Information Technology，2016（2）：145-148.
[9] 邓亚平，邓利军.无线传感器网络的能量有效加权分簇算法 [J].计算机工程与设计，2011，32（4）：1216-1219.
DENG Y P，DENG L J.Energy-efficient weighted clustering algorithm for wireless sensor networks [J].Computer Engineering and Design，2011，32（4）：1216-1219.
[10] FENG X，ZHANG J，REN C，et al.An unequal clustering algorithm concerned with time-delay for internet of things [J].IEEE Access，2018，6：33895-33909.
[11] 林启中，张冬梅，王聪，等.基于位置信息的双簇头路由算法 [J].计算机应用，2015，35（3）：606-609.
LIN Q Z，ZHANG D M，WANG C，et al.Dual cluster head routing algorithms based on location information [J].Computer Application，2015，35（3）：606-609.
[12] SONY C T，SANGEETHA C P，SURIYAKALA C D.Multi-hop LEACH protocol with modified cluster head selection and TDMA schedule for wireless sensor networks [C]//Communication Technologies.Thuckalay：IEEE，2015：539-543.
（责任编辑：包震宇，顾浩然）
关键词： 无线传感网（WSN）; 低功耗自适应集簇分层（LEACH）算法; 网络寿命; 簇首节点选取
中图分类号： TN929.5文献标志码： A文章编号： 1000-5137（2019）01-0001-06
Abstract： A new cluster head selection mechanism was proposed according to the classical low energy adaptive clustering hierarchy（LEACH） protocol.In the new algorithm，the cluster head selection was optimized by considering residual energy of nodes and density parameters of nodes comprehensively.Meanwhile，the relationship between cluster head load balancing and network lifetime was weighed to get an optimum weighting factor.The simulation results showed that，compared with LEACH algorithm，the proposed algorithm prolonged the death time of the first node by 19.6% when the simulation area was 100 m×100 m and the number of nodes was 100.The number of remaining nodes in the network after 500 rounds was more than 5 times that of LEACH algorithm，which improved the energy consumption of nodes and the whole network lifetime effectively.
0 引 言
無线传感器网络（WSN）是一种将传感测控技术、通信技术、嵌入式技术有机整合形成的一个新式协同系统[1].它由大量的传感器节点组成，通常用来检测一个区域的环境参数，并将收集到的数据发送给基站.由于其功耗低、无线传输、无线传感等特点，常常被应用于目标跟踪、环境检测等领域[2].但WSN电池能量有限且不易补充，有生存时间较短的问题，限制了其推广应用[3].
低功耗自适应集簇分层（LEACH）算法[4]是为了延长网络的生命周期而提出的一种分簇算法，分簇的基础是在网络中，将所有的节点划分为多个簇，每个簇中均有一个簇首节点，簇中的其他节点称为簇成员，簇首节点接收簇成员送来的采集信息，进行数据融合，并送到基站节点.由于LEACH算法在选取簇首节点时存在随机性，使得分簇不均，造成节点能量分布不均，影响网络寿命.杜超[5]提出低功耗自适应集中分层型（LEACH-C）算法，在选择簇首节点时，考虑了节点间的通信距离以及节点的剩余能量，解决了LEACH算法中通信方式和簇首节点选择的随机性.但是，LEACH-C算法过于依赖基站，增加了基站的能量消耗，降低了网络的稳定性.张辉等[6]提出了一种基于权值的LEACH改进算法，以权值作为选取簇首节点的一种数学度量，考虑了节点的能量、地理位置以及邻居节点数.该算法有效地提高了网络的生存时间，但簇首节点与基站之间的通信能耗过大.柴宝杰等[7]在非均匀分簇（EEUC）算法的基础上针对“空洞”节点（即某些节点并未加入任何一个簇）进行改进，但未考虑基站最优位置，影响节点的传输距离和消耗的能量.
本文作者结合了LEACH-C算法的优势，针对LEACH算法对簇首节点选择的随机性，提出了一种基于能量和密度的LEACH（LEACH-ED）改进算法.其基本思想是在簇首节点的选取中引入权值，综合考虑候选簇首节点的能量及位置信息，保证每轮都选取最佳节点做为簇首节点，同时根据节点的剩余能量确定进入下一轮大循环周期的条件，以期有效提高节点的生存时间，延长网络的生命周期.
1 LEACH算法
1.1 簇的建立
LEACH算法工作过程分为初始化阶段和稳定阶段.为了节省资源开销，稳定阶段的持续时间大于初始化阶段的持续时间.簇的建立过程可分成4个阶段：簇首节点的选择、广播、建立，和调度机制的生成.
1.1.1 初始化阶段
在簇首节点选取准备阶段开始时，每个节点产生一个值为0～1之间的随机数，并与阈值T（n） 进行比较，若随机值小于阈值则该节点当选为簇首节点，T（n）的计算公式如下：
其中，p为成为簇首节点的期望百分比，r为轮数，G为1p轮还没有当选簇首节点的节点集合，·为向下取整运算.
节点成为簇首节点后，向网络中广播自己成为簇首节点的消息，非簇首节点根据收到信号的强弱程度决定是否加入该簇，并向加入簇的簇首节点发送申请信息.当簇首节点收到申请加入信息后，通过时分多址（TDMA）建立通信时间表，并向簇内广播，至此，初始化阶段完成. 1.1.2 稳定阶段
簇内非簇首节点按照之前分配好的通信时间表，将采集到的数据发给簇首节点，随后进入休眠状态.簇首节点将接收到的数据进行融合后，转发给基站.稳定阶段的时间远远大于初始化阶段的时间.
1.2 LEACH算法的不足
LEACH 算法中，簇首节点的选举完全是随机的，易出现簇首节点分布不均的问题.而在智能家居应用中，传感器节点往往分布在由许多小区域组成的空间里，造成有的区域里有多个簇首节点，而有的区域里没有簇首节点，严重影响整个网络的寿命.此外，由于没有考虑到节点剩余能量因素，可能出现剩余能量低的节点重复当选簇首节点的问题，加速该节点的死亡速度，影响网络的寿命.
2 LEACH-ED算法
2.1 网络模型的假设
提出几点假设：1） 基站始终具备充足的能量，其余节点同构且初始能量相同;2） 所有节点一旦生成，位置不变，有唯一的ID标识;3） 接收节点可以根据接收到的信号强度计算与发射节点之间的距离，控制发射功率;4） 信道采取两种不同的工作模式——自由空间传输模式和多路径损耗模式.
2.2 无线通信能量消耗模型
2.3 LEACH-ED算法描述
利用加权思想对LEACH算法进行改进，使节点产生一个基于能量和密度的权值，通过这个权值概率阈值选择簇首节点，进而生成整个簇.该权值综合考虑了节点所处的网络环境和本身状态，节点的邻居节点越多，成为簇首节点的概率就越大，成为簇首节点的概率越大.
改进后的阈值其中，Eres为节点的剩余能量，E0为节点的初始能量，nneb为邻居节点数量，Ncnum为簇内成员数量，γ1与γ2分别为权值影响因子，且γ1+γ2=1.
改进后的算法流程图如图1所示.首先初始化节点，然后节点产生一个0～1之间的随机数，并与改进后的阈值进行比较，若小于阈值，则当选为簇首节点.考虑节点的剩余能量及密度所选取的簇首节点更为均匀合理.当节点的剩余能量低于网络的平均能量时，再重新选取簇首节点，减少了选取簇首节点的循环次数，进而减少了网络能耗.节点被选为簇首节点后，广播成簇消息，收到普通节点的加入请求后，簇首节点以TDMA方式为簇内成员分配时隙，进入稳定阶段.
3 仿真结果与分析
3.1 仿真环境以及模型配置
实验设置网络中有100个节点随机地分布在长宽为100 m×100 m的仿真场景内，基站位于坐标（50，50）处，网络拓扑图如图2所示.每帧数据为500 B，并假定各节点总有数据向基站发送[11].每个节点的初始能量设为0.02 J，Eda为0.02 nJ·bit-1·m-2，控制信息大小CM为32 bit，数据信息大小DM为 4000 bit，權值影响因子为0.55，网络中簇首节点个数所占比例p=0.1，Eelec=10 nJ·bit-1[12].
3.2 仿真波形及分析
通过Matlab仿真软件对传统LEACH算法以及LEACH-ED算法进行仿真，轮数-节点死亡数关系曲线如图3所示.由图3可知，随着轮数的不断上升，LEACH-ED算法的优势逐渐体现出来，与传统LEACH算法相比，提高了网络的生命周期.
4 结 论
在传统LEACH算法的基础上，考虑了节点的能量以及密度因素，提出改进的LEACH-ED算法，根据节点的剩余能量选取簇首节点，避免能量较低的节点再次当选簇首节点的情况，使网络中节点的剩余能量趋于平均.仿真实验结果表明：与LEACH算法相比，LEACH-ED算法延长了网络的生命寿命，降低了网络的平均能耗.但是该算法未考虑稳定阶段的传输问题，有待后续开展进一步的研究工作.
参考文献：
[1] 梁度，刘梦璐，章成驹.一种LEACH的分簇优化策略 [J].北京联合大学学报，2017，31（1）：75-80.
LIANG D，LIU M L，ZHANG C J.A clustering optimization strategy for LEACH [J].Journal of Beijing Union University，2017，31（1）：75-80.
[2] ARUMUGAM G S，PONNUCHAMY T.EE-LEACH：development of energy-efficient LEACH protocol for data gathering in WSN [J].Eurasip Journal on Wireless Communications and Networking，2015（1）：1-9.
[3] 韩广辉，张丽翠.基于LEACH协议的无线传感网能效分簇算法 [J].吉林大学学报（信息科学版），2017，35（1）：26-31.
HAN G H，ZHANG L C.Energy efficiency clustering in wireless sensor networks based on LEACH protocol [J].Journal of Jilin University （Information Science Edition），2017，35（1）：26-31
[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] 杜超.基于NS2的LEACH-C协议分析与仿真 [J].电子测量技术，2011，34（9）：121-123.
DU C.Analysis and simulation of LEACH-C protocol based on NS2 [J].Electronic Measurement Technology，2011，34（9）：121-123.
[6] 张辉，许峰.WSN中基于权值的LEACH协议的研究与改进 [J].微计算机信息，2010，26：199-201.
ZHANG H，XU F.Research and improvement of LEACH protocol for WSN based on weight value [J].Microcomputer Information，2010，26：199-201.
[7] 柴宝杰，马宝英，范书平，等.无线传感器网络中改进的EEUC路由算法 [J].微计算机信息，2012（9）：366-368.
CHAI B J，MA B Y，FAN S P，et al.Improved EEUC routing algorithms in wireless sensor networks [J].Microcomputer Information，2012（9）：366-368.
[8] 馮永亮，雷伟军.无线传感器网络LEACH协议的研究与改进 [J].信息技术，2016（2）：145-148.
FENG Y L，LEI W J.Research and improvement of LEACH protocol in wireless sensor networks [J].Information Technology，2016（2）：145-148.
[9] 邓亚平，邓利军.无线传感器网络的能量有效加权分簇算法 [J].计算机工程与设计，2011，32（4）：1216-1219.
DENG Y P，DENG L J.Energy-efficient weighted clustering algorithm for wireless sensor networks [J].Computer Engineering and Design，2011，32（4）：1216-1219.
[10] FENG X，ZHANG J，REN C，et al.An unequal clustering algorithm concerned with time-delay for internet of things [J].IEEE Access，2018，6：33895-33909.
[11] 林启中，张冬梅，王聪，等.基于位置信息的双簇头路由算法 [J].计算机应用，2015，35（3）：606-609.
LIN Q Z，ZHANG D M，WANG C，et al.Dual cluster head routing algorithms based on location information [J].Computer Application，2015，35（3）：606-609.
[12] SONY C T，SANGEETHA C P，SURIYAKALA C D.Multi-hop LEACH protocol with modified cluster head selection and TDMA schedule for wireless sensor networks [C]//Communication Technologies.Thuckalay：IEEE，2015：539-543.
（责任编辑：包震宇，顾浩然）