朱 光, 李 珂

(1.中原工學(xué)院 計算機學(xué)院， 河南 鄭州 450007； 2.河南省檔案局， 河南 鄭州 450003)

網(wǎng)絡(luò)實體定位，即獲取網(wǎng)絡(luò)實體IP地址與其地理位置之間的映射關(guān)系[1]。在互聯(lián)網(wǎng)中，IP地址通常能夠唯一標識一個網(wǎng)絡(luò)實體，因此也稱IP定位。隨著網(wǎng)絡(luò)空間安全領(lǐng)域逐漸受到重視，IP定位技術(shù)也發(fā)揮著重要的作用，如IP定位技術(shù)可以追蹤網(wǎng)絡(luò)敏感目標和鎖定網(wǎng)絡(luò)謠言散播者，為防恐維穩(wěn)提供技術(shù)支持；IP定位技術(shù)可應(yīng)用于商業(yè)領(lǐng)域中基于位置的服務(wù)；也可為電視節(jié)目、廣播和數(shù)字音像的區(qū)域版權(quán)保護提供技術(shù)支持等。

現(xiàn)有的網(wǎng)絡(luò)實體定位技術(shù)主要分為基于非測量方式和基于測量方式。前者利用互聯(lián)網(wǎng)公開的IP數(shù)據(jù)庫(如Whois、IP2Location等)查詢IP地址的地理位置；后者測量探測源、地標(已知地理位置的網(wǎng)絡(luò)實體)與目標之間的時延、拓撲等信息，從而估算出目標IP的地理位置，如GeoPing[2]、LBG[3]、Spotter[4]、CBG[5]、Octant[6]、SLG[7]算法等。

在上述基于測量的網(wǎng)絡(luò)實體定位方法中，將地標所在位置作為目標的位置估計(即基于地標的網(wǎng)絡(luò)實體定位技術(shù))是獲取高精度定位結(jié)果的重要方式之一[8]。然而，現(xiàn)有的網(wǎng)絡(luò)實體地標采集與評估算法較少，主要有Strcuton[9]、基于Web與在線地圖相結(jié)合的地標挖掘算法(簡稱基于Web的地標挖掘方法)[7]以及基于互聯(lián)網(wǎng)論壇的地標挖掘算法[10]。

基于Web的地標挖掘算法是利用在線地圖查詢地理位置的方式實現(xiàn)Web網(wǎng)站的IP地址與其地理位置之間的映射，其算法流程見圖1。在提供在線地圖服務(wù)的網(wǎng)頁中輸入“公司”“大學(xué)”“政府”等組織機構(gòu)的關(guān)鍵字和郵政編碼后，地圖服務(wù)器返回該郵政編碼區(qū)域內(nèi)的相關(guān)單位的網(wǎng)站域名，可將這些網(wǎng)站域名(或IP地址)與其地理位置建立映射關(guān)系。

圖1 基于Web的地標挖掘方法流程

基于Web的地標挖掘算法獲取的地標粒度為街道級，可滿足高精度定位算法的需求，然而，由于Web服務(wù)器可能存在主機托管、共享主機以及CDN(Content Delivery Network)網(wǎng)絡(luò)等情況，從在線地圖中獲取的域名與服務(wù)器的IP地址并不能保證一對一關(guān)系，且獲取的地理位置與Web服務(wù)器所在的地理位置也不能保證一一對應(yīng)。雖然，基于Web的地標挖掘算法中對存在上述問題的候選地標進行了評估，但效果并不理想，基于Web方式獲取的網(wǎng)絡(luò)實體地標精度雖高，但可靠性不能得到保證。

1 基于路由跳數(shù)的網(wǎng)絡(luò)實體地標篩選算法

1.1 算法思想與原理架構(gòu)

文獻[11]和[12]指出，同一網(wǎng)絡(luò)服務(wù)提供商在配置網(wǎng)絡(luò)環(huán)境和路由轉(zhuǎn)發(fā)策略時，數(shù)據(jù)包在骨干網(wǎng)上的轉(zhuǎn)發(fā)路徑往往相對穩(wěn)定，即對于同一區(qū)域的數(shù)據(jù)包到達另一區(qū)域時，數(shù)據(jù)包所經(jīng)歷的路由路徑往往相同或相似，由此通過多個探測源可量化出探測源到某個城市的路由跳數(shù)向量。

基于路由跳數(shù)的網(wǎng)絡(luò)實體地標篩選算法原理架構(gòu)如圖2所示。首先，通過多個IP位置數(shù)據(jù)庫獲取候選地標可能所處的地理位置，并在這些位置部署相應(yīng)的探測源，選取已知的高可靠的城市級地標為基準節(jié)點，測量探測源到所有基準節(jié)點的路由路徑與路由跳數(shù)，統(tǒng)計出每個探測源到每座城市的平均路由跳數(shù)以及每座城市內(nèi)部的平均跳數(shù)，為每一座城市建立跳數(shù)向量，稱為基準跳數(shù)向量；然后，依據(jù)上述方法，對待評估的候選地標建立候選地標跳數(shù)向量；最后，計算基準跳數(shù)向量與候選地標跳數(shù)向量的相似度，將相似度最高的基準跳數(shù)向量所對應(yīng)的城市作為候選地標的地理位置。

圖2 基于路由跳數(shù)的網(wǎng)絡(luò)實體地標篩選原理架構(gòu)

1.2 算法步驟

輸入：待評估的候選地標；

輸出：篩選后的高可靠地標；

Step1：基準節(jié)點選取與探測源部署。通過現(xiàn)有的多個IP位置數(shù)據(jù)庫獲取候選地標可能所處的城市，選取一定數(shù)量的位于這些候選城市的高可靠網(wǎng)絡(luò)實體地標為基準節(jié)點(應(yīng)屬于同一ISP)，基準節(jié)點在地理位置上應(yīng)均勻分布，且位于不同網(wǎng)段。在部署探測源時，應(yīng)在候選地標可能所在的城市周邊均勻部署多個探測源(探測源與基準節(jié)點應(yīng)屬于同一ISP)，探測源的數(shù)量一般由用戶對篩選精度的需求來確定。

Step2：路徑測量與跳數(shù)統(tǒng)計。利用Traceroute工具，使探測源發(fā)送數(shù)據(jù)包，測量探測源到所有基準節(jié)點的路由路徑，路由路徑包含探測源到基準節(jié)點之間經(jīng)過的所有路由器以及對應(yīng)的跳數(shù)信息。針對任一探測源，根據(jù)路由路徑分析，統(tǒng)計出該探測源到每座城市的平均路由跳數(shù)α以及每個城市內(nèi)部的平均跳數(shù)δ。

計算α?xí)r，根據(jù)現(xiàn)有IP位置數(shù)據(jù)庫查詢方式確定每條路由路徑中到達該城市的第一個路由器R，并將R之后的所有路徑移除；然后統(tǒng)計探測源到路由器R之間的路由跳數(shù)進而計算出該探測源到每座城市的平均路由跳數(shù)α。計算δ時，將路由器R之前的所有路徑移除，統(tǒng)計路由器R到基準節(jié)點之間的路由跳數(shù)，計算每座城市內(nèi)部的平均跳數(shù)δ。

Step3：建立基準跳數(shù)向量。依據(jù)上述方法，確定每座城市的平均路由跳數(shù)α及每座城市內(nèi)部的平均路由跳數(shù)δ。對任一城市，為每一個探測源建立到該城市的跳數(shù)向量Hi=(αi,(αi+δi))，其中，i表示第i個探測源，進而建立所有探測源到該城市的基準跳數(shù)向量。為便于計算，將每座城市的基準跳數(shù)向量記為DH，如式(1)所示，其中，m為探測源數(shù)量，i表示第i個探測源，其數(shù)量根據(jù)用戶對篩選精度的需求而定，hi,1與hi,2分別為候跳數(shù)向量Hi中的兩個元素。

DH=(h1,1,h1,2,…,hi,1,hi,2,…,hm,1,hm,2)

(1)

Step4：建立候選地標跳數(shù)向量。所有探測源發(fā)送探測包測量候選地標的路由路徑，獲取探測源到候選地標之間的路由跳數(shù)α以及城市內(nèi)部的跳數(shù)δ，為候選地標的所有可能城市分別建立候選地標跳數(shù)向量Tj=(αj,(αj+δj))，其中j表示第j個探測源，α與δ的計算方法同Step2，進而為候選地標建立多個跳數(shù)向量DT，如式(2)所示，其中，k表示候選地標可能所處的第k座候選城市，m為探測源數(shù)量，tj,1與tj,2分別為候選地標跳數(shù)向量Tj中的兩個元素。

DTk=(t1,1,t1,2,…,tj,1,tj,2,…,tm,1,tm,2)

(2)

Step5：候選地標篩選。計算候選地標跳數(shù)向量DTk和每座城市的基準跳數(shù)向量DH相似度，計算方法見式(3)，其中i表示第i個探測源。其中Ek為候選地標與第k座候選城市的誤差值，將與Ek最小的基準跳數(shù)向量所對應(yīng)的城市作為候選地標所在的城市，將候選地標宣稱的地理位置與評估出來的位置進行比較，兩者所處地理位置不一致的候選地標認為是可靠性低的地標，兩者地理位置一致的候選地標認為是高可靠的地標，進而完成對候選地標的篩選。

(3)

2 實驗結(jié)果及分析

為驗證本文提出的基于路由跳數(shù)的網(wǎng)絡(luò)實體地標篩選算法，以SLG與LBG定位算法為基準，采用兩類地標集：傳統(tǒng)的基于Web的地標挖掘算法得到的地標集(以下簡稱WBL)和本文算法對其篩選后的地標集(以下簡稱FWBL)，分別作為SLG與LBG定位算法的輸入，對分布在6座城市的300個已知地理位置的目標IP進行定位，比較兩種地標集對上述兩種定位算法精度的影響。

2.1 SLG與LBG算法基本原理

SLG算法采用三層定位的思想逐層縮小目標的位置估計[7]。第一層利用改進的CBG算法為目標限定一個粗粒度區(qū)域。第二層在第一層估計區(qū)域的基礎(chǔ)上，結(jié)合區(qū)域內(nèi)的網(wǎng)絡(luò)實體地標，計算地標與目標之間的相對時延，進一步縮小目標估計區(qū)域。首先，找到地標與目標相連的所有共同路由器，計算它們的相對時延。然后，將與目標相對時延最小的地標作為目標的位置估計。

LBG算法利用具有較低計算復(fù)雜度的樸素貝葉斯模型解決機器學(xué)習(xí)的分類問題[3]。該算法通過測量方式獲取探測源到大量地標的往返時延和跳數(shù)信息，并將時延和跳數(shù)劃分為不同的區(qū)間，根據(jù)劃分后的區(qū)間，分別統(tǒng)計出探測源到地標的概率分布，并建立相應(yīng)的概率分布模型。當(dāng)定位目標時，利用探測源到目標的時延與跳數(shù)信息，并結(jié)合概率分布模型，將目標定位到符合該概率分布模型的區(qū)域。

2.2 候選地標評估

2.2.1 基準跳數(shù)向量計算

對中國主流的IP位置數(shù)據(jù)庫QQWry(實驗使用版本為2015.05.15版)、IP138和IPcn進行解析與比對，篩選出鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的所有網(wǎng)吧IP，保留IP位置數(shù)據(jù)庫查詢結(jié)果均處于同一城市的IP，挑選出IP地址16 828個(均屬于中國電信)作為基準節(jié)點的樣本集，利用部署在北京、杭州、青島和深圳的4個探測源，在每天的不同時間段，對上述樣本集進行重復(fù)測量，共計20次，獲取探測源到16 828個基準節(jié)點的路由路徑1 137 456條。統(tǒng)計出探測源到每座城市的平均路由跳數(shù)α以及每座城市內(nèi)部的平均路由跳數(shù)δ，如表1所示。根據(jù)每座城市的α與δ構(gòu)建鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的基準跳數(shù)向量，如表2所示。

表1 探測源到6座城市的平均路由跳數(shù)及城市內(nèi)部平均路由跳數(shù)

表2 6座城市的基準跳數(shù)向量

2.2.2 候選地標跳數(shù)向量計算

通過基于Web的地標挖掘算法從上述6座城市采集與評估候選地標1 500個，構(gòu)建WBL地標集，利用部署在北京、杭州、青島和深圳4座城市的探測源，在每天不同時間段發(fā)送探測包對WBL地標集進行重復(fù)測量，共20次。獲取探測源到WBL地標集的路由路徑 117 659條，統(tǒng)計出每個候選地標的平均路由跳數(shù)α以及該地標所在城市內(nèi)部的平均路由跳數(shù)δ。根據(jù)表2中每座城市的基準跳數(shù)向量，對每個待評估的WBL地標進行相似度比較。篩選后的WBL地標集稱為FWBL地標集，WBL與FWBL地標集數(shù)量如表3所示。地標篩選前后的地理分布如圖3所示。

2.3 定位結(jié)果比較

選取鶴壁、許昌、鄭州、深圳、上海及西安等6座城市的可靠地標各50個，共計300個，作為待定位目標集。分別使用WBL地標集和FWBL地標集作為SLG算法及LBG定位算法的輸入，對目標集進行定位，實驗結(jié)果分別見表4和表5。

表3 WBL與FWBL地標集數(shù)量

(a-1)鶴壁篩選前的地標分布 (a-2)鶴壁篩選后的地標分布

(b-1)許昌篩選前的地標分布 (b-2)許昌篩選后的地標分布

(c-1)鄭州篩選前的地標分布 (c-2)鄭州篩選后的地標分布

(d-1)深圳篩選前的地標分布 (d-2)深圳篩選后的地標分布

(e-1)上海篩選前的地標分布 (e-2)上海篩選后的地標分布

(f-1)西安篩選前的地標分布 (f-2)西安篩選后的地標分布 圖3 各城市地標篩選前后的地理位置分布比較表4 兩類地標集對SLG算法定位的結(jié)果比較

城市WBL地標集定位正確數(shù)量準確率/%FWBL地標集定位正確數(shù)量準確率/%鶴壁43864690許昌45904896鄭州44884896深圳43864794上海44884794西安43864588合計26287．3328193．67

由表4可知，SLG算法對300個目標定位實驗中，WBL地標集定位正確數(shù)量為262個，準確率為87.33%；篩選后的FWBL地標集定位正確數(shù)量為281個，準確率為93.67%，相比于WBL地標集，提高了6.33%。因此，篩選后的地標能夠提高SLG定位算法的準確率。通過對定位結(jié)果的誤差分析可知，WBL產(chǎn)生的平均誤差為51.98 km，中值誤差為19.70 km，F(xiàn)WBL產(chǎn)生的平均誤差為45.71 km，中值誤差為10.28 km，F(xiàn)WBL的定位結(jié)果的誤差明顯小于WBL。因此，從定位精度上看，F(xiàn)WBL優(yōu)于WBL。

表5 兩類地標集對LBG算法定位的結(jié)果比較

由表5可知，LBG算法對300個目標進行定位實驗中，采用WBL地標集定位正確數(shù)量為246個，正確率為82%；FWBL地標集定位正確數(shù)量為269個，正確率為89.67%，相比于WBL地標集，提高了7.67%。通過對定位結(jié)果的誤差分析可知，WBL產(chǎn)生的平均誤差為57.33 km，中值誤差為23.42 km，F(xiàn)WBL產(chǎn)生的平均誤差為49.61 km，中值誤差為14.23 km，從定位精度上看，F(xiàn)WBL地標集優(yōu)于WBL地標集。

3 結(jié) 語

針對基于Web的候選地標評估算法中難以對候選地標進行有效評估的問題，提出了一種基于路由跳數(shù)的網(wǎng)絡(luò)實體地標篩選算法。實驗結(jié)果表明：本文算法能夠提高候選地標的可靠性，提高SLG定位算法及LBG定位算法的精度，為高可靠網(wǎng)絡(luò)實體城市級地標提供了一種新的篩選與評估算法。

[1] Muir J A, Oorschot P C V. Internet geolocation: evasion and counterevasion[J]. ACM Computing Surveys, 2009,42(1):4.

[2] Padmanabhan V N,Subramanian L.An investigation of geographic mapping techniques for internet hosts[J].ACM SIGCOMM Computer Communication Review,2001,31(4):173-185.

[3] Eriksson B, Barford P, Sommers J, et al. A learning-based approach for IP geolocation[C]//Proceedings of the 11th International Conference on Passive and Active Measurement(PAM),Zürich,2010:171-180.

[4] Laki S,Mátray P,Hága P,et al.Spotter:A model based active geolocation service[C]//Proceedings of Interna-tional Conference on Computer Communications (INFOCOM),Shanghai,2011:3173-3181.

[5] Gueye B,Ziviani A,Crovella M,et al.Constraint-based geolocation of internet hosts[J].IEEE/ACM Transactions on Networking,2006,14(6):1219-1232.

[6] Wong B,Stoyanov I.Octant: a comprehensive framework for the geolocalization of internet hosts[C]//Usenix Conference on Networked Systems Design & Implementation,San Jose,CA,2007:23-23.

[7] Wang Y,Burgener D,Flores M,et al.Towards street-level client-independent IP geolocation[C]//Proceedings of Conference on Networked Systems Design and Implementation (NSDI),San Jose,CA,2011:27-27.

[8] 王占豐,馮徑,邢長友,等.IP定位技術(shù)的研究[J].軟件學(xué)報,2014,25(7):1527-1540.

[9] Guo C, Liu Y, Shen W,et al.Mining the Web and the in-ternet for accurate IP address geolocations[C]//Proceedings of International Conference on Computer Communications(INFOCOM),Rio de Janeiro,2009:2841-2845.

[10] Zhu G,Luo X Y,Liu F L,et al.An algorithm of city-level landmark mining based on internet forum[C]//Proceeding of the 18th International Conference on Network-Based Information Systems (NBiS),TaiPei,2015:294-301.

[11] Zhao F,Song Y H,LiuF L,et al.City-level geolocation based on routing feature[C]//Proceeding of the 29th International Conference on Advanced Information Networking and Applications (AINA),Gwangju,2015:414-419.

[12] Eriksson B, Barford P, Nowak R. Estimating hop distance between arbitrary host pairs[C]//Proceedings of IEEE Conference on Computer Communications (INFOCOM),Rio de Janeiro,2009:801-809.