A Rendezvous Scheme for Self-Organizing Cognitive Radio Sensor Networks

Abstract

Two or more nodes need to establish a link on an available channel in a cognitive radio (CR) sensor network when they want to transmit data. Rendezvous is the process by which the nodes explore the available channels to establish a link when they want to communicate with each other. The method of finding a common channel is a challenging problem. A dedicated common control channel simplifies the rendezvous process, but it may create a single point of failure. In this paper, we propose a hopping sequence algorithm to provide an effective method to implement a rendezvous without relying on a dedicated control channel. Our scheme achieves a successful rendezvous within a single period in a CR sensor network. Analytical and simulation results show that our proposed scheme outperforms the existing schemes in terms of time to rendezvous, fairness, degree of overlapping, and the effect by primary user appearance.

1. Introduction

Wireless sensor networks (WSNs) have been used in many applications, including home automation, personal health care, and surveillance [1]. They usually utilize the license-exempt industrial, scientific, and medical (ISM) band, but the ISM band is very crowded, since many other communication systems are already operating on it [2, 3]. The concept of self-organization is used to manage resources and guarantee users quality of service with communication networks like ad hoc and sensor networks [4]. It does not require any central coordination to establish a link. Instead, the nodes on the link interact directly with each other. As a solution to overcome the lack of available radio spectrum for wireless sensor networks, the cognitive radio (CR) technology can be considered [5]. A cognitive radio sensor network senses event signals and collaboratively transmits data dynamically over available spectrum bands in a multihop manner to ultimately satisfy application-specific requirements [5]. The communication architecture of a cognitive radio sensor network with self-organization is illustrated in Figure 1.

Figure 1

Cognitive radio sensor network with self-organization.

In CR sensor networks, CR users are secondary users (SUs) that coexist with primary users (PUs), and they continuously sense the radio environment for vacant frequency bands. When two nodes want to communicate with each other, they must exchange a control message on an unoccupied channel in CR sensor networks. Two nodes rendezvous on an available common channel to enable reliable exchange of control messages. Two nodes access a common channel for a certain period of time that is sufficiently long to establish a reliable link; this is referred to as rendezvous [4–6].

In recent years, many works have addressed the rendezvous problem and have tried to simplify it in different ways. The study of rendezvous problems categorize the existing solutions into two major groups based on their operations [7]. These are required and can be achieved by either a centralized approach using a dedicated control channel as a common control channel (CCC) or a distributed approach without using a CCC [7].

The use of a dedicated control channel (or CCC) simplifies the rendezvous process, as well as other medium access issues. However, a dedicated control channel has a number of important disadvantages. A dedicated control channel may become a bottleneck or may create a single point of failure. In addition, the dynamically changing availability of spectrum may make it impossible to maintain a dedicated control channel [8]. The availability of any one channel cannot be guaranteed in a CR network, because SUs must vacate any channel as soon as incumbent signals appear in the channel, thus making it impossible to guarantee the availability of the CCC [9].

We focus on a distributed approach where each node visits all channels in a redefined order using a sequence to guarantee successful rendezvous if there is an available channel. This can provide an effective method to implement a rendezvous without relying on a dedicated control channel. In this paper, we propose a hopping sequence algorithm to achieve a successful rendezvous within a single period in a CR network. With the proposed algorithm, called a hopping sequence guaranteeing rendezvous within a single period (HS-GRSP), CR nodes can rendezvous in a single period and reliably exchange control messages with each other.

2. Background and Related Works

2.1. Background

Figure 2 shows a model for the rendezvous of two nodes in a CR sensor network. For the rendezvous, node A starts first, and node B starts k slots later than node A (i.e., the time lag is k). Assuming that time slots of the sequence are synchronized, two nodes can visit the same channel using the sequence S simultaneously. In Figure 2, two nodes can successfully rendezvous at the seventh time slot.

Figure 2

Rendezvous system model.

2.2. Related Works

2.2.1. Quorum-Based Asynchronous Maximum Overlapping Channel Hopping (A-MOCH)

The quorum-based scheme was proposed for CCC establishment in CR networks [10]. The channel hopping sequence (CHS) is constructed from quorum systems which satisfy the intersection property and increase the degree of overlap between sequences. The A-MOCH system assumes at least one commonly available channel utilizing the rotation closure property of quorum systems to enable at least one rendezvous in $N^2$ time slots, where N is the total number of channels.

In an A-MOCH system, the pairwise rendezvous over N channels may occur during the last N time slots of a CH period, and thus the maximum time to rendezvous (MTTR) equals $N^2-N+1$ . If a PU returns to the CCC used for the rendezvous, all quorum-based CH systems (Figure 3) simply replace the CCC with a randomly selected available channel to avoid interfering with the PU. While this may increase the time to rendezvous (TTR) by a factor of N for synchronous quorum systems, it preserves the desired properties of quorum systems in the hopping sequences.

Figure 3

Quorum-based CH system [10].

2.2.2. Sequence-Based Rendezvous

Sequence-based rendezvous (SBR) [11] is an asynchronous CH system in which CR users construct nonorthogonal CHS's by using a permutation of available channels. The sequence is built as illustrated in Figure 4. The rendezvous sequence is made from a combination of permutations. The first step in building such a rendezvous sequence is to select a permutation of N channels (there are $N!$ such permutations). The selected permutation is interspersed with each element in the selected permutation. Therefore the selected permutation appears $(N+1)$ times in the rendezvous sequence. For example, if we select $\{\mathrm{1,3},2\}$ as a permutation when $N=3$ , the rendezvous sequence will be $\{\mathrm{1,1},\mathrm{3,2},\mathrm{3,1},\mathrm{3,2},\mathrm{2,1},\mathrm{3,2}\}$ . The sequence generated by the SBR scheme in a CR network with N channels has a period of $N(N+1)$ slots. The expected TTR is $N^2+N$ , and the maximum TTR is bounded by $N(N+1)$ time slots.

Figure 4

Building a sequence for sequence-based rendezvous [11].

2.2.3. Channel Rendezvous Sequence

The channel rendezvous sequence (CRSEQ) is based on the properties of triangular numbers and the Chinese Remainder Theorem [12]. In this algorithm, nodes A and B visit channels according to the rendezvous sequence, $a_i$ , made by

$$\begin{array}{cc}& a_i=\{\begin{array}{cc}z\hspace{0.17em}\mathrm{mod}\hspace{0.17em}N+\mathrm{1},\hfill & \text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0}\le y<\mathrm{2}N-\mathrm{1},\hfill \\ x\hspace{0.17em}\mathrm{mod}\hspace{0.17em}N+\mathrm{1},\hfill & \text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{2}N\le y<\mathrm{3}N-\mathrm{1},\hfill \end{array}\end{array}$$

(1)

where $z=((x(x+1)+y)/2)\mathrm{mod}N,\hspace{0.17em}x=\lfloor i/(3N-1)\rfloor$ , $y=i\mathrm{mod}(\mathrm{3}N-\mathrm{1})$ , and $\mathrm{0}\le i<N(\mathrm{3}N-\mathrm{1})$ . For example, the channel rendezvous sequence when $N=3$ is $\{\mathrm{1,2},\mathrm{3,1},\mathrm{2,1},\mathrm{1,1},\mathrm{2,3},\mathrm{1,2},\mathrm{3,2},\mathrm{2,2},\mathrm{1,2},\mathrm{3,1},\mathrm{2,3},\mathrm{3,3}\}$ . The channel rendezvous sequence has a period of $N(3N-1)$ slots, and the MTTR is $N(3N-1)$ slots.

2.2.4. Asynchronous Efficient Channel Hopping

In [13], asynchronous efficient channel hopping (ASYNC-ETCH) protocol was proposed. ASYNC-ETCH first constructs a set of CHSs when a CR node joins the network. It starts the CHS process immediately after construction of the CHS is done. Within a hopping period, a pair of nodes using ASYNC-ETCH that select the same CHS is guaranteed to rendezvous in one slot. In cases where they select two different CHSs, they are guaranteed to rendezvous within N time slots, no matter how their hopping processes are misaligned.

3. Hopping Sequence Guaranteeing Rendezvous within a Single Period

In this section, we propose an algorithm to generate a sequence for a rendezvous in CR networks. The sequence is used by each node to decide the order in which the available channels are to be visited. This sequence should guarantee a successful rendezvous, even when each node has joined the CR network at different times [14]. In the HS-GRSP, each node uses a rendezvous sequence to visit the available channels to search for each other, when each node starts to look for another node at different times.

3.1. Definitions

We assume that time slot T is divided into a number of slots with the same time interval, t, and we are given N channels denoted by $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},\dots ,{\text{CH}}_{\text{N}}\}$ .

Rendezvous sequence is defined as the order of the channels that each node visits for the rendezvous. For example, a rendezvous sequence   $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{5}},{\text{CH}}_{\mathrm{6}}\}$ means that each node should sequentially visit ${\text{CH}}_{\mathrm{1}}$ , ${\text{CH}}_{\mathrm{3}}$ , ${\text{CH}}_{\mathrm{5}}$ , and ${\text{CH}}_{\mathrm{6}}$ . Each element in the sequence is called a term.

Time lag, denoted by k, is the difference between the visiting times of the nodes for the rendezvous. The time lag k is a nonnegative integer expressed as the number of time slots.

Center channel means the channel located at the center position of the available channel list. If we are given N available channels, then the center channel is given by ${\text{CH}}_{N/2}$ .

Subsequence is a sequence that can be derived from another sequence by choosing some contiguous terms without changing the order. For example, from the sequence $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{4}},{\text{CH}}_{\mathrm{5}}\}$ , we can get two subsequences with a length of 4: $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{4}}\}$ and $\{{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{4}},{\text{CH}}_{\mathrm{5}}\}$ .

Group sequence is defined by a subsequence that has a certain local regularity when the sequence is partitioned into specific groups. For example, the sequence {CH₁, CH₄, CH₃, CH₂, CH₁, CH₂, CH₃, CH₂, CH₁, CH₃, CH₂, CH₁, CH₄, CH₁} consists of four group sequences $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{4}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}}\}$ , and $\{{\text{CH}}_{\mathrm{4}},{\text{CH}}_{\mathrm{1}}\}$ .

3.2. Algorithm

Suppose there are N available channels in a cognitive radio network, where N is a prime number. The proposed rendezvous sequence consists of two parts: group sequence and guard sequence. First, we generate a chain sequence by catenating N group sequences. The first term of each group sequence is given by the group index, and the remaining terms (from the second to the last) are given by the arithmetic sequence in reverse order. For example, if there are three available channels ( $N=3$ ), then we generate three group sequences $\{{\mathbf{C}\mathbf{H}}_{\mathbf{1}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\mathbf{C}\mathbf{H}}_{\mathbf{2}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}}\}$ , and $\{{\mathbf{C}\mathbf{H}}_{\mathbf{3}},{\text{CH}}_{\mathrm{1}}\}$ (the first term is marked in bold for easier visualization). So, its chain sequence will be  $\{{\mathbf{C}\mathbf{H}}_{\mathbf{1}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}},{\mathbf{C}\mathbf{H}}_{\mathbf{2}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}},{\mathbf{C}\mathbf{H}}_{\mathbf{3}},{\text{CH}}_{\mathrm{1}}\}$ by catenating the three group sequences.

Next, we generate a guard sequence to guarantee rendezvous within the bounded time by repeating the center channels. The length of the guard sequence is given by the number of channels from the last center channel to the end of the chain sequence. For the channel list $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}}\}$ , for example, the guard sequence becomes $\{{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{2}}\}$ since the distance from last center channel to the end of the chain sequence is 4 as illustrated below:

$$\begin{array}{cc}& \left\{{\mathbf{C}\mathbf{H}}_{\mathbf{1}},{\text{CH}}_{\mathrm{3}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}},{\mathbf{C}\mathbf{H}}_{\mathbf{2}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}},{\mathbf{C}\mathbf{H}}_{\mathbf{3}},{\text{CH}}_{\mathrm{1}}\right\}.\end{array}$$

(2)

Last, the rendezvous sequence is made by merging the chain sequence and the guard sequence. As a result, the rendezvous sequence consists of one or more group sequences following a guard sequence. This rendezvous sequence can be used by each node for visiting channels to rendezvous (Table 1).

Table 1

Generation of the group sequences, the guard sequence, and the rendezvous sequence.

Number of available channels	Group sequence	Guard sequence	Rendezvous sequence
1	{CH1, CH1, CH1}	{CH1, CH1}	{CH1, CH1, CH1}
2	{CH1, CH2, CH1}, {CH2, CH1}	{CH1, CH1}	{CH1, CH2, CH1, CH2, CH1, CH1, CH1}
3	{CH1, CH3, CH2, CH1}, {CH2, CH2, CH1}, {CH3, CH1}	{CH2, CH2, CH2, CH2}	{CH1, CH3, CH2, CH1, CH2, CH2, CH1, CH3, CH1, CH2, CH2, CH2, CH2}
4	{CH1, CH4, CH3, CH2, CH1}, {CH2, CH3, CH2, CH1}, {CH3, CH2, CH1}, {CH4, CH1}	{CH2, CH2, CH2, CH2}	{CH1, CH4, CH3, CH2, CH1, CH2, CH3, CH2, CH1, CH3, CH2, CH1, CH4, CH1, CH2, CH2, CH2, CH2}
⋮	⋮	⋮	⋮
N	{CH1, ${\text{CH}}_N$ , ${\text{CH}}_{N-\mathit{1}}$ , …, CH1}, {CH2, ${\text{CH}}_{N-\mathit{1}}$ , ${\text{CH}}_{N-\mathit{2}}$ , …, CH1}, …, $\{{\text{CH}}_{N-\mathit{1}}$ , CH2, CH1}, {CHN, CH1}	$\{{\text{CH}}_{\mathrm{N}/\mathrm{2}}$ , ${\text{CH}}_{\mathrm{N}/\mathrm{2}}$ , ${\text{CH}}_{\mathrm{N}/\mathrm{2}}$ , …, ${\text{CH}}_{\mathrm{N}/\mathrm{2}}\}$	{CH1, ${\text{CH}}_N$ , ${\text{CH}}_{N-\mathit{1}}$ , …, CH1, CH2, ${\text{CH}}_{N-\mathit{1}}$ , ${\text{CH}}_{N-\mathit{2}}$ ,…, CH1,…, ${\text{CH}}_{N-\mathit{1}}$ , CH2, CH1, ${\text{CH}}_N$ , CH1, ${\text{CH}}_{\mathrm{N}/\mathrm{2}}$ , ${\text{CH}}_{\mathrm{N}/\mathrm{2}}$ , ${\text{CH}}_{\mathrm{N}/\mathrm{2}}$ ,…,  ${\text{CH}}_{\mathrm{N}/\mathrm{2}}\}$

In general, when there are N available channels, the rendezvous sequence S is given by

$$\begin{array}{l}S=\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_N,{\text{CH}}_{N-1},\dots ,{\text{CH}}_{\mathrm{2}},{\text{CH}}_{N-1},{\text{CH}}_{N-2},\dots ,\\ \hspace{1em}\hspace{1em}\hspace{0.17em}{\text{CH}}_{N-1},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{1}},{\text{CH}}_N,{\text{CH}}_{\mathrm{1}},{\text{CH}}_{N/2},\\ \hspace{1em}\hspace{0.17em}\hspace{1em}{\text{CH}}_{N/2},\dots ,{\text{CH}}_{N/2}\}.\end{array}$$

(3)

As shown in Figure 5, the length of the guard sequence of a channel list $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{2}},{\text{CH}}_{\mathrm{3}},\dots ,{\text{CH}}_N\}$ is given by

$$\begin{array}{cc}& T_{\text{guard}}=\frac{N^{\mathrm{2}}+\mathrm{6}N-\mathrm{8}}{\mathrm{8}}.\end{array}$$

(4)

So, the length of our proposed sequence is given by

$$\begin{array}{cc}& T=\frac{\mathrm{5}{N}^{\mathrm{2}}+\mathrm{18}N-\mathrm{8}}{\mathrm{8}}.\end{array}$$

(5)

Figure 5

Length of a rendezvous sequence by HS-GRSP.

3.3. Mechanism for PU Appearance

Unlike an SU, a PU is a licensed user who can arrive unexpectedly at any time and on any channel, including a rendezvous channel. The appearance of a PU disturbs SU's activity and may lead to link breakage. The appearance of a PU significantly degrades performance of the rendezvous since the channel(s) occupied by the PU must not be used for rendezvous until the PU leaves the channel. So CR users need to have a mechanism by which they sense and handle PU's appearance. The easiest way is preventing CR users from hopping to that particular channel until the PU leaves.

Figure 6 is the rendezvous mechanism for PU appearance in our scheme.

Figure 6

Rendezvous mechanism for PU appearance.

4. Performance Evaluation

We evaluated the HS-GRSP scheme in terms of four performance criteria, including TTR (ATTR and MTTR), effect of PU appearance, fairness of channel utilization, and degree of overlapping. And we compared their performance with the existing schemes available in the current literature. Comparison targets were SBR, CRSEQ, ASYNC-ETCH, and A-MOCH.

Performance evaluation was done by theoretical analysis and simulation. The CR sensor network is assumed to have 2 to 30 rendezvous channels, each of which could be occupied by a PU at any time. All SUs are supposed to be within communication range of the PU. In the simulation, we first randomly decide whether the PU is detected or not using a Poisson distribution. If the PU appears, we disable the rendezvous channel during a random period of time. Otherwise, all rendezvous channels are made available to the nodes during a random period of time. Every node randomly picks one sequence and performs channel hopping according to the sequence to exchange data packets after acquiring the common channel. The sender follows the receiver's sequences. We repeated this process during the entire simulation. Table 2 shows the simulation parameters.

Table 2

Parameters used for simulation.

Parameters	Values
Number of channels	2~30
PU appearance pattern	Poisson distribution
Duration of PU activity	Exponential distribution
Number of CR nodes	2~10
Number of PU nodes	One PU per channel

4.1. TTR Performance

We studied the performance of the HS-GRSP scheme in terms of TTR. TTR is the time needed for any two CR devices to rendezvous using hopping sequences and is measured by the number of time slots elapsed from the reference time to the rendezvous time. First, we show that our algorithm can guarantee a successful rendezvous of two nodes within a bounded time in a CR sensor network. That is, we show that at least one time slot exists in which nodes A and B both visit the same channel simultaneously within a single period in the worst case (Figure 7).

Figure 7

Rendezvous of nodes A and B when there are N channels.

When $N=1$ and $k=0$ , they certainly rendezvous in the first time slot, since they start searching simultaneously.

• (a)

  When $N=1$ and $k=1$ , we get rendezvous sequences for nodes A and B as follows:

  $$\begin{array}{l}{S}_A=\left\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\right\},\\ S_B=\left\{\mathrm{0},{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\right\},\end{array}$$

  (6)

  where the term “0” indicates no action. This signifies that node B starts the search process in the second time slot. The subsequences of $S_A$ and $S_B$ are $S_A^{\prime }=\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\}$ and $S_B^{\prime }=\{\mathrm{0},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{1}}\}$ , respectively (Table 3). All subsequences with a length of 2 have at least 1 center channel $({\text{CH}}_{N/2})$ in common. In this case, two nodes rendezvous two time slots after node A begins the search process, as illustrated in Figure 8.

• (b)

  When $N=3$ and $k=2$ , nodes A and B can rendezvous in the fifth slot using rendezvous sequences generated by our algorithm.

• (c)

  Assuming that node A starts first, and node B starts four time slots later (i.e., $k=7$ ), they can rendezvous at the tenth time slot by generated sequence S, as depicted in Figure 8.

In general, the MTTR with the HS-GRSP scheme is the same as the length of the rendezvous sequence. This means that HS-GRSP guarantees successful rendezvous within a single period. We have

$$\begin{array}{cc}& \text{MTTR}=\frac{\mathrm{5}{N}^{\mathrm{2}}+\mathrm{18}N-\mathrm{8}}{\mathrm{8}}.\end{array}$$

(7)

In HS-GRSP, we can get ATTR by averaging TTR values for all possible time drifts with a simple calculation:

$$\begin{array}{cc}& \text{ATTR}=E\left[\text{TTR}\right]=\frac{N^{\mathrm{2}}-\mathrm{2}N+\mathrm{6}}{\mathrm{2}}.\end{array}$$

(8)

Table 3

Subsequences $S^{\prime }$ .

Number of available channels	Subsequence $S^{\prime }$
1	{CH1, CH1}, {CH1, CH1}
2	{CH1, CH2}, {CH2, CH1}, {CH1, CH2}, {CH2, CH1}, {CH1, CH1}, {CH1, CH1}
3	{CH1, CH3, CH2, CH1}, {CH3, CH2, CH1, CH2}, {CH2, CH1, CH2, CH1}, {CH1, CH2, CH2, CH1}, {CH2, CH2, CH3, CH1}, {CH2, CH1, CH3, CH1}, {CH1, CH3, CH1, CH2}, {CH3, CH1, CH2, CH2}, {CH1, CH2, CH2, CH2}, {CH2, CH2, CH2, CH2}
4	{CH1, CH4, CH3, CH2}, {CH4, CH3, CH2, CH1}, {CH3, CH2, CH1, CH2}, {CH2, CH1, CH2, CH3}, {CH1, CH2, CH3, CH2}, {CH2, CH3, CH2, CH1}, {CH3, CH2, CH1, CH3}, {CH2, CH1, CH3, CH2}, {CH1, CH3, CH2, CH1}, {CH3, CH2, CH1, CH4}, {CH2, CH1, CH4, CH1}, {CH1, CH4, CH1, CH2}, {CH4, CH1, CH2, CH2}, {CH1, CH2, CH2, CH2}, {CH2, CH2, CH2, CH2}
⋮	⋮
N	$\{{\text{CH}}_{\mathrm{1}},{\text{CH}}_{\mathrm{N}},{\text{CH}}_{\mathrm{N}-\mathrm{1}},\dots ,{\text{CH}}_{\mathrm{N}/\mathrm{2}},\dots ,{\text{CH}}_{\mathrm{2}}\}$ , $\{{\text{CH}}_{\mathrm{N}},{\text{CH}}_{\mathrm{N}-\mathrm{1}},{\text{CH}}_{\mathrm{N}-\mathrm{2}},\dots ,{\text{CH}}_{\mathrm{N}/\mathrm{2}},\dots ,{\text{CH}}_{\mathrm{1}}\}$ , $\{{\text{CH}}_{\mathrm{N}-\mathrm{1}},{\text{CH}}_{\mathrm{N}-\mathrm{2}},{\text{CH}}_{\mathrm{N}-\mathrm{3}},\dots ,{\text{CH}}_{\mathrm{N}/\mathrm{2}},\dots ,{\text{CH}}_{\mathrm{N}-\mathrm{1}}\}$ , …, $\{{\text{CH}}_{\mathrm{N}/\mathrm{2}},{\text{CH}}_{\mathrm{N}/\mathrm{2}},{\text{CH}}_{\mathrm{N}/\mathrm{2}},\dots ,{\text{CH}}_{\mathrm{N}/\mathrm{2}}\}$

Figure 8

Examples of the rendezvous process.

We compare the TTR performance of the HS-GRSP, together with SBR, CRSEQ, ASYNC-ETCH, and A-MOCH. Figure 9 shows ATTR and MTTR achieved with those five channel hopping protocols. Figure 9(b) indicates that the maximum rendezvous time linearly grows as the number of channels increases. As seen from this figure, HS-GRSP provides the best performance of the five CH protocols in terms of MTTR for all values of N. Also, we can see that our algorithm offers a shorter average rendezvous time than SBR and CRSEQ. So, HS-GRSP can be used to reduce the delay of medium access control (MAC) protocols for a CR sensor network. In CRSEQ, it may take a long time to find a neighboring node on a channel to exchange control information, especially when the number of available channels is large.

Figure 9

TTR performance of channel hopping protocols.

4.2. Effect of PU Appearance on TTR

The appearance of a PU highly affects TTR of the hopping sequence since the channel occupied by the PU cannot be used anymore for conducting the rendezvous until the PU leaves the channel.

Assuming the PU appears on the channel for a time slot with a probability of p, then the probability that a given channel is occupied by the PU (i.e., the PU appears on a given channel at least one time) during a of hopping sequence period will be

$$\begin{array}{cc}& P_{\text{PU}}={\mathrm{1}-\left(\mathrm{1}-\rho \right)}^T,\end{array}$$

(9)

where T is the period of the hopping sequence.

As described earlier, the hopping sequence period with HS-GRSP is $(5N^2+18N-8)/8$ . Thus, during a hopping sequence period (denoted by M), the average number of channels occupied by a PU during will be

$$\begin{array}{cc}& M=N·P_{\text{PU}}=N\left({\mathrm{1}-\left(\mathrm{1}-\rho \right)}^{\left(\mathrm{5}{N}^{\mathrm{2}}+\mathrm{18}N-\mathrm{8}\right)/\mathrm{8}}\right).\end{array}$$

(10)

Now, we can get ATTR under the impact of PU activity in a CR network with N channels as follows:

$$\begin{array}{cc}& \text{ATT}{\text{R}}^{\prime }=\frac{N\left((N^{\mathrm{2}}-\mathrm{2}N+\mathrm{6})/\mathrm{2}\right)}{N-M}=\frac{\left(\mathrm{1}/\mathrm{2}\right)\left(N^{\mathrm{2}}-\mathrm{2}N+\mathrm{6}\right)}{{\left(\mathrm{1}-\rho \right)}^{(\mathrm{5}{N}^{\mathrm{2}}+\mathrm{18}N-\mathrm{8})/\mathrm{8}}}.\end{array}$$

(11)

From (8) and (11), we can express the effect of the PU appearance on ATTR performance with HS-GRSP with the following impact factor, f:

$$\begin{array}{cc}& f=\frac{\text{ATT}{\text{R}}^{\prime }}{\text{ATTR}}=\frac{N}{N-M}=\frac{\mathrm{1}}{{\left(\mathrm{1}-\rho \right)}^{(\mathrm{5}{N}^{\mathrm{2}}+\mathrm{18}N-\mathrm{8})/\mathrm{8}}}.\end{array}$$

(12)

The impact factor indicates the increasing ratio of ATTR when the PU appears on its own channel for a time slot with probability p.

As seen in Figure 10(a), our scheme is not significantly affected by the appearance of the PU regardless of the number of available channels. We can see that ATTR with our scheme does not rise meaningfully for all values of N, although the probability of a PU appearance increases. This means that our scheme provides a very stable performance in ATTR under the impact of the PU appearance.

Figure 10

PU impact factor.

4.3. Fairness of Channel Utilization and Degree of Overlapping Performance

Fairness of channel utilization can be expressed by a reciprocal value of the normalized standard deviation of the number of channels used for rendezvous by CR nodes. Even distribution of rendezvous channels over different time slots is an important requirement in order to overcome the rendezvous convergence problem. If a large proportion of neighboring nodes rendezvous on the same channel, then channel congestion can occur and lead to a control channel bottleneck problem [12]. Therefore, the rendezvous should spread out evenly over all channels. As the fairness of channel utilization increases, network capacity at the communication setup stage becomes proportionally large.

Figure 11 shows that in CRSEQ and SBR, fairness of channel utilization is inversely proportional to the number of channels, whereas fairness with HS-GRSP is not significantly affected by the number of channels, although it shows a small fluctuation. In CRSEQ, the rendezvous channels are not found with equal probability in a given period. Such unfair distributions may result in traffic load on certain channels over more than others. On the other hand, with HS-GRSP and SBR, the possibility of rendezvous convergence is low because different pairs of sender and receiver are likely to construct different pairs of alternative and default hopping sequences, and thus, the rendezvous points (in terms of frequency and time) of those hopping sequence pairs are different.

Figure 11

Fairness of channel utilization with channel hopping protocols.

Degree of overlap refers to the number of time slots in which any two sequences can overlap within one sequence period, or can intersect, to ensure any one pair of nodes is able to communicate. If two ith slots are the same for two CH sequences $S_A$ and $S_B$ (i.e., $S_{A[i]}=S_{B[i]}$ ), then this slot is called an overlapping or rendezvous slot between $S_A$ and $S_B$ . Figure 12 shows that CRSEQ offers the highest degree of overlap, whereas SBR only overlaps at a single rendezvous point per channel between any two given sequences. In HS-GRSP, the degree of overlapping linearly increases as the number of available channels increases above 5. This contributes to achieving a very short MTTR with HS-GRSP.

Figure 12

Degrees of overlap.

4.4. Comparison Summary

Finally, we compared HS-GRSP using five metrics: ATTR, MTTR, PU impact factor, fairness of channel utilization, and degree of overlapping. Table 4 summarizes the comparison results, where N is the number of channels used in the CR network and p is the probability that a PU appears on the channel in a time slot.

Table 4

Comparison of channel hopping schemes.

CH protocol	ATTR	MTTR	PU impact factor	Fairness of rendezvous channel utilization	Degree of overlapping
ASYNC-ETCH	$\frac{{\mathit{2}N}^{\mathit{2}}+N}{N-\mathit{1}}$	—	$\frac{\mathit{1}}{{\left(\mathit{1}-\rho \right)}^{\mathit{2}N-\mathit{1}}}$	High	At least 1
A-MOCH	—	$N^{\mathit{2}}-N+\mathit{1}$	$\frac{\mathit{1}}{{\left(\mathit{1}-\rho \right)}^{N^{\mathit{2}}}}$	High	High
SBR	$\frac{N^{\mathit{2}}+N}{\mathit{2}}$	$N^{\mathit{2}}+N$	$\frac{\mathit{1}}{{\left(\mathit{1}-\rho \right)}^{N(N+\mathit{1})}}$	High	At least 1
CRSEQ	$\frac{{\mathit{3}N}^{\mathit{2}}-\mathit{3}N}{\mathit{2}}$	$N(\mathit{3}N-\mathit{1})$	$\frac{\mathit{1}}{{\left(\mathit{1}-\rho \right)}^{N(\mathit{3}N-\mathit{1})}}$	Low	High
HS-GRSP	$\frac{N^{\mathit{2}}-\mathit{2}N+\mathit{6}}{\mathit{2}}$	$\frac{\mathit{5}{N}^{\mathit{2}}+\mathit{18}N-\mathit{8}}{\mathit{8}}$	$\frac{\mathit{1}}{{\left(\mathit{1}-\rho \right)}^{(\mathit{5}{N}^{\mathit{2}}+\mathit{18}N-\mathit{8})/\mathit{8}}}$	High	At least 1

5. Conclusion

In this paper, we propose an asynchronous channel hopping mechanism, called HS-GRSP, to establish a control channel in self-organizing CR sensor networks. We illustrate how two nodes wishing to communicate perform channel hopping in order to form a rendezvous point within an upper bound using our algorithm. We evaluated the performance of HS-GRSP and compared it with other schemes in the literature. Theoretical and simulation results showed that HS-GRSP provides successful communication rendezvous within a single period. HS-GRSP provides superior performance in terms of MTTR and shows very stable performance in ATTR under the effects of PU appearance, even when the number of channels increases. Thus, HS-GRSP can be used to successfully reduce delay of MAC protocols. Moreover, the possibility of rendezvous convergence is low with HS-GRSP because its fairness is not significantly affected by the number of channels. In HS-GRSP, the degree of overlapping linearly increases as the number of available channels increases above 5. This contributes to achieving a very short MTTR with HS-GRSP.