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

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

0 引言

臨空高超聲速飛行器（Near Space Hypersonic Vehicle，NSHV）飛行速度快、機動性能強、隱身性能好，兼具空間作戰(zhàn)和遠程精確打擊的能力，在未來攻防對抗中占有絕對性優(yōu)勢，對空天防御體系產(chǎn)生了嚴峻挑戰(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)任務分配的問題。本文借鑒反導和無人機任務分配的相關(guān)研究，搭建了NSHV多傳感器混合式任務分配體系，構(gòu)建了面向NSHV的多傳感器任務分配模型，將合同網(wǎng)的協(xié)商簽約機制引入量子遺傳算法中，提出了具有量子旋轉(zhuǎn)角和反饋信息雙重定向調(diào)整機制的合同量子遺傳算法，并通過仿真實驗，驗證了該算法的可行性和優(yōu)越性。

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

NSHV的高速、高空、高機動等特性，使得單一的探測平臺資源難以完成探測跟蹤任務，需要不同載荷、不同頻段的多源異類多傳感器協(xié)同完成，同時也就決定了其任務分配的復雜性、動態(tài)性。基于集中式的快速高效和分布式動態(tài)反饋的任務分配特點，建立了針對NSHV的多傳感器混合式任務分配體系，如圖1所示。

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

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

①集中下達、分層過渡

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

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

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

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

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

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

2.1 問題描述

假設(shè)在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多傳感器任務分配問題可以描述為：在盡可能短的時間內(nèi)將針對不同NSHV的不同任務分配給系統(tǒng)內(nèi)的多個傳感器，即，使其能夠快速高效穩(wěn)定地完成任務分配。

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

為進行有效任務分配作以下假設(shè)：

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

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

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

2.2 目標函數(shù)

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

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

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

其中，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（為權(quán)系數(shù)，根據(jù)以往經(jīng)驗預先設(shè)定。

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

其中，α和β為任務類型和傳感器能力的影響因子，p和q是關(guān)于任務類型和傳感器能力的函數(shù)［12］。任務完成率與任務類型執(zhí)行難度負相關(guān)，與傳感器能力正相關(guān)，同一任務被不同傳感器執(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)情況進行設(shè)定。設(shè)xij∈｛0,1｝為決策變量，其值滿足

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

2.3.2 傳感器任務類型

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

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

受資源條件和不同平臺傳感器部署條件的限制，NSHV傳感器的數(shù)量在可行范圍內(nèi)盡可能地越多越好，但是并不是無限多。記各個平臺的部署數(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é)調(diào)性，缺乏與任務執(zhí)行者之間的溝通，在運行過程中注重最優(yōu)解的求解，忽視了任務執(zhí)行者對所分配任務的“態(tài)度”。因此，本文引入了合同網(wǎng)的協(xié)商簽約機制［15］彌補其不足。

合同量子遺傳算法（Contract Net Quantum Genetic Algorithm，CNQGA），主要思想是任務處理中心下達作戰(zhàn)任務分配方案后，任務執(zhí)行者根據(jù)自身實際狀態(tài)對方案進行評估，若滿足執(zhí)行任務條件則與處理中心簽約，同時反饋任務的執(zhí)行情況；否則，產(chǎn)生定向反饋信息，處理中心依據(jù)反饋信息定向調(diào)整，重新分配直至滿足簽約條件。其兼顧了量子遺傳搜索范圍廣、并行計算快、全局尋優(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 量子旋轉(zhuǎn)門更新

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

通過量子旋轉(zhuǎn)門完成更新：

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

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

表1 量子旋轉(zhuǎn)門角度調(diào)整策略

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

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

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

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

①任務完成率

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

②傳感器負載

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

③等待時間

Sensori能否在下一項NSHV探測跟蹤任務到達時，執(zhí)行完本次任務，是保證總時間最小的關(guān)鍵。假定最大等待時間為σ，則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），進行量子旋轉(zhuǎn)門更新，定向調(diào)整，獲得新的種群Q（t），其中旋轉(zhuǎn)角調(diào)整策略借助表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：產(chǎn)生定向調(diào)整反饋信息，將迭代次數(shù)t=t+1，并判斷是否達到cmax，如果沒有達到，則重復步驟3.3～步驟3.6，否則以目前最優(yōu)個體進行任務分配，執(zhí)行步驟3.8，進行強制簽約；

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

圖2 CNQGA流程

4 仿真分析

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

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

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

表2 不同平臺傳感器特性

表3 3種算法運算結(jié)果

圖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 結(jié)論

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

［1］付強，王剛，郭相科，等.臨空高速目標協(xié)同探測跟蹤需求研究［J］.系統(tǒng)工程與電子技術(shù)，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é)同異構(gòu)任務分配［J］.控制與決策，2013，28（2）：274-278.

［7］萬路軍，姚佩陽，周翔翔，等.有人/無人作戰(zhàn)智能體分布式協(xié)同目標分配方法［J］.系統(tǒng)工程與電子技術(shù)，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］肖玉杰，李杰，劉方.基于合同網(wǎng)的分布式動態(tài)任務分配算法［J］.艦船科學技術(shù)，2015，37（3）：113-118.

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