1296 IEEE COMMUNICATIONS SURVEYS TUTORIALS.VOL.16.NO.3.THIRD QUARTER 2014 Nonfunctional Research Topics in Protocol Stack Requirements RFID Data Management Efficiency Anti-collision Algorithms PHY Layer Authentication and Privacy Trustworthy Protection Protocols MAC Layer Localization and Activity Localizability Sensing APP Layer Reliability Performance Tuning in Realistic Settings Fig.1.New Research Topics in RFID Data Management collisions.Therefore,effective anti-collision algorithms should TABLE II be customized for RFID systems.Klair et al.provided an COMPARATIVE STUDY OF THE TWO KINDS OF ANTI-COLLISION ALGORITHMS overview of RFID anti-collision protocols [10].Here,to be more specifically,we further classify and elaborate the princi- Binary tree-based anti- Slotted ALOHA-based ples of the most recent research progresses.In the following collision algorithms anti-collision algorithms Advantages Normally deterministic al- The randomized algorithm subsections,we first introduce the anti-collision algorithms in gorithm is used. is used with a good perfor- tag identification,then,two kinds of ingenious techniques are The query tree-based al- mance on average. respectively introduced,i.e.,estimating the tag size and polling gorithms do not require The randomization makes to store the intermediate the results over slots meet the tags based on the anti-collision algorithms. state variable. a certain probability distri- bution,facilitating various statistical analysis A.Tag Identification Disadvantages For the query tree-based The randomness of the al- In regard to the features of RFID system,an effective algorithms,the delay for gorithm makes the "star- tag identification is sub. vation problem"possible. tag identification protocol is expected to have the following ject to the length and dis- some tags can never se properties:1)Simple:the processing logic of the protocol tribution of tag IDs. lect a singleton slot to re- (including the execution flow and the state transition)should spond.In the worst case. be as simple as possible,due to the scarce resource in the tag; the delay approaches+. 2)Efficient:when interrogating a large number of tags,the protocol should provide a light-weight communication mech- anism to avoid unnecessary transmissions of control messages. range.At the beginning of each frame,the reader broadcasts In this way,the high throughput and low transmission delay the frame size f to the surrounding tags,i.e.,the number can be guaranteed. of slots in the following frame.After each tag receives the The current anti-collision algorithms can be divided into frame size f,it randomly selects a slot from the Ist slot to two categories:the tree based anti-collision algorithms [11,12] the fth slot in this frame and responds to the reader.If the tag and the slotted ALOHA based anti-collision algorithms [13- successfully responds,i.e.,no collision happens in the selected 18].The former leverages the binary search tree to divide the slot,then the specified tag is kept silent in the following query collided tag set into two subsets in a recursive approach.In rounds;otherwise,the tag will continue to select another slot regard to those tag sets with opportunities of collisions,the in the next frame to resend the ID.Therefore,there exists one "keeping silent mechanism is used to resolve the collision of the following situations for each slot within the frame:1) problems.The method to divide the sets is comprised of empty slot:no tag responds in this slot;2)singleton slot:only the random binary tree algorithms and the query binary tree one unique tag responds in this slot;3)collision slot:multiple algorithms.Myung et al.[11]proposed an adaptive tree-based tags respond in this slot.Each kind of slot gives different anti-collision algorithm to efficiently identify the tags.Pan et information.Currently,the slotted ALOHA protocol has been al.[12]proposed a smart tree traversal mechanism based on adopted in the EPC C1G2 standard. the query tree,which conducts the tag identification with low In Table II,we respectively compare the two kinds of anti- delay. collision algorithms in terms of advantages and disadvantages. The ALOHA protocol is first used for random access in Generally speaking,there are pros and cons to both kinds of packet radio network.In order to improve the efficiency of tag algorithms. identification in RFID systems,the slotted ALOHA protocol In regard to the slotted ALOHA protocol,the frame size [13,14]is proposed to effectively resolve the collisions.The for each query round is of crucial importance to the overall slotted ALOHA protocol combines a certain number of time performance for identification.For a given tag set,if the frame slots into a"frame".During the interrogation,the reader sends size is too large,then most of the slots in this frame will a continuous wave to energize all tags in the effective scanning be empty slots,causing the waste of slots;if the frame size1296 IEEE COMMUNICATIONS SURVEYS & TUTORIALS, VOL. 16, NO. 3, THIRD QUARTER 2014 Nonfunctional Requirements Efficiency Trustworthy Localizability Reliability Research Topics in RFID Data Management Anti-collision Algorithms Authentication and Privacy Protection Protocols Localization and Activity Sensing Performance Tuning in Realistic Settings Protocol Stack PHY Layer MAC Layer APP Layer Fig. 1. New Research Topics in RFID Data Management collisions. Therefore, effective anti-collision algorithms should be customized for RFID systems. Klair et al. provided an overview of RFID anti-collision protocols [10]. Here, to be more specifically, we further classify and elaborate the princi￾ples of the most recent research progresses. In the following subsections, we first introduce the anti-collision algorithms in tag identification, then, two kinds of ingenious techniques are respectively introduced, i.e., estimating the tag size and polling the tags based on the anti-collision algorithms. A. Tag Identification In regard to the features of RFID system, an effective tag identification protocol is expected to have the following properties: 1) Simple: the processing logic of the protocol (including the execution flow and the state transition) should be as simple as possible, due to the scarce resource in the tag; 2) Efficient: when interrogating a large number of tags, the protocol should provide a light-weight communication mech￾anism to avoid unnecessary transmissions of control messages. In this way, the high throughput and low transmission delay can be guaranteed. The current anti-collision algorithms can be divided into two categories: the tree based anti-collision algorithms [11, 12] and the slotted ALOHA based anti-collision algorithms [13– 18]. The former leverages the binary search tree to divide the collided tag set into two subsets in a recursive approach. In regard to those tag sets with opportunities of collisions, the “keeping silent” mechanism is used to resolve the collision problems. The method to divide the sets is comprised of the random binary tree algorithms and the query binary tree algorithms. Myung et al. [11] proposed an adaptive tree-based anti-collision algorithm to efficiently identify the tags. Pan et al. [12] proposed a smart tree traversal mechanism based on the query tree, which conducts the tag identification with low delay. The ALOHA protocol is first used for random access in packet radio network. In order to improve the efficiency of tag identification in RFID systems, the slotted ALOHA protocol [13, 14] is proposed to effectively resolve the collisions. The slotted ALOHA protocol combines a certain number of time slots into a “frame”. During the interrogation, the reader sends a continuous wave to energize all tags in the effective scanning TABLE II COMPARATIVE STUDY OF THE TWO KINDS OF ANTI-COLLISION ALGORITHMS Binary tree-based anti￾collision algorithms Slotted ALOHA-based anti-collision algorithms Advantages Normally deterministic al￾gorithm is used. The query tree-based al￾gorithms do not require to store the intermediate state variable. The randomized algorithm is used with a good perfor￾mance on average. The randomization makes the results over slots meet a certain probability distri￾bution, facilitating various statistical analysis. Disadvantages For the query tree-based algorithms, the delay for tag identification is sub￾ject to the length and dis￾tribution of tag IDs. The randomness of the al￾gorithm makes the “star￾vation problem” possible, some tags can never se￾lect a singleton slot to re￾spond. In the worst case, the delay approaches +∞. range. At the beginning of each frame, the reader broadcasts the frame size f to the surrounding tags, i.e., the number of slots in the following frame. After each tag receives the frame size f, it randomly selects a slot from the 1st slot to the fth slot in this frame and responds to the reader. If the tag successfully responds, i.e., no collision happens in the selected slot, then the specified tag is kept silent in the following query rounds; otherwise, the tag will continue to select another slot in the next frame to resend the ID. Therefore, there exists one of the following situations for each slot within the frame: 1) empty slot: no tag responds in this slot; 2) singleton slot: only one unique tag responds in this slot; 3) collision slot: multiple tags respond in this slot. Each kind of slot gives different information. Currently, the slotted ALOHA protocol has been adopted in the EPC C1G2 standard. In Table II, we respectively compare the two kinds of anti￾collision algorithms in terms of advantages and disadvantages. Generally speaking, there are pros and cons to both kinds of algorithms. In regard to the slotted ALOHA protocol, the frame size for each query round is of crucial importance to the overall performance for identification. For a given tag set, if the frame size is too large, then most of the slots in this frame will be empty slots, causing the waste of slots; if the frame size