李奇真

(中國西南電子技術(shù)研究所，成都 610036)

0 引 言

多傳感器協(xié)同組成的傳感器網(wǎng)絡(luò)能夠顯著提高對環(huán)境的探測、感知能力[1]。傳感器網(wǎng)絡(luò)對熱點區(qū)域、熱點目標(biāo)的感知覆蓋是全方位有效監(jiān)視、監(jiān)控?zé)狳c區(qū)域、熱點目標(biāo)的前提。傳感器網(wǎng)絡(luò)感知覆蓋通常分為目標(biāo)覆蓋、區(qū)域覆蓋和柵欄覆蓋[2]。隨著科技發(fā)展，入侵目標(biāo)具有隱身性、高機(jī)動性等特點，其可見性具有時間、位置上的不確定性，以區(qū)域覆蓋最大化為目標(biāo)，部署傳感器網(wǎng)絡(luò)能夠最大程度上快速發(fā)現(xiàn)目標(biāo)。

目前對區(qū)域覆蓋的研究工作主要集中在理想的二維平面，而在實際應(yīng)用中，傳感器節(jié)點和待監(jiān)視目標(biāo)都分布在三維空間中，針對傳統(tǒng)二維感知模型和二維平面待感知區(qū)域的感知覆蓋優(yōu)化算法很難應(yīng)用到現(xiàn)實復(fù)雜的三維環(huán)境中[3-4]。

三維有向傳感器能夠聚焦感知范圍，增大感知距離，因而能夠?qū)δ繕?biāo)空間進(jìn)行遠(yuǎn)距離監(jiān)視。然而，現(xiàn)有三維有向傳感器網(wǎng)絡(luò)感知覆蓋的相關(guān)文獻(xiàn)主要研究多媒體傳感器網(wǎng)絡(luò)，其只針對近距離待感知區(qū)域(空間)，未考慮地球表面曲率對遠(yuǎn)程感知覆蓋的影響。肖甫等人[5]提出了一種面向三維感知的無線多媒體傳感器網(wǎng)絡(luò)覆蓋增強算法，感知模型為三維椎體，監(jiān)視區(qū)域仍是二維平面。丁志強等人[6]針對復(fù)雜環(huán)境下的有向監(jiān)控設(shè)備網(wǎng)絡(luò)，建立了三維感知模型，提出了在三維空間區(qū)域中結(jié)合虛擬力及區(qū)域權(quán)重的設(shè)備監(jiān)控方向調(diào)整方法，其三維空間為近距離目標(biāo)空間。賈子熙等人[7]和王昌征等人[8]針對三維空間覆蓋問題重新定義了三維感知模型，采用粒子群優(yōu)化算法對空間覆蓋率進(jìn)行優(yōu)化，其感知類型仍為近距離感知。Ru等人[9]給出一種無人機(jī)無線多媒體傳感器網(wǎng)絡(luò)對復(fù)雜平面的三維感知算法，該算法并未涉及對地球表面三維待感知空間的遠(yuǎn)程覆蓋。Cao等人[10]采用分布式并行多目標(biāo)進(jìn)化算法解決智慧城市復(fù)雜環(huán)境中異構(gòu)無線有向傳感器網(wǎng)絡(luò)的三維部署優(yōu)化問題，與本文考慮的遠(yuǎn)程待監(jiān)視空間及傳感器優(yōu)化參數(shù)有很大差異。

本文提出一種面向地球表面三維空間的監(jiān)視覆蓋優(yōu)化算法：首先，將地球表面待監(jiān)視三維空間進(jìn)行離散化處理，并建立傳感器三維有向感知模型；然后，根據(jù)傳感器感知距離范圍、角度范圍以及地球曲率因素計算傳感器網(wǎng)絡(luò)對三維空間的感知覆蓋率，采用粒子群算法和遺傳算法對待監(jiān)視的三維空間進(jìn)行優(yōu)化覆蓋，分別處理連續(xù)優(yōu)化變量和離散優(yōu)化變量；最后，給出面向地球表面三維空間感知覆蓋的仿真想定。通過實驗對比了兩種智能優(yōu)化算法的收斂速度和覆蓋率，為實際三維有向傳感器部署提供了指導(dǎo)性意見。

1 地球表面三維空間的遠(yuǎn)程監(jiān)視覆蓋問題

1.1 三維有向感知模型構(gòu)建

傳感器三維有向感知模型由球頂椎體表示，即一個圓錐面和一個球面所圍成的立體，其中圓錐面的頂點與球面的球心重合，如圖1所示。三維有向傳感器的感知空間可以用四元組(S,V,D,α)來表示，其中，S表示傳感器所在位置，在直角坐標(biāo)系中用(x,y,z)表示；V表示感知方向，可用俯仰角和方位角表示；D表示感知半徑；α表示感知半頂角。

圖1 三維有向感知模型

1.2 待監(jiān)視空間離散化處理及可見性分析

本文考慮的待監(jiān)視空間是地球表面上一定區(qū)域、一定大地高范圍的三維空間，如圖2紅色部分所示。在實際應(yīng)用中，傳感器節(jié)點位置、待監(jiān)視空間位置往往以大地坐標(biāo)的形式給出，例如待監(jiān)視空間中某點的大地坐標(biāo)表示為(B,L,H)，三元素分別表示緯度、經(jīng)度和大地高。設(shè)該點的地心直角坐標(biāo)為(X,Y,Z)，根據(jù)文獻(xiàn)[11]給出的坐標(biāo)轉(zhuǎn)換方法，大地坐標(biāo)到地心直角坐標(biāo)的轉(zhuǎn)換由函數(shù)(X,Y,Z)=blh2xyz(B,L,H)完成，地心直角坐標(biāo)到大地坐標(biāo)的精確轉(zhuǎn)換由函數(shù)(B,L,H)=xyz2blh(X,Y,Z)完成。

圖2 地球表面待監(jiān)視三維空間示意圖

已知三維有向傳感器的大地坐標(biāo)(Bs,Ls,Hs)及其主感知方向的俯仰角γ和方位角θ，下面求主感知方向在地心直角坐標(biāo)系下的方向向量。傳感器地心直角坐標(biāo)表示為Ps=blh2xyz(Bs,Ls,Hs)，地心直角坐標(biāo)系下的傳感器正北方向向量可以近似表示為

VN=blh2xyz(Bs+ξ,Ls,Hs)-Ps。

式中：ξ為足夠小的正實數(shù)，如0.000 1。

正東方向向量可以近似表示為

VE=blh2xyz(Bs,Ls+ξ,Hs)-Ps。

視平線方向向量可以表示為

設(shè)傳感器主感知方向上的一點Cs的地心直角坐標(biāo)為(x,y,z)，主感知方向向量為Vs=Cs-Ps，主感知方向向量與地球切面的夾角為俯仰角γ。設(shè)傳感器所在位置Ps的地心直角坐標(biāo)為(xs,ys,zs)，地球切平面法向量為ns=(b2xs,b2ys,a2zs)，其中a和b分別表示地球橢球的長半軸和短半軸長度。利用叉乘法求解過傳感器節(jié)點，地球切面法向量ns、視平線向量VAz所表示平面的法向量n=(n1,n2,n3)，計算公式如下：

n=VAz×ns。

(1)

主感知向量與該法向量垂直，那么

n1(x-xs)+n2(y-ys)+n3(z-zs)=0。

(2)

主感知方向向量與視平線方向向量的內(nèi)積方程表示為

Vs·VAz=cosγ|Vs||VAz|。

(3)

將主感知方向向量的L2范數(shù)|Vs|2設(shè)為任意正常數(shù)C，以如下方程表示：

(x-xs)2+(y-ys)2+(z-zs)2=C。

(4)

(5)

式中：符號·表示內(nèi)積運算。上式判斷方法表示以過傳感器的地球切平面為基準(zhǔn)平面，過與地心同側(cè)點的方向向量為俯角向量，過與地心異側(cè)點的方向向量為仰角向量，從而根據(jù)俯仰角的符號選擇正確的解向量。通過上述算法，根據(jù)傳感器主感知方向俯仰角、方位角及位置坐標(biāo)，能夠得到傳感器主感知方向向量Vs。

待監(jiān)視空間通常是不規(guī)則的立體空間，難以通過解析的方式計算傳感器網(wǎng)絡(luò)對待監(jiān)視空間的覆蓋情況，本文考慮以一定的顆粒度在緯度B、經(jīng)度L和大地高H三個維度上對待感知空間等間隔離散化。根據(jù)傳感器感知距離、感知角度、地球表面曲率約束條件，判斷待監(jiān)視空間中的離散點能否被傳感器感知覆蓋。設(shè)待監(jiān)視空間某離散點的大地坐標(biāo)d(Bd,Ld,Hd)，根據(jù)文獻(xiàn)[12]和文獻(xiàn)[13],無線電極限視距廣泛采用下面的經(jīng)驗公式：

(6)

式中：Re=4R/3為地球等效曲率半徑，R=6.37×106m為地球曲率半徑；Hs、Hd和DLOS的單位都為m。

1.3 遠(yuǎn)程監(jiān)視覆蓋率計算

與文獻(xiàn)[5]中傳感器網(wǎng)絡(luò)監(jiān)視覆蓋率計算類似，首先對地球表面三維空間進(jìn)行離散化處理，即在緯度、經(jīng)度和大地高上分別間隔ΔB、ΔL、ΔH取離散點，從而將連續(xù)三維空間的覆蓋問題轉(zhuǎn)化為對目標(biāo)空間中離散點的覆蓋問題。設(shè)目標(biāo)空間離散化后對應(yīng)的離散點集合為Ω，所有至少被一個傳感器覆蓋的離散點集合為Ω1，則目標(biāo)空間監(jiān)視覆蓋率定義為

(7)

式中：符號|·|表示集合中的元素數(shù)量。

本文僅考慮位置固定的傳感器，優(yōu)化變量是每個傳感器的俯仰角和方位角，分別表示為γi和θi，其中i=1,2,…,N，N為傳感器的數(shù)量。目標(biāo)空間監(jiān)視覆蓋率是所有傳感器俯仰角和方位角的函數(shù)，即CR=f(γ1,θ1,…,γN,θN)。本文的目的是通過調(diào)整每個傳感器的俯仰角和方位角，最大化傳感器網(wǎng)絡(luò)對目標(biāo)空間的監(jiān)視覆蓋率，從而得到每個傳感器對應(yīng)的最優(yōu)主感知方向，表示如下:

(8)

2 基于智能算法的覆蓋優(yōu)化方法

目標(biāo)空間的監(jiān)視覆蓋優(yōu)化問題是多變量組合優(yōu)化問題，覆蓋率函數(shù)難以表示成自變量的閉合表達(dá)式，所以不能利用傳統(tǒng)的凸/非凸優(yōu)化方法求解每個傳感器的最優(yōu)主感知方向。為此，本文采用智能算法進(jìn)行目標(biāo)空間的監(jiān)視覆蓋優(yōu)化：首先考慮每個傳感器的俯仰角和方位角為連續(xù)變量，采用粒子群優(yōu)化算法[14]求解所有傳感器的最優(yōu)俯仰角和方位角；其次，考慮到地球表面三維空間距大地的高度范圍較小，傳感器俯仰角對覆蓋率的影響較小，采用遺傳算法[14]求解所有傳感器的最優(yōu)離散化方位角，從而有效降低算法復(fù)雜度。

2.1 連續(xù)方位角/俯仰角優(yōu)化

Step1 計算每個個體中每個優(yōu)化參數(shù)的更新速度，公式如下：

(9)

(10)

式中：r∈(0,1)是隨機(jī)數(shù)，若速度更新值超過邊界，則在更新速度可取范圍內(nèi)隨機(jī)取值作為有效速度更新值。

Step2 更新每個個體中的俯仰角γi和方位角θi，公式如下：

γi=γi+vγi，θi=θi+vθi。

(11)

若俯仰角γ和方位角θ的更新值超過參數(shù)邊界，則在優(yōu)化參數(shù)可取范圍內(nèi)隨機(jī)取值作為有效參數(shù)更新值。

Step3 計算每個個體的適應(yīng)度值(即傳感器網(wǎng)絡(luò)對目標(biāo)三維空間的覆蓋率，如公式(7)所示)，與群體歷史最優(yōu)適應(yīng)度值比較，判斷本代適應(yīng)度值是否優(yōu)于群體歷史最優(yōu)適應(yīng)度值，若是將本代適應(yīng)度值替換群體最優(yōu)適應(yīng)度值，否則保留當(dāng)前群體歷史最優(yōu)適應(yīng)度值。

2.2 離散方位角優(yōu)化

目標(biāo)空間的大地高范圍較小，傳感器俯仰角對目標(biāo)空間覆蓋率影響較小，本小節(jié)將每個傳感器的俯仰角固定在一個較優(yōu)的值(如0°)，將方位角進(jìn)行離散化、二進(jìn)制編碼，利用遺傳算法對其進(jìn)行優(yōu)化，從而得到最大監(jiān)視覆蓋率下的傳感器網(wǎng)絡(luò)最佳方位角組合。

Step1 初始化參數(shù)：設(shè)置進(jìn)化代數(shù)計數(shù)器g=0，設(shè)置最大進(jìn)化代數(shù)G，隨機(jī)生成Np個個體作為初始群體P(0)，計算群體中每個個體的適應(yīng)度，并對其進(jìn)行排序。

Step2 選擇運算：將選擇算子作用于群體，根據(jù)個體適應(yīng)度，按照一定規(guī)則和方法(如輪盤賭方法)，選擇一些優(yōu)良個體遺傳到下一代群體，保留當(dāng)前適應(yīng)度最佳個體。

Step3 交叉運算：交叉算子作用于群體，對選中的成對個體，按照某一概率交叉它們的部分染色體，產(chǎn)生新的個體，并保留當(dāng)前適應(yīng)度最佳個體。

Step4 變異運算：將變異算子作用于群體，以一定的概率改變某一或某些基因值為其他等位基因，并保留當(dāng)前適應(yīng)度最佳個體。

Step5 群體P(t)經(jīng)選擇、交叉、變異運算得到下一代群體P(t+1)，計算其適應(yīng)度值，并對根據(jù)適應(yīng)度進(jìn)行排序，準(zhǔn)備進(jìn)行下一代遺傳迭代。

Step6 終止條件判斷：若g≤G，則g=g+1，轉(zhuǎn)到Step 2；若g>G，則進(jìn)化過程中得到的最佳適應(yīng)度個體作為最優(yōu)解輸出，算法結(jié)束。

3 仿真結(jié)果與分析

本文仿真計算機(jī)CPU為Intel Core i5-6500,主頻3.2 GHz，采用Matlab軟件仿真固定位置有向傳感器網(wǎng)絡(luò)對地球表面三維空間監(jiān)視覆蓋優(yōu)化，優(yōu)化算法包括粒子群優(yōu)化算法和遺傳優(yōu)化算法，其中粒子群優(yōu)化算法包括俯仰角可調(diào)整和俯仰角固定兩種情況，遺傳算法優(yōu)化離散編碼的方位角。

仿真場景如圖3所示。設(shè)置固定位置三維有向傳感器網(wǎng)絡(luò)中的傳感器數(shù)量為5，每個傳感器的位置、感知半角和默認(rèn)最大感知距離如表1所示。地球表面待監(jiān)視目標(biāo)空間為緯度、經(jīng)度和大地高在一定取值方位的三維空間，其中，緯度取值范圍為北緯26.5°～35.5°，經(jīng)度取值范圍為東經(jīng)123°～127°，大地高取值范圍默認(rèn)為5 000～20 000 m。緯度和經(jīng)度的離散化顆粒度為0.1°，大地高的離散化顆粒度為100 m。

圖3 仿真場景設(shè)置

編號位置緯度/(°)經(jīng)度/(°)大地高/m感知半角/(°)最大感知距離/km13312022020°53023212113030°53233112128015°58742912178018.5°59052812130329°551

對于三種優(yōu)化算法，群體中的個體數(shù)量均為50，進(jìn)化代數(shù)為100。針對粒子群算法，設(shè)定俯仰角邊界為[-3°,3°]，方位角邊界為[60°，120°]，俯仰角更新速度邊界為[-1°,1°]，方位角更新速度邊界為[-5°,5°]，慣性權(quán)重w=0.8，自學(xué)習(xí)因子c1=0.5，群體學(xué)習(xí)因子c2=0.5。針對遺傳算法，每個傳感器的方位角邊界為[60°，120°]，由8位二進(jìn)制數(shù)編碼，染色體從高位到低位的交叉起始點隨機(jī)選擇，交叉概率為0.25，變異概率為0.01。

三種算法的群體歷史最優(yōu)適應(yīng)度隨迭代次數(shù)的變化曲線如圖4所示，每條曲線是5次仿真的平均值，其中，藍(lán)色實線表示俯仰角可調(diào)整粒子群算法結(jié)果，紅色點線表示俯仰角固定粒子群算法結(jié)果，黑色點劃線表示遺傳算法結(jié)果。由仿真結(jié)果可知，俯仰角固定粒子群算法最終收斂結(jié)果與俯仰角可調(diào)粒子群優(yōu)化算法相當(dāng)，兩種粒子群算法均優(yōu)于遺傳算法，這說明俯仰角優(yōu)化對收斂結(jié)果影響較小，自變量離散化編碼對收斂結(jié)果影響較大。

圖4 群體歷史最優(yōu)適應(yīng)度變化曲線

以固定俯仰角粒子群算法為例仿真了傳感器最大感知距離對覆蓋率的影響，結(jié)果如圖5所示，其中，藍(lán)色實線表示默認(rèn)最大感知距離下的結(jié)果，紅色點線表示所有傳感器最大感知距離增大10 km的結(jié)果，黑色點劃線表示所有傳感器最大感知距離減小10 km的結(jié)果。由仿真結(jié)果可知，隨著傳感器感知距離增大，傳感器網(wǎng)絡(luò)覆蓋率同時增大，其增長速度變緩。這一方面因為一些傳感器感知范圍超出待監(jiān)視空間，另一方面大地高程較小、距傳感器較遠(yuǎn)的目標(biāo)空間離散點被地球遮擋，未被傳感器覆蓋，新增被覆蓋離散點與新增待監(jiān)視空間離散點的比值減小。

圖5 傳感器最大感知距離對覆蓋率的影響

以固定俯仰角粒子群算法為例仿真了不同大地高范圍目標(biāo)感知空間的覆蓋率，結(jié)果如圖6所示，其中，藍(lán)色實線為默認(rèn)大地高范圍結(jié)果，紅色點線為大地高范圍4 000～19 000 m的結(jié)果，黑色點劃線為大地高范圍6 000～21 000 m的結(jié)果。由仿真結(jié)果可知，隨著大地高程增大，傳感器網(wǎng)絡(luò)對目標(biāo)空間的覆蓋率也增大，原因是根據(jù)公式(6)，大地高較小的目標(biāo)空間離散點被地球遮擋，傳感器網(wǎng)絡(luò)對該部分離散點無法有效覆蓋。

圖6 目標(biāo)空間大地高范圍對覆蓋率的影響

仿真過程中發(fā)現(xiàn)，俯仰角可調(diào)粒子群算法需要求解方程組，其時間復(fù)雜度(每輪迭代平均用時1 760 s)遠(yuǎn)高于其他兩種算法(俯仰角固定粒子群算法平均用時35.98 s，遺傳算法平均用時34.90 s)，因此，在地球表面空間大地高范圍較小的情況下，建議使用固定俯仰角粒子群優(yōu)化算法。

4 結(jié)束語

本文建立了地球表面曲率影響下的三維目標(biāo)空間模型以及傳感器三維感知模型，提出了基于粒子群算法和遺傳算法的面向地球表面三維空間的遠(yuǎn)程監(jiān)視覆蓋優(yōu)化算法，通過仿真分析了不同參數(shù)下兩種算法的性能及效率，為有向遠(yuǎn)程感知傳感器網(wǎng)絡(luò)的部署提供了技術(shù)支撐。

本文提出的智能優(yōu)化算法適應(yīng)度為目標(biāo)空間的一重覆蓋率，然而一重覆蓋下傳感器網(wǎng)絡(luò)不能對目標(biāo)空間進(jìn)行協(xié)同監(jiān)視，且可能在入侵方向上存在入侵盲區(qū)。在后續(xù)工作中，將進(jìn)一步采用多目標(biāo)適應(yīng)度函數(shù)，加入空間多重覆蓋和入侵方向柵欄覆蓋作為優(yōu)化目標(biāo)，提高目標(biāo)空間監(jiān)視效果。此外，本文對目標(biāo)空間離散化處理，分別對每個傳感器到每個離散點進(jìn)行可見性分析，串行計算非常耗時。后續(xù)工作中，將研究并行計算方法，以降低算法的時間復(fù)雜度。