论文部分内容阅读
资源交互共享是计算机网络和分布式系统的核心，如何有效的表示信息和查询信息是资源交互共享中最本质的问题。高速发展的计算机网络和计算机系统中，当数据不断膨胀时，数据集合的表示和访问越来越困难。因此，设计精简数据结构支持日益增长的数据存储需求，设计与之对应的算法支持海量数据下的高效查询交互成为当前网络、数据库、分布式系统中资源交互共享的核心问题与严峻挑战。布鲁姆过滤器（Bloom filter）采用一个位串表示数据集合并能有效支持元素的哈希查找，是一种能够简洁的表示集合并支持集合查询的数据结构，广泛应用于数据库、网络和分布式系统中。本文从理论和应用两个方面对布鲁姆过滤器查询算法进行了深入的研究。系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果，分析了目前布鲁姆过滤器查询算法的研究现状和缺陷，针对目前算法的不足，提出了分档布鲁姆过滤器查询算法、可扩展布鲁姆过滤器查询算法、联合多维布鲁姆过滤器查询算法、基于布鲁姆过滤器距离的集合变动评估算法，并探讨了布鲁姆过滤器代数运算和集合查询的关系。研究布鲁姆过滤器在分布式系统中的应用，提出了基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法和基于布鲁姆过滤器的混合移动自组织网络服务发现模型。本文的创新性成果主要体现在以下几个方面：1)提出代价敏感的分档布鲁姆过滤器查询算法针对现有的布鲁姆过滤器查询算法没有考虑查询失效代价这一缺陷，本文提出一种新的代价敏感的分档布鲁姆过滤器查询算法。它将元素根据不同的查询代价分为不同的子集，通过考查每档子集最低查询失效率的关系，建立由每档子集最低查询失效率表示的集合最低查询失效总代价目标函数，使用类目标函数梯度遗传算法获得每档的最优哈希函数个数ki，完成集合到向量的映射与查找。仿真实验结果表明，新的分档布鲁姆过滤器查询算法和标准布鲁姆过滤器算法相比，所用的查询计算时间基本相同，而查询失效总代价降低至少40％。2)提出基于H3哈希函数的可扩展布鲁姆过滤器查询算法布鲁姆过滤器可扩展性主要是当集合元素动态增长超出过滤器算法设计的容量时，如何调整布鲁姆过滤器参数，使得布鲁姆过滤器查询算法有较低的查询误判率，同时具有可接受的计算性能，保证过滤器的可用性。本文研究布鲁姆过滤器的可扩展性问题，提出基于H3哈希函数的可扩展布鲁姆过滤器查询算法，当集合元素增长超过布鲁姆过滤器集合容量限制时，通过增加成倍数扩大的布鲁姆过滤器向量来保持很低的误判率，利用H3哈希函数实现可扩展布鲁姆过滤器的设计以及过滤器中元素的插入、查询过程。实验分析表明，新的可扩展布鲁姆过滤器的元素查询误判率永远小于动态布鲁姆过滤器，平均为它的21.3％，且查询时间呈对数增长，解决了现有算法查询时间增长过快问题。3)研究多维布鲁姆过滤器查询算法针对现有多维布鲁姆过滤器查询算法（MDBF）在多维元素表示和查询时分割了各维属性为一体的缺陷，提出一种改进的两步表示和查询的联合多维布鲁姆过滤器查询算法（CMDBF）。CMDBF在MDBF的基础上，增加一个联合标准布鲁姆过滤器CBF，将多维元素整体经过两次哈希运算表示到CBF中。CMDBF的元素表示和查找分两步进行，将MDBF作为元素表示和查找第一步，第二步联合元素各属性值利用CBF进行确认。仿真实验表明，CMDBF相比MDBF查询误判率降低明显。4)探讨布鲁姆过滤器的代数运算布鲁姆过滤器是集合到向量的一个映射，本文探讨布鲁姆过滤器的代数运算和集合查询的关系。定义布鲁姆过滤器的“并”，“交”，“异或”，“补”，“差”代数运算，从理论和仿真实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集，交集，异或集，补集，差集的元素查询性质。理论分析和实验结果表明，布鲁姆过滤器的“并”，“交”运算能够支持集合并集交集的元素查询，这一结论可以大大简化利用布鲁姆过滤器进行的系统设计。5)提出基于布鲁姆过滤器的节点轨迹标签P2P副本一致性维护算法本文研究P2P系统副本一致性维护算法，从直接更改消息报文角度出发，提出一种基于布鲁姆过滤器的节点轨迹标签无结构P2P副本一致性维护算法。通过在传输消息的报文中添加已接收更新消息的节点轨迹地址链表标签，可在消息传输源节点进行冗余判断来减少冗余消息数目。因为直接存储节点地址轨迹标签算法的消息长度随着消息传输轮数和网络度数增加而不断加大，论文采用布鲁姆过滤器表示地址链表轨迹标签。通过布鲁姆过滤器这种简洁的结构表示地址链表，可以减少添加到报文中的轨迹长度，同时利用布鲁姆过滤器的“并”运算还可以简化传输节点的冗余判断。仿真实验表明：基于布鲁姆过滤器的节点轨迹标签算法可以大大降低冗余消息数目，提高P2P系统的可扩展性。副本节点网络连通性越强，消息数目和传输带宽减少越明显。6)提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型研究服务发现中服务信息的精简存储和查询方法，提出基于布鲁姆过滤器的混合移动自组织网络服务发现模型。模型采用计数式布鲁姆过滤器表示注册服务目录，采用两层混合服务发现体系结构和两级服务信息存储方式。论文详细描述了基于布鲁姆过滤器的服务发布、服务查询、服务取消、服务注册信息的扩散与同步和节点移动时对应在服务协调者节点的相关操作和过程。定义布鲁姆过滤器距离，从分析布鲁姆过滤器的统计特性出发，提出了基于计数式布鲁姆过滤器距离的集合变动评估算法。将距离的评估算法用于服务注册信息的扩散与同步中，用于制定有效的服务注册信息发散和同步更新策略。实验仿真和理论分析表明，距离评估算法评估准确性高，准确率高达99.7％，提出的基于布鲁姆过滤器的混合移动自组织网服务发现模型具有良好的性能。