∑j
i,j)∈E′fklij−∑ji,j)∈Ekfklii=⎧⎩⎨⎪⎪1,−1,0,若i=Ls若i=dk若i=m∑��,�)∈�′�����−∑��,�)∈�������={1,若�=�s−1,若�=��0,若�=�
i,j)∈E′fklij−∑ji,j)∈Ekfklii=⎧⎩⎨⎪⎪1,−1,0,若i=Ls若i=dk若i=m∑��,�)∈�′�����−∑��,�)∈�������={1,若�=�s−1,若�=��0,若�=�近几年来，随着国内各项特高压、交直流工程的实施，智能电网已经发展成为跨区域互联大电网.在大电网中，由于实现调度、控制作用的通信网络一般与物理电网同架构敷设，所以使部署在相对偏僻环境中的通信站点和线路更容易因自身或者外界因素的影响而发生故障[1].与此同时，智能电网规模的扩大和结构的复杂化加速了电力新应用和新功能的兴起，由此衍生的高带宽电力通信业务加剧了网络中关键节点和链路的瓶颈化.尤其在通信网络发生故障时，现有的路由重构算法无法同时确保路径可靠性与网络负载均衡的统一.
在重路由方面，Chen等[2]针对通信链路中断情况下业务路径重构的问题，以最小化通信时延和业务均衡分布为目标，结合最短路径算法和遗传算法进行路径求解，但对不同业务服务质量(QoS，quality of service)需求的差异性考虑不足，因而可能出现部分链路承载高带宽业务而导致网络拥塞的情况.为避免故障恢复过程中因为软件定义网络(SDN，software defined networking)控制器和交换机之间频繁的流交互操作而导致恢复时间过长，学者将多条流聚合成一条大流，然后迂回到本地回路上，最终建模为一个整数线性规划问题，并采用启发式算法进行求解[3-4]，但没有考虑不同业务差异性，因而在电力通信网络中适用性不强.为满足业务的严格时延及带宽预留需求，Xie等[5]以路径上链路的最小空闲带宽应大于业务需求带宽为依据，在Dijkstra算法的基础上为业务计算可行路径，然后从有可行路径集中计算最不拥挤路径，从而有效降低阻塞率，并提高带宽利用率.
在负载均衡方面，崔力民等[6]以业务信息熵为目标，以业务时延和链路带宽为约束，采用量子遗传算法求解最优路径集，但智能算法收敛较慢. Constantinou等[7]根据网络中的链路使用情况提出了一种面向负载均衡的算法，具有较好的负载均衡效果，而在智能电网通信网中由于不同电压等级的站点间所使用的电力光缆的类型及光缆芯数都不尽相同，故无法直接采用. Tseng等[8]联合网络负载均衡和业务生存性因素，将IP网中通信链路发生故障后业务的快速重路由抽象为混合整数规划问题，并采用启发式算法进行求解.
目前在电力通信领域还没有将业务路由重构和网络负载均衡相结合的研究，因此，在通信网络发生故障后如何进行面向负载均衡的业务路由重构成为智能电网通信领域关注的问题之一.为确保路由重构后负载均衡，笔者在SDN通信架构下以链路可用度为目标，综合考虑流守恒、平均恢复时延、链路带宽及站点等级差等因素构建问题模型，并用面向负载均衡的业务路由重构算法(SRALB，service rerouting algorithm for load balancing)进行求解，最后给出仿真验证和结果分析.
1 问题建模下面将从通信架构、业务优先级化划分、模型构建及模型分析4个方面对问题进行分析描述.
1.1 通信架构SDN通信架构因为软硬件解耦及逻辑上集中管控的特点，具有更为快速的路由收敛能力，更能适应智能电网通信网中业务强实时性、高可靠性的严苛要求[7]. “高带宽、低时延、广覆盖”的通信网络为智能电网的稳定运行起重要支撑作用.
图 1给出了基于SDN的通信架构，在兼容现有网络的同时，采用弱集中控制方式屏蔽了底层硬件差异，在通信链路或节点出现故障时，协同控制器根据IP设备网管、光层设备网管及SDN控制器获取全局拓扑及链路使用情况进行路由计算，并将结果转发至各SDN交换机.
在通信网络故障场景下，为确保网络中重要业务优先进行路径分配，依据业务紧急程度、QoS差异性及对电网稳定运行重要性程度，将电力业务分为以下4类：
1) 实时性要求高，对电网运行特别重要的传统控制类业务，优先级设为1；
2) 实时性要求高，对电网稳定运行影响大的SCADA/EMS及全景感知类业务，优先级设为2；
3) 实时性要求一般，对电网稳定运行重要的视频监控类业务，优先级设为3；
4) 实时性要求低，对电网重要性一般的信息管理类业务，优先级设为4.
1.3 模型构建设网络拓扑为G(V，E，W1，W2)，V为对部署在变电站、调度中心的SDN交换机和控制器的抽象，|V|为网络中的节点数；E为边集合，是对通信链路的抽象，|E|为网络中的边数；W1、W2分别表示每条边(链路)的可用带宽和总带宽.由于通信节点失效相当于与该节点相连的所有链路均失效，所以仅以链路故障为例进行建模.设故障链路集合为F(Ls，Ld)，Ls、Ld分别为故障链路的2个端点，E'为删除故障链路之后的集合.故障链路上需要恢复的业务集合为S={s1，s2，…, sn}，n为业务数，sk为S中第k条业务，k∈(1，2，…，n).每条业务为一个五元组sk=(hk, dk, bk, tk, pk)，其中hk、dk、bk、tk、pk分别表示sk的起点、终点、带宽、时延需求及业务优先级，Pk为业务sk的路径集合.为方便问题描述，定义如下基本概念.
1) 节点重要度.通信节点在网络中的重要程度与其所处变电站点重要性相关.一般来说，站点电压等级越高，规模越大，管辖区域越广，承载的流量越多，站点重要度越高，对应通信节点重要度也越大.这里用站点电压值的归一化值表示相应节点的重要度.同理于链路重要度的定义.
2) 节点可用度.节点可用度表征通信节点的流量可接纳能力.由于当前面向负载均衡的研究大多仅考虑链路可用率，而对节点的流量处理能力及连通度考虑不足，尤其在网络负载增大时会加剧网络中关键节点或链路的瓶颈化[8].结合智能电网通信网络的特定应用场景，考虑到与该节点相连链路的可用带宽、总带宽及节点重要度等因素影响，定义节点可用度为
Avi=Nvi∑j∈IFij∑j∈ICij,∀i,j∈V,(i,j)∈E′���=���∑�∈����∑�∈����,∀�,�∈�,(�,�)∈�′ | (1) |
其中：Aiv、Niv分别为节点i的可用度、重要度，I为与节点i相连节点集合；Fij、Cij分别为链路(i, j)的剩余带宽和总带宽.
3) 链路可用度.链路可用度表示当前网络状态下链路可传输业务流的能力.由于通信过程中链路两端节点也参与数据处理，所以链路可用度不仅与该链路的带宽可用率、链路重要度等因素相关，还与链路两端节点的可用度及连通度相关，定义链路可用度为
Aeij=FijNeijAviAvjCij,∀i,j∈V,(i,j)∈E′����=����������������,∀�,�∈�,(�,�)∈�′ | (2) |
Nije为链路(i, j)的重要度.进一步定义链路权重为
ωij=(Aeij)−1,∀(i,j)∈E′���=(����)−1,∀(�,�)∈�′ | (3) |
由于电网中业务大多具有分层汇聚的特点，为实现QoS差异的业务重路由后负载均衡，应选择高可用度即权重小的链路进行传输，因而建立如下目标函数：
min∑sk∈S∑pkl∈Pkωijxklij,(i,j)∈E′min∑��∈�∑���∈����������,(�,�)∈�′ | (4) |
其中Plk为业务sk的第l条路径，xijkl为0-1变量：
xklij={1,0,路径pkl经过链路(i,j)其他�����={1,路径���经过链路(�,�)0,其他 | (5) |
此外，网络中业务流还需满足以下约束条件：
1) 流守恒约束
fklij−xklij≥0,∀pkl∈Pk,sk∈S�����−�����≥0,∀���∈��,��∈� | (6) |
xklij−(fklij/M)≥0,∀pkl∈Pk,sk∈S�����−(�����/�)≥0,∀���∈��,��∈� | (7) |
∑j i,j)∈E′fklij−∑ji,j)∈Ekfklii=⎧⎩⎨⎪⎪1,−1,0,若i=Ls若i=dk若i=m∑��,�)∈�′�����−∑��,�)∈�������={1,若�=�s−1,若�=��0,若�=� | (8) |
其中前2个约束表示承载在故障链路(Ls, Ld)上的业务sk在路径Plk上的流量和链路(i, j)之间的关系，<span class="MathJax" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="xijkl=0⇔fijkl=0,同时xijkl=1⇔fijkl>0" role="presentation" style="display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">xklij=0⇔fklij=0,同时xklij=1⇔fklij>0�����=0⇔�����=0,同时�����=1⇔�����>0.第3个约束是确保在特定节点处流入总流量等于流出总流量.
2) 带宽约束
业务sk的带宽需求bk应小于当前网络状态下链路(i, j)的剩余容量:
bk<Fij,∀(i,j)∈E′,sk∈S��<���,∀(�,�)∈�′,��∈� | (9) |
3) 时延约束
通信链路故障情况下端到端的时延包括无故障传输时延、故障处理时延及业务重路由时延.任意业务sk总时延Tsdk可表示为
Tksd=t1+tfc+tkl����=�1+���+��� | (10) |
其中:t1为常数，表示业务无故障传输时延; tfc为控制器故障处理时延; tlk为业务重路由时延，保证业务性能; sk应满足式(11)的约束，φ为预设的时延阈值.
0<Tksd≤φ0<����≤� | (11) |
4) 站点等级差约束
依据电压等级关系和区域划分的原则，电力业务通常在与起点电压等级相同或者相近的站点间传输，较少出现跨级变化.但在特高压站点所形成的跨区互联电网中，为实现远距离输电，并降低输电成本，2个特高压站点之间的通信往往需要迂回至临近区域中较低级别的站点和线路，若此时不对路径上站点等级进行限定，可能会导致迂回路径过长，增大了业务传输时延，也间接增大了传输风险.而站点等级与站点电压级别密切相关，电压级别越高，站点等级也相应越高，因此对相邻站点等级差限定如下：
Δij=|τi−τj|≤δ,∀i,j∈pkl,τi,τj=0,1,2,j=i+1Δ��=|��−��|≤�,∀�,�∈���,��,��=0,1,2,�=�+1 | (12) |
其中：τi、τj为相邻两节点的站点等级, δ为站点电压等级差阈值.
综上，在路径重构时面向业务负载均衡的数学优化模型构建如下：
min∑sk∈S∑Pkl∈Pkωijxklij,(i,j)∈E′s.t.(5)(6)(7)(8)(9)(10)(11)(12)min∑��∈�∑���∈����������,(�,�)∈�′s.t.(5)(6)(7)(8)(9)(10)(11)(12) | (13) |
这是一个多约束路由问题，属于非确定性多项式时间求解问题(NP-hard, non-deterministic polynomial- hard)，因而可采用智能算法进行求解，但由于要满足时延、带宽、站点等级等多个约束条件，很难控制算法的收敛速度，在k最短路径(KSP, k shortest paths)算法基础上通过路径筛选的方法，提出了面向负载均衡的路由重构算法(SRALB)，以获取满足业务需求的近似最优路径解集.
2 算法描述SRALB算法描述如下:
1) 网络初始化，读取网络拓扑G、故障链路集合F及受影响业务集合S; 同时根据故障链路集合更新网络拓扑G′；
2) 将S中的业务按优先级降序排序；
3) 从S中取出优先级最高的业务sk，如果两条业务优先级相同，则随机选取一条业务；
4) 判断业务sk的终点dk与故障链路的端点Ld是否相同，如果相同，执行6)；否则执行5)；
5) 如果Ld节点度为0，则目的节点为孤点，恢复失败，算法结束；否则转6)；
6) 检查网络，将不满足业务带宽要求的链路移除，并更新为Gk，用式(3)计算当前网络状态下每条链路的可用度；
7) 为业务sk计算K条权重最小路径P1k, P2k, …, PKk，并置l=1；
8) 判断当前路径Plk(1≤l≤K)是否满足各约束条件，若满足则转向9)；否则执行10)；
9) 接受该路径，并更新网络中各链路的可用带宽、链路流量可用度值及S=S\{sk}，恢复网络拓扑G′，若S=Φ，算法结束；否则转向3)；
10) 设置l=l+1，执行9);如果l >K，没有符合条件的路径，业务恢复失败，转向3).
2.1 复杂度分析在步骤6)中为计算链路可用度需要先计算网络中每个节点的可用度，所以其复杂度为O(|V|+|E′|), 步骤7)中算法的最差时间复杂度为O(Kn|V| (|V|log|V|+|E′|))，但K条路径中只有部分路径满足所有约束，所以实际SRALB的时间复杂度远小于该值.
2.2 评价指标为评估算法效果，用流量标准差作为业务流在网络中分布是否均衡的评价指标，标准差值越小，流量分布越均衡；反之则不均衡.
ζE′=|E′|−1∑(i,j)∈E′(Uij−Uavg)2−−−−−−−−−−−−−−−−−−−−√��′=|�′|−1∑(�,�)∈�′(���−�avg)2 | (14) |
Uavg=|E′|−1∑(i,j)∈E′Uij�avg=|�′|−1∑(�,�)∈�′��� | (15) |
其中：Uij为链路(i, j)的已用带宽，Uavg为平均已用带宽.
3 仿真结果3.1 参数设置为验证模型及算法性能，采用IEEE14母线系统组网测试[11].由于在电力系统中通信线路沿输电线路敷设，所以将处于同一变电站的SDN交换机、控制器抽象为一个节点，这里不考虑站内通信.网络拓扑如图 2所示，平均节点度为3，包含10个节点、15条边，SDN控制器部署在6号节点.节点旁的数字是站点编号，链路旁的数字分别表示站点间距离及链路可用带宽.
设链路带宽为1Gbit/s，SDN交换机平均排队转发时延为0.1ms，控制器处理时延为0.01ms，K=10，δ=2.按30%、30%、25%、15%的占比分别生成带宽为2、20、4、100Mbit/s的业务，其中70%的业务以500kV站点和220kV为源节点，与源点相距不超过3跳的节点为目的节点，其余30%业务的源、目的节点从V中随机选择，仿真次数为500.
3.2 结果分析下面以典型的流量负载均衡算法(LBT，load balancing of traffic algorithm)[7]和基于多链路故障场景下的重路由算法(MFRA，multiple link failures based rerouting algorithm)[12]为对比算法，分别从流量标准差、业务平均恢复时延、站点等级差3个方面与本文算法进行比较.由于故障链路数超过3时中会产生大量信息孤岛，网络处于瘫痪状态，所以仅考虑最多2条链路故障的情形. 图 3给出了不同链路故障(IL，interrupted link)下业务恢复率与受影响业务数之间的关系，这里用Nil表示故障链路的数量.可以看出，Nil=1且受影响业务数不超过15时能完全恢复业务，并随着故障链路数和业务数的增加，业务恢复率下降明显.在Nil=2时，业务数为50时业务恢复率仅为2.1%.
图 4(a)表示Nil=1时与链路中断前网络流量标准差(STDBLD，standard deviation before link disrupted)及不同算法下流量标准差随业务的变化情况.可以看出，LBT效果最好，SRALB与LBT接近，MFRA效果一般.这是因为LBT仅考虑链路可用带宽，流量分布更为均衡，而MFRA还考虑了链路失效概率因素，因而负载均衡效果不如SRALB和LBT，并且随着业务数增加，SRALB越来越接近LBT，说明本文算法较好的适应性. 图 4(b)表示Nil=2时负载均衡指标的变化.与图 4(a)相比，前者的流量标准差呈现明显波动，这是因为两条链路中断使网络中可能出现孤点，从而导致一些业务无法通过迂回方式实现路径恢复，而Nil =1时网络连通性基本不受影响.
图 5(a)给出在Nil=1时不同算法下业务平均恢复时延随业务数的对比情况.可以看出，随着业务数的增加，平均恢复时延变大，业务数的增加使得网络中满足业务需求的可用链路变少，因而业务需要经过更长的迂回路径.在相同业务数下，SRALB的业务平均恢复时延最小, MFRA稍高于SRALB，LBT算法最大. 图 5(b)给出了Nil=2时不同算法业务平均时延随受影响业务数的变化情况，整体趋势与图 6(a)相同，与Nil=1时相比，MFRA、SRALB、LBT的业务平均恢复时延分别提高了55.81%、45.67%和35.54%.
图 6(a)给出Nil=1时不同算法下平均站点等级差随业务数的变化情况，可以看出，在业务数相同时，SRALB所经节点的平均站点等级差最小，MFRA与LBT相近. 图 6(b)给出了Nil=2时不同算法下平均站点等级差随业务数的变化情况.可以看出，随着业务数的增加, 平均站点等级差也呈增大趋势.在相同业务数下, 平均站点等级差的变化趋势与图 6(a)相近.
4 结束语结合电网运行实际综合考虑了影响业务路径重构的节点可用度、链路可用度、业务时延及站点等级差等因素，提出了一种面向负载均衡的业务路由重构算法.实验结果表明，本文算法与已有算法相比具有相近或者更好的均衡效果，且具有更低的业务平均恢复时延和站点等级差，从而对智能电网中通信链路发生故障时实现业务路由的快速重构，并确保负载均衡具有一定的参考意义.
| 欢迎光临 信息谷 - ICITU (https://icitu.com/) | Powered by Discuz! X3.4 |