Optimization of ARQ Protocols in Interference Networks with QoS Constraints

Marco Levorato, Daniel O'Neill, Andrea Goldsmith, Urbashi MitraICC 2011 · DOI

TL;DR

This paper introduces a novel framework for optimizing Automatic Retransmission reQuest (ARQ) protocols in wireless networks with multiple interfering sources. By formulating the problem as a constrained Markov Decision Process (MDP) and solving it using Linear Fractional Programming, the authors provide a method to find optimal transmission strategies that balance throughput, energy efficiency, and Quality of Service (QoS) constraints like packet delay and failure probability. This work is crucial for designing more efficient and reliable wireless communication systems.

What Problem Does This Paper Address?

Wireless networks are inherently prone to errors due to fading, interference, and other channel impairments. Automatic Retransmission reQuest (ARQ) is a common technique to combat these errors by retransmitting packets that fail to be delivered. However, in modern wireless networks, multiple users often share the same resources, leading to interference. This interference couples the behavior of individual ARQ protocols, making it challenging to optimize them independently.

The core problem this paper tackles is how to design optimal ARQ strategies for multiple, mutually interfering sources that not only aim to improve packet delivery but also adhere to strict Quality of Service (QoS) requirements. These QoS constraints can include ensuring a minimum throughput, limiting packet delay, and minimizing the probability of packet loss. Traditional ARQ optimization often focuses on single links or simpler scenarios, failing to capture the complex interdependencies introduced by interference and multiple QoS objectives.

Methods

The authors propose a comprehensive framework to address this challenge:

  • Stochastic Modeling: The network is modeled as a collection of interdependent stochastic processes, representing the state of each source's buffer (queue length and service time) and the outcomes of transmissions (success/failure).
  • Markov Decision Process (MDP): An infinite-horizon, undiscounted MDP is formulated to optimize the transmission and interference strategies of the sources. The state space captures the queue length and service time for each source, while actions involve transmission or dropping packets.
  • Linear Fractional Programming (LFP): The key innovation lies in solving the constrained MDP using LFP. This approach is particularly well-suited because the performance metrics (like energy per unit of throughput, or success probability) are naturally expressed as ratios of time-averaged cost functions. LFP allows for the direct optimization of these ratios while satisfying linear constraints on other performance metrics.
  • Renewal Interpretation: The paper also provides a renewal interpretation of some performance metrics, which helps in understanding the relationship between steady-state probabilities and average occurrences of events, further solidifying the LFP approach.

What's novel here is the formalization of an MDP problem with objective/constraint functions that are ratios of time-averaged costs, and solving it via LFP. This allows for a unified approach to optimize complex trade-offs between various performance metrics under QoS constraints in an interference-rich environment.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and numerical simulations based on defined network parameters rather than real-world datasets.

Key Insights and Ideas

  • Ratios as Performance Metrics: Expressing performance metrics as ratios of time-averaged costs (e.g., energy/throughput, delay/throughput) is a powerful way to capture efficiency and trade-offs. This is a core insight that enables the LFP formulation.
  • Interference Coupling: The paper highlights how interference significantly couples the behavior of ARQ protocols. The optimal strategy for one source is inherently dependent on the actions of others, necessitating a joint optimization approach.
  • QoS Dictates Strategy: Stringent QoS constraints, particularly for throughput, can force the system to move from time-splitting (one source at a time) to simultaneous transmission, even though the latter is less energy-efficient. This demonstrates how QoS requirements can override energy efficiency goals.
  • State-Dependent Strategies: The optimal transmission probabilities are shown to be highly dependent on the network state (e.g., queue lengths, service times). For instance, a strategy might prioritize transmitting a packet if its service time is longer than a competitor's to avoid discarding it.
  • Trade-offs are Explicit: The LFP framework explicitly visualizes and quantifies the trade-offs between different objectives (e.g., aggregate energy efficiency vs. individual source throughput).

Key Results

The numerical results illustrate several key findings:

  • Energy vs. Throughput: The paper shows that while simultaneous transmissions can increase aggregate throughput, they often come at the cost of lower energy efficiency (higher energy per unit of throughput).
  • Impact of Constraints: Increasing throughput constraints forces the system to schedule more simultaneous transmissions, leading to a worse energy/throughput balance. Conversely, relaxing delay constraints can allow for more energy-efficient strategies.
  • Symmetric vs. Asymmetric Behavior: In scenarios with asymmetric constraints, the strategy can lead to one source being prioritized or scheduled differently based on its QoS requirements. For example, a source with a relaxed constraint might be scheduled more often in interference-free slots to improve its efficiency.
  • State Space Partitioning: The optimal strategies partition the state space, assigning specific transmission probabilities to different states to meet the QoS objectives. For example, transmission probability can cluster in states where one source's packet service time is longer than another's.

Limitations and Future Work

  • Model Simplifications: The model assumes a single-hop network and a finite buffer size. While the framework can be extended, these simplifications limit direct applicability to more complex multi-hop or bufferless scenarios.
  • Memoryless ARQ: The paper primarily considers memoryless ARQ, where prior transmissions are discarded. More advanced hybrid ARQ (HARQ) schemes, which combine information from previous transmissions, could lead to a larger state space and more complex optimization.
  • Homogeneous Sources: The initial analysis often assumes homogeneous sources, though the framework can handle heterogeneous QoS requirements.
  • Future Work: The authors suggest exploring more complex ARQ protocols (like type-II HARQ), incorporating power control, and extending the framework to multi-hop networks. Investigating the impact of different channel models and exploring adaptive strategies based on real-time channel conditions are also promising directions.

Summary updated

BibTeX
@inproceedings{levorato2011optimization,
  author = {Marco Levorato and Daniel O'Neill and Andrea Goldsmith and Urbashi Mitra},
  title = {{Optimization of ARQ Protocols in Interference Networks with QoS Constraints}},
  booktitle = {ICC},
  year = {2011},
  doi = {10.1109/icc.2011.5963420},
}
Figure