Skip to Main content Skip to Navigation
Conference papers

Distance-2 Collision-Free Broadcast Scheduling in Wireless Networks

Valentin Pollet 1 Vincent Boudet 1 Jean-Claude König 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper, we study the distance-2 broadcast scheduling problem in synchronous wireless networks of known topology. Two constraints are taken under consideration: the schedule must be collision-free and the nodes at distance 2 must be informed by nodes at distance 1. In general graphs, a tight bound of O(log(n) 2 ) slots to complete the broadcast is known, n being the number of nodes at distance 2. We improve this bound to O(log(n)) in unit disk graphs, and to O(1) when the neighbourhoods of the nodes are circular intervals.
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Vincent Boudet <>
Submitted on : Friday, December 20, 2019 - 12:29:02 PM
Last modification on : Friday, December 20, 2019 - 12:49:30 PM
Long-term archiving on: : Saturday, March 21, 2020 - 7:53:52 PM


Publisher files allowed on an open archive




Valentin Pollet, Vincent Boudet, Jean-Claude König. Distance-2 Collision-Free Broadcast Scheduling in Wireless Networks. FedCSIS: Federated Conference on Computer Science and Information Systems, Sep 2017, Prague, Czech Republic. pp.469-472, ⟨10.15439/2017F140⟩. ⟨lirmm-01660842⟩



Record views


Files downloads