The goal of the sensor network localization problem is to determine positions of all sensor nodes in a network given certain pairwise noisy distance measurements and some anchor node positions. This paper describes a distributed localization algorithm based on second-order cone programming relaxation. We show that the sensor nodes can estimate their positions based on local information. Unlike previous approaches, we also consider the effect of inaccurate anchor positions. In the presence of anchor position errors, the localization is performed in three steps. First, the sensor nodes estimate their positions using information from their neighbors. In the second step, the anchors refine their positions using relative distance information exchanged with their neighbors and finally, the sensors refine their position estimates. We demonstrate the convergence of the algorithm numerically. Simulation study, for both uniform and irregular network topologies, illustrates the robustness of the algorithm to anchor position and distance estimation errors, and the performance gains achievable in terms of localization accuracy, problem size reduction and computational efficiency.
Bibliographical noteFunding Information:
Manuscript received February 27, 2007; revised August 15, 2007 and February 14, 2008; accepted March 1, 2008. The associate editor coordinating the review of this paper and approving it for publication was R. Fantacci. This research is supported in part by the National Science Foundation, grant no. DMS-0610037 and in part by the USDOD ARMY, grant no. W911NF-05-1-0567.
- Convex optimization
- Distributed algorithms
- Relaxation methods
- Second-order cone programming
- Synchronous and asynchronous algorithms