Abstract
Recent development in wireless communicationbased positioning technology brings significant challenge of detecting the weak signal component arriving from the direct propagation path for timeofarrival (TOA)based approach. Due to the common obstruction of the direct propagation path in dense multipath environments, identification of the weak direct path in these environments can be very difficult via the classical correlationbased estimator in the presence of interference from significant later arriving multipath components. A new direct path detection scheme using the multipath interference cancelation is presented in this article. For data communication purpose, an iterative estimator with improved accuracy for joint channel and data estimation is first developed; based on which, the interference of multipath components are reconstructed and subtracted from the original received signal. With the aid of the detected data, an enhanced preamble is formulated. The accuracy of direct path detection is substantially improved by using the correlation between the multipath interferencesuppressed signal and the enhanced preamble. Semianalytical expression of the performance of the iterative estimator is derived. The analysis enables the system to determine an automatic stopping criterion to reduce the computational complexity of the iterative process. The performance of the direct path detection is also analyzed in terms of the signaltointerferencenoise ratio (SINR) and compared with that of the conventional approach. Computer simulation results show the superiority of the proposed direct path detection. The accuracy of the positioning system using the proposed method is also evaluated in dense multipath environments.
Keywords:
Direct path; Later path; Multipath interference cancelation; Timeofarrival; Dense multipath environment; Orthogonal frequencydivision multiplexingIntroduction
Positioning techniques using wireless communication signals have attracted considerable attention, especially in dense multipath environments where the Global Positioning System (GPS) is often unreliable [1,2]. Potential applications include navigation, locationaware services, and asset tracking [3,4]. A few positioning system using data communication systems, e.g., cellular network [5,6], wireless local area network (WLAN) [7], digital television (DTV) [8], ultrawide bandwidth (UWB) [2,911], and wireless sensor networks [12,13] have been investigated in the literature. In these systems, timeofarrival (TOA)based approach is commonly preferred where the timing of the signal arriving from the direct propagation path is estimated and used for further location estimation [14,15]. However, significant challenges arise in dense multipath environments, where the direct signal propagation path is often blocked by various obstacles such as buildings, pedestrians and slowlymoving vehicles, making the strength of the direct path significantly weaker than those of later paths (LPs) from scattering, reflection or refraction.
TOA estimation can be achieved by the classical correlationbased estimator, where the correlation is performed between a signal template^{a} and its received version, and the timing of the first detected peak of the correlation output is considered as the TOA [9,16]. However, this method has limiting factors for positioning system using communication signals. The training sequence, designed for data communications, has limited duration in order to improve the transmission efficiency and therefore, the correlation peak of the first path is not distinct. Furthermore, due to the multipath propagation effect, the desired signal component of the first path is interfered by the superposition of the signal components of the LPs. In this case, the correlation output can exhibit adjacent peaks with similar or larger magnitude due to the large multipath interference, leading to ambiguity in the selection of the correct peak corresponding to the first path. Therefore, it is very difficult to reliably detect the weak direct path from the wireless signals consisting of strong multiple components and thus, large positioning error is inevitable when the direct path is erroneously identified.
To facilitate the TOA estimation with higher accuracy, superresolution schemes that jointly estimate the amplitude and the relative delay of each path were proposed in [1719]. Despite the extremely high computational complexity the methods entail, the results show that these estimators do not always lead to good TOA estimation. For real applications with complexity constraints, several simple techniques have been proposed to detect the first path. Energy detectionbased method was proposed in [2023]. However, the energy detector can perform poorly when the strength of the first path is not the strongest one. Meanwhile, thresholdbased approach to detect the first path by comparing the correlation output with a particular threshold [20,2429] are gaining interests due to their potential for complete analog implementation, and therefore, particularly attractive to low cost batterypowered devices, e.g., mobile receivers. However, the thresholdbased correlation estimator with the solutions to the aforementioned practical challenges in dense multipath environments remains large space undisclosed.
We introduced the idea of multipath interference cancelation in [30]; however, with a simple system model and performance evaluation under static channel. Furthermore, the theoretical performance and the practical constraints, e.g., complexity issues, have not been considered. In this article, we propose a direct path detection scheme using multipath interference cancelation for accurate TOA estimation in dense multipath environments. We consider an Orthogonal FrequencyDivision Multiplexing (OFDM)based communication system, which is widely adopted in various broadband wireless applications [31] and demonstrate the feasibility of the proposed direct path detection method in communicationbased positioning systems. For data communication purpose, an iterative estimator for joint channel estimation and data detection with progressively improved accuracy is first proposed to achieve better performance of data communication. Based on the output of the iterative estimator, we propose to reconstruct and mitigate the multipath components from the received signals. Dataaided method is also used to construct an enhanced preamble. The new direct path detection is therefore based on the crosscorrelation between the multipath interferencesuppressed signal and the enhanced preamble. Considering the computational burden for the mobile receivers, the characteristics of the iterative estimator is studied by deriving a semianalytical expression of the variance of the estimation error and the convergence conditions. An automatic stopping criterion is further developed to avoid the unnecessary computational complexity and allow a tradeoff between the performance degradation and computational burden. The performance of the direct path detection is analyzed by deriving the signaltonoiseinterference ratio (SINR)^{b}. Monte Carlo simulations are carried out to evaluate and verify the performance and effectiveness of different modules as well as the overall method.
The rest of the article is organized as follows. The model of the OFDMbased communication system is presented in Section ‘OFDMbased communication system with positioning capability’. The challenges of the classical correlationbased estimator for TOA estimation are also addressed in Section ‘OFDMbased communication system with positioning capability’. In Section ‘Proposed direct path detection scheme’, a new direct path detection scheme using the multipath interference cancelation and dataaided techniques are proposed. Performance analysis is presented in Section ‘Performance analysis of the proposed direct path detection method’ and demonstrated by Monte Carlo simulations in Section ‘Simulation results and discussions’. Finally, we conclude the article in Section ‘Conclusion’.
Notations: Throughout the article, if no special note is given, we denote vectors and matrices with letters in bold fonts and scalars with nonbold forms. For any variable X, we denote its corresponding estimated version by and the corresponding estimation error by . Superscript T denotes transpose and superscript H denotes the conjugate transpose. tr(·) denotes the trace of a matrix. I denotes the identity matrix. ∥·∥ denotes the Frobenius norm of a matrix.
OFDMbased communication system with positioning capability
System model
We consider a typical signal frame structure of OFDMbased communication system in Figure 1. Denote the preamble signal by p≜[a_{0},a_{1},…,a_{P−1}] with length P which is periodically multiplexed with OFDM data stream for initial synchronization and channel estimation purposes. x≜[x_{0},x_{1},…,x_{N−1}] denotes the OFDM data symbol where
where X_{k} denotes the complex data on the kth subcarrier and N is the total number of subcarriers. We denote the channel impulse response vector by with channel order L. In practice, L is usually unknown at the receiver. Furthermore, we assume that the receiver does not know the position of the first path h_{0}. Therefore, we replace h by an L^{′}dimension vector
where L_{h} and L_{t} are design parameters which depend on the observation range of initial synchronization and the maximum expected channel delay spread, respectively. Note that our main focus here is on the direct path detection for positioning purposes and therefore, In the following, it is reasonable to assume that in conventional communication system, the guard intervals (GIs) are longer than L^{′}. The data symbols are free of intersymbol interference (ISI) for data communication purposes. However, for the direct path detection, the signal component of the direct path is interfered by those of the multipath within each data symbol. The challenges will be explained in detail in the following section. The received signal can then be written in the following vectormatrix form
where we have defined the following matrices:
y_{p} and y_{x} represent the received vectors corresponding to the preamble signal and the OFDM data symbol, respectively. w_{p} and w_{x} denote the additive white Gaussian noise (AWGN) vectors with zero mean and variance .
Figure 1. Signal frame structure of an OFDMbased communication system.
Classical correlationbased TOA estimator
The conventional approach, which is based on the crosscorrelation between the received signal and the local signal template, is widely used in communications as well as positioning systems. The time index of the earliest detected peak on the correlation output can then be converted to the corresponding arrival time of the signal traveling along the direct propagation path. However, our approach aims for positioning with traditional communication systems where the existing signal structures are not originally designed for good positioning capabilities, e.g., short preamble signal, and therefore, the first path can have a weak correlation peak and it is also severely distorted by the interference from later arriving multipath components in dense multipath environments. We now analyze the performance of this method.
Mathematically, we can write the crosscorrelation between the received signal and the preamble as follows,
Once the first correlation peak corresponding to the direct path is detected at m = m_{0}, (4) can be further written as
where (·)_{p} represents the operation of modulo p and denotes the cyclic correlation value of the preamble. I_{LPs} denotes the interference components from the LPs. Note that C_{l} may vary depending on the use of different pseudo random sequence. In the following analysis, we concentrate on an msequence as the preamble signal. The following remarks are of interest.
1. msequence exhibits excellent correlation properties [32] such that the interference components from the LPs in (5) have been minimized by the preamble itself. In this case, the performance gain of the proposed direct path detection over the classical estimator will serve as a lower bound for other cases. Therefore, improved performance gain can further be expected when other types of preambles are used.
2. Unlike some complexvalued sequences, the msequence has low hardware implementation complexity which has been widely employed in various research works and real applications, e.g., synchronization in OFDM systems [33,34].
Subsequently, we have the cyclic correlation value C_{l} = −1 for l ≠ 0. SINR is used as a criterion to evaluate the performance of the estimator. For (5), the SINR of the classical correlationbased estimator can be formulated as
The SINR can be verified by noting that {h_{l}} are independent, {a_{n}} are known numbers and {w_{n}} are also independent. In wireless environments such as indoor or dense commercial areas, the strength of the direct path is often significantly weaker than the LPs due to the obstructions, e.g., . Therefore, interference from LPs’ components shown in (6) can have large negative impact on the SINR. It is straightforward to see that the duration of the preamble signal p and the interference from the LPs are two main challenges in the detection of the direct path. However, in data communication systems, the preamble signal is used for initial access, synchronization and channel estimation. To optimize the spectral efficiency in cellular networks, the overhead of such training has to be as low as possible to reduce the corresponding redundancy as long as the quality of service requirements are achieved. On the contrary, for positioning systems it is desired to have as long preamble as possible to provide large correlation gain for good timing estimation. To address the aforementioned challenges, we propose a new direct path detection scheme based on multipath interference cancelation and dataaided method in the following sections.
Proposed direct path detection scheme
Iterative estimator for joint channel estimation and data detection
In traditional communication systems, the channel estimate can be achieved by solely exploiting the preamble signal using a least square (LS) estimator when channel statistics are unknown and the channel is treated as a deterministic parameter [35],
However, the accuracy of LS channel estimation (and hence data detection) is usually not good enough. As our proposed multipath interference cancelation approach relies on the performance of the channel estimator, the improvement given by the proposed approach can be very limited when the LS estimator is used. We therefore propose an iterative estimator to provide accurate channel and data estimation which is of significant importance for further multipath interference cancelation purpose.
The basic idea of the proposed iterative estimator is to utilize data decision feedback to virtually extend the duration of the original preamble signal to refine the initial channel estimation. We want to use both P and the unknown X_{M} in (2) instead of only P to improve the accuracy of channel estimation. An approximation of X_{M} can be first obtained from the tentative demodulated OFDM data based on the initial channel estimation given in (7). However, this approximation is not reliable at the beginning and can be gradually improved when channel estimation improves. Hence, an iterative estimator is needed to progressively provide more accurate channel estimation. Consequently, the accuracy of both data and channel will be enhanced simultaneously as the process is iterated.
The proposed iterative estimator is described as follows:
Step 1. Initial Channel EstimationSet the iteration index i = 0. Initial channel estimation will be derived solely from the original multiplexed preamble signal. Without the subsequent OFDM data, the received signal now is
The LS estimator can be used to obtain the channel estimation since no channel statistics information is required,
The variance of the estimation error can be used as a criterion to evaluate the performance of the LS estimator,
It should be mentioned that the accuracy of the initial estimation is limited by the length of the preamble. Therefore, the performance of multipath interference cancelation will be dramatically degraded if a short preamble is used.
Step 2. Iterative ProcedureThe OFDM signal in frequency domain is equalized with the tentative channel estimation from the previous step,
Make hard decisions based on the equalizer output and denote it by . Now the transmitted signal in time domain can be remodulated using the decisioned data,
The following matrix is constructed,
Consequently, we formulate a hybrid matrix which consists of the preamble and the demodulated data,
The channel estimate then is updated by
Set iteration index i = i + 1. The updated channel estimate is subsequently used for the next round of data demodulation. As the above process is iterated, the channel and data estimation are progressively enhanced. Step 2 is repeated until the automatic stopping criterion is fulfilled. The characteristics of the iterative estimator and the automatic stopping criterion will be derived in the subsequent analysis.
Automatic stopping criterion design
Due to the limited battery life of the mobile devices, an automatic stopping criterion is proposed to terminate the iterative process as early as possible to avoid unnecessary computations while the userspecified requirement is achieved.
Before deriving the stopping criterion, it is necessary to study the variance of the estimation error of the iterative process. In [36], the authors analyzed the performance of an iterative channel estimation and multiuser detection in multipath DSCDMA channels with BPSK modulation. In this article, we extend the analysis to the proposed iterative estimator in OFDMbased communication system with MPSK modulation. We use both time and frequency domains’ signals analysis to derive a semianalytical result of the estimation error. Based on the result, the conditions of convergence and an automatic stopping criterion is also derived. Therefore, the analysis in this article represents a more general structure of the iterative channel estimator in communication systems. Given (15), the expression of the estimation error is straightforward to obtain (note that the superscript i denoting the iteration time has been dropped for simplicity, unless otherwise stated),
where
The terms Δh_{f} and Δh_{w} denote the estimation error caused by data decision feedback errors and AWGN, respectively. In (16), the approximation holds that when (p + N) ≫ L^{′} and therefore, the variance of Δh_{w} can be obtained by
For Δh_{f}, it is more difficult to determine its variance since it consists of the unknown data decision errors and the impact of the multipath channel. We can first write the variance as follows
Since can be equivalently expressed as
By substituting (19) into (18), (18) can further be arranged as
where F_{N} represents the DFT transform matrix with its element . is the frequency domain version of with its element . ΔΨ is the frequency domain version of ΔX_{M} with its element . An semianalytical expression of (20) is derived in the Appendix and can be represented by
where M is the modulation order and P_{e} denotes the symbol error rate (SER) of the data detection results from the iterative estimator. The definition of can also be referred to the Appendix. The overall variance of the estimation error can thus be written as
The following remarks are of interest:
1. The iterative estimator with data decision feedback should only be used along with the preamble if the resulting variance of channel estimation error is smaller than that obtained during the initial estimation. Based on (9) and (22), it is easy to check that P_{e max}, the maximum P_{e}, that assure the performance improvement when the iterative estimator is used, can be determined by
which results in
2. It can also be seen from (22) that P_{e} is a function of the variance of the channel estimation error at the symbol detector, and can be given by
where the function f can be determined using computer simulations. f(x) is a monotonous increasing function of x within a close interval . Therefore, at the ith iteration, can be given by
where
For the convergence problem, a reasonably good initial channel estimation where only the preamble is used is necessary to guarantee the convergence of the iterative estimator described in (25). Although it is very difficult to derive the analytical results of the iterative process, e.g., estimation error and convergence. We therefore derive a semianalytical result of the estimation error in (21) and based on which, we can also derive the initial conditions on the channel estimation and SER for the convergence purpose. These conditions are very important and can be used to evaluate the convergence of a given communication system when particular system configuration such as preamble structure, channel estimation algorithm and modulation scheme is predefined. In the following, we denote the variance of the channel estimation error of the initialization stage by and it must satisfy the following conditions:
• is located in the interval , namely
This condition ensures a reasonably good initialization performance of the iterative estimator.
• The variance of the channel estimation error should decrease with an increase in the number of iterations, namely
This condition ensures that the iterative estimator does not diverge.
3. Assuming the convergence of the iterative estimator in reasonable conditions, (22) implies that
almost surely, as P_{e} → 0. It should be mentioned that this bias cannot be removed when the length of the preamble and the OFDM data symbol is finite and it serves as a lower bound of the iterative estimator. In fact, P_{e} is dependent on SNR and therefore this bias vanishes as SNR→ ∞.
Based on the convergence analysis of the iterative estimator, an automatic stopping criterion can be derived. Consider the relative estimation error between consecutive two iterations at the ith iteration,
the iterative process is terminated if the following criterion is fulfilled,
where ϵ is a userdefined threshold factor depending on the tolerable performance degradation of the receiver. As a small ϵ that results in less performance degradation is often associated with large number of iterations and vice versa. Therefore, we simulate the performance of the iterative estimator with different threshold factors and it will be discussed in Section ‘Conclusion’. In realtime application, a tuneable threshold selection device can be equipped such that the user is flexible to adjust the threshold according to its required performance and power condition.
Proposed direct path detection method
Given the channel estimation results from the iterative estimator, the significant paths which introduce dominant interference to the direct path detection can be determined based on the estimated channel. We use a thresholdbased method to select the significant paths. Since the practical multipath channels often show some level of sparsity, where very limited channel paths carry significant energy. Usually the total AWGN perturbation from those nonsignificant paths (zero paths) is much higher than the channel energy carried by them. Therefore, choosing a relative high threshold can successfully reject those nonsignificant paths while detecting most of the significant paths.
From [37], we can first detect the strongest path from the estimated channel by
Then the significant paths can be obtained by
The signal components of the selected paths can be reconstructed using the regenerated OFDM data from the iterative estimator and removed from the received signal,
where and denote the interferencesuppressed signal corresponding to the preamble and OFDM data, respectively.
As we discussed, the preamble for data communications is originally designed to have short duration. In order to enhance the peak gain for direct path detection, we also incorporate the dataaided method. An enhanced preamble is formulated by
By utilizing the interferencesuppressed signal and the enhanced preamble, the new correlationbased estimator is then formulated as follows,
This correlation output can provide significantly higher peak gain due to the use of the virtually extended signal template which consists of the original template and a “dirty template” from data detection results. Furthermore, the impact of the overlay multipath signal components are mitigated.
The earliest correlation peak that exceeds a particular threshold can be considered as the direct propagation path and its timing index is straightforward to be converted to the TOA estimation. Details of the selection of the threshold can be found in [24].
Remark. Note the above method performs well in dense multipath environments, especially in nonlineofsight conditions [2,3841], where the strength of direct path is significantly lower than the LPs. However, in the presence of lineofsight propagation (strong direct path), the strength of the direct path can be strong w.r.t. the LPs. In this case, the signal component of the direct path may also be mitigated during the multipath interference cancelation stage. We therefore propose the following algorithm to adapt the proposed method to the dynamic wireless propagation environments, ranging from nonlineofsight condition to lineofsight condition.
Algorithm 1 Proposed direct path detection algorithm for dynamic propagation environments
Input: Received signals y_{p}and y_{d}.
Output: Time index of the direct path m_{0}.
begin
1. Perform the iterative estimator using (7) to (15), and obtain the estimated channel and data ;
2. Select the significant paths based on according to the proposed direct path detection method;
2.1 Detect the strongest path from the estimated channel using (31) and determine the threshold factor ηaccording to the method in [37];
2.2 Select the significant paths using (32);
2.3 Record the time index of the first selected significant path, and denote it by k=m_{0};
3. Perform multipath interference cancelation and direct path detection using (31) to (36);
3.1 Mitigate multipath interference using (33);
3.2 Adopt dataaided method in (35);
3.3 Detect the direct path based on (36), and record the time index of the detected peak ;
ifthen // No peak selected afterinterference cancelation
k = m_{0};
else
ifthen // A peak prior to m_{0} isdetected after interferencecancelation
else
k = m_{0};
end
end
Performance analysis of the proposed direct path detection method
To show the superiority of the proposed approach, we evaluate the SINR of the correlation output in (36) of the proposed method and compare it with (6).
Assuming the first detected peak at the time index m = m_{0} corresponds to the direct propagation path, we can write the correlation output in (36) as follows,
where and denote the contributions of the preamble and OFDM data, respectively. We can further write and as
Note that in the subsequent analysis, we let m_{0} = 0 and drop the operation of modulo (·)_{p} and (·)_{N} for mathematical notation simplicity. The peak signal can be represented by summing the corresponding components of and ,
The subsequent analysis are based on the following conditions:
• The OFDM timedomain data {x_{n}} and the regenerated data are mutually independent for different n and therefore it is also easy to show that and if m ≠ n;
• The channel taps {h_{l}} are independent complex Gaussian random variables with zero mean and variance and mutually independent of the channel estimation errors {Δh_{l}}. Also, ;
• For analytical simplicity, we assume that the LPs mitigated by the proposed method carry most of channel energy such that .
The average power of the peak can be obtained by
where
Similarly, the noise term associated with the peak can be written by
where and have the distribution,
Considering the above conditions and assumptions, we can derive the average power of by
where M is the number of mitigated LPs and
Based on the results of (41) and (43), the SINR of the proposed direct path detection is given by
Equation (45) is quite complicated as it consists of too many parameters. To be more intuitive, we can make the following simplification given some practical considerations. For practical communication systems where error correction coding is adopted, we can obtain accurate data detection and hence regeneration, e.g., . With the accurate estimation of the data, we have
Therefore, (45) can be simplified by
Recall the SINR of the conventional correlationbased estimator in (6), the SINR gain provided by the proposed method can be represented by,
where the term can be approximated to the inverse SNR due to the weak strength of the direct path. The term is significantly smaller than the inverse SNR and therefore neglected. An upper bound of the SINR gain is given by
Since we have N ≪ p, significant SINR gain can be expected. This conclusion will be further verified through computer simulations in the following section.
Simulation results and discussions
Numerical simulations have been carried out to quantify the performance of each block of the proposed system as well as the overall system. The demonstration system considered is an OFDMbase communication system with total number of subcarriers 512 and CP ratio of 1/16. The preamble signal is an msequence with length 15. The modulation scheme is 4QAM. We consider three different propagation scenarios. 8tap multipath channels with each path independently Rayleigh fading. The average power delay profiles are reported in Table 1. Channel I is a modified 3GPPLTE Extended Pedestrian A (EPA) channel model [42] where the strongest direct path has been replaced by a significantly weaker path, representing the obstruction in dense multipath environments. The power of the direct path is set to around 20 dB below the strongest LP. Channel II is a variation of Channel I with a stronger direct path. Channel III has a very short delay spread which is close to AWGN case. It should be noted that the propagation environments considered in this section are just several specific examples since our purpose is to verify the performance of the proposed algorithm in dense multipath environments.
Table 1. Average power delay profiles of multipath channels
Performance of the joint iterative estimator
We first evaluate the performance of the joint iterative estimator in Section ‘Iterative estimator for joint channel estimation and data detection’. The mean square error (MSE) of channel estimation is simulated under Channel I and plotted in Figure 2. It can be observed that the accuracy of channel estimation improves with an increase in the number of iterations. The iterative estimator converges rapidly and in fact only a marginal improvement can be found between the two iterations and three iterations. It is shown that only one iteration is needed to achieve the lower bound at high SNRs. The reason is that the improvement in MSE depends on the reliability of data detection results as derived in (22). At extremely low SNRs, the SER of iterative estimator is significantly high such that the dataaided method can be deteriorated by the large portion of data decision errors. Therefore, only limited improvement can be achieved over the previous iteration. On the contrary, at high SNRs where we can assume accurate or nearperfect data detection, a perfect enhanced preamble can be constructed from the initial estimation such that only one iteration is sufficient to achieve the lower bound. The characteristics of the iterative estimator indicates a good agreement with the theoretical analysis. Therefore, an automatic stopping criterion is needed especially for the batterypowered mobile devices to control the number of iterations in order to avoid unnecessary computation.
Figure 2. Mean square error of channel estimation of the iterative estimator for the OFDM system with 4QAM modulation under Channel I. The label “0 iteration” indicates that the initial estimation given by (7). The lower bound is achieved when the transmitted OFDM data is perfectly detected and regenerated.
The SER of data detection of the iterative estimator under Channel I and Channel III is shown in Figure 3. Good SER performance can be achieved with only 1 iteration under both channel conditions. The performance under Channel III serves as a benchmark due to its short maximum delay spread and therefore the performance is close to onetap channel. As for Channel II, the SER can achieve 10^{−3} at approximately 25 dB. Furthermore, the SERs in Figure 3 can be further reduced by the use of error correction coding in practical communication systems. Therefore, it can be demonstrated that the iterative estimator is capable of providing accurate channel and data estimation results for multipath interference cancelation purpose.
Figure 3. Symbol error rate of the iterative estimator for the OFDM system with 4QAM modulation under Channel I and Channel III.
The MSE of the iterative estimator has been analyzed as a monotonous function of the SER. To verify the theoretical results, we substitute the SERs from simulations (the red solid curve in Figure 3) into (21) and obtain the corresponding theoretical MSE. It is compared with the simulated MSE in Figure 4. The observation implies that the theoretical results match the simulation results well.
Figure 4. Comparison between simulations and theoretical values of MSE versus SER.
Impact of the automatic stopping criterion design
The impact of the threshold factor ϵin (29) is evaluated. The MSE degradation of different threshold factors is shown in Figure 5 and compared with 10 iterations. It can be found that the lower threshold we set, the better MSE we can achieve. Consequently, the lower threshold also requires more computations as shown in Figure 6. The threshold factor ϵ = 0.001 leads to more than 6 iterations at low SNRs and 2 iterations at high SNRs. However, only 1 iteration is needed for ϵ = 0.1 throughout the whole SNR range.
Figure 5. Mean square error of channel estimation of the iterative estimator with different stopping criterion thresholds. The performance is simulated under Channel I. The MSE after 10 iterations is also presented as benchmark.
Figure 6. The average number of iterations with different stopping criterion thresholds.
Performance of the proposed direct path detection method
The SINR of the direct path detection under Channel I and Channel II is shown in Figure 7. Due to the weak strength of the direct path, the SINR is extremely low for both propagation scenarios with the use of the conventional correlationbased estimator. It is obvious that such as a low SINR level cannot achieve acceptable accuracy of the direct path detection. However, as analyzed in Section ‘Performance analysis of the proposed direct path detection method’, the SINR significantly improves with the proposed detection algorithm using the multipath interference cancelation and dataaided methods. With as few as one iteration of the iterative estimator, the interference components from the LPs can already be largely removed from the received signal. Results show that our proposed techniques can achieve approximately 20 and 16 dB gain over the conventional scheme under Channel I and Channel II, respectively. In practical indoor or urban environments, the channel conditions can be much better than these specific models and therefore higher SINR can be expected. For example, in [43], the author pointed out that the penetration loss can vary around 10 dB for typical urban office buildings. In this case, the proposed method is capable of providing sufficient gain to overcome the severe attenuation in dense multipath environments.
Figure 7. Comparison of SINR between the poposed direct path detection method and the classical correlationbased estimator. Channel I and Channel II are considered. The label “Classical” indicates the classical correlationbased estimator. The label “MIC+DA” represents the proposed algorithm using multipath interference cancelation and dataaided method.
The error probability of the direct path detection under Channel I and Channel II is shown in Figure 8. Since it has been proved that the error probability of the direct path detection is a monotonous function of the SINR. As expected, the error probability is substantially reduced by using the proposed method. Again, the performance of the proposed method in these extremely bad environments also demonstrates its feasibility and effectiveness in practical conditions.
Performance of TOAbased positioning system using the proposed method
We now study the impact of our proposed algorithm on TOAbased positioning system under a more realistic signal propagation scenario. We evaluate the root mean square error (RMSE) of the TOA estimation with different strength of the direct path. A 60tap multipath channel is adopted where four LPs are randomly generated in the tap range of [20,59]. Different strength of the direct path is considered and labeled in the figure. The average power of the LPs is also randomly chosen and normalized to , where is the average power of the direct path. To obtain the initial channel estimation, the duration of the preamble is also increased to 63 samples. The unit of the root mean square error of the TOA is normalized to the sample period. From Figure 9, a significant gain of the proposed method over the conventional estimator is observed in all cases. The TOA estimation error is less than one sample at high SNRs with the proposed detection method. Furthermore, as expected, the gap between the proposed method and the conventional estimator becomes smaller as the strength of the direct path increases.
Figure 9. Comparison of root mean square error of the TOA estimation between the proposed method and the classical correlationbased estimator under a realistic signal propagation scenario.
Numerical results of the TOAbased positioning system using our proposed algorithm are shown in Figure 10. The simulation environment of the TOAbased positioning system is shown in Figure 11. Four synchronized reference stations are assumed to be located at (0,0),(0,500),(500,0) and (500,500) (in meters). This is based on the wellknown fact that placing the reference stations along the boundary of the location area provides better performance. The receiver location is randomly generated in the location area. The 3D coordinates of the receiver are calculated by solving the following nonlinear equation system:
where t_{i} is the relative signal propagation time from the ith reference station to the receiver which can be obtained by the proposed algorithm and Δtis the timing difference between the unknown reference stations’ network time and the receiver’s local clock, The propagation model in Figure 9 is used. The sample period is assumed to be 5 ns such that the maximum channel delay spread is around 300 ns [43]. The average power of the direct path is −21 dB and the SNR 15 dB. Each circle or star represents one round of location process (Stars are the results of the proposed algorithm). Figure 10 shows the distance between the estimation and the true location (origin of the coordinates) of the receiver. The simulation results indicate that the accuracy of the TOAbased positioning system using the proposed direct propagation path detection algorithm is within several meters while for the positioning system based on the conventional estimator, this value is as large as thirty meters.
Figure 10. Numerical results of the TOAbased positioning system using the proposed direct path detection method. The location area is a square with dimensions of 500×500 m^{2}.
Figure 11. TOAbased positioning system using four synchronized reference stations in typical indoor office environment.
Conclusion
A new direct path detection method using multipath interference cancelation scheme for TOA estimation is proposed for wireless communicationbased positioning systems. Based on the channel estimation and data detection results provided by the proposed iterative estimator, the interference from later arriving multipath components is reconstructed and removed from the original received signal. Performance of the proposed algorithm is evaluated through mathematical analysis and computer simulations. It is shown that the proposed algorithm is capable of improving the performance of direct path detection substantially with low complexity in dense multipath environments.
Endnotes
^{a}In data communication systems, the signal template can be a training sequence which is originally designed for multiple access, synchronization or channel estimation purposes.^{b}In [24], the authors demonstrated the error probability of the direct path detection is a monotonously decreasing function of the SINR. Therefore, to be more intuitive, we characterize the performance of the proposed direct path detection in terms of the SINR.
Appendix
Derivation of equation (21)
As observed from (20), due to the trace operation, we only concern the elements on the main diagonal of . Thus it can be written in detail as
It is straightforward to check that for any , , ΔX_{im} and ΔX_{jn}, they are mutually independent when (i,m) ≠ (j,n), then the expectation of (50) can be subsequently obtained by
For simplicity, we drop the subscripts and therefore can be represented as
Note the values of may vary depending on the modulation scheme and its corresponding signal constellation. Let P_{e} denote the SER of the iterative estimator. We can make further simplifying assumptions that a nearest neighbor selection is adopted when making symbol detection errors. For a particular point in a given signal constellation, assume that there are m nearest neighboring points with distance , each equally likely to occur when an decision error has occurred. We also assume zero conditional error probability to nonnearest neighboring points. For instance, if an MPSK constellation is used, then we have m = 2 and d = 2sin(Π/M). For QPSK constellation, this yields . Under these assumptions, we have
which yields
Therefore, and can be finalized by
It should be noted that there is no closed form expression for . Therefore, it can only be obtained through numerical calculations. For instance, for a known MPSK constellation , considering a particular point X = α_{k}, then the erroneous decision falls into its neighboring points {α_{k−1},α_{k + 1}} and the corresponding set of the error is with equal probability. Hence, can be defined as
consequently, can be achieved by
Substituting (51), (56), and (58) into (20) yields
Under the assumption that the overhead of the preamble signal is small, i.e., p ≪ N, (59) can be further simplified to
We also assume a moderate P_{e}and the last term consisting of in (60) can be neglected and therefore, (60) can be further simplified to
Abbreviations
GPS: Global Positioning System; WLAN: wireless local area network; DTV: digital television; UWB: ultrawide bandwidth; TOA: timeofarrival; LP: later path; OFDM: Orthogonal FrequencyDivision Multiplexing; SINR: signaltonoiseinterference ratio; GI: guard interval; ISI: intersymbol interference; AWGN: additive white Gaussian noise; LS: Least Square; EPA: Extended Pedestrian A; MSE: mean square error; SER: symbol error rate.
Competing interests
The authors declare that they have no competing interests.
Acknowledgements
This study was supported in part by Western Innovation Fund and Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant R4122A02 and ETRI Project KI002167.
References

ED Kaplan, Understanding GPS: Principles and Applications (Artech House, Norwood, Mass, USA, 1996)

A Conti, U Ferner, A Giorgetti, MZ Win, D Dardari, Ranging with ultrawide bandwidth signals in multipath environments. Proc. IEEE 97(2), 404–426 (2009)

FCC, Revision of the commission’s rules to ensure compatibility with enhanced 911 emergency calling system. ET Docket No, 94–102 (1996)

AH Sayed, A Tarighat, N Khajehnouri, Networkbased wireless location: challenges faced in developing techniques for accurate wireless location information. IEEE Signal Process. Mag 22(4), 24–40 (2005)

L Cong, W Zhuang, Hybrid TDOA/AOA mobile user location for wideband CDMA cellular systems. IEEE Trans. Wirel. Commun 1(3), 439–447 (2002). Publisher Full Text

JJ Caffery, GL Stüber, Subscriber location in CDMA cellular networks. IEEE Trans. Veh. Technol 47(2), 406–416 (1998). Publisher Full Text

P Prasithsangaree, P Krishnamurthy, PK Chrysanthis, On indoor position location with wireless LANs. in Proc, ed. by . 13th IEEE Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC’02), vol. 2, (Lisboa, Portugal, 2002), pp. pp. 720–724

X Wang, Y Wu, JY Chouinard, A new position location system using DTV transmitter identification watermark signals. EURASIP J. Appl. Signal Process 2006, 1–11 (2006, Article ID 42737)

S Gezici, HV Poor, Position estimation via ultrawideband signals. Proc. IEEE 97(2), 386–403 (2009)

Y Shen, MZ Win, Fundamental limits of wideband localization—part i: a general framework. IEEE Trans. Inf. Theory 56(10), 4956–4980 (2010)

Y Shen, H Wymeersch, MZ Win, Fundamental limits of wideband localization – part ii: Cooperative networks. IEEE Trans. Inf. Theory 56(10), 4981–5000 (2010)

MZ Win, A Conti, S Mazuelas, Y Shen, WM Gifford, D Dardari, M Chiani, Network localization and navigation via cooperation. IEEE Commun. Mag 49(5), 56–62 (2011)

N Patawari, JN Ash, S Kyperountas, AO Hero, RL Moses, Locating the nodes: cooperative localization in wireless sensor networks. IEEE Signal Process. Mag 22(4), 54–69 (2005)

Y Qi, H Kobayashi, H Suda, On timeofarrival positioning in a multipath environment. IEEE Trans. Veh. Technol 55(5), 1516–1526 (2006). Publisher Full Text

JY Lee, AR Scholtz, Ranging in a dense multipath environment using an UWB radio link. IEEE J. Sel. Areas Commun 20(9), 1677–1683 (2002). Publisher Full Text

HL Van Trees, Detection, Estimation, and Modulation Theory (John Wiley & Sons, Inc., New York, USA, 1968)

X Li, K Pahlavan, Superresolution TOA estimation with diversity for indoor geolocation. IEEE Trans. Wirel. Commun 3(1), 224–234 (2004). Publisher Full Text

T Manabe, H Takai, Superresolution of multipath delay profiles measured by PN correlation method. IEEE Trans. Antennas Propagat 40(5), 500–509 (1992). Publisher Full Text

F Bouchereau, D Brady, C Lanzl, Multipath delay estimation using a superresolution PNcorrelation method. IEEE Trans. Signal Process 49(5), 938–949 (2001). Publisher Full Text

I Guvenc, Z Sahinoglu, Thresholdbased TOA estimation for impulse radio UWB systems. in Proc, ed. by . IEEE Int. Conf. UltraWideband, 2005 (ICU’05) (Zurich, Switzerland, 2005), pp. pp. 420–425

P Cheong, A Rabbachin, J Montillet, K Yu, I Oppermann, Synchronization, toa and position estimation for lowcomplexity LDR UWB devices. in Proc, ed. by . IEEE Int. Conf. UltraWideband, 2005 (ICU’05) (Zurich, Switzerland, 2005), pp. pp. 480–484

AA D’Amico, U Mengali, L Taponecco, Energybased TOA estimation. IEEE Trans. Wirel. Commun 7(3), 838–847 (2008)

I Guvenc, Z Sahinoglu, TOA estimation with different IRUWB transceiver types. in Proc, ed. by . IEEE Int. Conf. UltraWideband, 2005 (ICU’05) (Zurich, Switzerland, 2005), pp. pp. 426–431

D Dardari, CC Chong, MZ Win, Thresholdbased timeofarrival estimators in UWB dense multipath channels. IEEE Trans. Commun 56(8), 1366–1378 (2008)

B Alavi, K Pahlavan, Modeling of the TOAbased distance measurement error using UWB indoor radio measurements. IEEE Commun. Lett 10(4), 275–277 (2006). Publisher Full Text

C Falsi, D Dardari, L Mucchi, MZ Win, Time of arrival estimation for UWB localizers in realistic environments. EURASIP J. Appl. Signal Process. vol. 2006 (2006, Article ID 32082) (pp), . 1–13

C Xu, CL Law, Delaydependent threshold selection for UWB TOA estimation. IEEE Commun. Lett 12(5), 380–382 (2008)

S Gezici, Z Sahinoglu, AF Molisch, H Kobayashi, HV Poor, Twostep time of arrival estimation for pulsebased ultrawideband systems. EURASIP J. Adv. Signal Process. vol. 2008 (2008, Article ID 529134) (pp), . 1–11

Z Sahinoglu, I Guvenc, Multiuser interference mitigation in noncoherent UWB ranging via nonlinear filtering. EURASIP J. Wirel. Commun. Network 2006, 1–10 (2006) (Article ID 56849)

J Yang, X Wang, SI Park, HM Kim, A novel first arriving path detection algorithm using multipath interference cancellation in indoor environments. in Proc, ed. by . IEEE 72nd Veh. Technol. Conf. (VTC’10 Fall) (Ottawa, Canada, 2010), pp. pp. 1–5

T Hwang, C Yang, G Wu, S Li, GY Li, OFDM and its wireless applications: a survey. IEEE Trans. Veh. Technol 58(4), 1673–1694 (2009)

DV Sarwate, B Pursley, Cross correlation properties of pseudorandom and realted sequences. Proc. IEEE 68, 593–619 (1980)

F Tufvesson, O Edfors, M Faulkner, Time and frequency synchronization for OFDM using PNsequence preambles. in Proc, ed. by . IEEE 50th Veh. Technol. Conf. (VTC ’99Fall), vol. 4 (Amsterdam, Netherlands, 1999), pp. pp. 2203–2207

H Puska, H Saarnisaari, Matched filter time and frequency synchronization method for OFDM systems using PNsequence preambles. in Proc, ed. by . 18th IEEE Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC ’07) (Athens, Greece, Sep. 2007), pp. pp. 1–5

JJ Beek, O Edfors, M Sandell, SK Wilson, PO Börjesson, On channel estimation in OFDM systems”. in Proc, ed. by . IEEE 45th Veh. Technol. Conf. (VTC ’95), vol. 2 (Chicago, IL, 1995), pp. pp. 815–819

H Li, SM Betz, HV Poor, Performance analysis of iterative channel estimation and multiuser detection in multipath DSCDMA channels. IEEE Trans. Signal Process 55(5), 1981–1993 (2007)

H Minn, VK Bhargava, KB Letaif, A robust timing and frequency synchronization and channel estimation for OFDM. IEEE Trans. Commun 2(4), 822–839 (2003)

I Guvenc, CC Chong, F Watanabe, NLOS identification and mitigation for UWB localization systems. in Proc, ed. by . IEEE Wireless Commun. Netw. Conf. 2007 (WCNC’07) (Kowloon, HongKong, 2007), pp. pp. 1573–1578

MP Wylie, J Holtzman, The nonline of sight problem in mobile location estimation. in Proc, ed. by . 5th IEEE Conf. Universal Pers. Commun. 1996 (Cambridge, MA, 1996), pp. pp. 827–831

R Casas, A Marco, JJ Guerrero, J Falco, Robust estimator for nonlineofsight error mitigation in indoor localization. EURASIP J. Appl. Signal Process. vol. 2006 (2006, Article ID 43429) (pp), . 1–8

S Marano, WM Gifford, H Wymeersch, MZ Win, NLOS identification and mitigation for localization based on UWB experimental data. IEEE J. Sel. Areas Commun 28(7), 1026–1035 (2010)

Evolved universal terrestrial radio access (EUTRA); user equipment (UE) radio tranmission and reception (Release 8), Technical Specification, 3GPP (TR 36.803), Sophia Antipolis, France (2007)

D Molkdar, Review on radio propagation into and within buildings. IEE Proc. H: Microwaves Antennas Propagat 138(1), 61–73 (1991). Publisher Full Text