（通信与信息系统专业论文）无线网状网路由算法研究.pdf

摘要 无线网状网是一种高速率、高容量的多点对多点网络，可把它看成 是a dh o c 网络的简化版本。正如a dh o c 网络一样，无线网状网中的路 由是它的一项关键技术。基于此，本论文对无线网状网的路由协议进行 研究。 文中首先介绍了无线网状网的结构，特点以及其发展与现状；其次， 分析了a dh o c 网络中各种路由协议的优劣；再次，重点研究了其中的 一种动态源路由协议( d s r ) 的具体实现过程；在d s r 的基础上，对其进 行改进，提出了一种均衡流量动态源路由协议，对它进行性能分析和仿 真。另在不能运行或运行d s r 困难的情况下，提出了简易动态源路由算 法( a d s r ) ，使得在低移动速率的情况下，a d s r 仍然有较高的分组接收 率。最后，将均衡流量的动态源路由算法和a d s r 结合起来，使得网络 性能有了双方面的改善。 关键词；无线网状网 a dh 0 c 网络 均衡流量算法简易动态 源路由 a b s t r a c t w i r e i e s sm e s l ln e t w o r ki sah i g b - 瑚t e 釉d1 1 i g h - c 印a b i l i t yn e t w o r k ，w e c a nc o n s i ( i e ri ta sf h es i 啪l ee d i t i o no fa dh o cn c t w o r k 。a si na dh o c n e “v o r k ，r o u t ei sa ni m p o n a n tp a ni i lw i r e l e s sm e s hn c t w o r k t h ea n i c l e s n l d i e st l l em m i gp m t o c o li i lw i r e l 船sm e s hn e t 、 r o 】r k f i r s t l y 协ea n i c l ei i l 劬d l l c e st l l es t n l c t u r e ，f e a l u ma n da p p l i c a t i o no f 、i r c l e s sm e s l l s e c o n d l y ，叩p l yt l l er o u t i n gp m t o c o lo fa dh o cn e “，o 】kt o 、i r e l e s sm e s hn e t v 础n 硼l y ，ad 咖i l e da n a j y s i si sm a d ei nd s rp m t o c 0 1 f m l y w e i 姗c e dt h ed s rb ye q u i l i b r i 啪也e 玎o w ，t l l es i m u l a t i o ns h o w s t l l a t 也em e t l l o dh a se n h a n c e dt h et h r o u g 烟) u tv e r ym u e h ，r e 工i e v e dt h el o e a l t l l r o u g h p u tw l i i c hp m v o k e db yt h eh e a v yl o a d t h a l lb a s e do nd s rp r o t o c o l ， a 1 1e n h a n c e dp r o t o c 0 1 一a d s ri sp r o p o d t h es i m u l a t i o nr e s u l t se x p r e s s t h 砒a tl o wm o b i l i 吼r c c e i v e d 幽l ap k e t sr a d i oi sl l i g h a tl 嬲t ，ic o m b i n e d m e 咖m e t l 的d si no r d e rt oi m d r o e 恤en e t w o r ko nt h et w os i d e st l l a ti h i v es a i db e f l o 豫 k e y 们r d ：w i r e l 黜sm e 3 ha dh o cd s r e q u m b r 嗑u mn o w a d s r 第一章绪论 1 1 无线网状网的概述 1 1 1 无线网状网的基本概念 无线网状网( w i r e l e s sm e s hn e t w o r k ，惴n ) 是一种多跳、具有自 组织和自愈合特点的宽带无线网络结构，即一种高容量、高速率的分布 式网络。目前主要观点认为，w 州是一种由无线链路连接路由器和终端 设备组成的静态无线网络，是i n t e r n e t 的无线版本，它解决了传统无线 局域网( 胃l a n ) 不能满足用户对于随时随地永远在线服务的要求，有助 于将w l a n 的覆盖范围经济高效地扩展到热点区域以外，为用户带来了 真正的移动性和灵活性。w 州不同于传统的无线网络，可以看成是 w l a n ( 单跳) 和移动a dh o c 网络( 多跳) 的融合，并发挥了两者的优势。 作为一种新型网络结构形态，m e s h 结构已被纳入到 8 0 2 1 6 2 0 0 4 ，8 0 2 1 6 e 和即将制定的8 0 2 1 l s 标准中。w 州可以通过一 些中间节点连接互相远离而不能直接连接的无线路由器。 无线网状网是一种新型的公共无线局域网解决方案”1 。与传统w l a n 不同，它将数据以无线方式接入到有线宽带网，从而大幅减少了对成本 高昂的有线连接的需求，并降低了网络部署的复杂程度。同时显著扩大 了覆盖范围，可以构建包括室外场所在内的大范围的网络。特别适用于 那些传统w l a n 系统无法覆盖，或由于网络条件限制而导致使用传统有 线访问成本过高的地区，是对现有网络基础设旌的一个有效补充，良好 的自我配置性使得网络具有自动搜寻、自动路出选择和自我修复能力 3 o 1 1 2 无线网状网的关键技术 无线网状网是基于i p 协议的通信技术，它支持多点对多点的网状 结构，主要由移动互联交换控制中心、智能接入点、无线路由器、p c m c i a 无线终端网卡四部分组成，整个网络以移动互联交换控制中心为中心建 立。 移动互联交换控制中心通过网线与智能接入点直接相连，在智能接 入点的周围相应位置安装若干个无线路由器，以扩展通信范围。网络中 持有笔记本电脑或掌上电脑等移动终端设备可以通过p c m c i a 的无线网 卡以即插即用的方式接入网络，从而确保所有用户都可以随时随地快速 接入无线宽带网络“3 。 无线网状网的核心是移动跳接式路由技术( m o b i l ea dh o c ) ，这是 它能实现移动宽带的根本，有的还采用rq d m a ( q u a dd i v i s i o n m u l t i d l ea c c e s s ) ，它是频分多址、时分多址、码分多址、带有避免冲 突的载波侦听多路存取协议的结合技术，提高了它的频谱利用率和抗干 扰特性。 无线网状网采用直序扩频技术。直序扩频是在发送端直接用具有高 码率的扩频编码去扩展信号的频谱，而在接收端用相同的扩频编码进行 解扩，使扩频信号还原为原始信号。它的优点是：因信号在很宽的频带 上被扩展，而单位带宽上的功率很小，即信号功率谱密度很低。这样， 信号将淹没在噪声之中，对方难于发现信号的存在，加之对方不知道扩 频编码，就更难提取有用信号。因此，扩频使信号的隐蔽性和抗干扰性 增强。 无线网状网还采用了隧道封包的加密技术，即在发送端将所发的数 据包外层再进行一次封包，只有相应的接收端才能将数据包的外层封包 去掉，得到里面的数据。这样，在发送端和接收端之间犹如形成了一条 安全的通信隧道。 还有，无线网状网中所有设备的硬件地址都是在网络系统中注册 的，只有这些注册的网络设备在经过系统认证后，才能接入无线网络与 其他网络设备进行通信。从而保障了安全性。 由于无线网状网不需要建立大型基站及发射塔，并且具有自愈和自 组网的功能，因此消除了因个别通信设备，如基站或发射塔的故障( 即 单点故障) 而导致整个系统通信受阻的隐患。 1 1 3 无线网状网的结构”1 无线网状网w 州由节点组成，节点分成网状路由器( m e s hr o u t e r s ) 和网状客户机( m e s hc l i e n t s ) ，每个节点都可以转发分组。网状路由 器的主要功能如下：网关网桥重发器功能；支持网状联网( 网状路由 器通常安装多块不同相同无线接入技术网卡) ；通过多跳通信可以用较 低功率达到相同的覆盖区域；增强型m a c 协议，以支持在多跳网状环境 下达到高可伸缩性。网状客户机可是笔记本、台式机、p d a 、i p 电话机 和r f i d 阅读器等。一般只安装一块无线网卡，具备必要的网状联网功 能，硬软件平台都比网状路由器简单，可以重发分组，但一般没有网关 网桥功能。 基于节点功能，可以把踟v 体系结构分成三类。第一类是基础设施 主干w m n 。网状路由器之间形成自配置与自愈合链路网。网状路由器 具备网关网桥功能，可以连接现有无线网络，可接入i n t e r n e t 。网状 路由器构成w m n 基础设施主干，供客户机连接。w m n 基础设施主干可 以采用不同类型无线电技术构建。典型情况下，网状路由器使用两种无 线电，一种用于主干通信，一种用于客户通信。典型应用在小区网络中。 第二类是客户机1 。客户机组成实际网络，支持客户机之问的p 2 p 联 网，执行路由和配置功能，不需要网状路由器。它的特点是分组可能需 要通过多个中间节点转发才能到达目的节点。通常基于同种无线电技 术构成，同基础设施主干黼矾相比，对客户机的要求提高。第三种是 混合w m n ，它是前两者的结合，网状客户机可以通过网状路由器访问网 络，也可以直接与其他网状客户机联网，尽管删n 主干提供对其他网络 的连通性，如i n t e r n e t 、w 卜f i 、w i 姒x 、蜂窝和传感器网络等。但是 客户机的路由能力可以改善w 删内的连通性和覆盖能力，从这个角度来 看，混合结构最有应用前景。 1 1 4 无线网状网与其他网络的比较 ( 1 ) 无线网状网与w 卜f i 的比较”。 w i - f i 是基于i e e e 8 0 2 1 l x 标准的技术。目前，w i - f i 包括 i e e e 8 0 2 1 1 b 、8 0 2 1 l a 和8 0 2 1 1 9 。w i f i 发射采用的是低功率无线电 信号，穿透能力差，不能穿过金属，水或其它密度高的材料。通常情况 下，在一般典型的居家或办公室里，w i _ f i 网络的传输距离大约为2 5 到5 0 米。在户外开放的环境里，w 卜f i 网络的传输距离也只有3 0 0 米 左右。由于w i f i 网络的特点是带宽较高但通信范围较小，并且不具有 移动性，但价格便宜，因此，它主要用于小范围的无线通讯，被定义为 无线局域网。 无线网状网是一种基于多跳路由、对等网络技术的新型网络结构， 具有移动宽带的特性，同时它本身可以动态地不断扩展，自组网、自管 理、自动修复、自我平衡。相对于w 卜f i 。无线m e s h 在组网方式、传 输距离以及移动性上都有很大的改进，特别是它具有兼容w i _ f i 的特 性，因此无线m e s h 网络会对w 卜f i 在增加传输距离和移动性，扩展w i f i 应用上提供很大帮助。同时，终端目前的普及应用又会为无线m e s h 的 迅速推广带来好处。因此，w i f i 和无线m e s h 网络可以相互补充、相 互融合。 ( 2 ) 无线网状网与3 g 的比较 到目前为止，3 g 在数字移动电话等一些基本应用上已经做得很完 美，如语音通信、短消息、简单的新闻服务以及股市行情等等。下一步 移动通信所要解决的就是实现移动电话之间更加直接的视频通信，但是 目前实际运行当中的3 g 的数据传输速率还不理想。巨额的牌照费，技 术问题、终端问题使3 g 的发展任重而道远，运营商需要投入大量的资 金、人力来建设和完善，这些因素都会给3 g 的发展带来巨大的挑战。 无线m e s h 网络也具有移动、宽带的特性，与3 g 提供的业务有些相 近。但是二者的定位有所不同。3 g 定位在广域网，与2 g 、2 5 g 一样， 将继续为公众移动通信服务，3 g 发展必须依赖大规模布网，时间会比 较长。而无线m e s h 是基于i p 的，定位在城域网，组网灵活，可以先在 小范围使用，然后逐渐发展起来，更适合于各垂直行业的专网应用。它 先于3 g 进入市场，同时它又具有很强的兼容性，便于将来与3 g 兼容， 解决3 g 末端接入的问题。 ( 3 ) 无线网状网与w i m a x 的比较 w i 嗽x 定位在无线i p 城域网，包含8 0 2 1 6 a 、8 0 2 1 6 e 。8 0 2 1 6 a 的标准已经制定，只支持视线范围传输，固定点接入，支持点对点或点 对多点组网；8 0 2 1 6 e 标准尚处在开发阶段，将会支持非视线传输具有 一定的移动性。从市场角度讲，无线m e s h 与8 0 2 1 6 a 都是在城域网应 用，但是无线 e s h 是移动城域网，目标是为专网中的个体提供移动宽 带服务；而8 0 2 1 l a 解决的点对点或点对多点的固定接入。 总体来说，在占有市场空侧方面，无线网状网已经先于w i m a x 、3 g 进入市场。同时，无线网状网也可以依靠已被市场接受的w i f i 终端迅 速发展起来。从技术上分析，无线网状网、w i f i 、w i m a x 彼此可以相 互补充，共同组成无线城域网。w i f i 以低廉的成本，普及的应用占据 末端局域网接入市场，w i m a x 则可以作为城域范围的固定点接入，无线 网状网能够实现城域范围内的移动宽带专用通信网。当然，随着技术和 市场的不断发展，无线网状网与将来的8 0 2 1 6 e 和3 g 在业务层面上的 确存在着重叠的地方，由此也会带来一定的竞争，但我们目前所能得出 的结论则是：它们之间的互补性要大于竞争性。 1 2 无线网状网的发展及现状”1 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒战术移动通信系统的研发。 在投入大量资金、持续6 年多的研发之后，有关移动a dh o c 网络的一 些理论与技术问题得以解决，从而彻底改变了过去构建无线网络的规 则。d a r p a 的目标是：无传统的通信基础设置；采用多跳转发的传输机 制；宽带数据数率；端到端的i p 支持；除了数据业务以外，还要支持 话音和视频业务；内置定位系统( 非g p s 系统) ；能支持高达2 5 0 英里 小时的车辆移动速度。特别是近几年，美国通过一些大型国防项目，攻 克了a dh o c 网络的一些关键技术，其中，i t t 持有了其中的核心的自 主知识产权技术。 可是，除了战术无线通信以外，真正的商业应用在那里是业界一直 困惑的一个问题。2 0 0 0 年初，i t t 将专有技术转让给了美国m e s h n e t w o r k s ，用于商业化产品的开发，至此，a dh o c 网络的商业化进程开 始显现。2 0 0 2 年，i n t e l 开始关注并认可a dh o c 网络技术，m e s h n e t w o r k s 和t r o p o s 等公司开始相继开发出适用于商业应用的相关产 4 品。 这些产品和方案主要定位于移动性较小或静止的a dh o c 网络即无 线m e s h 网络。于是，无线m e s h 网络的概念得到人们的关注。值得一提 的是，自2 0 0 0 年3 月m e s hn e t w o r k s 成立以后，它成功地开发了一系 列相关产品，基于其良好的成长性，目前被m o t o r o l a 收购。另方而， 2 0 0 2 年8 月，美国f c c 宣布停止c d p d ( c e l l u l a rd i g i t a lp a c k e td a t a ) 业务，一些采用c d p d 的企业开始寻求其替代技术，如w i _ f i ( 8 0 2 1 1 ) 等技术，因此基于w i _ f i 的多跳网络技术进入人们视野。除此之外，目 前网络设计的理念也开始从集中趋向分散：集中控制与管理向分散控制 与管理发展；客户机服务器模式向w e b 业务模式发展；集中式的目录 向联合式的标识发展；电路交换的电话业务向i p 电话与多媒体业务发 展；需要许可证的蜂窝电话向非许可证的无线业务发展。 2 0 0 4 年9 月2 1 日。中国无线技术大会上，北电网络展示了无线网 状网解决方案的优势和成功案例，并共同探讨了全球无线网络的部署现 状和未来发展趋势。无线网状网解决方案主要由无线接入点w i r e l e s s a p 7 2 2 0 ，无线网关w i r e l e s sg a t e w a y7 2 5 0 和o p t i v i t y 网络管理系统 构成。北电网络已和麻省理工学院、台湾大学，以及在美国的一家运营 商及欧洲的运营商合作进行了无线网状网的测试，并在网络上成功运行 了一系列先进的应用。暨南大学己选择北电为其位于广州的主校园部署 中国首个校园无线网状网。无线网状网于2 0 0 5 年1 0 月1 日投入运行， 暨南大学广大师生已能在整个校园范围内通过笔记本电脑和手持终端 在室内或室外访问大学网络和互联网上的资源。 1 3 论文研究目的及内容 本课题的目标是研究适应于无线m e s h 网络特点的快速、准确、高 效和可扩展的动态路由技术。在组网体制上，无线节点间通过无线信道 沟通和自组织，形成无线互联网络，实现网络的拓扑构成、中继与路由、 接入控制和用户管理等功能。与传统的a dh o c 网络相比，w m n 是一种 无线链路连接路由器和终端设备的静态无线网络，是i n t e r n e t 的无线 版本。 本文在第一章中首先介绍了无线m e s h 网络基本情况，包括w m n 起 源和发展、w m n 的主要优点和缺点、w m n 与w i f i ，3 g 和a dh o c 网络的 区别、w 心的网络结构形态、w 州的关键技术等。 在第二章中首先分析了无线网状网不能采用传统路由算法的原因 及现有路由算法的设计思路并详细分析了当前无线自组网的各种路由 算法，最后对各种算法进行了比较，应用于_ l v m n 。 在第三章中详细介绍了当前最为广泛使用的按需路由算法动态源 路由算法，详细的分析了此算法的实现过程，从中汲取有益的思路和经 验。 第四章是本论文的重点部分，在分析到了d s r 的缺点与不足的前提 下，在高负荷的情况下，提出在链路层进行均衡流量的算法改进，并对 改进前后进行仿真。再次，基于d s r 进行简化头文件的算法改进提出 a d s r ，从而在d s r 不能运行或运行困难的情况下，改善了信息接收率。 最后，将两种改进方法相结合，改善了d s r 路由在高负荷和运行困难时 双方面的性能。 第五章对全文进行总结。 6 第二章无线网状网路由技术 在设计无线网状网的路由算法之前，我们应当首先考察下当前已 经成为标准或者正在研究的各种路由算法的特点，尤其是与本课题有较 大相似之处的移动自组织网络的路由算法。经过分析和对比，我们可以 从中吸取有益的经验和思路，再结合移动互联网体系结构的特点和要 求，才能改进到我们所需要的无线网状网路由算法。 2 1 路由算法概述 在网络中一个报文可能要经过多个节点的中转才能到达它的目的 地，此时就需要一个路由协议来实现网络中多跳转发的功能。路由协议 有两个主要的功能：在网络拓扑中寻找并选择一条从源到目的的最佳路 径：按照所选的路径转发报文到目的节点。第一个功能在概念上很直观， 节点根据一定的协议和数据结构( 如路由表等) 就可以实现转发的功能。 因此我们把主要的讨论放在寻路和选路的功能上。 在传统的有线网络的路由协议中，经典的路由算法包括链路状态协 议和距离矢量协议两种。链路状态协议中每个节点都要保存整个网络的 拓扑信息以及每条链路的开销。为了使所有节点中保存的链路开销信息 保持一致，每个节点必须周期性地广播其与周围邻居节点的链路信息。 每个节点在收到这些信息的时候。更新保存的网络拓扑，然后用最短路 径算法来计算到目的节点的下一跳节点。然而某些节点保存的链路开销 可能因为传播的延迟或者网络分区等原因与实际网络中的状态不一致， 这时就可能会在网络中生成路由环路。不过这些路由环路存在的时间很 短，当所有节点保存的拓扑信息收敛后就会消失。 距离矢量协议中每个节点监听其与周围邻居节点的链路状态，但是 并不把这些链路状态向网络中的其他节点广播，而是向邻居节点广播它 估计的到达网络中其他节点的最短路径。收到这些信息的节点用最短路 径算法重新计算路由表。与链路状态算法相比距离矢量算法在计算时更 有效率，更容易实现并且所需要的内存也较少。但是距离矢量算法会导 致路由环路的生成，并且存在的时间既有短期的也有长期的。这是因为 节点对路由中下一跳节点的选择是一种分布式的算法，完全依赖于其他 节点所提供的信息。 现今已知的路由算法中还有一种算法，称为源路由算法。它让每一 个在网络中传输的报文都必须带上完整的路由信息。因此所有的路由计 算都必须在发出报文的源节点完成。这种算法的好处是可以完全避免路 由环路的生成，而缺点则是每个报文都要携带路由信息，增大了网络传 输的开销。 2 2 无线网状网路由协议面临的问题忉 无线网状网不能采用传统的路由算法的主要因素在于：无线网状网 中无线传输设备功率的差异以及无线信道中的大量干扰导致单相信道 的存在：无线信道的广播性使得常规路由的网络选路过程中产生了许多 冗余链路；常规路由周期性广播路由更新分组会消耗大量的网络资源； 常规路由协议周期性的路由更新分组会消耗大量的节点能源；此外，某 些常规的路由协议需要复杂计算使得c p u 始终处于很高的负载下，这也 同样消耗了大量的能源，并将对有限的节点能源带来更多的压力。因此 需要适用于无线网状网自身的路由协议。无线网状网其实是微型的无线 自组网，所以无线自组网的路由协议都适用于无线网状网，无线网状网 是无线自组网的缩小版。 2 3 无线网状网路由协议的设计思路 无线网状网的移动终端同时充当节点和路由两个角色，它一方面要 运行面向用户的应用程序，另一方面又要运行相应的路由协议，根据路 由策略和路由表完成数据转发和路由维护的任务。然而，出于移动终端 的计算能力和存储容量较低，尤其是在电源提供上深受限制，因此要求 路由协议尽量简单实用，这在一定程度上增加了无线网状网协议设计的 难度。 基于以上因素并考虑到无线网络的拓扑结构的动态变化，国内外许 多研究人员从不同的角度提出了相应的路由协议，这里主要有3 种思 路： 第1 种思路是通过修改现有的常规路由协议以适应在无线网状网 的工作环境，例如c h a r l e se p e r k i n s 在1 9 9 4 年提出的目的序列距离 矢量路由( d s d v d e s t i n a t i o n s e q u e n c e dd 【s t a n c e v e c t o r ) 协议。 d s d v 协议是在r i p 协议的基础上，通过引入序列号机制解决了距离矢 量类型协议固有的路由环路和计数到无穷的问题( 即收敛时间过长的问 题) ；通过采用“时间驱动”和“事件驱动”机制更新路由信息，尽量 减少路由等控制信息对无线信道的占用，以提高系统效率。 第2 种思路是基于按需路由发现的路由原则，例如动态源路由协议 d s r ( d y n 锄i cs o u r c er o u t i n g ) ，以及距离矢量按需驱动路由( a o d v ，a d h o to nd e 眦n dd i s t a n c ev e c t o rr o u t i n g ) 协议、基于联合稳定性的 路由算法( a b r ，a s s o c i a t e v i t y b a s e dr o u t i n g ) 、临时指定路由算法 ( t 0 队，t e m p o r a l l y o r d e r e dr o u t i n ga l g o r i t h m ) 等。按需路由是指 节点不再通过周期性的广播路由信息分组，而是在发现没有去往目的节 点的路由的时候按需发起路由请求。这种机制最先由美国的卡耐基一梅 隆大学的d a v i db j o h n s o n 于1 9 9 6 年在d s r 协议中提出。按需路由有 效地减少了占用的网络资源，按需路由是无线网状网路由协议区别于常 规路由协议的一个重要特征之一。 第3 种思路是基于q o s ( q u a l i t yo fs e r v i c e ) 路由。无线网状网环 境下的s 的路由是指节点收集网络的资源情况，选择一条最有可能 满足用户q o s 的路由，而不再仅仅是采用跳数作为路由度量尺度产生的 最短路由。已提出的无线网状网路由协议，对于q o s 支持尚不成熟， 只有少数如a b r 、s s r 有相关的功能，他们多是以链路的稳定作为q o s 标准。对于q o s 支持的难点在于无线网状网的终端随意性及带宽的有限 性，而支持q o s 需要收集周围节点的信息，这会增大开销，进一步造成 宽带的浪费。目前进行q o s 路由设计的思路是借鉴i n t e r n e t 上支持q o s 的方法，如建立区分服务和集成服务模型，并经过适当的改变或组合再 用于无线网状网中。 2 4 移动自组织网络路由算法现状 本节主要考察与本课题移动互联网密切相关的移动自组织网络的 路由算法现状。迄今为止，世界各国的研究人员已经提出了许多种针对 移动自组织网络的路由算法。其中具有代表意义的典型算法列举如下： a b r ( a s s o c i a t i v i t yb 够e dr d u t i n g ) a o d v( a d h o c0 n d c i i m dd i s t a n c ev b c t o rr o u t i n g ) c b i 己p ( c l u s t e rb 鹊e dr o u t i i l 卫p m t o c 0 1 ) d s d v( d e s t i r l a t i o ns e a u e n c e dd i s 乜m c ev e c t o r ) d s r( d y n 啪i cs o u r c er o u 血培) g s r ( g l o b a ls t a t er d u t i n g ) 0 l s r( 0 嘶m i z e dl i l l l 【s t a t er o 嘶豫) t o r a ( t c m d o r a l l yo r d e r e dr o u t i i l g a l 2 硎t l l m ) z r p( z o n ei 沁u t i n 窖p r o t o c 0 1 ) 在这里我们做一个简要的介绍，从中可以吸取它们的设计思路和优 点。 2 4 1 关联稳定度路由协议a 队 a b r ”1 是平面结构的反应式算法。a b r 用端到端的网络拓扑信息计算 路由选择并选择具有关联时间长的路径，路由时仅维护距离矢量。 路由发现过程如下j 当源节点中不存在所需的目的节点路由时，源 9 节点广播一个路由请求报文。中间节点收到请求报文后在报文中附加自 身的地址，然后广播此报文( 重复报文忽略) 。每个且的节点接收到的请 求报文中包含了从源节点到目的节点不同的源路由，因此目的节点可以 获得许多条可行的路由，需要从中选择一条“最优”的路径。 a b r 中每个节点都要广播一个周期性“心跳”报文，同时对从邻居 节点收到的心跳报文计数。这以参数衡量了节点之间的关联性 ( a s s o c i a t i v i t y ) ，即节点之间链路稳定的持续时间。路由请求报文中 递加每一跳的关联性参数。关磁性参数总和最高的路由被认为是最优 的，即使有其他较短的路径存在。因此，a b r 适合于较大区间内大部分 节点之间连通性变化少而问或有快速移动的节点存在的移动网络。 目的节点沿着选定的路由返回一个请求响应报文，每个中间节点都 在其路由表中激活相应的转发信息。 路由维护过程相当复杂，当发生链路失败时，协议根据该链路在路 由中的位置采取本地修补和源修补相结合的方法。失败链路下游的节点 发出一个路由错误报文到目的节点，删除无效的路由表项。而上游节点 则发出一个本地请求( 具有跳数限制的路由请求) 。如果这个本地请求没 有找到新的修补路径，则通知上游的下一个节点使其再发出个本地请 求寻找修补的路径。若这个过程一直回溯到源节点则放弃本地修补并发 出一个路由错误报文到源节点，引发一个新的路由发现过程，寻找到达 目的节点的路由。 2 4 2 按需距离矢量路由协议a o d v a o d v 盹”1 是平面结构的反应式算法。它将d s d v 中使用的目的序列 号技术结合到了反应式算法中。 路由发现过程：当源节点没有到达目的节点的路由时，广播一个路 由请求报文。接收到该请求的节点“反向”记录下指向源节点的距离矢 量，即记录从哪个节点接收到该报文并将其指定为下一跳节点，然后重 新广播该请求报文( 重复请求忽略) 。 当请求报文到达目的节点时，目的节点则利用记录在本地的反向距 离矢量作为路由发回路由响应报文。若中间节点知道最新的指向目的节 点的路由，它就代替目的节点直接发送路由响应报文。当路由响应报文 返回源节点时，每个中间节点相应产生“正向”距离矢量，源节点就可 以沿着新建立的路由开始发送数据。中间节点中的没有被路由响应报文 激活的反向距离矢量很快就被置为过期的。 距离矢量算法仍然受到环路由的影响。和d s d v 一样，a o d v 采用由 目的节点产生的序列号来保证使用的路由不是过期的。每个路由请求报 文都标记上源节点可以从目的节点得到的最大序列号。当且仅当中间节 点记录的指向目的节点的路由序列号大于等于请求报文中的序列号，并 o 且该路由没有过期时，中间节点可以代表目的节点向源节点发送路由响 应报文。如果是由目的节点发送路由响应报文，则该报文中的序列号反 应了目的节点所知的最新的拓扑变化。 路由维护过程：当一个节点发现链路失败，它会发出一个主动的路 由错误报文到通过该链路发送报文的每个邻居节点，且将报文中距离设 为无穷大并将序列号加一。这个路由错误报文从而被传送到每个使用到 失败链路的源节点，在源节点引发新的路由发现过程。目的节点检测到 与其相连的链路发生错误时，将其序列号加一，但不产生主动的路由响 应报文。 2 4 3 基于分群结构的路由协议c b r p c b r p ”是着重于支持单向链路的分区算法，属于分级结构的自组 织路由算法。簇内定义为双向链路，但簇与簇间链接可以由一对单向链 路实现。 为了确定簇的范围，每个节点需维护两跳的拓扑信息。每个簇中包 含一个簇首，簇首与簇成员( 即簇内其他节点) 具有双向链路连接。簇与 簇之间可以重叠也可以分离，但无论怎样，簇首与簇首之间不能相邻。 另外，为了交换相邻簇与簇之间的路由信息，节点必须找到并告诉其簇 首“网关”节点的状态。这样，每个簇首就可以知道所有与其具有双向 链路连接或者通过一对单向链路连接的簇的信息。后者可以通过向邻居 簇首广播请求获得适当的链路。 当源节点没有到达目的节点的路由时，它向其簇首发送一个路由请 求报文。网络的簇结构可以减少请求报文的传播，从而减少了网络资源 的消耗。簇首收到请求后，将自身地址和邻接簇首的列表附加到报文中 然后广播该报文。每个作为网关的邻居节点收到请求报文后，将其单播 到邻接簇的簇首。 请求报文到达目的节点后，它本身包含有一个不精确的由一系列簇 首组成的源路由。当路由响应从目的节点返回源节点时，每个中间簇首 根据本簇的拓扑消息得出最优的路径，并将其写入到路由响应报文中， 形成一个完整的路由。这样得出的路由不需要通过簇首。路由响应到达 源节点后，源节点就可以沿着这条路径发送数据了。 如同d s r 一样，中间节点可以产生新的路由来改进旧的路由或者修 补失败的路由。与d s r 不同的是仅仅簇一级的信息用于这种优化，因为 节点不会存储整个网络范围的拓扑信息。 2 4 4 目的节点序列距离矢量路由协议d s d v d s d v “”是一种平面结构的先应式路由算法，是传统距离向量算法 的一种改进。它在每条路由信息中加入由目的节点产生的序列号，以避 免路由环。为了避免路由振荡，d s d v 延迟广播可能的不稳定路由。 每个节点周期性广播它当前的路由表，包含对应于每个目的节点的 距离和所知的最大序列号。该广播消息还包含发送者自身的序列号，每 广播一次就自动加。每个收到该广播报文的节点将报文中的对应各目 的节点的序列号与自身路由表中相应表项比较，如果报文中的序列号较 高，则更新自己的踌由表，将发送者指定为下一跳，并将距离增加一跳。 如果序列号相等但距离较小，则接收节点也要更新自己的路由表。 当一个节点发现链路失败，它将所有通过该链路的目的路由的距离 设为无穷并将其序列号加一。由于更新了序列号，因此这一消息会传播 到整个网络。这样所有这些目的路由指向的目的节点都有效的与此节点 断开，直到有新的序列号产生并包含新的路由。 除了周期性的全路由表广播，节点还发送增加性的更新信息。为了 减少路由流量和路由振荡，节点在一定范围内决定那些信息包含在增加 性更新报文中。一些信息必须立即发送，如新目的节点，失败路出以及 修补路由等。其他的一些信息不需要立即发送，如路由的距离信息。具 有相同序列号但不同距离的更新信息因为通过不同的邻居节点可能会 按任意顺序到达。为了避免这种情况，节点延迟发送新的路出信息，延 迟的时间由历史记录的最早和最佳路由到达时间加权平均得出。与此相 似，一个对应于已存在路由的新的序列号的路由信息也不应该立刻发 送。然而。仿真的结果说明立即广播可以防止错误路由信息的广泛散播。 2 4 5 动态源路由协议d s r d s r “。w 是一种平面结构的反应式自组织路由算法。它着重于积极 的缓存策略以及从源路由中提取的拓扑信息的推演。 路由发现过程：当源节点没有到达目的节点的路由时，它广播一个 路由请求报文。每个收到该报文的中间节点附上自身的地址然后重新广 播( 忽略重复请求报文和已经包含自身i d 的报文) 。当路由请求到达目 的节点( 或者某个知道某条到达目的节点的路由的中间节点) 时，它就可 以决定一条到达目的节点的完整源路由。 目的节点( 或中间节点) 将所得的源路由包含在路由响应报文中，然 后沿着所得路由反向发送回源节点，也可阻附带在目的节点的路由请求 报文中。源节点收到路由响应报文后，它将源路由存入缓存，并置入每 个数据报的报头。中间节点根据数据报头中的路由信息中转数据报文。 在d s r 中结合了许多基于积极缓存和拓扑信息分析的优化措施。从 数据报文的报头中中间节点可以得出到达所有下游节点的路由，并且通 过合并多条路径的路由信息，还可以推演出更多的拓扑信息。另外，使 节点的网络接口工作在混杂模式下，监听邻居节点使用自潞由，还可以 获得更多的拓扑信息。 这样，在活动的路由上或者附近的节点就可以将越来越多的“感兴 趣”的网络拓扑信息存入自己的缓存中。高的缓存命中率就意味着可以 减少极其耗费网络资源的路由发现过程的频率，还可以更快的找到所需 的路由。然而，积极缓存也会增加将过期的路由信息注入到网络中的可 能性。 路由维护过程也需要使用缓存信息。如果数据报在逐跳传输过程中 发现链路失败，则可以由中间节点用缓存中的可用路由来代替报头中含 有失败的链路的路由，同时向源节点发送一个路由错误报文。和其他路 由控制报文一样，路由错误报文可以被中间节点监听到，并且根据它将 中间节点中的失败路由删除掉。这样可以使缓存中的错误路由信息的影 响最小。如果路由失败，源节点则重新开始一个新的路由发现过程。 拓扑变化可以导致更短的路由的产生，如果一个节点发现一个数据 报所包含的源路由下游中有自身的地址，可以发送一个主动的路由响应 报文，告知源节点一个更短的路由存在。 2 4 6 交换网关路由协议g s r g s r o ”是一种平面结构的先应式算法。它是传统的链路状态协议的 改进。传统的链路状态协议中各节点每当连接发生改变时会向其他所有 的节点发送链路状态信息，g s r 则是通过周期性的交换有序的数据来散 播链路状态信息，而并非传统的泛滥方式，大大减少了散播链路状态信 息的费用。 在g s r 中每个节点周期性向其邻居节点广播全部的拓扑表，拓扑表 中包含了该节点最近访问过的本地链接和当前的整个网络拓扑的链路 状态信息。表中每一项都标记上序列号。当且仅当节点收到具有更大的 序列号的对应表项时，对应于某个目的节点的链路状态被更新。 基于拓扑表中完整的网络拓扑信息，节点可以使用任意的最短路径 算法计算最优路由表，路由表中包含由该节点到达目的节点的路由的下 一跳信息。g s r 采用了d i j k s t r a 算法的改进算法来实现路由表的计算。 在无线环境中信道获取是非常重要的参数，因此较少频率交换大的 拓扑表比起广播链路状态信息的泛滥方式来说效率更高。同时这种交换 方式还可以保证路由控制对网络资源的消耗不会随节点移动的快慢而 改变。然而新的链接信息没有散播开来的时候，数据只能被丢弃掉，这 个散播的过程有可能需要好几个交换周期。 2 4 7 优化的链路动态协议0 l s r o l s r “”是一种基于邻域选择的非对等协议，它在其邻居节点中选取 一个子集参与链路状态协议。 链路状态协议中，每个节点与周围邻居节点的连接发生改变时都要 向网络中其他的所有节点发送链路状态信息。o l s r 在两个方面减少这 一操作的费用。首先，使用多点中继( m u l t i p o i n tr e l a y ) 来减少泛 滥方式下冗余的广播报文。另一方面为了减少广播的链路状态的大小和 频率，每个节点仅广播多点中继集中的节点的链路状态信息。 一个节点的多点中继集是其一跳邻居节点的最小( 或接近最小) 的 子集。使得该子集内的节点重新广播消息时可以让所有两跳距离的邻居 节点都能收到。当一个节点发送一个广播消息时，所有邻居节点都收到 并处理该报文。但是只有属于源节点的多点中继集的并且没有收到重复 报文的邻居节点才重新广播该报文。这样就极大的减少广播报文的数 量。因为每个节点独立地选择多点中继集，它必须知道距离自己两跳范 围内邻域的拓扑信息，但不需要更大范围内的节点间的合作。 0 l s r 协议中，每个节点都采用这种广播技术来发布其多点中继集 的链路状态信息。这个过程是周期性的，当多点中继集中链路状态发生 变化时周期就减少到一个最小值；当多点中继集中链路处于稳定状态 时，周期会增加到一个设定的更新间隔。每个节点用链路状态消息中的 拓扑信息计算自己的路由表。 2 4 8 临时预定路由算法t o r a t o r a 1 是一种平面结构的反应式算法。t o r a 是在早期的“链路反 转”( 1 i n kr e v e r s a l ) 算法的基础上发展出来的，它为每个目的节点构 造一个基于目的的有向无环图。如果链接的改变导致一个节点失去了其 所有的输出链路，则该节点“反转”一些或者全部的输入链路的方向。 t o r a 假设当每个节点的任何一条链接到邻居节点的链路发生改变 时都应该有消息通知该节点。如果链路层不提供这种消息，则需要使 用轮询技术。 当源节点没有到达目的节点的路由时，它广播一个路由请求报文。 该报文会被重新广播直到到达目的节点。目的节点将自己的高度定义为 o ，然后广播一个更新消息告诉其他节点自己的高度。每个收到更新报 文的节点都将自己的高度设为比报文中的高度大l ，然后再发出一个更 新消息，告诉其他节点自己的新的高度。这些更新消息必须按同步时序 或者逻辑的时间标记进行可靠的传输，以防止长时间存在的环路。这个 过程构造出一个从源节点到目的节点的有向无环图用来实现逐跳的路 由。 如果发生链路失败，节点就将自己的高度设为相对于失败链路的本 地最大值( “链路反转”) 并将自己的高度用更新消息广播出去。链路失 败仅仅在节点失去其最后一个输如链路时广播。t o r a 将高度反应出了 链路反转的节点区分开，从而可以直接检测到有向无环图被划分开，只 4 有这种情况下节点会广播一个清除路由消息，并重新开始路由发现过 程。 2 4 9 区域路由协议z 胂 z r p 【l ”是一种基于邻居选择的平面结构的路由算法。它结合了先应 式和反应式路由策略的优点，是一种混合式的路由协议。每个节点在本 地邻域内采用先应式路由，而在更远的区域使用反应式路由获取路径。 一个节点的区域( z o n e ) 是该节点在区域半径跳数之内可以到达的 邻近节点的集合。距离中心节点为区域半径跳数的节点组成了区域的边 界。因此每个节点潜在地处于多个区域之内和多个边界之上。 先应式的域内路由协议( i a r p ) 是一种改良的距离向量算法。当源节 点没有i a r p 路由到达目的节点时，则启动一个反应式的域外路由协议 ( i e r p ) 来发现所需的路由。该路由发现的过程与在对等的路由结构下进 行的路由发现过程有一定的区别，它可以利用每个节点所知的域内拓扑 信息。所以源节点“边界广播”一个路由请求报文到其所有区域边界节 点。收到该请求后，每个边界节点考察自己的i a r p 路由信息，如果目 的节点不在自己的区域之内，则将自己的地址加入请求报文并重新进行 “边界广播”。当请求报文到达某边界节点且该节点的区域恰好包含目 的节点时，报文中包含了一个非严格的源路由，即该路由中的每个节点 之间通过i a r p 路由相连。这个松散的路由可以用于计算完整的源路出， 同时也可以得出一些部分路由并保存在中间节点的缓存中。它还可以用 于路由优化。 边界广播比起其他反应式路由协议中使用的普遍广播方式费用更 高。这是因为一般来说节点的边界节点个数都大于其直接的邻居节点个 数。此外，每个边界广播报文都要经过区域半径跳数才