基于烟花算法的多传感器优化模型部署

0 引 言

20世纪以来,传感器技术和通信技术在各个领域迅速发展,在现代战场上,无论是在战役还是战略层面信息权都起着决定性的作用[1],而多传感器组网探测是获取情报和取得战场优势的基础。现今现代战争胜负的主导因素已经变成了信息获取,信息体系支撑通过完成信息联动、行动协同、武器控制、精准保障以及夺取其他制权来实现局部甚至于全方位的战场优势。即在信息体系的支撑下,体系结构优势才能得到保障,形成综合对抗优势。这些都需要传感器组网构成网络化探测跟踪系统,为体系提供实时的战场态势。为了使多传感器网络化探测跟踪系统发挥尽可能多的效能,提高对战场目标的检测概率,发挥网络化整体优势,就必须对网络中有限的资源合理利用,优化多传感器模型部署[2-3],以满足体系对现代化战场探测跟踪需求。但受到传感器探测跟踪任务、检测效率、传感器属性以及资源浪费等条件的约束,多传感器部署成为复杂的多约束非线性的问题[4-6]。

多传感器部署使传感器网络对物理世界有更好的感知范围和质量,多传感器优化模型部署是为了在紧急的情况部署的传感器网络能够更好更快地感知物理世界。在反导的作战领域,多传感器优化模型部署就是为了对已知范围的物理世界进行探测时能够迅速部署并且对探测范围精确感知。对传感器部署模型优化并且进行部署,是传感器在有限资源的条件下解决最佳分布、合理布局的手段,以满足现代化战场作战需求。

文献[4-7]提出了多种传感器部署方案,如基于遗传算法的部署方案、大面积开放式部署方案等。这些部署方案都难以满足在战场环境中迅速求解、精确定位的要求。针对这些问题,由反导战场需求出发,从传感器探测的总覆盖率、重点区域二重覆盖率以及资源利用率等方面建立多传感器优化模型部署,运用烟花算法对所建立的模型实现部署模型最优解的快速求解,并通过仿真验证方法的有效性,为解决多传感器快速优化部署问题提供了一条有效的技术路径。

1 多传感器优化模型部署策略

传感器部署策略被看作为多约束条件下的参数优化问题。传感器的性能指标和多传感器的部署将直接影响多传感器协同探测跟踪系统的探测能力。为了使多传感器优化模型部署时能够适应环境的快速变化,得到最佳和最快速度的解决方案,需要首先将部署问题进行细化,具体描述各项性能指标参数,然后把各项性能指标参数进行量化计算,最后生成的多传感器部署模型必须满足相应的性能参数。

1.1 多传感器优化模型部署性能指标参数

对于瞬息万变的战场态势,多传感器优化模型部署的性能指标参数必须包括:总区域覆盖率、重点区域的共视参数、传感器资源利用率。

1.1.1 总区域覆盖率

覆盖率被用来衡量多传感器网络服务质量,它的定义为区域内所有传感器节点覆盖面积的并集SC与整个目标作战区域面积Z的比值,可以表示为

(1)

式中,Sn为第n个传感器的覆盖面积;N为总节点数。

假定在划定的作战区域内,期望的多传感器协同探测的总覆盖率由地面坐标系来表示,为了使作战能够更加简明,优化作战操作示意图。定义地面坐标系原点为作战区域西南角,即定义重点作战区域中心点南偏西45°方向距离的点为坐标轴原点,正北方向为X轴,正东方向为Y轴。

其坐标定义为(X,Y),范围为

(2)

采用网格点统计法计算战场的总区域覆盖百分比记为P。用X轴最初起始位Xmin、X轴最远作战位Xmax、Y轴最初起始位Ymin、Y轴最远作战位Ymax,将想定战场定义为一个矩形,如第4.1节仿真中的定义区域,将该矩阵划分为小网格矩阵,每一个小网格大小一致,当传感器的探测范围在占据小网格一半以上区域时定义这个小网格被传感器完全覆盖探测,否则定义为完全没有被覆盖探测。则覆盖百分比可以表示为

P=m/M

(3)

式中,m代表占据的网格数;M为总的网格数。

1.1.2 重点区域的共视参数

重点区域的共视参数即为重点区域被共视的覆盖率,即被多个传感器同时覆盖的范围与重点区域的比值。

重点区域是指在战场中需要防守,从而为体系提供重点信息支撑的区域,一般采用二重覆盖探测区域对重点区域进行监控。

定义重点区域共视参数为

(4)

式中,Simportant为重点区域面积；Simportant2为重点区域内同时被大于等于两个传感器探测的区域。

通常来讲,当传感器的共视重数超过2层时,传感器的联合探测概率不会比2层重数的传感器有明显的增强,即在本文中重点目标区域共视的层数达到两层即可,当超过两层以两层的探测重复率计算时,只需要计算传感器的资源浪费程度,通过传感器资源利用率来计算,不进行额外的计算。

1.1.3 传感器资源利用率

传感器资源是有限的,为了最大程度利用优势资源,需要将传感器探测范围规范在体系需要的范围。

定义传感器资源利用率C为

(5)

1.2 多传感器优化模型部署的建立

在上述讨论中,定义了部署多传感器平台满足多传感器组网系统在战场探测的需求,确保重要区域的目标都能够被监控和跟踪,达到作战体系的军事信息获取要求的3个探测性能指标,需要使用合理简洁的优化算法,将这3个性能指标作为优化参数应用在多传感器优化模型部署中,将多约束条件问题转化为多目标优化问题,以方便传感器部署时适应瞬息万变的反导战场。

通过将3个不同性能指标进行优化加权求和,即可建立多传感器部署模型。在现代化战场中,首先考虑作战任务的完成度,即对要地的保护是作战的重心,尤其是在复杂环境下作战时;其次考虑的才是整个战场的覆盖式探测。如果在传感器足够的情况下,战场作战要求装备稳定、不出差错,必然会牺牲传感器的使用效率。因此,3个参数的重要排序依次是:重点区域共视参数,总区域覆盖率,传感器利用率。为此3项指标目标的重要性依次定义为ω1、ω2、ω3(ω1+ω2+ω3=1),权重的取值由传感器的功能、参数以及战场任务所决定。目标函数为

f=ω1×P+ω2×Q+ω3×C

(6)

式中,ω1×P表示传感器总利用率在目标函数中最终影响结果;ω2×Q表示重点区域共视参数在目标函数中最终影响结果;ω3×C表示传感器资源利用率在目标函数中最终影响结果。

2 基于多传感器优化部署烟花算法

烟花算法[7-13]是一种具有爆炸搜索机制的新型全局优化求解的群智能算法,它在求解复杂的多目标优化问题中表现出了非常优良的效率和性能。利用烟花算法解决问题的原理是通过爆炸算子[14-16]、变异算子、映射规则和选择策略[17-18],使所求解的非线性多约束问题达到区域求解的目的,得到最优值。目前,烟花算法已经广泛应用在信号处理、自适应控制、优化组合和机器学习等领域[19-21]。

2.1 烟花种群初始化

种群初始化将烟花算法与多传感器优化部署相结合,需要将传感器的部署位置进行编码。

编码方法采用如图1所示的X轴和Y轴串联编组。

图1 多传感器串联编码
Fig.1 Multi-sensor series coding

图1中,N1,N2…Nn表示第n个传感器的代码段;α1,α2,…,αn表示第n个传感器在X轴的代码段;η1,η2,…,ηn表示第n个传感器在Y轴的代码段。

假设传感器的探测精度为0.1 km,即可确定在第1节中小网格的边长为0.1 km,如若探测范围为1 000 km×1 000 km,采用十进制编码,根据编码规则,只需要考虑0到999.9即可,则定义传感器位置编码在X轴编码段和在Y轴编码段都为4位。即每一个传感器个体位置代码段是由X轴和Y轴代码段组成的8位代码。采用以下方式定义初始化种群:

(1) 设置初始种群数量100个;

(2) 在战场区域内随机生成1个传感器位置的X轴和Y轴代码段,将其组对生成8位代码,重复100次生成初始化种群;

(3) 为提高个别优势个体的竞争力,可以根据经验把最有可能的点进行人为编码。

2.2 爆炸算子

在烟花爆炸中,好的烟花产生的火花存在于爆炸中心,坏的则产生少量火花,并且这些火花零星散落在空间中。这样从烟花算法搜索的角度[12,22-24]来看,一个好的烟花意味着烟花要定位在距离最优点很近的位置,这就适合一个好的点附近有更多火花来搜索烟花的局部区域。相反,一个坏的烟花意味着距离最优位置可能比较远,这时就需要扩大搜索距离,两种情况如图2所示。

图2 烟花爆炸图
Fig.2 Fireworks explosion

对于初始烟花Li,定义每一个烟花爆炸半径幅度Ai和爆炸产生的火花数目Bi(i表示不同的烟花)的计算公式分别为

(7)

(8)

式中,Vmin=min(f(Li)), i=1,2,…,H为当前烟花父系算子中适应度最小值;Vmax=max(f(Li))(i=1,2,…,H)为当前烟花父系算子中最大适应度目标函数值;是调节烟花爆炸半径的常量;是调节烟花爆炸产生火花数目的常量;ε是一个避免造成除零操作的极小值常量;H表示总的烟花个数。

为了避免烟花爆炸产生过多的烟花,影响计算速度,对每个烟花爆炸产生的算子数量进行限制,文献[25-26]对每个烟花爆炸采用限制公式

(9)

式中,为第i个烟花产生的火花数量;round()为四舍五入后取整的函数;a和b为常数。

2.3 变异算子

为了保证烟花种群的多样性,不受到初始种群影响以及避免迭代后出现局域峰值的现象,加入高爆算子作为变异算子,使烟花算法在全局搜索时更加全面。本文采用高斯变异:随机选择初始种群中的烟花Li,对其某一个或多个维度进行高斯变异操作。其高斯变异操作为

(10)

式中,e～N(1,1)服从均值为1、方差为1的高斯分布。

2.4 映射规则

由于烟花算法通过爆炸和变异操作产生的火花具有随机性,因此求解域边界的烟花产生的火花有概率超出求解域。这时便通过映射的办法将超出求解域的火花转换到新的位置,通常超出求解域的值不大,并且一般都和求解域边界相对称,即为可行域在维度k上的上边界和下边界。超出边界的火花可以在维度k上被映射到一个新的位置上,这个位置一般情况靠近原点。具体的映射规则可表示为

(11)

式中,表示超出边界的火花个体在第k维的位置；为可行域SC第k维的上边界；为可行域SC第k维的下边界；%表示模的运算。

2.5 选择策略

在烟花算法中,要让种群中优秀的信息的个体或者特征能够在种群中一直传递下去,需要从爆照、变异操作产生的火花集合中选出部分优质个体成为下一代烟花母体,同时要保证所选择的个体具有全面性和优越性,以保证下一代火花产生的质量。

定义候选火花集合为Ω,每一代种群的数量为β。将适应度最大的火花个体保送至下一代种群中,保证种群质量;而对剩下的β-1个个体,为了保证样本多样性采用轮盘赌的方法进行选择。

(12)

式中,R(Li)表示个体Li与其他所有个体的两两距离的和;d(Li,Lj)表示两个体Li和Lj的距离。

候选火花Li被选择概率p(Li)可表示为

(13)

由式(13)可知,在火花集合中,同一位置附近的火花个体被同时选择的概率很低,这是因为样本多样性的需求,火花被选中的概率随着周围火花个体增多而减少。

3 多传感器优化模型部署仿真流程

多传感器战场部署求解复杂,在运用烟花算法优化求解时需要先设计算法流程,使用已经推导的适应度函数和定义的初始化种群流程,烟花算法的具体步骤如下:

步骤 1 初始化种群,设置起始参数,生成i个初始种群,并根据式(6)计算适应度。

步骤 2 将i个烟花分别进行爆炸操作,依照式(7)和式(8)计算每个烟花的爆炸半径和产生的火花个数。

步骤 3 按照式(10)计算爆炸半径和火花个数生成爆炸火花和高斯变异火花。

步骤 4 在新构成的候选烟花种群Ω中,找出当前最优值,依照式(6)计算适应度。

步骤 5 设置终止条件,并根据终止条件判断是否停止迭代,若停止,输出优化值,否则继续步骤6。

步骤 6 按照式(12)和式(13)轮盘赌的选择策略找出i个新烟花,并进入步骤2。

烟花算法操作流程如图3所示。

图3 烟花算法流程图
Fig.3 Fireworks algorithm flow

4 仿真实验

4.1 仿真条件

假设一般作战区域为1 000 km×1 000 km的方形作战区域,传感器探测的范围是250 km;作战的重点区域是以(400,400)为中心,半径范围是225 km的圆形区域。多传感器部署的适应度函数的权值系数假定为:ω1=0.3,ω2=0.5,ω3=0.2,设置终止条件为烟花算法迭代到第100代时,计算终止。通过Matlab编程计算后得到经过优化的战场传感器部署情况如表1和图4所示。

表1 多传感器部署情况
Table 1 Multi-sensor deployment situation

图4 多传感器部署图
Fig.4 Multi-sensor deployment map

4.2 仿真结果及分析

多传感器优化部署结果如图4所示,其迭代次数如图5所示。

图5 变权重烟花算法覆盖率对比
Fig.5 Coverage comparison of variable weight fireworks algorithm

图4中带加粗的圆为重点区域,传感器对战场区域的总探测覆盖率达到了92%,重点区域的共视参数达到了99%,可见,烟花算法能够很好地解决传感器部署的问题。

将多传感器部署的适应度函数的权值系数改变为:ω1=0.5,ω2=0.3,ω3=0.2,其他条件不改变,与第一次烟花算法迭代次数对比结果如图5所示。

由图5可知,在不同的权重条件下,多传感器总的重点区域覆盖率和总区域覆盖率的收敛速度不一样,当在烟花算法中对多传感器的重点区域覆盖率赋予较大权重时,重点覆盖率的收敛更快,并能迅速找到重点区域覆盖率的最大值,这对于总区域覆盖率也是一样的。这样,在战场区域内,就可以对最迫切的需求赋予更大的权重,以得到对多传感器某一方面(如重点区域保护、监视范围等)更快速的求解。

4.3 算法可靠性验证

为了验证算法的有效性和正确性,将本文算法与遗传算法、蚁群算法进行对比实验。由于烟花算法在算法结构上与遗传算法和蚁群算法有很多相似之处,所以使得对比实验更具有针对性。首先,这3种算法都需要初始化种群;其次,都需要对个体进行适应度计算,再根据适应度值对候选者种群进行选择;最后,3种算法都要通过计算的适应度进行迭代操作,并且都需要设置终止条件。

对3种算法各进行10次实验,迭代次数为100,种群规模为100,使用同一组数据输入,其余参数与上一实验相同,3种算法出的最优适应度值如图6所示。

图6 3种算法最优适应度对比
Fig.6 Comparison of optimal fitness of 3 algorithms

由图6可知,采用本文算法求得最优适应度值的次数占总实验次数的90%,远大于蚁群算法和遗传算法。这是因为烟花算法在每一次迭代过程中都能产生多个个体,每一代的样本都具有多样性,本文算法对烟花算法算子附近区域搜索更为彻底。因此,在相同实验条件下,本文算法有更好的寻优能力,能够更容易精准地寻找到最优部署位置。

4.4 算法执行效率验证

对于烟花算法的实时性分析,按照通常的两项来分析。一方面是从数学理论上证明其正确性,主要包括对烟花算法的相关推理模式和形式化证明等。在证明理论正确的基础上,另一方面就是分析算法的复杂度。算法的复杂度反映了程序执行时间的长短,能很好地反映出算法的优劣与否。本文算法的理论在第2节已经给出,先对复杂度进行分析和验证。

4.4.1 算法复杂度分析

烟花算法的执行时间取决于下列因素:

(1) 烟花算法采用的策略、方法;

(2) 烟花算子编译产生的代码质量;

(3) 初始种群输入规模;

(4) 计算机执行指令的速度。

在同时用烟花算法和遗传算法研究多传感器优化部署问题时,选取两种算法的基本操作的重复执行的次数作为算法的时间量度。

由图3的算法流程可知,烟花算法的时间复杂度为

T烟花=O(ilog2i)

(14)

而文献[5]中遗传算法时间复杂度为

T遗传=O(i2)

(15)

式中,O(·)表示算法渐进时间复杂度。

由式(14)和式(15)以及两算法初始种群都为大于零的常数可知,烟花算法的实时性好于遗传算法。

4.4.2 算法执行时间验证

为了验证本文算法的执行效率,在其余参数都相同的情况下,分别设置种群规模为10、20、30、40、50、60、70、80、90、100,迭代次数为20的对比实验。烟花算法、蚁群算法和遗传算法在相同初始条件下执行时间的对比情况如图7所示。

图7 3种算法执行时间
Fig.7 Execution time of 3 algorithms

由图7可见,烟花算法与其他两种算法在除了17时之外的种群规模数量条件下,都有巨大差异。尤其是烟花算法在大种群计算时,相比蚁群算法和遗传算法,执行时间在种群规模增大时相对增加量小,并且在种群规模为100时,蚁群算法和遗传算法比烟花算法的执行时间增加了超过一倍。这是因为本文烟花算法采用选择机制、爆炸算子、位移变异以及高斯变异来使种群始终保持多样性,并且通过映射规则使烟花种群存在局限性,将烟花位置限制在求解域的范围内,满足战场的范围限制。因此,烟花算法在执行时间较短和面对大规模种群计算时具有良好的稳定性,适合战场条件下计算。

5 结 语

在现代信息战场中,如何快速有效部署传感器成为信息战胜利的重要因素,也是传感器网络技术的重要研究方向。从传感器探测的覆盖率、重点区域覆盖层数以及资源利用率等方面建立了多传感器优化模型并进行部署仿真验证,通过烟花算法与优化模型相结合实验仿真验证证明了优化模型适合战场求解,为快速解决反导战场多传感器部署问题提供了技术路径。仿真实验表明,烟花算法在全局搜索条件下具有更快的收敛速度,更有利于求解战场多传感器的最优部署位置;在多传感器部署模型中赋予重点区域共视参数更高的权重,对取得更高的战场重点区域的二重覆盖率有利。未来针对引入烟花算法后多传感器网络部署新问题,还需要对战场环境进行充分分析。另外,雷达遮蔽角的问题及动态战场部署问题还需进一步研究。