Distributed Spectrum Sharing in Cognitive Radio Networks: A Pricing-Based Decomposition Approach

Abstract

The limited radio spectrum has become a bottleneck for various wireless communications. To better utilize the scare radio spectrum, cognitive radios have recently attracted increasing attention, which makes spectrum sharing more viable. Sharing radio spectrum from primary users to secondary users is of great importance. A licensed primary user (PU) can lease its spectrum to secondary users (SUs) for wireless communications. This paper studies the problem of social welfare maximization of distributed spectrum sharing among a PU and SUs. We first formulate the problem of social welfare maximization which takes into account both the cost of the PU and the utility gained by each SU. The social welfare maximization is a convex optimization problem and thus can be solved by a centralized algorithm. However, the utility function of each SU may contain the private information. To avoid privacy leakage of SUs, we propose an iterative distributed algorithm based on a pricing-based decomposition framework. It is theoretically proved that our algorithm converges to the optimal solution. Simulation results are presented to show that our algorithm achieves the optimal social welfare and converges quickly in a practical setting.

1. Introduction

With the increasing development of wireless communications, the scarcity of spectrum becomes more and more serious. Some allocated spectrum may not be used all the time. Many prior studies [1–3] show that the radio spectrum is underutilized in the real world. To make better use of the limited radio spectrum resource, cognitive radios [4] are becoming popular. The spectrum utilization can be largely improved by sharing the allocated spectrum of a primary user (PU) with those of secondary users (SUs) when the radio spectrum is not in use.

In this paper, we consider the problem of sharing the allocated spectrum owned by a PU to a set of SUs. Essentially, we consider a cognitive radio network consisting of one PU, the licensed owner of spectrum, and several SUs without licenses. Each secondary user consists of a pair of nodes, a sender, and a receiver, which have the demand of transmitting data over a wireless channel. A cost is incurred from the primary user when allocating some radio spectrum to secondary users. Each secondary user obtains a certain utility for transmitting data. The objective of spectrum sharing in such a cognitive radio network is to maximize the social welfare, which is defined as the sum of the utilities obtained by all secondary users minus the cost paid by the primary user.

A number of existing studies [5, 6] have been conducted for spectrum sharing in cognitive radio networks. Some of these studies [7–9] apply game theory to model interactions between PU and SU in a cognitive radio network. However, they fail to achieve the objective of social welfare maximization. They assume that secondary users are rational and selfish. For example, Niyato and Hossain [7] proposed a competitive spectrum sharing scheme based on game theory in multihop cognitive radio networks, and Han et al. [9] studied the correlated equilibrium concept for distributive spectrum access.

Some studies [10, 11, 19] maximize the network utility for spectrum sharing. For example, Peng et al. [10] proposed a general model and utility functions for optimizing the utilization in cognitive radio networks. One of the main issues is that these studies assume the utility function of each secondary user is known to all parties. In practice, however, such assumption may not hold. The utility function may contain private information and may not be known to others for the privacy protection purpose. Since these studies adopt a centralized algorithm, the privacy of a secondary user could not be guaranteed.

In response to the issue on privacy leakage for existing work, we focus on spectrum sharing among a primary user and a set of secondary users. We aim at maximizing the social welfare while not releasing the privacy in the utility function of each secondary user.

We have to address several challenges. First, the utility function of each secondary user contains the user-specific information, which may be concerning the privacy of the secondary user. Such private information should not be released in the process of spectrum sharing. Second, there may be a large number of secondary users. Thus, a distributed algorithm is preferable. Finally, the objective in the problem, maximizing the social welfare, couples the cost function of the primary user and the utility function of each secondary user. In other words, the objective function cannot be directly decoupled into several independent subproblems.

In response to the challenges mentioned above, we propose a distributed algorithm for spectrum sharing in cognitive radio networks, based on the decomposition algorithm for coupled systems [12]. Since the shared spectrum is priced by the primary user, we find that the optimal social welfare can be obtained when the optimal solution of an equivalent pricing problem is derived. Then, we propose a pricing-based decomposition framework, which decouples the problem into several subproblems. The primary user and each secondary user are responsible for a subproblem, which only contains its own private information, respectively.

Based on the decomposition framework, a distributed algorithm is provided, which is executed iteratively. In each iteration, each secondary user informs the primary user of its demanded spectrum, according to the given price. The primary user updates the price based on the collected demands. We also propose a price updating rule, under which the iterative algorithm converges to the optimal solution in finite steps. Extensive simulations have been conducted to evaluate the optimality and the convergence speed achieved by the distributed algorithm.

The rest of this paper is structured as follows. We introduce the network model and problem formulation in Section 3. The optimal distributed approach is described in Section 4. In Section 5, simulation results are reported to show the performance of our algorithm and compared algorithms. We review related work in Section 2 and conclude the paper in Section 6.

2. Related Work

We have witnessed the rapid increase in the use of various wireless communications, for example, 3G/4G, wireless sensor networks [13, 14], vehicular communications [15, 16], and WLAN. The radio spectrum becomes a precious resource. Cognitive radios have received extensive research from both industry and academia. Some studies [7, 8, 10, 19] focus on spectrum allocation, and some studies [17, 18] focus on opportunistic spectrum access without any monetary rewards to primary users. In our paper, we focus on distributed spectrum allocation with monetary rewards to the primary user.

Spectrum Allocation Based on Auction. By taking advantage of the models in the game theory, some of the existing works solve the spectrum sharing problem by achieving Nash Equilibrium. Niyato and Hossain [7] formulate the problem of spectrum sharing as an oligopoly market competition and use a Cournot game to obtain the spectrum allocation. However, the static Cournot game only adapts to some special environment. Han et al. [9] propose a correlated equilibrium concept for users to have the distributive opportunistic spectrum access. Wang et al. [8] propose a competitive spectrum-sharing scheme according to auction theorem without achieving social welfare maximization.

Spectrum Allocation Based on Optimization. Some centralized algorithms in some other works can actually achieve the social welfare maximization. Shi and Hou [18] propose a distributed throughput maximization algorithm in multihop cognitive radio networks. Peng et al. [10] propose a framework that defines the spectrum sharing problem for some definitions of overall system utility. The central server is designed for allocation assignments. Raman et al. [19] propose a centralized spectrum server that coordinates users to sharing a common spectrum. However, these algorithms could not protect the privacy of each user.

3. Network Model and Problem Formulation

In this section, we first describe the model of cognitive radio networks and then formulate the problem solved in this paper.

3.1. Network Model

We consider a cognitive radio network which consists of a primary user and n secondary users. The set of secondary users is denoted by ${{SU}_{1}, {SU}_{2}, \dots, {SU}_{n}}$ . Each secondary user actually consists of a sender and a receiver. The primary user, the owner of the spectrum, allocates its unused spectrum to secondary users. Each secondary user is allocated with a portion of spectrum, namely, bands. Each band is associated with a bandwidth representing a divided frequency range. The bandwidth allocated to secondary user ${SU}_{i}$ is noted by $p_{i}, 1 \leq i \leq n$ . We assume that the primary user can communicate with each secondary user directly. Moreover, the frequency allocated to different secondary users is orthogonal to avoid interference. The network model is illustrated in Figure 1.

Figure 1

An illustration of spectrum allocation in a cognitive radio network.

3.2. Problem Formulation

In this subsection, we formulate the social welfare of a cognitive radio network, including two parts: the cost paid by the primary user for spectrum allocation and the utilities obtained by the secondary users for data transmission.

Cost for Spectrum Allocation. The spectrum sharing with secondary users may impact the data transmission of the primary user. This leads to a highly increasing cost associated with the allocated bandwidth, which is formulated as an exponential function. We define the cost function as follows.

Definition 1.

The cost function of the primary user is formulated as

\begin{matrix} C (p) = β e^{\sum_{i = 1}^{n} p_{i}} - 1, \end{matrix}

(1)

where

p = (p_{1}, p_{2}, \dots, p_{m})

and β is a system parameter.

Remarks. The cost function emphasizes the cost of primary user for allocating the bandwidth to the secondary users. The larger the size of bandwidth allocated to the secondary users, the more the cost for the primary user. The cost may derive from the fact that the primary user can not use bandwidth as the primary user wants at any time. The exponential function indicates cost of primary user reasonably.

The primary user expects a payment in return from secondary users for using spectrum. The primary user provides a price $q_{i}$ for the spectrum spent by the ${SU}_{i}$ . Considering this payment, we formulate the profit of the primary user in Definition 2.

Definition 2.

The primary user obtains a profit for sharing spectrum as

\begin{matrix} Φ (p, q) = p q^{T} - C (p) . \end{matrix}

(2)

Utility for Data Transmission. It is intuitive that each secondary user obtains a utility for transmitting data. According to the bandwidth $p_{i}$ allocated to the secondary user, we define the utility function in the following.

Definition 3.

The utility function of secondary user ${SU}_{i}$ is defined as

\begin{matrix} u_{i} (p_{i}) = a_{i} \log (1 + p_{i}), \end{matrix}

(3)

where

a_{i}

is a user-specific parameter.

Remarks. The utility function emphasizes the utility obtained by each secondary user. The utility function of secondary user indicates the marginal utility. According to the law of diminishing marginal utility in economics [20], the $\log$ function implies that the increasing ratio of utility gain obtained by the secondary users degrades as the allocated bandwidth increases. Note that the parameter $a_{i}$ is the privacy information of secondary user ${SU}_{i}$ , which is unknown to the primary user and other secondary users.

Thus, the payoff of ${SU}_{i}$ is formulated as follows.

Definition 4.

The payoff of secondary user ${SU}_{i}$ is equal to the utility obtained minus the payment paid to the primary user:

\begin{matrix} P_{i} (q_{i}, p_{i}) = u_{i} (p_{i}) - q_{i} p_{i} . \end{matrix}

(4)

In this paper, we consider that the secondary users are rational, trying to maximize their own payoffs given a price $q_{i}$ by the secondary user.

Social Welfare. We introduce the concept of social welfare, which is equal to the utilities gained by the secondary users minus the cost paid by the primary user, which is formulated in the following definition.

Definition 5.

The social welfare of a cognitive radio network is defined as

\begin{matrix} S (p) = \sum_{i = 1}^{n} ‍ u_{i} (p_{i}) - C (p) . \end{matrix}

(5)

In this paper, we aim to maximize the social welfare of a cognitive radio network. The problem of social welfare maximization is defined in the following.

Definition 6.

The problem of maximizing the social welfare of a cognitive radio network is defined as

\begin{matrix} \max \sum_{i = 1}^{n} ‍ u_{i} (p_{i}) - C (p) \end{matrix}

(6)

\begin{matrix} s . t . p_{i} \in [0, δ_{i}], \forall i \in [1, n], \end{matrix}

(7)

where

δ_{i}

is the upper bound of

p_{i}

, determined by secondary user

{SU}_{i}

Note that the problem defined in Definition 6 is a convex optimization problem. According to [21], the problem must have an optimal solution $p^{*} = [p_{1}^{*}, p_{2}^{*}, \dots, p_{m}^{*}]$ .

The problem of maximizing the social welfare in a cognitive radio network should be solved in a distributed manner. First, if the problem is centrally solved in one point, it incurs a huge computation load on the single point. Second, the utility function of each secondary user is privacy, which leads to unknowing the exact formulation of social welfare.

4. Pricing-Based Decomposition Approach

In response to the difficulties described above, we design a distributed algorithm based on a pricing-based decomposition method, inspired by [12]. The algorithm can achieve the maximal social welfare and protect the private information for each secondary user at the same time.

We first convert the original problem in (6) into an equivalent pricing problem. The optimal spectrum allocation can be obtained when the optimal prices are achieved. Then, we propose a decomposition framework, which decouples the optimization problem into several subproblems. In the framework, each secondary user maximizes its own payoff based on the price given by the primary user. The primary user updates the price after collecting the returned spectrum demand from the secondary users. The above operations are executed iteratively until the spectrum allocation converges to the optimal solution. A price updating rule is also provided, given the insight of the condition that the optimal prices should satisfy. At last, we theoretically prove that our iterative algorithm converges to the optimum in finite steps. The notations that appeared in this paper are summarized in “Major Adopted Notations” section.

4.1. Equivalent Optimal Pricing Problem

As mentioned above, the primary user gives a price $q_{i}$ to each secondary user for leasing spectrum. According to the price, each secondary user decides the bandwidth of the spectrum $p_{i}$ it demands. Based on the pricing mechanism, the social welfare can be rewritten as follows:

\begin{array}{l} S (p) = \sum_{i = 1}^{n} ‍ u_{i} (p_{i}) - C (p) \\ = \sum_{i = 1}^{n} ‍ (u_{i} (p_{i}) - p_{i} q_{i}) + p q^{T} - C (p) \\ = \sum_{i = 1}^{n} ‍ P_{i} (q_{i}, p_{i}) + Φ (p, q) . \end{array}

(8)

Considering secondary users are rational, they will choose the bandwidth of allocated spectrum by maximizing their own payoffs given a spectrum price

\begin{matrix} {\tilde{p}}_{i} (q_{i}) = \underset{p_{i} \in [0, δ_{i}]}{\arg \max} u_{i} (p_{i}) - q_{i} p_{i} . \end{matrix}

(9)

We denote ${\tilde{p}}_{i} (q_{i})$ by ${\tilde{p}}_{i}$ for short in the next context. Therefore, the social welfare maximization problem (6) can be transformed into an equivalent optimal pricing problem, which determines the optimal price vector $q = [q_{1}, \dots, q_{n}]$ by maximizing the social welfare as follows:

\begin{matrix} \max_{q} Φ (\tilde{p}, q) + \sum_{i = 1}^{n} ‍ P_{i} (q_{i}, {\tilde{p}}_{i}) . \end{matrix}

(10)

We illustrate why the pricing problem is equivalent to the original problem briefly. Assume that the optimal solution of problem (10) is $q^{*}$ . The secondary user chooses ${\tilde{p}}_{i} (q_{i}^{*})$ depending on the optimal price $q_{i}^{*}$ by maximizing the payoff (9). After knowing ${\tilde{p}}_{i} (q_{i}^{*})$ and $q_{i}^{*}$ , the social welfare is maximized depending on (8). Therefore, the optimal solution of p can be obtained when finding the optimal price vector $q^{*} = [q_{1}^{*}, \dots, q_{n}^{*}]$ .

4.2. Pricing-Based Decomposition Framework

In this subsection, we introduce a pricing-based decomposition framework, which is shown in Figure 2.

Figure 2

The pricing-based decomposition framework.

Each secondary user computes the value of ${\tilde{p}}_{i}$ as shown in (9) locally and sends the result to the primary user. According to the collected value of ${\tilde{p}}_{i}$ , the primary user updates the price $q_{i}$ according to an updating rule, which is given in the coming context. The alternate operations are executed iteratively by the primary user and secondary users in turn until the optimal solution $q^{*}$ and $p^{*}$ is achieved.

Intuitively, the price updating rule is significant to guarantee the iterative operations eventually converge to the optimal solution. Here, we propose a pricing updating rule according to the Karuth-Kuhn-Tucker (KKT) condition. According to the convex optimization theory [22], the optimal solution $q^{*} = [q_{1}^{*}, \dots, q_{n}^{*}]$ of (10) must satisfy the KKT condition as shown in the following proposition.

Proposition 7.

An optimal price vector $q^{*} = [q_{1}^{*}, \dots, q_{n}^{*}]$ should satisfy

\begin{matrix} q_{i}^{*} = {\frac{\partial C (p)}{\partial p_{i}}|}_{p = \tilde{p}}, \forall i, \end{matrix}

(11)

where

\tilde{p} = [{\tilde{p}}_{1}, \dots, {\tilde{p}}_{n}]^{T}

with

{\tilde{p}}_{i} = {\tilde{p}}_{i} (q_{i}^{*})

given in (9).

The proof is provided in the appendix.

Given the insight of Proposition 7, we propose a price updating rule as follows:

\begin{matrix} q_{i} = (1 - ε) q_{i} + {ε \frac{\partial C (p)}{\partial p_{i}}|}_{p = \tilde{p}}, \forall i, \end{matrix}

(12)

where

ε \in (0,1]

is a tunable parameter.

Note that, in our decomposition framework, updating price is unnecessary to be executed after all ${\tilde{p}}_{i}, \forall i \in {1, \dots, n}$ are returned. The primary user can update $q_{i}$ for secondary user ${SU}_{i}$ arbitrary times before $q_{j} (j \neq i)$ is updated. It means that our decomposition framework can be realized in an asynchronous way so that the number of iterations can be largely degraded as different secondary users have different communication delay with the primary user.

4.3. Distributed Algorithm

In this subsection, we propose a distributed algorithm to maximize the social welfare of a cognitive radio network. In the distributed algorithm, the primary user and all secondary users should participate as follows. (i)

For each secondary user ${SU}_{i}$ , it maximizes the payoff $P_{i} (p_{i}, q_{i}) = u_{i} (p_{i}) - q_{i} p_{i}$ locally to obtain the value of ${\tilde{p}}_{i}$ based on the price $q_{i}$ given by the primary user. Each secondary user only needs to know its own utility function.

(ii)

For the primary user, it updates the value of $q_{i}$ based on ${\tilde{p}}_{i}$ returned from each secondary user. The price updating rule is given in (12).

The primary user generates a new price based on an original price and partial derivative ${(\partial C (p) / \partial p_{i})|}_{p = \tilde{p}}$ , which pushes the price $q_{i}$ towards the optimal value $q_{i}^{*} = \partial C (p^{*}) / \partial p_{i}$ . The details of the distributed algorithm are described in Algorithm 1.

Algorithm 1: Optimal distributed algorithm for spectrum sharing.

Input: Cost function $C (p)$ , Utility function $u_{i} (p_{i}), \forall i \in {1, \dots, n}$ .

Output: Optimal spectrum allocation $p_{i}^{*}$ .

(1) Set $q^{(0)} = θ$ , where θ is a little positive real value.

(2) $t \leftarrow 0$ , ζ is a tunable little real number and t counts the number of iterations.

(3) while $‖ {\tilde{p}}^{(t)} - {\tilde{p}}^{(t - 1)} ‖_{\infty} \leq ζ$ or $t = = 0$ or $t = = 1$ do

(4) for i from 1 to n do

(5) ${\tilde{p}}_{i}^{(t + 1)} (q_{i}) = \underset{p_{i} \in [0, δ_{i}]}{\arg \max} u_{i} (p_{i}) - q_{i} p_{i}$ ;

(6) end for

(7) for i from 1 to n do

(8) $q_{i}^{(t + 1)} = (1 - ε) q_{i}^{(t)} + {ε \frac{\partial C (p)}{\partial p_{i}} |}_{p = {\tilde{p}}^{(t + 1)}}$ ;

(9) end for

(10) $t \leftarrow t + 1$ ;

(11) end while

(12) return $p^{*} = {\tilde{p}}^{(t)}$ ;

4.4. Illustrative Example

We give an example in Figure 3, in which there are three secondary users and one primary user with the bandwidth of 73 MHZ. The parameter β of the cost function is equal to 10. The specific parameter a of each secondary user is set to $(2,5, 3)$ .

Figure 3

Illustrative example for spectrum allocation.

At the beginning of our algorithm, the primary user provides the value of $q_{i}$ for each secondary user. The original value of $q_{i}$ is equal to 5$. Each secondary user maximizes its own payoff according to 9 based on the value of $q_{i}$ . Then, each secondary user provides the value of $p_{i}$ to the primary user. The primary user updates the value of $q_{i}$ according to (12). In Figure 4, we can see that the social welfare can be achieved after ten iterations.

Figure 4

Convergence of illustrative example.

4.5. Convergence Analysis

Contraction Mapping. Many iterative algorithms can be expressed as $x (l + 1) = φ (x (l)), l = 0,1, \dots$ , where $x (\cdot) \in X$ and l denotes the number of iterations. Mapping φ is called a contraction if

\begin{matrix} ‖φ (x) - φ (y)‖ \leq κ ‖x - y‖, \forall x, y \in X, \end{matrix}

(13)

where

‖\cdot‖

is a norm and

κ \in [0,1)

is called a modulus of φ. Moreover, the mapping φ is called a pseudocontraction if there exists a fixed point

x^{*} \in X

(means

x^{*} \in φ (x^{*})

) and

\begin{matrix} ‖φ (x) - x^{*}‖ \leq ‖x - x^{*}‖, \forall x \in X . \end{matrix}

(14)

The convergence property of contraction or pseudocontractions is given in Theorem 8.

Theorem 8 (geometric convergence).

Suppose the mapping or the pseudocontraction and the modulus of φ are $κ \in [0,1)$ . Then, φ has an unique fixed point $x^{*}$ and a sequence ${x (l), l = 0,1, \dots}$ generated by $x (l + 1) = φ (x (l))$ satisfies

\begin{matrix} ‖x (l) - x^{*}‖ \leq κ^{l} ‖x (0) - x^{*}‖, \forall l \geq 0, \end{matrix}

(15)

for every choice of initial

x (0) \in X

. In particular,

x (l)

converges to

x^{*}

geometrically.

For simplicity, we use $c_{i} (p)$ to denote for $\partial C (p) / \partial p_{i}$ and $v_{i} (p_{i})$ for $u_{i}^{'} (p_{i})$ . A second order partial derivative of $C (p)$ is denoted by $\partial_{x_{j} x_{i}} C (p) = \nabla_{j} c_{i} (p)$ .

Convergence of Algorithm 1 with $ε = 1$ . We first define a notation $[λ]_{i}^{+}$ to denote the projection of $λ_{i} \in R$ onto the range $[0, τ_{i}]$ :

\begin{matrix} {[λ]}_{i}^{+} = \underset{z = [0, τ_{i}]}{\arg \max} |z - λ_{i}| . \end{matrix}

(16)

Briefly, a solution to (9) is equivalent to

\begin{matrix} {\tilde{p}}_{i} (q_{i}) = {[\arg \max_{p_{i}} u_{i} (p_{i}) - q_{i} p_{i}]}_{i}^{+} = {[v_{i}^{- 1} (q_{i})]}_{i}^{+} . \end{matrix}

(17)

Therefore, when $ε = 1$ , the price updating rule turns to $q_{i} = c_{i} (\tilde{p})$ . Substituting it into ${\tilde{p}}_{i} (q_{i})$ obtains

\begin{matrix} {\tilde{p}}_{i} = φ_{i} (\tilde{p}) = {[v_{i}^{- 1} (c_{i} (\tilde{p}))]}_{i}^{+} . \end{matrix}

(18)

Algorithm 1 applied with $ε = 1$ eventually achieves convergence under a certain condition which is given in the following proposition.

Proposition 9.

Supposing $ε = 1$ , if we have

\begin{matrix} \sum_{j = 1}^{n} ‍ |\partial_{p_{j} p_{i}} C (p)| < \min_{p_{i}} |v_{i}^{'} (p_{i})|, \forall p \in \prod_{i} ‍ [0, τ_{i}], \end{matrix}

(19)

according to Theorem 8,

{{\tilde{p}}_{i} (q_{i}^{(l)})}

generated by Algorithm 1 converges geometrically to an optimal solution

p_{i}^{*}

of (9), giving an initial value

q_{i}^{(0)}

The proof is provided in the appendix.

Convergence of Algorithm 1 with $ε < 1$ . We relax a value of ε by considering a convergence condition with $ε < 1$ . In this situation, we suppose that $\tilde{p} (q^{(l)})$ generated with each iteration l is always within a range $\prod_{i} ‍ [0, τ_{i}]$ . Therefore, we can rewrite a solution to (9) as ${\tilde{p}}_{i} (q_{i}) = v_{i}^{- 1} (q_{i})$ , which has a little difference from $ε = 1$ situation. Combining it with $q_{i} = (1 - ε) q_{i} + ε c_{i} (\tilde{p})$ , we can obtain

\begin{matrix} {\tilde{p}}_{i} = φ_{i} (\tilde{p}) = v_{i}^{- 1} ((1 - ε) v_{i} ({\tilde{p}}_{i}) + ε c_{i} (\tilde{p})) . \end{matrix}

(20)

Applied with (20), Algorithm 1 can achieve optimal under a convergence condition in the following proposition.

Proposition 10.

Set ${\tilde{p}}_{i} (q_{i}^{(0)})$ to be 0 for all i or $τ_{i}$ for all i. If we have

\begin{array}{l} 0 \leq ε \leq {(1 + \frac{\partial_{p_{j} p_{i}} C (p)}{c_{i}^{'} (p_{i})})}^{- 1}, \sum_{j \neq i} \partial_{p_{j} p_{i}} C (p) \leq 0, \\ \forall p \in \prod_{i} ‍ [0, τ_{i}], \end{array}

(21)

φ_{i}

given by (18) is a pseudocondition for all

p_{i}

between

p_{i} (q_{i} (0))

and

p_{i}^{*}

; according to Theorem 8,

{{\tilde{p}}_{i} (q_{i}^{(l)})}

generated by the Algorithm 1 converges geometrically to an optimal solution

p_{i}^{*}

of (9).

The proof is provided in the appendix.

5. Simulations

5.1. Methodology and Simulation Setup

We perform simulations to evaluate the performance of our optimal distributed algorithm, compared with two baseline algorithms as follows.

Distributed Weighted Allocation Scheme (DWAS). First, the primary user provides an initial value $q_{0}$ for all secondary users. Each secondary user ${SU}_{i}$ returns the value of $\tilde{p_{i}} (q_{0})$ by maximizing $P (q_{i}, p_{i})$ . Next, the primary user decides the final value of $q_{i}$ , $\forall i \in {1, \dots, n}$ by maximizing $Φ (q, p)$ , assuming that $u_{i} (p_{i})$ is a linear function of $p_{i}$ ; that is, $u_{i} (p_{i}) = b_{i} p_{i}$ . $b_{i}$ represents the weight of secondary user ${SU}_{i}$ , which is computed as $\tilde{p_{i}} (q_{0}) / q_{0}$ . After receiving $q_{i}$ , each secondary user computes its optimal $\tilde{p_{i}} (q_{i})$ .

Centralized Heuristic Algorithm (CHA). To illustrate the good performance of our algorithm, we add another heuristic algorithm to compare with our algorithm. Our objective is maximizing social welfare which is defined as utilities of all the secondary users minus the cost of primary user. The utility function of secondary user is concave and the cost function of primary user is convex. When utilities of all the secondary users equal cost of primary user, there is a size of bandwidth called $\hat{p}$ . So, the optimal size of bandwidth is between zero and $\hat{p}$ . The optimal size of bandwidth is approximately equal to $\hat{p} / 2$ . Then, the size of bandwidth obtained by each secondary user is $\hat{p} / 2$ . The primary user maximizes the profit which is defined as $\hat{p} q^{T} - C (\hat{p})$ to get the optimal price $\hat{q}$ .

In addition to the DWAS and CHA, we also compare our algorithm with the optimal value. The optimal value is obtained by maximizing the social welfare directly.

The evaluation of our algorithm is performed from two aspects, including the network performance and the convergence speed. The metrics of network performance are the social welfare and the total allocated spectrum. We perform the simulations with varying two factors: the number of secondary users and the value of β. The metric of convergence speed is the number of iterations. The simulations are performed under different numbers of secondary users and values of ε. The initial values of $q_{i}$ , $\forall i \in {1,2, \dots, n}$ in our proposed algorithm and the DWAS are set to 1. The default values of β and ε are 0.2 and 0.1, respectively. The values of $a_{i}$ are standard uniformly distributed in the open interval $(0.5,1)$ .

5.2. Impact of Number of Secondary Users

We first study the performance of our algorithm, the DWAS, and the CHA under different numbers of secondary users, compared with the optimum. The results are shown in Figures 6 and 9.

Figure 6 shows that the social welfare obtained by our algorithm performs as well as the optimum and much better than the DWAS and the CHA. The social welfare obtained by the DWAS performs much better than the CHA. The social welfare obtained by our algorithm, the DWAS, and the CHA increases with the increasing number of secondary users. When there are 20 secondary users, the social welfare obtained by our algorithm is 50.34% higher than the DWAS. The social welfare obtained by our algorithm is 20.20% higher than the CHA.

In Figure 9, the spectrum allocated by our algorithm is the same as the optimum and more than the DWAS and the CHA. The spectrum obtained by our algorithm, the DWAS, and the CHA increases with the increasing number of secondary users. However, the spectrum allocated by DWAS is always less than the spectrum allocated by our algorithm. The spectrum allocated by CHA is always less than the spectrum allocated by the DWAS. When there are 20 secondary users, the allocated spectrum obtained by our algorithm is 96.23% more than the DWAS. The allocated spectrum obtained by the DWAS is 80.43% more than the CHA.

5.3. Effect of β

We next study the performance of our algorithm, the DWAS, and the CHA under different β, compared with the optimum. The results are shown in Figures 7 and 10.

Figure 7 shows that the social welfare achieved by our algorithm performs as well as the optimum, more than the DWAS and the the CHA. The social welfare achieved by the DWAS performs more than the CHA. The social welfare obtained by our algorithm, the DWAS, and the CHA decreases with the increasing value of β. When there are 20 secondary users, the social welfare obtained by our algorithm is 40% more than the DWAS. The social welfare obtained by the DWAS is 20.23% more than the CHA.

In Figure 10, the spectrum allocated by our algorithm is the same as the optimum, more than the DWAS and the CHA. For our algorithm, the DWAS, and the CHA, the allocated spectrum decreases when the value of β increases. When there are 20 secondary users, the allocated spectrum obtained by our algorithm is 97.43% more than the DWAS. The allocated spectrum obtained by the DWAS is 89.45% more than the CHA.

5.4. Convergence Speed

In this subsection, we study the convergence speed of our algorithm under different numbers of secondary users and values of ε. The results are shown in Figures 5, 8, and 11.

Figure 5

Social welfare achieved with the number of iterations.

Figure 6

Social welfare comparison of different algorithms with varying number of secondary users.

Figure 7

Social welfare comparison of different algorithms with varying β.

Figure 8

Convergence of Algorithm 1 with different number of secondary users.

Figure 9

Allocated spectrum comparison of different algorithms with varying number of secondary users.

Figure 10

Allocated spectrum comparison of different algorithms with varying β.

Figure 11

Convergence of Algorithm 1 with different value of parameter ε.

Figure 5 plots the social welfare achieved by our algorithm in each iteration, when the value of system parameter ε is 0.1 and 0.15, respectively. Under the two settings, we can see that 99.9% of the optimal social welfare is achieved in the first ten iterations, which implies that our algorithm converges quickly.

In Figure 8, we study simulations of our algorithm when the number of secondary users is 20, 40, 60, 80, and 100, respectively. The value of parameter ε is 0.1 and 0.15. The numbers of iterations under different numbers of secondary users and different values of ε are close, which illustrates our algorithm is adapted to large-scale cognitive radio networks.

Figure 11 shows that the convergence speed of our algorithm under the condition of the value of ε varying from 0.1 to 0.15. The number of secondary users is 60 and 100. The number of iterations under different values of ε is less than 32. The higher the value of system parameter ε, the faster the convergence speed. Our algorithm converges fast under varying values of ε.

6. Conclusion

We have studied the problem of maximizing the social welfare in spectrum sharing in a cognitive radio network. We first formulate the cost of the primary user and the utility of each secondary user. To protect the private information of secondary users, we propose a distributed algorithm based on the pricing-based decomposition framework. The distributed algorithm is executed iteratively by the primary user and each secondary user in turn. Theoretical analysis is conducted to demonstrate that the algorithm converges to the optimal solution. Extensive simulation results show that our proposed algorithm achieves the maximum social welfare and converges quickly.

Footnotes

Appendices

Major Adopted Notations

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The research is supported by China 863 Program (no. 2013AA01A601). This work is also supported by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1158, PCSIRT), China.

References

Gupta

Kumar

P. R.

The capacity of wireless networks

IEEE Transactions on Information Theory 2000 46 2 388 404

MR1748976

2-s2.0-33747142749

10.1109/18.825799

Mitola

III Maguire

G. Q.

Jr.

Cognitive radio: making software radios more personal

IEEE Personal Communications 1999 6 4 13 18

10.1109/98.788210

2-s2.0-0033171330

Haykin

Cognitive radio: brain-empowered wireless communications

IEEE Journal on Selected Areas in Communications 2005 23 2 201 220

10.1109/JSAC.2004.839380

2-s2.0-13844296408

Zhao

Sadler

B. M.

A survey of dynamic spectrum access

IEEE Signal Processing Magazine 2007 24 3 79 89

10.1109/MSP.2007.361604

2-s2.0-34249728222

Competition and cooperation in multi-user communication environments [Ph.D. thesis] 2002

Stanford University

Zander

Kim

S. L.

Almgren

Queseth

Radio Resource Management for Wireless Networks 2001

Artech House

Niyato

Hossain

A game-theoretic approach to competitive spectrum sharing in cognitive radio networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′07)

March 2007

16 20

2-s2.0-36348951960

10.1109/WCNC.2007.9

Wang

Gao

Chen

H.-H.

Spectrum Sharing in cognitive radio networks: an auction-based approach

IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 2010 40 3 587 596

10.1109/TSMCB.2009.2034630

2-s2.0-77952582544

Han

Pandana

Liu

K. J. K.

Distributive opportunistic spectrum access for cognitive radio using correlated equilibrium and no-regret learning

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′07)

March 2007

Hong Kong

11 15

10.1109/WCNC.2007.8

2-s2.0-36348971086

10.

Peng

Zheng

Zhao

B. Y.

Utilization and fairness in spectrum assignment for opportunistic spectrum access

Mobile Networks and Applications 2006 11 4 555 576

10.1007/s11036-006-7322-y

2-s2.0-33745477695

11.

Ileri

Samardzija

Mandayam

N. B.

Demand responsive pricing and competitive spectrum allocation via a spectrum server

Proceedings of the IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks

2005

12.

Niu

An efficient distributed algorithm for resource allocation in large-scale coupled systems

Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM ′13)

April 2013

Turin, Italy

1501 1509

10.1109/INFCOM.2013.6566945

2-s2.0-84883059774

13.

Zhu

L. M.

Probabilistic approach to provisioning guaranteed QoS for distributed event detection

Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM ′08)

April 2008

1265 1273

10.1109/INFOCOM.2007.108

2-s2.0-51349099461

14.

Zhu

Building wifi radio map with zigbee sen sor networks

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′12)

March 2012

2926 2930

10.1109/INFCOM.2012.6195731

2-s2.0-84861618801

15.

Zhu

Bao

On maximizing delay-constrained coverage of urban vehicular networks

IEEE Journal on Selected Areas in Communications 2012 30 4 804 817

10.1109/JSAC.2012.120514

2-s2.0-84860007212

16.

Zhu

Trajectory improves data delivery in urban vehicular networks

IEEE Transactions on Parallel and Distributed Systems 2014 25 4 1089 1100

10.1109/TPDS.2013.118

2-s2.0-84896273328

17.

Feng

Yang

Joint transport, routing and spectrum sharing optimization for wireless networks with frequency-agile radios

Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM ′09)

April 2009

1665 1673

10.1109/INFCOM.2009.5062085

2-s2.0-70349659401

18.

Shi

Hou

Y. T.

A distributed optimization algorithm for multi-hop cognitive radio networks

Proceedings of the IEEE 27th Conference on Computer Communications (INFOCOM ′08)

April 2008

Phoenix, Ariz, USA

10.1109/INFOCOM.2008.186

19.

Raman

Yates

R. D.

Mandayam

N. B.

Scheduling variable rate links via a spectrum server

Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks

November 2005

110 118

10.1109/DYSPAN.2005.1542624

2-s2.0-33749070110

20.

Chateauneuf

Cohen

Risk seeking with diminishing marginal utility in a non-expected utility model

Journal of Risk and Uncertainty 1994 9 1 77 91

10.1007/BF01073404

ZBL0810.90006

2-s2.0-21344484524

21.

Boyd

Vandenberghe

Convex Optimization 2004

Cambridge University Press

10.1017/CBO9780511804441

MR2061575

22.

Bertsekas

D. P.

Nedi

Ozdaglar

A. E.

Convex Analysis and Optimization 2003