Name
Abstract | ||
|---|---|---|
Wireless mesh networks (WMNs) 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 multi-hop ad-hoc WMNs. 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. Minimum-latency gossiping problem is known to be NP-hard even for the scenario in which the topology of the WMN is known to all mesh nodes in advance. We show an approximation scheme that can complete gossiping task in O(n log3/2 n) time units with high probability at least 1 - 1/n in any ad-hoc WMN of size n. Our algorithm allows the labels (identifiers) of the mesh nodes to be polynomially large in n. To the best of our knowledge, this is the first time that randomized algorithm has been considered in ad-hoc WMNs with large labels. Moreover, our gossiping scheme also significantly improved all current gossiping algorithms in terms of approximation ratio. Our work has approximation ratio at most O(log3/2 n) which is a great improvement of the current best known state-of-the-art algorithm with approximation ratio O(log2 n) but for linearly large node labels by Czumaj and Rytter [FOCS'03]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICC.2009.5199185 | ICC |
Keywords | Field | DocType |
optimisation,size n,multi-hop wireless mesh network,all-to-all communication,wmn,np-hard problem,telecommunication network reliability,communication paradigm,ad-hoc wmn,minimum-latency gossiping,mesh node,telecommunication network topology,telecommunication services,approximation ratio,large label,computational complexity,telecommunication computing,multihop wireless mesh networks,n log3,ad-hoc wmns,multihop ad-hoc wmn,ad hoc networks,approximation scheme,np hard problem,topology,spread spectrum communication,broadcasting,wireless networks,network topology,randomized algorithm,approximation algorithms,wireless mesh network,schedules,ad hoc network,routing,cost efficiency,wireless network | Randomized algorithm,Approximation algorithm,Wireless network,Switched mesh,Computer science,Computer network,Network topology,Wireless ad hoc network,Wireless mesh network,Shared mesh | Conference |
ISSN | ISBN | Citations |
1938-1883 E-ISBN : 978-1-4244-3435-0 | 978-1-4244-3435-0 | 0 |
PageRank | References | Authors |
0.34 | 24 | 3 |