基于分簇的无线传感器网络拓扑维护算法研究毕业论文.doc

目录基于分簇的无线传感器网络拓扑维护算法研究毕业论文目 录原创性声明I关于论文使用授权的说明I摘要IIAbstractIII第1章 绪论11.1 课题的研究背景、目的及意义11.2 课题的研究现状21.3无线传感器网络简介31.3.1 无线传感器网络体系31.3.2 无线传感器网络的重要技术51.3.3 无线传感器网络在云南省跨境区域的应用61.4 论文的主要研究内容7第2章 无线传感器网络拓扑控制技术概述92.1 拓扑控制技术的定义92.2拓扑控制技术的意义92.3 一些拓扑控制算法综述102.3.1 算法简介102.3.2 网络寿命（生存时间）的定义202.4 本章小结21第3章 基于同心圆-象限划分的簇头拓扑维护算法223.1同心圆-象限的数学模型223.2基于同心圆-四象限划分的簇头拓扑维护算法253.2.1算法设计253.2.2算法的实现273.3 模拟实验分析283.3.1实验场景设计283.3.2结果的实现283.4 本章小结31第4章 基于多跳中继转发的簇头拓扑维护算法324.1问题的提出324.2基于距离的节点能耗模型334.3 数据多跳中继转发的簇头维护算法344.3.1算法的设计354.3.2算法的实现364.4 模拟实验分析384.4.1实验场景设计384.4.2结果的实现394.5 本章小结44第5章总结与展望455.1总结455.2展望46参考文献47在学期间发表的学术成果及获奖情况51致谢52 I第1章绪论第1章 绪论1.1 课题的研究背景、目的及意义信息的获取和处理是人类认识世界的两个重要方面。随着当今社会生产力的高速发展，以信息技术为代表的高科技技术也在不断拓展。科技的进步，使人类的许多想法成为可能，计算机系统的出现增强了人类处理信息的能力, 而无线传感器网络则大大拓展了人类获取信息的能力。因此，无线传感器网络成为了当前学术界研究的热点领域。无线传感器网络集成了许多目前最新的研究成果，比如传感器节点用到的微机电系统和嵌入式系统开发技术，信息传输阶段用到的分布式信息处理技术和以IEEE802.15.4协议为代表的无线通信技术等，这些应用于无线传感器网络的诸多技术都是各自领域的最新成果。另外，近来提出的物联网和泛在网等概念、理论，在信息的获取上也依赖于无线传感器网络节点快速、高效、广泛的获取能力，因此，物联网的发展带动了无线传感器网络的发展，而无线传感器网络技术的研究也必将推动物联网的研究发展达到新的高度。无线传感器网络（WSN，wireless sensor network）是一种特殊的Ad hoc网络，由部署在监测区域内大量的低成本、体积小、多功能的传感器节点通过自组织方式组成，通过无线通信方式形成一种多跳的、自组织的网络。其主要目的是通过高度集成化的微型传感器联合协作地实现对监测区域进行实时监听侦测、感知和采集受控对象的状态数据，如温度、光强度、噪声、压力、运动物体大小、速度和方向等，这些数据通过无线通信的方式被发送，并以自组织、多跳的通信传输方式传送到用户终端。无线传感器网络系统具有成本低、易部署、自组织、管理方便、可靠性高等特点，使其在国防军事、环境监测和预报、交通管理、智能家居、建筑物状态监控、医疗卫生、制造业、工农业控制等诸多领域有着广阔的应用前景和很高的应用价值。无线传感器网络在各社会方面如此巨大的应用价值，使得其发展将会给人类社会带来长久的深远影响，引起了世界许多国家众多领域极大的关注。美国商业周刊和MIT技术评论在预测未来技术发展报告中，分别将无线传感器网络列为21世纪最有影响力的21项技术和改变世界的10大技术之一1-2。美国国防部和空军、海军等军事部门对传感器网络给予了高度重视，提出C4KISR3计划，把传感器网络作为一个重要研究领域，设立了一系列研究项目。2005 年，欧洲第 1 届专业传感器网络会议在德国柏林召开。同年，Association for Computing Machinery（ACM，美国计算机协会） 增设传感器网络研究专刊TOSN (transactions on sensor networks)。我国颁布的国家中长期科学与技术发展规划纲要（2006年-2020年）4中，为信息领域确定了三个前沿方向，其中智能感知技术和自组织网络技术都直接与WSN的研究相关。因此，无线传感器网络技术的发展和广泛应用，必将对人类的社会生产、生活带来极大的变革，对科技产业产生巨大的推动作用，甚至引发新的产业革命。无线传感器网络巨大应用前景为科学研究者们带来了一个新的研究方向，提出了新的技术挑战。在无线传感器网络研究领域中，网络路由、拓扑控制、数据融合与管理、时间同步、节点定位等成为研究的重点。其中拓扑控制是无线传感器网络的一项关键技术，拓扑控制技术对网络的其他性能有着很大的影响，同时，拓扑控制技术也是无线传感器网络领域许多其他相关研究课题的支撑技术之一。本研究课题以无线传感器网络的拓扑控制为背景，对现有的WSN拓扑维护技术进行总结，从新的视角设计了用于拓扑维护的拓扑控制算法，提高无线传感器网络的容错性，减少通信节点之间的相互干扰，提高网络通信效率以及延长网络的生命周期。通过此算法，可以以较小的开销恢复中断的节点通信和网络通信，有效的提高网络通信质量、减小传输延时，保证数据成功发送率的情况下，减小能量的损耗。本课题来自于国家民委基金项目“基于跨层设计的无线传感器网络拓扑控制技术研究（10YN02）”、云南省教育厅科学研究基金重大专项项目“云南跨境区域复杂环境监测无线传感器网络拓扑控制与组网技术研究(ZD2011009)”。1.2 课题的研究现状由于无线传感器网络自身节点携带能量有限、网络拓扑易变化、随机部署、通信环境复杂等特点决定了拓扑控制技术在无线传感器网络中的重要性。近年来，国内外研究学者在拓扑控制方面做了大量的工作和研究。以麻省理工学院，加州大学伯克利分校，加州大学洛杉矶分校，伊利诺斯大学为代表的国外著名高校，在无线传感器网络拓扑控制研究方面已经取得了初步的研究成果。从2005年开始，国家自然科学基金委员会每年都有对无线传感器网络拓扑控制技术研究的项目资助。随着无线传感器网络应用的进一步深入，拓扑控制技术也应该进行下一步的研究。根据维基百科5给的定义，拓扑控制可分为拓扑构建和拓扑维护。拓扑构建指的是网络拓扑初始化，是拓扑从无到有的过程，拓扑维护指的是网络拓扑建立后，优化网络拓扑，是拓扑从有到好的过程。通过查阅大量文献、资料的情况来看，国内外对无线传感器网络拓扑控制技术的研究主要集中在拓扑初始构建方面，大部分的初始拓扑建立之后，并没有考虑诸如节点失效或者网络扩建等动态拓扑情况，无线传感器网络拓扑控制维护阶段的方面的研究相对少一点。但是拓扑维护作为组成拓扑控制的两个子环节之一，且拓扑维护是衔接于初始拓扑的后续发展，这些都足以说明拓扑维护对于网络的整个拓扑控制的建立有着十分重要的意义。现有的拓扑控制技术按照研究方向可以分为三大类：基于功率拓扑控制、基于层次型拓扑控制和休眠调度机制。目前的拓扑控制的研究已取得了较大进展，提出了许多经典算法，现有的拓扑控制大部分研究都是建立在这些经典算法之上。拓扑维护技术也是在这些典型的拓扑控制算法基础上进行发展和提高的，如具有k（k2）连通的拓扑控制容错算法FLSS/GLSS6、k-CBTC7、GAFT/LAFT8等，都具有容错功能，它们的产生是为了适应无线传感器网络中节点容易失效的这个特性；还有的拓扑恢复算法可以基于节点收集的信息对失效节点的网络拓扑结构进行局部修复或者全局修复，如LMST9算法构造的单连通拓扑结构，就具有潜在的局部恢复受损拓扑结构的能力。但是，目前拓扑维护算法的研究还很不充分，特别是针对拓扑控制的拓扑维护算法，还需要做大量的相关研究。1.3无线传感器网络简介1.3.1 无线传感器网络体系通常来说，传感器网络系统包括：传感器节点（Sensor nodes），基站节点（Base station node，也称汇聚节点：Sink node）和管理中心。无线传感器网络典型的体系结构如图1.1所示。通过人工或者自动化等方式，将大量传感器节点随机撒布在目标区域内或者附近，以自组织的方式构成无线通信网络。传感器节点采集到的数据在传递过程中可能被多个节点的处理，并直接或者间接传递到BS节点，最后通过外部网络如卫星、互联网或者移动通信网络等方式传递给管理中心。图1.1 无线传感器网络典型体系结构图1.2 无线传感器体系结构普通传感器节点通常是一个微型的嵌入式系统，通过电池供电，能量有限，信息处理能力、数据存储能力和通信能力相对较弱。传感器节点又担当着终端和路由的双重角色，除了监测、采集和处理监测对象的信息数据外，还可能要负责对其他节点传递来的数据进行转发、信息融合、存储等功能。所以针对不同的应用需求，传感器节点的设计也不尽相同，一般，传感器节点主要包括传感器模块、处理器模块、无线通信模块和能量供应模块四个部分，如图1.2所示10。依据特殊要求，传感器节点还可能包括定位、能量补给或移动等模块。1.3.2 无线传感器网络的重要技术不同于传统网络，由于无线传感器网络自身能量有限、应用环境复杂且动态变化、节点部署密集，以及对数据传递要求实时性、可靠性等特点，对无线传感器网络的研究提出了新的挑战。目前，无线传感器网络的关键技术主要有：定位技术、拓扑控制技术、数据融合技术、路由协议、网络安全、适用于无线传感器网络的软件或者硬件设计等。（1） 定位技术定位是指确定传感器节点的相对位置或绝对位置。传感器节点一般是由人工或者机械随机撒布在监测区域内的，所以其位置是未知的。但是对于大多数传感网应用来说，不知道节点位置信息的监测数据是没有意义的。节点只有明确自身的位置才能向管理者准确传递信息详细说明“在什么区域发生了什么事件”。了解节点位置信息还可以为拓扑控制的实现提供信息支持，提高路由效率，向管理者报告网络的覆盖情况，实现网络的负载均衡以及网络拓扑的自配置。而人工在确定无线传感器网络的位置或者给节点安装GPS等节点位置接收器会受到成本、功耗、可扩展性、复杂度等问题的限制，在某些场合可能无法实现，所以采取一定的方法机制或者算法实现节点定位是必要的。（2） 拓扑控制技术拓扑控制是指在维持拓扑全局优化的前提下，通过建立合适的相邻关系的方法构建网络拓扑关系，达到维持网络良好的通信能力、延长网络生命周期、提高网络吞吐量、降低网络干扰、节约节点资源的目的。它是解决网络连通性、提高连通可靠性、增强容错性以及节省能耗的最有效方法之一。（3） 数据融合技术无线传感器网络是以数据为中心且面向特定应用的，在许多应用中，管理者只关心监测的结果，不需要大量的原始数据，如何有效的提取有效的信息给管理者非常重要，数据融合技术是解决这一问题的重要手段。数据融合技术还可以减少传输的数据量，达到节约能耗的目的。在传感网中，数据融合技术可以与网络中各个协议层进行结合，只有面向应用需求设计针对性强的数据融合方法，才能最大限度的获益11。（4） 路由协议能耗问题是无线传感器网络设计考虑的重点，其很多特性决定了传统无线网络的路由协议在无线传感器网络中是不适用的。传感器网络是一种多跳的网络，如何寻找源节点和目的节点间的最优路径，将数据分组沿此路径正确转发是这类网络最重要的问题之一。因此，路由协议问题也是无线传感器网络的热点问题之一。用于无线传感网络的路由协议可分为:基于查询的路由、地理位置路由、能量感知路由和可靠路由协议。（5） 网络安全无线传感器网络是通过无线通信信道进行数据发送转发接收的，因此网络安全问题是一个非常重要的问题。无线传感器网络的主要安全问题包括：数据本身的可靠性、数据在节点间融合的高效性以及数据发送转发接收的安全性。为了保证任务的机密布置和任务执行结果的安全传递和融合，无线传感器网络需要实现一些最基本的安全机制：如数据加密特性，点到点的消息认证、完整性鉴别、新鲜性，数据认证广播以及安全管理12。综上所述，无线传感器网络研究中有着大量丰富的挑战。对于研究者来说，彻底解决所有问题是很难实现的，应该针对某个或者某些特定条件或问题进行研究，改善无线传感器网络性能。本课题即是针对无线传感器网络中拓扑控制技术的问题而展开的。1.3.3 无线传感器网络在云南省跨境区域的应用无线传感器网络（wireless sensor networks, WSN）是近十年来发展迅速的一种新型网络体系，由于其布置灵活、自组织、成本低廉、实时性强、免维护等特点，在工业控制、环境监测、减灾防灾、物流、医疗、国防等领域得到了广泛的应用，学术界对其体系结构、通信协议、电路设计、操作系统等关键技术的研究升温。若将其作为对边境地区幅员广阔、多民族人口聚集、越境通道分散、地理环境复杂、电磁波越界严重条件下的无线电信号监测的技术手段，部署于边境重点区域，就可为现有的造价高、数量有限、覆盖有限的监测网提供有效补充，为国家制定政策、避免国际纠纷、打击非法活动、维护民族团结和边疆稳定、主张国家主权提供基础数据和证据支持。云南省跨境地区的生态环境有四个重要特征：（一）信息量巨大。该地带是一个长度上千公里（从西到南）、宽度数十公里（从边境线向内、向外至少各跨20km），自然环境类型十分复杂，可以说其生态环境信息为海量信息。（二）空间信息上的多尺度和属性信息上的多层面叠置特征。具体讲，该地带的空间信息在宏观上受地带性分异规律的影响，从北到南跨越亚热带常绿阔叶林带、热带季雨林、热带雨林带等多个自然带，带有纬度地带性和经度地带性的烙印；在中观上又受非地带性因素影响，整个地区涵盖了山地、谷地、盆地、高原等多种地形区，多条国际河流出境口均分布在此地带上，因此具有中尺度的环境分异和演变规律；在微观上，该地带在阴坡与阳坡、谷底与坡地、高海拔与低海拔等不同情形的对比中，存在着多种多样的小尺度生态系统的变化。 在属性信息方面，该地带存在着从大气-植被-水域-土壤-地质体等多层面的属性叠加特征。（三）该地带的生态环境受自然和人为活动两种因素的综合影响，动态时效性十分明显。（四）该地带生态环境各要素之间相互关联，往往互为因果，错综复杂13。对于此地区的环境监测，往往需要在大面积监测区域布撒大量的节点，对此环境中各个样本信息进行实时监测，为此地区的生态研究提供数据支撑；而对于监测区域中数据的异常变化，环境的某个特征的改变可能会引起的灾害，因此对数据的实时监控和传递是很重要的。一个网络拓扑以及拓扑机制对网络的影响是非常大的，对于大规模网络的拓扑研究有着重要的意义。由于传感器节点的能量供给受限，计算能力有限，通信信号强度较弱，受周边环境的影响很大，如阻挡、吸收、反射、折射、多径效应等14。所以，跨境地区的复杂地形和复杂电磁环境，非常容易导致网络的拓扑发生变化，如网络中某个或者某些节点的通讯受到干扰或者破坏进而不能响应通信时，如何恢复拓扑或者重建新的拓扑并恢复网络通信显得尤为重要。1.4 论文的主要研究内容本文以无线传感器网络的理论为基础，阅读了国内外关于无线传感器网络的相关文献，特别是深入学习了关于拓扑控制方面的理论技术，概述了无线传感网络的体系结构、网络特点、关键技术和有关应用。然后有针对性的研究了无线传感器网络拓扑控制技术，以拓扑维护作为拓扑控制技术的主要切入点，提出了层次型拓扑控制技术中簇头失效的解决方案。本文主要研究内容如下：（1） 对现有的无线传感器网络的拓扑控制技术和拓扑维护算法进行研究和分类。（2） 根据地理位置的网格划分思想，提出用同心圆和象限划分的环弧空间的簇头拓扑维护算法。（3） 根据簇头节点与汇聚节点之间的多跳中继转发数据的思想，提出了一种基于多跳中继转发的簇头拓扑维护算法。（4） 分别对提出的算法进行了理论分析和模拟仿真数据上的比较分析，得出相应的结论。论文共分五章，结构安排如下：第一章， 阐述了本课题的研究目的以及研究意义，分析了国内外研究现状。主要介绍了无线传感网络的概念、特点，特别针对无线传感器网络的体系结构、节点结构以及无线传感器网络关键技术和国内外无线传感器网络典型应用做了较详细的介绍。第二章， 概述了拓扑控制的定义，研究了现有的拓扑控制算法，并且对近来新提出的拓扑控制技术进行了综述，对比总结了目前文献中提出的关于网络生命周期的定义。第三章， 提出基于同心圆和区域象限划分环弧空间的簇头拓扑维护算法。本章考虑的是在簇头失效的拓扑维护阶段之后，根据环分象限空间的思想对簇头进行拓扑维护，并对算法在不同仿真场景下进行了模拟仿真分析。第四章， 提出基于多跳中继转发的簇头拓扑维护算法。基于簇头和汇聚节点之间路径模型和基于距离的能量消耗模型，得出最佳中继转发次数，并以节点剩余能量和最佳转发次数为基础构建簇头选举的权值公式，然后对算法实施了模拟仿真，并进行了实验性能分析。第五章， 对全文的工作进行了回顾和总结，对未来的研究工作进行了展望。51第2章无线传感器网络拓扑控制技术概述第2章 无线传感器网络拓扑控制技术概述 网络拓扑（network topology）是指网络中各成员之间特定的物理的即真实的、或逻辑的即虚拟的排列方式5。一般来说网络拓扑包括以下七种方式：点对点型、总线型、星型、环型、Mesh型、树型、链状、混合型。2.1 拓扑控制技术的定义 拓扑控制技术主要是用于无线Ad hoc网络和无线传感器网络中的14，是指在满足网络的连通度和覆盖度前提下，通过调节传感器节点的发射功率和建立合适的相邻关系的方法构建网络拓扑关系来去除节点之间冗余的通信链路，或者选择骨干网节点让大量冗余节点进入休眠，从而形成一个数据分组转发均衡的优化网络结构10，以维持网络良好的通信能力、延长网络生命周期、提高网络吞吐量、降低网络干扰、节约节点资源为主要目标。2.2拓扑控制技术的意义拓扑控制是无线传感器网络通信和组网的基础，其性能的好坏将直接或者间接影响无线传感器网络其他方面。主要表现在以下几个方面：（1） 节约节点能耗，延长网络生存时间由于传感器网络节点的能量来源的局限性，无线传感器网络设计的首要目标就是节约能耗，通过拓扑控制技术，可以有效的节约能耗，延长网络的生存时间。（2） 保证网络的连通度和覆盖率无线传感器网络的连通覆盖是反应网络的服务质量和服务能力的两个重要指标。网络覆盖一般看作是无线传感器网络监测质量的度量，它直接反映了网络的感知能力；而网络连通体现的则是无线传感器网络数据通信服务的质量。连通是拓扑控制的基本要求，其可以保证数据传输的可靠性。网络的覆盖率是拓扑控制的基本问题，其反映了网络对物理世界“感知”的服务质量。（3） 减少通信干扰，提高通信效率一般来说，为了有效地监测目标场景对象，布置于监测环境中的传感器节点的密度较大。如果节点的通信半径太小，没有办法保证网络的连通，而且对网络的通信的可靠性和网络的可扩展性也会产生不好的影响；如果节点的通信半径过大，节点之间的干扰就会加剧，网络的吞吐量和通信效率降低，同时也会造成节点能量的浪费。因此，需要通过拓扑控制技术的功率控制来解决这一问题。（4） 为路由协议提供基础有人比喻，拓扑控制技术是为网络建立“高速公路”，拓扑建立了以后路由协议则负责“选路”。拓扑控制确定网络中节点之间的关系及节点分担的角色，对数据进行转发，为路由协议奠定基础。（5） 影响数据融合数据融合技术也是无线传感器网络关键技术之一。为传感器网络选择合适的节点对采集来的监测数据进行处理并发给管理者是拓扑控制技术另一工作，可以减少网络不必要的开销和降低通信量。（6） 适应网络的动态拓扑变化无线传感器网络中由于节点的失效或者新节点的加入、网络周围环境变化对节点通信的影响等各方面原因，导致无线传感器网络的拓扑时动态变化的，为了保证网络的正常工作，传感器网络拓扑应具有鲁棒性来适应这种变化。由此可见，无线传感器网络拓扑控制技术在无线传感器网络研究领域具有十分重要的研究意义。2.3 一些拓扑控制算法综述当前，对于拓扑控制的研究主要集中在平面拓扑结构和层次拓扑结构。大部分平面拓扑结构又基于节点的功率控制，所谓功率控制，就是为无线传感器网络的节点选择合适的发射功率和接收功率，即节点的发送功率和接收功率时可调的。在功率控制的研究方向，已经提出了基于同一功率分配拓扑控制算法COMPOW，基于节点度的拓扑控制算法LINT/LILT和LMN/LMA等，基于邻近图近似算法如CBTC、LMST、RNG、DRNG、DLSS等。在层次型拓扑控制的研究方向，主要有LEACH和HEED成簇算法，也有TopDisc和GAF分簇算法。2.3.1 算法简介下面主要介绍分布于两维坐标下的拓扑控制算法。（1）M.Huang S. Chen15等人研究了一种可预测（其随时间演进的网络拓扑可以被推理或者预测）的DTN（delay-toleant network）拓扑控制问题。DTN网络被视为在无线传感器网络的内部连接较弱时的专用网络。算法将随时间演进的网络表示成一个有向的（定向）时空图表，其中包括空间和时间信息。它的拓扑控制目标是从最初的时空图表中建立一个稀疏的拓扑结构，以达到以下两个目的：1超时时仍然能保持网络的连通以及支持任意两个节点间DTN路由；2这个结构的总体成本最小化。图2.1 （a）空间-时间关系响应图；（b）到空间-时间路径（绿色线条）通过空间-时间关系图，可以模拟随着时间演进的网络。如图2.1所示，数据包从到的路径如图所示一个特定的路由，数据包在网络中从到使用4个时隙。在t=0时刻有数据包要发送，在t =2时刻将其传递到，在t =3时刻将其传递到，等等。请注意，在此模型中，只允许一个时隙里的单跳传输。也就是说，假设每个时隙的有足够长的时间来用于一个信息包的传输。例如，无法将数据包发送到通过在一个时隙里。空间-时间关系图容易得到空间和时间网络的拓扑结构的维数。但该模型增加了算法的复杂性（引入了一个新的维数时域），但也增加了更多的路径选择（结合了时间和空间的路径选择方法）。基于空间-时间关系图建立的稀疏结构的拓扑控制算法就是要在时间T内构造一个空间-时间关系图，并使得关系图内的总的路径成本最低化，还要使各个节点在时间T内至少可以通过其他节点中继后能相互通信。文献所提出的两个基于贪婪算法（ULCP和GrdLCP）能在保持超时连通性的同时，可以显著减少网络拓扑结构的总成本。这两种方法都是反复添加一组边的拓扑结构来连接一个或多个的空间-时间关系图中的节点对。第一种方法，增加1对节点来连接最小成本路径，而第二种方法加入了多对节点来连接最小成本路径。后者在理论上可以得到一个近似的拓扑控制问题的最佳解决方案。但是这两个算法的时间复杂度比较高，空间-时间关系图也需要较高的连通度和节点完好性，而且算法在面对不可靠连接和无方向连接时候也没有提出很好的应对方法。（2）Ameer A. Abbasi16等人提出的LeDiR算法一种基于最小变化拓扑结构的修复算法，该算法是一个本地化的分布式算法，充分利用网络中现有的路由发现方法和没有施加任何额外的故障前的通信开销。图2.2 LeDiR算法恢复连接的过程。黑色节点参与到了恢复过程，灰色节点则移动了位置。如图2.2，A10节点失效后，LeDiR算法恢复连接的过程。图a所示为A10节点是一个关键节点，图b所示为A10节点失效后原网络拓扑将断裂成不相连的两部分，黑色节点表示A10节点一跳范围内的邻居节点，图c表示通过算法确定A14为关键节点的邻居集合为最小块，以及A14节点代替失效节点A10的移动位置，图d和图e表示A14节点移动到新位置后，它的子节点根据最短路径应该移动的位置，图f表示节点恢复后新的拓扑图。LeDiR算法的实施步骤如下：（1）故障检测：反应节点定期给邻居节点发送消息，一旦检测到故障节点在附近，就确定失效节点是否为网络连接的关键。如果是网络连接的关键节点则执行SRT(shortest-path routing table) 算法；（2）最小块标识：通过寻找每一个可以与原失效节点直接通信方向上可达的节点邻居集合，选择节点最少的节点集合作为标识块。由于失效的关键节点通常位于两个分布块的最短路径上，所以在排除了失效的关键节点后需要用SRT来确定可达通信节点的集合。（3）更换有故障的节点：可达通信节点的集合确定后，选择离原失效节点最近的节点来代替故障节点，以保证在恢复过程中所有节点移动的距离最短，以及最快的恢复速度和最小开销。（4）移动：确定移动位置后，父节点将通知子节点自己的移动位置，然后子节点计算自己的移动位置，来确保节点之间的通信正常。（3）M.Wawryszczuk17等人提出了一种较具体的网络拓扑控制机制，这种机制在不影响网络连通和覆盖的情况下显著减少了能量消耗。由于网络中的节点主要用来侦测运动物体以及追踪他们的运动轨迹，所以，部署于网络边缘的节点要常常处于活跃状态，而网络内部节点则可以处于休眠状态。而处于活跃状态节点的活跃时间越少，则节点的能量消耗越少。提出了外层节点以节点最大通信距离构成的子外层（external sub-layer）网络拓扑图。处于外层（网络边缘）的节点则在这种机制的调节下，在保证监测任务正常工作的前提下，外层的节点交替进入活跃状态，控制外层节点的能量消耗。同其他作者提出的不同拓扑控制机制进行了比较，并讨论了拓扑控制机制的未来应用。图2.3 子外层（external sub-layer）网络拓扑示意图（4）对于移动WSN，节点分布频繁地变化，使得现有拓扑结构不能够连续保持网络的连通性。为此，Longfei Wen18等人提出了“连接保持”分层拓扑模型（connecting-keeping），该模型是一类基于主干链路（backbone-based）的拓扑方式，其主干网络是基于网络连接度来生成的。这个拓扑结构的核心是将网络分为两层，并形成一个移动无线传感器网络骨干网。上层是骨干网，是整个网络传输数据的基础。下层是由其余的传感器节点组成的普通节点层。骨干网的节点主要分为三种类型的节点，称为簇头节点、网关节点和门户节点。所有普通节点可以与至少与一个簇头节点通信，每个簇头节点至少可以与三跳之内的其他簇头节点通过网关节点和门户节点进行通信。不管移动无线传感器网络节点分布如何变化，可以证明，节点的网络连通性可以保持。以此为基础，提出了路由协议CKBH (Connectivity-Keeping Backbone Hierarchy)。CKBH数据收集方法分为若干轮。在每一轮中，都分为骨干网络建立阶段和数据传输阶段。A.骨干网建立阶段簇头节点，网关节点和门户节点当选为形成作为整个网络的基础骨干网络。B.数据传输阶段在这个阶段，普通节点侦听所有簇头节点的广播信息，并选择最近的簇头节点的进行数据通信。然后，因为所有的簇头节点可以通过网关节点和门户节点彼此通信，所以数据的传输和融合就可以沿着这个骨干网络进行网络中的信息收集。最后，信息被发送到sink节点。仿真实验结果表明，能量消耗在特定的主干网生成算法下也能够明显地减少，且该拓扑方案具有比基于簇（cluster-base ）和链式（chain-based ）拓扑更好的能量有效性。（5）网络断层扫描（Network Tomography）可以作为一种应用来推断有线网络的拓扑结构。而涉及到无线传感器网络，大部分文献提出的拓扑发现方法是基于内部网络节点发送的邻居信息。T. Kontos119等人提出了一种基于收集测量网络中sink节点损耗，来推断无线传感器网络的树型拓扑结构的算法。该方法不依赖于内部网络节点的合作活动，仅通过接收到的传感器读数（被动方式），不用执行网络内的资源密集型任务，就能够推断出所寻找的拓扑结构。在本地信息和本地决策的基础上，该机制提出了一种结合动态资源因素、链路质量、用户行为和用于网络管理的应用程序数据的方法来发现全局拓扑。考虑到其资源的稀缺性。算法可以帮助基于定期的数据收集任务无线传感器网络解决部署问题。算法是完全基于测量接收到的sink节点的信号，从而提供了一个无源拓扑推断方法。具体而言，该算法是首先观察节点的信号衰减方向，然后测量信号衰减度以及找出衰减与节点距离之间的关系，进而揭示出完整的拓扑结构信息。该算法在每一个测量的基础上，逐步揭示出度数越高的树形拓扑结构。该算法的基础概念为节点簇NC（Node Clusters）。NC是包括寻找拓扑的传感器节点的一个子集，但它们之间的关系是未知的。 NC内部是相互连接的，可以表示为一个抽象的树的拓扑结构。直到所有的NC最后成为单独集，NC都将逐渐分开并放置在正确的位置在树中。NC分裂的过程中如图2.4所示，(a)表示分裂之前的树结构，节点4和节点5收到的测量数值较低；(b)表示应用信号衰落后的树形拓扑结构。图2.4 NC分裂过程示意图（6）Ying Zhu20等人引入一个新的拓扑控制问题：协同通信中能量有效的拓扑控制问题，提出的两种拓扑控制算法来建立协同能量检测（Cooperative Energy Spanners），使得每条路径的能量有效性得到了保证。图2.5 协同通信示意图协同通信CC(Cooperative Communication)如图2.5所示：(a)节点在它的协作者，的帮助下与进行通信；(b)连接代表了协同通信。如果一个网络的拓扑结构能够建立起协同能量检测，那当所有可能的直接链接和CC链接都是相通时候，文献20保证有每一对节点之间的路径的能源消耗是最低的，这将有利于网络的拓扑结构的能量高效性。由于只考虑了单跳邻居内协同通信节点。因此，协同通信的拓扑结构的CC链接只有单跳范围内的连接，不是所有的链接都加入到了CC链接中。此外，对于每一对节点vi和vj，如果有多个CC链接，则只保持一个最小成本链接链路的连接。提出的两个算法是贪婪算法。它们之间的主要区别是链接的处理顺序。 第一种算法从原来的拓扑图中贪婪地删除链接(Deleting Links)，而第二算法从原来的拓扑图中贪婪地添加链接(Adding Links).图2.6 两种贪婪算法示意图贪婪算法例子如图2.6，图(a)为建立于CC链接原始的拓扑图，图(b)-(d)用第一种贪婪算法删除链接，图(e)和(f)用第二种算法增加链接。（7）文献21提出一个分布式无死端（dead-end free）拓扑维护协议（DFTM），能在激活节点数量最小化的条件下构建无死端网络，并恢复已经中断的网络通信。为了确保网络中所有节点的能量消耗的均匀分布，DFTM提出了一个全局性的拓扑维护计划，旨在执行一个活动节点切换过程。在这过程中，所有当前活跃和休眠节点将每Tglobal秒转变他们的模式到未定模式。然后汇聚节点随机选择一个节点作为初始节点来构建无死端的拓扑结构。选择初始节点的随机性使得每个节点成为活跃节点的概率都是相同的，也由此来达到功耗均匀分布的目的。图2.7 DFTM算法执行过程图2.7给出了DFTM算法的拓扑结构的控制机制的详细状态图。最初，所有的节点都处于待定模式，即每个节点的最合适的模式尚未确定。过程开始时，随机指定一个节点处于活跃状态，这个节点转换到状态1，并被称为初始节点。在状态1中，所选择的节点（初始节点）转换到活跃模式并进入状态2。初始节点随后发出一条消息并搜索处于没有休眠状态的节点，然后转换到状态3接收回复。一旦未休眠的节点接收到了初始节点发出的消息，它就将自己的当前状态回复给初始节点。而当初始节点的定时器到一定时间，则进入状态图4。初始节点首先将所有已回复的节点添加的其邻居集（NS，neighbor set），然后将那些处于活跃模式节点添加到一个活跃的邻居集（ANS，active neighbor set），并转换到状态5。初始节点从状态5可能转换到状态6或者状态7。如果节点处于ANS中且初始节点不满足LDF条件，则初始节点的状态转换到状态6。否则，转换到状态7。在状态6，初始节点根据活跃节点选择算法从NS节点中选择一个新的活动节点，然后这个节点添加到其ANS中，并使该过程返回到状态5，以验证是否满足的LDF条件。在状态7，已被选择的节点成为活跃节点，且被指定为新的初始节点。然后每个节点都使用其ANS执行上述过程的拓扑构建。同时，由初始节点和其ANS中的节点的Voronoi多边形的垂直平分线之间所包围这些节点在进入睡眠模式。然后，该过程转换到的最终状态，即完成。在局部拓扑维护操作过程中，一些活动节点可能会突然因为节点碰撞，能量耗尽等原因而变得不可达。为了在节点故障时仍保持无死端的拓扑结构，DFTM采用本地拓扑维护操作，当活跃节点失效时以唤醒休眠节点。每个活跃节点都与处于活跃状态的邻居节点周期性地交换消息。当一个节点连续三次都未从一个特定的邻居节点接收到确认消息，则将该邻居节点从ANS中移除。通过仿真进行了一系列的数值模拟，将DFTM的性能与GAF、SPAN这些传统的拓扑维护策略进行了比较。仿真结果显示DFTM显著减少了网络中所需的激活节点数量，从而延长了网络寿命。在大多数的模拟情景中，DFTM也成功地构建了一个无死端拓扑结构。另外，即使不知道传感器的精确位置，DFTM仍然使得报文转发时几乎没有“死端”现象的发生。（8）LEACH算法 low-energy adaptive clustering hierarchy（LEACH）22算法是无线传感器网络中最早提出的一种自适应分簇拓扑算法。其后的大部分分簇拓扑控制算法都是基于它发展而来的。LEACH算法选举簇头的具体过程如下：每个节点产生一个介于0到1之间的随机数，如果这个数小于阈值T(n)，则广播消息通知其他所有节点自己是簇头节点，其他节点则根据接收到的信号的强弱来决定加入哪个簇。在下一轮循环中，若节点已经当选过簇头，则设T(n)为0，这样可以保证节点在之后的若干轮中不会再次当选为簇头。T(n)可表示为：，nG 式2-1，其他其中：P是簇头所在所有节点中所占的比率；r是选举轮数；r mod(1/P)代表这一轮循环中当选过簇头的节点个数；G是这一轮循环中从未当选过簇头的节点集合。从的判决式中可以看出，当选过的簇头节点在接下来的1/P轮循环中将不会再次当选簇头。采用LEACH方法使因能量耗尽而失效的节点 呈随机分布状态，因而与一般静态分簇算法相比，LEACH可以将网络生命周期延长15%。但是LEACH假设所有的节点都能直接与终端节点通讯，采用连续数据发送模式和单跳模式，因此不适用监测面积范围大的应用，而且动态分簇带来了额外的开销。（9）Power-Efficient Gathering in Sensor Information Systems（PEGASIS）23算法是在LEACH算法的基础上改进设计的。PEGASIS的基本思想是为了延长网络的生命周期，节点只需要和它们最近的邻居进行通信。节点与汇聚节点间的通信过程是轮流进行的，当所有节点都与汇聚点通信后，节点间再进行新一轮的轮流通信。由于这种轮流通信机制使得能量消耗能够统一地分布到每个节点上，因此降低了整个传输所需消耗的能量。不同LEACH算法的多簇结构，PEGASIS算法在传感器节点中采用链式结构进行连接。运行PEGASIS协议时，每个节点首先利用信号的强度来衡量其所有邻居节点距离的远近，在确定其最近邻居的同时调整发送信号的强度以便只有这个邻居能过听到。其次，链上每个节点向邻居发送和接收数据。采集到得数据以点对点方式传送、融合、并最终被送到汇聚点。图2.8 PEGASIS算法链式结构图PEFASIS协议的优点是减少了LEACH在簇重构过程中所产生的开销，并且通过数据融合降低了收发过程的次数，从而降低了能量的消耗，仿真结果表明，与LEACH协议相比，PEGASIS能够提高网络的生存周期近2倍。PEGASIS协议的缺点是：1.协议假设每个传感器节点都能直接与汇聚点通信，而在实际情况中，传感器节点一般需要采用多跳方式到达汇聚点。2.PEGASIS假定所有的传感器节点都具有相同级别的能量，因此节点很可能在同一时间内全部死亡。3.协议避免了构建簇的开销，但由于传感器节点需要知道其邻居的能量状态信息以便传输数据，协议仍需要动态调整拓扑结构。对那些利用率较高的网络而言，拓扑的调整会带来更大的能源开销。4.协议所构建的节点链中，远距离的节点会引起过多的数据延迟，而且链首节点的唯一性使得链首成为瓶颈。 由Lindsey等人提出的分簇PEGASIS协议是对PEGASIS的扩展，该协议的目标是降低数据包到汇聚点传送过程中所引起的延时。为此，协议采取了数据并行传输的机制，并提出了两种方法来避免传输期间的冲突和可能引起的信号干扰。第一种方法接了信号编码方式，如码分多址CDMA；第二种方法只允许空间上分隔的节点可以同时传输数据。基于CDMS的分簇PEGASIS协议采用树状分簇结构的方式，每一层选择的节点向更高的一级的节点传输数据。协议要求在每个回合的数据采集过程中，给顶层的节点都想附近的邻居发送数据，所有接收数据的节点被提升为上一层的节点。以此类推，最后顶层只有一个节点被保留下来并成为链首节点。为了使节点轮流与汇聚点间通信以均衡节点的能耗，第i回合的链首节点为节点号i除以节点总数N的余数。（10） Group-based SEnsor Network（GSEN）24。在LEACH算法和PEGASIS算法的基础上，文献24结合这两种算法的优点提出了基于分簇的无线传感器网络算法GSEN（Group-based Sensor Network）。在成簇阶段，GSEN算法根据LEACH算法的方法将网络中的节点分簇，簇内节点则根据PEGASIS中的贪婪算法组成相应的链，簇头之间形成另一层次较高级的链，并从此链中选出一个簇头节点和汇聚节点通信。在信息数据转发阶段，簇内节点沿着簇内链的方向将数据传输到簇头，簇头沿着另外的高级链将数据转发至汇聚节点。与LEACH算法不同的是，GSEN并非每一轮都成簇和链，而是每五轮重新产生新的簇和链，但是每一轮都会选出一个新的簇头节点。通过仿真分析发现，GSEN算法在40%节点死亡的情况下，数据转发性能比LEACH高30%，比PEGASIS高30%。然后又提出了GSEN的改进算法（WCA-GSEN），相比LEACH，它是利用增加簇头权值的方法改进簇头的选举方法，在簇头选举过程中综合考量节点的剩余能量、已担任簇头的次数和时间以及邻居节点的节点度。仿真结果表明：WCA-GSEN算法下的网络中最后一个节点的死亡时间能够比GSEN延长20%左右。2.3.2 网络寿命（生存时间）的定义网络的生命周期的长短取决于生命周期到底是怎么样定义的。现在学术界，网络的生命周期有着许多不同的定义。但是参阅较多拓扑控制算法，我们总结了几种广泛应用在不同拓扑控制算法的定义。（1）第一个节点的死亡时间：第一个节点的死亡时间常常用来定义网络的生命周期25。 且这个死亡节点通常被称为一个关键的节点。（2）存活节点的数量：活着节点的数量作为时间的函数的26，来衡量网络的生命周期也有重要的意义27。较多的未死亡节点数目可以描述其网络生命周期较长。（3）部分存活的节点：网络的生命周期也可以是存活节点的时间函数28。只有节点的存活率低于某个阀值意味着网络生命周期的结束。（4）少于建立骨干节点数目的时间：网络生命周期指的是直到网络缺乏骨干节点数目的时间29。在定义的网络生命周期内，网络拓扑主要有一组骨干节点形成，骨干节点的周期性循环可以延长网络的生命周期。这种网络生命周期的定义多用在层次型网络拓扑。（5）部分连通支配集（CDS）节点的存活时间。这是适用于CDS拓扑控制技术的网络生命周期的定义30。当存活的连通支配集（CDS）节点数目低于一个给定的阈值，意味着网络生命周期到了尽头。（6）数据包收发率大幅度下降的时间，此定义估算的是直到数据包传送率急剧下降31的时间。网络死亡时间t为当数据包收发率低于一个预定的阈值的时间。（7）保持连接到基站的节点的数目：网络的存活程度由依旧能够和基站通信的节点数目决定32。这种定义可以归纳为一个连通度的问题。2.4 本章小结本章给出了无线传感器网络拓扑控制技术的定义。拓扑控制算法在无线传感器网络研究已经有了较快发展，但是也面临实际应用方面的挑战；然后对无线传感器网络一些较新的拓扑控制算法做了介绍，最后对文献中无线传感器网络的网络寿命（生存时间）的定义进行了总结，为本文后续章节的相关拓扑控制算法的提出奠定了理论基础。第3章基于同心圆-象限划分的簇头拓扑维护算法第3章 基于同心圆-象限划分的簇头拓扑维护算法拓扑维护算法是在无线传感器网络拓扑初始构建完毕之后的小规模恢复维护算法。本章提出了一种基于地理位置的，用同心圆-象限划分环弧空间的拓扑维护算法。3.1同心圆-象限的数学模型在无线传感器网络中，为了获取有效准确的监测信息，网络有时需要获得地理信息，因此基于地理位置信息的拓扑控制、路由协议研究也广泛起来。利用地理位置信息将网络划分成一重或多重的网格，网内节点按照从属关系组织成一定的群组结构，并在此基础上区分节点的职能，从而实现分层网络拓扑结构以及分层路由协议，以改善网络的性能。基于网格划分的典型拓扑控制算法有GAF算法、DAEA算法等；基于网格划分的典型路由协议有：GRID33、GLS34算法等。还有一些学者将网格的概念用于WSN网络的覆盖和连通性的问题上35，也得到了很好的解决。GAF36（Geographical Adaptive Fidelity）算法是以节点地理位置为依据的分簇算法。该算法引入了虚拟单元格的思想，把监测区域划分成某干个虚拟单元格，将节点按照其地理位置信息划入相应的单元格；在每个单元格中定期选举产生一个簇头，簇头节点保持活动，其他节点进入睡眠状态。图3.1是GAF算法中虚拟单元格划分的示意图。图3.1 GAF算法中虚拟单元格划分的示意图GAF算