Source-linked AI summary
Wireless Capacity with Oblivious Power in General Metrics
Magnús Már Halldórsson, Pradipta Mitra
TL;DR
The paper asks how much wireless communication can occur simultaneously under SINR interference, especially when links lie in arbitrary metrics and power assignments are constrained to be oblivious. It provides general-metric approximation algorithms and applies them to power control, obtaining near-tight bounds for uni- and bi-directional links. These results clarify the centralized complexity of the capacity and scheduling variants.
Problem
Algorithmic capacity results for arbitrary wireless-link instances are limited, despite the need to account for interference in general metrics and compare power control with simpler oblivious assignments.
Source: §1 · pp. 1–2Method
The paper develops a general-metric capacity approximation for length-monotone, sub-linear power assignments and uses it to analyze power control through mean power.
Source: §1.1 · p. 2Results
Mean power gives O(1)-approximate bi-directional capacity and O(log n + log log Δ)-approximate uni-directional power control, while oblivious-power bi-directional scheduling has a tight Θ(log n) approximation.
Source: §1.1 · p. 2Takeaways & Limitations
The results characterize how well oblivious power assignments approximate power control for capacity and scheduling across general metrics.
Source: §1 · p. 2, §1.1 · p. 2The analysis assumes β = 1 and negligible noise N, which the paper justifies for power control by scaling powers.
Source: §4 · p. 8
Abstract
from arXiv · showhide
The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight $\theta(\log n)$-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal $O(\log n + \log \log \Delta)$-approximation to the power control problem using mean power, where $\Delta$ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.
1. Introduction.
The paper studies algorithmic capacity and scheduling for wireless links under SINR interference, focusing on arbitrary metrics and the gap between power control and oblivious power assignments. It gives approximation results across link types and power assignments, extending prior guarantees beyond restricted metrics and path-loss assumptions.
1. Introduction.
- The capacity problem seeks the largest simultaneously feasible link set, while scheduling partitions links into the fewest feasible slots.The paper focuses mainly on capacity and studies its relationship to scheduling under power control and oblivious assignments.Source: §1 · p. 2
- The paper explores completely arbitrary metrics, motivated by how antenna directionality, walls, obstructions, environmental conditions, and terrain distort wireless transmissions beyond the simplifying 2D Euclidean assumption.It notes that most approximation results assumed α > 2, although α can equal or fall below 2 in real networks.Source: §1 · p. 2
1.1. Our Contributions.
- For any length-monotone, sub-linear power assignment, the paper gives an O(1)-approximation for capacity in general metrics and for both uni- and bi-directional links.This includes uniform, mean-power, and linear-power assignments; the prior O(1) result cited was for uniform power in the plane with α > 2.Source: §1.1 · p. 2
- With mean power, the paper gives an O(1)-approximation for bi-directional capacity and an O(log n + log log Δ)-approximation for uni-directional power control.The uni-directional guarantee nearly matches the Ω(log log Δ) lower bound for oblivious power assignments [9].Source: §1.1 · p. 2
- For bi-directional scheduling with power control, an O(log n)-approximation using oblivious power is best possible for that power-assignment class.A constructed instance is schedulable in one slot with some power assignment but requires Ω(log n) slots with oblivious power; its equal-length links also imply general metrics are strictly harder than doubling metrics for scheduling.Source: §1.1 · p. 2
- The approximation results hold for every positive path-loss exponent α, and the paper proves that exponential dependence on α is necessary in general.The analysis treats both interference caused and interference received through a pairwise-affectance matrix, extending the red-blue lemma from the plane to arbitrary metrics.Source: §1.1 · p. 2
1.2. Related Work.
- The paper improves or generalizes prior algorithmic bounds, including centralized scheduling and power-control results previously restricted to particular metrics or power assignments.Prior work included an O(log^2 n)-approximation for scheduling with fixed length-monotone, sub-linear power assignments, while the paper's capacity algorithm yields an improved O(log n)-approximate centralized algorithm; it also distinguishes its oblivious-power focus from nonoblivious power control [11].Source: §1.2 · p. 3
2. Model and Preliminaries.
The model represents communication requests as links in a metric space and tests concurrent transmissions using SINR feasibility. It recasts interference as affectance and uses matrix properties to analyze feasible sets and capacity.
2. Model and Preliminaries.
- A link is a sender-receiver request with length ℓ_v, and Δ is the ratio of the longest to shortest link.The model assumes unit traffic demand and handles non-unit demands by replicating links.Source: §2 · p. 3
- Under the path-loss model, received signal strength is P/d^α, and a set is feasible when every scheduled link satisfies the SINR condition.The SINR condition includes ambient noise N and the required threshold β; in bi-directional communication, inter-link distance is the minimum of four endpoint distances.Source: §2 · pp. 3–4
- Affectance measures interference from one link relative to the power received on another, turning feasibility into a bound on summed affectance.The affectances form a matrix, and feasibility is equivalent to each scheduled link's incoming affectance sum being at most 1.Source: §2 · p. 4
- The analysis uses approximately symmetric nonnegative matrices and bounds on their total entries to reason about feasible sets.The preliminaries state a row-sum bound for matrices with bounded total sum and a total-entry bound when a nonnegative approximately symmetric matrix satisfies Mp ≤ p.Source: §2 · pp. 4–5
3. Fixed Power in General Metrics.
For fixed powers, the paper gives a greedy capacity algorithm with a constant-factor guarantee in general metrics for length-monotone, sub-linear power assignments. It also shows that exponential dependence on α is necessary for approximation in general metrics under the stated conditions.
3. Fixed Power in General Metrics.
- The greedy algorithm C considers outgoing affectances and adds a final step to ensure feasibility in general metrics.It is closely related to Algorithm A(c) in; that final step is not needed in R2 when α > 2.Source: §3 · p. 5, Figure 1
3.1. Constant Factor Approximation for P-Capacity.
- Algorithm C approximates P-Capacity within a constant factor for any length-monotone, sub-linear power assignment.The result applies to uni- and bi-directional links.Source: §3.1 · pp. 5, 7
- The analysis extends the blue-dominant-centers and blue-shadowed lemmas to arbitrary metrics and length-monotone, sub-linear power assignments.Its red-blue argument removes at most two blue guards per red link, then compares red interference against blue interference.Source: §3.1 · p. 6
3.2. The Necessity of Exponential Dependence on α.
- The lower bound makes exponential dependence on α necessary in general, while leaving open better dependence for special cases such as small α on the plane.The authors note this does not rule out improved dependence in those special cases.Source: §3.1 · p. 7, §3.2 · p. 7
- For α ≥ lg n + 1 and fixed ε > 0, U-Capacity cannot be approximated within Ω(2^((1−ε)α)) in polynomial time unless P = NP.The proof reduces maximum independent set to capacity using unit links, with feasibility corresponding to independent sets.Source: §3.2 · pp. 7–8
4. Approximating Power Control Using Oblivious Power.
Using mean power, the section gives an O(log n + log log Δ) approximation for uni-directional power-control capacity and an O(1) approximation for bi-directional capacity in general metrics. It also establishes bounds for Lipschitz assignments and describes the partitioning and scaling used in the uni-directional analysis.
4.1. Uni-directional Capacity with Power Control via Oblivious Power.
4.2. Bi-Directional Capacity with Power Control.
- O(1) approximation for bi-directional power-control capacity in general metrics uses mean power, which is optimal up to constant factors.The section states that the algorithmic result follows from the fixed-power capacity algorithm and Theorem 19.Source: §4 · p. 8, §4.2 · pp. 11–12
4. Approximating Power Control Using Oblivious Power.
- Scaling an oblivious power assignment can convert a zero-noise feasible set into a constant-fraction subset feasible with ambient noise.The scaling factor can be found efficiently.Source: §4 · p. 8
4.1. Uni-directional Capacity with Power Control via Oblivious Power.
- For any Lipschitz power assignment, optimal capacity is at most O(log Δ) times the capacity under that assignment, a bound stated to be best possible.The matching lower bound cited is for uniform and linear power.Source: §4.1 · p. 9
- For nearly equilength links, any Lipschitz power assignment gives an O(1)-approximation to optimal capacity.For such links, affectance under a Lipschitz assignment differs from uniform-power affectance by at most a constant factor.Source: §4.1 · p. 9
- The uni-directional algorithm partitions links into length levels with ratio D = 8n^2/α between scales, then separates odd and even levels.Each resulting set has intra-level length variation at most D and inter-level separation at least D.Source: §4.1 · pp. 9–10
5. Scheduling vs. Capacity.
Capacity approximations yield scheduling approximations with an additional logarithmic factor, and scheduling can be harder than capacity. A construction shows that equal-length links feasible under some power assignment may require logarithmically many slots under oblivious power.
5. Scheduling vs. Capacity.
- Capacity results imply corresponding scheduling approximations within an additional O(log n) factor, reflecting the distinction between maximizing simultaneous links and partitioning links into slots.The passage compares scheduling to graph coloring and capacity to independent set.Source: §5 · p. 12
- Scheduling under fixed length-monotone, sub-linear power admits an O(log n)-approximation; with power control, the stated bounds are O(log ∆ log n) and O((log log ∆ + log n) log n) for uni-directional links and O(log n) for bi-directional links.The bounds apply in general distance metrics and for all fixed α > 0.Source: §5 · p. 12
- The construction demonstrates that scheduling can be harder than capacity by a logarithmic factor, despite constant-factor capacity approximation being possible for bi-directional links via oblivious power.The lower bound is established for uniform power, which is the only oblivious assignment for the equal-length links.Source: §5 · p. 12, §5.1 · p. 12
5.1. A Lower Bound.
- Equal-length links can be feasible under some power assignment yet require Ω(log n) slots under oblivious power in both uni-directional and bi-directional cases.Equal lengths leave uniform power as the only possible oblivious assignment; the construction has K = θ(log n).Source: §5.1 · pp. 12, 14
A.1. Matrix-algebraic Claims.
The appendix establishes matrix-algebraic claims through a contradiction argument and an induction on matrix size, using the smallest component of the power vector in the inductive step.
A.1. Matrix-algebraic Claims.
- The row and column parts of Claim 1 are proved by contradiction, ruling out the asserted abundance of rows with Se(r) > γ · λ.The proof assumes at least n/λ such rows and derives a contradiction.Source: §A.1 · p. 15
- The induction for Lemma 2 starts at n = 1, where m11 ≤ 1 establishes the claimed bound.The base case follows from m11p1 ≤ p1.Source: §A.1 · p. 15
- For the inductive step, the proof orders the components so pn is smallest and combines the matrix property with the induction hypothesis to bound the row sum by (q + 1)n.The displayed argument concludes with (q + 1)(n − 1) + q + 1 = (q + 1)n.Source: §A.1 · p. 15
A.2. Proof of Lemma 8.
The proof reduces affectance from remaining blue links onto red links by assigning at most two blue guards to each red link. A geometric distance claim and the signal-set condition then support the comparison.
A.2. Proof of Lemma 8.
- The argument switches the roles of senders and receivers before following the proof pattern of Lemma 7.Source: §A.2 · p. 15
- Each red link receives up to two distinct-from-other-sets blue guards, selected by proximity to its receiver; removing guards leaves a blue link when |B| > 2|R|.The guards are selected using the nearest sender and nearest receiver among the specified links.Source: §A.2 · p. 15
- For a remaining blue link, its affectance on a red link is compared with its affectance on one of that red link’s guards, relating total red-set affectance to affectance on blue links.The proof uses that the guards themselves are blue.Source: §A.2 · p. 15
- The geometric argument establishes dbt ≥ d/2; sub-linearity and the triangle inequality then bound the relevant sum over links in B.The proof derives the distance claim by contradiction and invokes the 3α-signal-set condition to rule out a close pair.Source: §A.2 · p. 16