面向系統級能耗優化的無線實時網絡系統任務調度機制

朱 榮，袁朝暉，曹義親

（華東交通大學軟件學院，江西 南昌330013）

近年來，無線嵌入式網絡（wireless embedded real-time networks，WERNs）發展迅速，在災害檢測、目標監控等領域展現出極為廣泛的應用前景。作為典型的無線網絡系統，WERNs由大量通過無線連接的具備有限的計算和通信能力的微型嵌入式節點互聯組成［1-16］，這些節點一般依靠電池供電，其電池續航能力十分有限。同時，通常的WERNs中節點均部署在較為惡劣的環境或人類不宜到達的區域，為這些節點更換電池的成本極為高昂。因此，采用合理的機制和方法來達到節省能耗并最大化整體使用壽命成為無線嵌入式網絡系統的首要挑戰［2-15］。

合理的任務節點分配和運行模式設定是獲得較長網絡生命周期的有效途徑之一。首先，當一個節點的電池耗盡時，不僅該節點無法正常工作，還可能因為該節點的失效而造成系統的通信鏈路斷開，從而使整個系統失效。因此，WERNs 中的任務負載要優先分配到電量較為充足的節點上運行。其次，當前的嵌入式CPU均支持動態電壓頻率調節機制（DVFS）［23-24］，在滿足實時任務完成時間約束條件下，適當的調低CPU的電壓和運行頻率能有效降低耗能。例如，文獻［3］考慮周期搶占式硬實時任務分配問題，實現了能量消耗最小化。文獻［5］提出多項式時間的最優任務分配算法。在文獻［4］和［7］中，作者提出同時考慮任務的通信量和數據處理量進行任務分配以實現分布式實時系統的利用率最大化。在文獻［12］和［13］中，作者分別做了能量意識的調度機制和硬實時的任務在多處理器分配機制的綜述。這些研究成功的利用了系統的DVFS協議，然而這些工作均沒有考慮通信子系統的能耗影響。

除計算子系統外，射頻通信子系統也是WERNs中耗能的主要因素之一。一個有效的方法是使射頻模塊空閑的時候進入休眠模式，已有許多通信休眠調度機制被提出來并被實現。例如IEEE的802.11協議的休眠模式［29］，無線傳感器網絡中的MAC協議［27-28］等。然而，這些通信調度協議不考慮CPU的工作，無法達到系統級的能耗優化的目的。針對這些問題，以最大化系統壽命和最小總能耗為目的，提出一種任務調度和運行模式分配機制。該機制將系統接收的任務優先分配給剩余能量較多的節點，在滿足系統整體實時約束的條件下調節DVFS協議以節省耗能，并根據接收和發送的數據量調節通訊模塊的睡眠開合周期，從而在滿足系統的要求。仿真實驗表明，所提出的任務分配機制在系統壽命和總耗能的表現上優于其他兩種典型的調度機制［25-26］。

1 系統模型

形如常用的無線傳感器網絡系統，WERNs由隨機分布在有限區域中的M個的節點組成。假設對于任意兩個節點i和j（i，j=1，…，M且i≠j），存在一條穩定的無線通信鏈路使其相連。然而，WERNs的節點由電池供電且通常情況下難以更換電池，因此當一個節點的電池耗盡時，不僅該節點無法正常工作，還可能由于該節點的失效而造成系統的通信鏈路斷開，從而使得整個系統無法工作。因此，系統中負載任務的分配和調度的目標不僅是能耗的最小化，還應考慮系統整體工作壽命的最大化。對于系統中的每一節點i，電池的消耗主要由兩大子功能模塊造成，射頻通信模塊和數據處理模塊［4］，其能耗模型如下。

1.1 通信耗能

通信能耗不僅與發送和接收的數據量相關，而且與通信距離有關。常用的無線嵌入式節點的射頻模塊通常由發送電路、放大器和接收電路組成［15］，假設發送電路和接收電路的能耗均為apJ·bit-1，而放大器的能耗為bpJ·bit-1·m-2（由文獻［15］可知，a和b通常分別取50 和100）。在節點i發送d比特數據到距離為s的節點j的情況下，i和j的發送通信耗能Es和接收通信耗能Er可以分別通過下式計算：

1.2 計算耗能

除通信子模塊外，計算處理子系統是另一個主要消耗節點能量的因素。計算處理的能耗不僅與處理的數據量有關，還與處理器的實時工作頻率有關［16］。對同一個任務，不同的工作頻率對應不同的能耗和執行時間。常用的節點CPU動態電壓頻率調節功能（DVFS）通常支持多種離散的工作頻率［14］。例如，Intel Xscale PXA270 處理器支持7 種不同的工作頻率［22］，624，520，416，312，208，104 MHz 和13 MHz 以及與之相應遞減的功率消耗，如表1所示。同時，對同一任務的處理時間隨CPU工作頻率的上升而單調下降。

表1 Intel Xscale PXA270 能耗模型Tab.1 Intel Xscale PXA270 power model

2 任務模型

WERNs的工作任務通常由多個分布在成員節點中運行的子任務組成。例如，在無線傳感網中，聚族中各節點分別進行數據采樣并將采樣結果或者局部判斷發送給簇頭節點，簇頭節點根據收到的信息進行最終的全局判斷。系統的檢測任務可以劃分為各子節點上的采樣子任務和簇頭節點上的數據融合子任務。由于節點間數據傳輸的需要，各子任務之間根據數據傳遞相關性存在著一定的先后關系。一個系統的工作任務可以用一個有向無環圖SDAG=（T,V）表示，其中T為子任務集，V為子任務之間連接關系集；而子任務Ti(Ti∈T，i=1,…,N)可由一個6元組( )Di,mi,di,Tcpi,Ecpi,Ecmi描述，其中Di是子任務Ti的處理數據量，mi為Ti接收到的數據量，di是Ti發送數據量。Tcpi為Ti的執行時間，Ecpi是數據處理耗能，Ecmi為Ti的通信耗能，根據發送和接收的數據量可由式（1）+（2）計算得出。

3 問題定義

作為分布式實時系統中經典的NP問題［13，17］，以利用率或能耗為主要目標的任務調度和分配方法已經被廣泛研究［3-11］。然而，在WERNs中，系統中任務的分配與調度不僅要最小化耗能，還必須考慮系統中各節點的能耗均衡，使得系統的壽命最大。此外，任務的實時性約束也對任務分配和節點CPU的頻率設置產生要求。因此分布式無線嵌入式實時系統的任務分配和調度問題可以形式化描述如下。

給定①任務群的子任務關系圖SDAG=（T,V）；②該任務的完成時間約束L；③無線嵌入式實時系統G=(j|j=1,…,M)；④節點j的DVFS協議頻率能耗表(Fk,Ek|k=1,…,N) 。

問題的目標：①分配子任務Ti(Ti∈TDAG，i=1,…,N)給節點j；②設置節點j的CPU運行頻率Fj和當前通信休眠周期Kj。

使得任務完成后剩余能量最小的節點能量最大化，即

同時滿足：

其中：Ej為節點j的剩余能量，Ecpi為任務Ti在節點j上的數據處理能耗，而Er（i-1）和Esi分別為任務Ti在節點j上的接收通信能耗和發送通信能耗。TDAG為任務群的執行時間。式（3）描述了系統的壽命和總的耗能，而式（4）則為系統的實時性約束條件。

4 節點任務調度機制

對于一個NP（非確定多項式）問題，常用的最優解算法往往由于計算復雜而耗時過長，無法在實時系統中得到應用。例如，文獻［19-21］研究了智能計算在任務調度和分配中的應用，但是這些方法的計算時間過長，在無線嵌入式系統中難以滿足實時性約束。因此本文中提出的調度分配機制，其設計目的基于以下目標：①根據（3）式可知，系統的任務調度和分配需最大化系統的壽命，即剩余能量較多的節點優先分配到任務，防止某一個節點失效。②由式（4）可知，系統的時間約束必須得到保證，系統的調度和能耗調節需要滿足系統實時性約束條件。③系統的射頻模塊睡眠周期需要根據任務的完成時間加以調節使得通訊耗能最小。

根據上述設計目標，所提出的機制包含3個部分。首先，為了滿足系統任務的時間約束，使用基于關鍵主路徑的方法保證系統的實時性。在此基礎上，啟發式調節各條路徑上的頻率，使得系統關鍵路徑上的節點在最優模式能耗上運行。再次，在滿足系統的實時性約束的情況下，算法根據任務節點計算量的大小和處理器節點剩余能量進行任務和處理器的分配，實現系統的壽命最大化。最后，根據子任務之間的時間約束關系統一調配各子任務節點的通信睡眠周期，實現系統通訊耗能的最優。其具體步驟如下。

4.1 基于關鍵路徑方法的實時性保證策略

任務的實時性約束是系統調度和分配的首要目標之一。而在任務的調度過程中，子任務的計算負載和通訊負載均主要由該子任務的數據量決定［4］。因此，算法中首先將子任務圖中各節點的數據量作為權值，使用基于關鍵路徑［18］的搜索方法，找出子任務關系圖中耗時最長的路徑，用于滿足系統的實時性約束。圖1給出了一個任務群圖的變換及其關鍵路徑搜索過程，其具體的步驟描述如下：①對任務群中的所有邊進行編號（如圖1（a）所示）；②將圖中的邊轉換為點，將點轉換為邊，求出該子任務圖的對偶圖（如圖1（b）所示）；③加入源點和匯節點，將對偶圖中所有的無起始節點邊接入源點，無終點邊接入匯點并保留原始邊權值，使該任務圖成為AOE網絡（如圖1（c）所示）；④使用文獻［18］中的算法找出關鍵路徑（如圖1（d）所示）。

圖1 任務群變換Fig.1 Task group transformation

4.2 節點CPU的DVFS設定和調整

關鍵路徑上的任務決定任務群的最終完成時間，然而4.1節中的關鍵路徑算法利用的權值為節點上任務的最小完成時間，即：所有任務均由相應節點使用最高頻率執行時的最短路徑。在實際的調度過程中，為了使系統的壽命最大，同時最小化節點耗能，在滿足任務實時性的條件下，可以使用DVFS協議將CPU工作模式設定或調整為較低的頻率運行。DVFS調整算法偽碼描述如算法1所示。

算法1：任務群節點工作頻率設定和調整

在算法1中，首先使用拓撲排序，以找出任務圖SDAG中的所有路徑，并按照路徑的權值從大到小進行排序，對權值較大的路徑進行優先處理。在2.1至2.3行中，設置所有未處理節點的初始頻率為最高值，以首先滿足任務群的實時性約束。假設對于每個子任務，其完成時間Tcpi與數據量Di和工作頻率F之間直接存在著遞增關系Tcpi=g(Di,F)（其中函數g(·)可以由系統經訓練求出。例如，通常情況下，圖像處理中的小波變換執行時間與圖像的數據大小和執行頻率之間存在線性遞增關系。）。則在2.4行到2.6行中，在保證任務時間約束條件下適當調低CPU的工作頻率，以實現計算子系統的能耗優化。由算法描述可知，該算法的主要計算為拓撲排序和路徑權值的排序，其中拓撲排序的復雜度為O(N+e)，N為任務群中節點的個數，e為邊數；而路徑權值在快速排序的時候，其時間復雜度為O(NlogN)，因此，該算法總的時間復雜度為O(NlogN)。

4.3 任務節點與CPU節點的映射

在一個WERNs系統中，由于系統中單個節點可能擔任通信中繼的角色，該節點的電能耗盡則會導致整個系統失效，因此，系統中總的能耗最小并不代表系統的最優。為了實現系統的生命周期最大化，任務群中子任務節點與系統中CPU節點之間映射的首要原則為使用剩余能量較多的節點，并且盡量分配數據量較大的任務，同時最小化該任務的通信代價。

由第3節中問題定義可知，當子任務T(i-1)傳遞數據給子任務Ti的時候，若將子任務Ti分配（映射）到節點j上運行，則該分配所產生的能耗代價zi-j可以計算如下

算法2：子任務分配

在算法2中，首先將所有的路徑按照權值進行排序。針對系統G中所有的未分配任務的節點，利用（5）式計算出其分配當前子任務后的z值，并將該任務分配給z值最小（即能耗壽命最優）的處理節點，并為該節點設置工作頻率。該算法的時間復雜度為O(N·M），其中N為任務圖中節點的個數，而M為無線嵌入式系統G中節點的個數。

4.4 節點射頻休眠周期調整

除計算處理模塊外，射頻模塊也是系統中耗能的重要因素。合理的通信休眠調度能在滿足系統實時性約束條件下有效的降低能耗。算法3描述了節點射頻模塊睡眠周期設定過程。在該算法中，每一個分配到任務的節點根據該任務的預計完成時間設定后續節點的通信開啟時間，并在自身完成計算任務的時候調度節點通訊模塊進入休眠狀態，以實現能耗的最低。該算法偽碼描述如下：

算法3：節點的睡眠周期設定

輸入：路徑集合{Pi=(Si,Hi)|i=1,…,k} ，節點-任務映射F(Ti→G)

輸出：節點的射頻休眠周期

1 fori=1 到k（k為路徑數）

2 forh=1 到H（路徑k上的子任務個數H）

i（f子任務h映射節點的射頻激活時間未設定）

2.1 激活射頻模塊并設定時間為當前時間T0

end if

2.2 設定當前節點休眠時間為Tcp；（其中Tcp為子任務h的預定處理時間）

2.3 與所有后續節點同步并設定其激活時間為T0+Tcp

End for

3 End for

5 仿真實驗

5.1 實驗設定

仿真實驗模擬10個Intel Xscale PXA270處理器組成的分布式處理系統。在該系統中，每個處理器的初始剩余能量隨機分配。兩個處理節點之間的距離從2～10 m之間隨機產生。節點模擬支持7種工作頻率，分別為624，520，416，312，208，104，13 MHz，其相應的功耗由表1給出。任務群模擬由工作量隨機取值于5～10 Mflops之間的子任務組成，每次浮點計算占用6個CPU時鐘周期，數據量由0.1～10 M之間選取。射頻模塊耗能由CC2420射頻耗能規格定義，如表2所示［30］。

系統的生命周期采用文獻［19］中的定義，即以第一個處理器節點因能量耗盡而失效的時間作為系統的壽命。系統模擬不同的任務群連續載入，直到系統中有一個處理器節點能量耗盡，同時記錄系統的壽命和總的能量消耗。為了驗證所提出的任務調度和分配機制在系統的能耗和壽命方面的表現，本文使用兩種任務調度機制作為對比。第一種任務調度機制為ILP機制，由Yu 等人提出的，基本思想是將系統的任務調度和分配建模為多約束條件下的優化問題，并使用線性規劃求解［25］，以實現節省耗能的目的。第二種任務調度機制為EcoMapS機制，由Tian 等人提出的，在該機制中，研究者綜合考慮計算和通信能耗，最小化調度長度，以實現節省耗能的目的［26］。本文中所提出的算法命名為EeTSA機制。

5.2 實驗結果

為了驗證在網絡狀態不同的時候三種機制的性能表現，模擬了系統中所有節點的初始能量總和由20～300 J之間變化時所有機制的表現。實驗結果如圖2和圖3所示，圖2畫出了不同初始能量條件下3種機制在執行相同的任務群的時候的總耗能情況。而圖3畫出了系統的壽命隨初始能量變化曲線。當處理系統中總的電能增加的時候，系統的能耗和系統的壽命也不斷增加，而本文中提出的EeTSA機制均優于兩種對比機制。當節點的剩余能量較大的時候，EeTSA的能耗優勢更加明顯。

表2 CC2420射頻能耗規格Tab.2 RF transceiver data sheet of CC2420

圖2 系統的總能耗表現Fig.2 Energy consumption performance

圖3 系統的總體壽命表現Fig.3 System-life performance

為了驗證不同工作負載條件下3種機制的能耗表現，模擬在1 min內分別載入不同數量的任務群，圖4和圖5畫出了在工作負載不斷增加時系統的總耗能和系統壽命。由圖中可知，當系統中載入的工作負載不斷的增加，系統的能耗不斷上升，但是系統的壽命不斷下降，同時可以看出EeTSA機制均優于兩種對比算法。由于ILP機制沒有優化射頻子模塊的休眠調度，以至于浪費電能同時減少了系統的壽命。而EcoMapS機制，并沒有將DVFS協議和通信休眠機制統一進行調度。因此EeTSA算法的表現優勢和文中所提出的算法設計機理是相符的。

圖4 任務負載變化時的總能耗Fig.4 Energy consumption vs.task load

圖5 任務負載變化時的系統壽命Fig.5 System-life vs.task load

6 結束語

無線嵌入式實時系統的最優任務分配和調度問題是一個經典的NP問題，確定性的算法可能由于計算的過于復雜從而導致系統的實時性無法得到保證。以最大化系統使用壽命為目的，提出一種優化耗能的任務調度和運行模式分配機制。該機制將系統接收的任務優先分配給剩余能量較多的節點，在滿足系統整體實時約束的條件下調節DVFS協議以節省耗能，并根據接收和發送的數據量調節通訊模塊的睡眠開合周期，從而達到滿足系統實時性約束下最大化系統的使用壽命和最小化系統總能耗的目的。通過大量的仿真實驗表明，本文提出的任務分配機制在系統壽命和系統耗能的表現上優于經典的調度機制。

[1] 朱敬華,高宏.無線傳感器網絡中能源高效的任務分配算法[J].軟件學報,2007,18(5):1198-1207.

[2] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005:12-13.

[3] TAREK A, HAKAN A.Energy-aware task allocation for rate monotonic scheduling[C]//Real Time and Embedded Technology and Applications Symposium,IEEE 2005.RTAS 2005:213-223.

[4] HU X,XING G L,LEUNG J Y.Exploring the interplay between computation and communication in distributed real-time scheduling[J].IEEE Transactions on Computers,2011,60(12):1759-1771.

[5] SRIVASTAVA A, SOBAJE J, POTKONJAK M, et al.Optimal node scheduling for effective energy usage in sensor networks[C]//IEEE Workshop on Integrated Management of Power Aware Communications Computing and Networking,Springer, 2002.

[6] DREWS F,WELCH L,JUEDES D A,et al.Utility-function based resource allocation for adaptable applications in dynamic distributed real-time systems[C]//18th International Parallel and Distributed Processing Symposium,IEEE,2004.

[7] HU X, LEUNG J Y.Integrating communication cost into the utility accrual model for the resource allocation in distributed realtime systems[C]//The 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications,IEEE,2008:217-226.

[8] AYDIN H,YANG Q.Energy-aware partitioning for multiprocessor real-time systems[C]//The 17th International Parallel and Distributed Processing Symposium,IEEE,2003.

[9] MISHRA R, RASTOGI N, ZHU D, et al.Energy aware scheduling for distributed real-time systems[C]//The 17th International Parallel and Distributed Processing Symposium,IEEE,2003.

[10] ZHU D,MELHEM R,CHILDERS B R,et al.Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems[J].IEEE Transactions on Parallel and Distributed Systems, 2003,14(7):686-700.

[11] YANG Y,PRASANNA V K.Power-aware resource allocation for independent tasks in heterogeneous real-time systems[C]//The Ninth International Conference on Parallel and Distributed Systems,IEEE,2002:341-348.

[12] WANG L, XIAO Y.A survey of energy-efficient scheduling mechanisms in sensor networks[J].Mobile Networks and Applications,2006,11(5):723-740.

[13] DAVIS R, BURNS A.A survey of hard real-time scheduling for multiprocessor systems[J].ACM Computing Surveys (CSUR),2011,43(4):113-124.

[14] SEMERARO G, MAGKLIS G A, BALASUBRAMONIAN R, etal.Energy-efficient processor design using multiple clock domains with dynamic voltage and frequency scaling[C]//The Eighth International Symposium on High-Performance Computer Architecture,IEEE 2002:29-40.

[15] HEINZELMAN W R,CHANDRAKASAN A,BALAKEISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//The 33rd Annual Hawaii International Conference on System Sciences,IEEE,2000.

[16] YUAN Z H,ZHANG Y P,XUE C J.Sleep-aware mode assignment in wireless embedded systems[J].Journal of Parallel and Distributed Computing,2011,71(7):1002-1010.

[17] AMINIT N, FAZELI M, MIREMADI S.Distance-based segmentation: an energy-efficient clustering hierarchy for wireless micro-sensor networks[C]//The Fifth Annual Conference on Communication Networks and Services Research, 2007:18-25.

[18] HUANG S T,PANG T M.A new method of identifying critical paths for performance optimization[C]//The 4th European Conference on Design Automation,1993:455-459.

[19] 梁華為,陳萬明,李帥.基于蟻群優化的無線傳感器網絡能量均衡路由算法[J].模式識別與人工智能,2007,20(2):275-280.

[20] 易本順,陳杰,肖進勝.無線傳感器網絡優化的任務管理算法研究[J].電子與信息學報,2010,32(11):2606-2611.

[21] 沈艷,郭兵,丁杰雄,李迅波.無線傳感器網絡節能動態任務分配[J].四川大學學報:工程科學版,2008,40(4):143-147

[22] YE X,ZHOU H Y,TAO W J.Real-time 1.264/AVG decoder implementation on PXA270[C]//The International Conference on Communications,Circuits and Systems,2007:819-821.

[23] MANZAK A, CHAKRABARTI C.Variable voltage task scheduling algorithms for minimizing energy/power[J].IEEE Transactions on Very Large Scale Integration Systems.2003,11(2):270-276.

[24] YAO F, DEMERS A, SHENKER S.A scheduling model for reduced cpu energy[C]//Proceedings of Symposium Foundations of Computer Science,1995:374-382.

[25] YANG Y, VIKTOR K, PRANSANNA B.Energy-balanced task allocation for collaborative processing in wireless sensor networks[C]//Conference on Languages,Compilers and Tools for Embedded Systems,2003.

[26] TIAN Y,EYLEM E,FUSUN O.Energy-constrained task mapping and scheduling in wireless sensor networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems Conference,2005.

[27] INJONG R, WARRIER A, MAHESH A, et al.Z-MAC: A Hybrid MAC for Wireless Sensor Networks[J].IEEE/ACM Transactions on networking,2008,16(3):511-524.

[28] YE W,HEIDEMANN J,ESTRIN D.An energy-efficient MAC protocol for wireless sensor networks[C]//The Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies,2002:1567-1576.

[29] NATKANIEC M, PACH A R.A new channel access protocol for wireless LANs[C]//The 5th International Symposium on Wireless Personal Multimedia Communications,2002:1351-1355.

[30] KIM Y W,LEE S J,KIM G H.Wireless electronic nose network for real-time gas monitoring system[C]//The IEEE International Workshop on Robotic and Sensors Environments,2009:169-172.