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

Redundant RFID Data Removing Algorithm Based on Dynamic-additional Bloom Filter

作　　者：段雯 周良[1] DUAN Wen;ZHOU Liang(School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学》2021年第8期41-46,共6页Computer Science

摘　　要：针对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算法能够在数据量持续上升时保持平稳的低误判率。The high redundancy generated by RFID devices in reading tag information will result in pressure of real-time transmission,waste of storage space and unreliable analysis results of upper application.To slove these problems,a dynamic-additional Bloom filter algorithm(DATRBF)is proposed to remove redundant RFID data.Firstly,combining the characteristics of RFID data and considering the influence of time and reader,the basic Bloom filter(TRBF)is designed.Then,it is decided whether to adjust or add additional TRBF dynamically according to the change of data amount in a fixed time interval,and the misjudgment rate is controlled within the threshold by expanding bit array with additional TRBF.Finally,combining the two filters to judge whe-ther the data is redundant or not.The experiment proves that the DATRBF algorithm has obvious advantages over the traditional Bloom filter(BF)and temporal-spatial Bloom filter(TSBF)when filtering the redundant data stream of RFID.When the data amount fluctuates randomly,the misjudgment rate of DATRBF is about 49%of that of TSBF on average,and the DATRBF algorithm can maintain a stable and low misjudgment rate when the data amount continues to rise.

关 键 词：布隆过滤器 RFID 冗余数据 动态附加 误判率 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]