By Rob Knies, Managing Editor, Microsoft Research
John Krumm, a researcher for Microsoft Research, is one of four co-writers of Accuracy Characterization for Metropolitan-Scale Wi-Fi Localization, a research paper accepted for presentation during MobiSys 2005, the Third International Conference on Mobile Systems, Applications and Services, to be held June 6-8 in Seattle. In the days before the event, Krumm, whose co-writers included Yu-Chung Cheng, of the University of California, San Diego; and Yatin Chawathe and Anthony LaMarca, both of Intel Research, found time to answer a few questions about the research conducted by him and his colleagues.
Q: What was the purpose of this research?
Microsoft Research Podcast
Collaborators: Holoportation™ communication technology with Spencer Fowers and Kwame Darko
Spencer Fowers and Kwame Darko break down how the technology behind Holoportation and the telecommunication device being built around it brings patients and doctors together when being in the same room isn’t an easy option and discuss the potential impact of the work.
Krumm: This research builds on a technique that was invented at Microsoft Research by Victor Bahl, Venkata Padmanabhan and Anand Balachandran. The goal is to use Wi-Fi access points as location beacons to replace or augment a global-positioning system (GPS). GPS usually doesn’t work indoors and sometimes fails outdoors in urban canyons or under dense foliage. Also, regular people are much more likely to have a Wi-Fi device than they are to have a GPS. So if we can make Wi-Fi work as a location sensor, then we can enable all sorts of location-sensitive capabilities for lots of people, both indoors and outdoors.
Other researchers have taken this idea in different directions, including my co-authors at Intel Research in Seattle. Their goal is to make a Wi-Fi-based location system that works indoors and outdoors based on Wi-Fi access points found in the “wild,” as they put it. These are access points that have been set up by regular people with no intention of using them as location beacons. Because of the nature of Wi-Fi networking, it is easy for a mobile, wireless device to detect almost any access point, even without authenticating or accessing the network.
Once you’ve detected a few access points, the challenge we addressed in our paper is to find the best way to compute your location in terms of latitude and longitude. Because I’ve developed some algorithms of my own for this problem, Intel asked me to collaborate with them to develop a “bake-off” of the best-known algorithms of this type. We wanted to be the Consumer Reports of Wi-Fi location, with objective ratings of algorithms based on various criteria. Now that we’ve done this, we’re thinking of moving on to washers and driers, and then sports cars.
Q: What did you learn?
Krumm: We learned that we can estimate the location of a mobile Wi-Fi device to an accuracy of 13-40 meters, depending on the environment, using just the access points that are already deployed in urban and residential neighborhoods. We learned about how various factors affect the accuracy with which we can measure location with Wi-Fi triangulation, which gives us a better idea of what accuracy to expect. We also learned about which algorithms work best for doing this type of location estimation.
Q: Did you encounter any surprises?
Krumm: We found that measuring the signal strength of Wi-Fi access points really doesn’t help that much in estimating position. This was a surprise, because that’s how nearly all previous researchers and commercial systems have been doing this sort of thing. Other measures of signal quality work better.
Another surprise was how difficult it is to do “war driving,” the process of driving around in a car with a GPS and a laptop, recording the locations of Wi-Fi access points. Even with two of us in the car, driving around the University of Washington, attending to our equipment was a lot more distracting than talking on a cell phone. We had a few close calls in traffic. Eventually, I moved to the back seat to work with our three laptops so the driver could just drive without distractions. This is the closest I’ve ever come to being killed while doing computer-science research.
Q: What sort of tradeoffs did you make?
Krumm: As you work on any research project, you soon see many issues that no one has ever before thought about exploring. As we got deeper into this research, we realized that there are many interesting questions that we just didn’t have time to look at. Eventually we just had to stop the research so we could write the paper. That’s one nice thing about conference deadlines.
Q: What is the payoff from your findings?
Krumm: We expect the idea of using existing Wi-Fi access points as location beacons to catch on in various software products. Based on what we learned, we can definitively say what sort of accuracies to expect and what algorithms work best. One of the pleasant conclusions from our study is that, for this task, a simple algorithm worked almost as well as a much more complicated one. So now, when I talk to Microsoft product groups about these ideas, I can say they really don’t need to invest a lot of time programming a sophisticated algorithm. And I can tell them that the whole idea of measuring location in this way really works.
Q: Can you provide a real-life scenario on how your findings could be applied?
Krumm: Some things you can do if you know your location:
- Locate yourself on a map.
- Get a list of nearby businesses and other points of interest, then get Web pages pertaining to these things.
- Get driving or walking directions from where you are now to your destination.
- Have your meeting reminders pop up with enough time for you to get to the meeting from where you are.
- Transmit your location to your friends so they know where you are.
- Get location-sensitive reminders, such as: “You wanted to pick up a birthday card, and there’s a greeting-card store coming up on your left.”
- Automatically annotate your digital photos with the location where they were taken. Kentaro Toyama of Microsoft Research led the WWMX team to browse and share photos annotated in this way.
- Automatically build a travelogue or diary describing a trip you made.
We’re working on some advanced scenarios, such as:
- Given your location, we want to infer what you’re doing. For instance, if you’re in a movie theater or a restaurant, we can say with fairly high confidence what your current activity is. Given this, we can adjust the behavior of your cellphone to let through only messages of a certain priority.
- If a system knows your locations over time, it can do a pretty good job of predicting where you’ll go next. If we know this, we can prefetch certain data that might be useful to you, such as traffic information and upcoming restaurants and gas stations.
Algorithms 
Hardware and devices 
Systems and networking