临空高超声速飞行器多传感器任务分配算法*

孙 文，王 刚，付 强，王晶晶

（空军工程大学防空反导学院，西安 710051）

0 引言

临空高超声速飞行器（Near Space Hypersonic Vehicle，NSHV）飞行速度快、机动性能强、隐身性能好，兼具空间作战和远程精确打击的能力，在未来攻防对抗中占有绝对性优势，对空天防御体系产生了严峻挑战［1］。从防御角度分析，实现对NSHV的探测跟踪是进行拦截作战的重中之重，而高效、合理的探测跟踪任务分配机制则是作战行动的必要条件。NSHV的作战特性不同于弹道导弹的轨迹可预测，空气动力学目标的低空、慢速，使得现有的多传感器任务分配体系难以对其进行快速高效稳定、动态反馈、全面系统的任务分配。因此，展开对NSHV任务分配的研究是一项前沿重点课题。

目前，针对NSHV多传感器探测跟踪任务分配的研究刚刚起步，大多数作战任务分配研究集中在反导作战任务和无人机作战任务分配上，任务分配方式主要以独立的集中式和分布式为主，对具有快速高效、动态反馈和自适应的特点混合式任务分配研究不足［2-4］。文献［5-8］主要以攻击代价和收益为指标，运用粒子群算法、改进遗传算法、分布式拍卖算法等，解决多无人机协同任务分配问题；文献［9-10］运用多维动态列表规划的思想、自适应遗传算法，解决反导作战任务分配的问题。本文借鉴反导和无人机任务分配的相关研究，搭建了NSHV多传感器混合式任务分配体系，构建了面向NSHV的多传感器任务分配模型，将合同网的协商签约机制引入量子遗传算法中，提出了具有量子旋转角和反馈信息双重定向调整机制的合同量子遗传算法，并通过仿真实验，验证了该算法的可行性和优越性。

1 NSHV多传感器混合式任务分配体系

NSHV的高速、高空、高机动等特性，使得单一的探测平台资源难以完成探测跟踪任务，需要不同载荷、不同频段的多源异类多传感器协同完成，同时也就决定了其任务分配的复杂性、动态性。基于集中式的快速高效和分布式动态反馈的任务分配特点，建立了针对NSHV的多传感器混合式任务分配体系，如图1所示。

图1 NSHV多传感器混合式任务分配体系

图1可知，该体系主要包括任务处理/决策中心、天-临-空-地/海基平台传感器及其任务处理节点，可划分为决策层、中间层和执行层，充分体现了多平台交互协同、分层式指令下达、多属性效果反馈等特点，有利于多传感器探测跟踪任务的高效、快速分配。其具体特征如下：

①集中下达、分层过渡

NSHV任务分配涉及众多不同类型的传感器，由处理/决策中心向每一个传感器下达任务分配指令，会造成通信负载过大、效率低下。因此，将处理节点作为中间层，任务分配方案集中下达给各平台任务处理节点，由节点对各传感器进行具体任务的指令下达，通信负载和任务处理速度都有极大的改善。

②协商签约、动态反馈

不同于传统的指令下达，传感器收到指令后进行评估，决定是否接受任务，如果满足各项执行条件则执行任务，同时反馈任务执行效果；否则，产生定向反馈信息，使得方案的调整具有自适应性和快速性，同时再次形成的方案也更具针对性。

③层级引导、自主协同

同一平台的传感器可能具有相同的性能，在分配传感器时，根据引导信息，针对性选择特定传感器，得到相互协同的一组或几组任务-传感器分配序列（Mission-sensor Assigned Sequence，MAS） 来执行任务，使得任务完成概率、执行效果最大限度符合要求。

2 NSHV多传感器任务分配模型

2.1 问题描述

假设在NSHV多传感器探测跟踪任务分配问题中，Np表示传感器的数量，以Sensor=｛Sensor1，Sensor2，…，SensorNp｝表示；platformt表示传感器所处的平台，t取 1，2，3，4，分别代表天基、临空基、空基和地/海基平台，不同平台的传感器具有不同的探测性能；NM表示需要执行的任务数量，以Task=｛Task1，Task2，…，TaskNM｝表示；Tasktype 表示对目标的执行任务类型，Tasktype=｛detect，track｝；NV表示来袭目标NSHV的数量，以表示；以 Si表示分配给 Sensori的任务集合，Si=｛Taski1，Taski2，…，Taskik｝。NSHV多传感器任务分配问题可以描述为：在尽可能短的时间内将针对不同NSHV的不同任务分配给系统内的多个传感器，即，使其能够快速高效稳定地完成任务分配。

由于NSHV的威胁系数极高，在条件允许的前提下要保证每个任务至少分配给一个传感器，即，当 i≠j时，可以不为Ø，以保证较高任务完成率。

为进行有效任务分配作以下假设：

①所分配的任务是不可再分解的元任务，各个任务之间具有独立性；

②传感器在任务执行过程中保持正常工作且传感器列表SR不为空；

③任务动态变化截止日期Tdeadline之后，任务列表TS不会再有新任务加入。

2.2 目标函数

为更加全面地体现模型的合理性和优越性，目标函数一般涉及多个因素。本文主要考虑对NSHV作战任务分配的高效、快速、稳定均衡等特点，从效能、时间、完成率和负载4个方面进行目标函数的构建。

其中，U（Taskik）为 Sensori完成任务 Taskik后的效能。

其中，reward（Taskik）为完成任务的收益，cost（Taskik）为相应付出的代价。收益主要与NSHV的价值val（作战性能、目标成本等）以及其要攻击的要地重要程度imp有关，通过1～9标度法进行标度，reward=；代价主要与传感器损耗cons（能量、寿命等）、传感器特性 char等有关，。一般地，val、imp、cons、char由指挥决策人员预先设定，在实际作战中根据作战需求和态势变化动态调整。

其中，Time（Si）为Sensori完成任务集Si后的时间，Time（Taskik）为 Sensori完成任务 Taskik的时间。

其中，exe（Taskik）和wait（Taskik）分别为任务执行时间和等待时间。

对于任意任务Taski1、Taski2，假定，wait（Taski2）≥wait（Taski1），如果满足0≤exe（Taski1）≤wait（Taski2）-wait（Taski1），则最小等待时间0；否则最小等待时间［11］为min｛ω2（exe（Taski1）-wait（Taski2）+wait（Taski1）），ω1（exe（Taski2）+wait（Taski2）-wait（Taski1｝，ω1、ω2（为权系数，根据以往经验预先设定。

子目标3：使各个任务完成概率successP（Taskj）最大。

其中，α和β为任务类型和传感器能力的影响因子，p和q是关于任务类型和传感器能力的函数［12］。任务完成率与任务类型执行难度负相关，与传感器能力正相关，同一任务被不同传感器执行次数越多完成率越高。

具体含义：当WLit＞0时，表示platformt中传感器sensori的任务负载比平均负载水平要高，当WLit＜0则表示比系统中的平均负载水平要低［13］。

2.3 约束条件

2.3.1 多传感器协同约束

考虑NSHV高空高速高机动等作战特性，所以在探测跟踪任务集合中的任何一个任务至少被一个传感器完成，假定资源限制每个任务至多被mj个传感器执行，而每个传感器至多执行ni个任务，具体情况在预先的任务需求中要根据特定目标的实际作战情况进行设定。设xij∈｛0,1｝为决策变量，其值满足

多传感器协同约束可以表达如下：

2.3.2 传感器任务类型

传感器任务类型主要是指对于单个传感器而言，其携带载荷类型、探测范围、工作空间等有限，难以实现全天候、大范围地连续探测跟踪，导致其完成的任务类型和数量有限。记Taskkind（Sensori）为Sensori能够执行任务类型，则Taskkind（Sensori）⊆Tasktype。

2.3.3 传感器的数量及平台约束

受资源条件和不同平台传感器部署条件的限制，NSHV传感器的数量在可行范围内尽可能地越多越好，但是并不是无限多。记各个平台的部署数量为 platformnumt，则 platformnumt≤max（platformnumt），且Sensori⊆platformt。

2.3.4 传感器的载荷及探测范围约束

目前，对于传感器的研究发展现状而言，单一平台不可能搭载各种探测载荷，并且具备无限的探测能力。假定传感器搭载的载荷load=｛radar，infra，ultraviolet，light｝，传感器 sensori的载荷类型为 loadtypei，则 loadtypei⊆load；探测距离为 distancei，其探测范围为［ai，bi］，则 distancei⊆［ai，bi］。

3 基于合同量子遗传NSHV多传感器任务分配算法

3.1 算法基本思想

量子遗传算法（Quantum Genetic Algorithm，QGA）具有更好的种群多样性、并行计算能力、不易陷入局部最优等特点［14］，但是不具有自适应性和动态协调性，缺乏与任务执行者之间的沟通，在运行过程中注重最优解的求解，忽视了任务执行者对所分配任务的“态度”。因此，本文引入了合同网的协商签约机制［15］弥补其不足。

合同量子遗传算法（Contract Net Quantum Genetic Algorithm，CNQGA），主要思想是任务处理中心下达作战任务分配方案后，任务执行者根据自身实际状态对方案进行评估，若满足执行任务条件则与处理中心签约，同时反馈任务的执行情况；否则，产生定向反馈信息，处理中心依据反馈信息定向调整，重新分配直至满足签约条件。其兼顾了量子遗传搜索范围广、并行计算快、全局寻优能力强等特点，同时充分体现了自适应性、动态反馈的特点，避免在任务执行阶段造成任务冲突，某一传感器任务负担过重，导致任务无法完成等情况。

3.2 算法实现

3.2.1 量子比特编码

在CNQGA算法中，量子位是最小的信息单元，量子比特的状态可以表示为是复数，称为量子比特的概率幅，其中，表示处于量子位0的概率，表示1的概率。采用二进制进行量子比特编码，由于NSHV多传感器任务分配影响因素众多，故采用多量子比特编码，如式（12）。

其中，qij代表第t代，第j个个体的染色体；m为染色体的基因个数；k为编码每个基因的量子比特数，可以表示2k个状态。

多量子比特编码能够体现NSHV多传感器任务分配的多态性、多样性，使得NSHV任务分配的过程更加全面系统，有利于对最优解的寻找。

3.2.2 量子旋转门更新

在CNQGA中，量子门的构造是关键环节。通常采用量子旋转门，如：

通过量子旋转门完成更新：

其中，θ为旋转角，（αi，βi）为染色体中第i个基因，且旋转角的求值一般按照下式：

其中，s（αi，βi）为旋转方向；△θi为旋转角度系数，其大小会影响收敛速度，一般情况下在0.005π～0.1π之间调整；s（αi，βi）的方向是通过表1来确定。

表1 量子旋转门角度调整策略

其中，xi为当前染色体的第i位，bi为当前最优染色体的第i位，f（x）和f（b）分别为当前染色体和当前最优染色体的适应度函数。

在NSHV多传感器任务分配中，量子旋转角的调整，为第一重定向调整。保证了任务分配的快速高效，考虑NSHV多传感器任务分配的复杂性、动态性，采用动态调整△θi的方式，来提高算法的收敛性。

3.2.3 合同协商签约机制

处理中心通过任务处理节点将多传感器任务分配指令下达给各传感器，传感器根据自身的特性、任务负载等情况，对能否高质量完成任务进行评估。若评估结果不符合要求，则产生定向反馈信息，引导再分配过程，此为第二重定向调整；如果满足执行条件，则与处理中心签约并反馈执行情况。主要的评估标准如下：

①任务完成率

NSHV多传感器探测跟踪任务的分配，要保证各项任务都有较高的完成率。假定理想完成率为δ，则当succseeP（Taskj）≥δ时，传感器与处理中心的签约概率较大。

②传感器负载

假定传感器的负载阈值为ε，则当Li≤ε时，传感器执行任务的稳定性更好，有利于处理动态复杂情况。

③等待时间

Sensori能否在下一项NSHV探测跟踪任务到达时，执行完本次任务，是保证总时间最小的关键。假定最大等待时间为σ，则wait（Taskik）≤σ时，传感器接受任务签约的概率较大。

3.3 算法流程

为了更加全面有效地进行任务分配，确定传感器列表和任务列表TS如下：

①传感器列表SR1：为已分配任务的传感器列表；②传感器列表SR2：为未分配任务的传感器列表；③任务列表TS1：为已分配的任务；④任务列表TS2：为未分配的任务。

步骤1：判断NSHV任务分配时间是否到达任务动态变化截止日期；

① if t=Tdeadline执行步骤2；

② else if t＜Tdeadline更新TS和SR；

③ else进入下一周期确定新的Tdeadline。

步骤2：确定NSHV任务列表TS和传感器列表SR，并判断TS是否为NULL；

if TS=0，执行③；else，执行步骤 3。

步骤3：执行下页图2所示的流程，得到任务分配方案；

CNQGA的具体步骤如下：

步骤3.1：初始化种群Q（t0），随机生成n个以量子比特为编码的染色体，确定种群的大小sizepop，最大迭代次数cmax；

步骤3.2：对初始种群Q（t0）中的每个个体进行一次量测，得到对应的确定解P（t0）；

步骤3.3：对各个确定解进行适应度评估，找到最优个体作为进化目标；

步骤3.4：由式（14），进行量子旋转门更新，定向调整，获得新的种群Q（t），其中旋转角调整策略借助表1进行，测试新的种群个体，评估个体的适应度，同时记录最优分配方案和对应的适应度f（x），更新 SR1、SR2、TS1、TS2；

步骤3.5：判断是否满足目标函数的要求，如果满足则执行步骤3.6，否则执行步骤3.7；

步骤3.6：判断是否满足传感器接受任务的各项评价指标，若满足执行步骤3.8，否则执行步骤3.7；

步骤3.7：产生定向调整反馈信息，将迭代次数t=t+1，并判断是否达到cmax，如果没有达到，则重复步骤3.3～步骤3.6，否则以目前最优个体进行任务分配，执行步骤3.8，进行强制签约；

步骤3.8：传感器与任务处理中心签约，更新SR1、SR2、TS1、TS2并且反馈任务的执行情况。

图2 CNQGA流程

4 仿真分析

为了简化试验，本文共设置6个传感器，其特性［16］如表 2 所示。

仿真参数设定如下，种群大小sizepop=300，迭代次数cmax=200，染色体基因数m=5，量子比特数k=20，△θi动态变化。分别运用合同量子遗传算法（CNQGA）、改进量子遗传算法（IQGA）和量子遗传算法（QGA）进行500次仿真实验，对不同任务数的运算结果取平均值，如下页表3所示。

由表3可知，同IQGA和QGA相比，随着任务数的递增，CNQGA的寻优能力更加突出，迭代次数、运行时间相对较少，同时，任务的执行负载率相对均衡。为了更加形象地对比3种算法性能，分别取任务数为8和16时，采用MATLAB进行仿真得到结果如下页图3～图6所示。

表2 不同平台传感器特性

表3 3种算法运算结果

图3 NM=8 3种算法最大适应度曲线

图4 NM=16 3种算法最大适应度曲线

图5 NM=8传感器执行任务数

图6 NM=16传感器执行任务数

由图3～图6可知，CNQGA的收敛速度最快，寻优能力突出，最优解的近似度高，同时各个传感器的任务执行数量相对均衡，保证了执行NSHV任务时稳定性最好，能够有效地对后续任务进行处理，并且实际执行任务的总数大于等于分配任务数，保证了任务的完成率，同时，当任务数越多时，CNQGA优势越明显。仿真表明，CNQGA能够满足NSHV任务分配高实时性、高完成率、稳定系统性的要求。

5 结论

针对NSHV探测跟踪任务分配难以实现高效、实时、稳定等问题，本文汲取集中式和分布式任务分配的优势，搭建了兼具两者特性的混合型任务分配体系，以体系框架为背景，构建了涵盖效能、时间、完成率和负载率的任务分配模型，考虑了传感器性能、数量、任务类型等多种约束条件，提出了具有双重定向调整机制的合同量子遗传算法，通过同IQGA和QGA的比较，表明了CNQGA算法的高效性和稳定性。为NSHV多传感器探测跟踪任务分配研究提供了模型和算法基础，为未来NSHV多传感器探测跟踪体系的建立奠定了基础。

［1］付强，王刚，郭相科，等.临空高速目标协同探测跟踪需求研究［J］.系统工程与电子技术，2015，37（4）：758-762.

［2］ THOMAS L P，CHIARA P，CYNTHIA P，et al.Sensor mission assignment in rechargeable wireless sensor networks［J］.ACM Transaction on Sensor Networks，2014，10（4）：601-637.

［3］ROWAIHY H ，PORTA T.Sensor-mission assignment in wireless sensor networks［J］.ACM Transaction on Sensor Networks，2010，6（4）：361-392.

［4］ ANUGRAHK，WIDYOTRIATMOA ，HONGKS.Sensor-based planning and control algorithms for a mobile robot over a given global planning［C］//Proceedings of the 30th Chinese Control Conference，2011：3610-3614.

［5］杜庆伟，顾汉杰，陶军.WSN中基于多目标优化的协同任务分配算法［J］.东南大学学报（自然科学版），2014，44（4）：713-716.

［6］邸斌，周锐，丁全心.多无人机分布式协同异构任务分配［J］.控制与决策，2013，28（2）：274-278.

［7］万路军，姚佩阳，周翔翔，等.有人/无人作战智能体分布式协同目标分配方法［J］.系统工程与电子技术，2014，36（2）：278-287.

［8］林林，孙其博，王尚广，等.基于时间窗的多无人机联盟任务分配方法研究 ［J］.电子与信息学报，2013，35（8）：1983-1988.

［9］ MANSOURI M，NOUNOU H.Genetic algorithm-based adaptive optimization for target tracking in wireless sensor networks［J］.Journal of Signal Processing Systems，2014，74（2）：189-202.

［10］董涛，刘付显，李响，等.反导作战任务分配方法［J］.空军工程大学学报（自然科学版），2014，15（3）：41-44.

［11］TAKEDA T，NAMERIKAWA T.Sensor network scheduling algorithm considering estimation error variance and communication energy ［C］//2010 IEEE International Conference on Control Applications，2010：434-439.

［12］ BERGMANNG，MOLNARTM，GONCZYOL，etal.Optimal period length for the CGS sensor network scheduling algorithm ［C］//2010 Sixth International Conference on Networking and Services，2010：193-199.

［13］POLAN D，BFRAGUELA B，DOALLO R.Virtually split cache：an efficient mechanism to distribute instructions and data［J］.ACM Transaction on Sensor Networks，2013，10（4）：1721-1759.

［14］梁昌勇，柏桦，蔡美菊，等.量子遗传算法研究进展［J］.计算机应用研究，2012，29（7）：2401-2404.

［15］肖玉杰，李杰，刘方.基于合同网的分布式动态任务分配算法［J］.舰船科学技术，2015，37（3）：113-118.

［16］刘兴.防空防天信息系统及其一体化技术［M］.北京：国防工业出版社，2012.