||The k-Barrier Coverage Mechanism in Wireless Visual Sensor Networks
||Department of Computer Science and Information Engineering
Visual Sensor Networks
Wireless Sensor Networks
||近年來，k-邊界覆蓋(k-Barrier Coverage)問題在無線感測網路中受到廣泛討論。不同於以往的研究，本論文考慮無線視覺感測網路(Wireless Visual Sensor Networks，WVSN)應用在k-Barrier Coverage的議題，其中每個Camera Sensor具有攝影與無線通訊的能力，因此可對監控區域進行更嚴密的影像監控。由於每個Camera Sensor的感測範圍近似一扇形，使得傳統解決k-Barrier Coverage問題的方法將不再適用。我們考量Camera Sensor的感測範圍並提出一k-Barrier Coverage演算法，利用盡可能少的Camera Sensor數量組成組數盡可能多且彼此不相交的防衛曲線，並且滿足k-Barrier Coverage的限制。實驗模擬顯示，我們所提出的k-邊界覆蓋演算法具有較好的覆蓋效率。
||Wireless Visual Sensor Networks (WVSNs) consists of a set of camera sensor nodes each of which equips with a camera and is capable of communicating with the other camera sensors within a specific distance range. As an extension of wireless sensor networks (WSNs), the WVSNs can provide richer information such as image and picture during executing targets monitoring and tracking tasks. Since the sensing area of each camera sensor is fan-shaped, existing barrier-coverage algorithms developed for WSNs cannot be applied to the WVSNs. This paper is considering to address the k-barrier coverage problems in WVSNs and to propose a barrier-coverage approach aiming at finding a maximal number of distinct defense curves with each of which consists of as few camera sensors as possible but still guarantees k-barrier coverage. Compared with the related work, experimental study reveals that the proposed k-barrier coverage mechanism constructs more defense curves than the k-barrier coverage and the number of camera sensors participating in each defense curve is smaller.
||Table of Contents
List of Figures IV
List of Table VI
1. Introduction 1
2. Network Environment and Problem Statement 5
3. The Proposed k-Barrier Coverage Construction Algorithm (k-BCC) 9
3.1 Initialization Phase 10
3.2 Barrier Construction (BC) phase 12
3.2.1 Basic Approach(BA) 13
3.2.2 Backtracking Approach (BTA) 22
3.2.3 Branch Approach (BRA) 24
4. Simulation 27
4.1 Simulation Model 27
4.2 Simulation Results 28
5. Conclusion 35
Appendix A. Conference Version 37
List of Figures
Figure 1: The difference between WSN and WVSN in the same deployment 2
Figure 2: The examples to illustrate the valid and invalid crossing paths. 4
Figure 3: Disjoint property between and 6
Figure 4: Different constructions of DB-3 6
Figure 5: Grid-based network 9
Figure 6: Fully covered grids of sa and sb 9
Figure 7: Weighted grid matrix (WGM) 11
Figure 8: The jobs of DMcurrent 11
Figure 9: Priority Table 12
Figure 10: q-Beneficial Grid 12
Figure 11: An failure example by applying the BA 21
Figure 12: An example by applying the proposed BTA 21
Figure 13: An example of the proposed BRA 23
Figure 14: System model 28
Figure 15: The average numbers of constructed by applying BA, BTA, BRA and MDP. 29
Figure 16: The average numbers of constructed by applying BA, BTA, BRA and MDP 30
Figure 17: The average control overhead of constructing by applying BA, BTA, BRA and MDP 31
Figure 18: The probability of constructing a by applying BA, BTA, BRA and MDP 32
Figure 19: The comparison of BA, BTA, BRA and their combinations in terms of the different order for constructing 33
List of Table
Table 1. Simulation Parameters 27
|| Ai Chen, Santosh Kumar, Member, IEEE, and Ten H. Lai, “Local Barrier Coverage in Wireless Sensor Networks, ”IEEE TMC, April 2010.
 C.-F. Huang and Y.-C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” ACM WSNA, 2003, pp. 115-121.
 H. Ma and Y. Liu, “Some Problems of Directional Sensor Networks, ”International Journal of Sensor Networks, vol. 2, no. 1/2, pp. 44–52, Aug. 2007.
 Li Zhang, Jian Tang, and Weiyi Zhang, “Strong Barrier Coverage with Directional Sensors,” The 28th IEEE conference on Global telecommunications, p.1816-1821, Nov. 30- Dec. 04, 2009, Honolulu, Hawaii, USA
 S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” ACM MobiCom, 2005.
 K. P. Shih, C. M. Chou, I H. Liu, and C. C. Li, “On Barrier Coverage in Wireless Camera Sensor Networks,” IEEE AINA, 2010.
 A. Schrijver. ”Combinatorial Optimization : Polyhedra and efficiency,” Springer, ISBN 978-3-540-44389-6, 2003.