Fundamentals of Resource Allocation in Wireless Networks (eBook)

Theory and Algorithms

Slawomir Stanczak, Marcin Wiczanowski, Holger Boche (Autoren)

eBook Download: PDF

2009 | 2nd ed. 2008
I, 320 Seiten
Springer Berlin (Verlag)
978-3-540-79386-1 (ISBN)

Infos

The purpose of this book is to provide tools for a better understanding of the fundamental tradeo?s and interdependencies in wireless networks, with the goal of designing resource allocation strategies that exploit these int- dependencies to achieve signi?cant performance gains. Two facts prompted us to write it: First, future wireless applications will require a fundamental understanding of the design principles and control mechanisms in wireless networks. Second, the complexity of the network problems simply precludes the use of engineering common sense alone to identify good solutions, and so mathematics becomes the key avenue to cope with central technical problems in the design of wireless networks. In this book, two ?elds of mathematics play a central role: Perron-Frobenius theory for non-negative matrices and optimization theory. This book is a revised and expanded version of the research monograph 'Resource Allocation in Wireless Networks' that was published as Lecture Notes in Computer Sciences (LNCS 4000) in 2006. Although the general structure has remained unchanged to a large extent, the book contains - merous additional results and more detailed discussion. For instance, there is a more extensive treatment of general nonnegative matrices and interf- ence functions that are described by an axiomatic model. Additional material on max-min fairness, proportional fairness, utility-based power control with QoS (quality of service) support and stochastic power control has been added.

Inhalt

Preface 8
Contents 12
List of Figures 16
List of Symbols 21
Part I Mathematical Framework 26
On the Perron Root of Irreducible Matrices 27
Some Basic Definitions 27
Some Bounds on the Perron Root and their Applications 28
Concavity of the Perron Root on Some Subsets of Irreducible Matrices 35
Kullback--Leibler Divergence Characterization 38
A Rate Function Representation for Large Deviations of Finite Dimensional Markov Chains 39
Some Extended Perron Root Characterizations 44
Collatz--Wielandt-Type Characterization of the Perron Root 46
Convexity of the Perron Root 49
Some Definitions 50
Sufficient Conditions 52
Convexity of the Feasibility Set 54
Necessary Conditions 56
Special Classes of Matrices 58
Symmetric Matrices 59
Symmetric Positive Semidefinite Matrices 60
The Perron Root under the Linear Mapping 61
Some Bounds 63
Disproof of the Conjecture 66
The Perron Root under Exponential Mapping 69
A Necessary and Sufficient Condition on Strict Convexity of the Feasibility Set 69
Graph-theoretic Interpretation 72
Generalizations to Arbitrary Nonnegative Matrices 75
Log-Convexity of the Spectral Radius 76
Characterization of the Spectral Radius 76
Existence of Positive Eigenvectors 80
Collatz--Wielandt-Type Characterization of the Spectral Radius 81
Bibliographical Notes 83
On the Positive Solution to a Linear System with Nonnegative Coefficients 85
Basic Concepts and Definitions 85
Feasibility Sets 87
Convexity Results 90
Log-Convexity of the Positive Solution 91
Convexity of the Feasibility Set 93
Strict Log-Convexity 94
Strict Convexity of the Feasibility Sets 99
The Linear Case 100
Part II Principles of Resource Allocation in Wireless Networks 103
Introduction 104
Network Model 107
Basic Definitions 107
Medium Access Control 109
Wireless Communication Channel 112
Signal-to-Interference Ratio 116
Different Receiver Structures 120
Power Constraints 126
Data Rate Model 129
Examples 133
Resource Allocation Problem in Communications Networks 140
End-to-End Rate Control in Wired Networks 140
Fairness Criteria 141
Algorithms 145
Problem Formulation for Wireless Networks 146
Joint Power Control and Link Scheduling 147
Feasible Rate Region 150
End-to-End Window-Based Rate Control 153
MAC Layer Fair Rate Control 155
Utility-Based Power Control 157
Efficiency-Fairness Trade-Off 162
Kuhn--Tucker Conditions 167
Interpretation in the QoS Domain 171
Remarks on Joint Power Control and Link Scheduling 181
Optimal Joint Power Control and Link Scheduling 181
High SIR Regime 184
Low SIR Regime 184
Wireless Links with Self-Interference 188
QoS-based Power Control 189
Some Definitions 190
Axiomatic Interference Functions 195
QoS-Based Power Control Algorithms 201
Max-Min SIR Balancing Power Control 212
Some Preliminary Observations 213
Characterization under Sum Power Constraints 216
General Power Constraints 220
Some Consequences and Applications 225
Utility-based Power Control with QoS Support 231
Hard QoS Support 233
Soft QoS Support 234
Utility-Based Joint Power and Receiver Control 243
Problem Statement 243
Perfect Synchronization 245
Decentralized Alternating Computation 247
Max-Min SIR Balancing 248
Additional Results for a Noiseless Case 249
The Efficiency--Fairness Trade-off 250
Existence and Uniqueness of Log-SIR Fair Power Allocation 262
Proofs 267
Part III Algorithms 279
Power Control Algorithms 280
Introduction 280
Some Basic Definitions 281
Convex Statement of the Problem 283
Strong Convexity Conditions 285
Gradient Projection Algorithm 289
Global Convergence 289
Rate of Convergence 292
Diagonal Scaling 294
Projection on a Closed Convex Set 294
Distributed Implementation 295
Local and Global Parts of the Gradient Vector 295
Adjoint Network 297
Distributed Handshake Protocol 301
Some Comparative Remarks 302
Noisy Measurements 304
Incorporation of QoS Requirements 307
Hard QoS Support 308
Soft QoS Support 319
Primal-Dual Algorithms 321
Improving Efficiency by Primal-Dual Methods 323
Generalized Lagrangian 330
Primal-Dual Algorithms 338
Decentralized Implementation 341
Min-max Optimization Framework 345
Simulation Results 361
Part IV Appendices 364
Some Concepts and Results from Matrix Analysis 365
Vectors and Vector Norms 365
Matrices and Matrix Norms 367
Square Matrices and Eigenvalues 369
Matrix Spectrum, Spectral Radius and Neumann Series 371
Orthogonal, Symmetric and Positive Semidefinite Matrices 373
Perron--Frobenius Theory 375
Perron--Frobenius Theorem for Irreducible Matrices 376
Perron--Frobenius Theorem for Primitive Matrices 380
Some Extensions to Reducible Matrices 381
The Existence of a Positive Solution p to(I-X)p=b 389
Some Concepts and Results from Convex Analysis 395
Sets and Functions 395
Convex Sets and Functions 401
Strong Convexity 402
Majorization and Schur-Convexity 404
Log-Convex Functions 404
Inverse Functions of Monotonic Log-Convex Functions 406
Basics of Optimization Theory 407
Characterization of Numerical Convergence 408
Convergence of Gradient Projection Algorithms 410
Basics of Lagrangian Optimization Theory 413
Saddle Points, Saddle Functions, Min-Max Functions 416
References 419
Index 429

Produkt-Details

• Erscheint lt. Verlag: 29.6.2009
• Reihe/Serie: Foundations in Signal Processing, Communications and Networking
• Zusatzinfo: I, 320 p. 30 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Nachrichtentechnik
• Schlagworte: Algebra • algorithm • algorithms • Calculus • Communication • communication complexity • Complexity • Computational Discrete Mathematics • Convex Analysis • Convex Optimization • Discrete Mathematics • distributed algorithms • Distributed Networks • Gradient Projection Algorithm • Internet • linear algebra • Link Scheduling • Model • Multimedia • Perron-Frobenius theory • Power Control Algorithm • Q • Wireless Network
• ISBN-10: 3-540-79386-0 / 3540793860
• ISBN-13: 978-3-540-79386-1 / 9783540793861