A collision recovery algorithm using optimal Q parameter based on BIBD in RFID①

Cui Yinghua (崔英花)

(School of Information and Communication Engineering, Beijing Information Science and Technology University, Beijing 100101, P.R.China)

?

A collision recovery algorithm using optimal Q parameter based on BIBD in RFID①

Cui Yinghua (崔英花)②

(School of Information and Communication Engineering, Beijing Information Science and Technology University, Beijing 100101, P.R.China)

In this work, an optimal Q algorithm based on a collision recovery scheme is presented. Tags use BIBD-(16,4,1) codes instead of RN16s. Therefore, readers can make a valid recognition even in collision slots. A way of getting the optimal slot-count parameter is studied and an optimal Q algorithm is proposed. The theoretical and simulation results show that the proposed algorithm can improve reading efficiency by 100% more than the conventional Q algorithm. Moreover, the proposed scheme changes little to the existing standard. Thus, it is easy to implement and compatible with ISO 18000-6C.

radio frequency identification (RFID), anti-collision, collision recovery, balanced incomplete block design (BIBD), Q algorithm

0 Introduction

RFID (radio frequency identification) is an automatic identification system which includes readers and tags. Due to tags battery presence or absence, RFID technology can be divided into: passive, battery assisted passive and active RFID technology[1].

In passive RFID, a reader communicates and powers tags using radio frequency (RF) waves transmitted by a reader antenna. Passive tags are able to harvest energy from the RF waves to power its circuitry, and respond back to the reader by smart reflection of the same RF waves. The carrier frequencies of the signals received by the reader are equal, as they originate from a single source, namely the transmitter of the reader. As the same oscillator is also available at the receiver, a down conversion without any frequency offset is readily possible. However the EPC standard[2]permits a large deviation of up to ±22% from that nominal frequency. Therefore synchronization in RFID readers is still an important task. In general, synchronization mechanisms are distinguished into maximum likelihood timing recovery[3]and minimum mean square error methods[4]. The first class estimates the timing instant by maximizing the likelihood function, while the latter estimates the timing instant by minimizing the mean square error.

In RFID applications, the reader reads tags’ information within the effective range and the tags will respond the request according to a predefined protocol. If several tags respond simultaneously, the reader will detect collision and no tag will be recognized. To solve this problem, many anti-collision protocols have been designed. However, most of them are based on collision avoidance theory and have low system efficiency, usually less than 36.8%[5].

Many researchers have investigated slots with colliding tag signals. Khasgiwale, et al.[6]estimated the number of tags involved in collision by the collision information on the physical layer. Kumar, et al.[7]proposed to use an interference cancellation scheme to separate the combined signals. Angerer, et al.[8]showed an RFID system which can be recovered from collision when two tags collide on a physical layer with a single antenna receiver. Kotevic, et al.[9]followed the work of Angerer and used more receiving antennas in the reader.

Apart from the researches mentioned above, recently some researchers have studied on using BIBD (balanced incomplete block design) code in the RFID system. BIBD code is denoted by BIBD-(b,v,r,k,λ) and can be simply expressed as BIBD-(v,k,λ). Mathematically[10], it can be proved that the object set is unique for BIBD-(v,k,1) when no more than k blocks in a set. According to this theory, it can be concluded that BIBD- (b,v,r,k,1) can support b symbols, and identify up to k symbols at one transmission. For example, BIBD-(16,4,1), which is also denoted as, BIBD-(20,16,5,4,1) supporting up to 20 symbols, which are column vectors of the incident matrix. It can be recognized whenever not more than 4 symbols collide.

In Ref.[11], Seol, et al. designed the symbols by using BIBD-(7, 3, 1) codes in the process of RFID tags identification and proposed a Multi-State Query Tree Protocol. The scheme does not require re-transmission when no more than 3 symbols collide, which will not only reduce the cost of power consumption, but also improve the system identification efficiency. In Ref.[12], Zhang, et al. advanced a novel and fast anti-collision algorithm based on the regressive-style RFID of BIBD-(4, 2, 1). The algorithm makes good use of the advantages of BIBD code, and can also significantly reduce the query time. However, these schemes use BIBD code to construct the EPC code, which decreases total number of supporting users, and are constrained to application-specific scenarios.

In this study, an optimal Q parameter algorithm based on BIBD is proposed. This algorithm uses BIBD code to construct tag’s respond serials RN16 (16-bit random number) instead of tags’ EPC codes. The reader therefore can recover the RN16s from the colliding signals even in low SNR environment, and acknowledge one of the collision tags, thus increase the system efficiency greatly.

The rest of this paper is organized as follows: Section 1 describes the RFID anti-collision scheme based on BIBD, analyzes its performance and studies how to get the optimum slot-count Q parameter. Section 2 proposes the collision recovery algorithm using optimal Q parameter selection. A performance analysis of the proposed scheme is provided in Section 3. The last section concludes the work.

1 The optimal Q vlaue for the BIBD scheme

The ISO 18000-6C specification proposes a frame slotted ALOHA based on anti-collision protocol, named Q-algorithm[13]. It has three basic commands: Query, QueryRep and QueryAdjust. After the reader sends a Query to initiate an inventory round, it then issues one or more QueryAdjust or QueryRep commands in this inventory round depending on whether the Q value needs to be changed. In response, tags that have nonzero slot numbers should decrease their count values and backscatter RN16 when their counter values reach zero. This process continues iteratively until all the tags have been recognized.

In this section, a modified Q algorithm based on BIBD is presented which is compatible with ISO 18000-6C. In the scheme, tags use BIBD-(16,4,1) instead of RN16, and backscatter BIBD symbols to reader, who can recover the RN16s from the colliding signals, and make a valid recognition in collision slots.

First, the system efficiency should be analyzed, and then how to choose the optimal Q parameter should be studied. Suppose there are totally n tags to be identified and the total slot number is N, the probability that k tags exist in one slot (k-occupation slot) follows a binomial distribution[14]:

(1)

So the expectation of k-occupation slot number is

Ek=N×Pk

(2)

the system efficiency is defined by

(3)

Usually, the efficient reading slot refers to a successful tag transmission when exactly one tag transmits in a slot. The expectation of Eff can be calculated as

(4)

BIBD-(16,4,1) has 20 symbols with 16-bit in length, and identifies up to 4 symbols at one transmission. By using it instead of RN16, the reader can extract an individual BIBD code from the tags involved in a collision and make a valid acknowledgement. Accordingly, the expectation of the system efficiency can be denoted by

(5)

Letf=N/n, for different tag numbers, the optimal values of f and the maximal efficiency are obtained as shown in Fig.1 and Fig.2.

Furthermore, for n and N→∞, Eq.(5) can be reformulated to

(6)

Fig.1 The optimal values of f for different tag numbers

Fig.2 The maximal values of Eff for different tag numbers

The maximal system efficiency can be reached with

(7)

It is a non-linear equation in one variable, and a simple bisection search or Newton’s methods are used to solve it, and the result is foptimal≈0.452. Therefore, the max system efficiency can be obtained as

Effmax=Eff|f=0.452=0.817

(8)

The Q algorithm uses Q as the slot count parameter and sets the frame size as 2Q, where Q is in the range of [0, 15]. From the figure of function Eff(f), the maximal efficiency can be obtained at the point of nearby 0.452. It is easy to prove that the function is monotonic in the range of f<0.452 or f>0.452. Hence, the optimal Q value can be reached at

(9)

Here, integer T satisfies 2T-1<0.452n<2T.

2 The collision recovery algorithm with optimal Q value selection based on BIBD

Conventional readers only read data in singleton slots, while the proposed BIBD method is able to identify them in collision slots. So the original Q selection algorithm is not suitable here, and needs some modifications.

It is known that the exact number of tags in the field allows an optimal choice of Q. When collisions occur, the number of tags involved in the slot can be determined. Combining the number of tags detected in afore rounds will give an accurate estimate of the number of tags participating in the identification process. This can be used to set a near optimal Q value for the next round. The details of the optimal identification process are described as follows:

(1) Reader selects an initial tag number, let it be N=2Q, then sends Query command with a slot-count parameter Q to the tags. Tags will pick a random value in the range of [0, 2Q-1] and load this value into slot counter. Tags that pick zero will transit to the reply state, choose one of BIBD-(16,4,1) symbols randomly to make an 16-bit signal instead of RN16 and reply immediately, other tags will transit to the arbitrate state and await a QueryRep command.

(2) If the reader detects no more than 4 tags’ reply, it shall choose one and sends an acknowledgment command to the tag. The identified tag then processes the received ACK and reports its ECP back to the reader.

(3) If the reader detects idle or more than 4 RN16s, no tag will be acknowledged.

(4) For each slot, the reader determines the number of reply tags. If there are more than four tags, the reader can’t determine the exact tag number in the slot. It then estimates the number with an approximation by 5. For example, the estimate for i-th slot is given by

(10)

Suppose current slot is the l-th slot, reader can estimate the total tag population by

(11)

Then, suppose 2T-1

(12)

To make the estimate more accurate, such calculation is made only when l≥3.

(5) If Qoptequals to the current Q value, the reader uses QueryRep command to notify the tags to decrement their slot counters by 1, else reader estimates the remaining tags:

Rl=Estl-Il

(13)

here Ilis the recognized tag number during this identification round. then it is used to estimate the new Q value:

(14)

The reader then adjusts the Q value with QueryAdjust command.

(6) The above process may iterate many times, until all the tags have been recognized.

In contrast to the conventional Q algorithm, the proposed scheme uses BIBD-based 16-bit signals instead of RN16, and employs an optimal Q selection algorithm. The scheme estimates the tag population during recognition process, and adjusts the Q parameter more efficiently. For each collision slot, only one tag is preferred to acknowledge, though acknowledge all the collided tags within one slot can increase the system efficiency greatly. While it will introduce more change to the conventional Q scheme which is not desirable. It is clear that the scheme is compatible with ISO 18000-6C and easy to implement.

3 Simulation results

The performance of the proposed method for collision recovery is verified through MATLAB simulations. In this section, a simulation model based on the algorithms described in section 2 is established and it is compared with the conventional Q parameter algorithm and the modified Q algorithm mentioned in Ref.[15], which is one of the previous work based on BIBD without optimal Q parameter selection. The simulation is repeated 100 times for each number of tags from 100 to 1000, and the initial value of Q is set to 4. Actually, the tag number beforehand is unknown and the frame size N is a power of 2 and parameter Q can only be adjusted gradually, so the actual system efficiency should be a little lower than the theoretical maximum.

The result of this experiment is depicted in Fig.3. It shows that the optimal Q value scheme is far more effective than the conventional one. For other improved Aloha-based schemes, such as EDFSA[16]and TSA[17], the proposed scheme also behaves much better than them, as their average efficiencies did not exceed 38%. Moreover, the optimal scheme is also better than the modified Q algorithm. The two Q algorithms both choose 4 as the initial value of Q; the modified Q algorithm employs a slightly changed Q selection algorithm while the optimal scheme uses an optimal Q parameter selection, which proves that the optimal slot-count parameter choosing method contributes to the identification efficiency greatly. It is interesting to notice that the figure of the proposed scheme is like a wave, the crests are reached at about 64, 256, 512, … which are the points the estimation is the most accurate.

Fig.3 Comparison of the efficiency of different algorithms

It also should be emphasized that the proposed scheme only makes minor changes to the original Q algorithm. One is using BIBD-(16,4,1) block instead of RN16 for tags, which is the main idea of the proposed scheme to enable readers to decode RN16s from collision signals and make a valid acknowledge within a collided slot. The other is the optimal slot-count select algorithm. Qestis updated after every reading slot, and the Q value is adjusted dynamically when necessary. Therefore, the scheme is compatible with ISO 18000-6C and easy to implement. The theoretical and simulation results show that the scheme has greatly improved system efficiency.

4 Conclusion

In this work a collision recovery algorithm using optimal Q parameter based on BIBD is proposed. Using BIBD-(16,4,1) code instead of RN16 for tags’ backscatter, it enables readers to make a valid acknowledge from collision slots with no more than 4 tags. As a result, the system efficiency can be improved greatly. Moreover, the optimum slot-count parameter selection is studied and an optimal Q algorithm is designed which can adjust the slot-count parameter more efficiently. Simulation indicates that the scheme has good

performance. Compared with the standard Q algorithm in Gen2, a performance gain of about 100% can be achieved.

[ 1] Dobkin D M. The RF in RFID. Burlington: Elsevier, 2008

[ 2] EPCGloabl. EPC Radio-Frequency Identity ProtocolsClass-1 Generation-s UHF RFID, Oct., 2008

[ 3] Kobayashi H. Simultaneous adaptive estimation and decision algorithm for carriesr modulated adata transmission systems. IEEE Transcations on Communication Technology, 1997, 19(3):268-280

[ 4] Barry J R, Lee E A, Messerschmitt D G. Digital Communication. 3rd Edition, Springer, 2004

[ 5] Finkenzeller K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification. 2nd Edition. John Wiley & Sons Ltd, 2003

[ 6] Khasgiwale R S, Adyanthaya R U, Engels D W. Extracting information from tag collisions. In: Proceedings of the IEEE International Conference on RFID, Orlando, USA, 2009. 131-138

[ 7] Kumar R, La Porta T F. Interference cancellation-based RFID Tags Identification. In: Proceedings of the 14th International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, Miami, USA, 2011. 111-118

[ 8] Angerer C, Langwieser R, Rupp M. RFID reader receivers for physical layer collision recovery. IEEE Transactions on Communications, 2010, 58(12): 3526-3537

[ 9] Kaitovic J, Langwieser R, Rupp M. RFID reader with multi antenna physical layer collision recovery receivers. In: Proceedings of the IEEE International Conference On RFID-Technologies and Applications (RFID-TA), Sitges, Spain, 2011. 286-291

[10] Colbourn C J, Dinitz J H. The CRC Handbook of Combinatorial Design. Boca Raton: CRC Press, 1996

[11] Seol J M, Kim S W. Collision-resilient multi-state query tree protocol for fast RFID tag identification. In: Proceedings of the International Conference on Computational Intelligence and Security, Guizhou, China, 2006. 1159-1162

[12] Li Z, Zhang X, Lei Z. Anti-collision algorithm based on the regressive-style RFID of BIBD (4,2,1). In: Proceedings of the International Conference on Advanced Computer Theory and Engineering (ICACTE), Chengdu, China, 2010. 352-355

[13] International Organization for Standardization/International Electrotechnical Commission. ISO/IEC 18000-6 information technology automatic identification and data capture techniques—radio frequency identification for item management air interface—Part 6: parameters for air interface communications at 860-960MHz. International Organization for Standardization, 2007

[14] Vogt H. Efficient object identification with passive RFID tags. In: Proceedings of the 1st International Conference on Pervasive Computing，Zürich, Switzerland, 2002. 98-113

[15] Cui Y H, Yang S G. A modified Q parameter scheme based on BIBD in RFID. Advanced Materials Research, 2013, 765: 2041-2045

[16] Lee S R, Joo S D, Lee C W. An enhanced dynamic framed slotted aloha algorithm for RFID tag identification. In: Proceedings of the 2nd Annual International Conference for Mobile Ubiquitous Systems: Networking and Services, Boston, USA, 2005. 162-172

[17] Bonuccelli F L M A, Martelli F. Tree slotted aloha: a new protocol for tag identification in RFID networks. In: Proceedings of the International Symposium on World of Wireless, Mobile and Multimedia Networks, New York, USA, 2006. 603-608

Cui Yinghua, born in 1973. She received her Ph.D degree and Master degree from Peking University in 2009 and 2003. Her research interests include anti-collision algorithm in RFID, wireless communication, and wireless sensor network.

10.3772/j.issn.1006-6748.2016.04.002

① Supported by the National Natural Science Foundation of China (No. 61340005), Beijing Natural Science Foundation (No. 4132012), Beijing Education Committee Science and Technology Development Plan (No. KM201411232011), Beijing Outstanding Personnel Training Project (No. 2013D005007000006), Scientific Research Improving Project-Intelligent Sense and Information Processing (No. 5211524100).

② To whom correspondence should be addressed. E-mail: cui_ying_hua@sina.com Received on Sep. 15， 2015