基于POI地标与路径相似度的IP定位研究

金弋然 陈永乐 姚青桦 陈俊杰

(太原理工大学信息与计算机学院 山西 太原 030024)

0 引 言

IP定位技术是一种通过设备的IP地址确定其地理位置的技术，在社交网络[1]、网络安全[2]和拓扑优化[3]等领域中起着关键作用。网络安全领域中，IP定位技术可以将用户账号与常用登录IP地址绑定验证是否存在IP欺诈、识别非人类流量，还可以用于系统监控，定位脆弱设备、追溯攻击、增强系统防护，以达到报警联动。此外，IP定位技术在车联网、工控物联网等系统中的定位与通信中起着关键作用。网络应用服务通常会根据用户的IP地址为用户提供定制化服务，例如即时通信软件向用户推送当地天气、新闻或附近的活动资讯。IP定位技术还可以应用于网络性能优化，网络代理服务商可以通过网络节点的物理位置优化通信线路，降低通信时延与系统开销，提升系统性能。因此，IP定位技术可以使许多应用程序更加深入地了解用户和客户来自何处，掌握用户的在线行为，从而增加应用程序的安全系数与衍生价值。

由于网络协议中没有IP地址与相应物理位置的内置关联，IP定位技术研究备受关注。IP定位技术可分为以下两大类[2]：一类是基于客户端的IP定位技术，依靠设备上搭载的蜂窝网络、Wi-Fi和GPS等辅助定位模块进行定位。这类技术可以实现高精度的IP定位，但受传播噪声影响较大，容易收到匿名扫描，安全性低，应用场景受限。另一类是独立于客户端的IP定位技术，包括基于推理估计[4]、时延测量[5]和网络拓扑[6-7]的定位方法。尽管后者定位准确性降低了，但这类技术实现简单，不依赖于特定的定位设备，有很好的扩展性。本文算法专注于基于网络测量单点探测的IP定位技术，不受限于硬件支持，简化探测工作，深度挖掘路径之间的相似关系，对网络环境影响较小，可以广泛应用于各类应用场景。

数字地图中的兴趣点(POI)具有准确的位置信息，可以有效转化为网络节点的地理位置。但是，如何将POI信息映射到IP地址和如何验证POI地标的可用性仍然是两个大挑战。本文采用POI数据来缓解地标匮乏的现象，设计了基于数字地图和搜索引擎的地标收集方法，分别从北京市和上海市获取了2 038和1 429个POI地标，远优于著名的PlanetLab[13]，该平台在全球范围内部署了547个地标设备。在此基础上，本文设计了一种基于路由路径相似度的IP定位方法，简称SBG算法。SBG算法设计了加权二维字符串子序列核算法(TDSSK)计算路径相似度，通过离群点检测聚类算法进一步优化街道级的定位结果，可以在一定限度上消除不良网络状态对定位算法的有害影响。本文实现了原型系统，并将SBG方法的性能与其他算法进行了比较。SBG算法性能更为稳定，定位精度更高，可以实现5.7 km的定位中值误差。

1 相关技术

独立于客户端的IP定位技术不需要任何辅助定位设备的支持，具有广泛的应用场景。本节简要介绍独立于客户端的IP定位技术。

基于推测估计的IP定位技术根据中间节点的DNS名称、公开主机名等信息实现城市级IP定位[15]。此类方法分为三类[2]：① 直接查询Whois数据库；② 通过测量主机名与数据库信息相结合进行推断；③ 利用网络结构和数据库信息进行推理。然而，大部分国家的网络路径中并不存在暴露名称的中间节点。该方法高度依赖于IP分配数据库或主机名等信息，存在局限性，无法进行高精度的IP定位[11]。同时，云服务器与内容分发网络(Content Delivery Network,CDN)的存在引入了噪声数据，使其应用场景有限。

基于时延测量的IP定位技术根据探测报文的传输时延来估计地标节点与目标节点之间的距离。Wang等[8]提出了一种以基于约束的IP定位技术(CBG)[9]为基础的街道级IP定位方法(SLG)。根据探测时延缩小定位范围，寻找距离公共路由节点最近(具有最小时延)的地标节点，将目标节点定位到该地标的位置。Jiang等[10]训练两层神经网络模型逐步定位目标IP，在美国实现了4.1 km的中值误差。Wang等[17]提出了一种基于公共路由节点的定位技术，使SLG算法的性能提高了9.5%。时延测量依赖于世界范围内的公共勘探资源，例如Rocketfuel[12]、PlanetLab[13]。然而，这类资源在国内极为匮乏。我国密集的人口组成和巨量的网络交互导致互联网上的交换机、路由器等中间设备数量众多[14]。路径中的转发排队时间与转发处理时间难以估计。其中，由于防火墙设备的存在，某些设备无法返回有效的探测信息。同时，基于时延测量的IP定位技术随网络环境动态变化。由于密集复杂网络中存在网络抖动、网络拥塞和数据包丢失等现象，这类技术不可避免地会引入测量误差。

基于网络拓扑的IP定位技术中，Wang等[8]发现通信时延只能提供粗粒度定位，提出了一种三层街道级(SLG)IP定位算法，其中：第一层使用了改进的CBG算法确定粗粒度的地理位置；第二层利用基于网站的大量节点将IP缩小定位范围，利用与路径中最近相同路由器之间的时延估计地标和目标IP之间的距离；第三层增加网站地标的数量，选择最短延迟估计目标节点的准确地理位置。Zhao等[20]基于路由路径的相似性和城市本地时延分布实现了9 km左右的误差，累积概率为80%。本文设计了基于拓扑结构的IP定位技术，可以很好地挖掘网络结构特征，对复杂网络环境有一定的鲁棒性。

2 算法设计

图1为基于POI地标与路径相似度的SBG算法的结构图。SBG算法分为两个阶段：第一个阶段是预处理，包括收集POI地标和构建路由路径指纹库，此阶段从数字地图中挖掘POI，通过搜索引擎将POI物理位置映射到IP地址以构建路径数据库，是SBG算法设计的数据基础；第二个阶段通过计算路径相似度并优化定位结果来进行IP定位，通过离群点检测算法删除噪声数据，计算聚类中心以推测目标IP的地理位置。

2.1 数据收集

作为IP定位的主要参考依据，地标节点的数量和可信程度直接影响IP定位的精度。例如PlanetLab[13]、PerfSONAR[18]和PingER[19]等平台提供已知IP地址和地理位置的公共地标节点。PlanetLab[13]是一个运行着1 353个节点和547个站点的网络测试平台，其中大多数节点为大学和研究机构。PerfSONAR[18]是一个提供联合路径与端到端连接期望的网络测量平台。该公共平台运营的节点十分有限，无法在中国支持高准确率的IP地理位置。因此，本文从数字地图中挖掘POI信息，并通过搜索引擎扩充其地理位置。

POI可代表一栋大厦、一家商铺或一处景点，包括了城市中的大部分功能场所。获取POI的基本思想是从电子地图服务中收集每个城市的POI，百度地图、高德地图、谷歌地图等地图公司均提供POI服务，可以通过请求相关的Restful接口获得。本文从数量、可靠性和可访问性三个方面评估POI的质量，如表1所示。其中，由于网站更新和地址变迁等更改，POI信息也在不断更新。因此，可靠性是评估POI质量的重要标准之一。本文收集并比较了不同地点3 000多个数据的正确性，发现对于国内的POI数据，高德地图和百度地图的时效性几乎没有差异。必应地图的错误率较高，谷歌地图也存在一定的误差。因此，从可靠性来讲，高德≈百度>Google>必应。此外，百度地图单接口最大返回条数为500个。如果检索整个城市的POI，将忽略大量的POI信息。这里，高德地图提供了城市和POI类型分类代码。单接口限制返回数量为900，优于其他地图服务。因此，就获取POI的难易程度而言，高德>百度>谷歌>必应。本文选择高德地图作为SBG算法的POI信息来源。其中，高德POI服务接口中的“websites”字段标识该POI的网站信息。

表1 POI数据来源评估

POI地标获取流程如算法1所示。其中，输出si为IP位置数据(IP地址，经纬度)，例如：(218.205.182.142，38.032013114.453689)。

算法1

输入：城市。

输出：S={s1,s2,…,sN}。

1. 检索遍历指定城市的POI列表，如果POI信息包括website字段跳至第2步，否则跳至第3步。

2. DNS解析website字段中的域名，若解析成功，记录该节点位置信息对，否则丢弃该POI条目。

3. 在搜索引擎中检索该POI信息，爬取检索结果列表中的前5个网页。如果主页中没有网站的机构地址，迭代爬取与“加入我们”“招聘”“联系我们”对应的URL。如果找不到该条目地址，则删除。

4. 循环至遍历完全部节点。

5. 删除关键字大量重复或同一公司的多个地址等大量重复节点。

6. 将Maxmind与IPcn数据库中均不在目标城市的节点标识为跨城市级云地标并删除。

7. 将路径时延转化为路径距离，丢弃与目标距离大于2.5 km的中间节点。

8. 寻找地标间的公共路由节点，若两地标节点之间、经由公共节点的相对距离大于5 km，将其丢弃，否则保留。

因为许多企业将网站部署到阿里云和亚马逊云等平台上，本文删除云服务器数据，如第6步所示。Maxmind[22]和IPcn[23]提供了城市级IP位置数据库。单个数据库的准确性和可靠性不高，例如Maxmind在中国的城市级定位的准确性仅为68%[22]。本文采用两个数据库进行双重验证，以获得更可靠的数据集。

本文使用基于公共路由器的方法[17]将相对位置误差限制在5 km之内，验证网站的实际位置，如第7步-第9步。为验证地标的正确性，本文引入公共中间节点，使用4c/9(c是光速)作为通信时延和地理距离之间的转换系数[8]，计算相对距离。丢弃与地标相距超过2.5 km的公共路由。这类设备可能是三级或四级间接转发设备。同时，将距共同路由设备2.5 km内的地标视为靠近公共路由设备。

本文基于高德POI信息收集了北京和上海的地标数据。如表2所示，POI方法可以收集成千上万个地标节点。数据清理后，在北京市和上海市分别获得了2 038和1 429个可用地标，可用作街道级IP定位的数据基础。

表2 地标数据采集结果

与全球范围内部署547个设备的PlanetLab平台相比，本文可以在一个城市中收集数千个可用的地标数据。图2是数据清洗后北京市和上海市的地标节点分布热力图，颜色越深表示节点密度越大。不难发现，地标在城市核心区域具有较高的分布密度，在科技公司较少的郊区分布较为稀疏。

2.2 建立路由路径数据库

本文使用Ping指令探测存活POI设备，Traceroute(UDP/ICMP)、Paris-Traceroute工具记录探测路经序列。其中，Traceroute通过发送UDP报文、分析ICMP差错报文定位主机和目标IP之间的路径。Paris Traceroute[24]通过更改报文头部字段来保证单次探测内的探测报文遵循相同的路径，例如修改ICMP报文中的协议标识符和序列号的组合字段。下面将探测统称为Traceroute。

由于网络传输过程中的波动，路由路径长度是动态变化的。实验证实，Traceroute探测路径上的路由跳数大多数在20跳附近或以下。因此本文将探测过程中的最大跳数设置为30跳，以减少由网络数据包丢失、网络拥塞引起的无效检测。

本文间隔两天对3 000多个地标发起了两次Traceroute探测，并分析了路由路径长度的变化。如图3所示，横轴表示第一次探测的路径长度，纵轴表示第二次探测的路径长度。颜色的灰度表示两次探测路径长度的对比分布。颜色越深，两次探测中该路径长度出现的次数越多，参照右侧颜色栏。由图可知，两次探测的路径长度大多集中在8跳至20跳之间。实验数据大多接近等分线(y=x)，即路径长度在1跳或2跳内的变化占很大比例。此外，本文发现一部分长度为30的路径中，实际有效路径长度不到10跳。路径后半段全部是星号。探测路径中的星号表示无效数据，由网络数据包丢失、对探测数据包无响应、防火墙屏蔽等原因导致。为建立更加完整的地标路径指纹数据库，本文多次收集探测路由路径，过滤无效数据。对于已收集的3 467个地标样本，本文丢弃128条无效路由路径。

图4为两次探测中路径相似性的比较。横轴表示路由路径长度，纵轴表示路由路径的相似度。图4(a)仅比较IPv4地址的前三个网段，图4(b)比较完整的IPv4地址。匹配完整地址时，路径相似度平均约为60%。只匹配前三个网段时，相似度显著提高。这是因为网络负载均衡导致多个中间路由节点的IPv4地址的最后一个网段有所不同。即使探测相同的目标节点，路径的相似性普遍还是不能达到100%。因为探测过程一次只发送三个数据包。而候选路由线路的数量可能大于三个，路径可能会随时间变化。本文利用IPv4地址的前三个网段作为指纹来计算相似度，提高路由路径的稳定性。同时，由于POI和动态IP的变化，应该不断更新地标和路由路径。以两周的间隔足收集数据、更新指纹，可以有效地保证定位的时效性。

2.3 路径相似度算法

假设当两IP的地理位置很近时，其路由路径具有一定的相似性。探测路径上距离目标节点越近的节点在路径相似度中具有越大的权重。为验证该假设，本文探测300个地标进行交叉验证，如图5所示。折线表示出口节点(路径上目标节点的前一跳节点)相同时，目标节点之间距离变化的累积分布函数。不难发现，出口节点相同时，两个目标IP之间距离在12公里之内的概率超过90%。出口节点相似度与目标IP距离之间存在正相关的关联关系。此外，图中散点图表示出口节点相同时，目标IP之间距离分布的散点图。可以发现目标IP之间的路径相似性越高地理位置越近。这里，利用IPv4地址的前三个网段计算路径相似度的结果中存在一些异常值，可能是不同运营商导致的边缘网段的位置误差。实验表明，路径相似度与目标节点之间的距离相关联。路径上的节点距离目标节点越近，在相似度测量中的权重越大。SBG算法通过量化路径相似度，放大这些相关关系。

即使目标IP与地标的路径相似度远大于其他节点，也不能保证两者一定具有相近的地理位置。只基于路径相似度的IP定位是不准确的。为解决这一问题，本文深度挖掘路经相似性关系，提出了加权二维字符串子序列核(Two Dimension String Subsequence Kernel，TDSSK)算法，通过计算路径相似度定位目标节点。

TDSSK算法改进了传统的字符串子序列内核(String Subsequence Kernel，SSK)算法。SSK算法使用余弦相似度计算两个字符串的相似度，认为连续序列具有较高的权重。这符合路由转发的传输规则。实验表明，靠近出口节点的相似序列对定位结果的影响更大。同时，网段相似性可能引入较远的地理位置，因此需要改进相似度的计算。相连匹配节点的相似概率大于不相连序列，需要为连续序列设置更高的权重。极端情况下，如果路径上的相同节点为首尾节点，路径之间相似可能性较低。因此，本文为TDSSK算法设计了一个递减权重模型进行拟合。计算Kernel时，本文不仅考虑连续序列的权重，还考虑距离出口节点远近的权重序列。具体权重设计规则如下：

Ratei>Ratei+1&&Ratei

(1)

式中：i是序列中距离目标节点i跳的中间节点；Rate表示节点的权重级别，值越大表示权重越高。规则设计依据如下：离目标IP越近权重越大；第i个节点的权重小于邻接连续节点的权重。本文将上述原理拟合至SSK算法。TDSSK算法首先生成长度k为1和2的子序列向量空间，拟合序列权重递减模型计算子序列之间的相似度。

如图6所示，加权TDSSK算法中的序列权重递减模型有两个目标节点IP1和IP2。a1到a13是探测节点和目标节点之间的路由路径。如果两个路径中的同一位置均包含有效节点，则两处都有值；如果仅存在一个节点，则另一个置零。例如，IP1的路由路径包括a3节点，而IP2的路径中没有该节点的信息，置为0。

图6中λ是SSk算法中的衰减因子，代表两个相同子序列的距离。λ在相邻子序列之间迭代衰减，用来表示具有不同距离的相似子序列的相似度衰减情况。εi是序列递减系数，表示处于不同位置的节点在整体路径相似度中的不同权重，即式(1)中的Ratei。随着中间节点与目标节点之间跳数的增加，两个节点之间的地理距离呈指数增长，即与目标节点的不相关性呈指数增长。本文使用高斯函数设置序列减小系数，如式(2)所示。其中，n是路由跳数的总数，x是距离出口节点的跳数。这里，10是用于计算权重的放大因子。例如，节点a13对应的ε1为1.064 4；节点a12对应的ε2为0.948。

(2)

TDSSK=Sssk1+Sssk2=

(3)

2.4 IP定位及其优化

本文设置相似度阈值过滤低相似度节点，并过滤其中的离群点，计算集合中心估算目标IP的最终地理位置，如算法2所示。

算法2

输入：目标IP。

输出：定位结果——经纬度(x,y)。

1. 遍历地标路径集合，切割路径，保留目标城市两跳后路径。

2. 计算衰减序列εi，计算目标节点与地标节点之间的一维SSK、二维SSK以及TDSSK相似指数。

3. 如果相似地标集合中地标节点小于10且包含相似度极值时，直接根据极值点确定目标IP位置；否则计算离群点检测数量阈值Index2，去除离群点。

4. 计算集合中心估算目标IP物理位置。

(1) 设置相似度阈值。在目标节点与所有地标节点的匹配过程中，存在大量无关地标。SBG算法设置阈值去除此类节点。一方面，如果探测路径长度较短，到达目标城市之前的路径会大范围重复。这些路径高度相似，地理位置并不相近，设置阈值可以避免此类问题。另一方面，对于有限的地标集，阈值过高会导致符合条件的节点数量很少，无法准确定位。

本文为2 000个节点选择不同阈值进行过滤，考察目标IP对应的候选地标数量，如图7所示。阈值1-3表示到达目标城市后路径上的1-3跳，横轴表示具有不同候选地标数量的目标IP的数量，纵轴表示地标候选集中超过阈值的节点数量。由图可知，选择城市后一跳作为阈值时，获得的地标数量最多。过滤后，只有93个IP的候选地标节点的数量少于30个。此外，阈值为城市后三跳时，地标的数量明显减少。地标数量大于50的节点数少于全部节点的一半。探测路径较短时，该阈值将过滤大量有效数据。因此，将阈值设置为城市后两跳是中立的，满足了相似性和节点数之间的折中。不仅考虑了过滤无关节点的准确性，还可以保证过滤后的地标数量。因此，SBG算法选择从城市后两跳的阈值过滤地标节点。

报文从探测节点所在的城市出发，经由骨干网络转发，进而在目标城市内路由。探测路径上的单跳时延遵循“低-高-低”(城市内-城市间-城市内)分布[21]。城市内部路由设备之间的距离通常很短。不考虑网络拥塞的情况，单跳高延迟通常是由物理距离过长或报文转发队列排队引起的。本文利用这个规律提取目标城市后的路由路径。

本文使用加权TDSSK算法计算路径相似度值，对比不同起始节点对定位结果的影响，如图8所示。横轴为TDSSK相似指数，纵轴为对应的地标节点与目标IP之间的误差距离。其中，图8(a)将阈值(起始节点)设置为城市后一跳计算相似度，图8(b)为城市后两跳。由图8可知，城市两跳比城市后一跳具有更好的性能。另一方面，离散点表示数据中的离群点。两幅图都有较多的干扰数据。因此，离群检测是定位优化中非常重要的一环。同时可以看出，相似度越大距离越近只是一个大趋势。例如在定位某IP时，相似度大小第十的地标可能比具有最高相似度的地标更接近目标IP节点。因此，仅根据相似度的高低定位会导致很大的误差。本文选择具有较高相似性的地标集合定位IP。

(2) 清洗定位地标。SBG算法选择一个相似地标集合，通过离群点检测方法去除噪声点。SBG算法在设计离群值检测算法时比较了局部异常因子(Local Outlier Factor,LOF)算法、基于距离的累积和(Distance-Based)的离群点检测算法和半径领域算法(Circle-based)。

LOF算法是一种基于密度去除离群点的算法[16]。该算法计算每个点到其他点的球面距离并排序，然后计算每个点的局部相对密度。值越小代表密度越小，意味着该点很可能是一个离群点。LOF值小于1的点通常是离群点。

本文设计了基于距离累加和的离群点检测算法，计算某点到所有其他点的球面距离累加和。如式(4)所示，N为相似地标集，o′表示除o点外所有的点。总和越大表示该点距离其他点距离越远，越有可能是离群点。此外，本文设计了半径领域离群点检测算法。每个点都以固定半径r画圆，通过圆内包含其他点的数量来判断该点是否为离群值，如式(5)所示。如果数目较少，则将该点视为离群点。对于给定的数据集，需要指定半径r定义合理的邻域与数量阈值π确定是否为离群值。

(4)

(5)

上述离群点检测方法检测通用数据集只需要设置一些自定义参数即可。在IP定位的场景下，面对不确定的位置分布数据，选用何种方法、如何设定合适的参数值是决定算法性能的主要因素。考虑到集合的离散程度，SBG使用Grubbs思想，结合标准差、中位数和经验系数三个属性智能设置每个集合的距离阈值。距离累加和算法结合中位数(Med)和标准差(Std)计算阈值Index1，如式(6)所示。若累积和大于Index1，则删除该离群点。半径领域法为每个节点选择较大的半径，计算半径圆包含点的数量并逆序排序，计算Index2，如式(7)所示。小于Index2的值点为异常值。该选取规则考虑了集合整体的离散程度(标准差)，在最大程度上保证了数据的完整性。实验发现，当r=6，rate=1.6时，离群点检测效果最佳。

Index1=Med+rate×Std

(6)

Index2=Med-rate×Std

(7)

本文随机选取一个目标IP，对生成的地标相似集合进行离群值检测。如图9所示，去除异常值后能够生成更准确的定位结果。但在特殊情况下仍存在误差，例如：IP位于偏远位置、地标数量较少时，移除的异常值可能是最接近目标的位置，造成较大误差，此时可使用相似度极值直接位置。

3 实验结果与分析

本文实验使用部署在阿里云上的一台云服务器分别对北京、上海两个城市进行测量，获取了2 038个和1 429个可用的POI地标节点。然后，从这些地标节点集中随机选择测试目标，采用Common Router和SLG的性能评估指标，对SBG算法进行评估。

3.1 不同离群点检测算法的影响

不同离群值检测算法对定位精度有不同的影响。地标数量也会影响定位算法的性能。本文实验以北京市地标集合为对象，讨论三种离群值检测方法的性能，随机提取500个地标节点，然后以250个地标的增量梯度增加，将SBG算法与三种离群点检测算法结合进行IP定位，如图10所示。随着地标数量的增加，定位误差减小。大量可靠的地标数据可以提供更有效的信息使得IP定位更加准确。其中，SBG-Circle方法可以实现最好的定位精度。

本文对北京和上海2 000个地标进行定位。图11为定位误差的累积分布函数。三种算法整体上误差相近。半径领域算法的中值误差最优，收敛速度快于其他两种方法，整体误差距离在18 km附近收敛。尽管LOF算法总体表现一般，但是开始阶段的性能优于其他方法。同时，LOF收敛的速度相对较慢，这表明该方法具有较大的方差。半径领域算法的性能相对稳定。本文使用半径领域法去除异常值。因此，SBG算法又称为SBG-Circle算法。

3.2 地标密度对IP定位性能的影响

本节说明了地标密度与定位误差之间的关系。目标IP附近的地标数量越多，可以更准确地识别出更多相似候选节点。本文利用半径分别为1 km、3 km、5 km和8 km的候选领域，研究了不同地标密度变化下定位精度的变化趋势。如图12所示，同一半径圆中，定位误差随地标密度的增加而逐渐减小。相同密度条件下，在不同半径的圆上，地标节点的数量随半径增加而增加，定位误差随之下降。

如图12所示，半径为8 km时，地标数最大，定位误差最小，中位误差约为2.7 km。无论半径如何变化，随着地标分布密度的增加，三种IP定位算法的定位精度都会提高。同时，实验表明SLG算法和Common-Router算法的定位误差始终大于SBG算法。

3.3 SBG算法性能

本文选择北京市和上海市的3 339个地标作为目标节点，将SBG算法与SLG和Common Router两种算法进行比较。图13是定位误差的累积分布概率图。SBG算法在18 km处收敛，其他两种算法分别在35 km和48 km处收敛。此外，SBG算法的中值误差约为5.7 km，算法性能远好于国内现有的IP定位算法。特别是，SBG算法的长尾比其他两种算法占比低。这表明SBG算法的性能相对稳定，对实际网络的适应能力更好。

百度智能定位服务是目前国内较为成熟的定位服务。与SBG算法相比，百度高精度IP定位服务依赖卫星定位系统，需要定位辅助硬件设备，具有局限性；百度低精度IP定位服务只能实现城市级定位，经纬度坐标一般为城市中心点的坐标，定位误差较大。因此，与目前流行的定位服务相比，SBG算法依据单点测量技术，对实验环境的要求不高，具有较好的普适性，可以显著的提升定位精度，可以广泛应用于IP定位的应用场景。

4 结 语

本文提出了一种基于POI地标与路径相似度的SBG算法，以实现高精度IP定位。从数字地图和搜索引擎收集POI地标后，本文设计了路径相似度计算算法和离群点检测算法，实现了约为5.7 km的中位定位误差。实验验证了地标数量和分布密度对IP定位算法具有一定的影响。本文将SBG算法与现有的SLG算法、Common-Router算法、百度智能定位服务进行了比较。实验表明，SBG算法具有更稳定的性能，可以实现更高的定位精度。未来工作将专注于收集更可靠的地标，以提高定位的准确性，并分析其位置分布。