Delay Analysis of Max-Weight Queue Algorithm for Time-varying Wireless Adhoc Networks - Control Theoretical Approach
For wireless network designers, this work addresses the realistic scenario of time-varying conditions that break the instantaneous optimality assumption, providing both theoretical delay bounds and a practical algorithm.
This paper analyzes the delay performance of max-weight queue (MWQ) control in time-varying wireless ad hoc networks where channel and queue states change as fast as algorithm iterations. It derives a closed-form delay bound and proposes a modified MWQ algorithm with compensation that converges to the optimal policy under mild conditions.
Max weighted queue (MWQ) control policy is a widely used cross-layer control policy that achieves queue stability and a reasonable delay performance. In most of the existing literature, it is assumed that optimal MWQ policy can be obtained instantaneously at every time slot. However, this assumption may be unrealistic in time varying wireless systems, especially when there is no closed-form MWQ solution and iterative algorithms have to be applied to obtain the optimal solution. This paper investigates the convergence behavior and the queue delay performance of the conventional MWQ iterations in which the channel state information (CSI) and queue state information (QSI) are changing in a similar timescale as the algorithm iterations. Our results are established by studying the stochastic stability of an equivalent virtual stochastic dynamic system (VSDS), and an extended Foster-Lyapunov criteria is applied for the stability analysis. We derive a closed form delay bound of the wireless network in terms of the CSI fading rate and the sensitivity of MWQ policy over CSI and QSI. Based on the equivalent VSDS, we propose a novel MWQ iterative algorithm with compensation to improve the tracking performance. We demonstrate that under some mild conditions, the proposed modified MWQ algorithm converges to the optimal MWQ control despite the time-varying CSI and QSI.