A novel RFID anti-collision algorithm

A novel RFID anti-collision algorithm

radio frequency identification (RFID) is a non-contact automatic identification technology. Its basic principle is to use the transmission characteristics of RF signal and spatial coupling (inductive or electromagnetic coupling) to realize the automatic identification of specific objects in the green transformation project. RFID technology can be traced back to the Second World War. Later, it was developed and applied to railway, military cargo tracking and even pet identification. In the past half century, the development of RFID has experienced several important stages, such as technical exploration, experimental research, commercial application and standardization. Judging from the current development trend, RHD will build a bridge between the virtual world and the physical world. It can be predicted that in the near future, RFID technology will not only be widely used in all walks of life, but also integrate with pervasive computing technology, which will have a far-reaching impact on human society

rfid system is generally composed of electronic tags and readers, which have the function of reading multiple electronic tags at the same time. In the RFID system with multiple tags to one reader, tags often transmit data to the reader at the same time, which requires the RFID system to establish an arbitration mechanism to avoid data collision. Considering the limitations of the size and energy consumption of the electronic tag itself, the anti-collision mechanism is required to be as simple as possible while ensuring the function, which is one of the challenges of RFID system design

algorithm a is based on the principles of random avoidance and conflict detection. It uses an 8-bit register and an 8-bit random number generator. The maximum number of arbitrated tags is only 256. Algorithm B is based on the principle of binary numbers and uses an 8-bit register and a 1-bit random number generator. Theoretically, it can arbitrate up to 2256 labels. The literature puts forward an implementation scheme of the algorithm, which has been greatly improved. Algorithm C is similar to algorithm A. It uses one 16 bit register and 16 L-bit random number generators. The maximum number of arbitrated tags is 65536. In this paper, the author proposes an algorithm of cluster avoidance and intra cluster conflict detection and its improved algorithm. Only one 8-bit register and one 1-bit random number generator are needed to realize the arbitration of up to 1048576 tags. Moreover, the number of collisions is greatly reduced compared with that of dry algorithm B

1 description of arbitration mechanism

the core idea of this method is that this research has been laid out since 1997: first, the electronic labels are randomly grouped, and the groups are randomly sorted to achieve random avoidance of group questions, and then conflict detection and label arbitration are carried out in the group. When implementing, the tag only needs one register: using its high-order storage group number and low-order storage of the number of steps to retreat during conflict detection, the implementation is extremely simple. The arbitration mechanism of this algorithm is illustrated in detail by taking an 8-bit register as an example

when the reader/writer initializes the tag, all tags choose an integer between 0 and 15 to be stored in the upper 4 bits of the register (equivalent to randomly selecting a group), set the lower 4 bits of the register to all o, and generate a random number of O or l to be added to the register at the same time. If the number of 8 bits in the register is all 0 at this time, the ID of the tag will be transmitted circularly (ID refers to the unique identification of the electronic tag, which has different meanings in different coding systems). If multiple tags return data at the same time, a conflict occurs. After the conflict occurs, the number in the tag register whose upper 4 bits of other registers are o plus L, while the tag whose 8 bits in the register are all 0 generates a random number of 0 or 1 and adds it to the register. If the register is still all zero after addition. Then continue to return the ID of the tag; If there is no collision during the return, the label with the upper 4 bits of other registers as O will only subtract 1 from the lower 4 bits of the register and repeat the previous return operation. When all the tags whose upper 4 bits of the register are all 0 return the ID, all other tags will subtract 1 from the upper 4 bits of the register and repeat the previous operation

in addition, according to this algorithm, because all labels randomly select groups, there may be too many labels in a group, so that the labels in the group will always collide in the arbitration process, and the label register will always be increased by 1, resulting in the carry from the lower 4 bits of the register to the higher 4 bits. Carry means that the lower 4 bits of the register of all carry tags are cleared and the higher 4 bits are added by 1, which makes these tags no longer belong to the original group and return to the next group, thus optimizing the number of group tags with uneven distribution caused by random selection

in this algorithm, the maximum number of concession steps of labels is 2. Through continuous innovation, we can overcome technical barriers and break through technical bottlenecks by 4=16 steps. Therefore, the maximum number of labels that can be arbitrated in each group is 216=65536, so the theoretical upper limit of the number of labels that can be arbitrated in this algorithm is 16216=

2 algorithm steps

gives the algorithm steps. Assuming that an 8-bit register is used, the algorithm includes the following steps:

(1) design a 4+4-bit register (REL) and a 0, l random number generator (RGI) in the passive side tag of the RFID system, as shown in Figure L

(2) a reader writer on the active side of the RFID system sends an initialization command to all tags in the waiting state. Therefore, the tag enters the arbitration state, generates 4-bit random numbers with RGI, loads them into rel, and clears all the upper 4 bits r7~r4 and the lower 4 bits r3~r0

(3) after waiting for a certain time, the reader/writer sends the command to allow loopback

(4) the tag with rel of all zeros returns the tag ID to the reader writer

(5) if there is only one tag return ID at present, and the reader/writer correctly reads the ID, it sends a confirmation command, adding the low order of the command parameter minus L. After receiving the command, the tag that has returned the ID enters the confirmation state, and the other upper 4 bits are all zero tags RE1, and the lower 4 bits are reduced by 1. Return to step (4) and repeat the operation

(6) if there are currently multiple tags that return IDS, and the reader/writer materials used in aerospace have high requirements for many aspects of physical properties, the wrong ID number is detected through CRC verification or code length verification, then a confirmation command is sent, and the additional command parameter register is added by 1. After receiving the command from the reader writer, all tags in arbitration state and rel is all zero are generated by RGI, and the 1-bit random number is added to the number on the register and reloaded into the register; If the label rel in other arbitration States and the upper 4 bits of rel are zero and the lower 4 bits are not zero, add 1 to rel, return to step (4) and repeat the operation

(7) if there is no tag return ID at present, the reader/writer will send a confirmation command after waiting for a certain time, and the low order of the additional command parameter will be reduced by 1. All labels in arbitration state with high 4 being all zeros, rel lower 4 bits minus 1, return to step (4) and repeat the operation

(8) after the operation of subtracting 1 from the lower 4 bits is repeated l times (L is a system parameter, set by the system, and the empirical value is 4), the reader/writer thinks that all labels in the arbitration state and the upper 4 bits of the register are zero have been correctly read, then sends a confirmation command, adds the command parameter of subtracting 1 from the higher 4 bits, and returns to step (4)

(9) after the label receives the confirmation command of adding the high-order minus l parameter, all labels whose rel high 4 bits are not zero will be reduced by L, and return to step 4 to repeat the operation; Tags that have been zero before being asked to subtract 1 from the high order will return to the waiting state

(10) after repeating the high minus 1 operation for 15 times, the reader/writer thinks that all tags in the arbitration state have been read, then the arbitration process stops, and all tags in the arbitration state return to the waiting state

according to the above algorithm steps, the following improvements are made to form an improved algorithm of this algorithm

a, in step (1), the random number generator generates two groups of random numbers, which are loaded into the upper and lower 4 bits of the register respectively. The number of bits m loaded in high order can be dynamically set to 1, 2, 3 or 4

b, the number of repetitions in step (10) is 2m. Because the improved algorithm also loads random numbers in the lower 4 bits of the register, the probability of label transfer between groups (that is, the probability of low 4 bits to carry high bits) is greatly increased. Especially if the lower 4 bits of the register of the label in the last group are carried in the step of concession, a new group will be generated, so it is necessary to add an additional high-order minus l operation

3 circuit implementation

the reference circuit block diagram of algorithm implementation is shown in Figure L, where RGI is a 01 random number generator; Rel is an 8-bit register. The addition and subtraction functions of adders ADDL and add2 are set according to the command of the reader/writer: when performing the addition operation, add2 of the lower 4 bits needs to carry to ADDL of the upper 4 bits; When performing the subtraction operation, the two devices ADDL and add2 are independent of each other. The adder can work in synchronous state or asynchronous state. When working in synchronous state, the maximum clock of the electronic tag can be used

4 simulation results

simulation L: in order to evaluate the advantages and disadvantages of this algorithm, the following simulation is designed: the label uses 8-bit register, and the high 4 bits are high bits. It is defined as a transmission conflict when 0, 2 and more tags send data at the same time; When only one tag sends data, the transmission is successful, and the average number of conflicts is defined as the ratio of the total number of transmission conflicts to the total number of transmission successes; The empty transfer rate defines the ratio of the number of times o tags send data to the total number of successful transfers. Observe the average number of conflicts when the number of tags is 20~10000

the simulation results are shown in Figure 2. The performance of the algorithm proposed in this paper is close to that of the binary algorithm. On average, every successful transmission is accompanied by two transmission conflicts; The improved algorithm significantly reduces the number of collisions when the number of tags is 50~5000. At the same time, it is also noted that when the number of tags is less than 50, the performance of the improved algorithm decreases. This is because the number of tags is close to the number of clusters, which leads to the increase of space transmission rate. The solution is to reduce the number of clusters. To solve this problem, simulation 2 is designed to analyze

simulation 2: in order to analyze the performance of the improved algorithm at low label density, the following simulation is designed: the improved algorithm is adopted, and 5~8 bit registers are used respectively. The high l~4 bits are high bits, that is, the number of clusters is 2, 4, 8 and 16 respectively. The simulation results are shown in Figure 3. It can be seen that when the total number of tags is 20, if the number of bits of the high-order register is reduced from 4 to 1, the average collision times will fall back from 55 to 1.4. When the total number of tags is 200 and 2000, the change of the high-order register bits has little effect on the average collision times. Therefore, if there are multiple empty transfers in an arbitration, according to this prior knowledge, the reader/writer can instruct the tag to change the number of high bits of the register in the next arbitration, so as to reduce the empty transfer rate, and then reduce the average collision times

the anti-collision algorithm proposed in this paper can arbitrate up to 1048576 tags only by configuring an 8-bit register, an L-bit o, l-random number generator, two 4-bit plus minus l counters and a small number of selection circuits in the electronic tag. Simulation results show that the collision probability produced by this algorithm is significantly less than that of binary algorithm. At the same time, through the flexible setting of the high order of the register, it can effectively solve the problem of high space-time transmission rate of low label density, thus further reducing the collision probability