时序约束下的快速求解算法
由于电池状态变化的随机性，解决式（2)中随机 最优问题是非常困难的.为了求解该最优问题，我们 通过等价近似的方式将其转化为一个确定性问题， 以提高求解效率.
定义Er(S；，艮)叁ErP(S,，K,)为第i个时间 单元的平均恢复能量单元数，其中，艮表示在一个 时间单元中电池恢复的能量单元数，P(S,，K,)表示 在第i个时间单元恢复效应发生概率，而S是关于 电池状态的另外一种描
基于上面的定义，提出如下命题：
命题1.如果初始的电池运行信息为（S^l^) 以及操作提示符0;;已经给定，则义给出了一个关 于S,平均值的下限，即S;
根据命题1，式（2)的随机最优问题可以以近似 的方式转化为确定性的最优问题，转化结果如
现在，式（1)和式（2)构成随机双目标最优问题，巳经 近似等效转化为式（1)和式(6)构成的确定性双目标 最优问题.为了求解该双目标优化问题，首先将式（1) 作为一个主目标，式（6)作为一个辅目标来求解.定 义只„为采用系统电压％来给任务g供电所需的电 池能量单元数，其中{1,2,3,{1,2, 3,…，可以按照文献[1]给出的方法求出.定 义TS; = (<，4，^)来描述经过电压调整后任务的 属性，其中芯，<，<分别表示相应的任务执行所需 的平均电流、平均执行时间，以及开始执行时间；则 式（1)可以转化为
Step2中的核心思想是基于二叉树的搜索.我 们用一个例子来说明该方法，在图2中，给定4个任 务，经过Stepl得出E/(是）e {1，2，3,...’4}.我们考 虑3条路径，首先是对任务E/(l)进行电压调整，将
图2基于二叉树的搜索
系统电压调至最低，如果此时时序约束满足（<了）， 则继续右分支移动，对任务E/(2)进行电压调整，将 电压调整到最低；否则继续往左分支移动，将电压调 整的次低，然后再次对任务£/( 1)进行电压调整；判 断此时任务序列调整后的时序约束是否满足.因此， 搜索分支是向右移动还是向左移动取决于对当前任 务E/U)进行电压调整后的时序约束.若满足时序 约束，则向右分支移动，处理下个任务E/a + 1);否 则向左移，重新调整电压到次低来处理当前任务 E/(«，直至时序满足• .
基于二叉树的搜索方式实现简单、高效，充分考 虑了能耗和时序的要求，具有很强的实用性.在图2 中，有3条可能的路径分别为 ,
1)右边路径瓦/(1):%，£：/(2):巧，£/(3): vi，£/⑷：^i;
2)中间路径 v2，Ef(4) ：v,；
3)左边路径 £/(l):T；3，E/(2):t；2，E/(3): Vi ,Ef(4) -.vi.
根据调度结果，可以获得操作提示符O,”为了 保持电池在执行完所有任务后仍然维持在很高的状 态，将式（6)转化为
根据参考文献[10]提出的原则，由于f：厂（S;， K,)随着S[的增大而增大，因此为了能够恢复更多 的能量单元，就应该把空闲时间单元放在任务队列 开始执行的阶段，因为此时式是比较大的.尽管如 此，由于Sa。,是电池实际可以供给的能量单元数，当 劣+£厂时，没有能量单元可以再恢 复，因此我们对前面调度产生的空闲时间单元进行 再分配的方法就是在满足S; +Er(S；，iC,)
返回列表
3实验结果
3.1仿真环境
为了验证本文方法，采用了 Intel Xscal处理器
元内执行所有Q i任^所需的总能量单元数.在式
(7)中将求解的粒度从时间单元上升到任务本身，可 以极大地提高执行效率.
在式（7)中，可以根据最终求解出的t'q计算出 0,v.为了求解式（7),可以通过降低电压来降低系统 能耗但是也延长运行时间[1]这一个规律，设计出一 个基于二叉树的快速求解方法，该方法实用性比较 好.定义/^，^1, = 7^，将其作为任务9的能效因子； 用该能效因子作为二叉树求解方法的判断符.根据 文献[7]，如果能效因子变大，相应的任务应该首先 被调度执行，以确保更低的能量损失.