无线自组网的学习总结

精品文档无线自组织网的路由协议性能分析1. 什么是自组织混沌系统在随机识别时形成耗散结构（什么是耗散结构？系统在远离平衡态条件下, 通过与外界进行交换及组分间非线性关系所形成的一种新型有序组织结构。）的过程被定义为自组织。如果一个系统靠外部指令而形成组织，就是他组织；如果不存在外部指令，系统按照相互默契的某种规则，各尽其责而又协调地自动地形成有序结构，就是自组织。2. 什么是无线自组织网无线自组织网络即MANET(Mobile Ad Hoc Network)，是一种不同于传统无线通信网络的技术。传统的无线蜂窝通信网络，需要固定的网络设备如基地站的支持，进行数据的转发和用户服务控制。而无线自组织网络不需要固定设备支持，各节点即用户终端自行组网，通信时，由其他用户节点进行数据的转发。这种网络形式突破了传统无线蜂窝网络的地理局限性，能够更加快速、便捷、高效地部署，适合于一些紧急场合的通信需要，如战场的单兵通信系统。但无线自组织网络也存在网络带宽受限、对实时性业务支持较差、安全性不高的弊端。目前，国内外有大量研究人员进行此项目研究。 无线自组织网络(mobile ad-hoc network)是一个由几十到上百个节点组成的、采用无线通信方式的、动态组网的多跳的移动性对等网络。其目的是通过动态路由和移动管理技术传输具有服务质量要求的多媒体信息流。通常节点具有持续的能量供给。3. 自组织网的无线路由协议路由器提供了异构网互联的机制，实现将一个网络的数据包发送到另一个网络。而路由就是指导IP数据包发送的路径信息。路由协议就是在路由指导IP数据包发送过程中事先约定好的规定和标准。路由协议通过在路由器之间共享路由信息来支持可路由协议。路由信息在相邻路由器之间传递，确保所有路由器知道到其它路由器的路径。总之，路由协议创建了路由表，描述了网络拓扑结构；路由协议与路由器协同工作，执行路由选择和数据包转发功能。3.1主动路由主动路由的路由发现策略与传统路由协议相似主动路由的路由发现策略与传统路由协议类似，节点通过周期性地广播路由信息分组，交换路由信息，主动发现路由。同时，节点必须维护去往全网所有节点的路由。它的优点是当节点需要发送数据分组时，只要去往目的节点的路由存在，所需的延时很小。缺点是主动路由需要花费较大开销，尽可能使得路由更新能够紧随当前拓扑结构的变化。然而，动态变化的拓扑结构可能使得这些路由更新变成过时信息，路由协议始终处于不收敛状态。在自组网路由协议的研究初期，主要思路是修改有线网络的路由协议以适应在自组网环境中运行。这些路由协议大多属于主动路由。在下面的各种主动路由协议的过程描述中，将着重说明如何对传统路由协议的改进以适应自组网环境中运行。3.1.1 DSDV DSV(destination-sequenced distance-vector)协议是在DVA基础上进行改进设计的。它被认为是最早的自组网路由协议。DSDV的特点是采用了序列号机制用于区分路由的新旧程度，防止DVA可能产生的路由环路。它的缺点是不适应变化速度快的自组网，不支持单向信道。3.1.2 WRP WRP(wireless routing protocol)协议是在路径发现算法PEA(path finding algorithm)基础上改进设计的。PEA与DVA不同，它利用去往目标节点的路径长度和相应路径的倒数第二跳节点信息加速路由协议收敛速度，改善DVA中路由环路问题。WRP对PFA的改进之处在于当节点i监测到与邻居节点j的链路发生变化时，i会检查所有邻居节点关于倒数第二跳节点信息的一致性，而PFA只会检查节点j关于倒数第二跳节点信息的一致性。这种方式可以进一步地减少出现路由环路的次数，加快算法的收敛速度。3.2.3 STARA STARA(system and traffic dependent adaptive routing algorithm)协议采用最短路径算法计算路径，但“最短”路由度量采用了平均延时时间，而不是常用的跳数，也就是说STARA在进行分组路由时，考虑了无线链路的容量和排队延时等因素。每个节点i采用改进的端到端确认协议为每一对源和目的节点(i，d)计算平均延时D(t)，方法如式3-1所示。其中, 0,1，为遗忘因子，用于调整历史延迟值和当前延迟值的权重关系: kN，N表示节点i一跳可以到达的所有邻居节点的集合。然后根据式3-2所示，将经过的交通流量分配给不同的邻居节点，目标是使得所有可用的路径具有相同的延时。需要特别指出的是，这种路径平均延时估测机制并不需要双向信道和节点间的时钟同步的支持。 Ddik（t）=1(1-)iD(t-l) 3-1 Pdik(t)=Pdik(t-1)+a(t)(Did(t)-Ddik(t) 3-23.2按需路由与主动路由相反，按需路由认为在动态变化的自组网环境中，没有必要维护去往其他所有节点的路由。它仅在没有去往目的节点路由的时候才“按需”进行路由发现。因此，拓扑结构和路由表内容是按需建立的，它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现引起的延时。按需路由协议通常由路由发现和维护两个过程组成。当源节点发现没有去往目的节点的路由时，触发路由发现过程。这个过程类似于有线网络中建立电路连接的协商过程。 图一 按需请求示例 图一是一个典型的路由请求过程。源节点A在自组网中广播路由请求分组，邻居节点B和F收到路由请求分组后，记录分组经过了该节点，然后继续转发，直到到达了目的节点E。节点E将会收到来自两条不同路径的路由请求分组，每个路由请求分组中包含有相应的路径信息。节点E根据一定的选择原则选取一条从源节点到目标最优路径，并将该信息附在向源节点A发送的路由回答分组中，作为对路由请求的响应。源节点A根据收到的路由回答分组更新路由信息，从而获得去往目的节点E的路由。当拓扑结构发生变化时，通过路由维护过程删除失效路由，重新发起路由请求过程。路由维护通常依靠底层提供的链路失效检测机制进行触发。3.3.1 DSRDSR(dynamic source routing)协议是最早采用按需路由思想的路由协议。它包括路由发现和维护两个过程，协议操作与上节描述的过程基本一样。它的主要特点是使用了源路由机制进行分组转发。这种机制最初是IEE802.5协议用于在网桥互连的多个令牌环网中节点寻找路由。DSR协议借鉴了这种机制，并加入了按需思想而形成。SR的优点是中间节点不用维护去往全网所有节点的路由信息，而且可以避免出现路由环路。它的缺点是每个数据分组都携带了路径信息，造成协议开销较大。而且也不适合网络直径大的自组网，网络可扩展性不强。3.3.2 AODVAODV(ad hoc on demand distance vector)协议是在DSDV协议基础上结合类似DSR中的按需路由机制进行改进后提出的。不同之处在于AODV采用了逐跳转发分组方式，而DSR是源路由方式。因此，AODV在每个中间节点隐式保存了路由请求和回答的结果，而DSR将结果显式保存在路由请求和路由回答分组中。此外，AODV的另一个显著特点是它加入了组播路由协议扩展，并支持QOS。它的缺点是不支持单向信道，原因是AODV协议基于双向信道的假设工作，路由回答分组直接沿着路由请求的反方向回到源节点。3.3.3 TORATORA(temporally-ordered routing algorithm)协议是在有向无环图DAG(directed acyelicgraphic)算法的基础上提出的一种按需路由协议。它分为路由发现、路由维护和路由消除三个过程。TORA的路由发现与其他按 需路由协议一样，首先在网中扩散路由请求分组。但在路由回答中，采纳了DAG算法。其主要思想是:将每个节点分配一个相对于源节点的“高度值”，其中目的节点的“高度值”最低，并根据相邻节点之间的“高度值”的比较从而形成一条或多条的有向路径，方向是从“高度值”大的节点指向小的节点。从图论的角度来看，即为一棵根为目的节点的有向无环图。算法的具体实现是通过路由回答分组(在TORA协议中正式名称为更新分组)在回到源节点的过程中完成的。为了在拓扑结构发生变化时能够迅速重新生成路由，并将产生的协议分组限制只在受到影响的节点中扩散，TORA协议仍然采用上述算法重新构造失效的DAG。TORA协议的缺点主要有:一是协议的有效运行依赖于网络的高连通度提供路由维护所需的多条备选路径;二是TORA协议需要依靠IMEP(Intemet manet encapsulation protocol)协议提供邻居节点信息和底层可靠有序传输等功能，CMU Monarch小组的仿真研究结果表明TORA协议开销比其他按需路由协议大的主要原因在于使用了IMEP协议;三是它也不支持单向信道。3.3.4 LARLAR(location aided routing)协议是一个基于预测节点当前位置算法的按需路由协议。它的目标是如何有效提高路由请求的效率，限制路由请求过程中被影响的节点数目。类似的思想也已出现在移动蜂窝电话系统中选呼机制(selective paging)中。LAR假设节点采用GPS系统获得位置信息，且每个节点都知道其他节点的平均运动速度。路由请求时，源节点根据目的节点历史位置和移动速度指定一个地理区域:请求范围，并将此信息附在路由请求分组中。LAR规定只有位于请求范围内的中间节点才允许进行路由请求分组的转发操作，从而减少了路由请求的影响范围。当路由请求失败时，源节点将扩大请求范围，重新进行路由请求。LAR的缺点是它必须依靠GPS系统才能正常工作，限制了其应用范围。3.3.5 ABRABR(Associativity Based Routing )协议是一种由源节点发起的按需路由协议，由以下3个阶段组成：路由建立阶段、路由重建阶段和路由删除阶段。路由建立是基于洪泛的，源节点广播路径查询（BQ）分组，收到BQ分组的节点建立一条到源节点的路由，并在BQ分组中添加自己的ID和“稳定性信息”，然后继续广播BQ分组。为了获得整条路由上的信息，不允许中间节点回复路由应答分组。当目的节点收到第一个associativity值最高的路由，以收到沿其它路径到达的BQ分组的副本，然后选择一个associativity值改变，则启动路由重建，受限节点试图从局部进行路由修复，如果不成功，向上游节点发送RN（Route Notification）消息，在最坏的情况下，源节点收到RN消息后，启动一个新的路由建立过程。当源节点不再需要路由时，它将启动路由删除过程。路由删除有两种方法：（1） 通过洪泛RD（Route Delete)分组完成；（2） 超时则自动删除路由条目。4. 集群路由路由协议的设计思想和网络逻辑结构密切相关。从网络逻辑视图这个角度，路由协议又可以分为平面结构和集群结构两种。平面路由协议中，逻辑视图是平面结构，节点的地位是平等的。优点是不存在特殊节点，路由协议的鲁棒性较好，交通流量平均地分散在网络中。路由协议没有节点移动性管理任务。缺点是缺乏可扩展性，限制了网络的规模。集群路由协议中，网络由多个集群组成，节点分为两种类型:普通和群首节点。处于同一集群的群首节点和普通节点共同维护所在集群内部的路由信息，群首节点负责所管辖集群的拓扑信息的压缩和摘要处理，并与其他群首节点交换处理过后的拓扑信息。层次结构就是一种典型的集群方式。采用集群路由主要有两个目的。一是通过减少参与路由计算的节点数目，减小路由表尺寸，降低交换路由信息所需的通信开销和维护路由表所需的内存开销，这与有线网络中层次思想的目标是一致的。二是基于某种集群形成策略、选举产生一个较为稳定的子网络，减少拓扑结构变化对路由协议带来的影响。集群路由的优点是适合大规模的自组网环境，可扩展性较好。缺点是群首节点的可靠性和稳定性对全网性能影响较大，并且为支持节点在不同集群之间漫游所进行的移动管理将产生一定的协议开销。已提出的自组网路由协议大多数是基于平面路由思想，比如3.1和3.2节所描述的路由协议。其主要原因是，自组网目前主要以一种末端网络形式存在，应用规模都较小，使用集群思想的作用不明显。这在一定程度上抑制了集群思想在自组网中的研究。3.4.1 CGSRCGSR ( cluster head gateway switch routing )协议是在DSDV 协议基础上结合集群路由机制设计的。CGSR采用LCC ( least cluster change ) 算法形成集群结构。为了尽量避免群首节点频繁更替，保障群首节点身份的稳定性，LCC规定:只在两个群首节点相互靠近或一个节点离开所有群首节点的通信范围的两种情况下才会发生群首节点身份的变化。除了群首节点外，CGSR还规定了其他两种类型的节点。一个群首的内部节点是指位于该群首的无线通信范围内的节点。网关节点则是指同时位于多个群首的无线通信范围之内的节点。当节点移动导致集群结构被破坏时，CGSR通过集群维护算法重新构造集群结构。在这个过程中，一些节点会从当前集群转移到邻居集群。为了尽量减少转移节点的个数，它将具有最多邻居数的节点和它的邻居保留在当前集群中。节点维护两种数据结构:集群成员表和路由表，前者描述了每个目标节点所在集群的群首。节点使用DSDV协议周期性地与邻居节点交换集群成员表，更新表项内容。当节点需要发送一个分组时，首先在集群成员表中查找距离目的节点最近的群首，然后根据路由表查找去往此群首的下一跳节点。3.4.2 CEDAR CEDAR (core extraction distributed ad hoc routing) 协议目标是在自组网环境中构建一个稳定的虚拟核心结构用于可靠有效地扩散路由信息。为了降低虚拟核心的变化程度，有必要使得加入核心的节点数目尽量的少。图论中的最小覆盖算法MCDS(minimum connected dominating sets) 可以满足这个要求。但是可以证明MCDS算法是一个N-P完全问题，只能基于确定性图灵机模型采用多项式时间近似算法得到。CEDAR采用MCDS近似算法将网络分为不同的域，每个域中仅包含一个属于MCDS的主域节点，其他节点都是主域节点的邻居节点且不在MCDS中。主域节点收集网络路由信息，在MCDS中扩散，从而计算各个节点间的最短路由。采用MCDS的优点是当连接非主域节点之间的链路失效时，MCDS可以立即充当备份路由的作用。此外MCDS这种结构有利于支持广播和组播功能。缺点是随着网络规模增大，路由更新带来的协议开销急剧增加，可扩展性不好。3.4.3 ZRPZRP (zone routing protocol) 是第一个利用集群结构混合使用按需和主动路由策略的自组网路由协议。ZRP中，集群被称作域(zone)。域形成算法较为简单，它是通过一个重要的协议参数一区域半径(以跳数为单位)，指定每个节点维护的区域大小，即所有距离不超过区域半径的节点都属于该区域。一个节点可能同时从属于多个区域。为了综合利用按需路由和主动路由的各自优点，ZRP规定每个节点采用DVA主动路由协议维护去往区域内节点的路由，采用类似DSR协议中的按需路由机制寻找去往区域外节点的路由。ZRP协议的性能很大程度上由区域半径参数值决定。通常，小的区域半径适合在移动速度较快的节点组成的密集网络中使用;大的区域半径适合在移动速度慢的节点组成的稀疏网络中使用。目前ZRP采用预置固定区域半径值的做法，这无疑限制了它的可适应性。3.5 多播路由协议多播（Multicast）,又称组播，是一种一点到多点或多点到多点的通信方式，即多个接收者同时接收一个源发送的相同信息。支持多播的路由协议称为多播路由协议。自足网多播路由协议的核心是管理多播组的成员，动态生成和维护一个多播传输结构（Multicast Delivery Structure）,建立多播数据的传播路由。根据多播传输结构拓扑结构的不同，自组网多播路由协议主要分为两类：基于树的多播路由协议和基于网的多播路由协议。 基于树的多播路由协议 多播树是连接所有多播组成员的最小化生成树。自组网基于树的多播路由协议有两类:一种是多播组成员共享一颗多播树，另一种是基于源节点的书，每个源节点都有一颗以自己为跟的多播树，该树连接多播组中所有成员节点。 基于网的多播路由协议 基于网的多播路由协议（如ODMRP、CAMP等）在自足网多播路由协议中占了很大比重，在该类协议下，多播组的成员节点之间形成一种网状结构，节点之间有冗余的路径。 两类多播路由协议的比较 基于树的多播路由协议的抓药有点是效率高，但受到自组网拓扑结构动态变化的应小南瓜，树的结构很容易被破坏，需要不断根据网络的变化对树进行重构，维护树结构的开销较大，协议的简装行不佳。相反，基于网的多播路由协议健壮性好，不需因为少量链路的实效而重新配置多播网结构，但网状结构增加了转发和网络的负担。下面介绍几种自组网典型的多播路由协议1.ODMRP(On-Demand Multicast Routing Protocol) 是一种按需的自组网网多播路由协议，由多播数据的发送这按需发起建立多播路由。通过建立一个连接多播数据发送者和接受这的多播结构，来进行多播数据分组的转发。ODMRP是一种基于多播网的自组网多播路由协议，其核心是由多播发送节点用软状态的方法，按需建立和维护一个多播数据的转发组，节点加入或离开多播组不需发送额外的控制信息，且协议运行不需要依赖一个多播数据的转发组。该协议比较简单、健壮性好，不足之处是当多播组中的发送节点数量很多的情况下，控制消息的洪泛会造成过多的信道开销。2. MAODV（Multicast Ad hoc On-Demand Distance Vector Routing Protocol）协议是在单播AODV路由协议的基础上设计的按需多播路由协议。在该协议中，当一个节点欲加入某个多播接收数据或向某个多播组发送数据时，需要发起建立多播路由的过程。多播路由的建立仍使用单播ADOV路由协议中的RREQ和RREP消息，另外还添加了一个MACT消息，用于对多播树结构，来进行多播数据的传输。3. CAMP(Core_Assisted Mesh Protocol) 是一种基于多播网的自组网多播路由协议，它为每个多播组建立一个博阿含所有接收节点到发送节点逆向最短路径的共享多播网结构，且在该协议中有一个或多个核心节点，其他节点将想核心节点发送加入多播组的请求，而不是采用洪泛的方法，从而可以限制节点加入一个多播组的通信开销。核心节点不需要是多播网结构的一部分，且它的实效也不会导致数据分组转发及多播网维护过程的停止。CAMP协议支持发送节点以单工方式加入多播组，即节点仅发送多播数据，却不接收该多播组中其他节点发送的多播数据。另外，CAMP协议需要依赖下层的淡薄路由协议，要求它必须能够在有限的时间内提供到所有目的节点的正确路由及距离信息。 4. AMRoute(Ad hoc Multicast Routing Protocol)协议主要关注多播的健壮性，而不是最小宽带或时延等，它为每个多播组建立一棵多组成员共享的双向虚拟多播树，只有多播数据的发送者和接收者才是多播树中的节点，且只有多播有协议树建立之前需要先建立一个多播网结构来建立多播组成员之间的连接关系。5. AMRIS（Ad hoc Multicast routing Protocol utilizing Increasing id-number protocol) 是一种基于共享树的按需多播路由协议，支持在一个多播绘画中有多个发送者和接收者，它的核心思想是以多播会话中的某个发起节点为根，动态地给每个节点分配一个MSM_ID号，形成一个有向无环路（DAG）。节点离根越远，其MSM_ID的值越大；然后在此基础上利用DAG图的子集形成一个多播树。节点的MSM_ID号可以用来动态管理节点加入或离开多播组，决定多播数据的传送方向及用于链路中断时多播树的重构等，以避免多播树产生环路。4各种路由协议性能比较特性协议DSDVWRPSTARADSRAODVTORALARCOSRCRDAR分布式操作是是是是是是是是是无环路由是是是是是是是是是主动按需主动主动主动主动按需按需按需主动按需周期性路由更新是是是否发送HELLO分组否否是是维护多条路由否否是是否是否否是支持单向链路否否是是否否否否否基于节省能源的策略否否否否否否否否否平面集群平面平面平面平面平面平面平面集群集群分组转发机制逐跳逐跳逐跳源路由逐跳逐跳逐跳逐跳逐跳提供安全机制否否否否否否否否否路由度量选择最短路径最短路径平均时延最小的路径最短路径最短路径最短路径最短路径最短路径最短路径存在特殊节点否否否否否否否否否特殊硬件需求否否否否否双信道GPS否否否支持组播功能否否否否是否否否否QOS支持否否是否否否否否否5.无线自组织网所面临的苦难及解决方案常规路由协议主要采用两种形式的路由思想:距离一向量算法(distance algorithm)和链路