A Review of Tags Anti-Collision Identification Methods Used in RFID Technology

Abstract

With radio frequency identification (RFID) becoming a popular wireless technology, more and more relevant applications are emerging. Therefore, anti-collision algorithms, which determine the time to tag identification and the accuracy of identification, have become very important in RFID systems. This paper presents the algorithms of ALOHA for randomness, the binary tree algorithm for determinism, and a hybrid anti-collision algorithm that combines these two algorithms. To compensate for the low throughput of traditional algorithms, RFID anti-collision algorithms based on blind source separation (BSS) are described, as the tag signals of RFID systems conform to the basic assumptions of the independent component analysis (ICA) algorithm. In the determined case, the ICA algorithm-based RFID anti-collision method is described. In the under-determined case, a combination of tag grouping with a blind separation algorithm and constrained non-negative matrix factorization (NMF) is used to separate the multi-tag mixing problem. Since the estimation of tag or frame length is the main step to solve the RFID anti-collision problem, this paper introduces an anti-collision algorithm based on machine learning to estimate the number of tags.

1. Introduction

RFID (radio frequency identification) is a self-delivery identification technology that uses radio frequency for non-contact, two-way data exchange [1]. It uses special tags that contain information about the object, which transmit data wirelessly to be read and processed by a reader. The RFID system consists of three main components: tags, readers, and intermediate data processing and management systems. Tags can be attached to objects and contain some chips and antennas that store data. The reader can communicate wirelessly with the tag and read or write data. The data processing and management system is responsible for interpreting and processing the read data and performing corresponding operations. Among them, the tags are divided into passive tags, semi-passive tags, and active tags. However, since the anti-collision process mentioned in this article involves the communication protocol and does not involve the design of tags, the RFID tags in this article do not clearly distinguish between passive and semi-passive.

The basic working principle of RFID technology is not complicated. After the tag enters the working range of the reader, it receives the radio frequency signal sent by the reader. The energy obtained by the induced current sends out the product information stored in the chip (passive tag), or the tag actively sends a signal of a certain frequency (active tag). After the reader reads and decodes the information, it is sent to the central information system for relevant data processing. Among them, the communication and energy sensing methods between the reader and the electronic tag can be divided into inductive coupling and electromagnetic backscatter coupling. Inductive coupling refers to a coupling method that transmits energy and data through the interaction of electromagnetic fields. The reader generates a high-frequency electromagnetic field through the transmitting coil. When the electronic tag is within the range of the electromagnetic field of the reader, the antenna of the tag senses the electromagnetic field and extracts energy from it, and modulates the signal fed back to the reader by changing its own inductance and capacitance. Inductive coupling is suitable for low-frequency (LF) and high-frequency (HF) radio frequency systems, and its advantages are relatively long transmission distances and the ability to communicate with multiple tags simultaneously. Backscatter coupling refers to a coupling method in which the radio frequency signal emitted by the electronic tag reflection reader is used as the return signal. The reader sends a continuous wave radio frequency signal, and the electronic tag constantly switches the impedance of its own antenna to reflect a part of the signal back to the reader, and the reflected signal carries the data information of the tag. Backscatter coupling is usually used in ultra-high frequency (UHF) radio frequency systems, and its advantages are a high transmission rate and fast read speed. The computer system makes corresponding actions according to the received signal [2]. A structure diagram of an RFID system is shown in Figure 1.

In addition, the clock signal is used to synchronize the operation between the reader and the tag, ensuring that the reader and tag operate according to a synchronized time axis during the communication process. In half-duplex (HDX) communication mode, tags use the clock signal to determine when to send data or respond to a reader’s request. In a full-duplex (FDX) RFID system, compared with the HDX mode, the reader and the tag can communicate in both directions at the same time, which means that a clock signal is no longer required for time division. FDX systems allow readers and tags to send and receive data simultaneously, improving communication efficiency and throughput.

RFID technology offers vast commercial potential and a variety of applications. It provides the ability of object identification and tracking and data collection for the internet of things (IoT), thus enabling wider applications and smarter decision making. At the same time, connections to the IoT and cloud platforms enable RFID data to be more widely used in cross-device and cross-system scenarios, which promotes the development and application of the IoT. The technological benefits brought by the advancement of RFID technology encouraged many industries from China to adopt it, as shown in Figure 2. (Data sources: https://bg.qianzhan.com (accessed on 25 August 2023)).

It is precisely because of the rapid development and wide application of RFID technology that the tag signals transmitted by it will conflict due to the sharing of wireless channels. The following mechanisms enable passive RFID tags to recognize and respond to reader requests while avoiding collisions:

• Random reply: Passive RFID tags usually generate a random number through the internal pseudo-random number generator as the reply delay time. When the reader queries the tag, the tag uses this random number to determine the delay time and replies when the delay is over.
• Echo detection: The reader will send a specific signal when communicating with the tag, and then wait for a specified period of time to detect whether there is a tag reply. If the reader does not receive a reply within the specified time, it assumes that no tag is present at that location, thereby avoiding collisions.
• Anti-collision algorithm: When multiple tags are detected by the reader at the same time, the anti-collision algorithm can be used to avoid conflicts. This algorithm allows time-slicing of different tags, allowing them to reply or be acknowledged by readers at different intervals. By comparing the reader’s command with the tag’s identification code, the tags can be identified one by one, thereby avoiding conflicts.

Through random reply, echo detection, and anti-collision algorithms, tags can reply according to established rules, ensuring the accuracy and reliability of communication, and avoiding conflicts caused by multiple tags replying at the same time.

Tag collision refers to the simultaneous response to the reader by two or more tag signals at the same time, so that the returned signals collide with each other. An algorithm for solving this problem is called an anti-collision algorithm [3,4]. None of the tags that caused the collision can be identified, so the tag collision reduces the identification efficiency of the RFID system. At this stage, more domestic and international researchers have studied the problem of RFID system collisions and have achieved good results.

1.1. Research Status at Home and Abroad

In the late 1990s, the MIT Auto-ID Lab proposed storing the relevant information from the tag on a terminal server, thus making it clear that RFID technology is focused on providing identification functions [5]. At the same time, research into the standardization of RFID technology has received a great deal of international and domestic attention, resulting in three major organizations: ISO/IEC in Europe, EPCglobal in the US, and UID in Japan. Meanwhile, China has developed a national standard, GB/T 29768-2013, based on the technical characteristics of RFID and the realities of the country, which has prompted the steady promotion of RFID technology in China. On this basis, researchers have begun to work on the identification and management of large numbers of tags in a variety of scenarios. One of the anti-collision algorithms based on the ALOHA mechanism and tree structure achieves tag identification by collecting the tag IDs in the system [6,7,8,9]. As the recognition efficiency and throughput of traditional anti-collision techniques are too low, RFID anti-collision algorithms based on BSS have been proposed. Therefore, how to design an efficient identification and collection method for anomalous tags has received a lot of attention from both academia and industry.

(1)

Anti-collision algorithm for tags based on TDMA

ALOHA algorithms: The pure ALOHA (PA) algorithm, slotted ALOHA (SA), framed slotted ALOHA (FSA), and dynamic framed slotted ALOHA (DFSA) algorithms are all members of the ALOHA family of probabilistic algorithms. In the PA algorithm, the tag in the conflict slot will randomly evade for a period of time before returning its ID until it is recognized by the reader. However, the avoidance mechanism of PA will lead to the tag in its reply at any time point where other tags may interfere, causing “partial collision”, so the system throughput rate of PA is only 18% [10]. Researchers have gradually introduced better algorithms such as SA, FSA, and DFSA to solve the issue of decreased performance caused by partial collisions. In particular, the SA algorithm [11,12] divides the execution time into multiple segments called slots, so that the tag selects a slot from which to respond. In the event of a collision, the tag waits before choosing a new slot to continue responding until the reader recognizes it.

To further reduce the number of conflicting slots in SA, the FSA algorithm [13] groups a certain number of slots into a frame and specifies that a tag will respond at most once in each frame. Thus, a colliding tag can only respond at the execution of the next frame. The FSA increases the maximum throughput rate to 36.8%, but its frame length is set to a fixed value, creating a large number of idle slots in the recognition process if the frame length is larger than the number of tags in the system; however, severe tag collisions can still occur. DFSA [14] improves the FSA algorithm by counting the number of free slots, conflicting slots, and single slots after a frame is executed to estimate the number of remaining tags to be identified, which in turn adjusts the frame length at the next execution. Therefore, the effectiveness of DFSA depends on quick and precise tag count estimation as well as an appropriate frame length adjustment technique. The literature [15] proposes an RFID anti-collision algorithm, kg-DFSA, that equips the reader with prior information on accurate tag estimates. Using the improved k-means machine learning technique, this paper enhances the DFSA algorithm of the EPC C1G2 protocol with more intelligence in a manner that it uses the prior estimate of tags to predict the exact frame size from scratch. Although the anti-collision algorithm principle of the ALOHA mechanism is simple and the implementation is low in complexity, the upper limit of the throughput rate is only 42.6%. To further improve the system throughput rate, researchers have improved the tag recognition method based on the ALOHA mechanism, combined with the technical advantages of the tree structure algorithm [16,17].

Finally, we compared the performance of several typical ALOHA-type protocols in terms of tag requirements, scheme advantages and disadvantages, and system identification efficiency, as shown in

Table 1. Performance comparison of anti-collision protocols for ALOHA class tags.

	PA [10,18,19]	SA [11,12]	FSA [13,20]	DFSA [14,21,22]
Tag requirements	Timer	Random number generators, timers, synchronization circuits
Advantages	Tags can transmit information at any time.	Eliminates some collision issues.	Reduces duplicate conflicts.	Effectively saves time slots.
Disadvantages	High probability of collision and partial collision problems.	Repeated conflicts are serious.	Prone to a large number of idle or conflicting slots.	The requirements for readers are relatively high.
Efficiency	18.4%	36.8%	36.8%	42.6%
Complexity	$low\underrightarrow{\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}}high$

.

Tree-based algorithms: The three primary categories of anti-collision techniques for tree structures are tree splitting (TS), binary search tree (BS), and query tree (QT). The TS class algorithm is a random tag recognition algorithm and is currently included in the UHF RFID standard ISO/IEC 18000-6B. An efficient anti-collision algorithm is a key aspect which greatly affects the identification efficiency. Adaptive binary splitting (ABS) [23] has been one of the benchmark protocols in this regard. However, this protocol performs binary splitting to resolve collisions, which takes a considerable number of collision cycles to identify a large number of tags. To resolve this, a modified version of ABS has been proposed [24], where instead of performing binary splitting, an m-ary splitting of tags is performed using the tree splitting approach. The performance of the QT algorithm was analyzed in the literature [25], with a throughput rate of approximately 34.8% when the number of tags was greater than 100. Considering that the TS algorithm requires the tag to increase the random number counter and the BS algorithm cannot use the obtained tag information to improve the query, researchers have proposed the simpler and more efficient QT algorithm [26], which has now become the most widely used deterministic anti-collision algorithm.

The performance of the QT algorithm is influenced by the length of the tag ID and its ID distribution. When multiple tags have a long common prefix, the reader needs to receive multiple conflicting signals in order to break up the relevant tags into smaller groups. To this end, researchers have successively proposed a number of improvements [27,28,29,30,31,32,33]. Among them, the literature [27] proposes a dynamic multi-ary query tree collision protocol for RFID systems which can completely eliminate empty slots and greatly reduce collision slots. The proposed scheme is based on an iterative process between reader and tags which aims at locating all collision bits and dynamically encoding them to optimize slot allocation, which reduces the identification time and energy costs. Ref. [28] proposed a new anti-collision protocol, a bit-tracking knowledge-based query tree (BKQT), to effectively overcome the tag conflict problem. The BKQT first constructs a k-tree for all possible tags by using knowledge while it generates bit-collision cases and the corresponding actions for each node in this k-tree by using bit tracking. Ref. [30] proposed a collision tree (CT) algorithm, which uses the Manchester coding mechanism to detect the collision bit in the multi-tag response information, and then determines the subsequent query method and tag grouping, reaching a score of 50% system throughput. Ref. [33] presents an anti-collision technique based on a multi-decimal query tree (MQT) and enhances the CT algorithm. A performance comparison of the tree anti-collision protocols is shown in

Table 2. Performance comparison of tree-type anti-collision protocols.

	QT [25,26,27]	BS [29,31,32]	TS [23,24]
Tag requirements	Prefix matching and synchronization circuits	Have a unique binary identifier and be of equal length	Random number generators, synchronous circuits, counters that store static information
Advantages	Quick and efficient	Effectively avoid read and write conflicts	It is suitable for large-scale tag anti-collision environment
Disadvantages	Not suitable for large number of tags	Prone to performance bottlenecks	The adaptability to dynamic changes in tags is weak

.

(2)

Anti-collision algorithm for tags based on BSS

The principle of the TDMA-based anti-collision algorithm is to narrow down the tag’s response to each query time. These anti-collision algorithms have poor performance when the number of tags is large. Therefore, considering the prior unknown of tag signals, some researchers proposed an anti-collision algorithm based on blind source separation (BSS). In 2009, Yuan and others used the ICA algorithm to separate the collision signal of the RFID system with direct sequence modulation [34]. The results showed that the throughput of this method was nearly double that of the traditional PA algorithm. Based on the problem that the current RFID system does not allow the reader to communicate with different tags at the same time, Ref. [35] proposed a spatial multiplexing technology associated with the BSS, which can identify multiple RFID tags at the same time. With the help of BSS, it can facilitate improved read rates and reduce the time it takes to identify a large number of tags. Their research verified that the BSS algorithm is feasible for dealing with the problem of anti-collision in RFID tags. Therefore, more researchers have proposed different BSS-based anti-collision algorithms [36,37,38].

It can be seen from Figure 3 that the ICA series of algorithms have greatly improved the throughput of the RFID system, breaking through the throughput bottleneck of traditional algorithms. Different from the traditional TDMA algorithm, the ICA algorithm can identify multiple tags at the same time, so that the throughput of the RFID system will be greatly improved. It can be seen from the figure that the DFSA algorithm is an improved algorithm of the FSA algorithm. When the number of labels is less than 200, the throughput of the FSA algorithm is lower than that of the FSA algorithm. However, when the number of labels reaches more than 200, the throughput of the FSA algorithm decreases instead. The overall trend of the ICA algorithm using DFSA grouping is similar to that of the DFSA algorithm, but the overall value is increased by about five times. This is because the ICA algorithm can identify at most the same number of tags as the number of reader antennas each time. If the number of reader antennas is further increased, the throughput of the RFID system will be further improved, but limited by the production cost and production process, the number of antennas of the general reader is not more than eight. Therefore, it is not advisable to expect to increase the RFID system throughput by increasing the number of reader antennas.

The general BSS algorithm requires that the number of observation points be greater than or equal to the number of source signals; that is, the system is in a positive or over-determined state. Therefore, the blind source separation algorithm cannot be directly used to solve the RFID system collision problem in the under-determined state. The non-negative matrix factorization (NMF) algorithm in the blind source separation algorithm is essentially a matrix decomposition under specific constraints [39,40]. By setting the constraints, it can complete the source signal estimation, and applying it to the RFID system in the under-determined state can also complete the separation of the tag collision signal in the under-determined state. Ref. [41] proposed a method of using the constrained NMF algorithm to realize the separation of mixed signals in an RFID system in the under-determined state. The article adopts triple constraints on the NMF algorithm, so that the separated signals meet the requirements of the RFID system. The simulation results show that the throughput of the algorithm is 100% higher than that of the system applying the traditional ICA algorithm in the case of three reader antennas. Since then, more researchers have proposed and improved the anti-collision algorithm for blind source separation in under-determined situations [42,43,44].

As shown in Figure 4, the MSE (mean square error) of different algorithms under the under-determined condition is compared with the change in SNR (signal-to-noise ratio). The mean square error reflects the degree of difference between the estimator and the estimated quantity. The smaller the mean square error is, the more accurate the algorithm is in estimating the source signal, and the better the separation effect of the algorithm is. It can be seen from Figure 4 that the RFID system using the MCV_NMF algorithm as the anti-collision algorithm has a lower error. The MCV_NMF algorithm has the smallest error, followed by the SparseNMF algorithm, then the traditional NMF algorithm, and finally the MinvolNMF algorithm.

(3)

Anti-collision algorithm for tags based on machine learning (ML)

Generally, the number of RFID tags is unknown and must be estimated to set a sufficient frame size and, thus, achieve maximum throughput. This paper summarizes a method for combining machine learning with tag anti-collision algorithms to predict the optimal frame length and improve the accuracy of tag estimation. In the past few years, various methods and approaches have been used for tag estimation.

A study presented in [45] provides a unique tag number estimation scheme called “scalable minimum mean square error” (SMMSE), which improves the accuracy and reduces the estimation time. Effective modification of the frame size arises from two main parameters: the first imposes a limit on the slot occupancy and, thus, the need to expand the frame size; and the second determines the frame size expansion factor. The research presented in [46] introduces a new MFML-DFSA anti-collision protocol. To improve the accuracy of the estimation, it uses a maximum likelihood estimator (multi-frame estimation) that utilizes statistics from many frames. The algorithm selects the ideal frame length for subsequent read frames, taking into account the constraints of the EPCglobal Class-1 Gen-2 standard, based on the expected number of tags. The MFML-DFSA algorithm outperforms earlier proposals in terms of average recognition time and computational cost (lower), making it suitable for use in commercial RFID readers.

The rather novel study presented in [47] proposes an RFID tag anti-collision method applying adjustable frame length modification. The original number of tags is estimated based on the initial assumption that the number of tags identified in the first frame is known. The authors propose a nonlinear transcendental equation-based DFSA (NTEBD) algorithm and compare it with the ALOHA algorithm. The experimental results show that the error rate is less than 5%, and the tag recognition throughput is improved by 50%. The authors of [48] proposed an extension to collision avoidance estimation based on the binomial distribution. They build a simulation module to examine the estimator’s performance in various scenarios and show that the proposed extension has enhanced performance compared to other estimators regardless of the number of tags, whether 1000 or 10,000.

Table 3. The advantages and limitations of commonly utilized ML classifiers.

ML Classifier	Advantages	Limitations
DT [49]	Solves multi-class and binary problems; fast; can handle missing values; easily interpretable	Prone to overfitting; sensitive to outliers
k-NN [50]	Solves multi-class and binary problems; easy to implement	Sensitive to noisy attributes; poor interpretability; slow to evaluate large training sets
SMV [51,52]	Solves binary problems; high accuracy; durable to noise; excellent in modeling nonlinear relations	Training is slow; high complexity and memory requirements
RF [53]	Solves multi-class and binary problems; higher accuracy compared to other models; robust to noise	Can be slow for real-time predictions; not very interpretable
Naive Bayes [54]	Solves multi-class and binary problems; simple to implement; fast	Ignores underlying geometry of data; requires predictors to be independent
ANN [55]	Solves multi-class and binary problems; handles noisy data; detects nonlinear relations between data; fast	Prone to overfitting on small datasets; computationally intensive

shows the advantages and limitations of commonly used machine learning classifiers.

In short, the RFID tag anti-collision algorithm based on machine learning can greatly improve the accuracy and efficiency of tag identification, and reduce interference and repeated reading between tags, especially in large-scale RFID applications. It has high application value and feasibility.

1.2. Contribution of the Work in This Paper

This paper provides an overview of the problems posed by tag collisions and the methods used to solve them. It not only summarizes the traditional RFID tag anti-collision algorithm, but also introduces a novel anti-collision algorithm based on blind source separation and machine learning. The current research mainly solves the problem of tag anti-collision from the aspects of multi-tag identification, reading performance, and anti-interference ability. The main contributions of this paper are as follows:

(1)

An overview of the RFID tag anti-collision principle is presented.

(2)

Comparing the advantages and disadvantages of traditional anti-collision algorithms and introducing the advanced blind source separation anti-collision algorithm.

(3)

The application of machine learning in RFID tag anti-collision algorithm is summarized.

1.3. Organization of This Paper

The paper is structured as follows: Section 1 briefly introduces RFID anti-collision technology and provides an overview of the current state of the research in this technology at home and abroad. Section 2 describes time division multiple access (TDMA)-based RFID anti-collision algorithms and provides a comparison of such algorithms. Section 3 describes the hybrid tag anti-collision algorithm, which combines the advantages of the first two traditional algorithms. Section 4 describes the RFID tag anti-collision algorithm based on blind source separation. Section 5 introduces the anti-collision algorithm based on ML. Section 6 is a summary of the paper and a look at the future.

2. TDMA-Based RFID Anti-Collision Algorithm

Currently, there are four general categories for tag anti-collision algorithms used in near-field communication: time division multiple access (TDMA), frequency division multiple access (FDMA), code division multiple access (CDMA), and space division multiple access (SDMA) [56]. TDMA is the most efficient and widely used approach to address the RFID tag collision problem because the other three solutions have large hardware implementation requirements, complicated algorithms, and are, thus, rarely used. There are two types of TDMA anti-collision algorithms: one based on the ALOHA mechanism and the other on a tree structure, as shown in Figure 5.

In most cases, the antenna in RFID systems, especially those using TDMA/SDMA/CDMA methods, serves both for transmitting and receiving signals. The separation of these functions, such as transmitting and receiving on different frequencies, can be implemented in methods such as FDMA. Therefore, when discussing algorithms in the TDMA range, it is more appropriate to refer to the reader as a read/write device (RWD) rather than just a reader. This acknowledges the dual functionality of the antenna in RFID systems, as it actively participates in both reading and writing data to the RFID tags.

The classic TDMA-based anti-collision method operates at the protocol level, using protocol control to prevent signal collisions and so accomplish the anti-collision goal. The RFID RWD’s ability to recognize the signal from the tag depends on the communication protocol that is selected between the two devices. Several existing RFID air interface protocols that comply with applicable international standards are analyzed here. It was discovered that the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) standards and the global Electronic Product Code (EPC) are utilized more frequently than others. The EPC system is a system that includes EAN/UCC coding and is an important part of the EPC, which is characterized by high communication efficiency. ISO and IEC are the main institutions for customizing international standards. Unlike EPCglobal, which focuses on the 860-960 MHz band, ISO/IEC publishes standards for each band, with different standards containing different frequencies and identification algorithms for RFID devices. ISO/IEC 18000-6C is a global communications standard with higher tag recognition throughput than the ISO/IEC 18000-6B standard, while the ISO/IEC 18000-6B and ISO/IEC 18000-6A standards are suitable for refinement.

Table 4. Table of anti-collision algorithms and their performance under different international standards.

Applicable Frequency Bands	Anti-Collision Algorithms	International Standard of RFID	Throughput	Complexity
HF	QT/PA/FSA	ISO/IEC 18000-3 Mode 1	Low	Low
	DBSA	ISO 14443-3A	High	High
	SA	ISO/IEC 18000-3 Mode 2	Low	Low
	DFSA	ISO 14443-3B	High	Medium
UHF	TS	ISO/IEC 18000-6B EPCglobal Class 0 EPCglobal Class 1	High	High
	Q/FSA/DFSA	ISO/IEC 18000-6C EPCglobal C1G2	High	Medium
	BFSA-muting-early-end	ISO/IEC 18000-6A	Medium	High

ISO/IEC 18000-3 mode 1: basic mode; ISO/IEC 18000-3 mode 2: fast mode.

compares the anti-collision algorithms and their performance under different international standards. Among them, ISO/IEC 18000-3 is applicable to the high frequency band 13.56 MHz, and specifies the physical interface, protocol, command, and anti-collision method between the RWD and the tag. Its anti-collision protocol can be divided into two modes. Mode 1 is divided into the basic type and two kinds of extended protocols (no time slot, no termination, multiple electronic tag protocol and time slot, termination, adaptive polling, multiple electronic tag reading protocol). Mode 2 adopts the time–frequency multiplexing FTDMA protocol, with a total of eight channels, which is suitable for situations with a large number of tags.

2.1. ALOHA-Based Anti-Collision Algorithm

A tag control approach based on the ALOHA algorithm requires that all potential electronic tags be sequentially ordered in the transmit data channel in order to be sent. The quantity of electronic tags determines how quickly this anti-collision device operates; the more tags, the slower the identifying procedure. As a result, this approach is not appropriate in many situations.

(1)

Pure ALOHA algorithm

The pure ALOHA algorithm [57] is the most basic randomness anti-collision algorithm, the basic idea of which is to randomly send information and data to the RWD at some point in time when the tag enters the effective recognition range of the RWD and is activated by the electromagnetic wave signal emitted by the RWD. In the process of the tag sending data, if other tags also send data at the same point in time, it is possible that the data and signals sent by the tag will overlap and a tag collision will occur, thus making it impossible for the colliding tags to be correctly identified by the RWD, as shown in Figure 6.

The more serious major issue that can arise with the pure ALOHA algorithm is the logic control unit’s misjudgment, which occurs when a tag repeatedly sends its information after encountering the collision problem and the RWD considers the tag to be outside of its own valid range of action, misjudging the numerical information encoded on the tag. Another issue with this approach is that it has a poor channel usage and low throughput when there are numerous tags present in the same area of operation, since there is a particularly high possibility of collision during the transmission of encoded data from the tag to the RWD.

(2)

Slotted ALOHA algorithm

The slotted ALOHA (SA) algorithm [58,59] is an improvement on the PA algorithm, which divides time of equal length into multiple time intervals, and such time intervals are called slots. The size of each slot is greater than the duration of communication between the RWD and the tag. The tag can only send return data and information to the RWD within a certain slot, and if two or more tags respond to the RWD at the same time, a tag collision occurs within this slot. This is shown in Figure 7.

Any one slot may be in one of the following three states when employing the SA algorithm to solve the system tag collision problem:

• Successful slot: The RWD can successfully identify the tag supplied within this slot if just one tag transmits back information to the slot.
• Collision slot: If two or more tags transmit back information to the RWD within the slot, the information from the various tags will conflict and cause a tag collision, making it impossible for the RWD to recognize the tag within this slot.
• Idle slot: No tag is present in the slot to provide the RWD with return information.

(3)

Framed slotted ALOHA algorithm

The SA algorithm eliminates part of the collision problem by division into slots, but this case of slots leads to successive collisions of tags. The framed slotted ALOHA (FSA) [60] algorithm, which takes into account the limitations of the SA algorithm, further discretizes the time domain by “bundling” a number of slots into a single frame. The tag located within the effective operating range of the RWD antenna randomly chooses a slot in a frame to send an answer signal. Only once in each frame can a tag choose a certain slot to react to. The quantity of tags and the random fallback space are significant variables impacting the algorithm’s performance. The average ratio of effective slots to total slots in each frame is used to indicate the throughput rate of the algorithm, and the higher the effective communication in each frame, the more effective the recognition, as shown in Figure 8.

The length of the algorithm frame is determined in advance by the RWD, and the system achieves maximum recognition efficiency when the number of tags sending identification codes is close to the length of the frame slot. The shortcoming of the FSA algorithm is that when the frame length is fixed and the number of tags responding is very large, much larger than the frame length, its throughput rate drops rapidly. If the number of tags returning an answer signal in a given slot is much lower than the number of slots, a large number of slots will be left idle, and the system throughput performance will still be poor. The system throughput rate using the FSA algorithm is low when the number of frame slots differs significantly from the number of tags, which is a significant disadvantage of the FSA algorithm.

(4)

Dynamic Framed Slotted ALOHA algorithm

The Dynamic Framed Slotted ALOHA (DFSA) algorithm [61] is also an improved PA algorithm, which is based on the FSA algorithm, in order to make a certain performance index of the system reach the maximum or minimum value when determining the number of tags dynamically according to the number of tags within the RWD recognition range, or successfully identify slots, collision slots, and idle slots to change the size of the ton, thereby optimizing the RFID system. When the number of collision-prone slots surpasses a predetermined upper limit, for instance, the frame size may be increased, minimizing the likelihood of tag collisions. A reduced frame size can increase the probability of tag collisions when the number of collision-prone slots is below a predetermined lower limit. To recognize all tags in this instance, the RWD does not require a lot of slots. The frame size is automatically expanded when the number of tags is high, which lowers collisions and boosts the system’s slot throughput and recognition efficiency. The number of slots within each frame can be dynamically modified, as seen in Figure 9, to be roughly equal to the number of tags responding to the system.

The ALOHA class randomness tag anti-collision algorithm introduced above is the basic RFID tag anti-collision algorithm. All these algorithms have their own advantages and disadvantages and play a role in practical applications.

2.2. Anti-Collision Algorithm Based on Tree Structure

When there are many tags to be recognized, the ALOHA-based tag anti-collision method can take a long time to process, increasing the latency of the system. As a result, many RFID applications employ RWD-controlled deterministic tag anti-collision algorithms. Binary tree algorithms, commonly referred to as splitting algorithms, are the major types of deterministic tag anti-collision algorithms. The binary search method is the most popular one for RFID anti-collision issues since it is the easiest to utilize. For the time being, the emphasis lies in enhancing the binary search algorithm’s overall performance and investigating appropriate encoding algorithms to detect conflicting bits.

(1)

Tree splitting algorithm

The randomized tag recognition technique known as the tree splitting (TS) class algorithm is now part of the ISO/IEC 18000-6B UHF RFID standard. The tag has, among other things, a built-in counter with a start value of “0”. A tag with a counter value of “0” provides its ID response in response to an interrogation instruction that is received from the RWD. The RWD will broadcast collision feedback information to the tags within its recognition range if it detects a conflict signal. This causes the response tag to generate a “0” or “1” random number that it will add to its original count value, dividing it into two groups. Tags with a counter value of “1” are simultaneously added to the initial value, increasing it by “1”. The RWD broadcasts a non-collision feedback message, which causes all tag counters to be reduced by “1” from their initial value, if it does not detect a conflict signal. Figure 10, which depicts the TS recognition algorithm in action, demonstrates that it takes nine slots to recognize four tags.

(2)

Binary search algorithm

The most adaptable and straightforward deterministic technique is the binary search (BS) [62] algorithm, which uses a hierarchical search to pinpoint the precise tag where the collision issue arises. The BS algorithm’s workflow consists of the following, in accordance with its characteristics:

(1)

When a tag enters the RWD’s valid recognition range, the RWD sends a maximum query sequence “Q” to all tags, starting at the same time the transmission of each tag’s individual sequence numbers to the RWD’s reception module.

(2)

The RWD compares the numbers on the same digit of the tag response serial number, and if there is a discrepancy, for example, some tag serial numbers have a “0” in that digit while others have a “1” in that digit, then it can be said that a tag collision has been formed.

(3)

After determining that a tag collision has occurred, the highest collision position of the query sequence “Q” is set to “0”, and the remaining low positions are all set to “1” to obtain a new query sequence “Q”. The number with the largest serial number is excluded one at a time until the RWD compares the number of the serial number of the tag response on the same number of digits is completely consistent, at which point no tag collision has occurred. The number with the least serial number is then chosen at this point.

(4)

The RWD picks the tag pair indicated by the least number of serial numbers, communicates with it, and then puts the tag into a “silent” condition so that it stops responding within the RWD’s recognition range. The tag can reply once more if it is moved both inside and outside of the RWD’s effective recognition range.

(5)

Process (a) is repeated and the tag with the second-to-last serial number is selected for data exchange.

(6)

This process is looped several times until all tags have been successfully identified.

Assume that four tags exist within the radiation range of the RWD antenna, each with the coded sequence numbers 10110010, 10100011, 10110011, and 11100011.

Table 5. Binary search algorithm query process.

Number of Queries	First Query	Second Query	Third Query
Query sequence	11111111	10111111	10101111
Tag A	10110010	10110010	—
Tag B	10100011	10100011	10100011
Tag C	10110011	10110011	—
Tag D	11100011	—	—
Tag Response	1X1X001X	101X001X	10100011
Identification Tags	None	None	Tag B

lists the corresponding binomial tree algorithm implementation process.

The RWD’s query sequence “Q” is too long, and electronic tags must transmit the entire encoding sequence number when the encoding sequence number is too long. This causes redundancy in the BS algorithm, which not only prolongs the algorithm search time but also lowers recognition success rates. Later, researchers introduced the dynamic binary search (DBS) algorithm, an updated technique that has the capacity to dynamically alter the query sequence “Q” and the length of the tag ID throughout the query process, to overcome the redundancy problem of binary search algorithms [63,64]. For each finished query, the BS algorithm will be instructed to start over at the root node, and this algorithm will obviously exhibit redundancy, which not only extends the algorithm’s search time but also results in an unsatisfactory recognition success rate [65]. Many academics have developed various improved BS algorithms, such as the backward binary search algorithm [66], the jumping binary search method [67], the BIBD algorithm [68], etc., for the consideration of these difficulties.

(3)

Query tree algorithm

Given that the BS algorithm cannot use the acquired tag information to enhance the query and that the TS algorithm depends on tags to increase the random number counter, researchers proposed the query tree (QT) algorithm, which is now the most popular deterministic anti-collision algorithm. The RWD command of the QT algorithm has a prefix sequence that is dynamically settable. In response to the RWD, only tags that match the prefix sequence will provide the remaining ID numbers in addition to the prefix sequence. The collision tag will be applied to a new group to be asked again, so the process is repeated until there is only one tag answer. If the RWD detects a conflict signal after this, the “0” and “1” rise in the prefix sequence. Figure 11 depicts the tree structure of the QT method for tag identification. As can be seen, this requires identifying six tags in 13 slots. There are six slots that conflict, one that is empty, and six that are single.

The length of the tag ID and its ID distribution have an impact on the QT algorithm’s performance. The RWD needs to be given several contradictory cues when several tags share a long common prefix in order to separate the pertinent tags into smaller groups. Researchers have, therefore, suggested a variety of improvements one after another. In conclusion, the tree-structured anti-collision algorithms have low time efficiency and are complex to develop, but can reach large throughput rates.

3. Hybrid Tag Anti-Collision Algorithm

The query tree technique can successfully identify all tags, whereas the ALOHA algorithm is random and prone to “tag starvation”, both of which have advantages. In order to offer a hybrid type of tag anti-collision method, researchers have blended the concepts of the stochastic ALOHA algorithm and the deterministic query tree algorithm. There are essentially two types of hybrid anti-collision algorithms.

3.1. ALOHA Algorithm Combined with Binary Trees

The first kind introduces the idea of slots in a tree-based method by directly combining the ALOHA algorithm with a binary tree algorithm. In order to decrease the number of queries, Ryu J’s hybrid query tree (HQT) algorithm [69] incorporates the concept of slots into the QT algorithm. By incorporating dynamic binary search into the HQT algorithm and fusing the ALOHA concept with the tree query process, Wensheng Sun [70]. proposed an effective HQT (EHQT) algorithm. The algorithm flow is shown in Figure 12.

To illustrate the implementation of the algorithm, assume that there are six tags with 9-bit IDs, namely:

tag1: 000001110    tag2: 001101110

tag3: 001111010    tag4: 100100110

tag5: 011101010    tag6: 011110110

(1)

The RWD initializes to empty the queue stack and sends the request command (NULL).

(2)

All tags within range of the RWD will respond, not at the same time, but with response slots based on the first 3 bits of information. Tag 1 responds immediately. Tags 2, 3, and 4 respond after a one-slot delay. Tags 5 and 6 respond after a two-slot delay.

(3)

At compensation slot 0, there is only one tag, which the RWD identifies directly. At compensation slot 1, there are three tag responses, encoded by Manchester, decoded to obtain X0X1XXX10, and the RWD identifies the search string as 001 and 100 based on the first three pieces of information pressed into the search queue stack. At compensation slot 2, there are two tag responses, which are decoded to give 0111XXX10, and again, the search string is determined to be 011 based on the first three pieces of information, which are pressed into the search queue stack. At this point, the search strings in the stack are 001, 100, and 011.

(4)

The RWD sends the search request command (request 001), tags 2 and 3 respond, and at this time the tag sends the response bits for bits 4 to 9, where tag 2 responds at compensation slot 2 and tag 3 responds at compensation slot 3. If there is only one tag response at each of compensation slots 2 and 3, the RWD recognizes it directly.

(5)

The RWD sends the search request command (request 100), and tag 4 responds at compensation slot 1 for direct recognition.

(6)

The RWD sends the search request command (request 011), tags 5 and 6 respond at the compensation slot 2, the tag sends bits 4 to 9, which are encoded by Manchester and decoded to 1XXX10, and the RWD determines the new search string as 011101 and 011110 based on the first three bits of information obtained from the decoding and presses them into the search queue stack.

(7)

The RWD sends the search request command (request 011101), tag 5 responds at compensation slot 1, and the RWD recognizes it directly.

(8)

The RWD sends the search request command (request 011110), tag 6 responds at compensation slot 2, and the RWD recognizes it directly. At this point, all tags are recognized. End of story.

It is evident from the study above that a total of six interviews were necessary to identify the six tags. It requires 11 inquiries when the QT algorithm is used, and 20 questions when the HQT algorithm is used. It is evident that the number of inquiries has greatly decreased as a result of the revised HQT algorithm. Due to the significant number of additional idle cycles present in this case, the HQT algorithm has more queries than the QT algorithm, making it appropriate for cases involving more tags. However, the upgraded and efficient HQT algorithm does not face this issue because there are no idle cycles present.

The implementation process is shown in Figure 13. Where “*********” indicates a silent state, i.e., the tag is recognized and no longer responds to RWD queries; “_________” indicates that the tag does not respond; and “++++101110” indicates that the RWD responds and only 101110 is returned.

Later, the DFSA algorithm and the group collision tree algorithm (CGCT) were combined [71] to create the CG-DFSA algorithm for dynamic environments. This algorithm first uses the DFSA algorithm to assign frame lengths and identify tags before using the CGCT algorithm to identify collision tags. The algorithms QT-DFSA and RBS-DFSA are suggested in Ref. [72]. The QT-DFSA algorithm combines the QT and DFSA algorithms by first grouping tags according to the QT method, then identifying tags with the help of the dynamic framed slotted algorithm, and finally grouping them once more in accordance with the number of tags successfully identified. The RBS-DFSA algorithm combines the RBS and DFSA algorithms, first grouping data with the RBS method then identifying it with the DFSA algorithm. The grouping technique and the transmission of the identification code are different from the QT-DFSA algorithm. The RBS-DFSA technique reduces the amount of data transmitted by sending only the tag serial number portion of the transmission.

3.2. ALOHA Partitioning Ideas Combined with Tree-Based Algorithms

The second variant combines a tree-based algorithm with the ALOHA partitioning concept. By recommending a better hybrid query tree method, that pre-processes the tags and separates them into subsets to increase recognition efficiency, Ref. [73] has enhanced the HQT technique. Later, further researchers integrated the ALOHA partitioning concept with the binary tree algorithm [74,75,76], greatly enhancing both the algorithm’s performance and the system’s throughput. A dynamic framed slotted binary tree (DFBT) RFID anti-collision technique was proposed in 2018 [77] by combining dynamic frame slots with tree algorithms. First, the number of tags to be recognized is estimated using the Vogt technique. The frame length is then dynamically altered to recognize some of the tags, and the remaining unrecognized tags are then split on the left and right subtrees using the binary tree method. The algorithm decreases the overall number of slots, increases recognition stability, and lowers tagging costs.

The core of the DFBT algorithm is the use of an optimized DFSA algorithm for tag recognition and a binary tree algorithm for collision tag recognition. Additionally, the DFBT algorithm performs a tag estimation operation prior to the first tag recognition, counts the number of tags in the left and right subtrees of the binary tree after each round of recognition, and calculates the frame length for the following round of recognition. The highest collision bit is indicated by the “0” tag counter on LSC, while the “1” tag counter on RSC is indicated by the highest collision bit on each tag in the RFID system. The algorithm flow is shown in Figure 14.

The specific process of slot scanning is demonstrated with a concrete example. Suppose the system is to identify the tags A–J, and their ID codes are 11010111, 10100111, 01011111, 10111010, 01111101, 10001011, 00110111, 10101110, 01110000, and 11100110.

Frame slot processing phase: The number of tags to be identified in the first frame is estimated to be 10, and the number of tags to be identified in the second frame is estimated to be 3 using the Vogt algorithm. In the first frame, m = 3, and frame length L = 8. According to the tag selection slot rule, the tags each choose their own slot to respond to, so from (110)${}_A$ = 6, (101)${}_B$ = (101)${}_D$ = (101)${}_H$ = 5, (010)${}_C$ = 2, (011)${}_E$ = (011)${}_I$ = 3, (100)${}_F$ = 4, (011)${}_G$ = 1, (111)${}_J$ = 7, the slot numbers of the tags A–J responses are 6, 5, 2, 5, 3, 4, 1, 5, 3, and 7.

In the second frame, with m = 1 and frame length L = 2, tags B, D, and H enter into a similar slot processing operation as in the first frame, with (0)${}_B$ = (0)${}_H$ = 0 and (1)${}_D$ = 1 resulting in tags B, D, and H responding with slot numbers 0, 1, and 0, respectively. In this way, through the sequential scanning of the slots, the results of the idle, success, and collision states of each slot can be seen at a glance, and the tags responding to the success slot state are the successful identification tags, while the tags responding to the collision slot state are the collision tags, and these collision tags must then proceed to the next step of the “collision tag processing phase”.

Collision tagging stage: The collision tags E, I, B, D, and H are generated after the first frame slot processing is complete, and the RWD detects the highest collision bit of each of these five tags according to the Manchester encoding: $k_E=k_I=0,k_B=k_D=k_H=1$. So, tags E and I respond in the left subtree of the binary tree, then LSC = 2, and tags B, D, and H respond in the right subtree of the binary tree, then RSC = 3.

According to the DBFT method in Figure 14, tags E and I do not need to enter the “frame slot processing phase,” or second frame processing, because their LSC is equal to two. According to the Manchester encoding, the RWD picks up the highest collision bits as 1Ek and 0Ik, respectively. As a result, tags E and I are correctly recognized because tag E responds on the right subtree (RSC = 1) and tag I responds on the left subtree (LSC = 1).

The DBFT algorithm flow shown in Figure 14 indicates that tags B, D, and H must proceed to the “frame slot processing phase,” or second frame processing step, because these three tags have RSC = 3. In the second frame slot processing phase, tag D is successfully identified, however tags B and H cause collisions and their identification is comparable to that of tags E and I. The specific example demonstrates the process as shown in

Table 6. DBFT implementation process.

Number of Rounds	1	2	3	4	5	6
$R\stackrel{Request}{⟶}T$	0		01110	01111	10100	10101
Tag E	1111101
Tag I	1110000		000	101
Tag B		0100111			111
Tag D		0111010
Tag H		0101110				110
Counters	LSC = 2	RSC = 3	LSC = 1	RSC = 1	LSC = 1	RSC = 1
k-value	k = 0	k = 1	k = 0	k = 1	k = 0	k = 1
$T\stackrel{Response}{⟶}R$	Collision	Collision	I	E	B	H

R—RWD, T—tag.

.

The IDFSA algorithm, which was proposed in Ref. [78] the year after, utilized the DFSA algorithm to estimate the number of tags, categorized them into the ideal number of groups, and then used the IBS algorithm to identify the tags, preventing “tag starvation”. Ref. [79] proposes an enhanced adaptive tree time slot algorithm that groups tags according to frame length F, after which an improved binary method to identify tags outperforms the existing ALOHA algorithm. A hybrid approach based on ALOHA and multinomial trees was proposed in Ref. [80] in June 2021. It integrated ALOHA and multinomial tree techniques. During the dynamic frame slot phase, the tags are separated into slots according to ID numbers, and each slot’s condition is then decided. Slots with collisions proceed to the multinomial tree search stage, where an adaptive binary or quadtree is chosen for querying. This approach increases the effectiveness of tag queries while reducing the depth of the query tree. The AMTS technique, which is more appropriate in large-scale systems, was proposed in Ref. [81] in 2021. It first maps tags to various slots using a frame slot algorithm and then finds collision tags using a binary algorithm.

4. BSS-Based RFID Anti-Collision Algorithm

The tag signal’s anti-collision issue is actually the signal blind source separation (BSS) issue because of the tag signal’s previously unknown nature. Therefore, the multi-tag anti-collision problem is summarized in this study as a source signal separation problem from the perspective of signal processing at the transmission layer of the system communication.

A tag cluster, a multi-antenna RWD, and a computer system make up a blind source separation (BSS)-based RFID system (Figure 15). Tags that are within the RWD’s detection range transmit identification signals to the RWD, which are picked up by several antennae. Through the antenna mix, a blind source separation processing unit in the RWD recognizes these tags, records the pertinent data, and then delivers the data to the computer system for pertinent data processing.

In the practical application model, many observed signals can be regarded as a mixture of multiple source signals. After the output of the sensor is transmitted, the signal received by each receiving sensor is a signal mixed with different weights. The BSS algorithm can separate the source signal we need from the received mixed signal. Assume a mixed signal collected by a system with multiple sensors is

$$\mathbf{X}\left(k\right)={[{\mathbf{x}}_1\left(k\right),{\mathbf{x}}_2\left(k\right),\dots ,{\mathbf{x}}_m\left(k\right)]}^T$$

(1)

However, the source signal sent by the real sensor is

$$\mathbf{S}\left(k\right)={[{\mathbf{s}}_1\left(k\right),{\mathbf{s}}_2\left(k\right),\dots ,{\mathbf{s}}_n\left(k\right)]}^T$$

(2)

We neither know the source signal nor the mixing method of the source signal, and obtain an unmixing matrix $\mathbf{W}$ through the blind source separation algorithm. Assuming that the output of the system is $\mathbf{Y}\left(k\right)$, then

$$\mathbf{Y}\left(k\right)=\mathbf{WX}\left(k\right)=\mathbf{WAS}\left(k\right)\approx \mathbf{IS}\left(k\right)$$

(3)

We need to determine the unmixing matrix $\mathbf{W}$ based on some prior knowledge of the source signals, such as the independence or sparsity of the source signals. Given that the tag signals used in RFID systems have the following properties:

• Statistically independent and non-Gaussian;
• Insensitive to sign changes in the signal;
• The requirement of the algorithm for the uncertainty in the signal order is satisfied by the identification of the tag signal, which is independent of the order.

Therefore, using blind source separation techniques, it is possible to separate the signals from the identification tags.

4.1. BSS Algorithm for Determined RFID Systems

Since 2002, French scholar Y. Deville has applied blind source separation algorithms to RFID systems to handle multiple tags accessing the system at the same time [82], thus pioneering the use of blind source separation (BSS)-based RFID tag anti-collision. More and more scholars have since combined blind source separation algorithms with RFID systems as a way to improve the efficiency of RWD in identifying tag signals. Among them, the independent component analysis (ICA) algorithm is the most widely used for tag collisions in over-determined or positive-determined cases. The steps are as follows:

(1)

Form the original data into an n-row, m-column matrix $\mathbf{X}$ by columns.

(2)

Zero-mean each row of $\mathbf{X}$ (representing a feature), i.e., subtract the mean of this row.

(3)

Pre-processing the data for whitening.

(4)

Set the value of the parameter learning rate $\alpha$.

(5)

Solve for $\mathbf{W}$ at moment i, where initially $\mathbf{W}$ can be assigned to a random matrix with a sum of one in each row.

(6)

The source signal ${\mathbf{S}}_{n\times 1}^{\left(i\right)}$ at moment i will be solved based on the $\mathbf{W}$ obtained in the previous step and formula ${\mathbf{S}}_{n\times 1}^{\left(i\right)}={\mathbf{W}}_{n\times n}·{\mathbf{x}}_{n\times 1}^{\left(i\right)}$.

(7)

Repeat steps (4) and (5) to solve the source signal ${\mathbf{S}}_{n\times 1}^{\left(i\right)}$ at all times.

(8)

Combine the source signals obtained at each time to obtain the final result ${\mathbf{S}}_{n\times m}=[{\mathbf{s}}^{\left(1\right)},{\mathbf{s}}^{\left(2\right)},\dots ,{\mathbf{s}}^{\left(m\right)}]$.

The ICA approach reduces the statistical correlation between the signal’s many components while emphasizing the source signal’s fundamental structure. The FastICA fixed-point algorithm [83], which needs input data and pre-processing, is one of the most often used ICA algorithms. To centralize the data, we can remove the mean of the signals that were received:

$$\mathbf{X}=\mathbf{X}-E\left(\mathbf{X}\right)$$

(4)

where $\mathbf{E}(·)$ is the expectation. The whitening process can be completed using the following steps: First, calculate the eigenvalues of the received data $\mathbf{E}=({\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_m)$ and eigenvector $\mathbf{D}=({\mathbf{d}}_1,{\mathbf{d}}_2,\dots ,{\mathbf{d}}_m)$. Then, calculate the whitening matrix using the following method:

$$\mathbf{T}={\mathbf{D}}^{-1/2}{\mathbf{E}}^T$$

(5)

Whitening data:

$${\mathbf{Y}}_{\mathbf{1}}=\mathbf{TX}$$

(6)

The data were then successfully separated using the FastICA algorithm. The FastICA algorithm finds the solution mixing matrix by iterating over the objective function:

$$J\left(\mathbf{y}\right)\approx \sum _{i=1}^p{k}_i{\left\{E\left[G_i\left(\mathbf{y}\right)\right]-E\left[G_i\left(\mathbf{v}\right)\right]\right\}}^2$$

(7)

where $k_i$ is a positive constant, $\mathbf{v}$ is a Gaussian random variable with zero mean and unit variance, $G_i(•)$ is a non-quadratic function, and G is chosen differently from the Gaussian distribution. As the RFID signal is sub-Gaussian, the following options are available:

$$\begin{array}{c}G\left(\mathbf{u}\right)=\frac{1}{a_1}logcosh\left(a_1\mathbf{u}\right)\hfill \\ G^{\prime }\left(\mathbf{u}\right)=tanh\left(a_1\mathbf{u}\right),{}^{}1\le a_1\le 2\hfill \end{array}$$

(8)

Then, maximize the Lagrange:

$$L(\mathbf{w},\lambda )=|E\left[G\left({\mathbf{w}}^{\mathbf{T}}R\right)\right]|-\frac{\lambda }{2}({\mathbf{w}}^{\mathbf{T}}\mathbf{w}-1)$$

(9)

The RFID system based on the FastICA algorithm is mainly composed of the following six modules: tag, RWD (sensor), modulation module, sampling module, whitening module, and the most important algorithm implementation module, as shown in Figure 16.

From Figure 17, it can be concluded that the separated signals of several Fast-ICA algorithms can find completely corresponding source signals locally, and the order and polarity of the signals separated by the algorithm are randomly changed, and the separation is accurate.

The use of BSS technology optimizes the hardware complexity of the RFID system and reduces the number of iterations required to query all tags. As a result, the equipment for RFID systems becomes simple and inexpensive.

4.2. BSS Algorithm for Under-Determined RFID Systems

4.2.1. Combination of Tag Grouping and BSS Algorithms

Although the ICA algorithm’s use in solving the anti-collision problem for RFID systems is becoming more sophisticated, it is still not an effective way to deal with the issue of throughput deterioration brought on by a lot of tags. Based on the grouping method traditionally used to solve collision problems, a different grouping method is used to keep the number of tags less than or equal to the number of RWD antennas at each separation, i.e., over-determined or positive, when the number of tags is greater than the number of RWD antennas (under-determined). A blind separation technique is then used to separate the signals from each batch of collisions.

The blind separation and dynamic bit-slot grouping (BSDBG) multi-tag anti-collision algorithm [84] is based on selecting an appropriate number of groups with a fixed number of RWD antennas and tags, using dynamic slot grouping to ensure that the number of tags is less than or equal to the number of RWD antennas at each separation, maintaining the non-underdetermined state, and then using the FastICA algorithm to separate the colliding signals in each group.

The tags are grouped by the algorithm using a bit-slot [85]. The fundamental principle of grouping is that after receiving a disk storage command from the RWD, the tag generates a 128-bit binary number with any randomly selected bit set to “1”, and all other bits set to “0”. The tag provides the RWD with this 128-bit binary number as an answer to a question. The tag can be grouped based on which bit of this 128-bit number is “1”, as shown in Figure 18.

With dynamic grouping, an increase in the number of tags does not lead to an increase in the probability of having more than M tags within a group, and when the number of antennas M = 8, more than 99.94% of the packets with less than M tags can be correctly separated by the ICA algorithm, which is far more efficient than the traditional algorithm.

Later, researcher Jie Yan [86] used time-slot grouping and dynamic time-slot grouping in combination with ICA algorithms to implement anti-collision in RFID systems, analyzed the variation in RFID system throughput with different numbers of RWD antennas and different numbers of tags, and concluded that the change in the size of different frames directly affects whether the mixed signal is positive or over-determined for each separation. The blind separation and framed-slot algorithm (BSFA) for UHF RFID systems proposed by Yuchao Mu [87] in his Master’s thesis is more stable and takes less time to identify than the BSDBG algorithm proposed by Li Hua et al. The paper also proposes the adaptive tree grouping and blind separation (ATGBS) anti-collision algorithm, which solves the drawback that not all tags within a group are less than or equal to the number of RWD antennas in the traditional algorithm and makes the execution of the grouping algorithm more efficient. Later, Limeng Pu [88] and others combined the ICA algorithm with automatic modulation classification techniques and direct sequence spread-spectrum technology, enabling RFID systems to use different modulation methods depending on the device or owner, while using the PCA algorithm in the blind source separation algorithm to estimate the number of tags, making the RFID system intelligent.

4.2.2. NMF Algorithm for RFID Systems

The signal is in an under-determined state when there are fewer observed signals than there are source signals. The non-negative matrix factorization (NMF) algorithm in the BSS is essentially a matrix decomposition under specific constraints [89]. It can be configured to achieve under-determined state source signal estimation by applying it to under-determined state RFID systems that can also achieve under-determined state tag collision signal separation [90].

The majority of the current approaches to the issue of under-determined blind separation rely on sparse component analysis, which necessitates the existence of sparse characteristics in the source signal. However, as RFID typically employs ASK or PSK modulation, the obtained tag signal must first undergo sparse transformation, which is a challenging operation to accomplish, in order to be totally sparse. Therefore, a non-negative matrix decomposition method is introduced to process the collision non-sparse tag signal, and the steps are as follows:

(1)

The RWD simultaneously receives signals from synchronized tags and establishes a collision model for MIMO: Input source signal $\mathbf{S}={[{\mathbf{s}}_1\left(t\right),{\mathbf{s}}_2\left(t\right),\dots ,{\mathbf{s}}_n\left(t\right)]}^T$, mixed received signal $\mathbf{X}={[{\mathbf{x}}_1\left(t\right),{\mathbf{x}}_2\left(t\right),\dots ,{\mathbf{x}}_m\left(t\right)]}^T$, where $m<n$ means that the received signal is smaller than the dimension of the source signal, that is, it deals with the under-determination problem.

(2)

$\mathbf{W}$ and $\mathbf{H}$ are initialized as arbitrary non-negative matrices, where ${\mathbf{W}}_{m\times n}$ is the estimation of the mixed matrix $\mathbf{A}$ and ${\mathbf{H}}_{n\times T}$ is the estimation of the source signal matrix $\mathbf{S}$.

(3)

The objective function iteration error is set to $\delta ={10}^{-6}$. At the same time, a determinant constraint is applied to $\mathbf{W}$, and a sparsity constraint and a minimum correlation constraint are applied to $\mathbf{W}$ at the same time, that is, ${\alpha }_{\Omega }=1,{\alpha }_f=\frac{1}{4}\times 1000,{\alpha }_C=0.01$ is taken.

(4)

Iterate according to the iteration rules, judge the error in the adjacent two iterations, if it is not greater than $\delta$, turn to step (5); Otherwise, repeat step (4).

(5)

The operation is stopped to obtain the final matrices $\mathbf{W}$ and $\mathbf{H}$, and the separated signal $\mathbf{W}$ is the source signal.

The algorithm flowchart is shown in Figure 19:

The RFID system based on the NMF algorithm has throughput performance that is N times better than the time-slot ALOHA technique and is suited for tag collision under uncertain circumstances. This technique significantly increases the received signal’s energy while addressing the tag collision issue. Its relatively straightforward implementation and low hardware overhead make it suitable for use in real-world scenarios.

While the constrained NMF algorithm can solve the problem of under-determined RFID collisions, it cannot accurately separate collision signals when the number of tags is much larger than the number of RWD tags. A collision avoidance method for RFID systems in under-determined states using a combination of a frame-slot grouping method and a constrained NMF algorithm was later proposed in [91]. By grouping the tags into a suitable number of groups and separating them using the constrained NMF algorithm, the advantages of the NMF algorithm are fully exploited, and no separation is possible. After continuous research, they combined the NMF algorithm with constraints and the dynamic tree grouping algorithm [92] to achieve the under-determined blind separation of RFID systems, resulting in a significant reduction in the number of queries to identify tags in RFID systems. Ref. [93] proposed the use of the Hamming regrouping algorithm combined with the constrained NMF algorithm to implement the under-determined state RFID system collision method. They used the weight of the Hamming code in the first M bits of the ID carried by the tag as the basis for grouping the tags and showed that the best separation was achieved when the number of tags was twice the number of RWD antennas when using the constrained NMF algorithm to separate under-stated signals. Recently, Ref. [94] proposed a new non-negative matrix decomposition (NMF) anti-collision algorithm with minimum correlation and minimum volume constraints, namely, the MCV_NMF algorithm, which combines the tag signal independence principle with the NMF mechanism to achieve improved performance and can well solve the under-determined collision problem and improve the throughput of RFID systems. This algorithm outperforms the TDMA-based algorithm, and it makes sense to perform more research in this area.

It can be seen from Figure 20 that the MCV_NMF algorithm has high accuracy. After algorithmic processing, the sequence of tag signals has changed. However, due to the modulation and coding methods adopted by the RFID system, and the purpose of the RFID system being only to identify the signals carried by the tags, the change in the order of the tag signals does not affect the correct identification of the tag signals.

5. ML-Based RFID Anti-Collision Algorithm

In the past decade, ML has emerged as a new technique that effectively solves problems that traditional anti-collision algorithms cannot overcome. Previous research [95] showed that when the frame size is equal to the number of tags, the maximum throughput will reach its maximum value, which is about 37%. In the usual case, the number of tags is unknown and must be estimated in order to set the appropriate frame size to achieve maximum throughput.

The current mainstream anti-collision algorithms mainly include the binary tree anti-collision algorithm and ALOHA anti-collision algorithm, and the system design complexity of the binary tree anti-collision algorithm is high, so it is rarely used in actual systems. The ALOHA algorithm is popular because of its simple logic and systematic nature. It is widely used because of its low complexity [96]. Among the ALOHA algorithms, the DFSA algorithm is currently the most widely used, and its core problem is to estimate the optimal frame length at the next moment according to the current channel state. Ref. [97] proposes a hierarchical Mopt frame length division scheme, which improves the overall system efficiency by 0.032; Ref. [98] proposes an adaptive frame length optimization scheme, where the system can adaptively adjust to the optimal frame length, in order to improve the system throughput rate. Ref. [99] proposes a frame length and packet number adjustment scheme, which can still ensure better recognition efficiency when the number of tags is large.

The core of the above algorithm is to improve system throughput by determining the frame length of the next frame. This article will introduce a DFSA algorithm based on deep neural network optimization [100], which uses a deep neural network LSTM (long short-term memory) network to predict the frame length of the next frame, so as to accurately select the optimal frame length, and improve the system throughput.

5.1. LSTM Deep Neural Network Model

LSTM is a recurrent neural network designed to solve the long-term dependence problem. It is realized by forgetting gates, input gates, and output gates [101]. Its structure is shown in Figure 21.

The forget gate ${\mathbf{f}}_t$ determines what information is lost from the cell state:

$${\mathbf{f}}_t=\sigma ({\mathbf{W}}_f\times [{\mathbf{h}}_{t-1},{\mathbf{x}}_t]+{\mathbf{b}}_f)$$

(10)

where $\sigma$ is the sigmoid function, ${\mathbf{W}}_f$ is the weight of the forget gate, and ${\mathbf{b}}_f$ is the bias of the forget gate. The gate will output a number between 0 and 1, which determines how much information ${\mathbf{C}}_{t-1}$ retains.

The input gate determines what information will be kept in the cell state:

$$\begin{array}{c}{\mathbf{i}}_t=\sigma ({\mathbf{W}}_i·[{\mathbf{h}}_{t-1},{\mathbf{x}}_t]+{\mathbf{b}}_i)\hfill \\ {\tilde{\mathbf{C}}}_t=tanh({\mathbf{W}}_c·[{\mathbf{h}}_{t-1},{\mathbf{x}}_t]+{\mathbf{b}}_c)\hfill \end{array}$$

(11)

where ${\mathbf{x}}_t$ is the input variable value, $\mathbf{W}$ and $\mathbf{b}$ are the input gate weight and bias, respectively, ${\mathbf{i}}_t$ determines which ones need to be updated, and ${\tilde{\mathbf{C}}}_t$ is the candidate value vector that needs to be updated.

The output gate determines the value of the final output:

$$\begin{array}{c}{\mathbf{o}}_t=\sigma ({\mathbf{W}}_o·[{\mathbf{h}}_{t-1},{\mathbf{x}}_t]+{\mathbf{b}}_o)\hfill \\ {\mathbf{h}}_t={\mathbf{o}}_t·tanh{\mathbf{C}}_t\hfill \end{array}$$

(12)

where ${\mathbf{h}}_t$ is the final output value, and ${\mathbf{W}}_o$ and ${\mathbf{b}}_o$ are the weights of the output gate and bias, respectively.

5.2. LSTM-Optimized DFSA Algorithm

From the previous analysis, it can be seen that the core of the DFSA algorithm is to dynamically adjust the frame length. When the frame length is equal to the number of tags, the throughput can be maximized, and the LSTM neural network has a better performance in time series prediction. If the LSTM neural network is used to predict the number of tags in the next frame in advance, the accurate adjustment of the frame length can be realized to improve the throughput of the system.

The system identification process is shown in Figure 22. When the RWD performs the first identification, because there is no reference it cannot predict the number of tags in the next frame, and the RWD randomly determines a smaller frame length for identification. Starting from the second frame, LSTM predicts the tag number of the next frame before each recognition so that the frame length can be adjusted reasonably. In order to reduce the time delay of tag recognition, the LSTM pre-model in this process is a pre-trained model.

In practical applications, real-time training models need to consume a lot of computing power and cause large delays, so the corresponding models need to be trained in advance for different application scenarios. The training process of this model is shown in Figure 23. In the figure, the input layer standardizes the prepared data to speed up the convergence of the model, and divides the data into training set and test set input network layers; the network layer consists of two layers of LSTM neural networks and a dense layer with sigmoid activation function. The purpose of the dense layer is to enhance the nonlinear mapping ability of the network [102]. The output layer compiles and trains the network, and finally completes the model output.

From the above analysis, it can be known that in the DFSA system, the system throughput is the largest when the number of tags in the next frame is equal to the frame length. Therefore, it is only necessary to input the frame length at the current moment into the trained model to predict the optimal frame length of the next frame. In order to ensure the accuracy of the predicted data, the statistical characteristics of the input Poisson random number must be consistent with the statistical characteristics of the Poisson sequence used for training in the training model.

6. Conclusions

In the context of the rapid development of the IoT industry and the widespread application of the technology, the problem of multiple tag collisions in RFID systems is addressed. Anti-collision algorithms can be used to avoid collisions when multiple tags are detected by the reader at the same time. This algorithm allows time-slicing of different tags, allowing them to reply or be acknowledged by readers at different intervals. By comparing the reader’s command with the tag’s identification code, the tags can be identified one by one, thereby avoiding conflicts.

This paper first introduces in detail two traditional collision avoidance algorithms based on TDMA: the random ALOHA algorithm and the deterministic tree-based algorithm. The two types of algorithms are classified in detail and the relevant principles and algorithm execution processes of each algorithm are described. The analysis shows that the ALOHA-based randomness algorithm cannot meet the high real-time requirements of the application, and the tag may not be identified or be incorrectly identified. Binary-tree-based deterministic algorithms leak more information and are less secure. Furthermore, as with ALOHA, when the number of tags is large, the time delay consumed to identify all the tags will be too long to meet the requirements of practical applications due to the repeated communication between the tags and the reader. On this basis, this paper also introduces two types of hybrid tag collision prevention algorithms that combine the above traditional algorithms, combining the advantages of the ALOHA and TREE algorithms to avoid “tag starvation”.

Then, this paper views the tag collision problem as a mixing problem of signals from the perspective of the signal processing layer, and the process of tag identification as a blind source separation problem of mixed signals. The FastICA-based tag anti-collision algorithm based on independent component analysis is described, as well as a multi-tag anti-collision algorithm combining tag grouping with a blind separation algorithm in the under-determined case, and a constrained NMF algorithm. It is concluded that these algorithms have a higher system throughput rate than the ALOHA algorithm and the binary tree algorithm, and can better solve the system multi-tag collision problem and meet the requirements of practical applications, avoiding the shortcomings of traditional algorithms.

Next, the paper presents ML-based algorithms for tag count and frame length estimation. Combining the LSTM deep neural network with the DFSA algorithm, the LSTM neural network can more accurately predict the frame length, thereby improving the performance of the DFSA system. The system regards the number of tags in the range of the reader at different times as a time series, and uses the superior performance of the LSTM neural network in time series prediction to better estimate the number of tags in the next frame, and realize the rapid and accurate adjustment of the frame length. The DFSA algorithm based on LSTM optimization can still maintain a good throughput rate when the number of tags is large. Compared with the traditional DFSA algorithm, the recognition efficiency is higher and the time slot waste is lower. As shown in

Table 7. Performance comparison of anti-collision algorithms for RFID tags.

Anti-Collision Algorithm	Throughput	Complexity	Hardware Resources
Traditional algorithm	Low	Low	Low-power microcontroller, small memory size
Hybrid algorithm	Medium	Medium	Medium-/high-power microcontroller, large memory capacity
Based on BSS	High	Medium	High-performance processor, large memory capacity
Based on ML	High	High	High-performance processor, large memory capacity

, the advantages and disadvantages of the proposed algorithm in terms of throughput, complexity, and hardware resources are compared. It can be seen that the throughput of the RFID tag anti-collision algorithm based on BSS and ML is relatively high, but the complexity of the algorithm based on ML is much higher than other algorithms. Therefore, when the number of tags is not large, it is most efficient to use the BSS-based anti-collision algorithm.

Finally, in order to improve the overall performance of RFID systems, this paper presents the future trends and challenges faced by tag anti-collision technology.

7. Future Prospect

RFID technology, as a fundamental network information collection technology, is developing rapidly with the growing development of the internet of things and the expansion of the market [103]. Data integrity, one of the key technologies inherent in RFID, will attract the attention of a large number of researchers. An important advantage of RFID technology is the simultaneous identification of multiple targets. If you want to achieve multiple targets for simultaneous identification, we must solve multiple tags corresponding to a reader or multiple readers when there is a signal interference problem, namely, collision problem [104]. Tag collision refers to when more than one tag corresponds to a reader, and the tags simultaneously sends data to the reader, the signals collide with each other, so that the reader cannot correctly obtain the relevant information. Although a number of different tag anti-collision algorithms have been proposed, anti-collision techniques are yet to emerge in a fast and stable form, so the following issues have not been well addressed:

(1)

Low system throughput

With the advent of the big data era, RFID tags have increased in large numbers. Combined with practical considerations, reader receiving antennas are unlikely to increase with the number of tags, so the number of tags will be much greater than the number of receiving antennas. For the various algorithms previously studied, the throughput drops dramatically when the number of tags increases and this is no longer a good solution to such problems. So, how to resolve collisions between large numbers of tag signals is a problem that should be studied in depth in the future [105,106,107]. Research into this factor is also an important direction for throughput improvement in recognition systems, where the limitations of the reader’s recognition distance and factors such as noise and dynamic tag mobility can result in inaccurate recognition of all tags.

(2)

Excessive time delay and low channel utilization

The prevailing access technology for RFID collision avoidance, time division multiple access (TDMA), is now a technology that uses time-domain division to achieve multiple access. Usually, the reader is divided into multiple small slots, called slots, with each tag in a different slot responding to the reader’s read and write commands, thus completing multi-access. However, for the existing tag recognition system using the ALOHA algorithm, the TREE algorithm, or a combination of the two algorithms, the problem of high latency still exists [108,109,110], so choosing the appropriate transmission protocol and algorithm for optimization can reduce the delay in the RFID communication process, and thus, improve the channel utilization.

(3)

Co-channel interference

RFID is an information collection and processing technology that offers the advantages of speed, and accurate and instant communication. As the technology continues to evolve, the issue of RFID privacy and security is becoming more serious. Any transponder can be scanned by a reader at the same frequency. This vulnerability increases the false code rate, slows the recognition speed, and reduces the effective recognition distance of the RFID system. Therefore, it is also an unsolved challenge to eliminate this co-channel interference, so that a tag is not read by multiple readers of the same frequency at the same time [111,112,113].