×

zbMATH — the first resource for mathematics

Energy-efficient initialization protocols for ad-hoc radio networks. (English) Zbl 0970.68631
Aggarwal, Alok (ed.) et al., Algorithms and computation. 10th international symposium, ISAAC’ 99, Chennai, India, December 16-18, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1741, 215-224 (1999).
Summary: The main contribution of this work is to propose energy-efficient randomized initialization protocols for ad-hoc radio networks (ARN, for short). First, we show that if the number \(n\) of stations is known beforehand, the single-channel ARN can be initialized by a protocol that terminates, with high probability, in \(O(n)\) time slots with no station being awake for more than \(O(\log n)\) time slots. We then go on to address the case where the number \(n\) of stations in the ARN is not known beforehand. We begin by discussing, an elegant protocol that provides a tight approximation of \(n\). Interestingly, this protocol terminates, with high probability, in \(O((\log n)^2)\) time slots and no station has to be awake for more than \(O(\log n)\) time slots. We use this protocol to design an energy-efficient initialization protocol that terminates, with high probability, in \(O(n)\) time slots with no station being awake for more than \(O(\log n)\) time slots. Finally, we design an energy-efficient initialization protocol for the \(k\)-channel ARN that terminates, with high probability, in \(O(\frac{n}{k}+ \log n)\) time slots, with no station being awake for more than \(O(\log n)\) time slots.
For the entire collection see [Zbl 0933.00045].

MSC:
68U99 Computing methodologies and applications
68M12 Network protocols
PDF BibTeX Cite
Full Text: DOI