Delay Optimal Cross-Layer Scheduling Over Markov Channels with Power Constraint

Wenhao Zhan, Haoyue Tang, Jintao Wang

Abstract

We consider a scenario where a power-constrained transmitter delivers randomly arriving packets to a destination over a Markov time-varying channel. The transmitter adapts its transmission power to each channel state to guarantee successful delivery. To minimize the expected average transmission delay, we formulate the problem as a Constrained Markov Decision Process (CMDP). We reveal a queue-length threshold structure for the optimal policy: the transmitter sends packets if and only if the queue length surpasses a specific threshold. The optimal cross-layer scheduling strategy is obtained through Linear Programming (LP). Numerical results validate the performance of the proposed strategy and illustrate a clear delay-power tradeoff.

Introduction

In the rapidly expanding Internet of Things (IoT), communication devices must deliver high-reliability, low-latency data while operating on severely limited power budgets. Achieving this requires "cross-layer control"—strategies that simultaneously consider physical channel quality and network queue length to make transmission decisions.

While previous research identified optimal delay-minimizing policies, many relied on the simplifying assumption that wireless channel fading is an independent and identically distributed (i.i.d.) process. In reality, wireless channels possess memory; a "good" state often persists, as does a "bad" one. This paper addresses this gap by modeling the time-varying wireless link as an ergodic Markov chain and seeking the optimal scheduling policy to minimize average queueing delay under a strict average power constraint.

Methodology

The system is modeled as a discrete-time point-to-point communication link. The scheduling problem is formulated as a Constrained Markov Decision Process (CMDP), where the state is defined by the current queue length and the Markov channel state.

Key methodological contributions include:

  1. Structural Proof: Through Bellman equation analysis, the authors prove that the optimal policy follows a queue-length threshold structure. Due to the power constraint, the absolute optimal policy is a randomized mixture of two deterministic threshold policies.
  2. Linear Programming (LP) Transformation: To solve the CMDP efficiently, the authors introduce variables representing the steady-state probabilities of queue and channel states. This transforms the complex CMDP into an equivalent LP problem that can be solved to find exact optimal transmission probabilities.

Optimal Policy Structure

The optimal strategy is characterized by a "wait and see" approach. It dictates that for any given channel state, the transmitter should remain idle unless the queue length surpasses a specific threshold. This allows the system to wait for better channel conditions (requiring less power) to save energy. However, as the queue grows, the urgency of reducing delay eventually overrides power-saving goals, triggering a transmission.

Figure 4: Visualization of the optimal transmission probabilities across different power constraints (E). The plots illustrate the threshold structure where transmission becomes more likely as queue length increases.

As shown in the figure above, the policy naturally adapts to the available power budget $\mathcal{E}$. At lower power levels (e.g., $\mathcal{E}=0.8$), the thresholds are higher, and the policy often employs randomized transmission probabilities (like $f_{3,1} = 0.5763$) at the threshold to precisely meet the power constraint.

Performance and Tradeoffs

Numerical simulations using a 3-state Markov channel over $10^6$ time slots demonstrate the effectiveness of the LP-based optimal policy. It was compared against a "greedy" baseline that transmits whenever sufficient power is available.

Figure 3: Transmission delay as a function of power constraint. The optimal policy (theoretic and simulation) significantly outperforms the greedy approach, especially in low-power regimes.

Key findings include:

  • Superiority in Low-Power Regimes: Under strict power constraints (e.g., $\mathcal{E}$ between 0.8 and 1.1), the optimal policy drastically reduces average transmission delay compared to the greedy approach.
  • Piecewise Linear Tradeoffs: The relationship between available power and minimum delay consists of distinct linear segments, each corresponding to a specific threshold value in the underlying policy.
  • Convergence at High Power: As the power budget increases, the transmission threshold drops. When power is abundant, the optimal policy's performance converges with the greedy policy.

Conclusion and Future Work

This work provides a robust framework for delay-optimal scheduling over realistic Markov channels. While currently limited to point-to-point links with large buffers, the authors plan to extend this framework to multi-user environments and incorporate additional constraints, such as strict bandwidth limits, to better serve complex IoT network scenarios.

Summary updated

Abstract

We consider a scenario where a power constrained transmitter delivers randomly arriving packets to the destination over Markov time-varying channel and adapts different transmission power to each channel state in order to guarantee successful transmission. To minimize the expected average transmission delay of each packet, we formulate the problem into a constrained Markov decision process (CMDP). We reveal the queue-length threshold structure of the optimal policy, i.e., the transmitter sends packets if and only if the queue length surpasses a threshold and obtain the optimal cross-layer scheduling strategy through linear programming (LP). Numerical results validate the performance of the proposed strategy and illustrate a delay-power tradeoff in such scenario.
BibTeX
@inproceedings{zhan2020delay,
  author = {Wenhao Zhan and Haoyue Tang and Jintao Wang},
  title = {{Delay Optimal Cross-Layer Scheduling Over Markov Channels with Power Constraint}},
  booktitle = {BMSB},
  year = {2020},
  url = {https://openreview.net/forum?id=PqjoQDCRiNp},
}
Figure