COMPRESSIVE SPECTRUM SENSING FOR COGNITIVE RADIO
NETWORKS
By
UKASH NAKARMI
Bachelor of Engineering in Electronics and
Communication
Tribhuvan University
Kathmandu, Bagmati, Nepal
2008
Submitted to the Faculty of the
Graduate College of
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
Dec, 2011
COMPRESSIVE SPECTRUM SENSING FOR COGNITIVE RADIO
NETWORKS
Thesis Approved:
Dr. Nazanin Rahnavard
Thesis Adviser
Dr. Qi Cheng
Dr. Johnson P Thomas
Dr. Sheryl A. Tucker
Dean of the Graduate College
ii
TABLE OF CONTENTS
Chapter Page
1 INTRODUCTION 1
1.1 Motivation: Spectrum Demand and Scarcity . . . . . . . . . . . . . . 1
1.2 Cognitive Radio and Spectrum Sensing . . . . . . . . . . . . . . . . . 2
1.2.1 Cognitive Radio Challenges . . . . . . . . . . . . . . . . . . . 4
1.3 Outline of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 BACKGROUND AND LITERATURE REVIEW 7
2.1 Cognitive Radio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Conventional Spectrum Sensing Techniques . . . . . . . . . . . . . . . 9
2.2.1 Matched Filter . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Cyclostationary Feature Detection . . . . . . . . . . . . . . . . 11
2.2.3 Pilot and Radio Detection . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Waveform Based Sensing . . . . . . . . . . . . . . . . . . . . . 13
2.2.5 Energy Detector . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Introduction to Compressive Sensing . . . . . . . . . . . . . . . . . . 17
2.3.1 Compressible Signals . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.2 Compressive Sampling . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Compressive Sensing Reconstruction . . . . . . . . . . . . . . 21
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 WIDE BAND SPECTRUM SENSING FOR COGNITIVE RADIO
NETWORK USING DISTRIBUTED COMPRESSIVE SENSING 23
iii
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Proposed Compressive Spectrum Sensing . . . . . . . . . . . . . . . . 28
3.4.1 Generation of Sensing Matrix . . . . . . . . . . . . . . . . . 28
3.4.2 Compressed Measurements . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Compressive Decoding . . . . . . . . . . . . . . . . . . . . . . 30
3.5 Simulation and Results . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 JOINT WIDE BAND SPECTRUM SENSING IN FREQUENCY
OVERLAPPING COGNITIVE RADIO NETWORK USING DIS-TRIBUTED
COMPRESSIVE SENSING 39
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 ProposedWideband Compressive Spectrum Sensing in Frequency Over-lapping
Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.1 Sensing Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 Compressed Measurement Y . . . . . . . . . . . . . . . . . . . 42
4.2.3 Compressive Sensing Decoding . . . . . . . . . . . . . . . . . . 43
4.3 Simulation and Results . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 BINARY COMPRESSIVE SENSING 55
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Related Work and Contribution . . . . . . . . . . . . . . . . . . . . . 57
5.3 Binary Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . . 58
5.3.1 The Sampling Matrix, . . . . . . . . . . . . . . . . . . . 60
5.3.2 Compressed Measurements and the Check Nodes . . . 61
iv
5.3.3 Compressive Sensing Decoding . . . . . . . . . . . . . . . 61
5.4 An Alternative Approach . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Compressive Sensing Decoding . . . . . . . . . . . . . . . . . . 66
5.5 Analysis and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.5.1 Choice of Row-Weight (L) . . . . . . . . . . . . . . . . . . . . 66
5.5.2 Encoding and Decoding Complexity . . . . . . . . . . . . . . . 69
5.5.3 The Number of Measurements (M) . . . . . . . . . . . . . . . 69
5.5.4 The Error Rate (E.R) . . . . . . . . . . . . . . . . . . . . . . 70
5.6 Simulation and Results . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6 CONCLUSIONS AND FUTURE WORKS 80
6.1 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
BIBLIOGRAPHY 85
v
LIST OF FIGURES
Figure Page
1.1 Spectrum demand and scarcity . . . . . . . . . . . . . . . . . . . . . 1
1.2 The NTIA frequency allocation chart . . . . . . . . . . . . . . . . . . 2
2.1 Cognitive radio cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Various aspects of spectrum sensing for cognitive radios . . . . . . . . 10
2.3 Cyclostationary feature detection . . . . . . . . . . . . . . . . . . . . 12
2.4 Pilot Signalling in Primary Radio . . . . . . . . . . . . . . . . . . . . 13
2.5 Basic block diagram of the energy detector . . . . . . . . . . . . . . . 15
2.6 Implementation of FFT in energy detector . . . . . . . . . . . . . . . 16
2.7 Tradeoffs in complexity and accuracies of sensing methods . . . . . . 17
2.8 Traditional sampling and data compression . . . . . . . . . . . . . . . 18
2.9 Compressive sampling/sensing . . . . . . . . . . . . . . . . . . . . . . 18
2.10 Compressive sampling measurement process . . . . . . . . . . . . . . 20
2.11 CS Reconstruction Geometry. (a) Sparse vector in R3. (b) l2 mini-mization.
(c) l1 minimization. . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Primary and secondary users coexistence . . . . . . . . . . . . . . . . 25
3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Probability of Detection in Noiseless Measurements . . . . . . . . . . 33
3.4 Error Of Reconstruction in Noiseless Measurements . . . . . . . . . . 34
3.5 Probability of Detection in Noiseless Measurements using OMP . . . 34
3.6 Error Of Reconstruction in Noiseless Measurements using OMP . . . 35
3.7 Probability of Detection in Noisy Measurements . . . . . . . . . . . . 36
vi
3.8 Error of Reconstruction in Noisy Measurements . . . . . . . . . . . . 36
3.9 Probability of Detection using Reweighted l1 Minimization . . . . . . 37
3.10 Error of Reconstruction using Reweighted l1 Minimization . . . . . . 37
4.1 Schematic of overlapping networks and overlapping spectrum bands . 41
4.2 Joint spectrum sensing schematic in frequency overlapping networks . 45
4.3 POD using individual and joint reconstruction . . . . . . . . . . . . . 47
4.4 EOR using individual and joint reconstruction . . . . . . . . . . . . . 48
4.5 POD using individual and joint reconstruction in noisy measurements 49
4.6 EOR using individual and joint reconstruction in noisy measurements 49
4.7 Measurement gain for varying SOF when POD=0.99 . . . . . . . . . 50
4.8 ROC performance for different SNR . . . . . . . . . . . . . . . . . . . 51
4.9 ROC performance comparison, For SNR=-5dB, S.R=0.6 and Spar-sity=
40% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.10 EOR comparison, For SNR=-5dB, S.R=0.6 and Sparsity=40% . . . . 52
4.11 Original time domain signal and reconstructed using individual recon-struction
method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.12 Original time domain signal and reconstructed using joint reconstruc-tion
method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1 Representation of Compressive Sensing with Bipartite Graph . . . . . 59
5.2 Reduced Graph after the First cycle of First Phase Recovery and Edge
Removal and Check Nodes Update . . . . . . . . . . . . . . . . . . . 64
5.3 Probability of zero and light check nodes for different row-weight . . . 68
5.4 Probability of Check Nodes Recovered in First Iteration (CNRP) . . 72
5.5 Numbers of Check Nodes Recovered in First Iteration (CNRN) . . . . 73
5.6 Error Rate for different Row Weight . . . . . . . . . . . . . . . . . . 74
5.7 Row weight and Decode Time . . . . . . . . . . . . . . . . . . . . . . 74
vii
5.8 Error Rate for different Sampling Rate and Row weight . . . . . . . 75
5.9 Original and Reconstructed Signal using Binary l1 and Our Scheme . 76
5.10 Error Rate Comparison with Binary l1 scheme with threshold . . . . 77
5.11 Decode Time comparision Binary l1 scheme with threshold . . . . . . 77
5.12 Maximum heavy node degree . . . . . . . . . . . . . . . . . . . . . . 78
6.1 Spectrum occupancy state variation in spatio-temporal region . . . . 82
6.2 Wireless sensor network with dynamic and rapid event changes . . . . 83
viii
CHAPTER 1
INTRODUCTION
1.1 Motivation: Spectrum Demand and Scarcity
New advancements in wireless technologies have created an excessive demand of the
wireless spectrum and resources. Current spectrum usage paradigm reflects fixed
spectrum allocation technique. The available wireless spectrum resources have been
assigned to existing wireless technologies. The excessive use of wireless spectrum and
regulations imposed by the Federal Communications Commission (FCC) have created
spectrum scarcity. Fig. 1.1 shows the train of increase in spectrum demand. The
spectrum allocation chart in United States (Fig. 1.2) by National Telecommunications
and Information Administration’s (NTIA) shows the overlapping spectrum allocation
that clearly reflects the spectrum scarcity mindset. Figs. 1 and 2 clearly reflect
Time
N: Demand
K: N<K Available Resources
N~K
N>K
Demand
Figure 1.1: Spectrum demand and scarcity
the growing spectrum scarcity. FCC has shown its concerns regarding the excessive
1
spectrum demand at a rate faster than that can be made available. The demand of
spectrum is out stripping supply and we are in the danger of Spectrum Drought. On
Figure 1.2: The NTIA frequency allocation chart
one hand, we are facing spectrum scarcity, whereas on the other hand, recent spectrum
survey by spectrum policy task force (SPTF) shows that the wireless spectrum has
been used inefficiently and the wireless resources are underutilized. The report shows
the temporal and geographic variation in spectrum usage ranging from 15% to 85% [1].
A recent study by the Shared Spectrum [2] shows that over the spectrum band of
30 MHz to 3000 MHz over multiple locations, the spectrum usage is just 5.2% and
maximum occupancy of 13% was recorded in New York city. These reports reflect
the inefficient spectrum usage because of the spectrum distribution and licence and
call for the new methods to tackle the spectrum bottleneck in wireless domain.
1.2 Cognitive Radio and Spectrum Sensing
The reports on spectrum usage clearly show that the problem of spectrum scarcity
is not because of spectrum in-abundance but, it is because of inefficient usage and
distribution. The spectrum reallocation and creating new spectrum allocation chart
2
is unfortunately not feasible as it is not possible to predict the future usage and
demand of the spectrum, and also it is infeasible to create a uniform spectrum distri-bution
policy that can meet the varying spatial temporal spectrum demand. Besides,
any conflicts in spectrum reallocation will suffer opposition from the existing owners
or users of the spectrum. Thus, unharmed and unaffected access of spectrum for
the “primary users” is priority in development of any new efficient spectrum access
scheme. These conflicts in spectrum scarcity and inefficient utilization call for the
new technology which should be able to optimize the spectrum usage. The concept
of Cognitive Radio (CR) was recently proposed in [3], which introduces a concept of
secondary users (SR) or (CR) for efficient spectrum utilization. Mitola considered CR
as the radio in which every possible parameter observed by wireless node/network is
taken into account while making the decision on the transmission/reception. It is a
system that sense, and is aware of, its operational environment and can dynamically
and autonomously adjust its radio operating parameters accordingly. CR is: “A radio
that employs the model based reasoning to achieve a specific level of competence in
radio-related domains”. The primary objectives of a cognitive radio are two folds:
• Efficient utilization of wireless spectrum
• Reliable communications without affecting primary users
To achieve these objectives the primary task of CRs is to efficiently sense the primary
users in the environment. A spectrum is said to be vacant when there are no primary
users. The CRs should continuously monitor and sense the spectrum and efficiently
use the vacant spectrum (Spectrum Holes) without disrupting the primary users. So,
spectrum sensing is a mechanism of detecting presence or absence of primary users
in the environment and hence find the available spectrum holes for the secondary
communication purposes.
3
1.2.1 Cognitive Radio Challenges
The primary users or the current spectrum owners are not so receptive about the
cognitive radios and the spectrum trade policies as they are likely to cause disruption
to their access in the wireless spectrum and resources. The fundamental challenges
in cognitive radio are efficiently identifying vacant bands over a wide band of spec-trum
over spatio temporal domain and maintaining Signal to Noise ratio (SNR) of
secondary users communications [4] [5]. CRs have to be able to dynamically sense
the radio spectrum and adapt its transmitter parameters according to the dynamic
surrounding radio environment. The wideband spectrum sensing requires very fast
digital sampler with high resolution to meet the dynamic and wide spectrum charac-teristics.
Besides, the radio sensitivity of CRs have to be very precise with sensing
interval as short as possible to meet the agility requirements. The implementation
challenges in wideband spectrum sensing for Cognitive radios can be broadly seen
under following categories.
• Detection Capability: The Primary users are not so receptive about the CR
concept because of the harmful effects CR could cause them. A CR may not be
able to correctly detect the spectrum and may start using it when primary user
needs it and hence results in interference in the primary user communications.
CRs not only have to sense the spectrum before beginning its transmission but
also have to continuously sense during its transmission period so as to detect the
reappearance of primary users anytime and vacate the spectrum for the primary
users. Thus receiver sensitivity is also key factor in cognitive radio network. Be-sides,
the dynamic fading and noisy communications channel makes finding the
threshold for spectrum detection and decision process complex. Sensing time
duration is also an important factor as C.Rs cannot afford spending long du-ration
in spectrum sensing because it not only has to use the spectrum for its
own communication purposes, but it should also be able to vacate the spectrum
4
immediately after a primary user reappears. The SNR margin for secondary
communication creates the tradeoff between the receiver sensitivity and trans-mission
power allocation. This requires CRs to have adaptive transmit power
based upon the communications environment.
• Wideband Sampling Circuitry: Wideband spectrum sensing is a challenging
task because of dynamic wide range of the frequency bands. It requires either
discrete grouping of wide spectrum into the narrowbands and utilizes multiple
narrowband sensing or use the digital signal processors to sample the wideband
analog signal and then perform spectrum sensing. Unfortunately, the multiple
narrowband sensing is not feasible and less attractive because of its complex
structure in wideband model, whereas the DSP necessitates high speed ADCs.
A new sampling paradigm based upon sparse sampling named Compressive Sensing
(CS) provides a sampling mechanism at rates lower than the Nyquist rates. The
signal reconstruction scheme in compressive sensing is a norm optimization problem.
In this thesis, we present a novel spectrum sensing mechanism for cognitive radio
based upon the compressive sensing.
1.3 Outline of Thesis
The rest of the thesis is organized as follows. In the Chapter 2, we provide brief intro-duction
to the spectrum scarcity and cognitive radio technique. A general outline of
important spectrum sensing approaches is presented. A brief and quick introduction
of compressive sensing and decoding approaches is also presented. In the Chapter 3,
we propose wideband spectrum sensing for single network cognitive radio system using
compressive sensing. Compressive sensing based joint spectrum sensing in frequency
overlapping networks is proposed in the Chapter 4. We exploit the joint sparsity of the
overlapped region to have better spectrum sensing performance at minimal cost. A
5
novel compressive sensing scheme for Binary signals is proposed in the Chapter 5. We
implement the bipartite graphs to represent the binary compressive sensing process.
A unique, but universal sampling matrix for binary signal is developed and graph and
check-sum based decoding scheme for binary compressive sensing is proposed.
6
CHAPTER 2
BACKGROUND AND LITERATURE REVIEW
In this chapter, we present a brief introduction to cognitive radio and compressive
sensing techniques. We will discuss about different stages of cognitive radio cycle and
importance of spectrum sensing in cognitive cycle. We will present a critical viewpoint
on different conventional spectrum sensing techniques and some new approaches to
them. We shall also present an overview on new emergent sampling theory called
compressive sensing for sparse signals.
2.1 Cognitive Radio
The widespread acceptance of wireless technologies has created an unexpected de-mand
of wireless bandwidths and is well expected to grow in future as well. Spectrum
licensing has been the traditional approach to ensure the diverse wireless systems.
However, due to the surplus demand, the frequency allocation have overlapped and
left very small space for new emerging systems. On the contrary, the varying demand
and utilization have created many of the allocated frequencies unused and vacant
(spectrum holes) over spatio-temporal domain. The contrary in supply - demand
and utilization have urged to look for new methods to accommodate secondary (un-licensed)
wireless devices without disrupting the primary (licensed) users. Cognitive
radio in a broad sense refers to various solutions that seek to overlay, underlay or
interweave the secondary user’s signals with the primary users.
Cognitive radio is an idea to take advantage of open spectrum policy. It should be
designed to adapt dynamically to its environment and find the communication channel
7
ensuring minimal interference to the licensed users. The definition of cognitive radio
is very broad as its functions are dynamic. FCC has defined cognitive radio as:
A radio frequency transmitter receiver that is designed to intelligently
detect whether a particular segment of radio spectrum is currently in use,
and to jump into (and out of) the temporary unused spectrum very rapidly
without interfering with the transmission of other authorized users.
In [6], CR is defined as :
Cognitive radio is an intelligent wireless communication system that is
aware of its surrounding environment and uses the methodology of ‘under-standing
by building’ to learn from the environment and adapt its internal
states to statistical variations in the incoming RF stimuli by making cor-responding
changes in certain operating parameters (e.g. transmit power,
carrier frequency, modulation strategy) in real time, with two primary ob-jectives
in mind: highly reliable communication whenever and wherever
needed and efficient utilization of radio spectrum.
Basically, a cognitive radio has following capabilities:
• Sensors creating awareness in the environment
• Actuators enabling interaction with the environment
• Memory and a model of the environment
• Learning and modeling of specific beneficial adaptations
• Specific performance goals
• Autonomy
8
Global
States
Pre-process
New
States
Prior
States
Observe
Outside
World
Orient
Infer on context hierarchy
Establish Priority
Act
Decide
Urgent
Plan
Normal
Immediate
Learn
Register to current time
Allocate resources
Initiate process
Send message
Alternatives
Receive message
Figure 2.1: Cognitive radio cycle
In [7], cognitive radio cycle has been proposed as a top level loop for cognitive radio
system. The cognitive cycle mainly consists of observe, orient, plan, decide and act
(OOPDA). In cognitive cycle information about the communication environment is
received by a cognitive radio through the direct observation or the stimuli signaling.
In orient stage, based upon the received environment information a CR determines
the importance and urgency. Planning, including negotiations with peers for best
alternatives is considered in planning stage. Best decision is made based upon the
alternatives and consequences and finally a CR acts by adjusting its resources and
performs appropriate signaling. The cognitive cycle is shown in the Fig. 2.1.
2.2 Conventional Spectrum Sensing Techniques
Several factors make spectrum sensing practically challenging. Communication chan-nel
noise, multipath fading in environment makes spectrum sensing a complex prob-lem.
Receiver sensitivity of the spectrum detectors needs SNR of the signal to be
above some threshold value to sense the signal. The SNR at the receiver may not
9
Figure 2.2: Various aspects of spectrum sensing for cognitive radios
be always greater than the threshold value because of noise and fading. Time dis-persion
of wireless signal makes coherent detection infeasible whereas the spatio-temporal
varying noise interference characteristics yield power uncertainty issues in
spectrum sensing [8, 9, 10]. Considering these facts, various aspects of spectrum
sensing are taken into account while implementing efficient spectrum sensing method.
Fig. 2.2 [11] reflects various aspects of spectrum sensing.
In the following section we will discuss about some of the most common approaches
of spectrum sensing.
2.2.1 Matched Filter
A matched filter maximizes the signal to noise ratio, so when the information of
the PU signal is known matched filter is an optimal method for any kind of signal
detection [12]. Although, match filters are optimal and the coherency requires less
time to achieve high processing gain, it is less attractive for practical purposes as
it requires prior knowledge of the primary signal. Though information regarding a
signal can be stored in memory, the synchronization and channel equalization remains
10
inevitable. Besides, a secondary user or spectrum detector requires extra circuitry
to achieve carrier synchronization. So, in wideband spectrum sensing even though
we have prior information regarding the signal, the dynamic signal characteristics in
wideband communication makes it less feasible. Compressive detector using matched
filters have been proposed in [13, 14]. Despite of its drawbacks matched filter is
applicable to certain class of primary network with uniform signal characteristics and
information about the signal is known in prior.
2.2.2 Cyclostationary Feature Detection
A signal is said to have a cyclostationary process if its statistical properties vary
cyclically with time. Modulated signals are generally coupled with periodic carri-ers
like sine wave, pulse trains, hoping sequences or cyclic prefixes which gives the
periodicity to the signal. This periodicity helps in detecting and identifying the
signal in noise dominant environment. Let x(n) be a discrete time series with mean
μx(n) := E{x(n)} and covariance cxx(n; ) := E{[x(n)−μx(n)][x(n+ )−μx(n+ )]}.
For x(n) complex valued, the covariance is a complex conjugate, and n and are sets
of integer Z, then from [15] :
Process x(n) is cyclostationary iff, there exists an integer P such that
μx(n) = μx(n + lP), cxx(n; ) = cxx(n + lP; ), 8n, l 2 Z. The smallest
of all such Ps is called the period and its fourier coefficients called cyclic
correlation are related by :
cxx(n; ) =
PX−1
k=0
Cxx(
2
P
k; )ej 2
P kn $ Cxx(
2
P
k; ) =
1
P
PX−1
n=0
cxx(n; )e−j 2
P kn
(2.1)
The main advantage of spectral correlation in detection is that it differentiates
the noise energy from signal energy because of the spectral correlation in modulated
signal. A cyclostationary approach for signal detection is discussed in [16, 17]. Fig.
11
Decision (Detection)
r(t)
BPF
BPF
r(t) j at e − 2p
j at e − 2p
T
.
SCF Generation
SCF Generation
Unique Cycle
Frequency
(a ) searching
Figure 2.3: Cyclostationary feature detection
2.3 shows basic implementation of cyclostationary detection method using spectrum
correlation function (SCF). In this method, signal information like phase, frequency
and timing parameters are preserved for comparison. Though, this method is efficient
for signal detection in noisy environment it requires longer sensing time to collect sta-tistical
parameters over long period of time. Moreover, it is computationally complex
and requires prior knowledge about the signal.
2.2.3 Pilot and Radio Detection
Knowledge about the signal and its characteristics help in signal detection and iden-tification.
Such information enables cognitive radio with higher dimension knowledge
and provides higher accuracy. For example, if it is known that the primary signal is a
bluetooth signal, CR use this information for extracting information in space dimen-sion.
Radio identification techniques are used in European Transparent ubiquitous
project (TRUST) [18]. In radio identification based sensing [19, 20], different features
of signal are extracted and are classified using standard classification techniques and
are compared with the primary signal prior information and decision is made accord-
12
Unknown activity
pilot
Unknown activity
B
c f f
Figure 2.4: Pilot Signalling in Primary Radio
ingly. For example, in Pilot detection technique, the energy of the primary signal
is confined inside a prior known bandwidth around the central frequency (Fig. 2.4)
and activity outside it, is unknown. A primary signal sends periodic pilots and based
upon the pilot sequences detection, a primary radio is identified. Signal detection in
UWB impulse radio using pilot sequences is discussed in [21]. Radio identification
suffers same drawbacks as the cyclostationary scheme, thus these schemes are not so
attractive though they have better performance in discriminating against noise.
2.2.4 Waveform Based Sensing
Waveform based sensing is not a complete spectrum sensing approach in itself. In
this method, various characteristics of a signal are exploited. The metric so formed
from those characteristics like preamble, spreading sequences etc is compared with
the standard threshold and the decision is made accordingly. Let us consider a system
as :
y(n) = s(n) + w(n) (2.2)
13
where, y(n), s(n), w(n) are received signal, primary signal and noise, respectively.
The waveform based sensing metric is defined in [22] as:
M = Re
"
XN
n=1
y(n)s (n)
#
(2.3)
where, * represents the conjugation. In absence of the primary signal the value of M
becomes:
M = Re
"
XN
n=1
w(n)s (n)
#
(2.4)
whereas, in presence of the primary signal the decision metric becomes:
M =
XN
n=1
|s(n)2| + Re
"
XN
n=1
w(n)s (n)
#
(2.5)
The metric thus obtained is compared with the standard threshold value w and
decision is made accordingly. Waveform based sensing using preambles is discussed
in [23, 24]. Though waveform based sensing requires shorter sensing time [25] and can
sense the signal at known environments they suffer from synchronization problems.
2.2.5 Energy Detector
Energy detector based techniques in spectrum sensing are most common approach in
cognitive radio. Energy detection schemes, also known as radiometer or periodogram
are widely used because of it’s simple structure and computational gains [26, 27, 28].
When no information about the primary signal is known, and only the noise charac-teristics
of channel are known, energy detector is the optimal solution for spectrum
sensing. Basically, energy detector consists of a bandpass filter to out pass the out
band noise and adjacent signals and is followed by a sampler, square law device and an
integrator as shown in the Fig. 2.5. A band filtered signal is squared and integrated
over the period to find the energy of the received signal and then compared with the
threshold e and decision is made accordingly. Let us consider a system defined as:
y(n) = x(n) + w(n) (2.6)
14
ò y(t)
( . )2
Td Y
Decision
Figure 2.5: Basic block diagram of the energy detector
where, y(n), x(n) andw(n) are received signal, primary signal and the noise, respec-tively.
Then for Energy detection scheme, test statistic is given by:
T =
X
N
(Y [n])2 (2.7)
The decision making process in energy detector is equivalent to distinguishing between
the following two hypotheses:
H0 : y(n) = w(n) (2.8)
H1 : y(n) = x(n) + w(n) (2.9)
Expressions ( 2.8) and ( 2.9) are respectively cases of absence and presence of pri-mary
signal. The dectection performance of energy detector can be seen under two
parameters viz: probability of detection PD and probability of false alarm PF which
can be formulated as:
P(D) = Pr(T > e|H1) (2.10)
P(F) = Pr(T < e|H0) (2.11)
So the goal in energy detector is always increasing PD and decreasing PF .
The time domain energy computation of a signal is inflexible in case of narrowband
signals because of pre-filter matching problem. So energy computation in frequency
15
K pt
FFT
(.)2 Average M bins
N times
y(t)
A/D
Test statistics
Figure 2.6: Implementation of FFT in energy detector
domain is another prevailing approach. Fourier coefficients of received signals are used
to calculate the energy using Parseval’s theorem. The frequency resolution of FFT
increases with the number of points ‘K’ which is equivalent to increasing the sensing
time of pre filter in time domain analysis. Fig. 2.6 shows the basic block diagram
of energy detector in the frequency domain. The major challenge in energy detector
scheme is estimating the appropriate threshold parameter. Though no information
about the primary signal is required in this scheme, when the noise characteristics
cannot be modeled, optimizing e is a difficult challenge. In [29], the author has used
decode and forward scheme in energy detectors to improve its performance in fading
and noisy environment. For its simple implementation structure and computational
gain energy detector is still one of the most feasible and commonly used approach in
spectrum sensing.
Different spectrum sensing approaches have their own pros and cons based upon
the communication environment. There is always a tradeoff between the complexity
and the efficiency between different approaches of spectrum sensing. When noise
characteristics are known energy detector outperforms other sensing approaches in
terms of both accuracy and complexity. But when noise information are not known,
other schemes like cyclostationary and waveform based approaches are preferred.
Waveform based approach performs better when signal characteristics information are
prior. So, for detection of known signals waveform and cyclostationary schemes are
suitable. On the contrary, these approaches are very sensitive to hardware precession,
16
Figure 2.7: Tradeoffs in complexity and accuracies of sensing methods
clock synchronization and timing. Fig: 2.7 [11] provides a very broad comparison
between different spectrum sensing approaches. Based upon the facts that energy
detector is very simple to implement, computationally efficient and requires no any
prior information about the signals, it is still most commonly used in spectrum sensing
for cognitive radios.
2.3 Introduction to Compressive Sensing
Data acquisition and sampling is an important factor in digital systems. The Nyquist
sampling theorem specifies that in order to recover a signal from its samples, the sam-pling
process should be at least two times faster than the signal bandwidth. In many
applications, including digital images, large communication networks the Nyquist rate
is so high that it results too many samples, necessitates data compression, high-speed
analog-to-digital converters, and makes the data acquisition very expensive. How-ever,
Compressive Sensing, (CS) a novel sensing/sampling paradigm goes against the
17
common wisdom in data acquisition. CS theory asserts that one can recover certain
signals and images from far fewer samples or measurements than traditional meth-ods
[30, 31]. Compressive sensing is distinct from traditional single point sampling
approaches and data compression in two very broad sense. In CS, each sample is
linear functional of the original signal and, compression is carried in the data acquisi-tion
process itself rather than compressing the sampled data as in conventional data
compression techniques. This difference is shown in the Figs. 2.8 and 2.9.
M N
M
N>>M
N
Sample Compress Transmit/Store
Receive Decompress
Figure 2.8: Traditional sampling and data compression
M
M
N>>M
N
Compressive Sensing Transmit/Store
Receive Decode
Figure 2.9: Compressive sampling/sensing
18
2.3.1 Compressible Signals
CS relies on two principles: sparsity, which pertains to the signals of interest, and
incoherence, which pertains to the sensing modality. A signal is said to be sparse, if
it contains few non-zero elements and other zeros. A real-valued, finite-length, one-dimensional,
discrete-time signal X, X 2 {R}N with elements x[n], n = 1, 2, . . .N can
be represented in terms of a basis of N ×1 vectors { i}Ni
=1. Using N ×N basis matrix
= [ 1| 2| . . . N] with the vectors { i} as columns, a signal X can be expressed as
X =
XN
i=1
si i, i.e. X = S. (2.12)
The signal representation of X in domain is given by S and they are equivalent.
The signal X is called K sparse in if it is linear combination of K basis vectors,
i.e. only K elements of the S are non-zeros and other are zeros. In this special case,
when a signal X is sparse in some domain and K << N, X is said to be compressible.
2.3.2 Compressive Sampling
Let us consider, a real valued signal X 2 {R}N be a compressible signal in some
domain as discussed in the Section 2.3.1. Let us consider a sampling/sensing matrix
of dimension M × N, M < N. The sampling matrix is used to to generate M
linear measurements of signal X. Consider, a N length vector j , j = 1 : M, then the
compressed measurements can be expressed as an inner products between X and js
as, yj = hX, ji. Arranging, yjs in a M length vector Y , and measurement vectors
T
j as rows of sampling matrix , the compressive sampling process can be expressed
as:
Y = X = S = S. (2.13)
The Compressive sampling measurement process is depicted in the Fig. 2.10.
The sampling matrix does not depend on the the signal X, however, it has to
be stable and incoherent with the matrix. Some examples of suitable matrices
19
Y Y
Figure 2.10: Compressive sampling measurement process
are:
• Gaussian : i,j = N (0, 1
M )
• Bernouilli/rademacher
• Sparse Gaussian
• Random orthoprojection
In [32, 30], the robustness of CS measurement matrix is studied and the so called
Restricted Isometry Property (RIP) is proposed. For the matrix, = , the isom-etry
constant s, is defined as the smallest number such that
(1 − s)||S||22
|| S||22
(1 + s)||S||22
. (2.14)
Then, the matrix is said to have RIP of order S, if s is not close to 1. The mutual
coherence parameter μ also represents the robustness of the sampling matrix in CS.
The mutual coherence between two matrix and is defined as
μ( , ) =pN. maxk M,j N | < k, j > |. (2.15)
μ( , ) 2 [1,pN]. (2.16)
A Gaussian measurement matrix has shown to have these properties necessary for
the compressive sensing [32]
20
2.3.3 Compressive Sensing Reconstruction
The CS reconstruction is an under-determined system of linear equations. We have
M equations given by Y = X and N variables of X have to be reconstructed. Given
the RIP and incoherent property of sampling matrix is satisfied, a K − sparse,
N long signal can be reconstructed from M linear equations, where M < N. Let us
define, the pth norm of vector S as
||S||p :=
XN
i=1
|si|p
!1
P
. (2.17)
When p = 0, it gives the number of non-zeros entries in S. The CS reconstruction of
K − sparse signal X can be obtained from l0 minimization process. However, it is
computationally prohibitively complex.
The CS reconstruction approximation using least square solution is given by.
ˆ S = argmin||S||2, such that Y = S. (2.18)
The CS reconstruction approximation using l2 minimization is not a good approxi-mation.
Fortunately, l1 norm minimization process relaxes the l0 optimization and
gives approximate solution of the signal X as
ˆ S = argmin||S||1, such that Y = S. (2.19)
Figure 2.11: CS Reconstruction Geometry. (a) Sparse vector in R3. (b) l2 minimiza-tion.
(c) l1 minimization.
21
Fig. 2.11 shows the basic geometry of CS reconstruction using norm minimization
approach. Fig. 2.11 (b) shows pictorial representation of l2 minimization and why l2
minimization fails whereas from the Fig. 2.11 (c) we can see l1 minimization gives
a good approximation of sparse signal S. Details of CS geometry can be found in
[31, 30, 32].
Another class of CS reconstruction based on greedy pursuit such as Orthogonal
Matching Pursuit, CoSaMP, have been discussed in [33, 34, 35, 36]. Model based
compressive sensing decoding for special class of signals are discussed in [37, 38,
39]. There exists a tradeoff between different compressive sensing reconstruction
and decoding algorithm in terms of their complexity, error rate, and signal model.
However, we can list following important remarks about the compressive sensing
process.
• Stable : The CS acquisition and recovery process is numerically stable.
• Universal: The CS sampling matrix is adaptive and universal to the signal
models.
• Asymmetrical : Most of the processing is carried out at the decoder.
• Democratic : Each CS measurement carried equally important information.
2.4 Conclusion
In this chapter, we discussed about the spectrum scarcity and the cognitive radio
technique. We presented a brief introduction to various spectrum sensing techniques
and their tradeoffs. Spectrum sensing in cognitive radio for wideband network is
an expensive approach in terms of data sampling and acquisition cost. Compressive
sensing paradigm provides a new and efficient data acquisition and reconstruction
approach for certain class of compressible signals. In the next chapter, we will model
and discuss the application of compressive sensing in cognitive radio.
22
CHAPTER 3
WIDE BAND SPECTRUM SENSING FOR COGNITIVE RADIO
NETWORK USING DISTRIBUTED COMPRESSIVE SENSING
3.1 Introduction
The increasing demand for wireless resources and spectrum has created spectrum
scarcity. However, spectrum utilization studies show that these scarce wireless spec-trum
has been distributed and used inefficiently [40], [41]. This bottleneck in spec-trum
scarcity and inefficient usage is addressed by the dynamic spectrum access policy
[42, 43]. Cognitive radio (CR) with an ability to sense unused spectrum and oppor-tunistically
transmit over spectrum holes is proposed in [44], [6]. The fundamental
challenge in the cognitive radio implementation is detection of the vacant spectrum
(holes) [4].Various spectrum sensing and detection mechanisms such as an energy de-tector
[45], cyclo-stationary sensing [15] and pilot detection [46] have investigated the
spectrum sensing problem under different wireless environment. The current trends
in spectrum sensing and cognitive radios are well explained in many survey reports
[47], [11]. Many of the spectrum sensing algorithms deal with the narrow band sens-ing
which are tailored energy detector and power spectral density of the narrow band
signal. Wideband spectrum sensing requires fast and dynamic spectrum analysis
over larger spectrum band. Recent paradigm in sparse sampling, compressive sensing
(CS) [30], [32] provides solution to sparse signal reconstruction as an optimization
problem. In [48, 49], CS sampling, forward differentiation and singular value decom-position
methods are used for wideband spectrum sensing purpose. These approaches
provide wideband spectrum sensing in a simple individual network. To eliminate the
23
need of high speed analog to digital converters and digital signal processors in wide-band
sensing, techniques such as random demodulators, parallel signal processing are
proposed in [50, 51].
In this chapter, we build up basic compressive sensing model for the spectrum
sensing in cognitive radio network. This model is then extended to the frequency
overlapping jointly sparse networks in the Chapter 4. The rest of the chapter is
organized as follows: In the Section 3.2, we formulate the spectrum sensing problem
in single network for the cognitive radio. Section 3.3 presents the system model for our
problem statement. Proposed spectrum sensing for cognitive radio using compressive
sensing is discussed in the Section 3.4. Simulation results are presented in the Section
3.5 and finally Section 3.6, concludes the chapter.
3.2 Problem Definition
Let us consider a wideband communication model with primary and secondary (cog-nitive
radios) users coexistence as shown in the Fig. 3.1. The total communication
bandwidth of the system is divided into N subbands each centered at frequency fn,
where n = 1, 2, 3, . . . ,N. Very few of the N subbands are occupied by the primary
users at a given geographical and temporal region. Let us consider, out of N sub-bands,
S << N are occupied by primary users during sensing time. The unoccupied
channels by primary users over given spatia-temporal region called, spectrum holes,
are opportunistically accessed by the cognitive users keeping the rights of the pri-mary
safe. The cognitive radios in the system need to detect these spectrum holes
for secondary communication.
At time t, the received signal at mth cognitive user can be expressed as:
ym(t) =
XN
n=1
xn(t) gnm(t) + wm(t), (3.1)
where, represents the convolution, xn(t) is the signal of nth primary user, gnm(t)
24
Occupied Channels
Vacant Channels
1 2 3 N
Primary users
All other decvices are secondary users(Sensing device)
Figure 3.1: Primary and secondary users coexistence
denotes the channel gain response, and wm(t) is additive white gaussian noise with
zero mean and variance of 2w
. In frequency domain, (3.1) can be represented as:
y(m)
f =
XN
n=1
D(nm)
g x(n)
f + wm
f , (3.2)
where D(nm)
g is a diagonal N × N channel gain matrix between nth primary and
mth CR. xf and wf represent corresponding frequency response of x(t) and w(t),
respectively and elements g(nm)
f of D(nm)
g are given by:
g(i,j) = 0; i 6= j; and i, j 2 {1, 2, . . .N}, (3.3)
and, g(i,j) = gf(i,j); i = j; and i, j 2 {1, 2, . . .N}. (3.4)
However, we know that at any time t, only few of the N channels are occupied .
Let ˆ S be the set of occupied channels such that ˆ S ˆN
. ˆN
is the set of bands under
consideration. Thus for all n : n /2 ˆ S
xn(t) = 0. (3.5)
25
From (3.5), ˆN
is sparse. Accordingly, (3.1) and (3.2) reduce to,
ym(t) =
X
s2ˆ S
xs(t) gsm(t) + wm(t), (3.6)
and, y(m)
f =
X
s2 ˆ S
D(sm)
g x(s)
f + wm
f . (3.7)
This sparseness of signal in the frequency domain makes CS possible for the spec-trum
sensing purposes in cognitive radio network. The frequency response of the
channels occupied by the primary users are non-zero values, whereas, those of vacant
channels are zero. Hence, the total frequency response of the signal under consid-eration
is a sparse signal. In CS, instead of taking point by point samples as in
conventional sampling, each sample taken is linear functional of the sparse signal.
Consider the problem of reconstructing N × 1 length, S sparse signal X. Let us
consider an M × N dimension, where M < N, sensing matrix . We can obtain
M compressed measurements, Y , using, Y = X. Since, M < N, the recovery of
X from compressed measurements Y is ill-posed in general. Interestingly, provided
X is sparse in some domain and the measurement matrix satisfies the restricted
isometry property (RIP) [30], the signal X can be recovered from the measurement
vector Y . The recovery of S non-zero elements of signal X is actually the solution of
the l0 norm minimization problem.
ˆX
= arg min||X||l0, s.t. Y = X, (3.8)
Unfortunately, solving l0 is prohibitively computationally complex. However, the
approximate solution of X can be obtained using l1 minimization as:
ˆX
= arg min||X||l1, s.t. Y = X, (3.9)
For secondary communication in the cognitive radio network, finding the set ˆ S is
the most important and first requirement. The complexity of spectrum sensing de-pends
upon the requirements of an application. In cognitive radio spectrum sensing,
26
our primary concern is finding which of the S bands among N are occupied rather
than the exact signal strength of the the occupied channels. In cognitive radio net-work,
the problem of spectrum sensing using energy detector, at each mth CR boils
down to distinguishing between binomial hypotheses. The signal energy of each of
the subband is compared with the threshold e which is the function of noise and
channel characteristics. If the received signal is greater than e the channel is said
to be occupied else it is taken as vacant. Finding an optimal e is an agenda in the
communication channel modeling research [52].
In conventional spectrum sensing, each secondary user senses and detects each of
the band individually. This requires large number of measurements in the system and
increases data acquisition cost [11, 48]. Besides, each sensing device/cognitive radio1
needs to have sensing bandwidth entirely over the communication band making the
sensing process more prone to noise.
3.3 System Model
We have N channels to detect, and M compressive sensing measurements, where,
M << N. Out of N channels some of them are occupied by primary users (dark
blocks in Fig.3.2) and some of them are empty (white blocks in Fig.3.2). Let S
denotes the number of occupied channels and S << N. Hence in our system we
assume N >> M >> S. We refer to S/N as sparsity. The sensing devices in our
architecture can be seen as a unit having the combination of band-pass filters tapped
at different bands.
1The terms sensing device and cognitive radio have been used interchangeably in this work
27
Decode Compressed
Measurements
Compressed measurements
N Channels, S Occupied
Weighted sum of L random
channels
Controller
Figure 3.2: System Model
3.4 Proposed Compressive Spectrum Sensing
Let X = [xi]N×1 be the signal component test statistics of N channels. If we denote
the sensing matrix as M×N and Y = [yi]M×1 as the compressed measurements, then,
Y = × X. (3.10)
3.4.1 Generation of Sensing Matrix
In previous works [35, 30], the mathematical models of compressive sensing has been
explained thoroughly. From the implementation point of view, the physical realization
of sensing matrix is an important issue. The sensing matrix M×N in our model is
the element-wise combination of the two matrices: Frequency selective matrix FM×N
and channel response matrix HM×N. i.e
= F(.?)H, (3.11)
where, (.?) represents element wise product. We consider each of the Ms sensing
device/CR consists of ms filter banks where each filter bank is collection of random
28
bandpass filter tapped at L random bands. For simplicity , we assume the filters are
ideal with unity gain and zero phase. Hence, F is a binary matrix with constant row
weight L and it is characterized by the following expressions:
XN
n=1
Fm,n = L ;m = 1, 2, 3 . . .M, (3.12)
Also, if Lm denotes the the set of band index of the filters in the mth frequency
selective filter bank, then:
Fm,n = 1 ; if, n 2 Lm, (3.13)
else, Fm,n = 0. (3.14)
Similarly, the channel response matrix is defined by:
H = |hm,n|, (3.15)
m = {1, 2, . . .M} and n = {1, 2, . . .N},
where, |hm,n| is the channel response between mth sensing device and the nth primary
signal, and is function of the channel modeling. In our simulations, we model the
channel characteristics as the distance gradient model and assume we have complete
channel state information (CSI) [49]. From (3.11) and (3.13), we can have :
m,n = Fm,n × Hm,n ; ifFm,n = 1, (3.16)
else, m,n = 0. (3.17)
Hence, the sensing matrix is a constant row weight matrix.
3.4.2 Compressed Measurements
Each element of measurement vector Y is the weighted sum of L elements of X as
given by (3.18), where the ith element of Y , yi, is given by:
8i = 1, 2, 3, . . .M, yi =
X
i,j × xj , j = 1, 2, 3 . . .N, j 2 Li, (3.18)
29
where, i,j = 0, if Fi,j = 0, else, i,j = Fi,j×Gi,j , We know that the the Filter Matrix
is constant row weight matrix with row weight L and accordingly, is a also a constant
row weight matrix with row weight L. Hence, each compressed measurement is the
weighted sum of the L elements of X.
If we consider the transmission channel from sensing device to controller is noisy,
then the measurement Y is effected by noise as:
Y = × X +W, (3.19)
where, W is the additive gaussian noise of zero mean and variance 2w
.
3.4.3 Compressive Decoding
Compressive sensing (CS) decoding techniques based on optimization algorithms with
l1 minimization (Basis Pursuit) is discussed in [30, 32]. We implement Basis Pursuit
and Orthogonal Matching Pursuit in this problem to observe the performance in the
spectrum detection. CS decoding based on l1 minimization is as follows:
ˆX
= argmin||X||1, s.t. Y = X. (3.20)
In case of noisy measurements the constraint is modified as:
||Y − X||2 , (3.21)
where, is the noise energy. We also implement the compressive decoding technique
based upon the greedy pursuit called Orthogonal Matching Pursuit (OMP) [33, 34,
35]. A greedy algorithm computes the support of X iteratively. The steps in the
OMP can be summarized in following procedure.
Given: M × N measurement matrix , M, length compressed measurements Y
of N long vector X.
1. Normalize such that each column of , ( i) has unit norm. i.e || i||2 = 1.
30
2. Initialize residual: r0 = Y , Index set (Col), count, (t = 1) and empty set 0.
3. Find the index It that solves:
It = argmax| < rt−1, i > |, i = 1 : N.
4. Modify Index set and empty set Col(t) = Col(t−1) [ It and t = [ t−1 . . . t].
5. Solve least square problem to obtain signal estimate,
Xt = argmin|| tX − Y ||2. (3.22)
6. Calculate new residual,
rt = Y − tXt (3.23)
7. Increment count: t = t + 1 and go to step 3.
OMP is an iterative based method. At each step, the residual is modified and
new supports of the signal are determined. These steps are repeated until minimum
residual value threshold is met or up to predefined numbers of iteration. In our sim-ulations,
we implement l1 minimization (Basis Pursuit) and the orthogonal matching
pursuit for the spectrum detection. An improved version of l1 minimization termed as
weighted l1 minimization is developed in [53, 54]. In weighted l1, the weight to each
component of the signal vector is introduced. The use of weights is to counter influ-ence
the signal magnitude on the minimization function. The large weights are used
to discourage non-zero entries and vice versa. One of the possible weight functions
for this case may be the inverse function of the signal component. The re-weighted
l1 minimization scheme developed in [53] can be summarized as following.
1. Set the iteration count, l = 0 and weight, v0
i = 1; i = 1, 2 . . .N
2. Solve the l1 minimization problem,
xl = argmin||V (l)X||l1, Subject to : Y = X (3.24)
31
3. Update weights,
v(l+1)
i =
1
|xl
i| +
(3.25)
where, is small positive number slightly greater than the smallest sparse ele-ment
in X.
4. If iteration count l = maximum iteration, Terminate, else go to step 2.
The re-weighted l1 process improves the reconstruction performance. However, it
is an iterative l1 process, hence the performance gain is achieved at a cost of decoding
time. The l1 minimization process has to be repeated in every iteration for every
modified weight values. This accounts for the delay in reconstruction process and
spectrum detection.
3.5 Simulation and Results
For our experimental simulation we take N = 1000. We take measurements at differ-ent
rate from 10% to 40% of total signal length. The results provided are the average
of 10000 simulations under different signal strength values and different random mea-surement
matrices keeping sparsity (S/N) and other characteristics are same. We
consider two different simulation scenarios with sparsity 5 % and 10%. Moreover,
we observe the results in two different channels i.e. noiseless and noisy channels
with noise energy of 20 dB. Following parameters are defined for the performance
measurement.
• Sampling Rate (S.R = M
N %): Sampling rate is defined as the ratio of the
number of compressed measurements to the total number of channels. S.R is
represented in % as well.
• Probability Of Detection (POD): It is the ratio of total number of hits to
the sums of total hits and miss. Hit is an event when we decide the presence or
32
absence of primary user correctly, whereas, any other wrong decision is termed
as miss event. For an illustration let us consider, B and E denote busy and
empty state of channel respectively, and H and M denote Hits and Miss. The
following table shows an example of Hit and a Miss detection.
2
66664
B E B E
B B E E
H M M H
3
77775
• Error of Reconstruction (EOR): EOR is the ratio of energy difference be-tween
reconstructed and original signal to the energy of the original signal.
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
Sampling Rate
Probability of Detection
Primary Occupancy= 5%
Primary Occupancy=10%
Figure 3.3: Probability of Detection in Noiseless Measurements
Figs. 3.3 through 3.6 depict our simulation results for l1 minimization and OMP
method for different primary users occupancy rate. We can clearly see from our results
for the noiseless measurements that different decoding algorithms provide different
performance levels for our system. The POD using OMP for 5% primary occupancy
33
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0
0.2
0.4
0.6
0.8
1
1.2
Sampling Rate
Error of Reconstruction
Primary Occupancy= 10%
Primary Occupancy= 5%
Figure 3.4: Error Of Reconstruction in Noiseless Measurements
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0.8
0.85
0.9
0.95
Sampling Rate
Probability of Detection
Sparity=5%
Sparsity =10%
Figure 3.5: Probability of Detection in Noiseless Measurements using OMP
is about 0.95 at sampling rate of 40%. OMP is comparatively less efficient compared
to l1 minimization. l1 method has high POD increase rate as we increase the sampling
34
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0
0.2
0.4
0.6
0.8
1
1.2
Sampling Rate
Error of Reconstruction
Sparsity =10%
Sparity=5%
Figure 3.6: Error Of Reconstruction in Noiseless Measurements using OMP
rate. For sampling rate as low as 25%, we get POD close to 1. For a signal of 10%
occupancy, the number of measurements required for successful decoding increases
compared to that of 5% occupancy. Figs. 3.4 and 3.6 show the over all error in
energy of the reconstructed signal using l1 and OMP, respectively.
Figs. 3.7 and 3.8 shows the performance measurement comparison for noisy and
noiseless measurement in 10% primary occupancy, using l1 minimization method. We
can clearly see that POD and EOR deteriorates in noisy measurements but still more
than 90% of spectrum is detected with sampling rate as low as 40% and overall error
in energy is about 0.1
In Figs. 3.9 and 3.10, we clearly see that the reweighted l1 minimization improves
the performance in terms of both reconstruction detection probability and reconstruc-tion
energy error. The performance gain is achieved in reweighted scheme because in
each iteration, the higher value of weight suppresses the zero components and lower
value of weight estimates non zero components of the signal more closely to their
35
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0.6
0.7
0.8
0.9
1
Sampling Rate
Probability of Detection
Noiseless
Noisy
Figure 3.7: Probability of Detection in Noisy Measurements
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0
0.2
0.4
0.6
0.8
1
1.2
Sampling Rate
Error of Reconstruction
Noiseless
Noisy
Figure 3.8: Error of Reconstruction in Noisy Measurements
actual value. For this reason we choose the weight of each element to be the inverse
of its approximated value in each iteration. However, the reweighted l1 minimization
requires more computational complexity and decoding time because the minimization
36
process has to be repeated at every iteration for the modified weights.
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
Sampling Rate
Probability of Detection
l1 minimization
Reweight l1, 3 Iterations
Figure 3.9: Probability of Detection using Reweighted l1 Minimization
0.1 0.15 0.2 0.25 0.3 0.35 0.4
0
0.2
0.4
0.6
0.8
1
1.2
Sampling Rate
Error of Reconstruction
l1 minimization
Reweight l1, 3 Iterations
Figure 3.10: Error of Reconstruction using Reweighted l1 Minimization
37
3.6 Conclusion
In this chapter, we proposed a spectrum management architecture for cognitive ra-dios
using compressive sensing technique. We evaluated our scheme with different
simulations using different decoding algorithms and channel cases. The advantage
of our architecture is that, not only we reduce the total number of reports sent to
the controller using compressive sensing but also show that the Probability of De-tection
(POD) at the controller is improved. We also showed that our architecture
can also perform efficiently for spectrum sensing in noisy measurements by increasing
the sampling rate. Reweighted l1 scheme is used to improve the performance in the
spectrum sensing. In totality, the proposed architecture significantly enhances the
spectrum sensing for cognitive radio networks. This chapter also lays the foundation
for the concept of overlapping networks in the Chapter 4. The basic spectrum sens-ing
scenario presented in this chapter is extended into the system where more than
one network exists and networks overlap in their operating region in geo-spatial and
frequency domain.
38
CHAPTER 4
JOINT WIDE BAND SPECTRUM SENSING IN FREQUENCY
OVERLAPPING COGNITIVE RADIO NETWORK USING
DISTRIBUTED COMPRESSIVE SENSING
4.1 Introduction
The NTIA’s frequency allocation chart [55] shows many networks overlap in the fre-quency
zone because of spectrum scarcity. The spectrum overlapping or jointly sparse
frequency overlapping networks in cognitive radio network come into picture because
of spatial diversity of primary and secondary transmission power [56]. In conven-tional
spectrum sensing approaches, it is considered that all the CRs are silent and
synchronized during the sensing period. In large overlapping networks, or in spa-tially
distant CRs, synchronization cannot be guaranteed due to spatial diversity of
primary transmission power [56]. This creates jointly sparse frequency overlapping
networks over large spatial domain. In this chater, we extend our work in the Chapter
3 and propose joint reconstruction for wideband spectrum sensing in such frequency
overlapping networks using distributed compressive sensing. We extend our work in
wideband compressive sensing for cognitive radios [57] into a frequency overlapping
network and present joint reconstruction scheme for spectrum sensing in frequency
overlapping networks.
The rest of the chapter is structured as follows. In the Section 4.2, we introduce
the frequency overlapping network and formulate the spectrum sensing problem for it.
We propose joint compressive sensing scheme for jointly sparse frequency overlapping
cognitive radio networks. Individual reconstruction scheme and joint reconstruction
39
for the compressed measurement are presented and compared. Section 4.3 provides
simulation results for the proposed joint wideband spectrum sensing in frequency
overlapping networks and finally, Section 4.4 concludes the chapter.
4.2 Proposed Wideband Compressive Spectrum Sensing in Frequency
Overlapping Networks
The NTIA’s frequency allocation chart clearly shows the frequency overlapping over
different system protocols to meet the band scarcity issue. Let us consider two network
systems S1 and S2 with some overlapping operating bands as shown in Fig. 4.1. We
call the networks S1 and S2 as the frequency overlapping networks and denote it
with network HN. The theoretical backgrounds on joint sparse signal can be found
in literatures [58, 59]. Let Bs1 and Bs2 represent the spectrum band of S1 and S2
respectively, where |Bs1| = N1 and |Bs2| = N2. Bsc denotes the frequency overlapping
between S1 and S2 and |Bsc| = Nc. The total number of bands (channels) under
consideration is : NT = N1 + N2 − Nc. In jointly sparse frequency overlapping
networks, for each of the network, (3.7), takes the form of:
y(m)
if =
X
s2 ˆ Si
D(sm)
gi (x(s)
if + x(s)
cf ) + wm
f , (4.1)
where, i = 1, 2 refers to corresponding network, x(s)
if and x(s)
cf , denote the spec-tral
innovation of ith network and joint sparse portion, respectively, as illustrated in
the Fig. 4.1, and all other notations have same meaning as in (3.7). We consider,
each of the network consists of Ms sensing devices and each sensing device takes ms
compressed measurements. So total number of measurements taken in each network
= Ms × ms = M.
Let X1 = [x(1)
i ]N1×1 and X(2) = [x(2)
i ]N2×1 represent the test statistic for the spec-trum
sensing in two networks S1 and S2 respectively and X(c) = [x(c)
i ]Nc×1 represents
that of overlapping portion. A vector V of length N is said to be K sparse if V contains
40
Primary users
All other decvices are secondary users(Sensing device)
S1 S2 (Jointly Sparse)
Joint Sparse
Innovation
Overlapping Ban ds
Innovation
Sparse Innovation
Sparse Innovation
Bs1
Bsc
Bs2
Band 1
Band 2
Occupied Channels
Vacant Channels
Figure 4.1: Schematic of overlapping networks and overlapping spectrum bands
only K non-zero elements, i.e. kV kl0 = K, where, l0 denotes norm zero. Also, the
support of a vector, V = [vi]N×1 is defined as : supp(V ) = {i , vi 6= 0, i = 1, 2, . . .N}.
Let, |supp(X1)| = K1 and |supp(X2)| = K2. K1 and K2 denote number of occupied
channels in network 1 and 2, respectively. It should be noted that in spectrum sensing
for cognitive radios, our objective is to find the supp(X1) and supp(X2) and hence
detect primary users and find the spectrum holes.
In compressive sensing, it is the method of data acquisition which makes it distinct
from conventional sampling approaches. In the following subsections, we describe
the sampling approach, the structure of sparse sampling matrix , data acquisition
techniques and decoding approaches.
4.2.1 Sensing Matrix
In previous works [35, 30] the mathematical models of compressive sensing have been
explained thoroughly. From the implementation point of view the physical realization
of sampling matrix is an important issue. The sensing matrix M×N in our model is
the element-wise combination of the two matrices: random frequency selective matrix
41
FM×N and channel response matrix HM×N. i.e
= F(.?)H, (4.2)
where, (.?) represent element wise product. We consider each of the Ms sensing
device/CR consists of ms filter banks, where Ms × ms = M. Each filter bank is
collection of random bandpass filter tapped at L random bands. For simplicity, we
assume the filters are ideal filters with unity gain and zero phase. Hence, F is a
binary matrix with constant row weight L. Also, if Lm denotes the the set of band
index of the filters in the mth frequency selective filter bank, then:
Fm,n = 1 ; if, n 2 Lm, (4.3)
else, Fm,n = 0. (4.4)
Similarly, the channel response matrix is defined by:
H = hm,n, m = 1, 2, . . .M and n = 1, 2, . . .N, (4.5)
where, hm,n is the channel response between mth sensing device and the nth primary
signal, and is function of the channel modeling. From (4.2) and (4.3), we can have :
m,n = Fm,n × Hm,n ; ifFm,n = 1, (4.6)
else, m,n = 0. (4.7)
Hence, the sensing matrix is a constant row weight matrix.
4.2.2 Compressed Measurement Y
Let the sensing matrix for network systems S1 and S2 be represented by [ 1]M1×N1
and [ 2]M2×N2 respectively, with the characteristics as explained in Section 4.2.1.
For ease in calculation, we assume M = M1 = M2 and N1 = N2 = N. Each sensing
device samples the spectrum bands in the corresponding network system in S1 and S2.
42
Each sensing device gives ms compressed measurements and each network consists of
Ms sensing devices. For each system the total number of compressed measurements
sent to the individual controller unit is then M = Ms × ms. The ith compressive
measurement at mth sensing device is given by:
y(i)
m = (m,:) × X, (4.8)
i = 1, 2 . . .ms,m = 1 : number of sensing devices (Ms) Hence, Y1 and Y2, denoting
the compressed measurement at network system 1 and 2 respectively, can be written
as:
Yi = i × Xi; i = 1, 2. (4.9)
Similarly, in case of the noisy measurements, it is affected with additive white gaussian
noise of zero mean and variance 2, W(0, 2).
Yi = i × Xi +Wi; i = 1, 2. (4.10)
4.2.3 Compressive Sensing Decoding
The solution to the compressive sensing decoding is an optimization problem. CS
decoding algorithm based upon the norm optimization like Basis pursuit (l1) mini-mization
is discussed in [32, 30, 60].
In the followings, we first provide a quick reference to individual compressive
spectrum sensing and individual reconstruction, and then we illustrate the joint re-construction
scheme for the frequency overlapping networks.
Individual Reconstruction
In individual reconstruction scheme, each network reconstructs its compressively
sensed test statistics individually without cooperating with other networks and the
decision about the spectrum occupancy is made accordingly using thresholding [52].
43
The reconstructed test vector in individual reconstruction is give by:
ˆX
i = arg minkXikl1 s.t. Yi = iXi ; i = 1, 2, (4.11)
where as in case of the noisy measurements the optimization constraint is minimized
as:
kYi − iXik2 2, (4.12)
Joint Reconstruction
The number of required measurements for CS reconstruction is a function of the
sparsity of the signal. It has been shown that the number of samples required for the
CS reconstruction is in the order of CKlog
N
K
[30, 59]. In overlapping networks,
the individual reconstruction requires redundant numbers of samples for reconstruc-tion.
In individual reconstruction, the number of measurements required depends on
(K1 + K2). In [56], the LASSO algorithm with iterative user consensus is used to
detect the overlapped bands. However, the advantage of common sparse elements in
joint reconstruction is not exploited, and individual reconstruction is required in each
network. In joint reconstruction, the number of measurements required for recon-struction
depends on (K1 +K2 −Kc = KT ). It has been shown that the the number
of required measurements for CS reconstruction depends upon the sparsity, hence
the joint reconstruction will have the measurement gain. Moreover, only one joint
optimization is performed for the reconstruction of the both networks. We implement
joint reconstruction scheme for spectrum sensing in frequency overlapping networks
and compare it with the conventional individual reconstruction scheme and the itera-tive
LASSO consensus algorithm [56]. In joint reconstruction scheme, cognitive users
in each network take the compressed measurements of spectrum in their network.
The CS measurements are sent to a common controller unit. The schematic of joint
spectrum sensing and reconstruction in frequency overlapping network is shown in
the Fig. 4.2. The dark boxes represent the occupied channels whereas, white boxes
44
represent spectrum holes.
CS Measurements
Network 1
CS Measurements
Network 2
Joint Reconstruc!on
Network 1
Network 2
Figure 4.2: Joint spectrum sensing schematic in frequency overlapping networks
Let the measurements for the joint reconstruction be denoted by Y as,
Y =
2
64
Y1
Y2
3
75
, (4.13)
where, Y1 and Y2 are compressed measurements of networks S1 and S2, respectively.
Joint reconstruction matrix joint for reconstruction of the spectrum test statistics,
X :=
2
66664
Xi1
Xc
Xi2
3
77775
,
be represented as:
joint =
2
64
A C1 null
null C2 B
3
75
. (4.14)
If Ic denotes the set of the overlapping bands of two networks, ˆX
i1 and ˆX
i2 denote
innovation bands of network 1 and 2 respectively, and ( )j denotes the jth column of
45
the , then :
A = ( 1)j j 2 ˆX
i1,
B = ( 2)j j 2 ˆX
i2,
C1 = ( 1)j j 2 Ic,
C2 = ( 2)j j 2 Ic, (4.15)
and null are null matrices. Then the joint reconstruction optimization for X is
performed as:
ˆX
= arg minkXkl1 s.t. Y = joint × X. (4.16)
In case of noisy measurements the constraint of optimization is modified accordingly
as in (4.12).
4.3 Simulation and Results
For evaluating our performance we define following performance measurement pa-rameters.
Performance Measurement and Simulation Parameters
• Sampling Rate (S.R = 2M
NT
): Sampling rate is defined as the ratio of the
number of compressed measurements to the total number of channels.
• Probability Of Detection (POD): It is the ratio of total number of hits to
the sums of total hits and miss. Hit is an event when we decide the presence or
absence of primary user correctly, whereas, any other wrong decision is termed
as miss event.
• Error of Reconstruction (EOR): EOR is the ratio of energy difference be-tween
reconstructed and original signal to the energy of the original signal.
46
• Sparse Overlapping Factor (SOF = Kc
KT
): SOF is the ratio of number of
occupied channels in the overlapping bands to the total number of occupied
channels in the network.
• Measurement Gain (MG): For the given probability of detection, measure-ment
gain is defined as:
MG = 1 − # of measurements required in joint reconstruction
# of measurements required in individual reconstruction
For simulation purpose we take total number of channels, NT = 1000, out of
which, Nc = 30% are overlapping, the sparsity, (KT
NT
= 10%), and SOF = 0.5 unless
stated otherwise. Compressed measurements at different sampling rate are obtained
and reconstructed. The results provided are the average of 1000 simulations. Both
noisy and noiseless measurement schemes are simulated.
5 10 15 20 25 30 35 40 45 50
0.8
0.85
0.9
0.95
1
Sampling Rate
Probability of Detection
Individual
Joint
Figure 4.3: POD using individual and joint reconstruction
From Figs. 4.3 and 4.4, it is clearly observed that for the same number of com-pressed
measurements, the joint reconstruction algorithm has better performance
than the individual reconstruction. We see that the POD approaches 1 for joint
47
5 10 15 20 25 30 35 40 45 50
0
0.2
0.4
0.6
0.8
1
1.2
1.4
Sampling Rate
Error of Reconstruction
Joint
Individual
Figure 4.4: EOR using individual and joint reconstruction
reconstruction at sampling rate of 30% whereas it is at 44% for the individual recon-struction.
This gain in measurements is the consequence of sparse overlapping ele-ments
and joint reconstruction. The EOR for joint reconstruction approaches to zero
for the sampling rate of as low as 28% where as for that of individual reconstruction
it occurs at 40%. We see that for same performance the joint reconstruction requires
less number of samples. This reduces the data acquisition cost and the redundancies.
Figs. 4.5 and 4.6 are the performance measurement under noisy measurements.
48
5 10 15 20 25 30 35 40 45 50
0.8
0.85
0.9
0.95
1
Sampling Rate
Probability of Detection
Joint
Individual
Figure 4.5: POD using individual and joint reconstruction in noisy measurements
5 10 15 20 25 30 35 40 45 50
0
0.2
0.4
0.6
0.8
1
1.2
1.4
Sampling Rate
Error of Reconstruction
Joint
Individual
Figure 4.6: EOR using individual and joint reconstruction in noisy measurements
The performance under noisy measurements degrades both in terms of probability
of detection and reconstruction error, however the joint reconstruction scheme still
49
performs better than the individual reconstruction. Fig. 4.7 shows the effect of the
varying SOF on the measurement gain between the individual reconstruction and the
joint reconstruction. It shows the measurement gain for POD = 0.99.
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Sparse Overlapping Factor
Measurement Gain
Figure 4.7: Measurement gain for varying SOF when POD=0.99
We can clearly see that the measurement gain increases as the SOF increases.
This implies that the number of measurements required in joint reconstruction for
same performance decreases comparatively to individual reconstruction when there
are more occupied channels in the overlapping region.
In the Fig. 4.8 we present the performance of joint reconstruction scheme in terms
of probability of primary detection and false alarm rate. The Receiver Operating
Characteristic (ROC) curve for different SNR is presented. It is clearly seen that
the ROC have good performance for low false alarm rate and depends on the SNR.
We compare our performance with the iterative LASSO consensus scheme in [56]. In
[56], the frequency overlapping scheme is illustrated using multihop cognitive network.
Fig. 4.9 is the Receiver operating characteristics (ROC) comparison and Fig. 4.10
50
shows the comparison of reconstruction error. We clearly observe that the joint
reconstruction scheme has better receiver operating characteristics where as the error
of reconstruction is comparable to that of in iterative LASSO consensus.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.2
0.4
0.6
0.8
1
Probability of False Alarm
Probability of Primary Detection
SNR=−5dB
SNR=−10dB
SNR=−20dB
Sparsity=10%
Sampling rate = 30%
Figure 4.8: ROC performance for different SNR
51
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0.4
0.5
0.6
0.7
0.8
0.9
1
Probabilty of Flase Alarm
Probability of Primary Dectection
Joint reconstruction
LASSO consensus
Figure 4.9: ROC performance comparison, For SNR=-5dB, S.R=0.6 and Spar-sity=
40%
2 4 6 8 10 12 14 16 18 20
0.42
0.44
0.46
0.48
0.5
0.52
0.54
Number of Iterations
Error of Reconstruction
LASSO consensus
Joint reconstruction
Figure 4.10: EOR comparison, For SNR=-5dB, S.R=0.6 and Sparsity=40%
We also reconstruct the original time domain signal using individual and joint
52
reconstruction methods in Figs. 4.11 and 4.12, respectively, at sampling rate of 32%.
Comparing these figures, we observe that the signal reconstructed using the joint
reconstruction matches more closely to the original signal.
0 20 40 60 80 100
0
0.005
0.01
0.015
0.02
0.025
0.03
0.035
0.04
Time(t)
X(t)
Original
Individual Reconstructed
Figure 4.11: Original time domain signal and reconstructed using individual recon-struction
method
0 10 20 30 40 50 60 70 80 90 100
0
0.005
0.01
0.015
0.02
0.025
0.03
0.035
0.04
Time(t)
X(t)
Original
Jointly Reconstructed
Figure 4.12: Original time domain signal and reconstructed using joint reconstruction
method
4.4 Conclusion
In this chapter, we proposed a novel wide band spectrum sensing for cognitive ra-dios
in the frequency overlapping networks using distributed compressive sensing and
joint reconstruction. The concept have been demonstrated through the theoretical
explanation and have been validated using the simulation results. A distributed com-
53
pressive sensing for cognitive radio network in the frequency overlapping system has
been explored. Proposed joint reconstruction scheme for spectrum sensing exploits
the joint sparsity in frequency overlapping networks and efficiently reduces the number
of samples required. It is shown that the proposed scheme outperforms the individ-ual
reconstruction scheme and has better receiver operating characteristics compared
to LASSO consensus algorithm. This is because the overlapping channels can be
exploited to enhance the compressive decoding using joint reconstruction scheme.
54
CHAPTER 5
BINARY COMPRESSIVE SENSING
5.1 Introduction
The paradigm of sparse sampling and reconstruction, called Compressive Sensing (CS)
has been the state of art research in recent years. The gist of CS lies in determining
the sparse solution of an under-determined system of linear equations. The solution
of the under-determined system has been of particular research interest for a long
time. However, the CS [30, 31] approach opened up many new research spaces
in the field of under-determined system, ranging from theoretical formulations to
many practical applications in image processing, wireless communication, genetic
and molecular analysis, data-streaming, medical resonance imaging etc. Compressive
sensing provides solution for the under-determined system of a sparse source. A
vector, X 2 RN is said to be K sparse if X contains K non-zero elements, i.e.
||X||l0 = K, where, ||X||l0 denotes zero norm of X. For illustration, let us consider a
K sparse, N length source X be defined by M linear equations as in (5.1)
Y = X. (5.1)
In terms of compressive sensing, 2 RM×N, M << N is called sampling matrix
or measurement matrix and Y 2 RM is linear functionals of sparse source X and
is called compressed measurements. In general, the system in (5.1) is ill-posed, but
CS theory asserts that under the conditions, the source X is sparse and sampling
matrix satisfies the Restricted Isometry Property (RIP) [32, 61], the solution can
55
be obtained by the following optimization problem,
ˆX
= argmin||X||l0 : Y = X. (5.2)
Unfortunately, solving l0 is prohibitively computationally complex. However, the
approximate solution to (5.1) is obtained by following l1 minimization.
ˆX
= argmin||X||l1 : Y = X. (5.3)
Based on this general foundation, CS theory have been widely adopted and modified
according to the signal characteristics. Many works have been carried out in designing
the efficient sampling matrix , and decoding algorithms have been modified accord-ingly.
CS decoding algorithm based on matching pursuit [62] and greedy algorithm,
called Orthogonal Matching Pursuit and CoSaMP are developed in [33, 34, 36], re-spectively.
Designing of sampling matrix according to signal and application is also
of particular interest in CS. In [61], the RIP of random sampling matrices is proved.
Systematic random sampling matrix based on linear error correcting codes for com-pressive
sensing is designed in [63] and its RIP is proved. Similar sampling matrix
related to linear codes and orthogonal optical codes is introduced in [64]. Model based
compressive sensing for improved performance, and compressive sensing with prior
partial information are explained in [37, 38, 39].
In this chapter, we introduce a novel compressive sensing approach for special
class of signal with binary entries. We first design a sampling matrix for the binary
signal, and then we present two different decoding algorithms for the binary sparse
signal.
The rest of the chapter is organized as follows: In the Section 5.2, we formally
define the binary compressive sensing problem and provide a quick review on existing
works on binary compressive sensing and their pros and cons. In the Section 5.3,
we introduce our new binary sampling matrix and the binary compressive decod-ing
algorithm. Section 5.6 verifies our proposed scheme with numerical simulations
56
and comparison with the existing methods, and finally the Section 5.7 concludes the
chapter.
5.2 Related Work and Contribution
In this chapter, we deal with the special class of the under-determined system in (5.1).
Instead of considering the real valued signal, we have the prior information that the
source signal X is binary. The system is thus redefined as:
Y = X. (5.4)
where, X 2 BN and B = {0, 1}. Binary sparse signal can come into account in
many practical applications such as event detection in wireless sensor networks, group
testing, spectrum hole detection for cognitive radios etc [65, 66]. Linear programming
based solution to (5.4) have already been proposed and discussed. In [67], the author
modified the solution (5.3) for the binary system in (5.4) accordingly as in (5.5). The
author has also provided the recovery threshold for l1 reconstruction of the binary
signal.
ˆX
= argmin||X||l1 (5.5)
subject to Y = X,
0 xi 1, 1 i N.
In [68], the authors have developed reconstruction algorithm for binary sparse signal
using lq norm, where, 0 q 1, which is based upon the re-weighted l1 minimization
algorithm developed in [69]. Though these methods improve the performance for the
binary sparse signal, the reconstructed signal ˆxi 2 [0, 1], i = 1, 2, 3 . . .N, whereas,
the original xi 2 {0, 1}, i = 1, 2, 3 . . .N. The mapping function for ˆxi 2 [0, 1] to
the xi 2 {0, 1} is also undetermined. So, these solutions are not able to exactly
reconstruct the original signal in X 2 BN. In a very recent work [70], the authors
57
employ integer programming model to solve the the under-determined binary sys-tems
of linear equations. The work is basically the solution for the general binary
systems of equations. In compressive sensing, we have an added advantage of having
control over the sampling matrix , the elements of which are the coefficients of the
linear equations. Implementation of bipartite graphs has also been interesting topic
in CS. In [71], a mixed algorithm using two phase of encoding and reconstruction is
proposed for CS using graph and matrix inversion. In [72, 73], the authors proposed
use of bipartite graphs to represent the CS and have explained the rate distortion
performance of binary CS based upon the edge evolution in low density parity check
codes [74]. The authors have provided an interesting closed form solution for edge
evolution using large deviation probability theory and the martingales [75]. However,
the edge evolution process halts after some iterations and thus the reconstruction so-lution
is incomplete. In this chapter, we first design a unique but universal sampling
matrix for binary signal, suitable for graph based recovery. We then propose two
recovery algorithms each of them having trade-offs in terms of computation and phys-ical
resource. We also provide analysis of our scheme and discuss the measurements
required, error floor, and complexity and verify our scheme using both numerical
analysis and simulations.
5.3 Binary Compressive Sensing
Let us represent the binary compressive sensing system in (5.4) by the bipartite
graph as in the Fig. 5.1. The elements of the binary sparse signal X is represented by
the circular nodes and the compressive sensing measurements, i.e. elements of Y are
represented by the square nodes and are termed as Variable nodes (V −nodes) and the
Check nodes (C − nodes), respectively as shown in the Fig. (5.1). The ith V − node
and jth C − node are represented by vi and cj and their corresponding values are
represented by xi and yj , respectively. The edge Eij between vi and cj , represents
58
6
X
1 2 3 4 15
Y
1 2
Zero C -Node Light C -Node Par!al C -Node Heavy C -Node
"11
"16
"18
"64 "612
"615
Figure 5.1: Representation of Compressive Sensing with Bipartite Graph
the jth row and ith column element of sampling matrix, ( )ji. The filled V-nodes
represent xi = 1, xi 2 X and the empty V-nodes represent xi = 0, xi 2 X. Similarly,
the C − nodes are divided into 4 different types as shown in the Fig.(5.1). We will
discuss about these check nodes in the next section later. A V − node, vi is said to
be neighbor of C − node, cj , if, 9,Eji, i.e. ( )ji 6= 0. In previous binary compressive
sensing works using bipartite graph [72, 73], the sampling matrix is constant row
weight binary matrix with row weight L. So in these approaches, the compressed
measurements (C-nodes), yi 2 Y can be grouped in three groups, yi = 0 or yi = L
and rest all in one group.
Clearly, for decoding purpose,
8, vk 2 cm, xk = 0, if, ym = 0, (5.6)
xk = 1, if, ym = L,
xk = unknown.
This phase of recovering V −nodes associated with C −nodes with values yi = 0 and
yi = L is termed as First Phase Recovery (FPR). After the first phase recovery,the
edge recovery is performed by corresponding edge removal process. (For details in
edge recovery please refer to [72, 73, 74]. But this approach has two major setbacks.
59
First, the edge recovery process does not recover all the V −nodes and the second, the
work does not provides any explanation about the effect of row-weight L on overall
recovery of the C − nodes. In the following section, we first design the sampling
matrix and then discuss the consequence of row weight L on the FPR.
5.3.1 The Sampling Matrix,
Let us consider, the M × N dimension sampling matrix of row weight L. Each
row of contains L non-zero elements placed randomly. Let
i denotes the set of
non-zero elements in ith row and
i1 and
i2 are any two subsets :
i1 ,
i2
i
and
i1 6=
i2 i = 1, 2, . . .M. Let, denotes the elements in
i, then, the following
condition should be satisfied:
X
j2
i1
j 6=
X
j2
i2
j . (5.7)
In other words, all the possible sums of non-zero row elements of are unique. For a
finite constant row-weight L, when the row-elements of are sampled from continuous
random distributions such as Gaussian or Uniform, (5.7) is easily satisfied. Hence,
the ith, i = 1, 1.. . . .M, row of sampling matrix is given by following steps:
i = fr(i, L), i = fp(i, L,N), (5.8)
For, k=1,2,. . .N
i,k =
i; k 2 i,
else, i,k = 0. (5.9)
fr(i, L) is a function that generates L random numbers from Gaussian or Uniform
distribution, the function, fp(i, L,N) generates L random positions from 1 to N, and
i is the set of non-zero locations of the ith row of . Hence, the sampling matrix in
our method is sparse constant row weight matrix whose non-zero elements are drawn
from the Gaussian or uniform distribution and each row of satisfies (5.7).
60
5.3.2 Compressed Measurements and the Check Nodes
The compressed measurements (C − nodes) are the linear, scaled sums of the L
random V − nodes as represented by (5.4) and the Fig.(5.1). The C − nodes are
divided into 4 groups as followings:
Definition 1: A C − node, cj is said to be Zero C − node, if yj = 0. This happens
when all the neighbor v0
is of cj are zero elements. c1, c2 are examples of Zero C−nodes
in the Fig.(5.1).
Definition 2: A C − node, cj is said to be Light C − node, if, yj = ( )j,k, where,
k 2 j . In other words, a C − node, cj is said to Light C − node, if, yj is equal to
any one non-zero element of jth row of . This happens, when one of the neighbor
v0
is of cj is one and all other are zeros. c3, c4 are examples of Light C − nodes in the
Fig. (5.1).
Definition 3: c5 is an example of Partial C − node. A C − node, cj is said to be
Partial C − node, if, yj 6= 0 6= ( )j,k ; k 2 j but, during edge recovery process, the
node ultimately turns to be either Zero C − node or Light C − node.
Definition 4: c6 is an example of Heavy C − node. A Heavy C − node, cj occurs
when for all the V −nodes, v0
is which are neighbors of cj , there exists more than one
vi which is neighbor of only cj and is not recovered by edge removal process.
5.3.3 Compressive Sensing Decoding
The node recovery or decoding is divided into two phases.
First Phase Recovery
In the First Phase Recovery (FPR), the V − nodes which are neighbors of Zero
C − nodes and Light C − nodes are recovered. Let, j is set of neighbors vi’s of
C−node, cj . The V −nodes which are neighbors of Zero C−nodes or Light C−nodes
61
is recovered as follows:
if, cj is Zero C − node i.e. yj = 0,
xi = 0; 8 vi 2 j (5.10)
elseif, cj is Light C − node , i.e. cj = ( )jk, k 2 j
xk = 1, vk 2 j
xi = 0, 8vi 2 j , i 6= k. (5.11)
Edge Removal, Check Nodes Update and Iteration
After, the variable nodes are recovered from Zero and Light C −nodes, edges associ-ated
with the corresponding V −nodes are removed from the graph, and subsequently
the C − nodes are updated.
8cj , cj is Zero or Light C − node,
8vi 2 j ,
Remove Eji,
Remove Eqi, where, q 6= j, q = 1, 2 . . .M
if, xi = 0,
yq = yq. (5.12)
elseif, xi = 1,
yq = yq − qi. (5.13)
After, edge removal and check nodes update process, new Zero C − nodes and Light
C − nodes will be created. Then the FPR process and the edge removal and check
nodes update process is repeated until the generation of new new Zero C − nodes
and Light C − nodes stops. The process of FPR and edge removal and check nodes
update for the Fig.5.1 is illustrated graphically below.
62
For the graph in the Fig.5.1:
Zero C − node : c1: 1 = {1, 6, 8}, 1 = {v1, v6, v8}
y1 = 0, ! x1 = x6 = x8 = 0.
Edge Removal: Remove: E1,1, E1,6, E1,8
Remove: E4,6
Check Nodes Update: x6 = 0, ! y4 = y4
Similar process is carried out for all Zero C − nodes.
For Light C − node : c3 : 3 = {3, 5, 12}, 3 = {v3, v5, v12}
y3 = 3,3, ! x3 = 1, x5 = x12 = 0.
Edge Removal: Remove: E3,3, E3,5, E3,12
Remove: E6,12
Check Nodes Update: x12 = 0, ! y6 = y6
Similarly,
For Light C − node : c4 : 4 = {6, 9, 11}, 4 = {v6, v9, v11}
y4 = 4,9, ! x9 = 1, x6 = x11 = 0.
Edge Removal: Remove: E4,6, E4,9, E4,11
Remove: E5,9
Check Nodes Update: x9 = 1, ! y5 = y5 − 5,9
At this point, it should be noted that, the Partial C −node, c5, has changed to Light
C−node. The reduced graph after these steps is shown in the Fig.5.2. The process of
edge removal, check nodes update and Zero and Light C−nodes recovery is continued
as long as there exist single Zero or Light C − node. However, all V − nodes cannot
be recovered by these process. The V −nodes which are neighbor of Heavy C−nodes
(e.g. c6) have to be yet recovered. These nodes are recovered by following method.
63
15
6
X
1 2 3 4
5
!64
!615
!513
Figure 5.2: Reduced Graph after the First cycle of First Phase Recovery and Edge
Removal and Check Nodes Update
Check Sum Method for Heavy C − nodes
In the Section 5.3.1, we discussed about the non-zero elements of the sampling matrix
. The condition for non-zero row elements of in (5.7) guarantees that any combi-natorial
sum of these elements is unique. We use this property the sampling matrix
designed in the Section (5.3.1) to recover the Heavy nodes and V − nodes, which are
neighbors of Heavy nodes. The Check Sum method is described by following steps.
Algorithm 1 Check Sum Method for Heavy Nodes Recovery
1. 8, Heavy C − nodes, cj ,
2. Find: Updated j and j
3. Find: The numbers of elements in j , i.e. |j | =
4. Create: Vector, V = j,k, 8k 2 j .
5. Create: Binary Matrix (BT) 0 to 2 − 1,
where, each row of table is corresponding binary representation of 0 to 2 − 1 .
6. Compute: Check-Sum (SUM): SUM = BT × V 0
7. Find: yj = SUM(l)
8. Assign: 8, vi 2 j , Assign element wise lth row of BT to vi 2 j
To illustrate this process for the Fig.5.1, we can see from the Fig:5.2 that the c6
is Heavy Check − node. Following the steps described above.
For Heavy Check − node, c6,
64
Updated: 6 = {4, 15}, 6 = {v4, v15} and = 2.
V = [ 6,4 6,15], Binary Table: B.T =
0
BBBBBBB@
0 0
0 1
1 0
1 1
1
CCCCCCCA
SUM = [0 6,4 6,15 ( 6,4 + 6,15)]0
Clearly, y6 = SUM(4) ! j (BT)4.
Hence, x4 = 1 and x15 = 1.
In the following section, we present an alternative method of Binary CS based
only on the Check Sum.
5.4 An Alternative Approach
In this approach we modify the sampling matrix . The function fr(i, L) is made
independent of the row.
i.e.
1 =
2 = ...
M = fr(L) =
. (5.14)
This suggests that the all the rows in sampling matrix contains same non zero
elements from
. Then, the sampling matrix is generated as:
For, k = 1, 2, . . .N
i,k =
; k 2 i
else, i,k = 0 (5.15)
All notations and functions have same meaning as described in the Section 5.3.1
unless stated otherwise and
also satisfies the condition in (5.7).
65
5.4.1 Compressive Sensing Decoding
In this approach, the decoding center has a vector (SUM) stored. A SUM vector is
generated by following steps.
Create: Binary Matrix (BT) 0 to 2 L − 1,
Compute: Check-Sum (SUM): SUM = BT ×
0
It should be noted that the SUM vector is all possible combinatorial sum of elements
in
. Hence, the check nodes and their corresponding variable nodes are decoded by
following algorithm.
Algorithm 2 An Alternative Method
1. 8, C − nodes, cj ,
2. Find: yj = SUM(l)
3. Find: Vector, lbinary = fB(l − 1, L). where, fB(l − 1, L) is a function that gives
L bit binary representation of l − 1 with least significant bit at right and left bits
padded with zero whenever necessary.
4. Assign: 8, vi 2 j , xi = lbinary(k), k = 1 : L
5.5 Analysis and Discussion
The graph and check sum based compressive sensing for binary sparse signals is ben-eficial
than the solution based on the l1 minimization approaches. In this section, we
discuss the consequences of row weight L in performance, the encoding and decoding
complexities, the measurement constraints and error probability of our scheme.
5.5.1 Choice of Row-Weight (L)
In our scheme, the first phase of recovery is based on the number of Zero and Light
C −nodes. The number of Zero and Light C −nodes is a function of the row-weight
L and the sparsity S of the binary sparse signal. The sparsity (S) of signal X, with
66
|X| = N, is defined as, S K/N, where K is the number of non zero elements in
X. The recovery of Zero and Light C − nodes is crucial in our scheme for two broad
purposes. Recovery of Zero and Light C−nodes requires only search operation and is
faster than recovering Heavy C −nodes. Moreover, the edge recovery and check node
update process during first phase recovery reduces the edges of Partial and Heavy
C − nodes as illustrated in the Fig.5.2. The edge reduction decreases the size of j
and . Smaller is the , lesser is the computations in the Check Sum method.
Let us consider, P0 and P1 denote the probability that the check node is Zero −
node and Light − node respectively. Then, P0 is the probability the check node has
all zero neighbors and P1 is the probability that the check node has only one non-zero
(xi = 1) neighbor and all other are zero neighbors. P0 and P1 are given by:
P0 = (1 − S)L. (5.16)
P1 = (1 − S)L−1 · S ·
L
1
. (5.17)
It is clear that to maximize Zero−nodes and Light−nodes we need to maximize
P0 and P1. Let, FP = P0 + P1. Then,
FP =P0 + P1 (5.18)
d(FP )
dL
=
d(P0 + P1)
dL
(5.19)
=(1 − S)L · ln(1 − S) + (1 − S)L−1 · S + L ˙S
· (1 − S)L−1 · ln(1 − S). (5.20)
To maximize FP we equate (5.20) to 0 and approximating −ln(1 − S) S, we get
L=1. From (5.16) we see that for L = 0, P0 = 1. However, taking row-weight
L = 0 or 1 do not make any sense in compressive sensing because, when L = 0
we are not taking any samples and when L = 1 we are taking only one sample in
each measurement, it means in each measurement, we either sample only 0 or only 1.
This violates the basic norm of compressive measurement that each measurement in
compressive sensing is linear functionals of numbers of samples. So, taking L = 0 or 1
67
is not feasible in compressive sensing. To illustrate this, in the Fig. 5.3 we show P0, P1
and FP for S = 0.1 and varying L. Hence, it is desirable to maximize Light−nodes.
0 2 4 6 8 10 12 14 16 18 20
0
0.2
0.4
0.6
0.8
1
Row Weight (L)
Probability
P
0
+P
1
P
1
P
0
Figure 5.3: Probability of zero and light check nodes for different row-weight
Maximizing Light C − nodes has mainly two advantages:
• Light C-nodes reduce the edges of check nodes and makes the graph less denser.
• Light C-nodes after each iteration create new Light C-nodes. Every C-nodes
which has two non-zero neighbors and one of the non-zero neighbors belongs to
Light C-node turns into new Light C-node after edge removal and check node
update process.
Theorem 1 The optimal row weight L for the maximum Light C − node is (1/S).
Proof. Let, P1 denote probability of C − node being Light C − node.
P1 = (1 − S)L−1 · S ·
L
1
(5.21)
68
d
dL
(P1) = 0,
(1 − S)L−1 · S + L · S · (1 − S)L−1 · ln(1 − S) = 0,
L · ln(1 − S) = −1.
Expanding, −ln(1 − S) = S + S2
2 + S3
3 + . . . and for small S, −ln(1 − S) S
L (1/S) . (5.22)
5.5.2 Encoding and Decoding Complexity
For encoding purposes in both, first approach and the alternative approach, each
measurement requires L, measurements. We make M measurements. Hence, the
encoding requires O(ML) complexity.
The decoding complexity in the first approach depends upon the number of Heavy
nodes and the of the reduced graph. To decode Zero and Light C −nodes we need
just one search operation. However, for each Heavy C − node, we need one matrix
multiplication and a search operation. For this reason, it is very important to Zero
and Light C−nodes first and reduce the graph by edge removal and check node update
process. However, in an alternative approach, at the cost of physical memory to store
check-sum vector (SUM), the decoding complexity is greatly reduced. In alternative
approach, to decode each C − node, we need only one search operation. Both of our
decoding schemes are faster than the general compressive sensing decoding schemes
for binary sparse signal in [67, 68] as shown in the Fig.5.11.
5.5.3 The Number of Measurements (M)
In our scheme, for successful decoding of all C−nodes and hence recover all V −nodes,
two conditions have to be satisfied.
69
1. The non-zero elements of sampling matrix should satisfy (5.7).
2. Each of the V −node should be the neighbor of at least one C −node, i.e. Each
of the variable node should be sampled at least once.
Theorem 2 For successful decoding of binary sparse source from compressed mea-surement
using graph and sum based decoding algorithm, the number of measurements
M is of O(Klog(N)).
Proof. For a bipartite graph with N, V − nodes and M, C − nodes with L C − node
degree, we need M×L of order Nlog(N) for all V −nodes to be sampled in the graph
[76].
Hence, M = O
N
L
logN
We have, L = O(1/S)
M = O(KlogN)
Lemma 1 The encoding requires the computational complexity of O(ML) = O(NlogN)
5.5.4 The Error Rate (E.R)
Let the error rate of the graph and sum based compressive sensing algorithm for
binary sparse signals be defined as the ratio of numbers unrecovered variable nodes
to the total number of variable nodes. Provided, (5.7) is satisfied, in our scheme, the
variable nodes cannot be recovered only when it is not sampled in the check nodes
(compressed measurements).
Theorem 3 Error rate (E.R) of Graph and Sum based scheme is given by: E.R =
1 − L
N
M
70
Proof. The probability that a variable node is sampled in one measurement =
L
N
The probability that a variable node is not sampled in one measurement =
1 − L
N
The probability that a variable node is not sampled in M measurements =
1 − L
N
M
The probability that a variable node is sampled inM measurements =
h
1 −
1 − L
N
M
i
) For large N, average numbers of variable nodes sampled = N ×
h
1 −
1 − L
N
M
i
We have, E.R =
N − N
h
1 −
1 − L
N
M
i
N
) E.R =
1 −
L
N
M
(5.23)
5.6 Simulation and Results
For simulation purpose, following values are considered unless stated otherwise. We
take the number of variable nodes N = 1000, the sparsity of the binary source S = 0.1
In edge recovery, the number of check nodes recovered in the first phase is very
important factor. More the numbers of C −nodes recovered in first phase, easier and
quicker is the overall recovery scheme. The more numbers of C − nodes recovered in
first phase phase has following advantages.
• The number of edges removed in each iteration increases with number of check
nodes recovered in the iteration. The number of edges removed in each iteration
is given by the numbers of C − nodes recovered × C − node degree.
• It makes the overall V ariable Nodes recovery process faster as the bipartite
graph becomes less dense.
• Only few numbers of C−nodes will be remained for decoding using Check-Sum
method.
71
In the Figs. 5.4 and 5.5 we compare the first iteration recovery of C − nodes in
our scheme with that of in Binary Tree scheme in [72, 73].
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
10−6
10−4
10−2
100
Sparsity
CNRP
L=20, Binary Tree
L=20, Our Scheme
L=10, Binary Tree
L=10, Our Scheme
L=5, Binary Tree
L=5, Our Scheme
Figure 5.4: Probability of Check Nodes Recovered in First Iteration (CNRP)
Fig. 5.4 shows the probability of check nodes recovered (CNRP) in first iteration
for different sparsity and different row weight (L). We can clearly see that at each L
and sparsity the CNRP is greater than that of in Binary Tree scheme. It also shows
that for the given L, the CNRP decreases as the sparsity increases. So it is necessary
to decrease the row weight in high sparsity signal to increase the CNRP. However,
in all instances the CNRP in our scheme is greater than that of in the Binary Tree
scheme.
To address the low CNRP for large sparsity is desirable to take the row weight
L of the sampling matrix of the order O
1
S
as discussed in 5.5.1. In the Fig. 5.5,
we show the number of check nodes recovered in first iteration for different sparsity.
The row weight L is taken to be 1
S and the number of measurements (C-nodes) (M)
is taken as 300.
72
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55
0
50
100
150
200
250
300
Sparsity
CNRN
Binary Tree
Our Scheme
(L = 1/S), (M=300)
Figure 5.5: Numbers of Check Nodes Recovered in First Iteration (CNRN)
From the Fig. 5.5 we can clearly see that in our scheme, out of 300 C − Nodes,
about 225 are recovered in the first iteration itself whereas in Binary Tree scheme the
number is as low as 100.
In our scheme, it is necessary that all the V − nodes be neighbor of at least one
C −node. Whenever, a V −node is not a neighbor of any C −nodes, that particular
V −nodes remains unrecovered and increases the Error Rate. In the Fig. 5.6, we can
clearly see that for the given number of measurements, the Error Rate decreases as
the row weight increases. However, this increases in performance is achieved by some
cost in decoding time as shown in the Fig. 5.7.
73
5 10 15 20 25 30
0
0.05
0.1
0.15
0.2
0.25
Row Weight (L)
Error Rate (E.R)
M=300
Figure 5.6: Error Rate for different Row Weight
5 10 15 20 25 30
0
0.05
0.1
0.15
0.2
0.25
Row Weight (L)
Decode Time (Sec)
M=300
Figure 5.7: Row weight and Decode Time
Fig. 5.8 shows the performance of our scheme for various row weight and sampling
rate. It is clearly seen that the Error Rate decreases as the sampling rate increases.
74
We can also see that for the same sampling rate, the error rate decreases as the row
weight is increased.
15 20 25 30 35
10−5
10−4
10−3
10−2
10−1
Sampling Rate (%)
Error Rate
Simulated, L=20
Calculated, L=20
Calculated, L=25
Simulated, L=25
Calculated, L=30
Simulated, L=30
Figure 5.8: Error Rate for different Sampling Rate and Row weight
We can clearly see from the Fig. 5.8 that the simulated error rate is very close to
the error rate calculated in the section 5.5.4. Hence, our calculated error rate (5.23)
expression is validated through the experimental results as well.
In [67] and [68], the general l1 minimization method is modified for the Binaray
signal source. A new reconstruction constraint is used to bound the reconstruted
signal values within, 0 ˆx 1, in [67]. A similar approach is used in [68] where
the optimization is iterated using the weight factor. These methods perform com-paratively
better than general l1 method for binary signal. However, in both of
these schemes, the reconstructed binary signal values lie in the continious range of
0 ˆx 1 instead of giving discreet values 0 or 1. In the Fig. 5.9the original binary
singal and reconstructed signal using the l1 binary and our scheme is shown. In the
Fig. 5.9, (A) is the original Binary signal, (B) is the reconstructed signal using l1
75
binary method and (C) is reconstructed signal using our scheme.
0 50 100 150 200 250
0
0.5
1
Index
X (Original)
(A)
0 50 100 150 200 250
0
0.5
1
Index
X (Reconstructed)
(B)
0 50 100 150 200 250
0
0.5
1
Index
X (Reconstructed)
(C)
L=20, S=0.1, SR=0.2
L=20, S=0.1, SR=0.2
Figure 5.9: Original and Reconstructed Signal using Binary l1 and Our Scheme
For a better pictorial representation of the original and reconstructed signal in
the Fig. 5.9, the simulation has been carried out for the binary signal of length
(N = 250), Sparsity (S = 0.1) Row-weight (L = 20) and Sampling Rate (S.R = 0.2).
We can clearly see that the scheme has better reconstruction that the l1 binary scheme.
Besides, the reconstructed signal using l1 Binary method is continuously distributed
over 0 ˆx 1.
In Binary l1 scheme, the reconstructed signal values are in the range of 0 ˆx 1.
We modify this scheme slightly. We put the threshold 0.5 to make a decision if the
reconstructed spike is 0 or 1. Fig. 5.10 shows the error rate comparison of our scheme
and the Binary l1 scheme with threshold.
76
15 20 25 30 35
10−5
10−4
10−3
10−2
10−1
Sampling Rate (%)
Error Rate (E.R)
Our scheme, L=20
Our Scheme, L=25
Our Scheme, L=30
Binary l1, L=20
Binary l1, L=25
Binary l1, L=30
Figure 5.10: Error Rate Comparison with Binary l1 scheme with threshold
5 10 15 20 25 30
0
0.5
1
1.5
2
2.5
3
3.5
4
Row Weight
Decode Time (Sec)
Our Scheme
Binary l1
Figure 5.11: Decode Time comparision Binary l1 scheme with threshold
We can clearly see that for row weight of 30 at low sampling rate of 25%, the
error rate of our scheme is in the order of 10−4 whereas, the error rate in binary
77
l1 method is in the order of 10−2. At very low sampling rate our scheme has very
good performance rate compared to the binary l1 scheme. When the sampling rate
is increased binary l1 has slightly better performance than our scheme, however, the
error rate in both schemes are in the same order. It should be noted that the error
rate in our scheme is solely because of the un-covered V −nodes. Moreover, Fig. 5.11
shows that our schemes takes comparatively very less time for decoding and small
gain in error rate performance is achieved at very high cost of decode time in binary
l1 method.
In the Section 5.3.3, we discussed about the check-sum method and heave nodes
degree . Large values of , makes the check sum method computationally complex.
However, the iterative edge-recovery and check nodes update process make the heavy
nodes degree very small. In the Fig.5.12 we show the maximum beta occurrence rate
for S = 0.1, L = 30 and M = 300. The result provided is an average of 10,000
experiments.
2 3 4 5 6 7 8 9
0
0.05
0.1
0.15
0.2
0.25
b
Occurence Rate
Figure 5.12: Maximum heavy node degree
78
We can clearly see the distribution of maximum peaks around 3−5. This shows
that the iterative edge removal and check nodes update process effectively reduces
the heavy check nodes degree and makes check-sum method simple and feasible.
5.7 Conclusion
In this chapter, we presented a novel compressive sampling and decoding method for
Binary Sparse Signal using Graph and Check-Sum method. We modeled the binary
compressive sensing method as the Bipartite graph and implemented the edge recovery
scheme. Edge recovery scheme in itself cannot guarantee the complete decoding. To
overcome this drawback, we designed a unique sampling matrix for the binary sparse
source. We showed that consequences of row weight of sampling matrix in edge
recovery as well as overall recovery performance. We also formulated the error rate
of our scheme for a given row weight and number of measurements. We compared
our scheme with Binary tree recovery method and Binary l1 method. Binary sparse
source is found in many real life applications. For instance, in event detection scheme
in wireless sensor network, in spectrum occupancy decision and binary images, the
source can be modeled as the binary signal. In these applications, our scheme can
find appropriate applications.
79
CHAPTER 6
CONCLUSIONS AND FUTURE WORKS
In this thesis, we have proposed compressive sensing based spectrum sensing for wide-band
cognitive radio networks. In wideband cognitive radio networks conventional
spectrum sensing is less feasible because of the data sampling and acquisition cost.
A new paradigm in data sampling and acquisition, called compressive sensing is an
effective approach for wideband data sampling. Compressive sensing possess an abil-ity
to reconstruct the certain class of compressible original signal from fewer numbers
of samples than conventional point-to-point data sampling schemes. Unlike in tra-ditional
data compression, compressive sensing not only compresses sampled data,
the compression process in itself is embedded in the sampling process. In this light,
compressive sensing, in one hand reduces the number of samples and in the other
hand it also relaxes the number of sensors and sensing points in the sampling process
itself. These features make compressive sensing very feasible and attractive for data
acquisition and sampling purposes.
In the Chapter 2, we briefly discussed about the spectrum scarcity and evolution
of cognitive radio technique to address spectrum scarcity problem. Various challenges
in implementation of cognitive radio such as power constraints, and spectrum sensing
is briefly discussed. A brief introduction to spectrum sensing approaches and com-pressive
sensing is discussed. In the chapter 3, we proposed compressive sensing based
spectrum sensing for single network cognitive radio system. Proposed wideband com-pressive
sensing based spectrum sensing method has good performance in terms of
both detection probability and error in energy of reconstruction. We also investigated
80
various compressive sensing algorithms and their performance in spectrum sensing.
Compressive sensing based joint spectrum sensing in frequency overlapping net-works
is proposed in the Chapter 4. In many spectrum sensing schemes the geo-temporal
diversity of spectrum occupancy is overseen and all CRs are assumed to be
synchronized during sensing period. However, in large networks, this assumption is
very optimistic and deviates far from the practical scenario. Frequency overlapping
networks also comes into picture in multi-hop networks, multi-band operating de-vices.
We proposed joint spectrum sensing using compressive sensing and developed
joint reconstruction scheme for such frequency overlapping network. We exploit the
joint sparsity of the overlapped region to have better spectrum sensing performance
at minimal cost. Proposed joint spectrum sensing and reconstruction method have
shown to perform better than the individual reconstruction and LASSO consensus
scheme.
A novel compressive sensing scheme for Binary signals is proposed in the Chapter
5. Binary signals pictures into many practical applications such as detection problems,
black and white images, group testing, binary classification etc. We implement the
bipartite graphs to represent the binary compressive sensing process. A unique, but
universal sampling matrix for binary signal is developed. We first implement edge
evolution concept from error control coding to make the bipartite graph less dense
and then implement check-sum method to completely decode all the variable nodes in
the system. Our proposed scheme stands out from conventional optimization based
compressive sensing scheme in terms of both, decoding accuracy and decoding time.
In totality, in this thesis, we have proposed compressive sensing based spectrum
sensing for cognitive radio networks and also presented a novel binary compressive
sensing scheme. However, there exists ample of space to improve and enhance in
future work. Spectrum sensing in multiple Geo-Temporal-Frequency domains can be
an interesting new research space to look into. Spectrum diversity can be modeled in
81
the Geo-Temporal-Frequency domain and their inter relation can be used to enhance
the spectrum sensing performance. Our proposed compressive sensing for binary
signals can be used in many practical applications such as even detection in wireless
sensor networks, binary image sampling and reconstruction, small scale classification
problems etc.
6.1 Future Works
Current works in spectrum sensing and our work in this area are bounded on the
assumption that the spectrum occupancy state is static according to the Geo-temporal
and frequency domain. It is considered that if a channel has some occupancy state
busy or idle at any region or time, the occupancy state is same at any other location.
Besides, the correlation between the channel occupancy state in geographical and
temporal region is also not considered. If we model the channel occupancy state and
their correlation in geo-temporal or even frequency region then we can exploit this
prior correlation information in multi-dimensional spectrum sensing.
Figure 6.1: Spectrum occupancy state variation in spatio-temporal region
In the Fig. 6.1, we can see that the spectrum state variation according to the ge-
82
ographical and temporal region [77]. By modeling this correlation between the spatio
-temporal spectrum occupancy distribution, multi-dimensional spectrum sensing can
be carried out.
In the Chapter 5, we have developed a novel compressive sensing method for
binary sparse signal. Binary sparse signal comes into application in many areas such
as event detection in wireless sensor networks. In wireless sensor networks, an event
is modeled as 1 whereas, no-event is modeled as 0 [65, 66]. In this case, the signal
under consideration is Binary sparse signal so our approach can be used in this kind
of network for sparse event detection.
The current compressive sensing algorithms based on l1 minimization process takes
longer decoding time as discussed in the Chapter 5. Let us consider a dynamic wireless
sensor network where the sensor events changes very rapidly with time as shown in
the Fig. 6.2.
0 5 10 15 20 25
0
0.5
1
Sensor Nodes
Events
0 5 10 15 20 25
0
0.5
1
Sensor Nodes
Events
0 5 10 15 20 25
0
0.5
1
Sensor Nodes
Events
At Time, (t=t3)
At Time, (t=t1)
At Time, (t=t2)
Figure 6.2: Wireless sensor network with dynamic and rapid event changes
When the time difference between the state change in the network is very short, i.e.
83
(t2−t1) is very short, there is high probability that the optimization based schemes,
which takes longer decoding time fail to detect those changes. In these cases, we
need very fast decoding approach. In the Chapter 5 we have already shown that our
scheme takes comparatively very short decoding time compared to the optimization
based schemes. Hence, our scheme can be very beneficial in such scenarios.
84
BIBLIOGRAPHY
[1] FCC, Spectrum Policy Task Force Report,ET Docket No. 02-155. Nov 2002.
[2] S. S. Company, Spectrum Occupancy Measurements.
[3] J. Mitola, Cognitive radio: An Integrated Agent Architecture for Software Defined
Radio. Doctor of technology, Royal Inst. Technology. (KTH), Stockholm, Sweden,
2000.
[4] D. Cabric, S. Mishra, and R. W. Brodersen, “Implementation issues in spectrum
sensing,” Asilomar Conference on Signal, Systems and Computers, November
2004.
[5] A. Sahai, N. Hoven, S. Mishra, and R.Tandra, “Fundamental design tradeoffs in
robust spectrum sensing for opportunistic frequency reuse,” Tech. Report, 2006.
[6] S. Haykin, “Cognitive radio: Brain empowered wiless communications,” IEEE
Journal on selected areas in communications, vol. 23, February 2005.
[7] J. Mitola and G. Q. Maguire, “Cognitive radio: Making software radios more
personal,” IEEE Personal communications, pp. 13–18, August 1999.
[8] J. Sonnenschein and P. M. Fishman, “Radiometric detection of spreadspectrum
signals in noise of uncertainty power,” IEEE Transactions on Aerospace and
Electronic Systems, vol. 28, no. 3, pp. 654–660, 1992.
[9] R. Tandra and A. Sahai, “Fundamental limits on detection in low snr under noise
uncertainty,” Proceedings of the International Conference on Wireless Networks,
Communications and Mobile Computing, vol. 1, pp. 464–469, 2005.
85
[10] R. Tandra and A. Sahai, “’snr’ walls for signal detection,” Journal on Selected
Topics in Signal Processing, vol. 2, no. 1, pp. 4–17, 2008.
[11] T. Yucek and H. Arslan, “A survey in spectrum sensing algorithms for cognitive
radio applications,” IEEE communications surveys and tutorials, vol. 11, no. 1,
pp. 116–130, 2009.
[12] J. Proakis, Digital communications. McGraw Hill, 4 ed., 2001.
[13] M. Davenport, M.Wakin, and R. Baraniuk, “Detection and estimation with com-pressive
measurements,” TREE 0610, Rice ECE Department Technical Report,
November 2006.
[14] J. Haupt and R. Nowak, “Compressive sampling for signal detection,” IEEE Int.
Conf. on Acoustics, Speech, and Signal Processing (ICASSP), April 2007.
[15] G. Giannakis, Cyclostationary Signal Analysis. Boca Raton: CRC Press LLC,
1999.
[16] K.Kim, I. Akbar, K. Bae, T. Urn, C. Spooner, and J. Reed, “Cyclostationary
approaches to signal detection and classification in cognitive radio,” IEEE Int.
Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2007.
[17] C. M. da Silva, B. Choi, and K. Kim, “Distributed spectrum sensing for cognitive
radio systems,” Information Theory and Applications Workshop, Oct 2007.
[18] T. Farnham, G. Clemo, R. Haines, E. Seidel, A. Benamar, S. Billington,
N. Greco, N. Drew, T. Le, B. Arram, and P. Mangold, “Ist-trust:a perspective on
the reconfiguration of future mobile terminals using software download,” in Proc.
IEEE Int. Symposium on Personal, Indoor and Mobile Radio Communication,
pp. 1054–1059, Sept 2000.
86
[19] M. Mehta, N. Drew, G. Vardoulias, N. Greco, and C. Niedermeier, “Reconfig-urable
terminals: an overview of architectural solutions,” IEEE Commun. Mag.,
no. 8, pp. 82–89, 2001.
[20] G. Vardoulias, J. Faroughi-Esfahani, G. Clemo, and R. Haines, “Blind radio
access technology discovery and monitoring for software defined radio communi-cation
systems: problems and techniques,” Int. Conf. 3G Mobile Communication
Technologies, pp. 306–310, March 2001.
[21] Z. Wang, G. Arce, J. Paredes, and B. Sadler, “Compressed detection for ultra-wideband
impulse radio,” SPAWC 2007.
[22] H.Tang, “Some physical layer issues of wideband cognitive radio systems,” Int.
Symposium on New Frontiers in Dynamic Spectrum Access Network, pp. 151–
159, November 2005.
[23] S. Geirhofer, L.Tong, and B.Sadler, “A measurement based model for dynamic
spectrum access in wlan channels,” IEEE Military communication conference,
Oct 2006.
[24] S. Geirhofer, B.Sadler, and L.Tong, “A measurement based model for dynamic
spectrum access in wlan channels:emirical model and stochastical analysis,” Intl.
Workshop on technology and policy for accessing spectrum, Aug 2006.
[25] D. Cabric, A. Tkachenko, and R.Broderson, “Spectrum sensing measurement of
pilot, energy and collaborative detection,” IEEE Military communication con-ference,
Oct 2006.
[26] F. Digham, M. Alouni, and M. Simon, “On the energy detection of unknown sig-nal
over fading channels,” IEEE conference on communication, vol. 5, pp. 3575–
3679, May 2003.
87
[27] A. Ghasemi and E. Sousa, “Optimization of spectrum sensing for opportunistic
spectrum access in cognitive radio network,” IEEE consumer communicationa
nd networking conference, pp. 1022–1026, Jan 2007.
[28] Y. Yuan, P.Bahl, R. Chandra, P. Chau, J. Ferell, T. Moscibroda, S.Naralanka,
and Y.Wu, “KNOWS: Cognitive radio network over white spaces,” IEEE Intl.
Symposim on Dynamic Spectrum Access, pp. 416–427, April 2007.
[29] B. Nakarmi, “Study on cooperative spectrum sensing for the cognitive radio,”
Master’s thesis, Harbin Engineering University, Harbin, China, June 2008.
[30] D. Donoho, “Compressed sensing,” IEEE transaction on information theory,
vol. 52, pp. 1289–1306, April 2006.
[31] R. Baraniuk, “Compressive sensing,” Lecture Notes in IEEE Signal Processing
Magazine, vol. 24, July 2007.
[32] E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal
reconstruction from highly incomplete frequency information,” IEEE Transac-tions
on Information Theory,, vol. 52, no. 2, pp. 489 – 509, 2006.
[33] Y. Pati, R. Rezahfar, and P. Krishnaprasad, “Orthogonal matching pursuit:
Recursive function approximation with application to wavelet decomposition,”
In proc. of 27 Annual Asilomar Conference on Signals Systems and Computers,,
pp. 1 – 5, Nov 1993.
[34] J. A. Tropp and A. C. Gilbert, “Signal recovery from random measurements
via orthogonal matching pursuit,” IEEE Transactions on Information Theory,,
vol. 53, no. 12, pp. 4655 – 4666.
[35] P. Huber, “Projection pursuit,” The annals of statistics, vol. 13, pp. 1435–475,
1985.
88
[36] D. Needell and J. A. Tropp, “Cosamp: iterative signal recovery from incomplete
and inaccurate samples,” Commun. ACM, vol. 53, pp. 93–100, December 2010.
[37] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based com-pressive
sensing,” IEEE Trans. Inf. Theor., vol. 56, pp. 1982–2001, April 2010.
[38] D. Baron, S. Sarvotham, and R. G. Baraniuk, “Bayesian compressive sensing via
belief propagation,” to appear in IEEE Transactions on Signal Processing, 2009.
[39] N. Vaswani and W. Lu, “Modified-cs: modifying compressive sensing for prob-lems
with partially known support,” in Proceedings of the 2009 IEEE interna-tional
conference on Symposium on Information Theory - Volume 1, (Piscataway,
NJ, USA), pp. 488–492, IEEE Press, 2009.
[40] FCC, “Spectrum policy task force report,” In Procc. of the Federal communica-tions
comissions (FCC’02), Washigton, DC, USA, Nov 2002.
[41] M.H.Islam, C.L.Koh, and e. S.W.Oh, “Spectrum survey in singapore: occupancy
measurements and analysis,” Proc. of 3rd International Conference on Cognitive
Radio Oriented Wireless Network and Communications (CROWNCOM’08), sin-gapore,
May 2008.
[42] Q. Zhao and B. Sadler, “A survey of dynamic spectrum access,” Signal Processing
Magazine, IEEE, vol. 24, pp. 79 –89, may 2007.
[43] L. Grande, “Dynamic spectrum access policy standards work,” in Military Com-munications
Conference, 2009. MILCOM 2009. IEEE, pp. 1–4, oct. 2009.
[44] J. Mitola, Cognitive radio: An Integrated Agent Architecture for Software Defined
Radio. Doctor of technology, Royal Inst. Technology. (KTH), Stockholm, Sweden,
2000.
89
[45] F. Digham, M. Alouni, and M. Simon, “On the energy detection of unknown sig-nal
over fading channels,” IEEE conference on communication, vol. 5, pp. 3575–
3679, May 2003.
[46] G. Vardoulias, J. Faroughi-Esfahani, G. Clemo, and R. Haines, “Blind radio
access technology discovery and monitoring for software defined radio communi-cation
systems: problems and techniques,” Int. Conf. 3G Mobile Communication
Technologies, pp. 306–310, March 2001.
[47] I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty, “Next genera-tion/
dynamic spectrum access/cognitive radio wireless networks: A survey,”
Computer Networks, vol. 50, no. 13, pp. 2127 – 2159, 2006.
[48] Z.Tian and G. Giannaskis, “Compressed sensing for wideband cognitive radios,”
Proc. of International Conference on Acoustic Speech and Signal Processing,
pp. IV/1357–IV/1360, April 2007.
[49] J.Meng, W.Yin, H.Li, and Z.Han, “Collaborative spectrum sensing for sparse
observation using matrix completion for for cognitive radio network,” The 35th
International conference on acoustic, speech, and signal processing, (ICASSP),
2010.
[50] Z. Yu, X. Chen, S. Hoyos, B. M. Sadler, J. Gong, and C. Qian, “Mixed-signal par-allel
compressive spectrum sensing for cognitive radios,” International Journal
of Digital Multimedia Broadcasting, 2010.
[51] S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud,
and R. Baraniuk, “Analog-to-information conversion via random demodulation,”
2006.
90
[52] F. Digham, M. Alouni, and M. Simon, “On the energy detection of unknown sig-nal
over fading channels,” IEEE conference on communication, vol. 5, pp. 3575–
3679, May 2003.
[53] E. J. Candes, M. B. Wakin, and S. P. Boyd, “Enhancing sparsity by reweighted
l1 minimization,” J Fourier Anal Appl, vol. 14, pp. 877–905, 2008.
[54] Z. Zhang, S. Chan, Y. Zhou, and Y. Hu, “Robust linear estimation using m-estimation
and weighted l1 regularization: Model selection and recursive imple-mentation,”
in Circuits and Systems, 2009. ISCAS 2009. IEEE International
Symposium on, pp. 1193 –1196, may 2009.
[55] “http://www.ntia.doc.gov/osmhome/allochrt.pdf,”
[56] F. Zeng, C. Li, and Z. Tian, “Distributed compressive spectrum sensing in coop-erative
multihop cognitive networks,” IEEE Journal of Selected Topics in Signal
Processing, vol. 5, pp. 37–48, Feb 2011.
[57] U.Nakarmi and N. Rahnavard, “A new approach to spectrum management in
cognitive radio networks,” In proc. of International conference on smart technolo-gies
for materials, communications, controls, computing and Energy, (ICST),
pp. 3–7, Jan 2011.
[58] M. F. Duarte, S. Sarvotham, M. B.Wakin, D. Baron, and R. G. Baraniuk, “Joint
sparsity models for distributed compressed sensing,” Online Proceedings of the
Workshop on Signal Processing with Adaptative Sparse Structured Representa-tions
(SPARS), 2005.
[59] M. F. Duarte, S. Sarvotham, D. Baron, M. B. Wakin, and R. G. Baraniuk,
“Distributed compressed sensing of jointly sparse signals,” in Proceedings of the
39th Asilomar Conference on Signals, Systems and Computation, (Pacific Grove,
CA), pp. 1537–1541, Nov. 2005.
91
[60] C. Dossal, M.-L. Chabanol, G. Peyr´e, a