（计算机应用技术专业论文）无线传感器网络分簇算法研究.pdf

硕士擘住论文 m a s t e r st h e s i s 摘要 在无线传感器网络( w s nw i r e l e s ss e n s o rn e t w o r k s ) 体系结构中，网络层的路由技 术至关重要。分簇路由具有拓扑管理方便、能量利用高效、数据融合简单等优点， 成为当前重点研究的w s n 路由技术。本文分析了w s n 分簇路由机制，着重从簇头 的产生、簇的形成和簇的路由角度系统地描述了当前典型的分簇路由算法，并比较和 分析了这些算法的特点和适用情况。最后结合该领域当前研究现状，指出分簇路由算 法未来的研究重点 本文的主要工作包括以下几个方面： 1 文中首先介绍了当前w s n 分簇算法方面的研究情况。如l e a c h 分簇算法， 该算法通过概率选择节点作为簇头，引入能量约束的h e e d 分簇算法等。 2 本文将能量与选举思想相结合，提出一种能量均衡的分簇算法。同时着重思 考了传统网络的拓扑定义的一些问题，比如传统的拓扑的定义只是节点位置之间相 关联而形成的连通图，而本文希望从能量的角度，建立能量拓扑结构。由此来形成 在拓扑上能量均衡的分簇算法，然后通过优化理论求簇首优化解。 3 针对高密度w s n ，本文提出了相关度分簇算法，把具有高相关度的节点融合 为个虚拟的簇首，组成簇首的节点以t d m a 轮询的方式工作，由此减少节点竞 争减少簇首的消耗，延长簇的寿命，保证网络的稳定性。 经过仿真实验，本文提出的能量均衡的分簇算法和基于相关度分簇算法在特定 的网络情况下，网络的整体性能都有所改善：网络的负载均衡、节点的能量消耗很 平稳、分簇稳定、网络寿命明显延长。特别针对高密度的w s n 提出的相关度分簇 算法，在节点增多的情况下，算法的性能非常优越。 关键词：无线传感器网络；簇；簇首；分簇算法；能量均衡；网络寿命：聚类； 适合因子；相关度；虚拟节点 硕士学位论文 m a s t e r st h e s i s a b s t r a c t r o u t i n gt e c h n o l o g ya tt h en e t w o r kl a y e ri sp i v o t a li nt h ea r c h i t e c t m eo fw i r e l e s s s e n s o rn e t w o r k s a sa na c t i v eb r a n c ho fr o u t i n gt e c h n o l o g y , c l u s t e r - b a s e dr o u t i n g p r o t o c o l s e x c e l e si nn e t w o r kt o p o l o g y m a n a g e m e n t , e n e r g ym i n i m i z a t i o n ，d a t a a g g r e g a t i o na n ds oo n , i th a sb e c o m e0 1 1 eo ft h em o s th o t s p o t so fr e s e a r c h e so n w s n ( w i r e l e s ss 6 t i s o rn e t w o r k s ) i nt h i sp a p e r , c l u s t e r - b a s e dr o u t i n gm e c h a n i s m sf o r w s na a n a l y z e d c l u s t e rh e a ds e l e c t i o n , c l u s t e rf o r m a t i o na n dd a t an a n s m i s s i o na r e t h r e ek e yt e c h n i q u e si nc l u s t e r - b a s e dr o u t i n gp r o t o c o l s r e s e a r c h e si nt h i st h e s i si n c l u d e ： 1 o n eo ft h es i g n i f i c a n tc h a l l e n g e si sh o wt os u b d i v i d et h es e n s o rn e t w o r ki n t o r e a s o n a b l ea n ds t a b l en e t w o r ks t r u c t u r e ? t oa d d r e s st h ea b o v ep r o b l e m ，i nt h i st h e s i s ，a l i t e r a t u r er e v i e wo nt h ew i r e l e s ss e n s o rn e t w o r kc l u s t e r i n ga l g o r i t h m si sp r o v i d e d m a n y c l u s t e r i n ga l g o r i t h m st h a th a v eb e e np r e s c n t 钱ls u c ha sie a c hw h i c hd e c i d e st h e c l u s t e r sa c c o r d i n gt ot h ep r o b a b i l i t yt h e o r y 丑e e dw h i c hi n t r o d u c e st h ee n e r g y r e s t r i c t i o ns h o w sm o r ee 丘i c i e n c yt h a nl e a c h 2 i nt h i sp a p e r , w op r o p o s ea no p t i m i z a t i o na l g o f i t l m at oa v o i dt h es h o r t c o m i n go f t h e a b o v e - m e n t i o n a dc l u s t e r i n ga l g o r i t h m sb yc l u s t e r i n gu s i n gt h ee n e r g yi n f o r m a t i o n n e f l e wa l g o r i t h md e f i n e st h et o p o l o g y a c c o r d i n g t ot h ee n e r g yd i s r i b u t i o nw h i c hd i f f e r e n tt o t h ec l a s s i ca l g o r i t h m s a n dt h en o r m a ln o d e sc h o o s et h eo p t i m i z a dt h ec l u s t e rh e a d s a c c o r d i n gt o t h eo p t i m i z i n ge x p r e s s i o n sw h i c hs h o w st h ea d v a n t a g e st h a no t h e r a l g o r i t h m s 3 ac o r r e l a t i o n - b a s e dc l u s t e r i n ga l g o r i t h mi sp r o p o s e df o rt h eh i g h - d e n s i t yw s n , w h i c hm a k e st h en o d e sh a v i n gt h eh i g h e s tc o r r e l a t i o na so n ev i r t u a lc l u s t e rh e a d t h e m e m b e r so ft h ec l u s t e rh e a dw o r ki n 皿阱江as e q u e n c e s i tr e d u c e st h ec l u s t e rh e a d c o m p e t i t o na n ds t a b l et h es t r u c t u r eo f t h en e t w o r ka sl o n ga sp o s s i b l e a st h es 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 p o s e d a l g o r i t h m s h a v eb c t t f f f p e r f o r m a n c e st h a nt h el e a c ha n dh e e di nc e r t a i na c e n e s ：e n e r g yb a l a n c e ，e n e r g y c o u s u p t i o n , c l u s t e rs t a b i l i l y , t h ep r o l o n g e dl i f e t i m e e s p e c i a l l yt h ec o r r e l a t i o n - b a s e d c l u s t e r i n ga l g o r i t h mf o r t h eh i g hd e n s i t ys e n s o rn e t w o r k s ，i th a sd r a s t i c a la d v a n t a g e st h a n i 甩a c hw h e nt h en u m b e ro f n o d e si n c r e a s e s k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ；c l u s t e r ；c l u s t e rh e s d ；c l u s t e r i n ga l g o r i t h m ； e n e r g yb a l a n c e ；n e t w o r kl i f e t i m e ；a g g r e g a t i o n ；f i t n e s si n d e x ； c o r r e l a t i o n , v i r t u a ln o d e n 硕士学位论文 m a s t e rst h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 办l j | 1日期：，叼年j 月，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名t孙飞 日期：p 刁年月f f 日 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。园壶迨塞握童后进厦i 旦圭生；旦二生；旦三生筮查! 作者豁如n 日期：b 母年6 月f 日 乏重月浚 娩岬 师期 孚日 9 纱 昂哆日 格朋 ， 戳年 ：| | ：珂 醐 硕士擘位论文 m a s t e r s 了h e s i s 1 1 课题研究的目的和意义 第1 章绪论 无线传感器网络是一种全新的信息获取和处理技术，它综合了传感器技术、 微机电系统、分布式信息处理技术和无线通信技术，能够协作地实时监测、感知和 采集各种环境或监测对象的信息并对其进行处理，并将信息传送到用户。 虽然w s n 的大规模商业应用，由于技术等方面的制约还有待时日，但是最近 几年，随着计算成本的下降以及微处理器体积越来越小，w s n 已经开始投入使用。 目前w s n 的应用主要集中在环境的监测和保护、医疗护理、交通、军事等领域， 两且w s n 在一些危险的工业环境如井矿、核电厂等，也具有很高的应用价值。自 主地采集周围环境的数据并将其向外传输，是w s n 应用与设计的核心问题。其广 阔的应用前景，使得对w s n 的研究与开发成为目前信息领域的一个热点，学术界 和产业界对它投入了极大的研究热情国际上许多著名的大学和公司纷纷从不同的 层次、不同的角度对传感器网络进行了研究和开发。 近年来，我国的一些著名高校也展开了这一领域的研究工作，如国防科技大 学的相关科研人员已在该领域进行了前沿性的探索研究。内容包括无线传感器节点 的硬件设计、操作系统设计以及w s n 的路由技术、节能技术、覆盖控制技术等。 在众多研究领域中，如何能使传感器网络节点获取的数据，高效的完成应用 各项预定的任务，是一个异常活跃的研究领域。在完成任务的情况下，优化网络性 能，特别是网络的寿命、负载平衡、网络拓扑的稳定性等都是目前研究的热点 1 2 课题研究的发展 本课题的研究方向是w s n 的路由协议，因为8 5 以上的能量消耗都是消耗 在数据的发送和接收，因此路由协议极大的影响了整个网络的性能。 ( 1 ) 基于数据的路由协议 这类协议是基于查询和对目标数据的命名之上的，通过数据聚合减少重复的 数据传送。s p i n ( s e ! a s o rp r o t o c o lf o r i n f o r m a t i o nv i an e g o t i a t i o n ) 【8 9 】是以数据为中 心的自适应路由协议，通过协商机制来解决泛洪算法中的“内爆”和“重叠”问题。节 点仅广播数据的描述信息，当有相应的请求时，才向目的地发送数据。 d e s t r i n 等人设计了定向扩散【1 0 】。节点用一组属性值来命名它所生成的数据， s i n k 节点发出查询，并将之逐级扩散至全网，有匹配数据的节点通过与相邻节点建 立一个梯度场，接着，s i n k 节点通过再次发送兴趣消息来加强那条梯度最大的路径， 然后数据就可以沿着这条路径传送了。 ( 2 ) 基于层次的路由协议 分层次路由协议是让节点与特定的簇首节点进行通信，簇首再进行数据聚合， 减少向s i n k 节点传送的消息数量，从而达到节省能量和提高可扩展性的目的。典型 的簇形成是基于节点的能量储备及节点同簇首的接近程度。l e a c h 2 是传感器网 络中最早的分层次路由协议之一，它的主要思想是基于接收信号的强度来形成集 群，使用本地簇首作为到s i n k 节点的路由器。通过随机选择簇首，平均分担中继 通信业务来实现节点能耗的平衡。l e a c h 中的思想激发了许多分层次路由协议， 还有很多分层次协议是独立开发的。层次路由协议将在第二章作详细介绍。 ( 3 ) 基于位置的路由协议 基于位置的路由协议利用位置信息传送数据到指定区域。这方面的协议主要 是来源于移动a d h o c 网络，设计时考虑了节点的移动性g a f ( g e o g r a p h i c a l a d a p t i v ef i d e l i t ya l g o r i t h m ) f 1 1 是这方面的协议的典型代表，它是能量感知且基于 位置的路由协议，主要为移动a d - h o c 网络设计。g a f 通过关闭网络中不必要的 节点来节省能量。它先在所覆盖的区域形成一个虚拟的两格，每个节点使用g p $ 定位将自己与虚拟网格中的一点相关联，且认为关联到网格中同一点的节点有等价 的路由代价。这样可以利用等价性来使特定网格区域内的一些节点进入睡眠状态， 从而节省能量。因此，当网络中的节点数目增加时，g a f 可以显著的提高网络寿命。 在g a f 中，节点轮流从睡眠状态变到工作状态，达到网络负载均衡g a f 是基于 位置的路由协议，但也可以认为是一种分层次的路由协议，只不过它的集群是基于 节点的地理位置。 ( 4 ) 基于网络流的路由协议 基于网络流的路由协议的目标是在实现路由功能的同时满足一些网络q o s ( q u a l i t yo fs e r v i c e ) 要求。这类路由协议主要有s a r ( s e q u e n t i a la s s i g n m e n t r o u t i n g ) 1 2 等。s a r 是最早将q o s 概念引入传感器网络中的一种路由算法，它是 一种表驱动、多路径的方法，目标是达到高能效和容错功能，在确定路由树时，同 时考虑q o s 质量、路径上的能量资源和每个数据包的优先级。 1 3 课题研究的难点与突出问题 分簇算法是一种层次的路由协议，但是与普通的层次路由不同，它考虑更多的 是节点聚类和数据融合。而w s n 与a dh o e 网络和传统有线网络不同，传统的路由 2 技术很难在w s n 中使用。目前分簇算法的研究主要包括以下几个方面： 1 分簇的理论基础：研究的热点就是簇首的选择问题，目前提出的分簇算法 基本可以分为三类。其中之一是以l e a c h 为代表的基于概率的分簇算法，这类算 法不考虑节点的能量和网络整体的特征，很难确定算法的稳定性。在随机的网络中， 算法的效率不高。另外一种是考虑节点功能函数的分簇算法，例如h e e d ，它考虑 节点充当簇首的最小能量约束，因此算法的执行效率比l e a c h 明显增强。第三种 是以节点特征为约束的分簇算法，这类算法包括节点度、权值、能效函数、地理位 置等为基础的分簇算法。 2 簇内节点工作方式：这类研究的主要内容是在分簇的簇内和簇外实现节点 的公平性和效率的协同工作等问题。 3 路由问题；主要研究簇首节点如何把数据通过多跳传输到远端的s i n k 节点， 这类问题研究类似与a d h o e 网络中的路由问题，而分簇本身也是路由问题。 4 缺乏评价标准：因为w s n 是一个全新的研究，研究的领域相当多，因此， 很难为所作的研究确定统一的评价标准。目前讨论较多的标准问题包括，算法的稳 定性、能量优化、负载平衡、公平性、效率、网络寿命等。 因为w s n 的约束条件特别多，而网络中的节点一旦撒播，就很难人为的干预， 当节点能量下降时，网络的整体性能就急剧下降。如何有效的提高节点的工作效率， 提高整个网络的性能，特别是能量均衡和网络寿命是本文的研究重点。 1 4 本文工作以及内容安排 本课题主要工作是针对w s n 的特点，设计w s n 的分簇算法。主要目标是在 目前已经存在的多种算法的基础上，综合考虑节点的多项特征，特别是节点能量特 征，通过优化解，优化网络分簇结构，延长网络寿命。同时针对高密度传感器网络 提出相关度的分簇算法，延长分簇周期，设计合理的网络优化策略。 本文的内容安排如下： 第一章：介绍文章的研究目的、研究热点、研究难点和文章的目录结构。 第二章：首先介绍了w s n 的网络模型，然后总结目前研究成果，对无线传感网 络路由研究进行分类，讨论各种路由机制主要思想，以及可能的改进。对无线传感 器的研究热点，研究方向等进行归纳。同时介绍了分簇算法的概念，和一些典型的 分簇算法。 第三章：针对l e a c h 算法和h e e d 算法提出的能量均衡的分簇算法，节点通 过比较适合因子来决定自己是否成为簇首，而普通节点加入簇时，引入优化思想， 使网络的能量达到均衡。之后对提出的分簇算法进行理论和仿真实验。实验证明新 提出的分簇算法在一定的条件下对网络的性能有较大改善。 第四章：针对高密度w s n 节点密度高的特点，提出基于相关度的分簇算发，减 少节点对簇头的竞争，把具有高相关度的多个节点融合成为一个虚拟的簇首，使簇 的寿命延长，同时网络的稳定性也得至提高。簇的更新周期可以延长，网络的寿命 也有较大的改善。 第五章：对本文所做的研究创新与贡献进行总结，并指出了将来应该进一步深 入的问题。 4 硕士学位论文 m a s t e r st h e s i s 第2 章w s n 路由协议与分簇算法 无线传感器网络节点具有多方面限制，重要的包括节点的能量特征、散播方式、 通信方式、网络内部以及网络与外部的通信方式等。传感器网络的主要能量效耗在 稳定状态下的数据传输，因此，好的路由协议在确保网络寿命最大化方面特别重要。 由于无线传感器网络不同与其他无线网络，在路由算法设计问题上面临许多挑 战。第一，传感器节点数量多，维护节点d 的开销高，对大规模节点统一的寻址 不可能。第二，传感器网络几乎所有的应用要求从多个源节点采集数据流向某个 s i n k 节点，源与耳标节点见呈现多对一的数据流向关系。第三，传感器节点受其自 身能量、计算能力、存储容量和带宽资源等因素约束，因此，必须采用有效的资源 管理方式才能延长节点和网络的生命。第四，在多数的传感器网络中，几乎所有的 节点在部署之后都是静态的，可能除了少量的需要移动，拓扑结构上与传统的无线 网络不同。第五，由于传感器网络数据聚集操作通常是基于位置信息的，可能会使 用到g p s 技术等，然而所有节点都配备g p s 不可行，则需要使用三角定位技术， 根据节点之间的角度、信号强度和g p s 点之间的位置信息确定。最后，多个节点 可能采集到相同信息，为避免重复传输造成的带宽消耗，节点的路由算法应该能识 别冗余信息，改善带宽利用率。 由于这些差异的存在，该领域出现了许多用于解决传感器网络路由问题的新算 法。传感器网络中使用的路由算法通常都部分引用a d h o c 网络中路由的部分思想 通常使用的传感器网络专用的处理技术，包括：数据聚集、聚类、节点角色分类( 分 簇) 、以数据为中心的转发技术等。 2 1w s n 路由协议算法 图2 - l 平面网络结构图2 - 2 层次网络结构图 传感器网络有多种分类方法，按照网络结构，路由协议算法分成平面路由( 图 2 1 所示) ，层次路由( 图2 - 2 所示) 和基于位置信息的路由三大类别【2 5 】；按照协议操 作规则，可将无线传感器网络分成协商路由，多路经路由，q o s 路由，查询路由和 5 硕士擘位论文 m a s t e r st h e s i s 相关路由五大类所示。本文只介绍按照网络结构分类的路由协议，( 如表1 ) 。 表1 传感器网络有路由协议分类 平面路由 定向扩散，s p 矾，g a f 按照网络结构 层次路由i 正a c h ，p e g a s i s ，t e e n ， 路由分类 1 3 a f ，h e e d 基于位置信息路由 g 叁忑 ( 1 ) 平面路由协议 在平面无线传感器网络中，每个节点扮演相同的角色，多个传感器节点协同执 行数据采集任务。这种情况产生以数据为中心的路由方法，即s i n k 节点对某一特定 区域发送查询指令，等待该区域内的传感器节点返回采集的数据。通过多个节点协 同操作和消除冗余数据可以节约能量，比如s p i n 3 0 和定向扩散 3 l l 。 1 2 ) 层次路由协议 层次化或聚类路由策略，最早在有线网络中提出，是一种伸缩性好和通信效率 高的路由技术。因此，层次化路由概念也适用于传感器网络实现高能效的路由技术。 在层次化结构中，高能量传感器节点用于处理和发送信息，而低能量节点用于执行 对监控对象周围的数据采集工作。这意味着创建簇和为簇头节点分配特定任务可为 系统伸缩性、寿命和能效贡献极大好处。层次化路由通过执行数据聚集和融合减少 传输到s i n k 节点的数据量，降低类内各节点能耗，是一种有效改善能量效率的解 决方法。层次化路由主要由两个层次构成：一个层次用于创建簇，选择簇头节点， 另一个层次用于聚集和处理数据，路由数据。然而，这类路由方法多数不关心路由， 而是关心与多跳路由功能无关的一些问题，比如：哪个节点负责处理和聚集数据， 什么时候发送聚集后的数据，以及通信信道分配等内容。 分簇路由其实就是层次路由的分簇思想，是在网络中选择几个节点作为簇首， 其余的传感器节点作为簇首的成员，每个成员采集到数据后不是直接发送到基站， 而是发送到簇首，簇首把收集到的簇成员的数据经过压缩后发送到基站。 平面和层次路由协议的各种算法，在许多方面都有不同的特征( 如表2 所示) 。 6 硕士学位论文 m a s t e r st h e s i s 表2 平面路由和层次化路由协议的比较 层次路由协议 平面路由协议 预约式调度 竞争性调度 避免冲突存在冲突开销 由簇头节点实现数据聚集多跳路径上节点采集的数据和来自邻居节点的数据实现 逐跳聚集 简单但非优化的路由路径路径可以优化但增加复杂度，增加开销 整个网络创建多个簇，需要开销只在数据将路过的区域形成路由路径 簇头可用时相比多跳网络时延较时延开销在唤醒中间节点和建立多路径上 小 能耗均匀能耗依赖于流量模型 能耗不可控能耗适应流量模型 信道分配公平信道分配公平性不能保证 ( 3 ) 基于位置信息的路由协议 这类路由协议，传感器节点依靠位置信息进行寻址。邻居节点间的距离和相对 坐标可根据信号强度进行估算。换句话说，如果节点装配了小型低功率g p s 接收 器，节点利用g p s 通过直接与卫星通信可得到节点位置信息，其他节点可以通过三 角法则计算位置。典型的基于位置信息的路由算法有g a f 算法。 2 2w s n 路由协议算法设计目标 路由算法在各种网络路由协议中起着至关重要的作用，它直接影响网络性能， 传感器网络也不例外。通常需综合考虑以下一些设计目标： ( 1 ) 简洁性：指路由算法设计简洁，尽可能减少软件开销，提供有效路由功能。 ( 2 ) 可靠性：指路由算法处于各种非正常或不正常的网络环境时，如节点硬件 故障、节点死亡、网络负载过高或是用户操作失误时，都能确保正确运行。 ( 3 ) 伸缩性：指路由算法适应网络规模变化的能力。一旦网络规模变大，伸缩 性强的路由算法能及时适应网络环境的需要，仍然发挥良好的路由功能。 ( 4 ) 快速收敛：收敛是指最佳路径的判断上路由器节点信息更新到达一致的过 程。当某个网络事件发生引起拓扑变化使原有的路由变得不可使用时，路由器就发 出更新信息。路由更新信息使所有路由节点从新计算最合适的路径过程，最终找到 一致最合适的路径。收敛慢的路由算法可能会造成路径循环或是网络中断。 ( 5 ) 自适应性：指路由算法可以快速、准确地适应各种网络环境。 ( 6 ) 服务质量( q o s ) ：网络性能的一个指标是服务质量，它包括数据传输时延、 7 硕士攀住论文 m a s t e r s t h e s i s 响应时间、公平性、高效率性等，所以服务质量也是衡量路由算法的一个重要标准。 ( 7 ) 优化能力：指路由算法依据当前网络资源状态选择最合适的路径的能力。 传感器网络路由算法的设计除了以上需要关注的设计目标以外，如何有效的使 用节点的能量，提高节点的能量使用效率、减少数据包发送的能量消耗、选择最优 化的路由、延长整个传感器网络的寿命是无线传感器网络研究的热点。 2 3w s n 路由协议算法面临的挑战 传感器网络的约束包括节点能量供应有限、计算能力弱、无线带宽窄、通信距 离短和通信干扰等。而设计传感器网络主要目标之一是执行数据采集、传输，同时 通过运用高效的能量管理策略延长网络寿命和防止网络互连性能下降。由此看来， 路由算法性能对实现传感器网络设计目标起着关键作用。下面简要介绍传感器网络 路由算法设计中要考虑的各种影响因素以及可能面临的挑战 2 5 ，2 6 ，2 7 ( 1 ) 数据流传输模型：传输模型可以划分成连续流、时间驱动、查询驱动和混 合四种模型 2 8 ，2 9 1 。连续流数据传输模型适合周期性数据检测。在这样的应用中， 传感器节点周期性打开数据采集电路和无线收发器，采集传输数据到s i n k 节点；在 时间驱动和查询驱动数据模型中，对s i n k 节点发出的查询请求或是特定时问出现引 起节点设定的属性值的变化，该节点立刻作出反应，并将采集的数据发送到s i n k 节点。这两种模型适合对时间要求紧迫的系统。前三者数据传输模型的组合方式构 成混合数据传输模型。数据流传输模型对路由设计及性能有着重要影响。 ( 2 ) 节点部署方式：传感器节点部署方式依赖与具体应用，可以是位置确定的 或是随机撤播的。采用前者，传感器节点手工放置，数据以预定路径路由。若使用 后者，传感器节点随机撒播以自主方式构建通信网络。如果节点分布不均匀，为确 保网络互连和高效的网络操作，可以使用优化聚类，节点采用短距离多条路由通信。 可见，节点部署方式对路由协议多项性能产生影响。 ( 3 ) 容错性：由于能量消耗、损坏、环境干扰等导致一些节点可能失效或通信 被中断。如果多个节点失去作用，路由协议必须及时调整形成新的链路、新的路径， 便于数据快速路由到s i n k 节点。所以，在容错性强的传感器网络中，要求保存必较 多冗余信息来保障路由稳定性。 ( 4 ) 拓扑动态性：多数情况下，传感器网络应用假设节点都是静态的。然而， s i n k 节点或某些传感器在一些具体应用中保持节点移动性是必要的。首先，路由稳 定性成为设计时一个重要问题；其次，拓扑变化带来的能量消耗和带宽利用率等也 硕士学位论文 m a s t e r st 1 t e s i $ 值得考虑；第三，观测对象本身可以是移动或静止的，依赖于具体的应用。 ( 5 ) 能量问题：在传感器网络中，每个节点都可能扮演双重角色：数据采集器 和路由器。为节约能量，各个节点采用有关通信和计算的能量保护技术。此外，由 于一些节点电源耗尽或故障引起节点功能失效，会产生明显的拓扑变化，从而可能 要求重新路由数据包，或重组网络，这会增加额外的能耗。所以，能耗问题是路由 算法设计时的首要问题之一，也是讨论算法优劣的重要因素。 ( 6 ) 节点异构性：在多数研究中都假设传感器网络中所有节点都是同构的，具 有同等的计算通信能力，同样的数据采集功能，相同存储容量和传输功率。异构节 点的存在带来很多技术问题，包括数据路由等。 ( 7 ) 传输媒介：在传感器网络中，节点间通信通过无线传输媒介进行，无线信 道相关的传统问题，比如：信号衰弱，高出错率，可能影响路由算法所采用的路由 策略及性能。传感数据所需要的带宽较低，大约1 - 1 0 0 k b s 。t d m a 协议是一种适 用于传感器网络的m a c 协议，相对基于冲突的c s m a 协议来说，该协议可以节约 更多能量。路由算法设计时也应考虑m a c 协议设计上的策略问题。 ( 8 ) 网络连通性：节点密度高使传感器网络能保持较高的互连性。然而，这仍 然无法保障网络高连通性，因为节点死亡或失效将引起节点能量缩减，从而导致网 络规模变化。此外，连通性还依赖于节点的随机分布方式。所以路由算法需要适应 网络连通性的变化。 ( 9 ) 伸缩性：传感器网络应用中，要求任何路由策略必须有能力适应网络规模 大小的变化。 ( 1 0 ) 覆盖率：所谓覆盖率，指单位面积一个或是多个传感器节点“视野”所覆 盖的区域情况，该参数与网络连通性，与节点部署方式也有关系。在传感器网络中， 每个节点只负责监控器周围的特定区域。所以，区域覆盖率也是路由设计时应考虑 的一个重要参数。 ( 1 1 ) 数据聚集：多个节点可能采集到相同的数据，如果同一数据的多个拷贝” 被通过不同的路由传输到s i n k 节点，就会消耗网络中巨大的带宽和能量。因此把相 似的数据或是相邻节点的数据聚合，然后传输到远端的s i n k 节点可以减少带宽消 耗，优化网络资源。 ( 1 2 ) 服务质量( q o s ) - 在一些传感器网络应用中，对数据的时效性有要求。 所以，在数据传输时，时间的有效性必须考虑；而网络设计的另外一个要求就是网 络要有尽量长的寿命，有时候把网络的寿命看作是比服务质量更高的性能要求。所 以，有时候在网络的能量降低较大的时候，为了延长网络的寿命，会适当的降低网 9 络的服务质量。因此，实际应用的路由协议，可能需要在能量消耗和服务质量( q o s ) 这两个性能指标之间有效的控制，达到平衡和应用的目的。 2 4w s n 分簇算法的基本概念 在w s n 中，网络分簇结构与平面结构相比具有较好的可扩展性、可伸缩性、 灵活性，可以大大提高了系统的性能。合理有效的网络分簇结构，可以建立高效的 网络控制体系。实现包括带宽分配及频率复用等在内的有效的资源调度和应用、提 供信道接入控制、高效路由计算等功能。 分簇算法根据w s n 具体的应用需求，按照某种规则将网络分成可以相互连通 并覆盖所有节点的多个簇，并在网络结构发生变化时更新簇结构以及维护网络的正 常功能。分簇算法的目的是通过初始化，获得相互连通度、覆盖所有节点的簇结构， 随网络结构变化生成新的簇结构，确保节点感知到的信息正确地传递到s i n k 节点， 并且能够使用较少的计算和通信开销来构造和维护一个能够覆盖整个网络的逻辑 拓扑结构。 网络分簇过程一般由两个阶段构成，即：簇的初始和建立与网络运行中对簇的 更新和维护。在初始化建立阶段，网络中的节点将基于一定的准则构建节点集合， 这个集合就是所说的簇，在网络环境中，随着节点的移动或损坏等问题的出现。集 合也依据准则相继进行更新，即簇的更新，簇的更新包括簇内成员节点的交化、簇 头节点的改变，以及簇的重建( 即簇的重构) 。通常，簇的重构规则是与初始建立 簇的原则和方法紧密相关的。 2 5 分簇算法基本目标及其性能评价 在使用分簇的w s n 中，建立合理和有效的网络分簇结构、维持网络拓扑的相对 稳定性、提高系统性能是分簇算法的首要目标。 在比较各种分簇算法的性能时，主要采用以下几种性能指标： ( 1 ) 网络中簇( 头) 数日c ，它直接反应分簇网络的结构和特性分簇网络的簇 数目不应过多，也不能过少，应以满足系统要求和减少控制开销为准则。 ( 2 ) 单位时间内簇头构成的节点集更新的次数，说明簇重构的频率。重新分簇 会引起较大的计算和通信开销，该指标在很大程度上决定了分簇算法的性能。 ( 3 ) 簇重叠度，簇头处理负载的能力取决于它可以支持的节点数量。除了为簇 内节点分配资源外，簇头还需要维护簇间的路由。因此希望网络的负载能够比较均 1 0 匀地分配到各个簇，从而提高网络的整体性能。但在w s n 中优化负载比较困难， 为了定量地刻划簇头的负载平衡程度，引入簇重叠度和网络负载平衡因子( l b f ) 两 个参数。簇覆盖内所有节点的数目之和和网络节点总数的比值作为网络的簇重叠度 v r c d = 名譬，显然c d 越大，则处于重叠区域的节点数量越多。 ( 4 ) 网络负载平衡因子( l i f ) ：簇头的处理负载近似由该簇的大小表示，即簇的 大小的变化可以反映簇头负载分布。l b f 定义为簇内成员数( 不包括簇头的方差的 倒数，印l b f = i 芋l 气，其中是簇的数量， 毛是簇i 的 己h 1 懈一甜j 。 成员节点数，甜= ( 一吃) 砟表示网络中每个簇头的平均邻节点数，n 为网络中所 有节点的数目。显而易见，l b f 越大，网络的负载平衡程度越好，在最理想的情况 下五一，l b f 趋向无穷大。 ( 5 ) 节点充当簇头的公平指数( 砸i ) ：该指标说明各个节点充当簇头的公平程度， h f i 定义为节点担当簇头的时间偏差，即正舀= 7 = 以l 一比) i ，f 矿其中，表示节 点i 充当簇头的时间，戤) = f 毛，表示节点担当簇头的平均时问，h f i 表示节 万 点i 充当簇头时间偏离节点担当簇头平均时间的程度。因此h f i 越小，说明节点充 当簇头的公平性越好，在最好的情况下，f = e ( o 。h f i - o 由于簇头的能量消耗较 大，h f i 越小，意味着能量消耗越能均匀的分配到各个节点上，从而可以延长网络 的寿命。 随着研究的不断深入，迄今为止，已经提出了大量的分簇算法来构建和维护分 簇网络结构。利用分簇网络结构，可以减少路由算法和洪泛广播的开销，能够提高 网络的可扩展性和q o s 保障能力。不同的分簇算法具有不同的优化目标，包括最 小化簇数目、最大化簇稳定性和最大化网络生存时间等。上述各个目标之间可能存 在矛盾，因此通常采用启发式的分簇算法来寻求次优解。以下介绍一些比较有影响 的算法并比较其优缺点。 2 6 分簇算法在传感器网络中的应用 2 6 1 基于分簇的m a c 协议 对于分簇结构的传感器网络，文献【3 5 】提出了基于t d m a 机制的m a c 协议。 所有传感器节点固定划分或自动形成多个簇，每个簇内有一个簇头节点，负责为簇 内所有节点分配时序，收集和处理簇内节点发来的数据，并将数据发送给汇聚节点。 在基于分簇网络的m a c 协议中，节点状态分为感知、转发、感知并转发和非 活动四种状态。节点在感知状态时，采集数据并向其邻节点发送：在转发状态时， 接收其他节点送的数据并发送给下一个节点；在感知并转发状态时，需要完成上述 两项的功能；节点没有数据需要接收和发送时，自动进入非活动状态。 为了适应簇内节点动态变化、及时发现新的节点、选择能量相对高的节点转发 数据等目的，协议将时间帧分为周期性的四个阶段： ( 1 ) 数据传输阶段。簇内传感器节点在各自分配的时序，发送采集数据簇头。 ( 2 ) 刷新阶段。簇内传感器节点向簇头报告其当前状态。 ( 3 ) 刷新触发的重组阶段。紧跟在刷新阶段之后，簇头节点根据簇内节点的当 前状态，重新给簇内节点分配时序。 ( 4 ) 事件触发的重组阶段。节点能量小于特定值、网络拓扑发生变化等事件发 生时，簇头要重新分配时序。通常在多个数据传输阶段后有这样的事情发生。 上述基于分簇网络的m a c 协议在刷新和重组阶段重新分配时序，适应簇内阶 段拓扑结构的变化及节点状态的变化。簇头节点要求具有比较强的处理和通信能 力，能量消耗比较大，如何合理地选取簇头节点是一个需要深入研究的关键问题。 2 6 2 基于分簇的路由协议 基于分簇的路由协议通过分簇网络结构可以减少由于节点移动对路由算法带 来的影响和路由发现过程中的洪泛开销，并且能够加速路由的查找过程。为了防止 路由算法对于拓扑变化的强烈反应，节点通常只在簇内维护完整的路由信息，而簇 间的路由借助于虚拟骨干使用分级聚集或反应式路由以及两者的组合来维护簇内 的拓扑变化，从而减少节点移动对路由协议带来的影响。另外，采用基于分簇的路 由可以减少参与路由计算的节点数目和路由表尺寸，从而降低路由信息所需要的通 信开销和维护路由表所需的内存开销，可扩展性好。当网络规模较大时，采用基于 分簇的路由算法是一种较好的选择，代价是得到的路由可能不是最佳路由，并且需 要进行簇维护，不如平面路由健壮 到目前为止，对基于分簇的路由协议已经进行了大量的研究，并取得了很多成 果。l e a c h e i 2 ( i o we n e r g y a d a p t i v e c l u s t e r i n g h i e r a r c h y ) 算法是一种自适应分簇路由 算法，它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶 段。在簇的建立阶段，随机产生簇头，相邻节点动态的形成簇；在数据通信阶段， 簇内节点把数据发送给簇头，簇头进行数据融合并把结果发送给汇聚节点。由于簇 硕士擘位论吏 m a s t e r st h e s i s 头需要完成数据融合、与汇聚节点通信等工作，所以能量消耗大。l e a c h 算法能 够保证各节点等概率地担任簇头，使得网络中节点相对均衡地消耗能量。 t e e n 3 7 ( t h r e s h o l ds s t t t v ee n e r g ye f f i c i e n ts e n s o m e t w o r kp r o t o c 0 1 ) 路由协议把传感 器网络分为节点周期性发送信息的主动网络( p m a c t i v en e t w o r k ) 和及时监测突发事 件的反应网络( r e a c t i v en e t w o r k ) 。在反应网络中，人们只对属性值高于给定阂值的 数据感兴趣。t e e n 协议是应用于反应网络的对l e a c h 协议的改进，其核心操作 过程为：在簇首选举后，簇首会把绝对闭值和相对阂值两个参数广播给其他成员。 传感器节点持续地采集数据，当采集的数据第一次大于绝对阂值，节点把数据记录 下来，同时发送给簇首；在以后时间内，只有节点采集的数据大于绝对闭值，而且 与前一次记录结果之差大于相对闭值时，才对数据进行记录并发送给簇首。t e e n 协议的改进有两个好处：第一，对于突发事件能够及时响应；第二，对于持续的突 发事件，相邻两次数据之差在不大于相对闭值时，无需不断地发送数据，减少通信 流量。 2 6 3 基于分簇的网络管理 无线自组织网络管理结构根据在网络控制管理中信息的收集和通信策略不同， 可分为集中式、分布式和分层式网络控制结构。采用集中式控制的网络中，网络的 管理依赖于少量的中心控制管理站，负责收集所有节点的信息，并控制整个网络。 集中式控制的优点是实现容易，但对于节点规模较大的网络，用来收集管理数据的 开销很大，且当控制管理站出现故障或者网络出现分裂时，网络就全部或部分失去 了控制管理能力。 采用分布式控制的网络具有多个控制管理站，每个控制管理站都管理各自的成 员，控制管理站之间可通过点到点的方式进行通信，点到点结构的潜在优势在于能 够提供好的扩展性，可以在较少通信资源和计算资源开销的情况下实现较好的可靠 性和高效性。分层式控制的网络中有若干中间控制管理站来实