（通信与信息系统专业论文）无线传感器网络中基于地理位置的层次路由研究.pdf

摘要 无线传感器网络近年来得到了广泛的研究和讨论，它是由大量集成有传感、 数据处理单元和无线通信模块的微小节点组成，这些节点由电池供电，能量、计 算能力和带宽都非常有限，并且一般部署在人不便进入或不能进入的区域，给节 点充电或更换节点都是比较困难的。因此设计能耗低，生命周期长的路由算法成 为目前研究的重点。 本文主要研究了层次路由和基于地理位置的路由，并且针对这些算法能耗高 和生命周期短的缺点，实现了一种综合考虑层次结构和地理位置的路由算法，基 于最优跳数的自适应分簇算法( o h a c a ) 。该算法加入能量筛选过程，令能量储备 较少的节点立即进入休眠状态，通过簇头重新选举机制来调节节点的能量均衡， 并采用基于地理位置和功率控制的多跳路由来解决“热点问题。仿真结果表明， o h a c a 可以延长网络的生命周期，更加有效地利用能量，还可以保证很小的时延。 其中，o h a c a 的生命周期为l e a c h 的1 8 8 倍，相同的能量o h a c a 传送的数 据是l e a c h 的4 5 倍，同时，时延比l e a c h 降低了4 5 5 。 关键词：层次路由地理位置路由自适应机制最优多跳 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 ) h a sb e e nw i d e l ya p p l i e di nr e c e n ty e a r s i tc o n s i s t s o fm a s st i n yn o d e s 、析t hs e n s i n g d a t ap r o c e s s i n ga n dw i r e l e s sc o m m u n i c a t i o nm o d u l e s t h e s eb a t t e r yp o w e r e dn o d e sa r eu s u a l l yd e p l o y e dr a n d o m l ya n dw i d e l y , i ti sd i f f i c u l t f o rt h e mt ob er e c h a r g e do rc h a n g e d b e c a u s eo fl i m i t e dp o w e r , c a l c u l a t i o na b i l i t ya n d b a n d w i d t h , i ti si m p o r t a n tt od e s i g nt h er o u t i n ga l g o r i t h mw i t hl o we n e r g yd i s s i p a t i o n a n dl o n gl i f e t i m e f i r s t ，t h es t r u c t u r e ，f e a t u r e s ，a p p l i c a t i o nf i e l d si sg e n e r a l i z e d s e c o n d ，t h ec u r r e n t r o u t i n gp r o t o c o l so fw s na r ea n a l y z e d ，m a i n l yc l u s t e r - b a s e dr o u t i n gp r o t o c o l sa n d g e o g r a p h i cr o u t i n gp r o t o c o l s ar o u t i n ga l g o r i t h mb a s e dh i e r a r c h i c a la n dg e o g r a p h i c r o u t i n g ，o p t i m a lh o p s b a s e da d a p t i v ec l u s t e r i n ga l g o r i t h m ( o h a c a ) ，i sr e p r e s e n t e d t os o l v et h ed i s a d v a n t a g e ，s u c ha sh i g he n e r g yd i s s i p a t i o na n ds h o r tl i f e t i m e i nt h i s a l g o r i t h m , ap r o c e s so fe n e r g ys e l e c t i o ni sp r o c e e d e dt om a k et h en o d e sw i t hl e s se n e r g y a r em o r el i k e l yt og ot os l e e pi m m e d i a t e l y ；a l la d a p t i v em e c h a n i s mi si n t r o d u c e dt o b a l a n c ee n e r g y am u l t i h o p r o u t i n gb a s e db o t hp o w e rc o n t r o la n dg e o g r a p h i c i n f o r m a t i o ni sa d o p t e dt oa v o i d “h e a tp o i n t s i m u l a t i o nr e s u l t ss h o wt h a t , t h eo h a c ac a ne x t e n dt h en e t w o r kl i f e t i m e ，m a k ea m o r ee f f i c i e n tu s eo fe n e r g ya n dg u a r a n t e eas m a l l e rd e l a y t h en e t w o r kl i f e t i m ei s a b o u t1 8 8t i m e st h a to fl e a c h u s i n gt h es a m ee n e r g y , o h a c at r a n s m i t s4 5t i m e s d a t at h el e a c ha l g o r i t h mt r a n s m i t s b e s i d e st h e s e ，t h eo h a c ac a l ll o w e ru pt o 4 5 5 d e l a yt h el e a c h h a s k e y w o r d s ：c l u s t e r - b a s e dr o u t i n gp r o t o c o l sg e o g r a p h i cr o u t i n gp r o t o c o l s a d a p t i v ec l u s t e r i n gm e c h a n i s mo p t i m a lh o p s 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或研究成果；也不包含为获得西安电子科技大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期坠丝：三：! ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 煎盟型 娅 e t 期塑! ! ：主：! ! 第一章绪论 第一章绪论 近年来，由于在移动终端上的极大灵活性，无线通信在数据及多媒体通信应 用中占到了越来越大的比例。从无线广域网、无线城域网、无线局域网，到无线 个域网，无线通信技术使人们随时随地、及时可靠的进行信息交流的设想逐步成 为现实。无线传感器网络是a dh o e 网络( 无线自组网络) 的一种，作为一种具有 广阔应用前景的新型网络，它相对于传统的网络有很多不同的地方，从理论和技 术上都有很多问题需要解决。因而在网络理论研究乃至整个计算机与网络通信理 论研究中引起了广泛关注，成为研究最热门的领域之一。 1 1 研究背景 无线传感器网络【l 】【2 】是近年来得到迅速发展的新型网络，它的出现和发展对现 代科学技术产生了极其深刻的影响，也显著地改变了人们的观念。无线传感器网 络技术将现代无线通信技术、微型传感器技术和网络技术有机地融为一体，并且 能够获取客观物理信息，在国防、环境监测、运输和其他许多领域具有广阔的应 用前景。美国在2 0 世纪9 0 年代就开始了无线传感器网络的发展，我国国家自然 科学基金委员会已经审批了无线传感器网络相关的一个重点课题和多个面上课 题，在国家发展改革委员会的下一代互联网示范工程中，也部署了无线传感器网 络相关的课题。因此，这项技术已经引起了世界许多国家军界、学术界和工业界 的高度重视，并成为进入2 0 0 0 年以来公认的新兴前沿热点研究领域，被认为是将 对二十一世纪产生巨大影响力的技术之一【3 】。 在传感器网络中，传感器节点由电池提供能量，通过飞机散布，人工布置等 方式，大量部署在感知对象内部或附近，通过自组织方式构成无线网络，以协作 的方式感知、采集和处理网络覆盖区域中特定的信息，可以实现对任意地点，信 息在任意时间的采集，处理和分析。在很多情况下，传感器节点被配置在偏僻的、 难以接近的区域中，传感器网络必须在无任何基础设施的环境中进行长期自主的 工作。同时，传感器节点的能量资源和带宽非常有限，决定了无线传感器网络算 法各层的设计都必须以能源有效为首要的设计要素，同时要兼顾网络的生命周期。 无线传感器网络路由算法的设计与传统无线a dh o e 网络有很大的不同h i 5 1 ， 其重要目标是降低节点能耗，提高网络生命周期，而传统的无线a dh o e 网络的路 由算法设计的首要任务是移动条件下高服务质量的提供。这些不同导致了传统的 无线a dh o e 网络路由算法不能直接用于无线传感器网络中。本课题以提高网络性 2 无线传感器网络中基于地理位置的层次路由研究 能为目的，综合大量路由算法的基础上，对现有的路由算法进行归纳、对比、分 析，从中得出了值得借鉴的优秀思想。有针对性的选择了层次路由算法作为研究 重点，分析了其存在的问题，并针对这些问题在原有算法的基础上实现了改进方 案。总之，对该领域进行深入而广泛的研究提供重要的科学依据。 1 2 国内外研究现状 无线传感器网络路由算法缺乏统一的标准化组织，因此提出的路由算法数量 众多。迄今为止，国内外已经提出了几十种无线传感器网络的路由算法，分别应 用在不同的场合。然而，仍有许多课题有待研究，这些课题主要有以下几个方面： 1 低能耗方面的研究 由s i v ad m u r u g a n a t h a n 提出的由基站控制的动态分簇路由算法( b a s e s t a t i o n c o n t r o l l e dd y n a m i cc l u s t e r i n gp r o t o c o l ，b c d c p ) 6 利用高能量基站来执行更加密集 的工作，通过把能量消耗分散在所有传感器节点来改善网络的生命周期和平均能 量。该算法首先将网络分成两个子簇，然后再将这两个簇分成更小的簇，基站重 复这个工作直到满足了预定的簇数。b c d c p 通过迭代算法来提高能量的利用率， 并且适用于大规模的网络中。 c h i u k u ol i a n g 等人提出了一种基于树的层次路由算法( c l u s t e r - b a s e dm i n i m a l s p a n n i n gt r e ew i t hd e g r e e c o n s t r a i n e d ，c m s t - d c ) t7 1 。在此算法的初始阶段采用了 重新构建簇的方法，以簇为单位构建树，利用最小遍历树的方式减少总的传输距 离。但是，如果出现一个节点连接了很多节点的情况，这个节点就需要从邻居节 点处融合更多的数据，可能会消耗更多的能量。 2 i p v 6 与无线传感器网络的结合 下一代网络的核心是i p v 6 算法，无线传感器网络必将与i p v 6 紧密结合起来， 即6 l o w p a n ( i p v 6o v e rl o wp o w e rw i r e l e s sp e r s o n a la r e an e t w o r k s ) 1 8 】技术。目前提 出的6 l o w p a n 路由算法，主要有6 l o w p a n 基于需求距离的a dh o c 矢量路由 ( 6 l o w p a na dh o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g ，l o a d ) 州和6 l o w p a n 层 次路哇t ( h i e r a r c h i c a lr o u t i n go v e r6 l o w p a n ，h i l o w ) t 1 0 】两种。 l o a d 是一种按需路由算法，使用广播方式来查找路由，节点通常以广播方 式，向目的节点扩散路由请求报文，并由目的节点对该报文进行响应。由于路由 表和广播方式的消耗，使得l o a d 算法开销较高。 h i l o w 是一种分级式路由算法，不需要建立和维护路由表，依靠动态地址分 配算法在树状网络中转发数据。h i l o w 虽然降低了开销，但是路由效率不高，因 为有可能即使是两个相邻的节点通信，也要通过父节点多跳进行，而且一旦某些 关键节点( 如父节点) 失效时则可能造成大面积的网络重构，使得开销大幅度增 第一章绪论 加。 3 跨层算法优化 将路由算法、网络层算法和链路层算法等结合起来进行跨层设计，共享各层 信息，消除冗余报文，减少算法开销，实现算法的优化设计。 由王艳妹等人提出的多媒体传感器网络中跨层优化的实时路由算法 ( r e a l - t i m ee n e r g y b a l a n c e ，r t e b ) ，是一种新的基于能量均衡的实时路由。其核 心思想是做路由决策时，在保证端到端的传输速率基础上，充分考虑节点的剩余 能量和可靠性选择最优下一跳来均衡网络的能量消耗和减少数据重传次数。同时 采用主动拥塞检测机制，利用m a c 层的b a c k 确认消息来通告拥塞，减少控制消 息的开销。 由杨正东，熊庆旭提出的综合覆盖调度的无线传感器网络跨层路由研究 佗】通 过改变计算覆盖集合的条件和单组覆盖集合轮询的工作方式可以获得更好的网络 生存期。 4 q o s 路由 q o s 路由是指在具体的路由算法中增加q o s 参数对路由的约束，根据网络的 可用资源来决定传送路径，从而提供更好的数据传送性能。 t h e 等提出了一种q o s 实时通信路由算法( as t a t e l e s sp r o t o c o lf o rr e a l - t i m e c o m m u n i c a t i o n ，s p e e d ) t 1 3 】，提供了软件实时端到端传输速率保证、网络拥塞控制 和负载平衡机制。该算法要求每个节点都需维护其邻居信息，并采用局部地理信 息转发来寻找路径。此外，s p e e d 路由算法尽力确保网络中每个分组以一定速率 传输，以便每个应用在做出许可决策之前都能够通过到基站或汇聚节点的距离除 以分组的速率来估计分组的端到端延迟。同时，s p e e d 路由算法在网络拥塞时提 供了拥塞避免机制，能够很好的解决拥塞问题。 e m a df e l e m b a n 等人在s p e e d 路由算法的基础上提出了一个支持多路径、多速 度的实时路由算法( m u l t i p a t hm u l t i s p e e dp r o t o c o l ，m m s p e e d ) t 1 4 1 ，它根据相邻的 上下游节点对之间的丢包率来选择转发节点。m m s p e e d 将全局的可靠问题转化为 节点根据本地网络状态进行的判断，并能够在本地判断失误时提供了快速有效的 调整机制，缺点在于未考虑转发节点选择时的能耗等因素。 于磊磊等人提出了一种节能的无线传感器网络q o s 路由算法【1 5 】，该算法通过记 录邻居节点到s i n l ( 节点的最小跳数信息建立到s i n l ( 节点的多条路径，并根据信息包 的q o s 要求和节点剩余能量选择合适的路径进行路由。该算法在提供差别服务和提 高网络生存期方面有明显的优势。 5 路由安全 无线传感器网络具有开放媒体、无中心认证机构、分布式协作等基本特性， 其安全问题比有线网更为严重，路由算法是网络攻击的主要e l 标。 4 无线传感器网络中基于地理位置的层次路由研究 k e e b u mk i m 等人提出了一种基于层次的认证算法( a u t h e n t i c a t i o np r o t o c o lf o r h i e r a r c h y b a s e d ，a p h ) 1 6 】。此算法在网络部署前发布一个唯一的密钥给节点，通过 基站来认证即将进入网络的节点。在稳定阶段通过基站监测节点的状态，这样能 够很好地保护和认证层次路由中遭受网络内部攻击的节点，达到防御和能耗的折 衷。 王潮，贾翔字等人提出的基于可信度的无线传感器网络安全路由算法【l7 】提出 了节点可信度的概念，与群体智能优化算法结合，在路由中引入节点可信度，作 为信息素的一个分配策略，建立可信安全路由，把恶意节点排除出网络，提供安 全可信的无线传感器网络环境，此方法对w o r m h o l e s 攻击的效果明显。 1 3 论文内容及结构安排 本文在充分研究和分析已有研究成果的基础上，实现了一种基于最优跳数的 自适应分簇算法，集中处理如何延长无线传感器网络的生命周期和能量均衡等方 面的问题。该算法在层次路由和地理位置路由的基础上进行了改进，主要目标是 降低系统的能量消耗，延长网络的生命周期，提高数据的接收率，同时实现了网 络的负载均衡和能耗平衡，并且使用了n s 2 仿真工具对算法进行仿真实验，以评 价算法的性能。 本论文共分五章，具体章节安排如下。 第一章阐述了本文的研究背景、无线传感器网络路由算法国内外的研究现状 以及本文研究的目的和意义。 第二章研究了无线传感器网络的路由算法，对现有的路由算法进行了分类， 并描述了其中几种典型的路由算法，重点阐述了层次路由算法和基于地理位置的 路由算法。 第三章在前面几章的基础上实现了基于最优跳数的自适应分簇算法，阐述了 该算法的实现背景，能量模型和具体的实现细节。 第四章利用n s 2 对几种不同的路由算法进行了模拟仿真，并且利用网络的q o s 要求对仿真的结果进行分析。 第五章对全文进行了总结，阐述了对无线传感器网络的展望，并指出了下一 步要进行的工作。 第二章无线传感器网络路由算法研究 第二章无线传感器网络路由算法研究 网络数据传输离不开路由算法，传感器节点的计算能力、存储能力、通信能 量以及携带的能量都十分有限，每个节点又只能获取局部网络的拓扑信息，这就 要求网络算法不能太复杂而且必须考虑能量优先。传统的无线网络路由算法的主 要任务是寻找源节点到目的节点间通信延迟小的路径，同时提高整个网络的利用 率，避免产生通信拥塞并均衡网络流量等，而能量消耗问题不是这类网络考虑的 重点。因此，传统无线网络的路由算法不适用于无线传感器网络。目前提出了多 种类型的无线传感器网络路由算法，因此研究这些路由算法，比较分析哪一种路 由算法是相对合适的显得尤为重要，也是此课题的意义所在。 2 1 无线传感器网络结构 1 无线传感器网络的节点特征 组建一个无线传感器网络，首先要求组成的节点可靠且有效。节点的设计必 须满足具体应用的特殊要求，例如小型化、低成本、低功耗，并为节点配备合适 的传感器、必要的计算功能、内存资源以及适当的通信设备。不同的应用中，传 感器网络节点的结构不尽相同，但一般由传感单元、数据处理单元、数据传输和 电源四部分构成1 1 剐。图2 1 中描述了传感器节点的组成，其中实心箭头的方向表示 数据在节点中的流动方向。 高层应用 悃怔 传感器h 数模转换 存储器 传感单元 数据传输 j l j l 处理器 微控制器 l 电源 l 图2 1 传感器节点的内部组成 2 无线传感器的网络结构 无线传感器的网络结构如图2 2 所示【1 9 】。无线传感器网络系统包括任务管理节 6 无线传感器网络中基于地理位置的层次路由研究 点，s i n k 节点和传感节点。在传感器网络中绝大多数的节点只有很小的发射范围， 而s i n k 节点的发射能力较强，具有很高的电能，可以把数据发回远程控制节点。 大量的传感器节点随机的部署在需要被监测区域的内部或附近，这些节点自 组织地构成网络，以协作的方式感知、采集和处理网络覆盖区域中任意地点任意 时间的特定的信息，通过嵌入式系统对信息进行网内计算和融合，并通过随机自 组织无线通信网络以多跳中继方式将监测数据传到汇聚节点，最后通过互联网或 卫星到达管理节点。用户通过管理节点对传感器网络进行配置和管理，发布监测 任务以及收集监测数据。 点 图2 2 无线传感器网络的网络结构 3 无线传感器的拓扑结构 无线传感器网络的拓扑结构有3 种，星状网、网状网及混合网【2 0 】【2 l 】f 2 2 1 ，每种 拓扑结构都有自身的优点和缺点。 基本的星状网拓扑结构是一个单跳( s i n g l e h o p ) 系统，网络中所有无线传感器节 点都与基站和网关进行双向通信，如图2 3 ( a ) 。基站可以是一台p c 、p d a 、嵌入 式网络服务器，或其它与高数据率设备通信的网关，除了向各节点传输数据和命 令外，基站还与因特网等更高层系统之间传输数据。各节点将基站作为一个中间 点，相互之间并不传输数据或命令。 在各种无线传感器网络中，星状网整体功耗最低，但节点与基站间的传输距 离有限，一般只有几十米。网状拓扑结构是多跳( m u l t i h o p ) 系统，其中所有无线传 感器节点都相同，而且直接互相通信，如图2 3 ( b ) 。网状网的每个传感器节点都有 多条路径到达网关或其它节点，因此它的容故障能力较强。这种多跳系统比星状 网的传输距离远得多，但功耗也更大，因为节点必须一直“监听”网络中某些路 径上的信息和变化。 混合网兼具星状网的简洁和低功耗以及网状网的长传输距离和自愈性等优 点，如图2 3 ( c ) 。混合网中，路由器和中继器组成网状结构，而传感器节点则在它 们周围呈星状分布。中继器扩展了网络传输距离，提供了容错能力。当某个中继 器发生故障或某条无线链路出现干扰时，网络可在其它路由器周围进行自组。 第二章无线传感器网络路由算法研究 必嚣x y - 六o _ 一：妥一： oo u ( a ) 星型网络 ( b ) 网状网络 99 q 、厶一厶，o 厶a d 7bob r c 、层网混合网络 图2 3 无线传感器网络拓扑结构 2 2 无线传感器网络路由算法 路由技术是无线传感器网络通信层的核心技术，也是当今国内外研究的热点。 在多跳网络中，需要使用中间节点在源节点和目的节点之间中继数据分组。这样， 中间节点就必须确定其下一跳节点，使其知道向哪个邻近节点转发收到的、但并 不是发给自己的数据分组。路由技术就是负责将数据分组从源节点通过网络转发 到目的节点，主要包括两个方面的功能，寻找源节点和目的节点间的优化路径以 及将数据分组沿着优化路径正确转发。从路由的角度看，无线传感器网络有其自 身的特点，使它既不同于传统网络，又不同于移动自组织网( m o b i l e a dh o cn e t w o r k , m a n e t ) 。无线传感器网络自身的特性决定了其路由算法设计的基本特点，能量低、 规模大、移动性弱、拓扑易变化、使用数据融合技术以及通信的不对称。因此， 设计路由机制时，要满足下面的传感器网络路由机制要求【2 3 1 。 1 能量有效 无线传感器网络中节点由于地理位置等方面的问题，能量有限，因此需要考 虑节点的能量消耗问题，同时延长整个网络的生命周期也是传感器网络路由算法 设计的重要目标。传感器网络路由算法不仅要选择能量消耗小的消息传输路径， 而且要考虑整个网络，选择使整个网络能量消耗均匀的路由。 2 基于局部拓扑信息 无线传感器网络为了节省通信能量，避免某些节点过早死亡，通常采用多跳 的通信模式。而节点有限的存储资源和计算资源，使得节点不能存储大量的路由 信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的 情况下，如何实现简单高效的路由机制是无线传感器网络的一个基本问题。 3 可扩展性 传感器网络应该能支持上千个节点，网络规模更大，这就意味着路由算法收 敛时间更长。网络规模越大，路由收敛时间和路由发现时间就越长，而网络拓扑 8 无线传感器网络中基于地理位置的层次路由研究 保持不变的时间间隔则越短。所以说在传统无线网络中工作很好的路由算法在传 感器网络中性能却可能显著下降，甚至根本无法使用。这就要求路由机制具有可 扩展性，可以适应网络结构的变化。 4 容错性 能量用尽或环境因素使得节点死亡，周围环境影响无线链路的通信质量以及 无线链路本身的缺点等，这些无线传感器网络的不可靠特性要求路由机制有一定 的容错能力。 5 快速收敛性 传感器网络的拓扑结构动态变化，节点能量和通信带宽等资源有限，因此要 求路由机制能够快速收敛，以适应网络拓扑的动态变化，减少通信算法的开销。 2 2 1 无线传感器网络参考模型 随着无线传感器研究的深入，在无线传感器网络体系结构设计中，目前存在 很多的设计方案【2 4 】【2 5 】【2 6 】【2 7 】，尚不存在一个真正意义上统一的标准，虽然他们都 还是基于类似于o s i 的算法体系结构，但各自都有自己鲜明的特点。由于无线传 感器网络是由传统的网络发展而来，其最根本的特点在于继承了网络的无线自组 织成网的特点。无线传感器网络节点采用的通信算法依然是五层算法结构，物理 层、数据链路层、网络层、传输层和应用层，如图2 4 所示。该分层结构的设计是 以节约能耗为前提，并以高冗余度作为设计策略以保证不可靠环境下的有效特征 功能。该体系结构能够支持感知并适应动态的网络拓扑改变，并在此基础上实现 路由算法的自适应性和可扩展性。 应用层 传输层 网络层 数据链路层 物理层 网络服务接口：网络管理接口 事件同步 节点定位 传输控制 移动性 q 能配安远 路由 0 量置全程 s 拓扑控制 管管管管 信道接入拓扑构成 理 理 理 理 控制 无线电红外线光纤 图2 4 无线传感器网络协议栈 物理层的功能包括信道的选择、无线信号的监测、信号的发送与接收等。传 感器网络采用的传输媒体主要有无线电、红外线、光波等，物理层的设计目标是 以尽可能少的能量损耗获得较大的链路容量。 数据链路层的主要任务是加强物理层传输原始比特的功能，使之对网络显现 第二章无线传感器网络路由算法研究 9 为一条无错链路。该层又可细分为媒体访问控制子层和逻辑链路控制子层。其中 媒体访问控制层规定了不同的用户如何共享可用的信道资源。本文在数据链路层 中采取的是冲突避免结合时分复用技术来实现各个节点对信道资源的共享。 网络层的主要功能包括分组路由、网络互联、拥塞控制等。以通信网络为核 心，实现传感器与传感器、传感器与用户之间的通信，对传感器节点进行有效的 控制和管理，支持多传感器协作完成大型感知任务。需要展开的研究工作包括低 能耗、高速率、长生命周期的无线传感器网络的随机自组织通信算法、通信方式 及自重构、自调整性；无线传感器网络的可扩展性、容错性、可维护性及安全性、 隐私性；适用于无线传感器网络的网络通信模式、支持无线传感器网络通信的各 种算法、时间同步、任务分配与协调控制以及相应的软硬件资源等方面。本文选 择基于层次化的路由算法。 传输层负责数据流的传输控制，提供可靠的、开销合理的数据传输服务，结 合本文应用的无线传感器网络的通信特点，选择数据采集层中无线传感器网络传 输层的算法。 应用层主要实现各种数据融合的功能，进而满足系统对无线传感器网络定位、 时间同步等方面的要求，以及维护自身无线网络的组网和多跳数据的传输问题。 2 2 2 无线传感器网络路由算法分类 针对无线传感器网络中数据传输的特点和难题，研究人员提出了不同的路由 算法，无线传感器网络路由算法的分类基本上延续了传统a dh o c 网的分类方法， 根据不同的角度可以进行不同的分类f 2 3 1 2 8 】【2 9 1 ，如图2 5 所示。本文将现有的无线 传感器网络路由算法分为以下四类 3 0 1 ，以数据为中心的路由算法、层次路由算法、 基于地理位置的路由算法和基于q o s 的路由算法。 无线传感器网络路由协议 网络结构li 应用场合 亚 面 路 由 层 次 路 由 传感器节点的 特性和结构 能 量 感 知 路 由 基 于 查 询 的 路 由 地 理 位 置 路 由 可 靠 路 由 数 据 为 由 心 路 由 图2 5 路由算法的多种分类 层 次 路 由 地 理 位 置 路 由 基于 网络 q o s 的路 由 1 0 无线传感器网络中基于地理位置的层次路由研究 1 以数据为中心的路由算法 这类算法的基本思想是对传感器网络中的数据用特定的描述方式命名，数据 传送基于数据查询并依赖数据命名，对相同属性的数据在传输过程中进行融合操 作，减少网络中冗余数据的传输。s i n k 节点向特定区域发出查询，并等待该区域 节点发回符合查询条件的数据，从而将所有的数据通信都限制在局部范围内，极 大地减少了网络中大量传送的重复冗余数据，降低了能量损耗。高效标准的数据 命名机制和查询信息的高效传送是未来研究的方向。 这类算法有定向路由( d i r e c t e dd i f f u s i o n ，d d ) 【3 1 1 和基于协商的传感器路由 ( s e n s o rp r o t o c o lf o ri n f o r m a t i o nn e g o t i a t i o n s p i n ) t 3 2 1 。 2 层次路由算法 无线传感器网络无固定通信设施和自组织的特点使其具有极大的灵活性，但 分布控制、无中心和动态拓扑等特点限制了系统的可扩展性。为解决移动自组网 可扩展性问题，人们提出了层次化的解决方案。该方案重点考虑了路由算法的可 扩展性，其主要特征是将传感器节点按照特定规则分为多个簇，通过该簇的头节 点( c l u s t e rh e a d ，c h ) ? e 集簇内感知数据或者转发其他簇头节点的数据，具体可细分 为以下两种模式【3 3 】。 单层模式指路由算法仅对传感器节点进行一次簇划分，通常假设每个簇头节 点能直接与s i n l ( 节点通信。 多层模式指路由算法将对传感器节点进行多次簇划分，即簇头节点将再次进 行簇划分。 层次结构网络的可控制性比平面网络的要好，其扩展性也比较好，而且网络 相应时间也比较短。 典型的分层路由算法有低功耗自适应集簇分层算法( l o w - e n e r g ya d a p t i v e c l u s t e r i n gh i e r a r c h y , l e a c h ) t 3 4 1 ，中心控制的低功耗自适应集簇分层算法 ( l e a c h c e n t r a l i z e d ，l e a c h c ) t 3 5 1 ，传感器信息系统中能量有效聚合路由算法 ( 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 ns y s t e m s ，p e g a s i s ) 3 6 】，能量有效的 分布式层次路由算法( 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 ，h e e d ) 【3 刀，基于 能量有效的门限感知传感器网络算法( 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 r n e t w o r kp r o t o c 0 1 t e e n ) t 3 8 1 ，确定性簇头选择算法( d e t e r m i n i s t i cc l u s t e r - h e a d s e l e c t i o n ，d c h s ) t 3 9 】等。 3 基于地理位置的路由算法 在传感器网络中，节点通常需要获取它的位置信息，这样它采集的数据才有 意义。地理位置路由假设节点知道自己的地理位置信息，以及目的节点或者目的 区域的地理位置，利用这些地理位置信息作为路由选择的依据，节点按照一定策 略转发数据到目的节点。基于地理位置的路由算法利用节点的位置信息来进行数 第二章无线传感器网络路由算法研究 据发送，如何智能的利用节点的位置信息来达到能源有效性的目的是研究的要点。 节点的地理位置信息可以作为一个辅助条件，用来改善一些已有的路由算法的性 能，比如将感知数据或者查询请求发送到指定方向从而减少泛洪带来的数据无效 传输的问题，也可以直接使用地理位置信息来实现路由。 这类路由有最小传输能量路i 土l ( m i n i m u mt r a n s m i s s i o ne n e r g y , m t e ) 3 4 1 ，基于 最优化距离的地理位置路i 主l ( o p t i m a ld i s t a n c eg e o g r a p h i cr o u t i n g ，o d g r ) m j ，分布 式传感器网络中基于地理位置的多跳分簇路由( g e o g r a p h i c a l 。b a s e dm u l t i h o p c l u s t e r i n ga l g o r i t h mf o rd i s t r i b u t e dw i r e l e s ss e n s o rn e m o r k ，g b m c a ) 1 4 1 1 ，地理位置 和能量感知路由( g e o g r a p h i ca n de n e r g ya w a r er o u t i n g ，g e a r ) 4 2 1 等。 4 基于q o s 的路由算法 q o s 是网络在传输数据流时需要满足的一系列服务要求，是指用户要求网络传 输系统所必须保证的关于信息传输的质和量的特征集，它反映了服务提供者和服 务使用者之间的能力和需求的相互关系，是用来描述网络性能的。它具体可以量 化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标。 传感器网络的q o s 就是根据传感器网络感知现场的不同，把感知到的信息沿 最优的一组传感器节点传送到汇聚节点。通常涉及传感器网络路由要达到两个目 标，网络生存期最大化：有足够多的节点把信息传送到汇聚节点，以保证其收集 到足够多的数据。因此，需要从两个方面考虑q o s 路由，网络能耗方面，即信息 沿怎样的路径传送能均衡网络能耗，以延长网络生存期；业务方面，即保证业务 提出的延迟、可靠性等q o s 要求。在现代应用中这种算法具有更加深远的意义， 是将无线传感器网络路由算法应用于实际生活中所必须考虑的问题。 这类路由有有序分配路( s e q u e n t i a la s s i g n m e n tr o u t i n g ，s a r ) t 4 3 1 ，s p e e d 等， 针对一些特殊的网络应用，有一些特定的q o s 要求，比如对于网络安全的问题， 现存算法有a p h 等等。 2 2 3 路由算法性能比较 各种路由算法都是针对特定的应用环境而设计的，在不同的环境下表现出各 自的特色和优势，因此不能绝对的判断哪种算法最优。当需要持续采集网络中所 有区域的信息时，可以采用泛洪、谣传路由【4 4 1 、l e a c h 路由算法；当只需要采集 特定区域的特定数据信息时，可以采用s p i n 、t e e n 、d d 算法。 表2 1 重点选择了无线传感器网络各分类中最有代表性的路由算法作为比较 的对象，对它们的路由策略、路由优化方式和网络体系结构的不同表现给出了一 个综合比较。 1 2 无线传感器网络中基于地理位置的层次路由研究 表2 1 无线传感器网络路由算法性能比较 路由 路由提供生存以数据为数据健壮多跳最佳 结构策略节能时间中心融合性路径路径 f l o o d i n g 平面按需否不好否无较好 是 否 g o s s i p i n g 平面按需否不好否无较好是否 d d 平面按需是较好是有较好否是 s p i n平面 按需是较好是有不好否否 l e a c h层次主动是 较好 否 有较好否 否 p e g a s i s层次主动是 较好 否有 较好 否否 t e e n 层次主动是较好是有较好否否 2 3 层次路由算法 层次路由算法实际上是一种分簇结构的路由算法，如图2 6 所示。簇内和簇间 节点形成两层结构，将簇进行更细粒度的划分就形成多层嵌套的层次结构。多层 次结构适用于规模更大的网络，但通常两层结构已可以满足大多数应用需求， l e a c h 算法及改进算法均采用两层簇类模式。无线传感器网络中分簇算法必须完 成簇生成过程和簇维护过程两个部分。其目标是构造一个能够覆盖整个网络并较 好支持资源管理和路由的互联的簇集合。 员 图2 6 簇结构 分簇路由算法设计都大致包括3 个阶段，簇头的产生；簇的形成；簇的路由。 在分簇的拓扑管理机制下，网络中的节点可以划分为簇头节点和成员节点两类。 在每个簇内，根据一定的机制算法选取某个节点作为簇头，用于管理或控制整个 第二章无线传感器网络路由算法研究 簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处 理以及簇间转发。 簇头的产生是簇形成的基础，簇的路由依赖于簇的结构。它们是分簇路由算 法设计的关键技术。所有的无线传感器网络分簇算法都是围绕如何选择簇头、如 何成簇、如何传输数据来考虑设计的，同时要考虑如何节省能量和延长网络生命 周期。 1 低功耗自适应集簇分层算法( l e a c h ) 由h e i n z e l m a n 等人提出的l e a c h 算法假定了一个均匀的、节点能量有限的 密集传感器网络，各节点向接收节点报告其数据。图2 7 描述了l e a c h 算法的结 构，它将基于t d m a 的m a c 算法与聚类算法和一个简单的“路由”算法集成在 一起。出发点主要是考虑簇内节点的能量消耗问题，目的是为了延长节点的工作 时间，并且实现节点的能耗平衡。 卜- 设置阶段卜- 一稳态阶段 i 簇形成i 图蒜糯i 图勰 时间 _ 一i 帧 图2 7l e a c h 的结构 l e a c h 的基本思想是网络周期性地随机选择簇头节点，其他的非簇头节点以 就近原则加入相应的簇头，形成簇。簇内节点将感知到的数据直接发送给簇头， 由簇头转发给s i n l 【节点，簇头节点可以将本簇内的数据进行融合处理以减少网络 传输的数据量。 ( 1 ) 设置阶段 当簇创建时，每个节点决定是否在当前轮成为簇头节点。簇头节点的选择根 据网络中所需的簇头节点数和迄今为止每个节点已成为簇头的次数来决定。具体 选择方法是每个传感器节点选择【0 ，l 】之间的一个随机数，如果选定的值小于某一个 阈值p ( ，) ，那么这个节点成为簇头节点。( f ) 为 七 p ( ，) 2 1 7 一j 宰( 厂m 。d 譬) c ，( f ) = 1 ( 2 一1 ) e ( f ) = 0 式中，七为簇头节点的需求率，为网络中总的节点数，为当前的选举轮数， c ，( f ) = 0 表示最近的( r m o d ( n k ) ) 轮节点已经担任过簇头，c ，( f ) = l 反之。 一旦当节点决定它加入哪个簇后，它将通知簇头节点自己会成为该簇中的一 员，每个节点通过c s m am a c 算法将该信息传给簇头。在这个阶段，簇头节点要 保持其接收器始终处于接收状态。 1 4 无线传感器网络中基于地理位置的层次路由研究 当簇头节点收到所有簇成员节点发送的信息后，它将根据簇内节点的数量创 建t d m a 时刻表并通知每个节点何时开始传输数据。 ( 2 ) 稳态阶段( 数据传输阶段) 一旦簇形成，t d m a 时刻表确定，数据传输就开始了。簇头节点在收到成员 节点传来的数据后对数据进行数据融合和压缩，将压缩处理后的信号传输给s i n k 节点。在经历一段时间后，新的一轮又从新开始。上述过程又开始循环进行。 依据到目前为止的算法描述，l e a c h 不能覆盖几个平方英里这样大的区域， 这是凶为如果簇头距离接收节点的距离大于2 英里，则其很难保证有足够的能量 以与接收节点进行通信。如果簇头可以通过其他簇头进行转发，这种限制会减弱。 2 中心控制的低功耗自适应集簇分层算法( l e a c h c ) l e a c h 算法的提出者后来在l e a c h 的基础上改进得到了一种集中式的路由 算法l e