無線傳感器網絡節點任務調度與功耗管理算法研究*

田新越， 李翔宇

(清華大學 微電子學研究所，北京 100084)

?

無線傳感器網絡節點任務調度與功耗管理算法研究*

田新越， 李翔宇

(清華大學 微電子學研究所，北京 100084)

摘要:針對有能量采集系統的無線傳感器網絡節點異質多核SoC平臺，從提高能量利用效率的角度，提出了一種任務調度與功耗管理算法。該算法處理實時有截止時間并有相互依賴關系的任務，任務執行在多個電壓可調的處理單元上。通過對節點系統能量采集行為和應用情況進行分析建立了問題模型，并運用運籌學軟件LINGO對模型做了求解。利用多組隨機輸入的任務流圖對模型與算法進行了驗證，該算法在功耗與時間約束范圍內確實能有效提高系統的能量利用效率。

關鍵詞：能量采集； 無線傳感器網絡節點； 異質多核片上系統； 功耗管理； 任務調度

0引言

隨著微電子工藝水平的發展，無線傳感器節點也被應用到了諸如軍事監控、環境監測等更廣闊的領域，由此傳統的設計已經不能滿足系統各方面的需求[1]。在高采樣率無線傳感器應用場合，為了獲得較高的能量效率，單個節點的設計越來越多地采用含有專用加速器的異質多核片上系統(SoC)，這給系統設計帶來了諸多挑戰[2]。在能量供給方面，能量采集加可充電電池的單元設計也越來越多地被使用[3]，因此，更加依賴功耗管理技術。

目前，針對無線傳感器網絡節點的功耗管理算法大都面向單個微控制器構成的節點系統(單核系統)，針對異質多核SoC的相對較少，而面向能量采集異質多核SoC的則更在少數。單核系統的功耗管理不包含任務到處理單元的分配問題，問題相對簡單。基于此所提出的功耗管理解決方案除了典型的動態電壓頻率調整(DVFS)之外[4]，還有調整任務執行在處理單元上的占空比等[5]。針對異質多核SoC的功耗管理算法大多單一地采用電池為系統供能，問題的目標集中在解決調度問題和盡可能地利用電池有限的能量供給來完成更多的任務[6]。

本文面向具有能量采集單元的無線傳感器網絡節點異質多核SoC平臺，功耗管理的目標是提高能量利用效率，也就是合理利用采集的能量，一方面盡可能延長系統的工作時間；另一方面，盡量完成更多的計算任務[7]，由于無線傳感器網絡一般是一種實時嵌入式系統，還需要滿足節點執行任務的實時性要求。通過搭建目標平臺的問題模型，本文在完成初始任務調度后利用Lingo軟件進行功耗管理，從而改善系統能量利用問題。

1相關模型

1.1能量模型

考慮能量采集的情況下，采集的能量應首先提供電路工作，如果消耗的功耗小于采集功耗，則多余的功耗充入蓄電池；否則，不足的部分由電池提供[8]。假設平臺可以實時地檢測電池電量，同時根據能量采集器的輸入功率水平，可以得出系統整體的一個實時功耗預算PB。

1.2應用模型

本文采用基于DAG模型的任務流圖，一個周期性的應用抽象為一個任務流圖，對應一個程序(Pr)，有相應的運行周期和截止時間。其中的任務(task)是調度的基本單元，在完成調度前有一定的工作量范圍，該范圍指示任務實際執行中達到的系統精度、迭代次數等指標，比如：信號處理時使用的量化位數多,則精度高;位數少,則精度低，精度可以看作是一種系統“回報”，回報高意味著性能更優。調度完成后任務執行的工作量越多，則系統指標越高，認為系統最后的回報越大，性能越好。任務工作量與回報的函數關系為

(1)

式中Qj為任務taskj的工作量，Uj為相應工作量對應的回報。

每個程序執行完成的回報是其任務流圖中包含的所有任務執行完成后所得到的回報的加權和

Ui=∑wjUj,?taskj∈Pri,

(2)

式中wj為任務taskj的回報在程序Pri中所占的權重。

1.3硬件模型

硬件由多個處理單元(PE)組成，每個處理單元有多個工作模式，對應于不同的電源電壓，從而表現為不同的功耗水平和處理速度[9]，式(3)是任務taskj執行在處理單元PEu上的功耗表達式

(3)

其中,uj為任務對功耗的影響因子，Cu，Vu分別為處理單元的等效電容和電壓。

每個任務在各個處理單元的不同工作模式下有不同的執行時間。式(4)是任務taskj執行在處理單元PEu上的時間表達式

(4)

其中,aj為任務工作量和執行時間的比例系數，kuj為處理單元和任務對執行時間的影響因子。如果某個處理單元不支持某任務，則設其執行時間為無窮大。

2問題描述與建模

本文將應用情形抽象成一個周期性的過程，能量輸入的規律與系統執行的應用程序的內容在每個周期內是基本相同的。每個周期包含若干個時間步，假設能量輸入情況的變化速率相對于時間步長度足夠慢,即可以認為一個時間步內的輸入功率恒定，這樣可以預設一個時間步內的平均功耗預算。每個時間步的平均功耗預算是不變的，在可預測范圍內一個已知量，是該時間步內程序執行所消耗功耗的上限。對于能量采集變化情況可預測、應用程序運行有規律的情形，每個時間步的功耗預算可以根據預測確定[7]。

每個時間步內系統應用都要調度在系統的硬件平臺上，系統的應用包含了一組相互獨立的程序(Pr)，即一組任務流圖，用集合A表示，每個程序都必須在規定的時間之前執行完畢。對程序的任務流圖而言，從頭節點到尾節點都有一條路徑(path)，由于程序執行有規定時間約束，所以，每條路徑都有一個截止時間(dt)要求，路徑的截止時間是程序運行周期和截止時間的最小值。將路徑的截止時間與該路徑上所有任務執行時間(假設任務taskj執行在處理單元PEu上)加和的差值用slack表示為

slackk=dtk-∑Tuj,?taskj∈Pathk.

(5)

本文的目標是在能耗預算和系統應用的時間約束范圍內優化系統的性能，根據之前的定義即獲得最大的系統回報，該問題可以描述成如下數學形式

目標：max:∑σiUi,?Pri∈A

約束：∑puj≤PB,?taskjexecuteonPEu,

slackk≥0,?pathk,

Qmin,j≤Qj≤Qmax,j,?taskj∈Pri,?Pri∈A,

Vmin≤Vu≤Vmax,?PEu,

Dn-Dm-Tm≥0,?taskm∈precedenceoftaskn.

系統回報是應用集合A中所有程序回報的加權和(σi是程序Pri的回報在集合A中所占的權重)。任務執行在某個處理單元上的功耗由P表示，所有任務執行時的功耗總量要小于系統功耗預算PB。任務工作量(Q)和處理單元的執行電壓(V)都有上下界。D是每個任務開始執行的時間，對D的約束是為了保證有依賴關系的任務在處理單元上先后執行。應用集合A中全部程序所包含的每一條路徑上所有任務執行時間的和要小于該路徑的截止時間。

3任務調度和功耗管理算法

根據前面的問題描述和模型，就此提出一套完整的靜態解決方案。問題的解決包含了三個步驟：任務調度、約束提取以及功耗管理。

任務調度處理單個時間步內要執行的程序集合，將各個程序的任務分配到相應的處理單元上并不再變動。任務調度方法基于已有的算法做了適應性改進[10]，對執行在指定處理單元的任務，在分配過程中結合指定處理單元的使用情況和任務分別在該處理單元和通用處理單元的執行效率來確定分配的結果。

約束提取是從任務調度的結果提取模型描述的功耗約束和時間約束。為調度完前后執行在同一處理單元上的任務在任務流圖上連一條邊，保留結果到一個新的有向無環圖中，對該圖和原始輸入的任務流圖用深度優先搜索(DFS)算法[11]做路徑搜索，從而可以得到模型全部的路徑，也就得到了基于路徑延時的時間約束。考慮任務之間的依賴關系建立開始時間的約束，根據系統功耗預算建立功耗約束，這樣模型的全部約束就建立起來。

功耗管理對任務工作量和處理單元電壓做調整，在模型要求的功耗與時間約束范圍內，通過對兩個變量的規劃來達到整個系統運行所獲得的回報最大，同時保證任務之間的依賴關系不被打亂。通過LINGO軟件可以求得在當前功耗和時間約束下各個任務工作量與處理單元電壓的最優值，系統在該配置下運行可以獲得最大的回報。

4驗證

本文利用任務圖生成程序TGFF[12]隨機生成的一組任務流圖對模型與算法進行驗證。應用模型包含了三個程序，每個程序的任務流圖見圖1。

圖1　任務流圖Fig 1　Task flow graphs

硬件模型包含三個處理單元，其中,PE1和PE2是通用處理單元，PE3是專用加速引擎，只能執行t1,t4這樣的任務。初始調度完成后利用模型約束提取方法可以得到新的有向無環圖(見圖2)。

圖2　初始任務調度后新的有向無環圖Fig 2　New directed acyclic graph after initial task scheduling

調度結果見圖3，每個任務框的高度表征該任務的功耗水平，長度表征任務的執行時間，虛線表示程序的截止時間，處于任務流圖尾節點的任務用灰色標注。圖3(a)是初始調度的結果，此時系統回報低且任務執行超出了程序的截止時間。圖3(b),(c)是在不同的功耗預算下利用LINGO軟件做功耗管理優化后的結果，可以看到程序的截止時間都已經滿足，但由于圖3(c)中系統給的功耗預算相較于圖3(b)更充足，圖3(b)中系統回報經過優化提高到了546，圖3(c)中則達到了638。從任務執行時間來看，圖3(b)中結果已能滿足應用時間約束，而圖3(c)中還留出了更多的時間slack，可以看到不同的功耗預算下系統性能得到了不同程度的優化。

圖3　不同功耗預算的調度結果Fig 3　Scheduling result of different power consumption budget

5結束語

本文針對能量采集無線傳感網節點異質多核SoC平臺的能耗問題,提出了一種充分利用采集能量提高系統性能的任務調度與功耗管理策略;針對異質多核和能量采集的特點搭建了目標優化模型，并將系統優化問題歸結為對非線性規劃問題的求解;提出了一種對上述問題的靜態求解算法，經過一組隨機驗證可以看到本文提出的算法正確，并能夠切實提高系統的能量利用效率。

參考文獻:

[1]Yick J,Mukherjee B,Ghosal D.Wireless sensor networks sur-vey[J].Computer Networks,2008,52(12):2292-2330.

[2]Sharif A,Potdar V,Chang E.Wireless multimedia sensor network technology:A survey[C]∥7th IEEE International Conference on Industrial Informatics,NDIN 2009,IEEE,2009:606-613.

[3]Piorno J R,Bergonzini C,Atienza D,et al.HOLLOWS:A power-aware task scheduler for energy harvesting sensor nodes[J].Journal of Intelligent Material Systems and Structures,2010,21(13):1317-1335.

[4]Dargie W.Dynamic power management in wireless sensor networks:State-of-the-art[J].Sensors Journal,IEEE,2012,12(5):1518-1528.

[5]Kansal A,Hsu J,Zahedi S,et al.Power management in energy harvesting sensor networks[J].ACM Transactions on Embedded Computing Systems(TECS),2007,6(4):32.

[6]Chen J J,Kuo T W.Voltage-scaling scheduling for periodic real-time tasks in reward maximization[C]∥26th IEEE International Real-Time Systems Symposium,RTSS 2005,IEEE,2005:355.

[7]Moser C,Chen J J,Thiele L.Reward maximization for embedded systems with renewable energies[C]∥14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications,RTCSA’08,IEEE,2008:247-256.

[8]Moser C,Brunelli D,Thiele L,et al.Real-time scheduling for energy harvesting sensor nodes[J].Real-Time Systems,2007,37(3):233-260.

[9]Yang P, Catthoor F. Pareto-optimization-based run-time task scheduling for embedded systems[C]∥2003 First IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis,IEEE,2003:120-125.

[10] Zhang Y,Hu X S,Chen D Z.Task scheduling and voltage selection for energy minimization[C]∥Proceedings of the 39th An-nual Design Automation Conference,ACM,2002:183-188.

[11] Laarman A,Langerak R,Van De Pol J,et al.Automated Techno-logy for Verification and Analysis[M].Berlin Heidelberg:Springer,2011:321-335.

[12] Dick R P,Rhodes D L,Wolf W.TGFF:Task graphs for free[C]∥Proceedings of the 6th International Workshop on Hardware/software Codesign,IEEE Computer Society,1998:97-101.

Research on task scheduling and power consumption management algorithm for wireless sensor networks node*

TIAN Xin-yue， LI Xiang-yu

(Institute of Microelectronics，Tsinghua University，Beijing 100084，China)

Abstract:Aiming at heterogeneous multiple core SoC platform with energy harvesting system in design of wireless sensor networks(WSNs)nodes, a task scheduling and power consumption management algorithm is proposed to improve energy utilization efficiency.The scheduling algorithm is designed to deal with real-time dependent tasks with deadlines and these tasks are executed on variable voltage processing units.After an effective analysis on energy harvesting and application situation,mathematical model for problems are constructed and furthermore the models are resolved by operational research software,LINGO.Multiple group taskflow figure is used to verify that the model and algorithm can definitely effectively improve energy utilization efficiency of system,in restrain range of power consumption and time.

Key words:energy harvesting; wireless sensor networks(WSNs) node; heterogeneous multiple core SoC; power consumption management; task scheduling

DOI:10.13873/J.1000—9787(2016)02—0009—03

收稿日期：2015—05—15

*基金項目：國家自然科學基金資助項目(61006021)

中圖分類號：TP 301.6

文獻標識碼：A

文章編號：1000—9787(2016)02—0009—03

作者簡介:

田新越(1990-)，男，山西介休人，碩士研究生，研究方向為無線傳感器網絡節點低功耗設計。

李翔宇,通訊作者,E—mail：xiangyuli@mail.tsinghua.edu.cn。