Ichrak Amdouni

Cedric Adjih

Pascale Minet

Keywords: Graph coloring, wireless sensor networks, grid, periodic coloring, Vector-based Method, valid coloring, optimal coloring, number of colors bounds

Graph coloring is used in wireless networks to optimize network resources: bandwidth and energy. Nodes access the medium according to their color. It is the responsibility of the coloring algorithm to ensure that interfering nodes do not have the same color. In this research report, we focus on wireless sensor networks with grid topologies. How does a coloring algorithm take advantage of the regularity of grid topology to provide an optimal periodic coloring, that is a coloring with the minimum number of colors? We propose the Vector-Based Coloring Method, denoted VCM, a new method that is able to provide an optimal periodic coloring for any radio transmission range and for any h-hop coloring, h ≥ 1. This method consists in determining at which grid nodes a color can be reproduced without creating interferences between these nodes while minimizing the number of colors used. We compare the number of colors provided by VCM with the number of colors obtained by a distributed coloring algorithm with line and column priority assignments. We also provide bounds on the number of colors of optimal general colorings of the infinite grid, and show that periodic colorings (and thus VCM) are asymptotically optimal. Finally, we discuss the applicability of this method to a real wireless network.

Coloriage des réseaux de capteurs en grille: La méthode de coloriage basée sur les vecteurs

Résumé : Le coloriage des graphes est utilisé dans les réseaux sans fil afin d'optimiser les ressources du réseau: la bande passante et l'énergie. Les noeuds du réseau accèdent au médium en fonction de leur couleur. L'algorithme de coloriage a la charge d'assurer que les noeuds intereférents n'aient pas la même couleur. Dans ce rapport de recherche, nous nous concentrons sur les réseaux de capteurs sans fil ayant une topologie en grille. Comment un algorithme de coloriage peut profiter de la régularité de cette topologie pour réaliser un coloriage périodique optimal, c'est à dire un coloriage avec le nombre minimal de couleurs? Nous proposons la Méthode des Vecteurs, notée VCM, une nouvelle méthode qui est capable de fournir un coloriage à h sauts, périodique et optimal quelque soit h ≥ 1 et quelque soit la portée radio. Cette méthode consiste à déterminer quels noeuds de la grille peuvent utiliser la même couleur sans créer des interférences entre ces noeuds tout en minimisant le nombre de couleurs utilisées. Nous comparons le nombre de couleurs utilisées par la Méthode des Vecteurs, à celui obtenu par un algorithme distribué qui affecte les couleurs selon la priorité donnée par la ligne ou la colonne. Nous fournissons aussi des bornes sur le nombre de couleurs des coloriages généraux optimaux de la grille, et prouvons que les coloriages périodiques (et donc VCM) sont asymptotiquement optimaux. Enfin, nous discutons l'applicabilité de cette méthode à un réseau sans fil réel.

Mots-clés : Coloriage des graphes, réseaux de capteurs sans fil, grilles, coloriage périodique, Méthode des Vecteurs, coloriage valide, coloriage optimal, bornes sur le nombre de couleurs.

Context and motivation

Node coloring consists in assigning colors to nodes using a minimum number of colors such that two interfering nodes do not have the same color. It has been proved that the 1-hop coloring problem in [START_REF] Garey | Computers and intractability: a guide to theory of NP-completeness[END_REF] and more generally the h-hop node coloring problem with h an integer ≥ 1 is NP-complete [START_REF] Mccormick | Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem[END_REF][START_REF] Amdouni | Node coloring for dense wireless sensor networks INRIA Research Report[END_REF]. That is why, approximation algorithms are adopted. Among them, FirstFit [START_REF] Cargiannis | A tight bound for online coloring of disk graphs[END_REF] assigns to the uncolored node with the highest priority the first available color. Unfortunately, the number of colors obtained depends on the node coloring order given by the priority. A whole class of results expresses properties related to the worst-case performance of approximation algorithms: they typically prove that, for any input graph of a given family, the coloring obtained by a given algorithm uses at most α times the optimal number of colors. Such an algorithm is denoted an α-approximation algorithm. Many coloring algorithms have been designed to be used in wireless networks to make the medium access more efficient. Among them, we can cite TRAMA [START_REF] Rajendran | Energy-efficient, collision-free medium access control for wireless sensor networks[END_REF], FLAMA [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF], ZMAC [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF] which is based on the DRAND [START_REF] Rhee | Randomized dining philosophers to TDMA scheduling in wireless sensor networks[END_REF] coloring algorithm, TDMA-ASAP [START_REF] Gobriel | TDMA-ASAP: sensor network TDMA scheduling with adaptive slot stealing and parallelism[END_REF], FlexiTP [START_REF] Lee | FlexiTP: a flexible-schedule-based TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks[END_REF] and SERENA [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF]. In short, time slots are assigned per node color: two nodes with the same color can transmit in the same time slot without interfering.

In this research report, we focus on wireless sensor networks with grid topologies. These topologies are regular. Wireless sensors organized according to a grid topology are a natural choice and exist in many real applications. Often, the grid organization is easy to deploy, and is efficient in terms of coverage, connectivity and management. For instance, a grid topology is one of the best methods to ensure sensor coverage for surveillance [START_REF] Baumgartner | Hallway Monitoring: Distributed Data Processing with Wireless Sensor Networks[END_REF][START_REF] Chakrabarty | Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks[END_REF]. It also helps to collect measurements with a uniform spatial sampling such as for instance in precision agriculture and irrigation as in [START_REF] Mcculloch | Wireless sensor network deployment for water use efficiency in irrigation[END_REF]: when physical phenomena are numerically modeled, measurements from a grid pattern may be a direct input or directly compared to the output of equations solved with the finite element method on a grid -without requiring additional sensor localization and numerical measurement interpolation. Given such grid topologies, the question (and our problem statement), is: what is the method to color grids while maximizing the color reuse? Naturally, a first step towards answering the question, is to apply existing algorithms to a sample of grids and analyze the output for some sample topologies. We have performed simulations of a 3-hop coloring, because 3-hop coloring is needed when broadcast and immediate acknowledgement of unicast transmission are required. The algorithm colors nodes according to their priority order among their neighbors up to 3-hop. Node priority is given by one of the following heuristics: the position of the node in the line, column, diagonal, its distance to the grid center or random. Results are summarized in table 1. The '*' symbol highlights the optimality of the number of colors used. The reader can refer to [START_REF] Amdouni | Node coloring for dense wireless sensor networks INRIA Research Report[END_REF] for the proof of the optimal number of colors needed to color some grids with various transmission ranges. Different radio ranges are simulated. Mostly, we observe that no priority assignment tested provides the optimal number of colors for any grid size and any radio range. This prompts the following questions: Does a priority assignment exist in grid topologies such that the number of colors does not depend on node number but only on radio range? Is it possible to take advantage of the regularity of grid to design a h-hop coloring algorithm able to find the optimal number of colors for any grid with any transmission range value? Moreover, does a periodic color pattern that can tile the whole topology for a given radio range, exist? What is the optimal number of colors? Is the optimal number of color reached by periodic colorings?

In this research report, we answer these questions by proposing a coloring method, the Vector-Based Coloring Method, denoted VCM which provides an optimal and valid coloring of grids.

The research report is organized as follows. In Section 2, we introduce some definitions and notations. We present the problem statement and give an intuitive idea of VCM and introduce its main components. In Section 3, we focus on periodic coloring. In Section 4, we consider periodic colorings where any color is periodically reproduced, and show how VCM computes the color of an node in the grid. In Section 5, we restrict or study of periodic coloring to valid ones. We propose two methods to check the validity of periodic coloring. Section 6 allows us to characterize an optimal coloring and give upper and lower bounds on the number of colors, and shows that periodic colorings (and therefore VCM) are asymptotically optimal when the radio range increases1 . We then show how to reduce the research space of the generator vectors produced by VCM in order to reduce the complexity of VCM that we evaluate (which is polynomial time). We conclude this section by giving the method to find the optimal valid generator vectors. In Section 7, we summarize by giving rules to apply VCM in practice. Results obtained by VCM are given in Section 8 and compared with those obtained by different heuristics. Finally, in Section 9, we discuss how to apply VCM in real wireless sensor networks. We conclude in Section 10. In the Annex, the reader will find some mathematical results and grid properties useful for grid coloring.

Problem Statement and Overview

Notations, Definitions and Assumptions

In the remaining of this research report, we use the following notations:

• U V denotes a vector of extremities the nodes U and V .

• | U V | denotes the norm, or length of the vector U V , and d(U, V ) the euclidian distance between nodes U and V .

•

det( U V 1 , U V 2 )
is the determinant of the two vectors.

• U V 1 • U V 2 denotes the scalar product of the vectors.

• Λ( U V 1 , U V 2 ) denotes the lattice having as a base the vectors

( U V 1 , U V 2 ).
We call U V 1 and U V 2 the basis (or generator) vectors.

P( U V 1 , U V 2 )
is the fundamental parallelotope associated to Λ. In 2 dimensions, P is a parallelogram. Moreover, the number of nodes in

P( U V 1 , U V 2 ) called lattice determinant is given by det( U V 1 , U V 2 )
. These notations and definitions are adopted from [START_REF] Wübben | Lattice Reduction, A survey with applications in wireless communications[END_REF]. We also denote P U ( U V 1 , U V 2 ) the fundamental parallelotope translated at node U .

• For x, y in Z 2 , with y = 0, we denote "x modulo y" the integer z in {0, 1, . . . |y| -1} such that we have x ≡ z(mod|y|).

Moreover, the following definitions and assumptions are used:

• Nodes: The nodes are disposed in a grid. Without loss of generality, we assume that the grid step is 1, hence the set of nodes is identified by Z 2 .

• Neighborhood: R denotes the radio range and is a real number ≥ 1.

The underlying assumption is a unit disk model, assuming that nodes U and V can communicate if their euclidian distance is lower than R and are able to communicate directly in both directions. Hence, the set of neighbors of a node U is:

N (U ) = V ∈ Z 2 | 0 < d(U, V ) ≤ R .
• Coloring: A coloring φ is a mapping from the nodes Z 2 to a set of colors, identified with the set of integers {0, . . . k -1}, with k a positive integer.

• Valid Coloring: a coloring is said to be a valid h-hop coloring, with h an integer ≥ 1, when all nodes that are less or equal to h-hop away are assigned different colors.

• Periodic Coloring: A coloring is denoted "periodic" if the set of nodes with the same given color, is the lattice Λ(v 1 , v 2 ) for some fixed vectors v 1 , v 2 of Z 2 , after it is translated by some amount. In this paper, we consider a "strict" definition of periodicity because colors might otherwise be periodically repeated with a pattern generating more than a single lattice for instance.

Problem Statement

Our general goal is the following: Find a valid h-hop coloring of the nodes of the infinite grid Z 2 , with a minimal number of colors for h ≥ 1.

Because the set of colorings of Z 2 is infinite, in this paper we restrict ourselves to colorings exhibiting a periodic color pattern (following the definition of periodic coloring of section 2.1).

Problem Statement: Find one of the valid periodic h-hop colorings with the minimum number of colors for h ≥ 1.

Overview

In this paper, we propose the periodic Vector-Based Coloring Method, denoted VCM that answers the problem statement in polynomial time. This method consists in producing a periodic coloring obtained by tiling a color pattern. This color pattern is generated by two vectors verifying some conditions that will be detailed in the paper.

As illustrated in Figure 1, VCM is composed of the following components:

! " # $% $% Figure 1: Components of VCM RR n°7756
C1. VCM-NCC A periodic coloring based on two generator vectors. This component determines how any sensor node selects its color. C2. VCM-VC An algorithm to check the validity of the periodic coloring: the VCM incorporates two methods to verify the validity of the coloring for a given couple of generator vectors. C3. VCM-OVS An algorithm to search for optimal generator vectors, that is, yielding the minimum number of colors. Indeed, we limit the set of candidate vectors to find the vectors providing the optimal number of colors.

Intuitive Idea

The intuitive idea of the method is as follows. As the grid topology presents a regularity in terms of node position, VCM produces a similar regularity in terms of colors and generates a color pattern that can be periodically reproduced to color the whole grid. Our aim is to find such a color pattern that minimizes the number of colors used. More precisely, given a colored node U , we determine where its color can be reproduced. The method starts by the choice of two vectors U V 1 and U V 2 such that V 1 and V 2 use the same color as U . Of course, the vectors U V 1 , U V 2 must provide a valid h-hop coloring. The color pattern is given by the set of colors in the finite parallelogram P( U V 1 , U V 2 ) translated at U . Hence, the color of U is repeated also at any node W where U W is a linear combination of U V 1 and U V 2 . In the Sections from 4 to 6, we detail the components of VCM. P1. (Generator vectors) The two vectors U V 1 and U V 2 , if linearly independent, generate the parallelogram P( U V 1 , U V 2 ) of the color pattern. P2. (Parallelotope color unicity) Inside P( U V 1 , U V 2 ), there is no color reuse. P3. (Lattice color repetition) Because the periodic coloring is obtained by repeating the color pattern, the nodes W such that U W is a linear combination of U V 1 and U V 2 have the same color as U . Precisely, the set of nodes W having the same color as U forms a lattice of Z 2 with generator vectors U V 1 and U V 2 : the vector U W can be written as

Periodic Coloring

U W = α U V 1 + β U V 2 with α and β in Z 2 .

P4. (Coordinate-based color computation)

The grid can be seen as a tiling with the pattern P U ( U V 1 , U V 2 ). Thus, each node W belongs to its own parallelogram, and has coordinates relative to this parallelogram. Consequently, W has the same color as any node having the same coordinates in its own parallelogram.

To be applied to a wireless sensor network, these principles have to be enhanced. For instance, since nodes having the same color can simultaneously access the wireless medium, validity of the coloring must be verified. Moreover, to ensure an efficient usage of the bandwidth, the number of colors used should be minimized. These criteria are taken into account in our work and progressively introduced in the paper.

In the following we detail the components of VCM. As previously said, we only consider grid colorings that periodically reproduce a color pattern.

VCM: Node Color Computation (NCC)

Assigning Colors to Nodes

The node color computation (NCC) component of the VCM method takes as parameters two generator vectors u 1 ,u 2 (computed as in Section 6). Let (x 1 , y 1 ) and (x 2 , y 2 ) be their coordinates and let d = det(u 1 , u 2 ). Here we define two methods to compute the colors. Actual computation on an example is provided in Section 4.3.

Method NCC1

Method VCM-NCC 1: VCM assigns the color of a point W based on its coordinates w = (x, y) by computing first the integer quantities c 1 (w), c 2 (w) as in System (1),

c 1 (w) = (xy 2 -yx 2 ) modulo d c 2 (w) = (-xy 1 + yx 1 ) modulo d (1)
and then using a bijective mapping between the couple (c 1 , c 2 ) and a color ∈ {0, 1, 2, . . . |d| -1}.

Remark 1 Defining c 2 as c 2 (w) (xy 1yx 1 ) modulo d, instead of the definition in ( 1), would be more symmetrical compared to c 1 , and would yield identical results (as it is a trivial transformation: c 2 (w) → (-c 2 (w)) modulo d).

RR n°7756

Remark 2 In the remaining of this report, we will assume that d > 0 without loss of generality: indeed, if d < 0, it is sufficient to use the vectors (-u 1 , u 2 ) instead of (u 1 , u 2 ) and the results are similar ; notice that c 1 (w, u 1 , u 2 ) = c 1 (-w, -u 1 , u 2 ), etc. (hence change of sign of u 1 is equivalent to an origin symmetry of the coloring). This avoids minor technicalities on the definition of the modulo, integer part, fractional part, when numbers are negative (for which definitions are not universal).

Property 1 With the previous coloring VCM-NCC1, it is indeed possible to define a bijection from (c 1 (w), c 2 (w)) to {0, 1, 2, . . . |d| -1}. Moreover, the coloring verifies principles P3 and P4 defined in Section 3.

Proof: We assume that d > 0 without loss of generality (see Remark 2). We need to prove that the set (c 1 (w), c 2 (w)) | w ∈ Z 2 has cardinality d and that the set of nodes with the same color is exactly the lattice Λ(u 1 , u 2 ) translated at w. Let W be a grid point of coordinates w = (x, y). Performing a change of vector basis in

R 2 from {(1, 0), (0, 1)} to {u 1 , u 2 }, the new coordinates (α, β) ∈ R 2 of W in Λ(u 1 , u 2 ) verify w = αu 1 + βu 2 and      α = det(w, u 2 ) d β = det(u 1 , w) d (2)
with d = det(u 1 , u 2 ).
Let α ′ and β ′ be the integer parts of α, β, i.e., α ′ = ⌊α⌋ and β ′ = ⌊β⌋. For arbitrary nonzero integers λ, µ, with also µ > 0, we have the identity:

λ µ = ⌊ λ µ ⌋ + λ modulo µ µ
. Thus 2 becomes:

     α = α ′ + det(w, u 2 ) modulo d d = α ′ + c 1 (w) d β = β ′ + det(u 1 , w) modulo d d = β ′ + c 2 (w) d (3)
Let W ′ the point with coordinates w ′ = (α ′ , β ′ ). W ′ is on the lattice since α ′ , β ′ are integers, and observe that W is in fact inside the parallelogram of the lattice Λ(u 1 , u 2 ) placed at node W ′ (i.e. inside the parallelogram defined by the 4 points of the lattice:

w ′ , w ′ +u 1 , w ′ +u 2 , w ′ +u 1 +u 2 ). Then (3) means simply that ( c1(w) d , c2(w) d
) are the coordinates of W relative to this parallelogram (with the basis vectors u 1 , u 2 ).

Since there is a bijection between the set of coordinates of nodes in a parallelogram of Λ(u 1 , u 2 ) and the nodes themselves; and since ( c1(w) d , c2(w) d ) are these coordinates, we have the two properties: 1) there are exactly d possible values of (c 1 , c 2 ) (because there are exactly d nodes in the parallelogram), and 2) no two nodes inside the parallelogram have the same values c1, c2 since these are their coordinates, relative to one vertex of the parallelogram.

Lemma 1 With the color computation given by the System 1, the color of the node U is repeated at the nodes W with coordinates verifying: w = αu 1 + βu 2 , for some (α, β) ∈ Z 2 . Proof: Actually, by construction, the color of a node is given by its coordinates relative to the parallelogram it belongs to. Hence, the color of any node U is reused at nodes W , such that U W = αu 1 + βu 2 for all (α, β) ∈ Z 2 , which have the same relative coordinates. We deduce that VCM-CC1 provides a coloring that is really consistent with the principle of the method as described in Section 3.

Example of bijection for NCC1

One of the steps of the Method NCC 1, is that a bijection needs to be established between the set of values (c 1 (w), c 2 (w)) | w ∈ Z 2 and the set of colors {0, 1, . . . , d -1}: an example of bijection is provided in this section.

A bijection can be constructed by computing the values of (c 1 (w), c 2 (w)) for any node in P(u 1 , u 2 ) in a list, sorting the list by lexicographical order, and, finally, setting the color associated with a couple (c 1 (w), c 2 (w)) to be its index in the sorted list minus 1.

Example: if (0, 0) appears as the 1 st item of the sorted list [as it can be proved it will], the color assigned to that couple is 0. Then, for instance, for the point W of coordinates w = (x 1 , y 1 ), in other terms w = u 1 , we have (c 1 (w), c 2 (w)) = (0, 0) and therefore the color assigned to W is 0.

Note that, from a pure implementation point of view, it may be difficult to enumerate exactly the points of P(u 1 , u 2 ), but then, instead, it is sufficient to enumerate all the nodes in a superset, the bounding box of P(u 1 , u 2 ), itself computed from its four vertices O = (0, 0

), O + u 1 , O + u 2 and O + u 1 + u 2 .
Computing the set of values (c 1 (w), c 2 (w)) for the points in the bounding box, will yield all possible values for any w ∈ Z 2 .

Method NCC2

Method 2 is derived from the first method ; the difference is that it also establishes a direct bijection (and hence avoids the need for constructing a bijection as in section 4.1.2): it proceeds to a direct computation of the color based on the node coordinates without computing the colors of the other nodes on the parallelogram.

As for Method 1, we assume that we are given two generator vectors u 1 , u 2 with coordinates (x 1 , y 1 ) and (x 2 , y 2 ), and that we are computing the color of node of coordinates w = (x, y).

In addition to the notations and definitions used previously, we introduce the following ones:

• g 1 is the greatest common divisor of (x 1 , y 1 ); g 1 = gcd(x 1 , y 1 ). Similarly, g 2 = gcd(x 2 , y 2 ), with the convention gcd(a, 0) = gcd(0, a) = a

• v 1 is the vector = 1 g1 u 1 and v 2 is the vector = 1 g2 u 2 . Notice that the coordinates of v 1 and v 2 are coprimes.

• Let d ′ = det(v 1 , v 2 ). We have: d ′ = d g1g2 • Let (α ′ (w), β ′ (w)) ∈ R 2 be
the coordinates of the node w relative to the basis (v 1 , v 2 ), when performing a change of basis in R 2 from (1, 0), (0, 1)

to (v 1 , v 2 ). We have: α ′ (w) = det(w,v2) d ′ and β ′ (w) = det(v1,w) d ′ . • Let x ′ (w) = ⌊α ′ (w)⌋ modulo g 1 RR n°7756 • Let y ′ (w) = ⌊β ′ (w)⌋ modulo g 2 • Let c ′ (w) = det(w, v 2 ) modulo d ′
Method VCM-NCC 2: Using the notations mentioned above, a color of a node with coordinates w = (x, y) is equal to

c(w) = c ′ (w) + d ′ x ′ (w) + d ′ g 1 y ′ (w) (4)
which is an integer in {0, 1, 2, . . . |d| -1}

As in remark 2, we now assume that d > 0 without loss of generality.

The idea of the method VCM-NCC 2 is as follows:

• In method VCM-NCC 1, we did not identify nor did make use of the special structure of

E c = (c 1 (w), c 2 (w)) | w ∈ Z 2 ,
which is in fact a subgroup of ( Z dZ )2 ; hence we did not provide an explicit mapping from E c to {0, 1, 2, . . . d -1}. This is the problem that method 2 addresses:

• In method VCM-NCC 2, by dividing the vectors u 1 and u 2 by the respective gcd of their coordinates, we obtain vectors v 1 , v 2 , and we find that applying method VCM-NCC 1 with these vectors, the set of val-

ues c 1 (w, v 1 , v 2 ), c 2 (w, v 1 , v 2 ) | w ∈ Z 2
has good properties, allowing the construction of a direct bijection (see lemma 2).

• However using method VCM-NCC 1 with vectors v 1 , v 2 yields a coloring of Z 2 repeated by translation by v 1 and v 2 ; whereas we wanted a coloring repeated by translation by u 1 and u 2 (which are larger). Notice that the problem here is that method VCC-NCC 1 with generator vectors v 1 , v 2 is quite possibly an invalid h-hop coloring of Z 2 , even if u 1 , u 2 are vectors defining a valid h-hop coloring. For this reason, method VCM-NCC 2 constructs a coloring based on method VCM-NCC 1, but modified, by tiling the parallelogram P(v 1 , v 2 ) several times inside the parallelogram P(u 1 , u 2 ) and changing the colors in each internal tile (see figure 3).

Method 2 is in fact the combination of two functions; c(w) = b 3 (c 3 (w)) with:

• The first one, c 3 , from

Z 2 to {0, 1, ..d ′ -1}×{0, 1, ..g 1 -1}×{0, 1, ..g 2 -1}
, which associates to w the value c 3 (w) = (c ′ (w), x ′ (w), y ′ (w)).

• The second is bijection b 3 from {0, 1, . . . d ′ -1}×{0, 1, . . . g 1 -1}×{0, 1, . . . g 2 -1} to {1, 2, . . . d} by transforming (j, k, l) → b 3 (j, k, l) = j + d ′ k + d ′ g 1 l ; note that d = g 1 g 2 d ′ by definition.
The transformation b 3 is obviously a bijection from its domain to its codomain 2 , and therefore the crux of method VCM-NCC 2 is the function c 3 .

We start with the following lemma for the function c ′ (w), which is in fact c 1 (w, v 1 , v 2 ): This lemma establishes that for the specific generator vectors (v 1 , v 2 ), c 1 computes directly a color and c 2 is essentially redundant. Proof: We prove this lemma in two steps: (S1) proves that the set c 1 (w,

v 1 , v 2 ) | w ∈ Z 2
covers exactly integers in {0, 1, . . . d ′ -1} , and (S2) the coloring provided by c 1 has the same properties as V CM -N CC1. To prove this, we prove that there is a bijection between c 1 (w,

v 1 , v 2 ) | w ∈ Z 2 and E c = (c 1 (w, v 1 , v 2 ), c 2 (w, v 1 , v 2 )) | w ∈ Z 2 .
(S1) Consider the vector u 2 . By definition, g 2 is the gcd of its coordinates (x 2 , y 2 ). Applying Bézout's identity ( [START_REF] Jones | Bezout's Identity. 1.2 in Elementary Number Theory[END_REF]), there exist integers 3 (λ, µ) ∈ Z 2 , such that:

λx 2 + µy 2 = g 2 (5)
Let w 0 be the vector of coordinates (µ, -λ) and let

(x ′ 2 , y ′ 2 ) be the coordinates of v 2 (recall that v 2 is defined as v 2 = 1 g2 u 2 ). Because v 2 = 1 g2 u 2 , we have x ′ 2 = x2
g2 and y ′ 2 = y2 g2 and hence equation ( 5) becomes:

λx ′ 2 + µy ′ 2 = 1 =⇒ det(w 0 , v 2 ) = 1 =⇒ c 1 (w 0 , v 1 , v 2 ) = 1
Since c 1 is a linear map: c 1 (2w 0 , v 1 , v 2 ) = 2, etc. and by applying it to 0, w 0 , 2w 0 , . . . (d ′ -1)w 0 , we get exactly:

c 1 (w, v 1 , v 2 ) | w ∈ Z 2 = {0, 1, . . . d ′ -1}
. 3 this is even true when x 2 = 0 or y 2 = 0 with our convention gcd(a, 0) = gcd(0, a) = a RR n°7756

(S2) Let E c be the set E c = (c 1 (w, v 1 , v 2 ), c 2 (w, v 1 , v 2 )) | w ∈ Z 2 .
From properties previously proven for method VCM-NCC 1 (including property 1), we know that there exists a bijection from E c to the set {0, 1, 2, . . . d ′ -1} ; in other words, that its cardinality verifies

|E c | = d ′ .
Now consider the projection p x : (x, y) → x. The previous relation shows that p x (E c ) = {0, 1, . . . d ′ -1} hence it is a bijection because it is surjective between two sets of cardinality d ′ .

Therefore we have explicitly found one bijection (precisely: k, l → p x (k, l)) compared to the method VCM-NCC 1 where we only established the existence of such a bijection. The end result, is that when applying VCM-NCC 1 with the generator vectors (v 1 , v 2 ) and with this bijection p x , the color of a node w is c 1 (w, v 1 , v 2 ). The coloring provided by c 1 inherits from VCM-NCC 1, all the properties listed in Section 3. The next step is to build a coloring repeated by translation of u 1 and u 2 , from the coloring VCM-NCC 1. As illustrated in Figure 3, the idea is that v 1 , v 2 are the basis of the parallelogram P(v 1 , v 2 ) that can be tiled to cover the parallelogram P(u 1 , u 2 ) ; this is possible because u 1 = g 1 v 1 and u 2 = g 2 v 2 (where g 1 and g 2 are integers). Inside a parallelogram P(v 1 , v 2 ), the nodes are assigned the same color as given by VCM-NCC 1 with v 1 , v 2 , except that an offset is added, depending in which tile the node is located.

Concretely, in Figure 3, the parallelogram P u1 (u 1 , u 2 ) at the right side of the picture is tiled with 6 smaller parallelograms which are versions of P(v 1 , v 2 ), filled by different shades of gray. The nodes in one small gray parallelogram are allocated the colors 0, 1, 2 . . . d ′ -1 ; the ones of the next small gray parallelogram are allocated the colors d ′ , d ′ + 1, . . . 2d ′ -1; and generally the nodes of the k th parallelogram are allocated the colors kd ′ , kd ′ + 1, . . . (k + 1)d ′ -1. The actual coloring is then something like the colored nodes at the left of the Figure 3.

Thus, the central idea is to identify in which sub-parallelogram a node is located: this is given by x ′ (w), y ′ (w), which are in fact the coordinates of the smaller parallelogram on the basis (v 1 , v 2 ) counted relative to the larger parallelogram. For instance, in Figure 3, the point w is inside a sub-parallelogram of coordinates (x ′ (w), y ′ (w)) = (1, 2) relative to the bigger parallelogram. This is the informal idea behind the quantities defined previously: in the following lemma, we now prove formally that VCM-NCC 2 is a coloring satisfying the desired properties.

Lemma 3

The coloring provided by the method VCM-NCC 2 satisfies the principles P1, P2, P3 and P4 from Section 3.

Proof:

Almost all the properties can be derived from identifying the set of nodes with identical colors.

Let w 1 and w 2 be two nodes with the same color, hence, with c(w 1 ) = c(w 2 ). Because c = b 3 • c 3 and b 3 is a bijection, this implies that c ′ (w 1 ) = c ′ (w 2 ) and x ′ (w 1 ) = x ′ (w 2 ) and y ′ (w 1 ) = y ′ (w 2 )

The part c ′ (w 1 ) = c ′ (w 2 ) implies that w 1 and w 2 have the same color in the method VCM-NCC 1 applied with vectors v 1 , v 2 , therefore, by properties of this method:

w 1w 2 = λv 1 + µv 2 for some (λ, µ) ∈ Z 2

RR n°7756

Let us decompose λ as quotient and remainder modulo g 1 (resp. µ, modulo g 2 ): λ = g 1 q 1 + r 1 and µ = g 2 q 2 + r 2 where r 1 ∈ {0, 1, . . . g 1 -1}, r 2 ∈ {0, 1, . . . g 2 -1} and (q 1 , q 2 ) ∈ Z 2 .

The previous equality becomes:

w 1 -w 2 = (g 1 q 1 + r 1 )v 1 + (g 2 q 2 + r 2 )v 2 (7)
Now developing the part x ′ (w 1 ) = x ′ (w 2 ) from ( 6), we get:

⌊α ′ (w 1 )⌋ modulo g 1 = ⌊α ′ (w 2 )⌋ modulo g 1 =⇒ ⌊α ′ (w 1 ) -α ′ (w 2 )⌋ modulo g 1 = 0 or ⌊α ′ (w 2 ) -α ′ (w 1 )⌋ modulo g 1 = 0
Which equality is true depends on which one of α ′ (w 1 ) and α ′ (w 2 ) has the largest fractional part. Assume it is α ′ (w 1 ), then we have:

⌊α ′ (w 1 ) -α ′ (w 2 )⌋ modulo g 1 = 0 =⇒ ⌊ det(w1-w2,v2) d ′ ⌋ modulo g 1 = 0 (by definition of α ′ ) =⇒ ⌊(g 1 q 1 + r 1 ) det(v1,v2) d ′
⌋ modulo g 1 = 0 (using eq 7)

=⇒ r 1 = 0 (using the definition of d ′ )

In the same way, developing y ′ (w 1 ) = y ′ (w 2 ) from ( 6), yields r 2 = 0. Since

u 1 = g 1 v 1 , u 2 = g 2 v 2
, we can now rewrite Eq (7) as:

w 1 -w 2 = q 1 u 1 + q 2 u 2 for some (q 1 , q 2 ) ∈ Z 2
The opposite is true: if w 1w 2 verify this equality, w 1 = w 2 + q 1 u 1 + q 2 u 2 , and then one can easily check that c ′ (w 1 ) = c ′ (w 2 ) and similarly:

x ′ (w 1 ) = ⌊α ′ (w 2 + q 1 u 1 + q 2 u 2 )⌋ modulo g 1 = ⌊ det(w 2 + q 1 u 1 + q 2 u 2 , v 2 ) det(v 1 , v 2 ) ⌋ modulo g 1 = ⌊α ′ (w 2 ) + q 1 g 1 ⌋ modulo g 1 = ⌊α ′ (w 2 )⌋ modulo g 1 = x ′ (w 2 )
Likewise y ′ (w 1 ) = y ′ (w 2 ) and thus finally c(w 1 ) = c(w 2 ), that is, the two nodes of coordinates w 1 and w 2 have the same color. As a result, we have established that the nodes with identical colors are exactly the points located on a lattice generated by vectors v 1 , v 2 . This is exactly the principle P3, and actually implies the principles P1, P2 and P4. Remark 3 In this section, we selected c ′ (w) as c ′ (w) = c 1 (w, v 1 , v 2 ). Alternatively, one could select c ′ (w) = c 2 (w, v 1 , v 2 ). Notice also that once the choice is made, lemma 2 does not require that coordinates are coprimes for both vectors v 1 and v 2 . Indeed, for the choice c ′ = c 1 , (respectively c ′ = c 2 ) only v 2 (respectively v 1 ) is required to have coordinates that are coprime.

RR n°7756

Computing the Number of Colors

The number of colors used in a periodic h-hop coloring is given by the next Property.

Property 2 For any node U , the color pattern defined by the two generator vectors u 1 and u 2 meeting the aforementioned principles contains exactly |x 1 y 2x 2 y 1 | colors where (x 1 , y 1 ) and (x 2 , y 2 ) are the coordinates of u 1 and u 2 .

Proof: By definition, no two nodes within the parallelogram defined by u 1 and u 2 use the same color. Hence the number of colors is equal to the number of nodes in this parallelogram. Moreover, as we said, the number of nodes in P(u 1 , u 2 ), called lattice determinant, is equal to the absolute value of det(u 1 , u 2 ) [START_REF] Wübben | Lattice Reduction, A survey with applications in wireless communications[END_REF]. Hence the property.

Example of Color Calculation

In this section, we illustrate the color calculation, using the example of Figure 3.

In Figure 3, we have the following coordinates for u 1 , u 2 , w:

• u 1 = (6, 2) and u 2 = (-3, 6)

• w = (8, 9)

Applying VCM-NCC 1 with the generator vectors u 1 , u 2 , we get:

• Number of colors = 42

• (c 1 (w, u 1 , u 2 ), c 2 (w, u 1 , u 2 )) = (33, 38)

• Using the example bijection of Section 4.1.2, c 1 (w), c 2 (w) is the 36 th value in the sorted list of possible values, hence color(w) = 35

Applying VCM-NCC 2 with the generator vectors u 1 , u 2 , we get:

• Number of colors = 42

• g 1 = gcd(coords of u 1 ) = 2 and then v 1 = (3, 1)

• g 2 = gcd(coords of u 2 ) = 3 and then v 2 = (-1, 2)

• c ′ (w) = 4, x ′ (w) = 1, y ′ (w) = 2 • Color of w: c(w) = 39
For reference, the colors are computed internally from the coordinates w on different basis:

w = (1 + 33 42 )u 1 + 38 42 u 2 and w = (3 + 4 7 )v 1 + (2 + 5 7 )v 2

VCM: Validity Check (VC)

As defined previously, a h-hop coloring algorithm is valid if and only if no two nodes that are at less or equal to h-hop from each other use the same color. The node color computation algorithm of VCM (described in Section 4) takes as input two generator vectors u 1 , and u 2 , and gives the color of each node. In this section, we will assume that such two vectors are given and fixed, and we present two methods for checking beforehand whether the coloring induced by these vectors is a valid coloring.

Method VC1: Verification around Origin

Method VC1: For each node W in the h-hop neighborhood of the origin node O, we compute the color of this node based on the given generator vectors u 1 and u 2 . If W has the same color as O, then we conclude that the vectors u 1 and u 2 do not provide a valid coloring. Otherwise, if the color of O, is not repeated at any point W in its h-hop neighborhood, then the coloring is valid.

The idea of Method 4 is based on the following fact, proven in this section: if there is a color conflict between any two nodes V 1 and V 2 in Λ(u 1 , u 2 ) (V 1 and V 2 have the same color despite they are at less than or equal to h hops), there will be a color conflict in the h-hop neighborhood of the origin O. We set d = det(u 1 , u 2 ).

Lemma 4 If two nodes V 1 and V 2 with coordinates v 1 , v 2 in Z 2 have the same color, then the color of the origin node is repeated at the node W of coordinates v 2v 1 .

Proof: The functions c 1 , c 2 computed from System 1 are actually linear modulo d. That is, if W is the node with coordinates v 1v 2 , and w is the vector of nodes extremities the origin and W , we get:

c 1 (W ) = c 1 (V 1 ) -c 1 (V 2 ) modulo d. Hence, if c 1 (V 1 ) = c 1 (V 2 ) we have c 1 (W ) = c 1 (O)
. This is true also for c 2 , hence the lemma.

Theorem 1 If none of the nodes inside the h-hop neighborhood of the origin node O = (0, 0) has the same color as O itself, then the coloring is valid.

Proof: By contradiction: assume that the coloring is invalid, which implies that two nodes V 1 , V 2 at less or equal to h hops have the same color. Then from Lemma 4, the node W such as OW = V 1 V 2 has the same color as O. Notice that the distance in terms of hop number between O and W is the same as the distance between V 1 and V 2 . Hence we have found a color conflict between O and a node W which is at less than h hops from O. Hence the theorem. Theorem 1 proves that Method VC1 is a correct method for checking whether two generator vectors yield a valid h-hop coloring.

Method VC2: Verification in a Few Points

Method VC1 requires Θ(R 2 ) verifications when R → ∞. In the following, we propose Method VC2, usable when R > √ 2 and requiring only a bounded number of verifications. Method VC2 performs a check on a few nodes on the lattice Λ(u 1 , u 2 ) to guarantee that the h-hop coloring associated to u 1 , u 2 is valid. This method is based on Gauss lattice reduction [START_REF] Vallée | Lattice reduction in two dimensions: analyses under realistic probabilistic models[END_REF] (see the Annex for more details): u 1 and u 2 should be first reduced, and hence verify the Equations [START_REF] Gräf | On coloring unit disk graphs[END_REF]. Method VC2: The nodes with the same color as the origin are on the lattice Λ(u 1 , u 2 ): this method verifies that these nodes are at least (h + 1)-away from O, in which case the coloring is valid. However, not all grid nodes need to be checked. It is sufficient to check only nodes W in Λ(u 1 , u 2 ) with coordinates α, β on the basis {u 1 , u 2 }, such that |α| and |β| < µ(R), with µ

(R) = 2 √ 3R 3(R- √ 2)
. The coloring is valid if and only if these nodes are strictly more than h hops from the origin node.

RR n°7756

This method is based on the following theorem.

Theorem 2 For R > √ 2, the coloring provided by two reduced vectors u 1 , u 2 is valid if and only if: for all α, β integers verifying |α| < µ(R), and |β| < µ(R), the node with coordinates (α, β) on the basis {u 1 , u 2 } is at strictly more than h hops from the origin node O, where µ

(R) = 2 √ 3R 3(R- √ 2)
.

Proof: The property comes from the fact that the points on the lattice Λ(u 1 , u 2 ) are "far" from the origin node, because the vectors u 1 , u 2 are reduced. Indeed, Lemma 9 (see the Annex) means that any node on the lattice with coordinates αu 1 + βu 2 , with |α| or |β| ≥ µ(R) can reuse the color of the origin node O because they are at strictly more that h-hop from O (provided that the points of coordinates u 1 or u 2 are themselves strictly more than h-hop away from O). Hence, to check the validity of the coloring provided by VCM, it is necessary and sufficient to check that for all |α| and |β| < µ(R), nodes of coordinates α, β in the lattice Λ(u 1 , u 2 ) are strictly more than h hops away from the origin of the lattice. This check includes checking the validity of u 1 and u 2 themselves (cases (α, β) = (1, 0) and (α, β) = (0, 1))

Notice that for dense grids (R → ∞), µ → 1.15 . . .. This small bound reduces the set of nodes to be checked in order to verify the validity of the coloring for given vector candidates.

In fact for R > 3

√ 2 3- √ 3
, that is for R > 3.3461, we have µ < 2, hence only 4 points need to be checked (considering symmetries): u 1 (with α = 1, β = 0), u 2 (with α = 0, β = 1), u 1 + u 2 (with α = 1, β = 1), u 1u 2 (with α = 1, β = -1).

However, Method 1 is applicable for any radio range R, whereas Method2 requires (R > √ 2).

VCM: Optimal Vector Search (OVS)

To achieve an optimal spatial reuse, the coloring algorithm should minimize the number of colors used. For VCM, our aim is to judiciously choose the generator vectors u 1 and u 2 in order to reduce the number of colors used to color a grid. However, by default, the infinite lattice Z 2 is a possible set for candidate vectors. So, to find the optimal vectors in a small set, our approach is as the following:

• We determine the upper and lower bounds on the number of colors needed in a h-hop coloring of the grid, for h ≥ 1.

• Because for any couple of initial generator vectors, reduced vectors always exist, it is sufficient to search for some optimal vectors in the space of reduced vectors defined by System [START_REF] Gräf | On coloring unit disk graphs[END_REF].

We will show in Section 6.2 how to bound the set of candidate vectors using the properties of lattice reduction and the upper and lower bounds on the number of colors to decrease the complexity of the search for the optimal vectors.

Bounds on the Number of Colors in Colorings

In this section, we prove that the number of colors of optimal colorings when R → ∞ is shown to be asymptotically

√ 3 2 h 2 R 2 + O(R)
, from the combination of two bounds.

Lower Bound

For the lower bound, we have the following theorem that is valid for any coloring, not just periodic colorings. It uses known results on circle packings.

Theorem 3

The number of colors required to color an infinite grid with R > √ 2 is at least

√ 3 2 h 2 (R - √ 2) 2 .
Proof: Consider h-hop coloring of the grid Z 2 . Consider a fixed color c, and now let S c be the set of nodes having this color. We first establish a lower bound of the distance of nodes in S c . Let us define ρ = (R -√ 2)h. Consider two nodes A, B of S c . By contradiction: if their distance verifies d(A, B) ≤ ρ, from Lemma 6, they would be at most h-hop away, contradicting the definition of a h-hop coloring. Therefore, all nodes of S c are at a distance at least ρ from each other. Now consider the set of circles C of radius 1 2 ρ and whose centers are the nodes of S c . The fact that any two nodes of S c are distant of more ρ, implies that none of the circles in C overlap. Hence C is a circle packing by definition. From the Thue-Tóth theorem [START_REF] Thue | Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene[END_REF][START_REF] Tóth | Über die dichteste Kugellagerung[END_REF] establishing that the hexagonal circle packing is the densest packing, with a density of π √ 12 , we deduce that C must have a lower or equal packing density. This implies an upper bound of the density of set S c of centers of the disks of

1 (ρ/2) 2 √
12 . Because each color yields a set of nodes with at most this density, it follows a lower bound of the number of colors that is the inverse of this quantity, hence the theorem.

Upper Bound

For an upper bound, when R > √ 2 , we construct explicitly a periodic coloring; more precisely we construct two vectors v 1 , v 2 yielding a valid coloring with VCM. As a result, optimal colorings and optimal periodic colorings must have a number of colors which is lower or equal.

Because the vectors constructed yield lattices which are close to hexagonal lattices (when R → ∞), and because it happens that hexagonal lattices yields the densest packing (as used in the proof of theorem 3), the upper bound will be somewhat "close" to the previous lower bound.

We have the following theorem:

Theorem 4 The number of colors required to color an infinite grid is at most

√ 3 2 h 2 R 2 + 2hR + (hR + 2) √ 2.
Proof: We proceed with a constructive proof, exhibiting two valid vectors which yield the result, using an approximation of an hexagonal lattice. Figure 4 illustrates how some points V 1 and V 2 are constructed.

RR n°7756

Figure 4: Selecting vectors for a near-hexagonal lattice

• Starting from the point U , the line with an angle π 3 with the horizontal line is considered, and its intersection with the circle of radius hR yields the point B.

• Next, the closest point of B on the grid having higher coordinates x and y than B is sought and is V 2 with coordinates (x 2 , y 2 ).

• Then V 1 with coordinates (x 1 , y 1 ) is selected with (x 1 , y 1 ) = (2x 2 , 0).

Notice that by construction x 1 ≥ hR, and we have a valid choice of vectors U V 1 and U V 2 .

Denote (γ, δ) the coordinates of BV 2 . By construction: 0 ≤ γ ≤ 1 and

0 ≤ δ ≤ 1, hence: | BV 2 | ≤ √ 2. Moreover, | AV 1 | = 2x 2 -hR = 2(hR cos( π 3 ) + γ) -hR, with γ ≤ 1 ≤ 2
Consequently, we can write n c , the number of colors in the associated coloring as:

nc = det( U V1, U V2) = det( U A, U B) + det( AV1, U B) + det( U V1, BV2) ≤ det( U A, U B) + | AV1|| U B| + | U V1|| BV2| ≤ √ 3 2 h 2 R 2 + 2hR + (hR + 2) √ 2.

RR n°7756

Remark 4 An alternate, simpler, choice of vectors is to compute the integer λ = ⌊hR⌋+1, and select the vectors with coordinates u ′ 1 = (λ, 0) and u ′ 2 = (0, λ). The number of colors is higher than for the near-hexagonal previous vectors (it is

h 2 R 2 (1 + O( 1 R ))
), hence the vectors cannot yield the result of the next section, but the vectors can be used for an upper bound when R ≤ √ 2.

Asymptotic Number of Colors

Theorem 5 The number of colors n c (R) of an optimal periodic h-hop coloring for a fixed h verifies:

n c (R) = √ 3 2 h 2 R 2 (1 + O( 1 R ))
when R → ∞.

Proof: Combining the lower bound and the upper bound of the two theorems 3 and 4 yields the result.

Corollary 1 Theorem 5 is true even considering periodic and non periodic colorings.

Proof: A periodic coloring is a special case of general coloring (including periodic and non periodic). Hence, the optimal number of colors in general coloring is less than or equal to n c .

Corollary 2 VCM is asymptotically optimal even considering all possible valid colorings (even non-periodic). In other terms VCM is an (1+g(R))-approximation of the optimal coloring(s) of the grid with some g verifying g(R) → 0 (precisely:

g(R) = O( 1 R ))
when R → ∞. Proof: VCM will find vectors with better or equal performance than those in Theorem 4. Indeed, in the worst case, these generator vectors for the "nearhexagonal" lattice will be selected by VCM.

Finding Optimal Vectors

The complexity of VCM lies in the generator vectors computation and in their validity check. In this section, we show how to limit the set of candidate vectors. Let u 1 , u 2 be two candidate vectors and θ be the angle between them. We search l 1min , l 1max (respectively l 2min , l 2max ) the lower and upper bounds of the length of u 1 (respectively u 2 ). 1. Considering a h-hop coloring, the vectors u 1 and u 2 must be valid. According to Lemma 6, we have:

|u 1 | > (R - √ 2) h and |u 2 | > (R - √ 2) h. (8)
2. As we said, in order to reduce the set of candidate generator vectors, we reduce the size of these vectors by using the lattice reduction algorithm of Gauss. A consequence of Gauss property 19 is that: |cosθ| ≤ 1 2 , and hence:

| sin θ| ≥ √ 3 2 . ( 9
)
RR n°7756

3. As shown in Theorem 3,

det(u 1 , u 2 ) ≤ S h = √ 3 2 h 2 R 2 + 2hR + (2 + hR) √ 2.
It results: |u 1 ||u 2 || sin θ| ≤ S h . Using 9, we get:

√ 3 2 |u 1 ||u 2 | ≤ |u 1 ||u 2 || sin θ| ≤ S h (10)
And as |u 1 | ≤ |u 2 |, from 10 we have:

√ 3 2 |u 1 | 2 ≤ S h . (11)
We now separate the cases where R > √ 2 and R ≤ √ 2

6.2.1 Case R > √ 2
Using 8, from 11 we get:

√ 3 2 |u 1 |(R - √ 2)h < √ 3 2 |u 1 | 2 ≤ S h . (12)
And using 8 in 10:

√ 3 2 |u 2 |(R - √ 2)h < S h . (13)
To summarize, the two generator vectors should verify for R > √ 2:

l 1min < |u 1 | ≤ l 1max and l 2min < |u 2 | < l 2max (14)
with:

                 l 1min = h(R - √ 2) l 1max = 2 √ 3 S h l 2min = h(R - √ 2) l 2max = 2 √ 3 S h h(R - √ 2) (15)
In practice, to compute the two generator vectors, we determine the upper and the lower bounds of the coordinates of u 1 , and u 2 using the System 15. Notice that we can search the vectors in the half plane (y ≥ 0), because if u 1 and u 2 are generator vectors, then their symmetric vectors with respect to (y = 0) axis are also generator vectors. Consequently, we have:

-l 1max ≤ x 1 ≤ l 1max 0 ≤ y 1 ≤ l 1max (16)
and

-l 2max ≤ x 2 ≤ l 2max 0 ≤ y 2 ≤ l 2max (17) 6.2.2 Case R ≤ √ 2
We use l 1min = 0. In addition, we can use the bound implied by the vectors proposed in Remark 4, that is: S s = (hR + 1) 2 , which replaces S h for the computation of l 1max . Then, instead of a fixed bounds for l 1max and l 2max , we propose a bound depending on u 1 , by using [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF] we have:

l 2max (u 1 ) = 2 √ 3Ss 3|u1| , and because |u 2 | ≥ |u 1 | we have: l 1min (u 1 ) = |u 1 |. Hence:    0 < |u 1 | ≤ hR + 1 |u 1 | ≤ |u 2 | ≤ 2 √ 3(hR + 1) 2 3|u 1 | (18)

Method OVS

To find the optimal vectors, we define Method OVS.

Method OVS:

1. The first step is to search S 1 the initial set of generator vectors u 1 and u 2 . S 1 is the set of vectors having as coordinates the integers (x 3. After the step 2, we obtain the set of valid reduced vectors. Now, the optimal vectors are the vectors having the smallest absolute value of their determinant.

Notice that the search of the optimal vectors can be done by a central unit, that distributes the vectors to all nodes. It is also possible that each node in the grid computes the two generator vectors.

We can now evaluate the complexity of VCM that lies in the generator vectors computation and in their validity check.

Theorem 6 Depending on VC method, VCM complexity is in Θ(R 6 ) for Method VC1 and Θ(R 4 ) for Method VC2.

Proof: The vector search phase is in Θ(R 2 ) for each vector. The validity check is in Θ(R 2 ) for Method VC1 and Θ(1) for Method VC2.

Summary: How to Apply VCM in Practice

This section summarizes the previous sections. In practice, to apply VCM, we start from a set of sensor nodes arranged as a two-dimensional lattice (identified by their integer coordinates). In reality, in an actual network, the set of neighbors will not be exactly given by the set of nodes within a fixed range R. However, notice that a valid h-hop coloring for a given R, is also a valid h-hop coloring for R ′ < R (although likely non-optimal). Hence, we start by selecting the value of R, a radio range such as two nodes at a distance greater than R are never neighbors (may be using measurements or neighborhood detection), and hence is not presented here. Results are given for 3-hop coloring. For high radio range values, the number of nodes should be high enough to allow the reproduction of the color pattern. We observe that VCM provides an optimal 3-hop coloring, for any radio range. This is not true for any other priority assignment tested. Moreover, the number of colors does not depend on the grid size.

The Vector Method and Real Wireless Networks

In this paper, VCM has been described for grid topology since this topology is used by real applications briefly presented in Section 1. Notice however, that wireless communication may differ from what is expected by the theory that often uses simplified models: radio links may be asymmetric, a radio link may exist even if the remote node is at a distance higher than the transmission range or conversely not exist even if the remote node is in the theoretical radio range. That is why, the first step in VCM is to select R such that two nodes that are at a distance greater than R are not neighbors. Another real aspect in wireless sensor networks is nodes late arrival (because of the mobility or in case of late start-up) and nodes disappearance (a node is out of battery for instance). What is the impact of such impairments on VCM? We can classify these impairments in two categories: 1. Radio links disappearance: in this case, VCM always provides a valid coloring. The periodic coloring may still be optimal, as long as the percentage of missing radio links is below a given threshold L 1 .

2. Radio links appearance: in this case, nodes that should not be neighbors (or heard nodes in case of asymmetric links) are. As a consequence, nodes hav-ing the same color may interfere because of these additional radio links. The periodic coloring provided by VCM may still be perfectly acceptable by the application as long as the percentage of additional radio links is below a given threshold L 2 .

As a further work, we will evaluate the thresholds L 1 and L 2 and also study how random topologies can be mapped in grid topologies.

Conclusion

In this research report, we have presented a new method called VCM, the Vector-Based Coloring Method, able to provide an optimal periodic h-hop coloring of any grid, with h an integer ≥ 1, for any radio range R. This method is easy to use: a single round is needed. It suffices to compute the two generator vectors, as shown in this paper. Knowing its coordinates within the grid, each node deduces its color from a simple computation given in the paper. We have shown that this h-hop node coloring is optimal in terms of colors and rounds. We determined also an upper and a lower bound for the number of colors needed to color an infinite grid. VCM provides the optimal number of colors compared to all possible coloring including non periodic ones. Finally, we discussed how to apply VCM in real wireless networks.

Figure 2

 2 Figure 2 presents an example of a periodic 3-hop coloring of a 10 × 10 grid with a transmission range R = 1.

Figure 2 :

 2 Figure 2: Example of periodic 3-hop coloring (R=1)

Figure 3 :Lemma 2

 32 Figure 3: Method VCM-NCC 2

Table 1 :

 1 Number of colors for various transmission ranges, grid sizes and priority assignments., for 3-hop coloring

	Grid size priority assignment	colors	colors
			for range = 1 for range = 2
	10x10	line or column	8*	30
		diagonal	8*	28
		distance to origin	8*	30
		random	13	36
	20x20	line or column	15	33
		diagonal	8*	29
		distance to origin	8*	30
		random	14	41

  1 , y 1 ) and (x 2 , y 2 ) verifying System 17 if R > √ 2 and System 18 if R ≤ √ 2. 2. Now, the set S 2 should be filtered to keep only reduced and valid vectors. Indeed, for each couple of vectors (u 1 , u 2 ) in S 1 , we should verify: 2.1. (u 1 , u 2 ) are reduced, that is they verify System 19. 2.2. to check the validity of the coloring, two cases are possible:

	2.2.1 if R >	√ 2 apply Method VC2.
	2.2.2. otherwise, apply Method VC1.

Table 3 :

 3 Number of colors obtained for 3-hop coloring.

	Radio Grid size		Colors
	range		VCM line/column
	1	10x10	8*	8*
		20x20	8*	8*
		30x30	8*	8*
	1.5	10x10	16*	16*
		20x20	16*	16*
		30x30	16*	16*
	2	10x10	25*	30
		20x20	25*	33
		30x30	25*	33
	3	20x20	68*	80
		30x30	68*	83
	3.5	20x20	80*	91
		30x30	80*	91

RR n°7756

showing that specifically for grids, there are better techniques than already known general α-approximations (even for unit disk graphs, such as[START_REF] Gräf | On coloring unit disk graphs[END_REF]), since hereα = 1 + O(1/R) when R → ∞ RR n°7756

informally, it is similar to a transforming the time of the day expressed as h:m:sh hour m minutes s seconds -into the time of the day expressed as seconds from midnight as (h, m, s) →

× h + 60 × m + s RR n°7756

a value h. Then, each node proceeds as follows: 1. Find the optimal valid vectors using the Method OVS. 2. Each node computes its color by applying either VCM-NCC 1 or VCM-NCC 2.

We can notice that VCM allows each node to know its color in a single round.

Coloring Results with VCM

Note that further examples of colorings are available externally at [START_REF]Vector-Based Coloring Method page[END_REF].

Examples of Vectors

Table 2 gives for different radio ranges two vectors generating the optimal periodic pattern as well as the minimal number of colors obtained by a periodic pattern, for both a 2-hop coloring and a 3-hop coloring. The '*' symbol highlights the optimality of the number of colors used. We observe that 2-hop coloring of the grid with radio range R = 3 is not equivalent to 3-hop coloring of a grid with R = 2 in terms of the number f colors (33 vs. 25). We conclude that the optimal number of colors is not determined only by the product h * R, but also the values of h and R separately.

Comparison with Other Methods

Table 3 depicts the simulation results obtained with the VCM for various grids, with various radio ranges. The method is compared to a distributed coloring algorithm using line/column as priority assignment heuristics. As observed in Table 1, the random priority assignment produces a high number of colors and

Annex

In this Annex, we group mathematical results and grid properties that are useful to study the validity and the optimality of VCM.

Gauss Lattice Reduction

For any pair of vectors u 1 , u 2 generating a lattice Λ(u 1 , u 2 ), the Gauss lattice reduction algorithm provides two reduced vectors v 1 , v 2 generating exactly the same lattice and verifying the System ( 19)

Additional properties are that v 1 and v 2 are also the two shortest distinct vectors of Λ(u 1 , u 2 ) and have the same lattice determinant as u 1 , u 2 . See for instance [START_REF] Vallée | Lattice reduction in two dimensions: analyses under realistic probabilistic models[END_REF] for more details.

Relation between Number of Hops and Actual Distance

Hereafter, we introduce some results related to grid networks. These results can be applied to VCM, or any other algorithm.

Results in this section are inequalities, establishing links between number of hops and actual distance.

Lemma 5 For any point V of R 2 , there exists a node V ′ of the grid

Proof: In the worst case, the node V occupies the center of a grid cell. It is at equal distance of two grid nodes that are diagonally opposed. Hence, its distance to one of them is equal to √ 2/2.

Lemma 6 For any transmission range R > √ 2, for any grid node U , any node

Hence, nodes W i for i ∈ {1, 2, . . . , h -1} constitute a h-hop path between U and V .

Lemma 7 For any transmission range R, for any two grid nodes U and V , in h-hop coloring, if d(U, V ) > hR then U and V are at least (h + 1)-hop away.

Proof: By contradiction assume that, U and V are h-hop away or less. Let W i be the k -1 nodes constituting the k-hop path between U and V , with k ≤ h. Let W 1 = U , and W h = V . Since nodes W i are 1-hop neighbors, we have:

Hence the contradiction.

Let U , V be two points of Z 2 and define H(U, V ) as the number of hops between U and V (it is an integer). For any R > 0 (some inequalities are trivially true when R ≤ √ 2), the lemma 6 and lemma 7 can be summarized as:

Since u 1 and u 2 are reduced vectors, we can use the property given in the System 19, we get:

Notice that this quantity does not change if we change the sign of α or of β. Thus, we assume (α ≥ 0), (β ≥ 0), and let f (α, β) = (αβ) 2 + αβ. By a change of variable β = α 2 + λ, we get:

Hence the lemma.

Lemma 9 Consider any transmission range R > √ 2, two reduced generator vectors u 1 and u 2 of the lattice Λ(u 1 , u 2 ), and a node W with U W = αu 1 + βu 2 for some α and β in Z. Assume also that the point V 1 such that U V 1 = u 1 is at strictly more than h hops from the U . Then: if |α| ≥ µ(R) or |β| ≥ µ(R) where µ(R) = 2 √ 3R 3(R-√

2) , we have: W is strictly more than h hops away from U .

RR n°7756

Proof: Since u 1 and u 2 are reduced, we can apply Lemma 8 and obtain:

, and as α ≥ µ(R)

Since the point V 1 is strictly more than h-hop away from U , the lemma 6 implies by contradiction that

2)h. It follows that:

Applying Lemma 7, we obtain the result.


Idris Kharroubi Ceremade
email: kharroubi@ceremade.dauphine.fr

Comparison Theorem for Brownian Multidimensional BSDEs via Jump Processes

Keywords: Multidimensional backward SDE, random measure, backward SDE with jumps, comparison theorem MSC Classification: 60H05, 60H10, 60H20, 60G57

In this note, we provide an original proof of the comparison theorem for multidimensional Brownian BSDEs in the case where at each line k the generator depends on the matrix variable Z only through its row k.

Introduction

The comparison theorem for Backward SDEs (BSDEs for short) is a result which allows to compare the solutions of two BSDEs whenever you can compare their terminal conditions and generators. Although the comparison theorem holds true for Lipschitz BSDEs in the Brownian one dimensional case (see [START_REF] Peng | A generalized dynamic programming principle and Hamilton-Jacobi-Bellman equation[END_REF]), it needs stronger assumptions in the other cases.

In the Brownian multidimensional case, Hu and Peng [START_REF] Hu | On the comparison theorem for multidimensional BSDEs[END_REF] give a necessary and sufficient condition for the comparison theorem. Their result is based on the viability property for BSDEs studied in Buckdahn et al. [START_REF] Buckdahn | Viability property for a backward stochastic differential equation and applications to partial differential equations[END_REF] where the authors give an necessary and sufficient condition to ensure that the component Y stays in a given set. However, this approach uses analytical arguments and hence imposes a continuity assumption on the generator w.r.t. the time variable t.

In this note, we provide a comparison theorem for Lipschitz multidimensional Brownian BSDEs whose generator depends at each line k on the variable Z only through its line k :

f k (t, y, z) = f k (t, y, z k ) , (t, y) ∈ [0, T ] × R n , z =    z 1 . . . z n    ∈ R n×d .
For this, we introduce a random measure and show that the process constructed by choosing the component w.r.t. this random measure is solution to a BSDE with jumps. We then use existing comparison results for BSDES with jumps to state our main result. An important feature is that our result holds without supposing any continuity assumption on the generator w.r.t. the time variable t.

The rest of the note is organised as follows. In the next section we give the framework and state our result. In Section 3 we recall under which assumptions the comparison theorem for BSDEs with jumps holds. The last section is dedicated to the proof of our main result.

The comparison theorem for multidimensional BS-DEs

Let (Ω, A, P) be a probability space endowed with a standard d-dimensional Brownian motion (W (t)) t≥0 and let F = (F(t)) t≥0 be the P-completion of the filtration generated by (W (t)) t≥0 . We fix a terminal time T > 0 and an integer n ≥ 1. Throughout this note, we denote by -S 2 F the set of F-adapted continuous processes Y valued in R n such that

Y S 2 := E sup t∈[0,T ] |Y (t)| 2 < ∞ , -L 2 F the set of F-predictable processes Z valued in R n×d such that Z L 2 := E T 0 |Z(t)| 2 dt < ∞ .
We then consider two functions f 1 and

f 2 from Ω × [0, T ] × R n × R d×n to R n , which are F-progressive ⊗B(R n ) ⊗ B(R n×d )
-measurable, and two random variables ξ 1 and ξ 2 which are F T -measurable. We introduce the following assumptions.

(H1) ξ 1 and ξ 2 are square integrable:

E [|ξ i | 2 ] < ∞ , i = 1, 2 ,
(H2) f 1 (., 0, 0) and f 2 (., 0, 0) are square integrable:

E T 0 |f i (t, 0, 0)| 2 dt < ∞ , i = 1, 2 ,
(H3) there exists a constant L such that P-a.s. we have

|f i (t, y, z) -f i (t, y ′ , z ′ )| ≤ L(|y -y ′ | -|z -z ′ |) , i = 1, 2 .
for all (t, y, y ′ , z, z

′ ) ∈ [0, T ] × [R n ] 2 × [R n×d ] 2 .
For i = 1, 2, we consider the BSDE

Y i (t) = ξ i + T t f i (s, Y i (s), Z i (s))ds - T t Z(s)dW (s) , 0 ≤ t ≤ T . (2.1)
We denote by the partial ordering relation on

R n : for y 1 , y 2 ∈ R n , we have y 1 y 2 iff y k 1 ≥ y k 2
, for all k = 1, . . . , n. We also need an additional assumption on the form of the dependence of the generator f w.r.t. the unknown Z.

(H4) f 1 and f 2 depends on the last variable z at each line k only through the line k of z:

f k i (t, y, z) = f k i (t, y, z k ) , i = 1, 2 , for all (t, y) ∈ [0, T ] × R n and z =    z 1 . . . z n    ∈ R d×n .
Finally, we introduce an assumption which can be interpreted as a monotonicity condition of the generator w.r.t. the variable y.

(H5) f i satisfies the following monotonicity condition: there exit two constants

C 2 > C 1 > 0 and a map δ from Ω×[0, T ]×[R n ] 2 ×R n×d to [C 1 , C 2 ] k which is F-predictable⊗B(R n )⊗ B(R n ) ⊗ B(R n×d ) such that f ℓ i (t, y, z) -f ℓ i (t, y ′ , z) ≤ k∈K δ k (t, y, y ′ , z)(y k -y ′ k ) , ℓ = 1, . . . , n , for all (t, y, y ′ , z) ∈ [0, T ] × [R n ] 2 × R n×d .
We provide an example of a generator satisfying the previous assumption. Suppose that f i admits partial derivatives w.r.t. y k , k = 1, . . . , n, such that

∂f ℓ i ∂y k (t, y, z) ∈ [C 1 , C 2 ] , k, ℓ = 1, . . . , n , (2.2)
for all (t, y, z) ∈ [0, T ] × R n × R n×d , then f i satisfy (H5). Indeed, we have

f ℓ i (t, y, z) -f ℓ i (t, y ′ , z) = n k=1
f ℓ i (t, y ′1 , . . . , y ′k-1 , y k , . . . , y n , z)f ℓ i (t, y ′1 , . . . , y ′k , y k+1 , . . . , y n , z) .

Then using the mean value theorem and (2.2), we get

f ℓ i (t, y, z) -f ℓ i (t, y ′ , z) = n k=1 δ k (t, y, y ′ , z)(y k -y k ′ ) , with δ k (t, y, y ′ , z) ∈ [C 1 , C 2 ]. Hence (H5) is satisfied.
Notice that we can extend this example to the case where the generator f is less regular. To this end we replace condition (2.2) by the following one

f ℓ i (t, y 1 , . . . , y k-1 , x, y k+1 , . . . , y n , z) -f ℓ i (t, y 1 , . . . , y k-1 , x ′ , y k+1 , . . . , y n , z) x -x ′ ∈ [C 1 , C 2 ] , (2.3) for all x, x ′ ∈ R such that x = x ′ . If f ℓ i (t, y 1 , . . . , y k-1 , ., y k+1 , . . . , y n , z) satisfy (2.
3) for all (t, y 1 , . . . , y k-1 , y k+1 , . . . , y n , z) ∈ [0, T ]×R n-1 ×R n×d , and all ℓ = 1, . . . , n, then f i satisfy (H5). Indeed, we write as previously

f ℓ i (t, y, z) -f ℓ i (t, y ′ , z) = n k=1
f ℓ i (t, y ′1 , . . . , y ′k-1 , y k , . . . , y n , z)f ℓ i (t, y ′1 , . . . , y ′k , y k+1 , . . . , y n , z) .

Then from (2.3) we have

f ℓ i (t, y ′1 , . . . , y ′k-1 , y k , . . . , y n , z) -f ℓ i (t, y ′1 , . . . , y ′k , y k+1 , . . . , y n , z) ≤ (C 1 1 y k <y ′k + C 2 1 y ′k ≤y k )(y k -y ′k ) .
Taking δ k (t, y, y ′ , z) = C 1 1 y k <y ′k + C 2 1 y ′k ≤y k we get (H5).

We now state the main result of this note.

Theorem 2.1 (Comparison Theorem). Suppose that (H1)-(H4) hold and that f 1 of f 2 satisfies (H5). Suppose also that P-a.s.

ξ 1 ξ 2 and f 1 f 2 . Then if (Y i , Z i ) ∈ S 2 F × L 2 F is solution of (2.1) for i = 1, 2, we have Y 1 (t)
Y 2 (t) , 0 ≤ t ≤ T , Pa.s.

Remark 2.1. An important feature of our result is that it relax the continuity assumption of the generator w.r.t the time variable t used in [START_REF] Hu | On the comparison theorem for multidimensional BSDEs[END_REF].

Remark 2.2. Under Assumptions (H4) and (H5), the necessary and sufficient condition given by Theorem 2.1 in [START_REF] Hu | On the comparison theorem for multidimensional BSDEs[END_REF] is satisfied. Indeed, suppose w.l.o.g that (H5) holds true for f 1 .

Since f 1 f 2 , we have

-4 y -, f 1 (t, y + + y ′ , z) -f 2 (t, y ′ , z ′ ) ≤ -4 y -, f 1 (t, y + + y ′ , z) -f 1 (t, y ′ , z ′ ) ≤ -4 n k=1 [y k ] -f k 1 (t, y + + y ′ , z k ) -f k 1 (t, y ′ , z k ) -4 n k=1 [y k ] -f k 1 (t, y ′ , z k ) -f k 1 (t, y ′ , z ′ k )
From the Lipschitz property of f 1 and the inequality ab ≤ 1 2 a 2 + 2b 2 for a, b ∈ R, we get

-4 n k=1 [y k ] -f k 1 (t, y ′ , z k ) -f k 1 (t, y ′ , z ′ k ) ≤ 2 n k=1 1 y k <0 |z k -z ′ k | 2 + 8|y -| 2 . (2.4)
Then using assumption (H5) we have

-4 y -, f 1 (t, y + + y ′ , z) -f 1 (t, y ′ , z) ≤ 0 . (2.5)
Combining (2.4) and (2.4) we get

-4 y -, f 1 (t, y + + y ′ , z) -f 2 (t, y ′ , z ′ ) ≤ 2 n k=1 1 y k <0 |z k -z ′ k | 2 + 8|y -| 2 ,
which is the necessary and sufficient condition for comparison given in [START_REF] Hu | On the comparison theorem for multidimensional BSDEs[END_REF].

Comparison for BSDEs with jumps

We consider a Poisson random measure µ on R + × K with K := {1, . . . , n}. We assume that this random measure µ is independent of (W (t)) t≥0 . We denote by G = (G(t)) t≥0 the P-augmentation of the filtration generated by F and µ. We suppose that µ is of the form

µ([0, t] × B) = ℓ≥1 1 [0,t]×B (τ ℓ , ζ ℓ ) , t ≥ 0 , B ⊂ K , (3.6)
where (τ ℓ ) ℓ≥1 is nondecreasing sequence of G-stopping times and ζ ℓ is a G(τ ℓ )-measurable random variable for each ℓ ≥ 1.

We assume that µ admits a compensator of the form λ(k)dt with λ(k) > 0 for all k ∈ K and we denote by μ the compensated measure associated to µ:

μ([0, t] × B) = µ([0, t] × B) -t k∈K λ(k)1 B (k) , t ≥ 0 , B ⊂ K .
We then consider the following spaces:

-S 2 G the set of G-adapted càdlàg processes Y valued in R such that Y S 2 < ∞ , -L 2 G the set of G-predictable processes Z valued in R d such that Z L 2 < ∞ , -L 2 G,λ the set of processes U from Ω × [0, T ] × K to R such that U (k, .) is G-predictable for all k ∈ K and U L 2 λ := E T 0 k∈K |U (t, k)| 2 λ(k)dt < ∞ .
We consider two functions g 1 and g

2 from Ω × [0, T ] × R × R d × R n to R n , which are G- progressive ⊗B(R) ⊗ B(R d ) ⊗ B(R n )-
measurable, and two random variables η 1 and η 2 which are G T -measurable.

We then introduce the following assumptions (H'1) η 1 and η 2 are square integrable:

E [|η i | 2 ] < ∞ , i = 1, 2 ,
(H'2) g 1 (., 0, 0, 0) and g 2 (., 0, 0, 0) are square integrable:

E T 0 |g i (t, 0, 0, 0)| 2 dt < ∞ , i = 1, 2 ,
(H'3) there exists a constant L such that P-a.s. we have

|g i (t, y, z, u) -g i (t, y ′ , z ′ , u ′ )| ≤ L(|y -y ′ | + |z -z ′ | + |u -u ′ |) , i = 1, 2 . for all (y, y ′ , z, z ′ , u, u ′ ) ∈ [R] 2 × [R d ] 2 × [R n ] 2 .
For i = 1, 2, we consider the BSDE with jumps

Y i (t) = η i + T t g i (s, Y i (s), Z i (s), U i (s, .))ds - T t Z(s).dW (s) - T t K U (s, k)μ(dk, ds) , 0 ≤ t ≤ T . (3.7)
We finally introduce a monotonic assumption of the generator used by Royer [START_REF] Royer | Backward stochastic differential equations with jumps and related non-linear expectations[END_REF] to get comparison result for BSDEs with jumps.

(H'4) There exists two constants

C 4 ≥ C 3 > -1 and a map γ from Ω × [0, T ] × K × R × R d × [R n ] 2 to [C 3 , C 4 ] which is G-predicable ⊗B(R) ⊗ B(R d ) ⊗ B(R n ) ⊗ B(R n )-measurable such that P-a.s. g i (t, y, z, u) -g i (t, y, z, u ′ ) ≤ K γ y,z,u,u ′ (t, k) u(k) -u ′ (k) λ(dk) , for all (t, y, z, u, u ′ ) ∈ [0, T ] × I × R × R d × [R n ] 2 .
Under the previous assumptions we have the following comparison theorem (see Theorem 2.5 in [START_REF] Royer | Backward stochastic differential equations with jumps and related non-linear expectations[END_REF]).

Theorem 3.2. Suppose that (H'1)-(H'3) hold and that g 1 or g 2 satisfy (H'4). Suppose also that P-a.s.

η 1 ≥ η 2 and g 1 ≥ g 2 . Then if (Y i , Z i , U i ) ∈ S 2 G × L 2 G × L 2 G,λ is solution of (3.7) for i = 1, 2, we have Y 1 (t) ≥ Y 2 (t) , 0 ≤ t ≤ T , P -a.s. 4 Proof of Theorem 2.1 Let (Y i , Z i ) ∈ S 2 F × L 2 F be solution to (2.1) for i = 1, 2 and k ∈ K. To prove that Y k 1 (t) ≥ Y k 2 (t) , 0 ≤ t ≤ T , P -a.s.
we proceed in three steps.

Step 1. Construction of jump processes. Take µ a Poison random measure on R + × K of the form (3.6), independent of (W (t)) t≥0 with intensity λ defined by λ(k) = 2L for all k ∈ K, where L is the Lipschitz constant of f i , i = 1, 2. Consider the process (N (t)) t≥0 defined by

N (t) = k + t 0 K (k -N (t-))µ(dk, dt) , 0 ≤ t ≤ T .
Notice that since µ has the form (3.6), N is the process taking the value ζ ℓ on [τ ℓ , τ ℓ+1 ). Define also, for i = 1, 2, the processes Y i , Z i and U i by

Y i (t) = Y N (t) i (t) , Z i (t) = Z N (t-) i (t) , U i (t, k) = (Y k i (t) -Y N (t-) i (t-)) k∈K , 0 ≤ t ≤ T . (4.8)
(at time t, the component is chosen as the value given by the process

N ) Since (Y i , Z i ) ∈ S 2 F × L 2 F , we easily check that (Y i , Z i , U i ) ∈ S 2 G × L 2 G × L 2 G,λ for i = 1, 2.
A straightforward computation shows that, for i = 1, 2, (Y i , Z i , U i ) satisfies (3.7) with η i = ξ N (T ) i and g i (t, y, z, u) = f N (t) i t, y + u(1), . . . , y + u(n), z -k∈K u(k)λ(k) , (4.9) for (t, y, z, u)

∈ [0, T ] × R × R d × R n .
Step 2. Comparison of the jump processes. Notice that since ξ 1 ξ 2 and f 1 f 2 we have η 1 ≥ η 2 and g 1 ≥ g 2 . Notice also that since f i satisfy (H1)-(H3), g i satisfy (H'1)-(H'3) for i = 1, 2. We prove that g i defined by (4.9), satisfy (H'4). Indeed, for (t, y, z, u, u ′ ) ∈ [0, T ] × R × R d × [R n ] 2 we have from (H5) and (4.9) g i (t, y, z, u)g i (t, y, z, u ′ ) ≤

  k∈K δ k (t, y + u, y + u ′ , z)(u(k)u ′ (k)) -k∈K (u(k)u ′ (k))λ(k) ≤ n k=1 γ y,z,u,u ′ (t, k)(u(k)u ′ (k))λ(k) with γ y,z,u,u ′ (t, k) = δ k (t,y+u,y+u ′ ,z) λ(k) -1 ∈ [C 3 , C 4 ] with C 4 = C 1 min k λ(k) -1 and C 3 = C 1 max k λ(k) -1 > -1.Hence g i satisfy (H'4) and we have Y 1 (t) ≥ Y 2 (t) , 0 ≤ t ≤ T , Pa.s.(4.10)

Step 3. Back to the continuous processes. Recall that the random measure is of the form

where (τ ℓ ) ℓ is an increasing sequence of G-stopping times and ζ ℓ in a G τ ℓ -measurable r.v. valued in K. Using (4.10), we have

for all t ∈ [0, T ]. Since the processes Y i , i = 1, 2, are continuous and k is arbitrary fixed we get the result.


Oscar Botero
email: oscar.botero@it-sudparis.eu

Hakima Chaouchi
email: hakima.chaouchi@it-sudparis.eu

Platform and experimentation of secure service location with P2P/Client-Server over ad hoc networks *

Keywords: hoc networks, client-server, JXTA, peer to peer, network access control, network authentication, service location I

Ad hoc networking is considered as an inexpensive solution for easy and fast wireless network coverage. However, for real service deployment, security and availability in such networks are still under research even though some experimentation has shown its viability. Additionally, peer-to-peer (P2P) networking has emerged as a key technology to enable resource sharing among users. As a result, the load charge on servers can be reduced by using P2P, but this approach presents a drawback related to the services availability; when a peer is not connected, its resources are not reachable. Alternatively, Client-Server architecture provides a centralized approach; but a high demand on client requests might deteriorate service response and capacity. In the case of ad hoc networks, offering services securely is even more challenging since all nodes are anonymous until being authenticated. In this paper, we propose to offer a secure location of services in an ad hoc environment. We focused on the development of a proxy-based solution to combine a P2P-client/server network overlay in order to provide securely the location information of network services (e.g. AAA service, Kerberos) and to set a platform that can include application services (e.g. multimedia content service). More precisely, we deployed a network overlay P2P platform using JXTA; a set of peer to peer protocols, and we developed simple peer nodes and a proxy server for providing and ensuring service access control. Other security services can also be deployed such as Kerberos, PKI, among others. In our platform, the JXTA was combined; through the proxy server, with a distributed Radius AAA server to perform authentication tasks prior to discovering the location of the required services in the ad hoc network. We added encryption and message authentication code mechanisms to provide a complete secured solution. GPS Bluetooth devices were used to obtain nodes location but other location systems are also possible. Finally, a detailed description of the system architecture and platform is provided describing all the modular components as well as numerical results derived from a simple test bed.

INTRODUCTION

Providing services over an ad hoc network is a challenging issue from security, performance and feasibility points of view. To address this issue we combined P2P and Client-Server schemes to provide service access control and server location information. The P2P architecture provides a flexible approach when resources are shared between nodes. However, if peers are not available their resources and services are not reachable. A Client-Server architecture provides resources in a centralized manner offering control possibilities and network administration; conversely, server load can be affected when high rates of requests are managed. By combining both approaches we can rely on certain nodes to run some important network functions such as: AAA and main application services. The peers will provide their resources and services once available. We implemented a network overlay, by using JXTA [START_REF]JXTA: a network programming environment, Li Gong[END_REF][START_REF]Project JXTA 2.0 Super-Peer Virtual Network[END_REF][3][START_REF]JXTA Java Standard Edition v2.5: Programmers Guide[END_REF], which is a Sun's set of standard protocols. With these protocols, developers can be focused only on the application layer to implement P2P solutions co-existing with Client-Server platforms. We also developed a proxy server to manage service access control to peers on the application layer via an AAA server [START_REF]Radius server[END_REF] and simple peers to be authenticated and that will obtain a list of available services with their location. The location information is provided from a GPS Bluetooth device which gives to the nodes the possibility to calculate their geographical distance from the servicing node and get closer, in order to take advantages of specific applications e.g. social nets, content servers or network gaming. The security solution uses Radius, EAP-MD5, Bulk Encryption, and Message Authentication Code (MAC). We used for simplicity Radius and EAP-MD5 to provide authentication on the application layer but other strong also authentication methods can be used. Symmetric key encryption and MAC (based on RC4-SHA1) were also used in order to protect the message exchange. The following security requirements are provided: confidentiality: the messages are not disclosed to unauthorized peers, authentication: the sender is the one who claims to be and data integrity: the message was not modified accidentally or deliberately in transit. The approach is a modular design implemented with JAVA SE programming language [6] that provides easy nodes functionalities upgrade. By using a distributed Authentication Server we can implement different security approaches without modifying the JXTA protocols to grant access control. We are also open to use the authentication method that best fits the network requirements. We focused particularly on the authentication in the ad hoc network to allow secure service location discovery. The rest of the paper is organized as follows: In section II the problem is presented followed by section III where the platform architecture is described. In section IV the implementation is described followed by numerical results and finally the conclusions.

II. PROBLEM STATEMENT

The problem faced was how to provide LBS (location based services) discovery functionalities and to ensure at the same time authentication and secure communications among nodes in a general ad hoc environment. The proposal aims to authentication before service in the application layer by using the JXTA overlay with a proxy server connected to a radius server. The complete proposed solution is described in the following sections.

III. PROPOSED ARCHITECTURE

As stated before, we chose to use a P2P overlay to benefit from its flexibility in resource sharing and service exchange features and also we also considered a Client-Server approach to benefit from its centralized control. The services will be securely located thus allowing the user to estimate its distance from the requested service and to get closer to the servicing node if required.

The proposed solution consists of a JXTA P2P network, with simple peers that will perform authentication requests to our developed proxy server. It is to remark that JXTA itself provides an entry level security solution, where peers have their own certificate authorities and strong cipher functions are used. Despite that, no robust service access control is implemented. In order to implement it, a distributed AAA architecture is integrated into the overlay. We developed a proxy server in the P2P overlay to access the AAA server functionalities. This proxy is the interface between the distributed P2P overlay and the centralized AAA service; it will forward on behalf of the peers the requests to the Radius Server.

Encryption and MAC are used to keep the communications secure. GPS Bluetooth devices provide the current nodes' location; once collected and updated they will be transmitted to the trusted peers in order to communicate the list of available services and allow the calculation of the distance from them if necessary for some specific applications. All the platform modules were developed by using the JAVA SE programming language. The modularity of the design allows adding new features or upgrading functionalities with hard changes neither on the platform nor on the nodes. Figure 1 shows the simplified building blocks of our platform. The JXTA protocols define the default group to communicate called "Netpeergroup". We defined a new group called "ServiceNetgroup" to provide our services; in our scenario the AAA service.

The basic operation of the platform is as follows (Figure 1): a peer (a node connected to the network, in our scenario it is an ad hoc node) will discover the P2P group advertisement which is published by the proxy server. The peer will send the accorded messages to the proxy in order to be authenticated by using a symmetric key security scheme. The proxy will forward the request to the Radius Server. If the peer is authenticated it will obtain a list of available services indicating the current position by GPS coordinates, allowing the calculation of the distance to them and to further demand the service required. However, if the peer is not successfully authenticated no information will be disclosed.

IV. IMPLEMENTATION

As aforementioned, a combined architecture (P2P-Client/Server) solution based on JXTA protocols was implemented. We developed the simple peer application and the proxy server node, interacting with the AAA server by considering and implementing secure communication exchange between nodes as well.

Our contribution lies in providing the authentication prior to the service localization and access for ad hoc networks by using a set of P2P protocols to establish a network overlay and a proxy based solution and also providing the GPS location of the server and nodes to allow distance calculation. We proposed a modular solution that integrates the JXTA protocols, radius, GPS and security schemes.

The technology used and the overlay description is explained in the following parts.

A. Technology Details In order to develop the proposed solution the following elements were used: 1. JXTA " JXTA is a set of open, generalized peer-to-peer (P2P) protocols that allow any networked device -sensors, cell phones, PDAs, laptops, workstations, servers and supercomputers -to communicate and collaborate mutually as peers. " [START_REF]JXTA Java Standard Edition v2.5: Programmers Guide[END_REF].

JXTA name is derived from the word juxtapose, indicating that P2P solutions can co-exist with client/server solutions rather than replace them. In our case, we used the client/server based services such as AAA service via the P2P overlay. This allows us to benefit from P2P flexibility in resource sharing and service exchange as well as centralized control. JXTA defines a set of six XLM-based protocols that allow the establishment and use of P2P networks. These protocols are independent of the underlying implementation. Functions include: organize, discover and publish resources, communicate and monitor peer activity. With these protocols a virtual network overlay can be established on top of physical networks in order to allow peers to interact no matter which network or connectivity type is used. The standard JXTA protocols are six: Endpoint Routing Protocol (ERP), Rendezvous Protocol (RVP), Peer Resolver Protocol (PRP), Peer Discovery Protocol (PDP), Peer Information Protocol (PIP), and Pipe Binding Protocol (PBP). These protocols are independent from each other. A peer is not required to implement all of them to be a JXTA peer. It will implement only the protocols needed.

Basically JXTA provides a simple and generic P2P platform independent of the programming language used to implement it, the operating system, the network topology, and the security model used.

JAVA

Java is a very popular and functional object oriented platform independent programming language. The application was entirely developed using NetBeans IDE 6.1 with the UML plug-in [START_REF]Java IDE[END_REF] .The Java version used was J2SE 1.6 beta (Standard Edition), focused on desktops and personal computers with the Swing API for GUI development [6].

Security

In order to develop a secured application the following concepts were considered during implementation:

Encryption

In this work, bulk encryption is used. A bulk encryption algorithm uses a key to scramble data for transmission or storage. It can then only be decrypted using the same key [START_REF]Digital Signature Standard (DSS)[END_REF]. The Encryption/Decryption process used for the implementation of this project is based on RC4 algorithm with SHA1 and a pre-defined symmetric key that can be modified on the application interface in mutual agreement.

Integrity

In order to provide integrity and authenticity to the messages that will be exchanged, a MAC (Message Authentication Code) is added. It is based on RC4-SHA1 and a symmetric key. The JxtaCrypto interface is used to access each of the services provided in the Java security package [START_REF][END_REF]. The MAC is added into the message and it will be verified when it is received, if the validation is successfully achieved the message has not been corrupted.

Access Control: Radius-EAP

Radius stands for: Remote Authentication Dial In User Service, and it is a networking protocol that provides centralized management of access to networks. In order to implement the admission control with the Radius protocol the application freeradius V1.17 [START_REF]Radius server[END_REF] is used in addition to the jradius module [8], allowing us to link the jradius Java with freeradius on the proxy server.

Jradius is an open source server-client framework oriented to Java implementations. The server module works together with freeradius through module. We used radius for service authentication an rlm_jradius control on the application layer. EAP or Extensible Authentication Protocol is an authentication framework that provides the freedom of selecting any authentication mechanism. EAP typically runs directly over data link layers without requiring IP; in fact, EAP just provides some common functions and a negotiation of the desired authentication mechanisms, which are commonly called methods. We used EAP-MD5 method just for its simplicity on the implementation. We are focused on service access control on the application layer. For real deployment of the platform more secure methods can be used.

EAP-MD5 is a challenge/response protocol that uses the MD5 hash algorithm of 128-bit to verify the authenticity of user's password. It allows the user authentication to the server but does not allow any server authentication. This method is fast but vulnerable to man-in-the-middle attacks, dictionary attacks and exposes station identity; however, it is an interesting solution when power processing limitations on devices are present.

4) GPS

Global Positioning System is a global navigation satellite system that uses information from at least 24 Medium Earth Orbit satellites. The information obtained determines the location, speed, direction and time of the GPS device.

The GPS device used was the Holux GPS Slim 236 [START_REF]GPS product details[END_REF] (Figure 2) using Bluetooth and capturing the data in GPGGA format [START_REF]GPS messages details[END_REF] (Figure 3) from a virtual serial port managed through the nodes developed. To calculate the distance between the Server and the Client the Haversine formula [START_REF] Sinnott | Virtues of the Haversine[END_REF] was used but other formulas can be implemented as required to gain in precision (this one provides 3m accuracy)

B. Application Description

There are two nodes that were developed, one is the proxy server, that will perform the service access control tasks by using a radius server and the other is the client that will be authenticated by using the P2P overlay. The proxy server and the radius one can be located in the same computer or in a distributed way. In order to develop the applications the following equipments were used:

• Laptop Dell Inspiron 1525, Intel Core2Duo 2.4 GHz, OS Vista (Proxy Server and simple peers). • Laptop Elonex, Pentium M OS Fedora Core 8 (Radius Server)

• GPS Bluetooth Holux slim236
The Java Libraries required for running the applications are the following: $GPGGA,161721.000,4837.4334,N,00226.5935,E,1,03,2.4,104.7,M,47.4,M,,0000*5A.

The first time a JXTA application runs, we observe the JXTA network configurator that asks for the Peer ID: Used to identify the peer and as login for further uses and the Password: Used to identify the peer and to link it with the ID for authentication. We can also specify the type of peer (Relay, Rendezvous, proxy) and establish the HTTP and TCP settings. It is important to remark that when running several peers in the same computer, different TCP ports should be specified in order to perform the connections properly.

Radius Admission Control (EAP-MD5)

The API used for Radius authentication [START_REF]Radius server[END_REF] allows implementing the EAP-MD5 process. This method can be replaced for more secure options. For the client application the following parameters are required in order to be authenticated through the proxy server: radius login, radius password, radius secret, symmetric key, client ID. Once the client has obtained the server's advertisement, it will try to be authenticated, so the client application will send the parameters to the proxy server, and then the authentication with the Radius Server is performed.

Cryptography

The messages exchanged are encrypted in order to secure them. The jxtasecurity library is used to perform this task by using RC4-SHA1 and a symmetric key. The messages are embedded into XML structures that allow us to label the fields and to extract the information easily.

MAC (Message Authentication Code)

The MAC is generated and inserted into a new field within the messages that will be used later for validation.

Application Message exchange:

In the following figure are shown the message exchange between the elements on the platform, (Figure 4) as well as the main screens of the nodes (Figure 5, Figure 6)

V. DISCUSSION

We proceed with the measurement of the authentication delay time through our platform and we depicted the results in Figure 8. The results obtained with our testbed (Figure 7) are compared with some obtained for other research experiments for authentication delay by using locally radius on WiFi [START_REF] Bohák | An authentication scheme for fast handover between WiFi access points[END_REF]. The system developed is based on JAVA which is a popular programming platform independent language. New features can be added to extend the basic functionalities of the application in a modular way including the deployment of new services (multimedia content, social nets, gaming among others). Finally, it is easy to distribute and deploy the application for the clients by using jnlp/jar formats.

As mentioned earlier, we used EAP-MD5 method for simplicity but it presents vulnerabilities to man-in-the middle attacks and dictionary attacks. The symmetric key approach can be used but requires an alternate channel to distribute the key. The PKI approach can be used but the hardware limitations and processing power should be considered to make it feasible. We perform authentication before accessing the services and all communications between nodes being secure.

VI. CONCLUSIONS AND FUTURE WORK

We presented our solution to handle service access control by using a P2P-Client-Server JXTA platform. This is to allow trusted peer clients to request (in a secure way) location information (GPS) about services available in the same overlay. It is applied specifically for general ad hoc networks to allow only authenticated nodes to obtain the geographical location (and the distance) from servicing nodes. The practical and original aspect of this application in ad hoc networks is to let the nodes to know securely the geographical distance from the servicing and peer nodes, and to get closer to them as it can be required by different applications such as social networking, content service with QoS among others.

The proposed application was developed in Java keeping the modularity as a strong aspect. Modularity allows to integrate different services running the same set of protocols or to add new features easily (e.g. multimedia content).

On the scope of this project, the application developed provides only communication between the nodes and the server that authenticates them. In order to extend the application functionalities, we can deploy multimedia services on the platform and observe the peers' interaction. We can provide tokens to authenticated peers in order to further request services. Finally, our future plan is also centered on performance measurements and protocol optimization.

VII.

Figure 1 .

 1 Figure 1. JXTA overlay over Ad hoc

Figure 2 .Figure 3 .

 23 Figure 2. GPS Holux Slim 236

2 d

 2 = distance between the two points R = radius of the reference sphere l1=latitude point 1 l2=latitude point 2 ∆λ=longitude point 2 -longitude point 1

Figure 4 Figure 5 .

 45 Figure 4. Platform message exchange

Figure 7 .Figure 8 .

 78 Figure 7. Testbed

* This work is sponsored by ANR SARAH French National research project (2006-2009)

Jcommport: is an open source library that allows the serial port management and data capture. Swingx: Provides the graphical objects for the GUI. JXTA 2.5: Provides the JAVA implementation of the JXTA protocols. Jxtasecurity: It is used to perform cryptography and MAC functions. The nodes perform the following functions:

1. Proxy Server:

The proxy server has the following features:

Create the Peer Group that identifies the Access Control service. Capture GPS information from the Bluetooth GPS connected to the virtual serial port. Accept and process incoming peers' authentication requests.

Perform cryptography functions with the data sent and received (Encrypt\Decrypt\MAC). Establish communication with the Radius server using EAP-MD5 on the application layer in order to authenticate peers (ad hoc nodes in our scenario).

Send actual server GPS position to peers (Encrypted). Calculate peers' distance to server. Generates information related to the peers authentication attempts. Send list of peers with location and services provided to authenticated nodes if required.

Client:

The client node has the following features: Find the Peer Group advertisement published by the proxy server Perform cryptography functions with the data sent and received (Encrypt\Decrypt\MAC). Send actual GPS position (Encrypted) to the server. Calculate distance: peer to server. Extract peers available with their location. The nodes can be deployed by using the JNLP (Java Network Launching Protocol) format that allows us to download the executable file from a server, or it also can be distributed as a jar file compressed with all the libraries required for running the application.

Security

The nodes provide the following security features: 3.1. ID and password for the JXTA network Configurator