Tight Bounds for MIS in Multichannel Radio Networks

Sebastian Daum (1) , Fabian Kuhn (1)

1 Department of Computer Science [Freiburg]

In [8] an algorithm has been presented that computes a maximal independent set (MIS) within O(log^2 n/F + log n polyloglog n) rounds in an n-node multichannel radio network with F communication channels. The paper uses a multichannel variant of the standard graph-based radio network model without collision detection and it assumes that the network graph is a polynomially bounded independence graph (BIG), a natural combinatorial generalization of well-known geographic families. The upper bound of [8] is known to be optimal up to the polyloglog n factor. In this paper, we adapt this algorithm and its analysis to improve the result of [8] in two ways. Mainly, we get rid of the polyloglog n factor in the running time and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Sebastian Daum, Fabian Kuhn. Tight Bounds for MIS in Multichannel Radio Networks. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_38⟩. ⟨hal-01207228⟩