Mathematical Models and Algorithms for Wireless Network Design and Optimization

Optimization techniques always play an important role in designing high-performance wireless systems. This presented thesis studies a selected set of optimization problems for different kinds of wireless networks, making use of mathematical programming techniques to find optimal solutions and of efficient heuristics to find near-optimal solutions. The basic contribution of the thesis consists in a thorough study of the notion of the compatible set, and utilizing it for formulating and solving various wireless network optimization problems. The treatment is as follows. Firstly, an overview of problem formulations for compatible set optimization is made, and an enhanced formulation based on the matching polytope is proposed (Paper I). Then, an end-to-end delay minimization problem in wireless networks based on compatible sets is formulated (Paper II). Next, a max-min fair flow problem in wireless mesh networks is studied, and three related resource allocation problems are formulated, again using the notion of the compatible set. These three optimization problems include joint optimizing static rate control with transmission scheduling (Paper III), joint optimizing transmission scheduling, dynamic rate control, routing and directional antenna placement (Paper IV), and optimizing link metrics to design routing (Paper V). Finally, an emerging technology, free space optics, is considered in order for upgrading a cellular backhaul network for which a resilient topology design problem is studied (Paper VI). The six research papers included in this thesis not only make a contribution to improve the wireless network performance and efficiently use network resources but also bridge the gap between mathematical theory, specifically mathematical programming, and engineering problems. Paper I presents two formulations for finding an optimal compatible set, differing in the way of linearizing the signal-to-noise-plus-interference ratio (SINR) constraint. By incorporating a matching polytope, an enhanced formulation is developed that can be solved by the branch-and-cut method. The numerical study shows that the enhanced formulation works more efficiently than general formulations. Paper II studies the end-to-end delay minimization problem in wireless networks. The delay refers to the required number of time slots to deliver a given set of packets. Depending on different application scenarios, two scheduling schemes are proposed. One scheme extends from the minimal frame-length scheduling, then permutates the compatible sets in the resulting frame and repeats the frame to minimize the delay. The other scheme aims at minimizing the delay by optimizing the transmission scheduling directly. Paper III studies the problem of maximizing the minimal flow in wireless mesh networks with static rate control. In wireless mesh networks, several modulation and coding schemes (MCS) are applied and each of them corresponds to a data rate and a SINR threshold. Static rate control means that each link will use one selected MCS whenever it is active. A mixed integer programming model is formulated and an efficient simulated-annealing based heuristic is proposed. This heuristic makes use of a special character of this problem which greatly helps to reduce the searching space of the solution. With the same objective as in paper III, paper IV provides optimal solutions for placing directional antennas. Directional antennas can focus the energy between a pair of communicating nodes, resulting in better spatial reuse and increased transmission range. However, they may also bring more interference to non-intended receivers within the beam, as compared with omni-directional antennas. The paper considers the use of a combination of directional and omni-directional antennas, presents a mixed integer programming model and provides several heuristics. The results show that the minimal flow is greatly increased when directional antennas are placed at proper places, and also illustrate that it is not always optimal to deploy directional antennas at all nodes. Paper V proposes a metric-driven routing design for wireless mesh networks to resolve the trade-off between the implementation simplicity and the network traffic performance. The metric-driven routing design uses link metrics as variables and computes the routes according to shortest-path algorithms. A mixed integer programming model is formulated for this issue---the results show that the metric-driven routing can achieve good network performance in terms of the maximum minimal flow. Finally, paper VI focuses on resilient topology design for cellar backhaul networks with free space optics, a technology for high-speed wireless connections. Due to unreliability of free space optical links, a network optimization method is proposed to assure k-connectivity. The optical fibers already existing in the backhaul network are reused to decrease the deployment cost and increase the system reliability. On top of that, mirrors are considered to connect nodes not in the line of sight. A comprehensive mixed integer programming model and a heuristic based on problem decomposition is developed