Kennington / Olinick / Rajan Wireless Network Design

Optimization Models and Solution Procedures
1. Auflage 2010
ISBN: 978-1-4419-6111-2
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 158, 373 Seiten

Reihe: International Series in Operations Research & Management Science

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.

Autoren/Hrsg.

Kennington, Jeff

Olinick, Eli

Rajan, Dinesh

Inhaltsverzeichnis

1;Preface;6
2;Contents;8
3;List of Contributors;16
4;Acronyms;20
5;Chapter 1;22
5.1;Introduction to Optimization in Wireless Networks;22
6;Part I Background;28
6.1;Chapter 2;29
6.1.1;Introduction to Wireless Communications;29
6.1.1.1;2.1 Introduction;29
6.1.1.1.1;2.1.1 Layered Architecture;30
6.1.1.1.2;2.1.2 Digital Communication System;31
6.1.1.2;2.2 Digital Modulation in Single User Point-to-point Communication;34
6.1.1.3;2.3 Information Theoretic Capacity and Coding;38
6.1.1.4;2.4 Channel Coding;43
6.1.1.4.1;2.4.1 Block Codes;44
6.1.1.4.2;2.4.2 Convolutional Codes;46
6.1.1.5;2.5 Multiuser Communication;47
6.1.1.5.1;2.5.1 Data Link Layer Random Access Methods;48
6.1.1.5.2;2.5.2 Physical layer Multiuser Signaling Schemes;52
6.1.1.5.2.1;2.5.2.1 Direct Sequence Code Division Multiple Access DS-CDMA;52
6.1.1.5.2.2;2.5.2.2 Frequency Hopping Code Division Multiple Access (FH-CDMA);56
6.1.1.5.2.3;2.5.2.3 Orthogonal Frequency Division Multiplexing (OFDM);56
6.1.1.5.3;2.5.3 Power Control;59
6.1.1.6;2.6 Advanced Transceiver Methods;62
6.1.1.6.1;2.6.1 Multiple Antenna Systems;63
6.1.1.6.2;2.6.2 Scheduling, Rate, and Power Control;64
6.1.1.7;2.7 Conclusions;64
6.1.1.8;References;64
6.2;Chapter 3;67
6.2.1;Channel Models forWireless Communication Systems;67
6.2.1.1;3.1 Introduction;67
6.2.1.2;3.2 Wireless Channel;67
6.2.1.3;3.3 Propagation Model forWireless Channel;68
6.2.1.4;3.4 Mathematical Modeling ofWireless Channels;69
6.2.1.4.1;3.4.1 Experiments to Characterize Wireless Channels;70
6.2.1.4.1.1;3.4.1.1 Path Loss Models;70
6.2.1.4.2;3.4.2 Rayleigh and Ricean Flat Fading Channels;72
6.2.1.4.3;3.4.3 Doppler Spread Due to Relative Motion Between Transmitter and Receiver and Coherence Time;73
6.2.1.4.4;3.4.4 Finite Impulse Response Channel Model for Frequency Selective Fading Channels;75
6.2.1.4.5;3.4.5 Delay Spread Parameters;75
6.2.1.4.6;3.4.6 Decorrelation Distance of the Channel;76
6.2.1.5;3.5 Channel Models for Systems using Multiple Antennas;77
6.2.1.5.1;3.5.1 Spatial Wireless Channel Models using Geometry;77
6.2.1.5.2;3.5.2 Geometrically Based Single-Bounce Statistical Models;78
6.2.1.5.2.1;3.5.2.1 Geometrically Based Single Bounce Models;78
6.2.1.5.2.2;3.5.2.2 GaussianWide Sense Stationary Uncorrelated Scattering model;79
6.2.1.5.2.3;3.5.2.3 Gaussian Angle Arrival Model;79
6.2.1.5.2.4;3.5.2.4 Dominant Reflectors Model;80
6.2.1.5.2.5;3.5.2.5 Typically Urban (TU) and Bad Urban (BU) Models;80
6.2.1.5.2.6;3.5.2.6 Indoor Models Based on Measurement Data;81
6.2.1.6;3.6 Conclusion;81
6.2.1.7;References;81
6.3;Chapter 4;85
6.3.1;An Introduction to Integer and Large-Scale Linear Optimization;85
6.3.1.1;4.1 Introduction;85
6.3.1.2;4.2 Basics of Modeling and Optimization;86
6.3.1.2.1;4.2.1 Foundations of Optimization Models;86
6.3.1.2.2;4.2.2 Linear Programming Problems;88
6.3.1.2.3;4.2.3 Duality;91
6.3.1.2.4;4.2.4 Modeling with Nonlinear and Discrete Variables;94
6.3.1.2.5;4.2.5 Integer Programming Methods;95
6.3.1.3;4.3 Large Scale Optimization;101
6.3.1.3.1;4.3.1 Benders Decomposition;102
6.3.1.3.2;4.3.2 Dantzig-Wolfe Decomposition;107
6.3.1.3.3;4.3.3 Lagrangian Optimization;112
6.3.1.3.4;4.3.4 Other Methods;114
6.3.1.3.4.1;4.3.4.1 Basis Partitioning;114
6.3.1.3.4.2;4.3.4.2 Interior Point Methods;115
6.3.1.3.4.3;4.3.4.3 Heuristics;115
6.3.1.4;References;116
7;Part II Optimization Problems for Networks with Infrastructure;118
7.1;Chapter 5;119
7.1.1;Mathematical Programming Models for Third GenerationWireless Network Design;119
7.1.1.1;5.1 Introduction;119
7.1.1.2;5.2 Tower Location and Subscriber Assignment in CDMA Networks;122
7.1.1.2.1;5.2.1 The Core Model;122
7.1.1.2.2;5.2.2 Challenges in Solving the Core Model;125
7.1.1.3;5.3 Extensions to the Core Model;125
7.1.1.3.1;5.3.1 SIR-Based Power Control;126
7.1.1.3.2;5.3.2 Profit Maximization with Minimum-Service Restrictions;127
7.1.1.3.3;5.3.3 Infrastructure;128
7.1.1.3.4;5.3.4 The Power-Revenue Trade-Off;131
7.1.1.3.5;5.3.5 Additional Design Considerations;132
7.1.1.4;5.4 Solving the Models;134
7.1.1.4.1;5.4.1 The Nearest Available Tower Principle;134
7.1.1.4.2;5.4.2 Randomized Greedy Search;135
7.1.1.4.3;5.4.3 Improving Branch-and-Bound Performance;136
7.1.1.4.4;5.4.4 Dealing with Numerical Instability;138
7.1.1.4.5;5.4.5 Reducing Problem Size;139
7.1.1.5;References;140
7.2;Chapter 6;144
7.2.1;Optimization Based WLAN Modeling and Design;144
7.2.1.1;6.1 Introduction;145
7.2.1.2;6.2 Literature Survey;146
7.2.1.2.1;6.2.1 Site Surveys;146
7.2.1.2.2;6.2.2 Coverage Models;147
7.2.1.2.3;6.2.3 Channel Assignment;148
7.2.1.2.4;6.2.4 Access Point Placement;151
7.2.1.2.5;6.2.5 Proprietary Design Tools;151
7.2.1.2.6;6.2.6 Current State-of-the-Art;153
7.2.1.3;6.3 A Maximimum Capacity-Oriented Model;153
7.2.1.3.1;6.3.1 Solution Techniques for the Capacity-Oriented Model;157
7.2.1.3.2;6.3.2 Empirical Analysis;158
7.2.1.4;6.4 Summary and Conclusions;160
7.2.1.5;Appendix A: Attenuation Calculation;161
7.2.1.6;References;162
7.3;Chapter 7;164
7.3.1;Spectrum Auctions;164
7.3.1.1;7.1 Introduction;164
7.3.1.2;7.2 Some Auction Terms and Mechanisms;165
7.3.1.3;7.3 The First Spectrum Auction: The New Zealand Experiment;169
7.3.1.4;7.4 Evolution of the US Simultaneous Ascending Auction (SAA) Design;170
7.3.1.5;7.5 Combinatorial Auction Designs and their Use for Spectrum Allocation;177
7.3.1.5.1;7.5.1 Sealed-bid Combinatorial Designs;178
7.3.1.5.2;7.5.2 Two Combinatorial Ascending Auction Designs;182
7.3.1.5.2.1;7.5.2.1 General Ascending Package-bidding Design:;182
7.3.1.5.2.2;7.5.2.2 Clock Designs:;185
7.3.1.6;7.6 The Need for Bidder-aide Tools;189
7.3.1.7;7.7 Conclusions;190
7.3.1.8;References;191
7.4;Chapter 8;194
7.4.1;The Design of Partially Survivable Networks;194
7.4.1.1;8.1 Introduction;194
7.4.1.2;8.2 The Single Period Problem;196
7.4.1.2.1;8.2.1 Problem Formulation;196
7.4.1.2.2;8.2.2 Reduction to a Binary Knapsack Problem;197
7.4.1.3;8.3 The Multi-period Problem;199
7.4.1.3.1;8.3.1 Problem Description and Formulations;199
7.4.1.3.2;8.3.2 The Solution Procedure;201
7.4.1.3.2.1;8.3.2.1 Linear Programming Column Generation;201
7.4.1.3.2.2;8.3.2.2 Representing the Subproblem;202
7.4.1.3.2.3;8.3.2.3 Integer Programming and Column Generation;204
7.4.1.3.3;8.3.3 Computational Experiments;205
7.4.1.4;8.4 The Single Period Problem with Capacity Restrictions;206
7.4.1.4.1;8.4.1 A Partitioning Formulation;208
7.4.1.4.1.1;8.4.1.1 Representing the Subproblem;209
7.4.1.4.1.2;8.4.1.2 Reducing the Impact of Degeneracy;210
7.4.1.4.1.3;8.4.1.3 A Greedy Heuristic;211
7.4.1.4.2;8.4.2 Computational Experiments;211
7.4.1.5;8.5 Conclusions;211
7.4.1.6;References;213
8;Part III Optimization Problems in Ad Hoc Networks;214
8.1;Chapter 9;215
8.1.1;Routing in Mobile Ad Hoc Networks;215
8.1.1.1;9.1 Ad Hoc Networks;215
8.1.1.2;9.2 What is Routing?;216
8.1.1.3;9.3 Ad Hoc in the Link Layer;218
8.1.1.3.1;9.3.1 Ad Hoc Mode in Wi-Fi;219
8.1.1.3.2;9.3.2 Bluetooth Link Layer;221
8.1.1.4;9.4 Ad Hoc Routing Protocols;223
8.1.1.4.1;9.4.1 Introduction to Ad Hoc Routing Protocols;223
8.1.1.4.2;9.4.2 Reactive Protocols;224
8.1.1.4.2.1;9.4.2.1 AODV (Ad hoc On Demand Distance Vector);224
8.1.1.4.2.2;9.4.2.2 DSR (Dynamic Source Routing);225
8.1.1.4.3;9.4.3 Proactive Protocols;226
8.1.1.4.3.1;9.4.3.1 OLSR (Optimized Link State Routing Protocol);226
8.1.1.4.3.2;9.4.3.2 TBRPF (Topology Dissemination Based on Reverse-Path Forwarding);227
8.1.1.5;9.5 Quality of Service in Ad Hoc Networks;227
8.1.1.5.1;9.5.1 FQMM (Flexible QoS Model for MANETs);228
8.1.1.5.2;9.5.2 CEDAR (Core-Extraction Distributed Ad hoc Routing);229
8.1.1.5.3;9.5.3 TBP (Ticket-based Probing);229
8.1.1.5.4;9.5.4 INSIGNIA;230
8.1.1.5.5;9.5.5 SWAN (Stateless Wireless Ad hoc Network);230
8.1.1.5.6;9.5.6 QOLSR (Quality of Service for OLSR);231
8.1.1.6;9.6 Conclusion;232
8.1.1.7;References;232
8.2;Chapter 10;234
8.2.1;Compact Integer Programming Models for Power-optimal Trees in Ad HocWireless Networks;234
8.2.1.1;10.1 Introduction;234
8.2.1.1.1;10.1.1 Problem Overview;236
8.2.1.1.2;10.1.2 Outline of the Chapter;237
8.2.1.2;10.2 Problem Definitions;237
8.2.1.2.1;10.2.1 Notation and Assumptions;237
8.2.1.2.2;10.2.2 Minimum Energy Broadcast and Multicast;239
8.2.1.2.3;10.2.3 Range Assignment;240
8.2.1.2.4;10.2.4 Optimal Trees and Arborescence: Illustrative Example;241
8.2.1.3;10.3 Network Flow Models for MET;243
8.2.1.3.1;10.3.1 Models and Analysis;244
8.2.1.3.2;10.3.2 Models Based on Incremental Power;247
8.2.1.4;10.4 Network Flow Models for RAP;248
8.2.1.5;10.5 A Strong Multi-tree Model for RAP;249
8.2.1.5.1;10.5.1 The Model;249
8.2.1.5.2;10.5.2 LP Strength;251
8.2.1.6;10.6 Experimental Results;252
8.2.1.6.1;10.6.1 Results for MET;253
8.2.1.6.2;10.6.2 Results for RAP;254
8.2.1.7;10.7 Concluding Remarks;258
8.2.1.8;References;259
8.3;Chapter 11;262
8.3.1;Improving Network Connectivity in Ad Hoc Networks Using Particle Swarm Optimization and Agents;262
8.3.1.1;11.1 Introduction;262
8.3.1.2;11.2 Background;263
8.3.1.3;11.3 Proposed MANET Management System and Problem Description;265
8.3.1.3.1;11.3.1 Objectives and Evaluating Network Connectivity;265
8.3.1.3.2;11.3.2 Future User Location Prediction;266
8.3.1.3.3;11.3.3 Optimization Problem and Deployment Decision;267
8.3.1.4;11.4 Particle Swarm Optimization and Implementation;268
8.3.1.4.1;11.4.1 Particle Swarm Optimization (PSO);268
8.3.1.4.2;11.4.2 The Optimization Procedure;270
8.3.1.4.3;11.4.3 Semi-Intelligent Agent Node Behavior;272
8.3.1.5;11.5 Computational Experiments;273
8.3.1.5.1;11.5.1 Mobility Simulation Environment;274
8.3.1.5.2;11.5.2 The Effect of Number of Agents, Future Location Prediction, and Clustering;275
8.3.1.5.3;11.5.3 Comparative Performance of the PSO Algorithm;277
8.3.1.6;11.6 Conclusions;279
8.3.1.7;References;280
9;Part IV Optimization Problems in the Operation of Wireless Networks;283
9.1;Chapter 12;284
9.1.1;Simulation-Based Methods for Network Design;284
9.1.1.1;12.1 Introduction;285
9.1.1.2;12.2 Simulation Methodologies: a Taxonomy;287
9.1.1.3;12.3 Validating Discrete Event Simulations: the Random Number Seed and the Confidence Interval;289
9.1.1.4;12.4 Survey of Simulation forWireless Network Design;293
9.1.1.5;12.5 Case Studies;294
9.1.1.5.1;12.5.1 Traffic Modeling Application;295
9.1.1.5.2;12.5.2 Networkability and Impact Assessment Application;297
9.1.1.5.3;12.5.3 Network Operations and Capacity Planning;298
9.1.1.5.4;12.5.4 Network Research and Development;299
9.1.1.5.5;12.5.5 Network Emulation with Click;303
9.1.1.6;12.6 Conclusions;305
9.1.1.7;References;305
9.2;Chapter 13;307
9.2.1;Optimization of Wireless Broadband (WiMAX) Systems;307
9.2.1.1;13.1 Introduction;307
9.2.1.2;13.2 Brief Description ofWiMAX;309
9.2.1.2.1;13.2.1 WiMAX Physical Layer;309
9.2.1.2.2;13.2.2 WiMAX MAC Layer;312
9.2.1.3;13.3 Radio Resource Allocation Optimization;314
9.2.1.3.1;13.3.1 Modulation Coding Scheme Selection;315
9.2.1.3.2;13.3.2 MIMO Mode Selection;317
9.2.1.3.3;13.3.3 Power Control;319
9.2.1.3.3.1;13.3.3.1 Downlink Power Control;319
9.2.1.3.3.2;13.3.3.2 UL Power Control;319
9.2.1.3.3.3;13.3.3.3 Uplink Open Loop Power Control;320
9.2.1.3.4;13.3.4 Link Adaptation;321
9.2.1.4;13.4 Scheduling Optimization;322
9.2.1.4.1;13.4.1 Round Robin;322
9.2.1.4.2;13.4.2 Proportional Fair;323
9.2.1.4.3;13.4.3 Max System Throughput;324
9.2.1.4.4;13.4.4 WiMAX QoS Policy;325
9.2.1.4.4.1;13.4.4.1 Unsolicited Grant Service (UGS);325
9.2.1.4.4.2;13.4.4.2 Real-time Polling Services (rtPS);325
9.2.1.4.4.3;13.4.4.3 Extended Real-time Polling Services (ErtPS);326
9.2.1.4.4.4;13.4.4.4 Non Real-time Polling Services (nrtPS);326
9.2.1.4.4.5;13.4.4.5 Best Effort Service (BE);326
9.2.1.5;13.5 System Simulations;327
9.2.1.6;13.6 Conclusion;330
9.2.1.7;References;331
9.3;Chapter 14;332
9.3.1;Cross Layer Scheduling inWireless Networks;332
9.3.1.1;14.1 Introduction;332
9.3.1.2;14.2 Wireless Channel Capacity;333
9.3.1.2.1;14.2.1 Point-to-Point Capacity with Perfect Transmitter CSI;335
9.3.1.2.2;14.2.2 Multiuser Capacity with Perfect Transmitter CSI on the Uplink;337
9.3.1.3;14.3 A Framework for Cross Layer Scheduling;340
9.3.1.3.1;14.3.1 Opportunistic Scheduling;340
9.3.1.3.2;14.3.2 Energy Efficient Scheduling;341
9.3.1.3.3;14.3.3 System Model for Centralized Scheduling;341
9.3.1.4;14.4 Fair Scheduling;344
9.3.1.4.1;14.4.1 Notions of Fairness;345
9.3.1.4.2;14.4.2 Fair Scheduling Algorithms;345
9.3.1.5;14.5 Power Optimal Scheduling;346
9.3.1.5.1;14.5.1 Single User Scheduling;347
9.3.1.5.1.1;14.5.1.1 The Lagrangian Approach;348
9.3.1.5.1.2;14.5.1.2 Structural Properties of the Optimal Policy;349
9.3.1.5.1.3;14.5.1.3 Learning Algorithm for Scheduling;350
9.3.1.5.2;14.5.2 Multiuser Uplink Scheduling;353
9.3.1.5.2.1;14.5.2.1 Rate Determination Algorithm;354
9.3.1.5.2.2;14.5.2.2 User Selection Algorithm;355
9.3.1.5.2.3;14.5.2.3 Algorithm Analysis;355
9.3.1.6;14.6 Scheduling Schemes that Maximize Throughput;356
9.3.1.6.1;14.6.1 Throughput Optimal Scheduling;357
9.3.1.6.2;14.6.2 Delay Optimal Scheduling;358
9.3.1.7;Bibliographic Notes;360
9.3.1.8;References;361
9.4;Chapter 15;364
9.4.1;Major Trends in Cellular Networks and Corresponding Optimization Issues;364
9.4.1.1;15.1 Introduction;364
9.4.1.2;15.2 Current Situation;366
9.4.1.3;15.3 Overview of Solution Approaches;368
9.4.1.4;15.4 NewWireless Access Technologies;371
9.4.1.5;15.5 Backhauling and Transport;372
9.4.1.6;15.6 Power Efficiency;375
9.4.1.7;15.7 Leveraging Assets to Protect and Increase Revenues;376
9.4.1.8;15.8 Low Income Populations;377
9.4.1.8.1;15.8.1 Cost Reduction;378
9.4.1.8.2;15.8.2 Value;380
9.4.1.9;15.9 Conclusions;382
9.4.1.10;References;382