面向不同目标覆盖要求的异构有向传感器网络节点调度算法

李明　林新宇　彭鹏

摘要：针对给定部署区域中不同的监测目标有不同的覆盖需求和现有的调度算法大多针对同构有向传感器节点忽略了节点异构对调度性能的影响的问题，提出两种异构有向传感器网络节点调度策略。一种方法是通过对问题进行数学建模，将节点调度问题转化为目标优化问题，采用改进的和声搜索算法进行求解。改进和声搜索算法针对原始和声搜索在陷入局部最优时的过早收敛问题，通过将和声搜索算法和模拟退火算法结合增强其局部搜索能力。另一种方法采用贪婪算法求解满足条件的节点集合。仿真结果显示，与原始和声搜索算法相比，改进和声搜索算法能有效提高网络的工作时间，证明了改进算法的有效性。

关键词：有向传感器网络;异构网络;和声搜索算法;模拟退火算法;节点调度

中图分类号：TP393    文献标识码：A

文章编号：1009-3044（2021）03-0001-04

Abstract： Two node scheduling strategies for heterogeneous directional sensor networks are proposed to solve the heterogeneous coverage requirements of the targets in the deployed area. The characteristic of node heterogeneity and heterogeneous coverage requirements of the targets have great impacts on performance of scheduling algorithm， which are neglected by most of the existing research. One of the proposed algorithms formulate the scheduling problem as an objective optimization problem and improved harmony search algorithm （shortly for IHS） is utilized to address such scheduling problem. The IHS hybrid harmony search algorithm and simulated annealing algorithm to address the premature convergence problem especially when one or more initial harmonies are in the vicinity of local optimal. The other proposed algorithm is based on greedy algorithm to construct as more cover set as possible. Simulation results shows that the proposed IHS achieves better performance than the primitive harmony algorithm （shortly for HS）， which proves the effectiveness of the proposed algorithm.

Key words： directional sensor networks; heterogeneous network; harmony search algorithm; simulating annealing algorithm; node scheduling

随着传感器网络应用广度和深度不断拓展，由视频传感器、声音传感器和雷达传感器等有向感知模型的传感器节点构成的有向传感器网络在工程实践中得以广泛应用[1]。如何更有效的实施目标监测和延长网络寿命，是有向传感器网络应用时需要解决的关键问题。节点调度是一种降低传感器网络能耗和延长网络工作时间的有效方法，得到了越来越多研究者的重视[2]。文献[3]提出一种公平的有向传感器网络方向优化和节点调度算法。文献[4]提出一种基于离散网格的有向传感器网络冗余节點调度算法。文献[5]通过建立目标部署圆内覆盖最多邻居目标点的候选节点集合对随机部署的节点进行调度，提出一种面向目标的有向传感器网络连通覆盖算法。文献[6]提出了一种基于启发式的有向传感器网络节点调度算法延长网络寿命。文献[7]提出了一种基于贪婪算法的应用于智能城市场合的有向传感器网络节点调度算法。在异构有向传感器网络方面，文献[8]提出一种基于遗传算法的感知半径可调的有向传感器网络节点调度算法。文献[9]提出一种自动学习机的异构节点调度算法延长网络寿命。

上述文献[3]到文献[7]都是针对相同参数的有向传感器节点也就是同构传感器节点，忽视了在工程实践中，由于制造工艺等原因传感器节点的性能参数不可能完全相同，异构才是有向传感器节点最普遍的存在方式，使得上述成果不能很好应用工程实际。针对离散目标监测这种应用场合，尽管文献[8]和文献[9]对异构有向传感器节点调度问题进行研究并取得了一定的研究成果，但由于实际应用中目标出现的频率不尽相同，导致监测目标的重要性也不尽相同。对于重要的监测目标为了保证监测质量和容错性的要求，一般采用多个节点同时监测同一个重点监测目标。也就是说，不同的监测目标有不同的监测（覆盖）要求。上述两篇文献忽略了监测目标覆盖的要求可能不同，导致研究成果适用性受到限制。针对上述文献存在的问题，本文提出了两种算法——基于改进和声搜索算法和基于贪婪算法的异构有向传感器节点调度算法来解决具有不同覆盖要求的目标监测的应用场合的异构有向传感器网络中节点调度问题，以延长网络工作时间和增强网络的服务质量。

1 问题模型分析

假定平面区域A中，分布有N个有向传感器节点和T个需要监测的目标Ti （i =1，2，...，T），假定有向传感器节点的感知方向Di的数量为|Di|（i =1，2，...，N）和寿命Li （i =1，2，...，N）均不同，且同一时刻只能有一个感知方向处于工作状态。监测目标具有不同的优先级，分为优先级高的监测目标和优先级低的监测目标，其中优先级高的监测目标要求同时被多个传感器节点监测（覆盖）到，优先级低的监测目标只要被传感器节点监测到即可。如何在保證满足监测目标监测的要求条件下，尽可能延长传感器网络的寿命是本文要研究的问题。

根据上文的阐述，我们采用集合覆盖的思想，将传感器网络节点集合划分成多个符合监测目标监测覆盖要求的集合，通过集合之间不同的切换，达到延长网络寿命的目标。用形式化的语言可描述为：

[其中xi，j，k=1 if Di，j∈Ck0 其他，tk≥0]tk表示每个集合的工作时间，K表示划分的覆盖集合最大数量，Di，j表示节点Si的第j感知方向，Ck表示第k个满足条件的覆盖集合，Li表示节点Si的寿命，C_Tm表示能覆盖监测目标Tm的感知方向的集合，[m=1，2，…，T];[ Req（Tm）]表示监测目标Tm的监测要求。式子（2）保证节点工作的时间不会超过它的寿命;式子（3）保证在满足条件的集合中一个传感器节点最多只有一个感知方向处于工作状态;式子（4）保证每个监测目标的监测要求都能被满足，Req（Tm）为对目标Tm的监测要求，为正整数，具体取值根据目标的重要性确定。

2 改进和声搜索算法

2.1 原始和声搜索算法简介

和声搜索算法通过对音乐家的创作过程进行模拟，将决策变量和解向量分别类比乐器的音调和各种音调的和声，优化目标和种群分别类比适应度（评价）函数和和声记忆库，通过不断的迭代优化来实现问题的求解[10]。算法步骤包括初始化和声记忆库（ harmony memory，HM），新产生的解有两部分来源，一部分来源于HM，其占比为HMCR;另一部分在问题可行区域内随机取值。来源于HM的新解以概率PAR用参数BW进行局部扰动。若新产生解的适应度函数优于HM原有的最差解，则新解替换最差解。算法不断迭代进行上述步骤直到满足停止的条件[11]。

原始的和声搜索若在算法初始化时产生的解向量若在问题的局部值附近，则容易陷入早熟收敛，影响算法的优化效率。针对这一问题，借鉴模拟退火算法的思想和其局部搜索能力强的优点，将模拟退火算法与和声搜索算法结合，提出一种改进的和声搜索算法

2.2 改进的和声搜索算法IHS

改进算法的步骤同原始和声搜索算法相同，区别在于对于最差解的处理。原始和声搜索算法中若新产生的解优于最差解，则最差解被新产生的解替换。改进算法IHS中考虑到算法可能陷入局部最优的状况，结合模拟退火算法的思想，针对种群进化过程中的由于局部最优而导致过早收敛问题，采用对最差解以一定概率接受的策略，增强种群的多样性以提升算法优化能力。改进和声搜索算法的伪代码为：

输入：和声搜索算法参数，包括：HMCR，PAR， BW和初始化记忆库HMS;模拟退火算法参数，包括初始温度T0，温度变化参数α

输出：最优和声（解向量）

初始化和声搜索算法参数HMCR ，PAR， BW和和声记忆库HMS

初始化模拟退火算法T0，并设T=T0

1 While（和声搜索算法不满足结束条件）

2 Find current worst harmony in HM

3 For i=1 to Dim

4 If（rand（）<=HMCR）

5 Hi =[HMji] where j = rand_int（1，col （HM））

6 If （rand（）<=PAR）

7 Hi = Hi[±]rand（）×BW

8 End if

9 Else

10 Generate Hi randomly within the allowed bounds

11 End if

12 End for

13 Dif = f（H）-f（Worst）

14 If（Dif <0 or rand（）<[e-DifT']）

15 Update HM by replacing Worst harmony by H

16 End if

17 T =α×T

18 End while

19 Output Best harmony as solution

上述的伪代码其中行1-行18为和声搜索算法迭代过程，行2先寻找当前的最差的和声个体，行3-行12对于每个和声个体的每一维执行和声算法步骤，也就是每一维有概率HMCR来源自原来的和声记忆库HM，这部分个体中有PAR比率的个体会进行参数为BW的随机扰动以增加个体多样性;有1-HMCR概率是在问题可行区域内随机取值。对于新产生的和声个体若优于最差和声（行14，此处假定求最小值问题）或者满足rand（）<[e-DifT']条件（行14），则新个体替换最差个体。算法最后输出最优和声个体作为问题的解。Dim为优化问题的维数，函数f（）为待求解问题的函数，rand（）为区间（0，1）之间的随机数;函数rand_int（A，B）为返回整型数A到B之间的随机整数;col（C）作用为返回向量C的列向量个数。

2.3 节点调度问题的求解

利用和声搜索算法解决异构节点调度问题时，要解决优化目标的选择，适应度函数的设计，以及解的表示也就是编码问题三个关键问题。

1）优化目标

对于本文的优化问题，一方面要使满足覆盖条件的集合数量最大化，另一方面使得节点剩余寿命（跟节点的能量成正比）最大化。根据文献[12]满足覆盖条件节点集合数的上限值K为能覆盖监测要求最高目标的节点的寿命（若有多个节点，则选择寿命最小的）与监测要求最大值的比值，即[K=Lgmax（t）]，其中，L表示能覆盖监测要求最高目标的节点的寿命;gmax（t）表示监测目标中监测要求最大的值。

本文要优化的目标有两个：符合覆盖要求的节点集合和节點的剩余寿命，即：

其中Q为满足覆盖要求的集合格式，f1取值范围为[0，1]; f2为剩余寿命，tanh为双曲正切函数，β为比例系数，在本文中设为1;f2值域为[0，1]。

2）适应度设计

根据对优化目标的分析，对于本文的多目标优化算法，采用文献[13]随机加权的方式，将多目标优化问题转化为单目标优化问题。两个目标函数对应的权值按照下面的式子确定：

3）问题编码表示

种群中的每个个体代表求解问题的一个候选解，本文中采用整型编码的方法，编码示意图如图1所示。

3 贪婪算法

为了验证提出的IHS的节点调度算法的性能，提出一种基于贪婪算法的离散目标节点覆盖算法作为比较算法。贪婪算法的思想为每次选择节点剩余能量最多的且同时能覆盖最多监测目标的感知方向（在实现时，用这两个指标的乘积的值确定），其主要步骤为：

1） 初始化算法参数，包括可用的传感器集合S_K，设置其初值为所有的传感器节点;目标监测要求集合Req_T，并设置临时目标监测要求集合temReq_T，使其等于Req_T;传感器节点的寿命Li;已覆盖目标集合covered_T ={}，未覆盖目标集合uncovered_T ，并赋初值为监测目标集合T;节点是否用过数组isUsed，并设初值为0，表示所有节点均没用过;存储满足覆盖条件的结果集合Result = {}，该集合中每个元素都为满足覆盖要求的感知方向集合;对于每一个节点Si的每一个感知方向Di，j，求解其对应的COVi，j和D_Ti，j;

2）符合覆盖要求的集合求解： 对于每个传感器节点的每个感知方向，计算COVi，j [×]Li 的值，并按照值的大小进行排序;

3）节点参数和监测目标覆盖状况更新。通过每一次选择合适的感知方向后，考虑到同一时刻一个传感器节点只能有一个感知方向处于工作状，将该感知方向和该感知方向所属的传感器节点删除。当所有的监测目标都符合覆盖要求时，更新有向传感器节点的寿命，同时重新计算COVi，j [×]Li 的值。若有寿命为0的传感器节点，则将此节点从可用传感器节点集合S_K中删除。并且将变量Req_T、uncovered_T和isUsed按照（1）重新初始化，继续下一轮的贪婪算法，直到节点寿命为0或没有符合覆盖要求的节点集合。每一轮贪婪算法的主要步骤为：

（1）判断当前可用的感知方向是否能符合目标覆盖的要求，若不符合直接执行6）;否则执行2） ;

（2）当uncovered_T不空时（或者还有未符合覆盖要求的监测目标时），选择值最大的COVi，j [×]Li，并将传感器节点的序号和感知方向序号放入集合Result，即Result=Result∪{{i，j}}。若值最大的感知方向有多个则选择序号最小的节点和感知序号 ;

（3）更新所选节点的isUsed数组的值，设为1 ;

（4）根据D_Ti，j，更新监测目标要求集合temReq_T。根据更新集合的情况，若已有监测目标符合覆盖要求，则更新未覆盖目标集合uncovered_T ;

（5）继续执行步骤2），否则执行步骤6）;

（6）得到求解结果R 。

4 仿真结果与分析

4.1 仿真环境设置

在MATLAB平台对本文提出的算法进行仿真验证。节点部署区域设为50×50，部署节点数量N为30，节点的其他参数设置如表4所示。监测目标数T为6，分为两种类型：重点目标和非重点目标，其中对于重点目标，要求覆盖度不少于2，其余目标覆盖度为1，每一种类型的监测目标数量随机产生。β和声搜索算法的参数设置为：种群数为50，迭代次数为400，HMCR为0.8，PAR =0.4，BW = 0.01。模拟退火算法中T = T0=100， α=0.99。

4.2 仿真结果及分析

1）不同节点密度下集合数目比较

为比较改进算法IHS和原始IHS算法在问题求解过程中的性能，对两种算法在求解过程中的平均适应度进行比较。结果如图2所示。从图中可以看出，随着部署节点数量的增加，IHS算法、原始HS算法和贪婪算法求得的满足条件的集合数量也随之增加，究其原因在于，节点数量增加后能参与目标覆盖的感知方向随之增加，满足覆盖要求的感知方向集合也就相应的增加;在部署节点数和监测目标数量一定的条件下，改进HIS算法优于原始HS算法和贪婪算法，证明了IHS算法改进方案的有效性。

2）适应度比较

将监测目标数T设为6，节点数N为45，其他参数如4.1设置，比较改进算法IHS和原始和声搜索算法HS的平均适应度，每个算法运行30次，并取30次实验的平均值作为算法的结果。仿真结果如图3所示。从图中可以看出，随着迭代次数的增加，平均适应度都在增加，且趋于收敛;同时，改进算法IHS的平均适应度优于原始和声搜索算法，证明了改进算法的有效性。

5 结论

本文提出了一种基于改进和声搜索算法的节点调度策略，解决在异构有向传感器节点网络中面向不同目标监测要求的情形下的传感网寿命的最大化问题。在未来，将研究分布式的异构有向传感器节点调度策略，降低集中式算法执行过程中消息通信带来的功耗，从而进一步优化异构有向传感器网络的能源使用效率。

参考文献：

[1] H.Shen， G.Bai. Routing in wireless multimedia sensor networks： A survey and challenges ahead[J]. Journal of Network and Computer Applications， 2016， 71：30-49.

[2] P. Musilek， P. Kr?mer， T. Bartoň. Review of nature-inspired methods for wake-up scheduling in wireless sensor networks[J]. Swarm and Evolutionary Computation， 2015， 25：100-118.

[3] 温俊， 蒋杰， 窦文华.公平的有向传感器网络方向优化和节点调度算[J].软件学报， 2009，20（3）： 644-659.

[4] 高睿. 有向传感器网络覆盖和节点冗余算法研究[D].太原： 太原理工大学， 2018.

[5] 黄帅，程良伦. 一种面向目标的有向传感器网络连通覆盖算法[J].传感器与微系统， 2012，31（1）： 65-68，72.

[6] A. Singh， A. Rossi， M. Sevaux. Heuristics for lifetime maximization in camera sensor networks[J]. Information Sciences. 2017，385–386： 475–491.

[7] S. Sharmin， F.N. Nur， M.A. Razzaque， M.M. Rahman， A. Almogren， M.M. Hassan.Tradeoff between sensing quality and network lifetime for heterogeneous target coverage using directional sensor nodes[J]. IEEE Access 2017，5：15490–15504.

[8] A.Alibeiki， H.Motameni，H. Mohamadi. A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges[J]. Pervasive and Mobile Computing， 2019，52： 1–12.

[9] 李明，胡江平.基于学习自动机的异构有向传感器节点调度算[J].计算机工程，2018， 44（8）：199-203.

[10] T. Zhang， Z.W.Geem. Review of harmony search with respect to algorithm structure[J]. Swarm and Evolutionary Computation， 2019，48（8）： 31-43.

[11] 李明，曹晓莉，胡卫军.基于多目标和声搜索的无线传感器网络分簇路由算法[J].仪器仪表学报，2014，35（1）：162-168.

[12] Cardei M.， Thai M， Li Y. ， et al. Energy-efficient target coverage in wireless sensor networks. In Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies （INFOCOM）， Miami， FL， USA， 13-17 March 2005，2005： 1976-1984.

[13] Ishibuchi HMurata.Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[J].  IEEE Trans. Syst. Man. Cy. B， 1998，28（3） ：392-402.

【通聯编辑：代影】