田新越， 李翔宇

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

?

無線傳感器網(wǎng)絡節(jié)點任務調度與功耗管理算法研究*

田新越， 李翔宇

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

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

關鍵詞：能量采集； 無線傳感器網(wǎng)絡節(jié)點； 異質多核片上系統(tǒng)； 功耗管理； 任務調度

0引言

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

目前，針對無線傳感器網(wǎng)絡節(jié)點的功耗管理算法大都面向單個微控制器構成的節(jié)點系統(tǒng)(單核系統(tǒng))，針對異質多核SoC的相對較少，而面向能量采集異質多核SoC的則更在少數(shù)。單核系統(tǒng)的功耗管理不包含任務到處理單元的分配問題，問題相對簡單?；诖怂岢龅墓墓芾斫鉀Q方案除了典型的動態(tài)電壓頻率調整(DVFS)之外[4]，還有調整任務執(zhí)行在處理單元上的占空比等[5]。針對異質多核SoC的功耗管理算法大多單一地采用電池為系統(tǒng)供能，問題的目標集中在解決調度問題和盡可能地利用電池有限的能量供給來完成更多的任務[6]。

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

1相關模型

1.1能量模型

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

1.2應用模型

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

(1)

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

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

Ui=∑wjUj,?taskj∈Pri,

(2)

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

1.3硬件模型

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

(3)

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

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

(4)

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

2問題描述與建模

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

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

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

(5)

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

目標：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.

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

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

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

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

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

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

4驗證

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

圖1　任務流圖Fig 1　Task flow graphs

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

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

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

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

5結束語

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

參考文獻:

[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-)，男，山西介休人，碩士研究生，研究方向為無線傳感器網(wǎng)絡節(jié)點低功耗設計。

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