无线网络中的信道分配和路由算法研究

摘要

无线mesh网络由无线路由器和无线接入点通过多跳连接的方式组成，具有传输速率较高、覆盖范围较广和组网成本较低等特点，是解决无线终端接入Internet的一种比较有竞争力的技术方案。无线链路的传输速率因链路干扰问题而降低，目前降低干扰的一种有效方法是采用正交信道传输数据，在802.11a/b/g等标准中定义了不同数目的正交信道，研究如何有效利用正交信道提高网络吞吐率具有十分重要的意义。 本文基于IEEE 802.11 MAC协议，围绕如何提高无线mesh网络吞吐率这一问题，开展了以下研究工作： 针对目前已有的集中式静态信道分配算法在大规模无线mesh网络中存在的可扩放性问题，提出了基于链路负载信息的分布式信道分配算法——LLDCA算法。该算法通过分布式构建链路冲突图，使同一冲突域内数据传输量较大的链路优先选择干扰程度较低的信道，互不干扰的链路间能够并行选择信道，从而较大降低了链路分配所需要的轮数。理论分析表明，对任意给定的正整数t，该算法在O(Log n)+t+1轮内结束的概率大于1-(D/D+1)<'t-1>，其中n为网络中数据传输量大于O的链路数目，D为链路冲突图的最大顶点度；各链路的消息复杂度为D(D)。模拟实验表明该分布式算法的性能与Raniwala等人提出的集中式分配算法的性能相当，与Group CA算法相比较能够将网络吞吐率提升3倍左右。 针对目前缺少统一的静态信道分配算法性能评价标准的问题，提出了基于“冲突链路带宽占用率”的性能评价模型，通过计算同一冲突域中每条链路所在信道的带宽占用率，量化了信道分配结果对每条链路的影响，该模型能够较好评价各种静态信道分配算法的性能。基于该评价模型，提出了使用“网络拓扑控制”策略优化静态信道分配的算法，根据“冲突链路带宽占用率”的计算结果判断是否使用当前已有链路传输待分配链路的数据。模拟实验表明在网络中同时存在数据传输量较大和较小的链路时，该方法能够利用更多的正交信道，使网络吞吐率在LLDCA算法的基础上再提升10％以上。 针对混合式无线mesh网络中因少量节点在信道切换时存在较多冲突而影响传输速率的问题，提出了分布式信道切换序列生成算法——RCS算法。RCS算法采用随机置换策略生成新的切换序列，从而较好的分散了节点间的传输冲突，均衡了各节点的有效传输带宽。在RCS算法中，各网络节点的信道切换序列独立生成，有利于节点的动态加入和离开，其运行时间与正交信道的数目成线性关系，保证了信道切换序列生成的实时性。仿真实验表明，在网络负载程度达到75％以上时，该算法与当前同类算法相比能够将网络节点获得的有效带宽最小值提升30％以上，网络总吞吐率提升5％～15％。针对目前基于混合式策略的信道分配算法未考虑各节点数据传输量差异从而导致信道负载不均的问题，提出了负载平衡的分布式信道分配算法——LBCA。通过分布式构建节点局部冲突图，使处于同一冲突域中数据传输量较多的节点优先选择负载较小的信道，从而较好平衡了各信道负载。模拟实验表明，在网络负载程度达到80％以上时，对可用信道数目不大于6的网络，LBCA算法获得的网络吞吐率与当前相关算法相比提升了10％以上。 针对当前多信道路由度量标准在网络中数据流的数量较少时，不能够充分利用网络的可选路径和信道资源问题，提出了一种基于“跨层设计”的按需路由和信道分配算法。该算法综合考虑路由问题与信道分配问题，首先利用目前已有的多信道路由度量标准使用按需路由策略寻找最小传输时延路径，然后为该路径上的相邻链路尽量分配互不相同的信道，从而降低了路径上相邻链路间的干扰，提高了网络吞吐率。模拟实验表明，在信道数目为12且“源节点”和“目的节点”总数量占网络总节点数的比例小于50％时，该算法与当前同类型算法相比，能够将网络吞吐率提升10％～20％。 针对当前的无线mesh网络结构难以有效解决在网络中存在大量网内和网间数据流时的数据有效传输问题，提出了一种新型的混合式无线mesh网络结构。在该结构中，根据节点距离固定网络接入点的距离，将网络划分为静态mesh区域和动态mesh区域；并基于该网络结构提出了一种新型的路由算法，采用将反应式路由协议和先验式路由协议相结合的方法，较好解决了在网络中同时存在上述两种数据流时的数据有效传输问题。模拟实验表明，在信道数目为12并且访问固定网络产生的数据流占网络总数据流量的60％～80％时，与当前已有的mesh结构相比，该新型mesh结构能够将网络吞吐率提升15％以上。

目录

文摘

英文文摘

声明

第一章绪论

1.1无线mesh网络概述

1.2无线mesh网络关键技术

1.3本文研究内容和研究思路

1.4本文组织结构

第二章多信道无线Mesh网络

2.1多信道通信技术简介

2.2多信道分配算法的研究现状

2.2.1多信道分配算法的技术难点

2.2.2多信道分配算法的相关工作

2.3多信道路由算法的研究现状

2.3.1多信道路由算法的技术难点

2.3.2多信道路由算法的相关工作

2.4多信道调度算法的研究现状

2.4.1多信道调度算法的技术难点

2.4.2多信道调度算法的相关工作

2.5多信道无线Mesh网络结构设计的研究现状

2.5.1多信道无线Mesh网络结构设计的技术难点

2.5.2多信道无线Mesh网络结构设计的相关工作

2.6本章小结

第三章分布式静态信道分配算法

3.1信道分配问题描述

3.1.1静态无线Mesh网络模型

3.1.2信道分配问题描述

3.1.3传输干扰模型与链路冲突图

3.1.4信道分配问题与染色问题的关系

3.1.5信道分配算法的目标

3.2分布式静态信道分配算法的设计

3.2.1分布式分配的思想

3.2.2分布式算法描述

3.2.3算法的复杂度分析

3.2.4信道分配算法的性能评价模型

3.2.5网络拓扑控制与信道分配优化

3.3仿真实验

3.3.1算法的计算时间模拟

3.3.2传输性能模拟与分析

3.4本章小结

第四章混合式Mesh网络信道切换和信道分配算法

4.1信道切换序列生成问题

4.1.1信道切换序列生成问题的描述

4.1.2信道切换序列生成算法的目标

4.2固定接口卡的信道分配问题

4.2.1问题描述

4.2.2信道最优分配问题与图的顶点染色问题的关系

4.2.3问题复杂度分析

4.3分布式信道切换序列生成算法

4.3.1信道切换算法的思想

4.3.2信道切换序列生成算法的描述

4.3.3算法复杂度分析

4.4负载平衡的分布式信道分配算法

4.4.1信道分配算法的思想

4.4.2信道分配算法描述

4.4.3算法复杂度分析

4.5仿真实验

4.5.1切换序列生成算法仿真实验

4.5.2分布式信道分配算法仿真实验

4.6本章小结

第五章多信道Mesh网络路由算法

5.1路由问题描述

5.2按需路由和信道分配算法——ODRC算法

5.2.1 ODRC算法的思想

5.2.2 ODRC算法的描述

5.2.3算法复杂度分析

5.2.4 ODRC算法的讨论

5.3仿真实验

5.4本章小结

第六章一种新型的混合式无线Mesh网络结构

6.1对目前无线Mesh网络结构的分析

6.2一种新型的混合式无线Mesh网络结构

6.2.1新型Mesh网络结构的设计思想

6.2.2新型Mesh网络结构的具体实现

6.2.3基于新型Mesh网络结构的路由算法

6.2.4对新型Mesh网络结构的讨论

6.3仿真实验

6.4本章小结

第七章总结

7.1本文工作总结

7.2本文的主要贡献与创新

7.3下一步的研究工作

参考文献

致谢

在读期间发表的学术论文与取得的研究成果