Indoor people tracking based on dynamic weighted multidimensional scaling

ABSTRACT

Accurate location of people in indoor environments is a key aspect of many applications such as resource management or security. In this paper, we explore the use of short-range radio technologies to track people indoors. The network consists of two kind of radio nodes: static nodes (anchors) and mobile nodes (people). From a set of sparse connectivity matrices (people vs. people and people vs. anchors) at each time instant and people's dynamics, we infer people's trajectories. To combine connectivity and dynamic information, we propose an extension of Multidimensional Scaling(MDS), Dynamic Weighted MDS (DWMDS), that finds an embedding of people's trajectories (x and y coordinates of people through time). DWMDS has proven to be more accurate and effective, especially for low connectivity degree networks (i.e. sparse networks), compared to existing location algorithms. Extensive simulations show the effectiveness and robustness of the proposed algorithm.

REFERENCES

• 1: G. Anastasi , R. Bandelloni , M. Conti , F. Delmastro , E. Gregori , G. Mainetto, Experimenting an Indoor Bluetooth-Based Positioning Service, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.480, May 19-22, 2003
• 2: Daniel Ashbrook , Thad Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, v.7 n.5, p.275-286, October 2003 [doi>10.1007/s00779-003-0240-0]
• 3: P. Bahl and V. N. Padmanabhan. Radar: An in-building rf-based user location and tracking system. In INFOCOM, pages 775--784, 2000.
• 4: T. F. Cox, M. A. A. Cox, and T. F. Cox. Multidimensional Scaling, Second Edition. Chapman & Hall/CRC, September 2000.
• 5: E. Elnahrawy, X. Li, and R. P. Martin. The limits of localization using signal strength: a comparative study. Sensor and Ad Hoc Communications and Networks, 2004. IEEE SECON 2004, pages 406--414, 2004.
• 6: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 7: X. Ji. Sensor positioning in wireless ad-hoc sensor networks with multidimensional scaling, In Infocom 2004.
• 8: K. Lorincz and M. Welsh. A robust, decentralized approach to rf-based location tracking. Technical Report TR-04-04, Harvard University, 2004.
• 9: Natalia Marmasse , Chris Schmandt, Location-Aware Information Delivery with ComMotion, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.157-171, September 25-27, 2000, Bristol, UK
• 10: D. Niculescu and B. Nath. Ad hoc positioning system (aps) using aoa, in Proceedings of INFOCOM 2003, San Francisco, CA.
• 11: Yoshikazu Ohta , Masashi Sugano , Masayuki Murata, Autonomous Localization Method in Wireless Sensor Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.379-384, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.18]
• 12: N. Patwari, A. III, M. Perkins, N. Correal, and R. O'Dea. Relative location estimation in wireless sensor networks. In IEEE Transactions on Signal Processing, pages 2137--2148, Piscataway, NJ, USA, 2003. IEEE Signal Processing Society.
• 13: 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]
• 14: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 15: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 16: Y. Shang and W. Ruml. Improved mds-based localization, In Infocom 2004.
• 17: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 18: V. Vivekanandan and V. W. Wong. Ordinal mds-based localization for wireless sensor networks. In VTC-2006: IEEE 64th Vehicular Technology Conference, pages 1--5, 2006.
• 19: Kamin Whitehouse , Chris Karlof , Alec Woo , Fred Jiang , David Culler, The effects of ranging noise on multihop localization: an empirical study, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

General Terms:
Algorithms, Performance

Keywords:
connectivity data, indoor tracking, people's dynamics, rss, short-range radio technologies