# Research on RFID Anticollision Algorithms in Industrial Internet of Things

Authors: Haizhong Qian
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

As a perception enabling technology of the Internet of Things, RFID can quickly identify target objects. The tag-to-tag collision problem seriously affects the identification performance of the RFID system, which causes the reader to be unable to accurately identify any tag within the specific time. The mainstream anticollision algorithms are limited by the performance bottleneck under the standard framework. In this paper, we analyze the features and merits of three kinds of algorithms in detail and propose a new algorithm architecture for RFID anticollision. Through the extensive experimental results comparison, we prove that the new architecture is effective to improve the performance of DFSA algorithms. Finally, we summarize the future research trends in the RFID anticollision algorithms.


---

## Body

## 1. Introduction

Radio Frequency Identification (RFID) [1–3] technology is an emerging backscatter communication technology [4], which uses radio frequency signals to carry out information exchange in the wireless channel and realizes the noncontact identification between objects. A typical RFID system consists of readers, tags, and backend components. In many applications based on RFID technology, a mass of passive RFID tags is deployed in the RFID system. Due to the nature of passive tags, tags cannot communicate with each other, so all tags can only receive signals from readers. Since multiple tags share the same wireless channel to communicate with readers, when multiple tags send data to readers at the same time, the phenomenon of collision between more tags will occur, resulting in the failure of readers to identify tags. Obviously, the collision brings great challenges to information collection. Therefore, the research on RFID electronic tag information collection is very suitable for the background of the development of the times [5, 6] and has important reference value and practical significance. Therefore, when there are multiple tags at the same time in the covering area of the reader, the reader must use anticollision algorithm to improve the efficiency of tag recognition.The current RFID multitag anticollision algorithms can be mainly divided into three categories, namely, probabilistic algorithms [7–10], deterministic algorithms [11–15], and hybrid algorithms [16–18]. Probabilistic algorithms are mainly derived from Aloha-based ideas. An Aloha-based algorithm takes the way of tag answering first and lets the tag randomly select a time period to respond to the query request of reader. If only one tag responded to the query in the current time period, the tag was successfully identified. In the Aloha-based algorithm, the most commonly used is the dynamic framed slotted Aloha (DFSA) algorithm. The DFSA algorithm formulates the concept of frame length (the frame length is equal to the number of time slots allowed by the tag), and then, the tag that receives the reader command will randomly select a time slot in a frame to respond and reply with its own ID. When a frame is over, the reader uses mathematical methods to estimate the number of remaining tags based on the slot status counted in the previous frame and starts the next frame identification until all tags are successfully recognized. The performance bound of the DFSA algorithm is 0.368 [19]. All DFSA algorithms are easy to implement and have low equipment cost but may have tag starvation. Deterministic algorithms are also called tree-walking algorithms. The core idea of this type of algorithm is to use bit tracking technology [20, 21] to lock the specific location of ID information collisions, so that the reader can adjust the query prefix in time to successfully identify subsequent tags. As the query progresses, the tree splits and all the child nodes of the query tree are retrieved. In other words, as long as there are enough queries, readers can accurately query the ID of each tag. Thus, tree-walk algorithm has a 100% recognition rate and can avoid the problem of tag starvation. However, once the tag IDs are not evenly distributed, the tree-based algorithm will generate many collision slots and lead to a gradual deterioration in performance. In order to maximize the multitag recognition performance of the RFID system, many researchers have merged the advantages of different types of algorithms and proposed a series of hybrid anticollision algorithms. The representative algorithms are BSTSA [16], BTSA [17], and GBSA [18]. Compared with traditional anticollision algorithm, the above algorithms have been significantly improved in tag recognition performance, but at the same time, they also caused some problems, such as high hardware cost, compatibility with existing RFID standards, and other issues. It is noted that there are also two kinds of collisions in the RFID systems, namely, reader-to-reader collision. The reader can use some scheduling methods to avoid such collisions. And this kind of collision is not the focus of this paper.This paper mainly analyzes the performance of the typical representatives of the existing several types of anticollision algorithms and summarizes and analyzes the performance bottlenecks and other shortcomings of the existing methods. Based on the analysis, we propose a new algorithm architecture in which the system throughput can break through the bottleneck of existing DFSA algorithms. Different from the traditional DFSA algorithms, the proposed new method can separately cope with each collision slot with the independent small-size frame. Through theoretical derivation and analysis, we proved that the proposed new method can make the anticollision algorithm break the performance limit under the constraints of the existing framework. Finally, the future research trends of anticollision algorithms are summarized.


## 2. Related Works

Taking into account factors such as RFID equipment cost and implementation complexity, currently, in RFID readers, multitag conflict avoidance technologies based on time division multiplexing are mainly used, which mainly include three types of methods based on Aloha, binary splitting, and query tree. Among the methods based on Aloha, currently, the most widely used is the dynamic framed slotted Aloha algorithm, which has been adopted by the UHF international standard EPC C1 Gen2. At present, most research focuses on two aspects. One is to maximize the utilization of time slots by dynamically adjusting the frame length of each round, and the other is to avoid waste of resources by terminating low-utilization frames early. The EACAEA [22] algorithm proposed by Chen considers the difference in time duration between different types of time slots to optimize the frame length to maximize system throughput. Chen’s research shows that when the length of the collision slot is 5 times that of the idle slot, the optimal frame length is 1.89 times the number of tags to be identified. However, this method only adjusts the frame length once in one round of recognition, which causes its performance to show large fluctuations when the number of tags changes, and its stability is poor. Su et al. [4] designed a frame length adjustment strategy based on time and energy saving and, based on this strategy, proposed a multitag identification algorithm named TES-FAS suitable for the EPC C1 Gen2 standard. The TES-FAS algorithm combines subframe observation and adaptive frame adjustment mechanisms and can achieve better recognition performance under different reader parameter configurations. However, the frame length optimization of the reader in TES-FAS algorithm is based on a static RFID environment, which makes it not suitable for dynamic RFID environments. Taking into account the mobility of tags, Zhu et al. [23] designed a scheduling-based RFID anticollision algorithm that satisfies a high recognition rate under a certain tag moving speed. Although the method takes into account the movement characteristics of the tag, its design is based on an ideal communication channel. In actual RFID application scenarios, there are path loss, signal attenuation, shadowing effects, etc., resulting in unsatisfactory communication channels between the reader and the tag. For this reason, many researchers [24–26] have studied multitag identification methods suitable for nonideal channels. The binary splitting method is intuitively a random access algorithm. Different from the Aloha-based algorithm, the collided tag set will be separated by a fixed probability of 0.5. In binary splitting methods, the tag starvation will be significantly weakened.Law first used the query tree [21] algorithm to solve the signal conflict problem in the RFID tag identification process. The tag ID is essentially a sequence of 0/1 binary numbers. The recognition process of the query tree algorithm is similar to a virtual binary tree, the height of the tree is the ID length of the tag, and each branch is marked with the “left 0 right 1” method. The reader first sends a query command with a prefix of 0, and those tags whose ID prefix is 0 will respond to the reader and return their own ID. When a collision occurs, the reader divides the collided tag set into two subsets based on tag ID collision bit. These subsets get smaller and smaller until each subset contains only one tag. This type of algorithm requires a stack in the reader to store the query prefix information. The reader will continuously update the query prefix according to the collision bit and push the query prefix onto the stack. The entire recognition process will not end until the stack is null. The disadvantage of the query tree algorithm is that when the tags are dense, the signal conflicts are obviously intensified, which affects the system’s recognition performance. Pan and Wu [27] proposed the STT algorithm, which learns the distribution of tags online based on the previous query results, thereby dynamically selecting the query depth of the query tree. The shortcoming of the STT algorithm is that it assumes that the tag distribution of the subsequent query is consistent with the previously learned tag distribution. Shahzad and Liu [28] questioned this hypothesis and proposed the TH algorithm, which first uses the tag number estimation method to estimate the number of remaining tags and then estimates the ID distribution of unidentified tags and then jumps directly to the optimal layer for subsequent queries. In order to optimize the query prefix and improve the recognition efficiency of the query tree algorithm, subsequent researchers have presented a series of work on this basis, including the CT [29], CCMA [20], CwT [12], DPPS [30], and BQMT [13] algorithms. In Table 1, we summarize the features and development trends for existing representative anticollision algorithms.Table 1
Summary of various types of anticollision algorithms.
TypesRepresentativesFeaturesDevelopment trendsAloha-basedMAP [19]High estimation accuracy and high complexityReduce the complexityECD [10]Pulse detectionImprove the feasibilityFEIA [22]Slot-by-slot adjustmentEnhance initial performanceTree-basedCT [29]Remove the empty queriesFurther improve the efficiencyDPPS [30]Identify multiple tags in the same time slotOptimize query mechanismCwT [12]Window mechanism to reduce the transmitted bitsReduce the slot numberHybrid-basedBSTSA [17]First proposed hybrid architecturePerformance improvementGBSA [18]Performance limit of UHF RFIDOptimize the architecture


## 3. Performance Analysis of Anticollision Algorithms

### 3.1. Analysis of DFSA Algorithms

The DFSA algorithm is a classical representative of Aloha-based algorithm, which strictly follows the timing link of EPC C1 Gen2 standard as illustrated in Figure1. Based on the frame time slot algorithm, the DFSA algorithm estimates the number of tags in the current recognition stage through the tag estimation algorithm and adjusts the frame length at the beginning of each frame recognition stage according to the estimated number of tags to be recognized. Therefore, the key to the improvement of DFSA algorithm is (1) improve the accuracy of the estimation of the number of tags and adjust the frame length reasonably and (2) reduce the number of idle time slots and collision time slots. The workflow of the DFSA algorithm is illustrated in Figure 2.Figure 1
The timing link of EPC C1 Gen2 UHF RFID standard.Figure 2
The flowchart of the DFSA algorithm.We suppose the number of effective tags isN, and the length of frame size isF, since the probability of choosing the same time slot for anyrtags can be expressed as
(1)Pr=CNr1Fr1−1FN−r.For a successful slot, there is only one tag that sends its IDs to the reader. So, the probability of successful slot is(2)Ps=CN11F11−1FN−1.When the current time slot has no tag send ID, it is defined as an idle time slot, and its probability can be expressed as(3)Pe=1−1FN.There are only three slot statuses during the recognition process: successful slot, idle slot, and collision slot. Thus, the probability of collision slot is(4)Pc=1−Ps−Pe=1−N+F−1F1−1FN−1.According to Equations (1), (2), and (3) above, we can get the expected values of successful slot, idle slot, and collision slot as follows:
(5)Es=N1−1/FN−1,Ee=F1−1/FN,Ec=F−N+F−11−1/FN−1.We denote the system throughput as the ratio of successful slots to total slotsF, denoted as U. Thus, U is expressed as
(6)U=NF1−1FN−1.In order to satisfyU maximum, we take the derivative of F on both sides of Equation (6) and make it equal to 0; we then have
(7)dUdF=NN−FF−1N−2FN+1=0.From Equation (7), we can know that in order to maximize U, there are two possibilities for the value of F, either F=1 or F=N. Considering the actual situation, the number of tags in the coverage of the reader is usually much greater than 1. Therefore, we find that the F value that satisfies maximal U is N. That is, when the given frame length is equal to the number of tags to be identified, the anticollision algorithm can achieve the maximum system throughput.Figure3 reveals the relationship between U, Pe, and Pc under different tag numbers and different frame lengths. We can see from Figure 2 that each curve about U corresponds to a peak point, which is approximately equal to 0.368, which is obtained when F=N. Since the reader does not know the specific number of tags before identification, the purpose of the DFSA algorithm is to estimate the number of remaining tags so as to approach the performance to 0.368. Therefore, 0.368 has also become the performance bottleneck of the traditional DFSA algorithm. My research found that the reason for this bottleneck is that the current DFSA algorithm framework is aimed at all unread tags, and the reader sets a relatively large frame length to identify them. From Equation (6), we know that when F approaches infinity, the value of U approaches 0.368. When F is small, the value of U can be greater than 0.368. For example, when F=N=2, the value of U is 0.5. This phenomenon stimulates the design of an independent frame recognition scheme, so that system throughput of the anticollision algorithm exceeds 0.368. Let us do a simple theoretical derivation to verify this point.Figure 3
U, Pe, and Pc for different N and F values.According to the definition of system throughput, we know that it can be redefined asN divided by the total number of time slots to identify N tags. Accordingly, Equation (6) can be rewritten as the following formula:
(8)U=NF+A,where A represents the expected number of remaining time slots required for the reader to recognize N tags except for the initial frame F. Similarly, according to the calculation formula of system throughput, we can get
(9)A=Nrest1−1/NrestNrest−1,in which Nrest means the number of remaining tags. We know that before the end of the entire tag identification process, there are always collision slots, and the sum of the tags involved in all collision slots is the remaining tags. Thus, we have
(10)Nrest=∑i=1mri.Herein,m is the number of collision slots counted in the initial frame, and ri represents the number of tags involved in i-th collision slot. We assume that the idea of the new anticollision algorithm (designed in this paper) is to independently allocate a small frame for each collision slot to identify it; then, the system throughput of the algorithm can be derived as follows:
(11)Unew=NF+B,B=∑i=1mki1−1/kiki−1.Assume that among all collision slots, thelth time slot involves the largest number of tags, and the number of tags included is kl. So, we have
(12)B<B∗=∑i=1mki1−1/klkl−1.Obviously, the function of1−1/xx−1 is a monotonically decreasing function. From this, we can deduce
(13)Unew∗=NF+B∗>UDFSA=NF+A.The reason why the above formula holds is thatNrest>kl. Therefore, we have
(14)Unew>Unew∗>UDFSA.We prove through the above derivation that in the same multitag recognition scenario, the system throughput of the new algorithm can break through the performance bottleneck of the traditional DFSA algorithm. It is worth noting that the new algorithm here only refers to the concept and idea we put forward, and the detailed algorithm design is not the focus of this paper.


### 3.2. Analysis of Query Tree Algorithms

Unlike the DFSA algorithms, the query tree- (QT-) based algorithms do not have a common performance upper bound. Therefore, different optimization methods for query prefixes may result in large differences in final performance. The timing of QT-based algorithms usually follows the ISO-18000-6B standard, as shown in Figure4. The workflow of QT-based algorithm is illustrated in Figure 5. Since there will be differences in the performance of each QT algorithm, we choose several representative QT algorithms for performance analysis here.
(1)
Collision tree (CT) algorithmFigure 4
The timing link of ISO 18000-6B RFID standard.Figure 5
The workflow of the QT-based algorithm.The basic principle of the CT algorithm is that the reader sets the highest collision bit of the received string to 0 and 1, respectively; generates a new query prefix; and sends a new query command in the next time slot. The tag that receives the query command only needs to return the remaining ID information after matching the prefix. Compared with the traditional QT algorithm, the advantage of the CT algorithm is that it eliminates idle time slots in the query process and reduces the amount of data transmission in the time slot.Assuming that there are 5 tags (A, B, C, D, and E) in the current reader’s working domain, their IDs are “0010,” “0101,” “1101,” and “1110.” The reader uses the QT algorithm to recognize them, and the detailed recognition process is shown in Table2.Table 2
An recognition example by using QT algorithm.
SlotQuery prefixResponding data from tagsSlot status1Empty stringƐxxxxCollided200xxxCollided3000010Successfully identify A4010101Successfully identify B5111xxCollided610Idle71111xxCollided81101101Successfully identify C91111110Successfully identify DWe can observe in Table2 that it takes 9 time slots for the reader to recognize these 5 tags using the QT algorithm. The recognition process of the QT anticollision algorithm is similar to traversing a binary tree, and each node on the tree will be detected. We can see that in the QT algorithm, each tag replies with a complete ID, which undoubtedly increases the communication complexity in the recognition process. In addition, when the number of tags to be identified is large, the QT algorithm will generate a large number of idle time slots, thereby further reducing performance. Since the CT algorithm eliminates idle nodes on the basis of the QT algorithm, the binary traversal tree corresponding to the CT algorithm only contains collision nodes (intermediate nodes) and leaf nodes, thereby improving the recognition efficiency.Assuming that there are n tags to be identified in the RFID system, the reader uses CT algorithm to identify them; the total number of time slots required can be expressed as(15)Nt=Nc+n,where Nc represents the number of collision nodes in the traversal tree. We know that a collision node will produce 2 child nodes, so Nt can be further rewritten as
(16)Nt=2×Nc+1.Comparing Equations (15) and (16), we can have
(17)Nc=n−1.Therefore, the total number of slots required by the CT algorithm to identifyn tags can be expressed as
(18)Nt=2×n−1.According to the definition of system throughput, we can know that the maximum system throughput of CT algorithm is(19)UCT=limn⟶∞n2n−1=limn⟶∞12−1/n=12.Through formula (19), we know that the performance of the CT algorithm is relatively stable, and its system throughput is maintained at 50%. However, it is essentially a binary tree search. When the collision is obvious, the search process cannot be accelerated.
(2)
CCMA algorithmThe CCMA algorithm is a multiary search algorithm, which introduces a custom query command and a collision string mapping mechanism. The mapping relationship of collision data is shown in Table3. The main idea of the CCMA algorithm is that if the reader detects that the first and second collision bits are continuous, the reader will send a custom query command, namely, QueryP in the next time slot to make the involved tag return a 4-bit mapping string to replace the original ID prefix information. This mapping string can accurately reflect the collision information of the tag. The reader can accurately identify the first 2 bits of collision information of the tag through the received mapping string to determine the next query command. If the first and second collision bits are not consecutive, the reader will use the CT algorithm to identify the tag.Table 3
The mapping table used in CCMA algorithm.
Collision informationMapped string000001010010100100111000The authors in [20] only give the simulation results of the CCMA algorithm. In order to better evaluate the performance of the QT algorithm, we do the following analysis of the CCMA algorithm. Similarly, we assume that there are n tags in the RFID system, and the reader uses the CCMA algorithm to recognize them. The total number of time slots required is
(20)Nt=Pcc×Ncc+Psc×Nsc,where Ncc is the number of time slots required to identify n tags when all collisions are continuous collisions and Nsc is the number of time slots required to identify n tags when all collisions are noncontinuous. Pcc and Psc are the probability of continuous collision and discontinuous collision, respectively.Lemma 1.
Assuming that all collisions in the multitag recognition process are noncontinuous collisions, the number of time slots required by the CCMA algorithm to identifyn tags is Nccma=2×n−1.Proof.
In the entire tag recognition process, when all the detected collisions are noncontinuous, the recognition process of the CCMA algorithm is similar to the CT algorithm, at this time,Nsc=2×Nc+1=2×n−1. Thus, Lemma 1 is proved.Lemma 2.
In the entire tag recognition process, when all the detected collisions are continuous, the number of time slots used by the CCMA algorithm to recognizen tags is Ncc=20×n−11/9.Proof.
When all detected collisions are continuous, the recognition process of the CCMA algorithm is similar to a complete quaternary traversal tree. The collision node in the tree will produce 4 child nodes, soN4=Nl+Nc=4×Nc+1, where Nl and Nc denote the number of leaf nodes and collision nodes in the tree; we have
(21)Nl=3×Nc+1.
In the quaternary traversal tree, the leaf nodes may be successful nodes or idle nodes, so the above formula can be rewritten as(22)n+Ni=3×Nc+1.
In the CCMA algorithm, the number of idle nodes that a continuous collision node may produce is between 0 and 2. The CCMA algorithm can eliminate idle time slots through the QueryP command. Next, we consider the following three scenarios, respectively.
Scenario A: when the number of idle nodes generated by a continuous collision node is 0, Ni=0, and Nc=n−1/3 can be obtained from Equation (22). We substitute it into N4=4×Nc+1 to get N4=4×n−1/3. According to the principle of the CCMA algorithm, the number of sending the custom command QueryP in the CCMA algorithm is the number of consecutive collisions (i.e., Nc), so Ncc=N4−Ni+Nc=5×n−2/3.
Scenario B: when the number of idle nodes generated by a continuous collision node is 1, Ni=Nc, Nc=n−1/2 can be obtained from Equation (22), and substituting it into N4=4×Nc+1, we can find N4=2×n−1. Further, we can find Ncc=2×n−1.
Scenario C: when the number of idle nodes generated by a continuous collision node is 2, similarly, Ncc=3×n−2 can be obtained.
Since the above three scenarios appear with equal probability, we can getNcc=20×n−11/9; therefore, Lemma 2 is proved.Considering that in the process of tag recognition, the probability of continuous collision and discontinuous collision is 0.5, combining Lemmas1 and 2, formula (20) can be rewritten as
(23)Nt=12Nsc+12Ncc=19×n−109.Therefore, the maximum system throughput that the CCMA algorithm can achieve can be expressed as(24)UCCMA=limn⟶∞9n19n−10=919−10/n≈0.4736.From Equation (24), we can know that the system throughput that the CCMA algorithm can maintain is slightly lower than that of the CT algorithm, but the amount of data transmission required is lower than that of the CT algorithm.
(3)
DPPS algorithmThe performance analysis of the current mainstream QT anticollision algorithms shows that the recognition performance of the QT algorithm has a higher room for improvement. A typical idea is to optimize the response mechanism of the tag, and its representative is the DPPS algorithm. The basic principle of the DPPS algorithm is that the reader sends a query command to all tags within its coverage area, and when the tag receives this command, it will return its own complete ID. Once a collision is detected, the reader will update the query prefix based on the parsed data and send the PROBE_EQ command to probe the tag in the next time slot. There are 3 key parameters in the PROBE_EQ command. First is COM_Str, which represents the data part of the tag ID before the collision bit; second is Pre1, which represents prefix 1; and third is Pre2, which represents prefix 2. The value of Pre2 is equal to the value of Pre1 minus one. We can also make the following derivation to analyze the performance of the DPPS algorithm. In the DPPS algorithm, we useNslots to represent the sum of the number of successful slots, complete collision slots, and identifiable collision slots. Let ENslots be defined as the expected value of Nslots. According to the principle of the DPPS algorithm, ENslots can be expressed as
(25)ENslots=1+Nc,where Nc is the number of ID collisions during the recognition process.Lemma 3.
Similarly, we assume that there aren tags to be identified in the system, and the reader uses the DPPS algorithm to identify them; then, the expected total number of time slots ENslots is equal to n.Proof.
The recognition process of the DPPS algorithm is similar to a variant of a binary traversal tree, and each node on the tree corresponds to a time slot. For the convenience of analysis, we treat both identifiable collisions and complete collisions as collision nodes. Obviously, a collision node will produce 2 child nodes, so the total number of nodes on the traversal tree is2Nc+1=Nc+n. It can be seen that Nc=n−1. According to formula (25), we know that ENslots=1+n−1=n. Therefore, Lemma 3 is proved.Above, we analyzed the performance of three typical QT algorithms. Through analysis, we know that the performance improvement of QT algorithms mainly depends on the query mechanism of the reader and the response mechanism of the tag. By optimizing these two mechanisms, the performance of tag recognition can be continuously improved. Through Lemma3, we know that the DPPS algorithm only needs n time slots to identify n tags, and its system throughput reaches 100%. However, this does not mean that the performance of QT anticollision algorithms has reached the limit. The reason is that in the DPPS algorithm, the length of a single time slot is longer than the length of the time slot in the traditional algorithm, so the actual improvement effect is not so high. Therefore, there is still much room for improvement in the performance of QT algorithms.


## 3.1. Analysis of DFSA Algorithms

The DFSA algorithm is a classical representative of Aloha-based algorithm, which strictly follows the timing link of EPC C1 Gen2 standard as illustrated in Figure1. Based on the frame time slot algorithm, the DFSA algorithm estimates the number of tags in the current recognition stage through the tag estimation algorithm and adjusts the frame length at the beginning of each frame recognition stage according to the estimated number of tags to be recognized. Therefore, the key to the improvement of DFSA algorithm is (1) improve the accuracy of the estimation of the number of tags and adjust the frame length reasonably and (2) reduce the number of idle time slots and collision time slots. The workflow of the DFSA algorithm is illustrated in Figure 2.Figure 1
The timing link of EPC C1 Gen2 UHF RFID standard.Figure 2
The flowchart of the DFSA algorithm.We suppose the number of effective tags isN, and the length of frame size isF, since the probability of choosing the same time slot for anyrtags can be expressed as
(1)Pr=CNr1Fr1−1FN−r.For a successful slot, there is only one tag that sends its IDs to the reader. So, the probability of successful slot is(2)Ps=CN11F11−1FN−1.When the current time slot has no tag send ID, it is defined as an idle time slot, and its probability can be expressed as(3)Pe=1−1FN.There are only three slot statuses during the recognition process: successful slot, idle slot, and collision slot. Thus, the probability of collision slot is(4)Pc=1−Ps−Pe=1−N+F−1F1−1FN−1.According to Equations (1), (2), and (3) above, we can get the expected values of successful slot, idle slot, and collision slot as follows:
(5)Es=N1−1/FN−1,Ee=F1−1/FN,Ec=F−N+F−11−1/FN−1.We denote the system throughput as the ratio of successful slots to total slotsF, denoted as U. Thus, U is expressed as
(6)U=NF1−1FN−1.In order to satisfyU maximum, we take the derivative of F on both sides of Equation (6) and make it equal to 0; we then have
(7)dUdF=NN−FF−1N−2FN+1=0.From Equation (7), we can know that in order to maximize U, there are two possibilities for the value of F, either F=1 or F=N. Considering the actual situation, the number of tags in the coverage of the reader is usually much greater than 1. Therefore, we find that the F value that satisfies maximal U is N. That is, when the given frame length is equal to the number of tags to be identified, the anticollision algorithm can achieve the maximum system throughput.Figure3 reveals the relationship between U, Pe, and Pc under different tag numbers and different frame lengths. We can see from Figure 2 that each curve about U corresponds to a peak point, which is approximately equal to 0.368, which is obtained when F=N. Since the reader does not know the specific number of tags before identification, the purpose of the DFSA algorithm is to estimate the number of remaining tags so as to approach the performance to 0.368. Therefore, 0.368 has also become the performance bottleneck of the traditional DFSA algorithm. My research found that the reason for this bottleneck is that the current DFSA algorithm framework is aimed at all unread tags, and the reader sets a relatively large frame length to identify them. From Equation (6), we know that when F approaches infinity, the value of U approaches 0.368. When F is small, the value of U can be greater than 0.368. For example, when F=N=2, the value of U is 0.5. This phenomenon stimulates the design of an independent frame recognition scheme, so that system throughput of the anticollision algorithm exceeds 0.368. Let us do a simple theoretical derivation to verify this point.Figure 3
U, Pe, and Pc for different N and F values.According to the definition of system throughput, we know that it can be redefined asN divided by the total number of time slots to identify N tags. Accordingly, Equation (6) can be rewritten as the following formula:
(8)U=NF+A,where A represents the expected number of remaining time slots required for the reader to recognize N tags except for the initial frame F. Similarly, according to the calculation formula of system throughput, we can get
(9)A=Nrest1−1/NrestNrest−1,in which Nrest means the number of remaining tags. We know that before the end of the entire tag identification process, there are always collision slots, and the sum of the tags involved in all collision slots is the remaining tags. Thus, we have
(10)Nrest=∑i=1mri.Herein,m is the number of collision slots counted in the initial frame, and ri represents the number of tags involved in i-th collision slot. We assume that the idea of the new anticollision algorithm (designed in this paper) is to independently allocate a small frame for each collision slot to identify it; then, the system throughput of the algorithm can be derived as follows:
(11)Unew=NF+B,B=∑i=1mki1−1/kiki−1.Assume that among all collision slots, thelth time slot involves the largest number of tags, and the number of tags included is kl. So, we have
(12)B<B∗=∑i=1mki1−1/klkl−1.Obviously, the function of1−1/xx−1 is a monotonically decreasing function. From this, we can deduce
(13)Unew∗=NF+B∗>UDFSA=NF+A.The reason why the above formula holds is thatNrest>kl. Therefore, we have
(14)Unew>Unew∗>UDFSA.We prove through the above derivation that in the same multitag recognition scenario, the system throughput of the new algorithm can break through the performance bottleneck of the traditional DFSA algorithm. It is worth noting that the new algorithm here only refers to the concept and idea we put forward, and the detailed algorithm design is not the focus of this paper.


## 3.2. Analysis of Query Tree Algorithms

Unlike the DFSA algorithms, the query tree- (QT-) based algorithms do not have a common performance upper bound. Therefore, different optimization methods for query prefixes may result in large differences in final performance. The timing of QT-based algorithms usually follows the ISO-18000-6B standard, as shown in Figure4. The workflow of QT-based algorithm is illustrated in Figure 5. Since there will be differences in the performance of each QT algorithm, we choose several representative QT algorithms for performance analysis here.
(1)
Collision tree (CT) algorithmFigure 4
The timing link of ISO 18000-6B RFID standard.Figure 5
The workflow of the QT-based algorithm.The basic principle of the CT algorithm is that the reader sets the highest collision bit of the received string to 0 and 1, respectively; generates a new query prefix; and sends a new query command in the next time slot. The tag that receives the query command only needs to return the remaining ID information after matching the prefix. Compared with the traditional QT algorithm, the advantage of the CT algorithm is that it eliminates idle time slots in the query process and reduces the amount of data transmission in the time slot.Assuming that there are 5 tags (A, B, C, D, and E) in the current reader’s working domain, their IDs are “0010,” “0101,” “1101,” and “1110.” The reader uses the QT algorithm to recognize them, and the detailed recognition process is shown in Table2.Table 2
An recognition example by using QT algorithm.
SlotQuery prefixResponding data from tagsSlot status1Empty stringƐxxxxCollided200xxxCollided3000010Successfully identify A4010101Successfully identify B5111xxCollided610Idle71111xxCollided81101101Successfully identify C91111110Successfully identify DWe can observe in Table2 that it takes 9 time slots for the reader to recognize these 5 tags using the QT algorithm. The recognition process of the QT anticollision algorithm is similar to traversing a binary tree, and each node on the tree will be detected. We can see that in the QT algorithm, each tag replies with a complete ID, which undoubtedly increases the communication complexity in the recognition process. In addition, when the number of tags to be identified is large, the QT algorithm will generate a large number of idle time slots, thereby further reducing performance. Since the CT algorithm eliminates idle nodes on the basis of the QT algorithm, the binary traversal tree corresponding to the CT algorithm only contains collision nodes (intermediate nodes) and leaf nodes, thereby improving the recognition efficiency.Assuming that there are n tags to be identified in the RFID system, the reader uses CT algorithm to identify them; the total number of time slots required can be expressed as(15)Nt=Nc+n,where Nc represents the number of collision nodes in the traversal tree. We know that a collision node will produce 2 child nodes, so Nt can be further rewritten as
(16)Nt=2×Nc+1.Comparing Equations (15) and (16), we can have
(17)Nc=n−1.Therefore, the total number of slots required by the CT algorithm to identifyn tags can be expressed as
(18)Nt=2×n−1.According to the definition of system throughput, we can know that the maximum system throughput of CT algorithm is(19)UCT=limn⟶∞n2n−1=limn⟶∞12−1/n=12.Through formula (19), we know that the performance of the CT algorithm is relatively stable, and its system throughput is maintained at 50%. However, it is essentially a binary tree search. When the collision is obvious, the search process cannot be accelerated.
(2)
CCMA algorithmThe CCMA algorithm is a multiary search algorithm, which introduces a custom query command and a collision string mapping mechanism. The mapping relationship of collision data is shown in Table3. The main idea of the CCMA algorithm is that if the reader detects that the first and second collision bits are continuous, the reader will send a custom query command, namely, QueryP in the next time slot to make the involved tag return a 4-bit mapping string to replace the original ID prefix information. This mapping string can accurately reflect the collision information of the tag. The reader can accurately identify the first 2 bits of collision information of the tag through the received mapping string to determine the next query command. If the first and second collision bits are not consecutive, the reader will use the CT algorithm to identify the tag.Table 3
The mapping table used in CCMA algorithm.
Collision informationMapped string000001010010100100111000The authors in [20] only give the simulation results of the CCMA algorithm. In order to better evaluate the performance of the QT algorithm, we do the following analysis of the CCMA algorithm. Similarly, we assume that there are n tags in the RFID system, and the reader uses the CCMA algorithm to recognize them. The total number of time slots required is
(20)Nt=Pcc×Ncc+Psc×Nsc,where Ncc is the number of time slots required to identify n tags when all collisions are continuous collisions and Nsc is the number of time slots required to identify n tags when all collisions are noncontinuous. Pcc and Psc are the probability of continuous collision and discontinuous collision, respectively.Lemma 1.
Assuming that all collisions in the multitag recognition process are noncontinuous collisions, the number of time slots required by the CCMA algorithm to identifyn tags is Nccma=2×n−1.Proof.
In the entire tag recognition process, when all the detected collisions are noncontinuous, the recognition process of the CCMA algorithm is similar to the CT algorithm, at this time,Nsc=2×Nc+1=2×n−1. Thus, Lemma 1 is proved.Lemma 2.
In the entire tag recognition process, when all the detected collisions are continuous, the number of time slots used by the CCMA algorithm to recognizen tags is Ncc=20×n−11/9.Proof.
When all detected collisions are continuous, the recognition process of the CCMA algorithm is similar to a complete quaternary traversal tree. The collision node in the tree will produce 4 child nodes, soN4=Nl+Nc=4×Nc+1, where Nl and Nc denote the number of leaf nodes and collision nodes in the tree; we have
(21)Nl=3×Nc+1.
In the quaternary traversal tree, the leaf nodes may be successful nodes or idle nodes, so the above formula can be rewritten as(22)n+Ni=3×Nc+1.
In the CCMA algorithm, the number of idle nodes that a continuous collision node may produce is between 0 and 2. The CCMA algorithm can eliminate idle time slots through the QueryP command. Next, we consider the following three scenarios, respectively.
Scenario A: when the number of idle nodes generated by a continuous collision node is 0, Ni=0, and Nc=n−1/3 can be obtained from Equation (22). We substitute it into N4=4×Nc+1 to get N4=4×n−1/3. According to the principle of the CCMA algorithm, the number of sending the custom command QueryP in the CCMA algorithm is the number of consecutive collisions (i.e., Nc), so Ncc=N4−Ni+Nc=5×n−2/3.
Scenario B: when the number of idle nodes generated by a continuous collision node is 1, Ni=Nc, Nc=n−1/2 can be obtained from Equation (22), and substituting it into N4=4×Nc+1, we can find N4=2×n−1. Further, we can find Ncc=2×n−1.
Scenario C: when the number of idle nodes generated by a continuous collision node is 2, similarly, Ncc=3×n−2 can be obtained.
Since the above three scenarios appear with equal probability, we can getNcc=20×n−11/9; therefore, Lemma 2 is proved.Considering that in the process of tag recognition, the probability of continuous collision and discontinuous collision is 0.5, combining Lemmas1 and 2, formula (20) can be rewritten as
(23)Nt=12Nsc+12Ncc=19×n−109.Therefore, the maximum system throughput that the CCMA algorithm can achieve can be expressed as(24)UCCMA=limn⟶∞9n19n−10=919−10/n≈0.4736.From Equation (24), we can know that the system throughput that the CCMA algorithm can maintain is slightly lower than that of the CT algorithm, but the amount of data transmission required is lower than that of the CT algorithm.
(3)
DPPS algorithmThe performance analysis of the current mainstream QT anticollision algorithms shows that the recognition performance of the QT algorithm has a higher room for improvement. A typical idea is to optimize the response mechanism of the tag, and its representative is the DPPS algorithm. The basic principle of the DPPS algorithm is that the reader sends a query command to all tags within its coverage area, and when the tag receives this command, it will return its own complete ID. Once a collision is detected, the reader will update the query prefix based on the parsed data and send the PROBE_EQ command to probe the tag in the next time slot. There are 3 key parameters in the PROBE_EQ command. First is COM_Str, which represents the data part of the tag ID before the collision bit; second is Pre1, which represents prefix 1; and third is Pre2, which represents prefix 2. The value of Pre2 is equal to the value of Pre1 minus one. We can also make the following derivation to analyze the performance of the DPPS algorithm. In the DPPS algorithm, we useNslots to represent the sum of the number of successful slots, complete collision slots, and identifiable collision slots. Let ENslots be defined as the expected value of Nslots. According to the principle of the DPPS algorithm, ENslots can be expressed as
(25)ENslots=1+Nc,where Nc is the number of ID collisions during the recognition process.Lemma 3.
Similarly, we assume that there aren tags to be identified in the system, and the reader uses the DPPS algorithm to identify them; then, the expected total number of time slots ENslots is equal to n.Proof.
The recognition process of the DPPS algorithm is similar to a variant of a binary traversal tree, and each node on the tree corresponds to a time slot. For the convenience of analysis, we treat both identifiable collisions and complete collisions as collision nodes. Obviously, a collision node will produce 2 child nodes, so the total number of nodes on the traversal tree is2Nc+1=Nc+n. It can be seen that Nc=n−1. According to formula (25), we know that ENslots=1+n−1=n. Therefore, Lemma 3 is proved.Above, we analyzed the performance of three typical QT algorithms. Through analysis, we know that the performance improvement of QT algorithms mainly depends on the query mechanism of the reader and the response mechanism of the tag. By optimizing these two mechanisms, the performance of tag recognition can be continuously improved. Through Lemma3, we know that the DPPS algorithm only needs n time slots to identify n tags, and its system throughput reaches 100%. However, this does not mean that the performance of QT anticollision algorithms has reached the limit. The reason is that in the DPPS algorithm, the length of a single time slot is longer than the length of the time slot in the traditional algorithm, so the actual improvement effect is not so high. Therefore, there is still much room for improvement in the performance of QT algorithms.


## 4. Experimental Results and Analysis

### 4.1. Experiment Setup

In the experiment section, we measure the performance of the RFID anticollision through some common metrics such as system throughput, total number of time slots, and recognition efficiency and compared with our analysis results to verify the effectiveness of our theoretical analysis. The simulations are performed on the desktop computer with Intel Core i5-4590 CPU and 8 GB RAM. All experiments are realized through MATLAB program. Since the performance analysis results of most DFSA algorithms are similar and close (below 0.368), we choose the more classic Q-algorithm and MAP algorithm as reference. In the QT-based algorithms, we choose the CCMA and CT algorithm as the reference algorithms. The experimental parameters are listed in Table4 [31–33]. In order to ensure the convergence of the results, we independently repeat the experiments 1000 times and then take the average value as the final result [34].Table 4
The experimental parameters used in this paper.
ParameterValueThe number of tags(100, 1000)The length of IDs96Communication rate40 kbpsT125μsT225μsT312.5μs


### 4.2. Result Analysis

Figure6 compares the total number of time slots required by different algorithms to recognize the same quantity of tags. The comparative algorithms include Q-algorithm [9], MAP [19], CCMA [20], CT [29], and the new design concept proposed in this paper (named new idea in the simulations). It can be observed from the figure that when the QT algorithm recognizes the same number of tags, the number of time slots spent is significantly lower than that of the DFSA algorithm. Among the two QT algorithms, the CT algorithm spends less time slots than the CCMA algorithm, which is also consistent with the theoretical analysis results. Among three DFSA algorithms, the number of time slots consumed by the Q-algorithm and the MAP algorithm is very close, while the number of time slots consumed by the new idea is significantly lower than that by the other two DFSA algorithms.Figure 6
Experimental results: the total slot numbers by various algorithms.Figure7 depicts the system throughput that can be achieved under different algorithms. From the simulation results, we can further observe that the system throughput of QT algorithm is generally higher than that of DFSA algorithms. Through our previous theoretical analysis, we can see that the system throughput of most DFSA algorithms is lower than 0.368. This experimental result also further verifies our theoretical analysis. The throughput of the Q-algorithm and MAP algorithm is very close. Their average throughput is 0.3388 and 0.3398, respectively, which is 8.6% and 8.3% away from the theoretical maximum value. We can further observe that the average throughput that new idea algorithm can achieve is 0.4192 and 13.9% higher than the maximum throughput of the existing DFSA algorithms. The average throughput of the CT and CCMA algorithm is 0.5 and 0.453, respectively. The gap between the average throughput of the CCMA algorithm and the theoretical analysis is 4%. The reason is that the number of simulations is not set large enough.Figure 7
Experimental results: system throughput of various algorithms.


### 4.3. Challenges and Future Trends

We have verified through theoretical analysis and experiments that many of the current anticollision algorithms can alleviate the problem of multitag recognition to a certain extent, but there are still some problems in the recognition efficiency, complexity, stability, etc., which cannot meet the large-scale RFID systems. In summary, there are following problems:(1)
The existing tag quantity estimation methods cannot be applied to low-cost RFID systems. Existing research on anticollision algorithms is excessively pursuing accuracy in the estimation of the tag quantity, which makes the complexity of the algorithm increase sharply. Taking into account the limitation of the computing power of the RFID platform, the high-complexity algorithm cannot be applied to the low-cost RFID systems(2)
Existing anticollision technologies are facing performance bottlenecks. Most anticollision algorithms are based on a channel with only one tag reply, so that the reader can decode it correctly. The collision information is discarded, and the tag needs to be retransmitted. This undoubtedly wastes a lot of useful information and restricts the further improvement of the recognition efficiency of the anticollision algorithm


## 4.1. Experiment Setup

In the experiment section, we measure the performance of the RFID anticollision through some common metrics such as system throughput, total number of time slots, and recognition efficiency and compared with our analysis results to verify the effectiveness of our theoretical analysis. The simulations are performed on the desktop computer with Intel Core i5-4590 CPU and 8 GB RAM. All experiments are realized through MATLAB program. Since the performance analysis results of most DFSA algorithms are similar and close (below 0.368), we choose the more classic Q-algorithm and MAP algorithm as reference. In the QT-based algorithms, we choose the CCMA and CT algorithm as the reference algorithms. The experimental parameters are listed in Table4 [31–33]. In order to ensure the convergence of the results, we independently repeat the experiments 1000 times and then take the average value as the final result [34].Table 4
The experimental parameters used in this paper.
ParameterValueThe number of tags(100, 1000)The length of IDs96Communication rate40 kbpsT125μsT225μsT312.5μs


## 4.2. Result Analysis

Figure6 compares the total number of time slots required by different algorithms to recognize the same quantity of tags. The comparative algorithms include Q-algorithm [9], MAP [19], CCMA [20], CT [29], and the new design concept proposed in this paper (named new idea in the simulations). It can be observed from the figure that when the QT algorithm recognizes the same number of tags, the number of time slots spent is significantly lower than that of the DFSA algorithm. Among the two QT algorithms, the CT algorithm spends less time slots than the CCMA algorithm, which is also consistent with the theoretical analysis results. Among three DFSA algorithms, the number of time slots consumed by the Q-algorithm and the MAP algorithm is very close, while the number of time slots consumed by the new idea is significantly lower than that by the other two DFSA algorithms.Figure 6
Experimental results: the total slot numbers by various algorithms.Figure7 depicts the system throughput that can be achieved under different algorithms. From the simulation results, we can further observe that the system throughput of QT algorithm is generally higher than that of DFSA algorithms. Through our previous theoretical analysis, we can see that the system throughput of most DFSA algorithms is lower than 0.368. This experimental result also further verifies our theoretical analysis. The throughput of the Q-algorithm and MAP algorithm is very close. Their average throughput is 0.3388 and 0.3398, respectively, which is 8.6% and 8.3% away from the theoretical maximum value. We can further observe that the average throughput that new idea algorithm can achieve is 0.4192 and 13.9% higher than the maximum throughput of the existing DFSA algorithms. The average throughput of the CT and CCMA algorithm is 0.5 and 0.453, respectively. The gap between the average throughput of the CCMA algorithm and the theoretical analysis is 4%. The reason is that the number of simulations is not set large enough.Figure 7
Experimental results: system throughput of various algorithms.


## 4.3. Challenges and Future Trends

We have verified through theoretical analysis and experiments that many of the current anticollision algorithms can alleviate the problem of multitag recognition to a certain extent, but there are still some problems in the recognition efficiency, complexity, stability, etc., which cannot meet the large-scale RFID systems. In summary, there are following problems:(1)
The existing tag quantity estimation methods cannot be applied to low-cost RFID systems. Existing research on anticollision algorithms is excessively pursuing accuracy in the estimation of the tag quantity, which makes the complexity of the algorithm increase sharply. Taking into account the limitation of the computing power of the RFID platform, the high-complexity algorithm cannot be applied to the low-cost RFID systems(2)
Existing anticollision technologies are facing performance bottlenecks. Most anticollision algorithms are based on a channel with only one tag reply, so that the reader can decode it correctly. The collision information is discarded, and the tag needs to be retransmitted. This undoubtedly wastes a lot of useful information and restricts the further improvement of the recognition efficiency of the anticollision algorithm


## 5. Conclusions

This paper analyzes the current mainstream anticollision algorithms and conducts theoretical analysis and simulation on their performance. Based on the analysis of the reasons for the limited performance of the existing DFSA algorithm, a new DFSA algorithm architecture is proposed, and theoretical analysis and simulation results prove that it can break through the performance bottleneck of the current DFSA algorithm. Finally, we summarize the existing research on anticollision algorithms and present the current challenges and future research trends.



---

*Source: 6883591-2021-12-14.xml*