基于二次規劃優化算法的雷達自適應調度研究

彭新家，欒鑄徵

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

基于二次規劃優化算法的雷達自適應調度研究

彭新家，欒鑄徵

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

建立了雷達任務數學模型，介紹了幾種常用的資源調度方法，對其中的自適應調度算法進行了分析。在此基礎上，提出了一種基于二次規劃的自適應調度優化算法，分別對其與有時間窗自適應算法進行仿真，然后對比，得到了比傳統自適應算法更優的結果。

雷達任務數學模型；自適應調度；時間窗；二次規劃

0 引 言

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

1 相控陣雷達任務調度研究

1.1 雷達任務數學模型

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

1.2 相控陣雷達任務優化調度模型

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

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

1.3 資源調度策略

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

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

2 自適應調度算法

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

2.1 無時間窗自適應調度算法

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

2.2 有時間窗自適應調度算法

在有時間窗自適應調度中，雷達任務的tsi可以在tei周圍進行提前或延遲執行。這個“周圍”就是指的tw，tsi在tw內。

首先，建立雷達任務模型如下：

(1)

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

在滿足上述3個原則的基礎上，有時間窗自適應調度會將雷達任務請求分別送進執行列表、延遲列表和刪除列表中。

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

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

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

2.3 自適應調度算法仿真

針對上文分析的有時間窗自適應調度算法，本文對其進行了仿真。

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

圖1 多目標的有時間窗自適應調度算法的時序圖

3 基于二次規劃的自適應調度算法

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

由此可知，二次規劃算法已經在大量工程實際中應用，而本文研究的雷達任務優化調度可通過提出相應的自適應調度算法[6]進行運用。

3.1 雷達數學模型

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

(2)

式中：Ei為調度間隔內任務調度消耗能量；第i個事件的最佳時間偏移量dti=tsi-twi；pi為第i個事件的優先級。

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

3.2 優化調度算法分析

首先，在定義的周期T中，將雷達任務按pi排序，如果pi相同，則將其按tei排序，組成待調度隊列T={T1，T2，…，TN}。接著定義2個不參與調度分析的端點任務T0和TN+1，設定其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成立。

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

前文的連續函數最小值和最大定理已經提到，二次規劃的目標函數的最優解在可行域是有界閉域時一定存在，僅需確保可行域為有界閉域。

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

3.3 基于二次規劃的自適應調度算法仿真

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

圖2 基于二次規劃的自適應調度算法的時序圖

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

4 結束語

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

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

[2] 趙宇.相控陣雷達資源優化管理[D].上海：上海交通大學，2012.

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

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

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

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

[7] 盧建斌，胡衛東，郁文賢.多功能相控陣雷達實時任務調度研究[J].電子學報，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