Approximation algorithms for wireless link scheduling with flexible data rates

DOI10.1007/978-3-642-33090-2_57zbMATH Open1365.68124arXiv1205.1331OpenAlexW1957027869MaRDI QIDQ2912883FDOQ2912883

Authors: Thomas Kesselheim 

Publication date: 25 September 2012

Published in: Algorithms – ESA 2012 (Search for Journal in Brave)

Abstract: We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, which is determined by the signal-to-interference-plus-noise ratio (SINR). Each wireless link has a utility function mapping SINR values to the respective data rates. We have to decide which transmissions are performed simultaneously and (depending on the problem variant) also which transmission powers are used. In the capacity-maximization problem, one strives to maximize the overall network throughput, i.e., the summed utility of all links. For arbitrary utility functions (not necessarily continuous ones), we present an O(log n)-approximation when having n communication requests. This algorithm is built on a constant-factor approximation for the special case of the respective problem where utility functions only consist of a single step. In other words, each link has an individual threshold and we aim at maximizing the number of links whose threshold is satisfied. On the way, this improves the result in [Kesselheim, SODA 2011] by not only extending it to individual thresholds but also showing a constant approximation factor independent of assumptions on the underlying metric space or the network parameters. In addition, we consider the latency-minimization problem. Here, each link has a demand, e.g., representing an amount of data. We have to compute a schedule of shortest possible length such that for each link the demand is fulfilled, that is the overall summed utility (or data transferred) is at least as large as its demand. Based on the capacity-maximization algorithm, we show an O(log^2 n)-approximation for this problem.

Full work available at URL: https://arxiv.org/abs/1205.1331

Recommendations

• Wireless scheduling with power control
• Wireless Scheduling with Power Control
• Distributed wireless link scheduling in the SINR model
• Limitations of current wireless link scheduling algorithms
• Wireless Link Scheduling With Power Control and SINR Constraints

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cited In (10)

• Spanning Trees With Edge Conflicts and Wireless Connectivity
• The Power of Oblivious Wireless Power
• Approximability of OFDMA Scheduling
• Effective Wireless Scheduling via Hypergraph Sketches
• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Comparative study of approximation algorithms and heuristics for SINR scheduling with power control
• Wireless capacity with arbitrary gain matrix
• Approximate dynamic programming for link scheduling in wireless mesh networks
• Network design under general wireless interference
• Limitations of current wireless link scheduling algorithms

This page was built for publication: Approximation algorithms for wireless link scheduling with flexible data rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912883)