杜文占，余志勇，楊 劍，姜海濱

(1.火箭軍工程大學(xué) 302教研室，陜西 西安 710025；2.火箭軍工程大學(xué) 205教研室，陜西 西安 710025)

地面電磁輻射源監(jiān)測裝備的高效部署是全面可靠地感知電磁環(huán)境的基礎(chǔ)。然而，地形復(fù)雜，建筑物、樹木等障礙物分布雜亂，電磁信號可能被反射、散射和衍射，從而在傳輸路徑上消散，對輻射源信號監(jiān)測造成不利影響。MALON等[1]結(jié)合城市地形特點，以天線之間的距離為約束條件，給出了檢測參數(shù)、天線數(shù)量和距離約束對監(jiān)測裝備準(zhǔn)確性的影響。文獻(xiàn)[2]提出了一種新的分布式并行多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithms，MOEAs)解決傳感器網(wǎng)絡(luò)在城市三維地形中智能部署的問題，并通過實際地形對該算法進(jìn)行了驗證。文獻(xiàn)[3]將協(xié)同監(jiān)測模型的多個指標(biāo)歸一化為一個綜合評估指標(biāo)，可靠性較低。陳濤等[4]提出了基于地理信息系統(tǒng)(Geographic Information System，GIS)的優(yōu)化部署策略，根據(jù)地形復(fù)雜情況布設(shè)不同數(shù)量的電磁監(jiān)測裝備，有效避免了多徑效應(yīng)的影響，但覆蓋冗余率過高。基于自適應(yīng)遺傳算法[5-6]將天線部署作為協(xié)同優(yōu)化問題，對監(jiān)測站覆蓋范圍和站點布局規(guī)劃進(jìn)行仿真，提高了電磁監(jiān)測裝備的覆蓋率，但沒有考慮障礙物對監(jiān)測準(zhǔn)確性的影響。

在大多數(shù)的研究中，地面天線的部署優(yōu)化主要考慮靜態(tài)環(huán)境下的覆蓋率最大化，很少有針對避免障礙物影響和動態(tài)環(huán)境下高效部署的研究。當(dāng)部署區(qū)域、天線位置等發(fā)生改變時，算法收斂的速度決定著天線重新部署的效率，因此需要提高算法響應(yīng)動態(tài)變化的能力[7]。筆者以最大化覆蓋率、最小化冗余率和覆蓋區(qū)域內(nèi)障礙物為目標(biāo)構(gòu)建模型，并通過改進(jìn)NSGA-II算法在不同參考點數(shù)量和不同部署區(qū)域下分別對該模型進(jìn)行了仿真分析。

1 問題描述

覆蓋率和冗余率是評價監(jiān)測天線部署效率的重要指標(biāo)。實際地形中障礙物的存在會對天線的準(zhǔn)確監(jiān)測造成嚴(yán)重影響。戰(zhàn)場環(huán)境中高溫、噪音、氣候變化等問題，干擾數(shù)據(jù)傳輸，導(dǎo)致鏈路斷裂。因此，在部署時需要保證每兩個天線間至少有一條通信鏈路并且具有較強的連接能力和可靠性。在本節(jié)中對目標(biāo)函數(shù)和約束條件進(jìn)行了介紹。

1.1 障礙物

在復(fù)雜的戰(zhàn)場電磁環(huán)境下，電磁波難以在輻射源和監(jiān)測天線之間直線傳播。在傳播過程中遇到障礙物(如建筑物、樹木)時，輻射源信號被反射、散射、衍射或吸收。地理環(huán)境是一種客觀存在，不同的地形地貌，如平原、丘陵、山地等影響著地面對電磁波的吸收或反射。當(dāng)障礙物表面平滑且尺寸比信號波長大得多時，信號就會在障礙物表面發(fā)生反射或折射；當(dāng)障礙物尺寸與信號波長相似或更小時，信號就會繞過障礙物繼續(xù)傳播，形成繞射。

是否存在障礙物、障礙物是否連續(xù)、障礙物相比于電磁波波長的大小等因素引起的多徑效應(yīng)(Multipath Propagation)會對監(jiān)測天線相位和幅度產(chǎn)生影響，導(dǎo)致監(jiān)測結(jié)果產(chǎn)生偏差甚至突變。文獻(xiàn)[8]提出了估計輻射源和監(jiān)測天線之間功率損耗的無線傳播模型

(1)

其中，Lpl為輻射功率的路徑損耗；μ∈[2，5]為路徑損耗系數(shù)，自由空間中，μ=2，其他環(huán)境中，2<μ<5；d是發(fā)射源到接收端的直接路徑距離；K為直接路徑上障礙物的數(shù)量；α(i)和β(i)∈[0，1]分別為障礙物i的衰減指數(shù)和滲透率。β(i)i-1表明天線和障礙物之間的距離越小，對監(jiān)測準(zhǔn)確度的影響就越大。因此，在監(jiān)測天線覆蓋區(qū)域內(nèi)的障礙物數(shù)量K越少，對準(zhǔn)確監(jiān)測輻射源的影響就越小。

1.2 覆蓋率和冗余率

最大化天線覆蓋率是有效監(jiān)測未知位置的電磁輻射源的重要前提。假設(shè)每個天線的監(jiān)測覆蓋范圍是一個半徑為最大監(jiān)測距離的圓，則檢測概率可以定義為一個二元感知模型[9]，如式(2)所示。假設(shè)監(jiān)測天線數(shù)量為M，潛在輻射源數(shù)量為N，天線增益為0 dBi，則天線(m)監(jiān)測到輻射源(n)信號的結(jié)果為

(2)

其中，rx為監(jiān)測天線正確檢測信號的信號強度，tx為輻射源信號強度，Lpl(m，n)為輻射源和監(jiān)測天線間的路徑損耗。

如圖1所示，陰影部分面積為

圖1 計算陰影部分面積

SCBD=SACBD-SACD

(3)

其中，SACBD為扇形ACBD的面積，SACD為三角形ACD的面積。

計算冗余率，如式(4)所示，

(4)

其中，R為天線最大監(jiān)測距離；t為lAB<2R情況的個數(shù)，lAB為天線A和B之間的距離。

根據(jù)式(5)計算覆蓋率O，其中SROI為部署區(qū)域面積。

(5)

1.3 天線連通性

在M>1的情況下，天線需要交換數(shù)據(jù)，相互之間必須能夠無線通信，形成監(jiān)測網(wǎng)絡(luò)以獲得電磁態(tài)勢評估。監(jiān)測天線和輻射源的示例如圖2所示。

圖2 測向天線和輻射源示例圖

文獻(xiàn)[1]中給出式(6)計算兩個天線相互通信的能力：

(6)

其中，ry為監(jiān)測天線m1接收信號強度，ty為監(jiān)測天線m2發(fā)射信號強度，Lpl(m1，m2)為m1與m2之間的路徑損耗。

部署M個天線時，根據(jù)式(7)計算天線間保持通信的平均連接距離：

(7)

其中，lm1m2為具有連通性的兩個天線m1與m2間的距離，Ml表示天線間具有連通性的通信鏈路個數(shù)，lmax為最大通信距離。

1.4 多目標(biāo)優(yōu)化模型

多目標(biāo)優(yōu)化問題中的目標(biāo)之間存在矛盾沖突，無法保證每個目標(biāo)同時達(dá)到最佳值，即不存在能使所有目標(biāo)都為最優(yōu)的解，因此，解決方案將會是在均衡所有目標(biāo)的基礎(chǔ)上尋求最接近最優(yōu)解的解。

在動態(tài)多目標(biāo)優(yōu)化問題(Dynamic Multi-objective Optimization Problem，DMOP)中，目標(biāo)、約束或參數(shù)隨時間而變化，動態(tài)帕累托最優(yōu)前沿(Pareto Optimal Front，POF)和帕累托最優(yōu)解集(Pareto Optimal Solution，POS)分別是關(guān)于目標(biāo)空間和決策空間的非支配解的集合。當(dāng)環(huán)境改變并且被檢測到時，通常POS或POF也發(fā)生變化，影響DMOP的現(xiàn)有解決方案，所以目標(biāo)是跟蹤動態(tài)POF或POS。因此，必須提高算法收斂速度，在下一次改變發(fā)生前，盡快找到新部署方案。

多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型為

(8)

決策變量為天線部署位置坐標(biāo)，如下所示：

X=[(x1，y1)，(x2，y2)，…，(xm，ym)]T，(xi，yi)∈ROI，i=1，2，…，M，

(9)

其中，決策空間ROI(Region of Interest)為監(jiān)測天線部署區(qū)域，上標(biāo)T表示矩陣的轉(zhuǎn)置。

2 改進(jìn)NSGA-II算法

NSGA-II算法，即帶有精英保留策略的快速非支配多目標(biāo)優(yōu)化算法，是一種基于Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法。本節(jié)介紹了通過預(yù)先設(shè)定帶有偏好的參考點和利用內(nèi)存保留最優(yōu)解的方法改進(jìn)的NSGA-II算法。

2.1 NSGA-II算法

2000年DEB等[10]提出第2代非支配排序遺傳算法(NSGA-II)。該算法采用快速非支配排序降低計算復(fù)雜度，利用擁擠度及比較算子代替共享半徑，引入精英策略擴(kuò)大采樣空間，提高了魯棒性和運算速度。文獻(xiàn)[11]提出了一種基于參考點的NSGA-III算法，該算法遵循NSGA-II框架，將若干均勻分布的理想點設(shè)為參考點。通過提供和自適應(yīng)更新一些分布良好的參考點替換擁擠距離算子，來維持種群成員之間的多樣性。在解決3個目標(biāo)以上的多目標(biāo)優(yōu)化問題中取得了很好的效果[12]。文獻(xiàn)[13]針對動態(tài)環(huán)境下的多目標(biāo)進(jìn)化問題設(shè)計了新的動態(tài)和遷移策略，提高了算法收斂速度，但復(fù)雜度依然較大。

2.2 預(yù)設(shè)參考點

假設(shè)每個天線向周圍均勻監(jiān)測輻射源信號且最大監(jiān)測半徑R相同。通過計算障礙物之間的距離s，并比較s與R的大小來預(yù)先設(shè)定帶有偏好的參考點作為天線的部署位置，流程如圖3所示。

圖3 預(yù)設(shè)參考點流程圖

首先，輸入監(jiān)測區(qū)域ROI的范圍，即天線數(shù)量M和監(jiān)測覆蓋范圍最大半徑R，障礙物數(shù)量K和位置坐標(biāo)，天線間保持通信的最大距離lmax；然后，計算每兩個障礙物之間的距離s，并按照從小到大的順序排序，判斷si與2R的關(guān)系，進(jìn)而確定參考點數(shù)量和位置坐標(biāo)。

在保證覆蓋率的前提下，障礙物在天線覆蓋范圍邊緣時對其正常工作的影響最小。如圖4所示，實心三角形為障礙物，實心圓形為參考點，天線監(jiān)測覆蓋范圍(實心圓)最大半徑為R，兩個障礙物之間的距離為s，虛線圓是以障礙物為圓心、R為半徑的圓。

當(dāng)0

圖4 不同情況下參考點位置

當(dāng)s=2R時，如圖4(b)所示，虛線圓有一個交點，設(shè)為參考點，兩個障礙物都位于天線覆蓋范圍邊緣上，對監(jiān)測范圍內(nèi)的準(zhǔn)確監(jiān)測影響最小。如果參考點設(shè)在障礙物1的虛線圓的其它位置上，那么在部署第2個天線使障礙物2位于其覆蓋范圍邊緣時，會導(dǎo)致覆蓋率減小和冗余率增大，并且需要部署兩個天線才能避免兩個障礙物的影響，增加成本；如果保證最大覆蓋率和最小冗余率時，將導(dǎo)致障礙物2位于該天線監(jiān)測覆蓋范圍內(nèi)，監(jiān)測準(zhǔn)確性變差。

當(dāng)s>2R時，虛線圓沒有交點，虛線圓上任意位置都可以設(shè)為參考點。如圖4(c)所示，如果s<4R，則選取參考點位置時要避免覆蓋冗余，兩個實心圓相切時部署效率最高。如果s≥4R，則參考點位置沒有限制，如圖4(d)所示。

2.3 更新存儲種群

為了增強NSGA-II算法在動態(tài)環(huán)境下跟蹤非支配解的能力，在算法中使用顯式內(nèi)存來存儲每一代的最佳解。每當(dāng)發(fā)生環(huán)境改變時，搜索種群將隨機(jī)重新初始化并為存儲種群提供最優(yōu)解；主種群從存儲種群中得到非支配個體并對其更新。

在基于內(nèi)存存儲的NSGA-II算法中，存儲種群的更新過程非常重要，它直接影響算法的性能。更新存儲種群的流程如圖5所示。存儲種群的種群大小為K，索引j初始值為1。獲取當(dāng)前父代種群P(N)，并對其非支配排序。當(dāng)內(nèi)存不滿時，非支配解FP(j)直接添加到存儲種群中。當(dāng)內(nèi)存滿后，根據(jù)擁擠距離的概念[10]求解最小歐氏距離，得到每個非支配個體到存儲種群的最近解。如果新的非支配解比它的最近解更優(yōu)，則替換這兩個解；否則，存儲種群保持不變。

圖5 更新存儲種群

2.4 算法流程

加入預(yù)設(shè)參考點和更新存儲種群子流程后的改進(jìn)NSGA-II算法(MB-NSGA-II)得到下一代種群Pt+1的流程如圖6所示。程序運行前首先預(yù)設(shè)參考點，隨機(jī)初始化搜索種群S、父種群P和子種群Q，種群大小為N。存儲種群M大小為空。在達(dá)到迭代次數(shù)前的每一代種群中，算法都會檢查環(huán)境是否發(fā)生了變化。如果環(huán)境沒有變化，合并種群P和Q得到種群大小為2N的種群R。如果發(fā)生變化，重新預(yù)設(shè)參考點并隨機(jī)初始化搜索種群，合并種群P、Q和存儲種群M，得到大小為2N+K的種群R。

圖6 主程序流程圖

經(jīng)過非支配排序的種群R從F1開始，逐次將各非支配層(F1，F(xiàn)2，…)的解添加到種群Pt中，直至Pt的種群大小首次等于N或大于N。假設(shè)在最后添加的非支配層是Fl，如果Pt的種群大小正好為N，則直接輸出Pt+1=Pt；否則首先將前Fl-1個支配層的所有解添加到種群Pt+1，然后利用小生境算法[14]選取Fl中的前K個解添加到Pt+1中，得到大小為N的Pt+1。Pt+1經(jīng)過重組和變異得到種群Qt+1。對合并后的搜索種群S和存儲種群M非支配排序，得到合并種群的最優(yōu)非支配解的個數(shù)K，作為種群M的種群大小。在滿足更新條件時更新種群M。將該條件設(shè)定為迭代次數(shù)x，即每迭代x次則更新一次種群M。

3 實驗仿真及分析

實驗所用計算機(jī)型號為HP Z800 Workstation。處理器為Intel(R)Xeon(R)CPU X5675@3.07 GHz(2處理器)，安裝內(nèi)存(RAM)為12.0 GB；仿真軟件為MATLAB 2016a版本。需要輸入的參數(shù)及其數(shù)值如表1所示。

表1 輸入?yún)?shù)

6個障礙物坐標(biāo)分別為(172，50)、(159，463)、(367，361)、(244，200)、(411，73)、(485，470)。得到參考點和天線部署位置如圖7所示，部署結(jié)果數(shù)據(jù)如表2所示。

表2 部署結(jié)果數(shù)據(jù)

圖7(a)中4個參考點坐標(biāo)分別為(158，149)、(258，101)、(385.6，459.3)和(466.4，371.7)，其中，K為障礙物數(shù)量，C為參考點數(shù)量。圖7(b)中18條直線段表示天線間的通信鏈路，平均通信距離為165.15 m，覆蓋率為93.89%，冗余率為18.10%。部署效率表示平均每個天線有效監(jiān)測覆蓋范圍為21 339 m2，平均迭代一次的時間為1 297.9 s，有5個障礙物完全不在天線覆蓋區(qū)域內(nèi)。

將障礙物4的坐標(biāo)改為(96，255)，得到參考點和天線部署位置如圖8所示，部署結(jié)果數(shù)據(jù)如表2所示。其中，兩個參考點坐標(biāo)分別為(385.6，459.3)和(466.4，371.7)，共有18條通信鏈路，平均通信距離為164.81 m。未被覆蓋障礙物數(shù)量3/0個表示有3個障礙物完全未被覆蓋：障礙物1位于天線4和10的覆蓋范圍邊緣交點處，障礙物3位于天線1、2和7的覆蓋范圍邊緣交點處；障礙物6位于天線1和2的覆蓋范圍邊緣交點處。

圖8 K=6，C=2時參考點和天線部署位置

參考點數(shù)量C=2時的算法平均迭代一次的時間是C=4時的1.18倍，原因是在部署優(yōu)化過程中，天線位置是決策變量，在天線數(shù)量一定的情況下，預(yù)設(shè)的作為天線位置的參考點越少，則作為決策變量的未知部署位置的天線數(shù)量的個數(shù)越多，所以求解時間更長。

當(dāng)算法迭代60次時隨機(jī)改變障礙物數(shù)量和位置：7個障礙物坐標(biāo)分別為(63，117)、(112，369)、(423，71)、(205，374)、(411，483)、(243，166)和(470，280)，得到參考點和天線部署位置如圖9所示。4個參考點坐標(biāo)分別為(153.7，459.9)、(163.3，283.1)、(143.5，176.3)、(182.5，106.7)，共有21條通信鏈路，平均通信距離為131.91m。部署結(jié)果數(shù)據(jù)如表2所示，平均迭代一次的時間比K=6時降低了25.43%。這是因為決策變量始終是除了4個參考點外余下的7個天線的部署位置，改進(jìn)算法MB-NSGA-II中利用存儲種群存儲K=6時的非支配個體，在改變環(huán)境后重新部署天線位置時從存儲種群中選取最優(yōu)個體可以更快地找到Pareto解。

圖9 K=7，C=4時參考點和天線部署位置

由表2可知，在部署天線數(shù)量一定的情況下，障礙物數(shù)量相同時，參考點數(shù)量越多，則覆蓋率越小，冗余率越大，平均迭代一次的時間越短。這是因為參考點作為天線部署位置在尋求最優(yōu)解前已經(jīng)確定了坐標(biāo)，導(dǎo)致部署其它天線時不可避免地造成冗余率的增加和覆蓋率的減少；但同時參考點數(shù)量越多，則未確定位置的天線數(shù)量越少，求解速度更快。參考點數(shù)量相同時，障礙物數(shù)量越多，則覆蓋率越小，冗余率越大。K=7時的冗余率是K=6時的1.54倍，說明以未被覆蓋障礙物數(shù)量作為優(yōu)化多目標(biāo)之一時，障礙物的數(shù)量對冗余率的影響很大。

算法評價指標(biāo)(the mean Inverted Generational Distance just Before the change，mIGDB)量EmIGDB可以用來計算發(fā)生下次變化前平均反轉(zhuǎn)世代距離[15]。該指標(biāo)量EmIGDB計算代價小，可同時評價算法收斂性和多樣性。EmIGDB值越小，說明算法綜合性能越好。該指標(biāo)計算方法為

(10)

其中，EIGDt為只計算下次改變前的反轉(zhuǎn)世代距離，n為變化次數(shù)。

當(dāng)沒有發(fā)生環(huán)境變化時，利用(the mean Inverted Generational Distance，mIGD)量EmIGD評價算法的收斂性和多樣性。該指標(biāo)EmIGD計算方法為

(11)

其中，Gn是迭代次數(shù)，EIGDt為反轉(zhuǎn)世代距離。

依托多目標(biāo)優(yōu)化平臺PlatEMO[16]，在不同障礙物和參考點數(shù)量的情況下運行MB-NSGA-II或NSGA-II算法，得到EmIGD(或EmIGDB)指標(biāo)量隨迭代次數(shù)變化的結(jié)果如圖10所示。當(dāng)收斂條件為EmIGDB=0.2時，4種情況下算法收斂時的迭代次數(shù)X和平均迭代一次的時間t如表3所示。當(dāng)K=7，C=4時，從存儲種群中選取最優(yōu)個體，收斂速度最快且平均迭代一次的時間最短，3種方法都比NSGA-II算法收斂速度更快，說明應(yīng)用預(yù)設(shè)參考點的方法可以有效減少迭代次數(shù)和時間。

圖10 不同條件下的EmIGD指標(biāo)量隨迭代次數(shù)的變化情況

表3 算法性能比較

在部署天線數(shù)量和障礙物數(shù)量一定時，參考點數(shù)量越多，算法收斂的越快，平均迭代一次的時間越短；應(yīng)用MB-NSGA-II算法可以有效減少算法收斂的迭代次數(shù)和迭代時間。

4 結(jié)束語

障礙物對地面天線監(jiān)測電磁輻射源信號的準(zhǔn)確性帶來不利影響，筆者針對此問題構(gòu)建了以覆蓋率、冗余率、未被覆蓋障礙物數(shù)量為目標(biāo)的多目標(biāo)優(yōu)化模型。通過判斷障礙物間距離與天線監(jiān)測覆蓋范圍最大半徑的大小關(guān)系來預(yù)先設(shè)定參考點作為若干天線的部署位置。通過仿真驗證了以增加冗余率為代價可以有效減少天線覆蓋范圍內(nèi)的障礙物數(shù)量：K=6時，5個障礙物都未被覆蓋；K=7時，4個障礙物未被覆蓋。比較了不同參考點數(shù)量對冗余率和收斂時迭代次數(shù)等部署結(jié)果的影響。預(yù)設(shè)的參考點越多，收斂速度越快，但冗余率也會增加。利用存儲種群存儲前幾代非支配解的方法改進(jìn)NSGA-II算法，在改變障礙物數(shù)量和位置后，可以快速找到新的最優(yōu)解，求解速度是原來的74.57%。通過mIGDB算法評價指標(biāo)驗證了改進(jìn)算法MB-NSGA-II相比于NSGA-II算法可以提高部署效率和算法收斂速度。

下一步工作將針對算法檢測環(huán)境變化的實時性和優(yōu)化存儲種群的更新策略進(jìn)行深入研究。