多阶段输电网络拥塞规避路由算法研究

孙园，邵振华，张辑

（厦门理工学院福建省高电压技术重点实验室，福建厦门 361024）

多阶段输电网络拥塞规避路由算法研究

孙园，邵振华，张辑

（厦门理工学院福建省高电压技术重点实验室，福建厦门 361024）

为了提高多阶段输电网络性能，提出了一种基于蚁群算法的多阶段输电网络拥塞规避路由算法，采用IP模块中的LMH0034芯片对多阶段输电网络路由信号进行均衡处理，提高路由信号的抗噪能力，通过路由更新模块对接口状态机以及接口路由表产生影响，及时调整系统的路由状态信息，采用信息处理模块实现路由系统信息的塑造、传递、采集以及处理。软件设计过程中，引入蚁群算法实现了多阶段输电网络拥塞规避路由算法的改进，给出了多阶段输电网络拥塞规避路由算法的具体代码。仿真实验结果说明，拥塞规避路由算法可以提高多阶段输电网络的吞吐率，降低网络时延和丢包率，最终提升多阶段输电网络的数据传输性能。

多阶段输电网络；拥塞规避；路由设计

随着我国电力事业的不断发展，多阶段输电网络应运而生[1-2]，在其不断发展的过程中，多阶段输电网络信息资源呈指数形式爆炸增长，导致网络拥塞频发，在这种情况下，良好的拥塞规避方法可以改善网络的性能[3]，提高网络的吞吐量[4-6]，降低数据的平均时延[7]，具有重要的现实意义。

传统的拥塞规避路由算法包括：基于最短路径优先算法的多阶段输电网络拥塞规避路由算法[8]，基于主动队列管理的多阶段输电网络拥塞规避路由算法[9]，基于业务优先级的多阶段输电网络拥塞规避路由算法等[10]。

但是上述传统算法存在不能对多阶段输电网络链路的拥塞状态做出快速反应、不能分散流量，不能避免链路的拥塞。所以提出了一种基于蚁群算法的多阶段输电网络拥塞规避路由算法，并通过仿真实验对该算法的性能进行验证。

1 总结构图

图1描述的是多阶段输电网络路由总体结构。用户控件主要由路由消息处理模块、数据报文处理模块、路由表更新模块以及定时器维护模块。内核空间主要由数据分流模块组成，通过Netfilter框架作用，并且结合ip_queue模块，介入报文的处理过程。

图1 系统总体结构图Fig.1 Overall structure of the system

2 硬件设计

2.1 IP模块概述

IP模块可以对多阶段输电网络中路由信号进行均衡处理，提高路由信号的抗噪能力。如图2所示。

图2 IP模块的基本框图Fig.2 Basic block diagram of the IP module

2.2 路由更新模块

在对多阶段输电网络路由表进行更新的过程中，路由更新模块将路由更新分组放入发送队列，再发送至各状态正常的接口。如图3所示。

2.3 路由信息处理模块

图4描述的是信息处理模块的组成框图，该模块主要实现多阶段输电网络路由系统信息的塑造、传递、采集以及处理。

图3 路由更新模块图Fig.3 Routing update module

图4 信息处理模块组成框图Fig.4 Block diagram of information processing module

3 软件设计

蚁群算法（蚂蚁算法），是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，研究表明，蚁群算法在网络路由算法中具有很高的应用价值，本文在上述硬件的基础上，提出一种基于蚁群算的多阶段输电网络拥塞规避路由方法，详细实现过程描述如下。

在多阶段输电网络拥塞规避路由规划过程中，多阶段输电网络覆盖范围广，跨越多个地理区域，可根据区域划分网络路由域，对大规模多阶段输电网络进行分割处理，简化路由算法分配的计算复杂度，利用式（1）对多阶段输电网络资源进行划分：

式中：Tmax为多阶段输电网络的最大传输资源；T（i）为多阶段输电网络时延需求；Tmin为多阶段输电网络的最小传输资源。

对多阶段输电网络资源进行划分后，在多阶段输电网络规划中，利用式（2）构建资源传输的适应度函数来描述输电网络过负荷的情况。

式中：L为多阶段输电网络负荷总量；n为负荷调节因子。

分析式（2）可知，当输电网络出现过负荷情况时，需要对网络路由中每条路传输路径（i，j）是否发生拥塞进行判断，利用式（3）进行表示：

式中：ΔBij为输电网络路由路径（i，j）的剩余带宽；bk为网络资源传输过程中需要消耗的实际带宽；λk为网络资源到达某一节点的申请达到率。

对某个路径进行判断时，该路径不发生拥塞现象，则跳过，对下一条路径继续判断，某条路径判断发生拥塞时，则利用式（4）对拥塞率进行计算：

式中：Pen为多阶段输电网络拥塞惩罚系数；Pover为多阶段输电网络某一阶段过负荷总量；i为规划阶段号；r为链路连接阻塞率；cj为多阶段输电网络链路容量。

对拥塞率最大的路径，本文提出一种基于蚁群算法完成多阶段输电网络拥塞规避路由算法，详细实现过程描述如下。

蚁群算法的基本原理为：路由路径的信息素浓度越低，蚂蚁选择该路径的概率越大，利用式（5）计算蚂蚁相邻节点转移概率：

式中：ηij为蚂蚁爬行时的能见度；β为蚂蚁爬行轨迹的相对重要性；α为示能见度的相对重要性；τij为路径信息素浓度。

蚂蚁结束一次觅食，就利用式（6）对个信息素浓度进行更新：

式中：ρ（0<ρ<1）为信息素残留因子；k为蚂蚁编号；m为迭代次数；Q为信息素增长浓度；F（Sk）为适应度值，最后利用更新后的结果组建蚂蚁觅食爬行原理。

式（7）、式（8）表示第k个蚂蚁在路径（i，j）上更新后的信息素浓度；Q为蚂蚁所留单位信息素浓度常数；n为多阶段输电网络节点总数，蚂蚁搜索路径的过程是最短路径，或者是寻找最大带宽路径的过程，当蚂蚁的爬行轨迹可以构成一条由初始节点到目的节点的路径时，利用式（7）表示，将该路径信息传送到目标节点后，立即向拥塞节点发送至其他蚂蚁，避开所有的拥塞链路，实现流量的分散，减缓拥塞状态，完成输电网络的拥塞规避路由算法。

式中：hop为蚂蚁从源节点到当前节点所经历的跳数；f（hop）为其增函数；Bmax和Bmin分别为多阶段输电网络中蚂蚁所经历路径的最大带宽和最小带宽；T和U为相关系数。

4 仿真实验结果与分析

为了验证多阶段输电网络拥塞规避路由算法的有效性，需要进行一次实验。本实验在Windows Server 2003服务器中进行，实验采用Matlab仿真软件进行测试。

在实验仿真平台中，为了便于分析，只模拟40个网络节点。按照顺序开启同时运行各模块进程，调整网络中节点的连通关系，使网络保持全连通状态。该网络拓扑中，节点20到节点1至19都是1跳，节点40到节点21至39都是1跳。节点20到40之间有一条线性连接的路径，同时20与24，24与28，…，36与40互相连通。节点初始的区域半径是4。

上述分组基于边界解析协议完成边界信息传递。例如节点36收到路由请求，确定出目的节点40为区域内节点，则传输路径应答分组给路由路径。该路径沿路由请求记录的反向路径向节点20传输，节点

20收到路由路径后传输数据，经多跳转发最后到达目的节点40，该分组传输的路径信息为20，24，28，32，36，40。

本文所设计的路由在多阶段输电网络中能有效运行，验证了程序设计的正确性。在上述网络中路由能很快收敛，区间路由也可被高效地塑造。本文所设计的路由还能迅速适应拓扑变化情况，同时可依据拓扑的改变自适应改变区域半径。

测试结果表明，处于内网的控制机全部可以通过服务器的网络共享正常上网，同时将传统的Fast FW300R型路由作为对照进行测试与本文路由系统进行对比，结果用表1描述。

表1 测试结果对比Tab.1 Comparison of test results

从表1可以看出，吞吐量是可以接收并转发的最大数据速率，吞吐量越大网络性能越好。本文方法下多阶段输电网络资源的吞吐量为82.6 Mbit·s-1，而传统的Fast FW300R下吞吐量仅为61.2 Mbit·s-1；延时是指接收到数据包到开始向目的端口发送数据包之间的时间间隔，延时越短，说明系统响应越快。本文方法下延时为0.4 ms，而传统的Fast FW300R算法的延时为1 ms；丢包率是指丢失数据包数量占所发送数据组的比率，丢包率越小，路由算法性能越好，本文方法下输电网络的丢包率为0.001%，而传统的Fast FW300R算法丢包率为0.005%。以上实验数据说明，所设计的多阶段输电网络拥塞规避路由算法较Fast FW300R型路由有更大的吞吐率，且延时与丢包率均低于Fast FW300R型路由，验证了本文设计的路由系统的有效性。

为了进一步验证本文拥塞规避路由算法的效果，将传统的Fast FW300R算法作为对照，将两种方法下的多阶段输电网络的剩余带宽进行比对，结果利用图5进行表示。

分析图5可知，带宽代表网络每秒可传输之位数，带宽越大，数据的传输性能越好，本方法下的剩余带宽一直高于传统的Fast FW300R，说明本文方法能够更加均衡地利用网络资源，可以有效避免某些链路非常繁忙而发生拥塞的情况。

图5 不同方法下输电网络剩余带宽比对Fig.5 Comparison of residual bandwidth of transmission networks in different ways

5 结语

提出了一种基于蚁群算法的多阶段输电网络拥塞规避路由算法，实验结果说明，拥塞规避路由算法可以提高多阶段输电网络的吞吐率，降低网络时延和丢包率，最终提升多阶段输电网络的数据传输性能。

[1]岳伟，易荣，张海涛，等.模块化多电平柔性直流输电系统的直流侧启动方法研究[J].电网与清洁能源，2014，30（10）:8-12.YUE Wei，YI Rong，ZHANG Haitao，et al.Research on DC staring method in the MMC-HVDC system[J].Power System and Clean Energy，2014，30（10）:8-12（in Chinese）.

[2]赵艳军，陈晓科，张跃，等.一种基于分布参数模型的输电线路参数在线测量方法[J].陕西电力，2015，43（12）:52-56.ZHAO Yanjun，CHEN Xiaoke，ZHANG Yue，et al.Parameter on-line measuring method of transmission lines based on distributed parameter model[J].Shaanxi Electric Power，2015，43（12）:52-56（in Chinese）.

[3]万杰，陈宁，钱敏慧，等.基于混合型深信度网络的风速日前预测研究[J].节能技术，2016，34（1）:81-86.WAN Jie，CHEN Ning，QIAN Minhui，et al.Day-ahead wind speed prediction based on hybrid deep belief network[J].Energy Conservation Technology，2016，34（1）: 81-86（in Chinese）.

[4]金鑫.高压直流输电系统极控信号通信网络可靠性分析[J].电力系统保护与控制，2015（12）:110-116.JIN Xin.Reliability analysis on HVDC pole control signal transmission network[J].PowerSystem Protection and Control，2015（12）:110-116（in Chinese）.

[5]石鑫，朱永利.面向输电线路监测的无线传输网络QoS保障技术研究[J].中国电力，2015，48（3）:39-43.SHI Xin，ZHU Yongli.Research on QoS support technology of wireless transmission networks for transmission line monitoring[J].Electric Power，2015，48（3）:39-43（in Chinese）.

[6]杜海涛，黎建华，瞿统弟，等.基于S3C6410的高校三相电网无功补偿节能控制系统[J].电子设计工程，2014，22（22）:111-114.DU Haitao，LI Jianhua，QU Tongdi，et al.Reactive power compensation and energy-saving control system based on S3C6410 for university electric networks[J].Electronic Design Engineering，2014，22（22）:111-114（in Chinese）.

[7]李翔硕，王淳，龚娇龙.基于食物链生态进化算法的多阶段输电网络规划[J].南昌大学学报（工科版），2012，34（1）:93-97.LI Xiangshuo，WANG Chun，GONG Jiaolong.Multistage transmission network planning based on ecology evolutionary algorithm of food Chain[J].Journal of Nanchang University（Engineering&Technology），2012，34（1）:93-97（in Chinese）.

[8]高元海，王淳.动态输电网络规划的组合编码遗传算法[J].电力系统保护与控制，2013（16）:1-6.GAO Yuanhai，WANG Chun.Combinationencoding genetic algorithm for dynamic transmission network planning[J].Power System Protection and Control，2013（16）: 1-6（in Chinese）.

[9]王传臣，张润彤，李丹丹，等.认知网络中的拥塞规避多径路由算法[J].电子学报，2011，39（8）:1858-1863.WANG Chuanchen，ZHANG Runtong，LI Dandan，et al.Multiple-path routing algorithm with congestion avoidance in cognitive networks[J].Acta Electronica Sinica，2011，39（8）:1858-1863（in Chinese）.

[10]曾瑛，李伟坚，陈媛媛，等.基于业务优先级的电力调度数据网拥塞规避算法[J].电力系统保护与控制，2014（2）:49-55.ZENG Ying，LI Weijian，CHEN Yuanyuan，et al.A congestion avoidance algorithm based on the service priority for electric power dispatching data network[J].Power System Protection and Control，2014（2）:49-55（in Chinese）.

（编辑 徐花荣）

附录

程序代码设计

对路由器各软件模块的关系与系统性能进行分析后，本文通过三个阶段来实现多阶段输电网络拥塞规避路由算法，具体实现代码如下：

Research on Congestion Avoidance Routing Algorithm for Multi-Stage Transmission Networks

SUN Yuan，SHAO Zhenhua，ZHANG Ji
（Key High-Voltage Laboratory of Fujian Province，Xiamen University of Technology，Xiamen 361024，Fujian，China）

In order to improve the multistage transmission network performance，this paper puts forward a multistage transmission network congestion avoid routing algorithm based on ant colony algorithm.The LMH0034 chip of the IP module is used for the balance treatment of the multi stage transmission network routing to improve the ability of anti noise signal routing，The routing update module exerts impacts on the interface state machine and interface routing table and timely adjusts the routing status information of the system，and the information processing module realizes the shaping，transfer，acquisition and processing of the routing information system.In the process of software design，the ant colony algorithm is introduced to achieve the multi stage transmission network congestion avoidance routing algorithm，and to give the specific code of the multi stage transmission network congestion avoidance routing algorithm.Simulation results show that the congestion avoidance routing algorithm can improve the throughput of the multi stage transmission network，reduce the network delay and packet loss rate，and ultimately improve the data transmission performance of the multi stage transmission network.

multi stage transmission network；congestion avoidance；routing design

2016-03-23。

孙 园（1981—），女，硕士，讲师，研究方向为智能电器与在线监测等；

邵振华（1979—），男，博士，讲师，研究方向为电力系统智能算法检测；

张 辑（1976—），男，硕士，讲师，研究方向为电力电子技术、高电压绝缘技术研究。

国家青年科学基金（E070602）；福建省科技厅高校产学合作科技重大项目（2014H6028）；厦门市科技局项目（3502Z 20153016）。

Project Supported by the Natural Science for Youth Foundation of China（E070602）；Major Projects of the Science and Technologhy Department of Fujian Province for Cooperation between Enterprises and Universities（2014H6028）；Science and Technology Bureau Project of Xiamen City（3502Z20153016）.

1674-3814（2016）09-0067-05

TP311

A