宋世聰，尼俊紅，趙振東

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

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

宋世聰，尼俊紅，趙振東

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

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

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

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

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

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

2 廣電網(wǎng)拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)生存性

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

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

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

3 預(yù)置圈算法

3.1 預(yù)置圈的基礎(chǔ)知識(shí)

近年來(lái)P圈研究的主要問題是高效P圈的構(gòu)造和P圈的容量分配[5]，這也是P圈算法最主要的兩步。P圈的構(gòu)造是指在網(wǎng)絡(luò)拓?fù)渲袑ふ铱赡艿幕救拖闰?yàn)效率高的擴(kuò)展圈，經(jīng)典的有枚舉算法Donald B Johnson、BFS和DFS擴(kuò)展成生成樹，啟發(fā)式算法SLA，SP-Add和Grow生成法。P圈的容量分配就是已知網(wǎng)絡(luò)拓?fù)渲形幢槐Ｗo(hù)的工作容量，為候選P圈配置空閑容量對(duì)其進(jìn)行保護(hù)?？上攵臻e容量占用率越高，網(wǎng)絡(luò)故障恢復(fù)能力越強(qiáng)，但這會(huì)造成網(wǎng)絡(luò)成本的提高。為了合理分配網(wǎng)絡(luò)空閑容量，提出了最大保護(hù)效率模型和最少空閑容量模型。

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

3.2 預(yù)置圈的評(píng)價(jià)標(biāo)準(zhǔn)

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

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

P圈實(shí)際的保護(hù)能力由保護(hù)效率確定，保護(hù)效率是指在網(wǎng)絡(luò)拓?fù)渲蠵圈可以實(shí)際保護(hù)的工作流量與配置該圈所消耗的空閑容量的比值，即

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

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

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

4.1 CIDA

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

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

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

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

找出網(wǎng)絡(luò)工作容量矩陣中的最大工作容量MAX及其對(duì)應(yīng)鏈路；將網(wǎng)絡(luò)拓?fù)渲兴墟溌返臋?quán)值修改為MAX+1-workcapacity，這樣可以保證在計(jì)算最短路徑時(shí)最先選擇未保護(hù)工作容量較多的鏈路，提高構(gòu)造出來(lái)的P圈的實(shí)際保護(hù)效能。

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

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

步驟3，對(duì)步驟2構(gòu)造的簡(jiǎn)單P圈進(jìn)行擴(kuò)張。

擴(kuò)張時(shí)首先選擇該圈上工作容量較大的邊，進(jìn)行最短路徑的尋找，保存下來(lái)并計(jì)算實(shí)際保護(hù)效率。重復(fù)上述步驟，直到擴(kuò)張之后的P圈保護(hù)效率比擴(kuò)張前的小，停止運(yùn)算，保存有最大保護(hù)效率的P圈。這樣是為了得到擴(kuò)張之后有最大實(shí)際保護(hù)效率的P圈。

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

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

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

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

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

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

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

圖1 COST239網(wǎng)絡(luò)拓?fù)?/p>

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

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

由仿真結(jié)果可知，相比于CIDA，改進(jìn)算法需要配置P圈的個(gè)數(shù)較少，較少的P圈個(gè)數(shù)會(huì)減少?gòu)V電網(wǎng)管理的壓力。改進(jìn)算法所需的預(yù)留空閑容量少于CIDA算法，這就意味著改進(jìn)算法可用較少的空閑容量來(lái)保護(hù)與CIDA算法相同的工作容量，即提高了資源利用率，降低了冗余度。基于以上的驗(yàn)證結(jié)果可以認(rèn)為，改進(jìn)的算法優(yōu)于CIDA算法，可以在廣電網(wǎng)的應(yīng)用中起到良好的作用。

5 小結(jié)

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

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

[2] 周紀(jì)華，李司宇.光電傳送網(wǎng)絡(luò)建設(shè)模式探討[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)絡(luò)中基于P-cycle的保護(hù)算法研究[D].南京：南京郵電大學(xué)，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

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

尼俊紅（1971—），女，副教授，碩士生導(dǎo)師，主要研究方向?yàn)閷拵o(wú)線移動(dòng)通信系統(tǒng)中的關(guān)鍵技術(shù)、通信網(wǎng)絡(luò)管理；

趙振東（1956—），教授，碩士研究生導(dǎo)師，研究方向?yàn)殡娏ο到y(tǒng)通信、語(yǔ)音與圖像處理。