Source-linked AI summary
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model
Thomas Kesselheim
TL;DR
The paper studies wireless capacity maximization with power control under SINR constraints, where selecting admissible communicating pairs is computationally difficult. It presents a simple selection-and-scheduling approach that achieves constant-factor approximation in fading metrics, O(log n) in general metrics, and polylogarithmic guarantees for scheduling variants.
Problem
Wireless capacity maximization must jointly select admissible communicating pairs and transmission powers because interference makes the underlying optimization problems non-convex.
Method
The algorithm selects links using a sufficient condition, schedules them greedily, and chooses transmission powers afterward.
Results
A constant-factor approximation is achieved in fading metrics, O(log n) in general metrics, and polylogarithmic approximations for single-hop and multi-hop scheduling variants.
Takeaways & Limitations
The approach provides a simple abstraction for transferring techniques from wired networks to wireless interference problems and improving approximation guarantees.
Takeaways & Limitations
The approach assumes unrestricted transmission powers, and several log n factors may potentially be removed.
Abstract
from arXiv · showhide
In modern wireless networks, devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can improve the network capacity significantly. We study this problem in the physical interference model using SINR constraints. In the SINR capacity maximization problem, we are given n pairs of senders and receivers, located in a metric space (usually a so-called fading metric). The algorithm shall select a subset of these pairs and choose a power level for each of them with the objective of maximizing the number of simultaneous communications. This is, the selected pairs have to satisfy the SINR constraints with respect to the chosen powers. We present the first algorithm achieving a constant-factor approximation in fading metrics. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver. Expressed only in terms of n, they are (trivial) Omega(n) approximations. Our algorithm still achieves an O(log n) approximation if we only assume to have a general metric space rather than a fading metric. Furthermore, by using standard techniques the algorithm can also be used in single-hop and multi-hop scheduling scenarios. Here, we also get polylog(n) approximations.
1 Introduction
The paper studies capacity maximization with power control under SINR constraints and develops approximation algorithms that avoid dependence on link-length ratios. Its main algorithm is constant-factor in fading metrics, O(log n) in general metrics, and extends to scheduling variants.
- 1 Introduction: The capacity maximization problem selects a maximum-cardinality subset of n sender-receiver pairs and a power assignment satisfying every SINR constraint.SINR compares desired signal strength with interference and ambient noise against threshold β.
- 1 Introduction: Earlier distance-based power assignments can degrade to Ω(n) in terms of n when the link-length ratio Δ is large.The prior bound is O(log log Δ + log n), and its dependence on Δ can become no better than a trivial guarantee.
- 1 Introduction: The approach addresses nonconvexity by selecting admissible sets through a sufficient condition, then using power control to make those sets feasible.Feasibility of a fixed set and power assignment is polynomial-time decidable by linear programming, but finding suitable sets remains difficult.
- 1.2 Our Results: Constant-factor approximation is achieved for k-channel capacity maximization in fading metrics, including the Euclidean plane with α > 2.The algorithm selects links first and assigns powers afterward using a greedy sufficient condition.
- 1.2 Our Results: O(log n) approximation holds in arbitrary metrics, while repeated application yields O(log n) and O(log^2 n) bounds for interference scheduling in fading and general metrics.The scheduling objective is to serve all requests while minimizing the number of sets used.
- 1.2 Our Results: The framework extends to multi-hop scheduling, giving O(log^2 n) approximation with fixed paths and O(log^2 n) or O(log^3 n) after randomized routing.These results improve on the cited previous scheduling guarantees.
2 Admissible Sets in Fading Metrics
The admissible-set analysis derives distance-based necessary conditions for any feasible set and exploits fading metrics to bound aggregate interference. These bounds support the later comparison between greedy selection and feasibility.
- 2 Admissible Sets in Fading Metrics: Any admissible set must satisfy distance constraints that limit how many comparable-length links can be near an arbitrary sender-receiver pair.The analysis considers an added pair and bounds links whose sender-receiver lengths are at least the same scale.
- 2 Admissible Sets in Fading Metrics: Signal strengthening decomposes an admissible link set into constantly many subsets whose endpoints are mutually separated by at least the minimum link length.Each subset remains admissible with a strengthened gain, enabling geometric packing arguments.
- 2 Admissible Sets in Fading Metrics: The proof combines SINR inequalities, triangle inequality, and endpoint separation to show that involved nodes cannot cluster arbitrarily closely.Multiplying inequalities yields a product-distance constraint, followed by a lower bound on relevant pairwise distances.
- 2 Admissible Sets in Fading Metrics: In a fading metric, separated senders contribute only bounded total interference because the metric’s doubling dimension is strictly below the path-loss exponent α.Packing balls around nodes converts the fading-metric property into a convergent interference bound.
3 Selection and Power Control Algorithm
The algorithm greedily assigns links to sets using a sufficient interference condition, then assigns powers recursively in decreasing link-length order. The resulting power assignment is feasible, and similarity between sufficient and necessary conditions enables approximation guarantees.
- 3 Selection and Power Control Algorithm: The greedy procedure processes links by increasing length, assigns each to a set satisfying Condition 1, and discards links that fit no set.This selection stage is followed by recursive power assignment rather than fixed distance-based powers.
- 3 Selection and Power Control Algorithm: Powers are assigned in decreasing link-length order, with each shorter link receiving power proportional to what is needed to handle longer-link interference and noise.The powers are then scaled so p(ℓ′) ≥ 2βN · d(ℓ′)^α.
- 3 Selection and Power Control Algorithm: If Condition 1 holds for every link in a selected set, the recursive procedure produces a power assignment satisfying all SINR constraints.The proof separately bounds interference from longer links, shorter links, and ambient noise.
- 3 Selection and Power Control Algorithm: The shorter-link interference analysis bounds indirect effects from recursively adapted powers by decomposing contributions into direct interference terms.The proof partitions terms into M1 and M2 according to relative distances and uses the resulting geometric inequalities.
- 3 Selection and Power Control Algorithm: The feasible greedy solution supports approximation analysis because its sufficient condition resembles the necessary condition satisfied by every admissible set.This similarity is used to compare the selected solution with an optimum.
4 Deriving the Approximation Factor
The analysis compares the greedy algorithm with optimal admissible sets through an edge-weighted graph, yielding constant-factor approximation in fading metrics and robustness to bidirectional communication.
- The edge weight measures one link’s impact on another, and W(L) is the maximum outgoing weight over links.
- Theorem 5 bounds the greedy solution using the maximum interference weight W(L), the number of channels k, and threshold τ.
- The approximation follows by applying the bound to the union of k admissible sets in the optimal solution.
- The greedy algorithm approximates k-channel capacity maximization within O(1) in fading metrics.
- The feasibility argument is symmetric in senders and receivers, so the algorithm also applies to half-duplex and full-duplex communication.
5 General Metrics
In general metrics, feasibility remains valid under the triangle inequality, but the fading-metric interference bound weakens to O(log n), producing an O(log n) approximation.
- The algorithm remains feasible in general metrics because feasibility requires only the triangle inequality.
- The fading-metric assumption matters because the stronger constant interference bound does not hold in general metrics.
- For admissible sets in general metrics, W(L) is O(log n), and this bound is tight for the analysis.
6 Scheduling Single-Hop Requests and the Scheduling Complexity
Repeated use of the capacity-maximization algorithm yields greedy schedules for all single-hop requests, with polylogarithmic approximation guarantees tied to the metric class.
- It repeatedly runs the capacity-maximization algorithm on unscheduled requests, placing each link in the first feasible time slot.
- The greedy scheduling algorithm computes a schedule of length O(W(R) · log n).
- Because W(R) is O(T(R)) in fading metrics and O(T(R) · log n) in general metrics, the approximations are O(log n) and O(log^2 n), respectively.
- The scheduling complexity T(R) is characterized up to an O(log n) factor by W(R), the maximum weighted out-degree.
7 Scheduling Multi-Hop Requests
Random delays reduce fixed-path multi-hop scheduling to single-hop instances, while LP-based path selection extends the approach to routing; the resulting guarantees are polylogarithmic.
- 7.1 Scheduling Packets on Fixed Paths: Each packet receives a random delay, creating W(R)/(3 ln n) + D single-hop problems whose schedules are concatenated.
- 7.1 Scheduling Packets on Fixed Paths: For fixed paths, random delays and single-hop scheduling produce a schedule of length O(W(R) · log n + D · log^2 n) with high probability.
- 7.1 Scheduling Packets on Fixed Paths: Relative to the optimal fixed-path schedule, the method gives an O(log^2 n) approximation.
- 7.2 Routing: For routing, LP variables indicate whether a commodity’s path contains an edge, while the objective minimizes z = max{W(R), D}.
- 7.2 Routing: Independent randomized path rounding gives D ≤ 2z* and W(R) = O(z* · log n) with high probability.
- 7.2 Routing: The cross-layer latency problem receives O(log^2 n) and O(log^3 n) approximations in fading and general metrics, respectively.
8 Conclusions and Open Problems
The paper develops simple approximation algorithms for physical-interference problems, while identifying remaining approximation, decentralization, and power-range questions.
- 8 Conclusions and Open Problems: Several logarithmic factors may still be removable, and the best constant for capacity maximization in fading metrics—or a PTAS—remains unknown.The paper also notes that hardness results are scarce for these problems.
- 8 Conclusions and Open Problems: The abstraction enables well-known wired-network techniques to solve further wireless problems with significantly better approximations than previous algorithms.The authors suggest possible extensions to dynamic packet injection and topology control.
- 8 Conclusions and Open Problems: Practical relevance would improve if the algorithm were decentralized, with distributed-heuristic ideas identified as a possible source of techniques.The authors also point to restricted transmission powers as an important unresolved case.
A Proof of Theorem 7
The proof of Theorem 7 separates interference into contributions from near and far links, bounding each part in a different subsequent argument.
- A Proof of Theorem 7: Theorem 7 is proved by splitting the interference sum into near-link and far-link contributions.The next section handles near links, after which the remaining links are bounded.
- A Proof of Theorem 7: Near links are defined by one endpoint lying closer to w than to its corresponding endpoint.The proof then treats the contribution of these links separately.
- A Proof of Theorem 7: The remaining links are handled after the near-link contribution has been bounded.This decomposition organizes the proof into two complementary bounds.
A.1 Bounding the Contribution of Near Links
Near-link contributions remain bounded because their distances from w grow exponentially, despite the possibility of arbitrarily many such links.
- A.1 Bounding the Contribution of Near Links: Near links satisfy d(v,w) ≤ d(ℓv), and their distances from w increase exponentially, yielding a constant contribution bound in any metric.The argument applies even when arbitrarily many near links exist.
- A.1 Bounding the Contribution of Near Links: Signal strengthening decomposes the admissible link set into constantly many sets with gain β′ = 2α before bounding each set separately.This is used in the proof of the proposition bounding near-link interference.
- A.1 Bounding the Contribution of Near Links: The links are partitioned into T and distance-scale sets Ua, with each set containing at most one link.T contains links with an endpoint within distance d of w, while Ua groups links by dyadic distance ranges.
- A.1 Bounding the Contribution of Near Links: If two links occupied one such set, the triangle inequality would upper-bound cross-distances, contradicting the SINR-derived product lower bound.The lower bound is d(s,r′) · d(s′,r) ≥ 16 · d(s,r) · d(s′,r′).
- A.1 Bounding the Contribution of Near Links: The proof bounds the contribution after establishing cardinality bounds for the distance-partitioned sets.The cardinality result is then used to control the sum.
A.2 Bounding the Contribution of Far Links
Far-link contributions are bounded by combining a node-counting fact around w with a distance-ordered, exponentially grouped analysis.
- A.2 Bounding the Contribution of Far Links: The far-link case assumes both endpoints v satisfy d(v,w) ≥ d(ℓv), and the proof bounds links under this condition.This is stated as Proposition 11.
- A.2 Bounding the Contribution of Far Links: The proof first bounds how many nodes can lie within distance Z of w.This counting fact is then applied to progressively larger neighborhoods.
- A.2 Bounding the Contribution of Far Links: A minimum-power link and the SINR condition provide the basis for bounding the number of nodes in a neighborhood of w.The argument considers links with at least one endpoint in KZ(w).
- A.2 Bounding the Contribution of Far Links: Ordering endpoints by distance from w makes each neighborhood KZj(w) an initial segment of the ordered node set.The proof then groups indices into dyadic ranges Rj and defines Zj from each range.
- A.2 Bounding the Contribution of Far Links: Applying the neighborhood-counting fact to these groups yields the required bound on the far-link sum.The proof concludes the proposition after applying Fact 12 and bounding the sum.