Minimum-latency communication in wireless mesh networks under noisy physical interference model

In traditional physical interference model for Wireless Mesh Networks (WMNs) or wireless networks, a message transmitted by a node v to the intended node w within v′ transmission range can be successfully received at w if only if in this step w is listening and the interference power received at w due to simultaneous transmissions from other nodes within w′ interference range is less than the predefined system threshold. Otherwise, w does not retrieve any message in this time step/round. We relax the assumption of traditional physical interference model by introducing a “noisy” model in which random faults can occur at both senders and receivers. More precisely, for a constant noise parameter p ∊ [0, 1), either every sender has probability p of transmitting a noise or every receiver has probability p of receiving potential noise in addition to the traditional physical interference assumptions. Our new noisy physical interference model is an extension from the work in [ACM PODC 2017 [10]] for the graph-based interference model to the traditional physical interference model. We study the minimum-latency communication primitive of gossiping (all-to-all communication) in known topology WMNs under the “noisy” physical interference model, i.e., where the schedule of transmissions is based on full knowledge about the size and the topology of the given WMN). Each mesh node is initially given a message and the objective is to design a minimum-latency schedule such that each mesh node distributes its message to all other mesh nodes. The problem of computing a minimum-latency gossiping schedule for a given WMN is NP-hard, hence it is only possible to achieve a polynomial approximation algorithm. In this paper, we show the gossiping algorithm in [IEEE ICC 2010 [26]] does not remain robust under the noisy physical interference model. We give a modified version that is robust to sender and receiver faults with an extra small overhead. Our new robust scheme can complete the gossiping task in time O(D + Δ log 3 n) for any n-node wireless network of diameter D and maximum degree Δ. It is an almost optimal scheme since there exits a topology such as Δ-regular graphs under which the gossiping can not be accomplished in time less than Ω(D + Δ log n/log Δ).