ABSTRACT

In this paper, we consider the problem of cognitive radio (CR) user selection to maximize overall CR network (CRN) throughput when the available spectrum bandwidth is less than the demand by all CR users. We formulate optimal CR user selection problem. Then, based on approximation of the average received signal to interference plus noise ratio () and adaptive modulation and coding (AMC), we estimate the required bandwidth of CR users with different required quality of services (QoSs). Using the principle of optimality, we propose a novel cooperative spectrum sharing algorithm for a CRN. The proposed algorithm not only achieves exhaustive search performance but also its complexity is in the order of N × M versus 2^N for exhaustive search, where N is the number of CR users, and M is the spectrum pool size. Extensive simulation results illustrate that the proposed algorithm significantly outperforms the existing algorithms that ignore optimal CR user selection. Also, these results illustrate a better fairness criterion than those of previous works.

1. Introduction

In the fixed spectrum allocation policy that is currently used in wireless networks, fixed spectrum segments are allocated to spectrum-licensed primary radio (PR) users for a long time in large regions. In the last three decades, spectrum demands for the wireless applications have been increased so rapidly such that spectrum scarcity has become a bottleneck of this fixed spectrum allocation policy, while, PR users underutilize significant portions of the allocated spectrums, ranging from 15% to 85% of times or regions [1]. The underutilization and the limitation of the frequency spectrum necessitate applying a dynamic spectrum allocation policy, which can be implemented using cognitive radio (CR) technology [2]. Based on dynamic spectrum allocation, in a CR network (CRN), unlicensed-spectrum CR users can use parts of spectrum (spectrum holes) that are not being utilized by PR users at particular times or in specific regions. In a CRN, one of the main components is the spectrum sharing algorithm that is allocating new spectrum holes to CR users.

A spectrum sharing algorithm is designed with a specific objective. This can be achieved by a cooperative or noncooperative algorithm. In the first case, all CR users cooperatively implement an algorithm such that they optimize overall objective of the CRN. In contrast, CR users may have opportunistic and selfish behaviors in noncooperative spectrum sharing algorithms. Thus, the difference of these two types of spectrum sharing algorithms is in overall or individual definition of the objective. The objectives of spectrum sharing algorithms are throughput, power, interference, profit, and etc. [3]. In this paper, we propose a novel optimal cooperative spectrum sharing algorithm with overall CRN throughput as its objective.

The concept of “spectrum pooling” is the idea of merging different spectrum segments from different PR users into a common spectrum pool, where first was proposed in [4] for cooperative spectrum sharing. In [5], authors used this concept to formulate a cooperative spectrum sharing algorithm as a restless bandits model based optimization system, which maximizes the price and spectrum efficiency based utility function objective. In [6], relationship between the optimal capacity of spectrum pool and network efficiency is studied and a quantitative mathematical relation was derived for it. A basic spectrum sharing algorithm for CRN with a single PR user and multiple CR users was introduced in [7], and an analytical model was implemented to derive the statistics of the spectrum sharing algorithm. Also, in [8], a hierarchical spectrum sharing algorithm was proposed for clustering CRN; the methodologies behind its levels are the list-coloring and maximum matching. Such an algorithm achieves suboptimal performance.

In [9], authors developed a distance-dependent medium access control protocol (DDMAC) to improve the overall CRN throughput using a cooperative spectrum sharing. This algorithm exploits the dependence between the signal attenuation model and the transmission distance. It assigns spectrum holes with lower average signal to interference and noise ratio () to shorter transmission distances to increase the number of simultaneous transmissions, and consequently, to increases the overall CRN throughput. However, when available spectrum is insufficient to serve all CR users, this algorithm has no idea about how to select CR users in order to achieve optimal overall CRN throughput.

In this paper, we propose a novel optimal cooperative spectrum sharing algorithm that has the ability to select the CR users in order to achieve optimal overall CRN throughput. We use principle of optimality [10]. According to the principle of optimality, an optimal solution of a problem has the property that includes optimal solution for all sub problems of a main problem. We used orthogonal frequency-division multiplexing (OFDM) based spectrum pool, which has high flexibility with respect to spectrum holes [5]. In order to avoid corrupting the transmissions of PR users, a power mask is enforced on the transmission of CR users. The log-distance path loss model is used to approximate the transmission path loss, and. Then, we apply these and an adaptive modulation and coding (AMC), to estimate minimum required bandwidths of CR users. We formulated this optimal user selection problem with the objective of maximizing overall CRN throughput and meeting constraint of the given spectrum pool size. Then, using principle of optimality, we investigate a dynamic form of this problem, and propose a novel algorithm for spectrum sharing.

The proposed algorithm has reasonable (polynomial) computational complexity, which makes it useful for practical networks when spectrum holes are available only for idle period of PR users. In other words, the proposed algorithm not only achieves exhaustive search performance, i.e. optimal solution, but also has low computational complexity. Also, in performance analysis of the proposed algorithm, we consider fairness of the proposed algorithm compared with other algorithms.

The rest of this paper is organized as follows. Section 2 presents preliminaries of the proposed algorithm; includes an overview of the OFDM based spectrum pool and system model. The analysis of bandwidth requirement is presented in Section 3. In Section 4, we formulate the optimal CR user selection problem. Section 5 introduces our proposed cooperative spectrum sharing algorithm. Complexity analysis is given in Section 6. We evaluate the proposed algorithm through simulations in Section 7. Conclusions are given in Section 8.

2. Preliminaries

2.1. OFDM Based Spectrum Pool

Spectrum pooling is the idea of merging different spectrum segments from PR users into a common spectrum pool [4]. When, some of the PR users are idle, there are spectrum holes in their corresponding spectrums at the common spectrum pool. The CR users may use these spectrum holes of the spectrum pool, during idle periods of PR users. The main proposition is that the operations of CR users must be transparent for PR users, and PR systems do not need to be changed. So, the CRN system must have high flexibility to fill the spectrum holes in the common spectrum pool. In other words, the CR user must jumps from a newly occupied part of the spectrum pool to an unoccupied spectrum from already available separated spectrum holes. OFDM is the best choice for implementing this high flexible CRN.

The key advantage of the OFDM is that a set of subcarriers represented by their corresponding IFFT inputs can be fed with zeros, thus sparing certain spectral areas from the emission of power. So, if the CR user only uses the subcarriers lying in idle spectrums of the PR network (i.e., in the spectrum holes of the spectrum pool), spectral coexistence of both PR and CR systems is possible and the CR users have high flexibility respect to the spectrum holes. In fact, the basic idea of the OFDM based spectrum pool is to match the bandwidth of the PR user’s band with an integer multiple of the carrier that used in the CR systems.

2.2. System Model

In this paper, we consider a CRN with N CR users who use L different services having different quality of services (QoSs). denotes percentage of the CR users in the class l,. Class l of service type is determined by and, respectively, which denote minimum data rate and target bit error rate (BER) to guarantee minimum quality of service of this class.

The available spectrum in the common spectrum pool is divided into M subchannels, each having a fixed bandwidth. The number of available subchannels varies by changing size of the spectrum pool. In our proposed algorithm, the spectrum is allocated with the unit of one subchannel.

The CR user’s arrival and departure processes in the CRN are considered to be Poisson processes [4]. The expected arrival and departure rates of the CR users are represented by and, respectively. Similarly, the arrival and departure processes of available spectrum unit in the spectrum pool are also considered to be Poisson processes, with expected arrival and departure rates and, respectively. Table 1 presents system parameters and their definitions.

3. CR User Bandwidth Requirement Evaluation

In this section, we explain how to estimate the bandwidth required for the jth CR user. First, we evaluate average path loss and experienced by the CR user. Then, using AMC, we estimate the bandwidth required for the CR user. These estimations of required bandwidths will be used by the proposed spectrum sharing algorithm presented in Section 5.

3.1. Pass Loss Evaluation

We use the log-distance path loss model to estimate the path loss in the CRN [11]. This model is only valid for distances beyond the far field distance from the CR transmitter antenna, d_f, which depends on the maximum linear dimension of transmitter antenna (D_a), and carrier wavelength (, where c is the speed of light), and can be estimated as [12]

(1)

denotes the average large-scale path loss between a transmitter and a receiver separated by distance d. By choosing the close-in distance d₀(d₀ ≥ d_f) as a reference distance; based on the log-distance path loss model, for (at far field distance) is expressed as

, (2)

where n is the path loss exponent (typically, 2 ≤ n ≤ 6) that indicates the rate at which the path loss increases with d, also, is the path loss at. can be measured or estimated using Friis propagation model [12].

It is notable that in practice is in the order of the CR transmitter antenna dimension. For example, for a cellular phone operating at 900MHz band with D_a = 5 cm, d_f is 33 cm. Consequently, the probability that two CR users being separated by a distance lower than is very small (i.e.).

3.2. Average SINR

For transmission between two CR users, which are separated by d, the at the CR user receiver antenna over a band is determined by transmitter antenna power (P_t), average path loss associated with that transmission that is expressed using Equation (2), average interference in receiver (), and thermal noise (). Formally, is given by

, (3)

where is the inter carrier interference (ICI) of PR users that is evaluated in [13].

3.3. AMC and CR User Bandwidth Requirment

Equation (3) is used to estimate (of the CR user transmission) and bandwidth requirement as explained in the following. The CR users employ adaptive modulation and coding to transmit on assigned spectrum holes. For QAM modulation with quadratic constellation, i.e. 4QAM, 16QAM, and etc., BER for a single input single output (SISO) channel with additive white Gaussian noise (AWGN) is expressed as [14]

, (4)

where k^s [b/s/Hz] is the spectrum efficiency. To guarantee the quality of service for the jth CR user in class l (1≤ l≤ L), we set BER in Equation (4) equal to, and replace in Equation (4) with the R.H.S of Equation (3). Consequently, the required spectrum efficiency () for this CR user is expressed as

, (5)

where

(6)

Thus, the spectrum efficiency, which is required to guarantee minimum quality of service for the jth CR user (from class l) is given by Equation (5). As well, having and, the required bandwidth, , can be evaluated as

(7)

Thus, the bandwidth requirement of a CR user is mainly a function of its service type class (i.e.), transmission distance, and at its receiver.

As mentioned before, the CRN employs OFDM system, thus, spectrum sharing algorithm had better assign integer multiple of spectrum units to each CR user (if CR user is selected in spectrum sharing algorithm that is explained in Section 5). So, it is appropriate to express, given by Equation (7), as an integer number of spectrum units. Since, expresses the minimum spectrum requirement, the minimum number of required spectrum units is expressed as

, (8)

where is the ceil function.

4. Optimal CR User Selection Problem

In many cases, the available spectrum units, M (spectrum pool size), is less than the CR users’ bandwidth requirements i.e.. So, the spectrum sharing algorithm must have a strategy in deciding which CR users should use the available spectrum, and which spectrum units should be assigned to which CR users. The decision strategy is designed to achieve a certain objective in the CRN. In this paper, the objective is to achieve the optimal overall CRN throughput. All CR users cooperate to maximizing the overall CRN throughput by selecting a subset of the CR users that have better conditions to use spectrum. The constraint of this optimization problem is the spectrum pool size. Let denotes the required data rate for the jth CR user (), that is equal to when this user is in class l.

The optimization problem of CR user selection with overall CRN throughput objective is: given a set of N CR users, and a common spectrum pool with M spectrum units, select a subset of the CR users such that Maximize        ,(9)

subject to

, (10)

, (11)

where

(12)

But, the above integer linear programming (ILP) problem belongs to the class of NP-hard problems. To explain this proposition, we note that to solve this problem a naive approach would be to examine all possible binary vectors, selecting the best of those which satisfies the constraints. Unfortunately, the number of such vectors is 2^N, by exhaustive search, even a hypothetical computer, capable of examining one billion vectors per second, would require more than 30 years for a CRN with 60 CR users. However, it is clear that time access to spectrum hole, idle period of PR user, is so lower. On the other hand, the computational complexity of spectrum sharing algorithm should be low because a long computation time may result in the out of date spectrum state information. In Section 5, using principle of optimality, we propose a novel cooperative algorithm that provides an optimal solution that has a reasonable computation time such that in a CRN with N = 100 CR users, optimal solution is obtained in a reasonable time by a regular processor.

5. Proposed Cooperative Spectrum Sharing Algorithm

In this section, we propose a novel cooperative spectrum sharing algorithm such that it not only achieves optimal solution but also it has low computational complexity. The decision strategy of this algorithm is a new approach in selecting CR users for maximizing the overall CRN throughput.

In Section 4, we defined the optimization problem, and stated that evaluating optimal solution leads to an exhaustive search with decision tree with 2^N nodes where it is impractical for spectrum sharing applications from computational complexity view. The principle of optimality where is said to be applied in an optimal solution to an instance of a problem always contains optimal solutions to all sub instances, is used in our proposed algorithm. Based on this principle, we solve our optimization problem for the CRN with small number of CR users, store these results, and later, whenever we need a result, we look up in previously stored results instead of recomputing it.

We use notation for the following optimal cooperative spectrum sharing problem: Select vector X such that it maximizes

, (13)

where

(14a)

(14b)

subject to

(15)

Now, in order to design our cooperative spectrum sharing algorithm we define and prove the following lemma.

Lemma: The cooperative spectrum sharing problem can be expressed in a dynamic form using principle of optimality.

Proof:

We assume is an optimal solution

() for i.e. for

, where expresses which CR users can use the spectrum. If, then must be the optimal solution for, otherwise is not optimal solution for.

On the other hand, if, then must be optimal solution for, otherwise we have another sequence such as which satisfies

, (16)

and

. (17)

So, sequence is better than optimal solution where it is against the assumption. Consequently, if denotes an optimal solution value for, i.e.

, (18)

can be expressed in a dynamic form as follows,

.(19)

Therefore, the optimal solution for cooperative spectrum sharing problem that is explained in IV is, where we can evaluate its optimal value, , in a dynamic form using Equation (19). Algorithms 1 and 2 are consecutively are run to obtain the optimal solution for this cooperative spectrum sharing problem. The output of Algorithm 2 is vector X which indicates which CR users are selected for data transmission. Specifically, jth CR user is selected if. We note that the solution obtained from in Algorithm 1 (for the CRN with N CR users and spectrum pool with M spectrum units); it includes the optimal solution for any CRN with n(n ≤ N) CR users, and spectrum pool with m spectrum units (m ≤ M). This is a property that directly arises from the principle of optimality.

When Algorithm 2 selects the best sub set of CR users that they maximize the overall CRN throughput, spectrum sharing algorithm starts the spectrum allocation step. In this step, we use DDMAC [9], which assigns the spectrum units with high values for near distance transmission and vice versa.

6. Complexity Analysis

As mentioned earlier, computational complexity of the cooperative spectrum sharing algorithm must be reasonable such that the CR users have enough time to use spectrum holes. So, it is useful to analyze computational complexity of the proposed algorithm by studying Algorithm 1 and Algorithm 2. In Algorithm 1, computational complexity of initialization steps are in order of N and M. Also, computational complexity of two loops in lines two and three of the algorithm is in the order of. So, computational complexity of Algorithm 1 is in the order of. Similarly, complexity of Algorithm 2 is in the order of. Consequently, complexity of the proposed spectrum sharing algorithm is versus for an exhaustive search of full decision tree. For example, in CRN with N = 40 CR users and spectrum pool with M = 200; computational complexity is 8000 versus 2⁴⁰ respectively for the proposed algorithm and full exhaustive search.

7. Simulation Results

To evaluate the performance improvement of the proposed algorithm, extensive simulation results are discussed in this section. We consider a CRN with N CR users in field. The CR users are in the three classes (). These are respectively streaming traffic (e.g. data stream download), audio traffic (e.g. mp3) and video traffic (e.g. MPEG1). The percentages of CR users in these classes are 60%, 35%, and 5% of N CR users, respectively. The required data rates for these three classes are 300 kbps, 190 kbps, and 1.15 Mbps, respectively. Also, minimum BERs are andrespectively. The maximum transmitting power of the CR users is 50 mW and this power mask is enforced to avoid corrupting the connections of PR users. So, for a fair comparison, we let all CR users use the maximum transmitting power. The signal propagation model in Equations (1) and (2) is used with, the maximum linear dimension of transmitter antenna () is 5 cm, and. We set thermal noise, for all spectrum units in the spectrum pool.

We use Jain’s fairness index [15] to quantify the throughput fairness of the algorithms. This is a common fairness metric, which is used in network engineering to determine whether users are receiving a fair share of spectrum. Fairness index values closer to 1 indicates better fairness.

We compare our proposed algorithm with DDMAC. DDMAC regardless of optimal solution tries to maximize the overall CRN throughput using distance-dependent algorithm. Also, we compare the proposed algorithm with bandwidth (BW) based and data rate (DR) based algorithms. Their CR user selection strategies are based on low bandwidth requirement and high data rate requirement, respectively. In order to maximize overall CRN throughput, BW based algorithm selects CR users with low bandwidth requirements, such that the number of CR users which share spectrum increases. On the other hand, DR based algorithm selects CR users with high data rates to maximize overall CRN throughput. We compare the performances of these algorithms using simulations.

7.1. Algorithm Performance with Different Spectrum Pool Sizes

In Figure 1(a), we compare the overall CRN throughput of the proposed algorithm with other algorithms in different sizes of the spectrum pool, when the number of CR users is 40 (N = 40). Figure 1(b) shows fairness comparison. These results show that the proposed algorithm achieves a better overall CRN throughput, as well as, a better fairness. It can be observed from these simulation results that as the spectrum pool size increases, the number of CR users who can simultaneously access to spectrum increases, consequently overall CRN throughput and fairness criterion increase. When the spectrum pool size increases to a value more than CRN overall bandwidth requirement, i.e. (in Figure 1 when), we don’t have any optimization problem and all algorithms have the same performance results. Although in actual wireless network conditions, spectrum pool has insufficient spectrum holes to serve all CR users, so optimal spectrum sharing becomes more important to achieve maximum possible overall CRN throughput. For example, when the spectrum pool has 105 spectrum units (condition that), the proposed algorithm achieves 14.88%, 6.10%, and 21.11% higher overall CRN throughput, respectively, compared with those of DDMAC, BW based, and DR based algorithms.

7.2. Algorithm Performance with Different Numbers of CR Users

The number of CR users affects the performances of spectrum sharing algorithms. In this section, we consider different numbers of the CR users and a constant spectrum pool size having 100 spectrum units. Figure 2 illustrates the overall throughput and fairness of the CRN in this scenario. As Figure 2(a) shows by increasing the number of CR users, the overall CRN throughput similarly increases in all algorithms. This increase is similar in all algorithms until number of CR users arises to a value that CR users’ bandwidth requirements is more than common spectrum pool size (number of CR users that saturates spectrum pool). Since, after these number of CR users, spectrum pool is saturated by previous CR users, and DDMAC and DR based algorithms respectively have no idea and good idea to select the best CR users from those added CR users, thus overall CRN throughput stops increasing and becomes nearly fixed, respectively for these two algorithms. In other words, when CR user selection strategy is based on these two algorithms, after saturation point, increasing CR users has insignificant effect on the overall CRN throughput. Whereas, after saturation point, since the proposed and BW based algorithms, respectively have optimal idea and good idea to select CR users from those added CR users, thus the overall CRN throughput continually increases by increasing CR users. Inasmuch as the proposed algorithm has optimal CR user selection strategy, it has the best operation among other three algorithms for each number of CR users, as Figure 2(a) is shown. Since we assumed available spectrum in spectrum pool was constant, as Figure 2(b) is illustrated, by increasing number of CR users the ratio of CR users accessing to spectrum decreases, so fairness criterion will be worse by increasing the number of CR users.

7.3. Algorithm Performance with Different Arrival and Departure Event Rates

Simulation results in Figures 3 to 6 show that the performance affected by different arrival and departure event rates. In Figures 3 and 4, we present the overall CRN throughput and the fairness criterion for different CR user’s arrival and departure rates, respectively. We can draw a conclusion that the proposed algorithm significantly improves the overall CRN throughput under these conditions. Also, the proposed algorithm has better performance in fairness view.

Furthermore, the performance comparisons are shown in Figures 5 and 6 with different spectrum unit arrival and departure rates, respectively. A larger arrival rate for the spectrum unit or lower departure rate induces availability of more spectrum units; thus, according to the decision strategy of the proposed algorithm, the overall CRN throughput is larger for our proposed algorithm.

7.4. Algorithm Performance during Time

In this section, we study the performance of real network conditions by simulating the CRN working for 500 minutes under arrival and departure rates given below:

,

,

, and

.

Since, the proposed algorithm always can optimally select the CR users that have the strongest appropriate to access new available spectrum holes, thus it performs much better than the other algorithms as Figure 7 shows.

7.5. Algorithm Performance with Different Ratio of Service Type Classes

Finally, we analyze our proposed algorithm with the different ratios of service types. Let, , and where and. Simulation results as are shown in Figure 8, illustrate better performances for the proposed algorithm in different classes’ ratios. Also, when the traffic ratios in CRN become to pure video traffic, the overall throughput of the CRN increases. In this condition, the CR users that access to spectrum is lower, so fairness criterion becomes lower.

8. Conclusion

In this paper, using log-distance path loss model and AMC, we estimate CR user bandwidth requirement in different service type classes. Based on the principle of optimality, we proposed a novel cooperative spectrum sharing algorithm with overall CRN throughput objective. This algorithm achieves optimal solution (exhaustive search solution). In addition, its computational complexity () is much lower than exhaustive search

time complexity. As well, this provides a better result in fairness criterion.

9. Acknowledgements

This research is partially funded by the Iranian Institute of information and Communication Technology (the former ITRC). Also, the authors would like to acknowledge Mr. Eman Mahmoodi and Mr. Saeed Balaneshin Kordan for their insightful comments and helpful discussions.

REFERENCES