Paper by Erik D. Demaine

Reference:: Nissanka B. Priyantha, Hari Balakrishnan, Erik D. Demaine, and Seth Teller, “Mobile-Assisted Localization in Wireless Sensor Networks”, in Proceedings of the 24th Annual Joint Conference of the IEEE Communications Society on Computer Communications (INFOCOM 2005), volume 1, Miami, Florida, March 13–17, 2005, pages 172–183.
Abstract:: The localization problem is to determine an assignment of coordinates to nodes in a wireless ad-hoc or sensor network that is consistent with measured pairwise node distances. Most previously proposed solutions to this problem assume that the nodes can obtain pairwise distances to other nearby nodes using some ranging technology. However, for a variety of reasons that include obstructions and lack of reliable omnidirectional ranging, this distance information is hard to obtain in practice. Even when pairwise distances between nearby nodes are known, there may not be enough information to solve the problem uniquely.
This paper describes MAL, a mobile-assisted localization method which employs a mobile user to assist in measuring distances between node pairs until these distance constraints form a “globally rigid” structure that guarantees a unique localization. We derive the required constraints on the mobile's movement and the minimum number of measurements it must collect; these constraints depend on the number of nodes visible to the mobile in a given region. We show how to guide the mobile's movement to gather a sufficient number of distance samples for node localization. We use simulations and measurements from an indoor deployment using the Cricket location system to investigate the performance of MAL, finding in real-world experiments that MAL's median pairwise distance error is less than 1.5% of the true node distance.
Comments:: This paper is also available from IEEE Xplore.
Updates:: Proposition 2 should additionally state that n₀ and n₁ are known to be on the same side of the line through m₀, m₁, and m₂.
Length:: The paper is 12 pages.
Availability:: The paper is available in PostScript (350k), gzipped PostScript (94k), and PDF (211k).; See information on file formats.; [Google Scholar search]