On multipacket reception based neighbor discovery in low-duty-cycle wireless sensor networks

Neighbor Discovery (ND) plays an important role in the initialization phase of wireless sensor networks. In real deployments, sensor nodes may not always be awake due to limited power supply, which forms low-duty-cycle networks. Existing researches on the problem of ND in low-duty-cycle networks are all based on the assumption that a receiver can receive only one packet successfully at a time. k-Multipacket Reception (MPR) techniques (i.e., k (k   ≥ 2) packets can be successfully received at a time) have shown their significance in improving packet transmission. However, how MPR can benefit the problem of ND is still unknown. In this paper, we are the first to discuss the problem of ND in low-duty-cycle networks with MPR. Specifically, we first present a novel ALOHA-like protocol, and show that the expected time to discover all n−1n−1 neighbors is O(nlognloglognk) by reducing the problem to a generalized form of the classic K Coupon Collector’s Problem  . Second, we show that when there is a feedback mechanism to inform a node whether its transmission is successful or not, ND can be finished in time O(nloglognk). Third, we point out that lacking of knowledge of n results in a factor of two slowdown in the two protocols proposed. We also discuss some extensions related to the protocol’s design and different MPR models. Finally, we evaluate the ND protocols introduced in this paper, and compare their performance with the analysis results.