Latency optimal broadcasting in noisy wireless mesh networks
Qin Xin, Yan Xia · 2017
Broadcasting (one-to-all communication) is one of most important and fundamental research problems for information dissemination in all types of networks. In this paper, we mainly focus on the minimum-latency broadcasting in known topology Wireless Mesh Networks (WMNs), in which the network topology and the size is known in advance. It is well known that the computation of a minimum-latency broadcasting schedule for a given WMN is NP-hard, therefore polynomial-time solutions can be only achieved by approximation algorithms. In this paper, we adopt a new noisy wireless network model introduced very recently by Censor-Hillel et al. in [ACM PODC 2017, [6]]. More specifically, for a given noise parameter p ϵ [0,1], any sender has a probability p to transmit noise or any receiver has a probability p to potentially receive noise in addition to the traditional wireless collision model. In this paper, we first propose a new asymptotically latency-optimal approximation algorithm (under faultless model) that can complete single-message broadcasting task in D + O(log2n) time steps/rounds in any WMN of size n, and diameter D. We then show this diameter-linear broadcasting algorithm remains robust under the noisy wireless network model and also improves the currently best known and very recent result in [6] by a Θ(log logn) factor. In this paper, we also further extend our robust singlemessage broadcasting algorithm to k multi-message broadcasting scenario and show it can broadcast k messages in O(D + k log n + log2n) time rounds. This new robust multimessage broadcasting scheme is not only asymptotically optimal but also answers affirmatively the problem left open in [6] on the existence of an algorithm that is robust to sender and receiver faults and can broadcast k messages in O(D + klogn + polylog(n)) time rounds.