基 于 任 务 负 载 监 测 的 高 性 能 集 群 节 点 启 停 机 制 １，２， 曹荣强 １， 戴志辉 １，２， 朱　鹏 １， 迟学斌 １ 曹宗雁 （１．中国科学院计算机网络信息中心 超级计算中心， 北京 １００１９０； ２．中国科学院研究生院， 北京 １０００４９） 摘　要： 对高性能计算集群在运行过程中如何通过关闭闲置节点来实现有效节能的问题进行了研究和探讨，设 计和实现了基于任务负载量统计监测的节点启停机制。 根据对系统中作业运行和排队情况的记录和分析，通过 参数估计设计了反映队列任务情况的负载因子，并围绕负载因子制定具体策略，结合作业系统的队列设置和资 源分配规则，对集群中的空闲节点进行自动启停控制。 模拟实验表明，基于任务负载监测的节点启停机制能够 有效地自动启停系统中闲置的节点，从而降低系统功耗，并且对系统中作业的整体完成时间基本不造成影响。 关键词： 高性能计算机； 集群； 任务负载； 节点控制； 参数估计； 节能 中图分类号： ＴＰ３９３　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１１）１２唱４６６３唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．１２．０６９ Ｎｏｄｅｓ ｓｔａｒｔ／ｓｔｏｐ ｍｅｃｈａｎｉｓｍ ｆｏｒ ｈｉｇｈ唱ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐｕｔｉｎｇ ＣＡＯ Ｚｏｎｇ唱ｙａｎ１，２， ＣＡＯ Ｒｏｎｇ唱ｑｉａｎｇ１， ＤＡＩ Ｚｈｉ唱ｈｕｉ１，２， ＺＨＵ Ｐｅｎｇ１， ＣＨＩ Ｘｕｅ唱ｂｉｎ１ ｃｌｕｓｔｅｒｓ ｂａｓｅｄ ｏｎ ｔａｓｋ ｌｏａｄ ｍｏｎｉｔｏｒｉｎｇ （１．Supercomputing Center， Computer Network Information Center of Chinese Academy of Sciences， Beijing １００１９０， China； ２．Graduate School of Chinese Academy of Sciences， Beijing １０００４９， China） Abstract： Ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｄ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｃｌｏｓｉｎｇ ｉｄｌｅ ｎｏｄｅｓ ｔｏ ｓａｖｅ ｐｏｗｅｒ ｉｎ ｈｉｇｈ唱ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐｕｔｉｎｇ ｃｌｕｓｔｅｒｓ．Ｉｔ ｐｒｏ唱 ｐｏｓｅｄ ａ ｍｅｃｈａｎｉｓｍ ｆｏｒ ｎｏｄｅｓ ｓｔａｒｔ ａｎｄ ｓｔｏｐ ｃｏｎｔｒｏｌ ｂａｓｅｄ ｏｎ ｔａｓｋ ｌｏａｄ ｍｏｎｉｔｏｒｉｎｇ ａｎｄ ｓｔａｔｉｓｔｉｃｓ ａｎｄ ｄｅｓｉｇｎｅｄ ｔａｓｋ ｌｏａｄ ｉｎｄｉｃａｔｏｒ ｕｓｉｎｇ ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｉｏｎ．Ｉｔ ｓｅｔ ｕｐ ｄｅｔａｉｌ ｓｔｒａｔｅｇｉｅｓ ａｒｏｕｎｄ ｔｈｉｓ ｉｎｄｉｃａｔｏｒ ｔｏ ａｕｔｏｍａｔｉｃａｌｌｙ ｃｏｎｔｒｏｌ ｔｈｅ ｉｄｌｅ ｎｏｄｅｓ ｓｔａｒｔｉｎｇ ａｎｄ ｓｔｏｐｐｉｎｇ．Ｉｔ ａｌｓｏ ｃｏｎｓｉｄｅｒｅｄ ｑｕｅｕｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ａｎｄ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｏｆ ｊｏｂ ｍａｎａｇｅ ｓｙｓｔｅｍ ｉｎ ｔｈｅ ｓｔｒａｔｅｇｉｅｓ．Ｓｉｍｕｌａｔｉｏｎ ｔｅｓｔｓ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｎｏｄｅｓ ｓｔａｒｔ／ｓｔｏｐ ｍｅｃｈａｎｉｓｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｃｏｎｔｒｏｌ ｔｈｅ ｉｄｌｅ ｎｏｄｅｓ ｉｎ ｔｈｅ ｓｙｓｔｅｍ， ｓｏ ｔｈａｔ ｔｈｅ ｐｏｗｅｒ ｃｏｎｓｕｍｐｔｉｏｎ ｃａｎ ｂｅ ｒｅｄｕｃｅｄ； ｍｏｒｅｏｖｅｒ， ｔｈｅ ｍｅｃｈａｎｉｓｍ ｉｍｐａｃｔｓ ｖｅｒｙ ｌｉｔｔｌｅ ｏｎ ｔｈｅ ｓｙｓｔｅｍ ｏｖｅｒａｌｌ ｊｏｂ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｒｕｎｎｉｎｇ． Key words： ｈｉｇｈ唱ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐｕｔｅｒ； ｃｌｕｓｔｅｒ； ｔａｓｋ ｌｏａｄ； ｎｏｄｅ ｃｏｎｔｒｏｌ； ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｉｏｎ； ｐｏｗｅｒ ｓａｖｉｎｇ 第 ２８ 卷第 １２ 期 ２０１１ 年 １２ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ畅２８ Ｎｏ畅１２ Ｄｅｃ畅２０１１ 倡 第一大难题 大的电力资源开销给超级计算机的运行维护带来了巨大的挑 　　超级计算机规模扩大的同时也导致其功耗急剧提 高， ［１］，庞 ＴＯＰ５００ 中排名前３０ 位的机器总功率均在１ ０００ ＫＷ 以上 战。 人们认识到了高性能计算机带来的能源消耗的问题，ＤＡＲ唱 ＰＡ 在讨论Ｅｘａ（１０２１）级的高性能计算机时将系统能耗问题列为 ［２］。 在高性能计算机电力消耗得到重视的情况下， 系统管理工作自然要考虑到对系统功耗的控制和管理。 如何合 理地管理高性能计算机中的资源，在保证运行效率和服务能力 的同时，又能通过各种手段降低系统的总体功耗，节约电力资 源，实现绿色节能的高性能计算，是现今系统管理工作中值得研 究的问题。 本文以此为出发点，结合中国科学院超级计算环 的实际运行情况，利用对空闲计算节点的启停控制，对降低 ［３］ 系统整体功耗的方法和策略进行了研究和实现。 1　研究背景 式的不同使得这些工作不能直接应用于高性能计算集群。 高 性能计算集群在运行时，节点资源通常被划分为若干队列来接 收性质不同的用户作业。 而不同用户提交的作业频率、规模和 时长通常是随机的，在某一时刻可能队列中作业很多且大部分 在排队等待，而在另一时刻队列中作业则相对较少。 尤其是对 于作业运行时间较短的队列，在夜间或节假日等时段，用户向 系统中提交作业的可能性较低时，就很容易出现部分节点闲置 的情况。 另外，在系统运行时由于被调度执行的作业没能完全 装满队列，但剩余资源亦不足以装载其他作业，就会产生节点 碎片，碎片中的节点也会因为分不到作业而闲置。 闲置的节点 资源无法提供服务，因而造成了电力损耗。 对于集群来说，要让系统在整体任务较少时降低功耗，一 各个部件进入低功耗状态。 这种方法能够保证系统在线资源 数量稳定，应用的方法也较为简单，仅需安装好相应的驱动，并 设置好单台服务器的电源管理模式即可。 该方法的局限在于： ａ）低功率运行状态下系统仍然会有相当的功耗；ｂ） 有时因为 　　收稿日期： ２０１１唱０５唱２６； 修回日期： ２０１１唱０６唱３０　　基金项目： 国家“８６３” 计划重点资助项目（２００６ＡＡ０１Ａ１１６，２００６ＡＡ０１Ａ１１７）；中国科学院 “ 十一五” 信息化专项资助项目（ＩＮＦＯ唱１１５唱Ｂ０１） 作者简介：曹宗雁（１９８１唱），男，湖南湘潭人，助理研究员，博士，主要研究方向为高性能计算机系统管理及优化技术（ｚｙｃａｏ＠ｓｃｃａｓ．ｃｎ）；曹荣强 （１９８２唱），男，山东临沂人，助理研究员，博士，主要研究方向为计算网格、并行计算；戴志辉（１９８３唱），男，湖南涟源人，博士，主要研究方向为计算网 格、网格容错技术；朱鹏（１９７１唱），男，山东菏泽人，高级工程师，硕士，主要研究方向为高性能计算机体系结构、计算数学；迟学斌（１９６３唱），男，吉林 梅河口人，研究员，博士，主要研究方向为高性能计算方法与软件、并行计算应用． 在已有的关于降低集群功耗的研究中，有针对负载均衡集 ［５］，但系统运行方 ［４］，也有应用于分布式集群的方法 个途径是通过高级电源管理功能使空闲节点在开机的状态下 群的方法 境 

·４６６４· 驱动等原因使得状态切换不及时而影响应用性能；ｃ） 部分服 态运行，典型的例子如中国科学院超级计算中心的深腾 ７０００ 务器会因为硬件或操作系统版本的原因而无法支持低功耗状 超级计算机 ［６］。 ［７］。 让系统空闲时降低功耗的另一个方法是将空闲的资源直 要在保证服务水平的前提下通过关闭闲置节点来降低高 部分节点以降低系统总功耗的同时使系统的相对负载保持在 算集群的硬件厂商的产品都可以通过向供电控制模块发送命 接关闭或休眠，待需要时再将其启动或是唤醒。 多数高性能计 令来完成节点的开关机操作，并且在技术上不难实施。 该方法 能够使空闲节点的功耗达到或是接近０，从而让系统整体功耗 尽可能降至最低，关闭的节点大部分部件不会继续通电并发 热。 从机房散热的角度，这样做也能够进一步节约能源。 但这 样做的风险是会使系统中可用资源减少，如果实施不当，会出 现资源不足使得作业排队时间急剧上升，这相当于降低了服务 质量，对于用户来说是不可接受的 性能计算集群的功耗，需要制定合理的节点启停策略，在关闭 较均衡的水平；当监测到队列中作业量增大，可能需要更多的 资源时，应及时开启闲置节点，提供满足需求的节点资源，避免 出现作业调度响应时间过长的情况。 2　节点启停机制设计 2畅1　负载因子设计 要设计并实现基于负载监测的节点启停策略，确保节点启 停策略的有效性，首要任务是建立起一套对队列任务负载状况 进行监测和评价的机制。 这里所说的队列任务负载，不仅指当 前正在运行的作业对系统资源的占用状况，还包括队列中仍在 排队的作业可能对系统资源的使用情况。 由于在作业未完成 之前，从系统的角度几乎无法确定作业会在何时结束，因此必 须通过合理的估计对系统中未来可能需要的资源进行衡量。 Ｚｏｔｋｉｎｔ 等人在研究作业调度的回填策略时，针对未完成的作业 的运行时间估计这个问题，得出了两点结论：ａ） 策略的有效性 并不一定十分依赖于准确估计用户作业运行时长；ｂ） 如果采 ［８，９］。 从中可以得到一定的启发，即 用用户承诺的运行时间来执行回填策略的效果反倒不如采用 随机生成的作业运行时间 作业的运行时间能不能被准确估计并不一定是策略是否有效 的决定性条件。 ［１０］ ［１１］ 或负载预 已有的一些研究工作使用了随机调度的策略 对系统负载进行评估及控制，而本文尝试在高性 测的方法 能集群中采用更为简单的作业抽样统计并进行参数估计的方 法来估算队列中现有的任务负载。 首先对已完成作业情况进行统计。 考虑到不同规模的作 业对节点资源的实际消耗量相差较大，在进行资源消耗量的统 计和评估时，按作业规模划分区间进行统计，将队列中接收的 作业规模按照一定间隔（ 如 ２ 的整数次方） 划分成不同的区 间，从系统日志中回溯选取或是随机抽取足够数量已完成作业 的信息作为样本，例如某区间内的作业样本数量不够多，可以 将该组与其相邻的组进行合并处理。 分组完成后，对每一组中 每个作业样本计算其资源消耗量，即作业规模 ×实际运行时 长，并求出每组的样本均值和样本方差。 可知，当样本数量足够大 （≥３０）时，样本均值接近正态分布，可以用参数估计的方法， 由 Ｌｙａｐｕｎｏｖ 中心极限定理 ［１２］ 计 算 机 应 用 研 究 　 第 ２８ 卷 σ２ n σ２ n ，μ＋Z α２ 使用上面的样本均值和样本方差近似估算作业资源占用量均 间计数并分别乘以该规模作业资源占用量均值估计下界和均 值置信度在 α的置信区间。 当某个区间内作业数为 n、作业样 本资源占用量均值为 μ、样本资源占用量方差为 σ时，这样在 满足 α置信度的情况下，该规模作业整体资源占用量均值的 置信区间为 μ－Z α２ ，这即是该作业规模资源占 用量的均值在置信区间内的最小值和最大值，记这两个值为 rｍｉｎ 和 rｍａｘ。 然后据此对队列内的现存作业按不同作业规模区 值估计上界，得出该队列剩余作业资源占用量的最小估计值和 最大估计值。 为确保高性能计算机服务的有效性，在实际实现 过程中采用均值估计上界即 rｍａｘ。 接下来依据一定的规则或 倾向性，对不同队列定义不同的归一化转换函数，函数值随作 业估值同向变化，将求得的函数值定义为队列的负载因子 T。 本文工作在实现中采用了较为简单的转换函数，令负载因子 T 等于队列全部规模的作业资源占用量均值估计上界 rｍａｘ 之和 与队列节点数量 p 和队列允许的作业最长时间 tｍａｘ 乘积之比， 即 T ＝（Σrｍａｘ）／（p ×tｍａｘ）。 2畅2　节点启停策略 情况。 求出了队列的负载因子后，针对负载因子来制定节点启 停的规则，在队列负载因子较低时关闭空闲节点，较高时再开 启，从而有效降低系统功耗。 节点启停策略需要设定两个基本阈值用于启停控制，即闲 置节点关闭阈值 Tc 和闲置节点开启阈值 Ts（Ts ＞Tc）。 当队列 的负载因子低于 Tc 时，关闭部分闲置的节点；当队列的负载因 子高于 Ts 时，将部分因闲置关闭的节点启动。 除了 Tc 和 Ts 之 外，在节点启停机制发生作用时，还需要预先定义两个参考值 Tc′（Ts ＞Tc′＞Tc）和 Ts′（Ts ＞Ts′＞Tc），分别用于计算关闭和开 启节点的数量，以保证启停动作完成之后队列的负载因子大小 适中，减少反复启停操作的可能。 还需要注意的是，在关闭和开启节点时，需要考虑到作业 系统对队列的配置情况，保证队列在逻辑上的有效性，避免成 为无效队列而浪费资源，降低服务水平。 队列的负载因子能够在一定程度上反映队列目前的负载 综合以上原则，设计出节点启停策略的细节如下： ａ）计算队列当前的负载因子。 ｂ）如果队列负载因子高于开启阈值 Ts，或队列中排队的 最大作业规模超过了开启的节点总数，再或者空闲节点数量少 于队列允许的最小作业规模，则开启部分或全部已关闭的节 点，使队列达到下列状态之一： （ａ） 全部闲置节点开启，开启后负载因子仍然高于 Ts，且 队列中闲置节点数不小于队列允许的最小作业规模； （ｂ）开启部分已关闭的节点，开启后负载因子小于 Ts′，且 开启后队列中闲置节点数等于队列允许的最小作业规模，但如 于排队中作业最大规模，则应保证开启后的总节点数不小于排 队中最大作业规模； （ｃ）开启部分已关闭的节点，开启后负载因子等于或最接 近 Ts′，队列中闲置节点数不小于队列允许的的最小作业规模， 且所有未关闭的节点数不小于排队中最大作业规模； （ｄ）如果以上条件皆无法满足，则不开启任何节点。 ｃ）如果队列的负载因子低于闲置节点关闭阈值 Tc，或是 闲置节点数小于队列允许的最小作业规模，则关闭部分或全部 果有作业运行的节点数量与队列允许的最小作业规模之和小 

有作业运行的节点数量与队列允许的最小作业规模之和小于 第 １２ 期 闲置节点，使队列达到下列状态之一： （ａ）全部闲置节点关闭，关闭后负载因子仍低于 Tc，且队 列中正在运行作业的节点数不小于排队中最大作业规模； （ｂ）部分节点关闭，关闭后队列的负载因子小于 Tc′，且关 闭后队列中闲置节点数等于队列允许的最小作业规模，但如果 排队中作业最大规模，则应保证未关闭节点数不小于排队中最 大作业规模； （ｃ）部分节点关闭，关闭后队列的负载因子等于或最接近 于 Tc′，队列中闲置节点数不小于队列允许的最小作业规模，且 未关闭的节点数不小于排队中最大作业规模； （ｄ）如果以上条件皆无法满足，则说明队列中开启的闲置 节点是碎片节点，不论负载因子是多少，直接关闭。 ｄ）全部调整完毕，等待下一次实施策略。 3　模拟测试及结果分析 通过模拟程序虚拟出与深腾７０００ 功能相似的队列进行了模 拟测试，模拟程序用Ｃ 语言编写，实现了队列的作业接收、作业调 度、节点资源分配等功能 ［１３］。 在这些功能的基础上，加入了作业 历史信息的统计、队列负载因子的估计和节点的启停功能。 队列设 置 参 考 的 是 深 腾 ７０００ 上 ｘ６４＿ｂｌａｄｅｓ 队 列 的 设 ［６］，允许接收的作业规模为 １６ ～５１２ 处理器核心（ 每节点 ８ 处理器核心），作业运行的最长时间为 ６０ ｍｉｎ。 提交到队列的 作业来自于２００９ 年９ 月２８ 日至１０ 月３１ 日深腾７０００ 上 ｘ６４＿ ｂｌａｄｅｓ 队列接收到的真实作业数据信息。 关于节点启停策略的参数设置如下：关闭阈值 Tc 为 ０畅７， 开启阈值 Ts 为 １畅５，而两个中间参考值 Tc′和 Ts′分别设定为 １畅０ 和０畅９。 节点机在获取开机命令之后５ ｍｉｎ 才能完全开启 并接收作业。 而引起的启停机制效果变化的情况，依次设置模拟队列的节点 数为３２０、２４０ 和１６０ 节点进行三组测试，每组测试中设置不同 的节点启停机制启用的间隔，分别为 ３０、６０、１２０、２４０ ｍｉｎ。 通 过考察全部作业耗时、作业平均等待时间和节点关闭总时间来 验证基于任务负载监控的启停机制的效果。 三组测试的结果 数据分别列于表１ ～３ 中，而图１ 则画出了模拟测试中作业完 成所需的虚拟时长及各种机时的占比情况。 表 １　模拟 ３２０ 节点队列测试结果 为了体现出因队列资源的多少导致队列的负载程度不同 置 关机机时 作业机时 闲置机时 总时长／ｍｉｎ ４８ ９１５ ４８ ９１７ ４８ ９１５ ４８ ９１５ ４８ ９１５ 占比／％ ．４１ ５７ ．４１ ５７ ．４１ ５７ ５７ ．４１ ５７ ．４１ 占比／％ ．６６ ３９ ．７３ ３８ ３７ ．０７ ３０ ．７６ ０ ．００ 表 ２　模拟 ２４０ 节点队列测试结果 占比／％ ．９３ ２ ．８６ ３ ．５２ ５ １１ ．８３ ４２ ．５９ 平均等待 时间／ｍｉｎ ．５３ １ ．５５ １ ．８０ １ ２ ．２７ ０ ．６８ 调整频 率／ｍｉｎ ３０ ６０ １２０ ２４０ 全开 调整频 率／ｍｉｎ ３０ ６０ １２０ ２４０ 全开 总时长／ｍｉｎ ４９ ４８６ ４９ ４５６ ４９ ５０９ ４９ ３９１ ４９ ４０１ 作业机时 占比／％ ７５ ．６７ ．７１ ７５ ．６３ ７５ ７５ ．８１ ７５ ．８０ 闲置机时 占比／％ ３ ．３２ ．８３ ３ ．１５ ５ ８ ．２２ ２４ ．２０ 关机机时 占比／％ ２１ ．０１ ．４６ ２０ １９ ．２１ １５ ．９７ ０ ．００ 平均等待 时间／ｍｉｎ ３ ．４３ ．４５ ３ ．６２ ３ ３ ．５７ ２ ．７３ 　　可以看到，对于３２０ 节点的模拟队列，由于节点资源充足， 采用不同间隔的启停机制和保持节点全开对作业的总完成时 曹宗雁，等：基于任务负载监测的高性能集群节点启停机制 ·５６６４· 　　　 间影响很小；因启停机制生效而产生的节点关闭时间也很高； 当启停机制检测执行的频率越高时，节约的机时也就越多。 但 是启停机制对于作业的平均等待时间造成了一定的影响，启停 调整频率越低，平均等待时间增加得越多，这对执行作业的用 户可能是一个不利的影响。 从对节点数量稍少的 ２４０ 节点队 列的模拟测试（表２）中可以看出，作业总耗时和作业平均等待 时间相较３２０ 节点队列模拟有一定的增加，而采用不同间隔的 影响。 由于少了６０ 个节点，而作业量没有变化，因此在总耗时 不变的情况下闲置的机时亦有所下降，节点关闭的总时间占比 也有所减少。 从对于节点数量较少、队列负担相对较重情况的 １６０ 节点队列的模拟测试（表３）中可以看出，作业完成总时间 大幅增加，这是因为给定的节点数在与前两组模拟相近的时间 内能够提供的机时资源已小于全部作业所需，故需要花费更多 的时间才能完成所有作业，平均等待时间也随之激增，节点关 闭的总机时急剧减少。 在这种情况下，不论采用何种间隔的启 停机制来调整，关机机时占比都相对较少。 启停机制和保持节点全开对作业的总完成时间也有了微小的 表 ３　模拟 １６０ 节点队列测试结果 调整频 率／ｍｉｎ ３０ ６０ １２０ ２４０ 全开 总时长／ｍｉｎ ６２ ２５７ ６２ ２２１ ６２ １００ ６２ １４２ ６２ ０３４ 作业机时 占比／％ ．２２ ９０ ９０ ．２７ ．４５ ９０ ．３９ ９０ ９０ ．５４ 闲置机时 占比／％ ．２３ ４ ４ ．２２ ．４４ ４ ．２０ ５ ９ ．４６ 关机机时 占比／％ ．５６ ５ ５ ．５１ ．１２ ５ ．４２ ４ ０ ．００ 平均等待 时间／ｍｉｎ ５７ ．９７ ５８ ．３０ ．２５ ５７ ．３７ ５７ ．５３ ５６ 　　综合上面的实验结果，可以得出结论：当队列中节点资源 比较充裕、队列的任务负载量不高时，节点启停机制能够通过 关闭节点有效地节约闲置的机时，但是会造成作业平均等待时 间的增加；而当队列负载很重的情况下，启停机制产生的作用 不会很大。 实验结果表明，采用执行频率更高的启停机制得到 的实验数据会更好，但是需要考虑到频繁实施节点启停策略会 给节点硬件以及机房整体供电带来的冲击，因此在实际中还需 要选取合适的频率来执行启停调整。 4　结束语 本文提出在高性能计算集群、运行过程，根据队列任务负 载情况自动启停节点的机制，减小系统功耗， （ 下转第 ４６８０ 页） 

·０８６４· 式（８）（９）计算的结果比较（表３），其中取 p ＝０．９９。 表３ 中的 上限１ 是用式（８） 计算的结果，上限 ２ 是用样本计算的结果； 下限１ 是用式（９） 计算的结果，下限 ２ 是用样本计算的结果。 从表３ 可以看出，样本中的数据完全在式（８）（９）计算的上、下 限之间。 二跳 ９ 一跳 ０ ．００１４ ．０１２２ ．０１１２ ０ ０ ０ 表 ２　ＷＳＮＴＳ 误差的期望和标准差 期望 １ 期望 ２ 标准差 １ 标准差 ２ ０ ．５９６８ｅ －００４ ．０１７３ ０ ０ ．０１５０ 表 ３　ＷＳＮＴＳ 误差的上、下限 ．０４４６ ０ ．０２６４ ０ －０ ．０４４６ ．０２００ －０ ．０３１４ ０ ．０２６６ ０ －０ ．０３１４ ．０２０３ －０ 上限 １ 上限 ２ 下限 １ 下限 ２ 一跳 二跳 项目 项目 期望 标准差 上限 下限 三跳 ０ ．００１７ ．０２１２ ．０１３７ ０ ０ ０ 三跳 ．０５４６ ０ ．０２７６ ０ －０ ．０５４６ ．０２７２ －０ 4　结束语 本文在已有研究的基础上，考虑了发送方时延和接收方时 延对ＷＳＮＴＳ 误差的影响，分析并给出了影响 ＷＳＮＴＳ 误差的因 素及其分布规律。 首先，在分析了经典的 ＴＰＳＮ 时间同步协议 双向报文交换机制的基础上，指出了影响 ＷＳＮＴＳ 误差的因素， 建立了数学模型；其次，给出并证明了在考虑发送方时延和接收 方时延后单跳 ＷＳＮＴＳ 误差仍然服从正态分布的分布规律；最 后，给出了多跳ＷＳＮＴＳ 最大误差的随机过程模型，计算出了其 期望和方差，并给出其上、下限，得到了比文献［５］ 更普适的结 论。 仿真实验结果证明了这些结论的正确性。 参考文献： ［１］ ＬＡＳＡＳＳＭＥＨ Ｓ Ｍ， ＣＯＮＲＡＤ Ｊ Ｍ．Ｔｉｍｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ： ａ ｓｕｒｖｅｙ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｓｏｕｔｈｅａｓｔ Ｃｏｎｆｅｒｅｎｃｅ （上接第 ４６６５ 页）设计了根据作业统计信息估算的负载因子，并 设计实现了节点自动启停机制。 模拟实验表明，在队列中节点 资源较为充足的情况下，节点启停机制能够收到较好的效果， 但同时也会带来平均作业等待时间一定程度的增长。 下一步 探索和优化，而对于启停节点造成的抖动对系统的冲击也需要 作进一步观察，力求在保证系统全局稳定运行的情况下尽可能 地节约更多的能源。 参考文献： ［１］ Ｔｏｐ ５００ ｓｕｐｅｒｃｏｍｐｕｔｅｒ ｓｉｔｅｓ［ＥＢ／ＯＬ］．（２０１０唱１１唱１５）［２０１１唱０５唱 ２３］．ｈｔｔｐ：／／ｗｗｗ．ｔｏｐ５００．ｏｒｇ／． ［２］ ＫＯＧＧＥ Ｐ， ＢＥＲＧＭＡＮ Ｋ， ＢＯＲＫＡＲ Ｓ， et al．Ｅｘａｓｃａｌｅ ｃｏｍｐｕｔｉｎｇ ｓｔｕｄｙ： ｔｅｃｈｎｏｌｏｇｙ ｃｈａｌｌｅｎｇｅｓ ｉｎ ａｃｈｉｅｖｉｎｇ ｅｘａｓｃａｌｅ ｓｙｓｔｅｍｓ ［ Ｒ］． Ｗａｓｈｉｎｇｔｏｎ ＤＣ： ＤＡＲＰＡ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ Ｏｆｆｉｃｅ， ２００８． ［３］ 中国 科 学 院 超 级 计 算 环 境［ＥＢ／ＯＬ］．（２０１１唱０５唱０１）［２０１１唱０５唱 ２５］．ｈｔｔｐ：／／ｗｗｗ．ｃｓｃｇｒｉｄ．ｃｎ／． ［４］ ｆｏｒ ｉｄｌｅ ｓｙｓｔｅｍ ｉｎ ｃｌｕｓｔｅｒｓ： ＳＲＩＮＩＶＡＳＡＮ Ｖ．Ｐｏｗｅｒ ｍａｎａｇｅｍｅｎｔ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ， ２０１１／０１０６９３５［Ｐ］．２０１１唱０５唱０５． ［５］ ＯＰＰＥＮＨＥＩＭ Ｂ Ｍ．Ｒｅｄｕｃｉｎｇ ｃｌｕｓｔｅｒ ｐｏｗｅｒ ｃｏｎｓｕｍｐｔｉｏｎ ｂｙ ｄｙｎａｍｉ唱 ｃａｌｌｙ ｓｕｓｐｅｎｄｉｎｇ ｉｄｌｅ ｎｏｄｅｓ［Ｄ］．Ｓａｎ Ｌｕｉｓ Ｏｂｉｓｐｏ： Ｃａｌｉｆｏｒｎｉａ Ｐｏｌｙ唱 将对负载因子的生成函数以及启停策略的各项参数作进一步 计 算 机 应 用 研 究 　 第 ２８ 卷 （ＳｏｕｔｈｅａｓｔＣｏｎ）．２０１０： ２４２唱２４５． ［２］ ＨＵ Ｘｉｎ， ＰＡＲＫ Ｔ， ＳＨＩＮ Ｋ Ｇ．Ａｔｔａｃｋ唱Ｔｏｌｅｒａｎｔ ｔｉｍｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２７ｔｈ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．２００８： ４１唱４５． ［３］ ＳＵ Ｗｅｉ唱ｌｉａｎ， ＡＫＹＩＬＤＩＺ Ｉ Ｆ．Ｔｉｍｅ唱ｄｉｆｆｕｓｉｏｎ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］．IEEE／ACM Trans on Networ唱 king， ２００５，13（２）：３８４唱３９７． ［４］ 董超，田畅，倪明放．Ａｄ ｈｏｃ 网络时钟同步研究［Ｊ］．通 信 学 报， ２００６，27（９）： １１０唱１１７． ［５］ 田贤忠， 陈长军， 胡同森．无线传感器网络时间同步概率误差研 究［Ｊ］．计算机应用研究， ２００９，26（６）： ２１９９唱２２０１． ［６］ 钟海东， 邬春学， 孔若英．无线传感器网络时间同步算法误差分 析［Ｊ］．微计算机信息， ２００８（４）： １５１唱１５２． ［７］ ＧＡＮＥＲＩＷＡＬ Ｓ， ＫＵＭＡＲ Ｒ， ＳＲＩＶＡＳＴＡＶＡ Ｍ Ｂ．Ｔｉｍｉｎｇ唱ｓｙｎｃ ｐｒｏ唱 ｔｏｃｏｌ ｆｏｒ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅ唱 ｒｅｎｃｅ ｏｎ Ｅｍｂｅｄｄｅｄ Ｎｅｔｗｏｒｋｅｄ Ｓｅｎｓｏｒ Ｓｙｓｔｅｍｓ．２００３： １３８唱１４９． ［８］ ＫＵＬＡＫＬＩ Ａ Ｂ， ＥＲＣＩＹＥＳ Ｋ．Ｔｉｍｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｏｎ ｔｉｍｉｎｇ唱ｓｙｎｃ ｐｒｏｔｏｃｏｌ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ． ２００８：１８０唱１８４． ［９］ 李晓维， 徐勇军， 任丰原．无线传感器网络 技术［Ｍ］．北京： 北 京理工大学出版社， ２００７． ［１０］ ＴＩＡＮ Ｚｈｅｎ， ＹＵＡＮ Ｄｏｎｇ唱ｆｅｎｇ， ＬＩＡＮＧ Ｑｕａｎ唱ｑｕａｎ．Ｅｎｅｒｇｙ ｅｆｆｉｃｉｅｎ唱 ｃｙ ａｎａｌｙｓｉｓ ｏｆ ｅｒｒｏｒ ｃｏｎｔｒｏｌ ｓｃｈｅｍｅｓ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／／ Ｐｒｏｃ ｏｆ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ． ２００８： ４０１唱４０５． ［１１］ ＧＡＮＧ Ｘｉｏｎｇ， ＫＩＳＨＯＲＥ Ｓ．Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｎｓｅｎｓｕｓ ｔｉｍｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｗｉｔｈ Ｇａｕｓｓｉａｎ ｄｅｌａｙ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎ唱 ｆｅｒｅｎｃｅ．２００９： １唱５． ［１２］ 杨博，廖明宏．基 于 统 计 的 无 线 传 感 器 网 络 时 钟 同 步 协 议［Ｊ］． 哈尔滨工业大学学报， ２００７，39（１）：９８唱１０１． ｔｅｃｈｎｉｃ Ｓｔａｔｅ Ｕｎｉｖｅｒｓｉｔｙ， ２０１０． ［６］ 深腾７０００ 使用指南［ＥＢ／ＯＬ］．（２０１０唱０５唱１１）［２０１１唱０５唱２３］．ｈｔｔｐ：／／ ｗｗｗ．ｓｃｃａｓ．ｃｎ／ｇｂ／ｃｏｍｐｕｔｅ／ｓｕｐｐｏｒｔｓ／ｄｏｃｕｍｅｎｔｓ／Ｌｅｎｏｖｏ７０００．ｐｄｆ． ［７］ 中科院网络中心 ２０１０ 年第三方服务质量调查用户意见与建议落 实情况［ＥＢ／ＯＬ］．（２０１１唱０３唱１７） ［２０１１唱０５唱２５］．ｈｔｔｐ：／／ｗｗｗ． ｃｎｉｃ．ｃａｓ．ｃｎ／ｆｄｔｐ／２０１１０３／ｔ２０１１０３１７＿３０８６８８９．ｈｔｍｌ． ［８］ ＭＵ’ＡＬＥＭ Ａ Ｗ， ＦＥＩＴＥＬＳＯＮ Ｄ Ｇ．Ｕｔｉｌｉｚａｔｉｏｎ， ｐｒｅｄｉｃｔａｂｉｌｉｔｙ， ｗｏｒｋｌｏａｄｓ， ａｎｄ ｕｓｅｒ ｒｕｎｔｉｍｅ ｅｓｔｉｍａｔｅｓｉｎ ｓｃｈｅｄｕｌｉｎｇ ｔｈｅ ＩＢＭ ＳＰ２ ｗｉｔｈ ｂａｃｋｆｉｌｌｉｎｇ［ Ｊ］．IEEE Trans on Parallel and Distributed Sys唱 tems，２００１，12（６）：５２９唱５４３． ［９］ ＺＯＴＫＩＮ Ｄ， ＫＥＬＥＨＥＲ Ｐ Ｊ．Ｊｏｂ唱ｌｅｎｇｔｈ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｂａｃｋｆｉｌｌｉｎｇ ｓｃｈｅｄｕｌｅｒｓ ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ８ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ．Ｃａｌｉｆｏｒｎｉａ： Ｃｉｔｅｓｅｅｒ，１９９９：２３６唱２４３． ［１０］ 石高涛，廖明宏．大规模传感器网络随机睡眠调度节能机制［Ｊ］． 计算机研究与发展，２００６，43（４）：５７９唱５８５． ［１１］ 张立敏．渲染集群节能控制研究与实现［Ｄ］．长沙： 湖南师范大 学， ２００８． ［１２］ 盛骤，谢式千，潘承毅．概率论与数理统计［Ｍ］．２ 版．北京：高等 教育出版社， １９８９： ４０３． ［１３］ 曹宗雁，赵毅， 牛 铁，等．基 于 用 户 评 价 的 集 群 作 业 优 先 级 调 度 ［Ｊ］．华中科技大学学报：自然科学版，２０１１，39（Ｓ１）：１３４唱１３８．