基于多智能體混合調度的電網自愈系統

王娟娟 王宏安

1(中國科學院軟件研究所 北京 100190)

2(中國科學院大學 北京 100049)

(wjuanj89@126.com)

隨著智能電網、信息技術和新能源技術的飛速發展，風電、光伏等可再生能源的迅速建設以及電動汽車等儲能設備的快速出現，傳統電網的“源-網-荷”三個固化環節正在向“源-網-荷-儲”互動協調的智慧能源新型運營模型進行轉變[1].能源互聯網的提出，強有力地推動了新能源革命的發展.能源互聯網以智能電網為基礎，將不同種類的電力網絡(如火電、核電、風電等)、能源網絡(如天然氣管網、熱力管網等)、信息網絡(如互聯網、物聯網等)、交通網絡等多種類型網絡進行融合，實現了多種能源形態協同轉化、集中式與分布式能源協調運行的超大規模復雜網絡[2].因此，能源互聯網具有3個特點：

1) 彈性發電、優質供應.能源互聯網需要盡可能以可再生能源替代傳統能源，并以需求為向導，通過智能化管理實現按需供電、階梯電價.

2) 多能融合、雙向流動.能源互聯網能夠對不同形式的能源進行高效協同，將太陽能、核能、化學能與常規能源進行轉換和存儲，減少棄風、棄水、棄光等棄網問題，實現能源的最佳使用.

3) 高度自治、實時動態.以微網為代表的分布式發配電系統將成為電力網絡的關鍵節點，減少了輸配電能量損耗，提升冗余電力備份.同時，以電動汽車為代表的大量移動、小型儲能設備的接入，使電網具有較強的供需雙側隨機性變化.

可以看出，能源互聯網的正常運行涉及到電力、物流、計算機網絡等多種知識領域，需要極高的自動化、智能化的管理和調度系統.同時，能源互聯網是多種網絡的融合，必然存在“遺傳”的安全漏洞.一旦遭受攻擊，后果不堪設想.文獻[3]已經在傳統電力網絡中闡述了自愈系統相關概念和主體結構.自愈系統在電網正常運行時以預防為目標，及時發現、診斷和消除故障；在電網發生故障時，進行自動修復.但該文并未提出自愈系統的具體軟件設計架構和關鍵技術實現方式.隨著電網技術的不斷進步，智能電網中的自愈系統需要進一步考慮分布式發電設備、電動汽車等對電網造成影響.類似地，能源互聯網新增的多種能源轉換、多種網絡融合及客戶體驗提升等需求，給其自愈系統帶來了更多的挑戰性，具體表現在3個方面：

1) 智能化程度要求更高.能源互聯網日常運營涉及多種知識領域，其安全操作已逐步不能滿足于手工操作、程序化操作.自愈系統必須內置覆蓋多領域的專家系統，能夠根據當前狀態自動進行安全操作.

2) 安全性要求更高.能源互聯網本質上是安全攸關系統[4]，不論是日常操作還是應急故障處理，都必然進行大量甚至海量的安全操作.這些安全操作將在不同的節點、不同設備上執行，并且其次序和執行時間有著嚴格的規定.一旦指令在錯誤的設備上執行、在錯誤的時刻執行、執行時間超長、執行次序錯誤都可能帶來嚴重的故障，造成巨大的損失.

3) 實時性要求更高.能源互聯網需要在廣域地域內，對多種行業領域、海量個體設備進行狀態監控，并通過高速網絡進行信息采集和指令下發.同時，能源互聯網需要對各種設備進行“開關”、“增減”、“并串”等物理操作，每一個操作都有相應的時間長度.因此，在自愈系統對突發情況進行緊急處置的時候，其自動執行修復操作序列必須根據當前的故障狀態、信息網絡狀態、設備狀態等多種狀態才能形成真正有效的方案.如某個設備與自愈系統控制中心的通信鏈路網絡擁塞，指令無法及時下發和執行，則整個修復操作序列是無效方案.

因此，在能源互聯網中的自愈系統，必須能夠在全局時空范圍內，對網絡節點、網絡設備狀態進行實時的狀態采集，并根據物理設備的特性、地域的特性、信息網絡的特性，通過智能化的專家系統綜合考慮、進行決策.本文針對能源互聯網和給電網自愈系統的安全需求和截止期限，給出了一套初步的解決方案.主要貢獻有3點:

1) 我們提出了一種帶有截止期實時約束的電網自愈系統基于多智能體進行處理的機制和可供參考的軟件實現架構.在系統中加入了帶有截止期約束的故障鏈和安全操作樹，以在一個完整調度周期內求解出有效的修復解決方案，并且以總修復時間最短、持續的故障鏈長度最短為目標，以遍布電網中的多智能體為控制手段，對能源互聯網故障進行緊急處置.

2) 針對具有實時截止期約束條件下的安全操作序列求解問題，提出了一種基于多智能體的混合關鍵性調度任務模型.當故障發生并將信息傳遞到自愈系統控制中心時，故障鏈節點將被激活.在其對應的安全操作樹(即解決故障的操作方法集合)中，根據物理設備、網絡狀況、地域分布等多種特性，求解有效的安全操作序列.此后，系統會下發有效安全操作序列到關鍵節點中駐留的智能體代理，讓這些代理去執行這些安全操作.如果在其截止期實時約束之內能夠完成執行，后續可能產生的故障將被避免.

3) 本文給出了電網自愈多智能體進行混合調度的方法，給出了優化目標和約束條件，用混合整數線性規劃(MILP)模型求解；并通過仿真結果驗證了智能電網自愈多智能體混合關鍵性調度方法有效地增加了故障結點安全操作處理的成功率(平均17.74%)，并減少了故障鏈式的后續觸發率(平均7.72%).

1 相關概念

1.1 能源互聯網的基本概念

能源和環保是人類生存和發展的兩大主題，也是相互影響和相互制約的矛盾.隨著“霧霾”、“酸雨”等環境污染問題的不斷加劇，以石油和煤炭為核心的化石能源時代必須進行改變，形成了以互聯網技術為核心、以新能源和化石能源為互補的“能源互聯網時代[5]”.能源互聯網將以可再生能源為主要能量供應方式，通過互聯網技術實現能量流與信息流實時流動，多種能源供應、傳輸網絡及能源技術、信息技術高度耦合的新型能源利用體系[6].

可以看出，與傳統電網、智能電網有所不同，能源互聯網將匯聚“火電”、“水電”、“核電”、“風電”、“光伏”多種能量的相互轉化，并以互聯網技術為基礎、以電力系統為中心，將電力系統與天然氣網絡、供熱網絡以及工業、交通、建筑系統等緊密耦合，橫向實現電、氣、熱、可再生能源等“多源互補”，縱向實現“源-網-荷-儲”各環節高度協調.可以預計，能源互聯網將對電力、運輸、信息[7]等諸多方面產生深遠的影響.

能源互聯網覆蓋的地域如此之廣、能源類型如此之多、網絡規模如此之復雜，如何通過自動化、智能化的系統，在全網范圍內構建能夠快速自我修復的電網自愈系統，就變得更加重要.

1.2 能源互聯網中的智能化自愈系統

自愈系統能夠在日常運行過程中，實現自我控制、預防和故障恢復的功能.電網自愈系統是對電網的各個關鍵節點、核心設備中的運行狀態進行實時的監視和測量，能夠快速準確地評估當前的健康狀態，選取恰當的控制策略并進行有效執行.當電網經受擾動或故障時，自愈系統將自動進行故障檢測、隔離、恢復供電來進行自我修復.文獻[8]提出了電網自愈控制系統分模塊的設計方案及自愈時間、自愈率等評價指標.但是，該文僅僅是“記錄”電網從發出警報信號到自愈完成的時間長度，并未在系統中引入與自愈修復動作相關的時間約束和次序約束.

能源互聯網電網的自愈系統是在日常運行過程中能夠維持能源互聯網橫向能源轉換和縱向“源-網-荷-儲”配電的正常運行，同時盡量提升可再生能源和清潔能源的能效，實現低成本運行.當發生故障時，將根據故障發生的原因找到備選的解決方案，并根據當前設備的物理狀態求解出有效的安全操作序列，并進行執行.自愈系統將通過部署在全網范圍的智能硬件設備和軟件代理，對全網進行實時不間斷監測和數據上傳，并對數據進行分析，不斷預測和判斷當前能源互聯網的運行狀態，調用和能源互聯網相關的一切可用資源，及時發現和排除故障.

1.3 多智能體的基本概念

由于能源互聯網本身的復雜性和多知識領域相互交織，因此，僅僅采用人工的方式進行調度和修復時無法滿足電網自愈的要求；同時，能源互聯網還具有分布式[9]、自管理的特性，在電網發生故障時，有可能在局部上具有能夠完成電網自愈的資源和能力.

多智能體系統由多個可以既彼此獨立又可以相互協作的智能體組成.其中，智能體具有自治性、交互性、協作性、主動性等特點.在多智能體系統中，智能體可以根據自己的目標，結合已有的知識，規劃出需要采取的行為，并通過與其他智能體的通信協商來完成某項特定的任務[10].多智能體技術可以通過智能體間協作解決單個智能體無法獨立完成的復雜任務，提高了系統解決問題的能力.目前多智能體技術已經廣泛應用于工業制造、交通控制、智能機器人、面向智能體軟件開發等領域[11].

隨著技術的發展，針對不同領域的多智能體系統越來越多，因此，用多智能體系統構建電網自愈系統在技術上是可行的，而且在智能電網中基于多智能體構建電網自愈系統已有相應的設計和實現.文獻[12]考慮微網接入對配電網的影響，提出了“2-3-10”的自愈控制網絡架構結構，并進行了自愈控制的仿真，能夠使配電網保持在經濟運行狀態，并提供良好質量的電能.該文雖然給出了基于智能體的電網自愈系統軟件實現架構，并引入了實時預測模塊，在當前時刻對下一個時間周期的電網負荷進行預測，但是，并未考慮到在電網故障已經出現時且對修復時間有強制性要求時，如何進行快速修復.文獻[13]提出了基于多智能體的智能配電網分層保護思路，并且融入了免疫算法，完成電網的自愈控制.該文的配電系統是一個網絡結構，通過轉為關聯矩陣并進行矩陣運算，實現故障的隔離.但是，該文是通過將物理節點抽象為節點模型并進行故障識別運算的，考慮到了空間受限的問題，但未引入受限于操作時間、操作序列固定的修復動作的計算和編排.

但是，在能源互聯網中這種安全攸關的領域中，電網自愈系統對操作時間的要求十分嚴格.一個小小的時延可能會造成重大的災難.目前，雖然已經有不少成熟的多智能體平臺被不斷設計與開發，如JADE，Mobile-C，JACK等，但是這些平臺并沒有提供對實時的支持，無法保障電網內任務的實時約束.能源互聯網的日常維護需要進行大量甚至海量的安全操作，這些安全操作將在不同地域、不同設備上執行，并且其次序和執行時間有著嚴格的規定.

目前，只有少數研究針對多智能體平臺提出了實時性方面的改進，如設計實時多智能體平臺的體系結構以優化平臺內任務的響應時間、為平臺中任務引入截止期屬性使任務盡可能在截止期內完成等.然而這些工作都無法對任務的響應時間進行預測，也就無法保證任務的截止期約束，從而限制了多智能體平臺在實時領域的應用.更進一步地，基于多智能體平臺，如何實現在操作時間受限、操作序列受限的硬實時環境下進行規則調度，保證在事故截止期到達前完成全部安全操作序列，防止事故的進一步惡化是一個新的問題，并逐步成為當前實時調度領域的研究熱點.

隨著智能電網系統或能源互聯網的日趨復雜，電網安全操作越來越涉及多知識領域的交織，本文提出電網自愈多智能體混合實時調度方法，對電網自愈過程中的安全運行和故障處理提出減少后繼故障的實時性需求，要求在此過程中同時滿足保證不同關鍵性的故障鏈截止期和安全操作樹截止期.

2 多智能混合實時電網自愈系統的框架設計

2.1 能源互聯網中對多智能體電網自愈系統的需求

圖1展示了能源互聯網主要運行模式，能源互聯網在“源-網-荷-儲”之間有著緊密的合作和銜接；同時，自愈系統在全網范圍內通過物聯網[14]技術，對“源-網-荷-儲”系統進行實時監控，并通過遍布全網關鍵節點的智能體進行信息采集和設備操控.

Fig. 1 The concept of energy Internet圖1 能源互聯網的概念圖

能源互聯網的自愈系統日常運行的內容包括：

1) 多種能源的轉換控制.自愈系統將通過發電廠與清潔能源進行不同時間段、不同地域的協調互補；同時，不同能源還能夠通過能量轉換設備進行雙向轉換，提升能源利用率.

2) 協調電廠并網.遍布在廣泛地域的光伏、風能或類似可再生能源發電廠的發電效率和時長并不穩定，需通過與主干電網互補協作，才能在保證穩定供電的基礎上，降低一次性能源消耗，提升用電效能.

3) 動態存儲調度.在傳統電網中，用電負荷側被認為是固定的、具有周期性或可預測的.但是隨著電動汽車、蓄電池等儲能的需求，用電側也是可以進行配置的.因此，自愈網絡需要主動地對用電負荷和儲能設備進行控制，引導用戶主動使用可再生能源，提升用電效能.

4) 故障處理.自愈網絡在發現能源互聯網發生故障時，能夠快速定位故障位置，診斷故障原因，執行修復方案.

Fig. 2 The architecture of self-heal system圖2 自愈系統總體架構圖

因此，構建能源互聯網對電網自愈系統的需求滿足3方面的要求：

1) 高速高效地實時監控.能夠在能源互聯網中涉及到的相關領域都具有足夠、及時的信息收集、傳遞、執行的能力.如供熱系統、天然氣系統、電網系統、微網系統中，都需要有傳感節點采集和傳遞信息，并且有智能軟件代理接收和執行操作指令.

2) 智能化任務計算系統.能源互聯網應具有高速通信網絡及云端信息處理系統，能夠完成大量復雜的并行任務處理，用于對全網范圍內的信息進行實時處理，并計算出相應的電力維護和異常處理任務序列以完成任務.

3) 符合實際情況的硬實時操作序列推理.在日常維護(特別是故障緊急處理)過程中，自愈系統需要對各種關鍵設備進行諸如“開關”、“增減”、“并串”等物理操作.其中，每項操作都有相應的時間長度，并且，多項操作之間存在先后次序.因此，自愈系統必須正確計算出在當前狀態下，滿足一定時長、一定次序的安全操作序列，并下發給智能代理進行執行.

可以看出，能源互聯網必須具有高速高效的通信網絡、足夠的計算能力、遍及全網的神經感知末梢硬件基礎設施，通過合理的、可實現的軟硬件系統，執行正確的任務序列.

本文將重點在第3節中討論在具備以上硬件的條件下，如何實現避免后繼故障的硬實時任務序列的生成和執行.

2.2 基于多智能體的電網自愈系統的整體框架

多智能體電網自愈系統由大量可計算的、駐留在關鍵節點的智能代理組成，系統內的智能體既彼此獨立又可以相互作用.不同的智能體之間可以進行通信、交互.

圖2展示了多智能體電網自愈系統的概貌，包括了橫向、縱向和垂向：

1) 從橫向上看，包括了不同領域內的智能體代理，如電網系統、電廠系統、微網系統、供熱系統等，在每個領域內，都會有與本領域知識相關的軟件系統進行管控.

2) 從縱向上看，包括了不同層次的代理，如中央級代理、區域級代理.

3) 從垂向上看，包括了不同地域的智能體代理，如不同省市、不同地區、不同小區的智能體代理.

圖2給出的僅是一個參考架構，其本質上是一個自相似圖形系統，在省內、市內、區縣內甚至小區內都能以類似的軟件架構為參考，實現分層、分級、分區域的“源-網-荷-儲”互通協作.

本文的重點是提出和論證自愈系統中需要加入實時截止期約束，提出求解方法，這里并不針對每個知識領域內的智能體系統進行具體軟件設計和實現.在此，僅對每種領域抽象出3類智能代理用于完成基本的功能，包括通信代理、信息采集代理和命令執行代理.

能源互聯網的多智能體自愈系統日常工作可以抽象為若干任務的計算、分配、下發和執行，如圖3所示.電網自愈系統包括決策和執行2個層面.決策層包括信息預處理系統、專家系統和實時截止期約束推理機.信息預處理系統用于完成信息的收集、去掉冗余信息和矛盾信息，對電網系統當前的運行狀態進行定性判斷.

Fig. 3 The process of self-heal system圖3 自愈系統工作流程

電網自愈系統的主要工作流程包括：

1) 在能源互聯網的“源-網-荷-儲”中各個關鍵節點中部署的智能代理，通過相關傳感器收集相應的信息，并上傳到該分級決策系統.

2) 該級的決策系統將會先對收集的信息進行處理，去偽存真，而后判斷當前電網運行狀態是否正常.如果正常，將在安全操作樹中計算需要執行的日常維護操作任務；如果發生故障，將在安全操作序列樹中計算需要執行的日常維護操作任務.

3) 計算符合當前狀態需要的任務序列，并將任務序列進行實時截止期約束下的計算.如當故障發生時，對應的故障鏈上的結點將被觸發；推理機將根據故障結點在安全操作樹求解安全操作序列，當安全操作序列的操作時間滿足故障結點時間截止期時，則視為成功操作序列；若該操作序列不滿足，則求解新的操作序列；若所有求解的操作序列均不能滿足截止期，則視為該故障結點無法及時自動修復，后繼的故障結點也將被觸發.此時，將已觸發故障結點和后繼結點的截止期疊加，并以改截止期求解新的安全操作序列.

4) 向智能代理下發符合條件的任務序列進行執行，完成工作周期內的任務.

專家系統中包括了能源互聯網涉及到的各種領域知識，我們將其抽象為3個集合：故障鏈集合、正常狀態集合和安全操作樹集合.

故障鏈集合是根據經驗總結的可能發生或已經發生的故障狀態，每一個故障狀態都對應一個時間長度，在此定義為截止期，如果不能在截止期完成，將引發新的故障.不屬于故障鏈的集合將屬于正常狀態.安全操作樹包括了日常維護和故障處理的全部安全的任務處理序列，以有向圖的方式進行存儲.

任何一個故障鏈或正常狀態鏈，都至少對應了一個安全操作樹中的一個完整操作序列子樹；當對應的智能代理完成全部操作序列后，該故障排除；如果不能在規定時間內完成，故障無法排除，并產生新的故障，故障鏈進入下一環節，需要完成更多的安全操作序列，如圖4所示:

Fig. 4 The mapping between fault chain and security operation tree圖4 故障鏈和安全操作樹的映射

由于電網自愈系統是分級系統，在每一級中具有相應的決策系統，對該級別以下的所有區域、所有領域內的代理進行集中式協調，由該決策系統對電網自愈系統需要完成的日常維護或故障處理目標進行規劃和分配.

本文將電網自愈系統的行為抽象成為電網自愈多智能體混合關鍵性實時調度下的實時推理系統，并通過多智能體進行任務的執行實現.

本文的先期工作在文獻[15]中有所描述.該文對已有的多智能體平臺AgiBuilder進行了改進，構建了原型系統，可以運算和執行硬實時調度任務.本文在此基礎上，針對能源互聯網，提出和設計了基于多智能體的電網自愈系統軟件架構，以落實圖2所示的橫向(多種知識領域的融合)和縱向(多層級控制調度)電網自愈過程.

首先，在縱向上，電網自愈系統的多智能體包括設備級、小區級、中央級3種層次.在3種層次中，分別對應著不同知識領域的智能體進行相互協作和集中決策.

1) 設備級智能體，即能源互聯網的核心設備中部署的智能體.具體包括產線智能體、管網智能體、轉儲智能體，作用有3點：

① 產線智能體.部署在電廠、微網、化工廠等能源生產場所，完成數據采集、發送和指令接收.當發生故障時,可通過專用裝置隔離和消除故障，減少損失.

② 管網智能體.在多種管網中的核心裝置中部署智能體，完成管線狀態實時采集、管線的開關等功能.

③ 轉儲智能體.在儲能設備和能源轉化設備中部署智能體，用于完成儲能、能源轉化過程的監控.

在設備級智能體這一層次中，在各自領域設備中部署的智能體的設計與設備類型有關，軟件內部結構各有不同，核心目標是完成對該類設備的監控.

2) 小區級智能體，即可以匯聚該區域內設備級代理回傳的信息并進行處理.當小區級智能代理在收集本區域的信息后發現某個設備發生故障時，將立即進入修復過程；如果依靠本小區無法解決問題時，將會向中央級智能代理發送資源協調請求.

在小區級智能體這一層次中，各知識領域的智能體軟件結構是類似的，主要的區別在于內部的操作邏輯不同；每一領域的智能體擁有該領域的知識庫以及故障事件到安全操作的映射法則.

3) 中央級智能體，即在一個廣泛區域內掌控較充分資源的智能體.在收到小區級智能體資源協調需求后，中央級智能體將根據相應預案進行快速資源調度，計算相關安全操作序列，并將符合時間約束條件的指令序列經由小區級智能體下發到設備級智能體進行執行.

在中央級智能體這一層次中，其軟件結構與小區級智能體是類似的.兩者的區別在于中央級智能體擁有了該區域內全部的知識領域智能體，并擁有更高等級、更深層次、更大力度的安全操作能力及相應的映射法則.

通過這三級智能體，并結合原有的原系統，可以實現適用于電網自愈系統的基礎軟件架構.但是，以上的軟件體系僅僅是基礎設施層的設計和實現，并未解決電網自愈系統的操作序列固定、操作時間受限的調度問題.本文第3節和第4節分別對該調度問題進行建模和求解.

3 電網自愈多智能體混合實時調度任務建模

為了實現電網自愈多智能體混合實時調度，我們基于正常狀態集合、故障鏈集合、安全操作樹和智能體建立起調度任務模型，如圖5所示.

Υ={Υ(l),1≤l≤n},
Υ(l)={τi|ri,Di,Gi,{τi,j|Cij,1≤j≤ni},1≤i≤k}.
Ψ={Ψ(r),1≤h≤m},
Ψ(r)={τi,k∈G(τi),…,τj,h∈G(τj),…,τp,q∈G(τp)}.

該模型有8點內容需要說明：

1)Υ是由n個故障鏈Υ(l)組成的；

2) 每一條Υ(l)上有k個結點，每個結點代表了一個安全操作子圖，把這個操作子圖的處理過程看成一個調度任務τi,若Υ(l)上第1個結點對應的調度任務在其截止期內完成執行，則該故障鏈不向后傳播，否則觸發該故障鏈上的下一個結點對應的調度任務；

Fig. 5 Task model for scheduling圖5 調度任務模型

3) 就緒時間ri:τi進入系統的時間，即故障觸發進入安全操作樹的時間；

4) 相對截止期Di:τi所允許的最大響應時間；

5) 偏序圖Gi(graph):該有向圖定義了組成任務τi的ni個子任務之間的偏序關系，Gi代表了安全操作樹，決定了任務τi的執行流；

6) 執行時間Cij:通過最壞執行時間分析技術所預定義的子任務τij所需要執行的時間；

7) 多智能體有m類智能體給任務提供處理器資源，調度的目標是讓這些智能體能成功調度Υ中的所有子任務即Ψ=Υ，同時故障鏈上向后觸發的故障數最少；

8) 分屬不同Υ(l)的子任務根據操作類型的不同，被指定給對應類別的智能體上去執行，則智能體上能執行的子任務集合記為Ψ(r).

偏序圖Gi中，如果存在有向邊從子任務τi,u指向子任務τi,v，則τi,v被稱為τi,u的子結點直接后繼，τi,u被稱為τi,v的父結點直接前驅.子任務τi,j的直接前驅集合記為preddirect(τi,j)和τi,j的直接后繼集合記為succdirect(τi,j).如果存在有向邊路徑從子任務τi,u可達子任務τi,v，則τi,v被稱為τi,u的后繼，τi,u則被稱為τi,v的前驅.子任務τi,j的所有前驅集合記為pred(τi,j)和τi,j的所有后繼集合記為succ(τi,j).沒有前驅的子任務稱為源結點，沒有后繼的子任務稱為終結點.

表1中列出了每個任務?τi(i≥1)及其對應的子任務τi,k，k∈{1,2,…,j}在調度中可以用到的參數.

Table 1 Parameters of Tasks and Sub-Tasks表1 任務及子任務的調度參數

1) 開始時間si和si,k:τi和τi,k開始執行的時間；

2) 執行時間Ci,k:通過最壞執行時間(worst-cast execution time, WCET)分析技術所預定義的τi,k所需要執行的時間；

3) 時刻t的剩余執行時間Ci(t)和Ci,k(t):Ci和Ci,k減去到時刻t為止已執行過的累積時間；

4) 完成時間fi和fi,k:τi和τi,k執行結束的時間，即Ci(t)=0和Ci,k(t)=0的時刻，fi=min{t|Ci(t)=0}，fi,k=min{t|Ci,k(t)=0}；

5) 就緒時間ri,k是其Gi上所有直接前驅結點都完成的時刻，即ri,k=max(fi,j)，τi,j=preddirect(τi,k)；

6) 響應時間Ri:τi從就緒到執行完成的時間長度，Ri=fi-ri，Ri≤Di；

7) 絕對截止期di:di=ri+Di，fi≤di；

succ(τi,k),Pi,k,l∈Pi,k；

因為EDF在調度上的最優性[16-17]，在每個智能體上使用EDF對任務進行調度.那么，Ψ(r)被EDF成功調度的充分必要條件是?τi,k,τj,h∈Ψ(r),ri,k≤dj,h,dj,h-ri,k≥∑Cp,q(?τp,q∈Ψ(r),ri,k≤rp,q,dp,q≤dj,h).

4 電網自愈多智能體混合實時調度方法

電網自愈多智能體混合實時調度整體過程如下：

Step1. 對安全關鍵的任務子集合Υcri進行調度：通過給Υcri在多智能體上分布式地給每個任務偏序圖上的子任務找到一種可調度的局部截止期分配方案來確保多智能體的處理器資源可成功地調度所有的安全關鍵任務,并同時給剩余的其他任務留出盡可能多的空閑處理器資源；

Step2. 對其他任務Υnon-cri進行調度，重復執行Step2.1～Step2.3直至所有任務都執行完畢或沒有空閑的處理器資源：

Step2.1. 任務的默認當前等級為Level1;

Step2.2. 根據其鏈的結構，根據當前等級的執行時間需求和截止期內來分析能否在多智能體上找到足夠長的空閑處理器長度來完成執行；

Step2.3. 如果任務可被成功調度，則將該任務按當前等級準入并執行；否則，該任務進入下一個等級，轉到Step2.2進行執行.

其中，Step1需通過對各子任務劃分局部截止期保證其能夠被成功調度.

通過給子任務τi,k分配局部截止期di,k，使所有子任務在各自的智能體上分別完成其執行需求，同時任意子任務的截止期di,k都不超過其所屬任務τi的截止期di，從而Υcri中所有任務τi都能被成功調度.為此，前驅子任務不能過度使用智能體上的松弛時間而要給后繼子任務留出足夠的時間來完成執行.合適的局部截止期分配不僅要考慮調度任務在執行路徑上的執行工作總量，還要考慮與其他任務共享的智能體上處理器資源的競爭關系.

每個智能體上的局部截止期分配方法的優化目標是最大化子任務的最小松弛時間[18-19]，為后續其他子任務留出盡可能多的松弛時間來幫助滿足其所屬任務總截止期的約束.同時，也要保證不同任務在該智能體上的所有子任務是可調度的.

把上述目標和約束用數學形式化表述如下：

約束條件：

② ?τi,k,τj,h∈Ψ(r),ri,k≤dj,h,dj,h-ri,k≥∑Cp,q(?τp,q∈Ψ(r),ri,k≤rp,q,dp,q≤dj,h).

在完成Step1后，每個多智能體將根據子任務的局部截止期，對其Ψ(r)上的子任務進行調度，其核心算法如下：

挑選Ψ(r)中局部截止期最小的τi,k去執行，di,k=min{dj,h|τj,h∈Ψ(r)}.

當Ψ(r)的子任務τi,k完成執行時，

1) 將τi,k的完成信息通知給τi,j,其中，?τi,j∈succdirect(τi,k)∩τi,j∈Ψ(l)；

2) 把τi,k從Ψ(r)中丟棄Ψ(r)=Ψ(r)-{τi,k}；

3) 挑選Ψ(r)中局部截止期最小的子任務τp,q去執行，dp,q=min{dj,h|τj,h∈Ψ(r)}.

Ψ(l)獲得τi,k的完成信息后，

1) 讓τi,j就緒，τi,j∈succdirect(τi,k)∩τi,j∈Ψ(l)；

3) 如果劃分局部截止期失敗，采取以下步驟：

① 可借鑒文獻[21]的任務丟棄處理策略，用傳播的方式通知其對應智能體上的后繼succ(τi,j)并將τi丟棄；

② 若是Υnon-cri中的任務，再將τi轉入下一個等級分配到多智能體上.

重復上述操作直至所有任務執行完畢.

5 實驗與結果

本節通過實驗基于本文提出的電網自愈多智能體混合任務模型，隨機生成任務測試集，對EDF簡單調度和第4節調度方法下的任務成功率進行對比.

5.1 度量標準

1) 調度成功率STSR.STSR=N(STS)N(TS)×100%，其中，N(STS)是能被成功調度的任務集個數,N(TS)是隨機產生的任務集總個數.用于Υcri任務調度效果對比.

2) 故障出現率DTR.DTR=N(DT)N(T)×100%，其中，N(DT)是被調度丟棄的任務次數(丟棄的次數越多，故障個數也就越多),N(T)是隨機產生的任務總個數.DTR用于Υnon-cri任務的調度效果對比.

5.2 數據集

系統中有8個智能體提供處理器資源，隨機生成100個故障鏈，每條鏈上結點個數是取值于[3,9]中的隨機值，每個結點對應的任務具有泊松分布的到達時間ri,泊松分布的參數范圍是[10,150]之間(該值為就緒時間間隔的期望值),模擬生成不同的負載情況.隨機任務的相對截止期Di服從均勻分布U[100,500].

隨機任務在隨機鏈生成的基礎上添加1～5條路徑形成安全操作樹，書上結點的執行時間Ci,j服從參數為100Di的指數分布的隨機變量.若生成的任務執行時間超過Di，則該任務不被采納.在不同的任務集負載①(50,150,…,500)各隨機生成100個任務集.

5.3 實驗和結果

本節將觀察隨機任務測試集負載不同的情況下,用EDF簡單調度的策略和第4節調度方法下的調度成功率和故障出現率的變化，如圖6所示.

調度成功率的變化曲線如圖6(a)所示，這里比較的是在每個任務集負載下生成的100個任務集通過簡單EDF調度方法和本文提出的調度方法能成功調度的任務集個數.能被某個方法調度成功的任務集也稱為可行的任務集，那么，圖6(a)表明了本文提出的調度方法可比簡單EDF調度方法能找到的可行任務集個數要平均多出17.74%.本文提出的調度方法隨著任務集負載的增加調度成功率的降低比較平穩，是因為本文的調度方法始終都不斷逼近第4節中提出的優化目標；而簡單EDF調度則隨著任務集負載的增加、調度成功率的降低，根據隨機任務集參數的不同而時緩時急.

故障出現率的變化曲線如圖6(b)所示，故障個數增多伴隨著丟棄任務的次數增加，一個任務之所以會被丟棄，要么是因為在簡單EDF調度下該任務的截止期限無法得到滿足，要么在本文提出的調度方法下找不到給該任務的子任務劃分局部截止期的方案.從圖6(b)可以看出，本文提出的調度方法在隨機任務集不同負載的情況下，故障出現率都保持在一個較低的水平，尤其是高負載的情況下，故障出現率仍然令人滿意；而簡單EDF在較高負載下的故障出現率急劇增長.本文提出的調度方法比簡單EDF調度方法所丟棄的任務數，即出現故障幾率，要平均減少7.72%.

Fig. 6 Performance comparison on Simple EDF and Our Approach圖6 簡單EDF調度和第4節調度方法的結果比較

① 任務負載為密度之和比智能體個數：U(T)=sum(CiDi)m

6 總 結

本文提出了一種帶有截止期實時約束的電網自愈系統基于多智能體進行處理的機制和可供參考的軟件實現架構.針對具有實時截止期約束條件下的安全操作序列求解問題，提出了一種基于多智能體的混合關鍵性調度任務模型；并給出了電網自愈多智能體進行混合關鍵性調度的求解方法，給出了優化目標和約束條件，用混合整數線性規劃(MILP)模型求解.通過仿真結果驗證了智能電網自愈多智能體混合關鍵性調度模型及其求解算法有效地增加了故障結點安全操作處理的成功率，并減少了故障鏈式的后續觸發率.在下一步工作中，我們將把故障鏈擴展為故障樹，在此基礎上建立基于故障樹的調度任務模型并分析其調度方法.