1 Introduction

A cognitive radio (CR) network is defined as a collection of wireless devices that intelligently adapt their operating parameters and efficiently coordinate to achieve their goals effectively. In the context of opportunistic spectrum access (OSA), to utilize the frequency spectrum more efficiently CRs operating in a network may need to exploit radio frequency channels temporarily unused by primary users (PUs), which are generally referred to as spectrum holes or white spaces.

Distributed coordination of multiple autonomous devices in multichannel CR networks has recently attracted strong interest [1–6]. This is mainly due to: (1) The need for developing flexible wireless networks where the independent devices can make autonomous decisions; and (2) The need for low complexity methods to find solutions to the efficient utilization of resources among a group of autonomous devices.

A widely studied class of problems in multichannel CR networks are those in which the aim of autonomous devices is to attempt to find one another, such as OSA radio rendezvous problem [7]. In OSA radio rendezvous problem, two or more radios attempt to find one another in a dynamic spectrum access (DSA) environment, where a set of frequency channels is shared opportunistically by CRs with multiple PUs.

In this paper, a complementary class is considered in which the aim of the CRs is to disperse [avoid one another so that the interference from other CRs cannot disturb the reception of a given desired signal (or message)]. For instance, when a particular channel is simultaneously sensed free by two or more autonomous CRs, and more than one of them decide to transmit on the channel, then a collision occurs. In such scenarios the aim of two or more autonomous CRs is to attempt to avoid one another by selecting those channels in which the likelihood of collisions is reduced. In Fig. 1, illustrated example of sensing order dispersion problem in multichannel CR networks is presented. In scenario (a) when two autonomous CRs (transmitter/receiver pairs) select the same sensing orders then both CRs find the same channel free they both attempt to transmit and collision occurs. However, in scenario (b) when they both select orthogonal sensing orders they never simultaneously sense the same channel and therefore never collide with each other.

Fig. 1
figure 1

An example of the sensing order dispersion problem

Full size image

This paper presents research relating to the use of adaptation based methods for sensing order dispersion among autonomous CRs. We evaluate and compare the performance of different sensing order selection strategies in terms of: (1) Probability of a successful transmission in a given time slot \(P_{s}\) for an autonomous CR; (2) Probability of finding a channel free in first step (given that the channel is free) \(P_{s,1}*\) for an autonomous CR; (3) Probability of a collision in a given time slot \(P_c\) for an autonomous CR; and 4) Average throughput (bits/s/Hz) of an individual CR.

The rest of the paper is organized as follows. Section 2 presents the background and a survey of related literature to our research, while Sect. 3 introduces the system setup. Section 4 presents methods for sensing order selection and also presents analytical results. Section 5 presents detailed simulation results, and Sect. 6 concludes and also presents some future directions to this research.

2 Background and Related Literature

To avoid continuously repeated conflicts among autonomous CRs, some method must be devised using which two or more autonomous CRs attempt to avoid one another by selecting those sensing orders that reduce the likelihood of collisions among one another. In Fig. 2, a taxonomy of autonomous sensing order selection methods consisting of two branches is presented: Adaptive and nonadaptive sensing order selection methods. Under nonadaptive methods, a simple method proposed in the literature is a random selection of sensing orders [3]. In this method, in each time slot, a sensing order (which may come from either the space of all permutations of \(N\) channel indices, or some subset thereof) is independently and randomly selected (with equal probability) by each CR and then channels are sensed by each CR according to its sensing order. However, the performance of the random selection method is limited by the collisions among the autonomous CRs [8].

Fig. 2
figure 2

Taxonomy of autonomous opportunistic channel access methods with relevant reference numbers added below each item in the tree

Full size image

In the other branch, adaptive sensing order selection methods, CRs employ adaptive randomization based on feedback (occurrence of collisions) to minimize the likelihood of collisions with one another [4, 8, 9]. Adaptations are in the autonomous choice, by CRs, of the channel sensing order \(\mathbb {O}\). Adaptive sensing order selection methods are of two types: Adaptive persistent sensing order selection and adaptive nonpersistent sensing order selection. Under adaptive nonpersistent sensing order selection, initially each CR independently and randomly (with equal probability) selects a sensing order (which may come from either the space of all permutations of \(N\) channel indices, or from a subset thereof). In the next time slots, a CR randomly (with equal probability) selects a new sensing order only if it has experienced a collision in the previous slot; otherwise, it retains the previously selected sensing order. In an alternative approach, adaptive persistent sensing order selection, proposed by us in [8], a CR maintains information regarding past successes (and failures) in using a particular sensing order. In Sect. 5, it is shown that the proposed adaptive persistent sensing order selection strategy enable the CRs to reduce the likelihood of collisions with one another, as compared to the other sensing order selection strategies.

In the classic dispersion problem [10], there are \(M\) players that prefer to be more dispersed over \(A\) actions. The problem is solved by Alpern in 2002 for \(M=A\) under a basic simple strategy, in which, initially, each player independently and randomly selects an action. In the next rounds, a player selects a new action uniformly at random (from the set of those actions where the number of players selecting an action is not one) only if it has experienced a collision (if some other player also chooses the same action as that player) in the previous round; otherwise, it retains the previously selected action.

Grenager et al. [11] have extended the basic simple strategy to work in the scenarios where \(M\ne A\). They proposed an extended simple strategy, where the player (after experiencing a collision) does not assigns uniform probabilities to all actions where the number of players selecting an action is not one. The works in [10, 11] assume that the players have perfect collision observations and also the proposed strategies require that each player knows the number of players selecting each action in a given round.

This paper models and evaluates the opportunistic channel access problem in distributed multichannel CR networks as a sensing order dispersion problem in which the agents are the autonomous CRs, the possible actions are the selection of the sensing orders, and the equilibrium state of the network is the independent arrival of CRs at collision-free sensing orders. However, the basic simple and extended simple strategies proposed in [10, 11] cannot be applied straightforwardly to the sensing order dispersion problem in distributed CR networks due to the following reason: The proposed strategies require that each player knows the number of players selecting each action in a given round. When there are multiple autonomous CRs operating in the network and there is no information exchange among them, the CRs do not have the knowledge of number of players selecting each action in a given round.

Adaptation and learning for efficient channel access in multichannel CR networks is an active research topic, see, for example, the works published in [4, 9, 12, 13]. Different from previous works [4, 9, 12–15], where adaptive channel allocation strategies were proposed for CRs employing a single-channel sensing policy, in this paper, an adaptive sensing order selection strategy for autonomous CRs employing a sequential-channel sensing policy is evaluated. Moreover, the works in [4, 9, 15] assume that the CRs are able to accurately estimate channel availability statistics. The proposed adaptation method here do not rely on the CRs being aware of the channel availability statistics, which in practice may be difficult to estimate within the required time scale.

Several optimal policies for the selection of channel sensing orders for the sequential channel sensing model are proposed in the literature. The works in [5, 16, 17] propose optimal policies for the selection of a channel sensing order \(\mathbb {O}\) for a single CR with perfect sensing observations. Unlike [5, 16, 17], this research takes into account competition for channels among multiple CRs. The selection of an optimal sensing order by a coordinator for a two-CR network is the topic of [2]. The coordinator determines the sensing orders to be adopted by the two CRs based on the estimated channel availability statistics and announces these sensing orders to the two CRs. While the two-user CR network with a coordinator is simple to implement, in practice a network comprising a large number of CRs would require significant signaling overhead to coordinate successful channel utilization. Moreover, in some practical scenarios, the CRs may be owned and managed by different service providers, requiring a sensing order selection strategy that does not rely on a common coordinator. A channel sensing order policy for distributed CR networks is proposed in [3]. However, this work assumes that CRs have knowledge of the gains for each channel. Based on this assumption, [3] proposes that each CR should sense channels in descending order of their achievable rates and should transmit in the first channel that is sensed free. Unlike [3], this research does not assume knowledge of the channel gains. Moreover, in contrast with [3], it also proposes and analyzes adaptive sensing order selection strategies to minimize conflicts among CRs when accessing available channels.

The works in [18–20] propose learning-based medium access control (MAC) techniques that discover collision-free schedules. However, since the proposed techniques are designed for traditional Time Division Multiple Access (TDMA) based MACs, these schemes do not consider the possibility that a channel may not be available (due to the presence of a PU) and that the transmitter must perform sensing before transmission to determine which channels are available. Therefore, the techniques proposed in [18–20] cannot be applied straightforwardly to distributed CR networks.

The radio rendezvous problem studied by [7] is, in a sense, the dual of the problem studied here. While [7] proposes the use of non-orthogonal sequences to increase the probability of rendezvous, in this paper methods are devised that increase the likelihood that CRs will independently arrive at collision-free sensing orders.

3 System Model

A network of \(M\) autonomous CRs and a set \(\mathcal {N}=\{1, 2, \ldots , N\}\) of channels is considered. A CR is allowed to make use of one of these channels when the channel is not occupied by a PU [21]. In Fig. 3, we illustrate two practical (but not limited to) scenarios for our studied problem. The PUs and CRs are both assumed to use a time slotted system, and each PU is either present for the entire time slot, or absent for the entire time slot [1, 4, 12]. Due to hardware constraints, at any given time each CR can either sense or transmit, but not both. Also, each CR can sense only one channel at a time. The probability of a PU being present and the probability of a PU being absent in a given channel are assumed to be unknown to the CRs. In each time slot, we denote the number of channels free from PU activity by \(K\), where \(1\le K\le N\), and we assume that the \(K\) free channels are randomly scattered over the set \(\mathcal {N}\). Also, the random scattering of \(K\) free channels in each time slot is independent from the other slots. The status of the \(i\)th channel, \(i\in \mathcal {N}\), in a given slot is a binary variable, \(B_i \in \{0, 1\}\), where \(0\) means the channel is free and \(1\) means the channel is occupied by a PU. Sensing observations of each CR are assumed to be perfect, as in other works in the literature [4, 12].

Fig. 3
figure 3

Two practical (but not limited to) example scenarios for our studied problem: a \(M=3\) cognitive small cell base stations (SCBSs) deployed by multiple independent wireless operators for small cell offloading in \(N=7\) potentially available channels that permit opportunistic use of spectrum; and b \(M=3\) autonomous transmitter/receiver pairs deployed for opportunistic use of spectrum in \(N=7\) potentially available channels

Full size image

The CRs use the beginning of each slot to sense the potential channels sequentially in some order \(\mathcal {O}\) (based on their OSA strategy as explained in Sect. 4) to find a channel that is free of PU (or other CR) activity. We refer to this as the sensing stage. The CR then accesses the first vacant channel it finds. The sensing stage in each slot is divided into a number of sensing steps. Each sensing step is used by a CR to sense a channel. If a CR finds a channel free in its \(k\)th sensing step, it transmits in that channel until the end of the slot. We refer to this as the data transmission stage. The durations of the sensing stage and data transmission stage are \(kT_{sense}\) and \(T\) -\(kT_{sense}\), respectively, where \(T_{sense}\) is the time required to sense each channel, T is the total duration of each slot and \(T >> T_{sense}\). The sensing order that a CR selects can either come from the space of all permutations of \(N\) channels, or some subset thereof. In this work, we analyze the performance of the presented adaptive strategies using these two alternatives. In Fig. 4 we illustrate an example of each of the two alternatives for \(N = 4\) potential channels. Please note that list of (important) symbols and abbreviations used in this paper and their meaning are given in Table 1.

Fig. 4
figure 4

Examples of sensing orders for \(N=4\) potential channels. In alternative a the space of all permutations of \(N=4\) channels is illustrated, while in alternative b a subset of that space (a Latin Square) is illustrated

Full size image
Table 1 List of (important) symbols and abbreviations used in this paper and their meaning
Full size table

4 Adaptive and Non-adaptive Sensing Order Selection Strategies

When distributed uncoordinated CRs have to search multiple potential channels for spectrum opportunities, they face competition from one another to access the channel. The end result of this competition is reduced CR throughput due to collisions among CRs that transmit in the same channel. However, if there is a way for distributed CRs to autonomously reach orthogonal sensing orders, collisions no longer occur. Orthogonal sensing orders are those in which two or more CRs never simultaneously sense the same channels and therefore never collide with one another. In this section, we present non-adaptive sensing order selection strategies. We also present adaptive strategies that enable the CRs to reduce the likelihood of collisions. Moreover, the presented adaptive strategies allow the CRs in a distributed CR network to autonomously arrive at orthogonal channel sensing orders (provided that the number of CRs is less than or equal to the number of potentially available channels).

4.1 Non-adaptive Strategies

4.1.1 RPS Strategy

In sensing order selection strategy based on random permutation selection (RPS), in each time slot, the indices of \(N\) potential channels, i.e., \(\{1, 2, \ldots , N\}\), are randomly permuted by each CR independently and then channels are sensed by each CR according to its own random permutation. A permutation \(\sigma ^{(i)}=\bigl (\sigma _1^{(i)}, \sigma _2^{(i)}, \ldots , \sigma _N^{(i)}\bigr )\) of the \(N\) channels describes the sensing order in which the \(i\)th CR visits channels in a given slot, and the matrix of all possible permutations is denoted as \(\Theta \). An example of all possible permutations is shown in Fig. 4.

4.1.2 LS-Strategy

In Latin Square (LS)-strategy, in each time slot a CR selects a sensing order (which is a row of a Latin Square) randomly from a predefined Latin Square. An example of all Latin square is shown in Fig. 4.

4.2 Adaptive Strategies

4.2.1 Randomize After Every Collision Strategy

Anandkumar in [4] proposed a learning scheme that employs adaptive randomization based on feedback (occurrence of collisions) for the CRs to arrive at orthogonal channel selections. Similarly, in this subsection, we propose a randomize after every collision strategy that utilizes adaptive randomization based on feedback for the CRs to arrive at orthogonal sensing orders. In this strategy, initially each CR randomly selects a sensing order. In the next time slots, a CR randomly selects a new sensing order only if it has experienced a collision in the previous slot; otherwise, it retains the previously selected sensing order.

The adaptive randomization based on feedback is implemented in the following way. The CR, upon transmitting in a free channel in the \(n\)th slot, receives an acknowledgement (ACK) on whether the transmission in that slot was successful. If an ACK is received (no collision occurred) then the CR retains the previously selected sensing order for the next time slot; otherwise, the CR randomly selects a new sensing order for the next slot. If no channel is found free in the current time slot then the CR retains the previously selected sensing order for the next slot. The basic idea is for CRs to randomize their sensing orders in a way that leads them to distributedly arrive at orthogonal sensing orders.

Randomize After Every Collision Using All Permutations (rand-AP)

Initially each CR randomly permutes the indices of the \(N\) potential channels and then senses channels sequentially according to the selected sequence. In the next time slot, a CR performs a random permutation only if it has experienced a collision in the previous slot. Otherwise, it retains the previously generated sequence for its sensing order. Note that to perform a random permutation on the channel indices \(\{1, 2, \ldots , N\}\) is equivalent to random selection, with equal probability, of a sequence from the space of all permutations of \(N\) channels.

We next propose an alternative in which each CR selects a sensing order from a subset of permutations of \(N\) channels. We find that the selection of sensing orders from a pre-determined subset (such as a Latin Square) of permutations of \(N\) channels leads to faster convergence to orthogonal sensing orders, as compared to when the sensing orders are selected from the large space of all permutations of \(N\) channels (see Fig. 6 for results).

Randomize After Every Collision Using a Pre-selected Latin Square (rand-LS)

In the randomize after every collision strategy using a pre-selected Latin Square (rand-LS), each CR employs a common pre-defined sequence matrix \(\Theta \) to determine the sensing order in which \(N\) potential channels are to be visited. The predefined matrix \(\Theta \) is a Latin Square, i.e., an \(N\) by \(N\) array of \(N\) channel indices in which every channel index occurs exactly once in each row and column of the array [22, 23]. An example of a Latin Square is illustrated in Fig. 4.

Initially each CR randomly chooses one of the rows of the matrix \(\Theta \) and the channels are sensed sequentially according to the given sensing order in the selected row. In the next slots, a CR randomly selects one of the rows of the matrix \(\Theta \) only if there is a collision in the previous slot. Otherwise, it retains the previously selected row of the matrix \(\Theta \) for its sensing order. Note that using a Latin Square two or more CRs will only collide if they select the same row of the matrix \(\Theta \).

Using the rand-LS strategy, initially each CR will select any of the \(N\) sequences of the matrix \(\Theta \) with probability \(1/N\). Let \(E\) represent the event that, in a given slot, all CRs arrive at orthogonal sensing orders (provided that the number of CRs is less than or equal to the number of potential channels) and \(P_E\) the probability of this event. For the two-CR scenario, the probability that the two CRs can arrive at orthogonal sensing orders in the initial time slot is given by

$$\begin{aligned} P_{E,ini}=1-\frac{1}{N} \end{aligned}$$
(1)

For the two CR scenario, \(P_{E}=P_{E,ini}\) due to the following reason. In a given slot, the two CRs can be either in non-orthogonal or orthogonal sensing orders. The network can be in a non-orthogonal sensing order state if two CRs select the same sequence, which means that in their \(k\)th step both CRs will find the same PU-channel free, will start transmitting in that channel and collide. In the case of collision, each CR will again select any of the \(N\) sequences with probability \(1/N\). Therefore, if they are in non-orthogonal sensing orders, they will remain in non-orthogonal sensing orders in the next slot with probability \(1-P_E\) (the probability that both select the same sequence), and will arrive at orthogonal sensing orders with probability \(P_E\) (the probability that they select different sequences). If they arrive at orthogonal sensing orders in a given slot, they will remain in that order with probability \(1\) (since they will retain the previously selected rows of the matrix \(\Theta \)).

The expected time for the two-CRs to reach orthogonal sensing orders, which we call the time-to-orthogonalize (TTO), is simply

$$\begin{aligned} E[\text {TTO}]=\frac{1}{P_E} \end{aligned}$$
(2)

For \(M>2\) when \((M-1)\le K \le N\), we are able to derive an upper bound for TTO.

Proposition 1

For \(M>2\) when \((M-1)\le K \le N\), \(E[\text {TTO}]\le \frac{N^M(N-M)!}{N!}\).

Proof

To obtain this upper bound, we consider a genie-added modification of autonomous arrival at orthogonal sensing orders. The idea of a genie-added modification is inspired by [4].

The probability that the \(M\) CRs can arrive at orthogonal sensing orders in the initial time slot is given by

$$\begin{aligned} P_{E, ini}=\left( \frac{1}{N}\right) ^M\biggl [\frac{N!}{(N-M)!}\biggr ] \end{aligned}$$
(3)

For large \(M\) when \((M-1)\le K \le N\), if two or more CRs select the same sequence then in their \(k\)th step both CRs will find the same PU channel free, will start transmitting in that channel and collide. For \((M-1)\le K \le N\), in each slot a genie checks if any two or more CRs selected the same sequence and collide, in which case the genie instructs all the CRs to randomly select a sequence from the pre-defined matrix \(\Theta \); otherwise, the genie notifies the CRs that they have arrived at orthogonal sensing orders.

When \((M-1)\le K \le N\), for the rand-LS strategy, any CR not experiencing a collision does not select a new sequence from the sequence matrix \(\Theta \). Hence, the probability that each CR selects a different sequence in any slot is either equal to the genie-added scheme (for instance, when all CRs select the same sequence in the previous slot) or it is higher than the genie-added scheme (for instance, when two or more CRs select different individual sequences). Due to this reason, \(P_E\) for the rand-LS when \((M-1)\le K \le N\) is at least (3) and \(E[\text {TTO}]\le \frac{N^M(N-M)!}{N!}\) \(\square \)

When \(K < (M-1)\) then any two or more CRs that select the same sequence may not always collide (since there are not enough free channels, two or more CRs that select the same sequence may not be able to find a free channel to transmit, as other CRs may have found the free channels in earlier steps and started transmitting). Therefore, for \(K<(M-1)\), when two or more CRs select the same sequence they may not randomize in every time slot. This may lead to slower convergence to orthogonal sensing orders as compared to the genie aided scheme (where all CRs randomize in every time slot, until they arrive at orthogonal sensing orders). Through extensive simulations we find that the rand-LS strategy converges to orthogonal sensing orders when \(K<(M-1)\). We will quantify this claim by simulation results in Sect. 5 (see Table 2).

Table 2 Expected number of time slots required by \(\gamma \)-persistent strategy to arrive at orthogonal sensing orders (E[TTO]) for different scenarios
Full size table

4.2.2 \(\gamma \)-Persistent Strategy

In this strategy, a CR uses two binary flags \(d\) and \(c\) that track its success and failures of accessing the channel in prior steps. Let \(\mathbf {S}\) denote the number of available sensing orders (which is either the space of all permutations of \(N\) channels, or some subset thereof) and let each CR maintain an \(\mathbf {S}\)-element probability vector \(p\) (i.e., all components are non-negative and add to 1). In Fig. 5 we illustrate the update of \(p_i\) (probability of selection of sensing order \(i\)) for different states of binary flags \(c\) and \(d\). It can be seen from Fig. 5 that the basic difference between the rand-LS strategy and the \(\gamma \) -persistent strategy is that in the rand-LS strategy a sensing order is randomly (with uniform probability) selected by a CR whenever it experiences a collision in the previous time slot. In contrast, in the \(\gamma \) -persistent strategy, using the binary flags \(c\) and \(d\) a CR takes into account whether it was successful, experienced a collision or it found all channels busy after the previous collision, and in case of a successful transmission or collision it persists with that sensing order even after a collision.

Let \(p_i\) represents the probability of choosing the \(i\)th sensing order. The \(\gamma \) -persistent strategy involves the following steps.

figure c

Explanation of Eqs. 4 and 5 for updating \(p_i\) and \(p_j\):

When a CR collides with another CR in the current time slot then when \(c=1\) and \(d=0\) means that using a sensing order the CR found all channels busy. Since the CR stays quiet, it cannot be sure whether it was the sole user of the sensing order in time slot (as it may happen that one or more other autonomous CRs also selected the same sensing order and found all channels busy). Since the CR cannot be sure whether it was the sole user of the sensing order in the next time slot, after a collision the CR will select a sensing order independently and randomly (with uniform probability).

Fig. 5
figure 5

Illustrations of update of \(p_i\), \(c\) and \(d\) using \(\gamma \)-persistent strategy for four different scenarios. In all four scenarios we assume that in the \((n-1)\)th slot the CR either collided or was successful in a transmission

Full size image

In all other cases, when a CR collides using a sensing order \(i\), it multiplicatively decreases the probability of picking that sensing order in the next time slots, redistributing the probability evenly across the other sensing orders. This helps in faster convergence as if the CR has not been successful in the previous time slot then it decreases the probability of selection of that sensing order as some other CR may have been successful. Moreover, if the CR has been successful in the previous time slot then in the next time slot instead of random selection it persists with that sensing order with higher probability.

5 Numerical Results

We evaluate the performance of the proposed \(\gamma \)-persistent strategy in terms of different performance metrics such as: (1) Average throughput of an individual CR; (2) Probability of finding a channel free in first step (given that the channel is free) for an autonomous CR; (3) Average number of unsuccessful transmissions experienced by a CR; and (4) Average total number of successful transmissions in the network. Using these performance metrics, we compare the performance of the proposed strategy with other distributed strategies and also with a centralized (optimal allocation) strategy. In optimal allocation, in each time slot, a centralized entity (with perfect knowledge of channel availability) fairly allocates \(K\) free channels (out of \(N\) potentially available channels) among \(M\) CRs. In this optimal allocation, probability of a successful transmission in a given time slot \(P_{s}\) for each CR is min\(\{1,K/M\}\). We perform simulations using \(R\) = 5,000 Monte Carlo runs for autonomous OSA. In each Monte Carlo run, the process of autonomous channel access among \(M\) CRs is evaluated for \(n\) time slots using a particular strategy.

5.1 When \(N\ge M\)

In Fig. 6a–c, for \(N=16\) potential channels we compare the performance of the proposed strategies in terms of the average total number of successful transmissions in a given slot under three different scenarios, when \(M<N\) and the number of free channels is half the number of CRs, when \(M<N\) and the number of free channels is equal to the number of CRs, and when \(M=N\) and the number of free channels is half the number of CRs. We also show the maximum number of CR transmissions that can happen in a time slot, given by \(\text {min}\{K, M\}\). Note that orthogonal sensing orders lead the CR network to achieve maximum number of successful transmissions.

Fig. 6
figure 6

Simulation results for the average total number of successful transmissions for the CR network in a given time slot for different strategies

Full size image

It can be seen from the three figures (Fig. 6a–c) that, without adaptation, the RPS-strategy outperforms the LS-strategy (see Sect. 4 for each strategy explanation). This is due to the fact that the RPS strategy increases the number of ways to visit \(N\) channels and therefore reduces the chances of collisions between CRs. However, when adaptation is employed then the randomize after every collision strategy takes fewer time slots to achieve maximum number of successful transmissions when CRs select a sensing order from a predefined Latin Square (rand-LS) as compared to when they select a permutation of the indices of \(N\) channels (rand-AP), see Fig. 6a, b. Figure 6a shows that, for \(N=16\) channels and \(M=8\) CRs, when the number of free channels is set to be half the number of CRs then the rand-LS strategy takes roughly 40 time slots to achieve the maximum number of successful transmissions. For the same scenario, i.e., \(N=16\) and \(M=8\) CRs, when the number of free channels is set to be equal to the number of CRs then the rand-LS strategy takes roughly 20 slots to achieve optimal probability of success (see Fig. 6b). When \(M\) is small as compared to \(N\), the rand-LS strategy has better performance as compared to the rand-AP strategy because when CRs select a sensing order from a predefined Latin Square then the probability of arriving at orthogonal sensing orders is higher as compared to when they select from all permutations of the indices of \(N\) channels.

When the number of CRs \(M\) is increased to be equal to the number of channels \(N\) then the performance of both rand-LS and rand-AP strategies degrade significantly (see Fig. 6c). The reason is as follows. When \(M\) is close to \(N\), the number of ways that CRs can orthogonalize as well as the probability that \(M\) CRs select different sensing orders is reduced as compared to when \(M\) is small as compared to \(N\). Due to this it takes the CRs long to arrive at orthogonal sensing orders.

In Fig. 6a–c, we also present the performance of the \(\gamma \) -persistent strategy for the case when CRs select a sensing order from a predefined Latin Square. The three figures (Fig. 6a–c) also show that for all three scenarios the \(\gamma \) -persistent strategy using a Latin Square (\(\gamma \)-persistent using LS) outperforms all the other proposed strategies. Particularly for the scenario when \(M=N\) \(\gamma \)-persistent using LS significantly outperforms all the other proposed strategies (see Fig. 6c). This performance gain comes from the fact that the \(\gamma \) -persistent strategy allows some CRs to stick to sensing orders even when they experience some collisions.

In Table 2 we compare rand-LS strategy with \(\gamma \)-persistent strategy in terms of expected time to orthogonal sensing orders (E[TTO]) for different scenarios. It can be seen in Table 2 that \(\gamma \)-persistent strategy requires significantly less number of time slots to arrive at collision free sensing orders. Table 2 also shows that the increased PU activity in the channels slows down the convergence process. This is due to the reason that when number of channels occupied by PUs is higher then any two or more CRs that select the same sensing order may not always collide (since there are not enough free channels, two or more CRs that select the same sequence may not be able to find a free channel to transmit, as other CRs may have found the free channels in earlier steps and started transmitting). Therefore, for high PU activity in channels when two or more CRs select the same sequence they may not randomize in every time slot. This leads to slower convergence to orthogonal sensing orders.

In Table 3 we compare rand-LS and LS-strategies with \(\gamma \)-persistent strategy in terms of \(P_{s,1}*\) as a function of time slots \(n\). Table 3 shows that in the initial time slot all strategies perform equally, however, as the process moves to next time slots then \(\gamma \)-persistent strategy in terms of \(P_{s,1}*\) clearly outperforms other strategies. This is due to the reason that the \(\gamma \)-strategy allows the CRs to minimize the likelihood of collisions and hence allows them to find a free channel with high probability in the first sensing step (given that the channel is free). This reduces the overhead of multiple sensing steps incurred by an autonomous. The reduced number of sensing steps required to find a channel free in turn increases the throughput per time slot of a CR.

Table 3 Probability of finding a channel free in first step (given that the channel is free) \(P_{s,1}*\) for an autonomous CR under different strategies
Full size table

5.2 When \(N< M\)

In Table 4, we compare the performance of different strategies in terms of: (1) probability of a successful transmission in a given time slot \(P_{s}\) for an autonomous CR; and (2) probability of finding a channel free in first step (given that the channel is free) \(P_{s,1}*\) for an autonomous CR under difficult cases when \(M >N\). It can be seen from Table 4 that when \(N=16\), \(M= 18\), and \(K=12\) our proposed \(\gamma \)-persistent strategy maximizes \(P_{s}\) and \(P_{s,1}*\) as compared to the rand-LS strategy and LS-strategy based selection of sensing orders. It can also be seen that using the \(\gamma \)-persistent \(P_{s,1}*\) is 0.98 for the studied scenario as the strategy allows the CRs to minimize the likelihood of collisions and hence allows them to find a free channel with high probability in the first sensing step (given that the channel is free). This reduces the overhead of multiple sensing steps incurred by an autonomous. The reduced number of sensing steps required to find a channel free in turn increases the throughput per time slot of a CR. It can also be seen that there is some loss in the performance of the \(\gamma \) persistent strategy as compared to the optimal selection of sensing orders, as when \(M >N\), it is not possible for all CRs to autonomously select collision-free sensing orders.

Table 4 In \(n=200\) time slots, probability of a successful transmission in a given time slot \(P_{s}\) for an autonomous CR, and probability of finding a channel free in the first step (given that the channel is free) \(P_{s,1}*\) for an autonomous CR under different strategies. In an all cases, \(N=16\), \(M= 18\), and \(K=12\)
Full size table
Table 5 In \(n=200\) time slots, probability of collision in a given time slot \(P_c\) for an autonomous CR for different strategies and under different scenarios
Full size table

In a given time slot, an autonomous CR can be unsuccessful in communication either due to a collision with other CRs or it can be unsuccessful in communication as all channels are occupied by either a PU or another CRs (who found the free channels before that CR). In Table 5 it can be seen that compared to rand-LS and LS-strategy, the \(\gamma \)-persistent strategy reduces the likelihood of collisions among CRs which in turn reduces the transmission attempt costs of an autonomous CR.

5.3 Average Throughput

Let \(X\) be a random variable representing the number of sensing steps within a time slot until a CR is successful in finding a channel free from PU and other CR activity (given that the CR is successful). Note that, with a constant time slot of duration \(T\), the duration of successful data transmission in each slot is a function of \(X\). At the end of each slot, the instantaneous throughput \(C(\mathrm {X})\) achieved by a CR is given by

$$\begin{aligned} C(\mathrm {X})={\left\{ \begin{array}{ll} \left( 1-\frac{{\mathrm {X}}T_{sense}}{T}\right) R,&{}\text {if successful}\\ 0&{}\text { otherwise}\end{array}\right. } \end{aligned}$$
(6)

where \(R\) represents the transmission rate of each CR to its receiver when the channel is available. The average throughput achieved by a CR is given by

$$\begin{aligned} E[C]=P_{s} \sum _{k=1}^N \left( 1-\frac{{\mathrm {k}}T_{sense}}{T}\right) P[{\mathrm {X}}=k\mid s] R, \end{aligned}$$
(7)

where \(P_{s}\) represents the probability that a CR finds a channel free from both primary and other CR transmissions in a given slot and \(P[{\mathrm {X}}=k\mid s]\) represents the probability that the CR is successful in the \(k\)th sensing step (given that the CR is successful). Note that if \(N\) is larger than \(T/T_{sense}\), then the CR does not have time to visit all channels within a time slot. In that case, \(P[X=k\mid s] = 0\) for \(k > T/T_{sense}\), and the equation still holds. However, for simplicity and also for practical reasons, we assume that \(N < T/T_{sense}\). In Fig. 7, we evaluate the performance of \(\gamma \)-persistent strategy in terms of average throughput of an autonomous CR as a function of time slot \(n\). It can be seen that the \(\gamma \)-persistent strategy significantly outperforms other strategies.

Fig. 7
figure 7

Average throughput (bits/s/Hz) of an individual CR as a function of time slots \(n\) with \(T=1\) unit (length of time slot), \(T_{sense}=0.01\) unit (time to sense a single channel), \(R=1\) (bit/s/Hz) (see Eq. 7), \(N=M=16\), and \(K=8\)

Full size image

5.4 Parameter \(\gamma \)

To analyze the impact of parameter \(\gamma \) on the performance of \(\gamma \)-persistent strategy, we vary the value of parameter \(\gamma \) in Fig. 8. It can be seen in Fig. 8 that the \(\gamma \)-persistent strategy requires the least number of time slots to achieve the maximum number of transmissions when the value of \(\gamma \) is set to 1. Setting \(\gamma =1\) means that when a CR transmits successfully in a given slot using a sensing order then the CR persists with that sensing order in the next time slots. In other words, when two or more CRs collide using a sensing order then the CR that has been once or more successful in the previous slots (using the same sensing order) keeps that sensing order and the other colliding CRs randomly pick a sensing order in the next slot. Moreover, when the value of \(\gamma \) is set to zero then the performance of the strategy degrades as compared to the randomize after every collision strategy (see Fig. 8).

Fig. 8
figure 8

Performance comparison of \(\gamma \) -persistent strategy with rand-LS strategy when values of \(\gamma \) are varied between 0 and 1. In all scenarios CRs select a sensing order from a predefined Latin Square

Full size image

6 Concluding Remarks and Future Directions

In this research, using different performance evaluation metrics we evaluate and compare autonomous sensing order selection strategies for a distributed CR network. We show that compared to random selection of sensing orders and also compared to nonpersistent based adaptive sensing order selection our proposed \(\gamma \)-persistent strategy maximizes the average throughput of an autonomous CR and enables the CRs to arrive all collision free sensing orders. We also show that when the number of CRs is greater than the number of potentially available channels then although our proposed strategy outperforms other autonomous strategies, however, there is some loss in its performance as compared to the optimal selection of sensing orders by a centralized entity. This is due to the reason that when the number of CRs is greater than the number of potentially available channels then it is not possible for all CRs to autonomously select collision-free sensing orders in a given time slot.

There are several challenges relating to opportunistic multichannel access in distributed CR networks that are yet to be explored. The research presented in all the discussed works analyze adaptive and non-adaptive strategies for CRs with the same world view. However, in practice the CRs may have different world views. An example case for the CRs with different world views is the scenario where CRs have asymmetric interference links, i.e., when CR \(i\) interferes with CR \(j\) but not vice-versa. Due to different geographical locations of PUs and CRs, CRs may have different view of PU channel occupancy. Moreover, it may happen that the set of available channels differs from one CR to another.