{'fraction_non_alphanumeric': 0.038572312041699794, 'fraction_numerical': 0.01003622228112024, 'mean_word_length': 4.0859094176851185, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Minimum cost distributed source coding over a network

This work considers the problem of transmitting multiple compressible sources over a network at minimum cost. The aim is to find the optimal rates at which the sources should be compressed and the network flows using which they should be transmitted so that the cost of the transmission is minimal. We consider networks with capacity constraints and linear cost functions. The problem is complicated by the fact that the description of the feasible rate region of distributed source coding problems typically has a number of constraints that is exponential in the number of sources. This renders general purpose solvers inefficient. We present a framework in which these problems can be solved efficiently by exploiting the structure of the feasible rate regions coupled with dual decomposition and optimization techniques such as the subgradient method and the proximal bundle method.


I. INTRODUCTION
In recent years the emergence of sensor networks [1] as a new paradigm has introduced a number of issues that did not exist earlier. Sensor networks have been considered among other things by the military for battlefields, by ecologists for habitat monitoring and even for extreme event warning systems. These networks consist of tiny, low-power nodes that are typically energy constrained. In general, they also have low-computing power. Thus, designing efficient sensor networks requires us to address engineering challenges that are significantly different from the ones encountered in networks such as the Internet. One unique characteristic of sensor networks is that the data that is sensed by different sensor nodes and relayed to a terminal is typically highly correlated. As an example consider a sensor network deployed to monitor the temperature or humidity levels in a forest. The temperature is not expected to vary significantly over a small area. Therefore we do expect that the readings corresponding to nearby sensors are quite correlated. It is well-known that the energy consumed in transmission by a sensor is quite substantial and therefore efficient low power methods to transfer the data across the network are of interest. This leads us to investigate efficient techniques for exploiting the correlation of the data while transmitting it across the network. There are multiple ways in which the correlation can be exploited.
a) The sensor nodes can communicate amongst themselves to inform each other of the similarity of their data Aditya Ramamoorthy is with the Department of Electrical and Computer Engineering, Iowa State University, Ames IA 50011, USA (email: adit-yar@iastate.edu). The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Nice, France June 2007 and then transmit only as much data as is required. This comes at the cost of the overhead of inter-sensor communication.
b) The sensors can choose to act independently and still attempt to transmit the compressed data. This strategy is likely to be more complicated from the receiver's point of view. Usually the terminal to which the data is transmitted has significantly more resources (energy, computing power etc.). Thus, the latter solution is more attractive from a network resource efficiency point of view. The question of whether the distributed compression of correlated sources can be as efficient as their compression when the sources communicate with each other was first considered and answered in the affirmative by Slepian and Wolf in their famous paper [2]. A number of authors [3] [4] have investigated the construction of coding techniques that achieve the Slepian-Wolf bounds and also proposed their usage in sensor networks [5].
New paradigms have also emerged recently in the area of network information transfer. Traditionally information transfer over networks has been considered via routing. Data packets from a source node are allowed to be replicated and forwarded by the intermediate nodes so that terminal nodes can satisfy their demands. However, network coding offers an interesting alternative where intermediate nodes in a network have the ability to forward functions of incoming packets rather than copies of the packets. The seminal work of Ahlswede et al. [6] showed that network coding achieves the capacity of single-source multiple-terminal multicast where all the terminals are interested in receiving the same set of messages from the source. This was followed by a number of works that presented constructions and bounds for multicast network codes [7] [8]. More recently, there has been work [9][10] on characterizing rate regions for arbitrary network connections where the demands of the terminals can be arbitrary.
Given these developments in two different fields, a natural question to ask is how can one transmit compressible sources over a network using network coding and whether this can be done efficiently. This problem was considered by Song and Yeung [11] and Ho et al. [12]. They showed that as long as the minimum cuts between all nonempty subsets of sources and a particular terminal were sufficiently large, random linear network coding over the network followed by appropriate decoding at the terminals achieves the Slepian-Wolf bounds. The work of Ramamoorthy et al. [13] investigated the performance of separate source and network codes and showed that separation does not hold in general. Both these papers only considered capacity constraints on the edges of the network and did not impose any cost associated with edge usage.
In the networking context the problem of minimum cost network flow has been widely investigated. Here, every edge in the network has a cost per unit flow associated with it. The cost of a given routing solution is the sum of the costs incurred over all the links. The problem is one of finding network flows such that the demand of the terminals is satisfied at minimum cost. This problem has been very well investigated in the routing context [14]. The problem of minimum cost multicast using network coding was considered by Lun et al. [15] and they presented centralized and distributed solutions to it.
In this paper we consider the problem of minimum cost joint rate and flow allocation over a network that is utilized for communicating compressible sources. We consider the scenario when the compression is to be performed in a distributed manner. The sources are not allowed to communicate with each other. The main issue with joint rate and flow allocation is that typically the feasible rate region for the recovery of the sources (e.g. the Slepian-Wolf region) is described by a number of inequalities that is exponential in the number of sources. Thus, using a regular LP solver for solving the corresponding linear programming problem will be inefficient. In our work, we only consider networks where the links are independent and where transmission up to the link's capacity is assumed to be error free. In general, the capacity region characterization of more complex networks such as wireless networks will need to take account issues such as interference. Moreover, it would introduce related issues such as scheduling. We do not consider these problems in this work.

A. Main Contributions
The main contributions of this paper are as follows. We present a framework in which minimum cost problems that involve transmitting compressible sources over a network in a distributed manner can be solved efficiently. We consider general linear cost functions, allow capacity constraints on the edges of the network and consider the usage of network coding. The following problems are considered. a) Slepian-Wolf over a network. The sources are assumed to be discrete and memoryless and they need to be recovered losslessly [2] at the terminals of the network. We address the problem of jointly finding the operating rate vectors for the sources and the corresponding network flows that allow lossless recovery at the terminals at minimum cost. b) Quadratic Gaussian CEO over a network. A Gaussian source is observed by many noisy sensors and needs to be recovered at the terminal subject to a quadratic distortion constraint [16]. We present a solution to the problem of joint rate and network flow allocation that allows recovery at the terminal at minimum cost. c) Lifetime maximization of sensor networks with distortion constraints. A Gaussian source observed by many noisy sensors needs to be recovered at the terminal with a certain fidelity. We are interested in finding routing flows that would maximize the lifetime of the network. We demonstrate that these problems can be solved efficiently by exploiting the structure of the feasible rate regions coupled with dual decomposition techniques and subgradient methods [17].

B. Related Work
Problems of a similar flavor have been examined in several papers. Cristescu et al. considered the Networked Slepian-Wolf problem [18] and the case of lossy correlated data gathering over a network [19], but did not impose capacity constraints on the edges. Their solutions only considered very specific types of cost functions. The work of Li & Ramamoorthy [20], [21] and Roumy & Gesbert [22] considered a rate allocation under pairwise constraints on the distributed source code used for compression. The work of Liu et al. [23] and [24] considers a related problem, where they seek to minimize the total communication cost of a wireless sensor network with a single sink. They show that when the link communication costs are convex, then the usage of Slepian-Wolf coding and commodity flow routing is optimal. Moreover, they introduce the notion of distance entropy, and show that under certain situations the distance entropy is the minimum cost achieved by Slepian-Wolf coding and shortest path routing. They also propose hierarchical transmission schemes that exploit correlation among neighboring sensor nodes, and do not require global knowledge of the correlation structure. These schemes are shown to be order-optimal in specific situations. The main difference between our work and theirs, is the fact that we consider network coding and networks with multiple terminals. Moreover, in the case of general convex link cost functions, their focus is on showing that Slepian-Wolf coding and commodity flow routing is optimal. They do not consider the problem of actually finding the optimal flows and rates.
A problem formulation similar to ours was introduced by Barros et al. [25] but they did not present an efficient solution to it. The problem of exponentially many constraints has been noted by other authors as well [26] [27].
The approach in our work is inspired by the work of Yu et al. [28]. However since our cost functions only penalize the usage of links in the network, we are effectively able to exploit the structure of the feasible rate region to make our overall solution efficient. In addition we explicitly derive the dual function and the corresponding update equations for maximizing it based on the specific structure of the rate region. Furthermore, we consider applications in network coding and lifetime maximization in sensor networks that have not been considered previously. In concurrent and independent work [29] presented some approaches similar to ours (see also [30], where the case of two sources is discussed). However our approach has been applied to the minimum cost quadratic Gaussian CEO problem over a network and lifetime maximization with distortion constraints that were not considered in [29].
A reviewer has pointed out that the problem of generalizing the Slepian-Wolf theorem to the network case was first considered by Han [31] in 1980. However, in [31] only networks with a single terminal were considered. In the single terminal case the corresponding flows can be supported by pure routing. Interestingly, in the same paper, Han references the work of Fujishige [32] that studies the optimal independent flow problem (this was also pointed by the same reviewer). Fujishige's work considers a network flow problem that has polymatroidal [33] constraints for the source values and the terminal values. In particular, if there is only one terminal, then this algorithm provides an efficient solution to the minimum cost Slepian-Wolf problem over a network. However, it is unclear whether it can be extended to the case of multiple terminals and network coding. We discuss Fujishige's work in more detail in Section III, after the precise problem has been formulated.
This paper is organized as follows. Section II overviews the notation and the broad setup under consideration in this paper. Section III formulates and solves the minimum cost Slepian-Wolf problem over a network, Section IV discusses the quadratic Gaussian CEO problem over a network and Section V presents and solves the problem of lifetime maximization of sensor networks when the source needs to be recovered under distortion constraints. Each of these sections also present simulation results that demonstrate the effectiveness of our method. Section VI discusses the conclusions and future work.

II. PRELIMINARIES
In this section we introduce the basic problem setup that shall be used in the rest of this paper. In subsequent sections we shall be presenting efficient algorithms for solving three different problems that fall under the umbrella of distributed source coding problems over a network. We shall present the exact formulation of the specific problem within those sections. We are given the following. a) A directed acyclic graph G = (V, E, C) that represents the network. Here V represents the set of vertices, E the set of edges and C ij , (i, j) ∈ E is the capacity of the edge (i, j) in bits/transmission. The edges are assumed to be error-free and the capacity of the edges is assumed to be rational. We are also given a set of source nodes S ⊆ V where |S| = N S and a set of terminal nodes T ⊆ V where |T | = N R . Without loss of generality we assume that the vertices are numbered so that the vertices 1, 2, . . . , N S correspond to the source nodes. b) A set of sources X 1 , X 2 , . . . X NS , such that the i th source is observed at source node i ∈ S. The values of the sources are drawn from some joint distribution and can be either continuous or discrete. Based on these we can define the capacity region of the terminal T j ∈ T with respect to S as Thus, C Tj consists of inequalities that define the maximum flow (or minimum cut) from each subset of S to the terminal T j . A rate vector (R 1 , . . . , R NS ) ∈ C Tj can be transmitted from the source nodes 1, . . . , N S to terminal T j via routing [14]. In the subsequent sections we shall consider different minimum cost problems involving the transmission of the sources over the network to the terminals.

III. MINIMUM COST SLEPIAN-WOLF OVER A NETWORK
Under this model, the sources are discrete and memoryless and their values are drawn i.i.d. from a joint distribution p(x 1 , . . . , x NS ). The i th source node only observes X i for i ∈ S. The different source nodes operate independently and are not allowed to communicate. The source nodes want to transmit enough information using the network to the terminals so that they can recover the original sources, losslessly.
This problem was first investigated in the seminal paper of Slepian and Wolf [2] where they considered the sources to be connected to the terminal by a direct link and the links did not have capacity constraints. The celebrated result of [2] states that the independent source coding of the sources X i , i = 1, . . . , N S can be as efficient as joint coding when the sources need to be recovered error-free at the terminal.
Suppose that for the classical Slepian-Wolf problem, the rate of the i th source is R i . Let X B denote the vector of sources (X i1 , X i2 , . . . , X i |B| ), for i k ∈ B, k = 1, . . . , |B|. The feasible rate region for this problem is given by The work of Csiszár [34] showed that linear codes are sufficient to approach the Slepian-Wolf (henceforth S-W) bounds arbitrarily closely.
Note that the original S-W problem does not consider the sources to be communicating with the terminal (or more generally multiple terminals) over a network. Furthermore, there are no capacity constraints on the edges connecting the sources and the terminal. In situations such as sensor networks, where the sensor nodes are typically energy-constrained, we would expect the source nodes to be in communication with the terminal node over a network that is both capacity and cost-limited. Capacity constraints may be relatively strict since a significant amount of power is consumed in transmissions. The costs of using different links could be used to ensure that a certain part of the network is not overused resulting in nonuniform depletion of resources. Thus the problem of transmitting correlated data over a network with capacity constraints at minimum cost is of interest. We define an instance of the S-W problem over a network by P =< R SW , G, S, T >.
The transmission schemes based on linear codes (such as those in [34]) are based on block-wise coding, i.e., each source encodes N source symbols at a time. An edge with capacity C ij bits/transmission can transmit ⌊N C ij ⌋ bits per block. Conceptually, each edge can be regarded as multiple unit capacity edges, with each unit capacity edge capable of transmitting one bit per block. When communicating a block of length N , we consider the graph G N = (V, E, ⌊N C⌋), or equivalently the graph (V, E N , ½) (where ½ denotes a vector of ones) where E N splits each edge from E into unit capacity edges.
To facilitate the problem formulation we construct an augmented graph G * where we append a virtual super source node s * to G, so that We let G * = (V * , E * , C * ). Definition 1: Feasibility. Consider an instance of the S-W problem over a network, P =< R SW , G, S, T >. Let C Ti be the capacity region of each receiver T i ∈ T with respect to S. If then the feasibility condition is said to be satisfied and P is said to be feasible. The next theorem (from [12]) implies that as long as the feasibility condition is satisfied, random linear network coding over G N followed by appropriate decoding at T i suffices to reconstruct the sources X 1 , X 2 , . . . , X NS error-free at T i .
Theorem 1: Sufficiency of the feasibility condition [12]. Consider an instance of the S-W problem over a network, P =< R SW , G, S, T >. If the feasibility condition (Definition 1) is satisfied, then random linear network coding over G N followed by minimum-entropy [34] or maximum-likelihood decoding can recover the sources at each terminal in T with the probability of decoding error going to 0 as N → ∞. The proof of the necessity of the feasibility condition can be found in [31].
It follows that if C Ti ∩ R SW = φ for all T i ∈ T , it is sufficient to perform random linear network coding over a subgraph of G where the feasibility condition continues to be satisfied. The question then becomes, how do we choose appropriate subgraphs?
For this purpose, we now present the formulation of the minimum cost S-W problem over a network. Let ij , represents the virtual flow variable over edge (i, j) for terminal T k [15].
We introduce variables R . . , N S that represent the operating S-W rate variables for each terminal. Thus the cost for transmitting at a unit flow over edge (i, j). We are interested in the following optimization problem that we call MIN-COST-SW-NETWORK.
The constraints in (1), (2) and (5) are precisely the formulation of the minimum cost single-source multiple terminal multicast with network coding for a total rate of H(X 1 , X 2 , . . . , X NS ). The constraint (3) enforces the flow x . Constraint (4) ensures that the rate vectors R (T k ) belong to the Slepian-Wolf region R SW . A proof that the total rate can be fixed to be exactly H(X 1 , X 2 , . . . , X NS ) for each terminal can be found in Appendix-I.
Suppose there exists a feasible solution z, ( We define the subgraph of G * induced by z to be the graph G * z = (V * z , E * z , C * z ) and the corresponding graph over block length N as G * N z = (V * z , E * z N , ½). The subgraphs induced by x (T k ) can be defined analogously. We now show that if MIN-COST-SW-NETWORK is feasible then the subgraph induced by the feasible z continues to satisfy the condition in definition 1 and therefore it suffices to perform random linear network coding over this subgraph followed by appropriate decoding at the terminals to recover the sources.
Lemma 1: Suppose that there exists a feasible solution z, Then, random linear network coding over the subgraph G * N z induced by z followed by maximum likelihood decoding at the terminals can recover the sources X i , i ∈ S at each terminal in T as N → ∞.
Proof: To simplify the presentation we assume that all C ij , (i, j) ∈ E * and H(X B /X B c ), B ⊆ S are rational and the block length N is large enough so that N C ij and Consider a terminal T 1 ∈ T . We are given the existence of a feasible solution (z, x, R) from which we can find the corresponding flow for T 1 denoted by x (T1) . Now consider the subgraph of G * N induced by x (T1) . Since x (T1) is feasible, it supports a rate of N H(X 1 , X 2 , . . . , X NS ) from s * to T 1 which implies (using Menger's theorem [35] This means that there exist at least N H(X B |X B c ) edgedisjoint paths from B to T 1 in the subgraph induced by T 1 which in turn implies that min-cut(B, . This holds for all T k ∈ T , as we have a feasible x (T k ) for all the terminals. Finally z induces a subgraph where this property continues to hold true for each terminal since x for all sufficiently large N . Using Theorem 1 we have the required proof.
The formulation of MIN-COST-SW-NETWORK as presented above is a linear program and can potentially be solved by a regular LP solver. However the number of constraints due to the requirement that R ∈ R SW is |T |(2 NS −1) that grows exponentially with the number of sources. For regular LP solvers the time complexity scales with the number of constraints and variables. Thus, using a regular LP solver is certainly not time-efficient. Moreover even storing the constraints consumes exponential space and thus using a regular LP solver would also be space-inefficient. In the sequel we present efficient techniques for solving this problem.

A. Solving MIN-COST-SW-NETWORK via dual decomposition
Suppose that we are given an instance of the S-W problem over a network specified by P =< R SW , G, S, T >. We assume that P is feasible. The MIN-COST-SW-NETWORK optimization problem is a linear program and therefore feasibility implies that strong duality holds [36].
We shall refer to the variables z, x (T k ) , R (T k ) for T k ∈ T as the primal variables. To simplify notation we let x s * NS ] T denote the vector of flow variables corresponding to terminal T k on the edges from the virtual super node s * to the source nodes in S. We form the Lagrangian of the optimization problem with respect to the constraints R For a given λ, let g(λ) denote the dual function obtained by minimizing L(λ, z, x (T1) , . . . , x (TN R ) , R (T1) , . . . , R (TN R ) ) over z, x (T1) , . . . , x (TN R ) , R (T1) , . . . , R (TN R ) . Since strong duality holds in our problem we are guaranteed that the optimal value of MIN-COST-SW-NETWORK can be equivalently found by maximizing g(λ) subject to λ 0 [36]. Thus, if g(λ) can be determined in an efficient manner for a given λ then we can hope to solve MIN-COST-SW-NETWORK efficiently.
Consider the optimization problem for a given λ 0.
We realize on inspection that this minimization decomposes into a set of independent subproblems shown below.
and for each T k ∈ T , The optimization problem in (6) is a linear program with variables z and x (T k ) for k = 1, . . . , N R and a total of (2|T |+ 1)|E * | + |T ||V * | constraints that can be solved efficiently by using a regular LP solver. It can also be solved by treating it as a minimum cost network flow problem with fixed rates for which many efficient techniques have been developed [14].
However each of the subproblems in (7) still has 2 NS − 1 constraints and therefore the complexity of using an LP solver is still exponential in N S . However using the supermodularity property of the conditional entropy function H(X B |X c B ), it can be shown that R SW is a contra-polymatroid with rank function H(X B |X B c ) [37]. In addition, the form of the objective function is also linear. It follows that the solution to this problem can be found by a greedy allocation of the rates as shown in [33]. We proceed as follows.

2) Set
The previous algorithm presents us a technique for finding the value of g(λ) efficiently. It remains to solve the maximization max For this purpose we use the fact that the dual function is concave (possibly non-differentiable) and can therefore be maximized by using the projected subgradient algorithm [17]. The subgradient for λ k can be found as . Let λ i represent the value of the dual variable λ at the i th iteration and θ i be the step size at the i th iteration. A step by step algorithm to solve MIN-COST-SW-NETWORK is presented below.
using an LP solver and for each T k ∈ T , using the greedy algorithm presented in (8).
Goto step 2 and repeat until convergence. While subgradient optimization provides a good approximation on the optimal value of the primal problem, a primal optimal solution or even a feasible, near-optimal solution is usually not available. In our problem, we seek to jointly find the flows and the rate allocations that support the recovery of the sources at the terminals at minimum cost. Thus, finding the appropriate flows and rates specified by the primal-optimal or near primal-optimal z, x (T1) , . . . , x (TN R ) , R (T1) , . . . , R (TN R ) is important. Towards this end we use the method of Sherali and Choi [38].
We now briefly outline the primal recovery procedure of [38]. Let µ k j for j = 1, . . . , k be a set of convex combination weights for each k ≥ 1. This means that k j=1 µ k j = 1, and µ k j ≥ 0.
Let the primal solution returned by subgradient optimization at iteration k be denoted by the vector (z, x, R) k and let the k th primal iterate be defined as Suppose that the sequence of weights µ k j for k ≥ 1 and the sequence of step sizes θ k , k ≥ 1 are chosen such that 1) γ jk ≥ γ (j−1)k for all j = 2, . . . , k for each k.
Then an optimal solution to the primal problem can be obtained from any accumulation point of the sequence of primal iterates {(z,x,R)}. Some useful choices for the step sizes θ k and the convex combination weights µ k j that satisfy these conditions are given below (see [38]). 1) θ k = a/(b + ck), for k ≥ 1 where a > 0, b ≥ 0, and c ≥ 0 and µ k j = 1/k for all j = 1, . . . , k. 2) θ k = k −α , for k ≥ 1 where 0 < α < 1 and µ k j = 1/k for all j = 1, . . . , k. The strategy for obtaining a near-optimal primal solution for the MIN-COST-SW-NETWORK problem is now quite clear. We run the subgradient algorithm in the manner outlined above and keep computing the sequence of primal iterates {(z,x,R)} k≥1 and stop when the primal iterates have converged.

B. Results
In this section we present results on the performance of our proposed algorithm. We generated graphs at random by choosing the position of the nodes uniformly at randomly from the unit square. Two nodes were connected with an edge of capacity 40.0 if they were within a distance of 0.3 √ 2 of each other and were connected with an edge of capacity 20.0 if they were within a distance of 0.3 of each other. The orientation of the edges is from left to right. A certain number of nodes were declared to be sources, a certain number to be terminals and the remaining nodes were used for relaying.
Let the random vector at the sources be denoted by Z = (Z 1 , Z 2 , . . . , Z NS ). As in [39], a jointly Gaussian model was assumed for the data sensed at the sources. Thus the pdf of the observations is assumed to be where C ZZ is the covariance of the observations. We assumed a correlation model where C ZZ (i, i) = σ 2 i and C ZZ (i, j) = σ 2 exp(−cd β ij ) when i = j (where c and β are positive constants and d ij is the distance between nodes i and j). It is further assumed that the samples are quantized independently at all source nodes with the same quantization step ∆ that is sufficiently small. Under these conditions, the quantized random vector X = (X 1 , X 2 , . . . , X NS ) is such that as shown in [40] where H(X) represents the entropy of X and h(Z) = 1 2 log(2πe) NS det(C ZZ ) represents the differential entropy of Z. We can also express the conditional entropy We used these conditional entropies for the Slepian-Wolf region of the sources. Figure 1(a) shows a network consisting of 50 nodes, with 10 source nodes, 37 relay nodes and 3 terminals. We chose σ 2 = 1, c = 1 and β = 1 for this example. The quantization step size was chosen to be ∆ = 0.01. The cost of all the edges in the graph was set to 1.0.
For the subgradient algorithm, we chose µ k j = 1/k for all j, k and the step size θ k = 8/k 0.8 . The averaging process ignored the first 50 primal solution due to their poor quality. We observe a gradual convergence of the cost of our solution to the optimal in Fig. 1(b).
1) Remark 1: If one uses a regular LP solver to solve the M IN − COST − SW − N ET W ORK problem, as noted above, the complexity would scale with the number of variables and constraints, that grow exponentially with the number of sources. However, one is guaranteed that the LP solver will terminate in a finite number of steps eventually. Our proposed algorithm uses the subgradient method with step sizes such that the recovered solution will converge to the optimal as the number of iterations go to infinity [17].
In general, it does not seem possible to claim convergence in a finite number of steps for this method. A discussion around convergence issues of the subgradient method can be found in Chap. 6 of [17]. We point out that in practice, we found the algorithms to converge well. Note also that even the description of the LP requires space that increases very quickly, therefore using the LP formulation becomes impractical even with a moderate number of sources.

C. Discussion about Fujishige's algorithm
We now discuss the work of Fujishige [32]. Towards this end we need to define the following quantities. A polymatroid P is defined as a pair (A, ρ) where A is a finite set and ρ is a function from 2 A to the positive reals, R + , that satisfies the axioms of a rank function. A vector α ∈ R |A| + , with entries indexed by the elements of A is called an independent vector of P (A, ρ) if e∈B α(e) ≤ ρ(B), for all B ⊆ A.
Suppose that we have a directed graph G = (V, E, C), with linear costs f ij , ∀(i, j) ∈ E, (as defined above) with two vertex subsets V 1 (source nodes) and V 2 (terminal nodes). Suppose that for each V i , i = 1, 2, a polymatroid P i (V i , ρ i ) is defined. An independent flow is a triple (α, δ, β), such that: (i) α is an independent vector of P 1 and is the vector of flows entering the network at the source nodes, (ii) β is an independent vector of P 2 and is the vector of flows absorbed at the terminal nodes, and (iii) δ is a flow vector such that flow balance is satisfied at each node in G. The algorithm in [32], returns an independent flow of maximum value, whose cost f T δ is minimum.
In the case of a single terminal, this algorithm can be used to solve the M IN − COST − SW − N ET W ORK problem (as noted in [31]) as follows. The set of source nodes and the conditional entropy function, specify a contra-polymatroid. An equivalent polymatroidal representation can be found without much difficulty (see [31]). Thus, these specify V 1 and P 1 . If there is only one terminal, then one can simply define a (trivial) polymatroid on it. This specifies V 2 and P 2 .
The situation is different when one considers network coding and multiple terminals. The algorithm in [32], is only guaranteed to return one set of flows that satisfies flow balance at all source nodes, internal nodes and the terminals. It is possible to show the existence of instances where one set of flows will not simultaneously satisfy all the terminals, when one considers the M IN −COST −SW −N ET W ORK problem. An example can be found in Figure 6 in [13]. Moreover, the objective function in M IN − COST − SW − N ET W ORK, penalizes the maximum of the flows across the terminals at each node, which is different from the one in [32]. Thus, it is unclear whether this algorithm can be adapted to our problem in a straightforward manner.

IV. QUADRATIC GAUSSIAN CEO OVER A NETWORK
In general, the problem of transmitting compressible sources over a network need not have the requirement of lossless reconstruction of the sources. This maybe due to multiple reasons. The terminal may be satisfied with a low resolution reconstruction of the sources to save on network resources or lossless reconstruction may be impossible because of the nature of sources. If a source is continuous then perfect reconstruction would theoretically require an infinite number of bits. Thus the problem of lossy reconstruction has also been an active area of research. In this section we shall consider the quadratic Gaussian CEO problem [16] over a network. We start by outlining the original problem considered by [16]. We then present the minimum cost formulation in the network context and present efficient solutions to it.
Consider a data sequence {X(t)} ∞ t=1 that cannot be observed directly. Instead, independent corrupted versions of the data sequence are available at a set of L agents who are in communication with the Chief Estimation Officer (CEO) over different communication channels. The agents are not allowed to cooperate in any fashion. Suppose that the CEO requires the reconstruction of {X(t)} ∞ t=1 at an average distortion level of at most D. Here, the distortion level is a metric of the fidelity of the reconstruction. Suppose agent i communicates with the CEO at rate R i . The CEO problem [41] is one of studying the region of feasible rate vectors (R 1 , R 2 , . . . R L ) that allow the reconstruction of the data sequence under the prescribed distortion constraint. As in the Slepian-Wolf case there is a direct link between the agents and the terminal (or the CEO). The quadratic Gaussian CEO problem is the particular instance of the CEO problem when the data source {X(t)} ∞ t=1 is Gaussian and the distortion metric is mean squared error. A formal description of the problem follows.
We are interested in the quadratic Gaussian CEO problem over a network. In line with our general setup presented in Section II, the i th source node in S observes the process and encodes the observations at a rate R i . Once again we are interested in the minimum cost network flow problem with rates such that they permit the recovery of the source X at the terminals with the desired level of fidelity, which in this case shall be measured by mean squared error.
We start by highlighting the differences between this problem and the minimum cost Slepian-Wolf over a network. In the previous subsection we observed that the work of Ho et al. shows that random linear network coding over a subgraph such that C Ti ∩ R SW = φ, ∀T i ∈ T allows the lossless recovery of the sources at the terminals in T and essentially the Slepian-Wolf theorem holds even in the network case with multiple terminals i.e. any rate vector that can be obtained by joint coding can be obtained by distributed coding even when there are multiple terminals. However, an analogous result in the case of the quadratic Gaussian CEO problem does not exist. Furthermore, the rate region for the quadratic Gaussian CEO problem over a general network is unknown. As a simple example, we may have a network where two source nodes are connected to a common intermediate node. The intermediate node can then combine the quantized observations from these source nodes to generate a new quantized observation such that a lower rate is possible. Thus the rate region given by the classical Gaussian CEO problem may not hold as the two codewords may be fused to produce a new codeword that enables lower rate transmission.
The first issue can be handled by assuming that there is only one terminal, i.e., N R = 1 and C T1 ∩ R(D) = φ so that routing will suffice to transmit a rate vector belonging to C T1 ∩ R(D) to the terminal T 1 . Thus in this problem we shall not consider network coding. For the second issue we assume that the network operates in a separate compression and information transfer mode. The set of source nodes quantize their observations as they would in the original quadratic Gaussian CEO problem. After this source coding step, the network ignores any data correlations and routes the data as though it were incompressible. In general this separation of the compression and the information transfer is suboptimal, however it is likely to be a simple way of operating the network.
It is more convenient to cast this optimization in terms of the original graph rather than the augmented graph. The MIN-COST-QUAD-CEO-NETWORK problem becomes R ∈ R(D) Here (12) enforces the flow balance at all nodes in V except those in S ∪ {T 1 }, (13) enforces the constraint that at least R i units of flow is injected at each source node i ∈ S and (14) ensures that at least i∈S R i is received at the terminal T 1 . For the MIN-COST-SW-NETWORK problem the total rate to be transmitted to T 1 could be fixed to H(X 1 , . . . , X N ) as shown in the Appendix. However for the problem presented above fixing the total rate is not possible because of the nature of the inequalities specifying R(D). A feasible solution to the optimization presented above would yield a routing solution such that the delivery of a rate vector belonging to R(D) is possible at terminal T 1 . The proof is similar to the one presented in the proof of Lemma 1. However even though the optimization under consideration above is convex, the number of constraints specifying R(D) is exponential in N S that would make a regular convex program solver inefficient.

A. Solving MIN-COST-QUAD-CEO-NETWORK via dual decomposition
We assume that the MIN-COST-QUAD-CEO-NETWORK problem is strictly feasible so that strong duality holds [36]. The Lagrangian with respect to the set of flow balance constraints that contain terms dependent on R i , i ∈ S for a given λ is given by It is easy to see that finding the dual function g(λ) = min x,R L(λ, x, R) subject to the remaining constraints decom-poses as and minimize i∈S The optimization in (15) is a linear program that can be solved efficiently. To solve (16) we note that for a given (r 1 , . . . , r NS ) it can be shown that the region R D (r 1 , . . . , r NS ) (defined in (11)) is a contra-polymatroid [37]. Therefore an optimization problem such as can be solved in closed form by using the greedy allocation algorithm presented earlier. Using this fact we show (see Appendix-II) that the optimization in (16) reduces to a convex optimization problem with N S + 1 constraints that can be solved efficiently via Lagrange multiplier methods. It is important to note that the optimal value of the above optimization problem is −∞ if w i < 0 for any i. This is because the inequalities defining R(D) do not impose any upper bounds on the individual rates R i for i ∈ S. Consequently the optimization in (16) has a finite optimal value only if λ i + λ T1 ≥ 0, ∀i ∈ S. It is clear based on the previous arguments that we can evaluate g(λ) efficiently. We now need to solve the optimization For solving this maximization we use the projected subgradient method [17]. As noted in Section III the subgradient algorithm may not return a primal optimal or primal nearoptimal solution. For primal recovery for the MIN-COST-QUAD-CEO-NETWORK problem we use the technique proposed by Larsson et al. [44] that generalizes the method of [38] to the case of general convex programs. We point out some differences between the two methods below.
The method of Larsson et al. considers an optimization of the following form.
where the functions f and h i , i ∈ I are convex and the set X is convex and compact. It assumes the Slater constraint qualification condition, i.e., the existence of a strictly feasible point x 1 such that {x 1 ∈ X | h i (x 1 ) < 0, i ∈ I} and considers the dual function with respect to the constraints h i , i ∈ I, and then solves the maximization of the dual function max θ(u) subject to u 0 by using the projected subgradient algorithm. Let x (k) denote the primal solution obtained at the k th iteration. Section 3.2 of [44] shows that for step sizes α k ∈ µ b+k , M b+k , k > 0, 0 < µ ≤ M < ∞, k ≥ 0 the sequence of averages defined bŷ converges to the primal optimal solution as n → ∞. The choice of step sizes is more limited in this method as compared to [38]. In our problem the h i functions are the linear inequality constraints in (13) and (14) and the existence of a strictly feasible solution is assumed. However, the set R(D) is convex but not compact. The condition of compactness is however rather technical and can be enforced by imposing a loose upper bound on the rates. In practice, while running the subgradient algorithm the dual variables λ i , i ∈ S and λ T1 were constrained to be larger than or equal to 10 −10 at any iteration to ensure that the optimized rates were bounded. Averaging the solutions as in (18) we observed a steady convergence of the algorithm to the optimal cost in our simulations.

B. Results
As in the previous section we generated the graphs randomly. However, there is only one terminal in the MIN-COST-QUAD-CEO-NETWORK problem since we want a solution based on routing. Figure 2(a) shows an example of a network with 10 source nodes, 39 relay nodes and 1 terminal node. In this particular example we chose the variance of the source to be σ 2 X = 0.01, the sensing noise variance of the source nodes to be σ 2 i = 0.005 for all i ∈ S and the required distortion level D = 0.003. The capacity of the light edges is 11 and the capacity of the dark edges is 22. The cost of each edge was set to 1.0. For the subgradient algorithm the step size was chosen to be α k = 10 1+k . The averaging process ignored the first 100 primal solutions. As demonstrated in Fig. 2(b) there is a steady convergence of the subgradient algorithm to the optimal solution.

WITH DATA DISTORTION CONSTRAINTS
We now consider the problem of maximizing the lifetime of a sensor network when the terminal node needs to be able to reconstruct the data at a particular distortion level (related problems were studied in [26]). This problem is important in the context of sensor networks where nodes are typically battery-limited and are sensing correlated phenomena that need to be reconstructed at the terminal node. It has been studied in [45] when the rates of the sensors are fixed. As explained in the previous section, the sensor nodes observe independent corrupted versions of an i.i.d. Gaussian data sequence {X(t)} ∞ t=1 and communicate at a particular rate to the terminal node. The operating rate vector, whose components consists of the operating rates of each sensor should be such that the terminal should be able to reconstruct {X(t)} ∞ t=1 subject to a mean squared error distortion constraint. We are interested in finding routes over which the data should be routed so that the reconstruction (with an acceptable level of fidelity) can be ensured at the terminal for the longest period of time before a node runs out of energy.
There is an inherent trade-off between the choice of the operating rate for a given sensor and the energy consumption that occurs when the data from the sensor is transmitted to the terminal since the amount of energy consumption roughly depends on the amount of distance or hops that the data has to travel.. This is best illustrated in Fig. 3. The sensor node S2 that is closer to the phenomenon of interest has a better sensing SNR, but is far from the terminal. Therefore S2 requires less bits for quantization, however the data needs to travel a longer distance. On the other hand, sensor node S1 that is further away from the source but closer to the terminal has a lower sensing SNR and requires more bits for quantization, but its data needs to travel a smaller distance. Thus there is a clear tradeoff in how we would want to perform the rate and the flow allocation if we wanted to maximize the network lifetime.
Terminal S1 S2 Source Fig. 3. The figure shows sensor nodes S1 and S2 at different distances from the phenomenon of interest. The red path corresponds to the data from S1 and the blue path corresponds to the data from S2.
In this section we formulate the problem of maximizing the lifetime of a network in the quadratic Gaussian CEO setting. As in the previous section we assume that the network operates by separate compression and network information transfer. We are given the following. a) An i.i.d. Gaussian data source sequence {X(t)} ∞ t=1 and set of source nodes S that observe independent corrupted versions of {X(t)} given by There is a single terminal node T 1 that seeks to reconstruct the source such that the distortion under the mean squared error metric is at most D. The feasible rate region for this problem denoted R(D) is given by (11). b) The initial battery level, E i of each node i ∈ V and the following power consumption figures of interest.
i) P tx (i, j) -the power consumed when i transmits data to j at unit rate for all i, j ∈ V , ii) P rx (i, j) -the power consumed when j receives data from i at unit rate for all i, j ∈ V and, iii) P sense (i) -the power consumed when i uses an additional bit for quantizing its observations.
We define the network lifetime to be the time until the first node runs out of energy. The resultant optimization problem that we call MAX-LIFETIME-DISTORTION-CONSTRAINT can be expressed as where Γ denotes the reciprocal of the network lifetime. Note that [45] considers the lifetime maximization problem when the operating rate for each node i ∈ V is fixed. Therefore the problem becomes a linear program that can be solved efficiently. However we are interested in jointly optimizing the operating rates and the lifetime of the network. In the formulation above we note that the specification of the region R(D) is non-linear (although convex) with exponentially (in the number of sources) many inequalities. In [26], the authors considered a problem similar to MAX-LIFETIME-DISTORTION-CONSTRAINT and proposed suboptimal solutions for by approximating the constraints of R(D) by linear inequalities. The authors presented approximate linear programs that were obtained by strengthening and weakening these constraints and concluded that the true network lifetime was between the results obtained by solving these linear programs. However the number of constraints was still exponential in the number of sources that precluded solving large instances of the problem. In this section we present a solution to this problem based on dual decomposition. We point out that we are considering a strategy where the rate allocation is static. In practice, it may be beneficial to adapt the rate allocation over time to extend the lifetime of the network.

A. Solving MAX-LIFETIME-DISTORTION-CONSTRAINT by dual decomposition
We note that as in section IV we can dualize the appropriate flow balance and energy consumption constraints and compute the dual function for this problem efficiently by exploiting the contra-polymatroidal structure of R(D). However, in practice we observed that the simple projected subgradient algorithm for maximizing the dual function for this problem is far too slow to be practical. Therefore we pursue an alternate line of attack here. We actually minimize Γ 2 instead of Γ and use the proximal bundle method [46] and perform primal recovery as explained in [46]. The Lagrangian for a given λ 1 and λ 2 becomes L(λ 1 , λ 2 , x, R) = and finding g(λ 1 , λ 2 ) = min Γ,x,R L(λ 1 , λ 2 , x, R) subject to the remaining constraints decomposes as and minimize i∈S (λ 1i + λ 1T1 + P sense λ 2i )R i subject to R ∈ R(D).
The optimization problem in (19) can be solved by using a quadratic programming solver and the optimization problem in (20) can be solved as shown in Section IV. We used the quadratic programming package offered by MOSEK 1 for this part of the work. From the above decomposition we have an efficient method to evaluate g(λ 1 , λ 2 ). It remains to evaluate maximize g(λ 1 , λ 2 ) subject to λ 1 , λ 2 0 for which we used the method of [46]. We now briefly overview the proximal bundle technique.
Consider the convex optimization problem where Z is a compact and convex set, ψ j is a convex function for j = 0 . . . n. Let f be the dual function of this optimization problem with respect to the constraints ψ j (z) ≤ 0, j = 1 . . . n. Note that the dual function is always concave and that we may not know f in its functional form. However we assume f and a subgradient of f at any given point is available via an oracle. We are interested in solving the original convex optimization by finding max x∈A f (x) where A is a non-empty, closed convex set and performing primal recovery. Toward this end we use the following algorithm.
Step 4: Compute f (y k+1 ) and a subgradient s k+1 at y k+1 . Also store the value of the primal variables corresponding to y k+1 , denoted by z k+1 . The work of [46] shows that the aggregate primal solution obtained by computing k j=1 ν k j z j produces an asymptotically optimal primal solution as k → ∞. For more details (such as the choice of the µ k sequence) and for techniques for reducing the storage requirements associated with this method, we refer the reader to [46].
We applied this method to our problem since we can efficiently evaluate the dual function and can compute a subgradient at each point as well. Note that in this method as well, there is the technical compactness condition on Z. In our problem since there are no upper bounds on the rates, our region is not compact. However as in the previous section we impose loose upper bounds on the rates by enforcing the dual variables to be larger than or equal to 10 −10 .

B. Results
We ran the previous algorithm on the same topology shown in Fig. 2(a). We chose the variance of the source to be σ 2 X = 0.01, the sensing noise variance of the source nodes to be σ 2 i = 0.005 for all i ∈ S and the required distortion level D = 0.003. The battery levels for all the nodes were chosen to be 200 and we set P tx (i, j) = 1.0, P rx (i, j) = 0.5 and P sense = 0.001. As demonstrated in Fig. 4 there is a steady convergence of the proximal bundle algorithm to the optimal solution. We note that the lifetime maximization problem can also be solved in a similar manner if one consider the case of lossless reconstruction with multiple terminals.

VI. CONCLUSIONS AND FUTURE WORK
We considered the problem of jointly allocating rates and flows at minimum cost for distributed source coding problems over a network. In particular, we considered (a) the Slepian-Wolf problem, (b) the minimum cost quadratic Gaussian CEO problem and (c) the problem of maximizing network lifetime when a source needs to be reconstructed within a quadratic distortion constraint. These problems are of interest in domains such as sensor networks where the data that is sensed by different sensors is typically highly correlated. The feasible rate region of distributed source coding problems is typically specified by a number of inequalities that is exponential in the number of sources that makes these problems hard to solve. We presented an approach based on dual decomposition that uses the special structure of the rate regions to efficiently compute the dual function. Finally, we demonstrated approaches for maximizing the dual function using the subgradient algorithm and the proximal bundle algorithm.
It would be interesting to investigate algorithms along the lines of those considered by Fujishige [32] (that do not use dual decomposition), for the problems considered in this paper and study whether they have lower complexity. In all the problems we considered, we were able to decouple the rate allocations from the flow allocations. This essentially happens because the two sets of variables have a limited interaction via simple linear inequalities. As pointed out by a reviewer there may be other problems that may lend themselves to this kind of decomposition, where the interaction between these variables is more complex.

VII. ACKNOWLEDGEMENTS
The author would like to thank the anonymous reviewers whose suggestions greatly improved the quality and presenta-tion of the paper.
Then there exists another vector (R Proof. We claim that there exists a R j * ∈ {R 1 , R 2 , . . . , R n } such that all inequalities in which R j * participates are loose. The proof of this claim follows.
Suppose that the above claim is not true. Then for all R i where i ∈ {1, 2, . . . , n}, there exists at least one subset S i ⊂ {1, 2, . . . , n} such that, i.e. each R i participates in at least one inequality that is tight. Consider the subsets S 1 and S 2 , i.e. the subsets for which the inequalities are tight for R 1 and R 2 respectively. We have by assumption, ≤ H(X S1∪S2 |X (S1∪S2) c ) + H(X S1∩S2 |X (S1∩S2) c ) (21) where in the second step we have used the supermodularity property of conditional entropy. Now we are also given that k∈S1∩S2 R k ≥ H(X (S1∩S2) |X (S1∩S2) c ).
The above argument shows that there exists some j * such that all inequalities in which R j * participates are loose. Therefore we can reduce R j * to a new value R red j * until one of the inequalities in which it participates is tight. If the sum-rate constraint is met with equality then we can set R ′ j * = R red j * otherwise we can recursively apply the theorem to arrive at a new vector that is component-wise smaller that the original vector (R 1 , R 2 , . . . , R n ).
We refer the S-W constraint j R j ≥ H(X 1 , . . . , X NS ) as the sum rate constraint. From theorem 2 we realize that if there exists a rate vector (R 1 , R 2 , . . . , R n ) ∈ R SW that does not meet the sum rate constraint with equality then we can always find another vector (R and attempted to the solve the resulting linear program (without forcing the sum rate constraint to be satisfied with equality). Suppose that this optimization has a feasible point (z, x, R) where the rate allocation for some terminal does not satisfy the sum rate constraint. Then based on the previous observation we can conclude that we can replace R by a new set of rate allocations R ′ such that R R ′ and (z, x, R ′ ) continues to be feasible with the same cost. In fact one can possibly find a new set of flows that may have a lower cost.
To conclude this shows that it is sufficient to consider rate allocations that satisfy the sum rate constraint.

IX. APPENDIX-II
Consider the quadratic Gaussian CEO problem with n sources. For a given (r 1 , . . . , r n ), it can be seen that the rank function of the contra-polymatroid specified by R(D) is given by 1−e −2r k σ 2 where A ⊆ {1, 2, . . . , n}, A = φ. Therefore the minimizer of (17) can be written as (1), . . . , π(i)}) − f ({π(1), . . . , π(i − 1)}) where π is a permutation such that w π(1) ≥ w π(2) ≥ · · · ≥ w π(n) . The optimization problem in (17) becomes Let A π i denote the set {π(1), . . . , π(i)} c . The objective function simplifies to n i=1 w π(i) r π(i) + 1 2 n i=1 w π(i) log We note that the first constraint in (25) has to be tight. To see this suppose r π(1) > 0 and that the constraint is not tight. Then we can reduce r π(1) so that the objective function (26) is reduced. If r π(1) = 0, then the argument can be applied to r π(2) by realizing that the term corresponding to i = 1 in the second summation above is zero and so on. Using this observation the optimization in (25) can be rewritten as minimize n i=1 w π(i) r π(i) + w π(1) log(1/D) − w π(n) log(1/σ 2 X ) + n−1 i=0 (w π(i+1) − w π(i) ) log 1 σ 2 Next, we form the Lagrangian of the optimization problem in (27) above with respect to the equality constraint while treating the positivity constraint on the r i 's to be implicit and obtain the KKT conditions [36].