（计算机应用技术专业论文）传感器网络mac层中负载自适应的时隙调度算法研究.pdf

硕士学位论文 h t a s t e r s r h e s i $ 摘要 随着无线通信、计算技术、微电子技术的进步，极大地推动了无线传感器网络 ( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 的发展，并以其低成本、低功耗、自组织和分布式 的特点带来了信息感知领域的一场革命。无线传感器网络的媒体接入控制协议 ( m e a i u ma c c e s sc o n t r o l ，m a c ) 决定了传感器网络无线信道的使用方式，在传感器 节点之间分配有限的无线信道资源，m a c 协议处于传感器网络的底层部分，是无 线传感器网络研究的重要领域之一。 基于时隙调度的m a c 协议主要将w s n 的信道划分给节点，节点之间根据信 道建立链路实现数据转发的时隙。相对于基于竞争的协议，基于时隙调度的可以避 免冲突，减少节空闲帧听。但是目前基于时隙调度的协议确定节点时间同步较为困 难，比较适合数据量大，连续性的网络下工作。它在为节点分配时隙时，一般将各 节点的分为等长的时隙，如果网络处于复杂多变的环境下，容易造成节点的时隙的 浪费以及节点时延的增长。且忽视了与网络层融合，没有利用网络层路由信息降低 节点分配时隙的额外的能量消耗。 本文针对传感器网络处于不同的负载环境下，动态地分析每轮需要的时隙大 小，在t d m a 机制m a c 算法基础上，改进2 种不同环境下基于节点流量负载的时 隙调度算法。 ( 1 ) 针对节点处于连续的、环境复杂多跳异构网络，提出了一种多对一通讯的 时隙调度算法。通过对簇内构造的转发树来预测每轮节点需要的数据量，根据数据 量的大小决定时隙的大小，簇首据此为簇内成员节点分配时隙。 ( 2 ) 针对节点处于非连续的单跳同构网络，节点数据量变化较大，提出了一种 根据节点每时每刻的数据量来决定时隙调度算法。算法采用簇结构，每轮时序周期 内，簇首节点实时地采集成员节点数据量的信息，据此决定成员节点的时隙。实验 分析后，算法取得了预期的效果，满足工作地2 种算法的具体环境应用要求。 关键词：无线传感器网络；m a c 协议；时隙调度 硕士学位论文 m a s t e r st h e s i s a b s t r a c t ，n l ep r o g r e s si nt h ew i r e l e s sc o m m u n i c a t i o n , c o m p u t a t i o na n dm i c r o e l e c t r o n i c t e c h n o l o g yp r o m o t e dw k e l e s ss e n s o rn e t w o r k ( w s d e v e l o p m e n tc n o r r n o u s l y m a cp r o t o c o lt r i e st oe n s r i r et h a tt w on o d e sa r en o ti n t e r f e r i n gw i n le a c ho t h e r s t r a n s m i s s i o n s ，a n dd e a lw i t ht h es i t u a t i o n i ts h a r e sw i r e l e s sc o m m u n i c a t i o nc h a n n e l m a cp r o t o c o ld i r e c t l ya f f e c t st h el i f e t i m eo fw s n t h ee n e r g yc o n s u m p t i o no fm a c p r o t o c o li n f l u e n c e so nt h en o d ed a t aa c q u i s i t i o na b i l i t ya n dt h en e t w o r kl i f e t i m e i th a s t h ev e r yt r e m e n d o u si n f l u e n c eo nt h es e n s o rn e t w o r k sp e r f o r m a n c e ，t h em o s ti m p o r t a n t a i mo fd e s i g n i n gm a c p r o t o c o li st or e d u c et h ee n e r g yd i s s i p a t e di nt h en e t w o r ka n d m a x i m u mt h en e t w o r kl i f e t i m e s c h e d u l i n gm a cp r o t o c o li sm a i n l yb a s e do nt d m a i tp e r i o d i c a l l ys c h e d u l e se a c h n o d et i m es l o tf o rd a t at r a n s m i s s i o n t h en o d e sw h i c ha r ei ni d l et i m es l o t sg e ti n t os l e e p i no r d e rt os a v ee n e r g y t h es c h e d u l i n gm a c p r o t o c o lc a ns o l v et h ec o l l i s i o nr e - t r a n s m i t p r o b l e ma n dl e s sc o n t r o li n f o r m a t i o n b u ti tn e e d ss t r i c tt i m es y n c h r o n i z a t i o n i ti s s u i t a b l ef o rt h en e t w o r kn o d e sh a v em o r ed a t al o a da n dw o r k i n gi nc o n t i n u i t y h e nt h e s c h e m eb a s e do nt d m a a s s i g n st h et i l n es l o t , g e n e r a l l yi td i v i d e se a c hs u b - c h a n n e li n t o s a l n et i m es l o l i ft h en e t w o r ki su n d e rt h ec o m p l i c a t e da n dd i v e r s i f i e de n v i r o n m e n t , e a s i l yc r e a t e st h en o d et h et i m es l o tw a s t ea sw e l la st h en o d et i m ed e l a yg r o w s p r e s e n t m a cp r o t o c o lb a s e do nt h et i m es l o td o e s n tc o m b i n ew i t hn e t w o r kl a y e r , h a sn o tu s e d t h em u t i n gi n f o r m a t i o nf o rn o d et i m es l o ta s s i g n m e n t t h i sp a p e ri nv i e wo ft h ew i r e l e s s s e n s o rn o d ew o r ku n d e rd i f f e r e n tc o n d i t i o n s ，u n i f i e dt h en e t w o r kt o p o l o g y , d y n a m i c a n a l y s i sm a cl a y e re a c hr o u n dn o d e sn e e d st h et i m es l o ts i z e ，w ep r o p o s e dt w ok i n d s t i m es l o ts c h e d u l i n ga l g o r i t h m sb a s e do nt h en o d ec u r r e n tt l r 伍cl o a d ( 1 ) a ss e n s o rn o d e s w o r k i n gi nc o m p l e xm u l t i - h o p sh e t e r o g e n e o u sn e t w o r kt h i sp a p e rp r o p o s e sa l la d a p t i v e t i m e - s l o ts c h e d u l i n ga l g o r i t h m ( a t s a ) b a s e do nc l u s t e r i n g a t s ad i v i d e dt h ee n t i r e n e t w o r ki n t os o m ec l u s t e r s ，a n dc o n s t r u c t e dad a t ag a t h e r i n gt r e ei ne a c hc l u s t e r e a c h r o u n d , t h ec l u s t e rh e a ds c h e d u l e st h et i m e - s l o to fn o d e sa c c o r d i n gt ot h e i rt r a 伍cl o a d s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o t o c o lc o u l dm e e tt h es y s t e mr e q u i r e m e n t si n r e l i a b i l i t y , r e a l - t i m er e s p o n s ea n de n e r g ye f f i c i e n c y ( 2 ) a ss e n s o rn o d e sw o r k i n gi n n o n - c o n t i n u o u ss i n g l e - h o pi s o m o r p h i s mn e t w o r k ，at i m e s l o ts c h e d u l i n ga l g o r i t h mb a s e d u 硕士学位论文 m a s t e r st h e s i s o nn o d e s r e a l - t i m ec o n d i t i o i l sf o rw l e s ss e n s o rn e t w o r k s ( t r a t ) w a sp r e s e n t e d , t h e a l g o r i t h mw h i c hi sb a s e do nc l u s t e rs t r u c t u r e ，u n i f i e sd i s t r i b u t i o n a la n dt h ec e n t r a lm e r i t , i n t h i sa l g o r i t h m , t h ec l u s t e rh e a da d j u s t st h et i m e s l o to fn o d e sa c c o r d i n gt ot h e i r c o n d i t i o n s ，a n dt h ee n e r g yc o n s u m p t i o nb a l a n c i n ga m o n gn o d e sw a sa c h i e v e dw i t hal o w l a t e n c y s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mi m p r o v e st h en e t w o r ke n e r g y u s a b i l i t ya n di n c r e a s e st h en e t w o r kl i f e t i m e ，r e d u c e st h ed a t ap a c k e tt i m ed e l a y k e yw o r d s ：w v r e l e s ss e n s o rn e t w o r k ；m a cp r o t o c o l ；t i m e - s l o ts c h e d u l i n g i l l 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：寅d 铫日期：秒哆年万月公日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：列锇 日期：。，年善月秽日 规定享受相关权益。回壶途室提变压遗厦! 旦坐生；旦= 玺；旦三笙发查： 作：签名翌鬟，导师签名翻心 日期：、z p 忤二月8 日 日期： 力。忤莎月。禽日 硕士学位论文 t a s t e r st h e s i s 1 1 研究背景及现状 第一章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s 是由部署在监测区域内大量 具有无线通信功能的廉价微传感器节点以自组织方式组织起来的网络。它们分布在 需要采集数据的环境内，获取数据，数据经过加工处理以后转发给基站，如图1 1 所示。传感器节点固定位置以后，位置相对保持不变，可以运用在人类没有办法涉 及的领域。传感器网络的出现为一些特殊环境下的信息获取提供了便利，不需要对 环境进行破坏。无线传感器网络作为本世纪关键技术之一，在军事帧察、智能家居、 监控领域的巨大的应用价值得到了各国政府、军方、跨国公司和科研机构的关注与 重视。随着传感器网络技术的不断发展，其最终将成为现实世界与数字世界的接口， 深入到人们日常生活的各个方面，并对其带来深远的影响l l j 。 任务管理 恐 基站 节点 图1 - 1w s n 简单的结构图 它的巨大的价值已经引起了全球的关注，越来越多的组织加入到该研究中，如 美国国防部以及各国的军事部门，我国也较早展开该领域的研究工作，特别本世纪 以来，我国将传感器网络列为重点优先发展的领域，体现我国高度重视传感器网络 的发展。我国传感器网络的商用也取得了可喜的进展，相关应用已近进入市场。 w s n 研究主要方向，如图1 2 所示。 ( 1 ) 通信协议。包括物理层协议，数据链路层协议( 最重要的是m a c 协议) 、 网络层协议( 主要指路由协议) 、传输层协议等。 ( 2 ) 数据融合。无线传感器网络最重要功能的就是节省能量，减少数据的传输 量可以有效地实现这一点，因此在数据采集的过程中，利用节点的本地的条件对数 据有效地融合后去除冗余信息，减少数据传输量，节省能量。 ( 3 ) 定位技术。确定传感器节点的位置信息是无线传感器网络在数据采集过程 中重要工作，最基本的功能包括确定事件发生的位置以及采集数据的节点位置信 息。 图l - 2 传感器网络结构 1 2 研究目的与意义 无线传感器网络是一种全新的信息获取和处理技术，实现无线传感器网络，是 迈进人工智能的一大步 2 1 。及时的发展该技术关系重大，较早地掌握该技术可以带 来国家的军事、经济的全面进步。全球纷纷展开研究，探讨了其中的一些主要问题， 许多机构全面合作。我国也在较早时间内展开了相关的研究。目前，我国已经将它 列为国家优先研究领域，可见w s n 对我们整个国家和社会都具有不同一般的重大 的意义】，w s n 在我国取得了飞速的发展。 它较为特殊的构造决定了能量耗尽后，能源不能重新补充，节省能量是其推广 和应用中的难点。在没有比较好的节约能源且效率利用高的能源设备出现前，在具 体设计时候，节能是传感器网络考虑的重要部分，也是目前研究的热点例。选用合 2 硕士学位论文 m a s t e r st h e s i $ 理的m a c 协议，有效地提高能量的利用效率符合当前的要求，同时针对一些与众不 同的环境，m a c 协议还必须兼顾其他因素( 如实时性要求等) ，必须针对专门场景设 计性能不同的m a c 协议，满足具体的应用要求。 1 3 本文的研究工作 本文探讨了当前w s n 中m a c 协议的现状，总结了当前该领域一些较为经典 的协议。重点研究了基于时隙调度的协议，探讨了能量的消耗的主要方式及接收数 据不及时等因素。针对两种不同的网络环境，分析了它们其所需的性能，改进了基 于t d a m 的算法，满足两种不同网络应用环境需要的性能。 ( 1 ) 针对传感器节点处于连续性的复杂多跳异构网络下工作，在簇内通过构造 转发树结构实现的多对一通讯，根据树可以动态地预测节点的数据量，来分配节点 时隙大小。通过提高节点的时间利用率来节约网络的能量消耗，保证数据能够及时 的转发数据。 ( 2 ) 针对传感器节点处于非连续性的状态的单跳同构网络，实时要求比一般网 络的要求高，网络负载每轮时隙不稳定。在每个簇内，每轮时序帧内，成员节点向 簇首发送自己实时负载信息，据此合理分配时隙，提高数据实时要求。 1 4 论文的组织结构及安排 第1 章介绍了m a c 协议的研究意义和国内外研究现状等；对整篇文章的结构 进行了安排。 第2 章介绍了m a c 协议，分析了m a c 的一些共性要求，重点分析了能量消 耗的主要因素。根据对m a c 协议的分析，归纳了m a c 协议设计的一些原则。列 举了m a c 协议的类别，重点分析了基于调度的m a c 协议，介绍了几种常见的m a c 协议。 第3 章提出了一种基于多对一通讯的时隙调度算法a t s a 。算法中采用簇结构， 通过在簇内树，节点据此发送或接受数据。通过树结构来动态决定节点时隙大小和 顺序。对算法给出了详细的描述。最后对算法进行了仿真分析。 第4 章提出了一种基于节点实时性负载的时隙调度算t r a t 。算法同样采用簇 结构，每轮帧内，簇首节点采集自己单位内的节点各种信息，据此合理进行时隙的 分配，提高数据实时要求能。算法给出描述。并对算法进行了仿真分析。 第5 章归纳了前几章的主要内容，并指出了以后的研究的重点工作。 3 硕士学位论文 m a s t e r st h e s i s 第二章传惑器网络m a c 层协议相关研究 2 1 传感器网络m a c 协议概述 在o s i 中，媒体接入控* 0 0 d e d i u ma c c e s sc o n t r o l ，m a c ) 位于数据链路层的子 层，m a c 协议的性能与物理层、网络层有着直接的关联，如图2 1 所示。它主要任 务是主要任务是决定传感器网络无线信道的使用方式，在传感器节点之间分配有限 的无线信道资源，通常需要保证某些特定性能以及满足与应用相关的性能。作为传 感器网络的协议栈的关键部分，直接影响整个网络的性能，是保证传感器网络能够 顺利工作的基础【4 j 。 图2 - 1m a c 层次图 传感器网络的m a c 协议设计区别于其他网络的最主要特征在于：是否把减少 能量作为设计时考虑的首要问题。现有的对方具体的性能要求都不同于传感器网 络，都没有把节能作为设计时的首要任务，如蜂窝网络【5 1 、a dh o e 网、b l u e t o o t h l 7 等。虽然w s n 在组成网络的结构上面有某些相似的地方，蜂窝网络侧重于满足网 络服务质量，a dh o e 主要解决节点不断地运动对其带来的各种性能的挑战的影响， 并且他们都可以比较方便的准确地补充能量，因此也就没有必要把节约能量作为网 络设计的首要因数。可见，传统的无线网络的m a c 协议不能直接应用于传感器网 络中。 m a c 协议设计取决于网络实际的工作环境。如果传感器网络处于连续的且节 点状态变化较大的环境下工作，则期望一个连续的、数据量变化不大的网络。另一 方面，如果传感器网络在非连续环境下，数据持久性较差，节点可能需要实时数据 来确认信息。在不同的情况下都需要m a c 协议具有较高的数据转发效率，尽可能 地延长网络寿命嗍。 4 硕士学位论文 m a s t e r st h e s i $ 2 2m a c 协议设计目标 2 2 1m a c 协议设计的原则 无线传感器网络节点数目众多，它的功能是通过网络节点协同工作完成的。由 于节点无线通信的广播特征，节点间信息传递在局部范围内传递，需要m a c 协议 协调节点之间的无线信道分配。w s n 与a dh o c 网络的区别决定在设计m a c 协议 应该分别来对待，不能统一划分，尤其需要考虑能量的因素。虽然针对不同的环境 下m a c 要求不尽相同，特别的环境下甚至需要设计专门用的协议，但是在设计 w s n 的m a c 协议时，以下方面一般需考虑。 ( 1 ) 能量有效。无线传感器网络最重要的就是节约能量，为了长时间保证w s n 持久有效的工作，设计m a c 协议时应尽量较少使用节点的能量，提高w s n 的生 命周期。由图2 2 节点的通讯模块可以看出节点能量主要消耗的部分，应该减少节 点空闲帧听的时间，而转入休眠状态，这样网络节点的能量消耗相应就会减低。 2 0 功1 5 耗 1 0 m w 5 o 臻 茹燃黝 瀚骚翳 圜纛酸一 发送挟跫至用n n g 通信 图2 - 2 通讯模块 ( 2 ) 网络的动态性。由于传感器节点数目、节点分布密度等在传感器网络生存 过程中不断变化，节点位置也可能移动，还有新节点加入网络的问题，所以无线传 感器网络的拓扑结构具有动态性，m a c 协议也应具有可扩展性，以适应这种动态 变化的拓扑结构。 ( 3 ) 节点通讯的公平性。传感器网络每个节点应该共享无线信道，每个节点都 应该在一段时间内占有信道，发送数据。 ( 4 ) 可靠性和稳定性。在w s n 中，数据包的丢失可能不能避免，且w s n 一 般在恶劣的环境下受到外界环境影响较大，可能造成发送数据的丢失。这就要求在 设计m a c 协议需要检查数据接收情况，保证数据能够有效地传送。 硕士学位论文 m a s t e r st h e s i s 在以上几个方面中，降低网络的能量消耗成目前设计考虑的首要问题。其它性 能与网络的具体应用环境相关。设计一个合理的m a c 协议，需要考虑网络具体应 用环境，是一项对各种因素平衡的过程，目前还没有一种m a c 协议可以适应所有 的网络。 2 2 2m a c 协议能耗分析 w s n 相对于a dh o c 对网络节能要求更高，节约能量是w s n 面临的首要问题。 一般情况下造成w s n 能量的消耗主要是如下几个方面。 ( 1 ) 空闲帧听。节点不能预知他的邻居节点何时向自己传输数据的时隙，因此 节点的射频模块需要一直保持为接收模式，造成了节点能量的大量消耗。如节点a 为了能够工作，需要邻居节点b 转发数据，这样邻居节点b 就因为不知道需要转发 节点a 的数据，而一直保持监听状态，因而不能进入休眠阶段，造成了大量能量的 浪费。 ( 2 ) 冲突重传。节点在发送数据的过程中，在竞争共享的无线信道中，可能会 引起多个节点之间发送数据时产生碰撞，数据包发送失败，就会浪费发送和接收数 据上的能量，然后需要重传发送的数据，从而消耗节点更多的能量。 ( 3 ) 偷听。如图2 3 所示，节点3 必须保持监听状态当居节点2 有数据发送时 候，而节点2 发送给节点1 ，节点1 同样也会收到数据包，而这些数据根本就不是 该节点应该接受的。这样增加了网络节点的开销，造成能量浪费，降低了网络的工 作效率。 2 2 3m a c 协议的分类 图2 - 3 邻居节点偷听 w s n 与应用高度相关，目前研究人员从不同的方面出发，提出数量众多的m a c 协议。对协议分类是一项艰巨的工作，目前还没有成立标准化组织，也没有标准可 以参考 9 1 。研究人员目前大都根据信道分配方式、数据通信类型等其他方面，使用 多种分类方法对其分类。 6 硕士学位论文 m a s t e r st h e s i s ( 1 ) 基于竞争和基于调度。基于竞争协议，节点如果有数据需要发送，就发送 竞争消来占有信道，如果信道已经有节点在用了，就等待一段时间后再次占有，直 到占用信道。调度协议，主要通过为每个节点分配时隙，节点明确自己工作时隙， 其它状态下可以进入不工作的状态。 ( 2 ) 单一共享信道还是多信道。主要分为单的信道或多信道。如果用户投资较 小，对网络性能要求低可以使用单信道，所有节点共享唯一的信道；相反，用户投 资较多，需要网络具有良好的性能，多信道较为合适。 ( 3 ) 单层协议还是跨层协议。单层得仅限于m a c 层，没有考虑与其他层次的融 合，而多层的更多结合路由层或者物理层的信息来设计m a c 协议。 2 3 典型的m a c 协议 主要根据信道访问策略的不同介绍比较经典的m a c 协议，对不同类型的协议 进行一定分析总结，列举每种类型的一些典型协议。 2 3 1 基于竞争的m a c 协议 竞争信道的协议是目前采用最多的一种协议。主要思想就是一个节点向接受节 点发送的机会可能是从相邻几个节点竞争而来的。如果只有一个节点，就没有必要 竞争了，直接发送数据就可以了，相反就需要竞争来确定哪个节点占用信道。典型 协议是8 0 2 1 1 协议【1 0 1 、s - m a c 协议【1 1 】等。 ( 1 ) s - m a c 协议 s m a c 是在8 0 2 1 1 基础上改进而来，其工作方式如图2 4 所示。s m a c 通过 周期休眠阶段和占空比来减少监听时间。协议将时间分片( s l o t ) ，片长度由应用程 序确定，分为工作阶段和休眠阶段。并在工作形成一个虚簇，在该簇内节点工作保 持一致，见图2 5 所示。在休眠阶段，节点关闭射频模块，缓存这期间采集到的数 据，在工作阶段集中发送。通过占空比来确定节点在一个周期的工作阶段的时间片。 当节点处于工作阶段的时间片，节点就打开天线，保持监听、信息发送状态。两次 监听时间的间隔由物理层和m a c 的参数确定，比如竞争窗口的大小。所以节点自 由选择休眠阶段。不幸的是，它的占空比固定，s l e e p 不能动态的改变，且在网络 流量动态变化比较大的应用中，不能根据网络的负载动态地调节不同的时间u 2 j 。 7 硕士学位论文 m a s t e r st h e s i s 卜一l i s t e n p e r i o dh i i 舞。 r t sf o r d a m s l c 镕p n 础 二圣二二二二二 二五 2 二三二二二 j 三二瑁 图2 - 4s - m a c 时隙帧周期 虚 2 3 2 基于调度的m a c 协议 图2 - 5s - m a c 的虚簇 簇二 调度的m a c 协议基本思想是：传感器节点通过分配时隙来确定自己工作地时 隙，在该时隙内占有信道，发送数据，其它阶段进入休眠状态。常见的基于调度的 m a c 协议有t r a m a 协议【1 4 1 、b m a 协议【1 5 】1 等。 ( 1 ) b m a 协议 b m a 协议主要通过减少空闲监听和冲突避免来减低网络的能耗，同时网络可 以保持比较理想的延时。在b m a 协议采用许多“轮 循环工作，具体原理见图2 - 6 所示。协议分为建立簇阶段和稳定阶段。节点根据剩余能量选举簇头。当选簇头广 播当选通告，其余节点根据接收信号强度决定加入哪个簇。稳定状态阶段由多个时 间帧组成，每个时间帧由竞争时隙、数据传输时隙和空闲时隙3 个部分组成。节点 在竞争时槽获得数据传输时槽，并在数据传输时槽向簇头报告状态。簇头收集成员 节点状态信息并发布调度，每个有数据发送的节点获得一个确定的发送时槽，且只 硕士学位论文 m a s t e r st h e s i $ 在发送时槽向簇头节点发送数据，其余时间休眠。b m a 协议设计简单，相比t d m a 机制上增加了节点实时信息发送需求，但是改进不多，节点的时隙大小固定不变， 无法适应网络流量变化，降低了信道利用率，在特定情况下节点也无法作者设计的 要求1 7 1 。简单簇头选择已经不能满足本网络的需求，应该采用比较合理的分簇1 5 , 1 9 。 建立 阶段 稳定阶段 卜l 卜型l 一l 数据数据 数据教据数据 时骧 时骧 时隙时豫时隙 竞争数据空闲竞争数据空闲 时期传输时期时期传输时期 建立 阶段 稳定阶段 卜旦叫卜j l h 竞争 时期 2 3 3 其它类型的m a c 协议 图2 - 6b m a 工作原理图 竞争与调度的m a c 协议是目前传感器网络最基本、也是最主要两种类型协议。 近些年来随着传感器网路的发展，众多不同类型的网络需求以及大量学者深入研 究，推动了m a c 协议的发展。最近又提出了新的协议，典型的有结合型m a c 协 议以及跨层的m a c 协议。 结合型的m a c 协议指融合了不同的类型，比如竞争的与调度的融合，吸取他 们的优点，避免二者的缺点，总之就是不采用单一的机制，结合几种的策略的特点。 目前w s n 的m a c 协议设计基本基于单一数据链路层。w s n 仍然沿用经典网 络分层设计，每层设计简单，具有较好的兼容性。采用单一层次设计时，往往不能 兼顾每层不尽相同性能参数，没有合理地利用层与层之间的信息交互口o l 。实际上单 一层次m a c 协议虽然在某些方面取得理想的网络性能要求，但总体不利用整个网 硕士学位论文 m a s t e r st h e s i s 络设计，最理想的是采用多层的m a c 协议【2 1 1 。比如利用网络层路由信息与链路层 的交互，网络可以有效提高数据发送效率；利用物理层与m a c 层交互的信息减低 网络的能耗，提高节点效率等。 2 4 时隙调度的m a c 协议分析 从前面介绍的几种调度的m a c 协议可以看出，调度的m a c 协议相对于基于 竞争的m a c 协议，在流量较大的传感器网络中具有比较明显的优势，节约能量效 果好，但是不利于网络负载小的网络。下面从对传感器网络m a c 协议性能影响的 几个性能进行分析。 ( 1 ) 能量消耗。前文已经分析了对m a c 协议能耗影响的四个方面。基于时隙 调度的m a c 算法可以取得比较理想的能耗需求。算法可以通过合理分配节点的时隙 来避免节点发送数据时造成不必要的重新发送。总体来说，只要设计合理基于调度 的时隙m a c 算法应该能够取得较好的能耗需求。 ( 2 ) 时间延时。基于时隙调度的可以显著地减少节点的发送的时间，提高网络 实时性要求。整个传感器节点都是按照固有的时隙表工作，节点发送冲突的机会就 会大大减低，节点数据包转发效率可以提高。 ( 3 ) 吞吐量。基于时隙调度的协议本身具有独特的优势。由于它是完全按照分 配好的时隙工作，顺序已经决定好，节点有规律工作，因此节点的信道利用率较高， 虽然数据包的开销可能大了一些，但是综合这些因素，网络吞吐量比较理想。 ( 4 ) 公平性。基于时隙调度的m a c 协议就没有个别节点没有机会占有信道的情 况，节点按照时隙表来工作，只要在自己的时隙内才能占有信道，这样所有节点都 能享有信道的机会，不会造成个别节点长时间不能发送数据的情况。 从以上几点分析基于时隙调度的m a c 协议优势比较明显，尤其在网络负载比较 大的情况下具有无可比拟的优越性。同时基于时隙调度的m a c 协议也面临了一些问 题。 ( 1 ) 目前基于时隙调度的协议不适应于负载较小的传感器网络，由于负载小， 节点控制开销相对比较大，相对于另一种的m a c 协议不利于网络生命周期。 ( 2 ) 确定网络节点一起工作的时间较为困难，由于节点数目庞大，在时隙调度 的协议中，必须为节点分配每轮周期的时隙，决定节点时间同步就比较困难。 1 0 硕士学位论文 m a s t e r st h e $ 1 s 2 5 本章小结 本章介绍了无线传感器网络的m a c 协议的一些基础知识，探讨了m a c 协议 设计原则，重点分析了m a c 协议能量浪费的因素。对m a c 协议进行了简单的分 类。针对不同类型的m a c 协议，本章列举了一些典型的协议、并对其中协议进行 了分析。最后阐述了基于时隙调度的m a c 协议，总结了它主要的优缺点。 硕士学位论文 _ d ：a s t e r st h e s i s 第三章多对一通讯的自适应时隙调度算法 针对w s n 处于大规模的网络拓扑下，节点的数量众多且环境较为复杂，对于 设计的m a c 算法造成了较大的挑战1 2 4 1 ，如何使节点之间的有效转发数据，及时地 划分发送信息的所要的时隙等，都是目前研究的难点。本章提出了一种多对一通讯 的时隙调度算法( a t s a ) ，通过对网络分簇降低网络的设计复杂度，在簇内，构建转 发树结构，实现数据转发的工作，形成网络的转发路径路由。结合m a c 层与路径 信息，实时获取节点的数据量，决定节点的工作的时隙，减少网络能耗，提高节点 能量的利用效率，降低数据包的延时。 3 1 引言 基于时隙调度m a c 协议可以使节点通过消除冲突来避免空闲监听以及在非活 动状态时关闭节点等方式节省能量。基于时隙调度也有本身缺点：实现节点同步困 难，适合流量较大的网络，限制了它的应用规模。基于时隙调度的m a c 协议网络扩 展性不强，针对专门的网络需要设计专门的m a c 协议。简单时隙调度协议不符合复 杂环境的传感器网络。因为它主要基于节点的数目为每个节点划分时隙，对于每个 时隙的大小没有具体的设计，且一般将它们划成等长的。显然划分为等长较为不合 适，如果某些节点发送数据量较小，而给它较长的时间，就容易造成需要发送数据 量较小的节点的部分时间处于空闲状态，同时节点的延时也进一步延长。在网络数 据量较小的时候，传感器网络花费在划分方面的能量相对于合理利用部分的比例更 高，协议不适应于流量较小的网络以及流量不稳定的网络。 a t s a 算法主要基于网络处于大规模运营环境，多节点的异构网络，许多节点 因为距离较远而不能直接将数据转发出去，需要通过其它节点的转发。a t s a 算法 所处环境较为复杂，不同时刻以及不同节点需要发送的量差异较大。这就给设计工 作带来了难题。a t s a 采用分簇结构来降低网络计算量，且节点不需要麻烦的时间 同步。在每个簇内，构建数据转发树，通过树结构预测节点的数据量量大小来决定 节点实时的发生时间，可以有效地保证网络的应用性能。 3 2 网络模型与假设 a t s a 算法处于的网络环境拓扑较大，大量的节点无规律地分布，这对于m a c 1 2 士学t 论文 算法的设计工作造成了巨大的挑战。目前，比较好的方法是将整个网络划分一些较 小的单位组成，这些单位称为簇，见图3 1 所示。每个区域中簇头节点为中心节点， 管理该区域的所有节点，每个区域形成一个较小通讯单位。在a t s a 算法中，为异 构网络选取其中若干个能量较大的节点为簇首节点，其数据的处理能力比较强所 有成员节点都需要借助于匿节点转发数据。由于网络范围较大，分簇后，太部分节 点仍然要多次转发完成。簇首的选择的工作完成以后，普通节点根据距它远近决定 自己应该加入距离最近的簇的簇。每个节点只能有加入一个簇，a t s a 算法中没有 一个节点属于两个或者两个以上的簇。 图3 + i 网络丹簇拓扑凹 所谓多对一的通讯指：在簇内形成一颗转发树，由于簇首节点是数据是该区域 的最根节点，所有数据最终必然借助于该节点才能将数据发送出去，因此在每轮周 期内，簇内所有成员节点最终都要将数据传送给簇首最后通过簇首节点将数据转 发给基站。由于传感器节点位置周定，在每轮时隙周期内算法根据传感器节点数据 量自动地划分时隙大小，需要每轮预知节点所需要发送的量。每个簇内形成多对一 通讯的工作，类似于树型结构。a t s a 算法在每个簇内，根据形成的多对一通讯的 树来t 作，其中簇首为树的根节点，任何成员节点只能通过树来确定发送路径只 能将数据发给上一层双亲节点，由上一层双亲节点向上传输最终发送到树根节点， 节点不能向下传输数据。 硕士学位论文 m a s 丁e r st h e s i s 3 3a t s a 算法基本思想 a t s a 算法由树构造阶段以及若干轮的数据组成，每轮数据又可以分为准备阶 段和数据传输阶段两个部分。 ( 1 ) 准备阶段：该阶段在帧内的占有时间较长，主要根据路由树来决定节点的 路径信息，根据路径信息节点明确自己所处树的位置。由于a t s a 算法通过分簇降 低设计的规模，所以在每个簇内，在每轮需要分配的时隙帧内，动态地调节自己需 要发送的数据量来计算自己需要转发数据的时隙大小，簇首节点根据分配原则为成 员节点分配合理时隙的顺序，避免冲突的发生。所有节点都根据处于树的层次来实 现之间的通讯，只关心需要自己转发数据的时隙以及自己的工作时隙，别的时刻可 以进入能量节约状态。算法需要完成所有节点的时间确认问题。 ( 2 ) 传输阶段：节点根据自己工作时隙，打开模块，完成数据的转发工作。不 处于自己的时隙内，继续保持休眠状态。在数据发送过程中还需要对算法进行评价， 利用由于时隙没有及时调整大小而有剩余部分的时间内完成。完成所有节点数据发 送工作以后，进入轮询状态，开始下一轮的工作 3 4a t s a 算法设计 3 4 1 树的构造 树的构造主要基于每个簇内节点的位置信息，与周围节点连通情况。通过这些 信息可以建立普通节点到基站路由路径。树构造完毕以后，每个节点获取自己树中 的层次、双亲节点：孩子节点、邻居节点等信息。通过该树可以动态的调整节点接 受或发送数据需要的能量，节点主要通过选取最小跳数传输数据实现能量高效利 用。处于树中间的传感器节点既需要发送自己感知的数据，同时也需要转发下一层 节点的数据，因此节点工作量比较大，这就对整个网络生命周期有较大的影响。在 树构造时候采取适当的控制策略，避免某个节点由于下一层节点比较多造成节点工 作量过大，同样如果树中某个分支深度过长也会给该分支最上层节点带来较大的负 载。如何合理地构建数据转发树是比较棘手的难题，对a t s a 算法性能有着直接的 影响。a t s a 不考虑如何分簇，假定已经分簇完毕，不失一般性设定节点分布均匀， 每个簇内构造树构造策略主要步骤如下： ( 1 ) 簇首为r o o t 节点，首先由簇首广播消息bc h , 一跳内成员节点收到消息 发送确认消息a c k 确认自己为树的第二层节点，记录自己的信息。簇首收到a c k 1 4 硕士学位论文 m a s t e r st h e s i s 消息后，发送a c ks 消息。节点收到确认消息a c ks 后发送广播消息cc h 来确 定每个节点一跳内的邻居节点，并记录邻居节点的信息。 ( 2 ) 位于第二层节点一跳范围内的节点，根据收到的广播消息cc h 计算距离 自己较近的处于第二层的节点，向该节点申请加入分支消息r t s ，位于第二层节点 根据已经加入的节点数目决定是否接受该申请并发送返回消息c t s ，如果失败就选 取另外一个分支加入，如果该节点只要唯一的邻居节点就强行加入。 ( 3 ) 以下节点依次类推加入分支，同时在加入分支时候考虑节点所位于的层次， 如果长度过深，就从上层的邻居节点中选取新的双亲节点加入。 ( 4 ) 最后由叶子节点向上发送确认信息，各层节点确定消息并向上转发确定整 个树的拓扑。 在构造完毕后，所以节点都需要记录该节点所处于树中的位置、上一层节点、 下一层节点、一跳范围内的其他层次等信息。 3 4 2 时隙大小的划分 在分配新一轮节点时隙时，如果节点m 的上一轮时隙为如，发送数据的平均速 率为研，则节点上一轮发送数据量为s i 抱，节点缓冲区数据量为白。式( 3 1 ) 节点 计算这一轮数据量，其中r 表示这一轮与上一轮期间时间内产生的数据量，尼表 示这一轮孩子节点传输的资料量，西一s i * t il 表示还没有发送的数据量。f o 如式( 3 2 ) 所示，其中m i 表示上一轮节点m 数据生成平均的速率，m 表示该轮孩子节点个数， m ：表示这一轮孩子节点时隙内该节点生成的平均速率，t ，表示该轮对应孩子节点的 时隙，z 为该轮孩子节点的数目。记剩余数据量权值为p ，。 f = 岛( f o + 互) 十b 一s t 宰) ( 3 1 ) 厂一 朋 、 ， e = 砚l 一l + 以 。 ( 3 2 ) - - 1 i = l i = l 假设c n l 为叶子节点，那么该最下面一层节点由于没有其它节点，所