基于分层布隆过滤器的发布订阅自动发现算法  

Publish subscribe automatic discovery algorithm based on hierarchical Bloom filter

作　　者：耿宏 李勇猛 GENG Hong;LI Yong-meng(College of Electronic Information and Automation,Civil Aviation University of China,Tianjin 300300,China)

机构地区：[1]中国民航大学电子信息与自动化学院

出　　处：《计算机工程与设计》2019年第12期3494-3499,共6页Computer Engineering and Design

基　　金：中美绿色航线合作基金项目(GH201661279)

摘　　要：针对当前简单发现算法(SDP)中线性链表式存储结构对多层节点查找时延偏高和内存占用大的问题,提出一种基于分层布隆过滤器的发布/订阅自动发现算法(HBF_ADA)。使用动态布隆计数树(DBCT)型数据结构,根据添加元素个数动态创建节点,把待查询元素录入为集合,利用集合的相交运算判断元素是否存在于网络;对每个字节增加一个计数器,记录对应字节被置位的次数,解决布隆过滤器元素删除困难的问题。实验结果表明,HBF_ADA算法的时延参数和内存消耗明显低于SDP和BF_SDP,能够删除已存在的节点信息,在允许低误报率的情况下,满足现实应用的需求。Aiming at the problems that the linear linked list storage structure in the current simple discovery protocol(SDP)has high latency and large memory occupation in searching for multi-layer nodes,apublish/subscribe automatic discovery algorithm based on hierarchical Bloom filter(HBF_ADA)was proposed.A data structure based on dynamic Bloom count tree(DBCT)was used,which dynamically created nodes according to the number of joined elements,and the queried elements were added to the set,the set intersection operation was applied to determine whether the element existed in the network.To solve the problem that the Bloom filter element is difficult to delete,a counter was added to each byte to record the number of times the corresponding byte was set.The simulation results show that the latency and memory consumption of the proposed algorithm are significantly lower than SDP and Bloom filter simple discovery protocol(BF_SDP).The existing node information can be deleted.When low false positive rate is allowed,the algorithm meets the needs of practical applications.

关 键 词：数据分发服务 自动发现算法 分层布隆过滤器 发布/订阅 误报率 

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