Simulation parameters

## 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 (*x* _{i }*, y* _{i }) [*i = 1...M*], and calculates the distance difference on the basis of the time required for the signal to receive. *M* denotes 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 *T* _{start }is the transmission time, *T* _{r }is the reception time, and *c* is the speed of light. The reception time *T* _{i }from the tag to the node is as shown below:

Then, the propagation distance *D* _{i }is

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.

The number of node is *M* and these nodes have the information of position of *x* _{i }*,y* _{i }. 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) *R* _{ij }computed by each combination of nodes is given by

where *R* _{i }is distance between tag and each node, *t* _{i }is arrival time of each node. First, likelihood computation at arbitrary position P(m_{0},n_{0}) is performed.

The gradient of *R* _{ij }evaluated in a initial position is expressed as

where

And similarly for

Let G be the gradient matrix given by

Let

such that

### 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 *t* _{i }can be written as

Here, *T* _{0 }is the true arrival time, *T* _{A }is the AWGN error, and *T* _{N }is the error caused by NLOS. The multiplication of these parameters with *c* yields distances, and the distance of arrival *R* _{i }is expressed as

Here, *R* _{0 }is the arrival distance, *R* _{A }is the error in the arrival distance, and *R* _{N }is 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:

Here, *R* _{N }, 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 *R* _{N }to 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

## 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:

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.

*D*^{NLOS }_{i }of a LOS node on the opposite side of the NLOS node outputs a positive value.*D*^{NLOS }_{i }of 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 *D* _{basis }, and is changed according to the rules given below:

First, the largest of all *D* ^{NLOS }_{i }values is selected;

Similarly, smallest of all *D* ^{NLOS }_{i }values is selected;

As the maximum value approaches the reference value, only *D* ^{NLOS }_{i }of 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, *D* ^{NLOS }_{i }of 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 *D* ^{NLOS }_{max} 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.

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

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 *X* _{tem }*,Y* _{tem }. The shift vector that results from a delay originating from an arbitrary node *i* and *j* is expressed by the following equation:

This unit vector is expressed as follows:

Similarly,

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 *a* and *b*. Vector *b* is the unite vector from position B to TEP and vector *a* is the unite inverse vector from position A to TEP. Additionally, the sum vector of each unit shift vector is represented as vector *c*.

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 _{M}C_{2}=M(M-1)/2. Then, the sum of absolute value of all shift vectors is represented as

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

If D^{T} _{i} is smaller than 0, D^{T} _{i} becomes 0. Therefore, the D^{T} _{i} is the extracted value over basis value. *INV* _{L }and *INV* _{max} denotes the L-th iteration and total iteration number respectively in SVC process.

Therefore, shift vector is represented as

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, *X* _{S }and *Y* _{S }is compensated from *X* _{tem }and *Y* _{tem }respectively.

The equation (26) and (27) are repeated (*INV* _{L }=1~*INV* _{max}). 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’* _{i }of 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

Field | 30x30 [m] |

Tag position distribution | At random within the field |

Number of trials | 10000 |

Node position error | 0 [m] |

AWGN parameter | 0.3 [m] |

Number of nodes | 9 |

Number of iterations | 5 |

NLOS rate | 0.5 |

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

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.

### 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.

## 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.

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

listed in table \ref{tb:experiment}.

Node 1 | 0 [m] | 0 [m] |

Node 2 | 4.228 [m] | 0 [m] |

Node 3 | 8.456 [m] | 0 [m] |

Node 4 | 12.684 [m] | 0 [m] |

Node 5 | 12.684 [m] | 5.436 [m] |

Node 6 | 8.456 [m] | 5.436 [m] |

Node 7 | 4.228 [m] | 5.436 [m] |

Node 8 | 0 [m] | 5.436 [m] |

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.

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.

## 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.

## Acknowledgments

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.