text: A novel low-complexity wireless neighbor discovery scheme, referred to as sparse orthogonal frequency division multiplexing (sparse-OFDM) is proposed. One area of application is the "Internet of Things" (IoT). The number of devices is very large while every device accesses the network with a small probability, so the number of active devices in a frame is much smaller than the total local device population. Sparse OFDM is a one-shot transmission scheme with low complexity, which exploits both the parallel channel access offered by OFDM and the bursty nature of transmissions. When the transmission delay of each device is an integer number of symbol intervals, analysis and simulation show that sparse OFDM enables successful asynchronous neighbor discovery using a much smaller code length than random access schemes.
  @cite_14: We examine the problem of determining which nodes are neighbors of a given one in a wireless network. We consider an unsupervised network operating on a frequency-flat Gaussian channel, where K + 1 nodes associate their identities to nonorthogonal signatures, transmitted at random times, synchronously, and independently. A number of neighbor-discovery algorithms, based on different optimization criteria, are introduced and analyzed. Numerical results show how reduced-complexity algorithms can achieve a satisfactory performance.
  @cite_4: In this paper, we design a fast and efficient energy-based and asynchronous neighbor discovery protocol for the Internet of Things (IoT). In our solution, we relax the assumption of frame-level synchronization. We formulate a novel asynchronous group testing scheme and apply it to the neighbor discovery problem. We then show that our proposed scheme is able to detect the set of K active neighbors1 among a network of n nodes with codeword length and decoding complexity of Θ(K log (K) log (n)). Finally, we provide extensive simulation results to verify our theoretical guarantees.
  @cite_9: A novel solution is proposed to undertake a frequent task in wireless networks, which is to let all nodes broadcast information to and receive information from their respective one-hop neighboring nodes. The contribution in this paper is twofold. First, as each neighbor selects one message-bearing codeword from its unique codebook for transmission, it is shown that decoding their messages based on a superposition of those codewords through the multiaccess channel is fundamentally a problem of compressed sensing. In the case where each message is designed to consist of a small number of bits, an iterative algorithm based on belief propagation is developed for efficient decoding. Second, to satisfy the half-duplex constraint, each codeword consists of randomly distributed on-slots and off-slots. A node transmits during its on-slots and listens to its neighbors only through its own off-slots. Over one frame interval, each node broadcasts a message to its neighbors and simultaneously receives the superposition of neighbors' signals through its own off-slots and then decodes all messages. The proposed solution fully exploits the multiaccess nature of the wireless medium and addresses the half-duplex constraint at the fundamental level. In a network consisting of Poisson distributed nodes, numerical results demonstrate that the proposed scheme often achieves several times the rate of slotted ALOHA and CSMA with the same packet error rate.
  @cite_3: One challenging future application in digital communications is the wireless uplink transmission in sensor networks. This application is characterized by sporadic transmissions by a large number of sensors over a random multiple access channel. To reduce control signaling overhead, we propose that sensors do not transmit their activity states; instead sensor activity is detected at the receiver. As sensors have low activity probabilities, the multi-user vector is in general sparse. This enables Compressive Sensing (CS) detectors to perform joint Multi-User Detection (MUD) of activity and data, by exploiting the sparsity. Since sensors are either active or inactive for several symbol durations, block-wise CS detection can be applied to improve the activity detection. In this paper, we introduce blockwise greedy CS MUD, compare it to symbol-wise greedy CS MUD, and show that statistically independent channels for each symbol further improve the activity detection for block-wise CS detection. Herein, we use Code Division Multiple Access (CDMA) as a multiple access scheme.
  @cite_24: Fast and efficient discovery of all neighboring nodes by a node new to a neighborhood is critical to the deployment of wireless ad hoc networks. Different than the conventional ALOHA-type random access discovery schemes, this paper assumes that all nodes in the neighborhood simultaneously send their unique on-off signatures known to the receive node. In particular, a transmitter does not transmit any energy during an ldquooffrdquo mini-slot in its signature sequence. The received signal can be viewed as the outcome of a sequence of tests over the mini-slots, where the outcome of a test is positive if there is energy at the corresponding mini-slot from at least one neighbor, and negative if none of the neighboring nodes transmits energy during the mini-slot. The neighbor discovery problem is thus equivalent to a classical group testing problem. Two practical and scalable detection algorithms are developed from the group testing viewpoint. Unlike some previous neighbor discovery schemes using coherent multiuser detection, which are difficult to implement due to lack of training, the proposed scheme requires only non-coherent energy detection. The proposed algorithms are shown to achieve faster and more reliable discovery than existing random access schemes.
  @cite_19: The number of active users in code-division multiple access (CDMA) systems is often much lower than the spreading gain. The present paper exploits fruitfully this a priori information to improve performance of multiuser detectors. A low-activity factor manifests itself in a sparse symbol vector with entries drawn from a finite alphabet that is augmented by the zero symbol to capture user inactivity. The non-equiprobable symbols of the augmented alphabet motivate a sparsity-exploiting maximum a posteriori probability (S-MAP) criterion, which is shown to yield a cost comprising the l2 least-squares error penalized by the p-th norm of the wanted symbol vector (p = 0, 1, 2). Related optimization problems appear in variable selection (shrinkage) schemes developed for linear regression, as well as in the emerging field of compressive sampling (CS). The contribution of this work to such sparse CDMA systems is a gamut of sparsity-exploiting multiuser detectors trading off performance for complexity requirements. From the vantage point of CS and the least-absolute shrinkage selection operator (Lasso) spectrum of applications, the contribution amounts to sparsity-exploiting algorithms when the entries of the wanted signal vector adhere to finite-alphabet constraints.
  @cite_20: This two-part paper considers an uplink massive device communication scenario in which a large number of devices are connected to a base station (BS), but user traffic is sporadic so that in any given coherence interval, only a subset of users is active. The objective is to quantify the cost of active user detection and channel estimation and to characterize the overall achievable rate of a grant-free two-phase access scheme in which device activity detection and channel estimation are performed jointly using pilot sequences in the first phase and data is transmitted in the second phase. In order to accommodate a large number of simultaneously transmitting devices, this paper studies an asymptotic regime where the BS is equipped with a massive number of antennas. The main contributions of Part I of this paper are as follows. First, we note that as a consequence of having a large pool of potentially active devices but limited coherence time, the pilot sequences cannot all be orthogonal. However, despite the nonorthogonality, this paper shows that in the asymptotic massive multiple-input multiple-output regime, both the missed device detection and the false alarm probabilities for activity detection can always be made to go to zero by utilizing compressed sensing techniques that exploit sparsity in the user activity pattern. Part II of this paper further characterizes the achievable rates using the proposed scheme and quantifies the cost of using nonorthogonal pilot sequences for channel estimation in achievable rates.
  @cite_11: 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.
summary: Neighbor discovery can be formulated as multiuser detection from the perspective of physical layer processing @cite_14 . Due to the bursty traffic patterns, the number of active devices is typically orders of magnitude smaller than the total local device population. Based on this crucial observation, low-complexity neighbor discovery algorithms inspired by compressed sensing were proposed @cite_19 @cite_3 @cite_11 @cite_9 @cite_20 . These algorithms can reduce the code length by over 50 Noncoherent neighbor discovery based on energy detection can be formulated as the classical group testing problem @cite_24 . By utilizing the sparsity nature, neighbor discovery can be achieved efficiently using a low transmission overhead. A related study applies sparse graph codes to asynchronous group testing @cite_4 , where the required code length is larger than that for our proposed scheme.