Voronoi-Based Coverage Optimization for Directional Sensor Networks
- 1
- 2
- 3
- 4
Abstract
Sensing coverage is a fundamental problem in sensors networks. Different from traditional isotropic sensors with sensing disk, directional sensors may have a limited angle of sensing range due to special applications. In this paper, we study the coverage problem in directional sensor networks (DSNs) with the rotatable orientation for each sensor. We propose the optimal coverage in directional sensor networks (OCDSN) problem to cover maximal area while activating as few sensors as possible. Then we prove the OCDSN to be NP-complete and propose the Voronoi-based centralized approximation (VCA) algorithm and the Voronoi-based distributed approximation (VDA) algorithm of the solution to the OCDSN problem. Finally, extensive simulation is executed to demonstrate the performance of the proposed algorithms.
- I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” ACM Trans. on Multimedia Computing, Communications and Applications, Vol. 40, No. 8, pp. 102–114, August 2002.
- R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An analysis of a large scale habitat monitoring application,” ACM Conference on Embedded Networked Sensor Systems (SenSys), pp. 214–226, 2004.
- M. Li and Y. Liu, “Underground structure monitoring with wireless sensor networks,” Information Processing in Sensor Networks, IPSN, 6th International Symposium on, pp. 69–78, April, 2007.
- M. Rahimi, R. Baer, O. I. Iroezi, J. C. Garcia, J. Warrior, D. Estrin, and M. Srivastava, “Cyclops: In situ image sensing and interpretation in wireless sensor networks,” SenSys, pp. 192–204, 2005.
- W. Feng, E. Kaiser, W. C. Feng, and M. L. Baillif, “Panoptes: Scalable low-power video sensor networking technologies,” ACM Transactions on Multimedia Computing, Communications and Applications, Vol. 1, No. 2, pp. 151–167, May 2005.
- J. Djugash, S. Singh, G. Kantor, and W. Zhang, “Rangeonly slam for robots operating cooperatively with sensor networks,” Robotics and Automation, ICRA, Proceedings 2006 IEEE International Conference on, pp. 2078–2084, May 2006.
- M. Marengoni, B. A. Draper, A. Hanson, and R. A. Sitaraman, “A System to Place Observers on a Polyhedral Terrain in Polynomial Time,” Image and Vision Computing, Vol. 18, pp. 773–80, December 1996.
- A. Ghosh, “Estimating coverage holes and enhancing coverage in mixed sensor networks,” Local Computer Networks, 29th Annual IEEE International Conference on, pp. 68–76, November 2004.
- S. S. Dhillon, K. Chakrabarty, and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections,” Information Fusion, Proceedings of the Fifth International Conference on, Vol. 2, pp. 1581–1587, July 2002.
- S. S. Dhillon and K. Chakrabarty, “Sensor placement for effective coverage and surveillance in distributed sensor networks,” in Proceedings of IEEE WCNC, pp. 1609– 1614, March 2003.
- H. Ma and Y. Liu, “On coverage problems of directional sensor networks,” in International Conference on Mobile Ad-hoc and Sensor Networks (MSN), Vol. 3794, pp. 721–731, 2005.
- D. Tao, H. Ma, and L. Liu, “A virtual potential field based coverage-enhancing algorithm for directional sensor networks,” Journal of Software, Vol. 18, No. 5, pp. 1152?1163, May 2007.