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

doi:10.11896/jsjkx.200700093

摘要/Abstract

摘要： 针对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算法能够在数据量持续上升时保持平稳的低误判率。

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

Abstract: 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.

Key words: Bloom filter, Dynamic additional, Misjudgment rate, Redundant data, RFID

中图分类号:

TP391

段雯, 周良. 基于动态附加布隆过滤器的RFID数据冗余处理算法[J]. 计算机科学, 2021, 48(8): 41-46. https://doi.org/10.11896/jsjkx.200700093

DUAN Wen, ZHOU Liang. Redundant RFID Data Removing Algorithm Based on Dynamic-additional Bloom Filter[J]. Computer Science, 2021, 48(8): 41-46. https://doi.org/10.11896/jsjkx.200700093

参考文献

[1]CAO W,JIANG P Y,LU P,et al.Real-time data-driven monitoring in job-shop floor based on radio frequency identification[J].International Journal of Advanced Manufacturing Technology,2017,92(5/6/7/8):2099-2120.
[2]CAO W,JIANG P Y,JIANG K Y,et al.Radio frequency identification-based real-time data collecting and visual monitoring for discrete manufacturing workshop[J].Computer Integrated Manufacturing Systems,2017,23(2):273-284.
[3]KAMALUDIN H,MAHDIN H,ABAWWAJY J H,et al.Filtering Redundant Data from RFID Data Streams[J].Journal of Sensors,2015,2016:1-7.
[4]MA M,WANG P,CHU C H.Redundant Reader Elimination in Large-Scale Distributed RFID Networks[J].IEEE Internet of Things Journal,2018,5(2):884-894.
[5]LIAO G Q,ZHOU J,HUI N,et al.Approximately Filtering Redundant Data for Uncertain RFID Data Streams[C]//IEEE International Conference on Mobile Data Management.IEEE,2017.
[6]LIU L L,YUAN Z L,LIU X W,et al.RFID unreliable data filtering by integrating adaptive sliding window and Euclidean distance[J].Advances in Manufacturing,2014,2(2):121-129.
[7]YOUSIF A,KAFAFY A,ABDLKADER H M.Reducing RFID Data Uncertainty using Mean Field Variational Inference[C]//2018 14th International Computer Engineering Conference (ICENCO).2018:131-136.
[8]LIN Q M,XIAO Y,YE N,et al.A method of cleaning RFID data streams based on Naive Bayes classifier[J].International Journal of Ad Hoc & Ubiquitous Computing,2016,21(4):237.
[9]MAHDIN H.A Review on Bloom Filter Based Approaches for RFID Data Cleaning[C]//First International Conference on Advanced Data and Information Engineering.2014:79-86.
[10]BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].IPSJ Magazine,1970,12(7):422-426.
[11]MOUSAVI N,TRIPUNITARA M.Constructing CascadeBloom Filters for Efficient Access Enforcement[J].Computers &Security,2019,81:1-14.
[12]REVIRIEGO P,MARTINEZ J,PONTARELLI S.CFBF:Re-ducing the Insertion Time of Cuckoo Filters with an Integrated Bloom Filter[J].IEEE Communications Letters,2019,23(10):1857-1861.
[13]LU J,YANG T,WANG Y,et al.Low Computational CostBloom Filters[J].IEEE/ACM Transactions on Networking,2018,26(5):2254-2267.
[14]KLEYKO D,RAHIMI A,GAYLER R W,et al.AutoscalingBloom Filter:Controlling Trade-off Between True and False Positives[J].Neural Computing & Applications,2020,32:3675-3684.
[15]LEE C H,CHUNG C W.An approximate duplicate elimination in RFID data streams[J].Data & Knowledge Engineering,2011,70(12):1070-1087.
[16]WANG Y L,WANG C,JIANG X H,et al.RFID duplicate removing algorithm based on temporal-spatial Bloom filter[J].Journal of Nanjing University of Science and Technology,2015(3):253-259.
[17]ZHU W L.Warehouse Package Longitudinal Positioning Based on RFID Data Redundancy Cleaning and Clustering[D].Chongqing:Chongqing University,2017.
[18]HUANG W Q,ZHANG Y F,CAO Z W,et al.Redundant RFID Data Filtering Algorithm Research Based on Bloom Filter[J].Journal of Cyber Security,2019,4(3):93-105.
[19]GUO D,WU J,CHEN H,et al.Theory and Network Applica-tions of Dynamic Bloom Filters[C]//Proceedings IEEE INFOCOM 2006,25th IEEE International Conference on Computer Communications.IEEE,2006:2849-2860.
[20]XIE K,MIN Y H,ZHANG D F,et al.A Scalable Bloom Filter for Membership Queries[C]//IEEE Global Telecommunications Conference.IEEE,2007:543-547.

相关文章 15

[1]	罗文聪, 郑嘉利, 全艺璇, 谢孝德, 林子涵. 基于改进型多目标樽海鞘群算法的RFID阅读器天线优化部署 Optimized Deployment of RFID Reader Antenna Based on Improved Multi-objective Salp Swarm Algorithm 计算机科学, 2021, 48(9): 292-297. https://doi.org/10.11896/jsjkx.200700167
[2]	李丽, 郑嘉利, 罗文聪, 全艺璇. 基于近端策略优化的RFID室内定位算法 RFID Indoor Positioning Algorithm Based on Proximal Policy Optimization 计算机科学, 2021, 48(4): 274-281. https://doi.org/10.11896/jsjkx.200300028
[3]	刘嘉琛, 秦小麟, 朱润泽. 基于LSTM-Attention的RFID移动对象位置预测 Prediction of RFID Mobile Object Location Based on LSTM-Attention 计算机科学, 2021, 48(3): 188-195. https://doi.org/10.11896/jsjkx.200600134
[4]	徐鹤, 吴满星, 李鹏. 基于ARIMA模型的RFID室内相对位置定位算法 RFID Indoor Relative Position Positioning Algorithm Based on ARIMA Model 计算机科学, 2020, 47(9): 252-257. https://doi.org/10.11896/jsjkx.200400038
[5]	李丽,郑嘉利,王哲,袁源,石静. 基于异步优势动作评价的RFID室内定位算法 RFID Indoor Positioning Algorithm Based on Asynchronous Advantage Actor-Critic 计算机科学, 2020, 47(2): 233-238. https://doi.org/10.11896/jsjkx.190100070
[6]	侯培国, 王志轩, 严晨. 基于RFID标签的防碰撞算法改进 Improvement of Anti-collision Algorithm Based on RFID Tag 计算机科学, 2019, 46(11A): 359-362.
[7]	李璐璐, 董庆宽, 陈萌萌. 基于云的轻量级RFID群组标签认证协议 Cloud-based Lightweight RFID Group Tag Authentication Protocol 计算机科学, 2019, 46(1): 182-189. https://doi.org/10.11896／j.issn.1002-137X.2019.01.028
[8]	杨子薇, 郑嘉利, 岳世彬, 袁源, 石静. 基于标签分组的新型Q值防碰撞算法 New Q Value Anti-collision Algorithm Based on Label Grouping 计算机科学, 2018, 45(9): 152-155. https://doi.org/10.11896／j.issn.1002-137X.2018.09.024
[9]	姚寒冰,邢娜娜,周俊伟,李勇华. 支持结果排序的安全密文检索方法研究 Study on Secure Retrieval Scheme over Encrypted Data Supporting Result Ranking 计算机科学, 2018, 45(5): 123-130. https://doi.org/10.11896/j.issn.1002-137X.2018.05.021
[10]	刘耀宗, 刘云恒. 基于区块链的RFID大数据安全溯源模型 Security Provenance Model for RFID Big Data Based on Blockchain 计算机科学, 2018, 45(11A): 367-368.
[11]	章文斌,李二涛,李飞,李琰琰,朱艺华. 基于NAK的WISP数据传输方案 Negative Acknowledgement Based Data Delivery Scheme for WISP 计算机科学, 2017, 44(Z6): 294-299. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.067
[12]	贾宁. 面向智能终端的校园教育互联系统的研究与实现 Research and Implementation of Campus Education Interconnection System for Intelligent Terminal 计算机科学, 2017, 44(Z11): 573-576. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.122
[13]	王山,孙莉,吴杰,冯锋,王洪伟. 一种基于计数型布隆过滤器的分子相似性算法研究 Research of Molecular Similarity Algorithm Based on Counting Bloom Filter 计算机科学, 2017, 44(Z11): 552-556. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.117
[14]	关炀,闫国玉,王颖,蒋遂平. RFID室内实时定位系统的数据滤波方法 Data Filtration Method for RFID Based Indoor RTLS 计算机科学, 2017, 44(Z11): 293-296. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.062
[15]	宋岚,薛锦云,胡启敏,谢武平,江东明,游珍. 无线射频RFID识别协议自动验证方法研究 Research of Automatic Verification Method about Radio Frequency Identification Protocol 计算机科学, 2017, 44(9): 99-104. https://doi.org/10.11896/j.issn.1002-137X.2017.09.020

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed