自组网如何路由

1、自组网如何路由？发表时间：2001-5-18徐雷鸣英春史美林来源：计算机世界 关键字：自组网信息化应用调查在线投稿加入收藏发表评论好文推荐打印文本自组网是一个多跳的移动计算机网络。多跳是研究自组网路由协议的前提基础。图1左所示的是一个典型以太网的示例，它通常是一个单跳的局域网，一个节点通过共享的有线信道就可以直接到达另一个节点而不需要路由协议参与。在自组网中，由于可能存在如下情形：源节点需要借助中间节点的分组转发才能到达目的节点。图1中节点1与节点2需要通过中间节点3的分组转发。而且，节点 3和节点4都可以承担中间节点的角色，对于节点1需要根据某种路由策略进行最佳路由的选择。这里，需要对以下两

2、个经常被问的问题进行回答。 皿0m抖笔仆1r.叱#?第月门产图1单跳的以太网和学部的白祖国问题一为什么不通过某些技术手段来扩大每个节点的通信范围，从而将多跳网络简化为一跳网 络？我们认为主要有以下几个原因。其一，扩大通信覆盖范围，主要是通过加大发射功率， 加高天线的高度等手段。 这种方式对于许多移动终端而言，在功耗上、电磁屏蔽上、便携性和灵活性、设计成本等方面都是巨大的挑战。其二，当所有的终端都同处于一个通信覆盖域中，共享的无线信道将变得更加拥挤，信号碰撞的几率将加大， 信道的有效利用率将急剧下降。在自组网环境中，可以通过中间节点参与分组转发有效地降低对无线传输设备的设计难 度和成本，同时也扩

3、大了自组网的覆盖范围。当然，自组网中并不是没有大功率无线传输设备的存在。问题二自组网中的移动终端与通常的移动计算机网络中的移动终端有何不同？在计算机网络中，主机和路由器是两个完全不同的物理设备， 承担了不同的功能角色。 主机主要是运行面向用 户的应用程序，提供用户使用网络的人机接口。路由器， 作为网络互联设备，运行相应的路 由协议，进行分组转发和路由维护工作。在自组网中，移动终端需要同时承担这两个角色。这将意味着：参与自组网的移动终端之间存在某种协同工作的关系，这种关系使得每个终端都将承担为其他终端进行分组转发的义务；由于移动终端相对于常规固定主机而言，其计算能力、内存量等方面都要逊色一些，尤

4、其是在电能提供上， 因此在设计软件算法上要求简单实用，而不能像通常路由器软件那样复杂精巧。通常的移动计算机网络中的移动终端主要承担主机的角色，有关信息交换的智能性主要体现在移动路由器。路由协议的设计自组网的路由协议有着其特定的应用空间。假设自组网的网络拓扑结构与固定网络中一 样较为固定，可以认为采用常规路由协议就基本上解决了自组网中的路由问题。假设自组网的拓扑结构变化极为剧烈，可以认为除了采用泛洪协议( flooding )外没有任何协议可以适 应这种变化速度。在泛洪协议中，中间节点只需要对接收到的分组判断是否第一次收到，如果是而且自己不是目的节点则继续转发。所以泛洪协议是一种最简单也是最可靠

5、的路由协 议，网络拓扑结构变化对它毫无影响。但是泛洪协议会带来对网络带宽和设备能源的巨大消 耗。对于自组网的路由协议，其应用空间就是位于这两个极端之间，即网络的拓扑结构发生变化，但是其变化速度不至于使泛洪协议成为唯一可用协议的应用场景。三种设计思路目前，国内外许多研究人员基于不同角度提出了自组网路由协议。这里主要有三种思路。第一种思路是通过修改现有的常规路由协议以适应在自组网环境工作，例如Charles E.Perkins提出的DSDV协议。DSDV协议是在RIP协议的基础上，通过引入序列号机制解决 了距离矢量类型协议固有的路由环路和计数到无穷的问题。第二种思路是基于按需路由发现的路由原则，例

6、如DSR协议、AODV协议、ABR协议、TORA协议。按需路由是指节点不再通过周期性的广播路由信息分组而是在发现没有去往目 的节点的路由的时候按需发起路由请求。这种机制最先是由美国的卡耐基梅隆大学的DavidB.Johnson在DSR协议中提出的。按需路由是自组网路由协议区别于常规路由协议的一个 重要特征。第三种思路是基于 QoS路由。自组网环境下的 QoS的路由是指节点收集网络的资源情 况，选择一条最有可能满足用户QoS的路由，而不再仅仅是采用跳”作为路由度量尺度产生的最短路由。例如清华大学计算机网络&CSCW实验室提出的LS_QoS协议。目前自组网环境下的路由协议根据不同的角度可以进行不同

7、的分类。根据发现路由的策 略可以将其分为主动路由协议和按需路由协议；根据网络逻辑结构可以将其分为平面结构和层次结构两种。主动和按需路由主动路由协议采用周期性的路由分组广播，交换路由信息。每个节点维护去往全网所有 节点的路由。主动路由的优点是当节点需要发送一个去往其他节点的数据分组时，只要路由存在，发送分组的延时很小。缺点是主动路由协议需要花费较高代价(带宽、电源、CPU资源等)尽量使得路由表能够跟上当前网络拓扑结构的变化，但动态变化的拓扑结构可能使得花费较高代价得到的路由表中的内容变成无效信息，路由协议始终处于不收敛状态。目前，这种类型的自组网路由协议提出了各种机制改善在这些方面的性能。按需路

8、由协议是根据发送数据分组的需要按需进行路由发现过程，网络拓扑结构和路由 表内容也是按需建立的， 所以其内容可能仅仅是整个网络拓扑结构信息的一部分。按需路由的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是如果发送数据分组时，没有去往目的节点的路由，数据分组需要等待一定时间的延时。并且由于相应路由发现过程通常采用了全网泛洪机制进行搜索，这在一定程度上抵消了按需机制带来的好处。平面和层次结构路由对于平面结构的路由协议，如图2左所示，网络的逻辑视图是平面结构，移动节点的地位是平等的。平面结构路由的优点是没有特殊节点，路由协议的可靠性较好，网络交通流量平均地分散在网络中， 节点移动性较为

9、简单易于管理。其缺点是缺少可扩展性，限制了网络唐求M何明2平面乱展次第构冷山对于层次结构的路由协议，网络的逻辑视图是层次性的(如图2右所示)。层次划分的依据可以是信道编码、协同工作关系、地理位置等多种因素。层次结构通常有：骨干网和分支 子网组成的两层网络结构、多级层次结构。在两级网络结构中，骨干网由较为稳定、综合性 能较好的骨干节点组成，其他移动节点按照某种策略组成每个分支子网络。分支子网络又称为集群。在同一个集群的移动节点之间的通信只经过集群内部；在不同集群的移动节点之间的通信需要跨越骨干网。层次结构路由的优点是适合大规模的自组网环境，可扩展性较好。其缺点是骨干网节点的可靠性和稳定性对全网性

10、能影响较大，为支持节点在不同集群之间进行移动需要一定的协议开销。自组网路由协议描述我们以清华大学计算机系计算机网络&CSCW实验室提出的LS_QoS协议为例，描述一个自组网路由协议行为。LS_QoS ( Link State Based QoS Routing )协议是从 QoS路由角度提出的一种自组 网环境下的路由协议。大多数路由协议都是采用跳”作为路由的基本度量尺度，最好”路由的标准就是从源节点到目地节点一条跳数最少的路由。在QoS路由的研究中，对 QoS满足与否通常是与所选路由的可用带宽、延时、延时抖动、吞吐量、丢失率等QoS参数相联系。在LS_QoS中，充分利用了自组网无线信道的广播特

11、性，参考了信道的两个重要指标： 平均错误分组率和生存时间，在多条存在的路由中。最好”路由的标准是：信号接收质量和信道稳定性最好的路由，其中信号的接收质量是通过平均错误分组率表征，信道稳定性用生存时间表征。这主要是基于如下考虑。首先，这两个指标具有可比性。而诸如内存量、 CPU计算能力等其他指标由于大多数移动节点硬件配置通常是相同的，所以相应的这些指 标参数也是相同的。 其次，获取这两个指标所需的代价相对较低，容易实现，且不需要特殊的硬件支持。某些指标，诸如剩余电源的多少，节点的地理位置等都需要相应的软硬件支持。 可用带宽随着业务的变化而变化，且需要通过复杂缓冲区调度算法得到。其他QoS参数的获

12、取也都面临着这样的问题。的3 L3 Qo3愤R却案LS_QoS协议框架如图3所示。链路指标收集、计算、交换模块 ”实时收集无线设备驱 动程序提供的链路参数统计无线链路平均错误分组率，通过路由分组转发模块和底层提供的信息收集无线链路生存时间，并计算相应指标和链路边权，更新链路状态数据库的内容。LS_QoS协议周期性与邻居节点交换链路状态数据库的内容，通过序列号机制区分链路的新旧状态。路由分组转发模块”根据接收到分组的目的地址查询路由表进行不同的路由转发决 定：1.目的地址是自己则向上层网络应用程序递交；,2在路由表查找到目的节点，则向下一跳节点进行转发；3,没有去往目的节点的路由并且是上层应用程

13、序递交的数据分组，则触 发路由请求过程，发现去往目的节点的路由；4,否则丢弃该分组。 路由请求和维护模块”按需地发起路由请求过程，通过有控制的广播机制寻找一条最优”的路由，并更新中间节点的链路状态数据库。无线收发设备及其设备驱动程序模块”向网络层协议提供通过无线物理 信道进行数据传输和接收的访问接口，主要完成物理层和MAC子层的功能。大多数无线收发设备都是以广播方式工作，当驱动程序在无地址过滤模式”下工作时，网络层传输协议和路由协议可以接收到邻居节点发送的分组，即使分组的目的地址不是它。LS_QoS路由协议利用了这个重要的特性，充分收集可用的链路信息， 监听与邻居节点之间无线信道的有效性。 在

14、LS_QoS协议的设计过程中， 我们也借鉴了已有路由协议中一些好的思想（比如DSR中的按需路由请求方法），根据LS_QoS协议的整体设计思想作了相应改动后有效地发挥了其作用。协议性能比较目前自组网的工作小组还没有正式公布的自组网路由协议的RFC标准。其中一个重要的原因就是没有确定自组网路由协议评价框架。随着RFC 2501 （自组网路由协议性能观点和评价）的制定，将有利推动这方面工作的进行。根据RFC 2501 ,自组网路由协议的性能比较主要是从定性和定量两个方面进行。定性比较一个好的自组网的路由协议应当满足以下特性要求： 分布式运行方式； 提供无环路路由；按需进行协议操作； 安全性； 提供设

15、备睡眠”操作特性； 对单向信道的支持。定量比较通过以下指标可以对自组网的路由协议性能进行定量分析。端到端的平均延时； 分组的平均递交率； 路由协议开销； 路由请求时间。现有提出的各种自组网路由协议在相应的文献中都提供了相应指标的模拟结果。但是由于各自都是在不同的模拟环境下得到的，所以相互之间的可比性较差。目前自组网研究人员较为通用的模拟仿真平台是由Berkeley大学开发的NS-2软件。对于模拟仿真的另一个重要问题是模拟环境参数的设定。模拟环境参数主要包括：网络规模；网络的连接度；网络拓扑结构的变化程度；无线信道的传输带宽；单向信道的比例；信息流量的通信模式；终端节点的运动模式。目前提出的各种

16、自组网路由协议DSDV ( Destination Sequenced Distance Vector)协议WRP ( Wireless Routing Protocol )协议DSR (Dynamic Source Routing )协议ABR (Associativity Based Routing )协议ZRP (Zone Routing Protocol )协议AODV (Ad hoc On Demand distance Vector Routing )协议TORA (Temporally Ordered Routing Algorithm )协议 LS_QoS ( Link Sta

17、te Based QoS Routing )协议自组网面临的问题自组网的特性为自网路由协议设计提出了新的问题和挑战，主要有以下几点。动态变化的网络拓扑结构常规路由协议(例如RIP和OSPF)是为有线固定网络设计的，它们的网络拓扑结构通常是较为固定的，不会出现大的网络拓扑结构变化。而自组网正好相反，动态变化的网络拓扑结构正是它的一个最显著特点，常规路由协议通常是没有考虑这一点的。产生的后果就是在自组网环境中，当网络拓扑结构变化后，常规路由协议需要花费很长的时间才能到达收敛状态，而此时拓扑结构可能在达到收敛状态之前又发生了变化。所以可能造成这样的一种情况：自组网主机在花费了很高的代价(如网络带宽、能源、 CPU资源等)之后得到了网络 的临时拓扑结构，而由于动态变化的拓扑结构导致这个结果中的大部分内容变得陈旧，协议状态始终处于不收敛状态。单向信道的存在对于常规路由协议而言，通常认为底层的信道是双向的。但是在采用无线通信的自组网环境中，可能存在单向信道。这可能是由于地理位置或节点发射功率等因素造成的。如图4所示，两个移动终端 A、B, A由于发射功率较大所以能够到达B,而反之不行，即存在一条A-B的单向信道。因此，常规路由协议计算出的路由不能准确反映自组网的拓扑结构， 也无法有效利用单向信道。对于需要逐跳确认的数据分组也由于单向信道的存在而无法实 施。S 4单向信遒示例有限的无线传输