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

硕 士 学 位 论 文基于分簇的无线传感器网络拓扑维护算法研究Research of Topology Maintenance Algorithm for Wireless Sensor Network Based on Clustering 二零一三年四月分类号： UDC： 密 级：公开 保密年限： 年基于分簇的无线传感器网络拓扑维护算法研究Research of Topology Maintenance Algorithm for Wireless Sensor Network Based on Clustering学科门类： 学科专业： 论文作者： 指导教师： 培养单位： V声明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。论文作者签名：            签字日期：     年    月    日关于论文使用授权的说明学位论文作者完全了解XX有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属XX大学。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。（保密的学位论文在解密后遵守此规定） 学位论文作者签名：            签字日期：     年    月    日  导 师 签 名：               签字日期：    年    月    日摘要摘要无线传感器网络（WSN，wireless sensor network）是由众多能量有限的无线传感器节点组成的，通过节点感知和采集监测范围内的相关目标信息，用无线通信方式发送和接收数据、自适应的网络系统。拓扑控制技术(topology control technology)是无线传感器网络的重要支撑技术和研究领域的热点、难点。拓扑控制的主要目的是优化网络性能，减少节点能耗，延长网络生命期，同时具有保证连通度和覆盖度、减少通信干扰、提高通信效率以及增强网络的健壮性等作用。传统的拓扑控制算法主要考虑到拓扑构建阶段的拓扑，较少考虑到拓扑维护阶段的拓扑控制问题，即节点发生异变后，整个网络体系是否能够依照原拓扑控制算法继续工作。本文主要考虑的就是无线传感器网络拓扑维护阶段的拓扑控制算法在簇头节点失效之后，如何维护网络性能以及恢复通信，延长系统生存时间。根据GAF（Geographical Adaptive Fidelity）算法提出了一种基于同心圆的环分象限空间的簇头拓扑维护算法。该算法是按照同心圆和象限空间的方法划分出的环弧空间。假设网络的初始拓扑构建完成，所有节点都被分簇并且有簇头，然后所有簇头按照同心圆和区域象限的方法划分的网格环，寻找汇聚节点方向上的离自己最近的簇头节点。若某簇的簇头节点失效，则此簇内的节点就近按照环弧空间划分的情况就近加入刚才已找到的簇头。该算法维护了原有的网络属性，保证了簇头节点与汇聚节点的连通性，延长了网络的生存时间。 又根据簇头节点与汇聚节点之间多跳中继转发数据的思想，提出了一种基于信息路径多跳中继转发的簇头拓扑维护算法。该算法基于路径距离模型和能量消耗模型，通过簇头节点与汇聚节点通信时数据转发的最佳跳数的转发，使数据通信消耗的能量最低，从而减少了节点能耗，具有较好的能量有效性。关键词：无线传感器网络；拓扑控制技术；分簇；能量有效；拓扑维护 AbstractAbstractWireless sensor networks (WSN) is composed of numerous energy-limited wireless sensor nodes by node-aware and acquisition monitoring within the relevant target information.Topology control is an important technique used in WSN to achieve energy conservation and extend network lifetime without affecting important network performance such as connectivity and throughput. The main purpose of topology control is to optimize network performance, reduce energy consumption of nodes, to delay network life cycle, and ensure network connectivity and coverage reduce communications interference between the nodes. The idea of topology control is to grant sensor nodes a sense of control over certain parameters such that these parameters can be manipulated in a way that benefit the network. In particular, sensor nodes have the capacity to adjust the transmission range of their radio, switch to the various modes of operation or even decide on the eligibility of the nodes joining the network backbone. These features are the parameters that are exploited in enforcing a reduced topology to achieve energy saving and prolong network lifetime.Firstly, we proposed a topology maintenance algorithm based on space which divided by concentric circles and quadrant. The idea of the algorithm from the GAF algorithm. Assume that the initial network topology had built, then all nodes could find its sector_id and circle_id in the network by concentric circles and quadrant. when a cluster head node have failure, the nodes in this cluster would joined the other cluster head in accordance with the algorithm that its sector_id and circle_id is nearest from the failure node, and in this way ,the network avoid the bad influence brought by the node death. The algorithm maintained the original properties of the network, ensured the connectivity between cluster head node and sink node, extended the survival time of the network.According to the energy consumption model, we try to find a energy consumption minimum path between the clusterheads and sink node which take into account the data relay forwarding hops. So we proposed an algorithm to realize the topology maintenance when a cluster head being dead or elected based on the nodes remain energy and distance between the cluster head and sink node. Clusterheads can communicate with sink node directly or through multi-hop relaying and forwarding path which minimize the energy consumption. Analyzed and simulation results shown that the algorithm could optimize network topology and achieve longer system life time efficiently.Keywords：wireless sensor networks; topology control; clustering; energy efficiency; topology maintenance 目录目 录原创性声明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 第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）更换有故障的节点：可达通信节点的集合确定后，选择离原失效节点最近的节点来代替故障节点，以保证在恢复过程中所有节点移动