Vol.28 No.3
JOURNAL OF ELECTRONICS (CHINA)
May 2011
COOPERATIVE WIDEBAND SPECTRUM SENSING BASED ON SEQUENTIAL COMPRESSED SENSING1 Gu Bin
Yang Zhen
Hu Haifeng
(Institute of Signal Processing and Transmission, Nanjing University of Posts and Telecommunications, Nanjing 210003, China) (Key Lab of Broadband Wireless Communication and Sensor Network Technology, Ministry of Education, Nanjing University of Posts and Telecommunications, Nanjing 210003, China) Abstract Compressed sensing offers a new wideband spectrum sensing scheme in Cognitive Radio (CR). A major challenge of this scheme is how to determinate the required measurements while the signal sparsity is not known a priori. This paper presents a cooperative sensing scheme based on sequential compressed sensing where sequential measurements are collected from the analogto-information converters. A novel cooperative compressed sensing recovery algorithm named Simultaneous Sparsity Adaptive Matching Pursuit (SSAMP) is utilized for sequential compressed sensing in order to estimate the reconstruction errors and determinate the minimal number of required measurements. Once the fusion center obtains enough measurements, the reconstruction spectrum sparse vectors are then used to make a decision on spectrum occupancy. Simulations corroborate the effectiveness of the estimation and sensing performance of our cooperative scheme. Meanwhile, the performance of SSAMP and Simultaneous Orthogonal Matching Pursuit (SOMP) is evaluated by Mean-Square estimation Errors (MSE) and sensing time. Key words Cognitive Radio (CR); Wideband spectrum sensing; Sequential compressed sensing; Matching pursuit CLC index
TN92
DOI 10.1007/s11767-011-0612-y
I. Introduction Cognitive Radio (CR) provides a revolutionary scheme to improve the frequency usage efficiency by allowing Secondary Users (SUs) dynamically access the spectrum that is temporarily unoccupied by Primary Users (PUs)[1]. It is a prerequisite for the SUs to sense the environments with limited interference to PUs in CR network. Therefore, spectrum sensing is one of the key problems to the scheme. However, spectrum sensing is still a very challenging task in wideband CR network because SUs must achieve the wideband signal above the 1
Manuscript received date: December 7, 2010; revised date: February 24, 2011. Supported by the National High Technology Research and Development Program (No. 2009AA01Z241) and the National Natural Science Foundation (No. 60971129, No. 61071092). Communication author: Gu Bin, born in 1983, male, Ph.D. student. Nanjing University of Posts and Telecommunications, Mailbox 214, Nanjing 210003, China. Email:
[email protected].
Nyquist sampling rate. It is not realistic to implement the high-speed ADC to process massive information with current technologies for the wideband frequency up to a few GHz. In recent years, Compressed Sensing (CS) provides an efficiently way to compress and sense sparse signal[2,3]. According to CS theories, all characteristics of the sparse signal can be achieved by a number of measurements over a random basis. As a result, the original sparse signal also can be reconstructed perfectly with high probability from the small number of measurements by solving an optimization problem. CS can be used as a scheme to sense the wideband spectrum in CR was first introduced in Ref. [4], where the authors utilize the wavelet transform and CS to detect the edge of the sparse wideband spectrum. Nevertheless, the scheme in Ref. [4] still required the high-speed ADC for analog signal sampling. And in Ref. [5], the authors use an Analog-to-Information Converter (AIC) instead of ADC to sample the analog signal. A practical approach to implement an AIC
314
JOURNAL OF ELECTRONICS (CHINA), Vol.28 No.3, May 2011
can be found in Ref. [6]. However, as the sparsity level of the sparse signal is often not known a priori in practical settings, it can be very challenging to determinate the number of the measurements or estimate the reconstruction error. Another challenging work in compressed spectrum sensing is the development of a fast reconstruction algorithm with reliable accuracy and low computational complexity. The Orthogonal Matching Pursuit (OMP)[7] is one of the most popular recovery algorithms as it is faster and easier to implement. Other algorithms based on OMP include Stagewise OMP (StOMP)[8], Regularized OMP (ROMP)[9], Compressive Sampling Matching Pursuit (CoSaMP)[10] and Subspace Pursuit (SP)[11]. Although CoSaMP and SP algorithm offer comparable theoretical reconstruction quality as that of the liner program Linear Programming (LP) methods and low computational complexity, both SP and CoSaMP assume that the sparsity level K is known, whereas K may not be available in many practical applications. More recently, Sparsity Adaptive Matching Pursuit (SAMP)[12] is proposed by introducing the idea of backtracking of SP without prior information of the sparsity level. Meanwhile, distributed compressed sensing is considered in Ref. [13] where a fast iterative algorithm called Simultaneous Orthogonal Matching Pursuit (SOMP) is utilized to recover all of the signals jointly. Obviously, in the cooperative sensing scheme, a new algorithm must be proposed to take the advantage of both SAMP and SOMP. In this paper, we consider a cooperative windband spectrum sensing scheme based on sequential compressed sensing where one is able to get measurements in sequence from AIC. We have a centralized fusion center to collect measurements and each individual SU acquires the same wideband signal. The underlying signal model as such is covered by the joint sparsity model considered in Ref. [13]. With the same model but a novel method, a cooperative CS reconstruction algorithm named Simultaneous Sparsity Adaptive Matching Pursuit (SSAMP) is proposed to perform computations in between measurements to decide whether enough measurements have been obtained when the sparsity level K is unknown. Finally, the reconstruction sparse vectors are used to make a decision on
spectrum occupancy. The remainder of this paper is organized as follows. Section II introduces the CS background and the principle of sequential CS. Section III describes the spectrum sensing scheme based on sequential CS for single analog signals and the cooperative scheme using SSAMP. Simulation results are shown in Section IV and conclusions are made in Section V.
II. Compressed Sensing with Sequential Measurements 1. Compressed sensing background We consider an N × 1 vector of discrete-time signal x that is K -sparse in some N × N basis matrix Ψ with the vectors {ψi } as columns. And then the signal x can be expressed as N
x =∑ vi ψi , or x =Ψ v
(1)
i =1
Here v has only K non-zero elements with K << N . According to CS theories, if we project signal x over an M × N matrix Φ that is incoherent with Ψ where M << N [14], we can reconstruct the signal successfully with high probability from M measurements depended on the reconstruction algorithm. The matrix Φ can be constructed by choosing elements independently from a random Gaussian or Bernoulli matrix[3]. In practical applications, the noise will be lead into the measurement for the no idealities in the hardware system or other factors. Consider the same discretetime signal x, and suppose we collect noisy measurements y y =Φx +w=ΦΨ v +w=Θv +w
(2)
where w is the noise vector and Θ=ΦΨ is a M × N compressed sensing matrix. We suppose w 2 ≤ η, then we can recover the sparse signal v by solving an optimization problem = arg min v v
A1
, s.t. Θv − y
2
≤η
(3)
If we use CoSaMP algorithm to recover the signal, for instance, the reconstruction error of the sparse signal can be calculated by −v v
2
⎧ ≤ C max ⎪ ⎨η, ⎪ ⎪ ⎩
1 v − vK K
A1
⎫ ⎪ ⎬ ⎪ ⎪ ⎭
(4)
GU et al. Cooperative Wideband Spectrum Sensing Based on Sequential Compressed Sensing
where vK is a best K -sparse approximation to v with respect to the A 1 -norm. Obviously, the recovery algorithm of compressed sensing can be robust to noise. 2. Sequential compressed sensing
When the sparsity level K of a signal v is known a priori, the required number of measurements for successful recovery can be calculated from K . For instance, when we use the OMP algorithm, we can recover (with high probability) a N × 1 signal with K non-zero elements with only M = 2K ln N measurements[7]. In many practical applications, however, there are two problems to determine the number of measurements with this method. On one hand, the number of measurements is typically generous upper-bounds for guaranteeing recovery with high probability which often means we will take many unnecessary measurements. On the other hand, in many practical applications, the sparsity level K is unknown, which means we cannot determine the exact number of measurements. Fortunately, sequential compressed sensing[15] develops an approach to estimate the reconstruction error using only a small number of additional measurements, without any a priori knowledge on signal sparsity level. We consider T as the number additional measurements which also named by the sequential step size. We use the additional measurements to determine an affine space. If we compute the distance between the current reconstruction and the affine space, the reconstruction error can be calculated by the distance and an unknown constant CT M x −x
2
M , H M +T ) = CT d (x
(5)
Here H M +T {x | yi = ai x , 1 ≤ i ≤ M + T } is an affine space constructed by M + T measureM , H M +T ) denotes the distance from curments, d (x M to the affine space H M +T , rent reconstruction x and CT is a random variable which has an upper bound on both the mean and the variance as follows
E [CT ] ≤
N −M −2 T −2
(6)
315
N −M −2 N −M − (7) T −2 T Combining the upper bound in Eqs. (6), (7) and the Chebyshev inequality ( a − E [a ] ≥ k σa ) ≤ 1/ k 2 , we can get the following proposition[15]. Proposition 1 In the Gaussian measurement maM ⏐⏐2 ≤ C Tk d (x M , H M +T ) with trix we have: ⏐⏐x − x 2 probability at least 1 − (1/ k ), where C Tk = (L − 2)/(T − 2) + k ((L − 2)/(T − 2)) − L /T , for any K > 0, L = N − M . Now consider the case where one can get measurements in sequence, it’s easy to decide whether enough measurements have been obtained by performing computations in between measurements. As a result, sequential compressed sensing can recover the signal either exactly or to a given tolerance by using smallest possible number of additional measurements. Var [CT ] ≤
III. Cooperative Wideband Spectrum Sensing 1. Compressed spectrum sensing with sequential measurements
Firstly, we describe the wideband spectrum sensing scheme with sequential measurements for a single SU case. The SU uses an AIC to sample the wideband signal f (t ) and then acquire the measurements[6]. The AIC can be considered as a linear system that convert the analog signal to discrete measurements. We consider x as the discrete signal of f (t ) and suppose the wideband CR network with a total of N Hz in the frequency range. There are a total number of P channels can be used for communication and every spectrum channel contains N / P spectrum points. The sparse vector v and the signal vector x are related as follows −1
x =Ψ v= (Γ FW ) v
(8)
in which W denote the a wavelet based smoothing function and F denotes a Fourier transform in Ref. [4]. Γ is a derivative operation given in Ref. [4] and v has only K non-zero elements. Obviously, the signal is sparse because of the number of nonzero elements K << N . The compressed sensing matrix ΘM =ΦM (Γ FW )−1 describes the overall procedure of the sensing scheme on the sparse
316
JOURNAL OF ELECTRONICS (CHINA), Vol.28 No.3, May 2011
vector v by M measurement. Now using Eq. (3), we can reconstruction the space vectors v by solving an A 1 -norm optimization problem as follows M = arg min v v
A1
, s.t.
ΘM v − y M
2
≤η
(9)
The optimization problem above can be solved with SAMP algorithm when the sparsity level K is not known a priori. An M -measurement estimate M = of signal can now be obtained from x −1 M . Then, we can compute the distance (Γ FW ) v between the current reconstruction and the affine space determined by obtaining a small number of additional measurements T with the approach in Eq. (5). We define the pseudo inverse of a tall, fullrank matrix Φ by the formula Φ† = Φ(ΦΦ* )−1 . M to H M +T can be expressed The distance from x as M , H M +T ) = (ΦM +T ) (ΦM +T x M − y M +T ) d (x †
(10)
M , we have Then, for sparse vectors v
M v −v
M − y M +T ) ≤ C Tk (ΘM +T ) (ΘM +T v †
2
(11)
either When we recover the sparse vectors v exactly or to a given tolerance from the additional measurements, an estimate of the wideband spectrum can now be obtained from n
s(n )=∑ v(k ), n =1,2, ", N
(12)
k =1
The decision of the presence of a licensed transmission signal in a certain channel is made by an energy detector using the estimated frequency response over each channel. The test statistic of each channel is Vp =
pQ 1 2 s(q ) , p = 1,2, ", P ∑ Q q =( p−1)Q +1
(13)
where p is the channel index, q is the sub-carrier frequency index in each channel, and Q is the number of spectrum samples of each channel for energy detection. We evaluate the probability of detection Pd based on the test statistic V p . Suppose H 1p and H 0p denote the hypotheses of PU being present and absent respectively in channel P, and λ is the normalized decision threshold. We consider sensing
all P channels successfully in one time. Thus, we define the detection probability Pd as follows Pd =
1 P
P
∑ Pr (V
p
> λ | H 1p )
(14)
p =1
2. Recovery algorithm and cooperative sensing scheme
In practical applications, the common basis sparse among the J SUs enables a fast algorithm to recover all of the sparse signals jointly[13]. This joint sparse structure named distributed compressed sensing can efficiently reduce the require number of measurements. In Refs. [13] and [5], the SOMP algorithm is utilized for joint reconstruction. However, it has been observed that SOMP based on OMP lacks provable reconstruction quality. A practical algorithm must be adaptive to sparsity level and robust to noisy measurements so as to sense wideband spectrum at low SNR. In this paper, we proposed one such algorithm called SSAMP. We define ΘT as the column sub matrix of Θ whose columns are listed in the set T and suppose that all the J SUs obtain M measurements. The procedure of SSAMP algorithm is described as follows: Algorithm 1 Simultaneous sparsity adaptive matching pursuit (SSAMP) Input Sampling matrixes Θ = [Θ1 Θ2 " ΘJ ]; Measurement vectors Y =[y1 y2 " yJ ]; Step Size S F ; Target error tolerance ζ . =[v 1 v 2 " v J ]. Output Reconstruction vectors v Initialization: A = 1 {Iteration counter} i = 1 {Stage index} ξ = S F {Size of the finalist in the first stage} rj0 = y j {Current residual of each SU} T0 =/0 {Empty finalist} Repeat: A = A +1 S A = Max(∑ Jj=1 Θj rj( A−1) , ξ ) {Preliminary Test} C A = TA−1 ∪ S A {Make Candidate} T = Max(∑Jj=1 ΘC† A , j y j , ξ ) {Final Test} rj = y j − ΘT , j ΘT† , j y j {Compute Residue} if ⏐⏐rj ⏐⏐2 ≤ ζ for any j then Quit the iteration; else if ⏐⏐rj ⏐⏐2 ≥⏐⏐rj( A−1)⏐⏐2 for any j then {Stage switching} i =i + 1 {Update the stage index}
GU et al. Cooperative Wideband Spectrum Sensing Based on Sequential Compressed Sensing
ξ =i × S F {Update the size of finalist}
else TA =T {Update the finalist} rjA =rj {Update the residual} end if until halting condition true j = ΘT† ,j y j {Prediction of non-zero coefOutput: v ficients} In general, SSAMP algorithm takes the advantage of both SOMP and SAMP algorithm, the most innovative feature of SSAMP is its capability of signal reconstruction without prior information of the sparsity. In the extreme case, SSAMP can be regarded as the SAMP algorithm when J = 1. When step size S F = 1, SSAMP becomes the generalized SOMP and it would require at least K iterations. Because SSAMP introduced the idea of the two tests of SP, it has better reconstruction performance and stability guarantee than SOMP. When we increase step size S F , SSAMP takes fewer iterations but its performance is gradually degraded. This is a trade-off between computational complexity and reconstruction performance. When S F = K and J =1, the SSAMP offers comparable theoretical reconstruction as that of the SP. Let f j (t ) be the wideband analog signal received at the j -th SU. Each SU processes the received signal using the acquisition scheme to obtain a vector of the measurements, as in the CS acquisition step described in Section II. For the j -th SU, denote the corresponding sequential measurements +nT , n = 0, 1, 2 "; the minimum number M yM j measurements are sent to the fusion center for a start. The fusion center applies a SSAMP algorithm to jointly reconstruct the J received sparse Mj of the spectrum. When we recover v j vectors v either exactly or to a given tolerance, the reconstruction sparse vectors are then used for wideband spectrum sensing. The structure of cooperative spectrum sensing based on CS is shown in Fig. 1.
Fig. 1 Structure of cooperative spectrum sensing based on SSAMP
317
IV. Performance Analysis and Simulation Results In the simulations, we consider a spectrum bandwidth from 16 to 32 MHz. There are a total number of P = 16 channels and each channel has an equal bandwidth of 1 MHz. At each sensing period, there are not more than 10 channels are occupied by PUs and the remaining channels can be used by SUs. The occupied channels are choosed uniformly random. We use N = 256 denote the Nyquist rate and set the compression rate M / N to vary from 0.05 to 0.4. The received SNR at each SU is varying from 8 dB to 10 dB randomly. We choose Q = 10 and run 1000 independent trials for each experiment. The error tolerance of SSAMP algorithm is ζ = 10−2. Fig. 2 depicts the estimation performance of cooperative sequential compressed sensing scheme with the Mean-Square estimation Errors (MSE) of the sparse vectors respect to the compression ratio M / N . We perform 1000 experiments with J = 1; 2; 5 and T = 10. We use SSAMP to recover the sparse vectors as we obtain progressively more measurements, and define the estimated errors by an upper bound as follows (via Chebyshev inequality). 2
MSE es =
† 1 J +T Mj − y M C Tk (ΘjM +T ) (ΘjM +T v ) (15) ∑ j J j =1
We compare the estimated errors to the actual j − v j ⏐⏐22 } and see that the errors (1/ J )∑Jj =1 E {⏐⏐v actual reconstruction errors are reliably indicated by estimated errors with a small number of additional measurements. Meanwhile, as the compression rate M / N or the number of SUs J increases, the reconstruction quality of SSAMP algorithm improves. In Fig. 3, we plot the detection probability of cooperative sequential compressed sensing scheme versus compression rate. Note that when the PU is absent, the statistic V p in Eq. (13) is centralized Chi-square distributed. The threshold λ for each SU is found by fixing false alarm probability to 0.05. It can be seen that as the number of SU increases, the sensing performance by cooperative spectrum sensing has been improved. On the other hand, given the same sensing performance, more SUs
318
JOURNAL OF ELECTRONICS (CHINA), Vol.28 No.3, May 2011
mean smaller compression rate.
Fig. 4 Mean-square estimation errors of SOMP and SSAMP versus compression rate (1000 complete trials) Fig. 2 Actual errors and estimated errors with sequential compressed sensing versus compression rate (1000 complete trials)
Fig. 5 Average sensing time of SOMP and SSAMP versus compression rate (1000 complete trials) Fig. 3 Detection probability versus compression rate (1000 complete trials)
V.
We compare the SOMP and SSAMP algorithm in Fig. 4 with MSE and Fig. 5 with sensing time respectively. We can see that the signal spectrum recovery quality of our SSAMP algorithm improves faster than SOMP algorithm as the compression rate M / N increases, which means that SSAMP has better anti-noise performance, especially when M / N is smaller than 0.25. Note that when S F = 1, SSAMP can be roughly regarded as the (generalized) SOMP although it may require two tests to achieve more accuracy[12]. The running time of SSAMP is a little more than SOMP when M / N is more than 0.25. When S F > 1, each stage in the SSAMP still uses a similar principle of the SP (e.g. K = S F ). The running time of SSAMP is Ο(KMN / S F ) while SOMP is Ο(KMN ) [10]. As a result, the novel algorithm SSAMP can also reduce the sensing time comparing to the SOMP.
In this paper, we presented a cooperative compressive wideband spectrum sensing scheme based on sequential compressed sensing where one is able to get measurements in sequence from AIC. A novel algorithm named SSAMP is utilized to reconstruct the sparse vectors and determinate whether enough measurements have been obtained without any a priori assumption on signal sparsity level. When we recover the signal either exactly or to a given tolerance from the smallest possible number of random measurements, the reconstruction spectrum sparse vectors are then used to make a decision on spectrum occupancy. The simulation results show that the estimated errors reliably indicate the actual reconstruction error after a small number of additional measurements. The sensing performance of our cooperative sensing scheme is much better than a single spectrum sensing scheme. Performance evaluation using MSE and sensing time is showed that the SSAMP algo-
Conclusions
GU et al. Cooperative Wideband Spectrum Sensing Based on Sequential Compressed Sensing
rithm has better anti-noise characteristics and shorter sensing time compared to SOMP algorithm.
[8]
References [1]
[2]
[3] [4]
[5]
[6]
[7]
S. Haykin. Cognitive radio: brain-empowered wireless communications. IEEE Journal on Selected Areas in Communications, 23(2005)2, 201–220. E. Candes, J. Romberg and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2006)2, 489– 509. D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(2006)4, 1289–1306. Z. Tian and G. B. Giannakis. Compressed sensing for wideband cognitive radios. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Honolulu, HI, USA, Apr. 15–20 2007, 1357–1360. Y. L. Polo, Y. Wang, A. Pandharipande, et al.. Compressive wideband spectrum sensing. International Conference on Acoustics, Speech, and Signal Processing, San Diego, CA, USA. Feb. 8–13, 2009, 178–183. J. Laska, S. Kirolos, Y. Massoud Y, et al.. Random sampling for analog-to-information conversion of wideband signals. IEEE Dallas Circuits and Systems Workshop, Richardson, TX, USA, Oct. 29–30, 2006, 119–122. J. A. Tropp and A. C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53 (2007)12, 4655–4666.
[9]
[10]
[11]
[12]
[13]
[14]
[15]
319
D. L. Donoho, Y. Tsaig, and J. Starck. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, http://www-stat. stanford.edu/~donoho/Reports/2006/, 2006. D. Needell and R. Vershynin. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE Journal of Selected Topics in Signal Processing, 4(2010)2, 310– 316. D. Needell and J. A. Tropp. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(2009)3, 301–321. W. Dai and O. Milenkovic. Subspace pursuit for compressive sensing signal reconstruction. IEEE Transactions on Information Theory, 55(2009)5, 2230– 2249. T. T. Do, L. Gan, N. Nguyen, et al.. Sparsity adaptive matching pursuit algorithm for practical compressed sensing. 42nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, Oct. 26–29, 2008, 581–587. M. F. Duarte, S. Sarvotham, D. Baron, et al.. Distributed compressed sensing of jointly sparse signals. Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, Oct. 28–Nov. 1, 2005, 1537–1541. E. Candes and J. Romberg. Sparsity and incoherence in compressive sampling. Inverse Problems, 23(2007)3, 969–985. D. M. Malioutov, S. R. Sanghavi, and A. S. Willsky. Sequential compressed sensing. IEEE Journal of Selected Topics in Signal Processing, 4(2010)2, 435–444.