（计算机应用技术专业论文）能量最优化问题的算法研究.pdf

-：_j 露tii u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y o fc h i n a adi s s e r t a t i o nf o rd o c t o r sd e gr e e o p t i m i z a t i o n so fp o w e r a ll o c a t i o n a u t h o r sn a m e ：w e i w e iw u s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o n s s u p e r v i s o r ：p r o fe n h o n gc h e n d r m i n m i n gl i f i n i s h e dt i m e ：m a y1 0 眦，2 0 11 伽4 49洲8 0川9jjj川- 肌y 中国科学技术大学学位论文原刨性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作 了明确的说明。 作者签名： 签字日期：! ! ! ：! ! ! f ! 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 团公开口保密( 年) 作者签名： 签字日期： 主未夏 - 弓 、气州i ， 矽i i q o 导师签名： 签字日期： i 摘要 摘要 移动用户( 设备) 在2 0 1 0 年达到了5 0 亿的庞大数量鉴于移动设备的数量和 他们都使用电池供电的事实，设计高效的算法来减少设备的能量消耗和合理地 使用能量来最大化整个移动网络系统的数据吞吐量受到了广泛的关注近似算 法设计和分析是算法理论方向十分重要的领域和评价算法性能的重要手段本 文从理论分析的角度研究了基于调度和分配策略的算法以最优化能量的使用 本文关注的是计算最优解的算法，以及以近似比作为性能评价的近似算法，分别 给出了针对单一设备的最优近似的能量调度算法和针对移动系统的具有最优在 线近似比的能量分配算法 单个设备上的能量优化：针对单一设备，动态电压调节技术提供了调节处理 器的速度以控制能量消耗的能力本文首先研究了理想模型和相对更实际的加 速模型和处理器模型其中理想模型允许处理器瞬间变速而加速模型限制处理 器的加速率最大为k ，存储器模型则是将存储器操作时间也加以考虑目标是找 到能够在期限时间内完成所有任务的最小化能量消耗的最优调度本文针对单 一设备的研究包括以下结果， ( 1 ) 改进了理想模型下的最优解计算时间：理想模型的理论研究最早可以追 溯到1 9 9 5 年y a o 等人的富有启发性的工作，目前为止最好的是o ( n 2 l o g n ) 时间算 法来计算最优解我们关注一类称为一致性的任务集合，它们满足更早到达的任 务不会更迟结束基于对最优解结构的更加深入的理解和观察，本文改进了计算 最优解所需的时间复杂性，给出了d ( n 2 ) 时间的新算法 ( 2 ) 首次从理论分析角度给出了计算加速模型最优解的算法：区别于理想模 型，比较实际的考虑时间延迟的模型有加速模型和存储器模型，在此之前只有一 些启发式算法的研究，而没有关于它们的比较理论的研究对于加速模型，我们 从所有任务都有共同到达时间的特例开始研究，设计针对它的算法并将其作为 一个子程序，来确立加速模型下的最优解本文首次给出了计算其最优解的算法， 算法时间上只需用0 ( n 2 ) 时间 ( 3 ) 解决了处理器模型的复杂性和额外资源条件下的近似算法：本文证明了 处理器模型的最优解计算问题是n p 难解性鉴于难解性的结果，之后从近似算 法的角度，本文给出了s 倍额外速度条件下的具有常数近似比的算法这个结果 说明了用多项式时间的算法能够常数近似于需要指数计算时间的最优算法 摘要 系统层面上的能量分配：以上的内容都是从设备上的能量优化的角度进行 研究，之后本文关注系统层面( 移动网络) 的能量分配问题受限于设备有限的能 量和一些其它物理限制，总体的目标是最大化整个系统的数据吞吐量模型综合 考虑了系统中变化的信道状态，有限的能量和用户之间的干扰这些物理限制同 时，考虑系统的开放性和用户之间的竞争行为，用户可能通过欺骗私有数据信息 的方式来最大化自己的收益，以至对系统的性能产生不利影响方法是使用博弈 论中的机制设计理论来抑制用户使其没有对系统进行欺骗的动力( t r u t h f u l m e c h a n i s md e s i g n ) ，使用在线的竞争比分析( c o m p e t i t i v ea n a l y s i s ) 来证实系统的总 体性能不会受到太大影响关于系统层面的能量优化研究包括以下结果， ( 1 ) 设计出了能抑制用户欺骗行为的机制：本文设计出了一个随机的机制， 证明了它可以保证用户没有进行欺骗的动力，即满足t r u t h f u l 的要求 ( 2 ) 改进了目前关于任意算法所能达到的性能下界：关于任意算法所能达到 的最好性能，目前只有关于确定性算法的性能下界，本文改进了目前为止为好的 关于下界的结果，证明所有随机算法最好只能达n f l o o g 譬) 近似，这里使用到的 是y a o 的极大极小原理 ( 3 ) 证明本文所设计的机制是最优近似的：即机制在系统的总数据吞吐量评 价上是o ( 1 0 9 譬) 近似的这个结果也从性能评价上证明该机制不仅能应对用户的 自私的竞争行为，同时在系统的总体收益上能达到最佳性能( a y s y m p t o t i co p t i m a l c o m p e t i t i v e ) 鉴于近似比分析是以最坏情况的算法性能作为评价手段，这个结果 说明不存在其它算法能够在最坏情况的表现上大幅改进本文所设计的算法和机 制 关键词：能量最优化，移动网络，d v s 动态电压调节，速度调节，任务调度， 能量分配，机制设计 i i 一 a b s t r a c t a b s t r a c t t h en u m b e ro fm o b i l eu s e r s ( d e v i c e s ) r e a c h e s5b i l l i o ni ny e a r2 010 d u et ot h e g r e a tn u m b e ro fd e v i c e sa n dt h ef a c tt h a ta l lt h ed e v i c e sa r ee q u i p p e dw i t hl i m i t e d b a t t e r y ( p o w e r ) ，d e s i g n i n ga l g o r i t h m st os a v et h ee n e r g yu s a g eo nas i n g l ed e v i c eo r p r o p e r l yu t i l i z et h ep o w e rt om a x i m i z et h ed a t et h r o u g h p u to ft h em o b i l es y s t e m r e c e i v e s m a n yc o n c e m s w et h e o r e t i c a l l y s t u d y s e v e r a l s c h e d u l i n g a l l o c a t i o n p r o b l e m st oo p t i m i z et h ep o w e ru s a g eo nad e v i c ea n dt h es y s t e m w ep r o v i d ea t h o r o u g hs t u d yo na p p r o x i m a t i o na l g o r i t h m s ( o re x a c t ) t oc o m p u t et h e ( o p t i m a l ) p o w e ra l l o c a t i o no nas i n g l ed e v i c ea n do n l i n ea l g o r i t h m sw i t ho p t i m a lc o m p e t i t i v e r a t i ot om a x i m i z et h ed a t at h r o u g h p u to nam o b i l es y s t e m d y n a m i cv o l t a g es c a l i n gt e c h n i q u ep r o v i d e st h ec a p a b i l i t yf o rp r o c e s s o r st oa d j u s t t h es p e e da n dc o n t r o lt h ee n e r g yc o n s u m p t i o n w es t u d yt h ep e s s i m i s t i ca c c e l e r a t e m o d e lw h e r et h ea c c e l e r a t i o nr a t eo ft h ep r o c e s s o rs p e e di sa tm o s tka n di o b s c a n n o tb ee x e c u t e dd u r i n gt h es p e e dt r a n s i t i o np e r i o d t h eo b j e c t i v ei st of i n dar a i n - e n e r g y ( o p t i m a l ) s c h e d u l et h a tf i n i s h e se v e r yj o bw i t h i ni t sd e a d l i n e t h ea l i g n e dj o b s w h e r ee a r l i e rr e l e a s e d j o b sh a v ee a r l i e r d e a d l i n e sa r es t u d i e d w es t a r t b y i n v e s t i g a t i n gas p e c i a lc a s ew h e r ea l lj o b sh a v eac o m m o na r r i v a lt i m ea n dd e s i g na n d m 2 ) a l g o r i t h mt oc o m p u t et h eo p t i m a ls c h e d u l eb a s e do ns o m en i c ep r o p e r t i e so f t h eo p t i m a ls c h e d u l e t h e n ，w es t u d yt h eg e n e r a la l i g n e dj o b sa n do b t a i na no ( n 2 ) a l g o r i t h mt oc o m p u t et h eo p t i m a ls c h e d u l eb yu s i n gt h ea l g o r i t h mf o rt h ec o m m o n a r r i v a lt i m ec a s ea sa b u i l d i n gb l o c k b e c a u s eo u ra l g o r i t h mr e l i e so nt h ec o m p u t a t i o n o ft h eo p t i m a ls c h e d u l ei n t h ei d e a lm o d e l ( k = o 。) ，i no r d e rt oa c h i e v eo c n 2 ) c o m p l e x i t y , w ei m p r o v et h ec o m p l e x i t yo fc o m p u t i n gt h eo p t i m a ls c h e d u l ei nt h e i d e a lm o d e lf o ra l i g n e dj o b sf r o mt h ec u r r e n t l yb e s tk n o w nd ( n 2l o gn ) t oo ( n 2 ) w e f u r t h e rs t u d yt h es p e e ds c a l i n gp r o b l e mw i t hm e m o r y c a c h ec o n s i d e r a t i o n e a c hj o b n e e d ss o m et i m ef o rm e m o r yo p e r a t i o nw h e ni ti sf e t c h e df r o mt h em e m o r y c a c h e w e i n v e s t i g a t et h eg e n e r a lj o b sf o rw i t h 。c a c h em o d e lw i t hr e s o u r c ea u g m e n t a t i o nw h e r e t h em e m o r yo p e r a t i o nt i m es p e e d su pb ya tm o s t8t i m e s w ep r o p o s e da ( 2 a 者) a 2 。a p p r o x i m a t i o na l g o r i t h mf o rs u c has e t t i n g w et h e nt u r nt ot h ep o w e ra l l o c a t i o np r o b l e mo nam o b i l es y s t e m ( w i r e l e s s n e t w o r k s ) t h el i m i t e dp o w e r , d y n a m i cs t a _ t u sa n di n t e r f e r e n c e sa l ea l ls e r i o u s c o n c e r n so ft h ew i r e l e s sc h a n n e l s a p a r tf r o mc o n s i d e r i n gt h ep h y s i c a lc h a r a c t e r i s t i c s ， i i i a b s t r a c t a n o t h e r i m p o r t a n td i r e c t i o n i tt os t u d yt h es e l f i s hb e h a v i o r so ft h e u s e r s ( e g t r a n s m i t t e r s ) w es t u d yt h eo n l i n ep o w e ra l l o c a t i o np r o b l e mo nt h et i m ev a r y i n g c h a n n e l st om a x i m i z et h eg l o b a lg a i n so ft h en e t w o r kw i t hi n t e r f e r e n c e b e s i d e st h e p h y s i c a lc o n s t r a i n t s ，t r e a t i n ge a c hu s e ra sa l li n d i v i d u a la g e n t ( p l a y e r ) i nag a m e t h e o r e t i c a lv i e w , w es i m u l t a n e o u s l yc a p t u r et h es e l f i s hb e h a v i o ro ft h eu s e r s t h e u s e r sa r ea l l o w e dt oc h e a to nt h e i rp r i v a t ev a l u e ( p o w e rb u d g e t ) t oi n c r e a s et h e i ro w n u t i l i t y w ea i ma tm a x i m i z i n gt h eg l o b a lg a i n so ft h en e t w o r kw h i l ee n s u r i n gt h a te a c h a g e n to p t i m i z e si t so w nu t i l i t yb yr e p o r t i n gi t st r u ep o w e rb u d g e t ( a d m i t st r u t h f u l m e c h a n i s m ) w ed e r i v eag e n e r a ll o w e rb o u n d1 2 ( 1 0 9 鲁) - c o m p e t i t i v ef o ra n y r a n d o m i z e da l g o r i t h mu s i n gy a o sm i n i m a xp r i n c i p l e w ef u r t h e r p r o p o s ea r a n d o m i z e do n l i n ea l g o r i t h mw h i c hn o to n l ya d m i t st r u t h f u lm e c h a n i s mb u ta l s oi s p r o v e do ( 1 0 9 鲁) c o m p e t i t i v ei ne x p e c t a t i o na n dh e n c eo p t i m a lw i t hr e s p e c tt ot h e c o m p e t i t i v er a t i o k e yw o r d s ：e n e r g yo p t i m i z a t i o n ，m o b i l es y s t e m ，d v s ，s p e e ds c a l i n g ，j o b s c h e d u l i n g ，p o w e ra l l o c a t i o n ，m e c h a n i s md e s i g n i v 目录 目录 第l 章绪论l 1 1 研究背景与选题意义1 1 1 1 能量优化问题1 1 1 2单个设备上的能量最优化2 1 1 3移动网络系统的能量分配3 1 2相关研究5 1 2 1单个设备上的能量优化：动态电压调节5 1 2 2系统上的能量分配：动态能量分配6 1 3本文的贡献7 1 3 1单个设备上的能量优化7 1 3 2移动网络系统的能量分配8 1 4文章结构9 第2 章单个设备的能量优化：两个简单的算法1 1 2 1模型和符号l l 2 2加速模型：到达时间一致的任务的最优调度1 2 2 3理想模型：一致性任务的最优调度。1 9 2 4j 、结2 4 第3 章单个设备的能量优化：一般模型的算法2 5 3 1加速模型：一致性任务的最优算法2 5 3 1 1基本性质2 5 3 1 2用d ( 扎2 ) 时间算法来计算0 尸2 7 3 2存储器模型4 0 3 2 1n p 难解性。4 0 3 2 2额外资源下的近似算法4 2 3 3小结4 4 第4 章移动网络系统上的能量优化4 5 4 1准备知识4 5 4 1 1 模型4 5 4 1 2机制设计m e c h a n i s md e s i g n 4 5 v 目录 4 1 3 在线机制设计4 6 4 2 一个随机的在线机制4 7 4 2 1固定信道增益模型f i x e dc h a n n e lg a i nm o d e l ( f c g ) 4 7 4 2 2 一般模型的随机分配方法4 8 4 3m ，是期望上t r u t h f u l 的4 9 4 4所有随机算法的性能下界5 2 4 5对r a l l o c 的性能分析5 4 4 5 1在固定信道增益模型上f b a l a n c e 算法的分析5 5 4 5 2扩展到一般模型下的r a l l o c 算法6 9 4 6小结7 0 第5 章本文总结7 3 5 1本文主要的贡献和创新之处7 3 5 1 1单个设备上的研究7 3 5 1 2系统层面上的研究7 4 5 2下一步的研究工作7 5 参考文献7 7 致谢8l 在读期间发表的学术论文与取得的研究成果8 3 攻读学位期间参与的科研项目情况8 4 v i 图表列表 图表列表 图1 ：当1 8 1 ( t ) i o 时总有任务在执行之中能量等于功率函数在所有s 讹) = 0 且s ( t ) o 的 区间上的积分，h o e = f t l s ( t ) = o , s ( t ) op ( s ( t ，s ) ) d t 在此限制下，一个在截止时间前 完成所有任务并且速度函数满足i s 讹) l k 的调度被称为可7 渤调度在可行调 度s 中，用b l o c k ( 时间块) 来表示一个具有恒定速度的局部最长区间需要注 意的是相邻时间块间总有一个变速区间a c c e l e r a t i o ni n t e r v a l ( 用于变速的时间段) 因为变速需要一定的时间，在这一区间上没有任务执行在所有可行调度中，具 有最小的能量消耗的调度叫作最彷调度 假设t 。= m i n i r i ，t l = m a ) c i 也在调度s 中，所有在区间【n ，6 】上执行的工作 量用，6 1 ( s ) 表示若任务j 满足j ( j ) = 【r ( j ) ，d ( j ) 】【n ，6 】，我们说- 厂是内嵌 ( e m b e d d e d ) 在陋，b l o e 的简化起见，当我们说“第一 个时间或区间时，是指 时间轴上由左到右最早的时间使用( l ia n dy a o ，2 0 0 5 ) q b 的相似定义，如果t 让 是一个任务的截止时间( 或到达时间) 并且s 在小区间【t 札一a t ，t u 】( 或 ，t u + a t ) 上执行该任务，其中0 ，则说s 中t u 是紧的截止时间( t i g h t d e a d l i n e ) ( 或紧的到达时间t i g h ta r r i v a lt i m e ) 假设w ( t l ，t 2 ) 表示所有到达时间 第2 章单个设备的能量优化：两个简单的算法 在1 之后且截止时间在2 之前的任务的总工作量，即叫( t 1 ；t 2 ) = ，( ，) 【札t 。】c ( j ) 定义密度( i n t e n s i t y ) i t t ( t l ，t 2 ) 为一个确司l ，t 2 】上的平均工作量w ( t l ，t 2 ) ( t 2 一t 1 ) 2 2 加速模型：到达时间一致的任务的最优调度 对于到达时间一致的任务，不失一般性可以假设它们一开始就到达了，即 r i = 0 ，1 isn 本文将首先研究最优解的一系列性质以设计多项式时间的算法 来计算最优调度直觉上的证明思路如下与理想模型的最优解进行比较，当速 度由高到低变化时，某些时间会因加速而被占用最优解由若干个时间块组成并 且速度是非增的( 每两个时间块之间的速度是单降的) 为了找到所有时间块， 我们试图找一些“紧”的时间点( t i g h tp o i n t s ) ，它们是每一个降速区间的起点， 因为如果降速区间再延迟则至少有一个任务将错过截止时间最多有礼个时间块 需要计算，导致最终的算法将是d ( n 2 ) 时间的 注意本文假设每一个引理中“最优解”满足所有之前在该节中所出现过的引 理当上下文清楚时本文不区分闭区间h t ，t 2 】和开区间( t l ，t 2 ) 引理1 给定一个可行调度s ，其中速度函数s ( ) ，假设区f n - - ( t n ，t 口+ a t ) 是用来 加速的( 即s 他) 0 ，t ( t 口，t 口+ ) ) 并且8 ( t d ) = s ( t 口+ t ) 则另一调度雪， 其中速度函数吾( ) 定义如下，它将工作量q t , + a t , t 1 ( s ) 左移a t 时间，则它是 可行的并且消耗与s 相同的能量 f8 ( t ) t 【t 。，t 。】 吾( f ) = s ( t + a t ) t ( t o ，o ，一a t 】 l 0 t ( o ，一a t ，t l 】 证明：首先，证明雪是可行的在s 中，假设任务正在t o + a t 之后且在截止时 间d i 前完成因为五在起始点心= o 可运行，而且它没有在( t 口，t 口+ z x t ) 期间加 速，当左移五的运行区间时间，最终的调度仍然是可行的相似地向左移区间 + a t ，t ，) 时间，最终的调度雪仍然可行而且，当执行区间左移后，没有 工作量在最后的时间t f a t 上执行，所以区间( t ，一a t ，t 1 ) 消耗能量为0 最后， 工作量c t + a t , t j ，】( s ) 的执行配置( 速度) 并没有变，雪有和s 一样的能量损耗证 毕 引理2 在最优调度中，速度函数将以尽量快的速率加速，即或者i s 他) l = k 或者i s 他) i = 0 1 1 第2 章单个设备的能量优化：两个简单的算法 ；_ 么y 西 h ： ： ： ： ：7 t o ： ： ： ： t 4t ctf t tt ct b t r t b t c t f 图1 ：当i s i f t ) i k 时的变换 证明只需要移除0 i s 他) i k 的可能性如图l 所示，当0 s 他) k ，先证 明另一个以最快速率加速的调度将损耗更少或相同的能量假设( t d m t ) 是第一 个0 s i f t ) k 的加速区间，设置区间( 如，t 。) 上的加速率8 他) = k 因为最终的加 速目标速度不变，这暗示t 。 t b 不论区间( t b ，t f ) 上的速度函数如何，它都能进 一步左移t b t c 时间这个变换将移除区间( 如，t b ) a e 2 口速率等于0 s 他) k 的 情况并根据引理1 保证最终的调度不会增加能量相似地可以处理 一k s i f t ) 0 反复使用此变换，可以保证最优解在区间( 以，t f ) 上1 8 他) l = k 或 i s ，( ) i = 0 口 引理3 在最优调度中，速度 甬g a s ( t ) 是非增的 _ i 导零 t l t ht t t tl l i f c t 。 ( a ) 图2 ：去除，( ) = k 证明只需排除s 讹) = k 如果相反地有些区间上s 他) = k ，假设第一个 s 他) = k 的区间为( t 口，t b ) ，如图2 假设t 。是t 6 之后最近的一个满足8 他) o 的 时间点，即如：a r gr a i n ( s 讹) o ) 假设时间块( 拓，t c ) 上速度为s 2 注意t 口之前的速 度是非增的可以假设t 口的相邻时间块( 吃，t o ) 上速度为8 1 ，其中s l 8 2 现在证 明存在其他调度雪消耗更少能量方法是将q “a 】( s ) 与唧： 】( s ) 和之前的相邻 时间块合并成一个新块( 矗，t ：) 并假设区间( 艺，t c ) 上( ) = k 合并操作将保证新 块执行与参与合并的块一样多的工作量合并操作从右到左直到最后的吒前的 任务有一个比新块更高的速度假设新速度在( ，) 中为8 ，我们先证明( t 。，t c ) 中能量是减少的讨论两种情况8 , x 8 0 和8 a 8 0 ，其中8 0 是起始点t 。上的速度 首先，如果8 a 8 0 ，则q 。舨) ( s ) 在雪的一个单独的时间块中( ，t ：) 执行注意这 样一个调度是可能的( 因为所有任务在新调度中都可完成) ，而在区f 日l ( t 。，砭) 上的 p ， ，t 0 ：岭 ， iil， ， 第2 章单个设备的能量优化：两个简单的算法 速度是非增的而且，根据函数p ( s ) 的凸性，新调度消耗了更少的能量其次，若 8 a 8 0 ，贝l j c ( t , , t c ) ( s ) 在雪的一个单独的时间块( 以，t ：) 中执行，雪也同样是一个更好 的调度 注意第一个满足8 他) = k 的区间已经移到( ：，t e ) 接下来讨论下面两种情况： t c t t d 中s 心) = k 和s 他) = 一k 如果t c t t c t ：，则假设t ：是关于时 间线t = t c 的t ：的对称点( 见图2 ( b ) ) 注意蚕( ：) = 吾( ：) 可以将( 匕o ，) 中的速度 函数s ( ) 左移名一艺时间这将排除( 拓，“) 中s ( ) = k 的可能性然后可以反复 处理( 妇，t ) e e 的8 他) = k 若t a t c t 。一t ：，假设吃是t d 关于时间线t = t 。的对 称点( 见图2 ( c ) ) 可以将( 幻，o ，) 中的s ( t ) 左移t e 一缘则( t ：，：) 将是第一个满足 s 犯) = k 的区间因此，反复使用以上分析可以将满足s 他) = k 的区间移动到最 右边( # ，t ) 而o ，之后又没有工作量，这样可以除去最后的加速区间( t ) 证毕 口 引理4 存在一个最优解使所有任务都按e d f 顺序( 更早截止时间先行) 执行 证明假设五+ 。是第一个违反e d f 顺序的任务，即所有任务按如下顺序完成 盯( 歹) = ( 以，五，五+ ”五十l ) 注意仃( 了) 中五和五+ l 之间的任务有比也+ 1 更大的截止时间现在证明以仃7 ( 了) = ( ，也，五+ 1 ，五+ t ) 顺序执行任务， 即交换盯( 歹) 中五+ 。和五+ l ，且仍然以原有速度执行，将构成另一个可行调度明 显地，任务 ，五在截止时间前可完成而且，因为速度函数没有变化，在 口7 ( 了) 中任务五+ 。与盯( 歹) 中任务五+ 1 有相同的完成时间即，五+ 。并不会在也+ 1 后 完成( d 件l 吐+ 。) 而且，0 够) 中， + 1 和五+ 。之间的任务也能在截止时间前完 成，因为它们在盯7 ( 歹) 中在五+ l 前已经完成所以新的调度是可行的且能量未发 生变化使用相同的调整策略，可以最终得到一个调度，它的完成时间是按e d f 顺序执行的口 引理5 最优调度s 中，任务五只有一个速度m i ns 0 坠。民 ， 速度满 足寄b 茫岳 ， 则有 鍪。丢圣t 耳南+ 翟。孺言爵对，其中a 1 证明 首先注意到o t 可以是非整数定义a 1 = 冬2 文 而南+ e l - 2 覆焉b 5 1 2 作量z t 可以被分为竹一1 个部分 z 2 ，z ，z 乞假设= e 纭z l ，其中2 i n 假设z ：在z 长的时间内执行假 设z = e 纭丑注意蓦= 乃z l ，正= e t - _ 2 t 和z 1 = 垒z z ：现在研究如下差值 工?z 宁 开哥一疆耳蕊尸 尊一南 = ( 狞) a - 孔一( 卫t t + a 。、y q ( 五十a i ) = ( 凳) a 。( 墨2 z ) 一( 瓦旨) a ( 銎2 z + e i = 2 6 i ) = 銎2 ( 毒) 口霉一銎2 ( ) a ( z + 盈) = 翟2 番一e t - _ 2 南 第二个等式是因为噩= 警2 t 7 r a l = 翟2 国第三个等式成立是因为莠= 嚣 且一t ：+ a t = 嚣盘= 毒矗蠹= 霸k 现在只要证明 墨。毒备一鍪2 南冬。南一銎2 暑 为此， 我们将证番+ 著南+ 南 定义 ，( ) = 嵩+ 强南现在只需证在z t z + 瓯时，他) 0 ，它将使得 ，( z ) ，( z + 盈) 于是 ，( t ) = ( 1 一q ) 坐t a 一( 1 一q ) 豫南= ( 1 一q ) ( ( 譬) a 一( 南) a ) ，7 ( t ) = ( 一q ) 互一( 一q ) 币南= ( 1 一q ) ( ( 争) a 一( 稀) a ) ， 因为( 矿) 7 = q 护，其中任意实数q 1 因此，讹) 随增加而增加，其中q 1 现 在说明，7 ( z + 尻) 0 根 据坛 t i - l 6 i ， 有 ，馁+ 文) = ( 1 一口) ( ( 毳) 。一( 盎) a ) o ，因为毳= 卫t 。+ a x 盎这就 完成了证明口 引理6 存在最优解s ，其中每个时间块的完成时间f ( 它满足 l i m + 一8 他) = oal i r a 叶f + s 他) = 一k ) 是一个紧的截止时间 irlriiilr-i_r-l ； f-li_， -ii l-ii jj，rirlr-ir -i-， 第2 章单个设备的能量优化：两个简单的算法 ( a ) - - - 4 刁 图3 ：推迟操作p o s t p o n ep r o c e d u r e 证明假设相反地b l o c k p 的完成时间是第一个非紧的截止时间则对于每一 个b l o c k p 前的时间块，它们的完成时刻都是一个紧的截止时间假设i o 是b l o c k p 之前最紧邻的时间块的完成时间如果这样的时间点不存在，可以设置晶= 0 先证明( s o ，矗) 间的工作量可以以更低速度更长时间来执行以减少能量我们从 简单情况开始如图3 ( a ) 所示，在新调度雪中，速度吾( ) 用虚线表示，五的完成时 间延迟到了它的截止时间d i ( 延迟了d i 一1 时间) 同时，我们保证d i 之后的工 作量仍然与最初调度有一样的完成时间为此，任务五十l 。，厶将以一个比s ( t ) 中大一点的速度执行先考虑雪是可行的情况，即没有任务在雪中错过截止时间 注意以此假设，在以的完成时间被推迟到截止时间之后，( d i ，t ) 中的速度分配将 是唯一的( 因为速度季( d f ) 是唯一确定的) 根据性质1 ，现在证明这样的调度将 消耗更少的能量假设吨之后的时间块在s t 有执行时间t 2 ，且执行的 工作量分别为x 2 ，z m 而工作量巧在雪中将执行t j 一向时间( 2 j m ) 条 件 警和。，x + l 南显然满足，其中z l ，t 1 和分别表示工作量 g 厶柏( s ) ，执行工作量x l 的时间长度，以及s 和雪中执行z ，的时间长度的差值雪 少于s 中消耗的能量差值为墨1 暑一石羞b 一：2 瓦写：t 因此只需要证 a 凳2 如 为此，考虑时间u 矗，它是s ( ) 和否( t ) 的第一个交叉点，则s ( u ) = 蚕( u ) 注意 在最后的时间o ，速度满足季( o ，) s ( t ，) 在区间【u ，t 扎s ( t ) 使用比i ( ) 更多 的时间用于变速，因为尘掣 坐掣所以用于执行任务的长度( 即【u ，t ，1 中满足s 他) = o 的区间长度) 在雪中是比s 大的而且，两个长度之间的差值正 好等于一如一一轧因此有 翌，以 现在考虑更一般的情况，其中五推迟到它的截止时间后造成某些任务错过截 止时间注意在图3 ( a ) 中的变换对于只推迟以到一个任意小于盔一的量的情况 仍然成立所以先推迟五的工作量到一个小于也一毛的量，它正好导致以在其截 止时间上完成，而其他任务都在其截止时间前完成。如果k i ，则用图3 1 6 11、，ij1l 一1111 j1j1jl 第2 章单个设备的能量优化：两个简单的算法 ( b ) 中的另一变换，即给如之后分配了一个减速区间这样的变换将导致一个更 好的调度，其中证明与之前的情况基本一致之后可以先处理，d 知】中的速度曲 线使它满足此引理( 仍然在呶中维持相同速度8 7 ( 如) ) ，然后处理【以，t ，】中的曲线， 以初始速度8 7 ( d k ) 开始并使其满足此引理 如此重复，可以保证最优解在中正好是一个任务的截止时间和完成时间，也 就是紧的截止时间 口 足理1 在最佳调度中， 1 ) 第一个时间块是使得密度圣塑d 趔t最大的区间( o ，d r ) ，其中 j t = j j l d jsd t ) $ l l t 1 ，n ，即最优调度的最高速度为s l ：m a x 墨掣 2 ) 假设时间块j 的速度是町且在任务以，的截止时间上完成，在时间块歹+ 1 中的速度为s 升。：n 峄竺兰竺二! ：生且墅! ! 掣= 生兰竺兰皇兰