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

Lei Zhang*, Dongning Guo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 International Symposium on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011
Pages154-160
Number of pages7
DOIs
StatePublished - Jul 26 2011
Event2011 International Symposium of on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011 - Princeton, NJ, United States
Duration: May 9 2011May 13 2011

Publication series

Name2011 International Symposium on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011

Other

Other2011 International Symposium of on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011
CountryUnited States
CityPrinceton, NJ
Period5/9/115/13/11

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Communication

Fingerprint Dive into the research topics of 'Neighbor discovery in wireless networks using compressed sensing with Reed-Muller codes'. Together they form a unique fingerprint.

  • Cite this

    Zhang, L., & Guo, D. (2011). Neighbor discovery in wireless networks using compressed sensing with Reed-Muller codes. In 2011 International Symposium on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011 (pp. 154-160). [5930008] (2011 International Symposium on Modeling and Optimization of Mobile, Ad Hoc, and Wireless Networks, WiOpt 2011). https://doi.org/10.1109/WIOPT.2011.5930008