資源預覆蓋自動路由檢索系統設計與研發*

喻 敏

（中國移動通信集團廣東有限公司中山分公司，廣東 中山528400）

0 引 言

通信運營商全業務運營戰略發展規劃中，基礎網絡資源未來呈極快速、規模化發展趨勢。基礎網絡資源數據管理必須更加規范化、準確化和可視化，以應對由傳統業務轉變為全業務運營。目前，通信運營商在進行網絡和業務規劃時，無法準確根據現有網絡資源和目標用戶分布作出最適應當前基礎網絡分布情況的網格化規劃管理，給全業務運營工作及業務推廣帶來了一定影響。為提高對全業務規劃的支撐，需研發出全業務網絡和業務支撐應用系統，功能要實現資源預覆蓋，規劃移動新業務。系統可查找出待規劃點與最近光交設備間的最優路由，該路由經過的傳輸媒介包括了管道、人手井、吊線和撐點等。在當前移動通信網絡規模大、結構復雜的情況下，要實現高效的尋找最優路由，需要制定出一套高效的路由搜索算法。

1 智能算法原理

Dijkstra算法在地理信息系統（GIS）領域的所有求解最短路徑算法[1]中，是最普遍的算法之一。但是，由于現行系統網絡規模很大，頂點數目多，導致算法效率低下。本系統采用啟發式搜索算法——A*算法，能保證最短路的搜索向終點方向進行，明顯優于Dijkstra算法毫無方向的向四周搜索。

Dijkstra算法原理。首先，引進一個輔助向量，它的每個分量D表示當前所找到的從始點V到每個終點Vi的最短路徑的長度。如D[3]=2表示從始點V到終點3的路徑相對最小長度為2。這里強調相對，就是說在算法過程中D的值是在不斷逼近最終結果，但在過程中不一定就等于最短路徑長度。它的初始狀態為：若從V到Vi有弧，則D為弧上的權值；否則，置D為∞。顯然，長度為D[j]=Min{D|Vi∈V-S}的路徑就是從V出發的長度最短的一條最短路徑，此路徑為(V,Vj)。那么，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是Vk，則這條路徑或者是(V,Vk)，或者是(V,Vj,Vk)。它的長度或者是從V到Vk的弧上的權值，或者是D[j]和從Vj到Vk的弧上的權值之和。一般情況下，假設S為已求得最短路徑的終點的集合，則可證明下一條最短路徑（設其終點為X）或者是弧(V,X)，或者是中間只經過S中的頂點而最后到達頂點X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D|Vi∈V}。其中，D或者是弧(V,Vj)上的權值，或者是D[k](Vk∈S)和弧(Vk,Vi)上的權值之和。

Dijkstra算法描述：

（1）arcs表示弧上的權值。若不存在，則置arcs為∞。S為已找到從V出發的最短路徑的終點的集合，初始狀態為空集。那么，從V出發到圖上其余各頂點Vi可能達到的最短路徑長度的初值為D=arcs[Locate Vex(G,V),i](vi∈ v2)；

（2）選擇Vj，使得D[j]=Min{D|Vi∈S}；

（3）修改從V出發到集合V-S上任一頂點Vk可達的最短路徑長度。

Dijkstra算法是無方向的向四周搜索，針對移動通信網絡規模大的情況，如采用以上經典Dijkstra算法用于搜索資源預覆蓋路由，將無法保證搜索效率。考慮到移動通信傳輸網絡中可以根據資源經緯坐標估算各點的距離值，即可估算到某一點到目標點的距離，因此本系統考慮用改進A*算法進行路由搜索。

A*算法描述如下：A*（A-Star）算法是一種靜態網絡中求解最短路最有效的方法[2]。公式表示為 f ( n )= g (n )+ h(n)，其中 f ( n)是從初始點經由

節點n到目標點的估價函數， g ( n)是在狀態空間中從初始節點到n節點的實際代價， h ( n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在于估價函數 h ( n)的選取。估價值 h ( n)≤ n 到目標節點的距離實際值，這種情況下搜索的點數多，搜索范圍大，效率低，但能得到最優解。如果估價值大于實際值，搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

對于幾何網絡來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即：

這樣估價函數f在g值一定的情況下，或多或少會受估價值h的制約。節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點方向進行，明顯優于Dijstra算法毫無方向地向四周搜索。

搜索過程偽代碼如下：

創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點；

計算起點的估價值；

將起點放入OPEN表；

while(OPEN!=NULL)

{

從OPEN表中取估價值f最小的節點n;

if(n節點==目標節點){

break;

}

for(當前節點n的每個子節點X)

{

算X的估價值;

if(X in OPEN)

{

if(X的估價值小于OPEN表的估價值){

把n設置為X的父親;

更新OPEN表中的估價值;//取最小路徑的估價值

}

}

if(X inCLOSE){

if(X的估價值小于CLOSE表的估價值){

把X設置為X的父親;

更新CLOSE表中的估價值;

把X節點放入OPEN//取最小路徑的估價值}

if(X not inboth){

n設置為X的父親;

求X的估價值;

并將X插入OPEN表中;//還沒有排序

}

}//end for

將n節點插入CLOSE表中;

按照估價值將OPEN表中的節點排序;//實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。

}//end while(OPEN!=NULL)

保存路徑，即從終點開始，每個節點沿著父節點移動直至起點。

2 系統設計與實現

資源預先覆蓋所在的應用系統屬于典型的B/S體系結構，如圖1所示。

圖1 系統架構

針對資源預覆蓋這種實際應用，網絡環境是典型的靜態環境，網絡結構為“管井-管道段-管井”或“撐點-吊線段-撐點”這種點-線結構。因此，采用A*算法非常適合。

其中，網絡各資源信息存儲在數據庫的多個數據表中。從數據庫表中可獲取各個資源的經緯度坐標、管道/吊線長度等組成網絡的各環節基本信息。但是，這些數據都處于松耦合存儲狀態，不能直接用于執行路由算法。因此，需要從編寫接口函數獲取各資源的基本信息情況用于算法執行：

Double GetDistance()//此接口用于計算指定兩點經緯度坐標間的距離，需要根據GIS地理信息模型，按照標準公式計算兩經緯度間的距離，可直接利用GIS平臺的相關接口計算

List

Double GetLineLength()//獲取指定管道段/吊線段的長度，這是資源的基本屬性，可直接獲取

以上接口內部實現基本原理，是通過SQL語句對數據庫表進行查詢，并根據各庫表間的主外鍵關系進行整合查詢得出，此處不展開描述。

當準備好以上接口后，按照如下應用A*算法：

f ( n)為起始點到目標光交設施的最短距離，

g ( n)為起始點經由管井或撐點n到目標光交設施的估價函數。這里，直接通過GetDistance計算兩點間的距離為估價值。

h( n)是從管井或撐點n到目標光交接設施的最佳路徑的估計代價。

程序按照以上偽代碼進行展開運行，從而完成此模塊的設計。模塊運行情況如表1所示。

表1 模塊運行情況

根據以上運算結果可以看出，執行效果并不讓人滿意，執行情況不夠穩定，算法應用仍需改進。

經過對原有算法程序的分析研究發現，存在如下問題：

（1）GetDistance()、GetNextNodes() 和GetLineLength()等函數接口，均需要實時讀取數據庫中的資源信息來整合這些基本數據。整個算法執行下來需重復多次執行這些函數，每次都需進行數據庫訪問，效率很低；

（2）GetDistance是通過GIS地理模型計算兩經緯度間的距離，計算過程需要調用GIS平臺的應用服務，因此也較耗時。

以上兩點為導致算法執行效率低下的原因，因此作如下改進：

（1）在執行算法前，預先把半徑1 000 m范圍內的所有資源一次讀取出來，在內存中形成一份資源數據。當需要獲取資源屬性或計算資源距離時，直接從內存中讀取。如果在內存中找不到對應的數據，再考慮從數據庫中讀取。這樣改進可減少大量重復讀取數據庫的操作。

（2）考慮到做資源預覆蓋時要搜索的范圍主要都在半徑1 000 m內，在這種局部范圍內，空間地理坐標可近似看作平面坐標，因此該函數采取兩點間歐幾理德距離（直線距離）做為計算估價值。

經過以上改進后，再次運行后的結果如表2所示。

表2 改進后的運行結果

分析以上運行結果發現，本次算法改良很成功。無論起始和目標點遠近與否，計算時間均穩定在7～8 s，計算得到的結果也均符合要求。因此，算法在移動資源預覆蓋的自動路由應用中獲得了成功。

3 系統功能驗證

資源預覆蓋用于業務人員開通業務時的資源預判斷，以即將開通業務的地方為中心，查找指定范圍內的接入設備（分光器設備、光交接箱），并將搜索結果按距離進行排序，用戶選擇距離適合的分光器設備、光交接箱后，系統將會生成推薦的最短路由走向。

點擊“資源分析—500 m預覆蓋分析”，點擊“自選圓心”，然后在地圖上面點擊一個點，會自動獲取X、Y坐標。然后，將搜索出附近的資源，并在下面的列表中顯示出來，如圖2所示。圖2中圈圈的位置有人樣的位置，代表圓心的位置。

圖2 資源搜索

而此處的搜索資源只有一處，雙擊列表上面的資源。資源的位置就在500 m范圍的區域內高亮顯示出來，如圖3所示。圖3中圈圈的地方就是資源高亮顯示的位置。

雙擊查詢列表上面的一項資源，就可以定位到該項資源的路由信息，路由的走向如圖4所示。

4 結 語

本文通過對Dijkstra和A*算法的對比，選用了搜索效率更高的A*算法，并在應用算法時作出了改進。改進算法后的系統可查找出待規劃點與最近光交設備間的最優路由，而該路由經過的傳輸媒介包括了管道、人手井、吊線和撐點等。在移動通信網絡規模大、結構復雜的情況下，該系統實現了高效的尋找最優路由。經過系統使用驗證，最終證明了該設計是成功可行的。

圖3 資源顯示

圖4 預覆蓋自動路由

參考文獻：

[1] 萊維丁.算法設計與分析基礎[M].北京：清華大學出版社,2007.Anany Levitin.Algorithm Design and Analysis Foundation[M].Beijing：Tsinghua University Press,2007.

[2] 王萬森.人工智能原理及其應用[M].北京：電子工業出版社,2007.WANG Wan-sen.Principles of Artificial Intelligence

and Its Application[M].Beijing：Publishing House of Electronics Industry,2007.