（通信与信息系统专业论文）无线mesh网络路由协议的研究.pdf

摘要 无线m e s h 网络( w i r e l e s sm e s hn e t w o r k ) 简称w m n ，是一种新型的无线通信 网络。无线m e s h 网络w m n 可以看成是一种特殊的w l a n ，除移动性较低外， w m n 本质上是一种a dh o e 网络。目前主要观点认为，w m n 是一种由无线链路 连接路由器和终端设备的静态无线网络，是i n t e m e t 的无线版本。无线m e s h 网络 具有自组织和自愈的特点，并且具有有效的移动用户和跟踪机制，是一种多跳的 宽带无线网络，也是一种高容量，高速率的分布式网络。 本文主要研究无线m e s h 网络的路由协议。首先介绍了无线m e s h 网络的结构， 特点和应用；其次，介绍了无线m e s h 网络的三种类型的路由协议：先验式路由 协议，反应式路由协议和混合式路由协议，比较了三种路由协议的性能；接着重 点介绍了动态源路由协议d s r 的实现过程；最后，基于d s r 路由协议，考虑到 网络中节点的自私性的存在以及单纯使用最小跳数选路方法的缺陷，提出了一种 混合参数量度一信誉度，可用带宽和最小跳数，基于这个量度，通过m a c 层和网 络层的跨层设计，提出了一个基于以上混合量度的路由协议( f a b m h r a dh o e r o u t i n g b a s e d o n f a m ea n da v a i l a b l e b a n d w i d t h ) 。通过使用该协议在不同场景的网络 环境中仿真证明，该路由协议在网络的拥塞控制和负载均衡，网络的平均寿命， 节点的碰撞次数，平均端到端延迟方面较d s r 都有较大的改善。 关键词：无线m e s h 网络自组织网络动态源路由协议基于信誉度，可用带 宽和最小跳数的路由协议 a b s t r a c t t h ew i r e l e s sm e s hn e t w o r k0 v m n ) i san e wt y p eo fw i r e l e s sc o m m u n i c a t i o n n e t w o r k w m ni sas p e c i a lw l a n i ti si ns u b s t a n c eak i n do fa dh o cw i t hl o w m o b i l i t y w m ni sc a p a b l eo fs e l f - o r g a n i z a t i o na n dm u l t i h o pm u t i n g , a sw e l la si t s c a p a b i l i t yo f m o b i l eu s e rm a n a g e m e n ta n dt r a c i n g i ti sam u l t i - h o pb r o a db a n d w i d t h d i s t r i b u t i n gw i r e l e s sn e t w o r kw i t hh i g hc a p a c i t ya n dh i g ht r a n s m i s s i o nr a t e n o wm a n y p e o p l eb e l i e v et h a tw m n i saw i r e l e s sv e r s i o no fi n t e r n e ta sas t a t i cw i r e l e s sn e t w o r k w i t hr o u t e r sa n dn o d e sw i t hw i r e l e s si i n k s t h i sp a p e ri sa b o u tt h es t u d ya n di m p r o v e m e n to fr o u t i n ga l g o r i t h mi nw i r e l e s s m e s hn e t w o r k f i r s t l y , t h ep a p e ri n t r o d u c e st h es t r u c t u r e s ，f e a t u r e sa n da p p l i c a t i o no f w i r e l e s sm e s hn e t w o r k s e c o n d l y , t h er o u t i n gp r o t o c o l so fw i r e l e s sm e s hn e t w o r k a t ei n t r o d u c e d t h i r d l y , ad e t a i l e da n a l y s i si sm a d ei nd s rr o u t i n gp r o t o c 0 1 l a s t l y b a s e do nd s rr o u t i n gp r o t o c o l ，am u l t i p l e xm e t r i c - f a m ew i t ha v a i l a b l eb a n d w i d t hi s p r e s e n ti nv i e wo ft h en o d es e l f i s h n e s sa n dt h ed r a w b a c ko fm i n - h o pr o u t i n g s e l e c t i o n m e t h o d w i t ht h em e t r i c ，t h r o u g ht h ec r o s sl a y e rd e s i g no nm a c a n dn e t w o r kl a y e r , a r o u t i n gp r o t o c o lw h i c he m p l o y st h ea b o v em e t r i ci sg i v e ni nt h i sp a p e r s i m u l a t i o n r e s u l t ss h o wt h a t , u n d e rs t a t i c0 1 m o b i l ee n v i r o n m e n t ，f a b m h ra l lo u t p e r f o r md s r i nn e t w o r kc o n g e s t i o nc o n t r o l ，l o a db a l a n c e ，n e t w o r kl i f e - s p a n ，t h ec o l l i s i o nt i m e sa n d a v e r a g ee n d t oe n ad e l a y k e yw o r d s ：w i r e l e s sm e s hn e t w o r k ( w m n ) a d h o cd s rf a b m h r 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的 说明并表示了谢意。 申请学位论文与资料若有不实之处。本人承担一切的法律责任。 本人签名：鲤至煎日期兰! 塑：! ：! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权 保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分 内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业 后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本人签名： 导师签名： 解互埒 碰趣丛：vt 日期 2 口。7 ；，留 日期趔? _ i 主! 呈 第一章绪论 第一章绪论 随着信息技术的不断发展，人们对移动通信的需求越来越强。近年来，移动 通信技术得到了飞速发展和普及。蜂窝移动通信系统，无线局域网0 e e e 8 0 2 1 1 和h i p e r l a n ) ，蓝牙技术( b l u e t o o t h ) ，家庭无线i 网( h o m e r f ) 等移动通信新技术也 纷纷涌现。这些技术的出现，推动了无线通信技术的发展。ha n 在接入领域得 到迅速发展，因其所具有的巨大数据传输速率，w l a n 被认为是3 g 或3 g 后移 动通信部分的一个主要竞争对手。但w l a n 有其不足之处，其中最主要的一个便 是接入点( a p ) 的覆盖范围较为有限，若要在一个相对较大的区域提供无线覆盖， 就需要在该地区内配置多个接入点，因而增加了建设基于w l a n 的公共宽带网的 成本。虽然人们对此提供了一些解决方法，如通过多种无线技术的共存来提高无 线的覆盖和位置的适应性等等，但这些方法中大多是以增加接入点和降低网络运 行效率为代价。于是人们把目光转向了另一种网络结构无线网状网( w i r e l e s s m e s h ) ，希望通过这种全新的网络结构来克服传统无线网络中所存在的固有缺点， 实现无线宽带领域中的一次变革。， 1 1 无线m e s h 网络的背景与起源 1 9 9 7 年，美国d a r p a 开始组织战场鲁棒技术移动通信系统的研发。在投入 大量资金，持续六年多的研发之后，有关移动a dh o c 网络的一些理论与技术问题 得以解决，从而彻底改变了过去构建无线网络的规则。d a r a p 的目标是：无传 统的基础设施；采用多跳转发的传输机制；宽带数据效率；端到端的i p 支持；除 了支持数据业务以外，还要支持话音和视频业务；内置定位系统；能支持2 5 0 英里 d , 时的车辆移动速度。特别是近几年，美国通过一些大型国防项目，攻克了a dh o c 网络的一些关键技术，其中，r 兀持有了其中的核心的自主产权技术。 可是除了战术无线通信以外，真正的商业应用在哪里? 这是业务一直困惑的 一个问题。2 0 0 0 年初，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 等公司开始相继开发出适用于 商业应用的相关产品。 这些产品和方案主要定位于移动性较小或静止的a dh o c 网络无线m e s h 网络。于是，无线m e s h 网络的概念得到人们的关注。值得一提的是，自2 0 0 0 年 3 月m e s h n e t w o r k s 成立以后，它成功的开发了一系列相关产品，基于其良好的成 2 无线m e s h 网络路由协议的研究 长性，目前被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 幻业务，一些采用c d p d 的企业开始寻求其替代 技术，如w i f i ( 8 0 2 1 1 ) 等技术，因此基于w i f i 的多跳网络技术进入人们的视野。 除此之外，目前网络设计的理念也开始从集中趋向分散：集中控制与管理向分散 控制与管理发展；客户机服务器模式向w e b 业务模式发展；需要许可证的蜂窝 电话向非许可证的无线业务发展，如图1 1 所示。 集中控制与管理 客户机服务器模式 分散控制与管理 w e b 业务模式 图1 1 集中向分散的发展趋势 1 2 无线m e s h 网络及其特点 1 2 1 无线m e s h 网络的定义 无线m e s h 网络是一种与传统的无线网络完全不同的网络，传统的无线网络 必须首先访问集中的接入点( a p ) 才能进行无线连接。这样的话，即使两个 i e e e 8 0 2 1 l b 的节点实际上是互相挨着，它们也必须通过接入点才能进行通信。 而在无线m e s h 网络中，每个节点都可以与一个或者多个对等节点进行直接通信。 “m e s h ”这个词原来的意思就是指所有的节点都互相连接，m e s h 网络技术一度 曾是项军方技术，随着人们对i e e e 8 0 2 1 l a , i e e e 8 0 2 1 1 b 和i e e e 8 0 2 1 l g 等 w l a n 技术了解的深入，m e s h 网络才逐步成为企业界和消费者注意的焦点。 因特网的构架其实就已经是一个m e s h 网络的结构。众所周知，接入因特网 的用户位于网络的边缘，他们通过网络内部的路由器和节点相互连接，而这些路 由器和节点的连接方式是这样的：当任意两个节点之间的一条链路失效后，路由 器会经过一个或多个别的路由器找到一条替代路径。这体现的m e s h 网络的思想。 通常认为，无线m e s h 是点对点网络的一种，把它看成是移动a dh o c 技术的 一种简化版本。但两者有一定的区别，主要的不同在网络结构的连接上，即无线 m e s h 中的接入点既可以作为m a n e t 中一种对等的数据转发实体，又可以作为 一连接到其他有线网络的桥接器。无线m e s h 网络是一种高速率高容量的多点对 第一章绪论 3 多点网络，是一种新型的可以解决“最后一英里”瓶颈问题的分布式网络。 1 2 2 无线m e s h 网络的结构 通常我们把无线网络结构分成两种：一种是点到多点的星型网络，如 i e e e s 0 2 。1 1 无线局域网：一种是点到点的网状网络，如移动a dh o c 网络。实际上， 无线m e s h 吸收了星型和网状两种网络的优点，是对两者的一种无缝融合，这种 融合是通过在网络节点上执行w m r ( w i r e l e s sm e s hr o u t i n g ) 协议来完成的。无 线m e s h 与传统无线星型网络的差别在于：无线m e s h 采用了对等式的网络拓扑， 需要在一种分散式网络环境中进行构建。如图1 2 所示，无线m e s h 中主要存在着 两种网络实体：移动节点( m n ) 和接入点( a p ) ，与传统点对多点网络不同，无 线m e s h 的每个节点都具备路由选择的功能，而且每个节点只与其l 临近节点进行 通信，在网络中m n 既是业务的使用者又是业务的提供者，也就是说它具有数据 的转发功能，可以向网络中的其他节点( m n 或a p ) 转发它所接收到的数据包， 因而无线m e s h 是一种自组织和自管理网。 图1 2 无线m e s h 结构示意图 移动节点( m 接入点t a p ) 有线链路无线链路 应用层 1 p i p w 佩 m a c 物理层 图1 3 基于w 抓的无线m e s h 协议栈 图1 3 是无线m e s h 的协议栈，从图1 3 中可以看出，为提供多次反射无线路 4 无线m e s h 网络路由协议的研究 由功能，在a p 和m n 都执行w m r 路由协议。而且为实现与口兼容，w m r 被 作为一中间层协议放置在m a c 层和妒层之间，这样一来，在不需要对其它协议 层做太大改动的情况下便可很好的执行w m r 协议。因此，通过图1 2 的软件结 构，w m r 能较好的工作于现有的无线标准( 如i e e e s 0 2 1 1 b , l e e e s 0 2 1 l e ) 和现 有的多种应用中。 1 2 3 无线m e s h 网络的优点【1 l 从以上介绍可以看出，无线m e s h 在组网与选路特征上与传统无线网络存在 着明显的区别。实际上，无线m e s h 更像是i n t e r n e t 网络的一种无线版本，由于节 点只和其临近节点通信，从一个节点发出的数据包将根据w m r 协议的配置逐跳 ( h o p ) 传递到目的节点。这种结构与传统点对多点网络结构相比具有较多的优势， 主要表现在以下几个方面： ( 1 ) 可靠性提高 提高网络可靠性的方法是让每个节点使用多条路径进行接续，以便链路出现 故障时不会影响整个网络。而在传统的点对多点网络中，节点的接入采用了星型 ( s t a r ) 结构，即多个节点首先接入到一个中心点，再由中心点接入到网络中。 这样一来，若其中某一节点出故障，特别是中心节点出现了故障，将会影响到整 个网络的正常工作，因而这种网络的可靠性得不到很好的保证。例如，在蜂窝移 动通信系统中，星型结构的中心便是移动交换中心( m s c ) ，位于周边的若干个 基站( b t s ) 首先接入到一个基站控制器( b c s ) 上，然后再通过b c s 连接到 m s c 上，若其中某一b t s 与b s c 之间的链路出现故障，则b t s 便无法接入到 m s c 。为提高网络的可靠性，目前的点对多点网络也采用了一些保护措施。如 m h s p ( m o n i t o r e dh o t s t a n d b yp r o t e c t i o n ) ，为主链路配置后备链路，此方法虽然 简单，但每条链路都需要配备有两个独立的链路和一个保护交换，而且同时只能 有一个信道用于业务的传送，大大减低了信道带宽的使用效率。而在无线m e s h 中，链路为网状结构，每个节点可使用的链路数大大增加，而每个网络节点都具 有链路功能，如果其中的某一条链路出现了故障，节点便可以自动转移到其他可 选链路进行接入，因此对网络的可靠性有了很大程度的提高。 ( 2 ) 碰撞减轻 无线m e s h 可以较大程度上减轻业务执行时碰撞现象的发生。无线m e s h 中提 供了多个可选路径，业务在执行过程中受路径碰撞的影响便会更低，而且无线 m e s h 中还提供了碰撞保护机制，那些未经认证的无线链路若能去执行m e s h 业务 而引起碰撞时，系统将自动对此碰撞与链路进行标识，并将在此链路上执行的业 务转移到可选链路中。另外，在无线m e s h 节点中的可选链路与本身链路的夹角 第一章绪论 5 通常为一钝角，甚至为相反方向，这为减轻链路间的干扰创造了条件，我们知道， 天气对无线信道会有一定的影响，如雨天会对无线链路造成一定的功率衰减，但 是天气的影响是局部的，有方向性的。通常同一方向的可选路由或可选链路处于 这种天气条件下的几率要大于方向相差较大的可选路由或链路，因而呈钝角关系 的路由或链路受到这种天气因素的影响便会大大降低，这也减轻了业务执行时发 生碰撞的可能性。 ( 3 ) 简化无线链路设计 与星型网络相比，无线m e s h 在无线链路的设计上也有所简化，主要体现在 两个方面：一是无线m e s h 的节点问呈网状或环状连接，相距较远的节点间通信 时的数据包将通过多个节点的转发，逐点传递到目的节点。但是在星型网络中， 较远节点的数据包通常是用一个较长链路连接到某一中心点，再由此中心点转发 此数据包。与点对多点链路相比，无线m e s h 链路的长度通常更短，因而无线m e s h 对天线传输距离与性能的要求便会大大降低，降低了天线的成本；二是无线链路 更短，所需的发射功率越低，降低了射频信号问的干扰，从而也减少了整个网络 的自干扰现象。 ( 4 ) 可测量性 与星型网络相比，无线m e s h 是一种对等网络，网络中的每个节点是对等的， 这样连接到一共同节点的链路数目就会减少，因而需要进行信道分配的无线链路 数目就会随之减少，增加了网络的可测量性。另外，对于网络带宽的配置可以通 过对接入点( a p ) 的配置来完成，而且还可以通过运行在节点和接入点上的无线 m e s h 路由( w m r ) 协议对不同业务进行带宽的匹配，实现不同业物间带宽的平 衡。因而与星型网络相比，无线m e s h 网络具有更好的可测量性。 ( 5 ) 维护简便 无线m e s h 简化了网络的维护与升级，如前所述，每个节点都有多条可选路 由，因而局部地区的升级与扩容将不会影响到整个网络的运行，方便网络的维护 与操作。 1 2 4 无线m e s h 网络的应用 无线m e s h 网络的应用主要集中在两个方面：传感器和骨干网。 ( 1 ) 传感器m e s h 传感器是一种构造相对简单，体积较小的装置，具有一个简单的处理器。它 经常用来处理一些数据，例如湿度，压力，温度和振动等，并把这些数据传递给 其它的传感器。由于体积小，所以他们一般没有用户界面，甚至可以被视为数据 传送器。传感器还可以嵌入到设备当中，对压力，流量和温度进行监控。 6无线m e s h 网络路由协议的研究 ( 2 ) 骨干m e s h 无线m e s h 网络的骨干一般是指网络中构成主要数据传输线路的那些高速链 路。传统上，骨干网是指用光纤( 以前是铜线) 将各个边缘网络相互连接起来。 在m e s h 中只需要有一个节点连接到有线网络上，所有的m e s h 节点都可以接入到 有线网络了。当然出于对冗余度和流量的考虑，可能会需要更多的节点与有线网 络相连。骨干m e s h 可以布置在室内也可以布置在室外，室外设置往往布置在街 灯上或者是建筑物外表面上有电力可用的地方。由于线路上m e s h 设备的出现， 每一个节点都能与其它节点进行联系，因而，很多户外系统就不仅仅起到数据回 程作用了，它们也可以包含集成的接入点供客户端使用。这种解决方案往往包含 两套无线电，其中i e e e s 0 2 1 1 a 作为回程用，i e e e s 0 2 1 l b g 给客户端用，这大大 减轻了回程和用户对流量的争夺问题。 1 2 5 无线m e s h 网络的发展现状 美国m e s hn e t w o r k s 公司已经开发了相关的无线硬件和智能路由软件，其构 建的无线m e s h 网络支持诸如手机和笔记本等移动终端，这些终端可以自由接入 或退出网络，当两个或更多终端离开网络范围时，还可以组成自己的微型网。 由于新颁布的i e e e s 0 2 1 6 a 标准中已经明确提出把无线m e s h 技术应用于宽 带无线接入领域，无线m e s h 网络作为一种新的宽带无线接入方式已经引起业界 的关注，它会对用于驻地用户宽带接入网络的d s l 技术和电缆技术带来很大的竞 争压力。很多公司已经开始将无线m e s h 技术用于宽带网络接入，并且相关的无 线路由器产品已经开始商用，如诺基亚公司推出的无线路由器可以安装在屋顶上， 其产品目前已经获得超过5 0 家运营商的青睐，他们将借此建立以用户为基础的高 速无线网络。另外，无线m e s h ，智能天线和超宽带技术的融合将更深刻影响无线 宽带接入的未来。 1 3 无线m e s h 网络中的主要研究课题 无线m e s h 网络在几个关键技术问题需要进一步研究解决。 ( 1 ) 天线技术 无线m e s h 宽带网络中一个重要的问题就是天线的使用，因为每个节点必须 和多个方向上的多个节点通信，很简单的一种方式就是采用全向天线，但是这样 覆盖范围有限，并会带来干扰，导致频谱利用率下降，网络容量减小，所以不建 议采用全向天线。美国s k yp i l o t 公司将智能天线技术应用于无线m e s h 网络，允 许频谱重复使用，从而大大提高了频谱的利用率，同时减小了干扰。在i e e e 8 0 2 1 6 a 第一章绪论 7 宽带无线接入标准中也建议把智能天线技术应用到无线m e s h 网络中。 ( 2 ) 路由选择技术 无线m e s h 宽带接入网络中另一个很重要的问题就是路由选择，例如从节点 a 到节点b ，可以经过不同的用户站中转，存在多条路径，于是选择哪条路径就 成为一个关键的问题，这将直接影响系统性能。而且，当节点增加或是减少时， 无线m e s h 网络的拓扑结构将会发生变化，路由选择问题变得更加复杂，采用无 线m e s h 还会带来“隐藏终端”问题，这些都需要进一步研究解决。实际上，无 线m e s h 技术可以看作是自组网络技术的简化版本，所以可参考自组织网络中相 应的解决方法来解决无线m e s h 宽带接入网络中的这些问题。 ( 3 ) 动态带宽分配技术 宽带无线接入系统的频谱资源有限，因此必须使信道资源尽可能被充分利用。 在i e e e s 0 2 1 6 标准中规定的点到多点( p m p ) 宽带无线接入网络中采用了动态按 需时分多址d a m a _ t d m a 方式，在这种网络中资源的管理和分配由基站负责。 而在i e e e 8 0 2 1 6 a 标准中规定，对于基于无线m e s h 技术的宽带接入网络，带宽 的分配可以采用集中调度方式，或者采用分布调度方式。如果采用集中调度方式， 由m e s hb s 节点收集所有m e s hs s 节点的资源请求信息，分别为它们分配一定数 量的带宽资源。如果采用分布调度方式，包括m e s hb s 和m e s hs s 在内的所有节 点都应该相互协调，充分利用资源。任何一个节点发送数据时，不能和两跳以内 的临近区域的其它节点发送的数据产生碰撞。 1 4 本文主要内容 本文主要研究无线m e s h 网络的路由问题，主要包括以下几个方面： n ) 对当前常见几种路由协议的研究。 c 2 ) 重点研究动态源路由协议的原理，实现过程以及近几年来对其作的一些改进。 ( 3 ) 提出动态源路由协议的改进协议基于信誉度，可用带宽和最小跳数的多 量度自适应a d h o e 路由协议( f a b m h r ) 。 全文分为五章，具体安排如下： 第一章是绪论部分，介绍了无线m e s h 网络的结构，特点和应用。并提出它 的发展现状以及关键技术。 第二章是对无线m e s h 网络中的路由协议进行研究。主要以a dh o e 网络的路 由协议为参考。 第三章主要研究了动态源路由协议( d s r ) 。 第四章研究了基于信誉度，可用带宽和最小跳数的多量度自适应a d h o e 路由 协议( f a b m h r ) 。 8 无线m e s h 网络路由协议的研究 第五章是结束语。 最后是致谢和参考文献。 第二章无线m e s h 网络路由协议的分析 9 第二章无线m e s h 网络路由协议的分析 在第一章中我们提到无线m e s h 网络路由协议可以借鉴a dh o e 网络的路由协 议。a dh o c 网络路由协议从大的类别上不外乎分为三种：一种是先验式路由协议， 也叫表驱动式路由协议；一种是反应式路由协议，也叫源驱动按需路由协议；最 后一种就是二者的混合，叫混合试路由协议。本章对各种类型协议和其中具有代 表性的协议进行分析。 2 1 无线m e s h 网络的路由 第一章中讲到我们所熟知的i n t e r a c t 网络的构架就已经是一个m e s h 网络，那 基于i n t e r a c t 的路由选择协议是否适合无线m e s h 网络呢? 由于无线m e s h 网络的多跳性，所以每个节点都要有报文转发功能，这就要 求节点实现合适的路由协议。无线m e s h 网络的节点是可以自由移动的，网络拓 扑结构会发生变化，这样传统的基于i n t e r a c t 的路由选择协议，如距离矢量方法 的r i p 6 l 和链路连接状态方法的o s p f n 等不适合在无线m e s h 网络中使用，原因 如下： ( 1 ) 无线传输信道与有线传输信道具有不同的特性。自组网中主机间的无线信道 可能存在单向信道，常规路由协议设计中常常没有考虑这个问题或者必须以双向 链路作为工作的前提假设，由此计算出来的路由可能不能准确反映无线m e s h 网 络的拓扑结构，也没有考虑单向信道的存在。 ( 2 ) 无线信道的广播特性产生了很多冗余链路。由于在无线m e s h 网络中一个主机 的广播可能覆盖周围的数个主机，在常规路由协议看来，这些链路是冗余的。因 为在有线网络环境中，两个相邻的网络之间通常只会用一个或少数几个路由器进 行连接，冗余的链路需要常规路由协议发送更多更大的路由更新报文。 ( 3 ) 周期性的广播路由更新报文会消耗大量的网络带宽。无论哪种常规路由协议， 都需要路由器定期发送路由更新报文，即使网络的拓扑结构没有发生变化也是如 此，因为路由器之间通过交换路由报文进行邻居“活动”状态监测。这将对有限 的无线信道带宽带来更多的压力。 ( 4 ) 周期性的广播路由更新报文会消耗大量的主机能源。无线m e s h 网络中的主机 每次发送分组都会消耗主机能源，接收分组相对发送分组消耗的能源要少，但是 由于经常需要接收分组，使得主机很难进入“休眠”节能状态。此外，某些常规 路由协议需要的复杂计算使得c p u 处于很高的负载下，这也同样消耗了大量的能 1 0无线m e s h 网络路由协议的研究 源。这将对有限的主机能源带来更多的压力。 ( 5 ) 常规路由协议不适应动态变化的网络拓扑结构。常规路由协议是为有线固定 网络设计的，它们的网络拓扑结构通常是较为固定的，不会出现大的网络拓扑结 构变化，而无线m e s h 网络的网络拓扑结构会动态变化。常规路由协议通常是没 有考虑这一点的。产生的后果就是在无线m e s h 网络环境中，当网络拓扑结构变 化后，常规路由协议需要花费很长的时间才能达到收敛状态，而此时拓扑结构可 能在达到收敛状态之前又发生了变化。所以可能造成这样的一种情况：无线m e s h 网络主机在花费了很高的代价( 如网络带宽，能源，c p u 资源等) 之后得到了网 络的临时拓扑结构，而处于动态变化的拓扑结构导致了这个结果中的大部分内容 变得陈旧，协议状态始终处于不收敛状态。 正是由于传统的基于固定网络的路由选择协议无法适应无线网络拓扑快速变 化的需求，所以有必要设计专用于无线m e s h 网络的路由选择协议。 一个好的无线m e s h 网络路由协议同a dh o c 网络的一样，应当满足以下要求： ( 1 ) 分布式运行方式；( 2 ) 提供无环路路由；( 3 ) 按需运行协议操作；( 4 ) 安全 性；( 5 ) 提供设备“睡眠”操作特性；( 6 ) 对单向信道的支持。 无线m e s h 网络路由协议的目标是快速，准确，高效，可扩展性好。快速指 的是查找路由的时间要尽量的短，减少引入的额外时延；准确指路由协议要适应 网络拓扑的变化，提供准确的路由信息；高效的含义比较复杂：其一指提供最佳 路由，其二指维护路由的控制信息尽量少，以降低路由协议的开销，其三指路由 协议应能根据网络的拥塞状况和业务的类型选择路由，避免拥塞并提供q o s 保证； 可扩展性指路由协议要能够适应网络规模增长的需要。 2 2 1 简介 2 2 先验式路由协议 先验式路由协议又被称为表驱动( t a b l e d r i v e n ) 路由选择协浏”，是一种基 于表格的路由协议。在这种协议中，每个节点维护一张或多张表格，这些表格包 含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时，节 点在网络中发表路由更新消息。收到更新消息的的节点更新自己的表格，以维护 一致的，及时的，准确地路由信息。不同的先验式路由协议的区别在于拓扑更新 信息在网络中传输的方式和需要存储的表的类型。先验式路由协议不断的检测网 络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网 络的拓扑结构。源节点一旦需要发送报文，可以立即得到到达目的节点的路由。 图2 1 是现有的部分先验式路由协议1 1 0 j 。 第二章无线m e s h 网络路由协议的分析 1 1 困 ! 崮崮崮崮崮 卤崮 图2 1 先验式路由选择协议 d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 是一种无环路距离矢量路由 协议1 1 l l ，它是传统的b e l l m a n f o r d 路由协议的改进，下面将专门对d s d v 协议进 行分析。c g s r ( c l u s t e rg a t e w a ys w i t c hr o u t i n gp r o t o c 0 1 ) 是d s d v 的扩充版i l “， 它用于分级网络。w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 也是一种距离矢量路由协议l l ”， 每个节点包括距离表，路由表，链路权值表和消息重传表四张表。g s r ( g 1 0 b a ls t a t e r o u t i n g ) 是一种链路连接状态路由协议1 1 4 1 ，每个节点存贮邻居列表，拓扑表，下 一跳表和距离表四张表格。f s r ( f i s h e y es t a t er o u t i n g ) 对g s r 进行了改进1 ”j ，它 的更新信息包含临近节点的信息，显著的减小了更新信息的大小。h s r ( h i e r a r c h i c a ls t a t er o u t i n g ) 是一种用于分级网络的路由协议1 1 6 1 。高级的节点保 存它所有子孙节点的位置信息。沿从最高节点的根节点到最低节点的叶节点的路 径为节点分配逻辑序列地址。序列地址指示了节点的位置，可以简单的利用序列 地址进行寻址。z h l s ( z o n e b a s e dh i e r a r c h i c a ll i n l 【s t a t e ) 路由协议是一种基于 区域的路由协议旧。网络被分割成不重叠的区域以减少路由控制报文的个数，降 低路由开销。并定义了两级拓扑结构：节点级和区域级。节点级拓扑指一个区域 内节点的物理连接。区域级拓扑指各个区域如何相互连接。网络中存在两种链路 连接状态报文；节点链路状态报文和区域链路状态报文。节点链路状态报文包括 节点的邻居信息，只在区域内传播。区域链路状态报文包含区域间的链路状态， 在全网内传播。 2 2 2d s d v 协议 目的节点排序距离向量路由协议d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c e v e c t o rr o u t m g ) 是一种基于经典的b e l l m a n f o r d 算法【卅的表驱动路由协议，它通 过对路由编号等措施避免了路由环路的发生，并在路径自由度方面做了一定的改 善。 d s d v 的基本原理是：每一个节点维持一个到其它节点的路由表，表的内容 为路由的“下一跳”节点。d s d v 的创新之处是为每一条路由设置一个序列号， 1 2 无线m e s h 网络路由协议的研究 序列号大的路由为优选路由，序列号相同时，跳数少的路由为优选路由。正常情 况下，节点广播的序列号是单调递增的偶数，当节点b 发现到节点d 的路由( 路 由序列号为s ) 中断后，节电b 就广播一个路由信息，告知该路由的序列号变为 s + l ，并把跳数设为无穷大，这样，任何一个通过b 发送信息到节点a 的路由表 中就包括一个无穷大的距离，这一过程直道a 收到一个到达d 的有效路由( 路由 序列号为s + 1 + 1 ) 为止。 在此方案中，网络中所有的移动终端都建立一个路由表，包括所有的目标节 点和到达各个目标节点的跳进次数( 或标识距离矢量的路径矩阵) 。每个登陆条目 都有一个由目标节点设定的序列号。序列号使移动终端可以区分当前有效路由路 径和已过时的路由路径。路由表周期性的作全网更新而产生的大量路由信息传递， 减小网络路由开销，可以采用两种路由更新方式。第一种是全清除方式( f u l l d u m p ) ，即通过多个网络协议数据单元( n p d u ：n e t w o r kp r o t o c o ld a t au n i t ) 将 路由更新消息在全网中传输。如果网络内终端出现移动，则产生的新路由分组信 息不定期的传达至网络内所有终端。第二种方式是部分更新方式( i n c r e m e n t a l ) ， 或增量更新方式，即在最后一次全清除传输后，只传输那些涉及变化了的路由信 息，这些信息通常被放置在一个标准n p d u 里，从而减少路由信息的传输量。在 部分更新方式中，移动终端可以增加另外一个附加的表来存储路由更新信息。 新路由信息的广播信息包含目标节点的地址，到每个目标节点的跳进次数， 接收信息的序列号，以及独有的广播序列号。新路由信息使用最新的序列号。如 果两次更新具有相同的序列号，则具有最小距离矢量阵的路由具有优先权，因为 它代表最短路径( 或最少跳进次数) 。通常，从源节点到目的节点可能有很多条路 径，如图2 2 所示，但只有一条是最好的，比如说1 - 2 5 ，一旦确定了这一点，从 1 到5 的信息传递就按1 2 5 的路径走。在最佳路由路径的确定过程中，移动终端 跟踪不同路由路径的时间，最佳路由路径就是时间最短的路径。在找到最侍路径 之前，该时间呈收敛性涨落。一旦路径确定，这些信息就存放到每个终端里，直 道获得新的路径。 节点2 图2 2 节点1 到节点5 的路由 第二章无线m e s h 网络路由协议的分析 1 3 2 3 1 简介 2 3 反应式路由协议 反应式路由选择协议，又称为源启动按需路由( s o u r c ei n i t i a l e do n d e m a n d r o u t i n g ) 1 1 8 1 ，是一种当需要时才查找路由的路由选择方式。节点并不保存及时准 确的路由信息。当源节点要向目的节点发送报文时，源节点在网络中发起路由查 找过程，找到相应的路由后，才开始发送报文，为了提高效率，节点可以将找到 的路由保存在缓存中供后续发送使用。 图2 3 是现有的部分反应式路由协议。 圈 。一j 。 一一+ 一一 圆圈圆国圄 ， 回 图2 3 反应式路由选择协议 d s r ( d y n a m i cs o u r c er o u t i n gp r o t o c 0 1 ) 是一种动态源路由选择协议，齐篇 论文就是基于d s r 协议的改进，在稍后一章将对其进行详细描述。a o d v ( a dh o c o n d e m a n dd i s t a n c ev e c t o r r o u t i n g ) 是d s d v 的改进型( 1 9 1 ，通过按需路由来降低 d s d v 中控制报文的数目，从而提高系统效率。t o r a ( t e m p o r a l l yo r d e r e dr o u t i n g a l g o r i t h m ) 是一个有效的，可扩展性好的反应式路由协谢2 0 1 ，它可以找到从源节 ，直到目的茁点的务舞躐峨, m r ( a s s o c i a t i v i t y b a s e d r o u t i n g ) 中路由的选择以节 点间的连接稳定性作为度量依据【2 1 】。s s r ( s i g n a ls t a b i l i t yr o u t i n g ) 中路由的选 择以节点问的信号强度作为度量依据 2 2 1 。c b r p ( c l u s t e rb a s e dr o u t i n gp r o t o c 0 1 ) 被用于单频两级网络中，它也使用源节点发起路由查找，与a o d v 具有类似的 请求回应方式。为了减少报文丢弃率，引入了中间节点本地修复机制。 下面分析一个具代表性的反应式路由协议a o d v 协议，d s r 协议也是一 个代表性的协议，我们将在下一章重点研究。 2 3 2a o d v 协议 专用按需距离向量路由协议a o d v ( a dh o co n - d e m a n dd i s t a n c ev e c t o r r o u t i n g ) 1 1 9 j 是建立在d s d v 算法之上的，但是它并不维系一个路由表，而是在 1 4 无线m e s h 网络路由协议的研究 需要的时候才启动路由选择过程，因此大大地降低了路由维持的开销。事实上它 是d s r 和d s d v 的组合，它借用了d s r 的路由发现和路由维持机制，利用了 d s d v 的按跳( h o pb yh o p ) 路由，顺序编号( s e p ) 和周期更新( 只在路由维持 阶段) 的机制。 为了查找到达目的节点的路由，源节点广播一个路由请求信息。它的邻居收 到广播消息后再次广播，直到请求消息到达目的节点或到达知道到达目的节点路 由的中间节点。目的节点或知道到达目的节点路由的中间节点沿原来的路由向源 节点返回存在路由响应消息。源节点收到响应后，它就可以得到到达目的节点的 路由。a o d v 还包括路由维护部分，实现当路径上中间节点移动后对缓存中路由 的修改和删除。 a o d v 分为路由建立过程和路由维护过程两个阶段。其路由建立过程与d s r 基本一致，是基于一种泛洪路由( f l o o d i n gr o u t i n g ) 的方式。网络中的节点在接 收到路径建立报文后，根据自己是否目的节点，是否具有能够到达目的节点的有 效缓存，或是应答路径建立报文，或是继续转发路由建立报文。但是a o d v 协议 采用节点路由方式，而不是类似于d s r 的源路由，其数据分组报文不需要央带路 由的信息，这使得每个接收到路径建立报文的节点必须根据报文上一次转发节点 的地址记录下到源节点的逆向路径( a o d v 中假设网络是对称的) ，以便为之后 的应答报文提供路由。应答报文经过节点时( 这表明存在一条从源节点到目的节 点的路径经过本节点) ，记录下本节点到目的节点的路径，以便为将来数据分组报 文的到来提供路由服务。 一个有意