Robust Resource Allocation Algorithms In Wireless Networks

In the past decades, the dream of interconnecting every thing, everywhere, all the time has driven the fast development of wireless networking technologies. To extend the network access range with reduced cost and energy consumption, networks with multi-hop wireless networking structure have been proposed for some specific applications, such as wireless sensor networks, wireless mesh networks and mobile ad-hoc networks. However, current wireless multi-hop net-works are still inadequate to provide guaranteed quality of service (QoS) due to various dynamic factors, such as battery exhaustion, channel dynamics, external interference and topology diver-sity. Therefore, how to improve the robustness of wireless multi-hop networks in the dynamic environments is a challenging issue for wireless network practitioners. In this work, we analyze the main causes of robustness deficiency in wireless sensor networks and wireless mesh network-s, and propose corresponding solutions with different technologies including topology control, multi-radio multi-channel and resource allocation, and opportunistic routing. The contents of this thesis are organized as follows.Firstly, we consider wireless sensor networks where the location information of each sen-sor node is unknown. To improve the robustness of wireless sensor network, the main task is to ensure the network connectivity and guarantee the required coverage intensity as long as pos-sible with limited energy. To this end, we propose a topology control algorithm called adaptive random clustering (ARC), which can reduce the overall energy consumption and balance the energy usage among nodes while preserving the performance requirement. ARC forms a cluster topology using a novel cluster head competition scheme so as to provide contention free intra-cluster communication. The required coverage is achieved by adjusting the activation threshold of non-cluster-head node adaptively, and the connectivity is guaranteed by proper inter-cluster and intra-cluster transmit power control. Simulation results demonstrate that the required cover-age and connectivity can be guaranteed and the network lifetime is prolonged significantly.Secondly, assuming multiple radios and channels are available for the network, we attempt to improve the robustness of wireless mesh networks where the end-to-end traffic demands are specified. The concepts of interference margin and outage probability are incorporated to char-acterize the network robustness under channel variations and external interference. We formu-late the robust resource allocation problems as mixed integer nonlinear programming (MINLP) problems by explicitly taking into account practical radio switching, co-channel contention and multi-path routing constraints. To reduce the complexity, we exploit the special properties of the problems and decompose them into the feasibility-checking problems, and propose a bina-ry search algorithm to find the optimal solutions of the problems using an iterative procedure. By simulations using traces collected from an indoor wireless testbed, we show that our algo-rithms are more robust to the existing schemes under moderate channel variations and external interference.Thirdly, we consider the wireless mesh networks adopting both opportunistic routing and network coding techniques. We demonstrate that the robustness deficiency in this case is main-ly due to the dependency of network coding packets. We then propose a set of flow control constraints to alleviate the performance degradation caused by this problem, and formulate the robust flow control problem as a nonconvex optimization problem by taking into account of these constraints. To reduce the complexity of the problem, we propose a centralized algorithm which only considers the primary flow control constraints of the original problem, and a full distribu-tive algorithm which can operate adaptively according to the variation of link quality. Simulation results are provided to show that the proposed algorithms are superior to existing algorithms in reducing the packet dependency ratio and improving the goodput in both grid and random topology settings.Finally we conclude this thesis and suggest the directions for future research.