基于电池剩余电量的动态电压调节算法的改进
2008-07-28
作者：吴俊君，邓 军，詹 泳
摘 要： 低功耗的设计已经成为嵌入式系统设计中一个非常重要的方面，而动态电压调度算法DVS又被认为是降低功耗的一种有效手段。分析了已有的基于电池剩余电量的DVS调度算法局限性，通过实验对非周期性电流负载" title="电流负载">电流负载对应的电池单元行为进行建模，设计了一种新的低能耗" title="低能耗">低能耗调度算法。实验证明该算法能很好满足复杂的具有非周期性任务特点的嵌入式实时系统的性能与低功耗要求。
关键词： 电池非理想特性；自恢复效应" title="自恢复效应">自恢复效应；DVS算法；非周期性；低功耗
能量消耗问题是近几年在嵌入式系统设计中被广为关注的难点与热点，它严重制约着嵌入式系统的应用与发展[1]。降低能耗、延长电池寿命" title="电池寿命">电池寿命在军用或民用嵌入式系统中(如传感网络节点、微小卫星、PDA等)具有重要的现实意义。动态电压调节技术可以根据当前运行任务的需求来实时调节处理器工作电压" title="工作电压">工作电压，以达到任务完成时间和系统能耗之间的平衡，因而被广泛应用在嵌入式实时系统中。传统DVS(Dynamic Voltage Scaling)算法（Wiser and Govil[2]）多是基于最优化的电池单元模型，而没有试图对电池的理化现象精确建模。实际上不同的电流负载对应的电池单元行为不同，对不同情况下电池单元行为进行精确建模能提高电池利用率，延长其寿命，故进一步研究与电池特性相关的DVS策略非常有意义。
1 基于电池特性DVS算法本质
DVS策略主要基于一个事实，即：处理器的确定性能量消耗与工作电压呈平方正比的关系[3]：
C为工作电源电压，V为每周期的平均开关电容，f 为时钟频率，Vbs为衬底和源极之间的电压，Ij为节点漏电，K0、K1、K2均为常数。故在保证性能前提下，可根据系统工作状态动态调整电压达到降低能耗的目的。基于电池特性的DVS算法不仅根据系统工作状态来动态调节电压，而且还以电池特性为基础设计调度策略，以对电池合理利用，进一步延长电池寿命。Luo[4]等人研究提出的DVS策略通过降低电池的峰值功率来优化能量消耗；Rakhmatov[5]提议利用电池自恢复效应增加电容以节省能量等，这些都是基于电池特性的研究成果并取得较好的节能效果。
2 已有的基于电池剩余能量的DVS算法局限性
在Sukwon Choia[6]等人提出的一种基于电池剩余能量的可选择DVS策略中，对周期性电流负载对应的电池单元行为建模，并根据自恢复效应影响因子的强弱将电池放电过程分为三个不同的阶段，在不同阶段提供不同的策略起到了降低功耗的作用。但其存在下列缺点：
(1)建立的电池单元行为模型有一定局限性，只符合周期性电流负载的特点；而更为普遍的具有非周期性电流负载对应的电池单元行为模型与之存在较大差异，故需要对电池单元行为重新建模。
(2)在rate capacity区域计算Poptimal方法：基于过去周期段处理器利用率和当前时刻预测利用率来设定最优功率，即：
其中i≥1，P0=Pmax。而对非周期性和随机任务，简单的基于处理器以往利用率的计算模型不能提供最优的动态电压调节方法，需要考虑采取符合随机任务特点的新策略。
(3)在Alarm 区域电池进入低电压报警区，调节功率为Poptimal=Pmin可以降低能耗。但是如果结合动态电源管理DPM策略，对系统单元采用合理的休眠/唤醒算法，则能更好地减少不必要的消耗。
3 电池的非理想特性
大多数有关低能耗设计的研究，都将电池隐式认为是一个理想的电荷储存器，即：存储某个固定的电荷总量，而且直到电荷全部耗尽时电压才退出标称值。然而在实际情况中，电池没有任何一处接近于理想电荷存储单元。由于电池的化学特性，电池在满电荷至临界低电荷放电期间其放电率受到很多因素的影响。其中最主要的两个因素是：the rate capacity effect和the recovery effect[7]。the rate capacity effect现象反映了电流负载和电池寿命的非线性反比关系，而且电池寿命变化率比电流负载变化率要快。这主要是由于电池在生命周期中所能释放的容量总和与放电电流有关。因为从能量转换角度看，当电流越大时，电池在将内存的化学能转变成电能时的效率越低。电池的这种非线性特征可通过Peukert公式[8]来说明；the recovery effect现象反映了当电池空闲时电池电容有自恢复效应。因为电池在没有放电时，电极——电解质周围的有效物质通过扩散的方法会被重新填充，电池容量会有恢复现象。若能利用该特性，将有利于降低系统能耗，延长电池寿命。
实验在IPAQ3600 PDA上运行Linux，并修改Linux内核控制硬件来读取电池剩余电量值。系统预设5个任务，并通过随机策略调度其运行来模拟非周性任务的执行，在整个监测过程中，系统处于随机的繁忙和空闲交替状态中。实验数据显示（图1）：系统工作时间与电池剩余电量值局部呈不规则曲线状，但整体上曲线变化有一定规律，可以分为三个区域：在Recovery effect段（Lfull～LR）电容恢复现象明显，电池部分放电被恢复效应补偿，电量下降缓慢;在Rate capacity effect段(LR～Lc)恢复效应减弱补偿能力下降，电量下降加快，并与放电时间趋于线性关系；最后在Alarm段(Lc～Llow)放电行为占主导，电量急速下降。
实验结果：周期性电流负载和非周期性电流负载对应的电池电量监测曲线分别为细线条和粗线条部分。可以看到：非周期性电流负载对应的电池特性曲线仍然分为三个区域，但是其曲线波动特点很不规律。阶段1：前者曲线波动均匀，后者幅度较大；阶段2：前者呈线性下降，后者曲线围绕前者上下波动；阶段3：两者电量均迅速下降，前者下降平稳，后者有平缓部分。且由于任务的随机性，后者进入某区域的时间点相对模糊，其区域分割点与任务调度的随机过程有关。同样都是基于电池特性，但是在相同的特性区域，对应的电流负载特点不同，故在相同的特性区域应采用不同的策略以求低能耗最优。
4 基于电池非理想特性的DVS算法
4.1 DVS算法思想
根据曲线特点分析电池动态特性，从而设计合适的策略才是关键：该DVS算法根据电量余值L作出策略切换。当L∈(Lfull～LR)时，以充分利用电池恢复效应为主；L∈(LR～Lc)时，因L值持续减少，故在保证系统性能前提下尽量减少放电量；L∈(Lc～Llow)时，电池电量进入低报警区，系统单元采取关闭/唤醒的PM策略，需要牺牲部分性能以尽量延长电池寿命(Lfull、LR、Lc、Llow均为电池在某时刻的电量余值）。
4.2 确定电池状态
要根据电池剩余电量进行策略切换，首先要判断电池状态区间分割点。非周期电流负载对应的电池行为模型不像周期性电流负载对应的电池行为那么有规律，所以判断起来相对复杂。但共同之处在于：在相同的特性区域，同时间片能耗与补偿能量的大小关系类似。所以可以将处理器工作时间划分成若干时间段(如图2)，task期间在单位时间段内任务的平均能耗量ΔH(式(3))和随后相邻的Idle期间单位时间段内平均能量补偿量ΔB（式(4)），设ΔM=ΔH+ΔB，若有ΔM≤0现象出现，则电池处于recovery effect区；若在一定时间内持续ΔM>0，则认为恢复效应开始模糊，电池进入rate capacity区；若ΔM>0并且数值明显增大，则认为电池进入alrm区。Lmax为电池最大放电量，Li为I时间片时电池剩余电量，两个值都可通过监测获得。B(Qk)为Qk时能耗量为：
可推得Qi时能耗量：
在连续任务时间段内，单位时间片的平均能耗量：
相邻空闲时间段内，单位时间片平均补偿能量：
4.3 DVS算法设计
若电池状态为系统所知，则系统就可以根据电池当前状态选择合理的DVS策略。在Recovery effect区域，应考虑充分利用电池的自恢复效应，故可以使处理器Ppower=Pmax，用以缩短任务执行时间，使处理器更多地处于空闲状态以最大化恢复效应。在Rate capacity区，应在保证系统性能的同时，以降低任务执行时的电池负载为主。这个求解过程可以转化为一个在相关限制条件下求目标函数最值的非线性规划问题来解决，最优化对象是每个任务所对应的工作电压，分析过程如下。
(1)时序可行性检测（SFC）
假设在时刻t，任务队列中已经有N个被调度器接收但是还没有执行完毕的瞬态任务，记为SQ={Ti(Si，Ei，Di)，1≤i≤N}，参数依次表示任务Ti的到达时间、在最高电压下(即Vmax)的执行时间和截止时间。SQ中的各个任务按照Di的上升趋势进行排序。LE(Ti，Vi，t)表示任务Ti在时刻t基于工作电压Vi所对应的剩余执行时间。另外假设Ti(1，…，N)在进入SQ之前都经过时序可行性检测。其主要作用是保证SQ中所有任务的deadline得到满足。
(2)最优化数学模型。目标函数式(5)表示任务队列中所有任务执行完毕时所消耗的能量，其中P（Ti，Vi）表示任务Ti在Vi下所对应的功耗。三个限制条件分别从执行时间和工作电压上作出限制。由于Ti在进入任务队列之前都经过了时序可行性检测，因此该计算模型在式(6)、式(7)、式(8)限制条件下必然能够得到一组工作电压的最优解，记为OV={OVi，i=1，…，N}，其中OVi代表任务Ti所对应工作电压。
根据OV1来执行任务队列中处于起始位置的任务; 一旦出现新的瞬态任务Tnew，且该任务已通过SFC检验时，系统将为SQ重新计算最优解OV；而当前任务执行完毕时，其将从任务队列中移走并在OV中执行OVi->OVi+1的平移操作(i=1，…，N-1)。
在Alarm区，为了尽可能延长电池寿命，可结合基于动态超时的DPM策略，即当电池电压下降了ΔV(ΔV>0)后进入Alarm区域时，则在原有超时时限值t0的基础上进一步降低，从而尽量延长电池的使用时间；反之则恢复原t0值。
算法实现：
SelectiveDVS(Currrent task){
Open Dvs Mechanism；Time t0=value；
STATUS=Get current battery region information；
Switch(STATUS){
Case RECOVERY_REGION：Pi=Pmax
Case RATECAPACITY_REGION：
If(newtask) Calculate OV[n]；
else{ExecuteCurrentTask；RemoveCurrentTask；
Vdd=OVnext；Pi=KVdd3；}
Case ALARM_REGION：
Close Dvs Mechanism；
Start DynamicTime_outPolicy(t0)；
//t0 is first value } }
Time t1=t；//Dynamic time value
Dynamic time_out policy(t){
If(0<=t1<=t){
If(SystemTime>=t1) Close devices；
If(tasking) Sleep devices；
If(battery coulometry down)
t1--；
else t1++；}}
5 算法性能实验分析
实验分别采取本文设计的DVS算法、简单DVS（Pi=Pmin）、无DVS三种策略进行对比，分别称为算法1、算法2、算法3。如图3可知：由于在Recovery区算法1和算法3均设定Pi=Pmax，故电池行为方式比较接近，算法2由于Pi=Pmin没有最大化恢复效应，故曲线下降快；在Rate capacity区，算法1和算法2均考虑以降低电流负载为主，故后者曲线上升靠近前者曲线，而算法3功率仍为Pmax故电量下降较快；在Alarm区，算法1、算法2均采取了省电策略，故与算法3相比电量下降缓慢，且算法1与算法2相比，采取适当休眠策略要比持续Pmin节能效果好。表1为三种策略的效能比较。
基于电池特性的动态电压调节技术是降低嵌入式实时系统能耗的有效方法，也是当前研究的热门。少量系统的任务具有周期性特点，但更多的还是具有非周期性等随机特点的任务系统。本文通过实验对非周期性电流负载对应的电池行为进行分析，并在此基础上设计了适合于非周期性任务系统的策略。结果表明该算法能有效降低能耗,与无DVS策略相比，电池寿命延长17.3%，性能提高1.2%。该算法对降低非周期性电流负载的系统能耗比较合适，而对于混合型特点任务系统的低能耗策略还需要进一步研究。DVS技术在过去十几年的时间内取得了很大的研究成果，系统低功耗设计领域的研究空间仍然非常巨大。系统层的低能耗设计以及有关能耗最优化设计和分析技术在今后几年中还将是重要的研究主题。
参考文献
[1] 许海燕，卢伟，杨晨辉，等.低耗能嵌入式系统的设计[J].计算机应用研究，2002，19(6)：123-124.
[2] WEISER M，WELCH B，DEMERS A，et al.Scheduling for reduced CPU energy.Proceedings of USEN/X Symposium on Operating Systems Design，Monterey，California，United States，1994.
[3] FLAUTER K，REINHARDT S.Automatic Performance Setting for Dynamic Voltage Scaling[J].Mobile.ComPutingandNetworking，2001：26.
[4] LUO J，NIRAJ J K.Battery-aware static scheduling for distributed realtime embedded systems design.Proceedings of ACM/IEEE Conference on Design Automation, Las Vegas，Nevada，United States，2001：444-449.
[5] MARTIN T L，BATTERIES B.Power and performance：system issues in CPU speed-setting for mobile computing，Ph.D.thesis，Department of Electrical and Computer Engineering，Carnegie Mellon University，1999.
[6] SukwonChoi，HojungCha，RhanHa.A selective DVS technique based on battery residual Microprocessors and Microsystems 30，2006：33-42.
[7] BENINI L，CASTELLI G，MACII A.Extending lifetime of portable systems by battery scheduling.Proceedings of the Conference on Design，Automation and Test，Munich，Germany，2001：197-203.
[8] CaldariM，ContM，CIPPap，et al.Dynamicpower managementinanAMBA-basedbattery-poweredsystem[C].Electronics，CircuitsandSystems，2002.9thIntationalConfefence.2002，2：525-528.