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.
This article was written by Isabelle Krämer at the Institute of Geodesy and Navigation at the Federal Armed Forces University in Munich, Germany. The article was edited by Prof. Günter Hein.
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:
- The user does not have to pay additional fees for any data transmission or new devices.
- The need for a centralized infrastructure network can be avoided in favor of small local ad-hoc networks.
Bluetooth Ad Hoc Network
A wireless ad hoc network establishes connections between various devices without relying on external hardwired infrastructures. In general, an ad hoc network only lasts for a short time during which one device can transmit data to another and vice versa. The IEEE 802.15.1 communications technology better known as Bluetooth is an industrial standard that provides the specifications to establish such connections.
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
The principle of dead reckoning using step detection is very easy to explain. One starts with a more or less precise knowledge of a position and calculates for each step the new position based on new measurements.
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.
. . .
Simulation Model
As mentioned before, the main intention of our approach is to enable users to navigate in an indoor area independent of A-GNSS or any pre-installed infrastructure. The users’ positions are estimated by dead reckoning, which implies that each user has a rough idea of its position when starting the simulation, which we developed on a PC with the help of a high-level language and interactive environment software package.
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.
. . .
Simulation Results
To evaluate the peer-to-peer model we measured the distance between the true position and the estimated position plus the known error of each walker and averaged these for each simulation step. At the end of the simulation this value is also averaged for all walkers in order to generate a single value that can be compared.
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.
. . .
Conclusions
The results of the simulations presented in this article indicate that our approach has its advantages in case a GNSS signal is available only intermittently or unavailable for an extended period of time. This peer-to-peer model works best in areas of great size and when the possibility of using GNSS is limited to a few spots. But it is important that enough users participate.
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.
Acknowledgments
I want to thank Professor Eisfeller and my colleagues at the Institute of Geodesy and Navigation, especially José-Angel Ávila-Rodríguez, Felix Kneissl, Herbert Niedermeier, and Stefan Wallner. A special thank you goes to my former colleague Thomas Pany who — at least at the beginning — knew better than me how to implement such a service.
References
[1] F. van Diggelen: A-GPS Assisted GPS, GNSS, and SBAS, Artech House, 2009
[2] IEEE Std 802.15.1: Part15.1: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Wireless Personal Area Networks (WPANs), 2002
[3] J. Schiller, Mobilkommunikation, Addison-Wesley, 2003, 2nd edition
[4] S. Feldmann, K. Kyamakya, A. Zapater, Z. Lue: An indoor Bluetooth-based positioning system: concept, Implementation and experimental evaluation, Technical Report, University of Hannover, 2003
[5] K.Thapa, S.Case: An Indoor Positioning Service for Bluetooth Ad Hoc Networks, MICS 2003, Duluthm, MN, USA
[6] E. Pulido, R. Quiros, H. Kaufmann: Analysis of a Kalman Approach for a Pedestrian Positioning System in Indoor Environments, In Proceedings of the European Conference on Parallel and Distributed Computing, 2007
[7] G. Lachapelle: GNSS Indoor Location Technologies, Journal of Global Positioning Systems Vol. 3, 2004
[8] P. Maybeck: Stochastic Models, Estimation, and Control, Vol.1 Chapter 1, Academic Press Inc, 1982
[9] G. Welch, G. Bishop: An Introduction to the Kalman Filter, SIGGRAPH Course, 2001
[10] Ch. K. Chui, G. Chen: Kalman Filtering with Real-Time Applications, Springer Verlag Berlin, 1987
[11] J.A. Avila-Rodriguez, S. Wallner, G.W. Hein, B. Eissfeller, M. Irsigler, J.L. Issler: A Vision on New Frequencies, Signals and Concepts for Future GNSS Systems, Proceedings of ION-GNSS 2007, September 2007, Fort Worth, TX, USA
[12] O. Mezentsev: Sensor Aiding of HSGPS Pedestrian Navigation, UCGE Reports, March 2005, Calgary Canada
[13] J. W. Kim, H. J. Jang, D. Hwang, Ch. Park: A Step, Stride, and Heading Determination for the Pedestrian Navigation System, Journal of Global Positioning Systems, 2004
[14] S. Lee, K. Mase, K. Kogure: Detection of Spatio-Temporal Gait Parameters by Using Wearable Motion Sensors, Proceedings of the 2005 IEEE, Engineering in Medicine and Biology 27th Annual Conference, September 2005, Shanghai, China
[15] H. Niedermeier, G. Ameres, Th. Pany, B. Eissfeller, J. Winkel, G. Lopez-Risueno: Reproduction of User Motion and GNSS Signal Phase Signatures Using MEMS INS and a Pedestrian Navigation System for HS-GNSS Applications, Proceedings of the ESA NAVITEC 2008 Conference, December, 2008, Noordwijk, Netherlands
