Efficient limited data multi-antenna compressed spectrum sensing exploiting angular sparsity

Efficient Limited Data Multi-Antenna Compressed Spectrum Sensing Exploiting Angular Sparsity Ines Elleuch∗, Fatma Abdelkefi∗, Amor Nafkha† and Mohamed Siala∗ ∗ SUP’COM,

University of Carthage, Tunisia Email: {ines.elleuch, fatma.abdelkefi, mohamed.siala}@supcom.rnu.tn † SUPELEC/IETR, Campus de Rennes, France Email: [email protected]

Abstract—In this paper, we propose a novel approach for multiple antenna spectrum sensing based on compressed sensing. Our focus is on the angular sparsity of the received signal given an unknown number of primary user source signals impinging upon the antenna array from different Directions Of Arrival (DOA). Given multiple snapshots over a small time period, multiple measurement vectors are available and a joint sparse recovery is performed to estimate the common sparsity profile over the angular domain. In this estimation process, we employ the regularized M-FOCUSS algorithm [1], which is the noisy multiple snapshot extension of the iterative weighted minimumnorm algorithm, called FOCUSS. The contribution of this paper is to take advantage of the sparse primary user DOA estimation within the detection framework of multiple antenna spectrum sensing. In this scope, an accurate sparse reconstruction is not required and a coarse estimation using a reduced number of snapshots is sufficient to decide about the number of present primary users reflected by the angular sparsity order of the received signal. A simulation study shows significant constant false alarm rate performance gain of the proposed approach compared to the conventional maximum to minimum eigenvalue detector especially when the number of PUs increases. Index Terms—Cognitive Radio, Multiple Antenna Spectrum Sensing, Compressed Sensing, Multiple Measurement Vectors, Joint Sparse Recovery, Sparsity Order, Direction-of-Arrival Estimation.

I. I NTRODUCTION

AND

R ELATED W ORKS

In Cognitive Radio, the development of blind, fast and reliable Spectrum Sensing algorithms is a critical issue. Indeed, these requirements are hard to achieve given the tradeoff between the sensing duration on the one hand and the miss detection and false alarm probabilities (Pmd and Pf a respectively) on the other hand. Cooperative sensing as well as multiple antenna architectures for the secondary users (SU) are two approaches that have been proposed in the literature to alleviate this problem by exploiting spatial diversity [2], [3]. More recently, Compressed Sensing (CS) [4], [5] has been considered as a promising technique to improve spectrum sensing performance by exploiting some inherent sparsity feature of the received signal. Most of the literature on Compressed Spectrum Sensing (CSS) deals with sparsity in the frequency domain to perform wideband spectrum sensing [6]. In this scope, the This work was supported by a National Priorities Research Program grant from the Qatar National Research Fund under reference (NPRP08-577-2-241).

CS potential is put forward during 1) the data acquisition stage to alleviate the sampling bottleneck of the wideband analog signal by capturing it at a sub-Nyquist data rate and 2) the data processing stage to simultaneously detect vacant frequency bands from limited number of samples using sparse reconstruction algorithms. Eventhough cooperation has been considered within CSS, in most of the works the sparse recovery stage is decoupled from the cooperation scheme. In [7], [8] different distributed cooperation schemes have been proposed, where a consensus is forced among the LASSObased sparse power estimates of neighboring nodes. Many different centralized schemes have also been proposed. In [9], [10], multiple measurement vectors from different local/head nodes are stacked or separately processed at the fusion center then a soft or hard decision fusion was applied. On the contrary, in [11], [12], the joint frequency sparsity profile of the local compressed measurements has been explicitly handled within the recovery process at the fusion center using a joint sparse support recovery scheme. Furthermore, combining CSS with a multiple antenna architecture has attracted very little attention until quite recently in [13], where wideband sensing has been considered. In this paper, we investigate the potential of CSS when the SU is equipped with multiple antenna. While most of the literature on CSS originated in the single antenna scenario where a Single Measurement Vector (SMV) is involved in the sparse recovery process, we address the CSS in the Multiple Measurements Vector (MMV) framework suggested by the array architecture. Unlike [13], we consider the sparsity at the angular domain. Motivated by early works on sparse recovery of Direction Of Arrival (DOA) [14], [1], we focus on primary user (PU) detection through the estimation of the angular sparsity order of the received signal based on joint sparse recovery of DOA. Furthermore, measurement innaccuracy caused by additive noise is explicitly handled. For this purpose, we employ the regularized MMV FOCal Underdetermined System Solver (Reg M-FOCUSS) method [1] which is one of the most efficient methods for DOA estimation. We compare the Constant False Alarm Rate (CFAR) performances of the proposed method with the well-known Maximum to Minimum Eigenvalue (MME) method [15]. The reminder of this paper is organized as follows. In Section II, we present the CS background theory. In Section

III, we describe the system model and formulate the spectrum sensing problem as a sparse recovery problem. Section IV describes the proposed spectrum sensing technique based on the joint sparsity order estimation at the angular domain. In Section V, simulation results illustrate the significant performance gain of the proposed method over the MME [15] detector in terms of Receiver Operating Characteristic (ROC) curves, CFAR performances and robustness toward an increasing number of PU source signals. Finally, Section VI concludes the paper. Notations: we use bold-face lowercase letters to denote vectors and bold-face capital letters to denote matrices. Superscripts (.)T and (.)H stand for transpose and complex conjugate transpose respectively. Iq is the identity matrix of order q. Given a matrix X ∈ CN ×L , xn. and x.l denote the nth row and the lth column of X, respectively. The ℓp -norm of a vector P p 1/p x ∈ CN is defined as kxkp = ( N for p ≥ 1 and n=1 |xn | ) its ℓ0 -norm is defined as the number of its non-zero entries. The support of x is defined as supp(x) = {n : xn 6= 0}. Finally, k.kF is the Frobenius norm operator. II. C OMPRESSED S ENSING BACKGROUND A vector of discrete-time signal samples x ∈ CN is Ksparse in some basis Ψ ∈ CN ×N if there exists s ∈ CN with K ≪ N non-zeros entries such as x = Ψs. CS theory deals with the reconstruction of x or equivalently its sparse coefficient vector s from M < N linear and non-adaptive measurements given by: y = Φx = ΦΨs = As M

(1) M×N

where y ∈ C is the measurement vector and Φ ∈ C is the measurement matrix incoherent with the sparsity basis Ψ such as the matrix A satisfy the RIP condition [5]. This reconstruction problem can be solved by finding the sparsest solution consistent with the measurement: min ksk0

s.t. y = As

(2)

s

While solving the sparse problem (2) by an exhaustive search is NP-hard, many popular sub-optimal but tractable approaches to solve the problem exist. Given a probabilistic reconstruction guaranty and additional constraints on the matrix A and the number of measurement M , these approaches are (see [16] and references therein) 1) greedy algorithms such as MP, OMP 2) convex relaxation by substituting the non-convex ℓ0 -norm operator by a convex diversity measure that still promotes sparsity, such as ℓ1 -norm in BP 3) nonconvex optimization using a non-convex sparsity inducing measure such as ℓ(p≤1) -norm-like in FOCUSS and 4) iterative thresholding algorithms such as IHT. In the case of noisy measurements, the robustness of these algorithms is handled by relaxing the equality constraint in (2), to allow some error tolerance. The problem becomes: min ksk0 s

s.t. ky − Ask22 ≤ ε

(3)

where ε ≥ 0 is an error tolerance threshold. The alternative augmented Lagrangian formulation is: min ky − Ask22 + λksk0

(4)

s

where the regularization parameter λ balances the tradeoff between quality of fit and sparsity of the solution. Extensions of the above mentioned algorithms to deal with noisy measurements are BPDN/LASSO, R-OMP and regularized FOCUSS. In the case of multiple snapshots corresponding to multiple observation instants, instead of a single measurement vector, multiple measurement vectors are available. In the noiseless setting: y(l) = As(l), l = 1, . . . , L (5) where the vectors {s(l)}L l=1 are jointly sparse, i.e. have nonzero entries at the same locations. Equivalently, the matrix formulation is: Y = AS (6) where Y ∈ CM×L and the matrix S ∈ CN ×L is row-sparse. Instead of coherent combining of the data to reduce the MMV problem to a SMV problem, in the MMV framework, CS deals with the reconstruction of S using a joint sparse recovery procedure that exploits the common sparse support, such as M-BMP, M-OMP and M-FOCUSS [1]. In the sequel, given a K-sparse vector x, the terms ”sparsity level” and ”sparsity order” are used interchangeably to refer to the number K, while the ”sparsity profile” and ”sparsity support” refer to the locations of the non-zero entries of x. III. S YSTEM M ODEL AND P ROBLEM S TATEMENT In this section, we present the system model adopted in our study and show how the PU detection problem is casted to a sparse recovery problem. A. System Model The system model, as illustrated in Fig. 1, consists of K farfield PUs and only one SU equipped with a uniformly-spaced linear array (ULA) of M omnidirectional antenna elements. The narrowband PU transmit signals are impinging on the SU antenna array from different and fixed angles of arrival K {θk }k=1 , where θk ∈ [− π2 , π2 ]. PU1 PUk

θ1 θk

d SU

Y

CS

θ

Detection

H0 /H1

θK PUK

Fig. 1. System Model

Given L snapshots, the lth observation at the SU can be expressed in a vector form as: y(l) = A(θ)s(l) + b(l),

l = 1, . . . , L

(7)

where y ∈ CM , θ = [θ1 , . . . , θK ]T is a parameter vector corresponding to the unknown angles of arrival, A(θ) = [a(θ1 ), . . . , a(θK )]T ∈ CM×K is the array manifold matrix whose columns are the so-called steering vectors. The steering vector corresponding to the k th PU source from the angle θk is 2πf a(θk ) = [1, νk , νk2 , . . . , νkM−1 ]T where νk = e−j υ d sin(θk ) , 2πf υ d sin(θk ) is the phase shift across neighboring antenna resulting from signal propagating over an extra distance, d is the inter-antenna spacing, f is the PU signal center frequency and υ is the speed of light. The vector of PU source signals s ∈ CK is assumed to be circularly symmetric complex Gaussian s ∼ CN (0, ΣK ) where ΣK is a diagonal matrix with  K diagonal entries σs2k k=1 representing the PU signal powers. Finally, b ∈ CM is the uncorrelated noise vector assumed to be circularly symmetric complex Gaussian b ∼ CN (0, σb2 IM ), where σb2 is the noise variance. B. Problem Formulation Given L snapshots, the signal model in (7) could be casted to a noisy MMV sparse signal representation over an overcomplete dictionary: Y = AS + B

(8)

where Y, B ∈ CM×L are the observation and noise matrices, A = [a(θe1 ), . . . , a(θeN )]T ∈ CM×N is a known grid angle scanning matrix composed of the N ≫ K steering vectors e and S ∈ corresponding to all potential angle of arrivals θ CN ×L is a K-row-sparse matrix such as: ( sk (l) if ∃ k | θen = θk , snl = (9) 0 otherwise. For the purpose of spectrum sensing, the detection problem can be expressed as a binary hypothesis testing: H0 :

Y=B

H1 :

Y = AS + B

Consider the vector σ = [σs21 , . . . , σs2K ]T ∈ RK + of PU signal powers and the K-sparse vector γ ∈ RN defined as: + ( σs2k if ∃ k | θen = θk , γn = (10) 0 otherwise.

The vector γ represents the deterministic and unknown parameter vector controlling the power of each row of S. As the sparsity profile of γ dictates that of S, the CSS problem (10) is reformulated as follows: H0 : γ=0 H1 : γ 6= 0 and sparse IV. A NGULAR S PARSITY O RDER BASED M ULTIPLE A NTENNA CSS The proposed CSS method is based on the recovery of the K-sparse vector γ of signal powers from N ≫ K potential angles of arrival. Therefore, a joint sparse recovery algorithm, namely Reg M-FOCUSS, is used to recover the row-sparse matrix S. Actually, an exact reconstruction of the transmitted

PU signals is not required and we need only to recover the sparsity order K reflecting PU presence, by a coarse estimation of the power vector γ. A. Sparse Estimation Stage The joint sparse recovery of the row-sparse matrix S is based on Reg M-FOCUSS algorithm which is an extension of the the generalized FOCUSS method in the noisy MMV framework. FOCUSS is a nonparametric algorithm for finding localized energy solutions from limited data based on an iterative process of reweighted ℓ2 -norm minimization. Within the iterative Reg M-FOCUSS, the recovered matrix S(j) at each iteration j is computed based on a reweighting process using the vector γ (j−1) of the ℓ2 -norms of the rows of the matrix S(j−1) computed at the previous iteration j −1. The j th iteration of Reg M-FOCUSS consists of the following steps:   p ∈ [0, 1] (11) W(j) = diag (γn(j−1) )1−p/2 (j−1) k2 where γn(j−1) = ksn.

Q(j) =

A(j)H (A(j) A(j)H + λI)−1 Y where A(j) = AW(j)

(12)

S(j) =

W(j) Q(j)

(13)

ˆ The convergence of the algorithm to a K-row-sparse stable b was established in [17]. In other words, γ (j) → γ b solution S ˆ b is K-sparse. and γ Furthermore, the update rule of Reg MFOCUSS is guaranteed to converge monotonically to a local minimum of: kY − ASk2F + λJ (p) (S) (14) where the regularization term J (p) (S) is the sparsity-inducing diversity measure defined as: J (p) (S) =

N X

p

(ksn. k2 ) ,

p ∈ [0, 1]

(15)

n=1

where p is the sparsity parameter and λ is the regularization parameter balancing the tradeoff between estimation quality and row sparsity. We set the ℓp -norm parameter p = 0.8 as suggested by the authors [1] to ensure a good compromise between speed of convergence and quality of the generated sparse solution. B. Sparse Detection Stage The detection stage is based on the sparsity order estimation ˆ of the joint sparse estimation γ b of the K-sparse source K powers vector γ. Given the problem formulation in (11), a ˆ = 0, then hypothesis H0 simple decision rule is applied: if K ˆ PU signals from is adopted, otherwise the SU decides that K ˆ K e {θnk }k=1 such as nk ∈ supp(b γ ) are present and hypothesis H1 is claimed. Actually, under hypothesis H0 , the sparse estimation stage ˆ > 0 resulting in a false alarm. At the same may lead to K time, setting a threshold on the sparsity order is not feasible, since any desired Pf a will not be attainable. As the ℓp -norm parameter is fixed p = 0.8, the only way to fix the false alarm probability to a desired target value is by properly tuning the regularization parameter λ.

V. S IMULATION R ESULTS

Scenario 2 : K = 2, θ = [10◦ , 50◦ ]. Scenario 3 : K = 4, θ = [−30◦ , 10◦ , 50◦ , 80◦ ]. In all figures, solid curves correspond to our proposed method and dashed ones correspond to the MME method, while circle, diamond and triangle markers correspond to scenario 1, 2 and 3, respectively. Except for Figure 4, where the number of snapshots is varying, the performance analysis demonstrated by all of Figures 2, 3 and 5, is conducted given very limited data corresponding to L = 10 snapshots. In Figure 2, we illustrate the performance of our proposed detector in terms of ROC curves, for M = 4 and SN R = −5dB. Our proposed method provides significant gain compared to the MME method, especially when the number of primary user increases, in which case the MME detector totally fails. The robustness of the two methods is compared in Figure 3, where the miss detection probability is provided as a function of SN R, at Pf a = 0.1 given a small observation time corresponding to the limited number of snapshots L = 10 and M = 4 antennas. Our proposed method outperformes the MME detector. For instance, the SNR wall defined as the minimum SNR below which PU detection is not reliable (Pmd > 0.1), is 6dB pushed back for Scenario 2. The effect of varying the number of snapshots, on the miss detection probability Pmd is shown in Figure 4, where M = 4, SN R = −5dB and Pf a = 0.1. When the number of PU increases, the reliability of our method is maintained with a 1 https://sites.google.com/site/researchbyzhang/software

0.9 0.8 0.7

Pd

0.6 0.5 0.4 0.3 Proposed K = 1 MME o Proposed K = 2 MME o Proposed K = 4 MME o

0.2 0.1 0

0

0.2

0.4

0.6

0.8

1

P

fa

Fig. 2. ROC curves for M = 4, L = 10, SN R = −5dB and K = 1, 2, 4 0

10

−1

Pmd

10

−2

10

−3

10

−4

10

−6

Proposed o K = 1 MME o Proposed K = 2 MME o Proposed K = 4 MME −4

−2

0 SNR(dB)

2

4

6

Fig. 3. Pmd as a function of SN R for M = 4, L = 10, Pf a = 0.1 and K = 1, 2, 4 1 Proposed o K = 1 MME o Proposed K = 2 MME o Proposed K = 4 MME

0.9 0.8 0.7 0.6 Pmd

In this section, the performance of the proposed spectrum sensing method is evaluated and compared to the reference MME method [15] under the CFAR principle. We recall that the MME detector compute the sample covariance matrix and compare its maximum to minimum eigenvalue ratio to a threshold. Our method is implemented based on the Reg MFOCUSS Matlab code provided online1 . The CFAR comparaison is ensured by a proper tuning of the trade-off parameter λ of the proposed method and the decision threshold of the MME method. For this purpose, empirical values are generated using 104 trials of a Monte Carlo simulation. As no prior knowledge is available on the eventual PU signal powers, the N -dimensional unit vector is chosen for the initialization of the power vector γ (j) . In other terms, γ (0) = [1, . . . , 1]T . The PK Signal-to-Noise Ratio is defined as SN R = ( k=1 σs2k )/σb2 . The measurement matrix A is built using an inverse uniform e of N = 201 potential angles within the sinusoidal grid θ π π range [− 2 , 2 ]. Obviously, in the case that a PU signal is e its power contribution leaks into the incoming from θk 6∈ θ, closest angle within the grid. We take the distance d half the signal wavelangth f /υ. For all the simulations, 3 scenarios with different number of PUs with the same transmit power, are considered: Scenario 1 : K = 1, θ = [20◦ ].

1

0.5 0.4 0.3 0.2 0.1 0 10

15

20

25 30 35 Number of Snapshots L

40

45

50

Fig. 4. Pmd as a function of L for M = 4, SN R = −5dB, Pf a = 0.1 and K = 1, 2, 4

1

R EFERENCES

0.9 0.8 0.7

Pmd

0.6

Proposed K = 1 MME o Proposed K = 2 MME o Proposed K = 4 MME o

0.5 0.4 0.3 0.2 0.1 0

2

3

4

5 6 Number of Antenna M

7

8

Fig. 5. Pmd as a function of M for L = 10, SN R = −5dB, Pf a = 0.1 and K = 1, 2, 4

growing number of snapshots, while increasing the observation time becomes almost useless for the MME detector. Figure 5. compares the miss detection probability of the two methods for different number of SU receiver antennas M , at SN R = −5dB and Pf a = 0.1. Given the very limited number of snapshots, the MME performance is no longer enhanced by an increasing number of antenna. On the contrary, our proposed method performs better for each additional element in the SU antenna array. Indeed, when the number of sensors and the number of snapshots get closer together, the covariance matrix estimation involved within the MME detector becomes unreliable. On the contrary, the sparse estimation reliability is maintained by using Reg M-FOCUSS even when the number of snapshots is smaller then the number of sensors [1]. VI. C ONCLUSIONS We presented a novel approach for multiple antenna spectrum sensing based on the angular sparsity order of the received signal. We use the regularized M-FOCUSS algorithm for the joint sparsity order estimation and propose a simple decision rule for PU detection. The performance of our method is compared to the reference MME method by simulations. Our method show significant CFAR performance gain in terms of reduced number of samples, better SNR walls and better detection probability, especially in the case where the number of PUs increases.

[1] S. Cotter, B. Rao, K. Engan, and K. Kreutz-Delgado, “Sparse solutions to linear inverse problems with multiple measurement vectors,” IEEE Transactions on Signal Processing, vol. 53, no. 7, pp. 2477–2488, 2005. [2] I. F. Akyildiz, B. F. Lo, and R. Balakrishnan, “Cooperative spectrum sensing in cognitive radio networks: A survey,” Physical Communication (Elsevier) Journal, vol. 4, no. 1, pp. 40–62, 2011. [3] A. Taherpour, M. Nasiri-Kenari, and S. Gazor, “Multiple antenna spectrum sensing in cognitive radios,” IEEE Transactions on Wireless Communications, vol. 9, no. 2, pp. 814–823, 2010. [4] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006. [5] E. J. Candes, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Communications on pure and applied mathematics, vol. 59, no. 8, pp. 1207–1223, 2006. [6] Z. Tian and G. B. Giannakis, “Compressed sensing for wideband cognitive radios,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 4, 2007, pp. IV–1357. [7] J. A. Bazerque and G. B. Giannakis, “Distributed spectrum sensing for cognitive radio networks by exploiting sparsity,” IEEE Transactions on Communications, vol. 58, no. 3, pp. 1847–1862, march 2010. [8] Z. Fanzi, C. Li, and Z. Tian, “Distributed compressive spectrum sensing in cooperative multihop cognitive networks,” IEEE Journal of Selected Topics in Signal Processing, vol. 5, no. 1, pp. 37–48, 2011. [9] H. Moussavinik and W. G. A. Hayar, “Centralized collaborative compressed sensing of wideband spectrum for cognitive radios,” in International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2010, pp. 246–252. [10] F. Deng, Z. Fanzi, and R. Li, “Clustering-based compressive wideband spectrum sensing in cognitive radio network,” in 5th International Conference on Mobile Ad-hoc and Sensor Networks(MSN), 2009, pp. 218–222. [11] Y. Wang, A. Pandharipande, Y. Polo, and G. Leus, “Distributed compressive wide-band spectrum sensing,” in Information Theory and Applications Workshop, 2009, pp. 178–183. [12] L. T. Tan and H.-Y. Kong, “A novel and efficient mixed-signal compressed sensing for wide-band cognitive radio,” in International Forum on Strategic Technology (IFOST), 2010, pp. 27–32. [13] S. Monfared, A. Taherpour, and T. Khattab, “Compressed wideband spectrum sensing with correlated subband occupancy in multi-antenna cognitive radios,” in IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), 2012, pp. 2195– 2201. [14] D. Malioutov, M. C ¸ etin, and A. S. Willsky, “A sparse signal reconstruction perspective for source localization with sensor arrays,” IEEE Transactions on Signal Processing, vol. 53, no. 8, pp. 3010–3022, 2005. [15] Y. Zeng and Y.-C. Liang, “Eigenvalue-based spectrum sensing algorithms for cognitive radio,” IEEE Transactions on Communications, vol. 57, no. 6, pp. 1784–1793, 2009. [16] Y. C. Eldar and G. Kutyniok, Compressed Sensing: Theory and Applications. Cambridge University Press, 2012, vol. 95. [17] B. D. Rao, K. Engan, S. F. Cotter, J. Palmer, and K. Kreutz-Delgado, “Subset selection in noise based on diversity measure minimization,” IEEE Transactions on Signal Processing, vol. 51, no. 3, pp. 760–770, 2003.