（通信与信息系统专业论文）基于移动代理的无线传感器网络拓扑发现及优化分簇算法.pdf

摘要 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 是由部署在监测区域内 大量的能量有限的微型传感器节点组成，通过无线通信方式形成的多跳的自组织 的网络系统。然而由于无线传感器网络与传统的无线网络有很大的不同，传统网 络设计的通信协议不能直接应用于无线传感器网络。基于无线传感器网络自身的 特点和应用，开发专用的通信协议和测量方法成为无线传感器网络领域内亟待研 究的课题。 本文主要针对无线传感器网络领域内的拓扑发现算法和分簇路由算法进行研 究。提出了一种基于移动代理的拓扑发现算法，旨在解决无线传感器网络中分级 拓扑结构下的拓扑发现问题。该算法融合了移动代理技术和分级网络拓扑结构的 特点，同时对移动代理的迁移策略进行了改进，用于数据收集，周期性任务分配 和网络状态的监测。通过n s 2 仿真证实，该算法在扩展性和收敛速度方面都有着 较好的性能，有效地减少了冗余数据的传输，降低了通信损耗，延长了网络的生 命周期，为无线传感器网络路由设计提供了参考。 其次，提出了一种基于l e a c h 协议的优化分簇路由算法n d e a ( n o d ed e g r e e a n de n e r g y a w a r er o u t i n ga l g o r i t h m ) ，算法综合考虑节点度和剩余能量因素，为每 个节点定义一个权值函数w ( n ) ，作为簇首选择的标准。通过n s 2 仿真证明，n d e a 算法能够优化簇的分布，平衡网络负载，有效的降低了能量的损耗，从而延长了 网络的生命期。 最后，对全文作出总结，并展望了下一步的工作。 关键词：无线传感器网络拓扑发现分簇移动代理 a b s t r a c t 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 s ( w s n s ) c o n s i s to fal a r g en u m b e ro ft i n y , l o w - p o w e r e d s e n s o r st h a t c o m m u n i c a t ew i t he a c ho t h e rt h r o u g hm u l t i h o pw i r e l e s sl i n k sf o r m o n i t o r i n gaf i e l do fi n t e r e s t h o w e v e ld u et ot h eg r e a td i f f e r e n c e sb e t w e e nw s n s a n dt r a d i t i o n a lw i r e l e s sn e t w o r k s ，t r a d i t i o n a lc o m m u n i c a t i o np r o t o c o l sc a n n o tb e d i r e c t l ya p p l i e dt ow s n s t h e r e f o r e ，t h ed e v e l o p m e n to fs p e c i f i cc o m m u n i c a t i o n p r o t o c o l sa n dm e a s u r e m e n tw h i c hi sb a s e do nt h ec h a r a c t e r i s t i c sa n da p p l i c a t i o n so f w s n sh a sb e c o m ea ni m p o r t a n ti s s u ei nw s n s i nt h i sd i s s e r t a t i o n , w ef o c u s eo nt o p o l o g yd i s c o v e r ya l g o r i t h m sa n dc l u s t e r i n g r o u t i n ga l g o r i t h m si nw s n s f i r s t l y , at o p o l o g yd i s c o v e r ya l g o r i t h mb a s e do nm o b i l e a g e n ti sp r o p o s e dt od i s c o v e rn e t w o r kt o p o l o g yi nh i e r a r c h i c a lt o p o l o g y 黝t h e c o n s i d e r a t i o no fm o b i l ea g e n ta n dt h ec h a r a c t e r i s t i c so fh i e r a r c h i c a ln e t w o r kt o p o l o g y , t h em i g r a t i o ns t r a t e g yo fm o b i l ea g e n t sh a sa l s ob e e ni m p r o v e d t h ea l g o r i t h mc a nb e e f f e c t i v e l yu s e df o r d a t a c o l l e c t i o n ，p e r i o d i c t a s ka l l o c a t i o na n dn e t w o r ks t a t u s m o n i t o r i n g n en e t w o r ks i m u l a t i o np l a t f o r mi sb u i l ti nn s - 2a n ds i m u l a t i o nr e s u l t s s h o wt h a tt h et o p o l o g yd i s c o v e r ya l g o r i t h mg e t sab e t t e rp e r f o r m a n c ei ne x p a n s i b i l i t y a n d c o n v e r g e n c y , a n dc a l lr e d u c et h et r a n s m i s s i o no fr e d u n d a n td a t aa n d c o m m u n i c a t i o nc o n s u m p t i o n ，t h er e s u l t sa l s os h o wt h a tt h ea l g o r i t h mc a ne x t e n dt h e n e t w o r kl i f e t i m ea n db er e f e r e n c et or o u t i n gp r o t o c o ld e s i g ni nw s n s t h e n , w ep r o p o s ea ni m p r o v e dc l u s t e r i n gr o u t i n ga l g o r i t h mn d e a ( ar o u t i n g a l g o r i t h mb yn o d ed e g r e ea n dr e s i d u a le n e r g y ) b a s e do nl e a c h ( l o w - e n e r g y a d a p t i v ec l u s t e r i n gh i e r a r c h y ) i nt h i sa l g o r i t h m ，an e ww e i g h ti si n t r o d u c e dt os e l e c t c l u s t e rh e a d 、i t l lr e s i d u a le n e r g ya n d n o d ed e g r e e t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mn d e ac a no p t i m i z ec l u s t e r i n ga n db a l a n c en e t w o r kl o a d a n d g r e a t l yi m p r o v et h en e t w o r k l i f e t i m e f i n a l l y , w ec o n c l u d et h ep a p e ra n dg i v es o m es u g g e s tf o rf u t u r ew o r k s k e y w o r d s ：w s n st o p o l o g yd i s c o v e r yc l u s t e r i n g m o b i l ea g e n t 第一章绪论 1 1 1 无线传感器网络概述 第一章绪论 1 1 研究背景 在网络通信技术迅速发展的同时，一个非常有意义且充满挑战的研究领域一 一无线传感器网络也迅速发展并走向成熟。无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，w s n s ) 是由部署在监测区域内大量的廉价微型传感器节点组成，通过 无线通信方式形成的多跳的自组织的网络系统，其目的是协作地感知、采集和处 理网络覆盖区域内感知对象的信息，并发给观察者【l 】。无线传感器网络综合了现 代传感器技术、微电子技术、通信技术、嵌入式计算技术和分布式信息处理技术 等多个学科，是一个新兴的交叉研究领域，并被应用于军事侦察、环境监测、医 疗健康和空间探索等，遍布生活的各个层面，特别是在国防和重大灾害事件监测 等领域，将对我国的现代化建设起到十分重要的作用【2 】。 无线传感器网络具有巨大的应用前景，被认为将是对2 l 世纪产生具有重大影 响力的技术之一。2 0 0 3 年美国的技术评论杂志将无线传感器网络技术列为未 来改变人类生活的十大技术之首。在我国国家中长期科学和技术发展规划纲要 ( 2 0 0 6 - - - 2 0 2 0 年) 中，无线传感器网络被列为优先发展的主题。美国o a k 实验 室预言：r r 时代正从“t h en e t w o r ki sc o m p u t e r 向“t h en e t w o r ki ss e n s o r ”转变。 1 1 2 无线传感器网络的体系结构 l 、传感器网络结构 典型的无线传感器网络结构如图1 1 所示，传感器网络系统通常包括传感器 节点( s e n s o rn o d e ) 、汇聚节点( s i n k ) 和管理节点。大量的传感器节点随机部署 在监测区域内部或附近，能够通过自组织方式构成网络。传感器节点监测的数据 沿着其他传感器节点逐跳进行传输，在传输过程中监测数据可能被多个节点处理， 也可能未作任何处理，经过多跳路由到汇聚节点，最后通过互联网或卫星到达管 理节点。反之，用户也可以通过管理节点对无线传感器网络进行配置和管理，发 布监测任务以及收集监测数据等【1 1 。 2 、传感器节点结构 随着制作工艺的发展，现代传感器节点体积越来越小，能耗也越来越低。针 2 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 对不同的应用，传感器节点设计也各不相同，但它们的基本结构是大致一样的。 图1 1 无线传感器网络结构 一般而言，传感器网络节点的基本组成包括如下四个基本单元：传感单元( 包 括传感器和模数转换模块) 、处理单元( 包括c p u 、存储器、嵌入式操作系统等) 、 无线通信单元和能量供应单元。此外，可以选择的其他功能单元包括：定位系统、 移动系统以及电源自供电系统等，如图1 2 所示。传感单元负责监测区域内信息 的采集和数据转换；处理单元负责控制整个传感器节点的操作，存储和处理自身 采集的数据以及其他节点发来的数据；通信单元负责与其他传感器节点进行无线 通信、交换控制消息和收发数据；能量供应单元为传感器节点提供运行所需的能 量，通常采用微型电池供电。 图1 2 传感器节点结构 3 、传感器网络协议体系结构【l j i z j 网络体系结构通常指网络的协议分层以及网络协议的集合，是对网络及其部 件所有完成功能的定义和描述。无线传感器网络的体系结构不同于传统的计算机 网络和通信网络。研究表明，无线传感器网络的体系结构包含三部分，即分层的 网络通信协议、传感器网络管理以及应用支撑技术，如图1 3 所示。 分层的网络通信协议与互联网协议栈的五层协议相对应，包含物理层、数据 链路层、网络层、传输层和应用层。物理层提供简单但健壮的信号调制和无线收 发技术，包括信道的选择、无线信号的检测、信号的发送与接收等；数据链路层 第一章绪论3 负责数据成帧、帧检测、媒体访问和差错控制，使之对网络显现为一条无错的链 路；路由层主要负责路由生成、路由选择等；传输层负责数据流的传输控制，提 供可靠的、开销合理的数据传输服务；应用层包括一系列基于检测任务的应用软 件【。 传感器网络管理技术主要是对传感器节点自身的管理以及用户对传感器网络 的管理，例如能量管理、拓扑管理、q o s 支持、网络管理、网络安全、移动控制、 远程管理等。 传感器网络的应用支撑技术是建立在分层协议和网络管理技术的基础上，为 用户提供了各种具体的应用支持，包括时间同步、节点定位以及向用户提供协同 应用服务接口等 3 1 。 应用支持技术 臣亟亟圃 二巫堑堕堕 訾i 时间同步l fl 定位i，五 li- 传输 层 传输控制 1 i 毛 服网网移远 曹f 路由 l 里 拓扑管理i 务络络 动程 ，荭il管 i质 管安控管 理量 理全制理 殳据链路 媒体接入拓扑 层 眢r f0 i r i o p t i c a l1 分层的网络通信协议 传感器网络管理技术 图1 3 传感器网络协议体系结构 1 1 3 无线传感器网络的特点 l 、大规模网络。为了获取精确信息，在监测区域通常部署大量的传感器节点， 传感器节点数量可能达到成千上万，甚至更多。大规模包括两方面的含义：一是 节点数量众多；二是节点分布密集。大量冗余节点的存在能够增大覆盖区域，减 少洞穴和盲区，从而使得系统具有很强的容错性。 2 、自组织。与a dh o e 网络类似，无线传感器网络的布设和展开不依赖于任 何预设的网络设施，节点通过分层协议和分布式算法协调各自的行为，节点开机 后就可以自动、快速地组成一个独立的网络。在传感器网络使用过程中，部分节 点可能由于能量耗尽或环境因素而失效，或节点增加到网络中，使网络的拓扑结 构随之动态变化。传感器网络的自组织性要能够适应这种网络拓扑的动态变化。 4 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 3 、可靠的网络。传感器网络通常部署在恶劣环境或人类不宜到达的区域，节 点容易遭n # i - 界环境的破坏，并且传感器节点往往采用随机部署，这些都要求传 感器节点能够适应各种恶劣的环境。其次，由于监测区域的限制以及传感器节点 数量巨大，网络维护变得很困难，传感器网络的通信保密性和安全性也十分重要， 要防止监测数据被盗取和获取伪造的监测信息。因此，传感器网络的软硬件必须 具有很好的鲁棒性和容错性。 4 、与应用相关【l 】【4 】。传感器网络用来感知客观物理世界，获取物理世界的信 息量，不同的传感器网络应用关心不同的物理量。传感器网络不像i n t e m e t 一样， 有统一的通信协议平台，不同的应用背景对传感器网络的要求不同，其硬件平台、 软件系统和网络协议都会有很大的差别。 5 、资源有限。无线传感器网络中，节点只能携带有限的电池能量，且在应用 过程中不可能更换电池，因此能量相当受限。其次，节点只具有有限的硬件资源， 其计算能力和对数据的处理能力相当受限。 6 、以数据为中心【4 j 。无线传感器网络中节点数量巨大，加上节点放置的随机 性和网络拓扑的动态变化特性，节点并不需要也不可能以全局唯一的i p 地址来标 识，只需要使用局部可以区分的节点标识即可。用户对监测数据的收集，是以数 据为中心进行的，并不依赖于节点的标识【5 j 。 1 1 4 无线传感器网络的应用 无线传感器网络由于其快速展开、抗毁性强、监测精度高、覆盖区域大等特 点而产生了广阔的应用前景，并被广泛应用到军事、环境科学、智能家居、健康 护理、城市交通、空间搜索、安全监测等领域。随着传感器网络的深入研究，无 线传感器网络将逐渐深入到人类生活的各个领域中。 1 、军事应用。传感器网络的研究最早起源于军事领域。其快速部署、自组织、 隐蔽性强和高容错性的特点使无线传感器网络非常适用于军事应用。传感器的上 述特点使它具有重大的军事价值，主要用于监测人员、装备以及单兵系统；监测 敌军进攻；评估战果；侦查核能、生物、化学攻击等1 2 1 。 2 、环境科学。随着人们对环境的日益关注，环境科学所涉及的范围越来越广 泛。无线传感器网络的研究通常用于跟踪侯鸟和昆虫的迁移，分析环境变化对农 作物的影响，监测降雨量等，同时它对准确、及时地预防森林火灾也有一定帮助。 3 、医疗健康。无线传感器网络在医疗方面也日渐发挥作用。通过在病人身上 安装用于监测身体机能的微型传感器节点，如心率和血压监测设备等，医生可以 从医院里远程监视这些测试人群的健康状况t 2 t 3 1 ；还可以将一些微型传感器植入 人体器官中或以吞服的方式让传感器进入人体，也就是所谓的智能胶囊，用来随 第一章绪论 5 时观测器官的生理状态，如果发现器官功能恶化，及时采取措施。 4 、其他方面的应用。无线传感器网络在城市交通，安全，空间搜索以及商业 领域也有很广阔的应用前景。例如借助于航天器在外星体表面撤播一些传感器节 点，可以对星球表面进行长时间的监测；布置在道路上的传感器用于监测交通流 量等信息，为出行者提供信息服务，如果发现违章记录能及时报警和记录；布置 在建筑物中的用于监测温度、湿度、压力和辐射的传感器，可以发现火灾等异常 事件并及时报警等。 在不久的将来，无线传感器网络将是一个无孔不入的十分庞大的网络，其应 用会涉及到人类日常生活和社会生产活动的所有领域。 1 2 研究意义及现状 世界的一些知名研究机构，诸如麻省理工学院、哈佛大学、加州大学伯克利 分校和洛杉矶分校、康奈尔大学、南加州大学、斯坦福大学等，还有一向以革新 著称的i n t e l 、微软、d u s t 、c r o s s b o w 等公司都陆续投入到了这场新的抢占科研 制高点的战役中；国内也有不少大学和研究机构对此进行了大量的研究。到目前 为止，传感器网络的研究集中在两个方面：利用m e m s ( m i c r o e l e c t r o m e c h a n i s m s y s t e m ，微机电系统) 技术设计小型化的节点设备和对网络本身的研究。节点设 计的基本原则是采用尽量灵敏的传感器、尽量低功耗的器件、尽量节省的信号处 理和尽量持久使用的电源，由于电池体积有限，单位体积内的电池容量大幅提高 十分困难，有限的电量成为无线传感器网络发展的瓶颈之一，电池无线充电技术 成为人们关注和研究的方向。另外，将太阳能和节点供电结合在一起也是无线传 感器网络节点设计的一个潜在的发展方向【5 】，代表性的研究项目有w i n s 和s m a r t d u s t 。 另外，无线传感器网络有着分层的体系结构，每一层都有需要结合传感器网 络的特点进行细致研究的问题，就已有的研究而言，主要集中在m a c 层和网络 层。m a c 层主要用来构建底层的基础结构，控制传感器节点的通信过程和工作 模式，目前对m a c 的研究主要分为基于c s m a c a 的m a c 协议改进和基于 t d m a 的m a c 协议改进两大类；网络层的路由协议主要负责监测信息的传输路 径选择，在无线传感器网络中，路由协议不仅关心单个节点的能量消耗，更关心 整个网络能量的均衡消耗，这样才达到延长整个网络生命期的目的，因而路由协 议的设计对无线传感器网络显得尤为重要【l 】。然而由于无线传感器网络与传统的 无线网络有很大的不同，为传统网络设计的路由协议不能应用于无线传感器网络。 基于无线传感器网络自身的特点和应用，开发专用的路由协议成为无线传感器网 络领域内亟待研究的课题。 6 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 卜、一一、一，卜：f 一7 二一：一 一一一。- 7 7 、：i i 一- - 、0 图1 4 平面拓扑结构 在分级路由协议中，传感器节点被划分为若干个簇，每个簇按照一定的规则 选取一个节点作为簇首，其他节点作为该簇的成员节点，簇首负责管理和控制簇 内的成员节点，协调成员节点之间的工作，负责簇内信息的收集、信息融合以及 簇间信息的转发，节点采集的数据在簇首节点处进行数据融合，再由簇首发给s i n k 节点，分级拓扑结构如图1 5 所示，典型的分级路由协议有l e a c h 协议、t e e n 协议等。分级路由的设计可以有效的减少网络流量和路由开销，克服了平面路由 协议扩展性差的缺点。主要优点有成员节点功能简单，没有数据传输时可以关闭 通信模块，很大程度上节省了网络能量的消耗；簇首进行数据融合之后再进行信 息的转发，减少了冗余数据的通信；分级拓扑结构便于管理，有利于分布式算法 的应用，能够对系统变化做出快速的反应。由此可见，分级路由协议对于提高无 线传感器网络的整体性能、保障网络可靠性、节省能量、提供q o s 路由方面有较 大的优势。设计性能良好的分级路由协议已经成为无线传感器网络的重要研究内 容。 为了使无线传感器网络性能达到最优，针对不同应用，选择适用的网络通信 协议，另一个研究领域引起了人们的关注无线传感器网络拓扑发现。拓扑发 现的目的是获取和维护网络节点的存在性信息以及它们之间的连接关系的信息， 并在此基础上绘制出网络拓扑图，管理人员通过拓扑结构信息对网络故障进行定 第一章绪论 7 二7 、一一一一、_ 、 、裂,ii-_差,：i：i琴嘉) l 一专一一。孙 ( 二7 鲈一矿0 。越6 黔二) 、9g 。 垒 8 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 方法不能提供瞬时的网络拓扑，发现完整的网络拓扑需要很长的时间，并且需要 分发很多消息，因而效率不高且消耗带宽。 r a n v e e rc h a n d r a 提出一种基于网状网的拓扑发现算法，该方法分为两步：一 是扩散阶段，协调节点广播拓扑请求消息，每个节点接收并重新广播这条消息后， 构造本地邻居信息，更新相应的数据结构；二是收集阶段，所有节点向协调节点 转发本地邻居信息。为保证算法的可靠性，每一个节点接收k 个来自父节点的请 求，重新广播它们。同时为了保证广播的稳健性，采用了改进的r t s c t s 机制。 结果表明，该方法能够在包含不稳定链路的情况下正常工作。 这些方法要么需要网络管理协议s n m p 的支持，要么需要发送大量的数据包 进行探测，开销太大。因此要针对无线传感器网络能量有限、协议特点提出特有 的拓扑发现方法，以平衡网络负载、分担脆弱节点的业务量，从而能够提高网络 生存能力。 1 3 本文的工作及章节安排 本文的主要工作： l 、在参照了已有的一些拓扑发现算法的基础上，本文提出了一种基于移动代 理的拓扑发现算法，旨在解决无线传感器网络中分级拓扑结构下的拓扑发现问题。 该算法融合了移动代理技术和分级网络拓扑结构的特点，簇首节点收集成员节点 的信息并进行数据融合，在簇首节点上运行移动代理来获得簇首层的链路信息， 同时对移动代理的迁移策略进行了改进，仿真证明该算法能够近似准确的发现无 线传感器网络拓扑，为更加有效地配置监测点提供了依据。 2 、根据无线传感器网络特有的属性，研究其适合的路由算法，以达到平衡网 络负载、分担脆弱节点的业务量、提高网络生存能力的目的。提出了一种基于 l e a c h 算法的优化分簇路由算法n d e a ( ar o u t i n ga l g o r i t h mb yn o d ed e g r e ea n d r e s i d u a le n e r g y ) ，传感器节点在选择簇首时，综合考虑节点度和剩余能量，保证 网络整体达到能量和负载的均衡，从而延长了网络的生存时间。 文章中将本文提到的两个算法在n s 2 仿真平台上进行了仿真实现，并对仿真 结果进行了比较分析。结果证明，本文提到的算法比现有算法有更大的节能优势， 并且达到了预期的研究目标。 文章的章节结构组织如下： 第一章绪论部分。在这一部分中介绍了课题的研究背景，包括传感器网络的 概念、体系结构、特点以及应用，无线传感器网路路由算法和拓扑发现算法的研 究现状与意义，最后介绍了本文主要的研究工作和章节结构。 第二章相关背景知识的介绍。首先介绍了几种经典的分簇路由算法的基本思 第一章绪论9 想以及它们的优缺点，然后简要介绍了移动代理技术的概念，特点和应用。 第三章提出了一种改进的基于移动代理的拓扑发现算法，本章首先从整体上 介绍了该算法的设计思路及基本思想，然后详细描述了该算法的设计流程与实现 细节，最后通过网络仿真工具n s 2 验证了该算法的可行性。 第四章在l e a c h 算法的基础上，提出了一个兼顾能量均衡和负载均衡的分 簇路由算法，本章对该算法的提出、设计、算法流程进行了详细的介绍，最后通 过n s 2 仿真分析了该算法在实现网络节能，延长网络生命期方面的优势。 第五章对文章所做工作进行总结，并指出下一步还要进行深入研究的内容。 1 0 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 第二章无线传感器网络分簇路由算法概述及移动代理技术 1 l 第二章无线传感器网络分簇路由算法概述及移动代理技术 2 1 无线传感器网络的分簇路由算法研究 迄今为止，已经提出了很多种典型的无线传感器网络分簇算法，根据簇首的 产生方式，分簇算法可分为分布式算法和集中式算法。分布式算法通常根据某个 阀值自主决定是否当选簇首或者通过节点之间的信息交互动态产生簇首，不需要 网络的全局信息。集中式分簇算法是指由基站基于整个网络信息选择簇首，生成 的簇结构一般比较合理，但是能耗较大。下面介绍几种典型的分簇算法。 2 1 1l e a c h 分簇路由算法 l e a c h p l ( 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 ) 全称低功耗自适应分 簇路由算法。是2 0 0 0 年m i t 电子工程和计算机科学系的w e n d ih e i z e l m a n 等人为 无线传感器网络专门设计的路由协议，它是第一个提出的数据聚合的分级路由协 议，l e a c h 主要通过循环的方式随机选择簇首节点，以平衡整个网络的能量消 耗。它定义了“轮 的概念，每轮由簇首选择，簇的形成和稳定数据传输三个阶 段组成。图2 1 为l e a c h 算法的一轮工作过程。 簇形成阶段 图2 1l e a c h 算法的一轮工作过程 簇首选择阶段负责选出这一轮所有的簇首节点，主要选取原则为：每个传感 器节点生成一个卜1 之间的随机数，该随机数若小于定义的阀值t ( n ) ，则被选 为簇首，并发布自己成为簇首的广播消息；若不是，则为成员节点。如果节点已 经当选过簇首，则把t ( n ) 设置为0 ，这样节点以后不会再被选为簇首【引。 2 ( 刀) = 可p 习 p - ， 0其他 1 2 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 其中p 是网络中簇首数在所有节点中的百分比，是当前的选取轮数，g 为 最近1 p 轮不是簇首的节点集。 在簇的形成阶段中，被选为簇首的节点向其他节点发广播消息告知自己是新 簇首，其他节点根据接收信号的强度选择加入的簇，并告知簇首，这样簇就形成 了。之后簇首为每个成员分配t d m a 时隙并告知簇内各成员，当节点有数据发送 时，簇首收集节点监测到的数据发往s i n k 节点。图2 2 为l e a c h 算法中簇的形 成流程图。 图2 2l e a c h 算法中簇的形成算法流程图 2 1 2l e a c h c 和l e a c h f 分簇路由协议 l e a c h c ( l e a c h c e n t r a l i z e d ) 分簇路由协议是在l e a c h 协议的基础上改 进的一种集中式的簇首选择机制，不同于l e a c h 协议随机选择簇首的方式。每 轮开始时每个节点把自己的位置和当前能量情况报告给s i n k 节点，s i n k 计算出网 络中节点的平均能量，能量高于平均值的节点被选作候选簇首，然后采用模拟退 火算法从候选节点中选出数量合适且位置最优的节点作为簇首，最后s i n k 节点将 分簇结果广播给各个节点。 l e a c h f 9 1 ( l e a c h f i x e d ) 也是l e a c h 的一种改进算法。簇的形成过程 第二章无线传感器网络分簇路由算法概述及移动代理技术 1 3 与l e a c h c 类似，基站同样采用模拟退火算法生成簇。不同的是，基站为每个 簇生成一个簇首列表，指示簇内节点轮流当选簇首的顺序，也就是说簇一旦形成 就不再改变，只是簇首根据簇首列表依次成为簇首。 l e a c h c 算法每轮选出的簇首的数目稳定且分布比较均匀，但分簇的过程 需要网络的全局信息，扩展性较差。 l e a c h f 算法减少了成簇的开销，且簇首分布总体上比较平均，但它不适用 于真实的网络应用，当动态加入、移动或移除节点，网络的适应性较差，同时还 可能导致节点离其他簇的簇首比离自己的簇首更近，增加了簇间的信号干扰。 2 1 3p e g a s i s 分簇路由算法 严格意义上讲，p e g a s i s ( p o w e r - e f f i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o n s y s t e m s ) 算法并不属于簇类协议，它没有簇构造的过程，只是沿用了簇和数据融 合的思想。首先每个节点通过定位技术发现自己最近的邻居节点，同时调整发送 信号的强度以便只有该邻居节点能够听到；然后从距离基站最远的节点开始，采 用贪婪算法把传感节点组织成一条链，节点只与距离它最近的邻居节点通信，并 且每轮中只选一个节点作为l e a d e r 与s i n k 通信【i o l 【l l 】【1 2 1 。图2 3 为p e g a s i s 采用 贪婪算法成链的过程，其中n 7 为l e a d e r 。 图2 3p e g a s i s 采用贪婪算法成链的过程 p e g a s i s 的数据传输使用令牌机制t o k e n ，首先将令牌传递给链两端的端节 点，端节点将数据和令牌发送给链中的邻节点，邻节点将自己的数据与收到的数 据进行数据融合处理后，再发送给下一个节点，当数据收集完毕，t o k e n 回到l e a d e r 时，由l e a d e r 最后将数据传向s i n k ，令牌数据传输方式如图2 4 所示。当所有节 点都与s i n k 通信后，节点再进行新一回合的轮流通信。由于这种轮流通信机制使 得能量消耗能够统一的分布到每个节点上，因此降低了整个网络数据传输所需要 消耗的能量。 1 4 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 c o c lc 2c 3“ 图2 4 令牌数据传输方式 p e g a s i s 算法减少了簇建立过程所产生的开销，并且通过数据融合和数据压 缩减少了收发次数，降低了能量的消耗。但是p e g a s i s 采用令牌方式进行数据 传输，距离s i n k 远的节点会引起过多的数据延迟，而且链首节点的唯一性可能使 链首成为网络的瓶颈；另外，p e g a s i s 虽然避免了重构簇的开销，但是由于传感 器节点需要知道邻居的能量状态以便传送数据，算法仍需要动态调整拓扑结构， 带来巨大的开销。 2 1 4t e e n 分簇路由算法 t e e n t l j j ( t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o rn e t w o r kp r o t o c 0 1 ) 分簇路 由算法的提出是为了满足实时任务的需要，它能够对突发事件做出快速的反应。 t e e n 是一种主动型传感器网络协议，它采用与l e a c h 相同的多簇结构和运行 方式，簇首根据与s i n k 距离的不同形成层次结构。不同的是，在簇的建立过程中， 随着簇首节点的选定，簇首节点除了通过t d m a 方式实现数据的调度，还要向簇 内成员广播有关数据的硬阀值和软阀值两个参数。 硬阀值：指被监测数据不能逾越的阀值。 软阀值：指被监测数据的变动范围。 硬阀值和软阀值在每次簇首轮换时被广播出去，节点监测到的数据第一次超 过硬阀值时，将这次数据设为新的硬阀值，并在下一个时隙发给簇首。在以后的 过程中，只有当监测到的数据超过硬阀值并且监测数据的变化幅度大于软阀值时， 节点才会传送最新的监测数据。图2 5 为t e e n 算法中聚簇形成的层次结构。 t e e n 协议适用于需要实时感知的应用环境中，通过设置两个阀值，能够大 大减少数据传输的次数，从而一定程度上降低了能量的损耗；用户还可以根据需 要重新设定硬阀值和软阀值的值，从而控制数据传输的次数。 t e e n 算法存在的问题是：节点采集到的有效数据会实时传送给s i n k ，采用 t d m a 机制会造成数据的延迟；另外，如果节点监测的数据一直没有超过设定的 硬阀值，节点就不会传送数据，用户将无法得到任何数据，并且不知道该节点是 否失效。 8 第二章无线传感器网络分簇路由算法概述及移动代理技术 1 5 s i | l i c oh i g hl e v e lc l u s t e rh e a d l o wl e v e lc l u s t e rh e a d o n o r m a ls e n s o rn o d e i) c l u s t e r 图2 5t e e n 协议中由聚簇构成的层次结构 2 1 5h e e d 分簇路由算法 h e e d t l 4 1 ( 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 ) 是针对l e a c h 协议 簇首分布不合理的问题而提出的，它基于节点的剩余能量和簇间通信代价进行周 期性的簇首选择。首先选取剩余能量最多的节点，作为临时簇首的集合；然后根 据簇间通信代价确定出位于多个簇范围内的节点属于哪个簇，以平衡簇首的负载。 它以簇内平均可达能量a m p r ( a v e r a g em i n i m u mr e a c h a b l ep o w e r ) 作为衡量簇 内通信成本的标准。y o u n i s ( 2 0 0 4 ) 给出了a m r p 的计算方式： ：e 答lm i n p w r a m r p 但2 ) ： 佗2 1 朋 m 为簇内节点个数，m i n p w r t 表示节点同簇首节点u 通信所需的最小功率， 1 f m 。 节点初始化概率根据下列公式确定： c h m b - - m a x ( c m 口b + e m 渤m e 眦x ，只j q - 3 q 柚，厶加是整个网络的统一参量，对算法的收敛速度有一定的影响。 昂毗锄，e 瓣表示节点的剩余能量与节点初始化能量的百分比。 簇首确定之后，其他节点根据竞争阶段收集到的信息选择加入的簇。 h e e d 分簇算法在成簇速度上有一定的改进，簇首分布更加均匀，成簇后的 网络拓扑更趋于合理。另外h e e d 算法在簇首选择时考虑了节点的剩余能量，并 以主从关系引入了多个约束条件作用于簇首选择的过程，使网络能量消耗更加均 匀。 1 6 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 2 1 6g a f 分簇路由算法 g a f t l 5 】【1 6 1 ( g e o g r a p h i c a d a p t i v ef i d e l i t y ) 是以地理位置为依据的分簇路由算 法，它是a dh o e 网络中提出的一种分簇算法，将其引入无线传感器网络，是因为 它的虚拟单元格思想为分簇机制提供了新的思路。该算法中监测区域被划分为若 干个固定单元格，形成一个虚拟的网络。节点通过g p s 定位获取自己在网络中所 处的“位置 ，从而被划入相应的单元格，如果两个节点的“位置 相同，则认为 它们在路由上是等价的；每个单元格中定期选取一个簇首，只有簇首保持活动， 其他节点进入睡眠状态。g a f 算法主要分为两个阶段： 1 、划分单元格。 将网络划分为若干个相邻的虚拟单元格，每两个相邻的单元格中的任意两点 间的最大距离r ( 尺为无线信号通信半径) 和单元格边长，满足下式中的条件 7 1 ： d ，2 + ( 2 ，2 ) r 2 ，鲁 ( 2 4 ) ， 式( 2 4 ) 保证了两个相邻单元格之间的所有节点间的距离小于他们的无线通信 距离，簇首节点替代同一个单元格内所有其他节点进行通信时，仍能保证网络的 连通性。 2 、簇首选择。 每个节点有三种状态：睡眠、发现、活动状态。其节点状态转换如图2 6 所 示。网络初始化时，所有节点均设为发现状态。每个节点根据自身相对位置信息 和无线通信半径，采用式( 2 - 4 ) 确定其所在的单元格的大小以及单元格号。 图2 6g a f 算法中的节点状态转换图 每个节点都与邻居节点交换广播信息。信息结构如图2 7 所示。广播消息中 包括本地节点号、单元格号和状态信息。节点不负责转发该广播消息。一段时间 后每个节点都能得知同一单元格内其他节点的信息。 第二章无线传感器网络分簇路由算法概述及移动代理技术 1 7 图2 7 划分单元格时的消息结构 每个节点产生一个随机数乃( 0 1 s 间均匀分布) ，r a 时间后再次发送该广播 消息。若节点在乃时间结束之前已经收到同一单元格内其他节点的广播消息，说 明已经有其他节点被选为簇首，则放弃广播消息，并转移至睡眠状态；若发送广 播消息后没有收到其他节点的广播包，说明本节点的随机数乃小于该单元格中所 有节点的随机数，本节点成功选为簇首，并转为活动状态。簇首节点设置定时器 死，死代表它处于活动状态的时间。在死超时之前，簇首定期发送广播包声明自 己的状态，以抑制其他节点进入活动状态；死超时之后，簇首节点重新回到发现 状态，同时进行新一轮的簇首选举。处于睡眠状态的节点设置定时器瓦，瓦超时 后，重新回到发现状态1 6 i 。 2 1 7t o p d i s c 分簇算法 t o p d i s c 】算法是由d e b 等人提出的一种基于图论中最小支配集的经典算法， 利用颜色来描述节点状态，解决骨干网拓扑结构的形成问题。它由网络中一个节 点启动并发送查询消息，查询消息携带状态信息，随着消息的传播，t o p d i s c 算 法依次为每个节点标记颜色，最后按颜色区分出簇首节点黑色节点，并反向 寻找查询消息，在簇首节点之间建立通信链路，簇首节点负责管理自己簇内的成 员节点。 t o p d i s c 算法为了确定网络中的骨干节点，采用贪婪算法，提出了两种节点 标记方法，分别为三色算法和四色算法。三色算法中，节点有三种状态，分别用 黑色、白色和灰色三种颜色表示。黑色表示簇首，灰色表示成员节点，白色表示 未被发现的节点。四色算法相对于三色算法的区别是：节点多了一种深灰色状态 的节点，从而使得两种算法在成簇后的结构有所不同。四色算法能形成更少的簇， 且簇之间的交叠更少；但四色算法可能会形成一些孤独的黑色节点，它不覆盖灰 色节点。两种算法的核心思想都是利用颜色标记理论找到簇首节点；利用与传输 距离成反比的延时，使得一个黑色节点( 簇首) 覆盖更大的范围。 三色算法的具体过程【l7 】如下： l 、将初始节点标记为黑色，并广播查询消息。 2 、白色节点收到黑色节点的查询消息时变为灰色，灰色节点等待时间f 后再 广播查询消息，f 和它与黑色节点之间的距离成反比。 3 、当白色节点收到一个灰色节点的查询消息时，先等待时间r ，r 与白色节 点到该灰色节点的距离成反比。若在等待时间内，收到来自黑色节点的查询消息， 1 8 基于移动代理的无线传感器网络拓扑发现及优化分簇算法 节点立即变成灰色，否则节点变为黑色。 4 、当节点变为黑色或者灰色后，它将忽略其他节点的查询消息。 5 、通过反向查找查询消息的传播路径形成骨干网，黑色节点成为簇首，灰色 节点为簇内成员节点。图2 8 为三色法形成的簇的结构。 图2 s 三色法形成的簇结构 在图2 8 所示的例子中，初始节点a 将自己标记为黑色，并发起查询请求； 节点b 、e 收到a 发来的查询消息，将自己标记为灰色，并等待一段时间后再次 广播这个查询消息；节点c 、d 收到来自灰色节点b 的查询消息后，等待一段时 间，由于节点c 比节点d 距离节点b 更远，所以节点c 先超时，并将自己标记 为黑色，继续发送查询请求；这时节点d 收到来自节点c 的消息，停止等待，变 为灰色。算法如此进行下去。算法运行到网络边缘后，将按照查询消息发送的路 径进行回溯，构建网络的转发链路。 t o p d i s c 算法利用图论中的经典算法，提出了一种有效的构建网络近似拓扑 的方法，是分簇算法中的经典算法。它只需要利用网络的局部信息，是完全分布 式可扩展的拓扑控制方法，但同时也存在需要一些问题，如算法开销偏大；没有 考虑节点剩余电量，网络中部分节点因能量消耗过快而功能失