尤炳棋，徐向華，王 然

(杭州電子科技大學 計算機學院，浙江 杭州 310018)

在實際應用中，根據(jù)檢測對象的性質(zhì)，可將覆蓋問題大致分為3類，目標覆蓋[1-3]、區(qū)域覆蓋[4-6]、柵欄覆蓋[7-9]。覆蓋模型有全向覆蓋和定向覆蓋[10]。本文重點研究視頻傳感器網(wǎng)絡的柵欄覆蓋問題。

視頻傳感器與普通定向傳感器有較大不同，監(jiān)測有效性取決于目標正面朝向與視頻傳感器方向的可視角度[11]。因此，文獻[12]提出了視頻傳感器網(wǎng)絡的全視域覆蓋的概念并給出了全視域覆蓋的判定。全視域覆蓋是指被監(jiān)測的目標，無論朝向任何方向都能被至少一個視頻傳感器有效覆蓋。有效覆蓋是指目標的朝向與目標和視頻傳感器連線矢量的夾角小于給定角度。全視域覆蓋區(qū)域是指區(qū)域中每個點都是全視域覆蓋的?；谌曈蚋采w，文獻[13]提出了視頻柵欄的概念。視頻柵欄是指柵欄上的區(qū)域都是全視域覆蓋的。文獻[13～14]研究了普通定向視頻傳感器的視頻柵欄覆蓋問題。而在一些場景中，傳感器有多個可能的工作方向，同一時刻只能開啟一個方向工作[15]。

本文研究了多工作方向視頻傳感器網(wǎng)絡的視頻柵欄覆蓋問題。假設每個視頻傳感器都有3個可能的工作方向，但同一時刻只能有一個方向在工作。對于給定的區(qū)域，區(qū)域里隨機拋灑了很多這樣的視頻傳感器。研究如何挑選盡可能少的視頻傳感器并同時確定工作方向來構(gòu)成視頻柵欄。

1 問題描述

對于視頻傳感器網(wǎng)絡來說覆蓋時要考慮目標的朝向。

1.1 全視域覆蓋

圖1 全視域覆蓋模型

圖2 點的全視域覆蓋判定

圖3 安全區(qū)域和非安全區(qū)域

圖4 網(wǎng)格單元的全視域覆蓋示例

圖5 最小覆蓋集合示例

最小覆蓋集合定義：如果傳感器工作方向集合di能全視域覆蓋網(wǎng)格單元bi，且di的任何真子集都不能全視域覆蓋網(wǎng)格單元bi，則di就是網(wǎng)格單元bi的一個最小覆蓋集合。圖5中網(wǎng)格單元被10個視頻傳感器覆蓋，畫出傳感器間的非安全區(qū)域可得3個最小覆蓋集合分別為{S1,S2,S3,S4,S5,S6,S8,S10}，{S1,S2,S3,S4,S5,S6,S7,S9,S10}，{S1,S2,S3,S4,S5,S7,S8,S10}。

網(wǎng)格單元的I集合：網(wǎng)格單元bi的I集合就是網(wǎng)格單元bi的所有最小覆蓋集合所組成的集合。

1.2 問題定義

約束條件：

di∈Ii,1≤i≤m

(1)

?So,p∈di，1

若p≠t, 則0≠r

(2)

條件(1)保證所選的最小覆蓋集合為路徑上網(wǎng)格單元的最小覆蓋集合。條件(2)保證同一時刻一個視頻傳感器只能有一個方向在工作。

2 問題分析

本文的難點在于視頻傳感器有3個可能的工作方向，選擇不同的工作方向會形成不同的全視域覆蓋區(qū)域，而文獻[13～14]中為普通定向視頻傳感器，部署后全視域覆蓋的區(qū)域也已確定。因此，本文采用離散的方法將區(qū)域劃分成網(wǎng)格單元，判斷每個網(wǎng)格單元是否可能被全視域覆蓋，如果可能被全視域覆蓋，添加標記并求出所有滿足該網(wǎng)格單元全視域覆蓋的傳感器工作方向的集合，即所有最小覆蓋集合。求解最小覆蓋集合的算法參見文獻[14]，其中的算法是對不規(guī)格區(qū)域求最小覆蓋集合，該算法同樣適用于求解網(wǎng)格單元的最小覆蓋集合。根據(jù)標記情況，如果兩個標記網(wǎng)格單元相鄰，則彼此之間存在一條邊，邊的權(quán)值設置為1，再添加起始點S和結(jié)束點T分別代表區(qū)域的左右邊界。調(diào)用迪杰斯特拉算法，求出最短路徑，判斷該最短路徑是否有沖突，若無沖突則該路徑就是一條視頻柵欄。

圖6 調(diào)用迪杰斯特拉算法求最短路徑

變形后可得挑選問題與最大交集問題是等價的，而最大交集問題在文獻[16]中已被證明是一個NP問題，因此本文的問題也是NP問題。

3 算法設計

挑選問題在上文中已被證明是NP問題，所以設計 “不沖突選擇算法”來近似解決。算法步驟為：

步驟1 輸入最短路徑上網(wǎng)格單元的I集合{I1,I2,…,Im}，初始化參數(shù)MinBarrer=Φ,j=1,MinNum=∞；

步驟2 從{I1,I2,…,Im}中依次取出元素Ij，對取出的集合Ij中的每個最小覆蓋集Sm依次進行判斷，如果|Sm∪MinBarrer|

步驟3 令MinBarrer=Sk∪MinBarrer；

步驟4 輸出MinBarrer集合，該集合即使區(qū)域滿足全視域的視頻柵欄覆蓋的工作方向集合。

4 實驗模擬

實驗設定區(qū)域為10 m×20 m，網(wǎng)格單元大小為1 m×1 m，視頻傳感器的感應半徑為3 m，有效角度為π/3,傳感器的數(shù)量從500個依次增加到3 500個。每次設置傳感器數(shù)量后運行100次，記錄構(gòu)成視頻柵欄的次數(shù)以及每次構(gòu)成視頻柵欄所花費的傳感器的平均數(shù)量。

圖7 傳感器數(shù)量變化對構(gòu)成視頻柵欄概率的影響

由圖7可知，當隨機部署的視頻傳感器數(shù)量很少時不能構(gòu)成視頻柵欄。隨著部署的視頻傳感器數(shù)量的增多，構(gòu)成視頻柵欄的概率增大。圖7中普通視頻傳感器的曲線是文獻[14]的實驗結(jié)果，本文的方法比文獻[14]采用普通視頻傳感器的方法構(gòu)成視頻柵欄的概率更高，尤其是隨機部署的傳感器數(shù)量較少時，優(yōu)勢更明顯。

圖8 傳感器數(shù)量對構(gòu)成視頻柵欄所需傳感器數(shù)量的影響

由圖8可知，當設定的有效角度越小時，形成全視域覆蓋的難度越大，構(gòu)成視頻柵欄所需傳感器數(shù)量也越多。隨著部署視頻傳感器數(shù)量的增加，構(gòu)成視頻柵欄所花費的傳感器數(shù)量也不斷增加。這是因為隨著部署視頻傳感器數(shù)量的增加，單個網(wǎng)格單元滿足全視域覆蓋的視頻傳感器數(shù)量也增加了。

5 結(jié)束語

實驗結(jié)果表明，本文的方法可以應用于多工作方向視頻傳感器網(wǎng)絡，實現(xiàn)選擇盡可能少的視頻傳感器并確定工作方向來構(gòu)成視頻柵欄的目標。本文方法比普通視頻傳感器網(wǎng)絡構(gòu)成視頻柵欄擁有更好的性能，尤其當網(wǎng)絡中隨機部署的視頻傳感器數(shù)量較少時效果更佳。

[1] 魏鵬,路贊贊.無線傳感器網(wǎng)絡分布式多傳感器目標檢測[J].電子科技,2014,27(3):143-146.

[2] Mohamadi H,Salleh S,Ismail A S.A learning automata-based solution to the priority-based target coverage problem in directional sensor networks[J].Wireless Personal Communications,2014,79(3):2323-2338.

[3] Cai Y,Lou W,Li M.Cover set problem in directional sensor networks[J].Future Generation Communication & Networking, 2007(1):274-278.

[4] 宋蘇鳴,張燕,陳源.多蜜源蜂群算法在無線傳感器網(wǎng)絡覆蓋的優(yōu)化[J].電子科技,2013, 26(11):17-21.

[5] Tao D,Ma H,Liu L.Coverage-enhancing algorithm for directional sensor networks[M].Berlin Heidelberg:Springer,2006.

[6] Aghdasi H S,Abbaspour M.Energy efficient area coverage by evolutionary camera node scheduling algorithms in visual sensor networks[J].Soft Computing,2016, 20(3):1191-1202.

[7] Tao D,Wu T Y.A survey on barrier coverage problem in directional sensor networks[J]. Sensors Journal IEEE,2015,15(2):876-885.

[8] Zhang Y,Sun X,Wang B.Efficient algorithm for k-barrier coverage based on integer linear programming[J].China Communications,2016, 13(7):16-23.

[9] Eftekhari E,Mohsen A,Kranakis R,et al. Distributed algorithms for barrier coverage using relocatable sensors[J].Distributed Computing,2016,29(5):361-376.

[10] Wang B.Coverage problems in sensor networks:a survey[J].ACM Computing Surveys,2011,43(4):32-38.

[11] Chang C C,Aghajan H.Collaborative face orientation detection in wireless image sensor networks[C].Macro:Proceedings of ACM SenSys Workshop on Distributed Smart Cameras,2006.

[12] Wang Y,Cao G.On full-view coverage in camera sensor networks[C].Shanghai:IEEE International Conference on Computer Communications,2011.

[13] Wang Y,Cao G.Barrier coverage in camera sensor networks[C].Paris:ACM International Symposium on Mobile Ad Hoc Networking and Computing,2011.

[14] Ma H,Yang M,Li D,et al.Minimum camera barrier coverage in wireless camera sensor networks[C].Xi’an:IEEE International Conference on Computer Communications,2012.

[15] Cai Y,Lou W,Li M,et al.Energy efficient target-oriented scheduling in directional sensor networks[J].IEEE Transactions on Computers,2009,58(9):1259-1274.

[16] Clifford R,Popa A.Maximum subset intersection[J].Information Processing Letters,2011,111 (7):323-325.