Indoor localization using augmented ultra-high-frequency radio frequency identification system for Internet of Things

Abstract

This article addresses the problem of indoor localization with an augmented ultra-high-frequency radio frequency identification system. In the infrastructure of augmented ultra-high-frequency radio frequency identification system, a tag-like component called sense-a-tag applies envelope detection to capture the backscatter signals of other ultra-high-frequency tags in its proximity during their tag-to-reader communication. Such unique capability of sense-a-tag enables tag-to-tag backscatter communication. Tag-to-tag backscattering communication in augmented ultra-high-frequency radio frequency identification system has an obvious advantage over the conventional reader-to-tag link for proximity-based indoor localization by keeping both landmark and mobile tags simple and inexpensive. Through the investigation of tag-to-tag backscattering communication link, a new and more realistic probability model of detecting a tag by sense-a-tag is proposed. In augmented ultra-high-frequency radio frequency identification system, a large set of passive tags are placed at known locations as landmarks, and sense-a-tags are attached mobile targets of interest. We identify two technical roadblocks of augmented ultra-high-frequency radio frequency identification system and existing localization algorithms as false synchronous detection assumption and state evolution model constraints. With the new and more realistic detection probability model, we explore the use of particle filtering methodology for localizing sense-a-tag, which overcomes the aforementioned roadblocks. The performance of localization algorithm is demonstrated by extensive computer simulations.

Keywords

Internet of Things augmented ultra-high-frequency radio frequency identification system indoor localization tag-to-tag backscattering communication particle filter

Introduction

It is widely recognized that the Internet of Things (IoT) will be the third innovation wave of Information and Communication Technology (ICT) world, following the computer in 1940s and the Internet in 1970s.¹ The IoT conceptually means ‘who’, ‘where’ and ‘how’ of physical objects, such as food packages in supermarkets, pharmaceutical boxes in stores and file folders in offices. It is anticipated that trillions of radio tags will be embedded into objects, monitoring their physical properties, providing automation identification, as well as geographic location information. Therefore, following the achievement of satellite-based positioning systems in outdoor environment, the provision of localization service for trillions of objects in indoor environment forms the major bottleneck preventing seamless localization. Due to its low cost, miniature size, ease deployment and ultra-low power consumption, ultra-high-frequency (UHF) radio frequency identification (RFID) continues to gain recognition as a pivot enabler for IoT indoor localization applications.²

The majority of state-of-the-art UHF RFID localization methods are based on the fusion of relevant information of RF signals returned to RFID reader from tags. Examples of such information include received signal strength indicator (RSSI),³ angle of arrival (AoA),^4,5 time of arrival (ToA)⁶ phase of arrival (PoA)^7,8 and time difference of arrival (TDoA).² The major problem with the above methods is that they are easily affected by the non-line-of-sight (NLoS) conditions, severe multipath distortions and fast temporal changes of indoor environment.⁹ Besides that, these methods suffer from cost and system complexity issues. For example, AoA-based methods require complex and customized designed reader hardware. ToA-, TDoA- and PoA-based methods require multiple reference points, which are expensive RFID readers.¹⁰

One direction to address this problem is to apply proximity-based method, which relies on using binary measurements related to whether a target is within a small range of the reference landmarks. Existing approaches are to deploy passive tags at fixed locations as landmarks and attach the RFID reader to the mobile target and vice versa. Usually, the former approach is referred to as reader-based method, while the latter as tag-based method. In DiGiampaolo,¹¹ researchers deploy a grid of UHF RFID tags on the ceiling of the building. The read region of each tag is well defined, thus the floor environment is subdivided into a set of cells. When the target equipped with reader enters into the read region of UHF RFID tag, the tag ID or the equivalent tag coordinates are retrieved. The location of target is estimated according to retrieved data. Based on such reader-based technique, multiple indoor localization systems have been proposed.^12–14 In Geng et al.,^15,16 the area is covered by a mesh grid of a large set of RFID readers and associated antennas, whose locations are known. The objects with attached UHF RFID tags are localized and tracked using particle filter-based inference algorithm.

However, these approaches are strictly constrained by energy, cost and size. For example, the former approach is limited to relatively large and expensive objects that justify carrying the RFID reader, such as autonomous household robot. In the latter approach, it is not cost-efficient to densely deploy readers with tuned read range.

In our previous work, an EPCglobal Class1 Gen2 compliant UHF RFID component ST (from sense-a-tag) was proposed.¹⁷ In the same way as passive tags, ST applies envelope detection to extract baseband signal in the receiving path, and backscatter modulation to talk back in the transmitting path respectively. The difference is that ST’s receiving path does not only capture RFID reader’s pulse-interval-encoding (PIE) command signal but also passive tags’ backscattering signal. Such unique functionality enables tag-to-tag backscattering communication link, which keeps both landmark and mobile tags simple and inexpensive.

We showed how to use ST in augmented ultra-high-frequency radio frequency identification system (AURIS) for indoor localization in Athalye et al.⁹ The probabilistic model of detecting a tag by ST is introduced as the function of the distance between the tag to ST.¹⁸ However, through investigation of tag-to-tag backscattering communication link, it is demonstrated that the carrier wave (CW) from RFID reader has a major effect on ST-to-tag detection probability.^19–21 In this article, the probabilistic model is extended to be more realistic by integrating the distance and relative angle between the tag and the reader’s antenna, and considering the interference of reader’s CW on ST, the so-called phase cancellation effect.

We propose a novel particle filter with autoregressive model and auxiliary input (PF-AA) as inference algorithm for AURIS indoor localization. Some previous work dealing with particle filter-based RFID indoor localization possess strong assumption and constraints on the target state-space model, such as exact knowledge of the initial position of the moving object with ST, linear target motion model or exteroceptive sensor information.^18,22,23 Additionally, according to ST’s Gen2-based locator protocol, the host computer controls reader to send out a fixed number of successive query rounds to the reference tags. Then, the inference algorithm localizes ST using aggregated binary information reported by ST.¹⁷ Existing inference algorithms rely on false synchronous detection assumption that assumes that the detection measurements are received by ST at the same time instance.^9,18,21 The novel PF-AA introduces current measurements into a constraint-free auto-regressive (AR) state evolution model, and it also addresses the asynchronous measurements with a minor modification of ST locator protocol which is still EPC Gen2 compliant.

In summary, this work makes two major contributions. It proposes a novel detection probability model for ST-to-tag communication link, which is based on the systematic analysis about the tag-to-tag backscattering communication scheme. We then propose PF-AA algorithm for the ST-based AURIS localization system. To this end, we identify two technical roadblocks of AURIS and existing localization algorithm as false synchronous detection assumption and state evolution model constraints. It is demonstrated that the proposed PF-AA algorithm overcomes such roadblocks. The rest of this article is organized as follows: in section ‘Background and related work’, we introduce the background and related work. The new probabilistic detection model is presented in section ‘Detection probability model’. In section ‘Proposed localization method’, the PF-AA algorithm is introduced. In ‘Performance evaluation’, we provide the simulation results which show the performance of the proposed localization methods, followed by the conclusion and future discussion in section ‘Conclusion’.

Background and related work

Augmented UHF RFID system (AURIS)

In Athalye et al.,¹⁷ we proposed a tag-like UHF RFID component, referred to as ST. The ST has dual functionality: it is capable of sensing the backscattering communication between RFID reader and nearby passive tags, and it can also communicate the sensed information with RFID reader via backscatter communication like a standard passive tag. By adding ST to the off-the-shelf UHF RFID system, the augmented UHF RFID system can offer fine-grain localization scheme in indoor scenario.

Figure 1 shows the block diagram of ST hardware. The antenna is followed by a backscatter modulator, a corresponding matching network and a conventional diode envelope detector circuit. The output of envelope detector is fed into the analogue section, which has the ability to process both reader’s PIE signal and the tag’s backscatter. The analogue processing of reader’s PIE signal is exactly the same as the standard passive tag, which employs a hysteresis comparator to generate digital signal. The processing circuit of tag’s backscattering signal is more complex, which consists of a band-pass filter for removing the DC offset, followed by a comparator acting as one-bit A/D converter. The output of analogue section is the input of digital section, which runs finite state machine (FSM) for Gen2-based ST locator protocol. The detailed description and performance evaluation of ST are presented in Athalye et al.⁹

Figure 1.

Block diagram of ST hardware.

Figure 2 shows a deployment scenario of AURIS for fine-grained proximity-based localization. The system is composed of a personal computer running the localization algorithm, an off-the-shelf RFID reader, a large set of passive tags placed at known position and an ST attached to mobile target of interest. The detection range of ST, where it can detect tag’s backscatter, is shown by a dotted circle in figure. Accroding to field experiment, the detection range of ST-to-tag is around 1 m.²¹ Thus, ST can acquire the ID information of the tags within the detection range. Since the position of landmark tags are prior known, the host computer could aggregate the association information to localize ST.

Figure 2.

Deployment scenario of AURIS.

Tag-to-tag backscattering communication

UHF RFID provides superior performance among passive RFID systems, ensuring a larger operating distance (up to several meters), a higher data rate (up to hundreds of kb/s) and a smaller antenna size.¹ The conventional UHF RFID system is characterized as asymmetric communication where the majority of communication burden is shifted to the carrier-modulated transceiver RFID reader. Both reader-to-tag and tag-to-reader communication links have been thoroughly studied.^24–26 Unlike the conventional UHF RFID, tag-to-tag communication relies neither on an active radio for transmitting query signals nor on a full-scale IQ demodulator to the response. It relies purely on backscatter modulator to convey data to other tags and on passive envelope detector for the response. Tag-to-tag backscattering communication has been explored in literature, but mainly as a feasibility study.^17,27 While the general feasibility has been established, virtually not much attention has been paid to characterize the tag-to-tag communication link. One of the pioneering works in the field characterizes inter-tags communication by the near-field mutual coupling model.²⁸ However, it is not applicable for the ever increasing tag-to-tag range. The rest of this section aims to present the propagation mechanism governing tag-to-tag backscattering communication, and then set up some design guidelines for modelling ST-to-tag detection probability.

Tag-to-tag link budget

Figure 3 depicts the scheme of tag-to-tag backscattering communication link wherein the CW signal is provided by RFID reader. The first radio link budget is the linear-scale, power-up link budget that describes the amount of power arriving at the transmitting tag’s antenna²⁴

P_{T T} = \frac{P_{R F} G_{R F} G_{T T} λ^{2} X_{R T}}{{(4 π D)}^{2} Θ_{T T} B_{R T}}

(1)

where $P_{TT}$ is the power received by the transmitting tag antenna, $P_{RF}$ is the power transmitted by reader antenna, $G_{RF}$ is the free-space gain of reader antenna, $G_{TT}$ is the free-space gain of transmitting tag antenna, $Θ_{TT}$ is the on-object gain penalty of the transmitting tag antenna, $X_{RT}$ is the polarization mismatch of reader to transmitting tag, $B_{RT}$ is the blockage loss of reader to transmitting tag, $λ$ is the carrier frequency wavelength and $D$ is the distance from reader to transmitting tag. Equation (1) is similar with the form of Friis Equation,²⁹ but accounts for losses $Θ, B$ commonly encountered in indoor environment.

Figure 3.

Schematic depiction of tag-to-tag backscatter link.

The second link budget is the tag-to-tag backscatter link budget that governs the amount of modulated backscatter power received by the receiving tag

P_{R T} = \frac{P_{R F} G_{R F} G_{T T}^{2} G_{R T} λ^{4} X_{R T} X_{T R} σ}{{(4 π)}^{4} D^{2} d^{2} Θ_{T T} Θ_{R T} B_{R T} B_{T T}}

(2)

where $P_{RT}$ is the power received by the receiving tag antenna from the transmitting tag, $G_{RT}$ is the free-space gain of the receiving tag antenna, $X_{TR}$ is the polarization mismatch of transmitting tag to receiving tag, $B_{TT}$ is the blockage loss of transmitting tag to receiving tag, $d$ is the distance from transmitting tag to receiving tag separation, $σ$ is the radar cross section (RCS) of transmitting antenna and all other terms are as defined in equation (1). The RCS $σ$ is a measure of the amount of power backscattered by an antenna. In equation (2), the power received at the receiving tag goes as the inverse square of the separation distance between reader and transmitting tag, as well as the inverse square of the separation distance between transmitting tag and receiving tag. It is also proportional to the antenna gains. Therefore, it is evident that detection model should integrate these two separation distances and antenna gains.

Phase cancellation effect

In tag-to-tag backscatter communication scheme, the RFID reader must transmit CW for the tag to backscatter. Consequently, the signal at the receiving tag’s antenna is the superposition of reader’s continuous CW and the transmitting tag’s backscattering signal. Unfortunately, due to the relative phase difference between them, the modulation depth of transmitting tag’s backscattering signal at receiving tag’s envelope detector could be significantly attenuated or even cancelled out. We refer such effect to as phase cancellation effect.¹⁹ Since the proximity-based localization method purely depends on the detection of proximal tags by ST, handling the challenge of phase cancellation is the critical step for indoor localization. Various techniques have been proposed to counter the phase cancellation by introducing space or modulation diversity.^19,20,30 It is demonstrated that with these techniques, the overall probability of phase cancellation is reduced to be negligible.

PASS simulation framework

AURIS is modelled in our newly developed proximity-detection-based augmented RFID system simulator (PASS) framework. PASS is a time-domain system-level simulator, which is based on position-aware RFID system (PARIS) simulation framework.³¹ The development environment is MATLAB 2012a on Windows 8.1 (64 bits). The development of PASS simulation framework aspires to facilitate the research for indoor localization with UHF RFID technology. From PARIS simulation framework, PASS inherits the behaviour model of a NXP UCODE G2XM–based passive UHF RFID tag and wireless propagation channel, as well as a core framework to perform simple control and logging. While PARIS mainly focuses on ranging rather than the system behaviour, we completed the functionality of generic reader and tag so that the simulator behaves according to ISO 18000-6C protocol. The ST model is designed to emulate the specific ST device. The detailed structure and component description are presented in Wang and Bolic.²⁰ Noteworthily, the Q selection algorithm in Gen2 protocol is not implemented in the simulator, since the simulation platform MATLAB is discommodious for scheduling algorithm and also slow for massive computation tasks. Having the whole system implemented in the simulator allows for much faster evaluation of the system and faster validation of the effectiveness of ideas. The software and tutorial are available on Github repository.³²

Detection probability model

The location inference algorithm of AURIS relies on the detection probability model of ST-to-tag, which describes the relationship between successive detection and the true state of reader, tag and ST. In our previous work,¹⁸ the detection probability of ST-to-tag is proposed as a function of Euclidean distance between ST and tag, which is a common sensing model for active radios.³³

However, according to the research on tag-to-tag backscattering communication, the detection probability depends on other numerous factors including the distance from reader antenna, the orientation of antenna and phase cancellation effect. In this section, we therefore develop a more realistic detection probability model that is better suited for ST-to-tag communication link. First, the detection probability model is modelled as the function of the distance and (elevation, azimuth) angle pair from reader antenna to tag, as well as the distance between tag to ST. Secondly, augmented by phase cancellation effect-reducing techniques, phase cancellation has an insignificant effect on detection probability. Therefore, the detection probability model does not include the superposition of reader CW and tag’s backscattering.

Figure 4 depicts the distance D, azimuth $θ$ and elevation $ϕ$ from reader antenna to tag, as well as the distance d from tag to ST. The azimuth $θ$ represents the relative orientation angle between antenna (X, Z) plane and antenna-to-tag direction. The elevation $ϕ$ represents the relative orientation angle between antenna (X, Y) plane and antenna-to-tag direction. Both of these angles have the range of $[- π / 2, π / 2]$ . The detection probability of ST-to-tag $p (D, d, θ, ϕ)$ is formulated with the logistic regression model

p (D, d, θ, ϕ) = \frac{1}{1 + e^{a_{0} + a_{1} D + a_{2} d + a_{3} | θ | + a_{4} | ϕ |}}

(3)

where ${a_{k}, k = 0, 1, 2, 3, 4}$ are the model coefficients. The logistic regression model is used to estimate the probability of a binary response based on one or more variables, restricted to the range $(0, 1)$ .³⁴ We refer to such model as reader-tag-ST (RTS) model.

Figure 4.

Representation of detection probability model parameters.

For comparison, the previous model, where the detection probability is a function of distance between tag and ST, is presented. We refer to this probability detection model as TS model

p (d) = \frac{1}{1 + e^{a_{0} + a_{1} d}}

(4)

where $d$ is the distance between tag and ST, and $a_{0}$ and $a_{1}$ are the model coefficients.

We evaluated the proposed detection probability model by the experiment data obtained from PASS simulation framework. In the experiment, the reader antenna is RFMAX S9028PCRJ, which is a circularly polarized panel antenna working at 902–928 MHz frequency band. The power level of reader antenna is set as 30 dBm. Figure 5 plots the antenna radiation pattern. The channel type is selected as “room” in PASS. The reader antenna is placed at the origin $(0, 0, 0)$ . The position of tag is uniformly distributed over the cuboid area, where $x \in [1, 8] m$ , $y \in [- 4, 4] m$ and $z \in [- 4, 4] m$ . There are 3000 possible positions for tag, which are obtained by Monte Carlo sampling method. The position of ST is randomly sampled within the sphere, whose globe is at tag position and radius is 2 m. The detection y of ST-to-tag is recorded. The cost function for training the logistic model is³⁵

\begin{matrix} J (a) = \frac{1}{m} \sum_{i = 1}^{m} [- y^{(i)} \log (p_{a} {(D, d, θ, ϕ)}^{(i)}) - (1 - y^{(i)}) \\ • \log (1 - p_{a} {(D, d, θ, ϕ)}^{(i)})] \end{matrix}

(5)

where m is the size of dataset.

Figure 5.

Antenna radiation pattern.

We apply gradient descent method to estimate the model coefficient. Since the objective is to minimize the cost function $J (a)$ , gradient descent method obtains the optimized parameters according to the following equation

a_{k} = a_{k} - α \sum_{i = 1}^{m} (y^{(i)} - p_{a} (D, d, θ, ϕ)^{(i)}) (D, d, θ, ϕ)_{k}^{(i)}

(6)

where $(D, d, θ, ϕ)_{k}^{(i)}$ is 1 for $k = 0$ , $D^{(i)}$ for $k = 1$ , $d^{(i)}$ for $k = 2$ , $| θ |^{(i)}$ for $k = 3$ and $| ϕ |^{(i)}$ for $k = 4$ . $α$ is the scaling parameter in gradient descent method. The estimated values are $a_{0} = - 1.462$ , $a_{1} = 0.4941$ , $a_{2} = 2.506$ , $a_{3} = 0.0126$ and $a_{4} = 0.0523$ . Figure 6 shows the visualized detection probability model. It is found that distances $D$ and $d$ are much more significant in affecting the detection probability than orientation of the tag with respect to reader antenna. The reason is mainly related to the radiation pattern of panel antenna, as well as the position sampling space of tag and ST in experiment. Following the same manner, we obtain the estimated coefficient values for TS model, where $a_{0} = 0.8970$ and $a_{1} = 2.4443$ . The visualized detection probability is plotted in Figure 7.

Figure 6.

Estimated detection probability versus (a) D and d with $θ = 0$ , $ϕ = 0$ (b) $θ$ and $ϕ$ with $D = 2 m$ , $d = 0.5 m$ for RTS model.

Figure 7.

Detection probability versus $d$ for TS model.

Figure 8 shows the calculated detection probability based on the samples from training dataset. In Figure 8(a), the data samples are collected within the region $d \in [0.4, 1] m$ . The detection probability is calculated along the variable $D$ with the interval as $0.3 m$ shown by the bar chart. The probability curves of RTS and TS models are plotted along the variable $D$ at $d = 0.6 m$ . Since the TS model purely depends on the parameter $d$ , the distance between tag and ST, the detection probability is constant over the range of $D$ . In Figure 8(b), the data samples are collected with the region $D \in [2, 4] m$ . The detection probability along the variable $d$ with the interval as $0.2 m$ . The probability curves of RTS and TS models are plotted along the variable $d$ , in which the parameter $D$ of RTS model is set at $3 m$ . From Figure 8, we can see that probability curve of RTS model agrees with the dataset, while the TS model suffers from the underfitting problem.

Figure 8.

Detection probability versus (a) $D$ with data from region $d \in [0.4, 1] m$ and (b) $d$ with data from region $D \in [2, 4] m$ .

Finally, we obtain another 1000 measurement samples with the same simulation setup as test dataset. The cost is computed according to equation (5). The cost of RTS model on test dataset is 0.1278, while the cost of TS model is 0.1502. Therefore, we can conclude that RTS model has higher modelling accuracy than the TS model.

Proposed localization method

Overview of our method

The objective of this section is to propose an accurate method for continuous localization of moving objects using AURIS localization system. A possible deployment of AURIS localization system is shown in Figure 2. As briefly mentioned in earlier section, populated with passive tags with known locations in the environment, the ST-tagged objects can be localized based on the aggregated ST-to-tag detection binary information.

In some of our previous work,^9,18,21 we have studied various inference algorithms for AURIS localization system. First, we introduced weighted centroid localization (WCL) method, which is commonly used in wireless sensor network localization application.³⁶ The key idea of WCL method is to apply the weighted average of the detected tags’ locations. The WCL method is computationally inexpensive, but yields coarse location estimation. We then propose a general method for continuous localization of ST using particle filtering (PF), by which the localization accuracy is improved but with higher computation cost.¹⁸ Since the computation task is executed on the host server, the increased computation cost draws little concern. However, two fundamental issues, which deteriorate the localization accuracy, are identified in AURIS design itself and PF algorithm. These issues are discussed in the next section.

False synchronous detection assumption

EPCglobal Class1 Gen2 MAC protocol adopts a adaptive slotted Aloha variant.²⁹ ST locator protocol specifies two states for ST operation: Listening and Responding. In Listening state, ST does not respond to the RFID reader and instead listens for the backscatter of tags in its proximity. Once upon receiving any backscatter signal, ST decodes the signal, extracts the tag’s ID and stores a hash value corresponding to the ID temporarily. In Responding state, ST itself functions as standard passive tag and conveys the acquired ID information to RFID reader as part of its EPC payload. These operation states of ST are initiated by two distinct RFID reader queries ( $Q_{T}$ for Listening, $Q_{S}$ for Responding). In AURIS, reader first sends out $N$ rounds of $Q_{T}$ to address passive tags, and also drives ST to $Listenning$ state. During this query, ST listens to tag’s backscattering in its proximity. If ST captures any tag’s backscattering, it records the tag’s ID and the associated read rate out of $N$ . The following query $Q_{S}$ drives ST to $Responding$ state, and then ST responds the recorded tag ID and read rate back to reader. Finally, the host server runs localization algorithm for determining ST location. However, existing localization algorithms treat the detection measurements in $N$ rounds indiscriminately, which assumes that all the measurements are obtained at the time instant of $Q_{S}$ . As shown in Figure 9, RFID reader sends out 4 rounds of $Q_{T}$ queries to address landmark tags Tag 1 and Tag 2. The traditional localization algorithms treat the detection of tag by ST indiscriminately, which means it would use the detection rate 4 and 2 as the measurements input. We refer to this situation as false synchronous detection assumption. Such assumption is appropriate when ST is static. But it introduces a significant bias to the estimated ST location when ST is moving, especially when the speed is high. Noteworthily, the positioning precision is related with value of N. Since the positioning algorithm used in the paper mainly based on read rate. With higher N value, the detection rate would be more proportional to the detection probability of reader-to-tag. However, according to Gen2 protocol (?), higher N value means that the single localization step would consume more time, which leads to low update frequency. The low update frequency would be a major concern for target tracking problem.

Figure 9.

Representation of a set of queries $Q_{T}$ and $Q_{S}$ with $N = 4$ .

State evolution model constraints

In PF-like sequential Bayesian estimation algorithm, the state evolution model is used to approximate the current state based on the history.³⁷ Existing PF algorithms for AURIS localization application put strict constraints on the dynamic input of state evolution model.^18,38 These state evolution models have remarkable performance when the dynamic pattern of target motion is a priori known and comparatively stable. However, the performance of these models degenerates severely when the dynamic pattern is different. Besides, these algorithms require prior knowledge about initial state of target.

PF-AA algorithm

Our method includes two simple ideas: (1) we estimate the velocity of the moving target based on the estimation state history and current measurement using AR model. The current measurement is introduced into the AR model by WCL method. In Yang and Wu,¹² the velocity of state evolution model is updated by the time duration of each landmark tag staying in the reader’s reading range. The estimation is highly inaccurate and unreliable. To the best of our knowledge, our method is the first to use WCL on fusing the current measurement into the state evolution model; (2) we implement a minor modification, that will be described later, to ST locator protocol, by which the host server is able to obtain the asynchronous detection time information. Based on such information, the estimation bias could be computed. With these two ideas, we design PF-AA algorithm for better accuracy and applicability in indoor target localization application.

As mentioned earlier, RFID reader sends out the number of $N$ rounds of $Q_{T}$ queries in the time interval between $t - 1$ and $t$ . In the original ST locator protocol, ST simply accumulates the read rate of passive tags in its proximity. To counter the false synchronous detection assumption, a minor modification is introduced to record the asynchronous detection associated information. Since it is designed to be simple and energy efficient, ST is not a good candidate for the modification to record the detection information. Instead, we propose RFID reader records the time instant of successive detection associated with the tag ID for each query. In addition, ST reports to the reader the query round number of detections for each detected passive tag rather than merely the read rate out of $N$ . The host server obtains the time instants for each tag detection of ST by fusing the recorded information together. The modified ST locator protocol is still EPCglobal Class1 Gen2 compliant. We denote the detection of the specific passive tag $T_{k}$ at time $t$ by

\begin{matrix} y_{t, k} = {n_{t, k}, τ_{i, k}; n_{t, k} < N, t - 1 < τ_{i, k} < t \\ i \in {1, \dots, n_{t, k}}} \end{matrix}

(7)

where $n_{t, k}$ is the read rate and $τ_{i, k}$ is the time instant of ith detection of tag $T_{k}$ .

The state evolution model characterizes the location state $x_{t} = [x_{1, t} x_{2, t}]$ of the moving target over time. The main purpose of the state evolution model is to predict location state $x_{t}$ , given the most current one $x_{t - 1}$ . The implementation of state evolution model depends on the dynamic pattern of the moving target. In this work, we utilize MA model to represent the discrete state evolution model as follows

x_{t} = x_{t - 1} + v_{t} Δ t + q_{t}

(8)

where ${\hat{v}}_{t} = [{\hat{v}}_{1, t} {\hat{v}}_{2, t}]$ denotes the ST velocity estimation based on the current measurement and history estimation. $q_{t}$ is the noise vector with known Gaussian distribution.

Now we address the velocity estimation given the target location $x_{t - 1}$ and velocity $v_{t - 1}$ from previous sampling step, as well as the current measurement ${y_{t, k}, k \in {1, \dots, N_{tag}}}$ .

First, the current target location $x_{t}$ is estimated through WCL method

\begin{matrix} {\hat{x}}_{t}^{*} = \frac{\sum_{i = 1}^{N_{tag}} (n_{t, i} \cdot L T_{i})}{\sum_{i = 1}^{N_{tag}} n_{t, i}} \end{matrix}

(9)

where ${L T_{i}, i \in 1, \dots, N_{tag}}$ are the known locations of landmark tags. Then, the velocity estimation $v_{t}^{*}$ simply based on the current measurements is calculated by

\begin{matrix} {\hat{v}}_{t}^{*} = \frac{{\hat{x}}_{t}^{*} - {\hat{x}}_{t - 1}}{Δ t} \end{matrix}

(10)

The current velocity ${\hat{v}}_{t}$ is estimated by an AR model

\begin{matrix} {\hat{v}}_{t} = b_{0} {\hat{v}}_{t}^{*} + b_{1} {\hat{v}}_{t - 1} \end{matrix}

(11)

where $b_{0}$ and $b_{1}$ are weighting parameters. Note that one-order AR model is reasonable since there is no dynamic pattern constraints and proprioceptive sensor information. The value of $b_{0}$ and $b_{1}$ are obtained through grid search method.

The number of times that the tag is detected by ST is modelled as binomial distribution, that is, the probability of n detections out of the number $N$ query rounds is given by

\begin{matrix} P (n | D, d, θ, ϕ) = (\begin{matrix} N \\ n \end{matrix}) p (D, d, θ, ϕ)^{n} \\ • (1 - p (D, d, θ, ϕ))^{N - n} \end{matrix}

(12)

where $D$ , $θ$ and $ϕ$ are as defined in equation (3). $p (D, d, θ, ϕ)$ is the detection probability of ST-to-tag.

With the state evolution model and measurement model, we are ready to implement particle filter scheme to localize ST. Suppose that at time instant $t - 1$ , a random measure of size $M$ , $χ_{t - 1} = {x_{t - 1}^{(m)}, w_{t - 1}^{(m)}}_{m = 1}^{M}$ is available, which is used to characterize the posterior distribution of $x_{t - 1}$ , where $x_{t - 1}^{(m)}$ are the particles of the measure and $w_{t - 1}^{(m)}$ are the corresponding weights indicating the goodness of the particle.

Upon receiving the current measurements ${y_{t, k}, k \in {1, \dots, N_{tag}}}$ at the time instant $t$ , the particles are propagated using

\begin{matrix} x_{t}^{(m)} ~ π (x_{t} | x_{t - 1}^{(m)}, y_{0 : t}) \end{matrix}

(13)

where $π (x_{t} | x_{t - 1}^{(m)}, y_{0 : t})$ is the proposal distribution used for generating new particles $x_{t}^{(m)}$ .

Current measurement is used to update dynamic input of state evolution model through WCL method. Therefore, the target state at time instant $t$ is predicted by propagating all particles at time $t - 1$ according to the importance function $p (x_{t} | x_{t - 1}^{(m)})$ based on state evolution model. The weights that are assigned to the particles are given by

w_{t}^{(m)} \propto p (y_{t} | x_{t}^{(m)}) w_{t - 1}^{(m)}

(14)

where

\begin{matrix} p (y_{t} | x_{t}^{(m)}) = Π_{i = 1}^{N_{tag}} (\begin{matrix} N \\ n_{t, i} \end{matrix}) p_{i} (x_{t}^{(m)})^{n_{t, i}} \\ • (1 - p_{i} (x_{t}^{(m)}))^{N - n_{t, i}} \end{matrix}

(15)

p_{i} (X_{t}^{(m)}) = \frac{1}{1 + e^{a_{0} + a_{1} D_{i} + a_{2} d_{i}^{(m)} + a_{3} | θ_{i} | + a_{4} | ϕ_{i} |}}

(16)

where $D_{i}$ , $θ_{i}$ and $ϕ_{i}$ are from the geometry relationship between reader and tag $T_{i}$ , and $d_{i}^{(m)}$ is the distance between particle $x_{t}^{(m)}$ and tag $T_{i}$ .

Then, the weight of particles are normalized by

\begin{matrix} w^{(m)} = \frac{w^{(m)}}{\sum_{i = 1}^{M} w^{(i)}} \end{matrix}

(17)

Once the weights are normalized, we form the random measure for the time instant $t$ , $χ_{t} = {x_{t}^{(m)}, w_{t}^{(m)}}_{m = 1}^{M}$ . This random measure is used to estimate $x_{t}$ by

\begin{matrix} {\hat{x}}_{t} = \sum_{m = 1}^{M} w_{t}^{(m)} x_{t}^{(m)} \end{matrix}

(18)

To avoid degeneration of the random measure, the resampling scheme is executed to eliminate particles with small weights and replicate particles with large weights.³⁷ After resampling, the current particles are replaced with the new one and the weights ${w_{t}^{(m)}, m = 1, . . ., M}$ are set to $1 / M$ .

Then, we utilize the current target location estimation to update the current velocity estimation

\begin{matrix} {\hat{v}}_{t} = \frac{{\hat{x}}_{t} - {\hat{x}}_{t - 1}}{Δ t} \end{matrix}

(19)

An additional step of the algorithm is to characterize the estimation bias from the synchronous detection assumption. When the speed estimation ${\hat{v}}_{t}$ exceeds certain predefined threshold, the following steps are executed. We obtain the time instant of each successive detections from the measurement ${y_{t, k}, k \in {1, . . ., N_{tag}}}$ , which spreads over the range of $(t - 1, t)$ . We assume the location estimation ${\hat{x}}_{t}$ is at the time instant $\hat{t}$ given by

\begin{matrix} \hat{t} = \frac{\sum_{k}^{N_{tag}} \sum_{i}^{n_{t, k}} τ_{i, k}}{\sum_{k}^{N_{tag}} n_{t, k}} \end{matrix}

(20)

thereby, the final estimate of target at the time instant $t$ is given by

\begin{matrix} {\tilde{x}}_{t} = {\hat{x}}_{t} + (b_{0} {\hat{v}}_{t} + b_{1} {\hat{v}}_{t - 1}) (t - \hat{t}) \end{matrix}

(21)

The PF-AA algorithm takes the above steps in a recursive fashion. A pseudo-code description of this algorithm is given by Algorithm 1.

Algorithm 1: PF-AA algorithm
whilet = 1, 2, 3, … do if t == 1 then /Initialization / $x_{1}^{(m)} ~ N ({\hat{x}}_{1}^{}, q_{1})$ , $w^{(m)} = 1 / M$ and $v_{1} = 0$ , where $x_{1}^{}$ is calculated according to (9), $q_{1}$ is predefined Gaussian noise vector. /Weight Update / Update $w^{(m)}$ according to (14) and normalize according to (17) /Estimation / Estimate ${\hat{x}}_{1}$ according to (18) else /Velocity update / ${\hat{v}}_{t}$ is updated according to (11). /Propagation / Generate particles $x_{t}^{(m)} ~ p (x_{t} \| x_{t - 1}^{(m)})$ according to (8) /* Weight Update / Update $w^{(m)}$ according to (14) and normalize according to (17). / Estimation / Estimate ${\hat{x}}_{t}$ according to (18). / Velocity update / $v_{t}$ is updated according to (19). end / Resampling / Resample M particles from the current measure $χ_{t} = {x_{t}^{(m)}, w_{t}^{(m)}}_{m = 1}^{M}$ ; Assign $w^{(m)} = 1 / M$ to each weight of new particle set. / Output / if ${\hat{v}}_{t} < v_{threshold}$ then ${\hat{x}}_{t} = {\hat{x}}_{t}$ else / Bias compensation */ ${\tilde{x}}_{t}$ is estimated according to (21). end end

Algorithm 1: PF-AA algorithm

whilet = 1, 2, 3, … do
if t == 1 then
/*Initialization */

x_{1}^{(m)} ~ N ({\hat{x}}_{1}^{*}, q_{1})

w^{(m)} = 1 / M

and

v_{1} = 0

,
where

x_{1}^{*}

is calculated according to (9),

q_{1}

is predefined Gaussian noise vector.
/*Weight Update */
Update

w^{(m)}

according to (14) and normalize according to (17)
/*Estimation */
Estimate

{\hat{x}}_{1}

according to (18)
else
/*Velocity update */

{\hat{v}}_{t}

is updated according to (11).
/*Propagation */
Generate particles

x_{t}^{(m)} ~ p (x_{t} | x_{t - 1}^{(m)})

according to (8)
/* Weight Update */
Update

w^{(m)}

according to (14) and normalize according to (17).
/* Estimation */
Estimate

{\hat{x}}_{t}

according to (18).
/* Velocity update */

v_{t}

is updated according to (19).
end
/* Resampling */
Resample M particles from the current measure

χ_{t} = {x_{t}^{(m)}, w_{t}^{(m)}}_{m = 1}^{M}

;
Assign

w^{(m)} = 1 / M

to each weight of new particle set.
/* Output */
if

{\hat{v}}_{t} < v_{threshold}

then

{\hat{x}}_{t} = {\hat{x}}_{t}

else
/* Bias compensation */

{\tilde{x}}_{t}

is estimated according to (21).
end
end

Performance evaluation

In this section, the simulation is used to evaluate the effectiveness of the proposed algorithm. The simulation setup follows the deployment scenario of AURIS in PASS as shown in Figure 10. The area was 4 m × 3.2 m, and covered by 9 × 5 UHF RFID landmark tags. RFID reader’s panel antenna is placed at the centre of the area with 2 m height facing the ground. The PASS simulation framework is configured as given in section ‘Detection probability model’. As for simulation parameters, the state evolution noise vector is given as $q_{t} = [N (0, 0.3), N (0, 0.3)]$ . The parameters of probability detection model were the ones obtained in section ‘Detection probability model’. In all the simulation, the PF algorithms used 200 particles. The number of query round $Q_{T}$ was set as 10. The localization performance was measured by average root mean square error (RMSE). The RMSE for one realization is calculated as $\sqrt{{({\tilde{x}}_{1, t} - x_{1, t})}^{2} + {({\tilde{x}}_{2, t} - x_{2, t})}^{2}}$ .

Figure 10.

Experiment setup with landmark tag’s deployment and ST trajectories.

In the first set of experiments, our goal was to obtain the speed threshold used for bias compensation of false synchronous detection assumption. We compared the localization performance of two implementations of PF-AA algorithms over moving speed at the range of $[0.1, 3] m / s$ . One implementation was the original PF-AA without bias compensation at any $v_{t}$ by setting $v_{threshold}$ as 100. The other was the original PF-AA with bias compensation at any $v_{t}$ by setting $v_{threshold}$ as 0. We generated 100 independent realizations for the two implementations following the ST trajectory 1 as shown in Figure 10. The query period was set as $T_{s} = 0.3 s$ . The results are shown in Figure 11. We can see that these two implementations perform differently for ST with different speed. To be specific, PF-AA without bias compensation performs better than that with bias compensation when the speed of ST is lower than 1.2 m/s. Therefore, it is reasonable to set $v_{threshold}$ as 1.2 m/s.

Figure 11.

Performance of PF-AA bias compensation technique.

In the second set of experiments, we compared the localization performance of different PF algorithms: (a) PF-BIN algorithm in Savic et al.¹⁸ and (b) PF-AA algorithm. For PF-BIN algorithm, it requires prior knowledge of initial state and movement speed. The process covariance matrix of its state evolution model was given by $diag (0.2 V, 0.2 V)$ , where $V$ is the movement speed. Note the measurement model of PF-BIN is updated to RTS model, otherwise, the performance of PF-BIN degenerates due to model inaccuracy. First, ST trajectory was set as ST trajectory 2 in Figure 10. The speed was 0.5 m/s. We generated 100 independent realizations of the ST trajectory 2. The results are shown in Figure 12, where the data are obtained by averaging the RMSEs over time. The overall RMSE of PF-BIN is 0.1681 m, while that of PF-AA is 0.1717 m. In this situation, PF-BIN performs slightly better than PF-AA. Second, ST speed is modified to be 2.5 m/s. Here, we assume that the process covariance matrix of its state evolution model is $diag (0.01, 0.01)$ as the previous setup, since PF-BIN could not tune the parameter in realtime. We implemented 500 independent realizations of ST trajectory 2. According to Figure 13, the PF-AA consistently performs better than PF-BIN. During some initial period, the performance of PF-AA is not desirable due to the setup time for bias compensation. In Figure 14, we plot the cumulative distribution functions (CDF) of the errors for PF-AA and PF-BIN. PF-AA performs better than PF-BIN.

Figure 12.

Performance of PF-AA and PF-BIN with ST speed 0.5 m/s.

Figure 13.

Performance of PF-AA and PF-BIN with ST speed 2.5 m/s.

Figure 14.

CDFs of position erros of PF-AA and PF-BIN.

Finally, we simulated a scenario with random walk trajectory of ST to compare WCL and PF-AA. The random walk trajectory is implemented as that ST moves straight with a constant speed, whenever it arrives at the area boundary, it bounces back at random angle with random speed. The speed of ST is uniformly distributed over the range of $[0.1, 3] m / s$ . As seen in Figure 15, as expected, PF-AA performs better than WCL. As the time goes by 1500 s, the cumulated RMSE is reduced by around $36.6 %$ .

Figure 15.

Performance of PF-AA and WCL with random walk trajectory.

Conclusion

In this article, we have proposed a new and realistic probability detection model of ST-to-tag, which is better suited to ST-to-tag communication link. The probability detection model of ST-to-tag is modelled as a function of the distance and relative angle between tag and RFID reader antenna in addition to the distance between tag to ST. The modelling accuracy of RTS model is improved compared to TS model in terms of cross-entropy cost function. We further proposed a particle filter-based location inference algorithm for AURIS. To this end, we identify two technical roadblocks of AURIS and existing localization algorithm as false synchronous detection assumption and state evolution model constraints. Our method to overcome such roadblocks includes two simple ideas. First, we estimate the velocity of ST based on the estimation state history and current measurement using AR model. The current measurement is introduced into the AR model by WCL method. Second, we implemented a minor modification to ST locator protocol, which is still Gen2 protocol compliant. Through such modification, the host server is able to obtain the asynchronous detection information. With these two ideas, we designed PF-AA algorithm for better accuracy and applicability in indoor localization application. Compared to PF-BIN algorithm, the localization capability of PF-AA is enhanced to handle the sharp manoeuvre and speed change of target.

There are several interesting topics that deserve to be explored in future: simultaneous mapping of unknown passive tags, localization with uncertain landmark location and exploring the situation where the number of working landmark tags will decrease in time due to their potential failures.

Footnotes

Handling Editor: Jianga Shang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Zou

. Impulse radio UWB for the internet-of-things: a study on UHF/UWB hybrid solution. PhD Thesis, Royal Institute of Technology (KTH), Stockholm, 2011.

Bolic

Simplot-Ryl

Stojmenovic

et al . RFID systems: research trends and challenges. Chichester: John Wiley & Sons, 2010.

Nick

Smietanka

Gotze

et al . RSS-based channel measurements and their influence on localization in RFID applications. In: IEEE international symposium on consumer electronics, Hsinchu, Taiwan, 3–6 July 2013, pp.71–72. New York: IEEE.

Azzouzi

Cremer

Dettmar

et al . Improved AoA based localization of UHF RFID tags using spatial diversity. In: IEEE international conference on RFID-technologies and Applications, Sitges, Spain, 15–16 September, pp.174–180. New York: IEEE.

Kronberger

Knie

Leonardi

et al . UHF RFID localization system based on a phased array antenna. In: IEEE international symposium on antennas and propagation, Spokane, WA, 3–8 July 2011, pp.525–528. New York: IEEE.

Xiong

Liu

Yang

et al . Design and implementation of a passive UHF RFID-based real time location system. In: IEEE international symposium on VLSI design automation and test, Hsin Chu, Taiwan, 26–29 April 2010. New York: IEEE.

Wang

Malekian

et al . TrackT: Accurate tracking of RFID tags with mm-level accuracy using first-order Taylor series approximation. Ad Hoc Netw 2016; 53: 132–144.

Wang

Malekian

et al . TMicroscope: behavior perception based on the slightest RFID tag motion. Elektron Elektrotech 2016; 22(2): 114–122.

Athalye

Savic

Bolic

et al . Novel semi-passive RFID system for indoor localization. IEEE Sens J 2013; 13(2): 528–537.

10.

Liu

Darabi

Banerjee

et al . Survey of wireless indoor positioning techniques and systems. IEEE T Syst Man Cyb 2007; 37(6): 1067–1080.

11.

DiGiampaolo

. A passive-RFID based indoor navigation system for visually impaired people. In: IEEE international symposium on applied sciences in biomedical and communication technologies, Roma, 7–10 November 2010. New York: IEEE.

12.

Yang

. Efficient particle filter localization algorithm in dense passive RFID tag environment. IEEE T Ind Electron 2014; 61(10): 5641–5651.

13.

DiGiampaolo

Martinelli

. A passive UHF-RFID system for the localization of an indoor autonomous vehicle. IEEE T Ind Electron 2012; 59(10): 3961–3970.

14.

Yang

Moniri

et al . Efficient object localization using sparsely distributed passive RFID tags. IEEE T Ind Electron 2013; 60(12): 5914–5924.

15.

Geng

Bugallo

Athalye

et al . Indoor tracking with RFID systems. IEEE J Sel Top Signa 2014; 8(1): 96–105.

16.

Geng

Bugallo

Athalye

et al . Real time indoor tracking of tagged objects with a network of RFID readers. In: IEEE European signal processing conference, Bucharest, 27–31 August 2012, pp.205–209. New York: IEEE.

17.

Athalye

Savic

Bolic

et al . A radio frequency identification system for accurate indoor localization. In: IEEE international conference on acoustics, speech and signal processing. Prague, 22–27 May 2011, pp.1777–1780. New York: IEEE.

18.

Savic

Athalye

Bolic

et al . Particle filtering for indoor RFID tag tracking. In: IEEE statistical signal processing workshop, Nice, 28–30 June, pp.193–196. New York: IEEE.

19.

Wang

Bolic

. Exploiting dual-antenna diversity for phase cancellation in augmented RFID system. In: IEEE international conference on smart communications in network technologies, Vilanova i la Geltru, 18–20 June 2014. New York: IEEE.

20.

Wang

Bolic

. Reducing the phase cancellation effect in augmented RFID system. Int J Parallel Emerg Distrib Syst 2015; 30(6): 494–514.

21.

Bolic

Rostamian

Djuric

. Proximity detection with RFID: a step toward the internet of things. IEEE Pervas Comput 2015; 14(2): 70–76.

22.

Geng

Bugallo

Djuric

et al . Tracking with asynchronous binary readings and layout information in RFID systems with sense-a-tags. In: European signal processing conference, Marrakech, Morocco, 9–13 September, 2013. New York: IEEE.

23.

DiGiampaolo

Martinelli

. Mobile robot localization using the phase of passive UHF RFID signals. IEEE T Ind Electron 2014; 61(1): 365–376.

24.

Griffin

. High-frequency modulated-backscatter communication using multiple antennas. PhD Thesis, Georgia Institute of Technology, Atlanta, GA, 2009.

25.

Marrocco

DiGiampaolo

Aliberti

et al . Estimation of UHF RFID reading regions in real environments. IEEE Antenn Propag M 2009; 51(6): 44–57.

26.

Arnitz

Muehlmann

Witrisal

et al . Characterization and modeling of UHF RFID channels for ranging and localization. IEEE T Antenn Propag 2012; 60(5): 2491–2501.

27.

Nikitin

Ramamurthy

Martinez

et al . Passive tag-to-tag communication. In: IEEE international conference on RFID, Orlando, FL, 3–5 April 2012. pp.177–184. New York: IEEE.

28.

Marrocco

Caizzone

. Electromagnetic models for passive tag-to-tag communications. IEEE T Antenn Propag 2012; 60(11): 5381–5389.

29.

Dobkin

. The RF in RFID: passive UHF RFID in practice. Amsterdam: Elsevier, 2007.

30.

Shen

Athalye

Djuric

. Phase cancellation in backscatter-based tag-to-tag communication systems. IEEE Internet Things J 2016; 3: 959–970.

31.

Arnitz

Muehlmann

Gigl

et al . Wideband system-level simulator for passive UHF RFID. In: IEEE international conference on RFID, Orlando, FL, 27–28 April 2009. New York: IEEE.

32.

PASS simulation framework, https://github.com/wacoder/PASS (2014, accessed 30 November 2016)

33.

Yan

Zhao

et al . Leveraging read rates of passive RFID tags for real-time indoor location tracking. In: ACM international conference on information and knowledge management, Maui, HI, 29 October–2 November 2012, pp.375–384. New York: IEEE.

34.

Lee

. Learning to combine discriminative classifiers: confidence based. In: ACM international conference on knowledge discovery and data mining, Washington, DC, 25–28 July 2010, pp.743–752. New York: ACM.

35.

Bishop

. Pattern recognition and machine learning. New York: Springer-Verlag, 2006.

36.

Zodi

Hancke

et al . Enhanced centroid localization of wireless sensor nodes using linear and neighbor weighting mechanisms. In: International conference on ubiquitous information management and communication, Bali, Indonesia, 8–10 January 2015, pp.1–43. New York: ACM.

37.

Djuric

Kotecha

Zhang

et al . Particle filtering. IEEE Signal Proc Mag 2003; 20(5): 19–38.

38.

Geng

Bugallo

Athalye

et al . Real-time self-tracking in the Internet of Things. In: IEEE international conference on acoustics, speech and signal processing, South Brisbane, QLD, 19–24 April 2015, pp.5510–5514. New York: IEEE.