Date Added: Aug 2009
Neighbor discovery is one of the first steps in the self-organization of a large wireless network. Neighbor discovery algorithms can be classified into two categories, viz. randomized or deterministic. In a randomized neighbor discovery algorithm, each node transmits at randomly chosen times and yet discovers all its neighbors by a given time with high probability. In a deterministic neighbor discovery algorithm, each node transmits according to a predetermined transmission schedule that allows it to discover all its neighbors by a given time with probability one. Guaranteed neighbor discovery typically comes at the cost of increased running time and often requires unrealistic assumptions such as synchronization between nodes and apriori knowledge of the number of neighbors.