Group Target Tracking in WSN Based on Convex Hulls Merging

Quanlong LI, Zhijia ZHAO, Xiaofei XU, Tingting ZHOU
DOI: 10.4236/wsn.2009.15053                

Abstract

When a mass of individual targets move closely, it is unpractical or unnecessary to localize and track every specific target in wireless sensor networks (WSN). However, they can be tracked as a whole by view of group target. In order to decrease the amount of energy spent on active sensing and communications, a flexible boundary detecting model for group target tracking in WSN is proposed, in which, the number of sensors involved in target tracking is adjustable. Unlike traditional one or multiple individual targets, the group target usually occupies a large area. To obtain global estimated position of group target, a divide-merge algorithm using convex hull is designed. In this algorithm, group target’s boundary is divided into several small pieces, and each one is enclosed by a convex hull which is constructed by a cluster of boundary sensors. Then, the information of these small convex hulls is sent back to a sink. Finally, big convex hull merged from these small ones is considered as the group target’s contour. According to our metric of precision evaluation, the simulation experiments confirm the efficiency and accuracy of this algorithm.

Keywords

Sensor Networks, Target Tracking, Group Target, Convex Hull

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Chen, J. C. Hou, and L. Sha, “Dynamic clustering for acoustic target tracking in wireless sensor networks,” IEEE Transactions on Mobile Computing, Vol. 3, No. 3, pp. 258–271, 2004.
[2]	W. Zhang and G. Cao. “DCTC: Dynamic convoy tree-based collaboration for target tracking in sensor networks,” IEEE Transactions on Wireless Communications, Vol. 3, No. 5, pp. 1689–1701, 2004.
[3]	J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a moving object with a binary sensor network,” ACM Sensys’03, Los Angeles, California, USA, pp. 150–161, 2003.
[4]	J. Singh, U. Madhow, R. Kumar, S. Suri, and R. Cagley, “Tracking multiple targets using binary proximity sensors,” In Proceedings of the 6th International Conference on Information Processing In Sensor Networks, April 2007.
[5]	N. Shrivastava, R. Mudumbai, U. Madhow, and S. Suri. “Target tracking with binary proximity sensors: Fundamental limits, minimal descirptions, and algorithms,” In Proceedings of ACM SenSys, 2006.
[6]	X. Zhu, R. Sarkar, J. Gao, and J. S. B. Mitchell, “Light-weight contour tracking in wireless sensor networks,” In Proceedings of IEEE INFOCOM, pp. 1849– 1857, 2008.
[7]	K. P. Shih, S. S. Wang, P. H. Yang, and C. C. Chang, “CollECT: Collaborative event detection and tracking in wireless heterogeneous sensor networks,” In Proceedings of the 11th IEEE Symposium on Computers and Communications (ISCC’06).
[8]	X. Ji, H. Zha, John J. Metzner, and G. Kesidis, “Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks,” IEEE International Conference on Communications, Paris, FRANCE, June 20–24, 2004.
[9]	D. Cao, B. Jin, and J. Cao, “On group target tracking with binary sensor networks,” In Proceedings of the 5th IEEE International Conference on Mobile Ad Hoc and Sensor System (MASS), pp. 334–339, 2008.
[10]	O’ Rourke and Joseph, “Computational geometry in C,” China Machine Press, 2005.
[11]	T. H. Cormen, C. E. Leiseron, and R. L. Rivest. “Introduction to algorithms,” The MIT Press, pp. 947–956, 2002.
[12]	R. C. T. Lee, S. S. Tseng, and R. C. Chang, “Introduction to the design and analysis of algorithms,” Addison- Wesley, Chapter 12.6, 2002.