宋世聰，尼俊紅，趙振東

（華北電力大學 電子與通信工程系，河北 保定 071003）

大容量廣電網(wǎng)的P圈啟發(fā)式算法研究

宋世聰，尼俊紅，趙振東

（華北電力大學 電子與通信工程系，河北 保定 071003）

結(jié)合廣電網(wǎng)大容量的發(fā)展要求，考慮較為復雜的網(wǎng)狀網(wǎng)結(jié)構(gòu)，網(wǎng)絡生存性問題日益凸顯。對經(jīng)典的預置圈（P圈）容量算法進行了改進，并選用COST239網(wǎng)絡拓撲對改進算法進行編程仿真。結(jié)果證明，改進算法在減少預置圈數(shù)量的同時能夠提高資源利用率，性能有所提高，可以較好地解決廣電網(wǎng)的生存性問題。

廣電網(wǎng)絡；OTN；網(wǎng)絡生存性；P圈

1 廣電網(wǎng)的發(fā)展趨勢——OTN

隨著三網(wǎng)融合工作的不斷推進，廣電網(wǎng)絡用戶對IPTV、視頻點播等互動式業(yè)務需求迅速增長，高清電視、3D電視業(yè)務正在不斷開展，業(yè)務的增長使得網(wǎng)絡帶寬的需求迅速增長，建設高可靠、高速率、高效率、靈活方便部署、易維護的骨干傳輸網(wǎng)已成為廣電網(wǎng)絡業(yè)務發(fā)展迫在眉睫的需求[1]。光傳送網(wǎng)（Optical Trans?port Network，OTN）正是為適應這一需求而發(fā)展的下一代傳輸網(wǎng)技術(shù)。

廣電業(yè)務的發(fā)展經(jīng)歷了模擬電視、數(shù)字電視、互動、高清電視直至未來的多媒體全業(yè)務，目前，數(shù)字電視和數(shù)據(jù)業(yè)務占用現(xiàn)有SDH傳輸容量的絕大部分，下一步的互動、高清電視和多媒體數(shù)據(jù)業(yè)務等對傳輸帶寬的需求量會迅速膨脹。OTN作為目前骨干傳送網(wǎng)協(xié)調(diào)SDH網(wǎng)絡的主流技術(shù)，具備超大容量、超長距離傳送，靈活調(diào)度等，并且具備ASON網(wǎng)狀網(wǎng)組網(wǎng)保護能力[2]，繼承了SDH/MSTP的管理維護能力和傳統(tǒng)電視節(jié)目的廣播方式，可以支持迅速發(fā)展的互動高清電視業(yè)務。在三網(wǎng)融合和中國下一代廣播電視網(wǎng)（NGB）的發(fā)展中，OTN將起到中流砥柱的作用。

2 廣電網(wǎng)拓撲結(jié)構(gòu)與網(wǎng)絡生存性

OTN在為廣電網(wǎng)的大容量、大帶寬發(fā)展帶來機遇的同時，也帶來了一定的挑戰(zhàn)。大容量的傳輸網(wǎng)絡鏈路一旦發(fā)生故障，將影響業(yè)務的傳送，導致大量數(shù)據(jù)業(yè)務失效，為廣電公司帶來經(jīng)濟損失，為用戶生活帶來不便。OTN巨大的傳輸容量和超高的傳輸速率使得光網(wǎng)絡生存性問題更為突出。網(wǎng)絡生存性[3]主要包括保護和恢復技術(shù)。其中，網(wǎng)絡的拓撲結(jié)構(gòu)與網(wǎng)絡生存性息息相關(guān)。

目前，廣電網(wǎng)大部分采用環(huán)形組網(wǎng)，但是隨著三網(wǎng)融合的不斷發(fā)展，環(huán)形拓撲結(jié)構(gòu)在網(wǎng)絡升級與擴容方面存在缺陷，該結(jié)構(gòu)只能對全網(wǎng)統(tǒng)一升級，而不能針對部分鏈路升級擴容。網(wǎng)狀網(wǎng)中大量節(jié)點之間可通過直達路由互連，只需要1條鏈路就能建立2個節(jié)點的連接，避免了建立多條通道，使得網(wǎng)絡中節(jié)點之間有多種路由可選，具有靈活、易擴展的優(yōu)點，克服了環(huán)形網(wǎng)的缺點。結(jié)合兩種網(wǎng)絡結(jié)構(gòu)，未來廣電網(wǎng)可以考慮采用分級網(wǎng)絡構(gòu)造，各個骨干站點機房采用網(wǎng)狀或部分網(wǎng)狀拓撲構(gòu)建OTN網(wǎng)絡，然后圍繞骨干站點機房建立環(huán)形或部分網(wǎng)狀拓撲結(jié)構(gòu)的網(wǎng)絡。這樣可以解決環(huán)形網(wǎng)擴展性差、靈活性低、傳輸成本高等問題，優(yōu)化整體的網(wǎng)絡結(jié)構(gòu)，為未來廣電網(wǎng)的拓展與整合奠定基礎。

構(gòu)建的網(wǎng)狀網(wǎng)在較大程度上利用了網(wǎng)絡資源，具有高度的網(wǎng)絡連接性并且擴容方便，但是由于網(wǎng)絡復雜，其生存性的維護略差于線性、環(huán)形網(wǎng)絡。預置圈（P圈）保護算法的出現(xiàn)恰好可以在保證網(wǎng)絡恢復速度的同時維持網(wǎng)狀網(wǎng)較高的資源利用率，提高網(wǎng)狀網(wǎng)的網(wǎng)絡生存性[4]。P圈算法最大的優(yōu)點就是能為圈上鏈路提供一條保護通路的同時，為跨接鏈路故障提供兩條保護通路。

3 預置圈算法

3.1 預置圈的基礎知識

近年來P圈研究的主要問題是高效P圈的構(gòu)造和P圈的容量分配[5]，這也是P圈算法最主要的兩步。P圈的構(gòu)造是指在網(wǎng)絡拓撲中尋找可能的基本圈和先驗效率高的擴展圈，經(jīng)典的有枚舉算法Donald B Johnson、BFS和DFS擴展成生成樹，啟發(fā)式算法SLA，SP-Add和Grow生成法。P圈的容量分配就是已知網(wǎng)絡拓撲中未被保護的工作容量，為候選P圈配置空閑容量對其進行保護?？上攵?，空閑容量占用率越高，網(wǎng)絡故障恢復能力越強，但這會造成網(wǎng)絡成本的提高。為了合理分配網(wǎng)絡空閑容量，提出了最大保護效率模型和最少空閑容量模型。

現(xiàn)有的P圈容量分配算法根據(jù)使用的最優(yōu)化方法，可分為完全最優(yōu)化方法和啟發(fā)式方法兩類。完全最優(yōu)化方法是枚舉網(wǎng)絡中所有簡單圈作為候選P圈，然后利用整數(shù)線性規(guī)劃（ILP）得到最優(yōu)解，該方法在網(wǎng)絡節(jié)點和鏈路較少時可以使用，但是在大中型網(wǎng)絡中，由于計算量非常大、速度慢，不宜采用。啟發(fā)式方法又可以分為基于ILP的啟發(fā)式方法和完全啟發(fā)式方法兩類[5]，前者先計算出性能較好的備選圈，然后將備選圈進行最優(yōu)化組合得到最優(yōu)解，該方法仍然要用到ILP，因此計算時間較大，后者是直接利用啟發(fā)式算法構(gòu)造出性能較好的備選圈，再結(jié)合網(wǎng)絡中的已知工作容量，優(yōu)先配置實際保護能力大的備選圈，其目的是減小配置P圈的計算時間[6]。

3.2 預置圈的評價標準

對構(gòu)造的P圈進行優(yōu)劣選擇時，主要采用兩個指標：先驗效率AE（p）和保護效率Ew（p）。先驗效率體現(xiàn)了P圈在理論上最大的保護能力，定義為P圈能保護的最大工作容量與配置此圈所消耗的網(wǎng)絡空閑容量的比值，即

式中：S表示所有鏈路的集合；Ci表示每條鏈路上的代價；Xp,i表示該P圈能夠為鏈路i提供的保護通路的個數(shù)，主要用于構(gòu)造備選P圈。根據(jù)P圈算法的原理，可以確定當i是P圈的邊時，Xp,i=1；當i是跨接鏈路時，Xp,i=2；當i既不在圈上也不是跨接鏈路時，Xp,i=0。根據(jù)式（1）可知，P圈所包含的跨接鏈路越多，先驗效率就會相應提高。然而，這只是P圈潛在的保護效率。

P圈實際的保護能力由保護效率確定，保護效率是指在網(wǎng)絡拓撲中P圈可以實際保護的工作流量與配置該圈所消耗的空閑容量的比值，即

式中：Wp,i是指在該鏈路i上的工作容量中，可以被P圈保護的部分；Sp,i表示鏈路i消耗的空閑容量。

除先驗效率和保護效率之外，冗余度是網(wǎng)絡設計中一個相當重要的標準，定義為一個P圈的空閑容量（圈使用的波長數(shù)）與工作容量（圈上以及跨接鏈路上被保護的波長數(shù)）的比值[7]，它可以反映網(wǎng)絡的資源利用效率。

4 CIDA和啟發(fā)式算法的改進

4.1 CIDA

容量分配迭代算法（Capacitated Iterative Design Algorithm,CIDA）是P圈容量分配算法里最為經(jīng)典的算法，它采用構(gòu)造和容量分配相分離的思想，可以把過程大致分為兩步：首先是構(gòu)造候選P圈集合，可以采用SLA算法、SP-Add算法或GROW算法等來構(gòu)造先驗效率高的一系列基礎圈。然后在候選集合里選擇實際保護效率Ew（p）高的P圈進行容量分配。根據(jù)網(wǎng)絡拓撲的初始工作容量計算集合里每一個圈的實際保護效率Ew（p），選擇Ew（p）最大的一個P圈分配工作容量：圈上鏈路上減去一個工作容量，跨接鏈路上減去兩個工作容量。更新工作容量，剩余容量就是未保護的工作容量。重復第二步，直到為所有鏈路提供了完全的保護。

4.2 啟發(fā)式算法的改進

已知網(wǎng)絡中未被保護的工作容量分布，將網(wǎng)絡中每條鏈路的預留空閑容量初始化為0，算法具體步驟如下：

步驟1，修改鏈路權(quán)值。

找出網(wǎng)絡工作容量矩陣中的最大工作容量MAX及其對應鏈路；將網(wǎng)絡拓撲中所有鏈路的權(quán)值修改為MAX+1-workcapacity，這樣可以保證在計算最短路徑時最先選擇未保護工作容量較多的鏈路，提高構(gòu)造出來的P圈的實際保護效能。

步驟2，構(gòu)造簡單P圈。

以有最大工作容量的鏈路，即MAX對應的工作鏈路的起始節(jié)點為目標節(jié)點，刪除該鏈路；在目標節(jié)點之間用Dijkstra算法找到1條最短路徑，然后刪除該最短路徑；再在目標節(jié)點之間用Dijkstra算法尋找第2條最短路徑。2條最短鏈路構(gòu)成1個簡單P圈，MAX對應的工作鏈路即為跨接鏈路。

步驟3，對步驟2構(gòu)造的簡單P圈進行擴張。

擴張時首先選擇該圈上工作容量較大的邊，進行最短路徑的尋找，保存下來并計算實際保護效率。重復上述步驟，直到擴張之后的P圈保護效率比擴張前的小，停止運算，保存有最大保護效率的P圈。這樣是為了得到擴張之后有最大實際保護效率的P圈。

步驟4，更新工作容量，分配空閑容量。

將最后保存的P圈配置到網(wǎng)絡中，更新工作容量矩陣，P圈每條邊上工作容量為workcapacity-1，跨接鏈路工作容量為workcapacity-2。為配置的P圈分配空閑容量，每條邊為sparecapacity+1。

步驟5，檢查工作容量，完成算法。

遍歷網(wǎng)絡中每條鏈路上未被保護的工作容量，如果還存在尚未保護的工作容量，轉(zhuǎn)至步驟1，否則算法結(jié)束，網(wǎng)絡中的所有單鏈路故障就得到了100%的保護。

4.3 算法的仿真結(jié)果

為了驗證改進算法的優(yōu)劣，對其進行編程實現(xiàn)，并和經(jīng)典的CIDA算法進行對比。本文選取COST239網(wǎng)絡拓撲模型來模擬廣電網(wǎng)OTN網(wǎng)絡的網(wǎng)狀組網(wǎng)，其拓撲結(jié)構(gòu)如圖1所示，該模型包含11個節(jié)點、26條邊。已知鏈路上的工作容量以波長為單位，假定網(wǎng)絡中的工作流向雙向?qū)ΨQ，且每個節(jié)點都具有全波變換的能力。

為了更真實地模擬廣電網(wǎng)實際的業(yè)務分配情況，本文選取相對均衡和一般均衡兩種模型對工作容量進行分配。工作容量的波長范圍分別在[6，9]，[1，16]之間，前者的波長分布較為集中，相對均衡，后者則相對分散，這兩種模型可以模擬實際應用并且能較為全面地分析算法的優(yōu)劣。對這兩種模型進行算法仿真結(jié)果如表1、表2所示。

圖1 COST239網(wǎng)絡拓撲

表1 CIDA和改進算法對模型1的仿真結(jié)果對比

表2 CIDA和改進算法對模型2的仿真結(jié)果對比

由仿真結(jié)果可知，相比于CIDA，改進算法需要配置P圈的個數(shù)較少，較少的P圈個數(shù)會減少廣電網(wǎng)管理的壓力。改進算法所需的預留空閑容量少于CIDA算法，這就意味著改進算法可用較少的空閑容量來保護與CIDA算法相同的工作容量，即提高了資源利用率，降低了冗余度?；谝陨系尿炞C結(jié)果可以認為，改進的算法優(yōu)于CIDA算法，可以在廣電網(wǎng)的應用中起到良好的作用。

5 小結(jié)

廣電網(wǎng)絡大容量的發(fā)展成為必然的趨勢，OTN在傳輸網(wǎng)上的應用越來越廣泛，為了方便網(wǎng)絡擴容，網(wǎng)絡結(jié)構(gòu)傾向于網(wǎng)狀網(wǎng)，由此網(wǎng)絡生存性的問題日益凸顯。為了解決這一重要問題，本文對現(xiàn)有的P圈容量分配算法進行了改進，減少了預置圈的個數(shù)并且提高了資源利用率，對廣電網(wǎng)絡生存性的提高具有理論指導意義。

[1] 陳翔.三網(wǎng)融合時代廣電光傳輸網(wǎng)絡發(fā)展趨勢分析[J].電視技術(shù)，2011，35（4）：49-51.

[2] 周紀華，李司宇.光電傳送網(wǎng)絡建設模式探討[J].廣播與電視技術(shù)，2011（7）：166-168.

[3]BIRKS T，RUSSELL P，CULVERHOUSE D.The acousto-optic ef?fect in single-mode fiber tapers andcouplers[J].Journal of Light Wave Technology，1996，14（11）：2519-2529.

[4] 姚曉宇.WDM光網(wǎng)絡中基于P-cycle的保護算法研究[D].南京：南京郵電大學，2011.

[5] GROVER W，STAMATELAKIS D.Cycle-oriented distributed pre-configuration:ring-like speed with mesh-like capacity for self-planning network restoration[C]//Proc.IEEE International Conference on Communications.[S.l.]：IEEE Press，1988：537-543.

[6] 姚曉宇，徐榮青，李亞玲，等.一種基于P圈的單鏈路故障啟發(fā)式算法研究[J].光通信研究，2010（4）：9-12.

[7] HAMZA D，NICOLAS B，ESTHER L，et al.P-cycle design for mixed-line rate optical networks[C]//Proc.International Confer?ence on Optical Networking Design and Modeling.[S.l.]：IEEE Press，2012：1-4.

Research on Heuristic P-cycle Algorithm of Large Capacity Broadcast&TV Network

SONG Shicong，NI Junhong，ZHAO Zhendong
（Dept.of Electronic and Communication Engineering,North China Electric Power Univ.,Hebei Baoding 071003,China）

Combined with the large capacity requirement of broadcast&TV network,in view of more complex mesh network,survivability is important to large capacity OTN network.In this paper，the classical P-cycle capacity assignment algorithm-CIDA is improved and the algorithm is simulated by using the COST239 network topology.The simulation results show that the improved algorithm has brought about better resource utilization and less P-cycles.The performance has been improved.Thus the improved P-cycle algorithm can better solve the survivability problem of large capacity broadcast&TV network.

broadcast&TV network;OTN;survivability;P-cycle

TN915.08

A

宋世聰（1988—），女，碩士生，主研電力系統(tǒng)通信；

?? 盈

2013-05-22

【本文獻信息】宋世聰，尼俊紅，趙振東.大容量廣電網(wǎng)的P圈啟發(fā)式算法研究[J].電視技術(shù)，2014，38（6）.

尼俊紅（1971—），女，副教授，碩士生導師，主要研究方向為寬帶無線移動通信系統(tǒng)中的關(guān)鍵技術(shù)、通信網(wǎng)絡管理；

趙振東（1956—），教授，碩士研究生導師，研究方向為電力系統(tǒng)通信、語音與圖像處理。