A novel reduced power compressive sensing technique for wideband cognitive radio

Wideband spectrum sensing for cognitive radio requires high rate analog to digital (A/D) converters whose power consumption is proportional to the sampling rate. In this article, we propose to use sub-Nyquist non-uniform sampling for spectrum sensing to reduce the power consumption. Since the received signal samples are correlated in the time domain, we estimate the missing samples by using the expectation-maximization (EM) algorithm. It is shown that the combined sub-Nyquist non-uniform sampling and EM algorithm consume much less power than A/D converter at the Nyquist rate making the proposed algorithm a viable low-power solution for spectrum sensing. Moreover, it is shown by simulations that the proposed sub-Nyquist rate non-uniform sampler is accurate enough to detect the edges of the estimated power spectral density.


Introduction
A cognitive radio (CR) system [1,2] improves the spectrum utilization by allowing secondary users (SU) to access unused licensed spectrum. Moreover, it assesses its environment and adapts its parameters (e.g. the frequency and power of transmission) to reduce power consumption while having a reliable communication. One reason for increased power consumption is due to electromagnetic pollution. As more wideband access systems are designed, the underlying electromagnetic noise floor increases which in turn requires licensed users to increase their transmit power to maintain required signal to noise ratios (SNRs). CR adds little if any to the noise floor by allowing SU access to the unused bands. Furthermore, by reducing the power consumption of the SU themselves, we can significantly increase transmitted data volumes without a large increase in power consumption or CO 2 emissions. Along with reducing people's exposure to electromagnetic waves, this makes it an excellent candidate for green technology [3]. One important way to reduce power consumption is through developing new signal processing algorithms with lower power consumption. The vacant subbands used by SU are found using spectrum sensing. The first step in spectrum sensing is power spectral density (PSD) estimation. In non-parametric PSD estimation techniques, the PSD is obtained by observing the finite samples of the signal itself. Discrete Fourier transform (DFT)-based PSD estimation methods are the most widely used one [4]. Welch's method [5,6] is an example of DFT-based PSD estimation that was used for spectrum sensing for CR [7]. Simplified DFT (SDFT) is also proposed for PSD estimation in CR [8]. These methods are the simplest methods of PSD estimation, and thus are proposed for PSD estimation in CR [7].
In parametric PSD estimation methods, the received signal samples are modeled as the output of a linear filter to white noise. The PSD is then obtained by estimating the coefficients of that filter. The most important examples are the Yule-Walker auto-regressive (AR) [9] method and the Burg method [9]. These methods are more complex than the previously mentioned non-parametric methods, and thus have not yet been suggested for CR applications.
In subspace methods, the PSD is estimated based on eigenvalue analysis of the correlation matrix. The most important ones are the MUltiple SIgnal Classification (MUSIC) method [9] and the Eigenvector (EV) method [9]. In these methods, first the autocorrelation matrix of http://jwcn.eurasipjournals.com/content/2012/1/281 the received signal is calculated. Then, the EVs of the autocorrelation matrix are computed. The largest eigenvalues correspond to the signal subspace and are used to estimate the signal spectrum. These methods are even more complex than parametric methods.
The second step in spectrum sensing is to detect the PSD edges [10]. PSD edges are the locations of abrupt transitions between occupied and unoccupied subbands. It is shown in [11] that the edges can be detected by detecting the local extrema of the first derivative of the continuous wavelet transform (CWT) of the PSD with respect to frequency. Alternatively, the edges can be detected by differentiating the PSD with respect to frequency. Since the abrupt change in the PSD happens in the edge locations, the first derivative of the PSD exhibits local extremum at the edge locations. Different methods of edge detection for spectrum sensing have been introduced in [10]. In this article, to simplify the analysis as is done in [11], we initially assume that the received signal PSD in CR has a piecewise rectangular-like shape shown in Figure 1. Later, we use a more realistic shape of Sinc square for PSD.
Irrespective of the above steps, wideband spectrum sensing requires high rate analog to digital (A/D) converters with the associated high power consumption. Compressive sensing is a candidate for reduced power consumption in CR [12].
Compressive sensing uses a sub-Nyquist rate sampler to sense the received signal [13]. It was shown in [14] that despite the sub-Nyquist sampling rate, compressive sensing can recover the signals that are sparse or nearly sparse in one domain with some limits introduced in [15]. In [16], a simple least square reconstruction technique was used to recover the samples. Since the frequency edge vector of the received signal in CR has a nearly sparse nature, compressive sensing can be used to recover the edge locations of the PSD in CR [17]. The recovery algorithm of compressive sensing (l 1 minimization algorithm) is computationally complex, and thus time and energy consuming and cannot be easily implemented for real-time applications such as in CR.
In this article, we propose a new algorithm for compressive sensing to be used in spectrum sensing in CR. We show by simulations and analysis that the proposed sub-Nyquist rate non-uniform sampler allows for accurate detection of the edges of PSD and consumes much less power than the conventional sensing method. The proposed sampler samples only some portions of the received signal and switches off the A/D converter based on a predefined pattern to reduce power consumption. Since the received signal samples are correlated, the missing samples can be estimated. We propose to use expectationmaximization (EM) technique [18,19] to estimate these samples. It is shown that the combined sub-Nyquist sampler and EM algorithm consume much less power than Nyquist rate A/D converter making the proposed algorithm a viable low-power solution for spectrum sensing and thus extending the battery life of the CR.

System model
The compressed sampling procedure can be expressed in matrix format as where x c is the compressed sampling received signal vector of size P × 1, x is the Nyquist rate sampled received signal vector of size N × 1 (P N), and β is the compressive sampling matrix of size P × N. When β = I N (I N is the identity matrix of size N), the Nyquist sampling rate is achieved. If β = D N (D N is the DFT matrix of size N), the frequency domain sampling is obtained. For compressive sensing purposes, we can simply eliminate some rows of the identity matrix to achieve the matrix β of the compressed dimension. This elimination may be done on a random basis as is done in [17]. For example, for a 4 × 4 identity matrix with compression ratio of 0.75, we have in which the third row of identity matrix is deleted.

Spectrum sensing
In Welch's method, the received signal samples are segmented into M segments of length N. The estimated PSD (S) is achieved by linearly averaging the periodograms of all segments as where S m is the mth segment's periodogram. The periodogram of each segment is given by where X m is the DFT sequence of the mth segment defined as and we have The estimation error variance of Welch's method is inversely proportional to the number of segments (M) involved in the averaging process. We have [6] in which σ 2 S represents the estimation variance of Welch's method and σ 2 S m is the one for the mth segment's periodogram.
After PSD estimation, the edges are detected. Different methods of edge detection for wideband spectrum sensing are developed in [10]. A modified version of windowaveraging based edge detection technique proposed in [10] has been applied in this article. The proposed algorithm can be summarized as follows (1) The estimated PSD (in dB scale) is averaged over consecutive non-overlapping windows.
(2) The integer part of the window-averaged PSD is calculated. (3) Based on the low spectrum occupancy assumption in CR, the most frequent integer of windowaveraged PSD (the mode) is assumed to be the most probable noise level. The edges are located in the cross section of the noise level and the PSD curve. (4) The area under the PSD curve (the integral of the PSD) between two consecutive edges (detected in the previous step) gives the energy level of that subband. (5) A subband with energy level above the noise level determined in the previous step is assumed to be an occupied subband. Therefore their edges are rough estimates of the edges of the PSD. (6) The exact edge location can be detected by locating the extremum of the first derivative of the PSD within that specified window.
Steps 4 and 5 in the above algorithm are modifications to the window-averaging based edge detection algorithm presented in [10].

EM algorithm
The EM algorithm is an algorithm implementing maximum likelihood estimation. It can be applied to a set of data when their stochastic model is known, although the parameters of the model might be unknown [19]. The EM is an iterative algorithm which works as follows [19]: (1) Calculate the expected value of the log-likelihood function of the conditional probability distribution of the missing variables given the observed ones. This expected value is considered to be the current estimate of the missing points. (2) Maximize the above-mentioned distribution with respect to the parameters of the estimation such as mean, variance and covariance of the log-likelihood function. The parameters maximizing the distribution are used for the next expectation step. (3) Iterate the above-mentioned steps until convergence. (4) The maximum likelihood estimation of the missing variables is obtained after convergence.

Estimation of missing samples in compressive sensing for CR
In this article, we propose to estimate the missing points of the sub-Nyquist sampled received signal in the time domain by applying the EM algorithm. A non-uniform sub-Nyquist rate sampler is applied to the received signal of M × N matrix (recall that M is the number of segments and N is the number of points in each segment.). http://jwcn.eurasipjournals.com/content/2012/1/281 As is shown in Figure 2, the non-uniform sampler works as follows: (1) The sampler provides all samples in the first segment of a set of M 1 segments. (2) For the next (M 1 − 1) segments, the sampler samples only the first N 1 points of each segment and is turned off for the rest of this segment. (3) For the (M 1 + 1) th segment, we restart the process by repeating steps 1 and 2.
The fully sampled first segment and the N 1 points in each subsequent segment are used along with the EM algorithm to estimate the missing samples.
Equivalently, for the (m, n) th element of the received signal matrix, the A/D converter is switched on when either takes the remainder of a division and Fix (.) gives the quotient of a division.
Since the received signal samples are mixed with a Gaussian noise, it is assumed that each segment has a Gaussian distribution. Since the received signal samples are correlated, it is assumed that all segments construct a bi-variate Gaussian distribution with the adjacent segments.

EM algorithm for bi-variate Gaussian distribution
Let x 1 be the first segment (the known segment) and x m be the mth segment of the received signal samples. The first parts of each segment are known and the other parts are unknown and to be estimated by EM algorithm. The estimated missing points converge to their actual value after some iterations in EM algorithm [19].
Since, the received signal samples over consecutive windows are assumed to construct a bi-variate Gaussian distribution, the conditional distribution of missing variables given the observed ones has normal distribution with mean [19] (representing the expected value of missing points of x m+1 in expectation step of EM) given by: where μ m is the mean of the mth segment at each iteration given by σ 2 m,(m+1) is the covariance of the mth segment and its consecutive segment given by The variance of the conditional distribution of missing variables in the mth segment given the observed ones in the (m − 1) th segment (σ 2 m,m.m−1 ) is given by [19] in which σ 2 m,m is given by The above-mentioned procedure to estimate the means, variances and covariances of different segments is the maximization step of EM algorithm.
After a few iterations, the unknown elements of each segment are estimated. Each segment is built based on its preceding segment. The preceding segment is either fully known or partially estimated by the EM algorithm. Therefore, it is not required to wait for all segments to be received. This makes the proposed algorithm suitable for real time applications as it does not require a large buffer or long processing time. The required processing time depends on the processor speed.
After estimating the missing samples, Welch's method is applied to estimate the PSD and the edges.

Analysis of applying EM to spectrum sensing
The frequency bin values of each segment using DFT transformation are given by From Equations (13) and (8), we have (∀k) Since N−1 n=0 e −2πjkn/N = 0 and by applying Equation (13) into (14), Equation (14) can be re-written as In the EM algorithm, the expected value of the variable is chosen as its final value (E (X m+1 (k)) = X m+1 (k)). Thus we have Based on Welch's method, the PSD is obtained by The estimation variance of the EM algorithm-based Welch's method equals that of Welch's method [6]. We have in which σ 2 S represents the estimation variance of Welch's method and σ 2 S m is the one for the mth segment's periodogram.
By substituting Equation (16) into (17), we have (∀k) The term |X 1 (k)| 2 is equivalent to its expected value E |X 1 (k)| 2 in the EM algorithm. Thus Equation (19) can be re-written as (∀k) It can be seen from Equation (20) that the PSD obtained by EM algorithm has a scaling factor (shown in brackets) that is frequency-independent and therefore the PSD shape obtained after the application of the EM algorithm is not distorted compared to the one obtained by sampling above the Nyquist rate.

Power consumption comparison
The idea behind intermittently switching off the A/D converter is to reduce the power consumption and increase the battery life. To compare the power consumption of compressive and non-compressive methods, we calculate the power consumption of the EM algorithm that is additional to reduced power of the compressive sensing algorithm.
The A/D power consumption is linearly proportional to the sampling rate and thus to the number of received samples in each time frame [20]. Moreover for zero-crossing based ADC, the static power consumption is zero [21]. We have, where P c , P nc and P EM are the power consumption of compressive sensing method, non-compressive sensing method and EM algorithm, respectively. C r is the compression ratio and is given by From Equations (8)- (11), the whole procedure to update the missing points based on the EM algorithm requires approximately of 6N × M additions and 4N × M multiplications, a total of 10N × M operations (either http://jwcn.eurasipjournals.com/content/2012/1/281 addition or multiplications) for each iteration. Therefore, power consumption of EM algorithm is given by where P i is the power consumption per instruction, O is the number of operations, and I is the number of iterations. The power efficiency (η) of the system is defined by The system is efficient when η > 1.

Reduced power A/D converter system design example
Power consumption of two cases of compressive and noncompressive sensing is subject to proper design of the system, especially proper selection of ADC and processor.
The proposed system is efficient only if P c is much lower than P nc (η > 1) with the proper design of the system. An example is given in this subsection that is one possible design of the system.
For a system with a compression ratio of C r = 0.1 and power efficiency of (η > 1), we have: Equivalently, we have This will give us the boundary limit on the combination of ADC and processor that a designer can choose.
For example, if we select a 1.2 V 250 mW 14 b 100 MS/s digitally calibrated pipeline ADC in 90 nm CMOS which consumes P nc = 250mW [22], then from (27), we require Table 1 Complexity comparison table of non-compressive  and em-based compressive sensing methods   Method Complexity order For the given example a processor with an efficiency of x = 0.4GOPS/mW in order to achieve a power savings of a factor of 4 (η = 4). From [23], it is shown that processors can have efficiencies up to 17.3 GOPS/mW, therefore the above power savings is achievable with readily available processors.
To verify the applicability of the proposed method, simulation results for the above-mentioned case are presented in the upcoming section.

Complexity comparison of compressive and non-compressive sensing methods
Complexity of non-compressive and EM-based compressive sensing methods are compared in Table 1. The complexity order of Welch's method is given by O(N 3 ) [6] and complexity order of EM algorithm is given by 10INM in which I is the number of iterations. M is the number of received signal segments and N is the number of samples in each segment. For the given example, it can be seen that the complexity of EM-based compressive sensing is of the same order as of the non-compressive sensing technique.

Simulation results
For a wideband signal with 29% of spectrum occupancy, the simulation results of obtaining the PSD using both compressive and non-compressive sensing methods are shown in Figure 3 where the actual frequency shaper filter is shown at the top subplot, the PSD obtained by both compressive and non-compressive sensing methods are shown at the bottom subplot. The SNR of the strongest subbands in these simulations is SNR = 2 dB and the other subband is 3 dB weaker. SNR is calculated individually over various subbands and is defined as the ratio of the signal power in each subband to the noise power in that subband. The simulation results are derived from 100 non-overlapping frames of 1024 samples each using Welch's method. For the compressive sensing method, the whole first segment along with the first 128 points of the other segments are sampled. For M 1 = M = 100 segments and N 1 = 128, the compression ratio is 13%. The remaining unknown data are estimated using the EM algorithm for 15 iterations. It can be seen from Figure 3 that although the PSD for the compressed data has lower values than the non-compressive sensing one, the edges of the PSD are maintained. The power consumption calculations for this case are given in the previous section.  For the signal whose PSD is shown in Figure 3, the simulation results of the root mean square error (RMSE) of the edge frequency bins versus the number of iterations of the EM algorithm (used in the new compressive sensing method) is shown in Figure 4. Based on Figure 4, we use 15 iterations as a reasonable number after which the EM algorithm can be considered to have converged.
For the case considered in Figure 3, the edge detection rate versus SNR curves of both compressive and non-compressive sensing techniques along with the periodogram-based PSD estimation technique, are shown in Figure 5. In periodogram-based PSD estimation technique (whose detection rate is shown in the bottom curve of Figure 5), only the first segment is involved in the PSD estimation (one known segment). It can be seen that the detection rate of the compressive sensing method with 13% of compression ratio, is comparable to that of the non-compressive method and it is much better than the periodogram-based spectrum sensing method making it a viable alternative.
We now consider a more realistic PSD shaper filter as shown in Figure 6. The edge detection rate versus SNR curves of both compressive and non-compressive sensing techniques along with the periodogram-based PSD estimation technique are shown in Figure 7. The SNR of the strongest subbands in these simulations is  The remaining unknown data is estimated using the EM algorithm for 15 iterations. Again, it can be seen that the detection rate of the compressive sensing method is comparable to that of the non-compressive method and it is much better than the periodogrambased spectrum sensing method making it a viable alternative.
In order to examine the effects of roll-off factor of the PSD shaper filter on the detection probability, raised- cosine filter is used as the PSD shaper filter. For a low-pass raised-cosine filter given by in which k represents frequency bin, k 0 represents the cutoff frequency bin of the filter, and β is the roll-off factor (0 ≤ β ≤ 1). The edge happens at frequency bin (1 + β)k 0 . For β = 0, the filter has rectangular-like shape and for β = 1, it has a cosine function shape. For a low-pass raised cosine shaper filter with cut-off frequency bin k 0 = 100, the edge detection rate versus PSD shaper filter roll-off factor curves of both compressive and non-compressive sensing techniques are shown in Figures 8 and 9 for SNR = 0 and SNR = 5 dB, respectively. The simulation results are derived from 100 nonoverlapping frames of 1,024 samples each using Welch's method. For the compressive sensing method, the whole first segment along with the first 128 points of the other segments are available. The compression ratio is 13% for M 1 = M = 100 segments and N 1 = 128. The remaining unknown data is estimated using the EM algorithm for 15 iterations. Again, it can be seen that the detection rate of the compressive sensing method is comparable to that of the non-compressive method. The detection rate decreases by an increase in the roll-off factor of the PSD shaper filter. To understand the effects of different structures on the performance, the detection rate of the following scenarios are compared.
(1) Case 1: M 1 = 100 and N 1 = 128; i.e., starting from the first segment, one segment is known in each set of M 1 = 100 segments and the first N 1 = 128 points of the other segments are known. Its detection is shown in Figure 5. C r = 13%. The signal whose frequency shaper filter is shown at the top subplot of Figure 3 is used for the simulations. The simulation results are derived from 100 non-overlapping frames of 1,024 samples each using Welch's method. The edge detection rate versus SNR curves of the proposed compressive sensing algorithm for all compressive sensing cases and the one for non-compressive sensing are shown in Figure 10.
For above-mentioned cases, it can be seen in Figure 10 that the detection rate increases by both increasing the number of known segments M 1 (case 2) and the number of first known points in each segment N 1 (case 3). However, increasing N 1 results in higher detection rate compared to increasing M 1 under the conditions of the above-mentioned cases because a larger N 1 results in more accurate estimation of the covariance of the consecutive segments and thus results in a more accurate estimation of the missing points.

Conclusion
In this article, we apply a sub-Nyquist non-uniform sampler for spectrum sensing for use in CR. It is shown by simulations and analysis that the proposed sub-Nyquist rate non-uniform sampler is accurate enough to detect the edges of PSD and consumes much less power than the non-compressive sensing method. The proposed sampler samples only some portions of the received signal and switches off the A/D converter based on a predetermined pattern to reduce power consumption. Since the received signal samples in time domain are correlated, we estimate the missing samples using the EM technique. The analysis of applying EM technique to spectrum sensing shows that the locations of PSD edges are maintained after estimating the missing points of the received signal using EM algorithm. In a design example, it is shown that the combined sub-Nyquist sampling/ EM algorithm consumes much less power than Nyquist-based A/D converter thus making the proposed algorithm a viable low-power solution for spectrum sensing. It is shown that although the estimated PSD using the proposed compressive sensing method results in lower values than the non-compressive sensing one, the edges of the PSD are maintained. Since in CR, it is the location of the PSD edges that is important rather than the exact shape of PSD, the proposed compressive sensing method can be used as a low-power solution for A/D conversion in wideband CR.

Methods
Simulations were run in MATLAB. To generate the received data with a specified spectrum, a white Gaussian noise process is passed through spectrum shaping filter. This constructs the frequency domain samples of the cognitive radio received signal with a specified spectrum shaping filter. The time domain samples can be obtained by getting the inverse DFT of the frequency domain samples. Then noise is added to the constructed signal to introduce a specific signal to noise ratio. The PSD can be estimated using Welch's method for both DFT and SDFT techniques. The edges can be obtained based on the proposed edge detection technique. The detection rate of the proposed techniques can be obtained by comparing the estimated edge locations to the actual ones. The simulations were run several times to get an accurate detection rate using Monte-Carlo simulation technique.

Competing interests
The authors declare that they have no competing interests.