現場名字解析系統中地理鄰居發現機制研究

張 芳，孫 鵬，李 楊

（1.中國科學院大學，北京 100049；2.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，北京 100190）

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

1 相關工作

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

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

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

2 解析節點地理鄰居生成方法

2.1 問題分析

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

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

2.2 解析節點地理鄰居與最近鄰查詢

現場名字解析系統中地理鄰居節點的發現，不完全類似于上述兩種最近鄰查詢算法。前兩者只要滿足在預設搜索半徑內即可。由于地理鄰居結構的特殊性，因此查詢過程不僅要滿足距離的要求，同時也要兼顧方向。

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

2.3 基于Geohash編碼的地理鄰居發現機制

2.3.1 Geohash編碼

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

2.3.2 鄰居節點發現

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

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

2.3.3 算法具體步驟

1）根據名字解析節點時延屬性及外在網絡時延、節點分布等狀況，確定合適的網格長度，進而明確Geohash 編碼長度。

2）根據搜索半徑r，結合網格邊長d，確定單一方向搜索的網格個數k，k=（k向上取整）。

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

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

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

圖1 節點查找地理鄰居節點示意圖

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

3 實驗結果與分析

3.1 實驗環境與參數

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

軟件環境：Windows10 64 位平臺，Python3.8。

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

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

3.2 評價指標

1）算法總用時

數據集中所有節點查找發現自身地理鄰居節點并生成地理鄰居列表的總運行時間。算法總用時可以直觀地描述數據集在不同節點數量情況下運行時間的變化規律。

2）算法單節點平均用時

數據集中單個節點查找發現自身地理鄰居節點并生成地理鄰居列表的平均運行時間，為算法總用時與節點個數的比值。現場名字解析系統是典型的分布式系統，名字解析節點按需上線，各自生成自身地理鄰居結構，故單點平均用時更能反映算法性能。

3）查全率

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

3.3 實驗結果

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

圖2 不同節點數量算法總用時

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

圖3 不同節點數量算法單節點用時

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

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

4 結束語

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