Self-configuring Localization Systems: Design and Experimental Evaluation

Nirupama Bulusu, John Heidemann, Deborah Estrin and Tommy Tran
University of California at Los Angeles and USC/Information Sciences Institute

Abstract

Embedded networked sensors -- those that coordinate amongst themselves to achieve a sensing task -- promise to revolutionize the way we live, work and interact with the physical environment. Fundamental to such coordination is localization, or the ability to establish spatial relationships among such devices.

In very large, ad hoc deployed sensor networks, a localization system based on beacons (special nodes that are position-aware by virtue of being endowed with more sophisticated ranging hardware) can be used to localize smaller devices consistently even in a completely decentralized and scalable manner. However, in unattended sensor networks, these localization systems must self-configure, i.e., autonomously adapt to the dynamics of their environmental setting and the availability of beacons, instead of relying on extensive pre-configuration or manual reconfiguration.

In this paper, we present the motivation, design, implementation and experimental evaluation of a self-configuring localization system based on beacons. We identify density as an important parameter in determining localization quality, and propose HEAP and STROBE, two algorithms to enable system self-configuration based on beacon density. Building on the observation that the quality of localization saturates at a transition beacon density, these algorithms (i) automate placement of new beacons at low densities to significantly improve localization quality or (ii) rotate functionality amongst redundant beacons at high beacon densities to significantly increase overall system lifetime. Our performance results include experimental results from implementation of an RF-proximity based localization system using nodes with sharply limited resources (8-bit microprocessor, 8-K ROM, 512 bytes RAM, limited battery life).

Availability

This paper will be available in several formats later: abstract web page with pointers and cites, gzip'ed postscript, PDF, paper copies can be obtained by mail to the authors.

In the meantime, please e-mail me for a draft of the paper. Copyright terms for this paper appear below.

Reference

Bulusu02b: Nirupama Bulusu, John Heidemann, Deborah Estrin and Tommy Tran. Self-configuring Localization Systems: Design and Experimental Evaluation. ACM Transactions on Embedded Computing Systems(TECS), Special Issue on Networked Embedded Computing, To appear, May 2003. <http://www.cs.ucla.edu/~bulusu/papers/Bulusu02b.html>.

@article{Bulusu02b,
	author = "Nirupama Bulusu and John Heidemann and Deborah Estrin and Tommy Tran",
	title = "Self-configuring Localization Systems: Design and Experimental Evaluation",
	booktitle = "ACM Transactions on Embedded Computing Systems", 
	year = "2003",
	publisher = "ACM",
	month = "May",
	pages = "To appear.",
	keywords = "beacon placement, location, localization,self-configuration, empirical adaptation, wireless sensor networks",
	url = "http://www.cs.ucla.edu/~bulusu/papers/Bulusu02b.html",
	psurl = "http://www.cs.ucla.edu/~bulusu/papers/Bulusu02b.ps.gz",
	pdfurl = "http://www.cs.ucla.edu/~bulusu/papers/Bulusu02b.pdf",
	organization = "University of California at Los Angeles",
}

Copyright

This paper is copyright © 2002 by its authors. Permission to make digital or hard copies of part or all of this work for personal use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.

To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission of the authors.