1 Introduction

The tremendous growth in the applications of wireless devices operating in unlicensed spectrum bands has overcrowded the unlicensed spectrum (such as the 2.4 GHz ISM). On the other hand, a large amount of licensed spectrum (e.g., TV spectrum) is underutilized [1]. With the recent advances in Cognitive Radio (CR) technology, it is possible to solve unlicensed spectrum shortage problem, where the unlicensed users or the secondary users (SUs) opportunistically utilize the licensed band, when it is not being used by the licensed users or the primary users (PUs) [1,2,3]. The SU is outfitted with a cognitive radio transceiver and periodically senses or observes the signals of PU. Once the PU reappears, SU must immediately vacates the band and hops to next vacant band or spectrum holes to avoid interference with PU. Prior to data transmission, both the transmitter and receiver SUs need to exchange control information and establish a link over the available channel, known as rendezvous between the SUs. CRN’s current rendezvous systems may be either centralized or distributed type. Most of the rendezvous assignments are following the centralized approach, where a centralized controller [4] or a dedicated common control channel (CCC) [5] facilitates the rendezvous among the SUs. Though the centralized approach simplifies the rendezvous, it faces low scalability and flexibility issues in the network congestion. Besides, the CCC suffers from bottleneck, saturation and jamming attack problems [6, 7]. In real practice, a blind rendezvous without any centralized unit or CCC is preferred for the distributed system. The rendezvous is a challenging process, as both the SUs are unaware of their respective presence and also about the available channels sensed by each of them, which is dynamic in nature. In blind rendezvous, Channel Hopping (CH) sequences are used by the SUs [8,9,10,11]. According to the CH sequences, the SUs hop on different available channels in each time slot until they visit a common channel at the same time. To have an efficient CH sequence for each SU, the following different criteria are needed to be considered [10, 12,13,14,15].

  • Symmetric and Asymmetric model: Depending on the location of the SUs in the CRN, the availability of channels for each user varies. When SUs are located in a relatively small area, they have an identical set of available channels known as the symmetric model. In the asymmetric model, the SUs are supposed to be far apart from each other, and thus, have different sets of available channels. In this case, they can rendezvous with each other if they have at least one common channel in their respective available channel sets.

  • Synchronous and Asynchronous Environment: Once SUs begin to hop, it is presumed that their CH sequences are synchronized with each other. In real practice, however, there may be some time drifts between the CH sequences or they may not be aligned. Thus, in the case of an asynchronous environment, the CH sequences have to provide guaranteed rendezvous.

  • Heterogeneity of roles: The function of SUs in most CRNs is homogeneous i.e. all SUs are both sender and receiver at the same time. So the SUs cannot be given any particular position of sender or receiver. However, if SU has data to transmit, it may act as a sender, and act as a receiver when it is destined to receive data. Most master-slave networks exist, such as Bluetooth, body area networks [16], etc., where tasks are already assigned to users. For the generation of CH sequences, therefore, the network types can be taken into account.

After designing the CH sequences for the rendezvous, considering the above criteria, the performance can be measured for an efficient rendezvous method with the following metrics.

  • Rendezvous guarantee: There should be a guaranteed rendezvous between two SUs in the asynchronous environment for both symmetric, and asymmetric models. The minimum number of distinct channels on which rendezvous can be achieved by a pair of CH sequences, is called the degree of rendezvous. Large degree of rendezvous implies higher chances of rendezvous in a high traffic CRNs. Thus, the impact of long time channel blocking by the PUs can be addressed by increasing the degree of rendezvous.

  • ETTR and MTTR: Expected time to rendezvous (ETTR) is the average time required for the first rendezvous. The upper bound for ETTR is denoted by Maximum TTR (MTTR) when all channels are available to SUs. Minimum MTTR would minimize the medium access delay for the SUs, as they can exchange control information only after the rendezvous.

  • MCTTR: Maximum conditional time to rendezvous (MCTTR) is the maximum time required by a pair of SUs to rendezvous, while both may have different sets of available channels [17]. A CH scheme with MCTTR = 5 means that if there is at least one common available channel for a pair of SUs, they have a guaranteed rendezvous within 5 time slots on that available channel.

  • Channel loading: It is the maximum proportion of CH sequences that can rendezvous at the same time-slot on the same channel [17]. A high probability of SUs rendezvous on the same channel at the same time-slot, means large channel loading, which results a high chance of channel congestion and channel blocking by SUs. This kind of problem with the bottleneck emerges in the network, when everybody uses similar CH sequences.

In this paper a CH scheme has been designed for specific types of CRN, where the SUs with preassigned roles achieve the blind rendezvous in distributed, and asynchronous environment. The main contributions of this work are summarized as follows

  • In order to achieve full degree of rendezvous utilizing less time slots, a role based framework has been used in the generation of CH sequences. Here SUs are preassigned with roles as sender or receiver.

  • The degree of rendezvous, channel loading and the upper-bound for the ETTR under the symmetric, and asymmetric model are derived.

  • The performance of the rendezvous scheme has been presented through extensive simulation results under symmetric, and asymmetric model.

2 Related Works

Many researchers have been exploring the different criteria for efficient rendezvous, and developing different methods to generate CH sequence to achieve blind rendezvous, targeting different types of CR environment. In Jump-stay based channel hopping (JS) [10], the CH sequence of each SU consists of 3P-length sub-sequences. The SU jumps on channels for 2P-length slots with a specific pattern, which is a permutation of numbers 0 to P-1, while staying on a specific channel for the next P slots. P is the smallest prime number greater than the total number of available channels N. Though JS performs better in symmetric model, has a very large rendezvous time in asymmetric model. The JS scheme is further improved with Enhanced Jump-Stay (EJS) in [18] for the asymmetric model, where the SU jumps for 3P-length slots in a 4P length of sub-sequence. Channel rendezvous sequence (CRSEQ) [19] generates a periodic CH sequence with N subsequences, where each subsequence consists of two jump patterns. The jump pattern is generated with the available channels taking advantages of triangular number. In Disjoint relaxed difference set based channel hopping (DRDS) [20], authors have used disjoint relaxed difference sets to generate the CH sequence, where each set is with 3P elements. Here, the SU hops on a specific channel at a particular time slot based on the element value in the relaxed difference set to achieve full degree of rendezvous but with a high value of MTTR. In Interference based DRDS (I-DRDS) [21], though the rendezvous is guaranteed on the channel with less interference, the MTTR is still very high. Another difference set based rendezvous scheme is introduced in [22] with MTTR = 1. However, the optimal MTTR is achieved when SUs have equivalent available channel sets and equipped with multiple radios.

Matrix-based Rendezvous scheme is designed in [17], where identical CH sequences called T-CH are generated for each SU in the network by using a default matrix consisting of jump columns, and stay columns. This scheme guarantees rendezvous at all distinct channels within \(2N^{2} +\lfloor \frac{N}{2}\rfloor \times N\) with channel loading = \(\frac{1}{N}\). Here, N is considered to be the smallest prime number greater than the total number of available channels. An ID-based method of generating CH sequences designed for both the symmetric, and asymmetric models in Alternate hop-and-wait (AHW) [23] that can be used for multi-user rendezvous. In AHW, separate CH sub-sequences consisting of hop-modes and stay-modes are generated for each user with the help of each user’s assigned ID. Since the generation of the CH sequence is related to the length of the ID, this scheme may have a problem with a large number of SUs in a dynamic network, where the exact assignment of IDs is not easy. Considering the role of SUs, rendezvous schemes are proposed in [24, 25]. In Rendezvous couple channel-hopping scheme (RCCH) [24], the initial channels of the CH sequences for each sender, and receiver pair are expected to have the same parity to guarantee a rendezvous. Though this approach has a smaller MTTR value of \(\frac{N}{2}\), where N is the total channels available, this scheme is applied only to synchronous environments. The Asynchronous rendezvous channel-hopping scheme (ARCH) is proposed in [24] to address the deficiency of RCCH, which provides guaranteed rendezvous in asynchronous environment with \(MTTR=2N-1\). In the paper [26], a modified enhanced heterogeneous radio rendezvous (MEHRR) scheme is proposed for the SUs in heterogeneous CRNs, where the SUs may have multiple radios. Though this scheme provides fast rendezvous to the SUs with multiple radios, still has high MTTR value of \(3P^3\) time slots when the SUs are equipped with single radio. A novel cooperative rendezvous mechanism is introduced in paper [27], where rendezvous between two SUs is facilitated with the help of cooperative cognitive nodes. Here, extra helper nodes are required which serve as bridges between the communicating SU pairs. In [25], a matrix-based CH sequence is generated considering the role of SU, and a fast rendezvous with full degree of Rendezvous is achieved with the available channels. Table 1 summarizes the performance metrics of the mentioned schemes.

However, while most of the current CH schemes manage to solve the rendezvous problem effectively, they either depend on unfavorable assumptions, or have a long TTR. The challenge of achieving full degree of rendezvous, within minimum time slots in an asynchronous CRN environment is still open to researchers. This paper attempts to minimize the values of MTTR, and MCTTR by taking the advantage of the preassigned roles of the SUs.

Fig. 1
figure 1

Distributed cognitive radio network

Full size image

3 System Model and Problem Formulation

3.1 System Model

In this paper, distributed CR network is considered, as shown in the Fig. 1, where the SUs are coexist with the PUs and there are M number of licensed channels owned by the PUs (indexed as 0, 1, 2, 3, ..., and (M − 1)). The channels are supposed to be opportunistically used by the SUs, when they are not being used by the PUs. Each SU is equipped with a cognitive radio transceiver for channel sensing, and data transmission. According to their location, and sensing outcomes, each SU may have a different set of available channels, which is a subset of M licensed channels. Before data transmission, the SU transmitter (\(SU_{A}\)), and the SU receiver (\(SU_{B}\)) are supposed to rendezvous on an available channel to exchange their control information. Thus, \(SU_{A}\), and \(SU_{B}\) with available channels sets \(M_{A}\) and \(M_{B}\) respectively, will rendezvous on channel C, where C \(\in M_{A} \cap M_{B}\), and \(M_{A}\), \(M_{B} \subset \lbrace 0,1,2,\ldots ,(M-1)\rbrace\). The SUs follow channel hopping (CH) sequences to hop on their respective available channels till the rendezvous occurs. The time in the proposed system is divided into time slots. A SU will be on a particular channel at the particular time slot. The CH sequence of the \(SU_{X}\) is referred as a periodically repeating sequence (\(S_x\)) with a time period of m slots. Sequence \(S_x\) is represented by \(S_X=\lbrace \textit{x}_{0},\textit{x}_{1},\ldots ,\textit{x}_{m-1} \rbrace\), where \(x_i\) is the channel, visited by \(SU_{X}\) at ith time slot, and \({x}_{i}\in \lbrace 0,1,2, 3,\ldots ,(M-1)\rbrace\).

3.2 Problem Formulation

The main focus of this paper is to design a CH sequence for a blind rendezvous, considering the following required criteria.

  • Asymmetric model support: Since, in the symmetric model, all SUs have identical sets of available channels, \(M_{A}= M_{B}\). In real practice, \(M_{A}\) may not be equal to \(M_{B}\), which is termed as an asymmetric model. A rendezvous scheme should be designed such that, it can be applicable to both symmetric and asymmetric models. However, a CH scheme designed for asymmetric model can be used by the symmetric model by considering it as a special case under the asymmetric model.

  • Asynchronous rendezvous support: In the time-slotted communication system, the slot duration is set as 2T [14], where T is the minimum time required for information exchange between SUs. The reason is that the time slots of SUs may be unaligned. Since the clock synchronization is impractical, this work considers the asynchronous environment, where each SU’s local clock may not be synchronized with the global clock. Thus, there exists a drift of \(\delta\) time slots between \(S_A\) and \(S_B\), where \(\delta \in [0, m-1]\)

  • Guaranteed rendezvous: The CH sequence should ensure a rendezvous within finite time-slots. An efficient rendezvous scheme should have a degree of rendezvous, equal to the number of available channels, so that a guaranteed rendezvous can possible for an asymmetric model.

  • Role Assignment: In this paper, master-slave type networks are considered, where each SU is preassigned with a role, \(r \in \lbrace A, B \rbrace\). Thus, a SU is either a sender, \(SU_{A}\) (if it has data to send) or a receiver, \(SU_{B}\) (if it has data to receive). Generation of CH sequence would be different for SUs according to the role played by them.

  • Short time-to-rendezvous (TTR): The performance of rendezvous scheme is assessed using the metrics defined in the preceding section, such as MTTR, ETTR, MCTTR. An efficient blind rendezvous method should have the minimum possible values of these metrics, as it would minimize the medium access delay for a SU.

Thus, the Blind Rendezvous Problem can be formulated as follows:

For a sender and receiver SU pair, with the available channel sets \(M_{A}\), \(M_{B}\) respectively, design the channel access strategy at different time slots, \(S_{r}\)(t) \(\in M_{r}\), \(r \in \lbrace\)A, B\(\rbrace\), such that: \(\forall M_{A}\), \(M_{B} \subseteq \lbrace 0,1,2,\ldots ,(M-1)\rbrace\), \(\forall \delta\), and \(\forall R \in M_{A} \cap M_{B}\):

\(\exists t'\) s.t. \(S_{A}(t' + \delta ) = S_{B}(t')=R\).

The designed strategy should also have minimum MTTR and MCTTR value, where ETTR = \(\frac{\sum _{\delta =0}^{m-1} min_{\forall R} t'}{m}\), MTTR = \(max_{\forall \delta }\; (min_{\forall R} t')\), when \(M_{A} = M_{B}\), and MCTTR = \(max_{\forall \delta } t'\), when \(\vert M_{A} \cap M_{B}\vert =1\). Here \(min_{\forall R} t'\) represents the time slot at which the two CH sequences rendezvous for the first time, for a given \(\delta\).

4 Proposed Channel Hopping Scheme

4.1 Basic Idea

The main concept of this paper is developed by considering each licensed channel as a vertex on a circle, as shown in Fig. 2a. The basic idea is that if one user hops clockwise, and other hops in the counter-clockwise direction with the same speed, then both of them will rendezvous twice, when the total number of channels (N) is even, and rendezvous once when it is odd, as shown in Fig. 2b, c respectively. Generation of CH sequence by considering N as even can give better rendezvous in a synchronous environment, but does not work well in an asynchronous environment [24]. In this paper, the CH sequences are designed with N as an odd number. Since the available channel set might be different for different SU, N is chosen considering all the licensed channels in the CRN. Thus, N is the smallest odd number greater than M. So, if \(\lbrace 0,1,2,3\rbrace\) is the channels set then \(\lbrace 0,1,2,3,4(0)\rbrace\), is considered for the generation of CH, where the extra channel can be seen as one of the available channels (say channel-0).

Fig. 2
figure 2

a Channel-hopping of SUs, b N is even: In this example, N = 6 and the figure shows different cases of rendezvous for randomly chosen initial channel. Exactly two rendezvous exist in one cycle of hops, when the sender and receiver start hopping from channels of equal parity, c N is odd: In this example, N = 5. Exactly one rendezvous exist in one cycle, irrespective of the starting channel parity of sender and receiver

Full size image

Now if x is a CH sequence, then rotate(x, i) can be defined as another CH sequence which is i time slots ahead of sequence x. For example, if \(N=7\), and \(x = \lbrace 0,1,2,3,4,5,6\rbrace\), then rotate\((x,3) = \lbrace 3,4,5,6,0,1,2\rbrace\). It can be easily realized that \(x \ne\) rotate(x, i) for \(0< i mod N < N\), and \(x=\textit{rotate}(x, i)\) for \(i= mN\), where m is an integer.

4.2 Role-Based Channel Hopping Sequence Generation

Channel hopping sequence for a SU is generated based on its assigned role in the network. This role-based CH (R-CH) guarantees rendezvous on all available channels in an asynchronous environment. From now onward in this paper, N is considered as the number of total licensed channels, and N is odd.

4.2.1 Generation of Alternative CH Sequence for a Sender SU

To start the hop, the sender SU randomly chooses a channel (say ‘a’) from the available channel set. With the initial channel \(a\in \lbrace 0,1,2,3,\ldots ,N-1\rbrace\), a subsequence x is generated as \(x= \lbrace a,(a-1)mod N,(a-2)mod N,\ldots ,(a-(N-1))mod N\rbrace\). An alternative CH sequence \(S_{A}\) is formed by concatenating N distinct number of subsequences and is given by

$$\begin{aligned} S_{A}=\lbrace rotate(x,0),rotate(x,1),\ldots ,rotate(x,N-1)\rbrace \end{aligned}$$

The sender hops counter-clockwise in the circle (Fig. 2a) according to the generated CH sequence \(S_{A}\) periodically till the rendezvous occurs with the receiver SU.

figure c

4.2.2 Generation of Default CH Sequence for a Receiver SU

The receiver also starts hopping in clockwise direction (Fig. 2a) from a randomly chosen channel say b, where \(b\in \lbrace 0,1,2,3,\ldots ,N-1\rbrace\). It follows its CH sequence, which is the concatenation of N number of identical subsequences say(y). The subsequence, \(y=\lbrace b,(b+1)mod N,(b+2)mod N,\ldots ,(b+(N-1))mod N\rbrace\), and the default CH sequence \(S_{B}\) is given by

$$\begin{aligned} S_{B}&= \lbrace rotate(y,0), rotate(y,0), rotate(y,0),\ldots , (N \; times)\rbrace \\&= \lbrace y, y,\ldots (N \;times)\rbrace \end{aligned}$$
figure d

Example

let us consider a CR network with licensed channel set \(\lbrace 0,1,2,3\rbrace\), and hence \(M=4\). As already stated, the CH sequences are constructed with N as the smallest odd number greater than the total number of channels, M. Thus with \(N=5\), the considered channel set for the CH sequence generation is \(\lbrace 0,1,2,3,4(0)\rbrace\), where the extra channel-4 can be seen as one of the available channels (say channel-0). For a symmetric model, i.e. \(M_{B}=M_{B}\), and say all channels are available to both the SUs, that is \(\vert M_{B}\vert =\vert M_{B}\vert =M\). The sender SU randomly chooses a channel, say \(a=4\), and the receiver SU randomly chooses a channel say \(b=2\). A subsequence x is generated as \(x=\lbrace 4,3,2,1,0\rbrace\) and \(y=\lbrace 2,3,4,0,1\rbrace\). Then the alternative CH sequence \(S_A\) is formed using Algorithm 1, and is given by \(S_{A}=\lbrace 4,3,2,1,0,3,2,1,0,4,2,1,0,4,3,1,0,4,3,2,0,4,3,2,1\rbrace\) and default CH sequence \(S_B\) is the formed using Algorithm 2, and is given by \(S_{B}=\lbrace 2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1\rbrace\). Figure 3a, b depict the sequence generation for synchronous environment, and asynchronous environment respectively. For a specified symmetric model, when \(\vert M_{B}\vert =\vert M_{B}\vert =M' < M\), CH sequences are generated similarly by considering N as the smallest odd number greater than the total number of channels \(M'\).

Fig. 3
figure 3

Rendezvous under a symmetric model

Full size image

For asymmetric model, with the licensed channel set \(\lbrace 0,1,2,3\rbrace\), let the channel set available for \(SU_A\) is \(M_{A}=\lbrace 0,2,3\rbrace\), and for \(SU_B\) is \(M_{B}=\lbrace 1,2,3\rbrace\). The \(SU_A\) randomly chooses a channel \(a=4\), and the \(SU_B\) randomly chooses a channel \(b=2\). The alternative CH sequence \(S_A\) is formed using Algorithm 1 and is given by \(S_{A}= \lbrace 0,3,2,2,0,3,2,0,0,0,2,3,0,0,3,2,0,0,3,2,0,0,3,2,2 \rbrace\), and default CH sequence \(S_B\) is the formed using Algorithm 2, and is given by \(S_{B}= \lbrace 2,3,1,2,1,2,3,2,2,1,2,3,3,2,1,2,3,1,3,1,2,3,2,1,1\rbrace\). So the CH sequences in asymmetric model are similar to the CH in symmetric model with \(M_{B}=M_{B}=M\), where the unavailable channels in the sequences are replaced with the available channels. The underline digits, shown in Fig. 4 represent random replacement of channels.

Fig. 4
figure 4

Rendezvous under an asymmetric model

Full size image

Lemma 1

Suppose x and y are the CH subsequences of the sender, and receiver with a and b as initial channels randomly chosen respectively, where \(a, b\in [0, N-1]\) is used. Then the following two statements can be claimed.

  1. 1.

    x and y will have rendezvous on channel C, where

    $$\begin{aligned} C= \left\{ \begin{array}{ll} \dfrac{(a+b)}{2} mod\; N &{}\quad \textit{(if a and b are of same parity)}\\ \dfrac{a+b+N}{2} mod\; N &{}\quad \textit{(if a and b are of different parity)} \end{array} \right. \end{aligned}$$
  2. 2.

    x and y will have rendezvous at time slot i for \(i\in [0, N-1]\)

    $$\begin{aligned} i= \left\{ \begin{array}{ll} \dfrac{a-b+N}{2}mod N &{}\quad \textit{(if a and b are of different parity)}\\ \dfrac{a-b+2N}{2}mod N &{}\quad \textit{(if a and b are of same parity)} \end{array} \right. \end{aligned}$$

Proof

In order to find the channel, and the slot, where the rendezvous takes place, let the subsequences rendezvous at the time slot i within N slots. As mentioned earlier, the CH direction of x and y are counterclockwise and clockwise respectively. Suppose both the CH subsequence start at time slot 0, then following the proposed algorithm, at ith slot x is on the channel \((a-i)modN\) and y is on channel \((b+i)mod N\). The rendezvous will occur when

$$\begin{aligned} (a-i)modN = (b+i)modN \Rightarrow a-i+(m\times N) = b+i \end{aligned}$$

which implies

$$\begin{aligned} i mod N = \dfrac{a-b+m\times N}{2} mod N \end{aligned}$$
(1)

and

$$\begin{aligned} (b+i)mod N= \dfrac{a+b+m\times N}{2} mod N \end{aligned}$$
(2)

Now from (1) and (2), slot \(i =\frac{a-b+N}{2} mod N\) or \(\frac{a-b+ 2N}{2} mod N\) for a and b of different or same parity respectively as \(a-b+m\times N\) should be an even value. So x and y will have rendezvous on channel \(C=\frac{a+b+N}{2} mod N\) or \(\frac{a+b}{2} mod N\) for a and b of different or same parity respectively.

Lemma 2

If \(R(S_{A},S_{B})\) represents the set of the channels at which \(S_{A}\) and \(S_{B}\) rendezvous, then \(\vert R(S_{A},S_{B})\vert = N\).

Proof

We have \(S_{A}=\lbrace rotate(x,0),rotate(x,1),\ldots , rotate(x, (N-1) \rbrace\), and \(S_{B} = \lbrace y, y, y \ldots \textit{N} times \rbrace\) where, x and y are the CH subsequences with random initial channel values a and b respectively, and \(a,b\in [0,N-1]\). As rotate\((x,0) \ne\) rotate(x, j), each subsequence rotated with j slots (\(j=1,2,\ldots ,N-1\)) has an initial value \((a-j)\) that is distinct. It is evident from Lemma 1 that, regardless of the initial channel values a, and b, rendezvous occurs once in a subsequence. Further, the subsequence rotate(x, j) of \(S_{A}\) is pairing with the same subsequence y of \(S_{B}\), and \(S_{A}\) has N distinct subsequences. Therefore, rendezvous occurs at all N channels.

Lemma 3

The maximum number of time slots between two consecutive rendezvous is \(N+\lfloor \frac{N}{2}\rfloor -1\).

Proof

Let the first pair of CH subsequences x, and y start hopping from 0th time slot. The first rendezvous, according to Lemma 1, occurs at slot \(i_{1}= \frac{a-b+N}{2} mod N\), where a and b are of different parity. The subsequences rotate(x, 1), and y with initial channels \((a-1)\), and b respectively are to be considered for the next rendezvous to occur. Now it is obvious that \((a-1)\), and b are of the same parity. Therefore, the next rendezvous occurs at slot \(i_{2}=N+ \frac{a-1-b+ 2N}{2}mod N\). Then the interval between consecutive rendezvous would be \(i_{2}-i_{1}-1\). It is obvious from Lemma 1 that certainly two rendezvous occurs within two subsequences, which implies \(0< i_{2}-i_{1} < 2N-1\)

$$\begin{aligned} i_{2}-i_{1}&= N+ \frac{a-1-b+ 2N}{2}mod N- \frac{a-b+N}{2} mod N \\&= N+ \left( \frac{a-1-b+ 2N}{2}-\frac{ a-b+N}{2}\right) mod N+mN \\&= N+ \frac{N-1}{2} mod N +mN \\&= N+ \frac{N-1}{2} +mN \end{aligned}$$
(3)

Thus

$$\begin{aligned} i_{2}-i_{1}&= \frac{N-1}{2}\;\; or\;\; N+\frac{N-1}{2} \\&= \lfloor \frac{N}{2} \rfloor \;\; or \;\; N+\lfloor \frac{N}{2} \rfloor \\&= N+\lfloor \frac{N}{2}\rfloor \;\; or \;\; \lfloor \frac{N}{2}\rfloor \end{aligned}$$
(4)

Hence, the maximum number of time slots between two consecutive rendezvous would be \(N+\lfloor \frac{N}{2}\rfloor -1\).

4.3 Evaluation of Metrics for the Proposed Method

In the asynchronous environment, time-slots of the SU with the delayed local clock are considered for the calculation of performance metrics. For example, in Fig. 3b the receiver’s 0th time slot is considered starting slot as both users have CH sequences to get rendezvous at that slot. The other possibility about the receiver with delayed sender CH sequence can also be studied in a similar way.

Theorem 1

MTTR is \(N+\lfloor \frac{N}{2}\rfloor\)

Proof

As shown in Fig. 3b, let \(\delta\) time slots delay exists between the CH sequence pair of sender, and receiver SUs.

Case-1: It is evident that if \(\delta =mN\) (\(m=0,1,2,\ldots ,N\)), the first subsequence y of \(S_{B}\) is synchronized with any one of subsequences of \(S_{A}\). According to Lemma 1, the first rendezvous occurs within the first N slots.

Case-2: If \(mN<\delta < mN+N-1\), the first subsequence y is delayed \(\delta modN\) timeslots from the nearest subsequence of \(x'\) = rotate\((x,j)\; (j=0,1,\ldots ,N-1)\). Now \(y'\) (refer Fig. 3b of \(S'_{B}\) is synchronized with each subsequences of \(S_{A}\). Therefore, \(S_{A}\), and \(S_{B}'\) has a similar channel-rendezvous occurrence as of \(S_{A}\) and \(S_{B}\). To prove MTTR= \(N+\lfloor \frac{N}{2}\rfloor\) it is sufficient to prove that the maximum time slots between two consecutive rendezvous is \(N+\lfloor \frac{N}{2}\rfloor -1\) (Lemma 3). Hence, the maximum possible time slots required for the first rendezvous between \(S_{A}\), and \(S_{B}\) is \(N+\lfloor \frac{N}{2}\rfloor -1+1=N +\lfloor \frac{N}{2}\rfloor\).

Theorem 2

MCTTR is \(N^{2}\)

Proof

MCTTR is the total time required to have rendezvous on all the available channels. Since there are N subsequences, and each subsequence has N slots, it can easily be calculated from Lemma 2 that MCTTR is \(N^{2}\) for a synchronous environment. For an asynchronous setting (Fig. 3b, if there is a \(\delta\) time slots drift between \(S_{A}\), and \(S_{B}\) then the following two cases are considered.

Case-1: \(\delta =mN\), where \(m=0,1,\ldots ,N-1\). Though the first subsequence y of \(S_{B}\) is not synchronized with x of subsequences of \(S_{A}\), but is synchronized with any one of the subsequence represented as rotate(x, j) (\(j=1,2,\ldots ,N-1\)). So all the N set of sender–receiver subsequences are synchronized with each other which leads to N number of rendezvous at N distinct channels according to Lemma 1 and 2. Therefore, MCTTR is \(N^{2}\).

Case-2: If \(mN<\delta < mN+N-1\), for any value \(\delta\) the subsequence will be delayed with \(\delta modN\) time slots from subsequence of \(x'=rotate(x,j)\) where \(j=0,1,\ldots ,N-1\). As shown in Fig. 3b, \(y'\) of \(S'_{B}\) is synchronized with each subsequences of \(S_{A}\). According to Lemma 1, and 2, N number of rendezvous occurs at N distinct channels. Thus, \(S_{A}\), and the delayed \(S_{B}\) will have MCTTR = \(N^{2}\).

Theorem 3

Channel loading is \(\frac{1}{N}\)

Proof

According to the proposed method, there are N alternative CH sequences, and N default CH sequences. Thus, the total number of different sequences is 2N. Considering multiple SUs in a CRN, at a particular time slot, there could only be two sequences with a common C channel. For example, with N=5, out of 10 number of possible distinct sequences only two CH sequences are with channel 4 at time slot 2, only two CH sequences are with channel 2 at time slot 7, and so on as shown below.

\(S_{A1}=\lbrace 1,0,{\textcircled {4}},3,2, 0,4,3,2,1, 4,3,2,1,0, 3,2,1,0,4, 2,1,0,4,3\rbrace\)

\(S_{A2}=\lbrace 0,4,3,2,1, 4,3,{\textcircled {2}},1,0, 3,2,1,0,4, 2,1,0,4,3, 1,0,4,3,2\rbrace\)

\(S_{A3}=\lbrace 4,3,2,1,0, 3,2,1,0,4, 2,1,0,4,3, 1,0,4,3,2, 0,4,3,2,1\rbrace\)

\(S_{A4}=\lbrace 3,2,1,0,4, 2,1,0,4,3, 1,0,4,3,2, 0,4,3,2,1, 4,3,2,1,0\rbrace\)

\(S_{A5}=\lbrace 2,1,0,4,3, 1,0,4,3,2, 0,4,3,2,1, 4,3,2,1,0, 3,2,1,0,4\rbrace\) and

\(S_{B1}=\lbrace 2,3,{\textcircled {4}},0,1, 2,3,4,0,1, 2,3,4,0,1, 2,3,4,0,1, 2,3,4,0,1\rbrace\).

\(S_{B2}=\lbrace 3,4,0,1,2, 3,4,0,1,2, 3,4,0,1,2, 3,4,0,1,2, 3,4,0,1,2 \rbrace\).

\(S_{B3}=\lbrace 4,0,1,2,3, 4,0,1,2,3, 4,0,1,2,3, 4,0,1,2,3, 4,0,1,2,3 \rbrace\).

\(S_{B4}=\lbrace 0,1,2,3,4, 0,1,{\textcircled {2}},3,4, 0,1,2,3,4, 0,1,2,3,4, 0,1,2,3,4 \rbrace\).

\(S_{B5}=\lbrace 1,2,3,4,0, 1,2,3,4,0, 1,2,3,4,0, 1,2,3,4,0, 1,2,3,4,0 \rbrace\).

Hence, channel loading = \(\frac{2}{2N}=\frac{1}{N}\).

Table 1 Performane comparision of rendezvous schemes
Full size table

5 Simulation Results

In this section, the performance of the proposed scheme is presented through extensive simulations using MATLAB (version R2018a). The performance metrics namely ETTR and MCTTR are used to test the efficiency of the proposed work and are compared with state-of-art algorithms such as EJS [18], CRSEQ [19], T-CH [17] and QS-CH [25]. For the simulation, random time slots drift between the CH sequence pair is considered for the asynchronous environment. Using a half-duplex radio, every SU opportunistically exploits the M licensed channels of the PUs available in the CRN. It is assumed that all the SUs are within the communication range of the PUs. Based upon their assigned role as sender or receiver, the SUs independently generate their CH sequence. The SUs start channel hopping periodically for a rendezvous with their CH sequence. Once the rendezvous on an available channel occurs, a communication link is established between them. For the case of the asymmetric model, a parameter G is considered to show the number of common channels between the available channel sets of two SUs. So \(G=\vert M_{A} \cap M_{B}\vert\), and symmetric model would be the special case under asymmetric model, where \(\vert M_{A}\vert = \vert M_{B}\vert\). For the evaluation of different performance metrics, 10,000 sets of simulations are performed and the average value is considered for the final result.

Fig. 5
figure 5

ETTR versus number of available channels (for the symmetric model with \(\vert M_{A}\vert = \vert M_{B}\vert =M'\))

Full size image

5.1 Impact of Number of Available Channels in Symmetric Model

For a symmetric model, considering \(\vert M_{A}\vert = \vert M_{B}\vert =M'\), simulation experiment was performed for different values of \(M'\) to compare the average TTR or ETTR. In the simulation \(M'\) varies from 5 to 50, and the corresponding ETTR values are shown in Fig. 5. From the graph, it is observed that ETTR is increasing with \(M'\). As the length of the CH sequences increases with the increase in number of available channels, the number of time slots that ensure guaranteed rendezvous also increases. For an asynchronous environment the upper bound of the TTR i.e., MTTR values for different CH schemes are mentioned in the Table 1. The MTTR of CRSEQ [19] is \(O(N^2)\), and though, the MTTR of EJS [18], T-CH [17], and QS-CH [25] are O(N), the values are still higher than the MTTR of the proposed R-CH scheme. Thus, the proposed scheme shows better performance in ETTR, as it has lower value of MTTR compared to the other CH schemes.

Fig. 6
figure 6

MCTTR versus number of channels

Full size image

5.2 Impact of Number of Licensed Channels

MCTTR value is increased with the number of licensed channels (M) as analyzed in the Theorem 2. The correctness of the analysis can be seen in the Fig. 6, which shows MCTTR for different numbers of M, when there is at least one channel common to \(M_{A}\) and \(M_{B}\). In this experiment, M varies from 10 to 50 and \(\vert M_{A}\vert = \vert M_{B}\vert\) = M is considered to investigate the total time required to achieve rendezvous at all the distinct available channels. This metric is very useful, since it indicates the average time needed for a guaranteed rendezvous in the worst case, where there is at least one channel common to the SU pair. MCTTR for different CH schemes are mentioned in the Table 1. In EJS [18] scheme, the jump and stay pattern varies with the time drifts in the asynchronous environment, and for an asymmetric model, both SUs have different stay, and jump patterns with the randomly chosen channels from their respective available channel sets. Thus, the number rendezvous decreases between long CH sequences (large M) in asynchronous environment, that results large MCTTR in EJS method. The MCTTR value for CRSEQ, and T-CH in the worst case is \(3N^{2}-N\) and 2\(N^{2}+\lfloor \frac{N}{2}\rfloor \times N\) respectively as shown in Table 1, which is still large compared to R-CH. However from the graph it is observed that QS-CH, and R-CH have nearly same MCTTR.

5.3 Impact of Number of Common Channels(G)

In this simulation, an asymmetrical model is considered, where the number of licensed channels is fixed to \(M=50\). The available channel sets of the SU pair are considered as \(\vert M_{A}\vert = 10\), and \(\vert M_{B}\vert = 15\). Figure 7 shows the ETTR values for different combination of available channel sets \(M_{A}\), and \(M_{B}\) such that \(G=\vert M_{A} \cap M_{B}\vert\) varies from 1 to 10. It is observed that for a fixed value of M, ETTR increases as the number of common channels decreases, on which there would be a possibility of rendezvous. High MCTTR tends to increase ETTR, while quick-rendezvous property tends to decrease ETTR. Though EJS has both the properties, compared to R-CH it has high MCTTR, which leads longer ETTR. The T-CH, and CRSEQ CH sequences do not show the quick rendezvous in asynchronous environment, and comparatively have higher MCTTR than R-CH. Since the proposed R-CH scheme has relatively small MCTTR value compared to others, this CH tends to have shorter ETTR in asymmetric model, as it also possesses the quick rendezvous property. The correctness of the analysis is reflected in Fig. 7, which proves, R-CH works better than the others in the asymmetric model in asynchronous environment.

Fig. 7
figure 7

ETTR versus number common channels, for asymmetric model with M = 50, \(\vert M_{A}\vert = 10\), and \(\vert M_{B}\vert = 15\)

Full size image
Fig. 8
figure 8

ETTR versus number of channels, for different value of G in the asymmetric model

Full size image

For the proposed R-CH scheme, the impact of G can further be analyzed with different number of licensed channels as shown in Fig. 8. The simulation is performed with the proposed scheme for different values of M (varies from 10 to 30), and for each M value, ETTR is found for different values G (varies from 2 to 8). In the graph, it is observed that ETTR is directly proportional to the M, and indirectly proportional to the number of common channels between the SUs.

6 Conclusion

A new channel hopping scheme is suggested in this paper, to achieve blind rendezvous in specific cognitive radio networks, where the SUs are pre-assigned with roles as sender and receiver, before the rendezvous. The proposed R-CH rendezvous scheme performs better in both the symmetric and asymmetric models as compared to the current role-based algorithms. In both synchronous, and asynchronous network environment, the suggested approach guarantees a maximum degree of rendezvous, with lower MCTTR and MTTR values.