4 5000 -FSA -BT (s]os jo#) 4D00 Season-I 30a0 40 2000 0 20 000 20」 FSA 0.400.450.500.550.600.650.700.750.80 200 400 600 800 1000 20 0.30 0.35 0.40 Read Rate #of tags throughput Fig.9.CDF of read rate Fig.10.Identification time Fig.11.Throughput of RCG is 4.However,DCS and Colorwave require 27 and algorithm has been adopted by another well-known RFID 28 rounds due to the high probability of collision among their protocol family,ISO 18000-6 [10].When designing tree based randomly chosen colors in RCG.DCS is better than Colorwave algorithms,researchers usually organize the tags in a binary since DCS knows the maximum degree of RCG in advance tree according to their IDs and identify the tags by using the and this information helps DCS to reduce the probability of tree based search technique.Myung and Lee [29]propose an color collision. adaptive binary splitting(ABS)protocol to reduce collisions Furthermore,we measure the overall throughput of three and efficiently identify tags based on previous result. protocols in the five scenarios and show the results in Fig.13. For avoiding reader collisions,Colorwave [13]is one of The overall throughput of Season is much higher than other pioneer works.Colorwave tries to color the readers randomly twos due to the concurrent identification of non-contentious in a RCG such that each pair of interfering readers can gain tags and joint identification of contentious tags.For example, different colors.In [30],the authors suggest k-coloring of the the overall throughput of Season in 'sparse'scenario is 8.5, interference graph,where the k is the number of available meaning 8.5 tags can be identified per slot on average.Finally, channels.Recently,EPCGlobal [9]proposes a dense reading we measure the average delay of the three protocols and plot mode,in which the tag responses happen in different channels the results in Fig.14.In all the five scenarios,the average to avoid collisions.In [31].the authors design a Q-learning delay of Season is no more than 300 time slots,which can process to arrange channels and allocate time slots for readers be negligible in practice.It also indicates that Season can be with a help of a training process.In [14],the author proposes applied in mobile environments to identify high-speed tags(up a tag-access-scheduling protocol (EGA)based on STDMA. to 9 m/s).On the other hand,DCS and Colorwave suffer from Tang,et al.[15 study a challenging problem of scheduling a longer delays,i.e.,the longest delay is up to 62,352 time the activation of the readers without collision such that the slots,in which some tags have to wait for at least 2 minutes system can wok in a stable way in the long term. before the reader collects them To speed-up the identification procedure,Floerkemeier [32] suggests estimating the cardinality of tags based on the number V.RELATED WORKS of idle slots in the current frame.Kodialam and Nandagopal In the literature,RFID anti-tag-collision mechanisms com- [19]propose two estimation algorithms,Unified Simple Esti- prise of two categories,Framed Slotted ALOHA (FSA)based mator (USE)and Unified Probabilistic Estimator (UPE)with [9],[26]-[28]and Binary Tree (BT)based algorithms [10], three estimators.In addition,there are a lot of security and [29].The well known RFID organization,EPC Global,adopts privacy issues about the RFID system,such as [33]-[35].In a variation of FSA,'Q-Adaptive'in its protocol family,EPC our feature work,we will more focus on these issues in our Gen2 [9],which adaptively tunes the frame length according protocols. to the type of last slot.Lee et al.[26]find that the maximum identification throughput can be achieved within a reader's VI.CONCLUSION scanning field when the size of detecting frame equals to the Anti-collision is a crucial task in RFID systems.In this number of tags.Sheng et al.[27]focus on the fundamental paper,we propose an anti-collision protocol stack,Season, problems of continuously scanning in RFID systems and to improve the identification efficiency for densely deployed design their identifying algorithms based on the information RFID systems.Our results show that Season significantly gathered in the previous scanning process.Xie et al.[28] increases the identification throughput in both the single- involves the practical conditions in the design of probabilistic reader and multi-reader environments,and hence dramatically model of RFID systems,such as the path loss and multi- reduces the identification delay for tags.In our future work, path effect.They also utilize the real settings to efficiently we plan to extend our scheme to mobile reader environments identify tags on the moving conveyor.The binary tree based and explore more practical issues in the RFID identification0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0 20 40 60 80 100 Cumulative Frequency Read Rate Fig. 9. CDF of read rate 0 200 400 600 800 1000 0 1000 2000 3000 4000 5000 Identification time (# of sots) # of tags FSA BT Season-I Fig. 10. Identification time 0.20 0.25 0.30 0.35 0.40 20 40 60 80 100 Percentage (%) throughput BT Season-I FSA Fig. 11. Throughput of RCG is 4. However, DCS and Colorwave require 27 and 28 rounds due to the high probability of collision among their randomly chosen colors in RCG. DCS is better than Colorwave since DCS knows the maximum degree of RCG in advance and this information helps DCS to reduce the probability of color collision. Furthermore, we measure the overall throughput of three protocols in the five scenarios and show the results in Fig.13. The overall throughput of Season is much higher than other twos due to the concurrent identification of non-contentious tags and joint identification of contentious tags. For example, the overall throughput of Season in ‘sparse’ scenario is 8.5, meaning 8.5 tags can be identified per slot on average. Finally, we measure the average delay of the three protocols and plot the results in Fig.14. In all the five scenarios, the average delay of Season is no more than 300 time slots, which can be negligible in practice. It also indicates that Season can be applied in mobile environments to identify high-speed tags (up to 9 m/s). On the other hand, DCS and Colorwave suffer from a longer delays, i.e., the longest delay is up to 62,352 time slots, in which some tags have to wait for at least 2 minutes before the reader collects them. V. RELATED WORKS In the literature, RFID anti-tag-collision mechanisms com￾prise of two categories, Framed Slotted ALOHA (FSA) based [9], [26]–[28] and Binary Tree (BT)based algorithms [10], [29]. The well known RFID organization, EPC Global, adopts a variation of FSA, ‘Q-Adaptive’ in its protocol family, EPC Gen2 [9], which adaptively tunes the frame length according to the type of last slot. Lee et al. [26] find that the maximum identification throughput can be achieved within a reader’s scanning field when the size of detecting frame equals to the number of tags. Sheng et al. [27] focus on the fundamental problems of continuously scanning in RFID systems and design their identifying algorithms based on the information gathered in the previous scanning process. Xie et al. [28] involves the practical conditions in the design of probabilistic model of RFID systems, such as the path loss and multi￾path effect. They also utilize the real settings to efficiently identify tags on the moving conveyor. The binary tree based algorithm has been adopted by another well-known RFID protocol family, ISO 18000-6 [10]. When designing tree based algorithms, researchers usually organize the tags in a binary tree according to their IDs and identify the tags by using the tree based search technique. Myung and Lee [29] propose an adaptive binary splitting (ABS) protocol to reduce collisions and efficiently identify tags based on previous result. For avoiding reader collisions, Colorwave [13] is one of pioneer works. Colorwave tries to color the readers randomly in a RCG such that each pair of interfering readers can gain different colors. In [30], the authors suggest k-coloring of the interference graph, where the k is the number of available channels. Recently, EPCGlobal [9] proposes a dense reading mode, in which the tag responses happen in different channels to avoid collisions. In [31], the authors design a Q-learning process to arrange channels and allocate time slots for readers with a help of a training process. In [14], the author proposes a tag-access-scheduling protocol (EGA) based on STDMA. Tang, et al. [15] study a challenging problem of scheduling the activation of the readers without collision such that the system can wok in a stable way in the long term. To speed-up the identification procedure, Floerkemeier [32] suggests estimating the cardinality of tags based on the number of idle slots in the current frame. Kodialam and Nandagopal [19] propose two estimation algorithms, Unified Simple Esti￾mator (USE) and Unified Probabilistic Estimator (UPE) with three estimators. In addition, there are a lot of security and privacy issues about the RFID system, such as [33]–[35]. In our feature work, we will more focus on these issues in our protocols. VI. CONCLUSION Anti-collision is a crucial task in RFID systems. In this paper, we propose an anti-collision protocol stack, Season, to improve the identification efficiency for densely deployed RFID systems. Our results show that Season significantly increases the identification throughput in both the single￾reader and multi-reader environments, and hence dramatically reduces the identification delay for tags. In our future work, we plan to extend our scheme to mobile reader environments and explore more practical issues in the RFID identification