Error characteristics of ad hoc positioning systems (aps)

ABSTRACT

APS algorithms use the basic idea of distance vector routing to find positions in an ad hoc network using only a fraction of landmarks, for example GPS enabled nodes. All the nodes in the network are assumed to have the possibility of measuring: range, angle of arrival (AOA), orientation, or a combination of them. We give a lower bound for positioning error in a multihop network for a range/angle free algorithm, and examine the error characteristic of four classes of multihop APS algorithms under various condition, using theoretical analysis and simulations. Analysis of range/angle free, range based, angle based, and multimodal algorithms show a complex tradeoff between the capabilities used, the density of the network, ratio of landmarks, and the quality of the position obtained.

REFERENCES

• 1: G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI Research Report ISI/RR-87-180, University of Southern California, March 1987.
• 2: Julio C. Navas , Tomasz Imielinski, GeoCast—geographic addressing and routing, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.66-76, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262132]
• 3: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 4: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 5: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 6: Nirupama Bulusu, John Heidemann, and Deborah Estrin. GPS-less low cost outdoor localization for very small devices. In IEEE Personal Communications Magazine, Special Issue on Smart Spaces and Environments. October 2000.
• 7: Paramvir Bahl and Venkata N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In INFOCOM, Tel Aviv, Israel, March 2000.
• 8: 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]
• 9: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 10: Dragoş Niculescu and Badri Nath. DV based positioning in ad hoc networks. Telecommunication Systems, Kluwer, 22(1-4):267--280, January-April 2003.
• 11: Dragoş Niculescu and Badri Nath. Ad hoc positioning system (APS) using AoA. In INFOCOM, San Francisco, CA, April 2003.
• 12: Dragoş Niculescu and Badri Nath. Position and orientation in ad hoc networks. Elsevier Ad Hoc Networks, 2003. to appear.
• 13: Radhika Nagpal. Organizing a global coordinate system from local information on an amorphous computer. Technical Report 1666, MIT AI Lab, 1999.
• 14: 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]
• 15: Koen Langendoen and Niels Reijers. Distributed localization in wireless sensor networks a quantitative comparison. Technical Report PDS-2002-3, Delft University of Technology, The Netherlands, 2002.
• 16: B.W. Parkinson and J.J. Spilker. Global Positioning System: Theory and Application. American Institute of Astronautics and Aeronautics, 1996.
• 17: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 18: Leonard Kleinrock and John Silvester. Optimum transmission radii for packet radio networks or why six is a magic number. In IEEE National Telecommunications Conference, pages 4.3.1--4.3.5, Birmingham, Alabama, 1978.
• 19: T.K. Philips, S.S. Panwar, and A.N. Tantawi. Connectivity properties of a packet radio network model. In IEEE Transactions on Information Theory, volume 35, pages 1044--1047, September 1989.
• 20: L. Doherty, L. E. Ghaoui, and K. S. J. Pister. Convex position estimation in wireless sensor networks. In IEEE INFOCOM, Anchorage, AK, April 2001.
• 21: 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]
• 22: Slobodan Simić and Shankar Sastry. A distributed algorithm for localization in random wireless networks. Technical report, UC Berkeley, EECS, 2002.
• 23: A. Savvides, W. Garber, S. Adlakha, R. Moses, and M. B. Srivastava. On the error characteristics of multihop node localization in ad-hoc sensor networks. In IPSN03, International Workshop on Information Processing in Sensor Networks, PARC, Palo Alto, CA, April 22-23 2003.
• 24: R. Moses, D. Krishnamurthy, and R. Patterson. A self-localization method for wireless sensor networks. Eurasip Journal on Applied Signal Processing, Special Issue on Sensor Networks, 2002.
• 25: Regina Bischoff , Roger Wattenhofer, Analyzing Connectivity-Based Multi-Hop Ad-hoc Positioning, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.165, March 14-17, 2004
• 26: Y. T. Chan and K. C. Ho. A simple and efficient estimator for hyperbolic location. IEEE Transactions on Signal Processing, 42(8):1905--1915, August 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

General Terms:
Algorithms, Design, Performance

Keywords:
APS, Cramér-rao lower bound, ad hoc networks, ad hoc positioning system, error analysis, multihop positioning