大容量广电网的P圈启发式算法研究

宋世聪，尼俊红，赵振东

（华北电力大学 电子与通信工程系，河北 保定 071003）

大容量广电网的P圈启发式算法研究

宋世聪，尼俊红，赵振东

（华北电力大学 电子与通信工程系，河北 保定 071003）

结合广电网大容量的发展要求，考虑较为复杂的网状网结构，网络生存性问题日益凸显。对经典的预置圈（P圈）容量算法进行了改进，并选用COST239网络拓扑对改进算法进行编程仿真。结果证明，改进算法在减少预置圈数量的同时能够提高资源利用率，性能有所提高，可以较好地解决广电网的生存性问题。

广电网络；OTN；网络生存性；P圈

1 广电网的发展趋势——OTN

随着三网融合工作的不断推进，广电网络用户对IPTV、视频点播等互动式业务需求迅速增长，高清电视、3D电视业务正在不断开展，业务的增长使得网络带宽的需求迅速增长，建设高可靠、高速率、高效率、灵活方便部署、易维护的骨干传输网已成为广电网络业务发展迫在眉睫的需求[1]。光传送网（Optical Trans⁃port Network，OTN）正是为适应这一需求而发展的下一代传输网技术。

广电业务的发展经历了模拟电视、数字电视、互动、高清电视直至未来的多媒体全业务，目前，数字电视和数据业务占用现有SDH传输容量的绝大部分，下一步的互动、高清电视和多媒体数据业务等对传输带宽的需求量会迅速膨胀。OTN作为目前骨干传送网协调SDH网络的主流技术，具备超大容量、超长距离传送，灵活调度等，并且具备ASON网状网组网保护能力[2]，继承了SDH/MSTP的管理维护能力和传统电视节目的广播方式，可以支持迅速发展的互动高清电视业务。在三网融合和中国下一代广播电视网（NGB）的发展中，OTN将起到中流砥柱的作用。

2 广电网拓扑结构与网络生存性

OTN在为广电网的大容量、大带宽发展带来机遇的同时，也带来了一定的挑战。大容量的传输网络链路一旦发生故障，将影响业务的传送，导致大量数据业务失效，为广电公司带来经济损失，为用户生活带来不便。OTN巨大的传输容量和超高的传输速率使得光网络生存性问题更为突出。网络生存性[3]主要包括保护和恢复技术。其中，网络的拓扑结构与网络生存性息息相关。

目前，广电网大部分采用环形组网，但是随着三网融合的不断发展，环形拓扑结构在网络升级与扩容方面存在缺陷，该结构只能对全网统一升级，而不能针对部分链路升级扩容。网状网中大量节点之间可通过直达路由互连，只需要1条链路就能建立2个节点的连接，避免了建立多条通道，使得网络中节点之间有多种路由可选，具有灵活、易扩展的优点，克服了环形网的缺点。结合两种网络结构，未来广电网可以考虑采用分级网络构造，各个骨干站点机房采用网状或部分网状拓扑构建OTN网络，然后围绕骨干站点机房建立环形或部分网状拓扑结构的网络。这样可以解决环形网扩展性差、灵活性低、传输成本高等问题，优化整体的网络结构，为未来广电网的拓展与整合奠定基础。

构建的网状网在较大程度上利用了网络资源，具有高度的网络连接性并且扩容方便，但是由于网络复杂，其生存性的维护略差于线性、环形网络。预置圈（P圈）保护算法的出现恰好可以在保证网络恢复速度的同时维持网状网较高的资源利用率，提高网状网的网络生存性[4]。P圈算法最大的优点就是能为圈上链路提供一条保护通路的同时，为跨接链路故障提供两条保护通路。

3 预置圈算法

3.1 预置圈的基础知识

近年来P圈研究的主要问题是高效P圈的构造和P圈的容量分配[5]，这也是P圈算法最主要的两步。P圈的构造是指在网络拓扑中寻找可能的基本圈和先验效率高的扩展圈，经典的有枚举算法Donald B Johnson、BFS和DFS扩展成生成树，启发式算法SLA，SP-Add和Grow生成法。P圈的容量分配就是已知网络拓扑中未被保护的工作容量，为候选P圈配置空闲容量对其进行保护。可想而知，空闲容量占用率越高，网络故障恢复能力越强，但这会造成网络成本的提高。为了合理分配网络空闲容量，提出了最大保护效率模型和最少空闲容量模型。

现有的P圈容量分配算法根据使用的最优化方法，可分为完全最优化方法和启发式方法两类。完全最优化方法是枚举网络中所有简单圈作为候选P圈，然后利用整数线性规划（ILP）得到最优解，该方法在网络节点和链路较少时可以使用，但是在大中型网络中，由于计算量非常大、速度慢，不宜采用。启发式方法又可以分为基于ILP的启发式方法和完全启发式方法两类[5]，前者先计算出性能较好的备选圈，然后将备选圈进行最优化组合得到最优解，该方法仍然要用到ILP，因此计算时间较大，后者是直接利用启发式算法构造出性能较好的备选圈，再结合网络中的已知工作容量，优先配置实际保护能力大的备选圈，其目的是减小配置P圈的计算时间[6]。

3.2 预置圈的评价标准

对构造的P圈进行优劣选择时，主要采用两个指标：先验效率AE（p）和保护效率Ew（p）。先验效率体现了P圈在理论上最大的保护能力，定义为P圈能保护的最大工作容量与配置此圈所消耗的网络空闲容量的比值，即

式中：S表示所有链路的集合；Ci表示每条链路上的代价；Xp,i表示该P圈能够为链路i提供的保护通路的个数，主要用于构造备选P圈。根据P圈算法的原理，可以确定当i是P圈的边时，Xp,i=1；当i是跨接链路时，Xp,i=2；当i既不在圈上也不是跨接链路时，Xp,i=0。根据式（1）可知，P圈所包含的跨接链路越多，先验效率就会相应提高。然而，这只是P圈潜在的保护效率。

P圈实际的保护能力由保护效率确定，保护效率是指在网络拓扑中P圈可以实际保护的工作流量与配置该圈所消耗的空闲容量的比值，即

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

除先验效率和保护效率之外，冗余度是网络设计中一个相当重要的标准，定义为一个P圈的空闲容量（圈使用的波长数）与工作容量（圈上以及跨接链路上被保护的波长数）的比值[7]，它可以反映网络的资源利用效率。

4 CIDA和启发式算法的改进

4.1 CIDA

容量分配迭代算法（Capacitated Iterative Design Algorithm,CIDA）是P圈容量分配算法里最为经典的算法，它采用构造和容量分配相分离的思想，可以把过程大致分为两步：首先是构造候选P圈集合，可以采用SLA算法、SP-Add算法或GROW算法等来构造先验效率高的一系列基础圈。然后在候选集合里选择实际保护效率Ew（p）高的P圈进行容量分配。根据网络拓扑的初始工作容量计算集合里每一个圈的实际保护效率Ew（p），选择Ew（p）最大的一个P圈分配工作容量：圈上链路上减去一个工作容量，跨接链路上减去两个工作容量。更新工作容量，剩余容量就是未保护的工作容量。重复第二步，直到为所有链路提供了完全的保护。

4.2 启发式算法的改进

已知网络中未被保护的工作容量分布，将网络中每条链路的预留空闲容量初始化为0，算法具体步骤如下：

步骤1，修改链路权值。

找出网络工作容量矩阵中的最大工作容量MAX及其对应链路；将网络拓扑中所有链路的权值修改为MAX+1-workcapacity，这样可以保证在计算最短路径时最先选择未保护工作容量较多的链路，提高构造出来的P圈的实际保护效能。

步骤2，构造简单P圈。

以有最大工作容量的链路，即MAX对应的工作链路的起始节点为目标节点，删除该链路；在目标节点之间用Dijkstra算法找到1条最短路径，然后删除该最短路径；再在目标节点之间用Dijkstra算法寻找第2条最短路径。2条最短链路构成1个简单P圈，MAX对应的工作链路即为跨接链路。

步骤3，对步骤2构造的简单P圈进行扩张。

扩张时首先选择该圈上工作容量较大的边，进行最短路径的寻找，保存下来并计算实际保护效率。重复上述步骤，直到扩张之后的P圈保护效率比扩张前的小，停止运算，保存有最大保护效率的P圈。这样是为了得到扩张之后有最大实际保护效率的P圈。

步骤4，更新工作容量，分配空闲容量。

将最后保存的P圈配置到网络中，更新工作容量矩阵，P圈每条边上工作容量为workcapacity-1，跨接链路工作容量为workcapacity-2。为配置的P圈分配空闲容量，每条边为sparecapacity+1。

步骤5，检查工作容量，完成算法。

遍历网络中每条链路上未被保护的工作容量，如果还存在尚未保护的工作容量，转至步骤1，否则算法结束，网络中的所有单链路故障就得到了100%的保护。

4.3 算法的仿真结果

为了验证改进算法的优劣，对其进行编程实现，并和经典的CIDA算法进行对比。本文选取COST239网络拓扑模型来模拟广电网OTN网络的网状组网，其拓扑结构如图1所示，该模型包含11个节点、26条边。已知链路上的工作容量以波长为单位，假定网络中的工作流向双向对称，且每个节点都具有全波变换的能力。

为了更真实地模拟广电网实际的业务分配情况，本文选取相对均衡和一般均衡两种模型对工作容量进行分配。工作容量的波长范围分别在[6，9]，[1，16]之间，前者的波长分布较为集中，相对均衡，后者则相对分散，这两种模型可以模拟实际应用并且能较为全面地分析算法的优劣。对这两种模型进行算法仿真结果如表1、表2所示。

图1 COST239网络拓扑

表1 CIDA和改进算法对模型1的仿真结果对比

表2 CIDA和改进算法对模型2的仿真结果对比

由仿真结果可知，相比于CIDA，改进算法需要配置P圈的个数较少，较少的P圈个数会减少广电网管理的压力。改进算法所需的预留空闲容量少于CIDA算法，这就意味着改进算法可用较少的空闲容量来保护与CIDA算法相同的工作容量，即提高了资源利用率，降低了冗余度。基于以上的验证结果可以认为，改进的算法优于CIDA算法，可以在广电网的应用中起到良好的作用。

5 小结

广电网络大容量的发展成为必然的趋势，OTN在传输网上的应用越来越广泛，为了方便网络扩容，网络结构倾向于网状网，由此网络生存性的问题日益凸显。为了解决这一重要问题，本文对现有的P圈容量分配算法进行了改进，减少了预置圈的个数并且提高了资源利用率，对广电网络生存性的提高具有理论指导意义。

[1] 陈翔.三网融合时代广电光传输网络发展趋势分析[J].电视技术，2011，35（4）：49-51.

[2] 周纪华，李司宇.光电传送网络建设模式探讨[J].广播与电视技术，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光网络中基于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圈的单链路故障启发式算法研究[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—），女，硕士生，主研电力系统通信；

�� 盈

2013-05-22

【本文献信息】宋世聪，尼俊红，赵振东.大容量广电网的P圈启发式算法研究[J].电视技术，2014，38（6）.

尼俊红（1971—），女，副教授，硕士生导师，主要研究方向为宽带无线移动通信系统中的关键技术、通信网络管理；

赵振东（1956—），教授，硕士研究生导师，研究方向为电力系统通信、语音与图像处理。