Rendered path: range-free localization in anisotropic sensor networks with holes

ABSTRACT

Sensor positioning is a crucial part of many location-dependent applications that utilize wireless sensor networks (WSNs). Current localization approaches can be divided into two groups: range-based and range-free. Due to the high costs and critical as-sumptions, the range-based schemes are often impractical for WSNs. The existing range-free schemes, on the other hand, suffer from poor accuracy and low scalability. Without the help of a large number of uniformly deployed seed nodes, those schemes fail in anisotropic WSNs with possible holes. To address this issue, we propose the Rendered Path (REP) protocol. To the best of our knowledge, REP is the only range-free protocol for locating sen-sors with constant number of seeds in anisotropic sensor net-works.

REFERENCES

• 1: P. Bahl and V. N. Padmanabhan, "RADAR: An In-Building RF-Based User Location and Tracking System," in Proceedings of IEEE INFOCOM, 2000.
• 2: Pratik Biswas , Yinyu Ye, Semidefinite programming for ad hoc wireless sensor network localization, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984630]
• 3: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, MAP: medial axis based geometric routing in sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080839]
• 4: N. Bulusu, J. Heidemann and D. Estrin, "GPS-less Low Cost Outdoor Localization For Very Small Devices," IEEE Personal Communication Magazine, vol. 7(5), pp. 28--34, 2000.
• 5: Marcelo M. Carvalho , J. J. Garcia-Luna-Aceves, A scalable model for channel access protocols in multihop ad hoc networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023753]
• 6: S. P. Fekete, A. Kroller, D. Pfister, S. Fischer and C. Busch-mann, "Neighbor-based Topology Recognition in Sensor Networks," in Proceedings of ALGOSENSORS, 2004.
• 7: Stefan Funke, Topological hole detection in wireless sensor networks and its applications, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080819]
• 8: David K. Goldenberg , Pascal Bihler , Ming Cao , Jia Fang , Brian D. O. Anderson , A. Stephen Morse , Y. Richard Yang, Localization in sparse networks using sweeps, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161103]
• 9: 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]
• 10: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 11: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 12: X. Ji and H. Zha, "Sensor Positioning in Wireless Ad-hoc Sensor Networks with Multidimensional Scaling," in Proceedings of IEEE INFOCOM, 2004.
• 13: H. Lim and J. C. Hou, "Localization for Anisotropic Sensor Networks," in Proceedings of IEEE INFOCOM, 2005.
• 14: H. Lim, L. Kung, J. Hou and H. Luo, "Zero-Configuration, Robust Indoor Localization: Theory and Experimentation," in Proceedings of IEEE INFOCOM, 2006.
• 15: David Moore , John Leonard , Daniela Rus , Seth Teller, Robust distributed network localization with noisy range measurements, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031502]
• 16: Lionel M. Ni , Yunhao Liu , Yiu Cho Lau , Abhishek P. Patil, LANDMARC: Indoor Location Sensing Using Active RFID, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.407, March 23-26, 2003
• 17: D. Niculescu and B. Nath, "Ad Hoc Positioning System (APS) using AOA," in Proceedings of IEEE INFOCOM, 2003.
• 18: D. Niculescu and B. Nath, "DV Based Positioning in Ad Hoc Networks," Journal of Telecommunication Systems, 2003.
• 19: 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]
• 20: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 21: Y. Shang and W. Ruml, "Improved MDS-Based Localization," in Proceedings of IEEE INFOCOM, 2004.
• 22: 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]
• 23: Satish Vedantam , Urbashi Mitra , Ashutosh Sabharwal, Sensing the channel: sensor networks with shared sensing and communications, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127818]
• 24: Yue Wang , Jie Gao , Joseph S.B. Mitchell, Boundary recognition in sensor networks by topological methods, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161104]
• 25: B. H. Wellenhoff, H. Lichtenegger and J. Collins, Global Positioning System: Theory and Practice: Springer Verlag, 1997.

INDEX TERMS

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

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays; Graphs and networks

General Terms:
Algorithms, Design, Theory

Keywords:
anisotropic, range-free localization, wireless sensor network