Abstract | In this paper we address the problem of estimating the num-
ber 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(log2 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(log2 n). |