# Minimum Cost Data Aggregation for Wireless Sensor Networks Computing Functions of Sensed Data

Authors: Chao Chen; Kyogu Lee; Joon-Sang Park; Seung Jun Baek
Journal: Journal of Sensors
 (2015)

---

## Abstract

We consider a problem of minimum cost (energy) data aggregation in wireless sensor networks computing certain functions of sensed data. We use in-network aggregation such that data can be combined at the intermediate nodes en route to the sink. We consider two types of functions: firstly the summation-type which includessum, mean, and weighted sum, and secondly the extreme-type which includes max and min. However for both types of functions the problem turns out to be NP-hard. We first show that, for sum and mean, there exist algorithms which can approximate the optimal cost by a factor logarithmic in the number of sources. For weighted sum we obtain a similar result for Gaussian sources. Next we reveal that the problem for extreme-type functions is intrinsically different from that for summation-type functions. We then propose a novel algorithm based on the crucial tradeoff in reducing costs between local aggregation of flows and finding a low cost path to the sink: the algorithm is shown to empirically find the best tradeoff point. We argue that the algorithm is applicable to many other similar types of problems. Simulation results show that significant cost savings can be achieved by the proposed algorithm.


---

## Body

## 1. Introduction

Motivation. In this paper we consider the problem of minimum cost (energy) data aggregation in wireless sensor networks (WSN) where the aggregated data is to be reported to a single sink. A common objective of WSN is to retrieve certainsummary of sensed data instead of the entire set of data. The relevant summary is defined as a certain function applied to a set of measured data [1]. Specifically we are given a function g
(
·
) such that, for a set of measurement data x
1
,
…
,
x
n, the goal of the sink is to retrieve g
(
x
1
,
x
2
,
…
,
x
n
). Examples of g
(
·
) are mean, max, min, and so forth. When mean function is used, g
(
x
1
,
…
,
x
n
)
=
∑
i
=
1
n
x
i
/
n. For applications such as “alarm” systems, one can use max as g
(
·
), for example, g
(
x
1
,
…
,
x
n
)
=
m
a
x
i
=
1
,
…
,
n
x
i where x
i can be temperature values in forest-fire monitoring systems or the structural stress values measured in a building. We will refer to g
(
·
) as asummary function throughout this paper. Certain types of g
(
·
) allow us to combine data at the intermediate nodes en route to the sink. Such combining techniques are commonly referred to asin-network aggregation [2–4]. By using in-network aggregation one can potentially save communication costs by reducing the amount of traffic [5–7]. For instance, in the applications such as wireless multimedia sensor networks (WMSN) where the transmitted multimedia data has a far greater volume than that in typical WSNs, the in-network aggregation technique is crucial for the purpose of saving energy and extending network lifetime [8, 9]. While in-network aggregation offers many benefits, it poses significant challenge for network design, for example, designing routing algorithms so as to minimize costs such as energy expenditure and delay. In particular, we show that it is crucial to take into account how the summary function g
(
·
) affects the statistical properties of sensed data.Objectives. In this paper we study the minimum cost aggregation problem for several types of g
(
·
). The performance of in-network aggregation relies heavily on the properties of the function g
(
·
). To be specific let us briefly look at the problem formulation. Consider the single-sink aggregation problem where we define the cost function as follows. Let E denote the set of links in the network. We would like to minimize(1)
∑
e
∈
E
‍
w
e
ϕ
e
,where w
e represents the weight associated with link e and ϕ
e represents the average number of bits transmitted over e. Note that the objective similar to (1) has been considered in [10–14] as well. The most relevant objective associated with (1) is theenergy consumption. To see this, let us define weight w
e
:
=
k
e
d
e
-
α where d
e is the distance between nodes connected by Link e, α is the path loss exponent, and k
e is the related channel parameter. Hence (1) is proportional to the total transmitted energy consumed throughout the data aggregation. Note in [13, 14], the authors consider the same energy cost function. We refer to ϕ
e as theaggregation cost function (we will use notation ϕ to denote the cost function in general, whereas ϕ
e is used to denote the cost function specifically on Link e). Note that ϕ
e depends on the source measurements aggregated on e, and also on g
(
·
) which is the summary function applied to the measurements. The work in [15] also studies an aggregation problem in sensor networks computing summary functions, assuming that all the packets generated in the network have the same size. However, the amount of information generated at intermediate nodes may vary, since a summary of data can be statistically different from the original data, which is our key observation.Let us take an example. Consider the network in Figure1 where Nodes 1 and 2 are the source nodes, and the node in shaded color represents the sink. The sink wants to receive a summary of information from Nodes 1 and 2. The sensor readings generated at Nodes 1 and 2 are represented by the random variables (RV) X
1 and X
2, respectively. Since Node 1 is a “leaf” node, Node 1 will simply transmit the raw reading X
1 to Node 2. Node 2 will combine X
1 with its own data, X
2, by computing the summary function g
(
X
1
,
X
2
) which is then transmitted to the sink. We define the aggregation cost function ϕ as follows. Suppose the sensor information to be transmitted on Edge e is random variable Y. The average number of bits to be transmitted on e, or ϕ
e, is defined as (We temporarily ignore communication overheads incurred in addition to the sensor information, e.g., the packet header size. We will however take such overheads into account later when we formally define ϕ.)(2)
ϕ
e
=
H
Y
,where H
(
·
) denotes the entropy function. Note that the entropy function has been also adopted as cost function in [10, 12], and throughout this paper we will define ϕ in terms of H
(
·
). The average numbers of bits transmitted on Edges 1 and 2 are, respectively, given by(3)
ϕ
1
=
H
X
1
,
ϕ
2
=
H
g
X
1
,
X
2
.Suppose g
(
·
) is given by sum. Since H
(
g
(
X
1
,
X
2
)
)
=
H
(
X
1
+
X
2
)
≠
H
(
X
1
), the costs incurred at Edges 1 and 2, that is, ϕ
1 and ϕ
2, are different. If we had used other types of g
(
·
), such as max, we would have that ϕ
2
=
H
(
m
a
x
(
X
1
,
X
2
)
) which would incur different cost from the case where g
(
·
) was sum. In many cases we will assume symmetric sources; that is, ϕ depends only on the number of sensor readings to which g
(
·
) is applied. In those cases we will treat ϕ as a function ϕ
:
Z
+
→
R
+; that is, ϕ
(
m
)
=
H
(
g
(
X
1
,
…
,
X
m
)
) (we will also examine the cases of asymmetric sources as well). We will show that g
(
·
) determines the properties of ϕ
(
·
) such as convexity and monotonicity, and the structure of the aggregation problem heavily depends on those properties. Hence the aggregation scheme must be designed to capture key aspects of aggregation cost functions under the given summary function. The abovementioned links among summary functions, cost functions, and optimal aggregation strategies have not been previously well studied, as we will see in Section 2 through reviewing related works.Figure 1
An example of computing and communicating a summary.Contributions. In this paper we investigate the minimum energy aggregation problem for several widely used summary functions. We consider two types of g
(
·
). The first type is called thesummation type which involves sums of measurements: specifically sum, mean, and weighted sum. The second type is called theextreme type which is related to the extreme statistics of the data: specifically max and min. We will use the entropy function as the measure of information rate. We show that, when g
(
·
) is sum or mean, and if the source data is i.i.d., ϕ is indeed concave and increasing,irrespective of the distribution of the source data. This implies that one can use well-known algorithms such as the Hierarchical Matching (HM) algorithm [16] in order to approximate the optimal cost. When g
(
·
) is weighted sum however, it is unclear how we make association between the flow aggregation problem and the cost function. Nonetheless we prove that, if the source data is independent Gaussian random variables, there exists an efficient algorithm for the problem of aggregating weighted sum of data with arbitrary weights.Next we consider extreme type summary functions such asmax. We will show that for certain distributions of source data, ϕ can beconvex anddecreasing in the (nonzero) number of aggregated measurements. Note that the single-sink aggregation problems for concave/increasing [16–20] or convex/increasing cost functions [21, 22] have been widely studied, however convex and decreasing ϕ has not been well studied yet. We propose a novel algorithm which effectively captures such properties of ϕ. We begin by observing that there are two aspects in cost reduction as follows. Since ϕ is convex and decreasing, ϕ decreases faster when the number of aggregated data is smaller. The intuition is that it pays to locally aggregate data among nearby sources in theearly stages of aggregation, that is, when the number of measurements aggregated at sensors is small. This leads us to find a low-costlocal clustering of sources, which is a “microscopic” aspect of cost reduction. Meanwhile we need to simultaneously find a low-cost route to the sink, which must take theglobal structure of the network into account and thus is a “macroscopic” aspect of cost reduction. These are conflicting aspects and a good tradeoff point between them should be sought. To that end we propose Hierarchical Cover and Steiner Tree (HCST) algorithm. The algorithm consists of multiple stages and is designed to empirically find the best tradeoff point over the stages. We show that, by simulation, the algorithm can significantly reduce cost compared to baseline schemes such as a greedy heuristic using shortest path routing, or the HM algorithm.Our results show that the summary functiong
(
·
) can significantly impact the design of aggregation schemes. However there are many choices for g
(
·
): suppose for example, we would like to compute L
p norm of the vector of measurement data. Note sum  and max  functions which we study in this paper are in fact related such that, if the measurement data is always positive, then sum  function is simply L
1 norm and max  is L
∞ norm of a data vector. One could ask: what are good aggregation strategies if we take g
(
·
) as a different L
p norm, say L
2 norm? We leave such questions as future work.Paper Organization. We briefly review related work in Section 2. Section 3 introduces the model and problem formulation. Sections 4 and 5 discuss the optimal routing problem for summation and extreme type summary functions, respectively. Simulation results are presented in Section 6. Section 7 concludes the paper.


## 2. Related Work

In general the single-sink aggregation problem to minimize (1) is NP-hard [23], and a substantial amount of research has been devoted to designing approximated algorithms depending on certain properties of ϕ. In our case it is important to note that such properties of ϕ are determined by the choice of g
(
·
). Let us briefly review the related work on the single sink aggregation problem for two types of ϕ. Most research on the single sink aggregation problem has focused on the case where ϕ isconcave andincreasing. Due to the concavity of ϕ, the link costs associated with the amount of aggregated data exhibiteconomies of scale, that is, the marginal cost of adding a flow at a link is cheaper when the current number of aggregated flows is greater at the link. Buy-at-bulk network design [23, 24] is based on such property of ϕ. A number of approximation algorithms have been proposed, for example, [17–19]. When ϕ is known in advance, a constant factor approximation to the optimal cost is possible [20, 25]. Even when ϕ is unknown but is concave and increasing, Goel and Estrin [16] have proposed a simple and randomized algorithm calledHierarchical Matching (HM). The algorithm computes minimum weight matchings of the source nodes hierarchically over stages, and outputs a tree for aggregation. HM algorithm can approximate the optimal cost by a factor logarithmic in the number of sources [16]. Nonuniform variants of this problem such that ϕ differs among the links are also studied [26, 27] in which a polylogarithmic approximation to the optimal cost is shown to be achievable.The case whereϕ isconvex andincreasing in the number of aggregated measurements has been studied in [21, 22]. Here ϕ exhibits (dis)economies of scale, that is, the marginal cost of routing a flow at a link is more expensive when a greater number of flows are aggregated at the link. Such phenomenon can be observed from many applications, such as speed scaling of microprocessors modeled by ϕ
(
m
)
=
β
m
a where m is the clock speed, β
≥
0 and a
≥
1 are constants, and ϕ
(
m
) is the energy consumption at the processor. Notably the authors show that the problem can intrinsically differ from that for a concave and increasing ϕ. For example the authors show that constant-factor approximation algorithms do not exist for certain convex and increasing ϕ [21]. They nevertheless proposed a constant factor approximation algorithm for the case ϕ
(
m
)
=
β
m
a. These results show that the single-sink aggregation problem crucially depends on certain properties of ϕ such as convexity. However, none of the above works deal with convex and decreasing ϕ which we will study in the sequel.There have been many studies regarding the intermediate data combining in conjunction with routing in order for an efficient retrieval of the complete sensor readings. Scaling laws for achievable rates under joint source coding and routing are studied in [28]. The work [11] studies the problem of minimizing the flow costs under distributed source coding. They show that when ϕ
(
m
) is linear in m, firstly applying Slepian-Wolf coding at the sources, and secondly routing coded information via shortest path tree from the sources to the sink is optimal. In [10] a single-input coding model was adopted in which the coding of information among the nodes can be done only in pairs, but joint coding of the source data from more than two nodes is not allowed. Assuming reduction in packet size is a linear function of correlation coefficient between each pair of nodes, they proposed a minimum-energy routing algorithm. The impact of spatial correlation on routing has been explored in [12]. They showed that, assuming the correlation decays over distance, it pays to form clusters of nearby nodes and aggregate data at the clusterheads. The aggregated information is then routed from clusterheads to the sink. The algorithm is shown to perform well for various correlation models. The tradeoff between integrity of aggregated information and energy consumption has been studied in [29]. Further works on in-network aggregation combined with routing include [30, 31] which propose efficient protocols for routing excessive values among sensed data. A scheme using spatially adaptive aggregation so as to mitigate traffic congestion was proposed in [32].The above works aim at retrieving theentire set of data, instead of a summary, subject to certain degrees of data integrity. In our case, we design energy efficient aggregation schemes to compute the summary function g
(
·
) of the sensor readings. Also in the above mentioned works, the in-network aggregation reduces cost mainly by removing correlation among the data set. In our work, by contrast, we will focus on losslessly retrieving a summary ofstatistically independent sensor readings. We assume the independence of sensor readings because we would like todecouple the cost savings from removing correlation, and the savings from applying the summary function in association with aggregation strategies; we focus on the latter. Moreover, the assumption of the independence among the readings represents the “worst” case in terms of cost savings, since one cannot reduce the energy cost by removing correlations in sensor readings. In fact, the independence assumption can be valid in certain cases. For example, consider a large sensor network assuming that the sensed data is spatially correlated and the correlation decays quickly over distance. If the source nodes are sparsely deployed and thus tend to be far apart from one another, the correlation among their data can be very weak. Obviously such sparse node placement is motivated by cost efficiency: sparse placement of nodes enables us to reap as much information given a fixed number of sensor devices, assuming that the network senses a homogeneous field and the measure of information is given by the joint entropy function.


## 3. Model

### 3.1. Preliminaries

We are given an undirected graphG
=
(
V
,
E
) where V
=
1,2
,
…
,
n and E
⊆
V
×
V denote the set of vertices and edges, respectively. For u
,
v
∈
V, (
u
,
v
)
∈
E denotes the (undirected) edge connecting nodes u and v. For each edge in E we associate aweight defined by w
:
E
→
R
+. A weight captures the cost of transmitting unit amount of data between two nodes, for example, expenditure of transmission energy in order to compensate path loss. The set S
⊂
V denotes the set of source nodes, that is, the nodes which generate measurement data to be reported to the sink. Also define η
:
=
S where · denotes the cardinality of a set. For a source node u
∈
S, its measured data is modeled by an RV denoted by X
u. We assume that X
u’s are independent and identically distributed among the sources. The measured data is to be aggregated at the sink node denoted by t
∈
V. The nodes which are not source nodes act as relays in the aggregation process. For simplicity we will assume that any node in the network transmits data at most once during the aggregation process. Such an assumption has been made in other works such as [15]. Thus the routes for aggregation constitute a tree whose root is given by t. We refer to such tree as anaggregation tree. The aggregation process is performed as follows. The sources initiate transmissions. An intermediate node waits for all the data from the sources which are descendants of the node to arrive. Next the node computes the summary function of the aggregated data which is then relayed to the next hop.In this paper a summary function is defined to be a nonnegative function denoted byg
(
·
) which is adivisible function. Divisible functions are a class of summary functions which can be computed in a divide-and-conquer manner [1]. Divisible functions are defined as follows: given n data samples, consider a partition of the samples into sets of size k and n
-
k denoted by {
x
1
,
x
2
,
…
,
x
k
} and {
x
k
+
1
,
…
,
x
n
}, respectively. If g
(
·
) is divisible, g
(
g
(
x
1
,
…
,
x
k
)
,
g
(
x
k
+
1
,
…
,
x
n
)
)
=
g
(
x
1
,
x
2
,
…
,
x
n
) holds for any n and k. Examples of divisible functions are sum, max  and min. Particularly when g
(
·
) is divisible, the aggregation can be performed in a divide-and-conquer manner as follows. Suppose a set of data samples are aggregated at a node. If the node is a source, it applies g
(
·
) to the collected samples and its own data. If the node is simply a relay, it applies g
(
·
) to the aggregated data samples to obtain a summary of the samples where the summary of its aggregated data is transmitted to the next hop.Abusing notation for the sake of simplicity, we let the functiong
(
·
) take a set, a vector, or their combination as its argument. For example if g
(
·
) is sum, g
(
x
,
y
)
=
x
+
y, and g
(
{
x
,
y
}
)
=
x
+
y, and also g
(
{
x
,
y
}
,
z
)
=
x
+
y
+
z. For some U
⊆
V, we define X
U as the set of RVs representing the measurements from the nodes in U; that is, X
U
:
=
u
∈
U
∣
X
u. Thus g
(
X
U
) is the aggregation function applied to the set X
U, for example, if g
(
·
) is sum  then(4)
g
X
U
=
∑
u
∈
U
‍
X
u
.


### 3.2. Problem Formulation

We will define the problem of minimizing communication costs as follows. There exists a sink to which the data is to be aggregated. Our goal is to find a minimum-cost aggregation treeT
=
(
V
′
,
E
′
)
⊆
G rooted at the sink. We would like to solve the following aggregation problem:(5)
P
Minimize
T
=
V
′
,
E
′
⊆
G
⁡
∑
e
∈
E
′
‍
w
e
ϕ
e
,where ϕ
e represents the average number of bits communicated over Edge e. Note that the objective of (5) has been considered in the works [10, 12] as well. We call ϕ
e asaggregation cost function which we define as follows.We will use the entropy functionH
(
·
) as our measure of information rate similar to works [13, 14]. We assume that the average number of bits to represent random sensor measurement X is given by H
(
X
). A precise definition of the entropy function H
(
X
) depends on the nature of X: if X is a discrete RV, H
(
X
) denotes the usual Shannon entropy. If X is a continuous RV, H
(
X
) is implicitly defined to be H
(
X
^
) where X
^ is a discrete RV obtained by applying uniform scalar quantization to X with some quantization step size, say 2
-
b for some integer b
>
0. If the quantization precision is sufficiently high, it is known [33] that H
(
X
^
)
≈
b
+
h
(
X
) where h
(
·
) denotes the differential entropy of continuous RVs. Note that a similar approximation has been made in defining the information rates for continuous RVs in [13, 14]. Hence in this paper, we will assume that continuous RV X incurs the cost of b
+
h
(
X
) bits where b
>
0 is a sufficiently large parameter, and we denote such costs by H
(
X
)
:
=
b
+
h
(
X
).In addition, the measured data is transmitted as a packet in the network. Hence for each packet transmission, there is an overhead of metadata, for example, packet header. For any measurementY, no matter how small H
(
Y
), there is always an overhead of transmitting such metadata in practice. We will assume the header length is fixed to α
>
0 bits throughout this paper. Hence the average number of bits required to send measurement information Y per transmission over a link is given by(6)
α
+
H
Y
.For a given aggregation tree T
=
(
V
′
,
E
′
), let p
(
s
)
⊂
E
′ denote the path from a source s
∈
S to the sink. For a given Edge e
∈
E, let U
(
e
)
⊆
S denote the set of source nodes whose aggregated measurements are transmitted over e, that is, U
(
e
)
=
s
∈
S
∣
e
∈
p
s. The information to be communicated over Edge e is the function g
(
·
) applied to the set of measurement value from U
(
e
), that is, g
(
X
U
(
e
)
). Hence we define the aggregation cost function as follows:(7)
ϕ
e
=
0
U
e
=
∅
α
+
H
g
X
U
e
o
t
h
e
r
w
i
s
e
.We would like to solve (
P
) using the definition of ϕ
e given by (7). In the following sections we investigate several widely used summary functions and the associated optimal aggregation problems.


## 3.1. Preliminaries

We are given an undirected graphG
=
(
V
,
E
) where V
=
1,2
,
…
,
n and E
⊆
V
×
V denote the set of vertices and edges, respectively. For u
,
v
∈
V, (
u
,
v
)
∈
E denotes the (undirected) edge connecting nodes u and v. For each edge in E we associate aweight defined by w
:
E
→
R
+. A weight captures the cost of transmitting unit amount of data between two nodes, for example, expenditure of transmission energy in order to compensate path loss. The set S
⊂
V denotes the set of source nodes, that is, the nodes which generate measurement data to be reported to the sink. Also define η
:
=
S where · denotes the cardinality of a set. For a source node u
∈
S, its measured data is modeled by an RV denoted by X
u. We assume that X
u’s are independent and identically distributed among the sources. The measured data is to be aggregated at the sink node denoted by t
∈
V. The nodes which are not source nodes act as relays in the aggregation process. For simplicity we will assume that any node in the network transmits data at most once during the aggregation process. Such an assumption has been made in other works such as [15]. Thus the routes for aggregation constitute a tree whose root is given by t. We refer to such tree as anaggregation tree. The aggregation process is performed as follows. The sources initiate transmissions. An intermediate node waits for all the data from the sources which are descendants of the node to arrive. Next the node computes the summary function of the aggregated data which is then relayed to the next hop.In this paper a summary function is defined to be a nonnegative function denoted byg
(
·
) which is adivisible function. Divisible functions are a class of summary functions which can be computed in a divide-and-conquer manner [1]. Divisible functions are defined as follows: given n data samples, consider a partition of the samples into sets of size k and n
-
k denoted by {
x
1
,
x
2
,
…
,
x
k
} and {
x
k
+
1
,
…
,
x
n
}, respectively. If g
(
·
) is divisible, g
(
g
(
x
1
,
…
,
x
k
)
,
g
(
x
k
+
1
,
…
,
x
n
)
)
=
g
(
x
1
,
x
2
,
…
,
x
n
) holds for any n and k. Examples of divisible functions are sum, max  and min. Particularly when g
(
·
) is divisible, the aggregation can be performed in a divide-and-conquer manner as follows. Suppose a set of data samples are aggregated at a node. If the node is a source, it applies g
(
·
) to the collected samples and its own data. If the node is simply a relay, it applies g
(
·
) to the aggregated data samples to obtain a summary of the samples where the summary of its aggregated data is transmitted to the next hop.Abusing notation for the sake of simplicity, we let the functiong
(
·
) take a set, a vector, or their combination as its argument. For example if g
(
·
) is sum, g
(
x
,
y
)
=
x
+
y, and g
(
{
x
,
y
}
)
=
x
+
y, and also g
(
{
x
,
y
}
,
z
)
=
x
+
y
+
z. For some U
⊆
V, we define X
U as the set of RVs representing the measurements from the nodes in U; that is, X
U
:
=
u
∈
U
∣
X
u. Thus g
(
X
U
) is the aggregation function applied to the set X
U, for example, if g
(
·
) is sum  then(4)
g
X
U
=
∑
u
∈
U
‍
X
u
.


## 3.2. Problem Formulation

We will define the problem of minimizing communication costs as follows. There exists a sink to which the data is to be aggregated. Our goal is to find a minimum-cost aggregation treeT
=
(
V
′
,
E
′
)
⊆
G rooted at the sink. We would like to solve the following aggregation problem:(5)
P
Minimize
T
=
V
′
,
E
′
⊆
G
⁡
∑
e
∈
E
′
‍
w
e
ϕ
e
,where ϕ
e represents the average number of bits communicated over Edge e. Note that the objective of (5) has been considered in the works [10, 12] as well. We call ϕ
e asaggregation cost function which we define as follows.We will use the entropy functionH
(
·
) as our measure of information rate similar to works [13, 14]. We assume that the average number of bits to represent random sensor measurement X is given by H
(
X
). A precise definition of the entropy function H
(
X
) depends on the nature of X: if X is a discrete RV, H
(
X
) denotes the usual Shannon entropy. If X is a continuous RV, H
(
X
) is implicitly defined to be H
(
X
^
) where X
^ is a discrete RV obtained by applying uniform scalar quantization to X with some quantization step size, say 2
-
b for some integer b
>
0. If the quantization precision is sufficiently high, it is known [33] that H
(
X
^
)
≈
b
+
h
(
X
) where h
(
·
) denotes the differential entropy of continuous RVs. Note that a similar approximation has been made in defining the information rates for continuous RVs in [13, 14]. Hence in this paper, we will assume that continuous RV X incurs the cost of b
+
h
(
X
) bits where b
>
0 is a sufficiently large parameter, and we denote such costs by H
(
X
)
:
=
b
+
h
(
X
).In addition, the measured data is transmitted as a packet in the network. Hence for each packet transmission, there is an overhead of metadata, for example, packet header. For any measurementY, no matter how small H
(
Y
), there is always an overhead of transmitting such metadata in practice. We will assume the header length is fixed to α
>
0 bits throughout this paper. Hence the average number of bits required to send measurement information Y per transmission over a link is given by(6)
α
+
H
Y
.For a given aggregation tree T
=
(
V
′
,
E
′
), let p
(
s
)
⊂
E
′ denote the path from a source s
∈
S to the sink. For a given Edge e
∈
E, let U
(
e
)
⊆
S denote the set of source nodes whose aggregated measurements are transmitted over e, that is, U
(
e
)
=
s
∈
S
∣
e
∈
p
s. The information to be communicated over Edge e is the function g
(
·
) applied to the set of measurement value from U
(
e
), that is, g
(
X
U
(
e
)
). Hence we define the aggregation cost function as follows:(7)
ϕ
e
=
0
U
e
=
∅
α
+
H
g
X
U
e
o
t
h
e
r
w
i
s
e
.We would like to solve (
P
) using the definition of ϕ
e given by (7). In the following sections we investigate several widely used summary functions and the associated optimal aggregation problems.


## 4. Aggregation Schemes for Summation-Type Summary Functions

We consider the summary functions ofsum, mean, and weighted sum.


### 4.1.sum  and mean

We first discuss the case whereg
(
·
) is sum. We have that(8)
H
g
X
U
e
=
H
∑
u
∈
U
e
‍
X
u
.Clearly sum  is a divisible function. Thus the aggregation process is as follows: a node simply applies sum  function to the aggregated data, and relays the aggregated information to the next hop.When the source data is i.i.d., we will show that there exists a randomized algorithm which finds an aggregation tree whose expected cost is within a factor of(
l
o
g
(
η
)
+
1
) of the optimal cost to (5).Proposition 1.
SupposeX
i’s are i.i.d. For any distribution of X
i, there exists an algorithm yielding the mean cost within a factor of l
o
g
(
η
)
+
1 of the optimal cost of (
P
).
Goel and Estrin [16] studied a single-sink data aggregation problem as follows. A source generates a unit flow which needs to be routed to a sink where the flows are aggregated though a tree. Their objective is to minimize the following cost function:(9)
∑
e
∈
E
‍
w
e
ψ
m
e
,where w
e is the weight on Edge e, m
e is the number of flows on Edge e and ψ
:
R
+
→
R
+ is a function that maps the total size of flow to its cost. They proposed an algorithm to minimize (9) when ψ is acanonical aggregation function defined as follows.Definition 2 (see [16]).
The functionψ
:
R
+
→
R
+ is called a canonical aggregation function (CAF) if it has the following property: (1)
ψ
(
0
)
=
0.
(2)
ψ
(
·
) is increasing.
(3)
ψ
(
·
) is concave.Their algorithm, called Hierarchical Matching (HM) [16], guarantees the mean cost to be within the factor of l
o
g
(
η
)
+
1 of the optimalirrespective of
ψ, provided that ψ is a CAF. As mentioned previously, since X
i’s are i.i.d., ϕ
e depends only on m
e
:
=
U
e. Specifically we will define ϕ as follows:(10)
ϕ
e
=
ϕ
m
e
=
α
+
H
∑
u
∈
U
e
‍
X
u
,
m
e
>
0
,
0
,
m
e
=
0
.We will show that ϕ
(
·
) is a CAF by showing that ϕ
(
·
) satisfies the three properties of Definition 2. Note this implies that HM algorithm can be used to approximately solve (
P
), since (9) and the objective of (
P
) are identical.Proof of Proposition1.
For the first property, it trivially holds thatϕ
(
0
)
=
0. For the second property, for any two independent RVs X
1 and X
2, it is known that H
(
X
1
+
X
2
)
≥
H
(
X
1
) implying that ϕ
(
2
)
≥
ϕ
(
1
), that is, the sum of independent RVs always increases entropy [33], which implies that ϕ
(
m
) is increasing in m. For the third property, consider the following. It is shown in [34] that the entropy of the sum of independent RVs is a submodular set function. That is, the following holds for independent RVs Y
1, Y
2 and Y
3 [34, Theorem I]:(11)
H
Y
1
+
Y
3
+
H
Y
2
+
Y
3
≥
H
Y
1
+
Y
2
+
Y
3
+
H
Y
3
.Now consider m
+
2 sensor measurements X
1
,
…
,
X
m
+
2, and make substitutions Y
1
:
=
X
m
+
1, Y
2
:
=
X
m
+
2, and Y
3
:
=
∑
i
=
1
m
X
i in (11). We have that(12)
H
X
m
+
1
+
∑
i
=
1
m
‍
X
i
+
H
X
m
+
2
+
∑
i
=
1
m
‍
X
i
≥
H
∑
i
=
1
m
+
2
‍
X
i
+
H
∑
i
=
1
m
‍
X
i
.If we apply the definition of ϕ given by (10) to (12), the following holds due to symmetry:(13)
ϕ
m
+
1
+
ϕ
m
+
1
≥
ϕ
m
+
2
+
ϕ
m
.Hence ϕ
(
m
+
2
)
-
ϕ
(
m
+
1
)
≤
ϕ
(
m
+
1
)
-
ϕ
(
m
) holds, or the slope is decreasing in m, which implies that ϕ
(
·
) is concave on the domain of integers. Thus ϕ
(
·
) satisfies all the properties of Definition 2, and is a CAF. This implies that, by using HM algorithm, one can achieve the expected cost which is within the factor of 1
+
l
o
g
(
η
) of the optimal cost of (
P
).Next we considermean  as the summary function. Note that mean, as well as weighted sum considered in the next section, are not divisible functions in general. We will nevertheless show that the problem for those summary functions can be reduced to sum  problem as follows. Suppose every source node is aware of the total number of the sources, that is, η. In our scheme every source simply scales its measurement by η
-
1 prior to transmission, that is, Source i transmits η
-
1
X
i, then such scaled measurements are aggregated in a similar way as the sum  problem. The average number of bits transmitted over Edge e can be written as α
+
H
{
∑
u
∈
U
(
e
)
‍
(
(
1
/
η
)
X
u
)
}. Since (
(
1
/
η
)
X
u
)’s are i.i.d., for the minimum cost aggregation problem for mean  we can use the same algorithm as that used for sum, for example, HM algorithm.


### 4.2.weighted sum

Next we consider the case whereg
(
·
) is weighted  sum  as follows. We assign arbitrary weights a
i, i
∈
S, to the source nodes. The goal of the sink is to compute ∑
i
∈
S
a
i
X
i. Our method of aggregation is similar to that for the case of mean, that is, Source i scales its measurement by a
i, then transmits a
i
X
i where the aggregation process is the same as that for sum. However the effective source data a
i
X
i seen by the network is no longer i.i.d., unless a
i’s are identical for all i
∈
S. The aggregation cost function is given by(14)
ϕ
e
=
α
+
H
∑
i
∈
U
e
‍
a
i
X
i
.The difficulty lies in it is difficult to associate a “flow” with the source data a
i
X
i due to asymmetry, that is, the problem is no longer a flow optimization. Moreover, it is easily seen that (14) is not a CAF in general. Thus we restrict our attention to a specific distribution of X
i. We will show that, if X
i are independent Gaussian RVs, the problem for weighted sum is indeed a single-sink aggregation problem with concave costs, and there exist algorithms similar to HM algorithm which have good approximation ratio. Specifically we prove that our problem is equivalent to the single-sink aggregation/flow optimization problem withnonuniform source demands.Proposition 3.
SupposeX
i
~
N
(
μ
i
,
σ
i
2
), and X
1
,
…
,
X
η are independent. Let g
(
·
) be weighted sum with arbitrary weights a
1
,
…
,
a
η. For sufficiently large b, there exists an algorithm yielding the mean cost within a factor of l
o
g
(
η
)
+
1 of the optimal cost of (
P
).Proof.
Consider the information communicated over Edgee denoted by Y:(15)
Y
=
∑
i
∈
U
e
‍
a
i
X
i
.Since X
i’s are independent Gaussian RVs, Y is also Gaussian with variance σ
e
2 where σ
e
2
:
=
∑
i
∈
U
(
e
)
‍
a
i
2
σ
i
2. Thus the differential entropy of Y is given by(16)
h
Y
=
1
2
l
o
g
2
π
e
∑
i
∈
U
e
‍
a
i
2
σ
i
2
.We observe that, from (16), we can treat a
i
2
σ
i
2 as the “flow” generated by Source i, and the sum of flows at Edge e incurs the entropy cost as in (16). Specifically we will make the following definitions:(17)
f
i
:
=
a
i
2
σ
i
2
,
i
∈
S
,
(18)
f
∗
:
=
m
i
n
i
∈
S
f
i
,
(19)
ψ
x
:
=
α
+
b
+
1
2
l
o
g
2
π
e
x
,
x
≥
0
,
(20)
ϕ
x
:
=
ψ
x
,
x
≥
f
∗
,
ψ
f
∗
f
∗
x
,
0
≤
x
<
f
∗
.Here f
i represents the (unsplittable) flow demand generated by Source i, and f
∗ denotes the minimum demand. Hence under a flow routing scheme, the total amount of flow at Link e is given by ∑
i
∈
U
(
e
)
f
i. Then from (16), the associated communication cost incurred at Link e is given by ψ
(
∑
i
∈
U
(
e
)
f
i
) bits, that is, ψ
(
·
) represents the information rate of a flow aggregated at Link e. Unlike the previously defined cost functions, ψ is no longer a function of the number of sources on a link, but instead the function of the amount of flow on that link. Finally we define the aggregation cost function ϕ in terms of ψ as in (20) in order to meet the concavity condition for ϕ as follows: ϕ is essentially identical to ψ, and if(21)
b
≥
1
2
l
o
g
1
2
π
e
f
∗
,one can show that ϕ
(
x
) is concave and increasing for all x
≥
0. Hence under the condition (21), ϕ is an increasing concave function of the total flow aggregated on a link. In that case we can use the algorithm proposed by Meyerson et al. [19] which essentially extends the HM algorithm to the problems with nonuniform source flow demands, and can approximate the optimal cost by a factor of l
o
g
(
η
)
+
1 on average.In summary, the key question was whether(
P
) can be cast as a flow aggregation problem, if g
(
·
) is weighted sum. In general, it is difficult to make such association due to asymmetry; however, we revealed that such formulation is possible for independent Gaussian sources.


### 4.3. Discussions

Note that some properties regardingX
i’s such as the submodularity relation in (11), used to show that ϕ is a CAF rely heavily on the independence of X
i’s. When X
i’s are correlated, we can find examples of ϕ which are not CAF for the summary function of sum as follows. Let X
1 and X
2 be jointly Gaussian with the same marginal given by N
(
0,1
) with E
[
X
1
X
2
]
=
ρ. Then X
1
+
X
2 is distributed according to N
(
0,2
(
1
+
ρ
)
), thus we have that, if ρ
<
-
0.5, then(22)
h
X
1
+
X
2
=
1
2
log
⁡
2
π
e
·
2
1
+
ρ
<
1
2
l
o
g
2
π
e
=
h
X
1
.Thus the entropy function does not satisfy the second condition of Definition 2, that is, the increasing property, as a CAF. Hence for arbitrarily correlated sources, presumably few meaningful arguments can be made on optimal aggregation problems, even for simple summary functions such as sum.The discussion so far enables us to deal with more general objective functions extended from(
P
). Consider a function γ
:
R
+
→
R
+ which is concave and increasing. We now define communication overhead on an edge as the function γ of the average number of bits transmitted over the edge. Namely, we consider the following extension of (
P
):(23)
P
'
Minimize
T
=
V
′
,
E
′
⊆
G
⁡
∑
e
∈
E
′
‍
w
e
γ
ϕ
e
.Consider (
P
'
) for the summary function sum  for i.i.d. sources and weighted sum for independent Gaussian sources. Note that the composition of two concave and increasing functions is also concave and increasing [35]. Thus γ
(
ϕ
e
) is a concave and increasing function of the amount of flows at an edge, and thus is a CAF. Hence HM algorithm can be used to approximate (
P
'
).


## 4.1.sum  and mean

We first discuss the case whereg
(
·
) is sum. We have that(8)
H
g
X
U
e
=
H
∑
u
∈
U
e
‍
X
u
.Clearly sum  is a divisible function. Thus the aggregation process is as follows: a node simply applies sum  function to the aggregated data, and relays the aggregated information to the next hop.When the source data is i.i.d., we will show that there exists a randomized algorithm which finds an aggregation tree whose expected cost is within a factor of(
l
o
g
(
η
)
+
1
) of the optimal cost to (5).Proposition 1.
SupposeX
i’s are i.i.d. For any distribution of X
i, there exists an algorithm yielding the mean cost within a factor of l
o
g
(
η
)
+
1 of the optimal cost of (
P
).
Goel and Estrin [16] studied a single-sink data aggregation problem as follows. A source generates a unit flow which needs to be routed to a sink where the flows are aggregated though a tree. Their objective is to minimize the following cost function:(9)
∑
e
∈
E
‍
w
e
ψ
m
e
,where w
e is the weight on Edge e, m
e is the number of flows on Edge e and ψ
:
R
+
→
R
+ is a function that maps the total size of flow to its cost. They proposed an algorithm to minimize (9) when ψ is acanonical aggregation function defined as follows.Definition 2 (see [16]).
The functionψ
:
R
+
→
R
+ is called a canonical aggregation function (CAF) if it has the following property: (1)
ψ
(
0
)
=
0.
(2)
ψ
(
·
) is increasing.
(3)
ψ
(
·
) is concave.Their algorithm, called Hierarchical Matching (HM) [16], guarantees the mean cost to be within the factor of l
o
g
(
η
)
+
1 of the optimalirrespective of
ψ, provided that ψ is a CAF. As mentioned previously, since X
i’s are i.i.d., ϕ
e depends only on m
e
:
=
U
e. Specifically we will define ϕ as follows:(10)
ϕ
e
=
ϕ
m
e
=
α
+
H
∑
u
∈
U
e
‍
X
u
,
m
e
>
0
,
0
,
m
e
=
0
.We will show that ϕ
(
·
) is a CAF by showing that ϕ
(
·
) satisfies the three properties of Definition 2. Note this implies that HM algorithm can be used to approximately solve (
P
), since (9) and the objective of (
P
) are identical.Proof of Proposition1.
For the first property, it trivially holds thatϕ
(
0
)
=
0. For the second property, for any two independent RVs X
1 and X
2, it is known that H
(
X
1
+
X
2
)
≥
H
(
X
1
) implying that ϕ
(
2
)
≥
ϕ
(
1
), that is, the sum of independent RVs always increases entropy [33], which implies that ϕ
(
m
) is increasing in m. For the third property, consider the following. It is shown in [34] that the entropy of the sum of independent RVs is a submodular set function. That is, the following holds for independent RVs Y
1, Y
2 and Y
3 [34, Theorem I]:(11)
H
Y
1
+
Y
3
+
H
Y
2
+
Y
3
≥
H
Y
1
+
Y
2
+
Y
3
+
H
Y
3
.Now consider m
+
2 sensor measurements X
1
,
…
,
X
m
+
2, and make substitutions Y
1
:
=
X
m
+
1, Y
2
:
=
X
m
+
2, and Y
3
:
=
∑
i
=
1
m
X
i in (11). We have that(12)
H
X
m
+
1
+
∑
i
=
1
m
‍
X
i
+
H
X
m
+
2
+
∑
i
=
1
m
‍
X
i
≥
H
∑
i
=
1
m
+
2
‍
X
i
+
H
∑
i
=
1
m
‍
X
i
.If we apply the definition of ϕ given by (10) to (12), the following holds due to symmetry:(13)
ϕ
m
+
1
+
ϕ
m
+
1
≥
ϕ
m
+
2
+
ϕ
m
.Hence ϕ
(
m
+
2
)
-
ϕ
(
m
+
1
)
≤
ϕ
(
m
+
1
)
-
ϕ
(
m
) holds, or the slope is decreasing in m, which implies that ϕ
(
·
) is concave on the domain of integers. Thus ϕ
(
·
) satisfies all the properties of Definition 2, and is a CAF. This implies that, by using HM algorithm, one can achieve the expected cost which is within the factor of 1
+
l
o
g
(
η
) of the optimal cost of (
P
).Next we considermean  as the summary function. Note that mean, as well as weighted sum considered in the next section, are not divisible functions in general. We will nevertheless show that the problem for those summary functions can be reduced to sum  problem as follows. Suppose every source node is aware of the total number of the sources, that is, η. In our scheme every source simply scales its measurement by η
-
1 prior to transmission, that is, Source i transmits η
-
1
X
i, then such scaled measurements are aggregated in a similar way as the sum  problem. The average number of bits transmitted over Edge e can be written as α
+
H
{
∑
u
∈
U
(
e
)
‍
(
(
1
/
η
)
X
u
)
}. Since (
(
1
/
η
)
X
u
)’s are i.i.d., for the minimum cost aggregation problem for mean  we can use the same algorithm as that used for sum, for example, HM algorithm.


## 4.2.weighted sum

Next we consider the case whereg
(
·
) is weighted  sum  as follows. We assign arbitrary weights a
i, i
∈
S, to the source nodes. The goal of the sink is to compute ∑
i
∈
S
a
i
X
i. Our method of aggregation is similar to that for the case of mean, that is, Source i scales its measurement by a
i, then transmits a
i
X
i where the aggregation process is the same as that for sum. However the effective source data a
i
X
i seen by the network is no longer i.i.d., unless a
i’s are identical for all i
∈
S. The aggregation cost function is given by(14)
ϕ
e
=
α
+
H
∑
i
∈
U
e
‍
a
i
X
i
.The difficulty lies in it is difficult to associate a “flow” with the source data a
i
X
i due to asymmetry, that is, the problem is no longer a flow optimization. Moreover, it is easily seen that (14) is not a CAF in general. Thus we restrict our attention to a specific distribution of X
i. We will show that, if X
i are independent Gaussian RVs, the problem for weighted sum is indeed a single-sink aggregation problem with concave costs, and there exist algorithms similar to HM algorithm which have good approximation ratio. Specifically we prove that our problem is equivalent to the single-sink aggregation/flow optimization problem withnonuniform source demands.Proposition 3.
SupposeX
i
~
N
(
μ
i
,
σ
i
2
), and X
1
,
…
,
X
η are independent. Let g
(
·
) be weighted sum with arbitrary weights a
1
,
…
,
a
η. For sufficiently large b, there exists an algorithm yielding the mean cost within a factor of l
o
g
(
η
)
+
1 of the optimal cost of (
P
).Proof.
Consider the information communicated over Edgee denoted by Y:(15)
Y
=
∑
i
∈
U
e
‍
a
i
X
i
.Since X
i’s are independent Gaussian RVs, Y is also Gaussian with variance σ
e
2 where σ
e
2
:
=
∑
i
∈
U
(
e
)
‍
a
i
2
σ
i
2. Thus the differential entropy of Y is given by(16)
h
Y
=
1
2
l
o
g
2
π
e
∑
i
∈
U
e
‍
a
i
2
σ
i
2
.We observe that, from (16), we can treat a
i
2
σ
i
2 as the “flow” generated by Source i, and the sum of flows at Edge e incurs the entropy cost as in (16). Specifically we will make the following definitions:(17)
f
i
:
=
a
i
2
σ
i
2
,
i
∈
S
,
(18)
f
∗
:
=
m
i
n
i
∈
S
f
i
,
(19)
ψ
x
:
=
α
+
b
+
1
2
l
o
g
2
π
e
x
,
x
≥
0
,
(20)
ϕ
x
:
=
ψ
x
,
x
≥
f
∗
,
ψ
f
∗
f
∗
x
,
0
≤
x
<
f
∗
.Here f
i represents the (unsplittable) flow demand generated by Source i, and f
∗ denotes the minimum demand. Hence under a flow routing scheme, the total amount of flow at Link e is given by ∑
i
∈
U
(
e
)
f
i. Then from (16), the associated communication cost incurred at Link e is given by ψ
(
∑
i
∈
U
(
e
)
f
i
) bits, that is, ψ
(
·
) represents the information rate of a flow aggregated at Link e. Unlike the previously defined cost functions, ψ is no longer a function of the number of sources on a link, but instead the function of the amount of flow on that link. Finally we define the aggregation cost function ϕ in terms of ψ as in (20) in order to meet the concavity condition for ϕ as follows: ϕ is essentially identical to ψ, and if(21)
b
≥
1
2
l
o
g
1
2
π
e
f
∗
,one can show that ϕ
(
x
) is concave and increasing for all x
≥
0. Hence under the condition (21), ϕ is an increasing concave function of the total flow aggregated on a link. In that case we can use the algorithm proposed by Meyerson et al. [19] which essentially extends the HM algorithm to the problems with nonuniform source flow demands, and can approximate the optimal cost by a factor of l
o
g
(
η
)
+
1 on average.In summary, the key question was whether(
P
) can be cast as a flow aggregation problem, if g
(
·
) is weighted sum. In general, it is difficult to make such association due to asymmetry; however, we revealed that such formulation is possible for independent Gaussian sources.


## 4.3. Discussions

Note that some properties regardingX
i’s such as the submodularity relation in (11), used to show that ϕ is a CAF rely heavily on the independence of X
i’s. When X
i’s are correlated, we can find examples of ϕ which are not CAF for the summary function of sum as follows. Let X
1 and X
2 be jointly Gaussian with the same marginal given by N
(
0,1
) with E
[
X
1
X
2
]
=
ρ. Then X
1
+
X
2 is distributed according to N
(
0,2
(
1
+
ρ
)
), thus we have that, if ρ
<
-
0.5, then(22)
h
X
1
+
X
2
=
1
2
log
⁡
2
π
e
·
2
1
+
ρ
<
1
2
l
o
g
2
π
e
=
h
X
1
.Thus the entropy function does not satisfy the second condition of Definition 2, that is, the increasing property, as a CAF. Hence for arbitrarily correlated sources, presumably few meaningful arguments can be made on optimal aggregation problems, even for simple summary functions such as sum.The discussion so far enables us to deal with more general objective functions extended from(
P
). Consider a function γ
:
R
+
→
R
+ which is concave and increasing. We now define communication overhead on an edge as the function γ of the average number of bits transmitted over the edge. Namely, we consider the following extension of (
P
):(23)
P
'
Minimize
T
=
V
′
,
E
′
⊆
G
⁡
∑
e
∈
E
′
‍
w
e
γ
ϕ
e
.Consider (
P
'
) for the summary function sum  for i.i.d. sources and weighted sum for independent Gaussian sources. Note that the composition of two concave and increasing functions is also concave and increasing [35]. Thus γ
(
ϕ
e
) is a concave and increasing function of the amount of flows at an edge, and thus is a CAF. Hence HM algorithm can be used to approximate (
P
'
).


## 5. Aggregation Schemes for Extreme-Type Summary Functions

### 5.1. Case Study

In this section we consider summary functions regarding the extreme statistics of measurements, that is,max  or min. We will first investigate the entropy of the extreme statistics of a set of RVs. Consider m measurements denoted by X
i, i
=
1
,
…
,
m. Since m
a
x
1
≤
i
≤
m
X
i
=
-
m
i
n
1
≤
i
≤
m
(
-
X
i
), we will focus only on max  without loss of generality. It is easily seen that max function is divisible, thus the aggregation process is similar to that for sum: a node simply applies max function to the aggregated data. For example, suppose a node receives data given by X
1
,
…
,
X
m. The node simply computes m
a
x
i
=
1
,
…
,
m
X
i and forwards it to the next hop.For extreme-type summary functions, we will show thatϕ is in generalnot a CAF. In particular we consider several cases of practical importance.Case 1 (Gaussian RVs).
We consider the problem of retrieving the maximum of i.i.d. Gaussian RVs. We assume thatX
i
~
N
(
0,1
) for i
∈
S where we again assume that ϕ
(
m
)
=
α
+
b
+
h
(
m
a
x
i
=
1
,
…
,
m
[
X
i
]
) for m
≥
1 and some constant b. We provide a numerical evaluation of h
(
m
a
x
i
=
1
,
…
,
m
[
X
i
]
) on the left of Figure 2. We observe that ϕ
(
m
) is strictlyconvex anddecreasing in m for m
≥
1, thus ϕ is not a CAF.Figure 2
The differential entropy of the maximum of a set of i.i.d. RVs distributed according to an RVX. On the left, X
~
N
(
0,1
), and on the right, X is uniform on [
0,1
].
(a)
(b)Case 2 (Extreme data retrieval problem).
We consider the problem ofextreme data retrieval defined as follows. Assume that a source node i
∈
S measures some physical quantity which is distributed according to a continuous RV Y
i. We assume Y
i’s are independent but not necessarily identically distributed. Suppose with some probability Y
i is equal to a large number, which indicates an “abnormal” event. An important application of sensor networks is to detect the maximumabnormality among the measurements. The abnormality is defined as how far a sensor’s measurement has deviated from its usual statistics as follows. Let us denote the cumulative distribution function (CDF) of Y
i by F
i
(
·
) or P
(
Y
i
≤
y
)
=
F
i
(
y
), i
∈
S. Consider realizations of Y
1
,
…
,
Y
η given by y
1
,
…
,
y
η. We will quantify the abnormality at Source i in terms of howunlikely the measurement y
i is: specifically the goal of the sink is to retrieve m
i
n
i
∈
S
P
(
Y
i
>
y
i
), or alternatively,(24)
m
a
x
i
∈
S
F
i
y
i
,thus the abnormality of y
i is defined by F
i
(
y
i
). Let X
i
=
F
i
(
Y
i
). We will assume that the nodes transmit and aggregate X
i instead of Y
i, and the goal of the sink is to retrieve m
a
x
i
∈
S
X
i. Note since X
i
=
F
i
(
Y
i
) is the RV evaluated at its distribution function, one can show that X
i’s are i.i.d. RVs uniformly distributed on [
0,1
]. Thus the problem reduces to an optimal aggregation problem retrieving max  of i.i.d. uniform RVs.We will show thatϕ associated with the extreme data retrieval problem isconvex anddecreasing function when the number of aggregated measurements is greater than or equal to 2. Suppose the data aggregated at a node is given by X
1
,
…
,
X
m and define Z
m
:
=
m
a
x
i
=
1
,
…
,
m
X
i. As previously we assume that the node requires on average ϕ
(
m
)
=
α
+
b
+
h
(
Z
m
) bits to transmit Z
m.Proposition 4.
Consider the extreme data retrieval problem. The aggregation cost functionϕ
(
m
) is convex and decreasing for m
≥
2.Proof.
SinceZ
m is the maximum of m i.i.d. uniform RV’s, the CDF of Z
m denoted by F
Z
m
(
·
) is given by(25)
F
Z
m
z
=
z
m
.Thus the probability density function (pdf) of Z
m denoted by f
Z
m is given by m
z
m
-
1. If we compute h
(
Z
m
),(26)
h
Z
m
=
-
∫
0
1
‍
f
Z
m
z
l
o
g
f
Z
m
z
d
z
=
-
∫
0
1
‍
m
z
m
-
1
l
o
g
m
z
m
-
1
d
z
=
-
l
o
g
m
+
m
-
1
m
.Thus(27)
ϕ
m
=
α
+
b
-
l
o
g
m
+
1
-
m
-
1
,
m
≥
1
,
0
,
m
=
0
.By regarding m as a continuous variable, we have that, for m
≥
1,(28)
d
ϕ
d
m
=
-
1
m
+
1
m
2
,
d
2
ϕ
d
m
2
=
1
m
2
-
2
m
3
=
1
m
2
1
-
2
m
.Clearly ϕ
(
m
) is decreasing for m
≥
1, and since its second order derivative is nonnegative for m
≥
2, ϕ
(
m
) is convex for m
≥
2.On the right of Figure2 the plot of h
(
Z
m
) is shown. Note h
(
Z
m
) is strictly convex for m
≥
2, but overall appears to be approximately convex. Note that h
(
Z
m
) is nonpositive, thus one could select a sufficiently large b such that ϕ
(
η
)
=
α
+
b
+
h
(
Z
η
)
≥
0, so that ϕ
(
m
)
≥
0 for all 1
≤
m
≤
η.In general, for a convex and decreasingϕ, (
P
) is clearly NP-hard since the problem contains the Steiner tree problem as a special case. In the following section we present a novel algorithm which captures key properties of convex and decreasing ϕ. Later we show by simulation the algorithm effectively achieves low cost.


### 5.2. Algorithm for Convex and Decreasing Aggregation Cost Functions

#### 5.2.1. Motivation

Before we describe our algorithm we present the motivation behind the algorithm. An important observation for the data aggregation problems was made in [25] forconcave andincreasing
ϕ. They proposed a “hub-and-spoke” model for so-calledfacility location problem. The idea is that when ϕ is concave and increasing, one should first aggregate flows to some “hubs,” then route the aggregated flow from the hubs to the sink at the minimum cost; this is done by building an approximately optimal Steiner tree where the hubs (facility locations) are the Steiner nodes. The rationale is that, once multiple flows are aggregated at hubs, the cost of routing them collectively to the sink is cheaper than routing the sources’ flows separately, due to the concavity of ϕ. We observe two aspects in such hub-and-spoke schemes. Firstly by local aggregation of flows at hubs we aim at greedily reducing costs based on local information, which we view as themicroscopic approach to reduce cost. Secondly by building an approximately optimal Steiner tree with respect to the hubs and the sink, we take theglobal network structure into account, which can thus be seen as themacroscopic aspect for cost reduction. Hence there exists a tradeoff between microscopic and macroscopic aspects of the cost reduction. A similar observation on such tradeoff was made in [12]. However our key question is that, how do we achieve an optimal tradeoff between those aspects for aconvex anddecreasing
ϕ?Consider the three examples of aggregation cost functions denoted byϕ
1, ϕ
2, and ϕ
3 which are decreasing and convex for m
≥
1 as shown in Figure 3. In case of ϕ
1, we see that ϕ
1 is flat for m
≥
1, that is, the average number of bits communicated over a link is constant irrespective of the number of flows passed through it. Thus, the minimum cost routing problem reduces to a Steiner tree problem, in which case a completely “macroscopic” solution is optimal. In case of ϕ
2, we see that ϕ
2 decreases slowly in m. Thus, the more number of flows merges at a link, it takes the less number of bits to transmit the merged information. Suppose we use the hub-and-spoke scheme to aggregate flows in a local manner. The amount of aggregated flows at a hub is at least 2: note that however, ϕ
2 is approximately “flat” for m
≥
2. This implies that, once more than two flows are aggregated, the benefits from further local flow aggregation will be negligible. Hence the optimal routing problem from the hubs to the sink approximately reduces to the Steiner tree problem! Thus one could expect that local aggregation (microscopic approach) followed by an optimal Steiner tree construction (macroscopic approach) would yield a good solution. Now let us consider ϕ
3. The overall rate of decrease of ϕ
3 is higher than that of ϕ
2. It appears that when the number of aggregated flows is significantly high, for example, m is greater than 6, ϕ
3 becomes effectively “flat.” This suggests that, one should keep aggregating flows until sufficient amount of flows, say 6, is aggregated, that is, the microscopic cost reduction should be applied formultiple times in a hierarchical manner, then build an optimal Steiner tree with respect to the aggregated sources, that is, applying macroscopic reduction.Figure 3
Aggregation cost functions which are convex and decreasing form
≥
1.
(a)
(b)
(c)The example provides us with some insights. Sinceϕ
(
m
) is convex decreasing, the marginal benefit of local aggregation is large for small m but decreases with increasing m. In other words, when m is small, that is, in the early stages of the overall aggregation process, one should focus on low-cost local aggregation in order to benefit from high rate of decrease of ϕ
(
m
) for small m. Meanwhile, once a large number of flows are aggregated, it pays to perform macroscopic cost reduction from there on by building the optimal Steiner trees since ϕ becomes more “flat” with increasing m. This suggests that there exists a tradeoff point at which such microscopic and macroscopic reduction are optimally balanced. Unfortunately it is difficult to know such a tradeoff point in advance. The proposed algorithm not only exploits both the microscopic and macroscopic aspects of cost reduction for a convex and decreasing ϕ, but also empirically searches for the optimal tradeoff point. Details are presented in the following section.


#### 5.2.2. Outline

An outline of the proposed algorithm is presented as follows. The algorithm consists of multiple stages. A hub-and-spoke problem (or facility location problem) is approximately solved at each stage. The flows from source nodes are merged at the hubs. The hubs at the present stage become the source nodes in the next stage, that is, the flows are merged hierarchically. Instead of solving complex facility location problem, we find aminimum weight edge cover (MWEC) on the source nodes at each stage as a simple approximation. The rationale is that we would like to cluster sources for local aggregation at low costs, and by definition the MWEC incurs low cost in doing that. MWEC consists of multiple connected components, each of which is a tree. For each connected component we select a source as a hub and call it acenter node (details on the selection of center nodes are provided later). The flows in that component is aggregated at the center node.At each stage, once the center nodes are determined, we build an approximately optimal Steiner tree with respect to the center nodes and the sink. We use algorithm in [36] for the Steiner tree construction. Their algorithm provides the best known ρ
S-approximation for Steiner tree problem where ρ
S
≈
1.39.Each stage outputs an aggregation tree. The output tree at Stagei is theunion of the paths from all the hierarchical aggregations found up to Stage i and the Steiner tree built at Stage i. Namely, the output tree at Stage i is a combination of i
consecutive hierarchical aggregations (microscopic cost reduction) and a Steiner tree with respect to the sink and Stage i hubs (macroscopic cost reduction).Hence, over the stages, the algorithm progressively changes the balance between microscopic and macroscopic aspects of cost reduction in the output trees. Roughly speaking, the output trees from later stages are more biased towards the microscopic aspect. After the stages are over, we pick the tree with the minimum cost among the output trees. As a result the algorithm empirically searches for the point of the “best” balance between the two aspects of cost reduction over the stages. Hence one could expect that our algorithm will work well for any convex and decreasingϕ.


#### 5.2.3. Algorithm Description

We present a formal description of the proposed algorithm followed by an explanation of further details. For given aggregation treeT
⊆
G, let c
(
T
) denote the total energy cost associated with T, as in the objective of (
P
).Hierarchical Cover and Steiner Tree (HCST) AlgorithmBegin Algorithm(1)
(Metric completion ofG) If G is not a complete graph, perform a metric completion of G to yield a complete graph. Namely, if there exist any pair of vertices without an edge, create an edge between the pair and assign the edge a weight which is the distance between the pair. The distance is measured in terms of the sum of the weights on the shortest path between the pair.
(2)
(Initialization)i
←
0, S
0
←
S.
(3)
(Initialize flows at sources)f
u
←
1, for all u
∈
S.
(4)
(Initial output is a Steiner tree) Jump to Step 7.
(5)
(Minimum weight edge cover) Let us denote the subgraph ofG induced by S
i
-
1 by G
s. Find a minimum-weight edge cover M
i in G
s. Let C
i
=
(
S
i
-
1
,
M
i
) be the subgraph of G induced by the cover.
(6)
(Node selection) SupposeC
i has ν connected components, and denote the jth connected component of C
i by K
j
=
(
V
j
,
E
j
) for 1
≤
j
≤
ν. For each K
j, select a node with the maximum degree (ties are arbitrarily broken), say u
j, which is called acenter node. K
j is a tree, and u
j becomes the root of K
j. All the flows in K
j are aggregated at u
j such that every node transmits data to its parent node after the data from its child nodes has been aggregated at the node. The total flow at u
j is updated as follows:(29)
f
u
j
⟵
∑
u
∈
V
j
‍
f
u
.
Remove all the noncenter nodes fromS
i
-
1, and let S
i be the resulting set of source nodes.
(7)
(Steiner tree construction) Buildρ
S-optimal Steiner tree T
i
s with respect to the source nodes in S
i and the sink, using the algorithm in [36].
(8)
(Merging trees) Ifi
>
0, merge all the MWECs found up to the present stage and the Steiner tree found in Step 7; that is, let(30)
T
i
⟵
T
i
s
∪
⋃
j
=
1
i
‍
C
j
.
Ifi
=
0, T
0
←
T
0
s. We call T
i the output tree of Stage i.
(9)
(Loop) If|
S
i
|
>
1, i
←
i
+
1 and go back to Step 5. If |
S
i
|
=
1, continue to Step 10.
(10)
(Tree selection) The final output is the treeT
j
∗ such that(31)
j
∗
=
argmin
j
=
0
,
…
,
i
⁡
c
T
j
,
that is, the minimum cost tree among the output trees from all the stages.End Algorithm


#### 5.2.4. Comments

We explain the details of several steps in the algorithm. In Step 3 the flow variables denoted byf
u, u
∈
S, associated with the source nodes are initialized where we will track the amount of flows throughout the algorithm. In Step 6 it is natural to select a node with the maximum degree as the center node, since such node is literally a “hub.” When solving the hub-and-spoke problem at each stage, we choose to solve the MWEC problem whereas in [25] the load-balanced facility location problem is solved. An advantage of solving MWEC problem is that it is considerably simpler than load-balanced facility location problems since an MWEC problem can be reduced to a minimum weight perfect matching problem [37]. Note that the algorithm in [25] solves the hub-and-spoke problem only once, that is, its output is analogous to the output tree from Stage 1 of our algorithm. Meanwhile HM algorithm solves minimum weight perfect matching at each stage in order to locally aggregate flows with low costs. HM algorithm solves the matching problem hierarchically until all the flows are aggregated to a single source, and the final output is the union of those matchings. Thus its final output is analogous to that from the final stage of our algorithm. In other words, the outputs of the abovementioned algorithms correspond to those from intermediate stages in our algorithm. The HIERARCHY algorithm proposed in [20] hierarchically constructs Steiner trees and solves load-balanced facility location problems, however in a way which heavily relies on the concave and increasing property of ϕ. Thus the algorithm may not be suitable for convex and decreasing ϕ.


### 5.3. Performance Analysis

In this section we analyze the performance of HCST algorithm. For setE of weighted edges, let E denote the sum of its edge weights, that is, ∑
e
∈
E
w
e. For given source set Σ, let T
S
(
Σ
) denote the edge set of the optimal Steiner tree associated with Σ.Proposition 5.
For given network graphG
=
(
V
,
E
), the cost achieved by HCST algorithm is higher than the optimal algorithm by a factor of at most B defined as(32)
B
:
=
1
ϕ
Z
·
m
i
n
i
=
0
,
…
,
I
ϕ
2
i
ρ
S
+
∑
k
=
1
i
‍
ϕ
2
k
-
1
ρ
k
,where I
(
I
≤
l
o
g
2
η
) denotes the stage at which HCST algorithm terminates. ρ
S
≈
1.39 denotes the approximation ratio for Steiner tree problem, and ρ
i
∈
[
0,1
] is the ratio of the sums of edge weights between MWEC M
i at Stage i of HCST algorithm and the Steiner tree associated with source set S, that is,(33)
ρ
i
=
M
i
T
S
S
.Also Z is defined as(34)
Z
:
=
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
0
n
-
η
/
2
-
1
‍
w
|
E
|
-
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
0
n
-
η
/
2
-
1
‍
w
|
E
|
-
i
,where n
:
=
V, and w
[
i
] denotes the ith smallest value of the edge weights of G. Note that the second summation term of (32) is defined to be 0 if i
=
0.Proof.
Denote the optimal cost byO
P
T. We first find a lower bound for O
P
T. Let T
∗ denote the set of edges of the optimal aggregation tree. Let us sort the amount of edge flows of T
∗ in increasing order, and denote them by d
i, that is, 0
<
d
1
≤
d
2
≤
⋯
≤
d
l where T
∗ has l edges. There are at least η nonzero flows since there are η sources, hence d
η
>
0 and l
≥
η hold. In addition l is at most n, since T
∗ is a tree. Also it is clear that d
i
≤
i, for i
=
1
,
…
,
η, and d
i is at most η for η
<
i
≤
l. This implies that, since ϕ is decreasing, ϕ
(
d
i
)
≥
ϕ
(
i
), i
=
1
,
…
,
η. Let us denote the weight of the edge that carries flow d
i by v
i. For real numbers a and b, let a
∧
b
:
=
m
i
n
(
a
,
b
). We have that(35)
O
P
T
=
∑
i
=
1
l
‍
v
i
ϕ
d
i
≥
∑
i
=
1
l
‍
v
i
ϕ
i
∧
η
(36)
O
P
T
≥
∑
i
=
1
l
‍
v
i
ϕ
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
(37)
O
P
T
≥
T
S
S
ϕ
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
,where (36) is by Jensen’s inequality due to the convexity of ϕ, and (37) is from the definition of Steiner trees. Considering that ϕ is decreasing, we would like to make the argument of ϕ in (37) as large as possible in order to find a lower bound for O
P
T. Hence we would like to maximize λ
(
v
1
,
…
,
v
l
) defined as(38)
λ
v
1
,
…
,
v
l
:
=
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
,where v
i, i
=
1
,
…
,
l are chosen from the edge weights of G. For the purpose of maximizing (38), we will assume v
1
≤
v
2
≤
⋯
≤
v
l WLOG, because over all possible permutations π
(
1
)
,
π
(
2
)
,
…
,
π
(
l
) of {
1,2
,
…
,
l
}, ∑
i
‍
(
i
∧
η
)
v
π
(
i
) is maximized when v
π
(
1
)
≤
v
π
(
2
)
≤
⋯
≤
v
π
(
l
).
We first observe thatλ
(
·
) is decreasing in v
1
,
…
,
v
η
/
2, since if k
≤
η
/
2, we have that(39)
∂
λ
∂
v
k
=
k
∑
i
‍
v
i
-
∑
i
‍
i
∧
η
v
i
∑
i
‍
v
i
2
=
∑
j
=
1
k
-
1
‍
k
-
j
v
j
-
v
2
k
-
j
+
∑
j
=
2
k
l
‍
k
-
j
∧
η
v
j
∑
i
‍
v
i
2
≤
0
.Hence λ
(
·
) can be maximized over v
1
,
…
,
v
η
/
2 by choosing η
/
2 smallest weights from the edge weights of G, that is, by letting v
i
=
w
[
i
] for i
=
1
,
…
,
η
/
2.
Next we would like to derive an upper bound forλ
(
w
[
1
]
,
…
,
w
[
η
/
2
]
,
v
η
/
2
+
1
,
…
,
v
l
) as follows:(40)
λ
w
1
,
…
,
w
η
/
2
,
v
η
/
2
+
1
,
…
,
v
l
=
∑
i
=
1
η
/
2
‍
i
w
i
+
∑
i
=
η
/
2
+
1
l
‍
i
∧
η
v
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
η
/
2
+
1
l
‍
v
i
(41)
≤
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
η
/
2
+
1
l
‍
v
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
η
/
2
+
1
l
‍
v
i
(42)
≤
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
0
n
-
η
/
2
-
1
‍
w
E
-
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
0
n
-
η
/
2
-
1
‍
w
E
-
i
.For inequality (42), we used the fact that (41) is increasing in ∑
i
=
η
/
2
+
1
l
‍
v
i, hence we chose l
=
n and the largest possible weights w
[
|
E
|
]
,
w
[
|
E
|
-
1
]
,
… for v
η
/
2
+
1
,
v
η
/
2
+
2
,
…, in order to maximize ∑
i
=
η
/
2
+
1
l
‍
v
i. From (42), we obtain λ
(
v
1
,
…
,
v
l
)
≤
Z. Hence from (37), we obtain(43)
O
P
T
≥
T
S
S
ϕ
Z
.
Now let us consider the cost of output tree at Stagei of HCST algorithm, or c
(
T
i
). Recall that in HCST algorithm, S
i denotes the source set at Stage i, and T
i denotes the output tree at Stage i. The cost of T
i is divided into (i) the cost incurred by hierarchical MWECs M
1
,
…
,
M
i, and (ii) the cost of ρ
S-approximate Steiner tree T
i
s associated with S
i. Hence(44)
c
T
i
=
∑
k
=
1
i
‍
∑
e
∈
M
k
‍
w
e
ϕ
d
e
+
∑
e
∈
T
i
s
‍
w
e
ϕ
d
e
,where d
(
e
) denote the amount of flow at Edge e under HCST algorithm. Note that, the amount of flow in the network at Stage i is at least 2
i
-
1, since the flows are agglomerated through MWECs at every stage. Since ϕ
(
·
) is decreasing, the first summation of (44) is at most(45)
∑
k
=
1
i
‍
ϕ
2
k
-
1
∑
e
∈
M
k
‍
w
e
=
∑
k
=
1
i
‍
ϕ
2
k
-
1
M
k
.Note that the first summation of (44) is 0 for Stage 0. As for the second summation of (44),(46)
∑
e
∈
T
i
s
‍
w
e
ϕ
d
e
≤
ϕ
2
i
T
i
s
(47)
≤
ρ
S
ϕ
2
i
T
S
S
i
(48)
≤
ρ
S
ϕ
2
i
T
S
S
.Inequality (48) is due to S
i
⊆
S; specifically, the Steiner tree for S is a tree that spans S
i, hence by definition, the sum of edge weights of T
S
(
S
i
) is no more than that of the Steiner tree associated with S.
In conclusion, we have that, from (43), (45) and (48),(49)
c
T
i
≤
ρ
S
ϕ
2
i
T
S
S
+
∑
k
=
1
i
-
1
‍
ϕ
2
k
-
1
M
k
≤
O
P
T
ϕ
Z
ρ
S
ϕ
2
i
+
∑
k
=
1
i
‍
ϕ
2
k
-
1
M
k
T
S
S
.Since the cost of HCST algorithm is m
i
n
i
=
0
,
…
,
I
c
(
T
i
), the proposition is proved.An interpretation for ratioB in (32) is as follows: the first term in the bracket of B represents a bound on the macroscopic cost associated with the Steiner tree approximation. The second term in the bracket of B is a bound on the cost associated with the hierarchical aggregation of flows, that is, the microscopic cost reduction. Clearly we have that M
1
≥
M
2
≥
⋯, due to S
1
⊇
S
2
⊇
⋯, thus ρ
1
,
ρ
2
,
…, is a decreasing sequence where 0
≤
ρ
i
≤
1, for all i. The progressive cost reduction due to hierarchical flow aggregation is reflected in ρ
1
,
ρ
2
,
…. As in (32), B is the minimum of I
+
1 numbers, each of which contains a weighted sum of ϕ
(
·
) in different combination of weights ρ
i. Hence B represents the empirical minimum of different degrees of tradeoff between microscopic and macroscopic cost reduction.Next we discuss constantZ in (34). Firstly observe that Z
≤
η; the first summation of the numerator of (34) is at most η
∑
i
=
1
η
/
2
‍
v
i, in which case the first term of (34) is at most η. Note that a naive upper bound for λ
(
v
1
,
…
,
v
n
) is simply η, yielding a lower bound O
P
T
≥
T
S
(
S
)
ϕ
(
η
); however we observe that our bound (43) improves such a bound since ϕ
(
Z
)
≥
ϕ
(
η
).B can be numerically computed for a given graph, and in the next section we provide numerical examples of B. We also apply HCST algorithm to a specific graph as an example.


### 5.4. Illustrating Examples

In this section we consider a simple convex and decreasingϕ. As previously the packet header length is α bits, and we assume that the maximum packet size is 10 times the header length, that is, 10
α. We will accordingly consider ϕ
(
m
) which is convex and decreasing for m
≥
1 of the following form:(50)
ϕ
m
=
9
α
m
-
1
+
α
,
m
≥
1
,
0
,
m
=
0
.Clearly α
<
ϕ
(
m
)
≤
10
α holds for m
≥
1.Figures4 and 5 show the numerical examples of the performance bound B. B is computed and averaged over randomly generated graphs of uniformly distributed nodes in a square area. In Figure 4, network size n is fixed to 200, and B is plotted against the number of source nodes η. We consider two types of cost functions: the curve labelled “harmonic” represents the cost function (50) in which ϕ
(
·
) decreases as a harmonic sequence. The curve labelled “exp” corresponds to the case where the term m
-
1 in (50) is replaced by e
x
p
(
-
δ
(
m
-
1
)
) where the parameter δ
>
0 controls the decay rates of the cost function. We set δ
=
0.2 in this example. In addition, we compare B with a simple analytical bound; suppose we build a ρ
S-approximate Steiner tree based on S. The cost under that tree is at most ρ
S
T
S
(
S
)
ϕ
(
1
). By combining that cost with (43), we obtain a simple approximation ratio of ρ
S
ϕ
(
1
)
/
ϕ
(
Z
) for the approximately optimal Steiner tree. In Figure 4, the plots of such bounds based on ρ
S-approximate Steiner tree are added for both harmonic and exponential cost functions, and are labelled as “Steiner(har)” and “Steiner(exp),” respectively. We observe that B provides improved bounds as compared to those based on ρ-approximate Steiner tree. In Figure 5, B is plotted against varying n under the aforementioned harmonic and exponential cost function where we fixed δ to 10. In Figures 4 and 5, we observe that B eventually becomes nearly constant, or increases very slowly at most, even if the system size grows. Hence we conclude that B provides an approximation ratio which remains effectively constant irrespective of the system size.Figure 4
Performance bounds under varying number of sources.Figure 5
Performance bounds under varying network sizes.Next we present an example of the application of the HCST algorithm to a specific graph. An example ofG is given in Figure 6(a). G consists of n
=
10 nodes where Node 1 is the sink, that is, t
=
1. There are four source nodes: S
=
{
2,3
,
4,5
} where the sources are depicted in a shaded color. Each source generates 1 unit of data. We will again consider convex and decreasing ϕ
(
·
) given by (50), and assume α
=
1. Figure 6(b) shows the output of Stage 0 or T
0 which is an approximately optimal Steiner tree. Figure 7 shows the MWECs over the stages. Figure 7(a) shows the metric completion of the subgraph induced by S. Figure 7(b) shows the MWEC at Stage 1. Node 4 and 5 became the center nodes as emphasized in the figure. Figure 7(c) shows the MWEC and the center node at Stage 2.Figure 6
(a)G in the example. (b) The output T
0 from Stage 0.
(a)
(b)Figure 7
(a) A complete graph of the sources. (b) MWEC from Stage 1. (c) MWEC from Stage 2.
(a)
(b)
(c)Figure8(a) shows the full paths of the MWEC at Stage 1, that is, that in Figure 7(b), in G. By building an approximately optimal Steiner tree T
1
s associated with {
1,4
,
5
} and taking the union of T
1
s and C
1 as in Step 8, we get T
1 as in Figure 8(b). Similarly Figure 9 demonstrates Stage 2 of the algorithm. The full paths for the MWEC from Figure 7(c) in G are shown in Figure 9(a). Note that Node 4 is selected as the center node, and the output from Stage 2 or T
2 is shown in Figure 9(b). Let us compare the energy costs from all the stages. For T
0, a total of three flows pass through the link between Node 1 and 3, while the flow on the other links is simply 1. Thus, the cost of T
0 from Stage 0 is given by(51)
c
T
0
=
8
×
ϕ
3
+
8
+
6
+
5
+
10
×
ϕ
1
=
8
×
10
+
29
×
4
=
322
.Similarly, we have that(52)
c
T
1
=
314.8
,
c
T
2
=
275.5
.Thus the final output of HCST is T
2 with the final cost of 275.5. Note that in this example, the Shortest Path Tree (SPT) heuristic incurs the energy cost of 374.Figure 8
(a) MWEC inG from Stage 1. (b) The output T
1 from Stage 1.
(a)
(b)Figure 9
(a) MWEC inG from Stage 2. (b) The output T
2 from Stage 2.
(a)
(b)Next considerϕ
(
m
) such that(53)
ϕ
m
=
1
,
m
≥
1
,
0
,
m
=
0
.Assume that the algorithm has yielded the same T
0, T
1 and T
2 as the previous case. Since ϕ is constant for m
≥
1, the problem reduces to the Steiner tree problem, thus one would expect that T
0 would perform the best since T
0 is intended to be an approximately optimal Steiner tree. The energy costs are given by(54)
c
T
0
=
37
,
c
T
1
=
44
,
c
T
2
=
43
;thus indeed the HCST algorithm will output T
0 as the best solution with cost 37, whereas the SPT heuristic will yield the energy cost of 41. This demonstrates that our algorithm can effectively deal with various types of convex and decreasing aggregation cost functions. In the following section we will evaluate the performance of the HCST algorithm by simulation.


## 5.1. Case Study

In this section we consider summary functions regarding the extreme statistics of measurements, that is,max  or min. We will first investigate the entropy of the extreme statistics of a set of RVs. Consider m measurements denoted by X
i, i
=
1
,
…
,
m. Since m
a
x
1
≤
i
≤
m
X
i
=
-
m
i
n
1
≤
i
≤
m
(
-
X
i
), we will focus only on max  without loss of generality. It is easily seen that max function is divisible, thus the aggregation process is similar to that for sum: a node simply applies max function to the aggregated data. For example, suppose a node receives data given by X
1
,
…
,
X
m. The node simply computes m
a
x
i
=
1
,
…
,
m
X
i and forwards it to the next hop.For extreme-type summary functions, we will show thatϕ is in generalnot a CAF. In particular we consider several cases of practical importance.Case 1 (Gaussian RVs).
We consider the problem of retrieving the maximum of i.i.d. Gaussian RVs. We assume thatX
i
~
N
(
0,1
) for i
∈
S where we again assume that ϕ
(
m
)
=
α
+
b
+
h
(
m
a
x
i
=
1
,
…
,
m
[
X
i
]
) for m
≥
1 and some constant b. We provide a numerical evaluation of h
(
m
a
x
i
=
1
,
…
,
m
[
X
i
]
) on the left of Figure 2. We observe that ϕ
(
m
) is strictlyconvex anddecreasing in m for m
≥
1, thus ϕ is not a CAF.Figure 2
The differential entropy of the maximum of a set of i.i.d. RVs distributed according to an RVX. On the left, X
~
N
(
0,1
), and on the right, X is uniform on [
0,1
].
(a)
(b)Case 2 (Extreme data retrieval problem).
We consider the problem ofextreme data retrieval defined as follows. Assume that a source node i
∈
S measures some physical quantity which is distributed according to a continuous RV Y
i. We assume Y
i’s are independent but not necessarily identically distributed. Suppose with some probability Y
i is equal to a large number, which indicates an “abnormal” event. An important application of sensor networks is to detect the maximumabnormality among the measurements. The abnormality is defined as how far a sensor’s measurement has deviated from its usual statistics as follows. Let us denote the cumulative distribution function (CDF) of Y
i by F
i
(
·
) or P
(
Y
i
≤
y
)
=
F
i
(
y
), i
∈
S. Consider realizations of Y
1
,
…
,
Y
η given by y
1
,
…
,
y
η. We will quantify the abnormality at Source i in terms of howunlikely the measurement y
i is: specifically the goal of the sink is to retrieve m
i
n
i
∈
S
P
(
Y
i
>
y
i
), or alternatively,(24)
m
a
x
i
∈
S
F
i
y
i
,thus the abnormality of y
i is defined by F
i
(
y
i
). Let X
i
=
F
i
(
Y
i
). We will assume that the nodes transmit and aggregate X
i instead of Y
i, and the goal of the sink is to retrieve m
a
x
i
∈
S
X
i. Note since X
i
=
F
i
(
Y
i
) is the RV evaluated at its distribution function, one can show that X
i’s are i.i.d. RVs uniformly distributed on [
0,1
]. Thus the problem reduces to an optimal aggregation problem retrieving max  of i.i.d. uniform RVs.We will show thatϕ associated with the extreme data retrieval problem isconvex anddecreasing function when the number of aggregated measurements is greater than or equal to 2. Suppose the data aggregated at a node is given by X
1
,
…
,
X
m and define Z
m
:
=
m
a
x
i
=
1
,
…
,
m
X
i. As previously we assume that the node requires on average ϕ
(
m
)
=
α
+
b
+
h
(
Z
m
) bits to transmit Z
m.Proposition 4.
Consider the extreme data retrieval problem. The aggregation cost functionϕ
(
m
) is convex and decreasing for m
≥
2.Proof.
SinceZ
m is the maximum of m i.i.d. uniform RV’s, the CDF of Z
m denoted by F
Z
m
(
·
) is given by(25)
F
Z
m
z
=
z
m
.Thus the probability density function (pdf) of Z
m denoted by f
Z
m is given by m
z
m
-
1. If we compute h
(
Z
m
),(26)
h
Z
m
=
-
∫
0
1
‍
f
Z
m
z
l
o
g
f
Z
m
z
d
z
=
-
∫
0
1
‍
m
z
m
-
1
l
o
g
m
z
m
-
1
d
z
=
-
l
o
g
m
+
m
-
1
m
.Thus(27)
ϕ
m
=
α
+
b
-
l
o
g
m
+
1
-
m
-
1
,
m
≥
1
,
0
,
m
=
0
.By regarding m as a continuous variable, we have that, for m
≥
1,(28)
d
ϕ
d
m
=
-
1
m
+
1
m
2
,
d
2
ϕ
d
m
2
=
1
m
2
-
2
m
3
=
1
m
2
1
-
2
m
.Clearly ϕ
(
m
) is decreasing for m
≥
1, and since its second order derivative is nonnegative for m
≥
2, ϕ
(
m
) is convex for m
≥
2.On the right of Figure2 the plot of h
(
Z
m
) is shown. Note h
(
Z
m
) is strictly convex for m
≥
2, but overall appears to be approximately convex. Note that h
(
Z
m
) is nonpositive, thus one could select a sufficiently large b such that ϕ
(
η
)
=
α
+
b
+
h
(
Z
η
)
≥
0, so that ϕ
(
m
)
≥
0 for all 1
≤
m
≤
η.In general, for a convex and decreasingϕ, (
P
) is clearly NP-hard since the problem contains the Steiner tree problem as a special case. In the following section we present a novel algorithm which captures key properties of convex and decreasing ϕ. Later we show by simulation the algorithm effectively achieves low cost.


## 5.2. Algorithm for Convex and Decreasing Aggregation Cost Functions

### 5.2.1. Motivation

Before we describe our algorithm we present the motivation behind the algorithm. An important observation for the data aggregation problems was made in [25] forconcave andincreasing
ϕ. They proposed a “hub-and-spoke” model for so-calledfacility location problem. The idea is that when ϕ is concave and increasing, one should first aggregate flows to some “hubs,” then route the aggregated flow from the hubs to the sink at the minimum cost; this is done by building an approximately optimal Steiner tree where the hubs (facility locations) are the Steiner nodes. The rationale is that, once multiple flows are aggregated at hubs, the cost of routing them collectively to the sink is cheaper than routing the sources’ flows separately, due to the concavity of ϕ. We observe two aspects in such hub-and-spoke schemes. Firstly by local aggregation of flows at hubs we aim at greedily reducing costs based on local information, which we view as themicroscopic approach to reduce cost. Secondly by building an approximately optimal Steiner tree with respect to the hubs and the sink, we take theglobal network structure into account, which can thus be seen as themacroscopic aspect for cost reduction. Hence there exists a tradeoff between microscopic and macroscopic aspects of the cost reduction. A similar observation on such tradeoff was made in [12]. However our key question is that, how do we achieve an optimal tradeoff between those aspects for aconvex anddecreasing
ϕ?Consider the three examples of aggregation cost functions denoted byϕ
1, ϕ
2, and ϕ
3 which are decreasing and convex for m
≥
1 as shown in Figure 3. In case of ϕ
1, we see that ϕ
1 is flat for m
≥
1, that is, the average number of bits communicated over a link is constant irrespective of the number of flows passed through it. Thus, the minimum cost routing problem reduces to a Steiner tree problem, in which case a completely “macroscopic” solution is optimal. In case of ϕ
2, we see that ϕ
2 decreases slowly in m. Thus, the more number of flows merges at a link, it takes the less number of bits to transmit the merged information. Suppose we use the hub-and-spoke scheme to aggregate flows in a local manner. The amount of aggregated flows at a hub is at least 2: note that however, ϕ
2 is approximately “flat” for m
≥
2. This implies that, once more than two flows are aggregated, the benefits from further local flow aggregation will be negligible. Hence the optimal routing problem from the hubs to the sink approximately reduces to the Steiner tree problem! Thus one could expect that local aggregation (microscopic approach) followed by an optimal Steiner tree construction (macroscopic approach) would yield a good solution. Now let us consider ϕ
3. The overall rate of decrease of ϕ
3 is higher than that of ϕ
2. It appears that when the number of aggregated flows is significantly high, for example, m is greater than 6, ϕ
3 becomes effectively “flat.” This suggests that, one should keep aggregating flows until sufficient amount of flows, say 6, is aggregated, that is, the microscopic cost reduction should be applied formultiple times in a hierarchical manner, then build an optimal Steiner tree with respect to the aggregated sources, that is, applying macroscopic reduction.Figure 3
Aggregation cost functions which are convex and decreasing form
≥
1.
(a)
(b)
(c)The example provides us with some insights. Sinceϕ
(
m
) is convex decreasing, the marginal benefit of local aggregation is large for small m but decreases with increasing m. In other words, when m is small, that is, in the early stages of the overall aggregation process, one should focus on low-cost local aggregation in order to benefit from high rate of decrease of ϕ
(
m
) for small m. Meanwhile, once a large number of flows are aggregated, it pays to perform macroscopic cost reduction from there on by building the optimal Steiner trees since ϕ becomes more “flat” with increasing m. This suggests that there exists a tradeoff point at which such microscopic and macroscopic reduction are optimally balanced. Unfortunately it is difficult to know such a tradeoff point in advance. The proposed algorithm not only exploits both the microscopic and macroscopic aspects of cost reduction for a convex and decreasing ϕ, but also empirically searches for the optimal tradeoff point. Details are presented in the following section.


### 5.2.2. Outline

An outline of the proposed algorithm is presented as follows. The algorithm consists of multiple stages. A hub-and-spoke problem (or facility location problem) is approximately solved at each stage. The flows from source nodes are merged at the hubs. The hubs at the present stage become the source nodes in the next stage, that is, the flows are merged hierarchically. Instead of solving complex facility location problem, we find aminimum weight edge cover (MWEC) on the source nodes at each stage as a simple approximation. The rationale is that we would like to cluster sources for local aggregation at low costs, and by definition the MWEC incurs low cost in doing that. MWEC consists of multiple connected components, each of which is a tree. For each connected component we select a source as a hub and call it acenter node (details on the selection of center nodes are provided later). The flows in that component is aggregated at the center node.At each stage, once the center nodes are determined, we build an approximately optimal Steiner tree with respect to the center nodes and the sink. We use algorithm in [36] for the Steiner tree construction. Their algorithm provides the best known ρ
S-approximation for Steiner tree problem where ρ
S
≈
1.39.Each stage outputs an aggregation tree. The output tree at Stagei is theunion of the paths from all the hierarchical aggregations found up to Stage i and the Steiner tree built at Stage i. Namely, the output tree at Stage i is a combination of i
consecutive hierarchical aggregations (microscopic cost reduction) and a Steiner tree with respect to the sink and Stage i hubs (macroscopic cost reduction).Hence, over the stages, the algorithm progressively changes the balance between microscopic and macroscopic aspects of cost reduction in the output trees. Roughly speaking, the output trees from later stages are more biased towards the microscopic aspect. After the stages are over, we pick the tree with the minimum cost among the output trees. As a result the algorithm empirically searches for the point of the “best” balance between the two aspects of cost reduction over the stages. Hence one could expect that our algorithm will work well for any convex and decreasingϕ.


### 5.2.3. Algorithm Description

We present a formal description of the proposed algorithm followed by an explanation of further details. For given aggregation treeT
⊆
G, let c
(
T
) denote the total energy cost associated with T, as in the objective of (
P
).Hierarchical Cover and Steiner Tree (HCST) AlgorithmBegin Algorithm(1)
(Metric completion ofG) If G is not a complete graph, perform a metric completion of G to yield a complete graph. Namely, if there exist any pair of vertices without an edge, create an edge between the pair and assign the edge a weight which is the distance between the pair. The distance is measured in terms of the sum of the weights on the shortest path between the pair.
(2)
(Initialization)i
←
0, S
0
←
S.
(3)
(Initialize flows at sources)f
u
←
1, for all u
∈
S.
(4)
(Initial output is a Steiner tree) Jump to Step 7.
(5)
(Minimum weight edge cover) Let us denote the subgraph ofG induced by S
i
-
1 by G
s. Find a minimum-weight edge cover M
i in G
s. Let C
i
=
(
S
i
-
1
,
M
i
) be the subgraph of G induced by the cover.
(6)
(Node selection) SupposeC
i has ν connected components, and denote the jth connected component of C
i by K
j
=
(
V
j
,
E
j
) for 1
≤
j
≤
ν. For each K
j, select a node with the maximum degree (ties are arbitrarily broken), say u
j, which is called acenter node. K
j is a tree, and u
j becomes the root of K
j. All the flows in K
j are aggregated at u
j such that every node transmits data to its parent node after the data from its child nodes has been aggregated at the node. The total flow at u
j is updated as follows:(29)
f
u
j
⟵
∑
u
∈
V
j
‍
f
u
.
Remove all the noncenter nodes fromS
i
-
1, and let S
i be the resulting set of source nodes.
(7)
(Steiner tree construction) Buildρ
S-optimal Steiner tree T
i
s with respect to the source nodes in S
i and the sink, using the algorithm in [36].
(8)
(Merging trees) Ifi
>
0, merge all the MWECs found up to the present stage and the Steiner tree found in Step 7; that is, let(30)
T
i
⟵
T
i
s
∪
⋃
j
=
1
i
‍
C
j
.
Ifi
=
0, T
0
←
T
0
s. We call T
i the output tree of Stage i.
(9)
(Loop) If|
S
i
|
>
1, i
←
i
+
1 and go back to Step 5. If |
S
i
|
=
1, continue to Step 10.
(10)
(Tree selection) The final output is the treeT
j
∗ such that(31)
j
∗
=
argmin
j
=
0
,
…
,
i
⁡
c
T
j
,
that is, the minimum cost tree among the output trees from all the stages.End Algorithm


### 5.2.4. Comments

We explain the details of several steps in the algorithm. In Step 3 the flow variables denoted byf
u, u
∈
S, associated with the source nodes are initialized where we will track the amount of flows throughout the algorithm. In Step 6 it is natural to select a node with the maximum degree as the center node, since such node is literally a “hub.” When solving the hub-and-spoke problem at each stage, we choose to solve the MWEC problem whereas in [25] the load-balanced facility location problem is solved. An advantage of solving MWEC problem is that it is considerably simpler than load-balanced facility location problems since an MWEC problem can be reduced to a minimum weight perfect matching problem [37]. Note that the algorithm in [25] solves the hub-and-spoke problem only once, that is, its output is analogous to the output tree from Stage 1 of our algorithm. Meanwhile HM algorithm solves minimum weight perfect matching at each stage in order to locally aggregate flows with low costs. HM algorithm solves the matching problem hierarchically until all the flows are aggregated to a single source, and the final output is the union of those matchings. Thus its final output is analogous to that from the final stage of our algorithm. In other words, the outputs of the abovementioned algorithms correspond to those from intermediate stages in our algorithm. The HIERARCHY algorithm proposed in [20] hierarchically constructs Steiner trees and solves load-balanced facility location problems, however in a way which heavily relies on the concave and increasing property of ϕ. Thus the algorithm may not be suitable for convex and decreasing ϕ.


## 5.2.1. Motivation

Before we describe our algorithm we present the motivation behind the algorithm. An important observation for the data aggregation problems was made in [25] forconcave andincreasing
ϕ. They proposed a “hub-and-spoke” model for so-calledfacility location problem. The idea is that when ϕ is concave and increasing, one should first aggregate flows to some “hubs,” then route the aggregated flow from the hubs to the sink at the minimum cost; this is done by building an approximately optimal Steiner tree where the hubs (facility locations) are the Steiner nodes. The rationale is that, once multiple flows are aggregated at hubs, the cost of routing them collectively to the sink is cheaper than routing the sources’ flows separately, due to the concavity of ϕ. We observe two aspects in such hub-and-spoke schemes. Firstly by local aggregation of flows at hubs we aim at greedily reducing costs based on local information, which we view as themicroscopic approach to reduce cost. Secondly by building an approximately optimal Steiner tree with respect to the hubs and the sink, we take theglobal network structure into account, which can thus be seen as themacroscopic aspect for cost reduction. Hence there exists a tradeoff between microscopic and macroscopic aspects of the cost reduction. A similar observation on such tradeoff was made in [12]. However our key question is that, how do we achieve an optimal tradeoff between those aspects for aconvex anddecreasing
ϕ?Consider the three examples of aggregation cost functions denoted byϕ
1, ϕ
2, and ϕ
3 which are decreasing and convex for m
≥
1 as shown in Figure 3. In case of ϕ
1, we see that ϕ
1 is flat for m
≥
1, that is, the average number of bits communicated over a link is constant irrespective of the number of flows passed through it. Thus, the minimum cost routing problem reduces to a Steiner tree problem, in which case a completely “macroscopic” solution is optimal. In case of ϕ
2, we see that ϕ
2 decreases slowly in m. Thus, the more number of flows merges at a link, it takes the less number of bits to transmit the merged information. Suppose we use the hub-and-spoke scheme to aggregate flows in a local manner. The amount of aggregated flows at a hub is at least 2: note that however, ϕ
2 is approximately “flat” for m
≥
2. This implies that, once more than two flows are aggregated, the benefits from further local flow aggregation will be negligible. Hence the optimal routing problem from the hubs to the sink approximately reduces to the Steiner tree problem! Thus one could expect that local aggregation (microscopic approach) followed by an optimal Steiner tree construction (macroscopic approach) would yield a good solution. Now let us consider ϕ
3. The overall rate of decrease of ϕ
3 is higher than that of ϕ
2. It appears that when the number of aggregated flows is significantly high, for example, m is greater than 6, ϕ
3 becomes effectively “flat.” This suggests that, one should keep aggregating flows until sufficient amount of flows, say 6, is aggregated, that is, the microscopic cost reduction should be applied formultiple times in a hierarchical manner, then build an optimal Steiner tree with respect to the aggregated sources, that is, applying macroscopic reduction.Figure 3
Aggregation cost functions which are convex and decreasing form
≥
1.
(a)
(b)
(c)The example provides us with some insights. Sinceϕ
(
m
) is convex decreasing, the marginal benefit of local aggregation is large for small m but decreases with increasing m. In other words, when m is small, that is, in the early stages of the overall aggregation process, one should focus on low-cost local aggregation in order to benefit from high rate of decrease of ϕ
(
m
) for small m. Meanwhile, once a large number of flows are aggregated, it pays to perform macroscopic cost reduction from there on by building the optimal Steiner trees since ϕ becomes more “flat” with increasing m. This suggests that there exists a tradeoff point at which such microscopic and macroscopic reduction are optimally balanced. Unfortunately it is difficult to know such a tradeoff point in advance. The proposed algorithm not only exploits both the microscopic and macroscopic aspects of cost reduction for a convex and decreasing ϕ, but also empirically searches for the optimal tradeoff point. Details are presented in the following section.


## 5.2.2. Outline

An outline of the proposed algorithm is presented as follows. The algorithm consists of multiple stages. A hub-and-spoke problem (or facility location problem) is approximately solved at each stage. The flows from source nodes are merged at the hubs. The hubs at the present stage become the source nodes in the next stage, that is, the flows are merged hierarchically. Instead of solving complex facility location problem, we find aminimum weight edge cover (MWEC) on the source nodes at each stage as a simple approximation. The rationale is that we would like to cluster sources for local aggregation at low costs, and by definition the MWEC incurs low cost in doing that. MWEC consists of multiple connected components, each of which is a tree. For each connected component we select a source as a hub and call it acenter node (details on the selection of center nodes are provided later). The flows in that component is aggregated at the center node.At each stage, once the center nodes are determined, we build an approximately optimal Steiner tree with respect to the center nodes and the sink. We use algorithm in [36] for the Steiner tree construction. Their algorithm provides the best known ρ
S-approximation for Steiner tree problem where ρ
S
≈
1.39.Each stage outputs an aggregation tree. The output tree at Stagei is theunion of the paths from all the hierarchical aggregations found up to Stage i and the Steiner tree built at Stage i. Namely, the output tree at Stage i is a combination of i
consecutive hierarchical aggregations (microscopic cost reduction) and a Steiner tree with respect to the sink and Stage i hubs (macroscopic cost reduction).Hence, over the stages, the algorithm progressively changes the balance between microscopic and macroscopic aspects of cost reduction in the output trees. Roughly speaking, the output trees from later stages are more biased towards the microscopic aspect. After the stages are over, we pick the tree with the minimum cost among the output trees. As a result the algorithm empirically searches for the point of the “best” balance between the two aspects of cost reduction over the stages. Hence one could expect that our algorithm will work well for any convex and decreasingϕ.


## 5.2.3. Algorithm Description

We present a formal description of the proposed algorithm followed by an explanation of further details. For given aggregation treeT
⊆
G, let c
(
T
) denote the total energy cost associated with T, as in the objective of (
P
).Hierarchical Cover and Steiner Tree (HCST) AlgorithmBegin Algorithm(1)
(Metric completion ofG) If G is not a complete graph, perform a metric completion of G to yield a complete graph. Namely, if there exist any pair of vertices without an edge, create an edge between the pair and assign the edge a weight which is the distance between the pair. The distance is measured in terms of the sum of the weights on the shortest path between the pair.
(2)
(Initialization)i
←
0, S
0
←
S.
(3)
(Initialize flows at sources)f
u
←
1, for all u
∈
S.
(4)
(Initial output is a Steiner tree) Jump to Step 7.
(5)
(Minimum weight edge cover) Let us denote the subgraph ofG induced by S
i
-
1 by G
s. Find a minimum-weight edge cover M
i in G
s. Let C
i
=
(
S
i
-
1
,
M
i
) be the subgraph of G induced by the cover.
(6)
(Node selection) SupposeC
i has ν connected components, and denote the jth connected component of C
i by K
j
=
(
V
j
,
E
j
) for 1
≤
j
≤
ν. For each K
j, select a node with the maximum degree (ties are arbitrarily broken), say u
j, which is called acenter node. K
j is a tree, and u
j becomes the root of K
j. All the flows in K
j are aggregated at u
j such that every node transmits data to its parent node after the data from its child nodes has been aggregated at the node. The total flow at u
j is updated as follows:(29)
f
u
j
⟵
∑
u
∈
V
j
‍
f
u
.
Remove all the noncenter nodes fromS
i
-
1, and let S
i be the resulting set of source nodes.
(7)
(Steiner tree construction) Buildρ
S-optimal Steiner tree T
i
s with respect to the source nodes in S
i and the sink, using the algorithm in [36].
(8)
(Merging trees) Ifi
>
0, merge all the MWECs found up to the present stage and the Steiner tree found in Step 7; that is, let(30)
T
i
⟵
T
i
s
∪
⋃
j
=
1
i
‍
C
j
.
Ifi
=
0, T
0
←
T
0
s. We call T
i the output tree of Stage i.
(9)
(Loop) If|
S
i
|
>
1, i
←
i
+
1 and go back to Step 5. If |
S
i
|
=
1, continue to Step 10.
(10)
(Tree selection) The final output is the treeT
j
∗ such that(31)
j
∗
=
argmin
j
=
0
,
…
,
i
⁡
c
T
j
,
that is, the minimum cost tree among the output trees from all the stages.End Algorithm


## 5.2.4. Comments

We explain the details of several steps in the algorithm. In Step 3 the flow variables denoted byf
u, u
∈
S, associated with the source nodes are initialized where we will track the amount of flows throughout the algorithm. In Step 6 it is natural to select a node with the maximum degree as the center node, since such node is literally a “hub.” When solving the hub-and-spoke problem at each stage, we choose to solve the MWEC problem whereas in [25] the load-balanced facility location problem is solved. An advantage of solving MWEC problem is that it is considerably simpler than load-balanced facility location problems since an MWEC problem can be reduced to a minimum weight perfect matching problem [37]. Note that the algorithm in [25] solves the hub-and-spoke problem only once, that is, its output is analogous to the output tree from Stage 1 of our algorithm. Meanwhile HM algorithm solves minimum weight perfect matching at each stage in order to locally aggregate flows with low costs. HM algorithm solves the matching problem hierarchically until all the flows are aggregated to a single source, and the final output is the union of those matchings. Thus its final output is analogous to that from the final stage of our algorithm. In other words, the outputs of the abovementioned algorithms correspond to those from intermediate stages in our algorithm. The HIERARCHY algorithm proposed in [20] hierarchically constructs Steiner trees and solves load-balanced facility location problems, however in a way which heavily relies on the concave and increasing property of ϕ. Thus the algorithm may not be suitable for convex and decreasing ϕ.


## 5.3. Performance Analysis

In this section we analyze the performance of HCST algorithm. For setE of weighted edges, let E denote the sum of its edge weights, that is, ∑
e
∈
E
w
e. For given source set Σ, let T
S
(
Σ
) denote the edge set of the optimal Steiner tree associated with Σ.Proposition 5.
For given network graphG
=
(
V
,
E
), the cost achieved by HCST algorithm is higher than the optimal algorithm by a factor of at most B defined as(32)
B
:
=
1
ϕ
Z
·
m
i
n
i
=
0
,
…
,
I
ϕ
2
i
ρ
S
+
∑
k
=
1
i
‍
ϕ
2
k
-
1
ρ
k
,where I
(
I
≤
l
o
g
2
η
) denotes the stage at which HCST algorithm terminates. ρ
S
≈
1.39 denotes the approximation ratio for Steiner tree problem, and ρ
i
∈
[
0,1
] is the ratio of the sums of edge weights between MWEC M
i at Stage i of HCST algorithm and the Steiner tree associated with source set S, that is,(33)
ρ
i
=
M
i
T
S
S
.Also Z is defined as(34)
Z
:
=
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
0
n
-
η
/
2
-
1
‍
w
|
E
|
-
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
0
n
-
η
/
2
-
1
‍
w
|
E
|
-
i
,where n
:
=
V, and w
[
i
] denotes the ith smallest value of the edge weights of G. Note that the second summation term of (32) is defined to be 0 if i
=
0.Proof.
Denote the optimal cost byO
P
T. We first find a lower bound for O
P
T. Let T
∗ denote the set of edges of the optimal aggregation tree. Let us sort the amount of edge flows of T
∗ in increasing order, and denote them by d
i, that is, 0
<
d
1
≤
d
2
≤
⋯
≤
d
l where T
∗ has l edges. There are at least η nonzero flows since there are η sources, hence d
η
>
0 and l
≥
η hold. In addition l is at most n, since T
∗ is a tree. Also it is clear that d
i
≤
i, for i
=
1
,
…
,
η, and d
i is at most η for η
<
i
≤
l. This implies that, since ϕ is decreasing, ϕ
(
d
i
)
≥
ϕ
(
i
), i
=
1
,
…
,
η. Let us denote the weight of the edge that carries flow d
i by v
i. For real numbers a and b, let a
∧
b
:
=
m
i
n
(
a
,
b
). We have that(35)
O
P
T
=
∑
i
=
1
l
‍
v
i
ϕ
d
i
≥
∑
i
=
1
l
‍
v
i
ϕ
i
∧
η
(36)
O
P
T
≥
∑
i
=
1
l
‍
v
i
ϕ
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
(37)
O
P
T
≥
T
S
S
ϕ
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
,where (36) is by Jensen’s inequality due to the convexity of ϕ, and (37) is from the definition of Steiner trees. Considering that ϕ is decreasing, we would like to make the argument of ϕ in (37) as large as possible in order to find a lower bound for O
P
T. Hence we would like to maximize λ
(
v
1
,
…
,
v
l
) defined as(38)
λ
v
1
,
…
,
v
l
:
=
∑
i
=
1
l
‍
i
∧
η
v
i
∑
i
=
1
l
‍
v
i
,where v
i, i
=
1
,
…
,
l are chosen from the edge weights of G. For the purpose of maximizing (38), we will assume v
1
≤
v
2
≤
⋯
≤
v
l WLOG, because over all possible permutations π
(
1
)
,
π
(
2
)
,
…
,
π
(
l
) of {
1,2
,
…
,
l
}, ∑
i
‍
(
i
∧
η
)
v
π
(
i
) is maximized when v
π
(
1
)
≤
v
π
(
2
)
≤
⋯
≤
v
π
(
l
).
We first observe thatλ
(
·
) is decreasing in v
1
,
…
,
v
η
/
2, since if k
≤
η
/
2, we have that(39)
∂
λ
∂
v
k
=
k
∑
i
‍
v
i
-
∑
i
‍
i
∧
η
v
i
∑
i
‍
v
i
2
=
∑
j
=
1
k
-
1
‍
k
-
j
v
j
-
v
2
k
-
j
+
∑
j
=
2
k
l
‍
k
-
j
∧
η
v
j
∑
i
‍
v
i
2
≤
0
.Hence λ
(
·
) can be maximized over v
1
,
…
,
v
η
/
2 by choosing η
/
2 smallest weights from the edge weights of G, that is, by letting v
i
=
w
[
i
] for i
=
1
,
…
,
η
/
2.
Next we would like to derive an upper bound forλ
(
w
[
1
]
,
…
,
w
[
η
/
2
]
,
v
η
/
2
+
1
,
…
,
v
l
) as follows:(40)
λ
w
1
,
…
,
w
η
/
2
,
v
η
/
2
+
1
,
…
,
v
l
=
∑
i
=
1
η
/
2
‍
i
w
i
+
∑
i
=
η
/
2
+
1
l
‍
i
∧
η
v
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
η
/
2
+
1
l
‍
v
i
(41)
≤
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
η
/
2
+
1
l
‍
v
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
η
/
2
+
1
l
‍
v
i
(42)
≤
∑
i
=
1
η
/
2
‍
i
w
i
+
η
∑
i
=
0
n
-
η
/
2
-
1
‍
w
E
-
i
∑
i
=
1
η
/
2
‍
w
i
+
∑
i
=
0
n
-
η
/
2
-
1
‍
w
E
-
i
.For inequality (42), we used the fact that (41) is increasing in ∑
i
=
η
/
2
+
1
l
‍
v
i, hence we chose l
=
n and the largest possible weights w
[
|
E
|
]
,
w
[
|
E
|
-
1
]
,
… for v
η
/
2
+
1
,
v
η
/
2
+
2
,
…, in order to maximize ∑
i
=
η
/
2
+
1
l
‍
v
i. From (42), we obtain λ
(
v
1
,
…
,
v
l
)
≤
Z. Hence from (37), we obtain(43)
O
P
T
≥
T
S
S
ϕ
Z
.
Now let us consider the cost of output tree at Stagei of HCST algorithm, or c
(
T
i
). Recall that in HCST algorithm, S
i denotes the source set at Stage i, and T
i denotes the output tree at Stage i. The cost of T
i is divided into (i) the cost incurred by hierarchical MWECs M
1
,
…
,
M
i, and (ii) the cost of ρ
S-approximate Steiner tree T
i
s associated with S
i. Hence(44)
c
T
i
=
∑
k
=
1
i
‍
∑
e
∈
M
k
‍
w
e
ϕ
d
e
+
∑
e
∈
T
i
s
‍
w
e
ϕ
d
e
,where d
(
e
) denote the amount of flow at Edge e under HCST algorithm. Note that, the amount of flow in the network at Stage i is at least 2
i
-
1, since the flows are agglomerated through MWECs at every stage. Since ϕ
(
·
) is decreasing, the first summation of (44) is at most(45)
∑
k
=
1
i
‍
ϕ
2
k
-
1
∑
e
∈
M
k
‍
w
e
=
∑
k
=
1
i
‍
ϕ
2
k
-
1
M
k
.Note that the first summation of (44) is 0 for Stage 0. As for the second summation of (44),(46)
∑
e
∈
T
i
s
‍
w
e
ϕ
d
e
≤
ϕ
2
i
T
i
s
(47)
≤
ρ
S
ϕ
2
i
T
S
S
i
(48)
≤
ρ
S
ϕ
2
i
T
S
S
.Inequality (48) is due to S
i
⊆
S; specifically, the Steiner tree for S is a tree that spans S
i, hence by definition, the sum of edge weights of T
S
(
S
i
) is no more than that of the Steiner tree associated with S.
In conclusion, we have that, from (43), (45) and (48),(49)
c
T
i
≤
ρ
S
ϕ
2
i
T
S
S
+
∑
k
=
1
i
-
1
‍
ϕ
2
k
-
1
M
k
≤
O
P
T
ϕ
Z
ρ
S
ϕ
2
i
+
∑
k
=
1
i
‍
ϕ
2
k
-
1
M
k
T
S
S
.Since the cost of HCST algorithm is m
i
n
i
=
0
,
…
,
I
c
(
T
i
), the proposition is proved.An interpretation for ratioB in (32) is as follows: the first term in the bracket of B represents a bound on the macroscopic cost associated with the Steiner tree approximation. The second term in the bracket of B is a bound on the cost associated with the hierarchical aggregation of flows, that is, the microscopic cost reduction. Clearly we have that M
1
≥
M
2
≥
⋯, due to S
1
⊇
S
2
⊇
⋯, thus ρ
1
,
ρ
2
,
…, is a decreasing sequence where 0
≤
ρ
i
≤
1, for all i. The progressive cost reduction due to hierarchical flow aggregation is reflected in ρ
1
,
ρ
2
,
…. As in (32), B is the minimum of I
+
1 numbers, each of which contains a weighted sum of ϕ
(
·
) in different combination of weights ρ
i. Hence B represents the empirical minimum of different degrees of tradeoff between microscopic and macroscopic cost reduction.Next we discuss constantZ in (34). Firstly observe that Z
≤
η; the first summation of the numerator of (34) is at most η
∑
i
=
1
η
/
2
‍
v
i, in which case the first term of (34) is at most η. Note that a naive upper bound for λ
(
v
1
,
…
,
v
n
) is simply η, yielding a lower bound O
P
T
≥
T
S
(
S
)
ϕ
(
η
); however we observe that our bound (43) improves such a bound since ϕ
(
Z
)
≥
ϕ
(
η
).B can be numerically computed for a given graph, and in the next section we provide numerical examples of B. We also apply HCST algorithm to a specific graph as an example.


## 5.4. Illustrating Examples

In this section we consider a simple convex and decreasingϕ. As previously the packet header length is α bits, and we assume that the maximum packet size is 10 times the header length, that is, 10
α. We will accordingly consider ϕ
(
m
) which is convex and decreasing for m
≥
1 of the following form:(50)
ϕ
m
=
9
α
m
-
1
+
α
,
m
≥
1
,
0
,
m
=
0
.Clearly α
<
ϕ
(
m
)
≤
10
α holds for m
≥
1.Figures4 and 5 show the numerical examples of the performance bound B. B is computed and averaged over randomly generated graphs of uniformly distributed nodes in a square area. In Figure 4, network size n is fixed to 200, and B is plotted against the number of source nodes η. We consider two types of cost functions: the curve labelled “harmonic” represents the cost function (50) in which ϕ
(
·
) decreases as a harmonic sequence. The curve labelled “exp” corresponds to the case where the term m
-
1 in (50) is replaced by e
x
p
(
-
δ
(
m
-
1
)
) where the parameter δ
>
0 controls the decay rates of the cost function. We set δ
=
0.2 in this example. In addition, we compare B with a simple analytical bound; suppose we build a ρ
S-approximate Steiner tree based on S. The cost under that tree is at most ρ
S
T
S
(
S
)
ϕ
(
1
). By combining that cost with (43), we obtain a simple approximation ratio of ρ
S
ϕ
(
1
)
/
ϕ
(
Z
) for the approximately optimal Steiner tree. In Figure 4, the plots of such bounds based on ρ
S-approximate Steiner tree are added for both harmonic and exponential cost functions, and are labelled as “Steiner(har)” and “Steiner(exp),” respectively. We observe that B provides improved bounds as compared to those based on ρ-approximate Steiner tree. In Figure 5, B is plotted against varying n under the aforementioned harmonic and exponential cost function where we fixed δ to 10. In Figures 4 and 5, we observe that B eventually becomes nearly constant, or increases very slowly at most, even if the system size grows. Hence we conclude that B provides an approximation ratio which remains effectively constant irrespective of the system size.Figure 4
Performance bounds under varying number of sources.Figure 5
Performance bounds under varying network sizes.Next we present an example of the application of the HCST algorithm to a specific graph. An example ofG is given in Figure 6(a). G consists of n
=
10 nodes where Node 1 is the sink, that is, t
=
1. There are four source nodes: S
=
{
2,3
,
4,5
} where the sources are depicted in a shaded color. Each source generates 1 unit of data. We will again consider convex and decreasing ϕ
(
·
) given by (50), and assume α
=
1. Figure 6(b) shows the output of Stage 0 or T
0 which is an approximately optimal Steiner tree. Figure 7 shows the MWECs over the stages. Figure 7(a) shows the metric completion of the subgraph induced by S. Figure 7(b) shows the MWEC at Stage 1. Node 4 and 5 became the center nodes as emphasized in the figure. Figure 7(c) shows the MWEC and the center node at Stage 2.Figure 6
(a)G in the example. (b) The output T
0 from Stage 0.
(a)
(b)Figure 7
(a) A complete graph of the sources. (b) MWEC from Stage 1. (c) MWEC from Stage 2.
(a)
(b)
(c)Figure8(a) shows the full paths of the MWEC at Stage 1, that is, that in Figure 7(b), in G. By building an approximately optimal Steiner tree T
1
s associated with {
1,4
,
5
} and taking the union of T
1
s and C
1 as in Step 8, we get T
1 as in Figure 8(b). Similarly Figure 9 demonstrates Stage 2 of the algorithm. The full paths for the MWEC from Figure 7(c) in G are shown in Figure 9(a). Note that Node 4 is selected as the center node, and the output from Stage 2 or T
2 is shown in Figure 9(b). Let us compare the energy costs from all the stages. For T
0, a total of three flows pass through the link between Node 1 and 3, while the flow on the other links is simply 1. Thus, the cost of T
0 from Stage 0 is given by(51)
c
T
0
=
8
×
ϕ
3
+
8
+
6
+
5
+
10
×
ϕ
1
=
8
×
10
+
29
×
4
=
322
.Similarly, we have that(52)
c
T
1
=
314.8
,
c
T
2
=
275.5
.Thus the final output of HCST is T
2 with the final cost of 275.5. Note that in this example, the Shortest Path Tree (SPT) heuristic incurs the energy cost of 374.Figure 8
(a) MWEC inG from Stage 1. (b) The output T
1 from Stage 1.
(a)
(b)Figure 9
(a) MWEC inG from Stage 2. (b) The output T
2 from Stage 2.
(a)
(b)Next considerϕ
(
m
) such that(53)
ϕ
m
=
1
,
m
≥
1
,
0
,
m
=
0
.Assume that the algorithm has yielded the same T
0, T
1 and T
2 as the previous case. Since ϕ is constant for m
≥
1, the problem reduces to the Steiner tree problem, thus one would expect that T
0 would perform the best since T
0 is intended to be an approximately optimal Steiner tree. The energy costs are given by(54)
c
T
0
=
37
,
c
T
1
=
44
,
c
T
2
=
43
;thus indeed the HCST algorithm will output T
0 as the best solution with cost 37, whereas the SPT heuristic will yield the energy cost of 41. This demonstrates that our algorithm can effectively deal with various types of convex and decreasing aggregation cost functions. In the following section we will evaluate the performance of the HCST algorithm by simulation.


## 6. Simulation

In our simulation we randomly generateG as follows. The node locations are generated independently and uniformly on a unit square. We define G as the Delaunay graph induced by the node locations. An example of G is depicted in Figure 10 for n
=
20. As previously it is assumed that the average number of bits required to transmit the aggregated information g
(
X
1
,
…
,
X
m
) is approximately α
+
b
+
h
(
g
(
X
1
,
…
,
X
m
)
) where we set header length a to 1 and the number of quantization bits b to 3. The edge weights are randomly selected from {
1
,
…
,
10
} which represents the energy consumption per transmitted bit. In our simulation two types of sources are considered. The first type, called uniform type, is associated with the extreme data retrieval problem, that is, X
i are i.i.d. uniformly on [
0,1
]. The second type, called Gaussian type, is associated with retrieving the maximum of Gaussian source data where X
i
~
N
(
0,1
). The summary function g
(
·
) is given by max  function.Figure 10
An example of randomly generatedG for simulation.We will compare the performance of the HCST algorithm with HM algorithm [16] and SPT heuristic. Figure 11 shows the average energy consumption of the algorithms when we fix the number of sources to 8 with varying n. The energy cost shown on the left (resp. right) of Figure 11 is associated with the sources of uniform (resp. Gaussian) type. We observe that the HCST algorithm achieves lower energy costs than the SPT heuristic in both types of the sources. The gain in the energy savings by the HCST algorithm ranges 35–38% for uniform type sources and 24-25% for Gaussian type sources. Compared to HM algorithm, our algorithm reduces the energy consumption by 20-21% and 14-15% for uniform and Gaussian type sources, respectively. HM algorithm focuses on microscopic cost reduction, which may be effective for concave and increasing cost functions, however not for convex and decreasing cost functions. Comparing SPT heuristic and HCST algorithm, we observe that the difference in the mean energy consumption of the algorithms slightly increases with n. This can be interpreted as follows: for larger networks, there is further room for improvement by HCST, for example, there are more choices for Steiner nodes and more ways to merge sources at low costs by MWEC. Thus the performance gain from the HCST algorithm relative to the SPT heuristic is expected to grow with n as shown in the simulation.Figure 11
Energy cost associated with a fixed number of sources.Figure12 shows the mean energy costs with varying n where we scale the number of the sources proportional to n. Specifically in the simulation we let η
=
n
/
5, that is, one out of five nodes is a source node. In the figure we see that the HCST algorithm again outperforms the SPT heuristic. The relative savings in energy by HCST algorithm ranges 19–41% for uniform type sources and 14–27% for Gaussian type sources. Relative to HM algorithm, HCST algorithm saves energy costs by 20–23% and 14–17% for uniform and Gaussian type sources, respectively. The difference in the energy cost of the algorithms increases with n similar to the case of fixed number of sources, however, such a rate of increase is higher in the case of varying number of sources. This can be explained as follows. When we increase the network size, the number of sources also increases proportionally. When the network size grows, from the previous argument such that there is further room for improvement by HCST, its relative gain will increase with the network size. In addition to that, since the number of sources grows, the total number of stages at the end of the HCST algorithm will also increase. Since HCST chooses the best tree from the intermediate output trees collected over stages, a large number of stages implies that we can choose the final output tree from a large pool of trees having various degrees of tradeoff between microscopic and macroscopic aspects of the cost reduction. Thus the abundance of source nodes enables us to choose an aggregation tree with a “refined” tradeoff, which is crucial for a convex and decreasing ϕ. This explains the enhanced performance of HCST with increasing number of sources. Hence we conclude from the simulation that the HCST algorithm can improve performance for various proportions of source nodes among the network.Figure 12
Energy cost associated with a varying number of sources.


## 7. Conclusion

In this paper we have studied a single-sink aggregation problem for wireless sensor networks computing several widely used summary functions. It is observed that the problem is characterized by the aggregation cost functionϕ which maps the amount of aggregated measurements to transmission costs at a link. We show that the properties of ϕ depend heavily on the chosen summary function g
(
·
). When g
(
·
) is given by sum or mean, we showed that ϕ is concave and increasing, implying that there exist algorithms such as the HM algorithm which can approximate the optimal algorithm by a factor logarithmic in the number of sources. A similar argument was made when g
(
·
) is weighted  sum  for i.i.d. Gaussian sources. When g
(
·
) is given by max, however, we have shown that ϕ is convex and decreasing for certain types of sources. For such ϕ we identify that there exists a tradeoff between the following two aspects of cost reduction: firstly local clustering of sources which is the microscopic aspect, and secondly a low-cost routing from the clustered sources to the sink which is the macroscopic aspect. We proposed the Hierarchical Cover and Steiner Tree algorithm which empirically finds the best tradeoff point between the aspects. Numerical examples and simulation results were presented to demonstrate that the HCST algorithm is versatile and improves performance for various types of convex and decreasing ϕ. A future direction would be investigating the optimal aggregation problems for a wider range of summary functions. In addition, the evaluation of the HCST algorithm in a real-world testbed environment is also part of our future work.



---

*Source: 506909-2015-06-01.xml*