功耗管理中的动态电压调整综述

第２４卷第８期　计算机应用研究　Ｖｏ１．２４　Ｎｏ．８　２００７年８月　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ａｕｇ，２００７　功耗管理中的动态电压调整综述术　王彪，王小鸽　（清华大学操作系统与中间件研究中心，北京１０００８４）　摘要：综述了十年来动态电压调整的相关文献，对各种策略进行分类介绍；对ＤＶＳ问题的数学模型进行提　炼，抽象出它们解决问题的思路，评价它们的优缺点，并简述典型策略的实现。　关键词：动态电压调整；电源管理；时间片；任务调度　中图分类号：ＴＰ３１６．２　文献标志码：Ａ　文章编号：１００１—３６９５（２００７）０８—０００８—０５　Ｓｕｒｖｅｙ　ｏｆ　ｄｙｎａｍｉｃ　ｖｏｌｔａｇｅ　ｓｃａｌｉｎｇ　ｉｎ　ｐｏｗｅｒ　ｍａｎａｇｅｍｅｎｔ　ＷＡＮＧ　Ｂｉａｏ，ＷＡＮＧ　Ｘｉａｏ　ｇｅ　（Ｏｐｅｒａｔｉｎｇ跏　＆Ｍｉｄｄｌｅｗａｒｅ　Ｒｅｓｅａｒｃｈ　Ｃｅｎｔｅｒ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓ　，Ｂｅｉｊｉｇｎ　１０００８４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｓｕｒｖｅｙｅｄ　ｒｅｌａｔｅｄ　ｄｏｃｕｍｅｎｔ　ｒｅｌｅａｓｅｄ　ｉｎ　ｒｅｃｅｎｔ　１０　ｙｅａｒｓ，ｓｏｒｔｅｄ　ａｎｄ　ｉｎｔｒｏｄｕｃｅｄ　ｖａｒｉｏｕｓ　ｐｏｌｉｃｉｅｓ，ｒｅｆｉｎｅｄ　ｔｈｅｉｒ　ｍａｔｈｅｍａｔｉｃ　ｍｏｄｅｌ　ｆｏｒ　ＤＶＳ　ｐｒｏｂｌｅｍ，ａｂｓｔｒａｃｔｅｄ　ｔｈｅｉｒ　ｓｏｌｕｔｉｏｎ’Ｓ　ｃｏｍｍｏｎ　ｔｈｏｕｇｈｔｓ，ｍａｄｅ　ｃｏｍｍｅｎｔｓ　ｏｎ　ｔｈｅｉｒ　ｓｔｒｏｎｇｐｏｉｎｔ　ａｎｄ　ｓｈｏｒｔｃｏｍｉｎｇ，ａｎｄ　ｂｒｉｅｆｌｙ　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅｉｒ　ｔｙｐｉｃａｌ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ｄｙｎａｍｉｃ　ｖｏｌｔａｇｅ　ｓｃａｌｉｎｇ（ＤＶＳ）；ｐｏｗｅｒ　ｍａｎａｇｅｍｅｎｔ；ｔｉｍｅ　ｉｎｔｅｒｖａｌ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　功耗问题日益成为人们关注的热点，这主要是基于如下两　下几个标准：ａ）节能水平。无疑这是最重要的标准。ｂ）对性　种原因：无线、移动终端设备越来越普遍，并且功能越来越强　能的影响水平。降低频率肯定对性能有影响，但要做到终端用　大，这些设备使用电池供电，而电池供电量的增长远远落后于　户感觉不到，关键应用不受影响。Ｃ）尽量做到无须应用程序　这些设备功耗的增长；发热问题越来越严重，已经开始制约性　参与。这是由绝大多数已存应用程序缺乏这方面考虑的现实　能的进一步增长…。人们由过去单纯追求性能的增长变为追　原因决定的。ｄ）尽量做到对操作系统的侵入最少。动态调频　求性能与功耗的平衡。　是一个底层机制，与硬件有莫大的关系，不可能不影响现有系　典型的ＣＭＯＳ工艺制造的芯片，其消耗的电流主要分为动　统，但可以做到少一些影响。　态电流（ｄｙｎａｍｉｃ　ｃｕｒｒｅｎｔ）与漏电流（１ｅａｋａｇｅ　ｃｕｒｒｅｎｔ）两个部分。　一般而言，动态电流占绝大多数。但随着制造工艺的进步，漏　１　各种ＤＶＳ策略介绍与分析　电流所占的比重越来越大。动态部分的功耗计算公式　为　Ｐｄ　。＝ＣＬ　Ｘ　Ｖｄｄｚ　Ｘ　Ｎ　ｘＡ其中：ＣＬ为负载电容；Ⅳ为网络活　ＤＶＳ策略关注的是ＣＰＵ在什么时间以什么速度运行负　跃晶体管数目，即所谓的活跃系数；Ｖｄｄ为工作电压；ｆ为频　载。早期的研究采用基于时间片的策略。Ｗｅｉｓｅｒ等人　最早　率。漏电流的计算比较复杂，但降低频率对它的影响更　提出把时间分为固定长度的时间片，在各个时间片把速度设置　大　］。　为保证大部分任务能在此时问片的末尾完成。稍后Ｃｈａｎ等　动态电压（频率）调整正是基于以上事实：功耗与频率和　人　改进了Ｗｅｉｓｅｒ的策略，把它分为两个部分，即预测与设　电压的平方成正比关系。这意味着，若能降低ＣＰＵ芯片的工　置。一个时间片开始时，预测部分预测这个时问片ＣＰＵ的工　作电压，则能显著地降低功耗。当然，工作电压降低，晶体管的　作量（忙碌程度，往往用ＣＰＵ使用率来表征，即此时间片内非　状态变换速度必然变慢，这要求降压的同时要降频。ＤＶＳ正　空闲时间的比率）；然后设置部分利用这些信息设置该时间片　是根据系统的运行负载，动态调整频率与电压，以达到既节省　的速度。但是其共同缺陷是要求知道未来的ＣＰＵ利用率，以　能量又不损伤性能的目的。　此得出最优的调度，所以只有理论上的意义。稍后Ｐｅｒｎｇ等　市场上出售的供移动设备使用的ＣＰＵ现在几乎均具备了　人　。。及Ｇｒｕｎｗａｌｄ等人　都指出了这个缺点，并提出了他们的　动态调整频率与电压的功能，如Ｉｎｔｅｌ的ＸＳｃａｌｅ、Ｔｒｎａｓｍｅｔａ的　预测模型与设置策略（１．１节将详细描述）。他们比较了自己　Ｃｒｕｓｏｅ、ＡＭＤ的Ａｔｈｌｏｎ。这为动态电压调整提供了物质基　的以及另外的一些策略，得出的结论是悲观的，认为不可能做　础　引。　到既节约能量又不损害性能。但这种思想还是应用在了　关于在何处实现ＤＶＳ至今仍是一个开放问题…，绝大多　Ｔｒｎａｓｍｅｔａ的ＬｏｎｇＲｕｎ技术上。它简单地间隔固定时间测量　数的ＤＶＳ实现基于操作系统。衡量一个ＤＶＳ策略的好坏有如　ＣＰＵ的利用率，然后根据利用率增加或减少ＣＰＵ的频率　。　收稿日期：２００６　０８—１１；修返日期：２００７　０６—１８　基金项目：国家“８６３”计划资助项目（２００３ＡＡ１Ｚ２０９０）；清华大学基础研究基金资助项目　（Ｊｃ２００３ｏ２１）　作者简介：王彪（１９８２一），男，湖南常德人（土家族），硕士研究生，主要研究方向为中间件技术、动态电源管理技术（ｗａｎｇｂｉａｏｌＭ＠ｍａｉｌｓ．ｔｓｉｎｇｈｕａ．　ｅｄｕ．ａｎ）；王小鸽（１９５７一），女，北京人，副教授，主要研究方向为高性能计算、操作系统、中问件．　维普资讯 http://www.cqvip.com

第８期　王彪，等：功耗管理中的动态电压调整综述　。９・　Ｐｅｒｉｎｇ等人及Ｇｒｕｎｗａｌｄ等人在比较上述策略时提出了时　限的想法，认为若一个任务的时限能得到满足，那么运行快慢　无关紧要，从而引出了基于任务的ＤＶＳ策略。它的关键在于　怎样获取各个任务的时限与周期需求，从而求得各个任务运行　中的最佳频率设置。Ｆｌａｕｔｎｅｒ等人　、Ｌｏｒｃｈ等人　和　Ｃｈａｎ等人在工作站上的模拟结果表明，ｐｅａｋ算法是比较　好的一个，并认为复杂的预测策略不可取，而试着平滑速度改　变的简单策略则在总体上占优。同时从结果可以看出，上述种　种算法实质上都表现不佳，因为与没有调度（ｆｌａｔ）比，大部分算　法反而有下降。Ｇｒｕｎｗａｌｄ等人认为这是由于没考虑到任务的　Ｙｕａｎ等人　分别在解决这些问题时提出了自己的策略。其　主要不同是任务分类与动态的周期需求探测所用的方法不同。　除了上述分类方法，还可以将这些策略分类为通用系统上　与实时系统上的策略。本文关注的主要是通用系统策略与软　实时策略，主要原因在于硬实时策略往往需要应用告知系统其　差异性而造成的，且基于时间片的调度算法不可能做到既节能　又不损害性能。　１．２基于任务的策略　由于Ｐｅｒｉｎｇ和Ｇｒｕｎｗａｌｄ等人的研究结论，研究者开始转　向基于任务的策略，主要考虑任务所需要的ＣＰＵ时间（周期需　明确的最坏执行时间与周期需求，而大部分手持设备应用也不　需要硬实时。　１．１　基于时间片的策略　求）与任务必须完成的时限。因为只要满足时限要求，则可以　认为性能要求得到满足，而任务并不是每时每刻都需要峰值速　度，这是调整电压与频率的前提。　１．２．１　问题的形式化描述　Ｆｌａｔ策略与ｃｏｐｔ策略作为两种参考策略出现。前者把　ＣＰＵ的频率限定在某个常数水平，即没有电压与频率的改变。　后者只有理论上的意义，因为它假设知道将来的性能要求，从　ＤＶＳ问题可以抽象为：在一个有有限个频率与电压级别　的ＣＰＵ上，设为｛　，　）Ｉ　≤ｍ｝，并设调整频率的时间忽略不　计，即从一个频率水平调整到另一个频率水平所需时间忽略不　计，运行着ｎ个有着不同时限的任务，设这些时限为常数，记为　｛Ｔｉ，　≤ｎ｝，并假设各个任务的周期需求已知，设这个需求分　布为　（Ｗ），表示所需周期数不超过Ｗ的概率；根据功耗Ｐ与　而可以作出最优调度；具体做法一般是测量实际数据，然后计　算出在这种情况下的最优能耗　。　Ｐａｓｔ＿８　是第一个比较实际的策略，其预测部分只分析前１　个时间片的ＣＰＵ使用率。根据某种预设的阈值，若超过则设　置部分开始提速；若低于则减速。它基于利用率连续的假设，　简单地用前１个时间片的利用率预测当前利用率。在实现时　作了优化，主要是考虑时间片长度、各个时间片里溢出的情况　ｃｆ成正比的基本关系，问怎样设置各个任务运行中的频率值，　才能以最高的概率满足时限要求同时消耗最小的能量。　用数学语言表示如下（其中　为经过Ｗ个周期后的频率；　Ｃ　．（即没有完成的周期数）等。这种简单的预测模式在运行周期　变化比较平稳的系统负载时较为理想，所以根据一批基准测试　得出的结果还是不错的。　Ｃｈａｎ等人　９　随即试着在实际系统中实现这些策略，发现　效果不理想，并提出了如下几个新的策略：　ｆｗ）≤　。　Ｃ　为时限）：ｍｉｎｉｍｉｚｅ∑［Ｉ—Ｆｉ（Ｗ）］　；ｓｕｂｊｅｃｔ　ｔｏ　∑ｌ（Ｉ／　对上面模型的各个假设或参数略为调整，便可以得出以下　各个策略：如若令任务数目为Ｉ，则是ｐａｃｅ策略；若取消任务时　限为常数的假设，则是ｖｅｔｒｉｇｏ策略；若任务种类在多媒体　应用，则是ｇｒａｃｅ—ＯＳ策略等。　ａ）ＡＶＧ计算以前时间片中利用率的指数移动平均值。具　体而言是在每个时间片用上个时间片的利用率与以前的平均　利用率的平均作为当前时间片调度的依据；在计算时使用一个　权值ｗｅｉｇｈｔ，方法为（ｗｅｉｇｈｔ×ｏｌｄ＋ｎｅｗ）／（ｗｅｉｇｈｔ＋１）。　ｂ）Ｌｏｎｇ—ｓｈｏｒｔ试图找到短期行为与长期行为的结合点。　它维护两个利用率，即前面３个时间片的平均利用率和前面　１２个时间片的平均利用率；然后以两者的加权平均为基础设　置当前时间片的频率。Ａｇｅｄ—ａｖｅｒａｇｅ是ｌｏｎｇ—ｓｈｏｒｔ策略的一种　改进，基本想法是越往前的时间片所占的权重越低。　Ｃ）Ｃｙｃｌｅ是ｆｌａｔ策略的一种改进，它检查最后１６个时间片　的利用率，看是否存在某种周期性，当然这个周期性只要大致　精确即可。如果存在这种周期性，则在当前时间片延续这种周　上面模型假设了任务的周期需求分布已知，但在实际系统　中，这个需求是未知的，采用何种探测方法来尽可能精确的求　得这个需求分布是各个算法（策略）的主要区别。　１．２．２　Ｐａｃｅ系列策略　Ｐａｃｅ策略是一种调整算法，它本身不能作为一种的　策略，而是改进已存策略。它基于两个事实：若两个ＤＶＳ策略　在ｐａｃｅ调整后都能在时限前完成，则两个算法的性能相同；在　保证时限的前提下，任务执行采用不同的频率可以节约能量。　该算法的关键是在不改变已有算法的时限前完成周期数，也不　改变时限后剩余周期数，而仅仅改变在两个阶段中的频率。　Ｐａｃｅ策略假设了速率连续可调，即把速度假设为时间（或　者已完成周期数，称为工作）的连续函数（本文给出的模型已　期性；否则用常数的频率设置。Ｐａｔｔｅｎ是ｃｒｙｃｌｅ的一种泛化，它　把利用率分成四个等级，即０～０．２５、０．２５～０．５、０．５～０．７５、　０．７５～１．０；然后寻找与最后模式串相同的模式，并用以前的模　式来预测当前时间片的利用率并设置频率（实质是把ｃｙｃｌｅ的　经去除了这个不合理的假设）。但是速率不可能连续可调，所　以通过一个任务执行周期内分阶段设置速率以达到次优化的　目标，这涉及到两个问题：　条件降低，使得在ｃｙｃｌｅ中不算周期的利用率序列也能算上）。　ｄ）Ｐｅａｋ是一种考虑窄的峰值性能需求的策略，它采用某　些启发式算法。例如，若利用率正在下降，则认为它会继续下　降；若利用率已经很高，则预测它会经过其峰值然后下降一点；　ａ）如何选择转折点，即各个阶段如何划分。在上述模型　的基础上，用如下公式来选择：　ｑｉ＝１一ｃ～．１≤ｉ≤３　ｇ　＝Ｑ＋（　一．，）　。・。。　一０　一　，　＞Ｊ　若利用率很低且变化平坦，则预测它会保持低而平坦等等。　维普资讯 http://www.cqvip.com

・ｌ０・　计算机应用研究　２００７．雏　其中：Ⅳ是转折点数目；‘，是一个预设的接近Ⅳ的数；Ｑ是接近　感观。在每个事件期执行完成后，计算其全速运行的总时间，　０．９５的数；ｇ　即是转折点。这样选取的目的是为了速度变化　更平稳。　用指数递减平均值的方法求得下个事件期的预测运行时间。　若下个事件期的执行时间超过可忽略时限，则用计算出的预测　时间与感观时限的比来设置性能因子。　ｂ）速率如何设置。首先用几种传统的基于时间片算法中　常用的策略（ＡＧＥＤ、ｌｏｎｇ＿ｓｈｏｒｔ等）来处理采样任务所需的周期　数，这一般是一个周期数的带权和；然后根据这些样本来确定　一中间层的策略是用应用程序指定的方法来得到时限与性　能需求（这在实时系统中普遍采用，这是操作系统设计的趋　势。应用程序参与的电源管理会更直接而有效）。但本文只是　用于调试目的，因为目前所有应用（通用系统或ＰＤＡ应用）几　乎都不考虑功耗要求。　最底层的策略是采用任务级的时间片算法。这里与传统　个任务的需求分布。在确定这些分布时试验了Ｇａｍｍａ分　布、正态分布等常用方法（即假设这个任务的需求分布属于这　些分布，然后用样本值估算确定一个分布的具体参数，如正态　分布的期望与方差，从而确定一个具体分布）。　根据这个分布，可得出分布函数Ｆ（埘），表示所需周期数　不超过埘的概率。根据上述模型的求解，证明以Ｆ　（埘）　／　时间片算法的主要区别是粒度不同，不是全局地用一个系统的　ＣＰＵ利用率，而是在任务级采用。这样的预测往往精确得多。　因为就任务而言，其周期性显然强过一个通用的系统。其次就　是直接采用预测时间来设置速率，而不是像传统时间片算法那　样把一个策略分为两部分，典型的设置策略是在以前的频率水　ｓ（埘）＝Ｃ可以得出最优解，从而设置５（幻）＝　（ｓ）　×Ｃ。　其中：Ｆ　（埘）为各个阶段的Ｆ　（埘）的平均值，Ｆ。（埘）＝１一　Ｆ（埘）；ｓ（幻）为经过埘个周期后，ＣＰＵ的频率值。所以只要给出　了阶段与分布，就可以给出调度。这就是ｐａｃｅ算法的关键所　在。　平上加或减去一个人为的值。这个人为的值也影响了传统时　间片算法的精确性。　完整的基于ｐａｃｅ的ＤＶＳ策略是稍后提出的ｆｉｇｈｔｓｐｅｅｄ策　略，并在基于Ｔｒａｎｓｍｅｔａ　Ｃｒｕｓｏｅ　ＣＰＵ和ＡＭＤ　ＣＰＵ的Ｗｉｎｄｏｗｓ　具体而言，一个任务从开始执行到其主动让出ＣＰＵ，包括　中间被其他任务抢先，被认为是一个任务周期；把其中完整的　ＣＰＵ时间加起来，形成本周期的任务执行时间（Ｗｏｒｋ　），用指　２０００机器上实现了该策略。笔者主要考虑交互式任务，用上　述启发式算法确定各个不同类型的ＵＩ事件（如击键、鼠标移　动、鼠标击键等）的开始与结束，从而得出其性能要求分布与　时限要求。笔者用改进的ｐａｃｅ算法求得最优调度。改进主要　指根据离散而不是连续的可调度频率范围、功耗与频率的非线　性关系等因素得出。　１．２．３　Ｖｅｒｔｉｇｏ策略　数递减平均值作为新的预测执行时间，用同样的办法算出新的　时限ＷｏｒｋＥｓｔ　。　＝（ｋ×ＷｏｒｋＥｓｔｄｄ＋Ｗｏｒｋｆ￣）／（　＋１）、　Ｄｅａｄｌｉｎｅ～＝（后×Ｄｅａｄｌｉｎｅｏｌｄ＋Ｉｄｌｅ）／（ｋ＋１）；然后直接得出性　能因子Ｐｅｒｆ＝ＷｏｒｋＥｓｔ／Ｄｅａｄｌｉｎｅ。　上述三种策略形成了一个策略层次机构，成为一个策略　栈。它们对各种不同的事件作出反应，然后作出自已的决策。　一Ｆｌａｕｔｎｅｒ等人“　提出把任务分类，并修改０ｓ内核来自动　获取任务所需的ＣＰＵ时间与时限。其核心思想即是通过在线　（运行时）的监控来获取任务信息，通过动态调整来适应任务　性能要求的变化。他们把任务分为交互性任务与周期性任务，　个全局决策机构得出最优的决策，一般是最顶层的策略优　先。因为认为性能是要优先保证的，而顶层的策略保证了用户　的观感不会有损害。　将ｖｅｒｉｔｇｏ算法与ＣＰＵ本身的ＤＶＳ策略（ＬｏｎｇＲｕｎ）作比较　后得出的结论是，在大部分情况下ＬｏｎｇＲｕｎ显得过于保守，它　总是很快地将ＣＰＵ的速度调节到最高或较高的频率，在低频　率水平停留的时间很短。笔者认为这是基于系统利用率的原　因。因为不知道具体任务的性能需求，所以只能采取保守策　略。Ｖｅｒｔｉｇｏ则使大部分任务在较低频解决，只有在超过恐慌　时限时才设置到全速运行，能有效地节约能量。又由于顶层的　策略保证了用户的感觉不会受到什么损害，如在播放ＭＰＥＧ　时并没有丢帧。　１．２．４　ＧＲＡＣＥ－ＯＳ策略　又把周期性任务分为生产者任务与消费者任务。在交互性任　务中，计算出全速运行所需的时间和一个感观阈值（也就是一　般用户能接受的反应时间。根据一般的用户行为研究给出为　５０—１００　ＩｌｌＳ）；两者的比即是性能因子（设置的频率为最高频率　乘以性能因子）。这是事后计算，为的是预测下一个时间到来　时的性能因子。至于周期性任务，则简单地把速度减慢到在下　一个周期开始或与之对应的消费者任务开始时执行完。值得　注意的是，若同时有周期性任务与交互性任务，则在一个交互　性任务开始时，若其预测的性能因子高于周期性任务的性能因　子，取较高的值。　Ｖｅｒｔｉｇｏ把策略分为三个级别。最顶上的策略用上述的交　Ｗａｎｇｈｏｎｇ　Ｙｕａｎ等人¨　提出ｇｒａｃｅ—ＯＳ策略，把软实时调度　算法与ＤＶＳ策略整合在一起，为手持终端的多媒体应用提出　节能又保证服务质量的ＯＳ调度策略。　互式算法来选择预测值。具体做法是监控某个事件，以作为一　个时间处理期的开始，然后看看此事件所激发的任务与哪些任　务联系；当所有与这个事件的有关处理工作都完成后，认为这　个事件期完成。设置两个时限，一个是可忽略时限，一般设为　５　ＩｌｌＳ；这是指那些典型的小型事件（如输入时击键、普通的鼠标　该算法是基于ＰＡＣＥ算法的改进，但在以下几个方面作了　改进：ａ）去掉了频率连续可调的假设，代之以离散的频率范　围；ｂ）在线估测ＣＰＵ周期需求时不是按某种已知分布，而是用　统计分布图来大致地求得分布函数，即把从最小的周期数到最　大的周期数分成等分的区间，然后统计一定范围（最近／＂ｔ次同　一移动等），低于这个时间完成的事件均认为可以用最低的ＣＰＵ　速度来执行，从而不需要进入加速期。再设置一个感观时限，　一任务的周期需求，如１００）内落入各个区间的数目，则可以得　般定为５０　ＩｌｌＳ；若超过这个时限，则全速运行，以不损伤用户　出一个从小到大按序的分布图；ｃ）引入了最早时限优先算法　维普资讯 http://www.cqvip.com

第８期　王彪，等：功耗管理中的动态电压调整综述　’１１・　（ＥＤＦ），在统计上保证不超过时限的概率（即在分布图中选择　一Ｖｅｒｔｉｇｏ则是在内核级实现。因为它实现在Ｌｉｎｕｘ操作系　个合适的周期数目，低于这个周期数目的概率要超过一个预　统上，包括策略栈、事件追踪模块、速度控制器等。策略栈产生　具体策略；事件追踪模块负责获取任务的ＣＰＵ需求分布；速度　先定义的阈值）。　由于只关心多媒体应用，没有采用前两个策略的复杂任务　周期需求采样方法，而是直接修改操作系统内核的进程控制　块，加入周期计数器，用以监控每个任务在被调度选中和调出　过程中所消耗的周期数。执行完毕后求和，以求得它该落人哪　个区间，使该区间的频度增加。设划分的区间范围为ｂ。＜６　＜　ｂ：＜ｂ　＜…＜ｂ　，则落人各个区间的值　与ｎ的比值即为任务　的ＣＰＵ需求在此区间的概率。所以ＣＰＵ需求小于某个值，如　ｂ　的概率为Ｆ（ｂ　）：Ｐ［　≤６　］≥ｕ（其中ｕ是一个特定任务统　计意义上的性能需求，即该任务需要以ｕ％的概率满足时限要　求）。若给某个任务分配的周期为ｂ．，则其在时限内完成的概　率是可知的，据此可以保证实时性。使用的ＥＤＦ调度就利用　了这点。　ＤＶＳ策略关心采用何种频率完成分配给任务的周期。与　ｐａｃｅ算法一样，ｇｒａｃｅ．ｏｓ策略求解上述数学模型得出的解是　ｍ，．　．，．．　．．．．．．．　。．．．．．．－．．．．．．．．．一　一　＝　￣／　ｊ＿［１一Ｆ（６川／｛Ｔ　［１一Ｆ（ｂｉ）］｝，Ｖｉ。　对每一个任务完成点，可由设置的频率得出，在安排一个　任务时，其最佳调度便可应用。结果显示，在低负载的系统环　境下，只有极少任务不能满足性能需求，在高负载的环境下，大　部分任务（９０％以上）能满足性能要求；同时支持多任务环境，　这对于ｐａｃｅ也是一个改进。　１，３其他类型的策略　为了保证实时性提出的各种策略，本文不加以关注。这主　要基于如下两点原因：ａ）各种实时性策略往往需要应用程序　提供额外的信息，如最坏执行时间、周期需求。在普通的ＰＤＡ　或通用系统上不可能要求应用程序员提供这样的信息，大部分　任务交互式的特性也决定了不可能提供类似的信息。ｂ）在普　通的ＰＤＡ或通用系统上不需要保证硬实时，大部分是尽力而　为型，少部分为软实时型，如多媒体应用。　２实现简介　ＲｉｇｈｔＳｐｅｅｄ的实现包括一个底层的速度控制器，负责具体　执行频率设置；一个时钟，负责提供１　ｍｓ级别的调度粒度；一　个任务组文件管理器，因为各个任务都有其相关的信息需要记　录，如其时限、性能要求、以前采样的运行时间，以及下一个任　务周期该采用的调度（即在一个任务周期的各个时段采用的　频率水平和各个时段长度）；一个任务管理器和采样队列，在　任务启动或结束时通知速度控制器，并在任务结束时把采样信　息存人采样队列，以便在系统比较空闲时用ｐａｃｅ算法计算任　务的预测调度；一个空闲监测器，它是一个仅比系统空闲线程　优先级高的线程，负责识别任务的结束和计算最优调度值；一　个Ｉ／Ｏ计数器，主要帮助空闲监测器识别任务结束（参见前述　两个条件）；一个用户库，主要检测用户的ｕＩ事件。　ＲｉｇｈｔＳｐｅｅｄ的实现特点是基于系统线程，而不是更改操作　系统调度程序。这一优点使它可以在某些封闭源码的商业操　作系统上实现。　控制器负责具体的频率（电压）调整。Ｖｅｒｔｉｇｏ的实现特点是其　策略栈可以综合所有的策略，得出对各种类型的任务都较佳的　调度。　Ｇｒａｃｅ．ＯＳ在内核级实现，实现在Ｌｉｎｕｘ上，包括探测器、软　实时调度器、速度适配器。探测器负责收集监控任务的ＣＰＵ　周期；软实时调度负责调度及产生策略；速度适配器负责具体　的频率（电压）调整。　以上几种实现的一般架构是：底层的驱动程序负责与具体　的ＣＰＵ　ＤＶＳ芯片交互，实现频率调整，向上提供接口。更换　ＣＰＵ时，可以保证只有这部分代码需要重写；策略管理器负责　执行具体的ＤＶＳ策略，其实现要求是可以动态调换不同的　ＤＶＳ策略，可以更新ＤＶＳ策略；探测器可以追踪任务或系统的　运行情况，得出ＣＰＵ的负载；核心负责向上提供应用编程接口　（ＡＰＩ），向其他组件提供服务例程，并协调各个组件的工作。　３相关工作与后续工作　关于ＤＶＳ策略的综述不是很多。Ｃｈａｎ等人比较了早期的　各个基于时间片的ＤＶＳ策略。他们用模拟验证了早期Ｗｅｉｓｅｒ　等人提出的一些想法，并提出了自己的策略。Ｐｅｒｉｎｇ等人比较　了另外一些策略，并在实际系统中实现了几个算法，得出了被　引频次极高的结论。Ｇｒｕｎｗａｌｄ等人的研究与Ｐｅｒｉｎｇ等人的研　究共同催生出基于任务的ＤＶＳ策略。但以上文献均只是总结　与比较了早期基于时间片的ＤＶＳ策略。本文总结了十年以来　有关ＤＶＳ策略的相关文献，对其进行分门别类，比较系统地介　绍了ＤＶＳ策略从算法到实现的方方面面。　今后，笔者将在德信的一款基于ＸＳｃａｌｅ的智能手机上具　体实现上述种种算法，并在实际工作中进一步检验上述策略，　尽可能提出自己的策略。　４结束语　功耗的重要性已经提升到与性能和成本同等重要的地位。　从小处着眼，它可以延长电池使用的寿命，降低芯片散发的热　量；从大处着眼，它可以降低对能源的消耗，减少对环境的影　响，是一个值得关注与重视的问题。　ＤＶＳ是降低功耗的有效途径，经过近十年的发展，很多算　法与策略已经得到工业级别的应用，但空间还很大。作为进一　步的研究，笔者给出如下建议：　ａ）探求更清晰的任务周期需求预测与监控方法。这是得　到最优调度的必要条件。现在的基于用户界面事件和任务分　类方法比较宽泛，不够精确，分类的标准也没有统一。　ｂ）对数学模型进行进一步研究，尽量去掉不合理的假设，　如考虑调整时间。实际上，在Ｉｎｔｅｌ基于ＸＳｃａｌｅ微架构的　ＰＸＡ２７ｘ应用处理机上，调整一次频率的代价大概在１０２　ｔｘｓ级　别，这在时间要求较高的应用中是不能忽略的。又比如考虑各　个任务的交互等。　Ｃ）实现架构的研究，可以提出ＤＶＳ策略的通用体系结构。　维普资讯 http://www.cqvip.com

・１２・　计算机应用研究　２００７正　本文给出的结构可以作为一种参考，但各个接口函数、各个部　分间的交互没有标准化。同时ＤＶＳ策略暴露给应用程序员的　接口没有标准化，但这是一种趋势，即允许应用程序员与用户　参与到功耗管理中，应用参与的功耗管理将更直接而有效。　直　Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　Ｎｅｗ　Ｙｏｒｋ：Ｔｈｅ　Ａｄｖａｎｃｅｄ　Ｃｏｍｐｕｔｉｎｓ　Ｓｙｓ—　ｔｅｒｎｓ　Ａｓｓｏｃｉａｔｉｏｎ，１９９４：１３—２３．　［９］Ｇ０ＶＩＬ　Ｋ，ＣＨＡＮ　Ｅ，ＷＡＳＳＥＲＭＡＮ　Ｈ．Ｃｏｍｐａｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｄｙｎａｍｉｃ　ｓｐｅｅｄ—ｓｅｔｔｉｎｇ　ｏｆ　ａ　ｌｏｗ—ｐｏｗｅｒ　ＣＰＵ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　１　ｓｔ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９５．　接告知比迂回的探测肯定更有效，因为应用程序员与用户最清　楚它的性能需求与时限要求。　ｄ）在实际系统中试验与创造ＤＶＳ策略。本文所述的很多　［１０］ＰＥＲＩＮＧ　Ｔ，ＢＵＲＤ　Ｔ，ＢＲＯＤＥＲＳＥＮ　Ｒ　Ｗ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ａｎｄ　ｅｖａ１．　ｕａｔｉｏｎ　ｏｆ　ｄｙｎａｍｉｃ　ｖｏｌｔｇｅ　ｓｅａｌａｉｎｇ　ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｐｍｅ　ｏｆ　ｔｈｅ　１９９８　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｌｏｗ　Ｐｏｗｅｒ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｄｅｓｉｎ．ｇ　Ｍｏｎｔｅｒｅｙ，ＣＡ：ＡＣＭ，１９９８：７６—８１．　策略都是用模拟来验证的，不能提供让人确信的结论。实际的　系统有很多细节可以抵消可能的节能措施，在模拟器上验证，　靠一两组挑选的基准测试往往容易得出过于乐观的结论。　参考文献：　［１］ＬＯＲＣＨ　Ｊ　Ｒ．Ｏｐｅｒａｔｉｎｇ　ｓｙｓｔｅｍｓ　ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｒｅｄｕｃｉｎｇ　ｐｒｏｃｅｓｓｏｒ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｐｔｉｏｎ［Ｄ］．Ｃａｌｉｏｍｉｆａ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ　ａｔ　Ｂｅｒ．　ｋｅｌｅｙ，２００１．　［１１］ＧＲＵＮＷＡＬＤ　Ｄ，ＬＥＶＩＳ　Ｐ，ＦＡＲＫＡＳ　ＫＩ，ｅｔ　ａ１．Ｐｏｌｉｃｉｅｓｆｏｒｄｙｎａｍｉｃ　ｃｌｏｃｋ　ｓｃｈｅｄｕｌｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　４ｔｈ　Ｓｙｍｐｏ￣ｕｍ　ｏｎ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓ－　ｔｅｍｓ　Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｓａｎ　Ｄｉｅｇｏ：［ｓ．ｎ．］，２０００．　［１２］ＦＬＡＵＴＮＥＲ　Ｋ，ＲＥＩＮＨＡＲＤＴ　Ｓ，ＭＵＤＧＥ　Ｔ．Ａｕｔｏｍａｔｉｃ　ｐｅｒｆｏｒｍａ—　ｎｅｅ—ｓｅｔｉｔｎｇ　ｆｏｒ　ｄｙｅ，ａｌｅ　ｖｏｌｔｇｅ　ｓｃａａｌｉｎｇ［Ｃ］／／Ｐｒｃ　ｏｆ　ｔｏｈｅ　７ｔｈ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ（ＭＯ—　ＢＩＣＯＭ　２００１）．２００１．　［２］ＳＯＵＤＲＩＳ　Ｄ．Ｄｅｓｉｇｎｉｎｇ　ＣＭＯＳ　ｃｉｒｃｕｉｔｓ　ｆｏｒ　ｌｏｗ　ｐｏｗｅｒ［Ｍ］．Ｎｅｔｈｅｒ．　１ａｎｄｓ：Ｋｌｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ，２００２：９—２２．　［３］ＪＥＪＵＲＩＫＡＲ　Ｒ，ＰＥＲＥＩＲＡ　Ｃ，ＧＵＰＴＡ　Ｒ．Ｌｅａｋａｇｅ　ａｗａＦ￣ｄｙｎａｍｉｃ　ｖｏｌｔａｇｅ　ｓｃａｌｉｎｇ　ｆｏｒ　ｒｅａｌ－ｔｉｍｅ　ｅｍｂｅｄｄｅｄ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　４１ｓｔ　ＤＡＣ’０４．Ｓａｎ　Ｄｉｅｇｏ：［ｓ．ｎ．］，２００４．　［４］Ｉｎｔｅｌ公司．Ｉｎｔｅｌ＠ＰＸＡ２７ｘ　ｐｒｏｃｅｓｓｏｒ　ｆａｍｉｌｙ　ｄｅｖｅｌｏｐｅｒ　ｓ　ｍａｎｕａｌ　［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｉｎｔｅ１．ｅｏｍ／ｄｅｓｉｇｎ／ｐｅａ／ｐｒｏｄｕｃｔｓ／ｐｘａ２７ｘ／　ｔｅｃｈｄｏｃｓ．ｈｔｍ．　［１３］ＬＯＲＣＨ　Ｊ　Ｒ，ＳＭＩＴＨ　Ａ　Ｊ．Ｔｈｅ　ＶＴｒａｃｅ　ｔｏｏｌ：ｂｕｉｌｄｉｎｇ　ａ　ｓｙｓｔｅｍ　ｔｒａｃｅｒ　ｏｆｒ　Ｗｉｎｄｏｗｓ　ＮＴ　ａｎｄ　Ｗｉｎｄｏｗｓ　２０００［Ｊ］．ＭＳＤＮ　Ｍａｇａｚｉｎｅ，２０００，　１５（１０）：８６—１０２．　［１４］ＬＯＲＣＨ　Ｊ　Ｒ，ＳＭＩＴＨ　Ａ　Ｊ．Ｉｍｐｒｏｖｉｎｇ　ｄｙｎａｍｉｃ　ｖｏｌｔｇｅ　ｓｅａｌａｉｎｇ　ａｌｇｏ—　ｉｒｈｍｓ　ｗｉｔｈ　ｐａｃｅ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２００１ｔ　ＡＣＭ　ＳＩＧＭＥＴＲＩＣＳ　Ｃｏｎｆｅ—　ｅｎｅｅ．Ｃａｍｂｒｒｉｄｇｅ：［ｓ．ｎ．］，２００１：５０—６１．　［１５］ＬＯＲＣＨ　Ｊ　Ｒ，ＳＭＩＴＨ　Ａ　Ｊ．Ｕｓｉｎｇ　ｕｓｅｒ　ｉｎｔｅｒｆａｃｅ　ｅｖｅｎｔ　ｉｆｏｒｎｍａｔｉｏｎ　ｉｎ　ｄｙｎａｍｉｃ　ｖｏｌｔｇｅ　ｓｃａａｌｉｎｇ　ａｌｇｏｒｉｔｈｍｓ［Ｒ］．Ｃａｌｉｆｏｒｎｉａ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ　ａｔ　Ｂｅｒｋｅｌｅｙ，２００２．　［５］ＡＭＤ‘公司．Ｍｏｂｉｌｅ　ＡＭＤ　Ａｔｈｌｏｎ　４　ｐｒｏｃｅｓｓｏｒ　ｍｏｄｅｌ　６　ＣＰＧＡ　ｄａｔａ　ｓｈｅｅｔ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ａｍｄ．ｃｏｒｎ．　［６］ＫＬＡＩＢＥＲ　Ａ．Ｔｈｅ　ｔｅｃｈｎｏｌｏｇｙ　ｂｅｈｉｎｄ　ＣｒｕｓｏｅＴＭ　ｐｒｏｃｅｓｓｏｒｓ［Ｒ］．［Ｓ．　１．］：Ｔｒａｎｓｍｅｔａ　Ｃｏｒｐｏｒａｔｉｏｎ，２０００．　［７］ＦＬＡＵＴＮＥＲ　Ｋ，ＭＵＤＧＥ　Ｔ．Ｖｅｒｔｉｇｏ：ａｕｔｏｍａｔｉｃ　ｐｅｒｆｏｒｍａｎｃｅ—ｓｅｔｉｔｎｇ　ｏｒｆ　Ｌｉｎｕｘ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　５ｔｈ　ＵＳＥＮＩＸ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ　Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（ＯＳＤＩ）．Ｂｏｓｔｏｎ：［ｓ．ｎ．］，　２００２：１０５一ｌｌ６．　［１６］ＬＯＲＣＨ　Ｊ　Ｒ，ＳＭＩＴＨ　Ａ　Ｊ．Ｏｐｅｒａｔｉｎｇ　ｓｙｓｔｅｍ　ｍｏｄｉｉｆｃａｔｉｏｎｓ　ｆｏｒ　ｔａｓｋ．　ｂａｓｅｄ　ｓｐｅｅｄ　ｎｄ　ａｖｏｌｔｇａｅ　ｓｃｈｅｄｕｌｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆｔｈｅ　１ｓｔ　Ｉｎｆｌ　Ｃｏｆｏｎｎ　Ｍｏｂｉｌｅ　Ｓｙｓｔｅｍｓ，Ａｐｐｌｉｃａｔｉｏｎｓ，ａｎｄ　Ｓｅｒｖｉｃｅｓ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：［ｓ．ｎ．］，　２００３．　［１７］ＹＵＡＮ　Ｗａｎｇ—ｈｏｎｇ，ＮＡＨＲＳＴＥＤＴ　Ｋ．Ｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔ　ｓｏｆｔ　ｒｅａｌ—ｔｉｍｅ　ＣＰＵ　ｓｃｈｅｄｕｌｉｎｇ　ｏｆｒ　ｍｏｂｉｌｅ　ｍｕｌｔｉｍｅｄｉａ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｍｃ　ｏｆ　ｔｈｅ　１９ｔｈ　ＳＯＳＰ’０３．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ．２００３．　［８］ＷＥＩＳＥＲ　Ｍ，ＷＥＬＣＨ　Ｂ，ＤＥＭＥＲＳ　Ａ，ｅｔ　ａ１．Ｓｃｈｅｄｕｌｉｎｇ　ｏｒ　ｆｒｅｄｕｃｅｄ　ＣＰＵ　ｅｎｅｒｇｙ［Ｃ］／／Ｐｒｏｅ　ｏｆ　ｔｈｅ　１ｓｔ　Ｓｙｍｐ￣ｉｕｍ　ｏｎ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ　（上接第７页）　．　ｓｙｓｔｅｍ　ｆｏｒ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩｎｔｅｍａｔｉｏｎａＩ　ＪｏｕｍａＩ　ｏｆ　Ｎｅｔｗｏｒｋ　Ｍａｎａｇｅｍｅｎｔ，２００５，１５（４）：２２３－２３４．　［５］ＴＯＬＬＥ　Ｇ，ＰＯＬＡＳＴＲＥ　Ｊ，ＳＺＥＷＣＺＹＫ　Ｒ，ｅｔ　ａ１．Ｄｅｓｉｎ　ｏｆｇ　ａｎ　ａｐｐｌｉ－　ｃａｔｉｏｎ－ｃｏｏｐｅｒａｔｉｖｅ　ｍａｎａｇｅｍｅｎｔ　ｓｙｓｔｅｍ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２ｎｄ　Ｅｕｒｏｐｅａｎ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｗｉｅｌｒｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔ．　ｗｏｒｋｓ．１ｓｔａｎｂｕｌ，Ｔｕｒｋｅｙｅ：［ｓ．ｎ．］，２００５：１２１—１３２．　［６］ＢＯＵＬＩＳ　Ａ，ＪＨＡ　Ｓ．Ｎｅｔｗｏｒｋ　ｍａｎａｇｅｍｅｎｔ　ｉｎ　ｎｅｗ　ｒｅｌｍｓ：ｗｉａｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｅｔｗｏｒｋ　Ｍａｎａｇｅ—　ｍｅｎｔ，２００５，１５（４）：２１９－２２１．　［１１］ＺＨＡＯ　Ｊ，ＧＯＵＩＮＤＡＮ　Ｒ，ＥＳＴＲＩＮ　Ｄ．Ｃｏｍｐｕｔｉｎｇ　ａｇｇｒｅｇａｔｅｓ　ｏｒｆ　ｍｏｎｉ—　ｔｏｒｉｎｇ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［ｃ］／／Ｐ￣ｏｆ　ｔｈｅ｜ｓｔ　ＩＥＥＥ　ｌｎｔｅｒｎａｔｒｏ－　ｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋ　Ｐｒｏｔｏｃｏｌｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｐｉｓｃａｔａ—　ｗａｙ：ＩＥＥＥ　Ｐｒｅｓｓ，２００３：１３９—１４８．　［１２］ＨＩＬＬ　Ｊ，Ｓ￣ＷＣＡＹＫ　Ｒ，ＷＯＯ　Ａ，ｅｔ　ａ１．Ｓｙｓｔｅｍ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｄｉｒｅｃｔｉｏｎｓ　ｆｏｒ　ｎｅｗｏｒｋｅｄｓｔｅｎｓｏｒｓｆＣ１／／ＰｒｏｃｏｆＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ　ｏｎＡｒｃｈｉ—　ｔｅｃｔｕｒａｌ　Ｓｕｐｐｏｒｔ　ｆｏｒ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇｕａｇｅｓ　ａｎｄ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ．　Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２０００：９３．１０４．　［７］ＺＨＡＯ　Ｙ　Ｊ，ＧＯＶＩＮＤＡＮ　Ｒ，ＥＳＴＲＩＮ　Ｄ．Ｒｅｓｉｄｕａｌ　ｅｎｅｒｇｙ眦ｎ　ｆｏｒ　ｍｏｎｉｔｏｒｉｎｇ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　Ｗｉｅｌｒｅｓｓ　Ｃｏｍｍｕｎｉｃａ—　ｔｉｏｎｓ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ　Ｃｏｎｆｅｒｅｎｃｅ．Ｏｒｌａｎｄｏ，ＵＳＡ：［ｓ．ｎ．］，２００２：３５６．　３６２．　［１３］ＬＥＶＩＳ　Ｐ，ＰＡＴＥＬ　Ｎ，ＣＵＬＬＥＲ　Ｄ，ｅｔ　ａ１．Ｔｒｉｃｋｌｅ：ａ　ｓｅｌｆ－ｒｅｇｕｌａｔｉｎｇ　ａｌ—　ｇｏｒｉｈｍｆｏｒ　ｔｃｏｄｅ　ｍａｉｎｔｅｎａｎｃｅ　ａｎｄ　ｐｒｏｐａｇａｔｉｏｎ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔ－　［８］ＧＡＮＥＳＡＮ　Ｄ，ＣＥＲＰＡ　Ａ，ＹＥ　Ｗｅｉ．Ｎｅｔｗｏｒｋｉｎｇ　ｉｓｓｕｅｓ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｗｏｒｔｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕ－　ｔｉｎｇ，２００４，６４：７９９—８１４．　ｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　１ｓｔ　Ｓｙｍｐ￣ｉｕｍ　ｏｎ　Ｎｅｔｗｏｒｋ　Ｓｙｓｔｅｍｓ　Ｄｅｓｉｇｎ　ｎｄ　ＩａｒｒＩｐｌｅｍｅｎｔａｔｉ０ｎ．２００４：１—１４．　［９］ＤＯＨＥＲＴＹ　Ｌ，ＰＩＳＴＥＲ　Ｋ　Ｓ　Ｊ．Ｓｃａｔｔｅｒｅｄ　ｄａｔａ　ｓｅｌｅｃｔｉｏｎ　ｆｏｒ　ｄｅｎｓｅ　ｓｅｎ—　ｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆｔｈｅ　３ｒｄ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｆｏｒｎｍａｔｉｏｎ　Ｐｒｏｃｅｓ－　ｓｉｎｇ　ｉｎ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ．２００４：３６９－３７８．　［１４］ＨＥＩＤＥＭＡＮＮ　Ｊ，ＳＩＬＶＡ　Ｆ，ＥＳＴＲＩＮ　Ｄ．Ｍａｔｃｈｉｎｇ　ｄａｔａ　ｄｉｓｓｅｍｉｎａｔｉｏｎ　ｌａｇｏｒｉｔｈｍｓ　ｔｏ　ａｐｐｌｉｃａｔｉｏｎ　ｒｅｑｕｉｅｍｅｎｔｓ［Ｃ］／／Ｐｒｏｒｃ　ｏｆ　ｔｈｅ　ｌｓｔ　Ｉｎｔ’１　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｍｂｅｄｄｅｄ　Ｎｅｔｗｏ￣ｅｄ　Ｓｅｎｓｏｒ　Ｓｙｓｔｅｍｓ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　ｐｍｓｓ，２００３：２１８．２２９．　［１０］ＲＡＭＡＮＡＴＨＡＮ　Ｎ，ＫＯＨＬＥＲ　Ｅ，ＥＳＴＲＩＮ　Ｄ．Ｔｏｗａｒｄｓ　ａ　ｄｅｂｕｇｇｉｎｇ