On the Theoretical Gap of Channel Hopping Sequences With Maximum Rendezvous Diversity in the Multichannel Rendezvous Problem

In the literature, there are several well-known periodic channel hopping (CH) sequences that can achieve maximum rendezvous diversity in a cognitive radio network (CRN). For a CRN with N channels, it is known that the period of such a CH sequence is at least N
²
. The asymptotic approximation ratio, defined as the ratio of the period of a CH sequence to the lower bound N
²
when N → ∞, is still 2.5 for the best known CH sequence in the literature. An open question in the multichannel rendezvous problem is whether it is possible to construct a periodic CH sequence that has the asymptotic approximation ratio of 1. In this paper, we tighten the theoretical gap by proposing CH sequences, called IDEAL-CH, that have the asymptotic approximation ratio of 2. For a weaker requirement that only needs the two users to rendezvous on one commonly available channel in a period, we propose channel hopping sequences, called ORTHO-CH, with period (2 p+1) p, where p is the smallest prime not less than N.