2015/02/18 by Magnús M. Halldórsson, Halldorsson, Magnus M., Tigran Tonoyan +1
Computer Science · Engineering · #Advanced Wireless Network Optimization #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.1502.05279
openalex publication_date 2015/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation. We first show that the known algorithms fail to obtain sub-logarithmic bounds; that is, their approximation ratio are Ω(log max(Δ,n)), where n is the number of links, Δ is the ratio of the maximum and minimum link lengths, and Ω hides doubly-logarithmic factors. We then present the first O(loglogΔ)-approximation algorithm, which is known to be best possible (in terms of Δ) for oblivious power schemes. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability, and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our result resolve the price of oblivious power for wireless scheduling, or the value of allowing unfettered power control.