基于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算法具有更穩定的性能，可以實現更高的定位精度。未來工作將專注于收集更可靠的地標，以提高定位的準確性，并分析其位置分布。