Identifying the Missing Tags in Categorized RFID Systems

Abstract

RFID is a practical technology that supports extensive applications such as warehouse management, asset tracking, and transportation and logistics. Identifying the missing tags in categorized RFID systems is of practical importance for a variety of applications but is not yet thoroughly investigated. Traditional missing tag identification approaches can not solve the problem efficiently because they do not distinguish categories, leading to long scanning time and high energy consumption. To achieve time and energy efficiency, this paper proposes three protocols. First, we formally formulate the problem of missing tag identification in categorized RFID systems. And then a compact structure is proposed to active tags in protocols which carries a large volume aggregated tag ID information. To further improve the utilization rate of a frame, we design a rehash scheme to change empty slots and collision slots into singleton slots. We evaluate the performance of our protocols with extensive simulations. Compared with the physical-layer missing tag identification protocol (P-MTI), which is the state-of-the-art missing tag identification technology, our best protocol reduces the execution time up to 99.8%.

1. Introduction

Radio frequency identification (RFID) [1] has been widely employed in extensive applications such as warehouse management [2], transportation and logistics [3–5], and asset tracking [6, 7]. Compared with the existing barcode, RFID tags can be read wirelessly over a number of feet (passive RFID tags) or even hundreds of feet (active RFID tags). Meanwhile, a RFID tag has storage and computation capabilities. The data can be automatically read, eliminating the trouble of manual scanning. Their new functions have advantage over the barcode system that they extend the operational range and improve its reading accuracy in a variety of applications.

There are two major features in most of the current RFID systems. First, they are categorized systems. It is because each RFID tag not only has an inherent ID but also belongs to a category according to the product which it is attached to [8]. Such feature can be easily found in RFID system such as the systems in Walmart [9] and Hong Kong International Airport [10]. Hence, the methods in RFID systems should be able to distinguish the different categories. Second, RFID systems are large-scale systems. The quantity of the tags may scale up to millions in practical RFID systems. Many large-scale RFID systems can be seen in [11–13]. For this reason, the methods in RFID systems should be able to adapt to the increasing quantities of the tags.

The problem of missing tag identification has attracted wide attention due to its practical importance. Recently, many novel protocols have been proposed to identify the missing tags [13–15]. Typically, those approaches identify the missing tags for monitoring range of all RFID tags and do not distinguish categories. This will lead to time and energy inefficiency. However, the categorized system is very common in our daily life. For example, in the airport luggage management, considering the huge traffic every day, tens of thousands of pieces of luggage have to be dealt with. Luggage losses often happen due to theft or other reasons. Thus, passengers cannot timely access their luggage after they arrive which leads to tremendous financial losses for customers and industries. As we know, passengers check in the luggage according to different airlines and each piece of luggage is sorted to different categories according to different flights. Administrators want to know whether the luggage of a specific flight is complete or not.

The problem also exists in other applications such as warehouses, mega factories, hospitals, and military bases. In a large warehouse, there are different categories of merchandise such as clothes, shoes, watch, and jewelry. Managers want to know whether the merchandise of a specific category especially valuable categories is missing or not. Hence, an efficient categorized missing tag identification procedure will be greatly helpful.

There are two main challenges for identifying the missing tags in categorized RFID system. First, many applications may frequently run the protocol and need to receive a timely report of the missing tags. Thus, we need an efficient method to identify the missing tags as quickly as possible. Traditional missing tag identification approaches are not suitable because those approaches do not distinguish categories, leading to long scanning time. Meanwhile, in the process of previous missing tag identification, we find that some slots of a frame are wasted. Thus, the utilization rate of a frame still has room to improve. Second, how to solve the problem of energy consumption is another challenge. We only want to know the information of a specific category. All tags in RFID systems participating in will lead to energy wasting.

To address the above challenges, we propose three protocols for identifying the missing tags in categorized RFID systems. Our protocol design follows two guidelines to achieve time efficiency. One is to keep RFID tags which are not in the wanted category from participating in protocol. The other is to reduce radio collision that makes the information which is reported from the tags not be wasted. To achieve these goals, our three protocols add on top of one another, to improve the system performance. More specifically, the baseline protocol eliminates the transmission collision among the tags and avoids RFID tags which are not in the wanted category participating in protocol. The second protocol utilizes the Bloom filter as a tool to activate all tags in the wanted category. The protocol uses a compact structure to activate the tags and does not require any tag ID to be transmitted. Our last protocol further improves the second protocol by changing empty slots and collision slots into singleton slots. Here, empty slot means no response from tags in the slot; singleton slot means only one tag responds in the slot; collision slot means more than one tag responds in the slot. To achieve time efficiency, much prior work concentrates on how to turn the collision slots into singleton slots. And we found empty slots also account for a proportion of a frame. Hence, our protocol utilizes the empty slots and reduces collision slots that greatly improve the time efficiency. We analyze the protocol performance to obtain optimal parameter settings which are able to significantly reduce the time and energy overhead according to particular accuracy requirement.

Our contributions of this paper are briefly summarized as follows.

• (i)

  We formally introduce the problem of missing tag identification in categorized RFID systems.

• (ii)

  We propose three protocols that utilize a compact structure and reduce collision slots of a frame which significantly improve the time and energy efficiency.

• (iii)

  Compared with the physical-layer missing tag identification protocol (P-MTI) [15], which is the state-of-the-art missing tag identification technology, our best protocol reduces the execution time up to 99.8%.

The rest of the paper is organized as follows. The related work is presented in Section 2. In Section 3, we present the preliminaries of this paper. We give detailed description on our protocol and analyze system parameters in Section 4. The performance evaluation is illustrated in Section 5. Finally, we conclude this paper in Section 6.

2. Related Work

One closely related problem is RFID identification which aims at identifying the tags through collision arbitration [11, 16]. Existing RFID identification protocols can be generally classified into two categories: Aloha-based [17–23] and Tree-based [24–28] protocols. In Aloha-based identification protocols, the reader first broadcasts the query request to tags. Upon receiving such a request, each tag randomly chooses a time slot to transmit its ID. If a time slot happens to be selected by only one tag, then the tag can be successfully identified and will keep silent for the rest of the identification process. If more than one tag selects a time slot simultaneously, the responses are garbled due to tag-tag collision and the tags cannot be identified. Therefore, the tags need to retransmit and the process continues until all the tags are identified successfully. In Tree-based identification protocols, the reader queries the tags to detect whether any transmission collision occurs. If there are any tag-tag collisions, the reader continuously splits signal-collided tags into two subsets until all tags can be successfully identified. While the RFID identification protocols cannot be directly borrowed to address the missing tag identification problem in categorized RFID systems, the execution time increases with the number of tags and the communication overhead could be excessively high in categorized RFID systems.

Rather than identifying the RFID tags, the cardinality estimation protocols estimate the number of tags [12, 29–31], which may serve as primary inputs for tag identification. However, such approaches cannot be directly borrowed to address the categorized missing tag identification problem because they only provide an approximate estimation of tag number.

Recently, many efforts study the problem of tag monitoring and missing tag identification [2, 13–15]. Tan et al. [2] design a missing tag monitoring protocol (trust reader protocol: TRP) which can detect the missing tag events with probability α when the number of missing tags exceeds m. α and m are system parameters. However, TRP cannot detect the missing tag events with certainty and it cannot identify which tags are missing. In [13], Li et al. propose a missing tag identification protocol. Their optimal protocol (iterative ID-free protocol: IIP) can detect the missing tag events with certainty and identify the missing tags. In [14], Zhang et al. propose more efficient protocols and utilize multiple readers that can reduce the execution time. In [15], Zheng and Li look into the aggregated responses instead of focusing on individual tag responses and extract useful information from physical-layer symbols. They leverage the sparsity of missing tag events and identify the missing tags through compressive sensing. Opposite to the purpose of identifying the missing tags of all RFID tags in the monitoring region, in this work we focus on identifying the missing tags in categorized RFID systems.

3. Preliminaries

In this section, we will first introduce the system model which helps to understand the working process of the RFID system and then present the problem formulation of identifying the missing tags in categorized RFID systems.

3.1. System Model

In our model, the RFID system consists of three main components: a large number of RFID tags attached to items, a number of RFID readers that monitor the tags, and a backend server that has powerful computation capability. The backend server connects to the RFID readers through high speed and reliable wireless network such as Gigabit Ethernet. We focus on the communication between RFID readers and tags rather than the backend server. The RFID readers transmit commands of the backend server and later report responses back to the backend server. When multiple readers are synchronized, we logically treat them as one.

The RFID system may use battery-powered active tags that have larger transmission ranges or use passive tags that are energized by radio waves transmitted by the reader. The EPC global Class-1 Gen-2 standard [32] specifies several mandatory commands to regulate the RFID tags. It provides flexibility for RFID manufacturers to implement value-added features. Such an open design motivates researchers to explore new features of RFID tags for practical needs with currently available components (e.g., random number generator [32], lightweight hash function [33], etc.). We note that such routine components are widely implemented in current RFID tags. In this paper, the tag needs lightweight hash function.

In this paper, the RFID system works on a slotted Aloha model. According to the EPC global Class-1 Gen-2 standard [32], the reader communicates with the tags with the framed slotted Aloha protocol. In this standard, each tag contains a unique 96-bit ID. The communication between the reader and tags is composed of frames and each frame is further divided into time slots. The reader initiates communication by broadcasting commands and parameters to tags, for example, random number for hash function and number of time slots in one frame. Upon receiving the command, each tag will randomly select one slot to respond to the reader. If there is no response from tags in a slot, the slot is called an empty slot. If only one tag responds in a slot, the slot is called a singleton slot. In this case, the reader can decode the response successfully. If more than one tag responds in a slot, the reader cannot decode those responses because the signals collided; the slot is called a collision slot. Figure 1 illustrates an instance where 8 tags (A~H) contend for 10 time slots.

Figure 1

Framed slotted Aloha: 8 tags contend for 10 time slots.

A singleton slot or a collision slot is also called a nonempty slot. If the RFID reader only needs to know whether one slot is empty slot or nonempty slot, each tag can transmit one-bit short response in the selected slot. If the reader receives response in the slot, it indicates there has been a tag (tags) that selects the slot. Therefore, the slot is nonempty slot and it can be encoded as “1.” The empty slot can be encoded as “0.” The length of a short response can be denoted by $t_s$ . A slot can also allow the transmission of a 96-bit tag ID either from the reader to the tags or from a tag to the reader. The length of the slot can be denoted by $t_{\text{tag}}$ . Clearly, $t_s<t_{\text{tag}}$ . Using the parameters of the Philips I-Code system [32], we can get that $t_s=\mathrm{0.4}$  ms, and $t_{\text{tag}}=\mathrm{2.4}$  ms. To achieve time efficiency, we prefer to use short responses rather than 96-bit tag IDs.

3.2. Problem Formulation

We consider a large-scale RFID system with $\mathbf{N}=\{n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_{n_T}\}$ representing all the RFID tags in the interrogation zone covered by readers, where $n_T$ is the total number of tags. $\mathbf{C}=\{c_{\mathrm{1}},c_2,\dots ,c_{n_C}\}$ , representing different categories of all tags, where $n_C$ is the number of different categories. $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})=\{n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_{n_S}\}$ , representing the set of tags in a specific category, where $i=\mathrm{1},\dots ,n_C$ ; $n_S$ is the number of tags in a specific category and $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})\subseteq \mathbf{N}$ . $\mathbf{K}({\mathbf{c}}_{\mathbf{i}})=\{n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_{n_K}\}$ , representing the set of missing tags in a specific category, where $i=\mathrm{1},\dots ,n_C$ ; $n_K$ is the number of missing tags in a specific category and $\mathbf{K}({\mathbf{c}}_{\mathbf{i}})\subseteq \mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ . For example, given $c_i$ , we find $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ from N to identify the missing tags $\mathbf{K}({\mathbf{c}}_{\mathbf{i}})$ . The RFID reader has access to a database that stores the IDs of all tags. We can call $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ as a wanted category and each tag in $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ can be called a wanted tag. As Figure 2 depicts, what we want to know is whether there are missing tags in the set $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ . When the missing tag set $\mathbf{K}({\mathbf{c}}_{\mathbf{i}})$ is empty, it means all tags in $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ are present. Table 1 summarizes key notations used in this paper.

Table 1

Key notations.

Symbols	Descriptions
N	The set of tags in the interrogation zone
C	The set of different categories in the interrogation zone
$\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$	The set of tags in a specific category
$\mathbf{K}({\mathbf{c}}_{\mathbf{i}})$	The set of missing tags in a specific category
$n_T$	The number of tags in the interrogation zone
$n_C$	The number of different categories
$n_S$	The number of tags in a specific category
$n_K$	The number of missing tags in a specific category
$\text{BF}(·)$	The Bloom filter for the set
$h(·)$	A uniform hash function

Figure 2

Categorized missing tag identification.

The database alters according to the changing conditions. When new items are moved into the system, the tag IDs will be read into the database. When the items are moved out the system, they will be removed from the database. Even if a failure incurs such database information loss, we can recover it by executing an ID-collection protocol [21–23] that reads the IDs from the tags. In this case, we will not identify the missing tags that have already been lost. However, now that we have a database of the remaining tags, we can identify the missing tags after this point of time.

4. Protocol Design and Analysis

In this section, we propose three new protocols for identifying the missing tags in categorized RFID systems. We first give a baseline protocol which eliminates the transmission collision among the tags. We further propose a categorized missing tag identification protocol to avert any tag ID transmission. On top of it, we propose an enhanced categorized missing tag identification protocol to achieve time efficiency. In addition, we analyze system parameters of the protocols.

4.1. Baseline Protocol

We know that directly implementing the aforementioned missing tags identification protocols in set N is highly inefficient because the transmission size is not scalable. In the interrogation zone, the quantity of the tags may scale up to millions in some large-scale RFID systems. In many scenarios, we only care if there are missing tags in the wanted category $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ rather than in the whole tag space of set N. The RFID reader knows the information of tags in set $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ because it has access to the database. To reduce the searching space, an obvious optimization is that we let the RFID reader broadcast the IDs of tags in set $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ one after another and wait for the responses from tags. Upon receiving the broadcasted ID, each tag compares with its own ID. If the broadcasted ID matches its own ID, the tag immediately sends a short response. For each ID, we can reserve a one-bit slot for identifying tags short response, that is, “1” when tag response is received or “0” otherwise. If the reader receives the response, the tag must be in the system, or the tag is missing otherwise. Since a tag ID is 96 bits long and each tag replies a one-bit short response, the verification of each tag's existence takes $t_{\text{tag}}+t_s$ , and the total execution time of the baseline protocol is

$$\begin{array}{cc}& T_{\text{Baseline}}=n_S\times \left(t_{\text{tag}}+t_s\right).\end{array}$$

(1)

In practical large-scale RFID systems, the number of tags can scale to millions, while the number of tags in the wanted category is usually much smaller. Since the aforementioned missing tags identification protocols do not distinguish the categories, therefore the baseline protocol significantly reduces the time. We compare the execution time of P-MTI (with $K_{\mathrm{Max}}=N$ ) and P-MTI (with $K_{\mathrm{Max}}=\mathrm{0.2}N$ ) [15] with the baseline protocol, where $K_{\mathrm{Max}}$ is the estimated maximal number of missing tags. The result can be easily seen from Figure 3. We set $n_T$ as 1,000,000 and let $n_S$ change from 0 to 10,000.

Figure 3

Execution time: baseline versus P-MTI.

Although the baseline protocol demonstrates a promising performance improvement, it suffers from some limitations. In the baseline protocol, the transmission of query message takes a large portion of the execution time. Moreover, unique tag IDs are explicitly transmitted and acknowledged on the air which leads to potential privacy leaks. Therefore, it motivates us to design a more efficient and secure categorized missing tag identification protocol.

4.2. Categorized Missing Tag Identification Protocol (CMTI)

Based on the baseline protocol, we propose a categorized missing tag identification protocol (CMTI) to further reduce transmission overhead. In particular, we use the Bloom filter as a tool to carry aggregated tag ID information which is capable of encoding itemized information in a hashed Boolean vector. We transmit the vector instead of explicit tag IDs to activate the tags in wanted category $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ . The protocol consists of two phases. The whole verification procedure does not include any ID transmission.

4.2.1. First Phase

We activate the wanted tags by using a Bloom filter produced by the tags in $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ . An empty Bloom filter is a bit array of M bits, all set to “0.” If we want the Bloom filter to represent a set $\mathbf{A}=\{a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_L\}$ , where L is the number of set elements, there must be V independent hash functions $h_i(·)\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{1}\le i\le V)$ , each of which maps the set element to one of the M array positions with a uniform random distribution. To add an element, we feed it to each of the V hash functions to get V array positions. Set the bits at all these positions to “1.” The Bloom filter vector can represent the set A when L set elements are all added. In order to determine whether a given element b belongs to A, we feed it to each of the K hash functions $h_i(b)$ to get V array positions. If all $h_i(b)$ bits at these positions are “1,” we assert that $b\in \mathbf{A}$ . If any of the bits at these positions is “0,” the element is definitely not in the set A.

At the beginning of the phase, the backend server constructs a Bloom filter vector by mapping the tags in the wanted set $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ into an M-bit array using V hash functions. Then the RFID reader broadcasts the M-bit Bloom filter vector and V to all RFID tags in interrogation zone. Here we denote the Bloom filter vector by $\text{BF}(\mathbf{S}({\mathbf{c}}_{\mathbf{i}}))$ . Upon receiving $\text{BF}(\mathbf{S}({\mathbf{c}}_{\mathbf{i}}))$ and V, each tag $n_i\in \mathbf{N}\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,n_T)$ performs V hash functions and checks whether the bits $h_i(·)\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{1}\le i\le V)$ of $\text{BF}(\mathbf{S}({\mathbf{c}}_{\mathbf{i}}))$ are “1.” If all the V bits in $\text{BF}(\mathbf{S}({\mathbf{c}}_{\mathbf{i}}))$ are “1,” then we say that the tag $n_i$ passes $\text{BF}(\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ and the tag keeps active in the following phase. Otherwise it keeps silent. According to the procedure, we activate the tags in the wanted category without any ID transmission.

4.2.2. Second Phase

We identify the missing tags in the wanted category. At the beginning of this phase, the RFID reader transmits a request with two parameters f and r, where f is the frame size and r is a random number. The frame that consists of f short-response time slots follows the request. Upon receiving the request, each tag is pseudorandomly mapped to a slot at index $h(\text{id},r)$ , where id is the tag's ID and $h(·)$ is a hash function whose range is $[\mathrm{0},\dots ,f-\mathrm{1}]$ . Then the tag replies a one-bit short response at corresponding time slot. The RFID reader knows the wanted tags’ IDs, and it also knows the parameter r and the hash function, so it knows which slot each tag is supposed to respond to. Thus, the RFID reader knows the locations of empty slots, singleton slots, and collision slots. If the RFID reader finds a supposed singleton slot or a collision slot turns into an empty slot, the tag(s) that is mapped to the slot must be missing.

After receiving responses, the RFID reader measures the state of the slots. Since the one-bit short response can only successfully verify the tags which is mapped to a singleton slot, the RFID reader constructs a vector that consists of f bits, representing the actual state of the slots. In the vector, “0” indicates empty slots or collision slots and “1” indicates singleton slots. The RFID reader transmits the vector; each tag checks it at corresponding position according to its responding slot. If a tag sees that its bit in vector is “1,” it means that its slot is a singleton slot and the tag will not participate in the following protocol execution. The unverified tags execute the same second phase until they are all verified. The frame size f will change on the basis of the number of unverified tags.

If the size of a vector is too long, the RFID reader divides it into segments of 96 bits which are equivalent to the length of the tag ID. Each segment is transmitted in a time slot of size $t_{\text{tag}}$ . Since the tags know the index of hash functions, they know in which segment they need to look for the information.

4.2.3. Analysis

In the following, we determine an appropriate size of the two phases.

In the first phase, the execution time is $T_{\mathrm{1}}=\lceil M/\mathrm{96}\rceil \times t_{\text{tag}}$ . Let M be the length of the Bloom filter vector, which is divided into segments and transmitted in $t_{\text{tag}}$ . In the second phase, the execution time is $T_{\mathrm{2}}=\lceil f/\mathrm{96}\rceil \times t_{\text{tag}}+f\times t_s$ .

So the total execution time is

$$\begin{array}{cc}& T_{\text{CMTI}}=\left(\lceil \frac{M}{\mathrm{96}}\rceil +\lceil \frac{f}{\mathrm{96}}\rceil \right)\times t_{\text{tag}}+f\times t_s.\end{array}$$

(2)

Under our protocol, if a slot is a singleton slot, the corresponding tag can be verified. The probability for singleton slots is

$$\begin{array}{l}\text{Prob}\left\{X_i=\mathrm{1}\right\}=\left(\begin{array}{l}{n}_S\\ \mathrm{1}\end{array}\right)\left(\frac{\mathrm{1}}{f}\right){\left(\mathrm{1}-\frac{\mathrm{1}}{f}\right)}^{n_S-\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\approx \frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}.\end{array}$$

(3)

Let $X_i$ be the random variable for the number of tags that respond in the ith slot of the frame. In the frame, each of the f slots has the above probability to be a singleton slot. We define $N_{\mathrm{1}}$ as the expected number of tags whose presence will be verified by the frame. We can have

$$\begin{array}{l}{N}_1\approx f·\text{Prob}\left\{X_i=\mathrm{1}\right\}\\ \hspace{1em}=f·\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}=n_S·\exp \left\{-\frac{n_S}{f}\right\}.\end{array}$$

(4)

Thus, we can have the average time for verifying the presence of one tag as follows:

$$\begin{array}{cc}& \frac{T_{\mathrm{2}}}{N_{\mathrm{1}}}\approx \frac{\lceil f/\mathrm{96}\rceil \times t_{\text{tag}}+f\times t_s}{n_S·exp\left\{-n_S/f\right\}}\approx \frac{\mathrm{0.425}}{\rho ·\exp \left\{-\rho \right\}}.\end{array}$$

(5)

We let $\rho =n_S/f$ and call it the load factor. Meanwhile, $t_s=\mathrm{0.4}$  ms and $t_{\text{tag}}=\mathrm{2.4}$  ms based on the Philips I-Code system [32]. Figure 4 shows the value of $T_{\mathrm{2}}/N_{\mathrm{1}}$ with respect to ρ.

Figure 4

Average time of CMTI for verifying the presence of one tag with respect to the load factor ρ.

In (5), we can see that the average time depends on ρ which is determined by $n_S$ and f. We obtain the optimal value $\rho =\mathrm{1.0053}$ . Thus, we can set f according to $n_S$ , which can achieve the minimum average execution time. We choose the same load factor $\rho =\mathrm{1.0053}$ for all frames; so the average execution time for verifying a tag maintains a constant value.

In CMTI, we use the Bloom filter as a tool to activate the tags in the wanted category $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ without transmitting explicit tag IDs. However, the collision slots and empty slots of the frames are wasted during the second phase. Thus, we try to improve the utilization rate of the frame to achieve time efficiency.

4.3. Enhanced Categorized Missing Tag Identification Protocol (ECMTI)

Based on the CMTI, we propose an enhanced categorized missing tag identification protocol (ECMTI) to improve the utilization rate of the frame. Our final protocol consists of two phases. We also use a Bloom filter produced with the tags in $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ to activate the wanted tags. The first phase of ECMTI performs the same as the CMTI protocol.

4.3.1. Second Phase

When a slot is a singleton slot, the corresponding tag can be verified. We know the probability of a slot turning to be a singleton slot from (3). Hence, we have

$$\begin{array}{cc}& \text{Prob}\left\{X_i=\mathrm{1}\right\}\approx \frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\le \frac{\mathrm{1}}{e}\approx \mathrm{36.8}\%,\end{array}$$

(6)

where the probability reaches its maximum value when $\left|\mathbf{S}\right|=f$ . So the majority of all slots, 63.2% or more of them, are either empty slots or collision slots. Obviously, empty slots do not contribute anything in tag verification. And only if the tags in a collision slot are all missing will the verification be successful because the RFID reader will find this expected collision slot to be actually empty. However, the chance for a collision slot to have only missing tags is small because of the small quantity of the missing tags. Therefore, the majority of the slots of the frame are mostly wasted. We design a method to exploit the information contained in the collision slot.

Since the RFID reader knows the wanted tags’ IDs, it knows in which slot each tag is supposed to respond. At the beginning of the second phase, the RFID reader transmits a request with parameters f, $r_{\mathrm{1}}$ , and $r_{\mathrm{2}}$ . Meanwhile, it also transmits a vector which consists of f bits. Each of the bits indicates the expected state of a slot. In the vector, “0” indicates empty slots or collision slots and “1” indicates singleton slots. Upon receiving the request and the vector, each tag is pseudorandomly mapped to a slot at index $h_{\mathrm{1}}(\text{id},r_{\mathrm{1}})$ , where id is the tag's ID and $h_{\mathrm{1}}(·)$ is a hash function whose range is $[\mathrm{0},\dots ,f-\mathrm{1}]$ . Then they check the vector at corresponding position according to their index $h_{\mathrm{1}}(\text{id},r_{\mathrm{1}})$ . If a tag sees that its bit in vector is “1,” it means its slot is a singleton slot and it can reply at that slot. If a tag sees that its bit in vector is “0,” it means its slot is a collision slot and it will be pseudorandomly mapped to another slot at index $h_{\mathrm{2}}(\text{id},r_{\mathrm{2}})$ , where $h_{\mathrm{2}}(·)$ is a hash function whose range is $[\mathrm{0},\dots ,f^{\prime }-\mathrm{1}]$ . $f^{\prime }$ is the number of “0”s in the vector, namely, the number of empty slots and collision slots in the frame. In this case, each tag is mapped to these “0”s positions at index $h_{\mathrm{2}}(\text{id},r_{\mathrm{2}})$ . Thus, the empty slots and the collision slots have a chance to become singleton slots. Then, the tag replies with a one-bit short response at corresponding time slot. The RFID reader knows in which slot each tag is supposed to respond. So if the RFID reader finds that a supposed singleton slot or a collision slot turns to an empty slot, the tag(s) that is mapped to the slot must be missing.

After receiving responses, the RFID reader measures the state of the slots in the same way as CMTI does. Each tag checks the vector to determine whether it participates in the following protocol execution. The unverified tags execute the same second phase until they are all verified. Figure 5 shows the process of the second phase.

Figure 5

The process of ECMTI in the second phase: (1) transmission of a request with parameters f, $r_{\mathrm{1}}$ , and $r_{\mathrm{2}}$ and a vector from backend server to the tags in the wanted category; (2) each tag is pseudorandomly mapped to a slot at index $h_{\mathrm{1}}(\text{id},r_{\mathrm{1}})$ and checks the vector at corresponding position; (3) each collision tag is pseudorandomly remapped to another slot which is not a singleton slot at index $h_{\mathrm{2}}(\text{id},r_{\mathrm{2}})$ ; (4) the reader measures the state of the slots and constructs a vector. Each tag checks it to determine whether they participate in the following process.

4.3.2. Analysis

In the following, we determine an appropriate size of the two phases.

In the first phase, the execution time is the same as the CMTI protocol: $T_{\mathrm{1}}^{\prime }=\lceil M/\mathrm{96}\rceil \times t_{\text{tag}}$ . In the second phase, the execution time is $T_{\mathrm{2}}^{\prime }=\mathrm{2}\lceil f/\mathrm{96}\rceil \times t_{\text{tag}}+f\times t_s$ .

So the total execution time is

$$\begin{array}{cc}& T_{\text{ECMTI}}=\left(\lceil \frac{M}{\mathrm{96}}\rceil +\mathrm{2}\lceil \frac{f}{\mathrm{96}}\rceil \right)\times t_{\text{tag}}+f\times t_s.\end{array}$$

(7)

Under the ECMTI protocol, the probability for singleton slots is

$$\begin{array}{l}\text{Prob}\{X_i=\mathrm{1}\}+(\mathrm{1}-\text{Prob}\{X_i=\mathrm{1}\})\times \text{Prob}\{X_i=\mathrm{1}\}\\ \hspace{1em}=\left(\begin{array}{l}{n}_S\\ \mathrm{1}\end{array}\right)\left(\frac{\mathrm{1}}{f}\right){\left(\mathrm{1}-\frac{\mathrm{1}}{f}\right)}^{n_S-\mathrm{1}}\\ \hspace{1em}\hspace{1em}+\left[\mathrm{1}-\left(\begin{array}{l}{n}_S\\ \mathrm{1}\end{array}\right)\left(\frac{\mathrm{1}}{f}\right){\left(\mathrm{1}-\frac{\mathrm{1}}{f}\right)}^{n_S-\mathrm{1}}\right]\\ \hspace{1em}\hspace{1em}\times \left(\begin{array}{l}{n}_S\\ \mathrm{1}\end{array}\right)\left(\frac{\mathrm{1}}{f}\right){\left(\mathrm{1}-\frac{\mathrm{1}}{f}\right)}^{n_S-\mathrm{1}}\approx \frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\\ \hspace{1em}\hspace{1em}+\left[\mathrm{1}-\frac{n_S}{f}·\exp \{-\frac{n_S}{f}\}\right]·\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\\ \hspace{1em}=\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}·\left[\mathrm{2}-\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\right].\end{array}$$

(8)

We define $N_{\mathrm{2}}$ as the expected number of tags whose presence will be verified by the frame. We can have

$$\begin{array}{l}{N}_{\mathrm{2}}\approx f·\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}·\left[\mathrm{2}-\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\right]\\ \hspace{1em}=n_S·\exp \left\{-\frac{n_S}{f}\right\}·\left[\mathrm{2}-\frac{n_S}{f}·\exp \left\{-\frac{n_S}{f}\right\}\right].\end{array}$$

(9)

Thus, we can have the average time for verifying the presence of one tag as follows:

$$\begin{array}{l}\frac{T_{\mathrm{2}}^{\prime }}{N_{\mathrm{2}}}\approx \frac{\mathrm{2}\lceil f/\mathrm{96}\rceil \times t_{\text{tag}}+f\times t_s}{n_S·\exp \{-n_S/f\}·\left[\mathrm{2}-\left(n_S/f\right)·\exp \{-n_S/f\}\right]}\\ \hspace{1em}\approx \frac{\mathrm{0.45}}{\rho ·\exp \left\{-\rho \right\}·\left[\mathrm{2}-\rho ·\exp \left\{-\rho \right\}\right]}.\end{array}$$

(10)

And $\rho =n_S/f$ is called the load factor. Meanwhile, $t_s=\mathrm{0.4}$  ms and $t_{\text{tag}}=\mathrm{2.4}$  ms based on the Philips I-Code system [32]. Figure 6 shows the value of $T_{\mathrm{2}}^{\prime }/N_{\mathrm{2}}$ with respect to ρ.

Figure 6

Average time of ECMTI for verifying the presence of one tag with respect to the load factor ρ.

In (10), we obtain the minimum average time $\mathrm{0.75}$  ms for verifying the presence of one tag. To keep the minimum average time, we can set f according to $n_S$ . In the second phase of ECMTI, the execution time is 0.75 ms  ×   $n_S$ .

4.4. Discussion

4.4.1. False Positive of Bloom Filter

In the first phase of CMTI and ECMTI, a tag which is not in the wanted set $\mathbf{S}({\mathbf{c}}_{\mathbf{i}})$ has a chance to be active because its all corresponding positions are “1,” which have by chance been set to 1 during the insertion of other elements, resulting in a false positive [34].

Assume that a hash function selects each array position with equal probability. If M is the number of bits in the array and V is the number of hash functions, then the probability that a certain bit is not set to “1” by a certain hash function during the insertion of an element is $(\mathrm{1}-(\mathrm{1}/M))$ . The probability that it is not set to “1” by any of the hash functions is ${(\mathrm{1}-(\mathrm{1}/M))}^V$ . If we have inserted $n_S$ elements, the probability that a certain bit is still “0” is ${(\mathrm{1}-(\mathrm{1}/M))}^{V{n}_S}$ . The probability that it is “1” is therefore $\mathrm{1}-{(\mathrm{1}-(\mathrm{1}/M))}^{V{n}_S}$ .

Now we test membership of an element that is not in the set. The probability of all of them being “1,” namely, the error rate, is

$$\begin{array}{cc}& p={\left[\mathrm{1}-{\left(\mathrm{1}-\frac{\mathrm{1}}{M}\right)}^{V{n}_S}\right]}^V\approx {\left(\mathrm{1}-e^{-V{n}_S/M}\right)}^V.\end{array}$$

(11)

We can determine M and V by the required false positive probability. When the number of activated tags which are not in the wanted category is large due to the false positive probability, we can handle it by using the Bloom filter again to reduce the wrong activated tags.

4.4.2. Impact of Imperfect Channel

The presence of channel noise can cause false positives and false negatives. For example, we assume a missing tag is mapped to a singleton slot. The expected singleton slot will actually be empty. However, due to channel noise, a false positive may occur if the RFID reader receives high noise which is mistaken for a tag response. Occasional false positives do not cause too much influence because a categorized missing tag identification protocol can be executed periodically. Thus, a missing tag which is not identified due to a false positive in this round will be identified in a later round.

A false negative occurs when a tag replies with a short response, but the transmission is corrupted by channel error. In this case, the RFID reader can not receive the response and the tag is mistaken for a missing tag. False negatives can also happen in ID transmission. When the RFID reader transmits a tag ID to verify the tag, channel error corrupts the transmission and consequently the tag does not respond. Therefore, the RFID reader takes it for a missing tag which actually exists. The false negatives can be easily handled by doing extra verification step. For example, the RFID reader transmits the potential missing tags’ IDs to verify their absence. If no response is sent back from the tag, then the RFID reader can confidently ensure their absence.

When tags are moved in or out of the system during protocol execution, false positives and false negatives may also happen. They can be handled by the approaches mentioned above. However, in order to reduce the false events caused by normal inventory operations, we should minimize the execution time. This is the place where our protocols significantly improve. In the next section, we will demonstrate through simulations.

5. Evaluation

In the previous sections, we have elaborated the design details and parameter analysis of our protocols. In this section, we first evaluate our protocols’ performance and then we compare them with the state-of-the-art method in the missing tags identification.

5.1. Simulation Results

We have performed extensive simulations to observe the performance of the proposed protocols. Based on the specification of the Philips I-Code system [32], we set the simulation parameters. Any two consecutive transmissions (from the reader to tags or vice versa) are separated by a waiting time. Thus, a one-bit slot for a tag to respond is 0.4 ms, which includes a waiting time before the transmission. And a 96-bit slot that carriers a tag ID or a vector segment is 2.4 ms, also including a waiting time. Those transmission rates give an approximate bitrate of 40 kbps.

According to the discussion in Section 4.4, we first investigate the optimal parameter settings of Bloom filter. In the simulation, we assume the required false positive rate is 0.01. Figure 7(a) illustrates the execution time in the first phase with varied V from 1 to 10. It shows that when $V=\mathrm{7}$ , the execution time is the shortest. With the optimal value of V, Figure 7(b) illustrates the execution time in the first phase with different false positive rates. In the following simulation, we set the required false positive rate as 0.01 and the optimal value of V as 7.

Figure 7

The investigation with different Bloom filter parameters: (a) the execution time with varied V from 1 to 10; (b) the execution time with varied false positive rate from 1% to 5%.

Based on the above parameter settings, we evaluate the average time for identifying a tag of EMTI and CMETI, respectively. According to the different number of tags in the wanted category, we all perform 300 simulations to get an average time for identifying a tag. Figure 8 shows the comparison of the practical average time and the theoretical average time for identifying a tag. The results are within a certain range of the theoretical average time.

Figure 8

The average time for identifying a tag: (a) the average time for identifying a tag of CMTI with varied $n_S$ from 1000 to 10000; (b) the average time for identifying a tag of ECMTI with varied $n_S$ from 1000 to 10000.

Based on the above results, we perform simulations of our three protocols. We set $n_T$ as 1,000,000 and $n_K=\mathrm{50}$ and vary $n_S$ from 0 to 10,000. Figure 9(a) shows the execution time of our three protocols changing with $n_S$ . Since the baseline protocol transmits the whole tag IDs, the execution time is the longest of the three protocols. With a compact structure, CMTI improves the performance without transmitting tag IDs. Based on CMTI, ECMTI further improves the utilization rate of a frame which performs best. The execution time of ECMTI is around 35.3% of the time taken by the baseline protocol and accounts for around 68.7% of CMTI. Then we set $n_T$ as 1,000,000 and $n_S=\mathrm{5000}$ and vary $n_K$ from 0 to 100. Our three protocols’ performance is shown in Figure 9(b). Since our protocols check the whole tags in the wanted category, the execution time of protocols does not change with the different number of missing tags. So the execution time in Figure 9(b) keeps constant.

Figure 9

The execution time comparison of three protocols: (a) the execution time with varied $n_S$ from 0 to 10000; (b) the execution time with varied $n_K$ from 0 to 100.

5.2. Performance Comparison

We compare our three protocols with P-MTI [15], which is the state-of-the-art technology in the missing tag identification. P-MTI uses $O(K\log (N/K))$ measurements to detect the missing tag events in the whole monitoring range. We set the number of measurements as $C{K}_{\mathrm{Max}}\log (N)$ where $K_{\mathrm{Max}}$ represents the estimated maximum number of missing tags and C is a constant ( $C=\mathrm{3}$ here) which are the same as [15] settings. We set P-MTI (100%) with $K_{\mathrm{Max}}=N$ and P-MTI (20%) with $K_{\mathrm{Max}}=\mathrm{0.2}N$ . We mainly investigate the transmission time of tags and reader and ignore the negligible communication overhead such as transmission time of initialization and reader to server transmission.

Table 2 presents the execution times of the protocols. We vary $n_S$ from 1,000 to 10,000 and set $n_T$ as 1,000,000. Since P-MTI is not a missing tag identification protocol for a specific category, its execution times depend on the number of tags in $n_T$ instead of $n_S$ . Therefore, in Table 2, the execution time of P-MTI (100%) and P-MTI (20%) keeps constant. From Table 2, we can see the execution time of our final protocol ECMTI compared with P-MTI (100%) and P-MTI (20%). When $n_S=$ 5,000, P-MTI (100%) requires 450 seconds and P-MTI (20%) requires 90 seconds while ECMTI requires only 4.95 seconds, accounting for 1.1% and 5.5% of their execution times.

Table 2

The execution time with respect to $\left|\mathbf{S}\right|$ .

$n_S$	Execution time in seconds					ECMTI versus P-MTI $(\mathrm{100}\mathrm{\%})$	ECMTI versus P-MTI $(\mathrm{20}\mathrm{\%})$
	P-MTI (100%)	P-MTI (20%)	Baseline	CMTI	ECMTI	$(t_{\text{P-MTI}(\mathrm{100}\mathrm{\%})}-t_{\text{ECMTI}})/t_{\text{P-MTI}(\mathrm{100}\mathrm{\%})}$	$(t_{\text{P-MTI}(\mathrm{20}\mathrm{\%})}-t_{\text{ECMTI}})/t_{\text{P-MTI}(\mathrm{20}\mathrm{\%})}$
1000	450	90	2.8	1.44	0.99	99.8%	98.9%
2000	450	90	5.6	2.88	1.98	99.6%	97.8%
3000	450	90	8.4	4.32	2.97	99.3%	96.7%
4000	450	90	11.2	5.76	3.96	99.1%	95.6%
5000	450	90	14	7.2	4.95	98.9%	94.5%
6000	450	90	16.8	8.64	5.94	98.7%	93.4%
7000	450	90	19.6	10.08	6.93	98.5%	92.3%
8000	450	90	22.4	11.52	7.92	98.2%	91.2%
9000	450	90	25.2	12.95	8.9	98%	90.1%
10000	450	90	28	14.4	9.9	97.8%	89%

Meanwhile, we evaluate the time of identifying the first missing tag based on different number of missing tags. This is an important function for categorized RFID systems that require a quick answer on whether the wanted category of tags is complete or not. We set $n_S=\mathrm{10,000}$ and the number of missing tags $n_K$ varies from 1 to 5. Note that $n_K=\mathrm{0}$ indicates the tags in the wanted category are intact. Table 3 shows the time of identifying the first missing tag of all protocols.

Table 3

The time to identify the first missing tag with $\left|\mathbf{S}\right|$ = 10,000.

$n_K$	Execution time in seconds
	P-MTI (100%)	P-MTI (20%)	Baseline	CMTI	ECMTI
1	450	90	14.4	8.4	6.1
2	450	90	9.5	6.4	4.9
3	450	90	7.2	5.4	4.2
4	450	90	5.8	4.7	3.8
5	450	90	4.8	4.3	3.6

From Table 3, we get that the identification times of P-MTI (100%) and P-MTI (20%) are two constants since they require the RFID reader to accomplish all $C{K}_{\mathrm{Max}}\log (N)$ measurements from tags before the result comes out. For our protocols, the identification times decrease as $n_K$ increases. That is because more missing tags make it easier to identify one of them. Our best protocol ECMTI requires far less time to identify the first missing tag of the wanted category, especially when $n_K$ is small. For instance, when $n_K=\mathrm{1}$ , P-MTI (100%) requires 450 seconds and P-MTI (20%) requires 90 seconds while our protocol ECMTI requires only 6.1 seconds.

6. Conclusion

In this paper, we study the problem of identifying the missing tags in categorized RFID systems. The solution to the problem is of practical importance for many applications. In order to keep normal operations unaffected, we should minimize the execution time of the protocol for identifying the missing tags of the wanted category. We propose three protocols with progressive time efficiencies. We utilize the Bloom filter as a tool to activate all tags in the wanted category which keeps the tags in the monitoring range from all participating in the protocol. Meanwhile, we further use method to change empty slots and collision slots into singleton slots that improve the utilization of the frame. We do extensive simulations to evaluate the performance of our protocols. The results demonstrate that our three protocols outperform other possible solutions originated from existing approaches.