Advanced
Precise-Optimal Frame Length Based Collision Reduction Schemes for Frame Slotted Aloha RFID Systems
Precise-Optimal Frame Length Based Collision Reduction Schemes for Frame Slotted Aloha RFID Systems
KSII Transactions on Internet and Information Systems (TIIS). 2014. Jan, 8(1): 165-182
Copyright © 2014, Korean Society For Internet Information
  • Received : August 29, 2013
  • Accepted : January 04, 2014
  • Published : January 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Sunil Dhakal
Seokjoo Shin

Abstract
An RFID systems employ efficient Anti-Collision Algorithms (ACAs) to enhance the performance in various applications. The EPC-Global 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 FSA-based 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 EPC-Global G2 protocol and use it to derive a precise-optimal 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 parametric-heuristic approach to maximize the system performance and propose two simple schemes based on the obtained optimal frame length—namely, Improved Dynamic-Frame Slotted Aloha (ID-FSA) and Exponential Random Partitioning-Frame Slotted Aloha (ERP-FSA). The ID-FSA scheme is based on the tag set estimation and frame size update mechanisms, whereas the ERP-FSA 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 ID-FSA scheme performs better than several well-known schemes in various conditions, while the ERP-FSA scheme performs well when the frame size is small.
Keywords
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 (anti-collision algorithms) is fundamental to the effective use of RFID systems.
In the literature, much discussion on the issue of Anti-Collision Algorithms (ACAs) has taken place and protocols proposed [3 - 16] . The proposed protocols are either probabilistic, e.g., Aloha-based protocols [4 - 10] , or deterministic, e.g., tree based protocols [11 - 13] . In Aloha-based 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] .
EPC-Global 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 Dynamic-Frame 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, EPC-Global 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 EPC-Global 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 EPC-Global 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 precise-optimal 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 (ID-FSA) 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 (ERP-FSA) algorithm. The ERP-FSA 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 EPC-Global 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 industry-driven 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 18000-6C 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 EPC-Global 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 EPC-Global G2 protocol utilizes the well-known 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 Negative-ACK (NAK) command, which asks the tag involved to try againin the next frame.
PPT Slide
Lager Image
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):
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Timing parameters used to calculate the time duration of each slot
PPT Slide
Lager Image
Timing parameters used to calculate the time duration of each slot
- 2.1.2 Slot Count Q Selection Algorithm in EPC Global
In the EPC-Global 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 slot-by-slot 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 N-1. 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 ( Qfp ) . In this way, Q is dynamically assigned in every frame to maximize system performance.
PPT Slide
Lager Image
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 FSA-based 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 slot-by-slot 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 frame-based 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] :
PPT Slide
Lager Image
where P s and P c denote the success and collision probability, respectively. Hence, the estimated number of tags (B t ) is given by
PPT Slide
Lager Image
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 slot-by-slot 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 precise-optimal 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:
PPT Slide
Lager Image
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 ) n-1 , Idle slots: I = N (1–1 / N ) n , and Collision slots: C = N S I . The SE in (6) is consequently defined as
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
The optimal frame size (N*) for n number of tags can be expressed as
PPT Slide
Lager Image
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 EPC-Global 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:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
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 well-chosen 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 precise-optimal frame length parameter is used jointly with the popular tag estimation technique. Unlike previous schemes in which non-precise-optimal frame length is regulated, we implement the precise-optimal frame length for the estimated number of tags.
- 4.1 Improved Dynamic- Frame Slotted Aloha (ID-FSA) 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 sub-optimal. Therefore, to optimize the performance of RFID systems, the optimal frame size should be used.
In the Improved Dynamic-Frame Slotted Aloha (ID-FSA) algorithm, we combine the Schoute tag estimation approach and our precise-optimal 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 Bt = n , then the system is optimized only when the frame size of N = 1.46 × Bt , i.e., N = 3.49 × C is implemented.
Using this optimal frame length approach, the ID-FSA 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 N-1 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.
PPT Slide
Lager Image
The ID-FSA algorithm
- 4.2 Exponential Random Partitioning-Frame Slotted Aloha (ERP-FSA) Algorithm
A dynamic frame size adjustment mechanism is implemented in ID-FSA 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 precise-optimal 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 ID-FSA, 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 ERP-FSA 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 ERP-FSA 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 Pa = 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, Pa will be increased by two if Pa ˂ 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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
Evolution of Access Probability (Pa) 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 slot-by-slot basis. The Floerkemeier's technique is an improvised slot count Q selection algorithm that uses the Bayesian slot-by-slot 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 EPC-Global 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 N-1. 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 EPC-Global 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:
PPT Slide
Lager Image
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 ID-FSA and ERP-FSA 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 ERP-FSA algorithm as well as the ID-FSA 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 ID-FSA algorithm is more than 3% for the dense tag environment. The ERP-FSA 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 ERP-FSA algorithm is lower than that of the ID-FSA algorithm. This is because the ERP-FSA 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 ID-FSA scheme for small number of tags is closer to the ideal case, which implies that the ID-FSA scheme can precisely calculate the interrogating number of tags.
PPT Slide
Lager Image
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 ID-FSA 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 ID-FSA algorithm is consistent when the number of tags increases, as observed in Fig. 7 (b). However, with the use of unreliable and non-optimal frame length adjustment techniques, the performance of other algorithms rapidly decreases.
PPT Slide
Lager Image
Performance (TSE) of the various algorithms for initial frame size N = 32
On the other hand, the ERP-FSA 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 ID-FSA 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 ID-FSA and Schoute's algorithms.
PPT Slide
Lager Image
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 ID-FSA algorithm is better than that of the other algorithms. Conversely, the performance of the ERP-FSA 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 ID-FSA 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 ERP-FSA 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 ERP-FSA 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 EPC-G2 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 precise-optimal frame length that attempt to maximize system performance. First, we proposed the Improvised Dynamic-Frame Slotted Aloha (ID-FSA) algorithm, which optimally assigns a precise-optimal 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 (ERP-FSA) 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 ID-FSA 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 ERP-FSA algorithm performs well only when the fixed frame size is small. Therefore, the ERP-FSA algorithm can be adopted for use in sparse RFID systems in which the least initial frame size can be adjusted. The ID-FSA 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 next-generation wireless communication systems and network security and privacy.
References
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 Anti-Collision Protocols” IEEE Communications Surveys & Tutorials Article (CrossRef Link) 12 (3) 400 - 421    DOI : 10.1109/SURV.2010.031810.00037
Schoute F. 1983 "Dynamic frame length ALOHA" IEEE Transactions on Communications Article (CrossRef Link) 31 (4) 565 - 568    DOI : 10.1109/TCOM.1983.1095854
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 Anti-Collision Algorithm for RFID Systems” Springer Journal on Wireless personal communications Article (CrossRef Link) 59 (1) 109 - 122    DOI : 10.1007/s11277-010-0193-3
Khandelwal G. , Lee K. , Yener A. , Li Y. , Serbetli S. 2007 “ASAP: A MAC Protocol for Dense and Time-Constrained 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 tree-based reservation for efficient RFID tag anti-collision” IEEE Communication Letters Article (CrossRef Link) 11 (1) 85 - 87
park J. , Chung M. Y. , Lee T. J. 2007 “Identification of RFID tags in framed-slotted 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 “Anti-Collision protocols for single-reader 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
2004-208 “EPC Radio-Frequency Identification Protocols Class-1 gen-2 UHF RFID Protocol for communication at 860 MHz-960 MHz, Version 1.2.0” EPC global Inc. http://www.gs2.org/gsmp/kc/uhfcc1g2