（计算机应用技术专业论文）基于无线mesh网络的superimposed+codes算法的改进.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 无线m e s h n 络( w m n ) 是快速发展的新型网络技术并支持宽带高速多媒体业务服务，因 此近年来被高度重视。随着未来无线分布技术和无线分布网络的发展，无线m e s h 网络技术 将可能成为无线移动通信的基本网络技术，渗透到各种无线网络中，发挥更大作用。 如何提高无线m e s h 网络的容量来满足用户日益增长的带宽需求( 如实时音频、视频下 载等) 是近年来研究的热点和难点，i e e e8 0 2 1 1 等标准都定义了不同数目的正交信道，利 用这些正交信道可以同时发送数据包且不会相互干扰。充分利用多信道正交的特点，就可 以减少节点间的冲突，从而提高无线m e s h 网络的容量。原有的d s d v 、a o d v 、d s r 等路 由协议已不完全适合这种多接口多信道无线m e s h 网络。因此，论文中的s u p e r i m p o s e d c o d e s 路由算法是依据此类标准的多信道特点设计的。 论文首先阐述了无线m e s h 网络的概念、结构、特点以及设计s u p e r i m p o s e dc o d e s 路由 算法相关的m a c 层的基础知识。通过研究d s r ，发现在无线m e s h 网络中采用d s r 存在信道 选择和路径选择两方面的不公平现象。针对这两个问题，设计ts u p e r i m p o s e dc o d e s 路由算 法来选择信道，用已有的s m e t t 路由判据来选择路径，并根据路由算法和路由判据的需求 在d s r 路由表中添加了信道表和流表。运用d s r 的思路并结合s u p e r i m p o s e dc o d e s 路由算法 和路由判据，设计了一种基于多接口多信道路由协议m r m c r ( m u l t i r a d i o i n t e r f a c e m u l t i c h a n n e lr o u t i n g ) 。最后，对m r m c 瞄行仿真和性能分析，仿真结果表明：在无线 m e s h 网络中m r m c r 在网络吞吐量和时延方面与d s r 、a o d v 相比有较大的改善。 关键词：无线m e s h 网络；m r m c r 协议；多信道 南京邮电大学硕士研究生学位论文 a b s t r a c t 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 k ( w 2 v i n ) h a sb e e na c t i v e l yr e s e a r c h e da n dd e v e l o p e da sa n e wn e t w o r kt e c h n o l o g yt os u p p o r tb r o a d b a n da n dh i 曲s p e e dm u l t i m e d i as e r v i c e s w i t ht h e d e v e l o p m e n to fd i s t r i b u t e dw i r e l e s st e c h n o l o g ya n dd i s t r i b u t e dw i r e l e s sn e t w o r k si nt h ef u t u r e ， t h ew i r e l e s sm e s hn e t w o r kt e c h n o l o g ym a yb e c o m et h eb a s i cn e t w o r k i n gt e c h n o l o g y , a n dm a y b ei n v o l v e di na l lw i r e l e s sn e t w o r k s h o wt oi m p r o v ew i r e l e s sm e s hn e t w o r k s c a p a c i t yt om e e tg r o w i n gu s e rd e m a n df o r b a n d w i d t h ( s u c ha sr e a l t i m ea u d i o ，v i d e od o w n l o a d i n g ) i sa n o t h e rh o tt o p i ci nr e c e n ty e a r s t h e i e e e8 0 2 1is t a n d a r da n do t h e rs t a n d a r d sp r o v i d em a n yn o n - o v e r l a p p i n gf r e q u e n c yc h a n n e l s ， w h i c hc o u l db eu s e ds i m u l t a n e o u s l yw i t hi na n e i g h b o r h o o d a b i l i t yt ou t i l i z em u l t i p l ec h a n n e l s w i t h i nt h es a m en e t w o r ks u b s t a n t i a l l yi n c r e a s e st h ee f f e c t i v eb a n d w i d t h ，a n de n h a n c e st h e w i r e l e s sm e s hn e t w o r k s c a p a c i t y f o r m e rr o u t i n gp r o t o c o l sd on o tm a t c hm u l t i r a d i o - i n t e r f a c e m u l t i - c h a n n e ln e t w o r k t h e r e f o r e ，t h i st h e s i sd e s i g n s r o u t i n ga l g o r i t h mb a s e do ns u p e r i m p o s e d c o d e s t h i st h e s i sf i r s t l yi n t r o d u c e st h ec o n c e p t i o n , t h es t r u c t u r ef e a t u r e sa n db a s i ck n o w l e d g e o f r o u t i n ga l g o r i t h mb a s e do ns u p e r i m p o s e dc o d e s o nt h er e s e a r c ho fd s r , t h e r ei sap r o b l e m o f u n f a i r n e s si nc h o i c eo ft h ep a t ha n dc h a n n e l i no r d e rt os o l v et h ep r o b l e m ，r o u t i n ga l g o r i t h m b a s e do ns u p e r i m p o s e dc o d e si sd e s i g n e da n da c c o r d i n gt oi tm e s s a g ei sa d d e d an e wr o u t i n g p r o t o c o lm r m c r ，w h i c hi sb a s e do nt h i sr o u t i n ga l g o r i t h m ，s m e q q a n dd s r si d e a , i sg i v e n o u t i nt h ee n d ，as i m u l a t i o nw o r ki sc a r r i e do u tt os h o wt h ed i f f e r e n c e sb e t w e e nt h em r - m c r a n df o r m e rr o u t i n gp r o t o c o l s ，f o l l o w e db yac o n c l u s i o n ：m r m c rd o e sb e t t e rt h a nd s ra n d a o d vi nt h ea s p e c t so ft h r o u g h p u ta n dd e l a y i n g k e y w o r d s ：w i r e l e s sm e s hn e t w o r k ；m r m c rp r o t o c o l ；m u l t i c h a n n e l i i 南京邮电大学硕士研究生学位论文 缩略词 缩略词 缩略词英文全称 中文 a c k a c k n o w l e d g e 确认 姆a c c e s sp o i n t 无线访问接入点 c s m b v c a c a r r i e rs e n s em u l t i p l ea c c e s sw i t h 载波侦听多点接入冲突避免 c o l l i s i o na v o i d a n c e c t sc l e a rt os e n d 准备接收 c u lc h a n n e lu s e dl i s t信道使用状况列表 d c a d y n a m i cc h a n n e la c c e s s 动态信道接入 d c a p c d y n a m i cc h a n n e la c c e s s p o w e rc o n t r o l功率控制型动态信道接入 d c fd i s t r i b u t e ac o o r d i n a t i o nf u n c t i o n 分布式控制 d s r d y n a m i cs o u r c er o u t i n g 动态源路由协议 f c lf r e ec h a n n e ll i s t空闲信道列表 f i f of i r s ti nf i r s to u t 先进先出队列 f t pf i l et r a n s p o r tp r o t o c o l文件传输协议 i e e ei n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s 美国电气及电子工程师学会 m a cm e d i u ma c c e s sc o n t r o l媒体接入控制 m r m c rm u l t i r a d i o - i n t e r f a c em u l t i - c h a n n e lm u t i n g 多接口多信道路由协议 r e r r r o u t ee r r o r 路由错误 r e sr e s e r v e 保存 i 强r a d i of r e q u e n c y 射频 r j 也q r o u t er e q u e s t路由请求 i 盯s r e q u e s tt os e n d 请求发送 t c p ，i p t r a n s p o r tc o n t r o lp r o t o c o l i n t e r n e tp r o t o c o l 互联网传输控制协议 w r w i r e l e s sr o u t e r 无线路由器 w r w w i r e l e s sr o u t e rw i t h 与有线网络相连的无线路由器 i i l 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特另t l , , - h n 以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学 或其他教育机构的学位或证书而使用过的材料。与我一起工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：殛：後垂日期：2 1 翌：生：止 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保 存论文。本人电子文档的内容和纸质论文的内容相一致：除在保密期内的保 密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部 分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：啦导师签名：二妻数日期：2 竺2 ：垒丝 南京邮电大学硕士研究生学位论文第一章绪论 第一章绪论 近年来，w l a n ( w i f i ) 在接入领域中得到了迅速发展，依其所具有的巨大数据传输 速率，w l a n 被认为是3 g 或3 g 后移动数据通信部分的个主要竞争对手。但w l a n 有其不 足之处，其中最主要的一个便是接入点( a p ) 的覆盖范围较为有限，若要在一个相对较大的 区域提供无线覆盖，就需要在该地区内配置多个接入点，因而增加了建设基于w l a n 的公 共宽带网的成本。虽然人们对此提出了一些解决方法，如通过多种无线技术的共存来提高 无线的覆盖和位置的适应性等等，但这些方法中大多是以增加接入点或降低网络运行效率 为代价。于是人们把目光转向另一种网络结构无线m e s h 网络，希望通过这种全新的网 络结构来克服传统无线网络中所存在的固有缺点，实现无线宽带领域中的一次变革。 1 1 无线m e s h 网络的概述 1 1 1 无线m e s h 网络的概念 无线m e s h 网络是一种新型的宽带无线网络结构，一种高容量、高速率的分布式网络。 无线m e s h 网络不同于传统的无线网络，它可以看成是w l a n ( 单跳) 和移动a dh o c 网络( 多 跳) 的融合，且发挥了两者的优势。无线m e s h 网络作为可以解决“最后1 公里”网络接入瓶 颈问题的方案，已被写入了i e e e8 0 2 1 6 ( w i ) 无线宽带接入网络标准中，目前也被纳 入到i e e e8 0 2 1 5m e s h 和i e e e8 0 2 1l sm e s h 标准中。从技术特点来看，无线m e s h 网络将 可能成为未来无线城域网( w 删) 中核心网的理想组网方式。 传统的无线网络必须首先访问接入点才能进行无线连接。这样，即使两个8 0 2 1 l b 的 节点互相都在彼此的通信范围之内，它们也必须通过接入点才能进行通信。而“m e s h ”这 个词原来的意思就是指全连通，即所有的节点都互相连接，所以在无线m e s h 网络中，每个 节点都可以与一个或者多个对等节点进行直接通信。m e s h 网络技术原是一项军方技术，随 着人们对i e e e8 0 2 1 l a b 和8 0 2 1 l g 等w l a n 技术了解的深入，无线m e s h 网络才逐步成为 企业界和消费者瞩目的焦点。 目前主要观点认为，无线m e s h 网络是一种由无线链路连接路由器和终端设备组成的静 态无线网络，是i n t e r n e t 的无线版本，f l j i n t e r n e t 的构架其实就己经是一个m e s h 网络的结构。 众所周知，接入i n t e m e t 的用户位于网络的边缘，他们通过网络内部的路由器相互连接，而 这些路由器的连接方式：当任意两个节点之间的一条链路失效后，路由器会经由一个或多 l 南京邮电大学硕士研究生学位论文第一章绪论 个别的路由器找到一条替代路径。这也正好体现了m e s h 网络的思想。 无线m e s h 网络的应用主要集中在两个方面：传感器和骨干网。 传感器是一种构造相对简单、体积较小的装置，具有一个简单的处理器。它经常被用 来收集一些数据，例如湿度、压力、温度和振动等，并把这些数据传递给其它的传感器。 由于体积小，所以它们一般没有用户界面，甚至可以被视为数据传送器。传感器还可以嵌 入到设备当中，对压力、流量和温度进行监控。 无线m e s h 网络的骨干一般是指网络中构成主要数据传输线路的那些高速链路。传统 上，骨干网是使用光纤( 以前是铜线) 将各个边缘网络相互连接起来。在无线m e s h 网络中 只需要有一个节点连接到有线网络上，所有的节点就都可以接入到有线网络了。当然出于 冗余度和流量的考虑，可能会需要更多的节点与有线网络相连。骨干m e s h 可以布置在室 内也可以在室外，室外设备往往附着在街灯上或者是建筑物外表面上有电力可用的地方。 由于线路上m e s h 路由器的出现，每一个节点都能与其它节点进行联系，因而，很多户外 系统就不仅仅起到传输设备间传输数据作用，也可以包含集成的接入点供客户端使用。这 种解决方案往往包含两种m a c 协议标准，其中i e e e8 0 2 11 a 用作传输设备间传输数据， i e e e8 0 2 1 l b g 给客户端用，这大大减轻了传输设备和用户对流量的争夺问题。 1 1 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 路由器配置有多个无线接口，各个接口可以是相同的，也可以是不同的。m e s h 客户 节点也可以分为两类：一类是普通的w l a n 客户节点，这类节点不具有a dh o c 网络典型意 义下的信息转发功能，只是作为普通终端设备接入网络；另一类节点既具有普通终端设备 节点的接入功能，又具有路由和信息转发功能，即兼具了无线路由器的功能，但通常这类 节点不具备网关或网桥节点的功能。若按节点的不同功能，网络结构可分为基础设施的网 络结构、终端设备的网络结构和混合结构。若按结构层次，网络又可分为平面结构、多级 结构和混合结构。这两种分层思想本质上是相似的，基础设施的网络结构就是一种多级结 构，而终端设备的网络结构就是一种平面结构。 平面网络结构也称终端设备网络结构。网络中的节点为具有m e s h 路由器功能的增强型 终端用户设备，终端用户自身配置r f 装置，通过无线信道的连接形成一个点到点的网络。 这是一种任意网状的拓扑结构，节点可以任意移动，网络拓扑结构会动态变化。在这种环 2 南京邮电大学硕士研究生学位论文 第一荦绪论 境中，由于终端的无线通信覆盖范围有限，两个无法直接通信的用户终端可以借助其他终 端的分组转发功能进行数据通信。在任一时刻，终端设备在不需要其他基础设施的条件下 可独立运行，可支持移动终端设备较高速率的移动，快速形成宽带网络。终端用户模式事 实上就是一种a dh o c 网络结构模式，这种网络结构模式可以在没有或不便利的现有网络基 础设施的情况下提供一种通信支撑环境。 多级网络结构分为上层和下层两个部分。该模式在接入点( m e s h 路由器) 与终端用户之 间形成无线回路。移动终端通过m e s h 路由器的路由选择和中继功能与网关节点形成无线链 路，网关节点通过路由选择及管理控制等功能为移动终端选择与目的节点通信的最佳路 径，从而实现无线宽带接入。这样的结构降低了系统建设成本，也提高了网络覆盖率和可 靠性。混合网络结构( 图1 - 1 ) 就是多级网络结构中的下层改为平面网络结构的网络结构。 本文研究的网络模型就是图1 - 1 中的无线m e s h 网络结构图，并只研究图1 - 1 中的网 络上层中的节点。路由算法的前提只涉及静止或弱移动节点( 删和w r ，其中w r w 为与有线网络相连的无线路由器，w r 为没有与有线网络相连的无线路由器) ，w r w 与w r 之间、w r 与w r 之间为无线连接，这些节点是多接口多信道节点。， 图1 1 无线m e s h 网络结构图 1 1 3 无线m e s h 网络与传统无线网络的区别 线 一一无线 无线m e s h 网络与w l a n 有明显的区别：从拓扑结构上看，w l a n 是典型的点对多点 ( p 2 m p ，p o i n tt om u l t i p l ep o i n t s ) 网络，采取单跳方式而且数据不可转发。w l a n 口- - - $ 在较小的 3 南京邮电大学硕上研究生学位论文第一章绪论 范围内提供高速数据服务( 8 0 2 儿b 可达1 1 m b i v s ，8 0 2 1 l a 可达5 4m b w s ) ，但由于一般情 况下w l a n 接入点的覆盖范围仅限于几百米，如果想在大范围内应用w l a n 的这种高速率 服务模式，成本将非常高昂。而对于无线m e s h 网络，则可以通过无线路由器对数据进行智 能转发( 需要对w l a n 传统的a p 功能进行扩展和改进) ，直至把他们送至目的节点，从而 把接入点服务的覆盖延伸到几公里远，可以在大范围内实现高速通信。w l a n 的m a c 协议 完成的是本地业务的接入。而无线m e s h 网络则有两种可能，一种是本地业务的接入，另一 种是其他节点业务的转发。 无线m e s h 网络是从移动a dh o c 网络分离出来，然而，两者存在一些各自的特点：( 1 ) 虽然无线m e s h 网络与移动a dh o c 网络均是点对点的自组织的多跳网络，但从根本上说，无 线m e s h 网络由无线路由器构成的无线骨干网组成。该无线骨干网提供了大范围的信号覆盖 与节点连接。然而移动a dh o c 网络的节点都兼有路由和主机功能，节点地位平等。( 2 ) a dh o c 网络的健壮性比无线m e s h 网络差。( 3 ) 无线m e s h 网络节点移动性低于移动a dh o c 网络中的节点，所以无线m e s h 网络注重的是“无线”，而移动a d h o c 网络更强调的是“移 动”。( 4 ) 从网络结构来看，无线m e s h 网络多为静态或弱移动的拓扑，而移动a dh o c 网 络多为随意移动( 包括高速移动) 的网络拓扑。 1 1 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 网络；在无线m e s h 网络路由准则和选择算法等方 面，目前提出的特别适用于无线m e s h 网络路由协议很少；在无线m e s h 网络连接性和多路 支持方面，每个节点链路连接度也是一个至关重要的问题，并非使用射频信道数越多，网 络性能越好，射频信道数增加会带来设备开销和成本上升，同时可能带来更多的干扰问题； 在无线m e s h 网络带宽利用和资源分配算法方面，目前还没有提出非常有效的可用算法和 协议。 无线m e s h 网络具有以下一些结构或技术上的特点：多跳无线网络，支持a dh o e 网络 结构，具有自形成、自愈和自组织能力，移动性取决于节点的类型，多种网络接入方式( 无 线m e s h 网络中的网关或网桥等设备使无线m e s h 网络与现有的蜂窝网、无线传感器网络、 4 南京邮电大学硕士研究生学位论文第一章绪论 w l a n 、w i m a x 和w i m e d i a 等结合) ，功能限制取决于节点类型，与现有的无线网络具有 兼容性及互操作性。 1 2 无线m e s h 网络中的主要研究课题 无线m e s h 网络有几个关键技术问题需要进一步研究解决。 ( 1 ) 天线技术 无线m e s h 宽带网络中一个重要的问题就是天线的使用，因为每个节点必须和各个方 向上的多个节点通信，很简单的一种方式就是采用全向天线，但是这样覆盖范围有限，并 会带来干扰，导致频谱利用率下降，网络容量减小，所以不建议采用全向天线。现在出现 一些多射频技术( 如m i m o ) ，对频谱利用率比较高。 ( 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 8 0 2 1 6 标准中规定的点到多点宽带无线接入网络中采用了动态按需时分多址分配 d a m at d m a 方式，在这种网络中资源的管理和分配由基站负责。而在i e e e8 0 2 1 6 a 标准 中规定，对于基于无线m e s h 技术的宽带接入网络，带宽的分配可以采用集中调度方式，或 者采用分布调度方式。如果采用集中调度方式，f l j m e s hw r w 节点收集所有m e s h 节点的资 源请求信息，分别为它们分配一定数量的带宽资源。如果采用分布调度方式，包括m e s h w r w 和m e s hw r 在内的所有节点应该相互协调，充分利用资源。任何一个节点发送数据 时，不能和两跳以内的邻近区域的其它节点发送的数据产生碰撞。 1 3 内容安排 本文共分五章，内容安排如下： 第一章主要介绍了无线m e s h 网络的概念、无线m e s h 网络结构与特点、以及论文主 南京邮电大学硕士研究生学位论文 第一章绪论 要的内容安排。 第二章讨论了无线m e s h 网络中的多信道技术的必要性和多信道m a c 协议，跨层设 计思想。 第三章主要详细分析了d s r ，并根据s u p e r i m p o s e dc o d e s 路由算法和s m e t f 路由 判据的需求添加了信道表和流表。 第四章重点分析了本文提出的s u p e r i m p o s e dc o d e s 路由算法，且运用d s r 的思路来 结合该算法和s m e t t 路由判据提出了一种基于多接口多信道路由协议m r m c r 。 第五章使用n s 一2 对设计的方案进行仿真。结果显示还是比较理想的，相对于传统 的无线路由协议性能有所提高。 第六章总结了本文所作的工作，并展望了下一步的研究工作。 6 南京邮电大学硕士研究生学位论文 第二章多信道m a c 协议 第二章多信道m a c 协议 随着人们对无线接入技术了解的深入，无线m e s h 网络已经逐步成为企业界和消费者瞩 目的焦点。无线m e s h 网络作为典型的多跳无线网络，如何利用无线介质的共享特性来满足 用户日益增长的带宽需求( 如实时音频、视频下载等) ，是近年来研究的热点和难点所在。 由于i e e e8 0 2 1 1a b g 等标准都定义了不同数目的正交信道，利用这些正交信道可以同时 发送数据包且不会相互干扰。如果可以根据多信道的特点，并充分利用跨层设计思想和 m a c 层中的信道信息来设计多信道路由协议，就会减少节点间的冲突，从而提高无线m e s h 网络的容量。 本章探讨了无线m e s h 网络的多信道m a c 协议，基于多信道的无线m e s h 网络节点的模 型，重点研究了论文中路由算法所基于的无线m e s h 网络的多信道m a c 协议，以及无线m e s h 网络中的跨层设计思想，为下文设计的路由算法提供理论基础。 2 1 无线m e s h 网络的多信道m a c 协议 2 1 1 多信道技术的必要性 现有的无线局域网m a c 协议大多是单信道的m a c 协议，这种技术限制了整个网络的 速率及网络容量。根据无线信道的特点，源节点向目的节点传送数据时，为了避免网络冲 突，两个节点的所有相邻节点都不能够进行数据传输，这就很大程度上限制了网络的容量。 尽管现有的i e e e8 0 2 1 l 舶信与i e e e8 0 2 1 6 协议在物理层技术上有了很大的提高，如采用 了一些有效的功率控制方法，但仍然不能从根本上解决人们对网络带宽日益增加的需求。 i e e e8 0 2 1 l a g 标准的标称带宽为5 4 m b i t s ，但这只是峰值速率，真正的实际应用过程中， 由于节点接入时会发生多用户冲突、丢包等，真正可用的带宽不会超过标称值的一半。另 外，随着通信双方传输距离的增大，数据传输率会明显下降。在多跳的无线m e s h 网络中， 数据在收发过程中面临节点冲突的可能性会增加，暴露终端及隐藏终端也会造成网络吞吐 量大幅度下降。硬件技术发展到今天，使用多信道来构建无线局域网已成为可能。多信道 可以采用物理上的技术，也可以采用逻辑上的技术。多信道的m a c 协议最大的好处是可以 在不同的数据信道上同时通信，避免数据帧之间的冲突。并且多信道环境可以通过使控制 7 南京邮电大学硕士研究生学位论文 第二章多信道m a c 协议 信道与数据信道分离，缓减暴露终端及隐藏终端的问题。 2 1 2 信道和网络接口卡模型 本文中基于多信道的无线m e s h 网络采用图2 - 1 中的信道和网络接口卡模型。 首先假设网络中可用的信道数目为n ( 即n 个信道是正交的信道，所有信道相互之间同时 传输数据互相不干扰) 。在论文的研究中，为了便于分析，所有的n 个信道都是同构的：即 所有的信道都支持相同的数据传输速率和数据传输范围。假设每个路由器中有i n 个可用的 网络接口卡，针对每个路由器装配不同数目网络接口卡的更一般情况，在论文中没有进行 研究和分析。 每个网络接口卡在同一时间只能在一个信道上发送或者接受数据( 半双工操作) 。每个 网络接口卡在一定时问内可以切换到网络中的任何一个信道，切换花费的时间记为切换延 时，随着底层硬件技术的发展，这个延时在今后可能会忽略不计。但在研究中切换延时是 考虑到的，这样可以确保协议在网络接口卡的切换延时不同的情况下正常工作。 图2 - 1 多接口多信道网络模型 图2 1 就是我们的基于多信道无线m e s h 网络的信道和网络接口卡模型，我们用记号 ( m ，n ) 表示每个节点的网络接口卡数目为m ，可用的信道数目为n 。本文的研究主要针对 每个路由器网络接口卡的数目少于网络中可用信道数目的一般情况( 即m 3 。( 矩阵a 的构造在参考文献【1 1 】、【1 2 】中有详细论述) 下面举例子说明： 图4 11 3 列( 3 ，l ，1 3 ) 编码 图4 1 中任意3 个列向量相并都不包含其他列，如：x ( a ) 岱x ( 1 ) v x ( 2 ) v x ( 3 ) ，a ( 1 、 2 、3 ) 。 4 1 2s u p e r i m p o s e dc o d e s 算法和信道分配相结合 ( 1 ) 利用s u p e r i m p o s e dc o d e s 进行信道分配 根据s u p e r i m p o s e dc o d e s 路由算法的需求将图论中的g ( v 、e ) 该为g ( v 、e 、c ) 其 2 5 l 0 l 0 0 0 0 0 1 o 0 0 1 0 1 o 0 o 0 0 l o 0 o l 1 l o 0 o o 0 1 0 0 0 1 1 0 o o o o o 1 0 0 o l 1 0 l o o o 0 1 0 0 o l l o l 0 0 0 0 l o 0 o l l o l o o o 0 l 0 0 o 1 1 0 l o 0 o 0 1 o 0 o 1 l 0 1 o 0 0 o l 0 o 0 l 1 o l 0 0 o o 0 0 o o 1 1 o 1 o 0 o o 0 1 0 0 l 1 0 1 o 0 0 0 0 l o o 1 l 0 1 0 0 0 o 0 l 0 0 1 l 0 1 o o 0 o o 1 o 0 0 南京邮电大学硕士研究生学位论文 第四章基于s u p e r i m p o s e dc o d e s 算法的路由协议 中v 表示拓扑中的所有节点，e 表示拓扑中的所有边，c 表示某个节点的信道编码字( 用 0 1 来表示主信道次信道) 。在信道编码中n xl v i 是作为布尔矩阵来和g 相关联。u 表示 单个节点( u v ) 。x ( u ) 表示u 节点的主、次信道集；n ( u ) 表示u 节点的所有干扰节点的集。 m ( u ) 表示u 节点的所有干扰信道的集( m ( u ) 是通过把n 。( u ) 和n 。( u ) 所有工作信道相并后 所得结果) ，其中u 仨m ( u ) ，n 。( u ) 和n 。( u ) 分别表示u 的l 跳邻节点的集合和2 跳邻节点 的集合。t 列( s 、l 、n ) 编码中n 表示可利用的正交信道，s 表示单个节点的干扰节点数。 u 节点所选编码字x ( u ) 是根据m ( u ) 和矩阵a 计算得出的，然后u 节点依据下面的3 种情况 来选择通信信道。 ( 2 ) 求节点的主、次信道( 为新加入的节点) ： 求的x ( u ) 需要从3 种情况考虑： 1 u s 择在x ( u ) 中没有使用过的主信道的集作为x ，( u ) ； 2 如果没有情况1 下的集，就选在x ( u ) 中没有使用过的次信道集作为x 。( u ) ； 3 如果情况1 和2 都没有，则选与x ( u ) 相同主信道的集作为) 【3 ( u ) 。 下面根据图4 - 1 举例说明： 假设节点为u 和n ( u ) = v ，w ，y ，选x ( u ) = x ( 1 ) ，如果x ( v ) = x ( 2 ) ，x ( w ) = x ( 3 ) ，和 x ( y ) = x ( 4 ) ，根据a 情况x l ( u ) = l ，1 0 ) ，u 可选主通道1 和1 0 作为通信信道，则u 和其邻 节点不会产生干扰。如果n ( u ) = v ，w ，y ，z 。x ( v ) = x ( 3 ) ，x ( w ) = x ( 1 0 ) ，x ( y ) ：x ( 1 2 ) ，和 x ( z ) = x ( 1 3 ) ，根据b 情况就没有主信道分配给u 但u 可选次通道 5 ，7 ) 作为通信信道则u 和其邻节点也不会产生干扰。如果n ( u ) = v ，w ，y ，z ) ，x ( v ) = x ( 4 ) ，x ( w ) = x ( 1 0 ) ，x ( y ) = x ( 1 2 ) ， 和x ( z ) - x ( 1 3 ) ，根据c 情况u 会全是干扰信道，u 可选主通道 l ，2 ，4 ，l o ) 作为通信信道。 s u p e r i m p o 。dc o d e s 路由算法的思路：根据d s r 路由发现来搜索路径，再按照路由判 据选择路径。在选择路径时，路径中每个节点的接口和相连接的节点要有通信信道，就用 s u p e r i m p o s e dc o d e s 算法来选择通信信道，一旦选好路径，利用a c k 消息使路径中每个节 点的接e l 都要与各自的通信信道相绑定且每个节点有各自的信道编码字，信道和信道编码 字是根据s u p e r i m p o s e dc o d e s 路由算法计算得出来的，再通过路由协议来交换节点的信息。 该路由算法的核心是直接和m a c 层内的子信道列表相关联，可减少干扰。随着p h w 阳 m a c 层进一步的研究，子信道的细分就会有足够数量的信道数。该算法直接用于第1 种情 况下，各节点之间的干扰将大幅度减少。 路由算法和路由协议的相结合的基本原理是：首先在我们的网络模型( 图1 - 1 ) 中只 考虑双向传输，w r w 和w r 都有统一的s u p e r i m p o s e dc o d e s 和自身与邻节点的信道编码 字，w r w 有一个网络拓扑图和s u p e r i m p o s e dc o d e s 。当新增加一个w r 时，其邻节点会 2 6 南京邮电大学硕士研究生学位论文第四章基于s u p e r i m p o s e dc o d e s 算法的路由协议 把该信息传给w r w 并传给新增w r 节点s u p e r i m p o s e dc o d e s ，w r w 则更新拓扑图，新 增w r 则根据邻节点的信道编码字计算出自身信道编码字，然后w r 的邻节点更新相关信 息；当减少一个w r 时，其邻节点会把该信息传给w r w ，邻节点和w r 会更新相关信息。 4 1 3 理论分析 定义4 1 ：如果x 、( u ) o ，则节点u 就不会和n ( u ) 中的所有节点产生干扰。 证明：当x 。( u ) g ，u 所选的信道属于x ，( u ) 的主信道的子集，这些信道是n ( u ) 中所 有节点的次信道。而对于v v n ( u ) 不能用x ( u ) 的主信道，因为v 也只用x 。( v ) 中的主信道 且u n ( v ) ，v 所选信道也是u 的次信道，所以u 和v 节点间无干扰。 定理4 1 ：如果x 。( u ) 囝( v t i e v ) ，n ( u ) 是节点t l 的干扰节点的一个子集，所以根 据定义4 1 计算所得信道能确保在网络中无干扰。 定理4 1 指出如果网络中每个节点都计算出一个主通道并把其作为传输信道，且该主 通道是干扰节点的次信道，就能实现整个网络无干扰。 定义4 2 ：如果x 。( u ) = g ，x ：( u ) a ，则节点u 也不会和n ( u ) 中的所有节点产生干扰。 证明：x 。( u ) = a ，x 。( u ) o ，u 所选的信道来自x 。( u ) 的次信道的子集，这些信道是 n ( u ) 中所有节点的次信道。如果n ( u ) 中所有节点所选的信道只是自身编码字中的主信道， 则u 和n ( u ) 中所有节点也不产生干扰。( 注意： u v n ( u ) ) 中只能有一个选次信道作为传 输信道的节点) 定理4 2 ：如果s i n ( u ) i 且n ( u ) 是节点u 的干扰节点的一个子集，根据定义4 2 计 算所得信道能确保在网络中无干扰。 在情况1 下不会产生干扰，上面论述另在两种情况下整个网络无干扰的情况并作了证 明。通常我们希望达到这三种情况，在理论上是可以实现的，但实践要滞后于理论。如在 w i f i 中信道数较少、射频接口数不够，还有受地理位置的影响，因此存在n ( u ) s 的情况。 在参考文献 1 0 、 1 1 中分析了这种情况并计算出在n ( u ) s 的情况下相互干扰的概率。 nf 弋f 一 p ( x ( u ) = 刀，x ：( u ) = o ) = p ( m 2 0 i n ( u ) ) 2 兀( 卜普) ，l i l j 其中j 。= n ( u ) ，t 表示，元表示。 南京邮电大学硕士研究生学位论文 第四豪基于s u p e r i m p o s e dc o d e s 算法的路由协议 图4 2 选择三种情况中信道的概率 图4 - 2 能很直观地反映出随节点的干扰信道数的变化，在3 种情况下选信道的概率。 其中，in ( u ) i 节点u 的干扰信道数；p l = p x 。( u ) a ) ； p 2 = p x 。( u ) = a ，x ：( u ) f 2 j ) ；p 3 = p x 。( u ) = g ，x ：( u ) = g ) 。 4 2 路由判据 4 2 1 预期传输时间( e t t ) 在提出预期传输时间( e 订) 前，首先简短地描述e t x 准则。e t x 度量准则用于测量 传输的预期数量，包括重传( 需要在链路上发送一个单播分组) 。e t x 的推导开始于前向 和反向的分组损失概率的测量，分别用p f 和p ，表示，然后计算预期传输数量。 从计算分组传输不成功概率开始。因为m a c 协议需要的是传输成功，所以分组必须 成功地被应答。让p 表示从x 到y 的分组传输不成功的概率： p = l 一( 1 一p j , ) x ( 1 一p ，) ( 1 ) m a c 将会重传一个传输不成功的分组。让s ( k ) 表示分组从x 到y 经k 次尝试 后成功发送的概率。 s ( k ) - - p 卜1x ( 卜p ) ( 2 ) 最后，从x 到y 成功地传送一个分组所必需的预期传输数量用e t x 表示： 2 8 南京邮电大学硕士研究生学位论文第四章基于s u p 州m p o s 。dc o d e s 算法的路由协议 脚= k = l 舨m ) 2 南 ( 3 ) 土 p e t x 准则用于路由选择。将选择最低的积累e t x 的路径。但是e t x 准则不一定能 为无线m e s h 网络选择较高吞吐量的路径。例如，它可能选择8 0 2 1 1 b 链路，但不选损失 概率比较低的8 0 2 1 l a 链路。在文献 1 7 中，作者给出了一个信道差异性优先选择，提供 了一种新的准则，称为预期传输时间( e 订) 。它定义为“带宽修正e t x ”。让s 表示分 组的大小( 例如1 0 2 4 个字节