A Collecting Collision Tree Protocol for RFID Tag Identification with Capture Effect

Abstract

Multitag identification is one of the main advantages of the radio frequency identification (RFID) system. In the RFID system, the capture effect often happens in the real environment. When the capture effect occurs, the reader will not completely identify the tags in its scope. In many RFID applications, to get the real-time number of tags, the reader identifies the tags repeatedly. In these cases, the tag in the reader's scope is a staying tag or an arriving tag. The reader already stores the IDs of all staying tags, so it can just verify the existence of these tags to rapidly identify them. As a result, the reader can spend the main time in recognizing arriving tags. To cope with the capture effect and identify staying tags rapidly, this paper presents a collecting collision tree protocol for RFID tag identification with capture effect (CCT). In CCT, a collecting mechanism is adopted and a lot of staying tags can be recognized in a slot. What is more, the reader can identify all tags in its range when the capture effect happens. Finally, various analysis and simulation results show that CCT outperforms the existing algorithms significantly.

1. Introduction

Radio frequency identification (RFID) is a noncontact automatic identification technology [1], which is one of the most important technologies of the internet of things (IOT). The RFID system has been widely used in locating and tracking, warehouse management, goods inventory, and other aspects of daily lives [2, 3]. The main components of the RFID system are reader and multiple tags. When multiple tags send information to the reader simultaneously, collisions between these tags' signals will cause that the reader cannot receive the tags' data correctly. The colliding tags need to retransmit their IDs to the reader to be identified. The retransmitting will increase the reader's identification delay and waste spectrum resources. Therefore, we need to propose effective tag anticollision algorithms to solve the problem of collision between tags.

Tag anticollision algorithms of the RFID system can be classified into aloha-based [4] and tree-based algorithms [5]. The main drawback of aloha-based algorithms is that a specific tag may not be identified by the reader for a long time, which is the so-called “tag starvation” problem. Tree-based algorithms do not have the “tag starvation” problem. Tree-based algorithms continually split colliding tags into two subsets, until a subset only contains one tag. Tree-based algorithms can be further divided into binary tree (BT) [6], query tree (QT) [7], and collision tree (CT) [8]. The CT algorithm adopts a bit tracking technology, in which the reader can get the precise locations of all colliding bits. As a result, idle slots are avoided. The CT algorithm has the maximum efficiency among tree-based algorithms. This paper focuses on CT-based algorithms.

In the RFID system, when several tags send data to the reader simultaneously, among these tags, if a tag's signal strength is much larger than the other tags', the reader can still receive the tag's data correctly, which is called capture effect [9–12]. The reader will not recognize all the tags in its range when the capture effect happens. To cope with the capture effect, some algorithms, such as the generalized binary tree protocol (GBT) [11], the general query tree 1 (GQT1) and general query tree 2 (GQT2) [12], and a multiround collision tree (MRCT) [13] were proposed. These algorithms can completely identify the tags in the reader's range.

In many RFID applications, the reader identifies the tags in its scope continually. For example, in an exhibition, the organizers want to get the real-time number of visitors in each showroom. For another instance, the library manager wants to know the real-time numbers of different books in every bookshelf. Similar demands may also exist in ranch monitoring, warehouse management, and so on. In these situations, a tag in the reader's range is either a staying tag or an arriving tag. The reader should spend the main time in identifying arriving tags and recognize staying tags rapidly. For these applications, many algorithms were proposed [14–17], but these algorithms cannot work in the capture environment.

Considering the two requirements mentioned above, we present a collecting collision tree protocol for RFID tag identification with capture effect (CCT). When the capture effect happens, CCT reader can recognize all the tags in its range. If CCT reader identifies the tags in its range repeatedly, it can identify many (e.g., 32, 64, or more) staying tags in a slot by using a collecting mechanism. As a result, the reader's efficiency is improved greatly.

The rest of this paper is organized as follows. Section 2 describes related works. Section 3 depicts the details of the proposed CCT. CCT is analyzed in Section 4. Simulation results and discussions are contained in Section 5. Finally, Section 6 concludes the full text.

2. Related Works

Before introducing related works, we define two terms which are round and slot. A round represents the period from the time the reader starts to send commands to the time the reader identifies all the tags in its scope. The ith round is labeled as $T_i$ . A slot is from the start of a reader's command to the ending of tags' responding to the command. Typically, a round consists of several slots.

2.1. Bit Tracking Technology

Manchester code is widely used in the bit tracking technology. The encoding rule of the Manchester code is that bit 0 is represented by a positive transition and bit 1 is depicted by a negative transition. In the RFID system, when multiple tags transmit their IDs, which is encoded as Manchester code to the reader simultaneously, the reader can locate the positions of colliding bits. Assume that the IDs of Tag A and Tag B are 1100 and 1011, respectively. When the two tags send their IDs to the reader at the same time, the reader will receive a bit string of $1xxx$ as shown in Figure 1, where x means a colliding bit. Then, the reader can get that three bits of the received bit string are colliding bits.

Figure 1

Bit tracking technology.

2.2. Collision Tree (CT)

The bit tracking technology is used in CT. A CT reader maintains a stack Q to store ID prefixes. The initial value of Q is empty. At the beginning of a round, the reader sends a Query command without a parameter. All tags in the reader's scope send their IDs to the reader when receiving the command. If the reader detects no tag or only one tag replies, it terminates the current round. Otherwise, if the reader receives that the tags' responses are colliding, assuming the received bit string is $b_0{b}_1\cdots b_{c-1}{b}_c{b}_{c+1}\cdots b_{k-1}$ , where $b_c$ is the first colliding bit and k is the tag ID length, the reader stores two prefixes which are $b_0{b}_1\cdots b_{c-1}1$ and $b_0{b}_1\cdots b_{c-1}0$ to Q. After a slot ends, the reader checks whether Q is empty or not; if Q is empty, the reader terminates the ongoing round. On the contrary, if Q is not empty, the reader sends a Query command with parameter q which is popped from Q. When receiving the Query command with q, the tag, whose ID matches q, transmits the rest of its ID to the reader. If the tag's reply is readable, the reader stores the tag's ID to its memory. If the tags' replies are colliding, the reader stores two more prefixes to Q according to the first colliding bit. Then, the reader checks whether Q is empty or not, if Q is empty, the reader ends the current round; otherwise, if Q is not empty, the reader continues to recognize the remaining tags.

2.3. Multiround Collision Tree (MRCT)

A CT reader cannot identify all the tags in its scope when the capture effect happens. MRCT is proposed to cope with the capture effect.

MRCT includes multiple CT process. The tags hidden by the capture effect are identified in the subsequent CT process. The implementation process of MRCT is similar to CT. In MRCT, when a reader identifies a tag correctly, it sends an ACK command with the tag's ID. After receiving the ACK command, the tag whose ID matches the command parameter exits from the current round. After the completion of a CT process, MRCT reader continues to send a Query command without a parameter, and the command lets all the hidden tags reply to the reader. After MRCT reader sends a Query command without a parameter, if no tag replies to the command, the reader terminates the current round.

MRCT reader can identify all the tags in its range. However, if the reader recognizes tags repeatedly, the reader has to use the same operations to identify staying tags. To let a staying tag exit from the current round, the reader needs to transmit an ACK command. When the number of staying tags is large, the reader consumes many slots to send ACK commands. Although the reader has stored all staying tags' IDs, each staying tag retransmits its ID to the reader. As a result, the reader still spends long time in identifying staying tags.

2.4. Generalized Binary Tree Protocol (GBT)

GBT is modified from BT. GBT reader uses multiple BT process to identify the tags in its range completely. The tags hidden by the capture effect will be identified by the reader in the next BT process. GBT reader can identify all the tags in its range when the capture effect occurs. However, in the real environment, the probability of the capture effect may be small, or even 0, and in this situation, if the reader needs to identify tags repeatedly, GBT cannot recognize staying tags rapidly and staying tags will collide with arriving tags.

2.5. General Query Tree 1 (GQT1) and GQT2

GQT1 is modified from QT. The reader in GQT1 stores a stack Q which is a prefix set. The initial values of Q are $\left\{\mathrm{0,1}\right\}$ . When a round starts, the reader sends a Query command with a parameter q which is popped from Q. Then, the reader receives responses from tags; if the responses are colliding or idle, the reader implements the same operations as in QT, and if the responses are successful, the reader sends an ACK command with a parameter IID which is the received ID, and then the reader stores $q0$ and $q1$ to Q to recognize the tags hidden by capture effect. When receiving an ACK command with IID, the tag, whose ID matches the IID will quit from the current round. After sending an ACK command or receiving the tags' responses, the reader checks whether Q is empty or not; if Q is not empty, the reader continues to transmit a Query command with q which is popped from Q, and if Q is empty, the ongoing round ends.

The difference of GQT2 from GQT1 is that when the tag response is successful, the reader stores q to Q, rather than $q0$ and $q1$ .

From the identification process of GQT1 and GQT2, we can get that the reader can identify all tags in its range in the capture environment. However, when the probability of capture effect is low, there will be many idle slots in GQT1 and GQT2 and the identification delay of the reader will be increased. Meanwhile, if the reader needs to identify the tags in its range repeatedly, the reader has to recognize all tags in the same way. GQT1 and GQT2 cannot avoid the collisions between staying tags and arriving tags and cannot identify staying tags rapidly.

3. The Proposed Algorithm

3.1. The Principle of CCT

To cope with the capture effect and identify staying tags rapidly, we propose CCT. CCT reader can not only recognize all the tags in its range, but also identify staying tags quickly by using a collecting mechanism. Because of the collecting mechanism, many staying tags are identified by the reader in a slot and the collisions between staying tags and arriving tags are prevented. Thus, the data amount transmitted by tags is reduced greatly and the efficiency of the reader is improved significantly.

CCT reader uses two phases to identify all tags in its scope. In the first phase, the reader adopts the collecting mechanism to recognize staying tags. Based on the collecting operation, many (e.g., 32, 64, or more) staying tags reply to the reader in a slot. The reader can identify all staying tags contained in the slot, even though the responses of these tags are colliding with each other. In the second phase, the reader can identify all arriving tags when the capture effect happens. What is more, if the reader recognizes an arriving tag successfully, it assigns a unique TID which is larger than 0 to the arriving tag. As a result, the arriving tag will quit from the current round. In the next round, if the arriving tag still stays, it will be identified by the reader as a staying tag.

3.2. System Requirements and Assumptions

In CCT, the reader maintains a stack Q to store the prefixes of tag ID. Each tag maintains a counter TID which means temporary ID. The TID is recorded as a temporary variable, such as a register which will lose value if the tag leaves from the reader's scope. We assume that the coverage areas of any two readers are not overlapped. Thus, if a tag comes back again after it leaves from the reader's range for a while, it will be considered as an arriving tag. The value of TID is used to distinguish whether a tag is a staying tag or an arriving tag. The length of TID is 16. The TID of a staying tag is larger than 0 and the TID of an arriving tag is 0. The values of staying tags' TIDs are different from each other. If a staying tag leaves from the scope of a reader, its TID should be reset to 0 when it enters next time. CCT reader uses a two-dimensional table CQ to save the associated relationship between TIDs and IDs. The first column of CQ saves TIDs and the second column of CQ contains IDs. In the RFID applications, the reader should prepare a large memory if it needs to identify a large number of tags, even though the number of tags may be small in some cases. For simplicity and ease to process, the size of the CQ table can be static, which means that the static memory is only used to save tags' TIDs and IDs.

Besides the assumption of the reader's coverage area described above, some other assumptions adopted in the proposed CCT are as follows.

• (1)

In a slot, all tags reply to the reader simultaneously. As a result, the reader can get the locations of all colliding bits.

(2)

The wireless channel between the reader and tags is ideal. Thus, receipt errors are caused by collisions rather than channel errors.

These assumptions are common in the existing researches [8–13].

3.3. The Improvements of CCT

CCT has the following two improvements compared to MRCT.

• (1)

In CCT, if the reader identifies an arriving tag successfully, the reader sends an ACK command with RID and RTID, where RID is the received ID and RTID is used to assign a unique TID to the tag. To keep track of the existing TIDs in the CQ table, the reader should save the tag's TID and ID to CQ.

(2)

When an arriving tag is recognized by the reader, the tag's TID becomes a nonzero value, indicating that the tag becomes a staying tag, and then the tag no longer responds to the reader's command which is sent to the arriving tags.

CCT reader uses three commands to identify all the tags in its range, which are Query, ACK, and Collect. The commands Query and ACK are used to identify arriving tags and the command Collect is used to recognize staying tags. The parameters and responding conditions of these commands are described below:

• (1)

Query: the command's parameter is prefix. Only arriving tags (TID = 0) reply to the command. If the prefix is null, all the arriving tags send to the reader. Otherwise, if the prefix is not null, the arriving tag, whose ID matches the prefix, replies the rest of its ID to the reader;

(2)

ACK: the command's parameters are RID and RTID. Only arriving tags respond to the command. When receiving the command, the tag with ID = RID sets its TID to RTID. When assigning TIDs to tags, the reader should keep the continuity of tags' TIDs. For example, if there are three staying tags in the reader's scope, the TIDs of these tags are 1, 2, and 4, respectively, and then the reader should firstly assign 3 to the next arriving tag. If the TIDs of staying tags in the reader's range are already continuous, the reader assigns TID to the next arriving tag incrementally;

(3)

Collect: the command's parameters are $C1$ and $C2$ . $C1$ and $C2$ define the range of staying tags' TIDs which the reader wants to identify. The relationship of $C1$ and $C2$ is $C2\ge C1>0$ . Only staying tags (TID > 0) may reply to the command. If a staying tag's TID is in the range of $[C1,C2]$ , the tag should reply to the reader and the tag's reply format is $\underset{\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{s}}{\underbrace{0_0,0_1,\dots ,0_{i-1}}},1_i,\underset{\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{s}}{\underbrace{0_{i+1},0_{i+2},\dots ,0_{C2-C1}}}$ , where i is calculated as TID- $C1$ . For example, if a staying tag's TID is 8 and receives a Collect command with 6 and 10, the tag should reply to the reader a bit string of 00100. The reader can identify several tags by sending a Collect command. For example, after the reader sends a Collect command, if three staying tags satisfy the reply condition and the bit strings of these tags are 1000, 0100, and 0001, respectively, the reader will receive a sequence of $xx0x$ . The reader can then determine that the current slot contains three staying tags. Obviously, the reader can recognize up to $C2-C1+1$ staying tags by transmitting a Collect command.

3.4. The Procedure of CCT

The pseudocode of CCT is shown in Pseudocode 1, where (a) shows reader operations and (b) depicts tag operations.

Pseudocode 1: The pseudocode of CCT.

(a)

  ${/}^{\ast }$ Reader operations ${}^{\ast }$ /

 (1) Q = empty, $Cn$ , $C1$ = 1, $C2$ = 1, readall = 0

 (2) if   $\text{CQ}$ ! = empty  then

 (3)   $\text{MS}=\max [\text{CQ}(:,\mathrm{1})]$

 (4) else

 (5)  MS = 0

 (6) end if

 (7) while   $C2$ ≤ $\text{MS}$   do

 (8)  if   $C2$ == 1  then

 (9)    $C1$ = 1

 (10)  else

 (11)    $C1=C2+1$

 (12)  end if

 (13)  if   $C2+Cn$ ≤ $\text{MS}$   then

 (14)  if   $C2$ == 1  then

 (15)    $C2$ = $C2+Cn-1$

 (16)  else

 (17)    $C2=C2+Cn$

 (18)  end if

 (19)  else

 (20)   $C2$ = MS

 (21)  end if

 (22)  Transmit a Collect command with $C1$ and $C2$

 (23)  Receive tag responses

 (24)  if no tag reply  then

 (25)  Delete all the TID which belong to $[C1,C2]$ and the associated IDs from $\text{CQ}$

 (26)  else

 (27)  Delete the TID whose reply bit is 0 and the associated ID from $\text{CQ}$

 (28)  end if

 (29)  if   $C2$ == MS  then

 (30)   $C2$ = MS + 1

 (31)  end if

 (32) end while

 (33) while readall == 0  do

 (34)  prefix = pop(Q)

 (35)  Transmit a Query with prefix

 (36)  Receive tag responses

 (37)  if no tag reply && prefix == null  then

 (38)  readall = 1

 (39)  else if tag reply collision  then

 (40)    Save two prefix to Q

 (41)    else if tag reply readable  then

 (42)      Generate a unique RTID

 (43)      Set RID as the received ID

 (44)      Save the RTID and ID to $\text{CQ}$

 (45)      Transmit an ACK with RID and RTID

 (46)     end if

 (47)   end if

 (48)  end if

 (49) end while

(b)

  ${/}^{\ast }$ Tag operations ${}^{\ast }$ /

 (1) if enter the scope of the reader  then

 (2)  TID = 0

 (3) end if

 (4) Receive a command s from the reader

 (5) if  s is a Collect with $C1$ and $C2$   then

 (6)  if TID is in [ $C1$ , $C2$ ]  then

 (7)   Reply a bit string

 (8)  end if

 (9) end if

 (10) if  s is an ACK with RID and RTID  then                

 (11)  if ID == RID  then                           

 (12)   TID = RTID                             

 (13)  end if                                 

 (14) end if                                 

 (15) if  s is a Query with prefix  then                   

 (16)  if TID == 0  then                           

 (17)   if ID match with prefix $\hspace{0.17em}|\hspace{0.17em}\hspace{0.17em}|\hspace{0.17em}$ prefix is null  then          

 (18)    Transmit the remaining ID                  

 (19)   end if                               

 (20) end if                                

 (21) end if                                 

3.4.1. Reader Operations

Before the current round begins, the reader initializes parameters as shown in lines 1–6 of Pseudocode 1(a), where $Cn$ represents the number of staying tags a reader can identify by sending a Collect command. The typical value of $Cn$ is 64. The parameter readall is used to indicate whether all arriving tags are identified or not, when readall = 1, the reader can determine that arriving tags are recognized completely. MS represents the maximum TID in CQ. If CQ is empty, MS is set to 0.

The identification process of the reader is divided into two phases. The first phase identifies staying tags and arriving tags are recognized in the second phase.

To identify staying tags, the reader transmits a Collect command with $C1$ and $C2$ , where the values of $C1$ and $C2$ are determined by the relationship between $C2+Cn$ and MS as shown in lines 8–21 of Pseudocode 1(a). After the reader sends a Collect command, it receives tags' response. If no tag replies to the command, indicating that all the $C2-C1+1$ staying tags have left, the reader should delete all the TIDs which are in the range of $[C1,C2]$ and their associated IDs from CQ. If the reader can receive tags' responses, it checks whether the received sequence contains bit 0 or not. If the sequence contains bit 0, which means that the corresponding staying tag has left, the reader should delete the tag's TID and ID from CQ as shown in lines 24–28 of Pseudocode 1(a). For example, if the reader receives a sequence of $x0x$ , it should delete the TID which equals $C1+1$ and the associated ID from CQ. After transmitting a Collect command, the reader determines the relationship between $C2$ and MS. If $C2$ equals MS, indicating that all staying tags are identified, the reader sets $C2$ to MS + 1 as shown in lines 29–31 of Pseudocode 1(a).

Then, the reader ends the first phase and starts the second phase. In the second phase, the reader pops a prefix from Q and sends a Query command with the prefix. When popping a prefix from Q, the reader sets prefix to null if Q is empty.

After sending a Query command, the reader receives tags' responses. If no tag replies, the reader checks whether the prefix is null or not. If the prefix is null, the reader sets readall to 1 as shown in lines 37-38 of Pseudocode 1(a). If the tags' responses are colliding, the reader stores two prefixes to Q according to the first colliding bit as shown in lines 39-40 of Pseudocode 1(a). If the tags' responses are readable, the reader sets RID as the received ID and generates a unique RTID which should keep the continuity of TIDs, and then the reader stores the RTID and RID to CQ and sends an ACK command with the RTID and RID as shown in lines 42–45 of Pseudocode 1(a). After receiving tags' responses or sending an ACK command, the reader checks whether readall is 1 or not. If readall is not 1, the reader continues to pop a prefix from Q and send a Query command with the prefix; otherwise, if readall is 1, the reader terminates the current round.

3.4.2. Explanations of CQ Table Management

From the procedure of the reader operations, we can get that the management of CQ table is complicated. We add some explanations here.

In the first phase of reader operations, the reader should delete the leaving tags' TIDs and IDs from CQ. However, in the second phase, the reader should save the arriving tags' TIDs and IDs to CQ. Besides the deleting and saving operations, as the reader should keep the continuity of TIDs, the reader needs to search for all TIDs. Therefore, the operations about CQ are deleting, saving, and searching.

In the RFID system, the reader generally has enough storage and computation ability. Thus, the operations of storing the new TIDs and being sure of not having conflicts, searching for TIDs, and updating the table are acceptable for the reader. What is more, in the proposed CCT, the tags would be waiting for the reader's command after they replied to the reader. Based on this mechanism, the reader also has enough time to complete these operations.

3.4.3. Tag Operations

If the tag first enters the reader's scope, it sets its TID to 0 as shown in lines 1–3 of Pseudocode 1(b). When the tag receives a Collect command with $C1$ and $C2$ , the tag judges whether its TID is in the range of $[C1,C2]$ or not, if its TID is in the range of $[C1,C2]$ , the tag generates a bit string according to the values of TID, $C1$ , and $C2$ and then sends the bit string to the reader. Otherwise, if its TID is not in the range of $[C1,C2]$ , the tag does not respond as shown in lines 5–9 of Pseudocode 1(b). When the tag receives an ACK command with RID and RTID, the tag checks whether its ID equals the RID or not, if equals, the tag sets its TID to the RTID, on the contrary, the tag does not respond as shown in lines 10–14 of Pseudocode 1(b). When a tag receives a Query command with prefix, the tag judges whether its TID is 0 or not; if the tag's TID is 0, then, if the prefix is null or the tag's ID matches the prefix, the tag replies the rest of its ID to the reader as shown in lines 15–21 of Pseudocode 1(b).

4. Performance Analysis

The identification delay of a tag anticollision algorithm is defined as the number of slots a reader consumes to recognize all the tags in its range. In [13], the identification delay of MRCT is analyzed. However, the slots that a reader transmits ACK commands are not considered; for example, if MRCT reader uses r times CT process to identify n tags, then the reader's identification delay is as follows:

$$\begin{array}{cc}& D_{\text{MRCT}}\left(n\right)={\displaystyle \sum }_{i=\mathrm{1}}^r{N}_i={\displaystyle \sum }_{i=\mathrm{1}}^{r-\mathrm{1}}\left(\mathrm{2}{k}_i-\mathrm{1}\right)+\mathrm{1}=\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{r-\mathrm{1}}{k}_i-\left(r-\mathrm{1}\right)+\mathrm{1}=\mathrm{2}n-r+\mathrm{2},\end{array}$$

(1)

where $k_i$ represents the number of tags the reader identifies in the ith CT process.

According to the result in (1), if the capture effect does not occur, MRCT reader needs two CT process to complete the identification; that is, $r=2$ . Substituting r into (1), we can get that $D_{\mathrm{M}\mathrm{R}\mathrm{C}\mathrm{T}}\left(n\right)=2n$ . As $D_{\mathrm{C}\mathrm{T}}\left(n\right)=2n-\mathrm{1}$ , and MRCT reader only uses one more slot than a CT reader, which is obviously wrong. When identifying a tag, MRCT reader must send an ACK command to let the tag quit from the current round. The parameter of an ACK command is the tag's ID. If the tag ID length is long, the sending of an ACK command also takes a long time. Thus, we take it as an idle slot when a reader sends an ACK command. A more accurate identification delay of MRCT is as follows:

$$\begin{array}{cc}& D_{\text{MRCT}}\left(n\right)={\displaystyle \sum }_{i=\mathrm{1}}^r{N}_i+n=\mathrm{3}n-r+\mathrm{2}.\end{array}$$

(2)

When the capture effect does not occur, the identification delay of MRCT is $D_{\mathrm{M}\mathrm{R}\mathrm{C}\mathrm{T}}\left(n\right)=\mathrm{3}n$ , which is significantly greater than CT's.

The capture effect can reduce the identification delay of a reader. When the capture effect does not occur and the reader identifies tag repeatedly, we analyze the identification delay of CCT and MRCT. Assume that the number of tags in $T_i$ is n, and the numbers of arriving tags and leaving tags in $T_{i+\mathrm{1}}$ are α and β, respectively. Let the identification delay of CCT and MRCT in $T_{i+\mathrm{1}}$ be $D_{\mathrm{C}\mathrm{C}\mathrm{T}}\left(T_{i+1}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)$ and $D_{\mathrm{M}\mathrm{R}\mathrm{C}\mathrm{T}}\left(T_{i+1}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)$ , respectively. For MRCT, we can get that

$$\begin{array}{cc}& D_{\text{MRCT}}\left(T_{i+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)=\mathrm{3}\left(\alpha +n-\beta \right).\end{array}$$

(3)

For CCT, the reader uses two phases to identify all tags. In the first phase, the reader can identify $Cn$ staying tags by sending a Collect command. The identification delay of CCT is calculated as follows:

$$\begin{array}{cc}& D_{\text{CCT}}\left(T_{i+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)=⌈\frac{n}{Cn}⌉+\mathrm{3}\alpha ,\end{array}$$

(4)

where $\lceil \hspace{0.17em}\rceil$ means the ceiling function.

Next, we analyze the data transmission amount of CCT and MRCT, which are labeled as $B_{\mathrm{C}\mathrm{C}\mathrm{T}}\left(T_{i+1}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)$ and $B_{\mathrm{M}\mathrm{R}\mathrm{C}\mathrm{T}}\left(T_{i+1}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)$ , respectively. The data transmission amount includes all the interaction data between the reader and tags. In CCT, the length of TID is labeled as $L_{\mathrm{T}\mathrm{I}\mathrm{D}}$ . We do not consider the reader command code, the preamble of reader commands, and the preamble of tag responses. When the capture effect does not occur, the data transmission amount of MRCT is as follows:

$$\begin{array}{cc}& B_{\text{MRCT}}\left(T_{i+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)=\left[\mathrm{2}\left(\alpha +n-\beta \right)-\mathrm{1}\right]·L_{\text{ID}}+\left(\alpha +n-\beta \right)·L_{\text{ID}},\end{array}$$

(5)

where $L_{\mathrm{I}\mathrm{D}}$ is the tag ID length, $\left[2\left(\alpha +n-\beta \right)-\mathrm{1}\right]·L_{\mathrm{I}\mathrm{D}}$ represents the amount of data transmission between the reader and tags, and $\left(\alpha +n-\beta \right)·L_{\mathrm{I}\mathrm{D}}$ is the data amount of ACK commands.

For CCT, the data transmission amount is calculated as follows:

$$\begin{array}{cc}& B_{\text{CCT}}\left(T_{i+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{T}_i\right)=\mathrm{2}·⌈\frac{n}{Cn}⌉·L_{\text{TID}}+n+\left(\mathrm{2}\alpha -\mathrm{1}\right)·L_{\text{ID}}+\alpha ·\left(L_{\text{ID}}+L_{\text{TID}}\right),\end{array}$$

(6)

where $2·⌈n/Cn⌉·L_{\mathrm{T}\mathrm{I}\mathrm{D}}$ and n are the data amount transmitted by the reader and tags in the first phase, respectively, $\left(2\alpha -1\right)·L_{\mathrm{I}\mathrm{D}}$ represents the amount of data transmission between the reader and tags in the second phase, and $\alpha ·\left(L_{\mathrm{I}\mathrm{D}}+L_{\mathrm{T}\mathrm{I}\mathrm{D}}\right)$ is the data amount of ACK commands.

5. Simulation Results

In this section, we simulate the performance of CCT in $T_{i+\mathrm{1}}$ by comparing it with MRCT, GBT, GQT1, and GQT2. Let the probability of capture effect be cap. We assume that cap is constant and independent of the number of tags. The assumption is reasonable and has been used in many relevant studies [9–13]. The following three metrics are considered to evaluate the performance of algorithms:

• (1)

identification delay: this metric means the total number of slots used by a reader to identify all tags, which is the most important performance indicator;

(2)

number of collision slots: a collision slot contains a reader command and tag responses, but the reader cannot recognize any tag in the slot. Thus, high-performance anticollision algorithms should reduce the number of collision slots;

(3)

data transmission amount: in the identification process, the data transmission between the reader and tags takes up the most part of the recognition time, so the data transmission amount is also an important factor that affects an anticollision algorithm's performance.

When a reader identifies tags repeatedly, we analyze the impact of staying tags' number and arriving tags' number on the performance of CCT, MRCT, GBT, GQT1, and GQT2. We define the staying ratio $r_s$ and arriving ratio $r_a$ here. If the total number of tags in the simulation environment is N, the number of tags in $T_i$ is $\left|T_i\right|$ . In $T_{i+\mathrm{1}}$ , $r_s$ is defined as the ratio of staying tags' number over $\left|T_i\right|$ and $r_a$ is defined as the ratio of arriving tags' number over $N-\left|T_i\right|$ . Thus, the number of tags that the reader should identify in $T_{i+\mathrm{1}}$ is $r_s·\left|T_i\right|+r_a·\left(N-\left|T_i\right|\right)$ .

In a practical RFID system, the probability of the capture effect cap is typically low. Therefore, cap is set to 0.2 in all the simulations. The tag ID length is set to 96, which is the most commonly used in practice. We repeat every simulation 300 times and get the average values.

5.1. Impact of Staying Tags

Table 1 shows the simulation parameter settings. The identification delay, numbers of collision slots, and data transmission amount of these algorithms are shown in Figures 2, 3, and 4, respectively.

Table 1

Simulation parameter settings.

Parameter	N	$$\left|T_i\right|$$	$$r_s$$	$$r_a$$	cap	$Cn{}^{\ast }$
Value	200	100	0~1	0.5	0.2	64

${}^{\ast }Cn$ is only applied to CCT.

Figure 2

The impact of $r_s$ on the identification delay.

Figure 3

Impact of $r_s$ on the number of collision slots.

Figure 4

Impact of $r_s$ on the data transmission amount.

Figure 2 depicts the impact of $r_s$ on the 5 algorithms' identification delay. We can obtain from the figure that the identification delay of CCT is less than the other algorithms' when $r_s>0$ . In particular, the advantage of CCT will be more apparent when the number of staying tags increases. The reason for this phenomenon is as follows. Firstly, CCT is a blocking method, which means that the collisions between staying tags and arriving tags are prevented. Secondly, CCT reader only consumes $⌈\left|T_i\right|/Cn⌉=⌈\mathrm{100}/64⌉=2$ slots to identify all staying tags when the staying tags' number is increasing. We can see from Figure 2 that the identification delay of CCT is larger than GBT when $r_s=0$ . The reason for this phenomenon is that, although a collecting mechanism is adopted in CCT, CCT reader needs to send an ACK command to let every arriving tag quit from the current round. As a result, CCT reader will consume more slots than GBT reader when all the tags in the reader's scope are arriving tags ( $r_s=0$ ). Because GQT1 reader splits every successful slot into two slots and GQT2 reader retransmits every successful slot, there will be many idle slots in GQT1 or GQT2 reader. Thus, the identification delay of GQT1 or GQT2 is more than the other algorithms' as shown in Figure 2. The bit tracking technology is used in MRCT, but MRCT reader needs to send an ACK command to let every tag exit from the ongoing round. Therefore, the identification delay of MRCT is longer than GBT's.

Figure 3 describes the effects of $r_s$ on the number of collision slots. We can see from this figure that CCT, GQT1, and MRCT have similar number of collision slots when all staying tags leave ( $r_s=0$ ). This is because CCT has a similar manner as MRCT to identify arriving tags. CCT reader assigns a unique TID to each arriving tag in the identification process, but this operation does not affect the number of collision slots. The bit tracking technology is not adopted in GQT1, but GQT1 reader splits every successful slot into two slots, which will decrease the number of collision slots caused by the hidden tags (the tags hidden by the capture effect). Thus, GQT1 and MRCT have similar number of collision slots when $r_s<0.8$ . However, the effect of the bit tracking technology will be more obvious when $r_s\ge 0.8$ , so the number of collision slots of MRCT is less than GQT1 in this case. As the collisions between staying tags and arriving tags are suppressed in CCT, the number of collision slots of CCT is significantly less than the other methods. GQT2 reader only retransmits every successful slot, so GQT2's number of collision slots is more than GQT1. GBT reader identifies all hidden tags in the reserved slot, so the number of collision slots of GBT is the most among all methods.

Figure 4 shows the changes of these algorithms' data transmission amount as $r_s$ varies. We can get from this figure that CCT has less amount of data transmission than the other methods when $r_s\ge 0.3$ . However, the amount of data transmission of CCT is more than GQT1, GQT2, and GBT when $r_s<0.3$ . The reason is that CCT reader needs to send an ACK command to let every arriving tag quit from the current round. The parameters of ACK command will increase the data transmission amount of the reader. We can also see from this figure that MRCT has the most data transmission amount when $r_s>0$ . There are two reasons for this phenomenon. Firstly, collisions of staying tags and collisions between staying tags and arriving tags will increase the reader and tags' data transmission. Secondly, MRCT reader must send ACK commands to let all tags quit from the ongoing round. In GBT, all hidden tags are identified in a slot and these tags will collide with each other. As a result, the data transmission amount of GBT is more than GQT1 and GQT2. Because the number of collision slots of GQT1 is less than GQT2, the data transmission amount of GQT1 is also less than GQT2 as shown in Figure 4.

5.2. Impact of Arriving Tags

When we evaluate the effects of $r_a$ on the performance of CCT, MRCT, GBT, GQT1, and GQT2, Table 2 depicts the simulation parameter settings. The simulation results are shown in Figures 5, 6, and 7, respectively.

Table 2

Simulation parameter settings.

Parameter	N	$$\left|T_i\right|$$	$$r_s$$	$$r_a$$	cap	$$Cn$$
Values	200	100	0.5	0~1	0.2	64

Figure 5

The impact of $r_a$ on the identification delay.

Figure 6

Impact of $r_a$ on the number of collision slots.

Figure 7

Impact of $r_a$ on the data transmission amount.

Figure 5 shows the impact of $r_a$ on the identification delay of these algorithms. We can obtain from this figure that the identification delay of CCT is less than the other 4 methods among all $r_a$ values. This phenomenon indicates that the collecting mechanism can greatly improve the performance of CCT. Since the collecting mechanism is adopted in CCT, CCT reader uses three slots to identify all tags in its range when $r_a=0$ , in which two slots are used to identify staying tags and one slot is used to identify arriving tags. Contrarily, the other 4 algorithms still consume more than 100 slots to recognize all staying tags when $r_a=0$ . In the other 4 algorithms, GBT reader does not need to send an ACK command to let every arriving tag quit from the current round and does not need to split every successful slot or retransmit every successful slot, so the identification delay of GBT is less than MRCT, GQT1, and GQT2. MRCT reader sends an ACK command to let every arriving tag exit from the current round, but it uses the bit tracking technology to reduce the number of idle slots. Therefore, MRCT has less identification delay than GQT1 and GQT2. GQT1 splits every successful slot into two slots, so GQT1's identification delay is the largest.

Figure 6 shows these algorithms' numbers of collision slots when $r_a$ varies. The simulation results in Figure 6 show that CCT has less number of collision slots than the other algorithms among all $r_a$ values. Particularly, when $r_a=0$ , that is, all tags in the reader's scope are staying tags, CCT does not include any collision slots, and although staying tags' responses may be colliding, the reader can still identify all staying tags in the slot. The bit tracking technology can be used by MRCT reader to reduce the number of collision slots. GQT1 reader can also reduce the number of collision slots by dividing every successful slot into two slots. Thus, MRCT and GQT1 have similar number of collision slots. GQT2 only retransmits every successful slot and the probability of collision of hidden tags in GQT2 is higher than GQT1, so GQT2 has more number of collision slots than GQT1 and MRCT. GBT reader identifies all hidden tags in a slot, so GBT has the most number of collision slots.

Figure 7 illustrates the data transmission amount of these algorithms when $r_a$ increases. We can get that CCT's data amount is less than the other methods when $r_a<0.8$ . However, the data transmission amount of CCT may be more than GQT1 or GQT2 when $r_a\ge 0.8$ . The reason is that CCT reader needs to send many ACK commands to let the arriving tags quit from the ongoing round. The parameters of the ACK command are RID and RTID, which will increase the data transmission amount of the reader. GBT reader recognizes all hidden tags in a slot, so the number of collision slots is increased in GBT. As a result, the data transmission amount of GBT is more than GQT1 and GQT2. MRCT reader adopts the bit tracking technology to reduce the number of idle and collision slots, but it needs to send many ACK commands to let all staying and arriving tags quit from the current round. Thus, the data transmission amount of MRCT is more than the other algorithms.

6. Conclusion

Capture effect is an inevitable phenomenon in the RFID system. When a reader identifies the tags in its scope repeatedly, it should recognize staying tags rapidly and spend the main time in identifying arriving tags. Based on these demands, this paper presents a collecting collision tree protocol for RFID tag identification with capture effect (CCT). Compared to the existing algorithms, CCT has the following advantages. $(1)$ Collisions of staying tags are prevented. $(2)$ Collisions between staying tags and arriving tags are avoided. $(3)$ Many staying tags can be identified in a slot. Analysis and extensive simulation results show that CCT does significantly better than the existing MRCT, GBT, GQT1, and GQT2 in terms of identification delay, number of collision slots, and data transmission amount.