（信息与通信工程专业论文）多接口无线mesh网络路由协议研究及实现.pdf

摘要 摘要 无线m e s h 网络是宽带无线接入的关键技术，主要是为了实现区域范围的无 线覆盖，增强网络的系统容量和连通能力，提高系统的抗毁性和自愈能力。在构 建家庭网络、校园网、社区网络、企业网及城域网中有着广阔的应用前景。 本文对无线m e s h 网络的路由协议进行研究，并根据项目的需要在开发平台 上实现和验证。 论文首先研究单无线接口m e s h 网络中的路由算法，并在单接口无线m e s h 网络开发平台上实现了a o d v 和d s r 路由协议。该平台能够为用户提供宽带无 线接入、无线视频监控等服务。在平台上进行实验测量发现，路径吞吐量随着跳 数增加迅速下降，这是因为在单接口无线m e s h 网络中，所有链路都工作在一个 无线接口上，信道间干扰比较严重。 多接口无线m e s h 网络中的路由器都有多个无线接口，不同接口可以工作在 相互正交的信道上。我们研究并设计实现了有效的多接口无线m e s h 网络路由协 议，可以将网络中的流量在不同的接口信道上进行均衡，有效降低相互间的干扰， 大大提升了网络容量。论文首先提出一个基于最小路径干扰度的路由算法，该算 法为端到端数据流选择干扰度最小的路径，在计算干扰度时考虑了路径上各链路 之间的干扰( i n t r a f l o wi n t e r f e r e n c e ) 。n s 2 的仿真结果表明该算法能有效提高网 络性能。而后又提出一个基于信道相似度的路由算法，综合考虑跳数、负载以及 信道间干扰，从仿真结果看出，该算法能有效提高多接口无线m e s h 网络的吞吐 量。最后，在前面研究的基础上，提出用于多接口无线m e s h 网络的h c r l 路由 算法，该算法综合考虑路径跳数( h o p ) 、信道相似度( c s i ) 、接收信号强度指 示( r s s i ) 、链路剩余容量( l r c l ) 等参数进行路径选择。该路由协议综合了 先应式和按需方式的路由查找思想，可以通过表驱动实现源路由，支持多网关。 我们在多接口m e s h 网路开发平台上实现了该协议，实验测试结果表明采用 h c r l 路由协议可以有效地实现负载均衡，提高网络性能。 关键词：m e s h 网络，多接口，路由判据，a o d v ，d s r ，跳数，信道间干扰， 链路容量，r s s l ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) ，信道相似度 i i i a b s t r a c t 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 st h ek e yp o i n to fb r o a d b a n dw i r e l e s sa c c e s st e c h n o l o g y i tc a na c h i e v er e g i o n w i d ew i r e l e s sc o v e r a g e ，e n h a n c et h en e t w o r kc a p a c i t ya n d c o n n e c t i v i t y , i m p r o v et h es y s t e ms u r v i v a b i l i t y a n ds e l f - h e a l i n g c a p a b i l i t y i na b u i l d i n g ，h o m e ，c a m p u s ，c o m m u n i t y , e n t e r p r i s en e t w o r k sa n dm e t r o p o l i t a n a r e a n e t w o r k ，w i r e l e s sm e s hn e t w o r kh a sw i d ea p p l i c a t i o np r o s p e c t s i nt h i sp a p e r , w es t u d yr 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 ，t h e n i m p l e m e n ta n dv e r i f i c a t i o nt h e mo np l a t f o r m f i r s t l y , w es u r v e yr o u t i n ga l g o r i t h mo fas i n g l e i n t e r f a c em e s hn e t w o r k ，t h e n i m p l e m e n tr o u t i n gp r o t o c o l so fa o d v a n dd s ro np l a t f o r m t h i sm e s hp l a t f o r mc a n p r o v i d eu sw i t l lw i r e l e s sa c c e s s v i d e os u r v e i l l a n c e a n ds o m eo t h e rs e r v i c e s e x p e r i m e n tr e s u l t sd e m o n s t r a t et h a tt h ep a t ht h r o u g h p u tw i l ld e c r e a s er a p i d l ya st h e n u m b e ro fh o p si n c r e a s e s b e c a u s ei nas i n g l ei n t e r f a c em e s hn e t w o r k ，a l ll i n k sa r e w o r k i n go nt h es a m ei n t e r f a c e ，w h i c hc a u s e ss e r i o u si n t e r f e r e n c e i nm u l t i i n t e r f a c ew i r e l e s sm e s hn e t w o r k s ，e a c hm e s hr o u t e rh a sm u l t i p l e i n t e r f a c e s ，a n dd i f f e r e n ti n t e r f a c e sw o r ki nm u t u a l l yo r t h o g o n a lc h a n n e l w ed e s i g na n e f f e c t i v em u l t i i n t e r f a c ew i r e l e s sm e s hn e t w o r kr o u t i n gp r o t o c o l ，w h i c hc a nb a l a n c e t h en e t w o r kt r a f f i c t h r o u g h d i f f e r e n t i n t e r f a c e s ，e f f e c t i v e l y r e d u c en e t w o r k i n t e r f e r e n c ea n de n h a n c ec a p a c i t y t h i sp a p e rf i r s t l yp r o p o s ear o u t i n ga l g o r i t h m c a l l e dm i n i m u mr o u t ei n t e r f e r e n c e t h i sm e t r i ct a k ei n t oa c c o u n tt h ei n t r a f l o w i n t e r f e r e n c ea n ds e l e c tt h em i n i m u mi n t e r f e r e n c e p a t ht ot r a n s m i t d a t a n s - 2 s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h en e t w o r k p e r f o r m a n c e s e c o n d l yw ep r o p o s ear o u t i n ga l g o r i t h mb a s e do nc h a n n e ls i m i l a r i t y , t h en u m b e ro fh o p s ，l o a d ，a sw e l la si n t e r - c h a n n e li n t e r f e r e n c e s i m u l a t i o nr e s u l t s s h o wt h a tt h ea l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h em u l t i i n t e r f a c ew i r e l e s sm e s h n e t w o r kt h r o u g h p u t f i n a l l y , w ep r o p o s eh c r lr o u t i n ga l g o r i t h mf o rm u l t i i n t e r f a c e w i r e l e s sm e s hn e t w o r k ，w h i c hc o n s i d e r sp a t hh o p ( h o p ) ，t h ec h a n n e ls i m i l a r i t y ( c s i ) ， r e c e i v e ds i g n a ls t r e n g t hi n d i c a t i o n ( r s s i ) ，l i n kr e s i d u a lc a p a c i t y ( l r c l ) t os e l e c t v 浙江大学硕上学位论文 p a t h h c r lr o u t i n gp r o t o c o lh a sc o n b i n e dt h ea d v a n t a g eo fp r o a c t i v ea n do n d e m a n d m e t h o d st of i n dr o u t e ，c a na c h i e v es o u l c er o u t i n gb a s e do nt a b l e - d r i v e n ，a n ds u p p o r t m u l t i - g a t e w a y s a st h em e a s u r e m e mr e s u l t ss h o w , h c r lr o u t i n ga l g o r i t h mc a n e f f e c t i v e l yi m p r o v et h en e t w o r kp e r f o r m a n c e ，e v e ni nt h ec o n d i t i o no fh e a v yl o a d ，t h e a l g o r i t h ms t i l lc a nf i n dag o o dp a t ha n db a l a n c et h el o a di nd i f f e r e n ti n t e r f a c e s k e yw o r d ：m e s hn e t w o r k , m u l t i - i n t e r f a c e ，r o u t i n gm e t r i c ，a d o v , d s r ，h o p i n t e r - c h a n n e li n t e r f e r e n c e ，l i n kc a p a c i t y , r s s i ( r e c e i v e ds i g n a l s t r e n g t h i n d i c a t o r ) ，c h a n n e ls i m i l a r i t yi n d e x ( c s l ) v i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：秀武秀努 签字日期： 少f 。年弓月矿日 学位论文版权使用授权书 本学位论文作者完全了解逝姿态鲎有权保留并向国家有关部门或机构送交本论 文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎姿盘堂可以将学位论文的全部 或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：守致劈骂 导师签名： 签字日期：z of o 年3 月害 日签字日期：歹田。年；月毋日 致谢 致谢 首先我要衷心地感谢我的导师赵志峰副研究员，赵老师对学科前沿有着敏锐 的洞察力，他治学态度严谨、知识渊博，富有创新性。在读研究生的两年多时间 里，他在科研上给了我极大的帮助，总能够给予我方向性的指导，让我受益匪浅， 非常感谢他对我的关心和指导。在今后的工作和学习中，我谨记赵老师的教诲， 热爱自己的工作，并在工作中精益求精。 感谢张宏纲教授对我的悉心指导和无私帮助，他总是帮助我分析研究过程中 碰到的难题，并提出各种建议，衷心的感谢张老师。特别感谢周斌硕士，他认真 仔细的态度和严谨的思维让我印象深刻。本文涉及的项目与周斌合作完成，目前 取得的成果跟他的辛勤付出是分不开的。此外，还要感谢给我许多帮助的陈先福 博士、张建敏博士、罗海燕博士、杜维硕士、陈勋硕士、王海洋硕士等。他们的 关心和指导使我很快就适应实验室生活。 还要感谢与我朝夕相处的实验室同学，他们有崔云硕士、吕思达硕士、王峰 硕士、王晓硕士、危彦硕士、夏羽硕士、杨杰硕士、张广超硕士、王龙威硕士等。 感谢我的室友李珊硕士、魏玉欣博士，两年里我们和谐相处，一起度过了美 好的研究生时光。 最后，我要深深地感谢我的家人和好友，他们无微不至的关怀和不求回报的 付出，让我顺利的完成研究生阶段的学习，我会继续努力，回报他们的关爱。 陈琴琴 2 0 1 0 年1 月 第1 章绪论 第1 章绪论 1 1 无线m e s h 网络的研究背景 。嘭 惑。 妙量 妙 “ 。”嘲“矿 卫l “v 、然，。熟，“】_ 1 、? 。 渐江 学学位论文 网络也是分层的，但其下层是具有路由与信息转发功能的客户节点。本文讨论多 级网络结构，仿真和开发平台也都基于该结构。 1 2 无线m e s h 网络的应用场景 无线m e s h 网络的应用场景和应用范围都相当广泛，并且有着不可替代的作 用和优势。无线m e s h 网络与8 0 2l i w l a n 以及3 g 等各种无线接入技术相结合 可以满足家庭网络、社区网络、企业网络以及城域网络内的多层次多范围的无线 应用。 1 、宽带家庭网络 目前，宽带家庭网络互连主要采用8 0 2 1 1 w l a n 来实现，无线a p 的放置需要 根据现场情况而定，不可避免的存在无线信号覆盖不到的区域。为了消除这些无 线覆盖盲区，可在家庭网络互连中采用无线m e s h 网技术，通过放置多个小型m e s h 路由器以多跳中继的方式互连家庭内部数字设备，可以有效地增大无线覆盖范 围，同时还可以提高嘲络容错性，减少由于迂回访问造成的网络拥塞。具体结构 见图1 2 。 图i _ 2 m e s h 构建的宽带家庭网络 2 、社区网络互连 在社区内放置若干个无线m e s h 路由器可i 三l 将社区内各家庭用户网络互连， 形成一个社区无线多跳网络，如图13 。通过该m e s h 网络，社区家庭用户之间 第1 章绪论 就可以共享若干个i n t e r n e t 接入设备，而不必为每个家庭用户安装i n t e r n e 接入设备。而且社区无线m e s h 网还可以容许社区家庭用户在本地相互访问，共 享社区内网络资源。此外社区无线m e s h 网的组网方式，也给社区用户提供了 更加可靠的网络连接，增强了网络容错性和健壮性。 ，一4 、。一z 7 。 、：。 。，3， ，一 二一i 一，一一、 ： q 一且r + 。 一i - ， j i _【 ， 一_ l 量画 图1 3m e s h 构建的社区网络 3 、企业网络互连 目前，8 0 2i i w l a n 在企业办公室、写字楼中已经得到了广泛的应用但这 些w l a n 之间要么相互间没有连接，要么采用有线以太网方式相连。如果采用无 线m e s h 组网技术，就可以通过m e s h 路由器将这些w l a n 互连，而且组网十分方便， 不仅可以解决w l a n 网络之间的连接问题节约有线旆线的成本，还提高了企业 嘲络的容错性和抗毁性。具体结构见图i4 。 笳盯 弹 浙江 学坝l 学位论女 图1 4m e s h 构建的企业网 4 、城域网络互连 无线m e s h 网络，结合8 0 21 6 w m a n 、8 0 211 w l a n 以及3 g 等其他无线接 入技术可以形成一个大范围、多层次、接八方式多样化的城域无线网络，大大增 加无线接入网的覆盖广度和深度。它可以为市民提供公共交通，医疗，消防，公 共安全等市政公共服务及廉价免费的无线上网服务、多媒体应用等。典型应用 场景有楼宇和消防法令检查、城市公园和休闲设施维护、执法、市容维护、交通 监控、社区监管和其他公共安全职责、自动抄表系统。提供的基本业务技术包括： 无线上网，数据采集，i p 视频监控，实时上行视频传送等。 1 , 3 无线m e s h 网络的关键技术 无线m e s h 网络涉及的关键技术有： 1 ) 物理层无线电技术 物理层无线电技术包括定向智能天线、自适应调制编码、m 1 m o 技术，这些 技术已经成为下一代无线接入系统的不可或缺的关键技术。定向智能天线是指在 某一个或某几个特定方向上发射及接收电磁波特别强，而在其它的方向上发射及 接收电磁波则为零或极小的一种天线。采用定向天线可以提高辐射功率的有效利 第l 章绪论 用率，增加保密性，减少网络的干扰。自适应调制编码技术可以根据无线信道的 情况动态调整调制方式以及前向纠错编码方式，采用自适应调制编码技术可以获 得更高的带宽效率和系统容量。m i m o 技术采用多个天线发送和多个天线接收， 利用分集和空间复用可以提高信道的容量，同时提高信道的可靠性，降低误码率。 2 ) m a c 层媒体接入机制 m a c 接入技术主要负责有效的竞争接入和无线m e s h 网络中多跳节点间数 据包发送和接收的调度，将有限的通信资源在多个用户之间进行有效的切割与分 配，在保证多用户通信质量的同时，尽可能地降低系统的复杂度，并获得较高的 系统容量。m e s h 节点需要与其他m e s h 节点协调以解决竞争和共享无线媒体的 问题，从而保证该节点及其他节点的数据包能够通过多跳的无线m e s h 网络有效 转发。现有的一些无线网络m a c 机制大多都是针对单跳无线网络设计的，并不 适于分布式无线多跳网状网络。同时，在无线m e s h 网络中，由于时间同步和扩 频码分配都比较困难，采用t d m a 和c d m a 多址接入也比较困难。 3 ) 信道分配技术 信道分配是多信道技术中的一个关键问题。多接口无线m e s h 网络环境下的 信道分配，主要目的是在保证网络连通性的基础上，获得最大信道利用率。信道 分配主要包括固定信道分配方式、动态信道分配方式和混合信道分配方式。 4 ) m e s h 路由协议 在无线多跳网络中，由于相邻无线链路间存在干扰，中继节点的转发会抑制 其邻居节点的发送，不同路径的数据流间，同一路径上相邻链路间都存在某种程 度的干扰，降低无线m e s h 网络的网络容量。另一方面，无线m e s h 网络的骨干 网具有拓扑相对稳定，无功耗约束，多跳中继，业务流量汇聚于网关等特点，所 以可以通过对路由的合理优化，减小无线链路间的干扰，提高网络容量。因此， 路由协议在无线m e s h 网络中至关重要。 目前无线m e s h 路由协议的设计，主要有两种方法：一种是根据无线m e s h 网络与a dh o e 网络的相似特征，将a dh o c 网络中开发的路由协议d s r ( 动态源 路由协议) 、t o r a ( i 每时按序路由算法) 和a o d v ( a dh o c 按需距离矢量路由协议) 等移植过来用于无线m e s h 网络：另一种是开发无线m e s h 网络专用的路由协议， 如p w r p ( 可预测的无线路由协议) 、m r - - l q s r ( 多射频链路质量源路由) 等。单 浙江大学硕十学位论文 从性能上角度来考虑，开发适用于无线m e s h 路由协议更好。然而，从实现的复 杂性考虑，改进已有路由协议更快捷。微软公司提出的m i 卜l q s r 协议是一种 多接口多跳无线网络的路由协议，就是在d s r 路由协议的基础上改进而来。 路由判据是路由选择的基础，传统a dh o c 网络中普遍采用跳数作为路由判 据，不能反映出多跳网络中的干扰特性。无线m e s h 网络应该根据无线链路状态 以及高层需求等信息，对路径进行评估，选择最佳路由，有效增加网络容量。 5 ) 宽带q o s 业务支持 与a dh o c 网络不同，无线m e s h 网络的大多数应用都是具有不同q o s 要求 的宽带业务。这样，除了端到端时延和公平性以外，还需要在通信协议中考虑时 延抖动、聚合吞吐量、每节点吞吐量以及分组丢失率等性能评价指标。 6 ) 兼容性和互操作性支持 无线m e s h 网络不仅能支持m e s h 终端，最好还能支持传统的无线终端。这 就需要无线m e s h 网络能够后向兼容传统无线终端。此外，无线m e s h 网络应该 包容和整合多种异构类型无线接入网络，要求m e s h 路由器在不同异构无线接入 网络中具有互操作性。 1 4 无线m e s h 网络的路由协议 目前应用在无线m e s h 网络中的路由协议主要有先应式和按需式两种。 先应式路由协议需要不断地检测网络拓扑和链路质量的变化，根据链路变化 情况，及时地更新路由信息。网络中每个节点维护一张或多张表，表中给出到达 其他节点的最新路径信息。当源点要发送数据时，如果路径存在，就可以直接转 发，所需的时延很小。这种路由协议的缺点是需要周期性检测链路的情况，开销 较大。常见的a dh o c 路由协议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 ) ， w r p ( w i r e l e s sr o u t i n gp r o t o c o l s ) ，c g s r ( c l u s t e r e dg a t e w a ys w i t c hr o u t i n g ) 都是 先应式路由协议。 按需路由协议，是一种当需要时才查找路由的路由协议。当源节点有数据向 目的节点发送时，先在网络中发起路由查找过程，找到相应的路由后，才开始发 送数据报。它的优点是不需要周期性地广播路由信息，节省了一定的网络资源， 但与先应式路由协议相比，在数据分组发送时，如果没有到目的节点的路由，数 6 第l 章绪论 据分数需要等待。经常使用的d s r ( d y n a r n i cs o u r c er o u t i n g ) ，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 ) ，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 ga l g o r i t h m ) 等路由协 议都是按需的路由协议。 在无线m e s h 网络中，m e s h 路由器移动性小，网络拓扑结构相对稳定。所以 采用按需方式的路由协议不仅可以减少周期性广播路由信息带来的带宽浪费，而 且在路径建立后，就可以为后续的数据包提供路由。在按需路由协议中，以d s r 和a o d v 最为著名。这两种路由协议算法成熟，而且都有相对应的协议标准提 案，实现简单。在a dh o c 网络以及单接口无线m e s h 网络中的路由实现大多是 基于d s r 和a o d v 的，在多接口无线m e s h 网络中，路由协议多数也是在d s r 和a o d v 基础上改进来的。 传统的无线m e s h 网络一般是单接口的，随着无线m e s h 网络应用的推广， 用户希望m e s h 网络能提供视频、数据、语音通信等服务。如果采用多无线接口 技术，网络容量可以大大提高。采用多接口技术后，无线m e s h 网络的路由算法 需要综合考虑链路质量、信道间干扰、负载等因素，重新设计。 1 5 论文的研究背景 2 0 0 6 年以来，全球兴起了建设无线数字城市的高潮，目前已经有近3 0 0 个城 市已经或正在建设无线数字城市，即用宽带无线接入技术实现城市的无线覆盖， 采用的技术有w i f i 、w i m a x 和m e s h 。w i f i 和w i m a x 采用典型的点到多点服 务模式，一个基站作为集中点，覆盖一定区域，为用户提供接入服务，基站则通 过有线网络接入城域网。但在数字城市建设过程中，承建者发现基站有线回程的 布设非常困难，在有的场合施工难度非常高，比如大型场馆、广场等。由于无线 m e s h 网络是由多个m e s h 路由器自组织、自管理组成的网络，它可以通过一个 或多个网关接入到i n t e m e t 。用户利用附近的无线接入点接入无线m e s h 网络，在 m e s h 路由器之间以无线多跳的方式进行通信，不仅达到接入有线城域网的目的， 大大的增加了无线覆盖的范围，还可以解决w i f i 、w i m a x 技术在构建城域无线 网或区域无线网时无法布设有线回程的问题。 我们研究室承担的企业合作项目“基于8 0 2 1 l 的无线m e s h 路由器开发”和 浙江省科技厅重点工业项目：“多无线接口m e s h 网络路由器开发与应用”，旨 7 浙江人学硕 ：学位论文 在开发满足无线城市建设和运营需要的无线m e s h 路由器原型产品，解决无线 m e s h 网络在无线数字城市中应用的问题，本人主要负责无线m e s h 网络路由器中 路由协议的设计与开发。 1 6 论文研究的主要贡献 论文主要是解决无线m e s h 网络在实际应用中的路由问题，是“基于8 0 2 1 1 的无线m e s h 路由器开发”和“多无线接口m e s h 路由器开发与应用”项目研究 中的一部分。 论文的主要贡献如下： 1 在单接口无线m e s h 网络平台上实现路由协议d s r 和a o d v ，在m e s h 网 络开发平台上能够实现无线上网，数据下载，视频监控和无线局域网服务； 2 对多接口无线m e s h 网络路由协议进行研究，提出一种基于负载的最小路 径干扰度路由算法m 对。该算法考虑接口负载和发包速率，为每一条链路定义 一个干扰度值，在选择路径时优先考虑总干扰度最小的路径。从n s 2 的仿真结 果可以看出，该算法可以很好的避免拥塞，并获得更大的网络吞吐量。 3 在多接口无线m e s h 网络中，给出信道相似度c s i ( c h a n n e ls i m i l a r i t yi n d e x ) 的定义，用来表示信道问的干扰情况。信道相似度即一条路径上工作在相同信道 的链路数之和。并提出了一种基于信道相似度的路由算法，在n s 2 的仿真结果 中可知，该路由算法能获得很好的网络性能。 4 为多接口无线m e s h 网络平台提出h c r l 路由算法，该算法在路由选择时 综合考虑跳数( h o p ) ，信道相似度( c s i ) ，链路接收信号强度指示( r s s i ) ，链路剩 余容量( l r c i ) 。通过在多接口无线m e s h 网络平台上实际测量得知，h c r l 算法 在多接口情况下能有效解决单接口无线m e s h 网络中的带宽瓶颈问题，在负载增 加时，能通过各个接口均衡负载，避免拥塞。 5 多接口无线m e s h 网络的路由协议在a o d v 的基础上进行改进，主要改进 方面如下： ( 1 ) 混合先应式和按需方式进行路由查找：a o d v 是反应式路由，只有在有 数据包请求发送时才会寻找路径。考虑到无线m e s h 网络主要是解决最后一公里 的接入问题，m e s h 网络中最重要的一条路径就是到网关的路径，所以在协议实 第l 章绪论 现的过程中，首先会先应式请求到网关的路由，并且周期性地维护一条到网关的 路径。 ( 2 ) 用表驱动实现源路由：无线网络的路由可以有表驱动和源路由两种方式， 如果采用表驱动，就是由中间节点维护路由，这样就难以对数据进行分流，而且 也难以适应无线网络环境的动态变化，所以无线网络更适合采用源路由。但是源 路由需要为数据包添加源路由路径，增加包长，同时会引入分片问题。a o d v 协议本身是基于表驱动的，我们通过设计一种路由查找方式和添加路由表项的方 法来实现“用表驱动实现源路由 的算法。这种算法集合了表驱动和源路由的优 势。 ( 3 ) 多网关情况下的路由策略：在实际应用中m e s h 网络可能存在多个网关， 而其他节点并不知道网关的工p 地址，所以在请求到网关的路径是如何选择网关 也是值得研究的问题。本文给出一个在多网关情况下网关选择的方法，并在第四 章给出具体的实现过程。 1 7 论文的结构安排 论文的主要内容和章节安排如下： 第一章为绪论，主要介绍无线m e s h 网络的基本架构，应用场景及关键技术， 并对当前无线m e s h 网络的路由现状进行分析。最后给出本文的研究背景。 第二章是单接口无线m e s h 网络路由协议的实现及性能分析，首先分析单接 口无线m e s h 网络的路由情况，再给出m e s h 网络测试平台的硬件架构和软件架 构，然后主要介绍在该m e s h 平台上实现d s r 和a o d v 路由协议的流程，最后 对两个路由协议的性能进行分析。 第三章是多接口无线m e s h 网络路由算法的研究，主要为多接口m e s h 网络 设计路由算法。首先分析一些典型的多接口无线m e s h 网络的路由算法，然后提 出了一个最小路径干扰度的m r j 路由算法，通过仿真可知该算法能有效地避免 拥塞，均衡负载。而后又提出一种基于信道相似度c s i 的路由算法，通过仿真表 明该算法对网络吞吐量有了更大的提高。 第四章是为多接口无线m e s h 网络平台设计并实现路由协议，在第三章多接 口无线m e s h 网络路由协议研究的基础上，提出综合考虑跳数( h o p ) ，信道相似 9 浙江大学硕十学位论文 度( c s 0 ，接收信号强度指示( r s s i ) ，链路剩余容量( l r c i ) 的h c r l 路由算法。 路由协议的实现过程中对a o d v 进行改进，使其能适合多接口无线m e s h 网络 的应用特性。从实际测量的结果看出，该算法能在多接口情况下有效地解决m e s h 网络的带宽瓶颈问题，并且在负载比较大的时候，也能在各个接口间均衡负载， 找到好的路径，从而提高网络性能。 第五章是总结与展望，主要对本文工作进行总结，指出m e s h 网络的发展及 进一步研究的方向。 1 0 第2 章单接口无线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 网络中路由协议的实现， 并对其性能进行分析。 2 1 单接口无线m e s h 网络路由算法 无线m e s h 网络的路由协议主要分为先应式和按需式两种。先应式路由协议 不管有没有数据要发送，总是会主动请求到网络中其他节点的路径。其优点是时 延小，缺点是周期性广播路由信息的开销较大。按需路由协议只有在有数据包发 送时，才请求到目的节点的路径。其优点是路由协议开销小，缺点是时延大。 在无线m e s h 网络中，m e s h 路由器放置位置基本固定，移动性小，网络拓扑 结构相对稳定，一般采用按需方式的路由协议。在按需路由协议中，以d s r 和 a o d v 协议最为成熟，而且都有相应的协议提案。单接口无线m e s h 网络中的路 由实现大多是基于d s r 和a o d v 的， d s r 路由协议是动态源路由协议。源路由是指在每个数据分组头部携带到目 的节点的完整路径信息，中间节点根据源路由信息进行转发。d s r 路由协议主 要包括路由发现和路由维护，路由发现是指当路径不存在时，源节点发送一个包 含源路由列表的路由请求包r r e q ，一开始路由列表中只有源节点。每个节点都 有一个路由缓存区来记录最近收到的路由请求信息，避免重复转发。节点将已获 得的源路由表进行保存，当收到r r e q 时，先检查有没有合适路径，如果有就 不再转发，而是回复一个路由应答，否则就将自己地址添加到路由列表中再转发 该请求包。目的节点收到路由请求时，就会回传一个路由应答包，包含从源节点 到目的节点的所有地址信息，这样就完成了路由发现过程。路由维护是指当检测 到某条链路断开后，节点向上游节点发送r e r r 包。源节点在收到该包后就会 删除相应的路由表项。 a o d v 路由协议结合了表驱动和按需两种思想，只有在数据发送时，才发起 路由发现。但a o d v 和d s r 不同，它是由节点维护路径，中间节点根据路由表 浙江大学硕十学位论丘 柬转发数据。a o d v 路由协议也分为路由发现和路由维护两部分。路由发现指 源节点没有到目的节点的路径时，发起一个路由请求分组，接收到该请求的中问 节点建立到源节点的反向路径，然后再转发该请求分组，目的节点在收到该报文 后先建立反向路径再发送路由回复包。如果中间节点有到目的节点的路径，也 会发起路由回复包。在路由回复包沿着反向路径传递到源节点的过程中，建立前 向路径。任何出错的链路或过时的路径都会在路由维护过程中删除。 2 2 单接口m e s h 路由器开发平台 无线m e s h 路由器不仅要处理a p 收到的数据，还要负责中继其他路由器的 数据，所以需要高速的网络处理器和总线的支持，这对主处理板的硬件设计提出 了很高的要求，本文采用的单接口无线m e s h 路由器开发平台的总体硬件结构如 图21 所示，其中高速总线的下部是主处理板，包括了高速网络处理器、内存、 f l a s h 、交换芯片等，提供w a n 接口、l a n 接口、c o n n i e 接口。高速总线的上 部是多个无线模块，以实现对多无线接口的支持。 女粕r 网网丽丽 图2lm e s h 路由器总体硬件结构 对于主处理板，开发平台以高速网络处理器为核心来设计和开发。网络处理 器是一种新型的s o c 它不仪集成了高性能的c p u 梭，还集成了网络路出设各 第2 章单接口无线m c s h m 络路由挑议实现及性能分析 必须的e t h e m e t 接口、u a r t 接u 、1 2 s 、s l i c 等接口，此外还提供了高速的p c i h o s t 接口以实现模块的扩展。开发平台采用a t h e r o s 公司的a r 7 1 0 0 系列网络处 理器，主频高达6 0 0 m h z 。内嵌3 2 b i t m i p s2 4 k 主处理器核，支持双g e 接口， d d r 内存，具有3 2 b i t3 3 6 6 m x - l zp c i23 h o s t 接口。 主处理开发板上其他主要硬件设备有：1 个r s 2 3 2 串口、1 个1 0 0 m 有线网 口、1 个4 口1 0 0 m 有线以太嘲口、2 个u s b 口、2 个m i n ip c i 插槽。 无线接口完成无线信道的接入和数据的传输。我们采用a t h e r o s 公司的 a r 5 0 0 8 系列芯片组，包括了基带和射频，支持i e e e s 0 21 1 b ，g ，可以通过高速 m i n ip c i 接口接入a r 7 1 0 0 系列网络处理器。 圈圈圈 叵叵 豳鲤豳豳叵回叵 r 1硬件驱动卜_ il i n u x 操作系统 图2 3m e s h 路由器实物图 图2 2 给出路由嚣的软件架构基于l m u x 操作系统t 由一些低层的驱动和 标准协议组成，我们关注的是路由协议，主要是在网络层实现，【t 司时需要提取。 浙江大学硕十学位论文 些m a c 层的信息作为路由参数。图2 3 是单接口m e s h 路由器的实物图。 在图2 1 的硬件结构中，可以看到有两个无线模块，在本章中，我们将其中 一块配置成无线a p 工作模式，另一块配置成a dh o c 工作模式，所以对m e s h 网 络来说还是单接口的。 2 3i ) s r 路由协议的实现 文献【2 8 。1 1 已经对d s r 路由协议的实现做了一些研究，其中文献【1 5 】是i e t f 给出的d s r 协议实现的提案，本节就是根据该提案，在m e s h 网络路由器开发 平台上实现d s r 路由协议的。 d s r 路由软件主要由两部分构成：d s r 路由进程与d s r 内核路由模块( 简 称内核模块) 。d s r 路由进程在用户空间运行，主要用于路径发现和错误恢复， 可以非常方便的进行线程调度、事件处理，而且不会引起内核崩溃。d s r 内核 路由模块是指在内核中完成的一些数据包的操作，如添加删除d s r 头( 包含源 路由路径) 、按照源路由进行路径查找等。 d s r 路由进程和内核模块之间通过l i n u x 的n e t l i n k 消息机制进行通信， 消息类型主要包括以下四种： 1 ) d s r 头消息，d s r 是基于协议实现的，所以d s r 头上的信息都要从n e t f i l t e r 钩子函数上获取，这个后面会介绍。d s r 头消息包括r r e q 控制包，r r e p 控 制包，r e r r 控制包。内核模块在收到d s r 头消息后将该消息通过n e t l i n k 消息机制发送给d s r 路由进程进行相应处理； 2 ) 未找到源路由路径消息，当内核模块未能给数据包查找到目的地址的路径 则需要发送该消息来通知路由进程发起路由发现； 3 ) 链路失效消息，当检测到链路失效时，内核模块就发送链路失效消息通知 路由进程进行错误恢复，路由进程就会发送r e r r 包，通知源节点路径失效。 4 ) 添a n 删除源路由表项消息，路由进程发现到某目的地址的路径或者发现 某路径失效时，就通过发送该消息来通知内核模块添加或删除相应源路由表项。 2 3 1d s r 路由协议数据结构及流程 1 4 d s r 是基于i p 协议实现，协议号为4 8 ，下图是d s r 协议头结构。 第2 章单接口无线m e s h 网络路由协议的实现及性能分析 。m a c h e a d e r ji ph e a d e r ；d s r h e a d e l 5d a t a 。 。_ _ _ _ 。_ _ _ _ - 。_ _ _ 。_ 1 。一。_ _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ 。_ _ 。_ 。_ 。_ 。- 。- - _ 。 ? n e x th e a d e r + fi r e s e r v e d 7 p a y l o a dl e n g t h i l 。“。1 。一。+ 。l 。一。l 。1 。1 。一。_ 一 o p t i o n s 图2 4d s r 协议结构 在数据包中插入d s r 头是通过操作s kb u f r 结构完成的，s kb u f r 是网络处理 缓存，在网卡接收到分组后，就将分组放进s kb u f f 中再传给网络堆栈，网络堆 栈在后续处理中一