Algorithm Aids RFID Anti-Collision Success
This file type includes high resolution graphics and schematics when applicable.
For all of their convenience, radio-frequency-identification (RFID) systems have several shortcomings, including problems with signal collisions in crowded electromagnetic (EM) environments. Fortunately, it is possible to analyze and understand the factors responsible for these collisions.1 Through such analysis, it was possible to develop an improved adaptive slot-count (IAS) RFID anti-collision algorithm for greatly improved RFID performance, with higher tag recognition rates and greater throughput rates.
A Q algorithm is used as the basis of the new RFID anti-collision algorithm. It has a frame length designed as 2Q.2-4 When the frame size must be adjusted, the RFID reader sends a Q value to the RFID tag, then each tag randomly selects a value from (0, 2Q – 1) as its slot in response to the reader and then the slotted tag sends its own identification (ID) information to the RFID reader. Based on the response state of a tag, the reader adjusts the Q parameter.5
Figure 1 shows the method for the Q algorithm to adjust the frame length. The algorithm defines a floating number, Qfp, and a constant, C, with typical value of C being 0.1 < C < 0.5. Based on a current slot state, the Q algorithm updates the Qfp value adaptively, and Qfp is rounded down to an integer value, Q. When the current slot collision occurs, Qfp increases C; when the current slot is idle, Qfp decreases C; and when the current slot successfully identifies a tag, Qfp remains unchanged, as in the algorithm flow chart of Fig. 1.
Assuming a frame length of L in the Q algorithm, the total number of tag(s) is represented as N and the probability of M tag(s) in a slot is subject to a binomial distribution. The probability of recognition, which is the probability that only one tag exists in a slot, is depicted by Eq. 1:
Since L slot(s) exists in one frame, the number of tag(s) that can be identified in a frame is found by means of Eq. 2:
The throughput rate of the Q algorithm, ηQ, can be found by Eq. 3:
If T1 represents the time for collision detection of tags, and T2 is the time required to successfully identify a tag, the recognition efficiency of the Q algorithm, EQ, can be found by means of Eq. 4:
In the case where β = T2/T1, due to ηQ = S/L,
In the Q algorithm, the frame length can be quickly adjusted to an optimum length by modifying the Q value.6 Also, EQ has been greatly promoted in the Q algorithm compared to the RFID dynamic frame slot algorithm (DFSA).7 However, to achieve an optimal frame length using the Q algorithm, the Q value must be frequently adjusted, which increases the amount of communication required between reader and tags. Meanwhile, the reader randomly selects values each time, consuming system resources and reducing EQ. An evaluation of different RFID anti-collision algorithms may serve to help enhance the Q algorithm.
In a binary tree (BT) anti-collision algorithm,8-11 for example, each tag has a counter and a random number generator that can generate 0 or 1. At the beginning, the counter value of each tag is 0 and the tag card is in the waiting state. When a reader sends a query command, the tag with the counter showing 0 responds. When two tags collide, the one showing 0 is randomly added with 0 or 1. As a result, the tags on collision bits are classified into two sub trees, and the tag which counter does not show 0 is directly added with 1.
If no collision is detected by the reader, the counter values of all tags subtract 1. Whether or not it is 0 is then determined, so as to decide whether the tags are to respond to the reader or continue to wait. Such loop detection continues until all tags are identified. In the event that the random values generated by the tags are always 1 for a given period of time, the tags will remain in a waiting state and not be recognized. Therefore, the BT algorithm is a possible solution for use as an RFID anti-collision algorithm. Where there are few RFID tags, the recognition efficiency of the BT algorithm is not very high. But where the number of tags is large, it has a high recognition speed.12,13
The BT anti-collision algorithm dictates that when N tags collide, they are grouped by randomly selecting 0 and 1. As shown in Eqs. 6 and 7, the probability of the tags that can be separated is expressed as ps(N), while the probability of tags that cannot be separated is expressed as pf(N):14-17
From these two equations, it can be seen that the larger the number of collided tags, N, the smaller the value of tags that cannot be separated, pf(N), will be. In the case of N >> 2, the throughput rate, ηB of successfully identified N tahgs can be approximated by Eq. 8:
For the BT approach, the recognition efficiency, EB, can be found by means of Eq. 9:
Using the Q algorithm, tags can be quickly classified into different groups, and certain rules must be adopted to adjust the Q values to make the slot counts approximately equal to the number of tags to be identified. In this way, the throughput can reach a maximum rate. But if the collision resolution mechanism of the Q algorithm is ineffective, the recognition time will be extended if the Q value must be reselected.18,19
This file type includes high resolution graphics and schematics when applicable.
Searching for a Solution
This file type includes high resolution graphics and schematics when applicable.
The BT algorithm can solve the collision problem, and where there is a large number of tags, the system’s efficiency has been greatly improved. But in the BT algorithm, a root node is in turn split into child nodes and, when the number of tags is large, more collisions can take place. The IAS algorithm is divided into two phases, combining the benefits of the Q and BT algorithms with improved recognition efficiency.
Regarding improvements to the Q algorithm, determination of the optimal frame length is made by comparing the proportions of tag response collision slot, identification slot, and idle slot. If these comparisons show that the optimum frame length has been reached, the system is ready for the next step of the IAS algorithm. If not, the Q value must be changed for rejudgment. The random number selected by the collision slot is kept using queues in this process.
To allocate tags reasonably, which is to keep the sum of collision bits and idle bits small, the slot counts that are allocated should approximate the number of tags to be identified. Through analysis,20 the number of slot counts allocated is approximately equal to the corresponding proportion that the number of tags to be identified can meet. The proportional relation is:
N0: N1: NM= 2L2: 2NL: N2(1 + N/3L)
The quantities of collision slots, idle slots, and recognition slots are compared to determine the relationship between the frame length (L) and the total number of tags (N) tags to be identified. To establish some rules for the IAS algorithm, for Rule 1 (denoted as R1), in the case of N0 >2N1 and N10 >(24/7)(Nm, this indicates that l ≥ 2N and the number of slots should be reduced. For Rule 2 (denoted as R2), in the case of N0 < 2N1 and N1 < (3/5)Nm, this indicates that l ≤ (1/2)N and the number of slots should be increased.
According to these rules, the Q value can be quickly adjusted so that the number of slots that is allocated is approximately equal to the number of RFID tags to be identified. As a result, a reasonable number of slots are selected for the number of tags to be identified, to reduce collision slots and idle slots and improve the recognition speed of the tags.
Each tag has two counters, Ct1 and Ct2, in the RFID system. Counter Ct1 is used to save the random number selected by the tag, and counter Ct2 is used to back up this random number. It contains a counter (Cr) and queue (sc) in the reader, with counter Cr (Cr = 2) used to save the Q value and determine whether a slot comes to an end. Queue sc is used to save the random number selected by the collision slot. The nine related algorithm steps are as follows:
1. In the first step, the reader randomly selects one Q value and sends it to the tag to be identified, saving the value in Cr (Cr = 2Q.
2. In the second step, after the tag has received one Q value, a value among 0 – 2Q – 1 is selected randomly, then saved in Ct1; at the same time, this value is backed up in Ct2.
3. Next, the reader sends a query command and the Ct1 = 0 tag responds to it. If there is no tag response to the query command, a free slot is started. When more than one tag responds, there will be a collision slot, Ct1, of the collision tag is set to the maximum value; the Ct2 value is kept in the sc queue. If only one tag responds, there will be an identification slot, during which the tag will be identified and marked as being in the identification state.
4. In the fourth step, the reader counts Cr – 1, with the Ct1 of all other tags minus 1.
5. The fifth step is to determine whether Cr is zero. In the case where Cr ≠ 0, shift to step 3. In the case where Cr = 0, the first frame ends. In addition to the recognized tags, the collided tag Ct1 is set to the high position and Ct2 records the value initially randomly selected by each tag. The reader makes judgments based on the proportional relationship of the idle slot, the identification slot, and the collision slot in the frame. If meeting rule R1, the adjustment of Q ← Q – 1 is made, the queue sc is emptied, and the process begins again with step 1. If rule R2 is not met, move to step 6.
6. In step 6, the reader sends a command, resulting in the tag’s Ct1 = Ct2.
7. The seventh step is to determine whether the reader queue, sc, is empty. If empty, all tags have successfully identified in the first phase and it withdraws the identification process. If it is not empty, it is “dequeued” to Cr and sent a command to make the tag to be identified Ct1 ← Ct1 – Cr.
8. In the eighth step, the reader sends a query command and the Ct1 = 0 tag responds. If there is no tag response, an idle slot will result and the Ct1 for all tags will be Ct1 – 1 before repeating step 8. If multiple tags respond, a collision slot will result, with the Ct1 = 0 tag having 0 or 1 randomly added; in addition, the remaining tags will have 1 added to Ct1 before repeating step 8. If only one tag responds, there will be a recognition slot. This tag will be identified and marked in the identification state, with Ct1 – 1 assigned for the remaining tags.
9. In the final step, the reader will send a command, and the tag of counter Ct2 = Cr will respond. If multiple tags respond, there will be a collision slot. All tags will have Ct1 – 1, and a Ct1 = 0 tag will be randomly added after 0 or 1 before repeating step 8. If only one tag responds, there will be only a tag left in the collision slot to recognize the tag before going to step 7 to recognize the tag in the next collision slot.
Assuming N tags to be identified in the RFID system, the proportional relationship among N0, N1, and Nm can be classified into one of three conditions for analysis of the IAS algorithm. For the first condition, N0: N1:NM = 1: 1: 2/3.
Under this proportional relationship, L = N, there are η1 = (8/3)N tag(s) identified, and η2 = (5/8)N tag(s) collided in the (1/4)L = (1/4)N slot to start the recognition segment. Setting the number of tags contained in the ith collision bit as ki, the total number of tags identified can be expressed as:
η2 = ∑N/4i = 1ki
The total throughput of the IAS algorithm for this first condition can be found by Eq. 10:
The recognition efficiency of the IAS algorithm can be found by Eq. 11:
For the second condition, N0: N1: NM = 2: 1: 7/24. In this proportional relationship, for the case of L = 2N, the tag η1 = (48/79)N is identified and the tag η2 = (31/79)N collides in the slot (7/79)L = (14/79)N. It then starts the identification phase of:
η2 = ∑(14/79)Ni = 1ki
The total throughput of the IAS algorithm for this second condition can be found by Eq. 12:
For the third condition, N0: N1: NM = 1: 2: 10/3. In this proportional relationship, in the case of L = N/2, the tag η = (6/19)N is identified and the tag η2 = (13/19)N collides in the slot (10/19)L = (5/19)N. It then starts the identification phase where:
η2 = ∑(5/19)Ni = 1ki
Therefore, for the third condition, the total throughput of the IAS algorithm can be found by Eq. 13:
In the event that L = N/2, the recognition efficiency of the IAS algorithm is given by Eq. 14:
Figure 3 provides a comparison of the recognition efficiencies of the Q, BT, and IAS algorithms at β = 5. It shows that the IAS algorithm is superior to other two algorithms in recognition efficiency. Figure 4 indicates that in case of L = N/2, the IAS algorithm has a higher throughput but, due to β = 5, the time, T2, required to successfully recognize a tag is five times the time T1 for collision detection. Hence, the IAS algorithm has higher recognition efficiency in the case when L = N.
RFID systems have drawn upon different algorithms for operation. For example, tags can be quickly classified into different groups by means of the Q algorithm. By adjusting the Q value according to certain rules, and matching the number of slots with the number of tags to be identified, the Q algorithm can achieve high throughput. The BT algorithm is effective for solving the RFID tag collision problem.
By combining the benefits of these two approaches, the IAS algorithm can quickly group tags using the Q algorithm’s mechanisms while also minimizing collisions by means of the BT algorithm. But the IAS algorithm offers superior performance to the Q and BT algorithm approaches in terms of throughput, slot counts to recognize certain numbers of tags, as well as in recognition efficiency.
Acknowledgments
This work was financially supported by the Science Research Fund of Daqing Normal University (12ZR17). The authors would like to thank Daqing Normal University for providing the facilities and resources to perform this research. Also, the authors would like to thank our colleagues at the Department of Physics and Electrical Information Engineering of Daqing Normal University for their excellent collaboration and help during the preparation of this article.
Guihua Yang, Professor
Junchi Ma, Master
Yukai Gao, Master
Baohong Fu, Master
Chunmei Wu, Master
Department of Physics and Electrical Information Engineering, Daqing Normal University, Heilongjiang, 163712, People’s Republic of China
This file type includes high resolution graphics and schematics when applicable.
References
This file type includes high resolution graphics and schematics when applicable.
1. Jia Xiaolin, Feng Quanyuan, and Fan Taihua, “Analysis of anti-collision protocols for RFID tag identification,” IEEE 2012 2nd International Conference on Digital Object IdentiIdentifier, 2012.
2. J.H. Choi, D.W. Lee, and H.J, Lee, “Bi-Slotted Tree based Anti-Collision Protocols for Fast Tag Identification in RFID Systems,” Journal of IEEE Communications Letters, Vol.10, No. 12, 2006, pp. 861-863.
3. J.H. Choi, D. Lee, H. Jeon, J. Cha, and H. Lee, “Enhanced Binary Search with Time-Divided Responses for Efficient RFID Tag Anti-Collision,” IEEE International Conference on Communications (ICC2007). Glasgow, Scotland, 2007, pp. 3853-3858.
4. SungSoo Kim,YongHwan Kim,and KwangSeon Ahn.An, “Enhanced Slotted Binary Tree Algorithm with Intelligent Separation in RFID Systems,” IEEE Symposium on Computers and Communications (ISCC 2009), 2009, pp. 237-242.
5. Raghunathanv, Kansala, and Hsui, “Design consideration for solar energy harvesting wireless embedded system,” Proceedings of the 4th International Symposium on Information Proceeding in Sensor Networks, Piscataway, NJ, IEEE Press, 2009, pp. 457-462 .
6. Ding Zhi-guo and Zhu Xue-yong, “An Adaptive anti-collision algorithm based on multi-tree search,” Acta Automatica Sinica, Vol. 36, No. 2, 2010, pp. 237-241.
7. Xiong Wei, Teng Pei-jun, and Liang Qing, “Research of an anti-collision algorithm based on collision tracking of RFID system,” Journal of Air Force Engineering University, Vol. 10, No. 3, 2009, pp. 68-72.
8. J.I. Capetanakis, “Tree Algorithms for Packet Broadcast Channels,” IEEE Transactions on Information Theory, Vol. 25, 1979, pp. 505-515.
9. H. Choi, J.R. Cha, and J.H. Kim, “Fast wireless anti-collision algorithm in ubiquitous ID system,” Proceedings of IEEE VTC ’04, Los Angeles, CA. September 2004, pp. 4589-4592.
10. J.L. Massey, “Collision-resolution algorithms and random-access communications, Multiple User Communication Systems, Springer-Verlag, New York, NY, 1981, pp. 73-99.
11. Ming-Kuei Yeh, Jehn-Ruey Jiang, and Shing-Tsaan Huang, “Adaptive splitting and pre-signaling for RFID tag anti-collision,” Computer Communications, November 15, 2009, pp. 1862-1870.
12. Mollf, Mateul, “Review of energy harvesting techniques and application for microelectronics,” Proceedings of SPIE, 2009, pp. 359-373.
13. Gao Yi, Guiling Sun, and Weixiang Li, “Wireless sensor node design based on solar energy supply,” Proceedings of the 2nd International Conference on Power Electronics and Intelligent Transportation Systems, 2009, pp. 203-207.
14. ISO/IEC, Information Technology Automatic Identification and Data Capture Techniques - Radio Frequency Identification for Item Management Air Interface-Part 6: Parameters for Air Interface Communications at 860-960 MHz, Final Draft International Standard ISO 18000-6, November 2003.
15. S. Sarma, J. Waldrop, and D. Engels, “An anti-collision algorithm for the reader collision problem,” IEEE International Conference on Communications, Greece, 2003, pp. 1206-1210.
16. Li Bingzhang, Jing Zhengjun, and Luo Ye, “A RFID anti-collision searching algorithm based on regressive- style binary system,” Computer Applications and Software, Vol. 26, No. 12, 2009, pp. 96-98.
17. C. Law, K. Lee, and K. Y. Siu, “Efficient memory-less protocol for tag identification,” Proceedings of the 4th International Workshop on DIALM, Boston, MA, ISA, 2000, pp. 75-84.
18. Xuejun Zhang, Juan Wang, and Suoping Wang, “A Novel Anti-Collision Algorithm Based Continuous Tag ID Grouping in RFID System,” Journal of Computational Information Systems (JCIS), Vol. 7, No. 8, 2011, pp. 2964-2971 (EI: 20113814343464).
19. Zhang Xuejun, “One New RFID Anti-collision Algorithm based on Priority Control,” The International Conference on Electrical and Control Engineering (ICECE) 2010, Wuhan, China, pp. 2884-2887 (EI: 20111013722474).
20. M.K. Yeh and J.R. Jiang, “A Counter-Based RFID Anti-Collision Protocol Using Parallel Splitting [EB/OL].”
This file type includes high resolution graphics and schematics when applicable.