An Improved RFID-Based Localization Algorithm for Wireless Sensor Networks

Abstract

The position of RFID-tagged objects in sensor networks is becoming an important feature for ubiquitous computing applications. In this work, we develop an improved positioning algorithm for RFID-tagged objects. Compared with the VIRE algorithm, we apply a nonlinear interpolation method to further improve the positioning precision. We also introduce the concept of credibility of reference tags to reduce the influence of abnormal tags on positioning precision. Finally, we provide detailed simulations to evaluate the proposed technique.

1. Introduction

Location sensing is a crucial prerequisite for many wireless sensor networks (WSNs) applications [1] such as asset tracking, industrial automation, and homecare and healthcare systems. GPS is the most widely used technology for localization. However, once arriving at the earth surface, GPS signals are too weak to penetrate the building. To overcome those limitations, various localization technologies have been proposed for WSNs among which are indoor GPS, motion and rotation sensors, infrared, ultrasound, ultra-wideband (UWB), wireless local area network (WLAN), and radio frequency identification (RFID). Due to its lower cost and its technical capabilities, RFID has been widely adopted as an attractive technology for many WSNs' applications, which uses wireless communication for automatic identification of objects.

In the indoor environment, layout structure and moving objects can cause reflection, refraction, diffraction, dead spots, and absorption of radio signals. Therefore, the multipath phenomenon will occur and affect the accuracy of indoor location. Moreover, many other factors also influence the RSSI, such as temperature, orientation of antenna, and height to the ground. LANDMARC [2] was the first attempt using active RFID for indoor location sensing, while VIRE [3] improved it by introducing the concepts of virtual reference tags and proximity map. In this work, we develop an improved positioning algorithm for RFID-tagged objects, which not only achieves robustness to abnormal tags but also dramatically improves the positioning precision.

The rest of the paper is organized as follows. The next section presents a brief review on the related work. Our new approach, NICoT (RFID localization algorithm based on nonlinear interpolation and credibility of tags), is detailed in Section 3. We respectively evaluate the performance of our scheme by simulations in Section 4. Finally, we conclude this paper in Section 5.

2. Related Work

RFID-based ILS solutions can be categorized into the following three areas based on their localization methods: triangulation-based solutions, proximity, map-based solutions, and scene analysis solutions.

• (1)

Triangulation [4, 5]: the distance between the reader and tag is calculated by using the collected signal strength, and the distances are used for triangulation to obtain the position of the tracking tag. The triangulation method depends largely on an accurate signal propagation model, which greatly decreases its effectiveness.

(2)

Scene analysis [6–10]: the scene analysis method captures the signal strength in the sensing area and compares it with a preexisting signal strength database to map the target to its location. The scene analysis method needs to build a radio map by calibrating signal strength values at training locations, which is used repeatedly afterwards. However, the signal strength values change with the change of the environment. The fingerprint has to be updated periodically, which requires considerable time and labor.

(3)

Proximity [6, 11, 12]: the proximity method needs to measure the nearness of a set of neighboring reference tags. Those tags are close to the target, and their locations are fixed and known. The measured nearness, along with the corresponding known locations, is used to estimate the location of a target. The proximity map is a promising method for complex and dynamic built environments. This method can accommodate the impacts of the complexity and dynamic nature of built environments. It does not use the RSSI value to estimate the travel distance of the signal. Instead, it uses RSSI value to compare the nearness of reference tags to the target, which is qualitative and less sensitive to the obstructions that impact the propagation of the signal.

In LANDMARC, the concept of reference tags is introduced, which can provide reference locations. The known locations of the nearest neighboring reference tags and nearness to the tracking tag are used in computing the tracking tag's location. The algorithm has the following advantages. First, the algorithm uses tags instead of more readers, which greatly reduces the cost of system. Second, the reference tags and target tags are in the same environment, and the effect of environmental factors can be effectively off-settled. However, the algorithm has the following drawbacks. First, it does not work well in a closed area with severe radio signal multipath effects. Second, to further improve the localization accuracy, more reference tags are needed, which is costly and may cause RF interference phenomenon. In VIRE, the virtual reference tags were used to achieve a higher accuracy. These tags are virtually distributed linearly between real reference tags, which increase the density of the reference tag grids. Locations of the virtual reference tags are known and recorded, and their signal strength is estimated by linear interpolation of that of the real tags next to them. The sensing area is divided into small regions, and each reader maintains its own proximity map. As a result, the most probable location can be estimated.

3. The NICoT Approach

3.1. Credibility of Real Reference Tags

Due to hardware faults or external interference, the signal strength of tags may be erroneously read by RF reader. In the practical measurement, we observe that some tags' signal strengths read by readers are too large or too small, or zero (fail to read). Therefore, the signal strength of the reference tags is not trustworthy and needs to be verified before they are chosen for the tracking tag's location calibration.

With the placement of the reference tags and the readers shown in Figure 1, we can observe that a reference tag's signal strength is always similar to its neighbor's for the same reader. Therefore, with known signal strength of all reference tags, we can check whether the measurement is proper or not. Suppose we have n RF readers $(R_1,R_2,\dots ,R_n)$ along with m tags $(T_1,T_2,\dots ,T_m)$ as reference tags. We define the signal strength of all reference tags perceived on all readers as an $n\times m$ matrix SSM, where SSM $(i,j)$ denotes $T_i$ 's signal strength perceived on $R_j$ . We also define the difference of signal strength between $T_i$ and its neighborhood as an $n\times m$ matrix DSSM, where DSSM $(i,j)$ denotes whether the $T_i$ 's signal strength is similar to its neighborhood's average signal strength or not. For the same reader $R_j$ , if the difference between $T_i$ 's signal strength and its neighborhood's average signal strength is less than the threshold τ, then the element at row i and column j will be 1. Otherwise, it will be 0; namely,

$$\begin{array}{ll}& \text{DSSM}\left(i,j\right)\\ \hspace{1em}=\{\begin{array}{ll}1,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\left|\text{SSM}\left(i,j\right)-\text{averag}{\text{e}}_{T_x\in N}\left(\text{SSM}\left(x,j\right)\right)\right|\le \tau \hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(1)

Figure 1

Placement of RF readers and tags.

Here, N is the set of $T_i$ 's neighbors. Empirically, the threshold τ can be calculated as follows:

$$\begin{array}{cc}& \tau ={\max }_{T_x\in N}\left(\text{SSM}\left(x,j\right)\right)-\frac{\text{mi}{\text{n}}_{T_x\in N}\left(\text{SSM}\left(x,j\right)\right)}{2}.\end{array}$$

(2)

As an example in Figure 1, the set of $T_{13}$ 's neighbors is $\{T_7$ , $T_8$ , $T_9$ , $T_{12}$ , $T_{14}$ , $T_{17}$ , $T_{18}$ , $T_{19}\}$ . Therefore, the credibility $c(T_i)$ of the tag $T_i$ can be computed as follows:

$$\begin{array}{cc}& c\left(i\right)=\frac{{\sum }_{j=1}^n\text{DSSM}\left(i,j\right)}{n},\end{array}$$

(3)

where $0\le c(i)\le 1$ , and n is the number of all RF readers.

3.2. Nonlinear Interpolations

The concept of virtual reference tags can increase the precision of position estimation without additional cost. However, the VIRE algorithm calculates the virtual tags' signal strength by a simple linear method, which does deteriorate the performance of interpolation. To further improve the positioning precision, we apply a simple nonlinear interpolation in the solution model.

As shown in Figure 2, the real reference tags in our approach are also properly placed to form a 2D regular grid. Each physical grid cell covered by 4 real tags is further divided into $n\times n$ equal virtual grid cells. Therefore, each virtual grid cell can be considered as covered by four virtual reference tags. Since the coordinates of the four real reference tags are known, the coordinates of the virtual reference tags can be easily calculated.

Figure 2

Nonlinear interpolation.

The RSSI values of those virtual tags are a function related to the signal strength of 4 real reference tags in corner and can be obtained by the empirical formulas shown below:

$$\begin{array}{l}{S}_k\left(T_{i,j}\right)=(S_k\left(T_{\mathrm{0,0}}\right)\times D_a^2+S_k\left(T_{\mathrm{0,1}}\right)\times D_b^2\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+S_k\left(T_{n,0}\right)\times D_c^2+S_k\left(T_{n,n}\right)\times D_d^2)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {\left(D_a^2+D_b^2+D_c^2+D_d^2\right)}^{-1}.\end{array}$$

(4)

Here, $S_k(T_{i,j})$ represents the RSSI value of the reference tag located at the coordinate $(i,j)$ for the kth reader. $D_a$ , $D_b$ , $D_c$ , and $D_d$ denote, respectively, the distance between the virtual reference tag $T_{ij}$ and the four real reference tags $T_{0,0}$ , $T_{0,n}$ , $T_{n,0}$ , and $T_{n,n}$ .

3.3. Weight of Reference Tags

The proximity map is also used to eliminate those unlikely positions in the NICoT. When the interpolation and elimination processes are finished, we can obtain a set of possible positions. To improve the accuracy and robustness of NICoT, one weighting factor $w_i^{\prime }$ is introduced. The weighting factor $w_i^{\prime }$ not only demonstrates the discrepancy of RSSI values between the selected virtual reference tags and the tracking tag but also indicates the credibility of the reference tags. We observe that the reference information of a closer tag is more accurate and trustable, which gives a larger RSSI value. The $w_i^{\prime }$ is a function of the RSSI values of selected virtual tags, as given by

$$\begin{array}{cc}& w_i^{\prime }=\frac{1/E_i^2}{{\sum }_{j=1}^k\left(1/E_j^2\right)}.\end{array}$$

(5)

Here, $E_i$ is the Euclidean distance in signal strength between a tracking tag and a virtual reference tag $T_i$ . We define the signal strength vector of a tracking tag as $S=(S_1,S_2,\dots ,S_n)$ , where $S_i$ denotes the signal strength of the tracking tag perceived on reader $R_i$ . For the reference tags, we denote the corresponding signal strength vector as $\theta =({\theta }_1,{\theta }_2,\dots ,{\theta }_n)$ , where ${\theta }_i$ denotes the signal strength. Then, $E_i$ is given by

$$\begin{array}{cc}& E_i=\sqrt{{\sum }_{p=1}^n\frac{{\left({\theta }_p-S_p\right)}^2}{{\theta }_p}.}\end{array}$$

(6)

When we compute the coordinate of a tracking tag, the weighting factors should be considered. We suggest an assorted weight $w_i$ as $w_i=w_i^{\prime }\times C(T_i)$ . The calculated coordinate is given by

$$\begin{array}{cc}& (x,y)={\sum }_{i=1}^k{w}_i\times \left(x_i,y_i\right).\end{array}$$

(7)

Here, k is the number of total regions in the set of possible positions and $(x_i,y_i)$ denotes the coordinates of the virtual reference tag $T_i$ .

4. System Implementation and Simulation Evaluation

4.1. System Implementation

We use the simulation programs run in MATLAB to evaluate the performance of NICoT in an idealized network environment. The experiment environment is illustrated in Figure 3. In our environment, 16 real reference tags were set in $4\hspace{0.17em}\text{m}*4\hspace{0.17em}\text{m}$ area; the distance between them was 1 m; 4 readers were set in each corner; and 9 tracking tags were set too. Virtual reference tags were inserted as in Figure 2. We define the location estimation error e to be the linear distance between the tracking tag's real coordinates $(x,y)$ and the computed coordinates $(x^{\prime },y^{\prime })$ , given by $e=\sqrt{(x-x^{\prime }{)}^2+(y-y^{\prime }{)}^2}$ .

Figure 3

Experiment environment.

4.2. Effect of the Density of Virtual Reference Tags

Figure 4 shows the effect of the number of virtual reference tags on the estimation error when $\tau =2$ . We can see that the higher the density of virtual reference tags, the greater the location sensing precision. However, the positioning accuracy will not improve as the number of virtual reference tags is beyond a certain number. We note that the accuracy does not improve significantly when the number of reference tags increases from 30 × 30 to 40 × 40. In our experiments, each physical grid cell covered by 4 real tags is further divided into 30 × 30 equal virtual grid cells.

Figure 4

Estimation error of the 9 tracking tags.

4.3. Performance Comparison Using Different Parameters

Figure 5 shows that different threshold τ has different estimation error. We can see that the cumulation of estimation error under different choices of τ increases with the increase of error. We also note the estimation error is minimum, when $\tau =2$ is chosen.

Figure 5

Estimation error of the 9 tracking tags.

4.4. Performance Comparison Using Different Localization Algorithms

Figure 6 shows the comparison between the NICoT approach and the VIRE approach for 9 different locations of the tracking tags. The reduction in estimation error for NICoT is from 43.6% to 62.8% over VIRE for all 9 locations. For those tags, the worst estimation error is 0.228 m and the average estimation error is 0.14 m. Clearly, the NICoT approach provides a higher degree of accuracy than that of VIRE at all locations.

Figure 6

Cumulative percentile of error distance.

5. Conclusion and Future Work

This paper presented an improved algorithm based on nonlinear interpolation of the virtual reference tags' signal strength and the concept of the reference tags' credibility. Compared with the VIRE algorithm, we apply a nonlinear interpolation method to further improve the positioning precision. We also introduce the concept of credibility of reference tags to reduce the influence of abnormal tags on positioning precision. It can be used for real-time indoor locating. Obviously, the proposed algorithm can be easily extended to the three-dimensional space. In future research, we may combine our algorithm with other location algorithms to further improve the positioning accuracy.