Neighbor discovery is an important first step in the initialization of a wireless ad hoc network. In this paper, we design and analyze several algorithms for neighbor discovery in wireless networks. Starting with a single-hop wireless network of $n$ nodes, we propose a $Theta(nln n)$ ALOHA-like neighbor discovery algorithm when nodes cannot detect collisions, and […]