INT J COMPUT COMMUN, ISSN 1841-9836 8(6):854-862, December, 2013. A Improved EPC Class 1 Gen 2 Protocol with FCFS Feature in the Mobile RFID Systems X. Li, Y. Quan Xiaowu Li 1. School of Information Science and Technology Southwest Jiaotong University Chengdu 610031, Sichuan, China NO.111 of the North Second Ring Road lxwlxw66@126.com 2. School of Information and Technology Kunming University Puxin Road 2, Kunming 650214, China Quanyuan Feng* School of Information Science and Technology Southwest Jiaotong University Chengdu 610031, Sichuan, China NO.111 of the North Second Ring Road *Corresponding author: fengquanyuan@163.com Abstract: In all anti-collision protocols of RFID standards, EPCGlobal Class 1 Generation 2 (C1G2) protocol has been most widely used in RFID systems since it is simply, efficient and safety. Similar to most existing anti-collision protocols, The C1G2 protocol initially aims at tag identification of static scenarios, where all tags keep still during the tag identification process. However, in many real scenarios, tags generally move along a fixed path in the reader coverage area, which implies that tags stay the coverage area only for a limited time (sojourn time). The scenarios are usually called mobile RFID systems. Because the multiple tag identification based on a shared wireless channel is random, tags entering the reader coverage area earlier may be identified later (random later identification phenomenon). The phenomenon and the limited sojourn time may let some tags lost. In this paper, we propose an improved C1G2 protocol with first come first served feature in mobile RFID systems. The protocol can overcome the RLI phenomenon effectively and retains good initial qualities of C1G2 protocol by modifying it slightly. Simulation results show that the proposed protocol can significantly reduce the numbers of lost tags in mobile RFID systems. The idea of the paper is beneficial for redesigning other existing tag anti-collision protocols so as to make these protocols adapt to mobile RFID systems. Keywords:RFID, tag anti-collision, mobile RFID systems, EPC C1G2. 1 Introduction Radio Frequency Identification (RFID) based on wireless radio communication is increasingly used a great deal in many ways. A reader can only interrogate tags within its interrogation region, where the reader’s electromagnetic signal is strong enough to energize the tags. This region is also referred to as the reader coverage area. During tag identification process, a tag collision occurs when multiple tags reply simultaneously to a reader. So far, so many tag collision resolutions have been proposed for static scenarios where no tag enters or leaves the reader coverage area during the process of tag identification [1–11]. However, in other many practical scenarios, tags which are usually attached to items and moving along the fixed path in the reader coverage area need to be identified as soon as possible [12–17]. These scenarios are generally called mobile RFID systems and often appear at doorways Copyright © 2006-2013 by CCC Publications A Improved EPC Class 1 Gen 2 Protocol with FCFS Feature in the Mobile RFID Systems 855 of warehouse and highway [13,14]. In these scenarios, tags stay the coverage area only for a time (sojourn time). Since the reader has only limited sojourn time to identify the passing tags, tag loss may sometimes be inevitable. Figure 1 shows the mobile RFID system diagram and illustrates some parameters: the reader coverage area length, the tag moving velocity (assumed constant) and tag sojourn time S (given in slots) which is a quotient between the reader coverage area length and the time interval for one slot [17]. Mobile RFID systems shown in Figure 1 are our research scenarios. In the mobile RFID systems, some tags may leave the coverage area unidentified under the condition of high tag tag density or is high tag moving speed, etc. We refer to such a tag as a lost tag. How to decrease the number of lost tags is the critical research issue in mobile RFID applications. Therefore, we rate tag loss ratio (TLR) as a critical performance index, which is defined as the quotient between the number of lost tags and the total number of tags entering the reader coverage area [12–15, 17]. Figure 1: The mobile RFID system diagram. Besides, since the multiple tag identification based on a shared wireless channel is random, tags entering the coverage area earlier may be identified later, which is named the random later identification (RLI) phenomenon [17]. An example given in Figure 2 illustrates the phenomenon. In this figure, all tags in the coverage area contend the shared wireless channel together under the condition of high tag density. Each tag randomly selects a slot to communicate with the reader. For example, the tag with asterisk, which enters the coverage area earlier than other ones, is closer to the exit of the coverage area than other tags, but selects the latter slot (slot 12) for communication with the reader. So, it may leave the coverage area unidentified because its slot number (12) is relatively greater. According to the analysis, we believe that the RLI phenomenon and limited sojourn time are two main reasons for causing lost tags, especially under high tag density. Figure 2: Random later identification (RLI) phenomenon . In this paper, we will propose an improved EPC C1G2 protocol with first come first served feature in mobile RFID systems, which is an improvement to EPC C1G2 protocol [10]. The improved protocol overcomes RLI problem and converts random access for tags into sequential 856 X. Li, Y. Quan access for tag groups. For the sake of brevity, the proposed protocol is named IC1G2MRS protocol. The remainder of this paper is organized as follows. In Section 2 we briefly review the related work in the area. In Section 3 we propose the principle of tag sequencing. Then, in Section 4 we offer IC1G2MRS protocol. Section 5 provides the simulation results. Finally, section 6 concludes. 2 Related Works EPC C1G2 protocol is also known as Q algorithm or C1G2 algorithm. In the protocol [10], each tag randomly selects a frame slot and sends a 16-bit random number (RN16) to the reader for reserving the remainder of the frame slot at the selected frame slot. There are three kinds of replies (correspond to three kinds of slots): (1) No reply (empty slot): after waiting for a short time, if the reader has not received a RN16. The reader terminates the current frame slot. (2) Collision reply (collision slot): if multiple tags transmit RN16 in the frame slot, the reader terminates the current frame slot. (3) Success reply (success slot): if only one RN16 is sent to the reader in the current frame slot, the reader can successfully get the tag’s ID in the rest of the frame slot. One benefit of EPC C1G2 protocol is that empty frame slots and collision frame slots are shorter than success frame slots. Therefore, EPC C1G2 protocol is superior to the FSA very much [8]. Figure 3 shows the tag identification process in EPC C1G2 protocol. Figure 3: Random later identification phenomenon (RLI). Until now, some researches on mobile RFID systems have been done [12–14, 17]. Authors in [12, 13] pay attention to TLR computation of frame slotted ALOHA protocol (FSA) and CSMA by Markov model or dynamic systems model. In [14, 15], authors focused on single tag set passing the reader coverage area in a limited time where no more tag sets enter the coverage area until the previous one has left. Obviously, the scenario is different from our research scenario. In [16], Sarangan offered a framework which reduces the tag reading time by using bitmaps. The framework can improve to some extent the system performance of mobile RFID systems. However, the method also can not solve RLI problem effectively. In [17], authors present a grouping based dynamic framed slotted aloha for tag anti-collision protocol in the mobile RFID systems. The protocol has FCFS feature but does not possess the attributes of high system performance of EPC C1G2 protocol in static RFID scenarios. In this paper, we develop an improved C1G2 protocol with first come first served (FCFS) feature in mobile RFID systems (IC1G2MRS). Some advanced characteristics of the protocol are as follows: (1) IC1G2MRS protocol can be easily implemented without complicated computation. (2) The frequency of Tag sequencing for FCFS mechanism is adjustable. (3) The proposed protocol can retain initial good quantities of C1G2 protocol. (4) The protocol can avoid overflow error effectively when the RFID systems work continuously for an awful long time. A Improved EPC Class 1 Gen 2 Protocol with FCFS Feature in the Mobile RFID Systems 857 3 The Principle of Tag Sequencing It is well known that FCFS is based on the sequenced objects. So, tag sequencing is a critical work. In the following, we will give the detailed explanation of tag sequencing, which can refer to [17]. Usually, tags enter the reader coverage area continuously in mobile RFID systems. In this case, the tags in the coverage area can be grouped in their arrival order at regular intervals (assume M slots). Such obtained groups are called time groups and each time group can be assigned a time group sequence number (TGSN). We can derive that tags arriving in the same time interval possess the same TGSN and tags arriving in different time interval possess different TGSNs. For the special case of static scenarios, all tags’ TGSNs are the same because they enter the coverage area in the same time interval. Notice that M can be called the frequency parameter of tag sequencing. The lower M is, the higher the frequency of tag sequencing is. Figure 4: The tags grouped in their arrival time order. To record a TGSN, each tag should possess a memory cell to store TGSN. Figure 4 shows that the tags in the coverage area are sequenced to become three time groups. Initial TGSN of new tags are set as TGSN=null, which means that the new tags have entered the coverage area but have not received any TGSNs given by the reader. We can derive that if a tag’s TGSN equals null, the tag has not been sequenced. Notice that new tags may enter the reader’s field continuously, which can enlarge the TGSN extremely because every new time group may lead to TGSN plus one. To save the tag’s memory space, a circular queue mechanism is used to manage the TGSN. Moreover, for some mobile scenarios where RFID systems are required to work continuously for an awful long time, such as several months or years, only using circular queue mechanism to manage TGSN can avoid overflow of TGSN. For example, we assume that the length of TGSN is 8 bits. With circular queue mechanism, next time group’s TGSN will be set as TGSN=0 if ongoing time group’s TGSN==28-1 during the process of tag sequencing. This means that the reader coverage area can hold a maximum of 28-1 time groups at any time. The reason for subtracting 1 is that the circular queue has overflowed when there are 28-1 time groups in the coverage area. However, with non-circular queue mechanism, the occurrence of next time group will result in an overflow error if ongoing time group’s TGSN==28-1 [17]. We also know that a circular queue mechanism requires the aid of parameters HEAD and REAR. In our method, the two parameters are stored in the reader and respectively point to the earliest arrival time group’s TGSN and the latest arrival time group’s TGSN plus one. Based on the explanation, we can also say that HEAD points the tags in the earliest time group. Figure 5 depicts that a circular queue which is used to manage the TGSNs. The circular queue mechanism with 8-bit TGSN can use TGSN 0 ~ TGSN 28-1 repeatedly. In Figure 5 (a), HEAD = 1 and REAR =3 mean that there are two time groups in the coverage area, and time groups 1 and 2 are the earliest and latest time groups respectively. When HEAD == REAR, there is no unidentified tag in the reader coverage area, as shown in Figure 5 (b). 858 X. Li, Y. Quan (a) Two time groups (b) No time group. Figure 5: Circular queue mechanism is used to manage the TGSNs. In summary, the tag sequencing is summarized as follows: Upon hearing Sequencing command sent by reader, new tags set their TGSN as TGSN = REAR and then the reader set its REAR as REAR = (REAR +1) mod 28 where TGSN length equals 8. In this way, tag sequencing can be implemented, that is, tags in the coverage area can be divided into multiple time groups. 4 The Proposed IC1G2MRS Protocol IC1G2MRS is based on C1G2 algorithm. Compared with C1G2 algorithm, IC1G2MRS has two other features: (1) IC1G2MRS can sequence tags in the reader coverage area to be tag groups (time groups) every M slots (e.g. 20 slots). That is, the reader can group these tags in their arrival order. (2) On this basis, the reader can identify tag groups one by one in order of their TGSNs which indicates that IC1G2MRS has a first come first served (FCFS) character. IC1G2MRS protocol is summarized as follows: Step 1. The reader sequences tags in the coverage area by sending Sequencing command. Upon hearing this command, all tags whose TGSN is equal to ’null’ will be assigned a true TGSN (0 ~ 255). More details can refer to section 3. Following operations only aim at the tags in the earliest time group if no special explanation is given. Step 2. The reader sends a query command (e.g. Query or QueryRep) to tags. If it is currently the time to start a new frame, the reader issues Query command; Otherwise the reader issues QueryRep. Step 3. Tags receive the query command from the readers. It could be Query or QueryRep. If the received query command is Query, every unidentified tag selects a slot number (SN) between 0 and 2Q-1, inclusively. If the received query command is QueryRep, all unidentified tags decrease their SN by 1. After these operations, every unidentified tag randomly selects a slot number between 0 and 2Q-1, inclusively. The tags whose SNs equal 0 generate a 16-bit random number (RN16) and responds the RN16 to the reader. Because each tag conducts the operations independently, there are three possible outcomes (correspond to three kinds of slots): 1) Success reply (success slot): Only one tag responds and the reader receives the RN16 successfully. Then the reader will send out an acknowledgement (ACK) (go to Step 4). 2) Collision reply (collision slot): More than one tag responds simultaneously and collision occurs. Then the reader adjusts Q as Q=min (15,Q + c) and the reader continues to identify tags by sending QueryRep to tags (go to Step 2). 3) No reply (empty slot): No tag responds. Then the reader updates Q as Q=max (0,Q − c) and continues to identify tags by sending QueryRep to tags (go to Step 2). Notice that, a success slot is counted as a standard slot, named slot for short. According to EPC C1G2 standard, a collision and an empty slot respectively equal approximately 0.2 times A Improved EPC Class 1 Gen 2 Protocol with FCFS Feature in the Mobile RFID Systems 859 and 0.1 times the time cost of standard slots [10]. More details can refer to section 3. Step 4. After the reader successfully receives a RN16 from a tag, it sends an ACK back to all tags. But only the tag that successfully replies in Step 3 recognizes the ACK and then goes to Step 5. The ACK contains the RN16 that the reader received in Step 3. Step 5. All tags may receive the ACK, but only the tag that replies successfully in Step 3 continues to transmit its EPC to the reader. Then the reader continues to identify remaining tags in ongoing earliest time group by sending QueryRep (go to Step 2). Notice that identified tags are silenced. Namely, they will not reply the reader’s command in following identification process. Step 6. The reader sequences tags in the reader coverage area every M (e.g. 20) slots. Step 7. After one frame ends, if one or more collisions occur in the current frame, the reader sends Query command with updated Q to all unidentified tags in the earliest time group after ongoing frame (go to Step 2). If not, the ongoing earliest time group move next time group. Then go to step 1. In short, IC1G2MRS protocol is hybrid of C1G2 protocol and first come and first served (FCFS) mechanism. It can group tags in the reader coverage area to be multiple tag groups in their arrival order and then use basic principles of EPC C1G2 protocol to identify each time group in FCFS order. 5 Simulation and Results Before we evaluate the proposed protocol, we first offer a simplified mobile RFID experiment model because there are no good mathematical methods which can compute the TLR of various anti-collision protocols in the mobile RFID systems so far [17]. More reasons for using the simplified mobile RFID experiment model can refer to [17]. The model is composed of 3 groups of mobile tags, as shown in Figure 6 where T1 denotes the time interval between the 1st and 2nd groups of tags, T2 denotes the time interval between the 2nd and 3rd groups of tags, N1, N2 and N3 denote the number of tags in the 1st, 2nd and 3rd groups of tags respectively, S denotes the tag sojourn time. Notice that in the paper, all parameters related to time, such as T1, T2, S and M are measured in slot. Figure 6: Simplified mobile RFID experiment model. Now, we comprehensively evaluate IC1G2MRS by comparing it with the typical C1G2 pro- tocol [10]. Our simulation based on Monte Carlo technique and the simplified mobile RFID ex- periment model. The basic parameters of following simulation experiments are N1=70, N2=70, N3=70, T1=50, T2=80, S=200, M =20. The evaluation results are shown in Fig. 6. Figure 7 (a) depicts the relationship between TLR and the tag density by changing the number of tags N2 in the second group. TLR of two protocols increases as the tag density increases. The reason is that the reader has to identify more tags in the same interval. Compared with C1G2, IC1G2MRS has better performance. For example, when the number of tags in the second group N2 is less than or equal to 100 tags, TLR of IC1G2MRS is nearly zero while that of C1G2 is 10 percent. 860 X. Li, Y. Quan Figure 7 (b) depicts the relationship between TLR and the tag sojourn time S by changing S (correspond to change of the tag moving speed or the reader coverage area length). TLR of two protocols decreases as S increases. The reason is that the reader has more time to identify tags as S increases. Compared with C1G2, IC1G2MRS has better performance. For example, when tag sojourn time S is larger than or equals 200 slots, TLR of IC1G2MRS is nearly zero while TLR of C1G2 protocol is 5 percent. 20 40 60 80 100 0 0.05 0.1 N2 T ag L os s R at io IC1G2MRS C1G2 (a) TLR vs. the tag density 100 200 300 400 500 0 0.05 0.1 0.15 0.2 0.25 S T ag L os s R at io IC1G2MRS C1G2 (b) TLR vs. the sojourn time 10 20 30 40 50 60 70 80 0 0.02 0.04 0.06 0.08 T1 (T1+T2 =130) T ag L os s R at io IC1G2MRS C1G2 (c) TLR vs. T1 under the condition of T1+T2 =130 20 40 60 80 100 0 0.02 0.04 0.06 0.08 0.1 T1 T ag L os s R at io IC1G2MRS C1G2 (d) TLR vs. tag arrival rate 20 40 60 80 100 120 140 0 0.02 0.04 0.06 M T ag L os s R at io IC1G2MRS C1G2 (e) TLR vs. the frequency of tag sequencing Figure 7: TLR of the proposed IC1G2MRS protocol and C1G2 protocol. Figure 7 (c) depicts the relationship between TLR and time interval T1 under the condition that T1+ T2 equals a constant (e.g. 130), which can to some extent conclude which protocol is sensitive to changing T1 in the same time span, and which protocol is not. For the experiment, IC1G2MRS can maintain a stable performance whereas C1G2 is unsteady. Figure 7 (d) depicts the relationship between TLR and tag arrival rate by changing T1. From the figure, we can find that TLR of two protocols decreases as the tag arrival rate become slow. The reason is that the reader has more time to identify tags when the rate becomes slow. Compared with C1G2, IC1G2MRS has better performance. For example, when T1 is equal to 20 slots, TLR of IC1G2MRS is nearly zero percent while TLR of C1G2 protocol is 8 percent. Figure 7 (e) depicts the relationship between TLR and the frequency of tag sequencing by changing M. From the figure, TLR of IC1G2MRS increases as the frequency of tag sequencing decreases (correspond to increase of M). The reason is that RLI problem may not be resolved A Improved EPC Class 1 Gen 2 Protocol with FCFS Feature in the Mobile RFID Systems 861 when the frequency of tag sequencing is too low. For example, when M > 130, the three groups of tags in the Figure 6 are not sequenced and are seen as a group of tags. Thus TLR of IC1G2MRS significantly increases and is equal to that of C1G2. We can also know easily that if the frequency of tag grouping is too high, great TLR may occur. The reason is that the operation of the tag grouping also needs the time cost. From the experiments, we can derive that the frequency of tag sequencing has a strong influence on TLR. 6 Conclusions EPC C1G2 procotol is the most popular standard in RFID systems. But it can not be used in mobile RFID systems effectively because the random late identification (RLI) phenomenon can not be overcome. The paper specifies the random late identification (RLI) phenomenon which causes unnecessary tag loss in the mobile RFID systems. Then IC1G2MRS protocol is proposed to resolve the phenomenon and retains initial good quantities of C1G2 protocol, which improves the system performance of mobile RFID systems dramatically. Acknowledgement This work is supported by the National Natural Science Foundation of China (NNSF) un- der Grant 60990320, 60990323, 61271090, and the National 863 Project of China under Grant 2012AA012305, and Sichuan Provincial Science and technology support Project under Grant 2012GZ0101, and Chengdu Science and technology support Project under Grant 12DXYB347JH- 002. Bibliography [1] He, M. et al (2011); A fast RFID Tag Identification Algorithm Based on Counter and Stack, Expert Systems with Applications, ISSN 0957-4174, 38: 6829-6838. [2] Yeh, M. et al. (2009); Adaptive Splitting and Pre-signaling for RFID Tag Anti-collision, Computer Communications, ISSN 0140-3664, 32: 1862-1870. [3] Finkenzeller, K. (2002); RFID Handbook: Radio-frequency Identification Fundamentals and Applications, John Wiley Press. [4] Chen, Y. (2013); Multiple-Bits-Slot Reservation Aloha Protocol for Tag Identification, IEEE Transactions on Consumer Electronics, ISSN 0098-3063, 59(1): 93-10. [5] Alcaraz, J. et al. (2013); A Stochastic Shortest Path Model to Minimize the Reading Time in DFSA-Based RFID Systems, IEEE Communications Letters, ISSN 1089-7798, 17(2): 341- 344. [6] Wong, C. et al. (2007); Grouping Based Bit-slot ALOHA Protocol for Tag Anti-collision in RFID Systems, IEEE Communication Letters, ISSN 1089-7798, 11(12): 946-948. [7] Jia, X. et al. (2010); An Efficient Anti-collision Protocol for RFID Tag Identification, IEEE Communication Letters, ISSN 1089-7798, 14(11): 1014-1016. [8] Zhu, L.; Yum, T. (2011); A Critical Survey and Analysis of RFID Anti-Collision Mechanisms, IEEE Communications Magazine, ISSN 0163-6804, 5: 214-221. 862 X. Li, Y. Quan [9] Klair, D. et al. (2009); A Survey and Tutorial of RFID Anti-Collision Protocols, IEEE Com- munications Surveys and Tutorials, ISSN 1553-877X, 12(3): 400-421. [10] EPCglobal Specification for RFID Air Interface; Radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz - 960 MHz, version 1.0.9, 2005. [11] Vogt, H. (2002); Efficient Object Identification with Passive RFID Tag, Proceedings of 2002 IEEE international conference on systems, pp. 98-113 [12] Alcaraz, J. et al (2011); Dynamic System Model for Optimal onfiguration of Mobile RFID Systems, Computer Networks, ISSN 1389-1286, 55: 74-83. [13] Vales-Alonso, J. et al (2009); Markovian model for Computation of Tag Loss Ratio in Dy- namic RFID Systems, Proceedings of 5th European Workshop on RFID Systems and Tech- nologies, Bremen, Germany, pp. 16-17. [14] Vales-Alonso, J. et al (2011); On the Optimal Identification of Tag Sets in Time-constrained RFID Configurations, Sensors, ISSN 1424-8220, 11: 2946-2960. [15] Xie, L. (2010); Efficient Tag Identification in Mobile RFID Systems. , Proceedings of IEEE International Conference INFOCOM, pp. 15-19. [16] Sarangan, V. (2008); A framework for fast RFID tag reading in static and mobile environ- ments, Computer Networks, ISSN 1389-1286, 52(5): 1058-1073. [17] Li, X.; Feng, Q. (2013); Grouping Based Dynamic Framed Slotted ALOHA for Tag Anti- Collision Protocol in the Mobile RFID Systems, Appl. Math. Inf. Sci., ISSN 1935-0090, (2L): 655-659.