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-ofthe-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 available online for students and instructors, and a solutions manual for instructors only. To access the materials, please visit www.cambridge.org/hou.

Reasons for writing the book In recent years, there has been a growing trend in applying optimization approaches to study wireless networks. Such an approach is usually necessary when the underlying goal is to pursue fundamental performance limits or theoretical results. This book is written to serve this need and is mainly targeted to graduate students who are conducting theoretical research in wireless networks using optimization-based approaches. This book will also serve as a very useful reference for researchers who wish to explore various optimization techniques as part of their research methodologies.
To prepare a graduate student in either electrical and computer engineering (ECE) or computer science (CS) to conduct fundamental research in wireless networks, an ideal roadmap would include a series of graduate courses in operations research (OR) and CS, in addition to traditional communications and networking courses in ECE. These OR and CS courses would include (among others) linear programming, nonlinear programming, integer programming from OR, and complexity theory and algorithm design and analysis from CS. Today, these courses are typically offered as core courses within the respective disciplines. Instructors in OR and CS departments typically have little knowledge of wireless networks and are unable to make a connection between the mathematical tools and techniques in these courses and problemsolving skills in wireless networks. ECE/CS students often find it difficult to see how these courses would benefit their research in wireless networks. Due to this gap between teaching scopes and learning expectations, we find that the learning experience of our ECE/CS students in these courses is passive (or "blind") at best, as they do not have a clear picture of how these courses will benefit their research.
One approach to bridge this gap is to offer a course that reviews a collection of mathematical tools from OR and CS (with a focus on optimization techniques) and shows how they can be used to address some challenging problems in wireless networks. This book is written for this purpose.
Each chapter in this book starts with a brief pointer to the underlying optimization technique (with references to tutorials or textbooks so that students can do an in-depth study in a formal course or on their own). The chapter then immediately delves into a detailed case study in wireless networks to which the technique will be applied. The focus in each chapter is to show how the underlying technique can be used to solve a challenging problem in wireless networks. To achieve this goal, we offer details on how to formulate a research problem into a formal optimization model, reformulate or transform it in order to improve mathematical tractability, and apply the underlying optimization technique (with necessary customizations that are specific to the underlying problem) to derive an optimal or near-optimal solution.
We have taught this course a number of times to ECE and CS graduate students at Virginia Tech, using chapters from this book. The response from the students has been overwhelmingly positive. In particular, we find that:
For a graduate student (regardless of whether they have taken related OR or CS courses), this course opens a new landscape or perspective on what optimization techniques are available and how they can be applied to solve hard problems in wireless networks;
For those graduate students who are currently taking or will take the aforementioned OR and CS courses, this course will help them better appreciate the mathematical techniques in such OR and CS courses. The student will also have a better purpose and a stronger motivation when she takes these core courses in her future study.
We recognize that a single-volume book cannot possibly cover all techniques exhaustively. Neither is it our intention to cover everything in one book. Nevertheless, we have organized this book into four parts, where every chapter focuses on a single technique. We hope this organization will serve our purpose of offering a first course on this important subject of Applied Optimization Methods in Wireless Networks. Our experience shows that after taking this course, students become substantially more mature mathematically. Most of them are able to consciously develop their learning paths into many areas in OR and CS not covered in this book in order to further expand their own mathematical capabilities. This is an important ingredient in their life-long learning and discovery.
Finally, the idea of having a book that offers a systematic coverage of optimization techniques and their applications in wireless networks is a very natural one. Unfortunately (and quite surprisingly), after a rather thorough survey of the market (when we presented our initial proposal to our publisher), we found that there were hardly any such books available. The closest book that we can find that by Dimitri Bertsekas: Network Optimization: Continuous and Discrete Models (Athena Scientific, 1998). But that book still falls short in showing students suitable case studies that are relevant to modern wireless networks.
On the other hand, most other books addressing network optimization follow a problem-oriented approach (vs. our method-oriented approach). They do not offer a systematic treatment of the underlying optimization techniques like we do in this book. To make this point clear, we quote the following text from the preface of the book Combinatorial Optimization in Communication Networks, edited by Maggie Xiaoyan Cheng, Yingshu Li, and Ding-Zhu Du (Springer, 2006), to explain why the problem-oriented approach was adopted by most authors:
Two approaches were considered: optimization method oriented (starting from combinatorial optimization methods and finding appropriate network problems as examples) and network problem oriented (focusing on specific network problems and seeking appropriate combinatorial optimization methods to solve them). We finally decided to use the problem-oriented approach, mainly because of the availability of papers: most papers in the recent literature appear to address very specific network problems, and combinatorial optimization comes as a convenient problem solver.
Such a problem-oriented approach offers a convenient way of composing a book quickly (i.e., by assembling some research papers in the literature into an edited volume). But books based on such a problem-oriented approach, although useful as a reference book, do not teach graduate students optimization techniques in a systematic manner. This critical dearth in the existing literature was our main motivation for writing this book and bringing it to the community.

Preface page xi

Acknowledgments xiv

Copyright Permissions xvi

1 Introduction 1

1.1 Book overview 1

1.2 Book outline 3

1.3 How to use this book 7

Part I Methods for Optimal Solutions 9

2 Linear programming and applications 11

      2.1 Review of key results in linear programming 11

      2.2 Case study: Lexicographic max-min rate allocation and node lifetime problems 13

      2.3 System modeling and problem formulation 15

      2.4 A serial LP algorithm based on parametric analysis 20

      2.5 SLP-PA for the LMM node lifetime problem 25

      2.6 A mirror result 27

      2.7 Numerical results 30

      2.8 Chapter summary 34

      2.9 Problems 36

3 Convex programming and applications 38

      3.1 Review of key results in convex optimization 38

      3.2 Case study: Cross-layer optimization for multi-hop MIMO networks 40

      3.3 Network model 41

      3.4 Dual problem decomposition 46

      3.5 Solving the Lagrangian dual problem 48

      3.6 Constructing a primal optimal solution 50

      3.7 Numerical results 51

      3.8 Chapter summary 57

      3.9 Problems 58

4 Design of polynomial-time exact algorithm 61

      4.1 Problem complexity vs. solution complexity 61

      4.2 Case study: Optimal cooperative relay node assignment 62

      4.3 Cooperative communications: a primer 62

      4.4 The relay node assignment problem 65

      4.5 An optimization-based formulation 67

      4.6 An exact algorithm 69

      4.7 Proof of optimality 78

      4.8 Numerical examples 82

      4.9 Chapter summary 86

      4.10 Problems 89

Part II Methods for Near-optimal and Approximation Solutions 93

5 Branch-and-bound framework and application 95

      5.1 Review of branch-and-bound framework 95

      5.2 Case study: Power control problem for multi-hop cognitive radio networks 100

      5.3 Mathematical modeling 101

      5.4 Problem formulation 108

      5.5 A solution procedure 110

      5.6 Numerical examples 115

      5.7 Chapter summary 119

      5.8 Problems 119

6 Reformulation-Linearization Technique and applications 122

      6.1 An introduction of Reformulation-Linearization Technique (RLT) 122

      6.2 Case study: Capacity maximization for multi-hop cognitive radio networks under the physical model 125

      6.3 Mathematical models 126

      6.4 Reformulation 129

      6.5 A solution procedure 131

      6.6 Numerical results 138

      6.7 Chapter summary 144

      6.8 Problems 146

7 Linear approximation 148

      7.1 Review of linear approximation for nonlinear terms 148

      7.2 Case study: Renewable sensor networks with wireless energy transfer 151

      7.3 Wireless energy transfer: a primer 153

      7.4 Problem description 154

      7.5 Renewable cycle construction 156

      7.6 Optimal traveling path 162

      7.7 Problem formulation and solution 164

      7.8 Construction of initial transient cycle 174

      7.9 Numerical examples 176

      7.10 Chapter summary 180

      7.11 Problems 185

8 Approximation algorithm and its applications – Part 1 191

      8.1 Review of approximation algorithms 191

      8.2 Case study: The base station placement problem 192

      8.3 Network model and problem description 194

      8.4 Optimal flow routing for a given base station location 196

      8.5 Search space for base station location 197

      8.6 Subarea division and fictitious cost points 199

      8.7 Summary of algorithm and example 202

      8.8 Correctness proof and complexity analysis 204

      8.9 Numerical examples 207

      8.10 Chapter summary 208

      8.11 Problems 209

9 Approximation algorithm and its applications – Part 2 211

      9.1 Introduction 211

      9.2 Case study: The mobile base station problem 212

      9.3 Problem and its formulation 213

      9.4 From time domain to space domain 215

      9.5 A (1 − ∈)-optimal algorithm 223

      9.6 Numerical examples 233

      9.7 Chapter summary 240

      9.8 Problems 241

Part III Methods for Efficient Heuristic Solutions 243

10 An efficient technique for mixed-integer optimization 245

      10.1 Sequential fixing: an introduction 245

      10.2 Case study: Spectrum sharing for cognitive radio networks 246

      10.3 Mathematical modeling and problem formulation 247

      10.4 Deriving a lower bound 253

      10.5 A near-optimal algorithm based on sequential fixing 254

      10.6 Numerical examples 257

      10.7 Chapter summary 258

      10.8 Problems 260

11 Metaheuristic methods 262

      11.1 Review of key results in metaheuristic methods 262

      11.2 Case study: Routing for multiple description video over wireless ad hoc networks 264

      11.3 Problem description 265

      11.4 A metaheuristic approach 271

      11.5 Numerical examples 274

      11.6 Chapter summary 279

      11.7 Problems 280

Part IV Other Topics 281

12 Asymptotic capacity analysis 283

      12.1 Review of asymptotic analysis 283

      12.2 Capacity scaling laws of wireless ad hoc networks 284

      12.3 Case 1: Asymptotic capacity under the protocol model 287

      12.4 Case 2: Asymptotic capacity under the physical model 295

      12.5 Case 3: Asymptotic capacity lower bound under the generalized physical model 300

      12.6 Chapter summary 313

      12.7 Problems 313

Bibliography 316

Index 327

Hanif D. Sherali is a University Distinguished Professor Emeritus in the Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia, USA. He is an elected member of the U.S. National Academy of Engineering.

中科院文献情报中心