Optimal measurement matrices for neighbor discovery

We study the problem of neighbor discovery in which each node desires to detect nodes within a single hop. Each node is assigned a unique signature known by all other nodes. The problem can be considered as a compressed sensing problem. We propose a explicit-non-random-construction for the signatures. Further, we suggest the basis pursuit to detect the neighbors and offer a guarantee for its performance. Specifically, we show that the average number of errors can be made arbitrary small as the number of nodes in the network grows. Our result does not depend on the density of the network, i.e., how the average number of neighbors scales with respect to the total number of nodes.