Abstract
This paper addresses the challenge of scheduling wireless transmissions in multihop networks under a realistic physical interference model (SINR), where interference is global and additive. The authors propose a localized scheduling algorithm that utilizes shifting virtual grids to decouple global interference into manageable local problems. By employing a "pick-and-compare" scheme based on queue lengths, the algorithm is proven to achieve a guaranteed fraction of optimal network throughput without requiring a central controller. Theoretical results show constant-factor performance for linear power settings and logarithmic approximation for uniform power, validated by synthetic simulations.
Introduction
In multihop wireless networks, such as sensor or mesh networks, efficient link scheduling is critical for maximizing throughput. Traditionally, researchers have relied on binary interference models (e.g., protocol models) that assume interference is limited to a specific range. However, these models fail to capture the physical reality of Signal-to-Interference-plus-Noise Ratio (SINR), where the cumulative background noise from distant nodes can corrupt local transmissions.
Because physical interference is globally coupled, designing localized algorithms—where nodes make decisions based only on neighborhood information—is notoriously difficult. Most existing SINR-based scheduling requires global knowledge, which is impractical for large-scale, decentralized deployments. This paper introduces a framework that bridges this gap by localizing global interference through geometric partitioning.
Methodology
Partition and Shifting
The core of the proposed algorithm is a virtual partitioning of the network into a grid of "Super-subSquares" and "Sub-squares." To decouple global interference, the algorithm only allows scheduling within the inner "Sub-squares," ensuring that active transmission zones are separated by a mathematically calculated safe buffer distance ($M$). This buffer guarantees that the aggregate interference from all external nodes remains below a tolerable threshold ($I_{max}$).
To ensure fairness and prevent nodes in the buffer zones from being permanently silenced, the virtual grid "shifts" at every time slot. This shifting ensures that every node eventually falls within an active Sub-square over a finite period.
Pick-and-Compare Scheme
At each time slot, local coordinators compute a new schedule based on current queue lengths (the "weight" of the links). The algorithm uses a "pick-and-compare" logic: it compares the weight of the newly computed local schedule against the schedule from the previous time slot. By selecting the heavier (more productive) schedule, the network iteratively evolves toward an optimal throughput state.
Power-Specific Local Computation
The complexity of the local scheduling task depends on the power control policy:
- Linear Power: Transmission power scales with distance. The authors prove that the number of non-interfering links in a local area is bounded by a constant, allowing for exact local solutions via brute-force enumeration.
- Uniform Power: All nodes transmit at the same power. In this case, the number of local links is not strictly bounded, requiring the use of approximation algorithms to maintain efficiency.
Key Insights and Results
Theoretical Guarantees
The most significant contribution is the proof that global interference can be strictly bounded. Under the linear power setting, this is the first localized algorithm proven to achieve a constant fraction of the optimal capacity region. Under the uniform power setting, the algorithm achieves an $O(\log |V|)$ approximation ratio.
Simulation Performance
In synthetic simulations involving 500 nodes, the localized algorithm achieved approximately 50% of the maximum supportable traffic rate compared to centralized greedy algorithms. For instance, in linear power scenarios, the localized version maintained stability up to an arrival rate of ~0.18, while the centralized version reached ~0.28. This performance is a favorable trade-off considering the elimination of massive communication overhead required for centralized control.
Conclusion and Future Work
While the algorithm provides a robust framework for localized SINR scheduling, it requires nodes to have geographic location awareness (e.g., GPS) and assumes a relatively static topology. Future work may address the latency issues inherent in Maximum Weight Matching (MWM) style algorithms and seek to improve the approximation ratio for uniform power settings to a constant fraction.
Summary updated