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

4) 连接物理层和保护环层的节点。在物理层和保护环层每一个节点对(vi，PRL， vi，PL)之间加一条无向边，这些边为连接边，该边的失效概率为0，连接代价为0.

建立的分层模型如图3所示。

图3 分层模型示意图

2.2路由的计算

在分层模型中计算出一条从源节点到目的节点的路由R，使得这条路由的失效概率不大于连接请求允许的最大失效概率并且使得这条路由的代价尽可能小。为了寻找路由R，使用Dijkstra算法在分层模型中计算出一条从源节点vs到目的节点vs的链路代价最小的路由R。

2.3路由的选取

在计算从源节点到目的节点的代价最小的路由过程中，判断这条路由的失效概率是否满足要求，不满足则在分层模型中去掉这条路由的所有链路从而形成新的模型，然后在这个新的分层模型中重新计算路由，知道找到一条代价最小且失效概率符合要求的路由为止，如果最终都没有符合要求的路由，则判定从源节点到目的节点不可达。

2.4

由于路由R是在分层模型中选取的满足最大失效概率的最小代价的路由，如果在路由R中存在保护层的边，那么就需要对路由进行匹配，将保护层的边用整个保护环来代替，并且去掉物理层与保护环层之间相连的边。这样得到的路由R即为满足连接请求所要求的最终路由。

3实验分析及性能评价

为了验证DRPR算法性能，采用如图4所示的美国网络作为仿真网络模型。假定网络中每条链路的失效概率与该链路的长度成正比。考虑两种状态的仿真，一种情况是等链路代价，另一种情况是链路的代价和链路长度有关。连接请求逐个到达且服从泊松分布，假定网络中每条链路的带宽能够完全满足连接请求的带宽需求。

图4 仿真网络结构图

假定三类连接请求，三类连接请求所允许的最大失效概率分别为p1、p1、p3，且p1

路由成功率定义为成功地建立路由的次数与路由建立请求的总次数之比。该实验仿真了两种情况下的路由成功率，一种为链路代价相同且为1;另一情况是链路代不同且与链路长度相等。令p1=0，p2=0.06，p3=0~0.2.实验仿真了两种情况下的平均代价，一次实验在网络中随即生成10000个连接，记录下每次实验的平均代价。

图5 两种链路代价情况下的路由成功率曲线

从图5给出的实验结构可见，当失效概率p3变大时，由于可靠性要求的降低，路由连接更容易满足可靠性的要求，因此算法的路由成功率更高。

图6中的星形符号实现表示使用DRPR算法在链路代价相同的情况下10次实验平均代价的分布，图7中的星形符号实现表示使用DRPR算法在链路代价等于链路长度的情况下10次实验平均代价的分布。

图6 相同链路代价条件下的实验结构曲线

图7 不同链路代价条件下的实验结构曲线

在文献中作者提出了SPPA算法，图6和图7中三角形符号虚线分布式使用SPPA算法在相同的情况下得到的平均代价。在图6中科院看出实验使用SPPA算法和使用DRPR算法得到的平均代价相差不大，而在图7中，使用DRPR算法得到的平均代价比使用SPPA算法得到的平均代价小很多。

在所提DRPR算法中，建立分层模型时首先对链路进行排序，然后寻找最小代价的链路生成保护环层，以此可以最大化地减小链路代价，在图6中，由于链路代价都 设为1，无法做到最小代价链路的优先选择，因此两种方法的平均代价相差不大。图7是在假设链路代价等于链路长度的情况下进行仿真所得的结果，由于每条链路的长度各不相同，这样就能够优先的选择代价较小的链路，仿真结构显示文本所提DRPR算法得出的平均代价比使用SPPA算法得出的平均代价底55%，优化了路由选择的结果。

4结论

通过对区分可靠性的分析，提出了一种基于分层模型的满足不同考烤箱需求的保护路由算法，通过与SPPA算法比较，所提DRPR算法在满足最大失效概率的情况下可减少连接请求的代价。通过实验和数据分析，使用DRPR算法得到的平均代价比使用SPPA算法的得到的平均代价小很多，从而能够极大优化网络资源的利用效率，是电力通信网络能够安全、可靠地运行，为智能电网的发展提供强大的通信保障。