pith. sign in

arxiv: 1906.10424 · v1 · pith:DDBYLSDOnew · submitted 2019-06-25 · 💻 cs.IT · math.IT

ETTR Bounds and Approximation Solutions of Blind Rendezvous Policies in Cognitive Radio Networks with Random Channel States

Cheng-Shang Chang , Duan-Shin Lee , Yu-Lun Lin , Jen-Hung Wang This is my paper

Pith reviewed 2026-05-25 16:21 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords cognitive radio networksblind rendezvousexpected time-to-rendezvousmajorization orderingchannel selection policiesfast time-varying channelsslow time-varying channelsapproximation solutions
0
0 comments X

The pith

The optimal blind policy minimizes expected rendezvous time by always hopping the single best channel in fast time-varying models, while slow models admit ETTR bounds via majorization on exchangeable states.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper considers blind channel-hopping policies in cognitive radio networks where rendezvous success depends on unobservable channel states modeled as known stochastic processes. It establishes that in fast time-varying channels, where states are independent each slot, always selecting the best channel achieves the minimal expected time to rendezvous among all such policies. For slow time-varying channels where states persist, majorization ordering on exchangeable random variables produces lower and upper bounds on that expected time, which then support explicit approximation policies. The results carry over to any stationary joint distribution of the states. Readers care because rendezvous without prior coordination or observation is a basic requirement for spectrum sharing in dynamic wireless settings.

Core claim

Among the classes of the blind rendezvous policies that randomly hop on channels according to certain channel selection probabilities, the optimal channel selection policy that minimizes the expected time-to-rendezvous is the single selection policy that hops on the best channel all the time in the fast time-varying channel model. For the slow time-varying channel model, majorization ordering derives a lower bound and an upper bound for the ETTR under the assumption that the channel states are exchangeable random variables, from which various approximation solutions are proved. The results extend to general channel models where the joint distribution of the channel states is only assumed to

What carries the argument

Majorization ordering on exchangeable channel-state random variables to obtain lower and upper bounds on expected time-to-rendezvous for slow time-varying models.

If this is right

  • In fast time-varying channels the constant best-channel policy is optimal among all blind policies.
  • The majorization bounds directly enable proofs that certain approximation policies achieve ETTR within the derived interval.
  • The same bounding technique applies once the joint distribution is merely stationary rather than i.i.d. or constant.
  • Approximation solutions can be constructed explicitly from the lower and upper bounds without solving the full optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same majorization argument could be applied to other coordination tasks that rely on unobservable but exchangeable state variables.
  • Empirical checks on measured spectrum data would reveal how often the exchangeability assumption holds and how tight the resulting bounds are.
  • The bounding method may extend to rendezvous among more than two users by treating the multi-user state vector as exchangeable.
  • Connections to other partial-information scheduling problems, such as distributed medium access, could reuse the majorization step.

Load-bearing premise

The channel states are exchangeable random variables, which is invoked to apply majorization ordering for the ETTR bounds in the slow time-varying model.

What would settle it

An explicit joint distribution of channel states together with a mixed selection policy whose expected rendezvous time is strictly smaller than that of the constant best-channel policy under the fast time-varying (i.i.d.-per-slot) model would falsify the optimality claim.

Figures

Figures reproduced from arXiv: 1906.10424 by Cheng-Shang Chang, Duan-Shin Lee, Jen-Hung Wang, Yu-Lun Lin.

Figure 2
Figure 2. Figure 2: The ETTR (as a function of p1) with ρ = 0.3, r(1) = 1, and r(0) = 0.01, 0.001, respectively. ρ’s. It is interesting to see that the optimal p1 is very close to 1 when r(0) is either very small or very close to r(1). Such asymptotic results will be formally proved in the next section. 10-5 10-4 10-3 10-2 10-1 r(0) 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 optimal p 1 =0.1 =0.2 =0.3 =0.4 =0.5 =0.6 =0.7 … view at source ↗
Figure 3
Figure 3. Figure 3: The optimal p1 for r(0) ranging from 0.1 to 0.00001 with r(1) = 1. 5.2 An asymptotic (1 + )-approximation solution In this section, we show an asymptotic (1+)-approximation solution for the two-state slow time-varying channel model with N ≥ 2 channels. Note from the joint distribution in (24) that f(u) = E[ 1 PN i=1 r(Xi(0))ui ] = X 1 x1=0 · · · X 1 xN =0 1 PN i=1 r(xi)ui q(x1, x2, . . . , xN ) = X 1 x1=… view at source ↗
Figure 1
Figure 1. Figure 1: The ETTR (as a function of p1) with ρ = 0.9, r(1) = 1, and r(0) = 0.01, 0.001, respectively. In view of [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
read the original abstract

In this paper, we consider the multichannel rendezvous problem in cognitive radio networks (CRNs) where the probability that two users hopping on the same channel have a successful rendezvous is a function of channel states. The channel states are modeled by stochastic processes with joint distributions known to users. However, the exact state of a channel at any time is not observable. We first consider two channel models: (i) the fast time-varying channel model (where the channel states are assumed to be independent and identically distributed in each time slot), and (ii) the slow time-varying channel model (where the channel states remain unchanged over time). Among the classes of the blind rendezvous policies that randomly hop on channels according to certain channel selection probabilities, we show the optimal channel selection policy that minimizes the expected time-to-rendezvous (ETTR) is the single selection policy that hops on the ``best'' channel all the time in the fast time-varying channel model. However, for the slow time-varying channel model, it is much more difficult to find the optimal channel selection policy. By using the majorization ordering, we derive a lower bound and an upper bound for the ETTR under the assumption that the channel states are exchangeable random variables. Bases on these bounds, we then prove various approximation solutions. We then extend our results to general channel models where the joint distribution of the channel states is only assumed to be stationary in time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes blind rendezvous in cognitive radio networks where rendezvous success probability depends on unobservable channel states drawn from known joint distributions. For the fast time-varying (i.i.d.) model it claims that, among fixed-probability blind policies, the ETTR-minimizing policy is deterministic selection of the single best channel. For the slow time-varying model it invokes exchangeability of the state vector to apply majorization ordering and thereby obtain explicit lower and upper bounds on ETTR, from which approximation policies are derived; the results are then extended to the broader class of stationary (but not necessarily exchangeable) joint distributions.

Significance. If the derivations are correct, the work supplies the first explicit majorization-based bounds on ETTR for the slow model and a clean optimality characterization for the fast model. These results give theoretical grounding for policy design when channel quality is random and unobservable, and the use of majorization to produce parameter-free bounds is a methodological strength.

major comments (2)
  1. [slow time-varying model / extension paragraph] Abstract and slow-model section: the ETTR bounds and subsequent approximation guarantees are derived under the explicit exchangeability assumption via majorization ordering on the state vector. The manuscript then claims an extension to general stationary joint distributions; it is unclear whether the majorization inequalities continue to hold or whether only the approximation policies (but not the bounds) survive the relaxation. This distinction is load-bearing for the scope of the slow-model contribution.
  2. [fast time-varying model section] Fast-model optimality claim: the abstract states that the single-selection policy on the best channel is optimal among all fixed-probability blind policies. The proof must show that any other probability vector p yields strictly higher ETTR under the i.i.d. assumption; if the argument relies only on the per-slot success probability being maximized by the best channel, it should also confirm that the resulting geometric waiting time is minimized (no counter-example under non-uniform success probabilities).
minor comments (2)
  1. Notation for ETTR, channel selection probabilities, and the success-probability function should be introduced with explicit symbols in the preliminaries before being used in the abstract claims.
  2. The abstract refers to 'approximation solutions' derived from the bounds; the manuscript should state the approximation ratio or the precise sense in which the policies approximate the optimum.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the scope of our results. We address each major comment below and will revise the manuscript to improve clarity.

read point-by-point responses

  1. Referee: [slow time-varying model / extension paragraph] Abstract and slow-model section: the ETTR bounds and subsequent approximation guarantees are derived under the explicit exchangeability assumption via majorization ordering on the state vector. The manuscript then claims an extension to general stationary joint distributions; it is unclear whether the majorization inequalities continue to hold or whether only the approximation policies (but not the bounds) survive the relaxation. This distinction is load-bearing for the scope of the slow-model contribution.

    Authors: We agree the distinction is important and will make it explicit. The majorization-based ETTR bounds and inequalities are derived under exchangeability of the state vector. For general stationary joint distributions, the extension applies to the approximation policies (which are motivated by the exchangeable case) but does not claim the same bound guarantees. We will revise the abstract and the extension paragraph to state this scope clearly. revision: yes

  2. Referee: [fast time-varying model section] Fast-model optimality claim: the abstract states that the single-selection policy on the best channel is optimal among all fixed-probability blind policies. The proof must show that any other probability vector p yields strictly higher ETTR under the i.i.d. assumption; if the argument relies only on the per-slot success probability being maximized by the best channel, it should also confirm that the resulting geometric waiting time is minimized (no counter-example under non-uniform success probabilities).

    Authors: The fast-model proof shows that the per-slot success probability is strictly maximized by allocating all probability to the single best channel (the one with highest expected success probability). Because the time-to-rendezvous is geometric with this per-slot probability as its parameter, ETTR equals the reciprocal and is therefore strictly minimized. We will add an explicit sentence confirming that the inverse relationship precludes counter-examples under non-uniform probabilities. revision: yes

Circularity Check

0 steps flagged

No significant circularity; ETTR bounds derived from external majorization on explicit exchangeability assumption

full rationale

The paper states the exchangeability assumption explicitly before invoking majorization ordering to obtain ETTR lower/upper bounds for the slow time-varying model. Majorization is an external mathematical tool applied to the assumed joint distribution; the resulting inequalities are not reductions of the ETTR definition itself. The fast-model optimality result is shown directly from the i.i.d. channel model without that assumption. No parameters are fitted to data and then relabeled as predictions, no self-citation chain carries the central claim, and no ansatz is imported via prior work. The derivation therefore remains self-contained once the stated modeling assumptions are granted.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper rests on standard domain assumptions about stochastic channel processes and applies an existing ordering from mathematics; no free parameters or new entities are introduced.

axioms (3)
  • domain assumption Channel states are stochastic processes whose joint distributions are known to the users but whose exact realizations are unobservable.
    Core modeling premise stated in the abstract that defines the blind rendezvous setting.
  • domain assumption For the slow time-varying model the channel states are exchangeable random variables.
    Explicitly required to invoke majorization ordering for the ETTR bounds.
  • domain assumption The joint distribution of channel states is stationary in time.
    Used for the extension to general channel models.

pith-pipeline@v0.9.0 · 5798 in / 1565 out tokens · 41589 ms · 2026-05-25T16:21:15.637835+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    A Tutorial on Multichannel Rendezvous in Cognitive Radio Networks,

    C.-S. Chang, D.-S. Lee, and W. Liao, “A Tutorial on Multichannel Rendezvous in Cognitive Radio Networks,” Chapter 1 of Cogni- tive Radio Networks: Performance, Applications and T echnology . Nova Science Publisher, 2018

    work page 2018

  2. [2]

    Z. Gu, Y. Wang, Q.-S. Hua, and F. C. M. Lau, Rendezvous in Distributed Systems: Theory, Algorithms and Applications . Springer, 2017

    work page 2017

  3. [3]

    Alpern and S

    S. Alpern and S. Gal. The Theory of Search Games and Rendezvous . Dordrecht: Kluwer Academic Publishers, 2003

    work page 2003

  4. [4]

    DH-MAC: A dynamic channel hopping MAC protocol for cognitive radio networks,

    C.-F. Shih, T. Y. Wu, and W. Liao, “DH-MAC: A dynamic channel hopping MAC protocol for cognitive radio networks,” in Proc. IEEE ICC’2010

    work page 2010

  5. [5]

    Tight lower bounds for chan- nel hopping schemes in cognitive radio networks,

    C.-S. Chang, W. Liao, and T.-Y. Wu, “Tight lower bounds for chan- nel hopping schemes in cognitive radio networks,” IEEE/ACM T ransactions on Netowrking, vol. 24, no. 4, pp. 2343–2356, 2016

    work page 2016

  6. [6]

    Multicast rendezvous in fast-varying DSA network,

    M. J. Abdel-Rahman, H. Rahbari, and M. Krunz, “Multicast rendezvous in fast-varying DSA network,” IEEE T ransactions on Mobile Computing, vol. 14, no. 7, pp. 1449–1462, 2015

    work page 2015

  7. [7]

    Dynamic rendezvous algorithms for cognitive radio networks,

    H.-S. Pu, Z.-Q. Gu, X. Lin, Q.-S. Hua, and H. Jin, “Dynamic rendezvous algorithms for cognitive radio networks,” in Proc. IEEE ICC, May, 2016

    work page 2016

  8. [8]

    Efficient rendezvous schemes for fast-varying cognitive radio ad hoc networks,

    A. Al-Mqdashi, A. Sali, M. J. Abdel-Rahman, N. K. Noordin, S. J. Hashim, and R. Nordin, “Efficient rendezvous schemes for fast-varying cognitive radio ad hoc networks,” in T ransactions on Emerging T elecommunications T echnologies, vol. 28, issue 12, Decem- ber, 2017

    work page 2017

  9. [9]

    A quorum-based framework for establishing control channels in dynamic spectrum access networks,

    K. Bian, J.-M. Park, and R. Chane, “A quorum-based framework for establishing control channels in dynamic spectrum access networks,” ACM MobiCom’09, 2009

    work page 2009

  10. [10]

    Deterministic rendezvous scheme in multichannel access networks,

    D. Yang, J. Shin, and C. Kim, “Deterministic rendezvous scheme in multichannel access networks,” Electronics Letters , vol. 46, no. 20, pp. 1402-1404, 2010

    work page 2010

  11. [11]

    Rendezvous for cognitive radios,

    N. C. Theis, R. W. Thomas, and L. A. DaSilva, “Rendezvous for cognitive radios,” IEEE T ransactions on Mobile Computing , vol. 10, no. 2, pp. 216–227, 2011

    work page 2011

  12. [12]

    Jump-stay based channel-hopping algorithm with guaranteed rendezvous for cog- nitive radio networks,

    Z. Lin, H. Liu, X. Chu, and Y.-W. Leung, “Jump-stay based channel-hopping algorithm with guaranteed rendezvous for cog- nitive radio networks,” in Proc. IEEE INFOCOM 2011

    work page 2011

  13. [13]

    Nearly optimal asynchronous blind rendezvous algorithm for cognitive radio networks,

    Z. Gu, Q.-S. Hua, Y. Wang, and F. C. M. Lau, “Nearly optimal asynchronous blind rendezvous algorithm for cognitive radio networks,” in Proc. IEEE SECON , 2013

    work page 2013

  14. [14]

    A fast rendezvous channel-hopping algorithm for cognitive radio networks,

    G.-Y. Chang and J.-F. Huang, “A fast rendezvous channel-hopping algorithm for cognitive radio networks,” IEEE Communications Letters, vol. 17, no. 7, pp. 1475–1478, 2013

    work page 2013

  15. [15]

    Novel channel-hopping schemes for cognitive radio networks,

    G.-Y. Chang, W.-H. Teng, H.-Y. Chen, and J.-P . Sheu, “Novel channel-hopping schemes for cognitive radio networks,” IEEE T ransactions on Mobile Computing, vol. 13, pp. 407–421, Feb. 2014

    work page 2014

  16. [16]

    Fully distributed algorithm for blind rendezvous in cognitive radio networks,

    Z. Gu, Q.-S. Hua, and W. Dai, “Fully distributed algorithm for blind rendezvous in cognitive radio networks,” In Proc. ACM MobiHoc, pp. 155–164, 2014

    work page 2014

  17. [17]

    Efficient encod- ing of user IDs for nearly optimal expected time-to-rendezvous in heterogeneous cognitive radio networks,

    C.-S. Chang, C.-Y. Chen, D.-S. Lee, and W. Liao, “Efficient encod- ing of user IDs for nearly optimal expected time-to-rendezvous in heterogeneous cognitive radio networks,” IEEE/ACM T ransactions on Networking, vol. 25, no. 6, pp. 3323–3337, 2017. IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. X, AUGUST 20XX 14

    work page 2017

  18. [18]

    Deterministic dis- tributed rendezvous algorithms for multi-radio cognitive radio networks,

    G. Li, Z. Gu, X. Lin, H. Pu, and Q.-S. Hua, “Deterministic dis- tributed rendezvous algorithms for multi-radio cognitive radio networks,” Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems , pp. 313–320, 2014

    work page 2014

  19. [19]

    Multiple radios for fast rendezvous in cognitive radio networks,

    L. Yu, H. Liu, Y. W. Leung, X. Chu, and Z. Lin, “Multiple radios for fast rendezvous in cognitive radio networks,” IEEE T ransactions on Mobile Computing, vol. 14, no. 9, pp. 1917–1931, Sept. 2015

    work page 1917

  20. [20]

    Adjustable rendezvous in multi-radio cognitive radio networks,

    L. Yu, H. Liu, Y. W. Leung, X. Chu, and Z. Lin, “Adjustable rendezvous in multi-radio cognitive radio networks,” In Proc. IEEE Globecom, pp. 1–7, 2015

    work page 2015

  21. [21]

    An enhanced fast multi-radio rendezvous algorithm in heterogeneous cognitive ra- dio networks,

    Y.-C. Chang, C. S. Chang, and J.-P . Sheu, “An enhanced fast multi-radio rendezvous algorithm in heterogeneous cognitive ra- dio networks,” IEEE T ransactions on Cognitive Communications and Networking, vo. 4, no. 4, pp. 847–859, 2018

    work page 2018

  22. [22]

    Marshall and I

    A.W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications. New York: Academic Press, 1979

    work page 1979

  23. [23]

    S. M. Ross, Stochastic Processes. John Wiley and Sons, 1996

    work page 1996

  24. [24]

    Integration of discrete-time correlated Markov processes in a TDM system: structural results,

    C.-S. Chang, X. Chao and M. Pinedo, “Integration of discrete-time correlated Markov processes in a TDM system: structural results,” Probability in the Engineering and Informational Sciences , vol. 4, pp. 29–56, 1990

    work page 1990

  25. [25]

    Inequalities for distributions with given marginals,

    A. H. Tchen, “Inequalities for distributions with given marginals,” Ann. Prob., vol. 8, no. 4, pp. 814–827, 1980

    work page 1980

  26. [26]

    Upper bounds for single server queues with doubly stochastic Poisson arrivals,

    T. Rolski, “Upper bounds for single server queues with doubly stochastic Poisson arrivals, ” Math. of Oper. Res. , vol. 11, no. 3, pp. 442–450, 1986

    work page 1986

  27. [27]

    R. S. Sutton and A. G. Barto, Reinforcement learning: an introduction. Massachusetts: The MIT Press, 2012. Cheng-Shang Chang (S’85-M’86-M’89-SM’93- F’04) received the B.S. degree from National Taiwan University, Taipei, Taiwan, in 1983, and the M.S. and Ph.D. degrees from Columbia Uni- versity, New Y ork, NY , USA, in 1986 and 1989, respectively, all in e...

    work page 2012