三維無線多媒體傳感器網絡全目標覆蓋算法

王艷嬌，畢曉君，滕志軍，鄔春明

（1.東北電力大學 信息工程學院，吉林省 吉林市132012；2.哈爾濱工程大學 信息與通信工程學院，哈爾濱150001）

0 引 言

隨著無線多媒體傳感器網絡（Wireless multimedia sensor networks，WMSNs）研究的深入和實際應用的擴展［1－3］，為增強相應覆蓋控制算法的實用性和有效性［4－5］，一些學者致力于構建能夠描述無線多媒體傳感器節點真實感知能力的感知模型。Ma等［6］于2005 年首先設計了基于節點坐標、感知半徑、感知方向和感知角度的扇形感知模型，此后，Makhoul等［7－8］先后提出三角形和凸多邊形感知模型。其中，扇形感知模型能夠較好地描述節點感知性能并且最為簡單，是目前最具代表性、應用最多的一種感知模型，但是這些二維有向感知模型由于受到空間局限性以及與真實三維環境之間存在本質差別等因素的影響，無法準確描述節點的空間感知能力，使得基于此展開的覆蓋控制方法與實際應用之間存在不小的技術偏差?；诖?，某些研究者試圖建立面向真實環境的更為準確的三維有向感知模型，如：Ma等［9］于2009年首次提出基于傳感器節點位置、主感知方向、水平方向感知范圍和垂直方向感知范圍的多媒體傳感器節點三維感知模型；文獻［10］對上述模型進行改進，將主感知方向正交分解為仰俯角和偏向角，大幅降低了計算復雜度。

上述三維有向感知模型雖已具備一定的空間刻畫能力，但是其空間覆蓋區域與傳感器的高度無關，且當其處于某些主感知方向時在二維平面內的覆蓋區域沒有邊界限制，不符合人們的主觀認知，此外，無法適應實際三維物理環境的不規則表面覆蓋等問題，還不能準確描述節點的感知性能。為此，本文提出一種新的三維有向感知模型。在此基礎上，針對典型目標覆蓋問題［11］，即求出覆蓋全部目標所需的最小傳感器數目，設計了一種基于仰俯角優化和偏向角優化的新型目標覆蓋算法。仿真結果表明：對比隨機部署的方法，本文方法所需的傳感器數目大幅下降且比較穩定。

1 新型三維有向感知模型

多媒體傳感器節點處于三維物理場景，節點僅能覆蓋球形區域的一部分。本文受傳統傳感器節點的三維模型建立方式（即將二維平面內的圓節點模型旋轉拓展至空間得到球形三維感知模型）的啟發［12］，將多媒體傳感器感知模型中應用最廣的扇形模型繞節點旋轉一定角度構建新型多媒體傳感器三維有向感知模型，具體定義如下：

定義1 多媒體傳感器三維有向感知模型可用一個五元數組（P，C，α，β，R）表示，其中，C 為主感知方向（與Z 軸夾角稱為仰俯角γ，在X－Y 平面投影為偏向角θ），2α、2β和R 分別為水平感知角度（水平視域）、垂直方向感知角度（垂直視域）和感知半徑。

為充分理解本文所提三維有向感知模型的定義，這里給出其具體描述如圖1所示。

圖1 新的三維感知模型Fig.1 Novel three－dimensional directional perception model

由上述模型可見，其在二維平面內的最大覆蓋 范 圍 為 距 點P′（P 在X－Y 平 面 內 投 影）以內，且隨著傳感器被放置高度的增加，覆蓋范圍逐漸減小，符合人們的主觀認知，充分克服了現有兩種三維有向感知模型的缺陷，能夠更加真實地描述節點感知能力。

2 面向新型三維有向感知模型的目標覆蓋問題

定義2 本文研究的目標覆蓋問題是指，為實現對二維平面內存在的N 個目標的全面有效監測，在三維場景中隨機布撒M 個參數完全相同的傳感器，求出覆蓋所有目標需要開啟工作的最少傳感器數目。

對應于本文提出的三維有向感知模型，影響節點覆蓋能力的可控變量為主感知方向，那么相應的目標覆蓋算法就是求解包含仰俯角和偏向角的 一 個 最 優 組 合［（γ1，θ1），（γ2，θ2），…，（γM，θM）］，在覆蓋所有目標的同時，所用變量數目最少。

為了便于數學分析，這里給出其相應的數學定義，具體如下：

式中：S′為所選的傳感器集合；A 和S 分別為目標集合和傳感器集合；a為某目標；xijk為傳感器i工作在仰俯角j 和偏向角k 的主感知方向上。約束條件保證所有目標都被覆蓋以及每個傳感器至多工作在一個方向上。

確定目標是否被節點覆蓋是從數學上解決覆蓋問題的關鍵，為此，這里需明確本文提出的三維有向感知模型的目標覆蓋條件。

按照該模型的定義，其在水平監測區域的投影相當于一個扇形繞頂點旋轉后的橫截面，具體如圖2所示。

圖2 三維有向感知模型的橫截面圖Fig.2 Cross－sectional figure of novel three－dimensional directional perception model

受到α和β 的限制，不同的仰俯角只會獲得如圖2所示的圖形中的一部分，通過推導發現水平監測區域會出現如圖3所示的6種投影圖形。

圖3中γ1和γ2分別對應于如圖4所示的兩種臨界狀態，滿足如下關系：

限于篇幅，這里僅以最為復雜的投影圖形（圖3（e））為例說明目標節點的覆蓋判別方法。為便于分析說明，給出圖3（e）相應的空間位置分布，如圖5所示。其中，∠P′PO3＝γ＋β、PP′＝z、∠P′PO1＝β－γ、PD4＝PD6＝R、∠D1PO1＝∠N2PP′＝∠D4PO2＝∠D6PO3＝α。

判斷目標是否被節點覆蓋的方法如下：在滿足式（2）的基礎上，位于D5D3N1N2D4D6內部（即在有向線段D5D6的右側、有向線段N1D3右側、N1N2左側及N2D4左側），或處于四邊形D1D2N1N2內（在有向線段D1D2右側、D2N1右側、N1N2右側及N2D1右側）。

圖3 水平投影情況Fig.3 Horizontal projection situation

圖4 臨界條件示例Fig.4 Critical condition

圖5 圖3（e）的空間信息Fig.5 Spatial information of Fig.3（e）

以判斷目標T（X′，Y′）在有向線段D5D6左側或右側為例說明判別上述位置關系的實施方法，具體如下：目標T 關于P′的相對坐標為T′（X′－x，Y′－y）＝T′（x0，y0），D5、D6的坐標分別記為（xD5，yD5）、（xD6，yD6）。若D1＞0，在有向線段D5D6的右側；否則在該有向線段左側。其中，A1＝yD6－yD5、B1＝xD5－xD6、C1＝xD6yD5－xD5yD6、D1＝A1x0＋B1y0－C1。

為實施上述目標覆蓋方案，必須明確圖5中處于二維平面內的相應各點坐標，具體如下：

其中：

3 面向新型三維有向感知模型的目標覆蓋算法

對于本文設計的多媒體傳感器三維感知模型，為實現所有目標的有效覆蓋，如果直接同時優化主感知方向中的仰俯角和偏向角，復雜度過高，對算法效率等要求過高，難以求得滿意結果?？紤]到主感知方向中的仰俯角γ影響其在水平方向的投影覆蓋面積，偏向角θ影響其投影圖形的朝向。如果調整仰俯角γ保證每個傳感器在水平方向的覆蓋面積最大，就可以使每個傳感器覆蓋盡可能多的目標，再綜合調整各傳感器投影圖形的朝向，就可以達到目標覆蓋算法的要求，即用盡量少的傳感器覆蓋所有的目標，復雜度大幅降低?；谏鲜龇治?，將目標覆蓋算法分成仰俯角優化和偏向角優化兩部分。

3.1 仰俯角優化

仰俯角γ的大小決定傳感器在水平方向的投影覆蓋面積大小，投影覆蓋面積越大，傳感器所能覆蓋的目標就會越多，越有利于用較少的傳感器覆蓋所有的目標。這里把投影覆蓋面積達到最大的仰俯角稱為最優仰俯角。

由圖3中的三維感知模型的水平投影情況可以看出，當γ2＜2β時，只會出現圖3（a）（b）的情況，投影面積最大時對應圖3（b）的情況，此時，γ＋β＝γ2，即γ＝γ2－β；而當γ2＞2β時，投影面積最大應出現在圖3（d）（e）和（f）中，而圖3（d）（f）對應的最佳仰俯角為γ＝γ2－β和γ＝γ1－β，可以看作是圖3（e）的邊界情況。為此僅計算圖3（e）面積即可求出最優仰俯角。

由圖3（e）的空間位置關系（見圖5）可得到其在二維平面內的投影圖形的面積計算公式，具體表述為：

式（3）是非線性的復雜函數，傳統數學方法（如梯度下降法、最小二乘法等）很難求得理想結果，進化算法由于不受函數形式限制，越來越多地應用于此類問題的求解。差分進化算法［13］就是該領域最具前沿、最有代表性的算法，大量實驗及文獻指出該方法的連續函數優化性能已超越現有較為優秀的遺傳算法、粒子群算法等，為此，這里采用差分算法求解最優γ使S 最大。

3.2 偏向角優化

經仰俯角優化后，各個傳感器節點都具有固定的、最大覆蓋面積的投影圖形，如果隨機獲取偏向角，某些節點很可能未覆蓋任何目標或者相鄰的多個節點覆蓋相同目標，造成資源浪費，不符合目標覆蓋算法的設計要求。為此，必須優化偏向角調整各節點的投影圖形朝向，它的調整受到相鄰節點的彼此制約，是一個非常復雜的NP－Hard問題。其數學本質是優化各個傳感器節點的偏向角，在這種狀態下，挑選其中的kk 個傳感器（kk最?。崿F覆蓋全部目標的目的。鑒于差分進化算法的優化優勢，這里也采用該方法優化節點偏向角。該問題與普通優化問題不同的是，其適應度函數不具有明確的數學形式。為此，本文根據實際需求建立如下兩種適應度函數求解方式。

方式一：利用進化算法求解。

基于上述分析可知，該問題的適應度為挑選最優的部分傳感器實現目標覆蓋，可以通過如下方式實現：優化傳感器順序，達到所有目標被完全覆蓋的前kk 個傳感器就是該問題最終選擇的傳感器組合，而kk 就是適應度值。這一實現方式本身就是一個組合優化的過程，對于此類問題，現在廣泛采用遺傳算法（Genetic algorithm，GA）進行求解，鑒于該問題與TSP 問題的本質相似性，對于各種改進GA，這里選用實數編碼、交換序交叉操作的遺傳算法［14］求取適應度值。

方式二：隨機計算。

隨機計算的方式如下：設置一定的循環次數，在每次循環中，隨機產生一個傳感器順序，從第一個傳感器開始，逐個保留使覆蓋目標增多的傳感器，直至達到所有目標被有效覆蓋，參與計算的傳感器數目就是該問題的適應度值。

對比兩種適應度計算方式可以發現：方式一的結果更為準確，但是計算復雜、耗時長、不適宜大規模問題的求解；方式二的結果雖然不一定是最優的，但是計算簡單，適合于大規模問題的求解。因此，在大規模目標覆蓋問題的求解中采用方式二計算適應度，而對于小規模目標覆蓋問題或對時間要求不高時，選用方式一精確計算適應度值。

3.3 目標覆蓋算法

利用優化算法實現面向三維有向感知模型的無線多媒體傳感器網絡的目標覆蓋的步驟具體如下：

步驟1 初始化相關參數：區域邊界D；傳感器相關參數，包括β、α、γ和θ的取值范圍及傳感器數目M；目標數目N；種群數目PN；迭代次數Maxiter等。

步驟2 在區域內隨機布撒傳感器及目標。

步驟3 按3.1節中方法優化各傳感器仰俯角，得到最優仰俯角集合｛γ1，γ2，…，γM｝。

步驟4 初始化遺傳算法相關參數，產生有關傳感器偏向角的初始種群。

步驟5 采用3.2節中方法計算適應度值，即該種已定偏向角配合狀態下，達到目標覆蓋所需的最少傳感器數目。

步驟6 按照DE／current－to－best／1模式以及逐維單點交叉策略進行變異操作和交叉操作，得到新個體。

步驟7 按3.2節計算新個體的適應度值，并將其與原目標個體比較，保留適應度值更優個體。

步驟8 結合全部更優個體形成新的迭代種群。

步驟9 判斷是否滿足終止條件，若滿足，則輸出傳感器編號及相應仰俯角、偏向角；若不滿足，則轉至步驟6。

4 算法測試及結果分析

為充分驗證本文提出的面向三維感知的無線多媒體傳感器網絡的目標覆蓋算法的有效性和先進性，這里進行了大量實驗，所有實驗在硬件配置為Intel Centrino Duo，CPU：T7250、1G 內存、主頻為2.0 GHz 的計算機上進行，程序采用MATLAB R2007編寫。主要包括以下幾方面內容：①本文提出的算法能夠解決目標覆蓋問題；②驗證本文所提兩階段目標覆蓋方法的有效性；③將本文提出的目標覆蓋與其他幾種部署方法進行比較，說明本文方法的先進性。

實驗場景與文獻［10］一致：監測區域為500 m×500m 的矩形區域，傳感器參數完全相同，仰俯角，偏向角，水平感知視角和垂直感知視角均為120°，感知半徑為100 m，隨機布撒傳感器節點數目為M，高度信息z∈［5，12］，覆蓋N 個目標。

實驗一 驗證能有效解決目標覆蓋問題

不失一般性，這里模擬兩個目標覆蓋問題，隨機布撒參數完全相同的傳感器節點和目標，問題一和問題二中傳感器數目和目標數目分別為100、10和400、100。這兩個問題中傳感器和目標位置如圖6所示。

圖6 傳感器節點和目標節點的位置Fig.6 Position of the senor node and the target node

對于上述兩個目標覆蓋問題，利用本文算法優化后，所調用的傳感器在水平面的投影及相應覆蓋的目標如圖7所示。

圖7 本文算法處理目標覆蓋問題的效果Fig.7 Effect of the proposed targets coverage algorithm

本文算法參數設置如下：種群數目和迭代次數分別為50 和100，對于小規模目標覆蓋問題，即目標數目為10時，選用3.2節中方法一作為適應度計算方式，而對于目標數目為100的大規模覆蓋問題，適應度計算方式選為3.2節中方法二。

從圖7可以看出：經本文算法調整以后，對于小規模目標覆蓋問題，即目標數目為10時，僅用5個傳感器就能實現目標覆蓋；而對于大規模目標覆蓋問題，即目標數為100時，僅需要28個傳感器就可實現目標覆蓋。

由此可見，本文算法能夠解決目標覆蓋問題。

實驗二 驗證兩階段目標覆蓋方法的有效性

為驗證本文所提分步優化仰俯角和偏向角的目標覆蓋策略的有效性，將其與綜合調整主感知方向（即同時優化偏向角和仰俯角）的目標覆蓋方法進行比較。

固定目標數N 為10、20、30至100的位置，在各目標位置下傳感器數目都為200，兩種方法都采用3.2節中方法二計算適應度值，其中，綜合調整主感知方向的方法是指對俯仰角和偏向角統一進行優化。

鑒于公平性原則，當兩種算法處理相同問題時，即傳感器數目和目標數目相同時，保持傳感器和目標的位置相同，且保證算法的函數評價次數相同，此外，為避免隨機性對算法評價造成的不良影響，各算法都獨立運行10次。本文算法的參數設置如下：種群數目為50，迭代次數為100。在各種情況下，綜合調整主感知方向的方法以及本文所提算法覆蓋所有目標所需的傳感器節點數目如圖8所示。

圖8 兩種方法的性能比較Fig.8 Comparison of the performance of two methods

從圖8可以看出：在覆蓋少量目標時（如目標為10和20時），本文采用分別優化仰俯角和偏向角的目標覆蓋方法與直接調整主感知方向的方法所需傳感器數目相同，而隨著目標數目的增多，本文方法所需傳感器數目明顯減少，且目標數目越多優勢越明顯。這是由于對于不太復雜的小目標覆蓋問題，直接優化主感知方向的方法復雜度不是很高，一般方法尚且能夠滿足其復雜度要求，可求得較好結果，然而對于復雜情況，該方法的復雜度過高，對算法效率及運行機制要求過高，一般方法很難求得優異結果，而經本文方法簡化后，復雜度大幅降低，即可求得更佳結果。

綜上所述，對于復雜的目標覆蓋問題，與直接優化主感知方向的方法相比，本文所提仰俯角和偏向角分別優化的目標方法更為有效。

實驗三 驗證本文方法的先進性

鑒于目前并未見到基于三維有向感知模型的目標覆蓋算法相關成果發表，這里僅能將本文方法與隨機部署方法進行比較，其中，隨機部署方法是指俯仰角、偏向角在規定范圍內隨機變化，在某種部署狀態下，覆蓋所有目標所需的最少傳感器節點數目。為保證對比的全面性和完整性，這里進行復雜度和覆蓋效果兩方面的對比。對于時間復雜度的比較，限于篇幅，僅統計傳感器數目為200，目標數目分別為20、40、60、80及100時的算法運行時間。為對比的公平性，保證兩種方法的函數評價次數均為2000，兩種方法的時間復雜度比較如表1所示。為充分對比兩種算法的覆蓋效果，這里進行大量實驗，參數設置及實驗方式與實驗二相同，比較結果如圖9所示。

表1 傳感器數目為200時兩種方法的時間復雜度比較Table 1 Comparison of time complexity of the number of sensors＝200

圖9 兩種方法的性能比較Fig.9 Comparison of the performance of two methods

由表1中數據可以看出：無論是隨機方法還是本文方法，隨著目標數目的增多，算法的運行時間都有所增加，這是符合實際情況的。無論對于哪種目標覆蓋情況，與隨機方法相比，本文方法所需的時間都略長，但相差不大，且目標數目越多，兩者之間的差別越少。

由圖9可以得到以下結論：①目標數目相同時（見圖9（b）），無論是隨機部署還是本文所提算法，當傳感器數目增加時，所需的傳感器數目都會減少，這是因為當傳感器部署密度增大時，會使一些傳感器的某些方向更加“優秀”，即占據更好的位置，從而能覆蓋更多的目標點并使許多邊緣目標點集中化；②布撒相同數目傳感器節點時（見圖9（a）），目標數目越多，達到目標覆蓋所需的傳感器數目也越多，這與實際情況也是一致的；③無論上述哪種覆蓋情況本文方法所需的傳感器數目都比隨機部署要少，特別地，當目標數目為40、隨機拋撒傳感器數目為50或60時，隨機方法很難實現全目標覆蓋，而本文方法可以求得較為滿意的結果，且情況越為復雜，本文算法的優越性越明顯。

綜上所述，與隨機部署方法相比，本文建立的基于仰俯角和偏向角優化的兩階段目標覆蓋算法所需時間略長，但覆蓋效果的優勢十分明顯。

為進一步驗證本文采用差分進化算法對仰俯角和偏向角進行優化的正確性，將其與模擬退火方法、遺傳方法以及粒子群算法進行比較。固定目標數N 為25、75和125的位置，在各目標位置下改變傳感器數目為150、250和350，模擬不同的目標覆蓋問題。具體參數設置及實驗方式同上，其性能比較結果（包括算法精度、效率和穩定性）如表2所示。

表2 四種目標覆蓋方法的性能比較Table 2 Comparison of performance of four targets coverage algorithms

從表2中數據可以得出以下結論：

（1）在所求解精度方面，當覆蓋目標數目較少時（如目標數目為25），本文方法所需傳感器數目明顯比其他3種方法更少，而隨著目標數目的增加，4種方法所用傳感器數目相差不大，本文算法所需數目略少，說明本文方法在覆蓋效果方面具有一定優勢。這是由于在目標數目較少時，本文方法由于自身運行機制較好，能夠突破其他幾種方法在一定程度上陷入局部最優的僵局、并快速收斂到較優結果，而隨著目標數目的增多，問題復雜度急劇增高，對算法要求也越高，幾種方法的運行效率都有所下降。

（2）在穩定性方面，本文方法在處理小目標覆蓋問題（如目標數目為25）時，算法十分穩定，每次都能取得最優結果，而對于大目標覆蓋問題，與其他3種方法的方差相差不大，都較小，說明本文方法相對十分穩定。

（3）在運行效率方面，對于相同的覆蓋問題，在相同函數評價次數內，本文方法的運行時間明顯小于其他3種方法，說明本文方法在運行效率方面優勢明顯。

綜上所述，與采用其他方法執行進化策略的目標方法相比，本文方法能更為穩定地獲得優異結果，且在運行效率方面優勢明顯，說明了本文選擇差分進化算法作為進化策略構建目標覆蓋算法的正確性。

5 結束語

鑒于現有的多媒體傳感器網絡目標覆蓋算法都是針對理想的二維感知模型設計的，其理論研究結果與實際應用之間存在較大的技術偏差，本文從實際角度出發，在現有三維感知模型中加入感知范圍，提出一種新型三維感知模型，并設計了一種基于仰俯角優化和偏向角優化的目標覆蓋算法。實驗仿真結果表明，與隨機部署方法相比，本文方法能夠用更少的有向傳感器節點實現所有目標的覆蓋。由此可見，本文提出的目標覆蓋算法能夠有效解決目標覆蓋問題，具有一定的工程應用前景。

［1］Khuntia P，Pattnaik P K.Target coverge management protocol for wireless sensor network［J］.Journal of Theoretical and Applied Technology，2012，35（1）：20－25.

［2］Yang L，Xin H.Research on key technologies to target coverage algorithm in wireless sensor networks［J］.International Journal of Digital Content Technology and its Applications，2012，6（17）：542－550.

［3］凡高娟，孫麗娟，王汝傳，等.距離輔助的無線傳感器網絡節點覆蓋判別模型［J］.通信學報，2010，31（8）：127－133.Fan Gao－juan，Sun Li－juan，Wang Ru－chuan，et al.Distance－assistant node coverage identification model for wireless sensor networks［J］.Journal on Communications，2010，31（8）：127－133.

［4］Wang X，Ma J J，Wang S.Distributed energy optimization for target trackong in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2009，9（1）：73－86.

［5］Ai C，Santosh K，Ten H L.Local barrier coverage in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2010，10（4）：491－504.

［6］Ma Hua－dong，Liu Yong－he.Correlation based video processing in video sensor networks［C］∥2005International Conference on Wireless Networks，Communications and Mobile Computing，New York，USA，2005：987－992.

［7］Makhoul A，Saadi R，Pham C.Coverage and adaptive scheduling algorithms for criticality management on video wireless sensor networks［C］∥The 4th ACM Int＇l Workshop on Performance Monitoring，Measurement，and Evaluation of Heterogeneous Wireless and Wired Networks，St.Petersburg，2009：54－60.

［8］Adriaens J，Megerian S，Potkonjak M.Optimal worst－case coverage of directional field－of－view sensor networks［C］∥Proc of the 3rd Annual IEEE Conf on Sensor，Mesh and ad hoc Communications and Network，Reston，VA，2006：336－345.

［9］Ma H D，Zhang X，Ming A L.A coverage－enhancing method for 3Ddirectional sensor networks［C］∥Proceeding of 28th IEEE Conference on Computer Communications IEEE INFOCOM 2009，Washington，2009：2791－2795.

［10］肖甫，王汝傳，孫麗娟，等.一種面向三維感知的無線多媒體傳感器網絡覆蓋增強算法［J］.電子學報，2012，40（1）：167－172.Xiao Fu，Wang Ru－chuan，Sun Li－juan et al.Coverage－enhancing algorithm for wireless multi－media sensor networks based on three－dimensional perception［J］.Acta Electronica Sinica，2012，40（1）：167－172.

［11］Jian W，Changyong N，Ruimin S.Priority－based target coverage in directional sensor networks using agenetic algorithm［J］.Computers and Mathematics with Applications，2009，57（1）：1915－1922.

［12］任秀麗，程艷蕾，徐澤明.無線傳感器網中三維覆蓋控制和節點調度的研究［J］.小型微型計算機系統，2012，33（8）：1681－1684.Ren Xiu－li，Cheng Yan－lei，Xu Ze－ming.Coverage control and node－scheduling for three－dimensional wireless sensor networks［J］.Journal of Chines Computer Systems，2012，33（8）：1681－1684.

［13］Tatih T M，Bulut O，Quan P，et al.A differential evolution algorithm for median cycle problem［C］∥2011 IEEE Symposium on Differential Evolution（SDE），Paris，France，2011：1－7.

［14］Herera F，Lozano M.Gradual distributed real－coded genetic algorithms［J］.IEEE Transaction on Evolutionary Computation，2000，4（1）：43－63.