Relative received power factors for various mobile soft-handoff link conditions. Shadowing s.t.d
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
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
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.
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.
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
For wireless fading channels, the received signal at the output of the radio frequency (RF) receiver filter is written as
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.
The mobile received power at a given base station, BSi, is multiplied by an attenuation factor,
The path-loss factor is assumed to follow the model:
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:
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,
Table 1 and Table 2 give the different
|Case 1 (mobile close to home BS)||1||0.0216||0.0113||0.0069||0.0045||0.0031||0.0021|
|Case 2 (mobile in two-way SHO)||1||0.6982||0.2215||0.1202||0.0735||0.0485||0.0331|
|Case 3 (mobile in three-way SHO)||1||0.7922||0.6353||0.2993||0.1701||0.1065||0.0706|
|Case 1 (mobile close to home BS)||1||0.0248||0.0125||0.0072||0.0045||0.0030||0.0020|
|Case 2 (mobile in two-way SHO)||1||0.7000||0.2281||0.1258||0.0761||0.0486||0.0322|
|Case 3 (mobile in three-way SHO)||1||0.7985||0.6443||0.3403||0.1953||0.1252||0.0808|
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)
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):
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
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:
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).
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
where NBS is the number of involved BSs. The measured distances, li, is given by
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
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
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:
The conditional probability density function (PDF) of T given Θ is given by
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
By expressing the timing error in terms of the difference between the true TOA and measured one, this gives
Utilizing Equation (17), we may write
Substituting the result in Equation (28) yields
Substituting in Equation (27), we get
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
The above equations can be expressed in matrix notation as
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.
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.
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.
This work was gratefully supported by King Abdulaziz City for Science & Technology and King Fahd University of Petroleum & Minerals, Saudi Arabia.
Caffrey J. J. 1999Wireless Location in CDMA Cellular Radio Systems. Kluwer Academic Publishers.
Caffrey J. J. Stuber G. L. 2000Effects of multiple access interference on the non-coherent delay lock loop. , 48(December 2000) 2109-2119.
Chan-T Y. Hang H. Ching-C P. 2006 Exact and approximate maximum likelihood localization algorithms. , 55 1(January 2006) 10 16.
Chan Y. T. Ho K. C. 1994 A simple and efficient estimator for hyperbolic location. , 42 8(August 1994) 1905 1915.
Chan Y. T. Yau C. H. Ching P. C. 2006 Exact and approximate maximum likelihood localization algorithms. , 55 1(January 2006) 10 16.
Dahlman E. Gudmundson B. Nilsson M. Skold A. 2000UMTS/IMT-2000 based on wideband CDMA. , (September 2000) 70 -80.
Gosh A. Love R. 1998Mobile station location in a DS-CDMA system, , 1 254 258.
Kaplan E. 1996 Understanding GPS: Principles and Applications.Norwood, MA: Artech House.
Khan H. R. 2009DLL Code Tracking for CDMA Signals under Fading and Multiple Access Interference, M.S. Thesis, King Fahd University of Petroleum & Minerals, February 2009.
Niezgoda G. H. Ho K. C. 1994Geolocation by combined range difference and range rate measurements, Process (’94), Adelaide, Australia, 21994, 357 360.
Rappaport T. Reed J. Worner B. 1996 Position location using wireless communications on highways of the future. , (October 1996) 33 41.
Sayed A. H. Tarighat A. Khajehnouri N. 2005 Network-Based Wireless Location. , (July 2005) 24 40.
Su S. L. Yen N. Y. 1997 Performance of digital code tracking loops for direct-sequence spread-spectrum signals in mobile radio channels. , 45(May 1997) 596 604.
Trees H. L. V. 1968 Detection, Estimation, and Modulation Theory: Part 1, Wiley, New York.
Viterbi A. J. 1995 CDMA: Principles of Spread Spectrum Communication,Addison-Wesley.