彭新家，欒鑄徵

(中國船舶重工集團公司第723研究所，揚州 225001)

基于二次規(guī)劃優(yōu)化算法的雷達自適應(yīng)調(diào)度研究

彭新家，欒鑄徵

(中國船舶重工集團公司第723研究所，揚州 225001)

建立了雷達任務(wù)數(shù)學(xué)模型，介紹了幾種常用的資源調(diào)度方法，對其中的自適應(yīng)調(diào)度算法進行了分析。在此基礎(chǔ)上，提出了一種基于二次規(guī)劃的自適應(yīng)調(diào)度優(yōu)化算法，分別對其與有時間窗自適應(yīng)算法進行仿真，然后對比，得到了比傳統(tǒng)自適應(yīng)算法更優(yōu)的結(jié)果。

雷達任務(wù)數(shù)學(xué)模型；自適應(yīng)調(diào)度；時間窗；二次規(guī)劃

0 引 言

相控陣雷達是目前被廣泛研究和應(yīng)用的雷達。傳統(tǒng)雷達大多數(shù)情況下是通過電機來實現(xiàn)機械掃描，而相控陣雷達則可利用電子掃描來實現(xiàn)波束在方位和仰角同時掃描，且輻射波束可以在很短的時間內(nèi)改變波束指向。因此，相控陣雷達可以同時兼具實時搜索、跟蹤和制導(dǎo)多目標的能力，使傳統(tǒng)雷達發(fā)展模式有了質(zhì)的改變。在相控陣雷達體系中，工作時間、能量、信號處理單元等資源是有限的，需要對目標搜索、跟蹤、制導(dǎo)等多任務(wù)進行重新動態(tài)分配。除此之外，雷達系統(tǒng)的資源還受其他環(huán)境因素的影響，如雷達自身工作產(chǎn)生的熱噪聲，跟蹤目標的類型、速度、數(shù)量、距離、機動性，以及雷達自身有限的能量等，這些都會動態(tài)影響雷達資源去執(zhí)行相應(yīng)的任務(wù)。相控陣雷達資源管理是一項非常復(fù)雜、嚴格且必不可少的工作，它已不能僅憑借操作人員的經(jīng)驗或者通過事先直接分配來進行。因此，對相控陣雷達資源管理理論進行研究，分析波束駐留調(diào)度算法以及自適應(yīng)資源分配算法，實現(xiàn)有效、實時、動態(tài)的雷達系統(tǒng)資源管理，以提高相控陣雷達系統(tǒng)的整體作戰(zhàn)效能，是一項有十分有意義的研究工作[1]。

1 相控陣雷達任務(wù)調(diào)度研究

1.1 雷達任務(wù)數(shù)學(xué)模型

在雷達任務(wù)數(shù)學(xué)模型中，首先定義一個雷達調(diào)度間隔(SI)。在1個SI內(nèi)，這個任務(wù)數(shù)學(xué)模型可定義為[Ti，pi，tei，ηi，Δti，tsi，tfi，tli]。其中pi表示任務(wù)Ti的任務(wù)優(yōu)先級，tei表示任務(wù)Ti的期望執(zhí)行時間，ηi表示任務(wù)Ti的調(diào)度屬性(或直接執(zhí)行，或延遲，或刪除)，Δti表示任務(wù)Ti的駐留時間，tsi表示任務(wù)Ti的實際執(zhí)行時間，任務(wù)Ti時間窗區(qū)間[tfi，tli]中，tfi表示任務(wù)Ti的最早可執(zhí)行時間，tli表示任務(wù)Ti的最晚可執(zhí)行時間，時間窗tw=tli-tfi。上述定義中，優(yōu)先級用阿拉伯?dāng)?shù)字表示。其數(shù)值越大，代表任務(wù)的級別越高。駐留時間代表任務(wù)執(zhí)行的時間長度[2]。

1.2 相控陣雷達任務(wù)優(yōu)化調(diào)度模型

在同一個時間槽內(nèi)，如果出現(xiàn)多個任務(wù)進行競爭，這就表示各個任務(wù)彼此之間出現(xiàn)了沖突，需要對調(diào)度進行優(yōu)化。在對相控陣雷達任務(wù)調(diào)度優(yōu)化算法進行研究時，通常情況下需滿足下面幾個設(shè)計原則：(1)優(yōu)先級原則；(2)不重疊原則。同時，時間資源、能量資源和計算資源等幾種資源的約束在分析和設(shè)計調(diào)度策略時也必須考慮。

在雷達任務(wù)調(diào)度中，滿足上述幾個設(shè)計原則和資源約束條件是前提，而最終的目的卻是使雷達任務(wù)調(diào)度成功率和時間利用率盡可能地高。因此在進行調(diào)度時，首先要確定雷達任務(wù)的調(diào)度屬性ηi，然后是調(diào)度出雷達任務(wù)的實際執(zhí)行時間tsi(要使調(diào)度時耗費的時間資源、能量資源和計算資源最小)。這是一般的任務(wù)調(diào)度流程。

1.3 資源調(diào)度策略

相控陣雷達的任務(wù)調(diào)度，通常根據(jù)雷達系統(tǒng)的不同作用方式以及功能特性來選擇不同的調(diào)度策略。一些簡易的策略諸如固定模板、多模板、部分模板和自適應(yīng)調(diào)度算法在開始研究任務(wù)調(diào)度時被廣泛拿出來進行研究。這4種策略的調(diào)度性能和效率逐漸增加，但同時其復(fù)雜度也變得越來越高[1-2]。

其中，固定模板法是在事先設(shè)定好的一個調(diào)度間隔內(nèi)對雷達事件執(zhí)行調(diào)度任務(wù)。該方法消耗資源較少，但同時該方法缺乏靈活性，且自適應(yīng)性比較差，僅能適應(yīng)功能單一的特定雷達。多模板法顧名思義是有多個模板，提前設(shè)定好，然后使每種模板均能在這些特定雷達環(huán)境下適用。該方法比固定模板法更加靈活，但不利于系統(tǒng)調(diào)整及狀態(tài)更新，且增大了系統(tǒng)資源消耗。所以該方法僅適用于對目標環(huán)境有一定先驗知識的情況下進行雷達任務(wù)調(diào)度。部分模板法是結(jié)合了固定模板法，將某些固定模板嵌入到雷達任務(wù)的SI內(nèi)，并且同時給其他突發(fā)事件在SI內(nèi)預(yù)留空余的時間。該方法與前2種方法相比，適應(yīng)性更強，效率更高，但設(shè)計較復(fù)雜，故只能適用于某些特定功能的雷達?；谇?種策略較為簡易，本文主要對第4種算法進行深入分析和仿真驗證。

2 自適應(yīng)調(diào)度算法

雷達任務(wù)的自適應(yīng)調(diào)度是根據(jù)各個任務(wù)的tei確定其tsi的過程。在這個過程中，會對任務(wù)的時間、能量和計算等資源進行重新分配。下面開始介紹無時間窗自適應(yīng)調(diào)度算法和有時間窗自適應(yīng)調(diào)度算法[3-4]。

2.1 無時間窗自適應(yīng)調(diào)度算法

無時間窗表明雷達任務(wù)的tsi與tei保持一致，提前或者延遲在這種調(diào)度中是不被允許的。任務(wù)出現(xiàn)競爭時，pi值較大的任務(wù)被執(zhí)行，而pi值較小的則被刪除；pi值相同時，tei較早的執(zhí)行，同樣較晚的會被刪除。由于在該算法中大量雷達任務(wù)被刪除，整個系統(tǒng)的資源利用率、作戰(zhàn)效能都會降低。

2.2 有時間窗自適應(yīng)調(diào)度算法

在有時間窗自適應(yīng)調(diào)度中，雷達任務(wù)的tsi可以在tei周圍進行提前或延遲執(zhí)行。這個“周圍”就是指的tw，tsi在tw內(nèi)。

首先，建立雷達任務(wù)模型如下：

(1)

可知，被成功調(diào)度執(zhí)行的雷達任務(wù)的最終實際執(zhí)行時刻是在[tei-tw，tei+tw]之間。其中，tw表示時間窗。

在滿足上述3個原則的基礎(chǔ)上，有時間窗自適應(yīng)調(diào)度會將雷達任務(wù)請求分別送進執(zhí)行列表、延遲列表和刪除列表中。

執(zhí)行列表中，pi值較大的雷達任務(wù)其tei也相應(yīng)較早。即：(1)ΔTi+TEQ≤IS， ΔTi是指第i個雷達任務(wù)請求的波束駐留長度，而TEQ是指執(zhí)行列表中已調(diào)度任務(wù)的波束駐留長度之和；(2)max(t0,tei-twi)≤tsi≤min(tei+twi,t0+IS-ΔTi)，其中t0表示調(diào)度間隔的起始時刻，twi表示第i個雷達任務(wù)請求的時間窗長度；(3)min(tsj-tsi)≥ΔTi,j∈{j|tsj>tsi}；(4)上文提到的時間利用原則也需盡量滿足。

延遲列表中，pi值較大的雷達任務(wù)其tei也相應(yīng)較早，即：(1)不滿足執(zhí)行列表中的約束條件；(2)tli滿足在下一個SI內(nèi)執(zhí)行。

刪除列表中的雷達任務(wù)：(1)不滿足執(zhí)行列表和延遲列表的約束條件；(2)tli不滿足在下一個SI內(nèi)執(zhí)行[5]。

2.3 自適應(yīng)調(diào)度算法仿真

針對上文分析的有時間窗自適應(yīng)調(diào)度算法，本文對其進行了仿真。

為了驗證自適應(yīng)調(diào)度算法的正確性與合理性，本文設(shè)定了多任務(wù)請求搶占同一執(zhí)行時間的仿真場景，任務(wù)量飽和。對此，選擇了6種雷達事件，分別為搜索、低級跟蹤、中級跟蹤、失搜、高級跟蹤和確認，選擇的時間間隔IS=50ms，仿真得到的任務(wù)請求時序圖和調(diào)度結(jié)果時序圖如圖1所示。其中，時序圖中的矩形框表示雷達任務(wù)請求，矩形框的高度表示任務(wù)的相對優(yōu)先級(優(yōu)先級1～6)，寬度表示事件的駐留時間。由調(diào)度結(jié)果時序圖可知，當(dāng)不同雷達任務(wù)的期望執(zhí)行時間發(fā)生沖突時，調(diào)度會選擇相對優(yōu)先級較高的任務(wù)優(yōu)先執(zhí)行，而相對優(yōu)先級較低的任務(wù)則在時間窗允許范圍內(nèi)調(diào)整實際執(zhí)行時間，部分無法調(diào)整的任務(wù)會被刪除。

圖1 多目標的有時間窗自適應(yīng)調(diào)度算法的時序圖

3 基于二次規(guī)劃的自適應(yīng)調(diào)度算法

二次規(guī)劃是一種優(yōu)于常規(guī)自適應(yīng)算法、解決非線性優(yōu)化問題的算法，已應(yīng)用于很多方面的非線性問題。通過對比分析，二次規(guī)劃算法自身有以下幾個特性且可進行應(yīng)用：(1)二次規(guī)劃算法的目標函數(shù)是二次實函數(shù)，且其約束條件為線性約束，這樣就方便進行求解。(2)對于二次實函數(shù)，若其在可行域內(nèi)連續(xù)，則由連續(xù)函數(shù)最大值和最小值定理：在有界閉域內(nèi)的多元連續(xù)函數(shù)，其一定有最大值和最小值。這就可以證明二次規(guī)劃的目標函數(shù)在可行域內(nèi)連續(xù)的條件下其最優(yōu)解在可行域有界閉域時是一定存在的。(3)如果二次實函數(shù)的Hesse矩陣正定，則該二次函數(shù)為凸函數(shù)，且其最優(yōu)解存在且唯一。

由此可知，二次規(guī)劃算法已經(jīng)在大量工程實際中應(yīng)用，而本文研究的雷達任務(wù)優(yōu)化調(diào)度可通過提出相應(yīng)的自適應(yīng)調(diào)度算法[6]進行運用。

3.1 雷達數(shù)學(xué)模型

對于集合T中的2個任務(wù)T(p-1)和T(p)，當(dāng)優(yōu)化準則選擇為加權(quán)的時間偏移量平方和最小時，所建立的優(yōu)化模型如下：

(2)

式中：Ei為調(diào)度間隔內(nèi)任務(wù)調(diào)度消耗能量；第i個事件的最佳時間偏移量dti=tsi-twi；pi為第i個事件的優(yōu)先級。

雷達任務(wù)的相對優(yōu)先級用目標函數(shù)中的權(quán)值來表征，這表明對于同一時間偏移量，pi越高的雷達任務(wù)，其對應(yīng)付出的代價、消耗的資源也就越大。合理選擇約束條件，就可以使優(yōu)化模型中的幾個任務(wù)之間不存在沖突的情況[7]。

3.2 優(yōu)化調(diào)度算法分析

首先，在定義的周期T中，將雷達任務(wù)按pi排序，如果pi相同，則將其按tei排序，組成待調(diào)度隊列T={T1，T2，…，TN}。接著定義2個不參與調(diào)度分析的端點任務(wù)T0和TN+1，設(shè)定其pi為最高，同時令tf0=tw0=tl0=ts0=t0，Δt0=0和tf(N+1)=tw(N+1)=tl(N+1)=ts(N+1)=t0+IS，ΔtN+1=0成立。

可以假定當(dāng)調(diào)度到第k步，先從待調(diào)度隊列T中取出雷達任務(wù)Ti。并設(shè)此時已有M(M≤k)個已確定調(diào)度的雷達任務(wù)，再算上2個自定義的任務(wù)T0和TN+1后，組成新的調(diào)度隊列T={T0，T1，…，TM，T(M+1)}，而且調(diào)度執(zhí)行時間滿足ts0≤ts1<…

前文的連續(xù)函數(shù)最小值和最大定理已經(jīng)提到，二次規(guī)劃的目標函數(shù)的最優(yōu)解在可行域是有界閉域時一定存在，僅需確?？尚杏驗橛薪玳]域。

判斷調(diào)度屬性時，在滿足約束條件的前提下，就是要使雷達任務(wù)Ti的tei前面的任務(wù)T(p-1)盡可能前移，而后面的任務(wù)T(p)則盡可能延遲即后移，假使空余出的時間間隔大于雷達任務(wù)Ti的駐留時間，則將雷達任務(wù)Ti插入至調(diào)度雷達序列T中。

3.3 基于二次規(guī)劃的自適應(yīng)調(diào)度算法仿真

為驗證基于二次規(guī)劃的自適應(yīng)調(diào)度算法的正確性與合理性，本文同樣設(shè)定了多任務(wù)請求搶占同一執(zhí)行時間的仿真場景，任務(wù)量飽和。選擇了6種雷達事件，分別為低優(yōu)先級搜索、高優(yōu)先級搜索、普通跟蹤、精密跟蹤和確認，任務(wù)請求時序圖和調(diào)度結(jié)果時序圖如圖2所示。

圖2 基于二次規(guī)劃的自適應(yīng)調(diào)度算法的時序圖

對比常規(guī)的有時間窗自適應(yīng)調(diào)度算法與基于二次規(guī)劃的自適應(yīng)調(diào)度算法，上文對這2種算法分別仿真，得出了調(diào)度后時序圖的仿真結(jié)果。其中，2種算法均選擇了6種雷達事件，分別為搜索、低級跟蹤、中級跟蹤、失搜、高級跟蹤和確認，選擇的時間間隔SI均為50ms，優(yōu)先級均為1～6，任務(wù)時間設(shè)置均為300ms，任務(wù)負載均在100%以上。由圖1和圖2可知，經(jīng)過基于二次規(guī)劃的自適應(yīng)調(diào)度算法的任務(wù)調(diào)度的調(diào)度成功率相對于常規(guī)的有時間窗自適應(yīng)調(diào)度算法是更高的。常規(guī)的有時間窗自適應(yīng)調(diào)度算法的調(diào)度成功率SSR接近74%，但基于二次規(guī)劃的自適應(yīng)調(diào)度算法的調(diào)度成功率SSR達到了83.7%，調(diào)度成功率提高了接近10%，調(diào)度成功率改善較顯著。

4 結(jié)束語

本文主要針對二維相控陣雷達資源管理以及任務(wù)調(diào)度問題，展開了一系列研究，闡述了常用的資源優(yōu)化方法，介紹了資源調(diào)度策略，建立了基于二次規(guī)劃的自適應(yīng)調(diào)度算法下相控陣雷達任務(wù)調(diào)度數(shù)學(xué)模型，并對其優(yōu)化策略算法進行了仿真分析，與自適應(yīng)調(diào)度算法相比，任務(wù)調(diào)度率提高，驗證了算法的有效性，為相控陣雷達資源管理提供了一種實現(xiàn)方法。

[1] 丁鷺飛，耿富錄，陳建春.雷達原理[M].北京：電子工業(yè)出版社，2014.

[2] 趙宇.相控陣雷達資源優(yōu)化管理[D].上海：上海交通大學(xué)，2012.

[3] 毛依娜.相控陣雷達在跟蹤模式下的資源管理及任務(wù)調(diào)度研究[D].西安：西安電子科技大學(xué)，2011.

[4] 李倩.多功能相控陣雷達跟蹤及調(diào)度算法研究[D].西安：西安電子科技大學(xué)，2011.

[5]WASHBURNR,SCHNEIDERM,FOXJ.Stochasticdynamicprogrammingbasedapproachestosensorresouecemanagement[C]//Proceedingof5thInternationalConferenceonInformationFusion,2002:608-615.

[6] 陳永森，徐磊.一種基于二次規(guī)劃法的雷達資源調(diào)度方法[J].艦船電子對抗，2015,38(6):18-20.

[7] 盧建斌，胡衛(wèi)東，郁文賢.多功能相控陣雷達實時任務(wù)調(diào)度研究[J].電子學(xué)報，2011，34(4):732-736.

Radar Adaptive Scheduling Research Based on Quadratic Programming Optimized Algorithm

PENG Xin-jia，LUAN Zhu-zheng

(The 723 Institute of CSIC，Yangzhou 225001，China)

This article founds the mathematical model of radar task,introduces several common methods of resource scheduling,and analyzes the adaptive scheduling algorithm.On this basis,the article puts forward an adaptive scheduling optimized algorithm based on quadratic programming,separately simulates the algorithm and the adaptive algorithm with time window,then compares the simulation results,and gets a simulation result which is better than traditional adaptive algorithm.

mathematical model of radar task；adaptive scheduling；time window；quadratic programming

2016-04-13

國家國際科技合作專項項目，項目編號：2015DFR10560

TN958.92

A

CN32-1413(2016)06-0058-04

10.16426/j.cnki.jcdzdk.2016.06.013