（通信与信息系统专业论文）无线传感器网络分族算法及其在tinyos下的实现研究.pdf

南京航空航大人学硕士学位论文 摘要 无线传感器网络是由人量廉价、低功耗且具有传感、数据处理和短距离无线通信功能 的微型传感器节点组成，：符点之间以无线白组织方式协同工作，其目的是协作地感知、采 集和处理网络覆盖区域中感知对象的信息，并发布给观察者。无线传感器网络在目标跟踪、 战场监测、生物医疗、环境监测等领域有广阔的应用前景。分簇算法和节点软硬件平台设 计都是无线传感器网络的关键技术，对无线传感器网络的性能有很大的影响。 本文首先对无线传感器网络进行概述，阐述了传感器网络的体系结构、特点以及关键 技术，接着综述了几种典型的无线传感器网络分簇算法，并对现有分簇算法存在的不足进 行了深入研究。 然后，针对现有分簇算法存在的能量不均匀消耗问题，提出了一种基于负载均衡的无 线传感器网络分簇算法l b e e d ，该算法通过建立能量模型，从整体上优化了能量消耗，此 外，还通过功率控制机制使得网络内成簇人小均匀，从而均衡了网络内节点的负载。 m a t l a b 仿真实验表明，该算法在负载均匀方面的性能要优于典型分簇算法h e e d 和 l e a c h 。 此外，节点软硬件平台设计也是无线传感器网络研究的一个重要方面，介绍了基于芯 片c c 2 4 3 0 的硬件平台设计以及t i n y o s 操作系统后，在该平台下实现了h e e d 以及l b e e d 算法，并实现了能量高效的x m a c 协议，引入了超低功耗的j 【：作模式。在完成上述所有 ：f 作后，通过搭建一个小型的网络测试分簇算法以及x m a c 协议的性能。实验表明， l b e e d 算法能形成大小均匀的簇，x m a c 协议能使节点具有较低的能量占空比，从而延 长了整个网络的生存周期。 关键词：无线传感器网络，分簇算法，负载均衡，t i n y o s ，能量高效 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 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 s n ) c o n s i s t so fa l a r g en u m b e ro fl o w - c o s t ，l o w - p o w e r , m u l t i f u n c t i o n a ls e n s o rn o d e st h a ta r es i n a i li ns i z ea n dc o m m u n i c a t eu n t e t h e r e di ns h o r td i s t a n c e t h e s et i n ys e n s o rn o d e s ，w h i c ha r e a l w a y se q u i p p e d 谢ms e n s i n g ，d a t ap r o c e s s i n ga n d c o m m u n i c a t i n gc a p a b i l i t i e s o p e r a t ec o o p e r a t i v e l yi na dh o cm a n n e rt os e n s et h ei n f o r m a t i o ni n c o v e r a g e da r e a ，p r o c e s st h es e n s e dd a t aa n dt h e nt r a n s m i tt h er e s u l tt ot h ev i e w e r w i r e l e s s s e n s o rn e t w o r ki sw i d e l yu s e di na p p l i c a t i o n ss u c h 勰t a r g e tt r a c k i n g ，b a t t l e f i e l ds u r v e i l l a n c e 。 h e a l t ha n de n v i r o n m e n tm o n i t o r i n g c l u s t e r i n ga l g o r i t h ma n dn o d ea r c h i t e c t u r ed e s i g nw h i c h a r et w oo ft h ek e yt e c h n i q u e si nw i r e l e s ss e n s o rn e t w o r k sh a v eg r e a ti m p a c to nt h ep e r f o r m a n c e o fw i r e l e s ss e n s o rn e t w o r k s f i r s t ，w es u m m a r i z ew i r e l e s ss e n s o rn e t w o r k s ，i n c l u d i n gt h ea r c h i t e c t u r e ，f e a t u r e sa n dt h e k e yt e c h n i q u e s w ea l s og i v ea l lo v e r v i e wo fs e v e r a lr e p r e s e n t a t i v ec l u s t e r i n ga l g o r i t h m sr e c e n t l y p r o p o s e da n dt h e i rw e a k n e s s t h e n ，t oa d d r e s st h eu n b a l a n c e de n e r g yc o n s u m p t i o np r o b l e mo fe x i s t i n g c l u s t e r i n g a l g o r i t h m s ，w ep r o p o s eac l u s t e r i n ga l g o r i t h mc a l l e dl b e e d ( l o a d b a l a n c e de n e r g ye f f i c i e n t d i s t r i b u t e dc l u s t e r i n g ) w em a k et h en e t w o r kh a v em i n i m u me n e r g yc o n s u m p t i o nt h r o u g h m o d e l i n gt h ee n e r g yc o n s u m p t i o na n do p t i m i z i n gt h ep a r a m e t e r s f u r t h e r m o r e ，p o w e rc o n t r o li s u s e dt om a k et h en e t w o r kf o r ma l m o s te q u a ls i z ec l u s t e r sw h i c hc o n s e q u e n t l yb a l a n c e st h el o a d o fe v e r yn o d e m a t l a bs i m u l a t i o nr e v e a l st h a tt h ep r o p o s e da l g o r i t h mp e r f o r m sb e t t e rt h a n h e e da n dl e a c hi nl o a db a l a n c ea s p e c t s o r w a r ea n dh a r d w a r ep l a t f o r md e s i g nf o rs e n s o rn o d e si sa l s oa ni m p o r t a n ta s p e c to f w i r e l e s ss e n s o rn e t w o r k s a f t e rad e t a i l e dd e s c r i p t i o no ft h eh a r d w a r ep l a t f o r mw h i c hi sb a s e d c c 2 4 3 0c h i pa n dt h et i n y o so p e r a t i n gs y s t e m ，h e e da n dl b e e da r ei m p l e m e n t e do nt h e p l a t f o r m w ei m p l e m e n tx m a ca n di n t r o d u c ea l lu l t r a - l o wp o w e ro p e r a t i n gm o d e 觞w e l l b a s e do na b o v ed e s i g n ，as m a l l s c a l en e t w o r ki ss e tu pt ot e s tt h ep e r f o r m a n c eo ft h ec l u s t e r i n g a l g o r i t h m sa n dx m a c ，t h er e s u l t sp r o v et h a tl b e e dm a k e st h en e t w o r kf o r me q u a l s i z e c l u s t e r s ；b e s i d e sx m a cm a k e sn o d e sh a v el o wd u t yc y c l ea n dc o n s e q u e n t l yp r o l o n g st h e n e t w o r kl i f e t i m e k e y w o r d s ：w i r e l e s s s e n s o rn e t w o r k ，c l u s t e r i n g a l g o r i t h m ，l o a db a l a n c e ，t i n y o s ， e n e r g y - e f f i c i e n t i i 南京航空航大人学硕十学位论文 图1 1 图1 2 图1 3 图1 4 图2 1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图5 1 图5 2 图5 3 图5 4 图、表清单 无线传感器网络体系结构2 传感器节点结构2 无线传感器网络的协议栈体系3 m e d u s ai i 节点各部分能量消耗对比图5 传感器网络分簇后的拓扑结构8 l e a c h 的执行过程1 0 e e u c 算法预期形成的分簇结构1 3 l e a c h 算法产生的网络拓扑结构1 5 h e e d 算法产生的拓扑结构。1 6 分簇结构1 9 l b e e d 算法在各种网络拓扑下网络生存周期随a 的变化曲线2 5 节点均匀分布时网络生存周期比较2 5 节点均匀分布的情况下生存1 y 点数随时间变化的曲线一2 6 节点非均匀分布时网络生存周期比较2 7 节点非均匀分布的情况下生存1 y 点数随时间变化的曲线2 8 网络中簇人小的方差2 9 基于c c 2 4 3 0 的节点原理图3 1 ：宵点硬件实物图3 2 c c 2 4 3 0 芯片的结构框图3 3 c c 2 4 3 0 物理层调制和扩频功能图3 4 i e e e 8 0 2 1 5 4 数据帧格式3 4 数据传输过程中s f d 状态的变化3 5 数据接收过程中各状态的变化3 5 t i n y o s 的层次结构3 6 t i n y o s 的调度过程j 3 7 n e s c 的组件模型3 8 n e s c 的编译过程4 l 算法的t i n y o s 软件结构图4 4 n e i g h b o r t a b l e c 的组件结构4 5 p o w e r e s t i m a t o r c 的组件结构4 5 c l u s t e r o g a n i z e c 的组件结构4 6 v 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 图5 5 分簇算法流程图一4 6 图5 6 无线传感器网络中数据传输方向4 8 图5 7 路由协议的组件结构4 9 图5 8 带休眠的t d m a 时隙图4 9 图5 9x m a c 的机制图5 0 图5 1 0x m a c 的t i n y o s 组件结构51 图5 1 1系统流程图5 1 图5 1 2 节点在各种状态下的一】：作电流5 3 图5 1 3 数据传输过程5 4 图5 1 4 超低功耗测试5 8 表3 1l b e e d 算法中符号的含义2 2 表3 2 仿真参数2 4 表5 1 输山功率设置4 7 表5 2 算法的性能5 2 表5 3 节点的能量r 叶空比和数据成功到达率5 2 南京航空航天人学硕十学位论文 a d c a m r p c s m a c a e e u c f c s h e e d w s n l e a c h m a c s f d w c a 注释表 d i g i t a l a n a l o gc o n v e r s i o n a v e r a g em i n i m u mr e a c h a b i l i t yp o w e r c a r r i e rs e n s em u l t i p l ea c c e s s w i mc o l l i s i o na v o i d a n c e e n e r g y e f f i c i e n tu n e q u a lc l u s t e r i n g f r a m ec h e c ks e q u e n c e h y b r i de n e r g y e f f i c i e n td i s t r i b u t e dc l u s t e r i n g 、i r e l e s ss e n s o rn e t w o r k l o w e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y m e d i u ma c c e s sc o n t r o l s t a r to fd e l i m i t e r w e i g h t e dc l u s t e r i n ga l g o r i t h m 数模转换 最小平均可达能量 载波侦听多点接入冲突 避免 能量高效非均匀成簇协议 帧校验序列 混合能量高效分布式分簇协议 无线传感器网络 低能量自适应集簇分层型协议 介质访问控制 帧起始定界符 基于权重的分簇算法 v i i 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导 下，独立进行研究工作所取得的成果。尽我所知，除文中已 经注明引用的内容外，本学位论文的研究成果不包含任何他 人享有著作权的内容。对本论文所涉及的研究工作做出贡献 的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复 印件，允许论文被查阅和借阅，可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或其 他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：j 耻 e l期：塑! ：兰：! 篁 南京航空航天人学硕十学位论文 第一章绪论 本章首先概述无线传感器网络的概念、网络体系结构、特点，随后综述了无线传感器 网络的关键技术及研究现状。最后是本文的主要j 二作和内容安排。 1 1 无线传感器网络概述 无线传感器网络是当前备受关注的、涉及多学科高度交叉、知识高度集成的前沿研究 领域。它综合了传感器技术、嵌入式技术、a dh o e 网络及无线通信技术、分布式信息处理 技术等，具有十分广阔的应用前景，被认为是对2 1 世纪产生巨大影响力的技术之一【l 】。 无线传感器网络是由大量廉价、低功耗且具有传感、数据处理和短距离无线通信功能 的传感器节点组成，传感器：肖点之间以白组织方式协同工作，其目的是协作地感知、采集 和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者1 1 2 3 1 。 无线传感器网络是因特网从虚拟世界到物理世界的延伸，它将逻辑上的信息世界与真 实物理融合在一起，改变了人与自然交互的方式。人们可以通过传感器网络直接感知客观 世界，从而极大扩展现有网络的功能和人类认知世界的能力。无线传感器网络可广泛应用 于抢险救灾、战场监测、精细农业、智能家居、生物医疗和环境等领域【2 】。由丁无线传感 器网络有巨大的应用前景，1 9 9 9 年、2 0 0 3 年美国商业周刊和m i t 技术评论在预 测未来技术发展报告中，分别将w s n 列为2 l 世纪最有影响力的2 1 项技术和改变世界的 1 0 大新技术之一。一些有实力的人公司i n t e l 、i b m 、c r o s s b o w 等公司均投入了大量的人力、 物力用于研发传感器网络相关技术、标准与产品，预计在不久的将来就会有大量成熟的无 线传感器网络面世。 1 1 1 无线传感器网络的体系结构 无线传感器网络体系结构包括网络结构、传感器节点结构以及网络协议栈体系结构。 图1 1 所示为典型的无线传感器网络结构。传感器网络系统通常包括传感器节点、汇 聚节点( 或基站节点) 和管理节点( 用户) 。大量的传感器网络节点部署在被感知区域的内 部或附近，通过自组织方式构成无线网络，以协作的方式实时感知、采集和处理网络覆盖 区域内的信息，并通过多跳将整个区域内的信息传送给基站，基站通过i n t e m e t 网或者卫 星通信发送给远程用户。用户可以通过i n t e m e t 网或卫星对传感器网络进行配置和管理， 发布监测任务以及收集监测数据。 传感器节点是一个微型的嵌入式系统，它的处理能力、存储能力有限，通信距离短， 由电池供电，能量有限。由于节点之间通过a dh o e 形式组网，因而，每个传感器网络：市 点兼顾通信终端和路由器双重功能。传感器节点一般由传感器模块、处理器模块、无线通 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 信模块和能量供应模块四部分组成，如图1 2 所示。其中，传感器模块由传感器、a d 转 换器组成，负责感知监测对象的信息：处理器模块包括处理器和存储器，负责控制整个传 图1 1 无线传感器网络体系结构 感器节点的操作，存储和处理自身采集的数据以及其他节点发来的数据；无线通信模块包 括了射频收发器以及协议栈，用于控制射频收发、无线信道接入等功能；能量供应模块给 节点：【作供应能量，一般为体积较小的电池。 图1 2 传感器节点结构 随着无线传感器网络研究的深入，研究人员提出了传感器节点上的协议栈。传感器网 络的协议栈一般包括物理层、数据链路层、网络层、传输层和应用层，与传统t c p i p 的五 层协议结构相对应，另外，协议栈中还包括能量管理平台、移动管理平台和任务管理平台， 如图1 3 所示。这些平台让节点能够能鼍高效地工作，在节点移动的传感器网络中转发任 务，并支持多任务和资源共享。各层的功能如。f t i 】： 物理层：提供健壮的信号调制和无线收发技术： 数据链路层：负责数据成帧、信道监测、媒介访问等； 网络层：负责路由生成与路由选择； 传输层：负责数据流的传输控制，保证通信的服务质量： 应用层：包括一系列基于监测任务的应用层软件； 2 南京航空航天人学硕十学位论文 能量管理平台： 移动管理平台： 任务管理平台： 管理传感器节点的能量使用，在各个协议层都需要考虑：肖省能量； 监测并注册传感器肖点的移动，维护到汇聚节点的路由； 在一个给定的i 又：域内平衡和调度监测任务。 应用层 传输层能移任 蹙动 务 管管管 网络层 理理理 亚 平 平 数据链路层 厶厶厶 口口 口 物理层 图1 3 无线传感器网络的协议栈体系 1 1 2 无线传感器网络的特点 和无线自组网( m o b i l ea d h o en e t w o r k ) 一样，无线传感器网络是一种无中心、自组织、 不需要i 司定网络基础设施的网络，但同时它与无线自组网也存在很大的差异。传感器网络 是集成了监测、控制以及无线通信的网络系统，：1 了点数目更为庞大，节点分布更为密集； 由于环境影响，节点更容易出现故障：在人多数应刚中，传感器网络节点是固定不动的。 另外，传感器二1 了点的能鼍、处理能力、存储能力和通信能力都十分有限。这些筹异使得无 线传感器网络有许多自身的特点。 1 节点能量有限 无线传感器网络中的节点大部分采州干电池供电，且网络大多j r = 作在无人区或者对人 体有害的恶劣环境中，网络节点成千上万，更换电池困难。因此，如何高效使用能量是在 设计传感器网络硬件节点以及网络协议的时候首要考虑的因素。 2 高密度网络 为了获取精确信息，在监测区域通常部署大量传感器节点，传感器节点数量可能达到 成千上万，甚至更多。节点的大规模部署有如下优点：通过分布式处理大量的采集信息能 够提高检测的精确度，降低对单个节点传感器的精度要求：大量冗余节点的存在，使得系 统有很强的容错性能。高密度的网络就要求设计的网络协议及算法具有很强的可扩展性。 3 应用相关的网络 传感器网络用来感知客观物理世界，获取监测区域的信息。不同的传感器网络应用关 心的物理量不同，其硬件平台、软件结构和网络协议必然有很大差别。如环境监测的传感 器网络应用中，网络的生存周期是网络协议设计考虑的首要因素，允许有定的时延；而 在目标追踪、火灾监测的应用中，要求网络有较好的实盱陛。 4 以数据为中心的网络 3 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 目前的互联网是先有计算机终端系统，然后再互联为网络，终端系统可以脱离网络而 独立存在。互联网中，网络设备用网络中唯一的i p 地址标识，如果要访问互联网中的资源， 首先要知道存放资源服务器的i p 地址。可以说，目前的互联网是一个以地址为中心的网络。 传感器网络是任务型的网络，脱离网络的节点没有任何意义。用户使用无线传感器网 络杏询事件时，直接将所关心的事件通告给网络。用户只关心监测区域内的信息，并不关 心信息由哪个节点提供。这种以数据本身作为查询或传输线索的思想更接近于自然语言交 流的习惯。所以通常说传感器网络是以数据为中心的网络。 1 2 无线传感器网络的关键技术及研究现状 无线传感器网络涉及多学科交叉的研究领域，有非常多的关键技术有待发现和研究。 主要包括以下几个方面：网络拓扑控制、网络协议、能耗、数据融合等。 1 2 1 网络拓扑控制 拓扑控制对于无线传感器网络具有特别重要的意义。通过拓扑控制能生成良好的网络 拓扑结构，提高路由协议和m a c 协议的效率，可以为数据融合、时间同步等奠定基础， 有利于网络节点的休眠，从而延长网络的生存周期。传感器网络拓扑控制目前主要的研究 问题是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，生成一个 高效的数据转发的网络拓扑结构 4 1 。拓扑控制由此可以分为节点功率控制和层次拓扑结构 形成两个方面。节点功率控制调：1 了网络中每个：肖点的发射功率，使得节点有一定数量的邻 居二肖点，从而保持网络的连通性【5 】【6 1 。层次拓扑控制利刚分簇机制，通过一定的准则在网 络中选取一些：肖点担任簇头，用于管理簇内的其他节点，并且转发簇内节点的信息。簇内 节点在自己不需要通信的时候可以关闭无线通信模块，进入休眠状态以节省能量【7 1 。 1 2 2 网络协议 无线传感器网络节点的处理能力、存储能力、无线通信能力和供电能力都十分有限， 因此在传感器网络的协议设计时，既要考虑协议的简单性，又要考虑能量因素。目前无线 传感器网络研究的重点是网络层协议和数据链路层协议。网络层的路由协议给出了监测信 息传输的路径；数据链路层的m a c 层主要用来控制节点接入无线信道的方式。 无线传感器网络中有：1 了点死亡后，网络某些链路就有可能中断，网络性能将变得不稳 定，监测区域中可能会出现覆盖不到的地方，因此，在网络路由协议设计的过程中，既要 考虑路由的优越性，同时还要考虑到网络中节点负载的均衡。无线传感器网络是以数据位 中心的网络，一般采用的是分簇结构的路由协议，如l e a c h 、h e e d 等。 传感器网络的m a c 协议首先考虑节省能量和可扩展性，其次考虑的才是时延、公平 性等因素。m a c 层的能量浪费主要表现在以下四个方面：( 1 ) 空闲侦听( i d l el i s t e n i n g ) ( 2 ) 数据碰撞引起的重传( c o l l i s i o n ) ( 3 ) 串音( o v e r h e a r i n g ) ，即节点接收到发送给其他节点 4 南京航空航天人学硕+ 学位论文 的信息( 4 ) 控制信息。为了减小能量的消耗，无线传感器网络m a c 协议避免了传统的 8 0 2 1 1 d c f 中的r t s c t s 机制，从而减少了控制信息：其次，还引入了休眠机制，节点在 需要收发数据的时候才启动无线通信模块，监听信道，在空闲时刻尽量进入休眠状态，减 少空闲侦听。此外，m a c 层协议也采川了有效的方法避免数据发生碰撞。近期提出的包 括s - m a c t 8 1 、t - m a c t 9 1 、b m a c t l 们、x m a c l l u 等基丁竞争的m a c 协议和c s m a c a 和 t d m a 相结合的z m a c l l 2 1 协议中都引入了休眠机制。 由于传感器网络是应用相关的网络，不同的虑用对网络的实时性、低功耗等参数的要 求不同，相应地，使用的网络协议也差异很大。网络协议往往需要根据应用类型或应用目 的来制定，没有任何一个协议能够高效适用于所有不同的应用。 1 2 3 能量问题 在大多数情况下，传感器网络中的节点采川电池供电，电池容量非常有限，更换电池 非常困难，因此尽可能地节约传感器网络节点的电池能量成为传感器网络设计的核心问题。 传感器网络：肯点的节能通过两方面来实现，一是通过设计低功耗的硬件米实现：二是通过 设计合理的网络协议来实现。 现有的无线传感器网络节点主要由微处理器、存储器、传感器、射频模块等构成。在 网络实际运行过程中，能耗主要来源于处( p r o c e s s i n g ) 、传感( s e n s i n g ) 和无线传输( r a d i o ) 三个操作。各部分的能餐消耗冈硬件。1 了点而异，如文献【1 3 】给出了m e d u s ai i ：缸点各部分能 量的消耗状况，如图1 4 所示。由幽可以看出，。1 了点射频模块处1 ：空闲状态时的能量消耗 2 5 2 0 薄 粼1 5 暑 耋1 0 5 通信模块 厂 传感处理发送接收宅闲 休眠 图1 4m e d u s ai i 节点各部分能量消耗对比图 非常可观，相当于：符点接收时的z 日匕l - , 量，因此，在设计路由协议和m a c 协议时，应当使得 节点的射频尽量地处于休眠状态。传感器的某些节点芯片如c r o s s b o w 公司生产的c c 2 4 2 0 和c c 2 4 3 0 都支持处理器休眠的超低功耗工作方式，在节点不需要工作的时候，应使节点 进入超低功耗状态以：符省能耗。 5 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 1 2 4 数据融合 数据融合是无线传感器网络中重要的研究领域之一。使用数据融合技术能够有效地克 服无线传感器网络中能量的限制。网络中的相邻节点采集到的数据一般具有很大的相似性， 通过合并多个数据源产生的数据，去除冗余信息，数据融合能够有效地减少网络中的数据 传输量，从而节省传感器节点的能量，延长无线传感器网络的生存周期1 4 】 1 5 】。数据融合的 作心还体现在：通过减少网络中的数据传输量，数据融合能够降低无线信道中发生数据冲 突的概率，提高m a c 协议的效率；通过比较相邻传感器节点采集的数据，数据融合能够 检n - n 异常数据，从而提高数据的准确性。 数据融合技术可以与传感器网络的多个协议层次进行结合。在应用层设计中，可以利 川分布式数据库技术，对采集到的数据进行逐步筛选，达到融合的效果：在网络层，各种 分簇路由协议均结合了数据融合机制，以减少数据传输量。在传感器网络的设计中，要面 向应用需求设计针对性强的数据融合方法。 1 3 课题背景与本文的主要内容 当前，国内外的研究人员在无线传感器网络方面已经取得了初步的研究成果，在网络 拓扑控制、网络协议、：1 m 4 - z , 匕p _ , 、无线传感器节点设计等方面都有较为广泛的研究。其中，传 感器网络分簇算法的研究有着非常重要的意义，通过分簇使得网络形成良好的拓扑结构， 为设计能量高效、简单的网络协议以及数据融合奠定了基础。本文结合国内外已有的研究 成果，重点研究了网络拓扑控制方法中的分簇组网算法。在对现有分簇算法深入研究的基 础上，指出算法存在的不足，并做了合理的改进，提出一种基于负载均衡的无线传感器网 络分簇算法。 无线传感器网络一般布置在恶劣的环境中，受高山、建筑物、障碍物等地势地貌以及 风雨雷电等自然环境的影响，无线通信的信道状况1 f 常复杂。现阶段对无线传感器网络的 大多数研究用o m n e t + + 、n s 2 等仿真软件，这些软件对无线信道的建模都比较简单，一 般采用自由空间( f r e e s p a c e ) 模型或双地线地面( t w o r a y ) 模型，这些模型不能准确反映 信道的真实状况。本文对分簇算法的研究首先采用m a t l a b 仿真，比较算法的性能，然 后在硬件平台上实现。 硬件平台使用本实验室开发的a n t c 3 节点，采h jc c 2 4 3 0 芯片，该芯片集成了8 0 5 1 单 片机和射频收发模块，只需要很少的外嗣电路。该硬件平台使用t i n y o s 操作系统。t i n y o s 是n 3 h 大学伯克利分校的研究人员针对传感器网络开发的一个开源的嵌入式操作系统。该 操作系统是由n e s c 语言编写和实现的，采用了组件结构，这种组件化的编程方式有很强的 可扩展性，代码小，适合于存储器有限的传感器网络节点。 本文的主要研究内容包括： 1 ) 对无线传感器网络网络拓扑控制中的分簇算法进行深入的研究，通过仿真及理论分 6 南京航空航天人学硕+ 学位论文 析，指出现有算法如h e e d 、l e a c h 的不足，提山了一种基丁负载均衡的无线传感器网络 分簇算法，通过m a t l a b 仿真分析了该算法的性能。 2 ) 学习掌握了基于c c 2 4 3 0 芯片的硬件平台的功能、特点。熟练掌握了t i n y o s 系统 网络协议的开发，在硬件平台上实现了h e e d 算法及本文提出的分簇算法。 3 ) 在分簇算法的基础上，针对网络拓扑结构提出并实现了相应的路由、m a c 协议， 引入了射频休眠机制，由于c c 2 4 3 0 芯片支持c p u 休眠，同时，我们也引入了节点的超低 功耗工作模式，在该工作模式下，c p u 和射频均处于休眠状态，! t ：作电流只有o 0 8 微安。 1 4 论文结构 本文的主要结构如下： 第一章为绪论，介绍了无线传感器网络的概念、体系结构、特点和关键技术以及研究 现状。最后阐述了本文的主要丁作和结构。 第二章首先介绍了无线传感器网络分簇算法的概念、特点、设计要求和性能指标，然 后选取了几种典型的算法进行了深入研究，对各种算法的性能进行了比较分析。 第三章提出了一种基于负载均衡的无线传感器网络分簇算法l b e e d ，通过m a t l a b 仿真分析了l b e e d 的性能。 第四章详细介绍了基于c c 2 4 3 0 芯片的无线传感器网络硬件平台以及t i n y o s 操作系 统，在t i n y o s 操作系统下实现了基t - c c 2 4 3 0 的软什平台。 第无章描述了分簇算法在基y - c c 2 4 3 0 的t i n y o s 软件平台上的实现，并针对分簇后的 网络拓扑结构提出了相应的路由和m a c 协议，引入了c p u 休眠的超低功耗工作模式。最 后通过搭建实验测试了l b e e d 、h e e d 算法以及x m a c 等的性能。 第六章总结了本文工作并对未来的研究方向进行了展望。 7 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 第二章无线传感器网络分簇算法 本章简要介绍无线传感器网络分簇算法的概念、优点、评价指标等，对现有几种典型 的无线传感器网络分簇算法进行综述，并分析算法的性能。 2 1 无线传感器网络分簇的概念 拓扑控制中的分簇在传感器网络设计中起着非常重要的作用，良好的拓扑结构能够提 高路由协议和m a c 协议的效率，为数据融合、时间同步和目标定位等很多方面提供基础， 有利丁延长网络的生存时间。 分簇就是按照一定的准则在网络中选择一组节点充当簇头，用于协调和管理网络内属 于臼已簇内的其它节点的通信，并对该簇内节点感知的数据进行数据融合等处理后，直接 或者通过多跳方式发送给基站。由于传感器网络是应用相关的网络，选取簇头的准则一般 根据节点布置方式、网络结构、网络中节点情况以及网络模型确刮7 】。 图2 1 给出了无线传感器网络分簇后的网络拓扑图，图中实心点表示簇内节点，圆圈 表示分簇产生的簇头节点，虚线形成的区域表示该簇头管理的区域。图( a ) 为簇头到基站 、 c o 、i 一。： 、! ? ： 八， 三。甏笺j 装 j i 一 ( j ：! 二! f ! ! 一7 7 2 7 ：，e j 二_ ! - ， 1气： ( ( a ) 簇头到基站是单跳的情况( b ) 簇头剑基站是多跳的情况 图2 1 传感器网络分簇后的拓扑结构 的通信是单跳的情况，簇内节点监测到数据后，传输给簇头节点，簇头节点对数据进行处 理后，直接传输到基站。无线传感器网络：俗点通信距离有限，所以一般在小规模的网络中 使刚这种模型。图( b ) 为簇头到基站的通信是多跳的情况，簇头节点收到簇内节点传来的 数据后，通过一定的路由选择算法，经过多跳传输给基站。网络中簇头节点的通信距离大 于簇内节点的通信距离，簇内通信和簇间通信应使用不同的扩频码或者其他技术避免簇间 通信对簇内通信的干扰。 8 南京航空航天人学硕十学位论文 2 2 无线传感器网络分簇的优势 与平面型的网络拓扑结构相比，层次型( 分簇) 的网络拓扑结构有着非常明显的优势。 1 ) 传感器网络中节点的密度1 仁常高，节点数目多，网络协议设计需要有很好的可扩展 性，而分簇后网络的分层拓扑结构可以满足这种需求。 2 ) 分簇后的拓扑结构能给节点提供足够多的路由信息，从而简化了无线传感器网络的 路由选择算法，减小了路由表，使得网络协议能够很好地适应这种处理能力、存储能力等 资源受限的传感器网络节点。 3 ) 分簇使得簇内的普通：肖点在节点不需要发送数据的时候进入休眠模式，减少了冈空 闲侦听浪费的能量，能延长网络的生存周期。 4 ) 簇内节点只需要很小的发射功率，相应的竞争信道的。仃点数目减少，提高了m a c 协议的效率。 此外，分簇结构还为数据融合提供了基础，能有效减少网络中的数据传输量，提高数 据采集的准确性，且通过簇头节点便于管理网络中的节点。总之，针对传感器网络的应用、 网络特点等设计一种合理高效的传感器网络分簇算法能够提高整个网络的性能，有效延长 网络的生存周期。 2 3 无线传感器网络分簇算法的评价指标 分簇算法的性能一股从算法本身和对网络的影响两个方面米评价。其基本的评价指标 如。f ： 1 ) 算法应该是完全分布式的。由于无线传感器网络是白组织的，二肖点数目多，分簇算 法应当使得每个节点只依赖丁本地信息独立地做出决定。 2 ) 算法应该具有较低的时间复杂度和控制消息复杂度。 3 ) 算法应该有较好的稳定性。在传感器网络中，受自然环境的影响，某些链路经常会 中断，某些节点冈为电池能量耗尽也会导致网络拓扑结构发生变化，从而影响系统的稳定 性。分簇算法应该有一定的容错性。 4 ) 算法结束后，网络中的节点应该被唯一地确定，或者是簇头节点，或者是普通节点。 5 ) 分簇算法应该简单高效。分簇算法的目标是构造一个能够覆盖整个网络节点的、可 以较好支持资源管理和路由协议相互连接的簇的集合。为了减少网络分簇带来的通信和计 算开销，在拓扑变化较慢、保证能量均衡的前提下，分簇机制应该尽量保持原有结构。 在满足其他性能指标的前提下，能量是传感器网络设计中首要考虑的问题，在网络协 议中引入休眠机制、降低节点能量消耗的同时，还要尽可能地均衡网络中节点的能量负载， 使得网络中所有节点的能量几乎同时用完。定义网络的生存周期为从组网到网络中第一个 节点能量耗尽所用的时间，从而网络的生存周期也是评价无线传感器网络分簇算法性能的 一个量化指标。 9 无线传感器网络分簇算法及其在t i n y o s 下的实现研究 2 4 几种典型的无线传感器网络分簇算法 近年米，研究人员提出了多种无线传感器网络分簇算法。根据对网络中节点的要求， 传感器网络分簇算法可以分为基于地理位置信息的分簇算法和不需要地理位置信息的分簇 算法；根据选举簇头的准则，传感器网络分簇算法义可以分为基于节点号、基于节点度数 以及基于节点能量的分簇算法。下面我们简单介绍现有的几种典型的无线传感器网络分簇 算法。 2 4 1 低能量自适应分簇( l e a c h ) 协议 l e a c h ( 1 0 w - e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 6 】是无线传感器网络中最早提出的 且具有代表性的分簇算法。l e a c h 算法假设：网络中：宵点的发射功率足够大，任何节点 都可以一跳到达基站；网络中的：锚点可以根据到达目的：宵点的距离调整自己的发射功率； 相邻节点的数据具有很强的相关性。算法的基本思想是：通过等概率地随机循环选择簇头， 将整个网络的能量负载平均分配到每个传感器节点，从而达到降低网络能量消耗、延长网 络生存周期的目的。l e a c h 的执行时周期性的，每个周期为一“轮( r o u n d s ) ”，一轮由簇 头选举和数据传输两个阶段组成，如图2 2 所示。 簇头选举 数据传输 时同 图2 2l e a c h 的执行过程 1 ) 簇头选举过程 l e a c h 算法首先根据网络节点通信的能量模型计算出保证网络整体能量消耗最小所 需簇的个数k 。同时，为了平衡网络中的能量负载，网络中的：符点轮流充当簇头。设网络 中的节点数目为n ，则为了保证网络中所有节点担任簇头的次数相同，要求节点在n k 轮 中只能担任一次簇头。每个节点选举为簇头的概率为： 拍) = - 坝d 警) c i ( t ) = 1 ( 2 1 ) 【oc ，( t ) = 0 其中，r 表示轮数，c i ( t ) 为示意函数，值为l 表示节点i 在最近的n k 轮内没有担任过 簇头，值为0 表示节点i 在最近的n k 轮内已经担任过簇头，所以设置该节点担任簇头的 概率为0 由于每轮种选举的簇头数为k ，在第r 轮时，最近n k 轮内没有当选为簇头的节 点个数为n k 木( rm o d ( n l