Open access peer-reviewed chapter

Iterative Delay Compensation Algorithm to Mitigate NLOS Influence for Positioning

By Koji Enda and Ryuji Kohno

Submitted: October 22nd 2010Reviewed: April 16th 2011Published: July 20th 2011

DOI: 10.5772/17768

Downloaded: 1641

1. Introduction

Wireless sensor networks are attracting considerable attention in recent years as constituent elements of next-generation wireless networks. Determining the position information of sensor tags is extremely important, and hence, position estimation using RFIDs for sensor networks is a widely studied topic. In order to estimate these RFID tag’s position, TDOA positioning algorithm is focused on because each sensor tag is desirable of plain hardware configuration. Tag’s position is estimated to measure arrival time from tag to some reception nodes. In case of executing positioning process, Sensor tag is not necessary to synchronize with node, it is necessary to synchronize in time domain with only each node. Therefore, these features of TDOA positioning algorithm fulfill that sensor tag should be simple, independent and low power consumption. We use the NEWTON method because of its fast conversion property and its ability to yield the minimum square difference with few computations. The non-line-of-sight (NLOS) problem must be taken into consideration when employing positioning methods that involve the use of time-domain data. The problem is characterized by the fact that in addition to direct waves, reflected or diffracted waves are also incident on the target, resulting in the geometrical stretching of the obtained paths along the normal direction and a positive bias in the travel time. The resulting effect is a difference in the arrival time which, in turn, causes deterioration in the positioning accuracy. In this paper, in order to mitigate the influence of the NLOS propagation, we propose the iterative delay compensation algorithm based on NEWTON algorithm which improves the accuracy of positioning using the DCF and shift vector compensation (SVC) algorithm. In the proposed method, hypothetical coordinates are estimated by using the conventional NEWTON method. Then, the node positions and distances are derived from the estimated coordinate information. DCF is used to compensate for the difference between the calculated reception time and the actual measured time. The propagation delay included in the measured value is reduced step-by-step by repeatedly applying the compensation function. This helps in minimizing the effect on the line-of-sight (LOS) node, resulting in improved positioning accuracy. Next, the estimation accuracy is improved by compensating the influence vector caused by NLOS delays in the temporarily estimated positions by using the node distributions and geometrical relations among the estimated positions. The iterative algorithm using DCF and SVC fulfills high accuracy of positioning even in an NLOS environment. Furthermore, we make an experiment of TDOA tracking system using tag and node. The experiments show that tracking accuracy is improved and abnormal tracking position estimation is reduced.


2. Positioning system model and positioning algorithm

In this section, we state positioning system model of TDOA and a principle of the TDOA positioning algorithm.

2.1. System Model

Let us assume that positioning is to be carried out in a two-dimensional field. The component elements comprise mobile devices defined as tags, which are the targets for positioning, and fixed devices with known positions, defined as nodes. The tags send only signal and nodes receive only messages from the tags. The nodes need be synchronized among themselves. Time distance of arrival information is extracted by means of reception signal from the tags to nodes. In concrete terms, tag sends a signal to each node (xi, yi) [i = 1...M], and calculates the distance difference on the basis of the time required for the signal to receive. Mdenotes the number of nodes. This information is transmitted to the master node where the position is estimated by using signal processing. Signal losses that occur during the signal transmission are not considered. The distance between the nodes and tags is obtained as follows: Let us assume that Tstartis the transmission time, Tris the reception time, and cis the speed of light. The reception time Tifrom the tag to the node is as shown below:

Ti=Tr TstartE1

Then, the propagation distance Diis

Di=c TiE2

Figure 1.

Positioning situation

Since we are assuming that the distance between a node and a tag is calculated on the basis of signal transmission between the two, we can assume that the preamble portion of the packet is used. Distance calculation is based on the synchronization of the preamble. In the case of multiple incoming signals, the time of arrival of the signal taking the longest path is considered to be the reception time.

2.1. Principle of TDOA positioning algorithm

In this section, we show TDOA positioning method.

The positioning system configuration considered in this paper is shown in Fig.2.

Figure 2.

TDOA principle

The number of node is Mand these nodes have the information of position of xi,yi. Each node receives the signal of tag and tag's position is estimated using TDOA of each node. In TDOA system, the synchronization between tag and each node is not necessary. Therefore, the distance information is derived by comparing the received time of nodes and multiplying speed of light.

2.2. NEWTON algorithm

NEWTON algorithm is a linear search and an iterative algorithm. It is the algorithm of converging into true position by deriving the relative shift value from the gradient information. In other words, it starts with an initial guess, and improves the estimate at each step using least-squares. At first, distance difference of arrival (DDOA) Rijcomputed by each combination of nodes is given by

Rij= RiRj= c( titj)i(1,M1), j(2,M), ijE3

where Riis distance between tag and each node, tiis arrival time of each node. First, likelihood computation at arbitrary position P(m0,n0) is performed.


The gradient of Rijevaluated in a initial position is expressed as




And similarly forRijy

Let G be the gradient matrix given by


Let Δ(x,y)be the adjustment matrix defines as


such thatx0Δx+x0,y0Δy+y0. The process is repeated iteratively tillΔ(x,y)(0,0).

2.2. NLOS problem and delay modeling

If there are no differences among the arrival times of the signal from different nodes, the tag positions can be estimated very accurately. However, in general, this is not the case because node clock differences, the time resolution of the devices, and the NLOS problem. NLOS is the geometrical enlargement of the propagation path that occurs because of the presence of obstacles between the transmission and reception points. The fact that only reflected or diffracted waves arrive instead of the direct waves is responsible for the geometrical enlargement of the propagation time and the positive bias in the arrival time. This is illustrated in Fig.3.

This effect causes an error in the measurement of the arrival time, and results in the deterioration of positioning performance. In addition, a reception time error exists at the nodes and is expressed as a Gaussian error (Additive White Gaussian Noise: AWGN). The error is caused by factors such as time resolution limitation, jitter, and internal clock offset; this error also results in the deterioration of positioning accuracy. Therefore, the arrival time tican be written as

ti= T0+TA+ TNE10

Here, T0is the true arrival time, TAis the AWGN error, and TNis the error caused by NLOS. The multiplication of these parameters with cyields distances, and the distance of arrival Riis expressed as

Ri= R0+RA+ RNE11

Here, R0is the arrival distance, RAis the error in the arrival distance, and RNis the error caused by NLOS delay. Hereafter, for the sake of uniformity of units, our analysis will be carried out after converting all time parameters into distances. As previously mentioned, the errors in the distance calculated on the basis of TOA are expressed as AWGN, and their probability density function (PDF) is expressed as a Gaussian function of the form shown below:


Figure 3.

IEEE.802.15.4a propagation PDF CM1(LOS)

Here, σdenotes the variance. The NLOS delay measurements are supposed to be carried out in an indoor environment using UWB (more specifically Home CM1/CM2). The probability distribution function used for modelling delays is the one based on IEEE.802.15.4a for UWB analysis. The actual reception time is the time taken for receiving the waves that travel along the path associated with the largest peak of the received signal. For RN, the sum of the Generalized Extreme Value (GEV) distribution and Lognormal Distribution function (shown in Fig.4) is used for obtaining the LOS (CM1), while the PDF expressed as a Weibull distribution function, shown in Fig.5, is used for NLOS (CM2). Whether the value of RNto be added to the received time in each node is LOS or NLOS depends upon a parameter called NLOS Rate. This parameter is based on the probability that the node is in an NLOS environment

Figure 4.

IEEE.802.15.4a propagation PDF CM2(NLOS)

3. Iterative NLOS delay compensation algorithm and shift vector compensation algorithm

In order to compensate for the time delay caused by NLOS propagation, we consider a procedure in which the delays added to NLOS nodes are compensated in a step-by-step manner; we try to avoid modifying the parameters associated with LOS nodes. First, on the basis of the information obtained from all the nodes, the NEWTON method is used to obtain a preliminary estimate of the coordinates. Then, the transmission time is obtained by reverse calculation by using these coordinates. We assume that the greater the difference between this time value and the measured value, the larger is the effect of NLOS propagation on the measured value. An appropriate function derived using the above results is used to compensate for the time delay. In the absence of an error in the preliminary estimated coordinates, the derived NLOS delay is also correct. However, in practice, there is an error in the preliminary estimated coordinates, and therefore, there is no guarantee that a correct NLOS delay can be estimated if the correction is performed by considering the above-mentioned assumption. As previously mentioned, a naive correction may affect not only NLOS nodes but also LOS nodes, and therefore, the positioning accuracy cannot be improved to a satisfactory level. In order to resolve this problem, positioning estimation is carried out for minimizing the effect of delays on LOS nodes by performing compensation in a step wise manner, starting from large NLOS delays.

3.1. Delay compensation function

In this section, we discuss the modeling of a function that can be used for correcting the NLOS delay. Basically, the propagation time is estimated by calculating the distance from the nodes to the preliminary coordinates of a tag. In addition, the preliminary NLOS delay is obtained by subtracting the distance between the preliminary estimated position and the position of the node from the distance calculated by multiplying the measured time multiplied by the speed of light. Here, the closer the preliminary estimated position is to the true value, the more accurate is the estimated NLOS delay. Therefore, it is not desirable to correct all NLOS delays simultaneously. By correcting large NLOS delays first and then proceeding gradually to smaller NLOS delays, the errors in preliminary estimated positions also decrease in a gradual manner, enabling a more appropriate compensation of the NLOS delay. Below is a more detailed description.

The preliminary NLOS delay (distance) is expressed by the following equations:

DNLOSi= Ri DiE13

As explained in section 2.2 a node under the influence of NLOS has a positive value added to its true arrival time. Therefore, there is a higher probability that the coordinates of preliminary estimated positions shift in a direction opposite to the direction of influence of NLOS. As a consequence, for example, an error in this preliminary estimated position may produce the following influence.

  • DNLOSiof a LOS node on the opposite side of the NLOS node outputs a positive value.

  • DNLOSiof a LOS node on the same side as the NLOS node outputs a negative value.

Therefore, it is difficult to perform adequate compensation simply by correcting the preliminary NLOS delay that is the output here.

Proper compensation requires the setting of a reference value that can be used in the positioning NLOS delay equation. The reference value is expressed as Dbasis, and is changed according to the rules given below:

First, the largest of all DNLOSivalues is selected;

DNLOSmax=max[Ri Di]i=1...ME15

Similarly, smallest of all DNLOSivalues is selected;

DNLOSmin=min[Ri Di]i=1...ME16

As the maximum value approaches the reference value, only DNLOSiof the nodes affected by large NLOS delays tend to assume positive values; this has negligible influence on the LOS nodes. On the other hand, the nodes that are affected by other NLOS delays are not adequately compensated. In contrast, if the reference is close to the minimum value, DNLOSiof almost all the nodes become positive; thus making it possible to compensate for the NLOS delays for all the nodes. However, if the error in the preliminary estimated positions is large, its influence on the LOS nodes tends to be significant. Therefore, by setting the reference value closer to the maximum value DNLOSmax in the first iteration, compensating the NLOS delay, and dynamically setting the reference to values closer to zero, it is possible to correct only the NLOS error and lessen the influence on the LOS nodes since the error in the preliminary estimated positions decreases at later stages. This is shown in equation 17.

Dbasis= DNLOSmax( DNLOSmax DNLOSmin)INkINmaxE17

Here, INmax is the total number of iterations, and INk denotes the k-th iteration. Then, using Dbasis, the equation for the compensation value DCi is reconstructed as

DCi= DNLOSi DbasisE18

The delay compensation function (DCF) for each node DCF(DNLOSi) corrects only the positive component, and is expressed as follows:


This value is arranged such as


and next positioning process is performed using this R’i. Finally, these processes are repeated (INk=1~INmax).

3.2. Compensating the positioning shift resulting from the relative position between node and tag

3.2.1. Basic principle

As previously mentioned, the existence of NLOS delay causes a positive bias to be added to the actual distance, deteriorating the positioning accuracy. However, a problem arises: the bias tends to push the estimated position farther away from the node under consideration and with respect to the actual position. In other words, the effect is similar to that of a vector whose reference is the line joining each node to the tag position. In the present paper, the above vector is referred to as "shift vector". It is possible to partially alleviate this effect by means of the NLOS delay-compensation process on the basis of a DCF. However, if the error associated with the initial estimation that is based on raw information from all nodes is too large, it becomes difficult to alleviate the effect of NLOS in a satisfactory manner. Therefore, it is necessary to alleviate the effect through an analysis of geometrical relations. In addition, enhancing the synergy effect that exists with respect to DCF by improving the precision of the initial positioning estimation, appears to be possible. Hereinafter, the present algorithm is referred to as Shift Vector Compensation (SVC).

3.2.2. Mathematical expression

First, as in the case of the previously mentioned algorithm, TDOA positioning is carried out using raw data obtained from all the nodes. The determined position is Xtem,Ytem. The shift vector that results from a delay originating from an arbitrary node iand jis expressed by the following equation:


This unit vector is expressed as follows:


Similarly, Vj|Vj|is computed, too.

When distance difference of arrival between node A and node B in Fig.6 is computed, if NLOS delay is added into node B, each vector influenced by NLOS is represented as vector aand b. Vector bis the unite vector from position B to TEP and vector ais the unite inverse vector from position A to TEP. Additionally, the sum vector of each unit shift vector is represented as vector c.

Figure 5.

Shift vector principle

Therefore, the resultant shift vector is obtained by a summation of the unit shift vector divided by the number of nodes multiplied by the preliminary NLOS delay. Number of combination of nodes is MC2=M(M-1)/2. Then, the sum of absolute value of all shift vectors is represented as


where this value Zis sum of scalar value. Next, the iteration process of shift vector is performed same as the process using DCF.

DTi=DNLOSi ( DNLOSmaxDNLOSmin)(1INVLINVmax)if(DiT0)DiT=0E25

If DT i is smaller than 0, DT i becomes 0. Therefore, the DT i is the extracted value over basis value. INVLand INVmax denotes the L-th iteration and total iteration number respectively in SVC process.

Therefore, shift vector is represented as

[XsYs]=1MC21ZINVLINVmaxi=1M1j=i+1M(DTiDTj)(Vi|Vi|Vj|Vj|)if(DNLOSi0) DNLOSi=0,  if(DNLOSj0) DNLOSj=0E26

Furthermore, it is possible to further adjust the estimated position to a value closer to the true position by subtracting the shift vector from the estimated position. Next, XSand YSis compensated from Xtemand Ytemrespectively.


The equation (26) and (27) are repeated (INVL=1~INVmax). Finally, compensated position is output.

3.2.2. Embedding into the iterative process

We now describe a method to embed SVC into the iterative process described in the previous section. Basically, the portion used in the SVC was taken after excluding the portion compensated by the delay compensation algorithm. Using compensated arrival distance R’iof equation (20), SVC algorithm is performed. In other words, this equation shows that as the iterative process advances, the portion to be compensated by using SVC decreases with an increase in the compensation by using DCF. In addition, because of the synergy effect of the iterative DCF and SVC, delay compensation is more effective than that achieved by these methods separately, possibly resulting in better estimation accuracy.

4. Simulation

A simulation is carried out to compare the different approaches presented so far. Shown below is a description of the simulation method used. A comparison is carried out among the iterative algorithm using the DCF function (referred to as Iteration), the SVC algorithm, and a combination of the iterative algorithm and SVC (referred to as Iterative SVC)

The structure of the room may be a conventional cube or cuboid; in either case, from a geometrical perspective, the effect is more pronounced if the nodes taken as references are uniformly distributed with sufficiently large distances between them. On the contrary, if the reference nodes are distributed only along a straight line, the obtained accuracy may not be as expected.

4.1. Evaluating changes introduced in AWGN parameters

In this evaluation, the iterative algorithm is evaluated in terms of the appropriate number of iterations. If the number of iterations is small, the compensation is carried out while the preliminary estimated position is under the influence of NLOS delay, and this is used as a reference for further compensations. For that reason, the highly reliable LOS nodes are also

Field30x30 [m]
Tag position distributionAt random within the field
Number of trials10000
Node position error0 [m]
AWGN parameter0.3 [m]
Number of nodes9
Number of iterations5
NLOS rate0.5

Table 1.

Simulation parameters

The nodes are arranged in the system of coordinates illustrated in Figure 7.

Figure 6.

Node distribution

affected, resulting in an error in the estimation of the final positioning. On the other hand, if the number of iterations is large, the influence on LOS nodes is reduced however the computational cost may increase. Fig.6 illustrates the effect of the number of iteration on the actual estimation.

As shown in Fig.6, the results indicate that for the Iteration and Iterative SVC algorithms the accuracy improves as the number of iterations increases. A possible reason for this increase is that by increasing the number of estimation correction steps, the amount of compensation required per step decreases, alleviating the effect on NLOS nodes. However, it is worth noting that the accuracy does not increase significantly when the number of iterations exceeds 5~7 especially in Iterative SVC algorithm.

The reason is that NLOS errors can be compensated enough in a few steps by the synergy effect with Iterative algorithm and SVC algorithm.

4.2. Evaluating changes introduced in AWGN parameters

Fig.9 shows the results of changes introduced in the AWGN parameters of each node. The first conclusion that the characteristics of Iteration, SVC, and Iterative SVC algorithms improve than NEWTON algorithm. As a general rule, the Iterative SVC case exhibits the best characteristics in small AWGN error, however as the AWGN error increases, the difference between the characteristics of different methods tends to decrease. When the AWGN error is large, the Iteration algorithm outperforms the Iterative SVC algorithm. A possible explanation for this is that the large AWGN error causes a general drop in the reliability, which in turn deteriorates the reliability of the shift vector itself.

Figure 7.

RMSE evaluation changing AWGN parameter

4.3. Evaluation of changes in NLOS rate

Fig.10 shows the results of the changes introduced in NLOS Rate for each node.

NLOS Rate corresponds to the ratio of NLOS(CM2) terminals in the entire set of nodes. The others are LOS(CM1), and the delay PDFs are individually affected. Fig.8 shows that the characteristics of the Iteration and SVC are similar, however they are outperformed by the Iterative SVC algorithm. In addition, when the NLOS rate is zero, i.e., when only AWGN is present at each node, this result changes slightly. This happens because the algorithm performs some correction for any NLOS delay that may exist, however its performance decreases in other environments. In concrete terms, in the Iteration algorithm, a part of AWGN is interpreted as NLOS even though there is no NLOS delay. In the Iterative SVC algorithm, even when no geometrical shifts exist, compensation is performed in another direction. However, these problems do not cause a significant deterioration.

Figure 8.

RMSE evaluation changing NLOS rate

5. Tracking experiment by transmission tag and reception node

In this section, we perform the tracking experiment by using prototype device in NLOS environment. These devices are made in Fujitsu Co., Ltd. and Fujitsu Component Co,. Ltd. This appearance of tag is shown in Fig.11 and the appearance of node is shown in Fig.10.

Figure 9.

Tag appearance

Figure 10.

Node appearance

Reception nodes are distributed fixedly and the position of each node is

listed in table \ref{tb:experiment}.

Figure 11.

Tracking situation

Node 10 [m]0 [m]
Node 24.228 [m]0 [m]
Node 38.456 [m]0 [m]
Node 412.684 [m]0 [m]
Node 512.684 [m]5.436 [m]
Node 68.456 [m]5.436 [m]
Node 74.228 [m]5.436 [m]
Node 80 [m]5.436 [m]

Table 2.

Each node position for tracking expriment

Height of each node is 2 [m].

And, tag's position is estimated in the case of low-grade NLOS which tag is held up over human head, and in the case of serious NLOS which tag is held on breast side of human body. Tag is moved along the sides of the drawn rectangle. If signal from tag to node is vanished, available node is reduced, and if the number of available node is less or equal three, system outputs impossibility to estimate position. If estimated position is greatly exceeds the range covered by all nodes, previous once estimated result is output. Under this condition, NEWTON method which is conventional method and Iterative SVC algorithm which is proposed method is shown in Fig.11 and 12.

Figure 12.

Tracking result in low-grade NLOS environment

Fig.12 is low-grade NLOS situation, and Fig.13 is serious NLOS situation. These results show that positioning error occurs at several position in conventional method, however proposed method can decrease the error, and can improve the accuracy of positioning and tracking.

Figure 13.

Tracking result in serious NLOS environment


6. Conclusions

In the present paper, we proposed novel TDOA algorithm for reducing the error in the positioning estimation by using a positioning system in an UWB environment. In this process, a provisional position is first estimated using the NEWTON method. We then considered an NLOS delay compensation and a compensating function to alleviate the effect on LOS propagation. Then, we developed an adaptive system in which the function is adaptively renewed according to the number of iterations. This way, the vector expressing the relative positions of nodes and tags as well as the vector that corrects the vector resulting from NLOS delay were corrected. By repeating the above process for a certain number of times, an algorithm to gradually improve the positioning accuracy was developed. As previously shown in the explanation of the system model, the basic application scope of the present algorithm is an indoor environment using UWB with small signal loss. For each node, we assume the existence of the influence of a delay distribution on the basis of AWGN components and IEEE.802.15.4a, however the present algorithm may be extended to other types of delay distribution environments as well. Finally, we perform the experiment of tag tracking using TDOA system. This result shows that proposed method can mitigate abnormal tracking and improve accuracy.

The topics to be dealt with in the future are tag displacement, and extension to three dimensions. Extending to three dimensions would require the calculation of the height coordinate, which would influence the amount of computation and accuracy. It seems possible to use the existing positioning algorithm for three-dimensional analyses.


Part of the present research received support from the Global COE Program "Creating innovation by the integration of Medicine and Engineering using information and communication" of Yokohama National University. We express our deepest gratitude to all the people.

© 2011 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike-3.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited and derivative works building on this content are distributed under the same license.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Koji Enda and Ryuji Kohno (July 20th 2011). Iterative Delay Compensation Algorithm to Mitigate NLOS Influence for Positioning, Current Trends and Challenges in RFID, Cornel Turcu, IntechOpen, DOI: 10.5772/17768. Available from:

chapter statistics

1641total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Efficient Range Query Using Multiple Hilbert Curves

By Jing Dai

Related Book

First chapter

Design of Low-Cost Probe-Fed Microstrip Antennas

By D. C. Nascimento and J. C. da S. Lacava

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us