電力光纖通信網絡優化算法及其應用探討

連紀文 卓秀者

?

電力光纖通信網絡優化算法及其應用探討

連紀文1卓秀者2

1.福建電力調度通信中心 2.福建永福通訊技術開發有限公司

依據電力系統通信業務特點，改進了整數線性規劃算法，用于SDH組網優化設計，并開發了相應的軟件。最后以福州市區東南部的電力光纖網絡為例給出了具體的優化設計方案。

電力 SDH 優化 ILP算法 軟件

1 引言

近幾年來，隨著電網快速發展，電力系統光纖通信網絡迅速壯大，已經成為電網生產調度重要支撐手段。由于電力通信網一般都隨電網分期分批建設，網絡路徑及結構等均受電網結構的制約，從而影響了電力光纖通信網絡結構合理性和可靠性，因此當光纖通信網絡達到一定的規模之后，有必要借助先進的網絡優化算法，優化原有的通信網絡，從而提高通信網絡整體性能水平，滿足電網規模不斷擴大及現代化管理需求。

本文依據福建電力光纖通信網絡的實際情況，將對基于1+1保護的SDH/SONET環形網進行組網優化。它在給定業務需求的情況下，優化容納所有業務所需要的總成本或者說最小化總成本。具體來說，我們將研究SDH環網上的多線速優化問題,即在一個光纜網絡中如何組成多個SDH環，以及低速業務流在環上如何路由的問題。

2 SDH組網優化算法

2.1 狹義組網優化

在電力通信網中，存在大型節點（如地調）間對帶寬有著很大的需求。例如，可能要求一條甚至多條 STM-16的線路。但是，還有大量節點之間（相鄰節點、集控所和下屬站點，地調和其余節點）的網絡連接請求只需要一個光纖通道提供的STM-16帶寬的一小部分，例如STM-1、10Mbps等，因此光傳送網必須能夠有效地滿足這一類節點的業務需求。解決容量巨大的光纖通道和帶寬要求不大而數目眾多的節點帶寬需求之間矛盾的關鍵，就是有效地安排節點數據流共享高速的光纖通道。

本文將此問題稱為組網優化問題，它是從學術界的業務疏導問題引申而來，或者說其學術術語為業務疏導。借鑒業務疏導的定義，可以將我們要研究的組網優化定義為：將節點之間的低速數據流有效地復用到高速的光纖通道，將高速的光纖通道數據流解復用成為低速數據流，并且使得低速數據流在不同高速光纖通道上進行合理的交換。上述組網優化的定義我們稱之為狹義意義上的組網優化。

狹義組網優化，它包含兩個子問題：一個是確定邏輯拓撲，另一個是在該邏輯拓撲上路由低速業務流。第一個子問題中，要確定組建多少個光纖通道環，每個光纖通道環的線速以及經過哪些節點。如果在一些節點間有足夠的業務容量需要傳送，那么應該由這些節點組成一個高線速的環，使這些業務在該環上傳送，以獲得高線速環運送單位業務時的經濟性。另一方面，如果一些節點間的業務量較小，那么它們應該在一個線速較低的環上傳送，以減少ADM的成本。為給定低速業務流的網絡設計一個支持多線速的多環邏輯拓撲是一個困難的工作。一般來說，在整個網絡中始終采用單線速的光纖通道環，能大大減少設計的復雜性，但它會帶來成本上的不經濟性。我們可以不預先確定每一個環的線速，由優化算法來確定。但為了簡化計算復雜度和節省優化時間，這里由網絡設計或運營者依據業務容量的需求來估計這些環網的線速大致在什么范圍，如需要預估這些環的線速在OC-12還是OC-48的量級，然后再由優化設計程序來確定能否找到優化解，即能否在指定的幾個環中路由這些業務，并最小化ADM設備的成本。同時確定要組成幾個環，每個環的線速，每個環要經過哪些節點，業務在這些環上如何路由，哪些業務需要在環間交換等。

狹義組網優化問題可以形式化為一個整數線性規劃問題，并采用商業的整數規劃軟件來求解。

2.2 優化算法中的輸入參數和優化變量

對低速業務流進行組網優化這個問題可以簡單歸納如下所述。首先，我們給出組網優化問題的輸入條件：

（1） N：有低速業務流要傳送的節點數目，我們將在這些節點間組建光纖通道環；

（3）M：一個非常大的整數；

輸出結果或者說要得到的目標變量是：

從輸出變量可以看出我們的優化要確定組成幾個環，各環的線速，以及每個環由哪些節點組成，業務在這些環上如何路由，也可以推導出需要在環間進行交換的業務及其路由等。由于大量的光纜已經鋪設，網絡的費用主要反映在網絡設備上，在SDH環網中采用的設備主要是SDH的分插設備ADM，因此最小化ADM的成本就優化了網絡的建設成本。

2.3 優化算法的ILP公式

在組網優化設計方案中，我們以最小化容納所有低速業務流所需要的ADM設備成本為目標，利用ILP公式對組網優化問題進行求解。它可以表示為：

所需滿足的約束條件為：

2.3.1業務需求約束

2.3.2業務的環約束

業務在一環離開（或者說發出），一定要在該環上到達（或者說終止），離開和到達的節點在同一環上可以不是同一節點。即使業務為環間業務，它也要先從一環到達雙環共有的節點，到達（終止）于此環的該節點，再在該節點從另一環離開（重新發出），故有此約束。

2.3.3環容量約束

它表示任意節點發出的，經過任意節點離開的業務量之和要小于該環的業務容量。它約束了一個環上路由的業務總量不超過該環的業務容量，一個環的業務容量用該環所用ADM設備的線速來表示。

2.3.4節點約束

2.3.5環上最大節點約束

2.3.6環上已知節點約束

2.3.7ADM成本約束

組網優化結果中ADM成本的總和，它等于形成的多環網中所有ADM成本的總和。

2.3.8整數約束

通過業務疏導，能依據給定的業務矩陣，獲得最小的ADM成本，疏導的結果同時給出對應的邏輯拓撲和業務在邏輯拓撲上的路由結果。獲得的最優化性能值是性能的上限（對ADM成本而言該值為下界），它可以用于衡量現有網絡性能與最優網絡性能之間的差異。依據最優邏輯拓撲，可以調整以獲得想要的邏輯拓撲。

3 組網優化軟件實現及數值結果

3.1 組網優化的軟件實現

3.1.1參數錄入

(1)錄入需要組網的節點

錄入的16個節點如表1所示。

表1 組網節點表

(2)錄入需要路由的業務

錄入需要進行組網優化的低速業務矩陣，組網優化根據各節點間業務量的多少來進行組網設計。

(3)線速及成本設置

圖1 環線速、成本及最大節點數錄入

根據電力系統業務特點，環1~5的線速分別設為622Mbps、622Mbps、2500Mbps、0Mbps、0 Mbps，即后兩個環用戶可以指定不用，前三個環分別為OC-12環、OC-12環和OC-48環。假定OC-12環所用ADM的成本為3，OC-48的成本為9，這是基于高線速環所用ADM的成本高于低線速環，但其傳送單位業務的成本應低于低線速環。同時指定了同一環上允許的最大節點個數為8，以滿足福建電力系統繼電保護通道轉接次數要求。

(4)環上節點指定

指定某個環一定要經過某個節點，以適應實際情況的需要。如指定了環1要包含節點“東臺”和“江田”，環2也要包含節點“東臺”和“江田”，而環3一定要包含節點“地調”。

3.1.2組網優化求解

優化軟件將對整數線性規劃算法進行求解，并把最近的求解結果顯示在狀態窗口中，包括到目前為止的迭代次數，找到的解值（ADM的最小成本），和邊界值（下邊界，解值不可能小于這個值）。一旦求解結束或者用戶中斷求解過程，優化狀態將被顯示在狀態窗口中。它反映了到目前為止求解的狀態，如找到了“全局最優解”，“可行解”，“局部最優解”，還是“無可行解”，“求解過程失敗”等，見圖2。

圖2 組網優化求解

圖2中顯示找到了“全局最優解”，總共迭代了572258次，解值為105（即組建這些SDH環網的總成本），邊界值也為105。解值等于邊界值，也反映了最優解的獲得。

3.2 組網優化的數值結果

把輸入參數錄入后，通過對ILP算法的求解，可以獲得相應的數值結果。

3.2.1組建的環數

表2 值

3.2.2環包含節點

表3 環包含節點

圖3 優化后SDH網絡拓撲圖

4 結論

本文依據福建電力光纖通信網絡的實際情況，針對基于1+1保護的SDH/SONET環形網進行了組網優化設計。其內容為在給定節點對間要傳輸的低速業務流的情況下，設計一個多環SDH網絡來傳輸這些業務流，使得所花費的ADM設備成本最小。為此建立了組網優化模型，提出了組網優化設計算法，并針對福州市區東南部的電力光纖網絡給出了組網優化設計的數值結果，為其提出了優化方案，為組網設計提供了很好的參考。

[1] 王毅,趙彥靈,向軍.SDH環狀傳輸網絡中的業務疏導策略研究[J].通信與信息技術,2005,(8):36-42.

[2] 張程,鮑振武,曹俊忠.WDM網絡光層保護整數線性規劃算法的探討[J].光纖與電纜及其應用技術,2003,(6):17-20.

[3] 業務疏導在傳輸網絡評估中的應用研究.通信世界網,2007.

[4] 王慶鑄,連紀文等.電力系統光纖通信網絡優化模型建立與應用,2008.