基于路徑搜索算法的通信業務優化研究

陳郁喬

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

【關鍵詞】 路徑搜索 通信資源 業務優化

一、引言

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

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

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

二、業務模型概述

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

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

為簡化模型計算的呈現，對運算變量統一標識，表述基礎數據如下：

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

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

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

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

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

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

lik代表規劃路徑經中繼線段，第i條可達路徑的第k條線段。有lik∈L。

lenik代表第i條可達路徑的第k條線段的長度，有lenik∈Len。

所有規劃出的路徑集合（Trace Route）：

TRi= （1）

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

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

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

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

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

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

由此，該模型可轉變為：在有限的跳接次數以內，使得功率損耗最小的路徑，即目標函數為：

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

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

從函數的性質上看，應該有■U/■Ni>0，■U/■λi>0。從目標優先的次序看，有■U/■Ni>>■U/■λi。

規劃路徑的節點集：

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

規劃路徑的線路集：

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

路徑損耗：

n'

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

三、算法求解思路

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

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

具體算法設計如下：

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

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

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

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

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

F. 當結果TRi存在多個時，通過對比各個結果的λi選擇最優的業務規劃路徑。

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

四、結論

經測試算法內容通過輸入測試數據圓滿實現業務優化。基于自動化算法的模擬資源調配方案，可用于現網有限資源的調整，為新增業務騰出空間，同時也可推廣應用到基于現網資源基礎的工程預設計中，從方案初期就介入方案合理性，減少后期因資源優化帶來的業務中斷影響客戶感知。

參 考 文 獻

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

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