# Combined Sector and Channel Hopping Schemes for Efficient Rendezvous in Directional Antenna Cognitive Radio Networks

Authors: AbdulMajid M. Al-Mqdashi; A. Sali; Nor K. Noordin; Shaiful J. Hashim; Rosdiadee Nordin
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Rendezvous is a prerequisite and important process for secondary users (SUs) to establish data communications in cognitive radio networks (CRNs). Recently, there has been a proliferation of different channel hopping- (CH-) based schemes that can provide rendezvous without relying on any predetermined common control channel. However, the existing CH schemes were designed with omnidirectional antennas which can degrade their rendezvous performance when applied in CRNs that are highly crowded with primary users (PUs). In such networks, the large number of PUs may lead to the inexistence of any common available channel between neighboring SUs which result in a failure of their rendezvous process. In this paper, we consider the utilization of directional antennas in CRNs for tackling the issue. Firstly, we propose two coprimality-based sector hopping (SH) schemes that can provide efficient pairwise sector rendezvous in directional antenna CRNs (DIR-CRNs). Then, we propose an efficient CH scheme that can be combined within the SH schemes for providing a simultaneous sector and channel rendezvous. The guaranteed rendezvous of our schemes are proven by deriving the theoretical upper bounds of their rendezvous delay metrics. Furthermore, extensive simulation comparisons with other related rendezvous schemes are conducted to illustrate the significant outperformance of our schemes.


---

## Body

## 1. Introduction

The inefficiency of radio spectrum utilization due to the fixed assignment of spectrum bands, coupled with the huge increase in the number of wireless devices recently, leads to the emerging of cognitive radios (CRs). CRs have been introduced as an efficient solution for the spectrum scarcity issue. They allow unlicensed users, also known as secondary users (SUs), to opportunistically use licensed bands as long as this use does not create any interference to the bands licensed users, that is, primary users (PUs). In distributed CRNs, SUs need to meet each other on a common channel and exchange control messages in order to set up their data transmissions [1]. This operation is calledrendezvous, which is a fundamental and a vital process for initiating the connection of the SUs data communications.The use of a dedicated common control channel (CCC) is one widely adopted rendezvous approach in the literature [2–6]. Although this approach can simplify the rendezvous process, it has many drawbacks such as the CCC susceptibility to long-time blocking by PUs, early saturation by SUs, or jamming by attackers [7, 8]. Moreover, the spectrum heterogeneity among SUs, caused by the spatial and temporal variations of the spectrum opportunities (influenced by neighboring PU activities), makes this approach not practical. Therefore, channel hopping (CH) has been proposed as an alternative approach for rendezvous without the need for any predefined CCC. The existing CH-based rendezvous schemes were designed with omnidirectional antenna according to different mathematical structures (e.g., [9–18]) in order to provide a successful channel rendezvous between a pair of single-hop SUs. In the CH approach, each SU generates its CH sequence based on the available channels that are sensed to be idle from any PU activities within its omnidirectional range. Then, the SU keeps hopping over the channels according to the generated CH sequence for achieving channel rendezvous. The rendezvous occurs between a pair of communicating SUs when they hop during the same time slot over a channel that is commonly available for both of them. The existence of common available channels (at least one) between the pair of communicating SUs is a common and essential assumption made by all the existing CH schemes. Their designs rely mainly on this assumption to take place for ensuring the success of the rendezvous operation. However, none of the existing CH rendezvous designs were tailored for high-density PU networks, where the number of active PUs in the network is larger than the number of the channels. In such networks, the channel availabilities may vary dramatically among the SUs within the single-hop rendezvous region itself. This can lead to the inexistence of any common available channel between a pair of SUs and hence the failure of the rendezvous process.One approach to overcome this serious rendezvous problem is using directional antennas instead of the conventionally used omnidirectional ones [19]. Directional antennas have been utilized in emerging wireless networks such as the millimeter-wave (MMW) networks for providing highly reliable transmission and multi-Gigabit data rates. This is mainly due to their capabilities in enlarging the transmission range and limiting the interference [20, 21]. However, In CRNs, equipping SUs with directional antennas for channel rendezvous can bring about many advantages. First of all, it allows SUs to transmit their rendezvous messages towards specific directions which can reduce the amount of interference to the PUs in the network as compared with the omnidirectional antennas. This is because the transmission of the SU that is equipped with directional antenna is directed to a particular region which can only cause interference to those PUs that are within this region. On the contrary, when using the omnidirectional antennas, the transmission of the SU is scattered towards all the directions. Thus, it can cause interference to all the surrounding PUs within the SU transmission range. Second, as related to the interference restriction imposed by the CR concept, SUs can use only the channels that are idle from any PU activities within their transmission range. According to that and due to its directed transmission range, using directional antenna will increase the number of available channels that can be utilized by the SU in each of its transmission sectors. As a consequence, the probability for any pair of neighbouring SUs to have at least a common available channel within their crossed sectors is high regardless of the number of PUs in the CRN. Note that, in omnidirectional antennas, this probability could be less than 0.1 for some scenarios when the number of PUs is larger than the network channels [19]. Increasing the probability of existing common available channel between the SUs will significantly enhance the probability of successful channel rendezvous. Therefore, in this paper, we study the rendezvous problem in directional antenna CRNs where SUs are equipped with directional antennas.While the use of directional antennas for channel rendezvous in CRNs can bring about the above-mentioned advantages, it also imposes some unique challenges. Among these challenges is the sector rendezvous which must be achieved in advance between the pair of communicating SUs before they can achieve channel rendezvous. Specifically, the SUs need to steer their antennas towards each other in order to communicate over their commonly available channels. This necessitates the design of a deterministic sector hopping (SH) scheme that can guarantee that any pair of neighbouring SUs will steer their antennas to the proper directions (i.e., towards each other) at a certain time instance. So, when the SH scheme is combined with a suitable and deterministic CH scheme, SUs can achieve successful sector and channel rendezvous simultaneously within a bounded time. However, since the SUs do not know the relative locations of each other as well as the available channels before they rendezvous, the combined sector and channel hopping (SCH) scheme should be designed in fully distributed manner without any prior information or synchronization. Designing such combined SCH schemes for achieving rendezvous in DIR-CRNs is intuitively more challenging as compared with the traditional omnidirectional antenna paradigm.In spite of the existing research in the literature, there have been some papers that addressed the utilization of directional antennas in CRNs. However, most of the proposed works investigated issues other than the rendezvous issue such as sensing [22, 23], routing [24, 25], and connectivity [26, 27]. To the best of our knowledge, the works in [19, 28] are the only proposals that tackle the sector and channel rendezvous issue in DIR-CRNS. In [19], an efficient framework for beamforming was proposed to provide a pairwise sector and channel rendezvous in DIR-CRNs. However, the SH scheme in [19] is not a blind design, where it assumes that the receiver must have prior knowledge of the sender number of sectors in order to achieve a successful sector rendezvous. This is not practical, since SUs do not know any information about each other before they rendezvous. On the other hand, Li and Xie in [28] proposed a blind prime-based SH scheme, where the number of sectors is adjusted to primes for achieving a guaranteed sector rendezvous. However, since the scheme relies on the coprimality between prime numbers only, the authors added an initiating rotated SH sequence on the sender side. This is in order to ensure a successful rendezvous with the receiver when the sender and the receiver construct their sequences with the same prime. Accordingly, the extra sequence overhead incurs extensively long sector rendezvous latency and hence a long time-to-rendezvous (TTR) will result when the SH is combined with a CH sequence. Furthermore, the SH schemes in [19, 28] are designed only for asymmetric-role environment, where SUs have preassigned role (i.e., SU is either a sender or receiver). However, this design limits the applications of the schemes; for example, SUs cannot work as a forwarder (i.e., receive packets from one SU and then forward them to another SU) due to the permanent role assignment [29]. Another drawback of these works is their limitations to provide a complete solution for combining the SH scheme with a suitable and efficient CH scheme which consider the unique traits of DIR-CRNs. They claimed that their SH schemes can work on top of any existing deterministic CH schemes which were designed for the omnidirectional antennas paradigm. However, the combined CH scheme must be designed appropriately by taking into account the unique traits of DIR-CRNs such as the channels’ qualities in the different sectors.In this paper, we propose efficient schemes for achieving rendezvous in DIR-CRNs. The main contributions of this paper are summarized as follows:(i)
We propose two asymmetric- and symmetric-role coprimality-based SH schemes, called PES-SH and IPES-SH, for pairwise sector rendezvous in DIR-CRNs.(ii)
We combined our SH schemes with an efficient grid-quorum-based CH scheme, where the CH sequences are generated based on the best-quality channels in the sectors. The combined SCH schemes will provide guaranteed sector and channel rendezvous between the pair of SUs.(iii)
We derive the upper bound of the rendezvous delay metrics for all of our schemes. Also, we conduct extensive simulations to study their performance under various network settings and compare them with the related existing works in [19, 28, 30].The rest of this paper is organized as follows. The system model and problem formulation are presented in Section2. The design and theoretical analysis of the proposed SH schemes are presented in Sections 3 and 4. In Section 5, we present the combined sector and channel hopping schemes. Using simulations, in Section 6, we evaluate the performance of our proposed schemes and compare their performance with other comparable schemes. Finally, we conclude the paper in Section 7.


## 2. Models and Problem Definition

In this section, we present the system model and rendezvous problem definition in DIR-CRNs.


### 2.1. System Model

We consider a CRN consisting ofK SUs that coexist with several PUs in an w×w area. There are totally L primary channels which can be accessed opportunistically by the SUs in order to communicate with each other. Each SU i∈K is equipped with a directional antenna with beamwidth θi(0<θi<2π). Accordingly, the 2π communication range of the SU i is divided into Ni=2π/θi nonoverlapping sectors that are indexed from 1 to Ni. However, the number of sectors and the orientation of the sector indexing (i.e., either clockwise or anticlockwise) by each SU may be different from the others (see Figure 1). This is a very practical issue because each SU will configure its sectors based only on its own view to the surrounding environment. Each SU can transmit over any of its transmission sectors as long as it does not make any interference to any active PU transmission. Accordingly, we assume that the transmission sectors are also used as sensing sectors by which every SU can sense the appearance of the active PUs within them. Thus, the SU can obtain the channel availability information per each sector. We consider a time-slotted communication, where time is divided into discrete slots that have fixed and equal durations. During each time slot, we assume that a SU can only transmit in one sector over a single channel.Figure 1
Examples of directional antenna configurations in two pairs of communicating SUs: (a)SUX and SUY divide their transmission range into NX=5 and NY=4 sectors; the rendezvous sector pair is (2,3). (b) SUV and SUZ divide range into Nv=4 and Nz=3 sectors; the rendezvous sector pair is (4,1).
(a)
Pair ofX and Y SUs
(b)
Pair ofV and Z SUs


### 2.2. Definitions of Sector and Channel Rendezvous

In this paper, we mainly focus on the pairwise sector and channel rendezvous between any pair of SUs in a DIR-CRN. Firstly, we define the sector rendezvous problem as follows.


#### 2.2.1. The Sector Rendezvous Problem

For any two neighbour SUs (saySUi and SUj) that are equipped with directional antennas and want to communicate with each other, assume that SUi is located in the sector hj∈[1,Nj] of SUj and SUj is situated in the sector hi∈[1,Ni] of SUi. The pair of the sectors (hi,hj) is called the sector rendezvous pair. SUs are said to achieve a successful sector rendezvous if and only if they steer their antennas towards each other, where their transmission sectors can cover each other. Formally, let Si={Si0,Si1,…,SiTi} and Sj={Sj0,Sj1,…,SjTj} denote the sector hopping sequences for SUi and SUj, with periods Ti and Tj, respectively. Also let δ denote the clock drift between SUi and SUj in the asynchronous scenario. The sector rendezvous problem can be formulated as follows:If∀δ,∀Ni,Nj,∃t∈[0,TiTj-1],s.t,(Sit=hi and Sjt+δ=hj), then the sector rendezvous is achieved over the sector rendezvous pair (hi,hj).


#### 2.2.2. The Sector and Channel Rendezvous Problem

When a SU steers its directional antenna to each sector of its transmission sectors, it performs CH over the available channels within the sector according to a CH sequence. This is in order to attempt channel rendezvous with another SU over a commonly available channel between them. The combined CH scheme should be designed in such a way that guarantees a successful channel rendezvous within bounded time whenever the communicating SUs already achieved a successful sector rendezvous. During the current sector, if the SU does not achieve channel rendezvous with its intended communicating SU within the bounded time slots, it then steers its antenna to the next sector of its SH sequence and executes the CH scheme based on the available channels within this sector.One approach to view the problem is to look at it in a hierarchical way, in which time is divided into frames, where the SU tunes its antenna to one sector during each frame. In other words, the SH is implemented on the frame scale. Then, each frame is divided into number of time slots, where the combined CH sequence is executed (i.e., the CH is implemented on the time slot scale). The main goal of this paper is to design deterministic combined SCH scheme so as to tackle the sector and channel rendezvous problem.


#### 2.2.3. Metrics

The proposed SH schemes as well as the combined SCH schemes will be evaluated according to the following metrics:(i)
Sector rendezvous latency (SRL): it is defined as the required latency (in number of sector frames) for a pair of SUs to achieve sector rendezvous. We consider the maximum and average latency (MSRL/ASRL). MSRL is defined as the upper bound of the SRL between the SUs for all the possible clock drifts between them(ii)
Time-to-rendezvous (TTR): it is defined as the required time (in number of time slots) for a pair of SUs to achieve sector and channel rendezvous simultaneously. Maximum and average time-to-rendezvous (MTTR/ATTR) are considered. MTTR means the required time for a guaranteed rendezvous even in the worst case.


## 2.1. System Model

We consider a CRN consisting ofK SUs that coexist with several PUs in an w×w area. There are totally L primary channels which can be accessed opportunistically by the SUs in order to communicate with each other. Each SU i∈K is equipped with a directional antenna with beamwidth θi(0<θi<2π). Accordingly, the 2π communication range of the SU i is divided into Ni=2π/θi nonoverlapping sectors that are indexed from 1 to Ni. However, the number of sectors and the orientation of the sector indexing (i.e., either clockwise or anticlockwise) by each SU may be different from the others (see Figure 1). This is a very practical issue because each SU will configure its sectors based only on its own view to the surrounding environment. Each SU can transmit over any of its transmission sectors as long as it does not make any interference to any active PU transmission. Accordingly, we assume that the transmission sectors are also used as sensing sectors by which every SU can sense the appearance of the active PUs within them. Thus, the SU can obtain the channel availability information per each sector. We consider a time-slotted communication, where time is divided into discrete slots that have fixed and equal durations. During each time slot, we assume that a SU can only transmit in one sector over a single channel.Figure 1
Examples of directional antenna configurations in two pairs of communicating SUs: (a)SUX and SUY divide their transmission range into NX=5 and NY=4 sectors; the rendezvous sector pair is (2,3). (b) SUV and SUZ divide range into Nv=4 and Nz=3 sectors; the rendezvous sector pair is (4,1).
(a)
Pair ofX and Y SUs
(b)
Pair ofV and Z SUs


## 2.2. Definitions of Sector and Channel Rendezvous

In this paper, we mainly focus on the pairwise sector and channel rendezvous between any pair of SUs in a DIR-CRN. Firstly, we define the sector rendezvous problem as follows.


### 2.2.1. The Sector Rendezvous Problem

For any two neighbour SUs (saySUi and SUj) that are equipped with directional antennas and want to communicate with each other, assume that SUi is located in the sector hj∈[1,Nj] of SUj and SUj is situated in the sector hi∈[1,Ni] of SUi. The pair of the sectors (hi,hj) is called the sector rendezvous pair. SUs are said to achieve a successful sector rendezvous if and only if they steer their antennas towards each other, where their transmission sectors can cover each other. Formally, let Si={Si0,Si1,…,SiTi} and Sj={Sj0,Sj1,…,SjTj} denote the sector hopping sequences for SUi and SUj, with periods Ti and Tj, respectively. Also let δ denote the clock drift between SUi and SUj in the asynchronous scenario. The sector rendezvous problem can be formulated as follows:If∀δ,∀Ni,Nj,∃t∈[0,TiTj-1],s.t,(Sit=hi and Sjt+δ=hj), then the sector rendezvous is achieved over the sector rendezvous pair (hi,hj).


### 2.2.2. The Sector and Channel Rendezvous Problem

When a SU steers its directional antenna to each sector of its transmission sectors, it performs CH over the available channels within the sector according to a CH sequence. This is in order to attempt channel rendezvous with another SU over a commonly available channel between them. The combined CH scheme should be designed in such a way that guarantees a successful channel rendezvous within bounded time whenever the communicating SUs already achieved a successful sector rendezvous. During the current sector, if the SU does not achieve channel rendezvous with its intended communicating SU within the bounded time slots, it then steers its antenna to the next sector of its SH sequence and executes the CH scheme based on the available channels within this sector.One approach to view the problem is to look at it in a hierarchical way, in which time is divided into frames, where the SU tunes its antenna to one sector during each frame. In other words, the SH is implemented on the frame scale. Then, each frame is divided into number of time slots, where the combined CH sequence is executed (i.e., the CH is implemented on the time slot scale). The main goal of this paper is to design deterministic combined SCH scheme so as to tackle the sector and channel rendezvous problem.


### 2.2.3. Metrics

The proposed SH schemes as well as the combined SCH schemes will be evaluated according to the following metrics:(i)
Sector rendezvous latency (SRL): it is defined as the required latency (in number of sector frames) for a pair of SUs to achieve sector rendezvous. We consider the maximum and average latency (MSRL/ASRL). MSRL is defined as the upper bound of the SRL between the SUs for all the possible clock drifts between them(ii)
Time-to-rendezvous (TTR): it is defined as the required time (in number of time slots) for a pair of SUs to achieve sector and channel rendezvous simultaneously. Maximum and average time-to-rendezvous (MTTR/ATTR) are considered. MTTR means the required time for a guaranteed rendezvous even in the worst case.


## 2.2.1. The Sector Rendezvous Problem

For any two neighbour SUs (saySUi and SUj) that are equipped with directional antennas and want to communicate with each other, assume that SUi is located in the sector hj∈[1,Nj] of SUj and SUj is situated in the sector hi∈[1,Ni] of SUi. The pair of the sectors (hi,hj) is called the sector rendezvous pair. SUs are said to achieve a successful sector rendezvous if and only if they steer their antennas towards each other, where their transmission sectors can cover each other. Formally, let Si={Si0,Si1,…,SiTi} and Sj={Sj0,Sj1,…,SjTj} denote the sector hopping sequences for SUi and SUj, with periods Ti and Tj, respectively. Also let δ denote the clock drift between SUi and SUj in the asynchronous scenario. The sector rendezvous problem can be formulated as follows:If∀δ,∀Ni,Nj,∃t∈[0,TiTj-1],s.t,(Sit=hi and Sjt+δ=hj), then the sector rendezvous is achieved over the sector rendezvous pair (hi,hj).


## 2.2.2. The Sector and Channel Rendezvous Problem

When a SU steers its directional antenna to each sector of its transmission sectors, it performs CH over the available channels within the sector according to a CH sequence. This is in order to attempt channel rendezvous with another SU over a commonly available channel between them. The combined CH scheme should be designed in such a way that guarantees a successful channel rendezvous within bounded time whenever the communicating SUs already achieved a successful sector rendezvous. During the current sector, if the SU does not achieve channel rendezvous with its intended communicating SU within the bounded time slots, it then steers its antenna to the next sector of its SH sequence and executes the CH scheme based on the available channels within this sector.One approach to view the problem is to look at it in a hierarchical way, in which time is divided into frames, where the SU tunes its antenna to one sector during each frame. In other words, the SH is implemented on the frame scale. Then, each frame is divided into number of time slots, where the combined CH sequence is executed (i.e., the CH is implemented on the time slot scale). The main goal of this paper is to design deterministic combined SCH scheme so as to tackle the sector and channel rendezvous problem.


## 2.2.3. Metrics

The proposed SH schemes as well as the combined SCH schemes will be evaluated according to the following metrics:(i)
Sector rendezvous latency (SRL): it is defined as the required latency (in number of sector frames) for a pair of SUs to achieve sector rendezvous. We consider the maximum and average latency (MSRL/ASRL). MSRL is defined as the upper bound of the SRL between the SUs for all the possible clock drifts between them(ii)
Time-to-rendezvous (TTR): it is defined as the required time (in number of time slots) for a pair of SUs to achieve sector and channel rendezvous simultaneously. Maximum and average time-to-rendezvous (MTTR/ATTR) are considered. MTTR means the required time for a guaranteed rendezvous even in the worst case.


## 3. Prime- and Even-Based Sequences Sector Hopping (PES-SH) Scheme

In this section, we propose an asymmetric-role SH scheme, called prime- and even-based sequences sector hopping (PES-SH) scheme, and then we analyze its theoretical performance.


### 3.1. Scheme Design

For ensuring a successful sector rendezvous between a pair of communicating SUs, the key for the deterministic design of our PES-SH scheme is to construct two SH sequences based on two coprime numbers. However, the coprimality is maintained between a pair of prime and even numbers that are relatively prime (i.e., coprime). In our PES-SH scheme, we assume thatNmax is a global variable known by all SUs, which indicates the maximum number of sectors by which any SU is allowed to divide its omnidirectional 2π transmission range. The value of Nmax is obtained based on the number of channels in the network; for example, for L number of channels, the value of Nmax could be 2×L. Accordingly, we consider two avoided sets:(1)
The Avoided Prime Set (APS) which contains the primes{2,3}(2)
The Avoided Even Set (AES) which contains any even number in the range[2,Pmax], such that this even number is dividable by any prime number in the range [5,Pmax]. Pmax is the smallest prime not less than Nmax. For example, if Nmax=20, then Pmax=23 and hence AES ={10,14,20,22}The APS and AES sets are avoided by the sender and receiver, respectively, when they construct their SH sequences. Without loss of generality, assume that sender and receiver haveNs and Nr antenna sectors, respectively, where Ns,Nr∈[1,Nmax]. The main idea for the rendezvous of our PES-SH scheme is to let one SU (sender) adjust the number of its sectors to be the smallest prime number greater than Ns. On the other hand, the other SU (receiver) adjusts the number of its sectors to the smallest even number which is not smaller than Nr and not in the AES. Accordingly, the adjusted prime number of sectors for the sender and the adjusted even number of sectors for the receiver are guaranteed to be relatively prime.Algorithms1 and 2 are used by the sender and receiver, respectively, to construct each round of their SH sequences. The generating steps of the PES-SH sequences are as follows.Algorithm 1:The sender SH generation algorithm (PS-SH).
Input: Ns,Ss.
Output: a round ω of the PS sequence for the sender s.
(1) Find the smallest prime (Ps>3) that is not smaller
than Ns.
(2) for  t=0:Ps-1  do
(3) if  ((tmodPs)<Ns)  then
(4) ωs(t)=Ss(t+1).
(5) else
(6) r is a random number ∈[1,Ns]
(7) ωs(t)=Ss(r).
(8) end if
(9) end for
(10) return  ωs.Algorithm 2:The receiver SH generation algorithm (ES-SH).
Input: Nr,Sr, AES.
Output: a round γ of the ES-SH sequence for the receiver r.
(1) Find (Er:Er∉AES) as the smallest even number that
is not smaller than Nr.
(2) for  t=0:Er-1  do
(3) if  ((tmodEr)<Nr)  then
(4) γr(t)=Sr(t+1).
(5) else
(6) r is a random number ∈[1,Nr]
(7) γr(t)=Sr(r).
(8) end if
(9) end for
(10) return  γr.


#### 3.1.1. Sender Sequence in PES-SH

When a SU has data to transmit, it serves as a sender and hence generates a prime-based (PS-SH) sequence as follows. First, given the sector setS={1,…,Ns}, randomly select a starting sector index i∈[1,Ns] and rotate S circularly starting from i as S=rotate(S,i-1). Second, adjust Ns to be the smallest prime number Ps which is not smaller than Ns and is not in the APS set (i.e., Ps should be 5 when Ns<5). Third, construct each round of the PS sequence which has a length equal to PS as follows: the kth sector index of the PS round is S(k) if k≤Ns; otherwise the kth sector is selected randomly form S when k>Ns. The sender will keep steering its antenna according to the PS sequence until it achieves sector rendezvous with its intended receiver.Consider the cases for the sender SUsX and V in Figure 1; SU X in Figure 1(a) has a prime number of sectors Nx=5, where Sx={1,2,…,5} is not rotated. Then the first round of the PSX SH sequence with a length 5 is [12345]. This round is repeated many times, where SUX continues steering its directional antenna into its sectors as shown in Figure 2(a) to achieve sector rendezvous with its receiver SUY. On the other hand, the sender SUV in Figure 1(b) has NV=4 number of sectors, so it selects PV=5 as the smallest prime which is larger than NV. SV is rotated to start from 3 and hence Sv={3,4,2,1}. Then the first round of the PSV SH sequence which has adjusted length equal to Pv=5 is [3421r], where r indicates a randomly selected sector from SV. The PSV SH sequence is constructed as many rounds as shown in Figure 2(b), where SUV keeps hopping on its sectors to achieve sector rendezvous with the receiver SUZ.Figure 2
Successful synchronous and asynchronous sector rendezvous for the two pairs of communicating SUs in Figure1.
(a)
Sector rendezvous between the senderX and the receiver Y on the rendezvous sector pair (2,3) for the cases when Y starts its SH with i slots later than X, where i∈[0,…,(PX-1)]
(b)
Sector rendezvous between the senderV and the receiver Z on the rendezvous sector pair (4,1) for the cases when Z starts SH with i slots earlier, where i∈[0,…,(EZ-1)]


#### 3.1.2. Receiver Sequence in PES-SH

If a SU has nothing to transmit, it serves as a receiver and generates an even-based (ES-SH) sequence as follows. First, randomly select a starting sector indexj∈[1,Nr] and circularly rotate the sector set S={1,…,Nr} starting from j as S=rotate(S,j-1). Second, adjust Nr to be the smallest even number Er which is not smaller than Nr and is not in the Avoided Even Set (AES). Finally, construct each round of the ES sequence which has a length equal to Er as follows: the kth sector index of the ES-SH round is S(k) if k≤Nr; otherwise the kth sector is selected randomly form S.Consider the receiverSUY in Figure 1(a) which has an even number of sectors NY=4 which is not in AES and does not rotate its SY set. The round of the ESY SH sequence with a length 4 is [1234]. This round is repeated many times by SUY in order to be paired by a sender as shown in Figure 2(a). On the other hand, the receiver SUZ in Figure 1(b) has NZ=3 sectors; hence it finds EZ=4 as the smallest even number larger than NZ and not in AES. SUZ rotates its SZ to start from sector 2 and hence SV={2,3,1}. Accordingly, a round of the ESZ SH sequence with a length adjusted to Ez=4 is [231r], where r is a randomly selected sector from Sz. The ESZ SH sequence is constructed in rounds as shown in Figure 2(b).


### 3.2. Scheme Analysis

In this subsection, we study the theoretical performance of the PES-SH, where the MSRL between any two arbitrary SUs performing the PES-SH is derived.Theorem 1.
The MSRL under the PES-SH scheme is(PsEr), where Ps and Er denote the adjusted prime and even numbers of the sectors for the sender and receiver SUs, respectively.Proof.
Suppose that the sector rendezvous pair is(hs,hr)∈{1,2,…,Ns}×{1,2,…,Nr}, where × here indicates the Cartesian product of the two SUs sectors sets. Without loss of generality, we assume that Ps<Er. Also, we assume that the receiver SUr starts its SH sequence with δ sector slots earlier than the start of the sender SUs. Accordingly, in each PS-SH period of SUs, the ES-SH sequence of SUr is rotate(ESr,δ). In the first round of the SH, when the sender SUs is on its hs sector, the receiver SUr is on the (u1=u0 mod Er+1) sector, where 1≤u0≤Nr. During the subsequent Er-1 rounds, while the sender SU is on its hs sector, the receiver SUr must be sequentially on u2=((u0+Ps)modEr+1), u3=((u0+2Ps)modEr+1),…,uEr=((u0+(Er-1)Ps)modEr+1). As Ps and Er are relatively prime, it can be easily proven with the help of the Chinese Reminder Theorem [31] that these u1,u2,…,uEr sectors where the receiver resides in the Er rounds are all different. Hence, there must exist a sector among them which is equal to hr. According to that and since every round of the PS-SH contains Ps sector hops, the SRL required to guarantee a sector rendezvous is upper bound by PsEr.


## 3.1. Scheme Design

For ensuring a successful sector rendezvous between a pair of communicating SUs, the key for the deterministic design of our PES-SH scheme is to construct two SH sequences based on two coprime numbers. However, the coprimality is maintained between a pair of prime and even numbers that are relatively prime (i.e., coprime). In our PES-SH scheme, we assume thatNmax is a global variable known by all SUs, which indicates the maximum number of sectors by which any SU is allowed to divide its omnidirectional 2π transmission range. The value of Nmax is obtained based on the number of channels in the network; for example, for L number of channels, the value of Nmax could be 2×L. Accordingly, we consider two avoided sets:(1)
The Avoided Prime Set (APS) which contains the primes{2,3}(2)
The Avoided Even Set (AES) which contains any even number in the range[2,Pmax], such that this even number is dividable by any prime number in the range [5,Pmax]. Pmax is the smallest prime not less than Nmax. For example, if Nmax=20, then Pmax=23 and hence AES ={10,14,20,22}The APS and AES sets are avoided by the sender and receiver, respectively, when they construct their SH sequences. Without loss of generality, assume that sender and receiver haveNs and Nr antenna sectors, respectively, where Ns,Nr∈[1,Nmax]. The main idea for the rendezvous of our PES-SH scheme is to let one SU (sender) adjust the number of its sectors to be the smallest prime number greater than Ns. On the other hand, the other SU (receiver) adjusts the number of its sectors to the smallest even number which is not smaller than Nr and not in the AES. Accordingly, the adjusted prime number of sectors for the sender and the adjusted even number of sectors for the receiver are guaranteed to be relatively prime.Algorithms1 and 2 are used by the sender and receiver, respectively, to construct each round of their SH sequences. The generating steps of the PES-SH sequences are as follows.Algorithm 1:The sender SH generation algorithm (PS-SH).
Input: Ns,Ss.
Output: a round ω of the PS sequence for the sender s.
(1) Find the smallest prime (Ps>3) that is not smaller
than Ns.
(2) for  t=0:Ps-1  do
(3) if  ((tmodPs)<Ns)  then
(4) ωs(t)=Ss(t+1).
(5) else
(6) r is a random number ∈[1,Ns]
(7) ωs(t)=Ss(r).
(8) end if
(9) end for
(10) return  ωs.Algorithm 2:The receiver SH generation algorithm (ES-SH).
Input: Nr,Sr, AES.
Output: a round γ of the ES-SH sequence for the receiver r.
(1) Find (Er:Er∉AES) as the smallest even number that
is not smaller than Nr.
(2) for  t=0:Er-1  do
(3) if  ((tmodEr)<Nr)  then
(4) γr(t)=Sr(t+1).
(5) else
(6) r is a random number ∈[1,Nr]
(7) γr(t)=Sr(r).
(8) end if
(9) end for
(10) return  γr.


### 3.1.1. Sender Sequence in PES-SH

When a SU has data to transmit, it serves as a sender and hence generates a prime-based (PS-SH) sequence as follows. First, given the sector setS={1,…,Ns}, randomly select a starting sector index i∈[1,Ns] and rotate S circularly starting from i as S=rotate(S,i-1). Second, adjust Ns to be the smallest prime number Ps which is not smaller than Ns and is not in the APS set (i.e., Ps should be 5 when Ns<5). Third, construct each round of the PS sequence which has a length equal to PS as follows: the kth sector index of the PS round is S(k) if k≤Ns; otherwise the kth sector is selected randomly form S when k>Ns. The sender will keep steering its antenna according to the PS sequence until it achieves sector rendezvous with its intended receiver.Consider the cases for the sender SUsX and V in Figure 1; SU X in Figure 1(a) has a prime number of sectors Nx=5, where Sx={1,2,…,5} is not rotated. Then the first round of the PSX SH sequence with a length 5 is [12345]. This round is repeated many times, where SUX continues steering its directional antenna into its sectors as shown in Figure 2(a) to achieve sector rendezvous with its receiver SUY. On the other hand, the sender SUV in Figure 1(b) has NV=4 number of sectors, so it selects PV=5 as the smallest prime which is larger than NV. SV is rotated to start from 3 and hence Sv={3,4,2,1}. Then the first round of the PSV SH sequence which has adjusted length equal to Pv=5 is [3421r], where r indicates a randomly selected sector from SV. The PSV SH sequence is constructed as many rounds as shown in Figure 2(b), where SUV keeps hopping on its sectors to achieve sector rendezvous with the receiver SUZ.Figure 2
Successful synchronous and asynchronous sector rendezvous for the two pairs of communicating SUs in Figure1.
(a)
Sector rendezvous between the senderX and the receiver Y on the rendezvous sector pair (2,3) for the cases when Y starts its SH with i slots later than X, where i∈[0,…,(PX-1)]
(b)
Sector rendezvous between the senderV and the receiver Z on the rendezvous sector pair (4,1) for the cases when Z starts SH with i slots earlier, where i∈[0,…,(EZ-1)]


### 3.1.2. Receiver Sequence in PES-SH

If a SU has nothing to transmit, it serves as a receiver and generates an even-based (ES-SH) sequence as follows. First, randomly select a starting sector indexj∈[1,Nr] and circularly rotate the sector set S={1,…,Nr} starting from j as S=rotate(S,j-1). Second, adjust Nr to be the smallest even number Er which is not smaller than Nr and is not in the Avoided Even Set (AES). Finally, construct each round of the ES sequence which has a length equal to Er as follows: the kth sector index of the ES-SH round is S(k) if k≤Nr; otherwise the kth sector is selected randomly form S.Consider the receiverSUY in Figure 1(a) which has an even number of sectors NY=4 which is not in AES and does not rotate its SY set. The round of the ESY SH sequence with a length 4 is [1234]. This round is repeated many times by SUY in order to be paired by a sender as shown in Figure 2(a). On the other hand, the receiver SUZ in Figure 1(b) has NZ=3 sectors; hence it finds EZ=4 as the smallest even number larger than NZ and not in AES. SUZ rotates its SZ to start from sector 2 and hence SV={2,3,1}. Accordingly, a round of the ESZ SH sequence with a length adjusted to Ez=4 is [231r], where r is a randomly selected sector from Sz. The ESZ SH sequence is constructed in rounds as shown in Figure 2(b).


## 3.1.1. Sender Sequence in PES-SH

When a SU has data to transmit, it serves as a sender and hence generates a prime-based (PS-SH) sequence as follows. First, given the sector setS={1,…,Ns}, randomly select a starting sector index i∈[1,Ns] and rotate S circularly starting from i as S=rotate(S,i-1). Second, adjust Ns to be the smallest prime number Ps which is not smaller than Ns and is not in the APS set (i.e., Ps should be 5 when Ns<5). Third, construct each round of the PS sequence which has a length equal to PS as follows: the kth sector index of the PS round is S(k) if k≤Ns; otherwise the kth sector is selected randomly form S when k>Ns. The sender will keep steering its antenna according to the PS sequence until it achieves sector rendezvous with its intended receiver.Consider the cases for the sender SUsX and V in Figure 1; SU X in Figure 1(a) has a prime number of sectors Nx=5, where Sx={1,2,…,5} is not rotated. Then the first round of the PSX SH sequence with a length 5 is [12345]. This round is repeated many times, where SUX continues steering its directional antenna into its sectors as shown in Figure 2(a) to achieve sector rendezvous with its receiver SUY. On the other hand, the sender SUV in Figure 1(b) has NV=4 number of sectors, so it selects PV=5 as the smallest prime which is larger than NV. SV is rotated to start from 3 and hence Sv={3,4,2,1}. Then the first round of the PSV SH sequence which has adjusted length equal to Pv=5 is [3421r], where r indicates a randomly selected sector from SV. The PSV SH sequence is constructed as many rounds as shown in Figure 2(b), where SUV keeps hopping on its sectors to achieve sector rendezvous with the receiver SUZ.Figure 2
Successful synchronous and asynchronous sector rendezvous for the two pairs of communicating SUs in Figure1.
(a)
Sector rendezvous between the senderX and the receiver Y on the rendezvous sector pair (2,3) for the cases when Y starts its SH with i slots later than X, where i∈[0,…,(PX-1)]
(b)
Sector rendezvous between the senderV and the receiver Z on the rendezvous sector pair (4,1) for the cases when Z starts SH with i slots earlier, where i∈[0,…,(EZ-1)]


## 3.1.2. Receiver Sequence in PES-SH

If a SU has nothing to transmit, it serves as a receiver and generates an even-based (ES-SH) sequence as follows. First, randomly select a starting sector indexj∈[1,Nr] and circularly rotate the sector set S={1,…,Nr} starting from j as S=rotate(S,j-1). Second, adjust Nr to be the smallest even number Er which is not smaller than Nr and is not in the Avoided Even Set (AES). Finally, construct each round of the ES sequence which has a length equal to Er as follows: the kth sector index of the ES-SH round is S(k) if k≤Nr; otherwise the kth sector is selected randomly form S.Consider the receiverSUY in Figure 1(a) which has an even number of sectors NY=4 which is not in AES and does not rotate its SY set. The round of the ESY SH sequence with a length 4 is [1234]. This round is repeated many times by SUY in order to be paired by a sender as shown in Figure 2(a). On the other hand, the receiver SUZ in Figure 1(b) has NZ=3 sectors; hence it finds EZ=4 as the smallest even number larger than NZ and not in AES. SUZ rotates its SZ to start from sector 2 and hence SV={2,3,1}. Accordingly, a round of the ESZ SH sequence with a length adjusted to Ez=4 is [231r], where r is a randomly selected sector from Sz. The ESZ SH sequence is constructed in rounds as shown in Figure 2(b).


## 3.2. Scheme Analysis

In this subsection, we study the theoretical performance of the PES-SH, where the MSRL between any two arbitrary SUs performing the PES-SH is derived.Theorem 1.
The MSRL under the PES-SH scheme is(PsEr), where Ps and Er denote the adjusted prime and even numbers of the sectors for the sender and receiver SUs, respectively.Proof.
Suppose that the sector rendezvous pair is(hs,hr)∈{1,2,…,Ns}×{1,2,…,Nr}, where × here indicates the Cartesian product of the two SUs sectors sets. Without loss of generality, we assume that Ps<Er. Also, we assume that the receiver SUr starts its SH sequence with δ sector slots earlier than the start of the sender SUs. Accordingly, in each PS-SH period of SUs, the ES-SH sequence of SUr is rotate(ESr,δ). In the first round of the SH, when the sender SUs is on its hs sector, the receiver SUr is on the (u1=u0 mod Er+1) sector, where 1≤u0≤Nr. During the subsequent Er-1 rounds, while the sender SU is on its hs sector, the receiver SUr must be sequentially on u2=((u0+Ps)modEr+1), u3=((u0+2Ps)modEr+1),…,uEr=((u0+(Er-1)Ps)modEr+1). As Ps and Er are relatively prime, it can be easily proven with the help of the Chinese Reminder Theorem [31] that these u1,u2,…,uEr sectors where the receiver resides in the Er rounds are all different. Hence, there must exist a sector among them which is equal to hr. According to that and since every round of the PS-SH contains Ps sector hops, the SRL required to guarantee a sector rendezvous is upper bound by PsEr.


## 4. Interleaved Prime- and Even-Based Sequences Sector Hopping (IPES-SH) Scheme

In the previous section, the PES-SH scheme was designed using the asymmetric approach which requires that each SU have a preassigned role as either a sender or a receiver. In this section, we introduce our interleaved prime- and even-based sequences (IPES-SH) scheme, which is symmetric (i.e., no preassigned role assumption).


### 4.1. Scheme Design

In our symmetric IPES-SH scheme, every SU generates its SH sequence with the help of a binary bit sequence such as its globally unique ID. The SH sequence is constructed as an interleaved sequence of several PS and ES SH sequences through a two-step approach. Firstly, each SU transforms its unique ID according to a certain design into another ID sequence so that it is cyclically unique; that is, the resulting ID sequences of any two SUs are cyclic rotationally distinct to each other. Secondly, the SU replaces any bit of 1 (or 0) in its new ID sequence with a PS-based (or ES-based) SH sequence. Accordingly, for any pair of SUs, the cyclic uniqueness property will guarantee the existence of some time instances, where the two SUs are playing different roles. Hence, the sector rendezvous is achieved when one SU is hopping according to its PS sequence while the other SU is hopping based on its ES sequence and vice versa.Several methods have been proposed in the literature to transform the unique ID into another cyclically unique binary sequence. In [32], a method was proposed to expand the m-bit ID into another 3m-bit extended ID that is cyclically unique. The unique m-bit ID in that method is expanded by appending m-bit consecutive 0’s into the beginning of the ID and other m-bit consecutive 1’s at the end of the ID. Another method for generating cyclically unique IDs that are used for the construction of symmetric role SH sequences has been proposed in [30]. The method appends the original m-bit ID with other (m+1)-bits of consecutive 0’s and 1’s, which results in (2m+1)-bits expanded ID sequence. However, the extended ID sequences generated by these methods are relatively long, especially for the former method. This results in long rendezvous delay when they are used for constructing symmetric role sequences. Therefore, we propose an alternative method for constructing cyclic rotationally distinct sequences, which provides shorter extended ID lengths than the methods in [30, 32]. So, it provides shorter sector rendezvous delay when it is used for constructing symmetric role sequences in our IPES-SH scheme.


#### 4.1.1. Constructing the Cyclic Unique ID Sequences

In our method, eachm-bit ID is extended by appending only m-bits of 1’s and 0’s in the beginning and in the end of the ID.Lemma 2.
Given any twom-bit ID sequences α={α1,…,αm} and β={β1,…,βm}, let a and b be two 2m-bit expanded ID sequences generated from α and β as follows:a=def1(⌈m/2⌉)α0(⌊m/2⌋) and b=def1(⌈m/2⌉)β0(⌊m/2⌋), where 1· is a bit sequence composed of only 1’s and 0· is a bit sequence composed of only 0’s. Then a and b arecyclic rotationally distinct from each other, which means that(1)Ifa≠b⟹a≠rotateb,k,∀k∈0,2m-1.Proof.
To prove the above lemma, we consider all the possible cases that may happen when sequenceb is rotated with (k∈(0,2m-1]). We show in each case that bits in sequence a and other bits in sequence b′=rotate(b,k) have different values, even though these bits are in the same positions. Considering the five cases in Figure 3, it is sufficient to prove that a and b′=rotate(b,k) arecyclic rotationally distinct to each other.Figure 3
Illustration of the five cases in the proof of Lemma2.Case  1 (k∈(0,⌈m/2⌉]). As indicated by the red arrow in Figure 3, it holds that a2m=0 and b2m′=1.Case  2 (k∈(⌈m/2⌉,m)). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉+m+1)=0 and bm/2+m+1′=1.Case  3 (k=m). As indicated by the m red arrows in Figure 3, the m bits of sequence a starting from a(⌈m/2⌉+1) are {α1,…,αm-1}, while the m bits of b′ in the same positions are 0(⌊m/2⌋)∥1(⌈m/2⌉). On the other hand, as indicated by the m purple arrows in Figure 3, the first ⌈m/2⌉ bits of sequence a are 1’s and the last ⌊m/2⌋ are 0’s, whereas the first ⌈m/2⌉ bits of b′ are {β(⌈m/2⌉),…,βm} and the last ⌊m/2⌋ bits are {β1,…,β(⌊m/2⌋)}. And because α≠β, it holds that there must be at least a single bit that is different in a and b′.Case  4 (k∈(m,m+⌊m/2⌋]). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉)=1 and bm/2′=0.Case  5 (k∈(m+⌊m/2⌋,2m-1]). As indicated by the red arrow in Figure 3, it holds that a1=1 and b1′=0.According to these possible cases, we conclude thata≠rotate(b,k),∀k∈(0,2m-1]. In Figure 4, we give an example for two ID sequences of original lengths m=4 which are expanded to m=8 bits. The figure illustrates the cyclic uniqueness property between the IDs for all the rotation cases (i.e., ∀k∈[0,7]).Figure 4
An illustrative example for the correctness of our cyclic rotationally distinct sequences construction method whenm=4.


#### 4.1.2. Generating the Interleaved Sector Hopping Sequence

We now explain how to generate the symmetric IPES-SH sequence for any SU, saySUi. Let the number of sectors for SUi be Ni and hence the sector set Si={1,…,Ni}. Suppose that SUi has m-bits globally unique ID sequence, α, which is extended by our above method to 2m-bits sequence a=1(⌈m/2⌉)α0(⌊m/2⌋).(i)
Select randomly a starting indexk∈[1,Ni] and generate a rotated set SiP by rotating Si circularly starting from k as SiP=rotate(Si,k-1). Also, generate another sector indices set as a reverse of SiP which is SiE=Reverse(SiP).(ii)
Find(Pi:Pi>3) as the smallest prime number that is not smaller than Ni. Also find (Ei:Ei∉ AES) as the smallest even number that is not smaller than Ni.(iii)
Define an empty matrixMi that has 2m columns and Pi×Ei rows.(iv)
Fill the matrix by mapping each bit ina to a certain column as described in Algorithm 3.(v)
Generate the SH sequence by concatenating the matrix rows (row by row).SUi keeps hopping according to this generated SH sequence and repeats it in order to rendezvous with its pair partner SU.Algorithm 3
(1) for  c=1:2m  do
(2) if  (ac==1) then
(3)  Invoke Algorithm 1 with SiP and Ni to construct
a round ω of an PS sequence.
(4)  generate ω′ by repeating ω for Ei times.
(5)  Map the cth column of the matrix with ω′.
(6) SiP=Rotate(SiP,1).
(7) else
(8)  Invoke Algorithm 2 with SiE and Ni to construct
a round γ of an ES sequence.
(9)  generate γ′ by repeating γ for Pi times.
(10)  Map the cth column of the matrix with γ′.
(11) SiE=Rotate(SiE,1).
(12) end if
(13) end forFigure5 illustrates the IPES-SH sequence construction matrices for SUV and SUZ in our previous example in Section 3.1 (Figure 1(b)). In Figure 5, the ID sequence of SUV that has Nv=4 sectors is α={1,0} which is expanded to a={1,1,0,0}. On the other side, the ID sequence of SUV that has Nz=3 sectors is β={0,1} which is expanded also to b={1,0,1,0}. The constructed matrix for SUV has Pv×Ev=5×4=20 rows and 2m=4 columns. Similarly, SUZ constructs its matrix with Pz×Ez=5×4=20 rows and 2m=4 columns. Each SU will assign its matrix columns with either PS sequence or ES sequence based on the corresponding bits of its extended ID sequence. For example, since the first bit of SUV extended ID is one, SUV firstly generates its first sector sets as SvP={3,4,1,2} and then invokes Algorithm 1 with SvP and Nv=4 to construct a round of a PS sequence ω=[3412r]. This round ω is repeated for Ev=4 times and assigned to the first column of SUV matrix. Similarly, since the second bit of SUV extended ID is one, the second column of SUV matrix is assigned with a repeated sequence of the PS sequence [4123r], which is constructed after rotating the sector set SvP by one. On the other hand, SUV assigns the third and fourth columns of its matrix with ES sequences because the corresponding 3rd and 4th bits of its extended ID sequence are zeros. Specifically, SUV invokes Algorithm 2 with SvE=Reverse(SvP) and Nv=4 to construct a round of an ES sequence γ=[2143]. This round γ of the ES sequence is then repeated for Pv=5 times and assigned to the third column of SUV matrix. Similarly, the fourth column of SUV matrix is filled with the ES sequence [1432] after repeating it for Pv=5 times. Note that SUZ will follow the same procedures as SUV to construct its matrix with taking into account the different expanded ID sequence bz={1,0,1,0} and Nz, as well as the initial sector sets SzP and SzE.Figure 5
The construction of the IPES matricesMV and MZ for SUV and SUZ, respectively. NV=4 and NZ=3; αV={1,0} and βZ={0,1}. So the expanded ID sequences are aV={1,1,0,0} and bZ={1,0,1,0}.Figure6 shows partial sector slots of the IPES-SH sequences for the two SUs (SUV and SUZ). As depicted from the figure, the IPES-SH sequence of each SU is generated by concatenating the rows of the SU constructed matrix in Figure 5 row by row. The sequences are generated as interleaved slots of PS (light blue) and ES (gray) slots according to the respective columns types in the matrices. The figure also illustrates the rendezvous sector occurrence between the SUs (indicated by the green circle) on the sector rendezvous pair (4,1).Figure 6
IPES-SH sector rendezvous betweenSUV and SUZ for the synchronous case.


### 4.2. Scheme Analysis

In this subsection, the theoretical performance of IPES-SH scheme is studied where the MSRL is derived.Theorem 3.
Under the IPES-SH scheme, the MSRL between a pair of SUs(SUi and SUj) is 2m×(max{(PiEj),(EiPj)}).Proof.
To prove that IPES-SH hasMSRL=2m(max{(PiEj),(EiPj)}), it is sufficient to prove that any arbitrary pair of IPES-SH sequences, for example, IPESi and IPESj, can achieve a successful sector rendezvous within 2m (max{(PiEj),(EiPj)}) sector slots.
LetIPESi and IPESj be the corresponding IPES-SH sequences of IPES matrices Mi and Mj (i.e., IPESi and IPESj are generated by concatenating the rows of matrices Mi and Mj, resp.). For example, Figures 5(a) and 5(b) show the IPES matrices MV and MZ, respectively. Without loss of generality, assume that SUj starts its SH sequence δ sector slots earlier than the start of SUi. In each SH period of SUi, the SH sequence of SUj is rotate(IPESj, δ). Clearly, the rendezvous between this pair of SUs is the same as the rendezvous of Mi and M(j,δ). Suppose that the sector rendezvous pair is (hi,hj)∈{1,2,…,Ni}×{1,2,…,Nj}. The rendezvous of the matrices is a pair of entries in the matrices whose value in Mi is hi and its values in M(j,δ) is hj. Without loss of generality, suppose that the sector slot shift δ=2m×δR+δC, where δR∈[0,(Pj×Ej)-1], is the shift of row and δC∈[0,(2m)-1] is the shift of column. Below, we consider the two different cases for rendezvous of IPESi and IPESj.Case  1 (δC=0). In this case, it is implied that there is no column shift. Recall that the expanded ID sequences of SUi and SUj are distinct. Since the columns types of the matrices are assigned based on these distinct expanded IDs, it is guaranteed that there must exist at least a single common column f in both matrices which is a PS-column in one matrix and an ES-column in the other matrix, and vice versa. In other words, the fth column of Mi contains a PS-SH sequence (reps., ES-SH), while the same position fth column in M(j,δ) contains an ES-SH (resp., PS-SH). By Theorem 1, we know that when SUi and SUj repeat the PS-SH (resp., ES-SH) and the ES-SH (resp., PS-SH) sequences, respectively, they rendezvous within Pi×Ej (resp., Ei×Pj). Meanwhile, since the elements of a specific column of each matrix appear in the corresponding IPES-SH sequence every 2m slots, for any value of the row shift δR, Mi and M(j,δ) are guaranteed to rendezvous on their fth columns no later than 2m×max{(PiEj),(EiPj)}. Specifically, the rendezvous happens when an entry of the fth column in Mi is hi, while the same position entry of the fth column in M(j,δ) is hj. For example, Figure 5 shows the rendezvous of MV and MZ for the synchronous case where the slots shift δ=2m×0+0=0. The sector rendezvous occurs between the second columns of MV and MZ which is indicated by the green entry in MZ. However, Figure 7(a) shows the IPES matrix of SUZ when it is shifted with row shift δR=10. Hence, this means that δ=2m×10+0=40. The rendezvous between MV in Figure 5 and M(Z,40) in Figure 7(a) is achieved at their third columns.Figure 7
The IPES matrixMZ for SUZ when it is circularly rotated with (a) δ=2m×10+0=40 sector slots and (b) δ=2m×2+1=41 slots.Case  2 (δC≠0). In this case, it holds that there is a column shift δC∈[1,(2m-1)]. Let a and b be the expanded ID sequences of SUi and SUj, respectively. By Lemma 2, we know that a and b′=rotate(b,k), where k∈(2m-1) arecyclic rotationally distinct to each other. Thus, for a column shift δC∈[1,(2m-1)] of matrix Mj, there must exist a column f in matrix Mi which has different type than the same position fth column in the shifted matrix M(j,δC). Accordingly, the rendezvous is guaranteed to occur at the fth columns in the matrices, despite any value of the row shift δR. For example, Figure 7(b) shows the shifted IPES matrix of SUZ when the column shift δC=1 and the row shift δR=10, which results in δ=2m×10+1=41 slots. The first rendezvous between MV in Figure 5 and M(Z,41) in Figure 7(b) is achieved at the forth columns.Summarizing the discussion above, we show that, in IPES-SH, any two SUs are guaranteed to rendezvous on their sector rendezvous pair within SH period2m×max{(PiEj),(EiPj)}.


## 4.1. Scheme Design

In our symmetric IPES-SH scheme, every SU generates its SH sequence with the help of a binary bit sequence such as its globally unique ID. The SH sequence is constructed as an interleaved sequence of several PS and ES SH sequences through a two-step approach. Firstly, each SU transforms its unique ID according to a certain design into another ID sequence so that it is cyclically unique; that is, the resulting ID sequences of any two SUs are cyclic rotationally distinct to each other. Secondly, the SU replaces any bit of 1 (or 0) in its new ID sequence with a PS-based (or ES-based) SH sequence. Accordingly, for any pair of SUs, the cyclic uniqueness property will guarantee the existence of some time instances, where the two SUs are playing different roles. Hence, the sector rendezvous is achieved when one SU is hopping according to its PS sequence while the other SU is hopping based on its ES sequence and vice versa.Several methods have been proposed in the literature to transform the unique ID into another cyclically unique binary sequence. In [32], a method was proposed to expand the m-bit ID into another 3m-bit extended ID that is cyclically unique. The unique m-bit ID in that method is expanded by appending m-bit consecutive 0’s into the beginning of the ID and other m-bit consecutive 1’s at the end of the ID. Another method for generating cyclically unique IDs that are used for the construction of symmetric role SH sequences has been proposed in [30]. The method appends the original m-bit ID with other (m+1)-bits of consecutive 0’s and 1’s, which results in (2m+1)-bits expanded ID sequence. However, the extended ID sequences generated by these methods are relatively long, especially for the former method. This results in long rendezvous delay when they are used for constructing symmetric role sequences. Therefore, we propose an alternative method for constructing cyclic rotationally distinct sequences, which provides shorter extended ID lengths than the methods in [30, 32]. So, it provides shorter sector rendezvous delay when it is used for constructing symmetric role sequences in our IPES-SH scheme.


### 4.1.1. Constructing the Cyclic Unique ID Sequences

In our method, eachm-bit ID is extended by appending only m-bits of 1’s and 0’s in the beginning and in the end of the ID.Lemma 2.
Given any twom-bit ID sequences α={α1,…,αm} and β={β1,…,βm}, let a and b be two 2m-bit expanded ID sequences generated from α and β as follows:a=def1(⌈m/2⌉)α0(⌊m/2⌋) and b=def1(⌈m/2⌉)β0(⌊m/2⌋), where 1· is a bit sequence composed of only 1’s and 0· is a bit sequence composed of only 0’s. Then a and b arecyclic rotationally distinct from each other, which means that(1)Ifa≠b⟹a≠rotateb,k,∀k∈0,2m-1.Proof.
To prove the above lemma, we consider all the possible cases that may happen when sequenceb is rotated with (k∈(0,2m-1]). We show in each case that bits in sequence a and other bits in sequence b′=rotate(b,k) have different values, even though these bits are in the same positions. Considering the five cases in Figure 3, it is sufficient to prove that a and b′=rotate(b,k) arecyclic rotationally distinct to each other.Figure 3
Illustration of the five cases in the proof of Lemma2.Case  1 (k∈(0,⌈m/2⌉]). As indicated by the red arrow in Figure 3, it holds that a2m=0 and b2m′=1.Case  2 (k∈(⌈m/2⌉,m)). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉+m+1)=0 and bm/2+m+1′=1.Case  3 (k=m). As indicated by the m red arrows in Figure 3, the m bits of sequence a starting from a(⌈m/2⌉+1) are {α1,…,αm-1}, while the m bits of b′ in the same positions are 0(⌊m/2⌋)∥1(⌈m/2⌉). On the other hand, as indicated by the m purple arrows in Figure 3, the first ⌈m/2⌉ bits of sequence a are 1’s and the last ⌊m/2⌋ are 0’s, whereas the first ⌈m/2⌉ bits of b′ are {β(⌈m/2⌉),…,βm} and the last ⌊m/2⌋ bits are {β1,…,β(⌊m/2⌋)}. And because α≠β, it holds that there must be at least a single bit that is different in a and b′.Case  4 (k∈(m,m+⌊m/2⌋]). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉)=1 and bm/2′=0.Case  5 (k∈(m+⌊m/2⌋,2m-1]). As indicated by the red arrow in Figure 3, it holds that a1=1 and b1′=0.According to these possible cases, we conclude thata≠rotate(b,k),∀k∈(0,2m-1]. In Figure 4, we give an example for two ID sequences of original lengths m=4 which are expanded to m=8 bits. The figure illustrates the cyclic uniqueness property between the IDs for all the rotation cases (i.e., ∀k∈[0,7]).Figure 4
An illustrative example for the correctness of our cyclic rotationally distinct sequences construction method whenm=4.


### 4.1.2. Generating the Interleaved Sector Hopping Sequence

We now explain how to generate the symmetric IPES-SH sequence for any SU, saySUi. Let the number of sectors for SUi be Ni and hence the sector set Si={1,…,Ni}. Suppose that SUi has m-bits globally unique ID sequence, α, which is extended by our above method to 2m-bits sequence a=1(⌈m/2⌉)α0(⌊m/2⌋).(i)
Select randomly a starting indexk∈[1,Ni] and generate a rotated set SiP by rotating Si circularly starting from k as SiP=rotate(Si,k-1). Also, generate another sector indices set as a reverse of SiP which is SiE=Reverse(SiP).(ii)
Find(Pi:Pi>3) as the smallest prime number that is not smaller than Ni. Also find (Ei:Ei∉ AES) as the smallest even number that is not smaller than Ni.(iii)
Define an empty matrixMi that has 2m columns and Pi×Ei rows.(iv)
Fill the matrix by mapping each bit ina to a certain column as described in Algorithm 3.(v)
Generate the SH sequence by concatenating the matrix rows (row by row).SUi keeps hopping according to this generated SH sequence and repeats it in order to rendezvous with its pair partner SU.Algorithm 3
(1) for  c=1:2m  do
(2) if  (ac==1) then
(3)  Invoke Algorithm 1 with SiP and Ni to construct
a round ω of an PS sequence.
(4)  generate ω′ by repeating ω for Ei times.
(5)  Map the cth column of the matrix with ω′.
(6) SiP=Rotate(SiP,1).
(7) else
(8)  Invoke Algorithm 2 with SiE and Ni to construct
a round γ of an ES sequence.
(9)  generate γ′ by repeating γ for Pi times.
(10)  Map the cth column of the matrix with γ′.
(11) SiE=Rotate(SiE,1).
(12) end if
(13) end forFigure5 illustrates the IPES-SH sequence construction matrices for SUV and SUZ in our previous example in Section 3.1 (Figure 1(b)). In Figure 5, the ID sequence of SUV that has Nv=4 sectors is α={1,0} which is expanded to a={1,1,0,0}. On the other side, the ID sequence of SUV that has Nz=3 sectors is β={0,1} which is expanded also to b={1,0,1,0}. The constructed matrix for SUV has Pv×Ev=5×4=20 rows and 2m=4 columns. Similarly, SUZ constructs its matrix with Pz×Ez=5×4=20 rows and 2m=4 columns. Each SU will assign its matrix columns with either PS sequence or ES sequence based on the corresponding bits of its extended ID sequence. For example, since the first bit of SUV extended ID is one, SUV firstly generates its first sector sets as SvP={3,4,1,2} and then invokes Algorithm 1 with SvP and Nv=4 to construct a round of a PS sequence ω=[3412r]. This round ω is repeated for Ev=4 times and assigned to the first column of SUV matrix. Similarly, since the second bit of SUV extended ID is one, the second column of SUV matrix is assigned with a repeated sequence of the PS sequence [4123r], which is constructed after rotating the sector set SvP by one. On the other hand, SUV assigns the third and fourth columns of its matrix with ES sequences because the corresponding 3rd and 4th bits of its extended ID sequence are zeros. Specifically, SUV invokes Algorithm 2 with SvE=Reverse(SvP) and Nv=4 to construct a round of an ES sequence γ=[2143]. This round γ of the ES sequence is then repeated for Pv=5 times and assigned to the third column of SUV matrix. Similarly, the fourth column of SUV matrix is filled with the ES sequence [1432] after repeating it for Pv=5 times. Note that SUZ will follow the same procedures as SUV to construct its matrix with taking into account the different expanded ID sequence bz={1,0,1,0} and Nz, as well as the initial sector sets SzP and SzE.Figure 5
The construction of the IPES matricesMV and MZ for SUV and SUZ, respectively. NV=4 and NZ=3; αV={1,0} and βZ={0,1}. So the expanded ID sequences are aV={1,1,0,0} and bZ={1,0,1,0}.Figure6 shows partial sector slots of the IPES-SH sequences for the two SUs (SUV and SUZ). As depicted from the figure, the IPES-SH sequence of each SU is generated by concatenating the rows of the SU constructed matrix in Figure 5 row by row. The sequences are generated as interleaved slots of PS (light blue) and ES (gray) slots according to the respective columns types in the matrices. The figure also illustrates the rendezvous sector occurrence between the SUs (indicated by the green circle) on the sector rendezvous pair (4,1).Figure 6
IPES-SH sector rendezvous betweenSUV and SUZ for the synchronous case.


## 4.1.1. Constructing the Cyclic Unique ID Sequences

In our method, eachm-bit ID is extended by appending only m-bits of 1’s and 0’s in the beginning and in the end of the ID.Lemma 2.
Given any twom-bit ID sequences α={α1,…,αm} and β={β1,…,βm}, let a and b be two 2m-bit expanded ID sequences generated from α and β as follows:a=def1(⌈m/2⌉)α0(⌊m/2⌋) and b=def1(⌈m/2⌉)β0(⌊m/2⌋), where 1· is a bit sequence composed of only 1’s and 0· is a bit sequence composed of only 0’s. Then a and b arecyclic rotationally distinct from each other, which means that(1)Ifa≠b⟹a≠rotateb,k,∀k∈0,2m-1.Proof.
To prove the above lemma, we consider all the possible cases that may happen when sequenceb is rotated with (k∈(0,2m-1]). We show in each case that bits in sequence a and other bits in sequence b′=rotate(b,k) have different values, even though these bits are in the same positions. Considering the five cases in Figure 3, it is sufficient to prove that a and b′=rotate(b,k) arecyclic rotationally distinct to each other.Figure 3
Illustration of the five cases in the proof of Lemma2.Case  1 (k∈(0,⌈m/2⌉]). As indicated by the red arrow in Figure 3, it holds that a2m=0 and b2m′=1.Case  2 (k∈(⌈m/2⌉,m)). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉+m+1)=0 and bm/2+m+1′=1.Case  3 (k=m). As indicated by the m red arrows in Figure 3, the m bits of sequence a starting from a(⌈m/2⌉+1) are {α1,…,αm-1}, while the m bits of b′ in the same positions are 0(⌊m/2⌋)∥1(⌈m/2⌉). On the other hand, as indicated by the m purple arrows in Figure 3, the first ⌈m/2⌉ bits of sequence a are 1’s and the last ⌊m/2⌋ are 0’s, whereas the first ⌈m/2⌉ bits of b′ are {β(⌈m/2⌉),…,βm} and the last ⌊m/2⌋ bits are {β1,…,β(⌊m/2⌋)}. And because α≠β, it holds that there must be at least a single bit that is different in a and b′.Case  4 (k∈(m,m+⌊m/2⌋]). As indicated by the red arrow in Figure 3, it holds that a(⌈m/2⌉)=1 and bm/2′=0.Case  5 (k∈(m+⌊m/2⌋,2m-1]). As indicated by the red arrow in Figure 3, it holds that a1=1 and b1′=0.According to these possible cases, we conclude thata≠rotate(b,k),∀k∈(0,2m-1]. In Figure 4, we give an example for two ID sequences of original lengths m=4 which are expanded to m=8 bits. The figure illustrates the cyclic uniqueness property between the IDs for all the rotation cases (i.e., ∀k∈[0,7]).Figure 4
An illustrative example for the correctness of our cyclic rotationally distinct sequences construction method whenm=4.


## 4.1.2. Generating the Interleaved Sector Hopping Sequence

We now explain how to generate the symmetric IPES-SH sequence for any SU, saySUi. Let the number of sectors for SUi be Ni and hence the sector set Si={1,…,Ni}. Suppose that SUi has m-bits globally unique ID sequence, α, which is extended by our above method to 2m-bits sequence a=1(⌈m/2⌉)α0(⌊m/2⌋).(i)
Select randomly a starting indexk∈[1,Ni] and generate a rotated set SiP by rotating Si circularly starting from k as SiP=rotate(Si,k-1). Also, generate another sector indices set as a reverse of SiP which is SiE=Reverse(SiP).(ii)
Find(Pi:Pi>3) as the smallest prime number that is not smaller than Ni. Also find (Ei:Ei∉ AES) as the smallest even number that is not smaller than Ni.(iii)
Define an empty matrixMi that has 2m columns and Pi×Ei rows.(iv)
Fill the matrix by mapping each bit ina to a certain column as described in Algorithm 3.(v)
Generate the SH sequence by concatenating the matrix rows (row by row).SUi keeps hopping according to this generated SH sequence and repeats it in order to rendezvous with its pair partner SU.Algorithm 3
(1) for  c=1:2m  do
(2) if  (ac==1) then
(3)  Invoke Algorithm 1 with SiP and Ni to construct
a round ω of an PS sequence.
(4)  generate ω′ by repeating ω for Ei times.
(5)  Map the cth column of the matrix with ω′.
(6) SiP=Rotate(SiP,1).
(7) else
(8)  Invoke Algorithm 2 with SiE and Ni to construct
a round γ of an ES sequence.
(9)  generate γ′ by repeating γ for Pi times.
(10)  Map the cth column of the matrix with γ′.
(11) SiE=Rotate(SiE,1).
(12) end if
(13) end forFigure5 illustrates the IPES-SH sequence construction matrices for SUV and SUZ in our previous example in Section 3.1 (Figure 1(b)). In Figure 5, the ID sequence of SUV that has Nv=4 sectors is α={1,0} which is expanded to a={1,1,0,0}. On the other side, the ID sequence of SUV that has Nz=3 sectors is β={0,1} which is expanded also to b={1,0,1,0}. The constructed matrix for SUV has Pv×Ev=5×4=20 rows and 2m=4 columns. Similarly, SUZ constructs its matrix with Pz×Ez=5×4=20 rows and 2m=4 columns. Each SU will assign its matrix columns with either PS sequence or ES sequence based on the corresponding bits of its extended ID sequence. For example, since the first bit of SUV extended ID is one, SUV firstly generates its first sector sets as SvP={3,4,1,2} and then invokes Algorithm 1 with SvP and Nv=4 to construct a round of a PS sequence ω=[3412r]. This round ω is repeated for Ev=4 times and assigned to the first column of SUV matrix. Similarly, since the second bit of SUV extended ID is one, the second column of SUV matrix is assigned with a repeated sequence of the PS sequence [4123r], which is constructed after rotating the sector set SvP by one. On the other hand, SUV assigns the third and fourth columns of its matrix with ES sequences because the corresponding 3rd and 4th bits of its extended ID sequence are zeros. Specifically, SUV invokes Algorithm 2 with SvE=Reverse(SvP) and Nv=4 to construct a round of an ES sequence γ=[2143]. This round γ of the ES sequence is then repeated for Pv=5 times and assigned to the third column of SUV matrix. Similarly, the fourth column of SUV matrix is filled with the ES sequence [1432] after repeating it for Pv=5 times. Note that SUZ will follow the same procedures as SUV to construct its matrix with taking into account the different expanded ID sequence bz={1,0,1,0} and Nz, as well as the initial sector sets SzP and SzE.Figure 5
The construction of the IPES matricesMV and MZ for SUV and SUZ, respectively. NV=4 and NZ=3; αV={1,0} and βZ={0,1}. So the expanded ID sequences are aV={1,1,0,0} and bZ={1,0,1,0}.Figure6 shows partial sector slots of the IPES-SH sequences for the two SUs (SUV and SUZ). As depicted from the figure, the IPES-SH sequence of each SU is generated by concatenating the rows of the SU constructed matrix in Figure 5 row by row. The sequences are generated as interleaved slots of PS (light blue) and ES (gray) slots according to the respective columns types in the matrices. The figure also illustrates the rendezvous sector occurrence between the SUs (indicated by the green circle) on the sector rendezvous pair (4,1).Figure 6
IPES-SH sector rendezvous betweenSUV and SUZ for the synchronous case.


## 4.2. Scheme Analysis

In this subsection, the theoretical performance of IPES-SH scheme is studied where the MSRL is derived.Theorem 3.
Under the IPES-SH scheme, the MSRL between a pair of SUs(SUi and SUj) is 2m×(max{(PiEj),(EiPj)}).Proof.
To prove that IPES-SH hasMSRL=2m(max{(PiEj),(EiPj)}), it is sufficient to prove that any arbitrary pair of IPES-SH sequences, for example, IPESi and IPESj, can achieve a successful sector rendezvous within 2m (max{(PiEj),(EiPj)}) sector slots.
LetIPESi and IPESj be the corresponding IPES-SH sequences of IPES matrices Mi and Mj (i.e., IPESi and IPESj are generated by concatenating the rows of matrices Mi and Mj, resp.). For example, Figures 5(a) and 5(b) show the IPES matrices MV and MZ, respectively. Without loss of generality, assume that SUj starts its SH sequence δ sector slots earlier than the start of SUi. In each SH period of SUi, the SH sequence of SUj is rotate(IPESj, δ). Clearly, the rendezvous between this pair of SUs is the same as the rendezvous of Mi and M(j,δ). Suppose that the sector rendezvous pair is (hi,hj)∈{1,2,…,Ni}×{1,2,…,Nj}. The rendezvous of the matrices is a pair of entries in the matrices whose value in Mi is hi and its values in M(j,δ) is hj. Without loss of generality, suppose that the sector slot shift δ=2m×δR+δC, where δR∈[0,(Pj×Ej)-1], is the shift of row and δC∈[0,(2m)-1] is the shift of column. Below, we consider the two different cases for rendezvous of IPESi and IPESj.Case  1 (δC=0). In this case, it is implied that there is no column shift. Recall that the expanded ID sequences of SUi and SUj are distinct. Since the columns types of the matrices are assigned based on these distinct expanded IDs, it is guaranteed that there must exist at least a single common column f in both matrices which is a PS-column in one matrix and an ES-column in the other matrix, and vice versa. In other words, the fth column of Mi contains a PS-SH sequence (reps., ES-SH), while the same position fth column in M(j,δ) contains an ES-SH (resp., PS-SH). By Theorem 1, we know that when SUi and SUj repeat the PS-SH (resp., ES-SH) and the ES-SH (resp., PS-SH) sequences, respectively, they rendezvous within Pi×Ej (resp., Ei×Pj). Meanwhile, since the elements of a specific column of each matrix appear in the corresponding IPES-SH sequence every 2m slots, for any value of the row shift δR, Mi and M(j,δ) are guaranteed to rendezvous on their fth columns no later than 2m×max{(PiEj),(EiPj)}. Specifically, the rendezvous happens when an entry of the fth column in Mi is hi, while the same position entry of the fth column in M(j,δ) is hj. For example, Figure 5 shows the rendezvous of MV and MZ for the synchronous case where the slots shift δ=2m×0+0=0. The sector rendezvous occurs between the second columns of MV and MZ which is indicated by the green entry in MZ. However, Figure 7(a) shows the IPES matrix of SUZ when it is shifted with row shift δR=10. Hence, this means that δ=2m×10+0=40. The rendezvous between MV in Figure 5 and M(Z,40) in Figure 7(a) is achieved at their third columns.Figure 7
The IPES matrixMZ for SUZ when it is circularly rotated with (a) δ=2m×10+0=40 sector slots and (b) δ=2m×2+1=41 slots.Case  2 (δC≠0). In this case, it holds that there is a column shift δC∈[1,(2m-1)]. Let a and b be the expanded ID sequences of SUi and SUj, respectively. By Lemma 2, we know that a and b′=rotate(b,k), where k∈(2m-1) arecyclic rotationally distinct to each other. Thus, for a column shift δC∈[1,(2m-1)] of matrix Mj, there must exist a column f in matrix Mi which has different type than the same position fth column in the shifted matrix M(j,δC). Accordingly, the rendezvous is guaranteed to occur at the fth columns in the matrices, despite any value of the row shift δR. For example, Figure 7(b) shows the shifted IPES matrix of SUZ when the column shift δC=1 and the row shift δR=10, which results in δ=2m×10+1=41 slots. The first rendezvous between MV in Figure 5 and M(Z,41) in Figure 7(b) is achieved at the forth columns.Summarizing the discussion above, we show that, in IPES-SH, any two SUs are guaranteed to rendezvous on their sector rendezvous pair within SH period2m×max{(PiEj),(EiPj)}.


## 5. Combined Sector and Channel Hopping Schemes

While we explained in the previous sections the procedures of our SH schemes by which the SUs keep steering their antennas in order to achieve sector rendezvous with their communicating partners, the scheme for channel hopping (CH) exposed by the SUs in their sectors for achieving a channel rendezvous between them was not explained. In this section, the design of the exposed CH scheme and the procedure for the combined sector and channel hopping (SCH) schemes are presented. The key for the design of the exposed CH scheme is to construct two different types of CH sequences which will be combined within the two different types of PES-SH sequences. These CH sequences must guarantee a successful channel rendezvous between the pair of SUs as long as they achieve a successful sector rendezvous (i.e., directing their antenna beams towards each other). Furthermore, the CH sequences should be designed in such a way that the pair of communicating SUs stay for a similar period (i.e., number of time slots) in each sector of their SH sequences. By doing this, the pair of communicating SUs are guaranteed to achieve successful sector and channel rendezvous within a bounded and short time, despite any asynchronous time offsets between their local clocks.


### 5.1. Asymmetric Grid Quorum-Based Channel Hopping

In this subsection, we explain the design of our Asymmetric Grid Quorum-based Channel Hopping (AGQ-CH) scheme that is executed by the SUs in each sector of their SH sequences. The AGQ-CH scheme utilizes the grid quorum system (GQS) in asymmetric-role design, where two types of CH sequences are constructed. These types of CH sequences will be combined within the two different types of our SH sequences. Some preliminary definitions related to grid quorum systems are presented first to facilitate the understanding of the CH scheme.Definition 4.
For a setZn={1,2,…,n}, a quorum system Q under Zn is a group of nonempty subsets of Zn, each called a quorum, such that ∀X and Y∈Q,X∩Y≠∅. Here, Zn is the set of integers less than or equal ton.Definition 5.
A GQS arranges the elements ofZn as a n×n square grid array, where n must be a square of a positive integer. Hence, a quorum is formed as a union of the elements of one column and one row of the grid. There are n grid quorums in a GQS that is constructed under Zn and each quorum has a size of (2×n-1).For example, a GQSQ under Zn={1,2,3,4} is Q={Q1,…,Q4}={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}.Definition 6.
For a given integeri and a grid quorum G in a GQS Q under Zn, we define rotate(G,i)={(x+i)modn,x∈G} to denote a cyclic rotation of quorum G by i.Definition 7.
A GQSQ under Zn satisfies the rotation closure property because, ∀Gi1,Gi2∈Q and ∀j1,j2∈Zn, rotateGi1,j1∩rotate(Gi2,j2)≠∅.GQSs have been utilized to construct CH sequences that achieve asynchronous communications because they satisfy the intersection and the rotation closure properties [33, 34]. In the conventional GQS, each grid quorum is formed as a union of the elements of one column and one row of the grid array. However, different from the conventional GQS, our asymmetric GQS (AGQS) uses semigrid quorums. One semiquorum, called the Grid Column-based Quorum (GCQ), is formed from the elements of a single column of the grid. Meanwhile, the other semiquorum, called Grid Row-based Quorum (GRQ), is formed from the elements of a single row in the grid. The nonempty intersection and rotation closure properties in the AGQS are inherited from the conventional GQS. Specifically, for any arbitrary pair of GCQ and GRQ, there must exist one common element between them despite any rotation of the grid.The GCQs and GRQs in the AGQS are used to construct two asymmetric CH sequences that can be combined within the different types of sectors in our SH schemes. The constructed CH sequences are guaranteed to achieve a successful channel rendezvous between a pair of communicating SUs as long as there exists at least a single common channel between the available channel sets of the SUs. In our AGQ-CH scheme, to construct CH sequences for assigningn channels, n×n grid array is built. In the GCQ-based CH sequence, the n rows of the grid are used for assigning the n channels into the CH sequence, where the elements of each row are used to map a single channel. On the other side, the n columns of the grid are used for the assignment of the n channels into the GRQ-based CH sequence. For example, Let n=4 be the number of channels for a sender SUx and a receiver SUy. Suppose that SUx has the channel set Cx={Ch1,Ch2,Ch3,Ch4}, while the channel set of SUy is Cy={Ch3,Ch5,Ch6,Ch8}. Accordingly, a grid array of size 4×4 is formed by both SUs as shown in Figure 8. Without loss of generality, assume that the sender uses the 4 GCQs to map its channels into the time slots of its CH sequence as depicted in Figure 8(a), while the receiver SUy maps its channels based on the 4 GRQs as depicted in Figure 8(b). The CH sequences for both SUs are shown in Figure 8(c), where they map each channel of their channel sets into the time slots of their CH sequence according to the selected (GCQ or GRQ) semiquorum. As shown in Figure 8(c), the channel rendezvous is achieved on the common channel Ch3 between the SUs despite the time offsets between their local clocks.Figure 8
An example of AGQ-CH sequences constructions and rendezvous for a pair of communicating SUs.
(a)
GCQs for mappingCx
(b)
GRQs for mappingCy
(c)
Channel rendezvous between SUs on the common channelCh3 when SUy start its CH with 0, 1, and 5 slots later than SUx


### 5.2. Channel Ranking

As explained in the beginning of the section, the sector frame length which represents the number of time slots by which every SU spends on each sector for executing CH should be the same in all SUs. This is in order to guarantee channel rendezvous between any pair of neighbouring SUs side by side with the sector rendezvous despite any time offsets between their local clocks. To achieve this, we let the SUs construct their combined CH sequences based on the best-quality(n⊆L) channels. The channel’s quality is generally represented by the quantity of the measured PU noise on the channel within the corresponding sector. However, for cases where some of the channels have the same measured PU noise, channels indices are used to differentiate between their ranking levels. Specifically, the bigger the channel index, the higher the quality. We highlight here that the similarity of the measured PU noises for some channels is a practical issue in DIR-CRNs which happen when the channels are idle from any PU activity within the sector area.The channel ranking is done by each SU before executing the rendezvous process based only on its own view of the available channels in its sectors. EachSUi ranks the L network channels in each sector Sk of its sectors set Si={S1,S2,…,SNi} based on their qualities within the sector k. Thus, a ranking table of size L×Ni is maintained by each SUi which contains the ranked channels in all the sectors. This table is called Sectors Ranked Channels Table (SRCT), where each column k of it indicates a sector of the Ni sectors. These columns contain the L network channels ranked decreasingly from the best to the worst according to their qualities within the corresponding sectors. We note here that since each SU in the DIR-CRN performs the same ranking mechanism, this will increase the probability of having a similar ranked channel list among any pair of neighbouring SUs on their rendezvous sectors.


### 5.3. Combined SCH Sequence Generation

We now explain the generation procedures for the combined PES-SCH and IPES-SCH sequences.


#### 5.3.1. Combined PES-SCH Scheme

Since our PES-SH scheme is designed based on two different types of coprimality-based sequences (i.e., either PS or ES), we combine each sector of the SH sequences according to its type with a corresponding type from the two AGQ-CH sequences. Specifically, each sector of the sender PS-SH sequence is combined with a GCQ-CH sequence, while each sector of the receiver ES-SH sequence is combined with a GRQ-CH sequence. Algorithms4 and 5 describe the SCH generation procedures for the sender and receiver SUs, respectively. As illustrated by the algorithms, each SU will keep hopping on its best n quality channels in each sector of its SH sequence according to the corresponding CH sequence. This will guarantee that when a successful sector rendezvous occurs between a sector frame of the sender SUs and a sector frame of its receiver SUr, a successful channel rendezvous is achieved between GCQ-CHs and the GRQ-CHr. The channel rendezvous is guaranteed as long as there is a common channel between their n best channels, where they can set up a link through the exchange of RTS/CTS messages.Algorithm 4:The sender SCH generation algorithm (PS-SCH).
Input: Ns,Ss,SRCTs,n.
(1) Invoke Algorithm 1 with Ns and Ss to construct a round
ω
s of an PS-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=ωs((tFrame mod PS)+1).
(5)  Steer the antenna to (Current-sector).
(6)  Select the best channel list (BCL) in (Current-sector)
as BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GCQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GCQs(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileAlgorithm 5:The receiver SCH generation algorithm (ES-SCH).
Input: Nr,Sr,SRCTr,n.
(1) Invoke Algorithm 2 with Nr and Sr to construct
a round γr of an ES-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=γr((tFrame mod Er)+1).
(5)  Steer the antenna to (Current-sector).
(6)  BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GRQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GRQr(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileFor example, consider the pair of senderSUX and receiver SUY in our previous example in Figure 1(a). The SCH sequences constructions for the pair of SUs and the rendezvous among them when they construct their combined CH sequences based on n=2 best-quality channels are illustrated in Figure 9. As a sender, SUX in Figure 9(a) combines each sector of its PS-SH sequence with a grid column (GCQ-CH) sequence based on the two best-ranked channels of the respected column for the sector in SRCTX. For instance, the sector S1 is combined with a GCQ-CH sequence generated based on the two best channels {2,4} of the 1st column of SRCTX; the GCQ-CH is [2424]. On the other hand, each ES sector of the ES-SH sequence for the receiver SUY in Figure 9(b) is combined with a grid row (GRQ-CH) sequence based on the best two channels of the SRCTY column which corresponds to the sector number. For instance, SUY combine the GRQ-CH sequence [6688] within its sector S1 which is constructed based on the best channels {6,8}. The sector and channel rendezvous between the SUs when they start their PES-SCH sequences synchronously is shown in Figure 9(c). The rendezvous is achieved during the 25th and 28th time slots on the sector rendezvous pair (S2 of SUX, S3 of SUY), as well as on the rendezvous channels {1,6}. However, when SUX starts its SCH 4 time slots later than SUY, the channel and sector rendezvous is achieved after 5 time slots only from the SCH start time of SUX.Figure 9
Rendezvous between SUsX and Y according to the combined PES-SCH scheme. NX=5 and NY=4. Number of best-quality channels per each sector n=2.
(a)
The combined PES-SCH sequence construction for the senderSUX
(b)
The combined PES-SCH sequence construction for the receiverSUY
(c)
Synchronous sector and channel rendezvous betweenSUX and SUY
(d)
Asynchronous sector and channel rendezvous between the SUs whenSUY starts its hopping earlier than SUX by 4 slots


#### 5.3.2. Combined IPES-SCH Scheme

For this symmetric role scheme, any SU can generate its SCH sequence according to Algorithm6. During each sector frame of its interleaved SH sequence that is constructed using the method in Section 4.1.2, the SU executes one type of the AGQ-CH sequences according to the type of the frame. Specifically, if the sector frame is a prime-based (P-frame), the SU generates a GCQ-CH based on the n best-quality channels in the sector. On the other hand, when the sector is an even-based (E-frame), the SU generates a GRQ-CH. This will ensure that whenever the sector rendezvous occurs between a P-frame of IPESi and an E-frame of IPESj, channel rendezvous is achieved between the GCQi CH sequence and the GRQj CH sequence, and vice versa.Algorithm 6:IPES-SCH generation algorithm.
Input: Ni,Si, Extended-ID a, SRCTi,n.
(1) Construct an IPES-SH sequence Ui as explained in
Section 4.1.2.
(2) period = (Pi×Ei× length(a)).
(3) tFrame=0
(4) while  (not rendezvous)  do
(5) Current-sector = Ui((tFrame mod period)+1).
(6)  Steer the antenna to (Current-sector).
(7)  BCL = SRCTi [1 : n][Current-sector].
(8) if  (Current-sector is a P-sector)  then
(9)  Construct a GCQ-CH sequence based on BCL.
(10) for (t=1:n2) do
(11)  Attempt rendezvous on channel GCQi(t).
(12) end for
(13) else
(14)  Construct a GRQ-CH sequence based on BCL.
(15) for (t=1:n2) do
(16)  Attempt rendezvous on channel GRQi(t).
(17) end for
(18) end if
(19) tFrame=tFrame+1.
(20) end while


### 5.4. Performance Analysis of the Combined SCH Schemes

In this subsection, we analyze the theoretical performance for the combined SCH schemes. Specifically, we prove the guaranteed rendezvous between any two SUs performing the combined SCH scheme by deriving the maximum time-to-rendezvous (MTTR).Theorem 8.
For any schemeS of our SH schemes which is combined with the AGQ-CH scheme for n best-quality channels, the MTTR of the combined SCH is (MSRL(S)×n2). MSRL (S) here denotes the maximum sector rendezvous latency for the S SH scheme.Proof.
To prove that the combined PES-SCH has MTTR =(PiEj)×n2, it suffices to prove that the pair of combined PES-SCH sequences, for example, SCHi and SCHj, can achieve successful sector and channel rendezvous within (PiEj)×n2 time slots.
Without loss of generality, assume thatSUj starts its SCH sequence δ time slots earlier than the start of SUi. In each SCH period of SUi, the SCH sequence of SUj is rotate(SCHj,δ). As we stated before, the SCH sequence can be viewed as a series of sector frames which are composed of n2 channel time slots. Let the clock drift δ=n2×δF+δS, where δF∈[0,Ej-1] denotes the shift amount of the sector frames and δS∈[0,(n2)-1] denotes the shift of the channel time slots. Next, we prove the theorem in the following two cases.
Case  1 (δS=0). This case implies that the sector frames are perfectly aligned. In this case, since the SUs stay for similar number of time slots in each sector which is (n2) for executing their corresponding AGQ-CH sequences, for any value of δF, there must exist an entire overlap between a PS-frame of SCHi and an ES-frame of SCHj where the sector rendezvous happened. By Theorem 1, we know that the sector rendezvous is guaranteed to occur between a PS sector frame hi and an ES sector frame hj within (PiEj) sector frames. As a consequence, the channel rendezvous is guaranteed to happen between the GCQi CH sequence of hi and the GRQj CH sequence of hj. Thus, the MTTR is (PiEj) multiplied by the sector frame length n2. Figures 9(c) and 9(d) show the sector and channel rendezvous between SUX and SUY when δS=0 for two different values of δF and for n=2. In Figure 9(c), when δF=0 and hence the clock drift δ=(n2×0+0)=0, SUX can achieve the sector rendezvous with SUY on the second round of its SH frames. The SUs rendezvous on their commonly available channels (i.e., CH1 and Ch6). However, when δF=1 and δ=(n2×1+0)=4, SUX can rendezvous with SUY earlier where it rendezvous with SUY during the first round of its SH frames.Case  2 (δS≠0). When there is a time slot shift δS∈[1,n2], it implies that the sector frames are not aligned. For any value of δF, it is easily verified that each PS sector frame of SCHi is overlapped with partial channel time slots form two consecutive ES frames of SCHj. Specifically, the PS frame of SCHi overlaps with n2-δS time slots from the former ES frame and δS time slots from the later ES frame of SCHj. Recall the proof of Theorem 1, when SUi repeats each round of its sector frames for Er times, each occurrence of the hi sector frame must overlap with different sector frame from the Er sector frames of SUj. The sector rendezvous is achieved when hi overlaps with hj. However, considering the time slot shift δS of the SCHj sequence, we can prove in the same way as case 1 that, within the same rendezvous delay bound ((PiEj)×n2 time slots), there must exist at least two occurrences of hi which overlaps with different partial time slots of hj. In one of these occurrences, the overlap happens between the first n2-δS time slots of hi and the last n2-δS time slots of hj. On the other occurrence, the overlap happens between the last δS time slots of hi and the first δS time slots of hj. Accordingly, channel rendezvous can be achieved in any of these two partial sector rendezvous chances where partial slots of the GCQi CH sequence in hi overlap with other partial slots from the GRQj CH sequence in hj. For example, Figure 10 illustrates the asynchronous rendezvous between SUX and SUY when δF=0 for three different values of δS.Figure 10
Asynchronous rendezvous betweenSUX and SUY according to the combined PES-SCH scheme for n=2 best-ranked channels. SCHY is started earlier than SCHX with δS∈[1,3].Summarizing the discussion above, we show that, under the combined PES-SCH, any two SUs are guaranteed to achieve channel rendezvous within ((PiEj)×n2) SCH period. We highlight here that the theoretical MTTR for the combined IPES-SCH is (2m×max{(PiEj),(EiPj)})×n2. It can be proven in a similar way to the proof of the PES-SCH MTTR by considering the two alignment cases of the sector frames.


## 5.1. Asymmetric Grid Quorum-Based Channel Hopping

In this subsection, we explain the design of our Asymmetric Grid Quorum-based Channel Hopping (AGQ-CH) scheme that is executed by the SUs in each sector of their SH sequences. The AGQ-CH scheme utilizes the grid quorum system (GQS) in asymmetric-role design, where two types of CH sequences are constructed. These types of CH sequences will be combined within the two different types of our SH sequences. Some preliminary definitions related to grid quorum systems are presented first to facilitate the understanding of the CH scheme.Definition 4.
For a setZn={1,2,…,n}, a quorum system Q under Zn is a group of nonempty subsets of Zn, each called a quorum, such that ∀X and Y∈Q,X∩Y≠∅. Here, Zn is the set of integers less than or equal ton.Definition 5.
A GQS arranges the elements ofZn as a n×n square grid array, where n must be a square of a positive integer. Hence, a quorum is formed as a union of the elements of one column and one row of the grid. There are n grid quorums in a GQS that is constructed under Zn and each quorum has a size of (2×n-1).For example, a GQSQ under Zn={1,2,3,4} is Q={Q1,…,Q4}={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}.Definition 6.
For a given integeri and a grid quorum G in a GQS Q under Zn, we define rotate(G,i)={(x+i)modn,x∈G} to denote a cyclic rotation of quorum G by i.Definition 7.
A GQSQ under Zn satisfies the rotation closure property because, ∀Gi1,Gi2∈Q and ∀j1,j2∈Zn, rotateGi1,j1∩rotate(Gi2,j2)≠∅.GQSs have been utilized to construct CH sequences that achieve asynchronous communications because they satisfy the intersection and the rotation closure properties [33, 34]. In the conventional GQS, each grid quorum is formed as a union of the elements of one column and one row of the grid array. However, different from the conventional GQS, our asymmetric GQS (AGQS) uses semigrid quorums. One semiquorum, called the Grid Column-based Quorum (GCQ), is formed from the elements of a single column of the grid. Meanwhile, the other semiquorum, called Grid Row-based Quorum (GRQ), is formed from the elements of a single row in the grid. The nonempty intersection and rotation closure properties in the AGQS are inherited from the conventional GQS. Specifically, for any arbitrary pair of GCQ and GRQ, there must exist one common element between them despite any rotation of the grid.The GCQs and GRQs in the AGQS are used to construct two asymmetric CH sequences that can be combined within the different types of sectors in our SH schemes. The constructed CH sequences are guaranteed to achieve a successful channel rendezvous between a pair of communicating SUs as long as there exists at least a single common channel between the available channel sets of the SUs. In our AGQ-CH scheme, to construct CH sequences for assigningn channels, n×n grid array is built. In the GCQ-based CH sequence, the n rows of the grid are used for assigning the n channels into the CH sequence, where the elements of each row are used to map a single channel. On the other side, the n columns of the grid are used for the assignment of the n channels into the GRQ-based CH sequence. For example, Let n=4 be the number of channels for a sender SUx and a receiver SUy. Suppose that SUx has the channel set Cx={Ch1,Ch2,Ch3,Ch4}, while the channel set of SUy is Cy={Ch3,Ch5,Ch6,Ch8}. Accordingly, a grid array of size 4×4 is formed by both SUs as shown in Figure 8. Without loss of generality, assume that the sender uses the 4 GCQs to map its channels into the time slots of its CH sequence as depicted in Figure 8(a), while the receiver SUy maps its channels based on the 4 GRQs as depicted in Figure 8(b). The CH sequences for both SUs are shown in Figure 8(c), where they map each channel of their channel sets into the time slots of their CH sequence according to the selected (GCQ or GRQ) semiquorum. As shown in Figure 8(c), the channel rendezvous is achieved on the common channel Ch3 between the SUs despite the time offsets between their local clocks.Figure 8
An example of AGQ-CH sequences constructions and rendezvous for a pair of communicating SUs.
(a)
GCQs for mappingCx
(b)
GRQs for mappingCy
(c)
Channel rendezvous between SUs on the common channelCh3 when SUy start its CH with 0, 1, and 5 slots later than SUx


## 5.2. Channel Ranking

As explained in the beginning of the section, the sector frame length which represents the number of time slots by which every SU spends on each sector for executing CH should be the same in all SUs. This is in order to guarantee channel rendezvous between any pair of neighbouring SUs side by side with the sector rendezvous despite any time offsets between their local clocks. To achieve this, we let the SUs construct their combined CH sequences based on the best-quality(n⊆L) channels. The channel’s quality is generally represented by the quantity of the measured PU noise on the channel within the corresponding sector. However, for cases where some of the channels have the same measured PU noise, channels indices are used to differentiate between their ranking levels. Specifically, the bigger the channel index, the higher the quality. We highlight here that the similarity of the measured PU noises for some channels is a practical issue in DIR-CRNs which happen when the channels are idle from any PU activity within the sector area.The channel ranking is done by each SU before executing the rendezvous process based only on its own view of the available channels in its sectors. EachSUi ranks the L network channels in each sector Sk of its sectors set Si={S1,S2,…,SNi} based on their qualities within the sector k. Thus, a ranking table of size L×Ni is maintained by each SUi which contains the ranked channels in all the sectors. This table is called Sectors Ranked Channels Table (SRCT), where each column k of it indicates a sector of the Ni sectors. These columns contain the L network channels ranked decreasingly from the best to the worst according to their qualities within the corresponding sectors. We note here that since each SU in the DIR-CRN performs the same ranking mechanism, this will increase the probability of having a similar ranked channel list among any pair of neighbouring SUs on their rendezvous sectors.


## 5.3. Combined SCH Sequence Generation

We now explain the generation procedures for the combined PES-SCH and IPES-SCH sequences.


### 5.3.1. Combined PES-SCH Scheme

Since our PES-SH scheme is designed based on two different types of coprimality-based sequences (i.e., either PS or ES), we combine each sector of the SH sequences according to its type with a corresponding type from the two AGQ-CH sequences. Specifically, each sector of the sender PS-SH sequence is combined with a GCQ-CH sequence, while each sector of the receiver ES-SH sequence is combined with a GRQ-CH sequence. Algorithms4 and 5 describe the SCH generation procedures for the sender and receiver SUs, respectively. As illustrated by the algorithms, each SU will keep hopping on its best n quality channels in each sector of its SH sequence according to the corresponding CH sequence. This will guarantee that when a successful sector rendezvous occurs between a sector frame of the sender SUs and a sector frame of its receiver SUr, a successful channel rendezvous is achieved between GCQ-CHs and the GRQ-CHr. The channel rendezvous is guaranteed as long as there is a common channel between their n best channels, where they can set up a link through the exchange of RTS/CTS messages.Algorithm 4:The sender SCH generation algorithm (PS-SCH).
Input: Ns,Ss,SRCTs,n.
(1) Invoke Algorithm 1 with Ns and Ss to construct a round
ω
s of an PS-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=ωs((tFrame mod PS)+1).
(5)  Steer the antenna to (Current-sector).
(6)  Select the best channel list (BCL) in (Current-sector)
as BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GCQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GCQs(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileAlgorithm 5:The receiver SCH generation algorithm (ES-SCH).
Input: Nr,Sr,SRCTr,n.
(1) Invoke Algorithm 2 with Nr and Sr to construct
a round γr of an ES-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=γr((tFrame mod Er)+1).
(5)  Steer the antenna to (Current-sector).
(6)  BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GRQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GRQr(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileFor example, consider the pair of senderSUX and receiver SUY in our previous example in Figure 1(a). The SCH sequences constructions for the pair of SUs and the rendezvous among them when they construct their combined CH sequences based on n=2 best-quality channels are illustrated in Figure 9. As a sender, SUX in Figure 9(a) combines each sector of its PS-SH sequence with a grid column (GCQ-CH) sequence based on the two best-ranked channels of the respected column for the sector in SRCTX. For instance, the sector S1 is combined with a GCQ-CH sequence generated based on the two best channels {2,4} of the 1st column of SRCTX; the GCQ-CH is [2424]. On the other hand, each ES sector of the ES-SH sequence for the receiver SUY in Figure 9(b) is combined with a grid row (GRQ-CH) sequence based on the best two channels of the SRCTY column which corresponds to the sector number. For instance, SUY combine the GRQ-CH sequence [6688] within its sector S1 which is constructed based on the best channels {6,8}. The sector and channel rendezvous between the SUs when they start their PES-SCH sequences synchronously is shown in Figure 9(c). The rendezvous is achieved during the 25th and 28th time slots on the sector rendezvous pair (S2 of SUX, S3 of SUY), as well as on the rendezvous channels {1,6}. However, when SUX starts its SCH 4 time slots later than SUY, the channel and sector rendezvous is achieved after 5 time slots only from the SCH start time of SUX.Figure 9
Rendezvous between SUsX and Y according to the combined PES-SCH scheme. NX=5 and NY=4. Number of best-quality channels per each sector n=2.
(a)
The combined PES-SCH sequence construction for the senderSUX
(b)
The combined PES-SCH sequence construction for the receiverSUY
(c)
Synchronous sector and channel rendezvous betweenSUX and SUY
(d)
Asynchronous sector and channel rendezvous between the SUs whenSUY starts its hopping earlier than SUX by 4 slots


### 5.3.2. Combined IPES-SCH Scheme

For this symmetric role scheme, any SU can generate its SCH sequence according to Algorithm6. During each sector frame of its interleaved SH sequence that is constructed using the method in Section 4.1.2, the SU executes one type of the AGQ-CH sequences according to the type of the frame. Specifically, if the sector frame is a prime-based (P-frame), the SU generates a GCQ-CH based on the n best-quality channels in the sector. On the other hand, when the sector is an even-based (E-frame), the SU generates a GRQ-CH. This will ensure that whenever the sector rendezvous occurs between a P-frame of IPESi and an E-frame of IPESj, channel rendezvous is achieved between the GCQi CH sequence and the GRQj CH sequence, and vice versa.Algorithm 6:IPES-SCH generation algorithm.
Input: Ni,Si, Extended-ID a, SRCTi,n.
(1) Construct an IPES-SH sequence Ui as explained in
Section 4.1.2.
(2) period = (Pi×Ei× length(a)).
(3) tFrame=0
(4) while  (not rendezvous)  do
(5) Current-sector = Ui((tFrame mod period)+1).
(6)  Steer the antenna to (Current-sector).
(7)  BCL = SRCTi [1 : n][Current-sector].
(8) if  (Current-sector is a P-sector)  then
(9)  Construct a GCQ-CH sequence based on BCL.
(10) for (t=1:n2) do
(11)  Attempt rendezvous on channel GCQi(t).
(12) end for
(13) else
(14)  Construct a GRQ-CH sequence based on BCL.
(15) for (t=1:n2) do
(16)  Attempt rendezvous on channel GRQi(t).
(17) end for
(18) end if
(19) tFrame=tFrame+1.
(20) end while


## 5.3.1. Combined PES-SCH Scheme

Since our PES-SH scheme is designed based on two different types of coprimality-based sequences (i.e., either PS or ES), we combine each sector of the SH sequences according to its type with a corresponding type from the two AGQ-CH sequences. Specifically, each sector of the sender PS-SH sequence is combined with a GCQ-CH sequence, while each sector of the receiver ES-SH sequence is combined with a GRQ-CH sequence. Algorithms4 and 5 describe the SCH generation procedures for the sender and receiver SUs, respectively. As illustrated by the algorithms, each SU will keep hopping on its best n quality channels in each sector of its SH sequence according to the corresponding CH sequence. This will guarantee that when a successful sector rendezvous occurs between a sector frame of the sender SUs and a sector frame of its receiver SUr, a successful channel rendezvous is achieved between GCQ-CHs and the GRQ-CHr. The channel rendezvous is guaranteed as long as there is a common channel between their n best channels, where they can set up a link through the exchange of RTS/CTS messages.Algorithm 4:The sender SCH generation algorithm (PS-SCH).
Input: Ns,Ss,SRCTs,n.
(1) Invoke Algorithm 1 with Ns and Ss to construct a round
ω
s of an PS-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=ωs((tFrame mod PS)+1).
(5)  Steer the antenna to (Current-sector).
(6)  Select the best channel list (BCL) in (Current-sector)
as BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GCQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GCQs(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileAlgorithm 5:The receiver SCH generation algorithm (ES-SCH).
Input: Nr,Sr,SRCTr,n.
(1) Invoke Algorithm 2 with Nr and Sr to construct
a round γr of an ES-SH sequence.
(2) tFrame=0
(3) while  (not rendezvous)  do
(4) Current-sector=γr((tFrame mod Er)+1).
(5)  Steer the antenna to (Current-sector).
(6)  BCL = SRCTs [1 : n][Current-sector].
(7)  Construct a GRQ-CH sequence based on BCL.
(8) for (t=1:n2) do
(9)  Attempt rendezvous on channel GRQr(t).
(10) end for
(11) tFrame=tFrame+1.
(12) end whileFor example, consider the pair of senderSUX and receiver SUY in our previous example in Figure 1(a). The SCH sequences constructions for the pair of SUs and the rendezvous among them when they construct their combined CH sequences based on n=2 best-quality channels are illustrated in Figure 9. As a sender, SUX in Figure 9(a) combines each sector of its PS-SH sequence with a grid column (GCQ-CH) sequence based on the two best-ranked channels of the respected column for the sector in SRCTX. For instance, the sector S1 is combined with a GCQ-CH sequence generated based on the two best channels {2,4} of the 1st column of SRCTX; the GCQ-CH is [2424]. On the other hand, each ES sector of the ES-SH sequence for the receiver SUY in Figure 9(b) is combined with a grid row (GRQ-CH) sequence based on the best two channels of the SRCTY column which corresponds to the sector number. For instance, SUY combine the GRQ-CH sequence [6688] within its sector S1 which is constructed based on the best channels {6,8}. The sector and channel rendezvous between the SUs when they start their PES-SCH sequences synchronously is shown in Figure 9(c). The rendezvous is achieved during the 25th and 28th time slots on the sector rendezvous pair (S2 of SUX, S3 of SUY), as well as on the rendezvous channels {1,6}. However, when SUX starts its SCH 4 time slots later than SUY, the channel and sector rendezvous is achieved after 5 time slots only from the SCH start time of SUX.Figure 9
Rendezvous between SUsX and Y according to the combined PES-SCH scheme. NX=5 and NY=4. Number of best-quality channels per each sector n=2.
(a)
The combined PES-SCH sequence construction for the senderSUX
(b)
The combined PES-SCH sequence construction for the receiverSUY
(c)
Synchronous sector and channel rendezvous betweenSUX and SUY
(d)
Asynchronous sector and channel rendezvous between the SUs whenSUY starts its hopping earlier than SUX by 4 slots


## 5.3.2. Combined IPES-SCH Scheme

For this symmetric role scheme, any SU can generate its SCH sequence according to Algorithm6. During each sector frame of its interleaved SH sequence that is constructed using the method in Section 4.1.2, the SU executes one type of the AGQ-CH sequences according to the type of the frame. Specifically, if the sector frame is a prime-based (P-frame), the SU generates a GCQ-CH based on the n best-quality channels in the sector. On the other hand, when the sector is an even-based (E-frame), the SU generates a GRQ-CH. This will ensure that whenever the sector rendezvous occurs between a P-frame of IPESi and an E-frame of IPESj, channel rendezvous is achieved between the GCQi CH sequence and the GRQj CH sequence, and vice versa.Algorithm 6:IPES-SCH generation algorithm.
Input: Ni,Si, Extended-ID a, SRCTi,n.
(1) Construct an IPES-SH sequence Ui as explained in
Section 4.1.2.
(2) period = (Pi×Ei× length(a)).
(3) tFrame=0
(4) while  (not rendezvous)  do
(5) Current-sector = Ui((tFrame mod period)+1).
(6)  Steer the antenna to (Current-sector).
(7)  BCL = SRCTi [1 : n][Current-sector].
(8) if  (Current-sector is a P-sector)  then
(9)  Construct a GCQ-CH sequence based on BCL.
(10) for (t=1:n2) do
(11)  Attempt rendezvous on channel GCQi(t).
(12) end for
(13) else
(14)  Construct a GRQ-CH sequence based on BCL.
(15) for (t=1:n2) do
(16)  Attempt rendezvous on channel GRQi(t).
(17) end for
(18) end if
(19) tFrame=tFrame+1.
(20) end while


## 5.4. Performance Analysis of the Combined SCH Schemes

In this subsection, we analyze the theoretical performance for the combined SCH schemes. Specifically, we prove the guaranteed rendezvous between any two SUs performing the combined SCH scheme by deriving the maximum time-to-rendezvous (MTTR).Theorem 8.
For any schemeS of our SH schemes which is combined with the AGQ-CH scheme for n best-quality channels, the MTTR of the combined SCH is (MSRL(S)×n2). MSRL (S) here denotes the maximum sector rendezvous latency for the S SH scheme.Proof.
To prove that the combined PES-SCH has MTTR =(PiEj)×n2, it suffices to prove that the pair of combined PES-SCH sequences, for example, SCHi and SCHj, can achieve successful sector and channel rendezvous within (PiEj)×n2 time slots.
Without loss of generality, assume thatSUj starts its SCH sequence δ time slots earlier than the start of SUi. In each SCH period of SUi, the SCH sequence of SUj is rotate(SCHj,δ). As we stated before, the SCH sequence can be viewed as a series of sector frames which are composed of n2 channel time slots. Let the clock drift δ=n2×δF+δS, where δF∈[0,Ej-1] denotes the shift amount of the sector frames and δS∈[0,(n2)-1] denotes the shift of the channel time slots. Next, we prove the theorem in the following two cases.
Case  1 (δS=0). This case implies that the sector frames are perfectly aligned. In this case, since the SUs stay for similar number of time slots in each sector which is (n2) for executing their corresponding AGQ-CH sequences, for any value of δF, there must exist an entire overlap between a PS-frame of SCHi and an ES-frame of SCHj where the sector rendezvous happened. By Theorem 1, we know that the sector rendezvous is guaranteed to occur between a PS sector frame hi and an ES sector frame hj within (PiEj) sector frames. As a consequence, the channel rendezvous is guaranteed to happen between the GCQi CH sequence of hi and the GRQj CH sequence of hj. Thus, the MTTR is (PiEj) multiplied by the sector frame length n2. Figures 9(c) and 9(d) show the sector and channel rendezvous between SUX and SUY when δS=0 for two different values of δF and for n=2. In Figure 9(c), when δF=0 and hence the clock drift δ=(n2×0+0)=0, SUX can achieve the sector rendezvous with SUY on the second round of its SH frames. The SUs rendezvous on their commonly available channels (i.e., CH1 and Ch6). However, when δF=1 and δ=(n2×1+0)=4, SUX can rendezvous with SUY earlier where it rendezvous with SUY during the first round of its SH frames.Case  2 (δS≠0). When there is a time slot shift δS∈[1,n2], it implies that the sector frames are not aligned. For any value of δF, it is easily verified that each PS sector frame of SCHi is overlapped with partial channel time slots form two consecutive ES frames of SCHj. Specifically, the PS frame of SCHi overlaps with n2-δS time slots from the former ES frame and δS time slots from the later ES frame of SCHj. Recall the proof of Theorem 1, when SUi repeats each round of its sector frames for Er times, each occurrence of the hi sector frame must overlap with different sector frame from the Er sector frames of SUj. The sector rendezvous is achieved when hi overlaps with hj. However, considering the time slot shift δS of the SCHj sequence, we can prove in the same way as case 1 that, within the same rendezvous delay bound ((PiEj)×n2 time slots), there must exist at least two occurrences of hi which overlaps with different partial time slots of hj. In one of these occurrences, the overlap happens between the first n2-δS time slots of hi and the last n2-δS time slots of hj. On the other occurrence, the overlap happens between the last δS time slots of hi and the first δS time slots of hj. Accordingly, channel rendezvous can be achieved in any of these two partial sector rendezvous chances where partial slots of the GCQi CH sequence in hi overlap with other partial slots from the GRQj CH sequence in hj. For example, Figure 10 illustrates the asynchronous rendezvous between SUX and SUY when δF=0 for three different values of δS.Figure 10
Asynchronous rendezvous betweenSUX and SUY according to the combined PES-SCH scheme for n=2 best-ranked channels. SCHY is started earlier than SCHX with δS∈[1,3].Summarizing the discussion above, we show that, under the combined PES-SCH, any two SUs are guaranteed to achieve channel rendezvous within ((PiEj)×n2) SCH period. We highlight here that the theoretical MTTR for the combined IPES-SCH is (2m×max{(PiEj),(EiPj)})×n2. It can be proven in a similar way to the proof of the PES-SCH MTTR by considering the two alignment cases of the sector frames.


## 6. Results and Discussions

In this section, we evaluate the performance of our developed directional antenna rendezvous schemes and compare them with three related works in [19, 28, 30]. The former two selected schemes for comparisons are the only schemes in the literature which tackle the rendezvous issue in DIR-CRNs. However, since both of them are asymmetric-role, we select the third scheme [30] which is proposed for rendezvous in the 60 GHz networks for the comparison with our symmetric-role IPES scheme. This scheme follows a similar ID-based approach to our IPES-SH scheme. However, the extended ID in this scheme is relatively longer and the adjusted parameters of the number of sectors which are used for constructing the interleaved SH sequences are different.


### 6.1. Performance Comparison of the SH Schemes

We first compare the performance of our SH schemes with the two blind SH schemes in [28, 30]. The SH scheme in [19] is not compared here because it is not a blind scheme. Extensive simulation experiments are conducted to compute the sector rendezvous latency (SRL) between two neighboring SUs (a sender SUi and a receiver SUj). In the simulations, we consider different antenna configurations for the SUs where we simulate several combinations for the number of sectors (Ni and Nj). The relative locations of SUi and SUj represented by (hi, hj) as well as the clock drift are randomly generated. For the ID-based schemes, two different 7-bit IDs are randomly assigned to the SUs. For each (Ni and Nj) combination, the simulation results are obtained by conducting 105 independent runs where we accordingly compute the average and maximum SRL (ASRL and MSRL).Figure11 depicts the SRL results for the asymmetric-role SH schemes (our PES-SH and Li and Xie’s SH [28]). The results illustrate the significant reduction on the SRL provided by our PES-SH in terms of ASRL and MSRL under all the different antenna configurations of the pair of SUs. For some antenna configurations, PES-SH can reduce the ASRL and MSRL significantly up to 80% and 84%, respectively. The shorter ASRL and MSRL provided by the PES-SH scheme are due to its efficient design which relies on the coprimality between the adjusted prime and even numbers of Ni and Nj, respectively. And since Ni is prime for all the sender SUi antenna configurations while the values of Nj are even numbers that are valid for use (i.e., not in the AES set), this allows the sender SUi in our PES-SH to achieve sector rendezvous with its receiver SUj within NiNj SH period.Figure 11
Comparison of the sector rendezvous latency between our PES-SH scheme and Li and Xie’s SH scheme [28] under fixed Ni and varying Nj.
(a)
N
i
=
5
(b)
N
i
=
11
(c)
N
i
=
17On the other side, the design of Li and Xie’s SH scheme requiresNi and Nj to be adjusted to primes. Furthermore, the sender should perform an initiating round-robin SH sequence with a length of Ni2 before it converts to the regular prime-based sequence. Accordingly, this will prolong the SH period needed for achieving the sector rendezvous to (Ni2+NiPj) which actually represents the theoretical upper bound for the MSRL of Li and Xie’s SH scheme when (Ni≠Pj). We can notice that this upper bound is tight for some (Ni and Nj) combinations, while it is not for others. Specifically, when (Ni%  Pj=1) where Pj is the adjusted prime for Nj, the sender SUi cannot rendezvous with its receiver during its initiating Ni2 round-robin SH sequence. However, when it starts following the regular prime-based SH sequence, the sector rendezvous happens within the subsequent NiPj slots, which results in (Ni2+NiPj) MSRL. For example, when Ni=11 and Nj=4 in Figure 11(b), the sector rendezvous occurs in (121+11×5)=165 sector slots. The same thing can be noticed for the cases when Nj=2 in Figures 11(a), 11(b), and 11(c), where the MSRL is (Ni2+Ni×2). This explains the irregular increased results in the figures for such (Ni and Nj) combinations.In Figure12, the SRL results for the symmetric-role SH schemes (our IPES-SH and the Chen et al.’s SH scheme [30]) are shown. In the figure, it is shown that our IPES-SH scheme outperforms the other compared scheme especially in terms of MSRL. This improvement is due to the shorter SH period provided by IPES for achieving the sector rendezvous. In both schemes, the SH period for sector rendezvous depends mainly on the extended ID length as well as the adjusted numbers for (Ni and Nj) that are used for constructing the interleaved sequences. However, the adjusted parameters used by our IPES scheme are smaller than those used by the other scheme. Firstly, in the IPES-SH scheme, the extended ID length is 2m=14 which is relatively smaller than the 2m+1=15 extended ID used by the other scheme. Furthermore, the interleaved SH sequences in Chen et al.’s SH scheme are constructed by adjusting the number of sectors to a prime number as well as to a number that is a power-multiple of two (i.e., qk=2bk, where bk is the smallest integer satisfying 2bk≥Nk). However, these adjusted numbers must be coprime with the extended ID length in order to achieve a successful sector rendezvous. Meanwhile, in IPES-SH, the interleaved PS and ES sequences are constructed based on the closest prime number and the closest even number which is not in the AES set. Hence, under most of the simulated antenna configurations, the adjusted Ei and Ej in IPES are smaller than the adjusted qi and qj parameters in the other scheme. For example, in our IPES-SH scheme, Ej=Nj for all the Nj values, while the qj adjusted parameters for the Nj values in Chen et al.’s SH scheme are {2,4,8,8,16,32}. Moreover, when Ni or Nj is ≤5, the adjusted prime number used in IPES is 5, while it is 7 on the other scheme because 7 is the closest prime that is coprime with the 15-bit extended ID. According to that, SUs in the IPES scheme can achieve the sector rendezvous faster than Chen et al.’s SH scheme.Figure 12
Comparison of the sector rendezvous latency between our IPES-SH scheme and Chen et al.’s SH scheme [30] under fixed Ni and varying Nj. ID length = 7 bits.
(a)
N
i
=
5
(b)
N
i
=
11
(c)
N
i
=
17


### 6.2. Performance Comparison of the Combined SCH Schemes

In this subsection, we compare the channel rendezvous performance of our SCH schemes with the other works under a practical DIR-CRN. The simulation configuration parameters are shown in Table1.Table 1
Simulation parameters.
Network area deployment
500m×500m
Number of channels (L)
10
Number of PUs
50
The radius of the SU sensing/transmission range
150 m
Slot duration for sending a packet on a channel
2 ms
The PU packet arrival rate
10 packets/s
The length of a PU packet
120 slotsWe start our SCH simulation by comparing the performance of our combined PES-SCH with the combined SCH schemes of Song and Xie [19] and Li and Xie [28]. We evaluate our PES-SCH for n=4 best-quality channels which correspond to a AGQ-CH period of 16 time slots in each sector (i.e., the frame length = 16). The other selected schemes for comparison are simulated with their proposed CH schemes. In [19], the SH scheme is combined with the asymmetric-role CH scheme in [35], where the sender SU stays for L2 slots on each sector frame of its SH sequence performing a sequential fast CH on the (Ci⊆L) available channels within the sector. Meanwhile, the receiver SU stays for (Ni+1)×L2 slots on each sector of its Ni sectors performing a slow CH on all of its (Cj⊆L) available channels. On the other side, the SH scheme of Li and Xie [28] is combined with the EJS-CH scheme [10]. However, due to the long period of the EJS-CH scheme required to guarantee channel rendezvous, Li and Xie simulated their SCH scheme by letting SUs stay for smaller period on each sector of their SH frames. During this period, SUs execute the corresponding subsequences of their generated EJS-CH sequence. Therefore, we simulate Li and Xie’s SCH scheme with a similar sector frame length to our PES-SCH scheme (i.e., 16 slots). All the schemes are simulated under different asynchronous settings where the clock drifts amount between SUs is selected randomly in each experiment.Figure13 depicts the TTR simulation results for the three schemes when they are evaluated under different antenna configurations for the pair of SUs. Even though the combined SCH scheme of Song and Xie is not a blind scheme, it produces very long TTR results. This is due to the large sector frame length where the sender and receiver stay for L2 and L2×(Ni+1) time slots, respectively, on each sector for performing their corresponding CH sequence. As a consequence, the SCH period needed for achieving rendezvous is Nj×(L2×(Ni+1)) which is very long as compared to the period of our PES-SCH scheme. On the other side, Li and Xie’s SCH scheme can provide shorter ATTR than Song and Xie’s scheme because it is simulated with smaller frame length. However, the MTTR of this scheme cannot be traced because we observe that TTR in some cases cannot be achieved within the whole simulation duration which is set to 5×104 slots. The reason for the indeterministic behaviour of Li and Xie’s SCH scheme is because the stay period in each sector (i.e., 16 slots) is insufficient to guarantee rendezvous while using the EJS-CH scheme. According to the EJS-CH [10], the rendezvous cannot be guaranteed unless the EJS-CH sequences of the communicating SUs are overlapped for at least 4PL(PL+1-G)=44(12-G) time slots. PL is the smallest prime number greater than L, while G is the number of common available channels between the SUs available channels. Hence, to ensure rendezvous regardless of any misalignment of their local clocks, the SUs should stay for at least 4PL2 on each sector of their SH sequences to perform their EJS-CH sequences. This trade-off between the bounded MTTR of Song and Xie’s SCH scheme and the small ATTR of Li and Xie’s SCH scheme illustrates the efficiency of our proposed AGQ-CH scheme, which allows PES-SCH to guarantee rendezvous with the shortest TTR results.Figure 13
Comparison of the time-to-rendezvous (TTR) between the asymmetric-role SCH schemes whenNi=5.In the second setting of the SCH simulation, we combine the SH schemes of Li and Xie [28] and Chen et al. [30] with our proposed AGQ-CH scheme. This is in order to evaluate their channel rendezvous performance when they are combined with an efficient and suitable CH scheme. Figures 14 and 15 show the TTR results of these schemes and our schemes when they are simulated for different values of the best-quality channel n(2⩽n⩽5). In the simulation, we consider different values for the sender number of sectors (Ni={4,6,12}), while the receiver number of sectors Nj is set as 4. The figures show that our schemes always outperform the other schemes under all the different antenna configurations of the SUs. This is mainly due to the shorter SRL of our SH schemes and, as explained in Section 5.4, TTR depends on the SRL of the SH scheme coupled with the length of the sector frame (n2). Moreover, the figures illustrate the effect of n (i.e., the number of best-quality channels) on the rendezvous performance where we can notice that as n increases, the TTR results for all the schemes increase. This is because the larger n, the longer the frame length n2. Accordingly, when SUs spend longer period in each sector, they may waste more time while attempting rendezvous on other sectors rather than the rendezvous sector. This will result in a longer TTR until they can achieve a successful sector and channel rendezvous.Figure 14
Comparison of the time-to-rendezvous (TTR) between the asymmetric-role SCH schemes whenNj=4.Figure 15
Comparison of the TTR between the symmetric-role SCH schemes whenNj=4. ID length = 7 bits.Finally, to illustrate the performance gain brought by applying directional antennas for channel rendezvous, we compare the performance of our combined PES-SCH scheme with the AAsync-CH omnidirectional antenna rendezvous scheme [16]. The AAsync-CH is selected among the other omnidirectional CH schemes since it is designed for asymmetric-role environment (i.e., SUs have preassigned role) similar to our PES-SCH. The schemes are compared in terms of their probabilities for achieving a successful channel rendezvous under different number of PUs in the network area. In our PES-SCH, the simulated sender and receiver SUs have Ni=5 and Nj=6 number of sectors and the number of best-quality channels n=3.Figure16 shows the significant outperformance of our directional antenna scheme as compared with the omnidirectional antenna scheme. It can be noticed from the figure that when the number of PUs in the network increases, the probability of the successful channel rendezvous for the omnidirectional scheme decreases dramatically. Meanwhile, in the PES-SCH, this probability is almost 1 for most of the cases and only decreases slightly when the number of PUs is close to 100. This is due to the smaller interference region of the directional antenna, which results in higher channel availability for the SUs as compared to the omnidirectional antenna. So, when the total number of PUs in the network area increases, only few of them may reside within the SUs rendezvous sectors where they can only impose a slight change in the channel availability. Accordingly, the probability of having common channels between the SUs on their sector rendezvous pair is always high, which increases the probability of successful channel rendezvous.Figure 16
Comparison of the successful channel rendezvous probability between our PES-SCH directional antenna scheme and the AAsync-CH omnidirectional scheme.These results justify the motivation of our proposed schemes where equipping SUs with directional antennas can significantly enhance the channel rendezvous performance in high-density PU networks as compared with the omnidirectional antennas paradigm.


## 6.1. Performance Comparison of the SH Schemes

We first compare the performance of our SH schemes with the two blind SH schemes in [28, 30]. The SH scheme in [19] is not compared here because it is not a blind scheme. Extensive simulation experiments are conducted to compute the sector rendezvous latency (SRL) between two neighboring SUs (a sender SUi and a receiver SUj). In the simulations, we consider different antenna configurations for the SUs where we simulate several combinations for the number of sectors (Ni and Nj). The relative locations of SUi and SUj represented by (hi, hj) as well as the clock drift are randomly generated. For the ID-based schemes, two different 7-bit IDs are randomly assigned to the SUs. For each (Ni and Nj) combination, the simulation results are obtained by conducting 105 independent runs where we accordingly compute the average and maximum SRL (ASRL and MSRL).Figure11 depicts the SRL results for the asymmetric-role SH schemes (our PES-SH and Li and Xie’s SH [28]). The results illustrate the significant reduction on the SRL provided by our PES-SH in terms of ASRL and MSRL under all the different antenna configurations of the pair of SUs. For some antenna configurations, PES-SH can reduce the ASRL and MSRL significantly up to 80% and 84%, respectively. The shorter ASRL and MSRL provided by the PES-SH scheme are due to its efficient design which relies on the coprimality between the adjusted prime and even numbers of Ni and Nj, respectively. And since Ni is prime for all the sender SUi antenna configurations while the values of Nj are even numbers that are valid for use (i.e., not in the AES set), this allows the sender SUi in our PES-SH to achieve sector rendezvous with its receiver SUj within NiNj SH period.Figure 11
Comparison of the sector rendezvous latency between our PES-SH scheme and Li and Xie’s SH scheme [28] under fixed Ni and varying Nj.
(a)
N
i
=
5
(b)
N
i
=
11
(c)
N
i
=
17On the other side, the design of Li and Xie’s SH scheme requiresNi and Nj to be adjusted to primes. Furthermore, the sender should perform an initiating round-robin SH sequence with a length of Ni2 before it converts to the regular prime-based sequence. Accordingly, this will prolong the SH period needed for achieving the sector rendezvous to (Ni2+NiPj) which actually represents the theoretical upper bound for the MSRL of Li and Xie’s SH scheme when (Ni≠Pj). We can notice that this upper bound is tight for some (Ni and Nj) combinations, while it is not for others. Specifically, when (Ni%  Pj=1) where Pj is the adjusted prime for Nj, the sender SUi cannot rendezvous with its receiver during its initiating Ni2 round-robin SH sequence. However, when it starts following the regular prime-based SH sequence, the sector rendezvous happens within the subsequent NiPj slots, which results in (Ni2+NiPj) MSRL. For example, when Ni=11 and Nj=4 in Figure 11(b), the sector rendezvous occurs in (121+11×5)=165 sector slots. The same thing can be noticed for the cases when Nj=2 in Figures 11(a), 11(b), and 11(c), where the MSRL is (Ni2+Ni×2). This explains the irregular increased results in the figures for such (Ni and Nj) combinations.In Figure12, the SRL results for the symmetric-role SH schemes (our IPES-SH and the Chen et al.’s SH scheme [30]) are shown. In the figure, it is shown that our IPES-SH scheme outperforms the other compared scheme especially in terms of MSRL. This improvement is due to the shorter SH period provided by IPES for achieving the sector rendezvous. In both schemes, the SH period for sector rendezvous depends mainly on the extended ID length as well as the adjusted numbers for (Ni and Nj) that are used for constructing the interleaved sequences. However, the adjusted parameters used by our IPES scheme are smaller than those used by the other scheme. Firstly, in the IPES-SH scheme, the extended ID length is 2m=14 which is relatively smaller than the 2m+1=15 extended ID used by the other scheme. Furthermore, the interleaved SH sequences in Chen et al.’s SH scheme are constructed by adjusting the number of sectors to a prime number as well as to a number that is a power-multiple of two (i.e., qk=2bk, where bk is the smallest integer satisfying 2bk≥Nk). However, these adjusted numbers must be coprime with the extended ID length in order to achieve a successful sector rendezvous. Meanwhile, in IPES-SH, the interleaved PS and ES sequences are constructed based on the closest prime number and the closest even number which is not in the AES set. Hence, under most of the simulated antenna configurations, the adjusted Ei and Ej in IPES are smaller than the adjusted qi and qj parameters in the other scheme. For example, in our IPES-SH scheme, Ej=Nj for all the Nj values, while the qj adjusted parameters for the Nj values in Chen et al.’s SH scheme are {2,4,8,8,16,32}. Moreover, when Ni or Nj is ≤5, the adjusted prime number used in IPES is 5, while it is 7 on the other scheme because 7 is the closest prime that is coprime with the 15-bit extended ID. According to that, SUs in the IPES scheme can achieve the sector rendezvous faster than Chen et al.’s SH scheme.Figure 12
Comparison of the sector rendezvous latency between our IPES-SH scheme and Chen et al.’s SH scheme [30] under fixed Ni and varying Nj. ID length = 7 bits.
(a)
N
i
=
5
(b)
N
i
=
11
(c)
N
i
=
17


## 6.2. Performance Comparison of the Combined SCH Schemes

In this subsection, we compare the channel rendezvous performance of our SCH schemes with the other works under a practical DIR-CRN. The simulation configuration parameters are shown in Table1.Table 1
Simulation parameters.
Network area deployment
500m×500m
Number of channels (L)
10
Number of PUs
50
The radius of the SU sensing/transmission range
150 m
Slot duration for sending a packet on a channel
2 ms
The PU packet arrival rate
10 packets/s
The length of a PU packet
120 slotsWe start our SCH simulation by comparing the performance of our combined PES-SCH with the combined SCH schemes of Song and Xie [19] and Li and Xie [28]. We evaluate our PES-SCH for n=4 best-quality channels which correspond to a AGQ-CH period of 16 time slots in each sector (i.e., the frame length = 16). The other selected schemes for comparison are simulated with their proposed CH schemes. In [19], the SH scheme is combined with the asymmetric-role CH scheme in [35], where the sender SU stays for L2 slots on each sector frame of its SH sequence performing a sequential fast CH on the (Ci⊆L) available channels within the sector. Meanwhile, the receiver SU stays for (Ni+1)×L2 slots on each sector of its Ni sectors performing a slow CH on all of its (Cj⊆L) available channels. On the other side, the SH scheme of Li and Xie [28] is combined with the EJS-CH scheme [10]. However, due to the long period of the EJS-CH scheme required to guarantee channel rendezvous, Li and Xie simulated their SCH scheme by letting SUs stay for smaller period on each sector of their SH frames. During this period, SUs execute the corresponding subsequences of their generated EJS-CH sequence. Therefore, we simulate Li and Xie’s SCH scheme with a similar sector frame length to our PES-SCH scheme (i.e., 16 slots). All the schemes are simulated under different asynchronous settings where the clock drifts amount between SUs is selected randomly in each experiment.Figure13 depicts the TTR simulation results for the three schemes when they are evaluated under different antenna configurations for the pair of SUs. Even though the combined SCH scheme of Song and Xie is not a blind scheme, it produces very long TTR results. This is due to the large sector frame length where the sender and receiver stay for L2 and L2×(Ni+1) time slots, respectively, on each sector for performing their corresponding CH sequence. As a consequence, the SCH period needed for achieving rendezvous is Nj×(L2×(Ni+1)) which is very long as compared to the period of our PES-SCH scheme. On the other side, Li and Xie’s SCH scheme can provide shorter ATTR than Song and Xie’s scheme because it is simulated with smaller frame length. However, the MTTR of this scheme cannot be traced because we observe that TTR in some cases cannot be achieved within the whole simulation duration which is set to 5×104 slots. The reason for the indeterministic behaviour of Li and Xie’s SCH scheme is because the stay period in each sector (i.e., 16 slots) is insufficient to guarantee rendezvous while using the EJS-CH scheme. According to the EJS-CH [10], the rendezvous cannot be guaranteed unless the EJS-CH sequences of the communicating SUs are overlapped for at least 4PL(PL+1-G)=44(12-G) time slots. PL is the smallest prime number greater than L, while G is the number of common available channels between the SUs available channels. Hence, to ensure rendezvous regardless of any misalignment of their local clocks, the SUs should stay for at least 4PL2 on each sector of their SH sequences to perform their EJS-CH sequences. This trade-off between the bounded MTTR of Song and Xie’s SCH scheme and the small ATTR of Li and Xie’s SCH scheme illustrates the efficiency of our proposed AGQ-CH scheme, which allows PES-SCH to guarantee rendezvous with the shortest TTR results.Figure 13
Comparison of the time-to-rendezvous (TTR) between the asymmetric-role SCH schemes whenNi=5.In the second setting of the SCH simulation, we combine the SH schemes of Li and Xie [28] and Chen et al. [30] with our proposed AGQ-CH scheme. This is in order to evaluate their channel rendezvous performance when they are combined with an efficient and suitable CH scheme. Figures 14 and 15 show the TTR results of these schemes and our schemes when they are simulated for different values of the best-quality channel n(2⩽n⩽5). In the simulation, we consider different values for the sender number of sectors (Ni={4,6,12}), while the receiver number of sectors Nj is set as 4. The figures show that our schemes always outperform the other schemes under all the different antenna configurations of the SUs. This is mainly due to the shorter SRL of our SH schemes and, as explained in Section 5.4, TTR depends on the SRL of the SH scheme coupled with the length of the sector frame (n2). Moreover, the figures illustrate the effect of n (i.e., the number of best-quality channels) on the rendezvous performance where we can notice that as n increases, the TTR results for all the schemes increase. This is because the larger n, the longer the frame length n2. Accordingly, when SUs spend longer period in each sector, they may waste more time while attempting rendezvous on other sectors rather than the rendezvous sector. This will result in a longer TTR until they can achieve a successful sector and channel rendezvous.Figure 14
Comparison of the time-to-rendezvous (TTR) between the asymmetric-role SCH schemes whenNj=4.Figure 15
Comparison of the TTR between the symmetric-role SCH schemes whenNj=4. ID length = 7 bits.Finally, to illustrate the performance gain brought by applying directional antennas for channel rendezvous, we compare the performance of our combined PES-SCH scheme with the AAsync-CH omnidirectional antenna rendezvous scheme [16]. The AAsync-CH is selected among the other omnidirectional CH schemes since it is designed for asymmetric-role environment (i.e., SUs have preassigned role) similar to our PES-SCH. The schemes are compared in terms of their probabilities for achieving a successful channel rendezvous under different number of PUs in the network area. In our PES-SCH, the simulated sender and receiver SUs have Ni=5 and Nj=6 number of sectors and the number of best-quality channels n=3.Figure16 shows the significant outperformance of our directional antenna scheme as compared with the omnidirectional antenna scheme. It can be noticed from the figure that when the number of PUs in the network increases, the probability of the successful channel rendezvous for the omnidirectional scheme decreases dramatically. Meanwhile, in the PES-SCH, this probability is almost 1 for most of the cases and only decreases slightly when the number of PUs is close to 100. This is due to the smaller interference region of the directional antenna, which results in higher channel availability for the SUs as compared to the omnidirectional antenna. So, when the total number of PUs in the network area increases, only few of them may reside within the SUs rendezvous sectors where they can only impose a slight change in the channel availability. Accordingly, the probability of having common channels between the SUs on their sector rendezvous pair is always high, which increases the probability of successful channel rendezvous.Figure 16
Comparison of the successful channel rendezvous probability between our PES-SCH directional antenna scheme and the AAsync-CH omnidirectional scheme.These results justify the motivation of our proposed schemes where equipping SUs with directional antennas can significantly enhance the channel rendezvous performance in high-density PU networks as compared with the omnidirectional antennas paradigm.


## 7. Conclusions

In this paper, we studied the sector and channel rendezvous problem for SUs in DIR-CRNs. Two efficient coprimality-based sector hopping schemes have been proposed for providing sector rendezvous in asymmetric- and symmetric-role environments. The SH schemes are combined with an efficient grid-quorum-based CH scheme for providing a guaranteed sector and channel rendezvous simultaneously between the SUs in DIR-CRNs. Theoretical analysis and extensive simulations are conducted to demonstrate the efficiency of the proposed schemes. The simulations results verify that our schemes significantly outperform the previous directional antenna rendezvous schemes (in terms of SRL and TTR). Furthermore, they demonstrate that our directional antenna rendezvous paradigm is more resistant to rendezvous failures under high-density PU CRNs, as compared with the omnidirectional antenna rendezvous paradigm.



---

*Source: 5748067-2017-12-12.xml*