（通信与信息系统专业论文）多层网状局域连通环境wsn路由算法与节点定位.pdf

摘要 摘要 随着智能化、网络化传感器技术的日益成熟，针对特殊场合的应用的无线 传感网络( w s n ) 引起了人们的重视与研究。路由和节点定位问题是w s n 网络 进行目标识别、监控、跟踪等众多应用的前提，更是特殊场合w s n 网络研究中 的重点问题。 首先对现有的适用于自由空间的w s n 网络拓扑及路由协议和节点定位协议 进行了分析，借鉴相应的系统结构与协议。在此为基础上对多层网状局域连通 环境下的w s n 网络拓扑及路由和节点定位机制进行了总体设计，给出了新的算 法，着重分析了新算法的环境适应性和性能增益，根据应用需求完成了仿真和 相关指标分析。 基于地下空间交通或矿井的局域性、环状连接成网的、多层结构环境中无 线传感网络既有平面局部连通分布，也有垂向分层分布，形成多层网状连通的 空间分布的特点，在经典的分层路由l e a c h 算法的基础上，给出了加入了蚁群 优化算法的网络拓扑及路由方案( l e a c h 伽盯) ，着重考虑算法的能量和网络 生存时间的限制。同时，给出了考虑信号衰减和建筑材料的w s n 节点的数学模 型，使用改进的r s s i 和m l e 进行定位算法的实现。通过使用迭代的方式实现 了层内的节点定位，并在层与层使用连通节点传递不同层的节点信息，完成三 维空间的定位计算。 对以经典的l e a c h 算法和传统节点定位算法与l e a c h a n t 网络拓扑及 路由方案和改进后的定位算法性能进行了比较。仿真结果表明：在多层网状局 域联通环境下，l e a c h a n t 方案使得网络连通节点可以通过最优路径发送数据 包，减少了网络中传感器节点的能耗，延长了网络生存时间；节点定位算法能 够实现三维节点定位，与传统的基于信号强度指示测距算法相比精度有所提高。 研究成果为地下多层复杂环境空间w s n 网络应用提供了一定的理论基础。 关键词：w s n 网络，路由，节点定位，多层网状局域连通，算法 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e l l i g e n t i z e dw i r e l e s ss e n s o rn e t w o r k st e c h n o l o g y ， t h er e s e a r c h so fa p p l i c a t i o n o r i e n t e dw s na r eg e t t i n gm o r ea n dm o r ea a e n t i o n s b e i n gt h ec r i t i c a lp r o b l e m so f w s n t e c h n o l o g y ，r o u t i n ga n dn o d el o c a l i z a t i o na r et h e p r e c o n d i t i o no ft a r g e ti d e n t i f i c a t i o n ，s u r v e i l l a n c e ，t r a c k i n ga n do t h e ra p p l i c a t i o n s ， b a s eo nt h ea n a l y z eo fi n t e r n a la n do v e r s e a sr e s e a r c h e so fr o u t i n ga n dn o d e l o c a l i z a t i o np r o b l e m s ，an o v e lm e c h a n i s mo fs e n s o rr o u t i n ga n dn o d el o c a l i z a t i o ni s d e s i g n e db yu s i n gt h ec u r r e n tn e t w o r ks t r u c t u r e sa n dp r o t o c o l sf o rr e f e r e n c e t h e n o v e lm e c h a n i s me m p h a s i z ep a r t i c u l a r l yo na d a p t i o np e r f o r m a n c ea n da c c o m p l i s h t h ep a r a m e t e ra n a l y z eo n c o m m a n d a l o n ew i t ht h et r a n s p o r t a t i o na n dm i n e r a l e x p l o i t a t i o n ，t h es t r u c t u r e o f u n d e r g r o u n ds p a c eh a sb e c o m em o r ea n dm o r ec o m p l i c a t e d ，w h i c hf i n a l l yl e a dt oa m u l t i l a y e r - m e s h e dl o c a l - c o n n e c t e de n v i r o n m e n t t h u s ，t h er e q u e s t so ft h eh o r i z o n t a l a n dv e r t i c a lc o n n e c t i v i t yo ft h en e t w o r ka r er a i s e d t h en o v dr o u t i n ga l g o r i t h m c o m b i nt h el e a c ha n dt h ea n ta l g o r i t h ma n dg i v e s s p e c i a la n e n t i o nt ot h e l i m i t a t i o no fn e t w o r kl i f et i m ea n de n e r g yc o n s u m p t i o n ，a l s o ，an o d e m o d e l c o n s i d e r i n gt h ea t t e n u a t i o no fs i g n a la n dt h eb u i l d i n gm a t e r i a li sg i v e n ，a n dt h en o v d i t e r a t i v ec a l c u l a t i n gl o c a l i z a t i o na l g o r i t h mc o m b i n i n gt h er s s ia n dn 皿ei sd e s i g n e d w h i c hc a nr e a l i z en o d el o c a l i z a t i o n t h ec o m p a r ed a t ab e t w e e nt h ec l a s s i c a la n dt h en o v e lm e c h a n i s mi sg i v e nb y t h es i m u l a t i o no fn s 2 t h er e s u l t ss h o wt h a tt h el e a c h a n t r o u t i n ga l g o r i t h mh a s r e d u c e dt h e e n e r g yc o n s u m p t i o na n dp r o l o n g e dt h e l i f e - t i m eo fn e t w o r kb y t r a n s m i s s i o n t h r o u g h t h e o p t i m i z e dr o u t e f u r t h e r m o r e ，t h ea c q u i s i t i o n a n d c o m m u n i c a t i o no ft h r e e d i m e n s i o n a ln o d el o c a t i o ni n f o r m a t i o ni sr e a l i z e da n dt h e p r e c i s i o no fl o c a l i z a t i o ni si m p r o v e d t h e s ec o n c l u s i o n sa r eb e n e f i c i a l t ot h e a c a d e m i cf o u n d a t i o nf o rf u r t h e rw s n a p p l i c a t i o nr e s e r c h e si nm l m l c e n v i r o n m e n t k e yw o r d s ：w s n ，r o u t i n g ，n o d el o c a l i z a t i o n ，m u l t i l a y e r - m e s h e dl o c a l c o n n e c t e d ， a l g o r i t h m i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：髑蟮硅 砂堍 年工月砧日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：叭硅 瑚年1 月少| ) 日 第1 章引言 第1 章引言 1 1w s n 的发展及其特点 随着半导体技术、微系统技术、通信技术、计算机技术的飞速发展，2 0 世 纪9 0 年代末发展了现代意义的无线传感网络技术【1 1 。无线传感网络的概念和理 论的出现，相继被一些重要机构预测为将改变世界、对人类未来的生活方式产 生深远影响的重要新技术之一，相关研究工作在世界各国家迅速地开展起来。 无线传感网络综合了传感器技术、嵌入式计算技术、现代网络及无线通信 技术、分布式处理技术等，能够通过各类集成化的微型传感器协作地实时监测、 感知和采集各种环境或监测对象的信息。并以自组多跳的网络方式传送到用户 终端，从而实现物理世界、计算机世界以及人类社会三元世界的连通，实现所 谓的“传感网络时代 【2 1 。无线传感网络在当前在国际上备受关注的、涉及多学 科高度交叉、知识高度集成的前沿热点研究领域。随着无线通信、集成电路、 传感器以及微电子机械系统( m e m s ) 等技术的飞速发展，使得低成本、低功耗、 多功能的微型无线传感器的大量生产成为可能，这些微型无线传感器具有无线 通信、数据采集和处理、协同合作等功能，与相关的网络功能结合，形成互通 互连的信息网络平台。研究结果表明，无线传感器网络具有十分广阔的应用前 景，在军事国防、工农业、城市管理、生物医疗、环境监测等许多重要领域都 有实际与潜在的实用价值。 从研究与进展现状看【3 1 ，国内具有现代意义的无线传感网络及其应用研究几 乎与发达国家同步启动，首次正式出现于1 9 9 9 年中国科学院“信息与自动化 领域研究报告中的“重点地区灾害实时监测、预警和决策支持示范系统。随 着研究的深入，2 0 0 1 年中国科学院依托上海微系统所成立微系统研究与发展中 心，在无线传感器网络方向上陆续部署了若干重大研究项目和方向性项目，上 海微系统所、声学所、微电子所、计算技术研究所、半导体所、电子所、软件 所以及中国科技大学等1 0 余个研究所和高校参加相关的研究工作。经过几年的 努力，初步建立了传感器网络系统的研究平台，在无线智能传感器网络通信技 术、微型传感器、传感器端机、移动机站和应用系统等方面取得了很大进展， 1 第1 章引言 2 0 0 4 年相关成果在北京进行了大规模外场演示，部分成果已在实际工程系统中 使用。同时，国内许多重点大学成立了专门的研究机构，对无线传感网络的理 论和技术进行专门研究，取得了许多重要成果；许多大学的研究人员加入了研 究行列，发表了大批相关的论文。国外，“w i r e l e s ss e n s o rn e t w o r k s ”的概念提出 后，美国的加州大学伯克利分校、加州大学洛杉矶分校和麻省理工学院等多所 大学开始有很丰富的研究成果。到2 0 0 4 年到2 0 0 5 年，关于传感器网络的资料 非常多，美国主流大学几乎都在研究无线传感器网络，在许多方面取得了实质 性的进展；印度、日本、英国等许多国家也在无线传感网络研究方面取得了许 多成果【4 1 。 从理论与技术层面上看，国内外的研究人员普遍认为无线传感器网络的主 要特点为自组织、无控制中心、多跳路由、动态拓扑、以数据为中心、节点数 众多分布密集、资源受限、与应用紧密相关【4 5 】。围绕无线传感网络的这些特点， 研究人员的研究从涉及网络系统的基本网络协议，包括路由协议、m a c 协议、 拓扑控制协议以及低功耗低速率的无线网络协议i e e e8 0 2 1 5 4 、z i g b e e 协议的 网络核心技术；到形成完整网络应用所需要的定位技术、时间同步技术、网络 安全技术、数据管理技术、数据计算技术以及数据融合技术的网络支撑技术； 再到源于应用而又服务于应用的现实可行的网络硬件平台、软件平台、算法语 言、微操作系统，以及较完善的软硬件设计原则、高效的开发平台等系列具有 特色的应用方面进行了卓有成效的研究，基本解决了实现无线传感网络的理论、 技术与工程问题。 从发展趋势和目标看，无线传感网络一出现就受到的广泛关注，是源于其 可能及潜在的巨大应用价值，特别是针对特殊场合的应用，而且从目前的研究 成果也日益证明其良好的应用前景。因此在其基本理论已成熟的情况下，进一 步完善网络协议、网络支撑、应用开发平台的理论与技术，研究其特殊环境条 件下的适应性、应用机制，开发实用系统成为新的热点，这也是研究人员的研 究工作最终追求的目标。 1 1 1w s n 路由算法 路由协议的主要功能是将数据从源节点通过网络转发到目的节点，它主要 包括两个方面的功能：寻找源节点和目的节点之间的优化路径，将数据分组沿 着优化路径正确转发。w s n 网络具有通信、电源、计算能力有限；传感器数量大、 2 第1 苹引言 分布范围广；网络具有动态性：感知数据流巨大；以数据为中心等特点，这些 特点决定了不能简单地用传统a dh o c 网络的路由算法应用到传感器网络。与a d h o c 和w l a n 等传统的无线网络相比较，w s n 网络路由的首要任务并不是提高服务 质量和公平有效地利用网络带宽，相对的，它更注重对网络能量消耗、网络生 存时间和数据收集问题。因此必须设计全新的、适合于无线传感器网络特点的 路由协议。 按网络结构不同，w s n 路由协议可以分成平面、层次化和基于位置信息三 类路由技术【6 】。在平面路由协议中，所有节点角色相同。而层次化协议目标是： 形成多个簇以便簇头节点可以聚集数据，减少数据传输量，从而节约能量。基 于位置信息的路由协议利用位置信息转发数据到指定区域而不是整个网络。这 些协议也可根据协议操作的不同，分成多路径、查询、协商、q o s 和相关性等路 由技术。按照源节点到目标节点路径发现方式的不同，w s n 路由协议也可分成三 类：主动式( p r o a c t i v e ) 、反应式( r e a c t i v e ) 和混合式( h y b r i d ) 。主动式协议要 求在路由数据前所有路径己计算妥当，可以让发送出去的数据包立刻到达目标 节点，不会有任何时延，但是这种协议必须周期性广播信息以保持路径的时效 性，所以相当浪费网络带宽和能量，但是若要降低广播所造成的带宽浪费，就 要拉长每次广播的间隔时间，这又将会造成路由表不能及时正确反映网络拓扑 变化情况；而反应式协议只在需要使用路径时才计算路径，其最大好处是带宽 的使用量较小，只是数据包传输平均时延较长。混合式协议组合运用前两类协 议的思想，希望能充分利用这两类协议的优点。 美国的麻省理工学院、康奈尔大学、南加州大学等很多大学开展了无线传 感器网络通信协议的研究，先后提出了几种新的路由协议，包括s e n s o rp r o t o c o l f o ri n f o r m a t i o nv i an e g o t i a t i o n ( s p i n ) 、d i r e c t e dd i f f u s i o n 、l e a c h 、 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 o l ( t e e n ) 等。 目前，国内的清华大学、电子科技大学、哈尔滨工业大学等单位已经开始了该 领域的研究工作，但目前主要集中在介绍国外的研究进展，提出新的研究问题【7 8 】 o 1 1 2w s n 定位技术 无线传感器网络为科技工作者提出了许多具有挑战性的研究课题，而定位 就是其中之一。w s n 定位技术是大多数应用，特别是军事应用的基础。无线传感 3 第1 章引言 器网络中的定位机制与算法包括两部分【9 】：节点自身定位和外部目标定位，前者 是后者的基础。不知道传感器位置而感知的数据是没有意义的。传感器节点必 须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外 部目标的定位和追踪。另一方面，了解传感器节点位置信息还可提高路由效率， 为网络提供命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡和 网络拓扑的自配置。 节点定位技术是一项复杂的技术，涉及的内容多，范围广。从对目标节点 定位精度的要求来看，由于受多径、非视距( n l o s ) 传播的影响，使各种信号 特征测量值总是存在一定偏差，从而使各种适用于特征测量值误差服从零均值 高斯分布的定位算法，如最d - - 乘算法n 町的性能显著下降，使对目标节点的位 置估计精度出现较大偏差。而且由于传感器节点资源受限的特点，与传统的蜂 窝网络和w l a n 定位系统相比，解决其目标节点定位问题有更大的挑战性。传 感器网络节点的能量有限，存储能力和计算能力有限，这些约束要求定位算法 必须是低复杂性的。要进一步延长网络的生存周期，就必须要减少定位过程中 的通信开销，因为无线通信的能耗是节点的主要能耗。目前的算法大都在能耗、 成本和精度上作了折中考虑。由于各种应用差别很大，没有普遍适合于各种应 用的定位算法，因此要针对不同的应用，通过综合考虑节点的规模、成本及系 统对定位精度的要求，来选择最适合的定位算法。 由于无线传感器网络巨大的科学意义和应用价值，它已经引起了世界发达 国家的学术界、军事部门和工业界的极大关注。从2 0 0 1 年开始，节点自身定位 方面，d a r p a ( 美国国防部高级研究计划署) 已把智能传感器网络作为一项最 高优先发展的研究计划，出资近7 亿美元，在众多大学和研究机构展开传感器 网络的基础研究，以求获得五角大楼想要的所谓战区“超视觉”数据。2 0 0 2 年 8 月，n s f ( 美国国家科学基金会) 一期资助4 0 0 0 万美元在u c l a 成立了传感 器网络研究中心，联合周边大学( 包括u c b 、u s c 和u s r 等) 展开“嵌入式智能 传感器”的研究项目，以求利用传感器网络对我们生活的物理世界实现全方位 的测试与控制，这也是美国国情咨文中有关n g i 最主要的远景规划之一。美国 英特尔公司、微软公司等信息工业界巨头也开始了传感器网络方面的工作，纷 纷设立或启动相应的行动计划【l1 l 。 1 1 3w s n 路由及定位在特定场景下的应用 地下空间是特殊的环境场合，开发与利用地下空间一直是世界各国研究的 4 第1 章引言 热点【1 2 ”】。地下空间不仅是城市轨道交通、城市管网，核电站，地下矿产资源 开发等的重要场所，也是重要的军事基地。特别是随着城市轨道交通的发展及 矿产资源开发的需求，地下空间的结构与安全问题日趋复杂，逐步形成多层网 状局域连通的环境。这些特定的特殊环境，是人们活动的场所，由于其位置与 空间条件的复杂性，其环境条件与安全性的监测一直是共同的难题，目前频发 的矿井安全事故充分说明了这个问题。无线传感网络的出现，为解决这样难题 带来了契机；因此研究无线传感网络在地下空间多层网状局域连通环境条件下 的应用，符合无线传感网络技术发展要求，更具有重要的现实意义【1 4 ，1 5 】。 本课题研究基于多层网状局域连通环境条件下的无线传感网络的网络拓扑 及节点定位机制。对于不同环境条件的无线传感网络，网络拓扑控制对网络性 能影响很大，良好的拓扑结构能提高路由协议效率，为数据融合、时间同步和 节点定位等很多方面提供基础，能减小节点间通信干扰、弥补节点失效的影响， 并有利于保证整个网络的生存。考虑到降低节点成本，提供灵活、可靠的通信， 并提高网络的可扩充性，采用分层结构的路由方案。为了弥补经典l e a c h 路由 “多跳”性能不足，加入了蚂蚁算法进行优化，其基本思想是以“最短路由 作为第一优化准则的前提下，以循环的方式随机选择簇首，将整个网络的能量 负载平均分配到每一个传感器节点中，从而降低网络的能源消耗，提高网络的 生存时间。 实际应用的研究是本课题研究的目标，在地下空间多层网状巷道环境中无 线传感网络的应用主要涉及监测节点定位、移动节点定位和跟踪，这些应用集 中体现了无线传感网络的应用技术特性。在这种环境中，无需测距技术( r a n g e ，f r e e ) 的定位算法性能明显变差。而基于测距的w s n 定位算法相对精度较高， 同时，接收信号强度指示法( r s s i ) 作为基于测距的定位算法，具有通信开销 小，硬件要求低的特点，而在定位计算阶段，极大似然估计法( m l e ) 作为三 边测量法的一种扩展，充分考虑了无线传感器网络的硬件和能耗限制而导致的 误差问题，十分适合w s n 的定位计算。基于以上出发点，重点研究基于r s s i 和 m l e 的w s n 定位算法【l 。 基于多层网状局域连通环境的无线传感网络拓扑以及节点定位机制研究的 成果为地下空间环境监测、节点定位提供一条新的途径，特别对解决矿井安全 生产问题提供了一种新的方法，对促进无线传感网络在地下空间，特别是地下 隧道交通、地下矿产资源开发环境中的应用具有重要意义。 5 第1 章引言 1 2 本文的主要工作及论文结构 本文主要对多层网状局域连通环境条件下的无线传感网络的网络拓扑及节 点定位机制进行研究，着重考虑算法的能量和网络生存时间的限制，设计出了 网络拓扑及路由方案( l e a c h a n t ) 。同时，给出了考虑信号衰减和建筑材料 的w s n 节点的数学模型，使用改进的r s s i 和m l e 进行定位算法的实现。最后 将改进前后的路由方案和定位算法性能进行了比较。具体内容安排如下： 第1 章：引言。主要介绍了无线传感器网络发展现状和特点，重点分析了 无线传感器网络路由技术和节点定位技术的特点，及其在特定应用场景下的应 用。 第2 章：w s n 路由及节点定位。w s n 拓扑控制的关键技术包括：建立适应 特定拓扑结构的路由方案以及节点定位问题。本章描述了关键技术的原理及发 展情况，并归纳了这两类技术的分类和算法特点。 第3 章：多层网状局域连通环境下的路由算法的设计。本章首先介绍了多 层网状局域连通环境对路由算法的影响，一次为设计原点，设计出以经典路由 l e a c h 算法为基础，结合a n t 优化算法以解决路由的水平连通性和垂直连通 性特点的l e a c h a n t 路由方案。 第4 章：多层网状局域连通环境下的节点定位算法。本章主要从特点环境 节点传播模型和覆盖方式入手，对r s s i 和m l e 定位算法进行改进。结合迭代 思想以及连通节点的设立解决了静态节点以及动态节点三维定位的问题。 第5 章：多层网状局域连通环境路由及定位算法仿真与仿真结果分析。在 n s 2 仿真平台上，以网络生存时间、网络数据传输总量和能量消耗为收集指标， 采用层次分析方法，建立合理分析模型，对以经典的l e a c h 算法和传统节点定 位算法与l e a c h a n t 网络拓扑及路由方案和改进后的定位算法性能进行了比 较。 第6 章：结论与展望。总结全文工作，展望进一步的研究。 6 第2 章w s n 路由及节点定位 第2 章w s n 路由及节点定位 2 1w s n 网络路由算法 2 1 1w s n 路由算法的分类 传感器网络中有两种类型的节点，普通节点和s i n k 节点。普通节点散布在 传感区域内每个节点都可以采集数据并将数据发送回s i n k 。为了将数据发送到 s i n k ，需要很多中间节点转发数据包以创建一条多跳路径，路由协议的作用就是 让各节点找到并形成这样一条路径。 经过各国研究人员多年的努力，传感器网络路由协议算法己有相当多的积 淀，按照网络结构路由协议算法划分成平面路由、层次化路由和基于位置信息 的路由三大类别瞄吲。 1 平面路由协议 在平面多跳无线传感器网络中，平面路由协议通常要求每个节点扮演相同 角色，多个传感器节点协同执行数据采集任务。这种情况下产生了以数据为中 心的路由方法：r p s i n k 节点对某一特定区域发送查询指令，等待该区域内的传 感器节点返回采集的数据。由于数据通过查询请求而产生，所以基于属性命名 方法对描述数据特性是必要的手段。以数据为中心的路由策略研究表明：通过 多节点协同操作和消除冗余数据可以节约能量，例如：s p i n t l 6 1 ( s e n s o r p r o t o c o l f o ri n f o r m a t i o nv i an e g o t i a t i o n ) 和定向扩散( d d ：d i r e c t e dd i f f u s i o n ) 【1 7 】。这两种 协议推动了其它以数据为中心的路由协议的设计工作。 s p i n 协议类假定网络中所有节点都是潜在的s i n k 节点，每一个节点可给网 络中的其它节点传播信息。这支持用户查询某一节点即可获得所需的信息。s p i n 协议类利用相邻节点拥有类似数据的特点，所以只需要发送其它节点不拥有的 数据。此外，s p i n 协议类还运用数据协商策略和资源自适应算法。s p i n 协议类 优点之一在于将网络拓扑动态性这一复杂问题简化处理，节点不需保存全局拓 扑信息，只需了解并保存其单跳邻居节点的路由信息，所以保存的信息量少， 拓扑变化不会引起路由数据新的开销；优点之二在于s p i n 协议类比扩散法节约 更多能量，元数据协商机制可以消除大量冗余信息。然而，s p i n 协议类的数据 广播机制不能保证数据传播到目标节点。 7 第2 章w s n 路由及节点定位 定向扩散作为一种以数据为中心和应用感知的通信模型，要求传感器节点 产生的所有数据均以属性值对命名。其主要思想是通过将来自不同源节点的数 据聚集再重新路由达到消除冗余和最大程度降低数据传输量的目的，因而，可 节约网络能量和延长系统寿命。不像传统的端对端路由协议，d c 路由策略能找 到从多个源节点到单一目标节点的路径，并进行网内聚合冗余数据的操作。 运行定向扩散协议的所有传感器节点都是应用感知的，采用以经验为根据 选择路径和缓冲技术以及网内处理数据方法支持数据扩散，可以减少数据传输 量，节约能量。缓冲技术可提高效率、健壮性和多节点协商的伸缩性，是数据 扩散模型的精髓。定向扩散通信模型的另一用途是自主传播传感器网络某一区 域的重要事件。这类信息搜索方式仅适用于持续不变的查询。这对一次性查询 服务不适用，因为不值得仅仅为这一次查询而建立查询梯度。 运用于定向扩散通信模型的数据聚集方法性能受诸多因素影响：网络中源 节点位置，源节点个数和网络通信拓扑结构。另外，定向扩散协议中所有通信 是邻居节点之间进行的，每个节点具备执行数据聚集和缓存的能力。相对s p i n 协议而言，定向扩散协议在移动应用环境中适应能力较弱。此外，定向扩散通 信模型可能不适用于要求持续给s i n k 节点发送数据的应用，即可能不适用于连 续流数据传输模型应用。而且，查询和数据匹配工作可能需要额外的开销。 2 层次化路由协议 层次化或聚类路由策略，最早在有线网络中提出，是一种扩展性好和通信 效率高的路由技术。因此，层次化路由概念也适用于传感器网络实现高能效的 路由技术。在层次化结构中，高能量传感器节点用于处理和发送信息，而低能 量节点用于执行对监控对象周围的数据采集工作。这意味着创建簇和为簇头节 点分配特定任务可为系统扩展性、寿命和能效贡献极大好处。层次化路由通过 执行数据聚集和融合减少传输至u s i n k 节点的数据量，降低簇内各节点能耗，是 一种有效改善能量效率的解决方法。层次化路由主要由两个层次构成：一个层 次用于创建簇，选择簇头节点，另一个层次用于聚集和处理数据，路由数据。 l e a c h ( l o we 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 ) 路由协议是一种采用分布 式簇形成技术的分层路由协议【”】。l e a c h 随机选择若干传感器节点充当簇头节点 ( c h s ，c l u s t e r h e a d s ) ，让所有节点轮流充当簇头节点以均匀承担能量开销。 在l e a c h 协议中，簇头节点将隶属于该簇的所有非簇头节点( n o n c h s ，n o n c l u s e t e r h e a d s ) 采集的数据进行聚集处理，然后将聚集后的数据包发送到s i n k 8 第2 章w s n 路由及节点定位 节点减少传输数据量。l e a c h 协议运用t d m a c d m a 的m a c 协议减少簇间和簇内通信 碰撞问题。然而，由于数据聚集是集中的而且是周期性执行的，所以，这个协 议适用于持续性监测的传感器网络应用中。一个用户可能并不要求马上获得所 需的所有数据，所以，在这种情况下，周期性数据传输除可能耗尽节点有限的 能量外，是没有必要的做法。经过一定时间时隔后，簇头角色须随机轮换以便 传感器网络各节点的能耗均匀。基于w h e i n z e h n a n 提出的仿真模型计算得出， 仅需要节点总数的5 充当簇头节剧1 8 】。l e a c h 协议操作分成两个阶段：聚簇阶段 ( s e t u pp h a s e ) 和稳定状态阶段( s t e a d ys t a t ep h a s e ) 。在聚簇阶段，建立簇并 且选定簇头节点。在稳定状态阶段，才实际发生数据传输至u s i n k 节点的现象。 为了使能耗最小化稳定状态阶段持续的时间比聚簇阶段长。聚簇阶段和就绪阶 段所持续的时间总和称为一轮。这种方式能满足传感器网络的可扩展性，有效 的维持传感节点的能量消耗，从而延长网络生命周期。 3 基于地理信息的路由协议 这类路由协议，传感器节点依靠位置信息进行寻址。邻居节点间的距离可 根据到来的信号强度进行估算。邻居节点的相对坐标通过节点间信息交换来获 得。换句话说，如果节点装配了小型低功率g p s 接收器，节点利用g p s 通过直接 与卫星通信可得到节点位置信息。为节约能量，若无状况出现，一些基于位置 信息的策略要求节点进入睡眠状态。让尽可能多的节点睡眠，可节约更多的网 络能量。g a f 8 】( g e o g r a p h i ca d a p t i v ef i d e l i t y ) 算法是一种为移动a dh o c 网络 设计的能量感知的基于位置的路由算法，同样对传感器网络也是适用的。该算 法思想是网络覆盖范围首先被划分成若干个固定区域，形成一个虚拟网格：在 每个区域内，节点彼此协同充当不同角色。比如，一个区域内选举产生一个节 点在一段时间内保持清醒，接着其它节点进入睡眠；在该区域这个节点代表其 它节点负责监控和报告数据给s i n k 节点。所以，g a f 算法在不影响路由可信度水 平的前提下，通过关闭一些网络中不必要的节点来保护能量。每个节点运用g p s 引导的位置信息将自身与虚拟网格中的一点相关联。与网格中同一点相关联的 这些节点按照数据包路由成本被看作是等效的。利用这种等效性，可让特定网 格区域内的一些节点处于睡眠状态来节约能量。因此，g a f 算法当节点数据增多 时可有效增加网络寿命。 9 第2 章w s n 路由及节点定位 2 1 2w s n 路由算法的特点 目前常见的无线网络包括移动通信网、无线局域网、蓝牙网络、a dh o c 网 络等，与这些网络相比，无线传感器网络具有以下特点。 ( 1 ) 硬件资源有限：节点由于受价格、体积和功耗的限制，其计算能力、 程序空间和内存空间比普通的计算机功能要弱很多。这一点决定了在节点操作 系统设计中，协议层次不能太复杂。 ( 2 ) 电源容量有限：网络节点由电池供电，电池的容量一般不大。因此在 传感器网络设计过程中，任何技术和协议的使用都要以节能为前提。从为了减 少冗余的通信，局部算法有很大优势，它只通过网络中局部节点的信息交互来 达到全局的最优通信。 ( 3 ) 无中心：无线传感器网络中没有严格的控制中心，所有结点地位平等， 是一个对等式网络。结点可以随时加入或离开网络，任何结点的故障不会影响 整个网络的运行，具有很强的抗毁性。 ( 4 ) 自组织：网络的布设和展开无需依赖于任何预设的网络设施，节点通 过分层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组 成一个独立的网络。 ( 5 ) 多跳路由：网络中节点通信距离有限，一般在几百米范围内，节点只 能与它的邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信，则 需要通过中间节点进行路由。 ( 6 ) 动态拓扑：无线传感器网络是一个动态的网络，节点可以随处移动： 一个节点可能会因为电池能量耗尽或其他故障，退出网络运行；一个节点也可 能由于工作的需要而被添加到网络中。这些都会使网络的拓扑结构随时发生变 化，因此网络应该具有动态拓扑组织功能。 ( 7 ) 节点数量众多，分布密集：为了对一个区域执行监测任务，往往有成 千上万传感器节点空投到该区域。传感器节点分布非常密集，利用节点之间高 度连接性来保证系统的容错性和抗毁性。 正是基于以上特点，从路由的角度看，w s n 网络路由有其自身的特殊性，既 不同于传统i n t n e t 网络，又不同于a dh o c 网络。 与传统的i n t e r n e t 相比，w s n 属于无线接入网络，远离核心网络的中心，他 的体系结构、编址方法和通信协议不同于i n t e r n e t ，w s n 功能上实现的是传感器 到数据处理中心的数据采集，路由协议面向多到一的数据流和一到多的控制流， 1 0 第2 苹w s n 路由及节点定位 而非任意源一目的对之间的数据传输；传输过程中普遍采用数据融合方式，其 路由以数据而非报文为中心；节点的移动性较低，但传感器节点的工作模式( 正 常工作状态与休眠状态的切换) 使得网络拓扑表现出很强的时变性，传统的有 线网络的路由协议很难适应这种高拓扑变化，传统网络的路由协议在交互路由 控制信息以及构建自身路由表的过程需要大量的路由开销，这些开销一般都基 于实时广播的路由更新报文以及h e l l o 报文，并在一定程度上使得某节点的故障 失效信息对全网通告，在高拓扑变化的w s n 中，这种交互的控制开销是不可想象 的，即使通过传统的路由表方式建立了传感数据的传输路径，但由于网络拓扑 的快速改变，使得刚刚工作付诸东流，所以从路由开销的角度讲，传统i n t e r n e t 的路由应用在能量受限的无线传感器网络中是不可行的。 m a n e t ( m o b i l ea d h o cn e t w o r k ) 工作组如今对a dh o c 网络提出的路由算 法多达2 0 多种，根据路由的发起和维护方式划分，主要可以分为先应式路由协 议和反应式路由协议。前者每个节点必须预先发现并维护到达网络内其它节点 的最佳路径，网络中每个节点的变化都会引起所有节点进行全网范围内的路由 调整。节点需要通信时，从预先获得的路由表中查找到达目的节点的路径，并 使用该路径转发数据报文。后者是一种只有需要时才查找路由的路由选择方式。 节点并不保存及时准确的路由信息，当源节点要向目的节点发送报文时，才发 起一个路由发现过程获得到目的节点的最佳路径，并使用该路径转发分组。 与a dh o c 路由技术相比，w s n 路由也具有其独特性。首先表现在w s n 网络旨 在收集信息，其节点数量可以高出m a n e t 网络节点几个数量集，而m a n e t 则倾向 于分布式计算和端到端通信，且p w s n 网络在节点密度和规模上要大于m a n e t 网络， 当然w s n 节点要比m a n e t 移动节点廉价，便于大规模布网。其次，w s n 节点更注重 节点之间的协调，单个节点的重要性并不突出，单个节点在整个网络中不像 m a n e t 网络中需要进行唯一地址标识。在能量耗费方面，w s n 网络有更加严格的 要求，而m a n e t 节点在一定程度上可以再次充电，相对来说，能量限制方面要宽 松一些。再者，从数据提交和转发的角度考虑，w s n 网络结构一般都较为简单， 整个网络数据转发就是一个传感区域至l j s i n k 节点或基站的数据提交过程，以及 由s i n k 节点到传感器区域的数据控制过程，而m a n e t 网络更多的体现在节点之间 的互相通信上，数据流并没有w s n 网络那么规则。还有就是w s n 中的大部分节点 不像传统a dh o c 网络中的节点一样快速移动，因此没有必要花费很大的代价频 繁地更新路由表信息；中间节点上与具体应用相关的数据处理、融合和缓存也 第2 章w s n 路由及：1 了点定位 显得很有必要。在密集分布的w s n 网络中，相邻节点问的距离非常短，低功耗的 多跳通信模式节省功耗，同时增加了通信的隐蔽性，也避免了长距离的无线通 信易受外界噪声干扰的影响，这些独特的要求和制约因素为传感器网络的研究 提出了新的技术问题，n j a dh o c 网络所研究的针对高速移动情况下引起网络拓 扑变化的需求驱动式路由不完全适合w s n 的网络状况，但其反应式路由协议的研 究对无线传感器网络来说具有很强的借鉴意义，设计有效的策略延长网络的生 命周期成为w s n 网络的核心问题。 2 1 3m l m l c 环境下w s n 路由算法分析 无线传感网络一出现就受到的广泛关注，是源于其可能及潜在的巨大应用 价值，特别是针对特殊场合的应用，而且从目前的研究成果也同益证明其良好 的应用前景。 随着城市对空间资源利用力度的加大，地下空间不仅被用于地下矿产资源 开发，更是城市轨道交通、城市管网，核电站等新型生活应用的重要场所，同 时也是重要的军事基地。地下空间的结构与安全问题将日趋复杂，如城市地铁 的建设发展，每条独立的地铁隧道呈环状连通，而隧道与隧道之间又有部分交 叠区域连通，这使得地下形成多层网状交通体系；同时矿产资源的开发，更是 使地下空间中巷道交纵阡陌、错综复杂。这些特定的特殊环境，由于其位置与 空间条件的复杂性，其环境条件与安全性的监测一直是共同的难题，目前频发 的安全事故充分说明了这个问题。无线传感网络的出现，为解决这样难题带来 了契机；因此研究w s n 在地下空间中多层网状局域连通( m l m l c ， m u i l i l a y e r - m a s h e dl o c a l c o n n e c t e d ) 环境下的应用，符合无线传感网络技术发展 要求，更具有重要的现实意义，是目前我国国民经济与社会发展中迫切需要解 决的关键科技问题，努力使适应特殊环境条件、具有重要应用价值的无线传感 网络理论与技术能应用到地下军事、交通及矿井环境与安全生产等领域，对作 业环境和作业人员进行有效的监测和管理，为保证安全生产、降低频发的安全 事故起到的重要作用，是研究工作者的责任使然。 基于上述应用环境的特点及其与现有网络的区别，导致己有w s n 网络中的 许多技术并不能直接得到应用，m l m l c 环境下的路由方案将会遇到以下的特点 和挑战： ( 1 ) 由于地下环境是一个相对密闭的空间，四周的地层和岩层对电磁波损 1 2 第2 章w s n 路由及节点定位 耗阻碍了电磁波的传播，地下空间交通或矿井环境的特殊性在于其局域性，即 可视空间( 高频电磁波传播空间) 是局部的、环状连接成网的、多层结构的， 在此环境下的路由与平面路由的根本区别是如何分析设计路由方案的基点； ( 2 ) 基于m l m l c 环境的无线传感网络既有平面局部连通分布，也有垂向 分层分布，形成多层网状连通的空间分布，而现有的w s n 网络路由协议多是基 于平面地理环境的，如何将平面路由机制扩展到三维立体空间，是路由算法实 现过程中一个不可回避的障碍； ( 3 ) 确定路由设计的基准方案之后，选择什么样的优化算法，能够对该路 由方案进行以“最短路由”、“能量有限”等准则下进行路