Research on Anti-collision Problem of RFID Reader

Reader-writer conflict refers to the interference detected by one reader-writer and caused by another reader-writer. It has three main manifestations.

(1) Interference between readers

When a reader transmits a strong signal and interferes with a weak signal reflected by a radio frequency tag, interference between readers and writers occurs, as shown in Figure 1. Reader R1 is located in the interference zone of reader R2. The signal reflected from radio frequency tag T1 reaches reader R1 and is easily interfered by the signal transmitted by reader R2. This interference may occur even if the reading ranges of the two readers do not overlap.

(2) Interference between multiple readers and tags

When multiple readers read the same tag at the same time, it causes interference between multiple readers and tags, as shown in Figure 2, where the reading ranges of the two readers overlap. The signals emitted from readers R1 and R2 may cause interference at RFID tag T1. In this case, tag T1 cannot decrypt any query signals and readers R1 and R2 cannot read T1. Because of the reader conflict, reader R1 can read tags T2 and T3, but cannot read tag T1, so reader R1 indicates that two RFID tags exist instead of 3.

(3) Reader-writer conflict invalidates carrier sensing

Another reader conflict situation is shown in Figure 3. The reading ranges of the two readers do not overlap, but the signal transmitted by reader R2 interferes with the signal transmitted by reader R1 at tag T. This situation also occurs when the two readers are not within the listening range of each other, making carrier sensing ineffective in the RFID network.

In addition to misoperation, reader conflicts also slow down the overall reading rate of the RFID system, and these problems are more serious in mobile or handheld readers. Therefore, reducing reader conflicts is necessary.

2 Related Work and Research

2.1 Main characteristics of reader-writer conflicts

Reader-writer conflicts have the following characteristics:

①The hidden node problem is one aspect of the reader-writer conflict problem. When two readers are not within the range of each other and interfere with the tag, the normal carrier sensing in the RFID network cannot work.

② When the interrogation/transmission signals of multiple readers conflict at a certain RFID tag, the signal at that point will become very chaotic and the RFID tag will no longer be able to receive any interrogation/transmission signals from any reader.

③The RFID tags studied are passive tags, so the tags themselves can neither adjust nor actively communicate with the reader to avoid conflicts. RFID tags can only communicate after being activated by the interrogation signal of the reader.

2.2 Related multi-address mechanisms

The commonly used multiple access mechanism cannot be directly applied to the RFID system because:

①FDMA. In FDMA, readers use different frequencies to communicate with RFID tags. Since RFID tags do not have frequency tuning circuits, they cannot select a specific reader to communicate with. If RFID tags are equipped with frequency tuning circuits, the cost of RFID tags will be greatly increased. Therefore, FDMA is not suitable for use in RFID systems.

②TDMA. In TDMA mode, readers are assigned different time slots to avoid readers asking/sending RF signals at the same time. This is similar to the graph coloring problem in graph theory and is an NP-hard problem. In a mobile network, readers without interference may interfere with each other due to their close movement, and time slots need to be reallocated. Dynamic allocation of time slots reduces the reading rate of the RFID system.

③CSMA. RFID networks, like other wireless networks, have hidden node problems. Readers and writers are not within the range of each other and interfere with the tags. Therefore, relying solely on carrier sensing cannot avoid collision problems in RFID networks.

④CDMA. CDMA requires additional circuits to be added to the RFID tag, which greatly increases the cost of the tag, and it is a very complicated task to assign codes to all tags in the network. Therefore, CDMA is not a low-cost and effective solution.

2.3 Related anti-collision mechanisms

Common anti-collision protocols, such as RTS-CTS, cannot be directly applied in RFID systems because:

① In traditional wireless networks, only one node sends a CTS signal back to the sender. However, in an RFID system, if the reader broadcasts an RTS signal, all tags within the reader's reading range must send a CTS signal back to the sender reader. This requires the design of an additional anti-collision mechanism for these CTS signals, which will make the protocol more complicated.

② It is possible that due to a conflict, some tags (such as T1) did not receive the RTS signal while other tags (such as T2) received the RTS signal. In this case, the CTS signal sent back from T2 cannot determine whether there is no conflict within the reading range of the reader. How to determine whether the reader has received the CTS signal of all tags within its reading range is very important for determining whether there is a conflict in the reader.

2.4 Related reader-writer anti-collision methods

2.4.1 UHF second generation tag standards

The UHF second generation tag standard was developed by EPCglobal. This standard separates the signal transmission between the reader and the RFID tag, so that conflicts can only occur between tags or between readers. This separation allows the reader and RFID tag signals to be transmitted on different channels, solving the interference between readers. However, the tag has no frequency selectivity. Because when two readers communicate with the tag at the same time using different frequencies, the tag cannot be tuned to a specific frequency. Therefore, conflicts will occur at the tag. Therefore, this standard still has interference between multiple readers and tags.

2.4.2 Colorwave Algorithm

The Colorwave algorithm is a TDMA-based distributed algorithm. The algorithm stipulates that each reader randomly selects a time slot (color) from 0 to maxColors to transmit data. If a conflict occurs, the reader selects a new time slot (color) and sends a kick (a smaller control packet) to all its neighboring readers to tell them that it has selected a new time slot (color). If the neighboring readers have the same time slot (color), it reselects a new time slot (color) and sends a kick. This continues. This switching and resident action is called a kick. Each reader keeps track of what color the current time slot is.

The Colorwave algorithm requires time synchronization between readers and writers, and assumes that readers can detect conflicts in RFID systems. However, it is not feasible to detect conflicts at tags with only one reader, unless the tags also participate in conflict detection, and the movement of readers will reallocate time slots, which will propagate throughout the network, making the entire system invalid.

2.4.3 ETSI EN 208 Standard

ETSI EN 208 is a standard developed for RFID readers based on the "listen before talk" of the CSMA protocol. The reader first listens to any ongoing communication on the data channel for a specific small period of time. If the data channel is idle during that period, it will read the tag; if the channel is busy, it randomly selects a backoff time. However, as mentioned earlier, the reader cannot detect collisions by relying solely on carrier sensing.

2.4.4 Q-Learning Algorithm

The Q-learning algorithm proposes a HiQ, multi-layer, online learning algorithm. The algorithm dynamically solves the conflict problem of readers in RFID systems by learning the conflict patterns of readers and effectively allocating frequencies to readers. The multi-layer structure of the Q-learning algorithm is shown in Figure 4. The reader sends a conflict message to the reader-level server layer (R-Server). Then a single R-server then allocates resources to its readers in such a way that there is no interference in their mutual communication. R-Servers are assigned frequencies and time slots by the Q-learning server (Q-server). The root Q-server has full knowledge of all frequency and time slot resources and can allocate them. Unlike R-Servers, Qservers do not have constraints between individual readers, which are inferred through the interactions between servers below this layer.

[page]

If this method is applied in RFID system, there will be the following problems:

①The protocol requires additional management overhead to maintain a multi-layer structure.

② For mobile readers, the uncertain changes in network topology will change the multi-level structure of the Q learning algorithm, which requires reallocation of time slots, which will take more time and make the system invalid.

③Q-learning assumes that the collision detection of readers is not within the mutual listening range of readers. However, not all collisions can be detected, which will lead to incorrect operation of the protocol.

④ The use of time slots requires all readers and writers to be synchronized, and this synchronization will be an additional overhead for the entire system.

In summary, these reader anti-collision methods are not suitable for RFID network systems with mobile readers. Therefore, it is necessary to seek a practical and effective RFID system suitable for various situations.

3 A new algorithm to reduce reader-writer conflicts

3.1 Proposal of a new algorithm

When designing the anti-collision protocol for readers, an important factor to consider is that RFID tags are passive and therefore cannot participate in anti-collision. At the same time, any new functions added to the tags will increase the cost of the tags. Therefore, it is desirable to find an anti-collision protocol that does not involve the tags.

There is a hidden node problem in the RFTD network, as shown in Figure 5. R1 and R2 are not within each other's listening range, but the signal emitted from reader R2 at T interferes with the signal emitted from reader R1. In this case, a notification mechanism is required between R1 and R2. In this way, when R1 and T are communicating, R2 is notified of R1's communication, so R2 can delay communication with the RFID tag. We call this message sent in the form of broadcast a "beacon". When a reader is communicating with an RFID tag, it will periodically send a beacon in an independent control channel.

The communication range of the control channel refers to any two readers that interfere with each other's data channel (the channel used to read tags) and can communicate on the control channel. In Figure 5, although readers R1 and R2 interfere with each other on the data channel, they will communicate on the control channel. This is achieved by transmitting higher power on the control channel than on the data channel. The control channel is a sub-band of the RFID spectrum other than those used for communication between readers and tags. Therefore, propagation on the control channel does not affect any ongoing communication on the data channel. The data channel is used for communication between readers and tags, while the control channel is used for communication between readers and readers. It is assumed that the reader can receive signals on both the control channel and the data channel at the same time.

3.2 Frame format of the new algorithm beacon

The new algorithm is designed only for readers, because RFID tags do not participate in anti-collision activities. The frame format of the beacon is as follows:

① Frame type, indicating that the data packet is beacon data. It can be divided into frame type and sequence number, and the sequence number indicates the number of beacons to be sent.

② Source address, including the address of the reader that transmits the beacon. In this structure, the beacon has no target address because the beacon is broadcasted on the control channel.

③CRC check is used to detect errors and corrections, and is the cyclic redundancy check part of the data packet.

3.3 Workflow and steps of the new algorithm

FIG6 is a flowchart of the algorithm's workflow, which mainly includes the following steps:

① Before the reader communicates with the RFID tag, it must wait for at least tmin in the waiting state. This duration is equal to 3 times the beacon interval. The duration tmin is similar to the DIFS time of the 802.11 algorithm. In this state, every time the reader receives a beacon, it resets the waiting time to tmin.

② If the reader does not receive any beacon after the time tmin is consumed, the reader infers that there are no other readers reading tags nearby. So the reader enters the competition phase and selects a random backoff time from the time interval [OACW]. If it selects i, the reader must wait for i beacon time intervals in the competition state. If the reader receives a beacon now, it loses the current cycle and waits in the next cycle. For example, if a beacon is received at tmin, it will wait for the next tmin. If the random backoff time ends and the reader has not received a beacon, the reader assumes that there are no other readers competing with it, so the reader sends a beacon on the control channel and communicates with the tag on the data channel. The random backoff time helps readers avoid conflicts. Otherwise, many other readers will send beacons at the same time after waiting for tmin. The random backoff time is multiple times the beacon interval, which improves the fairness of the competition.

③When the reader communicates with the tag, the reader sends a beacon every beacon interval on the control channel. The beacon notifies the neighboring readers to prevent them from communicating with the tag, thus avoiding conflicts. After the communication with the tag is completed, the reader returns to the waiting state and continues the remaining cycle.

④ Each time the reader sends a beacon, it first detects the control channel. If the control channel is busy, it will continue to detect. Once the control channel is detected to be idle, the reader waits for a random delay and detects the channel and sends a beacon again. The random delay is a multiple of the beacon propagation delay to avoid conflicts. Otherwise, many readers will send beacons at the same time when the channel is idle. The contention delay and pre-beacon delay in the algorithm are similar to the backoff in a normal wireless network. Once the control channel detects the idle contention delay and pre-beacon delay, the counter decreases; when the transmission is detected, the counter stops timing; when the control channel detects idleness, the counter restarts counting. In addition, if the reader receives a beacon during the backoff period of the contention phase, it will store the remaining backoff calculation time and wait for the next opportunity. For example, if the reader receives a beacon within the tmin time, when the reader re-enters the contention phase, the reader uses the remaining backoff time. The purpose of this is to improve fairness between readers.

4 Conclusion

The distributed reader anti-collision algorithm achieves the purpose of anti-collision by periodically sending beacons on the control channel. Compared with the CSMA mechanism, it can reduce reader conflicts by 1% to 2% and increase the reading rate of the reader by up to 98%. It requires less reader expenses and does not require RFID tags to participate in anti-collision. The algorithm is also suitable for RFID networks of mobile or handheld readers and has great practical value.