基于規則引擎的通訊衛星應急任務調度

劉 永，李子揚，竇 帥，周春城，李傳榮+

(1.中國科學院光電研究院 中國科學院定量遙感信息技術重點實驗室，北京 100094；2.中國科學院大學 電子電氣與通信工程學院，北京 100049)

0 引 言

任務調度系統是衛星地面系統的重要組成部分，是進行衛星資源管理與分配的主要工具，負責衛星任務計劃的編制、執行和控制調整，在衛星資源相對稀缺、用戶的任務需求不能全部滿足的情況下，實現衛星資源的合理分配與沖突資源的優化調度尤為重要[1,2]。隨著航天事業的發展，衛星功能不斷增強，衛星任務需求與任務調度模式不斷演進[3]，使得調度規則發生變化，促使調度系統不斷升級。傳統方式使用配置文件或配置參數來增強系統的柔性和靈活性，但功能相對有限，難以適應具體調度規則的變化。因此建立一個柔性的、靈活性較高的任務調度系統，方便調度規則的修改和定制，降低調度系統的維護成本，是十分必要的。

為此本文將規則引擎技術應用于獨占資源衛星任務調度中，通過規則引擎將調度規則從業務邏輯代碼中分離出來，減少調度規則的變動對業務邏輯代碼的影響，增強調度系統的柔性和靈活性，降低調度系統維護的風險及成本。同時設計基于權重的推理網構建方法，優化了推理網的結構，提高了調度系統的運行效率。

1 獨占資源通訊衛星應急任務調度策略

根據任務調度模式的不同可將獨占資源通訊衛星任務調度分為集中任務調度和應急任務調度[4,5]。集中任務調度是在本周的某固定時間對用戶提交的下周的衛星資源使用申請進行集中處理的過程，按照規定，在集中調度時間點后提交的一般性衛星資源使用申請在本次調度周期中不予受理，但是由于突發的重要事件而產生的緊急衛星資源使用申請，需進行及時的特殊處理，這其中特殊處理被稱為應急任務調度模式。

在集中任務調度模式中，任務調度響應的時間要求并不緊急，調度目標是在滿足任務時效性的前提下實現調度任務的優先級之和最大，一般采用遺傳算法等智能優化算法求解近似最優調度方案。應急任務調度模式是在集中任務調度方案的基礎上進行的再調度，由于應急任務的突發性、緊急性及重要性，這類任務擁有較高的優先級和任務價值，所以采用基于優先級的調度策略，使優先級高的任務具有優先執行權。

本文調度的思路是當有應急任務提交時，在集中任務調度方案的基礎上采用直接調度或沖突替換原則。直接調度原則為當應急任務滿足衛星資源使用的各種約束，且申請的衛星資源處于空閑狀態，則將該任務直接納入衛星工作計劃。沖突替換原則為應急任務滿足衛星資源使用的各種約束，但申請的衛星資源處于被占用狀態時，即應急任務與已有的衛星工作計劃發生資源使用沖突，如果與應急任務產生沖突的計劃數量為一，且應急任務的優先級大于計劃的優先級，則用應急任務替換掉與之沖突的計劃，反之則不予替換；如果與應急任務產生沖突的計劃數量為多個時，并且應急任務的優先級大于所有與之沖突的計劃的優先級，則用應急任務替換掉與之沖突的所有計劃，反之則不予替換。這種替換雖然導致某些已經被調度的任務無法執行，但是從實際情況分析，緊急、重要的任務被優先執行是合理的。

2 規則引擎技術

規則引擎的定義請參見文獻[6]。

Drools是用Java語言開發的規則引擎，其內部使用的模式匹配算法是Rete，速度快、效率高。它采用聲明式的程序設計方式，比其它命令式的編程語言代碼更簡潔；可通過規則庫高效解決業務規則變動問題，更靈活地適應各種變化的業務場景。

Drools的組成如圖1所示。

圖1 規則引擎的組成

各部分的作用如下：

(1)工作內存(Working Memory)：存放系統工作時要處理的數據對象(Fact)；

(2)規則庫(Rule Base)：存放腳本語言編寫的業務規則；

(3)模式匹配器(Pattern Matcher)：進行數據與規則的匹配，創建規則的執行實例，并將實例加入議程中；

(4)議程(Agenda)：存放所有的規則執行實例，并根據某種策略制定實例的執行順序；

(5)執行引擎(Execution Engine)：執行議程中所有的規則執行實例。

Drools在工作時通過模式匹配器將工作內存中的事實和規則庫中的規則進行匹配，對匹配成功的規則創建執行實例，并將這些實例加入議程中。議程根據某種策略制定這些實例的執行順序，形成實例的執行隊列。執行引擎按照順序依次執行。在執行過程中事實對象的狀態會發生變化，即產生新的事實，使得某些未執行的實例失效而從隊列中剔除，也可能形成新的執行實例加入隊列中，形成一種動態的規則執行鏈[7-9]。

3 基于Drools規則引擎的獨占資源通訊衛星應急任務調度系統

結合上述研究，將規則引擎技術應用于獨占資源通訊衛星應急任務調度中，實現調度規則與應用程序的分離，提高系統的靈活性、可擴展性及易維護性，并對Drools規則引擎進行改進，優化了推理網的構建過程，提高了系統的工作效率。

3.1 系統結構

獨占資源通訊衛星應急任務調度系統采用C/S架構，分為數據層、服務層、應用層。應用層主要為衛星控管中心提供申請信息管理、計劃信息管理、調度規則管理和衛星資源管理等；服務層實現了系統運行中涉及的各類服務，包括規則推理服務、數據管理服務、任務調度服務等；數據層使用關系數據庫為系統提供數據管理功能，數據庫包括用戶申請數據庫、衛星工作計劃數據庫、衛星資源數據庫、調度規則數據庫，如圖2所示。

圖2 調度系統的結構

3.2 應急任務調度規則

規則庫是基于規則引擎的系統的核心，是系統進行業務判斷與決策的依據，規則庫的質量對處理結果的準確性及系統的運行效率有著直接影響。因此要得到良好的衛星任務調度結果和系統工作效率，在建立調度規則庫時，需要對應急任務模式下的調度規則進行精確的凝練和表達，對規則庫的結構進行合理設計。

通過章節1中對應急任務調度場景的分析與調度思路的設計，結合衛星資源使用約束，凝練出如下13條應急任務調度規則：

規則1：如果申請的狀態值為“null”，則申請的狀態值由“null”轉為“受理”；

規則2：如果狀態值為“受理”的申請的用戶目標不是當前用戶中心的管理型號，則申請的狀態值由“受理”轉為“不受理”；

規則3：如果狀態值為“受理”的申請的通信波段不在其申請的獨占資源通訊衛星通信波段范圍內，則申請的狀態值由“受理”轉為“不受理”；

規則4：如果狀態值為“受理”的申請的任務持續時長小于2分鐘，則申請的狀態值由“受理”轉為“不受理”；

規則5：如果狀態值為“受理”的申請的服務開始時間早于系統當前時間，則申請的狀態值由“受理”轉為“不受理”；

規則6：如果狀態值為“受理”的申請的用戶目標是地面設備，則申請的狀態值由“受理”轉為“可視”；

規則7：如果狀態值為“受理”的申請的衛星資源使用時段在獨占資源通訊衛星與用戶目標可視窗口內，則申請的狀態值由“受理”轉為“可視”；

規則8：如果狀態值為“受理”的申請的衛星資源使用時段不在獨占資源通訊衛星與用戶目標可視窗口內，則申請的狀態值由“受理”轉為“不可視”；

規則9：如果狀態值為“可視”的申請的衛星資源處于空閑狀態，則申請的狀態值由“可視”轉為“納入計劃”；

規則10：如果狀態值為“可視”的申請的衛星資源處于占用狀態，則申請的狀態值由“可視”轉為 “沖突”；

規則11：如果狀態值為“沖突”的申請的沖突對象是調度方案中衛星工作計劃，且申請的優先級大于與其沖突的計劃的優先級。則申請的狀態值由“沖突”轉為“納入計劃”，與其沖突的計劃狀態值由“計劃”轉為“被替代”；

規則12：如果狀態值為“沖突”的申請的沖突對象是調度方案中衛星工作計劃，且申請的優先級小于與其沖突的計劃的優先級。則申請的狀態值由“沖突”轉為“拒絕納入計劃”；

規則13：如果申請的狀態值為“納入計劃”，則調用衛星資源分配函數將申請寫入計劃表。

為了清楚表達上述規則間的聯系及申請在規則推理過程中的狀態變化情況，采用狀態機圖進行的表達如圖3所示。

圖3 申請的狀態機

3.3 基于Drools規則語法的調度規則形式化表示

Drools采用原生的規則語言，規則結構簡潔、可讀性強[10]。規則的結構組成如圖4所示。

圖4 Drools規則結構

關鍵詞rule標識一條規則的開始，其后是該規則名稱，是規則在規則庫中的唯一標識，具有唯一性；關鍵字attributes是規則屬性，是可選項，用于對規則的行為進行限定；關鍵字when是規則條件(left side hand,LHS)部分開始的標識，LHS是一些邏輯表達式，用于判斷；關鍵字then是規則結論部分(right side sand,RHS)開始的標識，RHS是一個Java語言代碼塊，是要執行的操作；關鍵字end表示規則的結束。

以3.2中的rule7為例，其對應“Drools”規則引擎的代碼如下：

rule “IsvisiableRule” //規則名稱

salience 10 //規則優先級

no-loop true //不能被同一事實再次激活

when

$app: Application(station==accepted); //申請狀態

$vw: VisiableWindow($app.satelliteID== satelliteID,$app.usertargetcode==user,$app.starttime>= starttime, $app.endtime<=endtime); //受理的申請是否在可視窗口內

Then

$app.setStation (“visible”); //狀態修改為可視

update($app); //更新申請狀態

end

其中規則屬性使用的是salience(優先級策略，salience值越大表示規則的優先等級越高)、no-loop(值為true時，該規則不會被同一事實再次激活)，分別用于解決規則沖突和規則庫死循環問題。

3.4 基于Drools的任務調度規則引擎的改進

Drools中使用的是目前效率最高的Forward-Chaining推理算法Rete。Rete算法將規則庫構建成推理網的形式，以達到顯著降低計算量的效果，并且Rete算法利用推理引擎的時間冗余性和產生式規則結構相似性的特點，在推理網的構建中實現狀態保存機制和節點共享機制，極大提高了Drools的工作效率[11,12]。

在實驗的過程中發現，Drools中的節點共享機制并非廣泛意義上的共享，其對規則結構有著較嚴格的要求。下面給出3個規則組，每個規則組中都有兩條規則，并且規則中的匹配條件相同，不同在于規則中的匹配條件排列順序不同。

規則組一：

rule “rule_1”

when

$app: Application (UserID==“GD”, satelliteID==“A”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(satelliteID==“B”,UserID==“GD”)；

Then

{Code}

End

規則組二：

rule “rule_1”

when

$app: Application(satelliteID==“A”，UserID==“GD”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(satelliteID==“B”,UserID==“GD”)；

Then

{Code}

End

規則組三：

rule “rule_1”

when

$app:Application(UserID==“GD”, satelliteID==“A”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(UserID==“GD”, satelliteID==“B”)；

Then

{Code}

End

3個規則組對應的推理網如圖5所示。

圖5 推理網

Root Node是所有對象進入推理網的入口；Type Node進行對象類型的判斷，只有類型匹配成功的對象才能進入下一個節點。Alpha Node又稱單輸入節點，用來對單一的對象進行條件判斷，對應著規則中的邏輯判斷。當規則有多個邏輯判斷，對應的Alpha Node會串聯在一起。對象在滿足當前Alpha Node對應的邏輯判斷后才能進入下一個Alpha Node；Adapter Node將單個對象轉為單對象數組。Terminal Node表示對象與規則完全匹配。

從圖5看出UserID==“GD”節點在規則組三的推理網中實現了規則間的共享，但在規則組一、二中沒能實現共享，使得規則組三的推理網較其它兩組節點更少，系統存儲開銷更小，工作效率更高。3個規則組的實現的功能相同，但形成的推理網結構不同，說明規則中邏輯判斷的排列順序不會影響規則的功能，但會影響推理網的結構，進而影響系統性能。

產生這種現象的原因是Drools在構建推理網時，如果一條規則中有多個邏輯判斷，那么它們對應的Alpha Node在推理網中的連接順序與其在規則中的排列順序是一致的，在這里稱為基于順序的連接方式。規則組一的推理網中，兩個UserID==“GD”節點的內存中存儲的數據對象并不相同(rule_1的UserID==“GD”節點中存儲的是滿足自身邏輯判斷的數據對象，rule_2的UserID==“GD”節點中存儲的是滿足satelliteID==“B”節點和自身邏輯判斷的數據對象)，此時二者是兩個同名不同質的Alpha Node，不能合并為一個共享節點，規則組二同理。所以規則組一、組二中雖然有相同的邏輯判斷，但由于規則原生結構的限制，使推理網中的同名節點不能共享。

綜上所述，Drools中這種基于順序的連接方式，使推理網的結構與規則的結構形成強關聯性，不具備節點連接時的動態調整能力，導致某些相同的Alpha Node沒能實現共享。針對這一問題本文提出基于權重的連接方式：在構建推理網時，如果一條規則中有多個邏輯判斷，權重大的邏輯判斷對應的Alpha Node會獲得優先連接權。具體改進方法為：首先統計規則庫中所有的邏輯判斷總數，然后將相同的邏輯判斷歸為一類并統計其數量，最后計算各類邏輯判斷的權重。計算方法為λi=(ni/N)，其中λi表示邏輯判斷i的權重值，ni表示規則庫中邏輯判斷i的個數，N表示規則庫中邏輯判斷總數。這樣各類邏輯判斷都擁有自己的權重值。在構建推理網時，對于一條規則中的多個邏輯判斷，Rete算法根據其權重值從大到小的順序依次獲取并構建對應的Alpha Node。這種基于權重的連接方式，使推理網的結構擺脫了規則原生結構的限制，充分利用規則庫中相同邏輯判斷在數量上的特征，并將這種特征用于推理網的構建過程中，使相同的邏輯判斷可以實現共享，降低推理網結構的冗余性，提高推理效率。

3.5 調度系統驅動數據及其表示

系統進行調度工作使用的數據包括：衛星可視窗口(用戶目標與獨占資源通訊衛星之間的可視時段)、衛星工作計劃、用戶任務申請，其中前二者稱為衛星系統資源狀態事實，第三個稱為待調度事實。為實現調度系統對數據的處理及數據在數據庫中的有效存儲與管理，需要對用戶申請、可視窗口、衛星工作計劃3類數據進行規范化表示。根據Java面向對象的編程特點，分別建立用戶申請類、可視窗口類、衛星工作計劃類，每個類具有各自的屬性及其對應的getter和setter方法。例如用戶申請表示形式見表1。

表1 用戶申請

4 實 驗

由于應急任務的特殊性，所以應急任務調度模式是一種實時調度，采用的是“申請-響應”的調度方式。下面兩組實驗，分別使用基于Drools改進前、后的任務調度系統對一天內(24 h)接收的50條應急申請進行調度，驗證調度系統的性能，并對Drools規則引擎改進前后的性能進行對比。其中實驗組1中的50條應急申請滿足衛星資源使用各種約束且與衛星工作計劃無沖突；實驗組2中的50條應急申請滿足衛星資源使用各種約束但與衛星工作計劃有沖突，其中，25條申請優先級大于計劃，25條申請優先級小于計劃。

4.1 實驗環境與數據概述

本文實驗的原型系統在eclipse中開發，規則引擎為Drools6.5，數據庫為MySQL8.0，服務器為TomCat7.0，運行平臺為windows10，CPU:Intel i3-3110M 2.4GHz。

實驗中包括4顆通訊衛星，10顆用戶衛星，使用的數據有衛星間可視窗口、用戶申請、衛星工作計劃，其中衛星間的可視窗口數據通過衛星星歷計算得出，用戶申請由模擬實際用戶申請程序生成，衛星工作計劃由集中任務調度程序生成。

4.2 實驗結果

系統運行時間的統計結果和申請處理結果如圖6和表2所示。

圖6是兩組實驗中50條應急申請的處理時間的折線圖，表2是處理時間統計出的均值和方差及申請調度的結果。對實驗結果從以下4個方面進行分析：①從Drools改進前后系統的運行時間進行對比分析，可以看出改進后的系統運行時間效率相比改進前提高了5%左右，說明文中提出的改進方法提高系統性能，規則數量越多，相同的邏輯判斷越多，效率的提升越明顯；②從兩組實驗對照角度分析，可以看出系統在處理有沖突的申請用時比無沖突的多，但是差距在20 ms內，說明系統在處理資源使用沖突時，

圖6 系統運行時間折線

表2 系統運行時間特征及申請調度結果統計

具有良好的優化調度效率；③從系統處理50條申請的時間方差角度分析，方差在5 ms2上下，說明系統運行的穩定性較好；④從申請調度后納入計劃的結果分析，實驗組1中50條無沖突的申請全部納入計劃，實驗組2中50條有沖突的申請，其中優先級大于計劃的25條納入了計劃，優先級小于計劃的25條沒有納入計劃，調度結果跟預期設想的結果一致，說明系統調度結果可靠。

5 結束語

本文將規則引擎技術應用于獨占資源通訊衛星應急任務調度中，實現了調度規則與業務邏輯代碼的分離，便捷了調度規則的集中管理與修改，降低了調度規則變動對系統造成的影響，提高了系統的靈活性和適用性。同時設計基于權重的連接方法對Drools規則引擎進行改進，優化了推理網的構建過程，降低了推理網中節點冗余問題，提高了系統的運行效率。實驗結果表明，基于改進的Drools規則引擎的獨占資源通訊衛星應急任務調度方法切實可行。在處理衛星資源使用沖突時如何通過規則引擎實現用戶申請窗口的滑動，進一步提高申請調度成功率，將是我們下一步的工作。