電力通信傳輸網絡的優化模型探討

王榮（1985-），女，遼寧海城人，碩士研究生，主要研究方向：計算機在通信網中的應用，

摘要：本文介紹網絡優化的數學模型和幾種算法，闡述了圖論的基本概念，介紹最小生成樹的Kruskal算法、最短路徑算法和最大流量算法，根據廣州電力通信網的結構，論述了優化的必要性，優化的目標。對于電力通信傳輸網，提出了受限最短路徑優先（CSPF）算法的具體步驟， 并詳細提出了用于CSPF計算的約束條件：鏈路約束和路徑約束。采用本算法對廣州電力通信網絡的骨干網絡進行計算機模擬，取得了有實際意義的結果。

關鍵詞：網絡優化，最小生成樹，最短路徑算法，最大流量算法，CSPF算法，

中圖分類號：TN72 文獻標識碼：A 文章編號：1672-3791（2015）01（a）-0000-00

0 引言

電力通信傳輸網分為A網和B網，覆蓋所有110kV及以上變電站和基層單位大樓，業務包括調度自動化（EMS/SCADA）、安穩信息、繼電保護等生產實時信息和生產管理信息。在生產運行中出現以下問題：（1）隨著電力專業集約化管理的實施，城區和二區二市網融合成一張網，業務流向由分布集中到全部集中到地調。如何對網絡保護方式和結構進行優化，提高網絡的安全可靠性。（2）在網絡結構上，由于各種因數，導致傳輸網網絡建設不均衡，網絡流量不足。資源利用率低，網絡的分層、分類不清。（3）在網絡業務上，通道使用缺少整體規劃，沒有詳細規劃，致使電路調配日益復雜，局端上下電路難度增加，交叉矩陣浪費嚴重且使用不均衡，電路運行的清晰度低，查找業務、調整業務困難，定位時間長。

對此，需要進行傳輸網絡優化，使網絡結構更清晰、支持業務更豐富、運營維護更方便、電路生產更高效、擴容升級更平滑。由于當前傳輸網絡的優化大多停留在人工預測、簡單計算和布點上，造成工作量大，預測不準確、科學。

1 數學模型

1.1定義

1.1.1網絡：用G表示一個網絡，則這個網絡由一組節點V={v1，v2， … ，Vn}和這組節點（兩個節點的聯結組）組成的邊E={eij}構成，表示為G=（V，E）。

1.1.2權重：在一個網絡圖中，邊上表示連接強度的權值，稱為權重，表示為wij。

1.1.3樹：網絡圖G=（V，E）中，如相鄰的兩個端點間都有一條路相連，但是又不存在任何回路即任兩點間有且只有一條路徑，這樣的圖稱為樹T。

1.1.4生成樹：對于網絡圖G，如樹T是G的子圖且包含圖G的所有的節點，則稱T是圖G的生成樹（Spanning Tree）. 根據G的不同，生成樹可以有多有少。

1.1.5最小生成樹：對于一個給定的網絡圖G中，其生成樹中有一個總容量最小的。

1.2 算法

求生成樹，可以有兩種思路：一種是從一個邊開始，通過搜索比較，尋找下一個邊。稱為選邊法，一種在全圖中，逐漸減去成環的邊，稱為破圈法。

1.2.1求最小生成樹，有Kruskal算法，Prim算法。Kruskal算法如下

給定網絡圖G=（V，E），每條邊e的權w（e）≥0.將G的邊按權的大小排序為e1，e2， …em，使W（e1）≤w（e2） ≤ …≤w（em）.

1.2.2 最短路徑算法

從起始點到其它各點的最短路徑，可以利用最小生成樹法求得。具體有以下算法Dijkstras算法。

如果節點vs到vt的最短路徑總是沿著某一特定的路徑先到達節點 vi，然后再沿邊到達節點vj，則這一特定路徑肯定也是節點vs到節點vi的最短路徑。

1.2.3 最大流量算法

在有向網絡圖中，每個邊上實際通過的信息量或物理量，我們定義為流量，定義為：fij。

以上兩條表明：某一邊上的實際流量不能超過該邊的容量。對于任意中間節點，流入該節點的流量之和等于流出該節點的流量之和。

2 優化模型

實際的通信網絡具有相當多的約束條件，除了考慮網絡的容量外，如要考慮網絡建設費用，節點間光路由的長短，節點的跳數和高低階業務的不同。

并結合IP路由算法如OSPF算法，考慮SDH環網保護（SNCP和MS-SPRING等）。所有這些都是在多種約束條件下的網絡優化。

2.1網絡分層

對于實際網絡，網絡組成包括管道層、物理層（光纜、纖芯）、DWDM、SDH層。通過每層間的對應關系，建立層間映射模型。

2.2 SDH分層

對于SDH層，有核心層、匯聚層和接入層。有2種模型，一種是對每一層作為一個獨立網絡圖進行計算，這種不能對全網起到有效的優化。另一種對不同層的節點賦予不同的權重，并反映到節點和邊的計算中。在子網內部采用MS-SPRING，MSP，SNCP等選路。

2.3高低階屬性

對于一條E1電路，在途經每個節點時，是否下低階關系到網絡業務的調配、定位等關系，必須對本節點賦予不同的屬性。

2.4受限最短路徑優先（CSPF）算法

在通信網絡中，使用Dijkstra和Bellman-Ford算法計算最短路徑是很有效的，但如果要求將約束條件引入優化問題時，算法會變的十分復雜。約束最短路徑優先（Constrained SPF）算法屬于啟發式算法，它是一種改進的最短路徑約束算法，在網絡中主要用來完成流量工程和快速的重路由。

2.5 用于CSPF計算的約束條件

通常約束條件分為兩類：鏈路約束和路徑約束。

2.5.1 鏈路約束

鏈路約束是指一條路徑上鏈路的使用限制，即光鏈路的屬性特征。

2.5.2 路徑約束

路徑約束是指在選定路徑上性能度量標準值的加性或乘性組合的界限。

4、小結

網絡優化設計時遇到的一個難點是大量網絡數據的收集、處理。由于數據量大，人工處理比較難，采用軟件處理也存在網管數據格式和優化軟件格式的轉化問題。

通過以上分析，數學模型和優化軟件是非常有用的，可以大大提高網絡優化的科學性，減輕工作量。但是，實際網絡環境是非常復雜的，優化工具不能完全代替人去思考和設計，因此在利用這些工具時，關鍵要了解原理和設計、優化思想。同時，數據輸入時要力求準確，否則，結果不但沒有參考價值，反而會誤導。本文首次應用約束最短路徑優先（Constrained SPF）算法在電力通信網絡優化上，并對本功能進行了仿真測試，實際結果表明，優化模型及算法在通信網絡規劃和建設中起著科學設計、輔助決策的良好作用。

參考文獻：

[1]雷功炎. 數學模型講義[M]. 北京：北京大學出版社，1999.

[2]高隨祥. 圖論與網絡流理論[M]. 北京：高等教育出版社，2009.

[3]劉桂真. 圖與網絡——優化決策的圖論方法. 上海：上?？茖W技術出版社，2006.

[4]梁雄健，孫青華，張靜，楊旭. 通信網規劃理論和務實[M]. 北京：通信網規劃理論與務實，2006