基于路徑搜索算法的通信業(yè)務優(yōu)化研究

陳郁喬

【摘要】 隨著光纖逐步成為傳輸業(yè)務的主要載體，越來越多的接入業(yè)務基于光路通道開放，由于通信網(wǎng)絡資源有限，業(yè)務擴張帶來的壓力與日俱增，如何通過有效的方法，對現(xiàn)網(wǎng)業(yè)務進行調(diào)整優(yōu)化，實現(xiàn)更好的市場效應，成為通信維護管理工作的一大挑戰(zhàn)。本文嘗試引入路徑搜索算法，對主干業(yè)務系統(tǒng)進行路徑分析和優(yōu)化，找到基于資源現(xiàn)狀且面向業(yè)務最優(yōu)分配的調(diào)度方案，在完成業(yè)務需求的同時，實現(xiàn)最佳的資源配置，并在現(xiàn)網(wǎng)中實踐應用。

【關鍵詞】 路徑搜索 通信資源 業(yè)務優(yōu)化

一、引言

在日常資源調(diào)度中，由于現(xiàn)網(wǎng)業(yè)務的緊迫性，需要及時根據(jù)資源情況調(diào)配業(yè)務需求。前期的調(diào)配本著快速完工形成市場效益，在資源分配上并非最優(yōu)，甚至會使部分片區(qū)資源呈現(xiàn)不合理的緊缺。隨著網(wǎng)絡規(guī)模擴大和建設拓展，維護管理中亟需對業(yè)務合理優(yōu)化，釋放緊缺資源，優(yōu)化網(wǎng)絡架構。

隨著數(shù)年來資源數(shù)據(jù)信息化的建設，已經(jīng)實現(xiàn)了資源數(shù)據(jù)的平臺化。在實際分配過程中，不同的需求部門對業(yè)務分配方式有各自的側(cè)重關注點，如市場部門關注業(yè)務覆蓋范圍，即資源的可達性；網(wǎng)絡線條關注資源的提供和承載能力；業(yè)務維護部門關注開通和維護的便利性；建設部門關注建設和當前需求的均衡性等。此外，還有業(yè)務的穩(wěn)定性、后期的擴容性等等。

基于這種全局化的資源分配需求，以及對后續(xù)拓展進行網(wǎng)絡優(yōu)化工作的探索，必須有能夠兼顧各方面需求的算法來進行資源調(diào)配，本文將針對線路資源數(shù)據(jù)的特點，采用搜索規(guī)劃的算法解決優(yōu)化問題。這種算法能夠就對一定規(guī)模的網(wǎng)絡節(jié)點和線段進行分析，尋求具備合理性的最佳業(yè)務路線。

二、業(yè)務模型概述

當前網(wǎng)絡基本建立在劃分城區(qū)而成的網(wǎng)格上，每個規(guī)劃的網(wǎng)格中都存在相應的業(yè)務側(cè)設備，并通過中繼段連通至接入側(cè)設備。為了便于簡化模型，假定在一個較小的片區(qū)中進行傳輸業(yè)務規(guī)劃，在整個業(yè)務的流向中，數(shù)據(jù)從源端設備到宿端設備所經(jīng)過的承載載體進行遍歷，不難發(fā)現(xiàn)業(yè)務的走向是經(jīng)由“始端設備→交接設施→中繼段→交接設施→…→交接設施→中繼段→末端設備”這種點線交替的形式。剔除首末端固定的設備，該路徑是由“點-線”間插交替的路徑模型。

針對該業(yè)務模型，可定義擬定優(yōu)化方向的判定標準：①總體和當前業(yè)務覆蓋能力，②交接設施成端的比率，③局向纖芯使用率。

為簡化模型計算的呈現(xiàn)，對運算變量統(tǒng)一標識，表述基礎數(shù)據(jù)如下：

交接設施點集（m為總節(jié)點數(shù)）：S={S1，S2，S3，…，Sm}

中繼段集（n為總線段數(shù)）：L={L1，L2，L3，…，Ln}

中繼段長度集：Len={Len1，Len2，Len3，…，Lenn}

中繼段纖芯占用率：Ф={Ф1，Ф2，Ф3，…，Фn}

中繼段纖芯數(shù)：n={n1，n2，n3，…，nn}

vik代表規(guī)劃路徑所經(jīng)交接設施，第i條可達路徑的第k個跳接點。有vik∈S。

lik代表規(guī)劃路徑經(jīng)中繼線段，第i條可達路徑的第k條線段。有l(wèi)ik∈L。

lenik代表第i條可達路徑的第k條線段的長度，有l(wèi)enik∈Len。

所有規(guī)劃出的路徑集合（Trace Route）：

TRi= （1）

如上，則第i條可達業(yè)務路徑的跳接次數(shù)為Ni，vi0=v0，viNi+1=vd。

假定某次業(yè)務優(yōu)化路徑數(shù)量為，全程功率損耗為λi dB，單位線長的損耗為λadB，跳接點的熔接損耗為λbdB，全程可供的最大損耗為λT，則可以得出每條規(guī)劃路徑的全程損耗為：

λi=∑Leni ×λa +Ni ×λb≤λT （2）

對于第i條規(guī)劃業(yè)務路徑自至的跳接次數(shù)Ni，假定有序集合TRi中的元素個數(shù)為Ri（Ri=CardiTRi），則：

Ni=（Ri-1）/2-1 （3）

在整個業(yè)務路徑規(guī)劃中，路徑損耗是業(yè)務開通的關鍵因素，路徑損耗必須在業(yè)務要求的功率范圍內(nèi)滿足，且取最小。損耗主要包括光路中的單位損耗和跳接點的接續(xù)損耗。而跳接點的數(shù)量也會在現(xiàn)場布線操作時產(chǎn)生人工消耗和業(yè)務不穩(wěn)定因素，所以確定路徑規(guī)劃的兩個基本約束條件為：a. 損耗最小，b. 跳接點最少。

由此，該模型可轉(zhuǎn)變?yōu)椋涸谟邢薜奶哟螖?shù)以內(nèi)，使得功率損耗最小的路徑，即目標函數(shù)為：

MINTRi U（Ni，λi）≤λT （4）

其中U（Ni，λi）為以目標優(yōu)先的二元目標函數(shù)集，也就是說在滿足最少跳接次數(shù)Ni的前提下使得λi可控且最優(yōu)的方案集合。

從函數(shù)的性質(zhì)上看，應該有■U/■Ni>0，■U/■λi>0。從目標優(yōu)先的次序看，有■U/■Ni>>■U/■λi。

規(guī)劃路徑的節(jié)點集：

PA={P1，P2，P3，…，PNi} （5）

規(guī)劃路徑的線路集：

QA={Q1，Q2，Q3，…，QNi+1} （6）

路徑損耗：

n'

根據(jù)上述推演，求解式（1）-（7）所形成基本約束條件。

三、算法求解思路

根據(jù)上述算法，擬定求解思路如下：

（1）根據(jù)業(yè)務點坐標確認覆蓋該業(yè)務范圍的業(yè)務設施位置，擬定為通路起點P1，確認設施P1的業(yè)務提供能力；（2）從所選擇業(yè)務點坐標確認覆蓋范圍內(nèi)是否含有末梢光交接設施，得出最近直線距離內(nèi)交接設施點坐標，擬為路徑終點PNi；（3）分別從P1、PNi點出發(fā)，對比各中繼段所能到達的交接設施，追溯由P1至PNi的可達路徑，通過比較跳接次數(shù)和全程功率損耗來確定最優(yōu)路徑；（4）從搜索算法來看，需設定多個路線集和點集，運算量會隨網(wǎng)絡規(guī)模和跳接次數(shù)的增加成級數(shù)增長，為節(jié)約算法復雜度和計算成本，需考慮限定措施。

具體算法設計如下：

A. 先將起始點作為P1，假定P1到目標點PNi存在直通通路（直通纜段），則直接得出最優(yōu)路徑；

B. 當直通纜段不存在時，匹配經(jīng)過節(jié)點P1的所有線路{QP1}和經(jīng)過節(jié)點PNi的所有線路{QPNi}，確認是否存在公共節(jié)點P2，若存在，則P1-P2-PNi為所求通路路徑；

C. 當{QP1}和{QPNi}中不存在公共節(jié)點P2時，將問題轉(zhuǎn)換為節(jié)點P2和節(jié)點PNi之間是否存在公共節(jié)點P3的問題求解，以確定P1-P2-P3-PNi的通路路徑；

D. 以此類推，考慮N次跳接的情況，逐步追溯得出結果；

E. 同步考慮功率損耗，當最短路徑已超出光功率限額范圍時，自動退出搜索并返回；

F. 當結果TRi存在多個時，通過對比各個結果的λi選擇最優(yōu)的業(yè)務規(guī)劃路徑。

不難看出，對業(yè)務優(yōu)化的模型可以轉(zhuǎn)換為對點線模型路徑規(guī)劃的算法演繹。受到路徑規(guī)劃算法復雜度的限制，算法的計算成本隨著網(wǎng)絡規(guī)模增長而加大，在本文應用的模型中，過多的跳接點會帶來額外的路徑損耗，而路徑損耗是業(yè)務規(guī)劃模型的基本約束條件，常規(guī)場景下，布線跳接次數(shù)應有限限定，因此，在算法中也可通過減少或限定計算的跳接次數(shù)（如NiMax≤5），使算法的計算成本基本可控。

四、結論

經(jīng)測試算法內(nèi)容通過輸入測試數(shù)據(jù)圓滿實現(xiàn)業(yè)務優(yōu)化?；谧詣踊惴ǖ哪M資源調(diào)配方案，可用于現(xiàn)網(wǎng)有限資源的調(diào)整，為新增業(yè)務騰出空間，同時也可推廣應用到基于現(xiàn)網(wǎng)資源基礎的工程預設計中，從方案初期就介入方案合理性，減少后期因資源優(yōu)化帶來的業(yè)務中斷影響客戶感知。

參 考 文 獻

[1] Santanu Saha Ray. Graph Theory with Algorithms and Its Applications[M]. 北京：Springer，India，PrivateLtd，2013

[2] 王海英. 圖論算法機器MATLAB實現(xiàn)[M]. 北京：北京航空航天大學出版社，2010