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

田新越， 李翔宇

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

?

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

田新越， 李翔宇

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

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

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

0引言

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

目前，針對無線傳感器網(wǎng)絡(luò)節(jié)點的功耗管理算法大都面向單個微控制器構(gòu)成的節(jié)點系統(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)供能，問題的目標集中在解決調(diào)度問題和盡可能地利用電池有限的能量供給來完成更多的任務(wù)[6]。

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

1相關(guān)模型

1.1能量模型

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

1.2應(yīng)用模型

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

(1)

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

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

Ui=∑wjUj,?taskj∈Pri,

(2)

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

1.3硬件模型

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

(3)

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

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

(4)

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

2問題描述與建模

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

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

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

(5)

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

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

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

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

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

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

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

4驗證

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

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

硬件模型包含三個處理單元，其中,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，每個任務(wù)框的高度表征該任務(wù)的功耗水平，長度表征任務(wù)的執(zhí)行時間，虛線表示程序的截止時間，處于任務(wù)流圖尾節(jié)點的任務(wù)用灰色標注。圖3(a)是初始調(diào)度的結(jié)果，此時系統(tǒng)回報低且任務(wù)執(zhí)行超出了程序的截止時間。圖3(b),(c)是在不同的功耗預(yù)算下利用LINGO軟件做功耗管理優(yōu)化后的結(jié)果，可以看到程序的截止時間都已經(jīng)滿足，但由于圖3(c)中系統(tǒng)給的功耗預(yù)算相較于圖3(b)更充足，圖3(b)中系統(tǒng)回報經(jīng)過優(yōu)化提高到了546，圖3(c)中則達到了638。從任務(wù)執(zhí)行時間來看，圖3(b)中結(jié)果已能滿足應(yīng)用時間約束，而圖3(c)中還留出了更多的時間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é)點異質(zhì)多核SoC平臺的能耗問題,提出了一種充分利用采集能量提高系統(tǒng)性能的任務(wù)調(diào)度與功耗管理策略;針對異質(zhì)多核和能量采集的特點搭建了目標優(yōu)化模型，并將系統(tǒng)優(yōu)化問題歸結(jié)為對非線性規(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

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

中圖分類號：TP 301.6

文獻標識碼：A

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

作者簡介:

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

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