（计算机应用技术专业论文）传感器网络的任务调度问题.pdf

东北大学博士学位论文 摘要 传感器网络的任务调度问题 摘要 传感器网络中每个节点既是传感器、又是路由器，大多工作在露天恶劣环境 中，计算能力、存储能力、通信能力和电源供应都非常有限。在这些苛刻的资源 环境约束下，如何使以“数据为中心”的传感器网络准确及时地获取和传输感知 对象的特征信息，是传感器网络需要解决的中心问题。 围绕这一中心问题，目前已经展开了许多研究工作，但针对传感器网络任务 调度问题的研究，还存在较大空白，在国内外还没有形成较全面深入系统的体系。 同时任务调度系统问题在传感器网络研究中是非常迫切和关键的，主要表现在： 一、传感器网络的任务负载波动极大，对环境非常敏感，一旦感应到特殊或紧急 情况发生，系统的计算负荷会成倍增长，任务调度系统如果驾驭不当，很容易造 成系统崩溃。如何在资源受限、环境恶劣的传感器网络中保证系统可靠的实时性 成为任务调度系统较为突出的问题。二、传感器网络节点数目众多，大多体积微 小，在相同硬件配置下提高节点的资源利用率会对降低系统的整体成本产生显著 效果。任务调度系统如何优化资源的利用，改善节点的任务处理能力，提高系统 的性价比，成为了一个非常关键的问题。三、传感器网络节点大都采用电池供电， 能源消耗条件苛刻，如何在满足系统实时性能条件下，降低能耗，协调好实时性 和节能之间的矛盾，也是传感器网络任务调度系统所面临的难题。四、传感器网 络同时也是分布式系统，不同于传统的分布式系统，其网络拓扑结构是自组织、 动态变化的，如何利用不稳定的动态网络，协调网络上节点的任务分配调度，实 现系统整体功能的协调统一，是传感器网络任务调度系统问题研究中最为复杂的。 针对这一现状，本文就传感器网络任务调度系统的多方面问题展开了综合研 究。针对传感器网络及节点的特殊性，从分析传感器网络任务调度的特征和主要 规律入手，结合嵌入式实时系统和分布式实时系统的任务调度理论基础，根据其 共性和不同，对传统算法进行科学地改造和重构，并对传感器网络节点的潜能进 行深层次挖掘，采用多层结构，将功能各异的任务调度系统集成为一体，以实现 传感器网络综合性能的改善和提高。 在实时性方面，本文分析了常用单处理器调度策略的优点与不足，在此基础 上提出了自适应s r r m 调度算法，不仅提高了系统的实时性，而且避免了在大负 东北大学博士学位论文 荷状态下实时任务调度系统的脆弱性；在经济性方面，本文结合传感器网络任务 单调的特性，提出在线的微调度模型，大幅度降低系统不必要的开销，提高系统 资源利用率和节点的性价比；在节能性方面，本文分析了现有的动态电源管理 ( d p m ) 和动态电压频率调节( d v f s ) 两种策略的关系以及与实时性能的矛盾， 提出动态电源管理d p m 和动态电压频率调节d v f s 双效处理器节能调度算法 d v f s r m 和d v f s e d f ，协调了传感器网络节点的实时性和节能性的矛盾，达 到显著的节能效果；在协调性方面，本文根据传感器网络分布式、异构性的特点， 建立了传感器网络与传统分布式网络任务调度系统衔接的处理器模型，并将此模 型成功应用到传感器网络任务调度遗传算法中，其中采用了独创的编码方法一一 逆排序消出结点法r s e e n ，并应用启发式变异方法，以加快数据搜索的收敛性， 达到良好效果；最后，本文采用分层结构，实现多种任务调度技术在传感器网络 任务调度系统中的统一协同控制，使传感器网络在实时性、经济性、节能性和协 调性方面得到改善和提高。 关键词：传感器网络任务调度s r - r m 调度算法微调度模型双效节能 调度遗传算法r s e e n 东北大学博士学位论文 a b s t r a c t t a s ks c h e d u l i n gi ns e n s o rn e t w o r k s a b s t r a c t e a c hn o d ei ns e n s o rn e t w o r k si sb o t hs e n s o ra n dr o u t e r , m o s to f w h i c hw o r k su n d e r b a d l yo p e ne n v i r o n m e n t s e n s o rn o d eh a sm a n yl i m i t a t i o n ss u c ha sl i m i t e dc o m p u t i n g a b i l i t y , l i m i t e ds t o r a g ea b i l i t y , l i m i t e dw i r e l e s sc o m m u n i c a t i n ga b i l i t ya n dl i m i t e dp o w e r s u p p l y i n ga b i l i t y t h e r e f o r e ，u n d e rl i m i t e dr e s o u r c ec o n d i t i o n s ，h o wt oo b t a i ne f f e c t i v e i n f o r m a t i o no fs e n s o ro b j e c ta n dr e a s o n a b l yt r a n s f e r r i n gt ot h eg r e a te x t e n ti ns e n s o r n e t w o r k sw i t ht h ec h a r a c t e r i s t i co f d a t ac e n t e rb e c o m e st h ef o c u si s s u em u s tb es o l v e d u p t i l ln o wal o to fr e s e a r c h e so ns e n s o rn e t w o r k sh a v ea l r e a d yb e e nd e v e l o p e d ， w h e r e a st h e r el e a v e sm u c hs p a c et ot a s ks c h e d u l i n gs y s t e m sa n dar e l a t i v e l yi n t e g r a t e d a r c h i t e c t u r eh a sn o tb e e nf o r m e dy e t a tt h es a m et i m e ，t a s ks c h e d u l i n gp r o b l e mi n s e n s o rn e t w o r k si sv e r yu r g e n ta n dp i v o t a l ，m a i n l yd e s c r i b e da sf o l l o w s a tf i r s t , t a s k l o a d si ns e n s o rn e t w o r k sa r et e r r i b l yf l u c t u a t e dw h i c hi ss e n s i t v et oe n v i r o m n e n t t h e l o a d sw i l lg ou ps e v e r a lt i m e sw h e ns o m es p e c i a lo ru r g e n te v e n ti ss e n s e d s y s t e mi s e a s yt oc o l l a p s e i fs c h e d u l i n g s y s t e mr e i n si m p r o p e r h o wt og u a r a n t e er e l i a b l e r e a l t i m ep e r f o r m a n c ei ns e n s o rn e t w o r k sw i t hl i m i t e dr e s o u r c ea n db a de n v i r o n m e n ti s t h ee x t r u s i v ek e yp r o b l e mo ft a s ks c h e d u l i n gs y s t e m s e c o n d l y , l a r g ea m o u n ta n ds m a l l v o l u m ea r et h eb a s i cp r o p e r t i e so fs e n s o rn e t w o r k s ，a n di m p r o v i n gn o d e sr e s o u r c e u t i l i z a t i o nc a nr e d u c et h et o t a lc o s to b v i o u s l yw i t ht h es a m eh a r d w a r ec o n f i g u r a t i o nt oa l a r g ed e g r e e h o wt oo p t i m i z eu t i l i z a t i o no fr e s o u r c e ，i m p r o v et h ec o m p u t i n ga b i l i t yo f n o d ea n dd e c r e a s ec o s tb e c o m e st h es e c o n dk e yt o p i c t h i r d l y , m o s to fs e n s o rn o d e s a d o p t b a t t e r i e sa sp o w e rs u p p l y i n gm o d ea n de n e r g yc o n s u m er e q u i r e m e n ta r er i g o r o u s o nt h ep r e m i s eo fg u a r a n t e en o d er e a l t i m ep e r f o r m a n c e ，h o wt ob r i n gd o w ne n e r g y c o n s u m p t i o na n db a l a n c et h ec o n t r a d i c t i o nb e t w e e nr e a l t i m ea n de n e r g ys a v i n gi st h e p u z z l ef a c e d 谢血t a s ks c h e d u l i n gs y s t e mi ns e n s o rn e t w o r k s f o u r t h l y , s e n s o rn e t w o r k s a r ea l s od i s t r i b u t e d s y s t e m s d i f f e r e n tf r o mt r a d i t i o n a ld i s t r i b u t e ds y s t e m s ，t h e i r n e t w o r k t o p o l o g yh a st h ec h a r a c t e r i s t i c s o fs e l f - o r g a n i z e da n dd y n a m i c h o wt o h a r m o n i z et a s ka s s i g n m e n ta m o n gn o d e st h r o u g hn e t w o r k sw i t hu n s t a b l es t a t u sa n d i m p r o v ei n t e g r a t e dp e r f o r m a n c eo f t h ew h o l es y s t e m si sa l s oav e r yd i f f i c u l ti s s u e a i m e da tt h ep r e s e n ts t a t u s ，t h i st h e s i se n d e a v o r st od oa ni n t e g r a t e ds t u d yi ns o m e a s p e c t so ft a s ks c h e d u l i n gs y s t e m si ns e n s o rn e t w o r k s a c c o r d i n gt ot h es p e c i a l i t yo f s e n s o rn e t w o r k sa n di t sn o d e ，t h et h e s i sa n a l y z e dt h ec h a r a c t e r i s t i ca n dm a i nr e g u l a r i t y o ft a s ks c h e d u l i n gi ns e n s o rn e t w o r k s b a s e do nt a s ks c h e d u l i n gt h e o r yi ne m b e d d e d i v 东北大学博士学位论文 a b s t r a c t r e a l t i m es y s t e ma n dd i s t r i b u t e dr e a l t i m es y s t e m ，t h et h e s i sr e b u i l d st r a d i t i o n a l a l g o r i t h mr e a s o n a b l ya n de x p l o i t s n o d e sd e e pp o t e n t i a la b i l i t yi nl i g h to ft h e i r c o m m o n n e s sa n dd i s s i m i l a r i t y w h a t sm o r e ，s e p a r a t e dt a s ks c h e d u l i n ga l g o r i t h m si s c o m b i n e dt o g e t h e rt h r o u g hh i e r a r c h i c a ls t r u c t u r et oi m p r o v ei n t e g r a t e dp e r f o r m a n c eo f s e n s o rn e t w o r k s a sc o n c e r n i n gr e a lt i m ep e r f o r m a n c e ，t h et h e s i sa n a l y z e sa d v a n t a g e sa n d d i s a d v a n t a g e so fc o m m o ns i n g l ep r o c e s s o rr e a l t i m es c h e d u l i n ga l g o r i t h m s b a s e do n t h e m ，ak i n do fs e l f - r e g u l a t i n gr i da l g o r i t h ms r - r mi sp u tf o r w a r di nw h i c hc a nn o t o n l yi m p r o v er e a l t i m ep e r f o r m a n c eb u tc a l l a v o i ds y s t e mf r a g i l i t yo rc o l l a p s er a i d e r h e a v yl o a d sa sw e l l c o m b i n i n g s e n s o rn e t w o r k s c h a r a c t e r i s t i c sw i t hr e l a t i v e l y m o n o t o n i ct a s k s ，am i c r o s c h e d u l i n gm o d e lf o rp e r i o d i ct a s k si nr e a d yq u e u ei sa l s o b r o u g h tf o r w a r dw i t ht h ei n t e n s i o no f d e c r e a s et a s k su n n e c e s s a r yp r e e m p tb e h a v i o ra n d p r e e m p to v e r h e a dw h i l ee n h a n c e sp r o c e s s o ru t i l i z a t i o na n di m p r o v et h er a t i oo fn o d e p e r f o r m a n c ea n dp r i c e w i t hr e s p e c tt op o w e ra w a r e ，t h er e l a t i o na n dt h ec o n f l i c tw i t h r e a lt i m ep e r f o r m a n c eo fp r e s e n td y n a m i cp o w e rm a n a g e m e n td p ma n dd y n a m i c v o l t a g e f r e q u e n c ys c a l i n gd v f sa l g o r i t h m sa r ea n a l y z e d a c c o r d i n gt ot h e m ，d u a l p o w e ra w a r es c h e d u l i n ga l g o r i t h md v f s - r ma n dd v f s e d fi sp u tf o r w a r d ，i n w h i c hc a r lb a l a n c et h ea b o v e dc o n f l i c ta n da t t a i nab e t t e rp o w e rs a v i n ge f f e c t i n a d d i t i o n ，i nl i g h to ft h ed i s t r i b u t e da n dh e t e r o g e n e o u sc h a r a c t e r i s t i c so fs e n s o rn e t w o r k s ， ap r o c e s s o rm o d e lc o m b i n e ds e n s o rn e t w o r k sw i t ht r a d i t i o n a ld 玛t r i b u t e dn e t w o r k s t a s k s c h e d u l i n gs y s t e mi sb u i l ta n da p p l i e dt ot a s ks c h e d u l i n gg e n e t i ca l g o r i t h ms u c c e s s f u l l y w h i c hi n t r o d u c e san o v e lc h r o m o s o m ee n c o d i n gm e t h o d r e v e r s es e q u e n c ee x c l u d e e x i tn o d ea n da d o p t sh e u r i s t i cm u t a t i o nm e t h o dt os p e e du pa l g o r i t h mc o n v e r g e n c e f i n a l l y , ah i e r a r c h i c a ls t r u c t u r et h a tl e tt h e mw o r kt o g e t h e rc o o p e r a t i v e l yi ss e tu pt o r e a l i z et h eg o a lo ft h ei m p r o v e m e n ta n de n h a n c e m e n to fs e n s o rn e t w o r k sp e r f o r m a n c e i nr e a lt i m e ，e c o n o m y , p o w e ra w a r ea n dh a r m o n y k e yw o r d ss e n s o rn e t w o r k ，t a s ks c h e d u l i n g ，s r - r ms c h e d u l i n ga l g o r i t h m ， m i c r o s c h e d u l i n gm o d e l ，d u a lp o w e ra w a r es c h e d u l i n g ，g e n e t i ca l g o r i t h m ，r s e e n v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：工i j 裘 日期： _ 2 卯堂7 ：，占 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 学位论文作者签名：丘小安 曰期： 2 舶 、7 另外，如作者和导师同意网上交流，请在下方签名；否则视为不 同意。 学位论文作者签名：导师签名： 签字日期：签字日期： t 东北大学博士学位论文第一章绪论 第一章绪论 自m a r k w e i s e r 在1 9 9 1 年于 s c i e n t i f i c a m e r i c a n 的“t h e c o m p u t e r f o r t h e2 1 s t c e n t u r y ”一文1 1 】中首次提出普适计算( u b i q u i t o u sc o m p u t i n g ) 思想以来，普适计 算作为2 1 世纪的计算模式，日益受到人们的关注和重视【2 】。国内外研究机构投入 大量的人力、物力和财力进行研究工作，主要研究方向包括支持普适计算的新型 网络技术( 如传感器网络) 、软件系统( 如支持普适计算的操作系统与网络中间件技 术) ，上下文感知计算技术等1 3 l 。传感器网络技术( s e n s o rn e t w o r k s ) 作为普适计 算思想大系统中的一个典型的应用，目前成为计算机科学领域个非常活跃的研 究分支。 传感器网络具有十分广阔的应用前景，在军事侦察、工业生产控制、森林火 灾监控、医疗监护、农业养殖、太空探索、城市管理、生态监视、环境监测、抢 险救灾、防恐反恐、危险区域远程控制等许多领域都有重要的科研价值和巨大实 用价值【4 。5 】( 表1 1 是传感器网络应用领域的简表) 。因而得到了各国政府、军方、 跨国公司和科研机构的关注与重视，成为当今世界工业界与学术界的研究热点， 被公认为将对二十一世纪产生巨大影响力的技术之一【1 6 1 。 表1 1 传感器网络的应用 t a b l e1 1a p p l i c a t i o n so f s e n s o rn e t w o r k 领域使命任务 军事及反恐友军兵力、装备、弹药调配监视：敌方军力侦察；目标追踪，战争 防爆应用 损伤评估：核生物和化学攻击的探授i 与侦察 环境应用森林火灾的监测；环境的生物复杂性映射；洪水监测；精密农业 保健应用人体生理指标的远程监测：医院内医生和患者的跟踪：药物管理 家庭应用家居自动化：居住环境智能化 其它商务应用汽车防盗；交互式博物馆：库存管理控制；车辆跟踪与控制 1 1 传感器网络的概念 【定义1 1 】传感器网络：传感器网络是由组传感节点以无线连接构成的网 络，以实现协作地感知、采集和处理网络覆盖地理区域中感知对象的信息，并发 布给观察者。一般由上千个传感器节点( s e n s o rn o d e ) 和一个( 或几个) 用户节 点( d a t as i n k ) 组成，传感器节点收集数据，对数据实行在网计算( c o m p u t i n gi n l 东北大学博士学位论文第一章绪论 n e t ) 或融合后，经多跳透信( m u l t i h o p ) 传输给用户节点进行再处理。传感器节 点、感知对象和观察者是传感器网络中的三个基本要素。 【定义1 - 2 】传感器节点：传感器节点是由电源部件、感知元件、嵌入式处理 器、收发部件、移动部件和嵌入式软件这几部分构成( 见图1 1 ) 。其中感知元件 一般是指能感受指定的被测量，并按照一定规律转换成可用输出信号的器件或装 置，通常由直接感受( 或响应) 被测量的敏感元件和转换元件组成。传感器网络 的感知元件一般为各种状态信号量感知元件( 如温度传感器、压力传感器、湿度 传感器、震动传感器、高度传感器、亮度传感器等) ，一般不包含声音、视频等 高带宽的传感元件。 【定义1 _ 3 】感知对象：感知对象是观察者感兴趣的监测目标，也是传感器网 络的感知对象，如车辆、设备、动物、有害气体等。感知对象一般通过表示物理 现象、化学现象或其它现象的数字量来表征，如温度、湿度等。个传感器网络 节点可以感知网络分布区域内的多个对象，一个对象也可以被多个传感器节点所 感知。 【定义1 4 】观察者：观察者是传感器网络的用户，是感知信息的接收和应用 者。观察者可以是人，也可以是计算机或其它设备。一个传感器网络可以有多个 观察者，一个观察者也可以是多个传感器网络的用户。观察者可以主动地查询或 收集网络的感知信息，也可以被动地接收网络发布的信息。 1 2 传感器网络节点的基本组成 传感器网络节点的基本组成和功能包括如下几个单元：传感单元( 由传感器 和模数转换功能模块组成) 、处理单元( 由嵌入式系统构成，包括c p u 、存储器、 操作系统等) 、通信单元( 由无线通信模块组成) 、以及电源部分，如图1 1 所示。 此外，可以选择的其它功能单元包括：定位系统、施动系统以及电源自供电系统 等。 2 东北大学博士学位论文 第一章绪论 图1 1 传感器网络节点结构 f i g 1 1n o d es t r u c t u r e o f s e n s o r n e t w o r k s 节点在网络中可以充当数据采集者、数据中转站或簇头节点( c l u s t e r - h e a d n o d e ) 的角色。作为数据采集者，数据采集模块( 传感单元) 收集周围环境的数 据( 如温度、湿度) ，通过通信单元直接或间接将数据传输给远方基站( b a s es t a t i o n ) 或汇节点( s i n kn o d e ) ，作为数据中转站，节点除了完成采集任务外，还要接收邻 居节点的数据，将其转发给距离基站更近的邻居节点或者直接转发到基站或汇节 点；作为簇头节点，节点负责收集该簇内所有节点采集的数据，经数据融合后， 发送到基站或汇节点。 1 3 传感器网络的特点 传感器网络技术是由多学科高度交叉的新兴技术4 1 ”，它综合了传感器技术、 工业实时控制技术、嵌入式计算技术、网络及无线通信技术、分布式信息处理技 术等。虽然传感器网络综合了上述技术的各种特点，但它与传统网络有着明显不 同【1 7 - 1 9 ，前者以数据为中心，后者则以传输数据为目的，与其它网络如有线网络、 无线a dh o c 网络等相比，传感器网络具有以下明显的特征：动态拓扑性、能耗有 限性、节点资源有限性、数据传感的不可靠性。 1 3 1 动态拓扑性 传感器网络中的节点都兼备数据采集和无线网络路由功能埔圳 ，网络中不存 在中心控制点，用户节点之间的地位是平等的。网络中的传感器、感知对象和观 察者这三要素都可能具有移动性，并且由于能量限制、环境干扰和人为破坏等因 素的影响，传感器节点经常会损坏和失效。传感器网络通常包含成百上千个节点， 东北大学博士学位论文 第一章绪论 图1 1 传感器网络节点结构 f i g 1 1n o d es t r u c t u r e o f s e m o r n e t w o r k s 节点在网络中可以充当数据采集者、数据中转站或簇头节点( c l u s t e r - h e a d n o d e ) 的角色。作为数据采集者，数据采集模块( 传感单元) 收集周围环境的数 据( 如温度、湿度) ，通过通信单元直接或间接将数据传输绐远方基站( b a s es t a t i o n ) 或汇节点( s i n kn o d e ) ，作为数据中转站，节点除了完成采集任务外，还要接收邻 居节点的数据，将其转发给距离基站更近的邻居节点或者直接转发到基站或汇节 点；作为簇头节点，节点负责收集该簇内所有节点采集的数据，经数据融合后， 发送到基站或汇节点。 1 3 传感器网络的特点 传感器网络技术是由多学科高度交叉的新兴技术1 4 - 1s ，它综台了传感器技术、 工业实时控制技术、嵌入式计算技术、网绍及无线通信技术、分布式信息处理技 术等。虽然传感器网络综合了上述技术的各种特点，但它与传统网络有着明显不 同【”o q ，前者以数据为中心，后者则以传输数据为目的，与其它网络如有线网络、 无线a dh o e 网络等相比，传感器网络具有以下明显的特征：动态拓扑性、能耗有 限性、节点资源有限性、数据传感的不可靠性。 1 3 1 动态拓扑性 传感器网络中的节点都兼备数据采集和无线网络路由功能js - 2 1 1 ，网络中不存 在中心控制点，用户节点之间的地位是平等的。网络中的传感器、感知对象和观 察者这三要素都可能具有移动性，并且由于能量限制、环境干扰和人为破坏等因 素的影响，传感器节点经常会损坏和失效。传感器网络通常包含成百上千个节点， 煮的影响，传感器节点经常会损坏和失效。传感器网络通常包台成百上千个节点， 东北大学博士学位论文第一章绪论 在一些特殊应用中，传感器网络的规模可以达到数百万节点。随着传感器节点数 量的增加，传感器网络的存活时间和处理能力也需相应增强。传感器网络需要有 效地融合新增节点，剔除不能正常工作的节点，进行新的组合，使它们融合到全 局的应用中。传感器网络的网络拓扑结构要根据节点的状况自调整和自我配置， 以保证在部分传感器节点损坏、失效和移动的情况下，不会影响到数据传输和全 局任务。 1 3 2 能耗有限性 传感器网络的一个重要特征就是能量受限。传感器节点通常采用能量有限的、 不可更换的电池做工作电源，为保证长时间正常工作，传感器网络必须节省能源 消耗。传感器网绍优化的主要目标是减少能量消耗和促进负载均衡，以提高网络 生存时间【2 2 25 1 。为此每个节点必须能感知环境以及网络拓扑结构的变化，优化自 身的工作状况，减少和消除不必要的能源消耗。 1 3 3 节点资源有限性 在传感器网络中的传感器节点大都采用体积微小的嵌入式处理器和存储器， 数据吞吐量小、计算能力弱、储能空间小、软硬件配置低，节点资源非常有限， 因此为完成大量信息感知任务，必须合理调配传感器网络中的有限资源1 2 “7 1 。 传感器网络节点密度不均匀，当单位面积所拥有的节点数众多时，分配给每 个节点的平均通信周期是很短暂的，通信带宽窄且不稳定，限制了单位时间内网 络数据流量。另外，传感器节点传输信息要t e 执行计算更消耗电能。据统计，传 输1 比特信息所需要的能源可以支持c p u 进行约3 ，0 0 0 条指令的运算，为节约电 耗，必须减少节点的通信时间和距离，通信覆盖范围一般限制在几十到几百米， 由于低功率射频信号的传播范围有限，传感嚣网络需采用多跳通信方式，即网络 中每个节点都需具各路由器的功能，数据通常需要多次中转才能达到目的地，所 有这些极大地限制了传感器网络的通讯能力。 1 3 4 数据传感的不可靠性 传感器网络节点所部署的监测点，通常是无法安排人员值守和维护的恶劣环 境 2 8 - 3 5 】。由于传感器网络经常受到高山、建筑物、障碍物等地势地貌以及风雨雷 电等自然环境因素的影响，节点可能会长时间脱离网络、离线工作；受到传感器 的电源能量的限制，网络中的传感器节点会失效或废弃；传感器节点之间的通信 - 4 东北大学博士学位论文 第一章绪论 断接频繁，经常通信失败；同时检测感应器件也会因环境的破坏和能源的不足而 失效，采集的数据会发生失真或丢失。相对其它网络，传感器网络的数据采集和 传输的稳定性和可靠性差。这些都要求传感器节点必须能随着环境的变化，动态 地调整工作状态，并滤除无效数据，使整个传感器网络系统有较长的存活时间， 能准确稳定地工作。 1 4 传感器网络对任务调度提出的新要求 任务调度是操作系统研究领域中的核心问题，其性能好坏直接影响到系统的 运行效果湖。针对传感器网络的任务调度需求，需要从实时性、经济性、节能 性和协调性四方面改善和满足传感器网络对任务调度系统的性能要求，使传感器 网络更好地协作进行实时监测、感知分布区域内的各种环境信息，通过处理，获 得详尽而准确的数据，传送给用户，并实现及时有效的控制。传感器网络的任务 调度系统研究应汲取传感器技术、嵌入式技术、分布式信息处理技术和实时控制 技术的精华，为操作系统提供专用的小巧、灵活、开放、稳定的内核，为传感器 网络应用的推广，奠定设备级软件体系结构的技术基础i 3 6 。 1 4 1 实时性要求 传感器网络是一个反应系统，通常被应用于工业、军事、航空、医疗等具有 很强的实时要求的领域阳，”l 。传感器网络采集的数据需要及时地传给观测点，并 通过执行器对环境的变化做出快速的反应。传感器网络的数据采集、处理和动作 反应都有一定的时间有效性，实时性要求很强。对于不同的事件，要求的响应周 期也不同。要求操作系统必须内置可靠高效的实时任务调度机制。 对于单个节点，实时系统常规的r m 、e d f 调度系统虽然能满足部分实时性 能，但出于资源、能耗、以及传感器网络任务新特点的考虑，还需要进_ 步优化， 以加强其稳定可靠的性能。 传感器网络又是一个群体的反应系统，当其感应的环境发生变化时，就象人 体的神经受到刺激，会产生大量的连锁反应，此时传感器网络节点的计算负荷将 急剧上升；传感器网络的任务负载极不平衡，高负荷状态下，任务调度系统如果 驾驭不当，很容易造成系统崩溃，系统对大范围任务负载波动的承受能力要求更 高。 因此，保证系统的可靠实时性是传感器网络任务调度系统首先要面对的一个 关键问题：传感器网络要求任务调度系统即具有很高的稳定性，又对计算负荷的 东北大学博士学位论文第一章绪论 大范围波动有良好的适应和平衡能力。 1 4 ，2 经济性要求 体积和成本限制了传感器网络节点的资源配置，资源受限是传感器网络设计 和实现过程中的根本约束。传感器网络节点体积微小，数目众多，大多采用超微、 超低功耗的高成本器件，在很多情况下是不可回收的，每个节点降低微小的成本 都可带来可观的经济效益f 4 卯8 j 。如何采用科学合理的任务调度内核，充分发挥节 点的处理能力，优化资源的利用，使有限的传感器网络的潜能得到充分挖掘，以 提高节点的性价比，降低系统成本，是传感器网络任务调度研究的第二个关键问 题。 1 4 3 节能性要求 传感器网络的一个重要特征就是能量受限。传感器网络节点大都采用电池供 电，且无法更换，甚至电池的体积也受到严格控制，电源能提供的工作电流和能 持续的工作时间都受到限制，能源消耗条件非常苛刻。因此，与传统网络以提供 高质量网络服务为主要目标不同，传感器网络的各个功能部件必须以节约能源为 主要目标m “j 。 传感器网络要求任务调度系统能加强对能源消耗的控制和管理，每个节点能 自动根据环境的变化，关闭部分或全部功能，进入休眠和半休眠状态，必要时还 能及时唤醒，减少能源浪费；同时还要在满足最低实时性能要求的条件下，使节 点处理器运行在低频率的节能工作状态。协调好节能性和实时可靠性的矛盾，就 要求系统必须有以能源消耗和状态转换为优化对象的任务调度机制。 不仅如此，在阿络中，节点间的工作状态也需要协调。对于密集分布在同一 范围内的同类型节点，其数据采集有很大冗余性，如何协调这些节点交替工作， 即保证数据的准确，又减少数据采集、通信和处理的能源消耗，也是传感器网络 任务调度系统要做的工作。 1 4 4 分布式协调性要求 传感器网络同时也是分布式系统，需对网络上的任务做全局或局部的分配调 度，如对物体移动方向和速度的检测需要多传感器节点协同参与检测和计算，应 采用优良的分布式多任务调度算法。不同于传统的分布式系统，传感器网络的网 络拓扑结构是自组织、动态变化的【1 7 - 2 0 ，如何利用状态不稳定的网络系统，协调 6 东北大学博士学位论文 第一章绪论 网络上节点的任务分配，提高整个系统的综合性能，是一个非常复杂的问题口“。 传感器网络的节点是移动的，工作状态因恶劣环境的影响也是不稳定的。传 感器网络的自组织、自扩展、自适应和自重构性能，不仅反映在每个节点必须能 感知网络拓扑结构的变化，自动调整路由，保证网络通信的顺畅和高效，同时反 映在可以根据节点位置和状态的变化，自动重构全体或局部的数据采集、处理和 控制等功能。在节点资源受限、功能单一的情形下，为追求整体或局部资源的充 分利用，功能的完备和稳定，同样需要对资源进行共享和调配。由于节点的移动 性和不稳定性，传感器网络的任务调度系统有别于其它系统，不仅能自动搜寻、 发现、定位和通知资源的变化，还要对资源的稳定性、可靠性做出合理评估，对 不稳定资源自动采用动态的冗余机制和补救措施；同样，为减少节点的能源消耗， 延长网络生存时间，系统能自动协调相同功能的节点间交替切换工作；调度系统 提供智能的冗余机制也非常关键，当某节点的功能丧失、能用其它节点自动顶 替和补救，保证局部或全局功能的实现。 在数据传输受限和参与计算节点动态变化的情况下，如何减少分布式多任务 调度算法的数据交换量，并对全局和局部的任务做动态调度，对个体或局部功能 的丧失具备良好的抵御能力，这些都需采用新的分布式任务调度机制。 1 5 传感器网络国内外研究动向 传感器网络是多学科高度交叉的新兴前沿热点研究领域。传感器网络综合了 传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术 等，能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或 监测对象的信息，通过嵌入式系统对信息进行处理，并通过随机自组织无线通信 网络以多跳中继方式将所感知信息传送到用户终端，从而真正实现“无处不在的 计算”理念。传感器网络的研究采用系统发展模式，因而必须将现代的先进微电 子技术、微细加工技术、s o c ( s y s t e m o n c h i p ) 设计技术、纳米材料与技术、现 代信息通信技术、计算机网络技术等融合，以实现其微型化、集成化、多功能化、 系统化及网络化，特别是实现传感器网络特有的超低功耗系统设计。 1 5 1 国内外总体研究动向 从2 0 0 0 年起，国际上开始出现一些有关传感器网络研究的报道，2 0 0 3 年2 月 的美国技术评论杂志评出对人类未来生活产生深远影响的十大新兴技术，传 感器网络被列为第- - 3 1 。 7 东北大学博士学位论文第一章绪论 美国为了保证在这一革命性技术领域的优势地位，其国防部高级研究计划局 d a r p a 和自然科学基金委员会n s f 先后制定了传感器网络研究的中长期研发计 划，支持相关基础理论的研究。2 0 0 2 年d a r p a 投入6 亿美元、2 0 0 3 年n s f 投入 3 4 0 0 万美元，分别资助了许多著名大学和科研机构进行研究，其中比较著名的研 究计划包括：加州大学伯克力分校的s m a r td u s t 项目；佐治亚理工大学s e n s o r n e t 项目；加洲大学洛杉矾分校的w i n s 项目；麻省理工学院的m a m p s 项目等。美 国英特尔公司、微软公司等信息工业巨头也开始了传感器网络方面的工作。日本、 英国、意大利、巴西等国家也对传感器网络表现出了极大的兴趣，纷纷展开了该 领域的研究工作1 4 “”。 我国在这方面的研究工作还很少，目前，国内一些高等院校与研究机构积极 开展传感器网络的相关研究工作，主要有清华大学、中科院沈阳自动化所、浙江 大学、哈尔滨工业大学、北京邮电大学、西北工业大学、中科院软件所以及东北 大学等。 传感器网络处于新技术的最前沿，但是，目前大部分的研究尚处于起步阶段， 少数投入实用的商业产品距离实际需求还相差甚远。目前尚存在着许多值得探讨 的热点课题，国内外学者正在进行深入地研究，很多相关领域仍处于百家争鸣的 阶段。 1 5 2 已开展的传感器网络研究项目 从2 0 0 0 年至今，国外已有多家研究机构、大学和公司投入了大量的人力、财 力进行这方面的研究，并取得了相应的进展： 美国加州大学伯克力分校推出了m o l e 传感器设备1 4 6 - 4 7 】，尺寸很小，功耗 极低，能收发信息，工作于多种模式(