No / Due to the attractive characteristics of high capacity, high-speed, wide coverage and low transmission power, Wireless Mesh Networks become the ideal choice for the next-generation wireless communication systems. However, the network congestion of WMNs deteriorates the quality of service provided to end users. Game theory optimization model is a novel modeling tool for the study of multiple entities and the interaction between them. On the other hand, cross-layer design is shown to be practical for optimizing the performance of network communications. Therefore, a combination of the game theory and cross-layer optimization, named cross-layer game optimization, is proposed to reduce network congestion in WMNs. In this paper, the network congestion control in the transport layer and multi-path flow assignment in the network layer of WMNs are investigated. The proposed cross-layer game optimization algorithm is then employed to enable source nodes to change their set of paths and adjust their congestion window according to the round-trip time to achieve a Nash equilibrium. Finally, evaluation results show that the proposed cross-layer game optimization scheme achieves high throughput with low transmission delay.

No description available.

No description available.

Recently, many new types of wireless networks have emerged for both civil and military applications, such as cognitive radio networks, MIMO networks. There is a strong interest in exploring the optimal performance of these new emerging networks, e.g., maximizing the network throughput, minimizing network energy consumption. Exploring the optimal performance objectives of these new types of wireless networks is both important and intellectual challenging. On one hand, it is important for a network researcher to understand the performance limits of these new wireless networks. Such performance limits are important not only for theoretical understanding, but also in that they can be used as benchmarks for the design of distributed algorithms and protocols. On the other hand, due to some unique characteristics associated with these networks, existing analytic techniques may not be applied directly to obtain the optimal performance. As a result, new theoretical results, along with new mathematical tools, need to be developed. The goal of this dissertation is to make a fundamental advance on network performance optimization via exploring a series of optimization problems. Based on the scale of the underlying wireless network, the works in this dissertation are divided into two parts. In the first part, we study the asymptotic capacity scaling laws of different types of wireless networks. By "asymptotic", we mean that the number of nodes in the network goes to infinity. Such asymptotic capacity scaling laws offer fundamental understandings on the trend of maximum user throughput behavior when the network size increases. In the second part of this dissertation, we study several optimization problems of finite-sized wireless networks. Under a given network size, we accurately characterize some performance limits (e.g., throughput, energy consumption) of wireless networks and provide solutions on how to achieve the optimal objectives. The main contributions of this dissertation can be summarized as follows, where the first three problems are on asymptotic capacity scaling laws and the last three problems are optimization problems of finite-sized wireless networks. <b>1. Capacity Scaling Laws of Cognitive Radio Ad Hoc Networks.</b> We first study the capacity scaling laws for cognitive radio ad hoc networks (CRNs), i.e., how each individual node's maximum throughput scales as the number of nodes in the network increases. This effort is critical to the fundamental understanding of the scalability of such network. However, due to the heterogeneity in available frequency bands at each node, the asymptotic capacity is much more difficult to develop than prior efforts for other types of wireless networks. To overcome this difficulty, we introduce two auxiliary networks ζ and α to analyze the capacity upper and lower bounds. We derive the capacity results under both the protocol model and the physical model. Further, we show that the seminal results developed by Gupta and Kumar for the simple single-channel single-radio (SC-SR) networks are special cases under the results for CRNs. <b>2. Asymptotic Capacity of Multi-hop MIMO Ad Hoc Networks.</b> Multi-input multi-output (MIMO) is a key technology to increase the capacity of wireless networks. Although there has been extensive work on MIMO at the physical and link layers, there has been limited work on MIMO at the network layer (i.e., multi-hop MIMO ad hoc network), particularly results on capacity scaling laws. In this work, we investigate capacity scaling laws for MIMO ad hoc networks. Our goal is to find the achievable throughput of each node as the number of nodes in the network increases. We employ a MIMO network model that captures spatial multiplexing (SM) and interference cancellation (IC). We show that for a MIMO network with n randomly located nodes, each equipped with γ antennas and a rate of W on each data stream, the achievable throughput of each node is Θ(γW/√<span style="text-decoration:overline;"> n ln n</span></span>). <b>3. Toward Simple Criteria for Establishing Capacity Scaling Laws.</b> Capacity scaling laws offer fundamental understanding on the trend of user throughput behavior when the network size increases. Since the seminal work of Gupta and Kumar, there have been tremendous efforts developing capacity scaling laws for ad hoc networks with various advanced physical layer technologies. These efforts led to different custom-designed approaches, most of which were intellectually challenging and lacked universal properties that can be extended to address scaling laws of ad hoc networks with a different physical layer technology. In this work, we present a set of simple yet powerful general criteria that one can apply to quickly determine the capacity scaling laws for various physical layer technologies under the protocol model. We prove the correctness of our proposed criteria and validate them through a number of case studies, such as ad hoc networks with directional antenna, MIMO, cognitive radio, multi-channel and multi-radio, and multiple packet reception. These simple criteria will serve as powerful tools to networking researchers to obtain throughput scaling laws of ad hoc networks under different physical layer technologies, particularly those to appear in the future. <b>4. Exploiting SIC forMulti-hopWireless Networks.</b> There is a growing interest on exploiting interference (rather than avoiding it) to increase network throughput. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters and interference rejection. However, due to some stringent constraints and limit, SIC alone is inadequate to handle all concurrent interference. We advocate a joint interference exploitation and avoidance approach, which combines the best of interference exploitation and interference avoidance, while avoiding each's pitfalls. We discuss the new challenges of such a new approach in a multi-hop wireless network and propose a formal optimization framework, with cross-layer formulation of physical, link, and network layers. This framework offers a rather complete design space for SIC to squeeze the most out of interference. The goal of this effort is to lay a mathematical foundation for modeling and analysis of a joint interference exploitation and avoidance scheme in a multi-hop wireless network. Through modeling and analysis, we develop a tractable model that is suitable for studying a broad class of network throughput optimization problems. To demonstrate the practical utility of our model, we conduct a case study. Our numerical results affirm the validity of our model and give insights on how SIC can optimally interact with an interference avoidance scheme. <b>5. Throughput Optimization with Network-wide Energy Constraint.</b> Conserving network wide energy consumption is becoming an increasingly important concern for network operators. In this work, we study network-wide energy conservation problem which we hope will offer insights to both network operators and users. Specifically, we study how to maximize network throughput under a network-wide energy constraint for a general multi-hop wireless network. We formulate this problem as a mixed-integer nonlinear program (MINLP). We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near optimal with guaranteed performance bound. <b>6. Bicriteria Optimization in Multi-hop Wireless Networks.</b> Network throughput and energy consumption are two important performance metrics for a multi-hop wireless network. Current state-of-the-art is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. However, the important problem of how to optimize both objectives simultaneously remains open. In this work, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. We show that the solution to the multicriteria optimization problem characterizes the envelope of the entire throughput energy region, i.e., the so-called optimal throughput-energy curve. We prove some important properties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. For the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while for the nonlinear case, we use a piece-wise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the trade-off between the two performance metrics. / Ph. D.

A critical factor affecting the future prospects of wireless networks for wide-scale deployment is network capacity: the end users wish to have their communication experience over wireless networks to be comparable or similar to that for wireline networks. An effective approach to increase network capacity is to increase spectrum efficiency. Such an approach can be achieved by the use of multiple antenna systems (also known as multiple-input multiple-output (MIMO) technology). The benefits of substantial improvements in capacity at no cost of additional spectrum and power have positioned MIMO as one of the breakthrough technologies in modern wireless communications. As expected, research activities on applying MIMO to a variety of wireless networks have soared in recent years. However, compared with the simple point-to-point MIMO channel, which is relatively well-understood nowadays, network design and performance optimization for MIMO-based wireless networks is considerably more challenging. Many fundamental problems remain unsolved. Due to the complex characteristics of MIMO physical layer technology, it is not only desirable but also necessary to consider models and constraints at multiple layers (e.g., physical, link, and network) jointly. The formulations of these cross-layer problems for MIMO wireless networks, however, are usually mathematically challenging. In this dissertation, we aim to develop some novel algorithmic design and optimization techniques that provide optimal or near-optimal solutions. Based on network structure, this dissertation is organized into two parts. In the first part, we focus on single-hop MIMO wireless networks, while in the second part, we focus on multi-hop MIMO networks. The main results and contributions of this dissertation are summarized as follows. Single-hop MIMO Networks. In the first part of this dissertation, we study three different optimization problems for single-hop MIMO networks. The first problem addresses weighted proportional fair (WPF) scheduling associated with MIMO broadcast channels (Chapter 2). For the WPF scheduling problem in MIMO broadcast channels, we develop two algorithms that can efficiently determine the optimal dirty paper encoding order and power allocation to achieve an optimal WPF performance. To our knowledge, our work is the first that provides solutions to the WPF scheduling problem in MIMO broadcast channels. Our next problem concerns single-hop MIMO ad hoc networks (Chapter 3), which are quite different from the MIMO broadcast channels studied in the previous chapter. Single-hop MIMO ad hoc networks can be simply described as "multiple one-to-one," as compared with MIMO broadcast channels, which are "one-to-many." Performance optimization for such networks is known to be challenging due to the non-convex mathematical structure. Indeed, these networks can be viewed as the general case of interference channels in network information theory context, for which the capacity region remains unknown even under the two-user case. In this chapter, we treat the co-channel interference in the network as noise. We consider the maximum weighted sum rate problem under the single-carrier setting. We propose a global optimization approach that combines branch-and-bound (BB) and the reformulation-linearization technique (RLT). This technique is guaranteed to find a global optimal solution Multi-hop MIMO Networks. In addition to managing resources such as power and scheduling in single-hop networks, routing and end-to-end session rate control need to be considered in multi-hop MIMO networks. Thus, performance optimization problems in multi-hop MIMO networks are more interesting and yet challenging. In Chapter 4, we first consider the problem of jointly optimizing power and bandwidth allocation at each node and multihop/multipath routing in a multi-hop MIMO network that employs orthogonal channels. We show that this problem has some special structure that admits a decomposition into a set of subproblems in its dual domain. Based on this finding, we propose both centralized and distributed optimization algorithms to solve this problem optimally. In Chapter 5, we relax the orthogonal channel assumption. More specifically, we exploit the advantage of "dirty paper coding" (DPC) to allow multiple links originated from the same node to share the same channel media simultaneously. However, the formulation of cross-layer optimization problem with DPC has a non-convex structure and an exponentially large search space inherent in enumerating DPC's encoding orders. To address these difficulties, we propose an approach to reformulate and convexify the original problem. Based on the reformulated problem, we design an efficient solution procedure by exploiting decomposable dual structure. One thing in common in Chapters 4 and 5 is that we adopt the classical matrix-based MIMO channel models at the physical layer. Although this approach has its merit, the complex matrix operations in the classical MIMO models may pose a barrier for researchers in networking research community to gain fundamental understanding on MIMO networks. To bridge this gap between communications and networking communities, in Chapter 6, we propose a simple, accurate, and tractable model to enable the networking community to carry out cross-layer research for multi-hop MIMO networks. At the physical layer, we develop an accurate and simple model for MIMO channel capacity computation that captures the essence of spatial multiplexing and transmit power limit without involving complex matrix operations and the water-filling algorithm. At the link layer, we devise a space-time scheduling scheme called order-based interference cancellation (OBIC) that significantly advances the existing zero-forcing beamforming (ZFBF) to handle interference in a multi-hop network setting. The proposed OBIC scheme employs simple algebraic computation on matrix dimensions to simplify ZFBF in a multi-hop network. Finally, we apply both the new physical and link layer models to study a cross-layer optimization problem for a multi-hop MIMO network. / Ph. D.

Cognitive Radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than existing multi-channel multi-radio (MC-MR) technology. In this thesis, we investigate the important problem of multi-hop networking with CR nodes. In a CR network, each node has a set of frequency bands (not necessarily of equal size) that may not be the same as those at other nodes. The uneven size of frequency bands prompts the need of further division into sub-bands for optimal spectrum sharing. We characterize behaviors and constraints for such multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We give a formal mathematical formulation with the objective of maximizing the network throughput for a set of user communication sessions. Since such problem formulation falls into mixed integer non-linear programming (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and linearization. Subsequently, we develop a nearoptimal algorithm to this MINLP problem. This algorithm is based on a novel sequential fixing (SF) procedure, where the integer variables are determined iteratively via a sequence of linear program (LP). In order to implement and evaluate these algorithms in a controlled laboratory setting, we design and implement an emulation testbed. The highlights of our experimental research include: • Emulation of a multi-hop CR network with arbitrary topology; • An implementation of the proposed SF algorithm at the application layer; • A source routing implementation that can easily support comparative study between SF algorithm and other schemes; • Experiments comparing the SF algorithm with another algorithm called Layered Greedy Algorithm (LGA); • Experimental results show that the proposed SF significantly outperforms LGA. In summary, the experimental research in this thesis has demonstrated that SF algorithm is a viable algorithm for optimal spectrum sharing in multi-hop CR networks. / Master of Science

Traditionally, achieving good performance for a multi-hop wireless network is known to be difficult. The main approach to control the operation of such a network relies on a distributed paradigm, assuming that a centralized approach is not feasible. Relying on a distributed paradigm could be justified at the time when the basic technical building blocks (e.g., node computational power, communication technology, positioning technology) were the bottlenecks. Recent advances and breakthroughs in these technical areas along with the emergence of programmable networks with softwarized control plane intelligence allow us to consider employing a centralized optimization paradigm to control and manage the operation of a multi-hop wireless network. The programmable control provides a platform on which the centralized global network optimization paradigm can be supported. The benefits of a centralized network optimization lie specially in that a network may be configured in such a way that offers optimal performance, which is hardly possible for a network relying on distributed operation. The objectives of this dissertation are to fully understand the potential benefits of a centralized control plane for a multi-hop wireless network, to identify any new challenges under this new paradigm, and to devise innovative solutions for optimal performance via a centralized control plane. Given that the performance of a wireless network heavily depends on its physical layer capabilities, we will consider a number of advanced wireless technologies, including MIMO, full duplex, and interference cancellation at the physical layer. The focus is on building tractable computational models for these wireless technologies that can be used for modeling, analysis and optimization in the centralized control plane. Problem formulation and efficient solution procedures are developed for various centralized optimization problems across multiple layers. End-to-end throughput maximization is a key objective among these optimization problems on the centralized control plane and is used to demonstrate the superior advantage of this paradigm. We study several problems: • Integration of SIC and MIMO DoF IC. We propose to integrate MIMO Degree-of-Freedom (DoF) interface cancellation (IC) and Successive Interference Cancellation (SIC) in MIMO multi-hop network under DoF protocol model. We show that DoF-based IC and SIC can be jointly integrated to combat the interference more effectively and improve the end-to-end throughput significantly. We develop the necessary mathematical models to realize the idea in a multi-hop wireless network. • Full-Duplex MIMO Wireless Networks Throughput. We investigate the performance of MIMO full-duplex (FD) in a multi-hop network. We show that if IC is exploited, MIMO FD can achieve significant throughput gain over MIMO HD in a multi-hop network, which is contrary to the recent literature suggesting an unexpected marginal gain. Our proposed model handles the additional network interference by joint efficient link scheduling and interference cancellation. • PCP in Tactical Wireless Networking. We propose the idea of the Programmable Control Plane (PCP) for the tactical wireless network under the protocol model. PCP decouples the control and data plane and allows the network control layer functionalities to be dynamically configured to adapt to specific wireless channel conditions, customized applications and/or certain tactical situations. The proposed PCP functionalities are cast into a centralized optimization problem, which can be updated as needed and provide a centralized intelligence to manage the operation of a wireless MIMO multi-hop network under the protocol model. • UPCP in Heterogeneous Wireless Networks. We propose the idea of the Unified Programmable Control Plane (UPCP) for tactical heterogeneous wireless networks with interference management capabilities under the SINR model. The UPCP abstracts the complexity of the underlying network comprised of heterogeneous wireless technologies and provides a centralized intelligence over the network resources. We develop necessary mathematical model to realize the UPCP. / Ph. D.

A fundamental problem in multi-hop wireless networks is to estimate their throughout capacity. The problem can be informally stated as follows: given a multi-hop wireless network and a set of source destination pairs, determine the maximum rate r at which data can be transmitted between each source destination pair. Estimating the capacity of a multi-hop wireless network is practically useful --- it yields insights into the fundamental performance limits of the wireless network and at the same time aids the development of protocols that can utilize the network close to this limit. A goal of this dissertation is to develop rigorous mathematical foundations to compute the capacity of any given multi-hop wireless network with known source-destination pairs. An important factor that affects the capacity of multi-hop wireless networks is radio interference. As a result, researchers have proposed increasingly realistic interference models that aim to capture the physical characteristics of radio signals. Some of the commonly used simple models that capture radio interference are based on geometric disk-graphs. The simplicity of these models facilitate the development of provable and often conceptually simple methods for estimating the capacity of wireless networks. A potential weakness of this class of models is that they oversimplify the physical process by assuming that the signal ends abruptly at the boundary of a geometric region (a disk for omni-directional antennas). A more sophisticated interference model is the physical interference model, also known as the Signal to Interference Plus Noise Ratio (SINR) model. This model is more realistic than disk-graph models as it captures the effects of signal fading and ambient noise. This work considers both disk-graph and SINR interference models. In addition to radio interference, the throughput capacity of a multi-hop wireless network also depends on other factors, including the specific paths selected to route the packets between the source destination pairs (routing), the time at which packets are transmitted (scheduling), the power with which nodes transmit (power control) and the rate at which packets are injected (rate control). In this dissertation, we consider three different problems related to estimating network capacity. We propose an algorithmic approach for solving these problems. We first consider the problem of maximizing throughput with the SINR interference model by jointly considering the effects of routing and scheduling constraints. Second, we consider the problem of maximizing throughput by performing adaptive power control, scheduling and routing for disk-graph interference models. Finally, we examine the problem of minimizing end-to-end latency by performing joint routing, scheduling and power control using the SINR interference model. Recent results have shown that traditional layered networking principles lead to inefficient utilization of resources in multi-hop wireless networks. Motivated by these observations, recent papers have begun investigating cross-layer design approaches. Although our work does not develop new cross-layered protocols, it yields new insights that could contribute to the development of such protocols in the future. Our approach for solving these multi-objective optimization problems is based on combining mathematical programming with randomized rounding to obtain polynomial time approximation algorithms with provable worst case performance ratios. For the problems considered in this work, our results provide the best analytical performance guarantees currently known in the literature. We complement our rigorous theoretical and algorithmic analysis with simulation-based experimental analysis. Our experimental results help us understand the limitations of our approach and assist in identifying certain parameters for improving the performance of our techniques. / Ph. D.

Wireless Sensor Networks (WSNs) are wireless networks that have recently drawn significant research attention since they offer unique benefits and versatility with respect to sensing, allowing low-power and low-cost rapid deployment for many applications that do not need human supervision. WSNs are self-created and self-organized by the collection of a large number of sensor nodes interconnected by multi-hop wireless paths. The sensor nodes are network embedded systems with Integrated Chips (ICs) to allow signal processing and micro-sensing. Each wireless sensor node is a micro-electro-mechanical device and can only be equipped with a limited power reserve. While energy consumption occurs in sensing, data processing and communications, care should be exercised to make the most of the expendable power source for the node. Though considerable research is being done in the area of energy saving techniques for WSNs, most of the proposed techniques have focused on energy awareness at different network layers in WSNs. Furthermore, most of the proposed techniques are based on protocols for mobile ad hoc networks that do not look into the possibility of a cross-layer design strategy that can exploit the unique features of WSNs. There still exists the need for a universal protocol that can be applied to such networks in general. In this thesis, we focus such a research on optimizing the energy consumption by suggesting a novel cross-layer architecture at the network/data-link layer for sensor networks. We have developed a scheme for better and improved energy efficiency in WSNs by combining the ideas of energy-efficient cluster formation and medium access together. Our cross-layer scheme provides good performance in terms of WSN-lifetime, scalability and minimizing network-wide energy consumption. The scheme is based on a collaborative approach supported by formation of dynamic clusters functioning with a traffic aware MAC (medium access control) scheme. Our MAC scheme incorporates a self-learning, traffic adaptive algorithm for varying traffic conditions inherent to the WSNs. The design methodology and results in this thesis aim at producing a reliable and scalable energy-aware sensing network, in spite of node failures, minimizing energy consumption at the same time. / Master of Science

Les réseaux sans fil maillés offrent une infrastructure pour interconnecter les stations d’accès de réseaux de différentes technologies. Ils disposent d’une topologie maillée où tous les routeurs sont connectés de proche en proche sans hiérarchie centrale. Le routage des données, dans ce type de réseaux, doit être réalisé tout en optimisant les ressources du réseau et en respectant au mieux les exigences de QoS des utilisateurs. Dans cette thèse, nous proposons un routage orienté qualité de service dans un réseau sans fil métropolitain grâce à une approche de type cross-layer. Nous avons commencé par étudier l’impact des couches PHY et MAC sur le routage afin d’en déduire la meilleure combinaison protocolaire pour un réseau sans fil maillé. Nous avons, par la suite, orienté notre travail sur l’étude du comportement du protocole de routage OLSR sous différentes métriques de routage. Les résultats de cette étude ont confirmé les limites des métriques existantes à reproduire la qualité réelle des liens et ont soulevé plusieurs points d’optimisation sur lesquels nous avons focalisé. Nous avons donc proposé de nouvelles métriques qui renseignent sur la qualité des liens, en se basant sur les caractéristiques PHY et MAC des liens réseaux, notamment la disponibilité du lien, le taux de perte, la bande passante résiduelle, etc. L’acquisition de ces paramètres des couches basses se fait à l’aide d’un mécanisme de cross-layer. Ces métriques permettent d’appréhender les interférences inter-flux et d’éviter de créer des goulots d’étranglement en équilibrant les charges sur les différents liens. En se basant sur le modèle de graphe de conflit et le calcul des cliques maximales, nous avons proposé une méthode d’estimation de la bande passante résiduelle qui permet de considérer, en plus, les interférences intra-flux. Finalement, nous avons proposé un protocole de routage qui supporte cette métrique et nous avons étudié ses performances par simulation en comparaison avec d’autres métriques et protocoles de routage existants. Les résultats obtenus ont révélé l’aptitude de notre protocole à supporter le passage à l’échelle du réseau ainsi que sa capacité à choisir les routes offrant le plus de débit et le moins de délai, permettant ainsi, une meilleure livraison du trafic de données. / Wireless Mesh Networks provide infrastructure to interconnect access stations in networks of different technologies. They have a mesh topology where all the routers are connected with no central hierarchy. Routing in WMNs must be carried out while optimizing network resources and respecting the best user QoS requirements. In this thesis, we propose a QoS-oriented routing in a metropolitan wireless network using a cross-layer approach. We first studied the impact of the PHY and MAC layers on routing to deduce the best combination protocol for a wireless mesh network. We have subsequently focused our work on studying the behavior of the OLSR routing protocol with different routing metrics. The results of this study confirmed the limits of existing metrics to reproduce the real link quality and raised a number of optimization points on which we focused. We have, therefore, proposed new metrics that provide information about link quality, based on PHY and MAC characteristics, including the link availability, the loss rate, the available bandwidth, etc. These low layers parameters are acquired using a cross-layer mechanism. These metrics allow to apprehend inter-flow interferences and avoid bottleneck formation by balancing traffic load on the links. Based on the conflict graph model and calculation of maximal cliques, we proposed a method to estimate the available bandwidth of a path which considers, in addition, intra-flow interferences. Finally, we proposed a routing protocol that supports this metric and we studied by simulation its performances compared to different existing routing metrics and protocols. The results revealed the ability of our protocol to support the network scalability as well as its ability to choose routes with high throughput and limited delay, thus, better delivery of data traffic.