An RFID systems employ efficient AntiCollision Algorithms (ACAs) to enhance the performance in various applications. The EPCGlobal G2 RFID system utilizes Frame Slotted Aloha (FSA) as its ACA. One of the common approaches used to maximize the system performance (tag identification efficiency) of FSAbased RFID systems involves finding the optimal value of the frame length relative to the contending population size of the RFID tags. Several analytical models for finding the optimal frame length have been developed; however, they are not perfectly optimized because they lack precise characterization for the timing details of the underlying ACA. In this paper, we investigate this promising direction by precisely characterizing the timing details of the EPCGlobal G2 protocol and use it to derive a preciseoptimal frame length model. The main objective of the model is to determine the optimal frame length value for the estimated number of tags that maximizes the performance of an RFID system. However, because precise estimation of the contending tags is difficult, we utilize a parametricheuristic approach to maximize the system performance and propose two simple schemes based on the obtained optimal frame length—namely, Improved DynamicFrame Slotted Aloha (IDFSA) and Exponential Random PartitioningFrame Slotted Aloha (ERPFSA). The IDFSA scheme is based on the tag set estimation and frame size update mechanisms, whereas the ERPFSA scheme adjusts the contending tag population in such a way that the applied frame size becomes optimal. The results of simulations conducted indicate that the IDFSA scheme performs better than several wellknown schemes in various conditions, while the ERPFSA scheme performs well when the frame size is small.
1. Introduction
W
ith the remarkable development and rapid growth of wireless technologies, Radio Frequency Identification (RFID) systems are being used more widely nowadays in application domains such as logistics, inventory management, retailing, public transportation, and security
[1]
,
[2]
. One of the primary factors spurring the increased utilization of RFID systems is the ability of these systems to identify objects wirelessly even when they are out of sight.
A simple RFID system consists of a single reader and multiple tags. First, the reader activates the tags, which then send back their identification and other information. During the identification process, multiple RFID tags transmit their identification information arbitrarily to the designated reader using a shared wireless channel. If more than one tag transmits at a given time, the transmitted identification packets may collide, and result in them not being decoded correctly by the reader. Therefore, the design and optimization of collision reduction protocols (anticollision algorithms) is fundamental to the effective use of RFID systems.
In the literature, much discussion on the issue of AntiCollision Algorithms (ACAs) has taken place and protocols proposed
[3

16]
. The proposed protocols are either probabilistic, e.g., Alohabased protocols
[4

10]
, or deterministic, e.g., tree based protocols
[11

13]
. In Alohabased protocols, the channel is slotted into time intervals, whereas in the tree based protocols, a reader iteratively queries a subset of tags matching a certain property of the tag until all tags are identified. Some schemes combine both the Aloha and tree based protocols
[14

16]
.
EPCGlobal G2
[17]
utilizes a simply designed Frame Slotted Aloha (FSA) algorithm as its ACA. Since the performance of the FSA algorithm is dependent on frame size, many schemes utilize a modified version of the FSA algorithm known as DynamicFrame Slotted Aloha (DFSA)
[4]
. The DFSA algorithm dynamically adjusts the frame size with the contending tag population by estimating the number of contending tags in the previous frame. Adjusting the frame size with a contending tag population is an effective way to improve system performance but is not the optimal solution. To achieve optimum system performance, the frame length should not only be dynamically adjusted but also optimally regulated in accordance with the tag population.
Many existing works attempt to find the optimal frame length by assuming that all the time slots are equal and conclude that the highest time system efficiency can be achieved when the number of slots in a frame is equal to the contending tag populations. However, EPCGlobal G2 clearly classifies the slots in a frame into success, collision, and idle slot, each of which has a different slot length. Compiling this information, some researchers
[5]
,
[7]
,
[15]
have tried to present an analytical model to find the optimal frame size based on EPCGlobal G2. However, the conventional analytical models they utilize are limited as they lack precise characterization about the timing details of the underlying ACA.
In this paper, we present an analytical model that precisely characterizes the timing details of each slot in accordance with the EPCGlobal G2 specifications to obtain an optimal frame size. The analytical model presented for optimal frame size is vital for performance improvement of the system, and is thus one of our main contributions. Further, we combine our preciseoptimal frame length model with other conventional models and develop two schemes that can optimize system performance. The schemes are developed with two different methods: one uses the conventional frame size updating mechanism and the other utilizes the tag grouping mechanism. Furthermore, both schemes can utilize the optimal frame length for estimated number of tags and optimize system performance very close to the theoretical upper bound.
We first propose the Improvised Dynamic–Frame Slotted Aloha (IDFSA) algorithm, which optimally assigns the next optimal frame length on the basis of the estimated number of tags in the collided slots from the current frame. This method suggests that the frame length should not only be dynamically adjusted but also be optimally regulated in accordance with the tag population, in order to achieve optimum system performance. We also propose the Exponential Random Partitioning–Frame Slotted Aloha (ERPFSA) algorithm. The ERPFSA algorithm first determines, on the basis of the frame size, whether the unread tags can be optimally accommodated in the given fixed frame size or not. If the remaining unread tags cannot be optimally accommodated in the given fixed frame size, it reduces the contending tag population by force until the applied frame size becomes optimal.
The remainder of this paper is organized as follows: We comprehensively discuss the essential details of the EPCGlobal G2 protocol and a number of dynamic frame adjustment techniques in Section 2. We introduce analytical models and our proposed precise model to estimate the optimal frame length in Section 3. We present the proposed collision reduction protocols in Section 4, and evaluate their performance in Section 5. Finally, we conclude this paper in Section 6.
2. Preliminaries and Related Work
 2.1 Preliminaries
EPC Global is one of the bodies responsible for RFID air interface standards and developed the industrydriven standard for international supply chain networks. Its latest amendment, the EPC Gen 2 Class 1 UHF standard, has been approved by the International Standards Organization (ISO) for publication as an ISO 180006C standard. Both standards detail the parameters for how the reader sends and receives data from the tags. They also specify other technical details such as the frequencies, channels, bandwidth, and modulation scheme to be used. This section gives an overview of the essential details specified in the RFID EPCGlobal G2 standard, which uses the FSA algorithm for medium access control. We also precisely characterize the variable length slots.
 2.1.1 Frame Slotted Aloha in EPC Global
The EPCGlobal G2 protocol utilizes the wellknown FSA algorithm as its ACA. The fundamental principle of this popular protocol is that the fixed time frame determined and broadcasted by the reader is slotted into numerous discrete time intervals (slots), and each tag randomly selects a slot to transmit its identification information.
Fig. 1
(a) shows a successful identification process. The reader begins with tag selection by transmitting the Select command, which activates the tags and requests that they participate in the identification process. After the tags have been activated, the reader sends the Query command, which begins a new frame and requests that each tag generate a 16 bit random number (RN16) to select their transmission slot. The tags maintain their slot counter according to the selected value and decrement it at the end of each slot. As soon as the slot counter reaches zero, the tag replies with RN16. On successful reception of an RN16, the reader sends an Acknowledgement (ACK) command requesting that the tag send its Electronic Product Code (EPC). In response, the tag sends its EPC along with other control messages, such as Protocol Control (PC) and 16 bit Cyclic Redundancy Check (CRC16) code. If there are no errors and the EPC code is valid then the reader begins the next slot by sending a Query Reply (QRep) command. However, if there are errors in the EPC, the reader sends a NegativeACK (NAK) command, which asks the tag involved to try againin the next frame.
Slot durations for Success, Collision and Idle events in the EPC Global G2
Fig. 1
(b) shows collision and idle state processes. When a collision occurs, the reader sends the QRep command to initiate the next slot. Similarly, if no tags reply for a specified threshold time, represented as T3 in
Fig. 1
(b), the reader assumes that the slot is idle and so begins the next slot by issuing a new QRep command.
Each of the above commands, data symbols, preamble, and turnaround transmission periods between the reader and tags are comprised of certain time durations. Therefore, from the parameters presented in the
Table 1
, the slot time duration for success, collision, and idle events (T
_{S}
, T
_{C}
, and T
_{I}
) can be calculated as in (1), (2), and (3):
Timing parameters used to calculate the time duration of each slot
Timing parameters used to calculate the time duration of each slot
 2.1.2 Slot Count Q Selection Algorithm in EPC Global
In the EPCGlobal G2 protocol, the slot count parameter, “Q,” plays a vital role in system optimization. In order to select the optimal Q, the number of interrogating tags (n) should be known in advance. However, in practical scenarios, the exact number of tags is always unknown. As a result, the Q selection algorithm uses information gleaned about the number of successes, collisions, and idle slots in the previous frame and makes changes in the next frame size to optimize the system.
Fig. 2
is an example of the slot count Q selection algorithm given in Annex D of
[17]
. Parameter Q
_{fp}
is adjusted slotbyslot according to the status of the received slot. Q is an integer value (rounded Q
_{fp}
) in the range 0–15. Every tag receives a query command with a frame size N = 2
^{Q}
from the reader and they randomly generate a slot counter between zero and N1. Following this example, during the identification process, Q
_{fp}
is incremented by a floating point value x if a collision is detected and decremented by x if the slot is idle. For the success slot, there is no change in Q
_{fp}
, and so, for the next frame, the size is N = 2
^{round}
^{(}
^{Q}_{fp}
^{)}
. In this way, Q is dynamically assigned in every frame to maximize system performance.
Slot count Q selection algorithm
However, the selection of the initial Q
_{fp}
for the first frame has always been a difficult task without a priori knowledge of the number of tags in the network. Moreover, this Q adjustment strategy leads to poor RFID system performance in dense tag environments.
 2.2 Related Work
The performance of the FSAbased ACA is dependent on a frame size updating approach. Consequently, a variety of approaches that adjusts the number of slots in a frame with the estimated number of tags have been proposed to enhance the performance of RFID systems. In the DFSA algorithm, the reader has the ability to adjust the next frame length dynamically according to the current frame statistics. Some of the DFSA schemes that have been proposed to enhance system performance are discussed in this subsection.
Floerkemeier
[8]
presented a transmission control strategy, called the Bayesian slotbyslot updating scheme, which evaluates the current frame size as the frame progresses. On the basis of empirical results, a normalized x is chosen as x = 0.8/Q. Claims have been made that the performance of the Q algorithm is poor when the Q value is updated with constant x = 0.8/Q. However, the performance of the Q slot count algorithm can be significantly increased when the changes to Q are restricted to incremental changes. Under these conditions, the oscillations of the slot count Q algorithm are damped and the simulated throughput is similar to the other framebased transmission schemes.
Schoute et al.
[4]
proposed an estimation technique that gets the expected number of contending tags that still remain to transmit their information after a frame has been executed. This backlog estimation technique for the DFSA algorithm is exact under the assumption that the frame size is chosen in such a way that the number of users transmitting in each time slot is a Poisson distributed with mean one. The total number of tags that have not been read (C
_{tags}
) is represented as backlog, but whose value after the current frame is then simply given by following relation
[9]
:
where P
_{s}
and P
_{c}
denote the success and collision probability, respectively. Hence, the estimated number of tags (B
_{t}
) is given by
where C is the number of collided slots in a frame.
Note that the processing of the FSA algorithm slows down as the number of contending tags increases. As a result, to accelerate the reduction process, schemes such as dynamic frame length Aloha
[4]
, enhanced dynamic framed slotted Aloha
[5]
, and the Bayesian slotbyslot updating scheme
[8]
have been proposed. Both dynamic frame size adjustment schemes mentioned above depend on the estimated number of tags. Using the estimated value of contending tags and dynamically adjusting the frame size is a smart approach to reduce collisions in the network. However, any frame size calculated based on unrealistic estimation schemes will not be optimal. To achieve optimum system performance, the frame length should not only be dynamically adjusted but also be optimally regulated in accordance with the tag population.
3. Analytical Models to Estimate Optimal Frame Length
Existing proposals to improve the performance of RFID systems focus on adjusting the frame size in accordance with the estimated number of tags and, to the best of our knowledge, there has been no attempt to utilize the optimal frame length. In this section, we introduce an analytical model that obtains a preciseoptimal frame size for the FSA algorithm. We assert that this model is precise because we consider and utilize the precisely characterized time duration of slots, introduced in Section 2, to derive the model.
 3.1 Frame Size Calculation: Conventional Models
Lee et al.
[5]
proposed a metric called System Efficiency (SE) that assumes the time duration of all slot events are equal. SE is defined as the number of successful slots out of the total number of slots, as given in the following equation:
Where S, C, and I denote the number of Success, Collision, and Idle slots, respectively, and N denotes the total number of slots in the frame.
In the FSA algorithm, each tag replies only once in a randomly selected slot, and each frame consists of a different number of slot events. In any arbitrary frame, if the frame size of N slots is used for n number of tags, then the number of tags replying in one slot follows a binomial distribution
[6]
. Thus, the expected number of different types of slots can also be calculated as Success slots:
S
=
n
(1–1 /
N
)
^{n1}
, Idle slots:
I
=
N
(1–1 /
N
)
^{n}
, and Collision slots:
C
=
N
–
S
–
I
. The SE in (6) is consequently defined as
The optimal N (i.e., N*) that maximizes SE can be calculated easily by differentiating SE with respect to N. The widely accepted conclusion is that N* = n, which implies that maximum system efficiency can be achieved when the frame size is selected to be equal to the tag population. However, the frame size calculated here is not correct because it assumes that the duration of success, collision, and idle events are equal. As discussed in the previous section, those event durations are not equal. Porta et al.
[15]
differentiated the duration of idle and success/collision events and derived a new metric called the Time System Efficiency (TSE). In the TSE, the idle slot duration is multiplied by a factor β (with T
_{I}
/T
_{S}
), as expressed in the following equation:
The optimal frame size (N*) for n number of tags can be expressed as
Equation (9) suggests that TSE is maximized when the frame size is selected to be 4.4 times larger than the tag population.
 3.2 Frame Size Calculation: Revised Model
Although the TSE considers different success/collision and idle slot event durations, it does not differentiate the duration of the success and collision events. For EPCGlobal G2, however, those durations are different, as defined in (1) and (2). Therefore, we revise the TSE in (8) to formulate a Precise TSE (PTSE) as follows:
where α is a multiplication factor (T
_{C}
/T
_{S}
).
The optimal frame size (N*) can then be obtained by differentiating
PTSE
with respect to N, as follows:
Solving (11) and finding the roots of N for a different set of tags, the relation between N* and the number of tags n, can be obtained as follows:
Equation (12) suggests that PTSE is maximized when the frame size is selected to be 1.46 times the contending tag population.
4. Proposed Collision Reduction Protocols
In Section 3, we precisely calculated the theoretical optimal frame size, which is one of our main contributions in this paper. We now have to evaluate and prove that the wellchosen frame size is vital for performance improvement in the FSA algorithm. To date, no attention has been paid to exploitation of the potential benefits that can be achieved by using optimal frame size for the estimated number of tags. In an effort to optimize the performance of the RFID system, we contribute two different schemes in which we combine our analytical model with other conventional models; the preciseoptimal frame length parameter is used jointly with the popular tag estimation technique. Unlike previous schemes in which nonpreciseoptimal frame length is regulated, we implement the preciseoptimal frame length for the estimated number of tags.
 4.1 Improved Dynamic Frame Slotted Aloha (IDFSA) Algorithm
Dynamic frame size regulation depends on the current frame statistics that give the number of successes, collisions, and idle slots. Some of the proposals are similar to that of Schoute
[4]
, which estimates the number of unidentified tags by counting the number of collided slots. According to Schoute, each collided slot contains 2.39 times the number of contending tags. Adjusting the frame size with the estimated number of tags can achieve some performance improvement in an RFID system. However, as discussed above, the given frame size is not optimal and the performance improvement achieved is only suboptimal. Therefore, to optimize the performance of RFID systems, the optimal frame size should be used.
In the Improved DynamicFrame Slotted Aloha (IDFSA) algorithm, we combine the Schoute tag estimation approach and our preciseoptimal frame size allocation approach. First, we estimate the number of unread tags with the Schoute collision slots estimation approach and apply our optimal frame size for the estimated unread tags. From our proposed analytical equation for the optimal frame length, the optimal N* required for n number of tags is N* = 1.46 × n. If the estimated number of unread tags from the collided slot is
B_{t}
=
n
, then the system is optimized only when the frame size of N = 1.46 ×
B_{t}
, i.e., N = 3.49 × C is implemented.
Using this optimal frame length approach, the IDFSA algorithm in
Fig. 3
shows the procedure used in the dynamic adjustment strategy and summarizes how the estimation of unidentified tags and control of frame length are achieved in the DFSA algorithm. The interrogation process is similar to that of the FSA algorithm. First, the reader sends a query command with a Q
_{fp}
value that gives the number of slots in a frame (N = 2
^{Qfp}
). Next, a tag has to choose a slot between zero and N1 to send its information. The reader then collects frame statistics such as success, collision, and idle slots and, at the end of the frame, it updates its frame size to N = 3.49 × C and begins a new interrogation process until all the tags are identified.
The IDFSA algorithm
 4.2 Exponential Random PartitioningFrame Slotted Aloha (ERPFSA) Algorithm
A dynamic frame size adjustment mechanism is implemented in IDFSA to maximize the performance of the system. However, the performance of the system can also be increased by reducing the number of contending tags in each frame according to the given frame size. Lee et al.
[5]
implemented a grouping mechanism to adjust the number of tags in accordance with the frame size and discovered that dividing the tags into small groups and adjusting the frame size potentially benefits the performance of the system. However, they did not examine the optimal case in which the given frame size is optimal for the interrogating number of tags. Consequently, to observe the potential benefits of reducing the contending tag population in each frame, we exploit the preciseoptimal frame length and adjust the contending tags in such a manner that the applied fixed frame size becomes optimal.
Let N denote the number of slots in a static frame to read a set of n tags. In IDFSA, we calculated that the frame size will be optimal if N = 3.49 × C, i.e., the frame size will not be optimal if N ˂ 3.49 × C. This implies that the number of collided slots that must be present in a frame to make the given frame size optimal is
C
˂ (1/ 3.49)×
N
, i.e.,
C
˂ 0.29×
N
. If a frame has more than 0.29 × N collided slots the given frame will not be optimal, therefore we have to reduce the contending tag population.
We use the above condition as a threshold value in the ERPFSA algorithm to partition the given set of tags. Assume that the given set of tags is partitioned exponentially with access probability, P
_{a}
. For the first frame, P
_{a}
= 1 is given to all the tags for access to the frame.
Fig. 4
shows the partitioning model in the ERPFSA algorithm. If the algorithm determines that, compared with the frame size, the unread tags cannot be optimally accommodated in the given frame size, then it limits the number of collided tags. If C ˃ 0.29 × N (Condition A), then
P_{a}
=
1/2
, which implies that the access probability of the interrogating tags is reduced by 50%. Consequently, in the second frame, the access number of tags is reduced by fifty percent. Similarly, until the given condition A is correct, the access probability is reduced exponentially and, if condition A is not satisfied, (Condition B), i.e., C ≤ 0.29 × N, we can confirm that the given frame size is optimal for the partitioned number of tags. Therefore, the reader will interrogate all the tags in that partitioned group regulating the fixed frame size. When all the tags in that group have been interrogated,
P_{a}
will be increased by two if
P_{a}
˂ 1 to accommodate the sufficient number of tags for further interrogation. The interrogation process is similar to that of the static FSA algorithm, in which the reader transmits a fixed frame size in every query command and the tag randomly selects one slot in which to send its information. Each tag can only transmit once in each frame and, if it is not recognized in that frame, it has to wait for another frame to transmit its information.
Exponential Random Partitioning Model
To observe the trend in the evolution of access probability, we extracted the values of access probability for various sets of tags (100–500) for a given fixed frame size of 32.
Fig. 5
depicts the evolution of the access probability and also gives the number of fixed frames needed to interrogate a given set of tags. Initially, for all the sets of tags (100–500) the access probability decreases exponentially until a certain access probability level is reached where the contending number of tags is sufficiently reduced. It can also be seen that for 100 tags, the graph again increases exponentially after reaching a certain point. However, for higher tag populations, after reaching a certain level (˂ 0.125), there is only a gradual increase. This is because the reader has to maintain the contending tag population in such a way that the given frame size always becomes optimal. However, this may not be the case when the frame size changes. For instance, if the frame size changes to eight and 100 tags are contending, then the evolution of access probability will change and it may follow a different trend.
Evolution of Access Probability (P_{a}) of various tag population when N is 32
5. Performance Evaluation
In this section, we present the simulation results obtained for our proposed schemes and compare them with those for other schemes specifically, Schoute's dynamic frame adjustment technique, the conventional EPC Global G2 protocol, Floerkemeier's scheme, and the ideal case as a reference. In ideal case, firstly the reader initialize the reading process with the given frame size. After completion of the first frame, we supposed that the reader knows the exact remaining number of tag population that has to be interrrogated, then it implements the optimal frame size (N = 1.46 × n) for those remaining number of tags. Further in the EPC Global G2 protocol, we implemented the slot count Q selection algorithm technique in which the initial Q value is updated on a slotbyslot basis. The Floerkemeier's technique is an improvised slot count Q selection algorithm that uses the Bayesian slotbyslot updating technique. Similarly, in Schoute's DFSA algorithm, we dynamically adjusted the frame size using N = 2.39 × C in each frame.
Note that in the EPCGlobal G2 protocol we implemented the slot count Q selection algorithm in which the current frame size Q
_{fp}
is incremented by
x
whenever the collision occurs and decremented by
x
when an empty slot occurs. The reader then sends a
QueryAdjust
command and a tag has to select a new random value in the range zero and N1. Thus, the random values chosen by the tags are dynamically adjusted instead of the frame size. We implemented the same technique in Floerkemeier's scheme, in which the x value is updated as
x
= 0.8/Q at the end of each slot instead of choosing a value from the range (0.1, 0.5), as in the EPCGlobal G2 protocol.
 5.1 Simulation Setup
We developed a system level simulator in Matlab that can characterize our proposed RFID model. In the simulator, we limited the choice of frame size to 8, 32, and 128 by selecting Q
_{fp}
= 3, 5, and 7 for n tags (10 ≤ n ≤ 1000). In the simulation, we performed 1000 iterations for each tag population in order to converge the simulation results. Each tag was allowed to pick a slot randomly and respond to the reader’s query and, if more than one tag responded in a particular slot, a collision was deemed to have occurred. The collided tags would subsequently be interrogated again until all the tags were identified. Each slot that responded with only one tag was regarded as a successful slot. We assumed that interference and capture effect were absent and that all the tags transmitted only in the selected slot. Further, we checked the performance of the system in two different tag environments; sparse tag environment, for n in the range (10–100) and dense tag environment, for n in the range (100–1000). For the ideal case, the reader starts with the first frame size Q
_{fp}
= 3, 5, 7 and after the first frame the reader is assumed to know the exact number of interrogating tags resulting to making the next frame size as N = 1.46 × n which optimizes the system performance. The ideal case can be seen as an upper bound of performance.
Although there is a difference between PTSE and TSE, as described in Section 3, for convenience we revised the metric TSE as defined similar to our PTSE. It incorporates both the number of slots and its time duration, so that the evaluated performance is more reliable. The revised TSE is defined as the total time duration for successful slots divided by the total time consumed by the system to read all the tags:
where S, C, and I are the total number of successes, collisions, and idle slots that arise during the overall identification process, respectively. In all the algorithms compared, we considered different slot lengths (T
_{S}
, T
_{I}
, T
_{C}
) for all three types of events.
 5.2 Results and Discussion
We evaluated and compared the performance (TSE) of our proposed IDFSA and ERPFSA algorithms with those of other techniques by varying the initial frame size values.
Figs. 6
(a) and (b) depict the TSE for the five algorithms we compared, for initial frame size N = 8. As the number of tags increases, the ERPFSA algorithm as well as the IDFSA algorithm performs better than the other three algorithms in both the sparse and the dense tag environments. This means that both algorithms potentially reduce the collision rate and increase the performance of the system. The performance improvement of the IDFSA algorithm is more than 3% for the dense tag environment. The ERPFSA algorithm also has more than a 2% improvement compared with the other algorithms in the dense tag environment. From the figure, it can be seen that the TSE of the ERPFSA algorithm is lower than that of the IDFSA algorithm. This is because the ERPFSA algorithm uses the static frame size and the initial collision ratio is high in each frame until the active tags in each frame are sufficiently reduced. Moreover, the IDFSA scheme for small number of tags is closer to the ideal case, which implies that the IDFSA scheme can precisely calculate the interrogating number of tags.
Performance (TSE) of the various algorithms for initial frame size N = 8
Similarly,
Fig. 7
(a) shows that with the increase in the initial frame size (N = 32) the performance of the IDFSA and Schoute's algorithm comes closer for sparse tag population (˂ 30). This is due to the fact that the initial frame size can easily accommodate the tags, which are less than the number of slots used in the frame. The performance of the IDFSA algorithm is consistent when the number of tags increases, as observed in
Fig. 7
(b). However, with the use of unreliable and nonoptimal frame length adjustment techniques, the performance of other algorithms rapidly decreases.
Performance (TSE) of the various algorithms for initial frame size N = 32
On the other hand, the ERPFSA algorithm initially deploys a large number of static frames and incurs many collision slots in the dense tag environment. Further, when the tag population is very large (˃ 700), the overhead during frame size adjustment is amortized and, as can be seen, gradual performance improvement results.
In
Fig. 8
(a), the initial frame size has been increased (N = 128), which results in the performance of the IDFSA and Schoute's algorithm being virtually the same for the sparse tag environment. This is because (1) the initial frame size can sufficiently accommodate the sparse tag population and (2) the adjustment in the frame size for such a small tag population does not differ much in the IDFSA and Schoute's algorithms.
Performance (TSE) of the various algorithms for initial frame size N = 128
However, when the number of tags increases, as shown in
Fig. 8
(b), the performance of the IDFSA algorithm is better than that of the other algorithms. Conversely, the performance of the ERPFSA algorithm is below that of the other algorithms. This is because of the large frame size—it either has to waste a large number of idle slots in the sparse tag environment or endure large collided slots initially and a large number of idle slots during the read cycles, in the dense tag environment. Moreover, the graph for the ideal case shows the increasing trend for the large number of tags as shown in
Fig. 7
(b) as well as in
Fig. 8
(b), because the frame size is very small and after certain point, as mentioned above, the overhead due to collision slot is amortized.
Our simulation results contain two significant phenomena. The first is that the IDFSA algorithm has improved performance results for any number of tag populations compared with other algorithms and the performance is close to the ideal case especially for small number of tags. This indicates that our approach of adopting the optimal frame size for the estimated number of tags could potentially improve the performance of RFID systems. The second phenomenon is that the performance of the ERPFSA algorithm decreases as frame size increases. This is because more static frames are wasted as the tag population adjusts, which creates a large proportion of collision slots and results in a significant decrease in performance when frame size is large. However, the ERPFSA algorithm performs well when the frame size is small and also has potential benefits such as the fact that it does not add much overhead and complexity to the RFID system compared with the EPCG2 and Floerkemeier schemes.
6. Conclusion
In this paper, we precisely characterized the time duration of slot events and evaluated the optimal frame size. We presented two collision reduction schemes based on the initially evaluated preciseoptimal frame length that attempt to maximize system performance. First, we proposed the Improvised DynamicFrame Slotted Aloha (IDFSA) algorithm, which optimally assigns a preciseoptimal frame length for the next frame on the basis of the estimated number of collided tags in the previous frame. We also proposed the Exponential Random Partitioning–Frame Slotted Aloha (ERPFSA) algorithm, which exponentially reduces the tag population based on information about the collided slots. This algorithm uses a fixed frame size and reduces the contending tag population until the group of tags partitioned is optimally equivalent to the frame length. Detailed analysis conducted using a Matlab simulator revealed that the IDFSA algorithm, which is more suitable for handling any number of contending tags, performs better than other algorithms in terms of time system efficiency even in dense tag environments and at various initial frame lengths. On the other hand, the ERPFSA algorithm performs well only when the fixed frame size is small. Therefore, the ERPFSA algorithm can be adopted for use in sparse RFID systems in which the least initial frame size can be adjusted. The IDFSA algorithm can be utilized in any RFID system, without any additional overhead and complexity, to improve the performance of the system.
BIO
Sunil Dhakal received B.S. degree in Electronics and Communication Engineering from Tribhubhan University, Kathmandu, Nepal in 2008 and M.S. degree in Computer Engineering from Chosun University, Korea in 2013. His research interests include RFID and WSN.
Seokjoo Shin received M.S. and Ph.D. degrees in Department of Information and Communications from Gwangju Institute of Science and Technology (GIST), Korea, in 1999 and 2002, respectively. He joined the Mobile Telecommunication Research Laboratory, Electronics and Telecommunications Research Institute (ETRI), Korea, in 2002. In 2003, he joined the Faculty of Engineering, Chosun University, where he is currently a Full Professor in the Department of Computer Engineering. He spent 2009 as a Visiting Researcher at Georgia Tech, USA. His research interests include nextgeneration wireless communication systems and network security and privacy.
Finkenzeller K.
2003
RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification
John Wiley & Sons, Inc.
Article (CrossRef Link)
Chen Y.C.
,
Yeh K. H .
,
Lo N.
,
Li Y.
,
Winata E.
2011
“Adaptive Collision Resolution for Efficient RFID Identification”
Eurasip Journal on Wireless Communication and Networks
Article (CrossRef Link)
1
(1)
1 
14
DOI : 10.1155/2011/103027
Klair D.
,
Chin K.W
,
Raad R.
2010
“A survey and tutorial of RFID AntiCollision Protocols”
IEEE Communications Surveys & Tutorials
Article (CrossRef Link)
12
(3)
400 
421
DOI : 10.1109/SURV.2010.031810.00037
Lee S. R.
,
Joo S. D.
,
Lee C. W.
2005
“An enhanced dynamic framed slotted aloha algorithm for RFID tag identification”
in Proc. of The Second Annual Conference on MOBIQUITOUS
Article (CrossRef Link)
166 
172
Vogt H.
2002
“Efficient Object identification with passive RFID tags”
in Proc. of Pervasive Computing
Article (CrossRef Link)
98 
113
Bin Z.
,
Mamoru K.
,
Masashi S.
2005
"Framed ALOHA for multiple RFID objects identification"
IEICE Transactions on Communications
Article (CrossRef Link)
88
(3)
991 
999
Floerkemeier C.
2007
“Bayesian transmission strategy for framed ALOHA based RFID protocols”
in Proc. of IEEE International Conference on RFID
Article (CrossRef Link)
228 
235
Deng D. J.
,
Tsao H. W.
2011
“Optimal Dynamic Framed Slotted Aloha Based AntiCollision Algorithm for RFID Systems”
Springer Journal on Wireless personal communications
Article (CrossRef Link)
59
(1)
109 
122
DOI : 10.1007/s1127701001933
Khandelwal G.
,
Lee K.
,
Yener A.
,
Li Y.
,
Serbetli S.
2007
“ASAP: A MAC Protocol for Dense and TimeConstrained RFID Systems”
EURASIP Journal on Wireless Communications and Networking
Article (CrossRef Link)
(2)
3 
3
Hush D. R.
,
Wood C.
1998
“Analysis of tree algorithms for RFID arbitration”
in Proc. of The IEEE International Symposium on Information Theory
Article (CrossRef Link)
107 
Law C.
,
Lee K.
,
Siu K. Y.
2000
“Efficient memoryless protocol for tag identification”
in Proc. of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications
Article (CrossRef Link)
75 
84
Choi J. H.
,
Lee D.
,
Lee H.
2007
“Query treebased reservation for efficient RFID tag anticollision”
IEEE Communication Letters
Article (CrossRef Link)
11
(1)
85 
87
park J.
,
Chung M. Y.
,
Lee T. J.
2007
“Identification of RFID tags in framedslotted ALOHA with robust estimation and binary selection”
IEEE Communication Letters
Article (CrossRef Link)
11
(5)
452 
454
DOI : 10.1109/LCOMM.2007.061581
La Porta T. F.
,
Maselli G.
,
Petrioli C.
2011
“AntiCollision protocols for singlereader RFID Systems: temporal analysis and optimization”
IEEE Transactions on Mobile Computing
Article (CrossRef Link)
10
(2)
267 
279
DOI : 10.1109/TMC.2010.58
Haifeng W.
,
Zeng Y.
,
Feng J.
,
Gu Y.
2013
“” Binary Tree Slotted ALOHA for Passive RFID Tag Anticollision”
IEEE Transactions on Parallel and Distributed Systems
Article (CrossRef Link)
24
(1)
19 
31
DOI : 10.1109/TPDS.2012.120
2004208
“EPC RadioFrequency Identification Protocols Class1 gen2 UHF RFID Protocol for communication at 860 MHz960 MHz, Version 1.2.0”
EPC global Inc.
http://www.gs2.org/gsmp/kc/uhfcc1g2