Open AccessArticle

New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks

Yaoxuan Wang

Xianhua Niu

^1,*

Chao Qi

¹,

Zhihang He

¹ and

Bosen Zeng

Department of Computer and Software Engineering, Xihua University, Chengdu 610039, China

Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, China

Author to whom correspondence should be addressed.

Entropy 2023, 25(10), 1473; https://doi.org/10.3390/e25101473

Submission received: 15 August 2023 / Revised: 15 October 2023 / Accepted: 20 October 2023 / Published: 22 October 2023

(This article belongs to the Special Issue Coding and Entropy)

Download

Browse Figures

Review Reports Versions Notes

Abstract

The channel-hopping-based rendezvous is essential to alleviate the problem of under-utilization and scarcity of the spectrum in cognitive radio networks. It dynamically allows unlicensed secondary users to schedule rendezvous channels using the assigned hopping sequence to guarantee the self-organization property in a limited time. In this paper, we use the interleaving technique to cleverly construct a set of asynchronous channel-hopping sequences consisting of d sequences of period

x N^{2}

with flexible parameters, which can generate sequences of different lengths. By this advantage, the new designed CHSs can be used to adapt to the demands of various communication scenarios. Furthermore, we focus on the improved maximum-time-to-rendezvous and maximum-first-time-to-rendezvous performance of the new construction compared to the prior research at the same sequence length. The new channel-hopping sequences ensure that rendezvous occurs between any two sequences and the rendezvous times are random and unpredictable when using licensed channels under asynchronous access, although the full degree-of-rendezvous is not satisfied. Our simulation results show that the new construction is more balanced and unpredictable between the maximum-time-to-rendezvous and the mean and variance of time-to-rendezvous.

Keywords:

cognitive radio networks; channel-hopping sequence; asynchronous

1. Introduction

Cognitive radio is one proposed solution to address the issue of limited spectrum resources in wireless communication systems and enhance spectrum utilization. The fundamental concept is to enable wireless communication devices to locate and utilize “spectrum holes” intelligently [1,2]. In cognitive radio networks, the communication between secondary users (SUs) requires a rendezvous point to establish an initial communication link by acquiring a common control channel through a spectrum database [3]. However, this centralized approach cannot avoid conflicts and control channel bottlenecks in a multi-channel, multi-user scenario [4], so it is more challenging to implement a rendezvous based on a distributed approach [5]. Figure 1 depicts the rendezvous between SUs through a distributed approach. SUs communicate in pairs, and when the primary user (PU) occupies the licensed channel, the SUs experience interference. Thus, the SUs rendezvous fails. The PU shares the licensed channels with the unlicensed SUs. When two SUs jump to the same licensed channel, rendezvous communication can be achieved. In most wireless communication technologies, the channel-hopping sequence (CHS) is a typical technique to achieve distribution.

CHS methods are generally classified by different symmetric/asymmetric roles and synchronous/asynchronous modes [6]. The symmetric role usually refers to the flexibility of SUs to act as a sender and a receiver with only one CHS. For example, a group of radio intercoms communicates, where the user’s intercom acts as the receiver. When a user sends a message over the walkie-talkie, that user’s walkie-talkie acts as the sender at that time. When the other users reply to the news, the user’s walkie-talkie picks it up and converts it to an audio signal. In contrast, the asymmetric role requires two separate CHSs to be assigned to each SU in advance to serve as the receiver [7]. When there are many SUs, it is evident that the symmetric role is more beneficial than the asymmetric one, and the symmetric part can be appropriately converted to the asymmetric position [6].

In the synchronization model, the SUs must operate within strict time constraints to ensure they send and receive information in the correct channel. Therefore, global synchronization is critical because all SUs must operate on the same schedule. However, in the asynchronous model, SUs can operate according to their propagation times (i.e., self-organization). They can be partially synchronized with other SUs to handle propagation delays and timing issues more flexibly [8]. Figure 2 shows three users that each have an independent CHS and communicate two-by-two at different time delays. Users can communicate with each other as long as they hop into the same licensed channel simultaneously. Due to the advantages mentioned above, therefore, asynchronous symmetric CHSs are investigated in this paper.

In order to address issues such as a higher parameter demand and maximum-time-to-rendezvous (MTTR) and maximum-first-time-to-rendezvous (MFTTR) performance, this paper focuses on a set of CHSs with new parameters that can be obtained with more CHSs of different lengths suitable for different scenarios. These sequences have shorter MTTR and MFTTR when equipped with the same parameters. The article’s structure is shown below: Section 2 briefly compares existing CHSs and summarizes the contribution. Section 3 describes in detail the natural number of field CHSs with new parameters. In Section 4, a comprehensive analysis of the characteristics of the new and existing constructions is provided by the simulation results. Finally, Section 5 summarizes and generalizes the previous studies and results.

2. Related Work and Contribution

Referring to the previous work, in the literature [9,10,11], the CHSs are designed under full degree-of-rendezvous(DoR) constraint. While in the literature [12,13,14,15,16], the CHSs are designed focusing on good MTTR and MFTTR performance without full DoR constraint, these CHSs are also applicable in many communication scenarios.

Liu [12] proposed a blind rendezvous algorithm, which employs a jump–stay strategy. In this algorithm, unavailable channels are randomly replaced with available channels to increase the chances of rendezvous. It is suitable for scenarios with multiple users and multiple hops. Bian [13] proposed a novel distributed protocol based on “neighbourhood diversity”. This protocol enables highly differentiated node encounters by selecting the optimal encounter channel and spectrum. Chuang [14] developed a method to achieve rendezvous in a cognitive radio network. The method involves alternating between frequency hopping and waiting algorithms, enabling nodes to efficiently locate available communication channels without needing global time synchronization. Sheu [9] proposed an asynchronous Quorum-based blind rendezvous scheme to achieve coordination between nodes by nodes communicating on different channels and time slots. Yang [10] has proposed a rendezvous algorithm based on Disjoint Set Cover (DSC) called Disjoint Set Cover Rendezvous (DSCR) to overcome limitations such as clock synchronization. DSC is utilized to adjust the arrangement of access channels, enabling users to quickly and efficiently rendezvous on all available channels. New asynchronous symmetric CHS were constructed, and their properties of channel overlap, even channel usage and pairwise shift invariance were investigated [15]. Chang [16] provided a new solution to improve the efficiency and effectiveness of rendezvous in cognitive radio networks by closing the theoretical gap in the multichannel rendezvous problem and introducing the IDEAL-CH sequence with an asymptotic approximation ratio of 2. Yang [11] developed a set of asynchronous CHSs based on IDs in a homogeneous setting. Their approach involved utilizing matrices and prime numbers to create algebraic algorithms.

Generally speaking, with the development of wireless networks and communication scenarios, the design of CHSs has the following two demands:

1. Due to the variety of wireless network topologies, more CHSs with different lengths are needed to support the communications. The existing work designed CHSs of length L as a function of

N^{2}

[9,12,13,14] or prime p [10,11,15,16].

2. Since shorter MTTR and MFTTR can improve the system throughput and spectrum utilization, new CHSs with short MTTR and MFTTR are demanded. The MTTR and MFTTR of [9,10,14] are shown in columns 2 and 3 of Table 1.

To meet the demand of CHSs in various communication scenarios, this paper focuses on using the interleaving to cleverly design CHSs consisting of d sequences of period

x N^{2}

with new parameters, which can generate sequences of different lengths and achieve shorter MTTR and MFTTR. The newly designed CHSs can be applied to various communication scenarios with complex network topologies. Using the designed new set of CHSs, the new construction can generate shorter sequences for better application where the network topology is changing rapidly; conversely, the new construction can also generate longer sequences for duration communication, thus, making communication safer and more reliable. The main contributions of this paper are:

(1) The new construction extends the period-length results of the existing constructions [9,11,13,15,16]. When N is a natural number, the period results from [9,13] are a special case of the results of our Theorem 2. When N = prime p, the period results from [11,15,16] are special cases of our Corollary 1 result.

(2) Compared to the previous studies without full DoR [12,13,14,15,16], the novel construction places its emphasis on achieving improved MTTR and MFTTR performance at identical sequence lengths when compared to the existing literature, although the full DoR is not satisfied. For example, when

x = 6

and

l = 1

, our constructed sequence has MTTR =

3 N^{2}

and MFTTR =

3 N^{2}

; whereas in [13], MTTR =

6 N^{2} - N + 1

and MFTTR =

6 N^{2}

. When

N = p

and

x = 2

, the MTTR =

2 p - 1

of our constructed sequence is 1 smaller than in [11], while the MFTTR is equal. Thus, the new CHS has smaller MTTR and MFTTR, but longer throughput.

3. Construction of Channel Hopping Sequence Sets with New Parameters Based on Natural Numbers

We created CHS sets by a unique interleaving construction in the natural number field. This method uses natural number sequences to construct

x N^{2}

CHSs with new parameters, called NPCH. It is guaranteed that any two shifted copies of the CHS set will have a mutual rendezvous with an integer

N \geq 3

. The

x N^{2}

CHS satisfy an irregular time-to-rendezvous (TTR) pattern, which makes the new CHS set unpredictable and unreliable during communication rendezvous. This design ensures reliability. Table 1 in Section 2 shows that this construction has the shortest MTTR and MFTTR under the same conditions.

3.1. NPCH Construction

Construction 1.Construction of CHS sets

Step 1: Choose an integer

N \geq 3

and

γ \in Z_{N}^{*}

with the largest multiplicative order. Let

o r d (γ) = d

with maximum value

φ (N)

, where

φ

is the Euler function. Without loss of generality,

d = φ (N)

Step 2: For any

λ \in [0, d - 1]

, the CHS

S^{λ}

can be written as:

S^{λ} = [\begin{matrix} s_{0, 0}^{λ} & s_{0, 1}^{λ} & \dots & s_{0, N - 1}^{λ} \\ s_{1, 0}^{λ} & s_{1, 1}^{λ} & \dots & s_{1, N - 1}^{λ} \\ ⋮ & ⋮ & \dots & ⋮ \\ s_{N - 1, 0}^{λ} & s_{N - 1, 1}^{λ} & \dots & s_{N - 1, N - 1}^{λ} \end{matrix}]

where

s_{α, β}^{λ} = γ^{λ} (α + β + λ) (\mod N)

(1)

α, β \in [0, N - 1]

Step 3: For any

λ \in [0, d - 1]

, the CHS

M^{λ}

can be obtained by stringing the matrix

S^{λ}

x times, which can be expressed as follows:

\underset{x}{\underset{⏟}{[S^{λ} | \dots | S^{λ}]}}

The specific algorithm is described in Algorithm 1.

Algorithm 1: Algorithm to generate CHS set with new parameters.

Input: Integer

N \geq 3

, x

Output: Channel-hopping sequences set

M = {M^{λ} | λ \in [0, d - 1]}

1:: $γ \leftarrow$ max(find_primitive_roots(N));
2:: set $λ = {0, 1, . . ., d - 1}$ , $d = φ (N)$ ; // $φ$ is the Euler function;
3:: $S []$ ← generate_matrix(N, $λ$ , $γ$ );
4:: for $i = 0$ to x do
5:: if $i = = 0$ then
6:: $M^{λ}$ ← $S []$ ;
7:: else
8:: $M^{λ}$ ← $[M^{λ} | S]$ ;
9:: end if
10:: end for
11:: return $M^{λ}$ ← expand $M^{λ}$ line by line.

3.2. Constructive Analysis

Since the new construction rendezvous is generated by the

x N^{2}

CHS “horizontal” and “vertical” shifts, Theorem 1 below shows that channel rendezvous is guaranteed in any two shifted CHSs.

Theorem 1.

The set

M

in Construction 1 is CHS set with d sequences of period

x N^{2}

, and there is at least one rendezvous between any two CHSs in the set at any time delay τ for any

N \geq 3

Proof.

It is easily checked that the CHS set

M

in Construction 1 is with d sequences of length

L = x N^{2}

for any

N \geq 3

. Next, we prove that the rendezvous point of any two sequences in

M

is at least one.

For any

λ_{1} \in [0, d - 1]

, the CHS

M^{λ_{1}}

can be expressed by the

N \times x N

matrix as follows:

[\begin{matrix} s_{0, 0}^{λ_{1}} & \dots & s_{0, N - 1}^{λ_{1}} & \dots & s_{0, 0}^{λ_{1}} & \dots & s_{0, N - 1}^{λ_{1}} \\ s_{1, 0}^{λ_{1}} & \dots & s_{1, N - 1}^{λ_{1}} & \dots & s_{1, 0}^{λ_{!}} & \dots & s_{1, N - 1}^{λ_{1}} \\ ⋮ & \dots & ⋮ & \dots & ⋮ & \dots & ⋮ \\ s_{N - 1, 0}^{λ_{1}} & \dots & s_{N - 1, N - 1}^{λ_{1}} & \dots & s_{N - 1, 0}^{λ_{!}} & \dots & s_{N - 1, N - 1}^{λ_{1}} \end{matrix}]

For any time delay

τ = x N v + h, 0 \leq h \leq x N - 1, 0 \leq v \leq N - 1

, the shift sequence

R^{τ} (M^{λ_{2}})

can be expressed by the

N \times x N

matrix as follows:

\underset{a N \times N matrixs}{\underset{⏟}{[\begin{matrix} s_{N - v - 1, N - b}^{λ_{2}} & \dots & s_{N - v - 1, N - 1}^{λ_{2}} & s_{N - v - 1, 0}^{λ_{2}} & \dots & s_{N - v - 1, N - b - 1}^{λ_{2}} & \dots & \dots \\ s_{N - v, N - b}^{λ_{2}} & \dots & s_{N - v, N - 1}^{λ_{2}} & s_{N - v, 0}^{λ_{2}} & \dots & s_{N - v, N - b - 1}^{λ_{2}} & \dots & \dots \\ ⋮ & \dots & ⋮ & ⋮ & \dots & ⋮ & \dots & \dots \\ s_{0, N - b}^{λ_{2}} & \dots & s_{0, N - 1}^{λ_{2}} & s_{0, 0}^{λ_{2}} & \dots & s_{0, N - b - 1}^{λ_{2}} & \dots & \dots \\ ⋮ & \dots & ⋮ & ⋮ & \dots & ⋮ & \dots & \dots \\ s_{N - v - 2, N - b}^{λ_{2}} & \dots & s_{N - v - 2, N - 1}^{λ_{2}} & s_{N - v - 2, 0}^{λ_{2}} & \dots & s_{N - v - 2, N - b - 1}^{λ_{2}} & \dots & \dots \end{matrix}}}

\begin{matrix} s_{N - v - 1, N - b}^{λ_{2}} & \dots & s_{N - v - 1, N - 1}^{λ_{2}} & s_{N - v, 0}^{λ_{2}} & \dots & s_{N - v, N - b - 1}^{λ_{2}} & \dots & s_{N - v, N - b}^{λ_{2}} & \dots & s_{N - v, 0}^{λ_{2}} & \dots & s_{N - v, N - b - 1}^{λ_{2}} \\ s_{N - v, N - b}^{λ_{2}} & \dots & s_{N - v, N - 1}^{λ_{2}} & s_{N - v + 1, 0}^{λ_{2}} & \dots & s_{N - v + 1, N - b - 1}^{λ_{2}} & \dots & s_{N - v + 1, N - b}^{λ_{2}} & \dots & s_{N - v + 1, 0}^{λ_{2}} & \dots & s_{N - v + 1, N - b - 1}^{λ_{2}} \\ ⋮ & \dots & ⋮ & ⋮ & \dots & ⋮ & \dots & ⋮ & \dots & ⋮ & \dots & ⋮ \\ s_{0, N - b}^{λ_{2}} & \dots & s_{0, N - 1}^{λ_{2}} & s_{1, 0}^{λ_{2}} & \dots & s_{1, N - b - 1}^{λ_{2}} & \dots & s_{1, N - b}^{λ_{2}} & \dots & s_{1, 0}^{λ_{2}} & \dots & s_{1, N - b - 1}^{λ_{2}} \\ ⋮ & \dots & ⋮ & ⋮ & \dots & ⋮ & \dots & ⋮ & \dots & ⋮ & \dots & ⋮ \\ s_{N - v - 2, N - b}^{λ_{2}} & \dots & s_{N - v - 2, N - 1}^{λ_{2}} & s_{N - v - 1, 0}^{λ_{2}} & \dots & s_{N - v - 1, N - b - 1}^{λ_{2}} & \dots & s_{N - v - 1, N - b}^{λ_{2}} & \dots & s_{N - v - 1, 0}^{λ_{2}} & \dots & s_{N - v - 1, N - b - 1}^{λ_{2}} \end{matrix}]

where

λ_{1} \neq λ_{2} \in [0, d - 1]

b = h \mod N

, and a denotes a total of

⌊\frac{h}{N}⌋

identical matrices.

The rendezvous number of any two sequences

M^{λ_{1}}

and

M^{λ_{2}}

under time-delay

τ

can be defined as follows:

H_{M^{λ_{1}}, M^{λ_{2}}} (τ) = \sum_{β = 0}^{x N - 1} (\sum_{α = 0}^{x N - 1} h (s_{α, β}^{λ_{1}}, s_{α + v, < β + h >_{N}}^{λ_{2}})), τ = x N v + h (0 \leq h \leq x N - 1, 0 \leq v \leq N - 1)

(2)

where

h (x, y) = 1

x = y

, and

h (x, y) = 0

; otherwise,

< x >_{y}

is denoted as the least non-negative residue of x modulo y for two positive integers x and y.

For any given CHS set

M

, for all

τ \in [0, x N - 1]

, the minimum number of rendezvous

H_{m i n} (M)

is defined as follows:

H_{m i n} (M) = \underset{0 \leq τ \leq x N^{2} - 1}{m i n} {H_{M^{λ_{1}}, M^{λ_{2}}} (τ) : M^{λ_{1}}, M^{λ_{2}} \in M, λ_{1} \neq λ_{2}}

(3)

By the construction of

s_{α, β}^{λ}

in Equation (1), for any

β^{*} \in [0, x N - 1]

, point

s_{α, β^{*}}^{λ_{1}}

and point

s_{α + v, < β^{*} + h >_{N}}^{λ_{2}}

for the rendezvous are satisfied:

γ^{λ_{1}} (α + β^{*} + λ_{1}) \equiv γ^{λ_{2}} (α \pm h + β^{*} \pm v + λ_{2}) (\mod N)

(4)

Since

γ^{λ_{1}} \neq γ^{λ_{2}}

, Equation (3) can be simplified by operating in the finite field N:

γ^{λ_{1}} i \equiv γ^{λ_{2}} j (\mod N)

(5)

where

i, j \in [0, N - 1]

Clearly, Equation (5) holds if

i = j = 0

. It indicates

\sum_{α = 0}^{N - 1} h (s_{α, β^{*}}^{λ_{1}}, s_{α + v, < β^{*} + h >_{N}}^{λ_{2}}) \geq 1

By Equations (2) and (3) for any

β^{*} \in [0, x N - 1]

, we have

H_{m i n} (M) \geq 1

(6)

It is shown that there is at least one rendezvous between any two shift sequences.

When N can be decomposed into

N = q_{1} q_{2} . . . q_{n}

, where

q_{1}, q_{2}, . . ., q_{u}, . . ., q_{n}

are all prime factors of N, if

γ^{λ_{1}} - γ^{λ_{2}} = \frac{N}{q_{u}}

holds, we have:

q_{u} (γ^{λ_{1}} - γ^{λ_{2}}) \equiv 0 (\mod q_{1} q_{2} . . . q_{n})

This means that there is another rendezvous point in addition to the

i = j = 0

point. It indicates

\sum_{α = 0}^{x N - 1} h (s_{α, β^{*}}^{λ_{1}}, s_{α + v, < β^{*} + h >_{N}}^{λ_{2}}) \geq 2

By Equations (2) and (3) for any

β^{*} \in [0, x N - 1]

, we also have

H_{m i n} (M) \geq 2

(7)

It is shown that there are at least two rendezvous points in a column. □

Example 1.

x = 2

and

N = 10

Step 1: Choose

γ = 3

the largest multiplicative order

o r d (γ) = 4

Z_{10}^{*}

Step 2: Let

λ = 0

, we can generate an

N \times N

matrix

S^{0}

according to Equation (1).

Step 3: String the matrix

S^{0}

2 times to create the

N \times 2 N

CHS

M^{0}

as follows:

[\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 \\ 2 & 3 & 4 & 5 & 5 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 8 & 1 \\ 3 & 4 & 5 & 6 & 6 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 7 & 2 \\ 4 & 5 & 6 & 7 & 7 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 6 & 3 \\ 5 & 6 & 7 & 8 & 8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 5 & 4 \\ 6 & 7 & 8 & 9 & 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 7 & 8 & 9 & 0 & 0 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 3 & 6 \\ 8 & 9 & 0 & 1 & 1 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 2 & 7 \\ 9 & 0 & 1 & 2 & 2 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{matrix}]

Then we constructed a CHS

M^{1}

with

λ = 1

[\begin{matrix} 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 \\ 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 \\ 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 \\ 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 \\ 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 \\ 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 \\ 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 \\ 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 \\ 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 \\ 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \end{matrix}]

and the CHS

M^{1}

with cyclic shift

τ = 1 (h = 1, v = 0)

[\begin{matrix} 7 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \\ 0 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 \\ 3 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 \\ 6 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 \\ 9 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 \\ 2 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 \\ 5 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 \\ 8 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 \\ 1 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 \\ 4 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 \end{matrix}]

the CHS

M^{1}

with cyclic shift

τ = 2 (h = 2, v = 0)

[\begin{matrix} 4 & 7 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 \\ 7 & 0 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \\ 0 & 3 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 \\ 3 & 6 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 \\ 6 & 9 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 \\ 9 & 2 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 \\ 2 & 5 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 \\ 5 & 8 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 \\ 8 & 1 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 \\ 1 & 4 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 \end{matrix}]

the CHS

M^{1}

with cyclic shift

τ = 8 (h = 8, v = 0)

[\begin{matrix} 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 \\ 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 \\ 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 \\ 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 \\ 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 \\ 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 \\ 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 1 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 \\ 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \\ 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 \\ 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 \end{matrix}]

The elements in red represent the rendezvous points in the CHS

M^{0}

and

M^{1}

Theorem 2.

For any integer

N \geq 3

, the MTTR and MFTTR of the CHS set generated by Construction 1 are

\frac{x N^{2}}{2}

and

\frac{x N^{2}}{2}

, respectively.

Proof.

According to Theorem 1, there are at least two rendezvous in a column if

γ^{λ_{1}} - γ^{λ_{2}} = \frac{N}{q_{u}}

. Thus, we can have the following discussion:

Let k be an integer; k denotes the total number of columns with rendezvous points. h is denoted as the horizontal shift, then we have

k = \{\begin{matrix} x N - h, if h is odd \\ h, if h is even \end{matrix}

Let

r (α, β)

represent the coordinate of the rendezvous point, where

α

corresponds to the row index, and

β

corresponds to the column index. If

r_{1} (α_{1}, β_{1})

and

r_{2} (α_{2}, β_{2})

are two rendezvous points then

M T T R = |α_{2} - (α_{1} - 1)| \times x N - β_{1} - (x N - β_{2})

M F T T R = α_{1} \times β_{1}

(1): If $0 < k \leq \frac{N}{2}$ :
If $k = 1$ , at this time the rendezvous point appears only in the last column ( $h = x N - 1$ ). Consider the worst situation where $r_{1} (α_{1} = \frac{N}{2}, β_{1} = x N)$ , $r_{2} (α_{2} = N, β_{2} = x N)$ ; therefore, MTTR = $|α_{2} - (α_{1} - 1)| \times x N - β_{1} - (x N - β_{2})$ = $(N - \frac{N}{2} + 1) \times x N - x N - (x N - x N)$ = $\frac{x N^{2}}{2}$ , and MFTTR = $α_{1} \times β_{1}$ = $x N \times \frac{N}{2}$ = $\frac{x N^{2}}{2}$ .
(2): If $\frac{N}{2} < k \leq x N - 1$ :
Since each row satisfies at least one rendezvous, the maximum MTTR is generated when only one rendezvous happens between both rows, i.e., $r_{3} (α_{3}, β_{3})$ , $r_{4} (α_{3} + 1, β_{3} - 1)$ . MTTR = $|α_{3} + 1 - (α_{3} - 1)| \times x N - β_{3} - (x N - β_{3} + 1)$ = $x N - 1$ is generated at this time. However, for $r (α = 1, β = x N)$ (the last column of the first row), it appears that MFTTR = $α \times β$ = $1 \times x N$ = $x N$ .

According to the above analysis, we have:

M T T R = \{\begin{matrix} \frac{x N^{2}}{2}, 0 < k \leq \frac{N}{2} \\ x N - 1, \frac{N}{2} < k \leq x N - 1 \end{matrix}

M F T T R = \{\begin{matrix} \frac{x N^{2}}{2}, 0 < k \leq \frac{N}{2} \\ x N, \frac{N}{2} < k \leq x N - 1 \end{matrix}

□

Example 2.

When

N = 10

L = 2 N^{2} = 200

, the MTTR and MFTTR performance of the new construction is shown below:

M T T R = \{\begin{matrix} 100, 0 < k \leq 5 \\ 19, 5 < k \leq 19 \end{matrix}

M F T T R = \{\begin{matrix} 100, 0 < k \leq 5 \\ 20, 5 < k \leq 19 \end{matrix}

Therefore, for

N = 10

, MTTR=100 and MFTTR=100.

Corollary 1.

For the new construction when

N = p

, and p is a prime, MTTR and MFTTR take

x p - 1

and

x p

, respectively, for any integer

p \geq 3

Proof.

In any combination of vertical and horizontal circular shifts, the new construction always has at least one rendezvous in each column between any pair of

p \times x p

CH matrices.

When

N = p

and p is a prime, MTTR =

x p - 1

because each row has

x p

elements, and each column consists of different factors. The worst case of the first rendezvous occurs in the last column of the CH matrix so that MFTTR =

x p

when all licensed channels are available. □

4. Performance Comparison

In this section, we compare the MTTR, the TTR mean and the variance of the new construction with S-ACH [13] and E-AHW [14] under the same channel N. Since the new construction is a flexible parameter, in order to accurately compare the three constructions, Figure 3, Figure 4 and Figure 5 illustrate the constant new construction of length

x = 2

. The performance of full DoR is not considered in S-ACH [13] and E-AHW [14], so we focus on their MTTR performances here. Thus, the new construction has MTTR =

N^{2}

, where N is non-prime, while S-ACH [13] and E-AHW [14] have MTTR of

6 l N^{2} - N + 1

and

3 (l + 1) N p - N + 1

, respectively. Here, l stands for the ID sequence length and p is the smallest prime number greater than N.

Figure 3 compares the new construction with the S-ACH [13] and E-AHW [14] construction for MTTRs with non-prime N. Observe that the MTTR deteriorates with increasing N. This is due to the rise in the licensed channel capacity, which leads to an increase in the distance between channel convergence communications. In the figure, we observe a concentration of convertible channels when the channel capacity increases. This is because, under asynchronous conditions, the ID expansion sequence affects both S-ACH [13] and E-AHW [14] construction, making the distribution between the converging channels uneven. However, the ID sequences do not affect the new construction, resulting in a better MTTR =

N^{2} (x = 2)

performance.

Figure 4 and Figure 5 compare the TTR mean and the variance between the construction with the same parameters as in Figure 3. For each construction, the TTR mean is calculated by averaging all TTRs in all simulation iterations, and the TTR variance is calculated by averaging over all TTRs. It can be seen in Figure 4 and Figure 5 that the mean and variance of the TTR for S-ACH [13] and E-AHW [14] are unstable, which is due to uneven distributions caused by convergent channel aggregation. Additionally, the new construction’s TTR mean value is not the smallest among them. However, a tiny TTR variance demonstrates that the new construction of channel rendezvous is evenly distributed, and the channel rendezvous is not concentrated in a specific time slot, which makes the communication quality more reliable.

5. Conclusions

In this paper, a set of asynchronous channel hopping sequences with new parameters is proposed based on arbitrary licensed channels. It is used to implement a cognitive radio network for asynchronous communication. The novelty of our approach lies in the fact that the new construction uses interleaving techniques to construct a family of channel-hopping sequences with new parameters, allowing it to be applied in different scenarios. Rendezvous is guaranteed to occur between any two sequences, and the rendezvous time is unpredictable and inhomogeneous. The simulated results show that the new construction is more balanced between the MTTR and small TTR mean and variance. In wireless communication, adopting this technology will be helpful in numerous communication scenarios. It helps reduce the channel congestion and interference that may jeopardize the dependability and security of communication. In future work, we will investigate new CHSs to achieve better performances of DoR, MTTR and MFTTR.

Author Contributions

Conceptualization, Y.W. and X.N.; methodology, Y.W.; software, Y.W. and Z.H.; validation, Y.W. and X.N.; writing—original draft preparation, Y.W.; writing—review and editing, Y.W., X.N., C.Q. and B.Z.; supervision, X.N. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the National Science Foundation of China grant number 62171387 and the China Postdoctoral Science Foundation grant number 2019M663475.

Institutional Review Board Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

The author thanks the reviewers for their useful comments.

Conflicts of Interest

The author declares no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

SUs	Secondary users
CHS	Channel-hopping sequence
PU	Primary user
TTR	Time-to-rendezvous
MTTR	Maximum-time-to-rendezvous
MFTTR	Maximum-first-time-to rendezvous
DSC	Disjoint Set Cover
DSCR	Disjoint Set Cover Rendezvous
JS	Jump–stay
S-ACH	Symmetric-asynchronous channel hopping
SQCH	Symmetric-role Quorum-based channel hopping
E-AHW	Enhanced-alternate hop-and-wait
ACHPS	Asynchronous channel-hopping prime sequences
IDEAL-CH	IDEAL channel hopping
CM2P-CH	Control-MTTR-by-2p channel hopping
NPCH	The natural number-based channel hopping sequence set with new parameters

References

Khan, A.A.; Rehmani, M.H.; Rachedi, A. Cognitive-radio-based internet of things: Applications, architectures, spectrum related functionalities, and future research directions. IEEE Wirel. Commun. 2017, 24, 17–25. [Google Scholar] [CrossRef]
Aslam, S.; Ejaz, W.; Ibnkahla, M. Energy and spectral efficient cognitive radio sensor networks for Internet of Things. IEEE Internet Things J. 2018, 5, 3220–3233. [Google Scholar] [CrossRef]
John, P. Cognitive radio: The technologies required. In Cognitive Radio Technology; Elsevier: Amsterdam, The Netherlands, 2006; pp. 119–161. [Google Scholar]
Onthoni, D.D.; Sahoo, P.K.; Atiquzzaman, M. ASAA: Multihop and Multiuser Channel Hopping Protocols for Cognitive-Radio-Enabled Internet of Things. IEEE Internet Things J. 2022, 10, 8305–8318. [Google Scholar] [CrossRef]
Zhao, J.; Zheng, H.; Yang, G.H. Distributed coordination in dynamic spectrum allocation networks. In Proceedings of the First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, DySPAN 2005, Baltimore, MD, USA, 8–11 November 2005; pp. 259–268. [Google Scholar]
Chang, G.Y.; Teng, W.H.; Chen, H.Y.; Sheu, J.P. Novel channel-hopping schemes for cognitive radio networks. IEEE Trans. Mob. Comput. 2012, 13, 407–421. [Google Scholar] [CrossRef]
Kwong, W.C.; Arthur, A.W.; Lo, F.W.; Yang, G.C. A Cognitive-Radio Experimental Testbed for Shift-Invariant, Asynchronous Channel-Hopping Sequences with Modern Software-Defined Radios. In Proceedings of the 2022 IEEE Long Island Systems, Applications and Technology Conference (LISAT), Old Westbury, NY, USA, 6 May 2022; pp. 1–6. [Google Scholar]
Wang, Y.T.; Yang, G.C.; Huang, S.H.; Chang, M.K.; Kwong, W.C. Multi-MTTR asynchronous-asymmetric channel-hopping sequences for scalable cognitive radio networks. IEEE Trans. Cogn. Commun. Netw. 2018, 4, 692–703. [Google Scholar] [CrossRef]
Sheu, J.P.; Su, C.W.; Chang, G.Y. Asynchronous quorum-based blind rendezvous schemes for cognitive radio networks. IEEE Trans. Commun. 2015, 64, 918–930. [Google Scholar] [CrossRef]
Yang, B.; Zheng, M.; Liang, W. A time-efficient rendezvous algorithm with a full rendezvous degree for heterogeneous cognitive radio networks. In Proceedings of the IEEE INFOCOM 2016—The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA, 10–14 April 2016; pp. 1–9. [Google Scholar]
Yang, L.H.; Yang, G.C.; Kwong, W.C. New asynchronous channel-hopping sequences for cognitive-radio wireless networks. IEEE Trans. Cogn. Commun. Netw. 2022, 8, 842–855. [Google Scholar] [CrossRef]
Liu, H.; Lin, Z.; Chu, X.; Leung, Y.W. Jump-stay rendezvous algorithm for cognitive radio networks. IEEE Trans. Parallel Distrib. Syst. 2012, 23, 1867–1881. [Google Scholar] [CrossRef]
Bian, K. Maximizing rendezvous diversity in rendezvous protocols for decentralized cognitive radio networks. IEEE Trans. Mob. Comput. 2012, 12, 1294–1307. [Google Scholar] [CrossRef]
Chuang, I.H.; Wu, H.Y.; Kuo, Y.H. A fast blind rendezvous method by alternate hop-and-wait channel hopping in cognitive radio networks. IEEE Trans. Mob. Comput. 2014, 13, 2171–2184. [Google Scholar] [CrossRef]
Chen, W.C.; Yang, G.C.; Chang, M.K.; Kwong, W.C. Construction and analysis of shift-invariant, asynchronous-symmetric channel-hopping sequences for cognitive radio networks. IEEE Trans. Commun. 2017, 65, 1494–1506. [Google Scholar] [CrossRef]
Chang, C.S.; Sheu, J.P.; Lin, Y.J. On the theoretical gap of channel hopping sequences with maximum rendezvous diversity in the multichannel rendezvous problem. IEEE/ACM Trans. Netw. 2021, 29, 1620–1633. [Google Scholar] [CrossRef]

Figure 1. An illustration of a rendezvous between SUs based on distribution.

Figure 2. Example of SUs asynchronous rendezvous model.

Figure 3. Comparison of the MTTR of related constructions under the same channel N.

Figure 4. Comparison of TTR mean of the correlation construction under the same channel N.

Figure 5. Comparison of TTR variance of the correlation construction under the same channel N.

Table 1. Comparison of Related CHSs.

	Period L	MTTR	MFTTR
JS [12]	$3 N p^{2}$	$4 p$	$3 p$
S-ACH [13]	$6 l N^{2}$	$6 l N^{2} - N + 1$	$6 l N^{2}$
SQCH [9]	$2 N^{3} + N^{2}$	$2 N^{2} + N$	$2 N^{3} + N^{2}$
E-AHW [14]	$3 (l + 1) N p$	$3 (l + 1) N p - N + 1$	$3 (l + 1) N p$
DSCR [10]	$2 p^{2} + p ⌊p / 2⌋$	$2 p^{2} + p ⌊p / 2⌋ - p + 1$	$2 p^{2} + p ⌊p / 2⌋$
ACHPS [15]	$p^{2}$	$p^{2} - p$	$p^{2}$
IDEAL-CH [16]	$2 p^{2}$	$2 p^{2} - p + 1$	$2 p^{2}$
CM2P-CH [11]	$2 p^{2}$	$2 p$	$2 p$
$T h e o r e m 2$	$x N^{2}$ ( $N \neq p$ )	$\frac{x N^{2}}{2}$	$\frac{x N^{2}}{2}$
$C o r o l l a r y 1$	$x p^{2}$ ( $N = p$ )	$x p - 1$	$x p$

N and x denote positive integers, p is a prime, and l represents the length of the ID sequence.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, Y.; Niu, X.; Qi, C.; He, Z.; Zeng, B. New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks. Entropy 2023, 25, 1473. https://doi.org/10.3390/e25101473

AMA Style

Wang Y, Niu X, Qi C, He Z, Zeng B. New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks. Entropy. 2023; 25(10):1473. https://doi.org/10.3390/e25101473

Chicago/Turabian Style

Wang, Yaoxuan, Xianhua Niu, Chao Qi, Zhihang He, and Bosen Zeng. 2023. "New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks" Entropy 25, no. 10: 1473. https://doi.org/10.3390/e25101473

APA Style

Wang, Y., Niu, X., Qi, C., He, Z., & Zeng, B. (2023). New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks. Entropy, 25(10), 1473. https://doi.org/10.3390/e25101473

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

New Construction of Asynchronous Channel Hopping Sequences in Cognitive Radio Networks

Abstract

1. Introduction

2. Related Work and Contribution

3. Construction of Channel Hopping Sequence Sets with New Parameters Based on Natural Numbers

3.1. NPCH Construction

3.2. Constructive Analysis

4. Performance Comparison

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Data Availability Statement

Acknowledgments

Conflicts of Interest

Abbreviations

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI