基于PSO的控制系統中周期性任務的優化調度

王得利

（唐山市人才交流中心，河北 唐山 063000）

1 引言

實時控制系統是運行于計算機系統上，主要完成數據采集、控制計算、控制輸出及報警等功能實時系統。為了充分利用處理器資源，減少系統的軟硬件投資，往往在一個處理器上處理多個回路。而系統中的任務必須在一定的時間內完成，否則會出現災難性后果[1]，這就涉及了實時多任務的調度問題。

針對實時任務的調度算法，Liu和 Layland[2]給出了著名的RMS算法和EDF算法，這兩種算法都是針對周期性任務的調度算法。然而控制系統的性能與控制系統的采樣周期有關[3－4]，因此出現了結合對系統性能進行優化的調度算法。文獻[4]給出了計算優化采樣頻率的方法；文獻[5]給出了使系統性能優化的動態調度算法。但是這些優化調度算法過于復雜。因此本文基于PSO算法設計控制系統的優化調度算法。

2 任務模型

典型的數字控制系統如圖1所示。實際上這只是一個控制回路，根據系統的需要它將完成多種功能，各功能之間既相互聯系、相互影響又相互獨立，因此可以看作一個任務，這是一個周期性任務。另外系統的采樣周期并非固定不變的，在保證控制回路穩定的前提下，根據系統的動態、靜態性能指標要求以及對象的數學模型可以確定回路的采樣周期[6]，這是采樣周期最大值，記為，而為了保證系統的正常運行，系統的采樣周期存在最小值（如必須大于該控制回路的采樣、控制計算和控制輸出的執行時間），記為。

在控制系統中，一般來說當控制算法、數據采集和控制輸出的方法確定后各任務的執行時間是確定的。

圖1 實時控制系統的結構

基于以上分析，我們給出控制系統的周期性任務模型如下：

定義1一個控制系統中的任務集可表示為

其中n≥1，iτ為一個回路任務，可表示為如下的形式

控制系統中除了回路任務外，還存在諸如報警等非周期任務。這類任務只要在一定的時間內調度完成即可，故可通過給非周期任務預留一定的處理器資源來實現對其調度，如采用帶非周期服務器的調度算法[1]，因此本文主要研究回路任務的優化調度算法。

定義2若所有回路任務的所有實例都能在其時限之前完成，則稱任務集S是可調度的。

為了分析合設計調度算法的方便，本文做如下假設：

（1）回路任務之間相互獨立，回路任務時限等于周期；

（2）所有的任務在同一處理器上完成。

3 調度算法及優化

由任務模型可知，控制系統中的任務均為周期性任務，故可采用 Liu和 Layland[2]給出了著名速率單調調度算法（RMS）和最早截止期優先調度算法（EDF），考慮到EDF可以獲得更高的處理器利用率，本文采用搶占式 EDF調度算法。由文獻[2]可知，EDF調度算法的可調度條件如下：

引理1對于周期性任務集，采用搶占式EDF算法，當且僅當

時，任務集是可調度的。

根據Seto[4]的研究，控制系統的性能與采樣周期和控制延遲有關，它們與控制系統的二次性能指標存在如下關系：

式中 ci, ai常數，可通過控制算法曲線獲得。由文獻[4]可知，Ji越小系統性能越好。由于各控制回路重要性不盡相同，結合前面任務的可調度性和采樣周期的取值范圍，則優化問題為：

約束條件：

當前的優化調度算法[3-5]過于復雜，本文基于優化搜索算法尋求最佳的采樣周期。搜索算法中 PSO是一種源于對鳥群捕食行為的優化迭代算法，該算沒有遺傳算法中的采用交叉和變異操作，沒有許多參數需要調整，因而實現簡單。為去掉(5)式中的第一個不等式約束條件，采用懲罰函數法[7]，并通過準精確懲罰函數，使得優化問題變為：

式中M為正常數，用于調整對不合法個體的懲罰程度，則約束條件化為

粒子群算法將每個個體視為在n維搜索空間中，以一定速度飛行的沒有質量和體積的粒子。每個粒子的飛行速度據其本身的飛行經驗和群體的飛行經驗進行調整。假設在n維目標搜索空間中，有m個粒子組成一個群落，其中第i個粒子表示為。在n維搜索空間中的位置為Ti，每個粒子的位置代表一個潛在的解。第i個粒子的飛行速度為n維向量，記為。記第i個粒子迄今為止搜索到的最優位置為，對應的適應值為pBest，整個粒子群迄今為止搜索到的最優位置為，對應的適應值為gBest。每個粒子的速度和位置按方程(8)和(9)進行迭代

式中 j,t均為1,...,n，t為迭代次數；ω為慣性權重，ω≥0；c1,c2為學習因子，也稱加速因子。這兩個參數對粒子群算法的收斂起的作用不是很大，但如果適當調整這兩個參數，可以減少局部最小值的困擾，當然也會使收斂速度變快。為粒子i目前位置到粒子i迄今為止搜索到的最優位置在第j維上的距離；為粒子i目前位置到整個粒子群迄今為止搜索到的最優位置在第j維上的距離。

4 調度算法的仿真

為了驗證前述方法的有效性，我們進行如下仿真，來考察對回路任務采樣周期的優化情況。每個任務的最大采樣周期在800到1000之間隨機生成；每個任務的最小采樣周期取為該任務最大采樣周期的0.6倍；每個任務的權重是在0到1之間歸一化生成的隨機數；每個任務的執行時間在0到0.1倍的最大采樣周期之間隨機生成。按照上述任務參數生成方式，隨機生成10個回路任務，任務參數如表1所示。

表1 控制系統回路任務參數

利用粒子群優化算法，采用前述算法流程，對上述 10個周期性任務的采樣周期進行優化。設該粒子群中有粒子80個，共進行250次迭代。仿真后所得結果如表2和圖2所示。利用 PSO算法，優化搜索了各個回路任務的最優采樣周期。

表2 單處理器控制系統仿真結果

圖2 控制系統平均目標函數和迭代次數之間的關系

利用表2的數據，根據處理器利用率計算公式

對單處理器的利用率進行計算，處理器的利用率為 0.999 991。該處理器的利用率非常接近于 1，表明采用本文所提出的單處理器控制系統的任務調度策略和回路任務采樣周期優化方法，在滿足所有回路任務均可調度這一前提下，系統計算資源的利用率很高。

同時，由圖2可見，盡管最終進行了250次迭代，在第50次迭代時，平均目標函數值就已從約120收斂至約20左右，可見收斂速度快，運算效率之高。采用粒子群優化搜索算法，平均目標函數值從第0次迭代的120.9945被優化至第250次迭代的20.74327，優化幅度約為82.856%，優化效果顯著。

5 結論

研究了控制系統中周期性任務，分析任務特性，給出了任務模型。為了提高處理器資源利用率，采用了 EDF調度算法。基于此，采用 PSO算法給出了控制任務采樣周期的優化求取算法。仿真實驗表明，本文給出的基于PSO的控制任務優化調度算法是有效的。