现场名字解析系统中地理邻居发现机制研究

张 芳，孙 鹏，李 杨

（1.中国科学院大学，北京 100049；2.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190）

随着信息技术的飞速发展，越来越多的设备接入互联网。当前互联网正面临IP 语义过载的问题，这对传统的基于传输控制协议（TCP）∕Internet 协议（IP）的网络提出了巨大的挑战[1]。以信息为中心的网络（Information-Centric Networking,ICN）作为一种新兴的网络架构，拥有简化的网络架构、无缝的多宿主支持、高效的网内缓存等特性，与当前的5G 网络需求高度融合[2-4]。ICN采用名字和地址分离的范例[5]，因此需要名字解析系统（Name Resolution System）存储名字和地址的映射关系[6-7]。在文献[8]中，廖怡等人将确定性时延的概念引入名字解析服务，并提出了确定性时延名字解析系统框架（DLNR）。DLNR基于不同的确定性时延约束将空间范围划分为嵌套的层次化弹性区域(Hierarchical Elastic Area,HEA)，形成了对应不同等级的确定性时延的层次结构。现有的根据确定性时延约束划分的层次嵌套结构，主要针对有时延需求上限的固定用户。当用户是移动的，并且用户因移动跨出当前请求服务的解析节点所属的HEA 后，如何快速发现附近可以为自己提供服务的新的名字解析节点从而确保服务的连续性，是现有结构不能解决的问题。因此，在基本层次结构的基础上，文中提出增强型邻居结构-地理邻居，并介绍了一种名字解析系统中节点地理邻居的生成方法。

1 相关工作

随着移动互联网以及地理信息技术的迅猛发展，基于位置的服务(Location-Based Service，LBS)广泛应用于人类生活的方方面面[9]。比如一个人想搜索自己附近的餐馆、加油站等，这种查询最近设施的需求诞生了最近邻查询(k-Nearest Neighbor,kNN)。kNN 查询问题于1973 年由Knuth 提出的邮局问题衍生而来[10]。最近邻查询的研究已趋成熟，主要包括基于欧氏空间和基于路网两类[11-14]。穷举法是最简单的kNN 查询方法，例如一个人想搜索自己附近的餐馆，实际上是通过计算自己与各个餐馆之间的距离，对距离进行排序后选取指定范围内的餐馆。位置表示采用经纬度坐标，距离计算公式一般采用Haversine 大圆距离计算公式，如下：

其 中，haversine(φ1-φ2)=sin2((φ1-φ2)2)=(1-cos(φ1-φ2))2，R 为地球半径（可取平均值6 371 km），φ1、φ2表示两点的纬度，∆λ表示两点经度的差值。此方法简单直观且便于理解，适用于数据量小的情况。当数据量较大时，必然会耗费大量的时间和计算资源，搜索效率急剧下降。

另外，还有采用网格索引结构的最近邻查询方法。基于地理位置的网格搜索算法最经典的是Geohash 算法，由Gustavo Niemeyer 于2008 年提出，其本质是一种基于规则网格的地理编码方式，通过将二维的经纬度坐标编码成一维的字符串对数据进行降维，便于存储且不会重复，具有全球唯一性[15]。Geohash 的编码方式决定了其网格的空间遍历方式可由Z 字形的Peano 曲线遍历。正是这种Z 字型曲线的特点可以很容易计算出网格周边的其他网格编码。因此Geohash 在邻近点的查询上具有天然的优势。Z 字型曲线也有明显的突变缺陷，造成编码虽然相似但距离可能相差很大的问题，因此在查询附近位置点时，首先筛选Geohash 编码相似的位置点，然后进行实际距离计算。搜索算法具体步骤：1）根据搜索半径确定Geohash 编码的前缀长度n，n层网格的长度大于搜索半径，n+1 层网格长度小于搜索半径；2）根据搜索中心经纬度位置，结合前缀长度n，计算出搜索中心所在的父级网格编码，即Geohash 前缀编码；3）根据Geohash 编码规律，计算出与搜索中心所在父级网格相邻的其他8 个同级网格的编码前缀；4）遍历9 个父级网格的基本Geohash 网格空间，通过在数据库中查询匹配前缀找到空间内的位置点；5）计算位置点到搜索中心的实际距离，满足搜索条件则加入到结果集[16]。

2 解析节点地理邻居生成方法

2.1 问题分析

以下对文中出现的特殊名词作提前说明：1）目标名字解析节点：简称目标节点，代表本身要生成地理邻居结构的名字解析节点，相当于前文提到的搜索中心点。2）待选地理邻居节点：需要通过一定的规则判断该节点是否可以与目标节点互为地理邻居节点，一般与目标节点同层级。若干待选地理邻居节点组成待选地理邻居节点集。

由于现场名字解析系统中地理邻居的特殊使用场景，使得节点地理邻居的发现过程不同于传统的最近邻查询。该文通过以下分析，得出增强型邻居结构-地理邻居构造的关键点：1）现场名字解析系统提供具有不同等级确切性时延保障的解析服务，所有其他服务都必须在保证时延的前提下进行。默认用户在移动过程中对时延的要求不变，因此互为地理邻居的解析节点必须保障相同时延等级的服务，即在上文提到的DLNR 框架中是同层的。2）用户在跨出原有名字解析节点覆盖区域（HEA）后需再次执行网络测距，以寻找合适的满足自身确定性时延要求的名字解析节点，这个动作会使得服务被迫中断。因此地理邻居节点必须在地理空间中距离最近，并且满足1）中属于同层的要求。3）用户移动方向的不确定性，要求在构建名字解析节点的地理邻居结构时，节点不能是唯一的。某个名字解析节点的地理邻居结构必须是一个列表的形式，列表中的节点应该分布在该节点的周围，尽量做到方向全覆盖（说明：因现场需求，在某些方向可能没有部署名字解析节点）。

2.2 解析节点地理邻居与最近邻查询

现场名字解析系统中地理邻居节点的发现，不完全类似于上述两种最近邻查询算法。前两者只要满足在预设搜索半径内即可。由于地理邻居结构的特殊性，因此查询过程不仅要满足距离的要求，同时也要兼顾方向。

综合分析以上两种最近邻查找算法，结合现场名字解析系统的特性，该文选择将基于网格编码的Geohash 算法做部分改进以适应名字解析节点地理邻居选择的要求。理由如下：1）Geohash 编码全球统一具有位置可区分性，而非局部相对位置，精度可随编码长度调整，如编码长度为6 位时，精度为610 m，编码长度为8 位时，精度可缩小至19 m。因此不同层级具有不同确定性时延约束的名字解析节点可根据需要选取不同的编码长度，用以标注地理位置信息；2）网格规则且方向易表示，根据网格编码易得到网格之间的相对方位。从用户角度考虑，用户可以根据自己的目的地网格，在地理邻居节点列表中选择合适的下一个为自己提供解析服务的解析节点；3）基于网格搜索的附近点查找本质上是从内而外逐步扩大搜索范围，无需计算所有节点，节省了计算资源。

2.3 基于Geohash编码的地理邻居发现机制

2.3.1 Geohash编码

解析节点基于部署上线提供解析服务，易获取精确的位置坐标，比如经纬度。根据名字解析节点所在层级的确定性时延约束，结合所在地区的网络时延状况以及节点分布情况确定合适的网格长度，尽可能保证每个网格内只有一个节点。网格长度范围按照Geohash 编码前缀长度对应的精确度等级来选取；比如给定经纬度坐标为（39.923 201,116.390 705），根据解析节点的分布状况，网格长度在30 m 左右可以保证网格内单一节点，Geohash 编码前缀长度为7 位时，精度为76 m，前缀长度为8 位时，精度为19 m 左右，故确定采取8 位编码长度，因此该节点的Geohash 编码为wx4g0ec1。

2.3.2 邻居节点发现

目标节点所在网格周围共计8 个方向，分别为东(E)、南(S)、西(W)、北(N)、东南(SE)、东北(NE)、西南(SW)、西北(WN)，相邻方向间夹角为45°。理想情况下，目标节点的地理邻居节点分布在这8 个方向，并且各自在该方向的直线网格包含节点集中与目标节点距离最近。由此可以保障用户无论向哪个方向移动，都可以根据目标节点的地理邻居结构找到下一个合适的解析节点。若某个方向未发现解析节点，可以用顺时针45°范围内的节点代替。

目标节点搜索邻居节点不可能无止境，在某一方向未发现邻居节点时必须有终止条件。单一方向搜索终止条件有两个：一是找到邻居节点即停止搜索，二是超过搜索半径则停止搜索。条件一的优先级高于条件二。

2.3.3 算法具体步骤

1）根据名字解析节点时延属性及外在网络时延、节点分布等状况，确定合适的网格长度，进而明确Geohash 编码长度。

2）根据搜索半径r，结合网格边长d，确定单一方向搜索的网格个数k，k=（k向上取整）。

3）根据Geohash 编码规则计算目标节点周围8个方向的网格编码。8 个方向分别是东(E)、南(S)、西(W)、北(N)、东 南(SE)、东 北(NE)、西 南(SW)、西 北(NW)，分别计算每个方向上k个网格的编码。

4）按顺序遍历每个方向的网格编码，与待选地理邻居节点集匹配，若网格编码对应的节点存在，则将节点加入目标节点的地理邻居列表；至此，目标节点此方向的地理邻居节点查找成功；若节点不存在，转至步骤5）。

5）根据Geohash 编码规则计算此方向顺时针45°范围内未被遍历的网格编码，并与待选地理邻居节点集匹配，匹配成功则作为目标节点此方向地理邻居节点加入地理邻居列表，未匹配成功则代表此方向查找失败，继续查找下一个方向；示意图如图1 所示，节点1、2、3 分别是在N、NE、E 方向上查找到的目标节点的地理邻居节点（以上查找动作在步骤4）完成），在遍历目标节点SE 方向网格时，未找到邻居节点。因此遍历东南方向顺时针45°方向上的灰色区域网格，节点4 符合要求，会作为目标节点东南方向上的地理邻居节点。

图1 节点查找地理邻居节点示意图

6）直到所有方向都查找完全，最后输出目标节点的地理邻居列表。

3 实验结果与分析

3.1 实验环境与参数

实验环境：硬件环境：台式计算机（INTEL i7-10510U,主频为1.8 GHz，16.0 GB RAM）及其相应配件。

软件环境：Windows10 64 位平台，Python3.8。

实验数据：现场名字解析系统提供名字解析服务的解析节点一般部署在机房，根据现有的IDC 数据中心分布密度，一定范围内的IDC 数量远远不能满足较低时延层级的名字解析节点的部署要求。因此，该文选用北京市科教文化以及公司企业兴趣点数据，在此基础上剔除一些位置太近的兴趣点，尽可能模拟真实场景下低时延层级的名字解析节点的部署场景。以下所有实验仿真结果都基于此数据。

对比算法：对kNN 查询中的穷举法做部分改进，满足上文所述地理邻居构造的关键点。计算所有节点与目标节点的距离、方向，在45°扇形区域内，选择距离最近的名字解析节点作为目标节点的地理邻居节点，分别在8 个扇形区域查找目标节点8 个方向的地理邻居节点。此方法可以保证精确度最高，而精确度是地理邻居构造需考虑的关键因素。

3.2 评价指标

1）算法总用时

数据集中所有节点查找发现自身地理邻居节点并生成地理邻居列表的总运行时间。算法总用时可以直观地描述数据集在不同节点数量情况下运行时间的变化规律。

2）算法单节点平均用时

数据集中单个节点查找发现自身地理邻居节点并生成地理邻居列表的平均运行时间，为算法总用时与节点个数的比值。现场名字解析系统是典型的分布式系统，名字解析节点按需上线，各自生成自身地理邻居结构，故单点平均用时更能反映算法性能。

3）查全率

具体可定义如下：查全率=实际找到邻居节点个数∕理想邻居节点个数=实际找到邻居节点个数∕（节点个数×8）。用来评价解析节点查找地理邻居节点个数的准确率。

3.3 实验结果

参考上海市经济与信息化委员会在2020 年5 月公布的《上海市5G 移动通信基站布局规划导则》，结合现场名字解析系统中解析节点的部署与5G基站都有保障低时延的相似场景，5G 网络服务能级为A 级的基站平均站间距为150 m，平均密度为50 个∕km2，大致对应于现场名字解析系统中确定性时延为10 ms 的层级。不同的确定性时延需求对应于不同的站间距。同样，在对名字解析节点的地理位置进行Geohash 编码时，也会对应于不同的编码长度。该文实验选择对节点位置进行8 位Geohash 编码，精度在19 m 左右。Geohash 网格编码查找算法与对比算法搜索半径均设定为1 900 m，故Geohash网格编码查找算法中单一方向网格的搜索个数k为100。实验结果为不同节点数量情况下重复运行100次，记录两种算法的总运行时间，最后取平均值。由图2 可以看出，当总的节点数量在2 000 个以下时，两种算法运行时间相差不大。事实上从具体数据而言，2 000 个节点以内对比算法的运行时间优于Geohash 网格编码查找算法。但随着节点数量的增加，对比算法的运行时间增长速度远远高于Geohash网格编码查找算法。这个可以从算法本身的特性分析原因，随着节点数量不断增加，对比算法中每个目标节点与其他节点都要一一计算距离和角度，因此每个目标节点生成地理邻居节点的计算时间随着节点数量的增加而增加，那么整个数据集所有节点的总运行时间会以指数形式增长。而Geohash 网格编码查找算法单个节点生成地理邻居的过程，与数据集中节点的数量没有严格相关性。在最大搜索半径内找到符合要求的节点即停止搜索，超过最大搜索半径也会停止搜索，因此理论上单个目标节点的计算时间维持不变，总运算时间随着节点数量的增加按比例增加。

图2 不同节点数量算法总用时

根据图3，Geohash 网格编码查找算法单个节点的平均运行时间随总节点数量的变化没有明显变化，对比算法单个节点的平均运行时间随总节点数量的增加而增加。说明Geohash 网格编码查找算法单节点运行时间与节点数量无关，仅取决于该节点周围其他节点的分布状况。

图3 不同节点数量算法单节点用时

图4 表示Geohash 网格编码查找算法在几乎相同的查全率情况下，设置不同的搜索半径（即不同k值）时的算法运行时间。可以看出，k值越大，即搜索半径设置越大，运行时间也随之增加。算法本身在查找每个方向的地理邻居节点时，遵循找到即停止搜索的原则。那么查全率不变意味着增大了搜索半径，邻居节点数量并没有增加，由此得出运行时间的增加集中在了搜索某些没有地理邻居节点存在的方向上。通过查全率与搜索半径的对比分析，可以明确知道要在尽可能保证查全率的同时兼顾运行时间，就需要设置合适的搜索半径。

图4 Geohash网格编码查找算法相同查全率下不同k值运行时间对比

4 结束语

该文通过对Geohash 编码周边查找算法的改进，提出了基于Geohash 编码的现场名字解析系统地理邻居的发现方法，以适应现场名字解析系统的特殊场景。并且通过实验验证，与kNN 查询中改进的穷举法对比，该文提出的算法在小规模数据（节点数量2 000 个以下）中与对比算法运行时间差别不大，在大规模数据（节点数量2 000 个以上）情况下，算法平均耗时下降60%以上，且随着节点数量的不断上升，算法耗时下降比例会继续增加，显现出了明显的优越性。另外，该文所提算法运行时间与搜索半径有一定相关性，因此需要设置合适的搜索半径，以保证在较短的时间内尽可能多地找到目标节点的地理邻居节点，可以作为后续研究方向，设计更加合理的算法。