Abstract: Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. Neighbor discovery in MPR networks is studied that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, a simple Aloha-like algorithm is analyzed and shows that it takes time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. Two adaptive neighbor discovery algorithms is designed that dynamically adjust the transmission probability for each node. The friend algorithms yield improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal.

Keywords: Wireless Networks, Multi packet Reception, Network Management, Neighbor Discovery, Friend Algorithm.