無線視頻傳感器網絡β-QoM目標柵欄覆蓋構建算法

郭新明，劉 蕊，謝 飛，林德鈺

（1.咸陽師范學院 計算機學院，陜西 咸陽 712000；2.貴州警察學院 計算機系，貴陽 550005；3.西安電子科技大學 前沿交叉研究院，西安 710071；4.西安市智能康復人機共融與控制技術重點實驗室（西京學院），西安 710123；5.南昌大學 軟件學院，南昌 330047）

0 引言

覆蓋技術是確保無線傳感器網絡（Wireless Sensor Network，WSN）信息采集準確性和完整性的一項關鍵技術，也是WSN 服務質量的重要指標之一［1］。柵欄覆蓋是WSN 的重要覆蓋技術之一，主要用于檢測非法穿越WSN 覆蓋區域的入侵行為［2］。目標柵欄覆蓋由Lalama 等［3］首次提出，主要研究大型監測對象周圍環狀區域中封閉柵欄的構建問題，是WSN 柵欄覆蓋研究的一個新領域。

封閉柵欄的概念最早出現在文獻［4］中，針對封閉環狀區域的柵欄覆蓋問題，假設封閉環狀區域一定存在合法的斷點，進而將它轉換為非封閉區域的柵欄構建問題進行求解。文獻［5］中針對環形WSN 中入侵行為合法性判定的問題，將從外向內被WSN 監測k次的入侵行為定義為非法入侵，在此基礎上提出了一種強k柵欄構建算法，有效過濾了環形監測區域的非法入侵行為。文獻［6］中針對三維空間中山地無線傳感器網絡的柵欄覆蓋問題，提出了一種基于等位區域的環狀柵欄構建算法，有效提高了復雜地貌環境下移動目標監測和軌跡追蹤的質量。文獻［7］中針對監測區的多目標柵欄覆蓋問題，提出了一個分布式的啟發式目標柵欄構建（Target-Barrier Construction，TBC）算法，將多個目標柵欄進行合并，形成包圍多個目標的封閉柵欄，在降低柵欄成員數量和消息交換量方面取得了良好的效果。文獻［8］中將WSN 監測區中的多目標柵欄覆蓋問題抽象為求解平面內點集的凸包問題，并提出了多目標柵欄的最優合并算法，該算法能以極小成本實現WSN 中多目標的柵欄覆蓋。文獻［9］利用文獻［8］中的成果實現了無人機殺蟲燈（Insecticidal Lamp Unmanned Aerial Vehicles，IL-UAVs）的最優部署，實驗結果表明該部署策略能勝任綠色農業害蟲防治工作。文獻［10］中針對存在部分天然屏障環境中的目標柵欄覆蓋問題，利用凸包吸引（Convex Hull Attraction，CHA）算法在出口和入口處構建柵欄來實現對目標的封閉監測。針對目標柵欄構建，文獻［4-10］中研究了全向感知模型的WSN 目標柵欄構建，但這些方法不適用于定向傳感網絡。

無線視頻傳感器網絡（Wireless Visual Sensor Network，WVSN）是一種典型的定向傳感網絡，目前在WVSN 中構建目標柵欄的研究還相對較少。文獻［3］中基于螺旋掃描的思想，設計了構建封閉視頻柵欄的螺旋外圍外覆蓋（Spiral Periphery Outer Coverage，SPOC）和螺旋外圍內覆蓋（Spiral Periphery Inner Coverage，SPIC）算法，在監測對象周圍的WVSN 中構建出監測非法入侵行為的封閉視頻柵欄。文獻［11］中針對可旋轉WVSN 目標柵欄的構建問題，利用虛擬目標柵欄構建（Virtual Target-Barrier Construction，VTBC）算法實現WVSN 的目標柵欄覆蓋，進而提出一個分布式粒子群優化（Distributed Particle Swarm Optimization，D-PSO）算法進一步優化視頻柵欄的覆蓋性能。文獻［12］中針對存在視覺障礙環境中的封閉柵欄覆蓋問題，提出了一種通過移動WVSN 中部分節點的方法圍繞監測目標構建出具有避障功能的封閉柵欄。文獻［3，11-12］中研究了WVSN 的目標柵欄構建問題，但卻未對視頻傳感器捕獲圖像的質量作任何要求，因此往往由于捕獲圖像質量過低導致入侵檢測失效。

為了改進WVSN 捕獲圖像的質量，文獻［13-16］中要求構建的WVSN 柵欄捕獲圖像質量必須不小于β監測質量（βQuality of Monitoring，β-QoM），但這些方法構建的柵欄不封閉，無法圍繞監測目標。在預警外敵入侵、保護珍稀野生動物等一些特殊應用環境中，要求在監測對象周邊一定范圍內部署大量視頻傳感器來獲取清晰可辨認的入侵者圖像。若能在監測對象周圍建立封閉的、捕獲圖像寬度大于β的WVSN 柵欄，自然可以實現這類監測的需求。針對該問題，本文提出了一個無線視頻傳感器網絡β-QoM 目標柵欄覆蓋（Wireless visual sensor networkβ-QoM Target-Barriers coverage Construction，WβTBC）算法，顯著改善了WSVN 入侵檢測的質量。主要工作如下：

1）建立了視頻傳感器β-QoM 區的幾何模型，并從理論上證明了質心進入視頻傳感器β-QoM 區的入侵者一定能被捕獲到寬度不小于β的圖像，為提高WVSN 入侵檢測的質量提供了理論依據；

2）證明了WVSN 中圍繞監測對象的最優β-QoM 目標柵欄覆蓋是NP-hard 問題；

3）設計了一個構建無線視頻傳感器網絡β-QoM 目標柵欄覆蓋的啟發式算法WβTBC，為WVSN 的非法入侵檢測提供了一種新型解決方案。

1 網絡模型及問題描述

1.1 網絡模型

為了研究β-QoM 目標柵欄覆蓋問題，本文定義了WVSN和入侵者的模型。WVSN 中所有視頻傳感器同構，除傳感器位置和朝向不同外，其余參數均一致。視頻傳感器感知區域是一個夾角為γ感知半徑為r的扇形區域，通信半徑R≥2r，每個傳感器均可以通過內置定位裝置或定位算法獲得自己的坐標位置（x，y）和視覺朝向d→，如圖1 所示。WVSN 的部署范圍是一個外圈邊長為L，寬度為W的正方形環帶區域，監測目標位于區域中心，WVSN 距離監測目標的安全距離不小于dsafe=(L-2W)/2，如圖2 所示。在該環帶區域內隨機均勻部署n個視頻傳感器，傳感器部署后，它的位置和視覺朝向均不發生改變。假設穿越WVSN 覆蓋區的入侵者為任意方向寬度不小于β(β?r)的凸多邊形，它的最大內切圓圓心稱為入侵者的質心，如圖3 所示。顯然，當入侵者內切圓的半徑r≥β/2，它的任意方向的寬度均大于等于β。

圖1 WVSN感知模型Fig.1 WVSN sensing model

圖2 WVSN部署范圍示意圖Fig.2 Schematic diagram of deployment scope of WVSN

圖3 入侵者幾何模型Fig.3 Geometric model of intruder

定義1β圓。以入侵者的質心為圓心，以β/2 為半徑的圓，稱為入侵者的β圓（如圖3 的虛線圓）。顯然，入侵者的β圓與它的最大內切圓同心，且被它包含。

1.2 問題描述

WVSN 的主要監測任務是獲取它的覆蓋范圍內移動對象的圖像，傳統的視頻監控應用只關注WVSN 能否捕獲到圖像，而對捕獲圖像的寬度沒有要求，因此在捕獲圖像寬度過窄的情況下WVSN 的監測功能將失效。本文假設只有當視頻傳感器捕獲圖像的寬度大于等于β時方可識別入侵對象。如圖4 所示，入侵者沿虛線所示軌跡穿越WVSN，視頻傳感器S1和S2均抓拍到入侵者的圖像，其中圖像寬度w1>β，而w2<β，因此S1能通過捕獲圖像識別出入侵對象，而S2由于捕獲圖像寬度過小而無法識別。由此可見，β-QoM 是影響WVSN 監測質量的一個關鍵因素。

圖4 視頻傳感器圖像監測失效示意圖Fig.4 Schematic diagram of visual sensor image monitoring failure

定義2 目標柵欄。視頻傳感器集合VS中所有傳感器的感知區域聯合構成了一個包圍監測對象的封閉環路，對于任意穿越該環路的入侵行為，至少能被VS中一個視頻傳感器感知，則集合VS為監測對象的一個目標柵欄，如圖5 所示。

圖5 目標柵欄入侵行為檢測示意圖Fig.5 Schematic diagram of target-barrier intrusion behaviour detection

目標柵欄在進行入侵行為檢測時，同樣存在由于捕獲圖像寬度過小而導致的非法入侵行為漏檢現象，因此WVSN 的目標柵欄覆蓋仍需考慮捕獲圖像寬度的約束。

定義3β-QoM 目標柵欄。對于沿任意軌跡入侵監測對象的入侵者，若監測對象的一個目標柵欄中至少有一個視頻傳感器捕獲的圖像寬度大于等于β，那么該目標柵欄稱為該監測對象的一條β-QoM 目標柵欄。

本文重點研究WVSN 中β-QoM 目標柵欄的構建問題，暫不考慮網絡的能耗和通信效率。

2 β-QoM目標柵欄覆蓋理論

2.1 單視頻傳感器的β-QoM圖像捕獲分析

由定義3 可知，β-QoM 目標柵欄對于任意入侵者至少存在一個視頻傳感器能捕獲到寬度大于等于β的圖像，因此需要研究視頻傳感器怎樣才能捕獲到β-QoM 的圖像。

定義4 視頻傳感器β-QoM 區。視頻傳感器的扇形感知區域內，與兩條邊的距離大于等于β/2，且與傳感器的距離小于等于的區域稱為該視頻傳感器的β-QoM 區，如圖6 陰影部分所示。

圖6 視頻傳感器β-QoM區Fig.6 Visual sensor β-QoM region

定理1 若入侵者的質心進入視頻傳感器的β-QoM 區，那么該視頻傳感器一定能捕獲到寬度大于等于β的入侵者圖像。

證明 由圖3 可知，入侵者的β圓被入侵者的凸多邊形包裹，只要入侵者β圓的任一條直徑線段出現在視頻傳感器的感知范圍內，那么該視頻傳感器就一定能捕獲到寬度不小于β的入侵者圖像。

至此，可知質心在視頻傳感器β-QoM 區邊界上的入侵者一定能被視頻傳感器捕獲到不小于β的圖像，而質心出現在視頻傳感器β-QoM 區內部時，該命題顯然成立。證畢。

2.2 目標柵欄的β-QoM圖像捕獲分析

目標柵欄覆蓋要求柵欄中所有視頻傳感器聯合實現非法入侵行為檢測，因此需要研究相鄰視頻傳感器的β-QoM 圖像捕獲問題。

定義5β鄰居。若視頻傳感器S1和S2的β-QoM 區相交，則傳感器S1和S2互為β鄰居。

定理2 若目標柵欄中所有相鄰視頻傳感器互為β鄰居，則該目標柵欄是β-QoM 目標柵欄。

證明 假設目標柵欄中所有相鄰視頻傳感器互為β鄰居，但該目標柵欄不是β-QoM 目標柵欄。

若目標柵欄不是β-QoM 目標柵欄，在目標柵欄上的某處一定存在一個薄弱點，從該薄弱點進入監測對象的入侵者不能被目標柵欄上的傳感器捕獲到寬度大于等于β的圖像。這說明覆蓋薄弱點的相鄰視頻傳感器的β-QoM 區一定不相交，不具有β鄰居關系，這與目標柵欄中所有相鄰視頻傳感器互為β鄰居矛盾。因此假設不成立，原命題成立。證畢。

2.3 WVSN最優β-QoM目標柵欄覆蓋分析

資源受限仍然是WVSN 的重要特征，為了節約資源，延長網絡生命周期，因此在WVSN 中組成β-QoM 目標柵欄的視頻傳感器應盡可能少。

定義6 最優β-QoM 目標柵欄覆蓋。若WVSN 的傳感器集合S={Si|i=1，2，…，n}的一個子集S'構成了一個圍繞監測對象的β-QoM 目標柵欄覆蓋，但不存在S的其他β-QoM 目標柵欄覆蓋子集Z，使 |Z|<|S'|，那么稱集合S'是監測對象的一個最優β-QoM 目標柵欄覆蓋。

定理3 WVSN 中監測對象的最優β-QoM 目標柵欄覆蓋是NP-hard 問題。

證明 對WVSN 的最優β-QoM 目標柵欄覆蓋作如下轉換。以監測對象中心為原點建立笛卡兒坐標系，將平面以原點為中心分成m個相等的角度空間，如圖7 所示。

圖7 最優β-QoM目標柵欄覆蓋Fig.7 Optimal β-QoM target-barrier coverage

用aij表示第i個角度空間與第j個傳感器間的覆蓋關系，1 ≤i≤m，1 ≤j≤n。如果傳感器j的感知區域與角度空間i的兩條邊相交，稱角度空間i被傳感器j覆蓋。如式（1）所示。

用bij表示傳感器i是否為傳感器j的β鄰居，1 ≤i≤n，1 ≤j≤n，如式（2）所示。

用xj表示傳感器（j1 ≤j≤n）是否在β-QoM 目標柵欄中：

至此，WVSN 中監測對象的最優β-QoM 目標柵欄覆蓋可以表示為如下的線性規劃形式：

式（4）表示構成β-QoM 目標柵欄的傳感器個數最少；式（5）表示每個角度空間至少被一個視頻傳感器覆蓋；式（6）表示每個傳感器只能有兩個β鄰居。如果將矩陣A和B定義為如下形式：

則式（4）～（7）可以表示成如下的矩陣形式：

其中：a為m維列向量；b、c、x為n維列向量。由式（10）～（13）可知，求解WVSN 中圍繞監測對象的最優β-QoM 目標柵欄覆蓋是NP-hard 問題［17］。證畢。

3 WβTBC算法設計

由定理3 可知，在WVSN 中構建監測對象的最優β-QoM目標柵欄覆蓋是一個NP-hard 問題，因此無法在多項式時間內求得該問題的最優解，但可以通過設計多項式時間的啟發式算法求得該問題的次優解。

3.1 算法設計思想

啟發式算法是基于直觀認識或經驗構造的算法。由于WVSN 最優β-QoM 目標柵欄是滿足捕獲圖像寬度要求的最少節點柵欄，因此最優β-QoM 目標柵欄實際上是一個最短環路問題，若能打破環路，就可用求最短路的方法在WVSN 中搜索最優β-QoM 目標柵欄的近似解。因此，求解的基本思想是先將WVSN 從監測目標的某一方向強制切斷，然后用Dijkstra 算法［18］在開放的WVSN 區域搜索β-QoM 柵欄，最后將斷點連接形成封閉柵欄。基于上述思想，首先根據節點間的β鄰居關系建立網絡的鄰接矩陣，然后在WVSN 中隨機找到一對β鄰居節點（G，H），以H為起點以G為終點利用Dijkstra 算法找到一條最短路徑，該路徑上的節點序列即為一個β-QoM 目標柵欄。但該方法存在漏洞，如圖8 所示，以S2為起點S1為終點搜索到了兩條封閉的柵欄，一條包圍了監測對象，而另一條由S2、S3、S4、S5、S1構成的封閉柵欄卻沒有包圍監測對象，本文將這種沒有包圍監測對象的封閉柵欄稱為假β-QoM 目標柵欄。

圖8 假β-QoM目標柵欄Fig.8 Fake β-QoM target-barrier

存在β鄰居關系的兩個傳感器節點的雙向性是假β-QoM目標柵欄產生的主要原因。為了使β-QoM 目標柵欄能包圍監測對象，需要對傳感器間的β鄰居關系進行單向性約束。

定義7 逆時針β鄰居。以監測對象中心為原點，如果傳感器S1和S2互為β鄰居，且S1出現在S2的逆時針方向，那么S1是S2的逆時針β鄰居，如圖9 所示。

圖9 逆時針β鄰居Fig.9 Counterclockwise β neighbor

本文用MaxA（S）和MinA（S）分別表示傳感器S覆蓋區相較于監測對象中心的最大角和最小角。為簡化邏輯，感知區域與X軸正方向相交的傳感器最大角應大于360°，如圖9（a）所示。一般認為如果視頻傳感器S1和S2的覆蓋區相交，且MaxA（S1）>MaxA（S2），則S1是S2的逆時針β鄰居，如圖9（b）所示；如果β鄰居中只有一個傳感器的覆蓋區域跨越X軸正方向，且滿足MinA（S1）≤MaxA（S2）mod 360°

3.2 β-QoM目標柵欄構建算法描述

根據上述思想，本文設計了一種在WVSN 中求解β-QoM目標柵欄覆蓋的啟發式算法WβTBC，它的偽代碼如下所示。

算法 WβTBC。

輸入S（WVSN 中的視頻傳感器集合）；

輸出BS（WVSN 的β-QoM 目標柵欄集合）。

3.3 時間復雜度分析

WβTBC 算法包含四個模塊：模塊一（第3）～5）行），清空所有傳感器節點的逆時針鄰居集，時間復雜度為O（n）；模塊二（第6）～19）行），根據節點的逆時針β鄰居關系建立網絡的鄰接矩陣，時間復雜度為O（n2）；模塊三（第21）行），運行Dijkstra 算法的時間復雜度是O（n2）；模塊四（第22）～33）行），在WVSN 中搜索β-QoM 目標柵欄，時間復雜度為O（n）。四個模塊在邏輯上并列，因此算法WβTBC 的時間復雜度為最大值O（n2）。

通過分析可知，文獻［3］中的算法SPOC 和SPIC 的時間復雜度至少是O（n3）；算法TBC 的時間復雜度為O（n）［7］。本文算法WβTBC 的時間復雜度優于算法SPOC 和SPIC，但是不及分布式算法TBC［7］。

4 仿真實驗與結果分析

4.1 實驗平臺構建

本文使用Matlab 2012a 搭建β-QoM 目標柵欄覆蓋的仿真實驗平臺，部署在監測對象周圍的WVSN 采用隨機均勻部署，實驗平臺的相關參數設置如表1 所示。

表1 實驗平臺的參數設置Tab.1 Parameter setting of experimental platform

4.2 仿真實驗與數據分析

實驗在WVSN 內部署視頻傳感器的數量從100 開始，步長為20，逐步遞增至1 000。為了增強實驗數據的可信度，同一部署規模擁有30 套不同的節點布局方案。按照已建立目標柵欄中的節點不再參與后續目標柵欄搜索的方法進行柵欄構建。圖10 是部署規模為500，β=20 m 時，WβTBC 算法在WVSN 中找到的3 條相互獨立的β-QoM 目標柵欄，圖10（a）的柵欄1 長度（l構成柵欄的節點數）最短，因此柵欄1 是該布局下找到的最優β-QoM 目標柵欄。

圖10 WβTBC算法仿真結果Fig.10 Simulation results of WβTBC algorithm

將WβTBC 算法分別與SPOC［3］、SPIC［3］和TBC［7］進行對比。由實驗數據分析可知，在能成功構建柵欄的前提下，算法WβTBC 需要的節點數更少，且分別比算法SPOC、SPIC 及TBC 節省了大約23.3%、10.8%和14.8%的傳感器節點，如圖11 所示。因為WβTBC 使用Dijkstra 算法搜索最短β-QoM目標柵欄，而SPOC 和SPIC 的螺旋掃描策略主要關注柵欄的連通性，沒有考慮柵欄長度的因素；TBC 構建的柵欄由4 個柵欄段拼接而成，由于沒有對整個目標柵欄作進一步優化，因此構建的目標柵欄長度較大。WβTBC 的節點高效性提高了網絡的節能效率，同時也延長了網絡的生存時間。

圖11 柵欄平均節點數對比Fig.11 Comparison of average nodes in barriers

然而，WβTBC 算法的柵欄構建成功率和平均構建柵欄數均低于SPOC 和SPIC，卻高于TBC，如圖12、13 所示。這是因為捕獲圖像的β寬度約束致使構建β-QoM 目標柵欄的視頻傳感器選擇范圍更小，因此WβTBC 構建柵欄的成功率和平均柵欄數比沒有圖像寬度要求的算法SPOC 和SPIC 偏低。TBC 算法由于構建目標柵欄需要在監測目標周圍找到4 個初始節點，限制了目標柵欄的搜索范圍，因此柵欄構建的成功率和平均柵欄數較低。圖14 表明4 種算法首次成功構建柵欄的網絡規模差距不大，而首次100%成功構建柵欄的網絡規模差距較大。在β-QoM 的約束下，相較于TBC 算法，WβTBC 算法構建目標柵欄的效率更高。

圖12 柵欄構建成功率對比Fig.12 Comparison of success rate of barrier construction

圖13 平均構建柵欄數對比Fig.13 Comparison of average constructed barriers

圖14 構建柵欄不同階段的網絡規模對比Fig.14 Comparison of network scales at different stages of barrier construction

WβTBC 在不同的β值下，算法性能也不盡相同。隨著β值減小，構建β-QoM 目標柵欄的成功率隨之增高（如圖15 所示）。這是由于β值越小，視頻傳感器就可能擁有更多的逆時針β鄰居，那么成功構建β-QoM 目標柵欄的概率就越大，自然柵欄構建的成功率會增高。另外，在網絡覆蓋面積不變的情況下，隨著部署節點的增多，節點密度隨之增大，致使節點的逆時針β鄰居增多，提高了成功組建柵欄的幾率，同時也減弱了β值對成功構建β-QoM 目標柵欄的影響。因此隨著網絡節點密度的增大，構建β-QoM 目標柵欄的成功率不斷提高，而β值對成功構建柵欄的影響則逐漸減弱。

圖15 不同β的β-QoM目標柵欄構建成功率Fig.15 Success rates of β-QoM target-barrier construction with different β

由圖16 可知，β越小，構成β-QoM 目標柵欄的平均節點數越少；具有β鄰居關系的兩個節點就能擁有越大的距離。根據本文鄰接矩陣的定義，歐氏距離越大的節點序列在Dijkstra 算法中更具優勢，因此β值越小，形成β-QoM 目標柵欄的節點就可能越少。

圖16 不同β的β-QoM目標柵欄平均節點數Fig.16 Average nodes of β-QoM target-barriers with different β

5 結語

本文針對WVSN 中目標柵欄因捕獲圖像寬度不足造成的入侵檢測失效問題，提出了WβTBC 算法。實驗結果表明，該算法能在WVSN 中構建β-QoM 目標柵欄，相較于SPOC、SPIC 及TBC，節點利用效率更高。在入侵者捕獲圖像寬度滿足要求后，β值越小，WβTBC 構建β-QoM 目標柵欄的成功率越高，構成柵欄的節點越少，因此，在不影響入侵檢測質量的情況下，β值應盡可能小。本文研究僅針對靜態WVSN 環境，沒有考慮動態WVSN 的應用環境，研究動態無線視頻傳感器網絡β-QoM 目標柵欄的構建問題，將是下一步的重點工作。