Sensor deployment and target localization in distributed sensor networks

ABSTRACT

The effectiveness of cluster-based distributed sensor networks depends to a large extent on the coverage provided by the sensor deployment. We propose a virtual force algorithm (VFA) as a sensor deployment strategy to enhance the coverage after an initial random placement of sensors. For a given number of sensors, the VFA algorithm attempts to maximize the sensor field coverage. A judicious combination of attractive and repulsive forces is used to determine the new sensor locations that improve the coverage. Once the effective sensor positions are identified, a one-time movement with energy consideration incorporated is carried out, that is, the sensors are redeployed, to these positions. We also propose a novel probabilistic target localization algorithm that is executed by the cluster head. The localization results are used by the cluster head to query only a few sensors (out of those that report the presence of a target) for more detailed information. Simulation results are presented to demonstrate the effectiveness of the proposed approach.

REFERENCES

• 1: Bhardwaj, M. and Chandrakasan, A. P. 2002. Bounding the lifetime of sensor networks via optimal role assignments. In Proceedings of IEEE INFOCOM, 1587--1596.
• 2: Richard R. Brooks , S. S. Iyengar, Multi-sensor fusion: fundamentals and applications with software, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 3: Adaptive Beacon Placement, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.489, April 16-19, 2001
• 4: Coding Theory Framework for Target Location in Distributed Sensor Networks, Proceedings of the International Conference on Information Technology: Coding and Computing, p.130, April 02-04, 2001
• 5: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 6: Dhillon, S. S., Chakrabarty, K., and Iyengar, S. S. 2002. Sensor placement algorithms for grid coverage. In Proceedings of the International Conference on Information Fusion, 1581--1587.
• 7: Elfes, A. 1990. Occupancy grids: A stochastic spatial representation for active robot perception. In Proceedings of the 6th Conference on Uncertainty in AI, 60--70.
• 8: Heidemann, J. and Bulusu, N. 2001. Using geospatial information in sensor networks. In Proceedings of CSTB Workshop on Intersection of Geospatial Information and Information Technology.
• 9: Howard, A., Matarić, M. J., and Sukhatme, G. S. 2002. Mobile sensor network deployment using potential field: A distributed scalable solution to the area coverage problem. In Distributed Autonomous Robotic Systems 5: Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems (DARS02), 299--308.
• 10: Sundararaja S. Iyengar , L. Prasad , H. Min, Advances in Distributed Sensor Integration; Application and Theory, Prentice Hall PTR, Upper Saddle River, NJ, 1995
• 11: Kasetkasem, T. and Varshney, P. K. 2001. Communication structure planning for multisensor detection systems. In IEE Proceedings of Radar, Sonar and Navigation. Vol. 148, 2--8.
• 12: Marco Locatelli , Ulrich Raber, Packing equal circles in a square: a deterministic global optimization approach, Discrete Applied Mathematics, v.122 n.1-3, p.139-166, 15 October 2002 [doi>10.1016/S0166-218X(01)00359-6]
• 13: Meguerdichian, S., Slijepcevic, S., Karayan, V., and Potkonjak, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of IEEE INFOCOM. Vol. 3, 1380--1387.
• 14: Musman, S. A., Lehner, P. E., and Elsaesser, C. 1997. Sensor planning for elusive targets. J. Computer & Mathematical Modeling 25, 103--115.
• 15: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 16: Penny, D. E. 1998. The automatic management of multi-sensor systems. In Proceedings of the International Conference on Information Fusion.
• 17: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 18: Qi, H., Iyengar, S. S., and Chakrabarty, K. 2001. Multi-resolution data integration using mobile agents in distributed sensor networks. IEEE Trans. System, Man and Cybernetics 31, 383--391.
• 19: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 20: Pramod K. Varshney, Distributed Detection and Data Fusion, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 21: Zou, Y. and Chakrabarty, K. 2003. Sensor deployment and target localization based on virtual forces. In Proceedings of IEEE INFOCOM.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.4 Distributed Systems
          Subjects: Distributed applications
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Management, Performance

Keywords:
Cluster-based sensor networks, cluster head, sensor field coverage, sensor placement, virtual force