Gateway Placement for Throughput Optimization in Wireless Mesh Networks

In this paper, we address the problem of gateway placement for throughput optimization in multi-hop wireless mesh networks. Assume that each mesh node in the mesh network has a traffic demand. Given the number of gateways to be deployed (denoted by k) and the interference model in the network, we study where to place exactly k gateways in the mesh network such that the total throughput is maximized while it also ensures a certain fairness among all mesh nodes. We propose a novel grid-based gateway deployment method using a cross-layer throughput optimization, and prove that the achieved throughput by our method is a constant times of the optimal. Simulation results demonstrate that our method can effectively exploit the available resources and perform much better than random and fixed deployment methods. In addition, the proposed method can also be extended to work with multi-channel and multi-radio mesh networks under different interference models.     

Joint Throughput Optimization for Wireless Mesh Networks

In this paper, we address the problem of joint channel assignment, link scheduling, and routing for throughput optimization in wireless networks with multiradios and multichannels. We mathematically formulate this problem by taking into account the interference, the number of available radios the set of usable channels, and other resource constraints at nodes. We also consider the possible combining of several consecutive channels into one so that a network interface card (NIC) can use the channel with larger range of frequencies and thus improve the channel capacity. Furthermore, we consider several interference models and assume a general yet practical network model in which two nodes may still not communicate directly even if one is within the transmission range of the other. We designed efficient algorithm for throughput (or fairness) optimization by finding flow routing, scheduling of transmissions, and dynamic channel assignment and combining. We show that the performance, fairness and throughput, achieved by our method is within a constant factor of the optimum. Our model also can deal with the situation when each node will charge a certain amount for relaying data to a neighboring node and each flow has a budget constraint. Our extensive evaluation shows that our algorithm can effectively exploit the number of channels and radios. In addition, it shows that combining multiple channels and assigning them to a single user at some time slots indeed increases the maximum throughput of the system compared to assigning a single channel.     

Gateway Placement Optimization in Wireless Mesh Networks With QoS Constraints

In a wireless mesh network (WMN), the traffic is aggregated and forwarded towards the gateways. Strategically placing and connecting the gateways to the wired backbone is critical to the management and efficient operation of a WMN. In this paper, we address the problem of gateways placement, consisting in placing a minimum number of gateways such that quality-of-service (QoS) requirements are satisfied. We propose a polynomial time near-optimal algorithm which recursively computes minimum weighted Dominating Sets (DS), while consistently preserving QoS requirements across iterations. We evaluate the performance of our algorithm using both analysis and simulation, and show that it outperforms other alternative schemes by comparing the number of gateways placed in different scenarios     

Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds     

TCP Throughput Enhancement over Wireless Mesh Networks

TCP is the predominant technology used on the Internet to support upper layer applications with reliable data transfer and congestion control services. Furthermore, it is expected that traditional TCP applications (e.g., Internet access) will continue to constitute the major traffic component during the initial deployment of wireless mesh networks. However, TCP is known for its poor throughput performance in wireless multihop transmission environments. For this article, we conducted simulations to examine the impact of two channel interference problems, the hidden terminal and exposed terminal, on TCP transmissions over wireless mesh networks. We also propose a multichannel assignment algorithm for constructing a wireless mesh network that satisfies the spatial channel reuse property and eliminates the hidden terminal problem. The simulation results demonstrate the effectiveness of the proposed approach in improving the performance of TCP in wireless multihop networks.     

Distributed Throughput Maximization in Wireless Mesh Networks via Pre-Partitioning

This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the maximum possible throughput. As an alternative to increasing the throughput fraction by designing new algorithms, we present a novel approach that takes advantage of the inherent multi-radio capability of WMNs. We show that this capability can enable partitioning of the network into subnetworks in which simple distributed scheduling algorithms can achieve 100% throughput. The partitioning is based on the notion of Local Pooling. Using this notion, we characterize topologies in which 100% throughput can be achieved distributedly. These topologies are used in order to develop a number of centralized channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms pre-partition a network in a manner that not only expands the capacity regions of the subnetworks but also allows distributed algorithms to achieve these capacity regions. We evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region. We note that while the identified topologies are of general interference graphs, the partitioning algorithms are designed for networks with primary interference constraints.      

基于选播机制的无线Mesh网络网关选取路由算法

提出了一种基于选播的无线Mesh网络网关选取模型和相应的网关选取路由算法。该模型将所有网关节点抽象成一个选播组,将所有的网关节点组成一个网关树,实现对网关组成员的管理与维护。网关选取路由算法以时延为度量,通过有效的选播机制自适应地查找"最优"网关节点为客户节点服务,以提供响应最快的高质量的因特网接入服务。实验结果表明,该算法能在合理的时间内有效地解决多网关选取问题。     

无线Mesh网络多网关选播QoS路由模型研究

无线Mesh网络中网关常常成为网络的瓶颈.为了解决网关的选取问题和提高QoS性能,根据多网关选取问题与选播路由的相似性,提出了一种基于选播机制的网关选取模型.该模型将所有网关节点抽象成一个选播组,带QoS约束的用户端通过有效的选播机制能够自适应地选择最优的网关节点为其服务,以保证无线Mesh网络良好的接入性能.仿真结果表明了该算法的正确性和有效性.     

A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks

The optimal and distributed provisioning of high throughput in mesh networks is known as a fundamental but hard problem. The situation is exacerbated in a wireless setting due to the interference among local wireless transmissions. In this paper, we propose a cross-layer optimization framework for throughput maximization in wireless mesh networks, in which the data routing problem and the wireless medium contention problem are jointly optimized for multihop multicast. We show that the throughput maximization problem can be decomposed into two subproblems: a data routing subproblem at the network layer, and a power control subproblem at the physical layer with a set of Lagrangian dual variables coordinating interlayer coupling. Various effective solutions are discussed for each subproblem. We emphasize the network coding technique for multicast routing and a game theoretic method for interference management, for which efficient and distributed solutions are derived and illustrated. Finally, we show that the proposed framework can be extended to take into account physical-layer wireless multicast in mesh networks     

Energy Efficient QoS Aware SOCCOR Protocol for Improving Throughput in Wireless Mesh Networks

Wireless Personal Communications - In this paper a new propagation model is proposed for use in complex indoor environments. The model was tested in the frequency range of 2.4 GHz in the...     

Cross-Layer Design for End-to-End Throughput and Fairness Enhancement in Multi-Channel Wireless Mesh Networks

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.     

A High Throughput Configurable SDR Detector for Multi-user MIMO Wireless Systems

Spatial division multiplexing (SDM) in MIMO technology significantly increases the spectral efficiency, and hence capacity, of a wireless communication system: it is a core component of the next generation wireless systems, e.g. WiMAX, 3GPP LTE and other OFDM-based communication schemes. Moreover, spatial division multiple access (SDMA) is one of the widely used techniques for sharing the wireless medium between different mobile devices. Sphere detection is a prominent method of simplifying the detection complexity in both SDM and SDMA systems while maintaining BER performance comparable with the optimum maximum-likelihood (ML) detection. On the other hand, with different standards supporting different system parameters, it is crucial for both base station and handset devices to be configurable and seamlessly switch between different modes without the need for separate dedicated hardware units. This challenge emphasizes the need for SDR designs that target the handset devices. In this paper, we propose the architecture and FPGA realization of a configurable sort-free sphere detector, Flex-Sphere, that supports 4, 16, 64-QAM modulations as well as a combination of 2, 3 and 4 antenna/user configuration for handsets. The detector provides a data rate of up to 857.1 Mbps that fits well within the requirements of any of the next generation wireless standards. The algorithmic optimizations employed to produce an FPGA friendly realization are discussed.     

A Novel Technique for Gateway Selection in Hybrid MANET Using Genetic Algorithm

Integration of Mobile Ad hoc NETworks (MANETs) with the Internet has been paid immense attention in the field of heterogeneous networks. In MANET some intermediate nodes called Internet Gateways (IGs) are responsible for sending the data traffic of source nodes towards the fixed nodes in the Internet. The key issue considered while selecting IG nodes is its optimised throughput with the reduced delay in resource constraint mobile nodes. In this paper, a genetic algorithm inspired Delay Sensitive Gateway Selection (DSGS) scheme is proposed considering the issue of network delay by minimising the total distance travelled by the source nodes to the gateway. The performance of the proposed GA-based DSGS scheme is studied using a comparative approach. The simulation results demonstrate that the proposed scheme significantly outperforms the conventional schemes and is capable of achieving higher network throughput while minimising the end-to-end delay.

     

Asymptotic Throughput Capacity Analysis of Multi-Channel, Multi-Interface Wireless Mesh Networks

Research into the analytical solutions for the capacity of the infrastructure wireless mesh networks (InfWMN) is highly interesting. An InfWMN is a hierarchical network consisting of mesh clients, mesh routers and gateways. The mesh routers form a wireless mesh infrastructure to which the mesh clients are connected through the use of star topology. The previous analytical solutions have only investigated the asymptotic per-client throughput capacity of either single-channel InfWMNs or multi-channel InfWMNs under conditions in which each infrastructure node (i.e. wireless routers and gateways), has a dedicated interface per-channel. The results of previous analytical studies show that there are quite few studies that have addressed the more practical cases where the number of interfaces per-node is less than the number of channels. In this paper, we derive an original analysis of the asymptotic per-client throughput capacity of multi-channel InfWMNs in which the number of interfaces per-infrastructure node, denoted by m, is less than or equal to the number of channels, denoted by c. Our analysis reveals that the asymptotic per-client throughput capacity of multi-channel InfWMNs has different bounds, which depend on the ratio between c and m. In addition, in the case that m < c, there is a reduction in the capacity of the InfWMN compared to the case in which c = m. Our analytical solutions also prove that when ${\frac{\text{c}}{\text{m}}=\Omega\left({\frac{{\rm N}_g^2}{{\rm N}_{\rm r}}}\right)}$ , where N_g and N_r denote the number of gateways and mesh routers respectively, gateways cannot effectively increase the throughput capacity of the multi-channel InfWMNs.     

基于无线Mesh网络的多目标TDMA调度算法

无线mesh网络的迅速发展使其得到了广泛的应用,此类网络的研究中,MAC层的资源优化问题备受关注.本文就无线mesh网络MAC层的时槽分配调度问题,提出了基于NSGA-Ⅱ算法的CNSGA-Ⅱ算法.理论分析和仿真结果表明该算法所得到的Pareto解集具有较好的相对覆盖率和整体前沿扩展性能,能在能耗和时延两个目标参数之间达到较好的平衡状态.     

A Novel Regression Based Clustering Technique for Wireless Sensor Networks

The objective of this paper is to develop a new adaptive iterative linear regression based clustering algorithm for wireless sensor network. According to this, the initial cluster is classified horizontally and vertically in parallel, each resulting in two sub-clusters. Of these two, the best is selected based on the proposed similarity index and with this selected cluster as reference, iteration continues until the convergence criterion ‘Delta’ is met. The similarity index is designed based on the intra cluster similarity and inter cluster dissimilarity. Delta is the difference between the similarity index of the current iteration and the previous iteration. The proposal is implemented in MATLAB and simulations are carried out under different network scenarios. The cluster quality is evaluated through external and internal indices using the Cluster Validity Analysis Platform tool. The cluster obtained by the proposal is studied and its quality is compared with the well-established k-means and hierarchical clustering. The performance indices confirm the supremacy of the proposal.     

无线Mesh网络QoS路由度量研究

无线Mesh网络的研究非常活跃,针对网络路由选择已经提出了一些路由选择度量。本文对各种路由度量及优缺点进行了详细的分析,并在此基础上,给出了一种新的路由度量方式并展望无线Mesh网络QoS路由度量选择的发展方向。     

On Path Selection and Rate Allocation for Video in Wireless Mesh Networks

Multi-path transport is an important mechanism for supporting video communications in multihop wireless networks. In this paper, we investigate the joint problem of optimal path selection and rate allocation for multiple video sessions in a wireless mesh network. We present a mathematical formulation to optimize the application level performance (i.e., video distortion) in the context of path selection and rate allocation. For this complex optimization problem, we propose a branch-and-bound based solution procedure, embedded with the Reformulation-Linearization Technique (RLT) that can produce $(1-epsilon)$-optimal solutions for any small $epsilon$ . This result is significant as it not only provides theoretical understanding of this problem, but also offers a performance benchmark for any future proposed distributed algorithm and protocol for this problem. Simulation results are also provided to demonstrate the efficacy of the solution procedure.      

基于紧密中心性的无线mesh骨干网网关部署

将定向天线和Delaunay图应用于无线mesh骨干网络的网关部署,提出了基于紧密中心性的无线mesh骨干网络网关部署算法。根据已知的mesh路由器和网关的最大流通量对网络进行划分,形成Delaunay子图,在划分的子图中根据欧几里德距离找出距离中心点最近的3个节点,形成候选网关集,在候选网关集中选择到其他节点总路径最短的节点作为网关的部署位置,将每个子图的网关位置输出。仿真结果表明,根据网关最大流通量进行合理网络划分后,算法能最小化网络的网关数量,由mesh路由器到网关的总路径长度优于随机算法。