A Low-Complexity Algorithm for Neighbor Discovery in Wireless Networks

We study a neighbor discovery problem in wireless networks for which each node wishes to identify the so-called neighboring nodes within a single-hop communication. This problem can be optimally addressed using maximum a posteriori (MAP) estimation, but its implementation is notoriously difficult in practice. In this letter, we present a low-complexity algorithm consisting of two stages: 1) we solve such problem using LASSO estimator that is a convex relaxation of MAP estimator to encourage a sparse solution; and 2) we find a desired binary vector (e.g., indicator of neighbor nodes) by taking a “hard-decision” with threshold, carefully chosen by exploiting fading statistics. Finally, we provide some numerical results to confirm that the proposed algorithm performs quite well.