Self-Mapping in 802.11 Location Systems

Self-Mapping in 802.11 Location Systems, Anthony LaMarca, Jeffrey Hightower, Ian Smith and Sunny Consolvo.

The authors propose a self-mapping algorithm that can reduce or even eliminate the overhead of mapping. With self mapping, only a small amount of initial map data (seed data) is needed to deploy the system. They present a graph-based algorithm for mapping radio beacons:

• Nodes in the graph represent radio beacons and weighted edges represent the nearness of the two beacons
• Edge weights are determined by using the radio scans to infer which beacons are near wich other beacons.
• By anchoring the beacons in the seed set at their known locations, we can treat the graph as a constraint problem and compute likely locations for the unknown beacons by minimizing constaint violations.

The results show that self-mapping works well in practice and is a viable alternative to explicit mapping.