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 implemented AFL based on our DES-LOFT framework and ran some inital experiments. 16 individual scenarios were considered based on the following parameters:

Dimensions: 2d or 3d space
Algorithmn: original phase 1 algorithm (MIT-Standard) or modified version (MIT-Enhanced)
Distance Error: include an 0, 5, or 10% error in distance measurements
Anchors: 5 anchor nodes or none

We number the experiments as follows:

Dimension	Algorithm	Error [%]	Anchor	#
2d	MIT-Standard	0	none	1
2d	MIT-Standard	0	5	2
2d	MIT-Standard	5	none	3
2d	MIT-Standard	10	none	4
2d	MIT-Enhanced	0	none	5
2d	MIT-Enhanced	0	5	6
2d	MIT-Enhanced	5	none	7
2d	MIT-Enhanced	10	none	8
2d	MIT-Standard	0	none	9
3d	MIT-Standard	0	5	10
3d	MIT-Standard	5	none	11
3d	MIT-Standard	10	none	12
3d	MIT-Enhanced	0	none	13
3d	MIT-Enhanced	0	5	14
3d	MIT-Enhanced	5	none	15
3d	MIT-Enhanced	10	none	16

The following graphs show three different metric values for the first two minutes. The metrics are

Average Percentage Error of Distances (APE): describes the average percentaged error of all node-to-node distances
Average Euclidian Distances} (AED): representing how good the localization matches the real topology by averaging over the absolute deviation of each node; makes only sense with anchor nodes
Global Energy Ratio (GER): represents the structural error in the determined embedding compared with the real topology

Each box-plot contains