An RFID anti-collision Q-value algorithm research

Abstract

RFID technology is an important technology of the Internet of Things. The key to realizing large-scale applications is to improve the efficiency of the system. For this reason, a novel RFID anti-collision Q-value algorithm is proposed, which changes the Q-rounding of the original Q-value algorithm to 2Q rounding, so that the adjusted frame length is closer to the theoretical optimal value, thereby the convergence is effectively reduced. Slot utilization of time is improved. By comparison, the actual throughput of the improved algorithm remains at a high level (average is 0.311 3), the total number of time slots is reduced by 26.7% when it is compared with the original Q-value algorithm.

Keywords

Internet of things Radio Frequency Identification(RFID)anti-collision algorithm EPC-C1G2 Q-algorithm

1 Introduction

RFID (Radio Frequency Identification) system communicates wirelessly by electromagnetic coupling in the space. The anti-collision algorithm determines its performance and its application. Radio frequency identification (RFID) technology is that radio frequency signals are used to achieve contactless information transmission and automatically identifies target objects through transmitted information [1]. In an RFID system, the same bandwidth is used in all tags. When multiple tags transmit data to the reader at the same time, they easily interfere with each other, it results in information conflict. This is the “multi-tag collision problem”. The tag collision problem has severely restricted the large-scale application of RFID technology, it has thus become one of the hot spots in this field [2].

Common anti-collision algorithms include deterministic binary tree algorithm and random competition ALOHA algorithm. Among them, ALOHA algorithm is widely used to solve collision problems due to its simple implementation [3]. Dealing with a large number of tags is not the advantage of ALOHA-based protocols because of the limitation of the frame size. The ALOHA algorithm mainly includes pure ALOHA, slot ALOHA, Framed Slotted ALOHA (FSA), and Dynamic Framed Slotted ALOHA (DFSA). The FSA algorithm is less efficient, so the researchers proposed the DFSA algorithm [4], it estimates the number of tags to be read next by observing the number of collisions and idle tags in the current frame, thus determining the size of the next frame. After a relative match is achieved between the frame length and the number of unread tags, the system efficiency is greatly improved.

EPCglobal uses the Q algorithm (Q-Algorithm) to further increase system efficiency. The reader adjusts the Q value so that the system operates at a dynamically changing frame length. In the Q-Algorithm algorithm, only Q is rounded, when the Q value is large, it results in a large change in the frame length before and after adjusting the Q value, a drop is caused in efficiency, which is manifested by the steep drop in throughput and the increase in the total number of used slots.

The previous improvements to the Q-value algorithm were mainly concentrated in the following sections:

Improvement of step size c: Wang Jin uses the differentiated c value to adaptively modify the Q value, the frame length is adjusted [5]. Ren Shougang divides the single adjustment parameter c into two weight parameters c1 and c2, the number of collision time slots and idle time slots are regulated [6]. He also proposes comparison of the difference operation with a preset threshold value, thus the Q value is dynamically adjusted [7]. Sun Wensheng uses two different C values to dynamically adjust the Q value, and the slot mechanism is used to make partial adjustments to the time slot in the event of a collision [8].

Changes to adjust Q timing: At the middle time slot and end, Hu Zhihong predicts the number of tags and compares them with the best frame length. If they are different, the instruction adjusts the value of Q, the frame length is adjusted to the optimal value [9].

A frame length pre-identification mechanism is introduced: Guan Zhenyang introduced a continuous collision detection mechanism, the best Q value is adjusted at the beginning of the recognition frame [10]. However, the above algorithm does not specifically improve the frame length in the unadaptation problem when Q changes.

2 Materials and methods

2.1 Q-value collision avoidance algorithm

2.1.1 Theoretical optimal frame length

The efficiency of the ALOHA system depends on the relationship between the number of timeslots and the number of labels. When the number of labels is much smaller than the number of timeslots, there are many idle time slots, the system efficiency is low. On the contrary, when the number of labels is much larger than the number of timeslots, the time-slot collision is serious, it also leads to a decrease in system efficiency [11].

When the number of slots per frame is approximately equal to the number of unread tags, the throughput of the system is maximized.

The number of tags is supposed to be identified is n. If the tags randomly select [0,n-1] range, the random number is loaded into the slot counter, the process of selecting random numbers for all tags is independent of each other, then the tags obey binomial distribution. Under the above conditions, the probability of r labels in the i-th time slot is formula (1): $P (m = r) = C_{n}^{r} {(\frac{1}{L})}^{r} {(1 - \frac{1}{L})}^{n - r}$ (1)

The probability of success for any time slot is formula (2): $P (m = 1) = C_{n}^{1} {(\frac{1}{L})}^{1} {(1 - \frac{1}{L})}^{n - 1} = \frac{n}{L} {(1 - \frac{1}{L})}^{n - 1}$ (2)

The number of time slots occupied by r tags is subject to: ${LC}_{n}^{r} {(\frac{1}{L})}^{r} {(1 - \frac{1}{L})}^{n - r}$

S can successfully identify the number of tags, it is formula (3): $S = {LC}_{n}^{1} {(\frac{1}{L})}^{1} {(1 - \frac{1}{L})}^{n - 1} = n {(1 - \frac{1}{L})}^{n - 1}$ (3)

System recognition rate is formula (4): $η = \frac{S}{L} = \frac{n}{L} {(1 - \frac{1}{L})}^{n - 1}$ (4)

In Equation (4), derivate L and make it equal to 0, L = n is obtained.

When the number of slots in a frame is approximately equal to the number of tags to be read, the successful timeslot in one frame reaches the maximum value, the reader identifies the largest number of tags, and the system throughput rate is the largest.

2.1.2 Q-value algorithm flow

In the ALOHA system, the most important thing is to accurately predict and adjust the frame length, so that it is as close as possible to the theoretical optimum frame length. Realizing the dynamic change of the frame length requires estimating the number of unread tags [12, 13]. Based on the number of successful slots, idle slots and collision slots which are generated in the identification process, a certain mathematical model is used for estimation. The researchers proposed the Schoute algorithm [4], it has a much higher efficiency than the frame slot ALOHA. However, there are still some problems.

In order to further improve the system efficiency and achieve higher recognition speed, the EPC-C1G2 standard [14] specifies anti-collision algorithm (Q-Algorithm) based on Q-value, it belongs to the ALOHA probabilistic algorithm. The feature of this algorithm is that the frame length is 2^Q, the frame length is adjusted by adjusting the Q value. The EPC-C1G2 standard specifies Q-Algorithm operation instructions. There are three key instructions, Query, QueryAdjust and QueryRep in each algorithm cycle. The flow chart is shown in Fig. 1.

Fig.1

Anti-collision algorithm flow chart based on EPC-C1G2.

The identification process is briefly described as follows:

The reader sends a Query command containing the parameter Q to the tag. The tag generates a random number in the range [0, 2^Q - 1], it is stored in its slot counter. The tag with a slot counter of 0 immediately reflects the random number RN16 to the reader. If there is only one tag reply, the reader can successfully complete tag identification; if there is no tag reply, that is, the slot is an idle slot, then Q_fp= max(0, Q_fp - C), where Q_fp is the floating point of parameter Q, that C is the adjustment step of Q, C is the variable step size of Q_fp. In general, Q is inversely proportional to C, so C = 0.8/Q can be taken [15]; if there are multiple tag responses, the time slot is a collision time slot, then Q_fp= min(15, Q_fp + C).

Next, the reader sends a QueryRep command, the value of the tag slot counteris decremented in the arbitration state. After the end of a frame, it is judged whether the Q value is changed. If it is changed, the reader sends a QueryAdjust command to modify the Q value; if the Q value does not change, the Query command is sent to enter a new inventory cycle.

2.2 MQ-algorithm algorithm

For the Q-Algorithm algorithm, only Q is rounded up, when the Q value is large, it results in a large change in the frame length before and after the Q value is adjusted. This results in a decrease in efficiency. This paper improves the Q-Algorithm algorithm and proposes an MQ-.Algorithm algorithm, FLASH memory is used to achieve better recognition efficiency without significantly increasing the amount of computation.

The MQ-Algorithm algorithm changes the rounding of the Q in the original Q-value algorithm to the rounding of 2^Q, the optimal adjustment threshold of 2^Q is determined through simulation.

2.2.1 Theoretical analysis of efficiency decline

The original efficiency value is formula (5): $η_{1} = \frac{n}{2^{Q}}$ (5)

After the number of unread tags adds a, frame length changes, the efficiency of this time becomes the value of Equation (6): $η_{2} = \frac{n + a}{2^{Q + 1}}$ (6)

The ratio of current efficiency to original efficiency is formula (7): $\frac{η_{2}}{η_{1}} = \frac{\frac{n + a}{2^{Q + 1}}}{\frac{n}{2^{Q}}} = \frac{n + a}{2 n}$ (7)

To find the limit of Equation (8), we get the formula (8): $lim_{n \to \infty} \frac{η_{2}}{η_{1}} = lim_{n \to \infty} \frac{n + a}{2 n} = \frac{1}{2}$ (8)

When the number of unread tags is large, efficiency will decrease by half when the frame length changes.

2.2.2 Changes in frame length adjustment

After a simulation observation, it was learned that the efficiency of the basic Q-value algorithm would suddenly drop in some places during the identification process. The simulation process is observed, the following reasons are found outfor changes in the value of each function: When the number of tags is large, each frame of Q changes by several hundred or even several thousand, it is far from the optimal frame length. When Q is changed, an excessively large change in the Q value results in a large gap between the frame length and the optimal frame length, efficiency is decreased.

In order to solve the above problems, the original Q-value algorithm is used to round Q to 2^Q. When the 2^Q change reaches a certain level, the frame length is adjusted. The extent of this change is called the “threshold.”

2.2.3 Threshold determination

This algorithm takes c = 0.2 and selects the threshold value that changes based on the original frame length (2^Q). That is formula (9). $μ = {\begin{matrix} 2^{Q} \times λ_{up}, Q_{fp} > Q \\ 2^{Q} \times λ_{downp}, Q_{fp} ⩽ Q \end{matrix}$ (9)

Where μ represents the threshold, 2^Q represents the current frame length, λ_up represents the increase factor, and λ_down represents the decrease factor. The coefficients λ_up and λ_down are related to the number of unread tags. Based on the number of conflicting tags in the recognition period, the number of unread tags is determined by the Schoute algorithm [4]. Schoute algorithm assumes that the number of collision tags conforms to the Poisson distribution, which is an average of 2.39 tags per time slot.: n = 2.39c_k + c₁, (number of collision slots c_k and number of successful slots c₁).

In Matlab, the MQ-Algorithm algorithm is used to simulate different λ_up and λ_down combinations of values for the same unread tag segment, the average system throughput rate s is obtained under the corresponding coefficient, which is Equation (10). $s = \frac{n_{suc}}{n_{total}}$ (10)

In the formula, s represents the average system actual throughput rate of the MQ-Algorithm algorithm under a specific combination of coefficients, n_suc represents the number of successfully identified time slots, and n_total represents the total number of cycles which is used in the identification.

For example, when the number of tags is 101 to 120, the simulation is shown in Fig. 2.

Fig.2

When n = 101 to 120, the relationship between the coefficient value and the actual throughput rate.

It can be seen from Fig. 2 that when λ_up= 1.95 and λ_down= 0.52, the average actual throughput rate of unread tags from 101 to 120 reaches the peak, that is, the efficiency of the system is maximum. Therefore, when the number of unread tags is in the range of 101 to 120, the optimal coefficient combination is λ_up= 1.95 and λ_down= 0.52.

By the same way in Fig. 3, when the number of unread tags is in the range of 201 to 220, the optimal coefficient combination is λ_up= 1.42 and λ_down= 0.43.

Fig.3

When n = 201 to 220, the relationship between the coefficient value and the actual throughput rate.

Through Matlab simulation, we can get the values of λ_up and λ_down in the range of different unread tags, as listed in Table 1. Each row in Table 1 corresponds to the coordinates of the peak point of a simulation graph.

Table 1

Combination of coefficients for different unread tags

Unread tags	λ _up	λ _down	Unread tags	λ _up	λ _down
1∼20	1.17	0.42	201∼220	1.42	0.43
21∼40	1.16	0.58	221∼240	1.48	0.43
41∼60	1.02	0.66	241∼260	1.54	0.42
61∼80	1.45	0.61	261∼280	1.61	0.42
81∼100	1.72	0.58	281∼300	1.66	0.42
101∼120	1.95	0.52	301∼320	1.72	0.41
121∼140	1.14	0.53	321∼340	1.75	0.39
141∼160	1.22	0.51	341∼360	1.82	0.40
161∼180	1.29	0.49	361∼380	1.87	0.40
181∼200	1.36	0.47	381∼400	1.95	0.41

2.3 Algorithm description and flowchart

2.3.1 MQ-Algorithm algorithm flow

The reader sends a Query command containing the parameter Q to the tag, a new recognition cycle starts. After receiving the command, the tag generates a random number in the range [0, 2^Q - 1], it is stored in its slot counter.

When the time slot counter is 0, the tag immediately reflects the random number RN16 to the reader, it turns to the answer state, the other tags enter the arbitration state. Three conditions may occur at this time:

Only one tag responds: At this point, the reader can receive a valid RN16, then it returns an ACK command with the RN16 parameter. If the tag receives a valid ACK command, it reflects its EPC to the reader, and it is converted to an acknowledgement state, the tag identification is completed.

There is no tag response: If the time slot is an idle time slot, then Q_fp= max(0, Q_fp - C), where Q_fp is the floating-point representation of parameter Q, and C is the adjustment step of Q.

Multiple tag responses: If the time slot is a collision time slot, then Q_fp= min(15, Q_fp + C).

The reader sends a QueryRep command, and in the arbitration state, the counter value of the tag slot is decremented by one, and step (2) is performed.

After the end of a frame, if it is judged that the difference between 2^Q and 2^Qfp is less than the threshold value, the Q value remains unchanged, and the Query command is sent to enter a new inventory cycle, and step (1) is performed; if If not, the reader sends the QueryAdjust command, the Q value is to modified.

The threshold value is changed according to the number of unread tags. The combination of the coefficients are shown in Table 1, it is stored in the reader with FLASH memory. Before the judgment, the corresponding coefficient is first searched according to the current unread tag number, the threshold value is calculated.

2.3.2 Flowchart

MQ-Algorithm algorithm flow chart is shown in Fig. 4.

Fig.4

MQ-Algorithm algorithm flow chart.

In the flow chart, the dotted box section is explained as follows: after the end of a frame, it is determined whether $| 2^{Q} - 2_{fp}^{Q} | < μ$ ? If $| 2^{Q} - 2_{fp}^{Q} | < μ$ , Q value is unchanged; If $| 2^{Q} - 2_{fp}^{Q} | ⩾ μ$ , $Q = {lb (2}_{fp}^{Q} + ζ)$ or $Q = {lb (2}_{fp}^{Q} - ζ)$ , ζ takes a random number in the range [1, $2_{fp}^{Q} - 1 - 1$ . Send a Query command to enter a new inventory cycle.

3 Simulation experiment

Time slot Aloha algorithm: In 1972, Roberts invented a channel allocation strategy that doubled channel utilization, the time slot Aloha protocol [16]. The principle is to use the clock to unify the user’s data transmission. It divides the time into discrete time slices. The user must wait until the next time slice to start sending data, thus avoiding the arbitrariness of the user to send data, reducing the possibility of data conflict and improving the channel utilization. When the cable TV cable was used to access the Internet, the technology was invented, and Aloha, which was abandoned for many years, was re-emphasized [17, 18].

Anti-collision technology is one of the key technologies of radio frequency identification. An improved Q-based algorithm is proposed for multi-tag collision problems [19]. The algorithm is based on EPCglobal Class-1 Generation-2 (EPC C1G2) standard and adjusts Q value. The mechanism has been improved. The reader does not need to adjust the Q value after the end of one frame, which improves the time slot utilization. The EPC standard does not specify the value of the adjustment step C, and the concept of threshold is introduced in the improved algorithm [20].

In order to evaluate the performance of the new algorithm, this paper writes a program in the MATLAB7.0 environment, the implementation of the algorithm is simulated. The metrics that measure the performance of an algorithm are the total number of tags that are needed to identify the same number of tags, as well as the actual system efficiency. In the MQ-Algorithm algorithm and the original Q algorithm, the comparison results of frame time slots with frame lengths of 128 and 256 bits and the related Q value improvement algorithm are shown in Fig. 5 (The total number comparison chart of Identified and used slots) and Fig. 6 (Algorithm system efficiency comparison chart) [21].

Fig.5

The total number comparison chart of Identified and used slots.

Fig.6

Algorithm system efficiency comparison chart.

As can be seen from Fig. 5, in the Q-Algorithm algorithm, MQ-Algorithm solves the problem of efficiency degradation which is caused by the Q change, and the number of identification tags has significantly reduced when it is compared to other algorithms (27.9% less than Q-Algorithm, a 10.4% reduction over the associated Q-value improvement algorithm).

It can be seen from Fig. 6 that the actual throughput rate of MQ-Algorithm has been greatly improved when it is compared with other algorithms, it is 33.6% higher than Q-Algorithm, it is 16% higher than the related Q-value improved algorithm. As the number of unread tags increases, he actual throughput rate of MQ-Algorithm gradually increases.

In each simulation experiment, the number of given tags ranges from 1 to 400. All the simulation obtained results were averaged after 500 iterations.

The actual throughput rate in this paper refers to the ratio of the number of identified tags to the total number of slots.

4 Conclusion

In this paper, an improved Q-Algorithm (Modified Q-Algorithm, MQ-Algorithm) is proposed. This algorithm changes the Q-rounding of the original Q-value algorithm to the rounding of 2^Q. The adjustment criterion is based on dynamic threshold of the current frame length. Matlab’s Monte Carlo simulation [22] shows that this algorithm solves the problem of unadaptable frame length when Q changes, the actual throughput of the system is increased, the number of total used slots is reduces.

The new Q-value algorithm (MQ-Algorithm) changes Q rounding in the original Q-value algorithm to rounding to 2^Q, the adjusted frame length is closer to the theoretical optimal value, thereby the convergence time is effectively reduced, and the time of gap utilization is increased. The total number of time slots, which is required to identify a specified number of tags by the MQ-Algorithm algorithm,is compared with the original algorithm, it is reduced by 27.9%, and the actual throughput rate is 33.6% higher than the original algorithm. If this algorithm is put into practical application, it can identify tags more quickly, it has a broad application prospect in many fields.

Footnotes

Acknowledgments

This work was sponsored by the National Natural Science Foundation project (51304076) of China; it is supported by Natural Science Foundation project(14JJ4064) of Hunan Province.

References

Gao,

(2017). Principles and technologies of Internet of Things RFID. Electronic Industry Press, Beijing, China, pp. 24–25. ISBN:9787121303616.

Chen,

, et al. (2010). China technology development strategy research of radio frequency identification. Scientific Decision-Making 1, 8–20. doi: 10.3969/j.issn.1006-4885.2010.01.002

Xie,

, et al. (2009). Study on the ALOHA anti-collision algorithm based on optimized theory for RFID system. Journal of Circuits and Systems 4, 8–12. doi: 10.3969/j.issn.1007-0249.2009.04.002

Schoute,

F.C.

(1983). Dynamic frame length ALOHA. IEEE Transactions on Communications 31(4), 565–568.

Wang,

, et al. (2011). Research on an enhanced anti-collision algorithm for RFID. Computer Engineering and Science 6, 182–185. doi: 10.3969/j.issn.1007-130X.2011.06.036

Ren,

, et al. (2014). Research on double weight parameter anti-collision Q value algorithm in RFID system. Computer Science 4, 256–259. doi: 10.3969/j.issn.1002-137X.2014.04.054

Ren,

, et al. (2014). Decision threshold-based Q algorithm for RFID anti-collision. Computer Science 8, 154–157. doi: 10.11896/j.issn.1002-137X.2014.08.034

Sun,

, et al. (2012). Research and improvement on RFID system tags anti-collision. Computer Engineering and Applications 48(16), 103–106. doi: 10.3778/j.issn.1002-8331.2012.16.023

Hu,

, et al. (2015). Research on Q value anti-collision algorithm in RFID system based on in-frame adjustment. Manufacturing Automation 8, 19–21. doi: 10.3969/j.issn.1009-0134.2015.08.006

10.

Zhang,

, et al. (2013). An Enhanced Q parameter hybrid anti-collision algorithm. Computer Technology and Development 8, 47–51. doi: 10.3969/j.issn.1673-629X.2013.08.012

11.

Xie,

, et al. (2007). RFID technology and anti-collision algorithm. Computer Engineering and Applications 43(6), 223–225. doi: 10.3321/j.issn:1002-8331.2007.06.071

12.

Vogt,

(2002). Efficient object identification with passive RFID tags. Lecture Notes in Computer Science 2414(10), 98–113.

13.

Floerkemeier,

(2006). Transmission control scheme for fast RFID object identification, 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006). Pisa: Institute of Electrical and Electronics Engineers Computer Society, pp. 457–462.

14.

EPC™ radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz 960MHz version 1.2.0[S]. EPC Global, 2008.

15.

Floerkemeier,

, Wille,

(2005). Comparison of transmission schemes for framed ALOHA based RFID protocols. The International Symposium on Applications and the Internet Workshops. doi: 10.1109/SAINT-W.2006.10

16.

Van Nee,

R.D.J.

, Van Wolfswinkel,

R.N.

, Prasad,

(1995). Slotted Aloha and code division multiple access techniques for land-mobile satellite personal communications. Selected Areas in Communications, IEEE Journal on 13(2), 382–388.

17.

Hu,

, et al. (2005). Application of slotted ALOHA to anti-collision of RFID system. Journal of applied Sciences 23(5), 489–492. doi: 10.3969/j.issn.0255-8297.2005.05.010

18.

Deng,

D.J.

, Tsao,

H.W.

(2011). Optimal dynamic framed slotted aloha based anti-collision algorithm for RFID systems. Wireless Personal Communications 59(1), 109–122.

19.

Wang,

, et al. (2014). Research on an improved RFID anti-collision algorithm based on Q value. Journal of Taiyuan University of Technology 45(3), 339–342. doi: 10.3969/j.issn.1007-9432.2014.03.013

20.

Klair,

D.K.

, Kwan-Wu,

, Raad,

(2010). A survey and tutorial of RFID anti-collision protocols. Communications Surveys & Tutorials, IEEE 12(3), 400–421.

21.

Che,

, et al. (2012). Research on anti-collision algorithm in UHF band RFID system. Science & Technology Information, China 32, 593–598. doi: 10.3969/j.issn.1001-9960.2012.32.543

22.

Hu,

, et al. (2010). Application research on monte carlo method in the communication system simulation. Digital Communications World 5, 43–45. doi: 10.3969/j.issn.1672-7274.2010.05.009