電力通信傳輸網(wǎng)絡(luò)的優(yōu)化模型探討

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

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

關(guān)鍵詞：網(wǎng)絡(luò)優(yōu)化，最小生成樹，最短路徑算法，最大流量算法，CSPF算法，

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

0 引言

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

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

1 數(shù)學模型

1.1定義

1.1.1網(wǎng)絡(luò)：用G表示一個網(wǎng)絡(luò)，則這個網(wǎng)絡(luò)由一組節(jié)點V={v1，v2， … ，Vn}和這組節(jié)點（兩個節(jié)點的聯(lián)結(jié)組）組成的邊E={eij}構(gòu)成，表示為G=（V，E）。

1.1.2權(quán)重：在一個網(wǎng)絡(luò)圖中，邊上表示連接強度的權(quán)值，稱為權(quán)重，表示為wij。

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

1.1.4生成樹：對于網(wǎng)絡(luò)圖G，如樹T是G的子圖且包含圖G的所有的節(jié)點，則稱T是圖G的生成樹（Spanning Tree）. 根據(jù)G的不同，生成樹可以有多有少。

1.1.5最小生成樹：對于一個給定的網(wǎng)絡(luò)圖G中，其生成樹中有一個總?cè)萘孔钚〉摹?/p>

1.2 算法

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

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

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

1.2.2 最短路徑算法

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

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

1.2.3 最大流量算法

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

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

2 優(yōu)化模型

實際的通信網(wǎng)絡(luò)具有相當多的約束條件，除了考慮網(wǎng)絡(luò)的容量外，如要考慮網(wǎng)絡(luò)建設(shè)費用，節(jié)點間光路由的長短，節(jié)點的跳數(shù)和高低階業(yè)務(wù)的不同。

并結(jié)合IP路由算法如OSPF算法，考慮SDH環(huán)網(wǎng)保護（SNCP和MS-SPRING等）。所有這些都是在多種約束條件下的網(wǎng)絡(luò)優(yōu)化。

2.1網(wǎng)絡(luò)分層

對于實際網(wǎng)絡(luò)，網(wǎng)絡(luò)組成包括管道層、物理層（光纜、纖芯）、DWDM、SDH層。通過每層間的對應(yīng)關(guān)系，建立層間映射模型。

2.2 SDH分層

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

2.3高低階屬性

對于一條E1電路，在途經(jīng)每個節(jié)點時，是否下低階關(guān)系到網(wǎng)絡(luò)業(yè)務(wù)的調(diào)配、定位等關(guān)系，必須對本節(jié)點賦予不同的屬性。

2.4受限最短路徑優(yōu)先（CSPF）算法

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

2.5 用于CSPF計算的約束條件

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

2.5.1 鏈路約束

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

2.5.2 路徑約束

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

4、小結(jié)

網(wǎng)絡(luò)優(yōu)化設(shè)計時遇到的一個難點是大量網(wǎng)絡(luò)數(shù)據(jù)的收集、處理。由于數(shù)據(jù)量大，人工處理比較難，采用軟件處理也存在網(wǎng)管數(shù)據(jù)格式和優(yōu)化軟件格式的轉(zhuǎn)化問題。

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

參考文獻：

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

[2]高隨祥. 圖論與網(wǎng)絡(luò)流理論[M]. 北京：高等教育出版社，2009.

[3]劉桂真. 圖與網(wǎng)絡(luò)——優(yōu)化決策的圖論方法. 上海：上海科學技術(shù)出版社，2006.

[4]梁雄健，孫青華，張靜，楊旭. 通信網(wǎng)規(guī)劃理論和務(wù)實[M]. 北京：通信網(wǎng)規(guī)劃理論與務(wù)實，2006