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 . 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.
Source on GitHub:
Mobile RSSI Recording Application “Trainer app”
Disclaimer: Much of the source is a mess. I wrote the RMA and the mobile UI plotting code.
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.
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.
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 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
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.
 http://dl.acm.org/citation.cfm?id=1451884  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