分布式计算机网络论文提纲

论文题目：布鲁姆过滤器查询算法及其应用研究

摘要：资源交互共享是计算机网络和分布式系统的核心，如何有效的表示信息和查询信息是资源交互共享中最本质的问题。高速发展的计算机网络和计算机系统中，当数据不断膨胀时，数据集合的表示和访问越来越困难。因此，设计精简数据结构支持日益增长的数据存储需求，设计与之对应的算法支持海量数据下的高效查询交互成为当前网络、数据库、分布式系统中资源交互共享的核心问题与严峻挑战。 布鲁姆过滤器（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％，提出的基于布鲁姆过滤器的混合移动自组织网服务发现模型具有良好的性能。

关键词：布鲁姆过滤器;数据结构;集合元素查询;计算机网络;分布式计算;分布式消息系统;副本一致性维护

学科专业：计算机应用技术

摘要

ABSTRACT

插图索引

第1章 绪论

1.1 网络高速发展给信息表示和查询带来的挑战

1.2 信息精简表示和快速查询的布鲁姆过滤器方法

1.3 布鲁姆过滤器算法国内外研究状态

1.4 本文的主要研究成果和贡献

1.5 论文结构和章节安排

第2章 查询算法概述

2.1 查询的基本概念

2.2 查询算法分类

2.3 树型查询算法

2.4 哈希查询算法

2.4.1 哈希查询算法原理

2.4.2 哈希算法主要应用

2.4.3 哈希算法研究进程

2.5 从哈希存储表到布鲁姆过滤器

2.6 查询算法比较

第3章 布鲁姆过滤器查询算法

3.1 标准布鲁姆过滤器查询算法

3.1.1 标准布鲁姆过滤器查询算法基本操作

3.1.2 标准布鲁姆过滤器查询算法理论分析

3.1.3 独立空间标准布鲁姆过滤器查询算法

3.2 布鲁姆过滤器查询算法主要应用

3.3 布鲁姆过滤器各种扩展算法

3.3.1 计数式布鲁姆过滤器查询算法

3.3.2 光谱布鲁姆过滤器查询算法

3.3.3 压缩布鲁姆过滤器查询算法

3.3.4 拆分型和动态布鲁姆过滤器查询算法

3.3.5 多维布鲁姆过滤器查询算法

3.3.6 其他布鲁姆过滤器查询算法改进

3.4 现有布鲁姆过滤器存在的待解决的问题

3.5 小结

第4章 分档布鲁姆过滤器查询算法

4.1 引言

4.2 分档布鲁姆过滤器设计

4.2.1 两档布鲁姆过滤器(L=2)

4.2.2 多档布鲁姆过滤器(L>2)

4.3 类目标函数梯度遗传优化求解分档布鲁姆过滤器

4.4 性能评估

4.4.1 计算时间

4.4.2 集合查询总代价

4.5 分档布鲁姆过滤器算法的应用探讨和仿真实验

4.5.1 协作式缓存文件系统结构

4.5.2 基于分档布鲁姆过滤器的安全敏感文件系统

4.6 小结

第5章 可扩展布鲁姆过滤器查询算法

5.1 引言

5.2 相关工作

5.3 可扩展布鲁姆过滤器

5.3.1 可扩展布鲁姆过滤器基本原理

5.3.3 可扩展布鲁姆过滤器元素插入

5.3.4 可扩展布鲁姆过滤器元素查询

5.4 基于H_3哈希函数的可扩展过滤器

5.4.1 H_3类通用哈希函数概述

5.4.2 可扩展布鲁姆过滤器H_3哈希函数设计

5.4.3 基于H_3哈希函数的可扩展过滤器元素插入

5.4.4 基于H_3哈希函数的可扩展过滤器元素查询

5.5 可扩展布鲁姆过滤器理论分析

5.5.1 误判率

5.5.2 查询时间

5.5.3 存储空间

5.6 可扩展布鲁姆过滤器实验结果和性能评价

5.6.1 误判率

5.6.2 查询时间

5.6.3 存储空间

5.7 小结

第6章 多维布鲁姆过滤器查询算法研究

6.1 引言

6.2 现有多维布鲁姆过滤器查询算法

6.2.1 多维布鲁姆过滤器查询算法原理

6.2.2 多维布鲁姆过滤器查询算法实例分析

6.3 联合多维布鲁姆过滤器查询算法

6.3.1 联合多维布鲁姆过滤器设计

6.3.2 联合多维布鲁姆过滤器元素插入

6.3.3 联合多维布鲁姆过滤器元素查询

6.4 实验结果和性能评价

6.5 应用探讨

6.6 小结

第7章 布鲁姆过滤器代数运算探讨

7.1 引言

7.2 布鲁姆过滤器形式化表示和相关定义

7.3 布鲁姆过滤器基本代数运算

7.3.1 布尔代数定义回顾

7.3.2 布鲁姆过滤器代数运算

7.4 布鲁姆过滤器代数运算和集合查询的关系

7.4.1 布鲁姆过滤器并运算查询算法

7.4.2 布鲁姆过滤器交运算查询算法

7.4.3 布鲁姆过滤器异或运算查询算法

7.4.4 布鲁姆过滤器补运算查询算法

7.4.5 布鲁姆过滤器差运算查询算法

7.5 小结

第8章 基于布鲁姆过滤器的P2P副本一致性维护算法

8.1 引言

8.2 P2P副本更新相关工作

8.3 问题描述和相关定义

8.4 节点轨迹标签P2P副本一致性维护算法

8.4.1 节点轨迹标签算法设计

8.4.2 布鲁姆过滤器表示节点轨迹标签的一致性维护算法

8.4.3 节点轨迹标签改进的Gossip算法

8.5 算法理论分析

8.6 仿真实验和算法性能评价

8.6.1 实验环境

8.6.2 仿真实验

8.7 小结

第9章 基于布鲁姆过滤器的混合移动自组织网络服务发现模型

9.1 引言

9.2 相关工作介绍

9.2.1 服务发现协议

9.2.2 移动自组织网络中服务发现结构

9.3 问题的描述和相关定义

9.4 基于布鲁姆过滤器的混合移动自组织服务发现模型

9.4.1 系统结构

9.4.2 服务发布

9.4.3 服务查询

9.4.4 服务取消

9.4.5 服务注册信息的扩散与同步

9.4.5.1 基于布鲁姆过滤器距离的集合变动评估算法

9.4.5.2 布鲁姆过滤器距离评估算法性能

9.4.5.3 基于布鲁姆过滤器距离的服务注册信息的扩散与同步

9.4.6 节点移动时服务注册信息处理

9.5 服务发现模型理论分析

9.5.1 节点动态性分析

9.5.2 查询处理能力分析

9.5.3 查询时间分析

9.5.4 网络负载分析

9.5.5 节点移动性代价分析

9.6 小结

结论

主要工作

今后工作设想

参考文献

致谢

B1 科研项目

B2 申请专利和其他奖项