Neighbor Discovery for Wireless Networks via Compressed Sensing

Lei Zhang, Jun Luo, Dongning Guo

Abstract

This paper investigates the challenge of neighbor discovery in wireless networks, where each node must identify the Network Interface Addresses (NIAs) of all nodes within a single hop. The authors propose a novel paradigm called "Compressed Neighbor Discovery," which allows all nodes to simultaneously discover their respective neighborhoods within a single transmission frame, typically spanning only a few thousand symbol epochs. By assigning each node a unique on-off signature, nodes can transmit simultaneously; despite being half-duplex, nodes observe a superposition of their neighbors' signatures during their own "off" slots. Identifying neighbors then becomes a sparse recovery problem. The study evaluates two schemes: one using random on-off signatures with group testing, and another using deterministic second-order Reed-Muller codes with a sub-linear chirp decoding algorithm. The latter demonstrates superior SNR performance and scalability, capable of handling address spaces as large as $2^{48}$ (standard IEEE 802.11 MAC addresses), making it significantly more efficient than conventional random-access discovery.

Introduction

In mobile ad hoc networks (MANETs) and dense cellular deployments like femtocells, the ability for a node to quickly and accurately identify its neighbors is a prerequisite for routing and network coordination. Traditionally, this "neighbor discovery" process has relied on random-access protocols where nodes transmit their identities at random intervals, hoping to avoid collisions. However, as network density increases, these traditional methods suffer from high overhead, frequent collisions, and poor scalability.

This paper introduces a paradigm shift: instead of avoiding collisions, it leverages them. By treating the simultaneous transmission of node identities as a compressed sensing problem, the proposed method—Compressed Neighbor Discovery (CND)—enables a network to identify all neighbors in a single, efficient frame.

The Problem with Random Access

Current discovery protocols, such as the "birthday" algorithm or standard IEEE 802.11 discovery, are inherently inefficient. In these schemes, nodes must retransmit over many frames with random delays to ensure a successful, collision-free announcement. This process often requires hundreds of frames and significant overhead for preambles and parity checks. As the number of neighbors grows, the time required for discovery increases exponentially, creating a bottleneck for highly mobile or dense networks.

Compressed Neighbor Discovery (CND)

The core innovation of CND is the use of unique "on-off signatures." Every potential node in the network is assigned a specific sequence of pulses and silences.

Simultaneous Transmission and Half-Duplex Constraints

Unlike traditional methods, CND encourages all nodes to transmit their signatures simultaneously. A significant challenge in wireless design is the half-duplex nature of most radios—they cannot listen while they are transmitting. CND overcomes this by ensuring signatures are sparse. A node listens to the channel during its "off" slots, capturing a partial superposition of its neighbors' signatures.

Sparse Recovery

Because the number of actual neighbors is very small compared to the total possible address space (e.g., 30 neighbors vs. $2^{48}$ possible MAC addresses), the discovery problem is mathematically "sparse." The signal received during a node's off-slots is a linear combination of the signatures of its active neighbors. This allows the node to use compressed sensing algorithms to reconstruct the list of neighbor NIAs from the combined signal.

Proposed Decoding Schemes

The paper evaluates two distinct approaches to solving the sparse recovery problem:

  1. Random Signatures with Group Testing: This scheme uses pseudo-random on-off patterns. Decoding is performed via a noncoherent detection algorithm based on group testing (a "t-tolerance" test). While conceptually simple, this approach has $O(N)$ complexity, where $N$ is the size of the address space. This makes it impractical for the massive address spaces used in modern networking.
  2. Reed-Muller (RM) Codes with Chirp Decoding: To achieve true scalability, the authors utilize deterministic second-order Reed-Muller codes. The algebraic structure of these codes allows for a "chirp decoding" algorithm with sub-linear complexity. This means a node can identify its neighbors among billions of possibilities without an exhaustive search, making it feasible for 48-bit IEEE 802.11 MAC addresses.

Key Insights

  • Collisions as Information: CND redefines collisions. Rather than a failure state, the superposition of signals provides the measurement vector necessary to solve the recovery problem.
  • Phase Randomization: To prevent destructive interference (where two neighbors' signals cancel each other out due to opposite phases), the authors implement phase randomization for each pulse in the signature, significantly improving discovery reliability.
  • Computational Efficiency: The RM-based scheme is not only faster to decode but also requires a much lower Signal-to-Noise Ratio (SNR) to achieve the same error performance as the random signature approach.

Performance Results

Simulation results, using Poisson Point Processes for node distribution and realistic Rayleigh fading models, highlight the efficiency of CND:

  • Speed: For a neighborhood of 30 nodes, the RM-based scheme completes discovery in approximately 4,000 symbols within a single frame. In contrast, traditional random access would require over 5,000 symbols spread across more than 500 frames.
  • Latency: When compared to IEEE 802.11g, CND could potentially complete the discovery process in 30ms, whereas 802.11g would require at least 165ms—a 5x improvement in speed.
  • Reliability: The RM/Chirp scheme achieves a target error rate of 0.2% even in large address spaces, demonstrating robustness that scales to global networking standards.

Limitations and Future Work

While CND offers a significant leap in efficiency, it requires nodes to be roughly symbol-synchronized. The authors suggest this could be managed via GPS or distributed consensus, though it remains an operational requirement. Additionally, the current model assumes a relatively static channel during the discovery frame; future research may explore how high-speed mobility and Doppler shifts affect signature reconstruction. Extensions into multicarrier systems like OFDM are also proposed to further enhance throughput.

Conclusion

By applying compressed sensing to the fundamental problem of neighbor discovery, this research provides a scalable, high-speed alternative to aging random-access protocols. The use of Reed-Muller codes and sub-linear decoding ensures that even as address spaces and network densities grow, discovery remains a fast, single-frame operation.

Summary updated

Abstract

This paper studies the problem of neighbor discovery in wireless networks, namely, each node wishes to discover and identify the network interface addresses (NIAs) of those nodes within a single hop. A novel paradigm, called compressed neighbor discovery is proposed, which enables all nodes to simultaneously discover their respective neighborhoods with a single frame of transmission, which is typically of a few thousand symbol epochs. The key technique is to assign each node a unique on-off signature and let all nodes simultaneously transmit their signatures. Despite that the radios are half-duplex, each node observes a superposition of its neighbors' signatures (partially) through its own off-slots. To identify its neighbors out of a large network address space, each node solves a compressed sensing (or sparse recovery) problem. Two practical schemes are studied. The first employs random on-off signatures, and each node discovers its neighbors using a noncoherent detection algorithm based on group testing. The second scheme uses on-off signatures based on a deterministic second-order Reed-Muller code, and applies a chirp decoding algorithm. The second scheme needs much lower signal-to-noise ratio (SNR) to achieve the same error performance. The complexity of the chirp decoding algorithm is sub-linear, so that it is in principle scalable to networks with billions of nodes with 48-bit IEEE 802.11 MAC addresses. The compressed neighbor discovery schemes are much more efficient than conventional random-access discovery, where nodes have to retransmit over many frames with random delays to be successfully discovered.
BibTeX
@inproceedings{zhang2012neighbor,
  author = {Lei Zhang and Jun Luo and Dongning Guo},
  title = {{Neighbor Discovery for Wireless Networks via Compressed Sensing}},
  booktitle = {Performance},
  year = {2012},
  doi = {10.1016/j.peva.2012.05.003},
}
Figure