一种基于公共地标配置的云数据定位算法

李靖平

（黎明职业大学信息与电子工程学院，福建泉州362000）

近年来，随着云计算变得越来越流行，越来越多的用户将数据存储在云端。考虑到数据的安全性、存取效率、法律限制以及数据的可用性，对云端存储来说，数据的地理位置变得越来越重要［1］。例如，很多用户将隐私数据存储在云端，而这些数据仅期望能够存储在特定的区域或国家。为了获得更优的服务性能，用户在存储数据时，有时期望将数据存储在距离自身较近的地方。由于受到法律约束，很多数据仅能够存储在指定的国家。此外，有时用户为了保证其数据不受到如自然灾害造成的数据丢失等，需要将存储在位置A的数据，复制到位置B，但是云服务商是否真的按照用户的需求来存储数据，用户则无法确认。

尽管在用户和云服务提供商之间存在服务水平协议（SLA），可用于确定用户数据的位置，然而，有时云服务提供商会在用户不知情或未授权的情况下移动用户数据的存储位置，而且没有第三方机构监管云服务提供商的行为。因此，对用户而言，对能够自主定位存储数据的服务器位置的需求，变得越来越迫切，云数据定位技术可为用户定位其数据存储的位置提供帮助。

1 研究现状与问题提出

当前已有多种服务器地理位置定位方法，很多网站也对外免费提供IP地理位置查询服务，但是这些网站通常基于用户的注册信息构建数据库来提供查询服务，因此，查询结果不可靠，常常出现查询无结果的现象，且定位的精度较低［2］。基于延迟的定位方法是当前的研究热点，这些方法大多基于SPing、GeoPing和CBG算法的基本思想实现。下面分别详细介绍这三种方法的基本思想。

SPing算法［3］首先从多个地标向目标发起延迟测量，然后比较所有地标和目标之间的延迟大小，最后将与目标延迟最小的地标的位置作为目标的位置。这种方法所需地标的数量往往与目标所在区域的大小相关，对毫无先验知识的目标，通常需要部署大量的地标，且定位误差与距离目标最近的地标相关，因此，定位误差不可控，且对地标数量要求较高［5］。

GeoPing算法［3］自身维护了大量能够主动发起测量的主动地标和能够对测量数据包进行响应的被动地标。该算法首先从所有的主动地标向每个被动地标和主动地标发起延迟测量，从而对每个地标构建一个延迟向量，同理，对待定位目标，也可构建延迟向量，最后，通过比较目标和地标的延迟向量，将与目标延迟向量最相似的地标的位置作为对目标的定位结果。

CBG算法［4］是十分典型的多点定位算法，该算法的基本思想是：利用多个地标相互测量延迟和距离，对每个地标构建一个如图1所示的延迟和距离的转换关系，图1中的bestline线是延迟到距离的最优转换关系。利用bestline，将地标到目标的延迟转换为距离，从多个点对目标进行定位，如图2所示，其中L1、L2和L3为地标，T为待定位目标。

图1 延迟-距离关系分析

图2 多点定位基本原理图

上述三种方法中，SPing算法和GeoPing算法通常需要部署大量的地标［6］，且定位的误差不可控，CBG算法通常将所有的地标都用来对目标形成距离约束，尽管定位效果比较好，但是使用的地标数量比较大，而在所有使用的地标中，产生有效距离约束的地标往往数量较少，即现有CBG算法消耗了较大的地标资源。

2 基于地标配置的云数据定位算法

为了能够利用更少的地标实现对存储云数据的服务器进行地理定位，本文提出了基于公共地标配置的云数据定位算法，算法的基本原理框架如图3所示，具体步骤如下：

图3 算法基本原理框架

（1）收集现有对外提供服务的云主机实例构成原始地标集；

（2）利用原始地标集中的实例，相互测量延迟和计算两者之间的地理距离，对测量得到的数据进行延迟-距离分析，对每个地标计算其自身的bestline；

（3）对输入的待定位目标，从地标集中所有的地标对目标发起延迟测量，选取其中延迟最小的若干个地标（本文取3），作为最终需要使用的地标；

（4）从挑选出的地标，再次向目标发起多次延迟测量，取测量值中最小的延迟值作为最终的延迟测量结果；

（5）根据测量的延迟值和已得到的bestline，将每个地标测量的延迟转换为到目标的最远距离，从多个点对目标进行约束；

（6）计算距离约束的交集的中心作为对目标的最终的定位结果。

3 实验

为了验证提出的算法的性能，笔者开展了相关实验，下面分别介绍实验设置和实验结果。

3.1 实验设置

本实验使用亚马逊弹性计算云（EC2）中的实例作为地标，截止目前为止，亚马逊在美国的弗吉尼亚、俄勒冈州和加利福尼亚等拥有3个数据中心，在欧洲的爱尔兰和法兰克福拥有2个数据中心，在亚洲的新加坡、东京和悉尼拥有3个数据中心，在南美的圣保罗拥有1个数据中心。本文在上述地方启动实例，启动实例的配置如下：Ubuntu 64位系统，613MB RAM。

首先，在每两个地标之间，本文测试了多组延迟，并计算两者之间的地理距离，构建延迟和距离之间的转换模型。在测试延迟时，采用的是Ping工具。对每个地标来说，都测试了与其他地标之间的延迟和距离，利用这些数据构建延迟和距离的转换关系，计算其bestline。表1给出了实验中使用的9个地标（记为）的和值。

其次，将多个地标与目标服务器之间的延迟，根据分析得到的bestline转换关系，将延迟转换为距离，利用多点定位思想定位目标服务器的位置。本文在谷歌云端设置了虚拟机实例，位于美国东部地区，将该虚拟机作为提供数据存储服务的云端主机，并作为待定位目标。从每个地标测量到该虚拟机的延迟，并将该延迟转换为估计的地理距离，以地标的位置为圆心，转换后的距离为半径，对目标虚拟机产生距离约束，相应的距离约束值如表2所示。

表1 各地标bestline的斜率和截距

表2 各地标到目标的延迟和转换后的距离

由于本文的实验在美国开展，位于其他国家或地区的地标对目标形成的距离约束太大，因此，在选择地标时，仅选择位于美国的地标，即位于俄勒冈州、加利福尼亚和弗吉尼亚的地标来对目标进行多点定位。

3.2 实验结果

如图4所示，本文利用位于俄勒冈州、加利福尼亚和弗吉尼亚的地标L1、L2、L3对目标虚拟机T进行定位，T的实际位置位于美国俄克拉荷马州的梅斯县，通过上述步骤对T进行定位，定位结果位于堪萨斯州东部，如图4中的M所示，距离测量显示，M和T之间距离约为235 km，即定位误差约为235 km，与现有CBG算法利用更多个地标的定位误差相当。因此，本文算法在基本保持定位精度的同时，仅需要更少的地标数量。

图4 对位于梅斯县的目标定位结果

4 结论

对云数据进行定位越来越受到用户的重视。本文针对现有定位算法存在的维护私有地标开销较大问题，提出了基于公共地标配置的云数据定位算法，通过对公共地标进行配置，能够利用较少的地标对目标进行定位，且保持定位精度不降低。实验结果验证了该算法的有效性。在今后的工作中，将进一步对定位算法进行优化，以提高定位精度。