基于粒子群的傳感器空間覆蓋優(yōu)化方法

張 滿(mǎn)，賈云璐，林 杰

(中國(guó)工程物理研究院 機(jī)械制造工藝研究所，四川 綿陽(yáng) 621000)

0 引 言

視頻監(jiān)控作為日常安防的重要手段，其在任務(wù)區(qū)域的有效覆蓋率又是評(píng)價(jià)服務(wù)質(zhì)量的重要指標(biāo)。目前大多數(shù)的研究都是基于傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題，監(jiān)控?cái)z像機(jī)屬于傳感器的一種類(lèi)型，所以可以借鑒傳感器網(wǎng)絡(luò)覆蓋問(wèn)題的解決方法展開(kāi)研究。當(dāng)前對(duì)于傳感器網(wǎng)絡(luò)覆蓋控制的研究大多數(shù)是基于二維模型[1-4]，少部分的三維傳感器模型是將三維空間問(wèn)題約束到二維區(qū)域來(lái)解決[5-7]。但是由于視頻監(jiān)控任務(wù)的特殊性，其需要對(duì)一定高度范圍內(nèi)的區(qū)域進(jìn)行較好的檢測(cè)，例如對(duì)于人就需要檢測(cè)從上到下等一系列特征，基于二維的傳感器感知模型及算法不能滿(mǎn)足視頻監(jiān)控的任務(wù)要求。

該文通過(guò)借鑒關(guān)于傳感器的研究，提出一種適用于監(jiān)控?cái)z像機(jī)的三維模型并通過(guò)算法增強(qiáng)監(jiān)控區(qū)域的覆蓋度。吳帥[8]與童海燕[9]提出的是一種三維全向的球形覆蓋模型，并分別通過(guò)粒子群算法與虛擬力算法使得球形傳感器在xyz三個(gè)方向上均勻分布。作者雖然提出了三維的傳感器模型，但是該模型屬于全向的模型，由于實(shí)際生活中監(jiān)控?cái)z像機(jī)模型的限制，不能直接應(yīng)用該模型。熊永華[10]通過(guò)粒子群智能算法對(duì)感知半徑可調(diào)的有向扇形傳感器進(jìn)行覆蓋優(yōu)化。李娜[11]針對(duì)監(jiān)控區(qū)域存在障礙物的情況，引入避障策略，提出基于虛擬力的傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法。蔣鵬[12]基于二維扇形模型提出了一種虛擬力導(dǎo)向的粒子群攝像頭網(wǎng)絡(luò)覆蓋增強(qiáng)策略，結(jié)合了虛擬力與粒子群算法來(lái)進(jìn)行傳感器的布置。Peng J與肖甫[13-14]使用的是傳統(tǒng)的三維傳感器模型，作者將關(guān)于傳感器位姿的方向正交分解為俯仰角和偏向角，在傳感器自身參數(shù)的限制下，調(diào)整單個(gè)傳感器的俯仰角使得傳感器在地面上的投影梯形面積最大化，再通過(guò)調(diào)整多傳感器的偏向角使得傳感器的覆蓋度最大化。這兩篇文獻(xiàn)中所使用的傳感器節(jié)點(diǎn)模型，與視頻監(jiān)控?cái)z像機(jī)的任務(wù)要求相比較，并不能滿(mǎn)足對(duì)具有一定高度信息的目標(biāo)進(jìn)行檢測(cè)。

總結(jié)已有文獻(xiàn)，現(xiàn)有的傳感器模型大多都集中于二維平面的感知范圍，并沒(méi)有考慮一定高度范圍內(nèi)的信息獲取。針對(duì)現(xiàn)有問(wèn)題，結(jié)合監(jiān)控?cái)z像機(jī)的實(shí)際情況與上述文獻(xiàn)中的傳感器模型，該文考慮一定高度的傳感器模型，同時(shí)假設(shè)傳感器同構(gòu)且布置在同一高度平面內(nèi)，將傳感器的布置分為對(duì)單個(gè)傳感器的可視范圍最大的俯仰角調(diào)整與通過(guò)智能算法對(duì)多個(gè)傳感器調(diào)整其位置與朝向，最終使得在給定的區(qū)域范圍內(nèi)減少重疊區(qū)域的覆蓋于盲區(qū)，提高覆蓋率。

1 問(wèn)題分析

1.1 視頻傳感器感知模型

參考文獻(xiàn)[8]中的球形傳感器模型與文獻(xiàn)[13-14]中的傳統(tǒng)三維模型可得，在三維現(xiàn)實(shí)場(chǎng)景中，視頻傳感器模型可以感知到傳感器為中心最大感知距離為半徑的球形區(qū)域；同時(shí)結(jié)合實(shí)際情況，監(jiān)控?cái)z像機(jī)存在最大水平視角與最大垂直視角的限制，所以將傳感器的模型定義為底面為球形其余四個(gè)面為扇形的立體圖形，如圖1所示。

圖1 空間感知模型

定義一：傳感器模型與參數(shù)。

定義二：定義可視區(qū)域范圍與各坐標(biāo)點(diǎn)。

圖2 有效感知區(qū)域

對(duì)于單個(gè)傳感器來(lái)說(shuō)，其偏向角所在平面與俯仰角所在平面相互垂直，調(diào)整傳感器的偏向角度并不能影響傳感器的有效感知區(qū)域。因此在傳感器高度固定的情況下，影響單個(gè)傳感器有效感知區(qū)域的因素為傳感器布置的俯仰角度。

如圖3所示，面PD1D2為傳感器整體可視范圍在坐標(biāo)系xoz面上的截面，由于傳感器可視范圍的底面為球形，面PD1D2為扇形。通過(guò)調(diào)整傳感器的俯仰角度影響的是上交面梯形的上下兩底之間的距離F1F2與下交面兩底之間的距離E1E2，所以該文通過(guò)分析在截面PD1D2內(nèi)，F(xiàn)1F2與E1E2隨俯仰角變化的關(guān)系，進(jìn)而分析出最佳俯仰角使得傳感器的有效三維感知區(qū)域最佳。

圖3 三維感知模型截面

1.2 視頻傳感器的覆蓋增強(qiáng)分析

為了方便計(jì)算，將監(jiān)控區(qū)域離散化為每隔ΔxΔyΔz選取一個(gè)離散點(diǎn)，這樣將連續(xù)空間覆蓋問(wèn)題就轉(zhuǎn)化為離散空間的覆蓋問(wèn)題。假設(shè)空間離散后對(duì)應(yīng)的點(diǎn)集為Ω，所有至少被一個(gè)傳感器有效空間覆蓋的點(diǎn)的集合為Ω'，則覆蓋區(qū)域的覆蓋率η定義為:

(1)

假設(shè)對(duì)區(qū)域布撒n個(gè)傳感器，第i個(gè)傳感器的參數(shù)Ti={pi,Ci}包括傳感器的位置Pi(x,y,z)，傳感器的朝向Ci(λ,θ)，則覆蓋增強(qiáng)是對(duì)所有變量組η(T1,T2,…,Tn)'≥η(T1,T2,…,Tn)。

2 覆蓋增強(qiáng)策略

2.1 基于單個(gè)傳感器俯仰角調(diào)節(jié)

為了便于研究，同時(shí)結(jié)合現(xiàn)實(shí)世界的設(shè)備，假設(shè)所有視頻傳感器同構(gòu)且布置在相同高度的平面之內(nèi)。由圖4可知，該文通過(guò)分析在扇形PD1D2中F1F2與E1E2隨俯仰角變化的關(guān)系來(lái)求得傳感器的最佳俯仰角度。

圖4 感知模型截面

由于在直角三角形PP'E2中，PP'為傳感器的布置高度Z，PE2為傳感器的最大可視距離L，這兩個(gè)值不會(huì)隨著傳感器的俯仰角度的變化而變化。

(2)

F1F2=(Z-H)tan(γ+β)-(Z-H)tan(γ-β)

(3)

由于有效檢測(cè)區(qū)域?yàn)樨Q直空間，所以有效區(qū)域?yàn)樵趚oz面上的截面E1E3F2F3,其中:

F3F2=E1E3=(Z-H)tan(γ+β)-Ztan(γ-β)

(4)

通過(guò)對(duì)上式中的γ求導(dǎo)得：

E1E3'=(Z-H)sec2(γ+β)-Zsec2(γ-β)

(5)

根據(jù)實(shí)際情況分析，一般布置情況下有(γ+β)>45°，(Z-H)>0.5Z，當(dāng)(γ+β)>45°時(shí)sec2(γ+β)>2，所以有(Z-H)sec2(γ+β)>Z；而(γ-β)的值一般情況下較小，且保持sec2(γ-β)≈1，所以有E1E3'=(Z-H)sec2(γ+β)-Zsec2(γ-β)≥0。

通過(guò)分析可得，F(xiàn)3F2與E1E3為隨著俯仰角γ的遞增函數(shù)，當(dāng)點(diǎn)E3與E2重合的時(shí)候，F(xiàn)3F2與E1E3達(dá)到最大值，即有效監(jiān)測(cè)區(qū)域值最大。

當(dāng)點(diǎn)E3與E2重合時(shí)有：

(6)

通過(guò)上述公式可求得傳感器節(jié)點(diǎn)的最佳俯仰角。

2.2 多傳感器位置及偏向角調(diào)節(jié)

通過(guò)俯仰角優(yōu)化后的傳感器空間中的最佳有效覆蓋區(qū)域如圖5所示，進(jìn)一步調(diào)整多個(gè)傳感器的位置與偏向角度使得對(duì)區(qū)域的覆蓋范圍最大化，對(duì)于偏向角與位置的優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題。粒子群優(yōu)化算法作為群體智能進(jìn)化算法，具有求解速度快、質(zhì)量高等優(yōu)勢(shì)，因此將粒子群智能算法引入傳感器覆蓋增強(qiáng)中[14]。該文以傳感器覆蓋率為優(yōu)化目標(biāo)，通過(guò)粒子群算法搜索傳感器的全局最優(yōu)分布，調(diào)整傳感器的位置與水平方向角來(lái)降低重疊感知區(qū)域與檢測(cè)盲區(qū)，實(shí)現(xiàn)傳感器的覆蓋增強(qiáng)。

圖5 有效感知區(qū)域

圖中的立體圖形的上下兩底相互平行，由于圖形完全豎直，兩底之間的距離為任務(wù)要求檢測(cè)的高度，所以對(duì)于圖5中的立體圖形在空間中的布置可以簡(jiǎn)化為平面ABCD在任務(wù)要求的水平面中的布置。

假設(shè)在給定的區(qū)域內(nèi)隨機(jī)布置傳感器數(shù)量為Num個(gè)，則節(jié)點(diǎn)的初始解向量空間為a1(Q11,Q12,…,Q1Num)，由于傳感器的俯仰角度與高度已經(jīng)確定，所以a1d=Q1d(x1d,y1d,θ1d)為每個(gè)傳感器在空間中的水平位置與水平俯仰角。設(shè)置粒子群的規(guī)模數(shù)為n，搜索空間為(a1,a2,…,an)。

粒子i的目標(biāo)函數(shù)為：

fi=η(ai1,ai2,…,aiNum)

(7)

目標(biāo)函數(shù)fi表示對(duì)應(yīng)的粒子ai在Num個(gè)傳感器下的空間覆蓋度。

計(jì)算粒子規(guī)模內(nèi)的最大目標(biāo)函數(shù)值并記錄為全局最優(yōu)值：

fmax=max(f1,f2,…,fn)

(8)

粒子群的迭代函數(shù)為：

(9)

其中，pid為粒子i的歷史最佳情況下的傳感器d的位置參數(shù)，gad為粒子全局最佳情況下對(duì)應(yīng)的傳感器d的位置參數(shù)，設(shè)初始值為初始情況下的值作為當(dāng)前每個(gè)粒子的最優(yōu)解，并記錄當(dāng)前位置作為局部最優(yōu)位置。aid(t)與vid(t)分別為第t次迭代中粒子i的傳感器位置參數(shù)與位置參數(shù)的改變量。ω為慣性因子，體現(xiàn)了第t+1次迭代的vid被上一代vid影響的大小。通過(guò)對(duì)ω進(jìn)行改進(jìn)，使得在迭代初期ω的值基本不變，非常有利于全局搜索。而后期變化緩慢，更利于得到或者接近全局最優(yōu)值[15]。其中t為當(dāng)前的迭代次數(shù)，r1、r2為[0,1]之間的隨機(jī)數(shù)，c1、c2為學(xué)習(xí)因子，分別調(diào)節(jié)粒子歷史最優(yōu)與全局最優(yōu)的影響程度。

粒子群算法流程如下：

步驟一：初始化節(jié)點(diǎn)位置(xi,yi)、數(shù)量Num、水平朝向角度θ、區(qū)域范圍、粒子維度D、規(guī)模N、迭代次數(shù)，初始化每個(gè)粒子，每個(gè)粒子是Num個(gè)傳感器在給定區(qū)域的布置，而每個(gè)傳感器又包括三個(gè)維度的解，即每個(gè)粒子的解的維度為3 Num。

步驟二：判斷是否滿(mǎn)足終止條件，如果滿(mǎn)足，則算法結(jié)束，否則繼續(xù)。

步驟三：利用式(9)更新粒子群算法中的粒子位置與速度。

步驟四：計(jì)算各粒子的目標(biāo)函數(shù)值即區(qū)域的覆蓋率η。

步驟五：更新各粒子的歷史最佳位置和全局最佳位置。

步驟六：返回步驟二。

3 仿真實(shí)驗(yàn)及分析

則通過(guò)傳感器俯仰角調(diào)整公式(6)可得最佳俯仰角γ=40.9°，之后求得有效覆蓋面的各參數(shù)代入粒子群算法。算法訓(xùn)練過(guò)程如圖6所示。

圖6 算法訓(xùn)練過(guò)程

通過(guò)實(shí)驗(yàn)分析，在傳感器的初始布置圖7中，傳感器的布置有些區(qū)域較為密集，有些區(qū)域則較為稀疏，覆蓋率為59.5%。如圖8所示，通過(guò)PSO算法調(diào)整傳感器的位置與朝向，傳感器的布置均勻，同時(shí)覆蓋率也提升為82%，覆蓋率提升了22.5個(gè)百分點(diǎn)，說(shuō)明通過(guò)該算法可以有效地提高傳感器在空間中的覆蓋率。

圖7 初始布置圖

圖8 調(diào)整后分布圖

同時(shí)在感知區(qū)內(nèi)通過(guò)算法調(diào)整不同的節(jié)點(diǎn)數(shù)所對(duì)應(yīng)的覆蓋度的變化，由圖9可知，當(dāng)節(jié)點(diǎn)數(shù)超過(guò)80個(gè)之后，覆蓋率隨節(jié)點(diǎn)的變化變得緩慢。由文獻(xiàn)[14]實(shí)現(xiàn)了只調(diào)節(jié)傳感器水平偏向角而不調(diào)節(jié)傳感器位置的算法TDPCA，對(duì)比可知，對(duì)位置及水平偏向角的調(diào)節(jié)結(jié)果優(yōu)于只調(diào)節(jié)傳感器水平偏向角的結(jié)果。由圖中點(diǎn)畫(huà)虛線還可以得出，只調(diào)節(jié)傳感器水平偏向角的算法結(jié)果的波動(dòng)性較大，這是由于該算法比較依賴(lài)傳感器布置的初始位置。

圖9 不同算法對(duì)比

4 結(jié)束語(yǔ)

對(duì)三維空間內(nèi)視頻傳感器覆蓋度的增強(qiáng)進(jìn)行了研究，結(jié)合已有模型提出三維有效模型，并將覆蓋度優(yōu)化問(wèn)題分為水平面與豎直面兩個(gè)方向。通過(guò)任務(wù)要求高度與傳感器的自身參數(shù)確定傳感器的最佳俯仰角，而后通過(guò)粒子群算法調(diào)整多傳感器水平方向上的位置及水平偏向角，最終使得多傳感器的覆蓋度得到優(yōu)化，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。