Fast and Effective Tag Searching for Multi-Group RFID Systems

Abstract

In RFID-assisted applications, the customers often request to provide the tag searching service to determine which specific tags are present in the system. In practice, tags are usually divided into different groups to represent different categories or brands. We found that the traditional tag searching protocols are not very appropriate for multi-group RFID scenarios because they cannot ensure that the searching results of each group satisfy the predefined reliability requirements. Therefore, we develop a series of effective multi-group tag searching schemes. B-Search is a basic method that leverages the filter vector and the indicator vector to perform tag searching for each group sequentially. G-Search and A-Search are two parallel multi-group tag searching schemes. G-Search selects the longest frame length as the frame length of all groups, while A-Search can adaptively adjust the frame length of each group to improve the searching efficiency. We evaluate the performance of the proposed protocols through theoretical analysis and discuss the optimal parameter settings to minimize the execution time. Extensive simulations illustrate that both G-Search and A-Search can achieve fast and effective multi-group tag searching.

1. Introduction

After years of development, a variety of Internet of Things (IoT) technologies [1,2,3,4] are fully applied in different industries. As the central supporting technology for IoT applications [5,6,7], radio frequency identification (RFID) has received widespread attention. RFID is a kind of short-range radio communication technology, which can automatically identify target objects and obtain relevant data through radio frequency signals, without manual intervention in the process. Compared with bar codes and QR codes, RFID technology has the advantages of larger data storage capacity, wider communication range, and nonline-of-sight transmission.

An RFID system generally consists of a reader and several tags [8,9]. By emitting electromagnetic waves, the reader can provide energy for tag operations and communicate with tags. The tag is the data carrier in the system that can send the stored data to the reader in a non-contact manner. Tags can be attached to products to indicate some certain information. With the price of RFID tags becoming lower and lower, RFID technology is deployed in a wide range of industries, such as identity recognition, cardinality estimation, inventory control, supply chain management, object localization, and object tracking [10,11,12].

Tag searching is a new problem derived from RFID-assisted warehouse management systems. For instance, a manufacturer has produced some sub-standard products, and these products have been delivered to some warehouses. The manufacturer manager wants to find out the sub-standard products in the warehouse. For the manager, the tag IDs of the sub-standard products are known, and the tag IDs of the other non-relevant products in the warehouse are unknown. With these known IDs, the manufacturer manager can perform tag searching in the warehouse to find out these sub-standard products. In summary, the tag searching problem is to determine which known tags are present in a given local tag set. There are two simple ways to solve the problem: local tag identification and wanted tag polling [13,14], but they are time-consuming. In recent years, researchers have proposed a lot of tag searching algorithms [13,14,15,16,17], including iterative algorithms and segmented algorithms, which have greatly improved the efficiency of tag searching.

Sometimes, tags are divided into different categories based on the type or brand of products to which they are attached. For the scenario, we may need to perform some operations for a certain category of tags. For example, the reader samples information, performs tag searching, and determines if a missing tag event occurs in a category. Typically, this scenario is referred to as the multi-group RFID system. In the system, researchers are most interested in the missing tag detection problem, and many effective multi-group missing tag detection protocols have been proposed [18,19,20]. The tag searching problem is much more complex and worthwhile. Obviously, the traditional tag searching focuses on studying single-group RFID systems, which is a special case of multi-group RFID systems. Currently, there is hardly a protocol which can effectively and pertinently solve the multi-group tag searching problem to ensure that the searching results in each group satisfy the predefined reliability requirements.

To overcome this challenge, we deliver a comprehensive analysis on tag searching in multi-group scenario and investigate how to devise optimal tag searching algorithms. Of course, the three multi-group tag searching protocols we proposed are still appropriate in the single-group situation.

The main contributions in our paper are summarized as follows:

• We expand the application scenario of tag searching and systematically formulate the multi-group tag searching problem;
• We use the segmented tag searching protocol to solve the multi-group tag searching problem and develop B-Search protocol. All groups are searched sequentially. For tag searching within a group, the reader first performs the deactivation of non-wanted tags and then further performs the verification of target tags;
• Meanwhile, we propose two parallel multi-group tag searching protocols called G-Search and A-Search, respectively. G-Search selects the longest frame length as the frame length of all groups. A-Search can adaptively adjust the frame length of each group, thus improving the searching efficiency when the number of local tags and the number of wanted tags are different.
• We conduct theoretical analysis to optimize the parameter settings of the three proposed protocols, and extensive simulations demonstrate that our best protocols can achieve fast and effective multi-group tag searching.

The rest of our paper is organized as follows: Section 2 gives a brief overview of traditional tag searching protocols and multi-group missing tag detection protocols. In Section 3, we construct the system model and define the multi-group tag searching problem. We propose a basic multi-group tag searching protocol called B-Search and give parameter optimizations in Section 4. Section 5 describes our parallel multi-group tag searching protocol called G-Search. In Section 6, we propose an adaptive multi-group tag searching protocol called A-Search to further improve the searching efficiency. Extensive simulations and analysis are presented in Section 7. Finally, we conclude this paper in Section 8.

2. Related Work

Previous researchers have studied RFID systems deeply, and have proposed a large number of algorithms for practical applications, such as tag identification, tag cardinality estimation, and so on. We will introduce the protocols associated with the multi-group tag searching in the following: the traditional tag searching protocols and the multi-group missing tag detection protocols.

2.1. Traditional Tag Searching Protocols

Traditional tag searching is to determine the intersection of wanted tag set and local tag set in a large-scale RFID system with the minimum time while satisfying the certain reliability requirements. Existing tag searching protocols can be classified into iterative protocols and segmented protocols, which are summarized as follows:

Iterative tag searching protocols perform iterative filtering in a variety of ways to dynamically approximate the target tag set, which is currently the most mainstream tag searching approach. Min et al. [13] designed a novel technique called a filtering vector and proposed an iterative tag searching protocol called Iterative Tag Search Protocol (ITSP). ITSP filters non-wanted tags and non-target tags by filtering vectors and then keeps repeating the process until the searching results satisfy the reliability requirements. Yu et al. [15] proposed a probabilistic tree-based tag searching approach called Tree-based Tag Search Protocol (TTS), which hashes multiple tags into each internal tree node and performs batched verification to verify target tags. Liu et al. [16] developed a time-effective tag searching protocol called Compact Exclusive Validation Protocol (CEV). CEV utilizes the Ordering Indicator and KEY-Filter to filter out non-wanted tags so that the target tags are verified without interference.

The segmented tag searching protocols implement interference tag deactivation and target tag verification, respectively. Compared with iterative tag searching protocols, segmented tag searching protocols can avoid repetitive verification of target tags. Zheng et al. [17] developed a solution called Compact Approximator-Based Tag Searching Protocol (CATS). CATS first filters the non-wanted tags through a Bloom filter and then forms a virtual Bloom filter from the remaining local tags to determine the target tags. Subsequently, BFSearch+ tag searching protocol was proposed by Yan et al. [14]. They designed new techniques called composite filter vector and indicator vector. The composite filter vector can complete non-wanted tag deactivation efficiently. The indicator vector is able to assign all the wanted tags to a singleton slot for verification and determine the target tags. BFSearch+ is the best time-effective traditional tag searching protocol available.

2.2. Missing Tag Detection Protocols in Multi-Group RFID System

In the scenario of multi-group RFID systems, the most popular problem investigated by researchers is the missing tag detection. The objective of missing tag detection is to determine if a missing tag event has occurred in the system. When the number of missing tags in the system is larger than a certain threshold, a missing tag event is considered to have occurred. Missing tag detection is flexible and useful in some practical scenarios.

For multi-group RFID systems, the reader needs to recognize whether a missing tag event occurs within a group. To solve this problem, researchers have proposed many multi-group missing tag detection protocols. Yu et al. [18] developed a series of missing tag detection protocols by incorporating an improved Bloom filter design and parameter tuning in multi-group and multi-region RFID systems. Shortly after, a Simultaneous Missing Tag Detection protocol (SMTD) was proposed by Liu et al. [19]. It can decode out multiple frame occupation vectors from one actual time frame, and each frame occupation vector can complete the missing tags detection within a group. Combined with the Category Clustering protocol (CC) which can cluster the tag categories into one batch, SMTD can significantly reduce the time for multi-group missing tag detection. Lin et al. [20] developed an Accurate and Expeditious Multi-group Missing Tag Detection protocol (AEMD), which implants a built-in vector to tags in the offline phase, and the reader implements multi-group missing tag detection by collecting the built-in vectors of tags.

3. Preliminary

In this section, the multi-group RFID system model and the multi-group tag searching problem statement are described in detail.

3.1. System Model

Normally, a multi-group RFID system [14,16] is composed of a back-end server, several readers, and lots of tags, which are divided into multiple groups in the interrogation region. Because readers are connected to the back-end server, we consider the readers and the back-end server as a whole and refer to it generically as the reader, which has great computing power and storage capacity. For the case of multiple readers, we can employ the existing reader scheduling algorithms to schedule readers without conflicts. Therefore, in our paper, we consider the case of a single reader.

The communication between the reader and tags complies with Class 1 Generation 2 (C1G2) standard and adopts listen-before-talk communication mode [21]: firstly, the reader initiates communication by broadcasting query command and related parameters, including the frame length f and random seed R, and then tags perform the hash function ($H(ID,R)$ mod f) to select a time slot and respond in the slot, where the $ID$ represents a 96-bit unique identification for each tag. Because of the randomness of slot selection, we usually divide the time slots into empty slots, singleton slots and collision slots, according to the number of tags responding in a slot. Only in a singleton slot, the tag can send the message to the reader successfully. There are usually three types of messages sent by tags: 1-bit short response, 16-bit long response, and 96-bit tag ID. We denote the time duration for transmitting a 96-bit tag ID as $t_{id}$ and the time duration for transmitting a 1-bit short response as $t_s$.

In practice, products are often located together with the same category in a warehouse. For the convenience of management, the tag ID is required to express the group information, and it contains two components: the group ID denoted by $I{D}_s$ and the member ID denoted by $I{D}_m$. The group ID indicates the group to which the tag belongs, and the member ID is the unique identification sequence of the tag in a group. Tags with the same group ID share the same group information, which may be the category, the brand, or the manufacturer of the tagged products [22]. The group information is deterministic and preloaded into tags to wait for query by readers after tags are put into service. The length of the group ID can be adjusted appropriately according to the practical requirements. In this paper, we assume that the category ID has 16 bits.

3.2. Problem Statement

Assume that the tags in the interrogation region are divided into G groups, with no overlap between groups. Each group has a group ID as a unique identification for the group. According to the knowledge of traditional tag searching, the local tag set represents the set of tags in the interrogation region, denoted by L. We suppose that the reader only knows the number of local tags in group g, denoted by $\left|L_g\right|$, and does not know anything else about them. We use W to denote the set of wanted tags, which represent the tags that we are interested in, and we want to check whether they are in the interrogation region. The reader not only knows the number of wanted tags in group g, denoted by $\left|W_g\right|$, but also knows the IDs of the wanted tags in group g, $g\in \{1,2,\dots ,G\}$. That is to say, the group state of the wanted tags is known, while the group state of the local tags is unknown. However, since the tag grouping is completed according to the actual situation before the tags are put into application, the reader has the knowledge of all group IDs. Moreover, the ultimate goal of tag searching is to determine the intersection of local tags and wanted tags in group g, and we refer to the tags in the intersection as target tags, represented by $T_g$, i.e., $T_g=W_g\bigcap L_g$. The reader can obtain the number of target tags in each group, denoted by $\left|T_g\right|$, through performing the target tag estimation protocol. In addition, we refer to the tags in the local tag set except for the target tags as non-wanted tags, and the tags in the wanted tag set except for the target tags as non-target tags. Figure 1 briefly illustrates the tag searching problem in a multi-group RFID system.

We are interested in tag searching event for each group. In other words, multi-group tag searching protocols need to discover the common part of the local tag set and the wanted tag set in group g under the predefined reliability requirement.

The multi-group tag searching problem is defined as: In a large-scale RFID system with G-group tags, given a wanted tag set, determine $T_g=W_g\bigcap L_g$ for group g with the minimum time while satisfying the following two requirements:

(1)

All target tags for group g in the interrogation region must be identified. To put it simply, for group g, the final searching result $T_g^{*}$ must contain all the target tags, i.e., $T_g\subseteq T_g^{*}$.

(2)

The tag searching result for group g has to satisfy the predefined reliability requirement $P_{req}$$(0<P_{req}<1)$, namely

$$\frac{|T_g^{*}-T_g|}{min(\left|W_g\right|,\left|L_g\right|)}\le 1-P_{req},$$

(1)

where $|·|$ denotes cardinality of the set and $g\in \{1,2,\dots ,G\}$. The phenomenon that the target tags in tag searching results are more than target tags in practice is due to the false positive during the tag searching, which means non-target tags and non-wanted tags are mistaken for target tags. Equation (1) indicates that the probability of the appearance of the false positive tags should be within the allowable range of reliability. Other than that, we define the target tag ratio as $\lambda$, i.e., $\lambda =\frac{\left|T_g\right|}{min(\left|W_g\right|,\left|L_g\right|)}$ and the group interval as r. Group interval is the increment size of the number of tags between different groups.

4. B-Search

In this section, we propose a baseline approach to solve the multi-group tag searching problem, called B-Search. The overall concept of the approach is that the tag searching is performed separately in order for each group, with only one group searched at a time. Specifically, B-Search consists of three phases: in phase I, the reader wakes up the tags in a group; in phase II, the reader eliminates the interference of non-wanted tags, laying the foundation for phase III; and, in phase III, the reader further determines the target tags in the group. Details are as follows.

4.1. Protocol Description

Phase I: Initiate the tag searching within a group. The reader broadcasts a group ID. After broadcasting, the tag in the interrogation region checks whether its group ID matches. The matching tags remain active and execute the algorithms of phases II and III. After the tag searching in this group is completed, the reader broadcasts the next group ID to initiate tag searching for the next group.

Phase II: Eliminate the interference of non-wanted tags in the group. First, the reader constructs a virtual filter vector by performing multiple hash operations on the wanted tag set. The reader initiates a query with the parameter $f_g$, $k_g$ and $R_1$, where $f_g$ indicates the frame length of this query, $k_g$ indicates the number of independent hash functions used in this query, and $R_1$ denotes the random seed in this query. The different hash functions in the query use the same random seed $R_1$. Based on the slots selected by the wanted tags, the reader can construct a vector. Each bit in the vector corresponds to a slot. The slot with tag responses is denoted by 1 and without tag responses is denoted by 0. The reader sequentially performs l queries by random seeds $\{R_1,R_2,\dots ,R_l\}$ to obtain l vectors. By synthesizing the information of these vectors, the reader can derive a filtering vector, denoted by $V_1$. If the first bit of the first vector is 0, the first slot in the filter vector $V_1$ is represented by 1. If the first bit of the first vector is not 0, but the first bit of the second vector is 0, the first slot of the filter vector is represented by 2, and so on. If the first bit of all vectors is not 0, the first slot in the filter vector is denoted by 0. In summary, each slot in the filter vector indicates where the first “0” occurs. Then, the reader broadcasts the related parameters and filter vectors $V_1$ to the local tags in this group. The local tag performs $k\times l$ hash operations in turn to select $k\times l$ slots in $V_1$ for confirming whether it is the non-wanted tag. If the number in the slot it chooses is the same as the number of the random seed it uses, the tag is a non-wanted tag and will be deactivated immediately.

Phase III: Determine the target tags in the group. First, the reader assigns all the wanted tags to a slot for verification. The reader initiates many queries on the wanted tag set by some random seed $\{R_1^{\prime },R_2^{\prime },\dots \}$, where the frame length is $f_g^{\prime }$. In first query, the reader can acquire an indicator vector based on the slots selected by the wanted tags, denoted by $V_2$. Each bit in the vector corresponds to a slot. The slot with only one wanted tag response is represented by 1, and the rest of the slots are represented by 0. The singleton slot which is selected by only one wanted tag is the verification slot of the wanted tag. The reader then removes the singleton slots and the wanted tags in the singleton slot, and initiates the second query with the remaining wanted tags and new frame length. At the end of the second query, the reader marks the bit in the indicator vector $V_2$ corresponding to singleton slots as 2. The reader no longer performs queries until all the wanted tags are assigned to a singleton slot. Assume that a total of $h_g$ hash operations have been performed with a $h_g$ random seed. Apparently, each bit in the indicator vector $V_2$ refers to the random seed number used by the wanted tag in the slot. The reader then broadcasts the corresponding parameters to the local tags in this group. The tag selects slots using these random seeds in turn and determines its response slot based on whether its corresponding bit in the indicator vector matches its random seed number. After determining the response slot, the tag forms a response vector. In the response vector, the response bits of the tag are marked as 1, and the others are marked as 0. The response vectors of all local tags are packaged into some 96-bit messages and sent to the reader at the same time. Depending on the local tag response, the reader can determine exactly which tags are the target tags.

Figure 2 illustrates the specific process of multi-group tag searching by the B-Search protocol.

4.2. Parameter Optimization

First, the reader needs to broadcast the group ID to notify the tags in the group performing tag searching. $T_0$ denotes the time taken to broadcast the group IDs:

$$T_0=16·G·T_s.$$

(2)

B-Search protocol performs tag searching sequentially in groups. Only one group is searched at a time. Thus, we can take the g-th group as an example for parameter optimization.

Actually, the filter vector $V_1$ is an important method for non-wanted tag deactivation, which is obtained by combining multiple vectors. The probability that any bit in a vector equals 1 is denoted by $P_v$, which is calculated as follows:

$$P_v=1-{\left(1-\frac{1}{f_g}\right)}^{k_g·\left|W_g\right|}\approx 1-e^{-\frac{k_g·\left|W_g\right|}{f_g}}.$$

(3)

Subsequently, if the third bit of the filter vector $V_1$ is equal to r, it means that the third bits in the vectors constructed by the first $r-1$ queries in the phase II all equal 1, and the third bit in the vector constructed by the r-th query equals 0. It represents the third bit in the vector constructed by the r-th query is adopted by the filter vector $V_1$. A non-wanted tag cannot be deactivated if all slots that the tag selects are not adopted by the filter vector $V_1$. We denote the probability that a non-wanted tag will not be deactivated as $P_d$. As we know,

$$P_d=\prod _{r=1}^l{\left(1-(1-P_v)·P_v^{r-1}\right)}^k.$$

(4)

Thus, the number of non-wanted tags in the g-th group that are not deactivated is $P_d·(\left|L_g\right|-\left|T_g\right|)$. In multi-group tag searching, the search results for each group need to satisfy predefined reliability requirements $P_{req}$, so

$$\frac{P_d·(\left|L_g\right|-\left|T_g\right|)}{min(\left|W_g\right|,\left|L_g\right|)}\le 1-P_{req}.$$

(5)

As shown in Equation (5), we need to choose the appropriate parameters l, k, and $f_g$, so that $P_d$ satisfies the reliability requirements.

In [14], Yan et al. revealed that, when $l\ge 3$, the decrease of $P_d$ is not significant as l increases through simulations. Therefore, it is quite appropriate for us to set l to 3.

The time spent by the g-th group in phase II is denoted as $T_g$, which is

$$T_g=\left(1+\lceil \frac{f_g·\lceil lo{g}_2(l+1)\rceil }{96}\rceil \right)·T_{tag}.$$

(6)

We can find the optimal frame length $f_g^{*}$ and the number of hash functions $k^{*}$ by integer programming.

$$\begin{array}{cc}\hfill & (k^{*},f_g^{*})=\underset{k,f_g}{argmin}\left(\left(1+\lceil \frac{f_g·\lceil lo{g}_2(l+1)\rceil }{96}\rceil \right)·T_{tag}\right),\hfill \\ \hfill & s.t.\left\{\begin{array}{c}k\in N^{+},f_g\in N^{+}\hfill \\ P_d\le (1-P_{req})·\frac{min(\left|W_g\right|,\left|L_g\right|)}{(\left|L_g\right|-\left|T_g\right|)}\hfill \end{array}\right.,\hfill \end{array}$$

(7)

where $N^{+}$ denotes the set of positive integers.

In phase III of B-Search, we only need to determine the frame length $f_g^{\prime }$. Because the response vectors of all local tags are packaged into some 96-bit messages, $f_g^{\prime }$ can be taken as:

$$f_g^{\prime }=\lceil \frac{\left|W_g\right|}{96}+p\rceil ·96p\in N^{+},$$

(8)

where p is an adjustment factor. We denote the time spent of the g-th group in the target tag verification phase by $T_g^{\prime }$. It is easy to know that:

$$\begin{array}{cc}\hfill T_g^{\prime }& =\left(\lceil \frac{f_g^{\prime }·\lceil {log}_2(h_g+1)\rceil }{96}\rceil +1\right)·T_{tag}+\lceil \frac{f_g^{\prime }}{96}\rceil ·T_{tag}\hfill \\ \hfill & \le \left(\lceil \frac{\lceil {log}_2(h_g+1)\rceil }{96}\rceil +2\right)·\lceil \frac{f_g^{\prime }}{96}\rceil ·T_{tag}\hfill \\ \hfill & \approx \lceil \frac{{log}_2(h_g+1)}{96}+2\rceil ·\left(\lceil \frac{\left|W_g\right|}{96}\rceil +p\right)·T_{tag}.\hfill \end{array}$$

(9)

From the analysis of Yan et al. in [14], we know that $T_g^{\prime }$ can be taken to the minimum value when $p=0$.

Assume that the time to perform the B-Search protocol in a large-scale RFID system with G-group tags is $T_B$. According to the analysis above, $T_B$ can be calculated as:

$$T_B=T_0+\sum (T_g+T_g^{\prime }),g\in \{1,2,\dots ,G\}.$$

(10)

5. G-Search

B-Search is a basic multi-group tag searching protocol, and each group is searched separately in order. B-Search is time-consuming because each group needs to broadcast the relevant parameters to initialize tag searching. In short, these parameters have to be broadcast G times, and the tag searching has to be performed G times. In this section, we propose a parallel multi-group tag searching protocol called G-Search, which performs tag searching only once in all groups simultaneously. G-Search can be divided into three phases. In phase I, the reader arranges the order for groups and assigns a response slot segment to each group. In phase II, the reader removes the interference of the non-wanted tags in all groups through one query. In phase III, the target tags in all groups are identified at once. The details of each phase are described below.

5.1. Protocol Description

Phase I: Assign a slot segment to a group. We consider the tags within a group as a whole. All operations at this phase are directed at a group, not a tag. The reader initializes a query with the parameter settings $\{f_s,R_{s1},R_{s1},\dots \}$. The reader performs a hash operation with $R_{s1}$ on all groups, i.e., $H(I{D}_s,R_{s1})$ mod $f_s$ and assigns them to a virtual frame. Those groups that are assigned to a singleton slot determine their response slot segment. Next, the reader removes the singleton slots from this frame and the groups in the singleton slot, and then performs the second hash operation. Similarly, in the second hashing, those groups that choose a singleton slot determine their response segments. Until all groups are assigned to a singleton slot, the operations are finished. Assume that a total of $h^{\prime }$ hash operations have been performed. Depending on the hashing number with which each group determines its response slot segment, the reader can construct a group segment indicator vector, denoted by $V_s$. For example, in Figure 3, the first bit in $V_s$ is 1, which means that Group 2 selected the first response segment by the first hash operation. The reader broadcasts the relevant parameters and the group segment indicator vector $V_s$ to the local tags. The local tag can determine the slot segment based on its group ID.

Phase II: Eliminate the interference of the non-wanted tags in all groups at once. First, the reader calculates the frame length required for each group to complete the tag searching with the specified reliability requirement, and takes the maximum frame length $f_m$ as the length of every group response segment. Thus, the total practical frame length of the phase II is $f_m·G$. If tags within a group responds in the n-th slot segment, the exact response slot of the tags is $[(n-1)·f_m+1,n·f_m]$. The reader performs multiple hashing operations on the wanted tags set to construct a filter vector. Subsequently, the reader initiates a query on local tag set. According to the filter vector, local tags can distinguish whether they are non-wanted tags or not. If so, they will remain quiet for the rest of the phase.

Phase III: Determine the target tags in all groups at once. First, the reader selects a group with the most wanted tags and determines the frame length $f_m^{\prime }$ for the group to complete the target tag determination. The overall frame length of this phase is $f_m^{\prime }·G$. Then, the response slot of the n-th response segment is $[(n-1)·f_m^{\prime }+1,n·f_m^{\prime }]$. The reader then assigns all the wanted tags to a singleton slot, broadcasts the parameters and the indicator vector $V_2$ to initiate a round query, and verifies whether they are the target tags through the responses of local tags.

Figure 3 illustrates the detailed process of multi-group tag searching by the G-Search protocol.

5.2. Parameter Optimization

In G-Search, we first need to assign the response slot segments to groups, and the time spent in this process is denoted by $T_{o^{\prime }}$, which is easily obtained as:

$$T_{o^{\prime }}=\left(\lceil \frac{f_s·\lceil {log}_2(h^{\prime }+1)\rceil }{96}\rceil +1\right)·T_{tag}.$$

(11)

According to the analysis in Section 4.2, it is easy to know that

$$f_s=\lceil \frac{\left|G\right|}{96}\rceil ·96.$$

(12)

In this section, a parallel approach is taken for multi-group tag searching. We use the group with the longest frame length $f_m$ as a sample for satisfying the reliability requirements. Therefore,

$$\begin{array}{cc}\hfill & (k^{*},f_g^{*})=\underset{k,f_g}{argmin}\left(\lceil \frac{f_g·\lceil lo{g}_2(l+1)\rceil }{96}\rceil ·T_{tag}\right),\hfill \\ \hfill & s.t.\left\{\begin{array}{c}k\in N^{+},f_g\in N^{+}\hfill \\ P_d\le (1-P_{req})·\frac{min(\left|W_g\right|,\left|L_g\right|)}{(\left|L_g\right|-\left|T_g\right|)}\hfill \end{array}\right.,\hfill \end{array}$$

(13)

where $N^{+}$ denotes the set of positive integers.

$$f_m=max\left(f_g\right)g\in \{1,2,\dots ,G\}.$$

(14)

$$f_m^{\prime }=max\left(\lceil \frac{\left|W_g\right|}{96}\rceil ·96\right)g\in \{1,2,\dots ,G\}.$$

(15)

Equations (14) and (15) indicate that we take the maximum frame length $f_m$ as the length of the group response segment in phase II and $f_m^{\prime }$ as the length of the group response segment in phase III. We still set l to 3 and allow that each group chooses the suitable k according to the reliability requirements.

The time spent by G-Search for the multi-group tag searching is denoted by $T_s$.

$$\begin{array}{cc}\hfill T_{s\prime }& =\left(\lceil \frac{f_s·\lceil {log}_2(h^{\prime }+1)\rceil }{96}\rceil +1\right)·T_{tag}\hfill \\ \hfill & +\left(1+\lceil \frac{f_m·\lceil lo{g}_2(l+1)\rceil }{96}\rceil ·G\right)·T_{tag}\hfill \\ \hfill & +\left(\lceil \frac{f_m^{\prime }·\lceil {log}_2(h+1)\rceil }{96}\rceil ·G+1\right)·T_{tag}+\lceil \frac{f_m^{\prime }}{96}\rceil ·G·T_{tag}.\hfill \end{array}$$

(16)

6. A-Search

G-Search provides a new approach to multi-group tag searching, which performs tag searching for all groups in parallel by assigning each group a response slot segment. To satisfy the reliability requirements, G-Search selects the group with the longest frame length as a template and uses the longest frame length to construct the whole frame. For the other groups, the frame length is actually redundant and a smaller frame length is sufficient for the reliability requirements. If each group can choose the frame length that best suits themselves, the whole frame will be shorter and the multi-group tag searching protocol will be more efficient. Therefore, we propose a new protocol called A-Search, which also has three phases. Phase I is used to assign a response slot segment to each group, phase II is used to deactivate non-wanted tags for all groups, and phase III is used to confirm the target tags for all groups. The frame lengths for each group in both phase II and phase III are adaptive. In Section 6.1, we introduce the details of the A-Search protocol.

6.1. Protocol Description

Phase I: Assign a slot segment to a group. This phase is exactly the same as the phase I of G-Search. The reader regards a group as a whole, and assigns each group to a singleton slot by performing multiple hashing operations based on the group IDs. Ultimately, the reader can assign a response slot segment to each group.

Phase II: Eliminate the interference of the non-wanted tags in all groups at once. The reader calculates the most suitable frame length $\{f_1,f_2,\dots ,f_G\}$ for each group to perform the non-wanted tags deactivation while satisfying the reliability requirement. The practical frame length in phase II is $\sum f_g$, $g\in \{1,2,\dots ,G\}$. Then, the reader constructs the filter vector $V_1$ in the wanted tag set. The reader performs a query in local tag set with parameter settings $\{f_1,f_2,\dots ,k_1,k_2,\dots ,R_1,R_2,\dots \}$ and the filter vector $V_1$ to deactivate the non-wanted tags.

Phase III: Determine the target tags in all groups at once. The reader selects the most appropriate frame length $\{f_1^{\prime },f_2^{\prime },\dots ,f_G^{\prime }\}$ for each group. The practical frame length in phase III is $\sum f_g^{\prime }$, $g\in \{1,2,\dots ,G\}$. Then, the reader assigns each wanted tag to a singleton slot by multiple hashing operations and constructs an indicator vector $V_2$. Finally, the reader broadcasts the relevant parameters, and then the local tag calculates its response time slot and replies with a response vector. The wanted tags can confirm whether it is the target tag depending on the response vectors.

Figure 4 illustrates the process of multi-group tag searching by the A-Search protocol.

6.2. Parameter Optimization

The tag searching process of A-Search is similar to G-Search, and they both use the parallel approach. However, A-Search is an improvement of G-Search in that each group can adaptively choose the frame length that best fits itself. In phase II and III of A-Search, the reader needs to send the frame length of each group to local tags in addition to the regular parameters.

We use $T_a$ to represent the time spent by A-Search for multi-group tag searching, and can be expressed as:

$$\begin{array}{cc}\hfill T_a& =\left(\lceil \frac{f_s·\lceil {log}_2(h^{\prime }+1)\rceil }{96}\rceil +1\right)·T_{tag}\hfill \\ \hfill & +\left(\lceil \frac{\sum \lceil \left(lo{g}_2(f_g+1)\right)\rceil }{96}\rceil +\lceil \frac{\sum f_g·\lceil lo{g}_2(l+1)\rceil }{96}\rceil \right)·T_{tag}\hfill \\ \hfill & +\left(\lceil \frac{\sum \lceil \left(lo{g}_2(f_g^{\prime }+1)\right)\rceil }{96}\rceil +\lceil \frac{\sum f_g^{\prime }·\lceil {log}_2(h+1)\rceil }{96}\rceil \right)·T_{tag}\hfill \\ \hfill & +\lceil \frac{\sum f_g^{\prime }}{96}\rceil ·T_{tag}.\hfill \end{array}$$

(17)

7. Performance Evaluation

In this section, we conduct extensive simulations in a large-scale multi-group RFID system to evaluate the performance of B-Search, G-Search, and A-Search in terms of execution time. To make the simulation results more convincing, we repeat the simulations with the same parameter settings 100 times and take the average value as the final results.

7.1. Simulation Setting

In our simulations, the communication parameters settings follow the specification of the EPCglobal C1G2 standard [23]. The transmission rate between the reader and the tag is asymmetric because of the physical implementation. Generally speaking, the transmission rate of tag-to-reader is 40∼460 kb/s for FM0 and the transmission rate of reader-to-tag is 5∼320 kb/s for a Miller-modulated subcarrier. In our paper, we adopt 62.5 kb/s as the tag-to-reader and reader-to-tag date transmission rate. Thus, the time taken by the reader and the tags to send 1-bit data are $0.016$ ms, denoted by $T_c$. It is well known that any two consecutive transmissions are separated by a $0.184$ ms time interval, denoted by $T_i$, whether reader-to-tag or vice versa. To sum up, we can set $T_s=0.2$ ms and $T_{id}=2.42$ ms.

7.2. Validity Verification of the Proposed Protocols

As we know, existing tag searching protocols cannot effectively solve the multi-group tag searching problem because they cannot ensure the searching results in each group satisfy the predefined reliability requirements. To demonstrate the multi-group tag searching validity of the B-Search, G-Search and A-Search, we propose a baseline protocol for comparison.

The reader can confirm whether a wanted tag is the target tag by polling it. To reduce the time spent on polling, the reader can first broadcast the group ID. Local tags immediately check whether their group ID matches the broadcast one. If so, it remains active. The reader then broadcasts the member ID of wanted tags in the group, and the active local tag checks if its own member ID is the same as the broadcast one. For each member ID, we can reserve a one-bit slot for identifying. When the local tag’s member ID are polling, the tag replies with “1”. Otherwise, the tag replies with “0”. $T_{bl}$ indicates the time taken by the baseline protocol to complete the multi-group tag searching. Simply,

$$T_{bl}=(16·T_c+T_i)·G+(80·T_c+T_i+T_s)·\sum \left|W_g\right|,g\in \{1,2,\dots ,G\}.$$

(18)

Based on Equation (18), the tag searching efficiency of the baseline protocol is only associated with the number of wanted tags in each group and the number of groups. In

Table 1. The searching time of baseline protocol, B-Search, G-Search, and A-Search.

	$\mathit{G}=21,{\mathit{W}}_{\mathit{g}}=1000$	$\mathit{G}=21,{\mathit{W}}_{\mathit{g}}=5000$	$\mathit{G}=41,{\mathit{W}}_{\mathit{g}}=1000$	$\mathit{G}=41,{\mathit{W}}_{\mathit{g}}=5000$
Baseline	34.95	174.73	68.24	341.14
B-Search	10.86	53.17	21.23	103.81
G-Search	10.71	53.00	20.90	103.46
A-Search	10.72	53.01	20.92	103.49

, we set the target tags ratio $\lambda =0.3$, the reliability requirement $P_{req}=0.9999$, the group interval $r=10$, and the number of local tags in each group $\left|L_g\right|=1000$. The table shows the searching time of baseline protocol, B-Search, G-Search, and A-Search. It is obvious that our proposed three multi-group tag searching protocol is far superior to the baseline protocol.

7.3. Simulation Results

In Figure 5, we set the target tags ratio $\lambda =0.3$ and the reliability requirement $P_{req}=0.999$. Then, we explore its impact on the time efficiency of our protocols by changing the number of local tags in each group from 1000 to 5000 by 1000 in Figure 5a,c and from 500 to 2500 by 500 in Figure 5b. It should be noted that the number of local tags in each group here refers to the average number. Taking Figure 5a as an example, we set the number of groups $G=21$, the group interval $r=10$, and the number of wanted tags in each group $\left|W_g\right|=1000$. It means that there are 21 groups in the local tag set, and the number of local tags in these groups is changing from 900 to 1100 by 10. We set the number of groups $G=41$, the group interval $r=10$ and the number of wanted tags in each group $\left|W_g\right|=500$ in Figure 5b, and set the number of groups $G=21$, the group interval $r=20$, and the number of wanted tags in each group $\left|W_g\right|=1000$ in Figure 5c. As you can see, the number of local tags for each group in Figure 5b is different from the other two figures because the group number in Figure 5b is different from the other two, and we must ensure the total number of local tags is consistent overall. This also applies to the number setting of wanted tags. We find that A-Search performs the best, followed by G-Search, and B-Search ranks third. In Figure 5a, when the number of local tags in each group $\left|L_g\right|=2000$, the time cost of B-Search, G-Search, and A-Search equals 9.63 s, 9.43 s, and 9.39 s. The time cost of A-Search is 97.47% of B-Search and 99.57% of G-Search.

In Figure 6, we set the target tag ratio $\lambda =0.3$ and the reliability requirement $P_{req}=0.999$. Then, we set the number of group $G=21$, the group interval $r=10$, and the number of local tags in each group $\left|L_g\right|=5000$ in Figure 6a. Set the number of groups $G=41$, the group interval $r=10$, and the number of local tags in each group $\left|L_g\right|=2500$ in Figure 6b. Set the number of groups $G=21$, the group interval $r=20$, and the number of local tags in each group $\left|L_g\right|=5000$ in Figure 6c. We explore its impact on the time efficiency of our protocols by changing the number of wanted tags from 1000 to 5000 by 1000 in Figure 6a,c and from 500 to 2500 by 500 in Figure 6b. Clearly, A-Search outperforms the other protocols. In Figure 6a, when the number of wanted tags $\left|W_g\right|=2000$, the time cost of B-Search and G-Search are 19.40 s and 19.72 s. The time cost of A-Search is 19.14 s, which is 98.65% of B-Search and 97.06% of G-Search. In this case, G-Search does not perform as well as B-Search. Because our method is not well suited for the situations where wanted tags are too many, and the fact that G-Search applies the longest frame length to all groups, inadvertently magnifying this disadvantage even more.

In Figure 7, we set the number of local tags in each group $\left|L_g\right|=2000$, the number of wanted tags in each group $\left|W_g\right|=1000$, and the reliability requirement $P_{req}=0.999$, while changing the target tag ratio from 0.2 to 0.8 by 0.2. Then, we set the number of groups $G=21$ and the group interval $r=10$ in Figure 7a, set the number of groups $G=41$ and the group interval $r=10$ in Figure 7b, and set the number of groups $G=21$ and the group interval $r=20$ in Figure 7c. We find that A-Search and G-Search always perform well. In Figure 7a, when the target tag ratio $\lambda =0.4$, the time cost of B-Search, G-Search, and A-Search is 9.59 s, 9.39 s, and 9.23 s. Compared with B-Search and G-Search, the time cost of A-Search reduces by 3.75% and 1.69%.

In Figure 8, we set the number of local tags in each group $\left|L_g\right|=2000$, the number of wanted tags in each group $\left|W_g\right|=1000$, and the target tag ratio $\lambda =0.3$. Then, we set the number of groups $G=21$ and the group interval $r=10$ in Figure 8a, set the number of groups $G=41$ and the group interval $r=10$ in Figure 8b, and set the number of groups $G=21$ and the group interval $r=20$ in Figure 8c. We evaluate the time efficiency of our protocols when the reliability requirement $P_{req}$ is 0.95, 0.99, 0.999, and 0.9999, respectively. We find that A-Search and G-Search both perform well, and the time efficiencies of A-Search and G-Search are almost the same. In Figure 8a, when the reliability requirement $P_{req}=0.99$, the searching time of B-Search, G-Search, and A-Search is 7.58 s, 7.38 s, and 7.39 s. The time cost of A-Search is 97.43% of B-Search and 100.11% of G-Search.

In the above two situations, the time efficiency of A-Search and G-Search are not comparable. The number of wanted tags and local tags in each group is the same, and the frame length selected by G-Search is appropriate for each group. In contrast, A-Search takes time to broadcast frame lengths for each group so that A-Search would not have the advantage.

8. Conclusions

In this paper, we have formulated the tag searching problem arising in large-scale multi-group RFID systems. With the segmented tag searching method, we propose a suite of three multi-group tag searching protocols: B-Search, G-Search, and A-Search. G-Search and A-Search innovatively adopt the parallel approach for tag searching in multiple groups, and achieve excellent performance. In our future work, we plan to study tag searching problems in the case of multiple mobile readers and multiple regions, and propose effective tag searching algorithms.