Neighbor discovery in wireless networks using compressed sensing with Reed-Muller codes

A novel scheme for full-duplex neighbor discovery in wireless networks is proposed. The scheme allows all nodes to simultaneously discover one-hop neighbors and identify their network interface addresses (NIAs) within a single frame of transmission, which typically consists of no more than a few thousand symbols. The key technique is to assign each node a unique on-off signature derived from a second-order Reed-Muller code and let all nodes simultaneously transmit their signatures. Despite that the radio is half-duplex, each node observes a superposition of its neighbors' signatures (partially) through its own off-slots. To identify its (small number of) neighbors out of a large network address space, each node solves a compressed sensing (or sparse recovery) problem using a chirp reconstruction algorithm. A network of over one million Poisson distributed nodes (with 20-bit NIAs) is studied numerically, where each node has 30 neighbors on average, and the channel between each pair of nodes is subject to path loss and Rayleigh fading. Within a single frame of 4,096 symbols, nodes can discover their respective neighbors with on average 99.9% accuracy at 16 dB signal-to-noise ratio (SNR). The algorithm is scalable to networks of virtually any size of practical interest due to its sub-linear complexity. The new scheme requires much fewer transmissions than conventional random-access discovery schemes to achieve the same performance.