×

Optimal movement of mobile sensors for barrier coverage of a planar region. (English) Zbl 1192.68816

Summary: Intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. They can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. We consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. We discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.

MSC:

68W05 Nonnumerical algorithms
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, N.; Kanhere, S. S.; Jha, S., The holes problem in wireless sensor networks: A survey, ACM SIGMOBILE Mobile Computing and Communications Review, 9, 2, 4-18 (2005)
[2] P. Balister, B. Bollobas, A. Sarkar, S. Kumar, Reliable density estimates for coverage and connectivity in thin strips of finite length, in: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, 2007, pp. 75-86; P. Balister, B. Bollobas, A. Sarkar, S. Kumar, Reliable density estimates for coverage and connectivity in thin strips of finite length, in: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, 2007, pp. 75-86
[3] A. Chen, S. Kumar, T.H. Lai, Designing localized algorithms for barrier coverage, in: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, 2007, pp. 63-74; A. Chen, S. Kumar, T.H. Lai, Designing localized algorithms for barrier coverage, in: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, 2007, pp. 63-74
[4] Cole, R., Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), 34, 1, 200-208 (1987) · Zbl 1378.68037
[5] Heo, N.; Varshney, P. K., A distributed self spreading algorithm for mobile wireless sensor networks, Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE, 3 (2003)
[6] Heo, N.; Varshney, P. K., Energy-efficient deployment of intelligent mobile sensor networks, Systems, Man and Cybernetics, Part A, IEEE Transactions on, 35, 1, 78-92 (2005)
[7] Hopcroft, J. E.; Karp, R. M., An \(n^{2.5}\) algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 2, 4, 225-231 (1973) · Zbl 0266.05114
[8] S.S. Hu, ‘Virtual Fence’ along border to be delayed, Washington Post, Thursday, February 28, 2008; S.S. Hu, ‘Virtual Fence’ along border to be delayed, Washington Post, Thursday, February 28, 2008
[9] Jung, B.; Sukhatme, G. S., Tracking targets using multiple robots: The effect of environment occlusion, Autonomous Robots, 13, 3, 191-205 (2002) · Zbl 1030.68714
[10] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97 (1955) · Zbl 0143.41905
[11] Kumar, S.; Lai, T. H.; Arora, A., Barrier coverage with wireless sensors, Wireless Networks, 13, 6, 817-834 (2007)
[12] J. Liu, P. Cheung, F. Zhao, L. Guibas, A dual-space approach to tracking and sensor management in wireless sensor networks, in: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, 2002, pp. 131-139; J. Liu, P. Cheung, F. Zhao, L. Guibas, A dual-space approach to tracking and sensor management in wireless sensor networks, in: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, 2002, pp. 131-139
[13] Megiddo, N., Applying parallel computation algorithms in the design of serial algorithms, Journal of the ACM (JACM), 30, 4, 852-865 (1983) · Zbl 0627.68034
[14] O’Rourke, J., Art Gallery Theorems and Algorithms (1987), Oxford University Press, Inc.: Oxford University Press, Inc. New York, NY, USA · Zbl 0653.52001
[15] Schrijver, A., Disjoint circuits of prescribed homotopies in a graph on a compact surface, Journal of Combinatorial Theory Series B, 51, 1, 127-159 (1991) · Zbl 0723.05050
[16] Se, S.; Lowe, D.; Little, J., Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks, The International Journal of Robotics Research, 21, 8, 735 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.