現(xiàn)場(chǎng)名字解析系統(tǒng)中地理鄰居發(fā)現(xiàn)機(jī)制研究

張 芳，孫 鵬，李 楊

（1.中國(guó)科學(xué)院大學(xué)，北京 100049；2.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190）

隨著信息技術(shù)的飛速發(fā)展，越來(lái)越多的設(shè)備接入互聯(lián)網(wǎng)。當(dāng)前互聯(lián)網(wǎng)正面臨IP 語(yǔ)義過(guò)載的問(wèn)題，這對(duì)傳統(tǒng)的基于傳輸控制協(xié)議（TCP）∕Internet 協(xié)議（IP）的網(wǎng)絡(luò)提出了巨大的挑戰(zhàn)[1]。以信息為中心的網(wǎng)絡(luò)（Information-Centric Networking,ICN）作為一種新興的網(wǎng)絡(luò)架構(gòu)，擁有簡(jiǎn)化的網(wǎng)絡(luò)架構(gòu)、無(wú)縫的多宿主支持、高效的網(wǎng)內(nèi)緩存等特性，與當(dāng)前的5G 網(wǎng)絡(luò)需求高度融合[2-4]。ICN采用名字和地址分離的范例[5]，因此需要名字解析系統(tǒng)（Name Resolution System）存儲(chǔ)名字和地址的映射關(guān)系[6-7]。在文獻(xiàn)[8]中，廖怡等人將確定性時(shí)延的概念引入名字解析服務(wù)，并提出了確定性時(shí)延名字解析系統(tǒng)框架（DLNR）。DLNR基于不同的確定性時(shí)延約束將空間范圍劃分為嵌套的層次化彈性區(qū)域(Hierarchical Elastic Area,HEA)，形成了對(duì)應(yīng)不同等級(jí)的確定性時(shí)延的層次結(jié)構(gòu)。現(xiàn)有的根據(jù)確定性時(shí)延約束劃分的層次嵌套結(jié)構(gòu)，主要針對(duì)有時(shí)延需求上限的固定用戶。當(dāng)用戶是移動(dòng)的，并且用戶因移動(dòng)跨出當(dāng)前請(qǐng)求服務(wù)的解析節(jié)點(diǎn)所屬的HEA 后，如何快速發(fā)現(xiàn)附近可以為自己提供服務(wù)的新的名字解析節(jié)點(diǎn)從而確保服務(wù)的連續(xù)性，是現(xiàn)有結(jié)構(gòu)不能解決的問(wèn)題。因此，在基本層次結(jié)構(gòu)的基礎(chǔ)上，文中提出增強(qiáng)型鄰居結(jié)構(gòu)-地理鄰居，并介紹了一種名字解析系統(tǒng)中節(jié)點(diǎn)地理鄰居的生成方法。

1 相關(guān)工作

隨著移動(dòng)互聯(lián)網(wǎng)以及地理信息技術(shù)的迅猛發(fā)展，基于位置的服務(wù)(Location-Based Service，LBS)廣泛應(yīng)用于人類生活的方方面面[9]。比如一個(gè)人想搜索自己附近的餐館、加油站等，這種查詢最近設(shè)施的需求誕生了最近鄰查詢(k-Nearest Neighbor,kNN)。kNN 查詢問(wèn)題于1973 年由Knuth 提出的郵局問(wèn)題衍生而來(lái)[10]。最近鄰查詢的研究已趨成熟，主要包括基于歐氏空間和基于路網(wǎng)兩類[11-14]。窮舉法是最簡(jiǎn)單的kNN 查詢方法，例如一個(gè)人想搜索自己附近的餐館，實(shí)際上是通過(guò)計(jì)算自己與各個(gè)餐館之間的距離，對(duì)距離進(jìn)行排序后選取指定范圍內(nèi)的餐館。位置表示采用經(jīng)緯度坐標(biāo)，距離計(jì)算公式一般采用Haversine 大圓距離計(jì)算公式，如下：

其 中，haversine(φ1-φ2)=sin2((φ1-φ2)2)=(1-cos(φ1-φ2))2，R 為地球半徑（可取平均值6 371 km），φ1、φ2表示兩點(diǎn)的緯度，?λ表示兩點(diǎn)經(jīng)度的差值。此方法簡(jiǎn)單直觀且便于理解，適用于數(shù)據(jù)量小的情況。當(dāng)數(shù)據(jù)量較大時(shí)，必然會(huì)耗費(fèi)大量的時(shí)間和計(jì)算資源，搜索效率急劇下降。

另外，還有采用網(wǎng)格索引結(jié)構(gòu)的最近鄰查詢方法。基于地理位置的網(wǎng)格搜索算法最經(jīng)典的是Geohash 算法，由Gustavo Niemeyer 于2008 年提出，其本質(zhì)是一種基于規(guī)則網(wǎng)格的地理編碼方式，通過(guò)將二維的經(jīng)緯度坐標(biāo)編碼成一維的字符串對(duì)數(shù)據(jù)進(jìn)行降維，便于存儲(chǔ)且不會(huì)重復(fù)，具有全球唯一性[15]。Geohash 的編碼方式?jīng)Q定了其網(wǎng)格的空間遍歷方式可由Z 字形的Peano 曲線遍歷。正是這種Z 字型曲線的特點(diǎn)可以很容易計(jì)算出網(wǎng)格周邊的其他網(wǎng)格編碼。因此Geohash 在鄰近點(diǎn)的查詢上具有天然的優(yōu)勢(shì)。Z 字型曲線也有明顯的突變?nèi)毕荩斐删幋a雖然相似但距離可能相差很大的問(wèn)題，因此在查詢附近位置點(diǎn)時(shí)，首先篩選Geohash 編碼相似的位置點(diǎn)，然后進(jìn)行實(shí)際距離計(jì)算。搜索算法具體步驟：1）根據(jù)搜索半徑確定Geohash 編碼的前綴長(zhǎng)度n，n層網(wǎng)格的長(zhǎng)度大于搜索半徑，n+1 層網(wǎng)格長(zhǎng)度小于搜索半徑；2）根據(jù)搜索中心經(jīng)緯度位置，結(jié)合前綴長(zhǎng)度n，計(jì)算出搜索中心所在的父級(jí)網(wǎng)格編碼，即Geohash 前綴編碼；3）根據(jù)Geohash 編碼規(guī)律，計(jì)算出與搜索中心所在父級(jí)網(wǎng)格相鄰的其他8 個(gè)同級(jí)網(wǎng)格的編碼前綴；4）遍歷9 個(gè)父級(jí)網(wǎng)格的基本Geohash 網(wǎng)格空間，通過(guò)在數(shù)據(jù)庫(kù)中查詢匹配前綴找到空間內(nèi)的位置點(diǎn)；5）計(jì)算位置點(diǎn)到搜索中心的實(shí)際距離，滿足搜索條件則加入到結(jié)果集[16]。

2 解析節(jié)點(diǎn)地理鄰居生成方法

2.1 問(wèn)題分析

以下對(duì)文中出現(xiàn)的特殊名詞作提前說(shuō)明：1）目標(biāo)名字解析節(jié)點(diǎn)：簡(jiǎn)稱目標(biāo)節(jié)點(diǎn)，代表本身要生成地理鄰居結(jié)構(gòu)的名字解析節(jié)點(diǎn)，相當(dāng)于前文提到的搜索中心點(diǎn)。2）待選地理鄰居節(jié)點(diǎn)：需要通過(guò)一定的規(guī)則判斷該節(jié)點(diǎn)是否可以與目標(biāo)節(jié)點(diǎn)互為地理鄰居節(jié)點(diǎn)，一般與目標(biāo)節(jié)點(diǎn)同層級(jí)。若干待選地理鄰居節(jié)點(diǎn)組成待選地理鄰居節(jié)點(diǎn)集。

由于現(xiàn)場(chǎng)名字解析系統(tǒng)中地理鄰居的特殊使用場(chǎng)景，使得節(jié)點(diǎn)地理鄰居的發(fā)現(xiàn)過(guò)程不同于傳統(tǒng)的最近鄰查詢。該文通過(guò)以下分析，得出增強(qiáng)型鄰居結(jié)構(gòu)-地理鄰居構(gòu)造的關(guān)鍵點(diǎn)：1）現(xiàn)場(chǎng)名字解析系統(tǒng)提供具有不同等級(jí)確切性時(shí)延保障的解析服務(wù)，所有其他服務(wù)都必須在保證時(shí)延的前提下進(jìn)行。默認(rèn)用戶在移動(dòng)過(guò)程中對(duì)時(shí)延的要求不變，因此互為地理鄰居的解析節(jié)點(diǎn)必須保障相同時(shí)延等級(jí)的服務(wù)，即在上文提到的DLNR 框架中是同層的。2）用戶在跨出原有名字解析節(jié)點(diǎn)覆蓋區(qū)域（HEA）后需再次執(zhí)行網(wǎng)絡(luò)測(cè)距，以尋找合適的滿足自身確定性時(shí)延要求的名字解析節(jié)點(diǎn)，這個(gè)動(dòng)作會(huì)使得服務(wù)被迫中斷。因此地理鄰居節(jié)點(diǎn)必須在地理空間中距離最近，并且滿足1）中屬于同層的要求。3）用戶移動(dòng)方向的不確定性，要求在構(gòu)建名字解析節(jié)點(diǎn)的地理鄰居結(jié)構(gòu)時(shí)，節(jié)點(diǎn)不能是唯一的。某個(gè)名字解析節(jié)點(diǎn)的地理鄰居結(jié)構(gòu)必須是一個(gè)列表的形式，列表中的節(jié)點(diǎn)應(yīng)該分布在該節(jié)點(diǎn)的周圍，盡量做到方向全覆蓋（說(shuō)明：因現(xiàn)場(chǎng)需求，在某些方向可能沒(méi)有部署名字解析節(jié)點(diǎn)）。

2.2 解析節(jié)點(diǎn)地理鄰居與最近鄰查詢

現(xiàn)場(chǎng)名字解析系統(tǒng)中地理鄰居節(jié)點(diǎn)的發(fā)現(xiàn)，不完全類似于上述兩種最近鄰查詢算法。前兩者只要滿足在預(yù)設(shè)搜索半徑內(nèi)即可。由于地理鄰居結(jié)構(gòu)的特殊性，因此查詢過(guò)程不僅要滿足距離的要求，同時(shí)也要兼顧方向。

綜合分析以上兩種最近鄰查找算法，結(jié)合現(xiàn)場(chǎng)名字解析系統(tǒng)的特性，該文選擇將基于網(wǎng)格編碼的Geohash 算法做部分改進(jìn)以適應(yīng)名字解析節(jié)點(diǎn)地理鄰居選擇的要求。理由如下：1）Geohash 編碼全球統(tǒng)一具有位置可區(qū)分性，而非局部相對(duì)位置，精度可隨編碼長(zhǎng)度調(diào)整，如編碼長(zhǎng)度為6 位時(shí)，精度為610 m，編碼長(zhǎng)度為8 位時(shí)，精度可縮小至19 m。因此不同層級(jí)具有不同確定性時(shí)延約束的名字解析節(jié)點(diǎn)可根據(jù)需要選取不同的編碼長(zhǎng)度，用以標(biāo)注地理位置信息；2）網(wǎng)格規(guī)則且方向易表示，根據(jù)網(wǎng)格編碼易得到網(wǎng)格之間的相對(duì)方位。從用戶角度考慮，用戶可以根據(jù)自己的目的地網(wǎng)格，在地理鄰居節(jié)點(diǎn)列表中選擇合適的下一個(gè)為自己提供解析服務(wù)的解析節(jié)點(diǎn)；3）基于網(wǎng)格搜索的附近點(diǎn)查找本質(zhì)上是從內(nèi)而外逐步擴(kuò)大搜索范圍，無(wú)需計(jì)算所有節(jié)點(diǎn)，節(jié)省了計(jì)算資源。

2.3 基于Geohash編碼的地理鄰居發(fā)現(xiàn)機(jī)制

2.3.1 Geohash編碼

解析節(jié)點(diǎn)基于部署上線提供解析服務(wù)，易獲取精確的位置坐標(biāo)，比如經(jīng)緯度。根據(jù)名字解析節(jié)點(diǎn)所在層級(jí)的確定性時(shí)延約束，結(jié)合所在地區(qū)的網(wǎng)絡(luò)時(shí)延狀況以及節(jié)點(diǎn)分布情況確定合適的網(wǎng)格長(zhǎng)度，盡可能保證每個(gè)網(wǎng)格內(nèi)只有一個(gè)節(jié)點(diǎn)。網(wǎng)格長(zhǎng)度范圍按照Geohash 編碼前綴長(zhǎng)度對(duì)應(yīng)的精確度等級(jí)來(lái)選取；比如給定經(jīng)緯度坐標(biāo)為（39.923 201,116.390 705），根據(jù)解析節(jié)點(diǎn)的分布狀況，網(wǎng)格長(zhǎng)度在30 m 左右可以保證網(wǎng)格內(nèi)單一節(jié)點(diǎn)，Geohash 編碼前綴長(zhǎng)度為7 位時(shí)，精度為76 m，前綴長(zhǎng)度為8 位時(shí)，精度為19 m 左右，故確定采取8 位編碼長(zhǎng)度，因此該節(jié)點(diǎn)的Geohash 編碼為wx4g0ec1。

2.3.2 鄰居節(jié)點(diǎn)發(fā)現(xiàn)

目標(biāo)節(jié)點(diǎn)所在網(wǎng)格周圍共計(jì)8 個(gè)方向，分別為東(E)、南(S)、西(W)、北(N)、東南(SE)、東北(NE)、西南(SW)、西北(WN)，相鄰方向間夾角為45°。理想情況下，目標(biāo)節(jié)點(diǎn)的地理鄰居節(jié)點(diǎn)分布在這8 個(gè)方向，并且各自在該方向的直線網(wǎng)格包含節(jié)點(diǎn)集中與目標(biāo)節(jié)點(diǎn)距離最近。由此可以保障用戶無(wú)論向哪個(gè)方向移動(dòng)，都可以根據(jù)目標(biāo)節(jié)點(diǎn)的地理鄰居結(jié)構(gòu)找到下一個(gè)合適的解析節(jié)點(diǎn)。若某個(gè)方向未發(fā)現(xiàn)解析節(jié)點(diǎn)，可以用順時(shí)針45°范圍內(nèi)的節(jié)點(diǎn)代替。

目標(biāo)節(jié)點(diǎn)搜索鄰居節(jié)點(diǎn)不可能無(wú)止境，在某一方向未發(fā)現(xiàn)鄰居節(jié)點(diǎn)時(shí)必須有終止條件。單一方向搜索終止條件有兩個(gè)：一是找到鄰居節(jié)點(diǎn)即停止搜索，二是超過(guò)搜索半徑則停止搜索。條件一的優(yōu)先級(jí)高于條件二。

2.3.3 算法具體步驟

1）根據(jù)名字解析節(jié)點(diǎn)時(shí)延屬性及外在網(wǎng)絡(luò)時(shí)延、節(jié)點(diǎn)分布等狀況，確定合適的網(wǎng)格長(zhǎng)度，進(jìn)而明確Geohash 編碼長(zhǎng)度。

2）根據(jù)搜索半徑r，結(jié)合網(wǎng)格邊長(zhǎng)d，確定單一方向搜索的網(wǎng)格個(gè)數(shù)k，k=（k向上取整）。

3）根據(jù)Geohash 編碼規(guī)則計(jì)算目標(biāo)節(jié)點(diǎn)周圍8個(gè)方向的網(wǎng)格編碼。8 個(gè)方向分別是東(E)、南(S)、西(W)、北(N)、東 南(SE)、東 北(NE)、西 南(SW)、西 北(NW)，分別計(jì)算每個(gè)方向上k個(gè)網(wǎng)格的編碼。

4）按順序遍歷每個(gè)方向的網(wǎng)格編碼，與待選地理鄰居節(jié)點(diǎn)集匹配，若網(wǎng)格編碼對(duì)應(yīng)的節(jié)點(diǎn)存在，則將節(jié)點(diǎn)加入目標(biāo)節(jié)點(diǎn)的地理鄰居列表；至此，目標(biāo)節(jié)點(diǎn)此方向的地理鄰居節(jié)點(diǎn)查找成功；若節(jié)點(diǎn)不存在，轉(zhuǎn)至步驟5）。

5）根據(jù)Geohash 編碼規(guī)則計(jì)算此方向順時(shí)針45°范圍內(nèi)未被遍歷的網(wǎng)格編碼，并與待選地理鄰居節(jié)點(diǎn)集匹配，匹配成功則作為目標(biāo)節(jié)點(diǎn)此方向地理鄰居節(jié)點(diǎn)加入地理鄰居列表，未匹配成功則代表此方向查找失敗，繼續(xù)查找下一個(gè)方向；示意圖如圖1 所示，節(jié)點(diǎn)1、2、3 分別是在N、NE、E 方向上查找到的目標(biāo)節(jié)點(diǎn)的地理鄰居節(jié)點(diǎn)（以上查找動(dòng)作在步驟4）完成），在遍歷目標(biāo)節(jié)點(diǎn)SE 方向網(wǎng)格時(shí)，未找到鄰居節(jié)點(diǎn)。因此遍歷東南方向順時(shí)針45°方向上的灰色區(qū)域網(wǎng)格，節(jié)點(diǎn)4 符合要求，會(huì)作為目標(biāo)節(jié)點(diǎn)東南方向上的地理鄰居節(jié)點(diǎn)。

圖1 節(jié)點(diǎn)查找地理鄰居節(jié)點(diǎn)示意圖

6）直到所有方向都查找完全，最后輸出目標(biāo)節(jié)點(diǎn)的地理鄰居列表。

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

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)

實(shí)驗(yàn)環(huán)境：硬件環(huán)境：臺(tái)式計(jì)算機(jī)（INTEL i7-10510U,主頻為1.8 GHz，16.0 GB RAM）及其相應(yīng)配件。

軟件環(huán)境：Windows10 64 位平臺(tái)，Python3.8。

實(shí)驗(yàn)數(shù)據(jù)：現(xiàn)場(chǎng)名字解析系統(tǒng)提供名字解析服務(wù)的解析節(jié)點(diǎn)一般部署在機(jī)房，根據(jù)現(xiàn)有的IDC 數(shù)據(jù)中心分布密度，一定范圍內(nèi)的IDC 數(shù)量遠(yuǎn)遠(yuǎn)不能滿足較低時(shí)延層級(jí)的名字解析節(jié)點(diǎn)的部署要求。因此，該文選用北京市科教文化以及公司企業(yè)興趣點(diǎn)數(shù)據(jù)，在此基礎(chǔ)上剔除一些位置太近的興趣點(diǎn)，盡可能模擬真實(shí)場(chǎng)景下低時(shí)延層級(jí)的名字解析節(jié)點(diǎn)的部署場(chǎng)景。以下所有實(shí)驗(yàn)仿真結(jié)果都基于此數(shù)據(jù)。

對(duì)比算法：對(duì)kNN 查詢中的窮舉法做部分改進(jìn)，滿足上文所述地理鄰居構(gòu)造的關(guān)鍵點(diǎn)。計(jì)算所有節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離、方向，在45°扇形區(qū)域內(nèi)，選擇距離最近的名字解析節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)的地理鄰居節(jié)點(diǎn)，分別在8 個(gè)扇形區(qū)域查找目標(biāo)節(jié)點(diǎn)8 個(gè)方向的地理鄰居節(jié)點(diǎn)。此方法可以保證精確度最高，而精確度是地理鄰居構(gòu)造需考慮的關(guān)鍵因素。

3.2 評(píng)價(jià)指標(biāo)

1）算法總用時(shí)

數(shù)據(jù)集中所有節(jié)點(diǎn)查找發(fā)現(xiàn)自身地理鄰居節(jié)點(diǎn)并生成地理鄰居列表的總運(yùn)行時(shí)間。算法總用時(shí)可以直觀地描述數(shù)據(jù)集在不同節(jié)點(diǎn)數(shù)量情況下運(yùn)行時(shí)間的變化規(guī)律。

2）算法單節(jié)點(diǎn)平均用時(shí)

數(shù)據(jù)集中單個(gè)節(jié)點(diǎn)查找發(fā)現(xiàn)自身地理鄰居節(jié)點(diǎn)并生成地理鄰居列表的平均運(yùn)行時(shí)間，為算法總用時(shí)與節(jié)點(diǎn)個(gè)數(shù)的比值。現(xiàn)場(chǎng)名字解析系統(tǒng)是典型的分布式系統(tǒng)，名字解析節(jié)點(diǎn)按需上線，各自生成自身地理鄰居結(jié)構(gòu)，故單點(diǎn)平均用時(shí)更能反映算法性能。

3）查全率

具體可定義如下：查全率=實(shí)際找到鄰居節(jié)點(diǎn)個(gè)數(shù)∕理想鄰居節(jié)點(diǎn)個(gè)數(shù)=實(shí)際找到鄰居節(jié)點(diǎn)個(gè)數(shù)∕（節(jié)點(diǎn)個(gè)數(shù)×8）。用來(lái)評(píng)價(jià)解析節(jié)點(diǎn)查找地理鄰居節(jié)點(diǎn)個(gè)數(shù)的準(zhǔn)確率。

3.3 實(shí)驗(yàn)結(jié)果

參考上海市經(jīng)濟(jì)與信息化委員會(huì)在2020 年5 月公布的《上海市5G 移動(dòng)通信基站布局規(guī)劃導(dǎo)則》，結(jié)合現(xiàn)場(chǎng)名字解析系統(tǒng)中解析節(jié)點(diǎn)的部署與5G基站都有保障低時(shí)延的相似場(chǎng)景，5G 網(wǎng)絡(luò)服務(wù)能級(jí)為A 級(jí)的基站平均站間距為150 m，平均密度為50 個(gè)∕km2，大致對(duì)應(yīng)于現(xiàn)場(chǎng)名字解析系統(tǒng)中確定性時(shí)延為10 ms 的層級(jí)。不同的確定性時(shí)延需求對(duì)應(yīng)于不同的站間距。同樣，在對(duì)名字解析節(jié)點(diǎn)的地理位置進(jìn)行Geohash 編碼時(shí)，也會(huì)對(duì)應(yīng)于不同的編碼長(zhǎng)度。該文實(shí)驗(yàn)選擇對(duì)節(jié)點(diǎn)位置進(jìn)行8 位Geohash 編碼，精度在19 m 左右。Geohash 網(wǎng)格編碼查找算法與對(duì)比算法搜索半徑均設(shè)定為1 900 m，故Geohash網(wǎng)格編碼查找算法中單一方向網(wǎng)格的搜索個(gè)數(shù)k為100。實(shí)驗(yàn)結(jié)果為不同節(jié)點(diǎn)數(shù)量情況下重復(fù)運(yùn)行100次，記錄兩種算法的總運(yùn)行時(shí)間，最后取平均值。由圖2 可以看出，當(dāng)總的節(jié)點(diǎn)數(shù)量在2 000 個(gè)以下時(shí)，兩種算法運(yùn)行時(shí)間相差不大。事實(shí)上從具體數(shù)據(jù)而言，2 000 個(gè)節(jié)點(diǎn)以內(nèi)對(duì)比算法的運(yùn)行時(shí)間優(yōu)于Geohash 網(wǎng)格編碼查找算法。但隨著節(jié)點(diǎn)數(shù)量的增加，對(duì)比算法的運(yùn)行時(shí)間增長(zhǎng)速度遠(yuǎn)遠(yuǎn)高于Geohash網(wǎng)格編碼查找算法。這個(gè)可以從算法本身的特性分析原因，隨著節(jié)點(diǎn)數(shù)量不斷增加，對(duì)比算法中每個(gè)目標(biāo)節(jié)點(diǎn)與其他節(jié)點(diǎn)都要一一計(jì)算距離和角度，因此每個(gè)目標(biāo)節(jié)點(diǎn)生成地理鄰居節(jié)點(diǎn)的計(jì)算時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加而增加，那么整個(gè)數(shù)據(jù)集所有節(jié)點(diǎn)的總運(yùn)行時(shí)間會(huì)以指數(shù)形式增長(zhǎng)。而Geohash 網(wǎng)格編碼查找算法單個(gè)節(jié)點(diǎn)生成地理鄰居的過(guò)程，與數(shù)據(jù)集中節(jié)點(diǎn)的數(shù)量沒(méi)有嚴(yán)格相關(guān)性。在最大搜索半徑內(nèi)找到符合要求的節(jié)點(diǎn)即停止搜索，超過(guò)最大搜索半徑也會(huì)停止搜索，因此理論上單個(gè)目標(biāo)節(jié)點(diǎn)的計(jì)算時(shí)間維持不變，總運(yùn)算時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加按比例增加。

圖2 不同節(jié)點(diǎn)數(shù)量算法總用時(shí)

根據(jù)圖3，Geohash 網(wǎng)格編碼查找算法單個(gè)節(jié)點(diǎn)的平均運(yùn)行時(shí)間隨總節(jié)點(diǎn)數(shù)量的變化沒(méi)有明顯變化，對(duì)比算法單個(gè)節(jié)點(diǎn)的平均運(yùn)行時(shí)間隨總節(jié)點(diǎn)數(shù)量的增加而增加。說(shuō)明Geohash 網(wǎng)格編碼查找算法單節(jié)點(diǎn)運(yùn)行時(shí)間與節(jié)點(diǎn)數(shù)量無(wú)關(guān)，僅取決于該節(jié)點(diǎn)周圍其他節(jié)點(diǎn)的分布狀況。

圖3 不同節(jié)點(diǎn)數(shù)量算法單節(jié)點(diǎn)用時(shí)

圖4 表示Geohash 網(wǎng)格編碼查找算法在幾乎相同的查全率情況下，設(shè)置不同的搜索半徑（即不同k值）時(shí)的算法運(yùn)行時(shí)間。可以看出，k值越大，即搜索半徑設(shè)置越大，運(yùn)行時(shí)間也隨之增加。算法本身在查找每個(gè)方向的地理鄰居節(jié)點(diǎn)時(shí)，遵循找到即停止搜索的原則。那么查全率不變意味著增大了搜索半徑，鄰居節(jié)點(diǎn)數(shù)量并沒(méi)有增加，由此得出運(yùn)行時(shí)間的增加集中在了搜索某些沒(méi)有地理鄰居節(jié)點(diǎn)存在的方向上。通過(guò)查全率與搜索半徑的對(duì)比分析，可以明確知道要在盡可能保證查全率的同時(shí)兼顧運(yùn)行時(shí)間，就需要設(shè)置合適的搜索半徑。

圖4 Geohash網(wǎng)格編碼查找算法相同查全率下不同k值運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

該文通過(guò)對(duì)Geohash 編碼周邊查找算法的改進(jìn)，提出了基于Geohash 編碼的現(xiàn)場(chǎng)名字解析系統(tǒng)地理鄰居的發(fā)現(xiàn)方法，以適應(yīng)現(xiàn)場(chǎng)名字解析系統(tǒng)的特殊場(chǎng)景。并且通過(guò)實(shí)驗(yàn)驗(yàn)證，與kNN 查詢中改進(jìn)的窮舉法對(duì)比，該文提出的算法在小規(guī)模數(shù)據(jù)（節(jié)點(diǎn)數(shù)量2 000 個(gè)以下）中與對(duì)比算法運(yùn)行時(shí)間差別不大，在大規(guī)模數(shù)據(jù)（節(jié)點(diǎn)數(shù)量2 000 個(gè)以上）情況下，算法平均耗時(shí)下降60%以上，且隨著節(jié)點(diǎn)數(shù)量的不斷上升，算法耗時(shí)下降比例會(huì)繼續(xù)增加，顯現(xiàn)出了明顯的優(yōu)越性。另外，該文所提算法運(yùn)行時(shí)間與搜索半徑有一定相關(guān)性，因此需要設(shè)置合適的搜索半徑，以保證在較短的時(shí)間內(nèi)盡可能多地找到目標(biāo)節(jié)點(diǎn)的地理鄰居節(jié)點(diǎn)，可以作為后續(xù)研究方向，設(shè)計(jì)更加合理的算法。