×

Basic computations in wireless networks. (English) Zbl 1173.68382

Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 533-542 (2005).
Summary: In this paper we address the problem of estimating the number of stations in a wireless network. Under the assumption that each station can detect collisions, we show that it is possible to estimate the number stations in the network within a factor 2 from the correct value in time \(O(\log n \log\log n)\). We further show that if no station can detect collisions, the same task can be accomplished within a factor of 3 in time \(O(\log^2 n)\) and maximum energy \(O(\log n)\) per node, with high probability. Finally, we present an algorithm that computes the minimum value held by the stations in the wireless network in time \(O(\log^2 n)\).
For the entire collection see [Zbl 1098.68001].

MSC:

68M14 Distributed systems
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI