基于布隆过滤器的RFID数据冗余处理算法研究
|
摘要
RFID技术作为物联网领域的关键技术,具有广阔的应用前景。然而RFID设备在读取标签信息时会产生大量冗余数据。因此,RFID数据冗余处理的研究对于减少RFID中间件系统负荷、快速检测出入标签有着重要的意义。之前针对RFID数据冗余过滤的研究往往是单维度、静态场景的简单过滤,无法实现复杂场景下标签的出入检测。因此,本文提出一种名为时间距离布隆过滤器(TDBF)的算法,该算法从时间和空间两个维度进行冗余过滤。与常用的时间布隆过滤器相比,该算法兼顾了RFID标签的读取时间和读取距离,极大的降低了数据的冗余问题。在保证漏读率较低的情况下,极大的降低了数据的误读率。同时该算法支持动态场景中移动标签的冗余过滤,能够较好的满足出入监控需求。
As a key technology in the field of Internet of Things, RFID technology has broad application prospects. However, RFID devices generate a large amount of redundant data when reading tag information. Therefore, the research on RFID data redundancy processing is of great significance for reducing the load of RFID middleware system and quickly detecting incoming and outgoing tags. Previous studies on the redundancy filtering of RFID data are often simple filtering of single-dimensional and static scenes, and it is impossible to detect the ingress and egress of tags in complex scenarios. Therefore, this paper proposes an algorithm called Time Distance Bloom Filter(TDBF), which performs redundant filtering from both time and space. Compared with the Time Bloom filter, this algorithm takes into account the reading time and reading distance of the RFID tags, which greatly reduces the redundancy of the data. In the case of ensuring a low miss rate, the false-positive rate of the data is greatly reduced. At the same time, the algorithm supports redundant filtering of mobile tags in dynamic scenarios, which can better meet the requirements of access control.
As a key technology in the field of Internet of Things, RFID technology has broad application prospects. However, RFID devices generate a large amount of redundant data when reading tag information. Therefore, the research on RFID data redundancy processing is of great significance for reducing the load of RFID middleware system and quickly detecting incoming and outgoing tags. Previous studies on the redundancy filtering of RFID data are often simple filtering of single-dimensional and static scenes, and it is impossible to detect the ingress and egress of tags in complex scenarios. Therefore, this paper proposes an algorithm called Time Distance Bloom Filter(TDBF), which performs redundant filtering from both time and space. Compared with the Time Bloom filter, this algorithm takes into account the reading time and reading distance of the RFID tags, which greatly reduces the redundancy of the data. In the case of ensuring a low miss rate, the false-positive rate of the data is greatly reduced. At the same time, the algorithm supports redundant filtering of mobile tags in dynamic scenarios, which can better meet the requirements of access control.
引文
[1]Derakhshan.R,M.E.Orlowska,and X.Li,“RFID Data Management:Challenges and Opportunities.”IEEE International Conference on Rfid.pp.175-182,2007.
[2]Bai.Y,Wang.F,Liu.P,“Efficiently filtering RFID data streams”Proc Cleandb Workshop,pp.50-57,2006.
[3]Y.Zhang,Yibin.Tang,and Xufei.Li,“Overview of RFID Data Cleaning Algorithm”,Micro Processing.Vol.31,pp:32-36,2016.(张燕,汤一彬,李旭斐,“RFID数据清洗算法概述”,微处理机,2016,37(1):32-36).
[4]Wang,Jinlin,et al,“A survey on data cleaning methods in cyberspace.”2017 IEEE Second International Conference on Data Science in Cyberspace(DSC),pp.74-81,2017.
[5]Tian.W,Xue.R,Dong.X,and Wang.H,“An Approach to Design and Implement RFID Middleware System over Cloud Computing.”International Journal of Distributed Sensor Networks.pp.1-13,2013.
[6]Vahdati,Farahnaz,R.Javidan,and A.Farrahi,“A new method for data redundancy reduction in RFID middleware.”International Symposium on Telecommunications.pp.175-180,2010.
[7]Gonzalez.H,Han.J,Li.X,and et al,“Warehousing and analyzing massive RFID data sets.”International Conference on Data Engineering IEEE(ICDE),vol.6,pp.83-94,2006.
[8]Che.Qing.Jin,Q.Wei.Ning,and Zao.Ying,“Analysis and Management of Streaming Data:A Survey.”Journal of Software,vol.15,pp.1172-1181,2004.
[9]Iyer.Vasanth,S.S.Iyengar,and Niki Pissinou,“Ensemble stream model for data-cleaning in sensor networks.”AI Matters.pp:29-32,2015.
[10]Ramírez-Gallego,Sergio,et al,“A survey on data preprocessing for data stream mining:Current status and future directions.”Neuro computing,pp:39-57,2017.
[11]Le.Z,“Research and development of RFID middleware data processing[Ph.D.dissertation],”Shanghai Jiao Tong University,2008(张乐.“RFID中间件数据处理研究与开发[D]”,上海交通大学,2008.)
[12]Jeffery,Shawn R,Alonso G,and Franklin M J,“A Pipelined Framework for Online Cleaning of Sensor Data Streams.”International Conference on Data Engineering IEEE,pp.140-140,2006.
[13]Kamaludin,Hazalila,Hairulnizam Mahdin,and Jemal H.Abawajy,“Filtering redundant data from RFID data streams.”Journal of Sensors,vol.2016,pp.1-7,2016.
[14]Ma.Meng,Ping.Wang,and Chao-Hsien Chu,“Redundant reader elimination in large-scale distributed RFID networks.”IEEE Internet of Things Journal vol.5,no.2,pp:884-894,2018.
[15]Gonzalez.Hector,J.Han,and X.Shen.“Cost-Conscious Cleaning of Massive RFID Data Sets.”IEEE International Conference on Data Engineering,pp.1268-1272,2007.
[16]Qiaomin.Lin,and et al,“A method of cleaning RFID data streams based on Naive Bayes classifier.”International Journal of Ad Hoc and Ubiquitous Computing,vol.21,no.4,pp.237-244,2016.
[17]Luo.YJ,Jiang.JG,Wang.SY,Jing X,Ding C,Zhang ZJ,and Zhang YF,“Filtering and cleaning for RFID streaming data technology based on finite state machine.”Journal of Software,vol.25,no.8,pp.1713-1728,2014.(罗元剑,姜建国,王思叶,等.“基于有限状态机的RFID流数据过滤与清理技术”.软件学报,2014(8):1713-1728.)
[18]Mahdin.Hairulnizam,“A Review on Bloom Filter Based Approaches for RFID Data Cleaning.”Lecture Notes in Electrical Engineering,vol.285,pp.79-86,2014.
[19]Zhijian.Y,Yingwen.C,Jiajia.Y,Yan.J and Shuqiang Y,“Research on typical Bloom filters and their data flow applications.”Computer Engineering,vol.35,no.7,pp.5-7,2009.(袁志坚,陈颖文,缪嘉嘉,贾焰,杨树强,“典型Bloom过滤器的研究及其数据流应用.”计算机工程,2009,35(7):5-7.)
[20]Bloom.Burton,“Space/Time Tradeoffs in Hash Coding with Allowable Errors”.Ipsj Magazine,vol.13,pp.422-426,1970.
[21]Lee.Chun Hee,and C.W.Chung,“An approximate duplicate elimination in RFID data streams.”Data&Knowledge Engineering,vol.285,no.12,pp.1070-1087,2011.
[22]Mahdin.H,Abawajy.J,“An approach for removing redundant data from RFID data streams.”Sensors.vol.11,no.10,pp.9863-9877,2011.
[23]Rui.Wu,L.Guoqiong,and D.Guoqiang,“Filtering Redundant RFID Data Based on Sliding Windows.”International Conference on Management of E-commerce&E-government,pp.187-191,2014.
[24]Guoqiong.L,Jun.Z,Ni.H,Xiaomei.H,Zhiwei.H,and Changxuan,W,“Approximately Filtering Redundant Data for Uncertain RFID Data Streams.”IEEE International Conference on Mobile Data Management,pp.56-61,2017.
[25]Yongli.W,Chuan.W,and Xiaohui.J,“RFID redundant data cleaning algorithm based on space-time Bloom filter”Journal of Nanjing University of Science and Technology,vol.39,no.3,pp.253-259,2015.(王永利,王川,蒋效会,“基于时空布隆过滤器的RFID冗余数据清洗算法.”南京理工大学学报,2015,39(3):253-259.)
[26]Rui.W,“Research on RFID redundant data filtering based on sliding window[M.S.dissertation].”Jiangxi University of Finance and Economics,2014.(吴锐.“基于滑动窗口的RFID冗余数据滤重研究[D]”,江西财经大学,2014.)
[27]Ali G?,˙Ik-Gerber,Oktepe A B.,Li,S.,&Li,N,“Analysis of the variability of RSSI values for active RFID-based indoor applications.”Turkish Journal of Engineering&Environmental Sciences.vol.37,no.2,pp.186-211,2013.
[28]W.Duan,Chunjiang.Liu,Yueshan.Wu,“Application of RSSI in RFID Reader.”Computer Engineering.vol.36,no.22,pp.289-290,2010.(段璞,刘春江,武岳山,“RSSI在RFID读写器中的应用”,计算机工程,2010,36(22):289-290.)
[29]H.Hadj.M,R.Touhami;S.Tedjini,“Cleansing RFID data based on RSSI estimation.”International Conference on Ubiquitous Wireless Broadband(ICUWB),pp.1-4,2017.
[30]Yu.Wei,Liang.F,He.X,Hatcher.W.G,Lu.C,and Lin.J,“ASurvey on the Edge Computing for the Internet of Things.”IEEEAccess.vol.6,pp:6900-6912,2018.
[31]Shi.W,Cao,J,Zhang.Q,Li.Y,and Xu.L,“Edge Computing:Vision and Challenges.”IEEE Internet of Things Journal.vol.3,no.5,pp:637-646,2016.
[32]Jing.Su,and C.Guoqiang,“A new RFID middleware architecture design.”International Conference on Computer&Automation Engineering IEEE,pp:637-639,2010.
[2]Bai.Y,Wang.F,Liu.P,“Efficiently filtering RFID data streams”Proc Cleandb Workshop,pp.50-57,2006.
[3]Y.Zhang,Yibin.Tang,and Xufei.Li,“Overview of RFID Data Cleaning Algorithm”,Micro Processing.Vol.31,pp:32-36,2016.(张燕,汤一彬,李旭斐,“RFID数据清洗算法概述”,微处理机,2016,37(1):32-36).
[4]Wang,Jinlin,et al,“A survey on data cleaning methods in cyberspace.”2017 IEEE Second International Conference on Data Science in Cyberspace(DSC),pp.74-81,2017.
[5]Tian.W,Xue.R,Dong.X,and Wang.H,“An Approach to Design and Implement RFID Middleware System over Cloud Computing.”International Journal of Distributed Sensor Networks.pp.1-13,2013.
[6]Vahdati,Farahnaz,R.Javidan,and A.Farrahi,“A new method for data redundancy reduction in RFID middleware.”International Symposium on Telecommunications.pp.175-180,2010.
[7]Gonzalez.H,Han.J,Li.X,and et al,“Warehousing and analyzing massive RFID data sets.”International Conference on Data Engineering IEEE(ICDE),vol.6,pp.83-94,2006.
[8]Che.Qing.Jin,Q.Wei.Ning,and Zao.Ying,“Analysis and Management of Streaming Data:A Survey.”Journal of Software,vol.15,pp.1172-1181,2004.
[9]Iyer.Vasanth,S.S.Iyengar,and Niki Pissinou,“Ensemble stream model for data-cleaning in sensor networks.”AI Matters.pp:29-32,2015.
[10]Ramírez-Gallego,Sergio,et al,“A survey on data preprocessing for data stream mining:Current status and future directions.”Neuro computing,pp:39-57,2017.
[11]Le.Z,“Research and development of RFID middleware data processing[Ph.D.dissertation],”Shanghai Jiao Tong University,2008(张乐.“RFID中间件数据处理研究与开发[D]”,上海交通大学,2008.)
[12]Jeffery,Shawn R,Alonso G,and Franklin M J,“A Pipelined Framework for Online Cleaning of Sensor Data Streams.”International Conference on Data Engineering IEEE,pp.140-140,2006.
[13]Kamaludin,Hazalila,Hairulnizam Mahdin,and Jemal H.Abawajy,“Filtering redundant data from RFID data streams.”Journal of Sensors,vol.2016,pp.1-7,2016.
[14]Ma.Meng,Ping.Wang,and Chao-Hsien Chu,“Redundant reader elimination in large-scale distributed RFID networks.”IEEE Internet of Things Journal vol.5,no.2,pp:884-894,2018.
[15]Gonzalez.Hector,J.Han,and X.Shen.“Cost-Conscious Cleaning of Massive RFID Data Sets.”IEEE International Conference on Data Engineering,pp.1268-1272,2007.
[16]Qiaomin.Lin,and et al,“A method of cleaning RFID data streams based on Naive Bayes classifier.”International Journal of Ad Hoc and Ubiquitous Computing,vol.21,no.4,pp.237-244,2016.
[17]Luo.YJ,Jiang.JG,Wang.SY,Jing X,Ding C,Zhang ZJ,and Zhang YF,“Filtering and cleaning for RFID streaming data technology based on finite state machine.”Journal of Software,vol.25,no.8,pp.1713-1728,2014.(罗元剑,姜建国,王思叶,等.“基于有限状态机的RFID流数据过滤与清理技术”.软件学报,2014(8):1713-1728.)
[18]Mahdin.Hairulnizam,“A Review on Bloom Filter Based Approaches for RFID Data Cleaning.”Lecture Notes in Electrical Engineering,vol.285,pp.79-86,2014.
[19]Zhijian.Y,Yingwen.C,Jiajia.Y,Yan.J and Shuqiang Y,“Research on typical Bloom filters and their data flow applications.”Computer Engineering,vol.35,no.7,pp.5-7,2009.(袁志坚,陈颖文,缪嘉嘉,贾焰,杨树强,“典型Bloom过滤器的研究及其数据流应用.”计算机工程,2009,35(7):5-7.)
[20]Bloom.Burton,“Space/Time Tradeoffs in Hash Coding with Allowable Errors”.Ipsj Magazine,vol.13,pp.422-426,1970.
[21]Lee.Chun Hee,and C.W.Chung,“An approximate duplicate elimination in RFID data streams.”Data&Knowledge Engineering,vol.285,no.12,pp.1070-1087,2011.
[22]Mahdin.H,Abawajy.J,“An approach for removing redundant data from RFID data streams.”Sensors.vol.11,no.10,pp.9863-9877,2011.
[23]Rui.Wu,L.Guoqiong,and D.Guoqiang,“Filtering Redundant RFID Data Based on Sliding Windows.”International Conference on Management of E-commerce&E-government,pp.187-191,2014.
[24]Guoqiong.L,Jun.Z,Ni.H,Xiaomei.H,Zhiwei.H,and Changxuan,W,“Approximately Filtering Redundant Data for Uncertain RFID Data Streams.”IEEE International Conference on Mobile Data Management,pp.56-61,2017.
[25]Yongli.W,Chuan.W,and Xiaohui.J,“RFID redundant data cleaning algorithm based on space-time Bloom filter”Journal of Nanjing University of Science and Technology,vol.39,no.3,pp.253-259,2015.(王永利,王川,蒋效会,“基于时空布隆过滤器的RFID冗余数据清洗算法.”南京理工大学学报,2015,39(3):253-259.)
[26]Rui.W,“Research on RFID redundant data filtering based on sliding window[M.S.dissertation].”Jiangxi University of Finance and Economics,2014.(吴锐.“基于滑动窗口的RFID冗余数据滤重研究[D]”,江西财经大学,2014.)
[27]Ali G?,˙Ik-Gerber,Oktepe A B.,Li,S.,&Li,N,“Analysis of the variability of RSSI values for active RFID-based indoor applications.”Turkish Journal of Engineering&Environmental Sciences.vol.37,no.2,pp.186-211,2013.
[28]W.Duan,Chunjiang.Liu,Yueshan.Wu,“Application of RSSI in RFID Reader.”Computer Engineering.vol.36,no.22,pp.289-290,2010.(段璞,刘春江,武岳山,“RSSI在RFID读写器中的应用”,计算机工程,2010,36(22):289-290.)
[29]H.Hadj.M,R.Touhami;S.Tedjini,“Cleansing RFID data based on RSSI estimation.”International Conference on Ubiquitous Wireless Broadband(ICUWB),pp.1-4,2017.
[30]Yu.Wei,Liang.F,He.X,Hatcher.W.G,Lu.C,and Lin.J,“ASurvey on the Edge Computing for the Internet of Things.”IEEEAccess.vol.6,pp:6900-6912,2018.
[31]Shi.W,Cao,J,Zhang.Q,Li.Y,and Xu.L,“Edge Computing:Vision and Challenges.”IEEE Internet of Things Journal.vol.3,no.5,pp:637-646,2016.
[32]Jing.Su,and C.Guoqiang,“A new RFID middleware architecture design.”International Conference on Computer&Automation Engineering IEEE,pp:637-639,2010.