Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

Does Compressed Sensing Improve the Throughput
of Wireless Sensor Networks?
Jun Luo

Liu Xiang

School of Computer Engineering
Nanyang Technological University (NTU), Singapore
Emails {junluo,xi0001iu}@ntu
...
sg

Abstract—Although compressed sensing (CS) has been envisioned as a useful technique to improve the performance of
wireless sensor networks (WSNs), it is still not very clear how
exactly it will be applied and how big the improvements will
be
...
We
formulate three flow-based optimization problems to compute
the throughput of the non-CS, plain-CS, and hybrid-CS schemes
...
Our
preliminary numerical results are only for a low-power regime
...

Index Terms—Wireless sensor networks, compressed sensing,
data aggregation, routing, scheduling
...
I NTRODUCTION
Improving the performance (in terms of throughput, lifetime, delay, etc
...
It is
well known that proper data aggregation techniques1 may
significantly reduce the amount of data transmission load
carried by a WSN and may hence improve its performance
in every aspect
...
First, if only statistical quantities such
as mean and max are extracted from the sensory data [1],
[2], other features of these data are lost and hence this aggregation technique only applies to particular applications that
require limited information from a WSN
...
Finally, whereas collaborative in-network
compression makes it possible to discover the data correlation
structure through information exchange [4], [5], the resulting
high computation and communication load may potentially
offset the benefit of this aggregation technique
...
It refers to any transformation that summarizes or compresses the data acquired and received by a
certain node and hence reduce the volume of the data to be sent out
...
uwaterloo
...
We first show
a naive application of CS where the encoding is performed
at every source
...
These are what we call respectively
the plain-CS and hybrid-CS schemes in the following
...
In formulating these problems, we
assume that the transmission through wireless links can be
scheduled in a conflict-free manner, and we make use of an
SINR-based interference model
...

The contribution of our work, apart from formulating the
joint compression and scheduling problems, is the crucial insights gained from the numerical solutions of these problems
...

Previous proposals to apply CS to WSNs are concerned
with either single-hop data aggregation [10] or efficient data
dissemination [11]
...
Due to their high complexity, the optimization
models and tools that we propose can only be used for
offline studies
...

The remaining of our paper is organized as follows
...
We then
formulate the three problems for non-CS, plain-CS and hybridCS in Section III
...
Finally, we conclude the paper in Section V
...
00 ©2010 IEEE

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

II
...

A
...
Let
us illustrate the idea in a WSN scenario
...
g
...
The ultimate goal of the WSN is to collect the vector
x = [x1 , · · · , xn ]T at the sink
...
, ψn ]T ,
m
n
...
t
...
i
...
zero-mean random variables
1
with variance k
...

z
z
The condition that guarantees the correctness of this recovery
is given by
k ≥ C · m · log n

(2)

where C is some small constant
...
Now, the meaning of “compressed” is
pretty clear: the sink needs to collect only k
n samples (as
m
n by assumption and k ≈ m) to reconstruct the sensory
data represented by the n samples
...
Using pseudo-random number
generators to produce the entries of Φ, we can meet the i
...
d
...
For example, if
we associate a specific generator (a publicly known algorithm
and its seed) with a node i, the i-th column of Φ, φi , can be
generated anywhere with consistent output
...
Although the Ψ
that yields the sparsest representation of x may not be known,
wavelets are in general considered as a good candidate for Ψ,
as explained in [7]
...

B
...
In particular, we call ρ = n the compression ratio
k
of CS
...
Given the de facto four-to-one rule discussed above,

our underlying assumption is that, as far as n ≥ nmin , the
sparsity index m is proportional to the dimension n of a data
vector
...
Of course, these intuitive simplification
assumptions deserve further validation in the future
...
1 to illustrate the idea of CS-based data aggregation as compared to conventional data collection (called
non-CS in the following)
...
1(a),
a node receiving s − 1 packets (each packet corresponding to
a data sample from a node, and the value of s depending on
routing) will send out s packets (the s − 1 received packets
plus its own data sample); the sink, in particular, will need to
receive all the n samples
...

CS-based network operation differs a lot from the non-CS
case
...
Obviously, in order to use CS, each node i
needs to know the value of n, i
...
, how many nodes participate
in the aggregation (could be the whole WSN or a subnet
if a partition has been performed, as we will explain later)
and the value of ρ
...
It
ρ
then creates a vector xi [φ1,i , · · · , φk,i ]T , where xi is its own
sensory data
...
e
...

Each received packet is an element of a column vector of size
k similar to xi [φ1,i , · · · , φk,i ]T and it carries its index from
1 to k so that it can be added to the data already waiting
in i with the same index (either locally produced or received
from a downstream neighbor)
...
As
long as routing is done to avoid duplications of packets, the
sink will receive exactly k aggregated packets that it will
transform back into a column vector x
...
As our studies are
concerning offline network dimensioning, we assume a reliable
network, i
...
, a network without packet losses
...

Note that it is not wise to perform the above CS operation
on the whole network since k = n may still be quite large
...

In addition, the easiest way to avoid duplication is to perform
routing on a spanning tree with the sink as the root
...

For example, given a WSN whose sink has a degree of δ, a
spanning tree may consist of δ subtrees, each rooted at one of

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

Subnet

18

Subnet

24

15

1

5

2

3
1

5
1

1

(a) Non-CS

5

2
5

5

5

2

5

1

5

1

5

1
5

Subnet

8

4

5

5

5

6

Subnet

5

5

5
2

9

Subnet

8

5

1

10
2

6
5

4
1

Subnet

5

2

1

3

5

1

(b) Plain-CS

1

(c) Hybrid-CS

Fig
...
Comparison of different data collection mechanisms
...
The underlined labels indicate CS encoded
traffic, assuming ρ = 3
...


the δ children and having the same number of nodes n = n (of
˜
δ
course building such a partition may not always be possible)
...
In that case,
˜
˜
˜
each subtree is responsible for sending k = n < n packets
ρ
ρ
and the sink will then receive in total k packets as before, but
intermediate nodes in the network will take a much lower load
˜
(k = k instead of k)
...

In the problem formulation described later, we will partition
the network into disjoint subnets and let individual subnets
aggregate data samples independently of the other subnets
...
We illustrate an unbalanced partition
(in particular on one of the subtrees) in Fig
...
Note
that whereas the CS operation (along with routing) is done
independently on each subnet, the link scheduling should still
be performed globally, as the interference generated by a link
(no matter which subtree it belongs to) has a global impact on
the rest of the network
...

III
...

A
...
Each node i ∈ N is associated with a geographical
location
...

We assume that all the nodes have the same transmit
power Ptx and the same data-rate c
...
We assume that the channel gain from a node

i to another node j is quasi-static, since we consider fixed
wireless networks
...
The feasibility of a
wireless link is based on whether a bit-error-rate (BER) less
than a tolerable maximum can be achieved on the link
...
We define L as the set of
all feasible links
...
Let |L| = L, and let lO
and lD denote the origin and destination of link l, respectively
...
Let
ζ ⊂ L denote a set of links
...
It is clear that all the links belonging to an ISet
can be scheduled at the same time in a conflict-free fashion
...
We use
the SINR-based interference model rather than other more
frequently used ones (e
...
, protocol model) simply because
it is more realistic [12]
...
A transmission schedule is
ˆ
an |S|-dimensional vector α = [αζ ]ζ∈S , and we can interpret
αζ as the fraction of time allocated to a link set ζ
...
Therefore,

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

a conflict-free transmission schedule is an |I|-dimensional
vector α = [αζ ]ζ∈I
...
Throughput Maximization for The Case without CS
In the non-CS data collection, we formulate our joint routing
and scheduling problem as a regular flow optimization problem
where we can assume that there is only one many-to-one flow
ending at the sink
...


ql,ζ =

(5)

Note that each column qζ of Q is a vector that represents an
ISet ζ and that the number of columns is |I| which is generally
very large
...


(6)

Let rl be the amount of flow going over a link l, and denote
by r = [r1 , · · · , rL ]T the associated link flow vector
...
The problem explicitly maximizes
flow rate λ over all possible link flows r (or equivalently
routing) and link schedules α
...
We will solve this
problem exactly in the following
...
Interested readers are referred to
[8], [9] for details
...

As shown in Fig
...
Consequently,
the bottlenecks in terms of throughput are usually located at
those “last-hop” nodes
...

T

C
...
II-B, one straightforward (but
naive) way of applying CS is the following: upon acquiring
a sensory data xi , node i generates a random vector φi and
sends xi φi + j∈Πi xj φj , where Πi is the set of downstream
neighbors of i
...
e
...
Translated into a
flow model, this yields a totally egalitarian load allocation, as
every link carries the same flow rate kλ, where k, as explained
in Sec
...
We illustrate this idea by
Fig
...

We will assume single-path routing in the following even
if it is not strictly a requirement
...
Let T be a node disjoint tree cover of N
...
Let T be the extended tree cover such that, for Ti ∈ T ,
ˆi ) = V (Ti ) ∪ {Θ} where V (T ) is the set of vertices of
V (T
ˆ
tree T and E(Ti ) = E(Ti ) ∪ {(i, Θ)} where E(T ) is the set
ˆ
of edges of tree T
...

ˆ
In other words, for l ∈ E(Ti ), the traffic load is ni λ
...

The link load ki λ on the RHS of (12) depends on the size ni of
ˆ
the sub-tree Ti (whose extension Ti includes the link l under
ni
consideration), as ki = ρ
...

Unfortunately, the tree cover problem is in general very hard
[13]
...
This gives
us a feasible solution that can be seen as a lower bound on
the optimal solution for problem (11-13)
...
Throughput Maximization with Hybrid CS
It can be observed that directly applying CS in the way
suggested in Sec
...
More precisely, starting coding
right from the leaf nodes of a tree might be counter-productive
as they have to transmit k packets for each data sample
as opposed to one packet in the non-CS case
...
6

−3

x 10

x 10
Non−CS
Plain−CS
Hybrid−CS

1
...
2
Optimal througput λ*

Non−CS
Plain−CS
Hybrid−CS

1
...
8

0
...
8

0
...
4
0
...
2

0
...


Fig
...


max

ql,ζ αζ

c
ζ∈I

αT 1 ≤ 1

(14)
ni
ρ

−35

−34

−33

−32
−31
Ptx (dBm)

−30

−29

−28

−27

Throughput comparison among non-CS, plain-CS, and hybrid CS
...


compression is only applied at a node whose incoming traffic
intensity becomes larger or equal to kλ
...
1(c)
...

This will be done by generating locally the column vector φ’s
for each sample
...
III-C
...
It is clear that, according to our hybrid-CS
policy, the outgoing links of node j will carry a load of
λ min |Πi,j |, ni , where the first term refers to the flow
ρ
conservation in the non-CS data collection, and the second
term indicates the use of CS to encode the data
...

Therefore, we, again, solve the problem later by decoupling
the tree cover from the scheduling upon it
...
According to Fig
...


IV
...
We assume that the distance between two closest nodes
is 8m
...
1m, and η = 3
...
4dB, and we investigate the optimal throughput as a
function of Ptx
...
Note that, although each value of Ptx ≥ Pmin may
not yield a new set of links (hence a new topology), it might
produce new ISets
...

For the cases with CS, we need to create a partition so that
each subnet has at least nmin nodes
...
For our current
computations, we use Dijkstra’s algorithm to generate the tree
cover T (which decouples routing from link scheduling), and
we set ρ = 5
...
We do not allow a
partition in which one of the subtrees becomes too small, i
...
We have limited our computations to low
values of Ptx since our computational tool requires a memory
space larger than what a 32-bit program can handle (recall that
the joint scheduling problem is on the whole network that has
1225 nodes and thus there is a huge set of potential ISets when
Ptx is large)
...

The results for both cases are shown in Fig
...
The black
lines in both figures show the maximum achievable throughput
of non-CS data collection if we keep increasing Ptx until

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

every node has a direct link to the sink
...
One may argue that it is not fair to compare a lower
bound on the throughput of plain-CS to the optimal throughput
of non-CS
...
Of course,
increasing ρ will improves the performance of both plainCS and hybrid-CS
...
Therefore, we are not expecting a significant
increase in ρ
...
Whenever new links are created due to a
transmit power increase, the algorithm will produce a tree
cover using these new links
...
This explains the big “falls” in the
curves at Ptx = −31
...
Note that,
at the maximum power shown in the figures (i
...
, −27
...
In order to show that the “falls” were
due to the way we constructed the tree cover and not to an
inherent problem with either the CS schemes or the particular
network topology, we computed the performance of the plainCS and hybrid-CS schemes at powers greater than −32dBm
by fixing T to be the one computed for Ptx = −32dBm
(i
...
, at a power level that does not make the shortest diagonal
links feasible)
...
As expected, the
performances with a fixed T (represented by the circles in the
figures) do not exhibit any decrease
...

V
...
We first describe a naive way of applying
CS called plain-CS, then we propose a hybrid-CS scheme that
combines conventional data collection (non-CS) with plainCS
...
The most important insights we acquired from
this study are: (i) applying CS naively may not bring any
improvement, and (ii) our hybrid-CS can achieve significant
improvement in throughput as compared with non-CS
...


It will be part of our future work to develop better partitioning strategies for our hybrid-CS scheme
...
Moreover, we will be looking at the
combination of the physical layer CS (e
...
, [11]) and our
networking layer CS to further improve the throughput of
WSNs
...

R EFERENCES
[1] S
...
Franklin, J
...
Hong, “TAG: A Tiny
AGgregation Service for Ad-hoc Sensor Networks,” ACM SIGOPS
Operating Systems Review, vol
...
SI, 2002
...
Gao, L
...
Milosavljevic, and J
...
of the 4th ACM IPSN, 2007
...
Slepian and J
...
on Information Theory, vol
...
4, 1973
...
Cristescu, B
...
Vetterli, and R
...
on Networking,
vol
...
1, 2006
...
Gupta, V
...
Das, and V
...
on Sensor Networks,
vol
...
1, 2008
...
Cand` s and M
...
, vol
...
3, 2008
...
Haupt, W
...
Rabbat, and R
...
, vol
...
3, 2008
...
Luo, A
...
Rosenberg, “Efficient Algorithms to Solve a
Class of Resource Allocation Problems in Large Wireless Networks,” in
Proc
...

[9] J
...
Rosenberg, and A
...
on Networking (to appear), 2010,
http://www3
...
edu
...
pdf
...
Rabbat, J
...
Singh, and R
...
of the
3th ACM IPSN, 2006
...
Bajwa, J
...
Sayeed, and R
...
of the 3th ACM IPSN, 2006
...
Iyer, C
...
Karnik, “What is the Right Model for
Wireless Channel Interference?” IEEE Trans
...
8, no
...

[13] G
...
amd N
...
K¨ nemann, R
...
Sinha, “Min-Max
o
Tree Covers of Graphs,” Elsevier Operations Research Letters, vol
...
4, 2004

---