Paper Info
Title
Scheduling multicast transmissions under SINR constraints
Abstract
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 O(log Γ)-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 O(log Γ)-competitive randomised online algorithm and show that every deterministic algorithm, even for unicast links and using arbitrary power assignments, has competitive ratio Ω(log Γ).
Year
DOI
Venue
2010
10.1007/978-3-642-16988-5_5
ALGOSENSORS
Keywords
Field
DocType
sinr constraint,competitive ratio,deterministic algorithm,competitive randomised online algorithm,multicast scheduling,multicast request,multicast transmission,approximation algorithm,sinr model,sinr scheduling,multicast sender,unit disk graph,online algorithm,signal to interference plus noise ratio
Source-specific multicast,Online algorithm,Computer science,Xcast,Computer network,Deterministic algorithm,Multicast,Unicast,Competitive analysis,Distributed computing,Unit disk graph
Conference
Volume
ISSN
ISBN
6451
0302-9743
3-642-16987-2
Citations 
PageRank 
References 
10
0.68
16
Authors
2
Name
Order
Citations
PageRank
Thomas Erlebach11233102.74
Tom Grant2161.16