資源預(yù)覆蓋自動(dòng)路由檢索系統(tǒng)設(shè)計(jì)與研發(fā)*

喻 敏

（中國(guó)移動(dòng)通信集團(tuán)廣東有限公司中山分公司，廣東 中山528400）

0 引 言

通信運(yùn)營(yíng)商全業(yè)務(wù)運(yùn)營(yíng)戰(zhàn)略發(fā)展規(guī)劃中，基礎(chǔ)網(wǎng)絡(luò)資源未來呈極快速、規(guī)?；l(fā)展趨勢(shì)。基礎(chǔ)網(wǎng)絡(luò)資源數(shù)據(jù)管理必須更加規(guī)范化、準(zhǔn)確化和可視化，以應(yīng)對(duì)由傳統(tǒng)業(yè)務(wù)轉(zhuǎn)變?yōu)槿珮I(yè)務(wù)運(yùn)營(yíng)。目前，通信運(yùn)營(yíng)商在進(jìn)行網(wǎng)絡(luò)和業(yè)務(wù)規(guī)劃時(shí)，無法準(zhǔn)確根據(jù)現(xiàn)有網(wǎng)絡(luò)資源和目標(biāo)用戶分布作出最適應(yīng)當(dāng)前基礎(chǔ)網(wǎng)絡(luò)分布情況的網(wǎng)格化規(guī)劃管理，給全業(yè)務(wù)運(yùn)營(yíng)工作及業(yè)務(wù)推廣帶來了一定影響。為提高對(duì)全業(yè)務(wù)規(guī)劃的支撐，需研發(fā)出全業(yè)務(wù)網(wǎng)絡(luò)和業(yè)務(wù)支撐應(yīng)用系統(tǒng)，功能要實(shí)現(xiàn)資源預(yù)覆蓋，規(guī)劃移動(dòng)新業(yè)務(wù)。系統(tǒng)可查找出待規(guī)劃點(diǎn)與最近光交設(shè)備間的最優(yōu)路由，該路由經(jīng)過的傳輸媒介包括了管道、人手井、吊線和撐點(diǎn)等。在當(dāng)前移動(dòng)通信網(wǎng)絡(luò)規(guī)模大、結(jié)構(gòu)復(fù)雜的情況下，要實(shí)現(xiàn)高效的尋找最優(yōu)路由，需要制定出一套高效的路由搜索算法。

1 智能算法原理

Dijkstra算法在地理信息系統(tǒng)（GIS）領(lǐng)域的所有求解最短路徑算法[1]中，是最普遍的算法之一。但是，由于現(xiàn)行系統(tǒng)網(wǎng)絡(luò)規(guī)模很大，頂點(diǎn)數(shù)目多，導(dǎo)致算法效率低下。本系統(tǒng)采用啟發(fā)式搜索算法——A*算法，能保證最短路的搜索向終點(diǎn)方向進(jìn)行，明顯優(yōu)于Dijkstra算法毫無方向的向四周搜索。

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

Dijkstra算法描述：

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

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

（3）修改從V出發(fā)到集合V-S上任一頂點(diǎn)Vk可達(dá)的最短路徑長(zhǎng)度。

Dijkstra算法是無方向的向四周搜索，針對(duì)移動(dòng)通信網(wǎng)絡(luò)規(guī)模大的情況，如采用以上經(jīng)典Dijkstra算法用于搜索資源預(yù)覆蓋路由，將無法保證搜索效率?？紤]到移動(dòng)通信傳輸網(wǎng)絡(luò)中可以根據(jù)資源經(jīng)緯坐標(biāo)估算各點(diǎn)的距離值，即可估算到某一點(diǎn)到目標(biāo)點(diǎn)的距離，因此本系統(tǒng)考慮用改進(jìn)A*算法進(jìn)行路由搜索。

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

節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù)， g ( n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)， h ( n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。

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

對(duì)于幾何網(wǎng)絡(luò)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價(jià)值，即：

這樣估價(jià)函數(shù)f在g值一定的情況下，或多或少會(huì)受估價(jià)值h的制約。節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對(duì)就小，能保證最短路的搜索向終點(diǎn)方向進(jìn)行，明顯優(yōu)于Dijstra算法毫無方向地向四周搜索。

搜索過程偽代碼如下：

創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)；

計(jì)算起點(diǎn)的估價(jià)值；

將起點(diǎn)放入OPEN表；

while(OPEN!=NULL)

{

從OPEN表中取估價(jià)值f最小的節(jié)點(diǎn)n;

if(n節(jié)點(diǎn)==目標(biāo)節(jié)點(diǎn)){

break;

}

for(當(dāng)前節(jié)點(diǎn)n的每個(gè)子節(jié)點(diǎn)X)

{

算X的估價(jià)值;

if(X in OPEN)

{

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

把n設(shè)置為X的父親;

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

}

}

if(X inCLOSE){

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

把X設(shè)置為X的父親;

更新CLOSE表中的估價(jià)值;

把X節(jié)點(diǎn)放入OPEN//取最小路徑的估價(jià)值}

if(X not inboth){

n設(shè)置為X的父親;

求X的估價(jià)值;

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

}

}//end for

將n節(jié)點(diǎn)插入CLOSE表中;

按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;//實(shí)際上是比較OPEN表內(nèi)節(jié)點(diǎn)f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。

}//end while(OPEN!=NULL)

保存路徑，即從終點(diǎn)開始，每個(gè)節(jié)點(diǎn)沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)。

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

資源預(yù)先覆蓋所在的應(yīng)用系統(tǒng)屬于典型的B/S體系結(jié)構(gòu)，如圖1所示。

圖1 系統(tǒng)架構(gòu)

針對(duì)資源預(yù)覆蓋這種實(shí)際應(yīng)用，網(wǎng)絡(luò)環(huán)境是典型的靜態(tài)環(huán)境，網(wǎng)絡(luò)結(jié)構(gòu)為“管井-管道段-管井”或“撐點(diǎn)-吊線段-撐點(diǎn)”這種點(diǎn)-線結(jié)構(gòu)。因此，采用A*算法非常適合。

其中，網(wǎng)絡(luò)各資源信息存儲(chǔ)在數(shù)據(jù)庫的多個(gè)數(shù)據(jù)表中。從數(shù)據(jù)庫表中可獲取各個(gè)資源的經(jīng)緯度坐標(biāo)、管道/吊線長(zhǎng)度等組成網(wǎng)絡(luò)的各環(huán)節(jié)基本信息。但是，這些數(shù)據(jù)都處于松耦合存儲(chǔ)狀態(tài)，不能直接用于執(zhí)行路由算法。因此，需要從編寫接口函數(shù)獲取各資源的基本信息情況用于算法執(zhí)行：

Double GetDistance()//此接口用于計(jì)算指定兩點(diǎn)經(jīng)緯度坐標(biāo)間的距離，需要根據(jù)GIS地理信息模型，按照標(biāo)準(zhǔn)公式計(jì)算兩經(jīng)緯度間的距離，可直接利用GIS平臺(tái)的相關(guān)接口計(jì)算

List

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

以上接口內(nèi)部實(shí)現(xiàn)基本原理，是通過SQL語句對(duì)數(shù)據(jù)庫表進(jìn)行查詢，并根據(jù)各庫表間的主外鍵關(guān)系進(jìn)行整合查詢得出，此處不展開描述。

當(dāng)準(zhǔn)備好以上接口后，按照如下應(yīng)用A*算法：

f ( n)為起始點(diǎn)到目標(biāo)光交設(shè)施的最短距離，

g ( n)為起始點(diǎn)經(jīng)由管井或撐點(diǎn)n到目標(biāo)光交設(shè)施的估價(jià)函數(shù)。這里，直接通過GetDistance計(jì)算兩點(diǎn)間的距離為估價(jià)值。

h( n)是從管井或撐點(diǎn)n到目標(biāo)光交接設(shè)施的最佳路徑的估計(jì)代價(jià)。

程序按照以上偽代碼進(jìn)行展開運(yùn)行，從而完成此模塊的設(shè)計(jì)。模塊運(yùn)行情況如表1所示。

表1 模塊運(yùn)行情況

根據(jù)以上運(yùn)算結(jié)果可以看出，執(zhí)行效果并不讓人滿意，執(zhí)行情況不夠穩(wěn)定，算法應(yīng)用仍需改進(jìn)。

經(jīng)過對(duì)原有算法程序的分析研究發(fā)現(xiàn)，存在如下問題：

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

（2）GetDistance是通過GIS地理模型計(jì)算兩經(jīng)緯度間的距離，計(jì)算過程需要調(diào)用GIS平臺(tái)的應(yīng)用服務(wù)，因此也較耗時(shí)。

以上兩點(diǎn)為導(dǎo)致算法執(zhí)行效率低下的原因，因此作如下改進(jìn)：

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

（2）考慮到做資源預(yù)覆蓋時(shí)要搜索的范圍主要都在半徑1 000 m內(nèi)，在這種局部范圍內(nèi)，空間地理坐標(biāo)可近似看作平面坐標(biāo)，因此該函數(shù)采取兩點(diǎn)間歐幾理德距離（直線距離）做為計(jì)算估價(jià)值。

經(jīng)過以上改進(jìn)后，再次運(yùn)行后的結(jié)果如表2所示。

表2 改進(jìn)后的運(yùn)行結(jié)果

分析以上運(yùn)行結(jié)果發(fā)現(xiàn)，本次算法改良很成功。無論起始和目標(biāo)點(diǎn)遠(yuǎn)近與否，計(jì)算時(shí)間均穩(wěn)定在7～8 s，計(jì)算得到的結(jié)果也均符合要求。因此，算法在移動(dòng)資源預(yù)覆蓋的自動(dòng)路由應(yīng)用中獲得了成功。

3 系統(tǒng)功能驗(yàn)證

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

點(diǎn)擊“資源分析—500 m預(yù)覆蓋分析”，點(diǎn)擊“自選圓心”，然后在地圖上面點(diǎn)擊一個(gè)點(diǎn)，會(huì)自動(dòng)獲取X、Y坐標(biāo)。然后，將搜索出附近的資源，并在下面的列表中顯示出來，如圖2所示。圖2中圈圈的位置有人樣的位置，代表圓心的位置。

圖2 資源搜索

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

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

4 結(jié) 語

本文通過對(duì)Dijkstra和A*算法的對(duì)比，選用了搜索效率更高的A*算法，并在應(yīng)用算法時(shí)作出了改進(jìn)。改進(jìn)算法后的系統(tǒng)可查找出待規(guī)劃點(diǎn)與最近光交設(shè)備間的最優(yōu)路由，而該路由經(jīng)過的傳輸媒介包括了管道、人手井、吊線和撐點(diǎn)等。在移動(dòng)通信網(wǎng)絡(luò)規(guī)模大、結(jié)構(gòu)復(fù)雜的情況下，該系統(tǒng)實(shí)現(xiàn)了高效的尋找最優(yōu)路由。經(jīng)過系統(tǒng)使用驗(yàn)證，最終證明了該設(shè)計(jì)是成功可行的。

圖3 資源顯示

圖4 預(yù)覆蓋自動(dòng)路由

參考文獻(xiàn)：

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

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

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