無線傳感器網絡操作系統調度策略研究
2009-01-01 00:00:00羅鈞吳志
計算機應用研究 2009年1期
(重慶大學 光電技術及系統教育部重點實驗室， 重慶400030 )
摘 要：針對無線傳感器網絡的特點，分析了無線傳感器網絡對于任務調度的特殊需求，提出了一種基于反饋控制的動態集成調度算法。該算法將簡單反饋控制與任務準入/回歸控制、可達/夭折等策略相結合，設計了新的動態調度框架。該框架適用于對任務的多種特征參數的綜合。最后從截止期錯失率、對關鍵任務的優先執行能力和CPU有效利用率三個方面分析了算法的性能。實驗結果表明，該算法在無線傳感器網絡環境下與最早截止期優先和固定優先級算法相比具有更好的性能。
關鍵詞：無線傳感器網絡；任務調度；反饋控制；截止期錯失率
中圖分類號：TP316.2 文獻標志碼：A
文章編號：10013695(2009)01016203
Research on tasks scheduling strategy in wireless sensor network operating system
LUO Jun，WU Zhi
（Key Laboratory of Optoelectronic Technology System ofMinistry of Education， Chongqing University， Chongqing 400030， China）
Abstract:
Aimed at the characteristics of the wireless sensor network， analyzed the special needs of task scheduling. Basing on feedback control， proposed a dynamic integrated strategy scheduling algorithm.The algorithm used simple feedback control and the access/recover control， reachable/abortion strategy and so on to unify， designed a new dynamic scheduling framework. This framework could be applied to integrate a variety of characteristic parameters. Finally， analyzed the performance of algorithm from the three aspects of missed deadline percentage， the priority implementation ability of critical tasks， and CPU efficacious utilization. Compared with earliest deadline first and fixed priority algorithm. Experiment results show that the algorithm achieves higher performance in the wireless sensor network environment.
Key words:wireless sensor network;task scheduling;feedback control;missed deadline percentage
隨著無線通信和電子信息技術的飛速發展，無線傳感器網絡表現出越來越廣泛的應用前景。目前，無線傳感器網絡正越來越多地被應用在各個特殊的應用領域中，如軍事、環境、空間探索以及其他多種商業應用領域。在這些應用中，絕大多數的應用領域都要求無線傳感器網絡系統能滿足實時性要求。例如實現動態測量功能，在動態測量時要求傳感器在時限內完成數據采集、計算、處理和輸出，這就要求無線傳感器網絡具備非常好的實時性能。因此，如何在資源受限的情況下實時地完成感知、通信、控制和計算工作是無線傳感器網絡研究面臨的主要問題。解決這個問題的關鍵是如何在軟件上對系統資源進行合理的分配和管理[1]，即需要研究滿足無線傳感器網絡特殊要求的操作系統調度策略。
現有的無線傳感器網絡操作系統中，最常見的是先來先服務(first come first service，FCFS)調度策略。TinyOS和文獻[2]設計的無線傳感網絡操作系統ZUOS都是采用FCFS的調度策略。FCFS調度策略簡單易實現，但是可調度性差，且難以保證重要任務的有效執行[3]。文獻[4]提出了基于最早截止期優先(earliest deadline first，EDF)調度策略的ISEDF調度算法，有效地提高了任務的調度成功率，但在系統負載較重時可調度性變差，同時難以保證關鍵任務的優先執行。文獻[5]提出了一種基于RM(rate monotonic)調度策略的緊急任務優先(emergency task first rate monotonic，EFRM)調度策略，有效地保證了重要任務的優先運行。但是RM算法是一種典型的固定（靜態）優先級調度策略，主要用于靜態周期任務的調度，難以適應多變的無線傳感器網絡環境[6]。以上的任務調度策略都或多或少地在無線傳感器網絡應用上存在一定的局限性。因此，迫切地需要研究一種更適合無線傳感器網絡特點的任務調度策略，以提高無線傳感器網絡的性能。
1 任務調度模型
在確定任務調度策略前，需要建立一個基于無線傳感器網絡的任務調度模型，并在此基礎上進行任務屬性及任務調度和可調度性分析。
通過對無線傳感器網絡節點行為過程的分析，可以把任務分成以下四大類：
a)感知任務。傳感設備從外界環境收集信息，并對收集的信息進行處理，完成數據采集功能。用Ts表示。
b)激勵任務。處理器產生控制信號，并傳輸給激勵裝置，控制激勵裝置影響外界環境，完成特定功能。用Ta表示。
c)接收任務。接收其他傳感器或中心機的請求或數據，采取相應的操作，完成相應的功能。用Tr表示。
d)傳輸任務。通過通信裝置發布當前節點的狀態信息，或者發送被請求的數據給其他節點或中心機。用Tt表示。
對無線傳感器網絡節點來說，其主要功能是實現對外部環境的檢測或控制，尤其是那些負責動態采集數據的傳感器。它們需要實時檢測和控制外界環境。因此，從這個角度出發，可以定義感知任務Ts和激勵任務Ta為硬實時任務；而相對應的接收和傳輸任務不是那么重要，接收任務Tr和傳輸任務Tt被定義為軟實時任務。硬實時任務在錯過截止期時就越容易導致致命錯誤或引發災難性后果；相反，軟實時任務錯過截止期不會引發嚴重后果，從而允許一定比例的截止期錯失。
對應于不同類型任務特點如表1所示。其中：ta是激勵裝置啟動以及執行所需的時間；ts是傳感設備收集外界環境信息所需的時間；tp是處理器處理所收集的或接收的數據所需的時間；tt是通信時間；tr是接收到其他傳感器節點的請求或數據后采取相應操作所需的時間；tDA是D/A轉換所需的時間；tAD是A/D轉換所需的時間。其他如任務的截止時間di、周期、最大執行時間ci、到達時刻、釋放時刻等都可以在系統設計過程中獲得。
表1 調度任務集分析
比較項任務類型
TaTsTrTt
類型周期周期間發間發
實時要求硬實時硬實時軟實時軟實時
執行時間ta+tDAtAD+ts+tptr+tttt
觸發周期性觸發周期性觸發接收中斷觸發Ts或Tr觸發
根據無線傳感器網絡的特點和現有算法的局限性，當前調度策略的設計目標為：
目標1 提高處理器有效利用率，盡可能讓更多的任務得到實時執行。處理器有效利用率指在截止期內完成的任務所耗費時間與總時間的比值。
目標2 能適應無線傳感器網絡多變的特點，即要求調度策略能動態地自我調整。
目標3 在系統過載時盡可能地保證硬實時任務的優先執行。
目標4 降低系統功耗。
2 調度策略
當前無線傳感器網絡任務調度算法的主要缺點在于難以適應多變的系統和混合多類型任務調度的要求，原因在于原有算法以一種不變的統一模式來處理變化多端的動態過程。因此，本文設計了一種基于反饋的動態集成調度策略（feedback dynamic integrated，FDI）來適應多變的無線傳感器網絡環境。
2.1 調度策略描述
圖1給出了FDI算法系統體系結構。
FDI算法將任務集劃分為任務子集H和S。兩個任務子集中的任務并不是固定不變的，而是策略控制器根據監視器的反饋結果對兩個任務子集的任務進行動態調整。如圖1所示，兩個任務集類似于兩個水箱，任務類似于水；H在下，S在上，任務優先注滿H子集，當系統超載即H任務集已滿時，軟實時任務被排除到S任務集中。其中，H任務集采用EDF算法進行調度，而S任務集采用短作業優先（short job first， SJF）算法進行調度。系統優先調度H中的任務。
2.2 簡單反饋控制
2.2.1 負載監視器
負載監視器對關鍵任務集H的總CPU利用率進行監測，并將結果傳遞給策略控制器。出于簡單性的原則，參考EDF算法最壞情況下的可調度性判斷[7]，負載監視器返回數據被定義為
ρ=underload if ni=1ci/di≤1
overloadotherwise （1）
2.2.2 策略控制器
策略控制器根據監視器的監測結果，利用給定的規則選擇確定當前的調度策略。
規則1 如果監視器返回ρ=underload，且任務子集S=，則單獨采用EDF算法對H中的任務進行調度，即正常負載完全采用EDF調度算法。
規則2 如果監視器返回ρ=underload，且S≠，采用準入控制/回歸策略調整H和S。
規則3 如果監視器返回ρ=overload，采用準入控制/回歸策略調整H和S，對要執行的任務作業進行可達/夭折判斷。
這里只給出了三個簡單的規則，而且將負載用兩個語言變量“underload”和“overload”來描述，實際應用中還可以根據需要靈活地采用更多的語言變量來描述，從而確定更多的規則。
2.3 任務作業可達/夭折策略
在超載情況下，第一個錯失截止期的作業會導致多個任務作業錯失截止期，這也是基于EDF的算法在超載情況下產生多米諾現象最重要的一個原因[8]。因此，FDI算法在系統超載時對即將調度運行的任務作業都要進行可達/夭折判斷。通過簡單的判斷發現無法在截止期之前完成的就不予調度并作夭折處理。
記t為系統當前時間，如果有
lij=dij-(t+ci)≥0(2)
表示該任務的截止期是當前可達到的。在調度時，按式(2)計算被調度就緒任務的lij。如果lij＞0，則進行調度；反之丟棄。
2.4 準入控制/回歸策略
為了適應系統瞬時超載的調度需求，目前有些算法已經采用了準入控制的策略，即通過在每個新任務到達時刻，判斷其加載是否會造成系統過載，若是，則拒絕對新任務調度運行，以確保系統當前任務集合能夠滿足實時性能要求。原有的準入控制策略的思想簡單直觀，但同時它又有以下的不足：a）它只考慮了新任務加載這一方面的問題，只能在一定程度上控制系統過載情況的發生，無法適應系統內部正處于運行態的任務對系統資源需求的動態變化[9]；b）新任務有可能是比較關鍵的任務，導致系統出現嚴重錯誤；c）采用的是最壞情況下的參數值，正常情況下有一定的余量。簡單的拒絕讓一些新任務失去了得到有效執行的機會。
FDI算法針對原有準入控制的不足，在原準入控制的基礎上加入回歸的支持。新到達任務直接放入H任務集，然后根據監視器反饋的數據對H和S任務集進行調整。被拒絕的任務不會被簡單地放棄而是進入后臺處理，并有回歸的機會。FDI的準入/回歸規則如下：
規則4 當ρ=overload，將處在H任務集中符合max(ci/di)的軟實時任務移入任務子集S，直到ρ=underload。
規則5 當ρ=underload，將S任務子集中符合min (ci/di)的任務回歸到H任務子集；當ρ=overload時，撤銷最近一次回歸并結束。
2.5 動態電壓調整
根據上面提到的負載監視器反饋的具體數值范圍，結合預測算法，對處理器電壓和工作頻率進行動態調整，以降低系統功耗[10]，這部分需要處理器的支持。本文采用的XScale處理器具有五個離散速度，具備相應的支持。
3 實驗及結果分析
3.1 實驗設計
采用FDI、EDF和固定優先級調度策略（fixed priority，FP)對無線傳感器網絡系統中的任務進行調度，分別統計整體任務截止期錯失率（missed deadline percentage，MDP）、硬實時和軟實時任務的MDP、CPU的有效利用率，并進行對比分析。計算系統當前所有就緒任務的總CPU利用率作為當前系統負載。
3.2 實驗結果比較及分析
調度算法的性能從三個方面考察：a)動態負載下的MDP。MDP指錯失的任務作業數與就緒任務作業總數的比值，顯示了算法的可調度性。b)硬實時和軟實時任務的MDP。顯示了調度算法對于保障關鍵任務優先執行的能力。c)CPU的有效利用率。所有實時完成任務的CPU占有時間/總時間。這個指標顯示了調度算法有效利用CPU處理資源的能力。3.2.1 MDP的對比
圖2顯示了動態負載情況下EDF、FP和FDI算法總的MDP變化的比較。其中，橫坐標L表示負載，縱坐標MDP表示截止期錯失率。MDP越低表示調度成功率越高。
從圖2可以看出，在負載較低的情況下，即Un≤1時，EDF和FDI算法都表現出其最優性，負載Un在[0.63，0.74]時FP開始出現MDP上升的現象；在系統超載的情形下，即Un>1時，FP和FDI算法的MDP開始平穩上升，這是系統資源的有限性所必然導致的。即便如此，FDI仍然保持最優的性能。另外值得注意的是，在超載的情形下，EDF算法的MDP性能開始出現快速下滑，出現明顯的多米諾效應，這是采用截止期單一特征參數的調度算法的通病。
3.2.2 保證關鍵任務的執行能力
圖3、4分別顯示了三種算法對關鍵的硬實時任務和非關鍵的軟實時任務的調度情況。圖中，橫坐標L均表示負載，縱坐標HMDP和SMDP分別表示硬實時任務和軟實時任務的截止期錯失率。
從圖3可以看出，FDI和FP算法有效地保證了關鍵的硬實時任務的正確執行，而EDF算法在超載時硬實時任務的MDP較高。圖4的結果表明，雖然在硬實時任務調度上FP和FDI的性能相當，但由于FP的總體MDP較高，其在軟實時調度上性能較差。FDI和EDF在軟實時任務調度性能上相當。
3.2.3 有效處理器利用率對比
圖5給出了三種算法在不同負載情形下的有效處理器利用率的變化曲線。其中，橫坐標L表示負載，縱坐標EU表示有效利用率。有效利用率越高，表示該算法越能有效地利用處理器資源。
從圖5可以看出，在低負載的情況下，FDI和EDF算法保持了一致的性能；在超載的情形下，EDF性能快速下降，而FDI和FP算法性能仍然保持較高的水平。其中，FDI算法還略優于FP算法。
4 結束語
本文討論了無線傳感器網絡實時任務調度問題；綜合考慮任務的截止期、實時性要求和剩余執行時間三個特征參數，將簡單反饋控制與任務準入/回歸控制、可達/夭折等相結合，設計了新的動態集成調度框架，提出FDI調度算法。這種設計方法不僅適合于截止期、實時性要求和剩余執行時間三種特征參數的結合，還可以根據需要用于其他多種特征參數的結合。最后，以目前應用于無線傳感器網的EDF與FP算法為基線，從總任務的MDP、硬實時和軟實時任務的MDP、CPU的有效利用率三個方面對FDI算法性能進行了實驗對比和分析。結果表明，FDI算法不僅避免了硬實時任務錯過截止期，而且最大程度地降低了軟實時任務的MDP，相比EDF和FP算法具有更好的綜合性能；同時FDI又具有自我動態調整的能力，更能適應無線傳感器網絡的要求。
參考文獻：
［1］
HILLJ， SZEWCZYK R， WOO A，et al.System architecture directions for networked sensors[C]//Proc of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge， Massachusetts:ACM Press， 2000:93104.
[2]HU Zhihua，LI Baochun.On the fundamental capacity and lifetime limits of energyconstrained wireless sensor networks[C]//Proc of the 10th Realtime and Embedded Technology and Applications Symposium. Toronto:IEEE Computer Society，2004:160166.
[3]王萬里，鄭扣根，姚翔，等.無線網絡傳感器及其微型操作系統的研究[J].計算機應用研究，2005， 22（9）:3942.
[4]尹震宇，趙海，徐久強，等.無線傳感器網絡操作系統中搶占式任務調度策略[J].東北大學學報：自然科學版，2007，28(5):652655.
[5]尹震宇，趙海，林凱，等.無線傳感器網絡操作系統調度策略[J].計算機工程，2007，33(17):7782.
[6]羅曉華.支持無線網絡傳感器的rOS操作系統若干關鍵軟件技術的研究和實現[D].杭州：浙江大學，2006.
[7]LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hardrealtime environment[J].Journal of the ACM，1973，20(1):4661.
[8]BUTTAZZO G，SPURI M，SENSINI F.Value vs deadline scheduling in overload conditions[C]//Proc of the 19th IEEE Realtime Systems Symposium. Pisa:IEEE Computer Society Press，1995:9095.
[9]鄒勇.開放式實時系統的調度方法研究[D].北京：中國科學院軟件研究所，2003.
[10]陳歡，陳向東，胡黎黎.無線傳感器網絡動態電壓調度算法[J].傳感器與微系統，2006，25(11):4143.
