Sensor Clustering and Sensing Technology for Optimal Throughput of Sensor-Aided Cognitive Radio Networks Supporting Multiple Licensed Channels

Abstract

In cognitive radio networks, secondary users may not sense licensed channels efficiently due to problems of fading channel, shadowing, unfamiliar environment, and so forth. To cope with the limitation, a pervasive sensor network can cooperate with cognitive radio network, which is called sensor-aided cognitive radio network. In the paper, we investigate sensor clustering and sensing time of each sensor cluster with aiming at achieving optimal throughput of sensor-aided cognitive radio network supporting multiple licensed channels. Moreover, the minimum throughput requirement of cognitive radio user is also guaranteed in the sensor clustering problem. To do this, we formulate the throughput maximization problem as a mixed-integer nonlinear programming and utilize the Branch and Bound algorithm to solve it. We also propose an heuristic algorithm which can provide similar performance to that of the Branch and Bound algorithm while reducing computation complexity significantly.

1. Introduction

The demand for radio spectrum has rapidly increased due to the rapid growth of wireless mobile devices and cellular networks, such as smartphones, along with booming of online applications for multimedia transferring, gaming, and so forth. We may face the problem of spectrum scarcity for huge demand of spectral usage. In fact, according to the FCC [1], frequency spectrum is being used less efficiently than its scarcity. Some frequency spectrum is underutilized, while some is heavily used. Cognitive radio (CR) technology of which a fundamental concept was first introduced by Dr. Mitola, allows cognitive radio users or secondary users (SUs) to utilize the same licensed channels to improve channel efficiency [2].

In CR context, channel access of SUs must not affect the channel usage of licensed users or primary users (PUs). Hence, before accessing any licensed channel, spectrum sensing is a prerequisite for detecting the absence or presence of PUs, such that SUs can utilize the channel if the channel is not occupied by PUs and SUs can avoid the unexpected collision with PUs during a channel access. Furthermore, while utilizing licensed channels, spectrum sensing needs to be frequently performed for detecting any return to the licensed channel by the PUs to immediately vacate the channel. Several sensing techniques have been proposed so far such as energy detection, waveform-based sensing, cyclostationary feature detection, matched filtering, and compressed sensing [3, 4]. Among these sensing techniques, energy detection method is most commonly used due to its easy deployment [5, 6]. Since single spectrum sensing by SU without any knowledge of PU locations degrades the sensing performance, a cooperative spectrum sensing (CSS) where multiple SUs work together can obtain more accurate awareness of PUs presence [4]. In CSS, a global decision at fusion center is based on local decisions made at sensor nodes that directly perform independent spectrum sensing on the same licensed channel.

Like CSS, the cooperation of some SUs to detect the presence of the PU can obtain accurate sensing results. However, this approach incurs high cost and high energy consumption. A more appealing approach is to perform sensing by cost-effective dedicated sensor network. Use of the sensor network for spectrum sensing is being explored by regulatory bodies like the FCC [7], which has invited experts to draft proposals for the use of the sensor network with low cost/energy/delay for enhanced spectrum sensing. In the approach called sensor-aided cognitive radio network, wireless sensor network is used to support the cognitive radio network in detecting activity of the PU network.

In fact, WSNs have been widely used in various practical applications, such as gathering of information on environment and monitoring of civilian, military, and community health status [8–10]. In the WSNs, multiple sensor nodes are distributed over the network in order to sense certain environmental properties and then send sensing data to a cluster head or sink such that a decision corresponding to arising events may be made quickly. Moreover, to evaluate network performance, many works in this research area have mainly focused on problems of clustering sensor nodes, routing between sensor nodes, [11] and processing collected data at a data fusion center. For example, in [12], the problem of gathering sensed information along with clustering protocol consideration is investigated. Base station forms clusters of sensor nodes based on information on both energy and distance of all sensor nodes. Among cluster heads, a leader node is appointed to a data transmission to the base station. In [13], cluster head selection for sensor network lifetime is addressed. The work proposed a method for energy-aware cluster of sensor nodes solved by particle swarm optimization approach instead of adopting a traditional optimization technique under constraints of residual energy, location, node degree, and head count (i.e., how frequently a node is selected as a cluster head) of probable cluster heads which affect the packet retransmissions over paths connected to the cluster head. In [14], the authors focused on evaluating performance of data aggregation at data fusion center for a WSN which is divided into sensor clusters. A dynamic clustering and aggregation strategy were investigated for local data at the sensor node and global data aggregation at the cluster head. They proposed a clustering algorithm comprising two phases. In first phase, sensor nodes which sense the same category of data are grouped in the same cluster. In second phase, it guarantees that all sensor nodes are assigned to the clusters, formed in the first phase, based on the least-divergent clusters.

In this paper, we investigate sensor clustering and sensing time of each sensor cluster in sensor-aided cognitive radio network with aiming at achieving optimal throughput of cognitive radio networks supporting multiple licensed channels under the constraint of primary user collision threshold. So far, the problem of throughput maximization for cognitive radios has been investigated in several works. In [15], for example, cooperative spectrum sensing among SUs is addressed to maximize the throughput obtained on a single licensed channel. This work offers many open issues for CSS in CRN so far. In [16], the authors focused on a method for sensing licensed channels in such a way that sensing order of secondary users over the licensed channel is studied in two modes where sensing time is designed in slotted time and continuous time. In [17], the problem of minimizing total energy consumption of secondary users for spectrum sensing is studied using the outer linearization method. However, in these works, cooperation between pervasive sensor network and CRN is not fully investigated for sensor-aided cognitive radio network especially in the case of multiple licensed channels. Therefore, in this paper, we formulate the throughput maximization problem for sensor-aided cognitive radio network as a mixed-integer nonlinear programming to find optimal sensor clustering and sensing time of the corresponding sensor cluster. To solve the formulated problem, the Branch and Bound algorithm is adopted. Furthermore, we also propose heuristic algorithm which can provide similar performance to that of the Branch and Bound algorithm while reducing computation complexity significantly.

The remainder of this paper is organized as follows. In Section 2, the system model is described and the mathematical formulation is presented. In Section 3, we present the problem formulation to evaluate throughput of pervasive sensor-aided cognitive radio networks. In Section 4, we discuss methodology and algorithms for sensor clustering problem. Simulation results are provided in Section 5. Finally, we draw main conclusions.

2. System Model

In the paper, we consider sensor-aided cognitive radio network shown in Figure 1 where the request-service model is used. That is, CRNs request WSN to sense licensed channels and WSN supports the CRN in detecting activity of the PU network. The WSN consists of N sensor nodes with the same sensing capability and performs spectrum sensing for CRNs. M licensed channels are considered to be utilized in a synchronized time-slotted fashion $(N \geq M)$ .

Figure 1

Sensor-aided cognitive radio network in which request-service model is used.

For an effective interaction between WSN and CRNs, CRNs first need to gather channel usage information of each channel from one pair of SU transmitter and SU receiver, which is consisted of minimum amount of data, denoted as $R_{m}^{r e q}$ , and maximum channel capacity, denoted as $C_{m}$ , where m is index of licensed channels. In the paper, for simplicity, only one pair of SU transmitter and SU receiver will utilize a licensed channel. Based on channel usage information, CRN assigns each pair of SUs a licensed channel for opportunistic data transmission. Next, CRNs send channel usage information of each pair of SUs to fusion center (FC) of WSN. Based on channel usage information, FC will divide its N sensors into M sensor clusters and all assigned sensors in each cluster will therefore perform spectrum sensing on a licensed channel. In each time slot, after sensing on a licensed channel, sensor nodes will report a 1 bit hard decision to FC over control channel(s) which indicates the licensed channel is busy or idle. With the 1 bit hard decision, reporting time is short and is the same for all sensor nodes. With local decisions of sensors in each sensor cluster, FC finally makes a final decision using “OR” rule and reports final decision on licensed channel states to CRNs. When the licensed channels are idle, data transmissions will be performed by pairs of SUs. Here, it is noteworthy that main objective of the paper is to determine optimal sensor clusters and sensing time of each sensor cluster where throughput of CRNs is maximized, while some constraints are satisfied.

We assume that all sensors are energy detectors. Correspondingly, during the duration of sensing, each sensor node gathers a considerable number of energy samples of PU signal on an assigned licensed channel, measures total of these energy samples, and compares the total energy with energy threshold to make a local decision on the absence/presence of the primary user. Sensor nodes then report the local decision to the FC over a common control channel. We denote by $S_{m}$ and $s_{m, n}$ a sensor cluster m, of which sensors perform CSS on licensed channel m, and a sensor n which performs spectrum sensing on licensed channel m, respectively.

At sensor node $s_{m, n}$ , local probability of detection $P_{m, n}^{d}$ and local probability of false alarm $P_{m, n}^{f}$ which are the probabilities that a PU transmitting its data on the channel m can be detected and that a free licensed channel m cannot be detected by the sensor $s_{m, n}$ , respectively, can be determined as follows [15]:

\begin{matrix} P_{m, n}^{f} = Q \{ξ_{m, n} y_{m, n} + δ_{m, n} \sqrt{τ_{m, n}}\}, \\ P_{m, n}^{d} = Q \{(x_{m, n} - δ_{m, n} \sqrt{τ_{m, n}}) ξ_{m, n}^{- 1}\}, \end{matrix}

(1)

where

x_{m, n} = Q^{- 1} (P_{m, n}^{f})

and

y_{m, n} = Q^{- 1} (P_{m, n}^{d})

are inverse translations of local probability of false alarm and local probability of detection, respectively.

ξ_{m, n} = \sqrt{2 γ_{m, n} + 1}

δ_{m, n} = γ_{m, n} \sqrt{f_{s}}

γ_{m, n}

is the SNR received at the sensor node

s_{m, n}

, and

f_{s}

is the sampling frequency of PU signal for the total energy (

ξ_{m, n} > 0, δ_{m, n} > 0

), and

τ_{m, n}

is the sensing time of the sensor

s_{m, n}

Q (x)

is the complementary distribution function of a standard Gaussian random variable, which can be written as follows:

\begin{matrix} Q (x) = \frac{1}{\sqrt{2 π}} \int_{x}^{\infty} \exp (- \frac{t^{2}}{2}) d t . \end{matrix}

(2)

From (1), sensing time $τ_{m, n}$ can be extracted as follows:

\begin{matrix} τ_{m, n} = {\{(x_{m, n} - y_{m, n} ξ_{m, n}) δ_{m, n}^{- 1}\}}^{2} . \end{matrix}

(3)

Furthermore, we can also extract constraints which are related to the variables $x_{m, n}$ and $y_{m, n}$ to guarantee positive values of the sensing time, which are expressed as follows:

\begin{matrix} x_{m, n} - y_{m, n} ξ_{m, n} = δ_{m, n} \sqrt{τ_{m, n}} > 0 . \end{matrix}

(4)

For data aggregation from multiple sensors, at FC or a cluster head, a combination rule is determined. Throughout the paper, we assume that the “OR” rule is applied in making a global decision such that licensed channel m is determined to be available for SUs if all sensors in sensor cluster $S_{m}$ report the same result of PU absence to FC. Thus, the global probability of detection, $Q_{m}^{D}$ , and the global probability of false alarm, $Q_{m}^{F}$ , for channel m are given by

\begin{matrix} Q_{m}^{D} = 1 - \prod_{n \in S_{m}} (1 - P_{m, n}^{d}), \\ Q_{m}^{F} = 1 - \prod_{n \in S_{m}} (1 - P_{m, n}^{f}) . \end{matrix}

(5)

In CSS, a data transmission is only implemented on channel m immediately after all reports of sensor cluster $S_{m}$ have been sent to FC, and channel m is deemed available. Thus the transmission time in a time slot can be expressed as

\begin{matrix} t_{m}^{T r} = T - τ_{m} = T - \max (τ_{m, n} + t_{m, n}^{r}), \end{matrix}

(6)

where T is slot duration,

t_{m, n}^{r}

is reporting time of sensor

s_{m, n}

, and

τ_{m}

is a time period from the beginning of a time slot to the point when all sensors in

S_{m}

must finish sensing licensed channel and report the sensing results. In this paper, the reporting time is assumed to be fixed. An example of time slot structure and transmission for global decision is shown in Figure 2, in which four sensors perform spectrum sensing on the same licensed channel m with their sensing time as

τ_{m, n}

, where n is from 1 to 4. In the example, sensor 3 spends more time for sensing the channel than others, and the transmission time

t_{m}^{T r}

T - τ_{m, 3}

when the channel is free.

Figure 2

Time slot structure for a sensor cluster in sensing and a pair of SUs in transmission on m-channel.

After local sensing, sensor nodes will report local sensing results to the FC. Collision may occur during reporting time when more than one sensor node sends local decision at the same time. Since a short time is required for reporting 1 bit local decision, we can design an efficient reporting method by utilizing contention and parallel reporting mechanism (parallel carrier frequencies) as follows: since each sensor node only reports a 1 bit hard local decision to the FC regarding the assigned licensed channel, the control channel can be reduced to a pair of frequencies corresponding to two possible values of a sensing decision per licensed channel. For example, for the ith licensed channel, two carrier frequencies, $f_{0 i} = (2405 + i)$ MHz for $H_{0}$ and $f_{1 i} = (2406 + i)$ MHz for $H_{1}$ , can be utilized when 2.4 GHz ISM Band is used for control channel, where i is index for licensed channel and $i = 1, \dots, M$ . Thus, sensor nodes that sense the ith licensed channel will only monitor two predetermined frequencies, that is, $f_{0 i}$ and $f_{1 i}$ , after sensing and the node that wins the contention will transmit its local decision on only one predefined frequency to the FC according to its sensing decision. Furthermore, each sensor node can self-determine an offset time for contention which is dependent on the reliability value of its sensing data. This offset time can be used for competing the transmission turn with other sensor nodes. Even in the case of two senor nodes which sense same licensed channel and have the same offset value a collision still will not occur since the two nodes will transmit local decision with the same frequency, and, at the receiver side, two transmitted frequencies can be considered as two versions of a multipath signal. Therefore, the collision and reporting mechanism to avoid the collision are not a big issue in the paper.

3. Problem Statement and Formulation

As previously mentioned, to evaluate the quality of the sensor clustering, we evaluate the performance of sensor-aided cognitive radio in terms of achievable throughput. Note that before sending request to sensor network for channel sensing CRNs also ask their SUs for perceiving demand of the minimum throughput that they want to attain.

Now we basically formulate the problem of throughput maximization for the CRNs as follows:

\begin{matrix} \max R = \sum_{m = 1}^{M} R_{m}, \\ subject  to Q_{m}^{D} \geq Q_{t h}^{d}, \forall m, \\ R_{m} \geq R_{m}^{r e q}, \forall m, \end{matrix}

(7)

where

Q_{t h}^{d}

is the desired threshold of global detection probability.

R_{m}

and

R_{m}^{r e q}

, respectively, are the achievable throughput obtained by SUs and minimum throughput requested by these users in sharing channel m. To get

R_{m}^{r e q}

, the CRN should know the transmission rate of SUs on channel m. This information is assumed to be shared among the networks.

The above formulation for sensor clustering represents two basic aspects of our problem as follows. First, it guarantees that global probability of detecting PUs needs to be greater than a designed threshold for protecting PUs during the licensed channel access. Second, clustering sensors in sensor network is to maximize the total throughput obtained by CRNs. However, this must satisfy requests of CRNs, that is, the minimum of throughput that CRNs attains on each channel as SUs access the channels in an opportunistic manner.

Considering the case where SUs can perfectly utilize a licensed channel, for example, sensing time is extremely short and sensing is perfectly performed in detecting channel status. Therefore, no collision between SUs and PUs occurs, and free time slots are all utilized for data transmission. In such case, the achievable throughput would be maximal and this type of throughput can be absolutely estimated. Let us further assume $C_{m}$ to be the channel capacity obtained by SUs on licensed channel m.

Due to the less perfect sensing ability of sensors, the achievable throughput is therefore degraded because of mandatorily taking time for channel sensing and regrettably missing utilization of few free time slots as well. Obviously, two factors which are sensing time and probability of false alarm can be adjusted to control achievable throughput. As a result, the achievable throughput obtained by SUs on a single licensed channel m can be calculated as follows:

\begin{matrix} R_{m} = (T - τ_{m}) (1 - Q_{m}^{F}) \frac{C_{m}}{T} . \end{matrix}

(8)

The total achievable throughput of the CRNs is expanded in taking a consideration of multiple licensed channels which can be expressed as follows:

\begin{matrix} \sum_{m = 1}^{M} R_{m} = \sum_{m = 1}^{M} C_{m} - \frac{1}{T} \sum_{m = 1}^{M} C_{m} \{T Q_{m}^{F} + τ_{m} (1 - Q_{m}^{F})\} . \end{matrix}

(9)

In this expression, the first term on the right hand is a constant and the total achievable throughput merely depends on channel capacity $C_{m}$ . Correspondingly, the problem of throughput maximization in (7) can be converted to a minimization of the second term of the expression (9). This problem will be further discussed in Section 4.

4. Solution Methodology and Algorithms

In this section, we present how to form sensor clusters among sensor nodes for CSSs. Although the whole system is exploiting M licensed channels, more than M sensor clusters can be considered for various purposes, in which a few sensor clusters can perform CSS on the same channel. Without loss of generality in this paper, we only consider M sensor clusters, that is, each sensor cluster for a single licensed channel.

For each sensor, we define indicating variables which are continuous variables and are denoted as $a_{m, n} (0 \leq a_{m, n} \leq 1)$ to determine whether sensor n is to join cluster m or not in such a way that the sensor will join the cluster if variable $a_{m, n}$ is set to one; otherwise the variable $a_{m, n}$ is set to zero. We can define $A_{m \times n} = [a_{m, n} | m = 1, \dots, M, n = 1, \dots, N]$ as a sensor assignment matrix in which each element indicates whether a corresponding sensor will join a cluster or not. This matrix will be used in the next subsection to explain algorithms. However, to relax the constraints on these indicating variables in simulation, we further define new variables $z_{m, n}$ , which follow the relation $z_{m, n} = Q^{- 1} (a_{m, n})$ , where the inverse function $Q^{- 1} (a_{m, n})$ can be computed by using (2). Therefore, the value range of $a_{m, n}$ in $[0,1]$ is in correspondence with the value range of $z_{m, n}$ in $(- \infty, + \infty)$ .

By inserting the indicating variables into (5), subsequently we can have the following equations:

\begin{matrix} Q_{m}^{F} = 1 - \prod_{n \in S_{m}} [1 - a_{m, n} P_{m, n}^{f}] \\ = 1 - \prod_{n \in S_{m}} [1 - Q (z_{m, n}) Q (x_{m, n})], \end{matrix}

(10)

\begin{matrix} Q_{m}^{D} = 1 - \prod_{n \in S_{m}} [1 - a_{m, n} P_{m, n}^{d}] \\ = 1 - \prod_{n \in S_{m}} [1 - Q (z_{m, n}) Q (y_{m, n})] . \end{matrix}

(11)

We can infer two cases from the above expressions as follows. First, value of variable $z_{m, n}$ approaches $- 4 (z_{m, n} \to - 4)$ and then value of indicating variable $a_{m, n}$ will approach one $(a_{m, n} \to 1)$ which indicates a sensor assignment because the terms $Q (x_{m, n})$ in (10) and $Q (y_{m, n})$ in (11) still affect global probability of false alarm and detection, respectively. Second, value of variable $z_{m, n}$ approaches +4 $(z_{m, n} \to + 4)$ and then value of variable $a_{m, n}$ will approach zero $(a_{m, n} \to 0)$ . In this case, the terms $Q (x_{m, n})$ and $Q (y_{m, n})$ will not affect global probability of false alarm and detection with respect to the sensor cluster m, respectively; that is, the sensor n does not join the cluster m. It is clear that, due to the physical ability, a sensor can only join a single sensor cluster and sense licensed channel corresponding to the cluster such that $\sum_{m = 1}^{M} a_{m, n} = 1$ . Without loss of generality, the constraint is acceptable as $\sum_{m = 1}^{M} Q (z_{m, n}) \leq 1 \forall n$ .

According to (9), the throughput maximization problem can be changed to a minimization problem, such as $\max R \to \min U$ . Hence, we reformulate the problem as follows:

\begin{matrix} \{z_{m, n}^{*}; x_{m, n}^{*}; y_{m, n}^{*}\} = \underset{x_{m, n}; y_{m, n}; z_{m, n}}{\arg \min} U = \underset{x_{m, n}; y_{m, n}; z_{m, n}}{\arg \min} [\sum_{m = 1}^{M} U_{m} = \sum_{m = 1}^{M} C_{m} \{T Q_{m}^{F} + τ_{m} (1 - Q_{m}^{F})\}] \end{matrix}

(12)

subject to

\begin{matrix} Q_{m}^{D} \geq Q_{t h}^{d}, \forall m, \\ R_{m} \geq R_{m}^{r e q}, \forall m, \\ \sum_{m = 1}^{M} Q (z_{m, n}) \leq 1, \forall n, \\ x_{m, n} - y_{m, n} ξ_{m, n} > 0, \forall x_{m, n}, y_{m, n} . \end{matrix}

(13)

The above problem is known as mixed-integer nonlinear programming (MINLP). Here, $U (\cdot)$ is convex function of $x_{m, n}$ and $y_{m, n}$ and is also a decreasing function of $y_{m, n}$ , which is proven in the appendix. In first stage, the objective is to find an optimal solution, which is an optimal value set of both continuous variables $z_{m, n}$ , which are expected to be −4 or +4, and continuous variables $x_{m, n}$ and $y_{m, n}$ . Intuitively, $z_{m, n}$ are integer variables which are relaxed continuous variables. In second stage, based on the integer value of variables $z_{m, n}$ , FC will assign sensor $n^{*}$ to cluster $m^{*}$ which is indicated by $z_{n^{*}, m^{*}} = - 4$ . Under the sensor assignment, from $x_{m^{*}, n^{*}}$ and $y_{m^{*}, n^{*}}$ , the sensing time $τ_{m^{*}, n^{*}}$ of sensor $n^{*}$ in cluster $m^{*}$ can be determined and computed by (3).

The optimal integer value of variables $z_{m, n}$ can be determined by applying the Branch and Bound algorithm [18] of which pseudocode is presented in Pseudocode 1. This algorithm can be explained as follows. In the Branch and Bound algorithm, a subproblem is defined as the problem to find $x_{m, n}$ , $y_{m, n}$ , and $z_{m, n} (m \neq i a n d n \neq j)$ which minimizes objective function U in (12) when a certain variable $z_{i, j}$ is fixed at $- 4$ or $+ 4$ . Since each variable $z_{m, n}$ can create two new subproblems in which the variable $z_{m, n}$ is fixed at $- 4$ or $+ 4$ , new subproblems will be created and solved during Branch and Bound algorithm implementation. Therefore, a list of unsolved subproblems denoted as L is maintained to track subproblem solving. At first, L can be simply created by choosing a variable $z_{m, n}$ to create two new unsolved subproblems such that $L = {z_{m, n} = - 4, z_{m, n} = + 4 | m \in {1, \dots, M}$ , and $n \in {1, \dots, N}}$ (line (1)). Then, a subproblem from L is selected and solved to get a solution and minimum value of U denoted as LB such that $L B = \min (U)$ . The chosen subproblem is removed from L. If the current subproblem is infeasible, which means no solution is found, we consider choosing another subproblem in L to solve. If the current subproblem is feasible, we compare LB with UB, where UB stores the best objective value of the previous integer solutions. Due to minimization problem, in the case where the current objective value LB is less than UB, we check whether the solution is an integer solution or not. If the current solution is an integer solution in which all variables $z_{m, n}$ are $- 4$ or $+ 4$ , UB is updated by the current objective value LB (line (12)); the current integer solution is stored (line (13)). If the current solution is not integer solution, there exists at least one variable $z_{m, n}$ with a value between $- 4$ and $+ 4$ . In this case, one new variable $z_{m, n}$ with fractional value must be selected and two new unsolved subproblems are created and added to L (lines $(15) – (18)$ ). In the case where the current objective value of a subproblem is greater than UB, the current subproblem cannot yield a better integer solution than the stored one. In this case, we stop creating new subproblems (line (21)) and the current branch is cut out of the Branch and Bound algorithm implementation.

Pseudocode 1: Pseudocode of Branch and Bound algorithm for sensor clustering.

Input: $C_{m}$ , $R_{m}^{req}$ , and $γ_{m, n}$

Output: $A_{m \times n}$ and $τ_{m, n}$

(1) Initiate: a list of unsolved subproblems, L

(2) $U B \leftarrow + \infty$ {Best found}

(3) while $\{L$ ≠ empty} do

(4) Select an unsolved subproblem from L

(5) Remove the chosen subproblem from L

(6) Solve the subproblem, $L B \leftarrow \min (U)$

(7) if {subproblem is infeasible} then

(8) Do nothing {since $L B$ = Φ}

(9) else

(10) if $\{L B < U B \}$ then

(11) if {solution is an integer solution} then

(12) Update: $U B \leftarrow L B$

(13) Store the integer solution

(14) else

(15) Find variable $z_{m, n}$ with fractional value

(16) Create a new subproblem with $z_{m, n} = - 4$

(17) Create a new subproblem with $z_{m, n} = + 4$

(18) Add two new subproblems to L

(19) end if

(20) else

(21) Stop creating new subproblems in current branch

(22) end if

(23) end if

(24) end while

To demonstrate the Branch and Bound algorithm, we provide an example as follows: WSN has 2 sensor nodes ( $N = 2$ ) and two licensed channels $(M = 2)$ . Figure 3 shows the Branch and Bound tree for the example. First, the variable $z_{1,1}$ is chosen to create two new subproblems with $z_{1,1} = - 4$ and $z_{1,1} = + 4$ (line (1) in Pseudocode 1). In the paper, we simply denote the list of unsolved subproblems as $L = {z_{1,1} = - 4, z_{1,1} = + 4}$ .

Figure 3

Branch and Bound tree when two sensor nodes and two licensed channels are considered.

In the first branch, we assume that the subproblem with $z_{1,1} = - 4$ is selected to be solved. Then $L = L ∖ {z_{1,1} = - 4} = {z_{1,1} = + 4}$ (it corresponds to lines (4) and (5)). After solving the subproblem with $z_{1,1} = - 4$ by using optimization function like fmincon function of Matlab, we get $z_{2,1} = + 4$ , $z_{1,2} = + 1$ , and $z_{2,2} = - 2$ , and $L B = \min {U} = 0.23$ (line (6)). Since $z_{1,2}$ and $z_{2,2}$ are not $- 4$ or $+ 4$ (line (14)), which means that the solution is not integer solution, we continue fixing two variables, $z_{1,2}$ and $z_{2,2}$ . Now let us choose $z_{2,2}$ to create two new subproblems and add them to L (lines (15), (16), and (17)). Therefore, there are three unsolved subproblems in L such that we get $L = {z_{1,1} = + 4, z_{2,2} = - 4, z_{2,2} = + 4}$ . Since L is not empty, we go to line (3) in Pseudocode 1.

In the second branch, let us choose the subproblem with $z_{2,2} = - 4$ to be solved. Then $L = L ∖ {z_{2,2} = - 4} = {z_{1,1} = + 4, z_{2,2} = + 4}$ . After solving the subproblem, we get $z_{1,1} = - 4$ , $z_{2,1} = + 4$ , $z_{1,2} = + 4$ , and $z_{2,2} = - 4$ , and $L B = \min {U} = 0.18$ . In this case, we get an integer solution (line (11)), and we then update $U B$ with $L B$ (line (12)). Since L is not empty, we go to line (3) in Pseudocode 1.

In the third branch, let us choose the subproblem with $z_{2,2} = + 4$ to be solved. Then $L = L ∖ {z_{2,2} = + 4} = {z_{1,1} = + 4}$ . After solving the subproblem, we get $z_{1,1} = - 4$ , $z_{2,1} = + 4$ , $z_{1,2} = - 4$ , and $z_{2,2} = + 4$ , and $L B = \min {U} = 0.22$ . In this case, we get an integer solution (line (11)). However, we do not update UB with LB, since $L B < U B$ . Since L is not empty, we go to line (3) in Pseudocode 1.

In the fourth branch, let us choose the subproblem with $z_{1,1} = + 4$ to be solved. Then $L = L ∖ {z_{1,1} = + 4} = {Ф}$ . After solving the subproblem, we get $z_{1,1} = + 4$ , $z_{2,1} = - 4$ , $z_{1,2} = + 3$ , and $z_{2,2} = - 1$ , and LB = $\min {U} = 0.21$ . In this case, LB is greater than UB. Therefore, this branch cannot generate a better integer solution and this branch is cut out of the implementation. Now, L is empty. Therefore, we stop running the Branch and Bound algorithm, and we get the best integer solution as ${z_{1,1} = - 4$ , $z_{2,1} = + 4$ , $z_{1,2} = + 4$ , $z_{2,2} = - 4}$ , which means that the sensor 1 is assigned to sense channel 1 and sensor 2 is assigned to sense channel 2. With this channel assignment, we find $x_{1,1}$ and $y_{1,1}$ and further the optimal sensing time (based on (3) and $x_{1,1}$ and $y_{1,1}$ ) of sensor node 1 and sensor node 2 which minimizes U or maximizes throughput.

In the Branch and Bound algorithm, since each variable $z_{m, n}$ has two integer values, we have ${(M * N)}^{2}$ possibilities of matrix $Z_{m \times n}$ . In the worst case, where we get the best integer solution in the last subproblem, the maximum number of subproblems will be ${(M * N)}^{2}$ . Since Branch and Bound algorithm requires high computation complexity, we propose an heuristic algorithm as follows: from the simulation results solved by the Branch and Bound algorithm, it is observed that sensors with a higher sensing SNR usually are assigned to the cluster which senses the licensed channels with higher channel capacity $C_{m}$ . It is mainly due to the fact that more throughput can be obtained on the licensed channel with a higher channel capacity than other licensed channels, and sensors with a higher SNR will be therefore assigned to the licensed channel with a higher channel capacity for a better sensing performance. Based on the observation, we can design heuristic algorithm for an efficient solution of clustering sensors. The pseudocode of the heuristic algorithm is shown in Pseudocode 2. The heuristic algorithm is comprised of two stages: sensor clustering and throughput maximization. First, the sensor clustering is performed as follows: the order (or priority) of clusters in sensor assignment denoted as ClusterOrder is determined based on corresponding channel capacity; that is, the cluster which senses the licensed channel with the highest capacity has the highest priority in choosing a sensor. For that a cluster $m^{*}$ with the highest priority (line (3)) will first select a sensor in a list of available sensors denoted as LoS (line (6)). An unassigned sensor $n^{*}$ with a higher sensing SNR in LoS will be first chosen by the cluster $m^{*}$ (line (7)) which means the sensor node $n^{*}$ is assigned to the cluster $m^{*}$ such that $a_{m^{*}, n^{*}} = 1$ (line (8)). Then, the assigned sensor $n^{*}$ is removed from LoS (line (9)). This process is repeated for clusters with less priority until no sensor is available; that is, LoS is empty. Second, each cluster finds optimal sensing time to maximize throughput on corresponding licensed channel (lines (16), (17), and (18)) by solving subproblem or (12). Main concept of the heuristic algorithm is as follows: for channel assignment, we start with the licensed channel that has the highest channel capacity and assign the sensor node that has highest SNR to the chosen licensed channel. After that, we go to the licensed channel with the second highest channel capacity and assign the sensor node that has the highest SNR to the chosen licensed channel. The process will be continued until all sensor nodes are assigned to clusters. Therefore, the number of sensor nodes per cluster will be equal.

Pseudocode 2: Pseudocode of heuristic algorithm for sensor clustering.

Input: $C_{m}$ , $R_{m}^{req}$ , and $γ_{m, n}$

Output: $A_{m \times n}$ and $τ_{m, n}$

(1) Initiate: a list of available sensors, LoS = $\{1, \dots, n \}$

(2) Determine: cluster priority based on $C_{m}$ , ClusterOrder

(3) OrderIndex← M

(4) $a_{m, n} \leftarrow 0$ for all $m, n$ $\{a l l s e n s o r s a r e n o t a s s i g n e d \}$

(5) while {LoS ≠ empty} do

(6) $m^{*}$ ← find{a cluster ∣ ClusterOrder( $m^{*}$ ) = $O r d e r I n d e x \}$

(7) $n^{*}$ ← find{a sensor ∣ $γ_{m^{*}, n^{*}}$ = max( $γ_{m^{*}, n} | n \in LoS$ )}

(8) $a_{m^{*}, n^{*}} \leftarrow 1$ {assign sensor $n^{*}$ to cluster $m^{*} \}$

(9) LoS ← LoS∖ $\{n^{*} \}$

(10) if $\{O r d e r I n d e x$ = 1} then

(11) $O r d e r I n d e x$ ← M

(12) else

(13) Decrease $O r d e r I n d e x$

(14) end if

(15) end while

(16) for {all clusters}

(17) $τ_{m, n}$ ← max( $R | A_{m \times n}$ ) or $τ_{m, n}$ ← min( $U | Z_{m \times n}$ )

(18) end for

In the heuristic algorithm, we solve subproblem after sensor clustering in order to get $x_{m, n}$ and $y_{m, n}$ further to get optimal sensing time $τ_{m, n}$ (line (17)). Therefore, heuristic algorithm has only one subproblem and can reduce computation complexity significantly compared with Branch and Bound algorithm which requires ${(M * N)}^{2}$ subproblems.

5. Simulation Results

In this section, we present simulation results for the proposed Branch and Bound scheme, the proposed heuristic scheme, and the random scheme.

For a comparison of the proposed schemes with a benchmark method, we consider the random scheme. In the random scheme, sensor nodes are selected randomly and equally assigned to each sensor cluster for sensing a licensed channel. After sensor clustering, sensing time of each sensor node is calculated by (12) for given cluster information ( $z_{m, n}$ ).

The deploying sensor nodes are distributed over licensed network. The SN forms sensor clusters to perform CSS over three licensed channels (M = 3). The SNR $γ_{m, n}$ presented at sensor nodes is different from others and is assumed to follow an exponential distribution with a mean μ (dB). Other parameters are given as follows: the sampling frequency of primary user signal is the same for all sensor nodes with a value of $f_{s} = 200$ kHz. The sensor network must form sensor clusters for CSS to guarantee a detection probability as $Q_{t h}^{d} = 0.9$ in all exploiting channels to protect the primary users. The licensed channels are organized which follows time slot structure with equal durations of $T = 10$ ms. We assume that channel capacity of each licensed channel can be measured by SU, and minimum throughput requirement of each licensed channel is given. In our simulation, three licensed channels are considered, and it is assumed that the channel capacities and the minimum throughput requirements of the three licensed channels are given as $C_{m} = [8; 7; 9]$ Mbps and $R_{m}^{r e q} = [6; 3; 5] M b p s$ , respectively.

In the first experiment, the number of sensor nodes N in the sensor network is uniformly increased as $N = [6, 9, 12, 15, 18]$ to evaluate the achievable throughput, while the mean SNR is given as $μ = - 10$ dB. Figure 4 shows total achievable throughput of CRNs for three schemes when three licensed channels are considered. Generally, the total throughput of CRNs increases as the WSN is equipped with more sensors. At first, the throughput sharply increases with the increasing number of sensors. However, the throughput slowly increases as the WSN deploys a large number of sensors, that is, the cases where $N \geq 15$ ; the increase of throughput is very limited. From Figure 4, it is observed that the proposed heuristic scheme offers good matching results with the proposed Branch and Bound scheme while reducing computation complexity significantly. Therefore, the proposed heuristic scheme can be very useful solution when CRN exploits a large number of licensed channels and sensor nodes. Figure 4 also shows that the random scheme provides less achievable throughput than two proposed schemes even though it has the same computation complexity as that of the proposed heuristic scheme.

Figure 4

Comparison of total achievable throughput of CRNs for the proposed Branch and Bound scheme, the proposed heuristic scheme, and the random scheme.

In the second experiment, the mean SNR μ and number of sensor nodes N were varied while maintaining other parameters. We generated 1000 cases of sensor distribution for each pair of N and μ and examined the average throughput of CRNs only using the heuristic algorithm. The results are illustrated in Figure 5. Generally, for each case of number of sensors, the average throughput of CRNs decreases as mean SNR decreases. However, it can be clearly seen that decrease in throughput becomes severe in the case of few number of sensor nodes and of less SNR.

Figure 5

Average throughput of CRNs when the heuristic algorithm is used.

6. Conclusions

In this paper, we have studied the problem of sensor clustering to maximize achievable throughput of pervasive sensor-aided CRNs which exploits multiple licensed channels. In the considered system, a pervasive sensor network is utilized to provide service of exploring free licensed channels for CRNs based on request-service model. We have formulated the problem of sensor clustering as a mixed-integer nonlinear programming problem. To reduce the computation complexity in the cases of large number of sensor nodes and licensed channels, a heuristic algorithm has been proposed for an efficient solution based on information of primary user SNR at sensor nodes. Finally, simulation results have been provided to demonstrate the performance of the proposed methods. Based on simulation results, the heuristic algorithm is proven to be effective since it provides similar throughput to that of MINLP method with less computation complexity.

Footnotes

Appendix

The first and second derivatives of Q function are given by (A.1)

\begin{matrix} \frac{d Q (x)}{d x} = - \frac{1}{\sqrt{2 π}} \exp (- \frac{x^{2}}{2}) < 0, \\ \frac{d^{2} Q (x)}{d x^{2}} = \frac{x}{\sqrt{2 π}} \exp (- \frac{x^{2}}{2}) . \end{matrix}

From (3), several expressions are derived as follows: (A.2)

\begin{matrix} \frac{\partial τ_{m}}{\partial x_{m, n}} = \frac{2 (x_{m, n} - y_{m, n} ξ_{m, n})}{δ_{m, n}^{2}} > 0, \\ \frac{\partial^{2} τ_{m}}{\partial x_{m, n}^{2}} = \frac{2}{δ_{m, n}^{2}} > 0, \\ \frac{\partial τ_{m}}{\partial y_{m, n}} = \frac{- 2 ξ_{m, n} (x_{m, n} - y_{m, n} ξ_{m, n})}{δ_{m, n}^{2}} = - ξ_{m, n} \frac{\partial τ_{m}}{\partial x_{m, n}} < 0, \\ \frac{\partial^{2} τ_{m}}{\partial y_{m, n}^{2}} = \frac{2 ξ_{m, n}^{2}}{δ_{m, n}^{2}} > 0 . \end{matrix}

The first and second derivatives of $Q_{m}^{F}$ with respect to $x_{m, r}$ are derived as (A.3)

\begin{matrix} \frac{\partial Q_{m}^{F}}{\partial x_{m, r}} = Q (z_{m, r}) \frac{d Q (x_{m, r})}{d x_{m, r}} \prod_{n \neq r} [1 - Q (z_{m, n}) Q (x_{m, n})], \\ \frac{\partial^{2} Q_{m}^{F}}{\partial x_{m, r}^{2}} = Q (z_{m, r}) \frac{d^{2} Q (x_{m, r})}{d x_{m, r}^{2}} \prod_{n \neq r} [1 - Q (z_{m, n}) Q (x_{m, n})] . \end{matrix}

Similarly, $\partial Q_{m}^{D} / \partial y_{m, r}$ and $\partial^{2} Q_{m}^{D} / \partial y_{m, r}^{2}$ can be calculated.

The first and second derivatives of U with respect to $y_{m, n}$ and $x_{m, n}$ are expressed as (A.4)

\begin{matrix} \frac{\partial U}{\partial y_{m, n}} = C_{m} (1 - Q_{m}^{F}) \frac{\partial τ_{m}}{\partial y_{m, n}} > 0, \\ \frac{\partial^{2} U}{\partial y_{m, n}^{2}} = C_{m} (1 - Q_{m}^{F}) \frac{\partial^{2} τ_{m}}{\partial y_{m, n}^{2}} > 0, \\ \forall x_{m, n}, z_{m, n}, \\ \frac{\partial U}{\partial x_{m, n}} = C_{m} \{(T - τ_{m}) \frac{\partial Q_{m}^{F}}{\partial x_{m, n}} + (1 - Q_{m}^{F}) \frac{\partial τ_{m}}{\partial x_{m, n}}\}, \\ \frac{\partial^{2} U}{\partial x_{m, n}^{2}} = C_{m} \{- 2 \frac{\partial τ_{m}}{\partial x_{m, n}} \frac{\partial Q_{m}^{F}}{\partial x_{m, n}} + (T - τ_{m}) \frac{\partial^{2} Q_{m}^{F}}{\partial x_{m, n}^{2}} + (1 - Q_{m}^{F}) \frac{\partial^{2} (τ_{m})}{\partial x_{m, n}^{2}}\} . \end{matrix}

Therefore, U is a decreasing and convex function of $y_{m, n}$ . The second derivative of U with respect to $x_{m, n}$ is always positive if the second derivative of $Q_{m}^{F}$ with respect to $x_{m, n}$ is positive. This is only satisfied if the second derivative of $Q (x_{m, n})$ is positive leading to $x_{m, n} > 0 (P_{m, n}^{f} < 0.5), \forall z_{m, n}, y_{m, n}$ . Therefore, U is a convex function of $x_{m, n} (x_{m, n} > 0)$ .

Conflict of Interests

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

Acknowledgment

This work was supported by the KRF funded by the MEST (NRF-2013R1A2A2A05004535).

References

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

Tishita

T. A.

Akhter

Islam

M. I.

Amin

M. R.

Spectrum sensing and data transmission in a cognitive relay network considering spatial false alarms

Journal of Information Processing Systems 2014 10 3 459 470

10.3745/JIPS.03.0007

2-s2.0-84908208707

Khan

R. T.

Islam

M. I.

Amin

Traffic analysis of a cognitive radio network based on the concept of medium access probability

Journal of Information Processing Systems 2014 10 4 602 617

10.3745/jips.03.0019

Yücek

Arslan

A survey of spectrum sensing algorithms for cognitive radio applications

IEEE Communications Surveys & Tutorials 2009 11 1 116 130

10.1109/surv.2009.090109

2-s2.0-70349185618

Nguyen-Thanh

Koo

An enhanced cooperative spectrum sensing scheme based on evidence theory and reliability source evaluation in cognitive radio context

IEEE Communications Letters 2009 13 7 492 494

10.1109/LCOMM.2009.090043

2-s2.0-68349157383

Hiep

V. V.

Koo

Cooperative spectrum sensing with collaborative users using individual sensing credibility for cognitive radio network

IEEE Transactions on Consumer Electronics 2011 57 2 320 326

10.1109/tce.2011.5955162

2-s2.0-79960902200

Federal Communications Commission

Promoting more efficient use of spectrum through dynamic spectrum use technologies

ET Docket 2010 10-237, FCC 10-198

Yoon

Kim

Y.-K.

Chang

J.-W.

An energy-efficient routing protocol using message success rate in wireless sensor network

Journal of Convergence 2013 4 1 15 22

J. K.-Y.

Ubiquitous healthcare: healthcare systems and applications enabled by mobile and wireless technology

Journal of Convergence 2012 3 2 15 20

10.

Pughat

Sharma

A review on stochastic approach for dynamic power management in wireless sensor networks

Human-Centric Computing and Information Sciences 2015 5, article 4

10.1186/s13673-015-0021-6

2-s2.0-84922570130

11.

Huang

Cheng

R.-H.

Chen

S.-R.

C.-I.

Enhancing network availability by tolerance control in multi-sink wireless sensor network

Journal of Convergence 2010 1 1 15 22

12.

Kusdaryono

Lee

K. O.

A clustering protocol with mode selection for wireless sensor network

Journal of Information Processing Systems 2011 7 1 29 42

10.3745/jips.2011.7.1.029

13.

Singh

Lobiyal

A novel energy-aware cluster head selection based on particle swarm optimization for wireless sensor networks

Human-centric Computing and Information Sciences 2012 2, article 13

10.1186/2192-1962-2-13

14.

Sinha

Lobiyal

D. K.

Performance evaluation of data aggregation for cluster-based wireless sensor network

Human-Centric Computing and Information Sciences 2013 3, article 13

10.1186/2192-1962-3-13

15.

Liang

Y.-C.

Zeng

Peh

E. C. Y.

Hoang

A. T.

Sensing-throughput tradeoff for cognitive radio networks

IEEE Transactions on Wireless Communications 2008 7 4 1326 1337

10.1109/twc.2008.060869

2-s2.0-46149091216

16.

Fan

Jiang

Optimal multi-channel cooperative sensing in cognitive radio networks

IEEE Transactions on Wireless Communications 2010 9 3 1128 1138

10.1109/twc.2010.03.090467

2-s2.0-77949558904

17.

Eryigit

Bayhan

Tugcu

Energy-efficient multichannel cooperative sensing scheduling with heterogeneous channel conditions for cognitive radio networks

IEEE Transactions on Vehicular Technology 2013 62 6 2690 2699

10.1109/TVT.2013.2247070

2-s2.0-84880552107

18.

Borchers

MINLP: branch and bound methods

Encyclopedia of Optimization 2009

New York, NY, USA

Springer

2138 2142

10.1007/978-0-387-74759-0_378