連紀(jì)文 卓秀者

?

電力光纖通信網(wǎng)絡(luò)優(yōu)化算法及其應(yīng)用探討

連紀(jì)文1卓秀者2

1.福建電力調(diào)度通信中心 2.福建永福通訊技術(shù)開發(fā)有限公司

依據(jù)電力系統(tǒng)通信業(yè)務(wù)特點，改進了整數(shù)線性規(guī)劃算法，用于SDH組網(wǎng)優(yōu)化設(shè)計，并開發(fā)了相應(yīng)的軟件。最后以福州市區(qū)東南部的電力光纖網(wǎng)絡(luò)為例給出了具體的優(yōu)化設(shè)計方案。

電力 SDH 優(yōu)化 ILP算法 軟件

1 引言

近幾年來，隨著電網(wǎng)快速發(fā)展，電力系統(tǒng)光纖通信網(wǎng)絡(luò)迅速壯大，已經(jīng)成為電網(wǎng)生產(chǎn)調(diào)度重要支撐手段。由于電力通信網(wǎng)一般都隨電網(wǎng)分期分批建設(shè)，網(wǎng)絡(luò)路徑及結(jié)構(gòu)等均受電網(wǎng)結(jié)構(gòu)的制約，從而影響了電力光纖通信網(wǎng)絡(luò)結(jié)構(gòu)合理性和可靠性，因此當(dāng)光纖通信網(wǎng)絡(luò)達(dá)到一定的規(guī)模之后，有必要借助先進的網(wǎng)絡(luò)優(yōu)化算法，優(yōu)化原有的通信網(wǎng)絡(luò)，從而提高通信網(wǎng)絡(luò)整體性能水平，滿足電網(wǎng)規(guī)模不斷擴大及現(xiàn)代化管理需求。

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

2 SDH組網(wǎng)優(yōu)化算法

2.1 狹義組網(wǎng)優(yōu)化

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

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

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

狹義組網(wǎng)優(yōu)化問題可以形式化為一個整數(shù)線性規(guī)劃問題，并采用商業(yè)的整數(shù)規(guī)劃軟件來求解。

2.2 優(yōu)化算法中的輸入?yún)?shù)和優(yōu)化變量

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

（1） N：有低速業(yè)務(wù)流要傳送的節(jié)點數(shù)目，我們將在這些節(jié)點間組建光纖通道環(huán)；

（3）M：一個非常大的整數(shù)；

輸出結(jié)果或者說要得到的目標(biāo)變量是：

從輸出變量可以看出我們的優(yōu)化要確定組成幾個環(huán)，各環(huán)的線速，以及每個環(huán)由哪些節(jié)點組成，業(yè)務(wù)在這些環(huán)上如何路由，也可以推導(dǎo)出需要在環(huán)間進行交換的業(yè)務(wù)及其路由等。由于大量的光纜已經(jīng)鋪設(shè)，網(wǎng)絡(luò)的費用主要反映在網(wǎng)絡(luò)設(shè)備上，在SDH環(huán)網(wǎng)中采用的設(shè)備主要是SDH的分插設(shè)備ADM，因此最小化ADM的成本就優(yōu)化了網(wǎng)絡(luò)的建設(shè)成本。

2.3 優(yōu)化算法的ILP公式

在組網(wǎng)優(yōu)化設(shè)計方案中，我們以最小化容納所有低速業(yè)務(wù)流所需要的ADM設(shè)備成本為目標(biāo)，利用ILP公式對組網(wǎng)優(yōu)化問題進行求解。它可以表示為：

所需滿足的約束條件為：

2.3.1業(yè)務(wù)需求約束

2.3.2業(yè)務(wù)的環(huán)約束

業(yè)務(wù)在一環(huán)離開（或者說發(fā)出），一定要在該環(huán)上到達(dá)（或者說終止），離開和到達(dá)的節(jié)點在同一環(huán)上可以不是同一節(jié)點。即使業(yè)務(wù)為環(huán)間業(yè)務(wù)，它也要先從一環(huán)到達(dá)雙環(huán)共有的節(jié)點，到達(dá)（終止）于此環(huán)的該節(jié)點，再在該節(jié)點從另一環(huán)離開（重新發(fā)出），故有此約束。

2.3.3環(huán)容量約束

它表示任意節(jié)點發(fā)出的，經(jīng)過任意節(jié)點離開的業(yè)務(wù)量之和要小于該環(huán)的業(yè)務(wù)容量。它約束了一個環(huán)上路由的業(yè)務(wù)總量不超過該環(huán)的業(yè)務(wù)容量，一個環(huán)的業(yè)務(wù)容量用該環(huán)所用ADM設(shè)備的線速來表示。

2.3.4節(jié)點約束

2.3.5環(huán)上最大節(jié)點約束

2.3.6環(huán)上已知節(jié)點約束

2.3.7ADM成本約束

組網(wǎng)優(yōu)化結(jié)果中ADM成本的總和，它等于形成的多環(huán)網(wǎng)中所有ADM成本的總和。

2.3.8整數(shù)約束

通過業(yè)務(wù)疏導(dǎo)，能依據(jù)給定的業(yè)務(wù)矩陣，獲得最小的ADM成本，疏導(dǎo)的結(jié)果同時給出對應(yīng)的邏輯拓?fù)浜蜆I(yè)務(wù)在邏輯拓?fù)渖系穆酚山Y(jié)果。獲得的最優(yōu)化性能值是性能的上限（對ADM成本而言該值為下界），它可以用于衡量現(xiàn)有網(wǎng)絡(luò)性能與最優(yōu)網(wǎng)絡(luò)性能之間的差異。依據(jù)最優(yōu)邏輯拓?fù)?，可以調(diào)整以獲得想要的邏輯拓?fù)洹?/p>

3 組網(wǎng)優(yōu)化軟件實現(xiàn)及數(shù)值結(jié)果

3.1 組網(wǎng)優(yōu)化的軟件實現(xiàn)

3.1.1參數(shù)錄入

(1)錄入需要組網(wǎng)的節(jié)點

錄入的16個節(jié)點如表1所示。

表1 組網(wǎng)節(jié)點表

(2)錄入需要路由的業(yè)務(wù)

錄入需要進行組網(wǎng)優(yōu)化的低速業(yè)務(wù)矩陣，組網(wǎng)優(yōu)化根據(jù)各節(jié)點間業(yè)務(wù)量的多少來進行組網(wǎng)設(shè)計。

(3)線速及成本設(shè)置

圖1 環(huán)線速、成本及最大節(jié)點數(shù)錄入

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

(4)環(huán)上節(jié)點指定

指定某個環(huán)一定要經(jīng)過某個節(jié)點，以適應(yīng)實際情況的需要。如指定了環(huán)1要包含節(jié)點“東臺”和“江田”，環(huán)2也要包含節(jié)點“東臺”和“江田”，而環(huán)3一定要包含節(jié)點“地調(diào)”。

3.1.2組網(wǎng)優(yōu)化求解

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

圖2 組網(wǎng)優(yōu)化求解

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

3.2 組網(wǎng)優(yōu)化的數(shù)值結(jié)果

把輸入?yún)?shù)錄入后，通過對ILP算法的求解，可以獲得相應(yīng)的數(shù)值結(jié)果。

3.2.1組建的環(huán)數(shù)

表2 值

3.2.2環(huán)包含節(jié)點

表3 環(huán)包含節(jié)點

圖3 優(yōu)化后SDH網(wǎng)絡(luò)拓?fù)鋱D

4 結(jié)論

本文依據(jù)福建電力光纖通信網(wǎng)絡(luò)的實際情況，針對基于1+1保護的SDH/SONET環(huán)形網(wǎng)進行了組網(wǎng)優(yōu)化設(shè)計。其內(nèi)容為在給定節(jié)點對間要傳輸?shù)牡退贅I(yè)務(wù)流的情況下，設(shè)計一個多環(huán)SDH網(wǎng)絡(luò)來傳輸這些業(yè)務(wù)流，使得所花費的ADM設(shè)備成本最小。為此建立了組網(wǎng)優(yōu)化模型，提出了組網(wǎng)優(yōu)化設(shè)計算法，并針對福州市區(qū)東南部的電力光纖網(wǎng)絡(luò)給出了組網(wǎng)優(yōu)化設(shè)計的數(shù)值結(jié)果，為其提出了優(yōu)化方案，為組網(wǎng)設(shè)計提供了很好的參考。

[1] 王毅,趙彥靈,向軍.SDH環(huán)狀傳輸網(wǎng)絡(luò)中的業(yè)務(wù)疏導(dǎo)策略研究[J].通信與信息技術(shù),2005,(8):36-42.

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

[3] 業(yè)務(wù)疏導(dǎo)在傳輸網(wǎng)絡(luò)評估中的應(yīng)用研究.通信世界網(wǎng),2007.

[4] 王慶鑄,連紀(jì)文等.電力系統(tǒng)光纖通信網(wǎng)絡(luò)優(yōu)化模型建立與應(yīng)用,2008.