Real-time trajectory estimation in mobile ad hoc networks

ABSTRACT

In this paper, we propose a new trajectory estimation method named TRADE (TRAjectory estimation in DEcentralized way). TRADE is a range-free localization algorithm in fully decentralized mobile ad hoc networks. In TRADE, each mobile node periodically transmits messages containing its estimated trajectory information, and re-computes its own trajectory using those from its neighbors. This information exchange considerably contributes to improvement of the position accuracy. Furthermore, we give the optimal design of the protocol based on the analysis of the algorithm property. Through the analysis, we consider how much trajectory information should be exchanged among nodes to estimate the position within a certain error range in the protocol design. We have evaluated the position accuracy under various settings, and have shown the effectiveness of the protocol in the real world through two realistic application examples.

REFERENCES

• 1: P. Bahl and V. N. Padmanabhan. RADAR: an in-building RF-based user location and tracking system. In Proc. of INFOCOM 2000, pages 775--784, 2000.
• 2: J. M. Cabero, F. D. la Torre, A. Sanchez, and I. Arizaga. Indoor people tracking based on dynamic weighted multidimensional scaling. In Proc. of MSWiM 2007, pages 328--335, 2007.
• 3: F. Fleuret, J. Berclaz, R. Lengagne, and P. Fua. Multicamera people tracking with a probabilistic occupancy map. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(2):267--282, 2008.
• 4: S. Fujii, A. Uchiyama, T. Umedu, H. Yamaguchi, and T. Higashino. An off-line algorithm to estimate trajectories of mobile nodes using ad-hoc communication. In Proc. of PerCom 2008, pages 117--124, 2008.
• 5: T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proc. of MobiCom 2003, pages 81--95, 2003.
• 6: L. Hu and D. Evans. Localization for mobile sensor networks. In Proc. of MobiCom 2004, pages 45--57, 2004.
• 7: A. Kleiner and D. Sun. Decentralized SLAM for pedestrians without direct communication. Proc. of International Conference on Intelligent Robots and Systems (IROS 2007), pages 1461--1466, 2007.
• 8: H. Lee, M. Wicke, B. Kusy, and L. Guibas. Localization of mobile users using trajectory matching. In Proc. of MELT 2008, pages 123--128, 2008.
• 9: M. Li and Y. Liu. Rendered path: range-free localization in anisotropic sensor networks with holes. In Proc. of MobiCom 2007, pages 51--62, 2007.
• 10: B. T. Morris and M. M. Trivedi. A survey of vision-based trajectory learning and analysis for surveillance. IEEE Transactions on Circuits and Systems for Video Technology, 18(8):1114--1127, 2008.
• 11: R. Nagpal, H. Shrobe, and J. Bachrach. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proc. of IPSN 2003, pages 333--348, 2003.
• 12: N. B. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket location-support system. In Proc. of MobiCom 2000, pages 32--43, 2000.
• 13: Y. Shang, W. Rml, Y. Zhang, and M. Fromherz. Localization from connectivity in sensor networks. IEEE Transaction on Parallel and Distributed Systems, 15(11):961--974, 2004.
• 14: A. Uchiyama, S. Fujii, K. Maeda, T. Umedu, H. Yamaguchi, and T. Higashino. Ad-hoc localization in urban district. In Proc. of INFOCOM 2007 Mini-Symposium, pages 2306--2310, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

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

General Terms:
Algorithms, Design

Keywords:
decentralized algorithm, localization, mobile ad hoc network, range-free, trajectory estimation