面向多目标探测的无线传感器网络资源调度方法

李琦, 韦道知, 王希,3, 谢家豪

(1. 空军工程大学防空反导学院, 710043, 西安; 2. 中国人民解放军第93605部队, 102100, 北京;3. 西安卫星测控中心, 710043, 西安)

无线传感器网络(wireless sensor networks,WSNs)是通过无线通信建立网络连接,将大量目标感知传感器设备分布式地部署在目标监测区域内形成的网络。因其具有良好的动态性、可扩展性和灵活性,常被应用在战场侦察、灾后搜救、跟踪定位等目标监测任务中。随着高技术信息化的发展,其在交通控制、智能家居、智慧农业等领域也发挥着重要作用[1-2]。然而,在目标监测任务中,如果WSNs网络对各个传感器设备以及整个系统管理不当,就会出现目标分配冗杂、能源消耗多、资源浪费等问题。面对日益复杂的目标属性和探测环境,如何利用无线传感器网络中的有限资源,尽可能高效、精确、快速地进行目标探测资源优化调度,已成为重要的研究方向[3-4]。

目标探测过程中,无线传感器网络资源调度问题的本质是在综合考虑传感器设备自身性能、相互关联、预期目的等多约束条件下,基于某种原则建立模型并求解最优调度方案的多目标优化问题[5]。当前,国内外学者围绕此问题开展了广泛研究。文献 [6-7]提出了基于信息论的算法,并采用信息熵来评价调度的性能。文献 [8]提出了线性规划方法,将调度建模成由跟踪精度和匹配传感器资源矩阵组成的优化问题。然而,在不考虑目标跟踪精度的情况下,该方法的检测性能较差。为提高传感器资源的跟踪精度,文献 [9]提出了一种基于后验克拉美-罗下界和拦截概率因子的传感器网络调度方法,将传感器资源的拦截概率控制在阈值域内,但由于模型中的目标函数是非凸的,直接采用梯度下降法不可行。文献 [10]首先提出了综合考虑目标损失风险和传感器资源辐射风险的风险评估模型,然后设计了与该模型相关的传感器网络调度方案,但由于目标损失风险与传感器资源辐射风险的比值是固定的,该方法在目标损失风险与传感器资源辐射风险比值变化时性能下降明显。文献 [11]采用随机分配传感器对目标进行检测和跟踪的方法,解决了低信噪比下的多目标跟踪问题。文献 [12]把动态联盟理论引入到无线传感器网络管理当中,根据不同时刻的环境态势组建相应时刻的最优联盟,由该联盟完成对目标的探测。针对WSNs资源优化调度问题,虽然上述文献均提出了一些解决方案,但在动态复杂环境下,由于对资源优化调度模型的构建要素考虑不全面,过多注重某一单方面性能约束指标的影响,缺少任务效能整体收益考虑,且同时对约束指标的定量、权重考虑不清,因而导致调度模型缺乏说服力。此外,在实际应用中,由于算法本身的随机特征,存在控制参数设置过多、计算复杂、求解效率不高、容易陷入局部最优等缺陷。

针对以上问题,本文提出了一种基于任务效能收益最优的WSNs网络资源优化调度策略,建立了以WSNs网络效能收益最大为目标的资源优化调度模型,并采用改进后的象群优化算法对模型进行求解,最后通过仿真实验验证了模型和算法的有效性。

1 传感器网络资源调度模型的建立

本文将无线传感器探测网络资源优化调度问题视为具有多约束条件的动态优化过程,从单个传感器设备的自身感知性能、工作效率、负载损耗、任务优先级以及多个传感器资源相互间的关联出发,动态分析影响整个WSNs网络效能收益的复杂约束指标,利用模糊层次分析法对这些评价指标进行量化分析,以任务效能收益最大化为目标建立调度模型。

1.1 约束条件评价指标分析

(1)

(2)

(3)

(4)

(5)

(6)协同覆盖范围约束。增大协同覆盖范围,不但能扩大目标监测区域,降低传感器资源之间的交接次数,而且能有效提升目标监测区域重合处的探测精度,增强可信度。协同覆盖范围与探测效果成正比,是WSNs资源优化调度的重要约束条件。传感器之间间距越大且相差越小,协同探测的效果越好,定义协同探测范围q的表达式如下

(6)

1.2 采用模糊层次分析法确定的约束指标权重

由于WSNs网络协同探测多目标过程中,资源优化调度约束评价指标难以定量且属于不同量纲范畴,不能通过直接加权的方式得到目标函数,因此,本文采用模糊层次分析法[15-18]对各指标进行量化计算。实现的过程主要包括:分析影响目标完成的因素,对影响因素上下层关系进行划分并建立评估模型,对同层影响因素进行量化评价并利用判断矩阵求解。建立的指标评估模型如图1所示。

图1 探测资源优化调度约束指标等级评估模型

根据图1所示,将WSNs资源优化调度约束评价指标分为A、B、C、D 4层,运用9标度法对各指标间的权重作出判断举证[19],如表1所示。

表1 9标度法参数

(1)目标要素B层对目标A层判断矩阵为

(7)

(2)准则C层对目标要素B层判断矩阵为

(8)

(3)方案D层对准则C层判断矩阵为

(9)

C2=[1]

(10)

C3=[1]

(11)

C4=[1]

(12)

C5=[1]

(13)

(4)约束指标权重计算。定义一致性指标I,如下所示

(14)

式中:λmax为判断矩阵的最大特征根;N为矩阵的阶数。当I=0时,判断矩阵一致;I的值越大,判断矩阵的一致性越差。

定义一致性比率R,如下所示

(15)

式中:S为平均随机一致性指标,通过查找表2可确定其对应的数值[20]。当R<0.1时,认为判断矩阵的一致性可以接受,否则需要修正。

表2 平均随机一致性指标

经计算,各判断矩阵的权重、λmax及R分别为

(16)

(17)

WB2=[1]T;λmaxB2=1;R=0

(18)

(19)

WC2=[1]T;λmaxC2=1;R=0

(20)

WC3=[1]T;λmaxC3=1;R=0

(21)

WC4=[1]T;λmaxC4=1;R=0

(22)

WC5=[1]T;λmaxC4=1;R=0

(23)

式中:W为对应矩阵的正规化特征向量。可以看出,所有的R值均小于0.1,符合一致性检验,因此,判断矩阵的特征向量可作为资源优化调度的权向量。方案元素层约束指标权重如表3所示。

表3 方案元素层约束指标权重

1.3 基于最大效能收益的WSNs资源调度方案

(24)

(25)

(26)

(27)

(28)

2 传感器网络资源调度算法设计

在构建WSNs资源优化调度模型后,需要采用优化算法对模型进行求解,才能得到最终的资源优化调度方案。

近年来,一种新的群智能算法被引入,即受大象放牧行为启发的大象放牧优化算法。该算法由Wang等于2015年提出[21],因具有良好的收敛特性和寻找最优解的潜力,能够探索比许多其他自然启发算法更好的最优解[22-23]。基于象群算法全局优化能力强、控制参数少、实现策略简单等优点,本文在其基础上进行改进,为WSNs资源调度提供稳定可靠的求解算法。当采用象群算法求解资源优化调度方案时,一个大象位置即一种资源调度方案,由于该调度方案为0-1矩阵,因此在对大象进行搜索时,产生新位置的方式可看作是以该调度矩阵为基础生成新矩阵,且新矩阵与原有矩阵之间仅有少数元素不同,其适应度为资源优化调度目标函数相关的函数。

2.1 基本象群算法(EHO)

基本象群优化算法(elephant herding optimization algorithm,EHO)主要包括部落更新操作和部落分离操作2个过程。

(1)部落更新操作。来自不同部落的大象在其女族长的领导下一起生活,其他大象的位置都根据女族长和自身的位置进行更新,位置更新公式如下所示

xnew,ci,j,d=xci,j,d+α(xbest,ci,d-xci,j,d)γ

(29)

式中:xnew,ci,j,d和xci,j,d分别为大象j在部落(ci)中第d个维度的新位置和旧位置,其中1≤d≤D,D为搜索空间的总维数;xbest,ci,d为女族长的位置;α代表部落中女族长对大象个体的影响因子,取值范围为α∈[0,1];γ用来增加每一代的种群多样性,γ∈[0,1]。

女族长的位置根据部落中心的位置进行更新,如下所示

xbest,ci,d=βxcenter,ci,d

(30)

式中:β为0和1之间的随机数,控制着部落中心对女族长位置的影响。其中,部落中心位置定义为

(31)

式中:nci为部落中大象的数量。

(2)部落分离操作。当部落中适应度最差的个体(公象αi)成熟时,它将远离部落,此时需在空间中进行随机搜索以增加全局搜索性能,其位置更新表达式为

xworst,ci,d=xmin+(xmax-xmin+1)p

(32)

式中:xmax和xmin分别为种群中大象搜索位置的上、下限;p为0到1之间的随机数。

2.2 改进象群算法(ASCEHO)

象群算法同其他智能算法一样,也存在一定的局限性。主要包括:①种群多样性差。基本EHO算法在初始化种群时采用的是随机方式,但这种方式并没有基于先验知识,因而导致种群出现多样性差的问题。而种群多样性差必然会影响后续的全局搜索寻优过程,也会对最优解的质量有一定影响。②容易陷入局部最优。基本EHO算法在迭代过程中容易早熟,导致经常出现在局部最优解附近搜索求解的情况;与此同时,现有的改进方法并不能有效避免全局和局部寻优的盲目性。因此,为改善基本象群算法的寻优能力,本文提出了3点改进措施。

(1)混沌映射策略。初始种群在解空间中分布越均匀,算法搜索到最优值的概率就越大。混沌映射策略因其遍历性、非重复性等特点被广泛用于群智能优化算法的初始种群生成中[24]。Tent混沌映射的公式表达如下

(33)

式中:Zk为随机产生的初始值;Zk+1为混沌映射后产生的初始值。

将得到的混沌序列映射到搜索空间中,得到

xci,j,d=L+(U-L)Zci,j,d

(34)

式中:xci,j,d为部落中第j只大象在d维的位置;U、L分别为搜索空间的上、下界;Zci,j,d为式(33)产生的混沌序列。

图2(a)和2(b)分别给出了初始种群规模为30时,随机生成和基于Tent混沌映射2种方法得到的种群分布。由图可见,采用基于Tent映射初始化方法得到的种群在搜索空间范围内的分布更均匀。

(a)随机初始化种群分布

(2)正余弦算法。正余弦算法(sine cosine algorithm,SCA)是Mirjalili于2016年提出的、利用正余弦函数的数学模型使解震荡性地趋于最优解的一种方法。该算法根据正余弦函数与单位圆的关系进行迭代,通过正余弦函数遍历单位圆模拟算法寻优过程,其遍历性特点可以防止算法陷入局部最优[25]。本文在搜索阶段融入正余弦算法更新搜索位置,在该阶段,大象以正余弦方式移动,融入SCA算法的全局搜索位置更新模型如下

xnew,ci,j,d=

(35)

式中:γ2∈(0,2π)、γ3∈(0,2)、γ4∈(0,1)为均匀分布的随机数;xbest,ci,j,d为当前最优解个体的位置;γ1为控制参数,可写为

(36)

式中:a为常数;t为当前迭代次数;Tmax为最大迭代次数。

(3)自适应权重因子。在算法的开发阶段通过引入自适应权重因子,以提高局部寻优能力,并将自适应权重因子应用于改进象群算法开发阶段的全部方程中。自适应权重因子的计算公式如下所示

(37)

因此,开发阶段最差个体位置更新如下所示

(38)

式中:xworst,ci,d为部落中适应度最差个体的位置。

2.3 算法流程图

基于改进后象群优化算法的多传感器资源调度求解流程如图3所示。

图3 改进象群优化算法流程图

3 仿真实验结果与分析

3.1 仿真条件

为验证本文所提算法的有效性,分别从算法性能优势以及调度方案求解两个方面进行仿真对比。仿真参数设置如下:侦察卫星8颗,X波段地基雷达1个,L波段球载雷达1个,空基预警机1个。仿真环境为64位Windows 11操作系统,采用的软件为Matlab R2019a。ASCEHO算法参数设置为:种群容量N=50,最大迭代次数Tmax=100,上界U=5,下界L=-5,无线传感器网络部署及感知能力如表4 所示。

表4 无线传感器网络部署及感知能力

3.2 算法改进前后优化结果对比

图4给出了在搜索阶段采用不同算法更新搜索位置的仿真结果。从图中可以看出,采用正余弦算法更新搜索阶段位置的EHO算法的适应度值高于基本EHO算法,同时收敛速度也更快。图5给出了搜索阶段采用不同更新算法得到的迭代次数、运行时间和求解精度对比图,从图中可以看出,ASCEHO算法在迭代次数、运行时间和求解精度3个方面均优于EHO算法,其主要原因是大象以正余弦方式移动寻找食物,在每一次迭代中根据式(35)中γ1、γ2、γ3的值来更新全局搜索的距离和方向,进一步缩小搜索区域,优化了全局搜索阶段的优化速度和求解质量。仿真结果进一步验证了采用正余弦算法更新搜索阶段种群位置的优越性。

图4 不同更新算法在搜索阶段的适应度值对比

图5 不同更新算法在搜索阶段的迭代次数、运行时间和求解精度对比

图6给出了在开发阶段引入自适应权重因子后2种算法的适应度值曲线对比。从图中可以看出,在开发阶段引入自适应权重因子后,ASCEHO算法的适应度值与EHO算法相比有所提高,且经过较少的迭代次数便能达到最优值,因此收敛速度也优于EHO算法。

图7给出了开发阶段2种算法的迭代次数、运行时间和求解精度对比图,从图中可以看出,在开发阶段引入自适应权重因子后,ASCEHO算法的迭代次数、算法运行时间和算法求解精度均优于EHO算法,这是因为将自适应权重因子应用于ASCEHO算法开发阶段的全部方程中,在为种群注入足够多样性的同时,也避免了任何解停滞的可能性。

图7 不同更新算法在开发阶段的迭代次数、运行时间和求解精度对比

为进一步说明本文所提ASCEHO算法的优越性,采用本文算法与基本象群算法(EHO)、长期记忆象群算法(LMEHO)、基于自适应合作觅食与分散觅食策略的象群算法(ADEHO)、鲸鱼算法(WOA)、粒子群算法(PSO)进行求解,对比了目标价函数的适应度值和算法的迭代次数、运行时间以及求解精度。图8给出了采用上述不同算法求解目标函数的适应度值对比曲线。图9给出了不同算法的迭代次数、运行时间和求解精度对比曲线。

图8 不同算法的适应度值对比

图9 不同算法迭代次数、运行时间和求解精度对比

由图8可见,尽管所有的算法最终都能收敛到定值,但收敛速度和最终收敛值存在一定差异。相比于其他算法,ASCEHO算法能更快地得到最优解,即收敛速度最快,且最终收敛值为0.98,表明了ASCEHO算法的优越性。EHO算法收敛速度最慢,且最终收敛值为0.68。这是因为改进后的算法对每个阶段存在的劣势都进行了改进,从而优化了解的质量。

从图9中不同算法的迭代次数、运行时间和求解精度对比结果可见,ASCEHO算法的迭代次数、运行时间和求解精度均优于其他算法,与EHO算法相比,迭代次数减少了41次,求解精度提高了124%,运行时间减少了57%。其主要原因是采用Tent混沌序列对种群进行初始化,初始化效果优于随机初始化结果,这就使得算法在后续搜索和开发阶段能够重点关注搜索空间中的信息区域以选择基本特征,避免了不相关特征。

综上所述,ASCEHO算法通过正余弦算法在搜索阶段对种群的位置进行更新,在开发阶段引入自适应权重因子更新位置方程来不断寻找新的有前景的区域,有助于防止算法陷入局部最优,改进了基本EHO算法的局部搜索。

3.3 算法改进前后优化结果对比分析

(1)传感器网络探测跟踪目标数量对比。为进一步验证本文所提ASCEHO算法在求解优化调度模型中的有效性,将ASCEHO算法与EHO算法、SCAEHO算法、ADEHO算法、LMEHO算法得到的探测跟踪目标数量进行对比分析,结果如图10所示。

图10 不同算法下探测跟踪目标数对比

从图10可以看出,不同算法下探测跟踪目标数量存在差异,总体来看,采用ASCEHO算法时,每个传感器设备探测跟踪的目标数较为均衡,不存在某一个传感器空载过久或者一直过载的情况,每个传感器平均负责探测跟踪2.7个目标,无线传感器网络负载较小,因此能效较高。而采用其他算法时,有的存在某一传感器执行对所有目标的探测跟踪,有的探测跟踪1个目标后停止工作,均会造成目标探测跟踪数量的不均衡,导致目标探测网络的能耗增加,负载较大。

(2)WSNs资源优化调度方案对比。在对探测跟踪目标数量开展分析后,进一步分析了不同算法下目标探测WSNs的资源调度方案,将本文提出的ASCEHO算法与EHO算法、SCAEHO算法、ADEHO算法、LMEHO算法得到的资源优化调度方案进行对比分析,结果如表5所示。

表5 多目标探测过程中WSNs资源优化调度方案

从表5可见,ASCEHO算法在求解优化调度方案时具有明显优势。采用ASCEHO算法生成的方案对目标进行探测跟踪,资源的使用较为均衡,每个目标均有5个传感器进行探测跟踪。而在其他改进EHO算法生成的调度方案中,探测资源的利用率极不均衡,如ADEHO算法中对某一个目标的探测跟踪过程中存在传感器重复利用的情况,造成了资源的浪费,以及LMEHO算法生成的调度方案中存在传感器资源利用率较低的情况。

4 结 论

本文从目标探测过程中的无线传感器资源优化调度问题出发,综合考虑了单传感器资源效能约束和多传感器资源相互关联约束等评价指标,并基于模糊层次分析法对评价指标进行量化,建立了以目标探测的WSNs网络综合效能收益最大为准则的资源优化调度模型,最后基于改进象群算法对模型求解,并通过仿真实验进行验证,得到以下主要结论。

(1)基于传感器资源相互关联约束指标建立调度模型,一定程度上提高了资源优化调度模型的可靠性和说服力,通过合理的调度,能够有效解决无线传感器网络资源利用率低的问题,并提高目标监测系统的探测效果。

(2)所提算法有效改善了算法容易陷入局部最优的问题,提高了计算效率,并使资源优化调度问题能够在有限时间内获得最优解。