基于电网需求响应约束的多播路由

龙 丹,李晓卉,丁月民

(1.武汉科技大学 信息科学与工程学院,湖北 武汉 430081; 2.天津理工大学 计算机科学与工程学院,天津 300384)(*通信作者电子邮箱lixiaohui@wust.edu.cn)

0 引言

智能电网(Smart Grid, SG)是当今备受关注的研究领域,其稳定高效运行有利于经济的可持续性发展。电网广域控制通常将智能控制信息通过通信网络从供应侧(控制中心)传输到需求侧(电力用户)的智能设备,以确保智能电网电力需求与供应之间的平衡，因此智能电网要求电力需求响应(Demand Response, DR)[1-4]的通信具备较短的时延,以保证电网频率的稳定和电力控制的可靠性。

针对电网广域控制通信中“一到多”的多播特点,满足时延约束的多播路由算法被广泛应用于电网实时通信中。基于时延约束的经典多播路由算法有:KPP(Kompella、Pasquale、Polyzos)算法[5]首先构造包括源节点和目的节点满足时延限制的完全图,再利用Prim算法求出完全图的最小生成树(Minimum Steiner Tree,MST),最后把生成树还原到原图,并去掉存在的环; CDKS(Constrained Dijkstra Heuristic)算法[6]运用Dijkstra最短路径算法计算从源节点到各个目的节点的最小时延和最小代价路径来构造多播树;BSMA(Bounded Shortest Multicast Algorithm)[7]先用Dijkstra算法求出源节点到各个目的节点的最小时延路径,构成多播树,然后不断用代价更低的路径替代树上代价较高的超边;QDMR(QoS Dependent Multicast Routing)算法[8]通过检查每个目的节点的时延和时延约束之间的余量的大小来动态地调整多播树的构造等。

以上基于时延约束的多播路由算法在应用于多媒体通信业务中时对降低通信时延有较好的效果,并有学者在此基础上提出了改进算法,如基于共享边的时延约束组播路由算法[9]和时延约束的链路选择平衡优化组播路由算法[10]等。然而,在实际电网通信中由于需求侧的电力用户分布常常具有以下特点:大型工厂等电力消耗较大的电力用户往往分布在距离控制中心较远的郊区,但其DR能力对电网的稳定性影响较大;居民区等电力消耗较小的电力用户常常分布在距离控制中心较近的城镇区,但其DR能力对电网的稳定性影响较小。如果构造多播路由树只考虑时延约束,可能出现控制信息到DR能力大的用户所需时延较大,从而导致DR能力大的需求侧响应时延增加,引起电网频率较大波动,影响电网稳定性。

为了解决上述问题,本文提出一种综合考虑DR能力和通信时延约束的多播路由树构造方法——基于DR能力约束的多播路由(Demand Response capability Constrained Multicast routing,DRCM)算法。该算法将时延和多播目的节点DR能力作为约束条件构造多播路由树。仿真结果表明该算法能够使DR能力大的电力用户得到控制信息的通信时延减小,保证DR能力较大的需求侧优先对电力需求作出响应,稳定电网频率,保证电网的可靠性。

1 智能电网需求响应及多播问题

1.1 智能电网需求响应与多播

智能电网的多播结构如图1所示,其主要组成部分有:发电厂、智能控制调度中心、输电线路、变配电站和电力用户。控制信息以多播形式从智能控制调度中心经过通信网络传输到各个电力用户的智能DR设备。智能调度控制中心是智能电网区别于传统电网的主要组成部分,它通过需求响应来实现智能电网与电力用户之间的电力供求信息互动。需求响应可以有效、及时且准确地传递电力成本和需求信息,有助于电力需求侧与供应方之间保持电力实时平衡。

图1 智能电网的多播结构

由于需求响应能力受用户的电力需求变化和所在区域的影响,需求响应存在一定的时延。如图1所示,电力消耗小的居民用户位于距离控制中心较近的区域,需求响应时延短,其DR能力对电网稳定性的影响较小,造成的电网频率波动较小;而电力消耗大的工业电力用户距离控制中心较远,需求响应时延大,DR能力对电网稳定性的影响大,造成的电网频率波动较大。

电网需求侧智能设备的DR能力主要由两个因素决定:1)智能DR设备的负载可调功率;2)控制信息从智能控制中心传输到电力需求侧的通信时延。具有较大可调功率和较小通信时延的智能设备具有较大的DR能力(式(1)定义)。由于应用传统的多播路由算法只考虑了时延约束,不能解决具有较大DR能力需求侧的需求响应时延过大的问题，因此本文提出了考虑DR能力约束和时延约束的多播路由算法。

1.2 基于DR能力约束多播问题的描述

智能电网的通信网络可以表示为带权值的无向图G=(V,E)。其中：V是电力通信网络中控制中心和所有智能DR设备(即节点)的集合；E是通信链路(即边)的集合。在边E上定义c(i,j)和d(i,j)两个权重函数,分别表示费用函数和时延函数(其中i,j∈V)。在图G中,给定一个源节点s和多播目的节点集D(D⊆V),源节点到多个目的节点间的通信即构成多播通信。

在描述智能电网多播树构造问题之前,首先定义需求侧智能DR设备的DR能力。本文将电网用户侧智能DR设备的负载可调功率与通信时延相联系,定义需求侧智能DR设备即多播目的节点vk的DR能力为pk:

pk=wk/dk

(1)

其中:wk是智能DR设备的负载可调功率;dk是多播树中从源节点s到目的节点vk的端到端时延,即控制信息从智能控制中心传输到电力需求侧智能DR设备的通信时延。dk定义如下:

(2)

其中:VTr和ETr分别是多播树中所有节点和边的集合;d(i,j)是边(i,j)上的通信时延。

(3)

(4)

2 DRCM多播路由算法

由于式(4)是一个NP完全问题,通常采用启发式方法求解该问题。本文在典型的基于时延约束的多播路由算法KPP基础上,提出和设计了综合考虑智能DR设备的DR能力、时延和多播树费用的DRCM算法。该算法包括四个基本步骤:1)根据原图构建满足式(4)中约束条件的闭合图,即包括源节点和目的节点的完全图;2)根据DRCM算法的启发函数求出该完全图的最小生成树;3)根据DR能力调整多播树;4)把完全图的最小生成树还原到原网络,去掉可能存在的环。

2.1 DRCM算法的启发函数

为了使到目的节点时延短且费用小的链路加入到多播树,定义了DRCM算法的链路选择启发函数为fC(i,j):

(5)

2.2 DRCM算法流程

根据DRCM算法的四个主要步骤,其具体流程描述如下:

Step1 根据原图构建满足式(4)中约束条件的闭合图。

Step2 根据启发函数(式(5))求出完全图的最小生成树。

采用Prim最小生成树算法构造完全图的最小生成树。利用链路启发选择函数(式(5))查找完全图的最小生成树,直到所有目的节点都加入到多播树中。

Step3 根据DR能力调整多播树。

Step4 把完全图的最小生成树还原到原网络,去掉可能存在的环。

将多播树还原到原网络拓扑中,去除可能存在的环路,并计算源节点到每个目标节点的端到端时延。

由于多播树中源节点到大功率叶子节点多播路径的替换,使源节点到大功率远距离叶子节点的时延减小。

3 算法仿真

为了分析DRCM算法在智能电网多播通信中对具有较大DR能力的智能设备需求响应时延的影响,本文通过在Matlab中建立电网模型,仿真实现了三种多播路由算法,分别是DRCM算法、KPP算法[5]和MST算法[11],并比较上述算法在以下两方面的性能:1)比较三种算法所生成的多播树上最大端到端时延与DR能力大小的关系;2)由于多播树上不同DR能力的智能设备其需求响应时延不同从而导致负载功率变化曲线不同,因此建立电网频率控制系统模型,观察不同的负载功率偏差信号对电网频率波动的影响。

3.1 仿真场景及参数

本次仿真场景采用的是RT-nested-Smallworld电网演化模型[12],该模型具有明显的电网拓扑特性和电气特性,即明显的小世界特性、良好的连通性和可扩展性。选取电网广域控制中典型节点数N为300的情况[13]在Matlab中进行仿真实验,将节点随机分布在面积为100 km×100 km的范围内,将两点间的距离作为网络权值,忽略节点的转发时延、排队时延,只考虑传播时延,根据信息的传播速率为光速的2/3[14],可将传播时延表示为:时延=距离(km)×5 μs,设网络的费用与距离成正比(仿真中取距离代替费用)。根据参考文献[15]可以得到如图2所示的电网频率控制系统框图及各环节的参数。在Simulink中建立系统模型,设系统中有三种不同DR能力的负载,由于控制信息传输到DR设备存在时延,如图2左侧输入信号,横向为时延,纵向为功率偏差ΔPd。DRCM算法优先响应的是功率变化量最大的负载,即第一时刻ΔPd最大,第二、三时刻ΔPd依次递减；反之KPP算法和MST算法优先响应的是功率变化量最小的负载。不同算法响应不同DR能力负载的时延不同,导致功率偏差曲线ΔPd不同,因此电网频率响应的波动程度受到不同程度的影响。

图2 电网频率控制系统结构

3.2 仿真结果及分析

图4为需求侧功率变化量对电网频率的影响,考虑时延对需求响应的影响,三种算法响应不同DR能力负载时的顺序不同导致负载功率偏差曲线不同,该图间接反映了需求侧负载响应时延对电网频率的影响。仿真进行1 s后负载突然变化,由于电网中通信时延的存在,KPP算法和MST算法所生成的多播树上,使具有较大DR能力的负载通信时延较大,因此负载偏差较大的DR后响应,从图4可以看出其对应的电网频率曲线波动比较剧烈。本文提出的DRCM多播路由算法,由于考虑了目的节点的DR能力约束,对具有较大负载偏差的DR优先响应,因此使电网频率的波动大幅减小,保证了电网频率的稳定性。

图3 最大端到端时延与DR能力关系

图4 需求侧负载的功率变化量对电网频率的影响

4 结语

本文提出一种基于DR能力约束的多播路由算法,该算法将时延和多播目的节点DR能力作为约束条件构造多播路由树。仿真结果表明，该算法构造的多播树,能够使DR能力大的电力用户得到控制信息的通信时延减小,保证DR能力较大的需求侧优先对电力需求作出响应,稳定电网频率,保证电网的可靠性。本文通过对智能电网广域控制中多播路由方式的研究来减小电网需求响应时延,在后续的工作将继续展开保证电网服务质量的多播路由的研究与设计。

参考文献(References)

[1] MATSUMOTO J. Multicast tree construction algorithm for stabilization of power quality in smart grid[C]// Proceedings of the 2016 IEEE 17th International Conference on High Performance Switching and Routing. Piscataway, NJ: IEEE, 2016: 122-127.

[2] 张钦,王锡凡, 付敏, 等. 需求响应视角下的智能电网[J]. 电力系统自动化, 2009, 33(17): 49-55.(ZHANG Q, WANG X F, FU M, et al. Smart grid from the perspective of demand response [J]. Power System Automation, 2009, 33(17): 49-55.)

[3] MATSUMOTO J, ZHONG W D. New demand response architecture for stabilization of power quality in smart grid[C]// Proceedings of the 2013 9th International Conference on Information, Communications and Signal. Piscataway, NJ: IEEE, 2013: 1-5.

[4] 周振宇, 蔡骥然, 师瑞峰, 等. 智能电网需求响应通信架构综述[J]. 电气应用, 2013(增刊1): 68-74.(ZHOU Z Y, CAI J R, SHI R F, et al. Overview of intelligent grid demand response communication architecture[J]. Electrical Applications, 2013(S1): 68-74.)

[5] KOMPELLA V P, PASQUALE J C, POLYZOS G C. Multicast routing for multimedia communication[J]. IEEE/ACM Transactions on Networking, 1993, 1(3): 286-292.

[6] SUN Q, LANGENDORFER H. Efficient multicast routing for delay-sensitive applications[EB/OL]. [2017- 05- 10]. http: //citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4260.

[7] PARSA M, ZHU Q, GARCIA-LUNA-ACEVES J J. An iterative algorithm for delay-constrained minimum-cost multicasting[J]. IEEE/ACM Transactions on Networking, 1998, 6(4): 461-474.

[8] MATTA I, GUO L. QDMR: an efficient QoS dependent multicast routing algorithm[J]. Journal of Communications and Networks, 2002, 2(2): 168-176.

[9] 李元臣, 刘维群. 基于共享边的时延约束组播路由算法[J]. 计算机应用, 2009, 29(11): 2901-2903.(LI Y C, LIU W Q. Delay-constrained multicast routing algorithm based on shared edges[J]. Journal of Computer Applications, 2009, 29(11): 2901-2903.)

[10] 刘维群, 李元臣. 时延约束的链路选择平衡优化组播路由算法[J]. 计算机应用, 2011, 31(4): 925-927.(LIU W Q, LI Y C. Delay-constrained multicast routing algorithm based on optimized path selection[J]. Journal of Computer Applications, 2011, 31(4): 925-927.)

[11] KOU L, MARKOWSKY G, BERMAN L. A fast algorithm for Steiner trees[J]. Acta Informatica, 1981, 15(2): 141-145.

[12] WANG Z, SCAGLIONE A, THOMAS R J. Generating statistically correct random topologies for testing smart grid communication and control networks[J]. IEEE Transactions on Smart Grid, 2010, 1(1): 28-39.

[13] ALI I, AFTAB M A, HUSSAIN S M S. Performance comparison of IEC 61850- 90- 5 and IEEE C37.118.2 based wide area PMU communication networks [J]. Journal of Modern Power Systems & Clean Energy, 2016, 4(3): 487-495.

[14] 余燕平, 仇佩亮. 一种时延和时延抖动受约束的启动式多播路由算法[J]. 通信学报, 2003, 24(2): 132-137.(YU Y P, QIU P L. A heuristic of multicast routing with delay and delay variation constraints[J]. Journal on Communications, 2003, 24(2): 132-137.)

[15] BEVRANI H. Robust Power System Frequency Control[M]. Berlin: Springer, 2014: 23-33.

This work is partially supported by the National Natural Science Foundation of China (61702369), the Tianjin Municipal Science and Technology Commission Project (15JCYBJC52400).