We study the problem of exchanging messages within a fixed group of k nodes, called participants, in an n-node radio network, modeled as an undirected graph. This communication task was previously considered in the setting of ATM video applications, in [J.M. Tsai, H.-H. Fang, C.-Y. Lee, A multicast solution for ATM video applications, IEEE Trans. Circuits Systems Video Technol. 7 (1997) 675-686], and was called multipoint-to-multipoint (M2M) multicasting. While the radio network topology is known to all nodes, it is assumed that no node is aware of the location of the participants. We give a distributed deterministic algorithm for the M2M multicasting problem in radio networks, and analyze its time complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O (d log2 n + k log4 n).

, , ,
Theoretical Computer Science
School of Computer Science

Gasieniec, L. (Leszek), Kranakis, E, Pelc, A. (Andrzej), & Xin, Q. (Qin). (2006). Deterministic M2M multicast in radio networks. Theoretical Computer Science, 362(1-3), 196–206. doi:10.1016/j.tcs.2006.06.017