MSP: multi-sequence positioning of wireless sensor nodes

ABSTRACT

Wireless Sensor Networks have been proposed for use in many location-dependent applications. Most of these need to identify the locations of wireless sensor nodes, a challenging task because of the severe constraints on cost, energy and effective range of sensor devices. To overcome limitations in existing solutions, we present a Multi-Sequence Positioning (MSP) method for large-scale stationary sensor node localization in outdoor environments. The novel idea behind MSP is to reconstruct and estimate two-dimensional location information for each sensor node by processing multiple one-dimensional node sequences, easily obtained through loosely guided event distribution. Starting from a basic MSP design, we propose four optimizations, which work together to increase the localization accuracy. We address several interesting issues, such as incomplete (partial) node sequences and sequence flip, found in the Mirage test-bed we built. We have evaluated the MSP system through theoretical analysis, extensive simulation as well as two physical systems (an indoor version with 46 MICAz motes and an outdoor version with 20 MICAz motes). This evaluation demonstrates that MSP can achieve an accuracy within one foot, requiring neither additional costly hardware on sensor nodes nor precise event distribution. It also provides a nice tradeoff between physical cost (anchors) and soft cost (events), while maintaining localization accuracy.

REFERENCES

• 1: CC2420 Data Sheet. Avaiable at http://www.chipcon.com/.
• 2: P. Bahl and V. N. Padmanabhan. Radar: An In-Building RF-Based User Location and Tracking System. In IEEE Infocom '00.
• 3: M. Broxton, J. Lifton, and J. Paradiso. Localizing A Sensor Network via Collaborative Processing of Global Stimuli. In EWSN '05.
• 4: N. Bulusu, J. Heidemann, and D. Estrin. GPS-Less Low Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications Magazine, 7(4), 2000.
• 5: David Culler , Deborah Estrin , Mani Srivastava, Guest Editors' Introduction: Overview of Sensor Networks, Computer, v.37 n.8, p.41-49, August 2004 [doi>10.1109/MC.2004.93]
• 6: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 7: 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]
• 8: 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]
• 9: Branislav Kusy , Prabal Dutta , Philip Levis , Miklos Maroti , Akos Ledeczi , David Culler, Elapsed time on arrival: a simple and versatile primitive for canonical time synchronisation services, International Journal of Ad Hoc and Ubiquitous Computing, v.1 n.4, p.239-251, July 2006 [doi>10.1504/IJAHUC.2006.010505]
• 10: Loukas Lazos , Radha Poovendran, SeRLoc: secure range-independent localization for wireless sensor networks, Proceedings of the 3rd ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023646.1023650]
• 11: Miklós Maróti , Péter Völgyesi , Sebestyén Dóra , Branislav Kusý , András Nádas , Ákos Lédeczi , György Balogh , Károly Molnár, Radio interferometric geolocation, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098920]
• 12: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 13: 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]
• 14: R. Nagpal and D. Coore. An Algorithm for Group Formation in an Amorphous Computer. In PDCS '98.
• 15: D. Niculescu and B. Nath. Ad-Hoc Positioning System. In GlobeCom '01.
• 16: D. Niculescu and B. Nath. Ad hoc Positioning System (APS) Using AOA. In InfoCom '03.
• 17: 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]
• 18: K. Römer. The Lighthouse Location System for Smart Dust. In MobiSys '03.
• 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: Radu Stoleru , Tian He , John A. Stankovic , David Luebke, A high-accuracy, low-cost localization system for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098921]
• 21: Radu Stoleru , Pascal Vicaire , Tian He , John A. Stankovic, StarDust: a flexible architecture for passive localization in wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182814]
• 22: E. W. Weisstein. Plane Division by Lines. mathworld.wolfram.com.
• 23: B. H. Wellenhoff, H. Lichtenegger, and J. Collins. Global Positions System: Theory and Practice, Fourth Edition. Springer Verlag, 1997.
• 24: K. Whitehouse. The Design of Calamari: an Ad-hoc Localization System for Sensor Networks. In University of California at Berkeley, 2002.
• 25: Z. Zhong. MSP Evaluation and Implementation Report. Avaiable at http://www.cs.umn.edu/~zhong/MSP.
• 26: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
localization, node sequence processing, wireless sensor networks