{'fraction_non_alphanumeric': 0.04444531926619951, 'fraction_numerical': 0.00988111172348634, 'mean_word_length': 3.9278370514064016, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Channel Hopping Sequences for Maximizing Rendezvous Diversity in Cognitive Radio Networks

In cognitive radio networks (CRNs), establishing a communication link between a pair of secondary users (SUs) requires them to rendezvous on a common channel which is not occupied by primary users (PUs). Under time-varying PU traffic, asynchronous sequence-based channel hopping (CH) with the maximal rendezvous diversity is a representative technique to guarantee an upper bounded time-torendezvous (TTR) for delay-sensitive services in CRNs, without requiring global clock synchronization. Maximum TTR (MTTR) and maximum conditional TTR (MCTTR) are two commonly considered metrics for evaluating such CH sequences, and minimizing these two metrics is the primary goal in the sequence design of various paper reported in the literature. In this paper, to investigate the fundamental limits of these two metrics, we first derive lower bounds on the MCTTR and MTTR, and then propose an asymmetric design which has the minimum MCTTR and an improvement on MTTR than other previously known algorithms. Moreover, when the number of licensed channels is odd, our proposed design achieves the minimum MTTR. We also present the TTR performance of the proposed design via simulation.

Cognitive radio, maximum rendezvous diversity, time to rendezvous, asynchronous channel hopping

I. INTRODUCTION
In order to improve the spectrum utilization of cognitive radio networks (CRNs), secondary users (SUs) are allowed to access the spectrum that is not occupied by primary users (PUs). Once a pair of SUs simultaneously visit the same available channel, which is called rendezvous, they can establish a connection via standard communication protocols. As rendezvous has a direct impact on the medium access delay of SUs, the time-to-rendezvous (TTR), which is defined precisely in Section II, is usually used for evaluating the performance of a rendezvous protocol.
However, since the channel availability is time-varying due to the presence of PU signals and it is difficult to maintain global time synchronization among SUs, how to guarantee an upper bounded TTR for delay-sensitive services in CRNs is a challenging problem. Asynchronous sequence-based channel hopping (CH) with the maximal rendezvous diversity, which minimizes the risk of rendezvous failures due to the interference of PU signals, is a representative technique to address this issue [1]- [12]. Here, the rendezvous diversity is defined as the minimum number of distinct channels which a pair of CH sequences could simultaneously visit, and the maximal rendezvous diversity is equal to the total number of licensed channels.
To avoid an unreasonably long TTR due to the PUs blocking, the primary goal in the design of asynchronous CH sequences with the maximal rendezvous diversity is to minimize the following two metrics [1]- [12]: • Maximum TTR (MTTR)-the maximum time for two CH sequences to rendezvous when all licensed channels are available for the two SUs.
• Maximum Conditional TTR (MCTTR)-the maximum time for two CH sequences to rendezvous assuming there is at least one available channel for the two SUs.
This paper continues the work to investigate asynchronous CH sequences with the maximal rendezvous diversity under this objective. The follow-on tasks after initial rendezvous, such as channel contention procedure and data packet transmission, are outside the scope of this paper.
Obviously, MTTR and MCTTR provide upper bounds on the TTR for two extreme channel conditions, and hence have been commonly considered for those applications that have stringent worst-case TTR requirement.
Previously known work on asynchronous CH sequences with the maximal rendezvous diversity in the literature can be classified into two categories: asymmetric and symmetric. Asymmetric approaches require each SU to have a preassigned role as either a sender or a receiver, and allow the sender and the receiver to use different approaches to generate their respective CH sequences, while symmetric approaches do not. As summarized in [9], [12], previously known asymmetric ones such as A-MOCH [4], ACH [5], ARCH [6], D-QCH [10], and WFM [11] all produce smaller MCTTR than previously known symmetric ones, such as CRSEQ [1], JS [2], EJS [3], Sym-ACH [5], DRDS [7], HH [8], T-CH [9] and S-QCH [10]. However, to the authors' best knowledge, the following two fundamental problems have not been settled until now. The answers of them determine whether the performance of the existing CH schemes can be further improved.
(i) What is the minimum MCTTR and MTTR of asynchronous CH sequences with the maximal rendezvous diversity? We note there are some recent papers [4], [11], [13] that made attempts to investigate this issue, but all are under additional constraints of sequence design. Bian et al. in [4] provided a lower bound on MCTTR, however, the proof therein requires the assumption that the sequence period is equal to the MCTTR. Chang et al. in [11] and [13] derived lower bounds on MCTTR and MTTR, respectively, but only considered the CH sequences that simultaneously satisfy the independence assumption (a pair of CH sequences are independent) and the uniform channel loading assumption (an SU hops to a particular channel at a particular interval with an equal probability).
(ii) How to design an algorithm with minimum MCTTR and MTTR? It was claimed in [4]- [6], [10], [11] that A-MOCH, ACH, ARCH, D-QCH and WFM all produced the minimum MCTTR, but the minimum is established based on the lower bounds in [4] and [11].
This paper presents analysis that addresses these issues.  known algorithms do not. Our work can be seen as a generalization of [11] for the asynchronous case which focused on tight lower bounds under some constraints of sequence design.
In addition to the theoretical analysis of the CH schemes, we also perform numerical study in terms of a new metric-MTTR h , to more comprehensively investigate the worst-case TTR performance under a variety of scenarios of opportunistic spectrum access; and perform simulations to evaluate the average TTR in a CRN.
We organize the rest of the paper as follows. We introduce the system model and relevant definitions in Section II. Lower bounds for MCTTR and MTTR are established in Section III.
We state the proposed FARCH algorithm and evaluate its MCTTR and MTTR performance in Section IV. In Section V, we discuss the worst-case rendezvous performance of different approaches under various scenarios of PU traffic, including those considered in MTTR and MCTTR. Simulation results on the TTR performance of the FARCH algorithm are presented in Section VI. Finally, we provide concluding remarks in Section VII.

II. SYSTEM MODEL
In this paper, an asynchronous CH system and relevant definitions are described as below, following the framework in [1]- [9], [11].
We assume that all SUs and PUs under consideration are in the same geographical area, and all SUs share a known channel set of N (N ≥ 2) licensed channels, labeled as 0, 1, . . . , N −1. To model the CH system, we assume all N licensed frequency channels admit the same time-slotted structure with the same time slot duration.
In a sequence-based CH scheme, each SU is assigned a CH sequence, which determines the order of channel-visit. All SUs visit channels by periodically reading CH sequences until a rendezvous occurs. We assume that all CH sequences enjoy a common CH period T .
From practical considerations, it may be desirable to require each SU to perform sensing to remove unavailable channels from consideration in its CH sequences [9], [10]. However, in this paper we do not adopt this approach. Instead, we follow the model in [1]- [6], [11], and assume that the SUs do not determine which channel is available by channel sensing.
Since there is no global clock synchronization, we assume the channel is only slot-synchronous, i.e., SUs know the slot boundaries, but they do not necessarily start their channel hopping sequences at the same global time.
Let Z N denote the set {0, 1, . . . , N − 1}. We represent a CH sequence u of period T as: where u i is an element in Z N for each i, and denotes the channel visited by u at the (i + 1)-th slot of a CH period.
Let τ be a non-negative integer. Given a CH sequence, u, of period T , the cyclic shift by τ slots is defined as where the addition is taken modulo T . In particular, u = u 0 .
Two CH sequences u and v are said to be distinct if neither one is a shifted version of the other, i.e., u τ = v and v τ = u for any non-negative integer τ .
Consider two CH sequences u and v of period T . In this paper, we only assume u and v are slot-synchronous, so they may start at different global time.
for some i and some available channel k. In this case, channel k is called a rendezvous channel and the (i + 1)-th slot of v is called a rendezvous slot. We refer to the smallest slot index of v in which there is a rendezvous, as the TTR between u and v.
Let v n be a subsequence of v, which only consists of the first n (1 ≤ n ≤ T ) entries of v.
Let H u τ ,vn (k) denote the times that u and v simultaneously visit channel k in the first n slots of v, when sequence u's clock is τ slots ahead of sequence v's clock, i.e., Similarly, in the case that sequence v's clock is τ slots ahead of sequence u's clock, let u m be In particular, two CH sequences u and v are said to be a pair of asynchronous CH sequences with the maximal rendezvous diversity [1]- [9] if and only if for any non-negative integers τ, τ ′ , and any k ∈ Z N .
We provide an example of asynchronous CH sequences with the maximal rendezvous diversity in Fig. 1. Due to the time-varying channel availability and random relative shift among SUs, it is difficult to directly formulate TTR, as seen in Fig. 1. Instead, we make the following formal definitions of MTTR and MCTTR, in order to study the TTR performance under two extreme scenarios as in [1]- [9], [11], [12].
For a pair of asynchronous CH sequences with the maximal rendezvous diversity, u and v, max{m, n} such that for any non-negative integers τ, τ ′ ; (ii) and define MCTTR to be the maximum time for u and v to rendezvous under all possible clock differences when at least one licensed channel is available, that is, the smallest value of max{m, n} such that for any non-negative integers τ, τ ′ and any k ∈ Z N .
Asynchronous CH sequences with the maximal rendezvous diversity can ensure that both MTTR and MCTTR are upper-bounded by the sequence period T . Moreover, in our considered CH system, MCTTR exists only when the rendezvous diversity is maximal.

III. LOWER BOUNDS ON MCTTR AND MTTR
Before deriving lower bounds on MCTTR and MTTR of asynchronous CH sequences with the maximal rendezvous diversity, we need the following useful proposition, which is a generalization of elementary cross-correlation properties of binary sequences [14].

Proposition 1. Given two CH sequences u, v of period T in a CRN with N licensed channels.
For respectively. We have Proof: Recall the definition of Kronecker's delta: Then, H v τ ,um (k) can be written as By summing H v τ ,um (k) over all τ and exchanging the order of summation, we have Proof: Consider a pair of asynchronous CH sequences, u and v, of period T with the maximal rendezvous diversity. Let l be the MCTTR between u and v.

A. A Lower Bound on MCTTR
Let us consider the case that v's clock is τ slots ahead of sequence u's clock. It is obvious that 1 ≤ l ≤ T . By the definition of MCTTR, it is required that for any non-negative integer τ and any k ∈ Z N . Let x k and y k denote the number of k's in u l and v, respectively. By Proposition 1, it follows that Combining (2) and (3) yields: for any k ∈ Z N . Then, after the summation on (4) from k = 0 up to N − 1, we have where ( * * ) is due to the Cauchy-Schwarz inequality. This completes the proof of (i).
From ( * * ), we know that l = N 2 only if y 1 = y 2 = · · · = y N , i.e., v visits all channels with uniform frequency. Consider that u's clock is τ slots ahead of sequence v's clock. By reversing the role of u, v in the above proof, we also obtain that l = N 2 only if u visits all channels with uniform frequency. Therefore, both sequences possess the property that all channels are visited with uniform frequency.
On the other hand, from ( * ), we know l = N 2 only if H v τ ,u l (k) = 1 for any τ ∈ Z T and any Similarly, by assuming that u's clock is τ slots ahead of sequence v's clock, we can obtain v = u τ for any τ ∈ Z T . Therefore, u and v must be distinct if l = N 2 .

Remark 2:
Since MCTTR of asynchronous CH sequences with the maximal rendezvous diversity is always less than or equal to the sequence period, Theorem 2 provides an alternative proof to the result in [5] stating that the minimum period of such CH sequences is at least N 2 .

B. A Lower Bound on MTTR
We are also interested in the minimum MTTR one can achieve. We note that Chang et al. Proof: Let u and v be a pair of asynchronous CH sequences of period T with the maximal rendezvous diversity. Let l be the MTTR between u and v. Obviously, 1 ≤ l ≤ T . By the definition of MTTR, it is required that for any non-negative integer τ , In addition, by Proposition 1, we have where x k and y k denote the number of k's in u l and v, respectively. Combining (5) and (6) yields As shown in the proof of Theorem 2, we know y 1 = y 2 = · · · = y N when MCT T R = N 2 .
Then, the inequality (7) can be simplified as Hence the result follows due to l = N −1 k=0 x k . As shown in Table I, A-MOCH [4] and ACH [5] both have MT T R = N 2 −N + 1, ARCH [6] (only for even N cases) and D-QCH [10] both have MT T R = 2N − 1, and WFM [11] has MT T R = N + 1. It should be noted that Sheu et al. in [10] claimed the D-QCH algorithm can achieve MT T R = N, and Chang et al. in [11] claimed the WFM algorithm can achieve MT T R = N, too. However, we find that the D-QCH and WFM have MT T R = 2N − 1 and MT T R = N + 1, respectively, in some cases for each N, as shown in Fig. 2. To the authors' best knowledge, there are no previously known CH sequences in the literature with MT T R = N and MCT T R = N 2 for an asynchronous CH system. In the next section, we will show that such CH sequences exist by providing concrete construction.

IV. THE PROPOSED ALGORITHM: FARCH
In this section, we design a fast rendezvous channel-hopping algorithm, called FARCH, for asynchronous CH systems. FARCH is an asymmetric design, and hence needs to assign the sender and receiver different approaches to generate their respective CH sequences.
In what follows, s and r are used to denote the sender sequence and receiver sequence, respectively.

A. Algorithm Description
Here is the description of the FARCH algorithm, which produces a pair of s, r with a common period N 2 .
(i) The Sender Sequence Construction.
(ii) The Receiver Sequence Construction.
r is constructed based on the selected permutation w in the construction of s. Note that, from the FARCH construction, it is easy to see that there are N! distinct pairs of CH sequences for each N.
Unlike the approaches taken for A-MOCH [4], ACH [5], ARCH [6] (only for even N cases), D-QCH [10] and WFM [11], our FARCH algorithm requires a one-to-one correspondence between sender sequence and receiver sequence. This property is acceptable in some scenarios, such as half-duplex communication systems or Bluetooth pairing. To make each pair of SUs spread out the rendezvous in time and channels more evenly, we can further allow sender to change its CH sequence in accordance with receiver after each rendezvous.

B. Metrics Evaluation
Now we evaluate the MCTTR and MTTR property of FARCH. First assume that sequence s's clock is τ slots ahead of sequence r's clock. Note that for any τ , the first N entries of r are all equal to a unique value, while for those N entries, s τ runs over all the N values. This implies that there must be a rendezvous between s τ and r within N slots for any τ .
Second, consider the case that sequence r's clock is τ slots ahead of sequence s's clock. The If 0 ≤ i ≤ m − 1, there is a rendezvous at channel w i at the (i + 1)-th entry; otherwise, if m ≤ i ≤ N − 1, there is a rendenzvous at channel w i+1 at the (i + 1)-th entry. Therefore, we have MT T R = N + 1.
It should be pointed out that although the WFM [11] also produces N + 1, it only has N 2 distinct pairs of CH sequences for each N.  for some i ∈ Z N . Since N is odd, such an i exists for any choice of τ . More precisely, Therefore, we conclude that (8) holds for any τ , i.e., there is a rendezvous between s τ and r within N slots for any τ .
Second, consider that sequence r's clock is τ slots ahead of sequence s's clock. Construct a sequence g 1 by repeating [w 0 , w N −1 ] N times and concatenating them into a single sequence.
Construct a sequence g 2 by repeating [w N −2 , w N −3 , . . . , w 1 ] N times and concatenating them into a single sequence. For any τ , the first N entries of r τ have the following four possible forms: (i) any consecutive N entries in g 1 ; (ii) any consecutive N entries in g 2 ; (iii) the last m entries of g 1 followed by the first N − m entries of g 2 ; (iv) the last n entries of g 2 followed by the first N − n entries of g 1 .
We continue to examine the MTTR of the above four cases. An illustration of these four cases is presented in Fig. 3.
(i) By the form of g 1 , it is easy to see that either the first entry of r τ is w 0 or the N-th entry of r τ is w N −1 . This implies that s and r τ always have a rendezvous at channel w 0 or w N −1 within the first N slots.
(ii) By the form of g 2 , if the first entry of r τ is N − 2 − δ for some 0 ≤ δ ≤ N − 2, then the N − 2 entries of r τ followed by the first one will be given by the following: These indices can be viewed as to the residue of a in Z b . Therefore, there exists a rendezvous between s and r τ within the first N − 1 slots if and only if for some i ∈ {1, 2, . . . , N − 2}. It is easy to see that is a solution to (9), which completes this case.
(iii) In the case that m is even, the first entry of r τ is w 0 , as the same as in s. As for the case that m is odd, the first N entries of r τ are Then, the (m + i)-th entry of r τ is w N −1−i for 1 ≤ i ≤ N − m. Since the (m + i)-th entry of s is w m+i−1 for 1 ≤ i ≤ N − m, they have a rendezvous at the (m + i)-th entry (i.e., channel w m+i−1 ) when i = N −m 2 . (iv) If n is odd, the N-th entry of r τ is N − 1, as the same as in s. As for the even case, the first n entries of r τ are w n , w n−1 , . . . , w 1 .
Then, the i-th entry of r τ is w n+1−i , while the i-th entry of s is w i−1 , for 1 ≤ i ≤ n. So they have a rendezvous at the i-th entry (i.e., channel w i−1 ) when i = n 2 + 1. We complete the proof of MT T R = N when sequence r's clock is τ slots ahead of sequence s's clock.

V. FURTHER DISCUSSION ON THE WORST-CASE TTR
As defined in Section II, MTTR and MCTTR only consider two extreme scenarios of opportunistic spectrum accessing. To evaluate the worst-case TTR performance of asynchronous CH sequences with the maximal rendezvous diversity more comprehensively, we introduce one new metric-MTTR h , that is used to denote the worst-case TTR for different channel availabilities.
This more general metric can help us better investigate how even the rendezvouses are distributed in regard to time and channels, in addition to MTTR and MCTTR.
For h = 0, 1, . . . , N − 1, MTTR h is defined as the maximum time for two CH sequences, u and v, to rendezvous under all possible clock differences when there are at most h unavailable channels for the two SUs, that is, the smallest value of max{m, n} such that for any non-negative integers τ, τ ′ and any A h ∈ Z N with cardinality N − h. Obviously, we The following theorem provides a lower bound on MTTR h of a minimum MCTTR system, which can help evaluate the FARCH algorithm in terms of MTTR h . Proof: Let u and v be a pair of asynchronous CH sequences of period T with the maximal rendezvous diversity. Let l be the MTTR h between u and v. Obviously, 1 ≤ l ≤ T .
Suppose there exists a non-negative integer τ * such that which contradicts the defining property of MTTR h .

Hence, we have
for any non-negative integer τ . Let x k and y k denote the number of k's in u l and v, respectively. By using the proof of Theorem 3, we further have Therefore, we obtain MT T R h ≥ (h + 1)N. N), D-QCH and WFM. We also note that the superiority of MTTR h in the FARCH becomes weaker when h increases. This observation implies that FARCH, ARCH, D-QCH and WFM algorithms all spread out the rendezvous in time and channels almost evenly, which will be useful to explain the simulation results presented in Section VI.

VI. SIMULATIONS
In this section, we compare the proposed FARCH scheme against five existing asynchronous CH schemes with the maximal rendezvous diversity and optimal MCTTR, A-MOCH, ACH, ARCH, D-QCH and WFM, via simulation. We aim to show that under a variety of scenarios, FARCH not only can achieve rendezvous quickly in the worst-case, but also can achieve rendezvous quickly on the average.
In the simulation, we consider 10 pairs of SUs and X PUs sharing N channels. We assume X < N, so that there is always at least one available channel, in which no PU signals are present.
The X PUs are operating on the X channels, respectively, and each channel is randomly chosen in each simulation run. It is assumed that each PU has an independent probability p to be transmitting. All of the SUs are within the transmission range of any one of the PUs. Each pair of SUs in each simulation run independently generate their CH sequences, and perform CH in We carry out simulations to attain the average TTR in the presence of PU signals averaged over all possible relative shift positions, which are generated with uniform probability. Note that the MTTR and MCTTR are the theoretical worst-case TTRs in the two extreme PU traffic scenarios, while the average TTR is obtained empirically. Each simulation point represents the average value of 10000 independent simulation runs.

A. Impact of the PU traffic
As FARCH uses different algorithms to construct the receiver sequence for even N and odd N, and ARCH [6] is only defined for even N, in the simulation we consider N = 11, 12, respectively. To model different PU traffic, we consider X = 5, 10 with 0 ≤ p ≤ 1 for each N.
In Fig. 6, we compare the proposed FARCH scheme with A-MOCH, ACH, D-QCH and WFM in terms of average TTR, when N = 11. It is shown that FARCH, D-QCH and WFM achieve a smaller average TTR in all cases. This is because that FARCH, D-QCH and WFM have smaller MTTR h than others for all 0 ≤ h ≤ N − 2, as shown in Fig. 4, and all schemes have the MTTR is obviously not a dominant factor in determining average TTR in the presence of PU signals. In the case of X = 10 with large p, we also observe that FARCH, D-QCH and WFM only have a slightly lower average TTR than the other schemes. The reason is that the MTTR h with small h is not much useful in reducing average TTR when the SUs frequently encounter PU-occupied channels, and instead, the MCTTR plays a more important role in determining average TTR for these cases.

B. Impact of the Number of Licensed Channels
We are also interested in the average TTR performance of our proposed FARCH algorithm under different number of licensed channels. Fig. 8 shows the average TTR comparison among the six schemes with respect to various N. We consider N = 10, 15, . . . , 50 with X = 0.8N and p = 0.4, 0.8. When p = 0.4, we notice that the average TTR of FARCH, WFM, D-QCH and ARCH (only defined for even N) is nearly the same, around 70% of that of A-MOCH or ACH for all N. When p = 0.8, the higher PU traffic increases this ratio to approximately 85% for all N. This observation confirms again that FARCH, WFM, D-QCH and ARCH spread out the rendezvous in time and channels more evenly, and MTTR h with large h contributes more to average TTR when PU traffic becomes higher.
Based on the above simulation results, we conclude that FARCH, ARCH, D-QCH and WFM have similar average TTR performance under a variety of channel conditions. Nevertheless, it should be noted that the FARCH can produce more distinct pairs of CH sequences than ARCH and WFM; and moreover, to the authors' best knowledge, FARCH is the only known algorithm that can achieve MT T R = N for odd N.

VII. CONCLUSIONS
In this paper, we focus on the design of sequence-based CH schemes that ensure maximal rendezvous diversity without time synchronization. After deriving lower bounds on minimum MCTTR, MTTR of such CH sequences, we propose a new rendezvous algorithm: FARCH, with optimal MCTTR for any N and the optimal MTTR when N is odd. However, there are still some possible extensions of our works that require further study.
(i) We conjecture that there does not exist asynchronous CH sequences with MCT T R = N 2 and MT T R = N for even N. It would be of interest to improve the current lower bound MT T R ≥ N to the best known achievable result N + 1 in FARCH and WFM for even N.
(ii) We have introduced a new metric-MTTR h , for a more comprehensive study on the worstcase TTR performance. Another direction of our future work is to design an asynchronous CH algorithm with MTTR h as small as possible, with a reference to lower bounds derived in Theorem 7.