Infrastructure wireless mesh networks (IWMNs) provide inexpensive deployment, flexible extension of wireless infrastructure, and easy access to the Internet. With multiple radios at each node, a capacity per node improves by transmitting over these radios simultaneously using orthogonal channels. However, without properly addressing the problem of channel assignment and routing for those nodes that form wireless infrastructures, the resulting network throughput and reliability are unlikely to meet the requirements of those highly demanding, media distribution applications. On a particular channel, poor resource allocation at a given access point/gateway of the underlying IWMN can amplify the problem even further. Motivated by these problems, we develop, based on the theory of network coding, a set of alternative solutions that addresses the above issues. We first introduce a sub-optimal solution to the joint problem of network coding, channel assignment and link scheduling for throughput optimization in the multi-channel multi-radio IWMN. We mathematically formulate the problem as a linear program, taking into account opportunistic overhearing, among other constraints. Based on this formulation, we develop a sub-optimal, auction-based algorithm for network throughput optimization. Simulation results reveal the effectiveness of our algorithm in exploiting multiple radios and channels while coping with fairness issues arising from auctions. The proposed solution also shows promising gains over traditional routing solutions. Our experimental results on an 802.11 testbed further confirm these results. The second part of this thesis then presents three AP/gateway-oriented solutions that address the link-level issues related to radio resource allocation at a particular AP/gateway node of the underlying IWMN, which operates on a given channel serving a set of wireless clients. Since the last-hop wireless link is normally a bottleneck of the IWMN, the key idea underlying all the proposed solutions is to use a version of network coding at the bottlenecked AP/gateway. We use Markov chains and the probability theory to derive several performance measures related to media distribution for both uplink and downlink applications. Via extensive simulations, we show the promising delay and reliability gains of the network-coding based schemes over the traditional schemes without network coding.

Infrastructure wireless mesh networks (IWMNs) provide inexpensive deployment, flexible extension of wireless infrastructure, and easy access to the Internet. With multiple radios at each node, a capacity per node improves by transmitting over these radios simultaneously using orthogonal channels. However, without properly addressing the problem of channel assignment and routing for those nodes that form wireless infrastructures, the resulting network throughput and reliability are unlikely to meet the requirements of those highly demanding, media distribution applications. On a particular channel, poor resource allocation at a given access point/gateway of the underlying IWMN can amplify the problem even further. Motivated by these problems, we develop, based on the theory of network coding, a set of alternative solutions that addresses the above issues. We first introduce a sub-optimal solution to the joint problem of network coding, channel assignment and link scheduling for throughput optimization in the multi-channel multi-radio IWMN. We mathematically formulate the problem as a linear program, taking into account opportunistic overhearing, among other constraints. Based on this formulation, we develop a sub-optimal, auction-based algorithm for network throughput optimization. Simulation results reveal the effectiveness of our algorithm in exploiting multiple radios and channels while coping with fairness issues arising from auctions. The proposed solution also shows promising gains over traditional routing solutions. Our experimental results on an 802.11 testbed further confirm these results. The second part of this thesis then presents three AP/gateway-oriented solutions that address the link-level issues related to radio resource allocation at a particular AP/gateway node of the underlying IWMN, which operates on a given channel serving a set of wireless clients. Since the last-hop wireless link is normally a bottleneck of the IWMN, the key idea underlying all the proposed solutions is to use a version of network coding at the bottlenecked AP/gateway. We use Markov chains and the probability theory to derive several performance measures related to media distribution for both uplink and downlink applications. Via extensive simulations, we show the promising delay and reliability gains of the network-coding based schemes over the traditional schemes without network coding.

[pt] Os esquemas de alocação fixa de canais - FCA - conferem aos Sistemas de Comunicação Móveis Celulares estabilidade com o custo da necessidade de um pré-planejamento de freqüências, trazendo como conseqüência a baixa tolerância à variabilidade de tráfego. Algoritmos de alocação dinâmica de canais - DCA - tem sido propostos por diversos autores com o intuito de minimizar estes problemas, permitindo ao sistema flexibilidade no momento da escolha do canal candidato para servir a uma ligação. Esquemas de alocação híbrida de canais - HCA, combinam as técnicas de alocação fixa com alocação dinâmica de canais, conferindo ao mesmo tempo estabilidade e flexibilidade ao sistema.Este trabalho compara os algoritmos FCA, DCA e HCA sobre um mesmo cenário de simulação, permitindo analisar o desempenho dos mesmos. O esquema FCA utilizado é o mais simples, onde o primeiro canal com o nível aceitável de relação sinal interferência é escolhido para ser alocado. O esquema DCA utiliza a técnica de Segregação de Canais - CS, permitindo ao sistema maior flexibilidade no momento da escolha do canal candidato, devido a não existência do pré-planejamento de freqüências. O terceiro algoritmo, HCA, combina os dois esquemas anteriores. Ao final, será analisado o impacto de se priorizar o procedimento de handoff utilizando-se a técnica conhecida como Canais de Guarda. / [en] Fixed channel assignment -FCA- brings to the Cellular Communication Systems stability at the cost of the use of frequency planning, leading to low tolerance to traffic variability. Dynamic channel assignment -DCA- algorithms have been proposed by several authors in order to minimize these problems,incorporating flexibility to the system with respect to channel selection. Hybrid channel assignment - HCA- combines the techniques of fixed and dynamic channel assignment, giving to the system stability and flexibility at the same time. This work compares the FCA, DCA and HCA algorithms on the same simulation scenario, allowing a complete analysis of these approaches. The FCA used is the simplest. In this algorithm, the first channel with an acceptable level of signal to interference ratio is chosen to be allocated. The DCA uses the technique of Channel Segregation -CS-, a distributed self-learning algorithm that is shown to yield very good performance. The third algorithm,HCA, combine the two previous techniques. At the end, the impact of prioritizing the procedure of handoff will be analyzed, using the technique known as Guard Channel.

In this thesis, the channel assignment and routing problems have been investigated for both cooperative and competitive Wireless Mesh networks (WMNs). A dynamic and distributed channel assignment scheme has been proposed which generates the network topologies ensuring less interference and better connectivity. The proposed channel assignment scheme is capable of detecting the node failures and mobility in an efficient manner. The channel monitoring module precisely records the quality of bi-directional links in terms of link delays. In addition, a Quality of Service based Multi-Radio Ad-hoc On Demand Distance Vector (QMR-AODV) routing protocol has been devised. QMR-AODV is multi-radio compatible and provides delay guarantees on end-to-end paths. The inherited problem of AODV’s network wide flooding has been solved by selectively forwarding the routing queries on specified interfaces. The QoS based delay routing metric, combined with the selective route request forwarding, reduces the routing overhead from 24% up to 36% and produces 40.4% to 55.89% less network delays for traffic profiles of 10 to 60 flows, respectively. A distributed channel assignment scheme has been proposed for competitive WMNs, where the problem has been investigated by applying the concepts from non-cooperative bargaining Game Theory in two stages. In the first stage of the game, individual nodes of the non-cooperative setup is considered as the unit of analysis, where sufficient and necessary conditions for the existence of Nash Equilibrium (NE) and Negotiation-Proof Nash Equilibrium (N-PNE) have been derived. A distributed algorithm has been presented with perfect information available to the nodes of the network. In the presence of perfect information, each node has the knowledge of interference experience by the channels in its collision domain. The game converges to N-PNE in finite time and the average fairness achieved by all the nodes is greater than 0.79 (79%) as measured through Jain Fairness Index. Since N-PNE and NE are not always a system optimal solutions when considered from the end-nodes prospective, the model is further extended to incorporate non-cooperative end-users bargaining between two end user’s Mesh Access Points (MAPs), where an increase of 10% to 27% in end-to-end throughput is achieved. Furthermore, a non-cooperative game theoretical model is proposed for end-users flow routing in a multi-radio multi-channel WMNs. The end user nodes are selfish and compete for the channel resources across the WMNs backbone, aiming to maximize their own benefit without taking care for the overall system optimization. The end-to-end throughputs achieved by the flows of an end node and interference experienced across the WMNs backbone are considered as the performance parameters in the utility function. Theoretical foundation has been drawn based on the concepts from the Game Theory and necessary conditions for the existence of NE have been extensively derived. A distributed algorithm running on each end node with imperfect information has been implemented to assess the usefulness of the proposed mechanism. The analytical results have proven that a pure strategy Nash Equilibrium exists with the proposed necessary conditions in a game of imperfect information. Based on a distributed algorithm, the game converges to a stable state in finite time. The proposed game theoretical model provides a more reasonable solution with a standard deviation of 2.19Mbps as compared to 3.74Mbps of the random flow routing. Finally, the Price of Anarchy (PoA) of the system is close to one which shows the efficiency of the proposed scheme.

The work in this thesis concerns the use of reinforcement learning solutions to re-source allocation problems in channelised cellular networks. The methodology of re-inforcement learning techniques was chosen for application to these problems due to its capability of finding efficient policies in a fully on-line, adaptable manner, without requiring specific environment models. All of the presented agent architectures are assumed to simultaneously learn and perform network control functions in a totally on-line and unsupervised manner, and agents are developed with a view to real-world implementability by focussing on techniques that have low resource requirements and make use of only local system information.

In this work, we consider the channel assignment problem in single radio multi-channel mobile ad-hoc networks. Specifically, we investigate the granularity of channel assignment decisions that gives the best trade-off in terms of performance and complexity. We present a new granularity for channel assignment that we refer to as component level channel assignment. The strategy is relatively simple, and is characterized by several impressive practical advantages. We also show that the theoretical performance of the component based channel assignment strategy does not lag significantly behind the optimal possible performance, and perhaps more importantly we show that when coupled with its several practical advantages, it significantly outperforms other strategies under most network conditions.

In recent years, mobile communications have become affordable and popular. High cellular capacity in terms of number of users and data-rates is in need. As the available frequency spectrums for mobile communications are limited, the utilization of the radio resources to achieve high capacity without imposing high equipment cost is of utmost importance. Recently, multi-hop cellular networks (MCNs) were introduced. These networks have the potential of enhancing the cell capacity and extending the cell coverage at low extra cost. However, in a cellular network, the cell or system capacity is inversely related to the cell size. In MCNs, the cell size, the network density and topology affect the coverage of source nodes and the total demands that can be served and, thus, the system throughput. Although the cell size is an important factor, it has not been exploited for maximizing throughput. Another major issue in MCNs is the increase in packet delay because multi-hopping is involved. High packet delay affects quality of service provisioning in these networks. In this thesis, we propose the Optimal Cell Size (OCS) and the Optimal Channel Assignment (OCA) schemes to address the cell size and packet delay issues for a time division duplex (TDD) wideband code division multiple access (W-CDMA) MCN. OCS finds the optimal cell sizes to provide an optimal balance of cell capacity and coverage to maximize the system throughput, whereas OCA assigns channels optimally in order to minimize packet relaying delay. Like many optimized schemes, OCS and OCA are computationally expensive and may not be suitable for large real-time problems. Hence, we also propose heuristics for solving the problems. For the cell size problem, we propose two heuristics: Smallest Cell Size First (SCSF) and Highest Throughput Cell Size First (HTCSF). For the channel assignment problem, we propose the Minimum Slot Waiting First (MSWF) heuristic. Simulation results show that OCS achieves high throughput compared to that of conventional (single-hop) cellular networks and OCA achieves low packet delay in MCNs. Results also show that the heuristics, SCSF, HTCSF and MSWF, provide good results compared to the optimal ones provided by OCS and OCA, respectively. / Thesis (Ph.D, Computing) -- Queen's University, 2009-02-02 22:53:41.825

Designing 802.11 wireless networks includes two major components: selection of access points (APs) in the demand areas and assignment of radio frequencies to each AP. Coverage and capacity are some key issues when placing APs in a demand area. APs need to cover all users. A user is considered covered if the power received from its corresponding AP is greater than a given threshold. Moreover, from a capacity standpoint, APs need to provide certain minimum bandwidth to users located in the coverage area. A major challenge in designing wireless networks is the frequency assignment problem. The 802.11 wireless LANs operate in the unlicensed ISM frequency, and all APs share the same frequency. As a result, as 802.11 APs become widely deployed, they start to interfere with each other and degrade network throughput. In consequence, efficient assignment of channels becomes necessary to avoid and minimize interference. In this work, an optimal AP selection was developed by balancing traffic load. An optimization problem was formulated that minimizes heavy congestion. As a result, APs in wireless LANs will have well distributed traffic loads, which maximize the throughput of the network. The channel assignment algorithm was designed by minimizing channel interference between APs. The optimization algorithm assigns channels in such a way that minimizes co-channel and adjacent channel interference resulting in higher throughput.

Scheduling algorithm is the algorithm to allocate system resources among processes and data flows. Joint channel-assignment and workload-based (CAWS) is a recently developed algorithm for scheduling in the downlink of multi-channel wireless systems, such as OFDM. Compared to well known algorithms, CAWS algorithm has been proved to throughput optimal with flow-level dynamics. In this master thesis project, we design a system that accounts for power control and for the characteristics of common radio channels. We evaluate the efficiency of the algorithm under a diverse set of conditions. We also do analysis of CAWS algorithm under different traffic density.

No description available.