（电工理论与新技术专业论文）无线传感器网络簇状网的研究.pdf

a b s t r a c t 1 1 1 ew i r e l e s ss e l f - o r g a n i z e ds e n s o rn e t w o r k w h i c hi si n t e g r a t i o no fs e n s o r t e c h n i q u e s ，m e m st e c h n i q u e s a n dn e t w o r kc o m m u n i c a t i o nt e c h n i q u e s ，i sa n i n n o v a t i v et e c h n i q u eo fi n f o r m a t i o na c q u i s i t i o na n dp r o c e s s i n g i ti sa na d v a n c i n g r e s e a r c hf i e l do fm u l t i - s u b j e c ti n t e r s e c t i o n i tb r i n g sw i d ea p p l i c a t i o nf u t u r ei na g o o dm a n yf i e l d s ，s u c ha sm i l i t a r y , i n d u s t r y , m e d i c a lt r e a t m e n t ，t r a n s p o r t a t i o na n d c o m m e r c i a l af e wa c h i e v e m e n t sh a v eb e e na c q u i r e di nt h ew o r l do f r e c e n ty e a r s ， b u to ns o m ek e yt e c h n i q u e s ，t h e r ea r ea l s oal o to f p r o b l e m si nn e e do f r e s o l u t i o n t h i sp a p e rd i dad e e ps t u d yi nc l u s t e r e d n e t w o r kc r e a t e dt h r o u g hh i e r a r c h i c a l t o p l o g ym a n a g e m e n t ，i n c l u d i n go p t i m i z a t i o no fe n e r g yc o n s u m i n ga n d1 0 9 i c a l t o p l o g yi nc u l u s t e r e d n e t w o r k ，a n dc o n s t r u c t i o no f c l u s t e r - t r e eb a c k b o n en e t w o r k i nv i e wo ft h ee n e r g y - i r r e p r o d u c i b i l i t yo ft h es e n s o rn e t w o r k ，h o wt oi m p r o v e t h ee f f i c i e n c yo f e n e r g yc o n s u m i n gi ns e n s o rn e t w o r ka n dm a x i m i z e i t sl i f et i m ei s o n eo fk e yi s s u e si nw i r e l e s ss e n s o rn e t w o r kt e c h n o l o g y o nt h eb a s i so fa n a l y z i n g s i n g l e h o pc l u s t e r e d - n e t w o r ka n de s t a b l i s h i n g n e t w o r km o d e la n dm a t h e m a t i c s m o d e l ，t h i sp a p e rd i s c u s s e dt h er e l a t i o n s h i pb e t w e e ns e v e r a lk e yn e t w o r k p a r a m e t e r sa n de n e r g yc o n s u m i n g ，t h e nf o u n dt h eo p t i m i z e dp a r a m e t e r st h a tw o u l d a c h i e v em i n i m u me n e r g yc o n s u m p t i o n n l eo p t i m i z a t i o no fl o g i c a lt o p l o g yo fc l u s t e r e d n e t w o r ki san p - h a r dp r o b l e m b a s e do nt h ef u n d a m e n t a lf r a m e w o r ko fg e n e t i ca l g o r i t h m ( g a ) ，a l li m p r o v e d a l g o r i t h mi sp r o p o s e di nt h i sp a p e r , i nw h i c han e wc r o s s o v e r ，m u t a t i o na n d s e l e c t i o nm e t h o da r eu s e d t h ec o n v e r g e n c ep r o c e s so fg e n e t i ca l g o r i t h mi s a c c e l e r a t e db yu s i n gt h es t r a t a g eo fs e c o n ds e l e c t i o n s i m u l a t i o n ss h o wt h a tt h e g l o b a la p p r o x i m a t eo p t i m a ls o l u t i o no f t h ep r o b l e mc a nb er a p i d l yf o u n d i no r d e rt os o l v et h ep r o b l e mo fi n a p p r o p r i a t ec l u s t e rh e a de l e c t i o na n d e x c e s s i v el o n gt r a n s m i s s i o n d i s t a n c e e a c t ( e n e r g y a w a r ec l u s t e r - t r e e ) a l g o r i t h mi sp r o p o s e dt oo r g a n i z et h ec l u s t e rt r e eb a c k b o n en e t w o r k b a s e do nr o o t t r e ea n dm a x i m a lw 萌g h t e di n d e p e n d e n ts e t e a c tu t i l i z e sp e r i o d i c a lr o t a t i o no f c l u s t e rh e a d st ob a l a n c et h ee n e r g yc o n s u m e db yn o d e s s i m u l a t i o nr e s u l t s d e m o n s t r a t et h a te a c tw o u l ds i g n i f i c a n t l yi n c r e a s et h el i f e t i m eo ft h en e t w o r k a n do u r a p p r o a c h b e a r st h ec h a r a c t e r i s t i c so fe n e r g ye f f i c i e n c y , a n dl o w c o m p l e x i t y k e y w o r k ：w i r e l e s ss e n s o rn e t w o r k s ，t o p o l o g ym a n a g e m e n t ，c l u s t e r i n g c l u s t e r - t r e e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得 的研究成果，除了文中特别加以杯注和致谢之处外，论文中不包含其他入已经 发表或撰写过的研究成果，也不包含为获得鑫鲞盘堂或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 学位论文作者签名：冬翻习 签字日期：- 年，月z 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规 定。特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同 意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：杏韵1 签字r 期：】j 6 年f 月土同 新繇彩雨钥 签字只期：加年，月2r 第章绪论 1 1 无线传感器网络结构 第一章绪论 随着传感器技术、微机电系统技术，无线射频通信技术以及信号处理技术 的飞速发展，出现了一种由大量廉价、低功耗、仅具备有限计算和通信能力的 微小传感器节点组成的无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) ， 节点之间采用多跳、无线射频或光波等方式通信，相互协作共同完成诸如数据 采集、目标跟踪和指定区域监控等任务“儿2 ”“。自2 0 世纪9 0 年代初美国国 防高级研究计划局( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ，d a r p a ) 开 展军方研究项目w i n s 嘞以来，又相继开展了s m a r t d u s t 删，s e a w e b “1 等相关研 究计划。随着研究的不断深入，无线传感器网络所具有的随机部署、自组织、 自适应等特点使其在军事之外的其它领域也具有广泛的应用前景，如精细农 业、环境监测、医疗卫生、智能家居、交通及其它商用领域“”。无线传感 器网络已经迅速成为当前学术界和工业界的一个研究热点，一些有实力的大公 司如i n t e l 、i b m 已经投入大量人力和物力进行相关产品的研发工作，预计在 不久的将来就会有大量成熟的无线传感器网络实际应用面世。 图1 1 无线传感器网络体系结构 如图l l 所示典型的无线传感器网络结构，它由分却式传感器节点群组 成。传感器节点可以通过飞机白撒或人工布置等方式，大量部署在被感知对象 内部或者附近这些节点通过自组织方式构成无线网络，以协作的方式实时感 第一章绪论 知、采集和处理网络覆盖区域中的信息，并通过多跳方式将整个区域内的信息 传送给b s ( 基站) ，b s 再通过i n t e r n e t 网络发送给远处的用户。反之，用户 可以通过i n t e r n e t 网发送命令给b s ，而b s 再将命令转发给各个传感器节点。 图1 2 传感器节点硬件结构 传感器网络节点是一个微型化的嵌入式系统，它构成了无线传感器网络 的基础层支持平台目前国内外已经出现了许多种节点的设计，它们在实现原 理上是相似的，只是分别采用了不同的微处理器或者不同的通信及协议方式。 典型的传感器节点由数掘采集模块、数掘处理和控制模块、通信模块和供电模 块组成( 图l - - 2 ) 。其中，数据采集模块由传感器、a d 转换器组成，负责感 知监控对象的信息；供电模块负责供给节点工作所消耗的能量，一般为小体积 的电池；通信模块完成节点问的交互工作，一般为无线电收发装置；数据处理 和控制模块包括存储器和微处理器，负责控制整个传感器节点的操作，存储和 处理本身采集的数据以及其他节点发来的数据。同时，一些节点上还装配有能 源再生装置、运动或执行机构、定位系统等扩展设备以获得更完善的功能。 1 2 无线传感器网络的特征 1 节点数量众多 为了准确的获得监控对象的信息，通常要在监测区域内部署大量的传感器 节点，传感器节点数量可能达到成千上万，甚至更多。高密度的传感器节点能 够提高监测的精确度，增大覆盖区域，降低单个传感器节点的精度要求。 第一章绪论 2 节点能量有限 网络中每个节点的电源是有限的，网络大多工作在无人区或者对人体有伤 害的恶劣环境中，更换电源几乎是不可能的事，这势必要求网络功耗要小以延 长网络的寿命，而且要尽最大可能的节省电源消耗。 3 网络自动配置，自动识别节点 传感器网络通常被布置在没有基础结构的地方，抛撤的节点位置一般无法 事先获得，这就要求网络具有自组织、自动识别节点的功能，能够自动进行配 置和管理，通过拓扑控制、路由机制完成网络组织和数据采集功能。同时，无 线传感器网络具有自适应性，能够对由于环境、电能耗尽因素造成的传感器节 点出现故障或者失效、新节点加入等改变网络拓扑的情况做出相应的反应，以 保证网络的正常工作。 4 网络的自动管理和高度协作性 在无线传感器网络中，数据处理由节点自身完成，这样做的目的是减少无 线链路中传送的数据量，只有与其他节点相关的信息才在链路中传送。以数据 为中心的特性是无线传感器网络的又一个特点，由于节点不是预先计划的，而 且节点位置也不是预先确定的，这样就有一些节点由于发生较多错误或者不能 执行指定任务而被中止运行。为了在网络中监视目标对象，配置冗余节点是必 要的，节点之间可以通信和协作，共享数据，这样可以保证获得被监视对象比 较全面的数据。对用户来说，向所有位于观测区内的传感器发送一个数据请求， 然后将采集的数据送到指定节点处理，可以用一个多播路由协议把消息送到相 关节点，这需要一个唯一的地址表，对于用户而言，不需要知道每个传感器的 具体身份号，所以可以用以数据为中心的组网方式。 5 与现有无线网络模型的区别 当前的网络模型主要有：移动自组织网络m a n e t t g j ( am o b i l e a dh o c n e t w o r k ) 、蜂窝网络“”以及包括蓝牙1 在内的许多短距离的无线局域网等。 移动自组织网络是对等网络，它通常包含成千上万个通信节点，这些节点 能覆盖到几百米的范围，可以是完全移动的。m a n e t 的目的是形成并维持一个 有联系关系的多跳网络，并保证在节点高速移动情形下，网络仍能提供好的吞 吐时延特性。m a n e t 的能量消耗并不是设计主要考虑的因素，因为每个设备总 是隶属于人的，当电池的能量可能快耗尽时，就将它替换掉。 蜂窝网络是由静止节点和移动节点组成的很大网络。位于通信子网中的静 止节点( 基站) 和构成固定基础设施结构的有线中枢网络相连。每个基站都覆盖 一个很大的区域，有成百上千个移动节点。这种蜂窝网络的主要目标就是提供 高的服务质量和高的带宽效率，基站有无限的功率供给，而移动台山电池供电。 3 第一章绪论 蓝牙是短距离的无线网络系统，其目的是替换掉电器之间的电缆线，同时提 供电器问的射频连接。蓝牙的拓扑为星型网络结构，一个主节点最多可以有7 个附属节点与之相连，从而构成了微型网络。网络的信息速率大约为1 m b i t s ， 典型的传输功率是l m w ，可望覆盖1 0 m 的范围。 还有一种正在发展的短距离商用系统是家庭射频“”( h o m e r f ) 。此系统网络 模型基于i e e e 8 0 2 1 1 标准，是一种单跳自组织网络。信道接入基于时分多址 ( t d m a ) 和载波侦听多址接入( c s m a ) 模式。信息速率最高可达大约2 m b i t s ，传 输功率是1 0 0 m w 。 综上所述，这些传统的无线网络的主要目标都是在移动环境下能提供高的 服务质量( 即高吞吐量低时延) 和高的带宽效率，以传输数据为目的。网络的 设计遵循着“端到端”的思想，强调将一切与功能相关的处理都放在网络的端 系统上，中间节点仅仅负责数据分组的转发，而且能量消耗并不是设计主要考 虑的因素。 6 以数据为中心的网络 目前的互联网是先有计算机终端系统，然后再互联成为网络，终端系统可 以脱离网络独立存在。在互联网中，网络设备用网络中惟一的i p 地址标识， 资源定位和信息传输依赖于终端、路由器、服务器等网络设备的i p 地址。如 果想访问互联网中的资源，首先要知道存放资源的服务器i p 地址。可以说， 目前的互联网是一个以地址为中心的网络。 传感器网络是任务型的网络，脱离传感器网络谈论传感器节点没有任何意 义。传感器网络中的节点采用节点编号标识，是否需要节点编号惟一取决于网 络通信协议的设计。由于传感器节点随机部署，构成的传感器网络与节点编号 之间的关系是完全动态的，表现为节点编号与节点位置没有必然联系。用户使 用传感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给某 个确定编号的节点，网络在获得指定事件的信息后汇报给用户。这种以数据本 身作为查询或传输线索的思想更接近于自然语言交流的习惯。所以通常说传感 器网络是一个以数据为中心的网络。 1 3 无线传感器网络关键技术 对无线传感器网络的研究最先由d a r p a 发起，它连续资助了s m a r t d u s t 、 n e s t t ”1 等主要以军事应用为目的的项目。考虑到这些项目的军事目的， d a r p a 把无线传感器网络定义为：大规模( 成千上万的节点，覆盖广大地理 第一章绪论 区域) 、无线通信、多跳的、结构相同的、微型的( 甚至难以看到) 、放置后不 可移动的节点随机地放置在监控区域内。近些年，无线传感器网络开始应用在 环境和毒气监测、农业、医疗、工业生产线监控等民用领域。而无线传感器网 络结构也发生了变化，如允许网络中存在不同结构、可移动的传感器节点；传 感器节点可能是某种可视的设备等。 1 3 1 硬件平台 无线传感器网络是由大量传感器节点构成，因此，网络的硬件平台包括节 点放置、节点制作等方面。 1 节点的布置 可以通过随机抛撒和人为放置两种方式将传感器节点布置在物理区域内， 我们需要分别讨论两种方式下节点的通信半径、数量与区域面积之日j 的关系， 以保证网络的连通性与覆盖率。 2 节点的制作 根据实际应用目的的不同，传感器节点的体积、性能也不尽相同，传感器 节点体积有砖块、火柴盒、谷物和尘埃四个等级。例如气象监测网络允许节点 有砖块般大小，而军事用途的网络节点一般是不可见的。相应的，节点的造价 也由上千元至几元钱不等。不同的应用目的要求传感器节点具有一定的扩展功 能，如对移动军事目标的监控，可能需要节点具有自动跟踪目标、报告地理位 置等功能，这就需要挂载移动装置和全球定位系统。传感器节点是独立的装置， 其能量、计算能力、存储空间、通信范围等资源必然受到节点体积和造价的影 响，如何改进生产工艺以制作适应不同领域的传感器节点，是传感器网络设计 的一个技术难题。 3 节点的种类 人们最初设想传感器网络是由同一类型的节点组成的，这些节点不论在硬 件还是软件上都是相同的。而一些实际应用的无线传感器网络中的节点是不尽 相同的，如a m o r p h o u sc o m p u t i n g 1 要求节点有不同的i d 和物理地址：一些 数据统计网络中，需要对采集的数据进行大量计算，因此，可以考虑在网络中 布置一些计算功能强大的特殊节点，普通节点将采集的数据传递给附近的特殊 节点，并在进行计算后上传至观察者，这样就减少了网络中大部分节点的能耗， 延长了网络生存期；又如毒气泄漏监控网络，需要获得发生泄漏的准确位置， 而在每个节点上都挂载g p s ( 全球定位系统) 必然极大提高网络造价，因此，考 虑在网络中靠冒少量带有g p s 的节点，其他节点通过定位算法来获得自己的物 第一章绪论 理位置。在网络中布置不同种类的节点可以有效地提高网络效率，而对于允许 存在不同种类节点的网络，如何确定各种节点的合理比例及放置节点的方法是 需要解决的问题。 4 连通可靠性与覆盖率i 0 6 1 探测覆盖率问题是无线传感器网络的研究热点问题之一。它研究的主要问 题包括两大类，第一类为当节点不可移动时，且探测半径一定，在一定区域内 随机抛撒多少传感器节点，才能保证以一定的探测覆盖率监测这一区域：第二 类为当节点可移动时，在一定区域内如何部署、调整传感器节点分布，才能使 网络的覆盖范围最大( 最优) 化。对无线传感器网络探测覆盖率的研究可以使 观察者了解被监测区域的覆盖情况，是否存在监测盲区，从而指导将来如何添 加传感器节点或者如何重新调整传感器节点的分布。还可以通过调整节点分布 对重要监测区域进行多重覆盖，从而提高这一区域的探测覆盖率，保证对目标 监测的可靠性。 连通性问题关系到网络的许多问题，它关系到每个节点直接相连的节点数 目；关系到每条链路是否由于干扰的存在，是单向链路还是双向链路；同样也 关系到应用环境中发射功率控制问题。在军事应用环境中如何严格控制发射功 率，避免被敌方发现，而同时又保证数据的传输。 1 3 2 通信协议体系结构 一囤圈囤园 一 二二堕互二 网络层 叵e 数警路圈囤圈 镕 li 物理层 区因囤圃 图1 3 通信协议体系结构 通信协议体系结构是网络通信协议的集合，是对网络及其部件所应完成功 能的定义和描述。对无线传感器网络来说，其网络通信协议结构类似于t c p i p 6 第一章绪论 协议体系结构，但又不同于传统的计算机网络和通信网络。如图1 3 所示， 将通信协议体系结构分为物理层、数据链路层、网络层、传输层、应用层。以 下分别叙述各组成部分的功能以及相关研究的最新进展。 1 物理层1 1 7 】 无线电传输是目前w s n 采用的主流传输方式，需要解决的问题有：频段 选择、节能的编码方式、调制算法设计等。在频段选择方面，i s m 频段由于具 有无需注册、具有大范围的可选频段、没有特定的标准、可以灵活使用的优点， 被人们普遍采用。与无线电传输相比，红外线、光波传输具有不需要复杂的调 制、解调机制，接收器电路简单，单位数掘传输功耗小等优点。但由于不能穿 透非透明物体，只能在一些特殊的w s n 系统中使用。另外，光束通信容易受 周围环境中的光线及阳光干扰，但它比无线电通信更加高效，s m a r t d u s t 中就 采用光束为通信介质。声波和超声波通信主要应用在水下等特殊环境下。根据 网络应用环境的不同，传感器网络可能同时采用几种方式作为通信手段。目前， 对w s n 物理层的研究迫切需要解决的问题有：在降低硬件成本方面需要研究 集成化、全数字化、通用化的电路设计方法：在节能方面需要设计具有高数据 率、低符号率的编码、调制算法。 2 数据链路层 数据链路层用于建立可靠的点到点，点到多点的通信链路，主要涉及媒介 访问控制( m a c ) 协议【1 8 j 【1 9 j 【2 0 1 。现有的蜂窝电话网络、a dh o c 网络中的m a c 协 议主要关心如何满足用户的q o s 要求、节省带宽资源以及如何在节点高速移 动的环境中建立彼此间的连接，功耗是第二位的，这些协议并不适合w s n 。 c s m a 是典型的随机竞争类m a c 协议，虽然具有分布式、易扩展的优点，但 冲突会导致能量浪费和时延的不确定性。目前，w s n 的数据链路层还存在以 下一些问题需要深入的探讨：网络的动态性对信道分配策略的影响；在节能的 基础上，如何提高带宽的利用率和信道访问的公平性、降低通信延迟等。 3 网络层【2 l 】 网络层包括拓扑控制( 组网) 和路由两个部分。本文将在后续章节详细介 绍拓扑控制相关内容。传感器网络中路由算法主要分为平面路由协议和层次路 由协议，每个传感器节点所带的电量有限，然而通讯、计算、传感等过程都要 消耗能量，其中通讯是消耗能量的最主要过程，需要通过适当的路由算法，减 少网络中的计算量和通讯量，有效延长网络的寿命。 4 传输层1 2 2 】【2 3 j 【2 4 】 现阶段对传输控制的研究主要集中于错误饮复机制。参考文献【2 2 】分析了 端到端错误恢复机制在无线多跳网络中的性能。仿真表明，随着无线信道质量 第一章绪论 的下降( 信道错误率从1 上升到5 0 ) ，端到端错误恢复机制的性能下降很快 ( 发送成功率从9 0 下降到接近o ) 。【2 3 设计了一种快取慢存的数掘流控制机 制。通过在数据通路中的每个中间节点中都保持正确的数据包转发次序，来减 少错序报文的盲目转发。该方法可以有效地平衡中间节点的报文缓存数量，为 w s n 提供低开销的错误恢复服务。目前对w s n 传输控制的研究还很少。如 何在拓扑结构、信道质量动态变化的条件下，为上层应用提供节能、可靠、实 时性高的数据传输服务是今后研究的重点。 5 应用层口j 【2 6 j 【2 7 j f 2 8 j 应用层与具体的应用场合和环境密切有关，因此其设计不可能是通用的， 必须针对具体应用的需求进行设计。尽管如此，应用层的主要任务是获取数据 并进行初步处理，这一点是共同的。以数据为中心和面向特定应用的特点要求 w s n 能够脱离传统网络的寻址过程，快速有效地组织起各个节点的信息并融 合提取出有用信息直接传送给用户。同时，为了适应不同网络的需求，还要考 虑加入时钟同步阎【2 6 1 、定位技术【2 7 】【2 8 1 等功能。 1 3 3 支撑管理技术 管理支撑技术主要是对传感器节点自身的管理以及用户对传感器网络的管 理。根据不同网络的不同应用要求，需要不同的支撑技术来保证网络的正常工 作。 1 网络安全1 2 9 1 ： 传感器网络多用于军事、商业领域，安全性是其重要的研究内容。由于传 感器网络中节点随机部署、网络拓扑的动态性以及信道的不稳定性，使传统的 安全机制无法适用。因此需要设计新型的网络安全机制。可借鉴扩频通信、接 入认证、鉴权、数据水印、数据加密等技术 3 2 】。 2 远程管理f 3 0 】： 对于某些应用环境，传感器网络处于人不容易访问的地点，为了对传感器 网络进行管理。采用远程管理是十分必要的，通过远程管理，可以修正系统的 b u g ，系统升级，关闭子系统，监控环境的变化等，使传感器网络工作更有效。 3 q o s 支持【3 l j ： q o s 是网络与用户之问以及网络上互相通信的用户之间关于信息传输与共 享的质量的约定。为满足用户要求，传感器网络必须能够为用户提供足够的资 源，以用户可以接受的性能指标工作。 4 网络管理： 8 第一章绪论 网络管理是对网络上的设备及传输系统进行有效的监视、控制、诊断和测 试时所采用的技术和方法。网络管理功能主要有故障管理、计费管理、配置管 理、性能管理和安全管理。 5 ，能量管理： 在传感器网络中，电源能量是各个节点最宝贵的资源。为了使传感器网络 的使用时间尽可能的长，必须合理有效地利用能量。传感器网络的能量管理部 分控制节点对能量的使用。 6 移动控制1 3 3 】： 某些应用环境中，有一部分节点可以移动。移动控制负责检测和控制节点 的移动，维护到基站的路由，还可使传感器节点能够跟踪它的邻居。 7 数据库查询p 卅： 从用户的角度，整个传感器网络看起来更像一个数据库，可以从里面查询 需要的信息。如何按照一定的属性查询信息是个重要的课题，它包括查询数据 的组成形式、查询数据的路由选择等，合理的选择查询属性和路由可以有效的 节省能量。除了查询以外，另一个方向是有用数掘的广播，如何使有用的信息 快速准确地传播到需要使用这些信息的节点处，同时又不造成广播泛滥，节省 宝贵的能量也是亟待解决的问题。 1 4 主要内容及创新点 当前，国内外的研究人员已经取得了初步的研究成果，开发出了若干无线 传感器网络原型系统，在相关理论上也有较为广泛的研究。但是，在些关键 理论和技术上，仍有很多问题需要解决。我国在无线传感器网络方面的研究工 作还处于起步阶段。本文将结合国内外已有的研究成果，及本实验室在无线传 感器网络的研究中已经取得的成绩，重点研究网络拓扑控制方法中的分簇组网 算法。本论文还运用实验室在图论上的研究经验，将无线传感器网络的能量优 化问题转化为图论问题，并进行了实验和仿真。本文主要研究内容和创新点如 下： 1 第二章介绍了拓扑控制的相关概念，总结了传感器网络的能耗因素， 并在此基础上建立了无线传感器网络能量模型。详细分析了影响单跳簇状网能 耗的主要网络参数，对各参数的作用进行了分析，并最终得出结论。 创新点：分析了无线传感器网络能量的分布特点，通过对简易模型的数学 计算得出了参数变化对能耗的影响情况，并提出了提高网络的工作效率、延长 第一章绪论 生存期的可行方法。 2 第三章讨论了以最小能耗为目标的簇状网优化问题，同时提出种基 于遗传算法思想的新算法，该算法能够对输入的物理拓扑进行优化，并得出近 似最优解。 创新点：簇状网的逻辑拓扑优化问题属于n p 完全问题，本文提出的算法 通过对经典遗传算法的改进，能够找到此类问题的全局近似最优解。仿真试验 证明算法是可行的，且具有很快的收敛速度。 3 第四章针对当前分簇算法中簇头选择不合理及传输距离过长的缺陷， 提出了用于构建分布式簇树骨干网的e a c t 算法。算法引入了图论中极大权极 大独立集( m w m i s ) 和根树的概念，并借助簇头轮换机制均衡节点消耗。本 章通过计算机仿真验证了算法的性能。 创新点：本章提出的e a c t 算法通过引入具极大权极大独立集的概念，使 得到的簇头更具合理性，从而均衡了全网的节点耗能；并通过选择中继节点连 接簇头节点的方法解决了簇头距离过大耗能增加的问题，更进一步地延长了全 网的寿命。同时，e a c t 还具有低复杂度、易于维护、易于控制的特点，适用 于实际无线传感器网络。 1 0 第一二章簇状网能簧分析及优化 2 1 引言 第二章簇状网的能量分析及优化 传感器节点通常是一个微型的嵌入式系统，它的处理能力、存储能力和通 信能力相对较弱，通过携带能量有限的电池供电。由于传感器节点个数多、成 本要求低廉、分布区域广，而且部署区域环境复杂，有些区域甚至人员不能到 达，所以为传感器节点补充能源是不现实的。如何高效使用能量来最大化网络 生存周期是传感器网络面临的首要挑战。 定义1 ：无线传感器网络物理拓扑是指传感器节点在最大通信半径下的网 络连接关系，这是在节点抛撒后就固定的；而逻辑拓扑是指在满足网络覆盖率 和连通性的前提下，通过信息交互、功率控制等手段，剔除物理拓扑中节点间 不必要的物理通信链路，建立逻辑链路后形成的网络连接关系；形成逻辑拓扑 的过程称为光线传感器网络的拓扑控制，也叫组网，期间传感器节点运行的算 法称为组网算法。 定义2 ：将所有传感器节点进行一次数据采集，并传递给b s 的过程称为 一轮( 不同于 3 5 中r o u n d 的概念) ，网络进行一轮动作消耗的能量称为单轮 能耗；同时定义从网络启动到第一个节点耗尽能源下线的时间长度为网络生存 期。 对于自组织的无线传感器网络而言，拓扑控制( 定义1 ) 对网络性能影响 很大。良好的逻辑拓扑结构能够提高路由协议和m a c 协议的效率，为数据融 合、时间同步和目标定位等很多方面提供基础，有利于延长整个网络的生存期 ( 定义2 ) 。所以，拓扑控制是传感器网络中的一个基本问题，它有着十分重 要的意义，主要表现在： 1 决定整个网络的生存期。传感器网络的节点一般采用电池供电，节省能 量是网络设计主要考虑的问题之一。拓扑控制的一个重要目标就是在保证网络 连通性和覆盖率的情况下，尽量合理高效地使用网络能量，延长整个网络的生 存时j 日j ； 2 影响节点| 日j 通信效率。传感器网络中节点是随机抛撤的，每个节点必须 根据邻接情况调节通信功率。如果节点通信功率过大，会加剧节点之间的干扰， 降低通信效率，并造成节点能量的浪费。而过小的通信功率则会影响网络的连 第二章簇状网能餐分析及优化 通性。所以，使节点选择合理的通信功率也是无线传感器网络主要考虑的问题 之一： 3 为路由协议提供基础，在传感器网络中，只有活动的节点才能够进行数 据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的 邻居关系； 4 影响数据融合。传感器网络中的数据融合是指传感器节点将采集的数据 发送给骨干节点，骨干节点进行数据融合，并把融合结果发送给观测者。而骨 干节点的选择是拓扑控制的一项重要内容； 5 弥补节点失效的影响。传感器节点可能部署在恶劣环境中，很容易受到 破坏而失效。这就要求网络拓扑结构具有一定的容错性，能够及时响应网络结 构的变化。 表2 1 传感器节点的能耗分布 能耗符号 能耗位置节点动作 e s e n s e 传感器部件及辅助电路进行一次传感器采样 e t x 无线通信模块发送l b i t 数据 e 。无线通信模块接收l b i t 数据 e h j ，“ 无线通信模块侦听信道l m s z o n 出f 处理器模块产生或分析一个数据包 e 血s 处理器模块压缩一个数据包 啄椭 处理器模块读取f l a s h 数据 表2 1 列出了传感器节点的能耗分布。传感器节点消耗能量的模块包括传 感器模块、处理器模块和无线通信模块。传感器模块负责从环境中采集需要监 控的数据信息；处理模块是节点的核心部分，通常为低功耗的微处理器；通信 模块则用于节点间通信，通常为射频、红外、蓝牙等无线装置。根据每个模块 不同的状态，节点可以工作于发送、接收、空闲和睡眠四种模式下。当收发器 发送或接收消息时，节点分别工作在发送或接收模式。空闲模式下收发器不发 送或接收任何消息，但是随时准备执行这些任务。睡眠模式则是节点关闭通信 模块，并且处理模块进入低能耗的状态，但此时传感部件仍然正常工作。这 四种模式中，传感器节点的无线通信模块在空闲状态使得能量消耗与在收发状 态时相当，所以只有关闭节点的通信模块，4 。能大幅度地降低无线通信模块的 能量开销。 第一二章簇状网能龄分析及优化 分簇组网依据一定机制选择某些节点作为骨干节点，打开其通信模块，并 关闭非骨干节点的通信模块，由骨干节点构建一个连通网络来负责数据的路由 转发。这样既保证了原有覆盖范围内的数据通信，也在很大程度上节省了节点 能量。在这种机制下，网络中的节点可以划分为骨干节点和普通节点两类，也 称为簇头节点和成员节点。簇头节点对周围的成员节点进行管理，这类组网算 法将整个网络划分为相连的区域，一般又称为分簇算法，而这种算法形成的逻 辑拓扑结构称为簇状网。由于簇头节点需要协调簇内节点的工作，负责数据的 融合转发，能量消耗相对较大，所以分簇算法通常采用周期性地选择簇头节点 的做法以均衡网络中节点能量消耗。簇状网具有很多优点，例如，由簇头节点 担负数据融合的任务，减少了数掘通信量：簇状网有利于分布式算法的应用， 适合大规模部署的网络；由于大部分节点可以在相当长的时间内关闭通信模 块，所以显著地延长了整个网络的生存期。当前分簇算法形成的簇状网有单跳 簇状网和多跳簇状网两种”“。 眢、= 囊 ：；t 。i 一la 。 。1 、一。 图2 1 单跳簇状网 衣分、夕于 0 叫? 厦：一一 t 、；：、 、 ； j 一 图2 2 多跳簇状网 如图2 1 所示，单跳簇状网是指网络成簇后，成为簇头的节点直接将簇内 消息发送给b s ，经典的l e a c h “1 算法就是这种网络。多跳簇状网( 图2 2 ) 是对单跳簇状网的改进，它要求成为簇头的节点再进行交互，使数据通过簇头 问的转发到达b s 。 本章对单跳簇状网进行分析，根掘其特点建立网络、数学模型，并在此基 础上讨论几个主要网络参数与网络能耗之| 日j 的关系，并均衡、优化这些参数， 以最小化单轮能耗。本章组织如下：第二部分给出网络模型、能量模型和数学 模型；第三部分列出影响能耗的主要参数；第四部分在模型的基础上对参数进 行了讨论、优化。 一13 文鼹 第一二章簇状网能颦分析及优化 2 2 模型的建立 2 2 1 能量模型 图2 3 无线通信模块能量模型 为了衡量不同算法和协议的能量消耗和性能，设计一个能准确地模拟实际 传感器网络特性的传感器节点能量模型是很重要的，本文采用【3 5 】给出的传感 器节点的收发器能量模型，如图2 3 所示。即若将一个长度为k - b i t 的分组 ( p a c k e t ) 消息传送距离工米，则收发器为了发送这个消息需耗能： 瓦( 七，互) = 取一删”+ 么一w m ，) = 七( + t x ”) ； 节点接收这个消息的能耗为： ( 七) = - d e c ( ”= 鸩5 ( 2 一1 ) ( 2 2 ) 其中：，l ( j b i t ) 表示无线发射装置每发送单位b i t 数据的耗能；肛4 为射频功 率放大器的能耗，其中传输系数口( j b i t m ) 考虑了数据传送过程中的能量衰 减，而衰减指数n ( 2 n 4 ) 的取值主要依赖于周围的环境。当网络环境平 坦、无障碍时，n 取值为2 ，对应传输系数为m ；而在建筑物、植被茂密的区 域或进行远距离传输时，h 取值为3 5 ，对应传输系数为。厶( j b i t ) $ j j 表示 无线接收装置接收单位b i t 数据的耗能，一些近似计算模型【”】中认为如= ，】：，。 其中，作为中转的节点不但要接收消息，还需要将消息转发给其他节点， 因此，将k b i t 的消息转发x 米需耗能： e 0 m ( t ，x ) = ( 七) + 露( 后，x ) = 七( + 厶+ t x ”) = k ( 2 1 + x “) ；( 2 - - 3 ) 考虑到节点采样数据、微处理进行计算所消耗的能量是很难优化的，且要 远小于传感器节点收发消息而耗费的能量，因此，模型忽略节点传感器模块及 微处理器模块的能量消耗。 第一二章簇状网能苗分析及优化 2 2 2 网络模型 丝避骧影 图2 - - 4 单跳簇状网模型 本章主要分析单跳簇状网的能耗情况，首先为其建立网络模型。单跳簇状 网要求簇头节点直接和b s 通信，其发送消息的距离决定于距b s 的距离。简 单起见，假设b s 与簇头节点的距离相同。 如图2 4 所示，假设由0 个无线传感器节点组成的无线传感器网络，放 置在m m 的正方形区域内。节点周期性地采集数据，并汇报给远处的b s ， 这里假设b s 位于区域正上方高度为d 的飞行器内。网络中的节点自组成网， 并划分为k 簇，每个簇均选举一个节点作为簇头，簇头节点收集本簇内所有节 点的数据，进行数据融合p 9 】后发送给飞行器。模型假设此网络具有以下特点： 1 1节点结构相同，分布服从均匀分布。发射功率可调，并具有相同的最 大通信半径。假设簇头节点可直接将数据发送给基站b s ，b s 位于监控区域垂 直距离d 处； 2 )不在彼此通信范围中的两个节点交互信息时，需要通过其他节点中转； ，3 1数据包具有相同的长度，一个节点一次只能发送一个数据包，成员节 点不对转发的数据进行压缩，簇头节点不论接收到消息的个数而只发送一个数 据包； 4 )单簇内所有节点使用同一信道通信，不同簇使用不同的信道通信，且 不考虑因消息碰撞造成的数据丢失。 2 2 3 数学模型 根据网络模型的特点，建立如图2 5 所示簇的数学模型。模型以簇头节点 为圆心，以节点通信半径的自然数倍做圆，将簇划分为m 层。这样，在优化 的传输链路下，簇的颤尼聊) 跳成员必然位于第k 层圆环内，且数掘尽可能沿 半径方向传输以减少能量消耗。把簇内成员节点将消息发送给簇头节点所允许 第一二章簇状网能鼙分析及优化 经历的最大跳数m 称为最大允许跳数，并把做出这样限制的网络称为埘跳分 簇网络。 j弋 历 、i 八 瓣秆 犍钞。 图2 5 单簇数学模型 下面，将借助本节建立的模型分析单跳簇状网的能耗情况，并对其进行优 化，得出减少能耗的可行方法。 2 3 参数分析 1 ) 监控区域面积 无线传感器网络的主要功能是对特定区域的环境、事件进行监控。监控区 域面积由应用目的决定，是不可改变的。此处，假设监控区域为m x m 的正 方形区域； 2 ) 抛撒节点数 抛撒节点数胁直接决定于监控区域的面积及监控信息的精细度。在保证节 点均匀抛撒的前提下，监控面积越大，对监控细节要求越高，就越大，反 之，节点数就越少。同时，节点的抛撒应保证网络的探测覆盖率h o l ，当给定通 信半径，在一定区域内抛撒多少点才能对环境实现可靠的监控是设计无线传感 器网络的一个基本问题。 ， 3 ) 簇内最大允许跳数埘 簇内最大允许跳数限制了簇的规模，在给定节点邻接关系的情况下，增大 m 值将扩大单簇的规模，从而减少了簇头数；但如果m 值过大，将造成单簇 的规模过大，链路过长，使得拓扑不易管理，且数据转发次数也就相应增加， 因此，m 的取值一般限制在3 跳以内。 4 ) 节点通信半径r 第一二章簇状网能量分析及优化 传感器节点的通信半径是网络的重要属性，当节点位置固定后，合理的设 置r 的取值能够很好的节省网络能量。首先，节点的通信半径应该足够大以保 证网络的连通性。文献e 4 1 1 1 4 2 都给出了为了保证网络连通，计算r 最小取值 的公式。其中 4 2 假设，1 个节点随机地均匀分布在一定区域内，那么，单位面 积网络连通的概率应满足： p ( c o n n e c t i v