| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks
July 2004 (vol. 3 no. 3)
pp. 258-271
In the paper, we devise and evaluate a fully decentralized, light-weight, dynamic clustering algorithm for target tracking. Instead of assuming the same role for all the sensors, we envision a hierarchical sensor network that is composed of 1) a static backbone of sparsely placed high-capability sensors which will assume the role of a cluster head (CH) upon triggered by certain signal events and 2) moderately to densely populated low-end sensors whose function is to provide sensor information to CHs upon request. A cluster is formed and a CH becomes active, when the acoustic signal strength detected by the CH exceeds a predetermined threshold. The active CH then broadcasts an information solicitation packet, asking sensors in its vicinity to join the cluster and provide their sensing information. We address and devise solution approaches (with the use of Voronoi diagram) to realize dynamic clustering: (I1) how CHs cooperate with one another to ensure that only one CH (preferably the CH that is closest to the target) is active with high probability, (I2) when the active CH solicits for sensor information, instead of having all the sensors in its vicinity reply, only a sufficient number of sensors respond with nonredundant, essential information to determine the target location, and (I3) both the packets that sensors send to their CHs and packets that CHs report to subscribers do not incur significant collision. Through both probabilistic analysis and ns-2 simulation, we show with the use of Voronoi diagram, the CH that is usually closest to the target is (implicitly) selected as the leader and that the proposed dynamic clustering algorithm effectively eliminates contention among sensors and renders more accurate estimates of target locations as a result of better quality data collected and less collision incurred.
[1] 258 F. Aurenhammer, Voronoi Diagrams-A Survey of a Fundamental Geometric Data Structure ACM Computing Surveys, vol. 23, pp. 345-405, 1991.[2] S. Bandyopadhyay and E.J. Coyle, An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks Proc. IEEE INFOCOM 2003, Apr. 2003.[3] D.P. Bertsekas, Nonlinear Programming, second ed. Belmont, Mass.: Athena Scientific, 1999.[4] R. Brooks, C. Griffn, and D.S. Friedlander, Self-Organized Distributed Sensor Network Entity Tracking Int'l J. High Performance Computer Applications, special issue on sensor networks, vol. 16, no. 3, Fall 2002.[5] W.-P. Chen, C.-J. Hou, and L. Sha, Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks Proc. IEEE Int'l Conf. Network Protocols, Nov. 2003.[6] M. Chu, H. Haussecker, and F. Zhao, Scalable Information-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks Int'l J. High Performance Computing Applications, vol. 16, no. 3, Fall 2002.[7] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-Efficient Communication Protocols for Wireless Microsensor Networks Proc. Hawaiian Int'l Conf. Systems Science, Jan. 2000.[8] C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Proc. Sixth Ann. IEEE/ACM Int'l Conf. Mobile Computing and Networking, Aug. 2000.[9] P. Krishna, N.H. Vaidya, M. Chatterjee, and D.K. Pradhan, A Cluster-Based Approach for Routing in Dynamic Networks ACM SIGCOMM Computer Comm. Rev., Apr. 1997.[10] C.R. Lin and M. Gerla, “Adaptive Clustering in Mobile Wireless Networks,” IEEE J. Selected Areas in Communications, vol. 16, pp. 1,265–1,275, 1997.[11] J. Liu, J. Liu, J. Reich, P. Cheung, and F. Zhao, Distributed Group Management for Track Initiation and Maintenance in Target Localization Applications Proc. Second Workshop Information Processing in Sensor Networks, Apr. 2003.[12] Computer Science and Telecommunication Board, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Research Council, Washington, D.C., 2001.[13] M.R. Pearlman and Z.J. Haas, Determining the Optimal Configuration for the Zone Routing Protocol IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1395-1414, Aug. 1999.[14] X. Sheng and Y.-H. Hu, Energy Based Acoustic Source Localization Proc. Second Workshop Information Processing in Sensor Networks, Apr. 2003.[15] Q. Wang, W.-P. Chen, R. Zheng, K. Lee, and L. Sha, Acoustic Target Tracking Using Wireless Sensor Devices Proc. Second Workshop Information Processing in Sensor Networks, Apr. 2003.[16] H. Yang and B. Sikdar, A Protocol for Tracking Mobile Targets using Sensor Networks Proc. IEEE Workshop Sensor Network Protocols and Applications, (in conjunction with IEEE ICC), May 2003.[17] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, A Two-Tier Data Dissemination Model for Large-Scale Wireless Sensor Networks Proc. ACM Int'l Conf. Mobile Computing and Networking, Sept. 2002.[18] W. Zhang and G. Cao, DCTC: Dynamic Convoy Tree-Based Collaboration for Target Tracking in Sensor Networks IEEE Trans. Wireless Comm., to appear.[19] F. Zhao, J. Shin, and J. Reich, Information-Driven Dynamic Sensor Collaboration for Tracking Applications IEEE Signal Processing Magazine, Mar. 2002.[20] Crossbow Technology, Inc.,http://www.xbow.com/support/support_pdf_files mts-mda_series_user_manual_revb.pdf , 2004.[21] Infrarad Sensor,http://www.interq.or.jp/japan/se-inouee_pyro.htm , 2004.[22] KEYENCE America,http://www.keyence.com/products sensors.html , 2004.[23] UCB, LBNL VINT Network Simulator http://www-mash.cs. berkeley.eduns/, 2004.[24] UCLA SensorSim: A Simulation Framework for Sensor Networks http://nesl.ee.ucla.edu/projectssensorsim /, 2004.
Index Terms:
Dynamic clustering, tracking, localization, sensor networks.
Citation:
Wei-Peng Chen, Jennifer C. Hou, Lui Sha, "Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks," IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 258-271, July 2004, doi:10.1109/TMC.2004.22
