Optimizing average-maximum TTR trade-off for cognitive radio rendezvous

Lin Chen, Shuyu Shi, Kaigui Bian, Yusheng Ji

TL;DR

In cognitive radio networks, finding a common channel to communicate (rendezvous) involves a strict trade-off between average and maximum delay. This paper introduces a clever hybrid channel hopping framework that borrows "wake-up schedules" from wireless sensor networks to interleave random and sequence-based hopping. The resulting protocols guarantee a bounded maximum time-to-rendezvous (MTTR) and high channel diversity, while drastically reducing the average time-to-rendezvous (ATTR).

What Problem Does This Paper Address?

In Cognitive Radio (CR) networks, Secondary Users (SUs) must find each other on a common frequency channel before they can communicate—a process known as rendezvous. Because Primary (licensed) Users might occupy certain channels, SUs use Channel Hopping (CH) protocols to search for each other.

Designing these protocols involves a frustrating trade-off:

  1. Random CH protocols yield a fantastic Average Time-To-Rendezvous (ATTR), but they offer no worst-case guarantees. Two users might theoretically never find each other (infinite Maximum Time-To-Rendezvous, or MTTR) and might not explore a diverse set of channels.
  2. Sequence-based CH protocols use deterministic mathematical sequences to guarantee that two users will eventually meet (bounded MTTR) across multiple different channels (high rendezvous diversity). However, this mathematical rigidity forces a much longer average wait time (high ATTR).

The authors ask: Can we design a protocol that achieves the low ATTR of random hopping while preserving the bounded MTTR and high diversity of sequence-based hopping?

Methods

To solve this, the authors look to an adjacent field: Wireless Sensor Networks (WSNs). In WSNs, nodes use binary "wake-up schedules" (strings of 1s and 0s) to alternate between sleeping and waking to save energy, designed so that any two nodes' awake times will eventually overlap regardless of clock drift.

The authors map this concept to the CR rendezvous problem:

  • "Awake" = Sequence-Based Hopping: When the wake-up schedule bit is 1, the radio hops to the channel dictated by a standard deterministic CH protocol (like CRSEQ or Jump-Stay).
  • "Asleep" = Random Hopping: When the wake-up schedule bit is 0, the radio hops to a completely random channel.

To make the math work, they introduce a Padding Scheme. This slightly increases the total number of channels $N$ to a new number $N'$ to ensure that the period length of the deterministic CH sequence and the length of the wake-up schedule are co-prime. This guarantees that the two sequences cycle through all possible combinations without getting stuck in a repetitive loop.

Datasets

Not discussed in the paper. The authors evaluate their framework using synthetic network simulations rather than empirical datasets. The simulations modeled 11 frequency channels, 20 pairs of nodes, and varying Primary User (PU) traffic loads (25% and 50% channel occupancy).

Key Insights and Ideas

  • Cross-Domain Inspiration: By treating deterministic channel hopping as an "energy-expensive" operation that only needs to happen periodically, the authors successfully repurposed WSN neighbor-discovery math to solve a cognitive radio latency problem.
  • Preserving the Upper Bound: Because the underlying wake-up schedules mathematically guarantee an overlap between any two asynchronous clocks, the deterministic CH sequences are guaranteed to eventually align. Thus, the strict upper bound on MTTR is perfectly preserved.
  • Stochastic Shortcuts: Injecting random hops into the "gaps" (the 0s in the schedule) acts as a shortcut. While the deterministic sequence acts as a safety net, the random hops frequently allow the radios to stumble into each other much earlier, dragging the expected ATTR down significantly.

Key Results

The authors applied their interleaving framework to two standard deterministic protocols: CRSEQ and Jump-Stay (JS).

  • Improved Average Latency: As the "duty cycle" (the ratio of 1s to 0s in the schedule) decreased, the ATTR dropped significantly. Protocols with a 5/14 duty cycle (mostly random hopping) achieved vastly superior average rendezvous times compared to the unmodified baseline protocols (which effectively have a duty cycle of 1).
  • Better Worst-Case Latency: Counterintuitively, the hybrid protocols actually improved the empirical Maximum TTR in simulations compared to the baselines, because the random slots provided early rendezvous opportunities even in worst-case clock drift scenarios.
  • Maintained Diversity: The rendezvous channel diversity rate (the ability to meet on various different channels to avoid localized jamming or congestion) was preserved and even slightly improved by the introduction of stochastic hopping.

Limitations and Future Work

  • Slot Alignment Assumption: The paper assumes that time-slot boundaries between two independent nodes are roughly aligned. While they justify this by doubling the link establishment time ($2t_0$) to ensure sufficient overlap, severe synchronization issues in the real world could complicate the theoretical guarantees.
  • Padding Overhead: The padding scheme requires artificially increasing the channel pool $N$ to find a co-prime integer. While trivial for small $N$, this could introduce slight inefficiencies if the sensible channel set is already very large.
  • Future Work: While not explicitly detailed in a dedicated section, the natural next steps for this research would involve testing the hybrid protocols on physical Software Defined Radios (SDRs) to observe how hardware switching delays and real-world RF interference impact the theoretical ATTR and MTTR bounds.

Summary updated

Abstract

In cognitive radio (CR) networks, “TTR”, a.k.a. time-to-rendezvous, is one of the most important metrics for evaluating the performance of a channel hopping (CH) rendezvous protocol, and it characterizes the rendezvous delay when two CRs perform channel hopping. There exists a trade-off of optimizing the average or maximum TTR in the CH rendezvous protocol design. On one hand, the random CH protocol leads to the best “average” TTR without ensuring a finite “maximum” TTR (two CRs may never rendezvous in the worst case), or a high rendezvous diversity (multiple rendezvous channels). On the other hand, many sequence-based CH protocols ensure a finite maximum TTR (upper bound of TTR) and a high rendezvous diversity, while they inevitably yield a larger average TTR. In this paper, we strike a balance in the average-maximum TTR trade-off for CR rendezvous by leveraging the advantages of both random and sequence-based CH protocols. Inspired by the neighbor discovery problem, we establish a design framework of creating a wake-up schedule whereby every CR follows the sequence-based (or random) CH protocol in the awake (or asleep) mode. Analytical and simulation results show that the hybrid CH protocols under this framework are able to achieve a greatly improved average TTR as well as a low upper-bound of TTR, without sacrificing the rendezvous diversity.
BibTeX
@inproceedings{chen2015optimizing,
  author = {Lin Chen and Shuyu Shi and Kaigui Bian and Yusheng Ji},
  title = {{Optimizing average-maximum TTR trade-off for cognitive radio rendezvous}},
  booktitle = {ICC},
  year = {2015},
  url = {https://openreview.net/forum?id=vWaQVBLuYQu},
}

Loading related content...

Figure