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

彭新家，欒鑄徵

(中國(guó)船舶重工集團(tuán)公司第723研究所，揚(yáng)州 225001)

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

彭新家，欒鑄徵

(中國(guó)船舶重工集團(tuán)公司第723研究所，揚(yáng)州 225001)

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

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

0 引 言

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

1 相控陣?yán)走_(dá)任務(wù)調(diào)度研究

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

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

1.2 相控陣?yán)走_(dá)任務(wù)優(yōu)化調(diào)度模型

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

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

首先，在定義的周期T中，將雷達(dá)任務(wù)按pi排序，如果pi相同，則將其按tei排序，組成待調(diào)度隊(duì)列T={T1，T2，…，TN}。接著定義2個(gè)不參與調(diào)度分析的端點(diǎn)任務(wù)T0和TN+1，設(shè)定其pi為最高，同時(shí)令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)度隊(duì)列T中取出雷達(dá)任務(wù)Ti。并設(shè)此時(shí)已有M(M≤k)個(gè)已確定調(diào)度的雷達(dá)任務(wù)，再算上2個(gè)自定義的任務(wù)T0和TN+1后，組成新的調(diào)度隊(duì)列T={T0，T1，…，TM，T(M+1)}，而且調(diào)度執(zhí)行時(shí)間滿足ts0≤ts1<…

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

[7] 盧建斌，胡衛(wèi)東，郁文賢.多功能相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度研究[J].電子學(xué)報(bào)，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

國(guó)家國(guó)際科技合作專項(xiàng)項(xiàng)目，項(xiàng)目編號(hào)：2015DFR10560

TN958.92

A

CN32-1413(2016)06-0058-04

10.16426/j.cnki.jcdzdk.2016.06.013