RILS: RFID indoor localization system using mobile readers

Abstract

The radio frequency identification technology was given greater interest as it is widely used for identification and localization in the cognitive radio sensor networks. While radio frequency identification–based indoor localization is attractive, the need for a large-scale and high-density deployment of readers and reference tags is costly. Using mobile readers mounted on guide rails, we design and implement an RFID indoor localization system, which requires neither reference tags nor received signal strength indicator functions, for stock-taking and searching in warehouse operations. In particular, we install two guide rails, which can allow a reader to move horizontally or vertically, on the ceiling of a warehouse or workshop. We then propose a continuous scanning algorithm to improve the accuracy for locating a single tagged object and a category-based scheduling algorithm to shorten the time for locating multiple tagged objects. Our primary experimental results show that RFID indoor localization system can achieve high time efficiency and localization accuracy in the indoor localization.

Keywords

Radio frequency identification indoor localization mobile reader scanning algorithm category-based scheduling algorithm

Introduction

Radio frequency identification (RFID) and cognitive radio sensor network (CRSN) are two important wireless technologies that have a wide variety of applications and provide unlimited future potentials. RFID assists identification and localization of the objects while CRSN gives information about the physical condition of the objects. Similar to sensor nodes in CRSNs, RFID tags have a typical read range of 3–10 m in free air. Compared with the traditional bar code system, the RFID system does not need line-of-sight so that tags can be attached on objects and deployed in harsh environments. An RFID system is divided into two parts, tags and the reader. The tags are classified into active tags and passive tags. Active tags have built-in power source. An internal battery inside provides power so that it can extend the read range of tags. Passive tags have no built-in power source. The power is extracted from the signal sent by the reader. It can be used to operate the microchip. Due to the absence of external power source, a passive tag has the following advantages: lower price, longer life time, and smaller size. These advantages make the passive tag used more widely than active ones in real-world applications.

Indoor localization has been known as an important application of RFID. Most existing RFID-based indoor localization systems use received signal strength indicator (RSSI) measurements to estimate the possible range of a tagged object. They place reference tags, which can be either custom or active tags, at known locations in a warehouse or a workshop. The reference tags serve as landmarks in the warehouse by providing information about signal strength. Comparing the signal strengths obtained from different tags, readers deployed in strategic locations can determine the rough trajectory of a moving object, or the presence of a stationary object within a certain range. Although existing systems can provide fine-grained localization, there are some practical problems with using RSSI measurements in RFID systems: (1) RSSI functions are not available on most RFID devices,^1,2 (2) the deployment of high-density reference tags and multiple readers is costly,² (3) the interference among reference tags may change signal strength and affect localization accuracy,^3,4 and (4) RSSI measurements are commonly used for locating active tags.^3,5–7

In this article, a cost-effective and high-accuracy RFID indoor localization system (RILS) is designed and implemented to improve efficiency and reduce costs in some major warehouse operations, such as stock-taking and searching, which are time-consuming and often lead to mistakes. In particular, two guide rails, x-axis and y-axis guide rails, are deployed on the ceiling of a warehouse or workshop. A reader can be moved along either the x-axis or y-axis by two rails. A continuous scanning algorithm is then proposed to improve the accuracy for locating a single tagged object. Locations of the reader are recorded by such an algorithm when the first and the last times the tagged object is successfully detected. The tagged object is located at one of the intersection points of two circles. Both circles are centered at the recorded locations with a radius equal to the read range. A category-based scheduling algorithm is also proposed to reduce the time for locating multiple tagged objects placed in different storage areas. When localization requests arrive or are processed, the number of storage areas to be scanned may change with time. Thus, the problem of finding an optimal scan path for the reader is a time-dependent optimization problem, which can be modeled by the dynamic traveling salesman problem (DTSP). The proposed algorithm decomposes DTSP into a series of static traveling salesman problems (TSPs) and runs the 2-approximation algorithm to solve the static TSP at regular time intervals. Overall, RILS has the following properties:

Reliability. It works in the steady state which is suitable for making reliable measurements.

Scalability. It uses only one standard passive RFID reader and requires neither reference tags nor phase/RSSI functions.

A prototype system is developed to evaluate the performance of the proposed algorithms. Our preliminary experimental results demonstrate that the localization error can be decreased by 30% and the time can be saved by 10% with continuous scanning under given conditions. By contrast, the category-based scheduling can shorten 42% movement time of the reader.

The contributions of this work are summarized as follows:

A continuous scanning algorithm is then proposed to identify the exact location of a tagged object.

A category-based scheduling algorithm is proposed to determine the scanning order of multiple tagged objects.

A prototype is implemented to evaluate the performance of proposed algorithm.

The rest of the article is organized as follows. Section “Related work” gives an overview of the related work. Section “System design and implementation” illustrates system design and implementation and analyzes the system cost. Section “Localization algorithm” proposes a continuous scanning algorithm to locate tagged objects. Section “Scheduling algorithm” offers a category-based scheduling algorithm to manage the reader movement. Section “Performance evaluation” designs experiments to evaluate the performance of the proposed algorithms. Section “Conclusion” concludes this article.

Related work

A considerable amount of experiments have been conducted about indoor localization systems. Tagged objects are located or tracked by a majority of extant systems or schemes via RSSI measurements. SpotON^5,6 is one of the earliest systems for RF-based three-dimensional (3D) location sensing. Multiple base stations estimate the approximate distance to the tagged object through signal strength measurements. The system requires a number of custom tags and base stations. The cost of a development board for tag or base station is around US$120. A central server then aggregates the distance values to triangulate the position of the tagged object. Instead of using custom tags and base stations, LANDMARC³ deploys active tags at known locations as reference tags. These reference tags provide information about the signal strength. With this information, the system adopts a k-nearest neighbor algorithm to estimate the location of the tagged object. Wang et al.⁷ proposed two RFID-based 3D positioning schemes, namely, active scheme and passive scheme. Both schemes are based on the Nelder–Mead nonlinear optimization method that minimizes the error objective functions. The active scheme locates an object equipped with a reader. The passive scheme locates an object with a tag attached. Zhang et al.⁴ presented a model of signal dynamics to allow tracking of transceiver-free objects. Based on the RSSI information, they proposed three tracking algorithms to eliminate noise behaviors and improve accuracy. Midpoint and intersection algorithms track a single object without calibration. The best-cover algorithm tracks multiple objects with calibration required. L-VIRT⁸ use both static and mobile readers to define topological constraints that delimit volumes of presence for the tags. Ting et al.² studied the feasibility of using the RSSI measurement for locating and tracking passive tags. They run an experiment on a $300 cm \times 300 cm$ area, which is divided equally into nine cells, and measure the average RSSI of each cell to four readers installed at each corner of the area. The experimental results show that only the object of height 100 cm can be reliably detected by the reader. Most of the above-mentioned systems require a set of readers and a large number of active tags. The cost of readers is around US$1500 each. The cost of an active tag ranges from US$15 to US$50 while that of a passive one is only about US$0.25. To make the system more affordable, it is essential to reduce system cost and complexity.

Some other existing systems increase practicability and performance in site-specific applications. The R-LIM system⁹ is an affordable system for locating books in the library. Unlike pervious systems, it places reference tags, called shelf-tags, rather than readers on each shelf, and associates book-tags with shelf-tags through periodic scanning. Zhu et al.¹⁰ proposed an activated tag included (ATI) method for the fault-tolerant RFID reader localization. Such a method is suitable for the situation that some tags fail to communicate with the reader due to shielding effects. Shangguan et al.¹¹ established a probabilistic model for recognizing the transient critical region and proposed the OTrack protocol to continuously monitor the order of tagged goods on the airport baggage conveyor belt. The Tagoram system¹² leverages the phase value of the backscattered signal, provided by the commodity-off-the-shelf (COTS) RFID reader, to realize real-time tracking of mobile RFID tags. Zhao et al.¹³ revealed the unique hardness in localization on 3D surface. A general 3D surface is not always localizable, given surface distance constraints only. Yang et al.¹⁴ proposed a distributed algorithm to locate wireless sensors deployed on 3D surface. Such an algorithm constructs a well-aligned mapping between the triangular mesh of the digital terrain model (DTM) of the terrain surface and the triangular mesh extracted from the connectivity graph of the network deployed on the terrain surface. Maneesilp et al.¹⁵ proposed two schemes, passive and active, to locate tags and readers in a hexahedron. Bu et al.¹⁶ studied RFID 3D localization from perspective of time efficiency and energy efficiency. The localization accuracy can be improved if the reader probes sufficient number of reference tags. Some applications for the vehicular networks are described in Quan et al.¹⁷ and Cheng et al.¹⁸ The security issues are discussed in Chen et al.^19,20

System design and implementation

In this section, the structure of the system is introduced. Then, a prototype system is presented and its cost is analyzed.

Design and architecture

A system called RILS was designed to locate stationary objects attached with passive tags with high accuracy. The system is built by the following four steps: (1) first, two kinds of guide rails, x-axis and y-axis guide rails, are customized in accordance with the size of the warehouse ceiling; (2) then two y-axis guide rails are installed on both vertical verges of the warehouse ceiling; (3) after that, the x-axis guide rail is installed between those two y-axis guide rails; and (4) finally, a reader is attached on the x-axis guide rail. Two electric motors, which are separately installed on x-axis and y-axis guide rails, called x-axis and y-axis electric motors, provide power to move the reader from one location to another. Two electric motors, called the x-axis motor and the y-axis motor, are separately installed on the x-axis and y-axis guide rails. The reader is moved from one position to the other freely by those two motors.

Figure 1 depicts how the reader moves to a certain location by the example. As shown in Figure 1, the reader attempts to move from location $(a, b)$ to location $(a', b')$ , where $a < a'$ and $b > b'$ . The following two steps are required to move the reader: (1) the power is provided by the x-axis electric motor to allow the reader move along the positive x-axis. The location of the reader changes from $(a, b)$ to $(a', b)$ ; (2) the x-axis guide rail is impelled to move along the negative y-axis by the y-axis electric motor. The reader moves from location $(a', b)$ to location $(a', b')$ . Through those two steps, the reader can reach any location of the warehouse ceiling.

Figure 1.

An example of the reader movement.

Implementation and costs

The system implementation consists of the following phases: guide rail installation and electric motor control. The guide rail installation takes the following steps: (1) two circular linear guide rails are chosen asy-axis guide rails, because each of them includes a support structure that can be easily attached to the ceiling; (2) four synchronous wheels are mounted at both ends of each y-axis guide rail and connect them via plain shaft or synchronous belts. The plain shaft is connected to an electric motor, providing power to all of these synchronous wheels. When the synchronous wheels turn, these synchronous belts will move the x-axis guide rail along the y-axis guide rail; (3) a miniature linear guide rail is set as the x-axis guide rail, because it is small in size and light in weight; and (4) two synchronous wheels are installed at both ends of the x-axis guide rail and connect them via a synchronous belt. One synchronous wheel is directly connected to an electric motor, which forces the other to turn, moving the reader attached to the synchronous belt.

A $300 cm \times 400 cm$ prototype system is implemented and fixed on a supporting structure made of light aluminum profiles. Figure 2 depicts a general picture of the prototype system. One 57STH stepper motor is installed on the supporting structure while the other one is attached to a sliding block on the y-axis guide rail. The antenna of the PR9000 reader moves synchronously with the synchronous belt by being attached to a sliding block.

Figure 2.

The prototype system.

The following parts are required for the electric motor control: electric motor, gear reducer, and micro-controller. The speed of the electric motor is relatively high, which is not suitable for starting, stopping, and slower movement. The gear reducer decelerates the higher speed motor, increasing torque in the process. Pulse signals are generated by the micro-controller to start and stop the motor, select forward or reverse rotation, and select and regulate the speed. Figure 3 demonstrates the fundamental components of the motor control. According to comments given by the personal computer, the MCS-51 single-chip microcomputer generates pulse signals which are taken by the stepper motor drivers to convert them to motor motion.

Figure 3.

Motor control components.

Table 1 shows the cost of main parts of the prototype system. The reader accounts for 70% of the cost of the system. RILS needs only one reader that makes it more affordable.

Table 1.

Parts and fees.

Part	Model	Unit	QTY	Total
Aluminum profile	3030	US$7/m	26 m	US$182
Circular linear guide rail	SBR12	US$10/m	10 m	US$100
Miniature linear guide rail	MGN12 C	US$30/m	4 m	US$120
Plain shaft	WCAS8	US$5/m	4 m	US$20
Synchronous belt	MXL	US$6/m	30 m	US$180
Synchronous wheel	MXL	US$7	4	US$28
Stepper motor	XY57STH76	US$35	2	US$70
Reader	PR9000	US$1500	1	US$1500

Localization algorithm

In this section, two localization algorithms, skip scanning and continuous scanning, are presented to locate a single tagged object. Also, a theoretical analysis is conducted to compare the performance of those two algorithms.

Continuous scanning

Traditionally, readers are deployed in strategic locations in a warehouse. When a reader detects a tagged object, the rough location of the tagged object is within a circle centered at the reader and with a maximum radius equal to the read range.

It is well known that placing disks at the centers of regular hexagons, which are also called cells, is optimal, in terms of the number of disks needed to achieve full coverage of a plane. The skip scanning algorithm realizes the seamless coverage by sampling signals from the reader on hexagonal lattices. This algorithm terminates when the reader locates the tagged object or completes scanning the whole warehouse. The estimated location of the tagged object is the last location of the reader. The skip scanning is a coarse-grained localization. Although simple and effective, the skip scanning, both search time and localization accuracy, largely depends on the read range of the reader. If the reader decreases the read range to achieve higher localization accuracy, it will take a long time to move back and forth or up and down to search the tagged object.

Roughly, a reader can read a single tag 20 times per second,²¹ which enables it to continuously scan the tagged object.^22,23 A continuous scanning algorithm is proposed to improve the localization accuracy and shorten the localization time. Compared with the skip scanning, the continuous scanning is a fine-grained localization. Suppose that the width and length of the warehouse are $W$ and $L$ , respectively. The read range of the reader is $r$ (assume that the read region of the reader is a circle with a radius $r$ ). The length of x-axis guide rail and the length of y-axis guide rail is set to $2 r + W$ and $⌈ \frac{L - r}{2 r} ⌉ 2 r$ , respectively. Figure 4 gives an example to show how the algorithm locates a tagged object.

Figure 4.

An example of the continuous scanning.

The reader moves from $(- r, r)$ to $(r + W, r)$ along the x-axis. When it arrives at $(r + W, r)$ , it moves $2 r$ along the y-axis and then goes to the negative x-axis. It continually scans the tagged object while moving along guide rails and records its location when it successfully detects the tagged object. Suppose that the reader locates at $(a, b)$ and $(a', b)$ when the first and last times it successfully detects the tagged tag. Here, $- 2 r \leq a' - a \leq 2 r$ and $b = (2 n + 1) r$ for $n = 0, 1, 2, . . ., ⌊ \frac{L}{2 r} ⌋$ . The tagged object must locate at one point of intersection of two circles with same radius $r$ , centered at $(a, b)$ and at $(a', b)$ , respectively. The points of intersection are calculated by solving the following equations

(x - a)^{2} + (y - b)^{2} = r^{2}

(1)

(x - a')^{2} + (y - b)^{2} = r^{2}

(2)

Then, the following equations are solved

x_{1} = x_{2} = \frac{a + a'}{2}

(3)

y_{1} = b + \sqrt{r^{2} - \frac{{(a' - a)}^{2}}{4}}

(4)

y_{2} = b - \sqrt{r^{2} - \frac{{(a' - a)}^{2}}{4}}

(5)

The coordinate of the tagged object may be $(x_{1}, y_{1})$ or $(x_{2}, y_{2})$ because of a flip ambiguity problem which leads to large errors in the location estimates. To solve this ambiguity problem, the reader moves $(y_{1} - y_{2}) / 2$ along the y-axis. If the tagged object can be detected still, the coordinate of the tagged object is $(x 1, y 1)$ . Otherwise, coordinate is $(x 2, y 2)$ .

Following three factors may adversely affect time cost and accuracy of the localization algorithm: (1) the overlapped scanning regions, (2) the high-speed sampling rate and appropriate moving speed, and (3) the suitable read range.

Time–cost analysis

A comparison is made for the time cost of two proposed algorithms. Assume that the reader moves with speed $s_{x}$ along x-axis and $s_{y}$ along y-axis, respectively. The time cost of the continuous scanning, $T$ , can be calculated as follows

T = \frac{(2 r + W) ⌈ \frac{L - r}{2 r} ⌉}{s_{x}} + \frac{⌈ \frac{L - r}{2 r} ⌉ 2 r}{s_{y}}

(6)

Then, a given tagged object is located by the continuous scanning and the time cost is recorded. Assume that the coordinate of the tagged object is $(x, y)$ , the time cost, $t_{y}$ , is calculated during the period of the y-axis movement, as $| y - r | / s_{y}$ . During moving along the x-axis, the reader scans an area of a rectangle with length $2 r + W$ and width $2 r$ . When the reader successfully reads the tagged object, the last location $(a', b')$ is calculated by taking two cases into consideration. Case one: if $⌊ \frac{y}{2 r} ⌋$ is even, the reader moves to the positivex-axis. We have $a' = x + \sqrt{r^{2} - {(y - (2 ⌊ \frac{y}{2 r} ⌋ + 1) r)}^{2}}$ and $b' = (2 ⌊ \frac{y}{2 r} ⌋ + 1) r$ . Case two: if $⌊ \frac{y}{2 r} ⌋$ is odd, the reader moves to the negative x-axis. We get equations $a' = x - \sqrt{r^{2} - {(y - (2 ⌊ \frac{y}{2 r} ⌋ + 1) r)}^{2}}$ and $b' = (2 ⌊ \frac{y}{2 r} ⌋ + 1) r$ . Then, we get the time cost of the x-axis movement, $t_{x}$ , as

t_{x} = {\begin{array}{l} \frac{(2 r + W) \frac{y}{2 r} + x + \sqrt{r^{2} - {(y - (2 \frac{y}{2 r} + 1) r)}^{2}}}{v_{x}} & if \frac{y}{2 r} is even \\ \frac{(2 r + W) (\frac{y}{2 r} + 1) - x + \sqrt{r^{2} - {(y - (2 \frac{y}{2 r} + 1) r)}^{2}}}{v_{x}} & if \frac{y}{2 r} is odd \end{array}

In summary, the continuous scanning takes $t_{x} + t_{y}$ to locate the tagged object.

Accuracy analysis

Another comparison is made for the accuracy of two proposed algorithms. Assume that the coordinate value of the reader is $(a, b)$ , and the tagged object is actually located at $(x, y)$ , where $x \geq a$ , $y \geq b$ , and $\sqrt{{(x - a)}^{2} + {(y - b)}^{2}} \leq r$ . We can write equations: $x = a + λ r \cos θ$ , $y = b + λ r \sin θ$ , where $0 \leq λ \leq 1$ and $0 \leq θ \leq (π / 2)$ .

For the continuous scanning, the tagged object is approximately located at $(x_{1}, y_{1})$ (the flip ambiguity is removed), where $x_{1}$ and $y_{1}$ can be solved by equations (3) and 4. Let $(a' - a) / 2 = r \cos ϕ$ where $0 \leq ϕ \leq (π / 2)$ (the reader moves toward the x-axis), we have $x_{1} = a + r \cos ϕ$ and $y_{1} = b + r \sin ϕ$ . After that, the localization error margin, $δ_{c}$ , is calculated by the following equations

\begin{matrix} δ_{c} & = \sqrt{{(x - x_{1})}^{2} + {(y - y_{1})}^{2}} \\ = \sqrt{{(x - \frac{a + a'}{2})}^{2} + {(y - b - \sqrt{r^{2} - \frac{{(a' - a)}^{2}}{4}})}^{2}} \\ = \sqrt{{(λ r \cos θ - r \cos ϕ)}^{2} + {(λ r \sin θ - r \sin ϕ)}^{2}} \\ = \sqrt{(1 + λ^{2}) r^{2} - 2 λ r^{2} (\cos θ \cos ϕ + \sin θ \sin ϕ)} \\ = \sqrt{r^{2} + λ^{2} r^{2} - 2 λ r^{2} \cos (θ - ϕ)} \end{matrix}

(7)

For the skip scanning, the tagged object is approximately located at $(a, b)$ . The localization error of the skip scanning, $δ_{s}$ , is $λ r$ . Take the case for $δ_{c} \leq δ_{s}$ into account, we have

\begin{matrix} δ_{c} \leq δ_{s} & \Rightarrow r^{2} + λ^{2} r^{2} - 2 λ r^{2} \cos (θ - ϕ) \leq λ^{2} r^{2} \\ \Rightarrow - \arccos \frac{1}{2 λ} \leq θ - ϕ \leq \arccos \frac{1}{2 λ} \end{matrix}

(8)

Inequalities (8) show that the localization accuracy of continuous scanning is better than the skip scanning when $θ - ϕ$ ranges from $- \arccos (1 / 2 λ)$ to $\arccos (1 / 2 λ)$ . The localization error margin of the continuous scanning is mainly caused by the error of $r$ , which can be defined as $(1 - λ) r$ . According to inequalities (8), when $λ$ increases, the range of $θ - ϕ$ increases synchronously. When $λ$ approaches 1, $θ - ϕ$ ranges from $- (π / 3)$ to $π / 3$ , which is $2 / 3$ of its full range.

Scheduling algorithm

In this section, a scheduling algorithm, called category-based scheduling, is proposed to manage the reader movement and locate multiple tagged objects.

Problem formulation

To monitor some valuable items, we need to obtain their location frequently even though they are static. A localization request will be generated to check whether a certain item is in the right place at the right time. To handle multiple requests, we should determine a scan path, which is the motion of the reader. The first come first served (FCFS) scheduling algorithm is a straightforward solution whereby requests are attended to in the order that they arrived. When processing a localization request, the algorithm extracts object’s category ID from object’s tag ID and then moves the reader to the corresponding area. The algorithm is intrinsically fair, but it generally does not provide the fastest service.

The problem of finding the optimal scan path for the reader can be modeled by the DTSP. As items from different categories are placed in different storage areas, we view each storage area to be scanned as a vertex in a complete graph (the reader can move to any storage area), and then find the minimum-weight Hamiltonian cycle in the graph. Note that the “vertices” have some dynamic properties as their number may change with time: (1) their number will increase when new requests arrive; (2) their number will decrease when old requests are processed. Suppose that vertex $i$ , $v_{i}$ , has predetermined entry and exit where the reader enters and leaves $v_{i}$ . The weight between $v_{i}$ and $v_{j}$ , $d_{ij}$ , is defined as the time cost that the reader takes to move from v_i’s exit to v_j’s entry. For example, if v_i’s exit and v_j’s entry are $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ , respectively, then we have

d_{ij} = \frac{| x_{1} - x_{2} |}{s_{x}} + \frac{| y_{1} - y_{2} |}{s_{y}}

(9)

Assume that the number of storage areas is $n (t)$ at time $t$ , a weight matrix can be used to describe the “dynamic” features of vertices

D (t) = {d_{ij}}_{n (t) \times n (t)}

(10)

Given a complete and undirected graph $G (t) = (V (t), E (t))$ with $n (t)$ vertices and a weight matrix $D (t)$ , we try to find a minimum-weight path (Hamiltonian cycle) in $G (t)$ at time $t$ . The objective function is defined as follows

\min (\sum_{i = 1}^{n (t) - 1} d (σ_{i}, σ_{i + 1}) + d (σ_{n}, σ_{1}))

(11)

where $σ (t)$ is a permutation over the set ${1, 2, . . ., n (t)}$ .

Category-based scheduling

The category-based scheduling is a practical solution to DTSP, which is an NP hard problem. Such an algorithm samples $G (t)$ , which changes with time, at regular time intervals and finds the TSP tour for each sampled $G (t)$ . To be specific, the algorithm contains the following three sub-algorithms: receiving, updating, and selecting.

Receiving

This algorithm receives requests for the location of tags. It contains the following four steps: (1) it waits for receiving localization requests (each of them contains a tag ID), (2) it extracts the category ID from the tag ID, (3) it finds the vertex that is associated with the extracted category ID, and (4) it adds the request into the pending queue of the associated vertex. The pseudo-code of the algorithm is shown in Algorithm 1.

Algorithm 1. Receiving.
Input: a complete and undirected graph $G = (V, E)$ of $n$ vertices. while true do //Wait for receiving requests. $r \leftarrow$ receiveRequest (); //Extract the category ID from the tag ID included in $r$ . id $\leftarrow r$ .getCategoryId (); //Add the request to the pending queue in the vertex associated with the category ID. for each $v \in G$ do if $! v$ . isAssociated (id)then continue; v.addRequest $(r)$ ;

Algorithm 1. Receiving.

Input: a complete and undirected graph

G = (V, E)

n

vertices.
while true do
//Wait for receiving requests.

r \leftarrow

receiveRequest ();
//Extract the category ID from the tag ID included in

r

.
id

\leftarrow r

.getCategoryId ();
//Add the request to the pending queue in the vertex associated with the category ID.
for each

v \in G

do
if

! v

. isAssociated (id)then
continue;
v.addRequest

(r)

;

Updating

The optimal scan path is updated by the algorithm at each time interval, $Δ T$ . A detailed pseudo-code is given by Algorithm 2, which can be further divided into two parts: collecting and finding.

Algorithm 2. Updating.
input: the current time $t$ , the time interval $Δ T$ , and the graph $G = (V, E)$ . output: a valid TSP tour $C'$ . while true do //Run at $Δ T$ intervals. If $t % Δ T! = 0$ then continue; //-------PART ONE: COLLECTING------- $G (t) \leftarrow G$ .clone (); //Remove those vertices that do not need to be scanned within next $Δ T$ . for each $v \in G (t)$ do if $! v$ . isScanned $& & v$ . isRequested then continue; $G (t)$ .removeVertex $(v)$ ; // ——PART TWO: FINDING—— Let $T$ , $T'$ , $C$ and $C'$ be lists. //Find a minimum spanning tree $T$ of $G (t)$ . $T \leftarrow$ findMinimumSpanningTree $(G (t))$ ; //Replace each edge of $T$ with two directed edges. $T' \leftarrow T$ . clone(); for each $e_{ij} \in T$ do $T'$ .addEdge $(e_{ji})$ ; Let $G' (t) = (V (t), T')$ ; // $G' (t)$ is Eulerian. Find an Euler tour $C$ of $G' (t)$ . $C \leftarrow$ findEulerTour $(G' (t))$ ; //Shortcut $C$ to get a valid tour $C'$ . $C' \leftarrow$ removeDuplicatedVertices $(C)$ ; return $C'$

Algorithm 2. Updating.

input: the current time

t

, the time interval

Δ T

, and the graph

G = (V, E)

.
output: a valid TSP tour

C'

.
while true do
//Run at

Δ T

intervals.
If

t % Δ T! = 0

then
continue;
//-------PART ONE: COLLECTING-------

G (t) \leftarrow G

.clone ();
//Remove those vertices that do not need to be scanned within next

Δ T

.
for each

v \in G (t)

do
if

! v

. isScanned

& & v

. isRequested then
continue;

G (t)

.removeVertex

(v)

;
// ——PART TWO: FINDING——
Let

T

T'

C

and

C'

be lists.
//Find a minimum spanning tree

T

G (t)

T \leftarrow

findMinimumSpanningTree

(G (t))

;
//Replace each edge of

T

with two directed edges.

T' \leftarrow T

. clone();
for each

e_{ij} \in T

T'

.addEdge

(e_{ji})

;
Let

G' (t) = (V (t), T')

;
//

G' (t)

is Eulerian. Find an Euler tour

C

G' (t)

C \leftarrow

findEulerTour

(G' (t))

;
//Shortcut

C

to get a valid tour

C'

C' \leftarrow

removeDuplicatedVertices

(C)

;
return

C'

Part one collects all vertices that require to be scanned within next interval, $Δ T$ . Each $v$ has two boolean parameters, isScanned and isRequested. The default value of both of them is “false.” The parameter isScanned will be changed to “true” when $v$ is completely scanned. The parameter isRequested will be “true” if $v$ has one or more unresponsive requests. The parameter setting will be described in detail in the next section.

$G (t)$ is a subgraph of $G$ , that is, $G (t) \subseteq G$ , where the following conditions are satisfied by $v$ in $G (t)$ : (1) $v$ has at least one request that has not been processed; (2) $v$ has not been scanned by the reader.

Part two applies the 2-approximation algorithm²⁴ to find the optimal scan path for the reader. Note that though $C$ visits every vertex of $G' (t)$ , it can not be an effective TSP tour because vertices are visited more than once. We simplify C by taking steps as follows: assume $C = v_{1}, . . ., v_{2 n - 2}, v_{1}$ . If the following inequality $1 \leq i < j \leq 2 n - 2$ exists such that $v_{i} = v_{j}$ , then estimate $v_{j}$ from $C$ . The cost of the new tour has increased by $d (v_{j - 1}, v_{j + 1})$ and has decreased by $d (v_{j - 1}, v_{j}) + d (v_{j}, v_{j + 1})$ . We then have $d (v_{j - 1}, v_{j + 1}) \leq d (v_{j - 1}, v_{j}) + d (v_{j}, v_{j + 1})$ as $d$ is a metric. As a result, the shortcut process does not increase the total cost. This process is repeated until it obtains a tour $v_{1}, . . ., v_{n}, v_{1}$ with no same vertices.

Suppose $H$ is an optimal TSP tour (a Hamiltonian cycle in $G (t)$ with minimum total cost). Suppose $H'$ is got from $H$ by deleting any edge. If the edge weights are positive, we have $d (H') \leq d (H)$ . Now $H'$ is a Hamiltonian path, in this case it also is a spanning tree of $G (t)$ . We have $d (T) \leq d (H') \leq d (H)$ on condition that $T$ is a minimum-cost spanning tree. Also, if $C$ is viewed as a walk in $T$ , each edge of $T$ is traversed exactly twice, we have $d (C) = 2 d (T) \leq 2 d (H)$ as each edge of $T'$ is traversed exactly once. Finally, we can obtain $d (C') \leq d (C)$ . The following inequalities verify the approximation ratio of 2

d (C') \leq d (C) = 2 d (T) \leq 2 d (H)

(12)

This algorithm is very simple and efficient in practice and the overall time complexity is $O (n^{2})$ . To be specific, the minimum spanning tree is found by Prim’s algorithm with a time complexity of $O (n^{2})$ . Then, Hierholzer’s algorithm is employed to find an Euler tour. Based on a double linked list, the individual operations of the algorithm can be performed at each constant time, so the algorithm has a time complexity of $O (n^{2})$ . Finally, the hashing method is selected to estimate duplicated vertices. The method has a time complexity of $O (n)$ due to one-time scanning, and the length of $C$ is $O (n)$ .

Selecting

This algorithm selects the next vertex to be scanned when the reader completes scanning a vertex. Suppose that the reader arrives at v_pre’s exit, the next vertex, $v_{next}$ , is found through the algorithm shown in Algorithm 3.

Algorithm 3. Selecting.
input: a valid TSP tour $C'$ and a vertex $v_{pre}$ . output: the next vertex $v_{next}$ . $v_{next} \leftarrow v_{pre}$ ; Index $\leftarrow C'$ .indexOf $(v_{pre})$ ; // $v_{pre}$ is not the last vertex in $C'$ . if index $! = C'$ .size ()–1 then //Set isScanned of $v_{pre}$ to true $v_{pre}$ . isScanned ← true; $v_{next} \leftarrow C'$ .get (index+1); else //Reset isScanned of all $v$ in $G$ to false. for each $v \in G$ do $v$ . isScanned ← false; return $v_{next}$ ;

Algorithm 3. Selecting.

input: a valid TSP tour

C'

and a vertex

v_{pre}

.
output: the next vertex

v_{next}

v_{next} \leftarrow v_{pre}

;
Index

\leftarrow C'

.indexOf

(v_{pre})

;
//

v_{pre}

is not the last vertex in

C'

.
if index

! = C'

.size ()–1 then
//Set isScanned of

v_{pre}

to true

v_{pre}

. isScanned ← true;

v_{next} \leftarrow C'

.get (index+1);
else
//Reset isScanned of all

v

G

to false.
for each

v \in G

v

. isScanned ← false;
return

v_{next}

;

To avoid starvation, $isScanned$ of each newly scanned vertex will be set to “true.” Recall that Algorithm 2 will not involve those vertices whose $isScanned$ are “true” in $C'$ even if some new requests are received. When a vertex is not found in $C'$ , $isScanned$ of all vertices in $G$ will be reset to “false” by the algorithm. As a result, vertices that have unfulfilled requests will be included in $C'$ at the next time interval by Algorithm 2.

The basic idea of this algorithm is same as elevator algorithm. The reader starts at one end of the tour and moves toward the other. It is servicing requests as it reaches each vertex until reaches the other end of tour. At the other end, the tour is refreshed, and servicing continues.

Performance evaluation

In this section, the performance of RILS is evaluated in terms of localization error and time cost via experiments.

Localization error estimation

An experiment is designed to estimate the error of the read range $r$ . The following settings are chosen in the experiment. The maximum output power of the reader is 20 dBm. The response timeout has a default value 50 ms, which is the maximum time that the reader waits for a response from a tag. In total, 225 tags are deployed on a $150 cm \times 150 cm$ area of a wall. Any two adjacent tags have a distance of 10 cm. The antenna is set up in front of the wall. The distance between antenna and area center is changed from 50 to 100 cm, then the value of $r$ is measured. The value shows the distance from a tag to the area center where tag data can be interrogated effectively.

Figures 5 –7 describe the detection rates (number of detections to be scanned of per total number) for different tags in the vertical plane. For each tag, the detection rates are set from 200 scans. The results indicate that the read region is not an regular area with a clear boundary. Actually, the shape of the read region is affected by numerous factors, such as reader and tag antenna patterns, the valid radiated power, and the antenna position. The irregular read region may lead to localization errors for both skip and continuous scanning. It can also be seen that $r$ increases as the distance between the antenna and the wall increases. For instance, as the distance increases from 50 to 150 cm, $r$ increases from 40 to 60 cm. Note that localization errors may be caused by the irregular read region. To build a better model for the read region, we divide it into some small grids and depict grid graphs in a matrix form.^25,26 To simplify the computation, we assume that the read region is an ideal cycle in this article.

Figure 5.

The detection rate (50 cm).

Figure 6.

The detection rate (100 cm).

Figure 7.

The detection rate (150 cm).

Localization algorithm comparison

Next, the continuous scanning is compared with the skip scanning from aspects of localization time and accuracy. The antenna is installed 50 cm above the ground floor and $r$ is set to around 50 cm due to the limitation of the prototype system. Then, 10 tags are placed randomly in a $300 cm \times 400 cm$ area. The speed of the x-axis movement, $s_{x}$ , is 19.6 cm/s, while that of the y-axis movement, $s_{y}$ , is only 7.5 cm/s. The reason for $s_{x} > s_{y}$ is that the x-axis guide rail is much heavier than the antenna. The y-axis electric motor needs to run at lower speed to produce higher torque. Figure 8 depicts that the continuous scanning is more time effective than the skip scanning. We can see that the mean localization time for the continuous scanning is around 10% lower than that for the skip scanning.

Figure 8.

Localization time.

Figure 9 shows that the continuous scanning has the higher accuracy compared to skipping scanning. The average localization error for the continuous scanning is 8.9 cm, which is about 60% of that for the skip scanning.

Figure 9.

Localization accuracy.

Scheduling algorithm comparison

Then the category-based scheduling is compared with FCFS scheduling in terms of time cost. In total, 10 tags are set randomly in a $300 cm \times 400 cm$ area. Each tag represents a storage area. For simplicity, suppose the arrival time of localization requests obey a Poisson distribution which has a mean of 10 s. The category ID, which is included in each request, is randomly selected. Figure 10 shows the category ID corresponding to each request ID. The reader is located at $v_{1}$ initially. For Algorithm 2, the time interval, $Δ T$ , is 5 s. Other parameters remain the same as that mentioned in the above section. Figure 11 shows that the performance of category-based scheduling is better than the FCFS scheduling. The category-based scheduling has an average response time of only 63 s while FCFS scheduling has that of 107 s. In addition, the category-based scheduling has a less standard deviation of the response time, which is 42% lower than that for the FCFS scheduling.

Figure 10.

The category ID for each request.

Figure 11.

The comparison of time cost.

The TSP tour determined by Algorithm 2, $C'$ , is recorded at 5 and 10 s, respectively. Figures 12 and 13 show that $C'$ changes as new requests arrive or the reader finishes scanning a new vertex. For example, when requests related to $v_{4}$ and $v_{7}$ arrive, $C'$ changes from ${v_{1}, v_{2}, v_{6}, v_{8}, v_{3}, v_{10}, v_{5}, v_{9}}$ to ${v_{2}, v_{6}, v_{8}, v_{3}, v_{10}, v_{4}, v_{7}, v_{5}, v_{9}}$ .

Figure 12.

The TSP tour (5 s).

Figure 13.

The TSP tour (10 s).

Figure 14 depicts the sequence of vertices scanned by the reader. It can be seen that the sequence for the category-based scheduling is ${v_{1}, v_{2}, v_{6}, v_{7}, v_{5}, v_{9}, v_{8}, v_{3}, v_{10}, v_{4}, v_{2}, v_{1}}$ , while that for the FCFS scheduling is ${v_{1}, v_{2}, v_{6}, v_{3}, v_{1}, v_{9}, v_{5}, v_{8}, v_{10}, v_{7}, v_{4}, v_{2}}$ . The low efficiency of the FCFS scheduling is recorded by the oscillation from $v_{1}$ to $v_{6}$ and then back to $v_{1}$ . Compared with the FCFS scheduling, the category-based scheduling has a better time efficiency, which saves 43% time to complete the whole scanning process.

Figure 14.

The sequence of vertices scanned.

Conclusion

In this article, RILS is designed and implemented for warehouse searching and stock-taking. Such a system can achieve high accuracy in the passive tag localization without the support of either RSSI function or reference tags. An effective architecture, which consists of two guide rails, is built to enable the reader to move horizontally and vertically. With such an architecture, a reader can be used to locate a tagged object placed at any position and scan the whole warehouse as well. Also, two novel algorithms, continuous scanning and category-based scheduling, are proposed for locating single and multiple tagged objects, respectively. Compared with the skip scanning, the continuous scanning narrows the possible location range of a tagged object from a region to a single point. The category-based scheduling considers the clustering of goods or items and optimizes the process to handle multiple requests. Our theistical analysis and experimental results show that the proposed architecture and algorithms can reduce system cost and localization time and improve the localization accuracy.

Footnotes

Handling Editor: Nan Cheng

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) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by National Nature Science Foundation of China under Grant No. 61602093.

References

Sanpechuda

Kovavisaruch

A review of RFID localization: applications and techniques. In: Proceedings of the 5th international conference on electrical engineering/electronics, computer, telecommunications and information technology, Krabi, Thailand, 14–17 May 2008, vol. 2, pp.769–772. New York: IEEE.

Ting

Kwok

Tsang

et al . The study on using passive RFID tags for indoor positioning. Int J Eng Bus Manag 2011; 3(1): 9–15.

Liu

Lau

et al . LANDMARC: indoor location sensing using active RFID. In: Proceedings of the first IEEE international conference on pervasive computing and communications, Fort Worth, TX, 26 March 2003, pp.407–415. New York: IEEE.

Zhang

Chen

et al . An RF-based system for tracking transceiver-free objects. In: Proceeding of the fifth annual IEEE international conference on pervasive computing and communications, White Plains, NY, 19–23 March 2007, pp.135–144. New York: IEEE.

Hightower

Want

Borriello

SpotON: an indoor 3D location sensing technology based on RF signal strength. Technical report, University of Washington, Seattle, WA, February 2000.

Hightower

Vakili

Borriello

et al . Design and calibration of the SpotON ad-hoc location sensing system. Technical report, Department of Computer Science and Engineering, University of Washington, Seattle, WA, August 2001.

Wang

Tzeng

NF.

RFID-based 3-D positioning schemes. In: Proceedings of the 26th IEEE international conference on computer communications, Barcelona, 6–12 May 2007, pp.1235–1243. New York: IEEE.

Bouet

Pujolle

L-VIRT: range-free 3-D localization of RFID tags based on topological constraints. Comput Commun 2009; 32(13–14): 1485–1494.

Choi

Song

IY.

R-LIM: an affordable library search system based on RFID. In: Proceedings of the international conference on hybrid information technology, Cheju Island, South Korea, 9–11 November 2006, pp.103–108. New York: IEEE.

10.

Zhu

Cao

et al . Fault-tolerant RFID reader localization based on passive RFID tags. In: Proceedings of the 31st IEEE international conference on computer communications, Orlando, FL, 25–30 March 2012, pp.2183–2191. New York: IEEE.

11.

Shangguan

Zhenjiang

Li ZY

et al . OTrack: order tracking for luggage in mobile RFID systems. In: Proceedings of the 32nd IEEE international conference on computer communications, Turin, 14–19 April, pp.3066–3074. New York: IEEE.

12.

Yang

Chen

et al . Tagoram: real-time tracking of mobile RFID tags to high precision using COTS devices. In: Proceedings of the 20th annual international conference on mobile computing and networking (MobiCom ’14), Maui, HI, 7–11 September 2014, pp.237–248. New York: ACM.

13.

Zhao

Jin

et al . Localization in 3D surface sensor networks: challenges and solutions. In: Proceedings of the 31st annual IEEE international conference on computer communications, Orlando, FL, 25–30 March 2012, pp.55–63. New York: IEEE.

14.

Yang

Jin

. 3D surface localization with terrain model. In: Proceedings of the 33rd annual IEEE international conference on computer communications. Toronto, ON, Canada, 27 April–2 May, pp.46–54. New York: IEEE.

15.

Maneesilp

Wang

et al . RFID support for accurate 3-dimensional localization. IEEE T Comput 2013; 62(7): 1447–1459.

16.

Liu

et al . Less is more: efficient RFID-based 3D localization. In: Proceedings of the 10th IEEE international conference on mobile ad-hoc and sensor systems, Hangzhou, China, 14–16 October 2013, pp.86–94. New York: IEEE.

17.

Quan

Liu

Zhang

et al . Enhancing crowd collaborations for software defined vehicular networks. IEEE Commun Mag 2017; 55(8): 80–86.

18.

Cheng

Zhou

Lei

et al . Performance analysis of vehicular device-to-device underlay communication. IEEE T Veh Technol 2017; 66(6): 5409–5421.

19.

Chen

Qin

Mao

et al . SmokeGrenade: an efficient key generation protocol with artificial interference. IEEE T Inf Foren Sec 2013; 8(11): 1731–1745.

20.

Chen

Zhang

Qin

et al . S2M: a lightweight acoustic fingerprints based wireless device authentication protocol. IEEE Internet Things 2017; 4: 88–100.

21.

Khan

Sharma

Ha Prabhu

A survey of RFID tags. Int J Recent Trends Eng 2009; 1(4): 68–71.

22.

Sheng

Mao

Efficient continuous scanning in RFID systems. In: Proceedings of the 29th conference on information communications, San Diego, CA, 14–19 March 2010, pp.1010–1018. New York: IEEE.

23.

Xie

Chen

et al . Continuous scanning with mobile reader in RFID systems: an experimental study. In: Proceedings of the 14th ACM international symposium on mobile ad hoc networking, Bangalore, India, 29 July–1 August 2013, pp.11–20. New York: ACM.

24.

Rosenkrantz

Stearns

Philip

et al . An analysis of several heuristics for the traveling salesman problem. SIAM J Comput 1977; 6(3): 563–581.

25.

Zhou

Luo

A general approach for the intensive RFID reader deployment. Int J Ad Hoc Ubiq Co 2014; 16(3): 206–215.

26.

Zhou

Liu

Luo

. A cube based model for RFID coverage problem in three-dimensional space. In: Proceedings of the IEEE 9th international conference on mobile ad-hoc and sensor networks, Dalian, China, 11–13 December 2013, pp.115–120. New York: IEEE.