Wireless Network Design (eBook)

Optimization Models and Solution Procedures

Jeff Kennington, Eli Olinick, Dinesh Rajan (Herausgeber)

eBook Download: PDF

2010 | 2011
XIX, 373 Seiten
Springer New York (Verlag)
978-1-4419-6111-2 (ISBN)

Infos

This book surveys state-of-the-art optimization modeling for design, analysis, and management of wireless networks, such as cellular and wireless local area networks (LANs), and the services they deliver. The past two decades have seen a tremendous growth in the deployment and use of wireless networks. The current-generation wireless systems can provide mobile users with high-speed data services at rates substantially higher than those of the previous generation. As a result, the demand for mobile information services with high reliability, fast response times, and ubiquitous connectivity continues to increase rapidly. The optimization of system performance has become critically important both in terms of practical utility and commercial viability, and presents a rich area for research.

In the editors' previous work on traditional wired networks, we have observed that designing low cost, survivable telecommunication networks involves extremely complicated processes. Commercial products available to help with this task typically have been based on simulation and/or proprietary heuristics.  As demonstrated in this book, however, mathematical programming deserves a prominent place in the designer's toolkit. Convenient modeling languages and powerful optimization solvers have greatly facilitated the implementation of mathematical programming theory into the practice of commercial network design.

These points are equally relevant and applicable in today's world of wireless network technology and design. But there are new issues as well: many wireless network design decisions, such as routing and facility/element location, must be dealt with in innovative ways that are unique and distinct from wired (fiber optic) networks. The book specifically treats the recent research and the use of modeling languages and network optimization techniques that are playing particularly important and distinctive roles in the wireless domain.

Inhalt

Preface 6
Contents 8
List of Contributors 16
Acronyms 20
Chapter 1 22
Introduction to Optimization in Wireless Networks 22
Part I Background 28
Chapter 2 29
Introduction to Wireless Communications 29
2.1 Introduction 29
2.1.1 Layered Architecture 30
2.1.2 Digital Communication System 31
2.2 Digital Modulation in Single User Point-to-point Communication 34
2.3 Information Theoretic Capacity and Coding 38
2.4 Channel Coding 43
2.4.1 Block Codes 44
2.4.2 Convolutional Codes 46
2.5 Multiuser Communication 47
2.5.1 Data Link Layer Random Access Methods 48
2.5.2 Physical layer Multiuser Signaling Schemes 52
2.5.2.1 Direct Sequence Code Division Multiple Access DS-CDMA 52
2.5.2.2 Frequency Hopping Code Division Multiple Access (FH-CDMA) 56
2.5.2.3 Orthogonal Frequency Division Multiplexing (OFDM) 56
2.5.3 Power Control 59
2.6 Advanced Transceiver Methods 62
2.6.1 Multiple Antenna Systems 63
2.6.2 Scheduling, Rate, and Power Control 64
2.7 Conclusions 64
References 64
Chapter 3 67
Channel Models forWireless Communication Systems 67
3.1 Introduction 67
3.2 Wireless Channel 67
3.3 Propagation Model forWireless Channel 68
3.4 Mathematical Modeling ofWireless Channels 69
3.4.1 Experiments to Characterize Wireless Channels 70
3.4.1.1 Path Loss Models 70
3.4.2 Rayleigh and Ricean Flat Fading Channels 72
3.4.3 Doppler Spread Due to Relative Motion Between Transmitter and Receiver and Coherence Time 73
3.4.4 Finite Impulse Response Channel Model for Frequency Selective Fading Channels 75
3.4.5 Delay Spread Parameters 75
3.4.6 Decorrelation Distance of the Channel 76
3.5 Channel Models for Systems using Multiple Antennas 77
3.5.1 Spatial Wireless Channel Models using Geometry 77
3.5.2 Geometrically Based Single-Bounce Statistical Models 78
3.5.2.1 Geometrically Based Single Bounce Models 78
3.5.2.2 GaussianWide Sense Stationary Uncorrelated Scattering model 79
3.5.2.3 Gaussian Angle Arrival Model 79
3.5.2.4 Dominant Reflectors Model 80
3.5.2.5 Typically Urban (TU) and Bad Urban (BU) Models 80
3.5.2.6 Indoor Models Based on Measurement Data 81
3.6 Conclusion 81
References 81
Chapter 4 85
An Introduction to Integer and Large-Scale Linear Optimization 85
4.1 Introduction 85
4.2 Basics of Modeling and Optimization 86
4.2.1 Foundations of Optimization Models 86
4.2.2 Linear Programming Problems 88
4.2.3 Duality 91
4.2.4 Modeling with Nonlinear and Discrete Variables 94
4.2.5 Integer Programming Methods 95
4.3 Large Scale Optimization 101
4.3.1 Benders Decomposition 102
4.3.2 Dantzig-Wolfe Decomposition 107
4.3.3 Lagrangian Optimization 112
4.3.4 Other Methods 114
4.3.4.1 Basis Partitioning 114
4.3.4.2 Interior Point Methods 115
4.3.4.3 Heuristics 115
References 116
Part II Optimization Problems for Networks with Infrastructure 118
Chapter 5 119
Mathematical Programming Models for Third GenerationWireless Network Design 119
5.1 Introduction 119
5.2 Tower Location and Subscriber Assignment in CDMA Networks 122
5.2.1 The Core Model 122
5.2.2 Challenges in Solving the Core Model 125
5.3 Extensions to the Core Model 125
5.3.1 SIR-Based Power Control 126
5.3.2 Profit Maximization with Minimum-Service Restrictions 127
5.3.3 Infrastructure 128
5.3.4 The Power-Revenue Trade-Off 131
5.3.5 Additional Design Considerations 132
5.4 Solving the Models 134
5.4.1 The Nearest Available Tower Principle 134
5.4.2 Randomized Greedy Search 135
5.4.3 Improving Branch-and-Bound Performance 136
5.4.4 Dealing with Numerical Instability 138
5.4.5 Reducing Problem Size 139
References 140
Chapter 6 144
Optimization Based WLAN Modeling and Design 144
6.1 Introduction 145
6.2 Literature Survey 146
6.2.1 Site Surveys 146
6.2.2 Coverage Models 147
6.2.3 Channel Assignment 148
6.2.4 Access Point Placement 151
6.2.5 Proprietary Design Tools 151
6.2.6 Current State-of-the-Art 153
6.3 A Maximimum Capacity-Oriented Model 153
6.3.1 Solution Techniques for the Capacity-Oriented Model 157
6.3.2 Empirical Analysis 158
6.4 Summary and Conclusions 160
Appendix A: Attenuation Calculation 161
References 162
Chapter 7 164
Spectrum Auctions 164
7.1 Introduction 164
7.2 Some Auction Terms and Mechanisms 165
7.3 The First Spectrum Auction: The New Zealand Experiment 169
7.4 Evolution of the US Simultaneous Ascending Auction (SAA) Design 170
7.5 Combinatorial Auction Designs and their Use for Spectrum Allocation 177
7.5.1 Sealed-bid Combinatorial Designs 178
7.5.2 Two Combinatorial Ascending Auction Designs 182
7.5.2.1 General Ascending Package-bidding Design: 182
7.5.2.2 Clock Designs: 185
7.6 The Need for Bidder-aide Tools 189
7.7 Conclusions 190
References 191
Chapter 8 194
The Design of Partially Survivable Networks 194
8.1 Introduction 194
8.2 The Single Period Problem 196
8.2.1 Problem Formulation 196
8.2.2 Reduction to a Binary Knapsack Problem 197
8.3 The Multi-period Problem 199
8.3.1 Problem Description and Formulations 199
8.3.2 The Solution Procedure 201
8.3.2.1 Linear Programming Column Generation 201
8.3.2.2 Representing the Subproblem 202
8.3.2.3 Integer Programming and Column Generation 204
8.3.3 Computational Experiments 205
8.4 The Single Period Problem with Capacity Restrictions 206
8.4.1 A Partitioning Formulation 208
8.4.1.1 Representing the Subproblem 209
8.4.1.2 Reducing the Impact of Degeneracy 210
8.4.1.3 A Greedy Heuristic 211
8.4.2 Computational Experiments 211
8.5 Conclusions 211
References 213
Part III Optimization Problems in Ad Hoc Networks 214
Chapter 9 215
Routing in Mobile Ad Hoc Networks 215
9.1 Ad Hoc Networks 215
9.2 What is Routing? 216
9.3 Ad Hoc in the Link Layer 218
9.3.1 Ad Hoc Mode in Wi-Fi 219
9.3.2 Bluetooth Link Layer 221
9.4 Ad Hoc Routing Protocols 223
9.4.1 Introduction to Ad Hoc Routing Protocols 223
9.4.2 Reactive Protocols 224
9.4.2.1 AODV (Ad hoc On Demand Distance Vector) 224
9.4.2.2 DSR (Dynamic Source Routing) 225
9.4.3 Proactive Protocols 226
9.4.3.1 OLSR (Optimized Link State Routing Protocol) 226
9.4.3.2 TBRPF (Topology Dissemination Based on Reverse-Path Forwarding) 227
9.5 Quality of Service in Ad Hoc Networks 227
9.5.1 FQMM (Flexible QoS Model for MANETs) 228
9.5.2 CEDAR (Core-Extraction Distributed Ad hoc Routing) 229
9.5.3 TBP (Ticket-based Probing) 229
9.5.4 INSIGNIA 230
9.5.5 SWAN (Stateless Wireless Ad hoc Network) 230
9.5.6 QOLSR (Quality of Service for OLSR) 231
9.6 Conclusion 232
References 232
Chapter 10 234
Compact Integer Programming Models for Power-optimal Trees in Ad HocWireless Networks 234
10.1 Introduction 234
10.1.1 Problem Overview 236
10.1.2 Outline of the Chapter 237
10.2 Problem Definitions 237
10.2.1 Notation and Assumptions 237
10.2.2 Minimum Energy Broadcast and Multicast 239
10.2.3 Range Assignment 240
10.2.4 Optimal Trees and Arborescence: Illustrative Example 241
10.3 Network Flow Models for MET 243
10.3.1 Models and Analysis 244
10.3.2 Models Based on Incremental Power 247
10.4 Network Flow Models for RAP 248
10.5 A Strong Multi-tree Model for RAP 249
10.5.1 The Model 249
10.5.2 LP Strength 251
10.6 Experimental Results 252
10.6.1 Results for MET 253
10.6.2 Results for RAP 254
10.7 Concluding Remarks 258
References 259
Chapter 11 262
Improving Network Connectivity in Ad Hoc Networks Using Particle Swarm Optimization and Agents 262
11.1 Introduction 262
11.2 Background 263
11.3 Proposed MANET Management System and Problem Description 265
11.3.1 Objectives and Evaluating Network Connectivity 265
11.3.2 Future User Location Prediction 266
11.3.3 Optimization Problem and Deployment Decision 267
11.4 Particle Swarm Optimization and Implementation 268
11.4.1 Particle Swarm Optimization (PSO) 268
11.4.2 The Optimization Procedure 270
11.4.3 Semi-Intelligent Agent Node Behavior 272
11.5 Computational Experiments 273
11.5.1 Mobility Simulation Environment 274
11.5.2 The Effect of Number of Agents, Future Location Prediction, and Clustering 275
11.5.3 Comparative Performance of the PSO Algorithm 277
11.6 Conclusions 279
References 280
Part IV Optimization Problems in the Operation of Wireless Networks 283
Chapter 12 284
Simulation-Based Methods for Network Design 284
12.1 Introduction 285
12.2 Simulation Methodologies: a Taxonomy 287
12.3 Validating Discrete Event Simulations: the Random Number Seed and the Confidence Interval 289
12.4 Survey of Simulation forWireless Network Design 293
12.5 Case Studies 294
12.5.1 Traffic Modeling Application 295
12.5.2 Networkability and Impact Assessment Application 297
12.5.3 Network Operations and Capacity Planning 298
12.5.4 Network Research and Development 299
12.5.5 Network Emulation with Click 303
12.6 Conclusions 305
References 305
Chapter 13 307
Optimization of Wireless Broadband (WiMAX) Systems 307
13.1 Introduction 307
13.2 Brief Description ofWiMAX 309
13.2.1 WiMAX Physical Layer 309
13.2.2 WiMAX MAC Layer 312
13.3 Radio Resource Allocation Optimization 314
13.3.1 Modulation Coding Scheme Selection 315
13.3.2 MIMO Mode Selection 317
13.3.3 Power Control 319
13.3.3.1 Downlink Power Control 319
13.3.3.2 UL Power Control 319
13.3.3.3 Uplink Open Loop Power Control 320
13.3.4 Link Adaptation 321
13.4 Scheduling Optimization 322
13.4.1 Round Robin 322
13.4.2 Proportional Fair 323
13.4.3 Max System Throughput 324
13.4.4 WiMAX QoS Policy 325
13.4.4.1 Unsolicited Grant Service (UGS) 325
13.4.4.2 Real-time Polling Services (rtPS) 325
13.4.4.3 Extended Real-time Polling Services (ErtPS) 326
13.4.4.4 Non Real-time Polling Services (nrtPS) 326
13.4.4.5 Best Effort Service (BE) 326
13.5 System Simulations 327
13.6 Conclusion 330
References 331
Chapter 14 332
Cross Layer Scheduling inWireless Networks 332
14.1 Introduction 332
14.2 Wireless Channel Capacity 333
14.2.1 Point-to-Point Capacity with Perfect Transmitter CSI 335
14.2.2 Multiuser Capacity with Perfect Transmitter CSI on the Uplink 337
14.3 A Framework for Cross Layer Scheduling 340
14.3.1 Opportunistic Scheduling 340
14.3.2 Energy Efficient Scheduling 341
14.3.3 System Model for Centralized Scheduling 341
14.4 Fair Scheduling 344
14.4.1 Notions of Fairness 345
14.4.2 Fair Scheduling Algorithms 345
14.5 Power Optimal Scheduling 346
14.5.1 Single User Scheduling 347
14.5.1.1 The Lagrangian Approach 348
14.5.1.2 Structural Properties of the Optimal Policy 349
14.5.1.3 Learning Algorithm for Scheduling 350
14.5.2 Multiuser Uplink Scheduling 353
14.5.2.1 Rate Determination Algorithm 354
14.5.2.2 User Selection Algorithm 355
14.5.2.3 Algorithm Analysis 355
14.6 Scheduling Schemes that Maximize Throughput 356
14.6.1 Throughput Optimal Scheduling 357
14.6.2 Delay Optimal Scheduling 358
Bibliographic Notes 360
References 361
Chapter 15 364
Major Trends in Cellular Networks and Corresponding Optimization Issues 364
15.1 Introduction 364
15.2 Current Situation 366
15.3 Overview of Solution Approaches 368
15.4 NewWireless Access Technologies 371
15.5 Backhauling and Transport 372
15.6 Power Efficiency 375
15.7 Leveraging Assets to Protect and Increase Revenues 376
15.8 Low Income Populations 377
15.8.1 Cost Reduction 378
15.8.2 Value 380
15.9 Conclusions 382
References 382

Produkt-Details

• Erscheint lt. Verlag: 10.11.2010
• Reihe/Serie: International Series in Operations Research & Management Science
• Reihe/Serie: International Series in Operations Research & Management Science
• Zusatzinfo: XIX, 373 p.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Informatik ► Weitere Themen ► Hardware
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Studium ► 1. Studienabschnitt (Vorklinik) ► Biochemie / Molekularbiologie
• Themenwelt: Technik ► Nachrichtentechnik
• Themenwelt: Wirtschaft ► Allgemeines / Lexika
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Unternehmensführung / Management
• Schlagworte: Ad-Hoc Networks • Capacity Planning • Information and Communication, Circuits • Operations Management • Optimization models • Wireless Network Design
• ISBN-10: 1-4419-6111-9 / 1441961119
• ISBN-13: 978-1-4419-6111-2 / 9781441961112