Improved MDS-based localization
Top Cited Papers
- 17 January 2005
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 4, 2640-2651
- https://doi.org/10.1109/infcom.2004.1354683
Abstract
It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. MDS-MAP is a recent localization method based on multidimensional scaling (MDS). It uses connectivity information - who is within communications range of whom - to derive the locations of the nodes in the network, and can take advantage of additional data, such as estimated distances between neighbors or known positions for certain anchor nodes, if they are available. However, MDS-MAP is an inherently centralized algorithm and is therefore of limited utility in many applications. In this paper, we present a new variant of the MDS-MAP method, which we call MDS-MAP(P) standing for MDS-MAP using patches of relative maps, that can be executed in a distributed fashion. Using extensive simulations, we show that the new algorithm not only preserves the good performance of the original method on relatively uniform layouts, but also performs much better than the original on irregularly-shaped networks. The main idea is to build a local map at each node of the immediate vicinity and then merge these maps together to form a global map. This approach works much better for topologies in which the shortest path distance between two nodes does not correspond well to their Euclidean distance. We also discuss an optional refinement step that improves solution quality even further at the expense of additional computation.Keywords
This publication has 14 references indexed in Scilit:
- Localization from mere connectivityPublished by Association for Computing Machinery (ACM) ,2003
- Convex position estimation in wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Location in distributed ad-hoc wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Ad hoc positioning system (APS)Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scalable Information-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor NetworksThe International Journal of High Performance Computing Applications, 2002
- Location systems for ubiquitous computingComputer, 2001
- GPS-less low-cost outdoor localization for very small devicesIEEE Wireless Communications, 2000
- Directed diffusionPublished by Association for Computing Machinery (ACM) ,2000
- A review of current routing protocols for ad hoc mobile wireless networksIEEE Wireless Communications, 1999
- Modern Multidimensional ScalingPublished by Springer Nature ,1997