A Novel Hybrid Anticollision Algorithm for RFID System Based on Grouped Dynamic Framed Recognition and Binary Tree Recursive Process

Abstract

Recently, RFID technology has come into end-user applications for monitoring, tracking, and so forth. In RFID system, a reader identifies a set of tags over a shared wireless channel. When multiple tags communicate with the same reader simultaneously, all packages will be lost and no tag can be recognized, which is known as tag collision. Tag collision is a significantly important issue for fast tag identification. We firstly make a thorough analysis among a variety of traditional RFID anticollision algorithms. Then a novel hybrid anticollision algorithm called T-GDFSA is proposed. Tags are assigned to different groups based on the initial tag estimation and then experience several dynamic read frames for identification. When a collision occurs in current slot, a tree-based recursive process will be deployed immediately. T-GDFSA combines the advantages of ALOHA-based and tree-based together and acquires higher system throughput by reducing unnecessary idle and collision slots and lower communication complexity by decreasing the data transmitted, which makes it identify tags faster with less power consumption. Simulations show that the theoretical values match well the simulation results. Moreover, T-GDFSA also has a good tolerance for the inaccuracy of initial tag estimation and the length variation of tag's ID.

1. Introduction

In the recent decades, Radio Frequency Identification (RFID) has become one of the most commonly used technologies in our daily life. RFID technology is similar to the technologies of barcodes and magnetic strips, but, in addition, it has the capability of identifying objects uniquely and even without requiring direct line of sight. It is nowadays getting more prevalent in daily applications, such as electronic toll collection, public transport, access control and security, and airport luggage position tracking [1, 2]. A basic RFID system is composed of a reader and a set of tags. The reader inquiries tags that are able to communicate on the wireless channel, returning their IDs. Tags are typically passive devices, which answer to reader's query by backscattering the received signal [3, 4]. However, because of all readers and tags sharing the same communication channel, when more than one reader tries to transmit to the same tag or more than one tag tries to communicate with the same reader simultaneously, all their packages will be lost. This phenomenon is called RFID system collision, which leads to long identification time, low system efficiency, and high power consumption [5, 6]. As illustrated in Figure 1, there are two different categories of collisions in RFID system: (1) reader collision and (2) tag collision. Reader collision happens when multiple readers coexisting in the same area interfere with each other, and can be overcome by the coordination strategy among readers. Tag collision occurs among tags simultaneously transmitting to the same reader and may be more difficult to solve because of constraints of energy supply and computing complexity on tags with low functionality. Since tag collision is considered as a key problem affecting the universal adoption of the RFID system, in this paper, we primarily focus on tag collision in single reader scenarios.

Figure 1

(a) Reader collision in RFID system. (b) Tag collision in RFID system.

In order to avoid tag collision, many tag anticollision algorithms have been proposed so far, which can be classified into two categories, ALOHA-based probabilistic anticollision algorithms [7–10] and tree-based deterministic anticollision algorithms [11–13]. ALOHA-based algorithms decrease the probability of collision by randomly scheduling the response time of tags. In those algorithms, identification time is slotted and time slots form up read frames. Frame size varies over time and is broadcast by the reader to all tags at the beginning of each read frame. When receiving frame size, tags select one time slot from current read frame randomly and only respond the reader when the selected time slot comes. Colliding tags are scheduled into the next read frame to be slotted and identified, until there are no tags left. The main representatives are DFSA [8, 9] and EDFSA [10], both of which need to estimate the initial tag population to set the proper read frame size to optimize performance. However, when the number of tags becomes much larger compared with the frame size, the performance deteriorates seriously. A detailed study of these two algorithms is presented in Section 2. On the other hand, tree-based algorithms proceed with the identification process represented as a tree where the root responds a set of tags to be identified. The algorithms periodically query a subset of tags which match the given query property, and continuously split a set of tags into two subsets until each set has only one tag. Although the identification time may be longer than that of ALOHA-based algorithms, they are deterministic which can avoid that a specific tag may not be identified all the time, leading to the so-called “tag starvation problem.” The main representatives are BS [11], QT [12], and QTI [12]. Unfortunately, there are many distinct disadvantages in BS, QT, and QTI. A great number of colliding subsets exist in BS, while performance of QT and QTI is very sensitive to the distribution of tag's ID. A more detailed description is shown in Section 2.

Furthermore, a good tag anticollision algorithm for RFID passive tags should have the following characteristics. Firstly, a reader must identify all tags existing in its covering range, as tag starvation problem may cause failure of tracking and positioning objects. Second, system throughput should be high enough to ensure tags are recognized promptly, which is of great importance for mobile tag identification. Finally, communication complexity ought to be low, since passive tags supplement power supply from the reader's electromagnetic wave, which causes the available power for tags being very limited. On the other hand, low communication complexity is also very useful for the RFID applications where large scale mobile readers are deployed.

Based on the analysis hereinbefore, we propose a novel hybrid anticollision algorithm to improve the performance of RFID tag identification. The new algorithm, called Grouped Dynamic Framed Recognition and Binary Tree Recursive Process (T-GDFSA), generally identifies tags by grouped dynamic frames and calls binary tree recursive process to solve each colliding slot. As T-GDFSA combines ALOHA-based and tree-based anticollision together, it avoids the waste of idle slots in the late identification stage in ALOHA-based and colliding slots in the early identification stage in tree-based. Also because of the combination, the communications between the reader and tags become reduced which means less power is consumed. According to the later simulations in Section 4, T-GDFSA acquires higher system throughput by reducing unnecessary idle and collision time slots and lower communication complexity by decreasing the data transmitted between the reader and tags, which overwhelm other main anticollisions and make it easier to be realized in the end-user applications.

The remainder of this paper is organized as follows. In Section 2, a variety of ALOHA-based and tree-based tag anticollision algorithms are observed specifically. In Section 3, the main concept and description of T-GDFSA are present in detail. In Section 4, evaluation of time complexity and communication complexity of T-GDFSA are proposed, respectively. In Section 5, performance simulations between T-GDFSA and other anticollision algorithms are shown via Matlab. Lastly, Section 6 gives conclusion.

2. RFID Tag Anticollision Algorithms

In this section, we review the main representatives of ALOHA-based and tree-based tag anticollision algorithms for RFID system. The major metrics observed include time complexity and communication complexity. We analyze time complexity by the identification time for recognizing a set of tags, expressed by T, and study communication complexity by the total bits sent by the reader and the average bits sent by single tag for the identification, expressed by ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ and ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ , respectively.

2.1. Dynamic Framed Slotted ALOHA (DFSA)

DFSA is an ALOHA-based algorithm which can adjust the read frame size dynamically according to the estimation of tag population. The identification process is made of several read frames, which is slotted into intervals of time, called time slot, whose duration is equal to the tag's ID transmission time. Before the initialization of the first read frame, the reader estimates the unidentified tag population n and sets the read frame size L. Tags randomly select one time slot in the range of $[1,L]$ and only respond the reader when the selected slot comes. As the proper frame size is decided in advance, DFSA decreases the potential collision probability to a great extent. The population of unidentified tags is estimated in the following way. Let $N_c$ be the number of colliding time slots; let $N_s$ be the number of time slots with single tag which can be identified successfully and let $C_{\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}}$ be the ratio of $N_c$ and n which can be calculated by (1). When the current read frame is finished, the population of unidentified tags varies to $N_c/C_{\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}}-N_s$ , which is set to be the new size of the next read frame to maintain an optimal system throughput:

$$\begin{array}{cc}& C_{\text{ratio}}=\mathrm{1}-{\left(\mathrm{1}-\frac{\mathrm{1}}{L}\right)}^n·\left(\mathrm{1}+\frac{n}{L-\mathrm{1}}\right).\end{array}$$

(1)

If we define $T_{\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{t}}$ as the duration of time slot, $L_{\mathrm{i}\mathrm{n}\mathrm{i}}$ as the initial frame size, L as the actual frame size after initial frame, $P_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}}(k)$ as the possibility of successful identification for a tag after k times attempts, $Q{\mathrm{R}\mathrm{e}\mathrm{p}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ as the symbol length of slot interval, $\mathrm{A}\mathrm{C}{\mathrm{K}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ as the symbol length of acknowledgment sent by the reader after receiving tag's ID, and ${\mathrm{I}\mathrm{D}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ as the length of tag's ID, the major metrics of DFSA can be described as follows:

$$\begin{array}{ll}T& =T_{\text{slot}}·\left(L_{\text{ini}}+L·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)\right),\\ {\text{Bits}}_R& =L_{\text{bits}}·\left({\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)+\mathrm{1}\right)+Q{\text{Rep}}_{\text{bits}}·L\\ & ·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)+n·{\text{ACK}}_{\text{bits}},\\ {\text{Bits}}_T& ={\text{ID}}_{\text{bits}}·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right).\end{array}$$

(2)

However, when tag population is large, the performance of DFSA deteriorates heavily. This is because the size of memory recording the selected slot in tags is limited and cannot keep pace with the increase of tag population, which makes the optimal condition that the frame size is set equal to the tag population not satisfied.

2.2. Enhanced Dynamic Framed Slotted ALOHA (EDFSA)

On the basis of DFSA, in order to enhance the system performance when tag population is large, EDFSA introduces the grouping strategy that it randomly splits tags into different groups according to the maximal frame size and the estimated number of unread tags. Only the tags associated with one of the groups are queried in the following read frames; then the identifications for tags in other groups are followed sequentially. In fact, the grouped identification is more like a combination of several DFSA processes. Chebysev's inequality is used in the end of each read frame to estimate the number of tags left, which is used to adjust the number of groups and frame size for the incoming read frames.

The grouping and frame sizing strategy is represented in Table 1, where the group number and frame size are adjusted in the way of doubling or halving, which can be easily realized in practical applications by the operation of left shifting or right shifting the group register.

Table 1

The strategy of grouping and frame sizing.

Tag populationn	Frame sizeL	Group sizeG	Tag populationn	Frame sizeL	Group sizeG
⋯	⋯	⋯	177–354	256	1
6–11	8	1	355–707	256	2
12–19	16	1	708–1416	256	4
20–40	32	1	1417–2831	256	8
41–81	64	1	⋯	⋯	⋯
82–176	128	1

If we define the same notations as given in DFSA above, the major metrics of EDFSA can be derived as follows:

$$\begin{array}{ll}T& =T_{\text{slot}}·\left(G_{\text{ini}}·L_{\text{ini}}+G·L·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)\right),\\ {\text{Bits}}_R& =G_{\text{bits}}·L_{\text{bits}}·\left({\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)+\mathrm{1}\right)+Q{\text{Rep}}_{\text{bits}}·G\\ & ·L·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right)+n·{\text{ACK}}_{\text{bits}},\\ {\text{Bits}}_T& ={\text{ID}}_{\text{bits}}·{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }k{P}_{\text{succ}}\left(k\right).\end{array}$$

(3)

2.3. Binary Tree Algorithm (BS)

BS and Query Tree (QT) are both tree-based algorithms, in which the reader iteratively queries a subset of tags matching a given property until all tags are identified. They differ in the way of querying tags: according to a binary random number in BS and a query prefix in QT. In BS, the reader recognizes tags in the time interval called read cycle. Colliding tags are split into two subsets recursively until just one tag is allocated in every subset. The tag has a counter initialized to 0 in the very beginning. Only tags with counter value equal to 0 can respond the reader query in current read cycle, and other tags keep silent and wait for their counters decreasing to 0. Tags modify the value of counter depending on the result of current identification. If a collision happens, colliding tags add a 1-bit binary value randomly to their counters, which are split into two subsets with the counter at 0 and the counter at 1, respectively. Other tags not involved in the collision increase their counters by 1 to maintain their former identifying order unchanged. In case of identifying successfully or no response, all tags unread decrease their counters by 1, and tags with counter at 1 respond the reader in the next read cycle.

If we define $T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ as the duration of a read cycle, $⌈{\log }_{\mathrm{2}}n⌉$ as the minimal integer not less than ${\log }_{\mathrm{2}}n$ , $C_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ as the length of query command, and other parameters as the same notations given in DFSA above, the major metrics of BS can be expressed as follows:

$$\begin{array}{l}T\\ =T_{\mathrm{cycle}}\\ ·\left(\mathrm{1}+\mathrm{2}·{\displaystyle \sum }_{k=\mathrm{0}}^{\infty }\left\{{\mathrm{2}}^k-\left({\mathrm{2}}^k+n-\mathrm{1}\right)·{\left(\mathrm{1}-{\mathrm{2}}^{-k}\right)}^{n-\mathrm{1}}\right\}\right),\end{array}$$

(4)

$$\begin{array}{l}{\text{Bits}}_R\\ =C_{\text{bits}}\\ ·\left(\mathrm{1}+\mathrm{2}·{\displaystyle \sum }_{k=\mathrm{0}}^{\infty }\left\{{\mathrm{2}}^k-\left({\mathrm{2}}^k+n-\mathrm{1}\right)·{\left(\mathrm{1}-{\mathrm{2}}^{-k}\right)}^{n-\mathrm{1}}\right\}\right),\end{array}$$

(5)

$$\begin{array}{l}{\text{Bits}}_T={\text{ID}}_{\text{bits}}·{\log }_{\mathrm{2}}n.\end{array}$$

(6)

The expressions (4) and (5) are general equations when k, collision times, that is, the depth of current node (read cycle) in the binary tree (the whole identification process), tends to positive infinity. For convenience, we derive the lower bounds of T and $\mathrm{B}\mathrm{i}\mathrm{t}{\mathrm{s}}_R$ for reference. As in BS the binary tree representing the whole identification process is a strict binary tree; the intermediate nodes denoted by $C_F(n)$ (i.e., the colliding times) achieve minimal value when they are regarded as a complete binary tree whose number of nodes can be expressed as $2C_F(n)+1$ . Consider the fact that the number of all nodes in the strict binary tree satisfies the inequation $N_{\mathrm{n}\mathrm{d}}(n)\ge 2C_F(n)+1=2·{\sum }_{k=\mathrm{0}}^{{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}n-\mathrm{1}}{\mathrm{2}}^k+1=2n-3$ , and each node corresponds with a read cycle, so we can derive the following expressions for fast tag estimation:

$$\begin{array}{cc}& T\ge T_{\mathrm{cycle}}·\left(\mathrm{2}n-\mathrm{3}\right),\\ {\text{Bits}}_R\ge C_{\text{bits}}·\left(\mathrm{2}n-\mathrm{3}\right).\end{array}$$

(7)

2.4. Query Tree Algorithm (QT)

QT splits a tag set according to tag's ID. The reader transmits a query including a bit string, and only the tag whose ID has a prefix matching the query string responds by transmitting its ID. In particular, if the current query string is $q_1{q}_2\cdots q_n\hspace{0.17em}\hspace{0.17em}(q_i\in \{\mathrm{0,1}\})$ and leads to a collision, the reader uses two 1-bit longer queries, that is, $q_1{q}_2\cdots q_{n}0$ and $q_1{q}_2\cdots q_{n}1$ , in the next read cycles in turn, which splits the set of colliding tags into two subsets. If a collision still occurs when the new 1-bit longer query string is sent, then the string length is further increased by 1 bit with 0 or 1 added to the end of the current query string, until the collision is solved and a tag is identified successfully. The reader has a stack S to manage query strings. In the beginning, S is initialized as NULL, which causes all tags response. When collision occurs, the reader pushed two 1-bit longer query strings into S. When current read cycle is finished, it pops a query string from S for the next read cycle. That S is popped empty indicates that all tags are recognized. Notice that collisions in QT correspond to the intermediate nodes, not including the root node, compared with BS.

If we define the same notations as given in BS above, the major metrics of QT can be derived as follows:

$$\begin{array}{cc}& T\le T_{\mathrm{cycle}}·\left(\mathrm{2.887}n-\mathrm{1}\right),\\ {\text{Bits}}_R\le {\text{ID}}_{\text{bits}}·\left(\mathrm{2.887}n-\mathrm{1}\right),\\ {\text{Bits}}_T={\text{ID}}_{\text{bits}}·\left(\mathrm{2.21}{\log }_{\mathrm{2}}n+\mathrm{4.19}\right).\end{array}$$

(8)

2.5. Query Tree Improved Algorithm (QTI)

There are amounts of useless query strings in QT, which increase the read cycles and depress the system throughput. QTI is an enhancement that removes those certainly causing collisions in advance. For example, consider the case in which query prefix q has produced a collision, while $q0$ result in no response. As $q1$ definitely leads to a collision, QTI skips it directly and takes $q10$ as the next query prefix.

Compared with QT, QTI only reduces the amount of data transmitted by the reader, while it maintains the amount of data sent by tags unchanged, which also makes the expression of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ unchanged.

If we follow the same notations defined in BS, we can obtain the formulas as follows:

$$\begin{array}{cc}& T\le T_{\mathrm{cycle}}·\left(\mathrm{2.665}n-\mathrm{1}\right),\\ {\text{Bits}}_R\le {\text{ID}}_{\text{bits}}·\left(\mathrm{2.665}n-\mathrm{1}\right),\\ {\text{Bits}}_T={\text{ID}}_{\text{bits}}·\left(\mathrm{2.21}{\log }_{\mathrm{2}}n+\mathrm{4.19}\right).\end{array}$$

(9)

From what has been discussed hereinbefore, we can see clearly that, regardless of time or communication complexity, the metrics of ALOHA-based, including DFSA and EDFSA, are the same order infinitesimal of n, while the metrics of tree-based, including BS, QT, and QTI, are the higher order infinitesimal of n. Although the metrics of tree-based algorithms seem worse, they are deterministic which can avoid the so-called “tag starvation problem” that a specific tag may not be identified all the time in ALOHA-based algorithms.

3. The Proposed Algorithm T-GDFSA

The proposed algorithm T-GDFSA can be divided into two steps, the step of the estimation of tag population and the step of tag identification. The former is just implemented once to estimate the initial number of tags existing in the covering range of the reader, which is used in the second step to calculate the optimal number of groups and frame size in each group. In T-GDFSA, the method used for tag estimation is similar to TEM (Tag Estimation Method) [14]. At the end of each read cycle, the recorded triple numbers $〈c_0,c_1,c_k〉$ can be obtained from the reader's memory, which quantifies the number of idle time slots, successful time slots occupied by only one tag, and colliding slots with more than two tags, respectively. Meanwhile, the expected triple numbers $〈a_0^{N,n},a_1^{N,n},a_k^{N,n}〉$ can be computed from the given frame size N and the number n of tags by statistical knowledge. According to Chebyshev's expression, the outcome of a random experiment involving a random variable X is most likely somewhere near the expected value of X. This property is used to calculate the distance between the recorded results $〈c_0,c_1,c_k〉$ and the expected results $〈a_0^{N,n},a_1^{N,n},a_k^{N,n}〉$ of each read cycle as defined in (10). When theminimal distance is achieved, the corresponding n is considered to be the optimal estimation of tag population. Consider

$$\begin{array}{cc}& \epsilon \left(N,c_{\mathrm{0}},c_{\mathrm{1}},c_k\right)=\underset{n}{\min }\left|\left(\begin{array}{c}{a}_{\mathrm{0}}^{N,n}\\ a_{\mathrm{1}}^{N,n}\\ a_k^{N,n}\end{array}\right)-\left(\begin{array}{c}{c}_{\mathrm{0}}\\ c_{\mathrm{1}}\\ c_k\end{array}\right)\right|,\end{array}$$

(10)

where $a_k^{N,n}$ is the expected value of colliding slots with k tags; then

$$\begin{array}{cc}& a_k^{N,n}=N·\left(\begin{array}{c}n\\ k\end{array}\right)·{\left(\frac{\mathrm{1}}{N}\right)}^k·{\left(\mathrm{1}-\frac{\mathrm{1}}{N}\right)}^{n-k}\left(k\le n\right).\end{array}$$

(11)

In (10), the minimal ε is supposed to be achieved by a searching process with n varying in the range $[c_1+2c_k,3(c_1+2c_k)]$ , where $c_1+2c_k$ is the lower bound of n according to [15], since $c_1$ tags have been identified, and if there are $c_k$ collisions, at least $2c_k$ tags collided. The upper bound of n is set to $3(c_1+2c_k)$ , since by simulation no further accuracy in the estimation is obtained if the upper bound is set to higher values.

From [1] we know that the system throughput becomes optimal when the frame size is set equal to the number of tags. In order to satisfy this condition, the grouping size is adjusted by 1 each time to ensure that the number of tags in each group is very close to the frame size. The optimal grouping size is decided by the expected system efficiency. Suppose the current number of groups is k; it will be increased to $k+1$ if the expected system efficiency with $k+1$ groups rises just equal to that with k groups. Consider

$$\begin{array}{cc}& \frac{a_{\mathrm{1}}^{N,n/k}}{N}=\frac{a_{\mathrm{1}}^{N,n/\left(k+\mathrm{1}\right)}}{N}\left(k=\mathrm{1,2},\dots \right).\end{array}$$

(12)

From (12), the maximum number of tags with k groups is

$$\begin{array}{cc}& n_k=\frac{\mathrm{l}\mathrm{g}\left(k/\left(k+\mathrm{1}\right)\right)}{\mathrm{l}\mathrm{g}\left(\mathrm{1}-\mathrm{1}/N\right)}·k·\left(k+\mathrm{1}\right)\left(k=\mathrm{1,2},\dots \right).\end{array}$$

(13)

By the utilization of (13), the optimal grouping size G can be obtained with a varying n and a given frame size L.

Then the optimal G is broadcast by the reader with a random number to tags. Grouping rule is as follows. Each tag generates a new random number by the old received one and its serial number (tag's ID). Then the new random number is divided by G, and all tags have a group number randomly in the range $\left[\mathrm{0},G-\mathrm{1}\right]$ . In the current read frame, only tags with group number 0 are permitted to respond the reader. When all of them have been identified, the reader begins a new read frame and tags with group number 1 are involved. The process continues until tags having group number $G-1$ are queried, which means all tags have been recognized. The frame size of each read frame decides how many time slots are included in it. At the beginning of each read frame, the reader broadcasts the optimal frame size L to all tags which means there are L time slots in the incoming read frame, and tags involved generate an integer $L_i$ in the range $[1,L]$ and save it in its slot counter. By this means, tags are allocated into L time slots randomly. In the first time slot initiated by the reader, tags with slot counter at 0 are permitted to respond the reader. When all tags in current time slot have been identified, the reader polls the next time slot and informs other unidentified tags to decrease their time slot counter by 1. Tags whose value of slot counters decreasing to 0 are permitted to respond the reader in the incoming time slot. If a collision happens in the current time slot, tags involved add 0 or 1 randomly to their slot counters which cause them to fall into two subsets. It means that a binary tree is introduced, and colliding tags are subdivided into two child nodes of the current parent node randomly. Other tags increase their slot counters by 1 so as to counteract the effect caused by splitting for the colliding tags to keep their former identification sequence unchanged. After splitting, the reader firstly turns to identify the tags in the left child node of current parent node, and if a collision is still detected, the node-splitting process will be executed again and tags falling into the deeper left child node will be read in the incoming time slot. The process will keep on going recursively until there is no collision happened in the current left child node. Because there is no more than 1 tag in the leaf, tag in it can be identified successfully and then muted. Next, the reader returns up to the parent node of the current left child node, then turns down to the right child node and identifies tags in it. There are three possible outcomes. Collision slot will cause a new node-splitting process similar to that represented beforehand. 1-tag slot will make the reader identify the tag successfully and then return to the parent node. Idle slot will make the reader directly come back to the parent node. Next, as all the child nodes of the parent node have been identified, the reader will return to the upper parent node. The procedure will continue recursively until all nodes of the binary tree have been queried, which means all tags in current colliding time slot have been identified. In the initiation of each binary tree recursive process, the reader sets a level counter for current colliding slot to record the depth of current node (i.e., read cycle) in the binary tree. It is increased by 1 when a collision happens in current node and the reader goes deeper to the child nodes and is decreased by 1 when all tags in the child nodes are already identified and the reader returns to the upper parent node. Level counter which decreased to 0 indicates that all tags in the current collision slot have been identified. In Figure 2, the tag identification process for group 1 is illustrated, where $\mathrm{L}\mathrm{e}\mathrm{v}$ means the level counter, Φ denotes no tag responding, and each “•” represents one tag. The identification processes for other groups are similar.

Figure 2

The execution process of the T-GDFSA.

4. Performance Evaluation

In this section we will evaluate the performance of T-GDFSA. There are several metrics focusing on different aspects of RFID system. We take time complexity and communication complexity for emphatic analysis. Because time complexity reflects the identification efficiency which is of great importance for fast tag identification, and communication complexity indicates power consumption of the reader and tags which is of great significance for mobile RFID applications. Time complexity is defined as the total time spent to identify a set of tags in the covering range of the reader. Communication complexity refers to the amount of data transmitted between the reader and tags, which can be composed of two parts: ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ (the total number of bits sent by the reader) and ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ (the total number of bits transmitted by single tag in average).

Prior to deeper analysis, it is necessary to make the following important assumptions.

Assumption 1.

As data received by the reader are mostly short symbols such as acknowledgement symbols and so forth, which are much less compared with the data sent by the reader, we simply ignore it and consider that ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ totally represents the communication complexity on reader.

Assumption 2.

The duration of time slot in read frame is set equal to that of read cycle in binary tree, which is denoted by the unified symbol $T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ , making it possible to calculate the system throughput quantificationally.

Assumption 3.

In most RFID applications, power consumption of tags is more sensitive than that of the reader. So we proposed a new strategy dedicated to reducing ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ , which is deployed as follows. Instead of sending complete tag's ID directly, tag firstly sends IDTest (a short bit string) to test the state of the current time slot. If no collision happens, IDTest can be received by the reader successfully. The reader responds with the acknowledgement IDReq to require the tag to transmit its complete ID. The strategy eliminates the useless mass data transmission of tag's ID caused by collisions and ensures that tag's ID is sent only once. Since the length of IDTest is much shorter than that of tag's ID, $\mathrm{B}\mathrm{i}\mathrm{t}{\mathrm{s}}_T$ is decreased drastically.

4.1. Time Complexity

The total consumed time, denoted by T, consists of three parts, $T_{\mathrm{e}\mathrm{s}\mathrm{t}}$ (time cost in the estimation of tag population), $T_{\mathrm{r}\mathrm{f}}$ (time cost in read frames), and $T_{\mathrm{r}\mathrm{c}}$ (time cost in read cycles of binary tree recursive process). Then we get

$$\begin{array}{cc}& T=T_{\text{est}}+T_{\text{rf}}+T_{\text{rc}}.\end{array}$$

(14)

Let $G_{\mathrm{i}\mathrm{n}\mathrm{i}}$ denote the initial grouping size for the estimation of tag population, and let $G(n)$ denote the actual grouping size calculated by (13). $L_{\mathrm{i}\mathrm{n}\mathrm{i}}$ and $L(n)$ represent the initial frame size and the actual frame size separately. n is the number of unidentified tags. Then $T_{\mathrm{e}\mathrm{s}\mathrm{t}}$ and $T_{\mathrm{r}\mathrm{f}}$ can be expressed as $G_{\mathrm{i}\mathrm{n}\mathrm{i}}{L}_{\mathrm{i}\mathrm{n}\mathrm{i}}{T}_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ and $G\left(n\right)L\left(n\right)T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ , respectively. According to [1], when the condition of maximal throughput of framed slotted ALOHA, the read frame size is equal to the number of unidentified tags, is satisfied, the average number of tags in each colliding time slot is about 2.3922 on average. Because $G(n)L(n)$ is very close to n in T-GDFSA, the average number of tags in each colliding time slot, denoted by $C_{\mathrm{t}\mathrm{a}\mathrm{g}}$ , can be considered as 2.3922 simply.

According to the representation above, we know that the binary tree process for each colliding time slot is a strictly binary tree, so there is no 1-degree node included, meaning that any non-leaf node (the root node or the intermediate node) has two child nodes. Let $N_{\mathrm{n}\mathrm{d}}$ and $N_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}$ be the number of non-leaf nodes and leaf nodes, respectively; then $N_{\mathrm{n}\mathrm{d}}=2N_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}-1$ can be easily deduced [16]. Since the root node corresponds to the colliding time slot which has already been counted in the read frame before, the effective number of nodes in every binary tree is $N_{\mathrm{n}\mathrm{d}}-1$ . Since the leaf nodes are composed of 1-tag leaf nodes and idle leaf nodes, the number of actual nodes in every colliding time slot, denoted as $N_{\mathrm{n}\mathrm{d}}^{\prime }$ , satisfies the inequation $N_{\mathrm{n}\mathrm{d}}^{\prime }\ge 2C_{\mathrm{t}\mathrm{a}\mathrm{g}}-2=2.7844$ on average. Note the fact that when $C_{\mathrm{t}\mathrm{a}\mathrm{g}}$ is small it is very close to $N_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{f}}$ , so the inequation above can be considered as equation $N_{\mathrm{n}\mathrm{d}}^{\prime }=2C_{\mathrm{t}\mathrm{a}\mathrm{g}}-2=2.7844$ simply. By probability knowledge, we can derive that the expected value of colliding time slots is $G\left(n\right)L\left(n\right)P_{\mathrm{c}\mathrm{o}\mathrm{l}}$ , where $P_{\mathrm{c}\mathrm{o}\mathrm{l}}$ is the probability of detecting a colliding time slot, and that $T_{\mathrm{r}\mathrm{c}}$ is no less than $2.7844G\left(n\right)L\left(n\right)P_{\mathrm{c}\mathrm{o}\mathrm{l}}{T}_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ . Substituting (14) with the all results above, we acquire the final expression of T as follows:

$$\begin{array}{l}T\text{'}\{G_{\text{ini}}\cdot L_{\text{ini}}+G\left(n\right)\cdot L\left(n\right)+2.7844\cdot G\left(n\right)\cdot L\left(n\right)\hfill \\ \hspace{1em}\cdot P_{\text{col}}\}\cdot T_{\text{cycle}}.\hfill \end{array}$$

(15)

In expression (15), $P_{\mathrm{c}\mathrm{o}\mathrm{l}}=\left[\mathrm{1}-n/G\left(n\right)·p{\left(\mathrm{1}-p\right)}^{n/G\left(n\right)-\mathrm{1}}-{\left(\mathrm{1}-p\right)}^{n/G(n)}\right]$ where $p=\mathrm{1}/L(n)$ is the probability of a tag selecting a time slot from total $L(n)$ time slots.

4.2. Communication Complexity on Reader

${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ is defined as the amount of data transmitted by the reader to identify a set of tags appearing in its irrigation range, which reflects the communication complexity on reader suitably. From the above analysis, we realize that, no matter in the step of initial tag estimation or in the step of tag identification process, the amount of data sent by the reader representing group size and frame size are both $(G_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}+L_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}})$ bits. The reader also needs to transmit QueryRep periodically to make the current time slot increased continually so as to poll tags allocated in different time slots of current frame, and the amount of data of this part can be expressed as $[G_{\mathrm{i}\mathrm{n}\mathrm{i}}{L}_{\mathrm{i}\mathrm{n}\mathrm{i}}+G(n)L(n)]\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}\mathrm{R}\mathrm{e}{\mathrm{p}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ . Besides, in every binary tree recursive process, as expressed above, the number of read cycles, $N_{\mathrm{n}\mathrm{d}}^{\prime }$ , is equal to $2C_{\mathrm{t}\mathrm{a}\mathrm{g}}-2=2.7844$ . As nodes in a binary tree consist of collision nodes and leaf nodes and the leaf nodes need no extra read cycles to query, the number of actual nodes for which reader sends read cycles should be $(2C_{\mathrm{t}\mathrm{a}\mathrm{g}}-2-C_{\mathrm{t}\mathrm{a}\mathrm{g}})=0.3922$ on average. The reader sends at most 1 read cycle in every node, so the number of read cycles in every binary tree recursive process is almost 0.3922. Considering that the expected number of collision slots is $G\left(n\right)L\left(n\right)P_{\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}}$ , the total number of read cycles in all binary tree recursive processes is $0.3922G\left(n\right)L\left(n\right)P_{\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}}$ . Let $R_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ be the string length of one read cycle and let $\mathrm{I}\mathrm{D}\mathrm{R}\mathrm{e}{\mathrm{q}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ be the string length of $\mathrm{I}\mathrm{D}\mathrm{R}\mathrm{e}\mathrm{q}$ sent by the reader, respectively; $\mathrm{B}\mathrm{i}\mathrm{t}{\mathrm{s}}_R$ can be finally expressed as follows:

$$\begin{array}{ll}{\text{Bits}}_R& \approx \mathrm{2}\left(G_{\text{bits}}+L_{\text{bits}}\right)\\ & +\left[G_{\text{ini}}{L}_{\text{ini}}+G\left(n\right)L\left(n\right)\right]\text{Query}{\text{Rep}}_{\text{bits}}+n\\ & ·\text{ID}{\text{Req}}_{\text{bits}}+\mathrm{0.3922}G\left(n\right)L\left(n\right)P_{\text{coll}}{R}_{\text{bits}}.\end{array}$$

(16)

4.3. Communication Complexity on Tag

Here we take ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ for consideration to indicate the average amount of data transmitted by single tag. Because of the randomness of tag identification, the average bits of data sent by single tag are difficult to observe exactly, so the lower bound and the upper bound are introduced for reference.

(a) The Lower Bound. If one lets $\mathrm{l}\mathrm{e}\mathrm{v}(i)$ be the level of the ith leaf node in a strict binary tree with n leaf nodes, where i varies from 1 to n, according to the property of strict binary tree, the following equation can be easily derived:

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^n\frac{\mathrm{1}}{{\mathrm{2}}^{\text{lev}\left(i\right)}}=\mathrm{1}.\end{array}$$

(17)

Since ${\sum }_{i=\mathrm{1}}^n\left(\mathrm{1}/{\mathrm{2}}^{\mathrm{l}\mathrm{e}\mathrm{v}(i)}\right)=n·\left(\mathrm{1}/n\right){\sum }_{i=\mathrm{1}}^n\left(\mathrm{1}/{\mathrm{2}}^{\mathrm{l}\mathrm{e}\mathrm{v}(i)}\right)\ge n·\sqrt[n]{{\left(\mathrm{1}/\mathrm{2}\right)}^{{\sum }_{i=\mathrm{1}}^n\mathrm{l}\mathrm{e}\mathrm{v}(i)}}$ , we can obtain

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^n\text{lev}\left(i\right)\ge n{\log }_{\mathrm{2}}n.\end{array}$$

(18)

Expression (18) shows that the sum of levels of all leaf nodes in a strict binary tree with n leaf nodes is no less than $n{\log }_{\mathrm{2}}n$ . Because the level of node indicates that the collision times tags allocated in it have experienced, and the colliding times in a strict binary tree with n tags become minimal only when the number of leaf nodes is equal to n, the total colliding times in a strict binary tree with n tags are no less than $n{\log }_{\mathrm{2}}n$ . Let $P_{\mathrm{c}\mathrm{o}\mathrm{l}}$ and $P_{\mathrm{s}\mathrm{u}\mathrm{c}}$ denote the expected possibility of colliding slots and singleton slots, respectively; according to Assumption 3, the amount of data transmitted by tags in all colliding time slots satisfies

$$\begin{array}{l}{\text{Bits}}_{\text{CS}}\ge G\left(n\right)·L\left(n\right)P_{\text{col}}·(\mathrm{2.3922}·{\log }_{\mathrm{2}}\mathrm{2.3922}\\ ·\text{ID}{\text{Test}}_{\text{bits}}+\mathrm{2.3922}·{\text{ID}}_{\text{bits}}).\end{array}$$

(19)

The total amount of data sent by all tags, represented by ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_{\mathrm{T}\mathrm{A}}$ , is composed of two parts: data sent by the tags in colliding time slots and data sent by the tags in singleton slots. The former is expressed by (19). Since every tag allocated in the singleton slot transmits $\mathrm{I}\mathrm{D}\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}$ as well as tag's ID only once, and there are $G\left(n\right)L\left(n\right)P_{\mathrm{s}\mathrm{u}\mathrm{c}}$ singleton slots with only 1 tag, ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_{\mathrm{T}\mathrm{A}}$ can be derived as the following expression:

$$\begin{array}{ll}{\text{Bits}}_{\text{TA}}& ={\text{Bits}}_{\text{CS}}+G\left(n\right)·L\left(n\right)·P_{\text{suc}}\\ & ·\left(\text{ID}{\text{Test}}_{\text{bits}}+{\text{ID}}_{\text{bits}}\right)\\ & \ge G\left(n\right)·L\left(n\right)\\ & ·\left(\mathrm{2.3922}·P_{\text{col}}·{\log }_2\mathrm{2.3922}+P_{\text{succ}}\right)\\ & ·\text{ID}{\text{Test}}_{\text{bits}}+n·{\text{ID}}_{\text{bits}}.\end{array}$$

(20)

Finally, the lower bound of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ can be obtained as follows:

$$\begin{array}{l}{\text{Bits}}_T\\ \ge \frac{G\left(n\right)·L\left(n\right)}{n}\\ ·\left[\left(\mathrm{2.3922}·P_{\text{col}}·{\log }_2\mathrm{2.3922}+P_{\text{suc}}\right)·\text{ID}{\text{Test}}_{\text{bits}}\right]\\ +{\text{ID}}_{\text{bits}}.\end{array}$$

(21)

(b) The Upper Bound. In order to measure the largest amount of data sent by tags, we must take the worst condition into account. Consider the following extreme situation. Let $p_s$ be the probability of all colliding tags falling into the same child node simultaneously after splitting current collision node, and λ is the probability of only one tag falling into one child node. Obviously, $p_s$ is much large than λ at the beginning of the binary tree recursive process, which means colliding tags will fall into the same child node after splitting. As the splitting process is ongoing recursively, $p_s$ is decreasing and approaching λ. If and only if $p_s$ becomes not great than λ for the first time, the splitting of current collision node will result in one child node with only 1 tag and the other child node with the remainder tags, which separates 1 tag from the colliding tags and identifies it successfully. The splitting process will repeat recursively for the remaining tags in the colliding child node until there is no more than 1 tag falling into every node, or we can say the leaf node has been reached. Assuming that the ith identified tag has experienced $k_i$ times of collision before being identified successfully and m denotes the total number of colliding tags in the binary tree, we can get

$$\begin{array}{ll}{\left[{\left(\frac{\mathrm{1}}{\mathrm{2}}\right)}^{m+\mathrm{1}-i}\right]}^{k_i^{\prime }}& \le \lambda ,\\ & \text{where\hspace{0.17em}\hspace{0.17em}}{k}_i^{\prime }\text{\hspace{0.17em}\hspace{0.17em}is\hspace{0.17em}\hspace{0.17em}an\hspace{0.17em}\hspace{0.17em}integer},k_i=\min \left(k_i^{\prime }\right)\\ & ⟹k_i=⌈\frac{\mathrm{1}}{m+\mathrm{1}-i}{\log }_{\mathrm{1}/\mathrm{2}}\lambda ⌉\\ & <\frac{\mathrm{1}}{m+\mathrm{1}-i}{\log }_{\mathrm{1}/\mathrm{2}}\lambda +\mathrm{1}.\end{array}$$

(22)

So the amount of data sent by m tags in the binary tree can be considered as

$$\begin{array}{ll}{\text{Bits}}_{\text{CS}}& \le {\displaystyle \sum }_{i=\mathrm{1}}^{m-\mathrm{1}}{k}_i·\text{ID}{\text{Test}}_{\text{bits}}+m·{\text{ID}}_{\text{bits}}\\ & =\left({\displaystyle \sum }_{i=\mathrm{1}}^{m-\mathrm{1}}⌈\frac{\mathrm{1}}{m+\mathrm{1}-i}{\log }_{\mathrm{1}/\mathrm{2}}\lambda ⌉\right)·\text{ID}{\text{Test}}_{\text{bits}}+m\\ & ·{\text{ID}}_{\text{bits}}.\end{array}$$

(23)

In the expression above, the fact that the range of i does not include m is because the mth tag will be identified undoubtedly in the next read frame if the $(m-1)$ th tag has been identified. Therefore, by expressions (22) and (23), we get the following expression:

$$\begin{array}{ll}{\text{Bits}}_{\text{CS}}& <\left\{\left[\left({\displaystyle \sum }_{i=\mathrm{1}}^m\frac{\mathrm{1}}{i}\right)-\mathrm{1}\right]·{\log }_{\mathrm{1}/\mathrm{2}}\lambda +\left(m-\mathrm{1}\right)\right\}\\ & ·\text{ID}{\text{Test}}_{\text{bits}}+m·{\text{ID}}_{\text{bits}}.\end{array}$$

(24)

Seeing that ${\sum }_{i=\mathrm{1}}^m\left(\mathrm{1}/i\right)$ is the sum of the first m terms of the harmonic series and its upper bound is $({\log }_{\mathrm{2}}m+\mathrm{1})$ [16], expression (24) can be rewritten as

$$\begin{array}{ll}{\text{Bits}}_{\text{CS}}& <\left[\left({\log }_{\mathrm{2}}m+\mathrm{1}-\mathrm{1}\right)·{\log }_{\mathrm{1}/\mathrm{2}}\lambda +\left(m-\mathrm{1}\right)\right]\\ & ·\text{ID}{\text{Test}}_{\text{bits}}+m·{\text{ID}}_{\text{bits}}\\ & =\left[{\log }_{\mathrm{2}}m·{\log }_{\mathrm{2}}{\lambda }^{-\mathrm{1}}+\left(m-\mathrm{1}\right)\right]·\text{ID}{\text{Test}}_{\text{bits}}+m\\ & ·{\text{ID}}_{\text{bits}}.\end{array}$$

(25)

Considering $m=2.3922$ , so the total amount of data sent by all tags is

$$\begin{array}{l}{\text{Bits}}_{\text{TA}}\\ ={\text{Bits}}_{\text{CS}}+G\left(n\right)·L\left(n\right)·P_{\text{suc}}·\left(\text{ID}{\text{Test}}_{\text{bits}}+{\text{ID}}_{\text{bits}}\right)\\ <G\left(n\right)·L\left(n\right)\\ ·\left[P_{\text{col}}·\left({\log }_{\mathrm{2}}\mathrm{2.3922}·{\log }_{\mathrm{2}}{\lambda }^{-\mathrm{1}}+\mathrm{0.5820}\right)+P_{\text{suc}}\right]\\ ·\text{ID}{\text{Test}}_{\text{bits}}+n·{\text{ID}}_{\text{bits}}.\end{array}$$

(26)

And the average amount of data sent by single tag is shown as follows:

$$\begin{array}{l}{\text{Bits}}_T=\frac{{\text{Bits}}_{\text{TA}}}{n}<\frac{G\left(n\right)L\left(n\right)}{n}[P_{\text{col}}({log}_{2}2.3922\hfill \\ \hspace{1em}.{log}_2{\lambda }^{-1}+0.5820)+P_{\text{suc}}]{\text{IDTest}}_{\text{bits}}+{\text{ID}}_{\text{bits}}.\hfill \end{array}$$

(27)

Thus, the final expression of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ can be deduced form expressions (21) and (27), which is expressed as an inequation with a lower bound and an upper bound as follows:

$$\begin{array}{l}\frac{G\left(n\right)\cdot L\left(n\right)}{n}\cdot [\left(2.3922\cdot P_{\text{col}}\cdot {log}_{2}2.3922+P_{\text{suc}}\right)\hfill \\ \hspace{1em}\cdot {\text{IDTest}}_{\text{bits}}]+{\text{ID}}_{\text{bits}}\le {\text{Bits}}_T<\frac{G\left(n\right)\cdot L\left(n\right)}{n}[P_{\text{col}}\hfill \\ \hspace{1em}\cdot \left({log}_{2}2.3922\cdot {log}_2{\lambda }^{-1}+0.5820\right)+P_{\text{suc}}]\hfill \\ \hspace{1em}\cdot {\text{IDTest}}_{\text{bits}}+{\text{ID}}_{\text{bits}}.\hfill \end{array}$$

(28)

5. Simulation

Next, we need to verify how close the mathematic formulas presented in Section 4 match the reality. As the key factors influencing application for anticollision algorithms include the system throughput and the communication complexities, which indicate how fast tags can be identified (especially important for mobile tags) and how low the energy is consumed, the comparisons for both of them between our algorithm and traditional ones should be made. So we program on Matlab7.1 and the simulations include (1) comparing theoretical values calculated by the mathematic formulas mentioned above with the simulative results acquired from simulations, (2) comparing the complexity of T-GDFSA with that of traditional algorithms including DFSA, EDFSA, BS, QT, and QTI, and (3) comparing the system throughput of T-GDFSA when the length of tag's ID varies in a large range or the initial estimation of tag population becomes inaccurate. System throughput, denoted by S, is defined as the ratio of the number of tags to the sum of all time slots used in the read frames and all read cycles produced for querying the nodes of binary trees and can be obtained from the formula $S=n{T}_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}/T$ , where $T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}$ is the duration of one time slot as well as the duration of one read cycle.

Before simulation, some parameters need to be set properly. The parameters are set as follows: $p_s=1/L$ , $L_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=14$ , $G_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=5$ , ${\mathrm{L}\mathrm{e}\mathrm{v}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=4$ , $R_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=23$    $(L_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}+G_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}+{\mathrm{L}\mathrm{e}\mathrm{v}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}})$ , ${\mathrm{I}\mathrm{D}\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=8$ , ${\mathrm{I}\mathrm{D}\mathrm{R}\mathrm{e}\mathrm{q}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=8$ , ${\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{p}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=4$ , and $L_{\mathrm{m}\mathrm{a}\mathrm{x}}=256$ . Considering that the possibility that each tag falls in a slot is $1/L$ when the frame size is L, we set $p_s$ to $1/L$ . $L_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ set to 14 means the maximal time slots in a read frame can be 2¹⁴. $G_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ set to 5 indicates that the maximal grouping size is 2⁵. ${\mathrm{L}\mathrm{e}\mathrm{v}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ is set to 4, which refers to the fact that the maximal depth of the binary tree in recursive process is 2⁴. Obviously, $R_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ can be set to 23 as a sum of $L_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}+G_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}+{\mathrm{L}\mathrm{e}\mathrm{v}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ . ${\mathrm{I}\mathrm{D}\mathrm{T}\mathrm{e}\mathrm{s}\mathrm{t}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ and ${\mathrm{I}\mathrm{D}\mathrm{R}\mathrm{e}\mathrm{q}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ set to 8 means the reader and tags use a 1-byte string to achieve the strategy of slot test. The value of ${\mathrm{Q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{p}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ is decided by the encoding method of commands and set to 4 in our simulations, which means each command sent by the reader is represented by a 4-bit binary string. As $L_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , the maximal frame size, refers to the memory used in tags which is usually very limited in reality, it is just set to 256 in our simulations which means 1-byte memory is required in tags. Besides, the following parameters are tuned:

• (i)

$n\text{:}$ the number of tags to be identified. It is increased by 50 in each trial in the range $[\mathrm{50,1000}]$ .

(ii)

$L_{\mathrm{i}\mathrm{n}\mathrm{i}}$ : the initial estimated number of unidentified tags. This value is used to set the initial read frame size. It is set to $0.5n$ , $1.5n$ , $2n$ , and $5n$ for inaccurate estimation.

(iii)

${\mathrm{I}\mathrm{D}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}$ : the length of tag's ID. It is assigned to the value $\{\mathrm{48,64,96,128}\}$ sequentially.

(iv)

Running times: the times each simulation runs. It is set to be 100 times and the average result is taken for analysis.

In Figures 3–5, performance comparison of T-GDFSA between theoretical values and simulative results is shown. In Figure 3, the theoretical curve of S appears as a zigzag line surrounding the curve of simulative results. The points of the wave crest of the theoretical curve correspond to the increase of grouping size, which reduces tags per group drastically and deteriorates S significantly because of more extra idle slots. Figure 4 shows that the theoretical ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ matches well the simulative one. In Figure 5, simulative values of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ are mostly 69 bits and the lower bound of theoretical values is near 58 bits, with the length of tag's ID set to 48 bits. Notice that the upper bound of theoretical values is very close to simulative results when λ is set to 0.01.

Figure 3

The comparison of S.

Figure 4

The comparison of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ .

Figure 5

The comparison of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ , with ${\mathrm{I}\mathrm{D}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=48$ and tag's ID uniformly distributed.

In Figure 6, compared with other traditional anticollision algorithms, T-GDFSA has the highest S about 0.41 when tag's ID is set to 48 bits long and uniformly distributed. Figure 7 shows that T-GDFSA has agreeable ${\mathrm{B}\mathrm{i}\mathrm{t}}_R$ which is reduced by at least half of that of tree-based algorithms and nearly equal to that of ALOHA-based algorithms. In Figure 8, T-GDFSA has the lowest ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ which means more power is saved in tags compared with other traditional algorithms.

Figure 6

The comparison of S, with $L_{\mathrm{i}\mathrm{n}\mathrm{i}}=n$ and ${\mathrm{I}\mathrm{D}}_{\text{bits}}=48$ .

Figure 7

The comparison of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_R$ , with $L_{\mathrm{i}\mathrm{n}\mathrm{i}}=n$ and ${\mathrm{I}\mathrm{D}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=48$ .

Figure 8

The comparison of ${\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{s}}_T$ , with $L_{\mathrm{i}\mathrm{n}\mathrm{i}}=n$ and ${\mathrm{I}\mathrm{D}}_{\text{bits}}=48$ .

Figure 9 shows the variation of S with inaccurate initial tag estimation. When the estimated number is varying from $0.5n$ to $1.5n$ , S is still higher than 0.38, which indicates that T-GDFSA has great tolerance for the inaccuracy of initial tag estimation. We also notice that T-GDFSA performs better in underestimation than overestimation. This is because smaller frame size in underestimation causes more tags to fall into colliding time slots, which can make full use of the advantages of T-GDFSA, while in the case of overestimation the identification process is more like an EDFSA identification, with more 1-tag time slots and idle time slots. Figure 10 shows that length variation of tag's ID has little influence on S. When tag population exceeds 450, this effect can be approximately ignored.

Figure 9

S versus n, when ${\mathrm{I}\mathrm{D}}_{\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}}=48$ with the inaccuracy of initial estimation of tag population.

Figure 10

S versus n, under the condition of $L_{\mathrm{i}\mathrm{n}\mathrm{i}}=n$ and the length variation of tag's ID.

The simulations above reflect the following. (1) Our mathematic formulas of the main metrics match well the reality. (2) Compared with traditional algorithms, T-GDFSA achieves higher system throughput while maintaining lower computing complexities, which is not available for traditional algorithms shown above. This significant advantage makes our algorithm easier to be realized in end-user applications.

6. Conclusion

In this paper, we firstly make a summary of traditional RFID anticollision algorithms, and then propose a novel hybrid anticollision algorithm called T-GDFSA to improve the performance of RFID tag identification. T-GDFSA, which is based on grouped dynamic frame-slotted ALOHA and binary tree recursive process, has optimal group size and optimal read frame size and solves colliding time slots by introducing the binary tree recursive process. System model and mathematics formulas are present, and theoretical values of metrics show great agreement with the simulative results obtained from simulations. Compared with traditional ALOHA-based and tree-based anticollision algorithms, T-GDFSA exhibits excellent comprehensive performance with preferable system throughput around 0.41 and lower communication complexity which is similar to EDFSA but at least half less than that of tree-based algorithms. Furthermore, T-GDFSA has tolerance for the inaccuracy of initial tag estimation and the length variation of tag's ID.

As we can see, an accurate estimation of actual tag population in T-GDFSA is very significant. The estimation is used to set the optimal grouping size and frame size which ensures the performance. Meanwhile, the computing complexity of estimation cannot be very high to ensure the reader to identify tags promptly. However, the estimation in T-GDFSA follows TEM (i.e., Vogt's method), which may not be optimal in both of time and accuracy, so one of the possible directions of our next work is to find a way to improve the estimation method for T-GDFSA to achieve better performance of RFID tag identification.