无线传感器网络的节能研究（本科毕业论文）

摘 要

无线传感器网络作为计算、通信和传感器技术相结合的产物，成为计算机科学领域一个活跃的研究分支。其中，针对无线传感器网络路由协议的研究更是研究的重点，因为网络层路由协议的设计直接影响无线传感器网络的整体工作水平和实用化进程。

本文针对无线传感器网络性能特点进行分析研究，并得出无线传感器网络最重要的技术指标是能量衰减。通过对以LEACH 协议和MRPS 协议为代表的分簇路由协议的研究，发现目前所提出的分簇路由协议整体性能还有待进一步改善。因此，本文提出了一种基于区域能量均匀分配的带管理节点的分簇路由协议，该协议综合考虑了网络负载平衡、多跳、节点密度、节点剩余能量和数据融合等因素，利用能量无限制的汇聚节点以集中式方式进行分簇，将整个监测区域固定划分为多个小区域，每个小区域作为一个簇，并且在每个簇内引入一个管理节点。管理节点负责定时查询簇头节点的状态，并且以分布式方式实现簇头的重新选举，避免了每轮分簇阶段的能量消耗。

本文详细描述了所提出路由协议的实现过程，对其性能进行了理论分析，理论分析表明该协议比LEACH 协议和MRPS 协议延长了网络的生命周期，具有更好的整体性能和实用价值。

关键词：无线传感器网络；分簇；路由协议；节能；数据融合

Abstract

As 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章 概述 ............................................................................................................................. 1

1.1 无线传感器网络 ....................................................................................................... 1 1.2 无线传感器网络节点结构 ....................................................................................... 3 1.3 无线传感器的协议栈 ............................................................................................... 3 1.4 无线传感器网络节点能耗分析 ............................................................................... 5 1.5 本课题的研究目的 ................................................................................................... 6 1.6 本文的主要工作 ....................................................................................................... 6 第2章 无线传感器路由协议 ................................................................................................. 8

2.1 无线传感器网络路由协议 ....................................................................................... 8 2.2 无线传感器网络路由协议设计要求 ....................................................................... 9 2.3 无线传感器网络分簇算法基本概念 ....................................................................... 9

2.3.1 平面路由协议 ............................................................................................... 9 2.3.2 分簇路由协议 ............................................................................................. 10 2.3.3 分簇算法基本目标及其性能评价 ............................................................. 12 2.3.4 分簇路由协议性能分析 ............................................................................. 12 2.4 LEACH 协议 .......................................................................................................... 13

2.4.1 LEACH算法 ............................................................................................... 13 2.4.2 分簇阶段 ..................................................................................................... 14 2.4.3 稳定数据通信阶段 ..................................................................................... 15 2.4.4 LEACH 协议特点 ...................................................................................... 15 2.5 MRPS协议 .............................................................................................................. 16 第3章 EDEBCRP-MN协议设计 ....................................................................................... 19

3.1 EDEBCRP-MN 协议假设条件 ............................................................................. 19 3.2 EDEBCRP-MN 协议无线通信模型 ..................................................................... 19 3.3 EDEBCRP-MN 协议分簇阶段 ............................................................................. 20

3.3.1 管理节点的引入 ......................................................................................... 21 3.3.2 节点命名机制 ............................................................................................. 22 2.3.3 确定最优簇头数 ......................................................................................... 22 3.4 EDEBCRP-MN协议报文格式 .............................................................................. 24 3.5 EDEBCRP-MN协议工作过程 .............................................................................. 25

3.5.1 节点死亡 ..................................................................................................... 25 3.5.2 更换簇头节点 ............................................................................................. 26 3.5.3 簇内路由 ..................................................................................................... 26 3.5.4 簇间路由 ..................................................................................................... 27

第4章 EDEBCRP-MN协议性能分析............................................................................... 29

4.1 网络生存时间 ......................................................................................................... 29 4.2 簇头节点发送数据到聚集节点成功率 ................................................................. 29 总结 ......................................................................................................................................... 31 参考文献 ................................................................................................. 错误！未定义书签。 附录: ....................................................................................................... 错误！未定义书签。 致谢 ......................................................................................................... 错误！未定义书签。

第1章 概述

1.1 无线传感器网络

作为一种典型的普适计算（Pervasive Computing）的应用，无线传感器网网络（Wireless Sensor Network，简称为WSN）通过大量部署在监测区域内的传感器节点，采集网络覆盖区域内感知对象的信息，通过多跳的无线通信方式，将收集、处理后的信息提供给终端用户，无线传感器网络包括传感器节点、感知对象和观察者构成了传感器网络的三个要素。无线传感器网络融合了现代通信、微电子机械系统和微电子等领域的最新技术，改变了人类与自然界的交互方式，将逻辑上的信息世界与客观上的物理世界融合在一起，WSN不需要固定的网络支持，具有快速展开、抗毁性强等特点，可广泛应用与军事侦察、环境监测和预报、健康护理、智能家居、城市交通等领域。

无线传感器网络作为21世纪最有影响的21项技术和改变世界的10大技术之一，对它的研究最早起步于20世纪90年代末期，从21世纪开始，传感器网络引起了学术界、军界和工业界的极大关注，美国和欧洲相继启动了许多关于无线传感器网络的研究计划，特别是美国通过国家自然基金委员会、国防部等多种渠道投入巨资支持传感器网络技术的研究。我国的中科院、哈尔滨工业大学、清华大学、西北工业大学等院校在国内较早开展了传感器网络的研究，2004年起有更多的院校和科研机构加入到该领域的研究工作中来。无线传感器网络涉及传感器技术、网络通信技术、无线传输技术、嵌入式计算技术、分布式信息处理技术、微电子制造技术、软件编程技术等多学科交叉的领域，成为当今信息领域新的研究热点，有非常多的关键技术有待研究，例如网络拓扑控制、网络协议、定位技术、时间同步、数据融合、数据管理、无线通信技术等。

目前常见的无线网络包括移动通信网、无线局域网、蓝牙网络、Ad hoc网络等，与这些网络相比，无线传感器网络具有以下鲜明的特点：

（1）分布式。网络中没有严格的控制中心，所有节点地位平等，节点之间通过分布式的算法来协调彼此的行为，是一个对等式网络。节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的运行。

（2）自组织。通常网络所处理的环境及网络自身有很多不可预测因素。比如，节点的位置不能预先精确设定；节点之间的相邻关系预先也不知道；部分节点由于能量耗尽或其它原因死亡，新的节点加入到网络中；无线通信质量受环境影响不可预测、网络环境中的突发事件不可控。这样就要求节点具有自组织的能力，无需人工干预和任何其

1

他预置的网络设施，可以在任何时刻，任何地方快速展开并自组织网，自动进行配置和管理，通过适当的网络协议和算法自动转发监测数据。

（3）拓扑变化。网络中节点具备移动能力；节点在工作和睡眠状态之间切换以及传感器节点随时可能由于各种原因发生故障而失效，或者有新的传感器节点补充进来以提高网络的质量；加之无线信道之间的互相干扰、地形和天气等综合因素的影响，这些都会使网络的拓扑结构随时发生变化，而且变化的方式与速度难以预测。这些要求网络系统能够适应拓扑变化，具有动态可重构的性能。

（4）多跳路由。由于节点发射功率的限制，节点的覆盖范围有限，通常只能与它的邻居节点通信，如果要与其覆盖范围以外的节点进行通信，则需要通过中间节点的转发。此外，多跳路是由普通网络节点协助完成的，没有专门的路由设备。这样每个节点既可以是信息的发起者，也可以是信息的转发者。

（5）动态性强。无线传感器网络工作在一定的物理环境中。不断变化的外界环境（如天线通信链路时断时续，突发事件产生导致网络任务负载变化等）往往会严重影响系统的功能，这就要求传感器节点能够随着环境的变化而适时地调整自身的工作状态。此外，网络拓扑结构的变化也要求系统能够很好地适应自身动态多变的“内在环境”。

（6）以数据为中心，在无线传感器网络中，人们通常只关心某个区域内某个观测指标的数值，而不会去关心单个节点的观测数据。这就是无线传感器网络以数据为中心的特点，它不同于传统网络的寻址过程，能够快速、有效地组织起各个节点的信息并融合提取出有用信息直接传送给用户。这种以数据本身作为查询或传输线索的思想更接近与自然语言交流的习惯。用户使用传感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给某个确定编号的节点。网络在获得指定事件的信息后汇报给用户。

（7）规模大，密度高。为获取尽可能精确、完整的信息，无线传感器网络通常密集部署在大片的检测区域中，其节点的数量和密度较无线自组织网络成数量级地提高。它并非依靠单个设备能力的提升，而是通过大量冗余节点的协同工作来提高系统的工作质量。

（8）安全性差。由于采用了无线信道、分布式控制等技术，网络更容易受到被动窃听、主动入侵等攻击。因此，网络的通信保密和安全性十分重要，信道加密、抗干扰、用户认证和其他安全性措施都需要特别考虑，以防止监测数据被盗取和获取伪造的监测信息。

由于无线信道自身的物理特性，通常使得它所能提供的网络带宽相对有线信道要小得多。此外，节点能量的变化、周围地势地貌以及自然环境的影响，使得网络的无线通

2

信性能也会经常变化，甚至通信有可能时断时续。因此，如何设计可靠的通信机制以满足网络的通信需求是无线传感器网络所面临的一个重要问题。

1.2 无线传感器网络节点结构

传感器模块 处理器模块 无线通信模块 传感器 AC/DC 处理器 网络 MAC 收发器 能量供应模块 图1.1 触感器节点结构图

传感器节点由传感单元、处理单元、无线收发单元和能量供应单元四部分组成，它通常是一个微型的嵌入式系统，如图1.1 所示。

传感单元用于感知、获取检测区域内的信息，并将其转换为数字信号，它由传感器和数/模转换模块组成；处理单元负责控制和协调节点各部分的工作，存储和处理自身采集的数据以及其他节点发来的数据，它由嵌入式系统构成，包括处理器、存储器等；无线收发单元负责与其它传感器节点进行通信，交换控制信息和收发采集数据，它由无线通信模块组成；电源单元能量为传感器节点提供正常工作所必需的能源，通常采用微型电池。

此外，传感器节点还可以包括其他辅助单元，如移动系统、定位系统和自供电系统等。由于需要进行比较复杂的任务调度与管理，处理器单元还需要包括一个功能较为完善的微型化嵌入式操作系统，如美国UC Berkeley大学开发的Tiny OS。目前已有多种成型的传感器节点时间，如Berkeley 的Motes, ICTCAS/PHKUST的BUDS，Intel的iMote等，它们在现实原理上是相似的，只是采用了不同的微处理器、不同的协议和通信方式。

由于传感器节点采用电池供电。一旦电能耗尽，节点就失去了工作能力。为了最大限度地节约电能，在硬件设计方面，要尽量采用低功耗器件，在没有通信任务的时候，切断射频部分电源；在软件设计方面，各层通信协议都应该以节能为中心，必要时可以牺牲其他的一些网络性能指标，已获得更高的电源效率。

1.3 无线传感器的协议栈

3

传感器网络的协议栈类似于传统Internet网络中的TCP/IP协议体系，包括物理层、数据链路层、网络层、传输层和应用层，与传统互联网协议栈的五层协议相对应，另外，传感器网络的协议栈还包括功率管理平台、移动管理平台和任务管理平台，如图1.2所示：

移动管理平台 任务管理平台 能量管理平台

图1.2 无线传感器网络协议栈

各层协议和平台的功能如下：

（1）物理层。无线传感器网络的物理层负责信号的调制和数据的收发，所采用的传输介质主要有无线电、红外线、光波等。

（2）数据链路层。无线传感器网络的数据链路层负责数据成帧、帧检测、媒体访问和差错控制，其中，媒体访问协议保证可靠的点对点和点对多点通信；差错控制则保证源节点发出的信息可以完整无误地到达目标。

（3）网络层。无线传感器网络的网络层负责路由发射和维护，通常，大多数节点无法直接与网关通信，需要通过中间节点以多跳路由的方式将数据传送至汇聚节点。

（4）传输层。无线传感器网络的传输层负责数据流的传输控制，主要通过汇聚节点采集传感器网络内的数据，并使用卫星、移动通信网络或者其他的链路与外部网络通信，是保证通信服务质量的重要部分。

（5）用层包括一系列基于监测任务的应用层软件；

（6）功率管理平台管理传感器节点如何使用能源，在各个协议层都需要考虑节省能量；

数据链路层 物理层 应用层 传输层 网络层 4

（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) 减少控制包的开销和包头长度：网络协议需要控制包和包

5

头来维护其正常运行，但控制包和包头并不是用户所需的数据，应尽量减少控制包的数量,减小包头长度，从而降低能耗。

（2）采用多跳通信方式

无线通信模块消耗的能量E与通信距离d的关系为E?kdn，其中参数n满足关系

2

无线通信模块存在发送、接收、空闲和睡眠四种状态。无线通信模块在空闲状态一直监听无线信道的使用情况，检查是否有数据发送给自己，而在睡眠状态则关闭通信模块。由图1.3可知，无线通信模块在发送状态的能量消耗最大,而在空闲状态和接收状态的能量消耗接近，略少于发送状态的能量消耗，在睡眠状态的能量消耗最少。如何让网络通信更有效率,减少不必要的转发和接收，不需要通信时，尽快进入睡眠状态是传感器网络协议设计需要重点考虑的问题。

1.5 本课题的研究目的

无线传感器网络节点消耗的能量通常是由微型电池提供的，电池的能量是非常有限的，但是由于无线传感器网络节点规模很大，工作环境往往又比较恶劣，使得节点的电池无法得到更换或者重新充电，所以要想延长传感器网络的生命周期，就必须在网络设计的每个环节首先考虑节能的问题。通过对节点能耗的分析，我们知道传感器节点的能量主要消耗在无线通信模块，也就是说网络层路由协议设计的好坏对无线传感器网络的性能起着至关重要的作用。因此，本文将对现有无线传感器网络路由协议进行分析，尤其是分簇路由协议，针对无线传感器网络自身的特点，设计一种高效利用能量的分簇路由协议，具有非常重要的现实意义。

1.6 本文的主要工作

Ad hoc、无线局域网等传统无线网络设计的首要目标是公平高效的利用网络带宽，提高服务质量，而无线传感器网络设计的首要目标是最大限度的节省节点的能量消耗，延长整个网络的生命周期。基于这个目标，本文完成了以下工作：

(1) 分析了无线传感器网络的特点及传感器节点能量消耗的情况，指出路由协议的设计对无线传感器网络的整体性能具有非常重要的意义。

(2) 对无线传感器网络路由协议，尤其是以LEACH 协议和MRPS 协议为代表的分

6

簇路由协议进行深入的研究，发现分簇路由协议虽然相对于平面路由协议来说具有很多优点，但是，目前所提出的分簇路由协议的整体性能还有待进一步完善。

(3) 设计一种新的能量高效的分簇路由协议，并详细描述所提出路由协议的工作过程。

(4) 按照本文所采用无线通信模型的能量消耗公式，运用数学推导对所提出路由协议的节能性和鲁棒性进行证明。

7

第2章 无线传感器路由协议

2.1 无线传感器网络路由协议

路由协议负责将数据分组从源节点通过网络转发到目的节点，它主要包括两个方面的功能：第一，寻找源节点和目的节点间的优化路径；第二，将数据分组沿着优化路径正确转发。Ad hoc、无线局域网等传统无线网络的首要目标是高效的利用网络带宽，提供高质量的网络通信服务，这些网络路由协议的主要任务是寻找源节点和目的节点间通信延迟小的路径，同时提高整个网络带宽的利用率，避免产生通信拥塞并均衡网络流量等，而能量消耗问题不是这类网络考虑的重点。在无线传感器网络中，节点能量有限且一般没有能量补充，因此路由协议需要高效利用能量，同时传感器网络节点数目往往很大，节点只能获取局部拓扑结构信息，路由协议要能在局部网络信息的基础上选择合适的路径。传感器网络具有很强的应用相关性，不同应用中的路由协议可能差别很大，没有一个通用的路由协议。此外，传感器网络的路由机制还经常与数据融合技术联系到一起，通过减少通信量而节省能量。因此，传统无线网络的路由协议不适用于无线传感器网络。与传统网络的路由协议相比，无线传感器网络的路由协议具有以下特点：

(1) 能量优先。传统网络路由协议在选择最优路径时，很少考虑节点的能量消耗问题。而无线传感器网络中节点的能量有限，延长整个网络的生存期成为传感器网络路由协议设计的首要目标，因此需要考虑节点的能量消耗以及网络能量均衡使用的问题。

(2) 基于局部拓扑信息。无线传感器网络为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资源和计算资源，使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单高效的路由机制是无线传感器网络的一个基本问题。

(3) 以数据为中心。传统的路由协议通常以地址作为节点的标识和路由的依据，而无线传感器网络中大量节点随机部署，所关注的是监测区域的感知数据，而不是具体哪个节点获取的信息，不依赖于全网唯一的标识。传感器网络通常包含多个传感器节点到少数汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发路径。

(4) 应用相关。传感器网络的应用环境千差万别，数据通信模式不同，没有

8

一个路由机制适合所有的应用，这是传感器网络应用相关性的一个体现。设计者需要针对每一个具体应用的需求，设计与之相适应的特定路由机制。

2.2 无线传感器网络路由协议设计要求

针对传感器网络路由机制的上述特点，在根据具体应用设计路由机制时，要满足下面的传感器网络路由机制的要求：

(1) 能量高效。传感器网络路由协议不仅要选择能量消耗小的传输路径，而且要从整个网络的角度考虑，选择使整个网络能量均衡消耗的路由。传感器节点的资源有限，传感器网络的路由机制要能够简单而且高效的实现信息传输。

(2) 可扩展性。在无线传感器网络中，监测区域大小不同或节点密度不同，造成网络规模大小不同；节点失败、新节点加入以及节点移动等，都会使得网络拓扑结构动态发生变化，这就要求路由机制具有可扩展性，能够适应网络结构的变化。

(3) 鲁棒性。能量用尽或环境因素造成传感器节点的失败，周围环境影响无线链路的通信质量以及无线链路本身的缺点等，这些无线传感器网络的不可靠性要求路由机制具有一定的容错能力。

(4) 快速收敛性。收敛是指在最佳路径的判断上，所有的路由器节点信息更新达到一致的过程。当某个网络事件比如节点硬件故障失去承担义务的能力引起拓扑变化使原有路由不可用时，路由器就发出更新信息，路由更新信息遍及整个网络，引发所有路由器重新计算最合适路由过程，最终使所有路由器找到一致公认的最合适路径。收敛慢的路由算法可能会造成路径循环或网络中断。

由于传感器网络独有的特征，每个传感器节点由电池供电，且电池一般不能更换或者充电，所以上述要求中，能量的高效使用是最重要的。

2.3 无线传感器网络分簇算法基本概念

在无线传感器网络中，网络的分簇结构与平面结构相比具有良好的灵活性、可伸缩性、可扩展性，合理有效的网络分簇结构可以建立高效的网络控制体系，对节点资源进行有效的管理，实现包括带宽分配及频率复用等在内的资源调度和应用、高效路由计算、提供信道接入控制等功能，大大提高了网络的性能。 2.3.1 平面路由协议

无线传感器网络通常由传感器节点自组织构成，传感器节点可能存在着异构问题，但从数学图论和建行研究的角度来看，在不考虑空间差异情况下可以将无线传感器网络的节点抽象成图的顶点，如下的平面图就是一个无线传感器网络的

9

平面结构。在平面拓扑结构中，所有网络节点的地位是平等的，因此，又把平面结构称对等式结构。平面结构具有生存性强、健壮性好等特点，但随着网络规模的增大，网络的性能将迅速下降。当网络规模增加到某个程度时，路由协议可能会消耗掉所有的网络带宽，即随着无线传感器网络中节点数目的增多，网络管理控制开销也会逐渐增加，从而极大地降低了网络的整体性能。因此，平面结构只适合中小型网络，无法满足大规模无线传感器网络的扩展性需求。

外部网络卫星 汇聚节点

任务管理节点 监测区域 传感器节点 用户

图2.1 平面拓扑结构图

2.3.2 分簇路由协议

鉴于无线传感器网络的特殊环境对系统性能的制约性要求，人们提出了无线传感器网络的分簇结构模式，通过分级的方式可以克服平面结构的缺点，达到提高网络容量、进行网络管理、路由优化和增强网络扩展性的目的。分级结构一般采用分簇算法将网络划分成不同的子网，簇内包含簇头和簇成员。分级结构的优点是以实现网络的管理与同步，并且这种结构类似于蜂窝网络结构，可以赋予簇头更多的功能，临时充当基站，实现资源的分配和无线接入管理。

层次拓扑结构的网络一般以簇的形式存在，所谓簇，就是具有某种关联(如根据位置、能量级别关联)的网络节点组成的集合。分簇算法是根据无线传感器网络的具体应用需求，按照某种规则或方法将网路分成可以相互连通并覆盖所有节点的多个簇，并在当网络结构发生变化时更新簇结构以及维护网络的正常功能。分簇算法的主要目的是通过初始化，获得高连通度、覆盖所有节点的簇结构，当网络结构发生变化时及时更新簇结构，确保节点感知到的信息正确地传递到汇聚节点，并且能够使用较少的计算和通信开销来构造和维护一个能够覆盖整个网络的逻辑拓扑结构。

网络分簇过程一般包括两个阶段：簇结构的初始化建立、网络运行中对簇以

10

及簇信息的更新和维护。在初始化建立阶段，网络中的节点将基于一定的准则构建多个节点集合，每个集合就是我们所说的簇；在网络运行时，随着节点的移动会损坏等问题的出现，集合也依据准则进行更新，即簇以及簇信息的更新，簇的更新包括簇头节点的改变、簇内成员节点的变化以及簇的重建。通常来说，重建簇的规则是与初始化建立簇的原则和方法是紧密相关的。层次拓扑结构与分簇路由协议相对应，在分簇路由协议中，网络中的节点可以划分为簇头节点和成员节点两类。在每个簇内，根据一定的算法机制选取某个节点作为簇头，用于管理或控制整个簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理以及簇间转发。

有线网络

图2.2 层次拓扑结构

同平面结构相比较，无线传感器网络的分级结构能够大大减少网络中路由控制信息的数量，提高网络带宽的利用率，并且极大较少了网络规模受节点数目限制的情况。但是，分成结构也存在一些缺点：（1）簇头的选择算法需要一定的额外开销，分簇完成后由于传感器节点具有弱移动性或者新节点的加入与旧节点的死亡等，需要及时进行簇结构的维护和更新，这也增加了网络节点的负载；（2）簇头节点的“额外”义务功能使其任务相对比较繁重，簇头往往会成为网络的瓶颈；（3）簇间的路由也往往不一定是最优路由。

尽管分级结构存在一定缺点，但是从实施资源管理、提高网络资源利用率和增加服务质量保障的角度考虑，分集结构较平面结构还是更有优势的，因此，只要在设计分簇算法时对一些问题加以考虑，则基于分级结构的无线传感器网络还是可以达到良好的服务性能的。

11

2.3.3 分簇算法基本目标及其性能评价

在使用分簇结构的无线传感器网络中，分簇算法的首要目标的建立合理和有效的网络分簇结构、维持网络拓扑的相对稳定性、提高网络性能。

在比较各种分簇算法的性能时，主要采用以下几种性能指标。

（1）网络中簇（头）数目，它直接反映了分簇网络的结构和特性。分簇网络中簇数目不应该过多，也不能过少，应以满足系统要求和减少控制开销为准则。

（2）单位时间内簇头构成的节点集更新的次数，说明簇重构的频率。重新分簇会引起较大的计算和通信开销，该指标在很大程度上决定了分簇算法的性能。

（3）簇重叠度，簇头处理负责的能量取决于他可以支持的节点数量。除了为簇内节点分配资源外，簇头还需要维护簇间的路由，因此希望网络的负载能够比较均匀地分配到各个簇，从而提高网络的整体性能。但在无线传感器网络中优化负载是比较困难的，为了定量地刻画簇头的负载平衡程度，引入簇重叠度和网络负载平衡因子(LBF)两个参数。簇覆盖内所有节点的数目之和与网络节点总数的比值作为网络的簇重叠度，显然簇重叠度越大，则处于重叠区域的节点数量越多。

（4）网络负载平衡因子(LBF)：簇头的处理负载近似由该簇的大小表示，即簇的大小变化可以反映簇头的负载分别。LBF定义为簇内成员数（不包括簇头）的方差的倒数，即

LBF?M?Mi?12 （2-1）

(xi?u)其中，M是簇的数量，xi是簇i的成员节点数目显然，LBF越大，网络的负载平衡程度越好，在理想的情况下xi?u，LBF趋向无穷大。

（5）节点充当簇头的公平指数（HFI）：该指标说明各个节点充当簇头的公平程度，HFI定义为节点担当簇头的时间偏差，即HFI=E?|ti中ti表示节点i充当簇头的时间，E(ti?E(ti)|?,i??，其

)??i??tiN表示节点充当簇头的平均时间，

HFI表示节点i充当簇头时间偏离节点担当簇头平均时间的程度，因此FHI越小，说明节点充当簇头的公平越好，ti?E(ti)，HFI=0。由于簇头的能量消耗较大，

HFI越小，意味着能量消耗越能均匀地分配到各个节点上，从而可以延长网络的寿命。

2.3.4 分簇路由协议性能分析

与平面路由相比，分簇路由协议有如下优点：（1）普通节点大部分时间可

12

以处于睡眠状态，关闭通信模块，由其上层连接网络负责数据的长距离转发，保证数据通信并节省网络能量；（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 协议节约能量

13

的主要原因是它运用了数据压缩技术和分层动态路由技术，通过本地的联合工作来提高网络的可扩展性和鲁棒性，通过数据融合来减少发送的数据量，通过把节点随机地设置成群头节点来达到网络内部负载均衡的目的，防止群头节点的过快死亡。LEACH协议分为两个阶段操作，即簇类建立阶段（set- up phase）和稳定工作阶段（steady- statephase）。簇类建立阶段和稳定工作阶段持续时间总和为一轮（round）。在簇类建立阶段，LEACH协议随机选择一个传感器节点作为簇头节点，随机性确保簇头与Sink 之间数据传输的高能耗成本均匀的分摊到所有传感器节点。在簇头节点选定后，该节点对网络中所有节点进行广播，广播数据包含有该节点成为簇头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个簇头节点广播信号强度，该节点选择信号强度最大的簇头，加入该簇，发送成为其成员节点的数据包。分簇形成后，簇头采用TDMA策略分配信道使用权给成员节点。一旦处于稳定工作阶段，簇头节点开始接收该簇中每个节点采集的数据，然后采用数据融合和数据压缩等技术进行汇聚，将整合后的数据传输给Sink，在稳定阶段持续一段时间后，网络又进入另一次分簇建立阶段。

从以上分析，我们知道LEACH协议的精华内容是分布式的成簇技术和自适应的成簇算法以及簇首位置的轮换算法。自适应的成簇算法以及簇首位置的轮换算法保证所有节点公平地承担能量消耗的负担，最终可以延长整个系统的生存时间。不足主要表现在：①簇首的产生具有极大的随机性，可能会出现部分簇首相距sink 节点太远或部分簇内成员离簇首太远的情况，大大增加了节点的传输能耗，故不能有效地延长网络生存时间。②LEACH 算法随机选择簇首并没有考虑到节点的能量状态，不能有效提高网络的生存时间。能量消耗均衡机制要求所有节点的初始能量相同，但这在实际的应用中保证此初始条件比较困难。③由于每轮固定簇头之后再建立簇类，所以簇头开销较大，并且离散式区域算法虽然对于节点位置等要求不高，但无法做到最优。④由于LEACH 要求节点之间以及节点与基站之间均可以自接通信，所以网络的扩展性不强，并且不适用于大型网络。⑤LEACH 的传输距离较远，并且数据融合相对较少，这就要求传输更多的数据到更远的距离，从而加大了能量消耗。 2.4.2 分簇阶段

LEACH 协议选举簇头的过程如下：节点产生一个0～1 之间的随机数，如果这个数小于阈值T(n)，则发布自己是簇头的公告消息。在每轮循环中，如果节点已经当选过簇头，则把T(n)设置为0，这样该节点不会再次当选为簇头。对

14

于未当选簇头的节点，则将以T(n)的概率当选；随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值T(n)随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选簇头的概率增大。当只剩下一个节点未当选时，T(n)=1，表示这个节点一定当选。阈值T(n)可表示为：

?p

n?G ?T(n)??1?p[rmod(1/p)] 其它 (2-2) ?0?

节点当选簇头以后，发布通告消息告知其他节点自己是新簇头。普通节点在收到该消息后，决定加入到相应的簇中。这种决策是依据接收到各簇头节点广播信号的强度，一个普通节点选择加入到发射信号强度最大的簇头节点，向其发送成为其成员的信息，这样“簇”便建立起来了。 2.4.3 稳定数据通信阶段

当簇头节点接收到所有非簇头节点的加入信息后，根据簇内节点个数，簇头节点创建一张TDMA 调度计划表，这张调度计划表广播给簇内所有成员节点，属于该簇的每个成员节点依次按TDMA 调度计划表分配到一个时间槽发送数据给该簇头节点。

在稳定状态阶段，在每个簇内，每个簇头节点用TDMA/SS 协议依次接收各自簇内成员节点采集、传输的数据，这些数据在簇头节点处进行数据融合；在各个簇间，各簇头节点采用CSMA 协议竞用通道，获得通道的簇头节点再将融合后的数据发送到汇聚节点。经过一个合理的时间段后，网络重新回到簇创建阶段，进入下一回合的选择簇头节点的阶段。每个簇使用不同的CDMA 码进行通信，减少隶属于其它簇的节点对本簇节点的通信干扰。 2.4.4 LEACH 协议特点

为了减少传送到汇聚节点的信息数量，簇首节点负责融合来自簇内不同源节点所产生的数据，并将融合后的数据发送到汇聚点；LEACH采用基于TDMA/CDMA的MAC层机制来较少簇内和簇间的冲突；由于数据采集是集中的和周期性的，因此该协议非常适合一要求连续监控的应用系统；对于终端使用者来说，由于它并不需要立即得到所有的数据，因此协议不需要周期性的传递数据，这样可以达到限制传感器能量消耗的目的；在给定的时间间隔后，协议重新选举簇首节点，以保证无线传感器网络获取用意的能量分布。

15

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) 簇的路由。簇头的产生是簇形

16

成的基础，簇的路由即簇的数据传输依赖于簇的结构。它们是分簇路由协议设计的关键技术，三者紧密相关，却也相对独立。在簇头产生之后，可以采取不同的分簇策略，同样的簇也可以采用不同的数据传输机制。LEACH协议的成簇思想贯穿于其后所提出的很多分簇路由协议中，如TEEN (Threshold SensitiveEnergy Efficient Sensor Network Protocol)、CEFL(Cluster-head Election Using Fuzzy Logic)等，几乎所有的分簇算法都是围绕如何选择簇头、如何成簇、如何传输数据来考虑设计的。当然，还有少数分簇路由协议是独立开发的，如ACE、LSCP等。

通过对大量分簇路由协议的研究，我们发现尽管分簇路由算法在拓扑管理、数据融合和传输等方面有很多优势，但是目前所提出的分簇路由协议整体性能表现良好的并不多，大多数分簇路由协议只是在某一方面表现出较好的性能，而整体性能还有待进一步改善，归纳起来主要体现在以下几点:

(1) 算法的节能性需要进一步提高。无线传感器网络分簇路由协议设计的首要目标是通过高效的分簇算法形成合理的网络结构，通过主动的能量管理阻止网络连通性的下降，延长网络的生命周期。因此，能量消耗成了通信连接性能好坏、网络运行周期长短的决定因素。

(2) 集中式簇头产生方式的成簇开销较大，限制了网络的扩展性。集中式算法由汇聚节点作出簇头选择决定，健壮性固然较好，但由于每个节点都须向汇聚节点周期性地报告它们的能量和位置等信息，因此，网络流量、时间延迟以及信号干扰的概率都会增加。所以，这类算法成簇开销较大，网络扩展性较差，一般只适合中小型网络。分布式算法则有较好的扩展性、较快的收敛速度和能量的高效性。

(3) 簇的负载均衡是分布式成簇算法的一大挑战。集中式算法基于全局信息成簇，一般生成的簇较均衡，而分布式算法是通过节点之间的信息交互和反馈成簇，由于节点是随机部署的，分布并不完全均匀，因此，基于局部信息成簇容易导致网络负载整体不均匀，造成局部网络负载过重。

(4) 多跳数据传输结构的缺陷。LEACH，TEEN等单跳网络中的簇内成员节点在属于它的TDMA时隙内把数据直接传送到簇头，其余时间关闭通信模块节省能量。而ECMR等多跳网络，簇内数据的传输必须依赖中间节点转发，这就存在一个致命的缺陷：靠近簇头的节点因为承担了更多的转发任务，能量耗费较快，因而影响了网络的生存周期。

(5) 算法健壮性的考虑。由于传感器节点易失效，而且分簇结构存在瓶颈和

17

潜在的危险性，簇头的高负载使网络瘫痪的可能性增加，因此要求算法具有一定的容错能力。

18

第3章 EDEBCRP-MN协议设计

无线传感器网络性能的好坏取决于路由算法的选择，路由算法在各种网络中都起着至关重要的作用，采用何种路由算法决定了最终的数据路由路径，直接影响网络的整体性能，因此针对传感器网络的自身特点，设计一种性能好的路由协议是非常具有挑战性的。通过前面对传感器节点能量消耗情况和无线传感器网络路由协议的研究，我们提出一种基于能量均匀分配的带管理节点的分簇路由协议EDEBCRP-MN (Evenly distributed Energy-based Cluster Routing Protocol with Monitoring Node)，该协议的主要思想是利用可补充能量的汇聚节点采用集中式方式将覆盖的区域内所有传感器节点按能量均匀划分的做法，划分为许多小区域，每个小区域作为一个簇。在每个簇中设置一个管理节点，管理节点以分布式方式实现每个簇中簇头的重新选举，以减少成簇的开销，同时增强网络的健壮性。

3.1 EDEBCRP-MN 协议假设条件

假设传感器节点随机分布在一个正方形监测区域内，并且该传感器网络具有以下性质：

(1) 汇聚节点位于监测区域外远处一点，以正方形区域某一顶点为坐标原点，以该顶点所在的两条边为坐标轴建立坐标系，正方形区域位于第一象限，本文假设汇聚节点的坐标为（－100，0）。

(2) 汇聚节点具有较强的计算、存储能力，且能量能够得到补充。

(3) 所有传感器节点部署后静止不动，具有相似的处理通信能力，地位是对称平等的。

(4) 节点无线发射功率可以调节，即节点通信半径可以改变。

3.2 EDEBCRP-MN 协议无线通信模型

本文采用无线通信模型，该模型给出一个阈值r0，当发送节点与接收节点的距离小于r0 时，发送端发送数据的能量损耗与距离的平方成正比，否则与距离的四次方成正比。这两种不同的能量衰减模型分别称为自由空间模型和多路衰减模型。

当网络选用单跳路由协议方式时，簇头节点以单挑方式接收每个传感器发送的数据，此时节点能量衰减模型为自由空间模型，节点发送信息消耗的能量E与通信距离d的平方成正比。在单跳路由情况下，距离簇头越远的节点消耗的能量越大，在各传感器初始能量都相等的情况下，远距离节点会因能量耗尽而很快就无法工作，距离簇头较近的节

19

点还会有很多能量，使得整个网络的能量消耗极不均匀，整个网络系统的实用性会大大降低。

若网络选用多跳路由协议，每个节点都把数据传送到下一跳的节点，这样就大大缩短了节点的通信距离，因此多跳路由协议和单跳路由协议相比，从节点消耗能量总和来看有很大的降低，比如每个节点传送一个单位的数据到簇头节点，单跳路由情况下能量总消耗为

E?d2E?(4d)?(3d)?(2d)?(d)22222?30d2，而多跳路由消耗能量总和仅为

?2d?3d2?4d2?10d2。

根据发送节端与接收节端之间的距离，发送节点可以使用不同的能耗模型计算发送数据所需要的能量。例如A节点向距离为d的另一节点B发送k字节的数据，其能量消耗的计算如下：

ETx(k,d)?ETx?ekec(k)?ETx?amp(k,d)?kEelec?k?ampf(d)2??kEelec?k?fsd?? (3-1)

4??kEelec?k?trd

当B接收到A发送的消息时，其无线接收装置的能耗为：

ERx(k)阀值r0由下式决定：

r0??kEelec (3-2)

?fs/?tr (3-3)

以上公式中，ETx?elec表示启动无线收发电路所消耗的能量，ETx?amp表示放大器消耗的能量，且=87.7m。

Eelec?50J/bit,?fs?10pJ/b/m2,?tr?0.0013pJ/b/m4.由上式可得r03.3 EDEBCRP-MN 协议分簇阶段

EDEBCRP-MN是基于分簇的路由算法，它和LEACH 算法一样，但不同之处是：LEACH 算法是所有传感器节点动态的形成多个簇，且经过一段时间的数据传输之后，会进行重新分簇；而EDEBCRP-MN 算法将所有传感器节点按地理位置划分为多个簇，簇的划分由能量充足的汇聚节点来完成，并且簇一旦形成，分簇在整个稳定数据通信阶段不再变化，当簇头节点出现故障或者能量小于某个阈值时，采用分布式方式在簇范围内重新选举簇头，而不是在整个网络中实行新一轮的聚簇。

EDEBCRP-MN 协议作为层次协议，其分簇过程包括三个阶段，传感器节点被随机地部署在监测区域中后，

20

第一步：通过节点定位算法或者GPS 获得每个节点的能量与位置信息，然后将每个节点的节点能量信息和位置信息发送到汇聚节点，如图3.1（a）所示，节点的通信则满足多路衰减模型，此时能量消耗较大，考虑在整个协议运行过程中只有一次，此后所有节点进入非活动状态，相对于较长时间的稳定工作阶段，这种方法是可取的。

第二步：汇聚节点接收所有节点的位置和能量信息，根据监测区域中节点的数量以及区域内所有节点的能量信息，就近地将整个监测区域划分成若干个小区域，且满足各区域中所有节点能量之和基本相等，划分的每个小区域作为一个簇，同时，将节点的能量划分层次，依次为0、1、2顺序增大，层次之间的能量差不一定是相等的；在每个小区域内选取能量水平值最大的两个节点分别作为簇头节点和管理节点（如果几个节点具有相同的最大能量水平值则选取距离各小区域中心最近的两个节点分别作为簇头节点和管理节点）。

第三步：汇聚节点将分簇信息连带初始路由信息进行广播，如图3.1（b）所示。就将监测区域内所有节点划分为许多簇，并且确定了每个簇的簇头节点和管理节点，划分后的结果如图3.1（c）所示

汇聚节点 普通节点 簇头节点 管理节点

（a） (b) (c) 图3.1 分簇形成过程示意图 3.3.1 管理节点的引入

LEACH 协议采用的是单簇头节点，无线传感器网络环境中，簇头节点数据传输失败通常有三种情况：（1）节点自身能量不足：当簇头节点向汇聚节点发送一次数据所需消耗的能量与簇头节点进行一次数据融合所消耗的能量以及簇头节点接收簇内普通节点发送数据所消耗的能量之和小于簇头节点自身的剩余能量值时。（2）节点硬件故障。（3）节点因环境干扰、障碍物阻挡等引起通道传输出错。

21

综上所述，簇头节点随着稳定通信阶段持续时间拉长，数据连续成功发送到汇聚节点的概率变小，但是由于分簇阶段能量开销较大，维持较长的稳定通讯时间是必要的，于是我们考虑在每个簇内引入一个管理节点来分布式实现簇头的选举。 3.3.2 节点命名机制

EDEBCRP-MN协议提出以下命名机制，将每个区域内的节点用（x，y，n，k）表示，以x和y为横坐标来表示每个区域的位置，其确定方式为各区域簇头节点相对于原点的位置，即以r和?来表示每个区域原点的距离和角度，n表示各区域中普通节点距离簇头节点的半径距离，当n=0时，表示节点为该区域的簇头节点或管理节点。K表示节点位于该区域的第几个角度区间内，取值[0,1,2，?,kmax]， kmax=[2?/?]，?为具体区域内节点角度设定的角度参数。当n=0时，k用来区分节点是簇头节点还是管理节点，设k=0表示为管理节点，k=1表示簇头节点，当n?0时，k依据到坐标轴的角度来区分不同节点，里坐标横轴角度小的为1，依次递增，从而区分相同距离不同角度的节点。 2.3.3 确定最优簇头数

我们可以把节点在监测区域的分布看作一个泊松分布，把监测区域内节点的数量N 当成一个泊松随机变量，不失一般性，我们设汇聚节点在正方形区域的一个顶点，设监测区域为边长2a的正方形，A表示正方形的面积，有A?4a2，N??A，?可以理解为

监测区域内节点密度。设p表示一个节点成为簇头节点的概率，设(xi,yi)，表示一个节点nodei的平面坐标,Di表示节点nodei到汇聚节点的距离，有：

E[Di|N=n]=?A22?1xi?yi?2?4a??dA?1.53a. (3-4) ?因为区域中平均会有np个簇头节点，并且根据泊松分布的特点，任意簇头节点的位置和其它簇头节点的位置是相互独立的，所以所有簇头节点到汇聚节点的总距离为1.53npa。既然节点成为簇头节点的概率是p ，可知节点成为管理节点的概率也是p，成为普通节点的概率是(1? 2p)，所以簇头节点、管理节点和普通节点服从相互独立的泊松分布，分布密度分别为?0?p?0 ，?1?p? ，?2?(1?2p)?。

当整个监测区域划分为许多个小区域，每个小区域中有一个服从密度为?0的泊松分布的簇头节点，我们设NN表示某小区域内普通节点的个数，LL表示普通节点到簇头节点的总长度，则有：

E[LL|N=n]≈E[LL]=

?1?03/2 (3-5)

22

E[NN|N=n]≈E[NN]=

?1?0 (3-6)

设C1 为小区域内普通节点传送一个单位的数据到簇头节点消耗的能量，C2 为监测区域内所有普通节点传送一个单位的数据到各自簇头节点消耗的能量，C3 为所有簇头节点传送融合数据到汇聚节点消耗的能量，C为网络中所有节点消耗的能量，则有：

E[C1|N?n]?E[LL|N?n]r (3-7)

E[C2|N?n]?npE[C1|N?n] (3-8)

1.53npa2r'E[C3|N?n]? (3-9)

E[C|N?n]?E[C2|N?n]?E[C3|N?n]?np(1?p)3/2r2p??1.53npar'. (3-10)

E[C]?E[E[C|N?n]]?E[N][??A[1?P2R1?P2rp?P???1.53par'']1.53par]. (3-11)

不妨我们设r'?2r，则要使E[C]取得最小值，需满足下列等式条件：

?p?1?0. (3-12)

cp3/2求得唯一实根为：poptimal?[13c3?23c??2?3c312],2

2??(2?27c?3327?4)1/3,c?3.06a? (3-13)

所以，最优簇头数目noptimal系。

?npoptimal,poptimal只跟监测区域的大小和节点的分布密度有关

设M=noptimal，节点nodei的能量为enodei，则传感器覆盖区域内所有节点的总能量为E，而每个划分的小区域所包含的所有节点的总能量为e,有：

ME???e11nodei （3-14）

e??e1nodei (3-15)

由E可得

23

E[E|N?n]?e?Enoptimal?EM (3-17)

设?为任意小的实数参数，要求各划分的区域所有节点的能量基本相等，即要满足:

M??e[e?e]?[11nodeiM??e1nodei]?? (3-18)

?的值根据实际环境的不同要求确定，满足上式条件的划分我们称整个区域以能量

均衡为标准的划分。

3.4 EDEBCRP-MN协议报文格式

报文格式：

（xd,yd,nd,kd） (xs,ys,ns,ks) Type Data

设（xd,yd,nd,kd）为目的节点，（xs,ys,ns,ks）为源节点，Type 为报文的类型，Data 为指向报文内容的指针。节点收到信息后首先判断目的节点，如果目的节点为(?1,?1,?1,?1)，表明该信息为广播信息，节点接收数据并根据Type 值判断信息类型进行相应处理；否则节点判断该信息是否是发向自己的，若是，则接收数据并根据Type 值判断信息类型进行相应处理，否则不进行数据接收。 报文主要 Type 类型定义如下：

Type=0：该类报文用于汇聚节点发送任务给簇头节点，或者簇头节点对接收任务进行广播，Data 部分包含采集信息的节点名字和采集任务的时间长度，简称为TASK 报文。

Type=1：该类报文用于采集信息节点发送采集信息到簇头节点，或者簇头节点发送融合数据到汇聚节点，报文内容即为节点采集的数据信息和节点的位置信息，简称为DATA 报文。

Type=2：该类报文用于簇头节点查询簇内普通节点和管理节点的状态，或者管理节点查询簇头节点的状态，Data 部分为空，简称为CNS(Check Node Status)报文。

Type=3：该类报文用于节点对CNS 报文进行回复，Data 部分为空，简称为SON(Status of Node)报文。

Type=4：该类报文用于广播节点死亡消息， Data 部分为空时表明死亡节点 即为源节点，否则，死亡节点在Data部分指明，简称为DON（Death Of Node）报文。

Type=5：该类报文用于簇内普通节点接收到管理节点死亡消息后，传送自身能量

24

信息和位置信息到簇头节点，Data 部分为节点对应的能量信息，简称为PON（Power of Node）报文。

Type=6：该类报文用于管理节点对新当选簇头节点进行广播，Data 部分为新当选簇头节点的相关信息，简称为NCH（New Cluster Head）报文。

Type=7：该类报文用于簇头节点对新当选管理节点进行广播，Data 部分为新当选管理节点的相关信息，简称为MCH（Monitoring Cluster Head）报文。

Type=8：该类报文用于节点广播其最新能量水平值，Data 部分为能量水平值，简称为COP（Change of Power）报文。

3.5 EDEBCRP-MN协议工作过程

3.5.1 节点死亡

由于无线传感器节点本身能量的限制以及周围环境等因素，节点会经常由于能量问题、硬件故障、环境因素等各种问题而无法工作，此时我们称节点死亡。节点死亡有两种可能，第一种情况是能量消耗殆尽而自然死亡，第二种情况是硬件故障或者外界环境因素引起的意外死亡，在该小节中我们只讨论普通节点和管理节点的死亡，关于簇头节点的死亡将会在下文中进行说明。

对于自然死亡，当一个节点的能量水平值由1变为0的时候（此时的节点能量值较小，但不是0），该节点便广播自己死亡的消息（DON 报文）。如果死亡节点是管理节点，簇内普通节点收到管理节点死亡的消息后，将本身位置信息和能量信息（PON 报文）发送到簇头节点，簇头节点从普通节点中选择能量水平值最大的节点作为管理节点，如果能量水平值最大的节点有多个，则选择距离簇头节点最近的节点作为管理节点，然后广播该节点成为管理节点的消息（MCH报文），并为管理节点发送必要的维护信息，普通节点收到簇头节点广播消息后会更新关于管理节点的相关信息；如果死亡节点是普通节点，其邻节点收到该消息后更新路由信息表（设定死亡节点能量水平字段值为0），簇头节点收到该消息后更新节点信息表，并且将节点死亡消息通告汇聚节点，汇聚节点也会对其维护的节点信息表进行更新。

对于意外死亡，当簇头节点启动簇内节点执行汇聚节点发送过来的TASK任务之前，会先查询簇内普通节点和管理节点的状态。簇头节点广播一个查询消息（CNS报文），并且设定一个定时器tout，，簇内普通节点和管理节点收到CNS 报文后会发送一个回复消息（SON 报文）到簇头节点，簇头节点如果在tout内收到某节点的回复消息表明该节点状态正常，否则说明该节点已经死亡。如果死亡节点是管理节点，簇头节点会广播管理节点死亡的消息（DON 报文），以后处理同管理节点的自然死亡相同；如果是普通

25

节点，簇头节点便更新节点信息，并广播该节点死亡的消息，死亡节点的邻近节点收到该节点死亡消息后，更新其路由信息 即可。 3.5.2 更换簇头节点

簇头节点有两种更换方式，一种是簇头节点因能量不足而主动让贤，另一种是簇头节点因发生故障而被迫重新选举簇头节点。因为簇头节点本身要采集数据还要收集簇内节点数据进行数据融合并充当路由节点的角色，所以簇头节点的能量消耗较大，为了不让簇头节点过早的因为能量耗尽而死亡，我们规定当簇头节点的能量水平值变为1 时便宣告其不再为簇头，即广播簇头节点死亡消息（DON 报文），但是此时节点并未退出，而是转为一个普通节点继续工作，然后重新选举簇头节点。簇头节点还有可能因为硬件问题或者外界环境因素而不能正常工作，为了防止簇头节点意外死亡而白白浪费簇内普通节点的能量，我们在每个簇内设置了一个管理节点，管理节点负责侦听簇头节点的活动，不进行数据采集和传输，管理节点一旦发现簇头节点失去作用，便向簇内普通节点广播簇头节点死亡消息，重新选举簇头节点。重新选举簇头节点是怎样进行的呢？簇头节点的更换是在管理节点的主持下完成的。簇内普通节点收到簇头节点死亡消息）后，暂停数据发送，直到新簇头产生为止。邻近单元格簇头节点收到簇头节点死亡消息后，更新其路由信息。管理节点发现簇头节点意外死亡或者收到簇头节点的死亡消息后，将查询节点信息，从簇内节点中选择能量水平值最大的节点作为簇头节点，如果能量水平值最大节点有多个，则选距离单元格中心最近的节点作为簇头节点。然后管理节点为簇头节点建立节点信息和路由信息，最后管理节点广播簇头节点选举完成的消息，邻近簇头节点收到该消息后更新路由信息，簇内普通节点收到该消息后更新簇头节点信息和路由信息，簇头选举工作完成。 3.5.3 簇内路由

因为汇聚节点在节点信息中保存了所有节点的相关信息，所以当用户需要监测区域内某范围的相关信息时，汇聚节点会先计算需要启动哪些节点采集数据，这些节点分别归属于哪个簇，然后便发送数据采集任务TASK 给相关簇头节点，簇头节点收到数据采集任务之后先查询簇内节点状态，然后对任务进行广播，簇内节点接收该任务，判断是否有自己的任务，如果有便启动传感模块进行数据采集，否则节点转入睡眠状态。当节点完成信息采集以后就会传送采集信息至簇头节点，然后簇头节点收集簇内工作节点采集信息后，进行数据融合，再将融合数据发送到汇聚节点。普通节点为了能够正常工作，需要维护自身的相关信息，路由信息，相应簇头节点和管理节点的相关信息。当节点的能量层次改变时，该节点会将其新的能量层次值进行广播，其邻节点收到消息后，对该

26

节点的能量水平值进行更新。在 EDEBCRP-MN 协议中，簇内节点并不像LEACH 协议那样采用单跳方式直接传送采集数据到汇聚节点，它采用多跳路由的方式，现在我们假设普通节点(x, y,n,k)要传送采集数据到簇头节点(x, y,0,0)，具体路由策略如下：

(1) 如果k=1，节点(x, y,n,k)直接传送数据到簇头节点(x, y,0,0)，否则转入（2）。 (2) 计算节点(x, y,n,k)和节点(x,y,n,k-1)的距离r1，(x,y,n,k)和节点(x,y,n,k-2)的距离

r2，节点(x,y,n,k-1)和节点(x,y,n,k-2)的距离r3，如果r22??(r1?r3)22（参数β 是根据具

体情况设定的，具体设定方法在下面会阐述）,传送数据到节点（x,y,n,k-1)，节点（x,y,n,k-1)将本身采集数据和所接收数据进行数据融合，然后依据该路由策略继续发送融合数据到簇头节点，否则转入（3）。

(3) 如果m < 3，节点（x,y,n,k)直接传送数据到簇头节点(x, y,0,0)，否则转入（4）。 (4) 计算节点(x,y,n,k)和节点(x,y,n,k-2)的距离r1，节点（x,y,n,k)和节点）x,y,n,k-3)的距离r2，节点（x,y,n,k-2)和节点(x,y,n,k-3)的距离r3，如果满足r22依据该路由策略继续发送融合数据到簇头节点，否则转入（5）。

(5) 依次类推，判断是否要将(x,y,n,k-3)、(x,y,n,k-4)?作为中继路由节点。总之，节点（x,y,n,k)在传送信息到簇头节点的时候，会依次判断是否把节点(x,y,n,j)，j

22??(r1?r3)22，传送

数据到节点（x,y,n,k-2)，节点(x,y,n,k-2)将本身采集数据和所接收数据进行数据融合，

3.5.4 簇间路由

簇头节点根据汇聚节点的任务，收集簇内普通节点采集的数据，然后对数据进行融合计算，通过多跳路由方式将融合数据通过其连通单元格的簇头节点转发至汇聚节点。设整个无线传感器网络区域被划分为 M×N 个单元格，需要传送数据的簇头节点是(x, y,0,0)，我们把该簇头节点记为Ni，i?路由过程可描述如下：

（1）记簇头节点Hi和相邻节点集合为CN汇聚节点之间的距离分别为di,dj,...,dk记簇头节点和汇聚节点的距离为di，y*M?x?1，

??Hj,...,Hk?,簇头节点Hi,Hj,...,Hk和

，设簇头节点集合CV??HV|HV?CN&dv?di?，

如果CV为空，则簇头节点直接传输融合数据到汇聚节点，否则转入步骤（2）。

（2）在集合CV中选择能量水平值最大的簇头节点，如果能量水平值最大的节点是唯一的，则将该节点作为下一跳的路节点，否则转入步骤（3）。

27

（3）在多个能量水平值最大的簇头节点中选择距离汇聚节点最近的簇头节点作为下一跳的路由节点。

（4）将该路由节点作为起始节点，重复(1)、（2）、（3）步。

这样，在汇集节点和每个需要采集信息的普通节点之间就形成了一条稳定的路径，这使得簇内普通节点传送数据到簇头节点以及簇头节点传送融合数据到汇集节点的过程中，采用了新的路由策略，具有更好的节能性。

28

第4章 EDEBCRP-MN协议性能分析

以下从网络生存时间、节点传送数据到汇聚节点的成功率对LEACH 协议、MRPS 协议、EDEBCRP-MN协议进行比较分析。

4.1 网络生存时间

网络生存时间指从网络开始工作到网络最后一个节点死亡所持续的时间，但网络的生存时间无法直接算出，而只能通过计算网络中每个节点发送一次采集数据到汇聚节点平均消耗的能量来估算网络的生存时间。

4.2 簇头节点发送数据到聚集节点成功率

簇头的产生是簇形成的基础，分簇路由算法的第一步就是考虑怎样产生簇头，在一些协议中，比如ECMR（Energy-Conscious Message Routing），簇头是被预先指定部署的，且假设他们的能量并不受限。这与一般的无线传感器网络不同，大多数分簇路由协议是让能量受限的传感器节点承担簇头的任务。为了延长网络的生命周期，簇头需要周期性的更新。簇头的产生方法、数量和位置决定了最终形成的簇的结构、大小和数量，从而也影响了节点的能量耗费进度和网络的生命周期。

根据簇头产生方式的不同，可以把簇头产生算法分为分布式和集中式两种。分布式算法包括两类：一类是由节点根据某个阈值自主决定是否当选簇头，如LEACH 算法；另一类是通过节点之间的信息交互动态产生簇头，如HEED 算法。集中式算法是指由汇聚节点基于整个网络信息挑选簇头，如LEACH-C算法和本文所述的MRPS 算法。纯粹的分布式算法每轮产生的簇头没有确定的数量和位置，而纯粹的集中式算法在每轮的簇头阶段都需要将网络中所有节点的信息传送到汇聚节点，开销巨大，并且要求稳定数据传输阶段的时间要远远大于分簇阶段时间。EDEBCRP-MN 算法第一轮采用集中式算法形成簇并产生簇头节点和管理节点，以后便采用分布式算法由管理节点主持完成簇头节点的重新选举，这样不仅克服了纯粹集中式簇头产生方式或者纯粹分布式簇头产生方式的缺点，还大大提高了簇头节点传送数据到汇聚节点的成功率。

我们假设三种算法稳定数据通讯时间均为Tdata(实际上，我们提出的EDEBCRP-MN 算法由汇聚节点将监测区域固定划分为多个簇之后，以后便采用分布式簇头产生方式产生簇头，各个簇的稳定数据通讯时间不是同步的），设共有nc个簇头节点，平均每个簇头节点传送一次数据到汇聚节点时间为t，设m?[Tdata/t]，如果节点能量无限且不会发

生任何硬件故障，则在Tdata内汇聚节点共接收到来自簇头节点的数据mnc次（包括间接

29

接收）。但是实际上我们必须考虑节点能量不足或者硬件故障等原因，假设在时间t 内，每个簇头节点因能量不足或硬件故障等原因发送数据失败的概率为Pf。

30

总结

本文主要分析实际的无线传感器网络模型特点，分析指出无线传感器网络存在的最大不足是系统的能耗，并针对这一缺点提出无线传感器网络的首要设计目标是节能，延长网络的生命周期。本文在以后各章节主要介绍了无线传感器网络的节点结构、网络协议栈，分析了传感器节点的能量消耗情况，发现无线传感器节点大部分能量都消耗在无线通信模块，所有路由协议的设计对无线传感器网络的性能至关重要，因此，本文对无线传感器网络的路由协议进行了深入的研究和分析。通过大量的研究，我们发现分簇路由协议具有拓扑管理方便、能量利用率高、数据融合简单等优点，成为当前路由技术研究的重点。但是，目前所提出的分簇路由协议整体性能表现良好的并不多，还有待进一步改善。因此，本文提出一种基于能量均匀分配的带管理节点的分簇路由协议——EDEBCRP-MN协议。

EDEBCRP-MN协议综合考虑了网络节点负载平衡、多跳、节点剩余能量和数据融合等因素，并提出以下创新研究：

（1）建议了集中式固定分簇和分布式簇头选举结合的策略，首先利用汇聚层节点进行集中式固定分簇，在随后稳定通信阶段分布式实现簇头的重新选举，以减少分簇阶段的能量消耗，延长网络的生命周期。

（2）建议了一种新的节点命名机制——用一个四元组（x,y,n,k）来表示一个节点，容易区分出物理位置相近的节点，避免位置相近的节点发送冗余数据，并且使路由选择更加容易。

（3）在每个簇内引入一个管理节点，该节点在稳定数据通信数据阶段负责监督簇头节点的状态，当发现簇头节点能量不足或者意外死亡时，主持完成簇头节点的重新选举，曾强了系统的鲁棒性。

（4）在簇内普通节点传送数据到簇头节点和簇头节点传送融合数据到汇集节点的过程中，采用了新的路由策略，具有较好的节能性。

本文针对无线传感器网络的特点提出了EDEBCRP-MN协议，它主要从节能方面考虑，延长了网络的生命周期，具有很好的实用价值。由于知识结构和时间有限，本文对无线传感器网络的介绍很有局限，还可从以下三个角度入手进一步解决无线传感器网络分簇路由的问题：

(1) 在簇头选择中，考虑更有效的簇头选择算法和簇头负载平衡算法。一

31

般来说，我们都是基于节点的某个属性来选择簇头，这个属性的选取与具体应用有关，反映系统倾向于何种性质的节点成簇头，比如本文所提出的EDEBCRP-MN算法是选择能量最大并且距离划分区域中心较近的节点作为簇头节点，但是这并非挑选簇头的唯一约束因素，在复杂的特定应用中，我们还必须考虑节点的位置、到汇聚节点的距离、计算能力和移动性等因素。另外，簇头的数量和位置分布对网络的负载平衡具有重大影响，也需要我们进一步的研究。

（2）信号干扰是分簇路由的一大困扰，解决这个问题一方面需要来自数据链路层的支持，另一方面，信号分配以簇的形成紧密相关，如何把二者结合起来，降低网络初始化的功耗，也是分簇算法需要深入考虑的问题。

（3）能量感知的QoS分簇路由越来越受到重视，它将在目标的实时追踪等方面得到应用，也是我们以后研究的一个方向。 本人对无线传感器网络的认识还不够深入、全面，文中会有一些疏漏和错误也在所难免，敬请阅读本文的各位老师和同学加以批评指正。

32

本文来源：https://www.bwwdw.com/article/rtcr.html