Stochastic Schemes for Dynamic Network Resource Allocation

Abstract

Wireless networks and power distribution grids are experiencing increasing demands on their efficiency and reliability. Judicious methods for allocating scarce resources such as power and bandwidth are of paramount importance. As a result, nonlinear optimization and signal processing tools have been incorporated into the design of contemporary networks. This thesis develops schemes for efficient resource allocation (RA) in such dynamic networks, with an emphasis in stochasticity, which is accounted for in the problem formulation as well as in the algorithms and schemes to solve those problems. Stochastic optimization and decomposition techniques are investigated to develop low-complexity algorithms with specific applications in cross-layer design of wireless communications, cognitive radio (CR) networks and smart power distribution systems. The costs and constraints on the availability of network resources, together with diverse quality of service (QoS) requirements, render network design, management and operation challenging tasks. Moreover, when the available network state information (NSI) is time-varying, nodes must be capable of adapting their operation parameters to the those variations. While traditional schemes only exploited local information, or did not take into account uncertainty in system parameters and future events, the methodology proposed in this thesis aims at designing schemes through the solution of rigorously formulated mathematical problems involving random variables. The three basic elements when formulating an optimization problem are the design variables (mainly corresponding to resources to be allocated, and sensing and control information), system and QoS constraints, and the objective function (usually formulated as weighted sums of utility functions). Equilibrium between problem tractability and realistic modeling is also sought. Previous works on dynamic RA for wireless networks that take into account cross-layer information rely on convex optimization and dual decomposition techniques, while exploiting instantaneous fading; whereas others build upon dynamic backpressure policies based on adaptive control tools and aim to stabilize queues of the network. Based on such a background, our first contribution is the design of a stochastic scheme that uses instantaneous fading and queue length information to optimally allocate resources at the transport, link and physical layers. Theoretical results allow to establish links between the transmit queue lengths and Lagrange multipliers; these links can be used to estimate and control queuing delays and establish delay priorities among users. Experimental results confirm that RA feasibility and optimality are preserved when the scheme employs window averages of multipliers and queue lengths. In the last years, CRs have emerged as the next-generation solution to the perceived spectrum underutilization, thanks to their capability to limit the interference inflicted to coexisting primary users (PUs). To do so CRs must sense the spectrum and dynamically adapt their transmission parameters according to the available resources and sensed information. Existing works limit CR-inflicted interference either through short- and long-term transmit-power constraints; or, by controlling the probability of interfering with PU transmissions. As the sensed information may be imperfect (due to errors or quantization) and get outdated, implementation of stochastic RA algorithms offers the possibility of adapting the operation of the network to varying channel conditions and PU behaviour. Motivated by these facts, we develop stochastic RA algorithms that optimize sum-rate performance of a CR network, limit the probability of interfering with PUs, and jointly account for outdated and noisy NSI. Additional works in this context point out the tradeoff between the sensing and RA and deal with their joint design. Hence, we also develop a jointly optimal sensing and RA algorithm that additionally takes into account the temporal correlation of the primary NSI and the sensing cost by means of stochastic dynamic programming (SDP). The proposed schemes obtain optimal performance, account for imperfections in the acquired state information, and are able to adapt to varying channel conditions. A two-step strategy significantly reduces the computational solution complexity without loss of optimality, and its formulation allows developing adaptive stochastic schemes. Numerical experiments confirm a significant performance improvement with respect to low-complexity alternatives and allow to trace sensing-decision maps. The last part of the thesis addresses the design of RA algorithms for smart grids, where increasing penetration of renewable energy sources (RESs) pose new challenges related to variability and uncertainty. Previous works formulate security-constrained and risk-limiting dispatch schemes based on stochastic optimization tools, whereas recent works demonstrate that power inverters can be controlled to effect voltage regulation. More recent works deal with smart grid operation schemes in different timescales, or capitalize on stochastic approximation to limit the magnitude of sporadic component overloads. Based on this background, we consider joint dispatch of slowand fast- timescale distribution grid resources under average or probabilistic constraints over fasttimescale decisions. Using an approximate grid model, the expected network operation cost is minimized under inverter and voltage constraints, and the two-stage dispatch is formulated as a stochastic saddle-point problem. The developed dispatch algorithms account for conventional and alternative energy resources at different timescales, which are coupled across time in a stochastic manner. Average and probabilistic voltage constraints are tackled using dual decomposition and convex optimization. The resulting schemes rely on random samples of stochastic generation and demand, and converge to optimal dispatch decisions. The experimental results throughout the thesis confirm that the proposed stochastic RA schemes achieve optimal or near-optimal performance, are robust against non-stationary NSI, fulfill instantaneous constraints and asymptotically fulfill long-term constraints. Average power consumption constraints and their treatment by means of dual stochastic gradients are common ground for the cross-layer and CRs designs undertaken. A similar strategy is followed to deal with (nonconvex) probability of interference constraints in CRs and voltage probabilistic constraints in smart grids with manageable complexity.