基于圖論的雷達優(yōu)化部署方法

孫華飛， 張世強, 何孟源, 陳靜超， 李萌萌, 曹越琦

(1. 北京理工大學 數(shù)學與統(tǒng)計學院, 北京 100081; 2. 中國航天系統(tǒng)科學與工程研究院，北京 100048)

現(xiàn)代空域環(huán)境日趨復雜，空襲是非常重要的防御目標之一. 空襲目標可能來自不同高度層，單部雷達顯然不能滿足多高度層覆蓋的需要，需要部署多部雷達協(xié)同作戰(zhàn).雷達組網(wǎng)的作戰(zhàn)效能很大程度上取決于組網(wǎng)部署，部署方案將直接影響空域情報信息的收集. 因此，雷達組網(wǎng)的優(yōu)化部署問題是現(xiàn)代空域防御的關(guān)鍵研究問題之一. 雷達網(wǎng)優(yōu)化部署的優(yōu)劣直接影響傳感器時間覆蓋、空間覆蓋、目標數(shù)據(jù)率，同時影響傳感器的抗干擾能力、反隱身能力以及生存能力，最終影響整個雷達組網(wǎng)的作戰(zhàn)性能.

在雷達組網(wǎng)優(yōu)化部署的問題中，已有許多研究工作，最為廣泛的方法是蒙特卡羅方法[1]和遺傳算法[2-5]以及一系列改進的自適應遺傳算法[6]等經(jīng)典方法. 蒙特卡羅方法是在限定組網(wǎng)部署形式時的常用方法,編程簡單便于實現(xiàn),而且在計算雷達組網(wǎng)的聯(lián)合探測面積時非常便利. 但這顯然限制了雷達部署形式，在實際應用中缺乏靈活性，不利于實時應變. 而遺傳算法及其一系列改進方法在解決該問題時，對部署形式有很好的適應性，打破部署形式的限制，且雷達數(shù)目較多時，可以并行處理，容易編程實現(xiàn)，且具有很強的自適應性. 以上傳統(tǒng)的優(yōu)化算法易于理解，便于實現(xiàn)，但當組網(wǎng)中雷達數(shù)目較多時，計算量大大增加，無法在一個較短時間內(nèi)給出最佳部署方案，并且戰(zhàn)爭環(huán)境的復雜性決定了雷達組網(wǎng)部署時約束的多樣性，以上兩種方法不夠靈活，不易于不同約束條件的嫁接.所以，針對傳統(tǒng)方法在雷達部署問題中存在的不足，本文基于圖論理論[7-8]設計了計算量小、運行速度快，對不同約束條件都能夠很好地兼容的算法.

本文對雷達的探測區(qū)域以及雷達的位置離散化后轉(zhuǎn)化為點，根據(jù)雷達的探測概率函數(shù)[9]等指標建圖，利用圖論相關(guān)知識將雷達部署問題轉(zhuǎn)化為一個圖論問題. 之后根據(jù)不同的約束條件建立相關(guān)模型并設計對應的算法求解，最后給出模擬仿真.

1 預備知識

1.1 圖論相關(guān)知識[10]

定義1.1.1一個無向圖G是一個有序的二元組,記為G=〈V,E〉,其中

①V是一個非空有序集，稱為頂點集，其元素稱為頂點或節(jié)點.

②E是無序集{{a,b}|a,b∈V}的有窮多重子集，稱為邊集，其元素稱為無向邊.

定義1.1.2無重邊無自環(huán)的圖稱為簡單圖.

定義1.1.3設無向簡單圖G=〈V,E〉,V*?V,若?vi∈V-V*，?vj∈V*使得(vi,vj)∈E,則稱V*為G的一個支配集，并稱vj支配vi.

定義1.1.4設無向簡單圖G=〈V,E〉,V*?V,若V*中任意兩個頂點不相鄰，則稱V*為G的一個點獨立集，簡稱獨立集.

定義1.1.5設無向簡單圖G=〈V,E〉,V*?V,若?e∈E,?v∈V*,使得v與e相關(guān)聯(lián)，則稱V*為G的點覆蓋集，簡稱點覆蓋，并稱v覆蓋e.

定義1.1.6設無向圖G=〈V,E〉,若能將V劃分成V1和V2(即V1∪V2=V,V1∩V2=?,V1,V2≠?)，使得G中每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G為二部圖(或二分圖)，稱V1和V2為互補頂點子集，常將二分圖G記為G=〈V1,V2,E〉.

1.2 雷達部署相關(guān)知識

在雷達部署問題中，通常側(cè)重某一高度的覆蓋問題，也即覆蓋區(qū)域是二維平面的一個連通子集. 在考慮覆蓋問題之前，首先要知道一部雷達的覆蓋區(qū)域，這就涉及到雷達的探測概率函數(shù)以及雷達的俯仰角.

雷達的探測概率函數(shù)是一個與雷達參數(shù)以及目標距雷達距離相關(guān)的函數(shù)，在雷達確定的前提下，雷達探測概率函數(shù)只依賴于目標距雷達的距離，且隨距離增大探測概率單調(diào)遞減. 由于不同種類的雷達探測概率函數(shù)不同，且探測概率函數(shù)形式較為復雜，在實際應用過程中直接用探測概率函數(shù)會極大地增加計算的復雜度，故通常設定一個可探測的概率界限，根據(jù)該概率界限得到雷達的探測范圍，只要目標在該探測范圍內(nèi)即視為該目標可探測，顯然雷達的探測范圍為一個圓.

雷達的俯仰角是對探測目標與雷達連線和水平平面夾角的限制，超出該限制的目標雷達是無法探測的，這與距離無關(guān)，只有滿足該限制時才能利用雷達探測概率函數(shù)判定是否可探測，這就是雷達探測盲區(qū)的由來.

注1.2.1在之后的討論中，不再具體分析探測概率函數(shù)和俯仰角，直接用內(nèi)外半徑分別為r和R來表示該雷達的圓環(huán)形探測區(qū)域.

在知道雷達的探測區(qū)域后，首先考慮的因素是對該區(qū)域的覆蓋率，即被覆蓋區(qū)域面積與整個區(qū)域面積的比值. 通常需要部署的雷達對整個區(qū)域全覆蓋，由于雷達頂端盲區(qū)(即圓環(huán)中間的空心圓)的存在，雷達重復覆蓋面積很大，這種冗余會造成雷達資源浪費，故實際考慮時需要控制冗余，使其面積不能過大.

定義1.2.3(冗余度)設整個區(qū)域面積為S，被覆蓋k次及以上的區(qū)域視作冗余，若某雷達部署方案的冗余面積為T，那么定義該方案的冗余度為T/S.

在之前的分析中是將整個區(qū)域不加區(qū)分，一個雷達探測范圍內(nèi)的區(qū)域均視作可探測，但實際中可能需要對一些區(qū)域重點探測，此時需要雷達聯(lián)合探測機制，即一塊區(qū)域需要多部雷達一起探測，這些區(qū)域稱作重點區(qū)域.

2 雷達部署

首先通過離散化后建圖將雷達部署問題轉(zhuǎn)化為圖論相關(guān)問題，介紹狀態(tài)壓縮的概念，并在離散化后的問題上重新定義覆蓋率、冗余度等約束條件，之后根據(jù)考慮因素的增多將雷達部署問題分成4個子問題，從最平凡的固定高度用同一種雷達不考慮重點區(qū)域的覆蓋問題入手，逐漸深化問題，最終對于不同高度用多用雷達考慮重點區(qū)域的覆蓋問題建立模型并設計相關(guān)算法，在模擬仿真中可以看出該算法對于這幾個子問題均可給出很好的部署方案.

2.1 離散化

在實際應用中，由于需要覆蓋的區(qū)域的點數(shù)無限，雷達位置也有無限種可能，故直接考慮該問題是十分困難的. 但如果把責任區(qū)域離散化為若干小區(qū)域(例如網(wǎng)格化)，只要每個區(qū)域的面積相對于整個區(qū)域以及雷達的掃描區(qū)域充分小，那么一個區(qū)域的覆蓋問題近似于對該區(qū)域中心點的覆蓋問題. 而對于雷達的位置，由于實際情況下一些區(qū)域無法安裝雷達，不妨取一些合適安裝雷達的點作為初始雷達的位置，那么問題轉(zhuǎn)化為從這些初始位置中選取一個子集作為所選雷達集合，選取的該集合需要滿足一定約束條件.

假設區(qū)域離散化后有n個小區(qū)域，進而得到這n個小區(qū)域的n個中心點，初始選取雷達位置有m個，根據(jù)每個位置雷達的圓環(huán)形探測范圍可以求出每部雷達可以探測到的中心點集，根據(jù)可探測關(guān)系建圖，可以得到一個二分圖如圖1所示，那么全覆蓋問題即為從雷達點集中選取子集使得區(qū)域點集中任一點都與該子集中某點相關(guān)聯(lián)，而冗余度等限制則是對所選點集的一種約束.

2.2 狀態(tài)壓縮

狀態(tài)壓縮方法是算法設計中常用的手段，該方法是用一個狀態(tài)壓縮值來表示一種將固定點集中每點分類的方案，且從一個狀態(tài)壓縮值可以很快地得到具體方案. 在本問題中，由圖論理論把警戒區(qū)域以及雷達位置均進行離散化，從而區(qū)域和雷達位置分別由兩個獨立點集表示，而每個位置是否放雷達、放何種雷達即為對該位置分類，以此為基礎，應用狀態(tài)壓縮方法可以將每種雷達部署方案數(shù)值化，極大地方便了數(shù)值求解.

此處首先給出狀態(tài)壓縮方法最初始的定義，即先不考慮點集中點的分類，只考慮每點選或不選(或從點集中選出子集)的方案與狀態(tài)壓縮值的一一對應.

定義2.2.1(狀態(tài)壓縮)對于一個有n個元素a0,a1,…,an-1的集合T的一個子集T′，定義T′的狀態(tài)壓縮值為

(1)

式中：xi=0表示T′中沒有元素ai；xi=1表示T′中有元素ai，進而建立了T的子集T′與一個介于0～2n-1之間整數(shù)的一一對應.

2.3 約束條件重新定義

定義2.3.1(覆蓋率)假設有n個中心點，某個雷達部署方案覆蓋了其中的n′個中心點，那么該方案的覆蓋率為n′/n.

定義2.3.2(冗余度)假設有n個中心點，一個中心點被覆蓋k次視作冗余，某個雷達部署方案讓n′個中心點冗余，那么該方案的冗余度為n′/n.

2.4 固定高度用一種雷達不考慮重點區(qū)域的覆蓋問題

假設有n個中心點，m個雷達位置集合，給m個雷達編號0,1,…,m-1，對于雷達集合T的一個子集T′,用其狀態(tài)壓縮值Sta(T′)表示，如此狀態(tài)壓縮將子集的概念數(shù)值化，進而極大地方便了存儲和計算. 此時不考慮重點區(qū)域，故先不考慮聯(lián)合探測. 本部分要解決的問題即為在全覆蓋的前提下如何使冗余度最小.

2.5 固定高度用一種雷達考慮重點區(qū)域的覆蓋問題

當所給區(qū)域中有一些重點區(qū)域，也即需要多部雷達覆蓋的區(qū)域時，此時需要考慮聯(lián)合探測，而之前的狀態(tài)壓縮理論依舊有效，但此時很大的變化是覆蓋的重新定義. 可以通過概率函數(shù)得到每個中心點被覆蓋需要的雷達部數(shù)(直觀上可以看做多個圓環(huán)的相交部分為重點區(qū)域)，注意到概率函數(shù)的不同會影響每一點需要被覆蓋的次數(shù)，記zi為第i個中心點需要被覆蓋的次數(shù). 本文要解決的問題依舊是在全覆蓋的前提下如何使冗余度最小.

2.6 固定高度用多種雷達考慮重點區(qū)域的覆蓋問題

2.6.1問題分析

該問題比之前二個問題的變化為要在選定雷達位置集合的基礎上還要給每個位置的雷達賦予對應的種類，故要對之前的狀態(tài)壓縮進行一些改變. 假設第i個位置的雷達有cnti-1個種類可以選取，分別為ai,1,…,ai,cnti-1，那么第i個位置的雷達有cnti種情況，不放置雷達或放置這cnti-1種雷達之一，故有以下進階的狀態(tài)壓縮.

定義2.6.1(狀態(tài)壓縮)對于一個有n個元素a0,…,an-1的集合T，假設ai有cnti-1種分配方案，那么定義從T中選取若干元素并分別分配好的方案T′的狀態(tài)壓縮值為

cnt0cnt1x2+…+cnt0cnt1…cntn-1xn-1.

(2)

2.6.2預備工作

根據(jù)一個方案的狀態(tài)壓縮值需要得到該方案的具體安排，對于之前的二進制狀態(tài)壓縮，可以通過邏輯運算快速得到狀態(tài)壓縮值的具體含義，而此時的狀態(tài)壓縮發(fā)生了較大改變，故需重新給出一種新的求具體方案的方法.

對于方案S，已知其狀態(tài)壓縮值Sta(S)，欲求x0,x1,…,xn-1，首先可以看出

x0=Sta(S)%cnt0.

(3)

之后把x0從Sta(S)中減掉，那么有

(4)

以此類推有

(5)

進而可以在線性復雜度內(nèi)求出x0,x1,…,xn-1.

2.6.3模型建立

① 初始參數(shù).

將區(qū)域離散化為n個中心點，設其坐標為(xi,yi),需要被覆蓋的次數(shù)為zi(0≤i

設初始雷達位置有m個，設其坐標為(Xi,Yi),0≤i

設有N種雷達，其掃描區(qū)域的內(nèi)外半徑為ri,Ri,0≤i

設第i個雷達位置可選雷達種類有cnti-1種，種類分別為ci,1,…,ci,cnti-1,0≤i

一個中心點覆蓋次數(shù)不低于k次視作冗余.

② 目標函數(shù).

對于給定的方案狀態(tài)壓縮值，線性時間得到每個位置放置的雷達種類，根據(jù)雷達的掃描概率函數(shù)得到每個點被覆蓋需要的雷達部數(shù)zi，根據(jù)所放置雷達的掃描范圍得到當前雷達集合對第i個點的覆蓋次數(shù)為ZT(i)，那么ZT(i)≥zi時第i個中心點被覆蓋，而ZT(i)≥k則視作該中心點冗余覆蓋，設waste(T)表示冗余點的個數(shù)，雷達集合T中的雷達個數(shù)為num(T)，那么目標函數(shù)及限制即為

(6)

2.6.4算法設計

第1步 離散化得到n個需要被覆蓋的點的坐標(xi,yi)，m個雷達的坐標(Xi,Yi)，通過每點位置和每個雷達的探測概率函數(shù)得到每個中心點需要被覆蓋的次數(shù)zi；

第2步 預處理mark(i)，即對于第i個目標點，求出第j個雷達到第i個目標點的距離，如果該距離位于該雷達的圓環(huán)掃描范圍內(nèi)則將j加入mark(i)中；

第3步 通過雷達的掃描概率函數(shù)以其俯仰角得到每種雷達在給定高度的圓環(huán)形掃描區(qū)域的內(nèi)外半徑ri,Ri,0≤i

第4步 初始化選取雷達最小數(shù)量ans=m表示選取所有雷達必然滿足條件，并計算出此時冗余點個數(shù)ansk；

2.6.5復雜度分析

2.7 多種高度用多種雷達考慮重點區(qū)域的覆蓋問題

在考慮多種高度時，顯然高空的覆蓋范圍是低空覆蓋范圍的收縮，若考慮對整個空域全覆蓋那么本質(zhì)上是對高空全覆蓋，問題變成固定高度用多種雷達考慮重點區(qū)域的覆蓋問題. 故此處可以考慮對不同高度設置權(quán)重，使得最終加權(quán)覆蓋率達到所給限制的覆蓋問題，而該問題本質(zhì)上是對第3部分結(jié)果的加權(quán)，此處不再重復之前的模型建立和算法設計.

3 模擬仿真

給定高度的平面上[0,1 000]km×[400,1 200]km的矩形區(qū)域. 考慮到雷達的掃描半徑，將該區(qū)域劃分成20×20的小塊，每塊區(qū)域用其中心點代替，進而將該區(qū)域離散化成n=2 000個點，設其坐標為(xi,yi),0≤i

3.1 固定高度用一種雷達不考慮重點區(qū)域的覆蓋問題

設定m=20個初始雷達坐標，其橫坐標分別為100,300,500,700,900，縱坐標分別為500,700,900,1 100，記其坐標分別為(Xi,Yi),0≤i

假設雷達在該高度掃描區(qū)域外半徑為330 km，內(nèi)半徑為30 km，結(jié)果如圖4，選取了7個雷達，最小冗余度為16.44%.

3.2 固定高度用一種雷達考慮重點區(qū)域的覆蓋問題

如圖5所示，劃定一塊由6個頂點的凸多邊形為重點區(qū)域，分別考慮不同掃描半徑的雷達對該區(qū)域的覆蓋情況.

假設雷達在該高度掃描區(qū)域外半徑為330 km，內(nèi)半徑為30 km，結(jié)果如圖6，選取了7個雷達，最小冗余度為16.35%.

3.3 固定高度用多種雷達考慮重點區(qū)域的覆蓋問題

同樣考慮之前的區(qū)域，此時不再分別考慮不同掃描半徑的雷達對該區(qū)域的覆蓋情況，而是考慮用多種雷達對該區(qū)域進行全覆蓋.

假設雷達有7種，其掃描半徑和俯仰角分別為(單位：(km，(°)):

(330,5～55),(170,8～52),(280,6～56),

(230,5～55),(360,10～50),(140,8～48),

(260,12～55).

在10 km高度考慮這7種雷達對整個區(qū)域的覆蓋，選取m=12個位置為雷達初始位置，其橫坐標分別為125,375,625,875，縱坐標分別為500,800,1 100. 根據(jù)不同位置所選雷達種類的不同，此處給出兩個運行結(jié)果如下.

第1種方案：如圖7所示，選取了8個雷達，冗余度為12.50%，其位置和半徑分別為

((125,500),330),((125,1 100),330),

((375,500),280),((375,1 100),360),

((625,500),330),((875,500),170),

((875,800),330),((875,1 100),280).

第2種方案：如圖8所示，選取了8個雷達，冗余度為14.70%，其位置和半徑分別為

((125,500),230),((125,800),360),

((125,1 100),330),((625,500),330),

((625,800),280),((625,1 100),230),

((875,500),280),((875,1 100),360).

3.4 結(jié)果分析

從模擬仿真結(jié)果可以看出，在無重點區(qū)域時，本算法給出的部署方案一方面保證了對整個區(qū)域全覆蓋，另一方面讓冗余度盡可能小，避免了資源浪費. 而在有重點區(qū)域時，雷達覆蓋會以該重點區(qū)域為重心，對該區(qū)域重點覆蓋，同時也能夠保證對冗余度的限制. 而在最后用多種雷達覆蓋該區(qū)域時，根據(jù)所給雷達的種類以及每個位置適合放置雷達種類的不同，本算法均可快速給出對應的部署方案，達到了多種雷達共同探測、全覆蓋、所用雷達代價最小、重點區(qū)域重點覆蓋、冗余度滿足約束等目標.

4 結(jié) 論

將圖論理論和狀態(tài)壓縮應用到雷達部署問題中，提出了新的雷達組網(wǎng)部署方法，在理論上突破了傳統(tǒng)優(yōu)化方法的研究思路. 該方法能夠靈活處理不同約束條件對雷達組網(wǎng)優(yōu)化部署的限制，具有很強的兼容性. 同時，與傳統(tǒng)優(yōu)化方法相比，本文所提方法計算量較低，大大節(jié)省了計算時間，提升優(yōu)化部署效率，便于實時戰(zhàn)略調(diào)整.