Neighbour Discovery in Wireless Networks with Multipacket Reception

Neighbor discovery is the first step in configuring and managing a wireless network. Many of the existing techniques on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. Motivated by the increasing prevalence of multi packet reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver in this paper. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Q?nln n k ? time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then come up with the design of two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms exhibit a Q?lnn? improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal. Ultimately, we analyze our algorithm in a multi-hop network setting. We show an upper bound of O?Dln n k ? for the Aloha-like algorithm has a performance which is at most a factor ln n worse than the optimal provided the maximum node degree is D. In addition to this, when D is large, we show that the adaptive algorithms are order optimal which means that have a running time of O?Dk? which matches the lower bound for the problem. I.INTRODUCTION Neighbor Discovery is one of the first steps in configuring and managing a wireless network. The output result obtained from neighbor discovery, is needed to support basic functionalities such as medium access and routing.This is nothing but the set of nodes that a wireless node can directly communicate with, In addition, this resultant data is needed by topology control and clustering algorithms to improve network performance. Due to its critical importance, neighbor discovery has received significant attention, and a number of studies have been devoted to this topic. Most studies, however, assume a single packet reception (SPR) model, i.e., a transmission is successful if and only if there are no other simultaneous transmissions. In contrast to prior literature, we study neighbor discovery in multipacket reception (MPR)