TY - GEN
T1 - Distributed broadcast scheduling in mobile ad hoc networks with unknown topologies
AU - Tan, Guang
AU - Jarvis, Stephen A.
AU - Xue, James W.J.
AU - Hammond, Simon D.
PY - 2007
Y1 - 2007
N2 - Broadcasting is a fundamental communication task in mobile ad hoc networks, and minimizing broadcasting time (or latency) is crucial to the performance of many applications. Extensive studies have been conducted on the minimization of broadcasting time in the context of radio networks, which are usually modeled as general graphs. In this paper, we consider how to achieve this goal with distributed algorithms based on a more realistic (and restricted) network model. We propose a randomized algorithm that completes broadcasting in O(D log(n/D) + log2 n) time, where n is the number of nodes in the network and D the eccentricity (maximum distance from the source node to any other node). Compared with a previous optimal algorithm that achieves the same result for general networks, our algorithm obviates the need to know the network eccentricity D beforehand. We also propose a deterministic broadcasting algorithm that works in O(n) time, which is in contrast with the best known result of O{n log2 D) for general networks.
AB - Broadcasting is a fundamental communication task in mobile ad hoc networks, and minimizing broadcasting time (or latency) is crucial to the performance of many applications. Extensive studies have been conducted on the minimization of broadcasting time in the context of radio networks, which are usually modeled as general graphs. In this paper, we consider how to achieve this goal with distributed algorithms based on a more realistic (and restricted) network model. We propose a randomized algorithm that completes broadcasting in O(D log(n/D) + log2 n) time, where n is the number of nodes in the network and D the eccentricity (maximum distance from the source node to any other node). Compared with a previous optimal algorithm that achieves the same result for general networks, our algorithm obviates the need to know the network eccentricity D beforehand. We also propose a deterministic broadcasting algorithm that works in O(n) time, which is in contrast with the best known result of O{n log2 D) for general networks.
UR - http://www.scopus.com/inward/record.url?scp=34548786028&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2007.370590
DO - 10.1109/IPDPS.2007.370590
M3 - Conference contribution
AN - SCOPUS:34548786028
SN - 1424409101
SN - 9781424409105
T3 - Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
BT - Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
T2 - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007
Y2 - 26 March 2007 through 30 March 2007
ER -