WSN中基于灰狼和乌鸦搜索算法的簇头选择路由方案

王彦昆; 吴锋

doi:10.13718/j.cnki.xsxb.2021.05.024

摘要: 针对无线传感器网络的节点吞吐量低、生命周期短和延迟时间长等问题，提出一种基于灰狼和乌鸦搜索混合优化算法的簇头选择路由方案，该方案综合考虑节点剩余能量、节点间距离和传输延迟等因素，采用基于灰狼优化(Grey Wolf Optimization，GWO)和乌鸦搜索(Crow Search Algorithm，CSA)混合优化算法选择簇头，实现能量均匀利用，提高网络预期寿命.混合算法充分利用CSA算法的全局寻优和GWO算法的局部开发能力，提高了簇头选择过程中最优解的精度和可靠性.实验结果表明：本文提出的方案簇头选择性能良好，在吞吐量、传输速率和网络寿命方面比其他对比算法更具优势.

Abstract: Aiming at the problems of low throughput, short life cycle and long delay time of wireless sensor networks, a cluster head selection routing scheme based on gray wolf and crow search hybrid optimization algorithm has been proposed. In this scheme, the residual energy, the distance between nodes and the transmission delay are taken into account. The hybrid optimization algorithm based on grey wolf optimization (GWO) and crow search algorithm (CSA) is used to select cluster heads, which can realize the uniform utilization of energy and improve the expected life of the network. The hybrid algorithm makes full use of the global optimization ability of CSA algorithm and the local development ability of GWO algorithm, thus improving the accuracy and reliability of the optimal solution in the process of cluster head selection. The experimental results show that the proposed scheme has good cluster head selection performance, and has more advantages than other comparative algorithms in throughput, transmission rate and network life.

Key words:

全文HTML

无线传感器网络(Wireless Sensor Networks，WSN)是由多个空间分布的独立传感器组成的通信平台，广泛应用于目标跟踪、环境监测等领域^[1-2].在WSN中，通过不同的通信方式来传输传感器收集的数据.直接通信时，网络中存在节点到基站的直接路由，但是由于节点的长距离通信，导致能量消耗大，网络寿命低.间接通信一般采用多跳技术，多跳通信的使用减少了传感器节点能量的消耗，但是也会导致节点之间的干扰，从而影响网络性能^[3].为了减少干扰，基于聚类的数据收集方式在WSN中流行.每个簇中都有一个带有集中控制算法的簇头(Cluster Head，CH)和以随机方式分布的一组传感器^[4].每个CH都被允许在其自己的簇中保持能效.传感器节点的能耗问题一直是困扰无线传感器网络的难点之一.

为了最大限度地降低传感器节点能耗，延长网络寿命，研究人员已经开发了多种提高节点能量使用效率的簇头选择优化算法.Reddy等^[5]采用自适应鲸鱼优化算法，通过结合WSN中传感器节点的能量、距离和延迟等参数，实现了能量感知型簇头的选择.Poonguzhali等^[6]使用蚁群算法与和声搜索算法来优化簇头选择和最小密度簇，通过减少路由路径，加快数据包传输速度来达到能耗降低的目的.冉涌^[7]提出一种多事件节能蚁群优化数据传输无线网络传感器协议，该协议根据簇中节点剩余能量和距离基站的长度来选择簇头，利用蚁群算法优化通信路径，有效提高了网络的寿命和传输性能.Mittal等^[8]为了克服基于聚类分层方法的局限性，提出一种基于阈值敏感节能聚类协议的模糊扩展灰狼优化算法，采用模糊聚类和灰狼算法对簇头选择和路由路径进行优化.

现有的群智能优化方法对WSN网络的节点能耗及路由选择起到一定的优化作用，但这些算法也容易出现局部最优、收敛速度慢和精度不够等问题.为了进一步提高节能效率和吞吐量以及延长网络寿命，本文提出基于灰狼和乌鸦搜索混合优化算法的簇头选择路由方案，该混合算法是将乌鸦搜索算法引入灰狼优化中，解决了由于GWO算法早熟收敛而无法有效地搜索最优解的问题.混合算法通过考虑延迟时间、节点传输距离和能耗等方面来选择簇头，在保证无线传感器自组织网络的高效簇和路由的同时，提高节点的能量利用率，延迟网络寿命.

1. 相关内容

1.1. 灰狼优化算法

灰狼优化算法(Grey Wolf Optimization，GWO)是模拟自然界灰狼族群狩猎行为而提出的一种启发式方法^[9]，具有操作简单、调节参数少等优点.在GWO算法中，种群分为头狼α、从属狼β、普通狼δ和底层狼ω共4种，狼群在狩猎时假定α、β和δ具有获得潜在猎物所在位置的能力，因此在迭代过程中优先找出三者的个体位置，并以此更新下一代个体的位置，最终达到捕食猎物的目的.假定D维搜索空间中，种群数量为N，灰狼个体的位置定义为X，则由式(1)和式(2)计算出个体与α，β和δ的距离为

式(2)中：t表示当前迭代，A=2ar₁-a和C=2r₂表示协同系数向量，r₁和r₂表示随机向量，a表示收敛因子，其元素在迭代过程中由2线性递减到0，即：

式(3)中：T_max表示最大迭代次数.个体向猎物移动的方向可以表示为

GWO算法经过多次迭代后捕获猎物，得到最优解.GWO算法在许多领域中获得了较成功的应用，但是算法也存在解精度低、早熟收敛过快和容易陷入局部最优等缺点.

1.2. 乌鸦搜索算法

乌鸦搜索算法(Crow Search Algorithm，CSA)是根据乌鸦觅食行为而提出来的一种智能算法^[10].在CSA算法中，乌鸦存储食物的位置代表问题的可行解，乌鸦通过搜寻存储食物最多的位置获得最优解.假定乌鸦群体总量为N，第i只乌鸦在第t次迭代时的位置为x_i(t)，食物存储位置为m_i(t).当乌鸦i随机选择乌鸦j进行跟踪时，跟踪过程中会出现两种情况：①乌鸦j未发现乌鸦i的跟踪，则乌鸦i偷取j的食物；②乌鸦j发现乌鸦i的跟踪，则乌鸦j随机飞行，避免食物被偷.综合两种情况，乌鸦i的位置更新公式为

式(5)中：r_i，r_j为随机数，fl_i(t)和p_i(t)为乌鸦i在第t次迭代时的飞行步长和感知概率.使用更新的乌鸦个体对食物存储位置进行更新.CSA算法通过飞行步长和感知概率2个参数来控制算法的全局和局部搜索进程，经过多次迭代后获得问题的最优解.CSA算法具有参数少、操作灵活、易于实现的优点，但是也存在收敛速度慢和寻优搜索盲目性的缺陷.

2. 基于灰狼优化和乌鸦搜索的簇头选择方案

本文提出一种基于灰狼和乌鸦搜索混合优化算法的最优簇头选择方案，该方案通过将灰狼优化算法与乌鸦搜索算法相结合，解决了由于早熟收敛而无法有效地搜索最优解的问题.混合算法通过考虑延迟时间、节点传输距离和能耗等方面来选择簇头，在保证无线传感器自组织网络的高效簇和路由的同时，提高了节点的能量利用率，延迟了网络的寿命.

2.1. 网络模型

对于无线传感器网络，本文的网络模型设置为：面积为M×M的监测区域内随机布置N个节点，基站布置在传感场内，节点和基站位置不可移动；所有传感器节点的初始能量相同，可以获取自身的剩余能量和位置；节点根据接收到的信号强度，可以计算相邻节点之间的距离.根据文献[11]，当网络节点发送kbit数据到距离为dm处的相邻节点时，需要消耗的能量为

式(6)中：E_elec表示接受和发送1 bit数据时电路的功耗系数，ε_fs和ε_mp分别表示自由空间和多径衰落模型下的功耗常数.同理，节点接收和处理kbit数据的能量消耗为

式(9)中：E_da表示处理1 bit数据时的能耗.

2.2. 基于混合算法的簇头选择

簇头的选择对路由算法的性能影响重大，为了节省传感器节点的能量，本文采用基于GWO-CSA算法对簇头选择进行优化.在传统的GWO中，每次迭代算法根据α，β和δ灰狼的位置对狼群其他个体进行更新，导致全局搜索能力较弱，容易陷入局部最优.而CSA算法在式(5)描述的位置更新搜索方程中，飞行步长fl和感知概率p作为控制参数允许群内个体从当前区域跳入其他区域，全局搜索能力较强.混合算法充分利用GWO算法与CSA算法的优点，实现探索和开发阶段之间的适当平衡.

在无线传感器网络中，节点的剩余能量、距离以及密度都能够影响簇头的选择.因此，本文将适应度函数定义为

能量因素E、距离因素D和密度因素S分别表示为

式(11)中：E_i是节点i的剩余能量，E_avg是节点i所在区域内的剩余能量，D_i是节点i到基站的距离，D_max和D_avg分别是区域内节点到基站的最大距离和平均距离，S_i是节点i的邻居数，S_max和S_min分别是最大和最小邻居数.式(10)中λ₁，λ₂和λ₃为权重因子，和值为1.

基于混合算法的簇头选择具体过程如下：

步骤1：对传感器网络节点、GWO种群以及参数进行初始化；

步骤2：根据式(10)计算种群个体的适应度值，并对其排序，选出α和β灰狼，其值所在位置对应的传感器节点极有可能被选为簇头；

步骤3：基于CSA的感知概率，设定混合算法的自适应平衡概率P_AB为

自适应平衡概率P_AB是为了平衡探索阶段和开发阶段，保证算法在优化早期阶段获得种群多样性和较大的空间搜索能力，同时在优化后期具有较强的局部搜索能力和收敛性.

步骤4：在式(1)和式(2)的基础上，利用式(15)、式(16)更新传感器节点的位置为

式(16)中：rand是区间[0, 1]上的随机数，FL是飞行步长.CSA算法中FL的大值用于全局探索，FL的小值用于局部开采.为了利用CSA的全局探索优点，使用较大的FL值.本文没有采用传统GWO算法使用的3个最优解，而是采取了缩减方法：当P_AB大于rand时选择式(15)，采用α和β两个最优解更新节点位置；否则采用式(16)，仅α一个最优解控制搜索方向.取消δ灰狼是为了减弱最优解对探测范围的影响.

步骤5：对当前迭代的自适应平衡概率P_AB和收敛因子a进行更新.为了获得更好的寻优性能，收敛因子采用非线性变换形式为

步骤6：根据式(10)计算种群个体的适应度值，更新α和β值；

步骤7：判断算法是否终止条件，若满足，输出最优解α，其对应的节点位置被选为簇头，算法终止；否则，t=t+1，返回步骤2.

2.3. 数据转发

簇头选择旨在提高所有收集信息的准确性.簇头选出之后，将向周围节点广播自己成为簇头的消息，簇成员根据收到的广播消息选择距离自己最近的簇头加入该簇，并发送包含自己位置和剩余能量的信息.当网络中的节点成簇后，通过簇头构建多跳路由.首先，簇内节点将收集到的信息发送至簇头节点.由于节点距离和监视区域之间存在重叠，因此传感器节点收集的数据存在冗余信息.在传输过程中，冗余信息增加了节点能耗，减少了无线传感器网络的寿命.因此，簇头节点需要将消息融合去掉冗余的消息，本文采用K-means算法对数据进行融合，将参量相近的数据聚成一类，提取关键信息.最后，当簇头位置与基站之间的距离较近时，簇头选择直接将信息传输到基站；当两者距离较远时，通过其他簇头以多跳的方式选择跳数最小的路径，把数据传送给基站.

4. 结语

本文提出的基于灰狼和乌鸦搜索混合优化算法的簇头选择路由方案，主要用于解决无线传感器网络节点吞吐量低、生命周期短和延迟时间长等问题.该算法考虑了节点剩余能量、节点之间的距离和延迟时间等因素，结合GWO算法的局部开发潜力和CSA算法的全局优化能力在基于簇头选择过程中实施动态搜索，通过优化选择簇头的精度来实现能量的均匀利用，进而提高网络的预期寿命.相比于其他算法，本文提出的方案在吞吐量、传输速率和网络寿命方面性能更佳.

参考文献 (13)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

[1]	董发志, 丁洪伟, 杨志军, 等. 基于遗传算法和模糊C均值聚类的WSN分簇路由算法[J]. 计算机应用, 2019, 39(8): 2359-2365. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201908029.htm
[2]	RESHMA J, SATISH KUMAR T, VANI B A, et al. Big Data Oriented Energy Aware Routing for Wireless Sensor Networks [J]. Mobile Networks and Applications, 2019, 24(2): 298-306. doi: 10.1007/s11036-018-1042-y
[3]	MASOOD M, FOUAD M M, SEYEDZADEH S, et al. Energy Efficient Software Defined Networking Algorithm for Wireless Sensor Networks [J]. Transportation Research Procedia, 2019, 40: 1481-1488. doi: 10.1016/j.trpro.2019.07.205
[4]	VIJAYALAKSHMI K, ANANDAN P. A Multi Objective Tabu Particle Swarm Optimization for Effective Cluster Head Selection in WSN [J]. Cluster Computing, 2019, 22(5): 12275-12282. doi: 10.1007/s10586-017-1608-7
[5]	REDDY M P K, BABU M R. Implementing Self Adaptiveness in Whale Optimization for Cluster Head Section in Internet of Things [J]. Cluster Computing, 2019, 22(1): 1361-1372. doi: 10.1007/s10586-017-1628-3
[6]	POONGUZHALI P K, ANANTHAMOORTHY N P. Improved Energy Efficient WSN Using ACO Based HSA for Optimal Cluster Head Selection [J]. Peer-to-Peer Networking and Applications, 2020, 13(4): 1102-1108. doi: 10.1007/s12083-019-00814-3
[7]	冉涌. 多事件节能的无线网络传感器协议[J]. 西南师范大学学报(自然科学版), 2019, 44(5): 126-131. doi: http://xbgjxt.swu.edu.cn/article/doi/10.13718/j.cnki.xsxb.2019.05.021
[8]	MITTAL N, SINGH U, SALGOTRA R, et al. An Energy Efficient Stable Clustering Approach Using Fuzzy Extended Grey Wolf Optimization Algorithm for WSNS [J]. Wireless Networks, 2019, 25(8): 5151-5172. doi: 10.1007/s11276-019-02123-2
[9]	KAUSHIK A, INDU S, GUPTA D. A Grey Wolf Optimization Approach for Improving the Performance of Wireless Sensor Networks [J]. Wireless Personal Communications, 2019, 106(3): 1429-1449. doi: 10.1007/s11277-019-06223-2
[10]	MAHESH N, VIJAYACHITRA S. DECSA: Hybrid Dolphin Echolocation and Crow Search Optimization for Cluster-Based Energy-Aware Routing in WSN [J]. Neural Computing and Applications, 2019, 31(1): 47-62. doi: 10.1007/s00521-018-3637-4
[11]	doi: http://www.researchgate.net/publication/327073236_A_hierarchical_adaptive_routing_algorithm_of_wireless_sensor_network_based_on_software-defined_network/download ZHAO Z N, WANG J, GUO H W. A Hierarchical Adaptive Routing Algorithm of Wireless Sensor Network Based on Software-Defined Network [J]. International Journal of Distributed Sensor Networks, 2018, 14(8): 1-15.
[12]	doi: http://www.researchgate.net/publication/332226901_An_Improved_Fruit_Fly_Optimization_IFFOA_based_Cluster_Head_Selection_Algorithm_for_Internet_of_Things POLURU R K, LOKESH K R. An Improved Fruit Fly Optimization(IFFOA)Based Cluster Head Selection Algorithm for Internet of Things [J]. International Journal of Computers and Applications, 2019(4): 1-9.
[13]	MURUGAN T S, SARKAR A. Optimal Cluster Head Selection by Hybridisation of Firefly and Grey Wolf Optimisation [J]. International Journal of Wireless and Mobile Computing, 2018, 14(3): 296-305. doi: 10.1504/IJWMC.2018.092373

留言板