On Heterogeneous Sensing Capability for Distributed Rendezvous in Cognitive Radio Networks
Zhaoquan Gu, Yuexuan Wang, Tong Shen, Francis C. M. Lau
Abstract
Cognitive radio networks (CRNs) have been proposed to solve the spectrum scarcity problem. One of their fundamental procedures is to construct a communication link on a common channel for the users, which is referred to as <i>rendezvous</i> . In reality, the capability to sense the spectrum may vary from user to user. We study distributed rendezvous for heterogeneous sensing capabilities in this paper. The licensed spectrum is divided into <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> channels, <inline-formula><tex-math notation="LaTeX">$U = \lbrace 1,2,\ldots,n\rbrace$</tex-math></inline-formula> . We denote the sensing capability of user <inline-formula><tex-math notation="LaTeX">$i$</tex-math></inline-formula> as <inline-formula><tex-math notation="LaTeX">$C_i \subseteq U$</tex-math></inline-formula> and the set of available channels (i.e., the channels not occupied by paying users) as <inline-formula><tex-math notation="LaTeX">$V_i \subseteq C_i$</tex-math></inline-formula> . Due to hardware differences, the users may have different sensing capabilities: <inline-formula><tex-math notation="LaTeX">$C_i \ne C_j$</tex-math></inline-formula> , and this is called <i>heterogeneous sensing capability</i> . In this paper, we propose efficient algorithms for two scenarios: the fully available scenario where <inline-formula><tex-math notation="LaTeX">$V_i = C_i$</tex-math></inline-formula> and the partially available scenario where <inline-formula><tex-math notation="LaTeX">$V_i \subseteq C_i$</tex-math></inline-formula> . Our idea is to utilize two ‘pointers’ to traverse the sensing capability set, which sets our algorithms apart from the extant rendezvous algorithms. Considering any two neighboring users <inline-formula><tex-math notation="LaTeX">$a, b$</tex-math></inline-formula> , we propose the Traversing Pointer (TP) algorithm that guarantees rendezvous in <inline-formula><tex-math notation="LaTeX">$O(\max \lbrace |C_a|,|C_b|\rbrace \log \log n)$</tex-math></inline-formula> time slots for the fully available scenario. This result is only <inline-formula><tex-math notation="LaTeX">$O(\log \log n)$</tex-math></inline-formula> larger than the theoretical lower bound. Moreover, it removes an <inline-formula><tex-math notation="LaTeX">$O(\min \lbrace |C_a|,|C_b|\rbrace)$</tex-math></inline-formula> factor when compared to the state-of-the-art result ( <inline-formula><tex-math notation="LaTeX">$O(|C_a||C_b|)$</tex-math></inline-formula> in S.-H. Wu <i>et al.</i> For the partially available scenario, we propose the Moving Traversing Pointers (MTP) and Prime based Moving Traversing Pointers (P-MTP) algorithms that can guarantee rendezvous within <inline-formula><tex-math notation="LaTeX">$O((\max \lbrace |V_a|,|V_b|\rbrace)^2\log \log n)$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$O(|V_a||V_b|\log \log n)$</tex-math></inline-formula> time slots respectively, where the latter one combines the pointers and a common technique of plugging in a prime number. The proposed algorithms work more efficiently than the previous best result ( <inline-formula><tex-math notation="LaTeX">$O(|C_a||C_b|)$</tex-math></inline-formula> in C.-C. Wu <i>et al.</i> under various circumstances. We also conduct extensive simulations and the results corroborate our analyses.