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_22: In this paper, we address two problems associated with static ad hoc wireless networks; methods of saving energy during a deployment of the nodes, and efficient methods of performing adjacent neighbor discovery. To meet these goals we introduce a family of "birthday protocols"which use random independent transmissions to discover adjacent nodes. Various modes of the birthday protocol are used to solve the two problems. We provide a mathematical model and analysis of two modes of the protocol and are led to a third mode which is the probabilistic analog of the deterministic round robin scheduling algorithm. We show by analysis and simulation that the birthday protocols are a promising tool for saving energy during the deployment of an ad hoc network as well as an efficient and flexible means of having the nodes discover their neighbors
  @cite_7: This paper proposes FlashLinQ--a synchronous peer-to-peer wireless PHY MAC network architecture. FlashLinQ leverages the fine-grained parallel channel access offered by OFDM and incorporates an analog energy-level-based signaling scheme that enables signal-to-interference ratio (SIR)-based distributed scheduling. This new signaling mechanism, and the concomitant scheduling algorithm, enables efficient channel-aware spatial resource allocation, leading to significant gains over a CSMA CA system using RTS CTS. FlashLinQ is a complete system architecture including: 1) timing and frequency synchronization derived from cellular spectrum; 2) peer discovery; 3) link management; and 4) channel-aware distributed power, data rate, and link scheduling. FlashLinQ has been implemented for operation over licensed spectrum on a digital signal processor field-programmable gate array (DSP FPGA) platform. In this paper, we present FlashLinQ performance results derived from both measurements and simulations.
  @cite_1: In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in which n nodes are located in a unit cube uniformly at random and each node is assigned one of K colors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm, and we therefore consider a natural online greedy coloring algorithm first proposed by Ko and Rubenstein in 2005. We prove two key results: 1) with just log n log log n colors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when K = Ω(log n), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility.
  @cite_0: We consider the problem of determining, in a distributed, asynchronous and scalable manner, what nodes are ''neighbors'' in a wireless network. Neighbor discovery is an important enabler of network connectivity and energy conservation. An asynchronous, probabilistic neighbor discovery algorithm is presented that permits each node in the network to develop a list of its neighbors, which may be incomplete. The algorithm is analyzed and parameter settings are derived which maximize the fraction of neighbors discovered in a fixed running time. A companion distributed algorithm is also described which allows all the nodes in the network to execute that neighbor discovery algorithm without the need to agree on a common start time.
  @cite_23: We consider the problem of neighbor discovery in static wireless ad hoc networks with directional antennas. We propose several probabilistic algorithms in which nodes perform random, independent transmissions to discover their one-hop neighbors. Our neighbor discovery algorithms are classified into two groups, viz. Direct-Discovery Algorithms in which nodes discover their neighbors only upon receiving a transmission from their neighbors and Gossip-based algorithms in which nodes gossip about their neighbors' location information to enable faster discovery. We first consider the operation of these algorithms in a slotted, synchronous system and mathematically derive their optimal parameter settings. We show how to extend these algorithms for an asynchronous system and describe their optimal design. Analysis and simulation of the algorithms show that nodes discover their neighbors much faster using gossip-based algorithms than using direct-discovery algorithms. Furthermore, the performance of gossip-based algorithms is insensitive to an increase in node density. The efficiency of a neighbor discovery algorithm also depends on the choice of antenna beamwidth. We discuss in detail how the choice of beamwidth impacts the performance of the discovery process and provide insights into how nodes can configure their beamwidths.
  @cite_2: Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical Coupon Collector's Problem . Consequently, we show that each node discovers all its @math neighbors in an expected time equal to @math , for some constant @math . When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a @math improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing @math results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.
  @cite_13: Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery between duty-cycled mobile devices. Each node is duty-cycled, i.e., its radio may only be active for a small fraction of the time. The duty cycles of the nodes can be the same or different, leading to symmetric or asymmetric cases of the neighbor discovery problem. In addition, the setting is asynchronous, i.e., clocks of different nodes may not be synchronized. Most existing studies assume an integer model (where time proceeds in discrete steps); two recent studies break away from this assumption, which allows them to develop significantly more efficient schemes. Our study improves the state-of-the-art in three main fronts. Firstly, we develop a generalized non-integer model (where time is continuous) that permits unified treatment of the assumptions in existing studies. We also provide a reduction that transforms any schedule in the basic integer model to a corresponding schedule in the generalized non-integer model while improving the performance by a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. Thirdly, we establish a new family of lower bounds for the best achievable latency guarantee in the non-integer model. They are applicable to both symmetric and asymmetric settings, and encompass the lower bounds for the integer model as special cases. Finally, we develop a novel optimal construction based on Sidon sets for the symmetric setting. Our approach differs from the approaches taken by all existing studies, and provides a new direction for constructing neighbor discovery schedules.
summary: Network layer protocol designs for neighbor discovery can be categorized into randomized and deterministic algorithms. The main objective is to optimize random access probability or the transmit schedule of each device such that the system throughput is maximized @cite_22 @cite_0 @cite_23 @cite_2 @cite_13 . Instead of purely avoiding collision, the FlashLinQ technology developed by Qualcomm assigns channels based on signal-to-interference ratios and achieves superior performance over carrier sense multiple access with collision avoidance (CSMA CA) systems @cite_1 @cite_7 . The neighbor discovery algorithm proposed in this paper can be regarded as a physical layer technique, which can be optimized with the network layer protocols to improve the system performance.