Error analysis of localization systems for sensor networks

ABSTRACT

The establishment of a localization system is an important task in wireless sensor networks. Due to the geographic correlation of the sensed data, location information is commonly used to name the gathered data, address nodes and regions, and also improve the performance of many geographic algorithms. Depending on the localization algorithm, different error behaviors (e.g., mean, probability distribution, and correlation) can be exhibited by the sensor network. The process of understanding and analysing this behavior is the first step toward a mathematical model of the localization error. Furthermore, this knowledge can also be used to propose improvements to these systems. In this work, we divide the localization systems into three components: distance estimation, position computation, and the localization algorithm. We show how each component can affect on the final error of the system. In this work, we concentrate on the third component: the localization algorithm. The error behaviors of three known localization algorithms are evaluated together in similar scenarios so the different behaviors of the localization error can be identified and analysed. The influence of these errors in geographic algorithms is also analysed, showing the importance of understanding the error behavior and the importance of geographic algorithms which consider the inaccuracy of position estimations.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Recursive Position Estimation in Sensor Networks, Proceedings of the Ninth International Conference on Network Protocols, p.35, November 11-14, 2001
• 3: Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004 [doi>10.1145/972627.972630]
• 4: L. Doherty, K. S. Pister, and L. E. Ghaoui. Convex position estimation in wireless sensor networks. In INFOCOM 2001, volume~3, pages 1655--1663, Anchorage, AK, USA, April 2001.
• 5: L. Girod and D. Estrin. Robust range estimation using acoustic and multimodal sensing. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), volume~3, pages 1312--1320, Maui, Hawaii, USA, October/November 2001.
• 6: G. H. Golub and C. F. V. Loan. Matrix Computations. JohnsHopkinsPress, Baltimore, MD, USA, second edition, 1989.
• 7: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 8: John Heidemann , Fabio Silva , Deborah Estrin, Matching data dissemination algorithms to application requirements, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958517]
• 9: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 10: B. Hofmann-Wellenho, H. Lichtenegger, and J.Collins. Global Positioning System: Theory and Practice. Springer-Verlag, fourth edition, 1997.
• 11: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 12: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 13: Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
• 14: K. Langendoen and N. Reijers. Distributed localization algorithms. In R. Zurawski, editor, Embedded Systems Handbook. CRC press, Aug. 2005. To Appear.
• 15: 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]
• 16: D. Niculescu and B. Nath. Ad hoc positioning system (aps). In IEEE Global Communications Conference (GlobeCom '01), pages 2926--2931, San Antonio, TX, USA, November 2001.
• 17: NS-2. The network simulator - ns-2, Access: march 2005. {Online} Available: http://www.isi.edu/nsnam/ns/.
• 18: H. Oliveira, E. Nakamura, A. Loureiro, and A. Boukerche. Directed position estimation: a recursive localization approach for wireless sensor networks. In The 14th IEEE International Conference on Computer Communications and Networks, San Diego, California, USA, 2005.
• 19: 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]
• 20: V. Ramadurai and M. L. Sichitiu. Localization in wireless sensor networks: A probabilistic approach. In Proc. of the 2003 International Conference on Wireless Networks (ICWN 2003), pages 275--281, Las Vegas, NV, USA, June 2003.
• 21: 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]
• 22: Karim Seada , Ahmed Helmy , Ramesh Govindan, On the effect of localization errors on geographic face routing in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984633]
• 23: 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]
• 24: M. L. Sichitiu and V. Ramadurai. Localization of wireless sensor networks with a mobile beacon. In Proc. of the 1st IEEE International Conference on Mobile Ad hoc and Sensor Systems (MASS 2004), pages 174--183, Florida, USA, October 2004.
• 25: K. Whitehouse. The design of calamari: an ad-hoc localization system for sensor networks. Master's thesis, University of California at Berkeley, 2002.
• 26: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 27: Y. Yu, R. Govindan, and D. Estrin. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks. Technical Report UCLA/CSD-TR-01-0023, UCLA Computer Science Department, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Management

Keywords:
error analysis, localization systems, sensor networks