Centimeter-Level Localization Algorithm with RFID Passive Tags

Abstract

Indoor localization technology of radio frequency identification (RFID) had gained much attention in recent years, but previous works usually need relative motion between a reader and a tag, or reference tags. Such operation brought about more complexities and difficulties for system deployment. This paper proposes an algorithm that enables centimeter accuracy on ranging and localization in line-of-sight (LOS) and non-line-of-sight (NLOS) environments without relative motion and reference tags. By exploiting physical properties to emulate a large virtual bandwidth on off-the-shelf passive RFID tags and combining with frequency hopping continuous wave (FHCW) algorithm, we can achieve centimeter-level ranging accuracy and perform centimeter-level 3D localization at x/y/z dimensions. In case of missing some channel information, we put a Non-uniform Discrete Fourier Transform (NDFT) to identify LOS path and obtain 1D ranging result with centimeter accuracy. For indoor multi-path environments, we propose an optimized multipath suppression algorithm to ensure centimeter-level accuracy on ranging and localization. Emulation results demonstrate that the algorithm can achieve 2 cm ranging accuracy within the distance of 7 m, and the accuracy probability is above 97%.

1 Introduction

With the increase of large and complex indoor environments such as large shopping malls, large parking lots, airports and so on, there is an urgent need for powerful indoor localization technology to satisfy self-localization and target localization in unfamiliar environments. However, due to indoor multipath effect, the Global Navigation Satellite System (GNSS) signal is rapidly attenuated and even cannot be detected [1,2,3], leading to a sharp drop in indoor localization accuracy. A variety of indoor localization technology came into being under such circumstance. Owing to low cost and simple deployment, the topic of radio frequency identification (RFID) localization has gained much attention from the academic community over the past decade [4, 5]. More generally, RFID localization can enable many applications in libraries, retail stores, warehouses and smart environments.

Many researches have been conducted on RFID localization. In [6, 7], they use the received signal strength (RSS) to achieve localization, however, these methods suffer from poor accuracy and reliability due to indoor multi-path environment since RSS is not sensitive to distance. The localization accuracy can be greatly improved by utilizing reference tags or anchor nodes, but the number of required reference tags or anchors is so large, resulting in extra costs. Besides, reference tags or anchors also need initial deployment with accuracy positions, which increases additional complexity to system deployment. Several arts have also shown tens of centimeter to centimeter accuracy about RFID localization, such as Holographic localization [8], Tagoram [9], PinIt [10] and so on. Unfortunately, they all require relative motion between readers and tags. When motion is required, the system latency is usually high.

Carrier phase-based methods are preferred for their ultra-high sensitivity as a function of distance. TOF obtained by carrier phase is the time that signal travels between a reader and a tag. Emulating a large virtual bandwidth on off-the-shelf passive RFID to obtain carrier phase and compute accurate TOF measurements, we can localize target tag without reference tags and any restrictive assumptions on motion of readers and tags [11]. Based on [11], in this paper, we propose an algorithm that we can leverage Non-uniform Discrete Fourier Transform (NDFT) to identify LOS path under the condition of missing some channel information. In addition, we propose an optimized multipath suppression algorithm to ensure centimeter-level accuracy on ranging and localization.

The rest of this paper is organized as follows. The discussion of virtual bandwidth emulation is presented in Sect. 2. The whole frequency hopping continuous wave (FHCW) algorithm is discussed in Sect. 3, including NDFT and optimized multipath suppression algorithm. The related evaluation results is presented in Sect. 4. And Sect. 5 concludes this paper.

2 A Large Virtual Bandwidth Emulation on Narrowband RFID Passive Tags

In the proposed algorithm, we need to acquire the absolute TOF, so we have to face the challenge – i.e., centimeter-level ranging and localization rely on accurate TOF, and accurate TOF depends on the ability to measure time at a very fine granularity. To achieve the above purpose, a specific hardware would be required to support very high sampling rate or very large bandwidth. However, billions of RFID tags already deployed in today’s world have narrow bandwidth so they can’t meet the requirement. If we design new RFID tags, not only would such a way make non-compliant with today’s FCC regulations and RFID communication protocols, but it would also waste a number of off-the-shelf narrowband RFID tags. Under such background, we present an approach that directly takes advantage of off-the-shelf passive RFID tags to enable centimeter-level ranging and localization.

When a passive tag receives a reader inquiry signal, it responds to the reader by switching its internal impedance between two states, i.e., reflective and non-reflective called the backscatter technology. Since the downlink (reader-to-tag) signal and the uplink (tag-to-reader) signal are on the same carrier frequency, the backscatter is linear. We hence can utilize the physical property to emulate a large virtual bandwidth by frequency hopping pattern. Two reader transmit continuous waves at a frequency $f_{1}$ inside the (Industrial Scientific Medical) ISM band and another frequency $f_{2}$ outside the ISM band respectively and simultaneously. It uses high power $f_{1}$ to power up and communicate with the passive tag, and uses lower power $f_{2}$ to hop over time and collect the channel state information at each of these carriers. The space between adjacent carriers is denoted as $\Delta f$. Then we stitch the channels at the various frequencies to realize a large virtual bandwidth in the time domain as shown in Fig. 1. Such an approach still remains compliant with FCC regulations.

Fig. 1.

In the linear backscatter, a tag responds to the readers. The two readers transmit $f_{1}$ and $f_{2}$ respectively and simultaneously, the tag reflects all the frequency. But after reaching the receiver, $f_{1}$ has already been filtered.

3 FHCW Algorithm Description

The proposal algorithm can enable centimeter localization of UHF (ultra-high frequency) RFID passive narrowband tags in LOS and NLOS environments, so it can operate in multipath-rich indoor environment. The whole algorithm consists of three components: (1) LOS path identification; (2) Optimized multipath suppression and phase cycle ambiguity resolving; (3) 3D localization. The flow diagram of 1D ranging estimate is shown in Fig. 2.

Fig. 2.

The flow diagram of 1D ranging estimate.

3.1 LOS Path Identification

In indoor environment, RF signals bounce off different obstacles (such as ceilings, walls, and furniture). As a result, the receiver obtains several copies of the signal and every copy has experienced a different TOF. In Sect. 2, to obtain accurate TOF, we have already realized a large virtual bandwidth. Multipath resolution is inversely proportional to the bandwidth, given by [12]:

$$ Multipath\,Resolution = 1/B $$

(1)

note that the larger bandwidth is, the higher resolution is. Thus it is not difficult to identify LOS path in the multi-path environments and obtain a rough TOF estimate of that path. Next, we discuss how the TOF of direct path from all the remaining paths teases apart.

To identify the LOS path, we leverage the fact that the LOS path has the shortest distance without experiencing reflectors in contrast to indirect paths, so it arrives the earliest in time under indoor conditions. The visual representation is the first peak in the channel impulse response (CIR) profile, and we can use the TOF corresponding to the first peak as an initial estimate for the LOS distance. If we, however, directly use off-the-shelf narrowband RFID tags with 26 MHz of bandwidth, there are many different paths merge into each other including direct path and indirect paths, since such a small bandwidth results in too low multipath resolution to disentangle the TOF of LOS path according to Eq. (1).

To illustrate, let us consider a transmitter sending a signal to its receiver without multipath effect. Then we can write the wireless channel $h$ as [13]:

$$ h = \alpha e^{ - j2\pi ft} $$

(2)

where $\alpha$ is the signal magnitude, $f$ is the frequency and $t$ is the round trip TOF. When the signal propagates in complex indoor environment, we can write the wireless channel $h$ as:

$$ h_{i} = \sum\limits_{k = 1}^{m} {a_{k} e^{{ - j2\pi f_{i} t_{k} }} } = a_{0} e^{{ - j\frac{2\pi }{c}f_{i} d_{0} }} + \sum\limits_{l = 1}^{L} {a_{l} } e^{{ - j\frac{2\pi }{c}f_{i} d_{l} }} $$

(3)

note that the equation stands for the sum of several Eq. (2). Where $k$ is the number of path to the receiver, $i$ is the number of frequency, $l$ is the number of multipath, $a_{0}$ is the LOS signal magnitude, $a_{l}$ is the each multipath signal magnitude, $d_{0}$ is the distance of the LOS path, $d_{l}$ is the distance of each multipath.

From the above equation, we obtain the channel estimates in the frequency domain. To identify the LOS path, we need to transform the channels from the frequency domain to time domain and find the first peak. Namely we need to perform an Inverse Discrete Fourier Transform (IDFT) following the operation:

$$ h\left( n \right) = IDFT\left[ {H\left( k \right)} \right] = \frac{1}{N}\sum\limits_{k = 0}^{N - 1} {H\left( k \right)e^{{j\frac{2\pi }{N}nk}} } $$

(4)

where $H\left( k \right)$ denotes the wireless channel in frequency domain obtained by Eq. (3). We can directly realize time domain representation and CIR profile through inverse fourier transform function in Matlab as shown in Fig. 3. Due to a large bandwidth leading to high time resolution, we can observe that the peak in the profile is sharp.

Fig. 3.

CIR profile at 220 MHz bandwidth. Due to a large bandwidth leading to high time resolution, we can directly leverage IDFT to identify LOS path and obtain the TOF (i.e. to compute initial distance estimate.)

There is a premise for such a method, which leverages IDFT to identify LOS path that the reader transmits continuous carrier wave $f_{2}$ over time by a way of hopping and the receiver obtains the channel measurements at many uniformly-spaced frequencies. If these measurements are not equally spaced frequencies, due to losing packets at some frequencies, IDFT cannot be simply used to separate individual paths and identify LOS path. In order to solve this problem, Inverse Non-uniform Discrete Fourier Transform (INDFT) is proposed. Here, we still use the principle of NDFT [14] instead of INDFT which gives:

$$ H\left( k \right) = \sum\limits_{n = 0}^{N - 1} {h\left( n \right)e^{{ - j\frac{2\pi }{T}kt_{n} }} } $$

(5)

where $T$ represents total sampling time, $t_{n}$ denotes different time per sampling. The equation transforms the channels from the time domain to frequency domain. Now we replace total sampling time with hopping frequency band and use each of hopping frequencies instead of time per sampling to achieve time domain profile, and Eq. (5) can be modified as:

$$ h\left( n \right) = \sum\limits_{n = 0}^{N - 1} {real[H\left( k \right)]e^{{ - j\frac{2\pi }{F}kf_{n} }} } $$

(6)

It should be noted that we only choose real part of the channel measurements. Where $F$ is hopping frequency band, $f_{n}$ is each of the hopping frequencies, hopping interval $\Delta f$ is non-uniform because of packet missing at some frequencies. Figure 4 shows the time domain profile lacking four frequencies with the same distance of LOS path as Fig. 3.

Fig. 4.

CIR profile at 220 MHz bandwidth lacking four frequencies. Such means can realize CIR profile that is symmetrical distribution with half of time as the axis of symmetry. It does not affect initial distance estimate that we only take a part of symmetrical distribution for analysis since actual localization distance is within 10 m in indoor environment.

Compared with Fig. 3, Fig. 4 demonstrates that although the receiver lacks some packet corresponding to several frequencies, we can also identify the LOS path and obtain a TOF estimate of that path to compute initial distance estimate. Even if there are some missed packets, IDFT and NDFT have the same effect on identifying LOS path.

3.2 Optimized Multipath Suppression and Phase Cycle Ambiguity

After identifying the LOS path and obtaining initial distance estimate $\tilde{d}_{0}^{c}$ corresponding to the estimated TOF, we can strengthen the LOS path and suppress the multipath in frequency domain through the following operation [11]:

$$ \theta_{k} = \angle \sum\limits_{i = 1}^{K} {h_{i} e^{{j\frac{2\pi }{c}\left( {f_{i} - f_{k} } \right)\tilde{d}_{0}^{c} }} } $$

(7)

where $c$ is the speed of signal propagation, $\angle$ denotes phase solving. And we can observe that LOS phase can reinforce about $K$ times but NLOS phase strengthen far less than $K$ times by expanding the equation. By this way, suppressing the multipath is achieved. Figure 5 demonstrates we can obtain better phase through multipath suppression to achieve centimeter ranging and localization.

Fig. 5.

Unwrapped phase with hopping frequencies. The black line is phase collected in multi-path indoor environment. The blue line denotes phase obtained by multipath suppression. The red line represents phase of only LOS path. Noise effects in all three cases. (Color figure online)

Even though multipath suppression can be realized by Eq. (7), the effect of multipath on phase still exists and influences the phase of LOS path. As a result, we can exploit some phase measurements to achieve better multipath suppression, given by:

$$ \theta_{l} = \angle \sum\limits_{i = 1}^{K} {h_{i} e^{{j\frac{2\pi }{c}\left( {f_{i} - f_{l} } \right)\tilde{d}_{0}^{c} }} } $$

(8)

where $l = \left( {K + 1} \right)/2$. $K$ is odd number. For example, when we take $i$ from 1 to 39, thus $l = 20$ and $\theta_{20}$ is just what we want. What our improvement is that we perform five or more times such operation and combine the obtained multiple phases to solve phase cycle ambiguity. The suppression approach is always applicable regardless of whether the packets corresponding to some frequencies are missed.

After the filtered phases are obtained, the phase ambiguity can be resolved by the Chinese Remainder Theorem (CRT) [15]. Since the collected phase is always within $\left[ {0,2\pi } \right)$, cycle ambiguity exists when the distance is longer than one wavelength. When the collected phase is $\theta$, the actual phase can be $\theta + 2n\pi$, where $n$ is the cycle integer. The standard modular arithmetic algorithm can be reflected in distance as following equation:

$$ d_{l} = \frac{{\theta_{l} c}}{{2\pi f_{l} }}\quad \bmod \lambda_{l} $$

(9)

where $\theta_{l}$ is the filtered phases at different frequencies, $\lambda_{l}$ is the wavelength at different frequencies. By computing multiple such $d_{l}$ at different frequencies and picking the solution satisfying the most number of equations (i.e., the $d$ with most number of aligned lines in Fig. 6), we can obtain the unique and centimeter-level ranging result $d$.

Fig. 6.

Resolving phase cycle ambiguity by CRT. We pick the $d$ with most number of aligned lines.

3.3 3D Localization

In the previous section, we have obtained the centimeter-level 1D ranging. Since each ranging result is a distance from the target tag to an Rx antenna, in 3D space, one ranging gives a sphere as shown in Fig. 7(a). To uniquely localize the target tag through trilateration [16] given by Eqs. (10) and (11). Three spheres are required to compute the intersection point as depicted in Fig. 7(b).

$$ \begin{aligned} & (x_{1} - x_{0} )^{2} + (y_{1} - y_{0} )^{2} + \left( {z_{1} - z_{0} } \right)^{2} = d_{1}^{2} \\ & (x_{2} - x_{0} )^{2} + (y_{2} - y_{0} )^{2} + \left( {z_{2} - z_{0} } \right)^{2} = d_{2}^{2} \\ & (x_{3} - x_{0} )^{2} + (y_{3} - y_{0} )^{2} + \left( {z_{3} - z_{0} } \right)^{2} = d_{3}^{2} \\ \end{aligned} $$

(10)

$$ \left[ {\begin{array}{*{20}c} {x_{0} } \\ {y_{0} } \\ {z_{0} } \\ \end{array} } \right] = \left( {A^{T} A} \right)^{ - 1} A^{T} b $$

(11)

where $A = \left[ {\begin{array}{*{20}c} {2\left( {x_{1} - x_{3} } \right)} & {2\left( {y_{1} - y_{3} } \right)} & {2\left( {z_{1} - z_{3} } \right)} \\ {2\left( {x_{2} - x_{3} } \right)} & {2\left( {y_{2} - y_{3} } \right)} & {2\left( {z_{2} - z_{3} } \right)} \\ \end{array} } \right]$, $b = \left[ {\begin{array}{*{20}c} {x_{1}^{2} - x_{3}^{2} + y_{1}^{2} - y_{3}^{2} + z_{1}^{2} - z_{3}^{2} - d_{1}^{2} + d_{3}^{2} } \\ {x_{2}^{2} - x_{3}^{2} + y_{2}^{2} - y_{3}^{2} + z_{2}^{2} - z_{3}^{2} - d_{2}^{2} + d_{3}^{2} } \\ \end{array} } \right]$

Fig. 7.

3D localization by three spheres intersection. (a) A sphere obtained by a ranging. (b) Intersection sphere obtained by three ranging.

4 Evaluation Results

We perform intensive emulation experiments and prove that the presented approach can realize centimeter accuracy on ranging and localization. In our emulation, the bandwidth is 220 MHz and hopping space is 5 MHz, so the multipath resolution is about 4.5 ns and the corresponding distance resolution is around 1.35 m. We assume the receiver obtained four copies of the transmitted signal in indoor environment, including one LOS path and three NLOS paths. We take the first ten energy columns in CIR histogram to analyze the performance of proposed method and obtain the initial distance estimate since RFID localization distance is generally within 10 m.

Figure 8(a) (b) show the 1D ranging accuracy under different distances. Figure 8(a) and (b) correspond to two cases of whether packets are missed, respectively. We can observe that the algorithm can achieve 2 cm accuracy on ranging within 7 m in both cases. The 2 cm accuracy probability is above 97%.

Fig. 8.

1D ranging accuracy with distance variety. (a) shows that the 1D ranging accuracy gradually decreases with distance without missed packets. (b) shows that the 1D ranging accuracy gradually decreases with distance and is worse than (a) for missed four frequencies corresponding channel information.

Figure 8(b) demonstrates that the 1D ranging accuracy is worse than Fig. 8(a) since the missed packets have influence on subsequent multipath suppression algorithm. However, as long as the number of missed packets is not very much, the 1D ranging accuracy is still able to satisfy our centimeter-level requirement in most cases as shown in Fig. 8(b).

Figure 9(a) (b) depict the relationship between ranging accuracy and bandwidth and hopping space respectively under the condition of without missed channel information.

Fig. 9.

1D ranging accuracy vs. different factors. (a) shows that 1D ranging accuracy gradually increases with bandwidth. (b) shows that 1D ranging accuracy gradually decreases with hopping space.

Figure 9(a) demonstrates that the 1D ranging accuracy gradually improves with increased bandwidth when the hopping space is 5 MHz. Besides, bandwidth is only close to 200 MHz, which can achieve centimeter-level ranging and localization when the energy of LOS path is enough high. Figure 9(b) demonstrates that the 1D ranging accuracy gradually decreases when the bandwidth is 220 MHz and the hopping space slowly increases from 5 MHz to 15 MHz. Therefore we generally take the hopping space to be equal to 5 MHz or 10 MHz, by doing so, we can make the performance of ranging and localization better and take integer number of frequencies when emulating a bandwidth of 220 MHz via frequency hopping.

After obtaining the 1D centimeter-level ranging, we can leverage two receiver antennas to achieve centimeter accuracy on 2D localization through Least squares [17] or weighting method. To perform 3D localization, we can exploit three receiver antennas and trilateration [16] to compute the optimal solution in intersection area of three sphere.

5 Conclusion

This paper presents an algorithm that enables centimeter accuracy on ranging and localization without relative motion or any reference tags. For this purpose, we first exploit off-the-shelf passive RFID tags to emulate a large virtual bandwidth, and then perform FHCW algorithm including LOS path identification, multipath suppression optimization, phase cycle ambiguity solving and 3D localization. We believe the proposed approach can provide a new idea for RFID indoor localization technology.