InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Communications and Security » "Trends in Telecommunications Technologies", book edited by Christos J Bouras, ISBN 978-953-307-072-8, Published: March 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 21

Performance Analysis of Time-of-Arrival Mobile Positioning in Wireless Cellular CDMA Networks

By M. A.Landolsi, A. H. Muqaibel, A. S. Al-Ahmari, H.-R. Khan and R. A. Al-Nimnim
DOI: 10.5772/8470

Article top

Overview

Network-based wireless mobile radiolocation
Figure 1. Network-based wireless mobile radiolocation
TOA radiolocation based on intersection of base station centered circles
Figure 2. TOA radiolocation based on intersection of base station centered circles
Cellular network model, with center cell and two tiers of interfering cells.
Figure 3. Cellular network model, with center cell and two tiers of interfering cells.
DLL system used for CDMA signal timing synchronization and TOA estimation
Figure 4. DLL system used for CDMA signal timing synchronization and TOA estimation
Mobile TOA Tracking error PDF at BS1, BS2, BS3 for Case 1 (MS without handoff)
Figure 5. Mobile TOA Tracking error PDF at BS1, BS2, BS3 for Case 1 (MS without handoff)
Mobile TOA tracking error PDF at BS1, BS2, BS3 for Case 2 (MS in 2-way soft handoff)
Figure 6. Mobile TOA tracking error PDF at BS1, BS2, BS3 for Case 2 (MS in 2-way soft handoff)
Mobile TOA time tracking error PDF at BS1, BS2, BS3 for Case 3 (MS in 3-way soft handoff)
Figure 7. Mobile TOA time tracking error PDF at BS1, BS2, BS3 for Case 3 (MS in 3-way soft handoff)
Illustration of the impact of the number of users on the TOA tracking error probability density function.
Figure 8. Illustration of the impact of the number of users on the TOA tracking error probability density function.
Layout of the mobile localization geometry used to test the accuracy of the AML algorithm.
Figure 9. Layout of the mobile localization geometry used to test the accuracy of the AML algorithm.
Illustration of mobile positioning accuracy with the Approximate Maximum Likelihood Algorithm.
Figure 10. Illustration of mobile positioning accuracy with the Approximate Maximum Likelihood Algorithm.

Performance Analysis of Time-of-Arrival Mobile Positioning in Wireless Cellular CDMA Networks

M. A. Landolsi1, A. H. Muqaibel1, A. S. Al-Ahmari1, H.-R. Khan1 and R. A. Al-Nimnim1

1. Introduction

Recently, wireless mobile communication systems have experienced a tremendous growth and became an integral part of people’s daily life worldwide. This global predominance of wireless communications has been ever more pronounced with the success of new generations of wireless communication standards that support a rich set of value-added features in addition to basic phone services. Among these features is the possibility to offer radiolocation services whereby the mobile system (MS) position is determined by combining relevant information (such as signal time of arrival or angle of arrival) from different base stations (BSs) having radio links with the intended mobile. This positioning capability can support many services ranging from medical emergency help, security and law enforcement, on-the-road assistance, location-dependent commercial advertisement, etc. As such, mobile radiolocation has been mandated by several of the recently introduced wireless standards, and is being widely deployed by cellular network operators worldwide (Rappaport et al., 1996).

With the deployment of the 3rd generation wireless cellular standards such as the Universal Mobile Telecommunication System (UMTS) (Dahlman et al., 2000), the use of wideband code division multiple access (CDMA) signals is poised to offer highly accurate positioning capabilities with time-of-arrival (TOA) information owing to the fine timing resolution of the high chip rate wideband spread-spectrum waveforms used. There are however some impairments such as multi-path fading, multi-user interference and noise, that can affect the performance of mobile positioning schemes. In particular, because of the need to use signal detection at several base stations in mobile positioning, the problem of near-far interference at remote base stations (whereby a far-away mobile weak signal can be overwhelmed by strong signals from close-in mobiles) can constitute a major limiting factor. In CDMA networks, this is further exacerbated by power control (Viterbi, 1995). Indeed, power control loops operate in such a way to maintain the received power from different users at the same level at their respective serving base station. However, at other non-serving base stations (not actively involved in a call with the intended mobile), the mobile received power level can be extremely low, thereby giving rise to a problem of signal hearability, which, in turn, will affect the accuracy of the mobile positioning algorithms (Gosh & Love, 1998). A thorough analysis of these different aspects under realistic channel modeling and network traffic loading conditions is therefore necessary in order to obtain an accurate assessment of the achievable positioning performance.

In this work, we study the accuracy of mobile radiolocation under near-far interference, and show that it can vary considerably depending on the mobile link quality with the base stations involved in position determination. We first present a detailed performance analysis of mobile TOA estimation in broadband CDMA wireless cellular networks at the different base stations surrounding the mobile terminal. In most previous works, the proposed radiolocation algorithms have simplistically assumed that the time-of-arrival measurements are Gaussian-distributed, with a fixed known variance that is commonly set irrespective of the actual RF channel and interference conditions or other system parameters. Moreover, the same TOA variance is typically assigned for all base stations involved in positioning, which is an inaccurate and overly optimistic assumption, as our results will show. Instead, our approach is the use of complete statistics for the mobile timing estimation errors, derived by taking into account realistic system parameters at the different base stations of interest.

Since precise TOA estimation in CDMA receivers is typically implemented by delay-locked loop (DLL) tracking systems (Viterbi, 1995), a detailed study of the DLL TOA tracking is introduced under fading and multi-user interference conditions assuming a cellular model with multiple tiers of base stations, and it is shown that the DLL tracking performance can vary widely depending on the level of multiple-access interference and RF propagation conditions of the links between the mobile and base stations. Using the TOA data collected at the base stations involved in mobile positioning, a numerically-efficient, quasi-optimum algorithm, based on Approximate Maximum Likelihood (AML) estimation (Chan et al., 2006), is presented, and a generalization of this algorithm is also derived under the realistic assumption of un-equal TOA estimation errors at the different base stations.

Based on our analysis, the impact of mobile link condition and its relative position with respect to the base stations involved in its positioning is fully quantified for a number of scenarios depending on the near-far interference environment and the level of Soft Handoff (SHO) connectivity of the mobile with the base stations. Our results show that positioning accuracy is greatly improved when the mobile station is in 2-way, and particularly in 3-way SHO (i.e., with two and three base stations, respectively), compared to single connectivity with only the home serving base station.

The rest of the chapter is organized as follows. First, in Section 2, we present an overview of radiolocation techniques, focusing in particular on network-based approaches with TOA processing suitable for cellular systems. The system modeling and analysis of near-far interference in CDMA networks is presented in Section 3, followed by a detailed analysis of the performance of delay-locked loops for time-of-arrival tracking in Section 4. Then, in Section 5, the approximate maximum likelihood positioning algorithm is presented, and various illustrative examples and numerical results are discussed in Section 6, followed by summary and final conclusions in Section 7.

2. Wireless Network-Based Mobile Radiolocation

2.1. Overview

The concept of wireless radiolocation refers to the determination of the geographic position information of a mobile user in terms of its geographic coordinates with respect to a reference point. Wireless location is also commonly referred to as mobile positioning, radiolocation, or localization. Position location techniques can be classified into two main categories: handset-based and network-based. A well known example of handset-based radiolocation is the Global Positioning System (GPS) and other similar systems (Kaplan, 1996). The other category consists of network-based techniques that utilize the existing wireless cellular networks to obtain location information (Sayed, et al., 2005). In this work, we mainly focus on the network-based approach which integrates seamlessly with the widely deployed mobile cellular infrastructures throughout the world. The basic architecture of such systems is illustrated in Figure 1.

media/image1.png

Figure 1.

Network-based wireless mobile radiolocation

The network-based positioning schemes rely on data collected by several base stations surrounding the mobile station of interest, and can be based on the mobile’s signal strength (SS), angle of arrival (AOA), time of arrivals (TOA) or time difference of arrival (TDOA) measurements. Using these measurements, specific geometric and/or statistical signal processing algorithms are used to determine the mobile location. Hybrid methods involving more than one of type of measurements can also be used (Sayed, et al., 2005). In general, locating a mobile in two-dimensions requires a minimum of three sets of measurements from corresponding base stations, although for AOA methods, two base stations are sufficient. However, in the presence of noisy measurements, statistical signal processing algorithms using data collected from multiple base stations are preferred in order to resolve the ambiguities arising from multiple crossings of the lines of position, and to improve the positioning accuracy.

2.2. Time-of-Arrival Mobile Radiolocation

TOA-based techniques offer several advantages compared to the other methods, including low cost and ease of use. The TOA data is readily available from timing synchronization mechanisms at the different base stations, without requiring complex hardware as with the Angle-of-Arrival methods. In particular, with the widespread deployment of the latest 3G CDMA-based wireless cellular networks, the spread-spectrum signaling waveforms offer high time resolution and good robustness vis-à-vis the radio channel impairments (fading, shadowing, and near-far interference), and are therefore well-suited to aid in achieving the required accuracy in position location services.

In the TOA-based mobile radiolocation approach, the distance between an MS and a BS is measured by finding the one-way propagation delay under direct line-of-sight (LOS) propagation conditions. The TOA measurements at the different base stations are therefore directly proportional to the mobile-base distance separation. The involved base stations are assumed to have a common timing reference, with a known mobile transmission time. Geometrically, the mobile position will trace a circle centered at the base stations. By using three base stations to resolve ambiguities, the mobile position is given by the intersection of these circles as illustrated in Figure 2. It should be pointed out that, in the presence of noisy TOA data due to interference and synchronization errors, the three circles may not intersect at a single point. Therefore, the geometric approach will not produce a single intersection point, and “statistical” techniques are typically adopted to process the noisy data, as will be further discussed subsequently when we introduce the AML algorithm.

media/image2.png

Figure 2.

TOA radiolocation based on intersection of base station centered circles

3. Near-Far Interference Analysis

3.1. Signal and System Models

Consider a cellular CDMA network employing signaling schemes with quaternary phase-shift keying (QPSK) modulation and complex spreading (conforming to 3G/UTMS standards (Dahlman et al., 2000). At the transmitter, the complex baseband signal for a given mobile user is given by

s˜(t)=m=smh(tmTc)
(1)

where {sm } are the complex spreading chip symbols, and Tc the chip duration. The information data bits are omitted here for simplicity as this will be applicable for a pure pilot signal that can be used for positioning purposes. The impulse response h(t) of the pulse-shaping filter is assumed to be a root-raised cosine filter with roll-off factor 22%, as recommended in the UMTS standard. As will be seen next, the Fourier transform H(f) of the filter impulse response h(t) will have a major impact on the other-user interference in cellular CDMA networks.

For wireless fading channels, the received signal at the output of the radio frequency (RF) receiver filter is written as

r(t)=PRe{i=1Ms˜(tτi(t))ai(t)ej2πfct}+n(t)
(2)

where P is the received signal power, M is the number of resolvable multipath signals, with a i and τ i denoting the i-th path complex Gaussian tap factor (with a Rayleigh-fading magnitude) and its propagation delay, respectively, and f c is the carrier frequency. The noise signal n(t) models the total noise-plus-interference terms and is assumed to be zero-mean Gaussian random process. For the different resolvable multipath signal epochs, we mainly focus on the first arriving signal which will be tracked to estimate its TOA. The combined multiple-access interference (MAI) terms from both same-cell and other-cell users can be modeled as being Gaussian distributed, which is a valid assumption for a large number of users. In this case, it can be shown that the total composite power spectral density (PSD), I 0, that captures the effect of both thermal noise and MAI terms (assumed to be statistically independent) is given by (Viterbi, 1995)

I0=N0|H(f)|2df+ρoTc|H(f)|4df=N0+ρoTc|H(f)|4df
(3)

where N o is due to the thermal noise component and the factor ρ ο represents both same-cell and other-cell MAI terms. The function H(f) denotes the Fourier transfer of the chip shaping filter impulse response h(t). The MAI PSD term is typically the dominant factor in CDMA systems, and will depend on network loading, fraction of inter-cell to intra-cell MAI, channel pathloss and shadowing models. For typical system parameters of interest, it is found that the ρ o MAI factor is approximately 1.6(K u-1), where K u is the number of users per cell (Viterbi, 1995).

3.2. Near-Far Interference and Soft Handoff Impact

We consider a cellular network with a central cell and two tiers of surrounding cells as illustrated in Figure 3, where mobiles are assumed to be uniformly distributed across the coverage area.

media/image6.png

Figure 3.

Cellular network model, with center cell and two tiers of interfering cells.

The mobile received power at a given base station, BSi, is multiplied by an attenuation factor, α , that reflects distance path loss, p(d), and log-normal shadowing factor, ξ, according to (Viterbi, 1995):

α(dBSi,ξBSi)=p(dBSi)10ξBSi/10
(4)

The path-loss factor is assumed to follow the model:

p(d)=10nlog10(d)
(5)

where n is the path loss exponent and d the mobile’s relative position with respect to the base station. For a given mobile location, shadowing vis-à-vis the different base stations is typically assumed to be partially correlated, log-normally-distributed, and given by (Viterbi, 1995):

ξBSi=aξc+bξi
(6)

where ξc and ξi denote the common and independent terms, respectively, and a 2+b 2=1.

With closed-loop CDMA power control, a given mobile will have the same received power at its home (serving) base station compared with other intra-cell mobiles. On the other hand, at the neighboring base stations, the mobile will be received at much lower power due to the so-called near-far problem (which cannot be mitigated due to the lack of “inter-cell” power control). However, when the mobile is in soft-handoff with other neighboring base stations, its received power is relatively close to that at the home cell, and this greatly improve radiolocation accuracy, as will be discussed next.

Since TOA estimation accuracy depends on the timing synchronization mechanism, which is in turn affected by the received interference levels at the different base stations, the near-far interference at the non-serving base stations will have a major impact on the final mobile positioning accuracy. To illustrate this point, we consider a system where the mobile is served by the center base station BS1 and is radio-located using TOA data from three or more base stations BS1, BS2,…, BS7 (sorted in a descending order from BS1 that receives the highest average received power). The near-far interference impact can be conveniently assessed by defining the ratio of its average received power at BSi compared to BS1 (for which the power will be normalized to 1, and used as a reference value). We then define the following:

where Pi is the received power at BSi and β 1 =1≥ β 2β 3...β 7. A wide fluctuation in the β factors is expected depending on the mobile position relative to the base stations of interest. It should be noted that, due to power control, all mobiles will be received at equal power (β =1) at their respective home serving base stations, but much lower values of β are expected at far-away base stations (because of the near-far problem). This however will depend on the relative position of the mobile with respect to the other base stations (i.e., its proximity to the cell border). Soft Handoff (SHO) is one of the salient features of CDMA cellular systems which allow the mobile to be simultaneously connected to more than one serving base station. In fact, the possibility of SHO calls enables a stronger signal reception at multiple base stations, and this will in turn improve positioning accuracy.

To further investigate this point, we consider different scenarios denoted by Cases 1, 2, and 3, respectively. Case 1 refers to a mobile in close proximity (within half the cell radius, R) of its serving BS1, with a signal at least 10dB above that at the other nearest two base stations. Case 2 represents a two-way soft handover scenario, with the mobile power at BS2 within 3dB from that at BS1. Finally, Case 3 corresponds to a 3-way soft handover situation where the mobile signal at both BS2 and BS3 is within 3dB compared to BS1. The numbers chosen here merely serve to illustrate the variability in received signal power (and its subsequent impact on TOA estimation accuracy), but do not attempt to model the specific thresholds and soft handover mechanisms used in CDMA standards.

Table 1 and Table 2 give the different β factors for the three cases of interest, and for different values for the pathloss and shadowing models, where a typical 50% correlation factor is assumed (a=b). For the numerical results, we assumed typical parameters for the radio propagation channel model. A two-segment pathloss model with breakpoint at distance do =200m and exponents n=2 and 4, respectively, was used, with a load of 20 users per cell, and a cell radius of 2Km. The relative powerfactors given in Table 1 and Table 2 clearly show that large variations occur across the base stations depending on the mobile soft handoff conditions and its proximity to one or more base station, and this will impact the accuracy of signal estimation at the different base stations as will be discussed next.

β1 β2 β3 β4 β5 β6 β7
Case 1 (mobile close to home BS)10.0216 0.0113 0.0069 0.0045 0.0031 0.0021
Case 2 (mobile in two-way SHO)10.6982 0.2215 0.1202 0.0735 0.0485 0.0331
Case 3 (mobile in three-way SHO)10.7922 0.6353 0.2993 0.1701 0.1065 0.0706

Table 1.

Relative received power factors for various mobile soft-handoff link conditions. Shadowing s.t.d σ=8dB.

β1β2β3β4β5β6β7
Case 1 (mobile close to home BS)10.0248 0.0125 0.0072 0.0045 0.0030 0.0020
Case 2 (mobile in two-way SHO)10.7000 0.2281 0.1258 0.0761 0.0486 0.0322
Case 3 (mobile in three-way SHO)10.7985 0.6443 0.3403 0.1953 0.1252 0.0808

Table 2.

Relative received power factors for various mobile soft-handoff link conditions. Shadowing s.t.d σ=12dB.

4. Signal Time-of-Arrival Estimation

4.1. Delay-Locked Loop Time Tracking

Timing synchronization for CDMA signals is typically implemented in two steps consisting of an initial coarse timing acquisition (within an uncertainty range on the order of one-chip interval), followed by fine time tracking achieved by a delay-locked loop (DLL) mechanism (Viterbi, 1995). In this work, we assume that the initial timing acquisition has been achieved, and focus on the more accurate DLL tracking as the main signal timing estimation mechanism. For each base station involved in mobile positioning, a DLL device continuously attempts to bring the local code timing estimate in perfect alignment with the incoming mobile signal. However, this timing estimation will be subject to error due to noise, fading and multiple-access interference. In the following, we consider TOA estimation based on a non-coherent DLL (NC-DLL) scheme. In practice, the NC-DLL is preferred over a coherent structure because of its insensitivity to carrier phase error and data modulation. Figure 4 depicts a block diagram showing the different processing stages of a NC-DLL code tracking loop. Because QPSK spreading is used, the NC-DLL employs both I & Q branches where the I & Q received signals, after down conversion and chip matched filtering, are fed to two early & late branches which correlate the spread-spectrum waveforms with advanced and delayed code sequence replicas. The outputs obtained at the I & Q channels of the early & late branches can be obtained as (Viterbi, 1995)

YI±=ANPTCR(τ±δ)cosθ
(8)
YQ±=ANPTCR(τ±δ)cosθ
(9)

where A is the fading signal envelope modeled as a Rayleigh random variable, and θ is its uniform phase. δ is the early & late timing offset (typically set to T c/2), P is the signal power, and N is the number of accumulated chips. The function R(τ) is a correlation function given by the convolution of the impulse responses of the pulse-shaping filter and its matched filter (Viterbi, 1995):

R(τ)=h(τ)h(τ)=|H(f)|2cos(2πfcτ)df
(10)

The DLL I & Q correlator outputs are combined as shown in Figure 4, and a resulting discriminator metric ΔZ is low-pass filtered to form an error signal used to drive a numerically-controlled oscillator (NCO) that controls the code timing adjustment. The DLL discriminator output can be obtained as (Viterbi, 1995):

ΔZ=βAS(ε)+η
(11)

where β is the power reduction factor reflecting the impact of DLL operation at different base stations (compared to the main serving base station, as discussed previously). The term η represents the combined Gaussian noise term with variance I 0. The function S(ε) is known as the normalized DLL S-curve, and is given by

S(ε)=R2(εδ)R2(ε+δ)
(12)

where ε is the normalized timing error given by

ε=(ττ^)/Tc
(13)

with τ denoting the correct TOA and τ^ the estimated one.

A common figure of merit for assessing the DLL performance is based on the tracking jitter variance. For additive white Gaussian (AWGN) channels, a simple upper-bound approximation for the tracking jitter variance, valid for linearized first-order DLL models, is derived in (Viterbi, 1995) as

σε2Io2+4NEcIoN2Ec2κ2
(14)

where Ec is the received chip energy, κ is the slope of the S-curve at the origin, and I 0 is the variance of the thermal noise & MAI terms. However, there is no simple equivalent result for the case of frequency-selective multipath fading channels considered in this work, and the above approximation is only valid for high mobile received Signal-to-Noise Ratio (SNR) conditions, which is not necessarily the case at the remote base stations (other than the home serving one), as discussed previously. In this work, we resort to a more accurate performance analysis valid for all SNR conditions and based on the computation of the full statistics (probability density function) of the DLL tracking loop, as discussed next.

media/image21.png

Figure 4.

DLL system used for CDMA signal timing synchronization and TOA estimation

4.2. DLL Tracking Error Statistics

For the purpose of analyzing the impact of TOA estimation error on mobile positioning accuracy, we need to obtain accurate statistics for the TOA measurements at each of the base stations involved in tracking the given mobile TOA. Hypothetical distributions (Gaussian models) are commonly assumed for the TOA timing estimation error. The same variance is usually assigned to the TOA error at all base stations involved in mobile positioning, and this variance is sometimes set rather arbitrarily. In this work, we use results based on a more rigorous analysis with full derivation of the TOA error probability density function (PDF). The results are obtained following the approach presented in (Su & Yen, 1997) and extended to quadrature-spread CDMA signals in (Khan, 2009). Assuming a discrete-time model, the analysis is based on a discrete-time Markov model for the residual DLL error, according to the following equation:

εk=εk1KNCO[βAk12S(εk1)+ηk1]
(15)

where KNCO is the NCO gain, and ηk is the additive Gaussian noise term. It can be seen that the residual tracking error follows a discrete-time Markov process for which the first order probability distribution can be obtained using the Kolmogorov-Chapman equation (Su & Yen, 1997):

pk(ε)=fk1(ε|x)pk1(x|ε0)dx
(16)

where ԑ 0 is the initial timing error, pk-1(x|ԑ0) is the PDF of x given ԑ0, and fk-1(ԑ|x) is the transition pdf of ԑk given x. Through detailed analysis, one can calculate the exact expressions fk-1(ԑ|x) under assumption of a Rayleigh fading channel. Using numerical integration, it is then possible to iterate the Kolmogorov-Chapman equation to get the PDF of the TOA estimation error. The lengthy details of this derivation are not included here, but can be found in (Khan, 2009).

The procedure outlined above can be done for different scenarios reflecting mobile TOA estimation at a given base station of interest. For our purpose, we analyze the performance of TOA DLL tracking at the different base stations for each one of the three cases described in Section 3. The results are shown in Figures 5 through 7, where it is clearly seen that the TOA residual error behavior can vary widely depending on the mobile position vis-à-vis the tracking base station. For example, in Figure 5 which corresponds to a mobile very close to its home serving base station, the residual error at the home base station is well-confined and nearly Gaussian-distributed (with a standard deviation found to be on the order of 0.15Tc), whereas for the other two base stations, the timing errors remain nearly uniformly-distributed with a standard deviation of 0.29Tc (which shows that the DLL loops at those base stations are not effectively tracking the mobile signal TOA). On the other hand, in Figure 6 and Figure 7 corresponding to 2-way and 3-way SHO, respectively, the mobile time tracking performance at BS2 and BS3 is markedly better, with distributions approaching that of the home BS1. It is to be noted that the number of users per cell (assumed the same for all cells, for simplicity) can also have a major impact on the timing estimation accuracy, regardless of the mobile position scenario (i.e., for all different cases discussed previously). Indeed, as shown in Figure 8, when the number of users increases, the tracking error PDFs are more wide-spread, and have an increasing error s.t.d (given with a normalization factor of 1/Tc).

media/image24.png

Figure 5.

Mobile TOA Tracking error PDF at BS1, BS2, BS3 for Case 1 (MS without handoff)

media/image25.png

Figure 6.

Mobile TOA tracking error PDF at BS1, BS2, BS3 for Case 2 (MS in 2-way soft handoff)

media/image26.png

Figure 7.

Mobile TOA time tracking error PDF at BS1, BS2, BS3 for Case 3 (MS in 3-way soft handoff)

media/image27.png

Figure 8.

Illustration of the impact of the number of users on the TOA tracking error probability density function.

5. TOA Processing for Mobile Positioning

5.1. Approximate Maximum Likelihood Algorithm

In time-of-arrival radiolocation techniques, the distance is calculated as the propagation time multiplied by the speed of light c. Line-of-sight (LOS) propagation is assumed, whereby the mobile signal travels on a direct path at the constant speed of light in free space. It is further assumed that the base stations are synchronized and the mobile transmission time is known (set to zero for simplicity). The TOA measurements, produced at each base station, are therefore directly proportional to the mobile-base distance separation. Geometrically, circles centered at the base stations can be drawn with the calculated distance as the radius. With the help of three base stations, the mobile location can be found geometrically as the intersection of the corresponding circles. However, in the presence of noise and interference, the three circles may not intersect at a single point. Therefore, the geometric approach is not suitable, and several other “statistical” techniques have been proposed (Caffrey, 1999), (Sayed et al., 2005) to process the noisy data. Many of these are based on iterative algorithms using least-squares or gradient search minimization. On the other hand, since the positioning equations involved are typically nonlinear, some traditional approaches based on linearization followed by a gradient search were proposed (Niezgoda & Ho, 1994). However, these approaches suffer from sensitivity to initialization errors and convergence problems. More recently, some researchers introduced new closed-form linear techniques (Caffrey & Stuber, 2000), (Chan & Ho, 1994), but the drawback of these methods is that optimum location estimates can only be found at high SNR values, which may not always be the case in practice.

Another interesting solution was proposed by (Chan et al., 2006) and shown to have near-optimum performance, with the added advantage of reduced complexity. Their method uses an Approximate Maximum Likelihood (AML) algorithm, which we adopt in this study. In the following, we give a general overview of the AML algorithm processing steps, and introduce a modification tailored towards the case of unequal TOA variances at the different base stations, and relevant to mobile radiolocation under near-far interference conditions (which is the focus of this work), as will be outlined subsequently. Based on the assumed cellular geometry, the true distances between the BSs and MS are given by

Ri=(xxi)2+(yyi)2
(17)

i=1,2,……,NBS

where NBS is the number of involved BSs. The measured distances, li, is given by

i=1,2,……,NBS

where εi is the DLL timing error. In matrix form, this is written as

Dividing by c to get the measured TOA vector T, we obtain

T=Rc+εc=T0+e
(20)

where

R=[R1RN]t=R(Θ)
(21)
and
e=[e1....eN]t
(22)

is the vector of additive measurement noise, and T0 is the vector of true TOAs. The original AML algorithm proposed by (Chan et al., 2006) assumes that all BSs have an equal error variance. Hence, the elements of e are assumed to be independent, zero-mean Gaussian random variables with covariance matrix

Q=E{eet}=σ2I
(23)

The AML algorithm can be generalized to account for different values of the error variance at different BSs. If the variance of the error can be estimated at each BS, one can use this information to improve the localization performance by giving more trust to BSs with lower error variance. In this case the elements of e are assumed to be independent, zero mean Gaussian random variables with covariance matrix:

Q=E{eet}=diag[σ12σN2]
(24)

The conditional probability density function (PDF) of T given Θ is given by

f(T|Θ)=(2π)NBS2(detQ)12exp{J2}
(25)

where

J=[TR(Θ)c]tQ1[TR(Θ)c]=[e1....eN][σ1200σN2]1[e1eN]=i=1NBS1σi2 ei2
(26)

The ML estimate of the MS position (x, y) is the Θ that minimizes J (Trees, 1968). Minimizing J is done by setting its gradient with respect to Θ to zero. Considering first the derivative with respect to the position variable x, we have

Jx=i=1NBS1σi2 ei2x=i=1NBS1σi2 2eieix
(27)

By expressing the timing error in terms of the difference between the true TOA and measured one, this gives

eix=x(TRic)=1cRix
(28)

Utilizing Equation (17), we may write

Rix=12(2(xxi)Ri)=(xxi)Ri
(29)

Substituting the result in Equation (28) yields

eix=1c(xxi)Ri
(30)

Substituting in Equation (27), we get

Jx=1ci=1NBS1σi22ei (xxi)Ri=2c2i=1NBS1σi2 (Rili)(xxi)Ri
(31)

The above steps starting with Equation (27) can be repeated for ∂J/∂y in a straightforward manner. Finally, by setting the gradient of J with respect to Θ to zero, we get the two ML equations

i=1NBS1σi2 (Rili)(xxi)Ri=0i=1NBS1σi2 (Rili)(yyi)Ri=0
(32)

The above equations can be expressed in matrix notation as

2[gixigiyihixihixi][xy]=[gi(s+Kili2)hi(s+Kili2)]
(33)

where

gi=xxiσi2Ri(Ri+li)
(36)
hi=yyiσi2Ri(Ri+li)
(37)

In a more compact form, Equation (34) can be re-written as

AΘ = b

(38)

with the matrix A and vector b being functions of Θ. A suboptimal solution based on a linear model (Chan & Ho, 1994) can be used as a first initial estimate of Θ, which will in turn give starting values of A and b. Then, solving Equation (33) produces a new value of Θ to update A and b, and subsequently Θ. This iterative procedure first gives an approximate maximum likelihood (AML) estimator, which can then be iterated a number of times to obtain a final solution. The final solution takes the Θ that gives the smallest J in Equation (26). This ensures that the AML will not diverge. In fact, simulation results presented in (Chan et al., 2006) show that the AML can nearly achieve the Cramer–Rao lower bound (CRLB) with a small number of iterations (typically on the order of five updates are found to be sufficient). It should be noted that, for the special case of equal measurement variance assumption (as in the original AML), the common σ term drops from Equation (32). However, with the modified AML in Equation (33), the quantities gi and hi will be different for different BSs, and this is found to yield some improvement in performance as will be discussed next.

5.2. Positioning Accuracy with the Modified AML Algorithm

To illustrate the impact of the modified AML that takes into account the unequal error variances, we consider an example of three BSs with different measurement error statistics for mobiles located in three different regions, as described in the different cases of Section 3. Figure 9 shows the geometry of the layout used for this purpose, where distances are shown in meters. The dense scatter points represents a total of 105 noisy mobile locations generated according to the TOA statistics for the different cases of interest which are referred to as MS1, MS2, MS3, corresponding to mobiles classified in Section 3 as Case 1, 2, and 3, respectively. For each mobile location, the AML and modified AML algorithms are executed to obtain the estimated mobile coordinates, and by comparing with the known mobile position, the resulting positioning error can be computed. The different parameters for the radio channel and relative received power factors used are based on the results given in Table 1 of Section 3.

media/image49.png

Figure 9.

Layout of the mobile localization geometry used to test the accuracy of the AML algorithm.

Various aspects of mobile positioning performance are illustrated in Figure 10 based on the cumulative distribution function (CDF) of the radiolocation error. First, it can be seen that the modified AML which takes into account the differences in TOA noise statistics at the various base stations (as proposed in this work) outperforms, albeit slightly, the conventional AML which assumes equal TOA noise variance at all base stations. This is more pronounced for mobiles categorized as MS1 (i.e., which are in close proximity to their home base stations). The other major observation from Figure 10 is that a large difference in radiolocation accuracy is present depending on the mobile relative position with respect to the base stations. It is clearly seen that MS2 and particularly MS3 mobiles, corresponding to mobiles in 2-way and 3-way soft handoff, respectively, achieve much better performance as opposed to MS1. This is due to the poor TOA accuracy at BS2 and BS3 for the latter case, owing to the overwhelming near-far interference experienced by the mobile at the remote bases stations, as discussed in Section 4. As an example, the probability of the residual positioning error being less than 20m is almost one for MS3 mobiles, while it is on the order of 70% for MS2, and only 50% for MS1–type mobiles. Similar observations also hold for other distances. Therefore, as highlighted throughout this study, the accuracy of mobile positioning is best when the mobile is in close proximity to a border cell region where soft handoff connectivity is established with one or two more cells involved in its positioning in addition to its home serving cell.

media/image50.png

Figure 10.

Illustration of mobile positioning accuracy with the Approximate Maximum Likelihood Algorithm.

6. Conclusion

This study dealt with the performance analysis of time-of-arrival (TOA) techniques for mobile positioning in CDMA wireless cellular networks. Since several base stations are typically needed for mobile radiolocation, the problem of weak signal hearability at remote base stations is a major challenge, and a detailed analysis of this issue was presented by taking into account the near-far interference usually present in CDMA cellular networks.

TOA-based positioning methods are well-suited for wide deployment of radiolocation services since the synchronization circuits that can extract timing information are readily available at the base stations receiving the mobile signal. For CDMA signals, the delay-locked loop (DLL) is commonly used as a TOA estimation device, and a detailed analysis of DLL-based TOA tracking was presented taking into account the cellular network layout, cell loading and other-user interference, as well as RF channel shadowing and pathloss that affect received signal strength at the different base stations. In particular, it was shown that the TOA tracking error statistics can vary considerably depending on the mobile link conditions with respect to the base stations involved in its positioning, and soft handoff (SHO) links with two or three base stations for mobiles close to border-cell regions were found to improve the precision of mobile TOA tracking.

Using TOA information, a mobile radiolocation positioning algorithm based on a computationally-efficient, near-optimum approximate maximum likelihood (AML) processing was presented, and a generalization to the case of unequal timing error variances at the different base stations was also derived. Numerical results were presented to quantify the achievable positioning accuracy of the AML algorithms, and it was also shown that SHO radio links with two or particularly three base stations have a clear impact on the precision of mobile radiolocation. Finally, it should be noted that the problem of non-line-of-sight (NLOS) propagation, which constitutes another major challenge to mobile positioning accuracy, was not included in this study, and would be addressed in future work.

7. Acknowledgements

This work was gratefully supported by King Abdulaziz City for Science & Technology and King Fahd University of Petroleum & Minerals, Saudi Arabia.

References

1 - J. J. Caffrey, 1999 Wireless Location in CDMA Cellular Radio Systems. Kluwer Academic Publishers.
2 - J. J. Caffrey, G. L. Stuber, 2000 Effects of multiple access interference on the non-coherent delay lock loop. IEEE Transactions on Communications, 48 (December 2000) 2109-2119.
3 - Y. Chan-T, H. Hang, P. Ching-C, 2006 Exact and approximate maximum likelihood localization algorithms. IEEE Transactions on Vehicular Technology, 55 1 (January 2006) 10 16 .
4 - Y. T. Chan, K. C. Ho, 1994 A simple and efficient estimator for hyperbolic location. IEEE Transactions on Signal Processing, 42 8 (August 1994) 1905 1915 .
5 - Y. T. Chan, C. H. Yau, P. C. Ching, 2006 Exact and approximate maximum likelihood localization algorithms. IEEE Transactions on Vehicular Technology, 55 1 (January 2006) 10 16 .
6 - E. Dahlman, B. Gudmundson, M. Nilsson, A. Skold, 2000 UMTS/IMT-2000 based on wideband CDMA. IEEE Communications Magazine, (September 2000) 70 -80.
7 - A. Gosh, R. Love, 1998 Mobile station location in a DS-CDMA system, Proceedings of IEEE VTC, 1 254 258 .
8 - E. Kaplan, 1996 Understanding GPS: Principles and Applications. Norwood, MA: Artech House.
9 - H. R. Khan, 2009 DLL Code Tracking for CDMA Signals under Fading and Multiple Access Interference, M.S. Thesis, King Fahd University of Petroleum & Minerals, February 2009.
10 - G. H. Niezgoda, K. C. Ho, 1994 Geolocation by combined range difference and range rate measurements, Proceedings of International Conference Acoustics, Speech, Signal Process (ICASSP’94), Adelaide, Australia, 2 1994, 357 360 .
11 - T. Rappaport, J. Reed, B. Worner, 1996 Position location using wireless communications on highways of the future. IEEE Communications Magazine , (October 1996) 33 41 .
12 - A. H. Sayed, A. Tarighat, N. Khajehnouri, 2005 Network-Based Wireless Location. IEEE Signal Processing Magazine, (July 2005) 24 40 .
13 - S. L. Su, N. Y. Yen, 1997 Performance of digital code tracking loops for direct-sequence spread-spectrum signals in mobile radio channels. IEEE Transactions on Communications , 45 (May 1997) 596 604 .
14 - H. L. V. Trees, 1968 Detection, Estimation, and Modulation Theory: Part 1, Wiley, New York.
15 - A. J. Viterbi, 1995 CDMA: Principles of Spread Spectrum Communication, Addison-Wesley.