Project topics and materials
Get Complete Project Material File(s) Now! »
Evolution of wireless localization systems
The need for location information goes back to a long time ago. At rst, when human beings started to explore new territories, the issue was to locate either themselves or their destination, and be able to come back home. These tasks were solved using terrestrial marks. Then, with the development of maritime transportation, needs for other solutions arose be-cause of the absence of marks at sea. The rst sea navigations followed the shore where terrestrial marks are available. Then, with the development of astronomical tools, navigators were able to compute their latitude at night by observing the locations of navigational stars. But unfortunately, the astronomical observation was not able to solve the longitude. The compass discovery allowed the development of dead reckoning technique, which is the process of estimating the present location from the past location, speed and direction of displace-ment, but this method lacks precision due to errors accumulation and was far from the nal answer for sea navigation. The longitude problem was solved with the invention of the marine chronometer in the late eighteenth century, where the longitude was computed by relating the locations of the stars to the time.
Era of wireless communications
The development of radio transmission systems at the beginning of the 20th century paved the way for a new era regarding location systems. With the improvement of the accuracy of local time generators (oscillators and atomic clocks), it becomes possible to use the radio signals as new localization marks. Since the middle of the 20th century several terrestrial location systems have been developed and commercially deployed, including Decca, Loran and Omega systems [6]. These systems rely on an infrastructure of synchronized stations, and the localization method is based on measuring the time di erence between pairs of signals from several stations. A given constant time di erence can be represented by a hyperbolic line of positions, and the intersection of two lines is the location of the receiver. The hyperbolic method is described in Section 2.4.
The Decca system uses low-frequencies (30-300kHz) and is able to deliver accuracies within 50 meters (m) with a range of around 400km. The Loran system also uses low frequencies (90-110kHz) with a range of up to 1900km and absolute error between 185 and 463m. In fact, there is a trade o between range and accuracy. Microwave systems can o er a higher accuracy (in the order of few meters) but with a very limited range, while low frequency systems o er a much reduced accuracy (50m) but with a higher range. The Omega system o ers a worldwide coverage and operates at very-low-frequency (10.2-13.6kHz) but the accuracy is of the order 1-3km. This system was designed principally for maritime and aeronautical users.
Global navigation satellite systems
In a global navigation satellite system (GNSS), signals transmitted by satellites of known locations are used as localization marks [7, 6]. The use of satellites for positioning resulted in real improvements in terms of availability, coverage and accuracy.
The rst satellite navigation system was launched in 1958 under the name of TRANSIT project. This system became operational for the U.S. Navy in 1964. The obtained accuracy was in the range of 200-500m. Then in 1973, the NAVSTAR-GPS project was launched by the U.S. Direction of Defense (DoD) to overcome the limitations of the previous system. The rst four GPS satellites were launched in 1978 and the 24th was launched in 1994. Initially, the highest quality of service was reserved for military use, and the signal available for civilian use was intentionally degraded (selective availability). The selective availability was turned o in year 2000 improving the precision of civilian GPS from 100m to 20m. The GPS system consists of three segments :
{ Space segment consisting of a constellation of orbiting satellites at an altitude of approximately 20 000km.
{ Control segment consisting of several ground stations and antennas for monitoring the system and keeping it operational, synchronizing the atomic clocks on board satel-lites and controlling the orbital con guration.
{ User segment consisting of the user receiver equipment capable of receiving and processing the GPS signals. The receiver determines the transit time of messages sent by synchronized satellites and computes the distance to each satellite. The distances along with the satellites locations are used to compute the receiver location. A possible computation method is trilateration which is explained in Section 2.4. The receiver is not synchronized with the satellites, and thus, it needs at least four satellites for solving both location and time.
Over the last decades, several improvements to the GPS have been implemented, and the di erent segments of the system are continuously improved to increase its performance and its accuracy. Several satellites were launched to update the constellation and replace out of order satellites, and more launches are scheduled in the upcoming years. The evolution in the eld of integrated circuits and electronics allowed the construction of GPS receiver chips of small size and low power consumption, and which are nowadays implemented in di erent kinds of digital equipments such as mobile phones, digital cameras and computers.
Other GNSSs have been equally developed or are under development :
{ The GLONASS system was launched by the Soviet Union in 1978 and became fully operational in 1995 with a 24 satellites constellation. Because of the short life time of the satellites and the limited nancial budgets, the constellation declined, and only seven satellites were operational in 2002. Then a renewal program was launched and in 2011 the constellation was fully restored.
{ The Compass system is a Chinese GNSS which became operational in China in 2011 and the global system should be nished by 2020.
{ The Galileo system is currently built by the European Union (EU) and European Space Agency (ESA) and aims at providing a high precision positioning system upon which European nations can rely. The initial service of this system is expected around 2014 and completion by 2019. The new major upgrade service of Galileo compared to GPS and GLONASS is the Search and Rescue (SAR) function [8]. To implement this function, the satellites should be equipped with transponders for transferring the distress signals from the user’s transmitter to the Rescue Coordination Center, which will then initiate the rescue operation. At the same time, the system will provide a signal to the users, informing them that their situation has been detected and that help is under way.
GNSS augmentation
This technique aims at improving the accuracy, integrity and availability of GNSS services. It is called augmentation since it integrates external information in the positioning process.
There are three kinds of external information :
{ Information for compensating the errors that are due to clock drift, ephemeris or io-nospheric delay.
{ Information consisting of additional ranging measurements for improving the coverage in the case of reduced visibility of the GNSS satellites.
{ Information for improving the startup performance and reducing the time-to- rst- x.
(TTFF). The TTFF is the time required for a GPS receiver to acquire satellite signals and navigation data.
External information can be delivered either by a satellite-based augmentation system (SBAS) in which messages are broadcast by additional satellites [9], or by a ground-based augmenta-tion system (GBAS) in which messages are broadcast by terrestrial wireless networks [10]. An example of a GBAS is the assisted GPS (AGPS). This system uses data acquired by a wireless network such as the cellular network for reducing the TTFF and improving the startup. The AGPS is currently used in many GPS-capable cellular phones or mobile stations (MS) (see Figure 2.1) . There are two categories of AGPS [11] :
{ MS-assisted in which unprocessed GPS data is sent to the network server.
{ MS-based in which the almanac and GPS ephemeris are sent to the handset.
The GNSS localization service may become unavailable or highly inaccurate in harsh en-vironments where there are signal blockage or multipath propagation, such as urban canyons and indoor environments.
Localization in terrestrial broadcast networks
This technique allows one to take bene t from the already existing infrastructures of FM and TV broadcast systems. The team at Rosum Corporation developed a series of techniques to take advantage of digital broadcast television signals to localize mobile users and devices in urban and indoor areas [12]. This solution has several advantages over the GPS :
{ The TV signals have higher power levels than satellite signals (about 40 decibels (dB) indoor power advantage).
{ The TV signals are spread over a wide range of frequency bands allowing higher tem-poral precision and additional strength against multipath.
{ Moreover, the locations of TV towers are well known, and do not cause any Doppler frequency shift as in the case of moving GPS satellites.
The main disadvantages of this solution are the lack of precision of the implemented clocks which are not intended to be used for localization and the insu ciency in the number of detected broadcast towers especially in rural areas. But since GPS provides a good accuracy in rural areas where GNSS satellites are in LoS, this solution can be used as a complementary to GPS. The system proposed by Rosum is based on the use of synchronization codes included in the broadcast signals for estimating the time-of-arrival which are converted into pseudo-ranges [12]. Rosum is manufacturing TV+GPS hybrid positioning modules for enabling a reliable localization [13]. An indoor accuracy of 30-50m is claimed.
Table of contents :
Abstract
Acknowledgements
Contents
List of Figures
List of Tables
Acronyms
Notations
1 Introduction
1.1 Outline of the thesis
2 Wireless Localization Systems and Applications
2.1 Introduction
2.2 Evolution of wireless localization systems
2.2.1 Era of wireless communications
2.2.2 Global navigation satellite systems
2.2.3 GNSS augmentation
2.2.4 Localization in terrestrial broadcast networks
2.2.5 Localization in cellular networks
2.2.6 Localization in wireless local area networks
2.2.7 Localization in wireless personal area networks
2.2.8 Localization of RFID tags
2.2.9 Pervasive localization systems
2.3 Applications
2.3.1 Navigation
2.3.2 Tracking
2.3.3 Emergency calls
2.3.4 Location-based services
2.3.5 Wireless sensor networks
2.3.6 Communications enhancement
2.4 Fundamental localization methods
2.4.1 Angle-of-arrival based method
2.4.2 Time-of-arrival based method
2.4.3 Time-dierence-of-arrival based method
2.4.4 Hybrid methods
2.4.5 Limits on localization accuracy
2.5 Ranging measurements and sources of errors
2.5.1 ToA ranging
2.5.2 RSS ranging
2.6 Fingerprinting method
2.7 Cooperative localization and tracking
2.8 Conclusion
3 Rigidity, Identiablity and Localizability in Cooperative Network Localization
3.1 Introduction
3.2 Graph rigidity theory
3.2.1 Denitions
3.2.2 Rigidity matrix
3.2.3 Generic frameworks
3.2.4 Generic rigidity testing
3.2.5 Generic global rigidity testing
3.2.6 Non-generic frameworks
3.2.7 Networks with known vertical elevations
3.2.8 Unique solvability
3.2.9 Distributed construction of rigid and globally rigid networks
3.3 Rigidity , FIM and identiability
3.3.1 Computation of the FIM
3.3.2 Correspondence between the rigidity and the FIM
3.3.3 Identiability theory
3.4 Localizability via semidenite programming
3.4.1 Denitions
3.4.2 SDP method and localizability test
3.4.3 Improving the unique solvability test
3.4.4 Examples
3.4.5 Correspondence between rigidity and localizability
3.5 Numerical results
3.5.1 SSDP vs. ISDP vs. global rigidity
3.5.2 SDP accuracy
3.5.3 Eect of number and placement of anchor nodes and range R
3.5.4 Eect of link shadowing correlation
3.6 Conclusion
4 Cooperative Localization Algorithms
4.1 Introduction
4.2 Overview of cooperative algorithms
4.2.1 Centralized vs. distributed
4.2.2 Range based vs. range free
4.2.3 Anchor based vs. anchor free
4.2.4 Probabilistic vs. non-probabilistic
4.3 WLS and probabilistic estimation
4.3.1 Denitions
4.3.2 Weighted least-squares
4.3.3 Probabilistic estimators
4.4 Inference in graphical models
4.4.1 Markov random elds
4.4.2 Marginalization
4.4.3 Sum-product and max-product algorithms
4.5 Nonparametric belief propagation
4.5.1 Monte-Carlo integration
4.5.2 Kernel-based message approximation
4.5.3 Kernel-based belief approximation
4.5.4 Application to localization
4.5.5 State estimation
4.6 Other message passing algorithms
4.7 Two-phases NBP and ip ambiguity mitigation
4.7.1 Dealing with ip ambiguity
4.7.2 Two-phases NBP solution
4.8 Numerical results
4.8.1 Example 1 : Distance measurements in additive Gaussian noise
4.8.2 Example 2 : Distance measurements in additive noise with outliers
4.8.3 Impact of the number of iterations
4.8.4 Impact of correlated shadowing on ip ambiguity mitigation
4.9 Conclusion
5 Position Tracking Based on RSS Measurements
5.1 Introduction
5.2 RSS measurements and shadowing modeling
5.2.1 Shadowing maps modeling
5.2.2 Auto-regressive shadowing model
5.3 Localization accuracy under known shadowing
5.4 Position tracking
5.4.1 Tracking under known shadowing
5.4.2 Joint position and shadowing tracking
5.5 Bayesian Map estimation
5.5.1 Atlas Update
5.5.2 Joint tracking and atlas update
5.5.3 Implementation using particle lters
5.5.4 Numerical results : Indoor tracking
5.5.5 Application to train tracking
5.6 Conclusion
6 Conclusions and Future Research
6.1 Conclusions
6.2 Future research
A Fisher Information Matrix in Cooperative Network Localization
A.1 Case of distance measurements with additive Gaussian noise
A.2 Case of RSS measurements with additive Gaussian noise
A.3 Case of distance measurements with additive noise distributed according to a mixture of Gaussian distributions
B Derivation of the Linear MMSE Estimator and Kalman Filter
B.1 Conditional distribution of multivariate Gaussian vectors
B.2 Linear minimum mean square error estimator
B.3 Sequential linear MMSE
B.4 Kalman lter
B.4.1 Prediction
B.4.2 Correction
C Proof of the Proposition of Section 5.4.2
D Resume en francais
D.1 Geolocalisation dans les systemes sans l : Techniques et applications
D.1.1 Introduction
D.1.2 Methodes fondamentales de localisation
D.1.3 Mesures de distances et sources d’erreurs
D.1.4 Localisation cooperative et poursuite
D.2 Rigidite, identiabilite et localisabilite en localisation cooperative
D.2.1 Introduction
D.2.2 Theorie de la rigidite graphique
D.2.3 La rigidite, la FIM et l’identiabilite
D.2.4 Localisabilite par programmation semi-denie
D.3 Algorithmes de localisation cooperative
D.3.1 Introduction
D.3.2 Denitions
D.3.3 Moindres carres ponderes
D.3.4 Estimation probabiliste
D.3.5 Algorithmes bases sur l’echange de messages
D.3.6 Algorithme de propagation de croyance (BP)
D.3.7 Propagation de croyance non-parametrique
D.3.8 Algorithme NBP a deux phases et compensation des ambigutes
D.3.9 Quelques resultats numeriques
D.4 Poursuite de position basee sur les mesures de RSS
D.4.1 Introduction
D.4.2 Modelisation des observations RSS
D.4.3 Precision de la localisation lorsque le masquage est connu
D.4.4 La poursuite de la position
D.4.5 Estimation bayesienne des cartes
Bibliography
