障礙物遮蔽下三維空間多傳感器優(yōu)化布站

俞 宙，單甘霖，段修生，2，徐公國(guó)

(1.陸軍工程大學(xué)石家莊校區(qū)，河北 石家莊 050003；2.石家莊鐵道大學(xué)，河北 石家莊 050043)

0 引言

目前，戰(zhàn)術(shù)偵察系統(tǒng)配置了不同體制、不同功能、不同頻段的雷達(dá)、紅外、激光和偵察車等傳感器，廣泛應(yīng)用于戰(zhàn)場(chǎng)環(huán)境監(jiān)視、目標(biāo)定位跟蹤、區(qū)域協(xié)同探測(cè)等。布站后的位置影響了傳感器系統(tǒng)的覆蓋范圍、通信以及資源管理能力，直接影響著系統(tǒng)的探測(cè)效果。因此，需要尋求一種優(yōu)化布站方案，確保最優(yōu)的區(qū)域覆蓋率和最佳系統(tǒng)效能。

文獻(xiàn)[1]考慮平面上的布站問(wèn)題，將目標(biāo)區(qū)域劃分為正方形網(wǎng)格。文獻(xiàn)[2]對(duì)傳統(tǒng)的虛擬力算法進(jìn)行了改進(jìn)，但采用的是簡(jiǎn)單的布爾傳感器感知模型。文獻(xiàn)[3]考慮了探測(cè)成本、目標(biāo)探測(cè)值以及探測(cè)能力等因素，提出一種基于博弈論的二維平面?zhèn)鞲衅髯晕也颊?。文獻(xiàn)[4]提出一種基于虛擬力的理想三維環(huán)境下覆蓋算法，解決傳感器非均勻覆蓋問(wèn)題。文獻(xiàn)[5]將果蠅算法和虛擬力相結(jié)合，來(lái)控制傳感器對(duì)空間的網(wǎng)格覆蓋，但研究的是理想的三維環(huán)境。文獻(xiàn)[6]考慮了環(huán)境因素，提出了一種基于視線覆蓋范圍的概率傳感器放置方法。文獻(xiàn)[7]針對(duì)三維空間中傳感器布站問(wèn)題，采用差分進(jìn)化算法解決了盲區(qū)問(wèn)題，但忽略了實(shí)際地形因素的影響。針對(duì)在指定地理位置和存在障礙物的情況下的布站問(wèn)題，文獻(xiàn)[8]提出了一種避障虛擬力算法來(lái)實(shí)現(xiàn)傳感器自主布站，避開(kāi)了障礙物但未對(duì)障礙物進(jìn)行建模。文獻(xiàn)[9]考慮了障礙物遮擋問(wèn)題，采用多目標(biāo)進(jìn)化算法研究了傳感器布站問(wèn)題。文獻(xiàn)[10]加入更實(shí)際的地形模型，但只考慮了可用凸多邊形建模的地形。

以上研究的都是二維平面以及理想三維環(huán)境下的布站，且依賴于過(guò)于簡(jiǎn)單化的傳感器探測(cè)模型和理想的環(huán)境因素。但在實(shí)際應(yīng)用中，戰(zhàn)場(chǎng)地理環(huán)境往往極不規(guī)則，且存在高山等障礙物遮蔽問(wèn)題。本文針對(duì)此問(wèn)題，提出了障礙物遮蔽下三維空間多傳感器優(yōu)化布站方法。

1 戰(zhàn)場(chǎng)多傳感器優(yōu)化布站模型

1.1 傳感器探測(cè)模型

假設(shè)地面?zhèn)刹煜到y(tǒng)中有N部方向傳感器S={S1,S2,…,Sn}，對(duì)于任意傳感器Si，有Si={(xi,yi),hi(xi,yi),ri,rci,θi,ξi},i∈[1,2,…,N]。其中，(xi,yi)是Si在平面上的坐標(biāo)；hi(xi,yi)是Si的高度；ri是Si的探測(cè)半徑；rci是傳感器的通信半徑；θi是傳感器圍繞垂直軸的水平角；ξi是傳感器圍繞水平軸的傾斜角。則空間中的傳感器探測(cè)模型可視為三維球，如圖1所示。

圖1 傳感器模型Fig.1 Sensor model

1.2 戰(zhàn)場(chǎng)環(huán)境模型

實(shí)際應(yīng)用中，戰(zhàn)場(chǎng)中難免會(huì)存在高山、湖泊、沼澤、建筑物等障礙物，會(huì)造成視場(chǎng)約束。且戰(zhàn)場(chǎng)環(huán)境的地形復(fù)雜多變，難以對(duì)其精確描述。為此，本文提出了一種基于網(wǎng)格化的戰(zhàn)場(chǎng)環(huán)境模型。

1.2.1 網(wǎng)格化戰(zhàn)場(chǎng)環(huán)境

基于網(wǎng)格化的策略是一種將區(qū)域劃分為網(wǎng)格的方法，網(wǎng)格點(diǎn)近似代表整個(gè)區(qū)域。首先將三維戰(zhàn)場(chǎng)環(huán)境投影到XOY平面上，實(shí)現(xiàn)對(duì)地形的數(shù)字化描述；接著用平行線對(duì)區(qū)域進(jìn)行等間隔的網(wǎng)格劃分，一個(gè)網(wǎng)格區(qū)域都是一個(gè)備選的傳感器布站位置點(diǎn)。精度取決于網(wǎng)格的大小，尺寸越小，計(jì)算的就越準(zhǔn)確。區(qū)域中的網(wǎng)格點(diǎn)表示為E={e1,e2,…,em}，對(duì)于任一點(diǎn)ej，有ej={(xej，yej),hej(xej，yej),wj},j∈[1,2,…,m]。其中，(xej，yej)是該點(diǎn)處的坐標(biāo)，hej(xej，yej)是該點(diǎn)處的高度，由數(shù)字高程模型(DEM)提供，wj代表該點(diǎn)處的權(quán)重。因此，T={he1,he2,…,hem}是一個(gè)數(shù)字高程矩陣，矩陣數(shù)值表示網(wǎng)格點(diǎn)的高度。

1.2.2 區(qū)域劃分

整個(gè)戰(zhàn)場(chǎng)區(qū)域可以劃分為四類：偵察區(qū)域Ar、障礙物O、布站區(qū)域Ad和不能布站區(qū)域Au。偵察區(qū)域是傳感器偵察系統(tǒng)需要覆蓋的區(qū)域，應(yīng)盡可能覆蓋。障礙物描述了環(huán)境中存在的障礙，本文認(rèn)為障礙物能阻礙傳感器的探測(cè)和布站，但不會(huì)阻礙傳感器之間的通信。布站區(qū)域表示傳感器允許布站的區(qū)域，包括但不限于偵察區(qū)域，并排除障礙物。不能布站區(qū)域包括但不限于障礙物。

1.3 自適應(yīng)LOS理論

影響可視性的主要因素是兩點(diǎn)之間連線上點(diǎn)的高度。高度由DEM提供，是一個(gè)基本的二維矩陣，矩陣中的元素存儲(chǔ)了戰(zhàn)場(chǎng)環(huán)境中點(diǎn)的高度。傳統(tǒng)的LOS方法根據(jù)網(wǎng)格大小，將連接點(diǎn)和傳感器之間的連線劃分為若干分裂點(diǎn)；接著將每個(gè)點(diǎn)高度與包含它的網(wǎng)格高度進(jìn)行比較。如果小于網(wǎng)格高度，那么兩者之間存在障礙物。但是這個(gè)方法的缺點(diǎn)是計(jì)算復(fù)雜，運(yùn)算量大。

為此，我們提出了一種新的自適應(yīng)LOS理論，使用分裂點(diǎn)之間的自適應(yīng)長(zhǎng)度來(lái)減少計(jì)算的點(diǎn)數(shù)?？紤]到分裂點(diǎn)和連續(xù)兩個(gè)分裂點(diǎn)之間網(wǎng)格的高度的差異性，如果在分裂點(diǎn)沒(méi)有測(cè)量到障礙物，那么下一個(gè)分裂點(diǎn)也可能沒(méi)有障礙物。因此，本文使用線性回歸來(lái)預(yù)測(cè)連接點(diǎn)和傳感器的線是否與障礙物相交。如果是，則記錄下這一點(diǎn)和開(kāi)始點(diǎn)的距離作為新長(zhǎng)度，將該點(diǎn)設(shè)置為開(kāi)始點(diǎn)，并繼續(xù)尋找另一個(gè)自適應(yīng)長(zhǎng)度，直到新點(diǎn)超過(guò)了傳感器位置點(diǎn)。可視性示意圖如圖2所示。

圖2 可視性示意圖Fig.2 Visibility schematic

1.4 障礙物建模

為了清晰直觀地描述障礙物，我們假定平面上存在圓形和矩形這兩種形狀障礙物，O={o1,o2,…,oh}表示戰(zhàn)場(chǎng)中存在的所有障礙物。其中，圓形障礙物對(duì)應(yīng)于環(huán)形山、大石頭、湖泊等圓形狀障礙物，表示為oi={(xoi,yoi),roi,hoi}, (xoi,yoi)是障礙物的圓心，roi表示圓形障礙物半徑，hoi表示障礙物高度。矩形障礙物對(duì)應(yīng)于高山、樹(shù)籬、建筑物等矩形狀的障礙物，表示為oi={(xoi,yoi),loi,woi,hoi},(xoi,yoi)表示矩形障礙物左上角頂點(diǎn)，loi和woi分別表示矩形障礙物長(zhǎng)度和寬度，hoi表示障礙物高度。障礙物建模示意圖見(jiàn)圖3。

1.5 優(yōu)化布站數(shù)學(xué)模型

對(duì)于布站區(qū)域內(nèi)的任意一個(gè)點(diǎn)ej，傳感器和目標(biāo)點(diǎn)之間的距離為：

(1)

如果戰(zhàn)場(chǎng)區(qū)域中所有點(diǎn)都能被傳感器系統(tǒng)覆蓋，那么戰(zhàn)場(chǎng)區(qū)域就能夠被覆蓋。通常，布站區(qū)域中的任一點(diǎn)ej需要滿足以下條件才能視為被傳感器Si所覆蓋。

1) 傳感器Si與點(diǎn)ej之間的距離小于等于傳感器的探測(cè)半徑ri，即：

(2)

2) 傳感器Si與點(diǎn)ej之間沿X軸方向的角度不大于傳感器的方位角。μb是一個(gè)用于描述傳感器Si沿著垂直軸對(duì)點(diǎn)ej覆蓋能力的二元函數(shù)：

(3)

3) 傳感器Si與點(diǎn)ej之間沿著Z方向的角度不大于傳感器Si的高低角。μc是一個(gè)用于描述傳感器Si沿著水平軸對(duì)點(diǎn)ej覆蓋能力的二元函數(shù)：

(4)

4)vij定義為傳感器Si與點(diǎn)ej之間的可視性，如果傳感器Si與點(diǎn)ej之間的視線被遮擋，則認(rèn)為傳感器Si探測(cè)不到點(diǎn)ej，vij=0；反之，vij=1。

(5)

式(5)中，nobstacle(Si,ej)是傳感器Si與點(diǎn)ej之間的障礙物數(shù)量，取決于自適應(yīng)LOS理論。

因此，傳感器探測(cè)模型主要取決于距離、方向以及可視性。則傳感器Si在點(diǎn)ej處的覆蓋能力可以定義為：

C(Si,ej)=μa×μb×μc×vij

(6)

考慮到點(diǎn)ej可能被一部或者多部傳感器所覆蓋，且傳感器之間相互獨(dú)立，因此，戰(zhàn)場(chǎng)環(huán)境中點(diǎn)ej被覆蓋的概率為：

(7)

那么整個(gè)區(qū)域的覆蓋率為：

(8)

綜合考慮戰(zhàn)場(chǎng)環(huán)境等因素，為了獲得最大偵察區(qū)域覆蓋率Call，建立如下的多傳感器優(yōu)化布站數(shù)學(xué)模時(shí)型，通過(guò)優(yōu)化求解，可以獲得最佳的多傳感器優(yōu)化布站方案：

(9)

2 多傳感器優(yōu)化布站算法

2.1 自適應(yīng)權(quán)重粒子群算法

粒子群算法(PSO，Particle Swarm Optimization)將優(yōu)化問(wèn)題可行解初始化為一群隨機(jī)粒子。粒子根據(jù)如下的公式來(lái)更新自己的位置和速度：

Vi(t+1)=ωVi(t)+c1r1(Pibest-Xi(t))+

c2r2(Pgbest-Xi(t))

(10)

Xi(t+1)=Xi(t)+Vi(t+1)

(11)

為了平衡PSO算法的全局搜索和局部改良的能力，采用非線性的動(dòng)態(tài)慣性權(quán)重系數(shù)來(lái)改進(jìn)粒子群算法。

(12)

式(12)中，ωmax和ωmin分別表示ω的最大值和最小值，f表示粒子當(dāng)前目標(biāo)函數(shù)值，fave和fmin分別表示當(dāng)前粒子群的平均目標(biāo)值和最小目標(biāo)值。因此，ω隨著粒子群目標(biāo)函數(shù)值自動(dòng)改變，故稱作自適應(yīng)權(quán)重。當(dāng)粒子目標(biāo)值趨于一致或局部最優(yōu)時(shí)，將增大ω，而粒子的目標(biāo)值比較分散時(shí)，將減小ω，保留該粒子。且差于平均目標(biāo)值的粒子，其對(duì)應(yīng)的慣性權(quán)重因子較大，使得該粒子向較好的搜索區(qū)域趨近。

2.2 虛擬力算法

虛擬力算法VF(Virtual Force Algorithm)，虛擬力借助于物理中的范德華力對(duì)區(qū)域中隨機(jī)分布的傳感器進(jìn)行重新布站，包括引力和斥力。布站時(shí)，傳感器隨其受到的合力進(jìn)行移動(dòng)，從而實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的均勻覆蓋。假設(shè)在偵察區(qū)域中，相鄰傳感器Sj作用在傳感器Si上的虛擬力為Fij，當(dāng)兩個(gè)傳感器之間的距離大于距離閾值Dth時(shí)，傳感器之間產(chǎn)生引力，傳感器向著對(duì)方移動(dòng)。當(dāng)傳感器之間的距離小于該閾值時(shí)，傳感器之間產(chǎn)生斥力，傳感器向著相反方向移動(dòng)。Fij的計(jì)算公式為：

(13)

目標(biāo)區(qū)域邊界對(duì)傳感器Si的作用力為Fia，障礙物對(duì)傳感器Si的作用力為Fir，則作用在傳感器Si上的總的虛擬力Fi為：

(14)

式中，dij是傳感器Si與傳感器Sj之間的幾何距離；adj(Si)是傳感器Si的鄰接集，當(dāng)且僅當(dāng)dij≤rc時(shí)，傳感器Sj稱為Si的臨集；Dth表示均勻分布時(shí)傳感器之間的平均距離。

2.3 虛擬力自適應(yīng)權(quán)重粒子群算法

本文在粒子進(jìn)化過(guò)程中，加入虛擬力來(lái)增強(qiáng)粒子的位置更新能力。得到了虛擬力自適應(yīng)權(quán)重粒子群算法(VF-APSO)，進(jìn)化過(guò)程如下：

Vi(t+1)=ωVi(t)+c1r1(Pibest-Xi(t))+

c2r2(Pgbest-Xi(t))+c3r3Fi

(15)

Xi(t+1)=Xi(t)+Vi(t+1)

(16)

式中，c3是調(diào)節(jié)虛擬力的加速因子，r3是[0,1]之間隨機(jī)數(shù)。虛擬力對(duì)于粒子位置更新具有積極作用，提高了算法的收斂速度。但到了后期，由于虛擬力的存在也會(huì)阻礙粒子的局部搜索，無(wú)法搜索到最優(yōu)解。因此，本文對(duì)c3進(jìn)行動(dòng)態(tài)調(diào)整。更新公式為：

(17)

此處，c3start取為0.6，c3end取為0.2。這樣，算法前期主要發(fā)揮虛擬力算法的優(yōu)勢(shì)，加快粒子的收斂速度。算法后期減小了虛擬力帶來(lái)的影響，發(fā)揮自適應(yīng)權(quán)重粒子群算法的優(yōu)勢(shì)，對(duì)全局最優(yōu)解附近的解空間進(jìn)行精確搜索，找到更優(yōu)解。

3 仿真與實(shí)驗(yàn)

為了驗(yàn)證所提算法的有效性，本文用Matlab對(duì)三維空間中視場(chǎng)約束下的多傳感器布站問(wèn)題進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)中，首先采用大量的測(cè)試點(diǎn)對(duì)自適應(yīng)LOS理論進(jìn)行驗(yàn)證。接著采用VF-APSO算法進(jìn)行傳感器優(yōu)化布站，并與經(jīng)典的PSO、VF-PSO算法進(jìn)行仿真對(duì)比。

3.1 自適應(yīng)LOS理論

首先，我們分別采用100，200，500，1 000，2 000，5 000個(gè)點(diǎn)對(duì)所提的LOS理論進(jìn)行了測(cè)試，每組運(yùn)行50次，平均結(jié)果如表1和圖4所示。

表1 自適應(yīng)LOS理論測(cè)試結(jié)果Tab.1 Adaptive LOS method test results

圖4 新舊LOS理論對(duì)比Fig.4 Comparison of two LOS method

仿真結(jié)果表明：自適應(yīng)LOS理論在檢測(cè)障礙物方面獲得了較好的精確度；且與傳統(tǒng)的LOS 理論相比，大大減少了運(yùn)算時(shí)間，提高了檢測(cè)效率，可以有效解決對(duì)空間中存在的障礙物檢測(cè)問(wèn)題。

3.2 基于VF-APSO的多傳感器優(yōu)化布站

實(shí)驗(yàn)中，首先將傳感器隨機(jī)分散在30 km×30 km×10 km的三維空間區(qū)域中。為了避免資源浪費(fèi)，采用10部傳感器對(duì)地面目標(biāo)區(qū)域進(jìn)行覆蓋，并在目標(biāo)區(qū)域中隨機(jī)設(shè)立了一些障礙物，用黃色區(qū)域表示。假定偵察系統(tǒng)中所有傳感器的探測(cè)半徑r為5 km，通信半徑rc為2r=10 km，距離門限值Dth為r=5 km，初始種群為300，最大迭代次數(shù)500。采用VF-APSO算法進(jìn)行優(yōu)化布站，并與經(jīng)典的PSO、 VF-PSO算法進(jìn)行仿真對(duì)比。運(yùn)行結(jié)果如表2，圖5—圖7所示。

表2 50次不同算法獨(dú)立優(yōu)化平均性能比較Tab.2 Comparison of different algorithms’ optimization performance

圖5 PSO優(yōu)化布站Fig.5 View of PSO optimal deployment

圖6 VF-PSO優(yōu)化布站Fig.6 View of VF-PSO optimal deployment

圖7 VF-APSO優(yōu)化布站Fig.7 View of VF-APSO optimal deployment

仿真結(jié)果表明：相比于PSO、VF-PSO算法，改進(jìn)后的VF-APSO算法增強(qiáng)了粒子的全局搜索能力，提高了運(yùn)算速度；且基于VF-APSO算法的多傳感器布站方法求出的傳感器位置有了明顯的改善，提高了覆蓋率，實(shí)現(xiàn)了對(duì)偵察區(qū)域的有效覆蓋，解決了障礙物遮蔽下的多傳感器優(yōu)化布站問(wèn)題。

4 結(jié)論

本文提出了障礙物遮蔽下三維空間多傳感器優(yōu)化布站方法。該方法首先網(wǎng)格化偵察區(qū)域，然后采用自適應(yīng)LOS理論來(lái)檢測(cè)區(qū)域中存在的障礙物，構(gòu)建多傳感器優(yōu)化布站數(shù)學(xué)模型，最后采用虛擬力自適應(yīng)權(quán)重粒子群算法求解傳感器的最優(yōu)布站位置，并與經(jīng)典算法進(jìn)行對(duì)比。仿真實(shí)驗(yàn)表明，該方法增強(qiáng)了粒子的全局搜索能力，提高了粒子的運(yùn)算速度，有效提高了區(qū)域覆蓋率。對(duì)于解決實(shí)際中存在障礙物條件下的多傳感器優(yōu)化布站問(wèn)題，具有一定的參考意義。