Voronoi-Based Coverage Optimization for Directional Sensor Networks

Jing LI, Ruchuan WANG, Haiping HUANG, Lijuan SUN

.

DOI: 10.4236/wsn.2009.15050                

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.

Keywords

Directional Sensor Networks, Coverage, Deployment, Voronoi Diagram

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	D. Tao, H. Ma, “Coverage-enhancing algorithm for directional sensor networks,” Stojmenovic I, Cao JN, eds. Proceedings of the 2nd International Conference on Mobile Ad-Hoc and Sensor Networks, pp. 256?267, 2006.
[14]	J. Ai and A. A. Abouzeid, “Coverage by directional sensors in randomly deployed wireless sensor networks,” Journal of Combinatorial Optimization, Vol. 11, No. 1, pp. 21–41, February 2006.
[15]	Y. Cai, W. Lou, and M. Li, “Cover set problem in directional sensor networks,” Proceedings of the Future Generation Communication and Networking (FGCN 2007), Vol. 01, pp. 274–278, 2007.
[16]	J. Wen, L. Fang, J. Jiang, and W. Dou, “Coverage optimizing and node scheduling in directional wireless sensor networks,” Wireless Communications, Networking and Mobile Computing, WiCOM’08, 4th International Conference on, pp. 1–4, October 2008.
[17]	S. Megerian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Worst- and best-case coverage in sensor networks,” IEEE Transactions on Mobile Computing, Vol. 4, No. 1, pp. 84–92, February 2005.
[18]	J. Adriaens, S. Megerian, and M. Potkonjak, “Optimal worst-case coverage of directional field-of-view sensor networks,” Sensor and Ad Hoc Communications and Networks, SECON’06, 3rd Annual IEEE Communications Society on, Vol. 1, pp. 336–345, September 2006.
[19]	F. Aurenhammer, “Voronoi diagrams-A survey of a fundamental geometric data structure,” ACM Computing Surveys, Vol. 23, No. 3, pp. 345–405, September 1991.