Low-Latency Broadcast Scheduling in Ad Hoc Networks
Lists
Only you see this
Abstract
Abstract. Broadcast is a fundamental operation in wireless network, and naïve flooding is simply not practical. Previous results showed that although broadcast scheduling can achieve constant approximation ratios in respect of latency, the current state-of-the-art algorithm’s ratio is still overwhelmingly large ( ≈ 650). In this paper we present two basic broadcast scheduling algorithms that both achieve small ratios 51 and 24, while preserving low redundancy 1 and 4 (in terms of number of retransmissions a node has to make). Moreover, we also present a highly efficient algorithm whose latency is R + O ( √ R log 1.5 R)(whereR is the network radius) and each node only has to transmit up to 5 times. This result, in a sense of approximation, is nearly optimal since O ( √ R log 1.5 R)isnegligible when R is large. Moreover, R is itself a lower bound for latency, so the approximation ratio is nearly 1 and this algorithm is nearly optimal. 1
BibTeX
@inproceedings{huang2006low,
author = {Scott C.-H. Huang and Peng‐Jun Wan and Xiaohua Jia and Hongwei Du},
title = {{Low-Latency Broadcast Scheduling in Ad Hoc Networks}},
booktitle = {WASA},
year = {2006},
url = {https://openreview.net/forum?id=5wE6ufqM4c},
}Loading related content...