Abstract
In this paper, we propose a fast rendezvous algorithm for a heterogeneous cognitive radio network (CRN), where each user might have more than one radio. One of the well-known problems for most multi-radio rendezvous algorithms in the literature is that they are not backward compatible to users with only one radio. To tackle this backward compatibility problem, our approach is a hierarchical construction that groups several time slots into an interval and proposes a novel algorithm to emulate two radios with a single radio in an interval. By doing so, at the interval level, each user behaves as if it had (at least) two radios. For the two-user rendezvous problem in a CRN with N commonly labelled channels, the interval length is chosen to be 2M time slots, where M=2lceil log-2 (lceil log-2 N rceil)rceil+10. We show that the maximum time-to-rendezvous (MTTR) of our algorithm is bounded above by 18 M lceil n-1/m-1 rceil cdot lceil n-2/m-2 rceil time slots, where n-1 (resp. n-2) is the number of available channels to user 1 (resp. 2), and m-1 (resp. m-2) is the number of radios for user 1 (resp. 2). For the setting that each user is equipped with only one radio and two available channels, our MTTR bound is only M and that improves the state-of-the-art bound 16(lceil log-2 log-2 N rceil+1) in the literature. By conducting extensive simulations, we show that the expected time-to-rendezvous (ETTR) of our algorithm is also better than the two commonly used multi-radio algorithms, JS/Independent and JS/Parallel, in most parameter settings.