Tag: indoor location

Recent changes in hardware and standards make one-meter accuracy possible, in some cases as soon as this year. The transcript of a talk given to Android developers earlier this year, this article gives a short overview of location in smartphones, introduces Wi-Fi round-trip time technology and standards, and then explains the Wi-Fi application programming interfaces.

By Frank van Diggelen, Roy Want and Wei Wang, Android Location, Google

It’s a great time for location applications because technology hardware standards and Android application programming interfaces (APIs) are all evolving simultaneously to enable an improved location accuracy that has not previously been possible when using smartphones.

Eventually, this means high accuracy for everyone, but we want to take you under the hood of location because we want to give you the opportunity to get a head start on the future. We also want to highlight the need to protect and respect the user. The more people who use location, the more careful we and you have to be. We will highlight where you must get user permissions and we’ll close with some guidelines for making great location apps.

Where are we today with indoor location accuracy? If you’ve noticed that your phone seems to be more accurate when you’re inside shopping malls and office blocks than it was a few years ago, you’re not imagining it. With each release of the fused location provider, we have had steady improvement of the Android algorithms and machine learning for Wi-Fi locations.

There continues to be improvement, and you’ll see indoor accuracy of better than 10 meters, but round-trip time (RTT) is the technology that will take us to the one-meter level.

Meanwhile, what about GPS? In terms of GPS accuracy in the open sky, there has not been much change in the last few years. If you’re outside and can see the open sky, the GPS accuracy from your phone is about five meters, and that’s been constant for a while. But with raw GNSS measurements from the phones, this can now improve, and with changes in satellite and receiver hardware, the improvements can be dramatic.

Everyone’s familiar with the blue dot, but to get the blue dot you need a location provider, and to get location you need measurements — specifically, range measurements from Wi-Fi access points or from GPS satellites. We’ll show you how one-meter measurement accuracy can be made available in smartphones. The key technologies are Wi-Fi RTT, GPS dual-frequency and carrier phase measurements.

If you want to wait a year or two, this will find its way into the worldwide ecosystem and the Android fused location provider API, but we want to give you a chance for a one- to two-year lead by taking accurate measurements and turning them into accurate location. We want to work with you to accelerate development and bring the present closer to the future.

You might wonder, why do I need better location accuracy anyway? Let’s look at two instances where existing apps could use much better location accuracy.

For indoor routing or navigation of the kind that you’re used to in your cars, you need much better accuracy than you have outdoors: you need one-meter accuracy, because indoor features like cubes or aisles are only a few meters wide. Even for the most loved outdoor applications such as map directions and finding alternate routes in traffic, we could benefit from higher accuracy than we have now.

For example, when you came here this morning in a car, you probably had your arrival time estimated using the average speed of the traffic. What you really want is the traffic speed in the lane that you’re in, so that you could ask, how much faster would it be if I took the carpool lane instead? There are, of course, many other use cases and we’ll mention a few. But the important thing is that we are sure that you will have many more ideas than we have, and that’s the beauty of the open Android ecosystem.

Wi-Fi Round-Trip Time

Wi-Fi RTT ranging and indoor position estimation is based on making measurements of the time of flight of RF signals, and can be used to estimate your indoor position to an accuracy of one to two meters.

Before we get into the details of Wi-Fi RTT, we want to tell you how we currently calculate an indoor location. At this time, we use Wi-Fi received signal strength indication (RSSI). Basically, we can calculate distance as a function of signal strength. Figure 1, with the access point in the center, shows a heat map of the signal strength around a Wi-Fi access point (AP).

The green is the strongest signal, near the AP and the red is the weakest, measured toward the edges. I’ve placed two phones on this diagram at the transition between the weak and the strong. Notice that the phone on the right is further away from the access point than the phone on the left. The signal strength can therefore vary at the same distance, which unfortunately makes it very hard to make accurate range measurements based on this type of measurement. There are lots of algorithms and tricks that can be used to improve this, but the greatest improvement can be achieved using a new Wi-Fi technology.

That’s where Wi-Fi RTT comes into play. It uses time-of-flight instead of signal strength. It measures the time it takes to send a Wi-Fi RF packet from an access point to a phone and back again. Because radio signals travel at the same speed as visible light, if we multiply the total round-trip time of a Wi-Fi packet by the speed of light and divide by two, we get distance, and therefore the range from the phone to the access point. That’s the basic principle.

If you want to use several ranges to nearby access points to calculate your position, we have to use a process called multi-lateration. The key thing to think about here is that the more ranges you have, the more accurate the position you can estimate. If you can use at least four ranges, then we think you can achieve a location accuracy of about one to two meters in most buildings.

Why are we telling you about Wi-Fi RTT today? Why not last year or before? Because 2018 is the year of Wi-Fi RTT in Android. We are releasing a public API in Android P based on the IEEE 802.11mc ranging protocol. Furthermore, we’re also integrating aspects of this protocol into the fused location provider, which is the main location API that developers use to put a blue dot on a map. So, in the near future, any time there are RTT access points in the vicinity of a phone, the estimated position accuracy will be greater.

History. The 802.11 standard was ratified in December 2016, and in early 2017 the Wi-Fi Alliance started an interop program for silicon vendors to make sure the chips followed the protocol. That’s when we started doing a lot of work to validate its operation and understand how it could be integrated into Android. By the fall of this year, we will release the public API so that you can all have access to this capability and can build your own applications around the technology.

Principles of Wi-Fi RTT Operation

The ranging process starts with a standard Wi-Fi scan. The phone discovers the access points that are nearby, and, based on certain bits in information elements (IEs) contained in the Wi-Fi beacons and the probe responses, we can figure out which of those access points are RTT-capable, and the phone can choose one of them to range to. It starts by making a request to the access point; as a result, the access point will start a ping-pong protocol in response. The ping sent to the phone is called a fine timing measurement (FTM) packet, and the pong sent back to the access point is an acknowledgment of that packet.

The arrival and departure time stamps are recorded at each end of the transaction, but for the phone to calculate the total round-trip time, it needs to have all four of those times. So the access point sends one more packet to the phone, and this third message contains the missing times. The phone then simply calculates the round-trip time by subtracting the time stamps from the AP, and subtracting its own packet turnaround timestamps. The difference between these times leaves just the packet time-of-flight. We multiply this by the speed of light to get distance, and divide by two to get the range that we are trying to measure.

Now, it turns out if you execute this process multiple times, you will in fact get more accuracy, and so that’s what the protocol allows for, enabling a burst of FTM packets. We’re typically doing a burst of about eight of these of these transactions and, as a consequence, the system can calculate ranging statistics, such as the mean and the variance. This allows us to more accurately plot a position on a map, and knowing the accuracy also allows us to more easily calculate a trajectory.

Now that you have ranges, how do you get a position? One way, similar to GPS positioning, is you take four ranges to four separate access points; if those ranges were accurate, they would define four circles that would intersect at a single point. In practice, because of error in each range, a maximum likelihood position is calculated using a least squares multilateration algorithm.

You can then further refine this position by repeating the process, particularly as the phone moves, and then calculate trajectory using filtering techniques, such as Kalman filtering, to optimize the estimate.

Like any new technology, there are challenges, and we’ve experienced some of these early on. What we find is that sometimes there is a constant range calibration offset that may be as much as half a meter. Sometimes you also see multipath effects where a packet on the non-line-of-sight path from the access point to the phone is received rather than on the line-of-sight path, making the range appear longer. That problem can be solved by the vendor using something called antenna diversity, but all of these issues are related to algorithms, which the vendors are improving.

Basically, we need to go through a sort of teething process to get rid of these bugs, and Google can help in this process by providing reference platforms and reference applications. Vendors can then calibrate their own platforms before you guys even get to use them, which will be the ideal situation.

We’ve assumed that as early adopters you want to start using this API, but as we move into the relatively near future, we expect you to just use the Fused Location Provider because we’re going to be integrating the RTT capability into it. At the moment, the Fused Location Provider uses GPS (when it’s available), cell-tower signal strength and Wi-Fi RSSI, and fuses all this with the onboard sensors: inertial navigation from the accelerometer, gyro and compass. Now we’re adding Wi-Fi RTT into that mix, and it will increase the accuracy of the Fused Location Provider whenever RTT-capable access points are available nearby.

One other thing to remember is that if you are calculating the Wi-Fi RTT position yourself, you also had to know the position of the access points. In the Fused Location Provider, we will calculate those positions for you automatically: we’ll crowd-source those positions so you won’t have to worry about that, and it will make life a lot easier for you to write applications.

RTT APIs

Let’s walk you through the RTT APIs in P to see how you can add RTT in your own application. As we mentioned, RTT measures the round-trip time between two Wi-Fi devices so both your mobile phone and your access points need to support the 802.11mc protocol. As you saw, RTT can give you very fine location estimates down to one-meter accuracy, so your application needs to declare the ACCESS_FINE_LOCATION permission. Of course, both location and Wi-Fi scanning need to be enabled on the mobile device.

How do you know whether your mobile phone supports RTT? In P, we added a new system feature called FEATURE_WIFI_RTT so you can simply check whether this returns true on your mobile device. Our pixel phones running P DP2, and above, will support RTT. How do you know whether your access points support RTT? As usual, you will need to do a Wi-Fi scan and get a list of Wi-Fi scan results. Then iterate through the scan results and check for each scan result whether the method is80211mcRepsonder() returns true. This will tell you whether the access points support RTT.

After you get a list of RTT-enabled APs, simply add them to the ScanRequest Builder to build a scan request. RTT is carried out by the WiFiRTTManager, which you can get access to by getting the system service WIFI_RTT_RANGING_SERVICE. Now we’re ready to start RTT ranging by sending the RTT request to the RTTManager with a ranging result callback. Usually RTT takes only a few hundreds of milliseconds, and when it finishes, you will get a list of information including the status — an RTT may fail, the MAC address — which AP you have just ranged, and most importantly, the distance between the mobile phone and the access point.

Here is the list of information you can get from RTT ranging results: the distance, the distance standard deviation, which is the standard deviation from multiple ranges in multiple FTMs, and the number of attempted FTM measurements and number of successful measurements. The ratio of successful measurements over attempted measurements will give you an idea of how good the Wi-Fi environment is for RTT ranging.

We mentioned all Pixel devices support RTT. How about access points? We are beginning to see access points supporting the 11mc protocol in production. We are also very excited to let you know Google Wi-Fi will soon support the 11mc protocol. By the end of this year, off-the-shelf Google Wi-Fi will have RTT enabled by default. Worldwide, we’re also beginning to see the deployment of RTT APs. South Korea is actually leading the deployment of RTT APs.
Of course, this is just the beginning of the long journey. We’re very eager to see a larger penetration rate of RTT APs in the coming years.

GPS and the Great Outdoors

Carrier-phase precision has been in commercial GPS receivers since the 1980s. What is new is the availability of these carrier-phase measurements from phones and dual-frequency measurements in phones. Right now, all of your smart phones, all smart phones everywhere, have GPS or GNSS on one frequency band only. It’s known as L1. But there’s a new frequency in town called L5, and it’s supported by all these GNSS systems: GPS, Galileo, BeiDou QZSS and IRNSS. The availability of a second frequency means that you get much faster convergence to carrier-phase accuracy.

What about hardware? In the last few months, several companies that produce consumer GPS chips have announced the availability of dual-frequency L1/L5 GPS chips both for the automobile market and for the phone market. These chips are now being designed into cars and phones.

Let’s talk about the measurements themselves and the APIs. The phone must support the GNSS measurements API. Your app is going to need the ACCESS_FINE_LOCATION permission, and location needs to be on.

How do you know if a particular phone supports these measurements? At a high level, you can just go to a website that we maintain, g.co/GNSSTools, as part of the Android developer site. A table there lists phones that support the GNSS measurements and also which characteristics they support. It’ll tell you which phones support the measurements and which of those support the carrier-phase measurements.

Programmatically, you do this as follows: You call the method onStatusChanged and it will return an integer that tells you the capability of the phone, either if the phone just does not support the measurements at all or if it supports it but location is off, or if it supports it and location is on; in that case, you’re good to go.

Let’s get into some details of the APIs. The most relevant methods for what we’re talking about here are the following three:

• getConstellationType() tells you which of the different GNSS constellations a particular satellite belongs to.
• getCarrierFrequencyHz() tells you whether you’re on the L1 or the L5 band for a particular signal.

Most importantly,

• getAccumulatedDeltaRangeMeters() tells how far along that carrier wave the receiver has tracked you since it began tracking the signal.

There’s something else that we need to explain, which is duty cycling. Right now when you’re navigating with your phone and you see the blue dot moving along, you might think that the GPS is on continuously. It’s actually not. What’s happening in the phone is that GPS will, by default, be on for a fraction of a second and then off for the remaining fraction of a second, and then repeat. This is to save battery. You perceive that the GPS is on all the time because the blue dot will move along continually, but actually it’s duty cycling internally.

For this carrier-phase processing, you have to continually track the carrier wave because the carrier wave is like a finely graduated ruler or tape measure with no numbers on it. So if the GPS was on and your receiver measured your phase and you get the data from the reference station, you’d start processing. If the GPS then goes off for a fraction of a second, you’ve lost where you were. It’ll start again, you’ll reacquire, you’ll be at a different phase on the reacquisition, you’ll start again — well, you’ll never solve the problem. You need the tape measure to stay out and you need to process, and to do that you need to disable duty cycling. You can do that in Android P with a developer option.

Details of the API. Figures 5 and 6 are screenshots of an application that we’ve put out called GNSS Logger. This enables you to log the raw measurements in the phone. The nice thing about this app is it’s a reference app: the code is open source and available to you on Github, so when you build your app, please make use of our code.

When you build an app that needs raw measurement, you will need the Android location manager API with the method registerGnssMeasurementsCallback. This method requires you to pass it a GnssMeasurementsEvent callback shown here. You construct this callback, and then override the method onStatusChanged, and that will give you the integer status that we discussed to tell you if measurements are supported.

If they are, you then override the method onGnssMeasurements Received, and this allows you to receive a GnssMeasurementEvent every epoch, for example, every second. This event gives you the values we’ve been talking about: constellation type, carrier frequency and accumulated Delta range. For duty cycling, that’s a developer option, so you access that through the developer page on your phone as you see there on P. This allows you to disable the duty cycling.

Keep in mind this introduces a trade-off between getting the continuous measurements and battery life. There will be an impact on battery life. How much? Well even when GPS is on continually, it will use less than 20% of the power that screen-on uses, so that gives you a feel for the magnitude. This is a developer option precisely because it’s a trade-off involving battery life, and we’re very concerned about maximizing battery life, but if you and our team together can prove that there’s value in this option and people want it, then it will be upgraded to a fully supported API in the future.

Figure 7 shows the basic architecture that we expect if you implement an app for high accuracy. On the bottom of the block diagram on the left you’ve got the GPS/GNSS chip. The GNSS measurements come up through the APIs we’ve just described, and then your app lives at the top in the application layer. You’re going to need access to a reference network to get the data that the reference stations are tracking. There are publicly available reference networks. I’ve listed one at the bottom: the International GNSS Service. You can get data from them free.

Then you need to process that data in some kind of position library, and that does all the carrier-phase processing, and that too is available as open-source code. RTKLib.com has an open-source package for precise positioning. Then you’re good to go.

We mentioned that dual frequency gives you much faster convergence to the high accuracy, but you don’t have to wait until the dual-frequency phones come out. You can start doing this with single-frequency phones. Here’s an example of someone who’s already done that. This is an app created by the French Space Agency, and they’re doing exactly what we show on the block diagram on the left and they’re achieving sub-meter accuracy after a few minutes of convergence.

Here’s some more external analysis that’s been done in a similar way. This is from a paper called “Positioning with Android GNSS.” This is using one of those chips that we showed you, the chip that goes in cell phones that does dual frequency. What’s been shown here is the cumulative results over many different starts of the GPS and what you see is that most of the time the accuracy is better than a meter. You see that on the vertical axis, which is 0 to 1 meters, the accuracy gets to better than a meter in less than one minute and then continues to converge as long as the phone continues to track that carrier phase continuously.

Here’s a another similar but different paper. This is using one of the chips that’s meant for cars. This was tested in a car driving around that track there, and what the plot here shows is the accuracy after the initial convergence while the car was driving. You see with GNSS alone the accuracy is 1 to 2 meters, and with this carrier-phase processing it’s at a couple of decimeters.

For you to build this, what are you going to need? Of course you need the device location to be enabled and your app has to have location permissions, so that’s going to come from the user. You need the basic GNSS measurements, that’s been available since Android N. You also need this continuous carrier phase I’ve been talking about and that’s available in P with the developer option. It would be nice to have dual frequency for fast convergence and that’s coming soon. You need a reference network such as the one we already mentioned; there are also commercial reference networks out there and commercially available software to do the same thing, but we recommend you start with the free stuff and go from there.

Finally there’s the app from you.

In summary, everything we’ve been showing you here is based on indoor and outdoor technology that’s been evolving kind of in parallel. In each case we have a new technology and Android P gives you a way to access it.

Indoors Again

The new technology is Wi-Fi RTT and round-trip time-enabled access points. We give you a public API to access these measurements, but you need access point infrastructure. This is where some of you can move ahead this year, because if you have a customer who owns or controls a venue, they can upgrade their access points — sometimes just a firmware upgrade — and then you have the infrastructure. Android P comes out later this year, and you can implement something and have indoor navigation, or create any other type of context-aware app.

For example, someone goes in a store: where’s the milk? You can make the world a better place for all of us by saving us from the tyranny of having to ask directions from strangers. And if you’re not one of those people who has access to this now, in a few years the infrastructure will naturally evolve as access points upgrade to RTT, and one-meter location will be automatically available from the Fused Location Provider.

Now Outdoors

For this carrier-phase process, it’s not just outdoors, but outdoors with open sky. What do you need? Dual frequency and continuous carrier phase. We give you the API and the developer option to make use of that. You will need reference-station access as we mentioned, and then applications.

What can you do outdoors with open sky? We already mentioned the traffic example. There are many others that readily come to mind where existing GPS accuracy doesn’t cut it. For example geocaching, where people look for treasures; it would be nice to have one-meter accuracy. Precision sports monitoring. Imagine a snowboarder who wants to measure her tracks very precisely after the fact. Five-meter location is not good enough. One meter would be great.

Speaking of sports, there are more and more drone apps where you have a kind of “follow me” capability, and the drone will fly along and video you. Well it would be nice if it videos you and not the person next to you. And so on. There are hundreds of apps, and you’re probably thinking of some right now, and that’s the whole point.

We want you to write those apps, and together we’ll bend the arc of technology history closer to the present. I’m really looking forward to next year to see you back here and see what you’ve created.

Finally, we want to leave you with a couple of pointers. When you build location apps, please build great location apps. You must have user trust. Please provide the user with transparency and control. You’re going to have to ask for location permissions for this. Explain to them what you’re doing, how it benefits them. When things go wrong, make your app recover gracefully. If these measurements are unavailable for some moment or something goes wrong, you can fall back to the Fused Location Provider location.

Think about that and, finally, respect the battery life trade-offs that we’ve discussed.

---

FRANK VAN DIGGELEN is a principal engineer in the Android location team, leading high-accuracy location including Wi-Fi and GPS. He holds more than 90 U.S. patents on GPS, and is the author of A-GPS, a textbook on Assisted-GPS. He has a Ph.D. from Cambridge University and teaches a GPS class at Stanford.

ROY WANT received his doctorate in computer science from Cambridge University and is a research scientist at Google. His interests include mobile and ubiquitous computing. He is an IEEE Fellow and secretary for IEEE Task Group 802.11az (Next-Generation Positioning). To date, he holds 100+ issued patents in this area.

WEI WANG s a software engineer in the Android location and context team. He works on the Fused Location Provider API. His main focus is reducing battery consumption of location, as well increasing location accuracy. He received a master’s degree in information security from Carnegie Mellon University and a master’s degree from Southeast University in China.

Featured image: Frank van Diggelen, Roy Want and Wei Wang