People/Web Search Calendar Emergency Info A-Z Index UVA Email University of Virginia

Computer Science Colloquia

Monday, May 9, 2011
Mario Marino Ph.D. Qualifying Exam
Advisor: Kevin Skadron
Attending Faculty: Kim Hazelwood; Sudhanva Gurumurthi; Westley Weimer

Olsson Hall 236D, 01:00:00

KOLF: Kirchhoff Optimal Localization Framework for Wireless Sensor Networks

Many approaches have been proposed to solve the localization problem in wireless sensor networks (WSN). However, there are several drawbacks to these solutions: first, most of them only provide estimates of the location, but not the confidence of the estimates; second, they assume that all measurements have the same accuracy or differentiate them only to a limited extent, which results in non-optimal estimates. In this paper, we present KOLF, a Kirchhoff Optimal Localization Framework for WSN localization. To our best knowledge, KOLF is the first WSN localization approach which takes quantitative uncertainties of measurements into consideration and derives an optimal location estimate (with minimum mean square error) based on all available location information. The underlying theory of KOLF is the spatial relation uncertainty theory, in which the localization problem is transformed to deducing the optimal relation between each node and the global origin in an uncertain relation graph. In order to apply the deduction to any complex relation graph, we present a general deduction algorithm which uses the Kirchhoff's Circuit Law to deduce the optimal equivalent relation between any node pair. Moreover, we propose several implementations of KOLF.

Extensive simulation demonstrates that the localization accuracy of KOLF achieves sub-meter error within 5 rounds when the maximum distance to the anchor node is 95 meters. The preferred distributed implementation is 96.4% as accurate as the optimal one in the 500-node network with 5% of the nodes being anchors. Furthermore, the deduced uncertainty has very important guidance to practical applications, since 99% of the estimates fall into the range of 2 standard deviations to the real positions.