基于集合覆盖的异构有向传感网寿命优化策略*

李 明，林新宇

(1.重庆工商大学 计算机科学与信息工程学院检测控制集成系统工程实验室, 重庆 400067; 2.电子科技大学 自动化工程学院, 成都 611731)

0 引 言

目前，微机电技术的发展和芯片价格的降低促使有向传感器网络得到广泛应用[1-2]。如何在保证监测质量的前提下，延长有向传感器网络的寿命受到了越来越多研究者的重视[3]。文献[4]对有向传感器网络节点调度算法进行研究并提出了一种优化策略,但该策略未考虑节点感知角度、感知半径等参数的不同对算法性能的影响；文献[5]通过建立目标部署圆内覆盖最多邻居目标点的候选节点集合对随机部署的节点进行调度，保证网络的生存时间，该文献假定参与连通覆盖的节点为同构节点，不利于网络扩展；文献[6]借助虚拟节点提出了一种休眠唤醒策略延长网络寿命；文献[7]提出一种基于分簇的有向传感器网络节点调度算法，通过减少工作节点的数量来延长网络寿命；文献[8]提出了一种基于启发式的有向传感器网络节点调度算法延长网络寿命；文献[9]提出一种基于集合覆盖的节点调度算法。上述文献都是针对同构有向节点展开研究，忽略了节点异构性对算法性能的影响，使其适用范围受到限制。文献[10-11]对半径可调的有向传感器网络覆盖问题进行研究，分别提出基于启发式和遗传算法的节点覆盖调度策略；文献[12-13]对异构有向传感器网络的调度算法进行研究，分别提出了基于学习自动机和差分进化算法解决策略，但算法复杂度较高。同时，在目标监测这种应用场景下，监测目标本身具有不同的重要性(优先级)，比如在森林林火预警和工业化学品监测中，易燃林木和易燃易爆化学品集中区域较其他监测区域更容易发生危险。为保证监测质量和满足网络容错性的要求，在监测中应部署多个传感器同时监测这些重点目标区域。上述的绝大部分文献都忽视了监测目标重要性对网络监测的要求，导致研究成果不能很好地应用在实践中。

针对上述文献存在的问题，在考虑节点参数异构性和由于监测目标重要性不同导致的覆盖要求不同以及满足网络容错性的条件下，提出一种基于集合覆盖的异构有向传感器网络寿命最大化策略，增强网络的服务质量。

1 问题模型

(1)

∀i,i∈[1,N]

(2)

∀k,k∈[1,K]

(3)

∑Di,j∈C_Tk,mxi,j,k≥Req(Tm)

∀k,m,k∈[1,K],m∈[1,W]

(4)

其中：tk表示每个集合的工作时间；K表示划分的符合要求的集合最大数量；Di,j表示节点si的第j感知方向；Ck表示第k个满足条件的覆盖集合；Ei表示节点si当前的能量；C_Tk,m表示在Ck中能覆盖监测目标Tm的感知方向的集合，m=1,2,…,W；Req(Tm)表示监测目标Tm的监测要求，即要求同时被多少个传感器节点监测到，取值为正整数。式(2)保证节点工作时消耗的能量不会超过它所携带的能量；式(3)保证在同一时刻一个传感器节点最多只有一个感知方向处于工作状态；式(4)保证每个集合中每个监测目标的监测要求都能被满足。

定理1 数学问题式(1)—式(4)是NP-hard问题。

证明令式(4)中，Req(Tm)=1,则要求解的问题变成文献[14]中节点调度问题。在文献[14]中已经证明该节点调度问题为NP-hard问题，即作为求解问题的一个特例为NP-hard问题，也即式(1)—式(4)为NP-hard问题。证明完毕。

2 改进和声搜索算法

2.1 原始和声搜索算法简介

受音乐家艺术创作过程的启发,和声搜索算法将决策变量和解分别类比乐器的音调和各种音调的和声，目标函数和种群分别类比适应度(评价)函数和和声记忆库，通过迭代来实现问题的求解[15]。关于原始和声搜索算法的描述，详见文献[15],算法流程如图1所示。

图1 和声搜索算法流程图Fig.2 Theflowchart of harmony search algorithm

原始的和声搜索在解决复杂优化问题或求解多目标进化问题时容易受种群初始化时解质量的影响。当初始种群在局部优化值附近取值时，由于算法本身结构的影响，导致种群多样性下降，进而使得算法早熟收敛，影响算法的优化效率。针对这些问题，本文从新解产生策略和新解接受策略两个角度进行改进。

2.2 改进的和声搜索算法思想

(1) 新解产生策略的改进。将其他智能算法中优秀的操作因子与和声搜索算法结合，可增强和声搜索的优化能力。受微分进化算法[16]思想的启发，将微分进化算法中的微分变异操作替代新解产生后的PAR扰动过程，即替换图1中的“以概率PAR进行扰动”。具体操作：在HM中随机选择3个不同的个体，利用DE/rand/1/bin微分变异策略，即

xnew=xi+Fn×(xr1-xr2)

(5)

式(5)中，xi，xr1和xr2为HM中3个不同的个体，Fn为第n次迭代时的缩放因子。采用混沌序列中Logistic方程产生Fn，防止算法的早熟收敛，即采用式(6)：

Fn+1=4×Fn×(1-Fn)

(6)

初始时，F1为[0,1]之间的随机数。

(2) 新解接受策略的改进。原始和声搜索算法中，当种群初始化生成解的质量不高时，种群易陷入局部最优导致算法的优化能力下降。针对这一问题，将模拟退火算法与和声搜索算法结合增强其局部搜索能力。即当新解优于种群中的最差解时，改进算法的步骤同原始和声搜索算法相同，直接用新解替代最差解；当新解差于种群的最差解时，将以一定概率接受该新解，该概率由模拟退火算法中温度变量决定。该温度变量在算法初期取值较大以利于逃脱局部极值；随着算法的进行，温度变量的值逐渐减小，以利于发挥优秀和声的引导作用，快速收敛。以求目标函数的最小值为例，接受新解的概率公式为

其中：p(T(n))为迭代次数为n，温度为T(n)下的接收概率；fit(new)为新解的适应度值，worst_fit(n)为原种群中最差解的适应度值；Rand为区间(0,1)之间的随机数；T(n)的计算公式为T(n)=α×T(n-1)，α为一个常数。

2.3 异构有向网络寿命最大化问题的求解

利用和声搜索算法解决异构节点寿命优化问题时，要解决优化目标的选择、适应度函数的设计、解的表示3个关键问题。

要优化的目标有两个：符合覆盖要求的节点集合和节点的剩余能量，即

其中：K为满足覆盖要求的集合数；f1取值范围为[0,1];f2为剩余能量的函数；tanh为双曲正切函数；β为比例系数，在本文中设为1；f2值域为[0,1]。

(2) 适应度设计。对于本文要优化的两个目标，采用随机加权[17]的方式转化成单目标优化问题。即对应的权值γ1和γ2为

其中：randi表示区间(0,1)之间的随机数。解向量的适应度表达式为

Fit(X)=γ1×f1+γ2×f2

(3) 问题编码表示。种群中的每个个体代表求解问题的一个候选解，本文采用整型编码，编码示意图如图2所示：

图2 染色体编码示意图Fig.2 The demo of chromosome coding

其中：染色体的每个位置pi,b表示第b个集合里有向传感器节点si的状态，即

其中：|Di|表示节点si感知方向的个数。

3 贪婪算法

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

(Ⅰ) 初始化算法参数，包括目标覆盖要求、每一个节点si的能量Ei,从每一个节点si的每一个感知方向Di,j得到每个感知方向覆盖目标的数量Ni,j。

(Ⅱ) 对于传感器节点的每个感知方向，计算Ni,j×Ei的值，并按照值的大小进行排序。

(Ⅲ) 当存在不满足覆盖要求的监测目标时，选择Ni,j×Ei值最大的感知方向和节点，将传感器节点的序号和感知方向序号放入集合R，即R=R∪{{(i，j)}}，同时将该节点从可用节点中去除，更新每个监测目标的覆盖要求及剩下的所有可用节点的Ni,j×Ei的值，并按照值的大小进行排序。

(Ⅳ) 继续执行(Ⅲ)，否则当所有监测目标都符合覆盖要求时则执行(Ⅴ)。

(Ⅴ) 得到一个满足要求的结果R，输出该结果，并初始化R，执行(Ⅵ)。

(Ⅵ) 更新节点的当前能量Ei，若有节点的能量为0，则将该节点从可用节点中删除。更新所有可用节点的Ni,j，当所有的节点能量为0或没有可用节点可以覆盖未达覆盖要求的目标时，程序结束；否则，继续执行(Ⅱ)。

4 仿真分析

4.1 仿真参数设置

表1 节点参数表Table 1 Node parameter table

4.2 仿真结果及分析

(1) 节点密度对算法性能影响。设置不同的部署节点数量对3种算法性能进行比较，结果如图3所示。从图中可以看出，一方面随着部署节点数量的增加，EHS算法、原始HS算法和贪婪算法求得的满足条件的集合数量也随之增加，究其原因，节点数量增加后能参与目标覆盖的感知方向随之增加，满足覆盖要求的感知方向集合也就相应的增加。另一方面，在部署节点数一定的条件下，改进EHS算法优于原始HS算法和贪婪算法，比如在节点数量为90时，与原始HS算法和贪婪算法求得的结果相比，EHS算法分别提高了45.4%和65.5%，证明了EHS算法改进方案的有效性。

图3 不同节点密度下算法性能比较Fig.3 Comparison of algorithm performances under different node densities

(2) 适应度比较。将监测目标数W设为6，节点数N为45，各个类型节点数量都相同，其他参数如4.1节设置，比较EHS和原始和声搜索算法HS的平均适应度。每个算法运行30次，并取平均值作为算法的结果。图4为适应度的比较结果。从图中可以看出，随着迭代次数的增加，平均适应度的值在增大，且趋于收敛；同时，改进算法EHS的平均适应度优于原始和声搜索算法，证明了改进算法的有效性。

图4 算法平均适应度比较

(3) 异构节点构成比例对网络寿命影响。为了评估不同比例节点构成对求解的集合数量的影响，分别设置A和B两种情形，每种情形下节点的构成比例详见表2所示，得到的算法结果如图5所示。其中，横坐标为部署节点数量，纵坐标为求解的满足目标覆盖的集合数量。从图中可以看出，随着部署节点数的增多，集合数也在增多；在部署节点数相同和构成比例不变的情况下，改进算法EHS优于HS和贪婪算法。比如在节点总数为90，情形B时，较之原始HS和贪婪算法，EHS求解得到的结果分别提高21.9%和42.9%，究其原因，贪婪算法本质上是一个局部最优算法，而本文中EHS算法通过借鉴其他算法优秀处理机制使其优化能力较之原始算法大为增强。

表2 节点构成比例表Table 2 Node composition ratio table

图5 不同比例下算法性能比较Fig.5 Comparison of Algorithm Performances under Different Proportions

(4) 监测目标数对算法性能的影响。比较不同目标数对网络的寿命的影响。其中，监测目标的重要性随机生成，参与监测的传感器节点数量为60，算法的其他参数如4.1节所示。图6为算法的运行结果。从图6可以看出，随着监测目标的增加，符合要求的集合数量在减少，究其原因，目标数越多，满足目标覆盖要求所需的节点也随之增加，导致节点消耗能量增加，因此符合要求的集合数减少；在监测目标一定的情况下，EHS算法求解的集合数优于贪婪算法和原始HS算法。

图6 监测目标数对算法性能影响

5 结 论

基于集合覆盖的思想，提出了一种利用改进和声搜索算法求解的节点调度策略，解决在异构有向传感器网络中面向不同目标有不同监测要求情形下的网络寿命最大化问题。下一步研究工作在于将研究对象从二维平面扩展到三维空间，研究三维空间内有向传感器网络的寿命最大化算法。