无线传感器网络节点任务调度与功耗管理算法研究*

田新越， 李翔宇

(清华大学 微电子学研究所，北京 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。