01.03.2014  Ausgabe 2/2014 Open Access
Distributed and Centralized Schemes for Channel Sensing Order Setting in Multiuser Cognitive Radio Networks
 Zeitschrift:
 Wireless Personal Communications > Ausgabe 2/2014
1 Introduction
Conventional wireless communication systems employ static spectrum allocation strategies, which results in both spectrum scarcity and spectrum underutilization. Cognitive radio (CR) is a promising technology to solve these spectrum inefficiency problems [
1]. In cognitive radio networks, the CR users (also referred to as secondary users, SUs) can select and reuse some of the spectrum bands/channels opportunistically when the licensed users (also referred to as primary users, PUs) are not active in these channels. In order to find available spectrum opportunities and guarantee the smooth communication of the primary system, SUs need to sense the spectrum channels before transmission [
2]. For ease of implementation and considering hardware constraints, we assume that SUs can sense and transmit on only one channel at a time.
Since there are a number of potential channels available, SUs can choose one channel to sense and transmit on it for the rest of the time slot if it’s available or wait until next time slot otherwise; or SUs can sense the channel sequentially till an available channel is found and transmit on it for the rest of the time slot. For the former case, Zhao et al. [
3] and [
4] proposed optimal dynamic access strategies using periodic sensing based on Markov decision process. In the latter case, SUs sense the channels sequentially, and after each sensing, a decision on whether to continue sensing or to start transmission is made according to the channel availability and channel quality. In this case, SUs can exploit multichannel diversity by opportunistically selecting a good channel for transmission. Sequential sensing brings a new problem: channel sensing order setting, which means that the SUs need to decide which channel to sense first. Channel sensing order is important for SUs to find a good available channel as fast as possible, and better channels and shorter sensing time will lead to higher throughput. Multiarmed bandit problems are used in [
5–
7] to solve the channel sensing ordering problems in uncertain environments, and polynomial regrets are obtained. In this paper, we assume that the primary users’ activity and channels’ achievable rates are known a priori to SUs. The authors in [
8] and [
9] derive the optimal sensingsequence for channels with homogeneous capacities, which means that the intrinsic features of a multipath channel are not taken advantage of. Dynamic programming is used in [
10] and [
11] to obtain the optimal channel sensing order for a single secondary user pair, heterogeneous channel capacities are considered. In the above researches only one sensing order is considered. However in this paper, we try to solve the sensingorder problem in a general multiuser network where multiple autonomous CRs have to search multiple channels according to their own sensing orders. Closely related to our research work here are [
12–
14]. However [
12] only considered the twouser case. Cheng and Zhuang [
13] only considered channel achievable rate in designing sensing orders. And Khan and Lehtomaki [
14] proposed to select sensing orders from a Latin Square which is not optimal. Compared to the above works, we comprehensively consider the channel availability, channel achievable rate, multiuser diversity and collisions among CR users in designing channel sensing orders for multi users.
Anzeige
The main contributions of our paper are as follows. In the distributed case, with limited information exchange among SUs, we derive a novel metric which exploits the multiuser diversity simply and efficiently. Using this metric we have modified the
potential function of traditional singleuser multichannel greedy search algorithm for multiuser case. In the centralized case, we first get the expected throughput of a CR network for given sensing orders of all users. Then we propose a suboptimal greedy search algorithm which has much lower complexity than the bruteforce search. The mutual collisions among SUs are formulated as a loss to the network throughput. Plenty of simulations are carried out to investigate the impacts of number of channels, sensing errors, number of SUs, etc. The efficacies of the proposed schemes are validated by comparisons with existing works.
The remainder of this paper is organized as follows. The related works and our motivation are presented in Sect.
2. Section
3 describes the system model. Distributed and centralized channel sensingorder setting schemes are discussed in Sects.
4 and
5, respectively. The performance of the proposed methods is evaluated in Sect.
6. Finally, conclusions are presented in Sect.
7.
2 Related Works
In the literatures, the channel sensing order setting problems have been discussed for both single user and multiuser cases. The optimal sensing order setting problem is formulated under the multiarmed bandit framework in [
5–
7], where a balance is found between longterm channel exploration and shortterm channel exploitation to optimize the total throughput throughout the entire transmission of the SUs. However in this paper we focus on exploiting the instantaneous channel condition under the assumption that the statistics of channel availability and channel achievable rate are known a priori. The authors in [
8] and [
9] proposed an efficient sensing order setting scheme that incurs a small opportunity–discovery delay. Channels are sensed at the descending order of channel idle probabilities, which is also referred to as the intuitive sensing order. However the multichannel diversity is not taken advantage of. In [
15], it is shown that fluctuating nature of heterogeneous spectrum bands is crucial in spectrum decision. In [
10], the optimal channel sensing order and the related stopping rule is derived for a singleuser case, with an assumption that recall (i.e., a previously sensed channel can be accessed) and guess (i.e., an unsensed channel can be accessed) are allowed. Dynamic programming is used in [
11] to obtain the optimal channel sensing order considering heterogeneous channel capacities and channel availabilities jointly. The optimal stopping rule is well studied in [
16] and [
17] under the homogeneous channel utilization scenario, however the optimal sensing order setting problem is not solved. In [
18] sensing order and power allocation are jointly considered to achieve the maximum energy efficiency. Our previous study in [
19] proposed sensing order setting schemes for both realtime and besteffort applications. However in the above researches the sensing ordering problem is discussed only for singleuser case. In this paper we focus on the sensing ordering problem for multiuser case. In a multiuser network, two new factors will influence the channel utilization and network throughput: collision (i.e., two or more SU pairs sense and transmit in the same channel at the same time) and useless sensing (i.e., a SU senses a channel which is being used by another SU).
The authors in [
12] discussed the sensing ordering problem for a twouser case, it is shown that the traditional stopping rule is not optimal anymore. Designing an optimal stopping rule for multiuser case is nearly impossible. So in our work, we focus on sensing ordering problem but ignore the stopping rule design. In [
13] the channels are sensed according to the descending order of their achievable rates, where the primary free probabilities are not considered. A novel metric comprehensively incorporating the channel availability and collision among SUs is proposed in [
20], based on which the sensing order is obtained for each user in a distributed manner. However the metric is designed improperly as it is mutable and uncertain in the process of designing a sensing order. In [
21], a systematic neural networkbased optimization approach is developed to set proper sensing order to maximize the average throughput of a CR network. However the training process may be too long when the number of SUs or channels is large, which is not suitable for adaption to changing environment. An adaptive persistent sensing order selection strategy is proposed in [
14], sensing orders are selected from a Latin Square matrix. It is assumed that none of the SUs can gain any reward for the rest of the slot if a collision happens. However, under our framework, the collision can be detected by the SUs using a probing signal, and then the SUs can keep sensing the rest spectrum opportunities. So, though the strategy in [
14] enables the CRs to converge to collisionfree channel sensing orders, the network throughput is not optimized. In this paper, aiming to maximize the average SU throughput and minimize collisions, two greedy search algorithms are proposed to obtain the sensing orders in both centralized and distributed manners.
Anzeige
3 System Model
We consider a CR network with
\(M\) cognitive transmitter/receiver pairs and a set
\(\mathbf{N}=\{1,2,\ldots ,N\}\) of channels, and we only consider the case that
\(M\le N\) (for the case that
\(M>N\), an admission control scheme similar to [
22] can be adopted). The cognitive users are synchronous with each other and they are synchronous with the primary network. Time is partitioned into slots of duration
\(T\), and each channel is either busy (i.e., with primary activities) or free (i.e., no primary activities) for an entire time slot. We assume that the channel availability probability and channel achievable rate are known to the SUs at the beginning of each time slot.
In each timeslot, the source node of a SU pair needs to scan (sense and probe) the channels according to its sensing sequence before transmission. Denote
\(\tau \) as the time duration needed for scanning one channel, which satisfies
\(N\tau <T\). If a channel is found to be free, the SU pair transmits in that channel. However, if no available channel is found after scanning all
\(N\) channels, the SU pair stays silent for the remaining duration of that time slot. The slot structure is depicted in Fig.
1, where after sensing the first
\((k1)\) channels to be busy, the SU finds the
kth channel is free and transmits on it for the reminder of that time slot. Thus the period of time spent on channel scanning and that on data transmission are
\(k\tau \) and
\(Tk\tau \), respectively. Define the
effectiveness of a slot as the ratio of the transmission phase length to the slot length. Therefore, if a user stops at the
kth channel in its sensing order, the effectiveness is
\(c_k =1k\tau /T\).
×
As depicted in Fig.
1, after each sensing, a probing phase is carried out. In specific, once a channel is sensed to be free, the SU transmitter transmits a channel probing packet (CPP) to its receiver so as to estimate the channel gain of this transmission link. Then the SU receiver feeds the estimated channel gain back to the transmitter with a probing feedback packet (PFP). It is assumed that the SU transmitter and its receiver are always synchronized through a centralized coordinator (or a dedicated control channel for the distributed case), so that they always tune to the same channel for sensing, probing and transmission. A receiver will not send back a PFP in two cases: (1) The receiver senses a channel to be busy, and (2) Probing collision happens among multiple transmitters. In both cases the transmitter will skip the channel and keep sensing. In the second case, multiple transmitters simultaneously sense the same channel to be free and transmit a CPP on that channel. Thus a probing collision happens and none of them can use that channel, a spectrum opportunity is wasted.
In this paper, we consider sensing order setting problem for both distributed and centralized cases. In the distributed case, each SU pair should determine their own sensing order by themselves. Before carrying out sensing and probing, a negotiation phase is needed where the SUs exchange their primary free probability and channel achievable rate information with neighbors on a common channel. In the centralized case, a coordinator exists in the cognitive radio network. According to estimated primary free probabilities and channel achievable rates, the coordinator determines the sensing orders of the SU pairs and announces the sensing orders to the pairs. Thus the coordinator needs to determine a sensing matrix
\(\mathbf{S}\) with dimensions of
\(M\times N\), in which the
\(m\)th row
\(\mathbf{S}_\mathbf{m} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,N}\}\) is the channel sensing order dedicated to the
\(m\)th SU pair. Each row
\(\mathbf{S}_\mathbf{m} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,N} \}\) is a permutation of the set
\((1,2,\ldots ,N)\), where
\(S_{m,k}\) denotes the channel that user
\(m\) senses at the
\(k\)th position in its sensing order. In this study, we assume that each SU pair can potentially see different primary user occupancy behavior on each channel due to their geographic dispersion. And we focus on the simplest completeinterference case when all secondary users interfere with each other and must therefore each be allocated distinct channels. The same assumption is also adopted in [
7] and [
20], and is discussed in [
23]. We use a
\(M\times N\) matrix
\(\mathbf{P}_\mathbf{I} \) to denote the primary free probabilities where its element
\(P_{m,i} \) is the primary free probability of channel
\(i\) for user
\(m\), and
\(P_{m,i}\) is uncorrelated with
\(P_{l,i}\) for
\(m\ne l\); and a
\(M\times N\) matrix
\(\mathbf{R}\) to denote the channel achievable rates where its element
\(R_{m,i}\) is the achievable rate of channel
\(i\) for user
\(m\), and
\(R_{m,i}\) is uncorrelated with
\(R_{l,i}\) for
\(m\ne l\). We assume that
\(\mathbf{P}_\mathbf{I}\) and
\(\mathbf{R}\) are known to the users a priori, the estimation of them is not our concern. We ignore the effect of the missed detection (due to strict protection of primary network) and only consider the effect of false alarm
\(P_f\). Thus we define the unconditional probabilities matrix that the SUs determine that the channels are idle as
\({\varvec{\uptheta }}\) with its element
\(\theta _{m,i} =P_{m,i} (1P_f )\) representing the probability that user
\(m\) determines channel
\(i\) to be free.
4 Sensing Order Selection for Distributed Case
4.1 Greedy Search Algorithm for Single User Scenario
We first briefly introduce the main idea of the greedy search algorithm for single user scenario in this section. Consider a single user pair
\(m\) with its aim to maximize the average throughput. Let
\(\mathbf{S}_\mathbf{m}^\mathbf{0} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,N}\}\) be the optimal channel sensing order of user
\(m\). The expected throughput using this optimal sensing order can be obtained as
where we define
\(\theta _{S_{m,0} } =0,\,\theta _{S_{m,k} } \prod \nolimits _{i=1}^k {\left( {1\theta _{S_{m,i1} } } \right) }\) is the probability that the user stops at the
kth channel, and
\(c_k R_{s_{m,k} }\) is the obtained normalized throughput if the user transmits in the
kth channel.
$$\begin{aligned} U_m^0 =\sum \limits _{k=1}^N {\left[ \,{\prod \limits _{i=1}^k {\left( {1\theta _{S_{m,i1} } } \right) }}\right] }\theta _{S_{m,k}} c_k R_{S_{m,k}} \end{aligned}$$
(1)
The optimal sensing sequence can also be expressed as
\(\{L_{k1} ,S_{m,k} ,S_{m,k+1} ,L_{k+2}^c \}\), where
\(L_{k1} =(s_{m,1} ,\ldots ,s_{m,k1} )\) is the former part of the sequence and
\(L_{k+2}^c =(s_{m,k+2} ,\ldots ,s_{m,N} )\) is the later part. Let
\(\mathbf{S}_\mathbf{m}^{\varvec{*}}\) be the counterpart of
\(\mathbf{S}_\mathbf{m}^\mathbf{0}\) constructed by switching the order of
kth and
\(k+1\)th channels,
\(\mathbf{S}_\mathbf{m}^{\varvec{*}} =\{L_{k1} ,S_{m,k+1} ,S_{m,k} ,L_{k+2}^c \}\). Since
\(\mathbf{S}_\mathbf{m}^\mathbf{0} \)is the optimal sensing order, the expected throughput
\(U_m^0 \) should be no less than that of its counterpart
\(U_m^*,\,U_m^0 \ge U_m^*\). We have:
Thus we define the
potential function of channel
\(i\) at the
kth round in a sensing order for user
\(m\) as:
which satisfies that:
Then a greedy search algorithm can be obtained as follows:
$$\begin{aligned} U_m^0 \!\!U_m^*&= \prod \limits _{i=1}^{k1} {\left( {1\!\!\theta _{S_{m,i}}} \right) } \{\theta _{S_{m,k}} (T\!\!k\tau )R_{S_{m,k}}\!+\!\left( {1\!\!\theta _{S_{m,k}}}\right) \theta _{S_{m,k+1}} (T\!\!(k+1)\tau )R_{S_{m,k+1}}\nonumber \\&\quad \,\theta _{S_{m,k+1} } (Tk\tau )R_{S_{m,k+1} } \left( {1\theta _{S_{m,k+1} } } \right) \theta _{S_{m,k} } (T(k+1)\tau )R_{S_{m,k} } \}\ge 0\nonumber \\&\Rightarrow \frac{R_{S_{m,k} } }{\tau /\theta _{S_{m,k} } +T(k+1)\tau }\ge \frac{R_{S_{m,k+1} } }{\tau /\theta _{S_{m,k+1} } +T(k+1)\tau } \end{aligned}$$
(2)
$$\begin{aligned} g_m (i,k)=R_{m,i} /(\tau /\theta _{m,i} +T(k+1)\tau ) \end{aligned}$$
(3)
$$\begin{aligned} g_m (i,k)\ge g_m (j,k)\Rightarrow U_m (\{L_{k1} ,i,j,L_{k+2}^c \})\ge U_m (\{L_{k1} ,j,i,L_{k+2}^c\}) \end{aligned}$$
(4)
Let
\(L_{k1}\) be the set of already chosen channels, at the initial step of the algorithm
\((k=1),\,L_0 =\varnothing \). For finding the
kth channel in the optimal sensing sequence, the channel
\(i\) with the largest potential function
\(g_m (i,k)\) is chosen, where
\(i\in \{1,2,\ldots ,N\}\backslash L_{k1} \). Till
\(k=N\), the whole optimal sequence is obtained.
4.2 Greedy Search Algorithm for Multiuser Scenario
When multiple autonomous SUs search multiple potentially available channels synchronously, then from an individual SU’s perspective one of the following three events will happen in each sensing step [
14]: (1) The SU senses a channel to be free, then it sends a probing signal on this channel to its receiver and successfully receives the response, the SU then has the channel for itself for the remainder of the time slot; (2) The SU senses a channel to be busy (occupied by primary users or another SU), then it keeps quiet for the probing phase and keeps looking in the next sensing step; (3) The SU senses a channel to be free, then it sends a probing signal, but so does at least one other SU; thus a collision occurs, none of these SUs can use this channel and they all skip into next sensing step, a spectrum opportunity is wasted. From above discussions, we can conclude that the optimal sensing order setting of an individual SU is not only affected by the channel free probabilities and channel achievable rates of its own perspective, but also affected by the sensing orders of other SUs.
For example, consider a CR network with
\(N=3\) channels and
\(M=2\) users, the scanning time for each channel is 0.1, slot duration is 1, and the achievable rate for each channel is 1. The channel free probabilities for user 1 are
\(\theta _{1,1} =0.9,\,\theta _{1,2} =0.5\) and
\(\theta _{1,3} =0.2\); the channel free probabilities for user 2 are
\(\theta _{2,1} =0.7,\,\theta _{2,2} =0.4\) and
\(\theta _{2,3} =0.6\). If the users search their sensing orders individually and don’t consider the other user’s sensing order, the sensing order setting of the two users is (1,2,3) for user 1 and (1,3,2) for user 2, and the total throughput can be calculated as
\(0.5576+0.5755=1.1331\). However By bruteforce search, we can obtain the optimal sensing order setting of the two users, which is (1,2,3) for user 1 and (3,1,2) for user 2, and the total throughput can be calculated as
\(0.8528+0.6614=1.5142\). We can see that in the former sensing order setting, both users sense channel 1 at their first sensing step. So a collision will happen with a high probability
\(\theta _{1,1} \theta _{2,1} =0.63\) (when both users sense channel 1 to be free and send a probing signal), the spectrum opportunity of channel 1 is wasted which causes the decrease of the network throughput.
Although it is possible that a SU can obtain the optimal channel sensing order by bruteforce search individually with the knowledge of the channel free probabilities and channel achievable rates of its own and all other SUs, the complexity of bruteforce search is
\(O((N!)^{M})\) if the complexity to calculate the expected network throughput with a specific sensingorder setting is
\(O(1)\), which is unacceptable for an individual user due to hardware constraint. Thus in this section we try to give a simple yet efficient greedy search algorithm for the distributed network scenario by modifying the
potential function in Eq. (
3) as follows:
where
\(\mathbf{M}\) and
\(\mathbf{N}\) are the sets of all SUs and potential channels,
\(g_m (i,k)\) is presented as in Eq. (
3).
\(g_m (i,k)\frac{1}{M1}\sum \nolimits _{l=\mathbf{M}\backslash m} {g_l (i,k)} \) represents the relative advantage of channel
\(i\) being used by user
\(m\) at its
kth sensing step compared with which being used by other users;
\(g_m (i,k)\frac{1}{N1}\sum \nolimits _{j=\mathbf{N}\backslash i} {g_m (j,k)} \) represents the relative advantage of channel
\(i\) being used by user
\(m\) at its
kth sensing step compared with other channels being used by user
\(m.\,g_m (i,k)\frac{1}{M1}\sum \nolimits _{l=\mathbf{M}\backslash m} {g_l (i,k)}\) guarantees that channel
\(i\) should be first allocated to user
\(m\) which can get a larger reward than other users;
\(g_m (i,k)\frac{1}{N1}\sum \nolimits _{j=\mathbf{N}\backslash i} {g_m (j,k)}\) guarantees that user
\(m\) should first choose the channel
\(i\) which can bring larger reward than other channels.
$$\begin{aligned} g_m^{\mathrm{mod}} (i,k)=(g_m (i,k)\frac{1}{M1}\sum \limits _{l=\mathbf{M}\backslash m} {g_l (i,k)} )+(g_m (i,k)\frac{1}{N1}\sum \limits _{j=\mathbf{N}\backslash i} {g_m (j,k)} )\nonumber \\ \end{aligned}$$
(5)
Using this
modified potential function, the greedy search algorithm for multiuser case in distributed network scenario can be stated as follows:
Let’s briefly explain how this
modified potential function works in the former mentioned example. We have
\(g_1^{\mathrm{mod} } (1,1)=0.25,\,g_1^{\mathrm{mod} } (2,1)=0.1142\) and
\(g_1^{\mathrm{mod} } (3,1)=0.5449;\,g_2^{\mathrm{mod} } (1,1)=0.0301,\,g_2^{\mathrm{mod} } (2,1)=0.1428\) and
\(g_2^{\mathrm{mod} } (3,1)=0.2933\). For the first channel in the sensing order, user 1 will choose channel 1 and user 2 will choose channel 3 (though from user 2’s individual perspective channel 1 is the best and should be chosen first, our method can choose another but still good one to avoid the collision), finally our greedy search method will get the same optimal sensing orders as bruteforce search does.

Step 1: Negotiation. Users exchange their channel free probability and channel achievable rate information, \({\varvec{\uptheta }}\) and R, with their neighbors on a common control channel;

Step 2: Initialization. \(k=1\), the set of already chosen channels of user \(m\) is \(L_m^{k1} =L_m^0 =\varnothing \).

Step 3: Find the kth channel in the optimal sensing order, \(S_{m,k} =\mathop {\arg \max }\limits _{i\in \{1,2,\ldots ,N\}\backslash L_m^{k1} } g_m^{\mathrm{mod} } (i,k)\). And \(L_m^{k1} =L_m^{k1} \cup \{S_{m,k} \}\).

Step 4: If \(k=N\), end; else, \(k=k+1\), go to step 3.
From the procedure of the algorithm, the complexity of the greedy search algorithm is
\(N+\left( {N1} \right) +\cdots +1=N\left( {N1} \right) /2\) if the complexity of calculating one
modified potential function is
\(O(1)\), which is much less than the brute force search
\(O((N!)^{M})\).
5 Sensing Matrix Setting for Centralized Case
5.1 Problem Formulation
In our centralized scenario, a coordinator exists to help the SUs to set their channel sensing orders. The coordinator needs to decide a
\(M\times N\) sensing matrix
\(\mathbf{S}\) to maximize the network throughput, in which the
mth row
\(\mathbf{S}_\mathbf{m} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,N}\}\) is the channel sensing order dedicated to the
mth SU pair. Each row
\(\mathbf{S}_\mathbf{m} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,N}\}\) is a permutation of the set
\((1,2,\ldots ,N)\), where
\(S_{m,k}\) denotes the channel that is at the
kth position in the sensing order of user
\(m\). For a given sensing matrix, let
\(\phi _{m,k} \) denotes the probability that user
\(m\) successfully stops and transmits at its
kth sensing step. Let
\(p(i,\mathbf{S}_\mathbf{m} )\) denotes the position of channel
\(i\) in user
\(m\)’s sensing order
\(\mathbf{S}_\mathbf{m}\).
We can note that given a sensing matrix, for each channel
\(S_{m,k} \) there are four possible cases might occur: (1) The channel is neither in the prior positions
\(({<}k)\) nor in the
kth position of any other users’ (other than user
\(m)\) sensing order; (2) The channel is not in the prior positions
\(({<}k)\) of any other users’ sensing order but is in the
kth position of some other users’ sensing order; (3) The channel is in the prior positions
\(({<}k)\) of some other users’ sensing order but is not in the
kth position of any other users’ sensing order; (4) The channel is in the prior positions
\(({<}k)\) and in the
kth position of some other users’ sensing order. By analyzing the above four possible cases of a channel,
\(\phi _{m,k}\) can be obtained as follows:
For
\(k=1\),
For
\(k>1\),
where
\((1\sum \nolimits _{j=1}^{k1} {\phi _{m,j} )\theta _{m,S_{m,k} } } \) is the probability that user
\(m\) reaches the
kth step and senses channel
\(S_{m,k}\) to be free.
\(l\) satisfies
\(l\in \{1,2,\ldots ,M\}\backslash m\) and
\(p(S_{m,k} ,\mathbf{S}_\mathbf{l} )=k\), is the user (other than user
\(m\)) that selects channel
\(S_{m,k}\) at the
kth position of its sensing order;
\(l^{*}\) satisfies
\(l^{*}\in \{1,2,\ldots ,M\}\backslash m\) and
\(p(S_{m,k} ,\mathbf{S}_{\mathbf{l}^{*}} )<k\), is the user (other than user
\(m\)) that selects channel
\(S_{m,k}\) at the prior
\(k1\) positions.
\(\prod \nolimits _l \left( {(1\sum \nolimits _{j=1}^{k1} {\phi _{l,j} )(1\theta _{l,S_{l,k} } )+\sum \nolimits _{j=1}^{k1} {\phi _{l,j} } } } \right) \) is the probability that channel
\(S_{m,k}\) is not simultaneously sensed to be free (or be sensed) by other users (other than user
\(m\)),
\(\sum \nolimits _{j=1}^{k1} {\phi _{l,j} }\) is the probability that user
\(l\) successfully stops and transmits at the previous
\(k1\) sensing steps (so does not reach the
kth step),
\((1\sum \nolimits _{j=1}^{k1} {\phi _{l,j} )(1\theta _{l,S_{l,k} } )}\) is the probability that user
\(l\) reaches the
kth step but senses channel
\(S_{m,k} \) to be busy.
\(\prod \nolimits _{l^{*}} \left( {1\phi _{l^{*},p(S_{m,k} ,\mathbf{S}_{\mathbf{l}^{{\varvec{*}}}} )} } \right) \) is the probability that channel
\(S_{m,k}\) has not been occupied by any other users at the previous
\(k1\) sensing steps.
$$\begin{aligned} \phi _{m,k} =\left\{ \begin{array}{l@{\quad }l} \theta _{m,S_{m,k}}, &{} \hbox {for case 1;}\\ \theta _{m,S_{m,k}}\prod \limits _l \left( {1\theta _{l,S_{l,k}}}\right) ,&{} \hbox {for case 2.} \end{array}\right. \end{aligned}$$
(6)
$$\begin{aligned} \phi _{m,k}= \left\{ \begin{array}{l@{\quad }l} (1\sum \limits _{j=1}^{k1} \phi _{m,j})\theta _{m,S_{m,k} }, &{}\hbox {for case 1;}\\ (1\sum \limits _{j=1}^{k1} \phi _{m,j} )\theta _{m,S_{m,k}} \prod \limits _l \left( {(1\sum \limits _{j=1}^{k1} {\phi _{l,j} )(1\theta _{l,S_{l,k}} )+\sum \limits _{j=1}^{k1} {\phi _{l,j}}}}\right) , &{}\hbox {for case 2;}\\ (1\sum \limits _{j=1}^{k1} {\phi _{m,j} )\theta _{m,S_{m,k}} \prod \limits _{l^{*}}}\left( {1\phi _{l^{*}, p(S_{m,k}, \mathbf{S}_{\mathbf{l}^{{\varvec{*}}}})}} \right) , &{}\hbox {for case 3;}\\ (1\sum \limits _{j=1}^{k1} {\phi _{m,j} )\theta _{m,S_{m,k}} \prod \limits _l \left( {(1\sum \limits _{j=1}^{k1} {\phi _{l,j})(1\theta _{l,S_{l,k}} )+\sum \limits _{j=1}^{k1} {\phi _{l,j}}}}\right) }\\ \times \prod \limits _{l^{*}} \left( {1\phi _{l^{*},p(S_{m,k}, \mathbf{S}_{\mathbf{l}^{{\varvec{*}}}})}} \right) , &{}\hbox {for case 4.} \end{array}\right. \nonumber \\ \end{aligned}$$
(7)
Using Eqs. (
6) and (
7) we can iteratively get all the
\(\phi _{m,k}\) for each
\(m\) and
\(k\). Then given a sensing matrix, the expected network throughput can be obtained:
The coordinator’s aim is to find the optimal sensing matrix
\(\mathbf{S}^{\mathbf{0}}\) to maximize the expected network throughput. This can be stated formally as:
Given this optimization problem, the coordinator can find the optimal sensing matrix by bruteforce search. However the complexity of bruteforce search is
\(O((N!)^{M})\) which will result in massive computational burden and is not scalable regarding to both
\(M\) and
\(N\). This paper targets at suboptimum algorithm that has much less complexity but is still efficient, as discussed in the following section.
$$\begin{aligned} U=\sum \limits _{m=1}^M {\sum \limits _{k=1}^N {\phi _{m,k} R_{m,S_{m,k} } c_k}} \end{aligned}$$
(8)
$$\begin{aligned} \mathbf{S}^{\mathbf{0}}=\mathop {\arg \max }\limits _{S_{1,1}, S_{1,2}, \ldots ,S_{M,N}} U \end{aligned}$$
(9)
5.2 Greedy Search Algorithm
As discussed before, for a target user to determine which channel to sense in its
kth sensing step, if a channel has already been in other users’ prior (
\(\le k)\) sensing positions, the probability that this channel is occupied by other users should be considered. And the throughput loss caused by collisions should also be considered when two or more users proceed to sense the same channel at the same time. Based on above observations, in this section, we will propose a greedy search algorithm which contains
\(N\) rounds. Let
\(\mathbf{S}_\mathbf{m}\) denotes the channel selection vector of user
\(m.\,\mathbf{S}_\mathbf{m}\) will be updated after each rounds. So it contains
\(k\) chosen channels after the
kth round. In the
kth round the coordinator needs to determine
\((S_{1,k} ,S_{2,k} ,\ldots ,S_{M,k} )\) for the users, where
\(S_{m,k} \in \overline{\mathbf{S}_\mathbf{m} } =\mathbf{N}\backslash \mathbf{S}_\mathbf{m}\). Figure
2 depicts the channel selection process with an example.
×
Let
\(p(i,\mathbf{S}_\mathbf{m} )\) denotes the position of channel
\(i\) in
\(\mathbf{S}_\mathbf{m}\) if it is in
\(\mathbf{S}_\mathbf{m}\). For a user
\(m\) selecting
\(S_{m,k}\) among channels from
\(\overline{\mathbf{S}_\mathbf{m} }\), the coordinator estimates the probability that each channel is free from primary users and other SUs, and accordingly assign each channel a reward. We define
\(G_i^{(m)} (k)\) the reward of channel
\(i\) selected by user
\(m\) as the
kth channel in its sensing order. It is set to the contribution of the user
\(m\) to the network throughput if channel
\(i\) is selected. Then the channel with the largest reward is selected as
\(S_{m,k}\) for user
\(m\). The selecting process is as follows:
5.2.1 Round1
At the beginning, the set of already selected channels for each user is empty (
\(\mathbf{S}_\mathbf{m} =\varnothing \) for user
\(m\)). We start with the first SU. The coordinator needs to choose
\(S_{1,1}\) for user 1 from
\(\overline{\mathbf{S}_\mathbf{1} } =\mathbf{N}\). For a channel
\(i\in \overline{\mathbf{S}_\mathbf{1} }\), we can obtain that
\(G_i^{(1)} (1)=\theta _{1,i} R_{1,i} c_1\). Thus, the first channel to be sensed by user 1 is:
After
\(S_{1,1}\) is determined, we have
\(\mathbf{S}_\mathbf{1} =\{S_{1,1}\}\).
$$\begin{aligned} S_{1,1}=\mathop {\arg \max }\limits _{i\in \overline{\mathbf{S}_\mathbf{1} } }G_i^{(1)} (1) \end{aligned}$$
(10)
While for the
mth user in the first round, a channel
\(i\) may have already been in the sets of selected channels of other users
\((i\in \mathbf{S}_\mathbf{l} ,l\in \mathbf{M}\backslash m)\). Thus we have:
where
\(\theta _{m,i} \prod \nolimits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ i\in \mathbf{S}_\mathbf{l} \end{array}} {\left( {1\theta _{l,i}}\right) }\) means the probability that channel
\(i\) is free from primary users and all other SUs. If channel
\(i\) has already been in the other users’ selected channel set, user
\(m\) selects it as the first channel will cause throughput loss to the network due to the collision with other users. Thus we can get the loss of reward as follows:
where
\(l\) is the user which has already selected channel
\(i,\,\overline{l}\) satisfies that
\(\overline{l} \in \mathbf{M}\backslash m,\,i\in \mathbf{S}_{\mathbf{l}^{{\varvec{*}}}}\) and
\(\overline{l} \ne l.\,c_1 R_{l,i} \theta _{l,i} \prod \nolimits _{\overline{l} } {(1\theta _{\overline{l} ,i} )}\) is the reward of channel
\(i\) using by user
\(l\). A collision happens if user
\(m\) senses channel
\(i\) as free at the same time (with probability
\(\theta _{m,i} )\), and then the reward of user
\(l\) is lost. Therefore, the reward in Eq. (
11) should be rewritten for user
\(m\) selecting channel
\(i\) as its first channel:
Then the coordinator selects the channel that has the largest reward as the first channel for user
\(m\):
$$\begin{aligned} G_i^{(m)} (1)=R_{m,i} c_1 \theta _{m,i} \prod \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ i\in \mathbf{S}_\mathbf{l} \end{array}} {\left( {1\theta _{l,i} } \right) } \end{aligned}$$
(11)
$$\begin{aligned} L_i^{(m)} (1)=\theta _{m,i} \sum \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ i\in \mathbf{S}_\mathbf{l} \end{array}} {\left( {c_1 R_{l,i} \theta _{l,i} \prod \limits _{\overline{l} } {(1\theta _{\overline{l} ,i} )} } \right) } \end{aligned}$$
(12)
$$\begin{aligned} G_i^{(m)} (1)=R_{m,i} c_1 \theta _{m,i} \prod \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ i\in \mathbf{S}_\mathbf{l} \end{array}} {\left( {1\theta _{l,i} } \right) } L_i^{(m)} (1) \end{aligned}$$
(13)
$$\begin{aligned} S_{m,1} =\mathop {\arg \max }\limits _{i\in \overline{\mathbf{S}_\mathbf{m} } }G_i^{(m)} (1) \end{aligned}$$
(14)
5.2.2 Roundk
After the
\(k1\hbox {th}\) round, the coordinator has selected
\(k1\) channels for each user, which means we have got a matrix of selected channels with a dimension of
\(M\times (k1)\). Thus using this matrix and Eqs. (
6) and (
7) we can get the
\(\phi _{m,j}\) for each user
\(m\) and
\(j\in \left[ {1,k1} \right] \). At the
kth round, we define
\(P_i^{free} (k)\) as the probability that channel
\(i\) is not occupied by any SU in the previous
\(k1\) sensing steps. We have:
where
\(l^{\varvec{*}}\) represents the user that has already selected channel
\(i\) at the previous
\(k1\) rounds.
$$\begin{aligned} P_i^{free} (k)=\prod \limits _{\begin{array}{c} l^{\varvec{*}}\in \mathbf{M}\\ p(i,\mathbf{S}_{\mathbf{l}^{{\varvec{*}}}})<k \end{array}} {\left( {1\phi _{l^{*}, p(i,\mathbf{S}_{\mathbf{l}^{\varvec{*}}})}}\right) } \end{aligned}$$
(15)
At the
kth round, the coordinator should first determine with which SU it should start. Similar to [
12], to achieve a certain level of fairness, we start with the user that has a less cumulative reward in the previous
\(k1\) rounds. The cumulative reward gained during the previous
\(k1\) rounds for user
\(m\) is calculated as,
When user
\(m\) selects a channel
\(i\in \overline{\mathbf{S}_\mathbf{m}}\) as its
kth channel, this channel may has already been selected by other users at the same round. So the collision free probability should be considered when selecting a channel. The reward gained by user
\(m\) selecting channel
\(i\) at the
kth round can be obtained:
where
\(P_i^{free} (k)\) is defined in Eq. (
15),
l is the user that has already selected channel
\(i\) at the
kth round. The formula in
\(\prod \) represents the collision free probability for user
\(m\) selecting channel
\(i\). A collision happens if user
\(m\) and
\(l\) sense channel
\(i\) to be free at the same time. So the reward of user
\(l\) may be lost because of user
\(m\) selecting channel
\(i\). The loss of reward caused by user
\(m\) selecting channel
\(i\) at the
kth round is calculated as:
where
\(\overline{l}\) satisfies that
\(\overline{l} \in \mathbf{M}\backslash m,\,p(i,\mathbf{S}_{\overline{\mathbf{l}} } )=k\) and
\(\overline{l} \ne l.\,F\) represents the probability that user
l is the only one that senses channel
\(i\) as free regardless of the effect of user
\(m\). So the considered loss of reward is only because of user
\(m\) selecting channel
\(i\) at the
kth round. Therefore, the reward in Eq. (
17) should be rewritten as follows:
Then the coordinator selects the channel from
\(\overline{\mathbf{S}_\mathbf{m} }\) that has the largest reward as the
kth channel for user
\(m\):
After
\(S_{m,k}\) is selected,
\(\mathbf{S}_\mathbf{m}\) is updated,
\(\mathbf{S}_\mathbf{m} =\{S_{m,1} ,S_{m,2} ,\ldots ,S_{m,k} \}\).
$$\begin{aligned} \phi _{m,1} c_1 R_{m,S_{m,1}} +\phi _{m,2} c_2 R_{m,S_{m,2}} +\cdots +\phi _{m,k1} c_{k1} R_{m,S_{m,k1}} \end{aligned}$$
(16)
$$\begin{aligned} G_i^m (k)=c_k R_{m,i} \theta _{m,i} P_i^{free} (k)\prod \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ p(i,\mathbf{S}_\mathbf{l} )=k \end{array}} {\left( {\sum \limits _{j=1}^{k1} {\phi _{l,j}} +(1\theta _{l,i} )\left( 1\sum \limits _{j=1}^{k1} {\phi _{l,j}}\right) } \right) }\quad \end{aligned}$$
(17)
$$\begin{aligned} L_i^{(m)} (k)&= c_k \theta _{m,i} P_i^{free} (k)\sum \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ p(i,\mathbf{S}_\mathbf{l} )=k \end{array}}\nonumber \\&\quad \times {R_{l,i} \underbrace{\left( {\theta _{l,i} (1\sum \limits _{j=1}^{k1} {\phi _{l,j}})\prod \limits _{\overline{l}} {\left( 1\theta _{\overline{l}, i} (1\sum \limits _{j=1}^{k1} {\phi _{\overline{l}, j}})\right) }} \right) }_F} \end{aligned}$$
(18)
$$\begin{aligned} G_i^m (k)=c_k R_{m,i} \theta _{m,i} P_i^{free} (k)\!\prod \limits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ p(i,\mathbf{S}_\mathbf{l} )=k \end{array}} \!\!{\left( {\sum \limits _{j=1}^{k1} {\phi _{l,j} } \!+\!(1\!\!\theta _{l,i} )\left( 1\!\!\sum \limits _{j=1}^{k1} {\phi _{l,j}}\right) } \right) } \!\!L_i^m (k)\nonumber \\ \end{aligned}$$
(19)
$$\begin{aligned} S_{m,k} =\mathop {\arg \max }\limits _{i\in \overline{\mathbf{S}_\mathbf{m} } }G_i^{(m)} (k) \end{aligned}$$
(20)
In the last round, the only channel in
\(\overline{\mathbf{S}_\mathbf{m} } \) is selected as
\(S_{m,N}\) for user
\(m\). Till the whole sensing matrix is got, the algorithm is done.
5.2.3 Modification of Reward
Let’s rewrite the reward Eq. (
19) as follows:
Where
\(P_{m,i}^{free} =\theta _{m,i} P_i^{free} (k)\prod \nolimits _{\begin{array}{c} l\in \mathbf{M}\backslash m\\ p(i,\mathbf{S}_\mathbf{l} )=k \end{array}} {\left( {\sum \nolimits _{j=1}^{k1} {\phi _{l,j}} +(1\theta _{l,i})(1\sum \nolimits _{j=1}^{k1} {\phi _{l,j}})} \right) }\) is the probability that channel
\(i\) is free for user
\(m\) from primary users and all other SUs. Thus from an individual user’s perspective, the preceding greedy search algorithm is just like the greedy algorithm discussed in Sect.
4.1, just changing the
potential function from Eq. (
3) to
\(g_m (i,k)=c_k R_{m,i} \theta _{m,i}\). From the simulation result in [
24] and our numerical analysis, the performance of greedy algorithm using the former
potential function is better than that of using the later one. So it’s reasonable to change our reward in Eq. (
21) according to the structure of Eq. (
3),
\(g_m (i,k)=R_{m,i} /(\tau /\theta _{m,i} +T(k+1)\tau )\). We modify Eq. (
21) as follows:
Where
\(P_{m,i}^{free}\) is the same of that in Eq. (
21).
$$\begin{aligned} G_i^m (k)=c_k R_{m,i} P_{m,i}^{free} L_i^m (k) \end{aligned}$$
(21)
$$\begin{aligned} G_i^m (k)=R_{m,i}/(\tau /P_{m,i}^{free}+T(k+1)\tau )\frac{R_{m,i} /(\tau /P_{m,i}^{free}+T(k+1)\tau )}{c_k R_{m,i} P_{m,i}^{free}}L_i^{(m)}(k)\nonumber \\ \end{aligned}$$
(22)
From the preceding procedure, we can see that the complexity of this greedy search algorithm is
\((N+N1+\cdots +1)M=\frac{N(N+1)}{2}M\) if the complexity of calculating one reward is
\(O(1)\), which is much less than the complexity of bruteforce search,
\(O((N!)^{M})\). In order to further have a midterm farness, we suggest that at the beginning of
Round 1, the coordinator chooses the user to start with in a
round robin way.
6 Performance Evaluation
6.1 Simulation Settings
In our simulations, we consider a network with
\(M\) SUs and
\(N\) potential channels. The primary activity is modeled as i.i.d. in both frequency channel and timeslot dimensions. We assign the values of primary free probability
\(\mathbf{P}_\mathbf{I}\) and channel achievable rate
\(\mathbf{R}\) randomly for each user and each channel at the beginning of each slot. We set the channel sensing
\(\backslash \)probing time
\(\tau =0.02\hbox {s}\) and slot duration
\(T=1\hbox {s}\). The achievable rates of the channels are uniformly distributed on (0,10)kbps. The performance metrics considered in this work are: Average SU throughput—the average number of successful bits transmitted per second per SU; Throughput difference—the average ratio of the standard deviation of the SUs’ throughputs to the average SU throughput in a slot, which represents the fairness between the SUs in a slot; Collision—the average times that two or more SUs sense the same channel as free (thus the probing signals collide and none of the SUs can use the channel) in a slot. We perform the simulations 10,000 time slots for each run. We then average the performance measurements over the timeslots.
6.2 Simulation Results
We evaluate the performance of the proposed greedy search algorithms versus
\(\mathbf{P}_\mathbf{I},\,M,\,N\) and
\(P_f\). We compare the performance of our distributed greedy search algorithm with reference [
20], and compare the sensing matrix proposed in our centralized greedy algorithm with the Latin Square matrix proposed in [
14].
We study the impact of the primary free probability on the performance of proposed algorithms, and keep the other parameters to be
\(M=5,\,N=7\) and
\(P_f =0\). We keep the standard deviation of the primary free probability to be 0.25, and change the average value between [0.25, 0.75]. The simulation results are depicted in Figs.
3,
4 and
5.
(1)
Effect of primary free probability,
\(\mathbf{P}_\mathbf{I}\)
×
×
×
Figure
3 shows the impact of primary free probability on the average SU throughput. We can see that the values of average SU throughput of all algorithms increase as the primary free probability increases. This is easy to understand that larger primary free probability means more transmission opportunity for the SUs. It is shown that both of our distributed algorithm and centralized algorithm gain more throughput than reference [
20] and Latin Square method in [
14]. To be specific, the proposed distributed greedy search algorithm outperforms reference [
20] by 14.78–8.56 % when
\(\mathbf{P}_\mathbf{I}\) increases from 0.25 to 0.75; the proposed centralized greedy search algorithm outperforms Latin Square method by 28.89–54.33 % when
\(\mathbf{P}_\mathbf{I}\) increases from 0.25 to 0.75. And the centralized greedy search algorithm outperforms the distributed algorithm by 1.82–4.66 %. We can see that the average SU throughput of distributed greedy search algorithm increases more slowly than that of the centralized algorithm as
\(\mathbf{P}_\mathbf{I}\) increases. This is because that when
\(\mathbf{P}_\mathbf{I}\) increases the relative difference between free probabilities of different channels decreases, so the advantage of the distributed algorithm (which takes advantage of the relative difference of different channels, see Eq. (
5)) decreases.
The throughput difference versus primary free probability is depicted in Fig.
4. It is shown that the throughput difference of each algorithm decreases as the primary free probability increases. This is because that when primary free probability is smaller, it’s more likely that some users can’t find an available channel which makes the difference between SUs throughputs larger. We can see that the throughput difference of our distributed greedy algorithm and centralized greedy algorithm is smaller than that of reference [
20] and Latin Square method, which means that our methods can guarantee better fairness among the SUs than reference [
20] and Latin Square method do. Specifically, when
\(\mathbf{P}_\mathbf{I}\) increases from 0.25 to 0.75, the throughput difference of the distributed greedy algorithm is 71.73–28.9 %, and 70.69–26.27 % for the centralized greedy algorithm, 76.26–35.38 % for reference [
20], 78.09–51.14 % for Latin Square method. The centralized greedy algorithm is the best because that it adopts a measure to guarantee the fairness among SUs, see Eq. (
16) and the related analysis.
Figure
5 shows the collision of different methods. The collisions of the distributed greedy method and reference [
20] increase with
\(\mathbf{P}_\mathbf{I}\). This is because the probability that two or more SUs sense the same channel to be free increases with
\(\mathbf{P}_\mathbf{I}\). We can see that the collision of the distributed greedy algorithm is smaller than that of reference [
20] in most cases. The collision of the Latin Square method is zero, and the collision of our centralized greedy algorithm is far smaller (from 0.06 to 0.02) than those of distributed greedy algorithm and reference [
20]. Though Latin Square method is collisionfree, it can’t get the optimal SUs throughput. This is because that when a collision happens, the SU can continue to sense the rest channels in its sensing order in the slot. The collision is not a dominant factor that influences the SUs throughput. However the collisions can waste available channel opportunities, thus cause throughput loss in some degree [see Eq. (
18)]. So our centralized greedy algorithm which has considered this impact can get the largest SUs throughput and very low collision.
We study the impact of the number of channels on the performance of proposed algorithms, and keep the other parameters to be
\(M=5,\,P_f =0\) and
\(\mathbf{P}_\mathbf{I}\) is randomly distributed on
\((0,1)\). Figure
6a depicts the effect of number of channels on the average SU throughput. It is shown that the average SU throughput of each method increases with the increase of the number of channels. This is because that more potential channels means more transmission opportunity for the SUs. We can see that the distributed greedy algorithm outperforms reference [
20] by 21.94–8.39 % when the number of channels increases from 5 to 10; the centralized greedy algorithm outperforms Latin Square method by 32.54–57.76 %; and the centralized greedy algorithm outperforms distributed greedy algorithm by 8.46–1.86 %. Figure
6b depicts the effect of the number of channels on the throughput difference. The throughput difference of each method decreases with the increase of the number of channels. This is because that with more potential channels it is more likely that every SU can get an available channel with good quality. It is shown that both of our distributed greedy algorithm and centralized greedy algorithm have smaller throughput difference than reference [
20] and Latin Square method which confirms the fairness among the SUs when using the proposed methods. We can see that when the number of channels gets larger, the performance (both average SU throughput and throughput difference) of the distributed greedy algorithm gets closer to that of the centralized greedy algorithm. This is because that the second part of Eq. (
5) will give a bigger effect with a larger number of channels.
(2)
Effect of the number of channels,
\(N\)
(3)
Effect of the number of SUs,
\(M\)
Figure
7 depicts the effect of the number of SUs on the performance of the algorithms, where the other parameters are kept as
\(N=10, \,P_f =0\) and
\(\mathbf{P}_\mathbf{I}\) is randomly distributed on (0,1). It is shown in Fig.
7a that the average SU throughput of each algorithm decreases with the increase of the number of SUs, since more SUs means less available channel opportunity for each SU. However the total network throughput increases with the increase of the number of SUs due to the multiuser diversity. We can see that both of our distributed greedy algorithm and centralized greedy algorithm gain more throughput than the traditional methods. In specific, the distributed greedy algorithm outperforms reference [
20] by 8.39–51.11 % when the number of SUs increases from 5 to 10; the centralized greedy algorithm outperforms Latin Square method by 57.54–48.95 %; and the centralized greedy algorithm outperforms distributed greedy algorithm by 1.73–4.55 %. It is shown in Fig.
7b that the throughput difference of each algorithm increases as the number of SUs increases. This is because that when the number of SUs increases, it’s harder to satisfy that each SU can get an available channel with good quality and it’s likely that some SUs even can’t get an available channel in a slot, so the throughput difference among the SUs increases. We can see that our distributed greedy algorithm and centralized greedy algorithm have smaller throughput difference than reference [
20] and Latin Square method. Specially, the performance of reference [
20] decreases very fast with the increase of the number of SUs. In contrast, both of our proposed methods can get far better performance (up to about 50%) than the traditional ones.
We study the impact of false alarm probability on the performance of the proposed algorithms, and keep the other parameters to be
\(M=5, \,N=7\) and
\(\mathbf{P}_\mathbf{I}\) is randomly distributed on (0,1). The simulation results are shown in Fig.
8. From Fig.
8a we can see that the average SU throughput of each method decreases with the increase of false alarm probability. This is because that with larger false alarm probability, it’s more possible that the SUs miss an actual available channel opportunity. It is shown that our proposed methods gain more SU throughput: the distributed greedy algorithm outperforms reference [
20] by 11.93–13.44 % when false alarm probability increases from 0 to 0.25; the centralized greedy algorithm outperforms Latin Square method by 43.63–36.29 %; and the centralized greedy algorithm outperforms distributed greedy algorithm by 3.83–2.68 %. Figure
8b depicts the collisions of the methods versus false alarm probability. We can see that Latin Square method is collisionfree, the collisions of distributed greedy algorithm and reference [
20] decrease with the increase of false alarm probability, while the collision of centralized greedy algorithm increases with the increase of false alarm probability. As we mentioned before, our centralized greedy algorithm has considered the throughput loss caused by collisions [Eq. (
18)], so it can get a very low collision compared to the distributed greedy algorithm and reference [
20]. However with the increase of false alarm probability, the value of Eq. (
18) (thus its impact) decreases, which causes the increase of collision. In contrast, both the distributed greedy algorithm and reference [
20] do not consider the impact of collisions on throughput loss, so their collisions decrease with the increase of false alarm probability because of the decrease of the probability that a channel is sensed to be free by two or more SUs simultaneously.
(4)
Effect of falsealarm probability,
\(P_f\)
×
×
×
7 Conclusions
In this paper, we study the channel sensing order setting problem for a multichannel multiuser cognitive radio network. Two suboptimal greedy search algorithms are proposed for both distributed scenario and centralized scenario. In the distributed greedy search algorithm, a novel
potential function is proposed to represent the relative advantage of a channel used by a user among multi channels and multi users. In the centralized greedy search algorithm, a sensing matrix is obtained by a coordinator for all the users. The loss caused by collisions is considered and the fairness between SUs is guaranteed in this centralized greedy search algorithm. Simulation results show that our distributed greedy algorithm gets more average SU throughput, better fairness and lower collision than the distributed method in the reference. And the sensing matrix obtained by our centralized greedy algorithm outperforms the Latin Square matrix in the reference. The distributed greedy algorithm has a very low computation complexity, and its performance gets very close to the centralized greedy algorithm (with a difference about 1 %) when the primary free probability is small, the number of channels is large and the false alarm probability is large. The stopping rules are not adopted in this paper because it should be jointly designed with the sensing order setting from a systematic point of view, this will be our future concern.
Acknowledgments
The work reported in this paper was supported by the National 973 Project of China under Grant No. 2009CB320401.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.