新一代电力ICT网络中基于DiR保护环的生存性路由算法(1)

0引言

电力信息通信技术是支撑智能电网发展的主要技术之一，现代信息技术、通信技术与电网技术紧密结合，构建起信息化、自动化、互动化的智能电网，向用户提供更加全面、安全、便捷、舒适的服务。电力企业开展光传送网络、智能光网络、自动交换光网络等信息通信技术的研究，统一规划信息网络和通信网络，是信息通信网更好的服务于电力系统。智能光网络技术在电力通信网中的应用将极大地改变传输网的理念和运行方式，智能化电力光传输网络将是未来发展的必然趋势。

由于智能电网中光网络技术的广泛应用，其可靠性问题备受关注。传统的WDM光网络只向用户提供两种级别的可靠性服务。随着电力信息通信技术的发展，对网络业务质量的要求的多样化，为电力用户提供区分的可靠性服务是智能电力通信网络发展的趋势。文献研究单链路失效模型下的环网中的可靠度约束路由问题，文献研究单链路失效模型下WDM网状网中有可靠度约束时的静态规划问题，并提出了一种基于模拟退火的两步算法。在文献中提出单链路失效模型下WDM网状网中的提供区分可靠服务时的恢复机制，然而，这些研究仅考虑到了可靠度约束下的静态规划问题。由于当前的网络越来越复杂，网络需要动态地进行路由。文献提出了单链路失效模型下WDM网状网中有可靠度约束时的动态路由连接保护问题，但是耗费的网络资源较高。

针对电力通信网中智能电网业务的可靠性问题，本文提出了一种基于保护环的区分可靠性路由算法(the routing algorithm with differentiated reliability requirements based on protection ring,DRPR),使得路由连接在满足可靠性要求的前提下，网络资源消耗最低，从而提高网络资源的利用效率。

1问题描述

假定光网络的物理拓扑为G=(V,E)，其中V为节点集，E为链路集。令n、m分别表示网络G中的节点数和链路数。假定每个网络节点具有全波长变换能力，并且网络中的每条链路都是可以双向传输的光线。因此任何一条链路失效意味着该链路上任何一个方向的传输都会中断。另外假设链路容量足够大，对于每个连接请求，每条链路都满足连接请求的带宽需求。每条链路(i，j)都有两个链路参数：链路代价c(i，j)和链路失效概率Pf(i，j)。链路代价c(i，j)代表单位带宽(如一个波长)上数据信息从该链路的一段i传送到另一端j所消耗的代价。给定一条通路P，该通路的代价就是该通路上所有链路的代价之和。链路失效概率Pf(i，j)是指在网络中只有一条链路失效的条件下链路(i，j)失效的概率。令τ表示网络中平均每条链路的单位长度失效时间，令length(i，j)表示链路(i，j)的长度并令SFP表示网络G中的单个失效的概率：

链路(i，j)的失效概率：

给定一条通路P，在单链路失效的假设下，该通路的失效概率为该通路上所有链路的失效概率之和。

业务请求R=(s，t，r)动态的到达网络，其中s为业务请求的源节点号、t为业务请求的目的节点号，r表示连接请求语序的最大失效概率值。每个业务请求达到之后，要根据当前的网络状况为该连接请求计算一条路由，使得这条路由的最大失效概率要小于连接请求允许的最大失效概率并且期望这条路由耗费的代价最小。

如果一条通路的失效概率不大于连接请求的允许的最大失效概率，则这条通路就可以作为连接请求的路由。然而在有些情况下，一条通路的失效概率会大于连接请求允许的最大失效概率。以图1为例，其中每条边旁边的数字表示该边的链路代价和失效概率，并假定网络中链路带宽足够大。对于连接请求(1,7，r=0.3)而言，由于通路AP=1-2-5-7的失效概率为0.3，刚好等于连接请求允许的最大失效概率，因而可以选择通路AP作为这个连接请求的路由。如果该连接请求允许的最大失效概率不是0.3而是0.25，则图1中没有任何一条通路的失效概率小于连接请求允许的失效概率，从而没有任何一条通路可以单独用来作为该连接请求的路由。然而，如果通路AP商的链路2-5与路径BS=2-4-5组成一个保护环的话，由于网络中只有单个链路失效，则当链路2-5失效后该连接请求可以通过通路1-2-4-5-7来路由。因而通路AP和通路BS一起为连接请求提供的失效概率为0.2，小于连接请求允许的最大失效概率0.25，从而通路AP和路径BS一起可以作为该连接请求的路由。

图1 单链路失效时链路保护示例

当网络中只有单个链路失效，对于一条给定的通路P而言，如果P上的某条链路l和一条路径BPl组成了一个保护环，那么当通路P中的链路l失效后，连接请求仍然可以利用通路P上那些没有失效的链路以及保护环中未失效路径BPl来建立路由。因此，可以通过和通路P上的一下链路单独建立保护环的方式来降低整个路由的失效概率，从而满足连接请求的最大失效概率，因为在单链路失效的情况下，保护环中的任意链路(i，j)的失效概率为零。以图1为例，路径2-4-5-2组成了一个保护环，如果链路2-5失效，可以通过2-4-5来路由。同样，如果2-4失效或者4-5失效，可以通过2-5-4或者4-2-5来路由。这样，在计算这条路由实际失效概率的时候，只需要计算通路P上那些没有单独组成保护环的链路的失效概率即可。令ap表示通路AP上所有未单独形成保护环的链路组成的集合，这条通路AP的实际失效概率ra为：

实际失效概率及通路P上所有未单独形成保护环的链路的失效概率之和。

2DRPR算法描述

由于可以通过建立保护环的方式来降低整个路由的失效概率，那么可以首先对网络进行处理，在网络中尽可能的建立保护环。经过处理，网络中的链路将分为保护环中的链路和非保护环中的链路，然后在这个处理过的网络中来寻找路由，如果找到保护环中的链路，那么保护环也作为路由的一部分，并且该保护环的链路的失效概率为零。通过构造一个在保护环中的链路和非保护环中的链路构成的模型，就能够在该模型中为连接请求计算一条满足最大失效概率且代价最小的路由。

2.1模型的构造

算法首先构造一个分层模型，其中的一层成为保护环层;而另一层称为物理层。保护环层包含了网络中所有能够建立的保护环，而物理层是原始网络拓扑。分层模型的建立如下方法：

1) 对网络中的每一个点vi，分成两个子节点vi，PRL和vi，PL，vi，PRL表示保护环层的节点，vi，PL表示物理层的节点。

2) 构造物理层。物理层为原始的网络拓扑，每条链路的代价和失效概率与网络中链路的代价和失效概率相同。

3) 构造保护环层

由于算法需要选择最小代价路由，所有对原始拓扑图中的链路代价进行排序，从中选出链路代价最小的链路，然后为这条链路建立保护环。保护环的建立采用寻找最短路径对的方法，即为这条代价最小的链路寻找一条路径完全分离的通路，这条通路与该链路就形成了一个保护环。如果存在该通路，则建立保护环，如果不存在，则无法建立保护环。建立保护环时，或许会存在多条路径完全分离的通路和这条链路形成多个保护环，此时应当判断哪条通路形成的保护环的总代价最下，选择总代价最小的那个保护环作为该链路的保护环。如果成功建立保护环，那么这个环中的每条链路的代价是这个环的总代价之和，每条链路的失效概率为零，然后在网络中去掉该链路所在保护环中的搜有链路，从而重新形成新的网络拓扑;如果不能建立保护环，那么在网络中去掉该链路，从而重新形成新的网络拓扑。下一次寻找保护环时在新形成的网络拓扑总查找，这样能够保证不会对链路进行重复查找。

以图1为例说明如何构造分层模型中保护环层。先对链路进行排序，按链路代价从小到大的顺序排列，排列结果如表1所示。从表1可以得出，链路2-5代价最小，因此为链路2-5建立保护环。建立保护环时，首先使用Floyd算法寻找节点2到节点5的除了链路2-5的最短路径，使用Floyd算法能够保证查找出的路径代价是最小的。通过运行Floyd算法，通路2-4-5的代价为7，是节点2到节点5的除了链路2-5的代价最小路径。这样形成一个保护环2-4-5-2，保护环中的链路代价为该环的所有链路之和，链路的失效概率为零。然后在网络中去掉该环中的链路，在余下的网络拓扑中用同样的方法查找保护环，该网络拓扑的保护环层如图2所示。

表1 链路排列结果

图2 图1所示网络拓扑的保护环层