張 芳，孫 鵬，李 楊

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

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

1 相關(guān)工作

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

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

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

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

2.1 問題分析

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

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

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

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

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

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

2.3.1 Geohash編碼

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

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

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

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

2.3.3 算法具體步驟

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

3.2 評價指標

1）算法總用時

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

2）算法單節(jié)點平均用時

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

3）查全率

具體可定義如下：查全率=實際找到鄰居節(jié)點個數(shù)∕理想鄰居節(jié)點個數(shù)=實際找到鄰居節(jié)點個數(shù)∕（節(jié)點個數(shù)×8）。用來評價解析節(jié)點查找地理鄰居節(jié)點個數(shù)的準確率。

3.3 實驗結(jié)果

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

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

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

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

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

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

4 結(jié)束語

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