一種無線網絡控制系統概率性任務實時調度算法

林 強，吳國偉，劉玥瑤，王文超

（1.大連理工大學 軟件學院，遼寧 大連 116024；2.大連科技學院，遼寧 大連 116052）

0 引 言

無線網絡控制系統（wireless networked control system，WNCS）是當前社會各界廣泛關注的研究領域，是涉及多學科、知識高度集成的前沿熱點［1］.WNCS 的核心部分是傳感器網絡，系統通常包括傳感器節點、匯聚節點和管理節點.在監測區域內部或附近隨機放置大量傳感器節點，監測數據順著傳感器的節點傳輸，經過多跳后路由到匯聚節點，最后通過互聯網或衛星到達管理節點.用戶通過管理節點對傳感器網絡進行配置和管理，發布監測任務以及收集監測數據.

傳感器網絡節點的組成和功能包括如下4個基本單元：傳感單元（由傳感器和模數轉換功能模塊組成）、處理單元（由嵌入式系統構成，包括CPU、存儲器、嵌入式操作系統等）、通信單元（由無線通信模塊組成）、電源.

因為無線傳感器網絡有自組織性、網絡動態變化、消耗能量、分節點電量有限等特點［2］，必須合理調度分配無線傳感器網絡中的任務，達到減少能量消耗、延長系統生命期、加快完成任務的速度和提高系統節點使用效率的目標［3］.

自Liu和Layland在20世紀70年代初發表了關鍵論文以來，有關無線傳感器網絡實時任務調度的方法層出不窮，而這些方法的基礎都是基于優先級以及截止時間優先的傳統方法.最開始的調度策略是最早截止時間（EDF）［4］以及最壞情況下的調度，雖然有一些局限性，但是其思想在當時還是比較先進的.本文對無線傳感器網絡實時系統任務調度的研究集中在時間及優先級分配上，即在提高任務完成率的同時減少任務完成時間，提高系統性能并延長系統生命周期.

1 隨機調度策略

無線傳感器網絡任務調度是為了把一組任務用確定的調度策略，確定其調度簇，即分配同一節點執行的任務，并且控制任務的執行順序和時間，確保任務能夠高效完成［5］.

1.1 隨機調度概述

自Liu和Layland提出開創性觀點以來，用最壞情況方法對關鍵系統時間分析的研究進行了很長時間.然而這些方法在提升性能方面表現得太過悲觀，因此在實時系統領域，設計實時調度算法很具挑戰性.在復雜結構中，程序執行時間的變化意味著最壞情況方法會歸結為系統不可行.因此，有些時候最壞情況方法限制新功能的引入，并把它作為結構的重要考量.

隨機方法可以替代最壞情況方法.一般地，實時系統的可行性以系統參數各種可能出現的值的概率來表示.近年來，實時系統的隨機性分析得到發展，涌現了隱式任務模型（亦稱Liu和Layland模型）、復合框架模型（MF）、拓展復合框架模型（GMF）、周期實時模型（RRT）等.

隨機模型是現在最具表現潛力的模型，由于它的概率性，任務的每個參數相互聯系.隨機模型能夠描述同一個任務中不同作業之間的關系，是最接近RRT 的任務模型.

1.2 標記和定義

隨機變量χ有分布函數（PF）fχ（·）：fχ（x）＝P（χ＝x），χ∈［xmin，xmax］.

隨機變量的可能取值和概率的關系表示如下：

兩個隨機變量X和Y是相互獨立的，表示一個事件的結果對另一事件無影響.

變量X和Y的卷積Z稱為兩個變量的累積和，即

1.3 隨機模型

考慮一個系統同時釋放n個任務｛τ1，τ2，…，τn｝，需要在單處理器上用固定優先級調度策略.不失一般性地，認為對于i＜j，τi優先級大于τj，hp（i）表示比τi優先級高的任務集.每個任務τi產生無窮多個連續的作業τi，j，j＝1，…，∞.

一項任務的一個作業的隨機執行時間（pET）表示概率性的執行時間，等于一個給定的值.每個任務τi被泛化為一個不定時發生的任務［6］，并且用隨機最壞情況執行時間（pWCET）和隨機最小到達時間（pMIT）來定義.

一項任務的pWCET 記作Ci，范圍是Cji，j，并且可以用關系≥來表示：Ci≥Cji，j.從圖像上看，這意味著Cji的累積分布函數一直低于Ci，j.

Ci可以寫作

例如一個任務τi，有Ci＝得出fCi（2）＝0.50，fCi（3）＝0.45，fCi（25）＝0.05.

用同樣的方法將pMIT 記作Ti.pMIT 范圍是pITTji，j，并且Tji≥Ti，j.

一個任務τi可以用二元組（Ci，Ti）表示.一個任務的某個作業需要在下一個作業到達之前完成執行，即新作業的到來代表著當前作業的截止時間.所以，一個任務也可以用一個隨機變量Di表示，和pMIT 的Ti有一樣的作用.

通過考慮最壞情況的概率值（pMIT 或pWCET），用隨機的獨立變量來表達pMIT 和pWCET［7］.這種獨立性是因為pMIT 和pWCET是邊界而不是任務執行的確切值.由這個獨立的性質，利用卷積計算任務的響應時間等.

任務的響應時間是從激活到執行結束的時間.作業有pET，因此響應時間也可以用隨機變量來描述.

約束條件用錯過截止時間的概率描述，作業τi，j的失敗概率DMPi，j是指任務τi的第j個作業錯過截止時間的概率，即

Ri，j是任務τi的第j個作業的響應時間的分布.

如果有計劃的任務是周期性的，換句話說pMIT 分布有一個概率值1，然后任務失敗的概率可以計算為作業的平均失敗概率，這些作業在時間段［a，b］內被執行，這就是調度的超周期.一個最壞情況的推論只能考慮所有執行在時間段［a，b］所有作業的DMP中最大的DMP（失敗概率）.

對于一個任務τi和一個時間段［a，b］，任務的失敗概率可以計算為

n是活躍在時間段［a，b］一個任務作業τi的作業的數量.

2 隨機調度算法改進

2.1 單調速率算法概述

（1）任務τi（Ti，Ci，Di）模型

Ti為任務i的周期，Ci為任務執 行時間，Di為截止時間且為周期終點.任務在周期的起點釋放，高優先級任務可以搶占低優先級任務.

（2）優先級分配方法

即靜態固定優先級分配.利用線性關系優先級與周期成反比，周期越短優先級越高.

（3）可調度性分析

n個獨立的周期任務組成的任務集τ可以被單調速率算法調度，如果U≤n（21／n－1），則該任務集可調度.其中U為實時系統周期任務集的負載

在靜態調度中，首先提出任務的臨界時刻（critical instant）的概念.定義其為一個特定時間點，如果在此時刻有任務提出請求，那么此任務就需要最大響應時間（最壞情況）.

性質1 一個任務的臨界時刻就是所有比此任務優先級高的任務hp（i）同時發出請求的時刻.

上述的價值在于它找到了一個調度算法在任何情況下（包括最壞情況），能否調度任一任務集的充分必要條件，即為在所有任務同時請求執行的情況下仍能保證每個任務滿足相對截止時間（時限）完成任務，那么就可以用這個調度算法來對這個任務集進行調度.

性質2 如果一個任務集能夠被靜態調度，那么就能夠用單調速率調度算法調度這個任務集.

單調速率調度算法已證明是靜態最優調度算法，開銷小，靈活性好，是實時調度的基礎性理論.即使出現特殊情況如系統瞬時過載，也可前瞻定位丟失時限的任務.缺點是處理器利用率較低，因此對于許多復雜任務實時應用有很大的限制.

2.2 調度算法改進

2.2.1 隨機實時調度 本節將呈現單處理器上固定優先調度算法的結果.此處研究的任務有單一的參數，用一個隨機變量表達，即Ci.考慮有n個任務的集合τi，i∈｛1，2，…，n｝，用（Ci，Ti，Di，p）表示，p∈［0，1］表示任務τi錯過它的截止時間的最大概率.在第一個超周期［0，P］來研究調度，P＝lcm｛T1，T2，…，Tn｝.

固定優先級調度算法問題（BPAP），需要為每個任務分配優先級，每項任務的DMR不能超過臨界值，即DMRi（Φ）≤pi.

定理1 系統τ＝｛τ1，…，τn｝有n個同時釋放的任務且有pWCET.對于這個系統，單調速率（RM）不是最優的，因為有一個可行的任務優先級分配，但是單調速率不一定能做到此情況下的優先級分配.

證明 設τ＝｛τ1，τ2｝是一個有兩個周期性任務及pWCET 的系統.把τ1和τ2分別設定為作業τ1需要滿足至少截止時間的50%，作業τ2為75%.

根據RM 優先級分配算法，τ1有最高的優先級，τ2有最低的優先級.假若這樣，τ1將會滿足所有它的截止時間，顯然也滿足要求的50%的限度.然而，τ2將不能滿足截止時間的75%，只有50%（圖1）.

因為優先級的不同引起響應時間不同，并且調整優先級后滿足截止時間的概率改變，從而產生優先級分配策略的影響，檢驗單調速率算法在特殊情況的最優性是否還存在.現在考慮作業τ2有最高優先級，作業τ1有最低優先級，然后兩個任務都能滿足它們各自的限制要求.這樣的話，τ2滿足它的截止時間的概率為100%（高于要求的75%），τ1將滿足截止時間的50%（圖2）.

圖1 單調速率調度算法調度結果Fig.1 Rate monotonic scheduling result

圖2 合適的優先級調度策略Fig.2 A feasible assignment of priorities

引理1（最高級的順序定理［8］） 設τ＝｛τ1，…，τn｝是n個任務的任務集并且用pWCET來約束，任務在一個用固定優先級搶占調度策略的單處理器上調度.如果任務有固定和已知的優先級，那么比τi更高優先級的任務集hp（i）的內部順序不影響任務τi的任何作業j的DMPi，j（Φ）的值且不影響DMRi（a，b，Φ），a，b的值.

2.2.2 隨機調度系統優先級算法 由于技術發展，系統很少可能錯過截止時間，時間約束不再合適，所以沒有必要設置一個系統功能數量的低界限，而是進行隨機分析.

引理2（響應時間的單調性） 在某一個任務分配Φ中降低某一任務τi的優先級，其響應時間會增大.優先級越低，來自高優先級的沖突越多，響應時間越長，錯過截止時間概率越大.

基本優先級分配問題最優算法［8］：令Γ是一個截止時間限制的任務集，任務有隨機執行時間并且表示為（Ci，Ti，Di，p）.對于任何任務集Γ，總能找到一個切實可行并且存在的優先級分配方案.

在基本優先級分配貪心算法上進行一些改進.從最低等級的任務開始分配優先級，直到最高級.當給任務τi設定了某一個優先級，不必擔心已經被設定了更低優先級的任務集lp（i），因為這不影響τi的響應時間（引理1）.

現在提出改進的算法.

基本的優先級分配最優算法：使得所有的任務τi滿足DMRi≤pi

改進的地方是將待分配的任務按照最壞失敗概率也就是按照pi的值進行從大到小排序，根據引理2如果最壞DMR越小則需要將任務的優先級分配得越高，這樣可以減少由于貪心算法導致的中途分配失敗的情況，從而提高算法的分配速度.

這個算法是貪心算法.可能存在一個未分配優先級的任務τ，如果分配當前優先級k不會讓最差的DMR更差，也就是不超過pi，就把優先級k分配給此任務，而不考慮高優先級會發生的情況.這個算法在解決當前優先級固定分配問題上效率比較高，對每一個任務都進行檢測，若適合就分配優先級.而如果所有任務都不滿足某一優先級的條件，那么該優先級分配失敗.

2.2.3 可調度性分析 考慮一個具有n個同步釋放的任務的任務集｛τ1，τ2，…，τn｝，在單處理器上使用固定任務優先級的搶占調度策略.不失一般性地，當i＜j時，認為τi比τj有更高的優先級，任務τn在被研究的n個任務中具有最低的優先級.

任務τi，j的響應時間Ri，j可由下面的公式計算得出：

Bi（λi，j）是在λi，j之前釋放的具有較高優先級的任務累積和，并且在λi，j時刻尚未終止執行.Ii（λi，j）是在λi，j之后到達的并且可以搶占任務τi，j的較高優先級的任務的最壞情況的執行時間pWCET 的累積和.在同時釋放任務的情況下，這些任務pWCET 的累積和為

式（5）可以進行迭代求解，新的搶占任務的整合是通過修改任務在每個新迭代的概率分布解決的.當沒有更多的搶占任務或者任務的完成時間已經大于最后完成時間時，迭代終止.

式（5）基于卷積運算，這要求任務變量Ci，i在概率上相互獨立.

pET 的情況：如果隨機變量Ci描述任務的pET，隨機變量不能獨立，在這種情況下，任務的當前狀態不能使用式（5）來解決.

pWCET 的情況：如果隨機變量Ci描述任務τi的pWCET，隨機變量是獨立的，因為它們是pET 的范圍，所以式（5）是可用的.

考慮之前的例子，τ＝｛τ1，τ2｝是一個有兩個周期性任務及pWCET 的系統，把τ1、τ2分別設定為

當任務τ2的優先級低于τ1時，使用式（5）計算第二個任務τ2的第一個作業τ2，1的響應時間，R2，1＝B2（λ2，1）C2I2（λ2，1），其 中λ2，1＝0，I2（0）.當I2（0）任務τ1可能的3個值：τ1，2在t＝2，τ1，3在t＝4，τ1，4在t＝6 時，代入得到R2，1＝

3 任務調度算法仿真

本章將對基于隨機模型提出的改進的固定優先級分配算法的正確性和有效性進行仿真驗證.實驗設定了多個具有代表性的實驗用例（僅舉1例），多角度全面進行仿真，并將結果與傳統算法進行對比，總結分析改進算法的性能.

實驗用例1Γ＝｛τ1，τ2｝，

仿真結果顯示，τ2優先級最高，其次為τ1，DMR2＝0，明顯小于0.1，DMR1＝0.387 5，且小于0.5，符合要求，算法結果正確.

下面分析實驗用例1，如果用單調速率算法，T1＜T2，所以τ1的優先級比τ2的高，按照這個優先級分配算法來計算DMR.τ1的每個任務響應時間都為因此得出兩個計算結果：即R2＝所以DMR2＝0.125＞0.1.因此這種優先級分配算法不可行，不符合優先級分配算法的基本要求，同時也證明了單調速率算法在這種任務模型的非最優性.

4 結 語

本文研究了目前已有的任務調度和優先級分配理論，在分析了傳統算法的缺點和任務調度問題的隨機性與動態性之后改進了固定優先級分配算法并進行了仿真實驗和性能比較，分析出本算法的優越性.

［1］ 任豐原，黃海寧，林 闖.無線傳感器網絡［J］.軟件學報，2003，14（7）：1282－1291.REN Feng－yuan，HUANG Hai－ning，LIN Chuang.Wireless sensor networks［J］.Journal of Software，2003，14（7）：1282－1291.（in Chinese）

［2］ Park H，Srivastava M B.Energy－efficient task assignment framework for wireless sensor networks［R］.Los Angeles：Center for Embedded Network Sensing，University of California，2003.

［3］ 吳光斌，梁長垠.無線傳感器網絡能量有效性的研究［J］.傳感器技術，2004，23（7）：74－76.WU Guang－bin，LIANG Chang－yin.Research of energy－efficiency for wireless sensor networks［J］.Journal of Transducer Technology，2004，23（7）：74－76.（in Chinese）

［4］ Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard real－time environment［J］.Journal of the ACM，1973，20（1）：46－61.

［5］ 郭文忠.無線傳感器網絡任務調度若干關鍵技術研究［D］.福州：福州大學，2010：4－8.GUO Wen－zhong.Research on some key technology of task scheduling in wireless sensor networks［D］.Fuzhou：Fuzhou University，2010：4－8.（in Chinese）

［6］ Mok A.Fundamental design problems of distributed systems for the hard－real－time environment［D］.Boston：Laboratory for Computer Science，Massachusetts Institute of Technology，1983：35－54.

［7］ Stappert F，Altenbernd P.Complete worst－case execution time analysis of straight－line hard realtime programs［J］.Journal of Systems Architecture，2000，46（4）：339－355.

［8］ Maxim D，Buffet O，Santinelli L，etal.Optimal priority assignments for probabilistic real－time systems［C］／／Proceeding of the 19th International Conference on Real－Time and Network Systems（RTNS）.Nantes：IEEE Computer Society，2011：2－8.