Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 11

Proceedings of the 2017 Federated Conference on Computer Science and Information Systems

Distance-2 Collision-Free Broadcast Scheduling in Wireless Networks

, ,

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 ()

Full text

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.