Rendezvous Issues in AD Hoc Cognitive Radio Networks
Rendezvous Issues in AD Hoc Cognitive Radio Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Nov, 8(11): 3655-3673
Copyright © 2014, Korean Society For Internet Information
  • Received : June 02, 2014
  • Accepted : September 10, 2014
  • Published : November 30, 2014
Export by style
Cited by
About the Authors
Gyanendra Prasad, Joshi
Seung Yeob, Nam
Sung Won, Kim

Rendezvous is a process of two or more cognitive radio nodes gathering on the same channel at the same time for a negotiation to establish data communications. This paper discusses rendezvous issues in cognitive radio networks. It details why rendezvous is an issue in cognitive radio networks and how rendezvous works. It classifies channel access methods, and details sequence-based channel-hopping methods. It surveys existing works on blind rendezvous and compares the proposed algorithms in terms of the maximum time to rendezvous. This paper discusses the properties that an efficient channel-hopping rendezvous algorithm should have and illustrates common issues in the existing rendezvous methods. It also explains open research issues in the rendezvous area.
1. Introduction
- 1.1 Why rendezvous?
U nlike other wireless networks, in a multichannel ad hoc cognitive radio network (CRN), cognitive radio (CR) nodes must access channels opportunistically. This means they can access a channel when no incumbent licensed user of the channel is using that channel. Rendezvous is a process of gathering two or more CR nodes on the same channel at the same time for communications.
The first and basic problem in CRN design is how CR nodes rendezvous on a channel to exchange channel negotiation control packets to initialize actual communications. These channel negotiation control packets may include activities of incumbent licensed users, channel conditions, and the number of channels available to use opportunistically, among other things.
In the multichannel environment, sender nodes do not know on which particular channel they will find the intended receivers. Therefore, receivers may miss the packet intended for them. This problem is called the multi-channel hidden node problem [1] . Some medium access control (MAC) protocols use request to send (RTS) and clear to send (CTS) to solve traditional hidden terminal and exposed terminal problems. In the multichannel scenario, nodes can miss RTS/CTS packets and suffer from the multichannel hidden node problem. This new problem is sometimes referred to as the missing RTS and missing CTS problem [2] .
In CRNs, CR nodes do not have absolutely guaranteed white space on any channel for communications. Ad hoc CRNs require multiple incumbent channels for efficient communications. In multi-channel environment, CR nodes may miss control packets intended for it while communicating in different channel and its transmission may collide with another CR node’s transmission or incumbents’ transmission. This problem is called the multichannel hidden node problem. This is a more serious issue in CR environment, because it may disturb incumbents’ transmission. To avoid the multichannel hidden node problem, CR nodes should rendezvous on a common channel and exchange channel negotiation packets for further data communication.
- 1.2 How to rendezvous
- 1.2.1 CCC-based approach
Assigning a channel as a common control channel (CCC) common to all the nodes in the network, which is used only for control messages, is the best solution to the multichannel hidden node issue. A CCC in CRNs also resolves recovery from the intervention of incumbents. Cognitive users should respect incumbent users’ right to access any channel, anytime, and anywhere. Therefore, whenever an incumbent user arrives on the channel currently using by cognitive users, they must leave within a pre-specified time. To renegotiate for another data channel, cognitive users can rendezvous in the CCC. As shown in Fig. 1 , there are two well-known methods to access a channel in multichannel ad hoc CRNs. The first approach is the CCC-based approach.
PPT Slide
Lager Image
Classification of rendezvous in CRNs.
Several of the MAC layer protocols for CRNs proposed in the literature assume that a global CCC is available to all CR nodes in the network for exchanging channel negotiation control packets for a data channel [3 - 6] . There is equal opportunity for all CR nodes to access this channel, and this channel is free from intervention by incumbents. These protocols simply assume that a CCC can be rented, leased or borrowed from incumbents. In fact, all these assumptions are not realistic in the practical world. Some issues that remain in those assumptions are as follows.
  • - Who will provide the CCC? Is it an incumbent licensed holder for a spectrum band? Or is it government that allocates such a channel?
  • - If an incumbent provides such a channel for lease or rent, who will manage it?
  • - Who will pay the cost? How much is the cost, and what is the payment method? Does every cognitive user need to subscribe to such a channel from the incumbent licensed holders or spectrum brokers? If there is such a ‘for-fee’ CCC channel, then can only the members of that channel communicate with each other? What if there are multiple incumbents who want to provide a CCC?
  • - If the CCC is free for all, how do you prevent the channel from being used for messages other than control messages for CRNs. For example, what if someone uses the CCC as an industrial, scientific and medical (ISM) band?
Even before raising these issues, a channel dedicated to control packets only is against the main objective of cognitive radio networks, which is to utilize spectrum efficiently. Another objective is to determine how maximum utilization of spectrum can be achieved. However, using a single channel just for control packets runs counter to the actual value of CRNs.
As shown in Fig. 1 , some multiple CCC-based mechanisms even require multiple channels for the control signals only [7 , 8] . Cluster-based approaches may use different channels in different clusters as the CCC, and do not need a dedicated global CCC, but they have the same rendezvous issues.
Some authors [9 , 10] suggested that ISM bands can be used for a CCC, which is simply not possible in most cases. ISM bands are shared with other technologies and users; therefore, they cannot be used solely for CRNs.
Other authors [11 - 13] argued that underlay CR techniques, such as an ultra-wide band (UWB), can be used for a CCC. This is a possible solution. However, a UWB is designed to work in the indoor environment. If used for overlay CRNs, several new hardware issues may arise. Because underlying technologies are not same, there needs to be vertical handover. Also, a UWB is useful for short range, but higher bandwidth required environment. Therefore, it is more suitable for a more specific environment only.
Let us suppose that a CCC is available exclusively for secondary users (SUs); there are several other issues, such as control channel bottleneck, channel early saturation [14] , security vulnerabilities, and single point of failure, among others. These issues increase delay, decrease throughputs and limit the performance of overall CRNs.
- 1.2.2 Channel hopping–based approaches
Rendezvous in CRNs can be categorized into two types: CCC-based rendezvous and channel hopping (CH)–based rendezvous, also called blind rendezvous, as shown in Fig. 1 . In the CH-based rendezvous approach , CR nodes hop through the potential channels for communications until they find the intended communications pair. Therefore, it is called blind rendezvous1 [15] .
In the CH-based rendezvous approach, the time is divided into slots of fixed duration. Two CR nodes access a channel during a certain period of time that is long enough to establish a connection. The time to rendezvous (TTR) is the number of time slots required for finding a common channel after CR nodes have begun the rendezvous process. Because, in this mechanism, a CCC is not required, there are no problems that occur owing to the CCC, such as control channel bottleneck, channel early saturation, security vulnerabilities, and single point of failure, among others.
CH-based rendezvous can be further categorized into sequence-based CH, also called sequence-based blind rendezvous, and random CH, also called random blind rendezvous. In random blind rendezvous, each node hops channels randomly at certain hopping rates. All the nodes may have the same or different hopping rates. Random blind rendezvous has no upper bound for TTR. Therefore, it may take a long time to rendezvous and does not guarantee rendezvous.
Sequence-based CH algorithms can be either synchronous or asynchronous. Synchronous algorithms assume that there exists a global clock synchronization mechanism for nodes in the network, and CR nodes can start their own channel-hopping sequences at the same global time. Nevertheless, synchronization among nodes may not always be feasible for ad hoc networks. Therefore, asynchronous algorithms were proposed to enable rendezvous among CR nodes without global clock synchronization.
Both synchronous and asynchronous algorithms can be evaluated under symmetric and asymmetric channel models. In symmetric channel model, every CR nodes have the same number of channels ( N ) and in asymmetric channel model, every CR nodes may have different number of channels. Many rendezvous algorithms in the literature do not work in asymmetric model (described in Section 3). In Fig. 1 , ‘symmetric’ and ‘asymmetric’ means algorithms that can work under symmetric and asymmetric channel models, simultaneously. Symmetric model is suitable for the topology where the nodes are in close proximity and asymmetric model is considered for the large geographical region.
In this paper, we have interchangeably used terms ‘CH-based rendezvous’, ‘sequence-based CH’ and ‘random CH’ for ‘blind rendezvous’, ‘sequence-based blind rendezvous’, and ‘random blind rendezvous’ respectively.
2. Basics of sequence-based CH (sequence-based blind rendezvous)
In the Sequence-based CH (also called sequence-based blind rendezvous ) approach , CR nodes generate CH sequences and follow the CH sequences until they find their intended receiver. For successful CH-based rendezvous, CR nodes should meet on the same channel in the same timeslot. After successful rendezvous in a common channel, CR nodes start channel negotiation for data channel, hop to the negotiated channel, and start data communication.
Fig. 2 shows an example of sequence-based blind rendezvous approach. Let us say there is a CR node (A) that wants to send data to another CR node (B). To make it simple, let us assume both sender and receiver have the same number of available channels. Assume there are five channels. The CR nodes generate random sequences, and the timeslots of the sequences are synchronized. Let us assume node A generates a sequence such as {1,2,3,1,2,3,1,2,3,…} and node B generates a sequence such as {5,5,5,4,4,4,3,3,3,…}. They switch channels according to their own hopping sequences and eventually rendezvous on a common channel (i.e. channel 3). They negotiate further for data communications on that channel and start communications.
PPT Slide
Lager Image
Basic sequence-based rendezvous mechanism.
An insufficiently large number of CH sequences can result in the rendezvous convergence problem [16] . Therefore, the CH sequence generated for sequence-based blind rendezvous should be designed carefully.
TTR is typically measured in timeslots and is the one of the main metrics for evaluating sequence-based mechanisms. A timeslot (or slot) is the minimum interval required to exchange control information in order to rendezvous between sender and receiver nodes. Generally, TTR depends on the channel-hopping algorithm, but in the CRN environment, it depends upon several other environmental factors, such as the number of channels available, incumbent licensed user behavior on the channels, misdetection and false alarms, among others. We discuss TTR owing to the CH algorithm, but analyzing the impact of these other environmental factors on TTR is outside the scope of this work .
Nevertheless, most of the blind rendezvous mechanisms are limited to two CR nodes, but there are some approaches proposed for multiple CR nodes to rendezvous and work in a multihop fashion [17 - 20] . In mechanisms for multiple CR nodes, a cognitive node waits for a period of time after it wakes up and listens for a beacon signal. If there is no beacon message for a period of time, it generates a hopping sequence and hops accordingly. It broadcasts a beacon in every channel and synchronizes with other CR nodes. It waits for time τ in every channel. If there is any other node in any channel, that node also follows the same hopping sequence of the first node. CR nodes complete synchronization in N × τ time periods, where N is the number of channels. If the number of channels is small, this mechanism works fine. If the number of channels is large, it takes a long time to synchronize and rendezvous. Also, this mechanism needs tight synchronization among all active CR nodes.
The time synchronization–based algorithms guarantee maximum time to rendezvous (MTTR) in most cases, and this solves the rendezvous problem, but it is difficult to start neighbor discovery and time synchronization for a CR node. Therefore, a competent rendezvous solution should achieve guaranteed rendezvous even without the need for time synchronization (i.e. CR nodes can start their channel hopping at any time). Fig. 3 shows such a time-slotted system, where different CR nodes have different timeslot start times for hopping.
PPT Slide
Lager Image
Time-slotted for CH without time synchronization.
Basically, a sequence-based blind rendezvous method works as shown in Fig. 4 . Each cognitive user generates its own hopping sequence and starts switching channels per the generated hopping sequence. Before sending its own beacon for receiver discovery, it senses the channel to confirm the presence of an incumbent licensed user on the channel. If it finds the incumbent licensed user, it generates another hopping sequence excluding the current channel and starts switching channels according to the newly generated hopping sequence. The exclusion of the busy channel is memory-less and only for the next hopping sequence generation. That channel is generally included in the hopping sequence generation after that. On the other hand, if there is no incumbent licensed user on the channel, it sends a beacon to communicate with the intended receiver. If the receiver is not on the same channel, then the cognitive user hops to another channel and repeats the procedure.
PPT Slide
Lager Image
Sequence-based blind rendezvous method in CRNs.
In literature, various sequence-based blind rendezvous algorithms have been proposed, which perform limitedly and cannot fully satisfy performance requirements, thus leaving room for improvement. Thus, in the following sections, we survey the existing literature, in order to assist researchers in the field of CRNs.
3. Some recent sequence-based CH rendezvous algorithms
Various rendezvous algorithms are proposed in the literature. In this section, we summarize some of the recent sequence-based CH algorithms, their properties and MTTRs.
- 3.1 Sequence-based rendezvous
DaSilva and Guerreiro [21] proposed a sequence-based rendezvous (SBR) that is asynchronous and uses non-orthogonal channel sequences. If the sequences are orthogonal, two radios cannot simultaneously occupy the same channel. Therefore, this method uses non-orthogonal channel sequences so as to maximize the probability that two CR radios eventually rendezvous on the same channel.
As shown in Fig. 5 , a node selects a permutation of the N channels (there are N ! permutations) and build the sequence. The selected permutation appears ( N + 1) times in the sequence, i.e. the permutation appears contiguously N times and once the permutation appears interspersed with the other N permutations.
PPT Slide
Lager Image
Sequence structure in SBR.
For example, let us assume N = 5 and a random permutation is {3,2,4,1}. The SBR scheme generates a rendezvous sequence such as
PPT Slide
Lager Image
In this sequence, the original permutation {3,2,4,1} is repeated N +1 times: the four original permutations and one interspersed among the other four appearances of the permutations. This sequence has a period of N ( N + 1) slots. Therefore, the maximum TTR is bounded by N ( N + 1) timeslots.
This is a good initiative; however this scheme still takes a long time for rendezvous.
- 3.2 Quorum-based channel hopping
Bian et al. [16] proposed quorum-based channel-hopping (QCH) algorithms to establish the CCC. These schemes are based on the property of intersection. The authors proposed both synchronous and asynchronous channel-hopping schemes.
Synchronous schemes, M-QCH and L-QCH are based on the quorum system, where a quorum is an element of the system Q that satisfies the intersection property p q ≠ ∅, ∀ p , q Q . These quorum-based rendezvous schemes guarantee rendezvous between CR nodes. Asynchronous quorum-based channel hopping (A-QCH) and asynchronous maximum overlapping channel hopping (A-MOCH) are two asynchronous schemes. A-QCH guarantees rendezvous only on two distinct channels. However, the A-MOCH mechanism assumes that the rotation closure property of the quorum-based system must be satisfied by one commonly available channel to rendezvous in N 2 timeslots. Two CR nodes may rendezvous during the last N timeslots of a channel-hopping period. Therefore, the MTTR is N 2 N + 1. These protocols may provide rendezvous regardless of the number of sets of channels available per CR node.
- 3.3 Deterministic rendezvous sequence
Yang et al. [22] proposed a distributed channel rendezvous scheme called deterministic rendezvous sequence (DRSEQ) for multichannel access networks. It has exactly one sequence, which consists of 2 N + 1 indices. Elements of a CH sequence are generated as i + 1, and 2 N i + 1 for 0 < i < N – 1, and N + 1 i ≤ 2 N simultaneously. An empty slot is inserted when i = N . In DRSEQ, two nodes visit available channels to rendezvous within 2 N + 1 timeslots.
- 3.4 Distributed channel rendezvous sequence
In CRNs, availability of channels is time- and geolocation-dependent; therefore, the available channels can be different for each CR node. Shin et al. [23] . presented a distributed channel rendezvous sequence (CRSEQ) algorithm to resolve this issue. This algorithm is based on the properties of triangular numbers and the Chinese remainder theorem. The channel number for slot i can be z mod N + 1 , for 0 y < 2P 1 and x mod N + 1 , for 2P 1 y < 3P 1 , where, z = ((( x + 1 ) + 2y ) / 2 ) mod P , x = ⌊ i / ( 3N 1 )⌋, y = i mod ( 3P 1 ), and 0 i < P ( 3P 1 ). P is the smallest prime number greater than or equal to N , and by the known results about the distribution of primes, P = N + 0 ( N 2/3 )) [24] . Two CR nodes rendezvous in P ( 3P 1 ) timeslots. This algorithm guarantees rendezvous even under the asymmetric model, i.e., users have different sets of available channels, within a bounded time.
- 3.5 Efficient channel hopping
Zhang et al. [25] proposed two algorithms, namely synchronous efficient channel hopping (SYNC-ETCH) and asynchronous efficient channel hopping (ASYNC-ETCH). In these schemes, sequences are constructed in a way similar to SBR. The SYNC-ETCH algorithm has three parts: rendezvous scheduling, rendezvous channel assignment, and CH sequence execution.
Rendezvous scheduling constructs 2 N − 1 rendezvous schedules among a set of 2 N empty CH sequences such that each CH sequence is paired with a different CH sequence in each of the rendezvous schedules. After scheduling rendezvous among the empty CH sequences, SYNC-ETCH assigns rendezvous channels to each of these sequences. Finally, after CH sequence construction, nodes synchronize with the existing nodes using the global synchronization mechanism and start the channel-hopping process. A node randomly selects a CH sequence and follows it. After finishing all the slots, it performs the random CH sequence selection again and starts hopping on the newly chosen CH sequence.
ASYNC-ETCH is similar to SYNC-ETCH but does not assume that the global clock synchronization mechanism exists. These approaches work under the symmetric model, and therefore, are not suitable for practical CRNs. MTTR for SYNC-ETCH and ASYNC-ETCH are 4 N – 3 and N (2 N + 1) simultaneously.
- 3.6 Generated orthogonal algorithm
Theis et al. [15] presented an asynchronous CH algorithm called the generated orthogonal algorithm (GOA), which is similar to SBR. In this algorithm, a sequence is generated from permutations of all the channel indices. A permutation appears N times continuously as well as once interspersed with the other N permutations. Its MTTR is N ( N + 1) timeslots.
The authors also proposed two algorithms called the modular clock (MC) algorithm for the symmetric model and the modified modular clock (MMC) algorithm for the asymmetric model. In MC and MMC, each user selects a prime number P and randomly selects a rate r , which is less than P , where r is the rate with which a cognitive user hops between channels. Based on these parameters, the cognitive user generates a CH sequence using modulo operations. If the current channel index is i , it hops onto the channel with index (( i + r ) mod P ) in the next timeslot. MC and MMC algorithms cannot guarantee rendezvous of two CR nodes in a finite time if the users select the same r and P .
- 3.7 Jump-stay rendezvous algorithms
Lin et al. [26] and Liu et al. [27] presented the jump-stay (JS) rendezvous algorithms and an enhanced version of the JS algorithm called the enhanced jump-stay (EJS) rendezvous algorithm [28] . Basically, these algorithms generate CH sequences in rounds, and each round consists of one jump-pattern and one stay-pattern. Users continuously hop onto available channels in the jump-pattern while staying on a specific channel in the stay-pattern. The jump-pattern lasts for 3 P timeslots and 2 P timeslots in the JS and EJS algorithms, respectively, whereas the subsequent stay pattern lasts for one P timeslot in both algorithms.
For example in JS, let us assume that two CR nodes have N = 4. The smallest prime number that is greater than N is 5. The first cognitive node selects a random start point 2 and a hopping step 4. The jump-pattern for the first cognitive node is {2, 1, 5, 4, 3, 2, 1, 5, 4, 3} and the stay-pattern is {4, 4, 4, 4, 4}. Again, the jump-pattern 5 is replaced by the initial channel for the first cognitive node (i.e. 2). The final JS-CH sequence for the first cognitive node is
PPT Slide
Lager Image
The second cognitive node selects a random start point 3 and a hopping step 2. The jump-pattern for the second cognitive node is {3, 5, 2, 4, 1, 3, 5, 2, 4, 1} and the stay-pattern is {2, 2, 2, 2, 2}. In the jump-pattern, 5 is replaced by the initial channel for the second cognitive node (i.e. 3). The final JS-CH sequence for the second cognitive node is
PPT Slide
Lager Image
The JS algorithm was also extended for multiuser and multiple-hop scenarios, as well. For multiuser rendezvous, first of all, a cognitive user performs rendezvous with its neighbor. Then those users exchange information on their 3-tuples: step-length (r), starting-index (i) and timeslot (t). The cognitive user that has the smaller 3-tuple will follow its neighbor and update its 3-tuple with the larger one. Then, both users synchronize and use the identical CH sequence for rendezvous with other users in a similar way. This process continues until rendezvous of all users is achieved.
MTTR of JS is 3 P and the MTTR of EJS is 4 P in the symmetric model, where P is the smallest prime number greater than N . In the asymmetric model, EJS has a lower MTTR than JS, i.e. 4 P ( P + 1 – G ) and 3 NP ( P G ) + 3 P , respectively, where G is the number of channels commonly available to the two users.
Paul et al. [29] extended the JS algorithm and presented it as the JS-based enhanced rendezvous algorithm (ERA). ERA supports multiple interfaces and works in asymmetric model. Channels are ranked according to the channel condition and an adaptive jumping pattern generated so that a better channel is jumped more often, and users have a higher possibility to rendezvous on such a channel.
- 3.8 Asynchronous channel hopping
Bian and Park [20] presented two asynchronous channel-hopping (ACH) methods: symmetric (Sym-ACH) and asymmetric (Asym-ACH).
Sym-ACH assumes that each cognitive node has a unique n -bit ID (such as the MAC address of a node), and HC is generated based on it. Sym-ACH does not require pre-assigned role as a sender or receiver. In the Asym-ACH system, every node needs to be pre-assigned a role as either sender or receiver. The sender and receiver CR nodes use different methods to generate their CH sequences for rendezvous. In the Sym-ACH system, CR nodes do not need to have a pre-assigned sender or receiver role, and every node generates a CH sequence following the same method. TTR for Sym-ACH and Asym-ACH are upper-bounded. The MTTR for Asym-ACH and Sym-ACH are N 2 N + 1 and 6n N 2 , respectively. Here, n is the length of user ID in bits.
- 3.9 Hopping sequence guaranteeing rendezvous within a single period
Kim et al. [30 , 31] proposed an asynchronous channel-hopping mechanism called a hopping sequence guaranteeing rendezvous within a single period (HS-GRSP). It generates two sequences, a group sequence and a guard sequence.
The group sequence has a group index and remaining terms in reverse order. For example, if N = 3 ( N is prime in this algorithm), then group sequences are
PPT Slide
Lager Image
From these group sequences, a chain is generated, such as {1,3,2,1,2,2,1,3,1}.
A guard sequence is generated by repeating the center channels. For the channel list {1,2,3}, the guard sequence becomes {2,2,2,2}. The guard sequence has 4 entries because the distance from last center channel to the end of the chain sequence is 4. Finally, a rendezvous sequence is generated by merging the chain sequence and guard sequence. The MTTR of HS-GRSP has the same length in the rendezvous sequence and is equal to 1/8(5 N 2 + 18 N - 8).
- 3.10 Fast rendezvous channel-hopping algorithm
Chang and Hung [32] proposed a symmetric asynchronous channel-hopping algorithm called the fast rendezvous channel-hopping (FRCH) algorithm. This algorithm can guarantee rendezvous within 2N 2 + N timeslots, even when not all channels are certain to be available to every SU. In this algorithm, a seed sequence is generated, as is done in DRSEQ. Two types of sequence are generated: a default sequence and an adaptive sequence. The default sequence consists of N rounds, and each round executes a seed sequence. The adaptive sequence is generated by replacing each unavailable channel in the default sequence with an available channel.
- 3.11 Synchronous channel-hopping sequence
Tessema et al. [33] presented two channel-hopping algorithms: a synchronous channel-hopping sequence (S-CHS) and an asynchronous channel-hopping sequence (A-CHS). These algorithms have three parts: (a) construction of a Cayley table, (b) reflection of the Cayley table, and (c) construction of S-CHS by cyclic shift and catenation.
The permutation of a set on the Cayley table is obtained with an integer addition modulo operation. The reflected Cayley table is constructed by appending all elements except the last element to the end of each row of the given Cayley table in reverse order. For example, if the elements in a row of the Cayley table are {0,1, …, N − 1}, the reflected row will be {0, 1, …, N – 2, N – 1, N – 2, N – 3, …, 1, 0 }. There are 2 N – 1 elements per row in the Caylay table.
- 3.12 Short-sequence-based algorithm
Reguera et al. [34] presented short-sequence-based (SSB) rendezvous algorithm that works under symmetric channel model and the channel replacement method that works in both the symmetric and asymmetric channel models.
The CR nodes start the sequences in one extreme of the segment, progressively move to the other extreme, and return through the opposite path. Once a CR node returns to the origin of the sequence, it remains there during one time slot. This method works only for the symmetric channel model. For the asymmetric channel model, the unavailable channel for certain CR node is replaced by the available channel for that period and this is called channel replacement method. Under the asymmetric model with N potentially available channels, MTTR upper bound is ( N–1 ) T , where T is the sequence period in which channel replacement procedure is used and T = 2N - 1 .
- 3.13 Simple role-based rendezvous algorithm
Guerra et al. [35] proposed simple role-based (SRB) rendezvous algorithm. This algorithm requires each CR node has a pre-assigned role as a sender or a receiver, but it does not require time synchronization. The transmitter and the receiver follow different hopping strategies. The transmitting CR node performs a sequential search for all the available channels in a round-robin fashion. The receiver CR node jumps or stays in a given channel according to the perceived channel activity. In each timeslot, the receiver CR node decides to stay in the same channel if no incumbent transmission is sensed or to jump the channel according to the predetermined CH sequence unlike the transmitter CR node.
If incumbents’ activity is low in the channel, receiver CR node stays longer in the channels. Therefore, rendezvous is more likely to occur in the less congested channels. This scheme works only for symmetric models. In the absence of the incumbents’ activity, ETTR and MTTR are smaller than the number of the available channels i.e. ( N − 1)/2 and N − 1 respectively.
- 3.14 Channel-hopping schemes
Chang et al. [36] proposed three rendezvous algorithms namely (a) rendezvous couple channel hopping scheme (RCCH), (b) asynchronous rendezvous channel-hopping scheme (ARCH), and (c) symmetric asynchronous rendezvous channel-hopping scheme (SARCH).
RCCH requires each CR node has a pre-assigned role as a sender or a receiver and CR nodes require to be synchronized. ARCH and SARCH are proposed for asynchronous environment. ARCH needs pre-assigned role as either sender or receiver while in the SARCH the previous role allocation is not required.
- 3.15 Role-based parallel sequence rendezvous algorithm
Yu et al. [37] proposed role-based parallel sequence (RPS) rendezvous algorithm, which requires multiple transceivers in a CR node. The basic idea behind this algorithm is one dedicated transceiver stays in a specific channel and another transceivers hop on the available channels with parallel sequences. RPS algorithm is proposed for both symmetric and asymmetric model. Time synchronization is not necessary in this algorithm.
Finally, cyclic shifting (shifting a vector in a cyclic order one at a time) is performed, and a CH sequence is generated by catenating all elements from all the rows of the reflected Cayley table. In these protocols, rendezvous can happen on any channel with equal probability. The MTTR of S-CHS and A-CHS are 2 N – 1 and 3 N + 1, respectively.
Table 1 summarizes the comparison of the rendezvous algorithms we discussed in this work. All the compared algorithms guarantee rendezvous and have upper bounds for TTR. In the table, async. means whether the algorithm works under asynchronous mode or not, Asymm. means whether it works on asymmetric channel model or not. MTTR means the maximum time for two CH sequences to rendezvous when all licensed channels are available and maximum conditional time to rendezvous (MCTTR) means maximum time for two CH sequences to rendezvous when all channels are not surely available for all CR nodes.
Comparison summary of rendezvous algorithms.
PPT Slide
Lager Image
Comparison summary of rendezvous algorithms.
4. Properties of an efficient sequence-based CH rendezvous algorithm and common issues
In this section, we discuss common basic properties that an efficient rendezvous algorithm should have. We also elaborate on some of the common issues in rendezvous methods.
- 4.1 Mandatory requirements
Any efficient rendezvous algorithm should have following properties.
- 4.1.1 Guarantee of rendezvous
Rendezvous algorithms should have a bounded and small MTTR, which is the maximum time for two CH sequences to achieve rendezvous. For any good CH-based synchronous communications rendezvous protocol, where all the rendezvous channels are utilized in each of the hopping slots, the average TTR should be close to (2 N – 1)/2 [25] .
- 4.1.2 Global time-synchronization
Global time-synchronization is not always feasible and has several factors that cause overhead. Therefore, rendezvous algorithms should be asynchronous, and CR nodes should be able to rendezvous on a channel without synchronizing.
- 4.1.3 Multiusers and multi-hop
Rendezvous between only two CR nodes is easy but is not a complete solution. For real-world scenarios, rendezvous algorithms should allow rendezvous between multiple users as well as in multiple hops.
- 4.1.4 Protection of incumbents
Cognitive users should not interfere with the communications of incumbents. They must leave the channel, respecting the incumbents’ primary right to access the channel whenever they want to access the channel. A CH sequence should exclude a channel currently occupied by an incumbent as well as channels that have a higher probability of incumbents arriving at the current time.
- 4.2 Common issues in rendezvous methods
- 4.2.1 CCC-based rendezvous vs. CH-based rendezvous
rendezvous. Both methods have their advantages and disadvantages. Htike et al. [38] surveyed some papers and presented the life cycle for the rendezvous problem in ad hoc CR networks. The survey states that CCC-based approaches make the protocol simple and efficient, but cannot guarantee availability. Conversely, sequence-based protocols may suffer from the multichannel hidden node problem. Unavailability of a CCC can be resolved with a sequence-based protocol. The multichannel hidden node problem can be resolved with a CCC-based protocol. Therefore, it is a lifecycle. Fig. 6 shows the lifecycles of the CH-based approach and the CCC-based approach.
PPT Slide
Lager Image
Lifecycle of the CH-based approach and CCC-based approach.
- 4.2.2 Channel access delay and number of channels
Channel access delay is one of the main factors we need to consider for MAC layer design. Rendezvous algorithms such as random blind rendezvous cannot guarantee rendezvous within a certain time bound.
Actually, there are more spectrum opportunities when the number of channels ( N ) is large. But TTR in CH sequence–based algorithms is highly dependent upon N . The larger the N , the larger the expected TTR. Because availability of spectrum in CRNs is time-, frequency- and geolocation-dependent, algorithms having a long expected TTR are not suitable for efficient CRNs.
- 4.2.3 Problems with multi-hop
A CH-based method is more complicated in a multi-hop environment. The intermediate node has to rendezvous with the sender and the receiver. However, many rendezvous protocols theoretically claim that after rendezvous between two nodes, they exchange the information and continue until they rendezvous with all other nodes [39 , 40] . Practically, this is very difficult, especially in asynchronous, asymmetric and heterogeneous network environments. Even after rendezvous, the intermediate node has to switch channels frequently to convey the message received from the sender to the receiver. Packet delay increases severely if the intermediate node has many senders and receivers. This issue is more serious if the CR nodes have a single transceiver. This issue is discussed in detail by Acharya et al. [41] .
- 4.2.4 Rendezvous catastrophe
If multiple nodes successfully meet in a timeslot and try to exchange control packets, there may be packet collision. In a mobile-node scenario, nodes may move out of communication range. Missed detection and false alarms about the signal may also seriously affect rendezvous success rates.
- 4.2.5 Incumbent licensed users
In CRNs, arrival of incumbent licensed users is uncertain. Most rendezvous algorithms ensure that if incumbents arrive on the channel, that channel is excluded. However, it is always better to use some learning technique to predict incumbent arrival and to generate a CH sequence excluding those channels. There should be a mechanism to share the incumbent’s arrival on the channel with neighbor CR nodes.
5. Future works
Although we have seen that most of the sequence-based blind rendezvous methods have a TTR upper bound, it remains to be determined how much channel access delay is acceptable and how much delay is tolerable for incumbent users.
A complete MAC protocol with sequence-based blind rendezvous has yet to come. Most of the papers in the literature are concerned with MTTR, average TTR (ATTR) or expected TTR (ETTR). Many other factors, such as incumbents’ arrival rate, channel conditions, missed detections and false-alarms, channel access delay, per packet delay, goodput, etc., which all affect network performance, have not been investigated broadly yet and are open for research.
Prediction of an incumbent’s arrival that leads to rendezvous success (or failure) has not been investigated yet. How intelligent and learning methods can be used for rendezvous and how quality of service for CRNs can be guaranteed by maintaining the incumbents’ right to access the channel is another area for research.
6. Conclusion
We surveyed, illustrated and compared the existing rendezvous methods for ad hoc CRNs. We also classified current rendezvous methods in CRNs and listed their characteristics, functions, working principles, and limitations. We pointed out the problems not addressed by existing approaches. We found that many schemes have been proposed as novel solutions for rendezvous issues, but that some improvements still need to be made.
Although, CCC-based rendezvous is a better way to resolve rendezvous issues in CRNs, the methods are not always scalable and flexible. They can incur overhead and can create a single point of failure. Sequence-based blind rendezvous schemes are alternatives to CCC-based rendezvous.
Although they depend highly upon the number of available channels, among the above protocols, S-CHS, SSB, SRB, RCCH and ARCH are seen as promising in terms of MTTR.
We hope this study will be helpful to researchers in this field and will provide the impetus required for further research to resolve rendezvous issues in ad hoc CRNs.
Gyanendra Prasad Joshi is an assistant professor in the Department of Information and Communication Engineering at Yeungnam University, Gyeongsangbuk-do, South Korea. He is an advisor of research and ICT at Global College of Management, Kathmandu, Nepal. He received his PhD in information and communication engineering from Yeungnam University, South Korea, in 2012. He worked for Minigate Co. Ltd. in South Korea as an IT manager after his graduation from Ajou University. He was a recipient of Korean Government Information Technology Scholarship Program (ITSP) and National Research Foundation (NRF) scholarship for his entire PhD and MS studies respectively. He has served in the review process for several international journals and conferences. His main research interests include MAC and routing protocols for next-generation wireless networks, MANETs, cognitive radio networks, RFID systems and digital convergence business.
Seung Yeob Nam received his BS, MS, and PhD in electrical engineering from the Korea Advanced Institute of Science and Technology (KAIST), Daejon, Korea, in 1997, 1999, and 2004, respectively. From 2004 to July 2006, he was a postdoctoral research fellow at CyLab at Carnegie Mellon University, supported by both CyLab and the Postdoctoral Fellowship Program of the Korea Science & Engineering Foundation (KOSEF). Between August 2006 and February 2007, he was a postdoctoral researcher in the Department of Electrical Engineering and Computer Science at KAIST. In March 2007, he joined the Department of Information & Communication Engineering, Yeungnam University, Gyeongsan, Korea, where he is currently an associate professor. His research interests include network security, network monitoring, network architecture, wireless networks, etc.
Sung Won Kim received his BS and MS from the Department of Control and Instrumentation Engineering, Seoul National University, Korea, in 1990 and 1992, respectively, and his PhD from the School of Electrical Engineering and Computer Sciences, Seoul National University, Korea, in August 2002. From January 1992 to August 2001, he was a researcher for the Research and Development Center of LG Electronics, Korea. From August 2001 to August 2003, he was a researcher in the Research and Development Center of AL Tech, Korea. From August 2003 to February 2005, he was a postdoctoral researcher in the Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL, USA. In March 2005, he joined the Department of Information and Communication Engineering, Yeungnam University, Gyeongsangbuk-do, Korea, where he is currently a professor. His research interests include resource management, wireless networks, mobile networks, performance evaluation, and embedded systems.
So Jungmin , Vaidya Nitin H. “Multi-channel MAC for ad hoc networks: handling multi-channel hidden terminals using a single transceiver,” in Proc. of the 5th ACM international symposium on mobile ad hoc networking and computing May 24–26, 2004 222 - 233
Wu S. L. , Lin C. Y. , Tseng Y. C. , Sheu J. P. “A new multi–channel MAC protocol with on–demand channel assignment for multi–hop mobile ad hoc networks,” in Proc. of the IEEE International Symposium on Parallel Architectures, Algorithms and Networks December 7–9, 2000 232 - 237
Cormio Claudia , Chowdhury Kaushik R. 2009 “A survey on MAC protocols for cognitive radio networks,” Ad Hoc Networks 7 (7) 1315 - 1329    DOI : 10.1016/j.adhoc.2009.01.002
Lo Brandon F. 2011 “A survey of common control channel design in cognitive radio networks,” Physical Communication 4 (1) 26 - 39    DOI : 10.1016/j.phycom.2010.12.004
Joshi Gyanendra Prasad , Kim Sung Won , Kim Byung–Seo “An efficient MAC protocol for improving the network throughput for cognitive radio networks,” in Proc. of the IEEE Third International Conference on Next Generation Mobile Applications, Services and Technologies September 15–18, 2009 271 - 275
Joshi Gyanendra Prasad , Nam Seung Yeob , Kim Sung Won 2014 “Decentralized predictive MAC protocol for ad hoc cognitive radio networks,” Wireless Personal Communications 74 (2) 803 - 821    DOI : 10.1007/s11277-013-1322-6
Zhao Q. , Tong L. , Swami A. “Decentralized cognitive MAC for dynamic spectrum access,” in Proc. of the IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN) November 8–11, 2005 224 - 232
Ma L. , Han X. , Shen C.–C. “Dynamic open spectrum sharing MAC protocol for wireless ad hoc networks,” in Proc. of the IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN) November 8–11, 2005 203 - 213
Brown T. “An analysis of unlicensed device operation in licensed broadcast service bands,” in Proc. of the IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN) November 8–11, 2005 11 - 29
Shah M. A. , Safdar G. A. , Maple C. “DDH–MAC: a novel dynamic de–centralized hybrid MAC protocol for cognitive radio networks,” in Proc. of the IEEE Roedunet International Conference (RoEduNet) June 23–25, 2011 1 - 6
Čabrić D. , Mishra S.M. , Willkomm D. , Brodersen R. , Wolisz A. “A cognitive radio approach for usage of virtual unlicensed spectrum,” in Proc. of the 14th IST Mobile and Wireless Communications Summit June, 2005
Pawelczak P. , Prasad R.V. , Xia L. , Niemegeers I.G. “Cognitive radio emergency networks–requirements and design,” in Proc. of the IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN) November 8–11, 2005 601 - 606
Masri A. , Chiasserini C. , Perotti A. “Control information exchange through UWB in cognitive radio networks,” in Proc. of the 5th IEEE International Symposium on Wireless Pervasive Computing (ISWPC) May 5–7, 2010 110 - 115
Joshi Gyanendra Prasad , Kim Sung Won 2011 “Mitigating the control channel bottleneck problem in dense cognitive radio networks,” International Journal of the Physical Sciences 6 (20) 4832 - 4837
Theis N.C. , Thomas R.W. , DaSilva L. A. 2011 “Rendezvous for cognitive radios,” IEEE Transactions on Mobile Computing 10 (2) 216 - 227    DOI : 10.1109/TMC.2010.60
Bian K. , Park J. , Chen R. “A quorum–based framework for establishing control channels in dynamic spectrum access networks,” in Proc. of the ACM MobiCom September 2009 25 - 36
Joshi Gyanendra Prasad , Kim Sung Won “An enhanced synchronized MAC protocol for cognitive radio networks,” in Proc. of the IEEE 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM) September 23–25, 2011 1 - 4
Song Yi , Xie Jiang “Performance analysis of spectrum handoff for cognitive radio ad hoc networks without common control channel under homogeneous primary traffic,” in Proc. of the IEEE INFOCOM April 10–15, 2011 3011 - 3019
Song Yi , Xie Jiang 2012 “Prospect: A proactive spectrum handoff framework for cognitive radio ad hoc networks without common control channel,” IEEE Transactions on Mobile Computing 11 (7) 1127 - 1139    DOI : 10.1109/TMC.2011.140
Bian K. , Park J.–M. 2013 “Maximizing rendezvous diversity in rendezvous protocols for decentralized cognitive radio networks,” IEEE Transactions on Mobile Computing 12 (7) 1294 - 1307    DOI : 10.1109/TMC.2012.103
DaSilva L. A. , Guerreiro I. “Sequence–based rendezvous for dynamic spectrum access,” in Proc. of the 3rd IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN) October 14–17, 2008 1 - 7
Yang D. , Shin J. , Kim C. 2010 “Deterministic rendezvous scheme in multichannel access networks,” IET Electronics Letters 46 (20) 1402 - 1404    DOI : 10.1049/el.2010.1990
Shin J. , Yang D. , Kim C. 2010 “A channel rendezvous scheme for cognitive radio networks,” IEEE Communications Letters 14 (10) 954 - 956    DOI : 10.1109/LCOMM.2010.091010.100904
Montgomery H. L. 1971 “Topics in multiplicative number theory,” Lecture Notes in Mathematics 227
Zhang Y. , Li Q. , Yu G. , Wang B. “ETCH: Efficient channel hopping for communication rendezvous in dynamic spectrum access networks,” in Proc. of the IEEE INFOCOM April 10–15, 2011 2471 - 2479
Lin Z. , Liu H. , Chu X. , Leung Y.–W. “Jump–stay based channel hopping algorithm with guaranteed rendezvous for cognitive radio networks,” in Proc. of the IEEE INFOCOM April 10–15, 2011 2444 - 2452
Liu Hai , Lin Zhiyong , Chu Xiaowen , Leung Y.–W. 2012 “Jump–stay rendezvous algorithm for cognitive radio networks,” IEEE Transactions on Parallel and Distributed Systems 23 (10) 1867 - 1881    DOI : 10.1109/TPDS.2012.22
Lin Zhiyong , Liu Hai , Chu Xiaowen , Leung Yiu–Wing 2013 “Enhanced jump–stay rendezvous algorithm for cognitive radio networks,” IEEE Communications Letters 17 (9) 1742 - 1745    DOI : 10.1109/LCOMM.2013.071013.131029
Paul Rajib , Jembre Yalew Zelalem , Choi Young–June “Multi–interface rendezvous in self–organizing cognitive radio networks,” in Proc. of the IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN) April 1–4, 2014 531 - 540
Kim Junhyung , Park Gisu , Han Kijun 2014 “A rendezvous scheme for self–organizing cognitive radio sensor networks,” International Journal of Distributed Sensor Networks Article ID 315874 2014 1 - 10
Kim Junhyung , Baek Yongmi , Yun Jeongbae , Cho Kenchul , Lee Kyuchang , Han Jihun , Lee Suk–Gyu , Han Kijun “A repeated group sequence rendezvous scheme for cognitive radio networks,” in Proc. of the IEEE Spring Congress on Engineering and Technology (S–CET) May 27–30, 2012 1 - 4
Chang G. Y. , Huang J. F. 2013 “A fast rendezvous channel–hopping algorithm for cognitive radio networks,” IEEE Communications Letters 17 (7) 1475 - 1478    DOI : 10.1109/LCOMM.2013.060513.130471
Tessema Widist Bekulu , Kim Byeongung , Kim Junhyung , Cho Wooseong , Han Kijun 2014 “Channel Hopping Sequences for Rendezvous Establishment in Cognitive Radio Sensor Networks,” International Journal of Distributed Sensor Networks 2014 1 - 12    DOI : 10.1155/2014/872780
Reguera Vitalio Alfonso , Guerra Erik Ortiz , Souza Richard Demo , Fernandez Evelio M. G. , Brante Glauber 2014 “Short Channel Hopping Sequence Approach to Rendezvous for Cognitive Networks,” IEEE Communications Letters 18 (2) 289 - 292    DOI : 10.1109/LCOMM.2013.112713.132338
Guerra E.O. , Reguera V.A. , Souza R.D. , Brante G. , Fernandez E.M.G. 2014 “Simple role-based rendezvous algorithm for cognitive ad hoc radio networks,” Electronics Letters 50 (3) 182 - 184    DOI : 10.1049/el.2013.2994
Chang Guey-Yun , Teng Wen-Hung , Chen Hao-Yu , Sheu Jang-Ping 2014 “Novel channel-hopping schemes for cognitive radio networks,” IEEE Transactions on Mobile Computing 13 (2)    DOI : 10.1109/TMC.2012.260
Lu Yu , Liu Hai , Leung Yiu-Wing , Chu Xiaowen , Lin Zhiyong “Multiple radios for effective rendezvous in cognitive radio networks,” in Proc. of the IEEE International Conference on Communications (ICC) June, 2013 2857 - 2862
Htike Zaw , Hong Choong Seon , Lee Sungwon 2013 “The Life Cycle of the Rendezvous Problem of Cognitive Radio Ad Hoc Networks: A Survey,” Journal of Computing Science and Engineering 7 (2) 81 - 88    DOI : 10.5626/JCSE.2013.7.2.81
Liu H. , Lin Z. , Chu X. , Leung Y. W. “Ring–walk based channel–hopping algorithms with guaranteed rendezvous for cognitive radio networks,” in Proc. of the 2010 IEEE/ACM Int’l Conference on Green Computing and Communications & Int’l Conference on Cyber, Physical and Social Computing December, 2010 755 - 760
Lin Zhiyong , Liu Hai , Chu Xiaowen , Leung Yiu–Wing “Jump–stay based channel–hopping algorithm with guaranteed rendezvous for cognitive radio networks,” in Proc. of the IEEE INFOCOM April, 2011 2444 - 2452
Acharya Srijana , Joshi Gyanendra Prasad , Kim Sung Won “Routing protocol for prolonging network lifetime in ad hoc cognitive radio networks,” in Proc. of the 1st International Symposium on Advanced and Applied Convergence Korea (ISAAC) November, 2013