（通信与信息系统专业论文）基于ieee80211b的无线mesh网络路由的设计与研究.pdf

捅要 无线m e s h 网络是一种新型的宽带无线网络结构，与传统无线网络不同，它基 于多跳路由、对等网络技术等新技术。相对传统单跳无线接入，他能够以邻居节 点相互接力的方式接入i n t e m e t ，弥补了传统网络可伸缩性低和健壮性差的缺点具 有很好的扩展性和自适应性。是一种新型的解决“最后一英里问题的分布式网 络。 文章首先介绍了无线m e s h 网络的结构，发展及其应用。然后分析现有几种常 见无线a d h o c 网络的路由协议。接着介绍了一下l i u n x 系统下编写路由程序要用 到的关键元素，为下面章节设计路由协议做好准备。第四章则详细分析了基于 a o d v 路由协议的m e s h 路由的实现过程：解决了如何根据l i n u x 系统特点对协 议进行模块划分，分块后的l i n u x 内核模块和用户守护进程( d a e m o n ) 如何配合 工作，以及具体的a o d v 协议定义的各个功能的实现等问题，并提出利用i p 隧 道封装方式来实现网关功能的方法。通过实验分析，验证了采用这种方法实现无 线m e s h 路由的可行性。文章结尾对m e s h 的发展和系统的改进做了进一步的讨论， 提出m e s h 路由以后可以改进的方向。 关键词：lin u x 无线m e s h 路由网关实现 a b s t r a c t w i r e l e s sm e s hn e t w o r ki san e wa r c h i t e c t u r eo fw i r e l e s sb r o a d b a n dn e t w o r k , u n l i k eo t h e rt r a d i t i o n a lw i r e l e s sn e t w o r k ，i tb a s e so nm u l t i - h o p ，p e e rt op e e ra n do t h e r n e wt e c h n o l o g y i nc o n t r a s tt ot r a d i t i o n a ls i n g l e - h o pw i r e l e s sa c c e s s ，i tc a l la c c e s s i n t e r n e tv i an e i g h b o u rn o d er e l a y i n g ，a n dc o m p e s a t e st h e l o we x p a n s i b i l i t ya n d r o b u s t n e s so ft r a d i t i o n a ln e t w o r k f a m o u sf o ri t se x p a n s i b i l i t ya n df l e x i b i l i t y ，i ti sa n e wd i s t r i b u t e dn e t w o r kw h i c hs o l v e d ”t h el a s tm i l e ”a c c e s sp r o b l e m t h et h e s i sf i r s t l yd oai n t r o d u c t i o na b o u tt h ea r c h i t e c t u r e ，d e v e l o p m e n t a n d a p p l i c a t i o no fw i r e l e s sm e s h n e t w o r k m a k ea n a l y s e so ns o m ef a m i l i a rw i r e l e s sa d h o e r o u t i n gp r o t o c 0 1 t h e nw ei n t r o d u c ei nt h ek e ye l e m e n t sf o rc o d i n gr o u t i n gp r o g r a m u n d e rl i n u xs y s t e m o nt h ef o u r t hc h a p t e rt h ed e t a i l e dm e s hr o u t i n gp r o t o c o lb a s e do n a o d vi sp r e s e n t e d i tc o v e r sh o w t od i v i d et h em o d u l et o 做f o rl i n u xs y s t e m ，h o wt o c o o p e r a t el i n u xk e r n e l m o d u l ea n du s e rd a e m o n ，h o wt oi m p l e m e n tt h em a t e r i a l f u n c t i o n sa o d v p r o t o c o ld e f i n e d a n dp u t sf o r w a r dam e s hi n t e r n e tg a t e w a ym e t h o d b yi pt u n n e le n c a p s u l i n g a c c o r d i n gt oe x p e r i e n c er e s u l t ，t h i sm e t h o di s s u c c e s s f u l a t t h ee n do ft h et h e s i sw ed oaf u r t h e rd i s c u s so nm e s hn e t w o r kd e v e l o p m e n t ，g i v es o m e t i p si nf u t u r ei m p r o v e m e n t k e y w o r d s ：l i n u xw i r e l e s sm e s hr o u t i n gg a t e w a yi m p l e m e n t 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 j 本人签名：三药互l 一 日期2 丛l 上三l 西安电子科技大学+ 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：瑾，塑 导师签名： 日期丛乒也l 日期塑乒卫l 第一章绪论 第一章绪论 伴随着计算机和通信网络技术的不断进步，以及人们对移动通信的需求越来 越强，许多的新技术新产品不断涌现。现在广泛使用的无线局域网技术( w l a n ) 就吐人们体验到了摆脱线缆束缚带来的好处和便利。无线局域网的用户具有可移 动性，可以在各接入点( a p ) 问漫游，而目叮以达到较高的数据传输速率。对于 电信运营商而占，w l a n 作为有线网络的延伸和补充，是一种价格经济，架设简 便的宽带接入手段。然而，传统w l a n 网络只能实现客户端到a p 的单跳接入方 式。而w l a n 的另一种组网方式- - a d h o e 模式，组成的多跳网络却是一个封 闭自组织网络。如何能够在使用现有设备的条件下实现移动节点互连和多跳 i n t e m e t 接入呢? 这证是无线m e s h 网络要解决的问题。 1 1 无线m e s h 网络研究概述 随着网络技术的进步，无线网络接入技术也在酝酿着新的突破。传统的基站 方案由于其接入范围有限，部署配置不够灵活，i f 在面临越来越多的挑战。而无 线m e s hf 目( w i r e l e s s m e s h n e t w o r k s 简称w m n s ) 技术证是其中一种。 制：謦 ，c ： w t p i t ：ju x hr t l w j l k 目h s l v s l e b “ 僦k l l a u lh n hh c l w e e l i # ce ，su m b l 0 c i hr i l k h l tc y er * ra 【t c i in t i _ o | - w i t hc * 10 t i e r r v u eo l l l tr 【l i e 日i5a e a l u d i 口w a 儿ir t a c k i n g i h e 1 w m 图1i 无线m e s h 网络拓扑 无线m e s h 网( 圈l1 ) 是一种多跳、具有自组织和自愈特点的宽带无线网络 结构，即一种高容量、高速率的分布式网络。与基站网络不同，无线m e s h 网可 以看成是单跳网络和移动a d - h o c 网络( 多跳) 的融合，且发挥了两者的优势。可 以为无线服务提供商( w i s p ) 提供热点地区的服务覆盖的延伸，向移动用户提供 高性能的i n t e m e t 接入服务。它的基本网络出m e s h 路由器( m e s hr o u t e r ) 和m e s h 熨 ；j了一 b _ 翼 哆，i - ，|铲警 茵一 、0 i i 帮 r 蟹 诤 |。 妒 m 扣 黼 勰 三 基于i e e e 8 0 2 1 l b 的无线m e s h 网络路由的设计与研究 客户端( m e s hc l i e n t s ) 组成，基于多跳路由、对等网络技术的新型网络结构，具有 移动宽带的特性，同时它本身可以动态地不断扩展，自组网、自管理，自动修复、 自我平衡。在网络中，m e s h 路由器是构成无线网状网的骨干，提供m e s h 客户端 和传统客户端( c o n v e n t i o n a lc l i e n t s ) 对网络的访问服务。另外，通过m e s h 路由器可 以实现无线网状网与互联网( i n t e m e t ) 、蜂窝网( c e l l u l a r ) 、i e e e 8 0 2 1 1 、i e e e 8 0 2 1 5 、 i e e e 8 0 2 1 6 和传感器网络等网络的综合桥接功能，实现多种设备互通。无线m e s h 网能够极大的改善无线局域网( w l a n s ) 、无线个域网( w p a n s ) 和无线城域网 ( w m a n s ) 的性能，能够对很大的区域像社区，校园，城市等提供无线服务。它具 有一下特点： ， ， 价格：每个m e s h 节点既是客户端又是中继器，由此减少了无线设备的投 入。 易用性：如果你有一个预装了m e s h 软件的带有8 0 2 1 l b 儋的主机，配置将 会是非常的简单。因为路由是动态配置的，我们只需将主机接上天线，放入网络 中即可。 组织和归属：m e s h 的分散特点决定了它的所有权也是公共的。 网络健壮性：在环境改变或一些节点失效时仍然具有强大的稳定性。 工作环境：m e s h 硬件可以是很小，无噪音，可以紧密封装，这使得它可以 在户外和室内都能正常工作。 目前，国内外的许多通信厂商都在进行m e s h 协议和设备的研发。例如 l o c u s t w o r l d 公司的m e s hb o x ，加拿大北电网络的o s p f m e s h 等等。对m e s h 的研 究无论是在科研上还是在商业上都是很有意义的。 尽管无线m e s h 网络的性能如此突出，然而在网络体系的各层研究中仍有很多 问题有待解决，如实现方式，网络容量，网络各层协议设计等问题。本文在对无 线m e s h 网原理与结构做了简单的分析，主要对无线m e s h 网路由协议设计与l i n u x 下实现进行详细探讨和研究。 1 2i e e e 8 0 2 1l b 特点及其m e s h 网适用性 i e e e 8 0 2 1 1 b 协议是第一代无线局域网标准之一，在目前的i e e e 8 0 2 1 1 家族 中它的产品普及率最高。 i e e e 8 0 2 1 1 b 使用开放的2 4 g h z 频段作为传输频段，物理层调制解调方式为 补码键控( c c k ) 编码的直接序列扩频( d s s ) ，最大数据传输速率为1 1 m b p s ， 无需直线传播。在实际使用中的传输速率大约在5 m b p s 左右，与普通的1 0 b a s e - t 规格有线局域网速度大致相当。它在传输中使用动态速率转换，当信道情况变差 时，可将数据传输速率降低为5 5 m b p s 、2 m b p s 和1 m b p s ，提高传输。且当工作 第一章绪论 在2 m b p s 和1 m b p s 速率时可向下兼容i e e e 8 0 2 1 1 。i e e e 8 0 2 1 1 b 的使用范围在室 外为3 0 0 米，在办公环境中则最长为1 0 0 米。使用与以太网类似的连接协议和数 据包确认，来提供可靠的数据传送和网络带宽的有效使用。 与i e e e8 0 2 3 有线局域网协议相比，i e e e8 0 2 1 1 b 除了采用无线介质取代线 缆进行传输外，在数据链路层协议也有所改进。由于在无线网络中冲突检测较困 难，i e e e 8 0 2 1l b 媒体访问控f 1 i j ( m a c ) 层采用避免冲突( c o l l i d ea v o i d a n c e ) 协议， 而不是冲突检测( c o l l i d ed e t e c t i o n ) 。c s m a c a 通信方式将时间域的划分与帧格 式紧密联系起来，保证某一时刻只有一个站点发送，实现了网络系统的集中控制。 因传输介质不同，c s m a c d 与c s m 刖c a 的检测方式也不同。c s m c d 通过 电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化； 而c s m a c a 采用能量检澳t j ( e d ) 、载波检n ( c s ) 和能量载波混合检测三种检测信 道空闲的方式。一方面，通过载波侦听( c a r d e rs e n s e ) ，查看介质是否空闲；另 一方面，通过避免冲撞( c o l l i d e a v o i d a n c e ) ，通过随机的时间等待，使信号冲突发 生的概率减到最小，当介质被侦听到空闲时，优先发送。通过c s m a c a 协议能 够减少数据的传输碰撞和重试发送，防止各站点无序地争用信道。另外， i e e e 8 0 2 1 l b 的m a c 层还提供安全服务、m s d u 重新排序服务和数据服务等服 务，以增加无线信道下数据传输的稳定性和安全性。 无线局域网的拓扑结构主要有两种：一种是无中心的对等网络，通常称a d h o e 网络，要求网络中的任意两个移动节点均可直接通信。一般来说，要实现移动节 点之间的多跳通信，都需要运行a d h o e 路由协议进行支持，否则只能是在单个移 动节点的覆盖范围内通信。这种拓扑的优点是网络抗毁性好，建网容易且费用较 低。但是网中移动节点数量过多，信道竞争将成为网络性能的瓶颈。该网络中的 路由信息可能会占据大部分的有效通信，从而降低网络的整体效率。另一种是有 中心的i n f r a s t r u c t u r e 网络，它要求网络中一个网络节点充当中心接入点，所有移 动节点对网络的访问都由它控制。有中心的网络拓扑结构的弱点是抗毁性差，中 心站点的故障容易导致整个网络瘫痪。此外中心站点的引入，也就在一定程度上 增加了网络成本。 无线m e s h 网对无线设备要求如下： 1 m e s h 网络节点收发器的功耗要足够低。m e s h 网是多跳系统，传输距离适中， 节点数量多，整个网络功耗要控制在一定数量以下，其节点收发器功耗必须足够 低。i e e e 8 0 2 1 1 中采用了p s m 协议作为节能模式，使通信中的无关节点能够进 入睡眠，在一定程度上降低了设备功耗。 2 组网能力强，网络容量大。由于m e s h 网节点数量众多，要形成m e s h 拓扑 结构，节点设备必须具备相当的组网能力。i e e e 8 0 2 1 1 b 采用c s m a c a 的多址 方式，理论上能支持任意多的节点，且不需要预先分配。节点间可以以a d h o c 模 3 一 一4 基于i e e e 8 0 2 1 1 b 的无线m e s h 网络路由的设计与研究 式组成自组织网络，有很好组网能力。 3 组网成本低。一种技术是否具有良好的应用前景，成本高低是能否被客户和 市场接受的重要因素。目前i e e e 8 0 2 1 1 b 设备已经具有很高的普及率，且价格低 廉，具有很大的用户群。 4 提供较高的数据传输数率，以支持多媒体数据流的传输。i e e e 8 0 2 1 1 b 最大 支持11 m b p s 的数据率，可以满足大多通信需求。 综合上面所述，采用i e e e 8 0 2 1 l b 设备作为无线m e s h 网的物理层设备，有其 合理性。目前任务组i e e e 8 0 2 1 1 s 就在进行基于8 0 2 1 1 的m e s h 网络标准的制定。 1 3 论文内容安排和主要研究结果 本论文的从对无线m e s h 网络的介绍分析入手，致力于基于a o d v 协议的 m e s h 路由设计及其在l i n u x 系统中的实现。 论文的主要工作和内容安排如下：第二章分析a o d v 协议的主要内容以及如 何应用于m e s h 网络，第三章介绍l i n u x 内核的路由表操作，和往内核中加入模 块的相关知识。第四章介绍具体实现流程以及其中一些关键点，并通过实验分析 验证协议设计的合理与有效性。 本论文的研究在于在现有的i e e e 8 0 2 1 1 b 无线局域网上实现无线m e s h 路由， 通过在移动主机和接入点上运行路由程序，移动主机能够以m e s h 的方式到达网 关节点，进而接入i n t e m e t 。 第二章m e s h 中的路由算法 第二章m e s h 中的路由算法 2 1 无线网络路由协议分类 作为一种无线网络接入路由协议，m e s h 网络的路由应能够实现以下3 个部分 基本功能：路由发现，路由维持以及网关i n t e r a c t 接入运作。而常见的a d h o e 路 由算法往往缺乏对网关的支持。所以，m e s h 路由应该是a d h o c 路由协议和网关 功能的合二为一。 一般来说，常见的路由协议可以分成两大类： 1 先验式路由( p r o a c t i v er o u t i n g p r o t o c 0 1 ) 顾名思义，就是在发包之前已先 进行过网络路由表的建立维护，上层数据包发送时直接查找路由表就可以确定路 径了。每个移动节点每隔一段固定时间就会发送一些路径相关信息，各个移动节 点就依据搜集进来的信息去改变自己的路由表，常见的距离矢量路由就属于这一 类。先验式路由可以让每个送出去的封包立刻得知到达目的地的路径，不会有任 何的d e l a y 。但是这种路由协议必须周期性的去广播讯息，所以相当的浪费无线网 络的频宽与m o b i l en o d e 的电源，但是如果要降低广播所造成大量频宽的消耗，就 要拉长每次广播的间隔时间，这又将会造成r o u t i n gt a b l e 不能正确反应网络拓朴 的变化。 2 反应式路由( r e a c t i v er o u t i n gp r o t o c 0 1 ) ：移动节点想发送数据包时，如果 找不到到达目的地的路由表项，才会开始路由发现运作，比如d y n a m i cs o u r c e r o u t i n g ( d s r ) 、z o n er o u t i n gp r o t o c o l 、a dh o co n - d e m a n dd i s t a n c e v e c t o r r o u t i n g ( a o d v ) 等就属于这一类。这类协议的最大好处就是带宽的使用量较小， 只是某一个移动节点欲送封包时未必能从路由表找到路径，所以平均延迟时间较 长。 m e s h 网络是a d h o c 网络的进化和延伸，同样要求在有限链路开销的情况下正 确查找网络路由，所以反应式路由更能够适应m e s h 网络的运作。 2 2 1d s d v 协议 2 2 常见无线路由算法分析 目的节点序序列号距离向量路由协议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 5 一 鱼基于i e e e 8 0 2 1 l b 的无线m e s h 网络路由的设计与研究 v e c t o r r o u t i n g ) 是一种基于经典的b e l l m a n f o r d 算法的表驱动路由的协议，它通过 对路由编号等措施避免了路由环路的发生，并在路径自由度方面做了一定改善。 d s d v 的基本原理是：每一个节点维持一个到其它节点的路由表，表的内容为目的 节点、跳数、路由的下一跳节点和目的节点序号。d s d v 创新之处是为每一条路 由设置一个目的序列号( 由e 1 的节点生成) ，序列号大的路由为优选路由，序列号 相同时，跳数少的路由为优选路由。 正常情况下，节点广播的序列号是单调递增的偶数，当节点b 发现到节点d 的路由( 路由序列号为s ) 中断后，节点b 就广播一个路由信息，告知该路由的序列 号变为s + l ，并把跳数设为无穷大，这样，任何一个通过b 发送信息的节点a 的 路由表中就包括一个无穷大的距离，这一过程直到a 收到一个到达d 的有效路由 ( 路由序列号为s + 1 + 1 ) 为止。在此方案中，网络内所有的移动终端都建立一个路 由表，包括所有的目标节点和到达各个目标节点的跳进次数( 或标识距离矢量的路 径矩阵) 。每个登陆条目都有一个由目标节点设定的序列号。序列号使移动终端可 以区分当前有效路由路径和已过时的路由路径。路由表周期性地做全网更新以维 护全网的通信有效性。 通常，为了减少由于路由表更新而产生的大量路由信息传递，减少网络路由 开销，可以采用两种路由更新方式。第一种是全清除方式( f u l ld u m p ) ，即通过多 个网络协议数据单元( 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 2d s r 协议 d s r ( d y n a m i cs o u r c er o u t i n g ) 是基于源路由思想的一种协议。在该协议中， 移动节点需要维持包含该节点获得的源路由的路由缓存。随着节点学习到新的路 第二章m e s h 中的路由算法 由，路由缓存中的内容不断的更新。d s r 协议包含两个主要阶段：路由发现和路由 维持。源节点要向目的节点发送数据包的时候，源节点查找其路由缓存来查看其 是否已经有到目的节点的路由。如果发现了到目的节点的未过期的路由，源节点 将利用该路由来发送数据包。如果源节点在其路由缓存中没有找到这样的路由， 那么它将通过广播路由请求( r r e q ) 包发起一个路由发现过程。这个路由请求 包包含了源节点和目的节点的地址以及一个唯一的标识号。每个中间节点检查是 否自身有到目的节点的路由，如果没有，中间节点将自身的地址添加到包的路由 记录中并将请求包发送给其邻居节点。为了限制路由请求传播的数目，一个节点 仅仅在其没有见到过这个请求包且其地址不在该包的路由记录中的时候处理这个 路由请求包。当请求包到达了目的节点或者中间节点有到目的节点的路由信息的 时候，将会产生路由应答( r r e p ) 。 随着路由请求包在网路中的传播，如果路由应答是由目的节点产生的，那么 目的节点将路由请求包中的路由记录放在路由应答包中。另一方面，如果产生路 由应答的是中间节点，那么中间节点将其到目的节点的缓存路由添加到路由请求 包的路由记录中并将其放到路由应答包中。要发送路由应答包，应答节点必须要 有到源节点的路由，如果在其路由缓存中有一条这样的路由，可以应用该路由进 行应答。如果链路是双向对称的，可以将路由记录反转过来使用。如果链路不是 双向对称的，节点可以发起到源节点的路由发现过程，并在新的路由请求包中包 含路由应答。 d s r 协议应用两种类型的包实现路由维持：路由错误( r e r r ) 包和确认 ( a c k n o w l e d g m e n t ) 包。当节点在数据链路层遇到致命的传输问题的时候，其产 生一个路由错误包。当节点收到路由错误包时，会将其路由缓存中的错误“跳 去掉。所有的包含错误“跳 的路由将会被删除。确认包被用来路由链路的正确 运作。也就是节点获知“下一跳”节点沿路由发送了数据包的被动确认。在d s r 协议中，节点不需要周期性的发送控制报文，节省了网络带宽和电池能源。尤其 是当节点没有通信请求的时候，网路中没有通信开销，可以支持节点的睡眠状态。 每次路由查找过程可以获得从源节点到目的节点的多条路由，从而有效的减小了 路由开销。由于中间节点可以进行路由应答，不但减小了路由请求报文的泛洪量， 还缩短了源节点获得到达目的节点路由的时间。但是中间节点应答可能会引起“应 答风暴 和过时路由在网路中的大量扩散。d s r 协议的每个报文都包含了到达目 的节点的完整路由信息，这在一定程度上降低了带宽资源的利用率。 2 3 a o d v 路由算法 a o d v 2 1 ( a dh o co n d e m a n dd i s t a n c ev e c t o r ) 协议实质上就是d s r 和d s d v 7 一 墨基于i e e e 8 0 2 1 l b 的无线m e s h 网络路由的设计与研究 协议的综合，它借用了d s r 中路由发现和路由维护的基础程序以及d s d v 中跳 到跳的路由选择、序列号码及周期性的更新信息的用法。当网络拓扑结构发生变 化时，它能快速收敛，具有断路的自我修复功能。计算量小，存储资源消耗小， 对网络带宽占用小。a o d v 的操作是无环路的，在避免了b e l l m a n - f o r d 算法的无 穷计数问题的同时，还提供了很快的收敛速度。 a o d v 有别于其他协议的最显著特点是路由表的每个项都使用了目的序列 号。目的序列号是目的节点创建，并在发给发起节点的路由信息中使用的使用目 的序列号可以避免环路。并且很容易编程实现。 a o d v 使用了3 种消息作为控制信息：r o u t er e q u e s t s ( r r e q s ) 、r o u t er e p l i e s ( i u 也p s ) 和r o u t ee r r o r s ( i 也i 汛s ) 。这些消息都在u d p 上使用6 5 4 端口。 a o d v 使用了分布式的、基于路由表的路由方式，所以建立路由表后，在路 由表中的每个节点都要进行路由维持管理路由表的任务，在路由表中都需要保持 一个相应目的地址的路由表项，实现逐跳转发。 在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相 应的项。同时，节点会监视一个活动路由中，下一跳节点的情况。当发现有链路 断开的情况时，就发出r e r r s 通告其他节点。换句话说，当一条活动路由发生了 断链，上游的节点就会使用r e r r s 通知更上游的节点。在r e r r s 中，指明了由 于断链而导致无法到达的目的节点。每个节点都保留了一个前驱列表来帮助完成 错误报告的功能，这个列表中保存了把自己作为到当前不可达节点的下一跳的相 邻节点。具体路由表项如表2 1 组成。 表2 1a o d v 路由表项结构 目的节点i p 地址 目的节点序列号 接口 跳数 上一次跳数 下一跳地址 前驱列表 生存时间 路由标记 根据卡耐基梅隆大学j o s hb r o e h 等人的实验：d s d v 算法在节点低速时运行 稳定，但是随着节点动速度的增加，路由算法无法收敛。d s r 在各种速率下表现 良好，报头开销较大，对路由需求的反应慢。a o d v 协议的移动性能和d s r 相 当，并能减少管理开销。因此本文路由算法实现主要是基于a o d v ，在本节将详 细介绍a o d v 协议的组成【5 1 。 第二章m e s h 中的路由算法 下面详细说明a o d v 的具体各种控制帧及其操作。a o d v 包括路由发现和 路由维护两个部分，主要通过路由请求( r r e q s ) 、路由应答( r r e p s ) 和路由错 误( i 汪i 淝) 这三种控制帧来完成。每个节点维护一张路由表，每个表项以一个 目的节点为索引，记录与该目的节点相关的信息和去往该目的节点的输出线路( 下 一跳邻居节点) 。当一个节点欲发送一个分组但路由表中又不存在该分组的目的节 点时，启动一个路由发现过程。当源节点发现路由表中不存在目的节点的路由表 项，于是构造一个r r e q 帧，启动一个路由发现过程。 2 3 1r r e q 帧的结构及处理 、 源节点构造的r r e q 帧的格式如表2 2 所示。具体含义如下： 标记项：j 为加入标记，为实现组播保留。r 是修复标记，为实现组播保留。 g 为是否产生免费r r e p 的标记。当中间节点响应r r e q 时，在将r r e p 发送 到源节点的时候，同时发送一个r r e p 帧到目的i p 地址节点，这个发送到目的 节点的r r e p 帧就叫免费r r e p 帧。d 指出只有目的节点才可以响应本r r e q 。 u 标明未知序列号，指出目的序列号未知。 r r e q i d ：每个节点维护自己的路由请求序号，每发送个新的路由请求分组， 序号就加1 ；源地址和r e q u e s ti d 唯一标识一个路由请求分组； 源序号和目的序号：每个节点还要维护另一个序号，每当发送了一个与路由 请求相关的分组( 路由请求或路由响应) ，序号就加1 ，利用这个序号可以判断这 个分组( 从而该分组携带的路由信息) 是否是最新的：源序号是源节点的序号， 目的序号是源节点收到的最新的目的节点序号； 跳数：记录该路由请求分组已经经历过的跳数。 表2 2r r e q 帧结构 类型 g rjd u预留跳数 r r e q i d 目的节点i p 地址 目的节点序列号 源节点i p 地址 源节点序列号 当一个路由请求分组到达一个节点时，节点进行如下处理： 1 首先判断该分组是否已经收到过并处理过，即是否是以前收到过的一个分组 的拷贝。每个节点会在一张历史表中记录从各个源节点收到的最新的r e q u e s ti d ， 节点用分组的( 源地址，r e q u e s ti d ) 去查这张历史表，就可以判断该分组是否 是最新的。如果是最新的，就将该分组的( 源地址，r e q u e s ti d ) 记录到历史表 9 一 竺 基于i e e e 8 0 2 1l b 的无线m e s h 网络路由的设计与研究 中，否则丢弃分组。 2 节点在它的路由表中查找分组的目的地址。如果存在一条去往该目的地址的 较新的路由，就向源节点发送一个路由响应分组( r o u t er e p l y ) ，所谓较新的 路由是指路由表中该条路由的目的序号大于或等于路由请求分组中的目的序号。 如果路由表中的目的序号小于路由请求分组中的目的序号，表明这条路由已经过 时，执行。 3 由于接收节点不知道到目的地址的较新路由，于是它增加分组中的h o p c o u n t 域，然后重新广播该路由请求分组：同时在它的反向路由表中增加一个表项， 记录这条反向路由( 如去往源节点的下一跳节点，距离源节点的跳数，该源节点 的序号等) 。反向路由用于将来向源节点发送路由响应分组，每条反向路由都有一 个定时器，当定时器超时时该条路由被清除。 2 3 2r r e p 帧的结构及处理 当r r e q 帧到达一个知道目的节点较新路由的节点或是目的节点自身时，节 点构造一个路由响应r r e p 帧，然后向r r e q 源节点单播发送。r r e p 帧的格式 如表2 3 所示： 表2 3r r e p 帧结构 类型 r a 预留前缀大小 跳数 目的节点l p 地址 目的一铮点序列号 源节点i p 地址 生存时间 标记项：r 为修复标记，为实现组播保留。a 需要应答标记，当节点收到这 个r r e p 帧后需要给于应答。这样做是为了避免单向链路的问题 源地址和目的地址：从路由请求分组中拷贝； 目的序号：取自于自己维护的目的序号； 跳数：自己到目的节点的跳数，若该节点是目的节点，则跳数设为0 ； 生存时间：路由有效的时间。 r r e p 帧沿着r r e q 从中得到的路径返回源节点，途经每一个节点时h o pc o u n t 域加1 ，以使每个节点都知道自己到目的节点的距离。在每一个中间节点上，分 组被检查，当满足以下一个或多个条件时该条路由被加到节点的路由表中，作为 去往目的节点的新路由。 1 路由表中不存在去往目的节点的路由； 2 路由响应分组中的目的序号大于当前路由表中的目的序号； 第二章m e s h 中的路由算法 3 路由响应分组中的目的序号等于当前路由表中的目的序号，但这条路由更 短。 按照以上算法，当某个节点启动路由发现时，从目的节点到该节点的反向路 径上的每一个节点都可免费获得去往目的节点的路由，而那些最初收到路由请求 分组但不在反向路径上的节点，将在定时器超时后删除反向路由表中的相应路由 表项。 当节点收到r r e p 协议帧，它首先建立或更新无有效序列号的到上一跳的路 由表项，然后r r e p 中的跳数值加1 ，将通过中间节点的新一跳计入其中。称已 经增加了l 的跳数为“新跳数”。随后，如果到目的节点的转发路由不存在，则建 立转发路由；否则的话，节点对r r e p 协议帧中的目的节点序列号和本身存储的 目的节点序列号进行比较，比较以后，现存的表项在下列情况下进行更新：现存 路由表项中的序列号无效；现存路由表项中的序列号有效，但r r e p 中的目的节 点序列号大于节点路由表项中保存的目的节点序列号；序列号相同，但是路由不 再有效；序列号相同，但r r e p 中标明的“新跳数”小于路由表项中的跳数。如 果需要对到目的节点的路由表项进行了建立或者更新，路由表项的下一跳就设置 为刚才发出r r e p 的节点( 可从i p 头中的源i p 地址获得) 。跳数设为“新跳数， 过期时间为当前时间加上r r e p 协议帧中的生存期。目的节点序列号为 r r e p 协议帧中的目的节点序列号。当前节点现在可以使用这条路由对去往目 的节点的用户数据分组进行转发了。 如果当前节点不是r r e p 协议帧中源节点字段指示的节点，并且转发路由已 经如上所述进行了建立或更新，节点将查询关于r r e q 源节点的路由表项来为 r r e p 报文确定下一跳，然后使用路由表项中的信息向r r e q 源节点转发r r e p 。 如果转发r r e p 的链路很可能会中断或者是单向的，节点应该设置“a ”标记， 请求r r e p 的接收者发送回r r e p a c k 协议帧。 任何节点传送r r e p 的时候，把r r e p 被转发到的下一跳节点加入到通往 r r e q 目的节点的路由表项的前驱列表中，对该前驱列表进行更新。同时， 往本节点发送r r e p 的上一跳节点也将加入到通往r r e q 源节点的路由表项的前 驱列表中。同时，每个节点上用来转发r r e p 的路由的生存期变为( 现有生存期， 当前时间+ a c t er o u t et i m e o u t ) 两者之间的最大值。 2 3 3r e r r 帧的结构及处理 r e r r 协议帧可以广播发送( 如果有很多前驱节点) ，也可以是单播( 如果只 有一个前驱者) ，或者交互式的单播至所有前驱者( 如果广播不合适) 。 节点在以下三种情况下发起r e r r 协议帧过程：1 如果节点检测到一条正在 里 基丁i e e e s 0 2 1 1 b 的无线m e s h 网络路由的设计与研究 传输数据的活动路由的下跳链路断开；2 如果节点收到去往某个目的节点的用 户数据分组，而节点没有到该目的节点的有效路由( 路由不存在或者处于无效状 态) 并且没有在进行修复；3 如果从邻居收到一个关于一条或多条有效路由的 r e r r 协议帧。r e r r 帧结构如表2 4 ： 表2 4r e r r 帧结构 类型 n预留跳数 不可达目的：1 了点i p 地址 不可达目的节点序列号 小叮达目的节点i p 地址( a d d i t i o n a l ) 小日j 达目的：1 了点厅夕号( a d d i t i o n a l ) n 为不删除标记。如果节点进行了本地链路的修复，通知上游节点不要进行 删除动作时设置这个标志。 对情况1 ，节点首先产生一张不可达目的节点的列表，包含不可达邻居和在本 地路由表中使用不可达邻居作为下一跳的其它任何目的节点。对于情况2 ，只有 一个不可达目的节点，就是无法发送的用户数据分组的目的节点。对于情况3 ， 不可达目的节点列表中的站点应该满足下面条件：包含在r e r r 中，而且这些不 可达目的节点在本地路由表中存在着对应的路由表项，路由表项的下一跳是所收 到的r e r r 协议帧的发送者。 不可达目的节点列表中的一些不可达目的节点可能会被邻居使用，所以需要 发送一个新的r e r r 帧。新的r e r r 帧中的不可达目的节点列表是由满足下面条 件的节点组成：节点存在已经建立的不可达目的节点链表中，并且这个节点在本 机路由表中具有非空的前驱列表。应该收到r e r r 的邻居节点都是这样一些节点： 它们存在新建立的r e r r 中至少一个不可达目的节点的前驱列表中。如果只有单 个邻居需要接收r e r r ，则r e r r 应该单播至目的节点，否则将r e r r 协议帧广 播发送。r e r r 报文中的d e s t c o u n t 自动指出报文中包含的不可达目的节点的数 目。在本节点发送r e r r 之前，需要对节点自己的路由表作一定的更新，这一更 新可能影响到不可达目的节点的目的序列号。对于每一个这样的不可达目的节点， 对应的路由表项按照如下步骤进行更新： 1 路由表项的目的节点序列号如果存在并且有效，对于上述情况1 和2 目的 序列号加1 ，对于情况3 目的序列号从收到的r e r r 协议帧中拷贝到路由表项。 2 将路由表项标记为无效。 3 路由表项的生存期字段更新为当前时间加上d e l e t ep e r i o d 。在这个时 间以前，表项不应该被删除。 注意路由表中的生存时间字段起着双重作用对于有效路由它是过期时 间，对于无效路由它是删除时间。如果一条无效路由收到一个请求使用这条路由 第二章m e s h 中的路由算法 的用户数据分组，它的生存期字段更新为当前时间加上d e l e t ep e r i o d 。 1 3 坐基t - i e e e 8 0 2 1 1 b 的无线m e s h 网络路由的设计与研究 第三章l i n u x 系统的网络相关操作 3 i 1 内核模块简介 3 1l i n u x 内核模块 要对l i n u x 系统下的网络数据包进行特定操作，我们必须能够在l i n u x 网络 数据流中的对特定报文进行捕获，例如论文中定义的a o d v 协议帧。 n e t f i l t e r i p t a b l e s 数据包捕获机制是最新的解决方案，而且也是第一个集成到 l i n u x 内核的解决方案因此我们现在简要讨论一下n e t f i l t e r i p t a b l e s 模块。数据包 捕获机制都是以l i n u x 内核模块的方式工作的，因此我们首先熟悉一下l i n u x 内 核的模块机制i ，k m ( l i n u xk e m e lm o d u l e ) 。