# Maximum Likelihood Time Delay Estimation Based on Monte Carlo Importance Sampling in Multipath Environment

Authors: Bin Ba; Weijia Cui; Daming Wang; Jianhui Wang
Journal: International Journal of Antennas and Propagation
 (2017)

---

## Abstract

In multipath environment, the computation complexity of single snapshot maximum likelihood for time delay estimation is huge. In particular, the computational complexity of grid search method increases exponentially with the increase of dimension. For this reason, this paper presents a maximum likelihood estimation algorithm based on Monte Carlo importance sampling technique. Firstly, the algorithm takes advantage of the channel frequency response in order to build the likelihood function of time delay in multipath environment. The pseudoprobability density function is constructed by using exponential likelihood function. Then, it is crucial to choose the importance function. According to the characteristic of the Vandermonde matrix in likelihood function, the product of the conjugate transpose Vandermonde matrix and itself is approximated by the product of a constant and an identity matrix. The pseudoprobability density function can be decomposed into product of many probability density functions of single path time delay. The importance function is constructed. Finally, according to probability density function of multipath time delay decomposed by importance function, the time delay of the multipath is sampled by Monte Carlo method. The time delay is estimated via calculating weighted mean of sample. Simulation results show that the performance of proposed algorithm approaches the Cramér-Rao bound with reduced complexity.


---

## Body

## 1. Introduction

The time delay estimation problem has always been a hot topic in wireless communications and is widely applied in radar [1], sonar [2], wireless communication system [3], and other fields. In multipath environments, the time delay estimation schemes for single snapshot narrowband signal using super resolution algorithms show good estimation performance. Generally, the super resolution algorithms mainly include two categories: the subspace estimation algorithm and the maximum likelihood (ML) estimation algorithm. To be specific, the subspace estimation algorithms include multiple signal classification (MUSIC) algorithm [4, 5], the root of MUSIC algorithm [6], and estimation of signal parameters via rotational invariance techniques (ESPRIT) algorithm [7]. Under the condition of single snapshot, these algorithms adopt smoothing in frequency domain in order to make autocorrelation matrix transformed into singular matrix. As a consequence, the effective bandwidth becomes narrow, which will lead to the result that mean square error (MSE) of the time delay estimation cannot be close to the Cramér-Rao bound (CRB).The ML estimator is an asymptotically best estimator and has the best estimation performance under the condition of the limited samples. Since the multidimensional likelihood function is a nonlinear function of time delays and has many local maxima, the exact ML estimate needs multidimensional grid search. However, the corresponding estimation accuracy is limited by the search interval, and the computational complexity increases exponentially with the increasing dimension. In order to reduce the complexity, the realization method of the ML estimation can adopt the iterative algorithm, such as the expectation maximization algorithm [8], but the iterative algorithm requires that the initial value must be close enough to the unknown parameters which will be estimated. Otherwise, the iterative algorithm will converge to local maxima of the likelihood function. In addition, the iterative algorithm uses multiple initial values to improve the performance. Accordingly, the iterative algorithm converges to the global maxima at the cost of high computational complexity. For this reason, literature [9] adopted Monte Carlo (MC) importance sampling to determine the ML estimation of time delay under the condition of no data assistance. This algorithm does not need iterative calculation, but it can only be applied to the single path scenario. Literature [10] used MC importance sampling to complete ML time delay estimation under the condition of multipath. The algorithm needs the known reference signal in frequency domain and cannot be directly applied to general time delay estimation model. The iterative expectation maximization algorithm was investigated [11]. However, it is sensitive to initialization value and has the problem of converging to local optimal value.In this paper, the time delay likelihood function under the condition of multipath is deduced by using channel frequency response. The normalized pseudoprobability density function is established. The importance function (IF) is given according to the properties of the normalized pseudoprobability density function and is sampled by using MC method. The time delays can be estimated by calculating the mean of the samples. Finally, the simulation results present the performance comparisons of the proposed algorithm, MUSIC algorithm, and the grid search ML algorithm.The symbols and the operators used in the paper are as follows:·Τ denotes a transpose; ·∗ represents a conjugated matrix; ·H represents a conjugate transpose; E· means an expectation.


## 2. Signal Model

In the process of electromagnetic wave propagation, the radio channel impulse response under the condition of the multipath can be modeled as(1)ht=∑i=0LP-1aiδt-τi,where LP is the number of the multipath components, ai=aiejφi is the complex fading coefficient of the ith multipath component, ai presents the amplitude, φi means the phase and obeys a uniform distribution U0,2π [5], τi denotes the time delay for the ith multipath component, and δ represents the Dirac delta function.Let us take the Fourier transform of (1). Then, the channel frequency response can be represented as(2)Hf=∑i=0LP-1aie-j2πfτi.It is common practice that channel frequency response is used for time delay estimation. The discrete sampling of the channel frequency response in different systems can be obtained by different methods. For example, multicarrier demodulation technique is used in Orthogonal Frequency Division Multiplexing (OFDM) system, and the received signal deconvolution method is used in direct sequence spread spectrum system, and so forth.The discrete measurement data is obtained by sampling the channel frequency responseHf at L equally spaced frequencies. Considering the impact of the additive white noise in the measurement process, we can express the sampled discrete channel frequency response as(3)xk=Hk+wk=∑i=0LP-1aie-j2πfc+kΔfτi,where k=0,1,…,K-1, fc is the carrier frequency, Δf denotes the frequency sampling interval, and wk represents the additive white noise with the zero mean and variance σ2.The vector form of the signal model can be represented as(4)x=H+w=Vα+w,where x=x0,x1,…,xK-1T and H=H0,H1,…,HK-1T are the channel frequency response estimation vector and frequency response vector, respectively, Vτ=vτ0,vτ1,…,vτLP-1, vτ=1,e-j2πΔf1τ,…,e-j2πΔfK-1τT, α=α0,α1,…,αLP-1T contains the modified complex fading coefficients, αi=aie-j2πfcτi, and w=w0,w1,…,wK-1T is the additive Gaussian white noise vector.According to (4) and noise related assumptions, the likelihood function of a single snapshot for time delay estimation can be expressed as(5)px∣τ,α=12πKσ2/2Ke-1/σ2x-VαHx-Vα.The ML time delay estimate τ^ can be expressed as(6)τ^,α^=argτ,α⁡max⁡px∣τ,α.Note that px∣τ,α is the joint distribution function of both τ and α, and α is a quadratic function. The analytical expression of α with respect to τ can be obtained by calculating partial derivatives:(7)α^=VHV-1VHx.We substitute (7) into (5), take the logarithm, and remove the constant parts. Then, likelihood function with respect to τ can be obtained as(8)Lτ=xHVVHV-1VHx.


## 3. Time Delay Estimation Algorithm Based on Importance Sampling

In ML time delay estimation algorithms, the computational complexity of the multidimensional grid search increases exponentially with the increase of the dimension, and estimation accuracy is limited by search intervals. The iterative algorithms require that the initial values be close to the estimated unknown parameters. Otherwise, they cannot guarantee the convergence to the global maximum. The MC algorithm converts the search of the global maxima into the expectations of a random variable. In the process of practical calculations, the expectation of a random variable can be replaced by the sample mean. Importance sampling is the most commonly used sampling method in classical MC methods and approaches the global maximum. Furthermore, the computational complexity does not increase exponentially with the increase of dimension of the likelihood function. The key of importance sampling is the selection of importance function. In order to reduce the estimation error, importance function should be similar to the original probability distribution. In addition, samples should be easily extracted from the importance function for implementation convenience.In the following sections, the global maxima of likelihood function will be first introduced. Then, importance function and the random sampling method are derived. Finally, the algorithmic steps and the computational complexity analysis are presented.


### 3.1. Global Maxima of Likelihood Function

In order to make the sample averages approximate the global maxima of corresponding parameters, we can make the distribution function more accurate to adopt the exponential for the likelihood functionLτ [10], which makes the estimation more accurate. The exponential likelihood function is defined as(9)πε0τ=exp⁡ε0Lτ,where ε0 is a constant. The different values of ε0 have significant influence on the distribution characteristics of πε0τ. If ε0 is sufficiently large, then πε0τ will approach the Dirac delta function.According to literature [12], τ^i can be expressed as(10)τ^i=∫J0⋯∫JLP-1τiπε0τdτ∫J0⋯∫JLP-1πε0τ-dτ-,i=0,1,…,LP-1,where ε0→∞; Ji represents the ith time delay search region.Let us define the normalized pseudoprobability density function:(11)fτ=πε0τ∫J0⋯∫JLP-1πε0τ-dτ-.Then, τ^i can be simplified into the following form:(12)τ^i=∫J0⋯∫JLP-1τifτdτ.According to the principle of importance sampling, (12) can be rewritten as(13)τ^i=∫J0⋯∫JLP-1τifτgτgτdτ,where gτ is the importance function.


### 3.2. Importance Function

The choice of importance functiongτ will affect the estimation accuracy in the proposed algorithm. gτ is selected as close as possible to fτ, and τ should be easily sampled from gτ.For the matrixVHV, (14)VHVi,j=∑k=0K-1ej2πkΔfτi-τj.If i=j, VHVi,j=K; if i≠j, VHVi,j<K. Therefore, we can obtain (15)VHV≈KILP,where ILP represents the LP×LP identity matrix. Then, Lτ≈(1/K)xHVILPVHx=(1/K)xHVVHx.Suppose(16)πε1′τ=exp⁡ε1xHVVHx=∏i=0LP-1exp⁡ε1Iτi,where ε1 is a constant coefficient and Iτi=∑k=0K-1xkj2πkΔfτi2. Define the importance function as(17)gτ=πε1′τ∫J0⋯∫JLP-1πε1′τ-dτ-=∏i=0LP-1qiτi,where qiτi=exp⁡ε1Iτi/∫Jiexp⁡ε1Iτ-idτ-i. The size of ε1 determines the distribution of the importance function samples. The corresponding sample is monotonically decreasing with respect to ε1. As a consequence, the choice of ε1 should be moderate.The MC method is an effective calculation method for the integral. It recasts the definite integral as a mathematical expectation of a random variable. As long as one can realize the sampling of the random variable, it can be effectively solved. By substituting the sampling average for the integral using the MC importance sampling method, we can expressτ^i as(18)τ^i=1M∑m=0M-1τimFτm,where τim is a random sample for the importance function gτ, Fτm=fτm/gτm, and M denotes the number of generated random samples.Due to the delay range,τi∈0,Tmax, where i=0,1,…,LP-1; the parameter τi has upper and lower bounds. According to [10], the linear mean can be converted to the sample circular mean. Consequently,(19)τ^i=Tmax2π∠1M∑m=0M-1Fτmexp⁡j2πτimTmax,where ∠ represents the angle of a complex number.In (19), only τim/Tmax affects the cycle average. Any positive multiplication item does not affect the final result. Therefore,∫J0⋯∫JLP-1πε0τ-dτ- and ∫J0⋯∫JLP-1πε1′τ-dτ- for the normalized positive multiplication item can be ignored. Meanwhile, in order to avoid Fτm overflow, Fτm can be replaced by F′τm:(20)F′τmexp⁡ε0Lτ-ε1K∑i=0LP-1Iτi-maxτi∈J,0≤i≤LP-1⁡ε0Lτ-ε1K∑i=0LP-1Iτi.


### 3.3. Random Sampling Method

In order to achieve random sampling, importance function needs to be computed as shown in (17). Therefore, it is necessary to replace the integral with the sum of discrete points. In Ji,N points are discretely sampled and noted as Ji=μi,1,μi,2,…,μi,N. The normalized probability density function can be expressed as(21)qiμi,n=exp⁡ε1Iμi,n∑l=1Nexp⁡ε1Iμi,l,where n=1,2,…,N.We can generateτi according to qiμi,n by using the inverse probability integration method. To be specific, we firstly generate a random variables vector ui=ui,1,ui,2,…,ui,M uniformly distributed over U0,1. Then, we compute τi=Fi-1μi,m, where Fi-1· is the inverse of the cumulative distribution function associated with qiμi,n. According to (21), the cumulative distribution function can be expressed as(22)Fiμi,n=∑l=1nexp⁡ε1Iμi,l∑l=1Nexp⁡ε1Iμi,l,where n=1,2,…,N.The closed-form expression for the inverse functionFi-1x is not easy to derive. We can obtain the sampling equation of τim for the mth sample by(23)τim=argμi,n∈Ji⁡min⁡Fiμi,n-μi,m.


### 3.4. Algorithm Flow

According to the above derivation and analysis, the processes of the proposed algorithm can be summarized as follows.Step 1.
Under the condition of a discrete setJi=μi,1,μi,2,…,μi,N, i=0,1,…,LP-1, calculate probability cumulative distribution function according to (22).Step 2.
Generate the vectorui=ui,1,ui,2,…,ui,M by using the uniform distribution U0,1.Step 3.
According to (23),M samples of τim can be obtained, where m=1,2,…,M.Step 4.
Substitute the samplesτim into (19) and (20). Then, one can obtain the estimate τ^i of τi.


## 3.1. Global Maxima of Likelihood Function

In order to make the sample averages approximate the global maxima of corresponding parameters, we can make the distribution function more accurate to adopt the exponential for the likelihood functionLτ [10], which makes the estimation more accurate. The exponential likelihood function is defined as(9)πε0τ=exp⁡ε0Lτ,where ε0 is a constant. The different values of ε0 have significant influence on the distribution characteristics of πε0τ. If ε0 is sufficiently large, then πε0τ will approach the Dirac delta function.According to literature [12], τ^i can be expressed as(10)τ^i=∫J0⋯∫JLP-1τiπε0τdτ∫J0⋯∫JLP-1πε0τ-dτ-,i=0,1,…,LP-1,where ε0→∞; Ji represents the ith time delay search region.Let us define the normalized pseudoprobability density function:(11)fτ=πε0τ∫J0⋯∫JLP-1πε0τ-dτ-.Then, τ^i can be simplified into the following form:(12)τ^i=∫J0⋯∫JLP-1τifτdτ.According to the principle of importance sampling, (12) can be rewritten as(13)τ^i=∫J0⋯∫JLP-1τifτgτgτdτ,where gτ is the importance function.


## 3.2. Importance Function

The choice of importance functiongτ will affect the estimation accuracy in the proposed algorithm. gτ is selected as close as possible to fτ, and τ should be easily sampled from gτ.For the matrixVHV, (14)VHVi,j=∑k=0K-1ej2πkΔfτi-τj.If i=j, VHVi,j=K; if i≠j, VHVi,j<K. Therefore, we can obtain (15)VHV≈KILP,where ILP represents the LP×LP identity matrix. Then, Lτ≈(1/K)xHVILPVHx=(1/K)xHVVHx.Suppose(16)πε1′τ=exp⁡ε1xHVVHx=∏i=0LP-1exp⁡ε1Iτi,where ε1 is a constant coefficient and Iτi=∑k=0K-1xkj2πkΔfτi2. Define the importance function as(17)gτ=πε1′τ∫J0⋯∫JLP-1πε1′τ-dτ-=∏i=0LP-1qiτi,where qiτi=exp⁡ε1Iτi/∫Jiexp⁡ε1Iτ-idτ-i. The size of ε1 determines the distribution of the importance function samples. The corresponding sample is monotonically decreasing with respect to ε1. As a consequence, the choice of ε1 should be moderate.The MC method is an effective calculation method for the integral. It recasts the definite integral as a mathematical expectation of a random variable. As long as one can realize the sampling of the random variable, it can be effectively solved. By substituting the sampling average for the integral using the MC importance sampling method, we can expressτ^i as(18)τ^i=1M∑m=0M-1τimFτm,where τim is a random sample for the importance function gτ, Fτm=fτm/gτm, and M denotes the number of generated random samples.Due to the delay range,τi∈0,Tmax, where i=0,1,…,LP-1; the parameter τi has upper and lower bounds. According to [10], the linear mean can be converted to the sample circular mean. Consequently,(19)τ^i=Tmax2π∠1M∑m=0M-1Fτmexp⁡j2πτimTmax,where ∠ represents the angle of a complex number.In (19), only τim/Tmax affects the cycle average. Any positive multiplication item does not affect the final result. Therefore,∫J0⋯∫JLP-1πε0τ-dτ- and ∫J0⋯∫JLP-1πε1′τ-dτ- for the normalized positive multiplication item can be ignored. Meanwhile, in order to avoid Fτm overflow, Fτm can be replaced by F′τm:(20)F′τmexp⁡ε0Lτ-ε1K∑i=0LP-1Iτi-maxτi∈J,0≤i≤LP-1⁡ε0Lτ-ε1K∑i=0LP-1Iτi.


## 3.3. Random Sampling Method

In order to achieve random sampling, importance function needs to be computed as shown in (17). Therefore, it is necessary to replace the integral with the sum of discrete points. In Ji,N points are discretely sampled and noted as Ji=μi,1,μi,2,…,μi,N. The normalized probability density function can be expressed as(21)qiμi,n=exp⁡ε1Iμi,n∑l=1Nexp⁡ε1Iμi,l,where n=1,2,…,N.We can generateτi according to qiμi,n by using the inverse probability integration method. To be specific, we firstly generate a random variables vector ui=ui,1,ui,2,…,ui,M uniformly distributed over U0,1. Then, we compute τi=Fi-1μi,m, where Fi-1· is the inverse of the cumulative distribution function associated with qiμi,n. According to (21), the cumulative distribution function can be expressed as(22)Fiμi,n=∑l=1nexp⁡ε1Iμi,l∑l=1Nexp⁡ε1Iμi,l,where n=1,2,…,N.The closed-form expression for the inverse functionFi-1x is not easy to derive. We can obtain the sampling equation of τim for the mth sample by(23)τim=argμi,n∈Ji⁡min⁡Fiμi,n-μi,m.


## 3.4. Algorithm Flow

According to the above derivation and analysis, the processes of the proposed algorithm can be summarized as follows.Step 1.
Under the condition of a discrete setJi=μi,1,μi,2,…,μi,N, i=0,1,…,LP-1, calculate probability cumulative distribution function according to (22).Step 2.
Generate the vectorui=ui,1,ui,2,…,ui,M by using the uniform distribution U0,1.Step 3.
According to (23),M samples of τim can be obtained, where m=1,2,…,M.Step 4.
Substitute the samplesτim into (19) and (20). Then, one can obtain the estimate τ^i of τi.


## 4. Cramér-Rao Bound

The CRB gives the lower bound of the mean square error of an unbiased estimator. The following model gives the corresponding CRB of time delay estimation. Firstly, we define the unknown parameter vectorσ2τTT.The log-likelihood function is given by(24)ln⁡p≜ln⁡px∣τ,α=-Kln⁡2π-Kln⁡σ22-1σ2x-VαHx-Vα.αRe and αIm represent the real and imaginary parts of α, respectively; that is, αRe=Reα and αIm=Imα. The respective partial derivatives of ln⁡p with respect to σ2, Reα, Imα, and τ, can be obtained as(25)∂ln⁡p∂σ2=-Kσ2+1σ4wHw,∂ln⁡p∂αRe=2σ2ReVHw,∂ln⁡p∂αIm=2σ2ImVHw,∂ln⁡p∂τi=2σ2ReαHdVHdτiw=2σ2Reαi∗dHτiw,i=0,1,…,LP-1,where(26)dτi=dvτidτi=1,-j2πΔfe-j2πΔf1τi,…,-j2πΔfK-1e-j2πΔfK-1τiT.Therefore, the partial derivative ofln⁡p with respect to τi is(27)∂ln⁡p∂τ=2σ2ReAHDHw,where (28)A=α00⋯00α1⋯0⋮⋮⋱⋮00⋯αLP-1,D=dτ0,dτ1,…,dτLP-1.By (25), we can obtain the following results:(29)E∂ln⁡p∂σ22=Kσ4,E∂ln⁡p∂αRe∂ln⁡p∂αReT=2σ2ReVHV,E∂ln⁡p∂αRe∂ln⁡p∂αImT=-2σ2ImVHV,E∂ln⁡p∂αIm∂ln⁡p∂αImT=2σ2ReVHV,E∂ln⁡p∂αRe∂ln⁡p∂τT=2σ2ReVHDA,E∂ln⁡p∂αIm∂ln⁡p∂τT=2σ2ImVHDA,E∂ln⁡p∂τ∂ln⁡p∂τT=2σ2ReAHDHDA.The Fisher information matrix (FIM) isEγγT, where γ=∂ln⁡p/∂σ2τTT. According to FIM and [13], the CRB is given by(30)CRB-1τ=2σ2ReAHDHI-VVHV-1VHDA.


## 5. Simulation Result and Performance Analysis

### 5.1. Simulation Result

Consider an OFDM wireless system where the number of multipaths is two and we analyze and compare the proposed algorithm with the MUSIC time delay estimation algorithm, the grid search ML time delay estimation algorithm, and the CRB [5]. Finally, the computational complexities of the above algorithms are analyzed and compared. The simulation parameter set-up of the OFDM system is shown in Table 1.Table 1
The simulation parameter set-up of the OFDM system.
Parameters Values Guard duration,TG 1.6μs FFT period,TFFT 3.2μs System bandwidth,B 20 MHz The number of subcarriers 64 Carrier frequency,fc 2.4 GHzTo begin with, define the mean square error as(31)ΩMSE=1M∑m=1Mx^m-x2,where x^m indicates the parameter estimate value obtained in the mth simulation, x denotes the true value of the corresponding parameter, and M represents the number of estimates.Simulation 1.
Compare the likelihood function and the exponential likelihood function withε0=1 and ε0=100.As shown in Figure1, compared with the normalized likelihood function, the two-dimensional bend surface is more acute for the normalized exponential likelihood function. From the comparison of Figures 1(b) and 1(c), we can find that the normalized exponential likelihood function approximates a Dirac delta function by increasing of ε0.Figure 1
(a) Normalized likelihood function. (b) Normalized exponential likelihood function withε0=1. (c) Normalized exponential likelihood function with ε0=100.
(a) (b) (c)Simulation 2.
Compare the performances between the proposed algorithm, MUSIC algorithm, and grid search ML algorithm.Parameter Settings. The number of samples M=3000, doing 100 Monte Carlo experiments and taking ε0=100 and ε1=1. The multipath power is unchanged in the simulation process.As shown in Figure2, the MSE of the proposed algorithm, MUSIC algorithm, and grid search ML algorithm all decrease with increasing SNR. The MSE of the proposed algorithm approaches the CRB algorithm and basically corresponds to the performance of grid search ML algorithm. The reason lies in that the importance sampling algorithm uses a weighted average of the sample to approach the global maxima of the objective function. The single snapshot MUSIC algorithm needs to use smoothing in frequency domain to make the autocorrelation matrix singular, which leads to the loss of effective bandwidth and the reduction of the estimation accuracy.Figure 2
(a) Time delay performance comparisons of the 1st multipath component. (b) Time delay performance comparisons of the 2nd multipath component.
(a) (b)


### 5.2. Algorithm Complexity

In this paper, the computational complexity of the proposed algorithm isOLPKN+Mlog2⁡N+MLP2K+LP3+2KLP+LP2+LP. The computational complexity of MUSIC algorithm is OK/22(K/2)+12+K/23+(K/2)Nτ, where Nτ is the number of candidate delay grid points. The computational complexity of the grid search ML algorithm for time delay estimation is LP2K+LP3+2KLP+LP2+LPNτLP. We can see that the computational complexity of the proposed algorithm is slightly higher than that of MUSIC algorithm but is significantly lower than that of grid search ML algorithm.


## 5.1. Simulation Result

Consider an OFDM wireless system where the number of multipaths is two and we analyze and compare the proposed algorithm with the MUSIC time delay estimation algorithm, the grid search ML time delay estimation algorithm, and the CRB [5]. Finally, the computational complexities of the above algorithms are analyzed and compared. The simulation parameter set-up of the OFDM system is shown in Table 1.Table 1
The simulation parameter set-up of the OFDM system.
Parameters Values Guard duration,TG 1.6μs FFT period,TFFT 3.2μs System bandwidth,B 20 MHz The number of subcarriers 64 Carrier frequency,fc 2.4 GHzTo begin with, define the mean square error as(31)ΩMSE=1M∑m=1Mx^m-x2,where x^m indicates the parameter estimate value obtained in the mth simulation, x denotes the true value of the corresponding parameter, and M represents the number of estimates.Simulation 1.
Compare the likelihood function and the exponential likelihood function withε0=1 and ε0=100.As shown in Figure1, compared with the normalized likelihood function, the two-dimensional bend surface is more acute for the normalized exponential likelihood function. From the comparison of Figures 1(b) and 1(c), we can find that the normalized exponential likelihood function approximates a Dirac delta function by increasing of ε0.Figure 1
(a) Normalized likelihood function. (b) Normalized exponential likelihood function withε0=1. (c) Normalized exponential likelihood function with ε0=100.
(a) (b) (c)Simulation 2.
Compare the performances between the proposed algorithm, MUSIC algorithm, and grid search ML algorithm.Parameter Settings. The number of samples M=3000, doing 100 Monte Carlo experiments and taking ε0=100 and ε1=1. The multipath power is unchanged in the simulation process.As shown in Figure2, the MSE of the proposed algorithm, MUSIC algorithm, and grid search ML algorithm all decrease with increasing SNR. The MSE of the proposed algorithm approaches the CRB algorithm and basically corresponds to the performance of grid search ML algorithm. The reason lies in that the importance sampling algorithm uses a weighted average of the sample to approach the global maxima of the objective function. The single snapshot MUSIC algorithm needs to use smoothing in frequency domain to make the autocorrelation matrix singular, which leads to the loss of effective bandwidth and the reduction of the estimation accuracy.Figure 2
(a) Time delay performance comparisons of the 1st multipath component. (b) Time delay performance comparisons of the 2nd multipath component.
(a) (b)


## 5.2. Algorithm Complexity

In this paper, the computational complexity of the proposed algorithm isOLPKN+Mlog2⁡N+MLP2K+LP3+2KLP+LP2+LP. The computational complexity of MUSIC algorithm is OK/22(K/2)+12+K/23+(K/2)Nτ, where Nτ is the number of candidate delay grid points. The computational complexity of the grid search ML algorithm for time delay estimation is LP2K+LP3+2KLP+LP2+LPNτLP. We can see that the computational complexity of the proposed algorithm is slightly higher than that of MUSIC algorithm but is significantly lower than that of grid search ML algorithm.


## 6. Conclusions

In the multipath wireless communication scenario, to alleviate the computational burden of the ML time delay estimation for single snapshot, we have proposed a ML time delay estimation algorithm based on Monte Carlo importance sampling. Meanwhile, we have introduced a normalized pseudoprobability density function, an importance function structure method, a random sampling method, and CRB of the model as well as the analysis of the computational complexity. The algorithm has taken sample for importance function and has used the weighted average of the samples to calculate the time delay estimation. The simulations have shown that the proposed algorithm can significantly reduce the computational complexity and obtain the approximate performance with the ML algorithm of grid search.



---

*Source: 4215293-2017-02-20.xml*