Contention-Based Neighborhood Estimation

This paper proposes a probabilistic technique that enables a node to estimate the number of its neighbors that fulfill certain criteria. The technique does not require any a priori information about the network topology. Based on a query from the estimating node, the neighbors send busy tones in a sequence of time slots. Evaluating the fraction of empty slots, the querying node can infer about its neighborhood. Mathematical analysis and numerical simulations show how the estimation success and accuracy depend on the available time period. Applications of the method can be found, for example, in RFID systems and medium access protocols.