電力通信網SDH環容量均衡優化算法研究

劉貴榮，周 靜，趙子巖，張睿汭

（中國電力科學研究院 北京 100192）

1 引言

電力系統通信網是一種專業的通信網，是由發電廠及變電所等各級電力部門相互連接的傳輸系統和設在這些部門的交換系統或終端設備構成，是電網的重要組成部分，由電網的結構、運行管理模式、經濟性等因素決定。

電力通信網在出現局部損傷的情況下，要求網絡的工作部分仍能保持較好的連通性。環形網由于其結構簡單，與點對點的拓撲結構相比，其業務恢復能力強，而與網狀網相比，其業務恢復算法簡單，可以使得網絡在極短的時間內恢復業務，因而環形網在SDH系統中得到了廣泛的應用。目前，電力通信網絡拓撲基本結構為SDH環網結構。環形拓撲實際上是指將鏈形拓撲首尾相連，從而構成網上任何一個網元節點都不對外開放的網絡拓撲形式，這是當前使用最多的網絡拓撲形式，主要是因為它具有很強的生存性，即可靠性高，網絡恢復時間短，具有良好的業務疏導能力。

2 電力光傳輸網特點與現狀

2.1 電力光傳輸網特點

電力光傳輸網的構成主要以SDH環網電路與鏈狀電路為主。光傳輸網絡架構主要依托輸電線路的走向。光傳輸網架依托于底層光纜路由形成后，面對以星狀匯聚業務為主的業務結構，將產生眾多的跨環穿透業務。過多的跨環穿透業務容易引發帶寬瓶頸和節點瓶頸，同時增加了網絡運行與維護管理的難度。

光傳輸網基本采用SDH體制，為了能夠最大限度地提高網絡結構的可靠性，在網絡設計和工程應用中不可避免地盡可能多地采用環形拓撲。當SDH環網數量較多時，光傳輸網絡拓撲結構域所承載業務網絡結構間的矛盾將越發明顯，環型拓撲的缺陷將對中心接入節點的安全性以及光傳輸網絡的維護性能產生巨大的壓力。

2.2 所承載的業務特點

現階段電力光傳輸網所承載的業務信息，其流向和流量具有電力企業固有的特點。

管理部門之間的業務信息以縱向為主 （縣>地>省>網），少有平行部門間（縣與縣、地與地、省與省、網與網）的橫向業務，業務流向具有明顯的星狀匯聚網絡的結構特點。在現階段，以SDH環網為主的光傳輸網中表現為環上多點向中心匯聚型的業務，環網中越接近中心點的區段業務流量越大，缺少運營商SDH環網中相鄰站點之間上下分散型業務。

電網管理部分與變電站、電廠之間的業務信息也是以縱向業務為主，具有星狀匯聚網絡結構特點，但是業務量比較小。

廠站業務主要是針對點對點的保護業務，是電力光傳輸網上承載的特殊業務。該業務建在廠站之間，不涉及管理部門，其占用帶寬較小，但是對通道的可靠性要求極高，對傳輸時延的要求也很嚴格。

3 環網業務模型

3.1 自愈網（環）技術

所謂自愈網(self-healing network)，就是具有網絡業務保護功能的傳輸網絡。不需網絡管理系統和人為的干預，網絡能在極短的時間內(ITU-T規定在50 ms以內)從失效故障中自動恢復業務傳輸能力。替代路由可以采用備用設備或是利用現有設備中的冗余能力，以滿足端到端的業務恢復，或指定優先級業務不受影響。在自愈過程中，各種業務不會中斷，用戶感覺不到網絡已經出現故障并發生了重組。

SDH自愈環是典型的利用備用線路的網絡結構,具有如下優點：配置簡單；具有自愈能力，網絡的生存性強；網絡的保護時間比較短(一般小于50 ms)；具有良好的業務疏導能力。

自愈環是利用多路由的網絡拓撲方式，不僅提高了網絡的生存能力，還降低了倒換所需備用路由的成本，在網絡規劃中起到重要的作用。目前，SDH傳輸技術已成為電力通信網絡中應用的主要技術手段，SDH傳輸網絡已經成為電力系統各類信息應用的基礎平臺，是行政調度電話、繼電保護、遠動信號、MIS信息等各類電力生產信息最主要的傳輸網絡。

3.2 業務模型

目前，SDH傳輸技術已成為網絡應用的主要技術手段，而SDH環網技術又是在網絡中大量應用的網絡保護手段，對于電力通信網來說，發生的業務多屬于匯聚型業務，即數據多由下級接入站點向上級匯聚站點，核心站點流入，如果某個跨距段上的業務特別多，而其他跨距段上的業務相對少，則在很大程度上影響了網絡的流量均衡以及可能對電力安全業務造成隱患。業務均衡建立在現有網絡結構之上，它提供了一種廉價、有效、透明的方法擴展網絡設備和服務器的帶寬、增加吞吐量、加強網絡數據處理能力、提高網絡的靈活性和可用性。典型的環網業務量分布類型，如圖1所示，共3種類型。

均勻型（即分布型）分布：此時各個節點之間的業務量分布比較均勻，電力通信網的一、二級網絡的業務量分布往往趨近這類分布。

相鄰型（循環型）分布：此時業務量分布主要集中在相鄰節點之間，某些中繼網的匯接局之間的業務量分布可能趨近這類分布。

匯聚型（即樞紐型）分布：此時業務量分布主要集中于一個特殊節點（如匯接局或端局）。接入網的業務量分布通常如此，另外某些省內干線業務量也往往集中在省會市落地，采用匯接制的中繼網的業務量也往往集中于幾個匯接局。

實際業務量是上述分布類型的混合形式，以其中一種為主，而且其分布隨時間、網絡的變化以及其他因素而異，但作為分析參考則仍有相當的典型性。

不同的業務量分配方案，不同的路由算法，對應著環中不同的業務容量。研究自愈環內的路由算法，尋找合理的業務量分配方案，以減小對環路的容量要求，對SDH自愈環的設計有著重要的實際意義。本算法的目的是使環上各跨距段分配的電路總數盡可能平衡，從而使最終環容量的需求盡可能的小。摒除瓶頸跨距段，優化環網容量，提高業務均衡度以及網絡利用率。跨距段上最大業務數記為CMax。

4 業務均衡算法介紹

選擇合適的路由算法可以減少對環路的容量要求，用盡量少的配置滿足通信的需要。以下為幾種路由算法及其實現的步驟介紹。

4.1 最少轉接法

這是環路的幾種基本算法之一，其選擇業務路由的原則是該業務經過中間節點轉接的次數最少，進入環中的所有業務都通過這一方法來確定其所經過路由的環路方向，這在一定程度上能減小對整個環的容量要求。這種算法速度快，且易于實現，但效率不高。以下用B2算法代之。

4.2 按需順序算法

按需順序法的主要思想為，先分配相鄰節點間的業務，然后把不相鄰節點間的業務從大到小排序，依次分配。比較此節點對間正反方向（最少跳數為正方向）業務數，將業務分配到業務數較少的方向上。算法流程如圖2所示。以下用B4算法代之。

按需順序法算法圖例見表1和圖3所示。

4.3 最優化算法

表1 原始業務分布量

首先，T(i,j)為各選定最短路由，并記錄為P(i,j)={i,a,…,b,j},其中a,b為途徑跨距段編號，令C=max Sk=Sm，將經由m段的各路由收集到S集合，將與S中路由交叉但不屬于S集合的路由收集到與S元素分別對應的Q集合。其次，從集合S中一一取出元素，安排至反方向，計算臨時Cmax，對應的Q集合元素也一一取出，安排至反方向，也得到Cmax，最后比較這些Cmax并與之前的C進行比較，得到最小值，并記錄此最小值的業務分配狀態。最后，如果新得到的Cmax小于C則回到（2）繼續執行。否則程序結束。算法流程圖如圖4所示。以下用B5算法代之。

算法示例：以B4算法提到的例子為例。優化算法業務分配結果如圖5所示。

5 仿真分析

為了對算法的性能進行驗證，我們用C++語言實現了所有算法，針對不同業務模型（均勻型業務，匯聚型業務），對不同節點數的環分別產生了100個隨機業務矩陣，如對于均勻型業務，5個節點環，產生100個業務矩陣，6個節點環，也產生100個業務矩陣，一直到16個節點（受SDH幀結構中段開銷字節K1、K2最大尋址能力的限制，在一個需要使用自動保護倒換算法的環中最多允許存在16個節點），對于匯聚型業務也一樣。最后求100次運算的均值，圖6和圖7是最后得到的仿真結果。

對于有N（5≤N≤16）個節點的環網，隨機產生100個均勻業務矩陣，在最優化算法（以下代稱B5算法），按需順序法 （以下代稱B4算法），最短路徑法 （以下代稱B2算法）算法下都可以得到100個CMax值，取其平均值，則可知這幾種算法性能的趨勢。由圖6和圖7可知，對于均勻型業務，隨著節點數的增加，B5算法是效果最好的，B4算法效果反而越差。對于匯聚型業務，B5算法最好，B4算法次之，B2算法最差。

由圖8可知，不管是均勻型業務，還是匯聚型業務，B5算法是最有效的算法，可以很好地減少跨距段上的最大業務數。隨著環網節點數的增加，B5算法的效果越明顯。對于均勻型業務，只有5個節點時，B5算法失效次數較多，對于匯聚型業務，低于7個節點時，B5算法失效次數偏高。這里的失效是指B5的算法所得結果不比B2算法所得結果更好。

對于均勻型業務，B4算法表現出極大的不穩定性。隨著節點數的增加，B4算法失效越多 （失效是指比B2算法得到的結果還差），且有全部失效的趨勢。對于匯聚型業務，B4算法失效次數有很大減少，環網節點多于7個時，基本趨于穩定，且有減少的趨勢，總體效果比B2算法強，比B5算法差。

在實驗中，最優化方法得到的結果相比較最短路徑法無疑是最好的，因為最優化方法得到的數據只能小于等于最短路徑方法的結果。只不過，最優化方法時間復雜度與空間復雜度都比最短路徑的大，并且實現相對復雜。

B2算法時間復雜度為O(N3),B4算法時間復雜度O(N3),B5算法時間復雜度O(kN4)，k為找到最小Cmax值的所需循環次數1≤k≤N。

6 結束語

本文對業務均衡的各個算法進行了性能方面的比較。從業務最常用的分配方式最少轉接法開始，依次提出了按需順序法和最優化方法兩種優化算法。并且對有代表性的兩種業務模型：均勻型和匯聚型業務進行了數百次的運算，得到充分的數據。得到的結論是最優化算法在以開銷較多時間的基礎上下能相對較好地降低網絡的跨距段最大業務數，有效地增加網絡業務的均衡性。最優化算法在運算效率上有待改進。

1 劉源.電力通信網S D H網絡優化研究.電力通信系統，2008,185(33)

2 李苑，方少元.S D H自愈環網特性分析及應用.計算機工程，2006，32（13）

3 Wu T H.Fiber Network service survivability.New York,Artech House,1992