基于动态附加布隆过滤器的RFID数据冗余处理算法

针对RFID设备在读取标签信息时产生的高度冗余会造成实时传输压力、存储空间浪费和上层应用分析结果不可靠等问题,提出一种动态附加布隆过滤器算法(Dynamic-Additional Bloom Filter,DATRBF)来清除RFID冗余数据.首先结合RFID动态数据流特点,利用时间和阅读器因素的影响设计了基础布隆过滤器(Time-Reader Bloom Filter,TRBF),然后根据定时间区间内数据量变化动态决定是否调整或附加额外的TRBF,通过附加TRBF从而扩充数组的方式将误判率控制在阈值内,最后结合两个过滤器对数据是否冗余进行综合判断.实验证明,在过滤RFID实时动态数据流中的冗余数据时,DATRBF算法相比传统布隆过滤器(Bloom Filter,BF)和时空布隆过滤器(Temporal-Spatial Bloom Filter,TSBF)有明显的优势,在数据量随机波动时DATRBF的误判率平均约为TSBF的49％,且DATRBF算法能够在数据量持续上升时保持平稳的低误判率.     

基于 BIoom fiIter 的 RFID 中间件数据过滤算法研究

有效地减少 RFID 系统中冗余阅读器或天线采集到的大量重复数据,可以降低系统能耗和提高处理效率。经研究,提出采用改进的布隆过滤器（Bloom filter）对 RFID 采集数据进行去重过滤,并运用到中间件系统中。改进的 Bloom filter 主要将两个标准的 Bloom filter 组成二维并行 Bloom filter,对 RFID 采集数据所包含的两个属性值 tagID 和 readerID 进行并行过滤。经实验可见,标准 Bloom filter 与哈希过滤（hash filter）相比具有明显的优势,对其改进后,采用二维并行 Bloom filter 在误判率、吞吐率和存储空间上具有更高的系统性能。     

基于Bloom filter的RFID中间件数据过滤算法研究

有效地减少RFID系统中冗余阅读器或天线采集到的大量重复数据,可以降低系统能耗和提高处理效率。经研究,提出采用改进的布隆过滤器(Bloom filter)对RFID采集数据进行去重过滤,并运用到中间件系统中。改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tag ID和reader ID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的优势,对其改进后,采用二维并行Bloom filter在误判率、吞吐率和存储空间上具有更高的系统性能。     

RFID数据流过滤算法研究

RFID在实时识别、定位、跟踪以及物理对象监控等方面有着广泛的应用前景.为了实现上述应用的目标,RFID数据必须经过采集、过滤等处理过程.采集的原始RFID数据包括噪音数据和冗余数据,只有将这些噪音数据和冗余数据过滤后,才能应用;另外,保证正确的RFID标签数据采集顺序,对于一些应用也非常关键.针对这些问题,提出了基本噪音过滤算法和基于hashtable的有序噪音过滤算法,以及基本冗余过滤算法和基于hashtable的冗余过滤算法,并通过仿真实验验证了该方法的有效性.     

基于有限状态机的RFID流数据过滤与清理技术

为了实现从大量不可靠、冗余的RFID（radio frequency identification）流数据中提取有效信息,提高RFID系统中数据的质量,提出了一种基于有限状态机的RFID 流数据过滤与清理方法.实验结果表明：该方法能够有效过滤系统外标签数据,清理系统内部冗余标签数据,筛选有效标签数据,并能够降低漏读、误读带来的风险.最后,利用地理信息系统的可视化技术,将过滤与清理结果展示在地图上.     

可验证布隆过滤器:加速区块链中的不存在查询与证明

传统基于区块链的“真实存储”系统在过滤“无效查询请求”时忽略了提供“不存在证明”,恶意节点可以随时对指定用户发动拒绝服务攻击.本文提出了可验证布隆过滤器的一种构建方式,基于布隆过滤器快速过滤无效查询请求的同时能有效提供证据证明数据不存在;此外,针对证明过程中可能造成的隐私泄露问题,本文提出了“隐秘的可验证布隆过滤器”和“数据混淆”两种方式,前者确保每个“不存在证明”只会泄露布隆过滤器的一位置零位,减少了数据泄露量;后者则是在前者的基础上进一步降低用户从泄露的布隆过滤器中推测出真实内容准确率.实验数据表明,当无效查询请求量占比为35%时,读取性能提升大约30%;当无效查询请求量占比为95%时,读取性能可提升十倍以上.     

帧时隙ALOHA的快速防冲突算法

标签防冲突算法是影响RFID系统效率的关键。目前基于帧时隙Aloha算法的改进算法主要是调整识别过程中的帧长,但都存在着帧长计算不准确、算法复杂和识别时间长的缺点。提出了一种新的防冲突算法,该算法将一个识别周期分为标签检测和数据读取两个步骤,充分利用标签检测的冲突信息,提高数据读取的效率,减少了识别的时间,提高了识别率。理论分析和仿真结果均表明,该算法可以更加高效快速地识别标签,特别适用于标签数目较多的场合。     

基于单哈希计数布隆的DDS自动发现算法

针对DDS简单自动发现算法中网络传输量大、内存消耗高以及端点匹配时间长的问题,提出一种基于单哈希计数布隆过滤器的DDS自动发现算法——SDP＿OHCBF。通过将标准布隆过滤器升级为计数布隆过滤器以支持元素删除操作,使用单个哈希函数和取模运算代替标准布隆过滤器中的多个哈希运算,加快布隆过滤器的元素查询过程。仿真验证结果表明,该算法降低了DDS自动发现过程的网络传输量与内存消耗,支持元素删除操作,提高了数据发布/订阅的实时性。     

面向仓储管理的RFID数据过滤模型研究

高冗余度的RFID原始数据制约了RFID技术的大规模应用。为了能够筛选出有效数据,提出一种面向仓储管理的RFID数据过滤模型。分析仓储管理系统中标签冗余和阅读器冗余的产生原因,给出解决这两种冗余的数据过滤模型,同时详细介绍了该模型的具体步骤。     

基于多维布隆过滤器的模式匹配引擎

针对传统的模式匹配引擎不具备完整报文检测功能的问题和出现的速度瓶颈,提出了基于FPGA实现的多维布隆过滤器解决方案,设计了能够同时检测报头和有效负载的多模式匹配引擎。引擎使用多维布隆过滤器过滤出可疑报文,由位拆分状态机进行精确匹配。分析和试验结果表明：与传统方法相比,基于多维布隆过滤器的模式匹配引擎可以并行检测报头和报文内容,在降低过滤器误判率的同时,有效提高了引擎的吞吐量。     

An approximate duplicate elimination in RFID data streams

The RFID technology has been applied to a wide range of areas since it does not require contact in detecting RFID tags. However, due to the multiple readings in many cases in detecting an RFID tag and the deployment of multiple readers, RFID data contains many duplicates. Since RFID data is generated in a streaming fashion, it is difficult to remove duplicates in one pass with limited memory. We propose one pass approximate methods based on Bloom Filters using a small amount of memory. We first devise Time Bloom Filters as a simple extension to Bloom Filters. We then propose Time Interval Bloom Filters to reduce errors. Time Interval Bloom Filters need more space than Time Bloom Filters. We propose a method to reduce space for Time Interval Bloom Filters. Since Time Bloom Filters and Time Interval Bloom Filters are based on Bloom Filters, they do not produce false negative errors. Experimental results show that our approaches can effectively remove duplicates in RFID data streams in one pass with a small amount of memory.     

Distributed load-balancing algorithm for fast tag reading

The radio frequency identification (RFID) technology has gained a lot of recent interests because it has been widely recognised as a foundation technology for the ‘Internet of things’. In current multi-reader RFID systems, readers work with fairly less cooperation and are responsible to retrieve data from different number of tags individually, which results in large reading time of obtaining all tag data. In this paper, a fast tag reading problem in multi-reader RFID systems with the goal of obtaining all tag data by using minimum reading time is studied. A distributed load-balancing algorithm based on diffusion method is proposed to solve the problem by migrating tags from highly loaded reader to lightly loaded reader. The simulation results demonstrate the effectiveness and efficiency of proposed algorithm.     

改进的基于堆栈存储的二进制搜索算法

针对无线射频识别(RFID）系统中的标签防碰撞问题,详细分析典型的二进制算法、动态二进制算法及后退式二进制算法的原理,同时考虑识别次数和传输位数这两方面的性能,提出了一种快速高效的防碰撞算法。通过对标签进行预处理以及在阅读器中设置堆栈,有效地减少碰撞算法中的识别次数和传输冗余信息。仿真结果表明该算法在次数效率和位数效率性能上有较大的提高。     

Efficient tag detection in RFID systems

Recent technological advances have motivated large-scale deployment of RFID systems. However, a number of critical design issues relating to efficient detection of tags remain unresolved. In this paper, we address three important problems associated with tag detection in RFID systems: (i) accurately detecting RFID tags in the presence of reader interference (reader collision avoidance problem); (ii) eliminating redundant tag reports by multiple readers (optimal tag reporting problem); and (iii) minimizing redundant reports from multiple readers by identifying a minimal set of readers that cover all tags present in the system (optimal tag coverage problem). The underlying difficulties associated with these problems arise from the lack of collision detection mechanisms, the potential inability of RFID readers to relay packets generated by other readers, and severe resource constraints on RFID tags. In this paper we present a randomized, distributed and localized Reader Collision Avoidance (RCA) algorithm and provide detailed probabilistic analysis to establish the accuracy and the efficiency of this algorithm. Then, we prove that the optimal tag coverage problem is NP-hard even with global knowledge of reader and tag locations. We develop a distributed and localized Redundant Reader Elimination (RRE) algorithm, that efficiently identifies redundant readers and avoids redundant reporting by multiple readers. In addition to rigorous analysis of performance and accuracy, we provide results from elaborate simulations for a wide range of system parameters, demonstrating the correctness and efficiency of the proposed algorithms under various scenarios.     

一种改进的二进制查询树RFID标签防碰撞算法

在射频识别（RFID）系统中,存在阅读器与多个标签同时通信的碰撞问题,标签防碰撞技术是解决标签碰撞问题、提高标签识别效率的关键技术。在阐述传统二进制查询树算法（QT）的基础上提出了一种改进的查询树标签防碰撞算法-动态二进制查询树算法（DQT）。该算法通过曼彻斯特编码,识别出碰撞位,从而动态改变查询前缀,使阅读器的查询次数与标签的通信量大大减少,提高了标签的识别效率。仿真实验表明,DQT算法在大量标签识别场合下比QT算法更具有效性和稳定性。     

一种用于UHF RFID系统循环冗余校验的新算法

基于ISO18000—6C协议标准的UHFRFID系统中的读写器和标签之间的通信,采用CRC5和CRC16循环冗余校验。目前UHFRFID系统中,收发数据的循环冗余校验都采用按位校验法,本文根据已有的循环冗余查表校验法,提出一种适用于ISO18000—6C协议标准的新型循环冗余校验算法,极大地提高了循环冗余校验效率,非常适合用于嵌入式实时系统通信。实验结果表明,该算法将CRC5校验的效率提高了17％,将CRC16校验的效率提高了27％以上。     

A power control technique for anti-collision schemes in RFID systems

The emerging technology of Radio Frequency IDentification (RFID) has enabled a wide range of automated tracking and monitoring applications. However, the process of interrogating a set of RFID tags usually involves sharing a wireless communication medium by an RFID reader and many tags. Tag collisions result in a significant delay to the interrogation process, and such collisions are hard to overcome because of the limited capabilities of passive RFID tags and their inability to sense the communication medium. While existing anti-collision schemes assume reading all tags at once which results in many collisions, we propose a novel approach in which the interrogation zone of an RFID reader is divided into a number of clusters (annuli), and tags of different clusters are read separately. Therefore, the likelihood of collisions is reduced as a result of reducing the number of tags that share the same channel at the same time.In this paper, we consider two optimization problems whose objective is minimizing the interrogation delay. The first one aims at finding the optimal clustering scheme assuming an ideal setting in which the transmission range of the RFID reader can be tuned with high precision. In the second one, we consider another scenario in which the RFID reader has a finite set of discrete transmission ranges. For each problem, we present a delay mathematical analysis and devise an algorithm to efficiently find the optimal number of clusters. The proposed approach can be integrated with any existing anti-collision scheme to improve its performance and, hence, meet the demand of large scale RFID applications. Simulation results show that our approach makes significant improvements in reducing collisions and delay.     

Indoor robot localization based on single RFID tag

With the mature of the RFID technology and the wide use of the Internet of Things technology, it is a new research hotspot that RFID technology was applied to robot localization and navigation. RFID tags have the characteristic of storing information, long reading distance and using conveniently. A novel robot localization method combining RFID with laser data is proposed in this paper. When the robot detects an RFID tag, RFID antenna angle probability model is determined based on the fuzzy reasoning algorithm. Then the Bayes rule is used to estimate the direction of the robot. Finally, the robot global localization is realized by fusion of the laser ranging data. The experimental results showed that the precision of the positioning based on single RFID tag is enhanced greatly by combining laser detecting data.     

快速检测RFID复制标签的算法研究

针对大型的RFID系统中使用标签ID无法识别具体复制标签的问题,提出了一种快速检测复制标签的CTDA算法。首先,标签内存储[k]个哈希函数,标签在接收到阅读器的查询帧后多次回复阅读器构造虚拟克鲁姆过滤器,找到阅读器通信区域内的标签集合[M];然后,[M]中标签通过多轮哈希运算使得阅读器构建时隙状态向量,目的是给每个标签分配单一时隙;最后,标签向阅读器回复10 bit信息,阅读器通过检测各个时隙是否由单一时隙变成冲突时隙来判断标签是否受到复制。经过仿真分析,证明该算法在执行时间上优于Bu K提出的GREAT算法和Qiao Yan提出的轮询协议RIP算法。     

基于滑动窗口的RFID自适应数据清洗算法

RFID（射频识别）标签阅读器对操作环境的敏感性很高,导致其产生的RFID数据流不可靠,并含有大量的漏读,因此必须要对原始数据进行清洗。设计基于滑动窗口的自适应数据清洗算法,算法使用滑动窗口技术和二项分布模型计算合适的窗口大小,通过窗口子区间的监测结果和标签的状态来动态调整窗口大小。结果显示,在移动环境下本算法比SMURF算法产生的平均错误数少,性能更加优越,准确率和稳定性都有明显提高。 