Keywords

1 Introduction

Global Positioning System (GPS) can achieve the most basic target localization in the outdoors environment, but in the indoor environment, GPS will be unavailable. With the development of personal mobile devices, domestic and foreign scholars have launched research on indoor localization technology. At present, the most commonly used indoor localization technologies include infrared localization technology, WiFi localization technology, ultrasonic localization technology and RFID localization technology. Infrared localization technology uses infrared sensors for distance measurement and angle measurement to achieve target localization. Literature [1] proposes the Active Badge system which can achieve simultaneous localization of multiple targets. However, infrared rays cannot penetrate obstacles and have a short propagation distance, so this method can only achieve target localization within the line of sight (LoS). Ultrasonic localization technology does not require strict synchronization between systems and can achieve high localization accuracy. Literature [2] proposes the first ultrasonic localization system Active Bat which deploys a large number of transponders, with a 95% probability of achieving localization accuracy within 9 cm. However, ultrasonic localization system requires large-scale layout with many of hardware devices, and the localization result is very sensitive with the environment. Due to the low cost and the ease installation of access points, indoor localization based WiFi [3] signal strengths are becoming increasingly popular. However, due to the abundant multipath in the indoor environment, WiFi has a low localization precision. In RFID localization system, the tag is attached to the object and the radio frequency signal from the reader is modulated by the tag and returned to the reader, then the information of the returned signal is processed to realize the target localization. In recent years, RFID technology has been used in warehouse management, service industries, smart home, logistics and transportation, automated office and other aspects. RFID [4] plays an irreplaceable role in indoor localization due to its low cost, strong anti-interference ability, battery-free, fast identification, etc.

In this context, it is particularly important to improve the distance estimation accuracy of RFID ranging [5] technology. The RFID ranging methods based on the radio frequency (RF) signals can be divided into two categories: received signal strength (RSS) and phase. Based on the RSS-distance estimation model, RSS [6] suffers from poor accuracy and reliability due to multi-path interference. And the method still needs a mass of reference tags or off-line RSSI fingerprint databases. The phase-based method has high sensitivity to distance, but the method based on the time difference of arrival (TDOA) [7, 8] is limited due to the narrow available bandwidth. Another typical method based on phase is based on the angle of arrival (AOA) [9]. Due to the phase ambiguity, the AOA-based method requires that the distance between adjacent antennas is less than half of the wavelength, which is impractical for the directional antennas used in RFID systems.

In order to improve localization accuracy in complex environments, the localization technology based on time sum of arrival (TSOA) has been widely used. TSOA [10] is usually done by measuring the sum of arrival times of signals at the same time by multiple stations. TSOA appears as an ellipse in space, and the target position is obtained by the intersection of several ellipses. Due to the pseudo-linearity of the measurement equation, many scholars have carried out related research. The most classic methods are the classic Newton iteration algorithm (Newton) and the least square (LS) method. The least squares algorithm is applied to multi-station passive localization. The algorithm first converts the nonlinear observation equation into a pseudo-linear observation equation, then constructs an augmented matrix, and performs singular value decomposition of the matrix to estimate the target position, so there is no need to iteratively calculate or obtain a coarse estimate of the target position. However, the LS is susceptible to measurement errors, resulting in a poor localization accuracy. Newton converges fast, and an accurate solution can be obtained quickly in the iterative process, but the convergence problem of Newton is often relying on the selection of initial values. Literature [11] proposed a joint localization algorithm using LS and Newton, but the LS is greatly affected by the ranging error. When the ranging error is large, this algorithm is not applicable.

Based on the above issues, the main contributions of this paper are as follows:

  • We design a RFID localization system which uses frequency hopping technology to expand the bandwidth and improve the resolution. Then we use the phase information to achieve the high accuracy ranging.

  • We propose a hybrid localization algorithm to solve the local convergence problem caused by the Newton iteration method based on Least squares (LS-Newton). We utilize the semidefinite programming (SDP) algorithm to provide initial values, and then use LS-Newton to complete target localization. The proposed method can effectively solve the initial valve problem and ensure the convergence of the LS-Newton algorithm, as well as improve the convergence speed of iterative algorithm. The experimental result shows that the hybrid localization algorithm has higher localization precision, better algorithm stability and faster convergence speed.

The rest of this paper is organized as follows. Section 2 mainly shows the experimental platform, distance estimation model and target localization model. Section 3 is the experimental analysis and performance comparison of the proposed algorithm. Finally, Sect. 4 provides the conclusion.

2 System Design

Figure 1 shows the system localization architecture, which mainly contains two modules: the distance estimation system and the target localization system. The testing platform is primarily composed of readers, passive tags, and RFID antennas. The two readers are Impinj R420 reader for activating the tag and USRP N210 as transmitter and receiver. As shown in Fig. 1, the Impinj R420 reader transmits a high-power signal to activate the tag. One USRP N210 transmitter sends low power signals, and three USRP N210 receivers receive signals reflected by tags. The RFID antennas we use are directional antennas. Literature [12] shows that directional antennas used at the receiver may help reduce the multipath in the channel as opposed to using omnidirectional antennas. Passive tags have a specific identification number. After the tag is activated, the stored ID information is sent to the receivers through backscatter modulation.

After the receiver receives the signal, the CFR is obtained through channel estimation. The phase information can be extract from CFR to complete distance estimation [13] and target localization.

Fig. 1.
figure 1

System localization frame

Full size image

2.1 Carrier-Phase Based Distance Estimation

The system emulates a large virtual bandwidth on RFIDs through frequency hopping technology [14, 15] and transmits signals at 20 frequency points, such as 730 MHz–920 MHz with 10 MHz interval.

The phase information can be extract from CFR [16] according to the Eq. (1):

$$ \phi = angle(h) $$
(1)

where \(h\) is the CFR. Due to the frequency points may be lost during the process of collecting data, we use linear interpolation method to compensate the phase information and finally obtain the phase information (\(\varphi = [\varphi_{1} ,\varphi_{2} ,...,\varphi_{20} ]\)) of the full frequency in 730 MHz–920 MHz. The clock of transmitter and receiver is synchronous, the inherent error generated by the equipment can be eliminated by making a phase difference with the reference point. Assuming the phase of the reference point is \(\varphi^{\prime} = \left[ {\varphi_{1}^{\rm{\prime }} ,\varphi_{2}^{\rm{\prime }} ,...,\varphi_{20}^{\rm{\prime }} } \right]\), then the phase difference between the target point and the reference point can be expressed as:

$$ \theta = \varphi - \varphi^{\prime} = \left[ {\varphi_{1} - \varphi_{1}^{\rm{\prime }} ,\varphi_{2} - \varphi_{2}^{\rm{\prime }} ,...,\varphi_{20} - \varphi_{20}^{\rm{\prime }} } \right] $$
(2)

The channel state information (CSI) can be reconstructed by leveraging the phase difference of Eq. (2):

$$ CSI = e^{ - j\theta } = \left[ {e^{{ - j\left( {\varphi_{1} - \varphi_{1}^{\rm{\prime }} } \right)}} ,\,e^{{ - j\left( {\varphi_{2} - \varphi_{2}^{\rm{\prime }} } \right)}} ,...,e^{{ - j\left( {\varphi_{20} - \varphi_{20}^{\rm{\prime }} } \right)}} } \right] $$
(3)

Literature [17] shows that the frequency domain zero padding is performed by adding zeros to a border of data record prior to the inverse fast Fourier transform (IFFT). The IFFT result of the zero-padded signal is viewed as the time sampled version of discrete Fourier transform (DFT) with a finer sampling interval. To obtain more accurate time domain information, the CSI after frequency domain zero-padding is:

$$ CSI^{^{\prime}} = \left[ {e^{{ - j\left( {\varphi_{1} - \varphi_{1}^{\rm{\prime }} } \right)}} ,e^{{ - j\left( {\varphi_{2} - \varphi_{2}^{\rm{\prime }} } \right)}} ,...,e^{{ - j\left( {\varphi_{20} - \varphi_{20}^{\rm{\prime }} } \right)}} ,0,0,...,0} \right] $$
(4)

The time-domain information after IFFT is:

$$ f(t) = IFFT(CSI^{\prime}) $$
(5)

where \(t\) is the time-of-flight (ToF) of the path. To do this, the coarse distance estimate can be solved by leveraging that: among all the paths of the wireless signal, the direct path is the shortest. Therefore, the ToF of the direct path is the time corresponding to the first peak in the time domain spectrum of Eq. (5). Due to the multipath interference, the coarse distance estimate has the low precision, so we use the multipath suppression method in [18] for multipath suppression, and finally utilize the phase after multipath suppression combined with the Chinese remainder theorem (CRT) [19, 20] to achieve the distance estimation.

2.2 Target Localization Model

Figure 2 is a propagation process of useful signals. Supposing the tag coordinate is \((x,y)\), the transmitter coordinate is \((x_{0} ,y_{0} )\), the receiver coordinate is \((x_{i} ,y_{i} )\,(i = 1,2,3)\). The total distance of the target tag is \(d_{i} = r_{0} + r_{i} (i = 1,2,3)\), where \(r_{0}\) is the distance from the tag to the transmitter, and \(r_{i} (i = 1,2,3)\) is the distance from the tag to the receiver. \(\hat{d}_{i} = d_{i} + v_{i} (i = 1,2,3)\) is the measurement total distance containing the distance estimation errors, where \(v_{i} (i = 1,2,3)\) is the distance estimation error of each receiver.

Fig. 2.
figure 2

Propagation process of useful signals

Full size image

According to the ellipse localization algorithm, the distance error equation is:

$$ \left\{ {\begin{array}{*{20}c} {\sqrt {(x - x_{0} )^{2} + (y - y_{0} )^{2} + h^{2} } + \sqrt {(x - x_{1} )^{2} + (y - y_{1} )^{2} } = \hat{d}_{1} + v_{1} } \\ {\sqrt {(x - x_{0} )^{2} + (y - y_{0} )^{2} + h^{2} } + \sqrt {(x - x_{2} )^{2} + (y - y_{2} )^{2} } = \hat{d}_{2} + v_{2} } \\ {\sqrt {(x - x_{0} )^{2} + (y - y_{0} )^{2} + h^{2} } + \sqrt {(x - x_{3} )^{2} + (y - y_{3} )^{2} } = \hat{d}_{3} + v_{3} } \\ \end{array} } \right. $$
(6)

where \(h\) is the height difference between the transmitter and receiver, and the height of the receiver is the same as the tag.

Obtaining Initial Value of Iteration.

LS-Newton method has the fast convergence speed and the algorithm can save much time under the condition of certain localization accuracy. But how to make the LS-Newton method converge is still a problem, which is often associated with the selection of initial values. Solving the initial value problems is the premise of high accuracy of LS-Newton method. We will introduce the SDP estimate value as the initial value of LS-Newton method for iteration calculation, which can realize the optimization of the algorithm.

First, we obtain the initial value of iteration through the SDP algorithm. Without considering the distance estimation error, Eq. (6) can be expressed as:

$$ \hat{d}_{i} = d_{i} = \sqrt {(x - x_{{0}} )^{2} + (y - y_{{0}} )^{2} + h^{2} } + \sqrt {(x - x_{i} )^{2} + (y - y_{i} )^{2} } $$
(7)

The matrix form can be obtained by simplifying the Eq. (7) combined with the equations \(x - x_{i} = (x - x_{1} ) - (x_{i} - x_{1} ),y - y_{i} = (y - y_{1} ) - (y_{i} - y_{1} )\):

$$ Az = l $$
(8)

where

$$ A = \left[ {\begin{array}{*{20}c} {x_{1} - x_{0} } & {y_{1} - y_{0} } & { - \hat{d}_{1} } \\ {x_{2} - x_{0} } & {y_{2} - y_{0} } & { - \hat{d}_{2} } \\ {x_{3} - x_{0} } & {y_{3} - y_{0} } & { - \hat{d}_{3} } \\ \end{array} } \right] $$
(9)
$$ l = \frac{1}{2}\left[ {\begin{array}{*{20}c} {(x_{1} - x_{0} )^{2} + (y_{1} - y_{0} )^{2} - \hat{d}_{1}^{2} - h^{2} } \\ {(x_{2} - x_{0} )^{2} + (y_{2} - y_{0} )^{2} - \hat{d}_{2}^{2} - h^{2} } \\ {(x_{3} - x_{0} )^{2} + (y_{3} - y_{0} )^{2} - \hat{d}_{3}^{2} - h^{2} } \\ \end{array} } \right] $$
(10)
$$ z = \left[ {\begin{array}{*{20}c} {x - x_{0} } \\ {y - y_{0} } \\ {r_{0} } \\ \end{array} } \right] $$
(11)

Considering the measurement error, Eq. (8) can be expressed as:

$$ Az = l - V $$
(12)

where \(V = [v_{1} ,v_{2} ,v_{3} ]^{T}\) is measurement error.

The least-square solution of Eq. (12) can be expressed as:

$$ z = \arg \min (Az - l)^{T} (Az - l) $$
(13)
$$ \, \begin{array}{*{20}c} {Subject} & {to} \\ \end{array} (x - x_{0} )^{2} + (y - y_{0} )^{2} + h^{2} = r_{0}^{2} $$
(14)

Therefore, the localization process can be modeled into the quadratic constrained quadratic programming problems. In order to linearize the constraint function and objective function, we introduce the redundant variables \(Z = zz^{T}\). However, the rank of the redundant variable is 1, it is not a convex optimization problem. Thus, the LS problem can be transformed into the following convex optimization problem by slacking the rank constraints:

$$ \begin{array}{*{20}l} {\mathop {\min }\limits_{Z,z} tr\left\{ {\left[ {\begin{array}{*{20}c} Z & z \\ {z^{T} } & 1 \\ \end{array} } \right]\left[ {\begin{array}{*{20}c} {A^{T} A} & { - A^{T} l} \\ { - l^{T} A} & {l^{T} l} \\ \end{array} } \right]} \right\}} \hfill \\ {\begin{array}{*{20}c} {subject} & {to\left\{ {\left[ {\begin{array}{*{20}c} Z & {zl} \\ {z^{T} l} & {l^{2} } \\ \end{array} } \right]\Sigma } \right\}} \\ \end{array} = 0} \hfill \\ {\left[ {\begin{array}{*{20}c} Z & {zl} \\ {z^{T} l} & {l^{2} } \\ \end{array} } \right] \ge 0} \hfill \\ {\left[ {\begin{array}{*{20}c} Z & z \\ {z^{T} } & 1 \\ \end{array} } \right] \ge {0}} \hfill \\ \end{array} $$
(15)

where \(\Sigma = diag(1,1, - 1,1)\).

The initial localization result can be obtained by Eq. (15). Due to the initial localization result is close to the true values but has low accuracy, we can use it as the initial value of the LS-Newton algorithm for obtaining the optimal solution.

Target Localization.

According to Eq. (15), the initial value of iteration can be obtained, assuming that the initial value is \((x^{\prime},y^{\prime})\). We leverage Tylor expansion and omit the quadratic term and above to linearize Eq. (6). The linearized equation is expressed in matrix form as:

$$ A^{\prime}z^{\prime} - l^{\prime} = V^{\prime} $$
(16)

The matrix shown in Eq. (16) is expanded into the following form:

$$ \left[ {\begin{array}{*{20}c} {A_{x1}^{\rm{\prime }} ,} \\ {A_{x2}^{\rm{\prime }} ,} \\ {A_{x3}^{\rm{\prime }} ,} \\ \end{array} } \right.\left. {\begin{array}{*{20}c} {A_{y1}^{\rm{\prime }} } \\ {A_{y2}^{\rm{\prime }} } \\ {A_{y3}^{\rm{\prime }} } \\ \end{array} } \right] \times \left[ {\begin{array}{*{20}c} {z_{x} } \\ {z_{y} } \\ \end{array} } \right] - \left[ {\begin{array}{*{20}c} {l_{1} } \\ {l_{2} } \\ {l_{3} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {v_{1} } \\ {v_{2} } \\ {v_{3} } \\ \end{array} } \right] $$
(17)

where,

$$ \begin{array}{*{20}l} {A_{xi}^{\rm{\prime }} = \frac{{x^{\prime} - x_{0} }}{{\sqrt {(x^{\prime} - x_{0} )^{2} + (y^{\prime} - y_{0} )^{2} + h^{2} } }} + \frac{{x^{\prime} - x_{i} }}{{\sqrt {(x^{\prime} - x_{i} )^{2} + (y^{\prime} - y_{i} )^{2} } }}} \hfill \\ {A_{yi}^{\rm{\prime }} = \frac{{y^{\prime} - y_{0} }}{{\sqrt {(x^{\prime} - x_{0} )^{2} + (y^{\prime} - y_{0} )^{2} + h^{2} } }} + \frac{{y^{\prime} - y_{i} }}{{\sqrt {(x^{\prime} - x_{i} )^{2} + (y^{\prime} - y_{i} )^{2} } }}} \hfill \\ {l_{i} = \hat{d}_{i} - \left( {\sqrt {(x^{\prime} - x_{0} )^{2} + (y^{\prime} - y_{0} )^{2} + h^{2} } + \sqrt {(x^{\prime} - x_{i} )^{2} + (y^{\prime} - y_{i} )^{2} } } \right)} \hfill \\ {z_{x} = x - x^{\prime}} \hfill \\ {z_{y} = y - y^{\prime}} \hfill \\ \end{array} $$
(18)

According to Eq. (16), we can obtain the least square estimation by Eq. (19):

$$ z^{\prime} = \mathop {\arg \min }\limits_{z} (V^{T} V) $$
(19)

By giving an upper threshold \(\varepsilon\), the final localization result \([x,y] = [x^{\prime} + z_{x} ,y^{\prime} + z_{y} ]\) can be obtained by solving Eq. (19) when the condition \(\left| {z_{x} } \right| + \left| {z_{y} } \right| < \varepsilon\) is satisfied.

The system localization process is shown in Fig. 3.

Fig. 3.
figure 3

Flowchart of the localization system

Full size image

3 Evaluation Measurement Results

We design RFID system on four USRP N210 software radios which are all synchronized, three of them are used as receiver and the rest one is used as transmitter. Due to the low power of the transmitter which cannot activate the tag to communicate with the readers, another commercial reader Impinj R420 is adopted. We conduct experiment in a small and empty room with a size of 5 × 5 m2. Figure 4 shows the layouts of the testbed. Figure 5 shows the test prototype in an empty room.

Fig. 4.
figure 4

Layout of the testbed

Full size image
Fig. 5.
figure 5

Prototype of the test

Full size image

As shown in Fig. 4, three receivers are placed in a row, and we mainly complete distance estimation and localization for 21 target points. The coordinates of the three receivers are (35 cm, 0 cm), (35 cm, 75 cm), (35 cm, 150 cm), the coordinate of the transmitter is (66 cm, 75 cm), the coordinates of the reference points are (0 cm, 150 cm), (75 cm, 150 cm), (150 cm, 150 cm). Among them, the reference point of known information is used to eliminate the inherent error between the devices. According to the distance estimation process, we can get the distance estimation result of each receiver for each position. Figure 6 is the CDFs of the distance estimation error.

Fig. 6.
figure 6

CDFs of the ranging error

Full size image

As shown in Fig. 6, three receivers can achieve the median ranging accuracy are 3 cm, 5 cm and 1.5 cm, respectively. Although the clocks between the receivers are synchronized, there are still errors between the devices. And in actual measurement environment as shown in Fig. 5, there is a table and other debris placed on the left of receiver 1, which causes serious multipath interference. On the right side of the receiver 3, there are no other obstacles except the wall, and the effect of multipath interference on the receiver 3 is small, so the receiver 3 has better ranging accuracy than the receiver 1. For the receiver 2, it can be found in Fig. 5 that the signals emitted by the Impinj antenna and the transmitter will affect the receiver 2, resulting in a decrease in ranging accuracy. In addition, the phase center of the directional antenna used in the system cannot be determined, which will lead to equipment measurement deviations and a decrease in ranging accuracy.

As shown in Fig. 4, the relative position between the tag and the receiver will also affect the ranging results. For example, the target position in the corner tends to have a poor ranging accuracy due to its lower signal-to-noise ratio, such as position 18 and position 21. Using the ranging result for target localization, the localization result is shown in Fig. 7.

Fig. 7.
figure 7

CDFs with different localization algorithm

Full size image

Figure 7 shows that the method we proposed achieves centimeter-level localization accuracy. It is clear that the localization precision relies on the choice of initial points. As shown in the subgraph in Fig. 7, improper selection of the initial point will result in local divergence of localization results. The localization result of the SDP algorithm is closer to the true value, but still has a poor accuracy. Therefore, we can use the initial localization result obtained by the SDP algorithm as the initial value of LS-Newton. As expected, the proposed method solves the local divergence problem of the localization results brought by the initial point and improve the localization accuracy.

4 Conclusion

The localization accuracy of LS-Newton depends on the choice of the initial value. LS-Newton requires that the initial value of the iteration must be close to the true value. To solve this problem, this paper proposes a hybrid localization algorithm based on carrier phase ranging in UHF RFID system. The algorithm uses the SDP algorithm to convert the least square problem into a quadratic constrained quadratic programming problem. The localization result of the SDP algorithm is used as the iteration's initial coordinates to complete the final target localization. Experimental results show that in this system, the average ranging error of the three receivers is less than 10 cm with a probability of 84%, and the final localization error is less than 50 cm with a probability of 95%. Compared with other algorithms, the proposed hybrid localization algorithm has better convergence performance. In addition, this paper solves the initial point selection problem of the LS-Newton method, and realizes the optimization of the algorithm.