【作者】 王钧；

【导师】 黄刘生；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2009， 博士

【摘要】 最近几年,作为宽带无线接入非常重要技术之一的无线Mesh网络(WMN-Wireless Mesh Networks)正倍受科学家和工程师的关注,它可以大大增加无线系统的覆盖范围,同时可以提高无线系统的带宽容量以及通信可靠性,是无线宽带接入的一个理想解决方案。使用WMN作为无线接入的骨干网激发了大量的无线带宽需求。但是,在并发传输之间的无线干涉使得网络系统的容量急剧下降。为了减轻无线干涉的影响,增加并发传输的带宽,两项新的天线技术被引入到无线mesh网络中:多信道多网卡技术(MCMI-Multiple Channel Multiple Interface)和多进多出天线技术(MIMO-Multiple Input Multiple Output)。MCMI技术在可能产生于涉的链路上使用多条互不重叠的通讯信道来最大化并发传输,提高系统的吞吐量。例如,IEEE 802.11b/g和802.11a标准可以分别使用3个或12个互不干涉的信道。同时,由于MIMO天线技术有着空间复用和干扰抑制的特性,因而在无线传输中使用MIMO技术是另一个可以减少干涉提高系统容量的方法。在这篇博士论文中,我们针对这两种技术,分别研究它们在无线mesh网络中的网卡(天线)配置,带宽分配和调度的相关问题:●由于增加了并发传输,避免了信道干扰,多信道多网卡的无线mesh网络有很大的潜力来提升网络容量,增加节点传输的公平性。但是,很多WMN的信道调度算法都提前假设了每个无线路由器中都平均配置相同数目的网卡。在第三章中,对于网卡配置和带宽分配问题,我们研究在保证节点应用基本需求的情况下,同时减少网络的构建成本并增加节点的吞吐量。我们提出每个节点甲均网卡配置方案不是必须的,也不是高效的,因为节点之间的干扰以及通讯负载的分布都是影响带宽并发使用的重要因素。在优化网络性能中,最大的挑战就是怎样能够定量的分析网卡配置,带宽分配和调度之间的内在关系。更进一步,我们对这些配置和调度的问题定义了新的问题空间。把复杂的多参数问题进行了分解和形式化成为定义良好的单阶段或多阶段分步解决的子问题。在使用线性规划方法给出最优解的同时,我们分析了网络传输和干涉的数学模型,提出了更高效的启发式算法。使得在网络结构不停发生变化,需要实时重新计算系统性能时,这些高效算法能提供在线的决断。通过大量的系统仿真,我们验证了这些算法能逼近线性规划得出的最优解。相对于平均的网卡配置方案而言,我们用更小的网络构建成本实现了系统性能的提升。●相对于传统的天线技术,由于有着空间复用和干扰抑制的特性,MIMO天线在提高网络容量上有很强的优势。为了更好的利用MIMO技术在并发传输上的特点,研究人员提出了大量网络跨层性能优化的算法以及MAC层的设计来增加无线mesh网络或是ad hoc网络的吞吐量。但是,这些研究都假设节点的天线阵列是给定的或是每个节点都使用同样的天线阵列(K×K,K为常数)。在第四章中,我们的研究表明在这些无线路由节点中,如果为每个天线阵列都配置同样多的天线单元对于提升系统性能来说并不是必须的。因为对于不同的路由节点,对天线单元的需求是不一样的;尤其是那些有着巨大的汇聚通讯流量的路由转发节点,更多的天线单元不仅能增加并发传输,也可以用来提高对周围无线干扰的抑制作用。基于这个观点,我们定义了天线单元配置,带宽分配和调度的联合问题,来定量的分析跨层优化方案对系统容量的提升。我们提出了一个代价相关天线单元配置技术(CAEA - Cost-Aware Element Assignment)来保证最优带宽分配的前提下,最小化天线配置的总成本。同时,为了验证CAEA配置的效率,我们设计了一个启发式的负载相关流控制链路调度算法(TSLS - Traffic-aware Stream-controlled Link Scheduling)来给出一个带宽分配的可行调度方案。大量系统仿真实验的数据验证了CAEA和TSLS算法的有效性。更多还原

【Abstract】 Recent years,Wireless Mesh Networks(WMNs) have emerged as a promising technology that provides wireless broadband accessibility and thus,extends the Internet connectivity at the edge and improves the network coverage and economy efficiency.Using WMN as a backbone for large wireless access imposes high bandwidth requirements.At the same time,the interference among simultaneous transmissions may dramatically cause capacity reduction.Fortunately,Multiple Channel Multiple Interface(MCMI) and Multiple Input Multiple Output(MIMO) are two of the new technologies introduced to mitigate interference and increase simultaneously transmissions.The first solution is to use multiple non-overlapping channels on the interfering links to maximize the parallel transmission and throughput.For example,IEEE 802.11b/g and 802.11a standards specify 3 and 12 non-interfering channels,respectively.The ability of using MIMO antenna technology in the wireless transmission is another major technique to alleviate the problem,and thus improve throughput substantially.In this dissertation,our research focuses on interface assignment,bandwidth allocation and scheduling for WMNs using both technologies,respectively:●With the ability of simultaneous transmissions,MCMI WMNs have emerged with great potential in the improvement of network throughput and fairness. However,most proposed channel assignment algorithms for WMNs made an assumption that the Network Interface Cards(NICs) are evenly assigned to the mesh touters.In Chapter 3,we investigate the problems of NIC assignment and bandwidth allocation to minimize the infrastructure cost, and meanwhile guarantee the application requirements.We argue evenly assigning NICs to all routers is neither a necessary condition nor an effective solution,since not only the interference but also the traffic flows are important factors that will affect the parallel use of the bandwidth.One of the principal challenges addressing these problems is their interactive impact on the optimization of network throughput.By analyzing all kinds of constraints for traffic,NIC and performance,we formally define a problem space that addresses the relationships between different assignment and allocation problems.Furthermore,we demonstrate that a hard NIC assignment and bandwidth allocation problem can be decomposed and formulated into a well-defined single or multiple-phase problem.In addition to the Linear Programming(LP) solutions,we propose novel efficient heuristics for on-line decisions for the situation whenever the network architecture changes and needs recompute the system performance in real-time.We show through extensive simulations that the heuristic algorithms can achieve close to optimal solution and outperform the equal NIC assignment method with even a smaller number of NICs.●Over conventional antenna technologies,MIMO technique have presented great ability in the improvement of network capacity with the unique features of spatial multiplexing and interference suppression.In order to exploit the benefit of simultaneous transmissions provided by MIMO,researchers have proposed a number of cross-layer optimizations and MAC layer designs to increase the throughput of wireless mesh networks,where the number of elements in the antenna arrays are pre-allocated or evenly assigned to the routers.In Chapter 4,we argue that using the same number of elements in each antenna array in all routers is not a necessary condition for the improvement of system performance.This is because the requirement for the number of elements is quite different for each router.Especially at those critical touters that have huge aggregate traffic toward the gateway,more elements are needed not only for the traffic relay but also for the interference suppression.Based on this observation,we define the joint problem of element assignment,bandwidth allocation and scheduling to characterize the throughput benefits of cross-layer optimizations.We propose a Cost-Aware Element Assignment(CAEA) technique to minimize the total number of the antenna elements when still achieving the optimal bandwidth allocation.In addition,to verify the efficiency of the CAEA assignment,a heuristic Trafficaware Stream-controlled Link Scheduling(TSLS) algorithm is proposed to provide a schedulable bandwidth allocation.We demonstrate through extensive simulations that our solutions(CAEA,TSLS) not only effectively save the total cost on antenna elements but also perform close to optimal.更多还原