Statistical location detection with sensor networks

ABSTRACT

The paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. To detect the location of a mobile sensor, the system relies on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). Location detection is posed as a hypothesis testing problem over a discretized space. Large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (Chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. The placement problem is shown to be NP-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. The resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. Numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment.

REFERENCES

• 1: [1] E. Biagioni and K. Bridges, "The application of remote sensor technology to assist the recovery of rare and endangered species," Int. J. High Perform. Comput. Appl., Special Issue on Distributed Sensor Networks , no. 3, Aug. 2002.
• 2: Mani Srivastava , Richard Muntz , Miodrag Potkonjak, Smart kindergarten: sensor-based wireless networks for smart developmental problem-solving enviroments, Proceedings of the 7th annual international conference on Mobile computing and networking, p.132-138, July 2001, Rome, Italy [doi>10.1145/381677.381690]
• 3: [3] S. Bandyopadhyay and E. Coyle, "An energy efficient hierarchical clustering algorithm for wireless sensor networks," in Proc. IEEE INFOCOM, San Francisco, CA, 2003.
• 4: [4] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, Global Positioning System: Theory and Practice, 4th ed. New York: Springer-Verlag, 1997.
• 5: Todd D. Hodes , Randy H. Katz , Edouard Servan-Schreiber , Lawrence Rowe, Composable ad-hoc mobile services for universal interaction, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.1-12, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262121]
• 6: 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]
• 7: [7] A. Meissner, T. Luckenbach, T. Risse, T. Kirste, and H. Kirchner, "Design challenges for an integrated disaster management communication and information system," in Proc. 1st IEEE Workshop Disaster Recovery Netw., New York, 2002.
• 8: [8] P. Bahl and V. Padmanabhan, "RADAR: An in-building RF-based user location and tracking system," in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000.
• 9: [9] J. Hightower, R. Want, and G. Borriello, "SpotON: An Indoor 3d Location Sensing Technology based on RF Signal Strength," University of Washington, Department of Computer Science and Engineering, Seattle, WA, UW CSE 00-02-02, 2000.
• 10: Paul Castro , Patrick Chiu , Ted Kremenek , Richard R. Muntz, A Probabilistic Room Location Service for Wireless Networked Environments, Proceedings of the 3rd international conference on Ubiquitous Computing, p.18-34, September 30-October 02, 2001, Atlanta, Georgia, USA
• 11: [11] M. Youssef and A. Agrawala, "Handling samples correlation in the Horus system," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 12: [12] R. Battiti, M. Brunato, and A. Villani, "Statistical Learning Theory for Location Fingerprinting in Wireless LANs," University of Trento, Department of Information and Communication Technology, Trento, Italy, DIT 02-086, 2003.
• 13: [13] P. Prasithsangaree, P. Krishnamurthy, and P. K. Chrysanthis, "On indoor position location with wireless LANs," in Proc. 13th IEEE PIMRC Conf., Sep. 2002.
• 14: [14]. [Online]. Available: http://www.cs.umd.edu/~moustafa/location_pa- pers. htm
• 15: [15] K. Mechitov, S. Sandresh, Y. Kwon, and G. Agha, "Cooperative Tracking with Binary-Detection Sensor Networks," University of Illinois at Urbana-Champaign Computer Science Department, Tech. Rep. UIUCDCS-R-2003-2379, 2003.
• 16: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 17: [17] J. W. McKown and R. L. Hamilton Jr., "Ray tracing as a design tool for radio networks," IEEE Netw. Mag., pp. 27-30, Nov. 1991.
• 18: [18] N. Bulusu, J. Heidemann, and D. Estrin, "GPS-Less Low Cost Outdoor Localization for Very Small Devices," University of Southern California/Information Sciences Institute, Tech. Rep. 00-729, 2000.
• 19: Asis Nasipuri , Kai Li, A directionality based location discovery scheme for wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570754]
• 20: Sasha Slijepcevic , Seapahn Megerian , Miodrag Potkonjak, Location errors in wireless embedded sensor networks: sources, models, and effects on applications, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.3, July 2002 [doi>10.1145/581291.581301]
• 21: [21] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications , 2nd ed. New York: Springer-Verlag, 1998.
• 22: [22] H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations," Ann. Math. Statist., vol. 23, pp. 493-507, 1952.
• 23: [23] (2002) ILOG CPLEX 8.0. ILOG, Inc., Mountain View, California. [On-line]. Available: http://www.ilog.com
• 24: [24] M. Daskin, Network and Discrete Location. New York: Wiley, 1995.
• 25: [25] T. IIhan and M. Pinar. An Efficient Exact Algorithm for the Vertex p-Center Problem. [Online]. Available: http://www.ie.bilkent.edu.tr/ mustafap/pubs/
• 26: F. Aykut Özsoy , Mustafa Ç. Pinar, An exact algorithm for the capacitated vertex p-center problem, Computers and Operations Research, v.33 n.5, p.1420-1436, May 2006 [doi>10.1016/j.cor.2004.09.035]
• 27: [27] R. Rockafellar, Convex Analysis. Princeton, NJ: Princeton University Press, 1970.
• 28: [28] C. C. Leang and D. H. Johnson, "On the asymptotics of M-hypothesis Bayesian detection," IEEE Trans. Inf. Theory, vol. 43, pp. 280-282, Jan. 1997.
• 29: Joseph C. Liberti , Theodore S. Rappaport, Smart Antennas for Wireless Communications: IS-95 and Third Generation CDMA Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 30: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Algorithms, Design

Keywords:
hypothesis testing, information theory, mathematical programming/optimization, sensor networks, stochastic processes