A comparison of learning and deterministic range-free techniques for indoor geo-location

Get Complete Project Material File(s) Now! »

Indoor geo-location: diﬀerent measurements and tech-niques

According to measurement techniques utilized to determine the mobile terminals position, lo-cation positioning systems can be classified into two basic categories:
• Range-based techniques: This category contains geometric approaches that depend on the propagation time, as Time Of Arrival (TOA), Time Diﬀerence Of Arrival (TDOA), or Round Trip Time (RTT) and/or Angle Of Arrival (AOA), to calculate the distance between M Ts and the WLAN access points (APs), then the M T position is estimated by applying triangulation or trilateration method [Zhen 04].
• Range-free techniques: This category of positioning is based on K-nearest neighbor [Bahl 00b], probabilistic [Yous 05], and pattern recognition techniques [Fang 08; Brun 05; Bore 08].
Hybrid approaches using several measurements/techniques attempt to improve the per-formance of positioning systems when the propagation characteristics vary diﬀerently in the environments.

Range-based techniques

Positioning systems belonging to this category exploit information provided in the wireless LANs to calculate the range (distance/angle) that relates the base stations to the mobile termi-nal. The knowledge of this basic information is necessary to apply one of lateration/angulation techniques to locate the mobile terminal. In the following, we present a brief description, advantages, and problems related to the use of each technique.

Distance-based techniques

Diﬀerent measurements are used to estimate the distance between the base stations and the mobile terminal, like time of wave propagation, signal phase, and signal strength.

a Time Of Arrival (TOA)

Time Of Arrival (TOA), sometimes called Time Of Flight (TOF), techniques are based on the accurate measurement of the arrival time of a signal transmitted from a mobile terminal to several receiving base stations. If we assume that signals travel with the speed of light c, the distance d between the mobile terminal and each receiving base station can be estimated from the elapsed time t of signal propagation: d = c t. Accurate synchronization is required in the TOA techniques. This synchronization is realized thanks to the knowledge of the transmission date, and all receiving base stations as well as the mobile terminal should be accurately syn-chronized with a precise time source. In the case of a two dimensional positioning system, TOA measurement must be made with respect to signals from at least three reference base stations. Fig. (1.2) illustrates the location process based on TOA measurements.
The TOA-based techniques suﬀer of two problems. The first problem is that all mobile terminals and base stations in the system have to be precisely synchronized. The second one is that the transmitting signal should include a timestamps in order for the base station to calculate the distance traveled by the signal. Finally, TOA can be measured using diﬀerent signal techniques such as direct sequence spread-spectrum (DSSS) [Pete 98; Li 00] or ultra wide band (UWB) measurements [Corr 03]. A straightforward approach uses a geometric method to compute the intersection points of the circles of TOA. The position of the mobile terminal can also be computed by minimizing the sum of squares of a nonlinear cost function, i.e., least-squares algorithm [Fang 90; Kana 04]. It assumes that the mobile terminal, located at (x0;y0), transmits a signal at time t0, the n base stations located at (xi;yi); i 2 f1;2;:::;ng receive the signal at time ti; i 2 f1;2;:::;ng. As a performance measure, the cost function can be formed by the equation (1.2.1):
where ai can be chosen to reflect the reliability of the signal received at the base station i, and i(d) is given by the equation (1.2.2):
where c is the speed of light, and the state vector d = (x;y;t)T . This function is formed for each base station, i 2 f1;:::;ng, and i(d) could be minimized with looking to the coordinates x; y, and the time t. Then, the approximate location is determined by minimizing the function F (d) defined in the equation (1.2.1).
There are other algorithms for TOA-based indoor location systems as closest-neighbor (CN) and residual weighting (RWGH) [Kana 04]. The CN algorithm estimates the location of the mobile terminal as the location of the base station or reference point that is located closest to the mobile terminal. The RWGH algorithm can be basically viewed as a form of weighted least-squares algorithm. TOA-based positioning solutions are typically challenged in environments where large amount of multipath (NLOS), interference, or noise exists.

b Time Diﬀerence Of Arrival (TDOA)

The main idea of Time Diﬀerence Of Arrival (TDOA) technique is to use relative time mea-surements at each receiving base station instead of absolute time measurements. Thus, TDOA does not require the use of a synchronized time source at the mobile terminal in order to resolve timestamps and estimate the position. For each TDOA measurement, the mobile terminal must lie on a hyperboloid with a constant range diﬀerence between the two base stations. The equa-tion of the hyperboloid in two-dimensional (2D) Cartesian coordinates is denoted by (1.2.3):
di;j = p(x xi)2 + (y yi)2 (x xj)2 + (y yj)2 (1.2.3) where (xi;yi) and (xj;yj) represent the fixed base stations i and j; and (x;y) represent the coordinates of the mobile terminal [Dran 98]. Except the exact solutions to hyperbolic TDOA equation shown in (1.2.3) through nonlinear regression, an easier solution is to lin-earize the equations through the use of a Taylor-series expansion and create an iterative algo-rithm [Torr 84].
A mobile terminal location in a 2D environment can be estimated from the two intersections of two or more TDOA measurements, as shown in Fig. (1.3).
Two hyperbolas are formed from TDOA measurements at three base stations (BS1; BS2, and BS3) to provide an intersection point, which locates the mobile terminal M T . Conventional methods for computing TDOA estimates are to use correlation techniques. TDOA can be estimated from the cross correlation between the signals received at a pair of base stations. Suppose that, for the transmitted signal s(t), the received signal at base station i is xi. Assume that xi(t) is corrupted by the noise ni(t) and delayed by di, then xi(t) = s(t di)+ni(t). Similarly, the signal xj(t) = s(t dj) + nj(t), which arrives at base station j, is delayed by dj and corrupted by the noise nj(t). The cross-correlation function of these signals is given by integrating the lag product of two received signals over a time period T , as shown in the equation (1.2.4):
Except the previous TDOA methods, a delay measurement-based TDOA measuring method was proposed in [Li 00] for 802.11 WLANs, which eliminates the requirement of initial synchro-nization in the conventional methods.
Geo-location techniques that use TOA and TDOA metrics have several similarities. These techniques have proven to be highly suitable for outdoor geo-location systems. In addition, satisfactory results have been obtained from TOA and TDOA geo-location systems in half-open environments such as theaters, halls, and museums. Indoor, TDOA-based geo-location systems achieve best performance in large environments that are relatively open, with limited amount of obstacles and high ceilings that aﬀord direct LOS between the mobile terminal and the base stations. However, the propagated signals suﬀer of multiple reflections in obstructed environments, and TOA measurements don’t express the real distance between the base station and the mobile terminal, therefore, the performance degrades in terms of accuracy. In general, in these types of environments, TDOA and TOA-based geo-location systems operate eﬃciently and prove their performance and superiority.

c Received Signal Strength (RSS)

The drawbacks in the case of indoor environments of the above mentioned distance-based techniques (TOA and TDOA) using elapsed time to measure distance are the following ones: it is diﬃcult to find direct LOS between the mobile terminal and the base station, the radio wave propagation in obstructed environments would suﬀer from multipath eﬀects, and the time and angle of arrival signal would be aﬀected by the multipath eﬀect; thus, the accuracy of estimated location will decrease and the performance degrades. An alternative approach consists in estimating the distance of the mobile terminal from the base stations and using the attenuation of received signal strength. The signal attenuation-based methods attempt to calculate the signal path loss due to the wave propagation. Theoretical and empirical models are used to translate the diﬀerence between the transmitted signal strength and the received signal strength into a distance estimate. The knowledge of the transmitter output power, cable losses, and antenna gains, as well as the appropriate path loss model, allows an accurate estimation of the distance between two stations. The path loss represents the level of signal attenuation present in the environment, due to the eﬀects of free space propagation, reflection, diﬀraction, and scattering. An example of a common path loss model used for indoor propagation [Pahl 09] is presented by the equation (1.2.5):
where d represents the distance between the transmitter and the receiver, P (d) is the received signal strength at distance d measured in dBm, P (d0) is the referenced signal strength at the initial distance d0, represents the path loss exponent for the environment that indicates the rate at which the path loss increases with distance. The value of the path loss exponent depends on the signal frequency and the environment, and is highly dependent on the degree of obstruction present in the environment. Table (1.1) summarizes some values of this exponent according to the environment type.
Using only RSS-based geo-location systems that do not take into account any additional steps for attenuation and multipath in the environment rarely produces acceptable results ex-cept in very controlled situations. This includes those controlled situations where there is always direct LOS between the mobile terminal and the receiving base stations, with little attenuation to be concerned other than free-space path loss and minor impact from multipath. Most of sensor-network-based positioning systems use RSS measurement [Ash 04]. The accu-racy of these techniques can be improved by utilizing the pre-measured RSS contours centered at the receiver [Zhou 05] or multiple measurements at several base stations. A fuzzy logic al-gorithm shown in [Teub 06] is able to significantly improve the location accuracy using RSS measurement. However, other positioning systems use RSS as range-free measurement. Au-thors in [Suro 11] proposed a new method of radio frequency (RF) fingerprint-based technique for indoor geo-location. The received signal strength indicator (RSSI) is used as database val-ues which correspond to the location of the sensor nodes. Fuzzy C-Means (FCM) clustering algorithm is applied as the experiment data cluster method. FCM algorithm is deployed to cluster the obtained feature vectors into several classes corresponding to the diﬀerent amount of RSSI values. Their results show that FCM can cluster the mobile terminals in a group of the fingerprint database. The location of target node is arranged in various forms to validate the accuracy of the clustering technique. Euclidean distance is used as the parameter to compare the similarity between fingerprint database and the mobile terminal location. Their results show that the new method is simple and eﬀective to reduce the complexity, to support the low power and to reduce the time used in the fingerprint-based geo-location technique.

READ Market Outlook and Forecasts

d Round-Trip Time (RTT)

As we have mentioned above, TOA measurement requires strong synchronization between base stations. An alternative solution is Round-trip time (RTT) measurement, also called round-trip delay or Round-Time-Of-Flight (RTOF). By definition, RTT is the time required for a signal to travel from a specific base station to a specific destination (mobile terminal) and back again, as shown in Fig. (1.5). The advantage of using RTT is to avoid the time synchroniza-tion between base stations; in other words, a more moderate relative clock synchronization requirement replaces the synchronization requirement in TOA. In addition, RTT conserves the same characteristic mentioned for TOA measurement. Therefore, positioning algorithms for TOA can be directly applicable for RTT. In RTT-based positioning systems, the base station plays the role of a common radar. Thus, the mobile terminal will respond to the interroga-tion signal transmitted by the base station, and the complete round trip propagation time is measured by the base station. However, it is still diﬃcult for the base station to know the exact delay/processing time caused by the responder in this case. If the order of the delay time is relatively small compared with the transmission time, then, it could be ignored and this technique becomes applicable in long-distance or medium-distance systems. However, for short-distance systems, it cannot be ignored. An alternative approach is to use the concept of modulated reflection [Koss 00], which is only suited for short-range systems. An algorithm to measure RTT of WLANs packets is presented in [Gunt 05] with the result of measurement error of a few meters.

Table of contents :

1 State of the art: mobile terminal geo-location
1.1 Introduction
1.2 Indoor geo-location: different measurements and techniques
1.2.1 Range-based techniques
1.2.1.1 Distance-based techniques
1.2.1.1.a Time Of Arrival (TOA)
1.2.1.1.b Time Difference Of Arrival (TDOA)
1.2.1.1.c Received Signal Strength (RSS)
1.2.1.1.d Round-Trip Time (RTT)
1.2.1.1.e Received Signal Phase (RSP)
1.2.1.2 Angle-based techniques: Angle Of Arrival (AOA)
1.2.2 Range-free techniques
1.2.2.1 Associated Cell (CellId)
1.2.2.2 Location patterning techniques
1.2.2.2.a Probabilistic methods
1.2.2.2.b K-nearest neighbors (KNN)
1.2.2.2.c Artificial neural networks (ANN)
1.2.2.2.d Support vector machine (SVM)
1.2.2.2.e Smallest M-vertex polygon (SMP)
1.3 Tracking systems and prediction filters
1.3.1 Tracking systems
1.3.2 Prediction filters
1.3.2.1 Kalman filter
1.3.2.1.a Kalman filter modeling
1.3.2.2 Particle filter
1.3.2.2.a Particle filter modeling
1.4 Location systems: architectures and requirements
1.5 Conclusion
2 Our indoor location based on TOA and AOA using coordinates clustering
2.1 Introduction
2.2 Clustering and problem formulation
2.2.1 Cluster analysis
2.2.2 Measurements choice
2.2.3 Problem formulation
2.3 Proposed method
2.3.1 Two dimensional environment case
2.3.2 Extension to three dimensional environment case
2.4 Experimental results and discussion
2.4.1 Case study
2.4.2 Two dimensional case
2.4.3 Thresholds impact
2.4.4 Three dimensional case
2.5 Comparison
2.6 Conclusion
3 A comparison of learning and deterministic range-free techniques for indoor geo-location
3.1 Introduction
3.2 Artificial neural networks (ANN)
3.2.1 Definition
3.2.2 Neural network topologies
3.2.2.1 Feedforward neural networks
3.2.2.2 Recurrent neural networks
3.2.2.3 Hybrid neural networks
3.2.3 Neural network training (learning)
3.2.3.1 Supervised learning
3.2.3.2 Unsupervised (adaptive) learning
3.2.3.3 Reinforcement learning
3.2.4 Neural network applications
3.3 Proposed ANN approach for indoor location
3.3.1 Case study and fingerprint collection
3.3.1.1 Case study
3.3.1.2 Fingerprint collection
3.3.2 ANN-based proposed algorithm for indoor location
3.3.3 ANN experimental results
3.3.3.1 Impact of hidden layers number
3.3.3.2 Impact of heterogeneous fingerprints
3.3.3.3 Impact of fingerprint database resolution
3.4 K-nearest neighbor (KNN)
3.4.1 Proposed KNN-based algorithm for indoor location
3.4.2 KNN-based experimental results
3.4.2.1 Impact of nearest neighbor number K
3.4.2.2 Impact of the chosen metric: -nearest neighbor (-NN)
3.4.2.3 Impact of heterogeneous fingerprints
3.4.2.4 Impact of fingerprint database resolution
3.5 ANN vs KNN: comparison and discussion
3.6 Conclusion
4 Mobile tracking based on fractional integration
4.1 Introduction
4.2 Digital fractional integration: characteristics and applications
4.2.1 Fractional integration
4.2.2 Properties of the fractionally integrated trajectory
4.2.2.1 Regularity
4.2.2.2 Statistical analysis of the fractionally integrated path
4.2.2.2.a Average value of the differentiated function
4.2.2.2.b Autocorrelation
4.2.3 The short-memory principle
4.3 Our proposed method
4.4 Results and discussion
4.4.1 Enhancement of the path prediction using DFI
4.4.2 On the decrease of archive size
4.4.2.1 The linear predictor (LP) case
4.4.2.2 The Kalman filter case
4.4.3 The short-memory principle
4.5 Conclusion
Conclusion and perspectives