Radio frequency identification (RFID) is an emerging wireless communication technology which allows objects to be identified automatically. The tag anticollision is a significant issue for fast identifying tags due to the shared wireless channel between tags and the reader during communication. The EPCglobal Class1 Generation2 which uses Q algorithm for the anticollision is widely used in many applications such as consumer electronic device and supply chain. However, the increasing application of EPCglobal Class1 Generation2 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 anticollision algorithm is proposed to deal with the two problems for largescale RFID systems. The algorithm has higher performance than the Q algorithm in the dynamic environment. Some simulations are given to illustrate the performance.
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 productrelated 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 anticollision algorithms maintain high efficiency in the static environment
[4]
. However, there exists a realworld 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 Class1 Generation2 (EPCC1G2) 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 anticollision 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 anticollision algorithm is proposed to deal with the two problems of the EPCC1G2 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 anticollision algorithm is proposed for the EPCC1G2 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 anticollision algorithm for the EPCC1G2 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 anticollision. According to the working principles, these algorithms can be divided into two classes: treebased algorithm
[8

10]
and alohabased algorithm
[5]

[6]
,
[10]

[12]
. As a classical alohabased algorithm, the DFSA is employed in industry standards such as the EPCC1G2 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
(
Q_{fp}
), where
Q_{fp}
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
s_{c}
of collision slots, the number
n
of unidentified tags is given by
n
=
round
(2.39
s_{c}
). The frame length
N
is given by
N
=
n
. L. Zhu et al
[7]
proposed a new theory to improve the efficiency of anticollision algorithm. In the theory, the identification process is modeled as a Markov Chain, and the optimal read strategy is derived through the firstpassagetime 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.BuenoDelgado 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 EPCC1G2 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.
Anticollision algorithm of the EPCC1G2
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 anticollision 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 anticollision 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 anticollision algorithm
[3]
. In this paper, an anticollision algorithm based on the anticollision system of the EPCC1G2 standard is proposed; therefore, this paper briefly introduces the anticollision system and the existing anticollision algorithm (i.e., Q algorithm) of the EPCC1G2 system.
The anticollision system of the EPCC1G2 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 16bit 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.
Anticollision system of the EPCC1G2
In each new frame, the
Q
value is obtained by the Q algorithm depicted in
Fig. 1
. There are some properties about the EPCC1G2: (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
t_{s}
=
t_{q}
+
t
_{1}
+
t_{r}
+
t
_{2}
+
t_{a}
+
t
_{1}
+
t_{epc}
+
t
_{2}
=967.95μs,
t_{c}
=
t_{q}
+
t
_{1}
+
t_{r}
+
t
_{2}
=242.92μs, and
t_{e}
=
t_{q}
+
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
Q_{fp}
. However, the reader modifies
Q_{fp}
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
Q_{fp}
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
={
F_{i}
 length(
F_{i}
) =
v_{i}
,
v_{i}
∈
Z
^{+}
}.
r_{i}
denotes the number of tags involving identification of the frame
F_{i}
_{+1}
. The frame
F_{i}
is composed of multiple slots, i.e.,
F_{i}
= {
t_{ij}

j
=1,…,
v_{i}
, where
t_{ij}
and
v_{i}
denote the
j
th slot of the frame
F_{i}
and its frame length, respectively}.
T_{i}
denotes the time of the frame
F_{i}
. Tag arrival rate
λ_{i}
(
λ_{i}
≥0) is defined as the average number of tags reaching the interrogation zone per second in the frame
F_{i}
. 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 anticollision is studied based on the dynamic environment. In the frame
F_{i}
, the expected number of slots, in which
k
tags involves identification, is given by H.Vogt
[11]
:
Identification process model for the dynamic environment.
Thus, the expected number
s_{is}
of success slots, the expected number
s_{ie}
of empty slots, and the expected number
s_{ic}
of collision slots in the frame
F_{i}
are given by
s_{is}
=
a
_{1}
^{vi,ri1}
,
s_{ie}
=
a
_{0}
^{vi,ri1}
, and
s_{ic}
=
v_{i}

s_{is}

s_{ie}
respectively. The tags arriving in the frame
F_{i}
attend the identification of the frame
F_{i}
_{+1}
instead of the frame
F_{i}
, because they do not receive the command ‘Select’ in the frame
F_{i}
. So, the tags attending the identification of the frame
F_{i}
_{+1}
consist of the ones that new arrive in the frame
F_{i}
, and ones in collision slots of the frame
F_{i}
, and the numbers of the two parts are denoted by
n_{i}
and
c_{i}
, respectively. Therefore, The number
r_{i}
of the tags attending the identification of the frame
F_{i}
_{+1}
is given by
Therefore, the equation (1) describes the dynamic environment when
r_{i}
is larger than
c_{i}
. To obtain the number of tags attending the identification in the frame
F_{i}
_{+1}
, the proposed anticollision algorithm not only estimates the number of tags which are not successfully identified, but also predicts tag arrival rate
λ_{i}
in the frame
F_{i}
according to
λ_{u}
(1≤
u
≤
i
1).
4. The proposed Anticollision Algorithm G2CDFSA
There are some methods for solving the tag estimating and reading strategy for the proposed G2CDFSA. 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
p_{e}
,
p_{s}
, and
p_{c}
denote empty probability, success probability, and collision probability, respectively. Similarly, let
s_{e}
,
s_{s}
, and
s_{c}
denote the expected number of empty slots, the expected number of success slots, and the expected number of collision slots, respectively.
is the estimated number of tags. The relations among these are as follow
[13]
Therefore, the number of tags which is not successfully identified is
n

s_{s}
. 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
It is noted that the estimation does not require the prerequisite condition. However, the prerequisite of the existing estimations is
v
=
n
. Here,
Let
v
=
n
, then it can be obtain that
C
(
v
,
n
)≈ 2.39, which is the Schoute’ estimation
[6]
. For the EPCC1G2 system under the dynamic environment,
v
and
n
in equation (5) are replaced with 2
^{Qi}
and
r_{i}
_{1}
, respectively, then
So the expected number of tags, which is not successfully identified in frame
F_{i}
, is given by the equality
 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 SelfAdaptive Residual Metabolic Gray Model, DSARMGM) 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
Next, let
a
^{(1)}
denotes the mean generation sequence, that is,
There is an exponential curve equation fitting
λ
^{(1)}
:
and its solution is
Because
λ
^{(1)}
are discrete,
and
λ
^{(1)}
of equation (10) are replaced by
λ
^{(0)}
and
a
^{(1)}
, respectively.
Then the gray difference equation yields
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:
The equation (12) fits the cumulative sequence by means of the leastsquares method, therefore,
where
According to equation (13), analog values which are close to real values of the original sequence are given as
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
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
which is similar to equation (15). The analog values are given by
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
where,
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
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 nonreverse 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 nonreverse mutation. So the length of the sequence should be dynamically adjusted according to the change tendency to obtain higher prediction accuracy. In the proposed DSARMGM, 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 EPCC1G2 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
D_{k}
^{(0)}
and
g_{k}
denote the
k
th original sequence and its length, respectively. Assuming
λ_{mp}
is the prediction value of
λ_{m}
. In the frame
F_{m}
,
s_{mc}
and
s_{ms}
represent the number of collision slots and the number of success slots, respectively. The DSARMGM is as follows.
Step 1:
g
_{1}
= 12,
k
= 1, the current sequence is
D_{k}
^{(0)}
Step 2: Let
D_{k}
^{(0)}
={
D_{k}
^{(0)}
(
i
) 
D_{k}
^{(0)}
(
i
) =
λ _{j}
,
i
∈[1,
g_{k}
],
j
∈[
k

g_{k}
+12,
k
+11]}. For the next sequence
D_{k}
_{+1}
^{(0)}
, its length
g_{k}
_{+1}
is given by the following knowledge rules which are listed in
Table 1
.
knowledge rules
Step 3: Tag arrival rate is predicted based on
D_{k}
_{+1}
^{(0)}
:
D_{k}
_{+1}
^{(1)}
,
AB_{k}
_{+1}
^{(1)}
,
Փ_{k}
_{+1}
,
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
F_{m}
_{+1}
is given by
Step 5: At the end of the frame
F_{m}
_{+1}
,
r_{m}
is obtain by W.Tzu Chen
[14]
; tag arrival rate of the frame
F_{m}
is given by
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 DSARMGM, the tag arrival process is modeled as the Poisson process with nonstationary parameter denoted by the density function
[16]
corresponding to the arrival rate. The function is given by
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 DSARMGM 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 DSARMGM, 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 DSARMGM adopts long length and short length on the condition of the nonreverse mutation and the reverse mutation, respectively.
Exponential smoothing prediction (a) v.s. DSARMGM(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
where
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.
Efficiency vs. the number of tags
The number of tags V.S. Q
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 G2CDFSA.
The FSDE is evaluated by comparing it with the typical anticollision algorithms including Q algorithm
[5]
, Bueno
[12]
, and Wu Haifeng
[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.
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
C_{i}
(
Q_{i}
,
r_{i}
_{1}
) of tags involving identification of each collision slot in frame
F_{i}
is computed by the equation (6), so the expected number
t_{ir}
of inventoried tags is given by
Step2:
The number
n_{ir}
of tags which is not inventoried and the number
s_{ir}
of remaining slots are respectively given by
Then efficiency
η_{ir}
of remaining slots is
where
Step3:
From the 1st column in the table I, the reader can decides the number range to which the number
r_{i}
_{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
n_{ir}
.
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.
Efficiency comparison for analysis of the frame termination
 4.5 G2CDFSA
An efficient anticollision algorithm, which be used for the EPCC1G2 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 Class1 Generation2 (G2CDFSA ) 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
where
T
_{1}
=
s
_{1}
_{s}t_{s}
+
s
_{1}
_{e}t_{e}
+
s
_{1}
_{c}t_{c}
.
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
F_{i}
by the DSARMGM, and denotes
λ_{ip}
as its prediction value. Therefore, the estimation value of the number of tags involving the identification of the frame
F_{i}
_{+1}
is given by
where
T_{i}
=
s_{is}t_{s}
+
s_{ie}t_{e}
+
s_{ic}t_{c}
.
Step3: Making use of
r_{ip}
, the reader determines the length
v_{i}
_{+1}
of the frame
F_{i}
_{+1}
by the FSDE and runs the AFE in the end of each slot of frame
F_{i}
_{+1}
.
Step4: In the frame
F_{i}
_{+1}
, the reader estimates
r_{i}
by using the method proposed by WenTzu Chen. Consequently, tag arrival rate
λ_{i}
is given by
If
s_{i}
_{+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 anticollision 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 G2CDFSA 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 G2CDFSA achieves 73.8%. Moreover, the G2CDFSA fluctuates with smaller amplitude than the Q algorithm. Therefore, the G2CDFSA outperforms the Q algorithm.
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 G2CDFSA 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 EPCC1G2 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 EPCC1G2 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 EPCC1G2 system when adopting the G2CDFSA.
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 G2CDFSA, the two numbers are 4375 and 4417. Therefore, the average success ratio of the Q algorithm is only 44.46%, whereas the G2CDFSA achieves 99.05%.
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 G2CDFSA 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 G2CDFSA can do it. Therefore, the G2CDFSA 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 anticollision algorithms in many applications, so analysis of the identification miss rate of anticollision 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 G2CDFSA 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 G2CDFSA 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 G2CDFSA 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
Identification miss rate comparison under seven time ranges
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 EPCC1G2 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 lowspeed 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 anticollision algorithm is proposed for the EPCC1G2 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 anticollision 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 anticollision system and internet of things.
Feng Quanyuan (M’06SM’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.
Song InChan
2008
“Enhanced pulse protocol RFID reader anticollision 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
“MultipleBitsSlot 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 anticollision mechanisms,”
IEEE Communications Magazine
49
(5)
214 
221
DOI : 10.1109/MCOM.2011.5762820
EPCglobal inc.
2008
“EPC Radio Frequency Identity protocols Class1 Generation2UHF RFID Protocol for Communications at 860MHz960MHz, version 1.2.0,”
96 
96
Zhu T.
,
Yum T. S.P.
2010
“The Optimal Reading Strategy for EPC Gen2 RFID AntiCollision Systems,”
IEEE Transactions on Communications
58
(9)
2725 
2733
DOI : 10.1109/TCOMM.2010.080310.090421
Zheng Y.
,
Li M.
2012
“PET: Probabilistic Estimating Tree for LargeScale 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 AntiCollision 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
BuenoDelgado M. V.
,
ValesAlonso J.
2011
“On the optimal framelength 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 WenTzu
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 nonhomogeneous 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 AntiCollision 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,”
NorthHolland