Analytic evaluation of target detection in heterogeneous wireless sensor networks

ABSTRACT

In this article, we address the problem of target detection in Wireless Sensor Networks (WSNs). We formulate the target detection problem as a line-set intersection problem and use integral geometry to analytically characterize the probability of target detection for both stochastic and deterministic deployments. Compared to previous work, we analyze WSNs where sensors have heterogeneous sensing capabilities. For the stochastic case, we evaluate the probability that the target is detected by at least k sensors and compute the free path until the target is first detected. For the deterministic case, we show an analogy between the target detection problem and the problem of minimizing the average symbol error probability in 2D digital modulation schemes. Motivated by this analogy, we propose a heuristic sensor placement algorithm, called DATE, that makes use of well-known signal constellations for determining good WSN constellations. We also propose a heuristic called CDATE for connected WSN constellations, that yields high target detection probability.

REFERENCES

• 1: Javed Aslam , Zack Butler , Florin Constantin , Valentino Crespi , George Cybenko , Daniela Rus, Tracking a moving object with a binary sensor network, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958509]
• 2: Sergio Benedetto , Ezio Biglieri, Principles of Digital Transmission: With Wireless Applications, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: Boutros, J., Viterbo, E., Rastello, C., and Belfiore, J. 1996. Good lattice constellations for both Rayleigh fading and Gaussian channels. IEEE Trans. Information Theory 42, 2, 502--518.
• 4: Cao, Q., Yan, T., Stankovic, J., and Abdelzaher, T. 2005. Analysis of target detection performance for wireless sensor networks. DCOSS05. http//www.cs.virginia.edu/~stankovic/psfiles/qingcao1568953971.pdf.
• 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: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for target detection, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570745]
• 7: Thomas Clouqueur , Kewal K. Saluja , Parameswaran Ramanathan, Fault Tolerance in Collaborative Sensor Networks for Target Detection, IEEE Transactions on Computers, v.53 n.3, p.320-333, March 2004 [doi>10.1109/TC.2004.1261838]
• 8: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 9: Olivier Dousse , Christina Tavoularis , Patrick Thiran, Delay of intrusion detection in wireless sensor networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132923]
• 10: Feller, W. 1971. An introduction to probability theory and its applications. Wiley Series in Probability and Mathematical Statistics 3rd ed. Wiley, New York.
• 11: Flanders, H. 1989. Differential Forms With Applications to the Physical Sciences. Dover.
• 12: Chao Gui , Prasant Mohapatra, Power conservation and quality of surveillance in target tracking sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023734]
• 13: Itô, K. 1984. Introduction to Probability Theory. Cambridge University Press.
• 14: Koushanfar, F., Slijepcevic, S., Potkonjak, M., and Sangiovanni-Vincentelli, A. 2002. Error-Tolerant multimodal sensor fusion. In IEEE CAS Workshop on Wireless Communication and Networking.
• 15: Santosh Kumar , Ten H. Lai , Anish Arora, Barrier coverage with wireless sensors, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080859]
• 16: Loukas Lazos , Radha Poovendran, Stochastic coverage in heterogeneous sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.3, p.325-358, August 2006 [doi>10.1145/1167935.1167937]
• 17: Lazos, L., Poovendran, R., and Ritcey, J. 2007a. On the deployment of heterogeneous sensor networks for detection of mobile targets. In Proceedings of the 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'07).
• 18: Loukas Lazos , Radha Poovendran , James A. Ritcey, Probabilistic detection of mobile targets in heterogeneous sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236426]
• 19: Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 01) 3.
• 20: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 21: Reuleaux, F. 1963. The Kinematics of Machinery. Dover, New York.
• 22: Santaló, L. 2004. Integral Geometry and Geometric Probability. Cambridge University Press.
• 23: Solomon, H. 1978. Geometric Probability. Society for Industrial and Applied Mathematics Philadelphia, PA.
• 24: Sylvester, J. 1890. On a funicular solution of Buffon's “problem of the needle” in its most general form. Acta Mathematica 14, 1, 185--205.
• 25: Yang, H. and Sikdar, B. 2003. A protocol for tracking mobile targets using sensor networks. In Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications, 71--81.

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: Network topology

General Terms:
Algorithms, Design, Performance

Keywords:
Target detection, heterogeneous, wireless sensor networks