本科毕业论文-无线传感器网络的节能研究.doc

摘 要无线传感器网络作为计算、通信和传感器技术相结合的产物，成为计算机科学领域一个活跃的研究分支。其中，针对无线传感器网络路由协议的研究更是研究的重点，因为网络层路由协议的设计直接影响无线传感器网络的整体工作水平和实用化进程。本文针对无线传感器网络性能特点进行分析研究，并得出无线传感器网络最重要的技术指标是能量衰减。通过对以LEACH 协议和MRPS 协议为代表的分簇路由协议的研究，发现目前所提出的分簇路由协议整体性能还有待进一步改善。因此，本文提出了一种基于区域能量均匀分配的带管理节点的分簇路由协议，该协议综合考虑了网络负载平衡、多跳、节点密度、节点剩余能量和数据融合等因素，利用能量无限制的汇聚节点以集中式方式进行分簇，将整个监测区域固定划分为多个小区域，每个小区域作为一个簇，并且在每个簇内引入一个管理节点。管理节点负责定时查询簇头节点的状态，并且以分布式方式实现簇头的重新选举，避免了每轮分簇阶段的能量消耗。本文详细描述了所提出路由协议的实现过程，对其性能进行了理论分析，理论分析表明该协议比LEACH 协议和MRPS 协议延长了网络的生命周期，具有更好的整体性能和实用价值。关键词：无线传感器网络；分簇；路由协议；节能；数据融合AbstractAs a result of the combination of low power computing, wireless communication and micro sensor technology, wireless sensor networks have become an active branch of the researches in computer science. Among these studies, research against the routing protocols is a hotspot, because it will have a direct influence on the working level and the practicability of the wireless sensor networks.This paper analyzes the routing protocols of wireless sensor networks that the most important skill is to reduce the using of energy. However, through the researches against the cluster-based routing protocols represented by LEACH and MRPS, we find that the performance of the cluster-based protocols is needed to be improved. On this basis, we propose a cell-based cluster routing protocol with monitoring node, which comprehensively considered factors such as load-balanced of network, multi-hops, dandify of nodes, energy of nodes left, data aggregation and so on. This protocol clusters the monitoring district into fixed cells by the sink node whose energy can be recharged in a centralized way. A cell is considered as a cluster, and every cluster has a monitoring node in charge of queering the status of the cluster head at scheduled time and presiding the electing of the cluster head in a distributed way, avoiding the energy consumption in the phase of cluster forming every round.This paper describes the proposed protocol in detail and gives a theoretical analysis on the performance of the proposed protocol. The theoretical analysis result demonstrate that the proposed protocol prolongs the lifetime of the network comparing with LEACH protocol and MRPS protocol and has a great use value.Keywords: wireless sensor network, cluster, routing protocol, energy-efficient, data aggregation目 录第1章 概述01.1 无线传感器网络01.2 无线传感器网络节点结构01.3 无线传感器的协议栈01.4 无线传感器网络节点能耗分析01.5 本课题的研究目的01.6 本文的主要工作0第2章 无线传感器路由协议02.1 无线传感器网络路由协议02.2 无线传感器网络路由协议设计要求02.3 无线传感器网络分簇算法基本概念02.3.1 平面路由协议02.3.2 分簇路由协议02.3.3 分簇算法基本目标及其性能评价02.3.4 分簇路由协议性能分析02.4 LEACH 协议02.4.1 LEACH算法02.4.2 分簇阶段02.4.3 稳定数据通信阶段02.4.4 LEACH 协议特点02.5 MRPS协议0第3章 EDEBCRP-MN协议设计03.1 EDEBCRP-MN 协议假设条件03.2 EDEBCRP-MN 协议无线通信模型03.3 EDEBCRP-MN 协议分簇阶段03.3.1 管理节点的引入03.3.2 节点命名机制02.3.3 确定最优簇头数03.4 EDEBCRP-MN协议报文格式03.5 EDEBCRP-MN协议工作过程03.5.1 节点死亡03.5.2 更换簇头节点03.5.3 簇内路由03.5.4 簇间路由0第4章 EDEBCRP-MN协议性能分析04.1 网络生存时间04.2 簇头节点发送数据到聚集节点成功率0总结0参考文献错误！未定义书签。附录:错误！未定义书签。致谢错误！未定义书签。第1章 概述1.1 无线传感器网络作为一种典型的普适计算（Pervasive Computing）的应用，无线传感器网网络（Wireless Sensor Network，简称为WSN）通过大量部署在监测区域内的传感器节点，采集网络覆盖区域内感知对象的信息，通过多跳的无线通信方式，将收集、处理后的信息提供给终端用户，无线传感器网络包括传感器节点、感知对象和观察者构成了传感器网络的三个要素。无线传感器网络融合了现代通信、微电子机械系统和微电子等领域的最新技术，改变了人类与自然界的交互方式，将逻辑上的信息世界与客观上的物理世界融合在一起，WSN不需要固定的网络支持，具有快速展开、抗毁性强等特点，可广泛应用与军事侦察、环境监测和预报、健康护理、智能家居、城市交通等领域。无线传感器网络作为21世纪最有影响的21项技术和改变世界的10大技术之一，对它的研究最早起步于20世纪90年代末期，从21世纪开始，传感器网络引起了学术界、军界和工业界的极大关注，美国和欧洲相继启动了许多关于无线传感器网络的研究计划，特别是美国通过国家自然基金委员会、国防部等多种渠道投入巨资支持传感器网络技术的研究。我国的中科院、哈尔滨工业大学、清华大学、西北工业大学等院校在国内较早开展了传感器网络的研究，2004年起有更多的院校和科研机构加入到该领域的研究工作中来。无线传感器网络涉及传感器技术、网络通信技术、无线传输技术、嵌入式计算技术、分布式信息处理技术、微电子制造技术、软件编程技术等多学科交叉的领域，成为当今信息领域新的研究热点，有非常多的关键技术有待研究，例如网络拓扑控制、网络协议、定位技术、时间同步、数据融合、数据管理、无线通信技术等。目前常见的无线网络包括移动通信网、无线局域网、蓝牙网络、Ad hoc网络等，与这些网络相比，无线传感器网络具有以下鲜明的特点：（1）分布式。网络中没有严格的控制中心，所有节点地位平等，节点之间通过分布式的算法来协调彼此的行为，是一个对等式网络。节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行。（2）自组织。通常网络所处理的环境及网络自身有很多不可预测因素。比如，节点的位置不能预先精确设定；节点之间的相邻关系预先也不知道；部分节点由于能量耗尽或其它原因死亡，新的节点加入到网络中；无线通信质量受环境影响不可预测、网络环境中的突发事件不可控。这样就要求节点具有自组织的能力，无需人工干预和任何其他预置的网络设施，可以在任何时刻，任何地方快速展开并自组织网，自动进行配置和管理，通过适当的网络协议和算法自动转发监测数据。（3）拓扑变化。网络中节点具备移动能力；节点在工作和睡眠状态之间切换以及传感器节点随时可能由于各种原因发生故障而失效，或者有新的传感器节点补充进来以提高网络的质量；加之无线信道之间的互相干扰、地形和天气等综合因素的影响，这些都会使网络的拓扑结构随时发生变化，而且变化的方式与速度难以预测。这些要求网络系统能够适应拓扑变化，具有动态可重构的性能。（4）多跳路由。由于节点发射功率的限制，节点的覆盖范围有限，通常只能与它的邻居节点通信，如果要与其覆盖范围以外的节点进行通信，则需要通过中间节点的转发。此外，多跳路是由普通网络节点协助完成的，没有专门的路由设备。这样每个节点既可以是信息的发起者，也可以是信息的转发者。（5）动态性强。无线传感器网络工作在一定的物理环境中。不断变化的外界环境（如天线通信链路时断时续，突发事件产生导致网络任务负载变化等）往往会严重影响系统的功能，这就要求传感器节点能够随着环境的变化而适时地调整自身的工作状态。此外，网络拓扑结构的变化也要求系统能够很好地适应自身动态多变的“内在环境”。（6）以数据为中心，在无线传感器网络中，人们通常只关心某个区域内某个观测指标的数值，而不会去关心单个节点的观测数据。这就是无线传感器网络以数据为中心的特点，它不同于传统网络的寻址过程，能够快速、有效地组织起各个节点的信息并融合提取出有用信息直接传送给用户。这种以数据本身作为查询或传输线索的思想更接近与自然语言交流的习惯。用户使用传感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给某个确定编号的节点。网络在获得指定事件的信息后汇报给用户。（7）规模大，密度高。为获取尽可能精确、完整的信息，无线传感器网络通常密集部署在大片的检测区域中，其节点的数量和密度较无线自组织网络成数量级地提高。它并非依靠单个设备能力的提升，而是通过大量冗余节点的协同工作来提高系统的工作质量。（8）安全性差。由于采用了无线信道、分布式控制等技术，网络更容易受到被动窃听、主动入侵等攻击。因此，网络的通信保密和安全性十分重要，信道加密、抗干扰、用户认证和其他安全性措施都需要特别考虑，以防止监测数据被盗取和获取伪造的监测信息。由于无线信道自身的物理特性，通常使得它所能提供的网络带宽相对有线信道要小得多。此外，节点能量的变化、周围地势地貌以及自然环境的影响，使得网络的无线通信性能也会经常变化，甚至通信有可能时断时续。因此，如何设计可靠的通信机制以满足网络的通信需求是无线传感器网络所面临的一个重要问题。1.2 无线传感器网络节点结构 传感器模块 处理器模块 无线通信模块 传感器 AC/DC 处理器 网络 MAC 收发器能量供应模块图1.1 触感器节点结构图传感器节点由传感单元、处理单元、无线收发单元和能量供应单元四部分组成，它通常是一个微型的嵌入式系统，如图1.1 所示。传感单元用于感知、获取检测区域内的信息，并将其转换为数字信号，它由传感器和数/模转换模块组成；处理单元负责控制和协调节点各部分的工作，存储和处理自身采集的数据以及其他节点发来的数据，它由嵌入式系统构成，包括处理器、存储器等；无线收发单元负责与其它传感器节点进行通信，交换控制信息和收发采集数据，它由无线通信模块组成；电源单元能量为传感器节点提供正常工作所必需的能源，通常采用微型电池。此外，传感器节点还可以包括其他辅助单元，如移动系统、定位系统和自供电系统等。由于需要进行比较复杂的任务调度与管理，处理器单元还需要包括一个功能较为完善的微型化嵌入式操作系统，如美国UC Berkeley大学开发的Tiny OS。目前已有多种成型的传感器节点时间，如Berkeley 的Motes, ICTCAS/PHKUST的BUDS，Intel的iMote等，它们在现实原理上是相似的，只是采用了不同的微处理器、不同的协议和通信方式。由于传感器节点采用电池供电。一旦电能耗尽，节点就失去了工作能力。为了最大限度地节约电能，在硬件设计方面，要尽量采用低功耗器件，在没有通信任务的时候，切断射频部分电源；在软件设计方面，各层通信协议都应该以节能为中心，必要时可以牺牲其他的一些网络性能指标，已获得更高的电源效率。1.3 无线传感器的协议栈传感器网络的协议栈类似于传统Internet网络中的TCP/IP协议体系，包括物理层、数据链路层、网络层、传输层和应用层，与传统互联网协议栈的五层协议相对应，另外，传感器网络的协议栈还包括功率管理平台、移动管理平台和任务管理平台，如图1.2所示：应用层传输层网络层数据链路层物理层 移动管理平台 任务管理平台 能量管理平台 图1.2 无线传感器网络协议栈各层协议和平台的功能如下：（1）物理层。无线传感器网络的物理层负责信号的调制和数据的收发，所采用的传输介质主要有无线电、红外线、光波等。（2）数据链路层。无线传感器网络的数据链路层负责数据成帧、帧检测、媒体访问和差错控制，其中，媒体访问协议保证可靠的点对点和点对多点通信；差错控制则保证源节点发出的信息可以完整无误地到达目标。（3）网络层。无线传感器网络的网络层负责路由发射和维护，通常，大多数节点无法直接与网关通信，需要通过中间节点以多跳路由的方式将数据传送至汇聚节点。（4）传输层。无线传感器网络的传输层负责数据流的传输控制，主要通过汇聚节点采集传感器网络内的数据，并使用卫星、移动通信网络或者其他的链路与外部网络通信，是保证通信服务质量的重要部分。（5）用层包括一系列基于监测任务的应用层软件；（6）功率管理平台管理传感器节点如何使用能源，在各个协议层都需要考虑节省能量；（7）移动管理平台检测并注册传感器节点的移动，维护到汇聚节点的路由，使得传感器节点能够动态跟踪其邻居节点的位置；(8）(8)任务管理平台在一个给定的区域内平衡和调度检测任务。1.4 无线传感器网络节点能耗分析传感器节点消耗能量的模块包括传感器模块、处理器模块和无线通信模块。随着集成电路工艺的进步，处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无线通信模块上。图1.3所示是 Deborah Estrin 在 Mobicom 2002 会议上的特邀报告（Wireless Sensor Networks, Part IV: Sensor Networks Protocols)中所述传感器节点各部分能量消耗的情况，由图1.3可知，传感器节点的大部分能量消耗在无线通信模块。图1.3 传感器节点能量消耗情况由于无线通信模块占了整个节点能耗的主要部分，因此，对无线通信模块的能耗管理非常重要，采取以下措施可以减少无线通信模块的能量损耗。（1）少通信流量通过减少通信模块发送和接收的比特数,能降低无线通信模块的能耗。减少通信流量有以下几种方法：(a) 本地计算和数据融合：对传感器节点采集的原始数据和各个节点汇集的相关数据进行处理，发送有用信息,有效减少通信量；(b) 减少冲突：如果两帧同时发送，它们会相互重叠,结果导致接收到的信号难以辨认，需要重传才能把信息正确发送到目的地。冲突引起的重传造成很大的能量浪费，减少冲突可以有效节约能量；(c) 增加错误检测和校正机制:增加错误检测可以尽早发现错误，校正机制可以校正少量比特错误的数据包。错误检测和校正机制可以在给定误码率的条件下有效减少数据包的重传，从而降低能耗；(d) 减少控制包的开销和包头长度：网络协议需要控制包和包头来维护其正常运行，但控制包和包头并不是用户所需的数据，应尽量减少控制包的数量,减小包头长度，从而降低能耗。（2）采用多跳通信方式无线通信模块消耗的能量与通信距离的关系为，其中参数满足关系249。的取值与很多因素有关，一般说来，传感器节点部署贴近地面时，障碍物干扰源多，的取值就越大；无线信道质量对信号发射质量的影响也很大。随着通信距离的增加，能耗将急剧增加。因此，在满足通信速率的前提下应该尽量减少单跳通信距离。一般而言，传感器节点的通信半径在几十米以内比较合适。（3）增加休眠时间无线通信模块存在发送、接收、空闲和睡眠四种状态。无线通信模块在空闲状态一直监听无线信道的使用情况，检查是否有数据发送给自己，而在睡眠状态则关闭通信模块。由图1.3可知，无线通信模块在发送状态的能量消耗最大,而在空闲状态和接收状态的能量消耗接近，略少于发送状态的能量消耗，在睡眠状态的能量消耗最少。如何让网络通信更有效率,减少不必要的转发和接收，不需要通信时，尽快进入睡眠状态是传感器网络协议设计需要重点考虑的问题。1.5 本课题的研究目的无线传感器网络节点消耗的能量通常是由微型电池提供的，电池的能量是非常有限的，但是由于无线传感器网络节点规模很大，工作环境往往又比较恶劣，使得节点的电池无法得到更换或者重新充电，所以要想延长传感器网络的生命周期，就必须在网络设计的每个环节首先考虑节能的问题。通过对节点能耗的分析，我们知道传感器节点的能量主要消耗在无线通信模块，也就是说网络层路由协议设计的好坏对无线传感器网络的性能起着至关重要的作用。因此，本文将对现有无线传感器网络路由协议进行分析，尤其是分簇路由协议，针对无线传感器网络自身的特点，设计一种高效利用能量的分簇路由协议，具有非常重要的现实意义。1.6 本文的主要工作Ad hoc、无线局域网等传统无线网络设计的首要目标是公平高效的利用网络带宽，提高服务质量，而无线传感器网络设计的首要目标是最大限度的节省节点的能量消耗，延长整个网络的生命周期。基于这个目标，本文完成了以下工作：(1) 分析了无线传感器网络的特点及传感器节点能量消耗的情况，指出路由协议的设计对无线传感器网络的整体性能具有非常重要的意义。(2) 对无线传感器网络路由协议，尤其是以LEACH 协议和MRPS 协议为代表的分簇路由协议进行深入的研究，发现分簇路由协议虽然相对于平面路由协议来说具有很多优点，但是，目前所提出的分簇路由协议的整体性能还有待进一步完善。(3) 设计一种新的能量高效的分簇路由协议，并详细描述所提出路由协议的工作过程。(4) 按照本文所采用无线通信模型的能量消耗公式，运用数学推导对所提出路由协议的节能性和鲁棒性进行证明。32第2章 无线传感器路由协议2.1 无线传感器网络路由协议路由协议负责将数据分组从源节点通过网络转发到目的节点，它主要包括两个方面的功能：第一，寻找源节点和目的节点间的优化路径；第二，将数据分组沿着优化路径正确转发。Ad hoc、无线局域网等传统无线网络的首要目标是高效的利用网络带宽，提供高质量的网络通信服务，这些网络路由协议的主要任务是寻找源节点和目的节点间通信延迟小的路径，同时提高整个网络带宽的利用率，避免产生通信拥塞并均衡网络流量等，而能量消耗问题不是这类网络考虑的重点。在无线传感器网络中，节点能量有限且一般没有能量补充，因此路由协议需要高效利用能量，同时传感器网络节点数目往往很大，节点只能获取局部拓扑结构信息，路由协议要能在局部网络信息的基础上选择合适的路径。传感器网络具有很强的应用相关性，不同应用中的路由协议可能差别很大，没有一个通用的路由协议。此外，传感器网络的路由机制还经常与数据融合技术联系到一起，通过减少通信量而节省能量。因此，传统无线网络的路由协议不适用于无线传感器网络。与传统网络的路由协议相比，无线传感器网络的路由协议具有以下特点：(1) 能量优先。传统网络路由协议在选择最优路径时，很少考虑节点的能量消耗问题。而无线传感器网络中节点的能量有限，延长整个网络的生存期成为传感器网络路由协议设计的首要目标，因此需要考虑节点的能量消耗以及网络能量均衡使用的问题。(2) 基于局部拓扑信息。无线传感器网络为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资源和计算资源，使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单高效的路由机制是无线传感器网络的一个基本问题。(3) 以数据为中心。传统的路由协议通常以地址作为节点的标识和路由的依据，而无线传感器网络中大量节点随机部署，所关注的是监测区域的感知数据，而不是具体哪个节点获取的信息，不依赖于全网唯一的标识。传感器网络通常包含多个传感器节点到少数汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发路径。(4) 应用相关。传感器网络的应用环境千差万别，数据通信模式不同，没有一个路由机制适合所有的应用，这是传感器网络应用相关性的一个体现。设计者需要针对每一个具体应用的需求，设计与之相适应的特定路由机制。2.2 无线传感器网络路由协议设计要求针对传感器网络路由机制的上述特点，在根据具体应用设计路由机制时，要满足下面的传感器网络路由机制的要求：(1) 能量高效。传感器网络路由协议不仅要选择能量消耗小的传输路径，而且要从整个网络的角度考虑，选择使整个网络能量均衡消耗的路由。传感器节点的资源有限，传感器网络的路由机制要能够简单而且高效的实现信息传输。(2) 可扩展性。在无线传感器网络中，监测区域大小不同或节点密度不同，造成网络规模大小不同；节点失败、新节点加入以及节点移动等，都会使得网络拓扑结构动态发生变化，这就要求路由机制具有可扩展性，能够适应网络结构的变化。(3) 鲁棒性。能量用尽或环境因素造成传感器节点的失败，周围环境影响无线链路的通信质量以及无线链路本身的缺点等，这些无线传感器网络的不可靠性要求路由机制具有一定的容错能力。(4) 快速收敛性。收敛是指在最佳路径的判断上，所有的路由器节点信息更新达到一致的过程。当某个网络事件比如节点硬件故障失去承担义务的能力引起拓扑变化使原有路由不可用时，路由器就发出更新信息，路由更新信息遍及整个网络，引发所有路由器重新计算最合适路由过程，最终使所有路由器找到一致公认的最合适路径。收敛慢的路由算法可能会造成路径循环或网络中断。由于传感器网络独有的特征，每个传感器节点由电池供电，且电池一般不能更换或者充电，所以上述要求中，能量的高效使用是最重要的。2.3 无线传感器网络分簇算法基本概念在无线传感器网络中，网络的分簇结构与平面结构相比具有良好的灵活性、可伸缩性、可扩展性，合理有效的网络分簇结构可以建立高效的网络控制体系，对节点资源进行有效的管理，实现包括带宽分配及频率复用等在内的资源调度和应用、高效路由计算、提供信道接入控制等功能，大大提高了网络的性能。2.3.1 平面路由协议无线传感器网络通常由传感器节点自组织构成，传感器节点可能存在着异构问题，但从数学图论和建行研究的角度来看，在不考虑空间差异情况下可以将无线传感器网络的节点抽象成图的顶点，如下的平面图就是一个无线传感器网络的平面结构。在平面拓扑结构中，所有网络节点的地位是平等的，因此，又把平面结构称对等式结构。平面结构具有生存性强、健壮性好等特点，但随着网络规模的增大，网络的性能将迅速下降。当网络规模增加到某个程度时，路由协议可能会消耗掉所有的网络带宽，即随着无线传感器网络中节点数目的增多，网络管理控制开销也会逐渐增加，从而极大地降低了网络的整体性能。因此，平面结构只适合中小型网络，无法满足大规模无线传感器网络的扩展性需求。外部网络卫星 汇聚节点 任务管理节点 监测区域 传感器节点 用户 图2.1 平面拓扑结构图2.3.2 分簇路由协议鉴于无线传感器网络的特殊环境对系统性能的制约性要求，人们提出了无线传感器网络的分簇结构模式，通过分级的方式可以克服平面结构的缺点，达到提高网络容量、进行网络管理、路由优化和增强网络扩展性的目的。分级结构一般采用分簇算法将网络划分成不同的子网，簇内包含簇头和簇成员。分级结构的优点是以实现网络的管理与同步，并且这种结构类似于蜂窝网络结构，可以赋予簇头更多的功能，临时充当基站，实现资源的分配和无线接入管理。层次拓扑结构的网络一般以簇的形式存在，所谓簇，就是具有某种关联(如根据位置、能量级别关联)的网络节点组成的集合。分簇算法是根据无线传感器网络的具体应用需求，按照某种规则或方法将网路分成可以相互连通并覆盖所有节点的多个簇，并在当网络结构发生变化时更新簇结构以及维护网络的正常功能。分簇算法的主要目的是通过初始化，获得高连通度、覆盖所有节点的簇结构，当网络结构发生变化时及时更新簇结构，确保节点感知到的信息正确地传递到汇聚节点，并且能够使用较少的计算和通信开销来构造和维护一个能够覆盖整个网络的逻辑拓扑结构。网络分簇过程一般包括两个阶段：簇结构的初始化建立、网络运行中对簇以及簇信息的更新和维护。在初始化建立阶段，网络中的节点将基于一定的准则构建多个节点集合，每个集合就是我们所说的簇；在网络运行时，随着节点的移动会损坏等问题的出现，集合也依据准则进行更新，即簇以及簇信息的更新，簇的更新包括簇头节点的改变、簇内成员节点的变化以及簇的重建。通常来说，重建簇的规则是与初始化建立簇的原则和方法是紧密相关的。层次拓扑结构与分簇路由协议相对应，在分簇路由协议中，网络中的节点可以划分为簇头节点和成员节点两类。在每个簇内，根据一定的算法机制选取某个节点作为簇头，用于管理或控制整个簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理以及簇间转发。 有线网络图2.2 层次拓扑结构同平面结构相比较，无线传感器网络的分级结构能够大大减少网络中路由控制信息的数量，提高网络带宽的利用率，并且极大较少了网络规模受节点数目限制的情况。但是，分成结构也存在一些缺点：（1）簇头的选择算法需要一定的额外开销，分簇完成后由于传感器节点具有弱移动性或者新节点的加入与旧节点的死亡等，需要及时进行簇结构的维护和更新，这也增加了网络节点的负载；（2）簇头节点的“额外”义务功能使其任务相对比较繁重，簇头往往会成为网络的瓶颈；（3）簇间的路由也往往不一定是最优路由。尽管分级结构存在一定缺点，但是从实施资源管理、提高网络资源利用率和增加服务质量保障的角度考虑，分集结构较平面结构还是更有优势的，因此，只要在设计分簇算法时对一些问题加以考虑，则基于分级结构的无线传感器网络还是可以达到良好的服务性能的。2.3.3 分簇算法基本目标及其性能评价在使用分簇结构的无线传感器网络中，分簇算法的首要目标的建立合理和有效的网络分簇结构、维持网络拓扑的相对稳定性、提高网络性能。在比较各种分簇算法的性能时，主要采用以下几种性能指标。（1）网络中簇（头）数目，它直接反映了分簇网络的结构和特性。分簇网络中簇数目不应该过多，也不能过少，应以满足系统要求和减少控制开销为准则。（2）单位时间内簇头构成的节点集更新的次数，说明簇重构的频率。重新分簇会引起较大的计算和通信开销，该指标在很大程度上决定了分簇算法的性能。（3）簇重叠度，簇头处理负责的能量取决于他可以支持的节点数量。除了为簇内节点分配资源外，簇头还需要维护簇间的路由，因此希望网络的负载能够比较均匀地分配到各个簇，从而提高网络的整体性能。但在无线传感器网络中优化负载是比较困难的，为了定量地刻画簇头的负载平衡程度，引入簇重叠度和网络负载平衡因子(LBF)两个参数。簇覆盖内所有节点的数目之和与网络节点总数的比值作为网络的簇重叠度，显然簇重叠度越大，则处于重叠区域的节点数量越多。（4）网络负载平衡因子(LBF)：簇头的处理负载近似由该簇的大小表示，即簇的大小变化可以反映簇头的负载分别。LBF定义为簇内成员数（不包括簇头）的方差的倒数，即 （2-1）其中，是簇的数量，是簇的成员节点数目显然，LBF越大，网络的负载平衡程度越好，在理想的情况下，LBF趋向无穷大。（5）节点充当簇头的公平指数（HFI）：该指标说明各个节点充当簇头的公平程度，HFI定义为节点担当簇头的时间偏差，即HFI=，其中表示节点充当簇头的时间，表示节点充当簇头的平均时间，HFI表示节点充当簇头时间偏离节点担当簇头平均时间的程度，因此FHI越小，说明节点充当簇头的公平越好，HFI=0。由于簇头的能量消耗较大，HFI越小，意味着能量消耗越能均匀地分配到各个节点上，从而可以延长网络的寿命。2.3.4 分簇路由协议性能分析与平面路由相比，分簇路由协议有如下优点：（1）普通节点大部分时间可以处于睡眠状态，关闭通信模块，由其上层连接网络负责数据的长距离转发，保证数据通信并节省网络能量；（2）簇头对成员节点的数据进行融合再转发，减少数据通信量；（3）成员节点无需维护复杂路由，减少路由控制信息的数量；（4）采用分簇拓扑结构，有利于分布式算法的应用，对系统变化作出快速反应，便于管理；（5）容易克服平面路由传感器节点移动带来的问题。正因为分簇路由协议具有这些优点，使得分簇路由协议成为一个研究的热点，下面我们讨论两个典型的分簇路由协议LEACH协议和MRPS协议，并结合这两种协议说明分簇路由协议的研究现状。2.4 LEACH 协议LEACH （Low- Energy Adaptive Clustering Hierarchy） 协议是第一个在无线传感网络中提出的分簇式路由协议，其后的大部分分簇式路由协议都是在它的基础上发展而来的。LEACH协议是MIT 的Heinzelman 等人为无线传感器网络设计的低功耗自适应分簇式路由算法。该算法的基本思想是先将传感节点恰当分簇（Clustering），然后为每个簇（Cluster）选取簇头，簇内非簇头节点直接与簇头通信，而簇头节点在接收到本簇之内所有节点的数据后进行数据融合，然后发给数据Sink。该算法通过随机选择每簇簇头，平均分担中继通信业务来实现负荷的均匀分担。LEACH协议定义了“ 轮”(round)的概念，每一轮随机选择簇头，动态分簇，由簇头承担中继通信业务。下一轮工作周期重新选择簇头并分簇。采用这种方法可以使因中继业务繁重而衰竭的节点呈均匀分布状态，LEACH可以延长网络的生命周期。但是LEACH假设所有的节点都能直接与每簇簇头和Sink 通信，因每簇的大小受限，而且整个网络规模的扩张性也并不良好。而且动态分簇引起路由计算的时延和计算处理的能耗。2.4.1 LEACH算法在开发协议的过程中，对传感器网络和网络模式做了如下假设：假设所有节点都能够与汇聚点直接通信；节点可以使用电源控制来控制发送能量的不同；每个节点都具备支持不同MAC协议的计算能力；进行信号处理的能量是可以计算的。无线传感器节点能量受限，在最初的簇首选择回合中，所有的节点都携带相同的能量，并且每个成为簇首的节点都消耗大致相同的能量。无线电信号传输在各个方向上能量消耗相同。节点可感知它的剩余能量，并能相应地改变它的发射功率。LEACH协议是第一个在无线传感器网络中提出的层次式路由协议，其后的大部分层次式路由协议都是在它的基础上发展而来的。LEACH 协议节约能量的主要原因是它运用了数据压缩技术和分层动态路由技术，通过本地的联合工作来提高网络的可扩展性和鲁棒性，通过数据融合来减少发送的数据量，通过把节点随机地设置成群头节点来达到网络内部负载均衡的目的，防止群头节点的过快死亡。LEACH协议分为两个阶段操作，即簇类建立阶段（set- up phase）和稳定工作阶段（steady- statephase）。簇类建立阶段和稳定工作阶段持续时间总和为一轮（round）。在簇类建立阶段，LEACH协议随机选择一个传感器节点作为簇头节点，随机性确保簇头与Sink 之间数据传输的高能耗成本均匀的分摊到所有传感器节点。在簇头节点选定后，该节点对网络中所有节点进行广播，广播数据包含有该节点成为簇头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个簇头节点广播信号强度，该节点选择信号强度最大的簇头，加入该簇，发送成为其成员节点的数据包。分簇形成后，簇头采用TDMA策略分配信道使用权给成员节点。一旦处于稳定工作阶段，簇头节点开始接收该簇中每个节点采集的数据，然后采用数据融合和数据压缩等技术进行汇聚，将整合后的数据传输给Sink，在稳定阶段持续一段时间后，网络又进入另一次分簇建立阶段。从以上分析，我们知道LEACH协议的精华内容是分布式的成簇技术和自适应的成簇算法以及簇首位置的轮换算法。自适应的成簇算法以及簇首位置的轮换算法保证所有节点公平地承担能量消耗的负担，最终可以延长整个系统的生存时间。不足主要表现在：簇首的产生具有极大的随机性，可能会出现部分簇首相距sink 节点太远或部分簇内成员离簇首太远的情况，大大增加了节点的传输能耗，故不能有效地延长网络生存时间。LEACH 算法随机选择簇首并没有考虑到节点的能量状态，不能有效提高网络的生存时间。能量消耗均衡机制要求所有节点的初始能量相同，但这在实际的应用中保证此初始条件比较困难。由于每轮固定簇头之后再建立簇类，所以簇头开销较大，并且离散式区域算法虽然对于节点位置等要求不高，但无法做到最优。由于LEACH 要求节点之间以及节点与基站之间均可以自接通信，所以网络的扩展性不强，并且不适用于大型网络。LEACH 的传输距离较远，并且数据融合相对较少，这就要求传输更多的数据到更远的距离，从而加大了能量消耗。2.4.2 分簇阶段LEACH 协议选举簇头的过程如下：节点产生一个01 之间的随机数，如果这个数小于阈值，则发布自己是簇头的公告消息。在每轮循环中，如果节点已经当选过簇头，则把设置为0，这样该节点不会再次当选为簇头。对于未当选簇头的节点，则将以的概率当选；随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值随之增大，节点产生小于的随机数的概率随之增大，所以节点当选簇头的概率增大。当只剩下一个节点未当选时，=1，表示这个节点一定当选。阈值可表示为： 其它 (2-2)节点当选簇头以后，发布通告消息告知其他节点自己是新簇头。普通节点在收到该消息后，决定加入到相应的簇中。这种决策是依据接收到各簇头节点广播信号的强度，一个普通节点选择加入到发射信号强度最大的簇头节点，向其发送成为其成员的信息，这样“簇”便建立起来了。2.4.3 稳定数据通信阶段当簇头节点接收到所有非簇头节点的加入信息后，根据簇内节点个数，簇头节点创建一张TDMA 调度计划表，这张调度计划表广播给簇内所有成员节点，属于该簇的每个成员节点依次按TDMA 调度计划表分配到一个时间槽发送数据给该簇头节点。在稳定状态阶段，在每个簇内，每个簇头节点用TDMA/SS 协议依次接收各自簇内成员节点采集、传输的数据，这些数据在簇头节点处进行数据融合；在各个簇间，各簇头节点采用CSMA 协议竞用通道，获得通道的簇头节点再将融合后的数据发送到汇聚节点。经过一个合理的时间段后，网络重新回到簇创建阶段，进入下一回合的选择簇头节点的阶段。每个簇使用不同的CDMA 码进行通信，减少隶属于其它簇的节点对本簇节点的通信干扰。2.4.4 LEACH 协议特点为了减少传送到汇聚节点的信息数量，簇首节点负责融合来自簇内不同源节点所产生的数据，并将融合后的数据发送到汇聚点；LEACH采用基于TDMA/CDMA的MAC层机制来较少簇内和簇间的冲突；由于数据采集是集中的和周期性的，因此该协议非常适合一要求连续监控的应用系统；对于终端使用者来说，由于它并不需要立即得到所有的数据，因此协议不需要周期性的传递数据，这样可以达到限制传感器能量消耗的目的；在给定的时间间隔后，协议重新选举簇首节点，以保证无线传感器网络获取用意的能量分布。LEACH 路由算法针对传感器节点在无线通信环节中消耗能量最多这一特点，以增加节点计算负荷为代价换取数据传输量的减少，达到减少能耗的目的。但是，该协议在分簇阶段的能量损耗较大，所以一般要求稳定数据通信阶段的持续时间要比分簇阶段长得多，但是这样会使簇头节点成功发送数据到汇聚节点的概率越来越小。另外，LEACH 协议假定所有节点都具有能力传送数据到汇聚节点，每个节点有计算能力支持不同的MAC 协议且在每一个竞选回合中，所有节点拥有相等的能量值，这些条件本身就是非常苛刻的。LEACH 协议经验证能有效的节省能量，延长网络的生存时间，使网络中的节点相对均衡的消耗能量，但是，LEACH 协议依所用的假设条件仍能存在着一些值得讨论的问题。（1）由于LEACH假定所有节点能够与汇聚节点直接通信，并且每个节点都具备支持不同MAC协议的能力，因此该协议不适合在大规模的无线传感器中应用。（2）协议没有说明节点的数目怎么分布才能及于整个网络。因此，很可能出现被选的簇头结点集中在网络某一区域的现象，这样就会使得一些节点的周围没有任何簇头节点。（3）由于LEACH假定在最初的簇头选择回合中，所有的节点都携带相同的能量，并且每个成为簇头的节点都消耗大致相同的能量。因此，协议不适合节点能量不均衡的网络节点经过簇头选举成为簇头后发布通告消息通告其他节点。其他节点根据以簇头节点的距离选择加入哪个簇。2.5 MRPS协议Jae-hwan Noh 等人提出了MRPS(Multi-hop Routing Protocol based onSuper-Cluster Header)协议，该协议和LEACH 协议一样，执行过程也是周期性的，在每一轮的分簇阶段由汇聚节点进行集中式分簇，在稳定数据通信阶段，簇内节点采用多跳的方式传送数据到簇头节点，但是跟LEACH 协议不同，簇头节点不是直接发送数据到汇聚节点。该协议引入一个主簇头节点（Super ClusterHead,SCH），该节点收集所有簇头节点的数据进行融合计算后转发到汇聚节点，这种三层数据融合结构，节省了能量，延长了网络的生命周期，但是却增加了网络的延迟。分簇路由协议的研究现状：从LEACH协议和MRPS协议的执行过程我们可以看出，分簇算法大致包括以下三个阶段：(1) 簇头的产生；(2) 簇的形成；(3) 簇的路由。簇头的产生是簇形成的基础，簇的路由即簇的数据传输依赖于簇的结构。它们是分簇路由协议设计的关键技术，三者紧密相关，却也相对独立。在簇头产生之后，可以采取不同的分簇策略，同样的簇也可以采用不同的数据传输机制。LEACH协议的成簇思想贯穿于其后所提出的很多分簇路由协议中，如TEEN (Threshold SensitiveEnergy Efficient Sensor Network Protocol)、CEFL(Cluster-head Election Using Fuzzy Logic)等，几乎所有的分簇算法都是围绕如何选择簇头、如何成簇、如何传输数据来考虑设计的。当然，还有少数分簇路由协议是独立开发的，如ACE、LSCP等。通过对大量分簇路由协议的研究，我们发现尽管分簇路由算法在拓扑管理、数据融合和传输等方面有很多优势，但是目前所提出的分簇路由协议整体性能表现良好的并不多，大多数分簇路由协议只是在某一方面表现出较好的性能，而整体性能还有待进一步改善，归纳起来主要体现在以下几点:(1) 算法的节能性需要进一步提高。无线传感器网络分簇路由协议设计的首要目标是通过高效的分簇算法形成合理的网络结构，通过主动的能量管理阻止网络连通性的下降，延长网络的生命周期。因此，能量消耗成了通信连接性能好坏、网络运行周期长短的决定因素。(2) 集中式簇头产生方式的成簇开销较大，限制了网络的扩展性。集中式算法由汇聚节点作出簇头选择决定，健壮性固然较好，但由于每个节点都须向汇聚节点周期性地报告它们的能量和位置等信息，因此，网络流量、时间延迟以及信号干扰的概率都会增加。所以，这类算法成簇开销较大，网络扩展性较差，一般只适合中小型网络。分布式算法则有较好的扩展性、较快的收敛