An improved RFID anti-collision algorithm

Abstract

In the communication of RFID system, it is easy to cause collision during data exchange between the tag and the reader, thus tags may not be identified. On the basis of researching binary algorithm, bit positions of collision are locked through setting different statuses of the order during collision, and then samples of the locked positions are recorded to select the remaining collision positions during the paging process to the descending order. Compared with traditional binary collision algorithm, significant improvements have been made in analyzing the algorithm’s indexes like searching times, amount of communication and throughput, improving efficiency of the system.

Keywords

RFID anti-collision lock position sample

1. Introduction

RFID (Radio Frequency Identification), a data acquisition technology that is automatically available without contact, relies on electromagnetic waves as a transmission medium for bidirectional communication and automatic identification purposes [1], and is widely used in medical, smart card, attendance system and project tracking attributable to its advantages such as strong automatic identification, fast response, low hardware cost and long service life.

RFID is mainly composed of readers, tags and processing systems, and works depending on the bidirectional communication between wireless network and tag after the ID with unique identification enters the electromagnetic field of the reader, which enables data collection of tags, data processing and resource sharing. However, one obvious disadvantage is that multiple tags entering the scope of the reader at the same time will cause communication collisions with the reader, which will lead to the failure of tag recognition. At present, the common tag anti-collision algorithms are time-division multipath based non-deterministic algorithm and deterministic algorithm [2]. The former is mainly represented by ALOHA algorithm [3], which is simple and easy to implement, can meet basic requirements and occasions, and read-only tags [4]. The latter is mainly represented by binary search algorithm [5], which requires multiple searches, has a large amount of identifying data and a low throughput. Scholars at home and abroad have put forward different solutions to this problem. An improved RFID tag anti-collision algorithm was proposed, and a new RFID technology module was established to improve the identification efficiency of the RFID system [6]. An optimized anti-collision algorithm was presented, which uses two-digit arbitration collision for bit-by-bit recognition by constructing a new request-building method, greatly reducing the number of corresponding tags in collision detection, thus reducing the bit collision probability [7]. The uniqueness of tag sequence number and the feature of Manchester encoding to identify tag collision locations are presented, and binary optimal encoding is used to optimize and shorten the length of sending characters [8].

In this paper, on the basis of researching binary algorithm [9], bit positions of collision are locked through setting different statuses of the order during collision, and then samples of the locked positions are recorded to select the remaining collision positions during the paging process in descending order [10]. Finally, good results have been achieved. Compared with traditional binary collision algorithm, significant improvements have been made in analyzing the algorithm’s indexes like searching times, amount of communication and throughput, improving efficiency of the system.

2. Basic binary anti-collision search algorithm

2.1 Algorithm process

In the binary search anti-collision algorithm, the bit conflict detection protocol is mainly used as the anti-collision scheme, in which the reader is required to accurately obtain the bit location of the collision. Therefore, Manchester codes are generally used to identify collision locations in bits when multiple tags respond simultaneously, and to search for tags again according to certain rules based on the collision locations. Basically, in the binary search algorithm, the reader sends a certain length of serial number to compare with each tag’s ID. If there are tags less than or equal to the serial number, the reader sends its ID to the reader, otherwise the response is not triggered. Assuming the tag ID number is $N$ in length and $[N,N-1,N-2,\ldots 1]$ in bits, there are three steps:

Step 1:
Initialization. First the reader sends the command with the sequence number of all 1, then all the tags send their IDs to the reader so that it can detect the ID number and find the conflicting bit location (assuming it is in the $X$ bit), according to which the reader gets a list of sequence number parameters for the next command requested. In this case, the first ( $N-X$ ) bits of the sequence number is the same as the first ( $N-X$ ) of the corresponding ID number, the $X$ -th position is 0, and all the remaining ( $X-1$ ) are 1.
Step 2:
Each tag compares its ID number with the reader’s new serial number in step 1, and the tag is sent back to the reader if less than or equal to the serial number, otherwise nothing is done.
Step 3:
Step 2 is repeated until the process where only one tag responds ends, the tag is identified, then it is de-selected, and step 1 is executed until all tags are identified.

2.2 Algorithmic efficiency analysis

The length of command request sent in the reader is mainly the length of its own code, the length of the relevant parameters and the length of the data of the tag response command. Therefore, the number of times the binary algorithm receives feedback command is as follows. The number of times the basic binary search algorithm searches the first tag to issue command is as follows:

$\displaystyle L(Q)=lb(Q)+1$ (1)

In the equation above, $Q$ means the number of tags, $L(Q)$ means the searched times, $lb(Q)$ means the log base two.

After the first tag is deselected, it is searched again from the beginning. At this time, the tag waiting for recognition is $Q-1$ , and the tag waiting for recognition in turn is $Q-i-1$ , so the number of commands for the $i$ -th tag is:

$\displaystyle L(Q-i-1)=lb(Q-i-1)+1$ (2)

So the number of times needed to search for all the tags is:

$\displaystyle T=\sum\limits_{i=1}^{Q}{(lb(i)+1)}$ (3)

Therefore, it is found that the efficiency of binary collision algorithm is mainly the response times of electronic tags. The longer the response times, the more times to complete all tags, which will reduce the efficiency of the algorithm and occupy more communication time.

3. Improved RFID anti-collision algorithm

3.1 Raise of problem

Assuming that all the tags in the reader’s working area are responding to replies, if there is a conflict of tags at $k$ locations, then the $k$ bit positions in the binary cannot be identified. During the conversation between the reader and the tag, the content of the conversation is carried out in the whole sequence, so that some information will be excessive. Therefore, the improvement of the binary algorithm mainly starts from reducing the redundant bits of information in the sequence to anti-collision processing in other places to improve its efficiency.

3.2 Related instructions of improved binary algorithm

The specific meanings of each instruction are as follows:

ID represents the sequence number obtained after the reader sends the first instruction sequence. After the reader judges the exact bit position of data collision, the information of multiple collision positions is extracted and set to 1 at one time, and the other non collision positions are set to 0, forming a new sequence number. In response, the tag compares the data bits in its ID with the serial number issued in the reader, and locks the bit positions in the corresponding tag set to 1 back to the reader.

SELECT(ID): The reader sends the serial number as a parameter to the electronic tag. A tag with the same serial number executes an answer command, while a tag with another serial number only responds to the REQUEST command.

READ: Selected tags send data to the reader.

UNSELECT: The tag is set to be silent and does not respond to the received REQUEST command.

3.3 Steps for the improved binary algorithm

Step 1:
Initialize settings for reader commands and related parameters.
Step 2:
The reader sends a REQUEST ( $X$ ) command, and the tag compares its ID code value with the result sent by the reader. If it is less than or equal to the result, the tag sends its ID, otherwise it does not respond.
Step 3:
The reader keeps searching for signals sent by surrounding tags. If the tag does not respond, go to step 2 and the reader keeps sending commands; Otherwise, go to step 4.
Step 4:
The reader decodes the response signal of the reply tag and compares the decoding results to determine whether a collision has occurred. If no collision occurs, send SELECT and READ commands for read and write operations, and then issue UNSELECT commands to make the tag secure. Otherwise, a collision occurs, and the location of the collision will be recorded using a set of samples.

Figure 1(a).
Algorithm implementation process.

Step 5:
How to find the specific collision location as soon as possible after the collision in step 4 is the key to improve the algorithm in this paper. Set the tags for the response to be in three states: wait, sleep, and exposure, and set a status counter. The value of the status counter equal to 0 indicates that the tag is in a waiting state, greater than 0 indicates that it is sleep, and the exposure state indicates that the reader has recognized the tag and no longer responds to the signal from the reader. When the reader detects the collision, it first detects the collision position. Assuming that the collision is at the $X$ -th bit position, the next order sequence is ( $N-X$ ). After receiving the REQUEST (ID, $X$ ) command from the reader, the tag compares it to its ID, sets the $X$ -bit where the collision occurs to a locked state, checks the tag with the highest bit of 1 in the locked bit, and responds to the command, then the tag is in a state of waiting, or sleeps. The reader sends instructions of SELECT and READ, and UNSELECT after reading and writing the tag, then the tag is set to be exposed. The above executions are set to the Sample set, where the result on the $X$ -bit is recorded as $(S_{x},i)$ , where $i$ is the recorded position of the sequence, and the collision position is recorded in turn to form the set $\{(S_{x},i)(S_{y},j)\ldots(S_{n},m)\}$ . Then, the index in the sequence corresponding to the collision position in the sample is selected for identification in descending order, and the execution is repeated until all tags in collision in in the sequence of 0 and 1 in the locked collision bit are identified. Finally, go to step 6.
Step 6:
Identify all tag locations and finish processing.

The description of the entire algorithm flow is shown in Fig. 1(a), in order to explaining the model clearly, you can take a look Fig. 1(b) which described by N-S chart. The further examples illustrated in Fig. 2.

Figure 1(b).
Algorithm implementation process described by N-S chart.

Figure 2.
Illustrated examples of the implementation process.

Figure 3.
Relationship between searching times and collision.

Here are the main steps about the examples:

(1)
First, send the request code ‘11111111’ to the 4tags (10110011, 10100011, 10111010, 11101011).
(2)
Second, according to the decoding is ‘1x1x001x’, so send out the request code ‘01010101,0’. The result is (001, 010,011,101), (10,01,11,00).
(3)
Then, set the decoding ‘0xx’, and send out request code ‘00’, we can get the target tag2.
(4)
So, the communicating can be done between the reader and the tag.
(5)
When finished, deselecting the tag, and reading for the next step.

4. Algorithm analysis

The performance of RFID anti-collision algorithm is mainly measured from the search times, communication and throughput, by comparison with representative algorithms, BS (Binary search) algorithm and DBS (Dynamic Binary Search) algorithm of binary collision algorithm.

4.1 Search times

Set the number of E-tag xxx as N, when the collision occurs at the $X$ -th bit, $S$ is the number of times the reader searches. The number of searching of BS algorithm is as shown in Eq. (4), that of DBS algorithm is as shown in Eq. (5), and that of the algorithm in this paper is as shown in Eq. (6). The comparison results are shown in Fig. 3.

$\displaystyle S1=\log_{2}N+1$ (4) $\displaystyle S2=N+1$ (5) $\displaystyle S3=2^{N}+1$ (6)

Table 1

Communication bit amount of three algorithm readers

Amount of tags	BS algorithm	DBS algorithm	Algorithm in this paper
2	4278	3187	2105
4	5000	3500	3000
8	6000	4125	3381
16	7500	7000	5245

Figure 4.

Relationship between data transmission and communication bit amount and collision times.

Figure 3 shows that compared with BS and DBS algorithm, the algorithm in this paper has a significant reduction in search times, and the more collision positions are, the more obvious the effect is. When the collision occurs at 14 bits, the effect is obvious.

4.2 Amount of data transmission and communication

To further illustrate the superiority of this algorithm, only the number of communication data bits of the reader is studied in this paper, mainly because the number of communication data bits sent by the reader is equal to the length of communication data returned by the tag. The tag serial number length is set to $M$ . The data communication data length for searching $N$ tags by BS algorithm is shown in Eq. (6), and that by DBS algorithm is shown in Eq. (7). The search by this algorithm is divided into two main parts, one is to lock the binary code of “0” and “1”, the second is to code the binary code for collision bit, so the data communication length is shown in Eq. (8). The number of tags is set to (2, 16), and the comparison results are shown in Fig. 4 and Table 1.

$\displaystyle L1=M\times(\log_{2}N+1)$ (7) $\displaystyle L2=M\times(N+1)$ (8) $\displaystyle L3=(M1+M2)\times(2^{N}+1)$ (9)

In Eq. (9), M1&M2 mean the minimum and the maximum length in the tags.

Figure 4 and Table 1 shows that the communication data consumed by BS and DBS algorithm is larger with more tags, but the consumption of this algorithm is relatively small and stable, which shows that this algorithm is stable.

4.3 Throughout

Throughput is related to the data efficiency in the process of data identification and transmission. If $N$ search tags are set, the system throughput of BS algorithm to complete the search is shown in Eq. (10), that of DBS algorithm is shown in Eq. (11), and that of the algorithm in this paper is shown in Eq. (12), and the comparison results are shown in Fig. 5.

$\displaystyle\lambda 1=\frac{N}{\log_{2}N+1}$ (10) $\displaystyle\lambda 2=\frac{N}{N+1}$ (11) $\displaystyle\lambda 3=\frac{N}{2^{N}+1}$ (12)

Figure 5.

Comparison of relationship between throughput and collision times for different algorithms.

Figure 5 shows that the throughput of this algorithm is wavy, and most of it is always better than that of BS algorithm and DBS algorithm, especially when the number of tags is increasing, the superiority of this algorithm is more obvious.

5. Conclusion

In this paper, firstly, the characteristics of binary search anti-collision algorithm are analyzed. On this basis, the collision bits are locked by setting different statuses in the process of collision, and the locked positions are recorded as samples. Then, in the process of paging, the remaining collision bits in the sample set are selected in descending order, and good results are achieved. The algorithm analysis shows that this algorithm has obvious improvement compared with the traditional binary collision algorithm and improves the efficiency of the system.

Footnotes

Acknowledgments

The work was financially supported by Science and Technology Research Project of Chongqing Municipal Commission of Education (KJQN201803105).

References

Finkenzeller

, RFID-Handbook Fundamentals and Applications in Contactless Smart Cards and Identification, New Jersey, John Wiley & Sons Ltd, 2003.

Nath

Chakravarty

A.K.

Ghosh

and Sarkar

S.K.

, FPGA placement optimization using firefly algorithm, Advances in Industrial Engineering and Management 6(2) (2017), 97–102.

Peng

Q.S.

Zhang

and Wu

W.M.

, Variant enhanced dynamic framed slotted ALOHA algorithm for fast object identification in RFID system, Anti-counterfeiting, Security, Identification, 2007 IEEE International Workshop on, 2007, pp. 88–91.

Ryu

Lee

Seok

Kwon

and Choi

, Ahybrid query tree protocol for tag collision arbitration in RFID systems, Proceedings of IEEE International Conference on Communications Glasgow, Scotland: IEEE, 2007, pp. 5981–5986.

Kim

Y.H.

and Kim

S.S.

, Improved 4-ary query tree algorithm for anti-collision in RFID system, International Conference on Advanced Information Networking and Applications, Bradford, United Kingdom, 2008, pp. 699–704.

Shi

W.D.

, An improved RFID tag anti-collision algorithm, Bulletin of Science and Technology 31(4) (2015), 121–123.

Shi

J.Y.

Zhou

and Ge

H.Y.

, An optimized binary search algorithm for RFID tag collision, Journal of Inner Mongolia Normal University (Natural Science Chinese Edition) 44(2) (2015), 249–253.

Cao

and Ma

, A binary search RFID anti-collision algorithm for optimized coding, Computer Applications and Software 32(6) (2015), 283–286.

Wang

Qian

Z.H.

Z.C.

, RFID anti-collision algorithm based on binary tree, Journal of Communications 31(6) (2010), 49–57.

10.

Kouider

and Polat

, Optimal position of piezoelectric actuators for active vibration reduction of beams, Applied Mathematics and Nonlinear Sciences 5(1) (2020), 385–392.