Real Time Indoor Tracking for Android Phones

For my senior design project I built a system with a few friends to track Android phones indoors using Wi-Fi signal strength. The technique we used is called Wi-Fi fingerprinting and has been detailed in a few academic papers [1][2]. A funded startup called Wi-Fi Slam is attempting to commercialize the same concept.

Update 3/23/2013: WifiSLAM has been bought by Apple for $20 million. There’s a lesson here somewhere.

The Product

The Android app looks like this: The web app allows you to track many phones. It looks like this:

Source on GitHub:

Remote Monitoring Application

Mobile Tracking Application

Mobile RSSI Recording Application “Trainer app”

Disclaimer: Much of the source is a mess. I wrote the RMA and the mobile UI plotting code.

Background

The project is driven by the fact that GPS performs poorly indoors– the receiver chips just can’t receive reliable signals through roofs. We decided to get around this with Wi-Fi. The original specs called for a personal inertial device built on Texas Instruments hardware. However, we weren’t too keen on designing an original embedded system and the math required to coordinate a gyroscope, accelerometers and e-compass was unpalatable. Our solution is to construct a table of Wi-Fi signal strengths. At many points inside the building, we recorded X-Y coordinates and the RSSI values from each available access point. We could then perform a lookup in this table to find the nearest point and tell the user that he was at that location.

Overview

The design consists of two subsystems. The first is an application on an Android phone, and the second is the Remote Monitoring Application that runs on a web server. The smartphone application sends real-time position information to the RMA. The system overview below enumerates the inputs and outputs of each subsystem and the interaction between them. The mobile application reads Wi-Fi RSSI values and turns them into positional data. The RMA receives these coordinates and plots them on a map in the user’s browser.

Android Application

The mobile application is an Android binary that users run on their smartphones. It tracks the mobile phone’s changing position using Wi-Fi fingerprinting. Fingerprinting allows the application to compare current RSSI values from nearby Wi-Fi access points to previously gathered values in a table stored on the mobile device. The stored values correspond to a physical location, thereby providing an accurate position reading. The application constantly displays its computed position on a map and relays that position to the RMA over an available Internet link (Wi-Fi). The position lookup itself is O(n * m) where n is the number of rows in the table and m is the number of access points sensed. Two nested loops compute the dot product[3] between the current RSSI values and those in the table. The point with the minimum difference is considered to be the closest point and sent to the RMA. The interesting code is in Map.java in the PointWithRSSI method.

Remote Monitoring Application

The RMA is a node.js web application built on the Express framework. Coordinates are received by the server as JSON-encoded post requests and pushed to the user’s web browser in real time using the socket.io library. The client-side JavaScript component plots these coordinates on an OpenLayers map. It supports an arbitrary number of phones as long as they report a unique device_id. The mobile app code uses the Android ID for this. The server-side code also stores the data received in MongoDB for future use. The original project requirements called for heat maps, but they were not completed. My implementation is hard-coded to the ENS building, but if you want to adapt our code, you’ll find that OpenLayers is pretty easy to work with. It wouldn’t be a stretch to swap out the image. Pay close attention to the bounds in map.js. They define the coordinate system used for plotting. The RMA also includes functionality to help train the mobile app. Clicking at any point on the map displays the XY coordinates of that spot. We entered these values into the trainer app when recording RSSIs.

Aftermath

Long story short, we had everything working for the open house. The accuracy was spotty– about 6 meters. It seemed to perform better in the hallway where the access points were installed rather than the rooms. Accuracy may have been improved by recording more points. In the end, it was enough to convince the professors. We ended up winning second place and taking home a modest cash prize. I wore that obnoxious shirt to troll Merwan for requesting business casual attire. It went okay.

This project was more of a lesson in project management than anything technical. We had another team member not pictured above because he just didn’t show up to anything. Not even the open house. Early on we made sure his work would be limited to the wholly independent heat map component. Sure enough, it never got completed.

References

[1] http://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?article=1007&context=cpesp

[2] http://dl.acm.org/citation.cfm?id=1451884 [3] The operation done for each BSSID column in the table is: difference += (stored RSSI) ^2 – (stored RSSI * current RSSI).  After the outer loop iterates through each row, the minimum difference tells you which row has the XY coordinates you need. This makes sense, but I’m not convinced it’s actually a dot product. Parts of this post were taken from a Testing and Evaluation plan coauthored by Rohan Singhal, Tim Osborne, and Merwan Hade, and myself.

Update: 11/29/2012: Today Google announced a very similar product: http://googleblog.blogspot.com/2011/11/new-frontier-for-google-maps-mapping.html

Update: 3/8/2018: The forthcoming Android P will support indoor positioning by providing explicit round-trip-times to access points. https://android-developers.googleblog.com/2018/03/previewing-android-p.html?m=1