彭金明 黃大巧 陳勝君 張奇

摘 要：隨著LTE的商用，無線網(wǎng)絡(luò)規(guī)模越來越大，網(wǎng)絡(luò)設(shè)備越來越復(fù)雜，運(yùn)營商為了網(wǎng)絡(luò)故障的響應(yīng)效率，投入了大量成本進(jìn)行網(wǎng)絡(luò)運(yùn)維，然而網(wǎng)絡(luò)運(yùn)維僅僅注重管理流程上和工具軟件方法上的改進(jìn)，卻忽視了基站故障物流處理能力，而這個方面往往是提高基站響應(yīng)速度的最佳手段，考慮到基站維保需要固定的檢測周期，移動基站的分布分散的特征，本文采用了一種通信故障設(shè)備物流建模的DA算法，通過對基站退服設(shè)備的信息挖掘，制定最優(yōu)的收集機(jī)制，大大提高的基站維保的響應(yīng)速度。使無線網(wǎng)絡(luò)更加具有競爭力，使運(yùn)營商在得到更加快速的備件服務(wù)、更加快速的故障響應(yīng)以及更加貼近的IT服務(wù)的情況下，減少企業(yè)的運(yùn)營成本。

關(guān)鍵詞：無線維護(hù)；通信設(shè)備；物流建模；迪克斯拉特（Dijkstra）算法

1 背景

對于無線網(wǎng)絡(luò)維護(hù)來說，基站是通信系統(tǒng)中很重要的一個節(jié)點，一旦某個基站出現(xiàn)退服，則該基站天線覆蓋范圍內(nèi)信號會中斷或者嚴(yán)重變?nèi)?，會?yán)重影響到覆蓋范圍內(nèi)客戶的正常通話。對于基站代維的我們來說，保證基站的正常運(yùn)行是我們?nèi)粘＞S護(hù)的重中之重，但是有些時候基站退服是不可避免的，所以只有增強(qiáng)代維人員的技術(shù)水平，降低退服處理歷時，才能保證移動公司在激烈的市場競爭中立于不敗之地。將會引起網(wǎng)絡(luò)調(diào)整和網(wǎng)絡(luò)容量的排除或者更換設(shè)備都需要上站，為了提高基站故障的處理能力，對于基站維保單位來說，需要出門收集故障設(shè)備，但是由于故障問題設(shè)備并不是集中在一起的，這就需要驅(qū)車趕往每個基站點進(jìn)行收集工作，所以就要求有一個較好的行車路線，使得其在取到所有的設(shè)備的同時，行進(jìn)的路線最短，耗時最少，這樣既可以節(jié)約成本，又可以提高勞動效率。

2 算法介紹及問題建模

2.1 算法介紹

利用計算機(jī)計算效率快以及現(xiàn)有的資源，我們將利用迪克斯拉特（Dijkstra）算法以及電子地圖為我們方案提供支持。我們首先電子地圖獲取點與點之間的最短的距離，之后再利用迪克斯拉特（Dijkstra）算法尋找出一個較好的行車路線。同時考慮為了不消耗過多的計算機(jī)資源，同時對迪克斯拉特（Dijkstra）算法進(jìn)行了優(yōu)化，找到最優(yōu)的路徑。

2.2 應(yīng)用建模

無線通信設(shè)備維保物流面臨的問題主要針對地圖上收取設(shè)備的站點非常多的情況，因為只有在這種情況下，算法的優(yōu)越性才能體現(xiàn)出來，而當(dāng)點比較少的時候，不同路徑的距離差異并不明顯。綜合迪克斯拉特（Dijkstra）算法，對較多收取設(shè)備站點的情況進(jìn)行路徑規(guī)劃。實際問題如圖所示，我們需要從圓點處移動到剩下的每一個標(biāo)記點處，最后再返回到圓點處的標(biāo)記點。

此時，站點在幾十個以內(nèi)，假設(shè)車的容量足夠大，可以考慮把情況表示如下圖2：

圓點代表出發(fā)點，三角形代表站點，則首先按照大致方位進(jìn)行分區(qū)，使得每個區(qū)內(nèi)的數(shù)量在10個以內(nèi)，以減少每個區(qū)的運(yùn)算量。然后分別對每個區(qū)用迪克斯拉特算法計算最短路徑（此時每個區(qū)的起點取為離上一個區(qū)最近的點，而終點取為離下一個區(qū)最近的點），如上圖中，從圓點首先到達(dá)1，然后1到2的路徑采用迪克斯拉特算法，即可走完此區(qū)域。這樣依次按圖中箭頭，即可在每個區(qū)域內(nèi)都按照迪克斯拉特算法算出的路徑走完，最終回到圓點。

當(dāng)站點點數(shù)進(jìn)一步增加，分的區(qū)域也變得更多的時候，區(qū)域與區(qū)域之間的路徑也應(yīng)考慮在內(nèi)，如下圖，此時可把區(qū)域看成點，然后用迪克斯拉特算法規(guī)劃出區(qū)域與區(qū)域之間的最優(yōu)路徑，此時，起點取為圓點點（車輛出發(fā)點），終點取為離圓點最近的區(qū)域。這樣，車輛行駛的距離，一方面從區(qū)域到區(qū)域之間是最短的，另一方面，在每一個區(qū)域內(nèi)部也是最短的。

如果車輛的容量并非足夠大，則需要先統(tǒng)計地圖中設(shè)備的量，假設(shè)為X，假設(shè)車輛的容量為M，那么車輛需要運(yùn)的次數(shù)為T=（[X/M]+E）

這時候我們先將地圖縱向或者縱向分成 個區(qū)域，調(diào)整邊界，保證前面每一塊區(qū)域的數(shù)量盡量接近S=K*N

接下來再調(diào)整其剩下的方向，保證前面劃出的區(qū)域數(shù)量盡量接近于汽車容量M。

3 算法應(yīng)用效果分析

以杭州市某運(yùn)營商無線基站維保物流為例，進(jìn)行算法建模與傳統(tǒng)方式比較。以比較算法在應(yīng)用中的優(yōu)劣和效果。圖4是我們假設(shè)的一次收取設(shè)備的過程，我們按著一般的經(jīng)驗選擇路線，在圖上，我們可以看到，路線可以說是按照我們一般平常車輛習(xí)慣的路線執(zhí)行，而總共我們走的路程為20.1公里。

將上圖化簡，并編號得到下面的圖

接下來我們要得到每兩個點之間的最短距離

利用迪克斯拉特（Dijkstra）算法我們可以得到最短路徑為0→1→5→3→2→4→6→7→0

總的距離為15.8公里，相對最初的選擇提高了21.4%的效率，時間節(jié)省了26.7%。

4 結(jié)論

結(jié)合迪克斯特拉（Djikstra）算法和復(fù)雜的無線基站物流的新的發(fā)展，提出了一種通信故障設(shè)備物流建模的DA算法，應(yīng)用實踐說明了按照該算法設(shè)計的路線，對提高整個網(wǎng)絡(luò)維保的經(jīng)濟(jì)型，時效性、安全性、溝通性和方便等性能都取得了較好的效果。當(dāng)結(jié)點就比較多，求解的復(fù)雜度就會很大對于路徑規(guī)劃問題，通過劃分區(qū)域，并分別在區(qū)域間和區(qū)域內(nèi)應(yīng)用該算法，使得整體和局部的路徑都得到優(yōu)化，從而可以達(dá)到省時省力、高效快捷的目的。

[參考文獻(xiàn)]

[1]Wikipedia.Dijkstra's algorithm.

[2]Rosen K H，Krithivasan K.Discrete mathematics and its applications[M].New York：McGraw-Hill，1999.P652.

[3]Rosen K H，Krithivasan K.Discrete mathematics and its applications[M].New York：McGraw-Hill，1999.P653.