【作者】 毕坤；

【导师】 顾乃杰；

【作者基本信息】 中国科学技术大学 ， 计算机系统结构， 2008， 博士

【摘要】 无线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为网络中数据传输量大于0的链路数目,D为链路冲突图的最大顶点度;各链路的消息复杂度为O（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%以上。更多还原

【Abstract】 Wireless mesh networks are comprised of a number of wireless routers and wireless access points which are connected to each other in a multi-hop manner. It has emerged as one of the promising solutions for next generation wireless networks because it could provide high-speed data rate, enlarge wireless service coverage area and reduce the network installation cost. The transfer rate of wireless links could be decreased by interference, so using non-overlapped channels for data transfer is an efficient way to lessen link interference. Different numbers of non-overlapped channels are defined in IEEE 802.11a/b/g standards and the network throughput could be increased effectively by utilizing those channels. Research on how to increase the throughput of wireless mesh network is of great significance.Based on IEEE 802.11 MAC protocol, the research work presented in this dissertation is mainly focused on how to improve the throughputs of wireless mesh networks.Firstly, considering the problem that current central channel algorithms have the scalability problem in large scale wireless mesh networks, a new link-load based distributed channel assignment algorithm （LLDCA） was proposed to assign channels to links. This algorithm constructed link conflict graph firstly in distributed way by exchanging the local link load information within its k-hop neighbors in the wireless network and then assigned channels to links according to the link load priorities in link conflict graph. Links that did not interference with each other could select channels concurrently, so the running rounds of LLDCA had been significantly reduced. Theoretical analysis shows that for any given positive integer t, LLDCA could finish in O（log n） + t + 1 rounds with probability higher than 1-（D/D + 1）^t-1 where n is the number of links whose loads are positive number in the network and D is the maximum node degree in the link conflict graph, and the message complexity of every link in this algorithm is O（D）. Simulation results show that this distributed algorithm has nearly the same performance as the central channel assignment algorithm proposed by Ashish Raniwala et al and it could improve the network throughput by a factor of three when comparing with Group CA algorithm.Secondly, a new performance evaluation model for channel assignment algorithms was proposed based on "conflict link bandwidth occupation rate". The impact of channel assignment result on each link was quantified by computing the channel bandwidth occupation rate of each link in its conflict area. This model could evaluate the performance of different channel assignment algorithms. Based on this evaluation model, a new algorithm was proposed to improve the static channel assignment algorithms by using topology control strategy. A decision was made by using this model before assigning a channel to a link. Simulation results show that this algorithm could improve the network throughput by a factor of 10% than LLDCA when the network consists of heavy-load and light-load links at the same time.Thirdly, considering the problem that the transfer rates of some nodes may be decreased due to their channel switching sequences being plenty of collisions with that of their neighbors, a distributed algorithm was proposed to generate channel switching sequences in hybrid mesh networks. A new sequence was generated in each round using random permutation method according to the node’s current switching sequence and it distributed the sending collisions among different node-pairs, so the useful bandwidth of every node was effectively balanced. Every node generates new sequences independently without any negotiation with its neighbors. This algorithm is insensitive to topology change, so it is convenient for nodes to join or leave the network dynamically. The algorithm’s running time is linear to the number of orthogonal channels in the network, so a real-time new sequence generation is guaranteed. Experimental results show that this algorithm could effectively improve the node’s minimum useful bandwidth by a factor of more than 30% and improve the network total throughput by a factor of 5%～15% when the network load increases to 75% of its capacity.Fourthly, by utilizing the load information of mesh nodes in hybrid channel assignment strategy, a load-balanced distributed channel assignment algorithm （LBCA） was proposed in this paper. A local node conflict graph was constructed in a distributed way and those heavy loaded nodes were assigned to light loaded channels by LBCA algorithm. In this way, the loads of every channel were balanced. Simulation results show that the network throughput could be improved by a factor of above 10% than that of state-of-art algorithms in mesh networks with no more than 6 channels when the network load increases to 80% of its capacity.Fifthly, a new joint routing and channel assignment algorithm using "cross-layer" method was proposed to optimize the network performance when the number of flows in the network was not large. The shortest path was discovered firstly using the current available routing metrics and then new different channels were assigned to those links. In this way, the interference on that path was minimized and the transfer rate was increased. Simulation results show that this algorithm could improve the network throughput by a factor of 10%～20% comparing with other state-of-art algorithms when the percentage of the summation of source and destination nodes is no more than 50%.Finally, a new network topology for organizing wireless mesh network was proposed to improve the network throughput when the network contains massive intra-mesh and inter-mesh flows simultaneously. The network was divided into two parts: the static mesh zone in which channels were assigned to mesh nodes statically and the dynamic mesh zone in which the channel assignment strategy was hybrid assignment method. A new routing algorithm was also proposed for the new network topology organization by combining proactive and reactive protocols. Simulation results show that the network throughput could be improved by a factor of 15% above comparing with tree topology and hybrid topology when the channel number of the network is 12 and the amount of inter-flow is of 60%～80% of the total network flow load.更多还原