Applied Optimization Methods for Wireless Networks

Written in a unique style, this book is a valuable resource for faculty, graduate students, and researchers in the communications and networking area whose work interfaces with optimization. It teaches you how various optimization methods can be applied to solve complex problems in wireless networks. Each chapter reviews a specific optimization method and then demonstrates how to apply the theory in practice through a detailed case study taken from state-of-the-art research. You will learn various tips and step-by-step instructions for developing optimization models, reformulations, and transformations, particularly in the context of cross-layer optimization problems in wireless networks involving flow routing (network layer), scheduling (link layer), and power control (physical layer). Throughout, a combination of techniques from both operations research and computer science disciplines provides a holistic treatment of optimization methods and their applications. Each chapter includes homework exercises, with PowerPoint slides and a solutions manual for instructors available online. Half Title 2 Title Page 4 Imprints 5 Dedication 6 Contents 8 Preface 12 Acknowledgments 15 Copyright Permissions 17 1 Introduction 20 1.1 Book overview 20 1.2 Book outline 22 1.3 How to use this book 26 Part I Methods for Optimal Solutions 28 2 Linear programming and applications 30 2.1 Review of key results in linear programming 30 2.2 Case study: Lexicographic max-min rate allocation and node lifetime problems 32 2.3 System modeling and problem formulation 34 2.3.1 Energy model 35 2.3.2 The LMM rate allocation problem 37 2.3.3 Two incorrect approaches 38 2.4 A serial LP algorithm based on parametric analysis 39 2.4.1 Determining rate levels 40 2.4.2 Determining minimum node set for a rate level 41 2.4.3 Optimal flow routing for LMM rate allocation 42 2.4.4 Complexity analysis 44 2.4.5 Extension to variable bit rate 44 2.5 SLP-PA for the LMM node lifetime problem 44 2.5.1 The LMM node lifetime problem 44 2.5.2 Solution 45 2.6 A mirror result 46 2.7 Numerical results 49 2.7.1 SLP-PA algorithm to the LMM rate allocation problem 49 2.7.2 Mirror results 51 2.8 Chapter summary 53 2.9 Problems 55 3 Convex programming and applications 57 3.1 Review of key results in convex optimization 57 3.2 Case study: Cross-layer optimization for multi-hop MIMO networks 59 3.3 Network model 60 3.3.1 MIMO input covariance matrices 61 3.3.2 Link capacity and bandwidth allocation 61 3.3.3 Flow routing 63 3.3.4 Problem formulation 64 3.4 Dual problem decomposition 65 3.5 Solving the Lagrangian dual problem 67 3.6 Constructing a primal optimal solution 69 3.7 Numerical results 70 3.8 Chapter summary 76 3.9 Problems 77 4 Design of polynomial-time exact algorithm 80 4.1 Problem complexity vs. solution complexity 80 4.2 Case study: Optimal cooperative relay node assignment 81 4.3 Cooperative communications: a primer 81 4.4 The relay node assignment problem 84 4.5 An optimization-based formulation 86 4.6 An exact algorithm 88 4.6.1 Basic idea 88 4.6.2 Algorithmic details 88 4.6.3 Caveat on the marking mechanism 95 4.6.4 Complexity analysis 96 4.7 Proof of optimality 97 4.8 Numerical examples 101 4.8.1 Simulation setting 101 4.8.2 Results 101 4.9 Chapter summary 105 4.10 Problems 108 Part II Methods for Near-optimal and Approximation Solutions 112 5 Branch-and-bound framework and application 114 5.1 Review of branch-and-bound framework 114 5.2 Case study: Power control problem for multi-hop cognitive radio networks 119 5.3 Mathematical modeling 120 5.3.1 Necessary and sufficient condition for successful transmission 120 5.3.2 Per-node-based power control and scheduling 123 5.3.3 Flow routing and link capacity constraints 126 5.4 Problem formulation 127 5.5 A solution procedure 129 5.5.1 Linear relaxation 129 5.5.2 Local search algorithm 131 5.5.3 Selection of partitioning variables 133 5.6 Numerical examples 134 5.6.1 Simulation setting 134 5.6.2 Results 136 5.7 Chapter summary 138 5.8 Problems 138 6 Reformulation-linearization technique and applications 141 6.1 An introduction of reformulation-linearization technique (RLT) 141 6.2 Case study: Capacity maximization for multi-hop cognitive radio networks under the physical model 144 6.3 Mathematical models 145 6.3.1 Power control, scheduling, and their relationship in the SINR model 145 6.3.2 Routing and link capacity 147 6.3.3 A throughput maximization problem 148 6.4 Reformulation 148 6.5 A solution procedure 150 6.5.1 Core variables 150 6.5.2 A solution 151 6.5.3 Determining upper bounds 152 6.5.4 Determining lower bounds 153 6.5.5 Partitioning approach 156 6.6 Numerical results 157 6.6.1 Simulation setting 157 6.6.2 Results 158 6.7 Chapter summary 163 6.8 Problems 165 7 Linear approximation 167 7.1 Review of linear approximation for nonlinear terms 167 7.2 Case study: Renewable sensor networks with wireless energy transfer 170 7.3 Wireless energy transfer: a primer 172 7.4 Problem description 173 7.5 Renewable cycle construction 175 7.6 Optimal traveling path 181 7.7 Problem formulation and solution 183 7.7.1 Mathematical formulation 183 7.7.2 Reformulation 184 7.7.3 A near-optimal solution 186 7.7.4 Proof of near-optimality 189 7.8 Construction of initial transient cycle 193 7.9 Numerical examples 196 7.9.1 Simulation settings 196 7.9.2 Results 196 7.10 Chapter summary 198 7.11 Problems 198 8 Approximation algorithm and its applications - Part 1 210 8.1 Review of approximation algorithms 210 8.2 Case study: The base station placement problem 211 8.3 Network model and problem description 213 8.3.1 Network model 213 8.3.2 Problem description 213 8.4 Optimal flow routing for a given base station location 215 8.5 Search space for base station location 216 8.6 Subarea division and fictitious cost points 218 8.6.1 Subarea division 218 8.6.2 Fictitious cost point 220 8.7 Summary of algorithm and example 221 8.8 Correctness proof and complexity analysis 223 8.9 Numerical examples 226 8.10 Chapter summary 227 8.11 Problems 228 9 Approximation algorithm and its applications – Part 2 230 9.1 Introduction 230 9.2 Case study: The mobile base station problem 231 9.3 Problem and its formulation 232 9.4 From time domain to space domain 234 9.5 A (1 - epsilon)-optimal algorithm 242 9.5.1 Optimal sojourn time computation for the C-MB problem 242 9.5.2 Solution to the U-MB problem and proof of (1bold0mu mumu --dotted----)-optimality 244 9.5.3 Summary of algorithm and example 248 9.5.4 Discussions 251 9.6 Numerical examples 252 9.7 Chapter summary 259 9.8 Problems 260 Part III Methods for Efficient Heuristic Solutions 262 10 An efficient technique for mixed-integer optimization 264 10.1 Sequential fixing: an introduction 264 10.2 Case study: Spectrum sharing for cognitive radio networks 265 10.3 Mathematical modeling and problem formulation 266 10.3.1 Modeling of multi-layer characteristics 266 10.3.2 Problem formulation 271 10.4 Deriving a lower bound 272 10.5 A near-optimal algorithm based on sequential fixing 273 10.5.1 Basic algorithm 273 10.5.2 A speedup technique 275 10.6 Numerical examples 276 10.7 Chapter summary 277 10.8 Problems 279 11 Metaheuristic methods 281 11.1 Review of key results in metaheuristic methods 281 11.2 Case study: Routing for multiple description video over wireless ad hoc networks 283 11.3 Problem description 284 11.3.1 Rate-distortion regions for DD coding 285 11.3.2 Description rates and success probabilities 286 11.3.3 The optimal multi-path routing problem 289 11.4 A metaheuristic approach 290 11.4.1 Solution representation and initialization 290 11.4.2 Evaluation 291 11.4.3 Selection 291 11.4.4 Crossover 292 11.4.5 Mutation 292 11.5 Numerical examples 293 11.5.1 Near-optimality 294 11.5.2 Comparison with trajectory methods 294 11.5.3 Comparison with traditional multi-path routings 296 11.6 Chapter summary 298 11.7 Problems 299 Part IV Other Topics 300 12 Asymptotic capacity analysis 302 12.1 Review of asymptotic analysis 302 12.2 Capacity scaling laws of wireless ad hoc networks 303 12.3 Case 1: Asymptotic capacity under the protocol model 306 12.3.1 A capacity upper bound 307 12.3.2 A constructive lower bound 308 12.4 Case 2: Asymptotic capacity under the physical model 314 12.4.1 Computing an upper bound 315 12.4.2 Computing a lower bound 317 12.5 Case 3: Asymptotic capacity lower bound under the generalized physical model 319 12.5.1 Main idea 320 12.5.2 Construction of the highway 321 12.5.3 Deriving a feasible solution 328 12.6 Chapter summary 332 12.7 Problems 332 References 335 Index 346 This book teaches you how various optimization methods can be applied to solve complex problems in wireless networks. Each chapter reviews a specific optimization method and then demonstrates how to apply the theory in practice through a detailed case study taken from state-of-the-art research. You will learn various tips and step-by-step instructions for developing optimization models, reformulations, and transformations, particularly in the context of cross-layer optimization problems in wireless networks involving flow routing (network layer), scheduling (link layer), and power control (physical layer). Throughout, a combination of techniques from both operations research and computer science disciplines provides a holistic treatment of optimization methods and their applications. -- Edited summary from book Provides a variety of practical optimization techniques and modeling tips for solving challenging wireless networking problems. Case studies show how the techniques can be applied in practice, homework exercises are given at the end of each chapter, and PowerPoint slides are available online, together with a solutions manual for instructors.