A S O N路由算法在电力系统中的研究

胡朝平，易颖

（南京邮电大学 江苏南京 21003）

0 引言

在电力通信网中引入下一代网络旨在改革现有电力通信网和信息产业的基础设施，以支持更广泛的业务。其特点是：基于分组传输、呼叫控制与承载相分离、支持各种业务、可与现有网络互通。下一代网络为电力行业信息化建设的一些急待解决的问题提供了解决方案。ASON的出现代表了光网络技术发展的趋势，能够解决带宽快速部署、端对端配置和保护/恢复等问题，提供QoS/SLA和分布式的网络控制能力。

1 电力特种业务

电力特种业务的服务对象是电力输变电网的保障和控制装置，业务本身则由电力通信传输网承载。电力特种业务的承载目标，是确保业务的传送质量，不对输送电系统的控制附加额外异常，确保电力特种业务装置正确运行。

电力特种业务这里特指继电保护，采用差动纵联保护，或纵联差动保护，简称纵差保护。其保护利用通信业务通道，将本侧电流或电压的波形信息，或者代表电流或电压相位的信号传送到对侧，每侧保护均需根据两侧电流/电压幅值及相位进行比较计算，并在之上判断是区内还是区外故障，进而采取适当的控制措施。数字式电流差动保护是最普通的纵差保护方法，首先将各端电气量数字化，通过数字通信方式进行传送，然后利用微处理器进行动作判定。差动保护在算法上要求参加比较的各端电流量必须同步采样，或者经采样同步化处理。

2 问题分析及描述

电力SDH传输网影响特种业务性能的因素，主要包括业务通道延时(Sd)、双向通道延时差(Sv)。5 ms的通信通道延时可作为电力特种业务优良性能的基础；7~8 ms是继电保护业务的可用指标；延时10 ms以内的通道可用于安全稳定业务，不利于继保业务；20 ms以上延时的通信通道，对继保和安稳业务完全不可用。所以对于单向业务通道时延，一般要求小于8ms。

纵联差动装置之间可采用采样时间补偿或时钟校准方法实现电气量采样数据的同步，也是现网中得到应用最多的采样同步方法。设M侧装置至N侧装置的通道延时为T1，反向通道延时为T2，上述两种采样同步法在假设双向通道延时相同时测出的通道延时为：

与实际值的偏差则为：

由此可知，M侧采样数据与N侧采样数据在差动计算时，实际的时间差为2Te。，即|T1-T2|。工频50Hz（对应用360 °相角）的电气量，采用固定周期采样，则采样周期为：

其中，f为一周采样数，通常为12或24。

进行纵差条件计算的保护装置，如果正确比对采样时间的相角差容限为 θ，即大于该相角的两侧数据将可能导致装置误动作。显然，理论上 θ 的最大值为360/2f =180 / f。若f =12, 则 θ = 15；若f =12, 则 θ = 7.5。

实际应用当中，相角差容限的经验值为4°~6 °。与相角差容限 θ 相对应的时间差为：

可知，纵联差动保护装置不发生误动作的条件是：2Te< Ts。

依据上式，可以计算出纵联差动保护对双向通道延时差的理论容限和经验容限。针对继电保护业务，与双向通道延时差对相角差，可容纳的有效区间，其经验值小于4°~6 °；对于一周24点均匀采样，理论计算有效区间值小于7.5 °。所以对于双向通道延时差要求小于0.333ms。

分析了两个电力特种业务的要求后，可以将问题描述为：在一个给定权值的有向图G(V,E)中，给出源节点S和目的结点T，要求能够寻找到两条路径S-T和T-S。记S-T的时延为Delay1,T-S的时延为Delay2;要求单向时延Delay1和Delay2均小于要单向传输时延约束值Dmax(这里取8ms)；双通道时延差|Delay1- Delay2|小于约束值Dgap(这里取0.333ms)。并且要求两条路径不能经过同条链路或同个SRLG组。

3 流程图及算法描述

该路由算法可以理解为一种约束路由算法（CSPF），两个具体的约束因子：单向路径时延Delay<8ms,双向路径时延差D<0.333ms；具体算法步骤描述为：

步骤1：

获取相应的拓扑信息和相应边的权值等，有向图G；

步骤2：

使用Dijkstra算法求出S-T最小时延路径。计算其时延值，判断其是否小于时延约束值Dmax：若大于，则表明无法满足业务需求，算法结束；若小于，保存计算所得路径和相应时延Delay1；

步骤3：

修改相应图的权值，使用Dijkstra算法计算T-S的最短路径,记录路径和时延Delay2,比较Delay2是否小于Dmax。若Delay2小于Dmax,则比较|Delay1-Delay2|是否小于Dgap，若小于则算法成功，记录相应路径及路由，结束；若大于Dgap则转步骤4。若Delay2大于Dmax,则转步骤5；

步骤4：

比较Delay1是否大于Delay2,若Delay1>Delay2则用背离路径方法计算T-S下一条路径（该路径是时延仅大于Delay2的次短路径），若结果非空，则转步骤3；若结果为空，则转步骤5。若Delay1

步骤5：

图1 算法流程图

用背离路径方法计算下一条S-T路径（该路径是时延仅大于Delay1的次短路径）若结果为空，则算法失败，无法找到相应的路径，算法结束；若结果非空，则转步骤3；

在这个算法中，求解次短时延路径时运用了背离路径的思想。假设vi为源节点,vj为目的节点.(vi,vj)间的两条路径vi,v1,v2,,…vn,vj和vi,v’1,v’2,…vn,vj,，如果vi,v1,v2,…vn, 和vi,v’1,v’2, …v’n节点相同，在vn+1处开始不同，则称路径vi,v1,v2,,…vn,vj由vi,v’1,v’2,…n,vj在vn+1处背离得到, vn+1为被背离节点, v’n+1为背离节点。背离路径的定义:路径vi,v1,v2,v3,…vn,vj以vn+1为被背离节点,以v’n+1为背离节点的所有背离路径中有一条最短,它由vi,v1,v2,v3,…vn,+链路vn,vn+1,vn+2,…vj的最短路径得到。以v’n+1为背离节点的路径专指这条最短路径，而非以为v’n+1背离节点的其它路径。在求v’n+1到vj的最短路径时,应删除与节点vi,v1,v2,v3,…vn有关的链路,再利用Dijkstra 算法求最短路径,以避免拼接而成的背离路径产生环路。

算法的流程图如图1所示。

4 仿真结果

为了验证算法的可行性和正确性，取一个典型的5节点全连通图进行测试，如图2所示。设置每条光链路的主要属性（时延、距离）为图3所示。

图2 网络拓扑图

图3 节点属性图

利用文中算法计算点0至点3的双向链路，其结果如图4所示。计算得到了两条路径，分别为0-2-3和3-1-0，满足要求。

图4 路由计算后结果

现修改其中一条光通路0-2的属性，修改其距离为10km，相应时延也比原来增加了10倍，如图5所示。

图5 修改后的节点属性

重新计算点0-点3的双向链路，其结果如图6所示。重新计算得到的结果为0-4-3和3-1-0，算法没有选择那条时延较大的路径，证明了其正确性。

图6 重新计算后的结果

5 结束语

目前文中的路由算法，应用到电力ASON系统，能有效解决电力特种业务对于搜索双向链路的要求。在提高路径搜索效率方面，借鉴了“背离路径”的思想，来解决第K短路径问题，大大降低了时间复杂度。

[1] 王明中,谢剑英,陈应麟. 一种新的 Kth 最短路径搜索算法[J].计算机工程与应用, 2004（30）.

[2] 傅俊伟,李兴明,陈捷. 基于背离路径的 Kth最短路径实用搜索算法[J].计算机技术 与发展,2009,19(2).

[3] Ricardo Martínez, Ramon Casellas, Raül Muñoz, Takehiro Tsuritani.Experimental Translucent-Oriented Routing for Dynamic Lightpath Provisioning in GMPLS-Enabled Wavelength Switched Optical Networks[J].LIGHTWAVE TECHNOLOGY,2010,28(8).

[4] Pei Luo, Shanguo Huang, Weihua Lian, Bin Li, Wanyi Gu.Novel Routing Algorithms for Hierarchical Architecture in ASON[C].2009 WASE International Conference on Information Engineering,2009.

[5] G Maier, F Mizzotti, A Pattavina.Multi-domain routing techniques in ASON networks[C].Proc of ECOC, 33rd European Conference and Exhibition of Optical Communication,2007.

[6] Seyed Reza Ehsani, Valiallah Ghorbani, Sadegh Abbasi Shahkooh.Hierarchical routing in optical networks[C].2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications,2008.