自组织网络及其路由技术

1、自组织网络及其路由技术一、背景及概念1.发展历史无线通信网一般都是有中心的，要基于预设的网络基础架构才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有接入点（AP）和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。无线自组织网络即可以满足这样的应用。 自组织网络技术的研究始于 20 世纪 70 年代。美国 DARPA 出于军事需要，开始研究分组无线网（PRNET）在战场环境下数据通信中的应用。项目完成之后，DA

2、PRA 又在 1993 年启动了高残存性自适应网络项目。研究如何将 PRNET的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994 年， DARPA 又启动了全球移动信息系统项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991 年成立的 IEEE 802.11 标准委员会采用了“无线自组织网络”一词描述这种特殊的对等式无线移动网络。 美国福布斯杂志报道了加州大学洛杉矶分校的无线传感器网络的研究项目，指出通过无线传感器网络，我们将实实在在地掌握这个物理世界。2003

3、年美国商业周刊将无线传感器网络列为21世纪改变世界的10大技术之一。美国技术评论杂志评出对世界产生深远影响的十大新兴技术，无线传感器网络排名第一。另外，像 IEEE(ComPuter等众多杂志也都发表了一些关于无限传感器网络的论文。我国也非常重视无线传感器网络的研究，中国国家自然科学基金委员会在2003年已经开始对无线传感器网络的研究进行了资助，并于2004年将其列为重点项目。2005年我国开始传感网络标准化研究工作。2006年，国家973计划，国家863高技术计划等国家和省部级科技发展“十一五”规划也设专项资助该领域的理论、方法和关键技术研究。同年，我国政府将发展无线传感器网络列入未来15年

4、的国家中长期科学和技术发展规划纲要(2006一2020年)。2008年9月启动的国家16个重大专项中03专项设立7个方向，无线传感器网络为第6个一“短距离无线互联与传感器网络研发”。未来科学家预言无线传感器将引发新的信息革命，一些专家将传感器网络、塑料电子学和仿生人体器官并称为全球未来的三大高科技产业，它们将掀起新的产业浪潮。这些都预示着未来到处是以电池为能源的无线传感器网络，这些传感器可监控环境、机器甚至人类自己。在自组织网络中，节点具有报文转发能力，节点间的通信可能要经过多个中间节点的转发，即经过多跳，这是自组织网络与其它移动网络的最根本区别。节点通过分层的网络协议和分布式算法相互协调，实

5、现了网络的自动组织和运行。2. 自组织网络特点无线自组织网络具有无中心和自组织性。网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通过分布式算法来协调彼此的行为，无需人工干预和任何其它预置的网络设施，可以在任何时刻任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。所以与传统网络相比，无线自组织网络有以下特性：1. 自动配置：自动配置是无线自组织网络的一个特征，节点必须检测其它节点以及它们可以提供的服务。由于网络动态变化，自动配置过程需要确保网络能够正常工作，这涉及到连接 Internet 的网关节点的更换，簇头的更新等。在

6、网络形成阶段，节点可以就网络拓扑进行协商（星形、环形、点到点、点到多点、平面和分级），这依赖于网络的类型、底层的无线技术和应用的需求。 2 .多跳性:由于节点发射功率的限制，其通信范围有限。当它要与其通信范围之外的节点进行通信时，需要中间节点的转发。另外， Adhoc网络中的多跳是由普通节点协作完成的，而不需要专用的路由设备(如路由器)来完成。3.无中心和自组织性 :网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通过分布式算法来协调彼此的行为自组成网，无需人工干预和任何其它预置的网络设施。由于网络的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。4.动态拓

7、扑 :网络中，移动终端能够以较随意的速度和方式移动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、发送功率的变化、无线信道间的互相干扰、地形和天气等综合因素的影响，移动终端间通过无线信道形成的网络拓扑可能随时发生变化，而且变化的方式和趋势都难以预测。5.带宽的限制 :自组织网络采用无线传输技术作为底层通信手段，由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多。此外，同时无线自组织网络受限于无线传输带宽，由于采用无线传输技术作为底层通信手段，它所能提供的网络带宽相对有线信道要低得多。此外考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等多种因素，移动终

8、端得到的实际带宽远远小于理论上的最大带宽。6.移动终端的局限性 :自组织网络中的移动终端具有携带方便、轻便灵巧等好处，但是也存在固有缺陷，例如能量有限、内存较小、CPU性能较低等，从而给应用程序设计开发带来一定的难度，同时屏幕等外设较小，不利于开展功能较复杂的业务。7.存在单向信道 :自组织网络采用无线信道通信，由于地形环境或发射功率等因素影响，一对节点之间可能产生单向信道。8.安全性较差 :自组织网络是一种特殊的无线移动网络，由于采用无线信道、无中心、分布式控制和临时组织等技术，它更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。信道加密、抗干扰、用户认证和其它安全措施都需要

9、特别考虑。3.Ad-hoc网络AdHoc网络是目前讨论的最多的自组织网技术。这种网络不需要固定的基站设备和路由器，应此不依赖于蜂窝移动通信网络。网络中的节点可在一定区域内随意移动并能于网络中的任意站点相互通信。每一个节点都能实现路由器的功能而在网络中搜寻、维护到另一节点的路由。自组织网可用在事故的突发现场以及人们希望能迅速共享信息的会议、办公室等场所。AdHoc网络根据站点间的逻辑关系可以分为两种网络结构:平面网络结构、分级网络结构。如图1-1所示，左边的自组织网络是一个平面结构的网络，而右边的则是一个二级结构的自组织网络。平面结构中，所有节点地位平等，也被称为是对等式结构。与之相对的分级结构

10、中，网络被划分为多个簇(cluster)，每个簇由一个簇首(cluster一header)和多个簇成员(cluster一member)组成。这些簇首在逻辑上组成了一个高一级的网络，而在这个高一级的网络中又可以分簇，形成更高一级的网络，直至最高级。任意两个不在一个簇之内的簇成员之间的通信都要通过各自的簇首来中转。图1.1 平面结构VS分级结构平面结构的自组织网络结构简单，由于站点间是对等一的逻辑关系无需任何的结构维护过程。源节点和目的节点之间可以存在多条路径，当一条路径繁忙时，可能通过另一条路径继续通信。由于网络中所有节点是对等的，原则上不存在瓶颈，所以比较健壮。平面结构的最大缺点是网络规模受限

11、。在平面结构中，每一个节点都需要知道到达其它所有节点的路由。由于节点的移动性，维护这些动态变化的路由信息需要大量的控制消息。网络规模越大，路由维护的开销就越大。当网络的规模增加到某个程度时，所有的带宽都可能会被路由协议消耗掉。所以平面式结构网络的可扩展性较差。分级结构的最大优点则是可以有效控制路由信息量的膨胀，可以支持更大的网络的规模，必要的时候可以通过增加新的簇或者增加网络级数来提高整个网络的容量。分级结构中，簇内成员只需要维护簇内站点间的路由信息，与簇外站点的通信交给簇首处理。即简化了成员站点的功能，又使得簇内的网络管理信息量大大减少，节省了网络开销。簇内成员无须知道其他簇的拓扑结构，一个

12、簇的拓扑变化不会被其它簇的节点感知，这就大大减少了网络中路由信息对无线链路带宽的消耗。簇首的功能较为复杂一些，不仅需要维护到达其他簇的路由信息，还要知道所有节点与簇的关系。网络中主要的路由功能由簇首完成，大部分路由、管理信息在由簇首组成的高级网络中传播。一般情况下簇首只是网络中的少数站点，在同样规模网络的条件下分级结构的路由开销要比平面结构的小。如果簇内通信的信息流量在整个网络的通信量中占较大比例的时候，更能够明显提高整个网络的吞吐量。当然分级结构也有其缺点存在。首先维护不同层次结构间站点的逻辑关系较为复杂。簇首站点如果由事先指定，在站点移动情况下无法保证各个簇的规模相当;选举产生簇首的算法又

13、较为复杂，需要仔细设计。其次簇内的节点与簇外的节点进行通信时必须经过簇头，所得到的路由不一定是最佳路由。第三簇首的通信负担较重，容易成为网络中的通信瓶颈。从上面的比较可以看出，平面结构和分级结构的自组织网络各自具有不同的优势。平面结构的自组织网络结构简单，站点间的路由较为灵活，不容易出现网络瓶颈。但是，在网络规模较大时路由更新信息的负载较重造成通信容量的下降。平面结构更适合较小规模的网络。分级结构通过路由信息局部化减小路由控制报文的开销，提高了系统的吞吐量;通过增加新的簇分级结构可以支持更大的网络规模，有较好的可扩展性;另外分级结构可通过簇首的管理功能为网络提供用户接入控制和站点定位等辅助功能

14、。在AdHoc网络当中，无论采用平面结构还是分级结构有一点是共同的:所有站点共享一个物理信道。分级结构网络虽然能够限制簇内部的路由信息向其它簇扩散，但是分簇和分级都只是限于站点间逻辑关系而言，并不能隔离站点对物理信道的竞争。当网络中有站点数量越大，站点取得信道资源就越困难，出现信道冲突的可能性也相应增加。由于站点的通信距离限制，多数情况下AdHoc 。网络中存在多跳路径。多跳网络中隐藏终端的存在使得站点难以区分无线信道是空闲还是正被一个隐藏终端使用，物理信道冲突比有线以太网和单跳无线网络中更复杂。4.无线传感自组织网的应用无线自组织网络的许多优良特性为它在民用和军事通信领域占据一席之地提供了有

15、利的依据。首先，网络的自组织性提供了廉价而且快速部署网络的可能。其次，多跳和中间节点的转发特性可以在不降低网络覆盖范围的条件下减少每个终端的发射范围，从而降低设计天线和相关发射（接收）部件的难度，也降低了设备的功耗，从而为移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，自组织网络降低了信号冲突的几率，提高了信道利用率。从对使用者的保护来看，高功率的无线电波产生的电磁辐射对用户的身体健康也有影响。另外，网络的鲁棒性、抗毁性满足了某些特定应用需求。它的应用场合可以分为以下几类： 1.紧急场合：在发生了地震、水灾、强热带风暴或遭受其它灾难打击后，固定的通信网络设施（如有线通信网络、蜂窝

16、移动通信网络的基站等网络设施、卫星通信地球站以及微波接力站等）可能被全部摧毁或无法正常工作，对于抢险救灾来说，这时就需要无线自组织网络这种不依赖任何固定网络设施又能快速布设的自组织网络技术。类似地，处于边远或偏僻野外地区时，同样无法依赖固定或预设的网络设施进行通信。无线自组织网络技术的独立组网能力和自组织特点，是这些场合通信的最佳选择。2.军事应用：军事应用是无线自组织网络技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字化战场通信的首选技术。无线自组织网络技术已经成为美军战术互联网的核心技术。美军的近期数字电台和无线互联网控制器等主要通信装备都使用了自组织网

17、络技术。 3.个人通信：个人局域网是无线自组织网络技术的另一应用领域。不仅可用于实现 PDA、手机、手提电脑等个人电子通信设备之间的通信，还可用于个人局域网之间的多跳通信。 4.传感器网络：传感器网络是无线自组织网络技术的另一大应用领域。对于很多应用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因素，传感器的发射功率不可能很大。使用无线自组织网络实现多跳通信是非常实用的解决方法。分散在各处的传感器组成无线自组织网络，可以实现传感器之间和与控制中心之间的通信。这在爆炸残留物检测等领域具有非常广阔的应用前景。5.移动通信系统补充：无线自组织网络还可以与蜂窝移动通信系统相结合利用移动台

18、的多跳转发能力扩大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务、提高小区边缘的数据速率等。6.商业应用：组建家庭无线网络、无线数据网络、移动医疗监护系统和无线设备网络，开展移动和可携带计算以及无所不在的通信业务等。7.其它应用:考虑到Adhoc网络具有很多优良特性，它的应用领域还有很多，这需要我们进一步去挖掘。比如它可以用来扩展现有蜂窝移动通信系统的覆盖范围，实现地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助教学和构建未来的移动无线城域网和自组织广域网等。二、自组织网络的路由技术1.路由算法设计目标路由协议是ad-hoc网络的核心，是节点之间进行通信而采用的协议，主

19、要由路由算法实现。由于网络中节点的移动性，网络拓扑的结构可能发生改变，因此路由算法要能满足动态路由的要求。选择和设计一个高效的路由算法对于一个ad-hoc网络来说显得非常重要，路由算法的好坏直接影响到ad-hoc网络的性能。Ad-hoc路由算法设计的首要问题是要求简单、高效并且控制开销小。本章主要研究ad-hoc路由算法的设计。路由算法的任务是在节点和节点之间建立路由，实现可靠地数据传递，一个完整的路由算法应包括路由方式、路由发现和路由维护等内容。要设计一个好的路由算法通常有以下的一个或多个设计目标:1.简单、最优化、高效、低耗、控制开销小自组织无线传输带宽有限，传送控制开销不可避免地消耗掉一

20、部分带宽资源，因此路由算法首先应尽量简单可靠，并具有选择最佳路径的能力，这样有助于减少各种开销。另外路由算法也必须高效的提供其功能，尽可能减少软件和应用的开销。不能在节点保存太多的状态信息，节点间不能交换太多的路由信息。2.无环路、快速收敛路由算法必须能够保证不会产生路由环路，并且能快速收敛，收敛是所有路由器对最佳路径达成一致的过程。由于自组织网状网络是动态的，随时处于变化之中，会导致大量已有路由信息在短时间内作废，从而更容易产生路由环路。因此无环路的路由算法就显得尤为重要，另外，路由算法必须对拓扑的变化具有快速反应能力，在计算路由时能够快速收敛，及时获得有效的路由，避免出现目的节点不可达的情

21、况。3.健壮、稳定、灵活路由算法必须健壮，即在出现不正常或不可预见事件的情况下仍能正常处理，例如硬件故障、高负载和不正确的实现方法等。路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环境，例如，当发现网络中出现链路中断时，路由算法要迅速选择次佳的路径。2.网络的组成部分无线传感器网络是由大量节点以自组织形式构成的网络。在被监视区域内，节点被任意散落后，每个节点都可以收集数据，网络中节点通过自组织快速形成一个无线网络，它们之间相互协作进行数据收集，融合和传递。如图2.1所示，典型的无线传感器网络是由传感器节点、簇节点 (clusternode)、汇聚节点(也称为网关节点，sink节点)

22、、internet或卫星通讯网组成的。传感器节点既负责采集和发送信息，也可负责作为其它节点信息的路由传输点。首先，每个节点将自己收集的数据传送给自己传输范围内的簇节点(或可到达簇节点的路由节点)，各个簇节点通过多跳中继方式将监测数据传到sink节点，最终通过Internet或卫星通讯网传送到监控中心，最终实现任务管理节点(观察者)与传感器之间的通信。图2.1无线传感器网络是在移动Ad一Hoc网络的基础上发展起来的，在自组织和多跳通信等方面与移动Ad一Hoc网络在某些方面具有一定相似性。但无线传感器网络具有自己的特点以及局限性，主要表现在:(1)传感器节点体积小，成本低，这是无线传感器网络的一大

23、特点和标志。同时也应看到，正由于节点体积小，传感器节点的使用(包括电源和时间)是有限的。如图2.1所示，无线传感器网络的多跳中继通信，使得越靠近sink节点，节点承担的流量就越大，通信时间越长，能耗也越大。关键节点过早能量耗尽，即使其它节点能量充足，网络仍然会因为通信不畅而致使整个区域通信瘫痪。(2)不同于一般网络的下TCP/IP协议，无线传感器网络划分为物理层、数据链路层、网络层、传输层和应用层五层。其中，物理层进行比特流的传输;数据链路层主要负责节点的接入，降低节点间的传输冲突;网络层实现传感器与传感器、传感器与观察者之间的通信，支持多传感器协作完成大型感知任务;传输层提供差错控制和流量控

24、制;应用层由各种传感器网络应用软件系统构成，可以实现不同的应用目的。(3)无线传感器网络是动态自组织的。由于节点的有限性，无线传感器网络中时常有节点失效或新节点的补入，因此节点之间是不断以自组织方式构成新的传输路径，确保网络的畅通。3. 节点结构组成无线传感器网络的基本单位是无线传感器节点，它是构成无线传感器网络的基础平台，节点在网络中可以充当数据采集者、数据中转站或簇头节点 (cluster-head_node)等角色。主要用于完成采集信息、融合并传送数据的作用。它的重要特征就是低功耗、低成本和小体积。尽管在不同应用中，无线传感器网络的组成不尽相同，但一般是由传感单元(由传感器、模数转换功能

25、模块即A/D转换器组成)、处理单元(CPU、存储器和嵌入式操作系统等)、无线通信单元(无线收发电路)以及电源四部分组成。另外，在有些应用中还可包括电源自供电系统单元、定位系统单元等。如图2.2所示图2.2节点结构图一般而言，传感器节点的类型通常是由被监测物理信号的形式决定的。单元模块的功能大同小异。传感单元负责信号的采集和转换。该单元收集周围环境的数据(如温度、噪声等)，通过路由通信协议直接或间接的将数据传输给远方汇聚节点(Sink但其各部分湿度、压力、node);数据转换时，为了进行一些比较复杂的监测操作或需要监测不同数据信息(如温度、湿度、压力、噪声等)，一个传感器节点常常装备了多种传感器

26、。无线通信单元要接收邻居节点的数据，同时将其转发给距离簇节点更近的邻居节点或者直接转发给汇聚节点。经研究表明，节点无线通信单元的能量开销占节点总能耗的90%以上，因此降低能耗的关键是降低通信模块的能耗。节点的电源一般采用只能携带有限能量的电池来实现，一旦电源耗尽，节点就失去了工作能力。并且，若更换节点电池的成本会比重新布放节点的成本还要高，因此，决定了无线传感器在使用过程中不太可能更换电池，而节能则成为无线传感器网络的一大关注点。为了最大限度的节约电源，在硬件方面，要尽量改善器件耗能量，甚至在不需要传输数据时，可以切断射频部分电源;在软件方面，各层通信协议应该以节能为中心。节点通过各功能单元之

27、间的协作可以感受各种数据的变化。每个无线传感器节点作为一个简单的个体将传感器节点收集到的信息转化成为数字信号，进行编码，通过多跳的方式传送到汇聚节点(sink)，汇聚节点(sink)再连接到Internet，最后接入管理中心的电脑。这样人们就可以进行干预，遥控和管理。无线传感器网络节点在早期是一些复杂的物理化学装置，通过把物理量变成电信号，经过信号线接入计算机进行数据处理。随着无线传感器网络的研究成为热点，很多国家投入巨资进行该方面的研究。同时，也受益于微机电技术，计算机技术以及无线通信技术的等各项技术的发展，使得传感器节点的各个功能模块单元的体积越来越小，甚至可以集成到一块芯片中，现在传感器

28、的尺寸越来越小，可以组成一个尺寸小、功耗少、成本低的传感器节点。4. 路由算法技术和分类根据路由发现的驱动模式的不同，移动AdHoc网络的路由协议可分为表驱动(Table-driven)和按需(on-demand)路由协议，这种划分方法是目前国内外学术界对移动AdHoc网络的路由协议的主流的划分方法。表驱动路由协议又称为先验式路由协议。在这种路由协议中，网络中的每个节点都会维护一张路由表，路由表中包含着到达网络中其它节点的路由信息。当源节点要向某个目的节点发送数据包时，则可以立即从路由表中获得路由。如果节点检测到网络的拓扑结构发生变化，节点将在网络中发送更新消息；而收到更新消息的节点将相应地更

29、新自己的路由表，以维护一致的、及时的、准确的路由信息。所以路由表可以准确地反映网络的拓扑结构，因此这种路由协议的时延较小；但是由于需要及时的更新路由信息，路由协议的开销较大。典型的表驱型路由协议有DSDV、CGSR、FSR、WRP、DBF，GSR、HSR、ZHLS等。(1)DSDVDSDV(Destination-Sequenced Distance Vector)路由协议是一种无环路距离向量路由协议，它是根据传统的路由选择算法改良而发展出来的。在协议中，每个移动节点都需要维护一个路由表，路由表的表项包括目的节点、跳数、下一跳节点和目的节点号。其中目的节点号由目的节点分配，主要用于判别路由是否

30、过时，并可防止路由环路的产生。每个节点必须周期性的与邻居节点交换路由信息，这种交换可以分为时间驱动和事件驱动两种类型。在节点发送分组时，将添加一个序号到分组中，节点从邻居节点收到新的信息，只使用序列号最高的记录信息，如果两个路由具有相同的序列号，那么将选择最优的路由(如跳数最小)。DSDV路由表更新采用触发的方式来更新网络链路。为减少路由分组的长度，使用两种更新方式：一种是全部更新，即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况，另一种方式是部分更新，更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。DSDV协议的主要优点是消除了路由环路，加快了收敛速度，同时减少了

31、控制信息的开销，但是它的不足在于难以适应速度变化快的移动AdHoc网络。（2）CGSRCGSR(Clusterhead Gateway Switch Routing)使用了层次结构路由，指定了簇首节点和网关节点，其中簇首节点用来控制一组节点和网关节点，网关节点是两个簇之间的节点。当一个节点要发送分组时，这个分组首先到达该发送节点的簇首节点，然后簇首节点把这个分组通过网关节点转发给另一个簇首节点，不断重复这个过程直到分组到达目的节点。因此，每个节点都必须有其簇成员的路由表。CSGR利用DSDV作为其底层路由选择机制，并针对分级网络做了适当的改进，寻路是通过簇首节点和网关节点完成的，簇内路由方式为

32、成员节点-簇首节点-成员节点方式，簇间路由方式采用成员节点-簇首-网关-簇首-成员节点方式。（3）WRPWRP(wireless routing protocol)协议是另一种表驱动路由协议，在网络的节点中保存路由信息。每个节点保存在路由表中的信息如下：距离、路由、链路开销和重传消息的列表(MRL)。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的更新列表等信息，这就使得节点可以决定何时发送更新消息以及发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节点。然后邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。WRP的优点就是当

33、一个节点试图执行路径计划算法时，可以通过目的节点的上游节点所保存的信息和邻节点所保存的信息来限制算法，使得算法收敛得更快并避免路由当中的环路。由于WRP需要保存4个路由表，所以比大多数的协议需要更大的内存。此外，WRP还依赖于周期性的HELLO消息，这也要占用带宽。按需路由协议又称为反应式路由协议，是一种当节点需要发送数据包时才查找路由的路由算法。在这种路由协议中，网络中的节点不需要维护及时准确的路由信息，只有当向目的节点发送数据包时，源节点才在网络中发起路由发现过程，寻找相应的路由。与先验式路由协议相比，反应式路由协议的开销比较小，但是由于发包时要进行路由发现过程，数据报传送的时延较大。典型

34、的按需驱动路由协议有DSR、AODV、TORA、ABR等。（1）DSRDSR(Dynamic Source Routing)是一种基于源路由的按需驱动路由协议，它使用源路由算法而不是按逐跳路由的方法。网络中每一个节点都需要维护一个已知的路由表，并且当发现新的路由时就更新该路由表。每一个数据包的包头都包含该数据包从源节点到目的节点路由所经过的中间节点序列信息，故称为源路由算法。DSR主要包括两个过程：路由发现和路由维护。当节点S向节点D发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程。DSR协议的优点在于节点不需要周期性地发送路由广

35、播分组，仅需要维护与之通信节点的路由，协议开销较小，节省了能量和网络带宽；使用路由缓存技术，减少了路由发现的耗费，一次路由发现过程可能会产生多条到目的节点的路由，将有助于路由选择，能完全消除路由环路。DSR协议的缺点在于由于每个数据包的头部都需要携带路由信息，数据包的额外开销较大；路由请求消息采用泛洪方式，相邻节点路由请求消息可能发生传播冲突并可能会产生重复广播。由于使用缓存路由，过期路由会影响路由选择的准确性。(2)AODVAODV(On-Demand Distance Vector Routing)协议是一个建立在DSR和DSDV上的按需路由协议，借用了DSR中路由发现和维护的基础，采用D

36、SDV逐跳路由，顺序编号和路由维护阶段的周期更新机制。在协议中，当中间节点收到一个路由请求分组后，它能够通过反向学习来取得源节点的路径，目的节点最终收到这个路由请求分组后，可以根据这个路径恢复这个路由请求，在源节点和目的节点间建立了一条全双工路径。AODV协议的特点在于它采用逐跳转发分组方式，同时加入了组播路由协议扩展。其主要缺点是依赖对称式的链路，不支持非对称链路。(3)TORATORA(Temporally Ordered Routing Algorithm)协议是在有向无环图算法(DirectedAcyclic Graphic)的基础上，结合反向链路算法提出来的自适应的分布式路由算法，主

37、要用于高动态的多跳无线网络。TORA协议能够按需快速地发现多个路由，尽管这些路由不一定是最优的，但是TORA协议能够保证这些路由是无环的。TORA的主要特点是当拓扑结构发生改变时，控制消息只在拓扑发生变化的局部范围传播，节点只需要维护相邻节点的路由信息。TORA协议的优点在于可以处理高密度的网络，具有很好的分布性。但是TORA协议是基于同步时钟的，时钟的不同可以导致路由的故障，并且当多个节点同时进行选路和删除路由时会产生路由振荡现象。3、 一些经典的路由算法1. 平面路由协议（1）泛洪协议Flooding协议即洪泛协议，节点以洪泛广播方式发送自身采集的消息或者收到的消息包，这些消息包会在网络中

38、不断进行洪泛广播直至到达目的节点。其优点在于实现简单，不需要维护复杂的网络拓扑信息，但缺点也显而易见，盲目利用计算和通信资源，不适合传感器网络实际的应用需要。Gossiping协议是对Flooding协议的改进，在Gossiping协议中，节点将自身采集的信息和自己收到的数据消息，转发给随机选择的下一跳节点，该协议很大程度上降低了洪泛协议的开销，但是增加了网络时延，且扩展性较差。 图3.3 信息爆炸优点：实现简单，不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源；适用于健壮性要求高的场合。不足：存在信息爆炸(Implosion)问题，即出现一个节点可能得到一个数据多个副本的现象，

39、如图3-1所示。出现部分重叠(Overlap)现象，如果处于同一观测环境的两个相邻同类传感器节点同时对一个事件做出反应，二者采集的数据性质相同，数值相近，那么，这两个节点的邻居节点将收到双份数据副本。盲目使用资源，即扩散法不考虑各节点数量可用状况因而无法做出相应的自适应路由选择。（2）定向扩散该协议是一种以数据为中心的平面结构协议，且能够同时承载多个应用。DD协议的最大特点是首次提出了网络梯度的概念，并与数据融合算法相结合，能够用较小的成本完成数据搜索的功能。定向扩散算法的主要思想是对网络中的数据用一组属性对来命名，并基于数据进行通信。其突出特点是引入了梯度来描述网络中间节点在某方向继续搜索以

40、获得匹配数据的可能性。为建立路由，汇聚节点(Sink节点)向所有传感器节点发送查询请求兴趣信息(Interest)，兴趣信息Interest包括属性列表、上报间隔、持续时间、地理区域等信息。沿途节点按需对各兴趣信息Interest进行缓存与合并，并根据兴趣信息Interest设计、创建包含数据上报率、下一跳等信息的梯度(gradient)，从而建立多条指向Sink节点的路径。兴趣信息Interest中的地理区域内节点则按要求启动监测任务，并周期性地上报数据。源节点采集的数据首先在本地采用汇聚融合技术进行整合，然后在传感器网络中传输。Sink节点可在数据传输过程中通过对某条路径发送上报间隔更小或

41、更大的兴趣信息Interest，以增强或减弱数据上报率。该协议采用邻节点间通信方式来避免维护全局拓扑，并采用查询驱动数据传送模式和局部数据聚集来减少网络数据流，因而是一种高能效的协议。它的缺点是在需要连续传送数据的应用中(如环境监测等)不能很好的应用，其数据命名只能针对于特定的应用预先进行，同时初始查询的扩散开销也较大。图3一2表示了定向扩散协议的路由建立过程。DD协议是以数据为中心的路由协议，所有通信都局限在邻居节点之间，每个节点都具有收集数据，进行数据聚集和缓存数据的功能，这种特性减少了网络数据流也降低了数据传输延迟。DD协议路径创建灵活，且路径恢复的局部算法设计使得系统对于网络的动态拓扑

42、具有更强的适应性。按需驱动数据的传送模式和不需要维护全局网络拓扑结构，使得DD协议成为一种高能源有效性的协议。图3.2 定向扩散（3）SARSAR(Sequential Assignment Routing)协议算法创建多颗树，每颗树的树根都是Sink的一跳邻居。在算法的初始阶段，树从根节点开始，不断吸收新的节点加入。在树延伸的过程中，将避免那些QoS不好及能量已经消耗较多的节点。初始阶段结束后，大多数节点都加入了某个树，各节点只需要知道自己的上一跳邻居，以转发报文。在网络工作过程中，一些树可能由于中间节点能量耗尽而断开，也可能有新的节点加入网络而使网络拓扑结构发生变化。所以网关周期性的发起“

43、重新建立路径”的命令，以保证网络的连通性和最优的服务质量。 （4）SPINSPIN(Sensor Protocol for Information via Negotiation)是一种以数据为中心的自适应通信路由协议，通过使用节点间的协商机制和资源自适应机制来解决扩散法存在的不足。为了避免出现扩散法的信息爆炸问题和部分重叠现象，传感器节点在传送数据之前彼此进行协商，协商制度可以确保传输有用数据。节点间通过发送元数据，即描述传感器节点采集的数据属性的数据，而不是采集的整个数据进行协商。由于元数据大小小于采集的数据，所以，传输元数据消耗的能量相对较少。为避免盲目使用资源，所有传感器节点必须监控各

44、自的能量变化情况。在传输或接收数据之前，每个节点都必须检查各自可用的能量状况，如果处于低能量水平，必须中止一些操作，比如充当数据中转站(路由器)角色的一些数据转发操作。SPIN有三种数据包类型，即ADV、REQ和DATA。ADV用于新数据广播。当一个节点有数据可共享时，它可用ADV数据包(包含元数据)对外广播。REQ用于请求发送数据。当一个节点希望接收DATA数据包时，发送REQ数据包。DATA包含附上元数据头(Meta-Data Header)的传感器采集的数据的数据包。在发送一个DATA数据包之前，一个传感器节点首先对外广播ADV数据包；如果一个邻居节点在收到ADV后有意愿接收该DATA数

45、据包，那么它向该节点发送一个REQ数据包，接着节点向该邻居节点发送DATA数据包。类似地进行下去，DATA数据包可被传输到远方汇聚节点或基站。图3-4表示了SPIN协议的工作过程。图3.4 spin工作流程2. 分层路由协议（1） LEACH低功耗自适应聚类路由算法Leach(low energy adaptive clustering hierarchy)是在无线传感器网络中提出的第一个层次型路由协议，是分簇式路由协议的代表，具有典型的研究价值。其后的大部分分簇式路由协议都是在它的基础上发展而来的。与一般的平面多跳路由协议和静态聚类算法相比，Leach可以将网络生命周期延长15%，主要是通过

46、随机选择簇首节点，平均分担中继通信业务来实现。Leach定义了“轮”(round)的概念，并以“轮”为单位周期性工作。每一轮由初始化和稳定工作两个阶段组成，为了使能耗最小化、降低初始化开销，稳定工作阶段持续的时间比初始化阶段长。初始化阶段，网络随机选择簇首，然后动态成簇；稳定工作阶段，节点将采集到的数据传送至簇首，簇首经过融合处理之后，发送到sink节点。持续工作一段时间以后，整个网络进入下一轮工作周期，重新选择簇首。1、 初始化阶段在初始化阶段，随机选择节点作为簇首节点，随机性可以确保簇首的高能耗均匀地分摊到所有传感器节点上；然后，成为簇首的节点向网络广播信息，其它节点根据接收到各簇首广播信

47、息的强度来选择所要加入的簇，并告知相应的簇首节点。1、簇首选举办法：节点产生一个0-1之间的随机数，若当前轮中这个数值小于设定的阀值T(n)，则该节点成为簇首节点。T(n)值按如下公式计算：以1/p为轮数周期，在每个轮数周期中，每个节点都会当选为一次簇首。其中，p=k/N为期望的簇首节点数量在所有传感器节点中的百分比，其中k为网络中每轮需要产生的簇首数量；N为网络中传感器节点的总数；r为当前轮数；G为当前轮数周期中，在剩余轮中未成为簇首节点的传感器节点组成的集合。在第0轮，即r=0时，每一个节点将会以相同的概率p成为簇首。经过(1/p)-1轮后，T(n)的值变为1，这时还没有担当过簇首的那些节

48、点就被选择为簇首。在经过1/p轮后，所有的节点再次以开始平等的竞选簇首。2、成簇节点当选簇首以后，便将当选的消息向网络广播。非簇首节点再根据接收到的各簇首节点广播消息的强度，选择接收强度最大的节点为自己的簇首，并告知相应簇首。当簇首接收到所有的加入信息后，会产生一个TDMA定时控制消息，并且通知该簇中所有节点，簇内节点收到这个广播消息后，在稳定工作阶段就会在各自的时间槽内向簇首节点发送数据。Leach协议WSN节点成簇后，各簇分布如图3.5所示：4.5 Leach 协议族分簇该图所示网络覆盖区域被划分成5个簇，图中黑色节点代表簇首，白色节点为非簇首成员节点。二、稳定工作阶段在稳定工作阶段，传感

49、器节点持续采集监测数据，并按各自TDMA分配的时隙向簇首发送，在簇首对数据进行必要的融合等处理之后，发送至网关。稳定工作阶段持续给定时间（远长于初始化阶段）后,网络进入下一轮工作周期,重新选择簇首。三、相关的Leach改进算法Leach算法假设网络中所有的节点都能直接与簇首节点和终端节点通信，数据传输采用单跳路径模式，因此不适用于监测范围较大的网络；另外，对于节点数量较多、节点密度较大的网络，部分簇首节点会因为簇内数据量较多、能耗过大而较先死亡。可见Leach算法具有较多的局限性。在Leach算法基础之上，研究人员陆续提出了一些较好的改进算法。Leach-C算法，采用集中式簇首选择机制，该算法根据网络全局信息包括节点地理位置、当前能量等，从网络中选取K个最优节点充当簇首，簇首选择更加合理，但属于典型的NP-hard问题,时间复杂度较大。Heed协议针对Leach算法簇首分布不均匀问题进行了改进。协议中以簇内平均可达能量AMRP(average minimum reachability power)作为衡量簇内通信成本的标准。节点以不同的初始概率CHprob发送竞争消息。初始化概率CHpro