D ' Gianlorenzo
email: gianlorenzo.dangelo@inria.fr

Angelo

Mattia D'emidio

Daniele Frigioni
email: daniele.frigioni@univaq.it

Camillo Vitale
email: camillo.vitale@gmail.com

Fully Dynamic Maintenance of Arc-Flags in Road Networks

The problem of finding best routes in road networks can be solved by applying Dijkstra's shortest paths algorithm. Unfortunately, road networks deriving from real-world applications are huge yielding unsustainable times to compute shortest paths. For this reason, great research efforts have been done to accelerate Dijkstra's algorithm on road networks. These efforts have led to the development of a number of speed-up techniques, as for example Arc-Flags, whose aim is to compute additional data in a preprocessing phase in order to accelerate the shortest paths queries in an on-line phase. The main drawback of most of these techniques is that they do not work well in dynamic scenarios.

In this paper we propose a new algorithm to update the Arc-Flags of a graph subject to edge weight decrease operations. To check the practical performances of the new algorithm we experimentally analyze it, along with a previously known algorithm for edge weight increase operations, on real-world road networks subject to fully dynamic sequences of operations. Our experiments show a significant speed-up in the updating phase of the Arc-Flags, at the cost of a small space and time overhead in the preprocessing phase.

Introduction

The problem of finding best connections in transportation networks has received a lot of attention in the last years. If travel times are assigned to the edges of the graph representing the network, this problem can be easily solved by applying Dijkstra's algorithm to find the shortest path between two points. Unfortunately, transportation networks deriving from real-world applications tend to be huge yielding unsustainable times to compute shortest paths. For this reason, great research efforts have been done over the last decade to accelerate Dijkstra's algorithm on typical instances of transportation networks, such as road or railway networks (see [START_REF] Delling | Engineering Route Planning Algorithms[END_REF] for a recent overview). These research efforts have led to the development of a number of speed-up techniques, whose aim is to compute additional data in a preprocessing phase in order to accelerate the shortest paths queries during an on-line phase. However, most of the speed-up techniques developed in the literature do not work well in dynamic scenarios, when edge weights changes occur to the network due to traffic jams or delays of trains. In other words, the correctness of these speed-up techniques relies on the fact that the network does not change between two queries. Unfortunately, such situations arise frequently in practice. In order to keep the shortest paths queries correct, the preprocessed data need to be updated. The easiest way is to recompute the preprocessed data from scratch after each change to the network. This is in general unfeasible since even the fastest methods need too much time. In general, the typical update operations that can occur on a network can be modelled as insertions and deletions of edges and edge weight changes (weight decrease and weight increase). When arbitrary sequences of the above operations are allowed, we refer to the fully dynamic problem, otherwise we refer to the partially dynamic problem; if only insertions and weight decrease (deletion and weight increase, respectively) operations are allowed, then the partially dynamic problem is known as the incremental (decremental, respectively) problem.

Related Works. We refer here only to papers on the dynamic case and refer to [START_REF] Delling | Engineering Route Planning Algorithms[END_REF] as a survey for the static case. A number of efforts have been done in the last years to accelerate the computation of shortest paths in dynamic scenarios [1-4, 6, 13, 15]. The first of these techniques was Geometric Containers [START_REF] Wagner | Geometric Containers for Efficient Shortest-Path Computation[END_REF], whose key idea is to allow suboptimal containers after a few updates. However, this approach yields a loss in query performance. The same holds for the dynamic variant of Arc-Flags [START_REF] Lauther | An extremely fast, exact algorithm for finding shortest paths[END_REF] proposed in [START_REF] Berrettini | Arc-flags in dynamic graphs[END_REF], where, after a number of updates, the query performances get worse yielding only a low speed-up over Dijkstra's algorithm. In [START_REF] Sanders | Dynamic Highway-Node Routing[END_REF] the authors combine ideas from highway hierarchies [START_REF] Sanders | Engineering Highway Hierarchies[END_REF] and overlay graphs [START_REF] Schulz | Using Multi-Level Graphs for Timetable Information in Railway Systems. In 4th Work[END_REF] yielding very good query times in dynamic road networks. The ALT algorithm, introduced in [START_REF] Goldberg | Computing the Shortest Path: A* Search Meets Graph Theory[END_REF] works considerably well in dynamic scenarios where edge weights can increase their value. Also in this case, query performances get worse if too many edges weights change [START_REF] Delling | Landmark-Based Routing in Dynamic Graphs[END_REF]. Summarizing, all above techniques work in a dynamic scenario as long as the number of updates is small. As soon as the number of updates is greater than a certain value, it is better to repeat the preprocessing from scratch. To our knowledge, the only other dynamic technique known in the literature with no loss in query performance is that in [START_REF] Sanders | Dynamic Highway-Node Routing[END_REF]. In [START_REF] Delling | Customizable route planning[END_REF], a very practically efficient algorithm has been given to compute shortest paths in continental road graphs with arbitrary metrics, whose efficiency is also due to the use of parallelism. This algorithm is fast enough to be used in dynamic scenarios for the recomputation from scratch of shortest paths. Recently, a data structure named Road-Signs has been introduced in [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF] to compute and update the Arc-Flags of a graphs. In detail, in [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF] the authors define an algorithm to preprocess Road-Signs and a decremental algorithm to update them each time that a weight increase operation occurs on an edge of the graph. As the updating algorithm is able to correctly update Arc-Flags, there is no loss in query performance. They also experimentally analyze this algorithm in real-world road networks showing that it yields a significant speed-up in the updating phase of Arc-Flags with respect to the recomputation from-scratch, at the price of a small space and time overhead in the preprocessing phase. However, the solution in [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF] is not able to update Arc-Flags in a fully dynamic scenario.

Contribution of the paper. We propose a new incremental algorithm which is able to update the Arc-Flags of a graph by updating Road-Signs, during a sequence of weight decrease operations. Since the new incremental algorithm uses the same data structures of the decremental solution of [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF], then the combination of these two solutions can be used to update Arc-Flags in a fully dynamic scenario. To check the practical usefulness of this combination we implemented the two algorithms and performed an extensive experimental study against the recomputation from scratch of Arc-Flags on fully dynamic sequences of weight increase and weight decrease operations on real world road networks. The results of our experiments can be summarized as follows: in comparison to the recomputation from-scratch of Arc-Flags, we obtained a significant speed-up in the updating phase, at the cost of a small space and time overhead in the preprocessing phase. In detail, we experimentally show that the fully dynamic algorithm is able to update the Arc-Flags between 40 and 431 times faster than the recomputation from scratch in average. However, in order to compute and store the Road-Signs, we need an overhead in the preprocessing phase and in the space occupancy. We experimentally show that such an overhead is small compared to the speed-up gained in the updating phase. In fact, the preprocessing requires, in average, 2.10 and 2.36 times the time and the space required by Arc-Flags, respectively.

Preliminaries

Road Graphs. A road graph is a weighted directed graph G = (V, E, w), used to model real road networks, where nodes represent points on the network, edges represent road segments between two points and the weight function w : E → R + represents an estimate of the travel time needed to traverse road segments. Given G, we denote as Ḡ = (V, Ē) the reverse graph of G where Ē = {(v, u) | (u, v) ∈ E}. A minimal travel time route between two crossings S and T in a road network corresponds to a shortest path from the node s representing S and the node t representing T in the corresponding road graph. The total weight of a shortest path between nodes s and t is called distance and it is denoted as

d(s, t). A partition of V is a family R = {R 1 , R 2 , . . . , R r } of subsets of V called regions, such that each node v ∈ V is contained in exactly one region. Given v ∈ R k , v is a boundary node of R k if there exists an edge (u, v) ∈ E such that u ∈ R k .
Minimal routes in road networks can be computed by shortest paths algorithms such as Dijkstra's one. In order to perform an s-t query, the algorithm grows a shortest path tree starting from s and stopping as soon as it visits t. A simple variation of Dijkstra's algorithm is bidirectional Dijkstra which grows two shortest path trees starting from both s and t. In detail, the algorithm performs a visit of G starting from s and a visit of Ḡ starting from t. The algorithm stops as soon the two visits meet at some node in the graph.

Arc-Flags. The preprocessing phase of Arc-Flags first computes a partition R = {R 1 , R 2 , . . . , R r } of V and then associates a label to each edge (u, v) in E. A label contains, for each region R k ∈ R, a flag A k (u, v) which is true if and only if a shortest path in G towards a node in R k starts with (u, v). The set of flags of an edge (u, v) is called Arc-Flags label of (u, v). The preprocessing phase associates also Arc-Flags to edges in the reverse graph Ḡ. The query phase of Arc-Flags consists of a modified version of the bidirectional Dijkstra's algorithm: the forward search only considers those edges for which the flag of the target node's region is true, while the backward search follows only those edges having a true flag for the source node's region. The main advantage of Arc-Flags is its easy query algorithm combined with an excellent query performance. However, preprocessing is very time-consuming since it grows a full shortest path tree from each boundary node of each region. This is unpractical in dynamic scenarios where, in order to keep correctness of queries, the preprocessing phase has to be performed from scratch any time that an edge weight changes.

Road-Signs. Given a road graph G = (V, E, w), a partition R = {R 1 , R 2 , . . . , R r } of V in regions, an edge (u, v) ∈ E and a region R k ∈ R, the Road-Sign RS k (u, v) of (u, v) to R k is the subset of boundary nodes b of R k , such
that there exists a shortest path from u to b that contains (u, v). The Road-Signs of (u, v) are represented as a boolean vector, whose size is the overall number of boundary nodes, where the i-th element is true if and only if the i-th boundary node is contained in RS k (u, v), for some region R k . Hence, such a data structure requires O(|E| • |B|) memory, where B is the set of boundary nodes of G induced by R. Notice that, in [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF] it has been also proposed a technique to compact road signs that requires O((|E| -|V |) • |B|) overall space. The Road-Signs of G can be computed in the preprocessing phase of Arc-Flags. Given an edge (u, v) and a region R k , A k (u, v) is set to true if and only if (u, v) is an edge in at least one of the shortest path trees grown for the boundary nodes of R k . Such a procedure can be generalized to compute also Road-Signs. In fact, it is enough to add the boundary node b to RS k (u, v) if (u, v) is in the tree grown for b.

Incremental update of Arc-Flags

Given a road graph G = (V, E, w) and a partition R = {R 1 , R 2 , . . . , R r } of V in regions, we consider the problem of updating the Arc-Flags of G in a dynamic scenario where a sequence of only weight decrease operations C = (c 1 , c 2 , . . . , c h ) occur on G. We denote as G i = (V, E, w i ) the graph obtained after i weight decrease operations, 0 ≤ i ≤ h, G 0 ≡ G. Each operation c i decreases the weight of one edge e i = (x i , y i ) of an amount γ i > 0, such that w i (e i ) = w i-1 (e i )-γ i > 0 and w i (e) = w i-1 (e), for each edge e = e i in E. Our algorithm is based on the following proposition given in [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF], which provides a straightforward method to compute the Arc-Flags of a graph given the Road-Signs of such graph.

Proposition 1. [3] Given G = (V, E, w), a partition R = {R 1 , R 2 , . . . , R r } of V , an edge (u, v) ∈ E and a region R k ∈ R, the following conditions hold: (i) if u, v ∈ R k , then A k (u, v) = true; (ii) if RS k (u, v) = ∅, then A k (u, v) = true; (iii) if u or v is not in R k and RS k (u, v) = ∅, then A k (u, v) = f alse.
Hence in what follows, we describe how our solution updates Road-Signs. The algorithm is denoted as IncRS and its pseudo-code is given in Figure 1. The algorithm is based on the observation that, when c i occurs, all the shortest paths which contain (x i , y i ) in G i-1 (i.e. before c i ) are shortest paths also in G i (i.e. after c i ). Therefore, if some boundary node for some region R k belongs to RS k (x i , y i ) before c i it belongs also to RS k (x i , y i ) after c i and no update is needed for it. However, it could happen that the shortest path from x i to some boundary node b of R k in G i-1 does not contain (x i , y i ) but, after the weight decrease, the new shortest path in G i contains (x i , y i ). In this case, b needs to be added to RS k (x i , y i ) and removed from RS k (x i , w), where (x i , w) is the edge outgoing x i whose road signs b belongs to. Same arguments can be applied to the incoming edges of x i , (z, x i ): if a boundary node belongs to RS k (z, x i ) and RS k (x i , y i ) before c i , then it belongs also to RS k (z, x i ) after c i ; if a boundary node b is in RS k (x i , y i ) (because it was already in RS k (x i , y i ) or because it has been added to it as a consequence of c i ) and it does not belong to RS k (z, x i ) before c i , then it might be added to RS k (z, x i ) in the case that the shortest path from z to b in G i contains the sub-path (z, x i , y i ). We iteratively apply the same arguments to the other edges of the graph, starting from x i and traversing its incoming edges. Note that, if at some point of the iteration we find out that the shortest path from a node z to some boundary node b does not decrease, then we do not need to add or remove b to any incoming edge of z. This allows us to reduce the search space of the algorithm.

IncRS works in two phases. In the first phase (lines 1-8) RS k (x i , y i ) is updated by possibly adding new boundaries b ∈ RS k (x i , y i ) to it. This phase is performed for each b ∈ RS k (x i , y i ) separately (line 1). In the pseudo-code, when needed, we store distances between a node u and a boundary b in data structure D[u, b] and we use an heap H to compute the minimum among the computed distances. Since each boundary node is processed separately, these data structures are overwritten at each computation, hence requiring O(n) space in the worst case. In detail, at lines 2 and 3-4 we compute the distances from y i to b and from node r such that b ∈ RS k (x i , r) to b, respectively. Then, at line 5, we check whether the weight of the path passing through y i is smaller than that passing through r (that is the shortest path from x i to b in G i-1 ). In the affirmative case, we update the road signs by adding b to RS k (x i , y i ) and removing b from RS k (x i , r) (lines 6-7). Moreover, we store the new distance from x i to b in D[x i , b] (line 8) in order to use it in the next phase. In the second phase (lines 9-22) the road signs are updated for each b ∈ RS k (x i , y i ) separately. The updating is done by mimicking the Dijkstra's algorithm, that is by greedily visiting the reverse graph starting from x i and stopping when a node does not need to update the road signs of its outgoing edges wrt b. At line 11, H is initialized by inserting x i into it using D[x i , b] as key. If b was already in RS k (x i , y i ), then D[x i , b] has not been computed at line 8 and hence it is computed at line 10. Until H is not empty (line 12), a node z and its distance

Procedure: IncRS(Gi-1, ci, R k ) Input : Graph Gi-1, weight decrease ci on edge (xi, yi) and region R k ∈ R Output: Updated RS k (u, v) ∀ (u, v) ∈ E 1 foreach b ∈ RS k (xi, yi) do

D[z, b

] is extracted from H. Then, for each node z i such that (z i , z) ∈ E, at lines 14-22 we perform the same steps done for x i and (x i , y i ): we compute the distance from r such that b ∈ RS k (z i , r) to b; we check whether the weight of the path from z i to b passing through z is smaller than that passing through r and, in the affirmative case, we update the road signs by adding b to RS k (z i , z) and removing it from RS k (z i , r); finally, we store the new distance from z i to b in D[z i , b] and insert z i into H or decrease its key if it already belongs to H.

The following theorem states the correctness of IncRS.

Theorem 1. Given G = (V, E, w) and a partition R = {R 1 , R 2 , . . . , R r } of V , for each (u, v) ∈ E and R k ∈ R, IncRS correctly updates RS k (u, v) and A k (u, v)
after a weight decrease operation on an edge of G.

Proof. Let us consider a region R k ∈ R and a weight decrease operation c i on edge (x i , y i ). From Proposition 1, it is enough to show that IncRS correctly updates RS k (u, v) after c i , for each (u, v) ∈ E. Given an edge (u, v), we denote as RS k (u, v) and RS ′ k (u, v) the road-signs of (u, v) before and after c i , respectively. As c i decreases the weight of (x i , y i ), then RS k (x i , y i ) ⊆ RS ′ k (x i , y i ), moreover for each (u, v) ∈ E, RS k (u, v) can be modified by adding or removing boundary nodes in RS

′ k (x i , y i ), that is RS ′ k (u, v) \ RS k (u, v) ⊆ RS ′ k (x i , y i ) and RS k (u, v) \ RS ′ k (u, v) ⊆ RS ′ k (x i , y i ).
It follows that phase one (lines 1-8) correctly updates the road-signs of edges outgoing from x i . The road-signs of the remaining edges are updated in phase two, whose correctness is shown separately for each boundary node b ∈ RS ′ k (x i , y i ) and derives from the following facts. F1 The nodes are extracted from H at line 13 in non-decreasing order of keys. ] was minimum and hence either u has been extracted into H after t u or its key has been decreased after t u . In both cases, the algorithm passed the test at line 17 which implies that there exists a node v 1 and a time

t v1 < t v such that D[v 1 , b] < D[v, b] < D[u, b], where D[v 1 , b]
is the key of v 1 at time t v1 when v 1 is extracted from H. If we iteratively repeat this arguments for node v 1 , we obtain a sequence of nodes v ≡ v 0 , v 1 , v 2 , . . . , v k , where v k ≡ x i , such that, if we denote as D[v j , b] the key of v j when it is extracted from H at time t vj , then D[v j+1 , b] < D[v j , b] and t vj+1 < t vj for each j = 0, 1, . . . k -1.

For the condition at line 12, one of the nodes in the sequence v j has to belong to H with key D[v j , b] < D[u, b] at time t u which contradicts the fact that, at time t u , node u is the node with the minimum key. F2 A node is extracted from H at line 13 at most once. Suppose that a node u is extracted from H at two different times t 1 < t 2 . Then, node u has been inserted into H at two different times, denoted as t1 and t2 , when it does not belong to H. It follows that [ t1 , t 1 ] ∩ [ t2 , t 2 ] = ∅. Further, let us denote as D t1 [u, b] (D t2 [u, b], resp.) the key of u at time t1 ( t2 , resp.) which is equal to that at time t 1 (t 2 , resp.). Let us consider the two (possibly different) nodes v 1 and v 2 which are extracted from H immediately before times t1 and t2 , respectively. Let us analyze the keys extracted from H. At time t1 , v 1 is extracted with key

D[v 1 , b], D[u, b] is set to D t1 [u, b] = w(u, v 1 ) + D[v 1 , b] and b is added to RS k (u, v 1 ). At time t 1 , u is extracted with key D t1 [u, b]. At time t2 , v 2 is extracted with key D[v 2 , b], and D[u, b] is set to D t2 [u, b] = w(u, v 2 ) + D[v 2 ,
b], it follows that the test at line 17 returned true and, as b

∈ RS k (u, v 1 ), w(u, v 2 ) + D[v 2 , b] < w(u, v 1 ) + D[v 1 , b]. Hence D t2 [u, b] < D t1 [u, b]. At time t 2 , u is extracted with key D t2 [u, b] and, since t 1 < t 2 , this contradicts Fact F1. F3 For each edge (u, v) such that RS ′ k (u, v) = RS k (u, v), u is inserted into H. We show a stronger statement that is: if a node changes its distance to b ∈ RS ′ k (u, v) it is inserted into H.
By contradiction, let us consider the node u such that: it changes its distance to b, it is not inserted into H, and its distance to b after c i is minimal among the nodes with the same properties. By this last property, the node v on the shortest path from u to b after

c i is inserted into H. When v is extracted from H, either b belongs to RS k (u, v) or w(u, v) + D[v, b] < w(u, r) + D[r, b],
where r is the node such that b ∈ RS k (u, r). In both cases, u is inserted into H at line 22. F4 When a node u is extracted from H at line 13, for each (u, v) ∈ E, RS k (u, v) is correctly updated. 1. Tested road graphs. 1st col.: the graph; 2nd and 3rd col.s: number of nodes and edges in the graph; 4th-7th col.s: percentage of edges into categories: motorways (mot), national roads (nat), regional roads (reg), and urban streets (urb).

By contradiction, let us consider the first node u whose outgoing edges have wrong road-signs when u is extracted from H. Let us consider the node v such that b ∈ RS k (u, v) when u is extracted, that is v is the node that was extracted from H immediately before the last time that either u is inserted into H or its key is decreased. As u is the first node whose outgoing edges have wrong roadsigns when it is extracted from H, then the road-signs of the edges outgoing from v are correctly updated. Moreover, also the road-signs of edges outgoing from w, for each (u, w) ∈ E are correctly updated. In fact two cases may arise: if w changes the road-signs of its outgoing edges then, by Fact F3, it is inserted into H, by facts F1 and F2, it is extracted before u and hence, by hypothesis, it correctly updates the road-signs of its outgoing edges; otherwise the road-signs of its outgoing edges are already correct. In any case, when u is inserted into H the distances used in the test of line 17 are correctly computed and hence the road signs are correctly updated.

From a theoretical point of view, IncRS requires a computational complexity which is, in the worst case, comparable to that of the recomputation from scratch of Arc-Flags. However, IncRS focuses the computation only on the nodes that change shortest paths to a subset of the boundary nodes (and possibly on the neighbors of such nodes). In contrast, the recomputation from scratch computes all the shortest paths from any boundary node to each other node of the network. This difference is difficult to be captured by a worst case analysis and this motivates the experimental study of the next section.

Experimental study

In this section, we compare the performances of the incremental algorithm proposed in this paper and the decremental algorithm of [START_REF] Angelo | Dynamic arc-flags in road networks[END_REF], whose combination is named here DynRS, on fully dynamic sequences of weight change operations against the recomputation from scratch of Arc-Flags. We used the implementation of Arc-Flags of [START_REF] Berrettini | Arc-flags in dynamic graphs[END_REF]. Furthermore, it has been shown in [START_REF] Möhring | Partitioning Graphs to Speedup Dijkstra's Algorithm[END_REF] that the best query performances for Arc-Flags are achieved when partitions are computed by using arc-separator algorithms. For this reason, we used arc-separators obtained by the METIS library [START_REF] Karypis | METIS -A Family of Multilevel Partitioning Algorithms[END_REF]. Our experiments are performed on a workstation equipped with a Quad-core 3.60 GHz Intel Xeon X5687 processor, with 12MB of internal cache and 24 GB of main memory. The program has been compiled with GNU g++ compiler 4.4.3 under Linux (kernel 2.6.32).

We consider seven road graphs available from PTV [11] representing the road networks of Luxembourg, Denmark, Belgium, Austria, Spain, Netherlands and Sweden, denoted as lux, dnk, bel, aut, esp, ned and swe, respectively. In each graph, edges are classified into four categories according to their speed limits: motorways (mot), national roads (nat), regional roads (reg) and urban streets (urb). The main characteristics of these graphs are reported in Table 1. We consider fully dynamic sequences of updates simulating disruptions on road networks built as follows. The most significant operation that can occur on a road segment is the increase of a weight, which simulates a delay in the travel time on that segment due, for instance, to a traffic jam. This operation is usually followed by a weight decrease on the same road segment which simulates the restore from the delay. Hence, for each operation in the sequence that increases the weight of an edge (x i , y i ) of a quantity γ i , there is a corresponding subsequent operation which decreases the weight of edge (x i , y i ) of the same amount γ i . We execute, for each graph considered and for each road category, random sequences of 100 weight-change operations as described above. The weight-change amount for each operation is chosen uniformly at random in [25%, 75%] of the weight of the edge involved in that operation. As a performance indicator, we choose the time used by the algorithms to complete a single update during the execution of a sequence. We measure, as speed-up factor, the ratio between the time required by the recomputation from scratch of Arc-Flags and that required by DynRS. The results are reported in Fig. 23, and in Table 2. on the right does. Outlier values occur when DynRS performs much better than Arc-Flags because the number of Road-Signs changed is very small. We consider a test as outlier if the speed-up factor is 1000 times the speed-up factor median value. Even without outliers, the speed-up gained by DynRS is high.

Notice that, in the case of swe (Fig. 2), the speed-up factors are quite similar on the different categories, thus highlighting an independency from categories. This is the typical behavior of road networks, as shown also for bel, dnk, esp and aut in Table 2, where we report the average time of the recomputation from-scratch of Arc-Flags and the average time of DynRS, the average ratios between these quantities and the speed-up factors. The only exceptions are lux and ned, where the percentage of motorways is very low. This is the reason why we highlight the behavior of DynRS on ned in Fig. 3, where the speed-up factor reaches the highest values when update operations occur on urban edges, while it is smaller when they occur on motorway edges. In fact, when an update operation occurs on urban edges, the number of shortest paths that change is small compared to the case that an update operation occurs on motorways edges. This implies that DynRS, which selects the nodes that change such shortest paths and focus the computation only on such nodes, performs better than the recomputation from-scratch of the shortest paths from any boundary node.

We note that, the speed-up factor increases with the size of the network. This can be explained by the fact that, when an edge update operation occurs, it affects only a part of the graph, hence only a subset of the edges in the graph need to update their Arc-Flags or Road-Signs. In most of the cases, this part is small compared to the size of the network and, with high probability, it corresponds to the subnetwork close to the edge increased or closely linked to it. In other words, it is unlike that a traffic jam in a certain part of the network affects the shortest paths of another part which is far or not linked to the first one. Clearly, this fact is more evident when the road network is big. In conclusion, it is evident from Table 2, that DynRS outperforms the recomputation from-scratch by far and that it requires reasonable computational time. 2. Avg update times and speed-up factors of DynRS. 1st col.: graph; 2nd col.: category where the weight changes occur; 3rd and 4th col.s: avg computational time for Arc-Flags and DynRS, resp.; 5th col.: ratio between the values of the 3rd and the 4th col.s; 6th col.: avg speed-up factors of DynRS against Arc-Flags.

Regarding the preprocessing phase, in Table 3 we report the computational time and the space occupancy required by Arc-Flags and DynRS. Table 3 shows that, for computing Road-Signs along with Arc-Flags, we need about twice the computational time required for computing only Arc-Flags, which is a small overhead compared to the speed-up gained in the updating phase. The same observation can be done regarding the space occupancy. In fact, Table 3 also shows that the space required for storing both Road-Signs and Arc-Flags is between 1.44 and 3.48 times that required to store only Arc-Flags. 3. Preprocessing time and space. 1st col.: graph; 2nd col.: number of regions; 3rd col.: preprocessing time, in seconds, of Arc-Flags; 4th col.: preprocessing time, in seconds, of Arc-Flags and Road-Signs; 5th col.: ratio between the values reported in the 4th and the 3rd column; 6th col.: space required, in Bytes, to store Arc-Flags; 7th col.: space required, in Bytes, to store Arc-Flags and Road-Signs; 8th col.: ratio between the values of the 7th and the 6th column.

2 8 DFig. 1 .

 81 Fig. 1. Pseudo-code of algorithm IncRS.

  Let us consider two nodes u and v extracted from H at times t u and t v with keys D[u, b] and D[v, b], respectively. By contradiction, suppose that t u < t v and D[u, b] > D[v, b]. Since at line 13 the node with the minimum key is extracted, at time t u , D[u, b

Fig. 2 .

 2 Fig. 2. Speed-up factors of the fully dynamic algorithm for the road network of Sweden, without (left) and with (right) outliers.

Fig.s 2 Fig. 3 .

 23 Fig. 3. Speed-up factors of the fully dynamic algorithm for the road network of the Netherlands, without (left) and with (right) outliers.

  graph reg. AF (s) AF+RS (s) t. ratio AF (B) AF+RS (B) s. ratio

	lux	64	5.52	11.79	2.14 1 209 216	1 744 531	1.44
	dnk 128 542.46	1 104.16	2.04 17 442 368	43 932 508	2.52
	bel 128 644.34	1 373.11	2.13 18 624 736	64 759 010	3.48
	aut 128 940.83	1 995.93	2.12 27 166 432	78 720 055	2.90
	esp 128 737.31	1 446.65	1.96 29 901 408	67 664 666	2.26
	ned 128 1 606.29	3 214.34	2.00 36 461 184	64 612 836	1.77
	swe 128 2 681.16	5 986.62	2.23 55 750 048	163 151 588	2.93
	Table


Ichrak Amdouni
email: ichrak.amdouni@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Cedric Adjih
email: cedric.adjih@inria.fr

Node Coloring in Wireless Networks: Complexity Results and Grid Coloring

Coloring is used in wireless networks to improve communication efficiency, mainly in terms of bandwidth, energy and possibly end-to-end delays. In this paper, we define the h-hop node coloring problem, with h any positive integer, adapted to two types of applications in wireless networks. We specify both general mode for general applications and strategic mode for data gathering applications. We prove that the associated decision problem is NP-complete. We then focus on grid topologies that constitute regular topologies for large or dense wireless networks. We consider various transmission ranges and identify a color pattern that can be reproduced to color the whole grid with the optimal number of colors. We obtain an optimal periodic coloring of the grid for the considered transmission range. We then present a 3-hop distributed coloring algorithm, called SERENA. Through simulation results, we highlight the impact of node priority assignment on the number of colors obtained for any network and grids in particular. We then compare these optimal results on grids with those obtained by SERENA and identify directions to improve SERENA.

I. MOTIVATIONS

Coloring has been used in wireless ad hoc and sensor networks to improve communications efficiency by scheduling medium access. Indeed, only nodes that do not interfere can have the same color and then are allowed to transmit simultaneously. Hence coloring can be used to schedule node activity. The expected benefits of coloring are threefold:

1) At the bandwidth level where no bandwidth is lost in collisions, overhearing and interferences are reduced. Moreover, the use of the same color by several nodes ensures the spatial reuse of the bandwidth [START_REF] Rajendran | Energy-efficient, collision-free medium access control for wireless sensor networks[END_REF], [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF], [START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF], [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF], [START_REF] Lee | FlexiTP: a flexible-schedulebased TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks[END_REF]. 2) At the energy level where no energy wasted in collision.

Furthermore, nodes can sleep to save energy without loosing messages sent to them because of the node activity schedule based on colors [START_REF] Rajendran | Energy-efficient, collision-free medium access control for wireless sensor networks[END_REF], [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF], [START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF], [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF], [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF], [START_REF] Lee | FlexiTP: a flexible-schedulebased TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks[END_REF]. 3) At the delay level where the end-to-end delays can be optimized by a smart coloring ensuring for instance that any child accesses the medium before its parent in the data gathering tree [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF], [START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF], [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF], [START_REF] Lee | FlexiTP: a flexible-schedulebased TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks[END_REF]. Concerning coloring algorithms, two types of coloring are distinguished: node coloring and link coloring. With link coloring, time slots are assigned per link. Only the transmitter and the receiver are awake, the other nodes can sleep. If the link is lightly loaded, its slot can be underused. Moreover, broadcast communications are not easy: the source must send a copy to each neighbor. On the contrary, with node coloring, the slot is assigned to the transmitter that can use it according to its needs: unicast and/or broadcast transmissions. Hence the slot use is optimized by its owner.

The value of h in h-hop node coloring must be chosen to ensure that any two nodes that are strictly more than hhop away can transmit simultaneously without interfering. It follows that h depends on the type of communication that must be supported. For instance, broadcast transmissions require 2hop coloring, whereas unicast transmission with immediate acknowledgement (i.e. the receiver uses the timeslot of the sender to transmit its acknowledgement) requires 3-hop coloring, see [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF] for an illustrative example.

This paper is organized as follows. First, we define the coloring problem in Section II and introduce definitions. We position our work with regard to the state of the art in Section III. In Section IV, we prove that the h-hop coloring decision problem is NP-complete in both general and strategic modes, for any integer h > 0. That is why, we propose SERENA, an heuristic to color network nodes. In Section V, we obtain theoretical results determining an optimal periodic color pattern for grid topologies with various transmission ranges. We compare them with SERENA results in Section VI. Finally, we conclude in Section VII pointing out future research directions.

II. COLORING PROBLEM DEFINITION A. Generalities

Let G(V, E) be an undirected graph representing the network topology. Each vertex v i ∈ V represents a network node with i ∈ [1, n], where n is the number of network nodes. For all vertices v 1 and v 2 in V , the edge (v 1 , v 2 ) ∈ E if and only if the two nodes v 1 and v 2 are one-hop neighbors. There are two types of graph coloring: vertex (or node) coloring assigns a color to each vertex of the graph, whereas edge (or link) coloring assigns a color to each edge of the graph.

Definition 1: One-hop node coloring of G consists in (i) assigning each vertex in V a color in such a way that two adjacent vertices have different colors and (ii) using the smallest number of colors.

We can easily extend one-hop node coloring to h-hop node coloring, where h is an integer strictly positive. h-hop node coloring is also called h-distance node coloring and 1-hop coloring of the power h of the graph G in [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF].

Definition 2: For any integer h > 0, two nodes u and v are said h-hop neighbors if and only if the shortest path between them has a length of h links.

Definition 3: For any integer h > 0, a h-hop node coloring is said valid if and only if any two nodes that are k-hop neighbors, with 1 ≤ k ≤ h have not the same color.

Definition 4: A valid h-hop node coloring is said optimal if and only if no valid h-hop node coloring uses less colors that this coloring. It can be easily shown that the breakage of a link does not compromise the validity of a coloring, whereas the creation of a new link may. For simplicity reasons, colors are represented by natural integers, starting with zero.

B. Application to wireless networks

We can notice that almost all coloring algorithms when applied to a wireless network, make the assumption of an ideal wireless environment.

Definition 5: A wireless environment is said ideal if and only if:

• Any node has a unique address in the wireless network.

• Links are symmetric: if node u sees node v as a onehop neighbor, then conversely node v sees node u as a one-hop neighbor. • Links are stable. More precisely, link creation during or after the completion of the coloring algorithm is not taken into account. • For any node u, any node w that is not in transmission range of u cannot prevent u from correctly receiving a message sent by v of its one-hop neighbors. Definition 6: For any node u, its 1-hop neighbors are all the nodes located in the disk centered at node u of radius the transmission range R. For any integer h > 1, any two nodes u and v are h-hop neighbors if and only if u is (h -1)-hop away from a 1-hop node of v. Figure 1 depicts a node w that belongs to the disk centered at node u of radius 2R. Node w is not a 2-hop node of u, whereas v 2 is because of the existence of v 1 . Consequently, with a 2-hop coloring, v 1 and v 2 cannot have the same color as u, whereas w can. If now we consider a transmission range R = 2R and a 1-hop coloring, nodes v 1 , v 2 and w cannot have the same color as u. The following example is taken in grid topologies, where the transmission range is expressed in grid step units. For any grid node u, Figure 2 depicts the nodes that cannot take the same color as u in case a) of a 1-hop coloring with transmission range=6, in case b) of 2-hop coloring with transmission range=3 and finally in case c) of 3-hop coloring with transmission range=2. Remark 1: For any graph G, for any transmission ranges R and R ≥ 1, for any integer h and k > 0

such that R • k = R • h, h-hop coloring of G with transmission range R is not equivalent to k-hop coloring of G with transmission range R .
To be able to support different applications, two modes are introduced in h-hop node coloring:

• the general mode to support general applications, where the destination of any unicast transmission can be any network node. The general mode is the default mode of the h-hop node coloring problem defined in section II-A.

• the strategic mode to support data gathering applications, where the destination of any unicast transmission is either the parent or a child of the node in the data gathering tree. With regard to the general mode, the strategic mode requires an additional constraint to be met: Constraint 1: Any node must select a color strictly higher than the color taken by its parent in the data gathering tree. To compare the performance of coloring algorithms, two criteria are used:

• the number of colors used: the optimal number is called chromatic number. • the number of rounds needed to color the graph. By definition, in a round, a node is able to send a message to its neighbors, to receive their message and to process them. We now present a brief state of the art dealing with graph coloring and its application to radio networks and wireless sensor networks.

III. STATE OF THE ART

Coloring has been first introduced in graphs with vertex coloring and edge coloring. One-hop vertex coloring has been shown NP-complete in [START_REF] Garey | Computers and intractability: a guide to theory of NP-completeness[END_REF] for the general case, whereas graphs with maximum vertex degree less than four and bipartite graphs can be colored in polynomial time. The first algorithms proposed were centralized like the greedy algorithm Dsatur (no color backtracking) [START_REF] Brelaz | New methods to color the vertices of a graph[END_REF], where the vertex with the highest number of already colored neighbor vertices is colored first. Later on, decentralized ones like Distributed Largest First [START_REF] Hansen | Distributed largestfirst algorithm for graph coloring[END_REF] were designed. In this algorithm, each node selects a color. It is allowed to keep its color only if it has the largest degree among its neighbors but also if this color does not conflict with the colors of its neighbors. This algorithm runs in O(∆ 2 logn), where ∆ is the largest vertex degree and n the number of vertices. The algorithm given in [START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF] proceeds iteratively by reducing the number of colors step-by-step; initially, all nodes have distinct colors. This algorithm runs in O(∆ 2 logn) and uses a number of colors close to ∆.

The theoretical performance of coloring algorithms has been studied in the literature, in general for 2-hop coloring. Because minimum 2-hop coloring is NP-complete, the focus has been on evaluating the performance of approximation algorithms, whose objective is not to find the optimal coloring, but at least to be reasonably close. A typical approximation algorithm for coloring is FirstFit: FirstFit [START_REF] Cargiannis | A tight bound for online coloring of disk graphs[END_REF] sequentially assigns colors to nodes; it chooses for each node the first available color. Depending of the order in which the nodes are colored, different results (with varied performance) are obtained.

Edge coloring problems can be transformed into a vertex version: an edge coloring of a graph is just a vertex coloring of its link graph. Applied to wireless networks, edge coloring has been called link scheduling. For instance, [START_REF] Gandham | Link scheduling in sensor networks: distributed edge coloring revisited[END_REF] obtains a TDMA MAC schedule enabling two-way communication between every pair of neighbors. Edges are colored and a feasible direction of transmission is found.

Coloring has then been applied to radio networks to provide a collision-free medium access. The goal is to schedule transmissions in time slots, in such a way that two senders allowed to transmit in the same slot do not interfere. Such a problem is also called broadcast scheduling in [START_REF] Ramaswami | Distributed scheduling of broadcasts in a radio network[END_REF], channel assignment in [START_REF] Krumke | Models and approximation algorithms for channel assignment in radio networks[END_REF] or slot assignment in [START_REF] Jain | Impact of interference on multi-hop wireless network performance[END_REF]. TRAMA, [START_REF] Rajendran | Energy-efficient, collision-free medium access control for wireless sensor networks[END_REF], schedules node transmissions by assigning time slots to transmitting nodes and receivers. Only nodes having data to send contend for a slot. The node with the highest priority in its neighborhood up to 2-hop wins the right to transmit in the slot considered. Each node declares in advance its next schedule containing the list of its slots and for each slot its receiver(s). The adaptivity of TRAMA to the traffic rate comes at a price: its complexity. DRAND, [START_REF] Rhee | Randomized dining philosophers to TDMA scheduling in wireless sensor networks[END_REF], the coloring algorithm used with the hybrid ZMAC protocol, [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF], that operates like CSMA under low contention and like TDMA otherwise, assigns slots to nodes in such a way that 1-hop and 2-hop neighbors have different slots. This randomized algorithm has the advantage of not depending on the number of nodes but at the cost of an asymptotic convergence.

More recently, coloring algorithms have been designed for WSNs, like FLAMA [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF], an adaptation of TRAMA, where its overhead has been considerably reduced. This is obtained by supporting communications limited to the data gathering tree, like TDMA-ASAP. TDMA-ASAP [START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF] integrates a coloring algorithm with the medium access. Moreover, this protocol can adapt to various traffic conditions by allowing a node to steal an unused slot to its brother in the tree. In WSNs where energy matters, sensors receive consecutive time slots, like [START_REF] Ma | Energy efficient TDMA sleep scheduling in wireless sensor networks[END_REF], to reduce the frequency of state transitions and thus save energy. FlexiTP [START_REF] Lee | FlexiTP: a flexible-schedulebased TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks[END_REF] is a TDMA-based protocol in which a slot is assigned to one transmitter and one receiver. The slot assignment order is given by a deep-first search of the tree. A node selects the smallest available slot in its neighborhood up to 2 hops and advertises its schedule. This solution does not support immediate acknowledgment. In [START_REF] Mahfoudh | Energy efficient routing and node activity scheduling in the OCARI wireless sensor network[END_REF], we proposed SERENA a node coloring algorithm that increases energy efficiency by avoiding collisions, reducing overhearing, allowing nodes to sleep to save energy and enabling spatial reuse of the bandwidth. This algorithm can support various types of communication (unicast with immediate acknowledgement, broadcast). It can also be optimized for data gathering applications by scheduling the children before their parent. Notice that SERENA is a practical distributed protocol that implements an efficient version of the algorithm FirstFit for a 3-hop coloring, with a specific order induced by node priority. In this paper, we give new theoretical results for grid coloring. Finally, we show how SERENA can be optimized.

IV. COMPLEXITY STUDY

In this section, we will demonstrate that h-hop (h ≥ 1) vertex coloring in both general and strategic modes is a NPcomplete problem. This assertion is given by Theorem 1:

Theorem 1: The decision problem of h-hop (h≥1) vertex coloring in both general and strategic modes is NP-complete.

It has been proved in [START_REF] Garey | Computers and intractability: a guide to theory of NP-completeness[END_REF] that the 1-hop vertex coloring problem is NP-complete. We now prove the NP-completeness in both general and strategic modes for h ≥ 1. Our proof of Theorem 1 is based on the following steps:

• First, we define the associated decision problem of the h-hop vertex coloring of a graph G in both general and strategic modes: can graph G be colored with k colors in both general and strategic modes (k is a positive integer smaller than the vertex number), such that two nodes that are l-hop neighbors with 1 ≤ l ≤ h have not the same color? This problem is called k-color h-hop coloring in both general and strategic modes.

• Second, we prove the following lemma:

Lemma 1: The k-color h-hop coloring problem in both general and strategic modes for h ≥ 1 is in NP.

Proof: Given a h-hop coloring of G, h ≥ 1 we can check in polynomial time (O(n h ), where n is the number of nodes) that the coloring produced by a given h-hop algorithm in both general and strategic modes does not assign the same color to two nodes that are p-hop neighbors with 1 ≤ p ≤ h, and that the total number of colors is k.

• Third, we define a reduction f of the k-color 1-hop vertex coloring problem that has been shown NP-complete in [START_REF] Garey | Computers and intractability: a guide to theory of NP-completeness[END_REF], to a k -color h-hop coloring problem in both general and strategic modes, with k a positive integer smaller than the nodes number. This reduction should be polynomial in time. Based on this reduction, we then prove the equivalence:

Equivalence 1: A k -color h-hop vertex coloring problem in both general and strategic modes has a solution if and only if a k-color 1-hop vertex coloring problem has a solution.

In general, to demonstrate that a problem is NP-complete based on another problem that is known to be NP-complete, the required reduction should allow us to show that we can find a solution for the first problem if and only if we can find a solution for the second problem. In our case, we should transform a graph G(V, E) into a graph G = (V , E ) and show that finding a k-color 1-hop coloring of G(V, E) can lead to find a k -color h-hop coloring of G (V , E ) in both general and strategic modes and vice versa, proving Equivalence 1. Finding a valid k -color h-hop coloring of G (V , E ) in both general and strategic modes based on a valid k-color 1-hop coloring of G(V, E) requires that for any two nodes v 1 and v 2 in G, the following constraints are met:

Constraint 2: Any two nodes v 1 and v 2 , 1-hop away in G must be at most h-hop away in G . Thus, these two nodes that are assigned different colors by a 1-hop coloring of G are also assigned different colors by a h-hop coloring of G .

Constraint 3: Similarly, any two nodes v 1 and v 2 , 2-hop away in G must be at least (h + 1)-hop away in G .

Consequently, the reduction separates any two 1-hop neighbors v i and v j of the initial graph G by a set of nodes such that the distance between them in the new graph G is at most h hops. V is obtained from V by adding new nodes. We denote

V = V ∪ V 1 .
The definition of these new nodes depends on h parity. In order to simplify the determination of k , the number of colors used for the h-hop coloring of G , we add to the transformation a new constraint:

Constraint 4: Any two nodes in V 1 must be at most h-hop away. Moreover, any two nodes u ∈ V and v ∈ V 1 must be at most h-hop away. Thus, in a h-hop coloring of G , nodes in V 1 cannot reuse a color already used in V 1 . Similarly, no node in V can reuse a color used by a node in V 1 .

The transformation proceeds as follows, depending on the parity of h: -First case: h is odd: see the example of h = 5 in Figure 3.

• Definition of V In this case, we first define h = (h -1)/2 copies of U , denoted U i and h bijective functions f i , with i ∈ [1, h ]:

f i : V → U i v → f i (v) = u i Now, we can define the set V 1 = ∪ i U i ∪ {u 0 } and V = V ∪ V 1 , ∀i ∈ [1, h ],
where u 0 is a new node introduced to meet constraint C3. Node u 0 is a neighbor of all nodes in U h .

• Definition of E To build the set E , four types of links are introduced. We then have:

E = E 1 ∪ E 2 ∪ E 3 ∪ E 4 where: • E 1 = {(v, u 1 ) such that v ∈ V and u 1 = f 1 (v) ∈ U 1 }.
Thus, each node v from the initial graph G is linked to u 1 , its associated node from the set U 1 (see links of type e 1 in Figure 3).

• E 2 = ∪ l∈[1,h -1] {(u l , u l+1 ) such that u l ∈ U l and u l+1 ∈ U l+1 and f -1 l (u l ) = f -1 l+1 (u l+1 )}. Each node u j from U j is linked to node u j+1 from U j+1 associated with the same node v ∈ V , that is f -1 j+1 (u j+1 ) = v and f -1 j (u j ) = v (see links of type e 2 ). • E 3 = {(u h , v h ) such that u h and v h ∈ U h and (f -1 h (u h ), f -1 h (v h )) ∈ E}.
Two nodes u h and v h from U h are linked to each other if their corresponding nodes in V are linked in E (see links of type e 3 ).

• E 4 = {(u, u 0 ) with u ∈ U h }. Finally, the nodes in U h are linked to the conjunction node u 0 , which was added to meet Constraint 4 (see links of type e 4 ). This construction is polynomial in time. An example of graphs G and G with h = 5 is illustrated in Figure 3. -Second case: h is even: see the example of h = 6 in Figure 4.

To build the graph G when h is even, Constraints 2, 3 and 4 are considered. However, as the number of links to introduce between nodes in the initial graph G depends on the number of nodes to introduce between them, and thus, on h parity, the reduction is slightly modified.

• Definition of V In this case, let h = h/2, we first define h -1 copies of U , denoted U i and h bijective functions

f i with i ∈ [1, h -1]: f i : V → U i v → f i (v) = u i and the bijective function f h : f h : E → U h e → f h (e) = u h We define the set U h . To each couple of nodes (u h -1 , v h -1 ) in V h -1 , we associate a node u h in U h if and only if there is an edge between f -1 h -1 (u h -1 ) and f -1 h -1 (v h -1 ). Now, we can define the set V 1 = {u 0 } ∪ i U i , ∀i ∈ [1, h ],
where u 0 is a node introduced to model the data gathering tree in G .

• Definition of E To build the set E , five types of links are introduced. We then have:

E = E 1 ∪ E 2 ∪ E 3 ∪ E 4 ∪ E 5 where: • E 1 = {(v, u 1 ) such that v ∈ V and u 1 = f 1 (v) ∈ U 1 }.
Thus, each node v from the initial graph G is linked to u 1 , its associated node from the set U 1 (see links of type e 1 in Figure 4).

• E 2 = ∪ l∈[1,h -2] {(u l , u l+1 ) such that u l ∈ U l and u l+1 ∈ U l+1 and f -1 l (u l ) = f -1 l+1 (u l+1 )}.
Each node u j from U j is linked to node u j+1 from U j+1 associated with the same node v ∈ V , (see links of type e 2 ).

• E 3 = {(u h -1 , u h ), (u h , v h -1 ) such that u h -1 and v h -1 ∈ U h -1 and u h ∈ U h with f -1 h (u h ) = (f -1 h -1 (u h -1 , f -1 h -1 (v h -1 ))}. In other words, for each couple of nodes u h -1 and v h -1 in U h -1 , we associate a node u h ∈ U h if and only if (f -1 h -1 (u h -1 ), f -1 h -1 (v h -1 )) ∈ E.
We then link u h with u h -1 and v h -1 (see links of type e 3 ).

• E 4 = {(u i , u j ) such that u i and u j ∈ U h and i = j}.

This means that the nodes in U h form a complete graph (see links of type e 4 ).

• E 5 = {(u i , u 0 )∀ u i ∈ U h }. All nodes in U h are linked
to a node u 0 (see links of type e 5 ). This construction is polynomial in time. The transformed graph G for h = 6 of the initial graph G depicted in Figure 3.a is illustrated in Figure 4. We now show, that the k -color h-hop vertex coloring problem in both general and strategic modes, for any value of h ≥ 1 has a solution if and only if the k-color 1-hop vertex coloring problem has a solution. We define the following Lemma:

Lemma 2: All nodes in G \ G are at most (h -1)-hop neighbors.

Proof: By construction of G . Lemma 3: To perform a h-hop coloring of the graph G , the number of colors taken by nodes in V 1 is equal to m with m is equal to (h • n) + 1 if h is an odd number, and (h -1) • n + p + 1 if h is an even number, where n is the number of nodes in G, p is the number of edges in G.

Proof: From Lemma 2, all nodes in V 1 are at most (h -1)-hop neighbors. Hence, no color can be reused with h-hop coloring (h ≥ 2) of G . By construction of G , the number of these nodes is equal to (h • n) + 1 if h is an odd number, and (h -1) • n + p + 1 if h is an even number.

Lemma 4: Any color used for a node in V by a h-hop coloring of G = (V , E ) cannot be used by any node in V 1 .

Proof: Let us consider any node u ∈ V \V and any node v ∈ V . Let d(v, u) be the number of hops between v and u.

By construction, d(v, u) = d(v, f 1 (v)) + d(f 1 (v), u). From Lemma 2, d(f 1 (v), u) ≤ h -1 and since f 1 (v) is a neighbor of v, we get d(u, v) ≤ h. Hence, u and v must use different colors with h-hop coloring of G for h ≥ 1.
To complete the proof of Theorem 1, we now prove the following Lemma:

Lemma 5: G(V, E) has a one-hop coloring with k colors if and only if G (V , E ) has a h-hop coloring in general mode with k colors, with h ≥ 2.

Proof: Given a one-hop coloring of G with k colors, we want to show that there exists a h-hop coloring of G with k colors as follows. According to Lemma 3, this h-hop coloring will use k colors for nodes in V and m colors for nodes in V \ V with m is equal to (h • n) + 1 if h is an odd number, and (h -1)•n+p+1 if h is an even number. From Lemma 4, colors used in V cannot be reused in V \ V . It follows that there exists a h-hop coloring of G with exactly k = k + m colors. Now, let us assume that we have a h-hop coloring of G with k colors and we want to show that we can find a onehop coloring of G with k colors. From Lemma 3, m colors are needed for h-hop coloring of nodes in V \V . From Lemma 4, colors used in V cannot be reused in V \ V . Hence, k -m colors are used to color the nodes in V . Moreover, since any two nodes v 1 and v 2 in V that are one-hop neighbors in G are h-hop neighbors in G , by construction of G , we deduce that no two one-hop neighbors in G use the same color. Hence, we can find a valid one-hop coloring of G with k = k -m colors.

Lemma 6: G(V, E) has a one-hop coloring with k colors if and only if G (V , E ) has a h-hop coloring in strategic mode with k colors, with h ≥ 1.

Proof: Given a one-hop coloring of G with k colors, we want to show that there exists a h-hop coloring of G with k colors in strategic mode such that Constraint1 is met, as follows. We start by building a tree T rooted at node u 0 from the graph G . Nodes from V are the leaves of this tree (see Figure 5). In the case h is odd, any node v in V has as parent f 1 (v). Any node v l in U l with l a positive integer such that 1 ≤ l ≤ h -1 has as parent the associated node from the level U l+1 . Any node in U h has as parent the root u 0 . In the case h is even, T has as root the node u 0 , any node v in V has as parent f 1 (v), and any node in U l with l a positive integer such that 1 ≤ l ≤ h -2 has as parent the associated node in U l+1 . Finally, we link the nodes in U h -1 to the tree. With any node v i ∈ U h (1 ≤ i ≤ p where p is the number of edges in G) linking two nodes u i and u j in U h -1 we associate as its child a node from the couple (u i , u j ), such that this node has not yet a parent. To color T , we start by coloring the node u 0 the root of the tree. Then, we color nodes level by level, to finally reach the original nodes. From Lemma 2 and Lemma 4, nodes in each level do not reuse colors from lower levels. Hence, each child has a color strictly higher than the color of its parent.

Figure 5 depicts the tree built from graph G for h = 5 and h = 6, where only tree links are represented.

V. THEORETICAL RESULTS IN GRID TOPOLOGIES

Because of the NP-completeness of h-hop coloring in both general and strategic modes, proved in Section IV, we focus on coloring algorithms based on heuristics. To compare different heuristics and select the best one, we use the optimal number of colors. The aim of this section is to determine this optimal number of colors for various topologies representative of wireless networks. We start with regular topologies such as grids that constitute large or dense wireless networks. In a further work, we will extend our results to random topologies and study how to efficiently color a wireless network with a random dense topology by mapping it into a grid. For space reasons, we only consider h-hop coloring in general mode.

The goal of this section is to determine the optimal color number for the 3-hop coloring of grids with various transmission ranges. In all the grids considered, we assume a transmission range higher than or equal to the grid step in order to get the radio connectivity. For simplicity reasons, the transmission range R is expressed as a function of the grid step, that is considered as the unit. Hence, R ≥ 1. Moreover, we assume an ideal environment where any node u is able to communicate via a symmetric link to any node v such that d(u, v) ≤ R, where d(u, v) denotes the euclidian distance from u to v.

In this paper, we only study grid colorings that reproduce periodically a color pattern. As a consequence, the optimality of a coloring obtained is only true in the class of periodic colorings. We adopt the following notation and definitions: Definition 7: A basic color pattern is the smallest color pattern that can be used to periodically tile the whole grid.

Definition 8: A basic color pattern is said optimal if and only if it generates an optimal periodic coloring of the grid.

A. Properties independent of the transmission range

We can now give properties that do not depend on the transmission range value.

Property 1: Any color permutation of an optimal basic pattern is still valid and optimal.

Proof: With the color permutation, no two nodes that are 1-hop, 2-hop or 3-hop neighbors have the same color. Hence, the permuted coloring obtained is still valid. The permutation keeps unchanged the number of colors. Hence the coloring is still optimal.

Property 2: Given an optimal color pattern of any grid and the color at node of coordinates (0,0), we can build a 3-hop coloring of a grid topology based on this pattern such that the color of node (0, 0) is the given color.

Proof: The coloring of the grid is obtained by setting the optimal color pattern in such a way that the color of node (0, 0) is the given color. The pattern is then reproduced to tile the whole topology.

Property 3: Knowing an optimal color pattern of its grid and the color at node of coordinates (0, 0), each node can locally determine its own color based on its coordinates (x, y). The 3-hop coloring obtained for the grid is optimal in terms of colors and rounds.

Proof: The 3-hop coloring obtained for the grid only requires each node to know the color of node (0, 0), its coordinates in the grid and the optimal pattern to apply. Hence, it is optimal in terms of colors and rounds.

B. Optimal coloring for

R = 1, R = 1.5 and R = 2
We now determine the optimal periodic coloring of grids for various transmission ranges. The proofs of the following theorems can be found in [START_REF] Amdouni | Node coloring for dense wireless sensor networks[END_REF].

Theorem 2: The optimal 3-hop coloring of a grid topology with a transmission range R = 1 requires exactly 8 colors, as shown in Figure 6a. An optimal basic color pattern is given in Figure 6b. Proof: Let u be any non-border node of the grid. Let N (u) denote the set of nodes that cannot have the same color as u. The proof is done in four steps:

1) First step: At least 8 colors are needed to color node u and N (u).

2) Second step: We build a valid coloring of u and N (u) with 8 colors, as depicted in Figure 6a. 3) Third step: This coloring can be regularly reproduced to constitute a valid coloring of the grid. 4) Fourth step: A basic color pattern containing exactly eight colors can be extracted (see Figure 6b).

Theorem 3: An optimal coloring of a grid with a transmission range R = 1.5 needs exactly 16 colors, as shown in Figure 7a. An optimal basic color pattern is given in Figure 7b. Theorem 4: An optimal coloring of a grid with a transmission range R = 2 needs exactly 25 colors, as shown in Figure 8a. An optimal basic color pattern is given in Figure 8b.

VI. SERENA: A THREE-HOP NODE COLORING

ALGORITHM

We now focus on wireless ad hoc and sensor networks, where the algorithm complexity must be kept small. Because of the NP-completeness of h-hop coloring, heuristics are used to color network nodes. SERENA is a distributed 3-hop node coloring based on an heuristic: the nodes with the highest priority are colored first. Results in Section V giving the optimal number of colors allow us to compare different node priority assignments and to select the best one for SERENA: the one giving a number of colors close to the optimal.

A. Basic principles of 3-hop node coloring

As previously said, 3-hop node coloring is necessary to support unicast transmissions with immediate acknowledgement in case of general communications, where any node is likely to exchange information with any neighbor node. In SERENA, any node u proceeds as follows to color itself:

1) Node u characterizes the set N (u) of nodes that cannot have the same color as itself. This set depends on the type of:

• communications supported: unicast and/or broadcast;

• application: general where any node is likely to exchange information with any neighbor node or on the contrary tree type where a node exchanges information only with its parent and its children in the data gathering tree; • acknowledgement for unicast transmissions: immediate or deferred. In our case, the set N (u) is the set of neighbors up to 3-hop.

2) Node u computes its priority. Different priority assignments will be tested in the next subsection. 3) Node u applies the two following rules:

• Rule R1: Node u colors itself if and only if it has a priority strictly higher than any uncolored node in N (u). • Rule R2: To color itself, node u takes the smallest color unused in N (u). In SERENA, each node sends its Color message to its 1-hop neighbors. This message contains the information related to the priority and color of the node itself and of its 1-hop and 2-hop neighbors.

B. Performance evaluation in grid topologies

Performance of SERENA is evaluated by the number of colors and the number of rounds needed to color all network nodes. The optimal number of colors is given for comparison. Table I reports the results obtained by SERENA for different grids and different transmission ranges. The number of nodes ranges from 100 to 900. The density is computed as the average number of neighbors per node (i.e. average number of nodes in radio range of a sender). It varies from 3 to 25. P rio1 means that there is only one criterion used for node priority assignment: either the position of the node in the grid line, or a random number. These choices are justified by the node address assignment: addresses are assigned either consecutively according to grid lines or randomly. P rio2 means that two criteria are used: first the number of nodes up to 2-hop and second either the position of the node in the grid line or a random number. Notice that identical results have been obtained when considering the column instead of the line in the grid. Results are averaged over 10 simulation runs. We can draw two conclusions from the results obtained: a) The number of colors strongly depends on the density of nodes and weakly on the number of nodes. The number of rounds strongly depends on the number of nodes and weakly on the density. For instance, for a radio range=1, we get 58 rounds for a 10x10 grid with 100 nodes and 178 rounds for a 30x30 grid with 900 nodes. b) The optimal number of colors is obtained by SERENA for P rio2 + line as well as P rio1 + line for transmission ranges R = 1 and R = 1.5. c) The coloring method that colors the whole grid in a single round by repeating the basic color pattern (see Property 3) uses exactly the same number of colors whatever the grid size. However, in small topologies where the number of nodes is too small to enable the repetition of the basic color pattern in the four directions, SERENA with P rio2 + random is able to obtain a number of colors smaller than this method. This is explained by the fact that a color can be reused earlier: a conflicting node does not exist. This phenomenon can be observed in the simulation results for a grid size 10x10, for R = 2.5 or 3. d) The number of colors as well as the number of rounds depend on the priority assignment. Another address assignment produces another coloring. The average number of colors reaches 15.4 for a 30x30 grid for the random priority assignment while it is 8 when the priority is given by the position of the node in the line. Why do not we have the same number of colors? The reason is given by the node priority assignment. A pure random assignment P rio1+random gives the worst results, except in configurations described in c). The line assignment gives better results than the random one, suggesting that regularity of the topology must be taken into account. P rio2 outperforms P rio1 in 12 cases out of 15 both in terms of colors and rounds, suggesting that nodes from the center, having the highest number of constraints must be colored first, as found in [START_REF] Hansen | Distributed largestfirst algorithm for graph coloring[END_REF] for 1-hop coloring. Such nodes will then enforce their colors on the border nodes.

VII. CONCLUSION

In this paper we have proved that the h-hop node coloring problem in both general and strategic modes is NP-complete, for any integer h > 0. We have then focused on specific cases of large or dense wireless networks: grids with a radio range higher than the grid step. We have determined an optimal periodic 3-hop coloring of grids with various transmission ranges. We have then compared the results obtained by SERENA, a distributed 3-hop coloring algorithm for different node priority assignments. The priority assignment equal to the number of neighbors up to 2-hop, where ties are broken by addresses assigned by grid line, gives the optimal number of colors for a transmission range of 1 or 1.5. It also outperforms random priority assignments in 12 cases over the 15 cases tested. As a further work, we will optimize SERENA to take into account these results. We will also study how to map a grid on a given random topology and determine the best grid adapted to this topology.

Fig. 1 .

 1 Fig. 1. Example of 1-hop and 2-hop nodes of u.

Fig. 2 .

 2 Nodes having a color different from u: (a) 1-hop coloring R = 6; (b) 2-hop coloring R = 3 and (c) 3-hop coloring R = 2.

Fig. 3 .

 3 Example of: (a) Graph G; (b) Transformed graph G for h = 5.

Fig. 4 .

 4 Fig. 4. Transformed graph G of G for h = 6.

Fig. 5 .

 5 Fig. 5. Tree built from G : (a) h=5; (b) h=6.

Fig. 6 .

 6 Fig. 6. R=1 a) 3-hop coloring, b) Basic color pattern with 8 colors.

Fig. 7 .

 7 Fig. 7. R=1.5 a) 3-hop coloring, b) Basic color pattern with 16 colors.

Fig. 8 .

 8 Fig. 8. R=2 a) 3-hop coloring, b) Basic color pattern with 25 colors.

TABLE I NUMBER

 I OF COLORS AND ROUNDS OBTAINED BY SERENA FOR VARIOUS GRIDS AND TRANSMISSION RANGES.

	Radio	Grid	Dens. Optim		Prio1		Prio2
	range	size			line	random	line	random
	1	10x10	3.6	8C	8C	13.8C	8C	11.8C
					58R	67.4R	54R	77.8R
		20x20	3.8	8C	8C	15.4C	8C	14.8C
					118R	82.4R	114R	110R
		30x30	3.87	8C	8C	15.4C	8C	15.4C
					178R	93R	174R	116.6R
	1.5	10x10	6.84	16C	16C	23.6C	16C	19.4C
					67R	94.8R	65R	107.6R
		20x20	7.41	16C	16C	27.6C	16C	26.6C
					137R	144.6R	134R	166.6R
		30x30	7.6	16C	16C	28.4C	16C	27.8C
					207R	169.2R	204R	195.4R
	2	10x10	10.04	25C	30C	33.8C	30C	28.2C
					85R	136.4R	123R	121.8R
		20x20	11.01	25C	33C	41.8C	33C	36.4C
					175R	236.6R	174R	282.4R
		30x30	11.34	25C	33C	44.4C	34C	42.8C
					265R	278R	264R	376.6R
	2.5	10x10	15.8	45C	52C	50.8C	49C	42.33C
					94R	176.8R	105R 146.17R
		20x20	17.85	45C	54C	66.8C	54C	64.8C
					194R	348.2R	197R	359.8R
		30x30	18.56	45C	55C	74C	58C	73.6C
					294R	422.2R	297R	440.8R
	3	10x10	21.16	68C	70C	68C	71C	67.6C
					112R	193R	116R	197.8R
		20x20	24.49	68C	80C	93.4C	79C	93C
					232R	449.4R	231R	451.4R
		30x30	25.64	68C	83C	107.8C	81C	107.8C
					352R	601.2R	351R	601.4R