尤炳棋，徐向華，王 然

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

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

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

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

1 問(wèn)題描述

對(duì)于視頻傳感器網(wǎng)絡(luò)來(lái)說(shuō)覆蓋時(shí)要考慮目標(biāo)的朝向。

1.1 全視域覆蓋

圖1 全視域覆蓋模型

圖2 點(diǎn)的全視域覆蓋判定

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

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

圖5 最小覆蓋集合示例

最小覆蓋集合定義：如果傳感器工作方向集合di能全視域覆蓋網(wǎng)格單元bi，且di的任何真子集都不能全視域覆蓋網(wǎng)格單元bi，則di就是網(wǎng)格單元bi的一個(gè)最小覆蓋集合。圖5中網(wǎng)格單元被10個(gè)視頻傳感器覆蓋，畫出傳感器間的非安全區(qū)域可得3個(gè)最小覆蓋集合分別為{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 問(wèn)題定義

約束條件：

di∈Ii,1≤i≤m

(1)

?So,p∈di，1

若p≠t, 則0≠r

(2)

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

2 問(wèn)題分析

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

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

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

3 算法設(shè)計(jì)

挑選問(wèn)題在上文中已被證明是NP問(wèn)題，所以設(shè)計(jì) “不沖突選擇算法”來(lái)近似解決。算法步驟為：

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

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

步驟3 令MinBarrer=Sk∪MinBarrer；

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

4 實(shí)驗(yàn)?zāi)M

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

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

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

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

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

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

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

[1] 魏鵬,路贊贊.無(wú)線傳感器網(wǎng)絡(luò)分布式多傳感器目標(biāo)檢測(cè)[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ú)線傳感器網(wǎng)絡(luò)覆蓋的優(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.