龍 丹,李曉卉,丁月民

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

0 引言

智能電網(wǎng)(Smart Grid, SG)是當今備受關(guān)注的研究領(lǐng)域,其穩(wěn)定高效運行有利于經(jīng)濟的可持續(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]的通信具備較短的時延,以保證電網(wǎng)頻率的穩(wěn)定和電力控制的可靠性。

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

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

為了解決上述問題,本文提出一種綜合考慮DR能力和通信時延約束的多播路由樹構(gòu)造方法——基于DR能力約束的多播路由(Demand Response capability Constrained Multicast routing,DRCM)算法。該算法將時延和多播目的節(jié)點DR能力作為約束條件構(gòu)造多播路由樹。仿真結(jié)果表明該算法能夠使DR能力大的電力用戶得到控制信息的通信時延減小,保證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)來實現(xiàn)智能電網(wǎng)與電力用戶之間的電力供求信息互動。需求響應(yīng)可以有效、及時且準確地傳遞電力成本和需求信息,有助于電力需求側(cè)與供應(yīng)方之間保持電力實時平衡。

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

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

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

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

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

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

pk=wk/dk

(1)

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

(2)

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

(3)

(4)

2 DRCM多播路由算法

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

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

為了使到目的節(jié)點時延短且費用小的鏈路加入到多播樹,定義了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é)點都加入到多播樹中。

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

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

將多播樹還原到原網(wǎng)絡(luò)拓撲中,去除可能存在的環(huán)路,并計算源節(jié)點到每個目標節(jié)點的端到端時延。

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

3 算法仿真

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻(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] 李元臣, 劉維群. 基于共享邊的時延約束組播路由算法[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] 劉維群, 李元臣. 時延約束的鏈路選擇平衡優(yōu)化組播路由算法[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] 余燕平, 仇佩亮. 一種時延和時延抖動受約束的啟動式多播路由算法[J]. 通信學(xué)報, 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).