文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2018, Vol. 30 Issue (6): 789-796  DOI: 10.3979/j.issn.1673-825X.2018.06.009
0

引用本文 

尚弘. 一种基于搜索树的轻量级RFID标签防碰撞方案[J]. 重庆邮电大学学报(自然科学版), 2018, 30(6): 789-796. DOI: 10.3979/j.issn.1673-825X.2018.06.009.
Hong SHANG. A lightweight RFID tags anti-collision scheme based on searching tree[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2018, 30(6): 789-796. DOI: 10.3979/j.issn.1673-825X.2018.06.009.

通信作者

尚弘 75643982@qq.com

作者简介

尚弘(1977—), 河南睢县人, 讲师, 硕士, 研究方向为物联网应用、智能控制。75643982@qq.com

文章历史

Received date: 2018-08-06
Modification date: 2018-11-17
A lightweight RFID tags anti-collision scheme based on searching tree
Hong SHANG     
Jiangsu Key Laboratory of Internet of Things, Taihu University of Wuxi, Wuxi 214064, P. R. China
Received date: 2018-08-06; Modification date: 2018-11-17
Abstract: The existing RFID (radio frequency identification) searching tree anti-collision schemes incur large amounts of redundancy data due to an excess of long query commands, which increases the communication overhead. The paper proposed a lightweight anti-collision scheme based on searching tree. At first, the scheme designed a novel query response mode (i.e., single query with duo responses), which can make the collided tags respond to the next query in two subsequent slots respectively according to their most significant collided bit, and reduce the total number of queries by half. The scheme replaced the prefix matching circuit in tag with a counter, which can eliminate the prefix as the reference parameter of query command. Besides, the scheme put forward a predictive identification method to decrease the total number of the required slots. Finally, the scheme also proposed a locking technique to avoid the identified tags colliding with the unidentified tags, which can improve the identification efficiency of tags. The experimental results show that the communication overhead is decreased overall 42% by using single query with duo responses mode and counter trigger, and that the throughput is improving with the number of tags by using predictive identification.
Keywords: radio frequency identification (RFID)    anti-collision    searching tree    lightweight    
一种基于搜索树的轻量级RFID标签防碰撞方案
尚弘    
无锡太湖学院 物联网技术江苏省重点实验室,江苏 无锡 214064
摘要: 针对现有的RFID(radio frequency identification)搜索树防冲突方案由于查询命令过长,会产生大量的冗余数据,增加通信开销的问题,提出一种基于搜索树的轻量级防冲突方案。该方案设计了一种新颖的查询-响应模式(即单查询双响应),该方法能够使冲突标签分别根据2个后续时隙中的最大有效冲突位对下一个查询作出响应,将查询总数减少一半;该方案用计数器代替了标签中的前缀匹配电路,可消除前缀作为查询命令的参考参数。此外,该方案提出了一种预测识别方法以减少所需时隙总数。最后,该方案还提出了一种避免识别标签与未识别标签冲突的锁定技术,提高了标签的识别效率。实验结果表明,采用双应答模式和计数器触发的单次查询方式,通信开销总体上降低了42%;采用预测识别方式,吞吐量随着标签数量的增加而提高。
关键词: 射频识别(RFID)    防碰撞    搜索树    轻量级    
1 Introduction

Radio frequency identification (RFID) is an automatic identification system which consists of readers and tags. A tag has an identification number (ID) and a reader recognizes an object through consecutive communications with the tag attached to it[1]. The reader sends out a signal which supplies power and instructions to a tag, the tags transmit their ID using back scattering in response to the query from the reader. Since tags are self-contained entities that don't know about other tags, they always send information to the reader on their own schedule. For a reader only has one channel for communication, having two or more tags simultaneously transmitting to the reader in the air interface leads to tag collision, the reader can't identify the tags due to tag collision. To read information properly from these tags, the reader must adopt an anti-collision scheme. Taking system cost, protocol complexity, bandwidth requirements, hardware requirements for tag, and overall performance into consideration, time division multiple access (TDMA) protocols are the most popular methods to deal with the tags collision[2]. According to the coordinating policy for the shared RF wireless channel, they can be further classified into Aloha and tree based schemes. Aloha-based ones have fairly low cost and complexity in system implementation, but their throughput are low (less than 36.8%), and usually suffer from the tag starvation problem (i.e., some specific tags possibly can't be identified due to always colliding with others)[3]. In contrast, tree-based schemes not only have high throughput, but don't suffer from the tag starvation problem. In fact, tree-based ones can single out and read every tag by iteratively grouping the collided tags. According to grouping policy, tree-based schemes can be categorized into the following categories[4], i.e., query tree, splitting tree, searching tree and bitwise arbitration tree. Among the tree-based schemes, the searching tree scheme outperforms others because it uses Manchester coding[5]. The reader can find collided bits in the received tag ID by Manchester decoding. Once collision occurs, the reader will divide the collided tags into two subsets. Hence, there always exist some tags responding the query from the reader, which reduces the delay caused by idle slot, and improves the throughput (more than 50%)[6]. Therefore, our proposed RFID tags anti-collision scheme will still focus on the searching tree scheme.

2 Related works

In this section, we survey the relatedprevious works for the proposed scheme, which include three schemes based on binary search.

In binary searching-based schemes, it requires the reader to knowthe position of collided bits, which can be resolved by Manchester coding. As known, Manchester coding represents each data bit by the level transition of signal wave within each bit period. So, there exists no data bit which signal level doesn't change. If such data bit is tracked, it would be identified as a collided bit. Therefore, the reader can obtain the position and the number of collided bits.

Binarysearching tree scheme (BST)[5] is the original binary searching-based scheme. The reader sends query command with reference ID. The initial reference ID is the maximum possible tag ID value (e.g., 11111111). Those tags with ID equal to or lower than the reference ID shall respond with their ID. If only one tag responds, the tag could be identified. Otherwise, some collisions occur, and none of tag could be identified. In this case, the reader can find the most significant collided bit (denoted as χ) in the received ID by Manchester decoding, and then send a new query command by replacing the |χ| bit of reference ID with '0' (|χ| is the position of χ). The above process is iterated, until only one tag responds. If the reader identifies a tag, it would send a quiet command, which require the tag to enter the sleep state and no longer respond to the query command from the reader.

BST scheme can deal with the tag collision, but it suffers from high communication overhead. BST usually selects the whole tag ID as the reference ID of the query command, and always require tag to respond the query with its whole ID. In order to reduce the communication overhead rooting from a long reference ID, conference[7] proposed dynamic binary searching tree (DBST) scheme which adopts variable-length ID as its reference ID. In the scheme, the reference ID is a prefix, which is a part of the received tag ID preceding the χ followed by a data bit '0'. If the part of tag ID is equal to the prefix (i.e., tag ID match the prefix), the tag should respond with the remaining bits of the tag ID, which can reconstruct as a complete tag ID combined with the prefix by the reader. Otherwise, the tag shall enter a wait state to wait for the later query from reader. If collision occurs when more than one tag has the same prefix, the above process will repeat many times until only one tag responds.

After a tag is identified successfully, DBST scheme will enter a new query iteration procedure after the reader sends a query command with initial reference ID (i.e., returns to the root), which doesn't use the history information of the query process and results in low throughput. To improve the throughput, conference[8] proposed dynamic binary searching tree scheme based on regressive strategy (RDBST), which set up a stack in the reader, and pushes the prefix into the stack in every collision slot. After a tag is identified, the latest prefix shall be popped out to replace the initial reference ID as the reference ID of the next query command. This regressive strategy reduces repeating steps by the stack recording the whole query steps orderly. The total number of slots is reduced from lb(n!)+n to 2n-1 (n is the number of tags).

RDBST scheme greatly reduce the total number of slots by the regressive strategy, thus its throughput is much higher than that of Aloha-based scheme. Furthermore by using variable-length ID, RDBST efficiently reduces the total number of transmitted bits, and improve the transmission efficiency of valid message. Hence, RDBST has much lower communication overhead. However, compared with the Aloha-based schemes, its communication overhead is still high because there are lots of redundant data in each turn of tag identification. Therefore, this paper aims to reduce the redundant data generated in the process of identification. As the above anti-collision schemes shown, the reader groups the collided tags into two subsets and then queries them respectively. Furthermore, the identified prefix is used as the reference ID of query command, which not only increases the communication overhead, but requires all the tag to do the prefix matching after receiving query command. However, using a new responses mode (i.e., Single query with duo responses mode) in our proposed scheme, the collided tags will respond the next query in two subsequent slots according to the |χ| bit in their ID, respectively. Meanwhile, the proposed scheme also eliminates the prefix matching related to query command through a new trigger method (i.e., Counter trigger).

3 A lightweight RFID tags anti-collision scheme based on searching tree

As the survey in Section 2 highlights, there is still a high communication overhead associated with these existing anti-collision schemes. So this paper focused on how to reduce the communication overhead and improve the throughput, and proposed a lightweight anti-collision scheme based on RDBST.

3.1 Methods for how to reduce the communication overhead

1) Single query with duo responses mode: to decrease the number of queries

In the existing searching tree schemes[7-11], the reader first finds the χ in the received ID if collision occurs, and then re-sends a query command with a new prefix. Here, the new prefix in the query consists of a part of the received ID before the χ and a data bit '0'. If the corresponding part of collided tags' ID matches the prefix (i.e., their |χ| bit is '0'), they will respond the query. Due to mismatching the new prefix, the remaining collided tags'ID (i.e., their |χ| bit is '1') must wait for a new query command to give responses. In other words, the collided tags are divided into two subsets by the new prefix, which depends on the |χ| bit in essence. However, there is only one subset able to respond to a query with this prefix. Hence, the query-response mode is called single query with single response. Obviously, the mode in the existing schemes does not make full use of the independent feature of the two tag subsets in terms of ID bit pattern.

To improve the tag identification efficiency of each query command, and further decrease the total number of queries, it require to design a new query-response mode, which is expected that the collided tags can give more than one independent responses for a query.For the purposes, the paper re-defines the part of the received ID preceding the χ as the prefix within query commands. The re-definition can make the corresponding part of all collided tags' ID able to match the prefix, and also make all of collided tags able to give respond once receiving a query. Besides, the paper also re-designs the responding strategy and operation for the collided tags as follows. If the |χ| bit in collided tags' ID is '0', then the tags are required to immediately respond in the current slot. Otherwise, they are required to be delayed a slot and respond in the next slot. The query-response mode is called single query with duo responses mode, which is illustrated by Fig. 1.

Figure 1 An example of single query with duo responses mode

If tag collision occurs in slot 0, the prefix is pushed into stack; otherwise, the reader sends a quiet command and then the identified tag enters the sleep state. If tag collision occurs in slot 1, the collided tags in the slot are queried again; otherwise, the latest prefix shall be popped out and used as the parameter of next query command (i.e., regressive query).

2) Counter trigger: to reduce the total length of query command

As known from the above subsection, the tag can respondonly if its ID matches the prefix of query command. Therefore, the prefix matching plays the key role in deciding whether the tag responds the query command. However, as the reference parameter in query command, the prefix usually takes more bits of query command, which increases the communication overhead in tag identification. By using variable-length ID, the prefix takes up partial tag ID, but it's not enough short yet.

In order to reduce the total length of query command, it is very necessary to shorten the identification parameter in query command. Based on the requirement, the value of |χ| directly replaces the prefix as the identification parameter of query command, and the prefix is re-assigned a new function, i.e., a recorder of collided tag. Besides, a counter is set up in tag to trace the depth of the recorder, and is used as a trigger to respond the next new query command. Its initial value is zero. If tag collision occurs, only the collided tags which counter value is zero can respond the new queries. The other tags which counter value is non-zero must wait for a regressive query command (i.e., de-query) until their counter decrease to zero, and then start a new round of query.

The identification process with counter trigger is illustrated as shown in Fig. 2. Here, the example will present the process from the following key aspects, i.e., when/how to push/pop the ID information of collided tags (i.e., the prefix and the value of |χ|), how to trace the collision event by the counter in the collided tag, and the counter how to trigger the response operations of the collided tag. There are 5 tags with tag ID of 8-bit length in this example.

Figure 2 An illustration of the identification process with counter trigger

Step 1  The reader starts the identification process by sending an initial command. All tags initialize their counter (i.e., C1~C5←0) and then respond. The reader finds the most significant collided bit |χ|=3 in received ID by Manchester decoding.

Step 2  The reader sends a query command, i.e., query(3). The tags with a counter value of zero check the 3th bit in their ID. It is '0' in tag1~3, so they respond in slot0. It is '1' in tag4 and tag5, so they respond in slot1. Tag1~3 collide in slot0, the reader pushes the prefix and the |χ| (i.e., 10110, 2) into the stack, and tag1~3 increase their counters by one (i.e., C1~C3←+1), respectively. Tag4~5 collide in slot1, the reader finds the |χ| (i.e., 0) in received ID.

Step 3  The reader sends a query command, i.e., query(0). Because the value of counters in tag1~3 is 1, so tag1~3 don't respond. In contrast, Tag4~5 respond in slot0 and slot1, respectively. And so they can be identified and then enter sleep state.

Step 4  Because no collision occurs in step 3, the reader pops the latest prefix and the |χ| (i.e., 10110, 2), and then sends a regressive command, i.e., de-query(2). Once received the de-query command, the tags (i.e., tag1~3) are required to decrease their counters by one, and so the counter value of tag1~3 is 0. Tag1~3 respond in slot0 and slot1, respectively. Tag1 is identified in slot0. Tag2~3 collide in slot1, the reader finds the |χ| (i.e., 1) in received ID.

Step 5  The reader sends a query command, i.e., query(1). Tag2~3 respond in slot0 and slot1, respectively. So that they can be identified and then enter sleep state. So far, the stack is null, so the identification process ends.

As shown, the tags can respond only if its counter value is zero. If prefix is pushed into the stack, the counter shall increase by one; if prefix is popped, the counter shall decrease by one.

3.2 The methods for how to improve the throughput

1) Predictive identification: to decrease the total number of slots

In [12], tag ID and its XORed value (i.e., parity-check bit) are reconstructed a new tag ID. Because the parity-check bit is the most significant bit of the new ID, it is always identified firstly. Once it is identified, all the responding tags will have even (or odd) number of '1' in their ID. But there isn't the case of one collided bit in the received ID. Only in the case of two collided bits, the reader can identify two tags by its parity-check bit. This scheme increases the complexity of scheme. In this paper, we adopted an easy predictive identification method as follows. If there is only one collided bit in received ID, the reader could directly identify the two tags. Because the collided bit must be caused by two tags, the bit is either '0' or '1'. For example, if the received ID is 101011X0 (X is the collided bit), the ID of two tags must be 10101100 and 10101110. The predictive identification could also save two slots.

2) Locking technique: to avoid the identified tags colliding with the unidentified tags

In some cases, the reader repeatedly identifies the same tags since these tags always stay in itscommunication range. If the overlapping area has tags, the identified tags still respond and collide with the unidentified tags. In order to prohibit the identified tags from colliding with the unidentified tags, the paper proposed a locking technique working as follows. Each tag reserves a memory area to store the ID of the reader (i.e., RID) when starting the identification, and clear the RID after leaving reader's communication range. When starting tag identification, the reader sends an initial command with RID to the tags nearby. Then the tags interpret themselves as the identified tags if the tags have a matching RID. These identified tags are locked, and enter the sleep state and don't respond. They can get out of the sleep state after leaving reader's communication range. If the storage area is empty, the tags regard themselves as the unidentified tags, and then store the received RID, meanwhile responding with their IDs to the query of reader.

4 Performance evaluation and analysis

The simulation of MATLAB situation is as follows. There is only one reader, and the number of tags in the field of the reader increases from 100 to 1 600. The length of the tag IDs is 16 bits. We consider two scenarios according to the distribution pattern of tag IDs, i.e., Random assignment and sequential assignment. The following metrics[13] are considered in evaluating the efficiency of tag identification, i.e., the total number of queries, the length of query command, the throughput and the communication overhead. From these aspects, we comparatively evaluate the performance of RDBST scheme[8], FST scheme[12] and our proposed scheme LWST. For simplicity, we use the bit-sequence of the reference parameter in the query commands and the transmitted ID bits as the communication overhead without considering the control parameters (e.g., suffixes and check redundancy). The ratio of the total number of slots to the total number of the identified tags is defined as the throughput (u).

As shown in Fig. 3 and Fig. 4, compared with FST scheme, the total number of queries is decreased by half in LWST no matter the allocation of tag IDs. The results show that Single query with duo responses mode decreases the total number of queries by half.

Figure 3 Number of queries (random ID)
Figure 4 Number of queries (sequential ID)

Fig. 5 shows the performance comparison where the prefix andthe |χ| are used as the reference parameter of query command, respectively. The LWST uses the counter as the trigger in response to query, which makes the reference parameter of query command need only the |χ|. The expression of the |χ| needs only lbk bits (k is the length of ID). If the length of ID is doubled, the parameter of query command only needs to increase one bit. However, other schemes use the prefix matching circuit as the trigger, which requires the prefix as the reference parameter of query command. If the length of ID is doubled, the parameter of command would double. The result indicates our proposed scheme significantly reduce the length of query command by using the counter as the trigger in response to query.

Figure 5 Length of query command

As shown in Fig. 6, the throughput of RDBST approaches 50%, which is close to theoretical value: u=n/(2n-1). The throughput of FST and LWST are significantly higher than RDBST. It indicates that the predictive identification improve the throughput by reducing the total number of slots. Fig. 7 shows the case that 16-bit IDs are allocated by sequential assignment. The throughput of RDBST is still 50%. However, the throughput of the other two schemes is close to 1. That indicates the predictive identification could improve the throughput by taking advantage of the allocation of tag IDs. As shown in Fig. 6 and Fig. 7, the throughput curves of FST and LWST almost coincide. That indicates the simple predictive identification of LWST could replace the complex predictive identification of FST.

Figure 6 Throughput (random ID)
Figure 7 Throughput (sequential ID)

Fig. 8 showsthe case that 16-bit IDs are allocated by random assignment, LWST has overall 42% less communication overhead than RDBST, 38% less than FST. Fig. 9 shows the case that 16-bit IDs are allocated by sequential assignment, LWST has overall 69% less communication overhead than RDBST, 39% less than FST. The results show that LWST performs better than other schemes no matter the allocation of tag IDs.

Figure 8 Communication overhead (random ID)
Figure 9 Communication overhead (sequential ID)

The results also prove thatin the sequential assignment of tag IDs experiment, LWST shows better performance. In most cases, tag IDs are assigned sequentially, such as warehouse management, production line, etc. In conferences [14] and [15], they preprocess ID or lock the collided bits before next query, and the locked bits constitute a new ID. In the case of a few tags, the schemes save some transmitted ID bits. While in the case of a large quantity of tags, the amount of the saved bits is the same as LWST. Therefore, those schemes don't win better performance but increase the complexity of the schemes.

5 Conclusions

This paper is aimed primarily at reducing the redundant data generated in the process of identification and proposes alightweight anti-collision scheme based on searching tree. The scheme greatly decreases the total number of queries and reduces the length of query command, thus reducing the communication overhead. In the case of one collided bit in the received ID, the reader can identify two tags by predictive identification, which reduces the total slots and improves the throughput. The analysis on simulation result indicates that LWST scheme performs significantly better than the existing binary tree schemes. It is very suitable for the RFID anti-collision protocol in the case of a large quantity of tags.

References
[1] LIU H C. The Approaches in Solving Passive RFID Tag Collision Problems[M]//Radio Frequency Identification Fundamentals and Applications, Bringing Research to Practice. Cristina Turcu. Shanghai, China: InTech, 2010: 978-953.
[2] MYUNG J, LEE W, SRIVASTAVA J, et al. Tag-splitting: adaptive collision arbitration protocols for RFID tag identification[J]. Parallel and Distributed Systems, IEEE Transactions on , 2007, 18 (6) : 763–775. DOI:10.1109/TPDS.2007.1098
[3] KLAIR D K, CHIN K W, RAADR. A survey and tutorial of RFID anti-collision protocols[J]. Communications Surveys & Tutorials, IEEE , 2010, 12 (3) : 400–421.
[4] FINKENZELLER K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards[M]. N J, USA: Wiley & Sons, 2010 : 194 -211.
[5] SHIH B Y, CHEN C W, CHEN C Y, et al. Merged search algorithms for radio frequency identification anticollision[J]. Mathematical Problems in Engineering , 2012 (2012) : 1–20.
[6] GUTIERREZ A, NICOLALDE F D, INGLE A, et al. High-frequency RFID tag survivability in harsh environments[C]//IEEE International Conference on Rfid. Penang, Malaysia: IEEE, 2013: 58-65. http://ieeexplore.ieee.org/document/6548136/
[7] DONG Y, WICKRAMASINGHE A, XUE H, et al. A novel hybrid powered RFID sensor tag[C]//IEEE International Conference on RFID. San Diego, USA: IEEE, 2015: 55-62. http://ieeexplore.ieee.org/document/7113073/
[8] BUFFI A, D'ANDREA E, LAZZERINI B, et al. UHF-RFID smart gate: Tag action classifier by artificial neural networks[C]//IEEE International Conference on Rfid Technology & Application. [S.l.]: IEEE, 2017: 45-50.
[9] VORA S A, MONGAN W M, ANDAY E K, et al. On implementing an unconventional infant vital signs monitor with passive RFID tags[C]//IEEE International Conference on Rfid. Phoenix, AZ, USA: IEEE, 2017: 47-53. http://ieeexplore.ieee.org/document/7945586/
[10] GENOVESI S, COSTA F, MONORCHIO A, et al. Phase-only encoding for novel chipless RFID tag[C]//Rfid Technology and Applications Conference. Tampere, Finland: IEEE, 2014: 68-71. http://ieeexplore.ieee.org/document/6934202/
[11] BUFFI A, NEPA P, CIONI R. SARFID on drone: Drone-based UHF-RFID tag localization[C]//IEEE International Conference on Rfid Technology & Application. [S.l.]: IEEE, 2017: 40-44.
[12] AMATO F, PETERSON C W, AKBAR M B, et al. Long range and low powered RFID tags with tunnel diode[C]//IEEE International Conference on Rfid Technology and Applications. Tokyo, Japan: IEEE, 2016: 182-187. http://www.mendeley.com/research/long-range-low-powered-rfid-tags-tunnel-diode/
[13] FÉLIX M, PEREIRA F, FERRO V, et al. Using labview to automate RFID tag tests: comparison between implemented system and voyantic test system[C]//2015 IEEE Brasil RFID. Sao Paulo, Brazil: IEEE, 2016: 1-5. http://ieeexplore.ieee.org/document/7523832/
[14] XUE Jianbin, WANG Wenhua, LI Songbai, et al. Anti-collision algorithm based on counting mechanism and multi-state binary[C]//Measuring Technology and Mechatronics Automation (ICMTMA), 2013 Fifth International Conference on. Hong Kong, China: IEEE, 2013: 276-282.. https://ieeexplore.ieee.org/document/6493721
[15] HOTTE D, SIRAGUSA R, TEDJINI S, et al. A new concept of UHF RFID tag for metallic object tracking with embedded cavity[C]//Rfid Technology and Applications Conference. Tampere, Finland: IEEE, 2014: 237-240. https://ieeexplore.ieee.org/document/6934235