（信号与信息处理专业论文）基于混合遗传算法的flexray总线静态段实时调度研究.pdf

一一一j at h e s i sf o rt h ed e g r e eo fm a s t e ri ns i g n a la n di n f o r m a t i o np r o c e s s i n g r e s e a r c ho nr e a l - t i m es c h e d u l i n gf o rs t a t i c s e g m e n t i nf l e x r a ys y s t e m sb a s e do n h y b r i d g e n e t i ca l g o r i t h m b y y i nx i a o n a s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rd i n gs h a n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 9 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名 签字日期 ： 孕施1 ：伽”乡 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：尹吨呷 导师签名：丁如 签字e l期 ：气n ，7 7 ， 签字e l 期：文阀7 7 厂 j - 东北大学硕士学位论文 摘要 基于混合遗传算法的f l e x r a y 总线静态段实时调度研究 摘要 随着“线控 ( x - b y - w i r e ) 系统的发展，要求车载网络具有传输速度高、可靠性好 和支持分布式控制的性能。目前车载网络大多使用的是基于事件触发的c a n 总线，但 由于c a n 总线的最高速率不超过i m b s ，带宽利用率较低，很难在有大数据量交换要 求的应用中取得优势，它无法提供下一代线控系统应用所需的容错功能或带宽。因此， 由b m w 、d a i m l e r - c h r y s l e r 、f r e e s c a l e 、b o s c h 和p h i l i p s 等公司组成的f l e x r a y 联盟建 立了f l e x r a y 系统标准。新一代汽车总线f l e x r a y 具有数据传输速率高、可靠性高和实 时性好等优点，从而比以往的汽车协议具有更大的优势，主要应用在汽车安全系统，例 如刹车或转向系统。 f l e x r a y 协议由静态段和动态段组成，f l e x r a y 协议的静态段基于时分多址访问 ( t i m ed i v i s i o nm u l t i p l ea c c e s s ，t d m a ) 技术，传输的是周期性消息，而动态段采用的 是柔性时分多址访问( f l e x i b l et d m a ，f t d m a ) 技术，传输非周期性消息。f l e x r a y 静 态段的任务调度以及创建静态调度表是设计高效f l e x r a y 系统的关键，本文主要针对 f l e x r a y 静态段的实时调度进行研究。 本文在分析f l e x r a y 协议及其实现方式的基础上，设计了f l e x r a y 静态段实时调度 的应用模型，并定义了性能指标带宽利用率，对静态段实时调度的约束问题进行了 详细分析，重点分析了传输路径的响应时间约束，保证路径传输在截止期限之前传输完 毕。f l e x r a y 静态段实时调度采用静态调度策略生成静态调度表，属于n p 完全问题， 本文首先采用装箱算法生成静态调度表，接着使用遗传算法对其求解，由于遗传算法存 在早收敛、局部搜索能力弱等缺点，最后本文将装箱算法与遗传算法相结合形成混合遗 传算法，从而能更快的找到最优近似解。本文最后将所提出的调度算法应用到车辆自适 应巡航控制系统、汽车电动助力转向、汽车牵引力控制等汽车安全系统中，从而验证了 算法的可行性。 关键词：f l e x r a y 总线；静态段；混合遗传算法；实时调度 一i i 一 r e s e a r c ho nr e a l - t i m es c h e d u l i n gf o rs t a t i cs e g m e n ti nf l e x r a y s y s t e m sb a s e do nh y b r i dg e n e t i ca l g o r i t h m a b s t r a c t w i t ht h ed e v e l o p m e n to fx - b y - w ns y s t e m ，h i g hs p e e dt r a n s m i s s i o n ，r e l i a b i l i t ya n d s u p p o r t i n gd i s t r i b u t e dc o n t r o l l i n ga l ea s k e d f o ri n - v e h i c l en e t w o r k m o s to ft h ec u r r e n t i n v e h i c l en e t w o r k sa r eb a s e do nt h ec a nb u sw h i c hi st r i g g e r e db ye v e n t s s i n c et h ec a n d o e sn o te x c e e d1m b sm a x i m u ms p e e da n di t sb a n d w i d t hu t i l i z a t i o ni sl o w , i ti sd i f f i c u l tf o r c a nt oo b t a i nt h ea d v a n t a g e si nal a r g ea m o u n to fd a t as w i t c h i n ga p p l i c a t i o n t h u sc a n i s u n a b l et om e e tt h er e q u i r e m e n to ft h ef a u l t - t o l e r a n c ea n dh i g hb a n d w i d t hi nn e x tg e n e r a t i o n x - b y - w i r es y s t e ma p p l i c a t i o n s t h e r e f o r e ，b m w , d a i m l e r - c h r y s l e r , f r e e s c a l e ，b o s c ha n d p h i l i p ss e tu pf l e x r a yu n i o nt ob u i l dt h ef l e x r a ys t a n d a r dp r o t o c 0 1 f l e x r a y , t h en e w g e n e r a t i o nv e h i c l eb u s ，h a st h ea d v a n t a g e so fh i g hs p e e d ，d e p e n d a b i l i t ya n d r e a l - t i m e t r a n s m i s s i o n t h ef l e x r a yp r o t o c o lo f f e r sv a r i o u sb e n e f i t so v e rt h ee x i s t i n gi n - v e h i c l e n e t w o r k a n di tc a nb es u c c e s s f u l l yu s e df o rs a f e t y - c r i t i c a la u t o m o t i v ea p p l i c a t i o n ss u c h 嬲 n e t w o r k - b a s e db r a k i n go rs t e e r i n gs y s t e m s f l e x r a yp r o t o c o li sc o n s t i t u t e db yt h es t a t i cs e g m e n ta n dt h ed y n a m i cs e g m e n t ，w h i l et h e s t a t i cs e g m e n ti sb a s e do nt i m ed i v i s i o nm u l t i p l ea c c e s s ( t d m a ) t oa c h i e v ed e t e r m i n i s t i c b e h a v i o r , t h ed y n a m i cs e g m e n ta d o p t ss 0 一c a l l e df l e x i b l et d m a ( f t d m a ) t oa c h i e v e f l e x i b l ea n de f f i c i e n tu s eo ft h en e t w o r k t h e r e f o r e ，s c h e d u l i n go ft h es t a t i cs e g m e n ta n d c r e a t i n gt h es t a t i cs c h e d u l i n gt a b l ea r ec r i t i c a lf o ra ne f f i c i e n tf l e x r a y - b a s e ds y s t e md e s i g n t h i sp a p e rm a i n l yf o c u s e so nt h er e a l t i m i n gs c h e d u l i n gf o rs t a t i cs e g m e n ti nt h ef l e x r a y s y s t e m s b a s e do nt h ea n a l y s i so ff l e x r a yp r o t o c o la n di t si m p l e m e n t a t i o n ，t h ep a p e rd e s i g n e st h e a p p l i c a t i o nm o d e lf o rt h ef l e x r a ys t a t i cs e g m e n ts c h e d u l i n g ，a n dt h i s t h e s i sd e f i n e st h e p e r f o r m a n c e m e t r i c s - - b a n d w i d t hu t i l i z a t i o n ， a n a l y z e s t h es t a t i cr e a l _ t i m e s c h e d u l i n g c o n s t r a i n t si nd e t a i l ，f o c u s i n go nt h er e s p o n s et i m ec o n s t r a i n t st oe n s u r et h a tt h em e s s a g e sc a n b es u c c e s s f u l l yt r a n s m i t t e db e f o r et h e i rd e a d l i n e s s c h e d u l i n gf o rs t a t i cs e g m e n ti nf l e x r a y s y s t e m si sd e s i g n e dt og e n e r a t es t a t i cs c h e d u l i n gt a b l eb ys t a t i cs c h e d u l i n gs t r a t e g y t h i s p r o b l e mb e l o n g s t on p c o m p l e t ep r o b l e m ，w h i c hi s f i r s t l y s o l v e db yt h eb i n 。p a c k i n g a l g o r i t h m s e c o n d l y , g e n e t i ca l g o r i t h m i su s e dt or e s o l v et h i sp r o b l e m ，b u ts o m e d i s a d v a n t a g e ss u c ha se a r l yc o n v e r g e n c e ，p o o rp a r t i a ls e a r c h i n gc a p a b i l i t ye x i s ti ng e n e t i c i i i 东北大学硕士学位论文a b s t r a c t a l g o r i t h m t h i r d l y , t h i sa r t i c l ec o m b i n e st h et w oa l g o r i t h m st of o r mt h eh y b r i dg e n e t i c a l g o r i t h mt oq u i c k l yf i n do u tt h eo p t i m a la p p r o x i m a t es o l u t i o n a tt h ee n do ft h ea r t i c l e , e x p e r i m e n t sa r em a d eb yas e to fa u t o m o t i v es a f e t ys y s t e mi n c l u d i n ga d a p t i v ec r u i s e c o n t r o l ，e l e c t r i cp o w e rs t e e r i n ga n dt r a c t i o nc o n t r o ls y s t e m t h e nt h ee f f e c t i v e n e s so ft h e p r o p o s e dm e t h o di sv e r i f i e d k e y w o r d s ：f l e x r a yb u s ；s t a t i cs e g m e n t ；h ：y b r i dg e n e t i ca l g o r i t h m ；r e a l t i m es c h e d u l i n g i v 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 研究背景与意义1 1 1 1 研究背景l 1 1 2 研究意义2 1 2 实时调度的必要性2 1 3 研究概况。3 1 3 1f l e x r a y 协议的研究现状3 1 3 2 任务调度算法的研究现状5 1 4 论文结构及创新点7 第2 章f l e x r a y 协议的分析9 2 1f l e x r a y 协议的特性9 2 2f l e x r a y 协议的网络连接。1 0 2 2 1f l e x r a y 协议的网络拓扑结构1 0 2 2 2f l e x r a y 协议的节点结构1 1 2 3f l e x r a y 的网络通信协议1 2 2 3 1f l e x r a y 协议的帧格式1 2 2 3 2f l e x r a y 协议的时钟同步1 5 2 3 3f l e x r a y 协议的群组启动15 2 4f l e x r a y 的访问机制1 7 2 4 1f l e x r a y 的通信周期1 7 2 4 2 两种触发机制的比较1 7 一v 一 东北大学硕士学位论文 目录 2 4 3f l e x r a y 静态段的驱动机制1 9 2 4 4f l e x r a y 动态段的驱动机制1 9 2 5 本章小结2 0 第3 章f l e x r a y 静态段实时调度的理论研究2 1 3 1 实时调度技术2 l 3 2f l e x r a y 静态段实时调度分析2 2 3 2 1 问题阐述2 2 3 2 2 应用模型及性能指标2 4 3 2 3 静态调度表参数设置。2 7 3 2 4 实时调度的约束2 7 3 3n p 完全问题3 0 3 4 本章小结3 0 第4 章f l e x r a y 静态段实时调度算法研究3 1 4 1 装箱算法在f l e x r a y 静态段实时调度中的应用3 l 4 1 1 经典装箱问题一31 4 1 2 经典装箱问题的算法分析3 l 4 1 3 任务的节点分配原则。3 4 4 1 4 算法的应用及时间复杂度分析3 4 4 2 遗传算法在f l e x r a y 静态段实时调度中的应用3 5 4 2 1 遗传算法的简介3 5 4 2 2 遗传算法的具体实现4 4 4 3 混合遗传算法在f l e x r a y 静态段实时调度中的应用4 8 4 4 本章小结。5 0 第5 章算法在汽车安全系统中的验证分析5 l 5 1 汽车安全系统介绍5 l 5 2 参数的初始设置5 3 5 - 3 算法验证结果及分析5 3 一v i 东北大学硕士学位论文 目录 5 4 本章小结5 8 第6 章结论与展望5 9 6 0l 结论5 9 6 2 展望6 0 参考文献6 l 致谢6 5 作者攻读硕士学位期间发表的论文6 7 一v i i ， 东北大学硕士学位论文笫1 章绪论 1 1 研究背景与意义 第1 章绪论 1 1 1 研究背景 随着微控制器在汽车控制领域上的广泛应用，汽车电子化程度越来越高。为减少成 本和简化线路，各汽车制造商纷纷采用各种总线控制技术。总线控制技术引入到汽车驾 驶上，就称为电控驾驶( d r i v e - b y - w i r e ) ，引入到制动上就产生了电控刹车 ( b r a k e b y - w i r e ) ，引入到转向控制上就有电控转向( s t e e r i n g - b y w i r e ) ，因此统称为线 控技术【l 】( x - b y - w i r e ) 。线控技术就是由电信号实现传递控制，而不是通过机械连接装 置来操作的。线控技术是在控制单元和执行器之间用电子装置取代传统的机械连接装置 或液压连接装置，由电线取代机械传动部件，取消了机械结构，赋予汽车设计新的空间。 美国汽车工程师协会( s a e ) 车辆网络委员会根据标准s a ej 2 0 5 7 将汽车电子技术 所使用的总线网络技术大概分为三类：a 类，b 类和c 类【2 ，3 1 ，如图1 1 所示。a 类：用 于传感器、执行器的通讯总线，代表的有l i n 总线，一般通讯速率在1 k b p s 一1 0 k b p s 属于低速总线。b 类：用于控制单元间的通讯总线，代表的有c a n 、j 1 8 5 0 ，一般通讯 速率在1 0 k b p s - 2 5 0 k b p s 属于中速总线。c 类：用于高速、实时、大数据量传输设备间 的通讯总线，代表的有高速c a n 、f l e x r a y 、m o s t 、i b d 1 3 9 4 ，一般通讯速率在5 0 0 k b p s 以上，属于高速总线。一般来讲，l i n 、c a n 、j 1 8 5 0 总线用于车身系统，5 0 0 k b p s 的 c a n 总线用于动力系统和安全系统，f l e x r a y 用于安全系统和主动悬架，m o s t 和 i b d 1 3 9 4 用于多媒体系统。 目前用于汽车安全系统的主要有c 类标准中的高速c a n 总线和f l e x r a y 总线。欧 洲的汽车制造商基本上采用高速c a n 总线标准i s 0 1 1 8 9 8 ，总线传输速率通常在1 2 5 k b p s 1 m b p s 之间。据s t r a t e g y a n a l y t i c s 公司统计，2 0 0 1 年用在汽车上的c a n 节点数目 超过1 亿个【2 1 。然而，作为一种事件驱动型总线，传统的c a n 总线具有如下缺点：网 络中节点缺少同步机制，消息的调度不可管理与预测，不适合于实时系统的需要；网络 资源利用率低，很难在有大数据量交换要求的应用中取得优势；无法提供下一代线控系 统应用所需的容错功能【4 1 。因为x - b y - w i r e 系统实时性和可靠性要求都很高，必须采用 时间触发的通信协议，f l e x r a y 联盟于2 0 0 0 年提出了f l e x r a y 协议。 f l e x r a y 是功能强大的通信网络协议，它是基于时分多址访问方式的确定性访问方 式，具有容错功能及确定的通信消息传输时间，同时支持事件触发与时间触发通信，具 备高速率通信能力。f l e x r a y 是下一代车载网络标准，可以有效管理多重安全和舒适功 能。f l e x r a y 以其确定的网络通讯、高速的数据传输及强大的容错功能，必成为将来汽 一l 一 东北大学硕士学位论文第1 章绪论 车上的底盘系统、动力系统及线控系统的电子控制单元通讯新的标准。为了更好地应用 f l e x r a y ，在设计初期需要对消息的实时性及其影响因素进行分析，目前，f l e x r a y 应用 中还有下列问题需要开始进一步研究： ( 1 ) 周期性消息的调度：由于周期性消息一般传输的是传感器的传感采样数据和 控制器计算得到的控制指令，其对网络控制系统的稳定性有决定性影响，所以必须综合 分析控制系统性能对周期性消息进行合理调度规划。在f l c x r a y 系统中，周期性消息是 在静态段传输的，通过对f l e x r a y 通信周期及其调度机制的综合分析，为了有效合理的 调度总线控制环中周期性消息的传输，满足稳定性要求，必须解决以下问题：确定系统 中任务所属节点的分配；确定各节点中任务的启动时间；确定总线中各个消息的传输起 始时刻。 ( 2 ) 可调度性分析：为了使网络控制系统中所有的消息传输都满足其时间要求， 必须在系统运行前对所构成的调度进行可调度分析。可调度分析主要分为网络资源利用 率可调度分析和响应时间可调度分析，前者主要适用于在线可调度分析，而后者主要适 用于离线可调度分析。 本文中主要研究周期性消息在f l e x r a y 总线中的调度及其可调度分析，周期性消息 调度采用的是静态调度法，所以使用响应时间的可调度性分析。 1 1 2 研究意义 目前，随着线控系统对车载总线的需求越来越高，越来越多的电子控制单元取代机 械部件，广泛应用于汽车，要求在网络上传输的信息量将会越来越大，这为汽车的发展 趋势一更加安全、可靠、舒适奠定了基础，现代豪华汽车中的电子控制单元多达7 0 个，它们之间相互传输2 5 0 0 个信号【5 6 】。随着更多的电子控制单元被采用和控制要求的 提高，对电控单元的通信提出了更高的要求，特别是一些与安全相关的信息要求绝对的 实时、可靠，如果一个节点有连续快变的消息或记录需要显示时，数据会有延迟时间不 确定的可能，会造成系统的不稳定和增加控制的难度。控制单元的指令发出去之后必须 保证在一定时间内得到响应，否则就有可能发生重大事故，所以，保证汽车的行驶安全 是至关重要的，保证总线的各个任务得到实时调度是很有重要意义的。 1 2 实时调度的必要性 给定一组实时任务和系统资源，确定每个任务何时何地执行的整个过程就是调度。 调度的实质是资源的分配，在非实时系统中，调度的主要目的是减小系统平均响应时间， 或优化某一指标，而实时调度的目的则是要尽可能地保证每个任务满足它们的时间约 束，及时对外部请求做出响应，为了精确管理“时间”资源，以达到实时性和可预测性 要求，并能够满足实时系统的新要求，需要实时调度理论对任务进行调度和可调度分析。 一2 一 东北大学硕士学位论文 第1 章绪论 f l e x r a y 车载网络已经开始广泛应用到汽车工业中实时分布式系统中，实时系统中， 实时性是重要研究问题之一。图1 1 中( a ) 表示的是自适应巡航控制系统模型，( b ) 是 该模型对应的任务关系图，自适应巡航控制系统对车辆前方或后方车辆或物体进行检 测，使车辆与它们保持安全距离。以t 8 一t l o t l i t 1 4 为例，就是通过检测目标车辆的 距离与速度来促使车辆减速，这个传输路径必须在周期时间2 m s 内传输完毕，否则就会 出现车辆碰撞。第五章将使用该模型以及汽车电动助力转向系统模型、汽车牵引力控制 系统模型对本文的调度算法进行验证分析。 ( a ) ( b ) 图i i 自适应巡航控制系统模型及其对应的任务关系图 f i g 1 it h ea d a p t i v ec r u i s ec o n t r o la p p l i c a t i o na n dt h ec o r r e s p o n d i n gt a s kr e l a t i o ng r a p h 实时系统的基本问题就是要保证系统中的任务满足其时间要求，从而保证系统的实 时性，所谓的实时性就是要保证系统的行为满足一定的时限要求。汽车的实时系统有多 种形式，从简化的指令控制到复杂的控制系统，这些多样化的系统有个共同特点和要求 就是系统中的任务不但执行结果要正确，而且它们必须在一定的时问约束内完成。如何 使任务集内各任务满足各自的实时性，使系统得以高效率地工作的任务调度算法一直是 实时系统领域内研究的焦点。 1 3 研究概况 1 3 1f l e x r a y 协议的研究现状 为了满足未来的车内通信需求，b m w 、d a i m l e r - c h r y s l e r 、f r e e s c a l e 、b o s c h 和p h i l i p s 等公司于2 0 0 0 年组成了f l e x r a y 联盟【7 】，目前几乎全部的知名汽车及汽车零部件企业都 加入其中，它们共同致力于开发能够满足未来车内通信需求的通信系统规范 一1 e x r a y 协议。目前f l e x r a y 协会拥有成员1 0 0 多个，其中，来自汽车行业的厂商 包括宝马、d a i m l e r - c h r y s l e r 、通用、m o t o r s 、大众、本田和丰田等，而来自芯片和系统 一3 一 东北大学硕士学位论文第1 章绪论 领域的公司有b o s c h 、摩托罗拉、飞利浦、a t m e l 、英飞凌和富士通等。 从2 0 0 2 年发布的v 0 4 3 协议规范到2 0 0 5 年的v 2 1 协议规范，f l e x r a y 联盟共发 布多达7 个版本。2 0 0 5 年1 0 月，p h i l i p 推出了全球第一个f l e x r a y 系统解决方案，包括 一个收发器和一个携带嵌入式f l e x r a y2 1 版本通讯控制器且基于a r m 的微控制器。 2 0 0 6 年1 月，飞利浦半导体公司推出了面向主动安全系统的f l e x r a y2 1 系统解决方案。 该解决方案包括两个主要部分：t j a l 0 8 0 收发器和包含一个a r m 9 微控制器并且完整集 成f l e x r a y 2 1 版本的s j a 2 5 1 0 通讯控制器。2 0 0 6 年底，德国宝马公司展示了首个f l e x r a y 产品级应用，将下一代车载网络f l e x r a y 应用于新款车型x 5 中，通过利用悬挂系统可 实现4 轮微操控，之所以在悬挂系统中采用f l e x r a y 系统，主要是它的通信速度快，且 可以使用时间触发方式，这个方式很难发生数据通信延迟现象。此外，f l e x r a y 的评估 套件也已经推出【8 】。相信在不久的将来，f l e x r a y 必定成为新一代车载网络的新标准。 作为全球车内网络的领先者，飞利浦的t j a l 0 8 0 和s j a 2 5 1 0 器件已经拥有几项领 先的成绩。t j a l 0 8 0 是市场上第一个基于最新的2 1 标准的f l e x r a y 器件，也是市场上 惟一能够在节点和主动式星形模式下运行的器件，使得同一设备能够用于所有的网络连 接上，从而减少了认证的工作量并简化了元件管理。 在f l e x r a y 实时性研究方面，国内外已经做了一些研究： 在 9 中，对f l e x r a y 的静态段和动态段的任务传输进行了实时性分析，但文中重点 研究了动态段的实时任务调度及最坏响应时间的分析策略，并给出了启发式的调度方 法，对静态段的研究较少。 1 0 q b 通过分析f l e x r a y 静态段消息帧的格式和实际传输规则，给出了计算消息帧 长度的实际方法，同时也介绍了通信周期中静态时槽的确定方法，但对消息的调度问题 并没有研究。 1 l 】对f l e x r a y 静态段的消息调度进行了分析研究，主要针对静态段的消息封装成 帧的方法及帧传输进行了研究，并分别分析了消息调度时无抖动和有抖动的情况，从而 研究了降低消息调度中抖动的策略，但并没有使用优化算法来优化消息调度。 1 2 】中使用遗传算法实现f l e x r a y 静态段的调度，但遗传算法在生成个体时随机性 太强，算法执行时间较长，并f 1 1 2 q b 对消息帧约束考虑的不够全面，没有顾及消息的 周期。本文在研究了f l e x r a y 协议及静态段消息传输特点的基础上，建立了静态段调度 的应用模型，在 1 2 】的基础上，使用装箱算法对基本遗传算法中的个体进行优化，并在 传统遗传算子的基础上设计适应本问题的遗传算子，形成基于装箱算法的混合遗传算法 实现静态段消息的实时调度。 一4 一 东北大学硕士学位论文第1 章绪论 1 3 2 任务调度算法的研究现状 任务调度算法大致可以分成两类：静态调度算法和动态调度算法。静态调度是指在 调度之前，了解了全部的调度所需信息，调度策略在任务执行之前已经确定，属于离线 调度模式。动态调度可以进一步划分为在线模式和批模式：对于在线模式，一旦任务到 达调度器，立即进行调度；对于批模式，当到达调度器的任务累积到一定数量或某个调 度事件发生后，再进行调度，所以在这种情况下，可以收集到足够多的任务和资源信息， 进行综合考虑，制定出合适的调度算、法【1 3 j 。 任务调度算法除了使用经典的启发式算法外，还引进了一些智能优化算法如模拟退 火算法、遗传算法、蚁群算法等，由于它们都是模拟自然现象或过程而发展起来的，并 且具有适应高度并行与自组织、自适应、自学习等特征，这些方法通过“拟物 与“仿 生 以使问题得到结果，为复杂问题提供了新的契机【1 4 1 5 】。下面简单介绍一下几种智能 优化算法： ( 1 ) 模拟退火算法 模拟退火算法f 1 6 】( s a ，s i m u l a t e d a n n e a l i n g ) 是1 9 5 3 年由m e t r o p o l i s 等人提的一种 简单算法，k i r k p a t r i c k 于1 9 8 3 年将其用于组合优化。它的出发点是基于模拟物理系统 中结晶退火过程与一般组合优化问题之间的相似性，采用随机搜索迭代过程求最优解。 模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中 随机寻找目标函数的全局最优解。 模拟退火是一个强大的解决组合最优化问题的通用方法，目前大量基于模拟退火的 算法专门用来解决非线性规划问题。该方法对目标函数无特殊要求，它是一个随机算法， 以概率1 渐近收敛于全局最优解，此解与初始可行解基本无关。尽管模拟退火结构概念 上简单直接，通用易实现，但是基于模拟退火的成功算法设计要求大量的工程判断，其 参数的选取比较复杂，为了使最终解尽可能接近全局最优，算法通常要求较高的初温、 较慢的降温速率、较低的终止温度以及温度下足够多次的抽样，模拟退火得到的最后解 质量和计算收敛速度依赖于退火方案的选取，若选择不当，则需要大量的随机迭代，计 算量大，并且得到的解与最优解相差甚远。 ( 2 ) 蚁群算法 蚁群算澍1 7 ，1 8 1 ( a n ta l g o r i t h m ) 是c o l o m i 和d o r i g o 等于2 0 世纪9 0 年代对蚁群行 为的研究受启发而提出的，是一种仿生类优化算法。蚂蚁在行进的途中会根据信息素的 浓度选择路径，即路径上的信息素浓度越大，则蚂蚁选择该路径的概率也就越高。信息 一5 一 东北大学硕士学位论文第1 章绪论 素会随时间的推移而挥发，同时蚂蚁在行进的过程中也会不断地分泌新的信息素，蚂蚁 很少选择的路径上的信息素浓度会越来越低，而蚂蚁经常选择的路径上的信息素浓度则 越来越高，并指导蚂蚁搜索到一条从蚁穴到食物源的最短路径。 研究表明，将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度， 从而改进算法的性能，但这种搜索方式一般需要较长的搜索时间，容易出现停滞现象， 即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜 索，即使早熟收敛行为更容易发生，不利于发现更好的解。 ( 3 ) 遗传算法 遗传算法【1 9 2 0 1 ( g e n e t i ca l g o r i t h m s ，g a ) 最早是由美国m i c h i g a n 大学j h h o l l a n d 教授在1 9 7 5 年提出来的，起源于6 0 年代对自然和人工自适应系统的研究，是一种建立 在自然选择原理和自然遗传机制上的新型优化算法，它能模拟自然界中生物进化的发展 规律，在人工系统中实现特定目标的优化。目前，遗传算法发展迅速，已被广泛应用于 解决各领域的实际问题，例如，系统优化、工程控制、模式识别、人工智能、故障诊断 等领域，取得了良好的效果。 遗传算法将“适者生存”这一基本的达尔文进化理论引入串结构，并在串之间进行 有组织但有随机的信息交换。伴随着算法的进行，优良的品质被逐渐保留并加以组合， 从而不断产生出更加优良的个体。这一过程就如生物进化那样，好的特征被不断继承下 来，坏的特性被逐渐淘汰。新一代个体中包含上一代个体的大量信息，新一代个体不断 在总体特性上胜过上一代，从而使整个种群不断向前发展。 作为一种全局优化搜索算法，遗传算法有着简单、通用、健壮性强、适于并行处理、 易于与其他技术相结合以及高效实用等显著特点，因此，已经有学者将遗传算法应用于 同构系统【2 i 2 2 域异构系统【2 3 划中的任务分配与调度，并且 2 5 ，2 6 】中将遗传算法应用到 t t c a n 实时调度中。在本文的算法研究过程中，我们将用遗传算法作为主要的研究方 法，来解决f l e x r a y 协议静态段任务的调度问题。但是，遗传算法的搜索效率低，易过 早收敛，理论还不成熟，其编码方式、群体大小、遗传算子的概率等尚需进一步研究。 f l e x r a y 协议静态段调度本质上属于基于调度表的调度，本文采用的是静态调度算 法。所有节点的发送顺序的安排都是事先离线设计的，这样在初始化的过程中，按照这 个离线设计对整个系统进行组态，离线生成调度表。该问题属于n p 完全问题，很难找 到最优解，只能寻找近似解。本文采用装箱问题的启发式算法生成静态调度表，并且对 遗传算法进行了深入研究，根据f l e x r a y 静态段实时任务调度的特点，设计符合问题的 一6 一 东北大学硕士学位论文第1 章绪论 编码机制，并与装箱算法相结合形成混合遗传算法，从而找到最优近似解。 1 4 论文结构及创新点 论文内容如下： 第1 章：绪论，介绍了论文的研究背景和意义，强调了实时调度在汽车总线应用中 的必要性，并对f l e x r a y 协议的研究现状以及任务调度算法的研究现状做了阐述，最后 给出论文的内容结构，并介绍了论文的创新点所在。 第2 章：f l e x r a y 协议的分析，对f l e x r a y 协议进行了详细介绍，分析了f l e x r a y 协议的特性以及作为下一代车载网络标准的优势，阐明了该协议的网络拓扑结构及节点 结构，并详细分析了f l e x r a y 协议的帧格式以及时钟同步、群组启动的实现方式。最后 对f l e x r a y 协议的周期组成部分进行了阐述，并详细分析了f l e x r a y 静态段和动态段的 触发机制。 第3 章：f l e x r a y 静态段实时调度的理论研究，主要是对f l e x r a y 静态段实时调度 问题进行了分析，介绍了实时调度技术，本文采用的是静态调度策略，并给出了应用模 型，分析了带宽利用率的定义，继而说明了静态调度表参数的设置方法，最后分析出 f l e x r a y 静态段任务的实时调度属于n p 完全问题。 第4 章：f l e x r a y 静态段实时调度优化算法，围绕两种算法装箱算法和遗传算 法对问题进行求解，分别对这两种算法进行了介绍，并对算法在问题中的应用做了分析， 进而将装箱算法与遗传算法相结合，形成混合遗传算法，从而能更方便的找到最优解。 第5 章：f l e x r a y 静态段实时调度算法在汽车安全系统中的应用，将第四章介绍的 算法应用到实际汽车安全系统中，并对算法的应用结果进行了分析。 第6 章：结论与展望，对课题的研究工作进行了概括性的总结，并阐述了未来的研 究方向。 论文创新点： ( 1 ) 本文在生成f l e x r a y 静态调度表的同时，分析了任务的路径传输响应时间， 给出了周期任务请求的响应时间计算方法。 ( 2 ) 本文给出了f l e x r a y 静态段带宽利用率的计算方法，并对生成的静态调度表 进行了带宽利用率分析。 ( 3 ) f l e x r a y 静态段实时调度问题实际上是装箱问题，本文将装箱算法与遗传算 法相结合，形成混合遗传算法，弥补了遗传算法所存在的早收敛等的缺点，从而提高了 寻找最优解的速度。 ( 4 ) 在设计遗传算子时，引进了基于预选择的小生境实现方法，这种实现方法可 以替换掉一些编码结构相似的个体，有效的维持群体的多样性。 一7