Deterministic Blind Rendezvous in Cognitive Radio Networks

Sixia Chen, Alexander Russell, Abhishek Samanta, Ravi Sundaram

TL;DR

This paper presents a novel deterministic algorithm for "blind rendezvous" in cognitive radio networks, enabling devices to find each other without prior coordination. The proposed method significantly improves rendezvous time, especially for networks with many channels but limited device capabilities, and offers a conceptually simpler approach than previous solutions.

What Problem Does This Paper Address?

Cognitive radio networks aim to dynamically share spectrum, but this introduces a fundamental challenge: how do devices (agents) discover each other in the first place? This is known as the "blind rendezvous problem." Agents have no shared infrastructure, no prior knowledge of each other, and must operate under several constraints:

  • Asymmetry: Each agent can only access a subset of available channels. Rendezvous is only possible if their channel subsets overlap.
  • Asynchrony: Agents don't have a perfectly synchronized clock. They might "wake up" at different times, and their schedules need to account for this relative shift.
  • Anonymity: Agents don't have unique identities. Their channel-hopping schedules must depend solely on their own available channels, not on any specific identifier.

Previous work had established deterministic algorithms for this problem, but they often resulted in high rendezvous times, particularly in scenarios with many channels or limited device capabilities. This paper aims to provide a more efficient and conceptually simpler deterministic solution.

Methods

The core of the paper's contribution lies in a new construction for deterministic channel-hopping schedules. The approach is built upon several key ideas:

  • Edge Coloring of a Linear Poset: For the fundamental case where agents have access to only two channels (effectively representing an edge in a linear order of channels), the authors leverage a 2-Ramsey edge coloring of a linear poset. This coloring ensures that no two consecutive channel hops by different agents form a monochromatic path, guaranteeing rendezvous.
  • Mapping to Balanced, Strictly Catalan, 2-Maximal Strings: A crucial step involves mapping binary strings (representing channel hop sequences) to a specific type of string that is balanced, strictly Catalan, and 2-maximal. This mapping is achieved through a series of transformations, including the "Knuth mapping" and further manipulations to satisfy the desired properties. These properties are essential for ensuring rendezvous in both synchronous and asynchronous settings.
  • Cyclic Schedules and Epochs: For the general case with arbitrary channel subsets, the authors construct schedules by dividing time into "epochs." Within each epoch, they utilize the size-two channel rendezvous construction. The use of cyclic schedules and the Chinese Remainder Theorem helps manage the asynchronous nature of the problem.
  • Deterministic Amplification (for one-bit beacon): In a variation of the problem where agents have access to a shared "one-bit random beacon," the authors employ techniques like min-wise independent permutations and "walking on an expander graph" to achieve highly efficient rendezvous times.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of Structured Mappings: The paper demonstrates how carefully constructed mappings between binary strings and specific types of sequences (balanced, Catalan, etc.) can be instrumental in designing efficient rendezvous schedules. These mappings encode the necessary properties for guaranteed rendezvous.
  • Leveraging Graph Theory for Scheduling: The use of edge coloring on a linear poset is a clever way to translate a scheduling problem into a combinatorial problem with known theoretical underpinnings (Ramsey theory).
  • Asynchronous Rendezvous as a Shifted Synchronous Problem: The authors show that asynchronous rendezvous can often be handled by considering shifted versions of synchronous schedules, simplifying the analysis.
  • The "One-Bit Beacon" Advantage: The introduction of a simple shared random bit dramatically reduces the required rendezvous time, highlighting the impact of even minimal shared resources.

Key Results

  • Improved Asynchronous Rendezvous Time: The paper presents an algorithm that guarantees asynchronous blind rendezvous in $O(|S_i||S_j|\log\log n)$ time for agents $A_i$ and $A_j$ with channel subsets $S_i$ and $S_j$, respectively. This is a significant improvement over previous $O(n^2)$ or $O(n^3)$ bounds, especially when channel subsets are small.
  • Optimal Symmetric Rendezvous: For the symmetric case (where all agents have the same channel subset), the algorithm achieves $O(1)$ rendezvous time, a substantial improvement over the previous $O(n)$ bound.
  • Lower Bounds: The paper establishes non-trivial lower bounds, including $\Omega(\log\log n)$ for synchronous rendezvous with constant-sized channel subsets and $\Omega(k^2)$ for asynchronous rendezvous with channel subsets of size $k$. These bounds demonstrate the tightness of their constructions in certain scenarios.
  • One-Bit Beacon Rendezvous: With a one-bit beacon, asynchronous rendezvous is achieved with high probability in $O(|S_i| + |S_j| + \log n)$ time.

Limitations and Future Work

  • Approximation for Graphical Rendezvous: The appendix discusses a 0.439-approximation algorithm for a related problem (maximizing rendezvous pairs in a single round for the graphical case), indicating that achieving optimal solutions for all variants might be challenging.
  • Complexity of General n-Schedules: While the paper provides an $O(|A||B|\log\log n)$ bound for general overlapping subsets, the construction involves selecting primes and managing epochs, which might have practical implementation complexities.
  • Future Work: The paper suggests exploring the "one bit beacon" scenario further and hints at the possibility of deterministic amplification techniques for achieving better performance guarantees. The authors also note that a precise understanding of $R_a(n,k)$ doesn't directly yield general $n$-schedules, suggesting further work in stitching together schedules for different subset sizes.

Summary updated

Abstract

Blind rendezvous is a fundamental problem in cognitive radio networks. The problem involves a collection of agents (radios) that wish to discover each other in the blind setting where there is no shared infrastructure and they initially have no knowledge of each other. Time is divided into discrete slots; spectrum is divided into discrete channels, $\{1,2,..., n\}$. Each agent may access a single channel in a single time slot and we say that two agents rendezvous when they access the same channel in the same time slot. The model is asymmetric: each agent $A_i$ may only use a particular subset $S_i$ of the channels and different agents may have access to different subsets of channels. The goal is to design deterministic channel hopping schedules for each agent so as to guarantee rendezvous between any pair of agents with overlapping channel sets. Two independent sets of authors, Shin et al. and Lin et al., gave the first constructions guaranteeing asynchronous blind rendezvous in $O(n^2)$ and $O(n^3)$ time, respectively. We present a substantially improved construction guaranteeing that any two agents, $A_i$, $A_j$, will rendezvous in $O(|S_i| |S_j| \log\log n)$ time. Our results are the first that achieve nontrivial dependence on $|S_i|$, the size of the set of available channels. This allows us, for example, to save roughly a quadratic factor over the best previous results in the important case when channel subsets have constant size. We also achieve the best possible bound of $O(1)$ time for the symmetric situation; previous works could do no better than $O(n)$. Using the probabilistic method and Ramsey theory we provide evidence in support of our suspicion that our construction is asymptotically optimal for small size channel subsets: we show both a $c |S_i||S_j|$ lower bound and a $c \log\log n$ lower bound when $|S_i|, |S_j| \leq n/2$.
BibTeX
@inproceedings{chen2014deterministic,
  author = {Sixia Chen and Alexander Russell and Abhishek Samanta and Ravi Sundaram},
  title = {{Deterministic Blind Rendezvous in Cognitive Radio Networks}},
  booktitle = {ICDCS},
  year = {2014},
  doi = {10.1109/icdcs.2014.44},
}
Figure