Minimum-Latency Communication in Wireless Mesh Networks under Physical Interference Model

Wireless Mesh Networking (WMN) is an emerging communication paradigm to enable resilient, cost-efficient and reliable services for the future-generation wireless networks. We study the minimum-latency communication primitive of gossiping (all-to-all communication) in known topology WMNs under physical interference model, i.e., where the schedule of transmissions is pre-computed in advance based on full knowledge about the size and the topology of the Wireless Mesh Network (WMN). Each mesh node in the WMN 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 get a polynomial approximation algorithm. In this paper, we show a deterministic O(log n)-approximation algorithm in which the proposed scheme can complete gossiping task in time at most O(log n) factor far from the optimum (e.g., the minimum-latency schedule) and it can be computed in polynomial time in terms of the size of the WMN. From our best knowledge, it is the first time to investigate gossiping problem in WMNs under physical interference model.