一种基于Trie树和扩展B树的RFID标签编码过滤方法研究  

Research on RFID Tag Code Filtering Method Based on Trie Tree and Extended B Tree

作　　者：赵文[1,2] 刘学洋[1,2] 刘殿兴 王立福[1,2] 

机构地区：[1]北京大学软件工程国家工程研究中心,北京100871 [2]北京大学信息科学技术学院软件研究所高可信软件技术教育部重点实验室,北京100871 [3]北京银行信息技术总部,北京100011

出　　处：《电子学报》2011年第A03期126-133,共8页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划(No.2006AA04A119;No.2006AA04A121);国家973重点基础研究发展计划(No.2009CB320706);国家自然科学基金(No.60803014)

摘　　要：面向EPC模式(EPC Pattern)的标签编码过滤是RFID中间件的主要功能之一.为提高过滤效率,本文给出了一种基于trie树和扩展B树相结合的标签编码过滤方法.通过分析标签编码和EPC模式的结构特征,将系统中大量的EPC模式构造成一个层次查找结构,对于EPC模式中的常规编码段采用trie树表达,对于区间形式采用扩展B树表达.查找过程按照编码段由高至低依次进行,并采用了基于位向量集合的优化方法.实验表明标签编码过滤效率受EPC模式数量变化的影响较小,能够有效降低向上层应用传输数据的延迟.Tag code filtering by EPC Patterns is one of the main functions of RFID middleware.In order to improve filtering efficiency,a trie tree and extended B tree based tag code filtering method is proposed.By analyzing the structural features of tag code and EPC Pattern,a layered searching structure is constructed with the EPC Patterns in the system,trie tree is used for expressing normal code sections of the EPC Patterns,extended B tree is used for expressing range forms.The search in layered structure is conducted with the descending order of code segments,and searching process is also optimized based on bit vector section set.The simulation tests show that the efficiency of our method to filter tag code suffers little effect by the change of EPC Pattern quantity and can effectively reduce the data transmission delay to the upper application.

关 键 词：RFID 中间件 EPC模式 过滤 TRIE树 B树 

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