In this thesis we consider the problem of neighbor discovery in synchronous single hop wireless ad-hoc networks. The central problem is to establish a broadcasting sequence such that only one transmitter broadcasts at a time while all others listen and every transmitter in the network gets at least one chance to broadcast. We consider the question: how fast we can achieve neighbor discovery with k nodes in the network, each having a unique id assigned from an id space much larger than k in radio communication models with and without collision detection. We take the simulation route to answer this question. We implemented one randomized and two deterministic algorithms for neighbor discovery and compared their performance in terms of number of rounds required as a function of the number of nodes in the network and the size of the space from which ids are chosen. Our simulation results show that the randomized algorithm is most efficient and is easiest to implement. The deterministic algorithm for the no collision detection model has round complexity comparable to the size of the id space and is orders of magnitude less efficient than the randomized algorithm. The deterministic algorithm for the collision detection model is slower than the randomized algorithm by a factor of log(n), where n is the size of the id space. Our analysis would be useful for choosing optimal algorithms for field applications depending on the radio communication model and network topology. It will reveal any large constants or second order terms discarded in the asymptotic analysis of the algorithms, which reduces effectiveness of some algorithms in applications.
