Anti-Collision for Mobile RFID – A Review

Anti-Collision for Mobile RFID – A Review

Ankit Ojha Dept. of ISE JSSATE

Bangalore, India

Ayush Pandey Dept. of ISE JSSATE

Bangalore, India

Anisoor Rahman Dept. of ISE JSSATE

Bangalore, India

Bhavika Sharma Dept. of ISE JSSATE

Bangalore, India

Dr. Nethravathi B Dept. of ISE JSSATE

Bangalore, India

Dr. Dayananda P Dept. of ISE JSSATE

Bangalore, India

AbstractIn this paper, a detail review of the various protocols and techniques that address the issue of collision in mobile Radio Frequency Identification (RFID) tags are done. RFID tags can help in extracting vital information about the product to which its attached. Collision is a daunting problem as far as the information retrieval from RFID tags is concerned. There have been different approaches in solving this problem [1] with Hierarchical Q protocol, Pulse Protocol, Mobile Tags Identification Procedure (MTIP), Anti-collision technique (DFSA) and Pulse being some of the approaches. We analyse all the approaches and understand the pros and cons.

KeywordsRFID, MTIP, DSFA

1. INTRODUCTION

   Radio Frequency Identification (RFID) is a technology that is derived from Automatic Identification & Data Capture (AIDC). AIDC group of technologies is concerned with identifying an entity, collecting data and storing the data into arrangements with minimal or no involvement of humans. RFID implements radio-waves to attain the tasks explained earlier. RFID systems comprise three principle components: RFID reader, RFID tagalong with an antenna. The tags contain a combined circuit and an antenna. The reader modulates the radio waves to the understandable form of data. The data poised from the tags is then transferred to the designated computer system in where it can be organised in a composed database. RFID tags like bar codes, hold information, however, RFID tags are capable of storing more information like manufacturer details, type of product and can even sense external parameters like temperature. Bar codes require the scanner to be physically aligned with the code. This isnt required for RFID tags as they dont have a visual factor associated with them. Despite all these advantages, RFID tags have taken really long to be commercially viable as it was really difficult for a full-fledged RFID system to compete with the highly cost-effective Barcodes which are essentiallypictorial representation of information on products that are printed. RFID tags are still more expensive as compared to Bar codes; however, the gap has reduced by a fair margin.

   RFID tags are extensively used in various fields like logistics, inventory management and many more. RFID tags are being increasingly used for monitoring a variety of entities. When the RFID reader gets transmitted into the mobile device, the reader associated with it gets converted into RFID device [2]. When multiple RFID tags and readers are present in the same space of activity, the interaction is hampered. This hampering

   is known as collision. Several approaches have been designed to tackle this problem. Color wave [6], Pulse [8] and Hierarchical Q-Learning [7] and Anti-Collision protocols [1] are some of the solutions. Color wave uses the graph colouring principle. It is a distributed TDMA protocol. It works by allotting time slots to the various readers in the same vicinity of activity. Each reader is allotted a unique colour which is analogous to a unique time slot. A range of colours from 0 to a maximum value is defined. The readers randomly choose a colour from the selected range. The readers fix their time slots to avoid interference from other readers. The requests are queued and are discarded based on the ownership of the current time slots. A reader can even request for a new time slot and notify the other readers. The value of Max colour is based on the number of collisions expected.

   The Hierarchical QLearning (HiQ) makes use of advance learning techniques to understand the collision structure patterns exhibited by the readers and then allot wireless communication channels and time slots based on the recognised patterns. HiQ implements RFID systems in a three-fold structure: reader, R server (reader request regulators) and Qlearning server. Communication can be initiated by the readers once wireless channels as well as time slots is allotted. Collision is handled in such a setup in the following manner:

   In case of collisions, the readers relay a transmission to the R server, which is connected to all the readers in the setup. The R server further communicates the information obtained about collision to the Q Learning server, which applies Q Learning to reallocate the wireless channel and time slots based on the collision data obtained and relays the information about the newly allocated resources to the R server. The R server further allot the adjusted values of resources to the collision conflicted readers. This neatly defined division of tasks makes for a highly efficient mechanism for handling collisions.

   The Pulse based RFID solution is composed of two channels: first one is control channel along with data channel. The readers are present in the control channel whereas the tags are present in the data channel. If a reader present in the control channel detects the desired tag that it wants to gather information from, it relays a signal to other readers in the control channel to notify them about the occupancy of the data channel. This relaying of signals ensures that collision is avoided.

   There are also another class of solutions known as anti- collision protocols. There are further categorized sets of anti- collision techniques: Tree protocol and Aloha protocol.

   The tree protocol has two varieties of solutions: Query trees and Tree splitting. In Query trees, the reader forwards a prefix code to the tags. The tags match the code against their id. If a match is found, the information is exchanged, otherwise, the reader generates longer prefix codes until a match is found. In Tree splitting, a continuous splitting into 2 trees takes place based on the generation of random numbers.

   Aloha Protocol is adopted due to its low cost. The most popular class of aloha protocol is Dynamic Framed Slotted Aloha (DFSA). For DFSA, it is a known fact that it can only be implemented efficiently if the size of the frame is equal to the frequency of the tags. The practical scenario for mobile RFID tags need to address two issues: deal with collision, manage new tags. The prevailing tag estimation techniques can only handle collision. This makes DFSA inefficient for mobile RFID systems.

   The paper analyses the different methods that are used to tackle collision in mobile RFID tags. The approaches that are discussed here are as follows:

   • Color waveprotocol.

   • Pulse protocol.

   • Hierarchical Q Learning protocol.

   • Anti-collision protocol.

2. DESCRIPTION OF THEMETHODS

   1. Colorwave Protocol

      Colorwave represent the subtle protocol which works for restricted network sensors as defined on-line MAC which is distributed over the network like RFID reader. It allows individually the reader to minimalize collisions based on local statistics because of the distributed nature of protocol. For the colorwave [6] to function effectively information sharing and global communication are not essential. To conform to the neighbourhood unsettling influences, colorwave permits the RFID protocol to do as such, similar to the presence of a portable RFID reader or setting up of a creative RFID reader. In this way, to help te reader in achieving a locally ideal correspondence plan and afterwards allowing every reader to minimalize the effects dependent on local measurements, colorwave utilizes confined reader to reader communicate association. Colorwave abuses on the kept idea of running an on-line dispersed, and nearby MAC protocol to reader to label correspondences that diminish reader to reader obstruction.

      The colorwave concept is based upon DCS (Distributed Color Selection) algorithm. In DCS the determined color variable is fixed. If by any chance there occurs a variable between the nodes of the communication, it can be harmful. So, Colorwaveapplies a technique [5] for dynamically fluctuating the extremeamount of colors. The effective transmission percentage is displayed by the individual reader. The percentage of successful transmission is monitored by each reader in Colorwave. For the flexibility to RFID reader networks with variable transmission probability more than one input is needed for color. So, it requires a process for vigorously adapting the newamount of colors at a RFID reader. A random color has to be chosen from 0 to max colors

      to transit. On collision, it takes out the new time slot, also it directs a set of kicks (small control packet) to the entire surrounding to form a new time slot. If the closest color collides with the alternative one, it moves to the next with appropriate new kicks. Though, all the participating readers monitor the proportion of effective transmission in Colorwave.

      Thus, colorwave exhibits a remarkable performance, when done in high load communication. The ability of having reserve the load helps in dealing with a big lumps of communication load. Its a way of measurement to check how good can a communication load can be handled within the all sets of communication load.

   2. Pulse Protocol

      Pulse protocol is yet alternative scheme of anti-collision. Its based on periodic set of beaconing which contains sets of channels, i.e., data channel and the control channel. What data channel does is that it helps in communication of reader-tag. The control channel on the other hand helps communication of reader-reader. Its like a beacon when the signal is sent to the readers, the readers accepts it or avoid it to avoid collision. So, in every phase, the beacon

      [5] sends the signal and corresponding signal is accepted by the corresponding reader. Pulse protocol needs nil support on the side containing tag though much less overhead on the side of the reader and helps excessively to collision avoidance. Further addition can be done on the pulse protocol to avoid the reader collision such as genetic algorithm along with neural networks.

      Fig 1. Flowchart for pulse

      As we can see in the above diagram from the paper [8]. The pulse protocol can be found in just the reader tag and not the tags because as we have seen in earlier explanations, i.e., to avoid the collision. The flowchart depicts the explanation with blocks IDLE, waiting, Contend, and the condition CSMA command channel which results in if its idle or not, transmit BEACON and finally the reading which shows the input of the communication on the reader side.

   3. Hierarchical Q learning protocol

      HiQ is an algorithm developed for the sole purpose of minimizing the reader collisions which occurs mostly in a

      high-density reader environment as in retail sectors for tracking carts and boxes by providing dynamic solutions.

      The authors of the paper [7] came up with the Hierarchical Q learning algorithm based mostly on the working of Q learning algorithm. The Q learning algorithm uses fortification learning to learn patterns of collision and then give time and frequency slots to readers to minimize the collisions occurring between the readers. The collisions have to avoided mostly among the readers due to the low functionality of the tags.

      The objective was to augment the number of readers taking part in the communication of the tags simultaneously avoiding the collisions.

      HiQ has three basic hierarchical levels which consists of the following: Readers, R-servers and Q-servers.

      The readers can only communicate when they have been given a time and frequency slot by the reader level from the R-servers. Readers can detect very well the collisions relating to the frequency and tags however the reader collisions are not detected by the readers. In this situation the R-servers comes into p lay as they are responsible of preventing of collisions between the readers.

      R-servers allocates the resources and time slots required by them only when the dominant Q-learning server or Q-server has authorized them to do so. The Q-servers makes up the top level of the hierarchy and it is the most savvy and competent group of servers. It has high scalability and flexibility which enables rapid solving of the collisions. There is one root node for any HiQ hierarchy.

      Q-learning being a reinforcement algorithm, maps system states to mapped actions which are based either by maximizing any reward or by minimizing the cost. The states are designed in such a way that they represent discrete time stochastic dynamic systems. The student or Q-learning agent chooses the activitydependent on the measures given by the Q-values.

      Q-values are execution measures which are determined using cost / rewardframework.

      The Q values are determined using the following equation:

      The Bellman Optimality Criterion is followed by the optimal policy to get the optimum value of Q as follows:

      1. learning executes recursively to find the most optimum value of Q by maintain a Q table of values that stores all state values, their actions and Q-values.

         The subsequent rule is shown to have converged the Q values to a more discrete Q*(x, a):

         The possible actions for the Q-agent executing on the Q- server comprises of the following options:

         1. Add – adds a resource.

         2. Remove deallocates or removes resource.

         3. Swap swaps between a resource and a node.

      The price function is the most integral part of the Q-agent as

      it is the only function to provide with a feedback. The cost function is one which has the total number of resource requirements, resource allowances, refusals, occurrence and possible tag collisions that are experienced by the user. The cost function ct at any time t.

      After all the potential moves has been calculated the HiQ utilizes a low likelihood randomizer to decide the most ideal

      move out of all the moves thereby avoiding entrapment in just locally optimal solutions and producing the globally ideal arrangement.

   4. Anti-collision protocol

      Anti-collision is a really broad category of algorithms [4]. The four fundamental division is based on division of Space division (SDMA), Time division (TDMA), Frequency domain (FDMA) and Code division (CDMA). The TDMA [9] algorithms are the most widely used as they operate at the lowest cost metric.

      Binary Tree (BT)

      Figure 2: Hierarchy of Anti-collision protocols.

      The core idea is to facilitate a single tag sending data to the reader in a given time slot. There are two broad divisions of the TDMA based anti-collision algorithms: Probabilistic and Deterministic. ALOHA constitutes the probabilistic algorithms. Deterministic algorithms consist of two categories: Query Trees (QT) and Binary Trees (BT).

      1. Deterministic Protocols

         Query Tree (QT)

         Figure 3.1.1: Query Tree protocol tag identification example:

         1. Prefix code tree (b) Query tree.

            The process of identification of tags in QT [11] starts when the reader transmits a command that contains a prefix code. The tags in the range compare the code with their ID and respond in case of a match. Multiple responses indicate a collision which is resolved by splitting the tags into two slots with different prefixes. The reader then sends a prefix code that is longer by 1 bit. Tags in one slot out of the slots ivided earlier transmit IDs to the reader. The reader continues splitting until there is a single tag in a slot and all the tags can be identified. The same process is repeated for all the slots. This marks the end of the tag identification process. Now, the reader can communicate with any tag without collision. The figure 4.1 shows the identification process in QT where 5 tags are identified.

            Figure 3.1.2: Binary Tree protocol tag identification example:

            (a) Identification procedure (b) Binary tree.

            BT implements pseudo random number generator to handle the slot splitting of tags. The responding tags are identified by iterative splitting. All tags maintain a counter variable which is set to 0 by default. A tag can respond only if its counter has a value of 0. The reader labels every response to the command as Collided, Identified or no-response. In case of a collision, tags with the value of the counter zero, increment the counter by 0 or 1. All other tags increment the counter by 1. There is recursive splitting of the responding tags until each slot contains a single tag, that is, all tags have been identified. This leaves us with a scenario where a single or no tag with a counter value of 0 is found. In the case of identification or no- response, all tags decrement the counter by 1.

      2. Probabilistic Protocols Aloha

   ALOHA has three classes of protocols: pure (PA), slotted (SA) and frame slotted (FSA). FSA [10] is the most widely used protocol among the three.

   Pure Aloha (PA)

   In PA, all tags in the range of the reader automatically transfer data (ID and other information) to the reader. In the scenario where multiple tags transfer data simultaneously, collision occurs. For handling collision, the transmission of data by the tags is stopped and the reader allots distinct waiting time to the tags. The tags can now transfer data after the waiting time is over.

   Slotted Aloha (SA)

   SA is a modification of PA where time slots are designed to enable the reader-tag communication. Every tag can send its data only at the starting of a slot. This restriction eliminates the partial collision case, so, only no collision and full collision exists. Slotted aloha boosts channel utilization by almost double compared to pure aloha.

   Figure 3.2.2: PA vs SA

   Frame Slotted Aloha (FSA)

   FSA is organized into frames and frames contain multiple slots. Each tag can choose a slot from the frame. The frame size is constant. Random number generation is used for selection of slots by the tags. The fixed frame size makes the implementation very simple but it comes at a cost of reduction in efficiency. The number of slots in a frame must be chosen taking into consideration the total number of tags. This inefficiency of FSA is tackled by DFSA. DFSA stands for dynamic FSA. In DFSA, the frame size can be changes to eliminate the unused slots in a frame. DFSA has multiple versions and is really flexible. DFSA uses a process to identify the number of tags and the number of collided slots to make an accurate estimate of the number of slots in a frame. It fixes an upper limit and a lower limit. In case the slots where collision exists exceed the upper limit, addition of slots to a frame takes place. In case the slots where collision exists is less than the lower limit, reduction of slots from a frame takes place.

3. ANALYSIS AND DISCUSSION

   Though to understand RFID much better, the advantages and disadvantages tell us the scope and usage of RFID [3].

   ADVANTAGES OF RFID:

   • RFID adds intelligence and flexibility in the procedure to advance the package levels.

   • Allows to read several tags and, thus, increasing the reading speed.

   • Logistics are done easily through RFID which increases security and monitoring.

   • Quickness in speed for locating the certain materials.

   • It supports in evading interfering with the copy of exceptional codes.

   • Reduced amount of manpower required.

   • RFID helps in supporting tag reading with no item- by-item scans required or no line-of-sight.

   • Increased efficiency and high accuracy

     DISADVANTAGES OF RFID:

   • High cost of RFID t1ags.

   • Its quite eases to intercept even though its encrypted.

   • RFID devices are very time consuming to program.

   • Execution can be problematic and time consuming.

   • Some materials may generate signal problem.

4. CONCLUSIONS

   We conclude that given protocols presents different techniques to remove the collision. The given protocols, i.e., color wave, pulse, hierarchical Q learning and anti-collision technique comprises of deterministic and probabilistic protocols are have been reviewed. Further in deterministic protocol, query tree and binary tree have been reviewed and in probabilistic protocol, types of ALOHA classes have been discussed. The DFSA protocol provides the most accurate result that we have acquire from the review, for it to come as the most efficient, thenumber of tags is equal to the frame size.Though the research done on this paper is limited comparing to the futuristic protocol which might give the more efficient and more accurate results.

5. REFERENCES

1. C. Yihong and F. Quanyuan, "A Collision Avoidance Identification Algorithm for Mobile RFID Device," in IEEE Transactions on Consumer Electronics, vol. 65, no. 4, pp. 493-501, Nov. 2019, doi: 10.1109/TCE.2019.2939159.

2. J. Kim and H. Kim, E-Pedigree discovery system and its verification service for consumer's mobile RFID device, in Proc. IEEE Int. Symp. on Consum. Electron., Irving, TX, USA, pp. 14, Jun. 2007, 10.1109/isce. 2007.4382171.

3. Klaus Finkenzeller. RFID Handbook: Radio-Frequency Identification Fundamentals and Applications. 1999, John Wiley & Sons, Ltd.

4. T. F. La Porta, G. Maselli and C. Petrioli, "Anticollision Protocols for Single-Reader RFID Systems: Temporal Analysis and Optimization," in IEEE Transactions on Mobile Computing, vol. 10, no. 2, pp. 267- 279, Feb. 2011, doi: 10.1109/TMC.2010.58.

5. Song, InChan& Fan, Xiao & Chang, Kyung. (2008). Enhanced Pulse Protocol RFID Reader Anti-collision Algorithm using Slot Occupied Probability in Dense Reader Environment. TIIS. 2. 299-311.

6. J. Waldrop, D. W. Engels, and S. E. Sarma, Color wave: a MAC for RFID reader networks, in Proc. IEEE Wireless Commun. Netw. Conf., New Orleans, LA, USA, pp. 12061210, Mar. 2003, 10.1109/wcnc.2003. 1200643.

7. J. Ho, D. W. Engels, and S. E. Sarma, HiQ: A hierarchical Q-learning algorithm to solve the reader collision problem, in Proc. of Int. Symp. Appli. & Internet Works., Phoeniz, AZ, USA, pp. 8891, Jan. 2006, 10. 1109/saint- w.2006.20.

8. S. M. Birari and S. Iyer, PULSE: a MAC protocol for RFID networks, in Proc. of Int. Works. Ubiq. Sens. Netw., Montreal, Quebec, Canada, pp. 10361046, Dec. 2005, 10.1007/11596042_106.

9. X. Jia, Q. Feng, T. Fan and Q. Lei, "Analysis of anti-collision protocols for RFID tag identification," 2012 2nd International Conference on Consumer Electronics, Communications and Networks (CECNet), Yichang, 2012, pp. 877-880,doi:10.1109/CECNet.2012.6202109.

10. T. Cheng and Li Jin, "Analysis and Simulation of RFID Anti-collision Algorithms," The 9th International Conference on Advanced Communication Technology, Okamoto, Kobe, 2007, pp. 697-701, doi: 10.1109/ICACT.2007.358450.

11. D. R. Hush and C. Wood, Analysis of tree algorithms for RFID arbitration, in Proc. IEEE Int. Symp. Informat. Theory, Cambridge, MA, USA, pp. 107107, Aug. 1998, 10.1109/isit.1998.708695.