A science campus Marauder's Map

There are hundreds of Wi-Fi access points at our campus. They're constantly broadcasting a beacon signal that identifies each station by a MAC address. The signals can be passively received by any Wi-Fi equipped device. Exploiting this fact, I wrote a program to help locate lost students and staff wandering around the campus. I submitted it as a project for my positioning class.

[Image: An indoor map of a building titled 'Exactum K', made to look like the stereotypical 'treasure map' on old paper. Several rooms are labeled. Three placemarks with different colors, drawn in an anachronistically modern style, are labeled with online screen names.]

Before the positioning would work, I could be seen walking around with my computer and mapping the Wi-Fi signal at various places. I would stay in one place for several minutes and collect signal strengths of all devices in range. I would then take each pair of access points and calculate a power ratio every few seconds; then assume a normal distribution and fit a Gaussian curve onto it; and save the Gaussian parameters in a database along with discrete location information input manually. (Kjaergaard, M.B. "Hyperbolic Location Fingerprinting: A Calibration-Free Solution for Handling Differences in Signal Strength", Pervasive Computing and Communications, 2008, Sixth Annual IEEE International Conference on, pp. 110–116)

To determine the position of a computer, a script is run that lists all signal strengths of all stations in range. Again, power ratios are calculated, and the fitted Gaussians are compared to Gaussians saved in the database. A location with the highest probability is determined using Bayesian inference and plotted on a map inspired by the Harry Potter realm.

Hearing 40 APs
┌─────────────────────────────┐
│═                            │  9.417e-217  24 Haxxorointiluokka
│═════════════════════════════│  2.011e-207  28 Navetta
│══════════════════           │  2.607e-211  27 Gurulan sohva
│════                         │  8.437e-216  25 Gurulan pöytä
│═══════════════════          │  8.032e-211  25 Unicafe Exactum (Gurulan puoli)
│═══════════════              │  1.079e-212  25 CK112 takaosa
│══════════════════════       │  1.107e-209  25 CK112 keskiosa
│═════════════════            │  9.121e-212  25 CK112 etuosa
│════════════════             │  1.986e-212  24 Unicafe Exactum (Normaali puoli)
│                             │  0.000e+00    2 BK107
│═════════════                │  4.054e-214  27 D123
│═                            │  6.020e-218  18 C127
│                             │  0.000e+00   12 C222
│                             │  0.000e+00   10 D234
│                             │  0.000e+00    9 Linus Torvalds -auditorio
│                             │  0.000e+00    0 Liikuntakeskus
│                             │  0.000e+00    0 Unicafe Physicum
│                             │  0.000e+00    0 Chemicumin aula
│                             │  0.000e+00    2 Lars Ahlfors -auditorio
│                             │  0.000e+00    4 B221
│                             │  0.000e+00    0 Unicafe Protoni
│                             │  0.000e+00    0 Unicafe Neutroni
│                             │  0.000e+00    5 B222
│                             │  0.000e+00   12 C323
│══════                       │  8.308e-215  25 CK110   
│                             │  0.000e+00    0 Puutarha
│                             │  0.000e+00    0 Kirjasto: yläkerran lukumesta
│                             │  0.000e+00    0 Kirjasto: hiljainen lukusali
│                             │  0.000e+00    0 Kirjasto: alakerran lukumesta (ikk.)
│                             │  0.000e+00    0 Kirjasto: alakerran lukumesta
└─────────────────────────────┘

we're in: --> Navetta <--
done

This is fun but presents a few problems. To get low-level access to the Wi-Fi interface on Linux, iwlist wlan0 scan needs to be run as a privileged user (i.e. root). Also, the prerecorded model of signal strengths gets out of sync with the real world in a few weeks, probably because of minute changes in room interiors. The positioning still works, but room-level resolution is lost. An automatically updating model would be practical, since the manual recording phase is pretty tedious.

The Perl source is on GitHub [hox: for scientific interest only; it's not a complete, working program].

8 comments:

  1. This is a great idea, but ugh! the script only works on Linux.

    Is there a way to make this run on FreeBSD?

    ReplyDelete
    Replies
    1. Yeah, I shouldn't really have published the scripts, they're not a working program :) My last attempt at installing FreeBSD crashed the host OS of the virtual machine, I hope it works next time.

      Delete
  2. Google used to have an API for doing queries on location based on surrounding access points. I implemented a client for it and during testing it seemed like it would just throw away signal strength. Maybe that data is just to uncertain to really use?

    ReplyDelete
    Replies
    1. Google's geolocation API aims to position the client on the world map, at a granularity of some hundreds of meters. Thus, Google only needs to know the MAC addresses of some of the surrounding access points, indeed with no information about signal strength. I aimed from room-level indoors accuracy or even better. Also, on our campus, almost a hundred access points are reachable from any given location, which renders the Google approach impractical for campus use.

      Delete
  3. Cool project!

    As a note about the varying AP signal strength you observed - yes the minute changes in the physical environment could cause this, but another important variable would be the centrally controlled wireless management system (very likely in use at a uni).

    Typical enterprise-grade WLAN installs will have a 'wireless controller' that manages all of the APs, and is able to dynamically adjust the radio power and channel for each AP. The APs listen to beacons from other APs within range, and report this info back to the controller. The controller is then able to dynamically adjust power levels and channel usage to create optimal WLAN coverage.

    All of that real-time AP radio information could be grabbed from the controller or direct from the AP via SNMP.

    ReplyDelete
  4. Yes, it would be worth looking if there is some sort of API to the wifi controller (to which your institution would give you access) to do this, as it would simplify things greatly.

    In theory, if you know where each AP is and can plot it's position in space, the controller should be able to feed you power readings for each client, and allow you to triangulate each client station based on it's visibility from each AP.

    This would avoid having to run clients on devices, the need to manually map the signal, and the problem of needing to run as root on clients to get low-level info from the wifi driver.

    A friend and I had an idea to do almost exactly what you've done here for a tech conference about 7 or so years ago, when the Trapeze Networks (now part of Juniper) kit was relatively new, or at least their functionality to triangulate client stations was.

    Sadly time and workload were not on our side, and lo-jacking our meeting attendees (or at least their devices) remained an idea only. Cool to see someone's actually tried doing this. :)

    ReplyDelete
    Replies
    1. Nitpick: No one triangulates wifi signals. They trilaterate wifi signals. (The latter involves distances instead of angles - intersecting circles or spheres, instead of intersecting lines.) It runs into trouble if you don't have a very good model of signal attenuation with all the walls in the right places. I believe more accurate techniques use some sort of statistical, Markov chaining approach instead of trilateration.

      Anyway. Aruba Networks will sell you a system to do exactly what you propose (named VisualRF) (it even supports multiple vendors' equipment). It keeps location histories as well.

      Delete

The comments section is pre-moderated; it will take some time for the comment to show up.

You might want to check out the FAQ first.