On the interdependence of routing and data compression in multi-hop sensor networks.
We consider a problem of broadcast communication in a multi-hop sensor network, in which samples of a random field are collected at each node of the network, and the goal is for all nodes to obtain an estimate of the entire field within a prescribed distortion value. The main idea we explore in this paper is that of jointly compressing the data generated by different nodes as this information travels over multiple hops, to eliminate correlations in the representation of the sampled field. Our main contributions are: (a) we obtain, using simple network flow concepts, conditions on the rate/distortion function of the random field, so as to guarantee that any node can obtain the measurements collected at every other node in the network, quantized to within any prescribed distortion value; and (b), we construct a large class of physically-motivated stochastic models for sensor data, for which we are able to prove that the joint rate/distortion function of all the data generated by the whole network grows slower than the bounds found in (a). A truly novel aspect of our work is the tight coupling between routing and source coding, explicitly formulated in a simple and analytically tractable model---to the best of our knowledge, this connection had not been studied before.
Appendix

B)), for is the minimum amount of bits that should be transported through the
network to solve the transmission problem we are interested in.
C. Contributions and Paper Organization
The main ideas of this paper are: 1) to de?ne a model for the sensor data to derive the scaling law of
versus combining routing and data-compression to prevent congestion in highly populated sensor networks. Our
main results are:
(a) The proof of the existence of routing algorithms and source codes that require no more than
bits in transmissions, where is the joint rate/ distortion function of all samples in the ?eld. This
would prove that, even under decentralization constraints, classical source codes can still achieve optimal compression
ef?ciency. And furthermore, attaining that optimal performance requires a number of transmissions that is sub-linear
in the number of nodes in the network.
(b) The proof that , under some mild regularity conditions on the random ?eld.
That is, if the average distortion per sample is kept constant, the ?eld generates a bounded amount of information,
independently of its size. And if the total distortion is kept constant, the growth of is only logarithmic in , well
below the total transport capacity of the network, which grows like (as will be argued in Section I-A in
agreement with the result in [9]).
Our paper shows that performing routing and data compression in a combined fashion can prevent congestion, however
several questions still remain to be answered: Is there an optimal strategy that allows to visit the nodes so as to
minimize the effective data-?ow? What is the optimum trade-off between routing delay and traf?c? These questions,
though practically very important, are outside the scope intended for this paper.
The rest of this paper is organized as follows. In Section IV we compute bounds on the transport capacity of our
network, and we use these bounds to impose constraints on total traf?c that can ?ow through the network. Then, in
Section V, we propose a model for the generation of sensor data, based on which we prove that indeed, the amount
of data generated by the network is well below network capacity. Numerical examples and concluding remarks are
presented in Section VII and VIII respectively.
II. INDEPENDENT ENCODERS
To provide the sought conditions, the ?rst thing we need to do is ?nd out how much traf?c does this network
generates. Very clearly this question depends on the statistics of the sensed data and the quantization/compression
technique used. In standard communication networks that support the transmission of analog sources (voice, images
and video) every information source independently encodes and compresses the data, which are then routed through an
high speed core network to the destination (see Fig.2). Networking issues and physical aspects of the the information
Routing
Quantization
Compression
Fig. 2. Traditional network setting.
processing are naturally kept separated in the traditional network structure in Fig. 2. It is obvious to ask ourselves how
would the bits generated by the sensors increase with the network size if the sensors operate as independent encoders,
following the traditional structure discussed above.
For illustration purposes we can consider a simple example: suppose that is uniform in the range , that
each node uses a scalar quantizer with bits of resolution (i.e., the quantization step is ), and that the distortion
is measured in the mean-square sense (i.e. A well known result from basic quantization
theory states that on this particular source the average distortion achieved by such a quantizer (also called operational
distortion-rate function) is [6]:
The total distortion on the entire vector of samples is , and hence,
solving for in , we derive that to maintain a total distortion over the entire network of each sample
requires bits. As a result, the total amount of traf?c generated by the whole network scales like
in network size. Interestingly, even using optimal vector quantizers at each node, if the compression of
the node samples is performed without taking into consideration the statistics of the other sensors' measurements, the
scaling law is still : in other words, one could certainly reduce the number of bits generated for a ?xed
distortion level but this reduction would only affect constants hidden by the big-oh notation and the
scaling behavior of network traf?c would remain unchanged [3] (examples of analyses of this type can be found in [14,
Sec. 3] and [19, Sec. 7]). In fact, even if each node utilizes a dimesional vector quantizer to compress optimally
a sequences of subsequent samples, say , high resolution methods [6] show that the operational
distortion rate function would be:
where , is the differential entropy of , i.e.:
is the joint density of the samples collected at the node and is a source speci?c
constant. Hence, the node distortion rate function with respect of a general source has a factor replacing the
of the example discussed above, but the dependence on is still through the exponential term .
Once we have determined how much data our particular coding strategy (independent quantizers at each node)
produces, we need to know if the network has enough capacity to transport all that data. For independent encoders the
answer is no [9]. To see how this is so, consider a partition of the network as shown in Fig. 3.
Fig. 3. nodes are spread uniformly over the unit square ( large). Take a differential volume of
size ( small). With high probability, the number of nodes in a differential volume is , and so the
number of nodes in a strip as shown in the ?gure is . Since the total number of nodes is , we must have
(because the total area of the unit square is the product of the areas of two strips as shown in the
?gure, one horizontal and one vertical), and hence we must have that the number of nodes in a strip as shown is
.
In the sensor broadcast problem of interest in this work, all the nodes in the network must receive information
about the measurements collected by all other nodes. As a result, all the traf?c generated on the left portion of the
network must be carried to the right, and all the traf?c generated on the right portion of the network must be carried
to the left. That is, according to our calculation above, the nodes within the strip marked in Fig. 3 must share the load
of moving bits across this network cut. But since the links present on the stripe have a capacity ,
the capacity of this cut cannot be larger than . From the max-?ow/min-cut theorem [4, Ch. 27], we know
that the value of any ?ow in this network is upper bounded by the capacity of any network cut, and therefore, the total
transport capacity of this network cannot be higher than .
And now we see what the problem is: bits must go across a cut of capacity . That is, even
optimal vector quantization strategies cannot compress the data enough so that the network can carry it?the network
Encoder
Decoder
Y
Fig. 4. Coding with side information.
does not scale up.1
A. Correlated Samples
The scaling analysis for independent encoders presented above ignores one fundamental aspect: increasing correlations
in sensor data as the density of nodes increases. And indeed, if the data is so highly correlated that all sensors
observe essentially the same value, at least intuitively it seems clear that almost no exchange of information at all
is needed for each node to know all other values: knowledge of the local sample and of the global statistics already
provide a fair amount of information about remote samples. And this naturally raises the question: are there other
coding strategies that can compress sensor data enough?
III. DEPENDENT ENCODERS
In [13], [20], [14] was ?rst introduced the idea that coding the sensors' data exploiting the correlation among the
samples can prevent network congestion. Speci?cally, in [13], [20], [14] the authors proposed to compress separately
the correlated samples at each node by mean of distributed source coding techniques. In this section we ?rst discuss
distributed source coding and then introduce the novel approach we propose, which consists in combining multi-hop
routing and data compression.
A. Distributed Source Coding
The idea of distributed source coding was ?rst introduced by Slepian and Wolf [18] who quanti?ed the number
of bits that are necessary to encode a source when the receiver has side information on the source (see Fig.4).
In the sensor network broadcast problem the measurements of the other sensors are themselves side information that
the receiver will have available [13], [20], [14]. Hence, each node can quantize the data considering that the side
information of the other samples will also be utilized by the decoder.
In [14], for the scenario that is described in Fig. III-A, it was shown that one can reduce the amount of bits per
node per square meter to an .
The result in [14] provides the ?rst theoretical evidence that coding techniques that exploit the dependence among
the sensors' samples are key to counteract the vanishing throughput of multi-hop networks. In fact, even if the transport
Capacity per node per square meter is vanishing so is the number of non-redundant bits that each node generates and,
furthermore, the latter is vanishing at a faster rate than the throughput is.
Techniques based on ?ows and cuts to analyze information theoretic capacity problems in networks have been proposed in [1],
[5, Ch. 14.10], In this context, those techniques provide an alternative interpretation for the Gupta/Kumar results [9].
Correlated N nodes
Sensors
Multi-Hop
Communication
Network N nodes
Central Control
Fig. 5. The sensor network setting in [14].
Even though multi-hop sensor networks appear to be the ?killer application? for distributed source coding there
are several reasons why the approach in [13], [20], [14] can be improved: 1) so far the theoretical evidence that
congestion can be avoided through distributed source coding is limited to a restrictive setting: in fact, the bounds in
[14] where derived for the situation described in Fig. 1 where the sensors are in a one dimensional space, and the relays
are in a two dimensional area which suggests that the nodes are physically separated, even if they are exactly in the
same ratio; 2) the approach of distributed source coding requires complex encoders to achieve signi?cant compression
gains. For example, the proof developed in [14] involves the use of codes for the problem of rate/distortion with side
information [5, Ch. 14.9] which are ef?cient when all codewords are nearly uniformly distributed and this is true for
highly correlated data only when the vector have large sizes. High-dimensional vector quantizers are not practical and
in short-block settings the gains obtained are in general less signi?cant. Last but not least: it is true that the encoding
is performed without sharing one single bit of data among the nodes. However, there is no real need to impose such
constraint. The separation of source-coding an routing in different layers of the communication system architecture
does not re?ect a physical separation of functionalities in the multi-hop sensor network setting of Fig. 1. After all, the
trademark of multi-hop networks is that power ef?cient transmission is achieved when the data travel through several
intermediate close-by nodes before reaching their ?nal destination. Hence, from the point of view of an engineer
engaged in the design of a practical sensor network this fact creates an opportunity for using simpler compression
techniques that cannot be missed. In fact, if the neighboring nodes are jointly compressing the data in their queues
before forwarding them remotely, when the network is dense and the ?eld is smooth, they can drastically reduce the
number of bits per sample while transmitting with the same or even greater precision. To accomplish this gain the
nodes can use a variety of techniques that are used to compress sequences with no need of resorting to highly complex
distributed source coding techniques. This is the truly novel and interesting aspect of our paper: the combination of
classical source coding methods and routing algorithms which, to the best of our knowledge, has not been explored by
other authors.
B. Routing and Source Coding
The scheme we propose is based on the idea described in Fig. Our idea is to use classical source codes as the
samples travel re-encoding jointly the data in the queues as they hop around the network, removing bits of information
that are redundant.
In general the th node will have to transmit to the th sensor a set of samples . If both the th and th node have
already received a set the encoder at the th node will need to pass to the encoder at the th node a number
Fig. 6. Routing and source coding.
of bits which is at least . This said, effectively designing the network ?ow using for every data ?ow the
rate/ditortion function lower bound becomes tedious, for it requires de?ning the level of distortion allowed for every
set of data exchanged which is a non-trivial function of the total distortion allowed .
A much simpler approach is to refer to the joint entropy of the samples which are discretized by quantizing them
?nely at every node with a quantizer with cell . The entropy induced on the codewords by quantization of the source
is denoted by . Because the shortest codeword length that represents uniquely a set of discrete data is equal
to the data entropy (see Appendix B) we can determine the number of bits transferred in every ?ow by using the joint
entropy of the data that ought to be transmitted; can be chosen so as to satisfy the global distortion constraint.
Obviously, this approach is suboptimal because the entropy of the quantized data is larger then the rate/distortion
function, since the rate/disortion function is by de?nition a lower bound on the number of bits necessary to represent
the data. However, as we will see in Section VI, in the worst case scenario, which is the case of Gaussian samples, the
entropy grows with the same scale as the rate/distortion function with respect to .
For now we can assume that the quantized samples are entropy-coded using an optimum vector quantizer, so that
for every ?ow we are transmitting the data using the shortest codeword length (see Appendix B) which is equal to
the data entropy. In practice, entropy coding is not a viable solution and there are a variety of alternatives that are
used in sequence compression available. In fact, contrary to the complicated vector quantizers required by distributed
source coding, when routing and source coding are combined the processing at each node can be done using any of
the standard compression technique which are used normally to compress sequences from analog sources (Predictive
Encoding, , Transform-Coding such as JPEG, etc. The dif?culty in applying such techniques only resides in
the dif?culty of implementing the algorithms in a distributed fashion, an interesting subject dealt with elsewhere [15],
[16].
In Section IV, we provide an example of possible network ?ow which is not by any mean optimized but yet
allows us to set up a study case where we can establish formally the condition under which the traf?c generated can be
transported by the network. The condition should be satis?ed by the data joint entropy (for the suboptimum
approach) or by the joint rate/distortion (when the ideal optimum quantization takes place). Then, in Section
V, we derive the asymptotic rate distortion function of the data and prove that, for a large class of sensors' data models,
the condition found is satis?ed in the limit as .
IV. TRANSPORT CAPACITY
Using simple network ?ow concepts, in Section I-A we argued that an upper bound on the transport capacity of a
network of size is . Our goal in this section is to construct one particular ?ow: from the amount of data
that this ?ow needs to push across the network, and from the upper bound on the capacity of the network, we derive a
constraint on the amount of data that the source can generate if it is to be broadcast over the whole network.
A. A Network Flow - The case of a Regular Grid
We consider ?rst the case of a regular grid, as it naturally precedes the construction for a general random grid. As
anticipated, we will construct our conditions on the network ?ow using the entropies of the quantized data .
We start with the case of four nodes and then generalize it to the entire network with a recursive algorithm. Two
examples (among many more possibilities) of transmission schemes are shown in Fig. 7.
(a) 1 (a) 1
(b) 2|1
(b) 2|1
(d) 3|1,2
(c) 1,2 (f) 1,2,3 (c) 1,2 (c) 1,2
(a) 3
(b) 4|3
Fig. 7. Consider a network with 4 nodes, each of which observes a variable ( ), with joint entropy
. Two possible ways of scheduling transmissions are shown. The notation used in the ?gure
is that (a) is the ?rst transmission, (b) the second, (c) the third, and so on; if two transmissions have the same letter
label, they can be performed in parallel; means that the sample of node is encoded when knowledge of the
sample of node is available. Using chain rules for entropies, we see that in the transmission schedule of the left
?gure we generate a total traf?c of , and it takes 8 time slots to complete. In the schedule of
the right ?gure, we generate more traf?c ( bits), but now we
only require 4 time slots to complete all transmissions.
We see from the examples in Fig. 7 that, at the expense of increased transmission delays, we can communicate
all samples to all nodes generating an amount of traf?c which is essentially the same as if one node had collected all
the samples and encoded them jointly, and then this information had been broadcast to all other nodes. Alternatively,
by sacri?cing some compression ef?ciency, it is also possible to incur in lower transmission delays. That is, there is
an inherent tradeoff between bandwidth use and decoding delay, and these two quantities are linked together by the
routing strategy employed.
For the entire network we can construct a ?ow recursively. For simplicity, assume , for some integer
. When , we have the trivial case of a network of size , in which all nodes (i.e., ) know the value
of all samples (i.e., ) without any transfer of information.
Consider now a partition of nodes into 4 groups: containing all the nodes in the upper-left corner of size
, nodes in the upper-right corner, lower-left, and lower-right. denotes the set of variables
observed by nodes in a set . This partition is illustrated in Fig. 8.
UL UR
Fig. 8. Partition of a network of size into four subnets.
We have that are all subnets of size , and so from our recursion we get that all
nodes within each subnet know the values of all quantized variables. But now, we have reduced our problem to the
problem with four nodes considered in Fig. 7, and we know that exchanging a total of
bits, in a total of 8 transmissions across cuts (plus transmissions to spread data within cuts), is enough to
ensure that every node in the network of size knows every quantized value. This construction is illustrated
in Fig. 9.
Fig. 9. Since each node on the boundary of a cut has knowledge of all samples within its subnet, each one of them
can encode all these samples jointly and send -th of this data across the cut. Then, in more
transmissions, all these pieces can be spread throughout the subnet to reach all nodes.
The idealized system, where all the data are quantized optimally without error propagation and with the minimum
number of bits necessary to represent the network samples, still must generate at least a total of bits of
traf?c, and still requires transmissions to complete the broadcast.
B. A Network Flow - The Case of a Random Grid
We next address the general case where the sensors are located in random positions, and in this case, the only
difference with the case of a regular grid as considered above is the fact that, in the random case, there is a non-zero
probability that in the recursive de?nition of the ?ow above, we may encounter an empty subnet. But in that case, only
trivial modi?cations can take care of this problem. The basic idea is that we can divide our network into squares of
area , and then with probability that tends to 1 as , we have that uniformly over all such squares,
the number of points falling into each square is [12, Ch. 2]. Therefore, in almost all networks with points,
the problem with a random grid is trivially reduced to the problem with a regular grid discussed above, plus a local
?ood within each square involving only about nodes. More details on the capacity of random networks are
presented in [11].
C. Constraints for network stability
We know the following facts:
Since , bits must go across the 4-way cut
de?ned by .
The capacity of the 4-way cut is .
Using the chain-rule we showed that we are capable of broadcasting all the data transferring
is the minimum amount of bits necessary to represent the same data (Appendix
B).
Therefore, the minimum requirement we need to satisfy is:
and, as we are going to show in the following sections, this requirement is satis?ed with probability one as ,
for the wide class of data models introduced in Section V.
V. A MODEL FOR SENSOR
In Section IV we saw that, by appropriate routing and re-encoding along routes, we can compress all the data
generated by the entire network down to . Our goal in this section is to verify that, for reasonable
models of sensor data, we have that eqn. (5) is satis?ed, so that the broadcast problem can be effectively solved.
To be able to talk about ?the rate/distortion function of the data generated by the entire network? we need a
model for this data. The main idea that we would like to capture in our models for sensor data is that, if this data
corresponds to measurements of a random process with some kind of regularity conditions, then these measurements
have to become increasingly correlated as the density of nodes becomes large. We propose to this end a fairly general
class of such models, under two assumptions: (a) the data are Gaussian random variables (b) the correlation among
samples is an arbitrary spatially homogeneous function; and (c), as we let the number of nodes in the network grow,
the correlation matrix converges to a smooth two-dimensional function.
Assumption (a) is a worse case scenario as far as compression is concerned, as a consequence of Theorem 4 in

Appendix

B. Spatial stationarity, even though not totally general is a technical assumption common to many statistical
analysis and captures well local properties of random processes.
A. Source Model
This section establishes the basic model upon which we will base our asymptotic analysis. Let denote the
random vector of the samples collected by the sensors at time . Our ?rst assumption is:
(c.I) , i.e. is a spatially correlated random Gaussian vector. The samples are temporally uncorrelated.
The samples are temporally independent if the power spectrum of is band-limited and the data are sampled at the
Nyquist rate. In any case, it is not a restrictive assumption and further gains in terms of compression could be obtained
exploiting the temporal dependence of the samples. Because of the temporal independence, we will focus on only one
vector of samples , and from now on we will drop the time index.
With the mean square error (MSE) as distortion measure and with the constraint
we can calculate under assumption (c.I) the rate/distortion function of the network using the reverse water-?lling
result [5]. Indicating by the ordered eigenvalues of , the rate/distortion function is
where
if
otherwise
and is such that
For , there exists an such that and , therefore:
and
The rate-distortion function is a function of the eigenvalues of only and is formed with the samples of the
continuous multivariate function that represents the correlation between the samples taken two arbitrary points in the
network:
The eigenvectors , with entries satisfy the following equation:
B. Asymptotic Eigenvalues' Distribution
Our derivations in the following try to capture the fact that the process cannot have in?nite spatial degrees of
freedom. The asymptotic rate-distortion function is obtained using the following two basic steps: 1) we prove that the
eigenvalues of the correlation matrix tend to the eigenvalues of the continuous integral equation:
we provide a model for the kernel of the continuous integral equation (13) which is bandlimited in the spatial
frequencies, and this allows us to obtain the asymptotic rate distortion bound.
As we said, the ?rst step is to rewrite (12) as a quadrature formula which approximate the integral equation (13).
For a general integral, there will be quadrature coef?cients such that the approximation of (13) holds:
Since we want to explore the convergence of the eigenvalues of (12) we can set in which case the ?rst
side (14) is equivalent to the right side of (12) normalized by . Therefore, when (14) is valid, the left sides of (12)
normalized by is approximately equal to the left side of (13) which leads to the following approximation:
The error in the approximation (14) determines the error in (15). The two errors are related by the following
theorem, derived from [10, Sec. 5.4]:
Lemma 1: Denoting by an arbitrary eigenvalue of (13) and by the corresponding normalized
eigenvector, for suf?ciently large there exist an eigenvalue of such that:
where denotes the quadrature error, i.e.:
Assuming that:
(c.II) For any continuous the grid is such that with the quadrature error ;
then (16) implies that:
Condition (c.II) in Lemma 1 is the operational condition on the distribution of the sensor nodes: the nodes should
be distributed in such a way that the quadrature error vanishes as .
There is another interesting and intuitively obvious consequence of Lemma 1 and (c.II), which is summarized in
the following corollary (it can be easily proved using the bounds in Lemma 1 and the triangular inequality):
Corollary 1: The eigenvalues of and corresponding to two different grids are such that
Hence, if (c.II) is satis?ed by both grids, and have the same eigenvalues asymptotically.
Corollary 1 implies that we can rely on any grid that has the same asymptotic behavior, such as for example a regular
lattice, and extrapolate the asymptotic behavior of the eigenvalues from the latter.
C. A tractable case
We assume that
(c.III) the correlation between points in (11) is spatially homogeneous:
The consequent structure of on a regular grid is also known as doubly Toeplitz, i.e.
with blocks that are Toeplitz themselves.
Assumption (c.III) implies that
The useful aspect of this model is that the empirical distribution of the eigenvalues of
sumptions to the 2-D Fourier Spectrum of (18), as we see next.
Under the assumption (c.III) we can de?ne:
is a block Toeplitz matrix
converges under mild as-
Adopting a regular grid covering the square of area , the spacing between them is
and like-wise . Szego?'s theorem [7] establishes that asymptotically the eigenvalues of a Toeplitz matrix converge
to the spectrum of the correlation function. Essentially, Szego?'s theorem establishes that the eigenfunctions of an
homogeneous kernel tend to be the Fourier basis of complex exponentials. The result can be generalized to the two
dimensional case when the matrix is doubly Toeplitz, i.e.:
Before proceeding, the ?nal modelling assumption is:
c.IV is bandlimited with respect to bandwidth , i.e. for .
With c.IV, we capture the notion that the limit covariance function varies smoothly in space.
D. Rate Distortion Function
The asymptotic rate-distortion function is obtained replacing the summations in (9) and (10) with integrals over
. Because the eigenvalues become asymptotically a continuous function, in (7) correspond to points
where crosses the threshold , i.e.
Let us denote the sets of points and where as , i.e.:
Let us also indicate as the set
The rate/distortion function is:
Because of c.IV the areas of both and are smaller than . Thus, we have the following lower bound on
(also illustrated in Fig. 10):
I
Fig. 10. One dimensional illustration of how the lower bound on from eqn. (27) is obtained by bounding the
integrals that de?ne in eqn. (25).
Together with c.IV, this justi?es the following upper-bound on the rate/distortion function:
So, we see that the total rate-distortion function over the entire network is , and because is
the average distortion per sample if that is kept ?xed, then the total amount of traf?c generated by the network is
upper bounded by a constant, irrespective of network size. Alternatively, if we keep the total distortion ?xed, by
considering increasingly large we let the average distortion . Even though the rate distortion function is
an asymptotic bound, the result is very signi?cant because we can observe that the amount of traf?c generated by the
entire network grows only logarithmically in , well below the capacity bound proved in eqn. (5).
VI. QUANTIZATION AND COMPRESSION
In Section IV we constructed an algorithm for the network ?ow which is based on the joint entropy of the samples
which are discretized by quantizing them at every nodes. The data ?les can be compressed using universal source
coding algorithms, such as Huffman coding or simpler suboptimal alternatives like Lempel-Ziv coding. Previously, in
Section III-B, we have argued that this approach is suboptimum but the growth of the entropy has the same behavior
of the rate/distortion function, which is what we prove next. High-resolution analysis shows that if are individually
quantized with an uniform quantizer with cell size their joint entropy is [6]:
where and is the joint differential entropy of the spatial samples, whose
de?nition is analogous to (4). For a Gaussian -dimensional multivariate process with full rank covariance matrix :
where is the determinant of the covariance matrix. Under conditions c.I through c.IV we have shown that
becomes singular as with an increasingly large null-space. For an -dimensional Gaussian process with a
singular covariance matrix having rank , the joint density of the samples can be expressed as the product
of the densities of an auxiliary set of independent Gaussian random variables with variance equal to the non-zero
eigenvalues of (also called principal components) whose number is equal to , and a set of Dirac
functions. Consequently, if we denote by the product of the non-zero eigenvalues and by the rank of
, the joint entropy of a Gaussian multivariate density can be in general written as:
It is not dif?cult to prove that the high resolution approximation for the general case is:
To determine the size of we can, in agreement with the high resolution analysis, consider the quantization
error as nearly independent from the signal and from sample to sample (which is a pessimistic assumption) and with
uniform distribution [6]. Thus, to have a total distortion in the order of the cell size has to be such that
. Therefore, . For , with arguments similar to those used to prove (28), we
can show that under c.IV , while . Hence, from (32) for
in other words also grows logarithmically with .
A. A simple compression strategy: down-sampling while routing
A simple-minded compression strategy that the nodes can implement is to down-sample appropriately the sensor
measurements as they are spread through the network. This simple strategy allows us the reach with some approximations
the same conclusion of our asymptotic analysis. In fact, even though a spatially bandlimited process requires
in?nite samples to be correctly reconstructed through interpolation, Nyquist theorem indicates that if condition c.II is
met, we can sample the ?eld with frequency in the and axis respectively. Because the network area is equal to
one, even if we over-sample to reduce the interpolation error at the borders, we need samples. In fact Nyquist
criterion strictly requires samples per unit area but border effects, due to the fact that the area is limited, and quantization
errors, which propagate when the missing data are interpolated, can be reduced by over-sampling. However,
the important conclusion is that number of samples does not grow with . On the other hand, if we constrain the total
distortion error to be , the average distortion per sample has to be . Let us assume that the variance of
each sample is : the interpolated samples will have distortion which is greater or equal to the distortion of the
non interpolated ones which implies that the non interpolated samples have to be quantized at a rate that is at least:
Therefore, the total amount of traf?c produced by the network will be in the order of:
q.e.d.
VII. NUMERICAL EXAMPLES
In this section we provide numerical evidence that validates our asymptotic claims.
The ?rst numerical example is aimed at corroborating Corollary 1. We assumed the area of the network is normalized
to one and that the function de?ned in (18) is:
where and it can be easily veri?ed that condition C.II is met. In ?g. 11 we show samples obtained
over the regular grid that are and in ?g. 12 we show the eigenvalues of the matrix , whose entries are
where in one case , are on a random grid (red line) and in the other case
they are on a regular lattice (blue line): we can observe that they are nearly identical in both cases and that the support
of the non zero eigenvalues does not grow with while their values increase proportionally to it. Finally, in ?g.0.5-0.5
Fig. 11. Samples where is de?ned in (38) obtained over the regular grid of sensors.300evd(R)150500 1 2 3
regular grid
random grid
eigenvalue index
Fig. 12. Eigenvalues of for various values of .
13 for the same covariance model in (38) and total distortion , we show the rate-distortion function calculated
numerically using the inverse water-?lling in (6). As expected, the growth is clearly logarithmic.
VIII. CONCLUSIONS
In recent work on the transport capacity of large-scale wireless networks, it has been established that the per-node
throughput of these networks vanishes as the number of nodes becomes large. This result poses a serious challenge
for the design of such networks; some have even argued that large networks are not feasible, precisely because of this
reason [9]. Previous work however pointed out that, in the context of sensor networks, the amount of information
Fig. 13. Rate distortion function for versus number of nodes in the network.
generated by each node is not a constant, but instead decays as the density of sensing nodes increases?this was
illustrated with an example based on the transmission of samples of a Brownian process, with arbitrarily low distortion
(even with vanishing per-node throughput), by means of using distributed source coding techniques [14].
In this work we have shown an alternative approach to work around the vanishing per-node throughput constraints
of [9]. This new approach is not based on distributed coding techniques, but instead is based on the use of classical
source codes combined with suitable routing algorithms and re-encoding of data at intermediate relay nodes. To the
best of our knowledge, these are the ?rst results in which interdependencies between routing and data compression
problems are captured in a system model that is also analytically tractable. And a key (and enabling) step in our
derivation was the construction of a family of spatial processes satisfying some fairly mild (and easily justi?able from
a physical point of view) regularity conditions, for which we were able to show that the amount of data generated
by the sensor network is well below its transport capacity. This provides further evidence that large-scale multi-hop
sensor networks are perfectly feasible, even under the network model considered in [9].


I. ENTROPY AND CODING
The entropy of a random variable with probability mass function is de?ned as:
For multivariate random variables the generalization is straightforward:
Note also that, the entropy of a vector can be decomposed according to the so called chain rule, resulting from the
iterated application of the chain rule for probability :
which was used in Figure 7. The importance of the de?nition of entropy lies in the fact that it provides a very accurate
answer to the following question regarding discrete data sources (i.e. sources producing symbols drawn form a discrete
What is the minimum number of bits necessary to represent the data from a discrete source so that they can be
reconstructed without distortion?
The answer is given by the the following theorem [5, Ch.5]:
Theorem 1: The expected length of any instantaneous D-ary code for a random variable is:
The proof of the theorem is based on the existence of a coding technique, Huffman coding, is known to achieve
the entropy within one bit if one symbol is encoded and, if multiple symbols are encoded together, the ef?ciency of
Huffman coding tends to be 100% [5]. This theory cannot be directly generalized to handle the case of analog sources
because their entropy is in?nite even if the signal is a discrete-time sequence. In fact, the source signal can take any
real value so that each sample still requires in?nite precision to be represented exactly. However, once a certain level
of distortion is accepted, the minimum number of bits necessary to represent the source can be calculated just as
rigorously as in the case of discrete sources, resorting to the parallel theory for analog sources which is called Rate
Distortion Theory.
II. RATE DISTORTION THEORY IN A NUTSHELL
Rate Distortion is based on the seminal contribution of Claude Shannon who tried to provided a theoretical frame-work
for the representation of a continuous source through discrete symbols [17].
Suppose a memoryless continuous source produces a random sample with density : the quantization problem
boils down to representing through discrete values so that, if our measure of the distortion is , our
mapping is such that .
To quantify how many bits are needed to represent , in his 1959 paper Shannon de?ned the so called rate
distortion function:
where:
is the average mutual information between and . In the same paper he proved the following two fundamental
theorems:
Theorem 2: The minimum information rate necessary to represent the output of a discrete-time, continuous-
amplitude memoryless Gaussian source with variance based on a mean-square distortion measure per symbol
(single letter distortion measure) is:
if
Theorem 3: There exists an encoding scheme that maps the source output into code words such that for any given
distortion , the minimum rate bits per symbol (sample) is suf?cient to reconstruct the source output with an
average distortion that is arbitrarily close to .
The implication of the two theorems above is that is the minimum number of bits that can represent within the
prescribed mean-square error if the source is Gaussian. In other words any discrete code that represents a Gaussian
source with a mean-quare distortion has
and the lower bound is asymptotically achievable. The following important theorem, proven by Berger in 1971 [2],
generalizes the results by Shannon:
Theorem 4: The rate-distortion function of a memoryless, continuous -amplitude source with zero mean and ?nite
variance with respect to the mean-square-error distortion measure is upper-bounded as:
Berger's theorem implies that the Gaussian source is the one the requires the maximum encoding rate, if the distortion
function is the MSE. Hence, if our distortion metric is the mean-square error, the case of a Gaussian source has to be
seen as a worse case scenario.
The theorems above have been extended to multivariate sources which are analogous to the ones we consider in
this paper. In particular, the so called inverse water-?lling result used in Section V is the direct generalization of
Theorem 2 to the multivariate Gaussian source.


--R

Network Information Flow.
Rate distortion Theory
Sphere Packings
Introduction to Algorithms.
Elements of Information Theory.
Vector Quantization and Signal Compression.

Critical Power for Asymptotic Connectivity in Wireless Networks.
The Capacity of Wireless Networks.

On the Maximum Stable Throughput Problem in Random Networks.
Convergence of Stochastic Processes.
Distributed Source Coding: Symmetric Rates and Applications to Sensor Networks.
Lattice Quantization with Side Information.
Distributed Signal Processing Algorithms for the Sensor Broadcast Problem.
Sensing Lena?
Coding Theorems for a Discrete Source With a Fidelity Criterion Institute of Radio Engineers
Noiseless coding of correlated information sources.
Multiple Description Vector Quantization with Lattice Codebooks: Design and Analysis.
Optimal Code Design for Lossless and Near Lossless Source Coding in Multiple Access Networks.
--TR
Introduction to algorithms
Vector quantization and signal compression
Elements of information theory
Distributed Source Coding
Lattice Quantization with Side Information
Optimal Code Design for Lossless and Near Lossless Source Coding in Multiple Access Networks

--CTR
Animesh Kumar , Prakash Ishwar , Kannan Ramchandran, On distributed sampling of smooth non-bandlimited fields, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Tamer ElBatt, On the scalability of hierarchical cooperation for dense sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Bharath Ananthasubramaniam , Upamanyu Madhow, Virtual radar imaging for sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Yaron Rachlin , Rohit Negi , Pradeep Khosla, Sensing capacity for discrete sensor network applications, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
G. Barriac , R. Mudumbai , U. Madhow, Distributed beamforming for information transfer in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
Abhinav Kamra , Vishal Misra , Jon Feldman , Dan Rubenstein, Growth codes: maximizing sensor network data persistence, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
Huiyu Luo , Gregory J. Pottie, Designing routes for source coding with explicit side information in sensor networks, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1401-1413, December 2007
Mihaela Enachescu , Ashish Goel , Ramesh Govindan , Rajeev Motwani, Scale-free aggregation in sensor networks, Theoretical Computer Science, v.344 n.1, p.15-29, 11 November 2005
An-swol Hu , Sergio D. Servetto, Asymptotically optimal time synchronization in dense sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA
Bhaskar Krishnamachari , Fernando Ordez, Fundamental limits of networked sensing: the flow optimization framework, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
Alexandre Ciancio , Sundeep Pattem , Antonio Ortega , Bhaskar Krishnamachari, Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
Hong Luo , Jun Luo , Yonghe Liu, Energy efficient routing with adaptive data fusion in sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
Christina Peraki , Sergio D. Servetto, On the maximum stable throughput problem in random networks with directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA
Mehmet C. Vuran , Ian F. Akyildiz, Spatial correlation-based collaborative medium access control in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.316-329, April 2006
Mehmet C. Vuran , zgr B. Akan , Ian F. Akyildiz, Spatio-temporal correlation: theory and applications for wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.3, p.245-259, 21 June 2004
Xun Su, A combinatorial algorithmic approach to energy efficient information collection in wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.3 n.1, p.6-es, March 2007
Micah Adler, Collecting correlated information from a sensor network, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Qun Li , Michael De Rosa , Daniela Rus, Distributed algorithms for guiding navigation across a sensor network, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Alexandra Meliou , David Chu , Joseph Hellerstein , Carlos Guestrin , Wei Hong, Data gathering tours in sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
Tarik Arici , Toygar Akgun , Yucel Altunbasak, A prediction error-based hypothesis testing method for sensor data acquisition, ACM Transactions on Sensor Networks (TOSN), v.2 n.4, p.529-556, November 2006
Himanshu Gupta , Vishnu Navda , Samir R. Das , Vishal Chowdhary, Efficient gathering of correlated data in sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
Razvan Cristescu , Baltasar Beferull-Lozano , Martin Vetterli , Roger Wattenhofer, Network correlated data gathering with explicit communication: NP-completeness and algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.41-54, February 2006
Sergio D. Servetto , Guillermo Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA
Christopher M. Sadler , Margaret Martonosi, Data compression algorithms for energy-constrained devices in delay tolerant networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA
Kai-Wei Fan , Sha Liu , Prasun Sinha, Scalable data aggregation for dynamic events in sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA
J. A. Paradiso , J. Lifton , M. Broxton, Sensate Media  Multimodal Electronic Skins as Dense Sensor Networks, BT Technology Journal, v.22 n.4, p.32-44, October 2004
routing;sensor networks;cross-layer interactions;multi-hop networks;source coding