This thesis presents several simple, robust, and optimal resource management schemes for multihop wireless access networks with the main focus on multi-channel wireless mesh networks (MC WMNs). In this regard, various resource management optimization problems are formulated arid efficient algorithms are proposed to solve each problem. First, we consider the channel as signment problem in MC-WMNs and formulate different resource management problems within the general framework of network utility maximization (NUM). Unlike most of the previously proposed channel assignment schemes, our algorithms can not only assign the orthogonal (i.e., non-overlapped) channels, but also partially overlapped channels. This better utilizes the avail able frequency spectrum as a critical resource in MC-WMNs. Second, we propose two distributed random medium access control (MAC) algorithms to solve a non-convex NUM problem at the MAC layer. The first algorithm is fast, optimal, and robust to message loss and delay. It also only requires a limited message passing among the wireless nodes. Using distributed learning techniques, we then propose another NUM-based MAC algorithm which achieves the optimal performance without frequent message exchange. Third, based on our results on random MAC, we develop a distributed multi-interface multi-channel random access algorithm to solve the NUM problem in MC-WMNs. Different from most of the previous channel assignment schemes in the literature, where channel assignment is intuitively modeled in the form of combinatorial and discrete optimization problems, our scheme is based on formulating a novel continuous optimization model. This makes the analysis and implementation significantly easier. Finally, we consider the problem of pricing and monetary exchange in multi-hop wireless access networks, where each intermediate node receives a payment to compensate for its offered packet forwarding service. In this regard, we propose a market-based wireless access network model with two-fold pricing. It uses relay-pricing to encourage collaboration among the access points. It also uses interference pricing to leverage optimal resource management. In general, this thesis widely benefits from several mathematical techniques as both modeling and solution tools to achieve simple, robust, optimal, and practical resource management strategies for future wireless access networks.

This thesis presents several simple, robust, and optimal resource management schemes for multihop wireless access networks with the main focus on multi-channel wireless mesh networks (MC WMNs). In this regard, various resource management optimization problems are formulated arid efficient algorithms are proposed to solve each problem. First, we consider the channel as signment problem in MC-WMNs and formulate different resource management problems within the general framework of network utility maximization (NUM). Unlike most of the previously proposed channel assignment schemes, our algorithms can not only assign the orthogonal (i.e., non-overlapped) channels, but also partially overlapped channels. This better utilizes the avail able frequency spectrum as a critical resource in MC-WMNs. Second, we propose two distributed random medium access control (MAC) algorithms to solve a non-convex NUM problem at the MAC layer. The first algorithm is fast, optimal, and robust to message loss and delay. It also only requires a limited message passing among the wireless nodes. Using distributed learning techniques, we then propose another NUM-based MAC algorithm which achieves the optimal performance without frequent message exchange. Third, based on our results on random MAC, we develop a distributed multi-interface multi-channel random access algorithm to solve the NUM problem in MC-WMNs. Different from most of the previous channel assignment schemes in the literature, where channel assignment is intuitively modeled in the form of combinatorial and discrete optimization problems, our scheme is based on formulating a novel continuous optimization model. This makes the analysis and implementation significantly easier. Finally, we consider the problem of pricing and monetary exchange in multi-hop wireless access networks, where each intermediate node receives a payment to compensate for its offered packet forwarding service. In this regard, we propose a market-based wireless access network model with two-fold pricing. It uses relay-pricing to encourage collaboration among the access points. It also uses interference pricing to leverage optimal resource management. In general, this thesis widely benefits from several mathematical techniques as both modeling and solution tools to achieve simple, robust, optimal, and practical resource management strategies for future wireless access networks.

To meet growing demand for wireless access to multimedia traffic, future generations of wireless networks need to provide heterogenous services with high data rate and guaranteed quality-of-service (QoS). Many enabling technologies to ensure QoS have been investigated, including cross-layer admission control (AC), error control and congestion control. In this thesis, we study the cross-layer AC problem. While previous research focuses on single-antenna systems, which does not capitalize on the significant benefits provided by multiple antenna systems, in this thesis we investigate cross-layer AC policy for a code-division-multiple-access (CDMA) system with antenna arrays at the base station (BS). Automatic retransmission request (ARQ) schemes are also exploited to further improve the spectral efficiency. In the first part, a circuit-switched network is considered and an exact outage probability is developed, which is then employed to derive the optimal call admission control (CAC) policy by formulating a constrained semi-Markov decision process (SMDP). The derived optimal policy can maximize the system throughput with guaranteed QoS requirements in both physical and network layers. In the second part, a suboptimal low-complexity CAC policy is proposed based on an approximate power control feasibility condition (PCFC) and a reduced-outage-probability algorithm. Comparison between optimal and suboptimal CAC policies shows that the suboptimal CAC policy can significantly reduce the computational complexity at a cost of degraded performance. In the third part, we extend the above research to packet-switched networks. A novel SMDP is formulated by incorporating ARQ protocols. Packet-level AC policies are then proposed. The proposed policies exploit the error control capability provided by ARQ schemes, while simultaneously guaranteeing QoS requirements in the physical and packet levels. In the fourth part, we propose a connection admission control policy in a connection-oriented packet-switched network, which can guarantee QoS requirements in physical, packet and connection levels. By considering joint optimization across different layers, the proposed optimal policy provides a flexible way to handle multiple QoS requirements, while at the same time, maximizing the overall system throughput. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2008-08-05 16:21:40.431

This thesis presents several simple, robust, and optimal resource management schemes for multihop wireless access networks with the main focus on multi-channel wireless mesh networks (MC WMNs). In this regard, various resource management optimization problems are formulated arid efficient algorithms are proposed to solve each problem. First, we consider the channel as signment problem in MC-WMNs and formulate different resource management problems within the general framework of network utility maximization (NUM). Unlike most of the previously proposed channel assignment schemes, our algorithms can not only assign the orthogonal (i.e., non-overlapped) channels, but also partially overlapped channels. This better utilizes the avail able frequency spectrum as a critical resource in MC-WMNs. Second, we propose two distributed random medium access control (MAC) algorithms to solve a non-convex NUM problem at the MAC layer. The first algorithm is fast, optimal, and robust to message loss and delay. It also only requires a limited message passing among the wireless nodes. Using distributed learning techniques, we then propose another NUM-based MAC algorithm which achieves the optimal performance without frequent message exchange. Third, based on our results on random MAC, we develop a distributed multi-interface multi-channel random access algorithm to solve the NUM problem in MC-WMNs. Different from most of the previous channel assignment schemes in the literature, where channel assignment is intuitively modeled in the form of combinatorial and discrete optimization problems, our scheme is based on formulating a novel continuous optimization model. This makes the analysis and implementation significantly easier. Finally, we consider the problem of pricing and monetary exchange in multi-hop wireless access networks, where each intermediate node receives a payment to compensate for its offered packet forwarding service. In this regard, we propose a market-based wireless access network model with two-fold pricing. It uses relay-pricing to encourage collaboration among the access points. It also uses interference pricing to leverage optimal resource management. In general, this thesis widely benefits from several mathematical techniques as both modeling and solution tools to achieve simple, robust, optimal, and practical resource management strategies for future wireless access networks. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Recently, many new types of wireless networks have emerged for both civil and military applications, such as wireless sensor networks, ad hoc networks, among others. To improve the performance of these wireless networks, many advanced communication techniques have been developed at the physical layer. For both theoretical and practical purposes, 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. However, due to some unique characteristics associated with these networks, existing analytical technologies may not be applied directly. As a result, new theoretical results, along with new mathematical techniques, need to be developed. In this dissertation, we focus on the design of new algorithms and optimization techniques to study theoretical performance limits associated with these new wireless networks. In this dissertation, we mainly focus on sensor networks and ad hoc networks. Wireless sensor networks consist of battery-powered nodes that are endowed with a multitude of sensing modalities. A wireless sensor network can provide in-situ, unattended, high-precision, and real-time observation over a vast area. Wireless ad hoc networks are characterized by the absence of infrastructure support. Nodes in an ad hoc network are able to organize themselves into a multi-hop network. An ad hoc network can operate in a stand-alone fashion or could possibly be connected to a larger network such as the Internet (also known as mesh networks). For these new wireless networks, a number of advanced physical layer techniques, e.g., ultra wideband (UWB), multiple-input and multiple-output (MIMO), and cognitive radio (CR), have been employed. These new physical layer technologies have the potential to improve network performance. However, they also introduce some unique design challenges. For example, CR is capable of reconfiguring RF (on the fly) and switching to newly-selected frequency bands. It is much more advanced than the current multi-channel multi-radio (MC-MR) technology. MC-MR remains hardware-based radio technology: each radio can only operate on a single channel at a time and the number of concurrent channels that can be used at a wireless node is limited by the number of radio interfaces. While a CR can use multiple bands at the same time. In addition, an MC-MR based wireless network typically assumes there is a set of "common channels" available for all nodes in the network. While for CR networks, each node may have a different set of frequency bands based on its particular location. These important differences between MC-MR and CR warrant that the algorithmic design for a CR network is substantially more complex than that under MC-MR. Due to the unique characteristics of these new wireless networks, it is necessary to consider models and constraints at multiple layers (e.g., physical, link, and network) when we explore network performance limits. The formulations of these cross-layer problems are usually in very complex forms and are mathematically challenging. We aim to develop some novel algorithmic design and optimization techniques that provide optimal or near-optimal solutions. The main contributions of this dissertation are summarized as follows. 1. Node lifetime and rate allocation We study the sensor node lifetime problem by considering not only maximizing the time until the first node fails, but also maximizing the lifetimes for all the nodes in the network. For fairness, we maximize node lifetimes under the lexicographic max-min (LMM) criteria. Our contributions are two-fold. First, we develop a polynomial-time algorithm based on a parametric analysis (PA) technique, which has a much lower computational complexity than an existing state-of-the-art approach. We also present a polynomial-time algorithm to calculate the flow routing schedule such that the LMM-optimal node lifetime vector can be achieved. Second, we show that the same approach can be employed to address a different but related problem, called LMM rate allocation problem. More important, we discover an elegant duality relationship between the LMM node lifetime problem and the LMM rate allocation problem. We show that it is sufficient to solve only one of the two problems and that important insights can be obtained by inferring the duality results. 2. Base station placement Base station location has a significant impact on sensor network lifetime. We aim to determine the best location for the base station so as to maximize the network lifetime. For a multi-hop sensor network, this problem is particularly challenging as data routing strategies also affect the network lifetime performance. We present an approximation algorithm that can guarantee (1- ε)-optimal network lifetime performance with any desired error bound ε > 0. The key step is to divide the continuous search space into a finite number of subareas and represent each subarea with a "fictitious cost point" (FCP). We prove that the largest network lifetime achieved by one of these FCPs is (1- ε)-optimal. This approximation algorithm offers a significant reduction in complexity when compared to a state-of-the-art algorithm, and represents the best known result to this problem. 3. Mobile base station The benefits of using a mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretical performance limits and provably optimal algorithms remain difficult to develop. Our main result hinges upon a novel transformation of the joint base station movement and flow routing problem from the time domain to the space domain. Based on this transformation, we first show that if the base station is allowed to be present only on a set of pre-defined points, then we can find the optimal sojourn time for the base station on each of these points so that the overall network lifetime is maximized. Based on this finding, we show that when the location of the base station is un-constrained (i.e., can move to any point in the two-dimensional plane), we can develop an approximation algorithm for the joint mobile base station and flow routing problem such that the network lifetime is guaranteed to be at least (1- ε) of the maximum network lifetime, where ε can be made arbitrarily small. This is the first theoretical result with performance guarantee on this problem. 4. Spectrum sharing in CR networks Cognitive radio is a revolution in radio technology that promises unprecedented flexibility in radio communications and is viewed as an enabling technology for dynamic spectrum access. We consider a cross-layer design of scheduling and routing with the objective of minimizing the required network-wide radio spectrum usage to support a set of user sessions. Here, scheduling considers how to use a pool of unequal size frequency bands for concurrent transmissions and routing considers how to transmit data for each user session. We develop a near-optimal algorithm based on a sequential fixing (SF) technique, where the determination of scheduling variables is performed iteratively through a sequence of linear programs (LPs). Upon completing the fixing of these scheduling variables, the value of the other variables in the optimization problem can be obtained by solving an LP. 5. Power control in CR networks We further consider the case of variable transmission power in CR networks. Now, our objective is minimizing the total required bandwidth footprint product (BFP) to support a set of user sessions. As a basis, we first develop an interference model for scheduling when power control is performed at each node. This model extends existing so-called protocol models for wireless networks where transmission power is deterministic. As a result, this model can be used for a broad range of problems where power control is part of the optimization space. An efficient solution procedure based on the branch-and-bound framework and convex hull relaxations is proposed to provide (1- ε)-optimal solutions. This is the first theoretical result on this important problem. / Ph. D.

In recent years, there has been a growing research interest in throughput optimization problems in a multi-hop wireless network. MIMO (multiple-input multiple-output), as an advanced physical layer technology, has been employed in multi-hop wireless networks to increase throughput with a given bandwidth or transmit power. It exploits the use of multiple antennas at the transmitter and receiver to increase spectral efficiency by leveraging its spatial multiplexing (SM) and interference cancellation (IC) capabilities. Instead of carrying complex manipulations on matrices, degree-of-freedom(DoF) based MIMO models, which require only simple computations, are widely used in networking research to exploit MIMO's SM and IC capabilities. In this thesis, we employ a new DoF model, which can ensure feasible solution and achieve a higher DoF region than previous DoF-based models. Based on this model, we study the DoF scheduling for a multi-hop MIMO network. Specifically, we aim to maximize the minimum rate among all sessions in the network. Some researches have been done based on this model to solve throughput optimization problems with the assumption that the route of each session is given priori. Although the fixed routing decreases the size of the problem, it also limits the performance of the network to a great extent. The goal of this thesis is to employ this new model to solve the throughput maximization problem by jointly considering flow routing, scheduling, and DoF allocation for SM and IC. We formulate it as a mixed integer linear program (MILP), which cannot be solved efficiently by commercial softwares even for moderate sized networks. Thus, we develop an efficient polynomial time algorithm by customizing the sequential fixing framework. Through simulation results, we show that this algorithm can efficiently provide near-optimal solutions for networks with different sizes. / Master of Science

This dissertation examines the design and application of network coding (NC) strategies to enhance the performance of communication networks. With its ability to combine information packets from different, previously independent data flows, NC has the potential to improve the throughput, reduce delay and increase the power efficiency of communication systems in ways that have not yet been fully utilized given the current lack of processing power at relay nodes. With these motivations in mind, this dissertation presents three main contributions that employ NC to improve the efficiency of practical communication systems. First, the integration of NC and erasure coding (EC) is presented in the context of wired networks. While the throughput gains from utilizing NC have been demonstrated, and EC has been shown to be an efficient means of reducing packet loss, these have generally been done independently. This dissertation presents innovative methods to combine these two techniques through cross-layer design methodologies. Second, three methods to reduce or limit the delay introduced by NC when deployed in networks with asynchronous traffic are developed. Also, a novel opportunistic approach of applying EC for improved data reliability is designed to take advantage of unused opportunities introduced by the delay reduction methods proposed. Finally, computationally efficient methods for the selection of relay nodes and the assignment of transmit power values to minimize the total transmit power consumed in cooperative relay networks with NC are developed. Adaptive power allocation is utilized to control the formation of the network topology to maximize the efficiency of the NC algorithm. This dissertation advances the efficient deployment of NC through its integration with other algorithms and techniques in cooperative communication systems within the framework of cross-layer protocol design. The motivation is that to improve the performance of communication systems, relay nodes will need to perform more intelligent processing of data units than traditional routing. The results presented in this work are applicable to both wireless and wired networks with real-time traffic which exist in such systems ranging from cellular and ad-hoc networks to fixed optical networks.

Rateless codes, also known as fountain codes, are a class of erasure error-control codes that are particularly well suited for broadcast/multicast systems. Raptor codes, as a particularly successful implementation of digital fountain codes, have been used as the application layer forward error correction (FEC) codes in the third generation partnership program (3GPP) Multimedia Broadcast and Multicast Services (MBMS) standard. However, the application of rateless codes to wireless multimedia broadcast/multicast communications has yet to overcome two major challenges: first, wireless multimedia communications usually has stringent delay requirements. In addition, multimedia multicast has to overcome heterogeneity. To meet these challenges, we propose a rateless code design that takes the layered nature of source traffic as well as the varying quality of transmission channels into account. A convex optimization framework for the application of unequal error protection (UEP) rateless codes to synchronous and asynchronous multimedia multicast to heterogeneous users is proposed. A second thread of the thesis addresses the noisy, bursty and time- varying nature of wireless communication channels that challenge the assumption of erasure channels often used for the wired internet. In order to meet this challenge, the optimal combination of application-layer rateless code and physical layer FEC code rates in time-varying fading channels is investigated. The performance of rateless codes in hybrid error-erasure channels with memory is then studied, and a cross-layer decoding method is proposed to improve decoding performance and complexity. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2011-06-12 16:26:36.136

Two-tier macrocell-femtocell network is considered an efficient solution to enhance area spectral-efficiency, improve cell coverage and provide better quality-of-service (QoS) to mobile users. However, interference and mobility management are considered to be the major issues for successful deployment of macrocell-femtocell network. In this thesis, a unified framework is developed for interference management, resource allocation, and call admission control (CAC) for two-tier macrocell-femtocell network. Fractional frequency reuse (FFR) is considered to provide both link-level and call-level QoS measures for mobile users. In this framework, joint resource allocation and interference coordination problem is formulated as an optimization problem to obtain design parameters for sectored FFR. The CAC problem is formulated as Semi-Markov Decision Process and Value Iteration Algorithm is used to obtain optimal admission control policy. Performance of this framework is evaluated through simulations. The performance evaluation results show that the proposed framework outperforms traditional non-optimized FFR scheme in two-tier network.

Two-tier macrocell-femtocell network is considered an efficient solution to enhance area spectral-efficiency, improve cell coverage and provide better quality-of-service (QoS) to mobile users. However, interference and mobility management are considered to be the major issues for successful deployment of macrocell-femtocell network. In this thesis, a unified framework is developed for interference management, resource allocation, and call admission control (CAC) for two-tier macrocell-femtocell network. Fractional frequency reuse (FFR) is considered to provide both link-level and call-level QoS measures for mobile users. In this framework, joint resource allocation and interference coordination problem is formulated as an optimization problem to obtain design parameters for sectored FFR. The CAC problem is formulated as Semi-Markov Decision Process and Value Iteration Algorithm is used to obtain optimal admission control policy. Performance of this framework is evaluated through simulations. The performance evaluation results show that the proposed framework outperforms traditional non-optimized FFR scheme in two-tier network.