CS-541
Wireless Sensor Networks
Lecture 5: Signal Sampling for WSN
PART A
Spring Semester 2016-2017
Prof Panagiotis Tsakalides, Dr Athanasia Panousopoulou, Dr Gregory Tsagkatakis
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 1
University of Crete, Computer Science Department
Today’s objectives
Signal Sampling
Compressed Sensing
Applications in WSN
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 2
University of Crete, Computer Science Department
Sensing in WSNs
Sensing Quantization Storage/Processing Communications
Sensor type A/D Size Route selection
Operations Bus Speed Reliability/Connectivity
Calibration Complexity Robustness
Power consumption
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 3
University of Crete, Computer Science Department
Objectives
Efficient data acquisition and gathering
• Increase life-time of network
• Reduce communication requirements
• Handle transmission errors
• Reduce calibration operations
• Facilitate data classification
Prior Knowledge
• Training data
• Spatio-temporal correlations
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 4
University of Crete, Computer Science Department
Signal Sensing
Nyquist–Shannon
• limited signal support
• Signal bandwidth B
Sampling rate Fs=2B
(Nyquist rate)
𝑦 Φ=I 𝑥
Limitations
• Requirements
• Power/battery
• Storage/Bandwidth =
• Calibration
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 5
University of Crete, Computer Science Department
Low dimensional signal models
• Why dimensionality reduction
• Compression
• Analysis
• Curse of dimensionality
• Visualization
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 6
University of Crete, Computer Science Department
Challenges in dimensionality reduction
30
20
10
0
1
-10
0.5
-20
0
-30
-30 -20 -10 0 10 20 30
-0.5 10
8
-1
1 6
0.5
-1 4
0 -0.5
-0.5 0 2
0.5
-1 1 0
-2
-4
-10 -8 -6 -4 -2 0 2 4
Spring Semester 2016-2017 7
Dimensionality reduction
sparse signal
sensing matrix
measurements
Dimensionality reduction
Directly acquire a compressed representation
with no/little information loss
Objectives:
• Extract low dimensional information from a signal that is in a high
dimensional space
• Preserve critical relationships among parts of the data
• Understand the structure of the low dimensional information
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 8
University of Crete, Computer Science Department
Principal Components Analysis
• Definition: Given a set of data , find the principal
axes, which are those orthonormal axes onto which the
variance retained under projection is maximal
• “Kosambi-Karhunen–Loève” (KLT) transform
• PCA: Eigenvectors of covariance matrix
Adapted from Dimensionality Reduction with PCA,Ke Tran, May 24, 2011
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 9
University of Crete, Computer Science Department
Principal Components
5 Input: 2-d dimensional points
2nd Eigenvector Output:
1st Eigenvector:
4 direction of maximal variance,
2nd Eigenvector:
direction of maximal variance, after
3 removing the projection of the
data along the first singular vector.
1st Eigenvector
2
4.0 4.5 5.0 5.5 6.0
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 10
University of Crete, Computer Science Department
Principal Components Analysis
1. Normalize the input data then center the input data by
subtracting the mean which results in X, used below
2. Compute the global mean and covariance matrix of X:
1 N n
Σ (x x)(x n x)T
N n1
3. Compute the eigenvalues and eigenvectors of the
covariance matrix
4. Arrange eigenvectors in the order of magnitude of their
eigenvalues.
5. Take the first d eigenvectors as principle components.
6. Put the d eigenvectors as columns in a matrix M.
7. Determine the reduced output E by multiplying M by X
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017
University of Crete, Computer Science Department
PCA in WSN
why:
• clarify relationships among variables
• clarify relationships among cases
when:
• significant correlations exist
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 12
University of Crete, Computer Science Department
PCA in WSN
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 13
University of Crete, Computer Science Department
Manifold Learning
• A K-dimensional manifold embedded in RN as a nonlinear, K-dimensional
“surface”within RN
• Isomap [8]
• Locally Linear Embedding (LLE) [9]
• Laplacian Eigenmaps (LE)
• Maximum Variance Unfolding (MVU) [10]
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 14
University of Crete, Computer Science Department
Application: Internet Traffic Visualization
• Spatio-temporal measurement vector:
temperature
day
temperature
day
temperature
day
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 15
University of Crete, Computer Science Department
Random Projections
Johnson-Lindenstrauss (JL) lemma
Sensing matrix What’s wrong with PCA
• Computational complexity
• Universality
• Adaptability
• Robustness
Given 0 < ε < 1, a set Q of m points in RN, and a number
n > 8 ln(m) / ε 2, there is a linear map ƒ : RN → Rn such that
for all x, y ∈ Q.
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 16
University of Crete, Computer Science Department
Simplified Random Projection (SRP)
• f: Random matrix is usually gaussian distributed
• mean: 0; standart deviation: 1
• f: sparse RP distribution
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 17
University of Crete, Computer Science Department
What about recovery?
Can we recovery the original signal from its RP?
YES…. for sparse signal
Biological Environmental Astronomical
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 18
University of Crete, Computer Science Department
x (+1)
x (-1)
Q: which sensor is different (using as few observations as possible) ?
A: Project the data onto random vectors (second column)
• Initially: n/2 hypothesis sensors are consistent with each random projection observation
• Exponential decrease of consistence observations
Observations
• Random projections -> binary bisections of the hypothesis space
• Only log n observations are needed to determine which sensor reads the nonzero value.
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 19
University of Crete, Computer Science Department
Compressed Sensing
(or compressive sensing, compressed sampling…)
• Goal: Recover signal
from measurements
• Problem: Random
projection not full rank
(ill-posed inverse problem)
• Solution: Exploit the sparse/compressible
geometry of acquired signal
• Recovery via (convex) sparsity penalty or greedy algorithms
𝑥 = arg min 𝑥 0 subject to Φ𝑥 = 𝑦
𝑥
[Donoho; Candes, Romberg, Tao, 2004]
NP-hard!
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 20
University of Crete, Computer Science Department
How many measurements?
Φ satisfies Restricted Isometry Property (RIP)
For all x that are K sparse
When Φ MxN satisfies RIP of order 2K with δ<√(2)-1,
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 21
University of Crete, Computer Science Department
Matching Pursuit Algorithms
• Use greedy algorithm to iteratively recover sparse signal
• Procedure:
1. Initialize
2. Find the column that is most correlated
3. Set Union (add one col. every iter.)
4. Solve the least squares
5. Update data and residual
6. Back to step 2 or output
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 22
University of Crete, Computer Science Department
A linear programming approach
Replace greedy with convex optimization problem
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 23
University of Crete, Computer Science Department
Compressed Sensing via
• 0-norm is nonconvex difficult to solve
• 1-norm is convex Basis Pursuit (Lasso)
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 24
University of Crete, Computer Science Department
Performance of Recovery
• Using methods
• Sparse signals
• noise-free : exact recovery
• noisy : stable recovery
• Compressible signals
• recovery as good as
K-sparse approximation
CS recovery signal K-term noise
error approx error
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 25
University of Crete, Computer Science Department
Sparse event detection
• N sources, K events, K<<N, M sensors
• Event vector
• Channel response
• Received signal
• Formulation
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 26
University of Crete, Computer Science Department
Sparse location estimation
• The location of mobile device is sparse in space.
Sparse vector: b
0 0 0 0 0
0
1 0 0 0 0 Space
Vectorization 1 User’s
0 0 0 0 0 .
. Location
.
0 0 0 0 0 0
0 0 0 0 0
Dx1
D cells
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 27
University of Crete, Computer Science Department
Sparse location estimation
MD Training RSS measurements are collected
for each position.
Signature map
TAP1,Cell1 TAP1,Cell2 … TAP1,CellD
TAP2,Cell1 TAP2,Cell2 … TAP2,CellD
TAP3,Cell1 TAP3,Cell2 … TAP3,CellD
Runtime
Runtime measurements
RAP1 RAP2 RAP3
Localization
Server (LS)
?
Compare
Location
TAP1,Cell1 TAP1,Cell2 … TAP1,CellD
Estimation
TAP2,Cell1 TAP2,Cell2 … TAP2,CellD
TAP3,Cell1 TAP3,Cell2 … TAP3,CellD
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 28
University of Crete, Computer Science Department
Sparse location estimation
Active laboratory area of 8.5 by 14 meters
5 APs, 135 training cells, cell size: 0.55 x 0.55 m
Online observations: 30 distinct cells, Performance metric: Location Error (m)
Empirical CDF as a function of CS measurements
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 29
University of Crete, Computer Science Department
Sparsity in a basis: Dictionaries
Sound WSN
Images
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 30
University of Crete, Computer Science Department
Reading material
Haupt, J., Bajwa, W. U., Rabbat, M., & Nowak, R. “Compressed
sensing for networked data.” IEEE Signal Processing Magazine, vol.
25(2), 92-101, 2008.
Qaisar, Saad, Rana Muhammad Bilal, Wafa Iqbal, Muqaddas Naureen,
and Sungyoung Lee. "Compressive sensing: From theory to
applications, a survey." Journal of Communications and networks 15,
no. 5 (2013): 443-456.
Useful links
http://dsp.rice.edu/cs
http://nuit-blanche.blogspot.gr/
CS-541 Wireless Sensor Networks
Spring Semester 2016-2017 31
University of Crete, Computer Science Department
