Multi-branch query tree protocol for solving RFID tag collision problem

The technology of anti-collision is a key point in radio frequency identification （RFID） system. To avoid data collision, there are two approaches： ALOHA based algorithm and binary tree （BT） based algorithm. However, these cannot solve the collision problem completely, especially when the tag quantity is big and the tag ID is long. In this article, we present a multi-branch query tree （MBQT） protocol based on balanced incomplete block design （BIBD） code, and use 16-bit vectors derived from the BIBD as query prefix symbols of RFID reader. Compared with the conventional anti-collision algorithm, the theoretic analysis and simulation show that the proposed protocol improves the identification efficiency.     

ASAF ALOHA Protocol for Dense RFID Systems

RFID tags are used for varied applications in large numbers. Human Tracking is one such important application wherein the RFID system detects the presence of a tag in a dense tag environment. Quick estimation of the number of tags in the field at a desired level of accuracy is one of the most common requirements in the present scenario. Identification of tags has become a critical area which need more time and unsuitable in many situations; especially where tag set is dense. We introduce a novel medium access control (MAC) protocol for Radio Frequency IDentification (RFID) systems which exploits the statistical information collected at the reader. The protocol, termed Adaptive Slot Adaptive Frame (ASAF) ALOHA protocol, is motivated to significantly improve the total read time performance of the currently suggested MAC protocols for RFID systems by minimizing the collisions of the tags. In order to perform this task, ASAF estimates the dynamic tag population and adapts the frame size and number of slots simultaneously in the subsequent round via a simple policy that maximizes an appropriately defined function. We demonstrated that ASAF is better than the current RFID MAC protocols. We also considered the case where suddenly if the number of tags increases, the running frame with adapted slots gets flushed away and new frame with increased number of slots gets adapted automatically by the system showing the robustness in this case as well.     

分组自适应分配时隙的RFID防碰撞算法研究

为了解决射频识别(Radio Frequency IDentification,RFID)系统中的多标签防碰撞问题,在分析帧时隙ALOHA算法的基础上,提出一种基于分组自适应分配时隙的RFID防碰撞算法(GAAS).首先让阅读器对标签随机所选的时隙进行扫描统计,并将其发送给每一个标签,标签再进行相应地时隙调整,使阅读器跳过空闲时隙和碰撞时隙,自适应地分配有效时隙,进而对标签进行快速识别.当未识别标签数比较大时,算法采用分组以及动态调整帧长等策略,以减少时隙处理的时间.仿真结果表明:GAAS算法提高了系统的识别效率和稳定性,降低了传输开销.特别是当标签数超过1000时,该算法的吞吐率仍保持在71%以上,比传统的帧时隙ALOHA-256算法和分组动态帧时隙ALOHA算法的系统效率分别提高了300%和97.2%.     

改进型帧时隙ALOHA防碰撞算法研究

为进一步提高RFID系统中电子标签防碰撞算法的识别效率,对帧时隙ALOHA防碰撞算法的性能进行分析,提出一种结合精确标签估计和二进制搜索的改进型帧时隙ALOHA算法.将识别过程分为标签估计和标签识别两个阶段,在标签估计算法中引入碰撞概率上、下限参数,并精确估计标签数量对初始帧时隙大小进行优化;在标签识别阶段,利用二进制搜索算法对时隙内的碰撞标签进行快速识别.通过对识别过程进行仿真结果表明:改进的算法改善了防碰撞性能,提高了RFID系统的标签识别效率.     

Energy-Aware Tag Anticollision Protocols for RFID Systems

Energy consumption of portable RFID readers is becoming an important issue as applications of RFID systems pervade many aspects of our lives. Surprisingly, however, these systems are not energy-aware with the focus till date being on reducing the time to read all tags by the reader. In this work, we consider the problem of tag arbitration in RFID systems with the aim of designing energy-aware anticollision protocols. We explore the effectiveness of using multiple time slots per node of a binary search tree through three anticollision protocols. We further develop an analytical framework to predict the performance of our protocols and enable protocol parameter selection. We demonstrate that all three protocols provide significant energy savings both at the reader and tags (if they are active tags) compared to the existing Query Tree protocol, while sharing the deterministic property of the latter. Further, we show that our protocols provide similar benefits even with correlated tag IDs.     

A new anti‐collision protocol based on information of collided tags in RFID systems

Radio frequency identification (RFID) technology has recently become an integral part of a wide range of applications. One of the challenges in RFID systems is the tag anti‐collision issue, for which several anti‐collision tag identification protocols have been proposed. This paper proposes a novel slotted ALOHA‐based RFID tag anti‐collision algorithm which can be employed for tag identification. The main idea of this algorithm is to use the information available in collision slots, called collided data, to identify tags uniquely. For this purpose, the collision slots that include only two tags are selected. Then, the non‐conflict bits in these slots are used to possibly identifying the tags. Because in the proposed algorithm readers use both single slots and also the collision slots for tag identification, the performance is increased significantly compared with other protocols. Results of the study indicate that in the proposed algorithm, the optimal frame size for an individual tag number is equal to the half of tags number and the efficiency of the proposed protocol is improved to about 73%. Copyright © 2015 John Wiley & Sons, Ltd.     

基于比特查询的多进制树标签防碰撞识别协议

多标签碰撞问题被认为是射频识别系统中的一个关键问题.近来,许多基于比特追踪技术的查询树算法被提出用于有效的解决标签碰撞问题,然而由于无用的碰撞比特信息和空闲时隙的存在,这些查询树算法的性能都有待进一步提升.本文提出了一种基于比特查询的查询方法,该算法使得标签返回一个映射过比特串来取代原始的ID序列.同传统的ID查询相比较,比特查询不仅可以消除空闲查询还可以将碰撞标签分成更多子集并充分利用碰撞比特信息.基于该比特查询方法,我们提出了一种基于比特查询的多进制树（Bit query based M-ary tree,BQBMT）新型查询树算法,它通过多进制树迭代的分离碰撞,并通过比特查询模式和ID查询模式之间的最佳切换来快速识别标签.理论分析和仿真结果显示,BQBMT算法的的系统效率接近0.89,超过了现有的QT算法和混合防碰撞算法.     

Adaptive Binary Splitting: A RFID Tag Collision Arbitration Protocol for Tag Identification

In the RFID system, a reader recognizes tags through communications over a shared wireless channel. When multiple tags transmit their IDs at the same time, the tag-to-reader signals lead to collision. Tag collision arbitration for passive RFID tags is significant for fast identification since collisions disturb the reader's identification process. This paper presents an Adaptive Binary Splitting (ABS) protocol which is an improvement on the binary tree protocol. To reduce collisions and identify tags efficiently, ABS uses information which is obtained from the last processes of tag identification. Our performance evaluation shows that ABS outperforms other tree based tag anti-collision protocols. This work was supported by Korea Research Foundation Grant (KRF-2005-041-D00680).     

多枝查询树协议在解决射频识别碰撞问题中的应用

数据碰撞是影响射频识别(RFID)系统识别效率的主要因素。目前,常用的防碰撞算法是ALOHA算法和二进制树搜索算法,但这两类算法都还不能完全解决标签碰撞问题,尤其是当待识别的标签数量较大且标签ID序列号较长时,识别速度相当慢。为此提出一种多枝查询树协议,采用均衡不完全区组设计(BIBD)对标签ID进行编码,并用16位的BIBD码作为读写器查询前缀符号。理论分析和仿真结果表明,这种协议的性能较传统的防碰撞协议有明显改善。     

可并行识别的分组动态帧时隙ALOHA标签防碰撞算法

该文针对现有动态帧时隙ALOHA标签防碰撞算法的系统吞吐率低、算法效率低等问题,提出一种可并行识别的分组动态帧时隙ALOHA(PIGDFSA)标签防碰撞算法。该文以实验为基础,探索了待识别标签数、标签分组数、帧长对系统吞吐率与标签碰撞率的影响,研究了提升系统吞吐率与降低标签碰撞率的策略与方法。结合射频识别(RFID)的多天线系统,引入FastICA技术,从而实现碰撞时隙重新定义,并以此为基础,利用未识别标签数目自适应确定分组数与帧长。仿真结果表明:PIGDFSA算法在标签数达到2000时,算法吞吐率仍能稳定在92%以上,与FSA-256, GDFSA, BSDBG等算法相比具有更高的算法吞吐率,更少的空隙时隙,更高的算法效率。     

基于模运算标签分类的RFID标签防碰撞识别方法

为了解决射频识别(RFID)系统中的多标签防碰撞问题,在分析帧时隙ALOHA算法的基础上,提出一种基于模运算标签分类的RFID标签防碰撞识别方法。引入一种检测信息碰撞的时隙选择信息,对标签所选取时隙的碰撞情况进行分析并估计标签数量;然后对标签EPC编码进行逐级的取模运算,将同余的标签归为一组。各个标签经过K次取模运算后,分为2k组,每组只有发生少量碰撞位的标签。再将标签按照分组对应的时隙发送,碰撞标签采用二叉树后退式算法处理。本方法极大的提高了标签的识别效率,适用于射频识别系统中阅读器对于大量电子标签的快速识别。     

基于分组动态帧时隙ALOHA防碰撞算法研究

为解决射频识别系统中多标签防碰撞问题,在现有ALOHA算法的基础上提出了一种改进的分组动态帧时隙ALOHA算法。当大量标签同时进入阅读器识别范围内时,算法通过设置一个阈值把要响应的标签分成两组,符合条件的一组去响应阅读器,不符合条件的暂时不响应,该算法通过分组限制响应标签数量达到较高的识别效率。仿真结果表明,该算法在标签数大于256甚至更多时识别效率也能维持在相对较高的数值。     

一种基于不等长时隙的射频识别防碰撞算法

该文提出了一种基于不等长时隙的射频识别(Radio Frequency Identification, RFID)动态帧时隙ALOHA (Dynamic Framed-Slotted ALOHA, DFSA)防碰撞算法。算法考虑到大量碰撞时隙和空闲时隙对系统效率的影响,采用帧内时隙长度不等的优化策略,由时隙优化参数和未读标签数确定帧长,通过优化的切比雪夫不等式法进行标签估计,并基于马尔科夫链分析标签识别过程,来实现读取周期的控制。分析和仿真结果表明,该算法比时隙优化前的DFSA算法效率更高,平均识别时间更短,标签数估计比下限值法、Schoute法和碰撞率法更准确。     

Enhanced energy-saving anticollision algorithms with improving throughput for RFID system

Tag collision algorithm is a key issue for energy saving and throughput with Radio Frequency IDentification (RFID) system more popular in sensing infrastructure of covering wider area on a large scale. Exploiting low energy consumption strategy would enable longer operational life of tags and reader with battery energy supply. And improving throughput is required on a large scale to preserve the capability of the correct reception. Therefore, this paper proposes an enhanced anti-collision algorithm called Dynamic Slotted with Muting (DSM), which uses multiple slots within a frame per node in a binary tree and takes tag estimation function to optimize the number of slots, and adds a mute command to put identified tags silence. The performance of the proposed algorithm is analytically provided, and simulation results show that DSM saves more than 40% energy consumptions both at reader and tags, and improves more than 35% throughput compared to the existing algorithms. Thus our algorithm is demonstrated to perform efficient energy savings at reader and tags with throughput improvement.     

CDMA-based anti-collision algorithm for EPC global C1 Gen2 systems

Frame slotted ALOHA protocol as a key technology to improve system throughput has been widely applied to modern radio frequency identification systems. In this paper, a novel frame slotted ALOHA collision arbitration protocol based on code division multiple access has been proposed. The main aim of the proposed algorithm is to avoid collisions between multiple tags. In the scheme, an orthogonal sequence is used as the means to distinguish the transmitted data from different tags within the same time slot and frequency band. The theoretical analysis and simulation results proved that the performance of our proposed algorithm outperforms the existing ALOHA-based protocols.     

Instant collision resolution for tag identification in RFID networks

In this paper, we approach the problem of identifying a set of objects in an RFID network. We propose a modified version of Slotted Aloha protocol to reduce the number of transmission collisions. All tags select a slot to transmit their ID by generating a random number. If there is a collision in a slot, the reader broadcasts the next identification request only to tags which collided in that slot. Besides, we present an extensive comparative evaluation of collision resolution protocols for tag identification problem in RFID networks. After a quick survey of the best performing RFID tag identification protocols, both deterministic and probabilistic, we present the outcome of intensive simulation experiments set up to evaluate several metrics, such as the total delay of identification process and the bit complexity of reader and tags. The last metric is strictly related to energy constraints required by an RFID system. The experiments point out that our protocol outperform all the other protocols in most cases, and matches them in the others.     

无后台服务器的射频识别标签安全查询协议

在许多射频识别(RFID)应用中,经常需要在多个标签中确定某个特定标签是否存在。在这种环境下,标签查询协议必不可少。然而,已有的协议要么存在安全漏洞,要么查询效率低下。利用Hash函数和时间戳,提出一个无后台服务器的RFID标签查询协议。GNY逻辑被用于证明新协议的正确性。分析显示提出的协议可以高效的实现特定标签的查询,且能够抵抗一些主要攻击,实现对标签隐私的保护。     

无源RFID自适应帧时隙防碰撞算法研究

射频识别RFID作为一种重要的物联网终端数据采集技术,系统的吞吐率直接影响着数据采集终端的性能,但目前广泛应用于无源RFID系统的帧时隙类防碰撞算法吞吐率普遍较低.本文着重分析了影响无源RFID帧时隙类ALOHA防碰撞算法性能两类因素：帧长和碰撞时隙的处理方式,通过构建和求解帧长调整和标签碰撞的数学模型,给出了无源RFID帧时隙类ALOHA防碰撞算法的具体优化途径和方案：帧长自适应调整和碰撞实时散列.在此基础上提出了自适应二进制散列帧时隙ALOHA防碰撞算法-ABSFSA.实验结果表明ABSFSA算法在同等条件下可以有效减少无效时隙,明显将RFID系统的吞吐率稳定提高到45%.本文的研究工作为无源RFID帧时隙类防碰撞算法的优化提供了可供参考的数学模型,同时对提升物联网数据采集终端的性能具有一定的应用价值.     

Probabilistic Dynamic Framed Slotted ALOHA for RFID Tag Identification

In this paper, we study radio frequency identification tag identification problems using framed slotted ALOHA protocol. Each tag will be assumed to participate in the contention with a certain probability. Then, the frame size and the probability will be dynamically controlled by the reader in every reading round so that all the tags can be detected in a short period of time. Moreover, we propose a practical way of controlling the probability in terms of transmit power control, assuming Additive White Gaussian Noise channel or flat Rayleigh fading channel. Computer simulation results demonstrate the effectiveness of the proposed method.     

Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems

Dynamic Framed-Slotted ALOHA (DFSA) is one of the most popular algorithms to resolve tag collision in RFID systems. In DFSA, it is widely known that the optimal performance is achieved when the frame size is equal to the number of tags. So, a reader dynamically adjusts the next frame size according to the current number of tags. Thus it is important to estimate the number of tags accurately. In this paper, we propose a novel tag estimation method for DFSA. We compare the performance of the proposed method with those of other existing methods. And, simulation results show that our scheme improves the accuracy of tag estimation and the speed of tag identification.