劉子宸，曲俊海，馬躍東

（北方自動控制技術(shù)研究所，太原 030006）

0 引言

在未來高動態(tài)、強對抗和不確定任務(wù)的無人化陸戰(zhàn)場，以異構(gòu)無人作戰(zhàn)平臺結(jié)合有人裝備的有人/無人混合編隊，將成為執(zhí)行區(qū)域作戰(zhàn)任務(wù)的主要力量。有人/無人混合編隊處于作戰(zhàn)的最前沿地帶，對接敵區(qū)域的偵察和封控尤為重要。如何將編隊中各異構(gòu)有人/無人平臺攜帶的可見光、紅外、雷達等多型偵察裝備進行最優(yōu)化的協(xié)同偵察部署，使得各平臺在最短時間內(nèi)，經(jīng)過最短的移動距離，同時規(guī)避陷阱和懸崖等不可到達區(qū)域，實現(xiàn)復(fù)雜目標區(qū)域的全域偵察監(jiān)視或多頻譜覆蓋，從而有效提升目標發(fā)現(xiàn)概率，發(fā)揮偵察裝備的最大效能，成為一個亟待解決的問題。

針對多傳感器的區(qū)域部署任務(wù)規(guī)劃問題，當前的技術(shù)途徑主要包括基于數(shù)學(xué)規(guī)劃的多約束問題、專家系統(tǒng)、基于智能算法的啟發(fā)式搜索等方法。近年來，啟發(fā)式搜索算法發(fā)展迅速，原理簡單且在收斂速度上優(yōu)勢明顯，其中，對PSO 算法的改進研究最為廣泛。文獻［9］提出一種改進的PSOSA算法，對初始隨機分布的移動傳感器進行重新部署，以獲得最優(yōu)的覆蓋效果。文獻［10］引入模擬退火方法改進粒子群算法，通過限制原始粒子和新粒子在迭代過程中的位置變化，可有效改善算法的收斂速度。文獻［11］在標準粒子群算法的基礎(chǔ)上引入模糊數(shù)學(xué)的思想，能夠在傳感器部分加入和全部加入兩種情況下均取得較好的覆蓋效果。文獻［12］提出一種基于多目標局部變異- 自適應(yīng)量子粒子群優(yōu)化（LM-AQPSO）算法，對復(fù)雜地形環(huán)境下的多傳感器部署問題進行研究，構(gòu)建了多傳感器多目標優(yōu)化部署模型。

當前的研究主要針對同種類型的多個傳感器，部署區(qū)域為規(guī)則的正方形區(qū)域，未考慮異構(gòu)傳感器在任意不規(guī)則的凸/凹多邊形區(qū)域的最優(yōu)化部署問題，因此，在實際應(yīng)用中受到了一定限制。

針對未來無人化陸戰(zhàn)場有人/無人混合編隊中異構(gòu)平臺攜帶的多型偵察裝備的協(xié)同偵察部署問題，本文提出了自適應(yīng)粒子群- 區(qū)域最優(yōu)匹配（PSO-ROM）算法。采用參數(shù)自適應(yīng)和局部變異方法對粒子群優(yōu)化算法進行改進，對異構(gòu)平臺中探測性能最優(yōu)的多個同類型傳感器進行優(yōu)化部署；依次針對異構(gòu)平臺中的多個其他類型傳感器，采用區(qū)域最優(yōu)匹配算法對尚未覆蓋的空白區(qū)域進行優(yōu)化部署，直至達到偵察部署目標。基于PSO-ROM 算法不僅可用于異構(gòu)無人平臺不規(guī)則區(qū)域協(xié)同偵察部署問題，還可實現(xiàn)重點區(qū)域的多頻譜覆蓋，提升偵察探測效能。

1 問題描述

1.1 地形模型

在實際作戰(zhàn)任務(wù)中，待偵察區(qū)域多為不規(guī)則的多邊形起伏區(qū)域。與理想的平坦區(qū)域相比，起伏區(qū)域表面由于存在電磁波的反射和吸收等現(xiàn)象，平臺所攜帶傳感器的偵察探測范圍將受到不同程度的影響。根據(jù)表1 所示的地形起伏度標準，結(jié)合平臺傳感器在開展偵察時升高幅度等因素，本文研究的偵察部署算法適用場景為：海拔高度低于400 m，局部地勢（16 km內(nèi)高差）低于75 m 的低平起伏與和緩起伏的平原、丘陵和高原等地形。

表1 地形起伏度標準

為簡化地形模型，將協(xié)同偵察目標區(qū)域建模為任意多邊形區(qū)域，可分為凸多邊形和凹多邊形區(qū)域兩種情況，典型的凹/凸多邊形任務(wù)區(qū)域示例如下頁圖1 所示。有人/無人混合編隊集結(jié)區(qū)域（圖中綠色圓形區(qū)域）的圓心位于坐標原點，多邊形區(qū)域內(nèi)的“*”代表陷阱、障礙等不可到達/部署位置。

圖1 邊界復(fù)雜的典型多邊形搜索任務(wù)區(qū)域示例

1.2 傳感器探測模型

針對不同的探測需求，有人/無人混合編隊各平臺攜帶了多種傳感器，主要分為可見光、紅外、雷達等類型。各傳感器的探測半徑會因氣候條件和能見度的差異而有所不同。假定在理想的能見度條件下，異構(gòu)傳感器的探測能力如表2 所示。

表2 傳感器參數(shù)模型

為了簡化，本文中的傳感器覆蓋感知模型采用二元感知模型，即以傳感器位置p 為圓心，探測半徑為r 的圓。r 的大小根據(jù)傳感器的性能而定，在圓內(nèi)所有位置的探測概率是一致的，傳感器在p 點對目標點q 的探測概率g（p，q）可表示為：

其中，d（p，q）為p 點和q 點之間的直線距離。

1.3 目標函數(shù)

異構(gòu)多傳感器的協(xié)同偵察部署屬于典型的多目標優(yōu)化問題，包含以下優(yōu)化目標：1）搜索覆蓋率R：即多傳感器部署完成后，對任務(wù)區(qū)域的覆蓋率，覆蓋率越高越好。在重點區(qū)域多頻譜覆蓋中，多頻譜傳感器的覆蓋率同樣越高越好。2）傳感器數(shù)量N：由于傳感器數(shù)量有限，因此，在達到區(qū)域偵察覆蓋目標的前提下，使用的傳感器數(shù)量越少越好。3）平均移動距離L：由于無人車存在續(xù)航問題，車輛從集結(jié)地到達部署目標位置的平均移動距離越短越好。本文不考慮基于路網(wǎng)信息的有人車/無人車路徑規(guī)劃問題，因此，平均移動距離L 取集結(jié)地到最終部署位置的直線距離。

綜上所述，目標函數(shù)為：

式中，α 和β 為權(quán)重因子，可根據(jù)實際作戰(zhàn)任務(wù)需求及各有人/無人平臺油/電剩余量及續(xù)航狀態(tài)進行設(shè)置。

2 自適應(yīng)粒子群- 區(qū)域最優(yōu)匹配（PSO-ROM）算法

本文用覆蓋比F 來表征待部署傳感器資源相

采用PSO-ROM 算法的異構(gòu)多傳感器部署流程如圖2 所示，R為任務(wù)要求達到的最低覆蓋率；Z為待部署傳感器的類型數(shù)量；k 為當前正在部署的傳感器類型（k=1，2，…，Z）。在讀取任務(wù)信息、地圖信息和傳感器資源信息后，首先判斷覆蓋比F 是否高于任務(wù)要求達到的最低覆蓋率R，如果是，則進行下一步；否則，表明傳感器資源無論在何種條件下都不足以滿足任務(wù)要求，因此，跳出流程。然后，基于任務(wù)需求與無人平臺資源狀態(tài)設(shè)置目標函數(shù)的權(quán)重因子。對異構(gòu)平臺攜帶的探測性能最優(yōu)的多個k 型傳感器（k=1），使用改進的PSO 算法進行優(yōu)化部署，部署完成后，判斷是否實現(xiàn)部署目標。如果實現(xiàn)部署目標，則結(jié)束程序；否則，依次對異構(gòu)平臺中剩余的多個k 型傳感器（k=2，3...，Z），采用區(qū)域最優(yōu)匹配算法在尚未覆蓋的空白區(qū)域內(nèi)進行優(yōu)化部署，直至實現(xiàn)部署目標或Z 型傳感器已全部部署完為止。

圖2 采用PSO-ROM 算法的異構(gòu)多傳感器部署流程圖

2.1 局部變異自適應(yīng)粒子群算法

2.1.1 自適應(yīng)粒子群算法

粒子群尋優(yōu)算法的基本原理如式（4）所示：

2.1.2 規(guī)避不可到達區(qū)域的粒子群局部變異

由于存在一些不可部署區(qū)域，在算法尋優(yōu)的過程中，粒子會不可避免地到達這些位置。此時，需要對進入不可部署區(qū)域的粒子進行局部變異，使粒子返回可部署區(qū)域。

假設(shè)粒子當前位置為（X，Y），運動調(diào)整后，移動至不可部署區(qū)域的位置為（X'，Y'），采用式（6）對該粒子進行局部變異調(diào)整：

根據(jù)當前位置和目標位置的坐標連續(xù)使用式（6）進行迭代調(diào)整，直至粒子脫離不可部署區(qū)域。變異過程如圖3 所示。

圖3 局部變異過程示意圖

2.2 區(qū)域最優(yōu)匹配算法

對剩余的傳感器資源按照探測能力進行降序排序，生成傳感器隊列Q。以隊首傳感器Q探測半徑的1/4 為步長，從距離集結(jié)地最近的任務(wù)區(qū)域開始向遠離集結(jié)地方向，呈射線狀掃描任務(wù)區(qū)域內(nèi)的未部署區(qū)域，對發(fā)現(xiàn)的可部署位置P與Q進行匹配，匹配閾值K 定義為：

式中，S為Q的理論最大可探測面積；S為Q部署在P后新增的任務(wù)區(qū)域覆蓋面積。閾值K 的取值范圍一般為（0.5，1］，可根據(jù)實際情況調(diào)整。當傳感器Q滿足閾值約束時，將Q出隊并部署在P處；否則，繼續(xù)掃描并尋找新的P'，直至部署目標實現(xiàn)或隊列Q 為空。具體流程如圖4 所示。

圖4 區(qū)域最優(yōu)匹配算法流程圖

2.3 傳感器與不規(guī)則多邊形相對位置的判斷

傳感器在優(yōu)化部署的過程中，每次尋優(yōu)部署都需要判斷傳感器是否移動到任務(wù)區(qū)域外部。一般采用射線法判定傳感器與不規(guī)則多邊形的相對位置。在射線法中，如果射線與多邊形的交點總數(shù)為奇數(shù)時，判定當前點在多邊形內(nèi)部；如果交點總數(shù)為0 或偶數(shù)，則判定當前點在多邊形外部。由于射線法在奇異情況下容易造成誤判，無法正確識別當前點是否真正在多邊形區(qū)域內(nèi)，本文通過對奇異情況進行分類，選取隨機射線對射線法進行改進。

假設(shè)當前傳感器位置為P（x，y），在多邊形區(qū)域D 內(nèi)隨機部署。首先判斷點P 是否與區(qū)域D 的頂點及各邊重合。在排除點在多邊形的某條邊或頂點上的奇異情況后，假設(shè)區(qū)域D 的邊界范圍最大值為X和Y，取當前點P 遠處隨機點P'（x'，y'）：

由P 點做經(jīng)P'點的射線L，通過連續(xù)取多條隨機射線的方式來消除L 經(jīng)過多邊形頂點這一奇異情況的影響。隨機取所有隨機射線中的兩條進行判斷，當兩次判斷結(jié)果一致時，即可確定當前點是否在多邊形內(nèi)部。

3 實驗結(jié)果

采用Qt5.12 編譯平臺，C 語言編程對PSO-ROM算法的效果進行驗證，并與傳統(tǒng)粒子群算法進行對比。

3.1 異構(gòu)多傳感器不規(guī)則區(qū)域部署結(jié)果

如圖5、圖6 所示，在面積均為484 km的凸多邊形任務(wù)區(qū)域1 和凹多邊形任務(wù)區(qū)域2 中，采用PSO-ROM 算法和傳統(tǒng)的PSO 算法，對傳感器資源（覆蓋比F=1.2）進行優(yōu)化部署如表3 所示，各傳感器的初始集結(jié)位置設(shè)為坐標原點。在優(yōu)化部署中，區(qū)域1 和區(qū)域2 的網(wǎng)格數(shù)量為20×20，目標函數(shù)的權(quán)重因子α=0.5，β=10。傳感器的部署效果如圖5 和圖6 所示，圖中紅色、粉色和藍色圓分別代表A、B、C型傳感器的部署位置。采用PSO-ROM 算法和傳統(tǒng)PSO 算法的部署結(jié)果對比如表4 所示。

表3 待部署傳感器資源列表

圖5 采用PSO-ROM 算法和PSO 算法的凸多邊形任務(wù)區(qū)域1 的覆蓋效果

圖6 采用PSO-ROM 算法和PSO 算法的凹多邊形任務(wù)區(qū)域2 的覆蓋效果

表4 PSO-ROM 算法和傳統(tǒng)PSO 算法的部署結(jié)果對比

如表4 所示，相比于傳統(tǒng)的PSO 算法，采用PSO-ROM 算法覆蓋率平均提升14.9%，耗時平均縮短91%，移動距離平均縮短0.65 km。算法時間消耗的降低，部分原因是采用PSO-ROM 算法，將整個區(qū)域的部署問題轉(zhuǎn)化為采用不同類型傳感器進行多階段部署，降低了每次尋優(yōu)問題的傳感器規(guī)模。如圖7 所示，在任務(wù)區(qū)域之中，采用傳統(tǒng)的PSO 算法，在耗時30 s 后取得了77.5%的覆蓋率，與PSO-ROM算法耗時5.2 s 收斂得出的部署結(jié)果相比，覆蓋率相差17.2%，平均移動距離相差1.2 km。在任務(wù)區(qū)域1中作相應(yīng)的對比，也有相似的結(jié)果。

圖7 傳統(tǒng)PSO 算法與PSO-ROM 算法耗時與覆蓋率的關(guān)系

3.2 重點區(qū)域多頻譜覆蓋

如圖8、圖9 所示，在面積均為550 km的凸多邊形任務(wù)區(qū)域3 和凹多邊形任務(wù)區(qū)域4 中，分3 次采用PSO-ROM 算法對如表5 所示的多型可見光、紅外、雷達傳感器資源（覆蓋比F=1.2，注意設(shè)定的各傳感器探測半徑非真實值）進行重點區(qū)域多重覆蓋部署。各傳感器的初始集結(jié)位置設(shè)為坐標原點。在優(yōu)化部署中，區(qū)域3 和區(qū)域4 的網(wǎng)格數(shù)量為20×20。傳感器的部署效果如圖8 和圖9 所示，圖中紅色、粉色和藍色圓分別代表探測半徑從大到小變化的3 型雷達/可見光/紅外傳感器的部署位置。如表6 所示，采用PSO-ROM 算法開展重要區(qū)域的多頻譜覆蓋時，雷達波段、可見光波段和紅外波段的平均覆蓋率分別為91.0%、94.3%和96.1%。在相同任務(wù)區(qū)域內(nèi)，在傳感器資源覆蓋比F 相同的情況下，傳感器探測半徑越小，傳感器數(shù)量越多，取得的覆蓋率越高。

表5 多頻譜覆蓋中的異構(gòu)傳感器資源列表

表6 基于PSO-ROM 算法的多頻譜覆蓋效果

圖8 采用PSO-ROM 算法的凸多邊形任務(wù)區(qū)域3 的多頻譜覆蓋效果

圖9 采用PSO-ROM 算法的凹多邊形任務(wù)區(qū)域4 的多頻譜覆蓋效果

3.3 覆蓋比F 對部署效果的影響

為了研究采用PSO-ROM 算法的尋優(yōu)結(jié)果與傳感器資源的覆蓋比F 之間的關(guān)系，如下頁圖10 和圖11 所示，在面積均為550 km的凸多邊形任務(wù)區(qū)域5和凹多邊形任務(wù)區(qū)域6 中，采用PSO-ROM 算法分別對如表7 所示的多型傳感器資源（覆蓋比F=0.6～1.5）進行覆蓋部署。在優(yōu)化部署中，區(qū)域5 和區(qū)域6 的網(wǎng)格數(shù)量為20×20。傳感器的部署效果如圖10 和圖11 所示，圖中紅色、粉色和藍色圓分別代表A、B、C 型傳感器的部署位置。不同覆蓋比時采用PSO-ROM 算法的覆蓋率如圖12 所示。

表7 傳感器資源不同覆蓋比信息表

圖10 覆蓋比F 取0.6～1.5 時，采用PSO-ROM算法對凸多邊形任務(wù)區(qū)域5 覆蓋效果

圖11 覆蓋比F 取0.6～1.5 時，采用PSO-ROM算法對凹多邊形任務(wù)區(qū)域6 覆蓋效果

由圖12 可知，在覆蓋比F 從0.6 增加到1.5 的過程中，傳感器的覆蓋率從58%逐漸增大到98.5%，且增長趨勢逐漸變緩。這是因為覆蓋比F 達到1.2時，對任務(wù)區(qū)域進行部署的傳感器資源的利用率已接近飽和，再增加更多的傳感器資源將不會對覆蓋效果產(chǎn)生明顯的影響。因此，在本文對PSO-ROM 算法進行驗證的過程中，將覆蓋比F 設(shè)置為1.2。

圖12 不同覆蓋比時采用PSO-ROM 算法的覆蓋率

3.4 區(qū)域劃分網(wǎng)格數(shù)量對部署效果的影響

為了研究在尋優(yōu)過程中，采用PSO-ROM 算法的尋優(yōu)結(jié)果與任務(wù)區(qū)域劃分網(wǎng)格數(shù)量之間的關(guān)系，在如圖10 和圖11 所示的凸多邊形任務(wù)區(qū)域5 和凹多邊形任務(wù)區(qū)域6 中，采用PSO-ROM 算法分別對如表8 所示的多型傳感器資源（覆蓋比F=1.2）進行覆蓋部署。在區(qū)域5 和區(qū)域6 的網(wǎng)格數(shù)量由10×10 依次變?yōu)?00×100 的過程中，傳感器的覆蓋效果如下頁圖13 所示，算法的時間消耗如圖14 所示。在網(wǎng)格數(shù)量由10×10 依次變?yōu)?00×100 的過程中，傳感器的覆蓋效果無明顯變化，算法的時間消耗按指數(shù)增大。這是因為在網(wǎng)格數(shù)量增大的過程中，對當前覆蓋率的計算更為精確，但是計算的復(fù)雜度大幅增加。

圖13 區(qū)域劃分網(wǎng)格數(shù)量對部署效果的影響

圖14 區(qū)域劃分網(wǎng)格數(shù)量對算法耗時的影響

表8 傳感器資源信息

4 結(jié)論

針對異構(gòu)多傳感器的協(xié)同偵察部署問題，本文提出了PSO-ROM 算法。在任意多邊形低平起伏與和緩起伏的任務(wù)區(qū)域內(nèi)，與傳統(tǒng)PSO 算法相比，采用PSO-ROM 算法在顯著提高覆蓋率的同時，有效降低了算法耗時與節(jié)點平均移動距離。采用PSO-ROM 算法開展重要區(qū)域的多頻譜覆蓋時，可見光、紅外、雷達等多頻段的覆蓋率平均達到93.8%。當覆蓋比F 為1.2 時，待部署傳感器資源的利用率已接近飽和，再增加更多的傳感器資源將不會對覆蓋率產(chǎn)生明顯的改善效果。在任務(wù)區(qū)域劃分網(wǎng)格數(shù)量由10×10 依次變?yōu)?00×100 的過程中，傳感器的覆蓋效果無明顯變化，算法的時間消耗按指數(shù)增大。實驗結(jié)果表明，采用PSO-ROM 算法處理異構(gòu)多傳感器的協(xié)同偵察部署問題和重點區(qū)域多頻譜覆蓋問題時具有較好效果。