需求響應調度樹的構建及評價方法研究*

祁兵，劉思放，李彬，陳宋宋，董明宇，喬學明

(1.華北電力大學 電氣與電子工程學院， 北京 102206；2.中國電力科學研究院有限公司, 北京 100192；3.國網山東省電力公司， 濟南 250011)

0 引 言

隨著智能電網領域技術的迅速發展，需求響應以其較少的系統運行成本和提高電網可靠性的潛力逐漸成為研究的新熱點。我國“十三五”規劃明確提出了“優化電力需求側管理，加快智能電網建設，提高電網側與發電側和需求側交互響應能力”的目標[1]。2017年《電力需求側管理辦法》以深入推進供給側結構性改革，推動能源革命和全社會節能減排，促進電力經濟綠色發展和生態文明建設為目標，提出了進一步推進電力體制改革、實施電能替代、促進可再生能源消納并提高智能用電水平的新任務，促進供給側與需求側相互配合、協調推進，做好新形勢下電力需求側管理工作。電網側與用戶需求側通過互動進行削峰填谷，可提高用戶舒適度，同時保障電力系統的供需平衡，進而提高區域電力系統的整體運行效率。

近年來，國內外研究機構對于需求響應系統實體建模和系統設計方面技術成果較為顯著：建立可實現風能發電量跟蹤的需求響應模型[2]；對用戶的用電方案進行優化，并建立由用戶需求波動引起的成本模型[3]；基于風電消納問題，研究需求響應的調度成本的最小化模型[4]；提出自動需求響應研究框架，并設計系統的總體業務信息流程等[5]。

目前對于尋求和優化最小生成樹方面也有大量的研究工作：使用多項式時間算法找到同時向最短路徑樹和最小生成樹近似的生成樹[6]；通過延遲有限多播樹的迭代改進法構建最小成本的多播樹[7]；基于配電網架規劃問題研究高效的最小生成樹算法[8]；通過將權重聚合成為綜合指標，在最短路徑樹的基礎上搜索多播樹，提高算法的速度和準確性等[9]。

開放式自動需求響應(Open Automated Demand Response, OpenADR)是一個具有傳輸和安全機制的通信數據模型，主要為需求響應用例發出相關信號，促進供電側和用戶間的數據交互。OpenADR與設備控制系統之間進行交互是自動的，對控制系統事先完成設定的。自動需求響應這種方便快捷的特性提高了需求響應的效率，更加方便快捷。

對于電網側來說，如何合理地為用戶側調度、分配需求響應資源，使得在整個網絡中達到資源利用率的最大化，是至關重要的問題。需求響應調度可以協助優化系統的可靠性，增加峰值負荷的管理，提高系統能效。雖然國內外很多學者和研究機構對于需求響應機制和模型應用等方面進行了研究，但對于如何通過分析需求響應潛力以合理分配需求響應資源、構建調度樹還鮮有研究。本課題對于復雜網絡拓撲中需求響應如何合理高效地調度、分配需求響應資源進行研究，根據拓撲圖中鏈路的容量、物理距離等參數，構建出滿足調度需求的最小生成樹，并用不同的指標對調度樹進行評價，判斷不同算法對于實際場景是否合適。

1 基本概念及原理簡述

1.1 需求響應技術

需求響應(Demand Response，DR)是電力用戶對實施機構發布的價格信號或激勵機制做出響應，并改變電力消費模式的一種參與行為[10]。需求響應技術對于實現電力系統供需平衡和資源的優化配置、提升資源利用率等方面具有重要意義。在實施需求響應項目的過程中，電力用戶對于供電公司激勵措施的響應行為和用戶對于自身用電方式的改變所導致的負荷特性的變化是不容忽視的重要環節。

需求響應的措施根據響應信號的不同可分為兩種類型：基于激勵的需求響應(incentive-based demand response)和基于電價的需求響應(price-based demand response)[11]。基于激勵的需求響應主要是在用戶的用電高峰時期，供電側通過一些激勵機制削減參與需求響應的負荷，達到降低負荷功率峰值的目的。基于電價的需求響應是通過對峰谷尖平不同時段電價的變化來改變用戶的用電行為，刺激并鼓勵用戶主動改變電力消費模式，調整不同時段的負荷功率，以達到削峰填谷的目的。

需求響應使得供電側和用戶側的信息交互更為靈活，是重要的互動資源，智能電網為需求響應的進一步應用與實踐提供了新的發展平臺。在解決需求側管理(DSM)的相關問題時，需求響應起到至關重要的作用，它也是推動智能電網和整個電力行業發展的關鍵技術，可以給用戶帶來便利的生活體驗，也可以幫助提高電力系統運行的穩定性和可靠性，并帶來良好的經濟效益。最初，主要依靠人工方式實現需求響應，用戶手動控制設備來實現供電側與用戶側之間的信息交互。但是人工方式可靠性及有效性較差，因此需求響應的發展趨勢開始向自動需求響應進行轉變。

1.2 OpenADR中定義的調度樹

OpenADR是關于自動需求響應中通信規范問題的描述，它定義了一種通信數據模型，以及供電側和用戶側之間信息交換的標準和規范，使用戶側措施可自動完成。

OpenADR 2.0協議中規定網絡中的節點被分為兩組：負責給其他節點分發并傳送事件信息的節點，以及接收應答該信息的通信節點(例如，終端用戶)。負責分發事件信息的上游節點稱為虛擬根節點(Virtual Top Nodes，VTN)；接收信息的下游節點稱為虛擬端節點(Virtual End Nodes，VEN)。分別對應于供電側和用戶側。這些節點可以使用各種協議進行通信。他們可以以PUSH模式(VTN發起通信)或以PULL模式(VEN從VTN請求信息開始一系列消息交換)進行通信。VTN / VEN還可以通過諸如XML消息和存在協議(XMPP)的其他傳輸機制進行通信。圖1是VTN與VEN的關系示意圖，頂層VTN節點代表供電側電力公司等實體，將信息分發給VEN節點，例如聚合商，聚合商將消息分發給工商用戶、住宅用戶等VEN節點，此時聚合商就是底層VEN節點的VTN。節點的角色會隨著功能、作用的不同發生轉變。

圖1 VTN與VEN關系示意圖

只要滿足OpenADR 2.0的相關協議，就可以實現需求響應的開放化和自動化[12-13]。OpenADR基于已有的標準通信協議，利用現有的設施高效、靈活地將需求響應、價格、可靠性信息等從供電側傳送至用戶側。OpenADR的協議主要側重于信息交互，但是對于電網側應如何合理分配并調度需求響應資源、如何構建需求響應的調度樹并未提及。因此，研究需求響應調度樹的構建和評價對于電力系統資源的分配具有重要意義。

2 需求響應調度樹構建過程分析

2.1 調度樹算法概述

實際應用中通常對圖中各邊的權重值有計算要求。例如，在電路中，邊的權重可以表示通過某線路的傳輸時間、線路長度等；在通信中，網絡拓撲中各邊的權重可以表示傳輸鏈路的長度、帶寬開銷、時間等。在較為復雜的網絡拓撲中尋求需求響應資源分配和調度的最佳路徑時，通常情況下會出現求最小開銷的問題，可通過求解最小生成樹(Minimum Spanning Tree，MST)來尋找最小開銷的方案。

計算過程中使用距離作為尋求最小生成樹和最短路徑的情況有很多，但權重不一定與距離成正比，權重也可以表示鏈路的帶寬開銷、用電容量等很多變量，有時甚至是負值，與距離之間也未必有關聯。

Prim算法是對稠密圖求最小生成樹的首選算法。首先任意確定一個節點vi作為MST選定的樹的頂點，選擇另一個節點vj為MST未選定的非樹的頂點，使得(vi，vj)具有的權值最小，將這條最小交叉邊放入MST(即將非樹頂點改為樹頂點)，再從vi和vj以外的節點中，選一點與vi或vj相連，使得所得邊權值最小。重復這一過程，直至將所有點相連，所有頂點都放入了MST，就可得到連接所有頂點的MST，算法結束。

Kruskal算法與Prim算法不同，首先將連通圖中的所有邊按照權值的非減次序排列；然后取權值最小的邊為樹枝，再按排序的次序依次選取有關的邊為樹枝(但不得與已選邊形成回路)，如果有幾條滿足條件的邊權值相同則任選一條；對于有n個端點的圖直到選出n-1條樹枝，算法結束。

Kruskal算法適合求解稀疏圖的最小生成樹，Prim算法適合求解稠密圖的最小生成樹。顯然，與Prim算法相比，Kruskal算法的效率較高，原因是它的運算過程只需要對權重排序一次，而Prim算法則需要對權重排序多次。雖然Prim算法運算過程中不一定每一次都包含連通圖的所有邊，但是由于使用排序算法的效率不斷提高，這兩種算法之間的差異會越來越明顯。

在電力系統的調度網絡中，使用Kruskal算法或Prim算法固然可以通過鏈路的物理距離、容量資源等權重尋找到最小生成樹，但是這兩種算法只是考慮了網絡中求解生成樹的算法，并沒有結合需求響應業務的相關背景和節點角色，因此具有一定局限性。

2.2 基本調度樹的構建

以江蘇省蘇州供電公司的蘇州城區光纜路由規劃圖(見圖2)為例，首先以物理距離為節點之間的權重(單位：千米，km)，分別使用Prim算法和Kruskal算法在Matlab軟件中仿真，構建出滿足物理距離最小的基本調度樹并重新規劃其節點位置，結果如圖3所示。

圖2 蘇州城區光纜路由規劃圖

圖3 需求響應基本調度樹示意圖

如OpenADR通信協議中所述，在需求響應業務系統中，VEN代表與家庭各電氣負荷或商業、工業負荷相連的末端設備；VTN/VEN為需求響應聚合系統或需求響應服務系統；VTN代表供電側的需求響應自動化服務器。VTN作為服務器的角色，向VEN節點傳遞DR事件信息，VEN負責監聽DR事件，并對其作出響應，同時支持向下一級的VEN節點擴散傳播該DR事件信息，此時的VEN節點可視作新交互過程中下一級VEN節點的VTN。

在調度需求響應資源的過程中，要考慮資源調度的頻率問題。調度較為頻繁、調度潛力較大的資源，樹枝長度應該較短，屬于更上層的節點，例如商業負荷、工廠等大型工業負荷。而調度頻率較低的資源，其樹枝長度可以設計得長一些，例如小型家庭負荷。以圖3為例，節點1為根節點，如果將節點5、6、7等作為工廠負荷的節點，離根節點1距離近，調度起來很方便，適合多次調度其資源，較為合理；相反，如果將節點29、30、25等節點作為大型企業負荷，則不太合理，因為一旦5、6、7、12、13、20、24中有任何一個節點損壞，都會影響下面的29、30、25節點，從而影響整個大型企業負荷的正常工作，對其造成較大損失。

出于對網絡中線路損壞問題的考慮，可以構建一棵備用樹。當源節點VTN到目的節點VEN中有鏈路出現損壞時，可以通過備用調度樹來實現業務數據等的傳遞，不會影響需求響應業務的正常工作運行。多播樹的構建可以很好地解決通信需求的機制，容易實現資源調度的可靠性、擁塞控制和安全性等功能。

2.3 多播調度樹的構建

為了簡化問題，還以蘇州城區的網絡拓撲為例，在仿真中隨機選擇某一節點作為VTN節點，再隨機選擇若干節點作為下一級VEN節點，在整個網絡中構建出滿足備用條件的多播調度樹。實際仿真時生成了多棵調度樹，此處只舉一例說明。仿真生成的多播調度樹示例結果如圖4所示，其中隨機選擇了節點9作為源節點VTN，隨機選擇節點1、2、4、5、7、12、13、16、24、26作為目的節點，可以看出當需求響應資源從節點9要調度給下面的VTN節點時，可以分別從節點3和節點8出發，避免了當這兩條路中任何一條鏈路出現損壞時需求響應資源無法調度的問題，保障了系統的安全穩定運行。

圖4 需求響應多播調度樹示意圖

3 實驗算例分析

3.1 基于阻塞率的評價

阻塞率這一概念最早來自于通信排隊論中的話務量問題。由于多方面因素影響，電話用戶的數量通常情況下要多于所提供的鏈路數。當發出通話請求時，很可能所有的通信鏈路都處于繁忙的狀態，這種情況被稱為“阻塞”。

在道路交通問題中，容量限制是交通網絡均衡研究問題中不可忽視的因素。有研究引入容量限制的概念模擬網絡的擁擠效應和排隊現象等[14]，也有一些優化模型的目標函數問題中，引入了容量限制參數。在電力需求響應業務中，同樣要考慮容量均衡的問題。鏈路容量資源有限，隨著調度次數的增加，鏈路上的容量不斷減少，當某條鏈路上資源減少為零時，這條鏈路就不能再進行調度。鏈路的阻塞率是衡量通信網絡傳輸質量的重要參數。在計算中考慮容量均衡的限制可以提供更優化的網絡設計方案，較好地解決由于阻塞率過高導致的各種問題。

在調度需求響應資源的過程中，每條鏈路上的波長總數是有限的。對于一條鏈路來說，每調度一次，容量資源就會減少一部分。因此，當生成調度樹的數量逐漸增加時，必然會導致某些鏈路上的容量資源減少為零。在仿真的過程中，如果鏈路上容量有剩余，即都不為零時，代表可以繼續生成調度樹的進程；當有鏈路容量資源減少為零時，則無法繼續生成調度樹。本文將阻塞率定義為由于資源限制而不能繼續生成的多播樹的數量n與所要生成的多播樹總數z之間的比值，即

(1)

由物理距離和容量資源、源節點和目的節點生成距離矩陣和容量矩陣，分別以物理距離和容量資源作為鏈路的權重生成相應的調度樹。在仿真過程中，假設鏈路的容量資源為12*40，即12根光纖，每根光纖40個波長，以100為步長，一共生成5 000棵多播調度樹，統計出調度樹生成過程中由于容量限制而不能繼續生成的調度樹數量和阻塞率，引用文獻[15]中改進的Prim算法作為對比算法，計算其阻塞率，并繪制出如圖5所示的曲線對比圖。

圖5 不同調度樹的阻塞率曲線對比圖

圖中藍色和紅色曲線分別代表以鏈路資源容量和物理距離為權重的調度樹阻塞率，黑色曲線代表對比算法的調度樹阻塞率。從圖中可以看出，剛開始三種調度樹都沒有產生阻塞的情況，隨著調度樹數量的逐漸增加，開始慢慢出現阻塞。相對于容量矩陣調度樹，距離矩陣調度樹會率先產生阻塞率，在生成1 000棵樹左右就開始出現阻塞，而容量矩陣與對比算法出現阻塞較晚，在生成1 400棵樹時才開始阻塞，但是對比算法阻塞率要高于容量矩陣調度樹阻塞率。另外，在生成樹的數量相同的情況下，距離矩陣調度樹的阻塞率要大于容量矩陣阻塞率。因此可以得出，在考慮容量均衡及阻塞率的情況下，使用鏈路容量資源作為權重所構建的調度樹的優勢更加明顯，可以降低阻塞率，但是由于沒有考慮物理距離，所以可能會在調度的過程中耗費較多的距離。與文獻[15]中改進的Prim算法相比，本文容量矩陣的阻塞率較低，具有優越性。

在仿真的過程中，最終距離矩陣和容量矩陣阻塞率分別達到了約0.7、0.6的較高值，這只是為了比較極限的情況，分析調度樹的數量對阻塞率的影響而選取較大數量調度樹進行極限仿真的結果，如果取值較低，無法體現出二者之間的變化關系。實際應用中阻塞率不會達到這么高的數值。在電力系統需求響應業務的實際應用中，可以通過基于阻塞率的評價方法對鏈路的距離和容量分別分析，選擇阻塞率較低的方式構建調度樹。在整個調度網絡中，上級VTN節點將信息和資源分發給下級VEN節點，尋找到阻塞率較低的調度樹可以為用戶側合理高效地分配需求響應資源。

3.2 基于資源占用率的評價

分別以物理距離和鏈路容量資源為權重構建調度樹，通過統計生成調度樹時鏈路已經使用的資源，計算出不同調度樹的資源占用率，資源占用率定義為在構建調度樹過程中已使用的資源容量與總資源容量的比值。

在仿真過程中，同樣假設鏈路的容量資源為12*40，代表12根光纖，每根光纖40個波長，以100為步長，一共生成5 000棵多播調度樹，由計算出的資源占用率繪制出如圖6所示的曲線圖。

圖6 不同調度樹的資源占用率曲線對比圖

從圖中可以看出，隨著調度樹數量的增加，三種種調度樹的資源占用率都先大幅度增加，當數量達到1 500左右時，距離矩陣調度樹資源占用率的增長速度慢慢減小，另外可以看出由鏈路容量矩陣構建的調度樹開始時資源占用率略高于由物理距離構建的調度樹，但二者很相近，當樹的數量逐漸增加至1 000棵以上時，由容量矩陣構建的調度樹資源占用率還繼續大幅提高，所以其資源占用率要逐漸超過距離矩陣調度樹，在1 800棵左右容量矩陣調度樹資源占用率的增長速度開始降低，但最終其資源占用率仍高于距離矩陣調度樹。對比算法的資源占用率始終高于文中提出的距離矩陣與容量矩陣構建的調度樹的資源占用率。相比之下，本文方法具有合理性和優越性。通過選擇鏈路的物理距離來構建時，在相同條件下可以降低資源占用率，節約鏈路資源。在電力需求響應網絡中，達到相同目標的條件下，可以使用此評價指標選擇資源占用率較小的鏈路，以節約需求響應資源。

3.3 累積分布分析

累積分布函數(Cumulative Distribution Function)可完整描述一個實數隨機變量的概率分布，是概率密度函數的積分，定義為對于連續函數，所有小于等于a的值，其出現概率的和，即：

F(a)=P(x≤a)

(2)

在仿真過程中，我們假定到達多播請求服從泊松分布，到達率是β。連接保持時間服從均值為1/μ的指數分布。因此，多播網絡負載是β/μ。整個網絡的負載是多播請求與單播請求的結合。定義R代表多播請求百分比，即多播請求占總請求的百分比。假定多播目的節點的數量服從參數為q的截斷幾何分布。包含x個節點的多播請求百分比在式(3)中給出。

(3)

對組播業務的有效輸入負載、有效單播業務負載和有效總業務負載如下所示。

ρ1=λμRE(x)

(4)

ρ2=λμ(1-R)

(5)

ρ=λμ[RE(x)+(1-R)]

(6)

參數r是多播業務有效負載率，定義如下：

(7)

文獻[16]中對多播業務有效負載率r與多播請求百分比R之間的關系進行了分析。分析結果顯示，多播的目的節點越多，多播的有效負載也越多，多播流量負載與目的節點數量成正比。但是，當多播請求百分比R增加到一定值時，多播有效負載r幾乎不增加，原因是過多的多播目的節點導致網絡擁塞，阻止了大部分多播請求。

選取具有代表性的兩個q的值，觀察多播樹不同趨勢的累積分布圖。圖7是生成5 000棵樹時，參數q=0.68時的多播樹累積分布圖，橫軸代表目的節點的數量，縱軸代表對應的生成調度樹的數量占總數的頻率。從圖中可以看出，隨著目的節點樹的增加，對應調度樹的頻率減少較多。

圖7 q=0.68時不同目的節點多播樹累積分布圖

圖8是生成5 000棵樹時，參數q=0.98時的多播樹累積分布圖。可以看出，參數q增加，隨著目的節點數的增加，同一節點數對應生成的調度樹的頻率分布更加均勻，但總體呈現下降趨勢。可以明顯看出q的值較大時，不同目的節點多播樹的數量比例更加接近。通過調節q的值來選擇多播目的節點的個數，控制可以生成的調度樹數量，從而改變多播樹的頻率分布。當調用大工業需求響應資源參與需求響應時，可以使q取較小值，因為大工業用戶的負荷量大，需求響應潛力大，在完成一次需求響應過程中，可能只需調用較少的用戶就能達到響應目標。當調用居民用戶和小型商業DR資源執行需求響應事件時，由于目標群體眾多而且分散，此時可以使q取較大值以便調用更多的小型分散式負荷參與需求響應，并且還有有利于保證參與DR的公平性。此外，在網絡資源緊張時，可以增大q值以增加多播樹平均目的節點數，從而使平均每棵多播樹調用的DR資源量增加，由于總的DR任務量是確定的，這樣就減少了DR樹的數量，節約了網絡資源，降低了網絡的阻塞。

圖8 q=0.98不同目的節點多播樹累積分布圖

在實際的電力需求響應業務網中，不僅要考慮阻塞率，更要考慮同等條件下對資源的資源占用率，綜合考慮多個評價指標，以選擇最合理優化的調度方式。供電側可以綜合使用不同的評價指標開發相應的調度系統和設備，在向用戶側分發需求響應資源時，選擇指標更好的鏈路，以優化系統可靠性，提高系統能效。

4 結束語

需求響應是智能電網的核心技術之一，智能電網的飛速發展為充分發揮需求響應資源提供了強大的技術支撐。在電力系統網絡中，對于需求響應資源的調度和分配就尤為重要。本文從自動需求響應通信規約和最小生成樹的傳統算法出發，重點研究了如何在復雜網絡拓撲中根據鏈路容量或物理距離等權重構建基本和多播調度樹，繪制出多棵調度樹構建過程中的評價指標變化曲線圖，并從阻塞率、資源占用率、累積分布函數等方面對構建的需求響應調度樹進行評價分析，并與改進的Prim算法進行對比，驗證了本文評價方法的合理性和優越性。但是，本文的課題研究還停留在理論層面，在電力系統網絡的需求響應資源調度實際應用方面，還有待進一步研究與實踐。