PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Delay-Aware Resource Control for Wireless Systems --- Large Deviation Theory, Stochastic Lyapunov Drift and Distributed Stochastic Learning

Ying Cui, Vincent K. N. Lau, Rui Wang, Huang Huang, Shunqing Zhang

arXiv:1110.4535v1cs.PF

TL;DR

Delay-aware wireless control must address the joint complexity of queueing state, channel state, and large action and state spaces. This paper surveys equivalent rate constraints, Lyapunov drift, and approximate MDPs with stochastic learning, covering single-hop allocation and multi-hop routing. In uplink OFDMA simulations, the MDP approach has better delay performance across all regimes, while the equivalent-rate approach is better than Lyapunov drift only in the large-delay regime.

  • Problem

    Delay-aware resource control is challenging because the system state and actions can be high-dimensional, while distributed decisions require locally measured CSI and QSI.

  • Method

    The paper provides a comprehensive survey of equivalent rate constraint, Lyapunov stability drift, and approximate MDP approaches using stochastic learning.

  • Results

    In uplink OFDMA simulations, the MDP approach has much better delay performance than the other schemes in all regimes; the equivalent-rate approach beats Lyapunov drift only in the large-delay regime.

  • Takeaways & Limitations

    The approaches differ in performance, complexity, and implementation issues, and the survey extends its discussion from single-hop allocation to delay-aware multi-hop routing.

Abstract

from arXiv · show

In this tutorial paper, a comprehensive survey is given on several major systematic approaches in dealing with delay-aware control problems, namely the equivalent rate constraint approach, the Lyapunov stability drift approach and the approximate Markov Decision Process (MDP) approach using stochastic learning. These approaches essentially embrace most of the existing literature regarding delay-aware resource control in wireless systems. They have their relative pros and cons in terms of performance, complexity and implementation issues. For each of the approaches, the problem setup, the general solution and the design methodology are discussed. Applications of these approaches to delay-aware resource allocation are illustrated with examples in single-hop wireless networks. Furthermore, recent results regarding delay-aware multi-hop routing designs in general multi-hop networks are elaborated. Finally, the delay performance of the various approaches are compared through simulations using an example of the uplink OFDMA systems.

I. INTRODUCTION

Delay-aware wireless resource control must jointly account for queueing delay, random arrivals, and PHY-layer performance, making policies adaptive to both CSI and QSI. The paper surveys three systematic approaches and their applications, limitations, and multi-hop extensions.

  • Motivation: Delay-aware cross-layer optimization must combine queueing delay metrics with conventional PHY-layer metrics under random bursty arrivals.This requires modeling both queue dynamics and PHY-layer dynamics.
  • Motivation: The system state includes CSI and QSI, so delay-optimal policies should adapt to both channel and queue conditions.Joint adaptation is required because delay and transmission performance depend on both state components.
  • Challenges: The control problem is difficult because objectives may lack closed-form relations to actions, optimization is often nonconvex, and state and action spaces grow exponentially.For N queues with finite buffer size NQ, the state space is described as O(N NQ).
  • Equivalent Rate Constraint Approach: The equivalent rate constraint approach uses large deviation theory to replace average delay constraints with average rate constraints, but its policies depend only on CSI.It is most suitable when buffers are rarely empty, corresponding to the large-delay regime.
  • Lyapunov Drift Approach: Lyapunov drift methods provide potentially simple throughput-optimal policies and can extend stability and performance optimization to multi-hop networks.Their delay performance may be weaker under moderate and light traffic loading.
  • Approximate MDP Approach: The approximate MDP approach targets delay-optimal control but faces infinite-horizon complexity, dimensionality limits, and signaling overhead under distributed implementation.The survey discusses stochastic-learning approximations, single-hop examples, and delay-aware multi-hop routing designs, then compares the approaches in uplink OFDMA simulations.

II. SYSTEM MODEL AND GENERAL CROSS-LAYER OPTIMIZATION FRAMEWORK

The paper models delay-aware control in general multi-hop wireless networks using channel, queue, arrival, delay, drop, throughput, and power metrics. It formulates three optimization categories and a unified Lagrangian framework over full or partial system states.

  • A. System Model: The network comprises nodes, directed transmission links, commodities, slotted time, and Markovian channel state information.Each link connects a transmit node to a receive node, while the system CSI is represented across all links.
  • B. Source Model: Each node maintains commodity-specific queues, with exogenous arrivals modeled as i.i.d. processes having average arrival rates.Queue dynamics account for offered transmission rates and actual arrivals, which may be smaller than offered service.
  • C. Control Policy and Resource Control Framework: The full system state combines CSI and QSI, and control policies map system states to resource-allocation actions such as power and subcarrier allocation.Policies may adapt to CSI only, QSI only, partial state, or the full state.
  • C. Control Policy and Resource Control Framework: Average delay is measured over data that reaches its destination, while data dropping is separately captured through the average drop rate.Finite buffers require dropping when overflow occurs, and the resulting delay relationships extend Little’s Law.
  • C. Control Policy and Resource Control Framework: Delay-aware control is divided into throughput maximization under delay, power, and drop constraints; delay minimization; and power minimization.The latter two categories assume given source arrival rates and impose the corresponding delay and drop constraints.
  • C. Control Policy and Resource Control Framework: The three optimization problems can be expressed in a unified Lagrangian form using weights or constraint-associated Lagrange multipliers.This creates a common formulation for the different delay-aware resource-control objectives.

D. Uplink OFDMA Systems

The uplink OFDMA example instantiates the general model with mobile stations communicating to one base station over frequency-selective fading subcarriers. It then illustrates equivalent rate constraints derived from effective bandwidth and effective capacity for delay guarantees.

  • D. Uplink OFDMA Systems: The OFDMA topology contains mobile stations communicating with one single-antenna base station, with uplink channels and data flows indexed consistently.The example uses the same index for link, node, and commodity for notational simplicity.
  • D. Uplink OFDMA Systems: The wideband channel is divided into orthogonal flat-fading subcarriers, with Markovian aggregate CSI and per-link queue and allocation states.Subcarrier fading variables are assumed i.i.d. across links and subcarriers.
  • D. Uplink OFDMA Systems: Each subcarrier’s received signal and rate depend on its allocation, channel gain, transmit symbol, noise, and allocated power.The link’s total rate is obtained by summing its subcarrier rates.
  • D. Uplink OFDMA Systems: A link control policy consists of power allocation and subcarrier allocation mappings from the system state to their respective action spaces.Binary allocation indicates whether a subcarrier is used by the link; with one carrier, allocation reduces to link selection.
  • III. Equivalent Rate Constraint Approach: Large deviation theory converts delay-tail requirements into equivalent rate constraints through effective bandwidth for arrivals and effective capacity for service.The delay violation probability is represented using a buffer-nonempty factor and a QoS exponent.
  • III. Equivalent Rate Constraint Approach: The equivalent rate approach offers potentially simple single-hop solutions and practical implementation, but relies on high traffic loading or the large-delay regime.For general delay regimes, delay-optimal policies should adapt to both CSI and QSI.

IV. STOCHASTIC LYNAPNOV STABILITY DRIFT APPROACH

The stochastic Lyapunov stability drift approach analyzes queueing systems through stochastic stability and develops control policies that can stabilize multi-hop wireless networks. Throughput optimality is characterized by stability regions and supported by several scheduling rules.

  • IV. STOCHASTIC LYAPUNOV STABILITY DRIFT APPROACH: Lyapunov drift techniques analyze control policies directly in the stochastic stability sense for queueing systems.The approach builds on discrete stochastic-process and Markov-chain theory.
  • IV. STOCHASTIC LYAPUNOV STABILITY DRIFT APPROACH: Lyapunov drift theory supports algorithms that stabilize multi-hop packet-radio networks with configurable link activation sets.Maximum weight matching and differential backlog scheduling are important components of dynamic queue control.
  • IV. STOCHASTIC LYAPUNOV STABILITY DRIFT APPROACH: The theory was extended to Lyapunov optimization, providing a broader framework for delay-aware control design.The paper introduces preliminaries and main results before presenting drift-based examples.
  • A. What is Queue Stability?: A queue is strongly stable when its time-average backlog is bounded, and the paper uses “stability” to mean strong stability.A network is strongly stable when all individual queues are strongly stable.
  • A. What is Queue Stability?: A throughput-optimal policy has a stability region containing that of every other feasible stabilizing policy and therefore equals the system stability region.Such policies stabilize the system whenever the average arrival-rate vector lies within the stability region.
  • A. What is Queue Stability?: Max Weight, EXP, and Log rules are identified as throughput-optimal policy classes, with proofs based on Lyapunov drift or related techniques.Max Weight and Log rules use Lyapunov-drift results, while EXP uses fluid limits with time-scale separation.

B. Main Results on Lyapunov Drift

Lyapunov drift theory provides stability conditions and motivates control algorithms that minimize drift bounds. Its extensions support throughput-optimality and utility, power, and delay tradeoffs under stated assumptions.

  • Lyapunov Drift: Lyapunov drift measures the expected one-slot change in a Lyapunov function and under negative-drift conditions establishes network stability with bounded average queue length.Theorem 1 supplies sufficient constants and drift conditions for stability.
  • Lyapunov Drift: Dynamic backpressure minimizes an upper bound on Lyapunov drift each slot and is throughput-optimal under resource-allocation constraints.For single-hop networks, the corresponding scheduling rule maximizes a queue-weighted service expression.
  • Lyapunov Optimization: Lyapunov optimization extends drift analysis by greedily minimizing a drift-based metric while maximizing a target utility over time.The framework also applies to minimizing convex objectives by reversing the utility formulation and inequalities.
  • Applications: EECA stabilizes queues while optimizing performance metrics and can approach minimum average power, achieving an [O(1/V ), O(V )] power-delay tradeoff.The parameter V adjusts the tradeoff, while the algorithm minimizes the drift-bound right-hand side over power allocations.
  • Lyapunov Optimization: When the utility gap is bounded, achieved utility can approach the target arbitrarily closely while the corresponding queue bound grows linearly in V.This establishes an explicit utility–queue tradeoff controlled by V.
  • Limitations: Theorem-based average-delay bounds are tight under sufficiently high traffic loading, but their tightness under moderate and light loading is unknown.End-to-end delay can also remain large even when average queue length is guaranteed to be bounded.

D. Methodology and Example

The Lyapunov drift approach converts stability and average-performance requirements into per-slot optimization problems, with uplink OFDMA examples illustrating adaptive cross-layer control. Its policies use CSI and QSI and are throughput-optimal in the stability sense, but stability alone may not ensure good small-delay performance.

  • Lyapunov drift procedure: The procedure chooses a Lyapunov function, computes drift or drift-minus-utility, and minimizes its upper bound in each time slot.The utility term is weighted by V when maximizing g(x).
  • Lyapunov drift procedure: Virtual cost queues transform other average performance constraints into queue-stability problems when needed.The approach can then apply Lyapunov drift analysis to the resulting queues.
  • Uplink OFDMA example: In uplink OFDMA, dynamic backpressure with subcarrier and average-power constraints follows from solving the corresponding per-slot optimization.Continuous relaxation and convex optimization yield subcarrier and power allocations.
  • Properties and limitations: The Lyapunov policies adapt to both CSI and QSI and are throughput-optimal in the stability sense.The paper distinguishes this stability guarantee from stronger delay guarantees.
  • Properties and limitations: Throughput optimality is only a weak form of delay performance, so the policies may perform poorly in the small-delay regime.The paper notes ongoing work on reducing delay in traditional dynamic backpressure algorithms for multi-hop networks.
  • MDP formulation: Under Markovian assumptions, delay-optimal resource control can be formulated as an infinite-horizon average-cost MDP over aggregated CSI and QSI.The action space includes resource allocation and routing actions, while average constraints can be incorporated through Lagrangian multipliers.

B. Optimal Solution of the Delay-Optimal MDP

The delay-optimal MDP has a Bellman-equation solution under unichain and ergodicity assumptions, but its global state space and centralized information requirements make direct computation and implementation difficult. The paper therefore introduces approximate MDP and stochastic-learning methods to reduce complexity and signaling overhead.

  • Optimal solution: Under unichain and ergodicity assumptions, relative value iteration and the Bellman equation can yield an optimal control policy.A policy attaining the Bellman minimum is optimal for the delay-optimal MDP.
  • Complexity and implementation: For N queues with buffer size NQ, the total number of queue-state configurations is (NQ +1)^N, which grows exponentially with network size.This state-space growth makes computing the potential function at every state difficult even for small networks.
  • Complexity and implementation: The optimal control is centralized and requires global CSI and QSI at each time slot, creating substantial signaling overhead.Distributed implementation instead seeks solutions based on local CSI and QSI.
  • Approximation strategy: Approximate MDP and stochastic learning are proposed to address the MDP’s complexity and distributed-implementation requirements.The paper develops feature-based approximations of potential functions and online stochastic-approximation procedures.
  • Stochastic approximation: The stochastic-approximation iterates converge almost surely to a compact connected internally chain transitive invariant set under stated regularity and boundedness conditions.The conditions include a Lipschitz map, martingale-difference noise, square-integrability, and almost-sure boundedness.

QSI Q1

The uplink OFDMA approximation example reduces computational complexity and signaling overhead relative to a brute-force centralized solution, but distributing Lagrange-multiplier terms remains costly.

  • Local information requirements: Each source node requires only local CSI, local QSI, and some potential functions of other links to compute its update.The local state is represented by channel information and queue information.
  • Complexity reduction: The feature-based approximation substantially reduces computational complexity and signaling overhead compared with the brute-force centralized solution.The reduction is demonstrated in the uplink OFDMA example.
  • Remaining overhead: Delivering the Lagrange-multiplier terms to all nodes remains computationally and communicationally heavy.The paper presents a second approximation approach to simplify complexity and signaling further.

D. Approach 2: Approximating Q-Factors

Approximating per-link Q-factors provides a second approximate-MDP route that supports distributed online learning and local action computation. It reduces complexity and signaling overhead, while trading off memory efficiency and, in some cases, action-computation simplicity against potential-function approximations.

  • Q-factor approximation: The approach approximates per-link Q-factors through a fixed-point equation and estimates them using an online Q-learning algorithm.Each Q-factor depends on a local state and local action, including resource-allocation choices.
  • Convergence: Per-link Q-factor updates converge almost surely under the stated stochastic-approximation conditions.The limiting per-link Q-factor satisfies the corresponding steady-state relation.
  • Uplink OFDMA implementation: In uplink OFDMA, subcarrier allocation is distributed through bids, assigning each subcarrier to the user with the minimum bid.Power allocation is then calculated locally at each user.
  • Uplink OFDMA implementation: Q-factor updates require only local information at each user and introduce no signaling overhead.The online update uses real-time local state observations.
  • Comparison: Both approximate-MDP approaches reduce complexity and signaling overhead, but their advantages differ between potential-function and Q-factor approximations.Potential functions generally use fewer dimensions, whereas Q-factor updates can be fully local.
  • Comparison: Potential-function approximations may require information exchange and can make action computation more complicated than Q-factor approximations.Q-factors depend on both system state and control action, increasing their dimensionality relative to potential functions.
  • Scope boundary: Extending approximate MDP and stochastic learning to multi-hop networks remains difficult because queue interactions create a much larger state space.The paper identifies further investigation of approximations and convergence proofs as necessary.

VI. DELAY-AWARE ROUTING IN MULTI-HOP WIRELESS NETWORKS

The survey examines delay-aware routing in multi-hop wireless networks, emphasizing that the Lyapunov drift approach is readily applied to coupled queue dynamics and adaptive control. It reviews traditional DBP routing and three classes of delay-reduction enhancements: shortest-path bias, modified queueing disciplines, and receiver diversity.

  • Lyapunov drift extends readily to multi-hop networks because it derives dynamic algorithms adaptive to CSI and QSI.
  • A. Traditional DBP Routing: Traditional DBP can incur excessive delay by exploring unnecessarily long routes under light or moderate loads.A single packet may take a random or periodic walk, producing infinite end-to-end delay despite zero average arrival rate.
  • A. Traditional DBP Routing: Traditional DBP also maintains large, distance-dependent queues to create differential-backlog gradients for data flows.In an N-hop tandem network, the informal construction Q_n = nϵ illustrates backlog growth upstream from the destination.
  • These enhancements aim to preserve throughput optimality while reducing delay and adapting routing or scheduling to random transmission outcomes.
  • Enhanced DBP designs reduce delay through shortest-path routing, modified queueing disciplines, and receiver diversity over unreliable channels.

B. Delay Reduction in DBP Routing by Shortest Path

Shortest-path concepts are incorporated into DBP routing to reduce excessive route exploration and end-to-end delay. The resulting enhanced algorithms retain throughput optimality while improving delay performance.

  • Traditional DBP’s extensive route exploration can create poor end-to-end delay, motivating shortest-path restrictions or bias.
  • Shortest-path bias adds a destination-directed term to link backpressure, encouraging shorter routes during light or moderate loading.
  • The shortest-path bias DBP algorithm remains throughput-optimal and has better simulated delay performance than traditional DBP.
  • Min-resource DBP Routing: Min-resource DBP minimizes total link rate, thereby preferring shorter paths, and introduces parameter V into the backpressure.
  • Min-resource DBP Routing: O(1/V ) optimality gap; larger V yields smaller delay but slower convergence, while smaller V yields larger delay and faster convergence.
  • Joint Traffic-Splitting and Shortest-Path-Aided DBP: Joint traffic-splitting and shortest-path-aided DBP is throughput-optimal and solves average path-length minimization as V →∞.

C. Delay Reduction in DBP Routing by Modified Queueing Discipline

Modified queueing disciplines and receiver-diversity routing reduce DBP delay while targeting throughput preservation. The survey also compares the three delay-aware resource-control approaches in uplink OFDMA.

  • Traditional DBP’s large queues support flow gradients but lead to poor delay, motivating queueing-discipline modifications.
  • Modified Queueing Discipline: FQLA achieves [O(1/V ), O(log2(V ))] utility-delay tradeoff versus [O(1/V ), O(V )] for traditional DBP.
  • Modified Queueing Discipline: FQLA subtracts an attractor to form a virtual backlog, allows packet dropping under conditions, and remains throughput-optimal.
  • Modified Queueing Discipline: LIFO DBP greatly reduces average delay for most packets, while an O(1/V log V ) arrival fraction can experience large delay and be dropped.
  • Receiver Diversity: Receiver-diversity methods route packets after transmission toward successful receivers; ORCD is throughput-optimal, whereas ExOR is not.

B. Comparison on Distributed Implementation

The three approaches differ in information requirements, computational complexity, and distributed implementability. Simulations show that approximate MDP with stochastic learning approaches brute-force MDP performance while reducing complexity.

  • Distributed Implementation: Equivalent-rate optimization can use decomposition and distributed auctions, with power allocation computed locally from auction results and local CSI.
  • Distributed Implementation: The Lyapunov M-LWDF solution requires only local transmitter state information, supporting distributed implementation in single-hop settings.
  • Distributed Implementation: Multi-hop distributed Lyapunov control requires neighboring-node QSI, creating additional signaling overhead.
  • Distributed Implementation: MDP distributed implementation is harder because potential functions and transition kernels are generally non-decomposable.
  • Comparison of Performance: Approximate MDP with stochastic learning reduces complexity and achieves near-optimal performance, with simulated convergence described as quite fast.
  • Comparison of Performance: The equivalent-rate approach is simplest; Lyapunov drift lies between it and MDP in delay and complexity, while MDP performs best across regimes.
  • Comparison of Performance: 5.9 average delay at the 500-th scheduling slot, much smaller than the other baselines, under the stated distributed-learning experiment.

APPENDIX A: PROOF OF LEMMA 3

The appendix proves convergence properties for the asynchronous learning algorithm by combining martingale arguments, boundedness, diminishing updates, and fixed-point analysis.

  • Boundedness: The parameter vector {eV_t} remains bounded almost surely during the algorithm’s iterations.This boundedness supports the subsequent convergence analysis of the learning procedure.
  • Martingale analysis: The asynchronous learning updates are analyzed using martingale sequences and unbiased, uncorrelated estimation noise.The proof establishes E[δZ_t|F_t−1] = 0 and identifies Y_t as an unbiased estimate of q_t.
  • Update comparison: The proof relates asynchronous and synchronous updates through matrix-sequence properties and bounds involving the maximum and minimum elements of q_l.The argument uses conditions on {A_l} and {B_l}, together with constants C1 and C2.
  • Vanishing error: Because δ_t = O(ϵ_t), the sequence q_t converges to zero as t →∞.This diminishing-error result is used to establish convergence of the parameter updates.
  • Fixed-point convergence: The update sequence {eV_l} converges to eV_∞, which satisfies a fixed-point relation.The appendix states that the convergence follows after q_t tends to zero.
Loading 1110.4535v1…