## Distance-2 Collision-Free Broadcast Scheduling in Wireless Networks

### Valentin Pollet, Vincent Boudet, Jean-Claude König

DOI: http://dx.doi.org/10.15439/2017F140

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 469–472 (2017)

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 $\mathcal{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 $\mathcal{O}(\log(n))$ in unit disk graphs, and to $\mathcal{O}(1)$ when the neighbourhoods of the nodes are circular intervals.

### References

- R. Bar-Yehuda, O. Goldreich, and A. Itai, “On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization,” Journal of Computer and System Sciences, vol. 45, no. 1, pp. 104–126, 1992, ISSN: 0022-0000. DOI : 10.1016/0022-0000(92)90042-H.
- N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, “A lower bound for radio broadcast,” Journal of Computer and System Sciences, vol. 43, no. 2, pp. 290–298, 1991, ISSN : 0022-0000. http://dx.doi.org/10.1016/0022-0000(91)90015-W.
- O. Cogis, B. Darties, S. Durand, J. König, and G. Simonet, “The mv-decomposition: Definition and application to the distance-2 broadcast problem in multi-hops radio networks,” in Fifth IFIP-TCS, 2008, 2008, pp. 115–126. http://dx.doi.org/10.1007/978-0-387-09680-3 8.
- D. Peleg, “Time-efficient broadcasting in radio networks: A review,” in ICDCIT 2007, Bangalore, India, December 17-20. Proceedings, T. Janowski and H. Mohanty, Eds. Springer Berlin Heidelberg, 2007, pp. 1–18, ISBN: 978-3-540-77115-9. http://dx.doi.org/10.1007/978-3-540-77115-9 1.
- T. Chan and E. Grant, “Exact algorithms and apx-hardness results for geometric packing and covering problems,” Computational Geometry, vol. 47, no. 2, pp. 112–124, 2014, Special Issue: 23rd Canadian Conference on Computational Geometry (CCCG11), ISSN : 0925-7721. DOI : 10.1016/j.comgeo.2012.04.001.