Mathematical Models and Algorithms for Wireless Network Design and Optimization
(2015) 66. Abstract
 Optimization techniques always play an important role in designing highperformance 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 nearoptimal 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,... (More)
 Optimization techniques always play an important role in designing highperformance 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 nearoptimal 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 endtoend delay minimization problem in wireless networks based on compatible sets is formulated (Paper II). Next, a maxmin 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 signaltonoiseplusinterference ratio (SINR) constraint. By incorporating a matching polytope, an enhanced formulation is developed that can be solved by the branchandcut method. The numerical study shows that the enhanced formulation works more efficiently than general formulations.
Paper II studies the endtoend 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 framelength 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 simulatedannealing 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 nonintended receivers within the beam, as compared with omnidirectional antennas. The paper considers the use of a combination of directional and omnidirectional 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 metricdriven routing design for wireless mesh networks to resolve the tradeoff between the implementation simplicity and the network traffic performance. The metricdriven routing design uses link metrics as variables and computes the routes according to shortestpath algorithms. A mixed integer programming model is formulated for this issuethe results show that the metricdriven 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 highspeed wireless connections. Due to unreliability of free space optical links, a network optimization method is proposed to assure kconnectivity. 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/4858524
 author
 Li, Yuan ^{LU}
 supervisor
 opponent

 Assistant Professor Cesana, Matteo, Electronics and Information Department, Politecnico di Milano, Italy
 organization
 publishing date
 2015
 type
 Thesis
 publication status
 published
 subject
 keywords
 maxmin flow, directional antenna, optimization, integer programming, cellular backhaul network design, delay minimization, SINR, compatible set
 volume
 66
 pages
 188 pages
 defense location
 Lecture hall E:1406, Department of Electrical and Information Technology, Ole Römers väg 3, Lund University Faculty of Engineering
 defense date
 20150122 10:15
 ISSN
 1654790X
 ISBN
 9789176230992
 language
 English
 LU publication?
 yes
 id
 84badb2a5bfa4751b6177477c6874ebc (old id 4858524)
 date added to LUP
 20150109 11:56:37
 date last changed
 20160919 08:45:00
@phdthesis{84badb2a5bfa4751b6177477c6874ebc, abstract = {Optimization techniques always play an important role in designing highperformance 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 nearoptimal 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 endtoend delay minimization problem in wireless networks based on compatible sets is formulated (Paper II). Next, a maxmin 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).<br/><br> 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.<br/><br> Paper I presents two formulations for finding an optimal compatible set, differing in the way of linearizing the signaltonoiseplusinterference ratio (SINR) constraint. By incorporating a matching polytope, an enhanced formulation is developed that can be solved by the branchandcut method. The numerical study shows that the enhanced formulation works more efficiently than general formulations.<br/><br> Paper II studies the endtoend 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 framelength scheduling, then permutates the compatible sets in the resulting frame and repeats the frame to minimize the delay.<br/><br> The other scheme aims at minimizing the delay by optimizing the transmission scheduling directly.<br/><br> 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 simulatedannealing 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.<br/><br> 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 nonintended receivers within the beam, as compared with omnidirectional antennas. The paper considers the use of a combination of directional and omnidirectional 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.<br/><br> Paper V proposes a metricdriven routing design for wireless mesh networks to resolve the tradeoff between the implementation simplicity and the network traffic performance. The metricdriven routing design uses link metrics as variables and computes the routes according to shortestpath algorithms. A mixed integer programming model is formulated for this issuethe results show that the metricdriven routing can achieve good network performance in terms of the maximum minimal flow.<br/><br> Finally, paper VI focuses on resilient topology design for cellar backhaul networks with free space optics, a technology for highspeed wireless connections. Due to unreliability of free space optical links, a network optimization method is proposed to assure kconnectivity. 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.}, author = {Li, Yuan}, isbn = {9789176230992}, issn = {1654790X}, keyword = {maxmin flow,directional antenna,optimization,integer programming,cellular backhaul network design,delay minimization,SINR,compatible set}, language = {eng}, pages = {188}, school = {Lund University}, title = {Mathematical Models and Algorithms for Wireless Network Design and Optimization}, volume = {66}, year = {2015}, }