Rennan Dantas
email: rennan@lia.ufc.br

Frédéric Havet
email: frederic.havet@cnrs.fr

Rudini M Sampaio
email: rudini@dc.ufc.br

Minimum density of identifying codes of king grids

Keywords: identifying codes, king grids, Discharging Method

The minimum density of an identifying code in G is denoted by d * (G). In this paper, we study the density of king grids which are strong products of two paths. We show that for every king grid G, d * (G) ≥ 2/9 = 0.222. In addition, we show that this bound is attained only for king grids which are strong products of two infinite paths. Given a positive integer k, we denote by K k the (infinite) king strip with k rows. We prove that d * (K 3 ) = 1/3 = 0.333, d * (K 4 ) = 5/16 = 0.3125, d * (K 5 ) = 0.2666 and d * (K 6 ) = 5/18 = 0.2777. We also prove that 2 9 + 8 81k ≤ d * (K k ) ≤ 2 9 + 4 9k for every k ≥ 7.

Introduction

Given an integer k ≥ 1, let [k] = {1, . . . , k}. Let G be a graph and v a vertex of G. The neighbourhood of v, denoted by N (v), is the set of vertices adjacent to v in G, and the closed neighbourhood of v is the set

N [v] = N (v) ∪ {v}. Given a set C ⊆ V (G), the identifier of a vertex v ∈ V (G) is C[v] = N [v] ∩ C.
We say that C is an identifying code of G if every vertex has non-empty identifier and, for all distinct u and v, u and v have distinct identifiers. Formally, C is an identifying code if (i) for all v ∈ V (G), C[v] = ∅, and

(ii) for all distinct u, v ∈ V (G), C[u] = C[v].
It is easy and well-known that a graph G has an identifying code if and only if it contains no twins (vertices u, v ∈ V (G) with

N [u] = N [v]). 1
Let G be a (finite or infinite) graph with bounded maximum degree. For any non-negative integer r and vertex v, we denote by B r (v) the ball of radius r in G centered at v, that is B r (v) = {x : dist(v, x) ≤ r}. For any set of vertices C ⊆ V (G), the density of C in G, denoted by d(C, G), is defined by

d(C, G) = lim sup r→+∞ |C ∩ B r (v 0 )| |B r (v 0 )| ,
where v 0 is an arbitrary vertex in G. The infimum of the density of an identifying code in G is denoted by d * (G). Observe that if G is finite, then d * (G) = |C * |/|V (G)|, where C * is a minimum-size identifying code of G.

The problem of finding low-density identifying codes was introduced in [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] in relation to fault diagnosis in arrays of processors. Here the vertices of an identifying code correspond to controlling processors able to check themselves and their neighbours. Thus the identifying property guarantees location of a faulty processor from the set of "complaining" controllers. Identifying codes are also applied for compact routing in networks [START_REF] Laifenfeld | Joint monitoring and routing in wireless sensor networks using robust identifying codes[END_REF][START_REF] Laifenfeld | Joint monitoring and routing in wireless sensor networks using robust identifying codes[END_REF], emergency sensor networks in facilities [START_REF] Ray | Robust location detection in emergency sensor networks[END_REF], to model a location detection problem with sensor networks [START_REF] Ray | Robust location detection with sensor networks[END_REF], or the analysis of secondary RNA structures [START_REF] Haynes | A quantitative analysis of secondary rna structure using domination based parameters on trees[END_REF].

Particular interest was dedicated to grids as many processor networks have a grid topology. There are three regular infinite planar grids, namely the hexagonal grid, the square grid and the triangular grid.

Regarding the infinite square grid G S , Cohen et al. [START_REF] Cohen | Improved identifying codes for the grid[END_REF] gave a periodic identifying code of G S with density 7/20 = 0.35. This density was later proved to be optimal by Ben-Haim and Litsyn [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. Some papers also obtained results for square grids with finite number of rows. For any positive integer k, let S k denote the square grid with k rows. Daniel, Gravier, and Moncel [START_REF] Daniel | Identifying codes in some subgraphs of the square lattice[END_REF] showed that d * (S 1 ) = 1/2 = 0.5 and d * (S 2 ) = 3/7 = 0.429. They also showed that, for every k ≥ 3, They also proved d * (S 3 ) = 3/7 = 0.429. Recently, Jiang [START_REF] Jiang | Periodicity of identifying codes in strips[END_REF] proved d * (S 4 ) = 11/28 = 0.393 and d * (S 5 ) = 0.38.

Regarding the infinite triangular grid G T , Karpovsky et al. [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] showed that d * (G T ) = 1/4 = 0.25. Let T k denote the triangular grid with k rows. In 2016, Dantas et al. [START_REF] Dantas | Identifying codes for infinite triangular grids with a finite number of rows[END_REF] proved that d * (T 1 ) = d * (T 2 ) = 1/2 = 0.5, d * (T 3 ) = d * (T 4 ) = 1/3 = 0.333, d * (T 5 ) = 0.3, d * (T 6 ) = 1/3 = 0.333 and d * (T k ) = 1/4 + 1/(4k) for every k ≥ 7 odd. Moreover, they proved that 1/4 + 1/(4k) ≤ d * (T k ) ≤ 1/4 + 1/(2k) for every k ≥ 8 even, and conjectured that d * (T k ) = 1/4 + 1/(2k) for every k ≥ 8 even.

Regarding the infinite hexagonal grid G H , the best known upper bound on d * (G H ) is 3/7 = 0.429 and comes from two identifying codes constructed by Cohen et al. [START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]; these authors also proved a lower bound of 16/39 = 0.4102. This lower bound was improved to 12/29 = 0.4138 by Cranston and Yu [START_REF] Cranston | A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid[END_REF]. Cukierman and Yu [START_REF] Cukierman | New bounds on the minimum density of an identifying code for the infinite hexagonal graph grid[END_REF] further improved it to 5/12 = 0.4166.

In this paper, we study king grids, which are strong products of two paths. Given two graphs G and H, the strong product of G and H, denoted by G H, is the graph with vertex set V (G) × V (H) and edge set :

E(G H) = {(a, b)(a, b ) : a ∈ V (G) and bb ∈ E(H)} ∪ {(a, b)(a , b) : aa ∈ E(G) and b ∈ V (H)} ∪ {(a, b)(a , b ) : aa ∈ E(G) and bb ∈ E(H)}.
The two-way infinite path, denoted by P Z , is the graph with vertex set Z and edge set {{i, i + 1} : i ∈ Z}, and the one-way infinite path, denoted by P N , is the graph with vertex set N and edge set {{i, i + 1} : i ∈ N}. A path is a connected subgraph of P Z . In particular, for every positive integer k, the finite path of length k -1, denoted by P k , is the subgraph of P Z induced by {1, 2, . . . , k}.

A king grid is the strong product of two (finite or infinite) paths. The plane king grid is G K = P Z P Z , the half-plane king grid is H K = P Z P N , the quater-plane king grid is Q K = P N P N , and the king strip of height k is K k = P Z P k . Note that every king grid is an induced subgraph of G K .

In 2002, Charon et al. [START_REF] Charon | Identifying Codes with Small Radius in Some Infinite Regular Graphs[END_REF] proved that d * (G K ) is 2/9 = 0.222. They provided the tile depicted in Figure 1, which generates a periodic tiling of the plane with periods (0, 6) and (6, 0), yielding an identifying code C ∞ of the infinite king grid with density 2/9. In 2013, Auger and Honkala investigated properties of watching systems in king grids, which is an extension of the notion of identifying code [START_REF] Auger | Watching Systems in the King Grid[END_REF].

In this paper, we first prove that G K is one king grid with the smallest identifying code density: for every king grid G, d * (G) ≥ 2/9 (Theorem 1). Our proof uses the Discharging Method. See Section 3 of [START_REF] Dantas | Identifying codes for infinite triangular grids with a finite number of rows[END_REF] for a detailed presentation of this technique for identifying codes. The advantage of this method is that it allows us to give better lower bounds for some king grids. We first prove that d * (G) > 2/9 for all finite king grids (Theorem 2). Then we consider king strips. In Section 3, we consider king strips of height at least 7. We prove that d * (K k ) ≥ 2/9 + 8 81k for every k ≥ 7 (Theorem 3). Moreover, we prove that [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]] for every a ∈ Z. In Section 4, we show optimal identifying codes of king strips of height 3, 4, 5 and 6. We prove that d * (K 3 ) = 1/3 = 0.333, d * (K 4 ) = 5/16 = 0.3125, d * (K 5 ) = 4/15 = 0.2666 and d * (K 6 ) = 5/18 = 0.2777 (Theorems 6 to 9). All these results imply that G K , H K and Q K are the unique king grids having an identifying code with density 2/9 = 0.222 (one can easily derive from C ∞ identifying codes with density 2/9 of H K and Q K ).

d * (K k ) ≤ 2/9 + 6/(18k) if k = 3p, d * (K k ) ≤ 2/9 + 8/(18k) if k = 3p + 1, and d * (K k ) ≤ 2/9 + 7/(18k) if k = 3p + 2, for p ∈ N (Theorem 4). Clearly d * (K 1 ) = 1/2 (as K 1 = S 1 = P Z ) and K 2 has no identifying code, since N [(a, 1)] = N [(a,
2 General lower bound for king grids Theorem 1. If G is a (finite or infinite) king grid, then d * (G) ≥ 2/9 = 0.222.

Proof. Let G be a king grid and C an identifying code of G. We set U = V (G) \ C. We shall prove that d(C, G) ≥ 2/9.

We use the Discharging Method. The initial charge of a vertex v is 1 if v ∈ C and 0 otherwise. We then apply some local discharging rules. We shall prove that the final charge of every vertex in G is at least 2/9. This would imply the result.

Given a subset X of vertices in G and an integer 1 ≤ i ≤ 9, we denote by X i (resp. X ≥i , X ≤i ) the set of vertices in X having exactly i vertices (resp. at least i vertices, at most i vertices) in their identifier defined by C. In particular, U 9 is empty. An X-vertex is a vertex in X and an X-neighbour is a neighbour in X.

A vertex is full if its eight neighbours in G K are in G. Otherwise it is a side vertex. Observe that every side vertex has at most five neighbours in G. (ii) Every full C 2 -vertex has at least three neighbours in U ≥3 .

(iii) Every full C 3 -vertex has a neighbour in U ≥3 .

Proof. (i) All neighbours of a C-vertex v have v in their identifier. Since all identifiers are distinct, at most one of them is {v}.

(ii) Let v = (a, b) be a full C 2 -vertex and let w be its C-neighbour. Then v and w have two common neighbours x and y whose identifiers contain {v, w}. Since {v, w} is the identifier of v, it cannot be the one of x or y which, consequently, must be in U ≥3 . Furthermore, by symmetry, we may assume that {(a

+ 1, b -1), (a + 1, b), (a + 1, b + 1)} ∩ {w, x, y} = ∅ and (a + 1, b) / ∈ U 1 .
Thus, by Claim 1.2, there is a vertex in U ≥3 in {(a + 1, b -1), (a + 1, b), (a + 1, b + 1)} which is distinct from x and y.

(iii) Let v = (a, b) be a full C 3 -vertex and let u 1 and u 2 be its two neighbours in C. If a U -neighbour w of v is adjacent to both u 1 and u 2 , then w is in U ≥3 and we have the result. If not, then u 1 and u 2 must be diagonal symmetric with respect to v, i.e. either

{u 1 , u 2 } = {(a -1, b -1), (a + 1, b + 1)} or {u 1 , u 2 } = {(a -1, b + 1), (a + 1, b -1)}.
{(a -1, b -2), (a -2, b -1), (a + 2, b + 1), (a + 1, b + 2)} ⊆ C or {(a + 1, b -2), (a + 2, b -1), (a -2, b + 1), (a -1, b + 2)} ⊆ C. Proof. Let v = (a, b) be a C 1 -vertex.
Its identifier is {v}. Moreover, all its neighbours have an identifier containing v but distinct from {v}. Hence, they are not in U 1 .

Let us no prove that v has at most six neighours in U 2 . If v is a side vertex, then it is trivially true, so we may assume that v is a full vertex. By Claim 1.2 and symmetry, there is a vertex of U ≥3 in each of the sets [START_REF] Charon | Identifying Codes with Small Radius in Some Infinite Regular Graphs[END_REF], the team exists. Moreover, by Claim 1.1, at least two vertices of the team are in C ≥3 . Those vertices are the partners of v (that is, the vertices of the team that are in C ≥3 ).

{(a + 1, b - 1), (a + 1, b), (a + 1, b + 1)}, {(a -1, b -1), (a -1, b), (a -1, b + 1)}, {(a -1, b -1), (a, b -1), (a + 1, b -1)},
{(a + 1, b -2), (a + 2, b -1), (a -2, b + 1), (a -1, b + 2)} ⊆ C. ♦ A defective vertex is a vertex in C 1 with six neighbours in U 2 . Let v = (a, b) be a defective vertex. The team of v is one of the two sets {(a-1, b-2), (a-2, b-1), (a+2, b+1), (a+1, b+2)} and {(a + 1, b -2), (a + 2, b -1), (a -2, b + 1), (a -1, b + 2)} which is included in C. By Claim 1.
Observe that a full C-vertex is partner of at most two defective vertices and a side Cvertex is partner of at most one defective vertex (see Figure 2 and recall that a partner is in

C ≥3 ).
We should apply the following discharging rules.

(R1) Every C-vertex sends 2 9i to each of its neighbours in U i .

(R2) Every defective vertex receives 1 54 from each of its partners.

We shall now prove that the final charge chrg(v) of every vertex v is at least 2/9. We distinguish several cases depending on the set to which v belongs. • Assume first that v ∈ U . There is some i such that v ∈ U i . Then v receives 2 9i from each of its i neighbours in C by (R1). Thus chrg(v) = 2/9.

• Assume that v is a side C-vertex. By Claims 1.4 and 1.3(i), either it is in C 1 and it has three or five neighbours in U ≥2 , or it is in C ≥2 and it has two or four neighbours, with at most one in U 1 . In both cases, v sends at most 5 9 by (R1). Moreover, it is partner of at most one vertex, so it sends at most 1 54 by (R2). Hence chrg(v) ≥ 1

-5 9 -1 54 = 23 54 > 2 9 .
• Assume that v is a full C ≥4 -vertex. It has at most five U -neighbours with at most one in U 1 by Claim 1.3(i). Henceforth it gives at most 2 9 (1 + 4 × 1 2 ) = 2/3 by (R1). Moreover, v is partner of at most two defective vertices, hence it sends at most 1 27 by (R2). Hence chrg

(v) ≥ 1 -2 3 -1 27 = 8 27 > 2 9 .
• Assume that v is a full C 3 -vertex. It has six U -neighbours with at most one in U 1 and at least one in U ≥3 by Claims 1.3(i) and 1.3(iii). Therefore it gives at most 2 9 (1+4× The bound 2/9 of Theorem 1 is best possible because of the infinite king grid G K . From C ∞ , one can also easily derive identifying codes of H K and Q K with density 2/9. However, for the other king grids, one can prove better that the density is larger than 2 9 .

The idea is to prove that there are vertices whose final charge is greater than 2/9. For every vertex v, its excess is exc(v) = chrg(v) -2/9. For a set X of vertices, its excess is exc(X) = x∈X exc(x). We shall prove that some vertices have positive excess. Suppose now that k, ≥ 3. We proceed as in the proof of Theorem 1. Let C be an identifying code of G. We start with the same initial charge and apply the same discharging rules. After applying them, every vertex v has a charge chrg(v) which is at least 2/9. It suffices to prove that a vertex has positive excess at least for some fixed . This would imply d * (G) ≥ 2 9 + k• . To do so we shall prove that there is a side C-vertex or a C ≥3 -vertex. Such a vertex has excess at least 1 27 as shown in the proof of Theorem 1. Suppose for a contradiction that there is no such vertex. Then (1, 1), (1, 2), [START_REF] Auger | Watching Systems in the King Grid[END_REF][START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF] and [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]]. Now by Claim 1.1, one vertex among (2, 2) and w is in C ≥3 , a contradiction.

(2, 1) are not in C. Therefore (2, 2) is in C because C[(1, 1)] = ∅. Moreover, (2, 2) has a neighbour w in C, because C[(1, 1)] = C[(2,

King strips with at least seven rows

The aim of this section is to give better lower bound than 2/9 on the density of identifying codes in king strips of large height. We need some definitions. The b-th row of

K k is R b = {(a, b) : a ∈ Z}. The a-th column of K k is Q k a = {(a, b) : 1 ≤ b ≤ k}.
In the following, we always omit k and just right Q a for the a-th column since k is always fixed and there is no risk of confusion. The bottom of

K k is B = R 1 ∪ R 2 ∪ R 3 , and its top is T = R k ∪ R k-1 ∪ R k-2 .
For every integer a, we set

B[a] = B ∩ (Q a-1 ∪ Q a ∪ Q a+1 ) and T [a] = T ∩ (Q a-1 ∪ Q a ∪ Q a+1 ). Theorem 3. For every k ≥ 7, d * (K k ) ≥ 2 9 + 8 81k .
Proof. We proceed as in the proof of Theorem 1. Fix k ≥ 7. Let C be an identifying code of K k . We start with the same initial charge and apply the same discharging rules. After applying them, every vertex v has a charge chrg(v) which is at least 2/9 and so it has nonnegative excess.

We shall prove that many vertices in the bottom (and top) of K k have positive excess. The following claim is easy. This claim implies that the lower bounds on the excess of C ≥3 -vertices given in Theorem 1 can be increased by 1 54 for such vertices in B because those bounds were considering that a vertex could send 1 27 by (R2), while it sends at most 1 54 . Consequently, we obtain the following.

Claim 3.2. . (i) Every C 3 -vertex in B has excess at least 1 18 .

(ii) Every C 4 -vertex in B has excess at least 5 54 .

Claim 3.3. Every vertex in R 2 has a C-neighbour in R 3 .

Proof. The closed neighbourhood of (a, 1) is included in the closed neighbourhood of (a, 2). The identifiers of those two vertices are distinct, thus there is a

C-vertex in C[(a, 2)] \ C[(a, 1)] which necessarily is in R 3 . ♦ Claim 3.4. If v is a side C-vertex, then exc(v) ≥ 2 9 .
Proof. Let v = (a, 1) be a side vertex.

If v is in C 1 , then it has five U -neighbours with none in U 1 by Claim 1.4. Hence, it gives at most 5 9 by (R1). So exc(v) ≥ 7 9 -5 9 = 2 9 . If v is in C ≥3 , then it has at most three U -neighbours with at most one in U 1 by Claim 1.3(i). Hence it sends at most 4 9 by Rule 1. Moreover, it is partner of at most one vertex, so it sends at most 1 54 by (R2). Thus exc(v)

≥ 7 9 -4 9 -1 54 > 2 9 . If v is in C 2 ,
then it has at least two U -neighbours adjacent to its C-neighbour, and which consequently are in U ≥3 . Therefore v sends at most 2 9 (1

+ 1 2 + 2 × 1 3 ) = 13 27 . Thus exc(v) ≥ 7 9 -13 27 = 8 27 > 2 9 . ♦ Claim 3.5. If (a + j, 1) ∈ U for all j ∈ {-2, -1, 0, 1, 2}, then exc(B[a]) ≥ 4 27 .
Proof. Let a such that (a + j, 1) ∈ U for all j ∈ {-2, -1, 0, 1, 2}.

Assume first that (a, 2) ∈ C. Suppose that (a -1, 3) ∈ C. This vertex has a C-neighbour in R 4 , because its identifier is distinct from the one of (a -1, 2). Moreover (a -1, 2) ∈ U ≥3 and (a, 3) is either in C or in U ≥3 because it has a C-neighbour in R 4 , because its identifier is distinct from the one of (a, 2). In addition, (a -1, 3) is partner of at most one vertex, so it sends at most 1 54 by (R2).

If (a -1, 2) ∈ C,
Thus exc(B[a]) ≥ exc((a -1, 3)) ≥ 7 9 -2 9 (1 + 2 × 1 2 + 2 × 1 3 ) -1 54 = 1 6
. Henceforth, we may suppose that (a -1, 3) / ∈ C, and by symmetry (a + 1, 3) / ∈ C. Thus, by Claim 3.3, (a, 3) ∈ C.

Observe that (a-1, 3), (a, 3) and (a+1, 3) have a neighbour in R 4 because their identifiers are distinct from those of (a -1, 2), (a, 2) and (a + 1, 2) respectively. In particular, (a -1, 3) and (a + 1, 3) are in U ≥4 . Thus (a, 3) is in C ≥3 , has two neighbours in U ≥3 ((a -1, 2) and (a + 1, 2)) and two neighbours in U ≥4 ((a -1, 3) and (a + 1, 3)), is partner of at most one vertex. Hence exc(B[a]) ≥ exc((a, 3))

≥ 7 9 -2 9 (1 + 1 2 + 2 × 1 3 + 2 × 1 4 ) -1 54 = 1 6 .
Assume now that (a, 2) / ∈ C. Since (a, 1) is adjacent to a neighbour in C, we may assume by symmetry that (a-1, 2) ∈ C. We distinguish two subcases depending on whether (a+1, 2) is in C or not.

• Suppose that (a + 1, 2) ∈ C.

Notice that (a, 3) must have a C-neighbour in R 4 , because its identifier is distinct from the one of (a, 2). Thus if (a, 3) ∈ C, then exc((a, 3)) ≥ 5 54 by Claim 3.2(ii). If (a -1, 2) or (a + 1, 2) is in C ≥3 , then it has excess at least 1 18 by Claim 3.2(i), and exc(B[a]) ≥ 5 54 + 1 18 = 4 27 . Henceforth we may suppose that both (a -1, 2) and (a + 1, 2) are in C 2 . This implies that (a -1, 3) and (a + 1, 3) are in U ≥3 because their identifiers are distinct from those of (a -1, 2) and (a + 1, 2). Therefore, exc((a, 3))

≥ 7 9 -2 9 (1 + 1 2 + 3 × 1 3 ) -1 54 = 11 54 ≥ 4 27 . If (a, 3) ∈ C, then w.l.g. (a -1, 3) ∈ C and exc((a -1, 3)) ≥ 7 9 -2 9 (1 + 1 2 + 2 × 1 3 + +2 × 1 4 ) -1 54 = 1 6 ≥ 4 27 . • Suppose that (a + 1, 2) / ∈ C. Then (a + 2, 2) ∈ C because (a + 1, 1) has a C-neighbour and (a -2, 2) ∈ C because C[(a -1, 1)] = C[(a, 1)]. In particular (a -1, 2) ∈ C ≥3
because it has a neighbour in R 3 by Claim 3.3.

If (a -1, 3) ∈ C, then it is in C ≥4 because it has a neighbour in R 4 to have its identifier distinct from the one of (a -1, 2). Hence, by Claim 3.2, exc(B[a]) ≥ 5 54 + 1 18 = 4 27 . Henceforth, we may suppose that (a -1, 3) ∈ U .

Observe that (a, 1) ∈ U 1 , (a -1, 1) ∈ U 2 and (a -2, 1)

∈ U ≥3 because its identifier is distinct from {(a -2, 2, a -1, 2)} = C[(a -1, 1)]. If (a, 3) ∈ C, then (a, 2) ∈ U ≥2 , (a -1, 3) ∈ U ≥4
because it has a neighbour in R 4 to have its identifier distinct from the one of (a -1, 2) and (a -2, 3)

∈ U ≥3 ∪ C because its identifier is distinct from {(a-2, 2, a-1, 2)} = C[(a-1, 1)]. Henceforth exc((a-1, 2)) ≥ 7 9 -2 9 (1 + 2 × 1 2 + 2 × 1 3 + 1 4 ) -1 54 = 1 9
. Moreover (a, 3) has neighbour in R 4 to have its identifier distinct from the one of (a, 2), therefore (a, 3) ∈ C ≥3 and so its excess is at least 1 18 by Claim 3.2(i). Hence exc(B[a]) ≥ 1 9 + 1 18 = 1 6 . Henceforth, we may suppose that (a, 3) ∈ U , and so (a -2, 3) ∈ C.

Necessarily, (a + 1, 3) ∈ C because C[(a, 2)] = C[(a, 1)]. Furthermore, (a + 1, 3) has a neighbour in R 4 to have its identifier distinct from the one of (a + 1, 2). Thus (a + 1, 3) ∈ C ≥3 and its excess is at least 1 18 by Claim 3.2. Then (a -1, 3) ∈ U ≥4 because it has a neighbour in R 4 to have its identifier distinct from the one of (a -1, 2) and (a, 3) ∈ U ≥3 because it has a neighbour in R 4 to have its identifier distinct from the one of (a, 2). Moreover, (a -2, 1) ∈ U ≥3 since it has an identifier distinct from the one of (a -1, 1). Therefore exc((a -1, 2))

≥ 7 9 -2 9 (1 + 2 × 1 2 + 2 × 1 3 + 1 4 ) -1 54 = 1 9 . Hence exc(B[a]) ≥ 1 9 + 1 18 = 1 6 . ♦ Claim 3.6. If (a -1, 1
), (a, 1) and (a + 1, 1) are in U , then exc(B[a]) ≥ 2 27 .

Proof. Assume (a -1, 1), (a, 1) and (a + 1, 1) are in U . Assume first that (a, 2) ∈ C. By Claim 3.3 it has a C-neighbour w in R 3 . By symmetry, we may assume that w ∈ {(a -1, 3), (a, 3)}. By Claim 3.3, there is a C-vertex in {(a, 3), (a + 1, 3), )(a + 2, 3)}, and there must be a C-vertex in {(a -1, 4), (a, 4), )(a + 1, 4)} because C[(a, 3)] = C[(a, 2)]. Consequently, w and (a, 2) cannot be partner of any vertex. Thus the vertex in C 3 among those two vertices has excess 1 18 + 1 54 = 2 27 . Henceforth, we may assume (a, 2) / ∈ C.

Since C[(a, 1)] = ∅, one of (a + 1, 2) and (a -1, 2) is in C. By symmetry, we may assume

(a + 1, 2) ∈ C. Then (a, 3) has a C-neighbour in R 4 , because C[(a, 3)] = C[(a, 2)]. If (a, 3) is in C, then it is in C 3 , so (a + 1, 2) ∈ C 2 because B[a]
has at most one vertex in C 3 . Thus (a -1, 2), (a + 2, 1) and (a + 2, 2) are in U , so C[(a, 1)] = C[(a + 1, 1)] = {(a + 1, 2)}, a contradiction. Hence (a, 3) ∈ U .

Assume that (a + 1, 3) is in C. Since B[a] contains at most one vertex in C 3 , then (a + 2, 2) and (a + 2, 3) are in U . Furthermore, one of {(a + 1, 2), (a + 1, 3)}, say t, is in in C 3 , and the other is in C 2 and has identifier {(a + 1, 2), (a + 1, 3)}. Hence the vertices (a, 2), (a, 3), (a + 2, 2) and (a + 2, 3) are in U ≥3 because their identifiers contain and are different from

{(a + 1, 2), (a + 1, 3)}. Hence exc(B[a]) ≥ exc(t) ≥ 7 9 -2 9 (1 + 1 2 + 4 × 1 3 ) -1 54 = 7
54 . Henceforth, we may assume (a + 1, 3) ∈ U . If (a -1, 2) ∈ C, then symmetrically to the preceding argument, a vertex t in {(a -1, 2), (a -1, 3)} is in C 3 and exc(B[a]) ≥ exc(t) = 7 54 . Henceforth, we may assume (a -1, 2) ∈ U . Now, (a + 2, 1) or

(a + 2, 2) is in C because C[(a + 1, 1)] = C[(a, 1)], and (a + 2, 3) is in C because C[(a + 1, 2)] = C[(a + 1, 1)]. Hence (a + 1, 2) is in C 3 .
In addition, it is the partner of no vertex because (a -1, 3) and (a + 2, 3) are in C. Thus exc(B[a]) ≥ exc((a + 1, 2)) ≥ 1 18

+ 1 54 = 2 27 . ♦
We first apply the following discharging rule.

(R3) Every side C-vertex sends 2 27 to each of its two side neighbours.

Let us denote by exc 3 the excess after applying (R3).

(v) ≥ exc 3 (v) -exc 3 (v) + 1 3k • 8 27 = 8 81k . Thus d(C, K k ) ≥ 2 9 + 8 81k .
Theorem 4. For every k ≥ 7,

d * (K k ) ≤      2 9 + 6 18k , if k ≡ 0 mod 3, 2 9 + 8 18k , if k ≡ 1 mod 3, 2 9 + 7 18k , if k ≡ 2 mod 3.
Proof. Recall the identifying code C ∞ of the infinite king grid in Figure 1:

C ∞ = (6a + 2, 6b +
1), (6a + 4, 6b + 2), (6a + 6, 6b + 2), (6a + 2, 6b + 3), (6a + 5, 6b + 4), (6a + 1, 6b + 5), (6a + 3, 6b + 5), (6a + 5, 6b + 6) a, b ∈ Z .

Let k ≥ 7 be an integer. If k ≡ 0 mod 3 or k ≡ 2 mod 3, let

C k = C ∞ ∩ Z × [k] ∪ (6a + 2, 3), (6a + 5, 3), (6a + 2, k -2), (6a + 5, k -2) a ∈ Z ; if k ≡ 1 mod 3, let C k = C ∞ ∩ Z × {2, . . . , k + 1} ∪ (6a + 2, 4), (6a + 5, 4), (6a + 2, k -1), (6a + 5
, k -1) a ∈ Z .
One can easily check that C k is an identifying code of K k when k ≡ 0 mod 3 or k ≡ 2 mod 3, and that C k is an identifying code of the strip induced by the rows 2 to k + 1 (which is isomorphic to K k ). For an example, C 5 and C 6 are the second identifying codes of Figures 3 and4, respectively (new vertices in black). It is not hard to verify that

d(C k , K k ) =      2 9 + 6 18k , if k ≡ 0 mod 3, 2 9 + 8 18k , if k ≡ 1 mod 3, 2 9 + 7 18k , if k ≡ 2 mod 3.
4 King strips with three, four, five or six rows

Given an integer k ≥ 3 and an identifying code

C of K k , let d(C, R i ) denote the density of C in the row i: d(C, R i ) = lim sup n→∞ 1 2n + 1 • C ∩ {(a, i) : a ∈ Z, |a| ≤ n} . Notice that d(C, K k ) = 1 k k i=1 d(C, R i ).
In order to prove the lower bounds, we first prove the following auxiliary lemma. Lemma 5. Let k ≥ 3 be an integer and let C be an identifying code of

K k . Then d(C, R 1 ) + d(C, R 2 ) ≥ 1/2, d(C, R k ) + d(C, R k-1 ) ≥ 1/2, d(C, R 3 ) ≥ 1/3 and d(C, R k-2 ) ≥ 1/3.
Proof. For every a ∈ Z, C ∩ {(a -1, 3), (a, 3), (a + 1, 3)} = ∅, since, otherwise, (a, 1) and (a, 2) have the same identifier, a contradiction. Then, d(C, R 3 ) ≥ 1/3. Symmetrically, we have

d(C, R k-2 ) ≥ 1/3. Consider now R 1 ∪ R 2 . Set A = {a ∈ Z : C ∩ {(a, 1), (a, 2)} = ∅}, and B = Z \ A.
For each a ∈ A let s(a) be defined as follows. If a -1 ∈ B, then s(a) = a -1, otherwise s(a) = a-3. We now prove that s is an injective mapping from

A into B. If s(a) = a-1, then s(a) ∈ B by definition. If not, then C ∩ {(a -1, 1), (a -1, 2)} = ∅. Hence either (a -2, 1) ∈ C or (a -2, 2) ∈ C because C[(a -1, 1)] = ∅, which implies that a -2 ∈ B. Moreover, since C[(a -2, 1)] = C[(a -1, 1)], then either (a -3, 1) ∈ C or (a -3, 2) ∈ C, so s(a) = a -3 is in B. Then s is injective. Therefore d(C, R 1 ) + d(C, R 2 ) ≥ 1/2. Symmetrically, we have d(C, R k ) + d(C, R k-1 ) ≥ 1/2. Theorem 6. d * (K 5 ) = 4/15 = 0.2666 . . .. Proof. Let C be an identifying code of K 5 . From Lemma 5, we have d(C, R 1 )+d(C, R 2 ) ≥ 1/2, d(C, R 4 ) + d(C, R 5 ) ≥ 1/2 and d(C, R 3 ) ≥ 1/3. Thus d(C, K 5 ) = 1 5 5 i=1 d(C, R i ) ≥ 1 5 ( 1 2 + 1 3 + 1 2 ) = 4/15.
The two periodic identifying codes of K 5 generated by the tiles depicted in Figure 3

Proof.

Let C be an identifying code of K 6 . From Lemma 5, we have

d(C, R 1 ) + d(C, R 2 ) ≥ 1/2, d(C, R 5 ) + d(C, R 6 ) ≥ 1/2, d(C, R 3 ) ≥ 1/3 and d(C, R 4 ) ≥ 1/3. Thus d(C, K 6 ) = 1 6 6 i=1 d(C, R i ) ≥ 1 6 ( 1 2 + 1 3 + 1 3 + 1 2 ) = 5/18.
The two periodic identifying codes of K 6 generated by the tiles depicted in Figure 4 The proofs of the following lemmas of this section use the Discharging Method on the columns. Recall that, with k fixed, Q a is the a-th column of K k for every a ∈ Z. The general idea is to consider any identifying code C of K k and associate to every a ∈ Z the initial charge chrg 0 (a) = |Q a ∩ C|. We will say that a ∈ Z is unsatisfied if chrg(a) is less than a given value q, and satisfied otherwise. Then we apply some local discharging rules (from satisfied a's to unsatisfied a's). Here local means that there is no charge transfer from a satisfied a ∈ Z to an unsatisfied a ∈ Z with |a -a| greater than a given constant. Finally, we prove that, after the discharging, every integer a ∈ Z is satisfied. With this, we obtain that the density of C is at least q/k. Let us now prove d * (K 3 ) ≥ 1/3. Let C be an identifying code of K 3 . For every a ∈ Z, let the initial charge chrg 0 (a) be |Q a ∩ C|. We say that a ∈ Z is satisfied if its current charge is at least 1, and unsatisfied otherwise. We apply the following five discharging rules, Rule i for i = 1 to 5, one after another. We denote by chrg i (a) the charge of a after applying Rule i.

[Rule 1 ≤ i ≤ 5]: every unsatisfied a ∈ Z receives charge 1 from a-i, if chrg i-1 (a-i) ≥ 2.

We shall prove that after applying the discharging rules, every a ∈ Z is satisfied. This yields d(C, K 3 ) ≥ 1/3. Observe that once an integer becomes satisfied, then its remains satisfied.

Consider an initially unsatisfied integer a. Then, Q a ∩ C = ∅. Assume for a contradiction that a is unsatisfied after applying the five discharging rules.

Then |Q a-1 ∩ C| < 2, for otherwise it is satisfied after Rule 1. Therefore, by symmetry, we may assume that we are in one of the following cases:

Q a-1 ∩ C = {(a -1, 2)} (Case 1), Q a-1 ∩ C = {(a -1, 1)} (Case 2) and Q a-1 ∩ C = ∅ (Case 3). Case 1: Q a-1 ∩ C = {(a -1, 2)}. Since C[(a -1, 1)] = C[(a -1, 2)] and C[(a -1, 3)] = C[(a -1, 2)]
, then (a -2, 1), (a -2, 3) ∈ C, hence a receives 1 from a -2 by Rule 2 and is satisfied, a contradiction. Let us now prove d * (K 4 ) ≥ 5/16. Let C be an identifying code of K 4 . For every a ∈ Z, let the initial charge chrg 0 (a) = |Q a ∩ C|. We say that an integer a is satisfied if its charge is at least 5/4, and unsatisfied otherwise. We apply three discharging rules, Rule i for i = 1 to 3 one after another. We denote by chrg i (a) the charge of a after applying Rule i, and we set exc i (a) = chrg i (a) -5/4 (observe that an integer is satisfied if and only if exc(a) ≥ 0).

Case 2: Q a-1 ∩ C = {(a -1, 1)}. Since C[(a -1, 1)] = C[(a -1, 2)], then (a -2, 3) ∈ C.
[Rule 1 ≤ i ≤ 3]: every unsatisfied a ∈ Z receives min{exc i-1 (a -i), -exc i-1 (a)} from a -i, if a -i is satisfied.
We shall prove that after applying the discharging rules, every a ∈ Z is satisfied. This yields d(C, K 4 ) ≥ 5/16. Observe that once an integer becomes satisfied, then its remains satisfied.

Assume for a contradiction that an integer a is unsatisfied after applying the three discharging rules. It was initially unsatisfied so |Q a ∩ C| ≤ 1. By symmetry, we may assume that we are in one of the following cases:

Q a ∩ C = ∅ (Case 1), Q a ∩ C = {(a, 1)} (Case 2), Q a ∩ C = {(a, 2)} (Case 3). Case 1: Q a ∩ C = ∅. In this case, exc 0 (a) = -5/4. First, note that (a -3, 1) ∈ C or (a -3, 2) ∈ C, since C[(a -2, 1)] = C[(a -1, 1)], and (a -3, 3) ∈ C or (a -3, 4) ∈ C, since C[(a-2, 4)] = C[(a-1, 4)].
In particular, exc 0 (a-3) ≥ 3/4. Now |Q a-1 ∩C| ≤ 2, for otherwise a receives 5/4 from a -1 by Rule 1, and is satisfied. Therefore, by symmetry, we are in one of the following seven subcases:

Q a-1 ∩ C = ∅ (Subcase 1.1), Q a-1 ∩ C = {(a -1, 1)} (Subcase 1.2), Q a-1 ∩ C = {(a -1, 2)} (Subcase 1.3), Q a-1 ∩ C = {(a -1, 1), (a -1, 2)} (Subcase 1.4), Q a-1 ∩ C = {(a -1, 1), (a -1, 3)} (Subcase 1.5), Q a-1 ∩ C = {(a -1, 1), (a -1, 4)} (Subcase 1.6), Q a-1 ∩ C = {(a -1, 2), (a -1, 3)} (Subcase 1.7). Subcase 1.1: Q a-1 ∩ C = ∅. Since C[(a -1, 1)] = C[(a -1, 2)] and C[(a -1, 4)] = C[(a -1, 3)], then (a -2, 2), (a -2, 3) ∈ C. Since C[(a -1, 2)] = C[(a -1, 3)], then (a -2, 1) ∈ C or (a -2, 4) ∈ C.
In addition |Q a-2 ∩ C| = 4, for otherwise exc 0 (a -2) = 11/4 , so a -2 sends 5/4 to a -1 by Rule 1 and 5/4 to a by Rule 2, and a is satisfied. By symmetry, we may assume (a -2, 1) ∈ C and (a -2, 4) ∈ C. Thus exc 0 (a -2) = 7/4 and so a -2 sends 5/4 to a -1 by Rule 1 and sends 1/2 to a by Rule 2. Moreover, a -3 sends charge 1/2 to a by Rule 3, and so a is satisfied, a contradiction.

Subcase 1.2: Q a-1 ∩ C = {(a -1, 1)}. Since C[(a -1, 1)] = C[(a -1, 2)] and C[(a -1, 4)] = C[(a -1, 3)], then (a -2, 2), (a -2, 3) ∈ C. In addition, |Q a-2 ∩ C| ≤ 2 for otherwise exc 0 (a -2) ≥ 7
4 , so a -2 sends 1/4 to a -1 by Rule 1, and 5/4 to a by Rule 2 and a is satisfied. Therefore (a -2, 1), (a -2, 4) ∈ C. Consequently a -2 sends 1/4 to a -1 (by Rule 1) satisfying it and sends 1/2 to a by Rule 2. Finally, a -3 sends charge 3/4 to a by Rule 3, and so a is satisfied, a contradiction.

Subcase 1.3: Q a-1 ∩ C = {(a -1, 2)}. Since C[(a -1, 1)] = C[(a -1, 2)], then

Figure 1 :

 1 Figure 1: Tile generating an optimal identifying code of the infinite king grid. Black vertices are those of the code.

Claim 1 . 1 .Claim 1 . 2 .

 1112 Two C 2 -vertices are not adjacent. Proof. Suppose for a contradiction that two C 2 -vertices u and v are adjacent. Then C[u] = C[v] = {u, v}, a contradiction. ♦ If (a, b) ∈ C, {(a + 1, b -1), (a + 1, b), (a + 1, b + 1)} ⊆ U and (a + 1, b) / ∈ U 1 , then at least one vertex of {(a + 1, b -1), (a + 1, b), (a + 1, b + 1)} is in U ≥3 . Proof. Suppose (a, b) ∈ C and {(a + 1, b -1), (a + 1, b), (a + 1, b + 1)} ⊆ U . If (a + 1, b) ∈ U 2 , then its identifier is contained in either the identifier of (a + 1, b -1) or the one of (a + 1, b + 1). Hence, one of these two vertices is in U ≥3 . ♦ Claim 1.3. . (i) Every C-vertex has at most one neighbour in U 1 .

  and {(a -1, b + 1), (a, b + 1), (a + 1, b + 1)}. Henceforth, if v has six neighbours in U 2 and thus only two in U ≥3 , then those two neighbours in U ≥3 are either (a -1, b -1) and (a + 1, b + 1) or (a -1, b + 1) and (a + 1, b -1). Assume (a -1, b -1) and (a + 1, b + 1) are the sole neighbours of v in U ≥3 . Then (a -1, b) and (a -1, b + 1) are in U 2 and have distinct identifiers, so the identifier of (a -1, b) is {v, (a -2, b -1)}. In particular, (a -2, b -1) ∈ C. In the same way, we have that (a -1, b -2), (a + 2, b + 1), and (a + 1, b + 2) are in C. Similarly, if (a -1, b + 1) and (a + 1, b -1) are the sole neighbours of v in U ≥3 , we have that

Figure 2 :

 2 Figure 2: The configuration of a defective vertex: v = (a, b) = (3, 3).

Theorem 2 . 1 2

 21 If G is a finite king grid, then d * (G) > 2 9 . Proof. Let G = P P k be a finite grid. If k = 1 or = 1, then one easily sees that d * (G) ≥ and if k = 2 or = 2, then G has no identifying code, so d * (G) = +∞.

Claim 3 . 1 .

 31 A vertex in B is the partner of at most one defective vertex.

  then By Claim 3.3, both (a -1, 2) and (a, 2) have a C-neighbour in R 3 . Moreover, since C[(a, 1)] = C[(a -1, 1)], (a -2, 2) or (a + 1, 2) is in C. If (a -1, 2) ∈ C, then a vertex in {(a -1, 2), (a, 2)} is in C ≥4 and the other in C ≥3 . Thus, by Claim 3.2, exc(B[a]) ≥ 5 54 + 1 18 = 4 27 . Henceforth we may suppose that (a -1, 2) / ∈ C. By symmetry, we may also suppose that (a + 1, 2) / ∈ C. Hence, since the identifiers of (a -1, 1) and (a + 1, 1) are distinct from C[(a, 1)] = {(a, 2)}, necessarily (a -2, 2) and (a + 2, 2) are in C.

= 1 9 .

 9 If B[a] contains a vertex of C ≥4 , then by Claim 3.2, exc(B[a]) ≥ 5 54 , therefore we may assume that all C-vertices of B[a] are in C ≤3 . If B[a] contains two vertices of C 3 , then by Claim 3.2, exc(B[a]) ≥ 2 × 1 18 So we may assume that B[a] has at most one vertex in C 3 .

Claim 3 . 7 .

 37 exc 3 (B[a]) ≥ 4 27 for every integer a. Proof. If (a, 1) ∈ C, then exc 3 (B[a]) ≥ exc((a, 1)) ≥ 2 9 by Claim 3.4. If (a -1, 1) ∈ C, then exc 3 (B[a]) ≥ exc 3 ((a -1, 1)) + exc 3 ((a, 1)) = exc((a -1, 1)) -2 × 2 27 + 2 27 ≥ 4 27 by Claim 3.4. Similarly, if (a + 1, 1) ∈ C, then exc 3 (B[a]) ≥ 4 27 . Henceforth, we assume that (a -1, 1), (a, 1), (a + 1, 1) are in U . If (a -2, 1) and (a + 2, 1) are also in U , then exc 3 (B[a]) = exc(B[a]) ≥ 4 27 by Claim 3.5. If not, say (a -2, 1) ∈ C, then exc 3 (B[a]) ≥ exc(B[a]) + 2 27 because (a -1, 1) receives 2 27 from (a -2, 1) by (R3). Moreover, exc(B[a]) ≥ 2 27 by Claim 3.6, so exc 3 (B[a]) ≥ 4 27 . ♦ We then apply the following rule (R4) For every integer a, every vertex v in B[a] sends 1 3k exc 3 (v) to each vertex in Q a , and every vertex in T [a] sends 1 3k exc 3 (v) to each vertex in Q a . Let exc 4 (v) be the excess of every vertex after (R4). Since k ≥ 7, a vertex v = (a, b) cannot be both in the bottom and the top. Moreover it belongs only to B[a ] for a ∈ {a -1, a, a + 1}. Hence v sends to at most three columns by (R4). Therefore it sends at most exc 3 (v). Moreover every vertex v receives 1 3k (exc 3 (B[a])+exc 3 (T [a])). By Claim 3.7 and symmetry, exc 3 (B[a]) ≥ 4 27 and exc 3 (T [a]) ≥ 4 27 . Hence exc 4

Figure 3 :

 3 Figure 3: Two tiles generating optimal identifying codes of K 5 (density 4/15)

  have density 5/18. Thus d * (K 6 ) = 5/18.

Theorem 8 .

 8 d * (K 3 ) = 1/3.

Figure 4 :Figure 5 : 13 Proof.

 4513 Figure 4: Two tiles generating optimal identifying codes of K 6 (density 5/18)

|Q a- 2 ∩

 2 C| ≤ 1, for otherwise a would receive 1 from a -2 by Rule 2 and be satisfied. So (a -2, 1), (a -2, 2) ∈ C. Since C[(a -2, 1)] = C[(a -1, 1)] = {(a -1, 1)}, then C ∩ {(a -3, 1), (a -3, 2)} = ∅. Moreover, since C[(a -2, 3)] = C[(a -1, 3)] = {(a -2, 3)}, then C ∩ {(a -3, 3), (a -3, 2)} = ∅. In addition, |Q a-3 ∩ C| ≤ 1, for otherwise a would receive 1 from a -3 by Rule 3 and be satisfied. ThusQ a-3 ∩ C = {(a -3, 2)}. Therefore (a -4, 1) ∈ C, since C[(a -3, 2)] = C[(a -3, 3)]. Moreover, {(a -4, 2), (a -4, 3)} ∩ C = ∅, since C[(a -3, 3)] = C[(a -2, 3)] = {(a -2, 3), (a -3, 2)}. Thus |Q(a -4) ∩ C| ≥ 2.Hence a receives 1 from a -4 by Rule 4, and is satisfied, a contradiction.Case 3: Q a-1 ∩ C = ∅. Since C[(a -1, 1)] = C[(a -1, 2)] and C[(a -1, 3)] = C[(a -1, 2)],then (a -2, 1), (a -2, 3) ∈ C. Thus a -1 receives 1 from a -2 by Rule 1 and is satisfied. Now (a -2, 2) / ∈ C, for otherwise a would receive 1 from a -2 by Rule 2 and be satisfied. SinceC[(a -2, 1)] = C[(a -1, 1)] = {(a -2, 1)}, then C ∩ {(a -3, 1), (a -3, 2)} = ∅. Moreover, since C[(a -2, 3)] = C[(a -1, 3)] = {(a -2, 3)}, then C ∩ {(a -3, 3), (a -3, 2)} = ∅.In addition, |Q a-3 ∩ C| ≤ 1, for otherwise a would receive 1 from a -3 by Rule 3 and be satisfied. ThusQ a-3 ∩ C = {(a -3, 2)}. Since C[(a -3, 1)] = C[(a -2, 1)], then C ∩ {(a -4, 1), (a -4, 2)} = ∅. Moreover, since C[(a -3, 3)] = C[(a -2, 3)], then C ∩ {(a -4, 3), (a -4, 2)} = ∅. In addition, |Q a-4 ∩ C| ≤ 1, for otherwise a would receive 1 from a -4 by Rule 4 and be satisfied. Thus Q a-4 ∩ C = {(a -4, 2)}. Since C[(a -4, 1)] = C[(a -4, 2)] and C[(a -4, 3)] = C[(a -4, 2)], then (a -5, 1), (a -5, 3) ∈ C. Hence a receives 1 from a -5 by Rule 5 and is satisfied, a contradiction. Theorem 9. d * (K 4 ) = 5/16.

Figure 6 :

 6 Figure 6: Tile generating an optimal identifying code of K 4 (density 5/16)

  (a -2, 3) ∈ C. Since C[(a -1, 2)] = C[(a -1, 3)], then (a -2, 1) ∈ C or (a -2, 4) ∈ C. If (a -2, 2) ∈ C, then a -2 sends 1/4 to a -1 by Rule 1 and 5/4 to a by Rule 2, so a is satisfied, a contradiction. Thus (a -2, 2) ∈ C. Now a -2 sends 1/4 to a -1 by Rule 1 and 1/2 to a by Rule 2. Moreover, a -3 sends charge 3/4 to a by Rule 3, so a is satisfied, a contradiction.Subcase 1.4: Q a-1 ∩ C = {(a -1, 1), (a -1, 2)}. Observe that a -1 sends 3/4 to a by Rule 1, so exc 1 (a) = -1/2. Since C[(a -1, 1)] = C[(a -1, 2)], we have (a -2, 3) ∈ C. But |C ∩ Q a-2 | ≤ 1,for otherwise a -2 sends 1/2 to a by Rule 2, and a is satisfied. Thus (a -2, 1), (a -2, 2), (a -2, 4) ∈ C. Now a -3 sends 1/4 to a -2 by Rule 1, and 1/2 to a by Rule 3, so a is satisfied, a contradiction. Subcase 1.5: Q a-1 ∩ C = {(a -1, 1), (a -1, 3)}. Then a -1 sends 3/4 to a by Rule 1, soexc 1 (a) = -1/2. Since C[(a-1, 3)] = C[(a-1, 4)], then (a-2, 2) ∈ C. But |C ∩Q a-2 | ≤ 1,for otherwise a-2 sends 1/2 to a by Rule 2, and a is satisfied. Hence (a-2, 1), (a-2, 3), (a-2, 4) ∈ C. Now a -3 sends charge 1/4 to a -2 by Rule 1, and 1/2 to a by Rule 3, so a is satisfied, a contradiction.Subcase 1.6: Q a-1 ∩ C = {(a -1, 1), (a -1, 4)}. Then C[(a -1, 1)] = C[(a -1, 2)] implies (a -2, 3) ∈ C. Moreover C[(a -1, 3)] = C[(a -1, 4)], so (a -2, 2) ∈ C. Thus, a -1 sends 3/4 to a by Rule 1, and a -2 sends 1/2 to a by Rule 2. Hence a is satisfied, a contradiction. Subcase 1.7: Q a-1 ∩ C = {(a -1, 2), (a -1, 3)}. Then a -1 sends 3/4 to a by Rule 1, so exc 1 (a) = -1/2. Moreover, C[(a-1, 2)] = C[(a-1, 3)], so either (a-2, 1) ∈ C or (a-2, 4) ∈ C. By symmetry, we may assume (a -2, 4) ∈ C. But |C ∩ Q a-2 | ≤ 1, for otherwise a -2 sends 1/2 to a by Rule 2, and a is satisfied. Hence (a -2, 1), (a -2, 2), (a -2, 3) ∈ C. Now a -3 sends charge 1/4 to a -2 by Rule 1, and 1/2 to a by Rule 3, so a is satisfied, a contradiction. Case 2: Q a ∩ C = {(a, 1)}. First, note that either (a -3, 3) ∈ C or (a -3, 4) ∈ C, since C[(a -2, 4)] = C[(a -1, 4)]. Moreover |Q a-1 ∩ C| ≤ 1, for otherwise a -1 sends 1/4 to a by Rule 1 and a is satisfied. Hence we are in one of the five subcases:Q a-1 ∩ C = ∅ (Subcase 2.1), Q a-1 ∩ C = {(a -1, 1)} (Subcase 2.2), Q a-1 ∩ C = {(a -1, 2)} (Subcase 2.3), Q a-1 ∩ C = {(a -1, 3)} (Subcase 2.4), Q a-1 ∩ C = {(a -1, 4)} (Subcase 2.5). Subcase 2.1: Q a-1 ∩ C = ∅. Then C[(a -1, 1)] = C[(a -1, 2)] and C[(a -1, 4)] = C[(a -1, 3)], so (a -2, 2), (a -2, 3) ∈ C. But |C ∩ Q a-2 | ≤ 2,for otherwise a -2 sends 5/4 to a -1 by Rule 1, and 1/4 to a by Rule 2, and a is satisfied. Thus (a -2, 1), (a -2, 4) ∈ C. In particular, a -2 sends 3/4 to a -1 by Rule 1, so exc 1 (a -1) = -1/2. Moreover, |C ∩ Q a-3 | ≤ 1, for otherwise a -3 sends 1/2 to a -1 by Rule 2 and 1/4 to a by Rule 3 and a is satisfied. In particular, (a -3, 1), (a -3, 2)∈ C. Now C[(a -2, 2)] = C[(a -1, 3)] = {(a -2, 2), (a -2, 3)} so (a -3, 3) ∈ C, and C[(a -2, 3)] = C[(a -2, 2)] = {(a -2, 2), (a -2, 3), (a -3, 3)}, so (a -3, 4) ∈ C. This contradicts |C ∩ Q a-3 | ≤ 1. Subcase 2.2: Q a-1 ∩ C = {(a -1, 1)}. Then C[(a -1, 1)] = C[(a -1, 2)], so (a -2, 3) ∈ C. Moreover C[(a -1, 3)] = C[(a -1,4)], so (a -2, 2) ∈ C. Thus a -2 sends 1/4 to a -1 by Rule 1 and 1/4 to a by Rule 2. Hence a is satisfied, a contradiction. and a is satisfied. Thus (a -2, 1), (a -2, 2), (a -2, 4) ∈ C. Now C[(a -2, 3)] = C[(a -2, 4)], so (a -3, 2) ∈ C. Hence |C ∩ Q a-3 | ≥ 2. Thus a -3 sends 1/4 to a -2, a -1 and a by Rules 1, 2 and 3, respectively. Hence a is satisfied, a contradiction.

  By symmetry, we may assume that we are in the first case. Now {u 1 , v} is in the identifiers of both (a, b -1) and (a -1, b), hence one of those must be in U ≥3 . ♦ Claim 1.4. Every C 1 -vertex (a, b) has no neighbour in U 1 and at most six neighbours in U 2 . Furthermore, if it has six neighbours in U 2 , then either

Acknowledgments

This research was supported by Funcap [4543945/2016] Pronem, CNPq [425297/2016-0] Universal, ANR (Contract STINT ANR-13-BS02-0007), Funcap/CNRS [083-47.01.00/2013] and CAPES [88887.143992/2017-00] DAAD Probral.

Subcase 2.3: Q a-1 ∩ C = {(a -1, 2)}. Then C[(a -1, 1)] = C[(a -1, 2)], so (a -2, 3) ∈ C. But |C ∩ Q a-2 | ≤ 1, for otherwise a -2 sends 1/4 to a -1 by Rule 1, and 1/4 to a by Rule 2, and a is satisfied. Thus (a -2, 1), (a -2, 2), (a -2, 4) ∈ C. Moreover |C ∩ Q a-3 | ≤ 1 for otherwise a -3 sends 1/4 to a -2, a -1, and a by Rules 1, 2 and 3, respectively, and a is satisfied. In particular, (a -3, 1), (a

for otherwise a -2 sends 1/4 to a -1 by Rule 1 and 1/4 to a by Rule 2, and a is satisfied. Thus, (a -2, 1), (a -2, 3), (a -2, 4) ∈ C. Moreover |C ∩ Q a-3 | ≤ 1 for otherwise a -3 sends 1/4 to a -2, a -1, and a by Rules 1, 2 and 3, respectively, and a is satisfied. In particular, (a -3, 1), (a

thus a -2 sends 1/4 to a -1 by Rule 1 and 1/4 to a by Rule 2. Hence a is satisfied, a contradiction.

for otherwise a -1 sends 1/4 to a by Rule 1 and a is satisfied. Hence we are in one of the five subcases:

for otherwise a -2 sends 1/4 to a -1 by Rule 1 and 1/4 to a by Rule 2, and a is satisfied. Thus (a -2, 1), (a -2, 2), (a -2, 4)

Thus a -3 sends 1/4 to a -2, a -1 and a by Rules 1, 2 and 3, respectively. Hence a is satisfied, a contradiction.

With this, a -2 satisfies a -1 and a sends charge 1/4 to them in Rules 1 and 2, respectively, and we are done.


Amir Krifa
email: amir.krifa@sophia.inria.fr

Chadi Barakat
email: chadi.barakat@sophia.inria.fr

Thrasyvoulos Spyropoulos
email: spyropoulos@tik.ee.ethz.ch

Optimal Buffer Management Policies for Delay Tolerant Networks

Delay Tolerant Networks are wireless networks where disconnections may occur frequently due to propagation phenomena, node mobility, and power outages. Propagation delays may also be long due to the operational environment (e.g. deep space, underwater). In order to achieve data delivery in such challenging networking environments, researchers have proposed the use of store-carry-and-forward protocols: there, a node may store a message in its buffer and carry it along for long periods of time, until an appropriate forwarding opportunity arises. Additionally, multiple message replicas are often propagated to increase delivery probability. This combination of long-term storage and replication imposes a high storage overhead on untethered nodes (e.g. handhelds). Thus, efficient buffer management policies are necessary to decide which messages should be discarded, when node buffers are operated close to their capacity.

In this paper, we propose efficient buffer management policies for delay tolerant networks. We show that traditional buffer management drop policies like drop-tail or drop-front fail to consider all relevant information in this context and are, thus, sub-optimal. Using the theory of encounter-based message dissemination, we propose an optimal buffer management policy based on global knowledge about the network. Our policy can be tuned either to minimize the average delivery delay or to maximize the average delivery ratio. Finally, we introduce a distributed algorithm that uses statistical learning to approximate the required global knowledge of the optimal algorithm, in practice. Using simulations based on a synthetic mobility model and real mobility traces, we show that our buffer management policy based on statistical learning successfully approximates the performance of the optimal policy in all considered scenarios. At the same time, our policies outperform existing ones in terms of both average delivery ratio and delivery delay.

I. INTRODUCTION

The traditional view of a network as a connected graph over which end-to-end paths need to be established might not be appropriate for modeling existing and emerging wireless networks. Due to wireless propagation phenomena, node mobility, low power nodes periodically shutting down and waking up, etc, connectivity in many wireless networks is, more often than not, intermittent. Despite this limited or episodic connectivity, many emerging wireless applications could still be supported. Some examples are the low-cost Internet provision in remote or developing communities [START_REF] Jain | Routing in a delay tolerant network[END_REF], [START_REF] Pentland | Daknet: Rethinking connectivity in developing nations[END_REF], vehicular networks (VANETs) for dissemination of location-dependent information (e.g. local ads, traffic reports, parking information, etc) [START_REF] Basu | Networked parking spaces: architecture and applications[END_REF], pocket-switched wireless networks to extend and sometimes bypass access point connectivity to the Internet [START_REF] Papadopouli | Seven degrees of separation in mobile ad hoc networks[END_REF], [START_REF] Motani | Peoplenet: engineering a wireless virtual social network[END_REF], [START_REF] Hui | Pocket switched networks and human mobility in conference environments[END_REF], tactical networks operating in an intermittent fashion for LPI/LPD reasons (low probability of interception and low probability of detection) [START_REF]Disruption tolerant networking[END_REF], underwater networks [START_REF] Heidemann | Research challenges and applications for underwater sensor networking[END_REF], etc.

To enable some services to operate even under these challenging conditions, researchers have proposed a new networking paradigm, often referred to as Delay Tolerant Networking (DTN [START_REF]Delay tolerant networking research group[END_REF]). To route messages in DTNs, Store-carry-andforward protocols are proposed, where a node may store a message in its buffer and carry it along for long periods of time, until it can forward it further. This routing may happen randomly, be based on statistical information [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], or even other relevant information about the destination (e.g. social links, affiliation, etc.). Furthermore, due to the inherent uncertainty caused by the lack of complete (or any) information about other nodes in the network, many replicas of the same message may be propagated to increase probability of delivery.

As one example, one of the first and most popular routing protocols in this context, namely Epidemic routing [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], disseminates a message replica to every node in the network.

Although a large amount of effort has been invested in the design of efficient routing algorithms for DTNs, there has not been a similar focus on buffer management policies. Yet, the combination of long-term storage and the, often extensive, message replication performed by many DTN routing protocols [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF] imposes a high storage overhead on wireless nodes (e.g. small handhelds, sensors, etc.). Moreover, the data units disseminated in this context, called bundles, are self-contained, atomic application-level data units, which can often be large [START_REF]Delay tolerant networking research group[END_REF]. It is evident that, in this context, node buffers will very likely run out of capacity and, thus, efficient buffer management policies are necessary to decide which message(s) should be discarded when a node's buffer is full.

It has been demonstrated that buffer constraints can severely affect the relative and absolute performance of DTN routing schemes and consequently applications. For example, a number of studies have clearly shown that Epidemic routing has minimum delivery delay under no buffer constraints (and no bandwidth constraints), but performs poorly when buffer sizes are limited [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: The multiple-copy case[END_REF], [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]. However, it is less clear what the right buffer management policy is, in this context. For example, the simple drop-tail policy, used in many networks, has been shown to perform poorly in the DTN context [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]. Although some improvement can be achieved, for example, using other policies like drop-front [START_REF] Zhang | Performance modeling of epidemic routing[END_REF], existing policies fail to take into account the intrinsic characteristics and requirements of delay tolerant networking and store-carry-and-forward routing. For example, one of our results in this paper is that the choice of the best message to drop is strongly dependent on the number of copies in the network of the different messages existing in the DTN node's buffer. None of the existing policies takes this network-wide statistics into account.

In this paper, we try to solve this problem in its foundation. We develop a theoretical framework based on Epidemic message dissemination [START_REF] Haas | A new networking model for biological applications of ad hoc sensor networks[END_REF], [START_REF] Groenevelt | Message delay in manet (extended abstract)[END_REF], [START_REF] Spyropoulos | Performance analysis of mobility-assisted routing[END_REF] that takes into account all information that are relevant for encounter-based (or storecarry-and-forward) message delivery. Based on this theory, we first propose an optimal buffer management policy. This policy uses global information about the network either to maximize the average delivery ratio or to minimize the average delivery delay. Then, we propose a distributed (local) algorithm that uses statistical learning in order to estimate information about the global status of the network, and uses this to approximate the optimal algorithm in practice. Finally, to evaluate the performance of the optimal and our statistical learning algorithm against other buffer management policies, we have implemented a DTN framework including all policies in the network simulator NS-2 [START_REF]The network simulator ns-2[END_REF]. We have performed simulations for both the Random Waypoint model and two real-world mobility traces, the ZebraNet trace [START_REF] Wang | Movement data traces from princeton zebranet deployments[END_REF] and the San Francisco's Yellow Cab taxi trace [START_REF]Cabspotting project[END_REF]. Simulation results show that our statistical learning algorithm outperforms other policies achieving closeto-optimal performance, in all considered scenarios. As a final note, our study is conducted in the context of the Epidemic routing scheme [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] due to its simplicity, popularity, and high buffer overhead. Nevertheless, our policies can be applied to other multiple copy routing schemes, as well.

The rest of this paper is organized as follow. Section II describes the framework for our study which includes a general forwarding strategy for which we apply our drop policies and a set of other buffer management policies already proposed in previous works [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF] [START_REF] Zhang | Performance modeling of epidemic routing[END_REF], against which we compare ours. In Section III, we establish theoretically an optimal, "reference" buffer management policy that uses global knowledge about the network. Then, we present in Section IV a learning process that enables us to approximate the global network state required by the reference policy. Section V describes the experimental setup and the results of our performance evaluation. Finally, we summarize our conclusions and discuss future work in Section VI.

II. DELAY-TOLERANT ROUTING AND BUFFER MANAGEMENT POLICIES

In this section, we briefly introduce the basic DTN routing mechanism that we will use throughout the paper, we describe some existing drop policies that we'll compare our policies to, and go over some related work.

A. DTN routing

In the DTN context, when nodes encounter each other they perform pair-wise exchanges of messages with the goal that each message will eventually be delivered to its destination. An index of all messages carried by a node, called summary vector, is kept by each node, and when two nodes meet, they exchange summary vectors [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF]. After this exchange, each node can determine if the peer node has any messages other than the ones stored locally, and based on this it can decide which messages among them to forward to (or to request from) its peer. When no other node is currently within communication range, messages are buffered.

One of the simplest routing protocols that one could implement based on the above mechanism is the Epidemic routing protocol proposed in [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF]. This protocol relies on the theory of Epidemic algorithms, where two nodes always exchange all messages they don't have in common when they encounter each other. Thus, if there is enough buffer space, messages will spread like an "epidemic" through the network, with every node eventually receiving (a copy of) the message 1 . As a result, Epidemic routing uses the maximum amount of resources and causes the highest amount of congestion.

More recently, a number of routing protocols have been proposed, e.g. Spray and Wait [START_REF] Thrasyvoulos Spyropoulos | An efficient routing scheme for intermittently connected mobile networks[END_REF], Prophet [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], and others, that aim at reducing the overhead of Epidemic routing. We have chosen here to base our study on Epidemic routing due to its simplicity, its high buffer requirements, and the fact that it achieves minimum delay if storage is infinite. However, our policies described in Sections III and IV apply to other multiple copy schemes, as well.

B. Buffer management policies

A buffer management policy defines which message to drop if the buffer of a DTN node is full when a new message has to be accommodated. Each message i in the buffer (B messages in total) has a set of information stored with it, S i : the source id, the time since the message was generated, the Time-To-Live (T T L), etc. In the DTN architecture [START_REF] Scott | Bundle protocol specification[END_REF], the T T L value is a timeout value, which specifies when a message is no longer useful and should be deleted. Let now a new message arrive at a buffer that is full. Then, usually, a buffer management policy is a function f (S 1 , S 2 , . . . , S B , S new ) = j ∈ {[1, B] ∪ {new}}. That is, based on the information of all messages in the buffer, it decides on a message to drop among the ones already in the buffer and the new one.

In order to evaluate the performance of our proposed buffer management policies, we have chosen to compare them with a set of existing policies that have been used in related work [START_REF] Lindgren | Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[END_REF]. This set includes: (i) DL-Drop Last (or "Droptail"), the most common used among the set, it simply removes the new received message, (ii) DF-Drop Front, it handles the queue in a FIFO order. The message that was first entered into the queue is the first message to be dropped when the buffer is full, (iii) DO-Drop Oldest, the message with the shortest remaining life time (closest to TTL expiring) is the first to be dropped, and (iv) DY-Drop Youngest, the message with the largest remaining life time is the first to be dropped.

As an additional optimization, we assume that in order to make space for the new received messages a node should not discard one of its own messages (source messages). If all buffered messages are source ones, and the arriving message is also a source message, then we choose to delete the oldest one. Relay messages arriving to a buffer full of source messages are not accepted. The idea of giving priority to source messages has been proposed in [START_REF] Zhang | Performance modeling of epidemic routing[END_REF] and was shown to improve the average delivery ratio.

C. Related work

Several solutions have been proposed to handle routing in DTN. Yet, an important issue that has been largely disregarded by the DTN community is the impact of buffer management policies on the performance of the system. In [START_REF] Zhang | Performance modeling of epidemic routing[END_REF], Zhang et al. present an analysis of buffer-constrained Epidemic routing, and evaluate some of the simple drop policies previously described. The authors conclude that DF outperforms DL in terms of both delivery delay and delivery ratio. Additionally, giving priority to source messages improves the delivery ratio further, but makes messages spread slower, increasing their delay. In [START_REF] Lindgren | Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[END_REF], Lindgren et al. evaluate a somewhat more extensive set of combinations of existing buffer management policies and routing protocols for DTNs. They show that Probabilistic routing [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF] together with the the right buffer management policy can result in performance improvements in terms of message delivery, overhead, and end-to-end delay. Specifically, in the context of Epidemic routing, the authors found that DF (with priority to source messages) gives the highest delivery ratio, while DO gives the smallest end-to-end delay. Our own results supports these findings.

Nevertheless, all the drop policies discussed thus far fail to consider some important information that significantly affects DTN performance, such as the number of replicas already created for a message. To our best knowledge, this is the first work to propose an optimal buffer management policy based on global knowledge about the network, as well as a distributed algorithm that uses statistical learning to approximate the optimal policy.

III. OPTIMAL BUFFER MANAGEMENT POLICY

In this section, we formalize the problem of choosing which message to discard when a node's buffer is full. We first make some assumptions regarding the routing protocol in hand and some generic mobility characteristics of the nodes. Then, we embark on finding theoretically the optimal buffer management policy, GBD (Global Knowledge based Drop), based on global knowledge about the network state. As global knowledge is required, GBD is difficult to be implemented, thus, it will serve as a point of reference. In Section IV, we will show how to design a local buffer management policy that uses learning methods to estimate the global information about the network assumed by GBD, and can approximate the performance of the optimal policy in practice.

A. Problem description (assumptions)

We will assume there are L total nodes in the network. Each of these nodes has a buffer, in which it can store up to B messages in transit, either messages belonging to other nodes or messages generated by itself. Each message is destined to one of the nodes in the network, and has a Time-To-Live (T T L) value. After this timer expires the message is no more useful to the application and should just be dropped by its source and all intermediate nodes.

In the context of DTNs, message transmissions occur only when nodes encounter each other. The minimum time a node has to wait until it can forward a message further, is the time until it encounters another node which can act as a relay. Thus, the time elapsed between node meetings is the basic delay component. This also implies that changes in the nodes' buffers also occur only during node encounters2 . The interencounter time between nodes depends on the value of a particular property of the mobility model assumed, namely the meeting time [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF], [START_REF] Durrett | Probability: Theory and Examples[END_REF] 3 .

Definition III.1. Meeting Time: Let nodes i and j move according to some mobility process and let them start from their stationary distribution at time 0. Let further X i (t) and X j (t) describe the mobility process (position) of nodes i and j, respectively, at time t. The meeting time (U ) between the two nodes is defined as the time it takes them to first come within transmission range (β) of each other, that is

U = min t {t : X i (t) -X j (t) ≤ β}.
To formulate the optimal buffer management policy problem, we do not make any assumption about a specific mobility model used. Our only requirement is that the meeting time of the mobility model is exponentially distributed or has at least an exponential tail, with parameter λ =

1 E[U]
, where E[X] denotes the expectation of a random variable X.

It has been shown that many popular mobility models like Random Walk [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF], Random Waypoint and Random Direction [START_REF] Spyropoulos | Performance analysis of mobility-assisted routing[END_REF], [START_REF] Groenevelt | Message delay in manet (extended abstract)[END_REF], as well as other more sophisticate synthetic models like the community model in [START_REF] Spyropoulos | Performance analysis of mobility-assisted routing[END_REF] have such a property. In practice, there exist some recent studies based on traces collected from real-life mobility [START_REF] Chaintreau | Impact of human mobility on the design of opportunistic forwarding algorithms[END_REF] that argue that intercontact and contact duration times may follow a power-law distribution, instead. Yet, the authors in [START_REF] Thomas Karagiannis | Power law and exponential decay of inter contact times between mobile devices[END_REF] show that even these traces in fact exhibit exponential tails after a cutoff point, and argue that for most mobility models that can be seen as a random walk on a graph, meeting times have an exponential tail. For this reason, we choose to stick with the exponential meeting time assumption, which makes our analysis tractable. Our trace-based evaluation further supports this assumption. Given the above problem setting, a key question to answer is the following: if a node is congested, which message should be dropped so as to optimize a specific routing metric? Our optimal buffer management policy derives a per-message utility, and then drops the message with the smallest utility value. This utility captures the marginal value of a given message copy for the overall routing process, and with respect to the chosen optimization metric. We derive here such a utility for two popular metrics: maximizing the average delivery ratio, and minimizing the average delivery delay.

In Table I, we summarize the various quantities and notations we use throughout the paper.

B. Maximizing the average delivery ratio

We will first look into the following scenario. We assume that a number of messages are propagated in the network using replication (e.g. Epidemic), each of which has a finite T T L value. The source of the message keeps a copy of it during the whole T T L duration, while intermediate nodes are not obliged to do so. We consider a time instant where the network is congested and a new message copy arrives to a new node during an encounter, to find its buffer full. Assuming now that we know all messages in the network and the number of copies for each message at that time, the problem we would like to solve is: what is the best message to be dropped (locally), among the ones already in the buffer of the given node and the newly arrived one, in order to maximize the average delivery ratio among all messages in the network (globally)? The answer is given in the following theorem.

Theorem III.1. Delivery-Ratio: Let us assume that there are K messages in the network, with elapsed time T i for the message i at the moment when the drop decision by the node is to be taken. For each message i ∈ [1, K], let m i (T i ) and n i (T i ) be the number of nodes that have "seen" the message since it's creation4 (excluding the source) and those who have a copy of it at this instant (n i (T i ) m i (T i ) + 1). The local optimal buffer management policy that maximizes the average delivery rate is to drop the message i min satisfying:

i min = argmin i (1 - m i (T i ) L -1 )λR i exp(-λn i (T i )R i ) (1)
Proof: We know that the meeting time between nodes is exponentially distributed with parameter λ. The probability that a copy of a message i will not be delivered by a node is then given by the probability that the next meeting time with the destination is greater than R i . This is equal to exp(-λR i ).

Knowing that message i has n i (T i ) copies in the network, and assuming that the message has not yet been delivered, we can derive the probability that the message itself will not be delivered (i.e. none of the n i copies gets delivered):

P {message i not delivered | not delivered yet} = ni(Ti) i=1 exp(-λR i ) = exp(-λn i (T i )R i ). (2)
Here, we have not taken into account that more copies of a given message may be created in the future through new node encounters (and thus even this policy is to some extent "greedy"). Predicting future encounters and the effect of further replicas created complicates the problem significantly. Nevertheless, the same assumption is performed for all messages equally and thus can justify the relative comparison between the delivery probabilities for different messages.

We should also take into consideration what has happened in the network since the message generation. Since all nodes including the destination have the same chance to see the message, the probability that a message i has been already delivered is equal to:

P {message i already delivered} = m i (T i )/(L -1). (3)
Combining ( 2) and (3) the probability that a message i will get delivered before its T T L expires:

P i = P {message i not delivered yet} * (1 -exp(-λn i (T i )R i )) + P {message i already delivered} = (1 - m i (T i ) L -1 ) * (1 -exp(-λn i (T i )R i )) + m i (T i ) L -1 .
So, if we take at instant t a snapshot of the network, the global delivery rate for the whole network will be:

DR = K(t) i=1 (1 - m i (T i ) L -1 ) * (1 -exp(-λn i (T i )R i )) + m i (T i ) L -1
In case of congestion, a DTN node should take a drop decision, that leads to the best gain in the global delivery ratio DR.

To find the local optimal decision, we differentiate DR with respect to n i (T i ):

∆(DR) = K(t) i=1 ∂Pi ∂ni(Ti) * ni(Ti) = K(t) i=1 (1 - mi(Ti) L -1 )λRi exp(-λni(Ti)Ri) * ni(Ti)
The best drop decision is the one that maximizes ∆(DR). We know that: ∆n i (T i ) = -1 if we drop an already existing message i from the buffer, ∆n i (T i ) = 0 if we don't drop an already existing message i from the buffer and ∆n i (T i ) = +1 if we keep and store the new received message i. Hence, the buffer management policy that maximizes the future delivery rate is the one that drops message i having the smallest value of the following metric:

(1 - m i (T i ) L -1 )λR i exp(-λn i (T i )R i ). (4)
This metric that is minimized over all messages can be viewed as the marginal utility value for a copy of a message i with respect to the total delivery rate. The value of this metric is a function of the global state of the message in the network.

C. Minimizing the average delivery delay

We now turn our attention to minimizing the average delivery delay. We assume that all messages generated have infinite T T L(s) or at least a T T L value large enough to ensure a delivery probability close to 1. (Note that if we assume that every source keeps a copy of its own messages indefinitely, or until it meets the destination, and that this meeting always occurs after finite time, then delivery is guaranteed unless the source buffer overflows.) In this context, we will look for a buffer management policy that minimizes the expected delivery delay over all messages in the network.

Let us denote the delivery delay for message i with random variable X i . Let further D i denote the expected remaining delay for message i: D i is equal to 0 if the message has been delivered already, and equal to E[X i |X i > T i ] if not. Then, the total expected delivery delay (D) for all messages for which copies still exist in the network (or local buffer) is given by,

D = K(t) i=1 Di ⇒ D = K(t) i=1 mi(Ti) L -1 * 0 + (1 - mi(Ti) L -1 ) * E[Xi|Xi > Ti] . (5)
We know that the time until the first copy of the message i reaches the destination follows an exponential distribution with mean 1/(n i (T i )λ). It follows that,

E[X i |X i > T i ] = T i + 1 n i (T i )λ . (6)
Substituting ( 6) in ( 5), we get,

D = K(t) i=1 (1 - m i (T i ) L -1 )(T i + 1 n i (T i )λ
).

Thus, we differentiate D with respect to n i (T i ) to find the policy that maximizes the improvement in D,

∆(D) = K(t) i=1 ∂D i ∂n i (T i ) * ∆n i (T i ) = K(t) i=1 1 n i (T i ) 2 λ ( m i (T i ) L -1 -1) * ∆n i (T i ).
The best drop decision will be the one that maximizes |∆(D)| (or -∆(D)). Hence, it is best to drop the message i that minimizes the following metric,

1 n i (T i ) 2 λ (1 - m i (T i ) L -1 ) (7)
This per-message metric is different than the one for the delivery ratio and can be seen as the utility of a copy of a message i regarding the average delivery delay. Again it is a function of the global state of this message across the network.

IV. USING LEARNING TO APPROXIMATE GLOBAL KNOWLEDGE IN PRACTICE

In order to optimize a specific routing metric using GBD, we need global information about the network and the "spread" of messages. In particular, for each message present in the node's buffer, we need to know the values of m i (T i ) and n i (T i ), the number of nodes that have seen the message and those that have a copy of it. Unfortunately, this is not feasible in practice due to intermittent network connectivity and the long time it takes to flood buffer status information across DTN nodes, which could make such info obsolete. Our proposed solution is to find appropriate estimators for these metrics.

To this end, we have proposed and implemented a learning process which permits a DTN node to gather knowledge about the global network state by making in-band exchanges with other nodes. Each node maintains a list of encountered nodes and the state of each message carried by them, which could be 0 if the message was in the node's buffer or 1 if the message was seen but deleted due to congestion as described in Figure 1. Note that each node maintains the time of the last list update and only sends the list if it has been updated since the last exchange. To reduce the length of the list further, the node can clean the entries corresponding to delivered messages and to those who have expired.

Since the copy information gathered thus for a specific message might take a long time to propagate (as mentioned earlier) and not be enough to correctly infer the current message status, we follow a different route. Rather that looking for the current value of m i (T ) and n i (T ) for a specific message i at an elapsed time T , we look at what happens, on average, for all messages after an elapsed time T . In As a final note, in order to justify our motivation for the history-based learning process described above, we introduce another buffer management policy, FBD (Flood Based Drop). FBD accounts only for the collected information based on messages flooding, that is, without considering past history or other messages. So, from the list (in Fig. 1), DTN nodes extract n i (T i ) value for message i simply by looking for the number of nodes still holding it and the m i (T i ) value by looking for the number of nodes which saw at some past time message i. These values are then plugged into the GBD's delivery ratio and delay metrics as in the case of HBD. Our results from Section V indicate that, unlike HBD, FBD approximates poorly GBD's performance for both metrics, and thus is not sufficient to infer the required information in practice.

A. Calculating estimators

m (T ) for the average delivery ratio metric

When the global information is unavailable, one can calculate the average delivery ratio of a message over all possible values for M (T ) and N (T ), and then try to minimize it. In the framework of the GDB, this is equivalent to choosing the estimators ∧ n (T ) and ∧ m (T ) so that the estimator of the delivery rate is unbiased.

E[(1 - M (T ) L -1 ) * (1 -exp(-λN (T )R i )) + M (T ) L -1 ] = (1 - ∧ m (T ) L -1 ) * (1 -exp(-λ ∧ n (T )R i )) + ∧ m (T ) L -1
By plugging in the metric in ( 4) any values of ∧ n (T ) and ∧ m (T ) that verify this equality, one can be sure that the obtained policy minimizes the average delivery rate. This is exactly our purpose. Suppose now that the best estimator for

E[1 - M (T ) L -1 -(1 - M (T ) L -1 ) exp(-λN (T )R i ) + M (T ) L -1 ] = 1 - - m (T ) L -1 -(1 - - m (T ) L -1 ) exp(-λ ∧ n (T )R i ) + - m (T ) L -1
From this last expression we extract:

∧ n (T ) = - 1 λR i ln( E[(1 -M(T ) L-1 ) exp(-λN (T )R i )] (1 - - m(T ) L-1 )
)

Substituting this last expression into the GBD's delivery rate metric in (4), we get the following metric for HBD,

λR i E[(1 - M (T ) L -1 ) exp(-λR i N (T ))]
Unlike GBD's delivery ratio metric, this new metric is a function only of past history of messages and so can be calculated locally.

B. Calculating estimators

E[(1 - M (T ) L -1 )(T i + 1 N (T )λ )] = (1 - ∧ m (T ) L -1 )(T i + 1 ∧ n (T )λ ) Again, supposing that ∧ m (T ) = - m (T ) = E[M (T )] we get: 1 ∧ n (T )λ - - m (T ) ∧ n (T )λ(L -1) = E[ 1 λN (T ) - M (T ) N (T )λ(L -1) ]
Simplifying this last expression further, we obtain:

∧ n (T ) = L -1- - m (T ) E[ L-1-M(T ) N (T ) ] (9)
By substituting this value in the GBD's delivery delay metric in [START_REF]Disruption tolerant networking[END_REF], we can find the delay metric specific to HBD,

E[ L-1-M(T ) N (T ) ] 2 λ(L -1)(L -1- - m (T ))
Note, that unlike GBD's delivery delay metric, this new metric is function of the locally available history of other messages.

C. On the approximation of

∧ m (T ) by E[M (T )]
In paragraphs IV-A and IV-B, we have supposed that

∧ m (T ) = E[M (T )].
This choice is driven by the observation we made that the histogram of the random variable M (T ) can be approximated by a Gaussian distribution with good accuracy. To confirm this, we have applied the Lillie test [START_REF] Lilliefors | On the kolmogorov-smirnov test for normality with mean and variance unknown[END_REF], a robust version of the well known Kolmogorov-Smirnov goodness-offit test, to M (T ) for different elapsed times (T = 25%,50% and 75% of the T T L). This test leads to acceptance for a 5% significance level. Consequently, the average of M (T ) is at the same time the unbiased estimator and the most frequent value among the vector M (T ).

V. PERFORMANCE EVALUATION

A. Experimental setup

To evaluate our policies, we have implemented a DTN framework into the Network Simulator NS-2. This implementation include the Epidemic routing protocol, the VACCINE mechanism described in [START_REF] Zhang | Performance modeling of epidemic routing[END_REF] to cleanup buffer space after message delivery, and the buffer management policies described in Section II, which will be compared to our policies. Each node uses a wireless communication channel 802.11b that has a range of 100 meters. Our simulations are based on three mobility patterns, a synthetic one, based on the Random Waypoint model and two real-world mobility traces: the first trace was collected as part of the ZebraNet wildlife tracking experiment in Kenya described in [START_REF] Wang | Movement data traces from princeton zebranet deployments[END_REF]. The second mobility trace tracks San Francisco's Yellow Cab taxis. Many cab companies outfit their cabs with GPS to aid in rapidly dispatching cabs to their costumers. The Cabspotting system [START_REF]Cabspotting project[END_REF] talks to the Yellow Cab server and stores the data in a database. We have use an API provided by the Cabspotting system in order to extract mobility traces. Note that this trace describes taxi's positions according to the GPS cylindrical coordinates (Longitude, Latitude) and in order to uses these traces as input for the NS-2 simulator, we have implemented a tool based in the Mercator [START_REF]The mercator projection[END_REF] cylindrical map projection which permit us to convert traces to plane coordinates.

To each source node, we have associated a CBR (Constant Bit Rate) application, which chooses randomly from [0, T T L] the time to start generating messages of 1KB for a randomly chosen destination. Unless otherwise stated, we associate to each node a buffer with a capacity of 10 messages. Finally, we assume that each time two nodes meet, they have enough time (bandwidth) to exchange all data and control messages, so we take into consideration only buffer constraints.

We compare the performance of the various buffer management policies using the following two metrics: the message's average delivery ratio and the delivery delay in the case of infinite T T L. Concerning the evaluation of the HBD policy, we suppose that different nodes are already in a converged state, so we start accounting for HBD's results 2 * T T L seconds after simulation starts. The choice of this value will be justified in paragraph V-D. Note that the results presented here are averages from 20 simulation runs, which is enough to ensure convergence.

B. Performance evaluation for delivery ratio

First, we compare the delivery ratio of all policies for the three scenarios shown in Table II. Figures 2, 3 and4 show respectively the delivery rate based on the Random Waypoint model, the ZebraNet trace, and the Taxi trace. From these plots, it can be seen that the GBD policy gives the best performance for all numbers of sources. When congestion-level decreases, so does the difference between GBD and other policies, as expected. Moreover, the HBD policy outperforms existing policies (DF, DO, DL, DY) and performs very close to GBD. For example, for 30 sources and Random Waypoint mobility, HBD's delivery ratio is 10% higher than Drop Front and only 2% worse than GBD. Similarly, for 40 sources and the ZebraNet traces, HBD delivers 12% more messages than Drop Front and 3% worse than GBD. Finally for the Taxi traces and 40 sources HBD performs 17% better than Drop Front and 3% worse than GBD.

Note that the fact that Drop Front gives a higher delivery ratio than Drop Oldest could be deduced from our delivery rate metric in [START_REF] Papadopouli | Seven degrees of separation in mobile ad hoc networks[END_REF]. Specifically, at an instant t, we have R f ront -R oldest >> |n f ront -n oldest |, which implies that our delivery rate metric gives a smaller value for the message at the front of the queue than for the oldest message. Hence, our metric predicts that dropping the message at the head of the queue will increase the delivery ratio more than dropping the oldest.

In order to justify our motivation for the learning process we also compare our HBD policy explicitly to FBD that uses only collected information per message. Figure 5 shows that when the congestion level increases the difference between FBD and GBD becomes significant, unlike the case of HBD. For example, for 30 CBR sources the difference is about 19% while HBD differs from GBD only by 2%. These results Average delivery rate for Random Waypoint mobility. further underline the importance of the history-based learning process in order to implement GBD in practice.

So far we assumed the same T T L value for all generated messages in different scenarios. In our last scenario, we fix the number of sources to 30 and arrange them in three groups of 10 nodes. Nodes in each group generate messages with TTL values equal to 250, 450 and 650 seconds, respectively. We range here the buffer size from 10 to 35 messages. (Note that in this scenario we start accounting for HBD's results 2 * 650 = 1300 seconds after simulations starts, for convergence.) Figure 6 shows that even for this scenario, HBD outperforms the four existing buffer management policies (DF, DO, DL and DY) and performs close to GBD. For example, for buffer size equal to 10 messages, HBD delivers 14% messages more than Drop Front and 3% messages less than GBD.

C. Performance evaluation for delivery delay

To evaluate the average delivery delay metric, we keep the same simulations durations and messages generation rates as those used for the delivery rate. Figures 7, 8 and 9 depict the average delivery delay for the Random Waypoint model, the ZebraNet trace, and the Taxi trace, respectively. As in the case of delivery ratio, GBD gives the best performance for all three mobility patterns. Moreover, the HBD policy outperforms the four buffer management policies (DF, DO, DL, DY) and performs close to GBD. Specifically, for 30 sources and Random Waypoint mobility, HBD's average delivery delay is 24% better than Drop Oldest and 6% worse than GBD. For the ZebraNet traces, HBD performs 15% better than Drop Oldest and 5% worse than GBD. Finally the highest improvement was observed for the Taxi trace, where HBD performs 29% better than Drop Oldest and only 3% worse than GBD. Once more, the fact that Drop Oldest has smaller delivery delay than Drop Front can be justified based on our delay metric in [START_REF]Disruption tolerant networking[END_REF]. Specifically, in most cases the oldest messages have a greatest number of copies, on average, than the message at the front of the queue. Thus, if we apply our delay metric to the oldest message, we will get a smaller value than for the messages in the front of the queue ( f ront (t) ), which explains why dropping the oldest message gives a smaller average delivery delay than dropping the message in the front of the queue.

Finally, in order to further emphasize on the importance of the learning process we compare again the HBD policy to GND and FBD, in terms of delivery delay also. Figure 10 shows that, when congestion level increases, the difference between FBD and GBD becomes significant which is not the case of HBD. For 30 CBR sources, the difference is 30% while HBD differs from GBD is 6%.

D. HBD's Convergence

In this last part, we look at the time taken by the learning process to converge. We consider the same simulations parameters as in Table II fixing the number of sources to 15. For the HBD policy and for different randomly chosen nodes, Figure 11 shows that as the number of measurements at elapsed time T = 100 increases, the delivery ratio metric's value increases and converges to the average value of the GBD's delivery rate metric, which is equal to 0.17. From Figure 11, one can also extract the convergence times of the delivery rate metric. These values are illustrated in Table III. In Figure 12, we depict similar convergence results for delivery delay. The average delivery delay metric converges to 271, the average value of the HBD's metric. The different convergence times are described in Table IV. These results justify the choice of the time of convergence in V-A. Indeed, in the different simulations scenarios described above, the HBD's metrics take less than 2 * T T L seconds to converge to the GBD's average metrics values for a fixed elapsed time.

VI. CONCLUSION AND FUTURE WORK

In this work, we investigated the problem of buffer management in delay tolerant networks. First, we proposed an optimal buffer management policy based on global knowledge about the network state. Then, we have introduced a distributed algorithm that uses statistical learning to approximate the required global knowledge of the optimal algorithm. Using simulations based on a synthetic mobility model (Random Waypoint), and two real mobility traces (ZebraNet and San Francisco taxi traces), we showed that our buffer management policy based on statistical learning successfully approximates the performance of the optimal algorithm in all considered scenarios. Finally, both policies outperform existing policies with respect to delivery rate and delivery delay, in all considered scenarios.

Note that in this work, we considered that all messages have the same size. It would be interesting to define buffer management policies that take into account different messages sizes. For example, in case of congestion, the end-to-end delay versus message delivery trade-off could be influenced by the choice of dropping several small messages or one large message that occupies the entire node's buffer.

Fig. 1 .

 1 Fig. 1. List maintained by each DTN node.

∧m

  (T ) is its average, i.e., ∧ m (T ) = m (T ) = E[M (T )]. A justification for this assumption will be given in paragraph IV-C. Then, we can calculate ∧ n (T ) as follows:

∧n

  (T ) and ∧ m (T ) for the average delivery delay metric Similar to the case of delivery ratio, we calculate the estimators ∧ n (T ) and ∧ m (T ) in such a way that the average delay estimator is unbiased.

Fig. 2 .

 2 Fig. 2.Average delivery rate for Random Waypoint mobility.

Fig. 3 .

 3 Fig. 3. Average delivery rate for the ZebraNet traces.

Fig. 4 .

 4 Fig. 4. Average delivery rate for the Taxi traces.

Fig. 5 .

 5 Fig. 5. FBD's average delivery rate for the Random Waypoint mobility.

Fig. 6 .

 6 Fig. 6. Average delivery rate for Random Waypoint mobility and different T T L(s).

Fig. 7 .

 7 Fig. 7. average delivery delay for the Random Waypoint mobility.

Fig. 8 .

 8 Fig. 8. average delivery delay for the ZebraNet traces.

Fig. 9 .

 9 Fig. 9. average delivery delay for the Taxi traces.

Fig. 10 .

 10 Fig. 10. HBD's average delivery delay for the Random Waypoint mobility.

Fig. 11 .

 11 Fig. 11.HBD's delivery rate metric convergence for different randomly chosen nodes.

Fig. 12 .

 12 Fig. 12. HBD's delivery delay metric convergence for different randomly chosen nodes.

TABLE I NOTATION

 I

	Variable	Description
	L	Number of nodes in the network
	K(t)	Number of distinct messages in the network at time t
	T T L i	Time To Live for message i
	R i	Remaining Time To Live for message i
	T i = T T L i -	Elapsed Time for message i. It measures the time since
	R i	this message was generated by its source
	n i (T i )	Number of copies of message i in the network after
		elapsed time T

i m i (T i ) Number of nodes (excluding source) that have seen message i since its creation until elapsed time T i λ Meeting rate between two nodes under the given mobility model; λ = 1 E[U ] where E[U ] is the average meeting time

Finite bandwidth and unexpected interruptions may not allow a node to transmit all the messages it would like to forward. In such cases, the order in which messages are transmitted is important. In this work, we will assume that enough bandwidth is available for each contact, and thus buffer space is the only constrain on performance.

One exception is when a message T T L expires while in transit, in which case it is deleted. Nevertheless, this does not affect our model in any part, and so we choose to look at the time instants of encounters only, without loss of generality.

If some of the nodes in the network are static, then one needs to use the hitting time between a mobile node and a static node, instead. For simplicity, we assume here that all nodes are mobile and we refer only to meeting times thereafter. Our theory can be easily modified to account for static nodes.

We say that a node A has "seen" a message i, when A had received a copy of message i sometime in the past, regardless of whether it still has the copy or if it has already removed it from the buffer.

ACKNOWLEDGMENTS

We thank Michal Piorkowski and Wei-Jen Hsu for pointing us out to the San Francisco's taxi cab mobility traces.