基于POI地標(biāo)與路徑相似度的IP定位研究

金弋然 陳永樂 姚青樺 陳俊杰

(太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院 山西 太原 030024)

0 引 言

IP定位技術(shù)是一種通過設(shè)備的IP地址確定其地理位置的技術(shù)，在社交網(wǎng)絡(luò)[1]、網(wǎng)絡(luò)安全[2]和拓?fù)鋬?yōu)化[3]等領(lǐng)域中起著關(guān)鍵作用。網(wǎng)絡(luò)安全領(lǐng)域中，IP定位技術(shù)可以將用戶賬號(hào)與常用登錄IP地址綁定驗(yàn)證是否存在IP欺詐、識(shí)別非人類流量，還可以用于系統(tǒng)監(jiān)控，定位脆弱設(shè)備、追溯攻擊、增強(qiáng)系統(tǒng)防護(hù)，以達(dá)到報(bào)警聯(lián)動(dòng)。此外，IP定位技術(shù)在車聯(lián)網(wǎng)、工控物聯(lián)網(wǎng)等系統(tǒng)中的定位與通信中起著關(guān)鍵作用。網(wǎng)絡(luò)應(yīng)用服務(wù)通常會(huì)根據(jù)用戶的IP地址為用戶提供定制化服務(wù)，例如即時(shí)通信軟件向用戶推送當(dāng)?shù)靥鞖?、新聞或附近的活?dòng)資訊。IP定位技術(shù)還可以應(yīng)用于網(wǎng)絡(luò)性能優(yōu)化，網(wǎng)絡(luò)代理服務(wù)商可以通過網(wǎng)絡(luò)節(jié)點(diǎn)的物理位置優(yōu)化通信線路，降低通信時(shí)延與系統(tǒng)開銷，提升系統(tǒng)性能。因此，IP定位技術(shù)可以使許多應(yīng)用程序更加深入地了解用戶和客戶來自何處，掌握用戶的在線行為，從而增加應(yīng)用程序的安全系數(shù)與衍生價(jià)值。

由于網(wǎng)絡(luò)協(xié)議中沒有IP地址與相應(yīng)物理位置的內(nèi)置關(guān)聯(lián)，IP定位技術(shù)研究備受關(guān)注。IP定位技術(shù)可分為以下兩大類[2]：一類是基于客戶端的IP定位技術(shù)，依靠設(shè)備上搭載的蜂窩網(wǎng)絡(luò)、Wi-Fi和GPS等輔助定位模塊進(jìn)行定位。這類技術(shù)可以實(shí)現(xiàn)高精度的IP定位，但受傳播噪聲影響較大，容易收到匿名掃描，安全性低，應(yīng)用場(chǎng)景受限。另一類是獨(dú)立于客戶端的IP定位技術(shù)，包括基于推理估計(jì)[4]、時(shí)延測(cè)量[5]和網(wǎng)絡(luò)拓?fù)鋄6-7]的定位方法。盡管后者定位準(zhǔn)確性降低了，但這類技術(shù)實(shí)現(xiàn)簡(jiǎn)單，不依賴于特定的定位設(shè)備，有很好的擴(kuò)展性。本文算法專注于基于網(wǎng)絡(luò)測(cè)量單點(diǎn)探測(cè)的IP定位技術(shù)，不受限于硬件支持，簡(jiǎn)化探測(cè)工作，深度挖掘路徑之間的相似關(guān)系，對(duì)網(wǎng)絡(luò)環(huán)境影響較小，可以廣泛應(yīng)用于各類應(yīng)用場(chǎng)景。

數(shù)字地圖中的興趣點(diǎn)(POI)具有準(zhǔn)確的位置信息，可以有效轉(zhuǎn)化為網(wǎng)絡(luò)節(jié)點(diǎn)的地理位置。但是，如何將POI信息映射到IP地址和如何驗(yàn)證POI地標(biāo)的可用性仍然是兩個(gè)大挑戰(zhàn)。本文采用POI數(shù)據(jù)來緩解地標(biāo)匱乏的現(xiàn)象，設(shè)計(jì)了基于數(shù)字地圖和搜索引擎的地標(biāo)收集方法，分別從北京市和上海市獲取了2 038和1 429個(gè)POI地標(biāo)，遠(yuǎn)優(yōu)于著名的PlanetLab[13]，該平臺(tái)在全球范圍內(nèi)部署了547個(gè)地標(biāo)設(shè)備。在此基礎(chǔ)上，本文設(shè)計(jì)了一種基于路由路徑相似度的IP定位方法，簡(jiǎn)稱SBG算法。SBG算法設(shè)計(jì)了加權(quán)二維字符串子序列核算法(TDSSK)計(jì)算路徑相似度，通過離群點(diǎn)檢測(cè)聚類算法進(jìn)一步優(yōu)化街道級(jí)的定位結(jié)果，可以在一定限度上消除不良網(wǎng)絡(luò)狀態(tài)對(duì)定位算法的有害影響。本文實(shí)現(xiàn)了原型系統(tǒng)，并將SBG方法的性能與其他算法進(jìn)行了比較。SBG算法性能更為穩(wěn)定，定位精度更高，可以實(shí)現(xiàn)5.7 km的定位中值誤差。

1 相關(guān)技術(shù)

獨(dú)立于客戶端的IP定位技術(shù)不需要任何輔助定位設(shè)備的支持，具有廣泛的應(yīng)用場(chǎng)景。本節(jié)簡(jiǎn)要介紹獨(dú)立于客戶端的IP定位技術(shù)。

基于推測(cè)估計(jì)的IP定位技術(shù)根據(jù)中間節(jié)點(diǎn)的DNS名稱、公開主機(jī)名等信息實(shí)現(xiàn)城市級(jí)IP定位[15]。此類方法分為三類[2]：① 直接查詢Whois數(shù)據(jù)庫；② 通過測(cè)量主機(jī)名與數(shù)據(jù)庫信息相結(jié)合進(jìn)行推斷；③ 利用網(wǎng)絡(luò)結(jié)構(gòu)和數(shù)據(jù)庫信息進(jìn)行推理。然而，大部分國家的網(wǎng)絡(luò)路徑中并不存在暴露名稱的中間節(jié)點(diǎn)。該方法高度依賴于IP分配數(shù)據(jù)庫或主機(jī)名等信息，存在局限性，無法進(jìn)行高精度的IP定位[11]。同時(shí)，云服務(wù)器與內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Delivery Network,CDN)的存在引入了噪聲數(shù)據(jù)，使其應(yīng)用場(chǎng)景有限。

基于時(shí)延測(cè)量的IP定位技術(shù)根據(jù)探測(cè)報(bào)文的傳輸時(shí)延來估計(jì)地標(biāo)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離。Wang等[8]提出了一種以基于約束的IP定位技術(shù)(CBG)[9]為基礎(chǔ)的街道級(jí)IP定位方法(SLG)。根據(jù)探測(cè)時(shí)延縮小定位范圍，尋找距離公共路由節(jié)點(diǎn)最近(具有最小時(shí)延)的地標(biāo)節(jié)點(diǎn)，將目標(biāo)節(jié)點(diǎn)定位到該地標(biāo)的位置。Jiang等[10]訓(xùn)練兩層神經(jīng)網(wǎng)絡(luò)模型逐步定位目標(biāo)IP，在美國實(shí)現(xiàn)了4.1 km的中值誤差。Wang等[17]提出了一種基于公共路由節(jié)點(diǎn)的定位技術(shù)，使SLG算法的性能提高了9.5%。時(shí)延測(cè)量依賴于世界范圍內(nèi)的公共勘探資源，例如Rocketfuel[12]、PlanetLab[13]。然而，這類資源在國內(nèi)極為匱乏。我國密集的人口組成和巨量的網(wǎng)絡(luò)交互導(dǎo)致互聯(lián)網(wǎng)上的交換機(jī)、路由器等中間設(shè)備數(shù)量眾多[14]。路徑中的轉(zhuǎn)發(fā)排隊(duì)時(shí)間與轉(zhuǎn)發(fā)處理時(shí)間難以估計(jì)。其中，由于防火墻設(shè)備的存在，某些設(shè)備無法返回有效的探測(cè)信息。同時(shí)，基于時(shí)延測(cè)量的IP定位技術(shù)隨網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化。由于密集復(fù)雜網(wǎng)絡(luò)中存在網(wǎng)絡(luò)抖動(dòng)、網(wǎng)絡(luò)擁塞和數(shù)據(jù)包丟失等現(xiàn)象，這類技術(shù)不可避免地會(huì)引入測(cè)量誤差。

基于網(wǎng)絡(luò)拓?fù)涞腎P定位技術(shù)中，Wang等[8]發(fā)現(xiàn)通信時(shí)延只能提供粗粒度定位，提出了一種三層街道級(jí)(SLG)IP定位算法，其中：第一層使用了改進(jìn)的CBG算法確定粗粒度的地理位置；第二層利用基于網(wǎng)站的大量節(jié)點(diǎn)將IP縮小定位范圍，利用與路徑中最近相同路由器之間的時(shí)延估計(jì)地標(biāo)和目標(biāo)IP之間的距離；第三層增加網(wǎng)站地標(biāo)的數(shù)量，選擇最短延遲估計(jì)目標(biāo)節(jié)點(diǎn)的準(zhǔn)確地理位置。Zhao等[20]基于路由路徑的相似性和城市本地時(shí)延分布實(shí)現(xiàn)了9 km左右的誤差，累積概率為80%。本文設(shè)計(jì)了基于拓?fù)浣Y(jié)構(gòu)的IP定位技術(shù)，可以很好地挖掘網(wǎng)絡(luò)結(jié)構(gòu)特征，對(duì)復(fù)雜網(wǎng)絡(luò)環(huán)境有一定的魯棒性。

2 算法設(shè)計(jì)

圖1為基于POI地標(biāo)與路徑相似度的SBG算法的結(jié)構(gòu)圖。SBG算法分為兩個(gè)階段：第一個(gè)階段是預(yù)處理，包括收集POI地標(biāo)和構(gòu)建路由路徑指紋庫，此階段從數(shù)字地圖中挖掘POI，通過搜索引擎將POI物理位置映射到IP地址以構(gòu)建路徑數(shù)據(jù)庫，是SBG算法設(shè)計(jì)的數(shù)據(jù)基礎(chǔ)；第二個(gè)階段通過計(jì)算路徑相似度并優(yōu)化定位結(jié)果來進(jìn)行IP定位，通過離群點(diǎn)檢測(cè)算法刪除噪聲數(shù)據(jù)，計(jì)算聚類中心以推測(cè)目標(biāo)IP的地理位置。

2.1 數(shù)據(jù)收集

作為IP定位的主要參考依據(jù)，地標(biāo)節(jié)點(diǎn)的數(shù)量和可信程度直接影響IP定位的精度。例如PlanetLab[13]、PerfSONAR[18]和PingER[19]等平臺(tái)提供已知IP地址和地理位置的公共地標(biāo)節(jié)點(diǎn)。PlanetLab[13]是一個(gè)運(yùn)行著1 353個(gè)節(jié)點(diǎn)和547個(gè)站點(diǎn)的網(wǎng)絡(luò)測(cè)試平臺(tái)，其中大多數(shù)節(jié)點(diǎn)為大學(xué)和研究機(jī)構(gòu)。PerfSONAR[18]是一個(gè)提供聯(lián)合路徑與端到端連接期望的網(wǎng)絡(luò)測(cè)量平臺(tái)。該公共平臺(tái)運(yùn)營的節(jié)點(diǎn)十分有限，無法在中國支持高準(zhǔn)確率的IP地理位置。因此，本文從數(shù)字地圖中挖掘POI信息，并通過搜索引擎擴(kuò)充其地理位置。

POI可代表一棟大廈、一家商鋪或一處景點(diǎn)，包括了城市中的大部分功能場(chǎng)所。獲取POI的基本思想是從電子地圖服務(wù)中收集每個(gè)城市的POI，百度地圖、高德地圖、谷歌地圖等地圖公司均提供POI服務(wù)，可以通過請(qǐng)求相關(guān)的Restful接口獲得。本文從數(shù)量、可靠性和可訪問性三個(gè)方面評(píng)估POI的質(zhì)量，如表1所示。其中，由于網(wǎng)站更新和地址變遷等更改，POI信息也在不斷更新。因此，可靠性是評(píng)估POI質(zhì)量的重要標(biāo)準(zhǔn)之一。本文收集并比較了不同地點(diǎn)3 000多個(gè)數(shù)據(jù)的正確性，發(fā)現(xiàn)對(duì)于國內(nèi)的POI數(shù)據(jù)，高德地圖和百度地圖的時(shí)效性幾乎沒有差異。必應(yīng)地圖的錯(cuò)誤率較高，谷歌地圖也存在一定的誤差。因此，從可靠性來講，高德≈百度>Google>必應(yīng)。此外，百度地圖單接口最大返回條數(shù)為500個(gè)。如果檢索整個(gè)城市的POI，將忽略大量的POI信息。這里，高德地圖提供了城市和POI類型分類代碼。單接口限制返回?cái)?shù)量為900，優(yōu)于其他地圖服務(wù)。因此，就獲取POI的難易程度而言，高德>百度>谷歌>必應(yīng)。本文選擇高德地圖作為SBG算法的POI信息來源。其中，高德POI服務(wù)接口中的“websites”字段標(biāo)識(shí)該P(yáng)OI的網(wǎng)站信息。

表1 POI數(shù)據(jù)來源評(píng)估

POI地標(biāo)獲取流程如算法1所示。其中，輸出si為IP位置數(shù)據(jù)(IP地址，經(jīng)緯度)，例如：(218.205.182.142，38.032013114.453689)。

算法1

輸入：城市。

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

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

2. DNS解析website字段中的域名，若解析成功，記錄該節(jié)點(diǎn)位置信息對(duì)，否則丟棄該P(yáng)OI條目。

3. 在搜索引擎中檢索該P(yáng)OI信息，爬取檢索結(jié)果列表中的前5個(gè)網(wǎng)頁。如果主頁中沒有網(wǎng)站的機(jī)構(gòu)地址，迭代爬取與“加入我們”“招聘”“聯(lián)系我們”對(duì)應(yīng)的URL。如果找不到該條目地址，則刪除。

4. 循環(huán)至遍歷完全部節(jié)點(diǎn)。

5. 刪除關(guān)鍵字大量重復(fù)或同一公司的多個(gè)地址等大量重復(fù)節(jié)點(diǎn)。

6. 將Maxmind與IPcn數(shù)據(jù)庫中均不在目標(biāo)城市的節(jié)點(diǎn)標(biāo)識(shí)為跨城市級(jí)云地標(biāo)并刪除。

7. 將路徑時(shí)延轉(zhuǎn)化為路徑距離，丟棄與目標(biāo)距離大于2.5 km的中間節(jié)點(diǎn)。

8. 尋找地標(biāo)間的公共路由節(jié)點(diǎn)，若兩地標(biāo)節(jié)點(diǎn)之間、經(jīng)由公共節(jié)點(diǎn)的相對(duì)距離大于5 km，將其丟棄，否則保留。

因?yàn)樵S多企業(yè)將網(wǎng)站部署到阿里云和亞馬遜云等平臺(tái)上，本文刪除云服務(wù)器數(shù)據(jù)，如第6步所示。Maxmind[22]和IPcn[23]提供了城市級(jí)IP位置數(shù)據(jù)庫。單個(gè)數(shù)據(jù)庫的準(zhǔn)確性和可靠性不高，例如Maxmind在中國的城市級(jí)定位的準(zhǔn)確性僅為68%[22]。本文采用兩個(gè)數(shù)據(jù)庫進(jìn)行雙重驗(yàn)證，以獲得更可靠的數(shù)據(jù)集。

本文使用基于公共路由器的方法[17]將相對(duì)位置誤差限制在5 km之內(nèi)，驗(yàn)證網(wǎng)站的實(shí)際位置，如第7步-第9步。為驗(yàn)證地標(biāo)的正確性，本文引入公共中間節(jié)點(diǎn)，使用4c/9(c是光速)作為通信時(shí)延和地理距離之間的轉(zhuǎn)換系數(shù)[8]，計(jì)算相對(duì)距離。丟棄與地標(biāo)相距超過2.5 km的公共路由。這類設(shè)備可能是三級(jí)或四級(jí)間接轉(zhuǎn)發(fā)設(shè)備。同時(shí)，將距共同路由設(shè)備2.5 km內(nèi)的地標(biāo)視為靠近公共路由設(shè)備。

本文基于高德POI信息收集了北京和上海的地標(biāo)數(shù)據(jù)。如表2所示，POI方法可以收集成千上萬個(gè)地標(biāo)節(jié)點(diǎn)。數(shù)據(jù)清理后，在北京市和上海市分別獲得了2 038和1 429個(gè)可用地標(biāo)，可用作街道級(jí)IP定位的數(shù)據(jù)基礎(chǔ)。

表2 地標(biāo)數(shù)據(jù)采集結(jié)果

與全球范圍內(nèi)部署547個(gè)設(shè)備的PlanetLab平臺(tái)相比，本文可以在一個(gè)城市中收集數(shù)千個(gè)可用的地標(biāo)數(shù)據(jù)。圖2是數(shù)據(jù)清洗后北京市和上海市的地標(biāo)節(jié)點(diǎn)分布熱力圖，顏色越深表示節(jié)點(diǎn)密度越大。不難發(fā)現(xiàn)，地標(biāo)在城市核心區(qū)域具有較高的分布密度，在科技公司較少的郊區(qū)分布較為稀疏。

2.2 建立路由路徑數(shù)據(jù)庫

本文使用Ping指令探測(cè)存活POI設(shè)備，Traceroute(UDP/ICMP)、Paris-Traceroute工具記錄探測(cè)路經(jīng)序列。其中，Traceroute通過發(fā)送UDP報(bào)文、分析ICMP差錯(cuò)報(bào)文定位主機(jī)和目標(biāo)IP之間的路徑。Paris Traceroute[24]通過更改報(bào)文頭部字段來保證單次探測(cè)內(nèi)的探測(cè)報(bào)文遵循相同的路徑，例如修改ICMP報(bào)文中的協(xié)議標(biāo)識(shí)符和序列號(hào)的組合字段。下面將探測(cè)統(tǒng)稱為Traceroute。

由于網(wǎng)絡(luò)傳輸過程中的波動(dòng)，路由路徑長度是動(dòng)態(tài)變化的。實(shí)驗(yàn)證實(shí)，Traceroute探測(cè)路徑上的路由跳數(shù)大多數(shù)在20跳附近或以下。因此本文將探測(cè)過程中的最大跳數(shù)設(shè)置為30跳，以減少由網(wǎng)絡(luò)數(shù)據(jù)包丟失、網(wǎng)絡(luò)擁塞引起的無效檢測(cè)。

本文間隔兩天對(duì)3 000多個(gè)地標(biāo)發(fā)起了兩次Traceroute探測(cè)，并分析了路由路徑長度的變化。如圖3所示，橫軸表示第一次探測(cè)的路徑長度，縱軸表示第二次探測(cè)的路徑長度。顏色的灰度表示兩次探測(cè)路徑長度的對(duì)比分布。顏色越深，兩次探測(cè)中該路徑長度出現(xiàn)的次數(shù)越多，參照右側(cè)顏色欄。由圖可知，兩次探測(cè)的路徑長度大多集中在8跳至20跳之間。實(shí)驗(yàn)數(shù)據(jù)大多接近等分線(y=x)，即路徑長度在1跳或2跳內(nèi)的變化占很大比例。此外，本文發(fā)現(xiàn)一部分長度為30的路徑中，實(shí)際有效路徑長度不到10跳。路徑后半段全部是星號(hào)。探測(cè)路徑中的星號(hào)表示無效數(shù)據(jù)，由網(wǎng)絡(luò)數(shù)據(jù)包丟失、對(duì)探測(cè)數(shù)據(jù)包無響應(yīng)、防火墻屏蔽等原因?qū)е隆榻⒏油暾牡貥?biāo)路徑指紋數(shù)據(jù)庫，本文多次收集探測(cè)路由路徑，過濾無效數(shù)據(jù)。對(duì)于已收集的3 467個(gè)地標(biāo)樣本，本文丟棄128條無效路由路徑。

圖4為兩次探測(cè)中路徑相似性的比較。橫軸表示路由路徑長度，縱軸表示路由路徑的相似度。圖4(a)僅比較IPv4地址的前三個(gè)網(wǎng)段，圖4(b)比較完整的IPv4地址。匹配完整地址時(shí)，路徑相似度平均約為60%。只匹配前三個(gè)網(wǎng)段時(shí)，相似度顯著提高。這是因?yàn)榫W(wǎng)絡(luò)負(fù)載均衡導(dǎo)致多個(gè)中間路由節(jié)點(diǎn)的IPv4地址的最后一個(gè)網(wǎng)段有所不同。即使探測(cè)相同的目標(biāo)節(jié)點(diǎn)，路徑的相似性普遍還是不能達(dá)到100%。因?yàn)樘綔y(cè)過程一次只發(fā)送三個(gè)數(shù)據(jù)包。而候選路由線路的數(shù)量可能大于三個(gè)，路徑可能會(huì)隨時(shí)間變化。本文利用IPv4地址的前三個(gè)網(wǎng)段作為指紋來計(jì)算相似度，提高路由路徑的穩(wěn)定性。同時(shí)，由于POI和動(dòng)態(tài)IP的變化，應(yīng)該不斷更新地標(biāo)和路由路徑。以兩周的間隔足收集數(shù)據(jù)、更新指紋，可以有效地保證定位的時(shí)效性。

2.3 路徑相似度算法

假設(shè)當(dāng)兩IP的地理位置很近時(shí)，其路由路徑具有一定的相似性。探測(cè)路徑上距離目標(biāo)節(jié)點(diǎn)越近的節(jié)點(diǎn)在路徑相似度中具有越大的權(quán)重。為驗(yàn)證該假設(shè)，本文探測(cè)300個(gè)地標(biāo)進(jìn)行交叉驗(yàn)證，如圖5所示。折線表示出口節(jié)點(diǎn)(路徑上目標(biāo)節(jié)點(diǎn)的前一跳節(jié)點(diǎn))相同時(shí)，目標(biāo)節(jié)點(diǎn)之間距離變化的累積分布函數(shù)。不難發(fā)現(xiàn)，出口節(jié)點(diǎn)相同時(shí)，兩個(gè)目標(biāo)IP之間距離在12公里之內(nèi)的概率超過90%。出口節(jié)點(diǎn)相似度與目標(biāo)IP距離之間存在正相關(guān)的關(guān)聯(lián)關(guān)系。此外，圖中散點(diǎn)圖表示出口節(jié)點(diǎn)相同時(shí)，目標(biāo)IP之間距離分布的散點(diǎn)圖?？梢园l(fā)現(xiàn)目標(biāo)IP之間的路徑相似性越高地理位置越近。這里，利用IPv4地址的前三個(gè)網(wǎng)段計(jì)算路徑相似度的結(jié)果中存在一些異常值，可能是不同運(yùn)營商導(dǎo)致的邊緣網(wǎng)段的位置誤差。實(shí)驗(yàn)表明，路徑相似度與目標(biāo)節(jié)點(diǎn)之間的距離相關(guān)聯(lián)。路徑上的節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)越近，在相似度測(cè)量中的權(quán)重越大。SBG算法通過量化路徑相似度，放大這些相關(guān)關(guān)系。

即使目標(biāo)IP與地標(biāo)的路徑相似度遠(yuǎn)大于其他節(jié)點(diǎn)，也不能保證兩者一定具有相近的地理位置。只基于路徑相似度的IP定位是不準(zhǔn)確的。為解決這一問題，本文深度挖掘路經(jīng)相似性關(guān)系，提出了加權(quán)二維字符串子序列核(Two Dimension String Subsequence Kernel，TDSSK)算法，通過計(jì)算路徑相似度定位目標(biāo)節(jié)點(diǎn)。

TDSSK算法改進(jìn)了傳統(tǒng)的字符串子序列內(nèi)核(String Subsequence Kernel，SSK)算法。SSK算法使用余弦相似度計(jì)算兩個(gè)字符串的相似度，認(rèn)為連續(xù)序列具有較高的權(quán)重。這符合路由轉(zhuǎn)發(fā)的傳輸規(guī)則。實(shí)驗(yàn)表明，靠近出口節(jié)點(diǎn)的相似序列對(duì)定位結(jié)果的影響更大。同時(shí)，網(wǎng)段相似性可能引入較遠(yuǎn)的地理位置，因此需要改進(jìn)相似度的計(jì)算。相連匹配節(jié)點(diǎn)的相似概率大于不相連序列，需要為連續(xù)序列設(shè)置更高的權(quán)重。極端情況下，如果路徑上的相同節(jié)點(diǎn)為首尾節(jié)點(diǎn)，路徑之間相似可能性較低。因此，本文為TDSSK算法設(shè)計(jì)了一個(gè)遞減權(quán)重模型進(jìn)行擬合。計(jì)算Kernel時(shí)，本文不僅考慮連續(xù)序列的權(quán)重，還考慮距離出口節(jié)點(diǎn)遠(yuǎn)近的權(quán)重序列。具體權(quán)重設(shè)計(jì)規(guī)則如下：

Ratei>Ratei+1&&Ratei

(1)

式中：i是序列中距離目標(biāo)節(jié)點(diǎn)i跳的中間節(jié)點(diǎn)；Rate表示節(jié)點(diǎn)的權(quán)重級(jí)別，值越大表示權(quán)重越高。規(guī)則設(shè)計(jì)依據(jù)如下：離目標(biāo)IP越近權(quán)重越大；第i個(gè)節(jié)點(diǎn)的權(quán)重小于鄰接連續(xù)節(jié)點(diǎn)的權(quán)重。本文將上述原理擬合至SSK算法。TDSSK算法首先生成長度k為1和2的子序列向量空間，擬合序列權(quán)重遞減模型計(jì)算子序列之間的相似度。

如圖6所示，加權(quán)TDSSK算法中的序列權(quán)重遞減模型有兩個(gè)目標(biāo)節(jié)點(diǎn)IP1和IP2。a1到a13是探測(cè)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的路由路徑。如果兩個(gè)路徑中的同一位置均包含有效節(jié)點(diǎn)，則兩處都有值；如果僅存在一個(gè)節(jié)點(diǎn)，則另一個(gè)置零。例如，IP1的路由路徑包括a3節(jié)點(diǎn)，而IP2的路徑中沒有該節(jié)點(diǎn)的信息，置為0。

圖6中λ是SSk算法中的衰減因子，代表兩個(gè)相同子序列的距離。λ在相鄰子序列之間迭代衰減，用來表示具有不同距離的相似子序列的相似度衰減情況。εi是序列遞減系數(shù)，表示處于不同位置的節(jié)點(diǎn)在整體路徑相似度中的不同權(quán)重，即式(1)中的Ratei。隨著中間節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間跳數(shù)的增加，兩個(gè)節(jié)點(diǎn)之間的地理距離呈指數(shù)增長，即與目標(biāo)節(jié)點(diǎn)的不相關(guān)性呈指數(shù)增長。本文使用高斯函數(shù)設(shè)置序列減小系數(shù)，如式(2)所示。其中，n是路由跳數(shù)的總數(shù)，x是距離出口節(jié)點(diǎn)的跳數(shù)。這里，10是用于計(jì)算權(quán)重的放大因子。例如，節(jié)點(diǎn)a13對(duì)應(yīng)的ε1為1.064 4；節(jié)點(diǎn)a12對(duì)應(yīng)的ε2為0.948。

(2)

TDSSK=Sssk1+Sssk2=

(3)

2.4 IP定位及其優(yōu)化

本文設(shè)置相似度閾值過濾低相似度節(jié)點(diǎn)，并過濾其中的離群點(diǎn)，計(jì)算集合中心估算目標(biāo)IP的最終地理位置，如算法2所示。

算法2

輸入：目標(biāo)IP。

輸出：定位結(jié)果——經(jīng)緯度(x,y)。

1. 遍歷地標(biāo)路徑集合，切割路徑，保留目標(biāo)城市兩跳后路徑。

2. 計(jì)算衰減序列εi，計(jì)算目標(biāo)節(jié)點(diǎn)與地標(biāo)節(jié)點(diǎn)之間的一維SSK、二維SSK以及TDSSK相似指數(shù)。

3. 如果相似地標(biāo)集合中地標(biāo)節(jié)點(diǎn)小于10且包含相似度極值時(shí)，直接根據(jù)極值點(diǎn)確定目標(biāo)IP位置；否則計(jì)算離群點(diǎn)檢測(cè)數(shù)量閾值Index2，去除離群點(diǎn)。

4. 計(jì)算集合中心估算目標(biāo)IP物理位置。

(1) 設(shè)置相似度閾值。在目標(biāo)節(jié)點(diǎn)與所有地標(biāo)節(jié)點(diǎn)的匹配過程中，存在大量無關(guān)地標(biāo)。SBG算法設(shè)置閾值去除此類節(jié)點(diǎn)。一方面，如果探測(cè)路徑長度較短，到達(dá)目標(biāo)城市之前的路徑會(huì)大范圍重復(fù)。這些路徑高度相似，地理位置并不相近，設(shè)置閾值可以避免此類問題。另一方面，對(duì)于有限的地標(biāo)集，閾值過高會(huì)導(dǎo)致符合條件的節(jié)點(diǎn)數(shù)量很少，無法準(zhǔn)確定位。

本文為2 000個(gè)節(jié)點(diǎn)選擇不同閾值進(jìn)行過濾，考察目標(biāo)IP對(duì)應(yīng)的候選地標(biāo)數(shù)量，如圖7所示。閾值1-3表示到達(dá)目標(biāo)城市后路徑上的1-3跳，橫軸表示具有不同候選地標(biāo)數(shù)量的目標(biāo)IP的數(shù)量，縱軸表示地標(biāo)候選集中超過閾值的節(jié)點(diǎn)數(shù)量。由圖可知，選擇城市后一跳作為閾值時(shí)，獲得的地標(biāo)數(shù)量最多。過濾后，只有93個(gè)IP的候選地標(biāo)節(jié)點(diǎn)的數(shù)量少于30個(gè)。此外，閾值為城市后三跳時(shí)，地標(biāo)的數(shù)量明顯減少。地標(biāo)數(shù)量大于50的節(jié)點(diǎn)數(shù)少于全部節(jié)點(diǎn)的一半。探測(cè)路徑較短時(shí)，該閾值將過濾大量有效數(shù)據(jù)。因此，將閾值設(shè)置為城市后兩跳是中立的，滿足了相似性和節(jié)點(diǎn)數(shù)之間的折中。不僅考慮了過濾無關(guān)節(jié)點(diǎn)的準(zhǔn)確性，還可以保證過濾后的地標(biāo)數(shù)量。因此，SBG算法選擇從城市后兩跳的閾值過濾地標(biāo)節(jié)點(diǎn)。

報(bào)文從探測(cè)節(jié)點(diǎn)所在的城市出發(fā)，經(jīng)由骨干網(wǎng)絡(luò)轉(zhuǎn)發(fā)，進(jìn)而在目標(biāo)城市內(nèi)路由。探測(cè)路徑上的單跳時(shí)延遵循“低-高-低”(城市內(nèi)-城市間-城市內(nèi))分布[21]。城市內(nèi)部路由設(shè)備之間的距離通常很短。不考慮網(wǎng)絡(luò)擁塞的情況，單跳高延遲通常是由物理距離過長或報(bào)文轉(zhuǎn)發(fā)隊(duì)列排隊(duì)引起的。本文利用這個(gè)規(guī)律提取目標(biāo)城市后的路由路徑。

本文使用加權(quán)TDSSK算法計(jì)算路徑相似度值，對(duì)比不同起始節(jié)點(diǎn)對(duì)定位結(jié)果的影響，如圖8所示。橫軸為TDSSK相似指數(shù)，縱軸為對(duì)應(yīng)的地標(biāo)節(jié)點(diǎn)與目標(biāo)IP之間的誤差距離。其中，圖8(a)將閾值(起始節(jié)點(diǎn))設(shè)置為城市后一跳計(jì)算相似度，圖8(b)為城市后兩跳。由圖8可知，城市兩跳比城市后一跳具有更好的性能。另一方面，離散點(diǎn)表示數(shù)據(jù)中的離群點(diǎn)。兩幅圖都有較多的干擾數(shù)據(jù)。因此，離群檢測(cè)是定位優(yōu)化中非常重要的一環(huán)。同時(shí)可以看出，相似度越大距離越近只是一個(gè)大趨勢(shì)。例如在定位某IP時(shí)，相似度大小第十的地標(biāo)可能比具有最高相似度的地標(biāo)更接近目標(biāo)IP節(jié)點(diǎn)。因此，僅根據(jù)相似度的高低定位會(huì)導(dǎo)致很大的誤差。本文選擇具有較高相似性的地標(biāo)集合定位IP。

(2) 清洗定位地標(biāo)。SBG算法選擇一個(gè)相似地標(biāo)集合，通過離群點(diǎn)檢測(cè)方法去除噪聲點(diǎn)。SBG算法在設(shè)計(jì)離群值檢測(cè)算法時(shí)比較了局部異常因子(Local Outlier Factor,LOF)算法、基于距離的累積和(Distance-Based)的離群點(diǎn)檢測(cè)算法和半徑領(lǐng)域算法(Circle-based)。

LOF算法是一種基于密度去除離群點(diǎn)的算法[16]。該算法計(jì)算每個(gè)點(diǎn)到其他點(diǎn)的球面距離并排序，然后計(jì)算每個(gè)點(diǎn)的局部相對(duì)密度。值越小代表密度越小，意味著該點(diǎn)很可能是一個(gè)離群點(diǎn)。LOF值小于1的點(diǎn)通常是離群點(diǎn)。

本文設(shè)計(jì)了基于距離累加和的離群點(diǎn)檢測(cè)算法，計(jì)算某點(diǎn)到所有其他點(diǎn)的球面距離累加和。如式(4)所示，N為相似地標(biāo)集，o′表示除o點(diǎn)外所有的點(diǎn)?？偤驮酱蟊硎驹擖c(diǎn)距離其他點(diǎn)距離越遠(yuǎn)，越有可能是離群點(diǎn)。此外，本文設(shè)計(jì)了半徑領(lǐng)域離群點(diǎn)檢測(cè)算法。每個(gè)點(diǎn)都以固定半徑r畫圓，通過圓內(nèi)包含其他點(diǎn)的數(shù)量來判斷該點(diǎn)是否為離群值，如式(5)所示。如果數(shù)目較少，則將該點(diǎn)視為離群點(diǎn)。對(duì)于給定的數(shù)據(jù)集，需要指定半徑r定義合理的鄰域與數(shù)量閾值π確定是否為離群值。

(4)

(5)

上述離群點(diǎn)檢測(cè)方法檢測(cè)通用數(shù)據(jù)集只需要設(shè)置一些自定義參數(shù)即可。在IP定位的場(chǎng)景下，面對(duì)不確定的位置分布數(shù)據(jù)，選用何種方法、如何設(shè)定合適的參數(shù)值是決定算法性能的主要因素?？紤]到集合的離散程度，SBG使用Grubbs思想，結(jié)合標(biāo)準(zhǔn)差、中位數(shù)和經(jīng)驗(yàn)系數(shù)三個(gè)屬性智能設(shè)置每個(gè)集合的距離閾值。距離累加和算法結(jié)合中位數(shù)(Med)和標(biāo)準(zhǔn)差(Std)計(jì)算閾值Index1，如式(6)所示。若累積和大于Index1，則刪除該離群點(diǎn)。半徑領(lǐng)域法為每個(gè)節(jié)點(diǎn)選擇較大的半徑，計(jì)算半徑圓包含點(diǎn)的數(shù)量并逆序排序，計(jì)算Index2，如式(7)所示。小于Index2的值點(diǎn)為異常值。該選取規(guī)則考慮了集合整體的離散程度(標(biāo)準(zhǔn)差)，在最大程度上保證了數(shù)據(jù)的完整性。實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)r=6，rate=1.6時(shí)，離群點(diǎn)檢測(cè)效果最佳。

Index1=Med+rate×Std

(6)

Index2=Med-rate×Std

(7)

本文隨機(jī)選取一個(gè)目標(biāo)IP，對(duì)生成的地標(biāo)相似集合進(jìn)行離群值檢測(cè)。如圖9所示，去除異常值后能夠生成更準(zhǔn)確的定位結(jié)果。但在特殊情況下仍存在誤差，例如：IP位于偏遠(yuǎn)位置、地標(biāo)數(shù)量較少時(shí)，移除的異常值可能是最接近目標(biāo)的位置，造成較大誤差，此時(shí)可使用相似度極值直接位置。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)使用部署在阿里云上的一臺(tái)云服務(wù)器分別對(duì)北京、上海兩個(gè)城市進(jìn)行測(cè)量，獲取了2 038個(gè)和1 429個(gè)可用的POI地標(biāo)節(jié)點(diǎn)。然后，從這些地標(biāo)節(jié)點(diǎn)集中隨機(jī)選擇測(cè)試目標(biāo)，采用Common Router和SLG的性能評(píng)估指標(biāo)，對(duì)SBG算法進(jìn)行評(píng)估。

3.1 不同離群點(diǎn)檢測(cè)算法的影響

不同離群值檢測(cè)算法對(duì)定位精度有不同的影響。地標(biāo)數(shù)量也會(huì)影響定位算法的性能。本文實(shí)驗(yàn)以北京市地標(biāo)集合為對(duì)象，討論三種離群值檢測(cè)方法的性能，隨機(jī)提取500個(gè)地標(biāo)節(jié)點(diǎn)，然后以250個(gè)地標(biāo)的增量梯度增加，將SBG算法與三種離群點(diǎn)檢測(cè)算法結(jié)合進(jìn)行IP定位，如圖10所示。隨著地標(biāo)數(shù)量的增加，定位誤差減小。大量可靠的地標(biāo)數(shù)據(jù)可以提供更有效的信息使得IP定位更加準(zhǔn)確。其中，SBG-Circle方法可以實(shí)現(xiàn)最好的定位精度。

本文對(duì)北京和上海2 000個(gè)地標(biāo)進(jìn)行定位。圖11為定位誤差的累積分布函數(shù)。三種算法整體上誤差相近。半徑領(lǐng)域算法的中值誤差最優(yōu)，收斂速度快于其他兩種方法，整體誤差距離在18 km附近收斂。盡管LOF算法總體表現(xiàn)一般，但是開始階段的性能優(yōu)于其他方法。同時(shí)，LOF收斂的速度相對(duì)較慢，這表明該方法具有較大的方差。半徑領(lǐng)域算法的性能相對(duì)穩(wěn)定。本文使用半徑領(lǐng)域法去除異常值。因此，SBG算法又稱為SBG-Circle算法。

3.2 地標(biāo)密度對(duì)IP定位性能的影響

本節(jié)說明了地標(biāo)密度與定位誤差之間的關(guān)系。目標(biāo)IP附近的地標(biāo)數(shù)量越多，可以更準(zhǔn)確地識(shí)別出更多相似候選節(jié)點(diǎn)。本文利用半徑分別為1 km、3 km、5 km和8 km的候選領(lǐng)域，研究了不同地標(biāo)密度變化下定位精度的變化趨勢(shì)。如圖12所示，同一半徑圓中，定位誤差隨地標(biāo)密度的增加而逐漸減小。相同密度條件下，在不同半徑的圓上，地標(biāo)節(jié)點(diǎn)的數(shù)量隨半徑增加而增加，定位誤差隨之下降。

如圖12所示，半徑為8 km時(shí)，地標(biāo)數(shù)最大，定位誤差最小，中位誤差約為2.7 km。無論半徑如何變化，隨著地標(biāo)分布密度的增加，三種IP定位算法的定位精度都會(huì)提高。同時(shí)，實(shí)驗(yàn)表明SLG算法和Common-Router算法的定位誤差始終大于SBG算法。

3.3 SBG算法性能

本文選擇北京市和上海市的3 339個(gè)地標(biāo)作為目標(biāo)節(jié)點(diǎn)，將SBG算法與SLG和Common Router兩種算法進(jìn)行比較。圖13是定位誤差的累積分布概率圖。SBG算法在18 km處收斂，其他兩種算法分別在35 km和48 km處收斂。此外，SBG算法的中值誤差約為5.7 km，算法性能遠(yuǎn)好于國內(nèi)現(xiàn)有的IP定位算法。特別是，SBG算法的長尾比其他兩種算法占比低。這表明SBG算法的性能相對(duì)穩(wěn)定，對(duì)實(shí)際網(wǎng)絡(luò)的適應(yīng)能力更好。

百度智能定位服務(wù)是目前國內(nèi)較為成熟的定位服務(wù)。與SBG算法相比，百度高精度IP定位服務(wù)依賴衛(wèi)星定位系統(tǒng)，需要定位輔助硬件設(shè)備，具有局限性；百度低精度IP定位服務(wù)只能實(shí)現(xiàn)城市級(jí)定位，經(jīng)緯度坐標(biāo)一般為城市中心點(diǎn)的坐標(biāo)，定位誤差較大。因此，與目前流行的定位服務(wù)相比，SBG算法依據(jù)單點(diǎn)測(cè)量技術(shù)，對(duì)實(shí)驗(yàn)環(huán)境的要求不高，具有較好的普適性，可以顯著的提升定位精度，可以廣泛應(yīng)用于IP定位的應(yīng)用場(chǎng)景。

4 結(jié) 語

本文提出了一種基于POI地標(biāo)與路徑相似度的SBG算法，以實(shí)現(xiàn)高精度IP定位。從數(shù)字地圖和搜索引擎收集POI地標(biāo)后，本文設(shè)計(jì)了路徑相似度計(jì)算算法和離群點(diǎn)檢測(cè)算法，實(shí)現(xiàn)了約為5.7 km的中位定位誤差。實(shí)驗(yàn)驗(yàn)證了地標(biāo)數(shù)量和分布密度對(duì)IP定位算法具有一定的影響。本文將SBG算法與現(xiàn)有的SLG算法、Common-Router算法、百度智能定位服務(wù)進(jìn)行了比較。實(shí)驗(yàn)表明，SBG算法具有更穩(wěn)定的性能，可以實(shí)現(xiàn)更高的定位精度。未來工作將專注于收集更可靠的地標(biāo)，以提高定位的準(zhǔn)確性，并分析其位置分布。