An Iterative Approach to Locating Simple Devices in an Ad-hoc Network

This paper considers the problems associated with location determination in wireless ad-hoc networks. It presents a simple algorithm allowing a distributed set of devices to independently determine their location given only the distances between themselves and neighbouring devices if some devices in the network (location aware devices) have external location information (such as GPS or being at a known fixed location). The algorithm allows each device to make a guess of location that it then communicates to all neighbouring devices. Depending on the information received from neighbours each device may then modify its guess. In this way, over time, the network as a whole is able to identify a set of positions that satisfies all the available distance data. The algorithm is shown to be resistant to errors in measuring the distances between devices.