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

張 滿，賈云璐，林 杰

(中國工程物理研究院 機械制造工藝研究所，四川 綿陽 621000)

0 引 言

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

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

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

1 問題分析

1.1 視頻傳感器感知模型

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

圖1 空間感知模型

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

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

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

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

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

圖3 三維感知模型截面

1.2 視頻傳感器的覆蓋增強分析

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

(1)

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

2 覆蓋增強策略

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

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

圖4 感知模型截面

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

(2)

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

(3)

由于有效檢測區(qū)域為豎直空間，所以有效區(qū)域為在xoz面上的截面E1E3F2F3,其中:

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

(4)

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

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

(5)

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

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

當(dāng)點E3與E2重合時有：

(6)

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

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

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

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

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

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

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

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

(7)

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

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

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

(8)

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

(9)

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

粒子群算法流程如下：

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

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

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

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

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

步驟六：返回步驟二。

3 仿真實驗及分析

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

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

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

圖7 初始布置圖

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

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

圖9 不同算法對比

4 結(jié)束語

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