◆刘渊博 甘勇 张鹤林 贾东伟

基于拓扑路径聚类的城市级地标评估方法

◆刘渊博1甘勇1，2张鹤林1贾东伟1

（1.郑州轻工业大学（郑州） 计算机与通信工程学院 河南 450002；2.郑州工程技术学院（郑州） 河南 450044）

从IP位置数据库中获得城市级地标，是地标获取的最直接的方法。但由于当前IP位置数据库存在初始数据来源不明、数据库构建方法不公开及地标可靠性低的问题，为此本文提出了一种基于拓扑路径聚类的城市级地标评估方法，通过对IP2Location数据库中地标的存活性探测，以北京、上海、纽约、东京四个城市为例获取数据库中在线地标的拓扑路径，并将排序后的IP地址映射到路由器空间中，使用K-Means算法进行聚类，实现对地标的可靠性评估。实验结果表明，评估后的地标可靠性提高了15%以上，可用于支撑高可靠定位。

拓扑路径探测；地标评估；聚类算法

网络实体定位技术是利用已知IP标识的网络实体设备来确定其地理位置，它可以用来提高网络空间的安全，优化网络性能以及提供基于位置的服务等[1]。现如今，网络实体地标作为定位技术所需的关键数据，主要有两类：城市级地标和街道级地标，本文主要关注城市级地标。网络实体地标是将网络实体映射到地理位置的基准点，根据现有的研究进展，国内外一些研究机构组织并构建了IP位置数据库，如Whois[2]、MaxMind[3]、IP2Location[4]、百度[5]等。在上述数据库中，此类地标多用于实验研究，实验通常选取交集，即选取多个位置数据库中地理位置一致的IP 地址[6]。但是该方法存在很多限制条件，数据来源不准确、可靠性差等问题都会影响定位技术的准确率，因此从IP 位置数据库直接获取地标的方法需要更进一步的研究改进。

1 相关工作

针对当前IP位置数据库存在的问题有很多学者做了大量研究，文献[7]提出了一种基于Internet论坛的城市级地标获取算法，明显提高了城市级网络实体地理的准确率。文献[8]提出了一种基于投票的城市级地标评估方法，该方法分析了中国大陆不同地理粒度的IP地址和数据块的分布和特征，并进行了比较，最后得到初步评估结果。文献[9]提出了一种城市级地标评估方法GeoCop（Geolocation Cop），利用边缘路由器关联的候选地标，进行位置投票确定路由器的位置，从而实现数据库中城市级地标的评估。文献[10]提出了一种基于路由识别的城市级地标评估算法，有效减少了路由器标识的开销，城市级地标的准确率也更高。文献[11]提出了基于 POP 网络分析的城市级地标评估方法，该方法根据节点的位置来进行准确性评估，评估结果可靠且效率高。综上，结合路由器、POP网络、多库查询的城市级地标评估方法在一定程度上提高了地标的准确率，但这些方法在数据量不足的情况下是无法进行有效评估的。

2 本文基本原理及主要步骤

本文首先对数据库中声称位于同一城市的在线IP进行网络路径测量，获得从探测源到各IP的网络路径；其次提取各IP网络路径上的路由器，将所有路径上的路由器进行排序，并以排序结果为基准构建多维路由器空间；其后根据IP的拓扑路径，将IP映射到路由器空间中，并使用K-Means算法对IP进行聚类，得到多个聚类簇；最后，依据数据库的平均准确率选择可靠的IP簇。主要分为以下几个过程：

2.1 路由器排序

若：

分组内排序：

分组间排序：

去重：

2.2 路径聚类

利用构建的路由器空间及各IP的探测路径，将各IP映射到路由空间中，并使用K-Means方法对IP进行聚类。在使用K-Means聚类时，需要首先指定聚类值。本文使用elbow-method获得聚类的最优值为128，在最优值下使用K-Means方法对IP进行聚类。SSE（Sum of the Squared Errors，误差平方和）是elbow-method的核心指标：

其中，是簇的个数，是第个簇，是簇中的点，m是簇中心。

在使用最优值聚类得到的个簇中，统计每个簇中属于同一C类网的节点数，计算与该C类网中在线IP数量的比值：

若：

在筛选可靠簇时，将每个簇中的所有IP都是可靠的，则该簇为可靠簇。在得到可靠簇后，将簇中节点对应的IP与城市的地理位置相关联，得到可靠地标，从而实现对地标的可靠性评估。

3 方法分析

要实现数据包在网络中的快速准确转发，路由器需要稳定、简单的路由表。为此，ISP（Internet Service Provider，互联网服务提供商）通常使用CIDR（Classless Inter Domain Routing，无类别域间路由选择）策略来减轻互联网上路由器的负担，同时，ISP通常采取稳定的路由策略（即对同一IP开展两次路由测量，两次测量的路径相同）来提高路由器的转发效率。这使得同一区域的网络实体，其IP地址在网络拓扑上也体现出区域性。本文方法利用这一特点，基于待评估地标在网络空间上的路径相似性，实现地标评估。

3.1 网络路径与地理位置相似性分析

当前网络构架大致可分为分层和网状两种，如下图1所示。

图1 两种网络架构

无论是分层架构还是网状架构，当从同一探测源出发，到两个IP所经过的路由相似时，说明从探测源到IP所经过的路径大致相同，路径的相似程度越高，说明两个IP的探测路径上，最后一个相同的路由器距离IP越近。当两个IP所具有的最近路由器到IP的跳数越小，根据CIDR策略可知，这两个IP在地理空间上的位置越接近。

3.2 路由稳定性分析

为分析网络中的路由稳定性，本文使用探测源“8.210.164.165”对目标IP“103.1.8.254”进行了网络路径测量。探测源每间隔10秒对目标发起一次路由测量，整个路由测量持续24小时，得到8640条路径，包含5条不同路径，各路径所占的比例如下图2所示。

图2 各探测路径占所有路径的比例

由图2可知，在对网络中的目标进行网络测量时，超过95%的数据包经相同的路由器进行转发，这表明网络中的路由是稳定的。

4 实验

4.1 数据源

VP S探测源：8.210.164.165，位于中国香港，配置为Ubuntu 16.04，4核CPU，16G内存，10M带宽。

待评估IP段：北京、上海、纽约、东京，每个城市选择8个B类网段。

可靠地标：用于验证评估后地标的可靠性，北京、上海、纽约、东京四个城市，每个城市100个可靠地标。

4.2 实验环境

实验环境为Ubuntu 16.04，32核CPU，512G内存，2*2080Ti显卡，Python 3.7。

4.3 实验方法

分别对北京、上海、纽约、东京的8个B类IP网段进行存活性探测，得到各城市存活IP数量如表1所示。

表1 各城市IP存活情况

对四个城市的存活IP进行网络路径测量，对每个城市的每个B类网段，分别构建路由器空间，并将对应网段中的存活IP映射到路由器空间上。

4.4 实验结果

利用上述方法中得到的最优k值，在每个城市的每个B类网段中，进行IP路径探测，将IP地址映射到路由器空间后，使用K-Means聚类方法对IP地址进行聚类。在每个聚类簇中，统计属于同一C类网段的IP地址数量，并计算该IP数量值与存活性探测结果中该C类网段中的存活IP数之比。将可靠簇中的IP与城市位置相关联，则该地标为可靠地标，各城市的可靠地标数量如表2所示。

表2 各城市可靠地标数量

从表2可以看出，评估后的可靠地标占比大于85%，该值相比于数据库的可靠性70%，提高了15%以上。

为验证评估后地标的可靠性，在北京、上海、纽约、东京四个城市分别使用评估后的地标对100个已知地理位置的IP进行城市级定位。城市级定位方法如下：从同一探测源，分别对目标和地标进行网络拓扑探测，获得网络路径。从探测源到目标和地标的网络路径上，提取最后3跳路由器IP构成集合RT和RL，若RT与RL的交集不为空，则成功对目标实现城市级定位，当城市级定位结果与目标实际城市位置相同，意味着对目标实现了准确定位。各城市的定位测试结果如表3所示。

表3 目标城市级定位测试

由表3得出，使用评估后的地标对目标进行城市级定位时，所有成功定位IP均被准确定位，定位准确率超过95%。由于定位准确率依赖于地标可靠性，因此，该实验从侧面印证了本文评估方法的有效性。上述实验测试结果也表明了本文提出的方法能够有效对在线地标的城市级位置进行评估，评估后的地标能够用于支撑网络目标的可靠定位。

5 结束语

本文基于IP拓扑路径上的相似性，使用K-Means聚类方法将IP进行聚类，从而实现对IP位置数据库中在线IP的可靠性评估，实验结果表明，本章方法评估后的可靠地标比例较数据库的可靠性，提高了15%以上，使用评估后的可靠地标进行定位，城市级定位准确率达到95%以上。

[1]王占丰，冯径，邢长友, 等. IP 定位技术的研究[J].软件学报，2014.

[2]Whois. IP require. www.whois.com.

[3]IP2Location. http://www.ip2location.com/.

[4]MaxMind. http://www.maxmind.com/.

[5]Baidu. http://lbsyun.baidu.com.

[6]邢子娟. 基于多点路由器测量的IP定位方法研究与实现[D]. 东南大学，2019.

[7]Guo C，Liu Y，Shen W，et al.Mining the Web and the Internet for Accurate IP Address Geolocations[C].IEEE INFOCOM 2009.IEEE，2009：2841-2845.

[8]Li H，He Y，Xi R，et al.A Complete Evaluation of the Chinese IP Geolocation Databases[C].International Conference on Intelligent Computation Technology and Automation.IEEE，2016：13-17.

[9]Wang T，Xu K，Song J，et al.An Optimization Method for the Geolocation Databases of Internet Hosts Based on Machine Learning[J].Mathematical Problems in Engineering，2015（10）：1-17.

[10]Ma T，Liu F，Zhang F，et al.An Landmark Evaluation Algorithm Based on Router Identification and Delay Measurement[C].International Conference on Artificial Intelligence and Security.Springer，Cham，2019：163-177.

[11]Shavitt Y，Zilberman N.A Geolocation Databases Study[J].IEEE Journal on Selected Areas in Communications， 2011，29（10）：2044-2056.

[12]Manaf Gharaibeh，Anant Shah，Bradley Huffaker，et al.A Look at Router Geolocation in Public and Commercial Databases[C].Proceedings of ACM International Conference on Internet Measurement Conference，2017：463-469.

2018年重点联合基金项目图像隐蔽通信的行为发现与主体定位关键问题研究（U1804263）