NLOS Identification and Weighted Least-Squares Localization for UWB Systems Using Multipath Channel Statistics

Abstract

Non-line-of-sight (NLOS) identification and mitigation carry significant importance in wireless localization systems. In this paper, we propose a novel NLOS identification technique based on the multipath channel statistics such as the kurtosis, the mean excess delay spread, and the root-mean-square delay spread. In particular, the IEEE 802.15.4a ultrawideband channel models are used as examples and the above statistics are found to be well modeled by log-normal random variables. Subsequently, a joint likelihood ratio test is developed for line-of-sight (LOS) or NLOS identification. Three different weighted least-squares (WLSs) localization techniques that exploit the statistics of multipath components (MPCs) are analyzed. The basic idea behind the proposed WLS approaches is that smaller weights are given to the measurements which are likely to be biased (based on the MPC information), as opposed to variance-based WLS techniques in the literature. Accuracy gains with respect to the conventional least-squares algorithm are demonstrated via Monte-Carlo simulations and verified by theoretical derivations.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Recommended by Richard J. Barton

DoCoMo Communications Laboratories USA, Inc., 3240 Hillview Avenue, Palo Alto, CA 94304, USA

Received 30 March 2007; Revised 6 July 2007; Accepted 21 July 2007

1. Introduction

The location of a mobile terminal (MT) can be estimated using different parameters of a received signal, such as the time-of-arrival (TOA), angle-of-arrival (AOA), and/or the received signal strength (RSS). Ultrawideband (UWB) radio has a great potential for accurate ranging and localization systems due to its very wide bandwidth and capability in resolving individual multipath components (MPCs) [1-7]. Therefore, the TOA of the received signal can be estimated with high accuracy for UWB systems if the first arriving path has been identified precisely [8-11]. One of the major challenges for localization systems is the mitigation of non-line-of-sight (NLOS) effects. If the direct path between a fixed terminal (FT) (An FT is usually a base station in a cellular network or an anchor node in a sensor network.) and the MT is being obstructed, the TOA of the signal to the FT will be delayed, which introduces a positive bias. Using such NLOS TOA estimates during the localization of the MT position may significantly degrade the positioning accuracy. Hence, FTs that are under the NLOS condition have to be identified and their effects have to be mitigated.

The NLOS identification and mitigation techniques have been discussed extensively in the literature, but mainly within the cellular network framework [12-14]. For example, in [12], the standard deviation of the range measurements are compared with the threshold for NLOS identification, where the measurement noise variance is assumed to be known. In [13], a decision-theoretic NLOS identification framework is presented, where various hypothesis tests are developed for known and unknown probability density functions (PDFs) of the TOA measurements. A nonparametric NLOS identification approach is discussed in [14, 15], where a suitable distance metric is used between the known measurement error distribution and the nonparametrically estimated distance measurement distribution in order to determine if a given FT is line-of-sight (LOS) or NLOS. Note that such techniques usually assume that the MT is moving and the number/density of obstructions between the MT and the FT vary. This implies that the bias for the NLOS range measurements change over time and have larger variances. On the other hand, when the MT is static, the variance of the NLOS range measurements may not show as much deviation from the variance of the LOS range measurements [16]. In such situations, the multipath characteristics of the received signal may provide some insight regarding the LOS/NLOS identification. For example, in [17], the NLOS identification for UWB systems was briefly addressed by comparing the normalized strongest path with a fixed threshold. However, for such a scheme, optimal selection of certain parameters such as the threshold and the time interval are essential.

As an alternative to identify the NLOS scenarios from the received multipath signal, it is also possible to use the information from the overall mobile network for NLOS mitigation, provided that there are sufficient number of LOS FTs. For example, in [18], a residual-based algorithm was proposed for NLOS mitigation by assuming that the number of available FTs are more than three.

When all the FTs are LOS, three FTs are sufficient for two-dimensional (2D) localization, and four FTs are sufficient for 3D localization.

Different combinations of FTs with at least three FTs in each combination are considered in order to evaluate the MT location and the corresponding residual error. The location estimates with smaller residuals have larger chances of corresponding to the correct MT location. Hence, the proposed technique weights different location estimates with the inverses of their residual errors. Some other NLOS mitigation techniques using the mobile network are reported in [19-27].

The objectives of this paper are three-fold. First, to model and characterize the amplitude and delay statistics of IEEE 802.15.4a channels. Second, to propose NLOS identification techniques based on the amplitude and delay statistics of the UWB channels. The amplitude statistics are captured using the kurtosis, and the delay statistics are evaluated using the mean excess delay and the root mean square (rms) delay spread of the received MPCs. And third, to analyze different weighted least-squares (WLS) localization techniques and evaluate their performance via Monte-Carlo simulations using the IEEE 802.15.4a channel model. The paper is organized as follows. In Section 2, the UWB channel model and associated channel statistics to be used in NLOS identification are outlined, and the localization system model is briefly reviewed. Section 3 introduces three different NLOS identification techniques based the statistics of the MPCs, while Section 4 introduces three different WLS localization techniques. Simulation results are presented in Section 5 and finally Section 6 provides some concluding remarks.

2. Channel and System Models

2.1. Multipath Channel Statistics

Let the channel impulse response (CIR) of the received signal be represented as [figure omitted; refer to PDF] where L is the total number of MPCs, and _αl and _τl are the amplitude and delay of the l th MPC, respectively. The TOA of the received signal is given by _τtoa =_τ1 , which is identified by the first arriving path. If _τ1 can be accurately estimated, the true distance d between the FT and the MT can be easily calculated for LOS scenarios. However, for NLOS scenarios, the distance estimate may typically include a positive NLOS bias. There may be two major reasons for the existence of such a bias: while the first path may be completely blocked and cannot be detected at the receiver, it may also be the case that it is being delayed due to experiencing a different propagation speed through the obstacles [28, 29]. For the second scenario, the delay of the first arriving path may be negligible for certain NLOS channels, which implies close to zero bias. In this paper, we assume that NLOS channels introduce considerable bias to the first arriving path. In other words, we have [figure omitted; refer to PDF] where c denotes the speed of light, _H0 is the LOS hypothesis, and _H1 is the NLOS hypothesis. Hence, for NLOS situations, even if the first arriving path is correctly identified, the estimated distance is larger than the actual distance between the FT and the MT due to the always present positive bias. Therefore, if NLOS FTs are used in localization, they will degrade the localization accuracy, and it is essential to identify the NLOS FTs and mitigate their effects for accurate localization.

The impact of NLOS bias may be different for a moving MT and a stationary MT as illustrated in Figure 1. As the MT-1 moves through the network, the LOS and NLOS condition changes intermittently. For example, at _t1 , MT-1 is under LOS condition with FT₁ , FT₄ , and FT₅ while it is under NLOS condition with other FTs. Similarly, at other time instants MT-1 will be under LOS and NLOS with some other FTs. As the MT-1 moves through the network, the intensity of obstacles for a NLOS FT will change which will effectively vary the NLOS bias. Hence, for a moving MT, the variance of the distance estimate to a NLOS FT will be larger due to the changes in the NLOS bias. On the other hand, for a stationary MT such as the MT-2, the NLOS bias is fixed over time as opposed to a moving MT. Hence, observing the variance of distance estimates may not provide sufficient information whether a stationary MT is under LOS or NLOS condition. Moreover, for indoor scenarios, the MT may move significantly prior to detecting if it is under LOS or NLOS scenario, and hence, a NLOS mitigation/localization based on the variance of the distance estimate may become quite complicated.

Figure 1: A simple scenario where there are six FTs (denoted with stars) and two MTs (denoted with circles). The environment is occupied with some obstructions (e.g., buildings, foliage, etc.). The MT-1 moves through the network while the MT-2 is stationary.

[figure omitted; refer to PDF]

In this paper, we distinguish between the LOS or NLOS scenarios by exploiting the statistics of the received MPCs. The kurtosis, the mean excess delay, and the rms delay spread are used in order to capture the amplitude and delay statistics for the LOS and NLOS scenarios, respectively. The kurtosis of a certain data is defined as the ratio of the fourth-order moment of the data to the square of the second-order moment (i.e., the variance) of the data. As stated in [30], the "kurtosis characterizes how peaky" a sample data. Thus, it may be used as a tool to characterize the level of LOS condition of a certain channel. This implies that for a CIR with high kurtosis values, it is more likely that the received signal is under LOS scenario. Given a certain channel realization h(t) , kurtosis of |h(t)| can be calculated as [30] [figure omitted; refer to PDF] where _μ|h| and _σ|h| are the mean and standard deviation of the |h(t)| , respectively.

While the kurtosis provides information about the amplitude statistics of the received MPCs, it does not provide any information regarding the delay properties of the received MPCs. Two important statistics that characterize the delay information of the multipath channel are the mean excess delay _τm and the rms delay spread _τrms , which are given by [31] [figure omitted; refer to PDF]

2.2. Localization System Model

For the localization system model, we consider a wireless network where there are N FTs, x^=^{[x^ y^]T} is the estimate of the MT location, _xi =^{[_{xi yi} ]T} is the position of the i th FT, _d^i is the measured distance between the MT and the i th FT commonly modeled as [figure omitted; refer to PDF] where _τi is the TOA of the signal at the i th FT, _di is the actual distance between the MT and the i th FT, _ni ~...A9;(0,^σi2 ) is the additive white Gaussian noise (AWGN) with variance ^σi2 , and _bi is a positive distance bias introduced due to LOS blockage, given by [figure omitted; refer to PDF] For NLOS FTs, the bias term _ψi was modeled in different ways in the literature such as exponentially distributed [18, 32], uniformly distributed [27, 33], Gaussian distributed [34], constant along a time window [21], or based on an empirical model from measurements [29, 35]. Typically, the model depends on the wireless propagation channel and the specific technology under consideration (e.g., cellular networks, wireless sensor networks, etc.). In this paper, we will model the term _bi as an exponentially distributed random variable with mean _λi based on [18, 32].

Once all the distance estimates in (5) are available, the noisy measurements and NLOS bias at different FTs yield circles which do not intersect at the same point, resulting in the following inconsistent equations: [figure omitted; refer to PDF]

3. LOS/NLOS Identification

3.1. Kurtosis of the Multipath Channel

The PDF of the kurtosis of the multipath channel κ can be obtained for both LOS and NLOS scenarios using sample channel realizations from both scenarios. Here, we used sample channel realizations of the IEEE 802.15.4a standard channel models in order to obtain the histograms of κ for eight different channel models (i.e., CM1 through CM8) as defined in [7]. It is found that the histograms can be well modeled by a log-normal distribution given as follows: [figure omitted; refer to PDF] where _μκ is the mean and _σκ is the standard deviation of In(κ) . The corresponding parameters for the eight different channel models are tabulated in Table 1. We also used the Kolmogorov-Smirnov (K-S) goodness-of-fit hypothesis test at 5% significance level to analyze how well the log-normal PDF characterizes the data. Table 1 also shows the passing rates of the K-S test for all the channel models. From the table, it shows that the log-normal distribution fits well to the kurtosis of the data for all channel models with more than 90% of passing rates.

Table 1: The mean and the standard deviation of the log-normal PDF for the kurtosis of the IEEE 802.15.4a channels.

Channel model	μκ	σκ	K-Sκ
CM1 (residential LOS)	4.6631	0.5770	95.4%
CM2 (residential NLOS)	3.6697	0.4886	94.6%
CM3 (indoor office LOS)	4.4744	0.4579	95.7%
CM4 (indoor office NLOS)	2.8154	0.3459	95.5%
CM5 (outdoor LOS)	4.4509	0.5163	95.5%
CM6 (outdoor NLOS)	4.8886	0.4497	95.5%
CM7 (industrial LOS)	4.2637	0.7447	95.6%
CM8 (industrial NLOS)	2.1141	0.1487	95.4%

The log-normal PDFs of the kurtosis for the eight channel models are depicted in Figure 2. It can be seen that for indoor residential, indoor office, and industrial environments, kurtosis can provide good information regarding if the received signal is LOS or NLOS. However, for outdoor environment, the PDFs are not distinct, and interestingly, the mean of the NLOS case is larger then the mean of the LOS case. A possible reason why the amplitude statistics is insufficient to identify the LOS/NLOS scenarios might be due to the highly dispersive characteristics of the outdoor environments [7]. Therefore, in order to have a more robust identifier, the delay statistics must be taken into consideration as will be discussed in the next section.

Log-normal PDFs of the kurtosis for CM1 to CM8 of the IEEE 802.15.4a channel models.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

3.2. Mean Excess Delay and rms Delay Spread of the Multipath Channel

Similar to the kurtosis analysis as discussed in the previous section, we obtained the histograms of the mean excess delay and rms delay spread for eight different channel models from the IEEE 802.15.4a channels. We also found that the log-normal distribution fits to the histograms well. This observation was further verified using the K-S hypothesis test with 5% of significance level. The mean and standard deviation of In(_τm ) and In(_τrms ) as well as the K-S passing rates are tabulated in Table 2, and their corresponding PDFs are depicted in Figures 3 and 4. We observe that as opposed to residential and indoor-office environments, the LOS and NLOS PDFs in outdoor and industrial environments are quite distinct, which implies reliability of the LOS/NLOS identification.

Table 2: The log-normal pdf parameters for the mean excess delay and the rms delay spread of the IEEE 802.15.4a channels.

	Maximum excess delay	rms delay spread
Channel model	μm [ns]	σm [ns]	K-Sm	μrms [ns]	σrms [ns]	K-Srms
CM1 (LOS)	2.6685	0.4837	95.7%	2.7676	0.3129	94.8%
CM2 (NLOS)	3.3003	0.3843	95.8%	2.9278	0.1772	95.2%
CM3 (LOS)	2.0993	0.3931	96.2%	2.2491	0.3597	96.2%
CM4 (NLOS)	2.7756	0.1770	95.3%	2.5665	0.1099	95.4%
CM5 (LOS)	3.0864	0.4433	94.6%	3.3063	0.2838	94.6%
CM6 (NLOS)	4.6695	0.4185	94.9%	4.2967	0.3742	95.7%
CM7 (LOS)	1.3845	0.9830	98.9%	1.9409	0.7305	93.9%
CM8 (NLOS)	4.7356	0.0225	94.7%	4.4872	0.0164	95.9%

Log-normal PDFs of the mean excess delay and rms delay spread of CM1-CM4 of the IEEE 802.15.4a channels.

(a) Mean excess delay spread (ns)

[figure omitted; refer to PDF]

(b) rms delay spread (ns )

[figure omitted; refer to PDF]

Log-normal PDFs of the mean excess delay and rms delay spread of CM5-CM8 of the IEEE 802.15.4a channels.

(a) Mean excess delay spread (ns)

[figure omitted; refer to PDF]

(b) rms delay spread (ns)

[figure omitted; refer to PDF]

3.3. Likelihood-Ratio Test

If the a priori knowledge of the statistics of κ,_τm , and _τrms are available under the LOS and NLOS scenarios in a certain environment, likelihood ratio tests can be performed for hypothesis selection. Let ^Ploskurt (κ),^Pnloskurt (κ),^Plosmed (_τm ),^Pnlosmed (_τm ),^Plosrms-ds (_τrms ) , and ^Pnlosrms-ds (_τrms ) be the PDFs of the kurtosis, the mean excess delay spread, and the rms delay spread corresponding to LOS and NLOS conditions, respectively. Then, given a channel realization h(t) , we may consider the following three likelihood ratio tests for LOS/NLOS identification of h(t) :

(1) kurtosis test: [figure omitted; refer to PDF]

(2) mean excess delay test: [figure omitted; refer to PDF]

(3) rms delay spread test: [figure omitted; refer to PDF]

where, if the likelihood ratio is larger than 1, we choose the LOS hypothesis (_H0 ) , and if otherwise, we choose the NLOS hypothesis (_H1 ) .

Rather than using only the PDFs of individual parameters, a better approach would be to consider the joint PDF of these parameters, which will yield [figure omitted; refer to PDF] Since in practice it is very difficult to obtain the joint PDFs as given in (12), a suboptimal approach is proposed by considering κ,_τm , and _τrms as independent to each other. Note that in practice, there is some correlation between these random variables, and independence assumption will not usually hold. In order to assess the amount of correlation between these random variables, we calculated the correlation coefficients

Correlation coefficient between two random variables _R1 and _R2 is given by _{ρR1 ,R2} =(E(_{R1 R2} )-E(_R1 )E(_R2 ))/_σR1σR2 , where _σR1 and _σR2 are the standard deviations of _R1 and _R2 , respectively.

between the pairs of random variables as tabulated in Table 3 for 1000 channel realizations from each of the IEEE 802.15.4a channel models. We also obtained the correlation coefficient between the strongest path (SP) energy (normalized with the total received energy) and each of the κ,_τm , and _τrms for comparison purposes. While the correlation coefficients are usually low for most channel models, relatively larger values of _{ρτm ,τrms} and _ρsp,κ for certain channel models are noticeable. Results in Table 3 imply that while there is some correlation between some of these parameters, a suboptimal detector that considers these parameters independently may still improve the NLOS detection performance since the correlation tends to be smaller than 0.5 for most of the channel models. Then, (12) can be simplified to [figure omitted; refer to PDF] where [figure omitted; refer to PDF] The histogram of the logarithm of J(κ,_τm ,_τrms ) is depicted in Figure 5(a) for CM3 and CM4 of the IEEE 802.15.4a channels, and Figure 5(b) shows the histogram of _{log 10} (1+J(κ,_τm ,_τrms )) . While J(κ,_τm ,_τrms ) can be used to make a hard decision to decide if a received signal is LOS or NLOS, it may also be used as a soft information in the WLS algorithm as will be discussed in the next section.

Table 3: Correlation coefficients of different channel parameters.

Channel model	ρκ,τm	ρκ,τrms	ρτm ,τrms	ρsp,τm	ρsp,τm	ρsp,τrms
CM1 (LOS)	-0.45	-0.06	0.70	0.96	-0.42	-0.02
CM2 (NLOS)	-0.34	-0.20	0.37	0.95	-0.33	-0.17
CM3 (LOS)	-0.33	-0.02	0.71	0.91	-0.32	-0.04
CM4 (NLOS)	-0.35	0.03	0.50	0.93	-0.29	0.01
CM5 (LOS)	-0.31	0.06	0.57	0.94	-0.27	0.05
CM6 (NLOS)	-0.21	-0.04	0.39	0.93	-0.20	-0.05
CM7 (LOS)	-0.53	-0.26	0.72	0.95	-0.54	-0.25
CM8 (NLOS)	-0.30	-0.26	0.40	0.90	-0.23	-0.21

LOS/NLOS metrics used for WLS algorithms.

(a) The logarithm of the likelihood metric J(κ,_τm ,_τrms ) for CM3 and CM4 of the IEEE 802.15.4a channels

[figure omitted; refer to PDF]

(b) SWS weights obtained upon modifying J(κ,_τm ,_τrms )

[figure omitted; refer to PDF]

4. WLS Localization Techniques

The NLOS information as discussed in the previous section can be used in numerous ways to improve the localization accuracy. In this section, we will present different WLS techniques in order to mitigate the NLOS effects. By considering the localization model presented in Section 2.2, a WLS estimate of the MT location using all the FTs can be expressed as [32, 36] [figure omitted; refer to PDF] where the weights _βi can be chosen to reflect the reliability of the signal received at i th FT.

Minimizing (15) requires numerical search methods such as steepest descent or Gauss-Newton techniques, which require good initialization in order to avoid converging to the local minima of the loss function [37]. Alternatively, it is possible to use the techniques as proposed in [27, 38] in order to obtain a linear set of equations from the nonlinear least-squares model in (15). If the nonlinear set of equations is given as in (7), by fixing one of the expressions for a particular FT and after some mathematical manipulation, we have the following linear model: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] [figure omitted; refer to PDF] with W=diag(_β1 ,_β2 ,...,_βN-1 ) being a diagonal matrix of size (N-1) , and r is the FT chosen in order to obtain the linear model.

Note that it is important to assure that FT r is selected appropriately because otherwise it will introduce bias in all the equations.

Therefore, the WLS solution is given by [figure omitted; refer to PDF] The mean square error (MSE) of the WLS solution in (19) is derived for LOS and NLOS FTs in Appendix A and Appendix B, respectively. Note that the WLS solution corresponds to the minimization of the following cost function: [figure omitted; refer to PDF]

For the mitigation of NLOS effects, it is critical to select _βi appropriately. In [32, 36], the authors use the inverse of the measured distances variance as a reliability metric for the i th FT, which corresponds to the maximum likelihood solution for Gaussian distributed and independent noise terms. However, for a static MT, the variance of the TOA measurements may not be significantly different for LOS and NLOS FTs as discussed in Section 2. Still, due to the biased observations at the NLOS FTs, the localization accuracy degrades when the conventional LS technique is used. As discussed in previous section, the MPCs of the received signal carries important information regarding the LOS/NLOS characteristics. In this paper, we deploy such information to develop different alternative WLS localization techniques. Comparison of the prior art WLS and proposed WLS techniques are summarized in Figure 6. Note that optimization of the weights _βi conditioned on the NLOS bias statistics and the LOS/NLOS likelihood functions is nontrivial in closed-form and is not part of the work to be discussed in this paper. Instead, we propose three different heuristic techniques for the selection of these weights, and show via simulations that the LS localization accuracy can be improved under NLOS scenario by deploying the information in the MPCs of the received signal.

Figure 6: Comparison between the commonly used prior art (distance variance estimation) and proposed WLS techniques for NLOS mitigation.

[figure omitted; refer to PDF]

4.1. Identify-and-Discard

As discussed in [39], if no prior knowledge regarding the NLOS bias _bi is available, the Cramer-Rao lower bound (CRLB) is minimized by discarding the NLOS FTs (assuming perfect identification of LOS/NLOS measurements). In here, we refer this technique as identify-and-discard (IAD), and the weights _βi for the i th measurement are given as follows: [figure omitted; refer to PDF] The drawback of IAD is that there is always the chance of misidentification (i.e., selecting an LOS FT as NLOS, or vice versa). Hence, in certain cases, there may be insufficient number of identified LOS FTs to estimate the MT location, which may considerably degrade the location accuracy. For example, if there are only two LOS FTs, this corresponds to two circles which intersect at two different points, resulting in an ambiguity of the MT location. In this paper, we randomly select one of the two intersection points for resolving the ambiguity for the two LOS FT case. On the other hand, if only one LOS FT can be identified, the best case with IAD would be to select the location of the LOS FT as the MT location.

4.2. Soft Weight Selection

While IAD minimizes the CRLB in ideal scenarios, in practice, discarding the NLOS measurements requires perfect knowledge of the LOS/NLOS situation. Moreover, it has been well reported in the literature that exploiting the NLOS information may improve the localization accuracy in more practical estimators such as the LS estimator [27]. Thus, instead of discarding the NLOS measurements, the likelihood functions given in Section 3.3 can be used to minimize the contribution of NLOS FTs to the residual error as given in (15). We may use a modified version of the likelihood ratios in (13) for a soft weight selection (SWS) where the weights for the i th measurement is given as follows: [figure omitted; refer to PDF] which penalizes the NLOS nodes by typically assigning them weights between 0 and 1 (see Figure 5(b)). The drawback of such an approach is that for LOS nodes, the dynamic range of weights may become very large as evident in Figure 5. This unnecessarily favors some of the LOS measurements with respect to others which may degrade the positioning accuracy.

4.3. Hard Weight Selection

We may improve the performance of SWS by assigning fixed weights to LOS and NLOS measurements, that is, by using hard weight selection (HWS). Based on this approach, _βi can be set as [figure omitted; refer to PDF] where ^k1(1) <^k2(1) . In other words, the identified NLOS FTs have limited impact on the WLS solution. When ^k1(1) =0,^k2(1) =1 , HWS1 becomes identical to the IAD.

Note that there exists an ambiguity region for the likelihood functions as shown in Figure 5(a) where a given likelihood value may correspond to both LOS or NLOS FT. Hence, an alternative HWS technique that partitions the likelihood space into three different regions can be obtained as follows: [figure omitted; refer to PDF] where ^k1(2) <^k2(2) <^k3(2) , the parameters ^k1(2) and ^k3(2) are the weights for the NLOS and LOS measurements, respectively, and ^k2(2) is the weight for the ambiguity region when the likelihood value falls in between _Δ1 and _Δ2 . For the special case when _Δ1 =_Δ2 =0 , HWS2 is equivalent to HWS1.

5. Simulation Results

Monte-Carlo simulations are performed to validate the proposed LOS/NLOS identification technique and the WLS algorithms using the IEEE 802.15.4a channel models. For each of the CM1 to CM8 channels, 1000 channel realizations are generated with channel separation of 494 MHz, central and sampling frequencies of 3.952 GHz, with an over-sampling factor of 8.

5.1. LOS/NLOS Identification Results

For each channel realization, we apply the likelihood ratio tests given in (9)-(13) and calculate the percentage of correctly identified cases. Table 4 tabulates both LOS and NLOS identification percentages using the four different techniques. It can be seen that using individual metrics may yield high identification percentage only for certain channel models (depending on the amplitude and delay characteristics of the channel under consideration), while the joint approach achieves high identification percentage for most of the channel models.

Table 4: LOS/NLOS identification percentages.

Channel model	κ	τm	τrms	Joint (κ,τm ,τrms )	SP-TC (ξ=0.05)	SP-TC (ξ=0.1)	SP-TC (ξ=0.2)
CM1 (LOS)	78.6%	74.3%	61.7%	81.8%	99.6%	75.5%	24.9%
CM2 (NLOS)	83.2%	77.9%	76.1%	84.3%	25.3%	78.1%	99.1%
CM3 (LOS)	99.0%	88.5%	73.6%	97.9%	98.7%	63.9%	11.5%
CM4 (NLOS)	96.7%	86.3%	89.0%	95.9%	56.2%	96%	99.9%
CM5 (LOS)	66.3%	98.2%	93.9%	98.9%	95.5%	48.2%	9.1%
CM6 (NLOS)	71.4%	95.2%	92.7%	97.8%	20.1%	80.7%	98.3%
CM7 (LOS)	98.3%	88.3%	98.3%	88.2%	95.9%	79%	37%
CM8 (NLOS)	98.4%	100%	100%	99.9%	100%	100%	100%

For comparison purposes, we also included the simulation results for the technique introduced in [17], which we refer here as strongest-path threshold-comparison (SP-TC). In summary, the NLOS identification is achieved by [figure omitted; refer to PDF] where 0≤ξ≤1 is a threshold set on the normalized strongest path. As shown in Table 4, the selection of the threshold is critical for balanced identification rates for the LOS and NLOS channels. Even with a reasonable threshold setting (e.g., ξ=0.1 ), identification rates for the joint approach are better than the SP-TC for most channel realizations.

5.2. WLS Localization Results

In order to test the performance of the WLS algorithm, we consider a rectangular room of size 30 m×20 m . The MT is centered at the middle of the room at [x,y]=(0,0) m, and two topologies for the placement of the FTs are considered. For topology-1, six FTs are placed at the borders of the room with _x1 =[-16,-10], _x2 =[14,-9],_x3 =[-15.5,11],_x4 =[15,9.5],_x5 =[0.5,-11] , and _x6 =[-0.5,10] (all in meters). For topology-2, FTs are placed in a hexagon-like structure with _x1 =[-7.5,-10.5],_x2 =[7,-10],_x3 =[-15.5,0.5],_x4 =[15,0],_x5 =[-8,11] , and _x6 =[7.5,10.5] (all in meters). We use the LS model in (19) with r=6 to estimate the MT location, and consider the cases when there are zero, one (only FT₁ ), two (FT₁ , FT₂ ), and three (FT₁ , FT₂ , FT₃ ) NLOS FTs. For each NLOS channel realization, we use a channel realization from CM4 of IEEE 802.15.4a channel models and prefix an exponentially distributed

Note that exponential distribution is taken as an example, and some other bias models may as well be used.

NLOS bias _bi with a mean of _λi =2 nanoseconds. For each LOS channel realization, we use CM3 of IEEE 802.15.4a channel models and assume that first path correctly characterizes the distance between the MT and the FT. For simplicity, we assume that ^σi2 =^σ2 is identical for all the FTs and does not change with distance. The results are averaged over 100 NLOS bias realizations, 100 noise realizations, and 100 channel realizations (i.e., over ¹⁰⁶ different observations), which are assigned randomly to different FTs. The simulation scenario is depicted in Figure 7 along with the circles given by (7) representing the possible MT positions for each FT in topology-1, where FT₁ has an NLOS bias of 3 m. For all the HWS algorithms, we use ^k1(1) =0.1,^k2(1) =1,^k1(2) =0.1,^k2(2) =0.2,^k3(2) =1,_Δ1 =-3 , and _Δ2 =3 .

Figure 7: Simulation scenario for the LS and WLS algorithms ( ^σ2 =3 and FT₁ has 3-meter NLOS bias). Actual MT location is denoted by o while its LS estimate is denoted by x . Locations of the FTs for both topology-1 (indicated in black) and topology-2 (indicated in red) are given, while only the position circles corresponding to topology-1 are drawn.

[figure omitted; refer to PDF]

In Figures 8 and 9, simulation results for the average localization error using conventional LS and different WLS algorithms are presented for ^σ2 ∈{0.3,1} and for different sets of NLOS FTs. We also simulated the performance of residual weighting (RWGH) algorithm reported in [18] which aims to mitigate the NLOS bias by weighting the location estimates (for different topologies) with the inverses of the corresponding residual location errors.

Reader is referred to [18] for details of RWGH algorithm. Note that different from the original RWGH algorithm in [18] which uses nonlinear LS, we used the linear LS in our simulations.

For the conventional LS estimator, the average localization error increases with increasing number of NLOS FTs. Also, location accuracy degrades slightly when the noise variance increases. While RWGH can mitigate the NLOS bias effects in certain settings, HWS-WLS techniques outperform all other approaches for all the scenarios.

Figure 8: The average localization error of different WLS algorithms with respect to different number of NLOS FTs for ^σ2 =0.3 and ^σ2 =1 (topology-1).

[figure omitted; refer to PDF]

Figure 9: The average localization error of different WLS algorithms with respect to different number of NLOS FTs for ^σ2 =0.3 and ^σ2 =1 (topology-2).

[figure omitted; refer to PDF]

Note that for topology-1, the accuracies of SWS-WLS and IAD-WLS improve when the number of NLOS FTs increases from 2 to 3 for ^σ2 =1 . This shows that the localization accuracy depends not only on the number of NLOS FTs, but also on their locations. In particular, NLOS biases of some FTs which are symmetric with respect to the MT (e.g., FT₂ and FT₃ ) may cancel out each other. In order to better evaluate the impact of NLOS FTs' locations, we simulated the localization algorithms with same number of NLOS FTs in Figure 10. For a single NLOS FT, the localization accuracies do not degrade significantly with the location of the NLOS FT. Exception to this is when the NLOS FT is the reference FT, in which the localization accuracy will degrade significantly. The WLS methods are no longer effective in such a scenario, since, as apparent from (B.1) in Appendix B, all equations become biased due to bias term _br . On the other hand, when there are two NLOS FTs, the location of the NLOS FTs may have a more significant impact on the localization accuracy especially for IAD and SWS. For example, when FT₁ and FT₅ are both in NLOS, discarding these measurements shows to significantly degrade the accuracy compared to other NLOS FT configurations. Again, WLS approaches are ineffective when the reference FT is in NLOS.

Figure 10: The average localization error of different WLS algorithms with respect to different FTs being in NLOS for ^σ2 =0.3 (Topology-1).

[figure omitted; refer to PDF]

In order to further clarify the NLOS bias cancelation, we consider a simple topology (topology-3) composed of four FTs as shown in Figure 11, where the FT locations are given by _x1 =[-20,-20],_x2 =[-20,20],_x3 =[20,-20] , and _x4 =[20,20] (all in meters). The FT₁ is used as the reference FT, and the true position of the MT is at [0,0] m. The theoretical (based on Appendix B) and the simulation results for the NLOS FT scenarios are presented in Figure 11. As expected, the MSE increases if the LOS is obstructed for any of the FTs. Moreover, the position of the NLOS FT(s) with respect to the reference FT affects the MSE. For example, if the NLOS FT is the reference FT itself (i.e., b = [2 0 0 0] m), the MSE becomes worst. If the NLOS FT is far away from the reference FT (e.g., b = [0 0 0 2] m), the MSE becomes better. Another interesting observation is that if two NLOS FTs are symmetric with respect to the MT location and have similar NLOS biases, the NLOS biases tend to cancel each other; for example, the MSE for b = [0 2 2 0] m is better than the MSE for b = [0 0 2 0] m.

Figure 11: Theoretical (markers) and simulated (dashed lines) MSE versus ^σ2 for an MT located at x=[0,0] for different NLOS bias scenarios in topology-3 with FT₁ taken as the reference FT.

[figure omitted; refer to PDF]

In Figure 12, the simulated MSEs of the LS, HWS1-WLS, and SWS-WLS algorithms are plotted when all the FTs are in LOS scenario along with the theoretical MSEs derived in the Appendix A. For comparison purposes, the CRLB of the location estimate is also included. Theoretical results capture the simulation results well for both the LS and WLS algorithms. Compared to the LS estimator, the MSE of the SWS-WLS gets considerably worse as ^σ2 increases when there are no NLOS FTs. On the other hand, the degradation in the accuracy of HWS1-WLS is negligible. In Figure 13, simulation and theoretical MSE results of the LS and HWS1-WLS algorithms are plotted for different fixed NLOS bias scenarios. When NLOS bias is larger than 1 m, HWS1-WLS performs always better than the LS for all the ^σ2 values. However, when FT₁ has 1 m NLOS bias, we observe that HWS1-WLS performance becomes worse than LS as ^σ2 increases. This may be due to the fact that we fixed ^k1(1) =0.1 and ^k2(1) =1 for all the simulations, and accuracy might possibly be improved by optimizing the weights with respect to some other parameters.

Figure 12: The theoretical (markers) and simulated (dashed lines) MSEs of the linear LS, HWS1-WLS, and SWS-LS estimators in topology-1 when all the FTs are in LOS, with FT₆ taken as the reference FT.

[figure omitted; refer to PDF]

Figure 13: The theoretical (markers) and simulated (dashed lines) MSE of the linear LS and HWS1-WLS estimators in topology-1 for different NLOS configurations, with FT₆ taken as the reference FT.

[figure omitted; refer to PDF]

6. Conclusion

In this paper, we proposed a novel NLOS identification technique that does not require a time history of range measurements as opposed to prior art techniques. The technique requires only the amplitude and delay statistics of the multipath channel in order to perform NLOS identification. Therefore, it is relatively simple as compared to previous reported works. Furthermore, this technique does not assume that the MT has to be in motion, which was commonly assumed in the literature. Hence, such a technique is especially suitable for indoor wireless personal area networks applications where most MT are either in static or in nomadic conditions. Simulation results show that correct LOS/NLOS identification can be achieved with over 90% of the realizations for most channel models. Here, the kurtosis, mean excess delay, and rms delay spread of the multipath channel were obtained by assuming knowledge of the first path arrival. As a future work, sensitivity of the proposed NLOS detectors to the errors in the first path arrival can be investigated. Furthermore, we also analyzed different WLS algorithms (e.g., IAD, SWS, HWS) which deploy the likelihood functions obtained from the MPCs of the received signal. Through Monte-Carlo simulations using the IEEE 802.15.4a channel models, HWS-WLS was proven to outperform the conventional LS algorithm under NLOS scenarios. Future work includes optimization of the NLOS weights using a priori information regarding the distribution of the NLOS bias.

References

[1] M. Z. Win, R. A. Scholtz, "On the robustness of ultra-wide bandwidth signals in dense multipath environments," IEEE Communications Letters , vol. 2, no. 2, pp. 51-53, 1998.

[2] M. Z. Win, R. A. Scholtz, "On the energy capture of ultrawide bandwidth signals in densemultipath environments," IEEE Communications Letters , vol. 2, no. 9, pp. 245-247, 1998.

[3] M. Z. Win, R. A. Scholtz, "Characterization of ultra-wide bandwidth wireless indoor channels: a communication-theoretic view," IEEE Journal on Selected Areas in Communications , vol. 20, no. 9, pp. 1613-1627, 2002.

[4] D. Cassioli, M. Z. Win, A. F. Molisch, "The ultra-wide bandwidth indoor channel: from statistical model to simulations," IEEE Journal on Selected Areas in Communications , vol. 20, no. 6, pp. 1247-1257, 2002.

[5] C.-C. Chong, S. K. Yong, "A generic statistical-based UWB channel model for high-rise apartments," IEEE Transactions on Antennas and Propagation , vol. 53, no. 8, pp. 2389-2399, 2005.

[6] C.-C. Chong, Y.-E. Kim, S. K. Yong, S.-S. Lee, "Statistical characterization of the UWB propagation channel in indoor residential environment," Wireless Communications and Mobile Computing , vol. 5, no. 5, pp. 503-512, 2005.

[7] A. F. Molisch, D. Cassioli, C.-C. Chong, "A comprehensive standardized model for ultrawideband propagation channels," IEEE Transactions on Antennas and Propagation , vol. 54, no. 11, pp. 3151-3166, 2006.

[8] B. Alavi, K. Pahlavan, "Analysis of undetected direct path in time of arrival based UWB indoor geolocation," in Proceedings of the 62nd IEEE Vehicular Technology Conference (VTC '05), vol. 4, pp. 2627-2631, Dallas, Tex, USA, September 2005.

[9] I. Guvenc, Z. Sahinoglu, A. F. Molisch, P. Orlik, "Non-coherent TOA estimation in IR-UWB systems with different signal waveforms," in Proceedings of the 2nd International Conference on Broadband Networks (BROADNETS '05), pp. 245-251, Boston, Mass, USA, October 2005.

[10] D. Dardari, C.-C. Chong, M. Z. Win, "Improved lower bounds on time-of-arrival estimation error in realistic UWB channels," in Proceedings of IEEE International Conference on Ultra-Wideband (ICUWB '06), pp. 531-537, Waltham, Mass, USA, September 2006.

[11] D. Dardari, C.-C. Chong, M. Z. Win, "Threshold-based time-of-arrival estimators in UWB dense multipath channels," to appear in IEEE Transactions on Communications

[12] M. P. Wylie, J. Holtzman, "The non-line of sight problem in mobile location estimation," in Proceedings of the 5th IEEE International Conference on Universal Personal Communications (ICUPC '96), vol. 2, pp. 827-831, Cambridge, Mass, USA, September-October 1996.

[13] J. Borras, P. Hatrack, N. B. Mandayam, "Decision theoretic framework for NLOS identification," in Proceedings of the 48th IEEE Vehicular Technology Conference (VTC '98), vol. 2, pp. 1583-1587, Ottawa, Canada, May 1998.

[14] S. Gezici, H. Kobayashi, H. V. Poor, "Nonparametric nonline-of-sight identification," in Proceedings of the 58th IEEE Vehicular Technology Conference (VTC '03), vol. 4, pp. 2544-2548, Orlando, Fla, USA, October 2004.

[15] S. Gezici, Z. Tian, G. B. Giannakis, "Localization via ultra-wideband radios: a look at positioning aspects of future sensor networks," IEEE Signal Processing Magazine , vol. 22, no. 4, pp. 70-84, 2005.

[16] S. Al-Jazzar Algorithms and parameter estimation for radiolocation in NLOS environments , Ph.D. dissertation, University of Cincinnati, Cincinnati, Ohio, USA, 2004.

[17] A. Rabbachin, I. Oppermann, B. Denis, "ML time-of-arrival estimation based on low complexity UWB energy detection," in Proceedings of IEEE International Conference on Ultra-Wideband (ICUWB '06), pp. 598-604, Waltham, Mass, USA, September 2006.

[18] P. C. Chen, "A non-line-of-sight error mitigation algorithm in location estimation," in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC '99), vol. 1, pp. 316-320, New Orleans, La, USA, September 1999.

[19] X. Wang, Z. Wang, B. O'Dea, "A TOA-based location algorithm reducing the errors due to non-line-of-sight (NLOS) propagation," IEEE Transactions on Vehicular Technology , vol. 52, no. 1, pp. 112-116, 2003.

[20] L. Cong, W. Zhuang, "Nonline-of-sight error mitigation in mobile location," in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '04), vol. 1, pp. 659, Hong Kong, March 2004.

[21] J. Riba, A. Urruela, "A non-line-of-sight mitigation technique based on ML-detection," in Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04), vol. 2, pp. 153-156, Montreal, Quebec, Canada, May 2004.

[22] C.-L. Chen, K.-T. Feng, "An efficient geometry-constrained location estimation algorithm for NLOS environments," in Proceedings of the International Conference on Wireless Networks, Communications and Mobile Computing (WIRLES '04), vol. 1, pp. 244-249, Maui, Hawaii, USA, June 2005.

[23] R. Casas, A. Marco, J. J. Guerrero, J. Falcó, "Robust estimator for non-line-of-sight error mitigation in indoor localization," EURASIP Journal on Applied Signal Processing , vol. 2006, 2006.

[24] Y.-T. Chan, H. Y. C. Hang, P.-C. Ching, "Exact and approximate maximum likelihood localization algorithms," IEEE Transactions on Vehicular Technology , vol. 55, no. 1, pp. 10-16, 2006.

[25] B. Li, A. G. Dempster, C. Rizos, H. K. Lee, "A database method to mitigate the NLOS error in mobile phone positioning," in Proceedings of IEEE Position, Location, and Navigation Symposium (PLANS '06), pp. 173-178, San Diego, Calif, USA, April 2006.

[26] X. Li, "An iterative NLOS mitigation algorithm for location estimation in sensor networks," in Proceedings of the 15th IST Mobile & Wireless Communications Summit, Myconos, Greece, June 2006.

[27] S. Venkatesh, R. M. Buehrer, "A linear programming approach to NLOS error mitigation in sensor networks," in Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN '06), pp. 301-308, Nashville, Tenn, USA, April 2006.

[28] B. Allen, M. Dohler, E. Okon, W. Malik, A. Brown, D. Edwards Ultra Wideband Antennas and Propagation for Communications, Radar, and Imaging , John Wiley & Sons, West Sussex, UK, 2007.

[29] D. B. Jourdan, D. Dardari, M. Z. Win, "Position error bound for UWB localization in dense cluttered environments," in Proceedings of IEEE International Conference on Communications (ICC '06), vol. 8, pp. 3705-3710, Istanbul, Turkey, June 2006.

[30] "Nist/sematech e-handbook of statistical methods," http://www.6sigma.us/handbook/eda/section3/eda35b.htm , 2006.

[31] T. S. Rappaport Wireless Communications: Principles and Practice , Prentice Hall, Indianapolis, Ind, USA, 2002.

[32] S. Gezici, Z. Sahinoglu, "UWB geolocation techniques for IEEE 802.15.4a personal area networks,", MERL, Cambridge, Mass, USA, August 2004.

[33] D. B. Jourdan, N. Roy, "Optimal sensor placement for agent localization," in Proceedings of IEEE Position, Location, and Navigation Symposium (PLANS '06), pp. 128-139, San Diego, Calif, USA, April 2006.

[34] V. Dizdarevic, K. Witrisal, "On impact of topology and cost function on LSE position determination in wireless networks," in Proceedings of Workshop on Positioning, Navigation, and Communication (WPNC '06), pp. 129-138, Hannover, Germany, March 2006.

[35] B. Denis, J.-B. Pierrot, C. Abou-Rjeily, "Joint distributed synchronization and positioning in UWB ad hoc networks using TOA," IEEE Transactions on Microwave Theory and Techniques , vol. 54, no. 4, pp. 1896-1910, 2006.

[36] J. J. Caffery Jr., G. L. Stüber, "Overview of radiolocation in CDMA cellular systems," IEEE Communications Magazine , vol. 36, no. 4, pp. 38-45, 1998.

[37] F. Gustafsson, F. Gunnarsson, "Mobile positioning using wireless networks: possibilites and fundamental limitations based on available wireless network measurements," IEEE Signal Processing Magazine , vol. 22, no. 4, pp. 41-53, 2005.

[38] J. J. Caffery Jr., "A new approach to the geometry of TOA location," in Proceedings of the 52nd Vehicular Technology Conference (VTC '00), vol. 4, pp. 1943-1949, Boston, Mass, USA, September 2000.

[39] Y. Qi, H. Kobayashi, H. Suda, "Analysis of wireless geolocation in a non-line-of-sight environment," IEEE Transactions on Wireless Communications , vol. 5, no. 2, pp. 672-681, 2006.

Appendix

Appendices

A.

Let _Aw =WA and _pw =Wp . Then, by replacing (5) in (18) and assuming that bias terms are zero, we may write [figure omitted; refer to PDF] where the constant and noisy

If _pn [arrow right]0 , all the lines will intersect at a single point, and the solution of the estimator in (19) is exact.

components of _pw are given by [figure omitted; refer to PDF] [figure omitted; refer to PDF] where [figure omitted; refer to PDF] [figure omitted; refer to PDF] with _ki =^xi2 +^yi2 .

Using (17) and (A.3), the MSE of the estimator in (19) can be derived as follows. We may calculate the covariance matrix of x^ as [figure omitted; refer to PDF] where x is the true location of the MT which can be obtained as [figure omitted; refer to PDF] Plugging (19) and (A.7) into (A.6) yields [figure omitted; refer to PDF] where E{_pn,w^pn,wT } is an (N-1)×(N-1) matrix. Let E_{{pn,w^pn,wT }ij} denote the term corresponding to the i th row and j th column of E{_pn,w^pn,wT } . If i≠j , we have [figure omitted; refer to PDF] which after some manipulation simplifies to [figure omitted; refer to PDF] On the other hand, if i=j , we have [figure omitted; refer to PDF] which after some manipulation simplifies to [figure omitted; refer to PDF] Note that when ^σ2 [arrow right]0,E{_pn,w^pn,wT }[arrow right]0 , and _pw [arrow right]_pc,w .

After calculating Cov(x^) from (A.8), the mean square localization error can then be computed as follows: [figure omitted; refer to PDF] where Tr(X) is the trace of matrix X .

B.

In the presence of NLOS biases at different FTs, extra bias-dependent terms are introduced in (A.5). Then we have [figure omitted; refer to PDF] [figure omitted; refer to PDF] where [figure omitted; refer to PDF] Comparing (B.1) with (A.5), we can easily deduce that [figure omitted; refer to PDF] where the bias dependent vectors b and c are obtained by stacking _{b i} and _{c i} into (N-1)1 vectors, respectively.

For a given bias vector b , we may derive the covariance matrix as in (A.8) as follows: [figure omitted; refer to PDF] [figure omitted; refer to PDF] where [figure omitted; refer to PDF] Note that comparing (B.6) with (A.8) implies that bias dependent noise terms will increase the MSE in an NLOS condition.

Expectation in (B.7) may further be derived as follows. Let I(i,j) be an indicator function defined as [figure omitted; refer to PDF] Then, proceeding similarly as in Appendix A, we may derive [figure omitted; refer to PDF]