On the accuracy of multi-hop relative location estimation in wireless sensor networks

ABSTRACT

Knowledge of node's locations is an essential requirement for many applications of wireless sensor networks. A major problem with multi-hop location discovery is the accumulated error. In this paper, we analyze the effect of reflection errors and present the Multi-hop Relative Location Estimation (MRLE) algorithm that estimates relative node's positions with low error margins. We capture the impact of different parameters on the accuracy of the estimated position and introduce a new metric, called the CLIQUE factor, that has a very dominant effect on the accuracy of the estimated positions. We further highlight means for trading accuracy for energy consumption and/or computational overhead.

REFERENCES

• 1: N. Bulusu, J. Heidemann, and D. Estrin. GPS-less Low-cost Outdoor Localization for Very Small Devices. IEEE Personal Communications, 7(5):28--34, October 2000.
• 2: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 3: X. Cheng, A. Thaeler, G. Xue, and D. Chen. Tps: A time-based positioning scheme for outdoor sensor networks. In the Proceedings of IEEE Conference on Computer Communications (INFOCOM), March 2004.
• 4: D. Niculescu and B. Nath. Ad-hoc positioning system. In the Proceedings of IEEE Global Communication Conference (Globcom'01), November 2001.
• 5: 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]
• 6: Y. Shang and W. Ruml. Improved mds-based localization. In the Proceedings of IEEE Conference on Computer Communications (INFOCOM), March 2004.
• 7: 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]
• 8: A. Youssef, A. Agrawala, and M. Younis. Accurate Anchor-Free Localization in Wireless Sensor Networks. In the Proceedings of the 1st IEEE Workshop on Information Assurance in Wireless Sensor Networks (WSNIA 2005), Phoenix, Arizona, April 2005.

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, Performance

Keywords:
CLIQUE factor, error analysis, multi-hop localization