一種基于公共地標配置的云數(shù)據(jù)定位算法

李靖平

（黎明職業(yè)大學(xué)信息與電子工程學(xué)院，福建泉州362000）

近年來，隨著云計算變得越來越流行，越來越多的用戶將數(shù)據(jù)存儲在云端。考慮到數(shù)據(jù)的安全性、存取效率、法律限制以及數(shù)據(jù)的可用性，對云端存儲來說，數(shù)據(jù)的地理位置變得越來越重要［1］。例如，很多用戶將隱私數(shù)據(jù)存儲在云端，而這些數(shù)據(jù)僅期望能夠存儲在特定的區(qū)域或國家。為了獲得更優(yōu)的服務(wù)性能，用戶在存儲數(shù)據(jù)時，有時期望將數(shù)據(jù)存儲在距離自身較近的地方。由于受到法律約束，很多數(shù)據(jù)僅能夠存儲在指定的國家。此外，有時用戶為了保證其數(shù)據(jù)不受到如自然災(zāi)害造成的數(shù)據(jù)丟失等，需要將存儲在位置A的數(shù)據(jù)，復(fù)制到位置B，但是云服務(wù)商是否真的按照用戶的需求來存儲數(shù)據(jù)，用戶則無法確認。

盡管在用戶和云服務(wù)提供商之間存在服務(wù)水平協(xié)議（SLA），可用于確定用戶數(shù)據(jù)的位置，然而，有時云服務(wù)提供商會在用戶不知情或未授權(quán)的情況下移動用戶數(shù)據(jù)的存儲位置，而且沒有第三方機構(gòu)監(jiān)管云服務(wù)提供商的行為。因此，對用戶而言，對能夠自主定位存儲數(shù)據(jù)的服務(wù)器位置的需求，變得越來越迫切，云數(shù)據(jù)定位技術(shù)可為用戶定位其數(shù)據(jù)存儲的位置提供幫助。

1 研究現(xiàn)狀與問題提出

當前已有多種服務(wù)器地理位置定位方法，很多網(wǎng)站也對外免費提供IP地理位置查詢服務(wù)，但是這些網(wǎng)站通?；谟脩舻淖孕畔?gòu)建數(shù)據(jù)庫來提供查詢服務(wù)，因此，查詢結(jié)果不可靠，常常出現(xiàn)查詢無結(jié)果的現(xiàn)象，且定位的精度較低［2］。基于延遲的定位方法是當前的研究熱點，這些方法大多基于SPing、GeoPing和CBG算法的基本思想實現(xiàn)。下面分別詳細介紹這三種方法的基本思想。

SPing算法［3］首先從多個地標向目標發(fā)起延遲測量，然后比較所有地標和目標之間的延遲大小，最后將與目標延遲最小的地標的位置作為目標的位置。這種方法所需地標的數(shù)量往往與目標所在區(qū)域的大小相關(guān)，對毫無先驗知識的目標，通常需要部署大量的地標，且定位誤差與距離目標最近的地標相關(guān)，因此，定位誤差不可控，且對地標數(shù)量要求較高［5］。

GeoPing算法［3］自身維護了大量能夠主動發(fā)起測量的主動地標和能夠?qū)y量數(shù)據(jù)包進行響應(yīng)的被動地標。該算法首先從所有的主動地標向每個被動地標和主動地標發(fā)起延遲測量，從而對每個地標構(gòu)建一個延遲向量，同理，對待定位目標，也可構(gòu)建延遲向量，最后，通過比較目標和地標的延遲向量，將與目標延遲向量最相似的地標的位置作為對目標的定位結(jié)果。

CBG算法［4］是十分典型的多點定位算法，該算法的基本思想是：利用多個地標相互測量延遲和距離，對每個地標構(gòu)建一個如圖1所示的延遲和距離的轉(zhuǎn)換關(guān)系，圖1中的bestline線是延遲到距離的最優(yōu)轉(zhuǎn)換關(guān)系。利用bestline，將地標到目標的延遲轉(zhuǎn)換為距離，從多個點對目標進行定位，如圖2所示，其中L1、L2和L3為地標，T為待定位目標。

圖1 延遲-距離關(guān)系分析

圖2 多點定位基本原理圖

上述三種方法中，SPing算法和GeoPing算法通常需要部署大量的地標［6］，且定位的誤差不可控，CBG算法通常將所有的地標都用來對目標形成距離約束，盡管定位效果比較好，但是使用的地標數(shù)量比較大，而在所有使用的地標中，產(chǎn)生有效距離約束的地標往往數(shù)量較少，即現(xiàn)有CBG算法消耗了較大的地標資源。

2 基于地標配置的云數(shù)據(jù)定位算法

為了能夠利用更少的地標實現(xiàn)對存儲云數(shù)據(jù)的服務(wù)器進行地理定位，本文提出了基于公共地標配置的云數(shù)據(jù)定位算法，算法的基本原理框架如圖3所示，具體步驟如下：

圖3 算法基本原理框架

（1）收集現(xiàn)有對外提供服務(wù)的云主機實例構(gòu)成原始地標集；

（2）利用原始地標集中的實例，相互測量延遲和計算兩者之間的地理距離，對測量得到的數(shù)據(jù)進行延遲-距離分析，對每個地標計算其自身的bestline；

（3）對輸入的待定位目標，從地標集中所有的地標對目標發(fā)起延遲測量，選取其中延遲最小的若干個地標（本文取3），作為最終需要使用的地標；

（4）從挑選出的地標，再次向目標發(fā)起多次延遲測量，取測量值中最小的延遲值作為最終的延遲測量結(jié)果；

（5）根據(jù)測量的延遲值和已得到的bestline，將每個地標測量的延遲轉(zhuǎn)換為到目標的最遠距離，從多個點對目標進行約束；

（6）計算距離約束的交集的中心作為對目標的最終的定位結(jié)果。

3 實驗

為了驗證提出的算法的性能，筆者開展了相關(guān)實驗，下面分別介紹實驗設(shè)置和實驗結(jié)果。

3.1 實驗設(shè)置

本實驗使用亞馬遜彈性計算云（EC2）中的實例作為地標，截止目前為止，亞馬遜在美國的弗吉尼亞、俄勒岡州和加利福尼亞等擁有3個數(shù)據(jù)中心，在歐洲的愛爾蘭和法蘭克福擁有2個數(shù)據(jù)中心，在亞洲的新加坡、東京和悉尼擁有3個數(shù)據(jù)中心，在南美的圣保羅擁有1個數(shù)據(jù)中心。本文在上述地方啟動實例，啟動實例的配置如下：Ubuntu 64位系統(tǒng)，613MB RAM。

首先，在每兩個地標之間，本文測試了多組延遲，并計算兩者之間的地理距離，構(gòu)建延遲和距離之間的轉(zhuǎn)換模型。在測試延遲時，采用的是Ping工具。對每個地標來說，都測試了與其他地標之間的延遲和距離，利用這些數(shù)據(jù)構(gòu)建延遲和距離的轉(zhuǎn)換關(guān)系，計算其bestline。表1給出了實驗中使用的9個地標（記為）的和值。

其次，將多個地標與目標服務(wù)器之間的延遲，根據(jù)分析得到的bestline轉(zhuǎn)換關(guān)系，將延遲轉(zhuǎn)換為距離，利用多點定位思想定位目標服務(wù)器的位置。本文在谷歌云端設(shè)置了虛擬機實例，位于美國東部地區(qū)，將該虛擬機作為提供數(shù)據(jù)存儲服務(wù)的云端主機，并作為待定位目標。從每個地標測量到該虛擬機的延遲，并將該延遲轉(zhuǎn)換為估計的地理距離，以地標的位置為圓心，轉(zhuǎn)換后的距離為半徑，對目標虛擬機產(chǎn)生距離約束，相應(yīng)的距離約束值如表2所示。

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

表2 各地標到目標的延遲和轉(zhuǎn)換后的距離

由于本文的實驗在美國開展，位于其他國家或地區(qū)的地標對目標形成的距離約束太大，因此，在選擇地標時，僅選擇位于美國的地標，即位于俄勒岡州、加利福尼亞和弗吉尼亞的地標來對目標進行多點定位。

3.2 實驗結(jié)果

如圖4所示，本文利用位于俄勒岡州、加利福尼亞和弗吉尼亞的地標L1、L2、L3對目標虛擬機T進行定位，T的實際位置位于美國俄克拉荷馬州的梅斯縣，通過上述步驟對T進行定位，定位結(jié)果位于堪薩斯州東部，如圖4中的M所示，距離測量顯示，M和T之間距離約為235 km，即定位誤差約為235 km，與現(xiàn)有CBG算法利用更多個地標的定位誤差相當。因此，本文算法在基本保持定位精度的同時，僅需要更少的地標數(shù)量。

圖4 對位于梅斯縣的目標定位結(jié)果

4 結(jié)論

對云數(shù)據(jù)進行定位越來越受到用戶的重視。本文針對現(xiàn)有定位算法存在的維護私有地標開銷較大問題，提出了基于公共地標配置的云數(shù)據(jù)定位算法，通過對公共地標進行配置，能夠利用較少的地標對目標進行定位，且保持定位精度不降低。實驗結(jié)果驗證了該算法的有效性。在今后的工作中，將進一步對定位算法進行優(yōu)化，以提高定位精度。