基于Crossbow平台无线传感网中跨层优化算法的研究.pdf

g 锄e r a l l yt 1 1 e r ea r ef o u rl a y e r s ，h e i lw ed i s c u s sw s n t h e va r e 印p 1 1 c a t l o nl a y n e t 、) l ，o r kl a y m e d i 啪a c c e s sc o n 仃0 1 ( m a c ) l a y e r 锄d p h y s i c s1 a mt h es e l l s o rn o d e sa r eo r 锄s u p p l i e d 谢t l lb a t t e r i e s ，a i l di t ，sn o t e a s y 士o rr 印i a 血gt h eb a t t 哪s ot 1 1 ee n 唧c 0 n s 啪p t i o ni sc o n s i d e 川觞 t h em o s tm p o r t 锄tf a c t o ri nw s n ，a n dt h j si sn l ed i 脑e i l c eb e 帆e e i lo 廿l e r n 咖o r ka n dw s n a uo fa b o v ef o u r 1 a y e r sn e e dt 0r 酣u c e e r g y c o n s u m p t l o n ，a n dm o s tp r o t o c o l sa r ep r o p o s e di nn e 帆o r kl a y e r 锄dm a c l a y 既i nn e t 、) l ，o r kl a y w s ni sc o n s 仃u c t c dw i t l ld i f j 陆e n tc l u s t e r sa i l de a c h c l u s t e rh e a di sr e s p o n s i b l ef o rc o n v e r 百n gd a t a r o mo t h e r n o d e si ni t sc l u s t 既 i nm a cl a y n o d e sa r ea s s i 印e d 、) i ，i n l a p p r 0 州a t es c h e d u l e s 觚ds o m e m e d l 啪a c c 船ss c h e n l e衙r e d u c i n gc o l l i s i o n n e s e铆o1 a y e r si s o u r o p t i m i z e dt a r g e t jn e r eh a v eb e e nm a l l yp r o t o c 0 1 si 1 1 w s n ，s u c h 嬲l e a c h ，h e e di n n 咖o r k1 a y e r 缸ds m a c ，t m a ci nm a c l a y 既t 1 1 em a cp r o t o c o lc a n r e d u c e l ei n t e r f 柏l c e 锄dc o l l i s i o ni 1 1 n 钟w o r k ，b u ti ti sn o ts u i t a b l ef o r l a r g en e t 、o r k t l l en e 铆o r kp r o t o c o lo r e i ls e l e c tc l u s t e rh e a d sr a n d o m l y a n d 也es e l e c t e dc 】u s t e rh e a dm a yb en o tt 1 1 es u i t a b l eo n e i nn e t 、) l ，o r k 1h l sp a p e rt i r s tp r o p o s e d 姐a d a p t i v e 仃孤s m i s s i o ns c h e m eb a u s e d o n 锄铝饥c yt o r h e t e r o g e n e o u sn 咖o r kc o n v 鹕e n c e w i t l ln l e 鼬s i s t 锄c eo f 础l u l a rn e 柳。咄也i ss c h e l i l ec a na c h i e v el o wp a c k e tl o s sr a t i o a n dl o w i a t 锄c y 仃锄s m l s s l o nt 0g a t 聃a y t h i ss c h e m ec 锄 a l s 0r e d u c e锄e r g y c o n s u i 】1 p t l o no fs c i l s o rn o d e 锄di n e 懿et l l el i f e t i m eo fn e 咐o r k a r e r e i i l e 唱e 1 1 c yd a t a 臼讹s m i s s i o nf i n i s h e d ，t h j ss c h 锄e0 p t i m i z e dt 1 1 en e “r k t o p o 】0 星弘 t l l i sp 印e rt l l p r o p o s e dan e w p r o t o c 0 lc a l l e d 黜n gc l u s t 嘶n gb 嬲e d o na b o v ep r o t 0 c 0 1 s 1 1 1n e 帆o r kl a y n o d ew i 廿1 t l l el e 懿tc o s tv a l u ei s i v 浙江大学硕士学位论文abstract s e l e c t e da sac l u s t e rh e a d t h ec o s tv a l u ei sd e t e n n i n e dn o to n l vb vc o s t i n t r a - c l u s t c rb u ta l s ob yc o s ti n t e r _ c l u s t e ls ot l l i sc o s tc a i lg u a r a n t m em o s t s u i t d b l ec l u s t e rh e a dc 觚b es e l e c t e d a l lt l l en o d e sa r en o tc l u s t e r i n ga tt h e s 锄et i m e h o w e v e r ，t h en o d e sa r cc l u s t 耐n gj 6 f o mi i l l l e rb o a r dt oo u t b o a r d i nr i n g ，j u s t1 i k eaw a t e rw a v e h lm a c1 a y w ea d o p ts u i t a b l es c h e d u l e b 嬲e do nc sma c a ，锄dm a k ei n 乜a c l u s t e rc o m m u n i c a t i o n 觚di n t e r - c l u s t e r c o m m u n i c a t i o n 1 1 o u g hd i 毹r e l l tc h a l l l l e l s t h e s es c h e m ec 锄r e d u c et h e i i l t e r f e r e n c eb e t 、) i r e 即 n o d e s t h eg o o ds i m u l a t i o nr e s u l t sv a l i d a t et h e e f f i c i 胁c yo f 黜n gc 1 u s t 丽n gp r o t o c 0 1 k e y w o r d s ：w i r e l e s ss e i l s o rn e m o r kc s m c 八h e t e r o g e n e o u sn e 呐o r k c o n v e 唱e 1 1 c e ，l e a c h ，c r o s s l a y e ro p t i m i z a l i o n v 一 浙江大学硕士学位论文目次 目次 致谢。i 摘j l ：i i a b s t r a c t i v 目次1 r i 1 绪论。 1 1 课题研究背景1 1 1 1 无线传感网概述l 1 1 2 无线传感网层次架构l 1 1 3 开发平台简介2 1 2 课题研究现状3 1 3 论文的主要工作及结构 1 3 1 主要工作3 1 3 2 论文结构4 2 网络层协议综述 2 1 l e a c h 协议 2 2 h e e d 协议 9 2 3 其余成簇协议1 3 2 4 本章小结 3 m a c 层协议综述 3 1 s m 渔c 协议。1 6 3 2 t m a c 协议1 7 3 3 c s m a c a 机制 ：! o 3 4 其余m a c 协议2 3 3 5 本章小结2 6 4 异构网络紧急事件应对机制。2 7 4 1 背景介绍2 7 4 2 紧急事件应对机制。2 8 4 2 1 场景描述 2 8 4 2 2 最优发射功率选择算法。2 9 4 2 3 自适应传输机制3 l v l 浙江大学硕士学位论文目 次 4 3 仿真结果3 2 4 3 1 仿真参数设定3 2 4 3 2 仿真结果分析3 3 4 4 总结3 5 5 环形组网机制3 7 5 1 多跳传输。3 7 5 2 环形组网机制。3 8 5 2 1 权重值的计算4 0 5 2 2 选簇流程( 网络层) 4 2 5 2 3 数据传输( m a c 层) 4 6 5 3 性能仿真。4 7 5 3 1 仿真参数4 7 5 3 2 仿真结果4 8 5 4 总结。 结束语。 5 0 ! ；：! 参考文献 攻读硕士学位期问主要研究成果 一v l l 一 5 3 5 7 浙江大学硕士学位论文绪论 1 绪论 1 1 课题研究背景 1 1 1 无线传感网概述 随机分布的带有传感器、数据处理单元和通信功能的节点，通过自 组织的方式构成的无线网络称为无线传感网( w s n ，l e s ss e i l s o r n 咖o r k ) 近年来成为了一个新的研究热点借助于节点内的传感器， 根据应用场景的不同，传感网可采集温度、湿度、噪声、光强、移动物 体的速度大小和方向等各种信息。然后通过数据处理单元，将采集到的 数据进行分析、筛选和融合，形成有效的可供通信的数据包最后通过 通信模块采用相应的通信协议将数据传输至应用中心。实际上这样一个 过程实现了远程采集数据的功能，避免了人工收集数据所带来的风险和 麻烦正是由于其有着上述优点，因此无线传感网技术有着广泛的应用 市场，如环境监测、医疗系统、机器人探测以及军事目标的监测 无线传感网有如下特点【1 1 ：( 1 ) 大规模、高密度的空间分布；( 2 ) 能量受限：传感网节点一般采用电池供电，而根据其应用的特性，节点 一般分布在环境恶劣、人烟稀少的地区，所以其电池的更换或充电尤为 不易因此需要尽可能的减小网络功耗、增加网络寿命；( 3 ) 网络的自 识别，防止未授权用户的侵入针对上述特点，目前无线传感网中的研 究大部分都是基于减小能耗和延长网络寿命这一目标，这也是无线传感 网与其他网络最为不同之处。 1 1 2 无线传感网层次架构 一般而言，我们把无线传感网分为四层，如图表1 1 所示，自上而 下分别为：应用层，网络层，媒体接入控制( m a c ，m c d i 啪a c c e s sc o n 仃0 1 ) 层和物理层 浙江大学硕士学位论文绪论 应用层 j e 网络层 j e 媒体接入控制( m a c ) 层 j e 物理层 图表1 1 无线传感网架构 由于无线传感网节点只进行简单的数据处理，因此没有必要设置更 高的层，一般而言，应用层进行业务的分级，数据的融合以及数据包的 生成工作。网络层也称为路由层，主要负责组网时信令的控制，簇头的 选择以及数据传输时的路由发现和路由选择m a c 层则负责醒睡周期 的调度，信道的分配和接入以及网络地址和物理地址的转换。物理层与 其他无线网络类似，负责数据的编码、交织、调制以及最终的发送和接 收。 1 1 3 开发平台简介 美国c o r s s b o w 公司发开出了适用于传感网研究的平台，采用 t i n y o s 操作系统和n e s c 语言进行软件的开发，硬件上则采用英特尔与 加利福尼亚州大学伯克利分校联合研制的微尘节点，目前主流节点型号 有m i c a z ，m i c a 2 和瓜i s 三种，各型号节点的配置如图表1 2 所示，目 前传感网络中的小型实现基本上是基于该平台完成的。 节点类型 m i c a zm i c a 2i r i s 微处理器a t m e g a l2 8 l a t m e g a l2 8 l a t m e g a l 2 8 1 射频 c c 2 4 2 0 ( 2 4 g h z )c c l o o o ( 4 3 3 m h z ， i 心2 3 0 ( 2 4 g h z ) 9 16 m h z ) 图表1 2 各节点配置 一2 一 浙江大学硕士学位论文绪论 1 2 课题研究现状 目前无线传感网吸引了一大批学者的目光，其主要研究目标便是在 保证数据传输可靠性和及时性的条件下，如何减小网络的总能耗，延长 网络的生命周期。目前研究的比较多的是无线传感网的网络层和m a c 层。 在网络层的研究主要是针对组网的机制，簇头的选取等方面。2 0 0 2 年，m jh a n d y 等人提出了l e a c h 协议【2 1 ，该协议主要通过随机选取簇 头，然后周期性的更新簇头来达到网络中所有节点能耗的平均性，从而 延长整个网络的生命周期。但是这样选出来的簇头并不能保证是最优簇 头，导致网络中节点能耗还是有一定概率的不平均性。相比而言，h e e d 协议【3 1 则是一个优化，该协议考虑了节点分布的密度和节点的剩余能量， 一定程度上能选出合理的节点。但是由于考虑时只考虑了簇内节点的分 布密度，未考虑簇间节点之间的分布，所以选出的簇头仍然不是最优的 簇头。 在m a c 层的研究工作则主要是针对调度机制以及信道接入的控制 y ew 葫等人于2 0 0 2 年提出了s m a c 协议【4 】【5 】，该协议旨在降低节点能 耗和提高网络吞吐量。针对传感网中能耗的四大原因：空闲侦听、碰撞、 串听和控制开销，s m a c 一一提出了机制将其解决，并提出了采用周期 性的醒睡机制来有效减小节点的空闲侦听能耗。在s m a c 基础上，t v 抽 d 锄等人于2 0 0 3 年提出了t m a c 协议【6 】，由于周期性的醒睡虽然可以 减少很多能量开销，但是一些节点醒着的时候仍然处于空闲状态，所以 t m a c 协议针对这一点继续提出优化机制，使节点处于空闲状态的时间 更短，从而进一步减少了能量消耗。 1 3 论文的主要工作及结构 1 3 1 主要工作 本文的工作主要是综合现有的网络层和m a c 层协议，针对无线传 感网能量受限的问题，提出一种基于异构网络融合的紧急事件应对机制 一3 一 浙江大学硕士学位论文绪论 和一种新型的环形组网跨层协议 传统的异构网络融合中针对紧急事件的应对机制并不多，多数应对 机制都是只在传感网内部完成，而通过异构网络、特别是蜂窝网络的辅 助，在紧急事件发生时节点能够快速、低能耗的将紧急事件发送至网关 或数据中心，使得相关部门能够迅速的采取相关应对措施，避免广大人 民财产的损失 相比传感网内部针对紧急事件处理的r t d d 机制，新型的基于异构 网络融合的紧急事件应对机制在丢包率，平均延时等性能参数上均有显 著改善。 环形组网跨层协议中在网络层，所有节点采用环形由里向外依次组 网，而非同时组网。同时，数据通信时支持多跳通信，从而使整个网络 的覆盖范围扩展到更远由于多跳机制的引入，在选取簇头时不能仅仅 考虑节点在簇内的通信代价，还需考虑节点在簇与簇之间的通信代价。 为了能够选出较为合适的簇头，给每个节点分配了一个权重值，该权重 综合考虑了能耗，簇内节点密度，簇间通信距离等因素，能保证所选簇 头的最优性，在成簇时簇内通信范围内的节点中权重值最小的节点成为 簇头该选出的簇头能保证通过该簇头收集和转发数据，跟簇内通信范 围内通过其余节点收集和转发数据相比，所消耗的整体能量是最少的 在m a c 层，引入了s m a c 周期性醒睡机制来降低能耗，同时在传 输数据时采用c s m c a 机制来避免碰撞，保证数据传输的可靠性在 簇内通信和簇间通信时，由于两者的发射功率不同，为了避免大功率发 射所带来的干扰，采用不同的信道进行数据传输。 相比经典的组网协议，如l e a c h ，h e e d 等，本文提出的环形组网 机制能够在不加大发射功率的情况下扩展无线传感网的覆盖范围，同时 保证数据传输的可靠性，为今后的大规模传感网组网奠定了坚实的基础。 1 3 2 论文结构 本文提出无线传感网中一种新型的环形组网机制，并将该机制与已 有的协议进行比较 一4 一 浙江大学硕士学位论文绪论 第一章，简要介绍了课题研究背景及意义，对目前无线传感网中已 有的协议做出简要分析与回顾，并概要说明了本文的主要工作及论文的 结构。 第二章，详细介绍目前已有的网络层的组网协议。 第三章，详细介绍目前已有的m a c 层的一些机制。 第四章，介绍一种新型的基于异构网络融合的紧急事件应对机制。 第五章，综合分析已有的网络层和m a c 层协议的优劣性，并在此 基础山提出新型的环形组网机制，最后将该机制的仿真结果与传统机制 的仿真结果进行对比。 结束语将对全文进行归纳概括，并介绍可以开展下去的相关后续工 作。 一5 一 浙江大学硕士学位论文网络层协议综述 2 网络层协议综述 2 1 l e a c h 协议 作为无线传感网中经典的组网协议，l e a c h 【2 】【7 】【8 1 ( l 0 we n e r g y a d 印t i v ec 1 u s t e r i n gh i e r a r c h y ) 凭借着其随机成簇的理论，成为了后来许 多学者研究的重点协议和基础比较标准。 l e a c h 协议是一个自组织自适应成簇协议，它使得整个网络节点的能 量消耗较为平均，而不是突出在某个节点上。其节点分布如图表2 1 所示。 4 5 加 3 5 2 5 加 i 1 5 1 0 5 o 8 o 。：。o o 二 。 。 - 。 。- o oo o o o o o o 。l o o ：o ；：。o ! ：。：o7oo o i a io o_ = 2 01 51 0 5o51 01 52 0 图表2 1 l e a c h 节点分布图 上图中的节点根据成簇算法组成簇，每个簇选出一个簇头，负责收 集簇内其他节点的数据然后转发至基站按照l e a c h 协议以往的成簇 协议，簇头是固定并且不更换的，这样可以预见簇头节点的能量会在很 短的时间内耗尽，从而导致簇内其他节点收集到的数据无法传输至基站 l e a c h 协议开创性的提出了周期性的簇头更换机制，并且使不同的节 一6 一 一0 o 。 o 。 oo 浙江大学硕士学位论文网络层协议综述 点轮流充当簇头，避免了其中某一个节点能耗过快。同时，簇头不仅仅 是单纯的转发簇内节点的数据，而是先进行压缩后转发，降低了簇内的 能耗，延长了网络中的生命周期。 每隔一个周期，每个节点以一定的概率选取自己为簇头，选出的簇 头将自己充当簇头该消息广播至网络中的其余节点。其余未被选为簇头 的节点收到多个簇头申明消息后，根据传输数据至簇头所需消耗的能量， 选取消耗能量最小的簇头成为其簇头并加入该簇。待所有节点都成簇后， 簇头给簇内的节点安排合适的调度计划，这样簇内的节点只有在调度中 规定的时间醒来传输数据至簇头，在其余时刻睡眠以节省能量。而且由 于不同节点醒来的时间也不同，因此避免了数据传输产生的碰撞和干扰。 簇头收集到节点的数据后将其压缩传输至基站。由于簇头与基站的距离 很远，因此簇头与基站之间的传输需要消耗很大的能量，远大于簇内通 信的能量。 正如前面所说，由于簇头消耗能量太大，簇头能量会很快耗尽。为 了使多个节点平摊能耗，在不同的时刻需更换簇头也就是说在t 时刻 是一组簇头，而在t + d 时刻则是另一组簇头，如图表2 2 所示图中黑 点表示簇头。是否选取自己为簇头依据节点的剩余能量而定，也就是说， 某节点是否成为簇头与其余节点无关，因此也不需要与其余节点的通信 协商而网络中簇头的个数则是需要根据多个参数而定 l e a c h 协议将更换簇头所需的一个周期称为轮( r o u n d ) ，每一轮分 为两部分：组网阶段( s c t u pp h 勰e ) 和稳定阶段( s t e a d y s t a t e ) 。 在组网阶段，首先节点需要计算是否选取自己为簇头。每个节点会 在0 和1 之间产生一个随机数，如果该随机数比门限值t ( n ) 小，则该节 点选取自己成为簇头，否则不选。t ( n ) 的定义如下： 丁( 行) = i f 刀g ( 2 1 ) 0 t l l e r 、衍s e 其中p 表示设定的簇头百分比，r 表示当前的轮数，g 表示在前1 p 轮中没有成为过簇头的节点。在初始轮( 产o ) ，每个节点以p 的概率成为簇 一7 一 南 o 浙江大学硕士学位论文网络层协议综述 头，然后在接下来的l p 轮中这些节点将不会成为簇头。以此类推，每 个节点在l p 轮中都会担当一次簇头。 图表2 2 动态簇头 当节点被选为簇头后，该簇头向其余节点广播消息，发送时采用 c s m a 协议。接收到多个簇头广播消息的节点根据接收到的信号强度选 择传输消耗能量最小的簇头作为它的簇头选出之后，节点需要发送一 个反馈信息至其簇头，告知簇头该节点成为该簇的成员节点，发送反馈 信息同样采用c s m a 协议。 当所有节点都已成簇，即所有节点的反馈信息都已被簇头收到，簇 头根据簇内节点的个数制定一个t d m a 的调度计划，然后将该计划广播 一8 一 浙江大学硕士学位论文网络层协议综述 至簇内成员节点。至此组网阶段结束。 在稳定阶段，由于簇头已经选取，路由已经建立，节点开始进行数 据传输。节点传输时采用簇头所分配的t d m a 调度计划，在其所分配的 时隙中传输数据簇头在收到节点传输的数据后，开始进行数据压缩并 转发至基站，为了避免不同的簇之间传输数据产生干扰，每个簇通信时 采用不同的c d m | a 编码。 l e a c h 协议开创性的提出了周期性的更换簇头机制，平均分摊了 节点的能耗，延长了网络的生命周期。但是其选取簇头时是轮流选取， 即每个节点依次成为簇头。如果某个节点的通信环境很差，距离基站也 很远，不适合担当簇头，那么该节点在一个循环中也会成为簇头；而某 个节点通信环境很好，距基站较近，且能量充足，适合担当多次簇头， 那么该节点在一个循环中只能担当一次簇头l e a c h 协议看似公平， 实际上并没有依据每个节点的不同条件选出最合适的簇头同时， l e a c h 协议假定所有节点都可以一跳到达基站，这样当网络覆盖范围 很大时，处于网络边缘的节点发射功率可能无法满足一跳到达基站，即 使能满足，那么消耗的能量也是巨大的。综上所述，l e a c h 协议有利 有弊，还是有很多改进之处。 2 2 h e e d 协议 h e e d ( 3 】( h y b r i de n e r | g y e 伍c i 朗td i s t r i b u t e dc l u s t 嘶n g ) 由o y o u n i s 等人于2 0 0 4 年提出，该协议基于l e a c h 协议周期性的更换簇头，但是在 选择簇头时增加了权重值的考虑，使得选出的簇头更合理 h e e d 协议所提出的场景基于以下假设： ( 1 ) 节点几乎是静止不动的； ( 2 ) 每个节点的能量消耗是非均匀的； ( 3 ) 节点没有装配g p s ，也就是说，节点是不清楚自己的绝对位置的； ( 4 ) 所有节点具有相同的通信和数据处理能力，不存在超级节点； ( 5 ) 节点在配置完成之后，初始状态为未组网； ( 6 ) 节点具有不同的发射能级，即可根据距高调整相应的发射功率 一9 一 浙江大学硕士学位论文 网络层协议综述 h e e d 协议的首要目标便是延长网络的生命周期，所以说，簇头的 选取主要依赖于节点的剩余能量。同时，除了需考虑当前节点的剩余能 量，还需考虑到该节点成为簇头后该簇内所有节点的能量消耗，该能量 消耗称之为“通信代价” h e e d 使用能量因素来粗略筛选出一组符合要求的簇头，然后使用 通信代价来进一步挑选出最合适的簇头。选出合适的簇头意味着在邻居 范围内只能存在一个簇头，该邻居范围指节点使用较小的发射功率所覆 盖的一个范围。通常节点会使用较小的发射功率来进行簇内通信，而用 较大的发射功率来进行簇间通信。因此，簇间通信功率的覆盖范围是簇 内通信功率覆盖范围的两倍或者更多 在使用通信代价筛选簇头时，能使簇内通信所消耗能量最小的节点 应该被选为簇头，即通信代价最小的节点被选为簇头。因此通信代价跟 簇的大小相关，通信代价还跟所要建立的网络类型相关。如果目标是建 立一个能量均衡的网络，即尽可能的平摊簇头的能耗，那么通信代价应 该跟簇的大小成正比；如果目标是建立一个密集的网络( 可能会带来更 多的簇内干扰，但会使空间利用率增加) ，那么通信代价应该跟簇的大小 成反比 与l e a c h 协议类似，一个周期也分为类似的组网阶段和数据传输 阶段，不同的是需要将组网阶段分为更小的一组重复阶段，每个小阶段 称之为“反复”每个反复的时间应该足够长以保证一个节点能够收到其 邻居范围内任意一个其他节点的消息。初始时先设置所有节点中簇头的 百分比q 栅，那么每个节点成为簇头的概率c h 舢计算如下： c h 岫= c 呻_ 等燃 f - 眦 ( 2 2 ) 上式中e 训删表示节点的当前剩余能量，e 嗽表示节点最大能量( 即 电池满时的能量) 。在确定了节点的选簇概率后，整个组网阶段的流程如 图表2 3 所示： 首先是初始化阶段，初始化阶段首先计算自己的通信代价，然后将该 通信代价广播至邻居表内的所有其他节点接着所有节点计算自己的选簇 一1o 一 浙江大学硕士学位论文网络层协议综述 i i n i t i a l 娩e 、 s n b r 一和：vt i e sw i t h 汛m y c t t t s t e rr 傩g e 2 c o r i p t l t e 口n db r o a d c q s tc o s tt o s n b r 3 6 - m 觚伟啪讹口，厄赢，p 舶 4 b j 嘀l s h 卜f a l s e r e p e a t 5 玎( s c h 七一f v ：vi sa c t t l s t e rh e n 田)g ) 6 m y l t t s t e r e a d 卜t e 口s t j 0 s t ( s c 曲 ，1 酵w j l t l s t e r e 融= n o d e i d 8 v ( c h p r o b = 1 ) 9 c l 榔t e r e n d m s g ( n o d e i d ，矗n 口l c h c o s t ) 1 0 f 蛳以口l c 日卜豫吧 !1e厶p u c h t e r j e a d j s g ( n 0 d e i d 。t 吼t m 如e s h 。c o s t ) n 。 e l s e 醇( c h p r o b = 1 ) 、4 c t u s t e r j e 甜舅g ( n 0 d e i d 彝n c l l s h 。c o s t ) 1 5 过撇l c 日卜豫汜 1 6 上泌p 矿r 口砌肌佃矽= c 无加6 1 1 1 c h l s t e r e 8 d m s g ( n o d e i d t e n t n t i v e c h c o s t ) 1 8 c e 坨1 ，勋凇- c e 厂d 6 1 9 c 己m 6 卜m 觑f ，c 加6 2 ， u n t na 淞= 1 i i i f i n a l 娩e 构 v ( i s j 舱l s h = f a l s e ) n 黟“s c h 卜和：vi s 口奔n q tc l t l s t e rh e q 螂)o ) 2 2 唧j l t l s t e r j e 积卜t e t j 0 s t ( s c h ) 2 3 j 0 讯j l s u t e r ( c h l s t e r 上e 口d - 王d n 0 d e i d ) 2 4 e l s ec l t l s t e r e 口d s y ( n o d e i d 矗m l h c 0 s t ) 2 5 e l s ec i u s t e r j l e n d m s y ( n 0 d e i d 矗n a l c h 。c o s t ) 图表2 3 h e e d 流程伪码 概率，为了保证“反复”的次数有限，需设定一个门限值，如果本节点 的选簇概率低于该门限值，那么设定新的选簇概率为该门限值这样做 一1 1 浙江大学硕士学位论文网络层协议综述 的目的在于保证一个最小的选簇概率。 初始化阶段完成后，节点进入到“反复”阶段。每个节点会维护一 个临时簇头链表s c h ，如果其收到任何一个其余节点的临时簇头广播消 息或者自己选为临时簇头，那么它将该临时簇头节点加入s c h 。在第一 个“反复”开始前，s c h 清空。按照图表2 3 所示，在第一次反复执行 时由于s c h 为空，且选簇概率小于1 ，那么所有节点与l e a c h 协议类似， 产生一个0 到l 的随机数，如果该随机数小于其选簇概率，那么该节点 宣布自己成为临时簇头并向邻居节点广播，收到该广播消息的邻居节点 将该节点加入s c h 。在每个反复结束时，每个节点都需要将其选簇概率 翻倍，如果翻倍后的选簇概率大于l ，那么设定新的选簇概率为1 ，否则 新的选簇概率设定为翻倍后的选簇概率。进入下一个反复时，节点就需 要对s c h 进行判断，如果为空且选簇概率小于1 ，那么重复第一次反复 的过程；如果选取概率为1 ，那么意味着该节点在一段时间内都没有收 到其邻居节点的临时簇头广播消息，该节点将直接宣布自己为最终簇头 并结束“反复”阶段。如果s c h 非空，那么节点会在s c h 中选出一个最 小通信代价的节点作为其簇头。如果最小通信代价的节点恰好是本节点， 那么需要根据此时的选簇概率来判断，如果选簇概率为1 ，那么宣布自 己为最终簇头并结束“反复”阶段，否则继续广播临时簇头消息。 最后，在所有“反复”阶段结束后，仍未成为最终簇头的节点从s c h 中挑选出一个通信代价最小的簇头作为其簇头，并向该簇头发送入簇请 求，至此整个组网阶段结束 由上述的组网阶段步骤可以看出，由于设定了最小的成簇概率，而 且每过一个“反复”成簇概率都会翻倍，因此在有限的反复次数内，该 成簇概率肯定会达到1 。在成簇概率达到1 后，满足条件的节点成为最 终簇头，而不满足条件的节点s c h 肯定非空，即其邻居节点中至少有一 个最终簇头，那么该节点可以找到合适的最终簇头并加入 从整个h e e d 组网过程中可以看出，h e e d 协议达到了下列要求： ( 1 ) 成簇过程是完全自组织的，每个节点只根据本节点的信息来做出选簇的 决定： 一1 2 浙江大学硕士学位论文网络层协议综述 ( 2 )无论网络有多大，成簇过程必须在有限的时间内完成； ( 3 ) 在组网阶段完成后，每个节点只可能处在簇头状态或者某簇的成员节点 状态，不可能处于第三种状态； ( 4 ) 成簇过程中的信令交互和处理复杂度尽可能的小； ( 5 ) 选出的簇头在整个网络中分布的很平均。 作为成簇协议中的另一个经典协议，h e e d 在继承了l e a c h 协议 周期性的更换簇头这一个优点的基础上改进了l e a c h 协议，选出了合 适的节点充当簇头而非轮流担任。在h e e d 协议中，剩余能量越大且通 信代价越小的节点将有越大的概率被选为簇头但是其通信代价只跟簇 的大小有关( 成正比或反比) ，与簇内节点通信的平均距离无关，这也是 不公平的。假设两个簇都有同样个数的节点，其中一个簇节点分布的比 较紧凑，而另一个簇节点分布的比较稀疏，那么比较紧凑的簇中所有节 点发送至簇头的能量消耗要比稀疏的簇中所有节点发送至簇头的能量消 耗要小得多，因此紧凑的簇头应该比稀疏的簇头有更高的概率能够被选 为簇头。同时，在网络范围扩大到需采用多跳传输时，h e e d 协议并没 有考虑到多跳传输时的簇间通信代价问题。上述问题是h e e d 协议的不 足之处，而在本文提出的环形组网机制中这些不足得到了较好的解决。 2 3 其余成簇协议 除了上述的l e a c h 与h e e d 协议外，还有许多其他的成簇协议， 在此简单介绍之： e e c s ( e n 钉g ye 衔c i e i l tc 1 u s t e 血gs c h 锄e ) 【9 1 协议提出在每一轮中由 临时簇头竞争最终簇头。首先所有的临时簇头将其剩余能量信息广播告 诉其邻居节点，若某节点没有发现另一个比它剩余能量更多的节点，那 么该节点宣布自己成为簇头同时，在簇的大小确定上，e e c s 不同于 l e a c h 协议l e a c h 协议中规定簇的大小取决于节点到簇头的最小距 离，而e e c s 在这基础上改进了该机制e e c s 认为离基站越远的簇头 传输数据至基站所消耗的能量要远远大于离基站近的簇头，所以e e c s 依据簇头到基站的距离来决定簇的大小：距离基站越近，则簇越大；距 一】3 一 浙江大学硕士学位论文 网络层协议综述 离基站越远，则簇越小。通过动态决定簇的大小，网络的能量分布变得 均匀，网络的生命周期也得以延长。但是靠近基站的簇可能会导致网络 拥塞从而导致簇头的过早死亡。 e e u c ( e n 哪y - e 佑c i e n tu n e q u a lc l u s t 舐n g ) 【1 0 】算法也同样考虑到动 态决定簇的大小。但是不同于e e c s 的是，e e u c 协议认为在多跳网络 中，由于靠近基站的簇头要担当更远簇头的中继簇头，所以其能量消耗 要快的多导致过早死亡。因此e e u c 提出越靠近基站的簇的范围要越小， 而远离基站的簇的范围则越大事实上，e e u c 与e e c s 类似，两者都 基于距离因此要求每个节点都知道各自的地理位置以及与基站的距离。 e e u c 延长了网络生命周期、均衡了网络中各节点的负载、解决了热点 问题：簇的大小与其到基站的距离成正比。但是，它同样带来了额外的 数据整合开销，因此降低了网络的一些性能。 e e h c ( e n 够g ) re 伍c i e n th i e r a r c h i c a lc l u s t 嘶n g ) 】协议是一个自组织 的随机成簇协议，簇头负责收集成员节点的数据并将其整合发送至基站 e e h c 分为两个阶段：初始化阶段和扩展阶段。在初始化阶段，每个节 点以相同的概率随机成簇，担任临时簇头。然后临时簇头将其成簇消息 广播出去，收到该消息的非临时簇头节点选择最近的簇加入。既没有成 为临时簇头也没有收到成簇消息的节点则成为被动簇头在扩展阶段， 簇头与基站建立一跳或多条连接。这样做的好处在于降低了远离基站的 簇头的能耗，但是由于靠近基站的簇头需要作为中继簇头，因此增加了 它们的能耗 m i 冲u c ( m u l t i h o pr o u t i n gp r o t o c 0 1w i t l lu n e q u a lc 1 u s t 甜n 曲1 2 】协议 也是夜歌分布式协议其每轮分为三个阶段：簇的建立，簇问路由建立 和数据传输。在第一阶段，每个节点收集其邻居节点的相关信息并选取 出具有最大剩余能量的节点作为簇头同样的，靠近基站的簇其覆盖范 围也更小其余节点选取距离越近的且剩余能量越大的簇加入第二阶 段，建立起远端簇头至基站的多跳路由。第三阶段，数据以多跳的方式 传输至基站由于选簇时考虑了节点的剩余能量并且建立簇问路由时也 考虑了中继簇头的能量，因此靠近基站的簇头也不会过早死亡类似的， 一1 4 浙江大学硕士学位论文网络层协议综述 簇间多跳路由的建立会带来额外的开销。 前面提到的各类成簇协议由于成簇信息的交换，都会带来额外的能 量消耗，尤其是在节点密集分布的无线传感网中。p e a c h ( p o w * e 伍c i e n t 锄da d 印t i v ec 1 u s t 出n gh i e r a r c h ”【1 3 】协议很好的解决了 这一问题，降低了网络的能耗，延长了网络的生命周期。在无线传感网 中，串听是不可避免并且有可能带来能量的浪费，而p e a c h 协议正是 利用串听来获取组网信息从而减少了额外的开销。p e a c h 协议可用于 位置可知的网络，也可用于位置不可知的网络。 2 4 本章小结 这章介绍了无线传感网中网络层的各成簇协议，着重介绍了l e a c h 和h e e d 两个协议。其余还有很多成簇协议【2 8 】【3 5 1 不一一介绍，各成簇协 议都有其优点和基于其他协议的改善，但是也有其不足之处最后图表 2 4 对本章介绍的各协议的特点进行了一个大致的比较 簇头的选取 成员节点的加入 协议是否考簇头开是否考延是否考是否考与簇开 虑簇头分布销虑能量时虑与簇虑簇的头的销 与基站是否头的距大小珧数 的距离 均匀 离 l e a c h否 否小否低是否 l 小 h e e d否 是大 日 高 否 是 1小 疋 e e c s 是是小是低是是 1 小 e e h c否否小否低是否 多 大 n 依m ，c是 是 小 是低是否 l 小 p e a c h否 否小否 士 是否 多 小 e e u c 是是 小 是低是是多 小 图表2 - 4 各成簇协议比较 一1 5 浙江大学硕士学位论文m a c 层协议综述 m a c 层协议综述 3 1 s m a c 协议 s m a c 协议【4 】【5 】首先研究了造成能量浪费的4 个原因：空闲侦听， 碰撞，串听和控制开销。其中空闲侦听是最主要的原因。s m a c 协议针 对以上四个原因采取相应机制分别实现了能量的节约并在前面提到的 c r o s s b o w 平台上进行了实际性能的测量。 空闲侦听：无线传感网络中节点能量的浪费很大程度上是由于节点 在空闲时也对媒体进行侦听造成的。为此s m a c 引入了周期性睡眠机制， 让节点在每一帧的固定时间内进行侦