基于規(guī)則引擎的通訊衛(wèi)星應急任務調度

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

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

0 引 言

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

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

1 獨占資源通訊衛(wèi)星應急任務調度策略

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

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

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

2 規(guī)則引擎技術

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

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

Drools的組成如圖1所示。

圖1 規(guī)則引擎的組成

各部分的作用如下：

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

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

(3)模式匹配器(Pattern Matcher)：進行數(shù)據(jù)與規(guī)則的匹配，創(chuàng)建規(guī)則的執(zhí)行實例，并將實例加入議程中；

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

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

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

3 基于Drools規(guī)則引擎的獨占資源通訊衛(wèi)星應急任務調度系統(tǒng)

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

3.1 系統(tǒng)結構

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

圖2 調度系統(tǒng)的結構

3.2 應急任務調度規(guī)則

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

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

規(guī)則1：如果申請的狀態(tài)值為“null”，則申請的狀態(tài)值由“null”轉為“受理”；

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

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

規(guī)則4：如果狀態(tài)值為“受理”的申請的任務持續(xù)時長小于2分鐘，則申請的狀態(tài)值由“受理”轉為“不受理”；

規(guī)則5：如果狀態(tài)值為“受理”的申請的服務開始時間早于系統(tǒng)當前時間，則申請的狀態(tài)值由“受理”轉為“不受理”；

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

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

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

規(guī)則9：如果狀態(tài)值為“可視”的申請的衛(wèi)星資源處于空閑狀態(tài)，則申請的狀態(tài)值由“可視”轉為“納入計劃”；

規(guī)則10：如果狀態(tài)值為“可視”的申請的衛(wèi)星資源處于占用狀態(tài)，則申請的狀態(tài)值由“可視”轉為 “沖突”；

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

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

規(guī)則13：如果申請的狀態(tài)值為“納入計劃”，則調用衛(wèi)星資源分配函數(shù)將申請寫入計劃表。

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

圖3 申請的狀態(tài)機

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

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

圖4 Drools規(guī)則結構

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

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

rule “IsvisiableRule” //規(guī)則名稱

salience 10 //規(guī)則優(yōu)先級

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

when

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

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

Then

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

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

end

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

3.4 基于Drools的任務調度規(guī)則引擎的改進

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

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

規(guī)則組一：

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

規(guī)則組二：

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

規(guī)則組三：

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個規(guī)則組對應的推理網(wǎng)如圖5所示。

圖5 推理網(wǎng)

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

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

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

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

3.5 調度系統(tǒng)驅動數(shù)據(jù)及其表示

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

表1 用戶申請

4 實 驗

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

4.1 實驗環(huán)境與數(shù)據(jù)概述

本文實驗的原型系統(tǒng)在eclipse中開發(fā)，規(guī)則引擎為Drools6.5，數(shù)據(jù)庫為MySQL8.0，服務器為TomCat7.0，運行平臺為windows10，CPU:Intel i3-3110M 2.4GHz。

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

4.2 實驗結果

系統(tǒng)運行時間的統(tǒng)計結果和申請?zhí)幚斫Y果如圖6和表2所示。

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

圖6 系統(tǒng)運行時間折線

表2 系統(tǒng)運行時間特征及申請調度結果統(tǒng)計

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

5 結束語

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