7/31/2019 Mobicom'09 CDG
1/17
Compressive Data Gathering for
Large-Scale Wireless Sensor
Networks
Chong Luo, Feng Wu, Jun Sun and Chang Wen Chen
Mobicom09, Beijing, China
7/31/2019 Mobicom'09 CDG
2/17
Outline
Background
Compressive sensing theory
New research opportunities
Compressive Data Gathering
The first complete design to apply CS theory for
sensor data gathering
Conclusion
7/31/2019 Mobicom'09 CDG
3/17
Compressive Sensing
If an N-dimensional signal is K-sparse in a known domain, itcan be recovered from M random measurements by:
7/31/2019 Mobicom'09 CDG
4/17
New Research Opportunities
Compressive Sensing Hallmarks
Universal
Same random projection op.for any compressible signal
Democratic
Potentially unlimited numberof measurements
Each measurement carriesthe same amount of
information
Asymmetrical
Simple encoding, mostprocessing at decoder
Data Communications Research
Random linear networkcoding
Achieves multicast capacity
Fountain code
a.k.a. rateless erasure code
Perfect reconstruction fromN(1+) encoding symbols
Distributed source coding e.g. Slepian-Wolf coding
Blind encoding, jointdecoding
7/31/2019 Mobicom'09 CDG
5/17
From Compressive Sensing to
Compressive Data Gathering
The asymmetrical property makes CS a perfect
match for wireless sensor networks
Compressive Sensing Compressive Data Gathering
Sample-then-compress
Sample-with-compression
Compress-then-transmit
Compress-with-transmission
7/31/2019 Mobicom'09 CDG
6/17
Data Gathering in WSNs
Challenges
Global communication cost reduction
Energy consumption load balancing
Sink
Internet or
Satellite
Sensing field
7/31/2019 Mobicom'09 CDG
7/17
Basic Idea
A simple chain topology
sNs1 s2 s3
d1
d1
d2
d1
d2
dN
Global comm. cost Bottleneck load
Baseline transmission N(N+1)/2 N
Proposed CDG NM M
7/31/2019 Mobicom'09 CDG
8/17
Is Reconstruction Possible?
Facts
Sensor readings exhibit strong spatial correlations
According to CS theory
Reconstruction can be achieved in a noisy setting by
solving:
M
7/31/2019 Mobicom'09 CDG
9/17
Practical Problem 1
Abnormal readings compromise data sparsity
Solution:
-10
-5
0
5
10
Signal in time domain
-5
0
5
10
Representation in DCT domain
-10
-5
0
5
10
-5
0
5
10
-10
-5
0
5
10
-10
-5
0
5
10
Signal d1
Signal d2
-10
-5
0
5
10
-10
-5
0
5
10
Representation ofd1 in DCT domain
Representation ofd2 in time domain
7-sparse
Overcomplete
basis
7/31/2019 Mobicom'09 CDG
10/17
Practical Problem 2
If a signal is not sparse in any intuitively known domain
1
2
3
4
56
7
8
9
10
11
12
13
14
15
16
17
18
19
20
t
value
y d
7/31/2019 Mobicom'09 CDG
11/17
Universal Sparsity
CS-based data representation and recovery isoptimal in exploiting data sparsity
Encoder
The same random projection operation Decoder
Select and design representation basis Reorder signal d to make it sparse in a known domain
Neither transform-based compression nordistributed source coding is able to exploit thesespecial types of data sparsity
7/31/2019 Mobicom'09 CDG
12/17
Network Capacity Gain
Theorem: In a wireless sensor
network with N nodes, CDG
can achieve a capacity gain
of N/M over baselinetransmission, given that
sensor readings are K-sparse,
and M = c1K.
Mathematical proof
Simulation verification
7/31/2019 Mobicom'09 CDG
13/17
Example 1
CTD data from NOAA
N=1000, K40
0
10
20
30
0 200 400 600 800 1000
T
emperature()
Depth / Pressure (dbar)
-10
0
10
20
30
0 200 400 600 800 10000
10
20
30
40
50
0 50 100 150 200
SNR(dB
)
Number of random measurements (M)
M=100
Recon. Precision 99.2%Comm. Reduction 5
Capacity Gain 10
7/31/2019 Mobicom'09 CDG
14/17
7/31/2019 Mobicom'09 CDG
15/17
Utilizing Temporal Correlation
Sensor readings at t0 + t are sparse as well
Temperatures do not change violently with time
10
20
30
(a) Original
10
20
30
(b) Reconstruction from 0.5N measurements
10
20
30
(c) Reconstruction from 0.3N measurements
t=30min
7/31/2019 Mobicom'09 CDG
16/17
Conclusion
Compressive Sensing is an emerging field whichmay bring fundamental changes to networkingand data communications research
Our Contributions The first complete design to apply CS theory to sensor
data gathering
CDG exploits universal sparsity
CDG improves network capacity
Future Work Bring innovations to LDPC, NC, DSC, and Fountain
code through CS theory
7/31/2019 Mobicom'09 CDG
17/17
THANKS!
Top Related