Throughput and delay optimization in interference-limited multihop networks

Ahmed Bader, Eylem Ekici2006 · DOI

TL;DR

This paper tackles the challenge of optimizing performance in wireless multihop networks, where interference significantly degrades throughput and increases delay. The authors propose a novel approach to manage packet injection at the source, introducing strategic waiting times and coordinating transmissions to strike a balance between high throughput and low delay, offering practical guidelines for network design.

What Problem Does This Paper Address?

In wireless multihop networks, multiple devices share the same radio channel, leading to significant interference. This interference makes it difficult to predict network performance, especially in fading environments. The core problem this paper addresses is how to improve both the rate at which data is successfully transmitted (throughput) and the time it takes for data to reach its destination (delay), despite this inherent interference. Existing approaches often focus on one metric at the expense of the other. This work aims to find a sweet spot by intelligently controlling when and how packets are sent into the network from their sources.

Methods

The paper introduces a framework for analyzing and optimizing packet flow in interference-limited multihop networks. Key methods include:

  • Non-linear Probabilistic Hopping Models: They develop models to describe how packets move through the network, considering the probabilistic nature of wireless links and interference. These models are initially developed for linear networks (1D) and then extended to a more general planar (2D) scenario.
  • Joint Optimization of Throughput (THR) and Head-of-Queue Delay (HQD): Instead of optimizing for one metric alone, the paper focuses on finding a Pareto optimal solution that balances both THR and HQD. This is achieved by introducing optimal waiting times for packets at the source queue before they are injected into the network.
  • Recursive Optimization: For linear networks, the paper uses a recursive approach to calculate optimal waiting times for successive packets. This means the optimal waiting time for one packet depends on the decisions made for the preceding packets.
  • Interference Management Strategies: The authors explore strategies for coordinating packet injections across multiple sources (flows) to minimize inter-flow interference. This includes determining optimal relative timings and the number of flows.
  • Link Model: The analysis relies on a probabilistic link model that accounts for signal-to-interference-and-noise ratio (SINR) and outage probability, which is a standard approach in wireless communication analysis.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation-based results derived from the proposed models, rather than empirical data from real-world networks or pre-existing datasets.

Key Insights and Ideas

  • The Inherent Trade-off: There's a fundamental trade-off between maximizing throughput and minimizing delay. Pushing more packets into the network (higher throughput) inevitably increases interference, slowing down all packets and thus increasing delay.
  • Strategic Waiting is Key: Introducing controlled waiting times for packets at the source queue is crucial for managing interference. This allows packets to "space out" and reduces the likelihood of collisions and signal degradation.
  • Interference is Predictable (to an extent): While interference is complex, by modeling it probabilistically and considering factors like distance and number of interferers, its impact on network performance can be analyzed and managed.
  • Coordination is Essential for Multiple Flows: When multiple data streams (flows) share the network, coordinating their injection times is vital to prevent them from interfering with each other, which would negate the benefits of individual flow optimization.
  • Guidelines for Network Design: The analytical framework provides practical insights for designing multihop networks, particularly for determining optimal placement of relay nodes and the number of parallel data flows.

Key Results

  • Optimal Waiting Times: The paper derives optimal waiting times for packets, which converge to a steady-state value in linear networks. These waiting times are shown to be dependent on factors like SINR thresholds and link outage tolerance.
  • Performance Balance: Through numerical examples, the paper demonstrates that by applying the proposed optimization strategies, a good balance between throughput and delay can be achieved. For instance, in one example, a maximum throughput of 231 Kbps was achieved with an HQD of 0.200 seconds, and in another, a THR of 1 Mbps was achieved with an HQD of 0.972 seconds.
  • Optimal Number of Flows: The analysis suggests that there's an optimal number of parallel data flows for a given network size and performance target, and that deviating from this optimum can degrade performance.
  • Scheduling Patterns: For multi-flow networks, the paper identifies optimal scheduling patterns for packet injections, often involving alternating shifts between flows to minimize interference.

Limitations and Future Work

  • Unlimited Node Density Assumption: The analysis often assumes unlimited node density, which simplifies calculations but might not perfectly reflect real-world scenarios with finite node placements. The authors note that their results can serve as guidelines for finite density networks.
  • Linear Network Simplification: While the 2D case is considered, the detailed recursive optimization is primarily developed for linear networks.
  • Synchronous Transmissions: The models assume synchronous transmissions, which is a simplification.
  • Future Work: The authors suggest extending the work to consider:
  • Random node positions in finite-density networks.
  • Treating packet flows as vector quantities.
  • Non-integer continuous time steps and asynchronous transmissions.
  • The relationship between routing strategies and inter-flow interference.

Summary updated

Abstract

The performance of a multihop wireless network is typically affected by the interference caused by transmissions in the same network. In a statistical fading environment, the interference effects become harder to predict. Information sources in a multihop wireless network can improve throughput and delay performance of data streams by implementing interference-aware packet injection mechanisms. Forcing packets to wait at the head of queues and coordinating packet injections among different sources enable effective control of co-packet interference. In this paper, throughput and delay performance in interference-limited multi-hop networks is analyzed. Using non-linear probabilistic hopping models, waiting times which jointly optimize the performance are derived. Optimally coordinated injection strategies are also investigated as functions of the number of information sources and their separations. Obtained results provide guidelines for the placement of relay nodes in multihop wireless networks.
BibTeX
@misc{bader2006throughput,
  author = {Ahmed Bader and Eylem Ekici},
  title = {{Throughput and delay optimization in interference-limited multihop networks}},
  year = {2006},
  doi = {10.1145/1132905.1132936},
}
Figure