Abstract
Traditional wireless network scheduling often ignores "weak" links by treating packet delivery as a binary success or failure. Mutual Information Accumulation (MIA) allows receivers to collect and combine partial information over multiple time slots, effectively utilizing these weak links to expand network capacity. However, MIA introduces temporal coupling, making stability analysis difficult for standard algorithms like backpressure. This paper proposes two scheduling policies to address this: a $T$-slot dynamic control algorithm and a virtual queue-based algorithm. The virtual queue approach transforms the temporal accumulation process into a spatial virtual network, enabling the application of Lyapunov drift analysis for slot-by-slot stability. Simulations on diamond and multi-commodity network topologies confirm that these algorithms significantly expand the network stability region while maintaining manageable delays.
Introduction
In conventional wireless networking, transmissions are typically modeled as independent events where a packet is either successfully decoded in a single time slot or discarded as noise. This "all-or-nothing" paradigm fails to exploit the potential of weak signals. Physical layer techniques such as Mutual Information Accumulation (MIA) allow a receiver to store corrupted or partial data and combine it with subsequent transmissions of the same packet. Once the accumulated mutual information exceeds the packet's entropy, it is successfully decoded.
While MIA offers significant capacity gains, it breaks the independent and identically distributed (i.i.d.) assumption required by standard scheduling algorithms like the "backpressure" algorithm. Because the state of a packet depends on information gathered in previous slots, the resulting "temporal coupling" makes proving network stability—ensuring queues do not grow indefinitely—a major theoretical challenge.
Methods
The authors propose two primary scheduling policies to manage temporal coupling in MIA-enabled networks.
1. $T$-slot Dynamic Control Algorithm
This algorithm simplifies the problem by making scheduling decisions every $T$ slots rather than every single slot. By holding a decision for $T$ consecutive slots, weak links are given sufficient time to deliver packets. However, this approach introduces a linear trade-off: as $T$ increases to approach maximum capacity, the average packet delay also increases linearly.
2. Virtual Queue Based Algorithm
To overcome the delay issues of the $T$-slot approach, the authors introduce a sophisticated virtual network model. They transform the temporal process of information accumulation into a spatial flow through virtual nodes and buffers.
As shown in the figure above, a single physical link $(i, j)$ is modeled using two intermediate virtual nodes, $v_{ij}$ and $p_{ij}$. The process is decomposed into three virtual hops:
- Moving a packet from the source queue $U_i^c$ to a "to-be-transmitted" virtual buffer $V_{ij}^c$.
- The accumulation process itself, modeled as a virtual link $r_{ij}$ between $v_{ij}$ and $p_{ij}$.
- Moving the decoded packet from the virtual buffer $P_{ij}^c$ into the receiver's physical queue $U_j^c$.
This virtualization allows the use of standard Lyapunov drift analysis to prove stability on a slot-by-slot basis, effectively decoupling the temporal dependencies and providing a more efficient scheduling mechanism.
Key Results and Discussion
The algorithms were evaluated using numerical simulations on two topologies: a 4-node "diamond" network and a 10-node multi-commodity network.
- Capacity Expansion: MIA-enabled scheduling fundamentally expands the stability region of the network. In the 4-node diamond network, the stability region grew from a simple triangle to a larger polygon, increasing the maximum supportable arrival rate per node from 0.5 to approximately 0.53.
- Delay Performance: The Virtual Queue algorithm significantly outperformed the $T$-slot algorithm in terms of delay, particularly under heavy traffic conditions near the network's capacity limit.
- Theoretical Consistency: The authors demonstrated that despite the complexities of packetization, the maximum capacity region aligns with a "fluid model" where data flows continuously.
Limitations and Future Work
While effective, the current algorithms primarily rely on centralized control, which can be difficult to implement in large-scale ad-hoc networks. Furthermore, the model assumes relatively static channels; highly mobile environments where channel quality fluctuates rapidly may require more complex accumulation models. Future work could also explore relaxing the "single parent" assumption to allow for true broadcast scenarios where multiple nodes accumulate information from the same transmission simultaneously.
Summary updated