一种面向大规模网络环境的分布式K近邻节点搜索方法

摘要

本发明公开了一种面向大规模网络环境的分布式K近邻节点搜索方法，要解决的技术问题是：提出一种面向大规模网络环境的分布式K近邻节点搜索方法，低成本高精度实现节点邻近性的测量。技术方案是采用直接测量方式为每个节点构建邻居集，并维护节点之间的网络距离信息；采用随机更新和最近邻更新两种方式更新节点的邻居集；基于回退思想，从与目标节点网络距离最远的节点开始搜索最近邻节点。采用本发明可有效降低搜索迭代次数，提高搜索效率，且能保证从全局范围搜索最近邻节点，低成本高精度实现节点邻近性测量。

主权项

一种面向大规模网络环境的分布式K近邻节点搜索方法，其特征在于包括以下步骤：第一步，系统初始化：1.1在系统初始状态，对于任意节点O，将其初始邻居集设置为除本节点O之外的其它所有节点，并通过直接测量方式获取节点之间的网络距离，每个节点维护的邻居集信息包括邻居节点IP和本节点与邻居节点之间的网络距离；1.2随机选择节点E作为入口节点；第二步，为新加入节点创建邻居集：2.1假设A是新加入的节点，节点A向入口节点E发送加入请求；2.2入口节点E从其邻居集中随机选择I个节点，将这些节点的IP发送给新节点A，I为正整数，I根据系统的扩展性和维护开销进行动态调整；2.3新节点A将入口节点E发送的I个节点设置为初始邻居集，并通过直接测量方式获取本节点与邻居节点之间的网络距离；第三步，节点邻居集更新：每个节点定期更新邻居集，具体包括随机更新和最近邻更新两部分，随机更新的周期为TR，最近邻更新的周期为TN，TR和TN根据系统的扩展性和维护开销动态设置，将正更新的节点设为B，3.1随机更新：3.1.1节点B随机选择其邻居集中的一个节点M，并向节点M发送请求消息；3.1.2节点M从其邻居集中随机选择比例为P的邻居节点构成集合S，并将集合S返回给节点B，P取5％；3.1.3节点B通过直接测量方式获取本节点与集合S中的各节点之间的网络距离；3.1.4节点B将集合S中的节点添加到自己的邻居集中；3.2最近邻更新：3.2.1节点B采用最近邻节点搜索方法搜索自己的最近邻节点，得到最近邻节点BN；3.2.2节点B将节点BN添加到其邻居集中；第四步，当接收到搜索目标节点T的K近邻节点的请求时，系统的节点数目之K≥1，进行回退搜索：4.1采用最近邻节点搜索方法搜索目标节点T的最近邻节点NN，最近邻节点搜索方法的流程是：(1)从入口节点E开始搜索目标节点T的最远邻节点：(1.1)节点E直接测量其与目标节点T之间的网络距离d；(1.2)在节点E的邻居集中选择符合如下条件的节点X：节点E与节点X之间的网络距离在[(1‑β)*d，(1+β)*d]范围内，β为系统参数，β取10％，符合条件的节点构成集合FS；(1.3)直接测量集合FS中的各节点与目标节点T之间的网络距离，确定与目标节点T距离最远的节点F，其与目标节点T之间的网络距离记为dF；(1.4)如果dF＞d，节点E向节点F发送搜索最远邻节点的请求信息，E＝F，然后转步骤(1.1)继续搜索最远邻节点；否则，当前节点E即为最远邻节点，记为Q；(2)从最远邻节点Q开始搜索目标节点T的最近邻节点：(2.1)节点Q直接测量其与目标节点T之间的网络距离l；(2.2)在节点Q的邻居集中选择符合如下条件的节点Y：节点Q与节点Y之间的网络距离在[(1‑β)*l，(1+β)*l]范围内，符合条件的节点构成集合NS1。(2.3)在节点Q的邻居集中随机选择m个节点构成集合NS2，m为正整数，m根据系统的扩展性和维护开销进行动态调整；(2.4)NS＝NS1∪NS2；(2.5)直接测量集合NS中的各节点与目标节点T之间的网络距离，确定与目标节点T距离最近的节点N，其与目标节点T之间的网络距离记为lN；(2.6)如果lN＜l，节点Q向节点N发送搜索最近邻节点的请求信息，节点N将节点Q记录为其上一跳步节点，为实现回退搜索提供信息，Q＝N，然后转步骤(2.1)继续搜索最近邻节点；否则，当前节点Q即为最近邻节点。4.2目标节点T的最近邻节点NN向其上一跳步节点R发送最近邻节点搜索请求和当前K近邻节点集合KNSet＝{NN}；4.3采用最近邻节点搜索方法从节点R开始，E＝R，在不包括当前K近邻节点集合KNSet的节点范围内搜索目标节点T的最近邻节点Y，当前K近邻节点集合更新为KNSet＝KNSet∪{Y}；4.4如果当前K近邻节点集合KNSet包含的节点数目等于K，那么，K近邻节点搜索结束；否则，节点Y向其上一跳步节点R’发送最近邻节点搜索请求和当前K近邻节点集合KNSet，R＝R’，转到第4.3步，继续回退搜索。