田新越， 李翔宇

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

?

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

田新越， 李翔宇

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

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

關(guān)鍵詞：能量采集； 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)； 異質(zhì)多核片上系統(tǒng)； 功耗管理； 任務(wù)調(diào)度

0引言

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

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

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

1相關(guān)模型

1.1能量模型

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

1.2應(yīng)用模型

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

(1)

式中Qj為任務(wù)taskj的工作量，Uj為相應(yīng)工作量對應(yīng)的回報(bào)。

每個(gè)程序執(zhí)行完成的回報(bào)是其任務(wù)流圖中包含的所有任務(wù)執(zhí)行完成后所得到的回報(bào)的加權(quán)和

Ui=∑wjUj,?taskj∈Pri,

(2)

式中wj為任務(wù)taskj的回報(bào)在程序Pri中所占的權(quán)重。

1.3硬件模型

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

(3)

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

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

(4)

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

2問題描述與建模

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

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

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

(5)

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

目標(biāo)：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)回報(bào)是應(yīng)用集合A中所有程序回報(bào)的加權(quán)和(σi是程序Pri的回報(bào)在集合A中所占的權(quán)重)。任務(wù)執(zhí)行在某個(gè)處理單元上的功耗由P表示，所有任務(wù)執(zhí)行時(shí)的功耗總量要小于系統(tǒng)功耗預(yù)算PB。任務(wù)工作量(Q)和處理單元的執(zhí)行電壓(V)都有上下界。D是每個(gè)任務(wù)開始執(zhí)行的時(shí)間，對D的約束是為了保證有依賴關(guān)系的任務(wù)在處理單元上先后執(zhí)行。應(yīng)用集合A中全部程序所包含的每一條路徑上所有任務(wù)執(zhí)行時(shí)間的和要小于該路徑的截止時(shí)間。

3任務(wù)調(diào)度和功耗管理算法

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

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

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

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

4驗(yàn)證

本文利用任務(wù)圖生成程序TGFF[12]隨機(jī)生成的一組任務(wù)流圖對模型與算法進(jìn)行驗(yàn)證。應(yīng)用模型包含了三個(gè)程序，每個(gè)程序的任務(wù)流圖見圖1。

圖1　任務(wù)流圖Fig 1　Task flow graphs

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

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

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

圖3　不同功耗預(yù)算的調(diào)度結(jié)果Fig 3　Scheduling result of different power consumption budget

5結(jié)束語

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

參考文獻(xiàn):

[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

*基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61006021)

中圖分類號：TP 301.6

文獻(xiàn)標(biāo)識碼：A

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

作者簡介:

田新越(1990-)，男，山西介休人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)低功耗設(shè)計(jì)。

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