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, and G. Mainetto. Experimenting an indoor bluetooth-based positioning service. In ICDCSW '03: Proceedings of the 23rd International Conference on Distributed Computing Systems, page 480, Washington, DC, USA, 2003. IEEE Computer Society.
2. D. Ashbrook and T. Starner. Using gps to learn significant locations and predict movement across multiple users. Personal Ubiquitous Comput., 7 (5):275--286, 2003.
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, USA, 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. N. Marmasse and C. Schmandt. Location-aware information delivery with commotion. In HUC, pages 157--171, 2000.
10. D. Niculescu and B. Nath. Ad hoc positioning system (aps) using aoa, in Proceedings of INFOCOM 2003, San Francisco, CA.
11. Y. Ohta, M. Sugano, and M. Murata. Autonomous localization method in wireless sensor networks. In PERCOMW '05: Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, pages 379--384, Washington, DC, USA, 2005. IEEE Computer Society.
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. N. Priyantha, A. Chakraborty, and H. Balakrishnan. The cricket location-support system. In MobiCom '00: Proceedings of the 6th Annual ACM International Conference on Mobile Computing and Networking, August 2000.
14. T. S. Rappaport. Wireless Communications: Principles and Practice. IEEE Press, Piscataway, NJ, USA, 1996.
15. A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Mobile Computing and Networking, pages 166--179, 2001.
16. Y. Shang and W. Ruml. Improved mds-based localization, In Infocom 2004.
17. Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz. Localization from mere connectivity, MobiHoc'03, Annapolis, Maryland. June 2003.
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. K. Whitehouse, C. Karlof, A. Woo, F. Jiang, and D. Culler. The effects of ranging noise on multihop localization: an empirical study. In IPSN '05: Proceedings of the 4th international symposium on Information processing in sensor networks, page 10, Piscataway, NJ, USA, 2005. IEEE Press.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization