基于電網(wǎng)需求響應(yīng)約束的多播路由

龍 丹,李曉卉,丁月民

(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院,湖北 武漢 430081; 2.天津理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,天津 300384)(*通信作者電子郵箱lixiaohui@wust.edu.cn)

0 引言

智能電網(wǎng)(Smart Grid, SG)是當(dāng)今備受關(guān)注的研究領(lǐng)域,其穩(wěn)定高效運(yùn)行有利于經(jīng)濟(jì)的可持續(xù)性發(fā)展。電網(wǎng)廣域控制通常將智能控制信息通過通信網(wǎng)絡(luò)從供應(yīng)側(cè)(控制中心)傳輸?shù)叫枨髠?cè)(電力用戶)的智能設(shè)備,以確保智能電網(wǎng)電力需求與供應(yīng)之間的平衡，因此智能電網(wǎng)要求電力需求響應(yīng)(Demand Response, DR)[1-4]的通信具備較短的時(shí)延,以保證電網(wǎng)頻率的穩(wěn)定和電力控制的可靠性。

針對電網(wǎng)廣域控制通信中“一到多”的多播特點(diǎn),滿足時(shí)延約束的多播路由算法被廣泛應(yīng)用于電網(wǎng)實(shí)時(shí)通信中。基于時(shí)延約束的經(jīng)典多播路由算法有:KPP(Kompella、Pasquale、Polyzos)算法[5]首先構(gòu)造包括源節(jié)點(diǎn)和目的節(jié)點(diǎn)滿足時(shí)延限制的完全圖,再利用Prim算法求出完全圖的最小生成樹(Minimum Steiner Tree,MST),最后把生成樹還原到原圖,并去掉存在的環(huán); CDKS(Constrained Dijkstra Heuristic)算法[6]運(yùn)用Dijkstra最短路徑算法計(jì)算從源節(jié)點(diǎn)到各個目的節(jié)點(diǎn)的最小時(shí)延和最小代價(jià)路徑來構(gòu)造多播樹;BSMA(Bounded Shortest Multicast Algorithm)[7]先用Dijkstra算法求出源節(jié)點(diǎn)到各個目的節(jié)點(diǎn)的最小時(shí)延路徑,構(gòu)成多播樹,然后不斷用代價(jià)更低的路徑替代樹上代價(jià)較高的超邊;QDMR(QoS Dependent Multicast Routing)算法[8]通過檢查每個目的節(jié)點(diǎn)的時(shí)延和時(shí)延約束之間的余量的大小來動態(tài)地調(diào)整多播樹的構(gòu)造等。

以上基于時(shí)延約束的多播路由算法在應(yīng)用于多媒體通信業(yè)務(wù)中時(shí)對降低通信時(shí)延有較好的效果,并有學(xué)者在此基礎(chǔ)上提出了改進(jìn)算法,如基于共享邊的時(shí)延約束組播路由算法[9]和時(shí)延約束的鏈路選擇平衡優(yōu)化組播路由算法[10]等。然而,在實(shí)際電網(wǎng)通信中由于需求側(cè)的電力用戶分布常常具有以下特點(diǎn):大型工廠等電力消耗較大的電力用戶往往分布在距離控制中心較遠(yuǎn)的郊區(qū),但其DR能力對電網(wǎng)的穩(wěn)定性影響較大;居民區(qū)等電力消耗較小的電力用戶常常分布在距離控制中心較近的城鎮(zhèn)區(qū),但其DR能力對電網(wǎng)的穩(wěn)定性影響較小。如果構(gòu)造多播路由樹只考慮時(shí)延約束,可能出現(xiàn)控制信息到DR能力大的用戶所需時(shí)延較大,從而導(dǎo)致DR能力大的需求側(cè)響應(yīng)時(shí)延增加,引起電網(wǎng)頻率較大波動,影響電網(wǎng)穩(wěn)定性。

為了解決上述問題,本文提出一種綜合考慮DR能力和通信時(shí)延約束的多播路由樹構(gòu)造方法——基于DR能力約束的多播路由(Demand Response capability Constrained Multicast routing,DRCM)算法。該算法將時(shí)延和多播目的節(jié)點(diǎn)DR能力作為約束條件構(gòu)造多播路由樹。仿真結(jié)果表明該算法能夠使DR能力大的電力用戶得到控制信息的通信時(shí)延減小,保證DR能力較大的需求側(cè)優(yōu)先對電力需求作出響應(yīng),穩(wěn)定電網(wǎng)頻率,保證電網(wǎng)的可靠性。

1 智能電網(wǎng)需求響應(yīng)及多播問題

1.1 智能電網(wǎng)需求響應(yīng)與多播

智能電網(wǎng)的多播結(jié)構(gòu)如圖1所示,其主要組成部分有:發(fā)電廠、智能控制調(diào)度中心、輸電線路、變配電站和電力用戶?？刂菩畔⒁远嗖バ问綇闹悄芸刂普{(diào)度中心經(jīng)過通信網(wǎng)絡(luò)傳輸?shù)礁鱾€電力用戶的智能DR設(shè)備。智能調(diào)度控制中心是智能電網(wǎng)區(qū)別于傳統(tǒng)電網(wǎng)的主要組成部分,它通過需求響應(yīng)來實(shí)現(xiàn)智能電網(wǎng)與電力用戶之間的電力供求信息互動。需求響應(yīng)可以有效、及時(shí)且準(zhǔn)確地傳遞電力成本和需求信息,有助于電力需求側(cè)與供應(yīng)方之間保持電力實(shí)時(shí)平衡。

圖1 智能電網(wǎng)的多播結(jié)構(gòu)

由于需求響應(yīng)能力受用戶的電力需求變化和所在區(qū)域的影響,需求響應(yīng)存在一定的時(shí)延。如圖1所示,電力消耗小的居民用戶位于距離控制中心較近的區(qū)域,需求響應(yīng)時(shí)延短,其DR能力對電網(wǎng)穩(wěn)定性的影響較小,造成的電網(wǎng)頻率波動較小;而電力消耗大的工業(yè)電力用戶距離控制中心較遠(yuǎn),需求響應(yīng)時(shí)延大,DR能力對電網(wǎng)穩(wěn)定性的影響大,造成的電網(wǎng)頻率波動較大。

電網(wǎng)需求側(cè)智能設(shè)備的DR能力主要由兩個因素決定:1)智能DR設(shè)備的負(fù)載可調(diào)功率;2)控制信息從智能控制中心傳輸?shù)诫娏π枨髠?cè)的通信時(shí)延。具有較大可調(diào)功率和較小通信時(shí)延的智能設(shè)備具有較大的DR能力(式(1)定義)。由于應(yīng)用傳統(tǒng)的多播路由算法只考慮了時(shí)延約束,不能解決具有較大DR能力需求側(cè)的需求響應(yīng)時(shí)延過大的問題，因此本文提出了考慮DR能力約束和時(shí)延約束的多播路由算法。

1.2 基于DR能力約束多播問題的描述

智能電網(wǎng)的通信網(wǎng)絡(luò)可以表示為帶權(quán)值的無向圖G=(V,E)。其中：V是電力通信網(wǎng)絡(luò)中控制中心和所有智能DR設(shè)備(即節(jié)點(diǎn))的集合；E是通信鏈路(即邊)的集合。在邊E上定義c(i,j)和d(i,j)兩個權(quán)重函數(shù),分別表示費(fèi)用函數(shù)和時(shí)延函數(shù)(其中i,j∈V)。在圖G中,給定一個源節(jié)點(diǎn)s和多播目的節(jié)點(diǎn)集D(D?V),源節(jié)點(diǎn)到多個目的節(jié)點(diǎn)間的通信即構(gòu)成多播通信。

在描述智能電網(wǎng)多播樹構(gòu)造問題之前,首先定義需求側(cè)智能DR設(shè)備的DR能力。本文將電網(wǎng)用戶側(cè)智能DR設(shè)備的負(fù)載可調(diào)功率與通信時(shí)延相聯(lián)系,定義需求側(cè)智能DR設(shè)備即多播目的節(jié)點(diǎn)vk的DR能力為pk:

pk=wk/dk

(1)

其中:wk是智能DR設(shè)備的負(fù)載可調(diào)功率;dk是多播樹中從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)vk的端到端時(shí)延,即控制信息從智能控制中心傳輸?shù)诫娏π枨髠?cè)智能DR設(shè)備的通信時(shí)延。dk定義如下:

(2)

其中:VTr和ETr分別是多播樹中所有節(jié)點(diǎn)和邊的集合;d(i,j)是邊(i,j)上的通信時(shí)延。

(3)

(4)

2 DRCM多播路由算法

由于式(4)是一個NP完全問題,通常采用啟發(fā)式方法求解該問題。本文在典型的基于時(shí)延約束的多播路由算法KPP基礎(chǔ)上,提出和設(shè)計(jì)了綜合考慮智能DR設(shè)備的DR能力、時(shí)延和多播樹費(fèi)用的DRCM算法。該算法包括四個基本步驟:1)根據(jù)原圖構(gòu)建滿足式(4)中約束條件的閉合圖,即包括源節(jié)點(diǎn)和目的節(jié)點(diǎn)的完全圖;2)根據(jù)DRCM算法的啟發(fā)函數(shù)求出該完全圖的最小生成樹;3)根據(jù)DR能力調(diào)整多播樹;4)把完全圖的最小生成樹還原到原網(wǎng)絡(luò),去掉可能存在的環(huán)。

2.1 DRCM算法的啟發(fā)函數(shù)

為了使到目的節(jié)點(diǎn)時(shí)延短且費(fèi)用小的鏈路加入到多播樹,定義了DRCM算法的鏈路選擇啟發(fā)函數(shù)為fC(i,j):

(5)

2.2 DRCM算法流程

根據(jù)DRCM算法的四個主要步驟,其具體流程描述如下:

Step1 根據(jù)原圖構(gòu)建滿足式(4)中約束條件的閉合圖。

Step2 根據(jù)啟發(fā)函數(shù)(式(5))求出完全圖的最小生成樹。

采用Prim最小生成樹算法構(gòu)造完全圖的最小生成樹。利用鏈路啟發(fā)選擇函數(shù)(式(5))查找完全圖的最小生成樹,直到所有目的節(jié)點(diǎn)都加入到多播樹中。

Step3 根據(jù)DR能力調(diào)整多播樹。

Step4 把完全圖的最小生成樹還原到原網(wǎng)絡(luò),去掉可能存在的環(huán)。

將多播樹還原到原網(wǎng)絡(luò)拓?fù)渲?去除可能存在的環(huán)路,并計(jì)算源節(jié)點(diǎn)到每個目標(biāo)節(jié)點(diǎn)的端到端時(shí)延。

由于多播樹中源節(jié)點(diǎn)到大功率葉子節(jié)點(diǎn)多播路徑的替換,使源節(jié)點(diǎn)到大功率遠(yuǎn)距離葉子節(jié)點(diǎn)的時(shí)延減小。

3 算法仿真

為了分析DRCM算法在智能電網(wǎng)多播通信中對具有較大DR能力的智能設(shè)備需求響應(yīng)時(shí)延的影響,本文通過在Matlab中建立電網(wǎng)模型,仿真實(shí)現(xiàn)了三種多播路由算法,分別是DRCM算法、KPP算法[5]和MST算法[11],并比較上述算法在以下兩方面的性能:1)比較三種算法所生成的多播樹上最大端到端時(shí)延與DR能力大小的關(guān)系;2)由于多播樹上不同DR能力的智能設(shè)備其需求響應(yīng)時(shí)延不同從而導(dǎo)致負(fù)載功率變化曲線不同,因此建立電網(wǎng)頻率控制系統(tǒng)模型,觀察不同的負(fù)載功率偏差信號對電網(wǎng)頻率波動的影響。

3.1 仿真場景及參數(shù)

本次仿真場景采用的是RT-nested-Smallworld電網(wǎng)演化模型[12],該模型具有明顯的電網(wǎng)拓?fù)涮匦院碗姎馓匦?即明顯的小世界特性、良好的連通性和可擴(kuò)展性。選取電網(wǎng)廣域控制中典型節(jié)點(diǎn)數(shù)N為300的情況[13]在Matlab中進(jìn)行仿真實(shí)驗(yàn),將節(jié)點(diǎn)隨機(jī)分布在面積為100 km×100 km的范圍內(nèi),將兩點(diǎn)間的距離作為網(wǎng)絡(luò)權(quán)值,忽略節(jié)點(diǎn)的轉(zhuǎn)發(fā)時(shí)延、排隊(duì)時(shí)延,只考慮傳播時(shí)延,根據(jù)信息的傳播速率為光速的2/3[14],可將傳播時(shí)延表示為:時(shí)延=距離(km)×5 μs,設(shè)網(wǎng)絡(luò)的費(fèi)用與距離成正比(仿真中取距離代替費(fèi)用)。根據(jù)參考文獻(xiàn)[15]可以得到如圖2所示的電網(wǎng)頻率控制系統(tǒng)框圖及各環(huán)節(jié)的參數(shù)。在Simulink中建立系統(tǒng)模型,設(shè)系統(tǒng)中有三種不同DR能力的負(fù)載,由于控制信息傳輸?shù)紻R設(shè)備存在時(shí)延,如圖2左側(cè)輸入信號,橫向?yàn)闀r(shí)延,縱向?yàn)楣β势瞀d。DRCM算法優(yōu)先響應(yīng)的是功率變化量最大的負(fù)載,即第一時(shí)刻ΔPd最大,第二、三時(shí)刻ΔPd依次遞減；反之KPP算法和MST算法優(yōu)先響應(yīng)的是功率變化量最小的負(fù)載。不同算法響應(yīng)不同DR能力負(fù)載的時(shí)延不同,導(dǎo)致功率偏差曲線ΔPd不同,因此電網(wǎng)頻率響應(yīng)的波動程度受到不同程度的影響。

圖2 電網(wǎng)頻率控制系統(tǒng)結(jié)構(gòu)

3.2 仿真結(jié)果及分析

圖4為需求側(cè)功率變化量對電網(wǎng)頻率的影響,考慮時(shí)延對需求響應(yīng)的影響,三種算法響應(yīng)不同DR能力負(fù)載時(shí)的順序不同導(dǎo)致負(fù)載功率偏差曲線不同,該圖間接反映了需求側(cè)負(fù)載響應(yīng)時(shí)延對電網(wǎng)頻率的影響。仿真進(jìn)行1 s后負(fù)載突然變化,由于電網(wǎng)中通信時(shí)延的存在,KPP算法和MST算法所生成的多播樹上,使具有較大DR能力的負(fù)載通信時(shí)延較大,因此負(fù)載偏差較大的DR后響應(yīng),從圖4可以看出其對應(yīng)的電網(wǎng)頻率曲線波動比較劇烈。本文提出的DRCM多播路由算法,由于考慮了目的節(jié)點(diǎn)的DR能力約束,對具有較大負(fù)載偏差的DR優(yōu)先響應(yīng),因此使電網(wǎng)頻率的波動大幅減小,保證了電網(wǎng)頻率的穩(wěn)定性。

圖3 最大端到端時(shí)延與DR能力關(guān)系

圖4 需求側(cè)負(fù)載的功率變化量對電網(wǎng)頻率的影響

4 結(jié)語

本文提出一種基于DR能力約束的多播路由算法,該算法將時(shí)延和多播目的節(jié)點(diǎn)DR能力作為約束條件構(gòu)造多播路由樹。仿真結(jié)果表明，該算法構(gòu)造的多播樹,能夠使DR能力大的電力用戶得到控制信息的通信時(shí)延減小,保證DR能力較大的需求側(cè)優(yōu)先對電力需求作出響應(yīng),穩(wěn)定電網(wǎng)頻率,保證電網(wǎng)的可靠性。本文通過對智能電網(wǎng)廣域控制中多播路由方式的研究來減小電網(wǎng)需求響應(yīng)時(shí)延,在后續(xù)的工作將繼續(xù)展開保證電網(wǎng)服務(wù)質(zhì)量的多播路由的研究與設(shè)計(jì)。

參考文獻(xiàn)(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] 張欽,王錫凡, 付敏, 等. 需求響應(yīng)視角下的智能電網(wǎng)[J]. 電力系統(tǒng)自動化, 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] 周振宇, 蔡驥然, 師瑞峰, 等. 智能電網(wǎng)需求響應(yīng)通信架構(gòu)綜述[J]. 電氣應(yīng)用, 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] 李元臣, 劉維群. 基于共享邊的時(shí)延約束組播路由算法[J]. 計(jì)算機(jī)應(yīng)用, 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] 劉維群, 李元臣. 時(shí)延約束的鏈路選擇平衡優(yōu)化組播路由算法[J]. 計(jì)算機(jī)應(yīng)用, 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] 余燕平, 仇佩亮. 一種時(shí)延和時(shí)延抖動受約束的啟動式多播路由算法[J]. 通信學(xué)報(bào), 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).