一种基于层次化单哈希计数布隆过滤器的DDS自动端点发现方法

本公开实施例涉及数据分发，尤其涉及一种基于层次化单哈希计数布隆过滤器的dds自动端点发现方法。

背景技术：

1、数据分发服务(data distribution service，dds)是对象管理组织(omg)颁布的以数据为中心的分布式实时通信中间件规范，广泛应用于多个领域的分布式仿真与实时控制系统。

2、dds采用去中心化发布/订阅模型，自动发现协议是其工作基础，可让域中参与者自动发现彼此，匹配发布与订阅端点建立通信。omg在dds互操作性标准中定义简单发现协议(simple discovery protocol，sdp)，是所有dds中间件必须支持的基础发现协议。

3、sdp采用全量发布与全量存储模式，运行分为spdp(simple participantdiscovery protocol)和sedp(simple endpoints discovery protocol)两个阶段：spdp阶段各节点广播参与者标识实现相互发现；sedp阶段参与者交换端点信息，按主题匹配建立通信。

4、sedp阶段中，协议会将域内所有节点端点数据同步给每个参与者，无关发现报文的无效传输会造成极大网络负载，同时各节点本地存储完整远端端点列表并参与全局同步，进一步加剧内存和带宽消耗。大规模分布式环境下，系统开销随节点规模快速增长，但单个节点实际所需远端端点仅占总量极小部分，该工作模式存在严重资源浪费。

5、为降低开销，研究者引入布隆过滤器（bloom filter）过滤无效报文。布隆过滤器是指纹标记法，用于快速检索元素是否在集合中，本质是二进制向量和一系列哈希函数：创建元素时将元素映射到位数组多个位置并置1；查询元素时检测对应映射位是否全为1，判断元素是否存在。

6、布隆过滤器空间效率高、查询速度快，可通过远小于原始集合的空间开销完成快速查询，实现数据过滤，降低通信与内存开销。作为概率型数据结构，它存在假阳性问题：位数组长度有限，不同元素映射位置可能重叠，导致不存在的元素被误判存在，但判定不存在的结果始终准确。另外标准布隆过滤器不支持删除，不适应元素动态变化场景。

7、近年来布隆过滤器应用广泛，为解决假阳性率高、动态适应性不足等问题，学界开展了大量研究。

8、然而，仍存在以下缺点：

9、第一，dds简单发现协议在sedp阶段采用全量同步策略，每个参与者需向所有其他参与者发送自身全部端点详情，并接收存储所有远端端点详情，导致网络消息量和内存占用随参与者数n和端点数m快速增长，严重限制系统可扩展性。

10、第二，平面布隆过滤器方案将所有端点映射到同一共享位数组，随着端点数量增加，位数组饱和，假阳性率呈指数上升，致使大量无关端点被误判为“可能存在”，引发大量无效的详细端点信息请求，削弱了选择性发现的收益。

11、第三，多哈希布隆过滤器每次插入或查询需执行多个独立的哈希函数，计算开销大；普通布隆过滤器不支持元素删除，难以应对dds中端点动态增删的常态，若需重建则成本高昂。

12、第四，已有层次化布隆过滤器通常基于固定的命名空间或主题树结构，通用性差；且查询过程需逐层访问各级过滤器，增加了内存访问次数和查询延迟，不利于实时性要求高的分布式系统。

13、因此，有必要改善上述相关技术方案中存在的一个或者多个问题。

14、需要注意的是，本部分旨在为权利要求书中陈述的本公开的技术方案提供背景或上下文。此处的描述不因为包括在本部分中就承认是现有技术。

技术实现思路

1、本公开实施例的目的在于提供一种基于层次化单哈希计数布隆过滤器的dds自动端点发现方法，进而至少在一定程度上克服由于相关技术的限制和缺陷而导致的一个或者多个问题。

2、根据本公开实施例的第一方面，提供一种基于层次化单哈希计数布隆过滤器的dds自动端点发现方法，包括：

3、步骤s1，分层构建：

4、获取本地参与者的端点描述符集合；

5、根据端点描述符的总数确定叶节点的期望端点数、叶节点数和第一路由深度；

6、为每个叶节点分配第一ohcbf；其中，所有第一ohcbf共享相同的分区参数；

7、对于每个端点描述符，计算其第一哈希值，并根据第一哈希值派生第一路由签名；

8、根据第一路由签名和第一路由深度确定该端点所属的第一叶节点索引，并将该端点的第一哈希值插入对应叶节点的第一ohcbf中；

9、步骤s2，摘要发布：

10、本地参与者向域内其他参与者发送参与者数据包，所述参与者数据包括第一路由深度和每个叶节点的第一ohcbf；

11、步骤s3，选择性查询：

12、本地参与者接收远程参与者的参与者数据包，并解析获得第二路由深度和各叶节点的第二ohcbf；

13、对于本地每个感兴趣端点，计算其第二哈希值并派生第二路由签名，根据远程参与者的第二路由深度计算第二叶节点索引，在远程参与者对应叶节点的第二ohcbf中执行成员判定；

14、若判定结果为可能存在，则触发选择性端点信息交换；若判定结果为一定不存在，则忽略该端点。

15、进一步地，期望端点数的计算公式为：

16、

17、最小叶节点数的计算公式为：

18、

19、第一路由深度的计算公式为：

20、

21、其中，为本地参与者的端点描述符的规模，取不小于最小叶节点数的最小2的幂作为叶节点数。

22、进一步地，第一路由签名的计算公式为：

23、

24、第一叶节点索引的计算公式为：

25、

26、其中，为第一哈希值。

27、进一步地，该方法还包括：

28、第一ohcbf将计数器槽划分为多个分区，所有分区大小两两互质；

29、对于任意端点，基于其第一哈希值分别对各分区大小取模，得到该端点在各分区中的映射位置；

30、插入时，将各映射位置的计数器加1；

31、查询时，检查所有映射位置的计数器是否均非零。

32、进一步地，该方法还包括：

33、当本地端点集合中的端点发生新增或删除时，计算该端点的哈希值，根据所述哈希值派生的路由签名确定该端点所属的叶节点，仅在该叶节点维护的布隆过滤器中对相应计数器执行自增或自减操作。

34、进一步地，选择性端点信息交换包括：

35、本地参与者向远程参与者发送端点的详细端点信息请求；

36、远程参与者接收到请求后，通过单播向本地参与者发送该端点的完整端点描述信息；

37、双方完成端点信息交换后，基于标准dds匹配逻辑建立通信。

38、进一步地，该方法还包括增量更新步骤：

39、当本地参与者的端点集合发生变化时，计算该端点的第一哈希值并派生第一路由签名，根据第一路由深度计算第一叶节点索引；

40、若为添加端点，则将该端点的第一哈希值插入对应叶节点的第一ohcbf并对相应计数器自增；

41、若为删除端点，则对对应叶节点的第一ohcbf中的相应计数器自减；

42、更新完成后重新发布刷新后的参与者数据包。

43、根据本公开实施例的第二方面，提供一种基于层次化单哈希计数布隆过滤器的dds自动端点发现装置，包括：

44、分层构建模块，用于获取本地参与者的端点描述符集合；根据端点描述符的总数确定叶节点的期望端点数、叶节点数和第一路由深度；为每个叶节点分配第一ohcbf；其中，所有第一ohcbf共享相同的分区参数；对于每个端点描述符，计算其第一哈希值，并根据第一哈希值派生第一路由签名；根据第一路由签名和第一路由深度确定该端点所属的第一叶节点索引，并将该端点的第一哈希值插入对应叶节点的第一ohcbf中；

45、摘要发布模块，用于向域内其他参与者发送参与者数据包，所述参与者数据包括第一路由深度和每个叶节点的第一ohcbf；

46、选择性查询模块，用于接收远程参与者的参与者数据包，并解析获得第二路由深度和各叶节点的第二ohcbf；对于本地每个感兴趣端点，计算其第二哈希值并派生第二路由签名，根据远程参与者的第二路由深度计算第二叶节点索引，在远程参与者对应叶节点的第二ohcbf中执行成员判定；若判定结果为可能存在，则触发选择性端点信息交换；若判定结果为一定不存在，则忽略该端点。

47、本公开的实施例提供的技术方案可以包括以下有益效果：

48、本公开的实施例中，通过上述方法及装置，第一方面，采用哈希路由分层策略，将本地端点集合按哈希值划分至多个相互独立的叶节点，每个叶节点仅维护其局部端点子集的ohcbf，使单个过滤器承载的元素基数远小于全局端点总数，从结构上有效抑制因填充密度过高导致的假阳性累积，从而降低无效端点信息请求的触发频率。

49、第二方面，提出基于叶节点独立维护的增量更新机制。每个叶节点的ohcbf采用计数方式独立管理其局部端点集合，端点插入或删除时仅需定位并更新对应叶节点中的计数器，无需重建全局结构，从而显著降低动态场景下的维护开销，增强对大规模高动态dds环境的适应能力。

50、第三方面，提出基于h_ohcbf（即层次化单哈希计数布隆过滤器）的选择性端点信息交换机制。参与者在参与者发现阶段仅发布轻量级的h_ohcbf摘要，接收方利用该摘要对本地感兴趣端点进行前置成员查询，仅当查询结果为“可能存在”时才触发详细端点信息交换，否则直接忽略。通过这一机制，避免了对无关端点详情的全量交换与全量存储，从而大幅降低发现阶段的消息数量和内存占用。

51、第四方面，通过单哈希设计实现路由定位与ohcbf成员判定复用同一哈希值，整个插入或查询过程仅需一次完整哈希计算，同时中间层不存储任何摘要信息，查询时直接定位至叶节点执行成员判定，避免逐层验证的额外开销，从而在引入分层过滤能力的同时保持与扁平单哈希方案相当的计算效率。

52、第五方面，能够同时降低发现消息数量、减少内存占用、抑制假阳性率、支持动态端点更新，并保持高构建与查询效率的dds自动端点发现方法，特别适用于大规模、高动态的分布式仿真与物联网系统环境。