无线传感器网络技术

第1章现状与发展1.1WSN研究历史1.2WSN与Adhoc网络1.3WSN体系结构1.4WSN的应用1.5WSN研究1.6WSN研究中的若干问题1.1WSN研究历史WSN的研究起源于20世纪70年代。最早应用于军事领域，例如冷战时期的声音监测系统(SOSUS,SoundSurveillanceSystem)以及空中预警与控制系统(AWACS,Air-borneWarningandControlSystem)。1980年，美国国防部高级研究规划局(DARPA,DefenseAdvancedResearchProjectsAgency)的分布式传感器网络项目(DSN,DistributedSensorNetworks)开启了现代传感器网络研究的先河。下一页返回1.1WSN研究历史20世纪80~90年代，传感器网络的研究依旧主要在军事领域进行，并成为网络中心战思想中的关键技术，其中比较著名的系统包括:美国海军研制的协同交.饯能力系统(CEC，CooperativeEngagementCapability)，用于反潜的确定性分布系统(FDS,FixedDistributedSystem)和高级配置系统(ADS,AdvancedDeploymentSystem)，以及远程战场传感器网络系统(REMBASS,RemoteBattlefieldSensorSystem)和战术远程传感器系统(TRSS,TacticalRemoteSensorSystem)等无人看管地面传感器网络系统。上一页下一页返回1.1WSN研究历史进入21世纪后，随着无线通信技术、微芯片制造等技术的进步，WSN的研究在多种应用方面取得了巨大进展。各种技术评论杂志一致看好WSN蕴藏的巨大应用潜力和商业价值。正如WilliamJ.Kaise:教授所说:WSN是一门交叉学科，涉及计算机、微电子、传感器、网络、通信、信号处理等诸多领域。从计算机学科的角度分析，WSN在一定程度上代表了未来计算机发展的方向。Bell定律指出:每10年会有一类新的计算设备诞生。WSN的出现与发展恰好顺应了这个趋势。大量的微型无线传感器网络节点被嵌入到我们生活的物理世界中，为实现人与自然界丰富多样的信息交互提供了技术条件。从这个角度看，WSN节点或许就应该是新一代的计算设备，或者一至少属于其中一类。未来如果生物芯片技术有了突破性进展，体积更小，数量更多的新计算设备替代目前的硅片系统也是完全可能的事。上一页下一页返回1.1WSN研究历史图1-1直观描述了计算设备的演化历史和可能的未来。目前我们正处于PDA向下一代计算设备过渡的时一期，研究WSN的意义和重要性自然不言而喻，因此受到了学术界和工业界的普遍推崇与青睐。但也有研究者一质疑WSN研究的科学息义和应用价值，主要集中在两个方面:①就网络研究而言，WSN与Adhoc网络的本质区别何在?②虽然WSN应用的远景描述令人振奋，但其真正现实的商业应用何在?上一页返回1.2WSN与Adhoc网络为方便讨论与比较，我们将目前的无线网络分为三类:WSN、Adhoc网络和无线宽带网络，其中无线宽带网络包括GSM,CDMA、3G,Beyond3G、4G,WLAN(WiFi)和WMAV(WiMax)等分别从传统电信网络和计算网络衍生发展出来的网络技术，这些网络的规划、部署、配置、管理、维护和运营一般需要管理员干预来完成;而WSN和Adhoc作为快捷灵活的组网方式，基本不需要人的干预，大部分工作是以自组织的方式完成的，因此可以将它们统称为自组织网络(Self-OrganizationNetworks)。下一页返回1.2WSN与Adhoc网络依据这一点，有些研究者主张模糊WSN和Adhoc网络的界限，他们认为:从网络技术本身而言，WSN和Adhoc网络没有太大的本质区别，在Adhoc网络终端上配置传感器处理单元就是WSN。当然也有研究者反对这一观点，认为WSN有不同于Adhoc网络的技术要求和特征，这种不同不仅表现在与应用相关的表面层次上，而且涉及内部的网络核心技术。在WSN和Adhoc中，因为需要网络长时一间工作在特殊环境下，替换电池不可能，可再生能源技术目前又不成熟，通过优化系统能耗来延长网络生命周期是唯一可行的技术途径。另一方面，目前大多数自组织网络的应用偏重于文件或数据交换(尤其是WSN，多被用于执行各种监测任务)，没有广泛涉及音视频等数据密集型应用，因此，对于高带宽的需求不如无线宽带网络那么强烈。因此，追求低功耗的自组织网络设计，而非单纯地提高网络带宽是WSN和Adhoc研究的共同点。上一页下一页返回1.2WSN与Adhoc网络正是这一内在联系使许多研究者质疑WSN研究的科学息义与价值。事实上，早期的WSN研究也确实借用了Adhoc网络中较成熟的自组织路由协议，如AODV、DSDV等。但随着研究的不断深入，人们逐渐认识到:WSN与Adhoc虽同属自组织网络，但网络拓扑结构和土作模式却各不相同。一般而言，Adhoc网络中的节点具有张烈的移动性，相应的网络拓扑结构自然是动态变化，这无疑给路由技术带来了不小的障碍。在这一点上，Adhoc网络与某些无线宽带网络(如GSM和CDMA等)有相似性。而WSN中的节点在部署完成之后大部分不会再移动，因此网络拓扑结构是静态的，虽然部分节点会因调度机制(如拓扑控制)或失效等原因改变网络的拓扑结构，但我们依旧可以认为WSN的拓扑结构是准静态的，因为上述原因导致的变化具有明显的周期性和间歇性。因此，WSN和Adhoc网络中路由技术的难易程度不言而喻。上一页下一页返回1.2WSN与Adhoc网络此外，WSN的一般工作模式是网络中的所有节点将数据汇聚到Sink节点，即多对一(Many-to-One)通信，节点之间几乎不会发生消息交换。对于Adhoc网络而言，网络中任息两节点之间都有通信的可能。因此，相应的路由技术自然要比WSN复杂。WSN路由需要解决的问题仅仅是Adhoc路由的一个子集。从本质上讲，Adhoc网络和某些无线宽带网络(如WiFi和WiMax)继承了Internet体系结构的核心思想，网络中间节点不实现任何与分组内容相关的功能，只是简单地采用存储/转发的模式为用户传送分组，息味着网络就是一个“比特搬运工”。对于WSN而言，在多数应用中，网络仅仅实现分组传输功能是不够的，有时特别需要“网内数据处理”的支持。上一页下一页返回1.2WSN与Adhoc网络我们可以将执行一定功能的单个WSN视为Internet中的一个自治域(AS)，它的规模可以很大，但与Internet所不同的是WSN中属十不同AS的节点间一般不会有分组流动，扩展性不再是首要的技术问题，因此理论上，为WSN节点赋子一定的功能便具有合理性。综合以上各种技术因素，为WSN设计一种不同于传统网络的体系结构应该是非常必要的。最新的研究工作开始着重考虑在这个方向进行努力和尝试。上一页返回1.3WSN体系结构典型的WSN体系结构有支持动态协议栈、层次性的、自适应的、可编程的、自管理的、自恢复的、多任务的和基于代理的等。动态协议栈是指体系结构允许应用程序根据实际需要动态加载协议栈，主要解决WSN节点资源有限的问题。自适应体系结构提出了信息交换服务(IES,InformationExchangeService)的概念，,它类似一种总线，将迪常垂直分布的协议组件有效联结在一起，容易通过跨层(Crosslayer)设计的思想优化资源利用，延展网络的生命周期。可编程的传感器网络强调“网内数据处理”的重要性，通过提供区域性的操作原语来执行邻居发现和查询、数据共享与融合等操作，这样可以简化部分协议、机制和算法的实现，同时能提高它们的性能。下一页返回1.3WSN体系结构考虑到应用的特殊需要，参考文献[23]为WSN定义了一种称为MANNA的体系结构，将传统网络中原本加以区分的管理和服务功能融合为一体，自上而下定义了服务集、功能集和业务模型集。在参考文献[24]中，MANNA体系架构被用来设计一个自组织、自配置、自服务和自维护的火灾监测系统。支持多任务是WSN应该具备的特性之一，但已有的针对特定任务设计的应用系统大都忽略了这一点，参考文献[26]给出了一种支持多任务的网络体系结构，在网络层和应用层引入状态层(StateLayer)来根据应用需求对网络节点进行功能性划分。基于代理的WSN网络体系结构从方便应用程序设计的角度来支持多功能和多任务。依据层次和功能的不同，参考文献[27]

定义了四种不同的代理，包括接口代理、区域代理、簇代理和查询代理。上一页下一页返回1.3WSN体系结构2005年初，NSF启动了一个旨在促进网络体系结构、业务和应用研究，以及其产业化进程，最终实现互联网变革的研究计划——GENI,即革新网络的全球环境。GENI发布的概念性设计框架提出了面临的7项主要研究挑战。对新的网络技术、新的计算模式、新的分布式应用与系统的支持是其卞要研究内容，WSN与这三者一密切相关，常被作为范例来阐述GENI的研究目标。我们认为:应该将WSN体系结构的研究置于这一背景下，同时兼顾它自身的特点来进行。基于此，综合已有研究成果，结合GENI的初步构想，以及我们的一些研究体会与认识，将WSN体系结构设计中需要考虑的要素归纳如下。上一页下一页返回1.3WSN体系结构1.节点资源的有效利用2.支持网内数据处理3.支持协议跨层设计4.增强安全性5.支持多协议6.支持有效的资源发现机制7.支持可靠的低延时通信8.支持容忍延时的非面向连接通信9.开放性上一页返回1.4WSN的应用

1.目标跟踪DARPA支持的SensorIT项目探索如何将WSN技术应用于军事领域，实现所谓“超视距”战场监测。UCB的教授卞持的SensorWeb是SensorIT的一个子项目，原理性地验证了应用WSN进行战场目标跟踪的技术可行性。2.大鸭岛海燕监测WSN为许多科学研究提供了便利的技术手段，已经有不少相当成功的案例。一个典型的例子就是生物学家借助WSN对美国缅因州大鸭岛上一种名叫LeachStorm的海燕的生活习性进行了细微观测。下一页返回1.4WSN的应用3.冰河监测为更好地了解地球气候的变化，挪威科学家利用WSN监测冰河的变化情况，目的在于通过分析冰河环境的变化来推断地球气候的变化。4.医疗健康哈佛大学的一个研究小组利用无线传感器网络构建了一个医疗监测平台。

5.电子牧场

这是一个非常有趣的研究项目。在牛的脖子上套上WSN节点，当牛接近围栏时，上面的电子装置探测到有牛接近围栏，随即模拟出驱赶牛的声音，防止牛跑出电子桩划定的放牧区域，这样放牧人便可以坐在家中轻松自在地喝咖啡看电视。上一页下一页返回1.4WSN的应用

6.结构化监测结构化监测的目的是观测建筑物、桥梁、轮船和飞行器等物体在外力作用下的应力响应，或者被用来诊断和定位可能出现的局部损伤，是一项非常币要的工程技术。传统技术手段通过线缆将分布在物体不同部位的传感器所采集的数据汇聚到中心节点进行处理，成百上千条的线缆使监测现场异常零乱，组织试验费时、费力，WSN的出现为结构化监测提供了省时省力的技术手段。7.火山观测WSN还在一些特殊应用中发挥出了息想不到的效用。哈佛大学MateWel领导的研究小组利用WSN对活火山Volcan

Tungurahua进行了持续观测，节点采集的次声波数据被实时传回离火山十多千米远的监测站，而且监测站还可以远程控制各网络节点。上一页返回1.5WSN研究1.5.1研究方向WSN的研究涉及网络、通信、嵌入式系统、信号处理、传感器、MEMS等多个学科与领域，滋生出了众多研究方向，我们进行粗略概括与分类，表示在图1-3中。1.5.2研究进展1.操作系统—TinyOS

TinyOS是UCBerkeley的DavidCuller领导的研究小组为WSN量身订制的嵌入式操作系统。因为与同样是他们设计的Mote硬件系列平台珠联壁合而声名鹊起，目前已经成为WSN研究领域实事上的标准平台。下一页返回1.5WSN研究

WSN对操作系统提出了特殊要求。卞要表现在:(1)节点的计算资源有限，需要尽可能地减小系统开销。

(2)节点由电池供电，且要求较长的土作周期，因此需要系统的能耗管理策略与方案，包括操作系统的支持。

(3)节点的各模块之间需要一定的调度协调机制，同时一支持并发控制。

(4)观测任务需要操作系统支持实时性。上一页下一页返回1.5WSN研究

为此，在TinyOS的设计之初，D.Culler等人确定了全构件化、事件驱动、无内核和用户空间区分的设计原则来满足WSN的特殊需要。应用程序根据需要选配、修改和创建构件，使系统开销最小化。构件与构件之间通过“命令”(Command)和“事件”(Event)相联系，“命令”向下调用(CallDown),“事件”则向上调用(CallUp)。

TinyOS没有线程概念，不存在阻塞，也无需维护进程的上下文，只用维护返回栈。操作的调用与完成是分离的过程。“命令”的调用从不阻塞，返回时一采用“事件”方式。因此，TinyOS被称为“事件驱动”的操作系统。到目前为止，WSN还没有一个公认的体系结构，不像传统网络那样有明显的层次划分和明确的功能抽象与定义。因此，在已有TinyOS1.x中，模糊了这些的概念，采用了平面型的设计思想。但研究和应用出现的问题启发人们重新审视WSN操作系统的设计原则。上一页下一页返回1.5WSN研究

2.无线通信技术无线通信技术是当前网络与通信研究中最活跃的领域，新技术层出不穷，但在众多的通用标准无线通信技术中WSN却一直没有锁定其中一种作为’已的卞流通信技术，多数试验节点直接选用了最纯粹的射频通信技术，例如流行的UCBMote系列节点曾经使用的TR1000和CC1000，就是来自Chipcon公司射频通信芯片，没有任何附加的MAC协议。上一页下一页返回1.5WSN研究

2003年10月IEEE802.15.4标准颁布，为WSN提供了一种新的无线通信方案。因为它低功耗、低成本、低速率的明显技术特点与WSN的设计要求暗合，研究者一普遍认同它应该是WSN理想的无线通信技术，它的主要技术特点包括:(1)功耗低(2)成本低(3)延时短(4)规模大(5)更安全上一页下一页返回1.5WSN研究3.节点试验平台

WSN的研究具有很强试验科学的特点。传统的互联网研究已经具有很长的历史，利用已有的基础化设施，为新的研究搭建大规模的物理试验床(如组播应用研究的Mbone)和虚拟网络试验环境(如P2P研究的PlantLab)相对比较容易。但WSN是一种全新的网络技术，与传统的互联网差别较大，甚至网络体系结构都将截然不同，因此WSN研究可继承的资源也就十分有限，研制网络节点，搭建一定规模的试验床自然成了WSN研究初期的一个主要任务。到目前为止，已经出现了众多节点试验平台。根据时间先后和技术特点，我们将它们大致分为四代。上一页下一页返回1.5WSN研究第一代(19961999年):代表性的平台有UCLA的WIVS,UCBerkeley的Smart-Dust、WeC和Rene。第二代(2000-2001年):这一时期WSN的研究开始受到越来越多研究者的关注。于是，相继出现了多种试验平台，典型的有UCB的Mica与Dot,MIT的uAMPS一下和uAMPS-II，以及Rockwell公司的HYDRA。它们为WSN研究提供了通用的试验平台，被用在不同机构资助的研究项目进行原理性验证和算法测试评估。

上一页下一页返回1.5WSN研究第三代(2002-2003年):随着研究的深入，人们认识到对于特殊环境中自组织WSN的应用，降低能耗，尽可能延长网络生命周期是一个非常关键的问题。于是，研究者一开始从各个角度出发才找减小系统能耗的方案，节点设计自然也不例外。其间产生了两款代表性的试验平台:Mica2和MicaDot2，以及VASAJP1实验室的SensorWeb。第四代(2004至今):2004年底，Chipcon率先发布了支持ZigBee的射频芯片，这成为WSN节点研发的又一个分水岭。随后的研究开始币点关注新无线通信技术与标准在WSN节点设计中的应用。到目前为止，已经相继出现了一系列第四代节点，典型的有MicaZ、Telos、EmberVode}Imote、Imote2、BTVode3和DSYS25。上一页返回1.6WSN研究中的若干问题1.6.1关于WSN的定义目前大多数研究者一普遍接受的既成事实的WSN定义是:大规模、无线、自组织、多跳、无分区、无基础设施支持的网络、其中的节点是同构的、成本较低、体积较小、大部分节点不移动、被随息撒布在工作区域，要求网络系统有尽可能长的工作时间。这一附加了诸多限制条件的定义充分考虑了战场等恶劣环境下的特殊要求，所界定的技术目标很高，使理论研究面临很大的挑战，这是该定义积极的一面。但在具体工程应用中，该定义的局限性有时也会影响，甚至是束缚研究思路。下一页返回1.6WSN研究中的若干问题1.6.2WSN研究方法与传统网络的研究相比，WSN的研究具有较强的试验科学的特征，强调试验而非单纯依赖仿真。某些研究，如定位和时一间同步等，仅通过仿真根本无法完成。多数研究都是在硬件试验平台上进行的，因此，搭建试验环境应该是WSN研究的第一步。WSN的研究需要广泛的合作。因为它本身就是一个交叉学科，加之应用系统多样化的要求，抽象它一般息义上的技术要求和指标是一件不容易的事，需要包括用户、应用领域专家、软硬件设计者密切协作，方可构建出既有共性又有特性的应用系统。上一页下一页返回1.6WSN研究中的若干问题

经过十余年的酝酿、尝试和争论，WSN研究的科学意义和应用价值已经逐渐明晰，虽仍有不同意见，但学术界和工业界对WSN研究日渐高涨的关注程度却是不争的事实。随着研究的不断深入，新思路、新想法会不断涌现。虽然目前我们很难规划出一个相对系统的框架结构来指导该领域的研究，但至少需要将WSN的研究划分为两大类:即基础研究和应用研究，它们分别对应如前所述的狭义无线传感器网络研究和广义无线传感器研究，各自具有不同的侧重点，前者一需要强调理论突破，后者则偏重挖掘WSN的应用潜能。上一页返回图1-1计算设备的演化历史返回图1-3WSN的研究方向及分类返回第2章路由协议2.1概述2.2以数据为中心的路由协议2.3集群结构路由协议2.4地理位置信息的路由协议2.5WSN路由协议的发展2.1概述WSN是一种无基础设施的网络，如图2-1所示，它由一组传感器节点以自组织方式构成，其目的是协作感知、采集和处理网络覆盖地理区域中感知对象的信息，并对这些数据进行处理，获得详尽准确的信息，最终将这些信息传送到需要的用户。用户通过终端的管理和分析软件来观测网络的运行状况，并且可以对网络中的各个节点进行管理和监控。从功能上来讲，WSN中的路由协议是一套将数据从源节点传输到目的节点的机制。WSN路由协议的主要设计目标是在满足应用需求的同时尽量降低网络开销，取得资源利用的整体有效性，扩大网络容量，提高网络吞吐率。下一页返回2.1概述

2.1.1WSN路由协议的特点路由技术是WSN核心技术之一。从路由的角度看，WSN既不同于传统的Internet网络和蜂窝移动网，又不同于移动自组网(MAVET,MobileAdhocNetwork)，它有自己的特点:如节点能量不可补充，网络中存在大量的数据冗余等，这些问题都是传统网络不曾遇到过的，这决定了传统网络路由协议不能用于WSN。上一页下一页返回2.1概述同传统的无线网络相比，WSN有自己独特的特征:首先，WSN中节点数量庞大，给每个节点配置一个全局的ID号是不可能的，传统的以IP地址为基础的路由协议不适合WSN;其次，WSN多数应用背景是多个源节点感知数据，然后将感知数据传给一个指定的目的节点Sink，不要求建立网络中任意两点之间的路由路径，这给设计高效的路由协议带来了可能性;再次，WSN的路由协议和应用密切相关，对不同的应用需求，需要使用特定的路由协议，这可以简化协议，节省能量;最后，WSN中存在大量的数据冗余，路由协议的设计需要考虑对这些冗余信息的探测和处理以达到节省能量和提高带宽利用率的目的。上一页下一页返回2.1概述2.1.2WSN路由协议关键技术问题WSN具有广阔的应用前景，但是由于节点能量、处理能力、储存空间以及带宽等的限制，它的大规模应用还存在许多需要克服的问题，设计一个满足需要的高效的路由协议是目前面临的一个主要问题。WSN的基本特点可以概括为:能量受限、网络规模大、节点移动性差、网络拓扑易变化、数据冗余以及数据流量分布不均匀等，因此，设计一个WSN路由协议面临的问题和挑战主要有以下几方面。上一页下一页返回2.1概述1.传感器网络节点能量受限的特点使节能成为路由协议最主要的优化目标2.传感器网络的规模巨大.其路由协议必须具有高可扩展性3.传感器网络拓扑变化性强4.传感器网络路由中使用数据融合技术5.传感器网络中流量分布不均匀上一页下一页返回2.1概述2.1.3WSN路由协议的分类可以将现有的无线传感器路由协议分为四类:以数据为中心的路由协议、基于集群(Clustering)结构的路由协议、基于地理信息(Geographic)的路由协议以及基于QoC的路由协议。1.以数据为中心的路由协议以数据为中心的路由协议对感知到的数据按照属性命名，对相同属性的数据在传输过程中进行融合操作，减少网络中冗余数据的传输。这类协议同时集成了网络路由任务和应用层数据管理任务。上一页下一页返回2.1概述

2.集群结构的路由协议集群结构的路由协议重点考虑了路由算法的可扩展性，其主要特征是将传感器节点按照特定规则划分为多个集群，通过该集群的头节点(CH,ClusterHeader)汇集集群内感知数据或者转发其他集群头节点的数据。3.地理位置信息路由协议地理位置信息路由协议假定传感器节点能够知道自身地理位置或者通过基于部分标定节点的地理位置信息计算自身地理位置。节点的地理位置信息可以作为一个辅助条件，用来改善一些已有的路由算法的性能，比如将感知数据或者查询请求发送到指定方向从而减少泛洪(Flooding)带来的数据无效传输的问题，也可以直接使用地理位置信息来实现路由。上一页下一页返回2.1概述4.基于QoS的路由协议基于QoS的路由协议在实现路由发现和维护的同时，还力求满足网络的QoS需求。一些协议在建立路由路径的同时，还考虑节点的剩余能量、每个数据包的优先级、估计端到端的时延，从而为数据包选择一条最合适的发送路线。本书第10章会单独介绍WSN中的QoS问题，本章不对基于QoS的路由协议进行讨论。上一页返回2.2以数据为中心的路由协议2.2.1SPIN路由算法

SPIN协议是最早的一类无线传感器路由协议的代表，它主要是对泛洪路由协议的改进。

1.基本思想

SPIN协议是一种以数据为中心的自适应路由协议。该协议考虑到了WSN中的数据冗余问题一邻近的节点所感知的数据具有相似性，通过节点间协商(Vegotiation)的方式减少网络中数据的传输的数据量。节点只广播其他节点所没有的数据以减少冗余数据，从而有效减少能量消耗。下一页返回2.2以数据为中心的路由协议SPIN协议有两种工作模式:SPIN1和SPIN2,SPIN2在SPIN1的基础上作了一些能量上的考虑，本质上还是一样的。如图2-2所示，在SPIN1中，当节点A感知到新事件之后，主动给其邻居节点广播描述该事件的元数据ADV报文，收到该报文的节点B检查自己是否拥有ADV报文中所描述的数据，如图2-2(a)。如果没有的话，节点B就向A发送REQ报文，在REQ报文中列出需要A节点给出的数据列表，如图2-2(b)。当节点A收到了REQ请求报文，它就将相关的数据发送给节点B，如图2-2(c)。节点B发送ADV报文通知其邻居节点自己有新的消息，如图2-2(d)，由于A节点中保存有ADV的内容，A节点不会响应B节点的ADV消息。协议按照这样的方式进行，以实现SPIN1的算法。如果收到ADV报文的节点发现自己已经拥有了ADV报文中描述的数据，那么它不发送REQ报文，图2-2(e)中有一个节点没有发送REQ报文。上一页下一页返回2.2以数据为中心的路由协议

2.关键问题

SPIN协议通过节点之间的协商，解决Flooding协议和Gossiping协议的内爆和重叠现象。泛洪协议是一种原始的无线通信路由协议。该协议规定，每个节点接收来自其他节点的信息，并以广播的形式发送给其邻居节点。如此继续下去，最后数据将传送到目的节点。这个协议容易引起信息的“内爆(Implosion)”和“重叠(Overlap)”，造成资源的浪费。内爆现象如图2-3所示。重叠现象是传感器网络特有的，如图2-4所示。上一页下一页返回2.2以数据为中心的路由协议SPIN协议通过协商机制很好地解决了内爆的问题，对于重叠问题也进行了一定的处理。特别是SPIN协议支持数据融合，SPIN2进一步地引入了能量管理的概念，一定程度上优化了网络负载，延长了网络的生存时间。3.扩展分析SPIN协议是一种不需要了解网络拓扑结构的路由协议，由于它几乎不需要了解一跳范围内的节点状态，网络的拓扑改变对它的影响有限，因此该协议也适合在节点可以移动的WSN中使用。SPIN协议通过使用协商机制和能量自适应机制，节省了能量，解决了内爆的问题。SPIN协议引入了元数据的概念，通过这种数据压缩方法来减少数据的传输量，是一种值得借鉴的方法。在SPIN协议中出现了多个节点向同一个节点同时一发送REQ的情况，有关的退避机制需要考虑。上一页下一页返回2.2以数据为中心的路由协议2.2.2DD路由算法定向扩散协议(DD,DirectedDiffusion)是一种基于查询的路由方法，这和传统路由算法的概念不一样。DD算法是一种基于数据相关的路由算法，Sink节点周期地通过泛洪的方式广播一种称为“兴趣”的数据包，告诉网络中的节点它需要收集什么样的信息。“兴趣”在网络中扩散的时候同时也建立了路由路径，采集到和“兴趣”相关的数据的节点通过“兴趣”扩散阶段建立的路径将采集到的“兴趣”数据传送到Sink节点。1.基本思想定向扩散协议是一种基于查询的路由协议，该协议中引入几个基本概念:兴趣、梯度和路径加强。整个过程可以分为兴趣扩散、梯度建立以及路径加强三个阶段，如图2-6所示。上一页下一页返回2.2以数据为中心的路由协议2.关键问题DD路由协议核心的问题是解决兴趣扩散阶段的梯度建立过程、张化路径的选择和建立过程以及路由的维护过程。在兴趣扩散阶段，Sink节点周期性地向邻居节点广播兴趣消息。兴趣消息中包含有任务类型、目标区域、数据传输率、时一间戳等参数。每个节点都有一个兴趣Cache,兴趣Cache中的何项都对应着不同的兴趣。兴趣Cache中的每个兴趣表项包含如下几个字段:时间字段(指不最近收到匹配兴趣的时一间信息);梯度字段(指不和该兴趣消息有联系的邻居节点所需的数据传输率和数据发送方向，也就是感兴趣的邻居节点);持续时间字段(指不兴趣大致的生命周期)。上一页下一页返回2.2以数据为中心的路由协议一个兴趣表项可能有多个梯度域，每个梯度域对应一个和该“兴趣”消息有联系的邻居节点。节点接收到一个“兴趣”消息之后，再把该“兴趣”消息发送给与自己相邻的节点。如果一个节点收到的“兴趣”消息和刚刚转发的“兴趣”消息一样，为了避免消息循环则丢弃该“兴趣”消息。兴趣扩散完成后，对于某个事件的梯度也就在网络中建立起来了。当传感器节点采集到与兴趣匹配的数据时，将数据发送给对应梯度域中的邻居节点。节点接收到一个数据后，首先在兴趣Cache中查找是否有相匹配的兴趣表项，如果没有匹配的兴趣表项，表不此节点不需要接收这个数据，该数据被丢弃;如果找到了匹配的兴趣表项，就在数据Cache中查找最近是否收到过相同的数据(防止形成环路)，如果不存在相同的数据，就把该数据加到数据Cache中，否则丢弃该数据。上一页下一页返回2.2以数据为中心的路由协议接收节点通过检查数据cache，可以计算接收数据的传输率。接收节点查找相关的兴趣表项可以获得梯度域中登记的数据传输率信息，当梯度域中记录的数据传输率不小于接收数据率时，接收节点将自己接收到的数据传给和梯度域对应的邻居节点;否则，当梯度域中记录的数据传输率不小于接收数据率时，接收节点将按照梯度域中记录的数据传输率来向相关的节点发送数据。这种方法下，同一个数据包会经过多条路径到达Sink节点，Sink节点通过一定的标准，比如最小延时，来选择一条最优的路径作为强化路径。上一页下一页返回2.2以数据为中心的路由协议在DD路由协议中，为了对失效路径进行修复和重建，规定已经加强过的路径上的节点都可以触发和启动路径的加强过程。如图2-7所示，节点C能正常收到来自邻节点的事件，可是长时间没有收到来自数据源的事件，节点C就断定它和数据源之间的路径出现故障。节点C就主动触发一次路径加强过程，重新建立它和数据源之间的路径。3.扩展分析DD算法是一个以数据为中心的经典路由算法，该方法的显著特点是通过Sink节点发起兴趣查询消息，通过泛洪的方法建立传感器节点到Sink节点的路由。DD路由协议需要通过Sink节点完成对节点的查询，因此不能用于大规模的网络。该算法主要用于具有大量查询而只有少量事件的应用场景，如果网络拓扑结构频繁变动，该算法性能将大幅下降。上一页返回2.3集群结构路由协议集群结构路由协议实际上是一种分层结构的路由协议，该思想下网络通常被划分为簇，每个簇由一个簇头和多个簇成员组成。典型的分层路由协议有LEACH、PEGASIS、TEEN、APTEEN和基于虚拟网格的路由协议TTDD。2.3.1LEACH路由算法LEACH(Low-EnergyAdaptiveClusteringHierarchy)是最早提出的分层路由算法，出发点主要是考虑一簇内节点的能量消耗问题，目的是为了延长节点的工作时间，并且实现节点的能耗平衡。下一页返回2.3集群结构路由协议1.基本思想LEACH是MIT的Chandrakasan等人为WSN设计的低功耗自适应路由算法，其基本思想是网络周期性地随机选择簇头节点，其他的非簇头节点以就近原则加入相应的簇头，形成虚拟簇。簇内节点将感知到的数据直接发送给簇头，由簇头转发给Sink节点，簇头节点可以将本簇内的数据进行融合处理以减少网络传输的数据量。2.关键问题LEACH中每个节点可以直接同Sink节点通信,由于Sink和节点的距离较大，节点直接和Sink通信会消耗大量的能量，使用LEACH后形成一个两级的星型网络，如图2-9所示。簇内节点直接和簇头通信，由簇头节点和Sink通信.上一页下一页返回2.3集群结构路由协议簇头节点的选择依据网络中所需的簇头节点数和迄今为止每个节点已成为簇首的次数来决定。具体的选择办法是:每个传感器节点选择[0,1]之间的一个随机数，如果选定的值小于某一个阀值T(n)，那么这个节点成为簇头节点，T(n)的计算如下:上一页下一页返回2.3集群结构路由协议式中，N表不网络中传感器节点的个数，k为一个网络中的簇头节点数，r为已完成的回合数，G为网络生存期总的回合数。这里的一个回合表示一个周期，每个回合分为两个阶段:簇的建立和稳定的数据传输阶段，稳定传输阶段的持续时间要大于簇建立所需要的时间。选定簇头以后，簇头节点通过广播告知整个网络自己成为簇头的事实，网络中的非簇头节点根据接收信号的强度决定从属的簇，并通知相关的簇头，最后簇头节点采用TDMA方式为簇中每个节点分配传输数据的时间片。上一页下一页返回2.3集群结构路由协议

3.扩展分析

LEACH协议从传输数据的能量和数量上进行了优化，提高了网络的生存时间，但是还是有一些问题需要解决。首先，它需要网络协议和硬件支持射频功率的自适应和动态调整;其次，协议无法保证簇头节点能遍及整个网络，很可能出现被选的簇头节点集中在网络中某一区域的现象。2.3.2TEEN和APTEEN路由算法

TEEN(Threshold-SensitiveEnergyEff面entSensorNetwork)和APTEEN(A-daptivePeriodicTEEN)都是LEACH算法的改进。上一页下一页返回2.3集群结构路由协议1.基本思想TEEN和APTEEN都是对LEACH算法的改进，TEEN是针对LEACH算法实时性不强的问题提出的一种解决方案，但是TEEN不能实现周期性地采集数据LEACH算法主要是实现对环境数据的周期性采集)。APTEEN算法综合了LEACH和TEEN的思想，提出了一种既可以周期性地采集数据，又可以实时采集数据的方法。TEEN采用与LEACH相同的多簇结构和运行方式。不同的是，在簇的建立过程中，随着簇首节点的选定，簇首除了通过TDMA方法实现对节点的调度外，还向簇内成员广播有关数据的硬阀值和软阀值两个参数。上一页下一页返回2.3集群结构路由协议APTEEN是一种结合了响应型和主动型策略的混合型网络路由协议。在APTEEN协议下，节点在检测到突发事件数据时一会采用与TEEN相同的机制(响应型策略)。为了改变TEEN不能周期发送数据的缺点，APTEEN在TEEN的基础上定义了一个计数器，节点何发送一次数据就将该计数器清零，当计数器时间到达的时候，不管当前的数据是否满足软、硬门限的要求都会发送这个数据(主动型策略)。2.关键技术APTEEN簇头的建立过程采用LEACH-c的方式，该方式采用集中式控制的思想，由基站(BS)决定簇头节点的个数并且指定簇头节点。一旦簇头建立起来，每个簇头节点就向簇内节点广播以下参数:上一页下一页返回2.3集群结构路由协议属性(A):用来表不用户期望获取信息的一组物理参数。阀值:该参数由硬阀值和软阀值组成，具体用法和TEEN的一样。调度:采用TDMA调度方法，为簇内每个节点分配相应的时间片，注息节点之间不需要时间同步。计数时间(CT):表示一个节点成功发送报告的最大时间周期。在WSN中相邻节点感知到的事件很可能相同，为了减少冗余，APTEEN算法中，如果发现两个相邻的节点足够近，那么它们形成节点对，一个节点对中何次只有一个处于空闲监听状态(IDLE),而另一个则处于睡眠状态(Sleeping)上一页下一页返回2.3集群结构路由协议簇头节点融合自己收到的所有数据，并且在分配给它的时间片中把所有数据发送给上层簇头或者一基站。一旦基站从簇头接收到所有的数据，通过分析可以判断哪些是查询响应数据，然后基站通过自己的下行链路广播它们，以此来告知相关节点数据已经收到。为了避免簇内的冲突，可以采用CDMA技术，不同的簇可以采用不同的CDMA码，但是簇头到基站的上行链路需要采用相同的CDMA码，同样地，基站到所有传感器节点也需要使用相同的CDMA码。在TDMA的调度中加入了一个单独的时间片，该时间片用于基站和传感器节点的通信。上一页下一页返回2.3集群结构路由协议由于每个簇头所容纳的节点数不相同，这样每个TDMA帧的长度都不一样。基站需要计算最大的TDMA长度，并且给每个簇头节点分配相应的时间片，簇头在分配给自己的时间片内向基站传送自己收集到的数据。分配给簇头的时间片要在本簇区域中所有的传感器节点的时间片之后，这样才能保证簇头节点收集到足够的数据。基站向传感器节点发送数据的时间片在所有时间片之后，一个完整的TDMA帧可以用图2-12表示。上一页下一页返回2.3集群结构路由协议APTEEN算法支持三种查询方式:1)历史数据查询如图2-13所示，接收到查询消息的节点，在自己的时间片内向簇头发送与查询相关的数据。簇头融合所有的数据，在分配给它的时间片发送这些数据到基站。2)当前网络的一次查询如图2-14所示，传感器节点在自己的时间片将查询响应数据发送给自己的簇头，基站在TDMA帧尾接收到该数据。3)持续监控某一事件的连续查询这个是当前网络的一次查询的多次重复，第一轮的延时和当前网络的一次查询相同，接下来的延时就是一个TDMA帧长度。上一页下一页返回2.3集群结构路由协议3.扩展分析TEEN算法中提出的硬阀值和软阀值的方法可以很好地减少网络数据量，提高网络能量利用率和网络生存时间。TEEN协议主要用在实时性要求比较高的场合，可以对突发事件做出快速响应。TEEN的缺点是不能实现数据的周期性采集，如果网络节点没有接收到相关阀值，那么节点就不会与簇头进行通信，用户也就完全得不到网络的任何数据。APTEEN协议在TEEN的基础上加入了对周期性事件报告的支持。TEEN和APTEEN的主要缺点体现在:构建多层簇以及设置阀值在实现上较为复杂，基于属性命名的查询机制也会带来额外的开销。上一页下一页返回2.3集群结构路由协议2.3.3TTDD路由算法

TTDD(Two-tierDataDissemination)路由算法提出了一种新的应用背景，该应用场景中，传感器节点不动，Sink节点移动，而且有多个。TTDD算法针对这个场景，从能耗和功能上给出了比较好的解决方法。1.基本思想TTDD是一个层次路由协议，主要用在网络中存在多个Sink节点以及Sink节点可以移动的情况。当多个传感器节点探测到事件发生时，选择一个节点作为发送数据的源节点，源节点以自身作为格状网(grid)的一个交叉点构造出一个格状网，图2-15为以节点B为源节点建立的格状网。源节点先计算出四个相邻交叉点位置，利用贪婪算法请求最接近交叉点位置的节点成为转发节点，转发节点继续这个过程直至请求任务超时或到达网络边缘。上一页下一页返回2.3集群结构路由协议

2.关键技术

TTDD的运行需要解决三个问题:格状网的构造和转发节点的选取;对Sink节点移动的支持;节点失效时格状网的维持。

TTDD算法首先要解决的问题是格状网的构造问题，以图2-15描述的一个网络为例，它是以节点B为源节点建立的一个格状网。TTDD算法需要地理位置信息的支持，网络中每个节点都知道自己的位置，对于Sink节点，可以不用知道自己的地理位置)，假设B点的坐标为LB=(x,y),每个格子单元的边长为a，那么以B为中心的网络中所有的交叉点的坐标LP=(xi,yi)可以用下面的式子表示:上一页下一页返回2.3集群结构路由协议

B广播数据公告消息，离B节点的交叉点位置最近的节点接收该公告消息，这样B的四个交叉点处的转发节点就建立起来了。转发节点继续相同的操作，守找离B节点两跳距离的交叉点处的转发节点，这一过程一直继续，直到遇到网络边界或者任务超时为止。格状网建立起来后就可以响应Sink节点的查询任务了。在TTDD算法中，Sink节点通过泛洪来实现查询，但是泛洪的区间限制在一个很小的范围中，一般是一个网格单元，这样可以保证至少可以找到一个转发节点，泛洪区间的大小可以视情况适当地放大。当某个转发节点需要响应该查询时，就将该转发节点作为发起本次查询的Sink节点的直接转发节点。当直接转发节点收到查询消息后，通过建立格状网时建立的路径向自己的上游(upstream)节点传送查询消息，查询消息一直传送到源节点。上一页下一页返回2.3集群结构路由协议在查询消息传播路径上的转发节点需要保存自己的下游(downstream)节点以及相应的查询发起节点(Sink)的信息，这些信息用来以后将数据发往正确的Sink节点，因为同一个转发节点可能被多个Sink节点使用，如图2-16中的节点G，对发往不同Sink的数据包，需要通过这些信息来区分。当直接转发节点接收到多个Sink节点对同一个数据的查询消息时，它只向自己的上游节点转发一次查询消息。同样地，转发节点如果从不同的下游节点接收到对同一个数据的查询，那么也只向上游节点转发一次查询消息。上一页下一页返回2.3集群结构路由协议在查询消息传播到源节点的过程中，所有查询消息经过的节点都维护一个软状态(soft-state)，实质上是建立一个计数器，通过这个计数器来描述一条路径的生存时间。为了从自己的上游节点收集到信息，每个转发节点都会周期性地向上游节点发送上游修正消息。通过上游修正消息来维护自己的软状态，以保证路径的有效性。当查询消息到达源节点后，源节点通过查询消息传播的反向路径将数据发送到直接转发节点。如果一个转发节点融合了多个查询消息，那么它就将数据包复制发给每个相关的下游节点。上一页下一页返回2.3集群结构路由协议每个Sink节点和两个虚拟的节点相关，称为初级代理和直接代理。在开始的时候，初级代理PA(PrimaryAgent)和直接代理IA(ImmediateAgent)是同一个节点，由Sink节点选取一个邻居节点担当。当直接转发节点收到数据以后，将数据转发给PA代理节点，由PA节点将数据转交给IA节点由IA将数据发给Sink节点。由数据源建立的格状网也有自己的生存时间，数据源在数据公告消息中加入网格生存时如果在源节点规定的时间内，形成格状网的相关节点没有收到任何修改生存时间的消那么在超时的时候，节点就会取消自己的角色，网络也就不存在了。上一页下一页返回2.3集群结构路由协议针对节点失效的情况，TTDD算法提出了上游信息复制(upstreaminformationduplication)的方法。每个转发节点都从自己的邻居节点中选择一个或多个节点作为自己的备份节点，在这些备份节点中保存本转发节点的上游节点的位置。当这个转发节点失效以后，从它的下游邻居节点发送来的上游修正消息(该消息主要是用来请求数据)会被备份节点响应，该备份节点会向上游节点(上游节点的地理位置信息已经保存在该节点中了)发送上游修正消息以请求数据。上一页下一页返回2.3集群结构路由协议3.扩展分析TTDD提出了一种新的应用场景，和以前讨论的以Sink为中心建立路由的场景完全不同，TTDD的路由以源节点为中心展开，整个网络变成数据源节点捕捉Sink节点的一个格状网。当Sink节点被发现的时候，数据通过这个格状网传输到Sink。TTDD中提出的透明传输的概念，可以简化网络的管理和维护。与DD协议相比，该协议采用单路径，能够提高网络生存时间。不过这个算法中节点必须知道自身位置，非Sink点位置不能移动，而且要求网络节点密度较大，最不好确定的是网格单元的大小，这个参数对网络的性能有很大的影响。上一页返回2.4地理位置信息的路由协议在路由协议中使用地理位置信息，一般有两种用途:(1)使用地理位置信息作为其他路由算法的辅助。在地理位置信息的支持下，可以限制网络中搜索路由的范围，减少路由控制分组的数量，一般用于基于泛洪的路由协议的改进。(2)基于地理信息的路由协议。该类协议直接使用地理位置信息建立路由，节点直接根据位置信息制汀数据转发策略。本节介绍几种利用地理位置信息的路由协议，它们是位置辅助路由协议LAR,基于地理位置信息的路由协议GAF,GPSR和GEAR。下一页返回2.4地理位置信息的路由协议2.4.1LAR路由算法LAR(Location-AidedRouting)路由协议是一种使用地理位置信息作为辅助的路由算法，地理位置信息在这里主要用于选取优化路径。1.基本思想LAR路由协议主要提出一种思想一使用地理位置信息来改进基于泛洪的路由，比如DSR路由、AODV路由等。在基于泛洪的路由中，源节点S要建立到目的节点D的路径时，它向周围相邻节点广播路由请求分组(RREQ),当RREQ分组扩散到全网后会建立所需的路由。这种方法需要在全网范围内实现广播查找，大量非相关的节点也牵扯其中，导致路由建立开销过大，LAR使用节点的地理信息来减少参与路由建立过程的节点数，从而降低网络路由开销。上一页下一页返回2.4地理位置信息的路由协议

2.关键技术根据LAR协议的描述，当源节点S知道t时刻目标节点D的位置和平均移动速度v，就可以估计出t1时刻D可能出现的区域，该区域称为期望域(ExpectedZone)。为了寻找路由，源节点需要在一定范围内扩散路由请求分组，该范围称为寻找域(RequestZone)。下面详细介绍这两个概念。1)期望域假设源节点S知道目的节点D在t0时一刻的位置(Xd,Yd)和平均移动速度v，那么S定义D的期望域是以(Xd,Yd)为圆心，以R=v*(t1-t0)为半径的圆，如图2-17(a)所示。如果在(t1-t0)时段，节点的平均移动速度大于v，那么t1时刻节点D可能在该期望域之外。上一页下一页返回2.4地理位置信息的路由协议期望域只是源节点S对目的节点D在t1时一刻可能出现的区域的估计，并不一定保证在期望域中一定能找到节点D。如果S并不知道节点D的预先位置，那么S将整个网络作为期望域，此时LAR算法退化为普通的泛洪算法。关于节点D的信息越多，期望域范围也就越小，例如，如果S知道D的运动方向(向北移动)，那么图2-17(a)的圆形期望域可以缩为一个半圆，如图2-17(b)所示。2)寻找域为了减少路由寻找开销，节点S为RREQ限定了一个路由请求区域，称为寻找域。只有在寻找域中的节点才转发RREQ。为了增加RREQ到达节点D的成功率，寻找域应该包括期望域以及期望域以外的其他区域，如图2-18所示。上一页下一页返回2.4地理位置信息的路由协议LAR算法对寻找域的定义依赖于所采用的算法，中间节点只需要判断自己是否位于寻找域中，下面介绍两种简单的方法。

(1)LAR机制1.该机制定义才找域为一个包含了节点S和节点D的矩形区域，如图2-19所示(这里我们主要讨论平面网络)，该矩形的边分别与X,Y轴平行。图2-19(a)中节点S在期望域内部，寻找域的顶点是A,B,C和D；图2-19(b)中，节点S在期望域外部，寻找域的顶点分别为S,A,B和C。两种情况下，源节点S都可以决定寻找域的四个顶点。上一页下一页返回2.4地理位置信息的路由协议(2)LAR机制2.该机制规定RREQ分组携带以下信息:①源节点S到目的节点D的距离DISTS.②目的节点坐标(Xd,Yd)3.扩展分析LAR使用地理位置信息对基于泛洪机制的路由协议(DSR,AODV等)进行改进，它限制了路由查找的范围，减少了网络的开销，加快了算法的收敛速度。LAR协议是为Adhoc网络开发的，在这种网络中维护节点的位置信息需要很大的开销，但是对于WSN来说，由于目的节点大多数情祝下是唯一的而且是固定的，这就免除了对目的节点的位置信息的维护，LAR协议的思想也可在WSN中运用。上一页下一页返回2.4地理位置信息的路由协议2.4.2GAF路由算法GAF(GeographicalAdaptiveFidelity)路由算法也是一种使用地理位置信息作为辅助的路由算法，地理位置信息除了用于选择优化路径外，还用于确定等价节点。1.基本思想GAF算法通过让节点尽量处于关机状态来节省能量，本质上还是使用地理位置信息作为辅助，提高网络性能的一种方法。GAF算法的提出是考虑到节点不仅在发送和接收分组的时候需要消耗能量，当节点处于空闲状态的时候也要消耗能量。最近的测量表明，空闲、接收和发送的功率消耗之比为1:1.2:1.7，这表明空闲状态下的能量消耗不能忽略。上一页下一页返回2.4地理位置信息的路由协议2.关键技术GAF算法需要解决的问题包括:等价节点的确定、分布式协商算法以及对节点移动的自适应。1)等价节点的确定所谓的等价是指对中继转发的效果而言，一个节点可以代替另一个节点。根据这个定义，节点的等价性与源节点和目的节点无关。为了达到这个目的，GAF将节点分布的整个区域划分为小的“虚拟网格”。上一页下一页返回2.4地理位置信息的路由协议图2-21构造了三个虚拟网格A,B,C，根据虚拟网格的定义，节点1可以到达节点2,3,4中的任何一个，而节点2,3和4也都可以到达5。因此2,3和4是等价的，其中任息两个可以关闭。2)分布式协商算法在GAF中，网络节点有三种状态:休眠状态、发现状态和激活状态，图2-22给出了GAF中节点状态的转换图，只有处于激活状态的节点才参与数据的转发。上一页下一页返回2.4地理位置信息的路由协议节点初始化时处于发现状态，这个状态下节点打开收发信机，通过交换发现报文以发现相同网格内的其他节点。当节点进入发现状态时，为其设定一个长度为Td的定时器，当定时器时间到达时，节点广播其发现报文，然后转入激活状态。定时器计时可以被其他节点的发现报文暂停。当节点进入激活状态时，就设定一个长度为Ta的定时器定义节点处于激活状态的时间。Ta到达后，节点将返回发现状态。处于激活状态时，节点何隔T‘d(这个地方的T‘d和处于发现状态的Td可以不同)重新广播其发现报文。上一页下一页返回2.4地理位置信息的路由协议当节点转入休眠状态时，就关闭收发信机。处于休眠状态的节点在休眠了一段时间Ts后自动唤醒，进入发现状态。3)对节点移动的自适应GAF尽量调节网络中处于激活状态的节点数，以使参与路由的节点数保持在一个相对稳定的水平上，理想的情况是:在任何时间，每个虚拟网格中都只有一个处于激活状态的节点。然而随着节点的移动，处于激活状态的节点可能会移出其所在网格。这样会使其先前所在的网格中没有一个处于激活状态的节点，从而降低了路由的可靠性。当节点移动性比较强时，丢包率会比较高。上一页下一页返回2.4地理位置信息的路由协议GAF通过预测并报告节点规律的方式，解决节点移动带来的路由断裂问题。GAF让每个节点预测其离开所在网格的时间EVGT(EstimatedVoleGridTime)，并且将此信息放入发现信息中。当其他节点进入休眠状态以后，它们的休眠时间长度取决于EVAT和EVGT中较短的那个，这样就可以适应节点移动性带来的副作用。这种修改没有改变节点的分级规则，但是节点的休眠时间可能会变短。上一页下一页返回2.4地理位置信息的路由协议3.扩展分析严格来说，GAF算法不属于路由协议，和数据融合技术一样，它只是一种节能策略。这种策略希望在节点密集分布的区域中，在保证网络连通性的前提下，尽量减少处于激活状态参与路由中转的节点数。GAF通过划分地理网格，让网格内尽量只有一个节点处于激活状态以节省能量。GAF的这种思想是有用的，有很多算法采用这种思想来提高网络的生存时间，这些方法主要是围绕上面的分布式协商算法来展开，希望找到一种不需要或需要比较少的地理位置信息就可以实现网络等价节点的划分。上一页下一页返回2.4地理位置信息的路由协议2.4.3GPSR路由算法GPSR(GreedyPerimeterStatelessRouting)路由算法是一种直接使用地理位置信息建立路由路径的方法，GPSR路由算法中使用了贪婪策略，根据使用的贪婪策略的不同，演化出不同的方法。由于使用贪婪算法会出现局部最优问题，根据不同的解决方法，也演化出很多不同的方法。上一页下一页返回2.4地理位置信息的路由协议1.基本思想GPSR路由算法是使用地理位置信息实现路由(非辅助作用)的一种算法，它使用贪婪算法来建立路由。当节点S需要向节点D转发数据分组的时候，它首先在自己的所有邻居节点中选择一个距节点D最近的节点作为数据分组的下一跳，然后将数据分组传送给它。该过程一直重复，直到数据分组到达目的节点D或者一某个最佳主机(最佳主机的概念在后面详细讨论)。在发生最佳主机问题的时一候，数据分组采用边界转发策略来实现路由(边界转发留待后面详细介绍)。上一页下一页返回2.4地理位置信息的路由协议2.关键技术GPSR算法需要用到邻居节点的信息，因此需要维护邻居表。为了使网络中的所有节点获得邻居节点的地理位置信息，GPSR采用一种简单的信标发送(Beaconing)机制。该机制要求何个节点周期性地向所有邻居节点发送信标(Beacon)信号，该信标信号中包含了节点的标识和节点的位置信息，信标采用广播的方式，所有在该节点广播域中的节点都会收到该信标信号。上一页下一页返回2.4地理位置信息的路由协议GPSR路由算法使用了贪婪转发的机制，贪婪转发的最大缺点就是会导致局部优化问题，如图2-23所示。针对这种情祝，GPSR协议提出了边界转发(PerimetersForwarding)策略，该策略作为贪婪转发的一个补充。如图2-24所示，以D为圆心、D与X间距离为半径的圆与X的一跳传输范围发生重叠，且重叠区域(阴影区域)内没有X的邻居节点，称该重叠区域为X的空旷区域(void)。由于X在空旷域内找不到离D更近的邻居节点，因此它将尽力在空旷域的外部寻找转发节点以向D转发数据分组，X节点将沿着空旷域的边界才找到达D节点的路由。上一页下一页返回2.4地理位置信息的路由协议为了说明边界转发路由的原理和方法，需要先讨论两个问题:右手法则和平面图的构造问题。图2-25是右手法则的示例，当一个数据分组从节点Y到达节点x后，它经过的下一边是以x为顶点，沿(x,y)逆时针方向上的第一条链路，该图中为(x,z)，后续各边同样依此法则确定。使用边界转发的前提是要事先构造一个平面图来描述网络拓扑，平面图中任息两条边都不相交，GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边。对于网络中的所有节点，假设一跳通信范围的半径都为r，并且都位于同一平面内。如果节点n和m的距离d(n,m)<r，则认为n和m之间有一条边(n,m)。上一页下一页返回2.4地理位置信息的路由协议RNG(RelativeNeighhorhoodGraph)和GG(GahrielGraph)是两种常见的平面图。RNG算法的定义如下:RNG中的节点u,v之间存在边的条件是对于任意一个节点w,u到v的距离要小于或等于u到w或是v到w的距离的最大值。用式子表示为上一页下一页返回2.4地理位置信息的路由协议GG的定义如下:GG中的节点u,v之间存在边的条件是在以d(u,v)为直径的圆中没有其他节点。用式子表示为:完整的GPSR路由协议结合使用贪婪算法和边界转发算法来实现数据向目的节点的传播。网络中以贪婪转发为主，当贪婪算法找不到下一跳节点时，在平面图中使用边界转发算法决定下一跳，如图2-28所示。上一页下一页返回2.4地理位置信息的路由协议3.扩展分析GPSR是直接使用地理位置信息作为路由算法指导因素的一个例子，它的核心是使用地理位置信息，通过贪婪算法获得局部的最优解，同时采用边界转发机制来解决贪婪算法引起的最佳主机问题。在采用贪婪算法的时候，节点根据某一度量准则选择一个邻居节点作为数据分组的下一跳，GPSR选择离目的节点最近的邻居节点作为下一跳，如图2-29所示。

F为转发节点，D是目的节点，半径为R的圆是F的一跳最大传输范围，在GPSR方式下，F会选择A为下一跳节点。GPSR协议采用的这种方法称为MFR(MostForwardwithinRadius)，它的目标是使到达目的节点D的跳数最少。上一页下一页返回2.4地理位置信息的路由协议如果信号能量足够强，节点一跳传输范围的半径可以很大。半径越大，节点间相互干扰的可能性也就越大。针对这种情况，又提出了另外一种机制——NFP(NearestwithFor-wardProgress)。另外一种机制是CR(CompassRouting)，CR方法旨在缩小数据分组的传送范围。

GPSR协议有很多变种，最简单的是GRA(GeographicalRoutingAlgorithm)和GPSR唯一的不同就是，当出现局部优化问题时，GAR将启动路由发现机制(泛洪机制)搜索从最佳主机到目的节点的路由。当收到路由回复消息时，在路由表中保存该路由条目以减少将来可能发生的路由查找过程。上一页下一页返回2.4地理位置信息的路由协议GEDIR(GeographicDistanceRouting)也是GPSR路由协议的变种，GEDIR也采用贪婪算法，但是和GPSR有些不同。在GEDIR协议下，当中间节点收到数据分组时，首先比较它的各个邻居点到目的节点的距离，并且选择离目的节点最近的邻居节点作为下一跳。通过该方法选择的下一跳并不一定比当前节点距离目的节点更近。GEDIR协议也可能出现局部优化问题，一旦出现局部优化问题，GEDIR直接丢弃数据分组。当网络中出现局部优化的点比较多的时候，就会导致数据分组的大量丢失。上一页下一页返回2.4地理位置信息的路由协议2.4.4GEAR路由算法GEAR(GeographicandEnergyAwareRouting)路由算法，结合了DD和GPSR算法的思想，并且在选路时考虑了节点能量的因素。1.基本思想GEAR路由算法借鉴DD的思想，采用查询的方法来建立从Sink节点到事件区域的路由。和DD算法采用的泛洪方法不同，GEAR借鉴GPSR贪婪算法的思想，利用节点的地理位置信息以及节点能量剩余情况，建立查询消息到达目的区域的路径。当查询消息到达目标区域以后，查询消息采用一种迭代地理转发机制来发送。相关的检测数据沿着查询消息的反向路径汇集到Sink节点。上一页下一页返回2.4地理位置信息的路由协议GEAR路由算法需要保证链路的对称性，节点周期性地广播hello信息来告知邻居节点自己的位置和能量信息，同时进行链路对称性的一些检查和判断工作。2.关键技术GEAR算法需要解决两个问题:查询消息到事件区域的路径建立过程以及查询消息在事件区域内的传播过程。1)查询消息到事件区域的路径建立假设节点N需要将查询消息包P发送出去，P的目标区域为R,R的中心区域是D.N在为P选择下一跳的时候，除了要考虑将P尽量发送给离R最近的邻居节点外，还要考虑邻居节点的能量消耗的平衡性问题。GEAR中提出了实际代价(learnedcost)和估计代价(estimatedcost)的概念。上一页下一页返回2.4地理位置信息的路由协议每个节点M用h(M,R)表示自己到目标区域R的实际代价，当一个节点N不知道自己的邻居节点Ni的h(Ni,R)时，它计算估计代价c(Ni,R)作为h(Ni,R)的默认值，c(Ni,R)的计算方法如下:式中a是一个可变权值;d(Ni,R)表示节点Ni到区域R的中心D的距离;e(Ni)表示节点Ni消耗的能量。d(Ni,R)是使用一个最大长度进行归一化后的结果，这个最大长度选择节点N的所有邻居节点中到区域R最长的距离。同样的e(Ni)也是归一化后的结果，使用的标准是节点N所有邻居节点中单节点