臨空高超聲速飛行器多傳感器任務分配算法*

孫 文，王 剛，付 強，王晶晶

（空軍工程大學防空反導學院，西安 710051）

0 引言

臨空高超聲速飛行器（Near Space Hypersonic Vehicle，NSHV）飛行速度快、機動性能強、隱身性能好，兼具空間作戰(zhàn)和遠程精確打擊的能力，在未來攻防對抗中占有絕對性優(yōu)勢，對空天防御體系產生了嚴峻挑戰(zhàn)［1］。從防御角度分析，實現(xiàn)對NSHV的探測跟蹤是進行攔截作戰(zhàn)的重中之重，而高效、合理的探測跟蹤任務分配機制則是作戰(zhàn)行動的必要條件。NSHV的作戰(zhàn)特性不同于彈道導彈的軌跡可預測，空氣動力學目標的低空、慢速，使得現(xiàn)有的多傳感器任務分配體系難以對其進行快速高效穩(wěn)定、動態(tài)反饋、全面系統(tǒng)的任務分配。因此，展開對NSHV任務分配的研究是一項前沿重點課題。

目前，針對NSHV多傳感器探測跟蹤任務分配的研究剛剛起步，大多數(shù)作戰(zhàn)任務分配研究集中在反導作戰(zhàn)任務和無人機作戰(zhàn)任務分配上，任務分配方式主要以獨立的集中式和分布式為主，對具有快速高效、動態(tài)反饋和自適應的特點混合式任務分配研究不足［2-4］。文獻［5-8］主要以攻擊代價和收益為指標，運用粒子群算法、改進遺傳算法、分布式拍賣算法等，解決多無人機協(xié)同任務分配問題；文獻［9-10］運用多維動態(tài)列表規(guī)劃的思想、自適應遺傳算法，解決反導作戰(zhàn)任務分配的問題。本文借鑒反導和無人機任務分配的相關研究，搭建了NSHV多傳感器混合式任務分配體系，構建了面向NSHV的多傳感器任務分配模型，將合同網的協(xié)商簽約機制引入量子遺傳算法中，提出了具有量子旋轉角和反饋信息雙重定向調整機制的合同量子遺傳算法，并通過仿真實驗，驗證了該算法的可行性和優(yōu)越性。

1 NSHV多傳感器混合式任務分配體系

NSHV的高速、高空、高機動等特性，使得單一的探測平臺資源難以完成探測跟蹤任務，需要不同載荷、不同頻段的多源異類多傳感器協(xié)同完成，同時也就決定了其任務分配的復雜性、動態(tài)性?；诩惺降目焖俑咝Ш头植际絼討B(tài)反饋的任務分配特點，建立了針對NSHV的多傳感器混合式任務分配體系，如圖1所示。

圖1 NSHV多傳感器混合式任務分配體系

圖1可知，該體系主要包括任務處理/決策中心、天-臨-空-地/?；脚_傳感器及其任務處理節(jié)點，可劃分為決策層、中間層和執(zhí)行層，充分體現(xiàn)了多平臺交互協(xié)同、分層式指令下達、多屬性效果反饋等特點，有利于多傳感器探測跟蹤任務的高效、快速分配。其具體特征如下：

①集中下達、分層過渡

NSHV任務分配涉及眾多不同類型的傳感器，由處理/決策中心向每一個傳感器下達任務分配指令，會造成通信負載過大、效率低下。因此，將處理節(jié)點作為中間層，任務分配方案集中下達給各平臺任務處理節(jié)點，由節(jié)點對各傳感器進行具體任務的指令下達，通信負載和任務處理速度都有極大的改善。

②協(xié)商簽約、動態(tài)反饋

不同于傳統(tǒng)的指令下達，傳感器收到指令后進行評估，決定是否接受任務，如果滿足各項執(zhí)行條件則執(zhí)行任務，同時反饋任務執(zhí)行效果；否則，產生定向反饋信息，使得方案的調整具有自適應性和快速性，同時再次形成的方案也更具針對性。

③層級引導、自主協(xié)同

同一平臺的傳感器可能具有相同的性能，在分配傳感器時，根據(jù)引導信息，針對性選擇特定傳感器，得到相互協(xié)同的一組或幾組任務-傳感器分配序列（Mission-sensor Assigned Sequence，MAS） 來執(zhí)行任務，使得任務完成概率、執(zhí)行效果最大限度符合要求。

2 NSHV多傳感器任務分配模型

2.1 問題描述

假設在NSHV多傳感器探測跟蹤任務分配問題中，Np表示傳感器的數(shù)量，以Sensor=｛Sensor1，Sensor2，…，SensorNp｝表示；platformt表示傳感器所處的平臺，t取 1，2，3，4，分別代表天基、臨空基、空基和地/海基平臺，不同平臺的傳感器具有不同的探測性能；NM表示需要執(zhí)行的任務數(shù)量，以Task=｛Task1，Task2，…，TaskNM｝表示；Tasktype 表示對目標的執(zhí)行任務類型，Tasktype=｛detect，track｝；NV表示來襲目標NSHV的數(shù)量，以表示；以 Si表示分配給 Sensori的任務集合，Si=｛Taski1，Taski2，…，Taskik｝。NSHV多傳感器任務分配問題可以描述為：在盡可能短的時間內將針對不同NSHV的不同任務分配給系統(tǒng)內的多個傳感器，即，使其能夠快速高效穩(wěn)定地完成任務分配。

由于NSHV的威脅系數(shù)極高，在條件允許的前提下要保證每個任務至少分配給一個傳感器，即，當 i≠j時，可以不為?，以保證較高任務完成率。

為進行有效任務分配作以下假設：

①所分配的任務是不可再分解的元任務，各個任務之間具有獨立性；

②傳感器在任務執(zhí)行過程中保持正常工作且傳感器列表SR不為空；

③任務動態(tài)變化截止日期Tdeadline之后，任務列表TS不會再有新任務加入。

2.2 目標函數(shù)

為更加全面地體現(xiàn)模型的合理性和優(yōu)越性，目標函數(shù)一般涉及多個因素。本文主要考慮對NSHV作戰(zhàn)任務分配的高效、快速、穩(wěn)定均衡等特點，從效能、時間、完成率和負載4個方面進行目標函數(shù)的構建。

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

其中，reward（Taskik）為完成任務的收益，cost（Taskik）為相應付出的代價。收益主要與NSHV的價值val（作戰(zhàn)性能、目標成本等）以及其要攻擊的要地重要程度imp有關，通過1～9標度法進行標度，reward=；代價主要與傳感器損耗cons（能量、壽命等）、傳感器特性 char等有關，。一般地，val、imp、cons、char由指揮決策人員預先設定，在實際作戰(zhàn)中根據(jù)作戰(zhàn)需求和態(tài)勢變化動態(tài)調整。

其中，Time（Si）為Sensori完成任務集Si后的時間，Time（Taskik）為 Sensori完成任務 Taskik的時間。

其中，exe（Taskik）和wait（Taskik）分別為任務執(zhí)行時間和等待時間。

對于任意任務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（為權系數(shù)，根據(jù)以往經驗預先設定。

子目標3：使各個任務完成概率successP（Taskj）最大。

其中，α和β為任務類型和傳感器能力的影響因子，p和q是關于任務類型和傳感器能力的函數(shù)［12］。任務完成率與任務類型執(zhí)行難度負相關，與傳感器能力正相關，同一任務被不同傳感器執(zhí)行次數(shù)越多完成率越高。

具體含義：當WLit＞0時，表示platformt中傳感器sensori的任務負載比平均負載水平要高，當WLit＜0則表示比系統(tǒng)中的平均負載水平要低［13］。

2.3 約束條件

2.3.1 多傳感器協(xié)同約束

考慮NSHV高空高速高機動等作戰(zhàn)特性，所以在探測跟蹤任務集合中的任何一個任務至少被一個傳感器完成，假定資源限制每個任務至多被mj個傳感器執(zhí)行，而每個傳感器至多執(zhí)行ni個任務，具體情況在預先的任務需求中要根據(jù)特定目標的實際作戰(zhàn)情況進行設定。設xij∈｛0,1｝為決策變量，其值滿足

多傳感器協(xié)同約束可以表達如下：

2.3.2 傳感器任務類型

傳感器任務類型主要是指對于單個傳感器而言，其攜帶載荷類型、探測范圍、工作空間等有限，難以實現(xiàn)全天候、大范圍地連續(xù)探測跟蹤，導致其完成的任務類型和數(shù)量有限。記Taskkind（Sensori）為Sensori能夠執(zhí)行任務類型，則Taskkind（Sensori）?Tasktype。

2.3.3 傳感器的數(shù)量及平臺約束

受資源條件和不同平臺傳感器部署條件的限制，NSHV傳感器的數(shù)量在可行范圍內盡可能地越多越好，但是并不是無限多。記各個平臺的部署數(shù)量為 platformnumt，則 platformnumt≤max（platformnumt），且Sensori?platformt。

2.3.4 傳感器的載荷及探測范圍約束

目前，對于傳感器的研究發(fā)展現(xiàn)狀而言，單一平臺不可能搭載各種探測載荷，并且具備無限的探測能力。假定傳感器搭載的載荷load=｛radar，infra，ultraviolet，light｝，傳感器 sensori的載荷類型為 loadtypei，則 loadtypei?load；探測距離為 distancei，其探測范圍為［ai，bi］，則 distancei?［ai，bi］。

3 基于合同量子遺傳NSHV多傳感器任務分配算法

3.1 算法基本思想

量子遺傳算法（Quantum Genetic Algorithm，QGA）具有更好的種群多樣性、并行計算能力、不易陷入局部最優(yōu)等特點［14］，但是不具有自適應性和動態(tài)協(xié)調性，缺乏與任務執(zhí)行者之間的溝通，在運行過程中注重最優(yōu)解的求解，忽視了任務執(zhí)行者對所分配任務的“態(tài)度”。因此，本文引入了合同網的協(xié)商簽約機制［15］彌補其不足。

合同量子遺傳算法（Contract Net Quantum Genetic Algorithm，CNQGA），主要思想是任務處理中心下達作戰(zhàn)任務分配方案后，任務執(zhí)行者根據(jù)自身實際狀態(tài)對方案進行評估，若滿足執(zhí)行任務條件則與處理中心簽約，同時反饋任務的執(zhí)行情況；否則，產生定向反饋信息，處理中心依據(jù)反饋信息定向調整，重新分配直至滿足簽約條件。其兼顧了量子遺傳搜索范圍廣、并行計算快、全局尋優(yōu)能力強等特點，同時充分體現(xiàn)了自適應性、動態(tài)反饋的特點，避免在任務執(zhí)行階段造成任務沖突，某一傳感器任務負擔過重，導致任務無法完成等情況。

3.2 算法實現(xiàn)

3.2.1 量子比特編碼

在CNQGA算法中，量子位是最小的信息單元，量子比特的狀態(tài)可以表示為是復數(shù)，稱為量子比特的概率幅，其中，表示處于量子位0的概率，表示1的概率。采用二進制進行量子比特編碼，由于NSHV多傳感器任務分配影響因素眾多，故采用多量子比特編碼，如式（12）。

其中，qij代表第t代，第j個個體的染色體；m為染色體的基因個數(shù)；k為編碼每個基因的量子比特數(shù)，可以表示2k個狀態(tài)。

多量子比特編碼能夠體現(xiàn)NSHV多傳感器任務分配的多態(tài)性、多樣性，使得NSHV任務分配的過程更加全面系統(tǒng)，有利于對最優(yōu)解的尋找。

3.2.2 量子旋轉門更新

在CNQGA中，量子門的構造是關鍵環(huán)節(jié)。通常采用量子旋轉門，如：

通過量子旋轉門完成更新：

其中，θ為旋轉角，（αi，βi）為染色體中第i個基因，且旋轉角的求值一般按照下式：

其中，s（αi，βi）為旋轉方向；△θi為旋轉角度系數(shù)，其大小會影響收斂速度，一般情況下在0.005π～0.1π之間調整；s（αi，βi）的方向是通過表1來確定。

表1 量子旋轉門角度調整策略

其中，xi為當前染色體的第i位，bi為當前最優(yōu)染色體的第i位，f（x）和f（b）分別為當前染色體和當前最優(yōu)染色體的適應度函數(shù)。

在NSHV多傳感器任務分配中，量子旋轉角的調整，為第一重定向調整。保證了任務分配的快速高效，考慮NSHV多傳感器任務分配的復雜性、動態(tài)性，采用動態(tài)調整△θi的方式，來提高算法的收斂性。

3.2.3 合同協(xié)商簽約機制

處理中心通過任務處理節(jié)點將多傳感器任務分配指令下達給各傳感器，傳感器根據(jù)自身的特性、任務負載等情況，對能否高質量完成任務進行評估。若評估結果不符合要求，則產生定向反饋信息，引導再分配過程，此為第二重定向調整；如果滿足執(zhí)行條件，則與處理中心簽約并反饋執(zhí)行情況。主要的評估標準如下：

①任務完成率

NSHV多傳感器探測跟蹤任務的分配，要保證各項任務都有較高的完成率。假定理想完成率為δ，則當succseeP（Taskj）≥δ時，傳感器與處理中心的簽約概率較大。

②傳感器負載

假定傳感器的負載閾值為ε，則當Li≤ε時，傳感器執(zhí)行任務的穩(wěn)定性更好，有利于處理動態(tài)復雜情況。

③等待時間

Sensori能否在下一項NSHV探測跟蹤任務到達時，執(zhí)行完本次任務，是保證總時間最小的關鍵。假定最大等待時間為σ，則wait（Taskik）≤σ時，傳感器接受任務簽約的概率較大。

3.3 算法流程

為了更加全面有效地進行任務分配，確定傳感器列表和任務列表TS如下：

①傳感器列表SR1：為已分配任務的傳感器列表；②傳感器列表SR2：為未分配任務的傳感器列表；③任務列表TS1：為已分配的任務；④任務列表TS2：為未分配的任務。

步驟1：判斷NSHV任務分配時間是否到達任務動態(tài)變化截止日期；

① if t=Tdeadline執(zhí)行步驟2；

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

③ else進入下一周期確定新的Tdeadline。

步驟2：確定NSHV任務列表TS和傳感器列表SR，并判斷TS是否為NULL；

if TS=0，執(zhí)行③；else，執(zhí)行步驟 3。

步驟3：執(zhí)行下頁圖2所示的流程，得到任務分配方案；

CNQGA的具體步驟如下：

步驟3.1：初始化種群Q（t0），隨機生成n個以量子比特為編碼的染色體，確定種群的大小sizepop，最大迭代次數(shù)cmax；

步驟3.2：對初始種群Q（t0）中的每個個體進行一次量測，得到對應的確定解P（t0）；

步驟3.3：對各個確定解進行適應度評估，找到最優(yōu)個體作為進化目標；

步驟3.4：由式（14），進行量子旋轉門更新，定向調整，獲得新的種群Q（t），其中旋轉角調整策略借助表1進行，測試新的種群個體，評估個體的適應度，同時記錄最優(yōu)分配方案和對應的適應度f（x），更新 SR1、SR2、TS1、TS2；

步驟3.5：判斷是否滿足目標函數(shù)的要求，如果滿足則執(zhí)行步驟3.6，否則執(zhí)行步驟3.7；

步驟3.6：判斷是否滿足傳感器接受任務的各項評價指標，若滿足執(zhí)行步驟3.8，否則執(zhí)行步驟3.7；

步驟3.7：產生定向調整反饋信息，將迭代次數(shù)t=t+1，并判斷是否達到cmax，如果沒有達到，則重復步驟3.3～步驟3.6，否則以目前最優(yōu)個體進行任務分配，執(zhí)行步驟3.8，進行強制簽約；

步驟3.8：傳感器與任務處理中心簽約，更新SR1、SR2、TS1、TS2并且反饋任務的執(zhí)行情況。

圖2 CNQGA流程

4 仿真分析

為了簡化試驗，本文共設置6個傳感器，其特性［16］如表 2 所示。

仿真參數(shù)設定如下，種群大小sizepop=300，迭代次數(shù)cmax=200，染色體基因數(shù)m=5，量子比特數(shù)k=20，△θi動態(tài)變化。分別運用合同量子遺傳算法（CNQGA）、改進量子遺傳算法（IQGA）和量子遺傳算法（QGA）進行500次仿真實驗，對不同任務數(shù)的運算結果取平均值，如下頁表3所示。

由表3可知，同IQGA和QGA相比，隨著任務數(shù)的遞增，CNQGA的尋優(yōu)能力更加突出，迭代次數(shù)、運行時間相對較少，同時，任務的執(zhí)行負載率相對均衡。為了更加形象地對比3種算法性能，分別取任務數(shù)為8和16時，采用MATLAB進行仿真得到結果如下頁圖3～圖6所示。

表2 不同平臺傳感器特性

表3 3種算法運算結果

圖3 NM=8 3種算法最大適應度曲線

圖4 NM=16 3種算法最大適應度曲線

圖5 NM=8傳感器執(zhí)行任務數(shù)

圖6 NM=16傳感器執(zhí)行任務數(shù)

由圖3～圖6可知，CNQGA的收斂速度最快，尋優(yōu)能力突出，最優(yōu)解的近似度高，同時各個傳感器的任務執(zhí)行數(shù)量相對均衡，保證了執(zhí)行NSHV任務時穩(wěn)定性最好，能夠有效地對后續(xù)任務進行處理，并且實際執(zhí)行任務的總數(shù)大于等于分配任務數(shù)，保證了任務的完成率，同時，當任務數(shù)越多時，CNQGA優(yōu)勢越明顯。仿真表明，CNQGA能夠滿足NSHV任務分配高實時性、高完成率、穩(wěn)定系統(tǒng)性的要求。

5 結論

針對NSHV探測跟蹤任務分配難以實現(xiàn)高效、實時、穩(wěn)定等問題，本文汲取集中式和分布式任務分配的優(yōu)勢，搭建了兼具兩者特性的混合型任務分配體系，以體系框架為背景，構建了涵蓋效能、時間、完成率和負載率的任務分配模型，考慮了傳感器性能、數(shù)量、任務類型等多種約束條件，提出了具有雙重定向調整機制的合同量子遺傳算法，通過同IQGA和QGA的比較，表明了CNQGA算法的高效性和穩(wěn)定性。為NSHV多傳感器探測跟蹤任務分配研究提供了模型和算法基礎，為未來NSHV多傳感器探測跟蹤體系的建立奠定了基礎。

［1］付強，王剛，郭相科，等.臨空高速目標協(xié)同探測跟蹤需求研究［J］.系統(tǒng)工程與電子技術，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中基于多目標優(yōu)化的協(xié)同任務分配算法［J］.東南大學學報（自然科學版），2014，44（4）：713-716.

［6］邸斌，周銳，丁全心.多無人機分布式協(xié)同異構任務分配［J］.控制與決策，2013，28（2）：274-278.

［7］萬路軍，姚佩陽，周翔翔，等.有人/無人作戰(zhàn)智能體分布式協(xié)同目標分配方法［J］.系統(tǒng)工程與電子技術，2014，36（2）：278-287.

［8］林林，孫其博，王尚廣，等.基于時間窗的多無人機聯(lián)盟任務分配方法研究 ［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］董濤，劉付顯，李響，等.反導作戰(zhàn)任務分配方法［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］肖玉杰，李杰，劉方.基于合同網的分布式動態(tài)任務分配算法［J］.艦船科學技術，2015，37（3）：113-118.

［16］劉興.防空防天信息系統(tǒng)及其一體化技術［M］.北京：國防工業(yè)出版社，2012.