（通信与信息系统专业论文）基于多信道多接口无线mesh网络研究.pdf

塑蔓 ! i 掣必必燃一 摘要 无线m e s h 网络的研究目前在全球越来越活跃，而多信道多接口无线m e s h 也 越来越受到重视，无线m e s h 的m a c 协议与路由协议是无线m e s h 的研究热点， 而现在最大的技术瓶颈却在m a c 层，已有的无线接入机制无法使得无线m e s h 最 大限度的发挥自己的技术优势。而无线m e s h 网络m a c 层研究的主要就是多信道 的接入与分配机制，让无线m e s h 网络达到高吞吐量，低延迟的标准来满足日益增 长的市场需求。i e e e 8 0 2 1 l 标准定义了多个不重叠的物理层信道。但是现在大多 数的无线m e s h 网络是在单一信道下工作，无线频段所提供的总带宽没有被充分利 用。 为了满足高吞吐量的需求，采用多信道多接口工作机制来提高网络容量。解决 热点地区业务负荷过载的问题。在n s 2 平台下实现多信道多接口的工作方式，采 用随机地信道分配机制。多信道多接口机制对于隐藏节点与暴露节点问题得到了 进一步的解决，将热点区域内的信道冲突问题得到有效降低，有效地提高了网络 容量。并运用n s 2 网络仿真软件对改进的多信道多接口的无线m e s h 网络进行了 仿真，仿真结果证明，多信道多接口在提高网络容量方面的有效性。 关键字：无线m e s hm a c 协议i e e e 8 0 2 1 1网络吞吐量多信道多接口 a b s t r a c t 1 kr e s e a r c ho fw i r e l e s sm e s hn e t w o r kb e c o m em o r ea n dm o r ep o p u l a r a n dt h e m u t i - c h a n n e lm u t i i n t e r f a c em e c h a n i s mp l a y sa ni m p o r t a n tr o l ei nt h ef i e l do fm e s h n e t w o r k 。t h em a ca n dr o u t ep r o t o c o lh a v eh i g h e rr e s e a r c hv a l u ew h i c hi st h em o s t d i f f i c u l tp r o b l e m n o we x i s t e dm a cp r o t o c o l sh a dm u c hd i s a d v a n t a g e ，c a n td e v e l o p i t s o w na d v a n t a g et ot h ec a p a c i t y n o w , t h ew i r e l e s sm e s hn e t w o r k 谢吐im u l t i c h a n n e l a n dm u l t i i n t e r f a c ei st h em o s ti m p o r t a n tm e c h a n i s mr e s e a c h e d t h i sm e c h a n i s mh a v e h i g h e rt h r o u g h p u ta n dl o w e rd e l a yf o r t h ei n c r e a s i n gm a r k e t i e e e 8 0 2 ii s t a n d a r d d e f i n em u l t i p l ec h a n n e l sw h i c ha r en o to v e r l a p e d b u tt h ew i r e l e s sm e s hn e t w o r ko f t e n w o r ki ns i n g l e - c h a n n e l ，i td i d n tt a k ef u l lu s eo ft h es p e c t r u m i no r d e rt os a t i s f yt h eh i g h e rt h r o u g h p u td e m a n d , w et a k et h em c m im e c h a n i s m i t c a ns o v l et h eo v e r l o a dp r o b l e mi nh o t s p o tf i e l da n dt h ep r o b l e mo fh i d d e nt e r m i n a l s t h i s m e c h a n i s mu s er a n d o mc h a n n e la l l o c a t i o n c h a n n e lc o n f l i c tw a sa v o i de f f e c t i v e ，i p r o v e t h et h r o u g h p u ta n ds a t i s f yi n c r e a s i n gd e m a n d w es i m u l a t e dt h em o d i f i e dm c m l w i r e l e s sm e s hn e t w o r k 晰也n s 一2 ，t h es i m u l a t i o nh a v eg o o dr e s u l ti nt h r o u g h p u ta n d d e l a y k e yw o r d ：w i r e l e s sm e s hm a cp r o t o c o l i e e e s 0 2 1 1 t h r o u g h p u tm c m i 第一章绪论 第一章绪论 1 1 无线m e s h 网络架构介绍 无线m e s h 网络( w m n ，w t r e l e s sm e s hn e t w o r k ，无线网状网) 是一种高容量 高速率的多点到多点的无线多跳网络，每个用户节点在收发业务时可以转发其他 用户节点信息，具有自配置，自组织与自管理性。为解决“最后一公里 宽带无 线接入问题提供的新的解决方案。由于本身所具有的高速率、易组网、成本低、 性能稳定等优势，已经引起人们的日益关注。无线m e s h 网络和智能天线、a d h o c 网络以及超宽带技术一起，正在成为无线通信领域中举足轻重的技术，对无线通 信领域将产生重大影响。 早在2 0 世纪9 0 年代中期，无线m e s h 网络概念就已提出，无线m e s h 网络是 在a d - h o c 网络的基础上发展而来。m e s hn e t w o r k 公司开发了一系列具有自主知 识产权的w m n 产品，在市场上引起巨大反响，2 0 0 5 年，m o t o r o l a 看好w m n 技 术，收购了m e s hn e t w o r k 公司。n o k i a ，n o r t e ln e t w o r k s ，t r o p o s 等等众多公司纷 纷投入大量精力在w m n 上。由此可见无线m e s h 技术的前景。 为提高m e s h 网络的灵活性，通常无线m e s h 网络路由器有多个接口，每个接 口可以自主配置。与传统的无线路由器相比，m e s h 路由器在性能上有很大提升， 不仅增加了多跳的路由功能，还在m a c 协议上也有很大改进。 w m n 网络包含两种节点类型：w m n 由客户端与m e s h 路由器。一般根据节点 不同分为三类：骨干网m e s h 结构( 分级网络结构) 、客户端m e s h 结构( 平面网 络结构) 与混合结构【2 引。 1 1 1 平面网络结构 所有的终端都是对等的，具有一致的特性，即每个终端均包含相同的m a c 协议、 路由协议，管理、安全协议，既具有客户端的功能，又具有转发业务的路由器功 能。这种结构适用于终端数较少且不需要接入到核心网络的应用场合。也称为终 端网络结构。这时网络中的终端节点具有m e s h 路由器增强功能。他们可以自己连 接成一个网络。节点可以相互移动，动态拓扑，两个无法直接通信的节点可以借 助其他终端分组转发进行数据通信。事实上，这是a d h o e 网络结构模式，可以在 没有或者不便利的情况下利用现有通信终端组网提供一种通信支撑环境。 如图1 1 1 所示为w m n 最简单的一种结构平面结构。 2 基于多信道多接口无线m e s h 网络设计 图1 1 1w m n 平面结构 1 1 2 分级网络结构 如图1 1 2 所示为典型的w m n 多级网络结构，分为上下两层。这些终端节点 通过上一层的m e s h 无线路由器来接入上层网络，是网络节点的互联互通。 糸 a p 图1 1 2 w m n 多级结构 这种结构通过a p 与移动终端进行通信。移动业务终端通过m e s h 路由器的转 发数据信息到网关节点，经过路由选择，无线m e s h 路由器为终端节点与目的节点 通信选择最佳路由。再经过网关节点，移动终端就可以与通信网络相连接，通过 这种方式实现无线网络的接入。这样的m e s h 网络架构不仅降低了通信系统的初期 建网成本，也提高了无线通通信系统的覆盖率和通信的可靠性。优点就是市场上 有兼容的设备，缺点就是两个终端之间不可以直接通信。 第一章绪论 3 1 2 3 混合网络结构 混合网络结构是在多级结构的基础上实现了终端之间的互联互通功能，可以根 据网络情况来选择合适的接入模式了连到终端。是平面结构和多级结构优势互补 的结合物。因此支持混合网络结构的设备之间就可以以多跳方式进行无线通信； 移动终端不仅可以直接通过无线宽带接入网络，而且可以与其他移动终端直接通 信；还可以充当路由器的功能，转发其他节点的数据。所以无线m e s h 网络不仅可 以当做w l a n 与移动a d - h o c 网络相融合的一种网络，也可看作是无线版本的 i n t e m e t 。 图1 1 3w m n 混合结构 传统的无线局域网是一种单跳的无线接入网络，网络中的移动终端节点都拥有 一个a p ( 无线接入点) ，a p ( 无线接入节点) 和骨干通信网络直接相连。移动终 端( m s ) 想要接入网络的话，通过一系列算法选择最优a p 就可接入网络。w m n ( 无线网状网) 可以实现多跳的路由功能，每个移动终端可以充当两个角色，a p ( 无线接入点) 和无线路由器。充当a p ( 无线接入节点) 时，移动终端可以通过 a p 接入网络；充当无线路由器时，移动终端之间可以直接进行通信，实现路径选 择和数据转发的功能。根据节点实现功能的不同，这种无线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 网关节点来 4 基于多信道多接口无线m e s h 网络设计 进行转发。 普通的无线m e s h 网络架构如图1 1 4 所示：整个网络由g a t e w a y ( 网关) ，m e s h a p ( m e s h 接入点) ，移动业务终端组成，通常a p 具有无线路由器的功能。 图1 1 4 无线m e s h 的网络结构 1 2 无线m e s h 关键技术及特征 作为一种新型的宽带无线接入技术，w m n ( 无线网状网) 相比当前已经被广 泛应用的传统无线局域网技术具有多项优势，无线m e s h 网络的特征主要有： l 、鲁棒性增强。由于w m n ( 无线网状网) 分布式控制功能的优势，因此避 免了的星型结构多种弊端，例如p c f ( 点协调功能) 中出现的网络拥塞，干扰， 单点故障，并且还需要大量的投资来保证可靠性。 2 、冲突保护功能。在w m n ( 无线网状网) 中，可以标识通信链路的状态， 通过链路状态标志，来鉴别通信链路质量的优良，因此选择最符合业务要求的通 信链路。选择与自身成钝角的通信链路来进行通信，这样就可以减小冲突概率。 3 、简化的通信链路的设计。在w m n ( 无线网状网) 中，通常单跳无线通信 链路都比较短，所以不需要专门安装天线塔，天线可以安装在屋顶，电线杆和路 灯上，这样就会减少建网初期的投资成本，同时发射功率也随之降低，不同系统 的射频干扰和自干扰也相应的降低。 4 、网络覆盖范围大。由于w r ( 无线路由器) 和l a p ( 无线接入节点) 的引 入，业务终端可以随时，随地接入网络。与现有的无线网络比较，基站的通信范 第一章绪论 5 围也变大，使得频谱利用率也随之提升，通信系统的网络容量也会得到明显增加。 5 、组网灵活，维护方便。无线m e s h 网络建网初期只需在必要的地方加上w r 与a p 等设备，就可以立马接入网络，实现无线宽带接入。由于w m n ( 无线网状 网) 具有链路中断和局部扩容的路由选择特性，线路升级不影响网络的整体运行， 网络的可靠性大大增强。比传统网络功能更强大，更完善。 6 、投资成本低，风险小。w m n ( 无线网状网) 建网初期投入成本低，由于 大量a p 与w r 的使用，节省了大笔的基站建设费用。由于多跳的路由选择，可使 得一个a p 的覆盖范围也相应增加不少，对于小运营商来说，这是更好的_ 个快速 占领市场的技术。再加上在伸缩性，扩容性，自配置等领域的优势，对于投资者 来说，在短期内可获得利益。此外，w m n 一般采用非许可证频段，所以为用户省 下了服务支出。 关键技术： 无线m e s h 网络从理论上可以解决无线城域网( w m n ) 和无线区域网( w r a n ) 建 设中遇到的问题。但在实际中，无线m e s h 网络的应用不够广泛。主要是因为无线 m e s h 网络商用技术还不成熟。存在很多缺陷，随着w m n 路由跳数、节点数的增 加，网络容量会急剧下降。为了提高无线m e s h 网络的吞吐量，可以采用下列关键 技术： l 、智能天线【8 l 。全向天线通信覆盖范围小，增益不高，并且对全方位干扰，频 率复用率减小，浪费频谱资源。智能天线通过多组独立天线组成的天线阵列系统， 动态地调整波束的方向，是每个用户获得最大的主瓣，减小了旁瓣的干扰。对于 其它方向的干扰也比较小，覆盖范围也大大增加。提高了频率复用率，提高了网 络容量。 2 、o f d m 与m i m o 技术以及功率控制技术【9 】等。o f d m 和m i m o 都是高速无 线传输技术，可以用来提高无线m e s h 数据传输速率。o f d m 可以有效减少子信道 之间的相互干扰，对抗频率选择性衰落，如果没有功率和带宽限制，o f d m 可以 实现任何传输速率，但是实际中要受到带宽和功率的限制。m i m o 可以对抗多径 衰落，却无法应对频率选择性衰落，在不增加带宽和发送功率的情况下，可以成 倍地提高信道容量，提高频谱利用率。因此，m i m o + o f d m 正好互补，在不需要 增加发送功率和带宽的前提下提高数据的传输速率，同时还可以消除时延扩展带 来的负面效应。 3 、m a c 层接入和优化技术f l o j 。w m n ( 无线网状网) 中各业务终端是对等的， 相邻的业务终端共享同一个信道。m a c 接入机制的目标就是在公平的为各业务终 端提供可靠信道接入服务。m a c 协议还可以根据业务流进行业务分级，在m a c 6 基于多信道多接口无线m e s h 网络设计 层实现一定的q o s 保障。可以有效的提高无线m e s h 网络的性能。目前w m n 的 技术瓶颈就在于m a c 层信道接入方面，所以就显得异常重要。在数据传输中， p r e a m b l e 和h e a d e r 所占的传输时间越来越多，p a y l o a d 用的时间就相应减少，传输 效率降低。可以对m a c 技术进行优化，改变数据帧的结构，增加净负载所占比重， 减少管理检错所占字节数，大大提升网络的容量。 4 、路由技术。路由协议的设计目标是为数据流选择最佳的路径，路径度量 ( r o u t i n gm e t r i c ) 对路由协议的性能影响很大。无线m e s h 网络除了要考虑链路传输 质量，链路间干扰，还需考虑路由协议的容错性。路由协议还应进行流量均衡， 避免业务拥塞，充分利用现有的网络资源，提升了系统吞吐量。 5 、多信道多接口技术【l 】。i e e e8 0 2 1 l 规定了多个正交信道。传统的无线网络 只使用单信道单接口，没有充分利用这些正交信道，造成资源浪费。采用多信道 多接口的话，利用正交信道互不干扰的原理使冲突链路同时传输数据且不产生干 扰，这样的话，可以大幅度提高系统的吞吐量。 1 3 论文的整体安排 第一章主要概括介绍了无线m e s h 与i e e e 8 0 2 1 1 相结合的网络的发展现状，以 及通用的来提高网络容量的一些方法。 第二章主要对无线m e s h 的m a c 层协议回顾了一下，从w l a n 的c s m a c a 到d b t m a 协议，对d b t m a 协议进行了较为深刻的研究，利用m a t l a b 对 d b t m a 协议进行建模，并对其性能进行了仿真验证。深入研究了多信道协议 m m a c 的发展、算法、以及其通信过程。 第三章主要阐述我自己的信道分配策略与接口的转换方法，分析了多信道无线 m e s h 网络的容量，通过数学分析来论证无线m e s h 的可达容量。 第四章是本论文的重点，将我自己的想法通过n s 2 来实现，这就需要将n s 2 的底层代码进行修改来实现我所附加的功能。通过我自己的信道分配算法，以及 改造，在n s 2 下实现多信道多接口无线m e s h 的过程，并且对三个场景进行了仿 真，并对结果进行了分析。 第五章是对无线m e s h 网络进行了总结以及展望。 第二章无线m e s h 网络m a c 协议分析 7 第二章无线m e s h 网络m a c 协议分析 本章讨论删m a c 协议，在m a c 协议上，w 心承袭了i e e e 8 0 2 1 1 标准里的很 多技术，特别是i e e e 8 0 2 1 1 s 标准更是专门针对传统的8 0 2 1 1m a c 协议扩展成为 支持网状结构的新的协议，本章先总结8 0 2 11 m a c 协议的基础上，专门针对v o d n 的m a c 协议进行分析，对w 删m a c 协议的有个大的把握。 2 1i e e e 8 0 2 11 b a gm a c 协议 2 1 1基于8 0 2 1 1 的，a nm a c 协议 i e e e s 0 2 11 的m a c 协议和i e e e s 0 2 3 的m a c 协议非常相似，都是在一个共 享媒体之上支持多个用户共享资源，由发送者在发送数据之前先检测网络的可用 性。而采用的m a c 协议就是c s m a c a ( 载波侦听多址接入碰撞回避) 机制。 l 、载波侦听多址接入碰撞回避( c s m a c a ) m 3 机制 i e e e s 0 2 1 l m a c 协议是基于二进制指数退避机制策略的c s m a c a 机制。在 i e e e s 0 2 3 中通过载波侦听多址接入碰撞检测( c s m a c d ) 的协调完成。 c s m a c a 是一种先听后说的机制，通过a c k 信号来避免信息碰撞，即是，只有 当客户端收到目的节点返回的a c k 信号后才确认自己发送的数据流已正确的到达 目的节点。c s m a j c a 机制通过这种方法提供无线信道的共享接入，a c k 机制在 处理这种无线问题时效果很好。然而不管是对于w l a n 还是有线网都增加了额外的 开销。 过程如下：发送消息之前，移动终端( m s ) 首先探测信道是否空闲，且空闲 时间与i e e e s 0 2 1 1 的i f s ( 帧间间隔) 相比，如果信道忙，该m s 就延迟信道接 入，直到当前数据传输完毕。刚传输完毕时，由于等待数据传输的终端都在等待 这一时刻，所以碰撞发生的机率最高。为了减少碰撞概率，移动终端再次随机退 避，让随机碰撞计数器自减，直到值为0 ，与此同时，进行信道探测这时，如果 有一个业务终端的退避时间更短的话，那这个终端就取得了信道的使用权，其他 站点就会探测到信道忙，只能再一次延迟信道接入，否则发现信道空闲的话，就 接入信道，发送数据信息。 在探测过程中，移动终端有两种信道探测方法，一个是物理载波检测，另一个 是虚拟载波检测。虚拟载波检测体现的是信道将来占用情况的信息。有两种方法 实现：一是r t s c t s 机制，即在传输信息数据前交换r t s c t s 帧信息，采用4 次 握手。r t s c t s 帧包含一个d u r a t i o n i d 域，它标志着下一刻信道空闲时间的间隔， 8 基于多信道多接口无线m e s h 网络设计 即网络分配矢量n a v ，它定义了信道将来的占用情况。另一种方法是由点对点发 送帧的d u r a t i o n i d 域来确定。物理载波检测通过接收信号能量的强弱来确定信道 是否空闲，每当信道由空闲转为忙或由忙转为空闲，物理层( p h y ) 的子层都产 生一种基本单元_ p h v c c a i n d i c a t i o n ( s 咖) ，它有b u s y 和i d l e 两个参数 值。当物理子层检测到信道忙时，其值为b u s y ；反之，其值为i d l e 。图2 1 1 为信号的发送流程图。 e j 图2 1 1c s m a c a 信号流程图 i e e e 8 0 2 1 1 专门为退避时间( b a c k o f f t u n e ) 的确定规定了计算方程： b a c k o f f r i m c = r a n d o m 0 xa s l o t t i m e 其中r a n d o m o 是均匀分布于【0 ，c w 中的随机整数，c w 为竞争窗口，其取值 介于a c w m i n 和a c w m a x 之间，初始取值为a c w m i n ，每次发送不成功时，c w 值都双倍增加，直到a c w m a x 。这提高了重负荷条件下接口协议的稳定性。 a c w m i n 、a c w m a x 、a s l o t t u n e 为p h y 子层的服务基本单元一一 p l m e c h a r a c t e s t i c s 提供的p h y 子层特征值，在d s s sw l a n 中分别为 3lp m ，10 2 3 t i n ，2 0 p m 。 2 、隐藏终端问题 无线m a c 层存在隐藏终端问题。为了解决这个问题，i e e e 8 0 2 1 1 在m a c 层 上引入了一个新的r t s c t s 选项，发端发送一个r t s 信号，随后等待接入点回送 c t s 信号。由于网络中所有终端都能监听到接入点的信号，所以其他终端收到c t s 后就停止发送自己的数据，这样发端就可以发送数据和接受a c k 信号，避免数据 冲突，从而解决隐藏终端问题。由于r t s c t s 需要占用网络资源，增加了网络负 第二章无线m e s h 网络m a c 协议分析 9 担，所以只是在那些大数据分组上采用以上协议( 重传大数据分组消耗比较大) 。 图2 1 2 为使用r t s c t s 解决隐藏终端问题的过程。 沪叫 卜叫! 卜叫o 卜删 多 h c ，那么节点a 想要向节点c 发送一个数据包。第一步，由 于节点b 的固定接口时2 ，节点a 会在向节点b 发送数据包之前将它的可转化接 口从3 转化到2 。类似的，接下来一步，由于节点c 的固定接口时3 ，节点b 需要 将它的可转化接口从l 转化到3 来向c 发送数据包。一旦接口在流量初始化过程 第三章多信道多接口无线m e s h 网络设计 中被适当的建立起来，随后的数据流将在很长时间内不需要转换接口。如图3 1 4 所示： f i x e d = l f i x e d = 2f i x e d = 3 i n i t i a l ： s w i t c h a b l e = 3s w i t c h a b l e = ls w i t c h a b l e = 2 s t e p1 ： s w i t c h a b l e = 2 s t e p2 - s w i t c h a b l e = 3 图3 1 4 接口转换( 3 信道，2 接口) 固定接口信道分配： 正如图3 1 5 所阐明的，节点a 、b 、c 各自使用信道1 、2 、3 ；所有直接向 a 、b 、c 的传输都会分别在信道l 、2 、3 上进行。固定接口分配的目的是给固 定接口分配信道并且向相邻节点报告固定接口所使用的信道。首先，每个节点维 持两个数据表： 邻节点数据表( n e i g h b o r t a b l e ，n t ) - 包含相邻节点所使用的固定信道。 信道使用列表( c h a n n e l u s a g e - l i s t ，c u l ) ：存放信道的使用信息 流程图如下图3 1 5 所示： 是 图3 1 5 固定接口信道分配 基于多信道多接口无线m e s h 网络设计 假定三个节点的无线m e s h 网络，每个节点具有有三信道和两接口( 一个固定一 个可转换) ，这样的一个可视的例子来介绍【2 1 中提出的局部分配算法。如图3 1 6 中 所展示的节点表格实际上是n t 和c u l 的隐含的组合。 ( 1 ) 、每个节点设定一个固定信道。 八 ( c) u f i x e d = l 图3 1 6 节点选择随机信道作为他的固定信道 ( 2 ) 、周期性地，每个节点在信道上广播h e l l o 包或者路由查找包，它包含该节点 的n t 与c u l 信息表。如图3 1 7 所示： f i x e d = l f i x e d = l 盯包括了邻居节点已占用 的信道信息 f i x e d = 图3 1 7 节点定期通告自己的固定接口 图3 i 8 收到h e l l o 包，节点更新c u l 和n t ( 3 ) 、当节点接收到邻节点的h e l l o 包或者路由查找包时，它会对自身的n t 与 c u l 进行更新。如图3 1 8 所示： ( 4 ) 、节点周期性地查询自己的c u l 信息。 如果该节点与其他节点使用同一固定信道，那么这个节点将会以概率p 将它 的固定信道转换到一个使用得更少的信道。然后该节点发送好h e l l o 包来更新邻节 点n t 与c u l 信息。如图3 1 9 所示： =、 d 2 ； 一b 一 1 ， ， o 第三章多信道多接口无线m e s h 网络设计 n o d eb l 田c 2 3 n o d ea l b c 2 3 o f i x e d = l n o d eb l肥 2c 3 n o d ea l肚 2c 3 f i z e d = l 霞定c 节点要用2 信道，c 得自 b 发送信息告诉 m h e l l o n o d ec lj i b c 2 3 f i x d = l 假定b 节点要占用3 信道，广播 信息给邻居节点 n o d ec l肥 2c 3 f i x e d ：l f i i e 忱 n o d eb l肥 2c 3 n o d ea l肥 2c 3 f i x e d = l n o d eb la 2c 3b d ea l 2c 3 8 f i x e d = l f i x e d = l 广播后，c 节点的干扰接口转 换到2 信道，并且更新信道稠 用信息 n o d ec l肥 2c 3 f i x e d 目广播后，b 节点转换至3 信道， 并且更新信道利用信息 n o d ec l 2c 3b o f i 抛 图3 1 9 节点定时更新c u l 可转换接口分配： 正如前面所提到的，不论目标节点的固定信道是否和节点x 的固定信道相同， 可转换接口都被用来从节点x 发送数据。如下图所描述，每个节点为每个信道维 持一个单独的包队列。如图3 1 1 0 所示： 图3 1 1 0 每个节点维护数据包队列 固定信道分 配 可变信道分 配 基于多信道多接口无线m e s h 网络设计 可转换接口的分配规则： ( 1 ) 、当链路层接收到一个单播包要发送时 该节点将会在n t 中查找数据包目的地的固定信道。如果发送者和接收者有相 同的固定信道，将数据包入队到固定信道。否则，将其入队到可转换信道。至于 广播数据包，节点将它复制到每一个信道的队列中。当该信道被安排发送数据时， 数据包将会被发送出去。 ( 2 ) 、当有数据包在另一个信道排队时，可转换接口将会改变信道。 如图3 1 1 1 所示t 3 1 2 接口的转换 是 是 i l ， i 材发i i一 图3 1 1 1 可转换接口流程图 在n s 2 的a o d v 路由中所实现的接口转换算法，举例如下：一个链式拓扑 中有4 个节点，3 条信道( 0 ，l ，2 ) 和2 个接n ( 0 ，1 ) ，图3 1 1 l 演示了算法的过 程。图中所示的符号意思： n t 【n 】是n e i g h b o rt a b l e 表示节点n 使用固定信道； c u l c 是c h a n n e l u s a g e l i s t 表示使用信道c 作为固定信道的节点的数量； f c 表示固定信道正被节点用于从相邻节点接受数据； s c 表示可变信道正被节点用于向相邻节点发送数据： 零 第三章多信道多接口无线m e s h 网络设计 纱5 “。 “8 二 n o d e0n o d e1n o d e2n o d e3 n t 1 = 0n t 2 3 = 2n t 3 = l c u l 0 = lc u l 2 = ic u l 1 】= l i n i t i a l l y c n t | i 。r 2 3 2 - - 2 i、le：-2sc=0_ f c = of c = 2f c = i s c = 2s c = 0s c = 2 | i n t 2 = 2 s t e p1 mn=o1cul0芝=霎icule23 m n t 卜=。2、2ulo=icul2=2褥 n t 3 = l c u l o = l 、一c u l 1 = l = l c u l 2 = l n t 1 = o n t 2 = 2 | s t e p2 1 = o 形l 0 钐 m n = 2 3 c u l 1 0 c u l c u l 2 = 2 n t 3 = l 。 = 、 = l 卅尸c u l o = i c u l l 2 = 2 l 1 = 1c o l h j = l t ， c u l l 2 = 2 n t o = 1n t 1 ：0 n t 2 - - 2 s t e p3 nh ，v ( g ) ，表示图g 的节点集合，节点数为p 1 。 ( 2 ) e ( g ) = e l ，e 2 ，岛，) ，表示图g 的边的集合，边数为p o 。其中q 为 n ，u ) 或者 。若q 为川，v ，则称巳为和u 为端点的无向边；若岛为 ，则称q 为v f 为起点，为终点的有向边。 ( 3 ) ( g ) ：e _ v x v 表示关联函数。 边e = 铷，v ) 连接节点 和v ，记为e = l n ，称为u y 与节点“和v 相关联，节点“ 和1 ，称为邻节点。如果两条边共用一个节点，则表示这两条边为是相邻的；如没有 边和节点相关联，则表示此节点为孤立节点。 定义2 ：节点1 , 1 的邻居节点集表示为n g b d ( u ) = ，：l n ，e ( g ) ) 。 第三章多信道多接口无线m e s h 网络设计 3 l 与节点1 ，相关联的边的数目用1 ，v ( g ) 的度d e g ( v ) 来表征，因此 d e g ( v ) = 2 q v e v ( g ) 节点的最小度定义为：8 ( g ) = m i n d e g ( v ) ：v 矿( g ) 节点的最大度定义为：a ( g ) = m a x d e g ( v ) ：vy ( g ) 式( 3 2 2 ) 定义3 ：有向图的每条边都是有方向的，无向图的每条边都是无方向的。 定义4 ：起点和终点重合的边叫做环。如果与一个节点相连的边的数量大于l ， 则这个边叫做多重边。没有环和多重边的图叫做简单图。完全图就是每一对不同 节点都有一条边相联的简单图。 定义5 ：设u 和1 ，是图g 的顶点，图g 的一条”一v 链是有限的顶点和边的交替 序列g o e l u l e 2 “2 e 3 u n _ l e n u 。 = u o ，= “。) ，其中u l - l 、+ l 为与边乞( 1 f 订) 是相邻端 点。对于一条甜一v 链，当甜1 ，时，称它是开的，否则是闭的。 定义6 ：任意图g 中，有一条链，链中各内部顶点不同，链的两端点相同，则 该链称为循环。若链中出现的边数为k ，则称该链为k 线循环。 定义7 ：若把简单图g 顶点集合分成两个不相交的非空集合k 和坎，使得图g 中的每条边与其关联的两个节点分别在k 和k 中，则称为双向图，记做 g = 。节点集k 和k 中各自节点度数相同的双向图称为规则双向图，否 则称为非规则双向图。 对于一个二分图g = ，设k = “毛黾毛 ，k = 挑照乃见，作为 m x n 阶矩阵a = ( ) ，其中，若咒与x ，相连，口：f ，= l ；否则，= o 。 定义8 ：如果图h 中的节点与边分别是图g 中的节点与边，则h 是图g 的子 图，如果图h 包含图g 中的多有节点，则称h 为g 的生成子图。 如果节点1 1 ，y ( g ) 之间有一条路径，则称u 和，是相连的。如果图g 中任意 节点都是相连的，则图g 是连接的，称为连通图。 如果q ( p 一1 ) ( p - 2 ) 2 ，则图g 连接： 另外，存在下列基于图的局部结构参数的结论： 如果6 ( g ) p 2 ，则a ( g ) = a ( g ) ；如果8 ( g ) = p - 2 ，则k ( g ) = a ( g ) ；如果 艿( g ) ( p + n - 2 ) ，1 甩p ，贝0g 是n 连接，即七( g ) n 。 基于图的无线m e s h 网络连通性： 将w m n 抽象成随机图q ( 拧) ，其中n 为图中节点总数，p 为节点连通的概率。 图q ( 疗) 中设定链路是相互独立互不影响的，直接连接的节点的数目叫做节点的 度。图中每个节点的度服从以下分布，如式( 3 2 - 4 ) ： 3 2 基于多信道多接口无线m e s h 网络设计 州，= 旷计h 百7 , k e - z 式( 3 - 2 - 4 ) 在研究w m n 的连通性时，可将无线网状网的网络拓扑看成具有固定拓扑的 图。如果图中任两节点间存在k 个独立的互不影响的路径，该图就被称为k 连通 图。对于w m n 的基于图的连通性有以下推理。 定理1 ：将无线网状网看做是有万个节点和o 个边的图，依次逐一加入边，直 到具有m 条边，当满足m 刀l o g ) 2 + 0 ( ) 时，则无线网状网就是全连通的网络。 定义p ：朵，满足条件时，删就是全连通的网络：p 坚掣时，无线网 f 刀l 行 l 2 一j 。 状网的连通性决定于通信设备的密度和通信覆盖范围的半径。 定理2 ：当无线网状网节点数比较多时( n 、n ) ，若终端的通信范围为r o ，通 信终端的分布密度为p ，则无线网状网图中k 连通的概率如式( 3 - 2 5 ) ： p r q 】_ p r 【k 】 式( 3 - 2 - 5 ) 同时有 州渊= 噍咩盯耐丁 式( 3 - 2 - 6 ) 基于渗透理论的无线m e s h 网络的连通性： l 、渗透理论中的布尔模型 ( 1 ) 无线终端节点按照泊松分布过程分布； ( 2 ) 当两个节点的距离小于等于其发射半径时，能相互连接。 在半径为，2 的通信范围内，两个节点的的距离是指数分布的，他们之间的距 离为x ，泊松分布指数为a ，则两个节点连通的概率为：x 增大时，连通概率按 照指数规律递减： 闰 旧一1 。 脚) ：曼丝等趔矿笠丝垫型州叫矿1 ( 3 2 7 ) 定理3 ：在二维网中，通信范围为r ，通信节点的密度为见。，且当通信终端的密度 a a 时，网络处于非连接状态。当通信终端密度a a