Quentin Bramas
email: quentin.bramas@lip6.fr

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

The Complexity of Data Aggregation in Static and Dynamic Wireless Sensor Networks $

Keywords: Data aggregation, dynamic graphs, complexity

The key feature of wireless sensor networks is to aggregate data collected by individual sensors in an energy efficient manner. We consider two techniques to save energy. The first one is to avoid collisions due to simultaneous transmissions among neighboring nodes. Second, when a node receives data from multiple neighbors, it aggregates these with its own data. Then, one transmission is sufficient to transmit all consolidated data to another neighbor. If the overall delay has to be kept as low as possible, scheduling sensors to avoid collisions while aggregating data becomes challenging.

The contribution of this paper is threefold. First, we give tight bounds for the complexity of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. As it is trivial to solve the problem in static graphs of degree at most two, our result implies that the problem is intrinsically difficult for any practical setting. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two (and it is trivial to solve the problem when the graph is of degree at most one). Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph.

We observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future. Thus we finally give the first approximation algorithm (centralized that knows the future) whose approximation factor is T (n -1) if there exists a bound T such that there is a journey (a path in a dynamic graph) for all pairs of nodes in every time interval [t, t + T ].

Introduction

The growing number of sensor nodes with sensing, computing and communication capabilities, was made possible by recent technological advances. This growth was encouraged by a variety of applications and contributes to the widespread interest in practical and theoretical aspects of wireless sensor networks. Sensor nodes should be inexpensive, small and sustainable in order to be easily deployed in a dangerous area, inside a human body or in vehicles, generally for monitoring applications. They generate data that have to be retrieved by an end-user or a base station. However, the environment and the lack of networking infrastructure does not permit direct transmission to the end user, but only transmissions between sensors that are close to one another. This raises various challenges, such as energy (sensors are battery powered) and delay efficiency (information is relevant for a short period of time only).

In a wireless sensor network (WSN), sensor nodes can communicate through a wireless ad hoc network. Then, there exists a communication link between two nodes if the Euclidean distance between them is smaller than their communication range. Since we assume all sensors to be identical, they have the same communication range and the communication graph can be modeled as a unit-disk graph1 [START_REF] Clark | Unit disk graphs[END_REF]. Sensor nodes typically generate data from their environment, such as temperature, number of vehicles on a road, or number of passenger in a bus. The end-user, called sink node, wants to extract this information. To do so, a node can send its data directly to the sink node if it is located within its communication range, or, if it is far from the sink, can use intermediate nodes to relay the data to the sink node.

In this paper we investigate the problem of retrieving data from a WSN whose data transmissions are constrained by two rules: avoiding collisions, and allowing data aggregation. In more details, the time is discretized and, at each time slot, a node is able to send its data to all of its neighbors (i.e., all nodes within its communication range). Now, if two or more nodes send their data in the same time slot, their common neighbors do not receive any data, due to interference. Whenever a node successfully receives data, it aggregates the data with its own and stores the result as its new data. This process ensures energy-efficiency of the protocol. Indeed, n transmissions are sufficient to retrieve the data from n sensors to the sink node (compared to possibly Ω(n 2 ) without the capability to aggregate data). The problem of aggregating data from all nodes in the network in a minimum amount of time slots (delay-efficiency), assuming that a node sends its data at most once (energy-efficiency) is known as the minimum data aggregation time (MDAT) problem [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF]. A solution to this problem consists of a transmission schedule, meeting the communication constraints, with minimum duration.

In this paper we also introduce the dynamic version of the MDAT problem, where individual sensors are now mobile entities. This could model cars evolving in a smart city, medical devices in a body area network, or mobile devices monitoring an area. A WSN whose topology evolves with time is modeled as a dynamic unit-disk graph, i.e., a sequence of static unit-disk graphs. In this setting, the communication constraints hold at each time slot, and a solution of the MDAT problem consists of a transmission schedule with minimum duration.

When sensor nodes have fixed positions, the maximum distance (in hops) from the sink node to any other node is a lower bound for the minimum data aggregation time [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF]. Indeed, if no collision occurs, the data from the farthest node can be sent through a shortest path. Each avoided collision increases the duration of the schedule by one time slot. However, if we suppose the nodes are moving, avoiding collisions can intuitively have a much greater impact. Indeed, if a collision occurs and we delay the transmission of a node by one time slot, the node may not be able to transmit again (maybe the node remains isolated thereafter). In other terms, the existence of a journey (a path in a dynamic graph) from every node to the sink node is not sufficient to guarantee the existence of a collision-free schedule.

Related Work. The data aggregation problem we consider here was first studied by Anamalai et. al. [START_REF] Annamalai | On tree-based convergecasting in wireless sensor networks[END_REF]. The authors assume that a fixed number of channels is available for a transmission, and a collision occurs at a receiver whenever two of its neighbors transmit on the same channel at the same time. The authors propose an algorithm that constructs a collision free convergecast tree that can also be used for broadcasting. Then, Chen et. al. [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF] present a well-defined model for the study of the MDAT problem in wireless sensor networks. The problem is equivalent to the convergecast problem defined by Anamalai et al. with a unique channel. In the same paper, Chen et al. prove that the problem is NP-complete, even in graphs of degree at most four (more precisely they restricted the problem to networks whose topology is a sub-graph of the grid, which cannot be considered directly as a wireless sensor network). They also gave a (Δ -1)-approximation algorithm (where Δ is the maximum node degree of the graph).

After the work of Chen et. al. [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF], a variety of papers proposed centralized and distributed approximation algorithms using geometric aspect of the MDAT problem to improve the data aggregation delay. Yu et. al. [START_REF] Yu | Distributed data aggregation scheduling in wireless sensor networks[END_REF] give a distributed algorithm with an upper bound at 24D + 6Δ + 16 (where D is the diameter, and Δ the maximum degree of the graph). Xu et. al., in [START_REF] Xu | A delay-efficient algorithm for data aggregation in multihop wireless sensor networks, Parallel and Distributed Systems[END_REF] and Ren et. al. in [6] propose centralized algorithms with upper bounds at 16R + Δ -14 and 16R + Δ -11, respectively (where R is the radius of the graph). The best known bound is due to Nguyen et al. in [START_REF] Nguyen | Efficient time latency of data aggregation based on neighboring dominators in wsns[END_REF], as they give a centralized algorithm that takes at most 12R + Δ -11 time slots to aggregate all data.

Related problems such as in-network aggregation [START_REF] Fasolo | In-network aggregation techniques for wireless sensor networks: a survey[END_REF] focus on an orthogonal perspective. They assume that collisions are handled by the MAC layer, and aim to find routes that minimize the delay. So, those works actually differ significantly from the MDAT problem.

On the other hand, dynamic graphs have received a lot of interest recently and efforts have been done in order to standardize the underlying model [START_REF] Casteigts | Characterizing topological assumptions of distributed algorithms in dynamic networks[END_REF][START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF][START_REF] Kuhn | Dynamic networks: Models and algorithms[END_REF]. Various problems have been studied in a distributed setting, such as designing foremost, fastest, and shortest broadcast algorithms [START_REF] Casteigts | Shortest, fastest, and foremost broadcast in dynamic networks[END_REF][START_REF] Casteigts | Building fastest broadcast trees in periodicallyvarying graphs[END_REF]. For each problem, sufficient and necessary conditions on the (dynamic) graph are given. The opposite problem of data dissemination (or flooding) has also received a lot of attention in random dynamic networks. Clementi et al. [START_REF] Clementi | Information spreading in dynamic graphs[END_REF] gave an almost tight bound for any random dynamic graphs including edge-markovian evolging graphs and geometric graphs (where nodes follow a random walk or a random waypoint). A conclusion of their work is that increasing the dynamicity of the graph (for instance by increasing the speed of the nodes) implies faster data dissemination, even if the network is at each instant very sparse (due to a short communication range). Most related to our concern are two previous attempts that consider collecting data in dynamic networks [START_REF] Abshoff | Structural information and communication complexity: 21st international colloquium[END_REF][START_REF] Cornejo | Aggregation in dynamic networks[END_REF], however they use a much more powerful communication model where no collision occurs. In more details, continuous aggregation [START_REF] Abshoff | Structural information and communication complexity: 21st international colloquium[END_REF] assumes that data have to be aggregated, and that the result of the aggregation is then disseminated to all participating nodes. The main metric is then the delay before aggregated data is delivered to all nodes, as no particular node plays the role of a sink. The alternative problem considered by Cornejo et al. [START_REF] Cornejo | Aggregation in dynamic networks[END_REF] aims to minimize the number of nodes that owns data (or partially aggregated data) assuming unicast communications. In this work [START_REF] Cornejo | Aggregation in dynamic networks[END_REF], the time is finite and no particular node plays the role of sink node as any node can retrieve the data from any other node. To summarize, no previous work considers the data aggregation problem in dynamic networks allowing collisions.

Our Contribution. The contribution of this paper is threefold. First, in order to compare the complexity of the data aggregation in static and dynamic WSN, we give a tight bound for the complexity of the MDAT problem in static WSN. In more details, we show that, in a static WSN, the problem remains NP-complete when the graph is a partial grid of degree at most three (a particular case of WSN topology). As it is trivial to solve the problem in static graphs of degree at most two, our result implies that the problem is intrinsically difficult for any practical setting. This result closes the complexity gap in the static case.

Second, we introduce an extension of the MDAT problem in dynamic WSNs, and we prove that the dynamic MDAT is NP-complete in a dynamic partial grid of degree at most two (and it is trivial to solve the problem if the graph is of degree at most one). As our result does not use the geometric properties of the graph, it remains valid for arbitrary dynamic graphs whose degree is greater than one. We also show that allowing simultaneous transmissions to the same node is not intrinsically helpful as it only delays the complexity wall: we show that the problem remains NP-complete if a node can correctly receive up to K > 1 simultaneous packets from different neighbors, if the maximum node degree of the graph is K + 2 in the static case (and K + 1 in the dynamic case).

Third, we give the first lower and upper bounds for the dynamic MDAT problem. More precisely, we define the notion of the foremost convergecast tree to the sink node as a convergecast tree to the sink node, with the earliest arrival time. Then, the minimum time to aggregate all data in a dynamic network is greater than the duration of a foremost convergecast tree (this result is valid in any graph, and for any degree Δ, there exists a dynamic graph such that the bound is attained) and is smaller than the duration of n -1 independent foremost convergecast trees (this later bound is valid for any graph, but actually obtained for dynamic graphs of degree n -1). If we restrain the class of dynamic graphs to those of degree smaller than n -1, we prove that the upper bound is greater or equal to the duration of l independent foremost convergecast trees (with l = (Δ -1) log Δ (n (Δ -1) + 1) -Δ + 2), which prevents previous approximation algorithms for the static case to be extended to the dynamic case. Finally, we observe that, even in periodic graphs, optimal solutions cannot be computed by an algorithm that is unaware of the future of the graph or by a distributed algorithm (even if each node knows its own future). This motivates our simple approximate algorithm presented in section 6 to be centralized with full knowledge (yet, it does not assume that the graph is a dynamic WSN in the sense that it can perform on arbitrary graphs). The approximation factor is T (n -1) if there exists a bound T such that there is a journey between every

Model and Preliminaries

Wireless sensor networks (WSNs) containing n nodes with transmission range normalized to 1, are modeled by unit disk graphs [START_REF] Clark | Unit disk graphs[END_REF] i.e., intersection graphs of n equal-sized circles. Each vertex corresponds to a circle of radius 1/2, and an edge exists between two vertices when the corresponding circles intersect (tangent circles are assumed to intersect).

We model a dynamic WSN as a discrete-time-varying graph [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. According to this model, we consider a discrete lifetime T = N with a constant latency function ρ that equals one for every edge at any time (messages can travel at most one hop at a given time). Under those assumptions, a dynamic graph is seen as an evolving graph i.e., a sequence of snapshots, where each snapshot is a static graph that represents the evolving graph at a given time t ∈ N. The maximum node degree of a dynamic graph, denoted Δ, is the maximum node degree among all its snapshots. We recall that in dynamic graphs, an edge is a pair ((u, v), t), where u and v are two nodes that are connected at time t. Definition 1. A dynamic wireless sensor network G is a dynamic graph (V, (E t ) t∈N ) where V is the set of vertices and (E t ) t∈N a sequence that represents the edges of the graph over the time, such that for each t, (V, E t ) is a unit-disk graph. Data Aggregation Schedule. The time is discrete and at each time round, called time slot, communications are constrained by the following rule. Sensor nodes can send or receive data, but cannot do both at the same time. Moreover, if two nodes send their data simultaneously, all their common neighbors do not receive anything, due to interference (see figure 1). A node can aggregate a received data with its own data, according to a given aggregation function (simple examples of aggregation functions include maximum and addition). The aggregation is supposed to be atomic, and the resulting data can be sent like the original data i.e., in one time slot.

Let G = (V, (E t ) t∈N ), A ⊆ V , and B ⊆ A. We say that data is aggregated from A to B at time t, denoted by (G, A, t) → (G, B, t + 1), if nodes in A \ B transmit their data simultaneously and all the data is received by at least one node in B. Formally if:

∀u ∈ A \ B, ∃v ∈ B, ∀u ∈ A \ B \ {u} : (u, v) ∈ E t ∧ (u , v) / ∈ E t
A dynamic data aggregation schedule to s of duration l is a decreasing sequence of sets

V = R 0 ⊇ R 1 ⊇ . . . ⊇ R l = {s} satisfying the following condition: ∀i s.t. 0 ≤ i < l, (G, R i , i) → (G, R i+1 , i + 1)
Dynamic Minimum Data Aggregation Time Problem. An instance of the dynamic MDAT problem is a pair (G, s), where G = (V, (E t ) t∈N ) models a dynamic WSN, and s ∈ V denotes the sink node. A solution of an instance (G, s) is a dynamic data aggregation schedule to s with minimum duration. The minimum duration is denoted by MDAT Opt (G, s).

Remark 1. The dynamic minimum data aggregation time problem may have no solution, even in a dynamic WSN G connected over time (i.e., such that for all u, v ∈ V , there exists a journey from u to v). Indeed, consider a set of edges defined as follow: E 0 = V × V and ∀i = 0, E i = ∅. Then, the graph is connected, but only one node can send its data to the sink node at time 0, and the other nodes are never able to send their data. A simple sufficient (but not necessary) assumption that ensures the existence of a solution is that the graph is recurrent connected (see our algorithm GDAS in the sequel).

NP-Hardness

Static grid graphs of degree at most three

A grid graph is a unit disk graph where all disks have centers with integer coordinates and radius 1/2 i.e., an induced sub-graph of the grid. However, a sub-graph of the grid (not necessarily induced, called partial grid) is not necessarily a grid graph.

Chen et. al. prove in [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF] that finding the minimum data aggregation time is NP -hard, even when the network is restricted to partial grid (with maximum degree Δ = 4). On the other side, if the maximum degree of a static graph is Δ = 2, the graph is either a line or a cycle and the minimum data aggregation time is easy to compute. Let ε be the eccentricity of the sink node and n the number of nodes. If n is odd and ε = (n -1)/2 (the graph is either a cycle or a line with the sink node in the middle) then the MDAT is ε + 1. Otherwise the MDAT is ε.

In this section we close the complexity gap of the MDAT problem in static networks by proving that the MDAT is NP -hard, even when restricted to grid graphs with maximum degree Δ = 3.

We use a construction that is similar to that of Chen et al. [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF] with some improvements about the topology (grid graph instead of partial grid) and about the maximum node degree (3 instead of 4). We first state a lemma slightly different from their lemma 2 [START_REF] Chen | Minimum data aggregation time problem in wireless sensor networks[END_REF], and follow with our first theorem.

Lemma 1.

Let H be a planar graph with n > 6 nodes and maximum degree Δ ≤ 4, there exist an orthogonal planar embedding of H such that each edge has the same length. This embedding can be computed in time polynomial in n.

Proof. From [START_REF] Biedl | A better heuristic for orthogonal graph drawings[END_REF], we know that there exists an orthogonal embedding of H in a grid g of size n where each edge has at most 2 bends (so each edge has length smaller than 3n). Let g i be the grid g where the unit has been divided by 4i, of size 4in. We consider the corresponding embedding of H in g i (so that the coordinates of vertices has been multiplied by 4i). In g i , the maximum length of an edge is 12in. We can increase the length of an edge by 2 by replacing a piece of edge between two points with integer coordinates by a new piece of edge, like in figure 2a. This is possible if there are no other edges around.

By choosing i ≥ 48n, there is enough space in a subgrid (2i -2) × (2i -1), called safe box, to contain an edge of length 3 × 4in. So that, if i ≥ 48n, since all the length are even, we can lengthen all the edges to make them have a length 12in. Indeed, we can lengthen a given edge in the first (2i -2) × (2i -1) subgrid of an end point, in the anticlockwise direction (see figure 2). Before stating our first theorem, we recall the definition of the restricted planar 3-SAT [START_REF] Lichtenstein | Planar formulae and their uses[END_REF]. Let ϕ be a 3-SAT formula composed by a set C of m clauses c 1 , . . . , c m over a set V of n variables v 1 , . . . , v n . We define the corresponding formula graph

G ϕ = (V ∪ C, E 1 ∪ E 2 ), where E 1 = {(x i , c j ) : x i ∈ c j or xi ∈ c j } and E 2 = {(x i , x i+1 ) : 1 ≤ i ≤ n -1} ∪ {(x n , x 1 )}.
ϕ is said to be planar if the formula graph G ϕ is planar. ϕ is said to be restricted if (i) each variable appears in at most three clauses, (ii) both negated and unnegated forms of each variable appears at least once, and (iii) clauses drawn on the same side of the cycle E 2 must share the same literal if they share the same variable (i.e., at a variable vertex in G ϕ , incident edges from one side correspond to the same literal). It is known that restricted planar 3-SAT is NP-complete [START_REF] Lichtenstein | Planar formulae and their uses[END_REF].

Theorem 1. The MDAT problem restricted to grid graphs of degree at most three is NP-complete.

Proof. The proof is by reduction from restricted planar 3-SAT. Let ϕ be an instance of the restricted planar 3 -SAT on n variables and m clauses. From the planar formula graph G ϕ , we construct a planar graph G with maximum degree Δ = 3. The idea behind the construction is that, in order to have a fast data aggregation, the schedule must "choose" between two sides (i.e., the data are aggregated along one of two possible paths) representing the true or false instantiation of a variable. The aggregation is fast if all clauses are connected to the correct side of at least one variable. First we construct the sub-graph X i that represents the variable x i (see figure Fig. 3

.1).

X i is composed of a cycle of nodes e i , l i , r i , s i , o i , si , ri , li . Then, we connect to l i (resp. li ) a line L i (resp. Li ) of length 5i -3. Thus l i cannot sends its data before

e i l i r i s i o i si ri li o i-1 X i e i+1 L i Li Fig. 3.1: sub-graphs X i , L i and Li X 1 X 2 X 3 X 4 X 5 e c 1 c 2 c 3 c 4 Ψ 1,3 Ψ 2,3 Ψ 3,3 Fig. 3.2: example for ϕ = (x 1 ∨ x 2 ∨ x5 ) ∧ (x 3 ∨ x4 ∨ x5 )∧(x 1 ∨ x2 ∨ x3 )∧(x 3 ∨ x 4 ∨ x 5 )
aggregating data from L i i.e., before 5i -3 timeslots. For 1 ≤ i < n we connect o i to e i+1 and we connect to e 1 a new node e 0 . Each clause c j is represented by a single node and for each variable x i (resp. negation xi ) in clause c j , we connect c j to r i or s i (resp. ri or si ) by a line Ψ i,j of length (5i In order to use the previous lemma we need to be able to change the distance between nodes. So we define G T obtained from G by replacing every edge by a line of length T i.e., by adding T -1 nodes between two connected nodes, and by adding a pending node e connected to e 0 .

-2) to r i (resp. ri ) or (5i -1) to s i (resp. si ). Let G = 1≤j≤m 1≤i≤n X i ∪ L i ∪ Li ∪ Ψ i,j (see figure
In the next three Claims we show that there exists a T such that G T is a grid graph (of degree at most 3) and that the minimum time to aggregate data from G T to o n is 5nT +1 if and only if ϕ is satisfiable. Then, the theorem follows from the NP-completeness of restricted planar 3-SAT [START_REF] Lichtenstein | Planar formulae and their uses[END_REF].

Claim 1. There exists a T such that G T is a grid graph.

From Lemma 1 we deduce that G has an orthogonal embedding such that every edge has the same length l ≥ 1 in a grid of size s. We divide the unit by 4 so that the embedding is in a grid of size 4s and every edge has length 4l (every vertex has their coordinates multiplied by 4). Then, we replace, in its embedding, each node by a disk of radius 1/2, and every edge by a chain of 4l -1 disk of radius 1/2, centered at integer coordinates along the edge. Finally, we add a disk of radius 1/2, centered at integer coordinates, at distance 1 from e 0 and at distance greater than 1 from other disks. The corresponding unit disk graph (that is also a grid graph) is exactly

G 4l . Claim 2. For all T ≥ 1, if ϕ is satisfiable, then the minimum time to aggregate data from G T to o n is 5nT + 1.
First of all, we remark that the distance between e and o n is 5nT + 1, so that 5nT + 1 is a lower bound for the minimum data aggregation time. Now suppose that ϕ is satisfiable and let I be an interpretation of the truth-functional propositional calculus satisfying ϕ. Let i ∈ [1..n] and suppose I(x i ) = true. Suppose that e i has aggregated at time (5i -4)T + 1 data from previous nodes X k ∪ (Ψ k,j -{c j }), k < i and from clauses c j containing for every j < i, x j if I(x j ) = true, and xj otherwise. As we said before, l i (resp. li ) can aggregate all data from L i (resp. Li ) at time (5i-3)T .

At the negative side of X i , li can also aggregate all data of the T -1 nodes between e i and li before time (5i -3)T . If ri is connected to a clause c j , it can receive all data from nodes between ri and c j (c j excluded) at time (5i -2)T -1. Then ri can receive all data from li at time (5i -2)T . If si is connected to c j , it can receive all data from nodes between si and c j (c j excluded) at time (5i -1)T -1. Then si can aggregate all data from ri at time (5i -1)T . Thus o i can aggregate all data from si at time 5iT .

On the other side of the cycle, l i has to wait time (5i -3)T + 1 to receive data from e i . Again, if r i is connected to c j , it can receive all data from nodes between r i and c j (c j included) at time (5i -2)T . Then r i can receive all data from l i at time (5i -2)T + 1. If s i is connected to c j , it can receive all data from nodes between s i and c j (c j included) at time (5i -1)T . Then s i can aggregate all data from r i at time (5i -1)T + 1. Finally, o i can aggregate all data from s i at time 5iT + 1.

If i = n, then it's over, otherwise o i can start transmitting to the next block X i+1 and e i+1 can aggregate data from o i at time (5(i + 1) -4)T + 1, the data includes data from clauses containing x i . If I(x i ) = false, the schedule on the positive and negative side of the cycle are exchanged in order to aggregate data from clauses containing xi instead of x i . Recursively, since all clauses are connected to a variable x i with I(x i ) = true or to xi with I(x i ) = false, o n aggregates all data at time 5nT + 1.

Claim 3. For all T ≥ 1, if the minimum time to aggregate data from

G T to o n is 5nT + 1, then ϕ is satisfiable.
Suppose that all data from G T are aggregated to o n at time 5nT + 1. Since e is at distance 5nT + 1, its data is sent directly through a shortest path i.e., there is a shortest path P from e to o n such that, when a node in P receives at time t a data from e (an aggregation that contains e's data) it sends the aggregation to the next node in the path at time t + 1. There are 2 n shortest paths from e to o n , indeed, at each block X i , the path can use the positive or the negative side, and implicitly choose to interpret x i as true or false. Let i ∈ [1..n], and suppose P uses the positive side of X i . As we saw before, data from L i and Ψ i,j for clauses c j that contain x i can be aggregated to l i , r i and s i before the data from e. The first observation is that o i receives data from e, L i and Ψ i,j for clauses c j containing x i at time 5iT + 1 and has to send the aggregation just after (it cannot receive data after time 5iT + 1).

On the other side, li can start sending at time (5i -3)T (because it must receive data from Li first), and its data must be aggregate through a path to o n of length smaller than or equals to 5nT + 1 -(5i -3)T . Because of its length, this path must pass through o i , by the negative side of X i . Thus data from li must be aggregate through a path to o i of length smaller than or equals to 3T + 1 (the maximum length of the path minus the minimum distance from o i to o n ). Adding this to the first observation, we know that data from li must be received by o i at time 5iT (and cannot be received before, because li and o i are at distance 3T ).

Thus, data from li cannot be delayed (except by o i ) i.e., if a node receives a data from li at time t, it must send the aggregation to the next node at time t + 1. Thus ri and si can receive data from other nodes only before time (5i -2)T and (5i -1)T , and so this data cannot include data from a connected clause c j (only from Ψ i,j -{c j }). Since all paths from a clause c j to o n passing trough X i contain a node r i , ri , s i or si , a connected clause can send its data through X i only if it contains x i .

The same thing happens if P uses the negative side of X i : a connected clause can send its data through X i only if it contains xi .

For a shortest path P from e to o n used to aggregate e's data, we say a variable x i is true if P uses the positive side of X i , and xi is true otherwise. We have shown that if the data of a clause c j is received by o n on time (before time 5nT + 1), then c j contains a true literal. Finally, if data from all clauses is received on time, then every clauses contains at least one true literal, and the formula is satisfiable.

An interesting extension can be to investigate the case when a constant number K of simultaneous transmissions are feasible. Let K ∈ N * , we define the MDAT K problem as the MDAT problem, with the additional assumption that nodes can simultaneously receive up to K messages from K different neighbors. Note that simultaneously receiving K +1 or more messages still results in a collision. We now revisit the previous result with K > 1. We show that allowing one more simultaneous transmission results in increasing by one the maximum node degree of the graph for the problem to be NP-complete. This may seems obvious at first sight, but the fact that the problem concerns unit-disk graphs makes the proof slightly technical. Indeed, every time we want to create a collision, to force the algorithm to make a choice, we have to create a node of degree K + 2, and in a unit-disk graph, if K is large enough, such a node must have two neighbors that are connected. So that we cannot connect an arbitrary amount of lines to a node while keeping the whole network as a unit-disk graph. The idea of the proof is as follow. For each node where we need a collision (see proof of theorem 1), we add a single special line of nodes. The resulting graph has now a maximum node degree of 4 and still have an embedding in the grid. Then, after replacing each edge in the embedding by nodes to create a unit-disk graph, we replace each special line by a unit-disk graph that creates the desired collision.

Theorem 2. The MDAT K problem restricted to graphs of degree at most K + 2 is NP-complete.

Proof. Let ϕ be an instance of the restricted planar 3 -SAT with n variables and m clauses. From the planar formula graph G ϕ , we construct a graph G as in the proof of Theorem 1, with 5 additional lines C 1 , C 2 , C 3 , C 4 , C 5 connected to nodes r i , l i , ri , li , and o i . We connect C 1 (resp. C 2 ) of length 5i -2 to r i (resp. ri ), C 3 (resp. C 4 ) of length 5i -1 to l i (resp. li ), C 5 of length 5i + 1 to o i . As in the proof of Theorem 1 we define G T obtained from G by replacing every edge by a line of length T i.e., by adding T -1 nodes between two connected nodes, and by adding a pending node e connected to e 0 . G has a maximum node degree of 4, so it has an orthogonal embedding such that every edge has the same length l ≥ 1 in a grid of size s (see Lemma 1). We divide the unit distance by 4 so that two edges are at distance at least 4 from each other. Then, we divide the unit distance by 2(K -1).

Let ε > 0 and

K = K -1. For each line C ∈ {C 1 , C 2 , C 3 , C 4 , C 5 } of length d in the embedding (d is a multiple of 8K
), we split the line in small parts of length 2K at the two extremities, and length 4K otherwise (see Figure 3). Each small part is either a straight line or two orthogonal straight lines. The goal is to replace each part by a unit-disk graph Ĉ such that, when aggregating all the data from Ĉ, K nodes then want to transmit simultaneously at time d their data to the node that connects Ĉ to the remaining of the graph.

Each straight line of length 4K is replaced by K × 4K disks of radius 1/2 spread across a grid of size K × 4K , that is constrained in a rectangular area of width 4K , 10 height ε, and centered at the middle of the initial line. This implies that the intersection graph of those disks (see Figure 3) is composed of 4K cliques of size K that are connected by K lines of length 4K . This graph has the property that the distance between two nodes located at distinct extremities is either 4K if the nodes are in the same line, or 4K + 1 otherwise. We repeat the same process for the parts at the extremities, using only K × (2K -1) disks for the part connected to the remaining of the graph, and K × 2K disks for the part at the other extremity.

Similarly, each part composed by two lines at a right angle is replaced by K × 4K disks of radius 1/2 in such a way that the intersection graph contains K lines of length 4K (connected with some additional edges), and has the same property as the previous intersection graph (see Figure 3). This implies that the intersection graph produced by all the disks of all the small parts contains K lines of length d such that the distance between two nodes at distinct extremities is d if they are in the same line, or d + 1 otherwise.

All the disks are slightly translated toward the node u ∈ {r i , ri , l i , li , o i } that connects C to the remaining of the graph, so that the K disks at the extremity of the line are at distance at most 1 from u. Also, ε is chosen sufficiently small so that disks that replace Line C do not intersect with other disks, located in the remaining of the graph.

Finally, as in the previous proof, we replace in the remaining of the embedding each node by a disk of radius 1/2, and every edge by a chain of 8K l -1 disks of radius 1/2, centered at integer coordinates along the edge. Finally, we add a disk of radius 1/2, centered at integer coordinates, at distance 1 from e 0 . The obtained graph is G 8K l , where each line C i is replaced by a subgraph Ĉi such that, to aggregate all data from Ĉi without delaying the data aggregation in the whole graph, the node u that connects Ĉi to the remaining of the graph has to aggregate the K -1 neighbors in Ĉi simultaneously at time d, which equals the length of C i . Then, only one other neighbor of u can transmit its data to u at time d. This simulates the constaint that no two neighbors of u could transmit at time d without interference in the previous setting. So, we can apply the same proof as the case K = 1 on the transformed graph.

One can observe that the problem is easy to solve in static graphs of degree at most K + 1. Indeed, when aggregating data along the shortest path tree, no collision occurs, except maybe at the sink node. Any schedule, for the transmissions of the neighbors of the sink, that avoid collisions is optimal.

Dynamic graphs of degree at most two

In a dynamic network we prove that, even when the maximum degree is two, the dynamic MDAT problem is NP-hard. This result is optimal since the problem is easy to solve in a graph of degree at most one (where no collision occurs).

v i s (a) configuration during T 1 c i c i a b c c i c i (b) configuration during T 2 v i vi s (c) configuration during T 3

Theorem 3. The dynamic MDAT problem is NP-complete even in a dynamic wireless sensor network of degree at most two.

Proof. The proof is by reduction from 3-SAT. Given any 3-SAT instance ϕ of n variables v 1 , . . . , v n and m clauses c 1 , . . . , c m , we construct the dynamic grid graph G ϕ (V, E) as follow:

Nodes are composed of one sink node, literals, clauses, and copy of clauses:

V = {s} 1≤i≤n {v i } ∪ {v i } 1≤i≤m {c i } ∪ {c i }
Let t f = 3n + 2m. We decompose the time interval [1, t f ] in three periods T 1 , T 2 and T 3 (see figure 4):

• During T 1 = [1, 2n],
we have for all i ∈ [1, n]:

E 2i-1 = {(v i , s)}, E 2i = {(v i , s)} • During T 2 = [2n + 1, 2n + 2m] we have for all j ∈ [1, m]: with {a, b, c} = c j , E 2n+2j-1 = {(c j , c j )}, E 2n+2j = {(c j , a), (c j , b), (c j , c)} • During T 3 = [2n + 2m + 1, 2n + 2m + n] we have for all i ∈ [1, n]: E 2n+2m+i = {(v i , s), (v i , s)}
The remaining of the dynamic graph (after time t f ) can contain for instance composed only empty snapshots, or be such that the graph is periodic. This does not change the proof, but can be used to analyze the best approximation ratio for this problem (see remark 2).

During T 3 , either a variable or its negation can send its data to the sink node s, but not both, so that the set of literals that send data can be seen as an interpretation of a truth-functional propositional calculus.

During T 1 , variables that does not send their data during T 3 can send their data directly to the sink node.

During T 2 , there is a link between a clause c i and its copy c i so that either c i or c i can send both data. Since all clauses can send their data only once to all the literals it contains, the data is successfully sent to the sink node if and only if at least one literals it contains sends its data in T 3 i.e., is true.

Thus, if the interpretation chosen in T 3 satisfies the formula ϕ, then each clause contains a literal that transmits during T 3 , and the minimum data aggregation time is exactly t f . Otherwise, some clauses must send their data before t = 1, and the minimum data aggregation time is greater than t f . So that the 3-SAT instance ϕ is satisfiable if and only if the minimum data aggregation time ending before t f is t f . Remark 2. Theorem 3 raises the question of the best approximation ratio achievable by an approximation algorithm. We observe that using time as a complexity measure is not relevant in the dynamic case. Contrary to the static case, where good approximation ratios have been found, the problem is not approximable in the dynamic case using the duration of the solution as a measure of complexity. Indeed, the dynamic graph constructed in the proof of Theorem 3, with empty snapshots when time is greater than t f , only contains the optimal solution. So, if an approximation algorithm finds an approximate solution, it actually finds the optimal solution, which is not possible in polynomial-time (unless P = NP ). Even when restricted to smaller classes of graphs, such as periodic dynamic graphs, the approximation ratio (with respect to duration) can be made arbitrary large by increasing the period. The approximation ratio can be bounded in periodic graphs, but only when the period is itself bounded (or in time-bounded recurrent connected graphs with fixed bound, as defined in Section 5). This remark justifies (i) our use of Foremost Convergecast Trees, defined in Section 4, as a complexity measure to establish upper and lower bounds, and (ii) the approximation ratio of our approximate algorithm, presented in Section 6, when restricted to time-bounded recurrent connected graphs.

As in the static case, we show that when K simultaneous transmissions are allowed without collisions, the problem is similar. Here, the geometric constraints do not hold, giving a more straightforward proof.

Theorem 4. The dynamic MDAT K problem restricted to evolving graphs of degree at most (K + 1) is NP-complete.

Proof. In the dynamic case, there is a simpler way to apply the same trick as in the static case. From a 3-SAT instance, we create the same evolving graph as in Theorem 3, but with (K -1) × n additional nodes (r 1 1 , r 1 2 , . . . , r n K-1 ), and where edges in the period T 3 are defined as follow: for all i ∈ [1, n],

E 2n+2m+i = {(v i , s), (v i , s)} ∪ K-1 j=1 {(r i j , s)}
So, in order for the data aggregation to terminates at time t f = 3n + 2m, all nodes r i j have to transmit during T 3 . This implies, like in the proof of Theorem 3, that either a variable or its negation can transmit during T 3 .

t = 0 t = 1 t = 2 Foremost Convergecast Tree

Upper and Lower Bounds

In this section, we introduce the notion of foremost convergecast trees. Then we propose the first upper and lower bounds for the dynamic MDAT problem, given in terms of foremost convergecast tree duration.

A journey from a node u to node a v is a sequence of edges ((e 1 , t 1 ), . . . , (e r , t r )) such that (e 1 , e 2 , . . . , e r ) is a path from u to v in the static graph (V,

∪ i∈N E i ) and ∀i ∈ [1..r -1], t i < t i+1 ∀i ∈ [1..r], e i ∈ E ti
For a journey J, we denote by departure(J) the starting time t 1 and by arrival(J) the arrival time t r + 1 of the journey. The arrival time corresponds to the time of the existence of the last edge plus the latency to travel along the last edge. Then, duration(J) = arrival(J)departure(J) denotes the duration of the journey. We denote by J (u,v) the set of journeys from u to v and by J Let G(V, E) be a dynamic graph. A foremost convergecast tree (abbreviated as FCT) to node s starting at time t s is a convergecast tree (T, c) to s such that departure(T, c) ≥ t s with minimum arrival time.

F CT (G, s, t s ) denotes the set of foremost convergecast trees of G to node s starting after time t s . The common duration of foremost convergecast trees starting after t s is denoted F CT D(G, s, t s ).

In dynamic WSNs, a foremost convergecast tree plays the same role as a shortest path tree in static WSNs. Indeed it gives the same lower bound as in the static version of the problem. Figure 5 shows an example of the unique foremost convergecast tree to the sink node s starting at time 0 of a simple dynamic graph (for the sake of simplicity, the position of the nodes do not change with time). 14 Lemma 2. Let G be a dynamic graph, we have:

t ≡ 0 mod 2 t ≡ 1 mod 2 Foremost Convergecast Tree
MDAT Opt (G, s) ≥ F CT D(G, s, 0)
Proof. Let G be a dynamic graph, s be a sink node, and S = {S t } t be a data aggregation schedule to s of duration l = MDAT Opt (G, s). Let x 0 be a node different from the sink. We know that there exists i is such that

x 0 ∈ S i and x 0 / ∈ S i+1 . Since (G, S i , i) → (G, S i+1 , i + 1)
, there exists a node x 1 ∈ S i+1 such that (x 0 , x 1 ) ∈ E i . We can apply the same argument to x 1 if it is different from the sink.

Recursively we have x 1 , x 2 , . . ., x p = s and t 1 < t 2 . . . < t p < l such that for all

1 ≤ i ≤ p, (x i-1 , x i ) ∈ E ti . Thus J = {((x i-1 , x i ), t i ) | 1 ≤ i ≤ p}
is a journey from x 0 to s ending before l. We can do this with every nodes in V -{s}, which proves F CT D(G, s, t s ) ≤ l.

In a static WSN, the same shortest path tree can be used to avoid collisions. But in a dynamic WSN, a FCT T 1 that exists at a given time may not exists thereafter. If we delay the transmission of a node, to avoid a collision, another FCT T 2 is then used to retry a transmission. In order to be sure that T 2 can be used by all delayed nodes, it has to start after the end of T 1 . In this case we say that (T 1 , T 2 ) is a 2-time-independent FCT. Definition 4. A l-time-independent FCT of G to s starting at time t s is a sequence of l foremost convergecast trees of G to s ((T 1 , c 1 ), . . . , (T l , c l )) such that:

• (T 1 , c 1 ) is a FCT starting at t s . • for all 1 < i ≤ l, (T i , c i ) is a FCT starting at arrival(T i-1 , c i-1 ).

Its duration is the sum duration of all FCT in the sequence and also equals to

tarrival(T 1 , c 1 )-t s . The set of l-time-independent F CT of G to s starting at t s is denoted F CT l (G, s, t s ). The common duration of all l-time-independent LT Js in F CT l (G, s, t s ) is denoted LT JD l (G, s, t s ).
This definition is used to give lower and upper bounds for the minimum data aggregation time in a dynamic graph G with n nodes as follow: Where the right-hand inequality comes from lemma 2 and the left-hand inequality comes from the fact that a node can send its data during a FCT, so that n -1 foremost convergecast trees are sufficient to aggregate the data of every nodes.

F CT D n-1 (G, s, 0) ≥ MDAT Opt (G, s) ≥ F CT D(G, s, 0)
The lower bound and the upper bound are tight in the sense that there exists a graph that reaches the lower bound (any graph of degree at most one) and a graph that reaches the upper bound (for instance a graph whose sink node is of degree n -1 at each time).

If we consider only graphs with a given maximum node degree Δ, the lower bound is still tight, but the upper bound is no longer tight. The following lemma gives a graph with a minimum data aggregation time that lowers the upper bound, for an arbitrary maximum node degree Δ. We conjecture that it also gives the worst data aggregation duration i.e., that it also give an upper bound that remains tight for an arbitrary maximum node degree. Lemma 3. Let n ∈ N * and Δ ≤ n, there exist a dynamic graph G with n nodes of degree at most Δ such that:

F CT D m (G, s, 0) = MDAT Opt (G, s) < +∞ with m = (Δ -1) log Δ (n (Δ -1) + 1) -Δ + 2
Proof. Let Δ ≥ 2. We consider the dynamic graph G(V, E). For the sake of simplicity, we suppose that there exists h ∈ N such that |V | = n = Δ h+1 -1 Δ-1 . One can construct G such that, there is a perfect Δ-ary tree T (of height h) such that, for all t ≡ 0 mod h, F CT (G, s, t) = {(T, c t )} and (T, c t ) is of duration h (and thus with collision appearing between every nodes having the same parent). See for instance figure 6 with Δ = 2 and h = 3. The path associated to a journey from a node u to the sink is unique. So that a node has to wait to receive the data from all its children before transmitting.

Since no two children of s can transmit at the same time, s needs Δ FCTs to receive the data from all its children. Let s be the first direct child of s that transmits, and T (s ) the sub-tree of T rooted at s . T (s ) is a perfect Δ-ary tree of height h -1. When s transmits, its data contains the data of its children. Again, Δ FCTs are needed to aggregate all the data from all its children. One of this FCT can be used to aggregate the data from s to s. For each layer of the tree, Δ -1 consecutive FCTs are needed.

Recursively, we need at least (Δ -1)h + 1 time-independent F CT s to aggregate all the data from G. One can show that this is also sufficient (see figure 7). Since h = log Δ (n(Δ -1) + 1) -1, the theorem is proved.

Conjecture 1.

Let G be a dynamic graph with n nodes of degree at most Δ. Let m = (Δ -1) log Δ (n (Δ -1) + 1) -Δ + 2, we have:

F CT D m (G, s, 0) ≥ MDAT Opt (G, s)
We observe that the conjecture is proved for Δ = n -1 and is trivial if Δ = 1.

Impossibility Results

In this section we present several classes of dynamic graphs where only a centralized algorithm that knows the future can compute optimal and "good" approximate solutions. A hierarchy of classes of dynamic graphs has been identify in previous work [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF]. Here we present only the few we are interested in.

• RC (Recurrent connectivity): ∀u, v ∈ V, ∀t ∈ N:

J [t,+∞) (u,v) = ∅
• BRC (Time-bounded recurrent connectivity): There exists a bound T such that, ∀u, v ∈ V, ∀t ∈ N:

J [t,t+T ] (u,v)
= ∅

• P (Periodic): the graph is connected and there exists T ∈ N such that:

∃t, (u, v) ∈ E t ⇒ (∀k ∈ N, (u, v) ∈ E t+kT )
The two following impossibility results are for the class of periodic graphs, and naturally extend to larger classes such as recurrent connected. The first impossibility result concerns distributed algorithms. A distributed algorithm is a set of local algorithms that are each executed independently by each node. It is also assumed that nodes no not have knowledge about the global topology (or future global topology) of the graph; they may only have knowledge about adjacent edges and nodes (or their future). In general, when two nodes interact, we assume that they are allowed and able to exchange their local knowledge (for instance, about their respective local future if they are aware of it) and use this information for future interactions. For our problem, a distributed algorithm has to decide, whenever an interaction occurs, whether the node sends its data or not.

Proposition 1. In P, the dynamic MDAT problem does not have a distributed optimal algorithm, even if each node knows its own future.

Proof. We define G = (V, {E i }) and G = (V , {E i }) as follow (see figure 8):

V = V = {s, 1, 2, 3}, ∀i ∈ N, E i = {(1, s), (2, 3)}, E i = {(1, s)} if i ≡ 0 mod 3 E i = E i = {(1, 2), (3, s)} if i ≡ 1 mod 3 E i = E i = {(1, s), (2, 3)} if i ≡ 2 mod 3
At time 0 a distributed algorithm A do the same thing for node 1 and s on G and G , because they have the same neighbors now and in the future. If A decide that node 1 transmits its data to s at time 0, then A is not optimal on G (since its faster to wait the data from node 2 at time 1 and then transmit at time 2). Otherwise, A is not optimal on G (since all data can be aggregated at time 1).

G : If we consider time as a measure of complexity, the following proposition shows that the best competitive ratio a distributed algorithm with knowledge of (local) future can achieve is unbounded.

G : t ≡ 0 [3] t ≡ 1 [3] t ≡ 2 [3]
Proposition 2. In P, the competitive ratio of a distributed algorithm is unbounded for the dynamic MDAT problem, when considering time as a measure of complexity, even if each node knows its own future.

Proof. We construct two graphs, G and G , so that there is an arbitrary delay between the optimal solution and any other solution, resulting in unbounded competitive ratio. In more details, for all K > 2, we define G K = (V, {E i }) and G K = (V , {E i }), periodic with period T = 2K 2 , as follow :

V = V = {s, 1, 2, 3}, ∀i ∈ N, E i = {(1, s), (2, 3)}, E i = {(1, s)} if i ≡ 0 mod T E i = E i = {(1, 2), (3, s)} if i ≡ 1 mod T E i = E i = {(1, s), (2, 3)} if i ≡ 2K mod T E i = E i = ∅ otherwise
So that, for an algorithm A, either (i) A chooses that node 1 transmits at time 0 and the time to aggregate all the data is greater than 2K 2 compared to 2K for an optimal centralized algorithm (i.e. a ratio of K) or (ii) A chooses that node 1 does not transmit at time 0 and the time to aggregate all the data is greater than 2K compared to 2 for an optimal centralized algorithm (i.e. a ratio of K). In both case, the ratio K between the time to aggregate the data with A compared to an optimal centralized algorithm can be made arbitrary big.

Proposition 3. In P, without knwoledge of the future, the dynamic MDAT problem does not allow a centralized optimal algorithm.

Proof. Let k ∈ {1, 2}. We define G k as follow (see figure 9):

V = {s, 1, 2}, ∀i ≥ 0, E i = (1, 2) if i ≡ 0 mod 2 (k, s) i fi ≡ 1 mod 2
Let A be an algorithm that does not know the future. At time 0, A is executed the same way on G 1 and G 2 . If A decides that node 1 should transmit its data to node 2 at time 0, A cannot solve the problem on G 1 . If A decides that 2 should transmit to 1 at time 0, then A cannot solve the problem on G 2 . Otherwise, if A choose to do nothing at time 0, the solution given by A is not optimal.

G 1 : G 2 : t ≡ 0 [2] t ≡ 1 [2]
Again, if we consider the time as a measure of complexity, the following proposition shows that the best competitive ratio a centralized algorithm without the knowledge of future (called online algorithm) can achieve is unbounded. Proposition 4. In P, the competitive ratio of an online algorithm (that is, a centralized algorithm without knowledge of the future) is unbounded for the dynamic MDAT problem, considering time as a measure of complexity.

Proof. Let G ∞ (V, E ∞ ) be defined as follow:

V = {s, 1, 2}, ∀i ≥ 0, E ∞ i = (1, 2) if i ≡ 0 mod 2 (1, s) i fi ≡ 1 mod 2
Let A be an algorithm that does not know the future. When executing A on G ∞ , either (i) A decides never to transmit, and the corresponding competitive ratio of A is infinite, (ii) the first node to transmit is node 1, and the competitive ratio of A is infinite, or (iii) at some time t, A decides that node 2 transmits to node 1. Let G t,T (V, E t,T ), with T > t, be defined as follow:

∀i ≥ 0, E t,T i = ⎧ ⎨ ⎩ (1, 2) if i ≡ 0 mod 2 (1, s) else, if i ≡ j mod 3T , with 0 < j < t (2, s) otherwise
Then, when executing A on G t,T , node 2 transmits to node 1 at time t, and node 1 has to wait until time 3T + 1 to transmit its data to s. Since the optimal offline algorithm executed on G t,T terminates in 2 steps if t > 0, and 3 steps otherwise, the competitive ratio of A on G t,T is greater than T .

Approximation Algorithm

In this section, we present an approximation algorithm for the dynamic MDAT problem. The maximum duration of a solution output by this algorithm reaches the theoretical upper bound given in Section 4. The complexity of our algorithm is better than the one appearing in the preliminary version of this paper [START_REF] Bramas | The complexity of data aggregation in static and dynamic wireless sensor networks[END_REF], as it needs to loop two times over the number of edges of all snapshots between time 0 and time t f (where t f is the duration of the found solution), instead of the square of this number for the previous algorithm.

During the first inner while loop, the algorithm finds the arrival time of a foremost convergecast tree of the nodes in remainingN odes, starting at time t s . The arrival time, denoted t f , becomes the starting point to find a collision-free schedule between time t f and time t s in a backward manner for the nodes in remainingN odes. If some nodes in remainingN odes are not able to transmit between time t s and time t f , we start a new iteration and compute the duration of the foremost convergecast tree consecutive to the one found in the previous iteration (its departure time is the arrival time of the previous foremost convergecast tree).

The last for loop converts the sequence S that contains the senders over the time to a dynamic data aggregation schedule. With this method, if a node is in S t1 ∩ S t2 , then only the last transmission is taken into account. The algorithm loops over all the edges, two times, for each snapshot of the dynamic graph between time 0 and the duration of the found solution.

Our algorithm uses Procedure canT ransmit(u, Senders, Receivers), that returns true if and only if Node u can transmit its data to a node in Receivers without interfering with other nodes in Senders.

Lemma 4. If Algorithm GDAS terminates, the sequence {S

i } i≤tf is a valid DAS.
Proof. If GDAS terminates, then the sequence S satisfies S 0 = V , because each node that has been removed from remainingN odes line 21 has been added to S t line 23. Moreover, for each time t, nodes in S t \ S t+1 (if not empty) have been added to S t line 23 after Function canT ransmit returned true, thus their data are successfully received by nodes in S t+1 . This implies (G, S t , t) → (G, S t+1 , t + 1).

Theorem 5. If a graph G is in RC, algorithm GDAS finds a valid dynamic data aggregation schedule such that duration(GDAS(G, s))

≤ F CT D n-1 (G, s, 0)
Proof. First, we observe that the inner while loop simulates a multicast of every node in the network and stops when the sink node receives data from the nodes in remainingN ode. The duration t ft s is smaller than the duration of a foremost convergecast tree starting at t s (and it terminates in finite time since the graph is recurrent connected).

We prove that after each iteration of the main do ... while loop, the cardinal of the set remainingN odes strictly decreases.

Let t i f be the value of t f at the end of the i-th iteration. Suppose we have already executed the i -1 iteration of the main loop. At the beginning of the i-th iteration, we compute in the inner while loop the minimum time to aggregate (maybe with collision) 20

Algorithm GDAS: Greedy Data Aggregation Schedule Input: MDAT Instance (G, s) the data of the nodes in remainingN odes. Indeed, for a node u, v ∈ data t [u] implies that there exists a journey from v to u ending before time t. Since data t i f [s] contains remainingN odes, for each node u ∈ remainingN ode, there exists a journey from u to s with departure greater than t i-1 f = t i s and arrival smaller that t i f . In the for loop starting Line 16, we create a collision-free schedule that aggregates the data of at least one node in remainingN odes. Indeed, for each time t ∈ [t i s ..t i f ] (in decreasing order), a node is chosen to transmit if the transmission does not create a collision (with the help of the function canT ransmit) and the node is in a journey from a node in remainingN odes to s (since data t-1 [v] ∩ remainingN odes = ∅). Since a node can be marked at most once, there exists a time t, when the only nodes (not marked) on a journey from a node in remainingN odes to s are themselves in remainingN odes. One of these nodes is chosen to transmit at time t and is removed from the set remainingN odes.

This implies that there can be at most n -1 = #(V \ {s}) iterations of the main loop. After each iteration, the duration t ft s is smaller than the duration of a foremost convergecast tree starting at t s . Since for each iteration, the computation restart from the end of the previous one, after i iterations of the main loop, t i f is smaller than the duration of i consecutive foremost convergecast trees. Since there can be at most n -1 iterations of the main loop, the duration of the dynamic data aggregation schedule is at most LT JD n-1 (G, s, 0).

If the graph is T -time-bounded recurrent connected, then a F CT duration is smaller than T . Thus, we can derive an absolute bound and the following approximation factor for the dynamic MDAT problem. Thus, it is an approximation of factor T (n -1), for the dynamic MDAT problem.

Conclusion

We studied the complexity of the minimum data aggregation time problem in wireless sensor networks. We proved that the problem is NP-complete in a static WSN of degree at most three, and NP-complete in a dynamic WSN of degree at most two. The degree constraint is crucial, as a smaller one induces a trivial solution in both cases. Then we gave tight lower and upper bounds for the minimum data aggregation time problem in dynamic networks and the first approximation scheme for the problem. Also, in a dynamic graph with n nodes of degree at most Δ, we conjecture a more accurate upper bound of l timeindependent foremost convergecast trees (with l = (Δ -1) log Δ (n (Δ -1) + 1) -Δ + 2).

Finally we observed that only a centralized algorithm with full knowledge can compute the optimal solution of the problem. Thus, we gave a simple approximate algorithm giving a solution whose time matches the theoretical upper bound.

One can observe that allowing nodes to transmit several times their data, instead of only once, does not change the results concerning centralized algorithms that are aware of the future. Indeed, a schedule that contains multiple transmissions by node can be converted to a schedule where each node transmits only once, by keeping only the last transmission. Moreover, we also believe that the impossibility results concerning 22 distributed algorithm, and online algorithms, still hold even if a constant number of transmissions are allowed by node.

  node u receives data from v and u from v

Figure 1 :

 1 Figure 1: Communication constraints

Figure 2 :

 2 Figure 2: Construction of the orthogonal embedding

  Fig. 3.1 and Fig. 3.2).

Figure 3 :

 3 Figure3: The replacement of a line connected to node u ∈ {r i , ri , l i , li , o i } by graphs containing K = K -1 lines of length 2K -1 for the part connected to u, and 4K for the parts not at an extremity.

Figure 4 :

 4 Figure 4: Node Configurations (clauses are blue and literals are red).

Figure 5 :

 5 Figure 5: An example of foremost convergecast tree.

[Definition 2 . 1 Definition 3 .

 213 ts,te] (u,v) the subset of journeys that start and end between t s and t e . Let G(V, E) be a dynamic graph. A convergecast tree to node s is a pair (T, c), where T (V, T edges ) is a tree rooted at s, and c is a function c :T edges → N that satisfies: if u is a descendant of vin T and (e 1 , e 2 , . . . , e r ) is the path from u to v in T , then ((e 1 , c(e 1 )), (e 2 , c(e 2 )) . . . , (e r , c(e r ))) is a journey in G called the journey from u to s induced by T . The departure (respectively, the arrival) of the convergecast tree is the departure of the first journey in T (respectively, the arrival of the last journey in T ): departure(T, c) = min e∈Tedges c(e) and arrival(T, c) = max e∈Tedges c(e) +

Figure 6 :

 6 Figure 6: Creation of a perfect binary FCT.

Figure 7 :

 7 Figure 7: Optimal data aggregation schedule when FCTs are complete binary trees.

Figure 8 :

 8 Figure 8: Optimal data aggregation in graph G and G . In G, node 1 transmits at time 0 and in G , node 1 does not transmits at time 0, even though node 1 has the same future in both G and G .

Figure 9 :

 9 Figure 9: Optimal data aggregation in graph G 1 and G 2 . In G 1 , node 2 transmits at time 0 whereas in G 2 , node 1 does.

Corollary 1 .

 1 Algorithm GDAS, in BRC with bound T , satisfies:duration(GDAS(G; s)) ≤ T (n -1)

25 while remainingN

  odes = ∅; 26 for t = t f -1, . . . , 0 do

1 S ← empty sequence 2 remainingN odes ← V \ {s} 3 t ← 0 4 do 5 ts ← t 6 for u ∈ V do 7 datat[u] ← {u} 8 while remainingN odes ⊂ datat[s] do 9 datat+1 ← datat 10 for (u, v) ∈ Et do 11 datat+1[v] ← datat[u] ∪ datat[v] 12 datat+1[u] ← datat[u] ∪ datat[v]

13 t ← t + 1 14 tf ← t 15 marked ← {s} 16 for t = t f -1, . . . , ts do 17 St ← ∅ 18 previouslyM arked ← marked 19 for v ∈ {Nt(u)|u ∈ previouslyM arked} do 20 if canT ransmit(v, St, marked) ∧ datat-1[v] ∩ remainingN odes = ∅ then 21 remainingN odes ← remainingN odes \ {v} 22 marked ← marked ∪ {v} 23 St ← St ∪ {v} 24 t ← tf 27 St ← St ∪ St+1 28 return S

We suppose here that the area is a two dimensional plane, but our results naturally extend to greater dimensions

$ This work was performed within the Labex SMART supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02.