Radio propagation-aware distance estimation based on neighborhood comparison

Distance estimation is important for localization and a multitude of other tasks in wireless sensor networks. We propose a new scheme for distance estimation based on the comparison of neighborhood lists. It is inspired by the observation that distant nodes have fewer neighbors in common than close ones. Other than many distance estimation schemes, it relies neither on special hardware nor on unreliable measurements of physical wireless communication properties like RSSI. Additionally the approach benefits from message exchange by other protocols and requires a single additional message exchange for distance estimation. We will show that the approach is universally applicable and works with arbitrary radio hardware. We discuss related work and present the new approach in detail including its mathematical foundations. We demonstrate the performance of our approach by presenting various simulation results.