基于電網的采樣感知加權循環調度算法

譚鑫 李曉卉 劉振興 丁月民 趙敏 王琦

摘 要：針對智能電網相量測量設備競爭使用有限的網絡通信資源時，會因資源分配不均而導致數據包延時或丟失，進而影響電力系統狀態估計的精度這一問題，提出了一種采樣感知加權循環（SAWRR）調度算法。首先根據電網相量測量單元（PMU）采樣頻率和數據包大小的特性，提出了基于PMU業務流均方差的權重定義方法;然后設計了相應的PMU采樣感知迭代循環調度算法;最后將該算法運用到PMU采樣傳輸模型中。該算法能自適應地感知PMU的采樣變化，及時調整數據包的傳輸。仿真結果表明，與原始的加權循環調度算法相比，SAWRR算法減少了95%的PMU采樣數據包的調度時延，降低了一半的丟包率，增加了兩倍的吞吐量。將SAWRR算法運用到PMU數據傳輸中有利于保證智能電網的穩定性。

關鍵詞：智能電網;相量測量;調度算法;權重;采樣

Abstract： When the smart grid phasor measurement equipment competes for limited network communication resources， the data packets will be delayed or lost due to uneven resource allocation， which will affect the accuracy of power system state estimation. To solve this problem， a Sampling Awareness Weighted Round Robin （SAWRR） scheduling algorithm was proposed. Firstly， according to the characteristics of Phasor Measurement Unit （PMU） sampling frequency and packet size， a weight definition method based on mean square deviation of PMU traffic flow was proposed. Secondly， the corresponding iterative loop scheduling algorithm was designed for PMU sampling awareness. Finally， the algorithm was applied to the PMU sampling transmission model. The proposed algorithm was able to adaptively sense the sampling changes of PMU and adjust the transmission of data packets in time. The simulation results show that compared with original weighted round robin scheduling algorithm， SAWRR algorithm reduces the scheduling delay of PMU sampling data packet by 95%， halves the packet loss rate and increases the throughput by two times. Applying SAWRR algorithm to PMU data transmission is beneficial to ensure the stability of smart grid.

Key words： smart grid; phasor measurement; scheduling algorithm; weight; sampling

0 引言

隨著智能電網（Smart Grid）快速發展，如何保證其運行的穩定性和高效性是近年來研究重點。電網廣域監測系統（Wide Area Measurement System， WAMS），通過在電網關鍵測點布局基于全球定位系統（Global Positioning System， GPS）的同步相量測量單元（Phasor Measurement Unit， PMU），實現對電網運行主要監測數據的實時高速率采集，并通過通信網絡實時傳送到廣域監測主站系統，從而提供對智能電網正常運行與事故擾動情況下的實時監測與分析計算，及時獲得并掌握電網運行的動態過程，為智能電網提供監測、保護和控制之用，因此PMU與主站系統之間數據傳輸的高效性、完整性和及時性，是實現智能電網系統穩定性的重要保證[1-2]。

由于WAMS中有大量的PMU同步采樣實測數據[3]需要傳送，為了保證電網監測的完備性和數據的高效性，近幾年來，不少學者在PMU的布局和數據預處理上進行研究，并取得了顯著效果。文獻[4]中提出了最優PMU通信鏈路布局（Optimal PMU-communication Link Placement， OPLP），與傳統的最優PMU布局模型相比，OPLP可以顯著降低總安裝成本;文獻[5]中提出一種線性迭代算法搜索滿足給定的同步相量可用性分布的最小數量的PMU的放置;文獻[6]中利用PMU數據中的固有相關性，利用空間和時間冗余，提出了一種兩階段壓縮算法，減少物理存儲器需求;文獻[7]中提出一種實時數據壓縮和適用于WAMS的IEEE C37.118協議技術，該壓縮改進協議技術可以在動態和穩定狀態下高精度地將數據包大小減小大約75%;然而，隨著智能電網的不斷普及發展，電網PMU的數量不斷增加，在網絡帶寬有限的條件下，主站系統通過WAMS接收PMU數據時，如何設計一種公平的調度算法，以實現對不同采樣頻率的PMU的數據流提供實時的調度越來越引起人們的關注[8-9]。

針對這個問題，本文將PMU采樣特性和調度算法相結合提出了一種基于采樣感知的加權循環（Sampling Awareness Weighted Round Robin， SAWRR）算法。該算法是根據每個PMU采樣頻率、包的大小和加權循環（Weighted Round Robin，WRR）權重來確定每個PMU的權重。通過對SAWRR算法和WRR算法進行仿真分析，結果表明SAWRR算法在平均時延、丟包率和吞吐量等性能上都要優于WRR算法。

1 WAMS結構及調度算法

1.1 WAMS結構

WAMS結構如圖1所示，其基本組件是PMU和主站系統以及聯系兩者的廣域網（Wide Area Network， WAN）[10-11]。PMU是一個通過GPS信號同步采樣電流電壓測量數據并提供相位、幅值和頻率信息的設備[12]。主站收集來自不同PMU的測量值，對其進行時間校準后，送往控制中心用于電力系統的狀態估計、動態監測和暫態穩定性分析。

由圖1可知，多個PMU將收集到的數據通過WAN傳輸給主站，主站間存在交換PMU數據的需求。未來隨著智能電網的不斷發展，WAMS中PMU的數量也會隨之增長。如果為新增的PMU不斷增加新的網絡通信資源是不現實的。不同采樣頻率的PMU競爭使用有限的網絡通信資源進行傳輸時，可能因為資源分配不均而導致部分PMU因缺乏網絡傳輸資源而引發時延的增加和大量丟包。PMU測量值的缺失，會導致主站對電力系統狀態估計的精度降低，不利于對電網進行相關的保護、檢測和控制，進而影響電網的穩定性。

為了解決上述WAMS中為PMU均衡分配網絡通信資源的問題，需要在主站系統中引入調度算法合理均衡地為PMU分配網絡通信資源，減小PMU數據傳輸的時延和丟包率。

1.2 調度算法

目前已經存在一些經典的調度算法：先進先出（First In First Out， FIFO）、輪詢調度（Round Robin， RR）[13-14]、加權循環（WRR）算法[15]等。在眾多算法中，WRR算法由于引入權重來合理分配網絡資源，其在調度的實時性和丟包率上的性能相對較好。

WRR算法為每個隊列賦予一個權值，并設置相關的權重計數器。在進行調度前，將權重分配給對應的計數器，該計數器指定一輪中對應隊列傳輸的數據包數量。如果一個隊列發送一個數據包，則該隊列權重計數器減1。繼續發送數據包，直到計數器達到零或者隊列為空。最后，所有隊列計數器都重置為其權重值。

當在WAMS中引入調度算法合理均衡地為PMU分配網絡通信資源時，有兩個特性是調度的依據：PMU采樣頻率和2）PMU數據包的大小，因此在網絡資源有限的情況下，如何根據以上兩個特性合理設計調度算法是本文的重點。

2 SAWRR算法

結合WAMS中PMU采樣頻率和數據包大小特性，本文提出了一種基于采樣感知的加權循環調度算法SAWRR。

2.1 權重的設計

在WAMS中，PMU收集并傳輸實時廣域同步數據，它的采樣頻率基本在50到150之間，其數據用于監測電力系統的動態安全性。由于PMU的采樣頻率會影響數據傳輸的效率，而在WRR算法中權重的確定尤為重要，所以通過采樣頻率來計算權重，能夠對PMU的數據進行比較好的調度。

其中：Wi是隊列i的WRR權重，samplei是隊列i的采樣頻率，N是總的隊列數。在WAMS中，WRR算法會造成隊列中多個數據包延遲。在隊列長度有限的情況下，累計延遲的數據包會溢出隊列，最終會導致數據包丟失。

如圖2所示，在權重為3的情況下對4個隊列q1、q2、q3和q4進行一輪調度時，虛線框表示被調度送出隊列的數據包，實線框表示隊列中剩余的數據包。其中，隊列q1剩余數據包量最多。隨著PMU采樣的數據包不斷進入隊列和WRR調度的持續，q1的滯留數據包增加，其調度時延也相應增加，隊列最終因延遲數據包累計而裝滿，導致數據包丟失。

為了解決電網中調度的上述問題，需要結合采樣頻率和數據包大小重新定義權重。該權重計算主要有以下兩個步驟：

第一步 多個PMU業務流量歸一化。根據PMU采樣數據包來確定當前多個PMU業務流量的均方差，以判定當前多個PMU業務流的離散程度。

假設每輪進隊列i的標準數據包大小為size_standardi，業務流為traffici，則：

第二步 確定新權重wi。由第一步可知β值越大說明當前多個PMU業務流差異比較大，多個業務流的調度權重也要相應調整，此時需將帶寬劃分的模塊減小，資源分配才越均衡; β值越小說明當前多個PMU業務流差異較小，業務流量較均衡，多個業務流的調度權重也應接近;但當β<1時，需要加1避免產生大的量化誤差[16]，因此權重調整系數ωi可以定義如下：

然后通過系數ωi來調整當前權重，為每個隊列產生適當的權重：

2.2 SAWRR算法

根據上面權重，設計SAWRR算法。算法偽代碼如下。

步驟1 參數初始化。

定義隊列數量n，第k輪隊列i的數據包數為qi，k，隊列i的權重為wi，隊列i的權重計數器為WCi，循環輪數k，最大循環輪數k_max。

步驟2 進行隊列數據包的調度。

先確定隊列是否為空，如果不為空，則根據式（6）確定wi，將每個隊列的權重賦給對應的計數器，如果一個隊列發送一個數據包，則該隊列權重計數器減1。繼續發送數據包，直到計數器達到零或者隊列為空。然后將計數器重置為對應的隊列權重值，重復上述過程，直到隊列為空。

當PMU的采樣頻率或者包的大小發生改變，由于式（6）的迭代計算，該算法可以根據PMU當前的采樣來計算權重，因此，SAWWR算法可以自適應地感知PMU的采樣變化，及時根據PMU新的采樣頻率和數據包大小調整調度算法中的權重。通過在圖1的主站運行SAWRR調度算法，可以達到減少PMU采樣數據包的排隊時延。

表1顯示的是基于圖2中隊列計算SAWRR算法的權重。

將表1中計算的權重用到圖2的隊列中進行調度，可以發現，與圖2中運用WRR算法相比，SAWRR算法將延遲數據包的總數從6減小到0，傳輸效率明顯提高。

3 仿真結果分析

為了分析SAWRR算法在智能電網PMU數據傳輸中對數據傳輸的高效性、完整性和及時性的影響，本文通過在Matlab中建立傳輸調度模型，仿真實現了SAWRR算法、WRR算法，并比較了上述算法在不同的PMU的數目下平均時延、丟包率、吞吐量三個方面的性能。根據電網WAMS中PMU采樣頻率和采樣數據包大小，在仿真中PMU采樣頻率為50～150次/s隨機分布，PMU采樣數據包大小為60～80B隨機分布。

圖3顯示了SAWRR算法相對WRR算法時延減少率。從圖中可以看出，SAWRR算法的調度時延相對WRR算法減小少了95%左右。在PMU數目相同的情況下，SAWRR的權重是根據PMU采樣頻率和采樣數據包大小確定的，通過SAWRR算法調度每輪輸出的數據包數量比用WRR算法調度的多，數據包能夠更快地被傳輸，因此通過SAWRR算法調度數據包的時延要比用WRR算法調度的時延小。

圖4顯示了兩種調度算法下的丟包率的比較。從圖中可以看出來，隨著PMU數量增加，兩個算法的丟包率都不會發生明顯的變化，調度的穩定性較好;然而，SAWRR算法丟包率要低于WRR算法。在相同數目PMU的情況下，由于SAWRR可以自適應感知PMU采樣變化而調整權重，所以用SAWRR算法調度時滯留的數據包較少，因隊列緩存滿而溢出丟包的情況也隨之減少。

圖5顯示了SAWRR算法相對WRR算法吞吐量增加率。從圖中可以看出來，通過SAWRR算法調度PMU數據包的吞吐量相比用WRR算法調度的吞吐量增加了210%左右。在相同數目PMU的情況下，因為每輪SAWRR算法傳輸的數據包比用WRR算法多，所以SAWRR算法的總吞吐量要比WRR算法多。

4 結語

本文針對WAMS中不同采樣頻率的PMU競爭使用有限的網絡通信資源可能存在不均衡的問題，提出了一種基于電網PMU采樣感知的SAWRR調度算法。該算法結合了PMU的采樣頻率和數據包大小兩個特性定義了循環調度的權重，使調度的數據包得到高效的傳輸。由于權重的迭代計算，該算法可以自適應感知PMU采樣變化，及時調整數據包傳輸。仿真結果表明，將SAWRR算法運用到PMU中數據包的傳輸中，能夠增大數據包的吞吐量，減小數據包的時延和丟包率，從而保證數據傳輸的高效性、完整性和及時性，有利于智能電網的穩定性。在后續工作中將繼續展開保證電網中數據高效傳輸的研究和設計。

參考文獻 （References）

[1] 謝小榮，辛耀中.基于同步相量測量技術的廣域測量系統應用現狀及發展前景[J].電網技術，2005，29（2）：44-49.（XIE X R， XIN Y Z. Present application situation and development tendency of synchronous phasor measurement technology based wide area measurement system[J]. Power System Technology， 2005， 29（2）： 44-49.）

[2] 張恒旭，靳宗帥，劉玉田.輕型廣域測量系統及其在中國的應用[J].電力系統自動化，2014，38（22）：85-90.（ZHANG H X， JIN Z S， LIU Y T. Wide-area measurement system light and its application in China[J]. Automation of Electric Power Systems， 2014， 38（22）： 85-90.）

[3] ARAVIND M N， ANJU L S， SUNITHA R. Application of compressed sampling to overcome big data issues in synchrophasors[C]// Proceedings of the 2016 IEEE 6th International Conference on Power Systems. Piscataway， NJ： IEEE， 2016： 1-5.

[4] ZHU X， WEN M H F， LI V O K， et al. Optimal PMU-communication link placement for smart grid wide-area measurement systems[J]. IEEE Transactions on Smart Grid， 2018， 10（4）： 4446-4456.

[5] SARAILOO M， WU N E. A new PMU placement algorithm to meet a specified synchrophasor availability[C]// Proceedings of the 2016 Innovative Smart Grid Technologies Conference. Piscataway， NJ： IEEE， 2016： 1-5.

[6] GADDE P H， BISWAL M， BRAHMA S， et al. Efficient compression of PMU data in WAMS[J]. IEEE Transactions on Smart Grid， 2016， 7（5）： 2406-2413.

[7] ZHANG F， CHENG L， LI X， et al. Application of a real-time data compression and adapted protocol technique for WAMS[J]. IEEE Transactions on Power Systems， 2015， 30（2）： 653-662.

[8] 鮑興川，彭林.智能配電網通信多信道調度策略[J].計算機應用，2018，38（5）：1476-1480.（BAO X C， PENG L. Multi-channel scheduling strategy in smart distribution network[J]. Journal of Computer Applications， 2018， 38（5）： 1476-1480.）

[9] 向敏，陳誠.基于改進Dijkstra算法的配用電通信網流量調度策略[J].計算機應用，2018，38（6）：1715-1720.（XIANG M， CHEN C. Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network[J]. Journal of Computer Applications， 2018， 38（6）： 1715-1720.）

[10] 薛禹勝，徐偉，DONG Z，等.關于廣域測量系統及廣域控制保護系統的評述[J].電力系統自動化，2007，31（15）：1-5.（XUE Y S， XU W， DONG Z， et al. A review of wide area measurement system and wide area control system[J]. Automation of Electric Power Systems， 2007， 31（15）： 1-5.）

[11] 鞠平.電力系統廣域測量技術[M].北京：機械工業出版社，2008：9-24補充頁碼范圍.（JU P. Power System Wide Area Measurement Technology[M]. Beijing： China Machine Press， 2008： 9-24.）

[12] 竇開明，祝鑫，馬夢宇，等.IEEE同步相量相關標準的發展與比較[J].電氣應用，2018，37（6）：41-45.（DOU K M， ZHU X， MA M Y， et al. Development and comparison of IEEE synchronous phasor related standards[J]. Electrotechnical Application， 2018， 37（6）： 41-45.）

[13] HAHNE E L. Round-robin scheduling for max-min fairness in data networks[J]. IEEE Journal on Selected Areas in Communications， 1991， 9（7）： 1024-1039.

[14] SHREEDHAR M， VARGHESE G. Efficient fair queuing using deficit round-robin [J]. IEEE/ACM Transactions on Networking， 1996， 4（3）： 375-385.

[15] KATEVENIS M， SIDIROPOULOS S， COURCOUBETIS C. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[J]. IEEE Journal on Selected Areas in Communications， 1991， 9（8）： 1265-1279.

[16] ITO Y， TASAKA S， ISHIBASHI Y. Variably weighted round robin queueing for core IP routers[C]// Proceedings of the 21st IEEE International Performance， Computing， and Communications Conference. Washington， DC： IEEE Computer Society， 2002： 159-166.