Research on RFID Anti-collision Technology Based on ALOHA Algorithm
1 Introduction to Radio Frequency Identification System Radio Frequency Identification (Radio Frequency IdenTIficaTIon, RFID) is a non-contact automatic identification technology. Compared with traditional identification methods, it can complete information without direct contact, optical visualization, and manual intervention. Input and processing have the advantages of convenient and fast operation, large amount of stored data, good confidentiality, short reaction time, strong adaptability to the environment, etc., and have been widely used in industrial automation, commercial automation and transportation management, etc. One of the hot topics in industry research.A typical RFID system mainly includes three parts: an electronic tag (tag), a reader / writer (Read), and an application system (see Figure 1). The electronic tag is placed on the identified object and is the real data carrier of the RFID system. Generally, the electronic tag is in a dormant state, and it will be activated once it enters the range of the reader, and it will perform wireless non-contact two-way data communication with the reader to achieve the purpose of identifying and exchanging data. In addition, many readers also have additional communication interfaces in order to pass the obtained data to the application system for further processing.
2 When the system anti-collision RFID system works, when two or more electronic tags send data to the reader at the same time within the same reader's scope, signal interference will occur. This interference is called In order to collide, the result will fail the transmission, because appropriate techniques must be used to prevent collisions.
3 ALOHA algorithm and simulation results There are currently a variety of anti-collision algorithms, mainly divided into ALOHA algorithm and tree decomposition algorithm. Because the tree decomposition method may sometimes make the identification delay of some tags longer, the ALOHA algorithm has become one of the most widely used algorithms because of its advantages such as simplicity and easy implementation. The ALOHA algorithm is an algorithm system that is continuously improved based on the characteristics of ALOHA and the characteristics and technical requirements of the RFID system. Its essence is to separate the response time of the tag, so that the tag can send a response in different time slots. Once a collision occurs, the back-off principle is generally adopted, and the response is sent in the next cycle. ALOHA algorithm is divided into frame time slot ALOHA algorithm, dynamic frame time slot ALOHA algorithm and packet frame time slot ALOHA algorithm.
3.1 Frame Slot ALOHA Algorithm Frame Slot ALOHA (Framed slotted Aloha, FSA) algorithm is based on the ALOHA protocol in the communication field. In FSA, "Frame" (Frame) is a period of time defined by the reader, which contains several time slots. The tag randomly selects a time slot in each frame to send data. All tags respond synchronously, that is, information can only be sent to the reader at the beginning of the slot (Slot), the slot sent by each tag is randomly selected. Time slots can be divided into three categories: idle time slots, response time slots, and collision time slots. No label is identified in the idle time slot, and a label can be correctly identified in the response time slot. When multiple tags in a time slot send replies at the same time, a collision occurs, forming a collision time slot. The collided label exits the current loop, waiting to participate in a new frame loop.
The length of the current frame used by the reader is N, the number of tags is n, and the probability of r tags in a slot is:
When r = 1, it means that there is only one tag in a time slot, that is, the successfully read time slot. Therefore, the expected value of the number of tags read in a reading cycle is:
among them, 
Indicates the total number of time slots in which only one label occupies one time slot. The frame length is N, and the total number of tags is n.
The system efficiency is PN:
Figure 2 shows the system efficiency when the length of the frame is 256. When we want to achieve maximum efficiency, make:
According to the above formula, when the length of the frame is N, the number of the most efficient label responses is:
When the number of labels is n, the optimal value of the frame length is: 
When n is very large, expand the above Taylor: 
Therefore, when the number of tags is the same as the number of frame slots, the reader has the highest reading efficiency. When the number of tags does not match the number of frame slots, the reading efficiency will be greatly reduced. If the number of tags is much smaller than the number of frame slots, it will cause a large number of idle slots; and when the number of tags is much higher than the number of frame slots, too many collision slots will be generated; both cases will lead to recognition efficiency Reduction.
3.2 Dynamic Frame Time Slot ALOHA Algorithm To optimize the system efficiency, a dynamic frame time slot ALOHA (Dynamic Framed Slotted Aloha, DFSA) algorithm is proposed to make the number of frame slots equal to the number of tags participating in the cycle. The number of time slots per frame of DFSA can be adjusted in time according to the change of the number of tags, so that the number of tags matches the number of frame slots. When starting a new frame cycle, the reader must estimate the number of tags participating in the frame cycle. This process plays an important role in the entire algorithm. If the estimated number of tags is far from the actual situation, the efficiency of the algorithm will drop significantly, which will affect the stability of the system.
At present, there are two main methods for estimating the number of labels. The first method is that when a collision occurs, at least two tags in a time slot collide. The estimated function of the label is: 
N represents the length of the current frame, C0 represents an idle time slot, C1 represents a successful time slot, and Ck represents the number of collision time slots. When conflicts are frequent, the relative estimation error of this estimation method is large, but it has the advantages of simple method.
Another method is to estimate the number of tags based on the slot binomial distribution. Suppose N represents the length of the current frame, and n represents the number of tags. The number of timeslots for label selection is equal probability. The probability of r tags in the same timeslot, according to the binomial distribution principle, is: 
Use Chebyshev inequality to estimate the number of tags.
3.3 Packet frame time slot ALOHA algorithm In RFID system, we often use dynamic frame time slot ALOHA algorithm. However, there is a limit due to the maximum number of frame slots. When the number of tags is too large, we cannot increase the number of time slots in the frame without limit. Therefore, a group framed slotted Aloha (GFSA) algorithm is proposed. The purpose of grouping is to limit the number of tags' replies so that the tags participating in the identification cycle match the number of slots in the frame. In the GFSA algorithm, if it is estimated that the number of labels to be recognized exceeds the range that the maximum number of frame slots can match, ensure that the labels to be recognized in each group match the maximum number of frame slots.
In Figure 3, regardless of whether one group or two groups are used, the same number of tags with the desired system efficiency will be achieved:
From the above formula we can get n = 354. If the number of unidentified tags is greater than 354, in order to achieve the best system efficiency, we divide the tags into two groups. The grouping algorithm we propose is based on the dynamic frame time slot ALOHA algorithm with a maximum number of frame time slots of 256. In the algorithm, first define:
(1) To achieve maximum system efficiency, the response to the packet label is determined by obtaining the result of the last read frame (0 or 1) to determine the size of the new loop frame.
(2) To reduce the complexity of the RFID system, the number of tags is determined by using the n = c1 + 2ck estimation function.
(3) Use n = 354 derived above as a grouping condition. When the number of tags in the system is relatively small, the dynamic frame time slot ALOHA algorithm with a maximum number of frame time slots of 256 is used. Once the number of tags exceeds 354, the packet frame slot ALOHA algorithm is used to limit the number of tags in the system response. The process is shown in Figure 4.
We use binary tree decomposition method to group tags, as shown in Figure 5. The binary tree structure can effectively search for unrecognized tags. After grouping, the result of the last reading frame (0 or 1) is obtained to determine whether to continue grouping. If the result is 1, it means that the time slot separation condition is reached, and it is necessary to continue grouping the tags until the structure is 0. If the result is 0, it means that the time slot separation condition is not met, and the dynamic frame time slot ALOHA algorithm is used to identify the tag.
The proposed algorithm was simulated. The results show that when the number of tags is less than 354, the ALOHA algorithm of the group frame slot uses the dynamic frame slot ALOHA algorithm; when the number of tags is greater than 354, the ALOHA algorithm of the group frame slot performs group identification on the number of tags. Therefore, the greater the number of tags, the fewer the number of time slots used by the packet frame time slot ALOHA algorithm, and the higher the efficiency. As shown in Figure 6.
4 Conclusion Based on the ALOHA algorithm, this paper separately studies and analyzes the frame slot algorithm and the dynamic frame slot algorithm, and proposes a slotted ALHOA algorithm using binary tree grouping. Compare the proposed grouping algorithm with the traditional dynamic frame slot algorithm. When the number of tags is too large, using this method is conducive to improving system efficiency and reducing the complexity of calculation and operation.
Socket Cover,Metal Socket Cover,Aluminum Power Outlet Cover,Aluminum Power Sockets Cover
Dongguan baiyou electronic co.,ltd , https://www.dgbaiyou.com