A-GNSS: A Different Approach
Working Papers explore the technical and scientific themes that underpin GNSS programs and applications. This regular column is coordinated by Prof. Dr.-Ing. Günter Hein. Contact Prof. Hein at Guenter.Hein@unibw-muenchen.de
More and more mobile devices are integrating GNSS technology — and this increases the pressure to improve positioning capabilities in difficult environments. In this column, the authors introduce a novel use of peer-to-peer transfer of position information that combines GNSS and dead-reckoning techniques with Bluetooth communications to assist positioning indoors.
When the GPS program was established, military services were undoubtedly targeted as its primary user group, focusing on outdoor operations and offering the capability of continuous tracking. In addition we have heard several times that GPS was planned as a dual-use system from its very beginning.
Given the nature of its design, however, GPS clearly was not primarily intended for use in urban canyons or indoors where its weak, line-of-sight signal often cannot reach. Nevertheless, the demand for portable devices with an integrated GPS chip continues to increase steadily and in consequence also the desire to navigate not only on highways by car but also in cities with tall buildings and especially within buildings.
According to one estimate, almost 30 percent of all mobile phones that will be sold between 2009 and 2011 have an integrated GPS chip. The increasing rate of mobiles sold with integrated GPS chips has created a distinct change in the use of civilian navigation — by markedly expanding its use pedestrians as well as motorists, indoors as well as on the highways.
Various methods have been developed to make navigation in environments with weak signal coverage possible. Unfortunately they either require an accurately surveyed area (e.g., WLAN “fingerprint”), additional equipment (e.g., gravitational sensors), or additional data transmission (assisted-GNSS or A-GNSS).
The latter principle — A-GNSS — is well known: by sending assistance data from a server via the radio network a device is able to perform a “hot start” and acquire a position fix within seconds rather than the lengthy time-to-fix-first usually required with a cold start under normal situations. Moreover, A-GNSS also helps in increasing the sensitivity of the receiver and in acquiring signals within buildings.
The improved results from A-GNSS are already substantial, but considerable research indicates that the performance within buildings is still not completely satisfying. Other drawbacks include the requirement for users to buy an A-GNSS-capable device and to pay for the data transmission. Moreover, when many such devices use A-GNSS service in one area at the same time, the server calculating and providing the aiding data might soon be overstrained.
Some approaches to indoor navigation do not rely on GNSS, but they often require an already well-surveyed area with infrastructure, for example, WLAN access points or RFID readers.
This column will introduce an approach that avoids these drawbacks and uses short-range peer-to-peer communication to enhance the estimation of a position. Portable devices calculate their position by dead reckoning when no satellite signals are available. To keep the approach simple only a compass and a step detector are used. When two of these devices can communicate their results, they can also try to improve their positions by using a Kalman filter.
Accordingly, the devices will use GNSS to calculate a position whenever possible (e.g., near doors, windows, or reference stations) and otherwise use dead reckoning to estimate their position based on stride length estimation and heading from a magnetometer.
When two or more devices come within reach (i.e., communications range) of each other, they compare their individually estimated positions and calculate a corrected one based on weighted average.
This article will first discuss Bluetooth, the communications technology of choice for this approach. Then we will briefly explain the operation of the Kalman filter for this application. Finally, we introduce our A-GNSS method accompanied by a simulation model and results of test simulations.
This new approach addresses two shortcomings of existing indoor navigation technologies:
Bluetooth Ad Hoc Network
The Bluetooth protocol stack is divided into the so-called core specification and the profile specification. The former describes the protocols of the physical layer and the data link layer while the latter specification contains several protocols and functions to fit Bluetooth to different applications.
. . .
Dead Reckoning and Kalman Filter
This approach assumes that the portable device has a measuring sensor such as a compass in combination with a step-detection unit. For simulation purposes, the length of one stride is always assumed to be of 0.7 meter, which can be considered to be a realistic value based on substantial investigation by numerous researchers.
. . .
To display the effects of the Kalman filter, the simulation must maintain two positions and the error variance of the position. One position is the true position, the other a position that is estimated by the user’s device based on the compass measurements and the assumption that the stride length is 0.7 meter.
. . .
Additionally, for each simulation one walker is randomly chosen to watch the behavior when encountering another walker, coming to a reference position or reaching the limits of the indoor area. Three parameters are varied for each simulation: number of walkers, size of the indoor area, correction with walkers and reference positions (correction_true), or only with reference positions (correction_false).
The simulation only allows a walker to correct its position when it comes within a range of two meters of a reference position. The two meters are an estimated value. We assume that a walker could only calculate a useful position by GNSS when it is no more than two meters away from a window or door area. The walker incorporates the first reference position at which the distance between itself and the reference point is smaller than two meters.
In real life, the walker’s device would estimate its position by dead reckoning until it realizes that a GNSS signal can be acquired. Then it corrects the estimated position with the position calculated using GNSS signals. In the simulation, we used two modes to point out that the accuracy of the position improves when the walker is allowed to correct its estimation with other walkers’ position estimation AND reference points (correction_true) instead of only correcting with reference points (correction_false).
The variation of the number of the walkers for each simulation follows the scale 100, 200, 300, and 500 (only for the indoor area of greater size). The size of the indoor area ranges from 100 x 200 meters to 400 x 600 meters. Every simulation instance is processed with the correction varying the involvement of other walkers.
So, each simulation (characterized by size of the indoor area and number of walkers) is done twice: The first time the walker is only allowed to correct its position with reference points the second time he is allowed to correct with reference points and other walkers.
. . .
Our first simulations confirm that, with fewer than 100 walkers, no real improvement occurs compared to the situation when the correction is only done at the reference points. In practical terms, this means that the more people there are using this kind of navigation aiding, the better the service will work.
The use of Bluetooth for this kind of approach also seems logical because no additional costs are incurred when transmitting data. The master/slave architecture makes it easy for one device to start a piconet and to query different slaves to find the one that fits best to correct the position.
This peer-to-peer approach requires no additional infrastructure. The piconets can be easily and quickly implemented and disappear just as quickly. And, as already mentioned, Bluetooth is a very common protocol with widespread availability on portable devices.
It does not matter what kind of devices communicate with each other, making such a service potentially available for every portable device. With SDP (Service Discovery Protocol) Bluetooth has also already implemented a protocol that makes it easy to discover new services on other devices.
Nonetheless, some practical issues do arise. GNSS positioning is anonymous, but this kind of A-GNSS approach by definition requires the sharing of position-related information with neighboring users. A Bluetooth device must be enabled to participate in this service at any time, and the estimated positions of two walkers must be exchanged to calculate a correction. This means that incoming connections have to be accepted no matter who requests them.
Bluetooth, however, has several security mechanisms available to protect the user from wiretapping of their transmitted data: encryption and a challenge-response algorithm to authenticate the devices mutually. Normally each user has to enter a PIN to establish a connection with another device when the devices do not know each other. Based on this PIN, a link key is calculated and used for the rest of the connection session.
This security mechanism is often eroded by the manufacturers, which may allow a PIN of only four figures or implement a static PIN. But even when users are able to enter the PIN manually and begin the authentication process, they have to trust the other user’s device when exchanging the PIN.
A better situation would be to have this process take place automatically when the user is not even aware of the data transmission between the devices to correct a position. Of course, the user has to authorize its device to take part in this kind of service. But the transmitted positions of other devices should not be known to him and should not be accessible in any of his mobile device’s other applications. In this way, the other devices remain anonymous to the user.
Some variations on our approach come to mind. As mentioned earlier, the users’ only additional device is a compass to measure their heading with a known accuracy and a step detector. The stride length is always thought to be 0.7 meters but surely varies depending on the walker. Adding a device that measures the stride length of each walker to a certain degree of precision would not be problematic. This would also make the position estimation more accurate when correcting only with reference positions.
Our original simulations had the walker correcting its position with the first walker that came within communication range. This often did not lead to the expected improvement in positioning accuracy. Indeed, this is the reason a walker now corrects its position with the one that is nearest. But we could also choose the walker with the smallest error variance or the walker with the minimum error. More simulations will be carried out to evaluate the decision rule that fits this approach best.
It might also be difficult to define which of the other walkers is the nearest. The only value that we can rely on for this is the RSSI, which as mentioned previously does not allow very precise conclusions about the distance between sender and receiver. An exchange of the error variance would provide an easier and more reliable approach.
In contrast to other approaches that use dead reckoning, Kalman filtering, or Bluetooth triangulation to acquire a position, this peer-to-peer approach needs neither many additional devices nor a previous surveying of the area. The algorithm is not too complex and doesn’t need much processing power — an important consideration particularly for smaller devices. By using Bluetooth as a transmission protocol the exchange of data is done in a local network without requiring or overloading an infrastructure network.
Applying Bluetooth operating in the 2.4 GHz portion of the S-band as a communication link to enhance navigation is also interesting from another point of view. As indicated in the article by J.A. Avila-Rodriguez et alia (Additional Resources), S-band could be used on a global basis for RDSS applications if approved by the International Telecommunications Union.
Indeed, both the Indian Regional Navigation Satellite System and China’s Compass/Beidou GNSS are already using or will eventually use S-Band for navigation purposes on a regional basis. Using Bluetooth communications to support and enhance navigation performance in indoor environments could provide a more seamless link between a potential S-band GNSS navigation service and the communication link. This might encourage users to implement such a service on their mobile device.
For the complete story, including figures, graphs, and images, please download the PDF of the article, above.
Copyright © 2013 Gibbons Media & Research LLC, all rights reserved.