Received February 2015

ABSTRACT

A tag-collision (or missed reads) in RFID system (Radio Frequency Identification) system degrades the identification efficiency. The so-called tag collision is that a reader cannot identify a tag when more than one tags respond to a reader at the same time. There are some major anti-collision protocols on resolving tag collision, e.g., ALOHA-based protocol, binary tree protocol, and Query Tree (QT) protocol. Up to date, most tag anti-collision protocols are QT protocols. QT protocols are categorized into M-ary query tree (QT). In the previous literature, choosing M = 3 (i.e., a ternary QT (TQT)) was proven to have the optimum performance for tag identification. Recently, Yeh et al. used parallel response approach to reduce the number of collisions. In this paper, we combine the partial response and TQT to propose an effective parallel response TQT (PRTQT) protocol. Simulation results reveal that our PRTQT outperforms Yeh et al.’s protocol and TQT protocol.

Keywords:

Radio Frequency Identification (RFID), Tag Collision, Query Tree, Ternary Tree, Parallel Response

1. Introduction

Radio frequency identification (RFID) system consists of readers, tags and backend database server [1]. This technology can be applied in inventory control, distribution industry, supply chain management,∙∙∙, and etc. However, there are two types of collision problems in RFID system, the tag collision and the reader collision [2] [3]. Tag collisions occur when multiple tags respond to a reader simultaneously and the reader cannot differentiate these tags correctly. In this paper, we deal with the tag-collision problem. When tags communicate with a reader through wireless transmission, they should be uniquely identified one by one. After the successful identification, a reader then sends the collected data from tags to a data processing system (backend database server), for the further application need.

There are two types of two tag anti-collision protocol to address tag-collision problem. One is ALOHA-based protocol [4] and the other is tree-based protocol. ALOHA protocol reduces the tag collisions since it has the starvation problem (a tag cannot be identified for a long time). Tree-based protocols can be classified to the binary tree (BT) and the query tree (QT). In BT protocols [5]-[8], a tag generates a random bit. If the bit is “0”, tags transmit their Electronic Product Codes (EPCs) to the reader, and tags having “1” transmit later. By repeating this process, all tags can be uniquely identified.

QT protocols [9]-[12] are sending a query string to identify the tags. If just one tag ID matches the query string, then the tag is identified. When multiple tags have the same query string, they are collided with each other. Otherwise, this situation is idle. Usually, QT protocol is implemented as binary QT (BQT) protocol that query tree is binary tree. Also, M-ary QT (MQT) were proposed in [10]-[12] with arbitrary number M. Repre- senting binary tuples to a decimal digit, a QT can be used as MQT for M = 2, 4, 8∙∙∙etc. Using large M-ary tree reduces the number of collisions, but increases the number of idle situations. Obviously, MQT protocol is reduced to BQT protocol for M = 2. Mathys et al. claimed the optimum performance of MQT is M = 3, i.e., ternary QT (TQT) [13]. However, in real environment, readers and tags communicate through binary code. TQT protocol is hard to implement from binary EPC. In [14], the authors adopted a conversion of 3B2T (3 binary code to 2 ternary code), to practically implement TQT protocol.

Recently, Yeh et al. [15] proposed a parallel response query tree scheme that combines the frequency shift keying (FSK) modulation and Manchester coding to provide two subcarriers for tags communicating with reader in parallel. In this paper we adopt the parallel subcarriers of Yeh’s protocol and the optimal performance of TQT protocol to design a parallel response ternary query tree (PRTQT) protocol. The remainder of this work is organized as follows. In Section 2, we review previous woks, Yeh et al.’s protocol and 3B2T conversion in TQT protocol. In Section 3, we propose the PRTQT algorithm for tag anti-collision. Performance and comparison are given in Section 4. Finally, our conclusion is drawn in Section 5.

2. Previous Works

2.1. Partial Response in Query Tree

Yeh et al. [15] used frequency shift keying (FSK) modulation technique combining Manchester code to provide two subcarriers for tags to communicate with reader in parallel. In [16], two subcarrier tones in f₀ = 2.2 MHz and f₁ = 3.3 MHz based on the baseband carrier in 900 MHz is provided for a reader could receive two separate signals at the same time. The responded bits of tags are encoded as Manchester code, in which a low-to-high transition stands for 0, and a high-to-low transition stands for 1, as shown in Figure 1(a) and Figure 1(b). By this parallel two subcarrier responding and partial parallel prefix matching, Yeh et al.’s protocol performs like 4-ary QT protocol. However, Yeh et al.’s enhance the performance of 4-ary QT protocol since using two subcarriers.

A simple example with 8 tags with IDs {(0000100), (0010100), (0011010), (0011101), (1010110), (1011000), (1100111), (1101110)}. When reader send a query string S = (00), tags with prefix (00) and (11) will respond.

Also, the MSB + R₁ = 0 (respectively, 1) will use subcarrier f₀ (respectively, f₁) to respond, where MSB is the first bit of ID and R₁ is the first bit of the tag remainder exclusive S. In Figure 1(c), since MSB + R₁ = 0 for the tag (0000100), and MSB + R₁ = 1 for other tags of (0010100), (0011010), (0011101), (1100111), and (1101110), thus the tag (0000100) respond using subcarrier f₀ to sender and uniquely identified. Other five tags respond using f₀ and collide with each other. By the same argument, reader continuously sends the query string S = (0010). This procedure is repeated until all tags are successfully identified.

2.2. 3B2T Conversion in TQT

A ternary tree is impossible directly implemented in QT protocol to identify a binary EPC. So using TQT delivers a problem how to efficiently convert 96-bit (EPC)₂ to a ternary (EPC)₃.

The tradition method of convert binary digits to ternary digits is difficult to implement, and it would waste more time. The 3B2T conversion divides 96 bits EPC to 32 parts of three binary digits. And each three digits can map to two ternary digits by conversion table, this is shown in Figure 2. Actually, 96 binary bits just needs 61 ternary digits for conversion. Using 96 ´ (2/3) = 64 ternary digits for conversion is not the optimal choice, but this way could finish conversion faster than the traditional conversion. By 3B2T conversion divides all bits to be 32 parts, and each part is independent with others. Thus, we do not need to turn covert all EPC at once, and just convert the part we use.

3. The Proposed PRTQT Protocol

As we know, in [13], the authors showed that TQT (M = 3) has the optimum performance (i.e., the less identification time). The proposed PRTQT is motivated by the parallel subcarriers of Yeh’s protocol and the optimal performance of TQT protocol. We use a more complex reader that could distinguish three responded signals with different frequencies from tags, and meantime process each response in parallel. Notations and their descriptions used in the proposed PRTQT protocol are defined below.

The proposed PRTQT protocol combines the parallel subcarrier response method and TQT protocol. In the proposed PRTQT, we have to convert binary IDs to ternary IDs for all tags by using 3B2T conversion. A tag with ternary digit t = (t₁, t₂,∙∙∙, t₆₄), where t_iÎ{0, 1, 2} and 1 ≤ i ≤ 64. Readers first push (Q, 0) into a NULL queue Q. When the queue Q is not null, readers pop a ternary string q (|q| = x) from Q to broadcast. If t_i = q_i, for 1 ≤ I ≤ x − 1. Then the tag responds by using subcarrier c, where c is t_x. There are three outcomes may occur in subcarrier. When more than one tags respond with the same subcarrier, the collision occurs. Then, readers would push (Q, q’||c||0) into the queue Q, where q’ = (q₁, q₂,∙∙∙, q_x−1). On the other hand, if only one tag responds with the subcarrier, the tag would be uniquely identified. After the successful identification, tag sends its ID to the reader. This procedure is repeated until the queue Q is empty. In the proposed PRTQT, all binary digits of ID are not necessarily converted to ternary digits at first. We just need 3B2T conversion when the query strings need to be used, so that the performance can be improved. The proposed PRTQT algorithm is shown in Figure 3.

Example 1. We use eight tags with 12-bit ID: (000101010010), (000111010111), (001101110000), (001110010110), (010110100001), (101010110001), (110000100010), and (110001110011), to test the pro-

posed PRTQR protocol.

At first, the first three bits of all tags are converted into two ternary digits: (00), (00), (01), (01), (02), (12), (20), and (20) by 3B2T conversion. Readers then push (0) into a NULL queue Q for initialization. Readers pop a ternary string q = 0 from queue Q and broadcast the query string to all tags. Five tags with ternary prefix (00), (01) and (02), where t₁ = 0, respond to this query using subcarrier 0, and collide with each other since they respond with the same subcarrier 0. However, two tags with ternary prefix (20), where t₁ = 2, respond with subcarrier 2, and collide with each other since they respond with the same subcarrier 2. The tag with ternary prefix (12), where t₁ = 1, responds with subcarrier 1, and is uniquely identified. Thus, the tag (101010110001) with ternary prefix (12) is identified successfully. Readers then push (Q, 00) and (Q, 20) into the queue Q. When tags respond with the same subcarrier c, readers push string (q’||c||0) into the queue Q. After the first query cycle, the remainder of queue Q is {00, 20}. Hence, in the second query cycle, readers pop the string q = (q₁, q₂) = (00) and broadcast to all tags. Table 1 lists the detail of identifying procedure for all eight tags, and Figure 4 is its corresponding tree plot. Since we use three subcarriers to send the ternary digits, and thus there are no idle situations in the proposed PRTQT protocol. Finally, there are total 7 interrogation cycles.

4. Performance Evaluation

In this section, we conduct two experiments to evaluate the performance of BQT, TQT and the proposed PRTQT. Suppose tag’s ID is using EPC (96-bits). And we have n tags need to be identified, where n = 100, 200, 300, 400, 500, 1000 and 2000. In Experiment A, n tags are randomly chosen that is for real situation. Experiment B is special case for test the performance with similar EPC. In [17], we consider the RFID warehouse distribution. It is reasonable to assume that the EPC data of most items from the same warehouse will be very similar since the items are manufactured by the same company, and are stacked together in a large warehouse. So, tags have very similar EPCs for this case. Both experiments are showing the number of collision cycles N_C, idle cycles N_I and total cycles N_T.

Experiment A. Three protocols are tested: BQT, TQT, Yeh et al.’s protocol (denoted as PRQT), and the proposed PRTQT. Also, 96-bit EPCs of test tags are randomly generated.

^*successfully identified

In BQT and TQT, the leaf in a query tree just can be one of identification, collision, or idle node, where identification node is that one tag is uniquely identified. Hence N_T = n + N_C + N_I. For example, when n = 100, the BQT has 140 collisions and 42 idle times. The number of total interrogation cycles is N_T = 282 (= 100 + 140 + 42). However, in the proposed PRTQT, when n = 100, we have 61 collisions and no idle times. The number of total interrogation cycles is N_T = 95 (¹100 + 0 + 61). In fact, the PRTQT protocol can identify more than one tag in a cycle. Since three subcarriers are used in the proposed PRTQT, at most three tags can be simultaneously identified within one cycle. Thus, for PRTQT, N_T »[n/3] + N_C + N_I = [n/3] + N_C (∵no idle cycle). For example, the PRTQT has N_T = 1836 interrogation cycles, while [n/3] + N_C = 667 + 1164 = 1831. Both values are almost the same. For the case n = 2000, there 5534 and 5282 interrogation cycles for BQT protocol and TQT protocol, respectively. Our PRTQT uses parallel response method and ternary query tree, and there are total 1836 interrogation cycles, and enhance the N_T = 2729 in PRQT. Table 2 shows all the values of N_C, N_I, and N_T, and Figure 5 illustrates the number of total collisions for 100 £ n £ 2000. Obviously, our PRTQT protocol has the less interrogation cycles among all protocols.

Experiment B. Redo Experiment A, but use test tags with the very similar EPC data.

As we know, EPC embraces four sections: header (H: 8 bits), GMN (G: 28 bits), object class (O: 24 bits), and serial number (S: 36 bits). In fact, l_f and l_s are the first half and the second half in an EPC. Thus, in the so-called very similar EPC, we use the same first l_f = 60 bits (H + G + O) cascaded with the random l_s = 36 bits (S) for all tags. Experimental data are shown in Table 3. Compared with Experiment A using random EPC, the numbers of N_T for BQT, TQT, PRQT, and PRTQT increase when using similar EPC. Figure 6 illustrates the number of total

collisions for 100 ≤ n ≤ 2000. It is observed that our PRTQT also has the better performance. No matter what types of tags (random EPC or similar EPC) are tested, our protocols has the less N_T. For example, for n = 2000, our PRTQT has N_T = 1899, less than N_T = 5706, 5454, and 2852 in BQT, TQT, and PRQT, respectively.

5. Conclusion

In this paper, we proposed a PRTQT protocol to address the tag collision in RFID system. We adopt the parallel-subcarrier approach into TQT, so that tags can be identified in parallel subcarriers. Experiments reveal that the proposed PRTQT has better performance than BQT protocol, TQT protocol, and PRQT protocol.

Acknowledgements

This work was supported in part by Ministry of Science and Technology, under Grant 102-2221-E-259-009-MY2 and 103-2221-E-259-015.

Cite this paper

Ching-Nung Yang,Song-Ruei Cai,Li-Zhe Sun, (2015) Parallel Response Ternary Query Tree for RFID Tag Anti-Collision. Journal of Computer and Communications,03,72-79. doi: 10.4236/jcc.2015.35009

References