[發明專利]邊緣計算環境下基于強化學習的DIDS任務調度算法

有效

• 申請號: 202110059634.4
• 申請日: 2021-01-18
• 公開（公告）號: CN112839048B
• 公開（公告）日: 2022-10-28
• 發明（設計）人: 趙旭;薛濤;趙子江
• 申請（專利權）人: 西安工程大學
• 主分類號: H04L9/40
• 分類號: H04L9/40;H04L67/60;G06F9/50
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 戴媛

1.一種邊緣計算環境下基于強化學習的DIDS任務調度算法，其特征在于：具體包括如下步驟：

步驟1、工作開始前，對分布式入侵檢測系統中的各檢測引擎進行的性能評估，收集其對測試流量的檢測時間dt和內存占用mu信息，并將作為檢測引擎的性能指標；對所有檢測引擎測試后，根據性能高低將其分成不同等級d,d＝1,…,D，d值相差在10％以內的，可歸為同一等級；

步驟2、開始工作后，當一個數據包到來需要檢測時,調度器首先獲取數據包長度，對數據包產生的負載進行評估，評估方法是通過數據包長度與以太網最大傳輸單元MTU1500Bytes的比值，得出該數據包所產生的負載等級k,k＝1,…,K；k值相差在10％以內的，可歸為同一等級；

步驟3、利用強化學習就所要解決的具體調度問題建模，調度器通過模型進行決策，決定分配哪個性能等級的檢測引擎去檢測這一數據包；

所述步驟3的具體過程如下：

步驟3.1，基于步驟3，定義參數；

步驟3.2，基于步驟3.1所得結果確定狀態空間；

步驟3.3，基于步驟3.2所得結果確定決策時刻；

步驟3.4，基于步驟3.3所得結果確定動作集合；

步驟3.5，基于步驟3.4所得結果確定轉移速率與轉移概率；

步驟3.6，基于步驟3.5所得結果確定價值函數和最優策略；

步驟3.7，基于步驟3.6所得結果進行策略迭代；

所述步驟3.1的具體過程為：

分布式入侵檢測系統有D個性能等級的檢測引擎對K個負載等級的數據包的檢測需求,檢測時間服從指數分布,數據包的到達過程可以看作K個獨立的泊松過程；評判準則采取平均負載準則；考慮數據包到達和檢測結束的時刻,那么此時嵌入鏈是馬爾科夫鏈；

下面對后文將使用的各種標記進行說明:

所述步驟3.2的具體過程為：

將s＝(N(D,K),B(K),r)設為狀態,其中N(D,K)是一個向量,具有形式(n₁₀,n₁₁,…,n_1K-1,n₂₀,…,n_DK-1),描述了分布式入侵檢測系統的工作狀態,包括尚未分配檢測任務的檢測引擎的分布以及正在為各等級數據包檢測的檢測引擎狀況；B(K)也是一個向量，而且具有形式(b₁,b₂,…,b_K),描述了正在等待檢測的數據包情況,包括各種數據包的數量；而r取值于集合{K,K-1,…,1,0},描述最一個到達的數據包的情況；當隊列長度的限制b確定以后，就可以定義一個含有所有可能狀態的集合X，如公式1所示；

在上式中，b＞0是允許的隊列長度；

下面列出集合X中的幾種典型的可能狀態

1)系統里如果有空閑的檢測引擎，剛好有一個數據包到達，經過負載評估是第j等級數據包，那么X₁作為X集合中的一個狀態，如公式2所示

其中狀態(N(D,K),B(K),j)表示新到的數據包帶來了第j等級的檢測需求；

2)系統里沒有可用的檢測引擎時的所有可能狀態X₂可以表示為下式

3)系統里仍有空閑的檢測引擎且無數據包等待檢測的所有可能狀態X₃可以表示為下式，此時r＝0，

4)系統里只有一個空閑的檢測引擎且有等待檢測的數據包的所有可能狀態，這種情況比較少見，

所述步驟3.3的具體過程為：

當一個新的數據包到達，需要調度器分配一個檢測引擎進行檢測，這時發生了系統狀態的變化，所以調度器需要做出決策，選擇執行對應的行為，當一個檢測引擎完成對某個數據包的檢測時，這個行為的執行使得系統的狀態也發生了改變，使系統當前的狀態轉移到狀態空間中另一個狀態；

所述步驟3.4的具體過程為：

在步驟3.2列出的幾種情況中，對于X₁中的狀態，調度器需要進行決策指派何種等級的檢測引擎來處理這個數據包，對于X₄中的狀態，系統需要考慮目前唯一空閑的檢測引擎應該檢測隊列中何種的等級數據包，對于X₂和X₃中的狀態，系統不需要做出選擇；所以狀態空間X的動作集合A(·)定義為

A(s)＝{d|n_d0＞0,d＝1,2,...,D},s∈X₁

A(s)＝{0},s∈X₂

A(s)＝{0},s∈X₃

A(s)＝{k|b_k＞0,k＝1,2,..,K},s∈X₄ (6)

動作集合中的0表示不需要作出決策，動作k∈A(s)(s∈X₄)表示由系統里唯一空閑的檢測引擎去處理一個等待的k等級數據包，而d∈A(s)(s∈X₁)表示由第d等級的檢測引擎去檢測剛剛到達的數據包；

所述步驟3.5的具體過程為：

轉移概率是依賴于系統當前所處的狀態和調度器選取的行動來決定；中因為使用的是馬爾科夫決策過程，所以轉移概率可以通過轉移速率求得；而轉移速率可以分為下面的幾種情況確定:

1)對于X₁中的狀態s，當k等級的數據包到達，調度器選擇與之對應的d等級檢測引擎去檢測，此時，會出現兩種可能的轉移：

I)轉移到狀態s'∈X₃，其轉移速率為

這里的s'∈X₃表示一個i等級的檢測引擎恰好完成對一個j等級數據包的檢測；

II)轉移到狀態s'∈X₁∪X₂，其轉移速率為q(s'|s,d)＝λ_j，s'∈(X₁∪X₂)表示一個j等級的數據包到達；

2)對于X₂中的狀態s，也會發生兩種轉移:

I)轉移到狀態s'∈X₄，其轉移速率為q(s'|s,0)＝n_ijμ_ij,s'(∈X₄)表示一個i等級檢測引擎恰好完成一個j等級數據包的檢測；

II)轉移到狀態s'∈X₂，其轉移速率為q(s'|s,0)＝λ_j，s'(∈X₂)表示一個j等級的數據包到來；

3)對于X₃中的狀態s,只有可能發生兩種轉移：

I)s′∈X₃,其轉移速率為q(s'|s,0)＝λ_j，s′(∈X₃)表示一個j等級的數據包到來；

II)s′∈X₁，其轉移速率為q(s'|s,0)＝n_ijμ_ij，s'(∈X₁)表示一個i等級檢測引擎恰好完成一個j等級數據包的檢測；

4)對于X₄中的狀態s,n_k0＞0，采取行動k，可能會發生兩種轉移：

I)轉移到狀態s′∈X₃∪X₄,其轉移速率為

s′∈X₃∪X₄表示一個i等級檢測引擎恰好完成一個j等級數據包；

II)轉移到狀態s'∈X₂,其轉移速率為q(s'|s,k)＝λ_j，s'(∈X₂)表示一個j等級的數據包到來；

除了上面已經定義的元素以外,轉移速率矩陣的非對角元素全部都是0；轉移速率矩陣的對角元素可以定義為

對任何的確定性策略f∈F,可以得到對應的轉移速率矩陣Q(f).根據連續時間的馬爾科夫決策過程理論,得到轉移概率矩陣P(f)為

P(f)＝λ^-1[Q(f)]+I (10)

其中λ滿足

對于轉移速率矩陣Q(f)，將每一行除以該行對應對角線上的元素以后，再加上一個單位矩陣，也可以得到一個嵌入馬爾科夫鏈的轉移概率矩陣P'(f)；通過這兩種不同方法得到的系統，它們的最優策略和對應的值函數都是相同的；

所述步驟3.6的具體過程為：

設定l_k為檢測第k等級數據包對檢測引擎帶來的最小負載，l_k依賴于要檢測的數據包的負載等級k；平均負載l_dk取決于檢測引擎的性能等級d和數據包的負載等級k，考慮到檢測時間的分布是指數分布,那么在狀態s時采取行動a的期望負載為

上式也就是基于策略f的狀態-行為價值函數((state-action value function)q_f(s,a)，所以q_f(s,a)＝l(s,a)；

使用平穩策略f時,希望的最小的平均負載準則是

在上式中，Y_i是決策時刻i的狀態，s是初始狀態，τ_i是決策時刻i的平均滯留時間；這樣，一個連續時間的馬爾科夫決策過程系統就形成了；考慮到行動集和狀態空間都是有限集合，所以可以得出：對于平均最小負載準則，存在確定性平穩最優策略f^*滿足g(f^*,s)≤g(f,s),對所有f∈F和s∈X，f^*是最優策略；

所述步驟3.7的具體過程為：

通過以上步驟的推導，可找到實現最小負載的最優策略f^*；在尋找更小的g(f^*,s)過程中，可以使用策略迭代Policy Iteration；策略迭代算法包含了策略估計的過程，而策略估計則需要對所有的狀態掃描sweep若干次，這個過程所產生的巨大的計算量會影響策略迭代算法的效率，實際上價值函數的值沒有必要計算的非常精確，為了縮短策略估計的過程，可采用值迭代的方法；值迭代的具體方法是依靠循環的方式通過對不同動作下的g(f,s)進行計算，如果小于收斂閾值便可以確定；

步驟4、當一個檢測引擎完成檢測后，如果調度器沒有再分配別的檢測任務，它將暫時空閑；

步驟5、當一個檢測引擎還被分配有其他檢測任務時，它將馬上去完成調度器指派的另一檢測任務；

步驟6、當一個檢測請求到來時,如果分布式入侵檢測系統中沒有空閑的檢測引擎,調度器將記錄這一檢測請求并放入隊列,一旦隊列滿額,這個新到的數據包將不得不被放棄檢測；如果分布式入侵檢測系統中有空閑的檢測引擎時,將不會將數據包放入隊列等待。