Anchor-Free Distributed Localization

The Anchor-Free Distributed Localization-Algorithm (AFL) algorithm by  Priyantha et al. distinguishes two separate phases: initial fold-free graph embedding and mass-spring based optimization. In the first phase, a coordinate sytem for the network is created. Hop-count is applied as metric to select particular nodes that create the axis. All nodes are then asigned initial positions based on their location in the network topology. In the second phase, the nodes are considered to be connected by springs which apply forces to them. The power of these forces depend on the difference between the measured distances to the neighbors and the distances based on the positions in the coordinate system. The mass-spring algorithm “pushes and pulls” the nodes in the coordinate system to minimize the network-wide force.

We have already some experience with an AFL implementation in the DES-Testbed. Additionally, there is a Python script simulating AFL. With the latter the algorithm can be evaluated and improved in a deterministic environment. At the current time we lack extensive results from the simulation for a sophisticated study. Further on, the simulation model represents only a best case scenario; real world issues should be considered.

For an introduction to AFL you may also have a look at some slides (german) prepared for the "Lange Nacht der Wissenschaft 2010".

Objectives

• Get familar with AFL
• Tryout the AFL implementation in Python
• Extend the implementation to make the scenario more real world like, e.g., lossy links
• Extend the implementation to simulate mobile nodes
• Run extensive study to evaluated the different parameters