Treffer: Scheduling Multicast Transmissions under SINR Constraints.

The problem of scheduling wireless transmissions under signal to interference-plus-noise ratio (SINR) constraints has received increasing attention recently. While previous work has considered the unicast case where each transmission has one sender and one receiver, we consider the setting of multicast requests where each transmission has one sender and a set of receivers. A set of multicast transmissions can be scheduled in the same round if the SINR at all receivers is above a certain threshold. The goal is to minimise the number of rounds. Building on the relationship between SINR scheduling and unit disk graph colouring established by Halldórsson (ESA 2009), we present an ]> -approximation algorithm for multicast scheduling in the SINR model, where Γ is the ratio of the longest to the shortest link length, considering only the longest link of each multicast request. The algorithm uses uniform power assignment and can be implemented online. We also compare the model of atomic multicasts (where all receivers of a multicast must receive the transmission in the same round) to the model of splittable multicasts (where a multicast sender can transmit in several rounds, each time serving a subset of its receivers). Furthermore, we consider the throughput maximisation problem and obtain an ]> -competitive randomised online algorithm and show that every deterministic algorithm, even for unicast links and using arbitrary power assignments, has competitive ratio Ώ(logΓ). [ABSTRACT FROM AUTHOR]

Copyright of Algorithms for Sensor Systems is the property of Springer Nature / Books and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)