# 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
Full Text: