Advanced
An Efficient Anti-collision Algorithm for the EPCglobal Class-1 Generation-2 System under the Dynamic Environment
An Efficient Anti-collision Algorithm for the EPCglobal Class-1 Generation-2 System under the Dynamic Environment
KSII Transactions on Internet and Information Systems (TIIS). 2014. Nov, 8(11): 3997-4015
Copyright © 2014, Korean Society For Internet Information
  • Received : December 01, 2013
  • Accepted : September 21, 2014
  • Published : November 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Chen Yihong
School of Computer Science and Technology, Southwest University for Nationalities Chengdu, Sichuan, 610041 - China
Feng Quanyuan
School of Information Science and Technology, Southwest JiaoTong University Chengdu, Sichuan, 610031 - China

Abstract
Radio frequency identification (RFID) is an emerging wireless communication technology which allows objects to be identified automatically. The tag anti-collision is a significant issue for fast identifying tags due to the shared wireless channel between tags and the reader during communication. The EPCglobal Class-1 Generation-2 which uses Q algorithm for the anti-collision is widely used in many applications such as consumer electronic device and supply chain. However, the increasing application of EPCglobal Class-1 Generation-2 which requires the dynamic environment makes the efficiency decrease critically. Furthermore, its frame length (size) determination and frame termination lead to the suboptimal efficiency. A new anti-collision algorithm is proposed to deal with the two problems for large-scale RFID systems. The algorithm has higher performance than the Q algorithm in the dynamic environment. Some simulations are given to illustrate the performance.
Keywords
1. Introduction
T he Radio Frequency Identification (RFID) [1] , as an automatic identification technique, is widely used in many applications such as supply chain and consumer electronic device [2] . Usually, an RFID system consists of a reader and many tags [3] . The tags attached onto the products contain the product-related information (unique identification codes, called IDs), and transmit IDs in responses to interrogation signals from a reader through the shared wireless media. In the RFID system, there are many tags within the interrogation zone of the reader. If multiple tags transmit data almost at the same time, the burst of data traffic will lead to low packet reception rate at the reader because of serious transmission collisions. For many years, the tag collision problem has been widely investigated considering the static environment where no tag enters the interrogation zone of the reader during identification. The existing anti-collision algorithms maintain high efficiency in the static environment [4] . However, there exists a real-world dynamic environment, for example, the inventory management often requires a reader to scan all the mobile products in a warehouse. This task often involves tens of thousands of tags, and conducts a quick scanning operation to be feasibly implemented. In the environment, the performance of the Q algorithm dramatically decreases.
The EPCglobal Class-1 Generation-2 (EPC-C1G2) applied to Internet of Things adopts EPC (Electronic Product Code) and Q algorithm [5] to support the network with global coverage and handle the tag collision problem. The Q algorithm achieves high identification efficiency by using the Dynamic Framed Slotted Aloha (DFSA) mechanism. The efficiency of DFSA algorithms is optimal only when the number of tags matches the frame length [6] . However, it is difficult to determine whether or not the frame length matches the tag number in the dynamic environment. Therefore, if the Q algorithm is used as anti-collision mechanism for the RFID system under the dynamic environment, its performance will drop dramatically, which is illustrated in Fig.8 . In addition the frame length determination and frame termination will lead to the suboptimal efficiency problem, which is shown in Fig.6 . So, a new anti-collision algorithm is proposed to deal with the two problems of the EPC-C1G2 system under the dynamic environment.
The ingredients of a DFSA algorithm includes tag estimation, frame length determination, and frame termination [7] . The purpose of the tag estimation is to obtain the number of tags in the coverage of the reader. The frame length determination is to choose the most optimal frame length according to the number of tags. And some requirements such as simplicity of tag should be considered in the process of choosing the frame length. The reader terminates the current frame and allocates a new one in order to further improve the efficiency if it allocates the remainder of the current frame resulting in low efficiency. In this work, four methods are developed for dealing with tag estimation of each collision slot, tag arrival rate prediction of each frame, the frame length determination, and the frame termination. By means of comprehensive application of the four methods, a new anti-collision algorithm is proposed for the EPC-C1G2 system under the dynamic environment.
The paper is organized as follows. The related work is presented in Section 2, and an identification process model supporting the dynamic environment is proposed in Section 3. In section 4, the four methods and the anti-collision algorithm for the EPC-C1G2 system under the dynamic environment are depicted. And in section 5, the performance evaluation is shown, followed by conclusions in section 6.
2. Related Work
Various algorithms have been proposed for the tag anti-collision. According to the working principles, these algorithms can be divided into two classes: tree-based algorithm [8 - 10] and aloha-based algorithm [5] - [6] , [10] - [12] . As a classical aloha-based algorithm, the DFSA is employed in industry standards such as the EPC-C1G2 because of their simplicity and robustness.
For the Q algorithm [5] , the number of unidentified tags and the frame length are given by n =2 Q and N = n , respectively. It is noted that Q = round ( Qfp ), where Qfp is modified by using an empirical value C, which is illustrated by Fig. 1 . Moreover, any frame will be terminated when Q changes. In F.C.Schoute [6] , the number of the tags in the same slot has the Poisson distribution with mean 1 on condition that the number of tags equals the frame length. With the number sc of collision slots, the number n of unidentified tags is given by n = round (2.39 sc ). The frame length N is given by N = n . L. Zhu et al [7] proposed a new theory to improve the efficiency of anti-collision algorithm. In the theory, the identification process is modeled as a Markov Chain, and the optimal read strategy is derived through the first-passage-time analysis. The optimal termination method depends only on the system state (the number of unresolved tags, the number of not triggered slots in the current frame, and the number of tags in the remaining slots). In H.Vogt [11] , the number of tags is estimated by minimizing the distance between an actual read result vector and the theoretically result. The authors also adopted N = n when determining the frame length. In M.V.Bueno-Delgado et al [12] , the analysis of the identification process is conducted using discrete time Markov chains; a feasible model is proposed to obtain the optimal frame length. Besides, the authors took the EPC-C1G2 restriction that the frame length N is confined to power of two (i.e., N =2 Q , Q Z +, 0≤ Q ≤15) into account for reducing the tag complexity.
PPT Slide
Lager Image
Anti-collision algorithm of the EPC-C1G2
It is noted that the number of tags involving the identification in each collision slot is estimated based on the prerequisite condition N = n in above algorithms. However, the condition is not always satisfied when the frame length is restricted to power of two and the reader identifies tags under the dynamic environment. Supposing that all slots have the same time and frame length is not restricted to power of two, many anti-collision algorithms set frame length to maximize the throughput for the frame length determination. In terms of the frame termination, the Q algorithm uses an empirical value, while L. Zhu et al. compared the expected finishing time when the current frame is canceled with the time when the next slot is continually triggered. Unfortunately, it is found that the former leads to the suboptimal efficiency problem; the later requires accurate estimation of unresolved tags.
The anti-collision system designed according to standards or product manuals specifies command set of the reader and the tag’s responses to the commands set. The reader knows when and how to use the command set to obtain high efficiency by the anti-collision algorithm [3] . In this paper, an anti-collision algorithm based on the anti-collision system of the EPC-C1G2 standard is proposed; therefore, this paper briefly introduces the anti-collision system and the existing anti-collision algorithm (i.e., Q algorithm) of the EPC-C1G2 system.
The anti-collision system of the EPC-C1G2 is depicted in Fig. 2 . Firstly, the reader transmits the command ‘Select’ to tags for them to participate in the identification of the current frame. Secondly, the reader sends the command ‘Query’ with parameter Q (0≤ Q ≤15, the current frame has 2 Q slots) to these tags, and each tag generates its own random number between 0 and 2 Q -1 and stores the number to a slot counter SC . Subsequently, the reader transmits the command ‘QueryRep’ to allocate a new slot. Lastly, their SCs are subtracted by 1 when tags receive the ‘QueryRep’. If SC of a tag equals 0, the tag responds to the command with a 16-bit random sequence ‘RN16’ in the slot. There are three cases in terms of the slot as follows: (1) Success slot: if there is only one ‘RN16’ in the slot, the reader transmits the command ‘ACK’ with the ‘RN16’ to tags, then the tag with the ‘RN16’ transmits its EPC to the reader and the reader identifies the tag. (2) Collision slot: if there are multiple ‘RN16’s in the slot, then the reader transmits ‘QueryRep’ to terminate the current slot and allocate a new one. (3) Empty slot: if there are not any ‘RN16’ in the slot, the reader transmits ‘QueryRep’ whose function is similar to the one of the 2nd case.
PPT Slide
Lager Image
Anti-collision system of the EPC-C1G2
In each new frame, the Q value is obtained by the Q algorithm depicted in Fig. 1 . There are some properties about the EPC-C1G2: (1) The frame length is 2 Q {0≤ Q ≤15}. (2) The time of empty slot is different from that of success slot and collision slot. Success slot time, collision slot time, and empty slot time are given by ts = tq + t 1 + tr + t 2 + ta + t 1 + tepc + t 2 =967.95μs, tc = tq + t 1 + tr + t 2 =242.92μs, and te = tq + t 1 + t 3 =165.22 μs, respectively [5] . (3) The current frame can be terminated by the command ‘QueryAdjust’.
In the Q algorithm, the frame length determination and the frame termination are based on the modification of Qfp . However, the reader modifies Qfp without regarding to the dynamic environment, so the determination and termination method are not suitable for the dynamic environment. Therefore, the efficiency will decrease when it is applied to the dynamic environment, which is shown in Fig. 8 (a). In addition, the Qfp value is modified by using an empirical value C, which leads to the suboptimal efficiency problem.
3. Identification Process Model
An identification process model shown by Fig. 3 is established for description of tag identification under the dynamic environment. In the DFSA, each identification cycle P consists of many frames; the cycle P is expressed as P ={ Fi | length( Fi ) = vi , vi Z + }. ri denotes the number of tags involving identification of the frame Fi +1 . The frame Fi is composed of multiple slots, i.e., Fi = { tij | j =1,…, vi , where tij and vi denote the j th slot of the frame Fi and its frame length, respectively}. Ti denotes the time of the frame Fi . Tag arrival rate λi ( λi ≥0) is defined as the average number of tags reaching the interrogation zone per second in the frame Fi . There are two cases for λi : (1) λi =0, which means no tags arrive, that is the static environment; (2) λi >0, the tags continuously enter the interrogation zone in the process of identification, that is the dynamic environment. The tag anti-collision is studied based on the dynamic environment. In the frame Fi , the expected number of slots, in which k tags involves identification, is given by H.Vogt [11] :
PPT Slide
Lager Image
PPT Slide
Lager Image
Identification process model for the dynamic environment.
Thus, the expected number sis of success slots, the expected number sie of empty slots, and the expected number sic of collision slots in the frame Fi are given by sis = a 1 vi,ri-1 , sie = a 0 vi,ri-1 , and sic = vi - sis - sie respectively. The tags arriving in the frame Fi attend the identification of the frame Fi +1 instead of the frame Fi , because they do not receive the command ‘Select’ in the frame Fi . So, the tags attending the identification of the frame Fi +1 consist of the ones that new arrive in the frame Fi , and ones in collision slots of the frame Fi , and the numbers of the two parts are denoted by ni and ci , respectively. Therefore, The number ri of the tags attending the identification of the frame Fi +1 is given by
PPT Slide
Lager Image
Therefore, the equation (1) describes the dynamic environment when ri is larger than ci . To obtain the number of tags attending the identification in the frame Fi +1 , the proposed anti-collision algorithm not only estimates the number of tags which are not successfully identified, but also predicts tag arrival rate λi in the frame Fi according to λu (1≤ u i -1).
4. The proposed Anti-collision Algorithm G2-CDFSA
There are some methods for solving the tag estimating and reading strategy for the proposed G2-CDFSA. There are two integrations in the tag estimation, one is tag estimation of each collision slot, and the other is the tag arrival rate prediction of each frame, which aims to obtain the number of tags involving identification of each frame. In addition, the read strategy consists of the frame length determination and the frame termination.
- 4.1 Tag Estimation of Each Collision Slot
In this section, n and v denote the number of tags involving identification of each frame and the frame length, respectively. Moreover, let pe , ps , and pc denote empty probability, success probability, and collision probability, respectively. Similarly, let se , ss , and sc denote the expected number of empty slots, the expected number of success slots, and the expected number of collision slots, respectively.
PPT Slide
Lager Image
is the estimated number of tags. The relations among these are as follow [13]
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Therefore, the number of tags which is not successfully identified is n - ss . Let C ( v , n ) denotes the expected number of tags involving identification of each collision slot when n tags attend identification of a frame with length v , then
PPT Slide
Lager Image
It is noted that the estimation does not require the prerequisite condition. However, the prerequisite of the existing estimations is v = n . Here,
PPT Slide
Lager Image
Let v = n , then it can be obtain that C ( v , n )≈ 2.39, which is the Schoute’ estimation [6] . For the EPC-C1G2 system under the dynamic environment, v and n in equation (5) are replaced with 2 Qi and ri -1 , respectively, then
PPT Slide
Lager Image
So the expected number of tags, which is not successfully identified in frame Fi , is given by the equality
PPT Slide
Lager Image
- 4.2 Tag Arrival Rate Prediction
In 1982, Deng Julong developed the Gray Model (GM) [15] . The method reveals the development law of things by analyzing the known information and predicting the change of thing based on the law. Generally, the tag arrival rate randomly fluctuates with certain amplitude due to influences of some factors. Since it is difficult to quantify the influences, so the process of the random fluctuation of arrival rate is a gray process. A tag arrival rate prediction method (called Dynamic Self-Adaptive Residual Metabolic Gray Model, DSA-RMGM) is proposed based on the GM. The Gray Model of the tag arrival process is introduced as follows.
Let λ (0) denotes the original sequence, i.e., λ (0) ={ λ (0) (1), λ (0) (2), …, λ (0) ( g ), λ (0) ( i ) = λi }, where g is the sequence length, and λ (0) ( g +1) can be predicted based on the sequence. The GM formalizes a quasi exponential sequence by differential equation and uses the equation to predict future changes of the sequence. Let λ (1) denote the quasi exponential sequence (called the cumulative sequence) which is obtained by accumulating the original sequence λ (0) as
PPT Slide
Lager Image
Next, let a (1) denotes the mean generation sequence, that is,
PPT Slide
Lager Image
There is an exponential curve equation fitting λ (1) :
PPT Slide
Lager Image
and its solution is
PPT Slide
Lager Image
Because λ (1) are discrete,
PPT Slide
Lager Image
and λ (1) of equation (10) are replaced by λ (0) and a (1) , respectively.
Then the gray difference equation yields
PPT Slide
Lager Image
Let Փ denote the parameter vector, i.e., Փ =( η , ξ ), where – η and ξ are the development coefficient and the gray effect volume, respectively. Solution of equation (12) is given by:
PPT Slide
Lager Image
The equation (12) fits the cumulative sequence by means of the least-squares method, therefore,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
According to equation (13), analog values which are close to real values of the original sequence are given as
PPT Slide
Lager Image
The Residual Gray Model (RGM) based on the GM is proposed to gain higher prediction accuracy. Let ε (0) denote the residual sequence, i.e., ε (0) ={ ε (0) (1), ε (0) (2), …, ε (0) ( g )}, where
PPT Slide
Lager Image
have the same sign (i.e., positive or negative), then {| ε (0) ( k 0 )|,| ε (0) ( k 0 +1)| ,…, | ε (0) ( g )| } is a remaining residuals sequence. Analog values from the remaining residuals sequence are given as
PPT Slide
Lager Image
which is similar to equation (15). The analog values are given by
PPT Slide
Lager Image
where ηε and ξε are similar to η and ξ of the equation (15). Therefore, these analog values ( k < g ) and prediction values ( k g ) are computed by the equation
PPT Slide
Lager Image
where,
PPT Slide
Lager Image
is recorded as λk +1 , p .
Let av ( i , j ) denote the average tag arrival rate between the ith frame and the j th frame, then
PPT Slide
Lager Image
Local correlation of data in the original sequence indicates that the new data reflects the future development of the sequence better than the old data. The Residual Metabolic Gray Model (RMGM) based on RGM can further improve prediction accuracy by taking advantage of the local correlation. In the RMGM, the new data is added in the current sequence, while a few of old data are deleted from the sequence. Accordingly, the next sequence has come into being. In the experiment on RMGM, it is found that longer length of RMGM sequence leads to smaller fluctuation between prediction values as well as larger hysteresis between the prediction and original curves. Moreover, the accuracy of prediction based on the RMGM increases when the original sequence changes without reverse mutation, whereas the accuracy decreases when the sequence changes with reverse mutation. So, the long sequence is better for predicting tag arrival rates than the short one on the condition of the non-reverse mutate, whereas the short sequence is propitious to the prediction of the rates than the long one under the reverse mutation conditions. The change tendency of tag arrival rates may include reverse mutation and non-reverse mutation. So the length of the sequence should be dynamically adjusted according to the change tendency to obtain higher prediction accuracy. In the proposed DSA-RMGM, the length of the next sequence is obtained according to change tendency in the current sequence.
The relative difference between length and cycle of the sequence also has impact on the prediction accuracy [15] . One case is that the length is smaller than the cycle, and another case is that the length is larger than or equal to the cycle. Generally, the former is superior to the later in prediction accuracy. In the EPC-C1G2 system, the frame time is smaller than 500ms; there are at least two frames in one second. Therefore, the maximum length of the sequence may be set to 12, while the minimum one must be greater than or equal to 4 [15] .
Let Dk (0) and gk denote the k th original sequence and its length, respectively. Assuming λmp is the prediction value of λm . In the frame Fm , smc and sms represent the number of collision slots and the number of success slots, respectively. The DSA-RMGM is as follows.
Step 1: g 1 = 12, k = 1, the current sequence is Dk (0)
Step 2: Let Dk (0) ={ Dk (0) ( i ) | Dk (0) ( i ) = λ j , i ∈[1, gk ], j ∈[ k - gk +12, k +11]}. For the next sequence Dk +1 (0) , its length gk +1 is given by the following knowledge rules which are listed in Table 1 .
knowledge rules
PPT Slide
Lager Image
knowledge rules
Step 3: Tag arrival rate is predicted based on Dk +1 (0) : Dk +1 (1) , ABk +1 (1) , Փk +1 ,
PPT Slide
Lager Image
are given by equation (8), (9), (14), (15), and (16), respectively. Then λm ( m = k +13) is predicted using equation (17), and its prediction value is λmp .
Step 4: The number of tags involving identification of the frame Fm +1 is given by
PPT Slide
Lager Image
Step 5: At the end of the frame Fm +1 , rm is obtain by W.-Tzu Chen [14] ; tag arrival rate of the frame Fm is given by
PPT Slide
Lager Image
k = k +1, go to step 2.
In the process of identifying tags, tag arrival rates continuously come into being by equation (20); the length of the sequence adapts to the change tendency of the sequence timely. To evaluate performance of the DSA-RMGM, the tag arrival process is modeled as the Poisson process with non-stationary parameter denoted by the density function [16] corresponding to the arrival rate. The function is given by
PPT Slide
Lager Image
Eighty data set is obtained by the simulation based on this function. These data being equivalent to arrival rate are the average numbers of tags arriving in each slot. λi (1≤ i ≤80) denote the data that constitute the original sequence with periodical fluctuation; the fluctuation can simulate a variety of tag arrival rate changes; Fig. 4 shows the sequence. Based on a few of data, the exponential smoothing prediction method and the DSA-RMGM are suitable for predicting the tag arrival rates. The figure presents the results of comparison between the two prediction methods in terms of accuracy. Fig. 4 (a) shows that the prediction values always lag one step behind the original values, that is, the prediction deviation of the exponential smoothing prediction method is large in the random fluctuation environment. Fig. 4 (b) presents the results of prediction based on DSA-RMGM, and it is found that the proposed prediction method is better for predicting tag arrival rates than the exponential smoothing prediction on the condition of the random fluctuation environment, because the DSA-RMGM adopts long length and short length on the condition of the non-reverse mutation and the reverse mutation, respectively.
PPT Slide
Lager Image
Exponential smoothing prediction (a) v.s. DSA-RMGM(b).
- 4.3 Frame Length Determination
The Frame length is determined according to the number of tags involving identification of the current frame; the guarantee of achieving the optimal efficiency should be taken into consideration. The efficiency is defined as the ratio of success slot time to total frame time; the determination method is called Frame Size (length) Determination based on Efficiency (FSDE). It is noted that the frame length is power of two.Let ηi denote the efficiency of the i th frame, there is
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Fig. 5 is obtained by using the equation (22). The figure presents five efficiency curves which correspond to five Q values respectively, and four important intersected points at which two curves with two adjacent Q values intersects. The horizontal coordinates of these points are obtained by the equations (23). Each efficiency curve segment between two important intersected points corresponds to a Q value. Fig. 5 also shows that the efficiency fluctuates in narrow range and has a maximum value when n varies between two adjacent horizontal coordinates. Table 2 lists these data. For each tag range in the 1st column, a corresponding Q value is listed in the 2nd column, and a maximum η value in the 3rd column. In the 4th column, a pair of boundary values of η are showed. Moreover, it is found that the efficiencies are above 72.7%; here 72.7% is viewed as theoretical value of efficiency.
PPT Slide
Lager Image
Efficiency vs. the number of tags
The number of tags V.S. Q
PPT Slide
Lager Image
The number of tags V.S. Q
As far, the frame length is determined by taking advantage of Table 2 , that is, Q can be take a corresponding value in the 2nd column when the number n of tags belongs to a range in the 1st column. The frame length equals to 2 Q . The method reduces the requirements for estimating the number of unidentified tags accurately, thus, tag estimation error in a certain range affects the identification efficiency very little in the proposed G2-CDFSA.
The FSDE is evaluated by comparing it with the typical anti-collision algorithms including Q algorithm [5] , Bueno [12] , and Wu Hai-feng [17] in terms of efficiency. In this evaluation, the number of tags varies from 1 to 300. Fig. 6 presents the comparison results and shows that the FSDE outperforms the other methods.
PPT Slide
Lager Image
Efficiency comparison for analysis of the frame length determination
- 4.4 Frame Termination
The frame termination method aims to enhance the efficiency and the stability of the FSDE. The reader terminates the current frame depending on whether the efficiency of the remaining slots is less than a threshold value or not. Therefore, the method is called Aborting Frame based on Efficiency (AFE). The method is shown as follows.
Step1: The expected number Ci ( Qi , ri -1 ) of tags involving identification of each collision slot in frame Fi is computed by the equation (6), so the expected number tir of inventoried tags is given by
PPT Slide
Lager Image
Step2: The number nir of tags which is not inventoried and the number sir of remaining slots are respectively given by
PPT Slide
Lager Image
PPT Slide
Lager Image
Then efficiency ηir of remaining slots is
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Step3: From the 1st column in the table I, the reader can decides the number range to which the number ri -1 of tags belongs, and then obtains two boundary values ( li , ri ) by using the number range. If ηir < min ( li , ri ), the reader terminates the current frame and allocates a new one whose length is determined by the FSDE based on nir .
In order to verify the performance of the FSDE with AFE, the efficiency is compared among three methods, i.e., the FSDE with AFE, the Q algorithm, and FSDE. Fig.7 shows that the efficiency of Q algorithm is the lowest and the FSDE with AFE outperforms the other methods. Moreover, the fluctuating amplitude of the FSDE with AFE is smaller than that of the FSDE.
PPT Slide
Lager Image
Efficiency comparison for analysis of the frame termination
- 4.5 G2-CDFSA
An efficient anti-collision algorithm, which be used for the EPC-C1G2 system under the dynamic environment, is developed based on the methods in previous subsections (A,B,C,D). The algorithm called Continual Dynamic Framed Slotted Aloha for the EPCglobal Class-1 Generation-2 (G2-CDFSA ) is as follows.
Step1: Identifying tags in frames ( F 1 , F 2 , F 3 , F 4 ) and computing λ 1 , λ 2 , λ 3 , and λ 4 .
The length v 1 of the frame F 1 is set to 128 by the reader. At the end of the frame, it counts the number s 1c of collision slots, the number s 1s of success slots, and the number s 1e of empty slots. By using s 1c , s 1s , and s 1e , the reader can estimate the number n 1 of tags involving the identification of the frame F 1 by means of the equation (4d), which proposed by W.-Tzu Chen [14] . Similarly to computation of n 1 , the reader computes the number n 2 of tags involving identification of the frame F 2 for obtaining tag arrival rate λ 1 , therefore tag arrival rate λ 1 is given by
PPT Slide
Lager Image
where T 1 = s 1 sts + s 1 ete + s 1 ctc .
Similar to computation of λ 1 , the reader calculates λ 2 , λ 3 , and λ 4 , and the frame counter i is set to 5.
Notes: The reader does not know initial identification tags’ number in the first frame, here, we use 128 as the length of the first frame without consideration of the initial number. In fact, we can also choose other values as the first frame length with less whole performance effect, because the algorithm can automatically optimally adjust following frame lengths according to the estimated tags’ number. Therefore, the initial Q and the initial identification tags affect performance evaluation very little.
Step2: Based on λj (1≤ j i -1), the reader predicts arrival rate λi of the frame Fi by the DSA-RMGM, and denotes λip as its prediction value. Therefore, the estimation value of the number of tags involving the identification of the frame Fi +1 is given by
PPT Slide
Lager Image
where Ti = sists + siete + sictc .
Step3: Making use of rip , the reader determines the length vi +1 of the frame Fi +1 by the FSDE and runs the AFE in the end of each slot of frame Fi +1 .
Step4: In the frame Fi +1 , the reader estimates ri by using the method proposed by Wen-Tzu Chen. Consequently, tag arrival rate λi is given by
PPT Slide
Lager Image
If si +1, c =0, the reader ends the current identification process, otherwise, i = i +1 and go to step 2.
5. Performance Evaluation
In the dynamic environment, four performance indexes (identification efficiency, inventory speed, success ratio, and identification miss rate) should be taken into account for performance evaluation of anti-collision algorithms. There are two classic dynamic environments, one for evoluations of identification efficiency, inventory speed, and success ratio, the other for evoluation of identification miss rate. The Q algorithm has higher performance than the existing DFSA algorithms [3] , so the G2-CDFSA is evaluated by comparing its indexes with ones of the Q algorithm.
In the first dynamic environment, in which tags continuously arrive in the zone of the reader, but not leave, tag arrival is modeled by the Poisson process with the density function (21) to simulate the real tag arrival process. The 300 frames are obtained for performance evaluation of the two algorithms.
As for the identification efficiency, Fig. 8 presents the efficiency evaluation. It is found that average efficiency of the Q algorithm is only 34.1% whereas the G2-CDFSA achieves 73.8%. Moreover, the G2-CDFSA fluctuates with smaller amplitude than the Q algorithm. Therefore, the G2-CDFSA outperforms the Q algorithm.
PPT Slide
Lager Image
Efficiency comparison in the dynamic environment
The inventory speed is the other realistic metric. Fig. 9 presents evaluation results of the two algorithms in terms of this index. It shows that average inventory speed of the Q algorithm is 412 tags per second, whereas one of the G2-CDFSA is about 741. It is found that the inventory speed does not decrease even if the tags arrival rate changes dynamically. It is noted that the EPC-C1G2 system under the dynamic environment is a kind of queuing system [18] . The reader and tags are a service station and customers of the queuing system, respectively. Moreover, the tag arrival rate and the inventory speed equal to the arrival rate of customer and the service rate of the service station, respectively. According to the queuing theory, the EPC-C1G2 system under the dynamic environment can keep steady if the tag arrival rate is smaller than the inventory speed. Therefore, upper limitation of the tag arrival rate is about 741 tags per second in the EPC-C1G2 system when adopting the G2-CDFSA.
PPT Slide
Lager Image
Inventory speed comparison in the dynamic environment
It is well known that the higher success ratio means the lower the tag miss rate in the dynamic environment. The ratio is defined as the number of tags successfully identified to the number of tags arriving in the range of the reader. Fig. 10 presents two numbers. In the Q algorithm, the two numbers are 245 and 551. In the G2-CDFSA, the two numbers are 4375 and 4417. Therefore, the average success ratio of the Q algorithm is only 44.46%, whereas the G2-CDFSA achieves 99.05%.
PPT Slide
Lager Image
Success ratio comparison in the dynamic environment
There are some analyses for explaining the above emerged results. In fact, the Q algorithm determines frame length only according to tags involving the identification of slots in the previous frame, whereas the G2-CDFSA considers not only the tags involving the identification of collision slots but also new arrival tags in the previous frame. Under the dynamic environment, the frame length of the Q algorithm does not match the number of tags, however, one of the G2-CDFSA can do it. Therefore, the G2-CDFSA can be used for solving the efficiency decrease problem and the suboptimal efficiency, and it is more suitable for the dynamic environment than the Q algorithm.
In the second dynamic environment, tags continuously arrive in the zone of the reader, and randomly leave from the zone. In experiments on the environment, tag arrival is also modeled by the Poisson process with the density function (21) to simulate the real tag arrival process, and the retention time of each arrival tag is set by selecting randomly a value from a time range, there are seven time ranges in Table 3 . When staying time of a tag is larger than its retention time, it cannot identify these tags, which is an identification miss problem. The identification miss limits many anti-collision algorithms in many applications, so analysis of the identification miss rate of anti-collision algorithms is necessary. In this paper, the identification miss rate is defined as the number of identification miss tags to the number of tags arriving in the zone of the reader during one observation time. For the evolution of the identification miss rate, there are two experiments on the dynamic environment. One experiment is about effect of time range on the identification miss rate, and its observation time is 5s. Fig.11 presents results of the experiment. The figure shows that the identification miss rate of G2-CDFSA is significantly lower than one of Q algorithm in every time range, and that the miss rate decreases as time range increases. The other experiment is done for evaluating the identification miss rates of G2-CDFSA and Q algorithm considering different observation times, its time range is from 0.08s to 1s. Fig. 12 presents experiment results about the identification miss rate. The figure shows that the miss rate of G2-CDFSA is significantly lower than Q algorithm in every observation time, and that the identification miss rate rises as the observation time is increased.
Time Range
PPT Slide
Lager Image
Time Range
PPT Slide
Lager Image
Identification miss rate comparison under seven time ranges
PPT Slide
Lager Image
Identification miss rate comparison under different observation times
6. Conclusion
The problems of the efficiency decrease and the suboptimal efficiency are systematically studied for the EPC-C1G2 system under the dynamic environment. The identification process model which combines the static environment and the dynamic environment is established. And a new method for tag estimation of each collision slot is proposed. The method is superior to the existing tag estimation methods in the application because of no restrictions between the frame length and the number of tags. It is proved that the Schoute’ method is only a special case of the tag estimation method. The residual metabolic gray model and knowledge rule have been combined to develop a new method of the prediction of tag arrival rate in the dynamic environment. The method can predict the tag arrival rates accurately by using a few data in the case of various changes of arrival rate. Hence, the method is suitable for the low-speed reader. The frame length determination method and the frame termination method are proposed to overcome the shortcomings of the Q algorithm. The effectiveness of the two methods are verified by the experiments. At last, based on the proposed four methods, an efficient anti-collision algorithm is proposed for the EPC-C1G2 system under the dynamic environment. Simulations show that the proposed algorithm significantly outperforms the Q algorithm in terms of four performance indexes (identification efficiency, inventory speed, success ratio, and identification miss rate) under the dynamic environment. The proposed algorithm can be expediently applied to the real RFID system after modifying anti-collision procedure of the reader.
Acknowledgements
This work was jointly supported by the National Natural Science Foundation of China under (61271090, 61471306), the National 863 Propjet of China under (2012AA012305), Fundamental Research Fund for the Central University under (2014NZYQN54, 13NZYTD02), Sichuan Province Science and Technology Project (2014GZ0006), ChengDu Science and Technology Project (2013H056), Science and Technology Project of Sichuan Education (14ZA0368), The State Ethnic Affairs Commission Research Project (2014), and National Social Science Foundation (13BZJ032).
BIO
Chen Yihong was born in Sichuan, P.R.China in 1972. He has received his M.S. degree in computer science from Southwest Petroleum University, Chengdu, P.R. China in 2005. He is currently pursuing a Ph.D. degree in computer science from Southwest Jiaotong University, Chengdu, P.R. China. Meanwhile, he is also working as a lecture at the School of Computer Science and Technology, Southwest University for Nationalities. He has received an outstanding academic achievement award from the Southwest Petroleum University in 2004, a model student reward from the National University of Defense Technology, Changsha, P.R.China in 2010, and an outstanding research award from the Southwest University for Nationalities in 2010, respectively. His current research interests include RFID anti-collision system and internet of things.
Feng Quanyuan (M’06-SM’08) was born in Jiangxi, P.R.China in 1963. He has received a Ph.D. degree from Southwest Jiaotong University, Chengdu, P.R.China in 2000, and he is currently a professor and an advisor of Ph.D. candidates in the School of Information Science and Technology, Southwest Jiaotong University, Chengdu, P.R.China. He has been honored as “the excellent expert” and “the leader of science and technology” of Sichuan province because of his outstanding contributions. In the last 5 years, he has published more than 240 papers. His current research interests include RF and microwave devices, integrated circuits design, RFID technology, embedded systems, wireless communications, antennas and propagation, microwave & millimeter wave technology, smart information processing, electromagnetic compatibility and environmental electromagnetics.
References
Song InChan 2008 “Enhanced pulse protocol RFID reader anti-collision algorithm using slot occupied probability in dense reader environment,” KSII Transactions on Internet and Information Systems 2 (6) 299 - 311    DOI : 10.3837/tiis.2008.06.002
Yu J. , Lee W. , Du D. 2011 “Reducing reader collision for mobile RFID,” IEEE Transactions on Consumer Electronics 57 (2) 574 - 582    DOI : 10.1109/TCE.2011.5955194
Yihong C. , Feng Q. , Ma Z. , Liu T. 2013 “Multiple-Bits-Slot Reservation Aloha Protocol for Tag Identification,” IEEE Transactions on Consumer Electronics 59 (1) 93 - 100    DOI : 10.1109/TCE.2013.6490246
Zhu L. , Yum T. -S.P. 2011 “A critical survey and analysis of RFID anti-collision mechanisms,” IEEE Communications Magazine 49 (5) 214 - 221    DOI : 10.1109/MCOM.2011.5762820
EPCglobal inc. 2008 “EPC Radio Frequency Identity protocols Class-1 Generation-2UHF RFID Protocol for Communications at 860MHz-960MHz, version 1.2.0,” 96 - 96
Schoute F. C. 1983 “Dynamic Frame Length ALOHA,” IEEE Transactions on Communications 31 (4) 565 - 568    DOI : 10.1109/TCOM.1983.1095854
Zhu T. , Yum T. -S.P. 2010 “The Optimal Reading Strategy for EPC Gen-2 RFID Anti-Collision Systems,” IEEE Transactions on Communications 58 (9) 2725 - 2733    DOI : 10.1109/TCOMM.2010.080310.090421
Jia X. , Feng Q. 2010 “An Efficient Anti-Collision Protocol for RFID Tag Identification,” IEEE Communications Letter 14 (11) 1014 - 1016    DOI : 10.1109/LCOMM.2010.091710.100793
Zheng Y. , Li M. 2012 “PET: Probabilistic Estimating Tree for Large-Scale RFID Estimation,” IEEE Transactions on Mobile Computing 11 (11) 1763 - 1774    DOI : 10.1109/TMC.2011.238
Jia X. , Feng Q. , Yu L. 2012 “Stability Analysis of an Efficient Anti-Collision Protocol for RFID Tag Identification,” IEEE Transactions on Communications 60 (8) 2285 - 2294    DOI : 10.1109/TCOMM.2012.051512.110448
Vogt H. 2002 “Multiple object identification with passive RFID tags,” IEEE International Conference on Systems, Man and Cybernetics 3 6 - 13
Bueno-Delgado M. V. , Vales-Alonso J. 2011 “On the optimal frame-length configuration on real passive RFID systems,” Journal of Network and Computer Applications 34 864 - 876    DOI : 10.1016/j.jnca.2010.04.022
Kodialam M. , Nandagopal T. 2006 “Fast and reliable estimation schemes in RFID systems,”SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing 322 - 333
Chen Wen-Tzu 2009 “An Accurate Tag Estimate Method for Improving the Performance of an RFID Anticollision Algorithm Based on Dynamic Frame Length ALOHA,” IEEE Transactions on Automations Science and Engineering 6 (1) 9 - 15    DOI : 10.1109/TASE.2008.917093
JuLong D. 1989b “Introduction to grey systems theory,” The journal of Grey System 1 (2) 1 - 24
Garrido J. , Lu Y. 2004 “On double periodic non-homogeneous Poisson processes,” Bulletin of the Association of Swiss Actuaries https://orffpruebas.uc3m.es/handle/10016/70 2 195 - 212
Wu H. , Zeng Y. 2010 “Bayesian Tag Estimate and Optimal Frame Length for Anti-Collision Aloha RFID System,” IEEE Transactions on Automations Science and Engineering 7 (4) 963 - 969    DOI : 10.1109/TASE.2010.2042957
Takagi H. 1991 “Queuing analysis, vol.1. vacation and priority systems,” North-Holland