Minimum Incremental k-Coverage in Ad-Hoc Sensor Network

Abstract:

The deployment is one of the stage while creating a wireless sensor network. A deployment may not reach some requirements for sustained and reliable operations, even though some redundant sensors are deployed. Improving the deployment by adding some sensors is an efficient way, which is treated as the incremental deployment problem. A problem named Minimum Incremental k-Coverage in a two-dimensional continuous space is formulated. Some definitions and theorems of coverage and adding target positions are derived. A heuristic approach to this problem is proposed and its performance is evaluated through extensive simulation-based experiments.

• Periodical: Advanced Materials Research (Volumes 271-273)
• Pages: 377-382
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.271-273.377
• Online since: July 2011
• Authors: Shen Wei, Wen Zhe Ni
• Keywords: k-Coverage, Minimum Incremental, Sensor Network

References

[1] A. Howard, M.J. Mataric, and G.S. Sukhatme. An incremental self-deployment algorithm for mobile sensor networks. Autonomous Robots, Special Issue on Intelligent Embedded Systems, 9 (2002).

DOI: 10.1109/irds.2002.1041702

[2] Guiling Wang, Student Member, Guohong Cao, and Thomas F. La Porta. Movement-assisted sensor deployment. In Proceedings of INFOCOM, pages 2469–2479, 3 (2004).

DOI: 10.1109/infcom.2004.1354668

[3] Yi Zou and Krishnendu Chakrabarty. Sensor deployment and target localization based on virtual forces. In Proceedings of INFOCOM, (2003).

DOI: 10.1109/infcom.2003.1208965

[4] Guiling Wang, Guohong Cao, Tom La Porta, and Wensheng Zhang. Sensor relocation in mobile sensor networks. In Proc. of IEEE INFOCOM, pages 2302–2312, (2005).

DOI: 10.1109/infcom.2005.1498517

[5] H. Gupta, S. R. Das, and Q. Gu. Connected sensor cover: selforganization of sensor networks for efficient query execution. In Proc. of the ACM MobiHoc, pages 189–200, (2003).

DOI: 10.1145/778415.778438

[6] Z. Zhou, S. Das, and H. Gupta. Connected k-coverage problem in sensor networks. In Proc. of Int. Conf. on Computer Communications and Networks, pages 373–378, (2004).

[7] M. Hefeeda. Randomized k-coverage algorithms for dense sensor networks. In Proc. of INFOCOM Minisymp., pages 2376–2380, (2007).

[8] S. Yang, F. Dai, M. Cardei, J. Wu, and F. Patterson. On connected multiple point coverage in wireless sensor networks. Int. J. of Wireless Info. Networks, 13(4): 289–301, (2006).

DOI: 10.1007/s10776-006-0036-z

[9] A. Savvides, C. Han, and M. Strivastava. Dynamic finegrained localization in ad-hoc networks of sensors. In Proc. of ACM MOBICOM, pages 166–179, (2001).

[10] J. C. Culberson and R. A. Reckhow. Covering polygons is hard. In Foundations of Computer Science, 1988., 29th Annual Symposium on, pages 601–611, 10 (1988).

DOI: 10.1109/sfcs.1988.21976

[11] D. Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE Transactions on Computers, 31(6), 6 (1982).

[12] Alok Aggarwal1, Leonidas J. Guibas, James Saxe, and Peter W. Shor. A linear-time algorithm for computing the voronoi diagram of a convex polygon. Discrete and Computational Geometry, 4(1), 12 (1989).

DOI: 10.1007/bf02187749