| Authors | Q. Xin and F. Manne |
| Title | Latency-Optimal Communication in Wireless Mesh Networks |
| Afilliation | , Communication Systems |
| Status | Published |
| Publication Type | Proceedings, refereed |
| Year of Publication | 2009 |
| Conference Name | Proceedings of the 15th Asia-Pacific Conference on Communications (APCC 2009) |
| Publisher | IEEE |
| ISBN Number | 978-1-4244-4784-8 |
| Abstract | 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, 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 approximation algorithm that can complete gossiping task in (D+\fracΔłog n}łogΔ}) time units in any WMN of size n, diameter D, and maximum degree Δ. This is an asymptotically optimal schedule in the sense that there exists a WMN topology, specifically a Δ-regular tree, in which the gossiping task cannot be accomplished in less than Ømega(D+\fracΔłog n}łogΔ}) units of time. Our algorithm also improves on currently best known gossiping schedule of length O(D+\fracΔłog n}łogΔ-łogłog n}}) in [Algorithmica 54(2):226-242, 2009]. |
| Citation Key | Simula.ND.345 |