Density-adaptive beacon placement algorithms for localization in ad hoc wireless networks

Nirupama Bulusu, John Heidemann, Vladimir Bychkovskiy and John Heidemann
University of California, Los Angeles and USC/Information Sciences Institute

Abstract

Pervasive computing and sensor networks are emerging as key application drivers for wireless networks. Localization is of fundamental importance to pervasive computing and sensor networks because the former operate on devices based on their physical proximity and the latter names data and organizes the network in terms of their physical location. Beacons (known-location nodes) are one key approach to achieving localization in wireless networks. This paper addresses the essential issue of beacon placement for unattended networks where beacon placement must be self-configuring. Neither uniformly dense nor centrally optimized placement are feasible for large, ad hoc deployable wireless networks that must operate in diverse, unpredictable environments. In this paper, we propose two novel distributed algorithms for beacons to adaptively self-configure to achieve the right placement and density for localization. For sparse beacon deployment, we propose HEAP, an algorithm to add new beacons so as to maximize the improvement in localization. For dense beacon deployment, we propose STROBE, a localized algorithm that rotates functionality amongst beacons to reduce interference as well as extend the system lifetime. STROBE builds on the observation that above the threshold density nu, additional beacons can be switched off without diminishing the localization granularity. We validate the intuition for our design through experiments on mores (small embedded devices). Our simulation results demonstrate the potential benefits of these algorithms. Gains with HEAP are comparable to a centralized adaptive algorithm. STROBE can extend the system lifetime 1.5 times for density 3 nu, with higher lifetime gains at higher densities.

Keywords - localization, sensor networks, beacon placement, density-adaptive

Availability

This paper is available in several formats:abstract web page with pointers and cites, gzip'ed postscript, PDF, paper copies can be obtained by mail to the authors. Copyright terms for this paper appear below.

Reference

Bulusu01b: Nirupama Bulusu, John Heidemann, Vladimir Bychkovskiy and Deborah Estrin. Density-adaptive Beacon Placement Algorithms for Localization in Ad Hoc Wireless Networks. <http://lecs.cs.ucla.edu/~bulusu/papers/Bulusu01b.html>.

@inproceedings{Bulusu01b,
        author = "Nirupama Bulusu and Deborah Estrin and Lewis Girod and John Heidemann",
        title = "Scalable Coordination for Wireless Sensor Networks: Self-configuring Localization Systems",
        booktitle = "Proceedings of the Sixth International Symposium on Communication Theory and Applications (ISCTA '01)",
        year = "2001",
        publisher = "",
        month = "July 15-20th",
        pages = "xxx",
        keywords = "low-power wireless, sensor networks, localization, self-configuration, localized algorithms.",
        url = "http://lecs.cs.ucla.edu/~bulusu/papers/Bulusu01b.html",
        psurl = "http://lecs.cs.ucla.edu/~bulusu/papers/Bulusu01b.ps.gz",
        pdfurl = "http://lecs.cs.ucla.edu/~bulusu/papers/Bulusu01b.pdf",
        organization = "University of California, Los Angeles",
}

Copyright

This paper is copyright © 2001 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.