異構(gòu)多基地雷達(dá)直線(xiàn)柵欄覆蓋的布站優(yōu)化方法

李海鵬， 馮大政， 陳少鋒

(1.西安電子科技大學(xué) 雷達(dá)信號(hào)處理國(guó)家重點(diǎn)實(shí)驗(yàn)室， 陜西 西安 7100071;2.西安電子工程研究所 總體一部， 陜西 西安 710100；3.武警工程大學(xué) 教研保障中心， 陜西 西安 710086)

0 引言

柵欄覆蓋在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)的應(yīng)用中有著極其重要作用與地位，其廣泛應(yīng)用于工業(yè)、經(jīng)濟(jì)、軍事等諸多領(lǐng)域。近年來(lái)，基于雷達(dá)的WSN被用于對(duì)重點(diǎn)區(qū)域進(jìn)行探測(cè)與監(jiān)控。為能夠檢測(cè)到以任意路徑進(jìn)重點(diǎn)區(qū)域的入侵者，通常需要利用雷達(dá)網(wǎng)絡(luò)構(gòu)建一個(gè)連續(xù)的雷達(dá)柵欄覆蓋。

傳統(tǒng)的雷達(dá)柵欄覆蓋是基于圓盤(pán)或扇形覆蓋模型而構(gòu)建的，在這些模型中發(fā)射器與接收器共置，通常稱(chēng)其為單基地雷達(dá)。但是單基地雷達(dá)發(fā)射器利用率不高、安全性較差。相對(duì)的，多基地雷達(dá)由若干分開(kāi)放置的發(fā)射器和接收器構(gòu)成，具有抗干擾、抗反輻射導(dǎo)彈、反隱身、反低空突防能力強(qiáng)等特性，在性能上和成本上相比于單基地雷達(dá)更具有優(yōu)勢(shì)。由于發(fā)射器和接收器的布站位置對(duì)多基地雷達(dá)的覆蓋區(qū)域有直接影響，因此近年來(lái)關(guān)于多基地雷達(dá)的布站優(yōu)化問(wèn)題受到了廣泛關(guān)注。根據(jù)應(yīng)用場(chǎng)景不同，布站優(yōu)化問(wèn)題可分為直線(xiàn)(帶狀)柵欄覆蓋和圓周(圓環(huán)帶)柵欄覆蓋。文獻(xiàn)[11]以布站成本最小化為準(zhǔn)則構(gòu)建帶狀柵欄覆蓋,并研究了雷達(dá)布站的容錯(cuò)和節(jié)能問(wèn)題；文獻(xiàn)[12]構(gòu)建K柵欄覆蓋；文獻(xiàn)[13]構(gòu)建點(diǎn)目標(biāo)柵欄覆蓋；文獻(xiàn)[14-18]基于直線(xiàn)構(gòu)建帶狀柵欄覆蓋，使得布站總成本最?。晃墨I(xiàn)[19-20]以最小化布站總成本為準(zhǔn)則，分別研究圓周型柵欄覆蓋問(wèn)題和具有給定寬度的圓環(huán)型柵欄覆蓋問(wèn)題。同時(shí)，以上文獻(xiàn)均假設(shè)發(fā)射器和接收器的性能參數(shù)都分別相同，即為同構(gòu)多基地雷達(dá)(HMMR)。而實(shí)際應(yīng)用中由于布站位置受限的原因，基于HMMR的優(yōu)化結(jié)果可能不易實(shí)現(xiàn)。利用含有不同發(fā)射器的多基地雷達(dá)網(wǎng)絡(luò)進(jìn)行布站，即采用異構(gòu)多基地雷達(dá)(HTMR)，則可以適應(yīng)更復(fù)雜的應(yīng)用場(chǎng)景。如圖1(a)所示，假設(shè)兩條曲線(xiàn)之間為限制區(qū)，雷達(dá)不能布置在該范圍內(nèi)，此時(shí)基于HMMR的布站結(jié)果不符合實(shí)際應(yīng)用要求。相對(duì)的，在圖1(b)中，采用HTMR的布站方法可以避開(kāi)限制區(qū)。、是兩種不同的發(fā)射器，其中紅色發(fā)射器為異構(gòu)發(fā)射器，,…,為接收器。

圖1 雷達(dá)網(wǎng)絡(luò)構(gòu)建柵欄覆蓋示意圖Fig.1 Barrier coverage diagram of the radar network

文獻(xiàn)[21]基于HTMR進(jìn)行研究，主要討論了直線(xiàn)柵欄覆蓋的布站問(wèn)題，通過(guò)仿真實(shí)驗(yàn)表明HTMR的最優(yōu)布站結(jié)果依賴(lài)于不同發(fā)射器的布站次序，指出從理論上給出如何確定這一最優(yōu)次序是十分困難的。因此，如何優(yōu)化HTMR網(wǎng)絡(luò)的布站位置，使得成本最小是一個(gè)值得研究和探討的問(wèn)題。本文受文獻(xiàn)[21]啟發(fā)，但與該文獻(xiàn)不同，主要有以下區(qū)別：

1) 文獻(xiàn)[21]對(duì)雷達(dá)傳感器的布站位置無(wú)要求與限制，本文從實(shí)際應(yīng)用場(chǎng)景出發(fā)，考慮在布站位置受限的情況下，基于HTMR的優(yōu)化布站方法。

2) 文獻(xiàn)[21]在仿真中采用6種HTMR(每種發(fā)射器最多只有一個(gè))構(gòu)建柵欄覆蓋，由于使用雷達(dá)種類(lèi)較多，不利于實(shí)施及維護(hù)。

3) 文獻(xiàn)[21]方法的優(yōu)化結(jié)果為近似最優(yōu)，本文方法計(jì)算的布站結(jié)果是最優(yōu)。

4) 本文進(jìn)一步提出了基本布站模式中接收器個(gè)數(shù)上限閾值的計(jì)算方法。

1 多基地雷達(dá)基本概念與問(wèn)題描述

1.1 多基地雷達(dá)覆蓋區(qū)域模型

設(shè)、分別表示雷達(dá)發(fā)射器與接收器，其組成的雙基地雷達(dá)記為(,)，位于點(diǎn)處的目標(biāo)信噪比()為

(1)

圖2 基本布站模式Fig.2 Basic deployment patterns

目標(biāo)在點(diǎn)處可能被多組雙基地雷達(dá)探測(cè)到，記該點(diǎn)的最大噪聲比為()，即有

(2)

式中：由發(fā)射器所確定的常數(shù)。因此，點(diǎn)處的目標(biāo)能被多基地雷達(dá)覆蓋的充分必要條件是()≥。

若發(fā)射器與發(fā)射器發(fā)射功率相同，記為=；若發(fā)射器的功率大于發(fā)射器，記為>。同時(shí)假設(shè)所有接收器相同，布站成本一樣，用、分別表示發(fā)射器與接收器的成本，設(shè)=為發(fā)射器與接收器成本之比。實(shí)際應(yīng)用中發(fā)射器成本高于接收器，因此有>1。

1.2 直線(xiàn)柵欄覆蓋的基本概念

假設(shè)雷達(dá)傳感器網(wǎng)絡(luò)中所有發(fā)射器、接收器均部署在直線(xiàn)段上，以形成直線(xiàn)柵欄覆蓋。那么對(duì)于直線(xiàn)段上任一點(diǎn)，滿(mǎn)足()≥，?∈, 直線(xiàn)段被稱(chēng)為布站線(xiàn)。此時(shí)所有穿越直線(xiàn)段的目標(biāo)均可以被多基地雷達(dá)網(wǎng)絡(luò)探測(cè)到。不失一般性，在直線(xiàn)段上從左到右依次部署發(fā)射器和接收器。同時(shí)，為了充分發(fā)揮發(fā)射器的作用，布站線(xiàn)的左右兩端均部署接收器，如圖3所示。

圖3 HMMR直線(xiàn)柵欄覆蓋示意圖Fig.3 HMMR linear barrier coverage diagram

圖4 模式中發(fā)射器耦合度(Tj>Ti)Fig.4 Transmitter coupling degree of

1.3 直線(xiàn)柵欄覆蓋問(wèn)題描述

圖5中，布站線(xiàn)左端點(diǎn)為數(shù)軸的原點(diǎn)，布站限制區(qū)寬度‖‖=，限制區(qū)將布站線(xiàn)分為和兩段，長(zhǎng)度分別記為、。

圖5 布站線(xiàn)示意圖Fig.5 Deployment diagram

因此問(wèn)題可表述為：在有約束的布站線(xiàn)上采用1個(gè)異構(gòu)發(fā)射器和若干同構(gòu)發(fā)射器及接收器構(gòu)建直線(xiàn)柵欄覆蓋，上任意一點(diǎn)均處于雷達(dá)網(wǎng)絡(luò)的覆蓋范圍內(nèi)。在總布站成本最小的準(zhǔn)則下優(yōu)化布站節(jié)點(diǎn)的位置和數(shù)量。相應(yīng)的模型為

min++
s.t.()≥,?∈,=+
=,,?(,),=1,…,

(3)

2 最優(yōu)柵欄覆蓋序列的特征與優(yōu)化模型

2.1 基本模式覆蓋長(zhǎng)度的計(jì)算及性質(zhì)

(4)

(5)

式中：「?表示向上取整。

以下進(jìn)一步給出柵欄覆蓋長(zhǎng)度的計(jì)算公式及主要證明過(guò)程。

211 覆蓋長(zhǎng)度計(jì)算公式

(6)

(7)

(8)

結(jié)論1和結(jié)論2可通過(guò)簡(jiǎn)單的代數(shù)運(yùn)算證明，過(guò)程從略。

進(jìn)一步，構(gòu)建HTMR覆蓋長(zhǎng)度增幅序列{|=(+1)-()}，由(8)式可以證明該序列具有單調(diào)遞減性。該特點(diǎn)說(shuō)明隨著接收器數(shù)量增加，HTMR覆蓋長(zhǎng)度也會(huì)增加，但是增加的幅度是遞減的。因此僅通過(guò)增加接收器來(lái)增加覆蓋長(zhǎng)度的方法不是最優(yōu)的。同理可構(gòu)造HMMR覆蓋長(zhǎng)度序列{|=(+1)-()}，該序列也是單調(diào)遞減序列，即通過(guò)增加接收器來(lái)增加HMMR覆蓋長(zhǎng)度的方法也不是最優(yōu)的。因此需要研究覆蓋長(zhǎng)度的性質(zhì)，確定最優(yōu)布站方法。

212 HMMR模式的性質(zhì)

設(shè),為自然數(shù)，如下結(jié)論成立：

1)若+=2,則當(dāng)且僅當(dāng)=，或、均為連續(xù)奇數(shù)時(shí)，()+()取得最大值2()；

2)若+=2+1，則當(dāng)且僅當(dāng)|-|=1時(shí)，()+()取得最大值()+(+1)。

1) 不妨令=-，=+,為非負(fù)整數(shù)。當(dāng)、均為奇數(shù)時(shí)，分為奇數(shù)和偶數(shù)2種情況進(jìn)行證明。

②若為奇數(shù)，則為偶數(shù)，類(lèi)似可證明當(dāng)且僅當(dāng)=0，即、均為相等奇數(shù)時(shí)取得最大值。

在、均為偶數(shù)時(shí)，也分為奇數(shù)和偶數(shù)2種情況進(jìn)行證明。

其余情況可類(lèi)似證得結(jié)論1成立。

2) 不妨令=+1-,=+，為偶數(shù)，為奇數(shù)。類(lèi)似結(jié)論1的證明，可得結(jié)論2成立。由定理2可知(2+1)+(2-1)=2(2),這表明兩個(gè)同構(gòu)模式2-1與2+1覆蓋長(zhǎng)度之和可用2個(gè)相同的模式2等量替代。另一方面，模式2與2+2的覆蓋和不可用2個(gè)模式2+1替代，即(2)+(2+2)<2(2+1)。

設(shè)、為自然數(shù)， 若+為定值，那么，當(dāng)且僅當(dāng)|-2|≤1時(shí)，()+()的值最大。進(jìn)一步有，當(dāng)為奇數(shù)時(shí)，=(-1)2或=(+1)2；當(dāng)為偶數(shù)時(shí)，=2。

分3種情況進(jìn)行證明：①+=3+2;②+=3+1;③+=3。下面給出當(dāng)+=3+2時(shí)的證明過(guò)程，不妨令=2+1-,=+1+，則

同理可證，若+=3，則當(dāng)且僅當(dāng)=2，=時(shí)，()+()取最大值(2)+(),即=2。若+=3+1，則當(dāng)且僅當(dāng)=、=2+1時(shí)，()+()取最大值(2+1)+()，即=(-1)2。

定理2和3說(shuō)明了HMMR中最優(yōu)柵欄覆蓋序列的性質(zhì)，以下研究HTMR中最優(yōu)覆蓋序列性質(zhì)。

213 HTMR模式的性質(zhì)

(′)+(′)≤()+()

(9)

214 最優(yōu)柵欄覆蓋序列的基本結(jié)構(gòu)

2.2 布站問(wèn)題的優(yōu)化模型及其求解算法

模型M：

(10)

模型M的目標(biāo)函數(shù)中沒(méi)有顯含變量Δ，但目標(biāo)函數(shù)值的大小卻依賴(lài)于Δ。直接求解十分困難，因此本文提出分層分解的算法：第1層，模型M拆分為模型M-1、模型M-2及模型M-3；第2層，模型M-1,M-2再分別按照模型M-1-1、M-1-2拆分。

模型M-1:

式中:

(11)

模型M-2:

式中:

(12)

再求解以下優(yōu)化模型：

模型M-3:

(13)

由于優(yōu)化模型(11)式與優(yōu)化模型(12)式的求解算法類(lèi)似，下面以求解模型(11)式為例給出具體算法。

首先對(duì)給定的進(jìn)一步分解模型M-1，則有

模型M-1-1：

min{q(1)1,q(1)2,n′1,t(1)1,t(1)2}cn1=q(1)1(n1+α)+t(1)1n12+n1+q(1)2(n1+1+α)+t(1)2n1+12+αs.t. q(1)1σF(n1)+q(1)2σF(n1+1)+σF10(n′1)+t(1)1σP(n12)+t(1)2σP(n1+12)≥ξs1

(14)

由此可得模型(11)式的最優(yōu)解。綜上，本文模型分解過(guò)程如圖6所示，相應(yīng)的算法流程如圖7所示。

圖6 模型分解過(guò)程Fig.6 Model decomposition

圖7 算法流程圖Fig.7 Algorithm workflow

=?(-1)2」

(15)

具體算法步驟如圖8所示。

3： 對(duì)求解子優(yōu)化問(wèn)題(14)，得到HMMR模式中接收器個(gè)數(shù)為時(shí)，直線(xiàn)最優(yōu)覆蓋序列

優(yōu)化模型(13)式的求解算法如圖9所示。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)通過(guò)仿真實(shí)驗(yàn)來(lái)說(shuō)明所提方法的有效性與可行性。假設(shè)柵欄的長(zhǎng)度從100 km以步長(zhǎng)20 km增加到300 km，限制區(qū)的寬度為3 km，且其左右兩邊的布站線(xiàn)長(zhǎng)度分別為=67+10和=30+10,=0,…,10。不失一般性，設(shè)接收器的費(fèi)用=1元，在算法2中設(shè)置步長(zhǎng)為01 km。其他參數(shù)設(shè)置如表1所示。

表1 仿真試驗(yàn)參數(shù)設(shè)置

方案1柵欄長(zhǎng)度與布站費(fèi)用關(guān)系如圖10所示。由圖10可以看出，總費(fèi)用隨著柵欄長(zhǎng)度的增加而增加，且呈現(xiàn)近似線(xiàn)性關(guān)系。發(fā)射器的費(fèi)用總是大于

圖10 方案1柵欄長(zhǎng)度與布站費(fèi)用關(guān)系Fig.10 Barrier length versus deployment cost for Scheme 1

4： 初始化集合=?

5： for=1∶2

6：=()+Δ，=-

接收器的費(fèi)用，若發(fā)射器費(fèi)用增加幅度大，相應(yīng)地接收器費(fèi)用增加幅度就小，反之亦然。

方案1柵欄長(zhǎng)度與傳感器數(shù)量關(guān)系如圖11所示。由圖11可以看出，布站所用總節(jié)點(diǎn)數(shù)量、接收器數(shù)量和發(fā)射器數(shù)量隨柵欄長(zhǎng)度增加的變化趨勢(shì)?？偣?jié)點(diǎn)數(shù)量與接收器數(shù)量的變化趨勢(shì)一致，且變化幅度較大，而發(fā)射器數(shù)量的變化趨勢(shì)平緩，呈近似線(xiàn)性變化。這是因?yàn)榘l(fā)射器的費(fèi)用要遠(yuǎn)大于接收器的費(fèi)用，為了使布站費(fèi)用最小，盡可能多用較低費(fèi)用的接收器而少用發(fā)射器。當(dāng)然也不能僅通過(guò)增加接收器，定理1指出隨著接收器數(shù)量的增加，其覆蓋效果就越差，因此，需要優(yōu)化使用發(fā)射器與接收器才能使布站費(fèi)用最少。

圖11 方案1柵欄長(zhǎng)度與傳感器數(shù)量關(guān)系Fig.11 Barrier length versus number of sensors for Scheme 1

下面對(duì)方案2與方案1的優(yōu)化結(jié)果進(jìn)行比較。在方案2中，HTMR模式中發(fā)射器性能不變，而其余同構(gòu)雷達(dá)發(fā)射器的性能增強(qiáng)。相應(yīng)的布站總費(fèi)用、發(fā)射器、接收器費(fèi)用差如圖12所示(方案1費(fèi)用減方案2的相關(guān)費(fèi)用)。

圖12 方案1與方案2費(fèi)用差Fig.12 Cost difference between Scheme 1 and Scheme 2

圖12表明，與方案2相比，方案1消耗的總費(fèi)用、接收器費(fèi)用和發(fā)射器費(fèi)用普遍較少。這是由于方案2中HMMR發(fā)射器的成本更高，因此在方案2中更多使用了成本較低的接收器，少用了成本高的發(fā)射器，但是方案2中發(fā)射器的費(fèi)用仍高于方案1發(fā)射器的費(fèi)用。

方案3與方案1優(yōu)化結(jié)果的比較。在方案3中，發(fā)射器的性能增強(qiáng)，而其余發(fā)射器性能不變，相應(yīng)的布站總費(fèi)用、發(fā)射器、接收器費(fèi)用差如圖13所示(方案1費(fèi)用減去方案3的相關(guān)費(fèi)用)。

圖13 方案1與方案3費(fèi)用差示圖Fig.13 Cost difference between Scheme 1 and Scheme 3

由圖13可知，方案1比方案3節(jié)省費(fèi)用，但節(jié)省的數(shù)量不大，且不隨柵欄的長(zhǎng)度變化而改變。這是由于兩個(gè)方案的差別僅在于一個(gè)異構(gòu)的發(fā)射器，方案3中異構(gòu)雷達(dá)發(fā)射器的探測(cè)性能增強(qiáng)了，而其余的發(fā)射器探測(cè)性能相同。發(fā)射器費(fèi)用及接收器費(fèi)用隨著柵欄長(zhǎng)度的改變而變化，但二者呈現(xiàn)出此消彼長(zhǎng)的趨勢(shì)。

在仿真實(shí)驗(yàn)中，假設(shè)雷達(dá)的探測(cè)閾值與雷達(dá)的費(fèi)用為近似線(xiàn)性關(guān)系，在實(shí)際應(yīng)用中可根據(jù)實(shí)際情況進(jìn)行調(diào)整。

仿真實(shí)驗(yàn)表明，布站總費(fèi)會(huì)隨采取的布站方案不同而改變。因此在有多種雷達(dá)可選擇的條件下，參考本文方法進(jìn)行仿真，有助于選擇最經(jīng)濟(jì)的布站方案。

下面以柵欄長(zhǎng)度=180 km(其中限制區(qū)寬度等于3 km，=107 km，=70 km)為例給出以上 3種方案的具體布站序列。

4 結(jié)論

本文在雷達(dá)布站位置受限的情況下，討論了一種直線(xiàn)柵欄覆蓋的優(yōu)化布站方法。本文假設(shè)當(dāng)有一對(duì)雷達(dá)的布站位置受限制的情況，在尋找兩個(gè)柵欄覆蓋分界點(diǎn)(即發(fā)射器的布站位置)時(shí)，由于是在一維區(qū)間，故采用定步長(zhǎng)的一維搜索方法。從本文的仿真結(jié)果看出，利用本文所提方法，在實(shí)際應(yīng)用中可以準(zhǔn)備多種不同的雷達(dá)布站方案，從中選擇成本最小的方案作為最終的布站結(jié)果。最優(yōu)的柵欄覆蓋布站方法往往與實(shí)際場(chǎng)景密切相關(guān)，如無(wú)法構(gòu)建直線(xiàn)柵欄覆蓋，而用若干段直線(xiàn)構(gòu)成的折線(xiàn)柵欄覆蓋；或跨越多條河流的直線(xiàn)柵欄等等。本文所構(gòu)建的數(shù)學(xué)模型與布站方法可以拓展到這些雷達(dá)布站位置受限制的情況，此時(shí)優(yōu)化模型的復(fù)雜度增大，相應(yīng)求解算法的難度會(huì)顯著增大，這種情況下，定步長(zhǎng)搜索方法效率低，需要采用其他的優(yōu)化算法進(jìn)行求解，如智能算法中的遺傳算法、蟻群算法、鯨魚(yú)優(yōu)化算法、哈里斯鷹優(yōu)化算法等等。