无线传感器网络flooding路由协议的MATLAB仿真

摘 要

无线传感器网络是计算机科学技术的一个新的研究领域，是传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术相结合的产物。与传统网络相比，无线传感器网络具有造价低、功耗低、布局灵活性强、监测精度高等特点，因此在军事、医疗、家用等多个领域均有广阔的应用市场。

本文重点研究基于无线传感器网络的泛洪式路由协议，无线传感器网络节点数量庞大、单个节点资源有限，其路由协议设计的首要目标是提高能量有效性，延长网络寿命。本文总结了WSN的概念、结构、特点，分析了WSN的关键性技术问题及网络协议；研究了WSN的网络协议体系和路由协议的分类，分析比较了目前国内外学者提出的几种有代表性的路由协议及其性能优缺点；选择了flooding路由协议为研究重点，分析了该路由算法的具体实现，针对传感器节点能量及传输范围有限等特点，提出了一种基于延迟的自适应泛洪路由算法，首先通过源节点在网内用较小的路由请求报文和路由回复报文来建立路由，路由建立的过程中自适应地确定等待时间以使更优的路由请求报文得到转发，然后源节点再沿着建立好的路径转发较大的数据报文。并采用MATLAB网络仿真工具对该路由协议进行了整体仿真，并对其数据进行了分析。仿真实验表明新算法较Flooding节能，能较好的克服Flooding算法中报文冗余度高、能耗大等不足。

关键词：无线传感器网络；flooding路由协议；MATLAB仿真

ABSTRACT

Wireless sensor networks are a new research field of computer science and technology. They are the integration of sensor techniques, nested computation techniques, distributed computation techniques and wireless communication techniques. Comparing with traditional networks, the wireless sensor networks features with low cost, low power loss, flexible layout and high monitor precision, therefore the sensor networks can be used for various application are as such as military, chemical, home.

This article focus on wireless sensor networks based on the Pan Hung-routing protocol, wireless sensor network nodes large number of individual nodes with limited resources, the routing protocol designed first and foremost objective is to improve energy efficiency and extend the network lifetime. This paper summarizes the WSN the concept, structure and characteristics of the WSN the key technical problems and network protocols; study of the WSN system and network routing protocol agreement the classification, analysis and comparison of the current domestic and foreign scholars have proposed several representatives The routing of the agreement and its performance advantages and disadvantages; chosen the flooding focus on routing protocols, analysis of the routing algorithm to achieve the specific, the sensor nodes the limited scope of energy and transmission characteristics, a delay based on the Adaptive Flood routing algorithm, first of all through the nodes in the network source in the smaller routing, and routing the request to restore the text to create a routing, routing the process of establishing adaptive to determine the waiting time to make better Routing the request was transmitted by text, and then another source nodes along the path forward the establishment of good data on the larger text. MATLAB and use the network simulation tool for the overall routing protocol simulation, and the data were analyzed. The simulation shows that the new algorithm than Flooding energy-saving, can better overcome Flooding algorithm message redundancy and high energy consumption, such as the insufficient.

Keywords：WSN；flooding routing protocols；MATLAB Simulation

目 录

1 绪 论 .................................................................................................................................... 1

1.1 课题背景 .................................................................................................................... 1 1.2 国内外技术研究现状 ................................................................................................ 2 1.3 课题研究的目的和意义 ............................................................................................ 3 2 WSN综述 ............................................................................................................................ 4

2.1 WSN的概念 .............................................................................................................. 4 2.2 WSN的结构 .............................................................................................................. 4

2.2.1 节点结构 .......................................................................................................... 4 2.2.2 网络体系结构 .................................................................................................. 5 2.3 WSN协议栈 .............................................................................................................. 6 2.4 WSN的拓扑结构 ...................................................................................................... 7 2.5 WSN的特点 ............................................................................................................ 10

2.6 WSN的关键性技术问题 ................................................................................. 11 2.6.1 功耗问题 ........................................................................................................ 12 2.6.2 节能策略 ........................................................................................................ 12 2.6.3 通信问题 ........................................................................................................ 14 2.6.4 网络安全问题 ................................................................................................ 15 2.6.5 定位问题 ........................................................................................................ 15 2.6.6 数据管理 ........................................................................................................ 15 2.6.7 服务质量 ........................................................................................................ 16 2.6.8 嵌入式操作系统 ............................................................................................ 16

3.WSN路由协议算法分析 ..................................................................................................... 17

3.1 WSN路由协议的分类方法 .................................................................................... 17 3.2 几种典型路由协议的分析 ...................................................................................... 18

3.2.1 平面路由协议 ................................................................................................ 18 3.2.2 分层路由协议 ................................................................................................ 22

4 Flooding路由协议的分析与研究 .................................................................................... 27

4.1 泛洪算法模型 .......................................................................................................... 27

4.2 算法流程图 .............................................................................................................. 28 4.3 基于延迟的自适应洪泛路由算法 .......................................................................... 29

4.3.1 算法中用到的报文和数据 ............................................................................ 29 4.3.2 SFD算法描述 ................................................................................................ 30 4.3.3 性能比较尺度 ................................................................................................ 31 4.3.4 理论分析 ........................................................................................................ 32

5 Flooding路由协议的MATLAB仿真 .............................................................................. 35

5.1 MATLAB仿真平台介绍 ......................................................................................... 35 5.2 算法仿真实验参数 .................................................................................................. 38 5.3 实验结果 .................................................................................................................. 39 6 结 论 ................................................................................................................................. 42 致 谢 ........................................................................................................................................ 43 参考文献 .................................................................................................................................. 44 附录A：英文原文 .................................................................................................................. 45 附录B：中文翻译 .................................................................................................................. 51 附录C：程序代码 .................................................................................................................. 55

沈阳理工大学学士学位论文

1 绪 论

1.1 课题背景

无线传感器网络是新兴的下一代传感器网络，最早的代表性论述出现在1999年，题为“传感器走向无线时代”。随后在美国的移动计算和网络国际会议上，提出了WSN下一个世纪面临的发展机遇。2003年，美国《技术评论》杂志在论述未来新兴十大技术时，WSN名列第一；同年，美国Business week预测的未来四大新技术：效用计算、传感器网络、塑料电子学和仿生人体器官，QSN也列入其中。2004年 ((IEEE spectrum》杂志发表一期专集《传感器的国度》，论述了WSN的发展和可能的广泛应用。可以预计，WSN的发展和广泛应用，将对人们的社会生活和产业变革带来极大的影响和产生巨大的推动。有专家预计，WSN的广泛应用是一种必然趋势，它的出现将会给人类社会带来极大的变革。传感器网络的发展主要经历了4代：

(1)第一代：上世纪70年代，就出现了具有简单模拟信号传输功能的传统传感器所组成的点对点输出的测控系统网络。该网络具有简单信息获取能力，只是初步实现了信息的单向传递，其缺点是布线复杂、抗干扰性差。

(2)第二代：随着相关学科的不断发展和进步，传感器网络具有了获取多种信息的综合处理能力，并通过采用串/并接口与传感控制器的相联，组成了有信息综合和处理能力的传感器网络。

(3)第三代：20世纪90年代后期，出现了基于现场总线技术的智能传感器网络。现场总线是连接智能化现场设备和控制室的全数字、开放式的双向通信网络智能传感器的通信技术进入局域网阶段，其局部测控网络通过网关和路由器可以实现与Intimae灯Intranet连接。

(4)第四代：大量多功能传感器被运用，并采用无线通信机制，因此也称为。WSN，正处于研究和开发阶段。

WSN是一种无基础设施的网络，由一定数目的传感器节点构成，它综合了 传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能协作地 实时监测、感知和采集节点部署区域的各种环境或监测对象的信息(如光强、温 度、湿度、噪音和有害气体浓度等物理现象)，并对这些数据进行处理，获得详

1

沈阳理工大学学士学位论文

尽而准确的信息，通过无线网络最终发送给观察者。在环境监测、医疗护理、抢 险救灾、智能家居、工业生产控制以及商业等领域具有广阔的应用前景。

1.2 国内外技术研究现状

目前，国内外WSN研究主要集中于网络协议、能量、定位、可靠性、网络架构以及数据处理等问题，网络协议的研究是其中的热点之一。针对无线自主网络的特点，经过多年的研究，国内外的研究人员相继提出了许多专门应用于无线自主网络的路由协议。目前提出的各种路由协议基本上可以按照三种思路进行分类。

(1) 按照获取路由信息的时机分类，可分为主动路由协议和按需路由协议。主动路由有DSDV、WRP、STARA；按需路由协议主要有DSR、AODV。

(2) 按照网络的层次分类，可分为平面结构路由和层次结构路由。平面路由协议主要有flooding、SPIN、DD、HREEMR、SAR；层次结构路由主要有LEACH、PEGASIS等。

(3) 按照协议的功能分类，可分为支持地理定位辅助路由和不支持地理定位辅助路由；支持服务质量QoS的路由协议和不支持QoS的路由协议；支持组播通信的路由协议和不支持组播通信的路由协议等。地理定位辅助协议主要有MECN和SMECN。

无线传感器网络的研究起始于20世纪90年代末期，由于具有巨大的应用价值，它己经引起了世界许多国家的军事界、工业界和学术界的极大关注。从2000年起，国际上开始出现一些有关传感器网络研究的报道，美国自然科学基金委员会2003年制定了传感器网络研究计划，支持相关基础理论的研究。在美国自然科学基金委员会的推动下，美国的加州大学伯克利分校、麻省理工学院、康奈尔大学、加州大学洛杉矶分校等学校开始了传感器网络的基础理论和关键技术的研究。美国国防部和各军事部门都对传感器网络高度重视，把传感器网络作为一个重要研究领域，设立了一系列的军事传感器网络研究项目。美国英特尔公司、微软公司等信息业巨头也开始了传感器网络方面的研究工作。日本、德国、英国、意大利等科技发达国家也对无线传感器网络表现出了极大的兴趣，纷纷展开了该领域的研究工作。

我国在WSN方面的研究工作刚刚开始，清华大学、电子科技大学、哈尔滨工业大学等单位已经进行了该领域的研究工作，但目前主要集中在介绍国外的研究进展，提出新的研究问题，尚未见有新的协议提出。由于WSN是一门新兴技术，IEEE尚未成立WSN的标准制定小组，美国也是在2000年才开始出现一些有关WSN研究结果的报道，

2

沈阳理工大学学士学位论文

所以国内与国际水平的差距并不大，电子科技大学计算机学院正在开展WSN路由协议的设计和仿真工作，力争在5年内达到国际水平。但WSN尚未达到完全实用阶段，大部分工作仍处在仿真和实验阶段，仿真规模在数百至数千个节点，实验规模在几十个节点左右。

1.3 课题研究的目的和意义

如前所述，WSN有着广泛而有价值的应用领域，比如水工建筑物安全监测，大型工程建筑物的运行安全，结合现代监测理论及WSN技术，布置节点实现无人值守，为设计施工及时反馈信息，对减轻观测的劳动强度，提高安全监控的技术水平，具有重大的社会经济效益和应用价值。而在个人通信和接入网等方面的应用则具有良好的商业前景。因此，对WSN网络技术的研究既有重要的社会意义又蕴含着潜在的经济价值。因此它已经引起了世界工业界和学术界的极大关注，开展这项对人类未来生活影响深远的前沿科技的研究，对整个国家的社会、经济将有重大的战略意义。而从网络层模型的角度分析，每一层都有需要结合WSN的特点进行细致研究的问题，己有的研究主要集中在网络层和链路层。

网络数据传输离不开路由协议，路由协议是其组网的基础。路由技术是WSN通信层的核心技术。路由选择问题是WSN网络构建时所要着重考虑的一个问题，从路由的角度来看，WSN有其自身的特点，使它既不同于传统网络，又不同于无线自组网Ad hoc网络。传统的无线Ad hoc网络路由协议不适合用于WSN，我们必须设计全新的、适合于WSN特点的路由协议。

路由协议作为影响网络性能的一个重要因素，是确保WSN网络正常运行的关键。虽然己提出了很多的协议，但是到底那一种是最合适的还没有一个定论。因此研究这些路由协议，比较分析哪一种路由协议是相对合适的显得尤为重要，也是此论文的意义所在。本课题重点研究基于无线传感器网络的泛洪式路由协议，无限传感器网络节点数量庞大、单个节点资源有限，其路由协议设计的首要目标是提高能量有效性，延长网络寿命。本文总结了WSN的概念、结构、特点，分析了WSN的关键性技术问题及网络协议；研究了WSN的网络协议体系和路由协议的分类，分析比较了目前国内外学者提出的集中有代表性的路由协议及其性能优缺点；选择了flooding路由协议为研究重点，分析了该路由算法的具体实现，并采用MATLAB网络仿真工具对flooding路由协议进行了整体仿真，并对其数据进行了分析。

3

沈阳理工大学学士学位论文

2 WSN综述

无线传感器网络是传感器技术、网络通信和计算机技术的集大成者，是一种全新的信息获取和处理技术。美国《技术评论》杂志在论述未来新兴十大技术时, 更是将无线传感器网络名列第一；美国Business Week 预测的未来四大新技术：效用计算、传感器网络、塑料电子学和仿生人体器官，无线传感器网络也列入其中。有专家预计，无线传感器网络的广泛应用是一种必然趋势，它的出现将会给人类社会带来极大的变革。

2.1 WSN的概念

无线传感器网络是由一个个具有数据采集、计算和通信能力的传感器节点，通过自组织网络形成的一个动态、自适应的分布式计算平台。每个传感器都是典型的嵌入式系统，具有存储容量小、运算能力差、功耗低、易失效的特点。

2.2 WSN的结构

2.2.1 节点结构

在不同应用中，传感器节点的结构不尽相同，但一般都由传感器模块、处理器模块、无线通信模块和能量供应模块四部分组成，如图2.1所示。传感器模块负责监测区域内信息的采集和数据转换，传感器的类型是由被监测物理信号的形式决定的，如用于温度监测的铂电阻传感器，用于压力传感的电容式传感器等;处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其他节点发送来的数据;无线通信模块负责与其他传感器节点进行无线通信，交换控制信息和收发采集数据;能量供应模块为传感器节点提供运行所需的能量，通常采用微型电池，不过已有公司探索从周围环境取得能量并将其转换成微瓦电能的方法。

4

沈阳理工大学学士学位论文

能量供应模块

图2.1 传感器网络节点结构

处理器 传感器 AC/DC 存储器 网络 MAC 无线通信模块 处理器模块 收发器 传感器模块 2.2.2 网络体系结构

在传感器网络中,节点任意散落在被监测区域内,这一过程是通过飞行器撒播、人工埋置和火箭弹射等方式完成的。节点以自组织形式构成网络,通过多跳中继方式将监测数据传到sink节点,最终借助长距离或临时建立的sink链路将整个区域内的数据传送到远程中心进行集中处理。卫星链路可用作sink链路,借助游弋在监测区上空的无人飞机回收sink节点上的数据也是一种方式,UC Berkeley在进行UAV(unmanned aerial vehicle)项目的外场测试时便采用了这种方式。如果网络规模太大,可以采用聚类分层的管理模式,图2.2给出了传感器网络体系结构一般形式的描述。

5

沈阳理工大学学士学位论文

图2.2 传感器网络的体系结构

2.3 WSN协议栈

无线传感器网络协议栈包括物理层、数据链路层、网络层、传输联网协议栈的五层协议相对应，如图2.3所示。另外，协议栈还包括动管理平台和任务管理平台。这些管理平台使得传感器节点能够按照同工作，在节点移动的传感器网络中转发数据，并支持多任务和资源平台的功能如下：

(1) 物理层提供简单但健壮的信号调制和无线收发技术； (2) 数据链路层负责数据成帧，帧检测、媒体访问和差错控制； (3) 网络层主要负责路由生成与路由选择；

(4) 传输层负责数据流的传输控制，是保证通信服务质量的重要； (5) 应用层包括一系列基于监测任务的应用层软件；

(6) 能量管理平台管理传感器节点如何使用能源，在各个协议层量；

(7) 移动管理平台检测并注册传感器节点的移动，维护到汇聚节感器节点能够动态跟踪其邻居的位置；

(8) 任务管理平台在一个给定的区域内平衡和调度检测任务。

6

沈阳理工大学学士学位论文

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

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

能量管理平台移动管理平台任务管理平台 2.4 WSN的拓扑结构

在无线传感器网络中，传感器节点是体积微小的嵌入式设备，采用能量有限的电池供电，它的计算能力和通信能力十分有限，所以除了要设计能量高效的MAC协议、路由协议以及应用层协议之外，还要设计优化的网络拓扑控制机制。对于自组织的无线传感器网络而言，网络拓扑控制对网络性能影响很大。良好的拓扑结构能够提高路由协议和MAC协议的效率，为数据融合、时间同步和目标定位等很多方面提供基础，有利于延长整个网络的生存时间。所以，拓扑控制是传感器网络中的一个基本问题。

在无线传感器网络中，网络的拓扑结构控制有着十分重要的意义，主要表现在以下几个方面:

(1) 影响整个网络的生命周期。基于无线传感器网络有限的能量，节能是网络设计主要考虑的问题之一，拓扑控制的一个重要目标就是在保证网络连通性和覆盖率的情况下，尽量合理高效地使用网络能量，延长整个网络的生存时间。

(2) 减小节点间通信干扰，提高网络通信效率。无线传感器网络中节点通常密集分布，如果每个节点都以大功率进行通信，会加剧节点之间的干扰，降低通信效率，并造成节点能量的浪费。另一方面，如果选择太小的发射功率，会影响网络的连通性。 (3) 为路由协议提供基础。在无线传感器网络中，只有活动的节点才能进行数据转发，而拓扑结构控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。 (4) 影响数据融合。无线传感器网络中的数据融合指传感器节点将采集的数据发送给中

7

沈阳理工大学学士学位论文

心节点，中心节点进行数据融合，并把融合后的数据发送给汇聚节点。而中心节点的选择是拓扑结构控制的一个重要内容。

(5) 弥补节点失效的影响。传感器节点可能部署在恶劣的环境中，在军事应用中甚至部署在敌方区域中，所以很容易受到破坏而失效。这就要求网络拓扑结构具有鲁棒性以适应这种情况。

无线传感器网络特定的应用环境及其固有的特征，对传感器网络拓扑结构的设计提出了新的要求。在无线传感器网络中，节点需要完全以自组织的形式构成自治型网络，并且能够工作在无人值守的恶劣环境当中。到目前为止，无线传感器网络拓扑结构的研究主要集中在两个方向，即平面型拓扑结构和层次型拓扑结构。 (1) 平面型拓扑结构

平面型拓扑结构，所有节点的地位平等、作用相同，既采集数据又进行数据通信的中转，网络中不存在集中式控制中心。为了有效地节省能量，远距离节点之间以多跳通信方式，如图2.4所示。平面结构网络比较简单，无需任何的结构维护过程，节点根据预定的路由协议自组织成无线网络。由于随机分布、高密度等特性，源节点和目的节点之间可能存在多条传输路径，如图2.4中节点A和E之间存在两条路径:A一>C一>D一>E和A一>C一>F一>E，既可以使用多条路径实现负载分担，也可以为不同的数据传输需求选择适当的路径。平面结构网络中所有的传感器节点理论上是对等的，不存在瓶颈和单点故障，所以比较健壮，但是网络规模受限，动态扩展性差，难以维护。在平面结构中，源节点为了获得目的节点信息通常需要传输大量的查询消息，而且由于网络的动态性，如节点失效、增加等，维护这些动态变化的路由信息需要发送大量的控制消息。网络规模越大路由维护的开销就越大，当网络的规模增加到某个程度时，网络的所有带宽可能被路由协议消耗掉，所以平面式结构的网络扩展性较差。

8

沈阳理工大学学士学位论文

Sink Internet D 传感器节点 传感区域 C A B E F

图2.4 平面型拓扑结构

(2) 层次型拓扑结构

层次型拓扑结构中，网络根据具体应用需求，如地理区域、能源、应用类型等，划 分为簇(Cluster)，每个簇由一个簇头节点和多个簇成员构成，多个簇头节点抽象成高 一级的网络，在高一级网络中可以继续分簇，形成更高一级网络，最终形成多层次组织 结构的传感器网络，如图2.5所示。

簇头 传感器节点 A C2 B C1 C3 图2.5 层次拓扑结构

层次型拓扑结构中，不同层次以自己的局部概念进行交互，聚集起来实现期望的全

9

沈阳理工大学学士学位论文

局任务。分层组织结构中，簇内成员节点负责感知任务，以多跳方式将采集的信息发送到簇头节点。簇头节点作为簇类的中心节点，担负着与远程终端通讯、发布簇类管理信息、执行更高层次的数据融合和数据分析等使命。为了有效利用能源和延长网络的生命周期，簇头节点通常依据能量概率分布由网络节点轮流充当。这样可以使簇头节点的高能量消耗平均到网络节点上，同时也避免了固定簇头引起的网络的脆弱性和不稳定性，

而且可以通过簇拆分来增加簇的个数或者簇聚合形成更高一级网络来提高整个网络的容量。但缺点是，为了维护层次化结构需要仔细设计簇头选择算法。而且簇间节点为了完成数据通信需要经过簇头转发，因此不一定能使用最佳路由，例如图2.5中的A、B节点，物理距离很接近，在平面结构中可以直接通信，但分簇后需要通过两个簇的簇头中继进行通信。

2.5 WSN的特点

(1) 传感节点体积小，成本低，计算能力有限

无线传感器网络是在MEMS技术、数字电路技术基础上发展起来的，传感节点各部分集成度很高，因此具有体积小的优点，当然从应用角度讲，减小节点尺寸也是必须考虑的设计要素。传感网络是由大量的传感节点组成的，单个节点的成本直接影响到网络的总体成本，如果总体成本比使用传统传感器的成本高，势必会影响无线传感网络的竞争力。由于体积、成本以及能量的限制，嵌入式处理器和存储器的能力和容量有限，因此传感器的计算能力十分有限。

(2) 传感节点数量大、易失效，具有自适应性

根据应用的不同，传感器节点的数量可能达到几百万个甚至更多。此外，传感器网络工作在比较恶劣的环境中，经常有新节点加入或已有节点失效，网络的拓扑结构变化很快，而且网络一旦形成，人很少干预其运行。因此，传感器网络的硬件必须具有高强壮性和容错性，相应的通信协议必须具有可重构和自适应性。 (3) 通信半径小，带宽很低

无线传感器网络是利用多跳来实现低功耗下的数据传输，因此其设计的通信覆盖范围只有几十米。和传统无线网络不同，传感器网络中传输的数据大部分是经过节点处理过的数据，因此流量较小。根据目前观察到的现象特性来看，传感数据所需的带宽将会很低(l~100kbi灯s)。 (4) 电源能量是网络寿命的关键

10

沈阳理工大学学士学位论文

无线传感器网络中通常运行在人无法接近的恶劣甚至危险的远程环境中，能源无法替代，只能选择钮扣式电池供电，电源能量极其有限，网络中的传感器由于电源能量的原因经常失效或废弃，因此电源效率是设计考虑的关键因素。 (5) 以数据为中心的网络

对于观察者来说，传感器网络的核心是感知数据，而不是网络硬件。比如在智能家居应用中人们可能希望知道“现在客厅的温度室多少”，而不会关心“2号节点感测到的温度是多少”。以数据为中心的特点要求传感器网络的设计必须以对感知数据的管理和处理为中心，把数据库技术和网络技术紧密结合，从逻辑概念和软、硬件技术两个方面实现一个高性能的以数据为中心的网络系统，使用户如同使用通常的数据库管理系统和数据处理系统一样自如地在传感器网络上对感知数据进行管理和处理。

2.6 WSN的关键性技术问题

无线传感器网络与传统的无线网络(如WLAN和蜂窝移动电话网络)有着不同的设计目标，后者在高度移动的环境中通过优化路由和资源管理策略最大化带宽的利用率，同时为用户提供一定的服务质量保证。在无线传感器网络中，除了少数节点需要移动以外,大部分节点都是静止的。因为它们通常运行在人无法接近的恶劣甚至危险的远程环境中,能源无法替代，设计有效的策略延长网络的生命周期成为无线传感器网络的核心问题。

当然,从理论上讲,太阳能电池能持久地补给能源，但工程实践中生产这种微型化的电池还有相当的难度。在无线传感器网络的研究初期，人们一度认为成熟的Internet技术加上Ad-hoc路由机制对传感器网络的设计是足够充分的,但深入的研究表明:传感器网络有着与传统网络明显不同的技术要求。前者以数据为中心,后者以传输数据为目的.为了适应广泛的应用程序,传统网络的设计遵循着“端到端”的边缘论思想,强调将一切与功能相关的处理都放在网络的端系统上,中间节点仅仅负责数据分组的转发,对于传感器网络,这未必是一种合理的选择。一些为自组织的Ad-hoc网络设计的协议和算法未必适合传感器网络的特点和应用的要求。节点标识(如地址等)的作用在传感器网络中就显得不是十分重要,因为应用程序不怎么关心单节点上的信息；中间节点上与具体应用相关的数据处理、融合和缓存也显得很有必要。在密集性的传感器网络中,相邻节点间的距离非常短,低功耗的多跳通信模式节省功耗,同时增加了通信的隐蔽性,也避免了长距离的无线通信易受外界噪声干扰的影响。这些独特的要求和制约因素为传感器网络的研究提出了新

11

沈阳理工大学学士学位论文

的技术问题。 2.6.1 功耗问题

作为一种微电子设备，无线传感器节点只能配置电池，电池电量一般小于0.SAh，电压为1.2v-3.3V。在一些具体应用中，电池更换是不现实的。

所以，节点生命期严重依赖于电池供电的持续时间。在WSN中，每个节点都起着数据采集器和路由器的双重作用。一些节点的故障会引起拓扑的明显变化，可能要求重建路由或重组织网络。所以，能量保护和能量管理至关重要。传感节点的主要功能是感知、处理和数据传输，其能耗也主要分布在这三个方面。感知能耗与具体应用环境中携带的不同传感单元有关。通信能耗在节点能耗中比例最大，需要考虑启动功耗、接收功耗和发送功耗，无线电收发器能耗公式如下:

Pc?NT?PT?TOn?Tst??POUTTOn??NR?PR?ROn?RST??

（2.1）

其中，Pc为无线通信功耗；PT和PR分别为无线发送和接收器件的功耗；PouT为无线发送器的输出功率；Ton、Ron伽分别为每个单位时间内无线发送器和无线接收器的打开的时间；Tst、RST分别为发送和接收的启动时间；NT、NR为单位时间内接收和发送的次数，依赖于任务和采用的媒介访问控制(MAC)策略；Ton也可写成L/R，L为数据包大小，R为数据传输速率。数据处理功耗比通信功耗要小得多，例如:假定瑞利衰落且能量与距离的4次方成正比损耗，实验表明，无线传输1K比特的数据100米的能量可以让l00MIPS/W的处理器处理300万条指令。因此尽可能地进行本地数据处理而减少数据的无线传输是降低WSN能耗的有效办法之一。

针对数据采集、接收、发送和计算这四者的能耗问题，curt Schurgers等人进行了实验。实验结果表明，发送数据(Tx)的能耗略大于接收数据(Rx)，二者远大于数据处理(计算)和数据采集的能耗。 2.6.2 节能策略

由于无线通信是WSN能耗的主要部分，因此对无线收发系统的能耗管理非常重要，可以采取以下措施减少通信模块的能量损耗。 (l)减少通信流量

减少通信流量的方法有：a.本地计算和数据融合b.减少冲突，增加错误检测和校正机制d.减少控制包的开销和包头长度。

12

沈阳理工大学学士学位论文

(2)增加睡眠时间

无线通信模块有发送、接收、空闲和睡眠4种状态。无线通信模块在空闲状态一直监听无线信道的使用情况，检查是否有数据发送给自己，而在睡眠状态则关闭通信模块。从实验中可以看到：无线通信模块在发送状态的能量消耗最大，而在空闲状态和接收状态的能量消耗接近，略少于发送状态的能量消耗，在睡眠状态的能量消耗最少。因此不需要通信时，尽快进入睡眠状态是WSN协议设计重点考虑的问题。 (3)采用多跳短距离无线通信方式

无线通信消耗能量E与通信距离d的关系为E=kdn。其中，参数n满足关系2≤n<6，考虑诸多因素，一般取n为3。随着通信距离的增加，能耗将急剧增加。因此，在满足通信速率的前提下，应该尽量减少单跳通信距离。一般传感器节点的通信半径在10Om以内较为合适。

(4)动态功率管理(dynamic power management，简称DPM)

DPM技术的核心问题是状态转换策略，由于状态转换需要消耗一定的能量并且带有时延，如果状态转换策略不合适，不仅无法节能，反而会导致能耗的增加，还会影响实时性能。DPM的状态转换可如图2.6所示，假定状态转换分别发生在t1和t2时刻，其中t2=ti+t1，在tl时刻节点K想要从Sm状态进入休眠状态Sn，在t2时刻需要从Sn返回到Sm状态，每个状态都有对应的能耗Pm和Pn，状态转换分别需要时间tdk和tuk则能量节约如公式所示:

Esave?Pm?ti??Pm?Pn?/2??tdk?tuk??Pn??ti?tdk?

（2.2）

只有当ti大于某一数值时，Esave才能大于零，从而实现节能。 E Pm

Pn tdk t1 t1 t2 Sm Sn tuk t 图2.6 状态转换和能量的关系

13

沈阳理工大学学士学位论文

(5)动态电压调度(dynamic voltage scheduling，简称DVS)

DVS的主要原理是基于负载状态动态调节供电电压来减小系统功耗，并被应用到PDA之类的个人移动设备上。可将其应用到WSN中，如图2.7所示的功率控制原理图。节点上的嵌入式操作系统负责调度来自不同任务队列的请求接受服务，并实时监测处理器的利用率和任务队列的长度，负载观测器依据这两个参数的序列值计算负载的标称值。，直流/直流变换器参照该值输出幅值为A的电压，支持处理器的正常工作。这构成了一个典型的闭环反馈系统。控制理论中成熟的方法可以为该系统中各个模块的设计提供有力的支持。传感器节点大部分时间计算负载较低，在低负载时调低微处理器的电压可以有效节约能量。

标准电压

图2.7:DVS功率控制原理图 Vrixod W DC/DC V（A） r 负载观测器 L 带可变电压的处理器 2.6.3 通信问题

WSN内正常通信联系中，信号可能被一些障碍物或其它电子信号干扰而受到影响，如何安全有效的进行通信是个有待研究的问题。WSN需要具有能对信道衰落不敏感、发射信号功率谱密度低、低截获低功耗短距离的无线通信技术。IEEE802.15.4标准是针对低速无线个人域网络的无线通信标准，由于它的网络特征和WSN存在很多相似之处，故很多研究机构将它作为WSN的无线通信平台。超宽带技术(UWB)是一种极具潜力的无线通信技术。超宽带技术具有系统复杂度低、能提供精确至数厘米的定位精度

14

沈阳理工大学学士学位论文

等优点，非常适合应用于WSN。 2.6.4 网络安全问题

安全是系统可用的前提，WSN是网络家庭的新成员，像其他网络一样需要考虑安全问题。WSN的安全问题主要以下几个方面： (1) 传统无线电磁干扰； (2) 对路由机制进行攻击；

(3) 对能量的攻击，侵入节点导致网络的某些节点和网络段互发大量的垃圾数据，使WSN能量迅速耗尽，网络分立，形成监测黑洞，无法完成正常的监测工作；

针对以上各种不同的攻击方式，一般可采用扩频通信、sensor接入认证/鉴权、数据水银和数据加密技术以提高网络的安全性。基本思想有两种:一种是从维护路由安全的角度出发，寻找尽可能安全的路由以保证网络的安全。如果路由协议被破坏导致传送的消息被篡改，那么对于应用层上的数据包来说没有任何的安全性可言。另一种是把着重点放在安全协议方面。 2.6.5 定位问题

WSN的定位机制与算法包括两部分:节点自身定位和外部目标定位，前者是后者的基础。获得节点位置的一个直接方法就是使用全球定位系统GPS，但该定位装置价格昂贵而且在有遮挡的情况下使用效果不佳;对于精度不高的还可以采用LPS(Local Position System)。为每个节点都配备GPS定位装置是一个高成本的设计思想，是一个不现实的想法，因此一般采用GPS+绝对定位或相对定位来实现。 2.6.6 数据管理

从数据存储的角度来看，无线传感器网络可被视为一种分布式数据库。以数据库的方法在无线传感器网络中进行数据管理，可以将存储在网络中的数据的逻辑视图与网络中的实现进行分离，使得无线传感器网络的用户只需要关心数据查询的逻辑结构，无需关心实现细节。虽然对节点感知到的数据进行抽象在一定程度上影响执行效率，但可以显著增强传感器网络的易用性。美国加州大学伯克利分校的Tiny DB系统和Comell大学的Cougar系统是目前具有代表性的传感器网络数据管理系统。

传感器网络的数据管理与传统的分布式数据库有很大的差别。由于传感器节点能量

15

沈阳理工大学学士学位论文

受限且容易失效，数据管理系统必须在尽量减少能量消耗的同时提供有效的数据服务。同时，传感器网络中节点数量庞大，且传感器节点产生的是无限的数据流，无法通过传统的分布式数据库的数据管理技术进行分析处理。此外，对传感器网络数据的查询经常是连续的查询或随机抽样的查询，这也使得传统分布式数据库的数据管理技术不适用于传感器网络。 2.6.7 服务质量

在某些应用中，数据应是刚感受到的一段时间内，否则数据将无用的。因此，范围潜伏期为数据传送是另一个条件，时间约束的应用。然而，在许多应用中，节约能源是直接关系到网络的一生，被认为是相对来得重要数据的质量发送。当能量耗尽之时，该网络可能必须减少质量，以减少节点能量损耗和从此延长整个网络寿命。因此，路由协议能量是必须有这个必备的条件。 2.6.8 嵌入式操作系统

传感器节点是一个微型的嵌入式系统，携带非常有限的硬件资源，需要操作系统能够节能高效地使用其有限地内存、处理器和通信模块，且能够对各种特定应用提供最大的支持。在面向无线传感器网络的操作系统的支持下，多个应用可以并发地使用系统的有限资源。传感器节点有两个突出的特点。一个特点是并发性密集，即可能存在多个需要同时执行的逻辑控制，这需要操作系统有效地满足这种发生频繁、并发程度高、执行过程比较短的逻辑控制流程;另一个特点是传感器节点模块化程度很高，要求操作系统能够让应用程序方便地对硬件进行控制。上述这些特点对设计面向无线传感器网络的操作系统提出了新的挑战。

16

沈阳理工大学学士学位论文

6 结 论

无线传感器网络是由一组传感器以自组织方式构成的无线网络,其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息,并发布给观察者。传感器网络具有十分广阔的应用前景，在军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域远程控制等许多领域都有重要的科研价值和巨大实用价值，已引起了世界上许多国家军界、学术界和工业界的高度重视，并成为近年来公认的热点研究领域。

本文首先对目前传感器网络路由方面的研究进行了分析，并对常见的路由算法进行分类，详细地描述了现有的算法，并阐述了它们各自的优缺点。针对经典的平面路由算法Flooding进行了分析研究针对传感节点能量和传输范围均有限等特点，提出了一种基于延迟的自适应洪泛路由算法，算法引入RREQ（路由请求报文）和RREP（路由回复报文）建立路由，初始化阶段后，源节点先向其邻居广播RREQ，在建立路由的过程中当有节点收到RREQ时，若它比上一跳节点离Sink更远或该报文的TTL－1＝0则它丢弃该报文；否则，该节点先等待一段时间看是否有更优的来自同一Source的RREQ，若有则转发更优的RREQ直到Sink。Sink接收到RREQ后向最优路回复RREP；而后源节点再沿着建立好的路径转发较大的数据报文。理论分析表明算法具有较低的复杂度，实验结果也表明新算法较Flooding更节能，与其相比在路由性能方面有较大的提高，能较好的解决Flooding报文冗余度高，能耗大等问题。

如前所述，能耗问题成为了限制传感器网络路由算法的关键性问题之一。同时，路由算法的设计还应考虑到网络的物理层、链路层、应用层等相关的问题。如何结合特定应用场景及传感器物理设备的特点、如何考虑到网络中数据融合、优化、管理、安全等问题，以设计更优的能满足实际应用的路由算法，是我们下一步要深入的研究课题。

42

沈阳理工大学学士学位论文

致 谢

首先，我要感谢我的毕业设计指导教师——梁英老师。他为我们提供了设计题目范围，让我们根据自己的爱好，选择相关课题，然后给予我们帮助，让我们在最大的发挥自己的能力的前提下，帮助我们完成自己的设计。

在毕业设计期间，梁老师一直非常负责：前期理论研究的时候，梁老师对我们的问题耐心讲解，并督促我们的进度；后期程序设计期间，梁老师全天留在教研室，指导我们的设计。梁老师灵活的指导方式让我们的毕业设计在一种自由，严谨的氛围内进行，使我们充分发挥自己的能力。

其次，我要感谢我的同伴，没有她的协助，我的设计是无法进行到最后的。在她的帮助下，我们合作完成了我们的毕业设计。她在一边工作实习，一边做毕业设计的情况下，给予了我这么多的帮助，我非常感谢。

总之，感谢梁老师在百忙之中给予的热心指导以及我的同伴给予我的配合及帮助。

43

沈阳理工大学学士学位论文

参考文献

[1] 于洪斌 曾鹏 梁伟《智能无线传感器网络系统》科学出版社

[2] 史永彬 叶湘滨 刘培亮《无线传感器网络技术研究现状》国外电子测量技术, 2005,(11)

[3] 宫晓渊 周兴社 李志刚 刘刚《无线传感器网络组织结构研究》 微电子学与计算机 [4] 李方敏 刘新华 旷海兰《无线传感器网络中一种高能效低延时的泛洪算法研究》通 信学报 2007年,第08期

44

沈阳理工大学学士学位论文

附录A：英文原文

2 Routing Challenges and Design Issues in WSNs

Despite the innumerable applications of WSNs, these networks have several restrictions, e.g., limited energy supply, limited computing power, and limited bandwidth of the wireless links connecting sensor nodes. One of the main design goals of WSNs is to carry out data communication while trying to prolong the lifetime of the network and prevent connectivity degradation by employing aggressive energy management techniques. The design of routing protocols in WSNs is influenced by many challenging factors. These factors must be overcome before efficient communication can be achieved in WSNs. In the following, we summarize some of the routing challenges and design issues that affect routing process in WSNs.

Node deployment: Node deployment in WSNs is application dependent and affects the performance of the routing protocol. The deployment can be either deterministic or randomized. In deterministic deployment, the sensors are manually placed and data is routed through pre-determined paths. However, in random node deployment, the sensor nodes are scattered randomly creating an infrastructure in an ad hoc manner. If the resultant distribution of nodes is not uniform, optimal clustering becomes necessary to allow connectivity and enable energy efficient network operation. Inter-sensor communication is normally within short transmission ranges due to energy and bandwidth limitations. Therefore, it is most likely that a route will consist of multiple wireless hops.

Energy consumption without losing accuracy: sensor nodes can use up their limited supply of energy performing computations and transmitting information in a wireless environment. As such, energy-conserving forms of communication and computation are essential. Sensor node lifetime shows a strong dependence on the battery lifetime. In a multihop WSN, each node plays a dual role as data sender and data router. The malfunctioning of some sensor nodes due to power failure can cause significant topological changes and might require rerouting of packets and reorganization of the network.

45

沈阳理工大学学士学位论文

Data Reporting Model: Data sensing and reporting in WSNs is dependent on the application and the time criticality of the data reporting. Data reporting can be categorized as either time-driven (continuous), event-driven, query-driven, and hybrid. The time-driven delivery model is suitable for applications that require periodic data monitoring. As such, sensor nodes will periodically switch on their sensors and transmitters, sense the environment and transmit the data of interest at constant periodic time intervals. In event-driven and query-driven models, sensor nodes react immediately to sudden and drastic changes in the value of a sensed attribute due to the occurrence of a certain event or a query is generated by the BS. As such, these are well suited for time critical applications. A combination of the previous models is also possible. The routing protocol is highly influenced by the data reporting model with regard to energy consumption and route stability.

Node/Link Heterogeneity: In many studies, all sensor nodes were assumed to be homogeneous, i.e., having equal capacity in terms of computation, communication, and power. However, depending on the application a sensor node can have different role or capability. The existence of heterogeneous set of sensors raises many technical issues related to data routing. For example, some applications might require a diverse mixture of sensors for monitoring temperature, pressure and humidity of the surrounding environment, detecting motion via acoustic signatures, and capturing the image or video tracking of moving objects. These special sensors can be either deployed independently or the different functionalities can be included in the same sensor nodes. Even data reading and reporting can be generated from these sensors at different rates, subject to diverse quality of service constraints, and can follow multiple data reporting models. For example, hierarchical protocols designate a cluster head node different from the normal sensors. These cluster heads can be chosen from the deployed sensors or can be more powerful than other sensor nodes in terms of energy, bandwidth, and memory. Hence, the burden of transmission to the BS is handled by the set of cluster-heads. Fault Tolerance: Some sensor nodes may fail or be blocked due to lack of power, physical damage, or environmental interference. The failure of sensor nodes should not affect the overall task of the sensor network. If many nodes fail, MAC and routing protocols must accommodate formation of new links and routes to the data collection base stations. This may

46

沈阳理工大学学士学位论文

3.WSN路由协议算法分析

3.1 WSN路由协议的分类方法

WSNs路由协议负责在sink点和其余节点间可靠地传输数据。由于WSNs与应用高度相关，单一的路由协议不能满足各种应用需求，因而人们研究了众多的路由协议。为揭示协议特点，我们根据一些路由协议采用的通信模式、路由结构、路由建立时机、状态维护、节点标识和投递方式等策略，运用多种分类方法对其进行了分类。由于研究人员组合多种策略来实现路由机制，故同一路由协议可分属不同类别。

（1）根据传输过程中采用路径的多少，可分为单路径路由协议和多路径路由协议。单路径路由节约存储空间,数据通信量少；多路径路由容错性强,健壮性好,且可从众多路由中选择一条最优路由。

（2）根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面路由协议和层次路由协议。平面路由简单,健壮性好,但建立、维护路由的开销大，数据传输跳数多，适合小规模网络；层次路由扩展性好，适合大规模网络，但簇的维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。

（3）根据路由建立时机与数据发送的关系，可分为主动路由协议、按需路由协议和混合路由协议。主动路由建立、维护路由的开销大，资源要求高；按需路由在传输前需计算路由，时延大；混合路由则综合利用这两种方式。

（4）根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基于位置的路由协议和非基于位置的路由协议。有大量WSNs应用需要知道突发事件的地理位置，这是基于位置的路由协议的应用基础，但需要GPS定位系统或者其他定位方法协助节点计算位置信息。

（5）根据是否以数据来标识目的地，可分为基于数据的路由协议和非基于数据的路由协议。有大量WSNs应用要求查询或上报具有某种类型的数据，这是基于数据的路由协议的应用基础，但需要分类机制对数据类型进行命名。

（6）根据节点是否编址、是否以地址标识目的地，可分为基于地址的路由协议和非基于地址的路由协议。基于地址的路由在传统路由协议中较常见，,而在WSNs中一般不单独使用而与其他策略结合使用。

17

沈阳理工大学学士学位论文

（7）根据路由选择是否考虑QoS约束，可分为保证QoS的路由协议和不保证QoS的路由协议。保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从众多可行路由中选择一条最适合QoS应用要求的路由。

（8）根据数据在传输过程中是否进行聚合处理，可分为数据聚合的路由协议和非数据聚合的路由协议。数据聚合能减少通信量，但需要时间同步技术的支持，并使传输时延增加。

（9）根据路由是否由源节点指定，可分为源站路由协议和非源站路由协议。源站路由协议节点无须建立、维护路由信息，从而节约存储空间，减少通信开销。但如果网络规模较大，数据包头的路由信息开销也大，而且如果网络拓扑变化频繁，将导致路由失败。 （10）根据路由建立时机是否与查询有关，可分为查询驱动的路由协议和非查询驱动的路由协议。查询驱动的路由协议能够节约节点存储空间，但数据时延较大，且不适合环境监测等需紧急上报的应用。

3.2 几种典型路由协议的分析

3.2.1 平面路由协议

平面路由协议主要特点有：所需的信息域较小，一般仅需一跳（1 hop）内的信 息；无需进行周期性的路由信息维护；复杂度较低。 (1) Flooding

泛洪是一种传统的路由技术，不要求维护网络的拓扑结构，并进行路由计算，接收到消息的节点以广播形式转发分组。对于自组织的传感器网络，泛洪路由是一种较直接的实现方法，但消息的“内爆”(implosion)和“重叠”(overlap)是其固有的缺陷。为了克服这些缺陷，S.hedetniemi等人提出了Gossiping策略，节点随机选取一个相邻节点转发它接收到的分组，而不是采用广播形式。这种方法避免了消息的“内爆”现象，但有可能增加端到端的传输延时。

18

沈阳理工大学学士学位论文

图3.1 Flooding路由协议中的内爆和重叠问题

(2) SPIN (sensor protocol for information via negotiation)

SPIN是以数据为中心的自适应路由协议，通过协商机制来解决泛洪算法中的“内爆”和“重叠”问题。传感器节点仅广播采集数据的描述信息，当有相应的请求时，才有目的地发送数据信息。SPIN协议中有3种类型的消息，即ADV，REQ和DATA。

ADV—用于新数据广播。当一个节点有数据可共享时，它以广播方式向外发送DATA数据包中的元数据。

REQ—用于请求发送数据。当一个节点希望接收DATA数据包时，发送REQ数据包。 DATA—包含附上元数据头(meta一header)的实际数据包。 SPIN协议有4种不同的形式:

? SPIN-PP：采用点到点的通信模式，并假定两节点间的通信不受其他节点的干扰，分组不会丢失，功率没有任何限制。要发送数据的节点通过ADV向它的相邻节点广播消息，感兴趣的节点通过REQ发送请求，数据源向请求者发送数据。接收到数据的节点再向它的相邻节点广播ADV消息，如此重复，使所有节点都有机会接收到任何数据。 ? SPIN-EC：在SPIN-PP的基础上考虑了节点的功耗，只有能够顺利完成所有任务且能量不低于设定阈值的节点才可参与数据交换。

? SPIN-BC：设计了广播信道，使所有在有效半径内的节点可以同时完成数据交换。为了防止产生重复的REQ请求，节点在听到ADV消息以后，设定一个随机定时器来控制REQ请求的发送，其他节点听到该请求，主动放弃请求权利。

? SPIN-RL：它是对SPIN-BC的完善，主要考虑如何恢复无线链路引入的分组差错与丢失。记录ADV消息的相关状态，如果在确定时间间隔内接收不到请求数据，则发送重传请求，重传请求的次数有一定的限制。图3.2表明了SPIN协议的路由建立与数据传送。

19

沈阳理工大学学士学位论文

图3.2 SPIN协议的路由建立与数据传送

基于数据描述的协商机制和能量自适应机制的SP创协议能够很好地解决传统的Flooding协议所带来的信息爆炸、信息重复和资源浪费等问题。此外，由于协议中每个节点只需知道其单跳邻居节点的信息，拓扑改变呈现本地化特征。SP州协议的缺点是数据广告机制不能保证数据的可靠传递，如果对数据感兴趣的节点远离源节点或者在源节点和目的节点中间的节点对数据不感兴趣，那么数据就不可能被传递到目的地。因此，对于入侵发现等需要在定期间隔内可靠传递数据的应用系统来说，SP州并不是一个很 好的选择。

(3) SAR (sequential assignment routing)

在选择路径时，有序分配路由(SAR)策略充分考虑了功耗、QoS和分组优先权等特殊要求，采用局部路径恢复和多路经备份策略，避免节点或链路失败时进行路由重计算需要的过量计算开销。为了在每个节点与sink节点间生成多条路经，需要维护多个树结构，每个树以落在sink节点有效传输半径内的节点为根向外生长，枝干的选择需满足一定QOS要求并要有一定的能量储备。这一处理使大多数传感器节点可能同时属于多个树，可任选其一将采集数据回传到sink节点。 (4) 定向扩散(directed diffusion)

DD是以数据为中心的路由协议发展过程的里程碑，其突出特点是引入了梯度来描述网络中间节点对该方向继续搜索获得匹配数据的可能性。这是一个重要的基于数据的、查询驱动的路由协议。该协议用属性/值对命名数据。为建立路由，sink点flooding包含属性列表、上报间隔、持续时间、地理区域等信息的查询请求Interest (该过程本质上是设置一个监测任务)。沿途节点按需对各Interest进行缓存与合并，并根据Interest计算、创建包含数据上报率、下一跳等信息的梯度(gradient),从而建立多条指向sink点的路径。Interest中的地理区域内节点则按要求启动监测任务，并周期性地上报数据，途中各节点可对数据进行缓存与聚合。sink点可在数据传输过程中通过对某条路径发送上

20

沈阳理工大学学士学位论文

报间隔更小或更大的Interest，以增强或减弱数据上报率。该协议采用多路径，健壮性好；使用数据聚合能减少数据通信量；sink点根据实际情况采取增强或减弱方式能有效利用能量；使用查询驱动机制按需建立路由，避免了保存全网信息，但不适合环境监测等应用。而且，Gradient的建立开销很大，不适合多sink点网络；数据聚合过程采用时间同步技术，会带来较大开销和时延。图3.3描述了定向扩散模型的工作原理。

图3.3 定向扩散模型的工作原理

DD路由是一种经典的以数据为中心的路由机制。Sink节点根据不同的应用需求定义不同的任务类型、目标区域等参数的兴趣消息，通过向网络中广播兴趣消息启动路由建立过程。中间传感器节点通过兴趣表建立从数据源到Sink节点的数据传输梯度，自动形成数据传输的多条路径。DD采用相邻节点间通信的方式来避免维护全局拓扑，采用查询驱动数据传送模式和局部数据聚集而减少网络数据流，因此是一种高能源有效性的协议。它的缺点是，在需要连续数据传送的应用中(环境监测等)不能很好的应用；数据命名只能针对于特定的应用预先进行；初始查询的扩散开销大。

(5) 基于最小代价场的路由算法：算法开始之前，所有的节点都将自己的代价设为无穷大。网关广播一个代价为0的广告报文，其他节点接收到广告报文后，如果报文中所表示的代价小于节点自己的代价，则使用这个新的代价作为自己的代价，并将新的代价广播出去；反之，则丢弃该信息。最终每个节点都获得了自己距离网关的最小代价，由此建立代价场，报文沿着最小代价路径向网关发送。当报文被发送的时候它将附带源节点的最小代价，及从源节点到当前节点所消耗的代价，一个邻居节点接收到报文，只有该报文已消耗的代价和自己的代价之和等于源节点代价的时候，才转发这个报文。采用这种方法，节点不需要维持任何的路径信息，就可以实现报文的最短路径发送。

21

沈阳理工大学学士学位论文

3.2.2 分层路由协议

在层次路由协议中，网络通常被划分为簇（cluster），每个簇由一个簇头（cluster-head）和多个簇成员（cluster-member）组成，低一级网络的簇头是高一级网络中的簇成员。在这种分级结构中，簇头不仅负责簇内信息的收集和融合处理，还负责簇间数据转发。层次路由协议中簇的形成通常是基于节点的能量和其与簇头间的距离。为了延长整个网络的生存期，簇头节点需要周期更新。层次路由的优点是便于管理，可以对系统变化做出快速反应，能够提供高质量的通信服务，能量利用率较高。但簇的维护开销较大。

（1）LEACH (low energy adaptive clustering hierarchy)

LEACH是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法。与一般的平面多跳路由协议和静态聚类算法相比,LEACH可以将网络生命周期延长15%,主要通过随机选择聚类首领,平均分担中继通信业务来实现。LEACH定义了“轮”(round)的概念,一轮由初始化和稳定工作两个阶段组成。为了避免额外的处理开销,稳定态一般持续相对较长的时间。 如图3.4所示：

初始化阶段 稳定工作阶段

时间

图3.4 LEACH协议的时序图

在初始化阶段,聚类首领是通过下面的机制产生的。传感器节点生成0,1之间的随机数,如果大于阈值T,则选该节点为聚类首领.T的计算方法如下:

T?1?P?rmod?P1p??

（3.1）

其中p为节点中成为聚类首领的百分数,r是当前的轮数。

当簇头选定之后，簇头节点主动向网络中节点广播自己成为簇头的消息(ADV_CH)。接收到此消息的节点，依据接收信号的强度，选择它所要加入的簇，并发消息通知相应的簇头(JOIN_REQ)。基于时分多址(Time Division Multiple Address，简称TDMA)的方式，簇头节点为其中的每个成员分配通信时隙，并以广播的形式通知所有的簇内节点

22

沈阳理工大学学士学位论文

(ADVSCH)。这样保证了簇内每个节点在指定的传输时隙进行数据传输，而在其他时间进入休眠状态，减少了能量消耗。在稳定工作阶段，节点持续采集监测数据，在自身传输时隙到来时把监测数据传给簇头节点(DATA)，如图3.5所示。簇头节点对接收到数据进行融合处理之后，发送到Sink节点，这是一种减小通信业务量的合理工作模式。持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇头节点。

图3.5 LEACH协议

LEACH协议采用动态转换簇头的方法来平均网络节点的能量消耗，使因能量耗尽而失效的节点呈随机分布状态，因而与一般的多跳路由协议和静态簇算法相比，LEACH可以将网络生命周期延长15%。但是LEACH协议在每轮固定簇头节点后在划分簇的过程中，簇头节点开销较大。并且簇头节点的选择无法达到最优，有可能簇头节点位于网络的边缘或者几个簇头节点相邻，某些节点不得不传输较远的距离来与簇头通信，这就导致了大量能量消耗。而且LEACH协议所有簇头节点直接与Sink节点通信，采用连续数据发送模式和单跳路径选择模式，使得每轮中簇头节点能耗巨大，因此不适合在大规模的传感器网络中应用。

（2）TEEN (threshold sensitive energy efficient sensor network protocol)

依照应用模式的不同，通常可以简单地将无线自组织网络(包括传感器网络和Ad-hoc网络)分为主动(proactive)和响应(reactive)两种类型。主动型传感器网络持续监测周围的物质现象，并以恒定速率发送监测数据；而响应型传感器网络只是在被观测变量发生突变时才传送数据。相比之下,响应型传感器网络更适合应用在敏感时间的应用中。TEEN和LEACH的实现机制非常相似,只是前者是响应型的，而后者属于主动型传感器网络。在TEEN中定义了硬、软两个门限值，以确定是否需要发送监测数据。当监测数据第一次超过设定的硬门限时,节点用它作为新的硬门限,并在接着到来的时隙内发送它。在接下来的过程中，如果监测数据的变化幅度大于软门限界定的范围，则节点传送最新采集的数据，并将它设定为新的硬门限。通过调节软门限值的大小，可以在监测精

23

沈阳理工大学学士学位论文

度和系统能耗之间取得合理的平衡。图3.6表示的是TEEN协议中由聚簇构成的层次结构。 High level cluster head Sink Low level cluster head

Clustering Normal sensor node

图3.6 TEEN协议中由聚簇构成的层次结构

TENE适用于实时性要求较高的应用场合，比如入侵警报，爆炸预警等，用户可以及时获取感兴趣的信息。而且用户可以通过设置不同的软门限方便地平衡监测的准确性与系统节能性两项指标。但是这个方案也有一些不足之处，例如门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得到任何数据;没有相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状态的节点，所以TEEN协议不适合应用在。 （3）PEGAGIS (power-efficient gathering in sensor information system)

PEGASIS由LEACH发展而来。它假定组成网络的传感器节点是同构且静止的。节点发送能量递减的测试信号，通过检测应答来确定离自己最近的相邻节点。在收集数据前，首先利用贪心算法将网络中的所有节点连接成一条单链。通过这种方式，网络中的所有节点能够了解彼此的位置关系，进而每个节点依据自己的位置选择所属的聚类，聚类的首领向链的两端发出收集数据的请求，数据从单链的两个端点向首领流动。中间节点在传递数据前要执行融合操作，最终由首领节点将结果数据传送给Sink节点。因为PEGASIS中每个节点都以最小功率发送数据分组，并有条件完成必要的数据融合，减小业务流量。因此,整个网络的功耗较小。研究结果表明，PEGASIS支持的传感器网络的生命周期是LEACH的近两倍。

24

沈阳理工大学学士学位论文

图3.7 PEGAGIS的单链结构 0 2 1 6 3 4 5 Sink 单链结构的PEGASSI算法主要有以下两点缺陷:

第一点是平均延迟较大:数据需要沿着单链结构顺序传送，收集数据的延迟决定于首领节点与单链端节点的距离，因此平均延迟与节点数成正比；

第二点是鲁棒性较差:由于传感器节点的易失效性，如果不采取适当的修复策略，单链结构的传输路径容易增大数据收集请求的失败率。 （4）多层聚类算法

多层聚类算法是Estrin为传感器网络设计的一种新的聚类实现机制。工作在网络中的传感器节点处于不同的层，所处层次越高，所覆盖面积越大。起初，所有节点均在最低层，通过竞争获得提升高层的机会。新的工作周期开始时，每一个节点都广播自己的状态信息，包括储备能量、所在层次和首领的ID(如果有)等，然后进入等待状态以便相互了解信息，等待时间与所在层次成正比。处在最低层的节点如果没有首领，等待状态结束后，立刻启动一个“晋升定时器”，定时时间与自身能量以及接收到同层其他节点广播消息的数目成反比，目的是为能量较高且在密集区的节点获得较多的提升机会。一旦定时时间到，节点升入高层，将有发给自己广播消息的节点视为潜在的子节点，并广播自己新的状态信息，低层节点选择响应这些准首领的广播消息，最终确定惟一的通信关系。选择了首领的节点，自己的“晋升定时器”将停止工作，也就意味着本轮放弃了晋升机会。在每一个工作周期结束以后，高层节点将视自己的状态信息(如有无子节点，功率是否充足)决定是否让出首领位置。上述的多层聚类算法具有递归性，Estrin等人用两层模型验证了它在传感器网络中的有效性。

25

沈阳理工大学学士学位论文

（5）Younis等人提出了基于三层体系结构的路由协议。与LEACH不同的是，该协议要求在网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的ID标识和簇内所分配节点的位置信息。簇内节点可以以感知、转发、感知并转发、休眠这四种方式之一存在。簇头不受能量的限制，它可以监控节点的能量变化，决定并维护传感器的四种状态，并利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。

表3.1 几种常见平面路由协议比较

名称 Flooding Gossiping SAR SPIN DD 基于最小代价场的路由算法

表3.2 几种常见分层路由协议的比较

主要思想 收到数据的节点向所有邻居节点广播报文 收到的数据节点随机选取地选择一个邻节点转发报文 依据每条路径上的能量资源和QoS要求来决策路由 根据临时的请求、应答的方式转发数据 在所有节点中为Sink的请求建立一个临时的“梯度”场；匹配数据沿“梯度”最大的方向中继回Sink 每个节点获得了自己距离网关的最小代价后建立代价场，报文沿最小代价路径向网关发送 MAC协议 SMACS 基于CSMA的 介质 TDMA/FDMA组合方案 描述 固定时隙收发数据，并在空闲时将节点转入休眠状态以减小能耗 基于竞争机制随机接入，通过调整相位避免冲突重复发生 选择适宜数量的信道，在相应中心频率信道内时分复用

26

沈阳理工大学学士学位论文

4 Flooding路由协议的分析与研究

泛洪(Flooding)路由算法是一种经典的路由算法，由于其具有实现简单，容错能力强等特点，无论在有线网络中还是在无线网络中都得到了广泛的应用。由于实现简单，泛洪算法在传感器网络中也得到了广泛应用。但是泛洪算法能耗过大的缺点又在相当程度上抵消了其优势，使其不适合直接地应用于无线传感器网络。如果将泛洪作为一种路由算法应用于传感器网络，需要解决其能耗过大、数据冗余量高问题。如DD、SPIN、Gossiping等算法都是Flooding的改进算法。

4.1 泛洪算法模型

在泛洪算法中，任一节点ni接收到报文的动作可用如下伪代码描述。每个报文都包含TTL（报文存活时间）、DATA（数据）等内容。算法基本步骤如下： Step1：Sink和其他节点广播自己的位置信息和序列号； Step2：源节点广播报文；

Step3：若收到报文的节点为Sink则报文已传送到目的地；否则转Step4； Step4：若报文的TTL－1＝0或节点已收到过该报文，则转Step5，否则转Step6； Step5：节点丢弃该报文；

Step6：节点将报文转发给它所有的邻居节点。

报文中的TTL字段，通常用来防止报文在网络内被无限制的转发，在洪泛的工作模式下，网络中有节点要发送报文时，它将把报文发送给所有的邻居节点；而收到报文的节点则将报文转发给自己所有的邻居节点，除非TTL－1＝0或接收节点本身就是汇集点。其中TTL通常表示跳数或时间，当TTL－1＝0时，报文将被丢弃。传感器网络中基于自适应的路由算法研究。

27

沈阳理工大学学士学位论文

4.2 算法流程图

是否 是否 是否 开 始 Sink和其他节点广播自己的位置信息和序列号 源节点广播报文 收到报文的节点为Sink 将数据包交高层处理并失去对该数据包的转发权 报文的TTL－1＝0？ 丢弃该报文 节点已收到过该报文 丢弃该报文

图4.1 泛洪算法流程图

28

沈阳理工大学学士学位论文

4.3 基于延迟的自适应泛洪路由算法

在整个网络内进行泛洪时，因为每个节点无论是否在最终的转发路径上，都要转发报文，这使网络中充斥了大量的无用报文，浪费了许多资源，节点的能量也消耗很快。为了解决泛洪模型的缺陷，本章提出了一种基于延迟的自适应泛洪模型，算法的主要思想是初始化阶段后，源节点先在全网内用较小的路由请求报文(Routing Request Packets，RREQ)和路由回复报文(Routing Reply Packets，RREP)来建立路由，在建立路由的过程中当有节点收到RREQ时，若它比上一跳节点离Sink更远或该报文的TTL－1＝0则它不转发RREQ并丢弃该报文；否则，节点先根据网络的实际情况等待一段时间看是否有更优的来自同一Source的RREQ，若有则转发更优的RREQ直到Sink。Sink接收到RREQ后向最优路回复RREP。而后源节点将沿着建立好的路径转发较大的数据报文。新算法可以分为初始化、路由建立和数据传输阶段。其中，路由建立阶段主要是找到一条较优的从源节点到目的节点的路径，而数据传输阶段则依据路由建立阶段建立的路径传输数据报文。

4.3.1 算法中用到的报文和数据

各阶段中用到的报文和各节点需要维护的表格分别如表4.1、4.3所示：

表4.1 flooding报文表

报文名称 NIP：Neighbors Information Packet(节点信息报文) RRE：Routing Request Packet (路由请求报文) RREP：Routing Reply Packet (路由回复报文) DP：Data Packet（数据报文） RR：Rerouting(重建路由报文)

报文中包含的域 PT＝0,POS,SN PT＝1,SNL,POSS,E,TTL PT＝2,SNL,POSS,TTL PT＝3,SNL,Data PT＝5,SN 长度（bit） 21 ≥24 ≥16 2000 11 29

沈阳理工大学学士学位论文

表4.2 对flooding报文及表格中各数据域的说明

域名 PTP SN POSS E TTL SNLS Data Type

注解 长度（bit） acket Type，报文类型，PT＝0..5分别表示NIP、RREQ、RREP 3 和DP、RR五种中不同的报文 Serial Number，节点序列号 Position，位置信息，其中POSS表示源节点位置信息 Energy，记录报文传送到目前为止所消耗的能量 Time-to-live，报文存活时间 8 10 8 3 Serial Numbers List序列号表，将报文经过的节点序列号都=报文经过的依次列出来 节点数×8 数据，数据报文一律统一为2000bit － 节点类型，TYPE=0,1分别表示存活(Alive，默认值)或死亡 1 表4.3 flooding中各节点需要维护的表格

表格名称 NIT：Neighbors Information Table (邻居信息表) RQT：RREQ Table (RREQ表) RPT：RREP Table (RREP表) 表格中包含的域 POS，SN，Type SNL，POSS SNL，POSS 4.3.2 SFD算法描述

算法包括以下三个阶段：初始化阶段（Initialization Phase，In P）、路由建立阶段（Routing Building Phase，RBP）和数据传输阶段（Data Forwarding Phase，DFP）。 1、初始化阶段（Initialization Phase，In P） Step1：各节点广播节点信息报文NIP；

Step2：收到NIP报文的节点将相关信息存储到邻居信息表NIT中。 2、路由建立阶段（Routing Building Phase，RBP）

30

沈阳理工大学学士学位论文

Step1：Source查找RPT表，若它是某个RREP报文SNL中的一个节点，则它直接沿该RREP确定的路径转发DP，否则广播一个新的RREQ；

Step2：节点ni接收到RREQ后查找RPT表，若它是某个RREP报文SNL中的一个节点，则它直接沿该RREP确定的路径向它的上一跳节点回复RREP，否则：

Step I：若报文的TTL－1＝0，或ni的剩余能量已不够转发一个DP，则转Step IV，否则转Step II；

Step II：ni分别计算ni和该RREQ上一跳节点与Sink之间的距离，若ni较上一跳离Sink更近，则转Step III，否则转Step IV；

Step III：ni等待Δt时间，若来自同源节点有转发能耗更小的RREQ，则将到目前为止收到的来自同一源节点的RREQ中能耗最小的那个报文转发，直到RREQ到达Sink； Step IV：ni丢弃该报文。

Step3：Sink收到RREQ后，沿能耗最小的那些RREQ确定的路径回复RREP，直到RREP到达指定的Source。

3、数据转发阶段（Data Forwarding Phase，DFP）

Step1：Source收到RREP后沿该RREP指定的路径向Sink发送数据报文。

Step2：当ni剩余能耗不够转发DP时，则其广播RR报文，收到该报文的节点在其NIT中将ni状态改为Dead。若ni是目前正在使用的到Sink的路径中的一个节点，则其在该路径中的邻居节点向自己在路径中的上一跳节点发送RR报文，并将RPT表中对应的RREP信息删除，直到RR报文到达该路径的起点。当Source收到RR后，转2。（RR报文中记录了ni的序列号）传感器网络中基于自适应的路由算法研究

4.3.3 性能比较尺度

为了更好的比较各路由算法的优缺点，本文定义了如下一些尺度来具体地衡量算法性能。本文在后面几章中进行算法的性能评价时，仍然使用这些指标。 (1)时间复杂度（Time Complexity，TC）：算法实现时所耗费的时间量级。 (2)消息域（Message Field，MF）：算法实现时所需要的信息范围。

(3)网络检测到的事件总数（即从Source传送到Sink的数据报文总数，Total Detected Events，TDE）：反映了系统的吞吐量。

(4)传送一个事件的平均能耗(Average Energy Expenditure per Event，AEE)：

AEE?网络总能量。

所检测到的时间总数31

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