Improved MDS-based localization

TLDR

Knowing node positions is valuable, but equipping every node with GPS is costly; MDS‑MAP estimates locations from connectivity data but is centralized and thus limited in many settings. This paper introduces MDS‑MAP(P), a distributed variant of MDS‑MAP that uses patches of relative maps. The method constructs a local map at each node from its neighbors, merges these patches into a global map, and optionally refines the result for higher accuracy. Simulations show that MDS‑MAP(P) matches the original method on uniform networks and outperforms it on irregular topologies, especially when shortest‑path distances poorly approximate Euclidean distances.

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.