# An Efficient Early Frame Breaking Strategy for RFID Tag Identification in Large-Scale Industrial Internet of Things

Authors: Zhiyong He; Hanguang Luo
Journal: Scientific Programming
 (2021)

---

## Abstract

With the increase in the number of tags, an efficient approach of tag identification is becoming an urgent need in Industrial Internet of Things (IIoT). However, the identification performance of existing Aloha-based anticollision schemes is limited when the initial frame size is seriously mismatched with the actual tag population size. The performance will degrade further when IIoT is deployed in the error-prone channel environment. To optimize the identification performance of RFID system in an error-prone channel environment, we propose an efficient early frame breaking strategy based anticollision algorithm (EFB-ACA) with channel awareness. The EFB-ACA divides the whole tag identification process into two phases: convergence phase and identification phase. The function of convergence phase is to make the adjusted frame quickly converge to an appropriate size. The early frame breaking strategy is embedded in the convergence phase. Numerical results show that the proposed EFB-ACA algorithm outperforms the other methods on efficiency and stability in the error-prone channel. In addition, EFB-ACA algorithm also outperforms the other methods in the error-free channel.


---

## Body

## 1. Introduction

RFID is a key enabler of the Internet of Things (IoT), playing a crucial role in connecting low-/nonpowered devices to IoT environments. EPC C1 Gen2 [1] is the standard UHF RFID protocol devised to meet the demands and requirements of such applications. An RFID reader can communicate with hundreds of passive RFID tags within seconds, even at a distance of several meters away from the tags. The most remarkable virtue of the Gen2 standard is its lightweight and universality. Due to the shared nature of communication channel, a passive RFID system requires a collision arbitration protocol to serialize tag responses and mitigate collisions between the tag responses.Recently, there have been three types of collision arbitration protocols to cope with tag identification, namely, Aloha-based [2–5], query-tree-based [6–8], and tree-splitting-based [9, 10] protocols. In Aloha-based protocols, the reader uses tag quantity estimation and frame size adjustment strategies to identify tags. Specifically, the reader sends a query command containing a parameter F (F denotes the number of slots per frame) to allow the tags to return the IDs. The reader decodes the responses in each slot and distinguishes their states: collision, empty, and singleton. According to slot statistics in a frame, the reader can estimate the cardinality of unread tags and update the new frame for the next round. According to the analysis in previous works, the maximal system throughput of Aloha-based protocols is 0.368 [2–5]. In query-tree-based protocols [6–8], the reader queries the tags through probe commands. Each tag is required to be equipped with a prefix matching circuit, and it will respond only when the tag ID matches the prefix of the probe command. Once a collision is detected, the reader will update the query prefix according to the position of collision bits. Then, the reader uses the updated prefixes to interrogate the tags until all of them are successfully identified. In tree-splitting-based protocols, the reader continues to group the colliding tags with a separation probability of 0.5, until a certain group contains only one tag.In existing Aloha-based anticollision algorithms, tag population size estimation is a critical issue because it can help the reader to achieve the maximum efficiency when the frame size is the same as the tag population size. The authors in literature [11] utilized minimum distance to estimate the tag population size and adjusted the frame size based on the estimated tag cardinality. Schoute [12] concluded that the unread tag population size should be approximately 2.39 times of the number of collision slots. Chen in [13] proposed a feasible and easy-to-implement anticollision (FEIA) algorithm. In FEIA algorithm, when the first slot is an empty slot, the identification efficiency will be seriously constrained. The study in [14] firstly presented a subframe-based dynamic frame slotted Aloha (SUBF-DFSA) algorithm, which introduces a fixed early breaking scheme to tag identification process. However, the error-prone channel is not considered in above methods. Moreover, when the initial frame size is mismatched with the actual number of tags, the identification efficiency of these algorithms will be seriously affected.Nowadays, RFID tags can be assembled almost anywhere. Considering environmental factors, RFID systems may not be able to maintain highly reliable communications [15]. The signal quality of RFID systems will be affected by the communication distance between the reader and tags [16]. The reader may not be able to successfully decode the weak signal returned by the tag; and it will cause the wrong statistical information of slot types in a frame [17]. Accordingly, the performance of anticollision algorithm will be severely weakened. Therefore, when designing an anticollision algorithm, the adaptability of the algorithm to the channel environment should be considered.To cope with the above challenges, we propose an efficient early frame breaking strategy based anticollision algorithm (EFB-ACA) with channel awareness. The proposed EFB-ACA divides the tag identification process into two phases: convergence phase and identification phase; and various collision ratios are applied to identification phase to improve the identification efficiency. The core contributions of this paper can be summarized as follows:(1)
An efficient and channel-aware anticollision algorithm is proposed. It can derive the actual number of singleton slots and collision slots in each frame based on the successful transmission possibility of identified tags, which indicates that EFB-ACA can be utilized in a variety of channel environments.(2)
In our proposed EFB-ACA, the identification process can be divided into convergence phase and identification phase, where Bayesian estimation and various average collision ratios are utilized to improve the estimation accuracy of tag population sizes.(3)
This paper reviews the most appropriate break point of the frame in detail. Our proposed approach makes full use of the early breaking strategy. It can not only accelerate the convergence of frame sizes but also improve the stability of anticollision algorithm.


## 2. The Proposed Algorithm

In this section, we present the proposed algorithm in detail. Table1 summarizes the notations used in the paper.Table 1
Notations used in the paper.
SymbolDescriptionFFrame sizeFsubSubframe sizeNNumber of tags waiting to be identifiedNestEstimated number of remaining tagsENumber of empty slots in a frameSNumber of actual singleton slots in a frameCNumber of actual collision slots in a frameSdNumber of slots where the tag response is successfully decoded in a frameCdNumber of slots where the tag response fails to be decoded in a frameDue to the uncertainty of the channel, a singleton slot may be misjudged as a collision slot. Therefore, an error resilient method is required to improve channel adaptability of anticollision algorithms. EPC C1 Gen2 specifies the communication link between a reader and tags. The tags respond by reflecting the electromagnetic wave from the reader. Assume that the wavelength isλ and that the distance between the reader and the tag is d. The channel coefficients of the downlink and uplink are defined as hd and hu, respectively. Considering the large-scale fading, the downlink attenuation hd2 can be expressed as(1)hd2=λ4πd2.The uplink attenuationhu2 is equal to hd2 because the distances are equal. Let η denote the tag reflection loss. Assume that the transmitting power of the reader is defined as Pt, and the receiving power can be written as(2)Pr=Pthd2ηhu2.LetN denote the noise power, and the signal to interference plus noise ratio (SINR) can be calculated as(3)PSINR=PrN.Since the passive RFID system adopts PR-ASK modulation, the bit error ratio (BER) can be expressed as(4)RBER=12erfcRSINR2,where erfc() is the complementary error function. Consider that the packet length is L, and the probability that a tag response can be successfully decoded by the reader can be expressed as(5)Pd=1−RBERL.Accordingly, the reader can estimate the distance away from the tag based on the fixed transmitting power. When a tag is identified successfully, the reader can obtain the distance and calculatePd. After identifying all tags, the reader can obtain the average successful probability Pd¯. The actual number of singleton slots can be estimated as(6)S=SdPd¯.Then, the actual number of collision slots can be estimated as(7)C=Cd−1−Pd¯SdPd¯.Due to the estimation of channel quality, the proposed algorithm can improve robustness and identification efficiency over the previous work.To accelerate convergence and improve estimation accuracy, early breaking strategy and Bayesian estimation are utilized in convergence phase. When the firstm slots are collision slots, the actual tag population size is probably much larger than current frame size. The following slots are very likely to be collided. It can be viewed as current frame size is seriously mismatched with the actual tag population size. In this case, it is necessary to end the frame and adjust the frame size in advance. If early breaking strategy is used, the break point needs to be determined. The tag population size is a random variable N, which follows a discrete probability distribution. The number of tags in a subframe is also a random variable Nsub. Due to randomness of a tag to choose a slot, the relation between Nsub and N is(8)Nsub=MsubMN.Then, the total number of tagsNE is written as(9)NE=MMsubNsub,and ENE is the estimated tag population size, which is the expected value of NE. DNE is the variance of NE. The error of expected value can be calculated as(10)ErrorE=ENE−ENEN.The error of variance is(11)ErrorD=DNE−DNDN.Assume that the maximum error of variance isε, and we can have(12)ErrorD≤ε.Then, we can obtain(13)M2DNsub1+εDN≤Msub≤M2DNsub1−εDN.Therefore, given a probability distribution andε, the break points can be calculated. As Figure 1 shows, in the tag identification process, the distribution of tag population size is close to normal distribution. To obtain appropriate break points, we choose the normal distribution NM,M/162 as the distribution of N and set ε = 0.03. Then, the break points shown in Table 2 can be derived.Figure 1
Performance comparison of the convergence phase in error-prone channel.Table 2
Breaking point.
Frame sizeSubframe size161632166416128162561651232102432204832At the breaking point of a frame, the distribution of tag population size needs to be updated based on Bayesian estimation. The updating function is(14)PN|E,S,C=PNPE,S,C|NPE,S,C,where PN|E,S,C is the updated distribution and P(N) is the previous distribution. Conditional probability PE,S,C|N can be calculated by(15)PE,S,C|N=M!E!S!C!PEPS|EPC|E,S.where P(E) is the probability of E empty slots; PS|E and PC|E,S are the conditional probability of S successful slots and C collision slots. PE,S,C can be considered as a constant. It can be ignored during updating distribution. When the distribution is updated, normalization should be completed for the probability distribution. Since the identified tags are no longer involved in the following identification process, PN−S|E,S,C will be the new probability distribution P(N) of the random variable N in the next frame. The number of rest tags will be estimated as the expected value E(N). We limit the maximum adjustment multiple of frame sizes as 8 for the consideration of stability.Since the frame sizes are restricted to the power of 2, various tag population sizes may be matching with the same frame size. The corresponding relation between the number of tags and optimal frame size is shown in Table3.Table 3
Optimal frame sizes for various tag population sizes.
Tag population sizeFrame sizes2–546–11812–221623–443245–886489–177128178–354256355–709512710–14191024Once the frame size is matching with the estimated tag population size, the proposed algorithm will enter identification phase, where the frame size will almost match with the tag population size all the time. The aim of this phase is to improve identification efficiency. In such phase, the early breaking strategy is no longer utilized. For the sake of estimating the tag population size, it is needed to compute the number of tags in a collision slot. The average collision ratioRc can be calculated by(16)Rc=1Nmax−Nmin+1∑N=NminNmaxN−NsMc.where Nmax and Nmin are the maximum and minimum number of tags corresponding to the current frame size. Ns is the average successful tag population size, which is written as(17)Ns=N1−1MN−1.Mc is the expected collision slots, which can be obtained by(18)Mc=M−Ns−M1−1MN.Then, the number of tags in the collision slot can be derived. Therefore, the number of rest tags will be estimated asRc times of the actual collision slot population size C. Then, the corresponding optimal size of the next frame will be confirmed.Tag identification process enters the convergence phase first and transfers to identification phase when the frame size becomes matching with number of rest tags. In the convergence phase, early breaking method is utilized to accelerate the convergence process. At the check slot of each frame, whether current frame size is matching with the estimated tag population size or not will be examined. If not, current frame will break and update the distribution of the tag population size. Then, the reader launches a new round with an appropriate frame size. If the current frame size is matching with the estimated tag population size, the frame will continue and enter identification phase at the end of the frame.In the identification phase, simple tag estimation is used to improve the efficiency and reduce the complexity. After each frame, the related information of the frame will be recorded. According to the current frame size and the number of collision slots, the number of rest tags will be accurately estimated. Then the optimal frame size can be determined. The above procedures will be repeated until there are no collisions.


## 3. Experimental Study

This paper evaluates the performance of our proposed EFB-ACA algorithm, SUBF-DFSA, ERE-ABS, DS-MAP, and LC-DFSA in the error-prone channel. To maintain the convergence, Monte Carlo method is used in the simulations [18–21]. Figure 1 compares the convergence phase duration of various algorithms in error-prone channel. Benefiting from the early breaking strategy and Bayesian estimation method, the proposed EFB-ACA can quickly pass the convergence phase and choose an appropriate frame size. Due to the fixed break points, the convergence speed of SUBF-DFSA is slower than that of the proposed algorithm. Because LC-DFSA and DS-MAP adjust the frame size only at the end of each frame, they will consume more slots to obtain an optimal frame size. As for ERE-ABS, it consumes most number of slots to enter into identification phase, resulting into the worst convergence speed among these algorithms.Figure2 shows the efficiency in the identification phase of various algorithms in the error-prone channel. The initial frame sizes of various algorithms are varied. The proposed algorithm estimates the number of rest tags by different collided ratios, which leads to the accurate estimation result. It has the highest identification efficiency among these algorithms. The other methods are affected by the error-prone channel. The efficiencies of ERE-ABS and LC-DFSA are relatively less affected by initial frame size; and SUBF-DFSA is relatively more affected by initial frame size. The reason is as follows. In an error-prone channel environment, an inappropriate frame size will cause a large difference between the collision probability and the empty probability, leading to inaccurate estimation results of tag cardinality.Figure 2
Performance comparison of the identification efficiency in various initial frame sizes.Figure3 presents the identification efficiency of different algorithms in the error-prone channel. We can find that the proposed algorithm can identify the same amount of tags with the least slots. It fully utilizes early break scheme and Bayesian estimation. Then, it achieves the highest identification efficiency in both convergence stage and identification stage. However, for the other reference methods, the inaccurate information of singleton and collision slots leads to the estimation accuracy deterioration. Then, the identification efficiency will be affected.Figure 3
Comparison of identification efficiency in error-prone channel.Figure4 presents the effect of different initial frame sizes on the access efficiency in the error-prone channel. The number of tags is set as 1,000. As we can see from the results, the proposed algorithm can achieve stable and high access efficiency no matter the initial frame size is. The efficiency is not affected by the initial frame size because of the reasonable early break scheme. When the initial frame size is small, SUBF-DFSA can realize stable efficiency. However, the stability will be worse as the initial frame size further increases due to its fixed early points. Because the early break method is not utilized in ERE-ABS and LC-DFSA, the initial frame size greatly affects the identification efficiency; and when the initial frame size is close to the number of tags, it can achieve higher identification efficiency.Figure 4
Influence of initial frame size in error-prone channel.


## 4. Conclusion

In order to improve tag identification efficiency and channel adaptability of anticollision algorithms in RFID systems, a Bayesian estimation and early break based anticollision algorithm with channel awareness is proposed. We model the communication links between the reader and tags and carry out theoretical analysis of the proposed algorithm. The reader can estimate the link condition through the fixed transmitting power. It helps to obtain the real slot status; and the whole tag identification process is divided into two stages: convergence stage and identification stage. The main purpose of convergence stage is to make the frame size quickly converge to an appropriate value; and the tag identification is mainly performed in identification stage. Early break scheme and Bayesian estimation are applied to the convergence stage to accelerate convergence and improve the estimation accuracy. Different collided ratios are used in the identification stage, which can improve the identification efficiency. Through our simulations, we can find that the proposed algorithm outperforms the other algorithms on both stages in the error-prone channel; and the initial frame size has little effect on efficiency of the proposed algorithm. Besides, even in the error-free channel, the proposed algorithm can also outperform the other algorithms. The identification efficiency of the proposed algorithm can reach 0.36, which is close to the theoretical optimal performance.



---

*Source: 4603629-2021-05-20.xml*