考虑时延与流量均衡性的广域保护通信迂回通道重构算法
考虑时延与流量均衡性的广域保护通信迂回通道重构算法
【技术领域】
[0001] 本发明属于电力系统中继电保护领域，是一种考虑时延与流量均衡性的广域保护 通信迂回通道重构算法。
【背景技术】
[0002] 电力系统光纤通信线路运行过程中，工程人员经常需要检修和改造光纤线路，此 时就必须停运待操作的线路。有时光纤线路也会因突发事件而意外中断。在该些情况下， 我们仍期望中断光纤线路上原先承载的电力系统通信业务包括广域保护通信业务能够不 间断运行，实现电力系统持续正常工作。利用剩余健全网络预先构建一条最优迂回通信通 道用于传输需转移的实时业务，可实现电力系统通信业务包括广域保护通信业务持续、高 效运行。
[0003] 现有的一种构建最优迂回通信通道算法是将信道时延和带宽利用率两个参数用 于蚁群算法中选择最优迂回通信通道，但是只考虑了网络正常时各信道的时延，未考虑需 转移的数据流量加入备选信道后对备选信道通信时延造成的影响，其所选最优路径可能在 加入转移数据后变得堵塞（刘宝，尹项根，李振兴，等.基于蚁群算法的广域保护迂回通信 通道重构技术研究[时.中国山东济南；中国电工技术学会电力系统控制与保护专业委员 会，2012. 98-103)。另一种算法基于最短信道长度选择最优迂回通信通道，但是信道长度 只是影响通信时延的一部分因素，仅考虑信道长度不足W完整地反映出信道的时延特性 (鲍晓慧.基于迂回方式的继电保护信道重构技术[J].武汉理工大学学报，2010,23(4); 578-582)。还有观点提出基于安全性选择最优迂回通信通道，然而广域保护对通信时延有 着严格的要求，此方案不能满足广域保护快速性的要求（高会生，王慧芳.基于安全性的继 电保护光纤迂回通道路径选择[J].电力系统保护与控制，2014,42(14) ;25-31)。
【发明内容】
[0004] 本发明W选择出时延最短和流量均衡的迂回通信通道为目标。选取影响发送时延 的信道带宽倒数，影响传输时延的信道长度，影响排队时延的信道利用率=者之和作为权 重指标，用于改进的DiAstra算法中选择最优迂回通信通道。在计算信道利用率时，考虑 转移数据流入备选信道对备选信道内数据排队时延的影响，预算加入转移数据后备选信道 的信道利用率。在选择最优路径时，考虑转移数据流入备选信道后可能使备选信道变得堵 塞，提前筛选并剔除无法容纳转移数据流量和流入转移流量后堵塞的信道。本发明考虑影 响信道时延的因素较为全面，预先估计了转移流量可能对备选信道的影响，使所选最优路 径时延最短，并且可W选择出流入转移数据后仍不堵塞的信道，达到使所选各信道上流量 较为均衡的目的。
[0005] 本发明采取的技术方案为：
[0006] 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，包括W下步骤：
[0007] 步骤一：基于通信网络当前拓扑结构建立两中断节点间的预迂回路径表；
[0008]步骤二：综合影响信道时延的各种因素，选择影响发送时延tf的信道带宽倒数1/B、影响传输时延t,的信道长度山影响排队时延tP的信道利用率U，作为重构最优路径的影 响因子；
[0009]步骤考虑转移数据流入备选信道后，对备选信道内数据排队时延tp造成的影 响，根据排队时延tp与信道利用率U成指数关系，预算包含转移数据流量的备选信道的信 道利用率U;
[0010] 步骤四：对预迂回路径表内所有信道的信道带宽倒数和信道长度做归一化处理， 将归一化处理的带宽倒数、信道长度和预算的信道利用率=者加权得权重指标；
[0011] 步骤五；检查所有备选信道能否容纳转移数据流量Tt，剔除不能容纳转移流量的 备选信道，考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵塞，剔 除加入转移流量后发生堵塞的备选信道，最终形成可用的预迂回路径表；
[0012] 步骤六：把可用的预迂回路径表下路径总权重最小作为改进DiAstra算法寻优 目标。将权重指标作为改进DiAstra算法选择最优路径的条件，运用改进的DiAstra算 法选择出最优迂回通信通道。
[0013]步骤一中，W中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结构罗 列由起点到终点的所有迂回路径。
[0014]步骤二中，发送时延tf=1/B，1为数据帖长度，B为信道带宽；传输时延t,=d/v，d为信道长度，V为电磁波在信道上的传播速度；排队时延tp=au(a〉l)，u为信道利用率。
[0015]步骤S中，信道利用率U=Tm"/B，Tm。,为加入转移数据后备选信道最大流量，B为 相应备选信道的带宽。
[0016]步骤四中，归一化处理信道带宽倒数
为第i条信道带 宽倒数归一化处理后的值，为通信网中信道带宽倒数最大值，（1/B)mi。为通信网中 信道带宽倒数最小值。归一化处理信道长度
<为第i条信道长度归一化 处理后的值，屯"为通信网中信道长度最大值，dmi。为通信网中信道长度最小值。选择最优 路径的权重指标巫=巧/公巧*4.|+似;V,.，巫i为通信网络中i信道的权重值，《 1为归 一化的信道带宽倒数1/耸的系数，为归一化的信道长度却的系数，为信道利用率yi 的系数。《1，和《巧相对值，在不同的目标下，《 1，和《 3的相对大小会发生变化。
[0017] 步骤五中，判断Tit+Tw〉Bi是否成么是则剔除第i条信道，否则即第i条 信道可容纳转移流量，保留该信道为可用备选信道。Tit为流入第i条信道的转移流 量，Ti。为第i条信道原有的最大数据流量，Bi为第i条信道的带宽。然后，计算权重 0,.=巧巧八,，用于判断可能堵塞的信道。因为信道利用率y是反映转移数 据使备选信道时延增大的主要因素，所W推荐取《1= 1，《 2= 1，《 3= 5。筛选出权重值 最大的〇,该值对应的信道是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包 含堵塞信道的路径，最终形成可用的预迂回路径表。
[0018]步骤六中，将权重指标〇作为改进DiAstra算法选择最优路径的条件。此时，重 新计算0,.=巧/《+巧*式-fw, ，因为信道长度d和信道利用率y是反映信道整体时延 的主要因素，所W此时推荐取"1=1，《2=2,《3=2。执行改进Dijkstra算法时，选择 出与源点S相邻且权重值最小的点i;Wi为中间点计算& (i)+q(i,j)，& (i)为节点i与 源点s间信道上的权值，q(i，如为i到j信道上的权重值。比较〇 (i)+q(i，如与〇 (j)， 若〇 (i)+q(i，_]'）小于〇 (j)，则更新〇Ci)为〇 (i)+q(i，_]'），否则不更新；将此时B集合中 与起点间权重值最小的点j加入A集合中，若有多个点与起点权值相同且均为最小，则可W 任意选择一点加入A集合中；重复W上两点，直到检测到终点e包含入A集合。
[0019] 本发明是一种考虑时延与流量均衡性的广域保护通信迂回通道重构算法，优点在 于：
[0020] 1)、本发明在考虑迂回通道时延时，综合了影响发送时延的信道带宽倒数、影响传 输时延的信道长度、影响排队时延的信道利用率=个参数，并将该=个参数之和作为广域 保护通信迂回通道重构的权重指标。考虑时延的影响因素较为全面，使所选最优迂回通道 时延最小。
[0021] 2)、本发明在计算影响备选信道排队时延的信道利用率时，预先考虑中断信道上 需转移的数据流量流入备选信道后，对备选信道内数据排队时延的影响。利用加入转移 数据后备选信道的总数据流量预算备选信道的信道利用率，并将其用于迂回通道重构算法 中，使得所选最优迂回通道上各个信道的信道利用率受到限制，避免了个别信道上排队时 延骤增的情况，实现了最优迂回通道的流量均衡。
[0022] 3)、本发明在选择迂回 路径时，考虑了备选信道对转移数据流量的容纳能力。对于 不能容纳转移流量和流入转移流量后可能堵塞的备选信道提前剔除，减少了改进DiAstra 算法的执行步数，加快了整个迂回通道重构过程的执行速度。
[0023] 4)、本发明采用信道带宽倒数、信道长度、信道利用率S个参数加权构建改 进DiAstra算法的选路权重指标，基于可用预迂回路径表下路径权重最小作为改进 DiAstra算法寻优目标。该算法原理简洁，捜寻方向明确，可快速准确地选择出流量均衡下 时延最短的迂回通道。
【附图说明】
[0024] 图1为实施例中IE邸14节点系统简化模型图；
[00巧]图2为实施例中IE邸14节点系统参数矩阵，包括IE邸14节点系统信道长度矩阵 J、IE邸14节点信道原最大流量矩阵L、IE邸14节点信道带宽矩阵D。
【具体实施方式】
[0026] 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，步骤如下：
[0027] 步骤一 中断信道一端为起点，另一端为终点，统计通信网络当前拓扑结构，罗 列由起点到终点的所有迂回路径，形成两中断节点间的预迂回路径表；
[0028] 步骤二：综合影响信道时延的各种因素，选择影响发送时延tf的信道带宽倒数1/ B、影响传输时延t,的信道长度山影响排队时延tP的信道利用率U，作为重构最优路径的影 响因子。具体实施中提取预迂回路径表内所有节点间的信道带宽、信道长度、信道原最大流 量分别构成信道带宽矩阵D、信道长度矩阵J、信道原最大流量矩阵L。对信道带宽矩阵求倒 数，得信道带宽倒数矩阵，信道原最大流量矩阵用于计算预迂回路径表内所有信道的信道 利用率；
[0029]步骤考虑转移数据流入备选信道后，对备选信道内数据排队时延tp造成的影 响，根据排队时延tp与信道利用率U成指数关系，预算包含转移数据流量的备选信道的信 道利用率U，用信道利用率U反映排队时延的变化。依据U=Tm"/B计算预迂回路径表内所 有信道的信道利用率，形成信道利用率矩阵U;
[0030] 步骤四：对基于预迂回路径表的带宽倒数矩阵和信道长度矩阵做归一化处理，依 据
?对信道带宽倒数矩阵归一化处理，依据
对信道长 度矩阵归一化处理，选择最优路径的权重指标=巧/公;+巧*式+巧*从.，〇i为通信网络 中i信道的权重值，为归一化的信道带宽倒数1/却的系数，为归一化的信道长度马 的系数，《巧信道利用率yi的系数。《 1，和《 3为相对值，在不同的目标下，《 1， 和《 3的相对大小会发生变化。
[0031]步骤五：考虑预迂回路径表内所有备选信道能否容纳转移数据流量Tt，剔除不能 容纳转移流量的备选信道。具体做法是：判断Tit+Tw〉Bi是否成立，是则剔除第i条信道；否 则即第i条信道可容纳转移流量，保留该信道为可用备选信道。Tit为流入第i条信道的转 移流量，Ti。为第i条信道原有的最大数据流量，Bi为第i条信道的带宽；
[0032] 步骤六：考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵 塞，剔除加入转移流量后发生堵塞的备选信道，最终形成可用的预迂回路径表。计算权重 〇,=巧/公;+化八.，因为信道利用率y是反映转移数据使备选信道时延增大的 主要因素，所W推荐取《1= 1，《 2= 1，《 3= 5。筛选出权重值最大的〇,该值对应的信 道是流入转移数据后最堵塞的信道，在预迂回路径表中剔除包含最堵塞信道的路径，最终 形成可用的预迂回路径表。
[0033] 步骤^;：:把可用的预迂回路径表下路径总权重最小作为改进Di Astra算法寻优 目标。将权重指标作为改进Dijkstra算法选择最优路径的条件，运用改进的Dijkstra算 法选择出最优迂回通信通道。此时，重新计算〇,.=巧/与+啤*式+巧*八.，因为信道长度 d和信道利用率y是反映信道整体时延的主要因素，所W取《1= 1，《 2= 2，《 3= 2。 执行改进Dijkstra算法。选择出与源点S相邻且权重值最小的点ii为中间点计算 巫（i)+q(i，j)，巫（i)为节点i与源点S间信道上的权值，q(i，j)为i到j信道的权重值。 比较 & (i)+q(i,j)与 & (j)，若 & (i)+q(i,j)小于 & (j)，则更新 & (j)为 & (i)+q(i,j)， 否则不更新。将此时B集合中与起点间权重值最小的点j加入A集合中，若有多个点与起 点权值相同且均为最小，则可W任意选择一点加入A集合中；重复W上两点，直到检测到终 点e包含入A集合中为止。
[0034]实施例；
[003引如图1所示，在IE邸14节点系统中，5和6两个节点因为在同一变电站中，合并为 一个节点，编号为5。4、7、8和9四个节点在同一变电站内，合并为一个节点，编号为4。其 中5号节点因为连接支路数最多且位于系统中央，因此将5号节点作为中屯、节点，其余节点 为边缘节点，并且向5号节点发送信息。算例假定节点2与节点5之间的信道通信中断，求 节点2与节点5之间的最优迂回路径。
[0036] 根据本发明提出的考虑时延与流量均衡性的广域保护通信迂回通道重构算法进 行算例计算分析，具体步骤如下：
[0037] 步骤一 中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结构罗列 由起点到终点的所有迂回路径，建立两中断节点间的预迂回路径表；
[0038] 步骤二；初始化信道带宽矩阵D，信道长度矩阵J和信道原最大流量矩阵以如图2 所示。此时，因为节点2与5之间的信道中断，S个矩阵中节点2与5之间的数据全部置零。
[0039] 步骤根据U=Tm"/B预算加入转移数据后各个备选信道可能达到的最大信道 利用率，形成信道利用率矩阵U。
[0040] 步骤四：对信道带宽矩阵求倒，根据
.对信道带宽矩阵归 一化处理，根据
对信道长度矩阵归一化处理，选择最优路径的权重指标 0,. =巧/与+啤八,.，巫i为通信网络中i信道的权重值，为归一化的信道带宽 倒数1/马 1的系数，为归一化的信道长度马的系数，为信道利用率yi的系数。《 1， ? 2和《3为相对值，在不同的目标下，《1，《2和《3的相对大小会发生变化。
[0041] 步骤五；筛选出能容纳转移数据流量的信道。信道（2, 5)上有由节点2到节点5的 流量36. 74Mbit/s，此流量即为需转移的数据流量。将流量36. 74Mbit/s加入流量矩阵中的 每个非零项，然后判断36. 74+Tw〉Bi是否成立，是则剔除第i条信道；否则即第i条信道可 容纳转移流量，保留该信道为可用备选信道。经判断发现节点7到节点5间的信道流入转移 流量后可能达到的最大流量为56. 78Mbit/s，大于节点7到节点5间的信道带宽50Mbit/s。 因此，信道化5)不能承担转移流量，将该条信道从备选信道中剔除。剔除信道长度矩阵、 信道带宽矩阵和信道原最大流量矩阵中有关信道（7, 5)的数据，形成可用的备选信道数据 矩阵。
[004引步骤六：计算权重巫,.=巧/成+份2 *马+A*化，用于判断可能堵塞的信道。因为信 道利用率y是反映转移数据使备选信道时延增大的主要因素，所W推荐取《1= 1，《 2 = 1，《3= 5。筛选出权重值最大的0,经计算发现信道化5)的权重值0最大，为7. 374。 即信道化5)是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包含堵塞信道的 路径，最终形成可用的预迂回路径表。
[0043] 步骤走：将权重指标〇作为改进DiAstra算法选择最优路径的条件。此时，重新 计算=巧/公,1 +巧*却+似;//,，因为信道长度d和信道利用率y是反映信道整体时延的主 要因素，所W此时推荐取"1=1，《2=2,《3=2。执行改进Dijks tra算法，选择出最优 迂回通道。
[0044] 表1为节点（2, 5)间信道中断时执行本文提出的广域保护通信迂回通道重构算法 提取的全部备选路径及对应权值。
[0045] 表1 (2, 5)信道中断时全部备选路径及其权值
[0046]
[0047] 表2列出了信道（7, 5)流入转移流量后的信道总流量与相应带宽的对比。由表2 可知，信道化5)流入转移流量后的信道总流量可能大于其相应带宽，该条信道无法容纳 转移流量。因为首先考虑到转移数据对于备选信道原数据流量传输的影响，发现了无法容 纳转移数据流量的信道（7, 5)，提前剔除了备选路径中包含信道化5)的两条路径（如表1 所示），减少了执行改进DiAstra算法的步数，加快了整个选择最优路径算法的执行速度。
[0048] 表2 (7, 5)流入转移流量后信道总流量与相应带宽
[0049]
[0050] 表3为最优路径上流入转移数据前后信道利用率对比。需要转移的信道（2, 5)上 的数据流量是36. 74Mbit/s。该个流量数值大于其余信道上原有的数据流量。当转移数据 流量流入到某一信道上时，信道利用率增大是必然的，排队时延也会有一定程度的增加。从 表3可W看出所选路径各个信道上信道利用率虽然增大，但是仍在允许的范围内。在计算 信道利用率时，因为考虑到了数据转移对备选信道数据流量信道利用率的影响，使得所计 算的信道利用率与实际情况更加符合，而且本算法对最优路径的信道利用率有限制作用， 使所选最优路径各信道上流量较为均衡。
[0051] 表3最优路径上各信道加入转移数据前后的信道利用率U
[0052]
[0053] W上所述为本发明的较佳实施例而已，但本发明不应该局限于该实施例和附图所 公开的内容。所W凡是不脱离本发明所公开的精神下完成的等效或修改，都落入本发明保 护的范围。
【主权项】
1. 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，其特征在于，包括以下 步骤： 步骤一：基于通信网络当前拓扑结构建立两中断节点间的预迂回路径表； 步骤二：综合影响信道时延的各种因素，选择影响发送时延&的信道带宽倒数1/B、影 响传输时延ts的信道长度d，影响排队时延t p的信道利用率u，作为重构最优迂回路径的影 响因子； 步骤三：考虑转移数据流入备选信道后，对备选信道内数据排队时延％造成的影响，根 据排队时延tp与信道利用率u成指数关系，预算包含转移数据流量的备选信道的信道利用 率； 步骤四：对预迂回路径表内所有信道的信道带宽倒数和信道长度做归一化处理，将归 一化处理的带宽倒数、信道长度和预算的信道利用率三者加权得权重指标； 步骤五：检查所有备选信道能否容纳转移数据流量Tt，剔除不能容纳转移流量的备选 信道，考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵塞，剔除加 入转移流量后可能堵塞的备选信道，最终形成可用的预迂回路径表； 步骤六：把可用的预迂回路径表下路径总权重最小作为改进Di jkstra算法寻优目标， 将权重指标作为改进Di jkstra算法选择最优路径的条件，运用改进的Di jkstra算法选择 出最优迂回通信通道。2. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于，步骤一中，以中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结 构罗列由起点到终点的所有迂回路径，形成两中断节点间的预迂回路径表。3. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于，步骤二中，发送时延tf= 1/B，1为数据帧长度，B为信道带宽；传输时延t s = d/v，d为信道长度，V为电磁波在信道上的传播速度；排队时延tp= au(a>l)，u为信道利用 率。4. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤三中，信道利用率u = Tmax/B，Tmax为加入转移数据后备选信道最大流量， B为相应备选信道的带宽。5. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤四中，归一化处理信道带宽倒数为第i条信道 带宽倒数归一化处理后的值，（1/B)max为通信网中信道带宽倒数最大值，（1/B)min为通信网 中信道带宽倒数最小值，归一化处理信道长度，< 为第i条信道长度归一化 处理后的值，(1_为通信网中信道长度最大值，dmin为通信网中信道长度最小值；选择最优路 径的权重指标(丨),=叫/尽1+?2*4+? ?*//;_，0^为通信网络中1信道的权重值，〇1为归一 化的信道带宽倒数1/劣的系数，ω 2为归一化的信道长度4的系数，ω 3为信道利用率μ 4勺 系数；W1, 〇2和ω 3为相对值，在不同的目标下，ω i，〇2和ω 3的相对大小会发生变化。6. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构 算法，其特征在于：步骤五中，判断UTiPBi是否成立，是则剔除第i条信道，否则即 第i条信道可容纳转移流量，保留该信道为可用备选信道，Tit为流入第i条信道的转移 流量，Titl为第i条信道原有的最大数据流量，B i为第i条信道的带宽；然后，计算权重 Φ,.=叫/成+咚^/,1 +呌，用于判断可能堵塞的信道；因为信道利用率μ是反映转移数 据使备选信道时延增大的主要因素，所以推荐取ω1= 1，ω 2= 1，ω 3= 5 ;筛选出权重值 最大的Φ，该值对应的信道是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包 含堵塞信道的路径，最终形成可用的预迂回路径表。7. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤六中，将权重指标Φ作为改进Dijkstra算法选择最优路径的条件，此时， 重新计算Φ,.=以/尽1 +岣?1 +呌* ，因为信道长度d和信道利用率μ是反映信道整体时 延的主要因素，此时推荐取O1= 1，ω 2= 2, ω 3= 2。执行改进Dijkstra算法时，选择出 与源点s相邻且权重值最小的点i ;以i为中间点计算Φ⑴+q(i，j)，Φ⑴为节点i与源 点s间信道上的权值，q(i，j)为i到j信道上的权重值。比较Φ⑴+q(i，j)与Φ (j)，若 〇(i)+q(i，j)小于Φ〇_)，则更新Φ〇_)为Φ⑴+q(i，j)，否则不更新；将此时B集合中与 起点间权重值最小的点j加入A集合中，若有多个点与起点权值相同且均为最小，则可以任 意选择一点加入A集合中；重复以上两点，直到检测到终点e包含入A集合。
【专利摘要】一种考虑时延与流量均衡性的广域保护通信迂回通道重构算法，以电力通信网络中时延最短和流量均衡为最优目标，全面分析信道时延的构成和影响信道时延的各种因素，综合选择影响发送时延的信道带宽倒数、影响传输时延的信道长度和影响排队时延的信道利用率三个因素加权作为选择最优信道的权重指标，并将该权重指标用于改进的Dijkstra算法中选择最优迂回通信通道。以时延重权指标在可用的预迂回路径表下构建路径总权重，并以总权重最小作为改进Dijkstra算法寻优目标，执行改进Dijkstra算法，实现所选最优路径时延最短且各个链路流量较为均衡的重构选择。该方法重在电力系统通信光纤中断时基于剩余完好网络快速构建一条迂回通信通道以保证广域网通信业务正常进行。
【IPC分类】H04L12/727, H04L12/721, H04L12/751, H04L12/803
【公开号】CN104901886
【申请号】CN201510223246
【发明人】李振兴, 张腾飞, 李振华, 徐艳春, 袁兆强, 宋劢
【申请人】三峡大学
【公开日】2015年9月9日
【申请日】2015年5月5日
【技术领域】
[0001] 本发明属于电力系统中继电保护领域，是一种考虑时延与流量均衡性的广域保护 通信迂回通道重构算法。
【背景技术】
[0002] 电力系统光纤通信线路运行过程中，工程人员经常需要检修和改造光纤线路，此 时就必须停运待操作的线路。有时光纤线路也会因突发事件而意外中断。在该些情况下， 我们仍期望中断光纤线路上原先承载的电力系统通信业务包括广域保护通信业务能够不 间断运行，实现电力系统持续正常工作。利用剩余健全网络预先构建一条最优迂回通信通 道用于传输需转移的实时业务，可实现电力系统通信业务包括广域保护通信业务持续、高 效运行。
[0003] 现有的一种构建最优迂回通信通道算法是将信道时延和带宽利用率两个参数用 于蚁群算法中选择最优迂回通信通道，但是只考虑了网络正常时各信道的时延，未考虑需 转移的数据流量加入备选信道后对备选信道通信时延造成的影响，其所选最优路径可能在 加入转移数据后变得堵塞（刘宝，尹项根，李振兴，等.基于蚁群算法的广域保护迂回通信 通道重构技术研究[时.中国山东济南；中国电工技术学会电力系统控制与保护专业委员 会，2012. 98-103)。另一种算法基于最短信道长度选择最优迂回通信通道，但是信道长度 只是影响通信时延的一部分因素，仅考虑信道长度不足W完整地反映出信道的时延特性 (鲍晓慧.基于迂回方式的继电保护信道重构技术[J].武汉理工大学学报，2010,23(4); 578-582)。还有观点提出基于安全性选择最优迂回通信通道，然而广域保护对通信时延有 着严格的要求，此方案不能满足广域保护快速性的要求（高会生，王慧芳.基于安全性的继 电保护光纤迂回通道路径选择[J].电力系统保护与控制，2014,42(14) ;25-31)。
【发明内容】
[0004] 本发明W选择出时延最短和流量均衡的迂回通信通道为目标。选取影响发送时延 的信道带宽倒数，影响传输时延的信道长度，影响排队时延的信道利用率=者之和作为权 重指标，用于改进的DiAstra算法中选择最优迂回通信通道。在计算信道利用率时，考虑 转移数据流入备选信道对备选信道内数据排队时延的影响，预算加入转移数据后备选信道 的信道利用率。在选择最优路径时，考虑转移数据流入备选信道后可能使备选信道变得堵 塞，提前筛选并剔除无法容纳转移数据流量和流入转移流量后堵塞的信道。本发明考虑影 响信道时延的因素较为全面，预先估计了转移流量可能对备选信道的影响，使所选最优路 径时延最短，并且可W选择出流入转移数据后仍不堵塞的信道，达到使所选各信道上流量 较为均衡的目的。
[0005] 本发明采取的技术方案为：
[0006] 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，包括W下步骤：
[0007] 步骤一：基于通信网络当前拓扑结构建立两中断节点间的预迂回路径表；
[0008]步骤二：综合影响信道时延的各种因素，选择影响发送时延tf的信道带宽倒数1/B、影响传输时延t,的信道长度山影响排队时延tP的信道利用率U，作为重构最优路径的影 响因子；
[0009]步骤考虑转移数据流入备选信道后，对备选信道内数据排队时延tp造成的影 响，根据排队时延tp与信道利用率U成指数关系，预算包含转移数据流量的备选信道的信 道利用率U;
[0010] 步骤四：对预迂回路径表内所有信道的信道带宽倒数和信道长度做归一化处理， 将归一化处理的带宽倒数、信道长度和预算的信道利用率=者加权得权重指标；
[0011] 步骤五；检查所有备选信道能否容纳转移数据流量Tt，剔除不能容纳转移流量的 备选信道，考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵塞，剔 除加入转移流量后发生堵塞的备选信道，最终形成可用的预迂回路径表；
[0012] 步骤六：把可用的预迂回路径表下路径总权重最小作为改进DiAstra算法寻优 目标。将权重指标作为改进DiAstra算法选择最优路径的条件，运用改进的DiAstra算 法选择出最优迂回通信通道。
[0013]步骤一中，W中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结构罗 列由起点到终点的所有迂回路径。
[0014]步骤二中，发送时延tf=1/B，1为数据帖长度，B为信道带宽；传输时延t,=d/v，d为信道长度，V为电磁波在信道上的传播速度；排队时延tp=au(a〉l)，u为信道利用率。
[0015]步骤S中，信道利用率U=Tm"/B，Tm。,为加入转移数据后备选信道最大流量，B为 相应备选信道的带宽。
[0016]步骤四中，归一化处理信道带宽倒数
为第i条信道带 宽倒数归一化处理后的值，为通信网中信道带宽倒数最大值，（1/B)mi。为通信网中 信道带宽倒数最小值。归一化处理信道长度
<为第i条信道长度归一化 处理后的值，屯"为通信网中信道长度最大值，dmi。为通信网中信道长度最小值。选择最优 路径的权重指标巫=巧/公巧*4.|+似;V,.，巫i为通信网络中i信道的权重值，《 1为归 一化的信道带宽倒数1/耸的系数，为归一化的信道长度却的系数，为信道利用率yi 的系数。《1，和《巧相对值，在不同的目标下，《 1，和《 3的相对大小会发生变化。
[0017] 步骤五中，判断Tit+Tw〉Bi是否成么是则剔除第i条信道，否则即第i条 信道可容纳转移流量，保留该信道为可用备选信道。Tit为流入第i条信道的转移流 量，Ti。为第i条信道原有的最大数据流量，Bi为第i条信道的带宽。然后，计算权重 0,.=巧巧八,，用于判断可能堵塞的信道。因为信道利用率y是反映转移数 据使备选信道时延增大的主要因素，所W推荐取《1= 1，《 2= 1，《 3= 5。筛选出权重值 最大的〇,该值对应的信道是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包 含堵塞信道的路径，最终形成可用的预迂回路径表。
[0018]步骤六中，将权重指标〇作为改进DiAstra算法选择最优路径的条件。此时，重 新计算0,.=巧/《+巧*式-fw, ，因为信道长度d和信道利用率y是反映信道整体时延 的主要因素，所W此时推荐取"1=1，《2=2,《3=2。执行改进Dijkstra算法时，选择 出与源点S相邻且权重值最小的点i;Wi为中间点计算& (i)+q(i,j)，& (i)为节点i与 源点s间信道上的权值，q(i，如为i到j信道上的权重值。比较〇 (i)+q(i，如与〇 (j)， 若〇 (i)+q(i，_]'）小于〇 (j)，则更新〇Ci)为〇 (i)+q(i，_]'），否则不更新；将此时B集合中 与起点间权重值最小的点j加入A集合中，若有多个点与起点权值相同且均为最小，则可W 任意选择一点加入A集合中；重复W上两点，直到检测到终点e包含入A集合。
[0019] 本发明是一种考虑时延与流量均衡性的广域保护通信迂回通道重构算法，优点在 于：
[0020] 1)、本发明在考虑迂回通道时延时，综合了影响发送时延的信道带宽倒数、影响传 输时延的信道长度、影响排队时延的信道利用率=个参数，并将该=个参数之和作为广域 保护通信迂回通道重构的权重指标。考虑时延的影响因素较为全面，使所选最优迂回通道 时延最小。
[0021] 2)、本发明在计算影响备选信道排队时延的信道利用率时，预先考虑中断信道上 需转移的数据流量流入备选信道后，对备选信道内数据排队时延的影响。利用加入转移 数据后备选信道的总数据流量预算备选信道的信道利用率，并将其用于迂回通道重构算法 中，使得所选最优迂回通道上各个信道的信道利用率受到限制，避免了个别信道上排队时 延骤增的情况，实现了最优迂回通道的流量均衡。
[0022] 3)、本发明在选择迂回 路径时，考虑了备选信道对转移数据流量的容纳能力。对于 不能容纳转移流量和流入转移流量后可能堵塞的备选信道提前剔除，减少了改进DiAstra 算法的执行步数，加快了整个迂回通道重构过程的执行速度。
[0023] 4)、本发明采用信道带宽倒数、信道长度、信道利用率S个参数加权构建改 进DiAstra算法的选路权重指标，基于可用预迂回路径表下路径权重最小作为改进 DiAstra算法寻优目标。该算法原理简洁，捜寻方向明确，可快速准确地选择出流量均衡下 时延最短的迂回通道。
【附图说明】
[0024] 图1为实施例中IE邸14节点系统简化模型图；
[00巧]图2为实施例中IE邸14节点系统参数矩阵，包括IE邸14节点系统信道长度矩阵 J、IE邸14节点信道原最大流量矩阵L、IE邸14节点信道带宽矩阵D。
【具体实施方式】
[0026] 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，步骤如下：
[0027] 步骤一 中断信道一端为起点，另一端为终点，统计通信网络当前拓扑结构，罗 列由起点到终点的所有迂回路径，形成两中断节点间的预迂回路径表；
[0028] 步骤二：综合影响信道时延的各种因素，选择影响发送时延tf的信道带宽倒数1/ B、影响传输时延t,的信道长度山影响排队时延tP的信道利用率U，作为重构最优路径的影 响因子。具体实施中提取预迂回路径表内所有节点间的信道带宽、信道长度、信道原最大流 量分别构成信道带宽矩阵D、信道长度矩阵J、信道原最大流量矩阵L。对信道带宽矩阵求倒 数，得信道带宽倒数矩阵，信道原最大流量矩阵用于计算预迂回路径表内所有信道的信道 利用率；
[0029]步骤考虑转移数据流入备选信道后，对备选信道内数据排队时延tp造成的影 响，根据排队时延tp与信道利用率U成指数关系，预算包含转移数据流量的备选信道的信 道利用率U，用信道利用率U反映排队时延的变化。依据U=Tm"/B计算预迂回路径表内所 有信道的信道利用率，形成信道利用率矩阵U;
[0030] 步骤四：对基于预迂回路径表的带宽倒数矩阵和信道长度矩阵做归一化处理，依 据
?对信道带宽倒数矩阵归一化处理，依据
对信道长 度矩阵归一化处理，选择最优路径的权重指标=巧/公;+巧*式+巧*从.，〇i为通信网络 中i信道的权重值，为归一化的信道带宽倒数1/却的系数，为归一化的信道长度马 的系数，《巧信道利用率yi的系数。《 1，和《 3为相对值，在不同的目标下，《 1， 和《 3的相对大小会发生变化。
[0031]步骤五：考虑预迂回路径表内所有备选信道能否容纳转移数据流量Tt，剔除不能 容纳转移流量的备选信道。具体做法是：判断Tit+Tw〉Bi是否成立，是则剔除第i条信道；否 则即第i条信道可容纳转移流量，保留该信道为可用备选信道。Tit为流入第i条信道的转 移流量，Ti。为第i条信道原有的最大数据流量，Bi为第i条信道的带宽；
[0032] 步骤六：考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵 塞，剔除加入转移流量后发生堵塞的备选信道，最终形成可用的预迂回路径表。计算权重 〇,=巧/公;+化八.，因为信道利用率y是反映转移数据使备选信道时延增大的 主要因素，所W推荐取《1= 1，《 2= 1，《 3= 5。筛选出权重值最大的〇,该值对应的信 道是流入转移数据后最堵塞的信道，在预迂回路径表中剔除包含最堵塞信道的路径，最终 形成可用的预迂回路径表。
[0033] 步骤^;：:把可用的预迂回路径表下路径总权重最小作为改进Di Astra算法寻优 目标。将权重指标作为改进Dijkstra算法选择最优路径的条件，运用改进的Dijkstra算 法选择出最优迂回通信通道。此时，重新计算〇,.=巧/与+啤*式+巧*八.，因为信道长度 d和信道利用率y是反映信道整体时延的主要因素，所W取《1= 1，《 2= 2，《 3= 2。 执行改进Dijkstra算法。选择出与源点S相邻且权重值最小的点ii为中间点计算 巫（i)+q(i，j)，巫（i)为节点i与源点S间信道上的权值，q(i，j)为i到j信道的权重值。 比较 & (i)+q(i,j)与 & (j)，若 & (i)+q(i,j)小于 & (j)，则更新 & (j)为 & (i)+q(i,j)， 否则不更新。将此时B集合中与起点间权重值最小的点j加入A集合中，若有多个点与起 点权值相同且均为最小，则可W任意选择一点加入A集合中；重复W上两点，直到检测到终 点e包含入A集合中为止。
[0034]实施例；
[003引如图1所示，在IE邸14节点系统中，5和6两个节点因为在同一变电站中，合并为 一个节点，编号为5。4、7、8和9四个节点在同一变电站内，合并为一个节点，编号为4。其 中5号节点因为连接支路数最多且位于系统中央，因此将5号节点作为中屯、节点，其余节点 为边缘节点，并且向5号节点发送信息。算例假定节点2与节点5之间的信道通信中断，求 节点2与节点5之间的最优迂回路径。
[0036] 根据本发明提出的考虑时延与流量均衡性的广域保护通信迂回通道重构算法进 行算例计算分析，具体步骤如下：
[0037] 步骤一 中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结构罗列 由起点到终点的所有迂回路径，建立两中断节点间的预迂回路径表；
[0038] 步骤二；初始化信道带宽矩阵D，信道长度矩阵J和信道原最大流量矩阵以如图2 所示。此时，因为节点2与5之间的信道中断，S个矩阵中节点2与5之间的数据全部置零。
[0039] 步骤根据U=Tm"/B预算加入转移数据后各个备选信道可能达到的最大信道 利用率，形成信道利用率矩阵U。
[0040] 步骤四：对信道带宽矩阵求倒，根据
.对信道带宽矩阵归 一化处理，根据
对信道长度矩阵归一化处理，选择最优路径的权重指标 0,. =巧/与+啤八,.，巫i为通信网络中i信道的权重值，为归一化的信道带宽 倒数1/马 1的系数，为归一化的信道长度马的系数，为信道利用率yi的系数。《 1， ? 2和《3为相对值，在不同的目标下，《1，《2和《3的相对大小会发生变化。
[0041] 步骤五；筛选出能容纳转移数据流量的信道。信道（2, 5)上有由节点2到节点5的 流量36. 74Mbit/s，此流量即为需转移的数据流量。将流量36. 74Mbit/s加入流量矩阵中的 每个非零项，然后判断36. 74+Tw〉Bi是否成立，是则剔除第i条信道；否则即第i条信道可 容纳转移流量，保留该信道为可用备选信道。经判断发现节点7到节点5间的信道流入转移 流量后可能达到的最大流量为56. 78Mbit/s，大于节点7到节点5间的信道带宽50Mbit/s。 因此，信道化5)不能承担转移流量，将该条信道从备选信道中剔除。剔除信道长度矩阵、 信道带宽矩阵和信道原最大流量矩阵中有关信道（7, 5)的数据，形成可用的备选信道数据 矩阵。
[004引步骤六：计算权重巫,.=巧/成+份2 *马+A*化，用于判断可能堵塞的信道。因为信 道利用率y是反映转移数据使备选信道时延增大的主要因素，所W推荐取《1= 1，《 2 = 1，《3= 5。筛选出权重值最大的0,经计算发现信道化5)的权重值0最大，为7. 374。 即信道化5)是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包含堵塞信道的 路径，最终形成可用的预迂回路径表。
[0043] 步骤走：将权重指标〇作为改进DiAstra算法选择最优路径的条件。此时，重新 计算=巧/公,1 +巧*却+似;//,，因为信道长度d和信道利用率y是反映信道整体时延的主 要因素，所W此时推荐取"1=1，《2=2,《3=2。执行改进Dijks tra算法，选择出最优 迂回通道。
[0044] 表1为节点（2, 5)间信道中断时执行本文提出的广域保护通信迂回通道重构算法 提取的全部备选路径及对应权值。
[0045] 表1 (2, 5)信道中断时全部备选路径及其权值
[0046]
[0047] 表2列出了信道（7, 5)流入转移流量后的信道总流量与相应带宽的对比。由表2 可知，信道化5)流入转移流量后的信道总流量可能大于其相应带宽，该条信道无法容纳 转移流量。因为首先考虑到转移数据对于备选信道原数据流量传输的影响，发现了无法容 纳转移数据流量的信道（7, 5)，提前剔除了备选路径中包含信道化5)的两条路径（如表1 所示），减少了执行改进DiAstra算法的步数，加快了整个选择最优路径算法的执行速度。
[0048] 表2 (7, 5)流入转移流量后信道总流量与相应带宽
[0049]
[0050] 表3为最优路径上流入转移数据前后信道利用率对比。需要转移的信道（2, 5)上 的数据流量是36. 74Mbit/s。该个流量数值大于其余信道上原有的数据流量。当转移数据 流量流入到某一信道上时，信道利用率增大是必然的，排队时延也会有一定程度的增加。从 表3可W看出所选路径各个信道上信道利用率虽然增大，但是仍在允许的范围内。在计算 信道利用率时，因为考虑到了数据转移对备选信道数据流量信道利用率的影响，使得所计 算的信道利用率与实际情况更加符合，而且本算法对最优路径的信道利用率有限制作用， 使所选最优路径各信道上流量较为均衡。
[0051] 表3最优路径上各信道加入转移数据前后的信道利用率U
[0052]
[0053] W上所述为本发明的较佳实施例而已，但本发明不应该局限于该实施例和附图所 公开的内容。所W凡是不脱离本发明所公开的精神下完成的等效或修改，都落入本发明保 护的范围。
【主权项】
1. 考虑时延与流量均衡性的广域保护通信迂回通道重构算法，其特征在于，包括以下 步骤： 步骤一：基于通信网络当前拓扑结构建立两中断节点间的预迂回路径表； 步骤二：综合影响信道时延的各种因素，选择影响发送时延&的信道带宽倒数1/B、影 响传输时延ts的信道长度d，影响排队时延t p的信道利用率u，作为重构最优迂回路径的影 响因子； 步骤三：考虑转移数据流入备选信道后，对备选信道内数据排队时延％造成的影响，根 据排队时延tp与信道利用率u成指数关系，预算包含转移数据流量的备选信道的信道利用 率； 步骤四：对预迂回路径表内所有信道的信道带宽倒数和信道长度做归一化处理，将归 一化处理的带宽倒数、信道长度和预算的信道利用率三者加权得权重指标； 步骤五：检查所有备选信道能否容纳转移数据流量Tt，剔除不能容纳转移流量的备选 信道，考虑转移数据流量Tt流入备选信道后，可能使备选信道时延过大，发生堵塞，剔除加 入转移流量后可能堵塞的备选信道，最终形成可用的预迂回路径表； 步骤六：把可用的预迂回路径表下路径总权重最小作为改进Di jkstra算法寻优目标， 将权重指标作为改进Di jkstra算法选择最优路径的条件，运用改进的Di jkstra算法选择 出最优迂回通信通道。2. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于，步骤一中，以中断信道一端为起点，另一端为终点，根据通信网络当前拓扑结 构罗列由起点到终点的所有迂回路径，形成两中断节点间的预迂回路径表。3. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于，步骤二中，发送时延tf= 1/B，1为数据帧长度，B为信道带宽；传输时延t s = d/v，d为信道长度，V为电磁波在信道上的传播速度；排队时延tp= au(a>l)，u为信道利用 率。4. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤三中，信道利用率u = Tmax/B，Tmax为加入转移数据后备选信道最大流量， B为相应备选信道的带宽。5. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤四中，归一化处理信道带宽倒数为第i条信道 带宽倒数归一化处理后的值，（1/B)max为通信网中信道带宽倒数最大值，（1/B)min为通信网 中信道带宽倒数最小值，归一化处理信道长度，< 为第i条信道长度归一化 处理后的值，(1_为通信网中信道长度最大值，dmin为通信网中信道长度最小值；选择最优路 径的权重指标(丨),=叫/尽1+?2*4+? ?*//;_，0^为通信网络中1信道的权重值，〇1为归一 化的信道带宽倒数1/劣的系数，ω 2为归一化的信道长度4的系数，ω 3为信道利用率μ 4勺 系数；W1, 〇2和ω 3为相对值，在不同的目标下，ω i，〇2和ω 3的相对大小会发生变化。6. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构 算法，其特征在于：步骤五中，判断UTiPBi是否成立，是则剔除第i条信道，否则即 第i条信道可容纳转移流量，保留该信道为可用备选信道，Tit为流入第i条信道的转移 流量，Titl为第i条信道原有的最大数据流量，B i为第i条信道的带宽；然后，计算权重 Φ,.=叫/成+咚^/,1 +呌，用于判断可能堵塞的信道；因为信道利用率μ是反映转移数 据使备选信道时延增大的主要因素，所以推荐取ω1= 1，ω 2= 1，ω 3= 5 ;筛选出权重值 最大的Φ，该值对应的信道是流入转移数据后可能堵塞的信道，在预迂回路径表中剔除包 含堵塞信道的路径，最终形成可用的预迂回路径表。7. 根据权利要求1所述的考虑时延与流量均衡性的广域保护通信迂回通道重构算法， 其特征在于：步骤六中，将权重指标Φ作为改进Dijkstra算法选择最优路径的条件，此时， 重新计算Φ,.=以/尽1 +岣?1 +呌* ，因为信道长度d和信道利用率μ是反映信道整体时 延的主要因素，此时推荐取O1= 1，ω 2= 2, ω 3= 2。执行改进Dijkstra算法时，选择出 与源点s相邻且权重值最小的点i ;以i为中间点计算Φ⑴+q(i，j)，Φ⑴为节点i与源 点s间信道上的权值，q(i，j)为i到j信道上的权重值。比较Φ⑴+q(i，j)与Φ (j)，若 〇(i)+q(i，j)小于Φ〇_)，则更新Φ〇_)为Φ⑴+q(i，j)，否则不更新；将此时B集合中与 起点间权重值最小的点j加入A集合中，若有多个点与起点权值相同且均为最小，则可以任 意选择一点加入A集合中；重复以上两点，直到检测到终点e包含入A集合。
【专利摘要】一种考虑时延与流量均衡性的广域保护通信迂回通道重构算法，以电力通信网络中时延最短和流量均衡为最优目标，全面分析信道时延的构成和影响信道时延的各种因素，综合选择影响发送时延的信道带宽倒数、影响传输时延的信道长度和影响排队时延的信道利用率三个因素加权作为选择最优信道的权重指标，并将该权重指标用于改进的Dijkstra算法中选择最优迂回通信通道。以时延重权指标在可用的预迂回路径表下构建路径总权重，并以总权重最小作为改进Dijkstra算法寻优目标，执行改进Dijkstra算法，实现所选最优路径时延最短且各个链路流量较为均衡的重构选择。该方法重在电力系统通信光纤中断时基于剩余完好网络快速构建一条迂回通信通道以保证广域网通信业务正常进行。
【IPC分类】H04L12/727, H04L12/721, H04L12/751, H04L12/803
【公开号】CN104901886
【申请号】CN201510223246
【发明人】李振兴, 张腾飞, 李振华, 徐艳春, 袁兆强, 宋劢
【申请人】三峡大学
【公开日】2015年9月9日
【申请日】2015年5月5日
最新回复(0)