1Introduction

The research in high-resolution GSM positioning is part of a new localization system called “I-LOV” for search and rescue of buried people [1]. It is expected that at the time a building collapses, up to 80 % of the buried people carry along their mobile phone. Therefore, the I-LOV system intends to accelerate the search process by providing the rescue forces with possible positions of buried people based on network-based mobile phone localization. The decision to deploy GSM is due to the fact that (unlike 3G or 4G technologies) almost every mobile phone supports the standard. Apart from localizing an emergency call, GSM positioning is of interest in police and military applications, or may be utilized for location based services in smartphones.

To date, a variety of network-based GSM localization techniques are utilized. The most basic one is the method of cell identification (Cell-ID), which determines the mobile station’s position by indicating the nearest base station. With the help of the timing advance value and by narrowing results down to the sector of the directional antenna, a positioning resolution of roughly 550 m can be achieved [2]. Other approaches are based on received signal strength measurements or multipath fingerprinting. These techniques, however, require complete knowledge of the radio channel, which is not feasible for search and rescue applications [3].

Another method called Time of Arrival (TOA), measures the time a signal travels from the mobile station to three or more neighboring base stations. The requirement here is the knowledge of the time the transmission begins as well as a synchronized time basis with the base stations [2]. Unfortunately, the former requirement can not be fulfilled as access to the mobile phone is generally not available.

In this paper, the high-resolution principles time difference of arrival (TDOA) and angle of arrival (AOA) are proposed (depicted in Fig. 1).

Both methods are compatible with the GSM standard, and do not require any knowledge on the radio channel or the transmission time of the mobile phone. Nevertheless, it is advisable to have full control over the base stations and AOA receivers require additional array antenna equipment. It is also possible to use operator-independent receiver stations [4].

Because results are highly dependent on the signal’s bandwidth, our institute developed a bandwidth expansion technique for GSM that allows TDOA to reach a higher resolution. This makes it possible to compare the performance of TDOA in wideband with AOA in narrowband. The estimation algorithms presented here are the maximum likelihood estimator (MLE) for TDOA, root multiple signal classification (Root-MUSIC) and estimation of signal parameters via rotational invariance techniques (ESPRIT) for AOA. Although GSM has its own characteristics in signal composition and wave propagation, the results presented here may be transferable to other communication systems.

2Signal and channel models

2.1Global system for mobile communication

Despite the vast development in 3G and now 4G communication, GSM remains the world’s most widespread mobile communication standard. This makes it a popular source for radio-location. Its specification is continuously updated by the 3rd Generation Partnership Project (3GPP) [5]. Europe and most other parts of the world operate in the frequency bands GSM 900 and 1800. Due to the cellular nature of the mobile systems, geographic areas hold only a subset of the available frequency bandwidth. Therefore, GSM combines two multiplexing techniques, frequency division multiple access (FDMA) and time division multiple access (TDMA).

The research in this paper focuses on the E-GSM 900 uplink band from 880–915 MHz that is spanned in 124 channels, each 200 kHz wide. The time axis is further divided in 8 (or 16 half-rate) time slots. One time slot covers 156.25 bits, which is equivalent to a duration of about 577 μs. There are five different data formats that can be used in a time slot. The normal burst, the most frequently used burst structure, is chosen as signal source as it typically transfers digitized voice data. Voice generates stochastically distributed signals, which is favorable for the proposed estimation techniques because the signal will only correlate with itself. In addition, the following channel coding, interleaving, encryption and modulation of the voice data further randomizes the signal. However, some bits are used for signaling purposes and add a deterministic part to the signal. GSM uses a continuous-phase frequency-shift keying modulation named Gaussian minimum shift keying (GMSK).

The simulation of the GSM normal burst in this paper is compliant to the GSM specifications. It includes a pseudo-random bit generator characterizing speech, a normal burst generator, channel coding, interleaving and a GMSK modulator [6]. As encryption does not change the random nature of the bits, it is not required here. A power ramping function on the other hand may affect the estimator’s accuracy. The effects of power ramping is not studied here because it is expected to be negligible if the device is working accordingly to the standard, where tolerances for 147 of 148 bits are restricted to a ±1 dB power level. The multiplexing of the complex baseband signals is discussed in the following.

2.2Dependency of resolution on signal bandwidth

The actual resolution of the proposed estimators is highly dependent on the signal’s bandwidth. In general, the 200 kHz wide GSM signal can be declared narrowband. This, for instance, is beneficial for angle of arrival subspace methods, which are defined for narrowband signals and might fail in case of wideband signals [7].

This is different for the temporal resolution of the time difference of arrival method, which is proportional to the bandwidth of a signal. A GSM normal burst with a bandwidth of 200 kHz results in a coarse resolution of approximately 1.5 km (c/BW) [4]. In case of narrowband signals, estimators based on the correlation of signals have difficulties resolving the time delay between two consecutive signals. The result is characterized by a broadened correlation peak, which can only be resolved by a very high signal-to-noise-ratio (SNR) or exceedingly long observation intervals. Both criteria are usually bounded by the measurement equipment or the signal itself. The effect may become even more severe if multipath signals superimpose with the line-of-sight signal.

A technique within the GSM standard called frequency hopping is used to reduce frequency selective interferences caused by fading or interferences from adjacent channels. The base station triggers frequency hopping by switching the carrier frequency either periodic or pseudo-random after every TDMA frame. Figure 2 illustrates the time-frequency allocation with active frequency hopping. Here, the service provider’s cell is assigned to three different frequency bands. The traffic channel hops after each frame to a predefined frequency channel.

Research at our institute has demonstrated that by using frequency hopping, it is possible to virtually increase the frequency bandwidth on receiver side. This is realized by combining multiple bursts sent on varying carrier frequencies to one single signal [8]. For example in Fig. 2, a higher bandwidth signal is constructed by merging the first three TDMA frames. Then, the signal gets spanned over a bandwidth of 600 instead of 200 kHz (three times 200 kHz).

The bandwidth expansion allows a high temporal resolution for TDOA estimation. It can be applied if control over the base station is established, or at least the hopping sequence is known. Frequency hopping is simulated by a frequency mixer, which creates analytical signals on varying carrier frequencies of the E-GSM 900 band. In order to easily reconstruct the signal in the receiver, a fixed frequency spacing between following bursts is selected. The frequency mixer is followed by a multiplexer. In the simulations of this paper, the multiframe is simplified to contain only traffic channels.

3Time difference of arrival estimation

The method time difference of arrival (TDOA) refers to the difference in time-of-arrival of a mobile phone signal at two spatially separated receivers:

with n indicating the number of available base stations. Its equivalent distance is the product of the TDOA and the propagation speed (approximately the speed of light c):

The resulting range differences yield hyperbolic curves between base stations (BS), as depicted in Fig. 3. A mobile station’s position (MS) lies at the intersection of these hyperbola. Assuming the positions of the base stations are known, multilateration can be performed with a minimum of three time-synchronized base stations (four in 3D).

In Section 2.2 it was pointed out that the temporal resolution of TDOA estimation is constrained by the signal bandwidth. Therefore, a bandwidth expansion technique is introduced to improve resolution in narrowband GSM. The SNR, however, is fixed by the individual measurement equipment and the observation length can only be maximized by feeding the estimator with full GSM bursts. Another effect may result from multipath signals, which interfere by inducing a measurement bias depending on their signal strength. Furthermore, inaccuracies in the time-synchronization process or positioning of the base stations need to be minimized as they degrade the performance of the whole system.

In this paper, the maximum likelihood estimator (MLE) is used for calculating the time differences Δτ. The parametric estimator performs the probability density function (PDF) of a normal distribution on a set of noisy or incomplete observations. It is stated that the MLE has optimal asymptotic properties of being unbiased, and achieving the Cramer-Rao lower bound (CRLB) for an infinite number of samples [10].

The signal model for TDOA with two base stations is specified as the receive signal at BS 2 as a function of the receive signal at BS 1:

where Δτ refers to the time difference, α represents the complex attenuation, and n(t) AWGN. The receive signal y2(t) is considered an approximately random process with a Gaussian PDF. The signal model indicates a single source estimation, but may be modified if further clutter cancellation is required.

The likelihood function is defined as the joint PDF of the signal model for the unknown parameter $\theta ={\left[\Delta \tau ,\alpha ,{\sigma }_n^2\right]}^T$ and given observation intervals $y_2(N).{\sigma }_n^2$ describes the noise variance and N the number of independent discrete observations. In this particular case, it can be reduced to a function only dependent on Δτ. The so-called reduced log-likelihood function reads

The maximum likelihood estimator Δˆτ is the value that maximizes the reduced log-likelihood function and is found iteratively, where

Due to the analog to digital conversion, the MLE accuracy is bounded by the sampling interval. Therefore, it is recommended to perform additional polynomial interpolation subsequent to the estimation process. Simulations in this paper are performed with a 2nd order polynomial interpolation that approximates the maximum by fitting a parabola on three given data points:

Δˆτ0 is the MLE, Δt the sampling interval, and Λ−, Λ0 and Λ+ the values of the reduced log-likelihood function for the three given data points.

4Angle of arrival estimation

Another method for mobile phone localization is based on determining the angle of arrival (AOA) of a signal. Antenna arrays at the base stations measure the difference in phase (time) of the signal between antenna elements. The phase difference is then converted into an angle. Their relation can be expressed as

where Δφio refers to the phase difference between the sensor element i and the coordinate origin o. The distance di is a function of the angle of arrival θ, and λ denotes the wavelength of the signal. As illustrated in Fig. 4, positioning of the mobile station is performed with a minimum of two base stations via triangulation (3D additionally requires the elevation angle). The positions of the base stations are assumed to be known.

Simulations in this paper are conducted with a standard ULA antenna. A ULA consists of M identical sensors that are distributed equidistant on a line. The term standard is used if the spacing between array elements is half the wavelength of the signal. A magnetometer is used to determine the antenna array’s orientation. Errors in orientation measurement are directly transferred into the estimation error. In this paper, it is assumed that the orientation error is negligible. Also, antenna arrays need to be carefully calibrated to reduce mutual coupling effects as well as placed in the far-field of the source. Their accuracy may drop significantly for noisy nearly planar incoming waves [11].

Using the MLE for AOA estimation would mean a multi-dimensional (computational intensive) search. That is why subspace-based methods, which are significantly less computational complex, are employed. However, these estimators are declared suboptimal because they only approximate the CRLB for high SNR. Subspace methods for AOA estimation are (unlike TDOA) designed to detect narrowband signals. Hence, a single 200 kHz GSM burst works well as signal source. The SNR and the observation length have a similar effect on the accuracy as stated for TDOA. Multipath signals induce a measurement bias in case the angle of arrival differs from the direction of the LOS signal.

The subspace estimation methods follow a covariance matrix model. The receive signal is given as

where y(t) is a M-long column vector of the antenna element outputs. The array manifold matrix A = [a(θ1), . . . , a(θK)] holds all information on the geometry of the antenna array for a number of incoming waves (K). Since n(t) is AWGN, the covariance matrix of y(t) becomes

X denotes a nonsingular covariance matrix of the noise-free signal x(t) [7]. For coherent signals, X is singular and a forward-backward spatial smoothing decorrelation becomes necessary [12].

Root multiple signal classification (Root-MUSIC) is a parametric estimator with higher resolution than the original MUSIC, but only valid for ULAs. In a first step, it computes the sample covariance matrix, on which it performs an eigendecomposition in order to obtain the noise subspace. Root-MUSIC is different from MUSIC as it estimates the AOA by determining the argument (phase) of the roots nearest the unit circle of a spectrum polynomial. The polynomial equation is based on the noise subspace. If the AOA is defined perpendicular to the ULA, ˆθ is obtained by

where Δφi denotes phase angle of the ith root nearest the unit circle [13]. As mentioned before, the distance between antenna elements in a standard ULA is Δa = λ/2. fc is the carrier frequency of the signal.

The second estimator proposed is the estimation of signal parameters via rotational invariance techniques (ESPRIT). It has the advantage of being far less computational intensive since it does not involve a search for maxima as in Root-MUSIC. ESPRIT divides the antenna array in two identical subarrays with a known displacement vector Δā. This restricts the user to specific array configurations, e.g. the ULA. For ULAs, the displacement vector is the same as the interelement spacing Δa [7].

Instead of using the noise subspace, ESPRIT determines the signal subspace of the twin subarrays S1 and S2. The ESPRIT requirement is formulated as

where Φ describes a rotational matrix. The phase angle Δφi is the ith eigenvalue of ˆΦ, while ˆΦ is derived using Least-Square (LS) or Total-Least-Square (TLS) approximation. The AOA is calculated using (12).

It is noted that the subspace methods are limited to detecting a maximum of M −1 signal sources. The estimation of the actual number of incoming waves (multipath signals) is critical as this number determines the dimension of the signal/noise subspace. Its estimation is not included in the named methods and is usually done beforehand. Popular methods for this cause are the Akaike information criterion (AIC) or the minimum description length (MDL), which both originate from information theory [14]. Another method is based on sphericity tests, which in some cases yields better results than AIC or MDL [15]. In order to investigate the performance of the presented AOA estimators independently hereof, the number of signals here is fixed and assumed to be known.

5Simulation results

The setup for the following simulations consists of two base stations located around a GSM mobile station, as sketched in Fig. 1. The distance to the mobile station is 80 and 100 m, respectively. Depending on the sampling frequency, the actual location varies by ±c/2fs (here: fs = 40 MHz). It is possible to determine positioning accuracies by using techniques like the Geometric Dilution of Precision [16]. However, it is difficult to directly compare positioning results as the positioning method, number and placement of the base stations highly diversify the results. The following simulations solely investigate the capability of the localization methods TDOA and AOA for high-resolution detection of GSM signals.

5.1TDOA estimation with LOS signals and AWGN

TDOA estimation is performed with the MLE and a 2nd order polynomial interpolation (see Section 3). The MLE search is stopped after a distance difference of 100 m as higher values may not be plausible (case-specific). The actual distance difference for the mentioned setup is 14.97 m, which gives a maximum error of about 85 m. The MLE is fed with a single GSM burst as well as with bandwidth expanded signals containing up to 25 bursts. In theory, a higher number of bursts (frequency channels) can be used, but the computational complexity rises linearly with the number of bursts.

Figure 5 illustrates the performance of the MLE in a LOS scenario without multipath by indicating the root-mean-square error (RMSE) for a range of SNRs. This figure outlines that TDOA estimation using a single GSM normal burst (N = 1) is only reliable for a high SNR. As depicted in Fig. 5.b, there is a rapid increase in the magnitude of errors below a critical SNR of 27 dB. This can be explained by ambiguities in the peak detection of noisy signals when side-peaks approach the intensity of the main peak causing global errors. Side-peaks occur from signaling bits or the finite length of a signal. Eventually, below an SNR of −5 dB the AWGN superimposes with the likelihood of the estimator. The estimated difference in propagation distance of about 42 m is exactly the amount of variance one would expect from a wild guess.

The figure further shows that the resolution can be enhanced by combining multiple bursts sent on different frequencies. A bandwidth expanded signal of two bursts with a frequency spread of 200 kHz lowers the critical SNR by 5 dB. By spreading the two bursts on a wider frequency range (Δfc = 34.8 MHz is the maximum for E-GSM), it is possible to further lower the critical SNR before global errors occur. However, the transition between isolated ambiguities and a wild guess becomes very narrow due to stronger side peaks. Hence, the effective bandwidth can only be increased with an increase in the number of bursts. The upper end for the simulations presented here is the MLE using 25 bursts with a frequency spacing of 200 kHz. The algorithm is then well-capable of resolving the TDOA, indicated by an RMSE of less than one meter for an SNR of −8 dB or more. This concludes that the TDOA technique using the MLE proves to be robust against AWGN, assuming a wideband signal is provided.

5.2TDOA estimation with multipath signals

The impact of multipath propagation on the estimator is demonstrated in Fig. 6 by plotting the reduced log-likelihood function of the MLE algorithm (without polynomial interpolation) for a 25-burst signal with Δfc = 200 kHz. Additionally, the graph marks the LOS and the non-LOS (NLOS) signals according to the individual received signal power. The actual distance difference of 14.97mcan be clearly associated with the LOS signal. In this particular example, the LOS signal’s power is about 20 dB greater than the next NLOS signal. However, as described in Section 3, multipath signals may be of greater signal strength, which eventually results in more dominant peaks after the actual distance difference.

TDOA simulations in the B1 multipath scenario (see Section 2.3) using the MLE with polynomial interpolation for varying bandwidths are listed in Tab. 1. The number of signals (LOS and NLOS) is set to K = 7. The results show that the superposition of the multiple signal sources lead to a considerable measurement bias, e.g. an RMSE of 11.4 m for a single burst in scenario B1 LOS. Furthermore and in contrast to the AWGN simulations, a larger frequency spread for two bursts degrades the accuracy due to more frequent ambiguities in the peak detection. However, if the bandwidth is sufficiently increased as with 25 bursts, the RMSE can be halved. Naturally, the bias is much larger in scenarios without LOS due to the longer journey of the NLOS signals. The RMSE for 25 bursts then reaches merely 20.6 m. Nevertheless, for TDOA it is possible to compensate parts of the bias effect resulting from multipath by conducting channel measurements matching the required application scenario.

5.3AOA estimation with LOS signals and AWGN

AOA estimation is performed with the Root-MUSIC and ESPRIT algorithm as described in Section 4. In the mentioned setup, the distance between BS 1 and the mobile station is given as 97.30 m. The estimators performance is shown in Fig. 7 for a perpendicular incoming wave using a standard ULA of 2, 4, and 8 elements. The lower bound of the RMSE is denoted by the SQRT-CRLB. Due to the definition of the CRLB for local errors only, a comparison of the estimators to the CRLB fails below a certain SNR. Yet, the CRLB demonstrates that the accuracy can be increased with a higher number of array elements. Further, Root-MUSIC stands out as an efficient estimator by approaching the CRLB for SNR above −22 dB (8-element array). ESPRIT, on the other hand, is offset from the optimum for array configurations of more than 2 array elements, while the LS and the TLS-approximation yield similar results. Nevertheless, the results indicate that both algorithms are robust against noise. An RMSE of less than 1° is achieved with an SNR of −10 dB, even with a 2-element array.

Tab. 1. RMSE of TDOA estimation with multipath, 5000 simulation runs.

5.4AOA estimation with multipath signals

The challenge coming from multipath propagation for AOA estimation is visualized in Fig. 8 with an example of a Root-MUSIC estimation on an 8-element antenna array and seven incoming signal sources. The figure indicates the absolute value (magnitude) of the polynomial roots on the y-axis and their associated AOAs on the x-axis. The signal power of the LOS and NLOS signals is depicted on the right hand side. In theory, the 8-element array is capable of detecting all seven paths, while the root nearest the unit circle is supposed to represent the LOS signal. In this particular example, the angle of the LOS signal is properly identified and strongly valued. However, the remaining paths are not recognized, and instead, the algorithm calculates roots at seemingly random angles. This leads to an estimated angle of 29 °, far off the actual AOA.

Simulations in the B1 multipath scenario (K = 7) using the Root-MUSIC and ESPRIT algorithm with 2, 4, and 8 array-elements are summarized in Tab. 2.a. The results in the B1 NLOS scenario indicate that AOA estimation without a LOS to the mobile station is not feasible as NLOS signals arrive from all kinds of directions. Furthermore, it is shown that ESPRIT reaches higher accuracies for 4- and 8-element arrays than Root-MUSIC. The LS-approximation’s performance is similar to the TLS-approximation. Surprisingly the best results are given for a 2-element array with an RMSE of 11.2 °. Subspace methods using 2 sensors are only able to detect a single path as the maximum number of resolvable paths is M − 1 (see Section 4). This suspects the AOA estimation process to show a better performance if only one path is resolved.

Therefore, the simulations are repeated in Tab. 2.b with the difference that only one path is set to resolve. The resulting angle can be interpreted as the average over all seven paths. Now, the estimators show a considerable smaller RMSE for 4 and 8 array elements. The RMSE of 7.2 ° and 7.1 ° of ESPRIT is about one degree smaller than that of Root-MUSIC. The simulations demonstrate subspace methods have severe problems with path allocation. Eventually, if only one path is resolved, a 4-element antenna array is recommended considering accuracy and cost of hardware.

Tab. 2. RMSE of AOA estimation with multipath, 5000 simulation runs.

6Conclusion

The proposed methods TDOA and AOA are analyzed in simulations for high-resolution GSM mobile phone localization. First, it is shown to be essential to integrate the band-width expansion technique in the TDOA estimation process. This allows achieving a high resolution for the 200 kHz narrow GSM signals. Moreover, the MLE demonstrates the robustness of the method against noise. In the presence of multipath however, and especially if no line-of-sight (LOS) to the mobile station exists, the accuracy is reduced by an additional bias due to the superposition of multiple signal sources. If a LOS can be established, the RMSE reaches approximately 5 mfor a bandwidth expanded signal of 25 bursts.

In comparison, the subspace methods Root-MUSIC and ESPRIT provide very accurate angle estimates for signals buried in noise. However, the simulations highlight that the AOA technique depends on a LOS to the mobile station and preferably little multipath, e.g. in open-space scenarios. A rough estimate of 7.2 ° for ESPRIT with 4 antenna elements can be obtained by resolving only a single signal source.

As search and rescue applications eventually face strong multipath signals, the TDOA method is recommended. TDOA is realized with a single antenna, but requires a minimum of three base stations and additional hardware for their time-synchronization. As presented, the LOS and WINNER II channel models differentiate the effects of channel noise and multipath interference. The I-LOV project further conducted channel measurements and initiated a channel model for collapsed buildings [17]. Based on this channel model, a sophisticated multilateration algorithm can be developed, which is expected to largely improve the TDOA system’s performance with multipath.

Acknowledgment: This work has been created as part of the “I-LOV” project funded by the German Federal Ministry of Education and Research (BMBF).