Force-directed approaches to sensor localization. ALENEX-06

As the number of application areas where sensor networks are used increases, the sensor network localization problem gains more importance. It is the problem of recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this paper, we consider the anchor-free sensor localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor’s neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with non-convex or non-simple underlying topology. Moreover the distributed nature of the problem makes some of the available techniques useless in a wide range of applications. To address these problems we describe a multi-scale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are appropriately modified with a multi-scale extension to handle the scalability issue and a dead-reckoning extension to overcome the problematic case