（检测技术与自动化装置专业论文）无线传感器网络中任务动态调度.pdf

摘要 摘要 无线传感器网( w i r e l e s ss e n s o rn e t w o r k ) 是当前在国际上备受关注的、涉及多 学科高度交叉、知识高度集成的前沿热点研究领域。本文主要针对无线传感器网 络中任务的动态调度展开研究，与其他算法相比由于蚁群算法具有正反馈、分布 式等诸多优点，本文选取蚁群算法作为任务动态调度算法。因为无线传感器网络 的能量受限特点，所以任务调度算法要在保证任务调度成功率基础上，尽量降低 任务能耗以延长网络寿命。基于以上两点要求和蚁群算法局部最优的缺点，对蚁 群算法进行信息素局部扩散和基于能量的启发函数的改进，仿真试验证明改进策 略不但可以有效提高任务调度成功率，而且还可以延长网络寿命。为了在网络后 期节点出现死亡时，进步提高调度成功率，本文提出了一种任务迁移策略，按 照节点能量与任务能耗确定迁移时刻，在节点死亡前将任务迁移到其他节点执行， 仿真试验证明，此种迁移策略的确对提高任务调度成功率有一定效果。 由于任务间不可避免的有数据依赖关系，针对这种互相联系得任务，本文以 d a g 任务描述为基础，对图解一重构算法进行改进，得到任务聚合动态复制算法 ( c g d c ) ，改进后的算法分聚簇、复制和冗余删除三个部分。经c g d c 算法形成的 任务簇交由蚁群算法向传感器节点调度，仿真试验中，与其他d a g 任务图动态调 度算法相比，c g d c 算法取得了较优的结果。 关键词：任务动态调度，蚁群算法，调度成功率，网络寿命 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k ( w i r e l e s ss e n s o rn e t w o r k ) i st h ec u r r e n tc o n c e r n i nt h e i m e m a t i o 叫c o m m u n i t yw h i c hi n v o l v i n gah i g hd e g r e e o fc r o s s m u l t i d i s e i p l i n a r y , h i g h l yi n t e g r a t e dk n o w l e d g eo fc u t t i n g e d g er e s e a r c ha r e a s i nt h i sp a p e r , w e m a l 蚵 r e s e a r c hi nt a s k sd y n a m i cs c h e d u l i n gi nw i r e l e s ss e n s o rn e t w o r k s c o m p a r e d 埘吐lo t h e r a l g o r i t h m sa n tc o l o n ya l g o r i t h mh a sp o s i t i v e f e e d b a c k ，d i s t r i b u t e d ，a n dm a n y 甜1 e r a d v a i l t a g e s ，s oi nt h i sp a p e r , w es e l e c ta n tc o l o n ya l g o r i t h mf o r t h ed y n a m i cs c h e d u l i n g a l g o r i t h m i nw i r e l e s s s e n s o rn e t w o r k s ，n o d e se n e r g yi sc o n s t r a i n e d ，s o t h et a s k s c h e d u l i n ga l g o r i t h mn o to n l yt oe n s u r et h es u c c e s s r a t eo ft a s k sd y n a m i cs c h e d u l i n g ， b u ta l s ot oe x t e n dn e t w o r kl i f e b a s e do nt h ea b o v et w or e q u i r e m e n t sa n dt h e a n tc o l o n y a l g o r i t h m ，sd i s a d v a n t a g eo f l o c a lo p t i m i z a t i o n , w ei m p r o v ea n tc o l o n ya l g o r i t h mf r o m p h e r o m o n ed y n a m i cd i f f u s ea n dh e u r i s t i c f u n c t i o ni m p r o v i n gb a s e do ne n e r g yc o s t s i m u l a t i o nt e s tp r o v e dt h a tt h ei m p r o v i n gw a y n o to n l yt oe n h a n c et h es u c c e s sr a t eo f t a s ks c h e d u l i n g ，b u ta l s ot oe x t e n dt h en e t w o r kl i f e t i m e i no r d e rt ol m p r o v m g s u c c e s s r a t e 鼬e rw h e nn o d e sb e g i nt od e a d ，w ep u tf o r w a r dat a s km i g r a t i o ns t r a t e g y i nf a c t t h i ss t r a t e g ya c h i e v e dt h ei n i t i a lp u r p o s e r e a j l y ，d a t 2 l 也a tt a s k sn e e da l w a y sf r o mo t h e r s i nv i e w o ft h i st a s kw h i c hc o n t a c t w i t he a c ho t h e r , t h i sp a p e rp u t f o r w a r da c g d c p o l i c y w h i c hi s b a s e do n p a r t i t i o n - r e c o n f i g u r a t i o na r i t h m e t i c c g d cp o l i c y c o n s i s t so ft h r e ep a r tw h i c hi sc r i t i c a lp 抽 亿kg a t h e r t a s kd y n a m i cc o p ya n dr e d u n d a n c yt a s kd e l e t e t a s kc l u s t e r s c o m ei n t ob e i n gb y c g d cp o l i c ya n ds c h e d u l eb ya n tc o l o n ya l g o r i t h m f i n a l l yc o m p a r e dw i t ho t h e r t a s k d y n a m a t i cs c h e d u l i n ga l g o r i t h m t h a tb a s e do nd a g , c g d cp o l i c ya c h i e v e d b e t t e r r e s u l t s k e y w o r d s ：t a s kd y n a m i cs c h e d u l i n g ，a n tc o l o n y a l g o r i t h m ，s u c c e s s r a t eo f s c h e d u l i n g ，n e t w o r kl i f e n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：互垂瑶灶日期：砂a 7 年 衫月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：堑霪 日期：乙p 呷年乡月e t 第一章绪论 1 1 研究背景与现状 第一章绪论 1 1 1 无线传感器网络研究现状与综述 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ) 是当前在国际上备受关注的、涉及 多学科高度交叉、知识高度集成的前沿热点研究领域【l 】。无线传感器网络能够实时 监测、感知和采集网络分布区域内的各种环境或监测对象的信息，包括温度、湿 度、噪声、光强度、电磁波、压力、土壤成分、移动物体的大小、速度和方向等 物理信号和物质现象，并对这些信息进行处理，从而为远程用户提供详尽而准确 的信息【2 】。其整体网络架构如图卜1 。 图1 1 无线传感器网络整体架构图1 2 1 图1 - 1 种从宏观上对无线传感器网络进行了描述，传感器节点被飞机随即抛 撤在固定区域，节点间通过自组织形成网络和路由，汇集的数据经过网关节点发 送到远端基站或卫星网络，由基站或卫星将数据转发到数据中心或最终用户。传 感节点组成了无线传感器网络的最小单位，每一节点由分别由传感器模块、处理 模块、无线收发模块和能量模块组成，各模块之间联系如图卜2 描述。 由于无线传感器网络的实用性，其被广泛应用于国防军事、国家安全、环境 监测、交通管理、医疗卫生、制造业及反恐抗灾等众多领域【3 ，4 】。近年来无线传感 器网络得到了社会各界的广泛关注，美国著名的期刊商业周刊【5 j 和技术评论 1 6 j 分别于1 9 9 9 年和2 0 0 3 年将无线传感器网络列为2 1 世纪最重要的技术和即将改 电子科技人学硕士学位论文 变世界的1 0 大新技术之一，另外2 0 0 3 年8 月2 5 同的商业周刊指出传感器网 络作为四大高技术产业之一将掀起新的产业浪潮【_ j 。 无线传感器网络的研究不仅得到学术界的关注，也得到了各国政府部门的极 大重视与支持，并给予了较大的资金投入。根据有关资料，美国自然科学基金委 员会2 0 0 3 年制定了传感器网络研究计划，投资3 4 0 0 万美元支持相关基础理论的 研究。美国国防部和各军事部门都均对传感器网络给予了高度重视，并在该领域 的投入更为巨大，包括美国国防部著名的s e n s l t 项刚圳。 图1 - 2 无线传感器网络节点结构酣1 1 j 国外的许多大学和研究机构纷纷投入了大量的研发力量从事无线传感器网络 软硬件系统的研究工作。最具代表性的是美国j j h , j 小i 大学伯克利分校( u c b e r k e l e y ) 和英特尔公司( i n t e l ) 联合成立的“智能尘埃( s m a r td u s t ) ”实验室，它的目标是 为美国军方提供能够在一立方毫米的体积内自治地完成感知和通信功能的设备原 型系统( a u t o n o m o u ss e n s i n ga n dc o m m u n i c a t i o ni nac u b i cm i l l i m e t e r ) ，也就是无线 传感器网络节点的研制。这项工作从1 9 9 8 年开始到2 0 0 1 年结束，受到了美国国 防预先研究计划局( d a r p a ：t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 的 支持。在随后的几年里，加州大学伯克利分校有多个实验室开始了关于无线传感 器网络及其相关的工作，如：n e s t ( n e t w o r ke m b e d d e ds y s t e m st e c h n o l o g y ) 、 w e b s ( w i r e l e s se m b e d d e ds y s t e m ) 、b a r w a n ( b a ya r e ar e s e a r c hw i r e l e s sa c c e s s n e t w o r k l 、b w r c ( b e r k e l e yw i r e l e s sr e s e a r c hc e n t e r ) 等实验室【8 | ，从不同的角度对 无线传感器网络进行了大量具有开创性的研究。 近年来，国内对无线传感器网络的研究也不断加深，起步较早的科研机构有 中科院软件研究所，中科院沈阳自动化所，浙江大学，清华大学，华中科技大学， 哈尔滨工业大学，西北工业大学，黑龙江大学等。中国国家自然科学基金委 ( n a t i o n a ls c i e n c ef o u n d m i o no f c h i n a ，n s f c ) 于2 0 0 3 年开始对无线传感器网络的 研究进行了资助，其中2 0 0 4 年将“基于无线传感器网络的分布自治系统及协调控 2 第一章绪论 制”列为重点项目立项，2 0 0 5 年又有两项无线传感器网络相关项目列为重点项目 立项，而且关于无线传感器网络的面上资助项目达1 4 项之多9 1 。 1 1 2 无线传感器网络任务描述 任务描述是任务调度的基础，任务描述能力直接影响任务分配系统的复杂性， 传感器网络的任务描述涉及了对任务功能的描述和对参与任务的节点的描述问 题。在目前的研究中，通常采用有向无环图( d a g 图) 【1 2 】、a t a g ( a b s t r a c tt a s kg r a p h ) 图【1 3 l 和角色任务图 1 4 , 1 5 1 对传感器网络的任务进行描述。以下对这几重描述方式分 别阐述。 有向无环图( d a g ) 有向无环图的描述方式如图1 3 ，设d a g = ( t ，e ，w ，c ) 为一四元组，丁是任 务节点的集合，t 表示第i 个任务；e = q ，it it ，t 表示任务结点间通信边的 集合，p 。为边；w 是任务计算开销的集合，w w 表示f ，的计算开销；c 是任务 间通信开销的集合， c ：? c 表示t i 和f ，之间的通信开销，如果两个任务被映射到 。 同一节点，那么q ，就变成0 。例如c ，表示任务与任务，2 的通信数据量，结合图 2 - 3 可知，c ，= 2 ，若f 1 、如在同一处理器执行，则q ，= 0 。 图1 3 任务的d a g 描述 基于角色的任务图 无线传感器网络与传统网络不同，网络中的节点有明显的分工特色，每个节 电子科技人学硕士学位论文 点都在扮演不同角色，角色扮演是传感器节点所特有的、被系统赋予的或者期待 的某种行为，例如，汇聚节点、簇首节点、路由节点、探测节点、休眠节点等。 网络中的每一节点至少扮演一种角色，在满足约束的条件下，传感器节点根据自 身能力和任务需求也可持有多种角色。 在任务执行时，由于传感器节点状态、参数的变化将影响其当前角色的扮演， 所以角色扮演不是一成不变的，是动态的。所以任务调度过程中需要根据角色变 化及时调整任务分配方案。基于角色扮演的不确定性，k a yr o m e r 1 6 提出了一种角 色描述模式，该模式包括角色说明和属性目录等要素。节点具体充当或扮演何种 角色需要实时的参数和属性目录确定。属性目录中包含了节点所固有的属性，例 如，处理能力、内存容量、传感器配备、通信带宽、地理位置等，主要说明了节 点的能力。在k a yr o m e r 提出的角色说明模式里面，实时参数和属性目录联合确 定了当前传感器节点所扮演的角色。 探测节点 节点 广、)休眠节点 图1 4 任务服务角色抽象图i l o j 图1 4 是由m a n i s hk o c h h a l1 1 6 】等提出了一种基于角色的通用抽象描述框架， 根据该框架，网络中存在汇聚节点、簇首节点、路由节点、探测节点、休眠节点 等不同角色，汇聚节点负责收集其它节点信息进行融合处理，处理后的数据由路 由节点到达簇头，这些节点的角色伴随着任务执行获得，在任务执行完毕时自动 放弃。另外在m a n i s hk o c h h a l 等人提出的抽象描述框架中，任务是指不同角色问 进行交互的集合，这些任务通过不同节点角色间计算、探测和通信被完成。 抽象任务图 抽象任务图是由a r n o lb a k s h i 1 3 】从传感器网络编程的角度出发提出的，是基 于一种宏编程( m a c r o p r o g r a m m i n g ) 模型一抽象任务图( a b s t r a c tt a s kg r a p h a t a g ) 的模式。抽象任务图是一系列抽象声明( a b s t r a c td e c l a r a t i o n ) 的集合，在 抽象声明中a m o lb a k s h i 定义了三种类型，分别是抽象任务、抽象数据和抽象通道。 4 第一章绪论 其中抽象任务被描述成了应用中的一种处理，通过目标平台编写的执行代码将于 每个任务进行关联。抽象数据代表抽象任务间交换的与应用相关的数据对象，抽 象通道为任务和数据间的输入和输出关系。为了便于理解，抽象声明中可以添加 注释以更好表明声明中的一些属性。另外，a m o lb a k s h i 的a t a g 模型是独立于网 络体系结构的，属于系统级的描述。 丽面丽秤丽赢d 堕巫画叵堕圜 务 据 道 图1 - 5 环境监测系统抽象任务图【1 3 】 图1 - 5 是根据抽象任务图产生的一个描述实例，图中描述了无线传感器网络 中一个周期性温度检测的任务。在1 5 中的环境监测系统中，每个传感器节点都配 备了温度传感器，若两相邻传感器采集的温度差值超过了规定范围，系统将对更 大的区域进行测量以确定是否有温度异常出现，若异常温度被正式则触发警报。 t e m p e r a t u r e 是从传感器得到的温度之表示抽象数据，l o c a la l a r m 和g l o b a la l a r m 分 别代指超过阈值的异常事件和区域异常事件，m o n i t o r 为抽象任务负责监测温度， 系统通过v e r i f y 监测分析更大区域内的温度值。 a m o lb a k s h i 所提出的抽象任务图更好地描述了无线传感器网络中的任务， 其所用的传统编程语言对于用户开发更是打开了方便之门，但由于其极度的抽象 性对于任务分配具有很大障碍，不适合对任务分配进行优化处理。 1 1 2 任务调度算法相关研究 任务一般指的是具有一定功能的实体，在调度中充当基本单位。一个任务一 般具有到达时间、运行时间、截止时间、到达频率等特点。对任务调度算法的评 价一般从调度成功率、调度长度、处理器空闲率、网络寿命等角度考虑，不过各 评价标准间存在互相制约的关系，任何一种调度算法都不可能充分兼顾全部的标 准。 目前已经提出的任务调度算法数目众多，可有多种分类方法，常见的分类方 法见表1 1 。 电子科技人学硕士学位论文 表1 1 任务调度算法分类 分类依据类别 根据所解决的问题性质静态调度雨i 动态调度 根据任务是否可被抢一叶抢占式调度和非抢to i 式调度 根据系统运行环境境单处理器实时调度和多处理器实时调度 根据调度器体系结构构集中式调度和分布式调皮 静态调度中任务的分配执行相对固定，且任务本身也具有一定规律性，调度 中甚至对任务的属性假定是预知的。调度中调度器脱机地工作，根据任务属性和 网络节点情况产生调度表格。任务到达时按照此表选择各自处理节点。动态调度 算法具有运行开销小的特点，但不灵活，不能适应多变的环境。动态调度相对于 静态而言，动态调度中任务在运行期间彳决定其执行节点，对于未到达的任务系 统一无所知，所以动态调度算法需要对变化的环境做出反应，因此，动态调度算 法较灵活，但其开销较大。 本文主要研究动无线传感器网络中任务动态调度算法，以下就当今静态任务 调度和动态任务调度研究现状分别加以说明。 1 1 2 1 任务静态调度算法 一般来说，多处理器任务静态调度分为静态的任务分配和处理器上任务静态 调度两个部分。处理器上的任务调度及单机调度，一般采用单机的静态调度算法 处理。此处主要介绍多处理器任务静态调度分配。 多处理器任务的静态任务调度一般应用在调度需求事先定义好的系统上，其 算法一般运行开销小，但缺乏灵活性 一般来说，任务的静态调度算法多从算法运行开销、通讯损耗、负载均衡， 资源利用率等多个角度考虑。算法通常将其中一个或多个方面作为目标函数，并 尽力对这个目标函数进行优化。相对任务动态调度算法，任务的静态调度算法相 对成熟，种类也较多。主要有：基于最优化思想算法、基于非指导性搜索算法、 基于启发搜索算法和基于图论的算法。以下将对这几种算法详加说明。 基于最优化思想的算法 基于最优化思想的算法一般从两个方面展开，方面寻找一个确实存在的可 行解方案；另一方面根据相应的目标函数，在可行的解空问中寻找最优解。例如 分值定界( b r a n c h a n d b o u n d ) 算法【l 。7 】属于第一方面的内容，另外在文献 1 8 $ 1 1 1 9 6 第一章绪论 中采用的则是根据解空间寻找最优解的方式。由于最优化思想的调度算法具有较 高复杂度，因此，随着时间的推移这方面的研究正在逐渐减少，人们的注意力开 始慢慢转向其他复杂度较小的方法进行研究。 基于非指导性搜索技术的算法 在最优化搜索过程中，非指导性搜索技术是比较常用的技术。它不仅被广泛 应用于各种最优化问题，而且在多处理器任务静态分配上得到了成功应用。其中， 最速下降算法、禁止搜索算法【2 0 】、模拟退火算法 2 1 , 2 2 】、阀值接受算法和遗传算 法【2 2 】均属于其经典算法。另外，在一些非指导性搜索算法中还使用了神经网络1 2 3 1 ， 和线性规划技术【1 9 】。 非指导性搜索技术的每一种算法几乎都是从一个初始分配方案开始。初始是 指将一组具有相关性的任务尽量分配到一个处理器中。初始方案只是一个可行解， 在以后的每一步迭代中，都将对这一初始方案进行调整。每一次迭代中的调整都 是根据网络具体情况将处理器上的某些任务迁移到不同的处理器上进行的，或者 根据任务的自身属性进行调整。每次迭代过程中，对于最终的调整结果需要对其 进行可调度性测试以检查其可行性。若调整后的可行性不满足要求则抛弃，保留 原来调度结果，若可行则保留调整后的调度结果，进入下次迭代。在非指导性搜 索算法中为了寻找到最优的任务调度方案，通常在目标函数中包含对任务截止期 的衡量。 基于启发式搜索的算法 启发式搜索的显著有点是避免了算法在目标函数优化上花费过多精力。基于 表处理( l i s t p r o c e s s i n g ) 的启发搜索算法和基于空闲方法( s l a c km e t h o d ) 的启发搜索 算法是启发式搜索算法中两类最具有代表性的算法。 绝大多数表处理的启发式搜索算法都是以优先级栈或一个或多个全局的优先 级表为基础的。任务的调度执行都是依据这些优先级表或优先级栈进行的。区别 各种表处理算法的关键在于用来构造优先级表和优先级栈的优先级函数有所不 同。其中，有的表调度算法 2 4 , 2 5 1 采取回溯策略，以便于对当前不可行的分配方案 进行处理，提高任务调度成功率；另外一些算法【2 6 】中允许算法中断，从而对算法 中参数进行优化调整。此外，大多数算法都采取了一定策略使问题规模进一步降 低，如预群集( p r e c l u s t e r i n g ) 技术。 空闲方法【2 7 】是启发式搜索算法的另一种具有代表性的算法，综合各种空闲方 法的启发式算法特点，可以得到空闲方法基本有两个目标，一是构造可行的分配 方案；二是尽可能少地使用网络资源。即空闲方法在可行解的约束条件下尽可能 7 电子科技人学硕十学位论文 少地占用处理器。一般空闲方法以构造可行分配方案为主要目标，任务图规约和 任务影射是其两个重要部分。任务图归约利用空闲值，使用路径群集策略简化任 务图复杂度。经过任务图规约处理后，系统将得到一系列的任务簇，这些任务簇 满足时限约束，作为任务影射的输入。在任务影射过程中，各任务簇被影射到合 适的处理器上。空闲方法极有可能使任务产生信息丢失或通信冲突的矛盾，因此， 它并不是最理性任务的静态调度方式。 基于图论的算法 在这类算法中，最常见的是基于网络流图州f g ) 的算法【l2 1 ，它将任务分配问 题等价成了著名的“最大网络流”问题。 1 1 。2 2 任务动态调度算法 静态调度算法要求任务属性相对固定，多处理器网络环境稳定。而在大多数 多处理器网络中，任务属性是动态多变的( 例如到达时间、执行能耗) ，网络环境 也是极易变化的，这时，静态调度算法便不再适用了，必须动态地对任务进行调 度分配，以适应多边的任务和网络。 经过不断研究，m o k 和d e t o u z e 2 8j 发现，多处理器动态调度是n p 难度的，且 任务动态调度不存在最优算法。近年来，对于多处理器的任务动态调度研究较多， 提出了各种动态调度算法，归纳来看各种动态调度算法基本上基于两类思想：一 类是基于计划的思想，另一类是基于最大努力的思想。 在基于计划的调度算法中，对于新到达任务的调度，调度器必须保证对于那 些已经保证了截止期的任务不产生影响。另外，基于计划的思想对于任务的调度 还要进行可调度性分析，只有满足要求的分析结果才被认为是可调度的，调度可 行，任务可以被接受，否则任务不可调度。 在基于最大努力思想的动态调度中，算法一般不进行可调度性分析，而是对 于新到达的任务尽可能的满足其截止时i b j 。例如，某些算法将任务的解释时间作 为调度的优先级，并根据优先级抢占处理器。此种方式保证了时间限制最为严格 的任务顺利执行，但对于其他时限限制不是那么严格的任务，由于优先级问题及 其可能被不断中断，得不到充分的执行时l 训，以致截止时间到来而被抛弃，任务 调度失败，这j 下是这种调度思想的致命缺陷。 另外根据所采取的具体方法，任务的动态调度算法还可分为基于单机经典调 度的算法、基于时间片的调度算法、基于合作式调度的调度算法、基于启发式搜 索算法和基丁任务并行性的算法等。以下将加以详细描述。 8 第一章绪论 基于单机经典调度的算法 此类算法将单机的动态调度算法进行了扩展，使其应用到多处理器网络环境 中。文献 2 9 e f t 将应用于单机的最早截止期优先算法( e a r l i e s td e a d l i n ef i r s t ，e d f ) 进行改进，使其应用在多处理器任务动态调度环境中。在文献 3 0 】中m d o m i n i c 等人提出了最小延迟优先算法( m l l f ) ，最小延迟优先算法中，首先按照任务的 截止时间和运行时间确定优先级，然后使排序完毕的任务队列进栈，每次为栈中 的前门个任务分配n 个处理器执行。m l l f 算法中截止期严格的任务总是具有较高 优先级，首先被调度。当在截止时间相同情况下，m l l f 算法使运行时间长的任务 具有较高的优先级。此种调度策略对于提高任务调度成功率具有明显效果。 基于时间片的算法 时间片的思想主要是指在任务具体执行时，将处理器可用时间划分为不等间 隔地时间段，每个任务使用处理器的最长时间段称为“时间片 。若任务在自己所 分得的时间段内未完成，则排入任务队列的尾部，等待下一个供它使用的时间片 到来。s k b a n m h 等人【3 1 】提出了一种用于共享式多处理器系统的动态调度算法 p f ( p f a i r ) 。该算法中的核心思想就是基于时间片的，算发中每一任务所拥有时间 片的大小与任务利用率有一定的正比关系。 基于合作式调度的算法 合作式调度算法通常应用在分布式任务调度系统中。处理器节点间的地位是 平等的，通常通过动态合作方式来完成单个或多个任务。根据合作方式的差异， 合作是调度算法有随即调度算法和非随机调度算法之分。 基于随即思想的调度算法中，当以处理器出现任务不可调度情况时，通常该 处理器在网络中随机地为不可调度任务的任务选择一个处理器节点，并将不可调 度任务迁移到所选择的处理器上。这种随即算法的优点在于大大减小了分布式调 度模式的通信损耗，加快了任务的调度速度，但由于其选则执行节点的随即性， 缺少可行性分析，可能会使某些任务一直在迁移，在截止时间到来前找不到合适 处理器而被抛弃，从而减小任务调度成功率。 相对随即调度算法，非随机调度算法对于任务的调度成功率有明显提高。这 是由于非随机调度中处理器将根据网络中其它处理器节点状态和任务本身属性， 有目的的选择处理器进行任务迁移，所以可以有效控制任务调度成功率。非随机 算法中，为了避免过多的通信损耗，网络中每一处理器节点将周期性地向其他处 理器节点发送本身的负载信息，每一处理器节点将维护一张包含其它节点负载情 况的表格，当任务需要迁移时，算发将根据此表选择目的处理器节点。但相比随 9 电子科技人学硕士学位论文 即算法，非随机的策略仍有较大的通信丌销，速度稍慢。 相比其它任务动态调度算法，基于合作是的模式中每一处理器都可作为调度 其使用，具有较强的灵活性。但合作式的思想使网络内不断有任务被迁移，增加 了任务动态调度的不可预测性，这对于本来预测性较差的动态调度无疑是雪上加 霜，将会使任务动态调度不可控。同时，大量的任务迁移带来了过多的通信损耗， 降低了任务调度成功率。 基于启发式搜索的算法 由于多处理器中任务动态调度不存在最有算法【28 】的思想被验证，人们开始将 注意力转移到启发式搜索领域，希望通过启发式搜索思想找到较优的动态调度结 果。基于启发式搜索思想的算法较多，经典的近视算法【3 2 】就属于启发式搜索算法， 由于近视算法的实用型，基于近视算法衍生出了许多的任务动态调度算法【3 3 】【3 4 】， 当然，这些衍生出的算法仍然属于启发式搜索的范畴。 著名的近视算法由k r i t h ir a m a m r i t h a m 等人【3 2 】提出，近视算法的提出确实地 解决了多处理器任务动态调度的问题，他在传统启发式搜索的基础上采取回溯策 略，限定了一次调度中被考虑的任务数，与传统启发式算法相比，将复杂度由d f 门21 降到了o ( 门) ( ，2 为系统中任务的数目) 。近视算法中根据动态到达任务具有的资源约 束进行可行性分析，若分析结果满足要求则有调度器产生调度方案，否则对任务 进行回溯处理。在选择回溯来扩充当前局部调度的任务时，仅考虑可行性检查窗 口中的任务，并从中选择一个目标函数值最优的加入到当前局部调度中。 以近视算法为基础，m a r a i 等人【3 3 j 又提出了实时多处理器系统任务的集成动 态调度方法。在这一一方法中使用了不精确计算保证硬、软任务的集成动态调度， 算发从实用性上保证了较高的任务动态调度成功率。 基于任务并行性的算法 在多处理器任务调度中，存在任务可以被并行执行的情况。根据这一特性人 们提出了并行的任务动态调度算法 3 4 , 3 5 】，其中文献 3 4 3 5 】以近视算法为基础，将 若干任务并行执行，提高了系统资源利用率，在一定程度上提高了任务调度成功 率。 1 2 本文主要工作 本文主要研究了基于蚁群算法的无线传感器网络中任务的动态调度，对算法 本身和任务的动态调度本文主要做了如下工作。 l o 第一章绪论 1 ) 蚁群算法改进 针对算法局部最优的局限性，本文提出了基于信息素动态扩散的改进策略， 使信息素不再局部不断积累，从而导致算法的局部寻优。另外针对无线传感器网 络能量受限的特点，引入信息熵对每一步调度的能耗均衡性进行衡量，并将其和 任务能耗引入算法启发因子，最终仿真结果表明无论在网络寿命还是任务调度成 功率上都优于原始蚁群算法。 2 ) 改进算法参数优化匹配 现今，由于对蚁群算法中p 、口、参数取值未有较好的数学模型可供参考， 而且参数p 、口、针对改进策略不同其最优组合也将不同。针对这一情况，对于 p 、认的最优匹配本文进行了大量数据搜索工作，最终找到了改进算法的参数 最优匹配。 3 ) 任务调度动态调度框架 任务动态调度采用集中式调度策略，并参照任务动态调度的经典算法一近视 算法思想，采取任务回溯策略，建立待转发任务列表，当新任务到来时将带转发 任务列表中的任务回溯，通过算法重新优化调度。另外节点周期性将自身情况反 馈到调度器。 4 ) 任务动态迁移策略 由于网络能量受限，在后期由于节点能量不足，易出现任务未完成而执行节 点能量耗尽的现象。针对此种情况，本文提出任务的动态迁移策略。经过仿真试 验，迁移策略有效提高了任务调度成功率。 5 ) 针对互相联系任务的c g d c 算法 由于任务间的互相联系和数据依赖使得互相联系的任务处理较复杂，针对此 神情况，本文在图解重构的机群系统静态调度算法基础上，提出了c g d c 算法， 对互相联系的任务首先经过c g d c 算法处理，使其总体能耗降低，联系度减小便 于处理后交由调度算法调度。仿真试验表明c g d c 算法在任务动态调度中可以取 得较好效果。 以上五点为本文主要工作重点。其中蚁群算法改进又是整个文章的核心重点， 任务的动态调度都是围绕其展开的。 1 3 论文组织结构 论文主要分为七章 电子科技人学硕士学位论文 第一章为绪论部分。主要介绍了任务无线传感器网络及任务调度的研究背景、 现状，本文的工作和结构。 第二章为基本蚁群算法及其发展。此章中对贯穿任务调度的核心算法蚁群算 法做了详细描述，设计了算法产生、原理及其发展过程。 第三章为基本蚁群算法改进及独立任务动态调度。本章节是文章重点，详细 阐述了对基本蚁群算法的改进策略；提出了集中式的任务动态调度器，将改进蚁 群算法置于调度器中对独立任务进行了动态调度；另外，对改进蚁群算法进行了 参数优化和其他仿真试验。 第四章为互相联系任务调度。针对互相联系的任务，本章在图解重构的机群 系统静态调度算法基础上进行改进，提出了c g d c 算法，较少了总体任务的能耗 和数据传输量。 第五章为结论和展望。本章对论文所做工作进行了总结，并对未来作了展望。 1 2 第二章基本蚁群算法及其发展 第二章基本蚁群算法及其发展 2 1 基本蚁群算法的数学模型 蚁群算法【3 5 】最早是由意大利生物学家d o r i g om 于2 0 世纪9 0 年代初期提出的， 是一种模拟了昆虫王国中蚂蚁群体智能行为的仿生优化算法。蚁群算法的主要主 要具有正反馈、分布式计算、易与其他方法相结合特点。其中正反馈过程使得该 方法能很快发现较优解；分布式计算易于并行实现。 蚁群算法最初用于解决旅行商问题。自从在著名的旅行商问题【3 6 】和工件排序 问题【3 7 1 上取得成效以来，已经陆续渗透到其他领域中，如图着色问题【3 8 】、二次分 配问题( q a p ) 3 9 】、车辆调度问题【4 0 】等。虽然对蚁群算法研究的时间不长，但是这 些初步研究已显示出蚁群算法在求解复杂优化问题( 特别是离散优化问题) 方面 的优越性，表明它是一种很有发展前景的方法。 为了说明蚁群算法模型，首先引入旅行商( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 问题。t s p 具有广泛的代表意义和应用前景，许多问题均可抽象为t s p 的求解。 t s p 问题就是指给定n 个城市和两两城市之间的距离，要求确定一条经过各 城市当且仅当一次的最短路线。设m 是蚁群中蚂蚁的总数目，用吐，表示城市f 和 城市，之间的距离，r ，i ( t ) 表示，时刻残留在城市f 、，连线上的信息量。初始时 刻t = o 时，将m 只蚂蚁随机放置到n 个城市中的m 个城市上，各条路径上的信息 素量相等，设t i ，( 0 ) = c o n s t ，蚂蚁k ( k = l ，2 ，3 ，m ) 在运动过程中根据各条路径上 的信息素量决定转移方向。这里用禁忌表( t a b ul i s t ) ( k = l ，2 ，3 ，m ) 来记录蚂蚁 k 当前所走过的城市，集合随着禁忌表t a b 材k 进化过程作动态调整。在搜索过程 中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在f 时刻，蚂蚁k 在城市f 选择城市，的转移概率p ? ( f ) 为： j 0 ( f ) 】口( f ) 】r ， 露： 夏三i 赫 j 鲫“洲鲥 1 ) 【 a ， 。t h e r w i s p 其中，a l l o w e d 。= c t a b u 女 表示蚂蚁k 下一步允许选择的城市。口为信息 启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在 u 了科技大学硕j ：学位论义 蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径， 蚂蚁之间协作性越强；为期望启发式因子，表示能见度的相对重要性，反映了 蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状 态转移概率越接近于贪心规则；编心) 为启发函数，其表达式如下： 7 7 ，) = 1 d u ( 2 2 ) 式中，d j j 是相邻两城市i 和之问的距离。对蚂蚁k 而言，d 口越小，则7 7 ，( ，) 越大，磁( t ) 也就越大。显然，该启发函数表示蚂蚁从城市i 转移到城市的期望 程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步 或者完成对所有即个城市的遍历( 也即一个循环结束) 后，要对残留信息进行更 新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同 时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，0 + 刀) 时 刻在路径( f ，) 上的信息量可按如下规则进行调整： t i j ( ，+ 胛) = ( 1 一p ) d r 盯( f ) + 丁，( f ) ( 2 3 ) a r f ( ，) = 勺k ( f ) ( 2 4 ) 式中，pc o ，1 ) 表示信息挥发系数，则( 1 一户) 表示信息残留因子，为了防止信 息的无限积累，p 的取值范围为：pc 【o ，1 ) ；f ，( f ) 表示本次循环中路径( f ，) 的 信息素量的增量，初始时刻f 。( o ) = 0 ，a 2 j k ( f ) 表示第k 只蚂蚁在本次循环中留 在路径( f ，) 上的信息量。 根据信息素更新策略的不同，d o r i g om 提出了三种不同的基本蚁群算法模型， 分别称之为a n t c y c l e 模型、a n t q u a n t i t y 模型、a n t d e n s it y 模型。三种模型 的差别仅在于a v , j 七( f ) 的表达式不同。 在a n t c y c l e 系统模型中 r 、 ；l 等，如果第七只蚂蚁在本次循环中经过路径( ，)、 f ：( f ) = 厶 ( 2 - 5 ) 。 l0 ， 否则 在a n t q u a n t i t 系统模型中 1 4 第二章基本蚁群算法及其发展 。l 羊，如果第七只蚂蚁在本次循环中经过路径( f ，_ ，) a v i l i ( f ) = 办 ( 2 - 6 ) 【0 ， 否则 式中，q 为信息素强度。从上式可见，蚁量系统中，一只蚂蚁在路径( f ，) 上 释放的信息素量为q 吐，因此较短路径对蚂蚁更有吸引力。 在a n t d e n s i t y 系统模型中 蜘= 舻嬲职贼林溯种鲋路鬻 ( 2 - 7 ) 可见一只蚂蚁从i 向_ ，移动的过程中路径( f ，) 上信息轨迹强度与以无关。 其中，厶是第k 只蚂蚁在本次循环中所走的路径长度。与a n t q u a n t i t 和 a n t d e n s i t y 系统不同的是，a n t - c y c l e 系统是在蚂蚁已建立了完整的轨迹后再释 放信息素，利用的是整体信息；而前面两者则是在建立方案的同时释放信息素， 利用的是局部信息。在求解t s p 问题时，a n t - c y c l e 算法模型明显优于其他两种 算法模型，因此通常采用式( 2 5 ) 作为蚁群算法的基本模型。 2 2 基本蚁群算法的实现 以t s p 为例，基本蚁群算法实现的程序结构流程f 4 1 1 如图2 2 所示。 uf 科技大学硕 二学位论文 2 3 蚁群算法研究现状 虽然蚁群算法具有正反馈等多种优点，但其自身仍具有需要较长的搜索时间 以及容易出现停滞现象等不足的特点，这些缺点已经引起了许多研究者的注意， 提出了若干改进的蚂蚁算法，如m d o r i g o 提出的a n t qs y s t e m ( a c s ) 4 2 1 ，s t u t z l e 等人提出的最大最小蚂蚁系统( m m a s ) 【4 3 】以及b b u l l n h e i m e r 等人提出的基于排序 的蚂蚁系统【4 7 】等。下而就这些有代表性的改进算法进行讨论。 2 3 1a n t - os y s t e m 算法 为了避免出现停滞现象，m d o r i