Keywords: gathering, personalized broadcasting, grid, interferences, radio networks

In the gathering problem, a particular node in a graph, the base station, aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbor (such an action is called a call). However, a node cannot send and receive a message during the same step. Moreover, the communication is subjet to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most d I from the other caller. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i.e., minimizing the number of steps (called makespan). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints. In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with d I ∈ {0, 1, 2}. In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when d I = 0. If no messages are "close" to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when d I = 0, 4 when d I = 2, and 3 when both d I = 1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting.

Data Gathering and Personalized Broadcasting in Radio Grids with Interferences

Résumé : Dans le problème de la collecte, un sommet particuler (la base) doit recevoir des messages de certains sommets dans un graphe. A chaque étape, un noeud peut envoyer un message à un de ses voisins.

De plus, les communications sont sujettes à des interférences. Le but du problème est de calculer l'ordre des envois pour que la base reçoive tous les messages aussi vite que possible. Le nombre d'étapes d'un ordre est le makespan. Le problème de collecte est équivalent au problème de diffusion personnalisée où la base doit envoyer des messages personnalisés à certains des sommets du graphe, avec les mêmes contraintes d'interférence. Dans cet article, nous considérons ces problèmes dans les grilles et dans le cas où le buffering n'est pas permis. La complexité de calculer le makespan minimum n'est pas connue dans le case des grilles. Nous proposons des algorithmes, pour les cas d'interférences à distance d I ∈ {0, 1, 2}, pour calculer des ordres acceptables (sans collisions de messages) en temps linéaire en le nombre de messages. Nos algorithmes calculent des ordres dont le makespan est à une petite constante de l'optimal. Lorsqu'aucun message n'a une destination "proche" des axes (la base étant l'origine), il s'agit d'une +1 approximation dans le cas d I = 0, d'une +4 approximation dans le cas d I = 2, et, si de plus la base est un coin de la grille, d'une +3 approximation dans le cas d I = 1. Nous prouvons aussi que nos algorithmes sont des approximations avec facteur multiplicatif 2 dans le cas où le buffering est autorisé. Nos résultats améliorent des résultats connus dans la litérature et sont prouvés en termes de diffusion personnalisée.

Mots-clés : calcul formel, base de formules, protocole, différentiation automatique, génération de code, modélisation, lien symbolique/numérique, matrice structurée, résolution de systèmes polynomiaux 1 Introduction

Problem, model and assumptions

In this paper, we study a problem that was motivated by designing efficient strategies to provide internet access using wireless devices [START_REF] Bertin | Accès haut débit en zone rurale: une solution "ad hoc[END_REF]. Typically, several houses in a village need access to a gateway (for example a satellite antenna) to transmit and receive data over the Internet. To reduce the cost of the transceivers, multi-hop wireless relay routing is used. We formulate this problem as gathering information in a Base Station (denoted by BS) of a wireless multi-hop network when interferences constraints are present. This problem is also known as data collection and is particularly important in sensor networks and access networks.

Transmission model

We adopt the network model considered in [START_REF] Bermond | Hardness and approximation of gathering in static radio networks[END_REF][START_REF] Bermond | Gathering with minimum completion time in sensor tree networks[END_REF][START_REF] Bonifaci | Data gathering in wireless networks[END_REF][START_REF] Florens | Lower bounds on data collection time in sensory networks[END_REF][START_REF] Revah | Improved bounds for data-gathering time in sensor networks[END_REF]. The network is represented by a node-weighted symmetric digraph G = (V, E), where V is the set of nodes and E is the set of arcs. More specifically, each node in V represents a device (sensor, station, . . . ) that can transmit and receive data. There is a special node BS ∈ V called the Base Station (BS), which is the final destination of all data possessed by the various nodes of the network. Each node may have any number of pieces of information, or messages, to transmit, including none. There is an arc from u to v if u can transmit a message to v. We suppose that the digraph is symmetric; so if u can transmit a message to v, then v can also transmit a message to u. Therefore G represents the graph of possible communications. Some authors use an undirected graph (replacing the two arcs (u, v) and (v, u) by an edge {u, v}). However calls (transmissions) are directed: a call (s, r) is defined as the transmission from the node s to node r, in which s is the sender and r is the receiver and s and r are adjacent in G. The distinction of sender and receiver will be important for our interference model.

Here we will consider grids as they model well both access networks and also random networks [START_REF] Klasing | From balls and bins to points and vertices[END_REF]. We assume that the time is slotted and that during each time slot, or step a transmission or a call between two nodes can transport at most one message. The network is assumed to be synchronous. We suppose that each device is equipped with an half duplex interface: a node cannot both receive and transmit during a step. This models the near-far effect of antennas: when one is transmitting, it's own power prevents any other signal to be properly received.

Following [START_REF] Florens | Lower bounds on data collection time in sensory networks[END_REF][START_REF] Gargano | Optimally fast data gathering in sensor networks[END_REF][START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF][START_REF] Revah | Improved bounds for data-gathering time in sensor networks[END_REF][START_REF] Zhu | Delay efficient data gathering in sensor network[END_REF] we assume that no buffering is done at intermediate nodes and each node forwards a message as soon as it receives it. One of the rationales behind this assumption is that it frees intermediate nodes from the need to maintain costly state information and message storage.

Interference model We use a binary asymmetric model of interference based on the distance in the communication graph. Let d(u, v) denote the distance, that is the length of a shortest directed path, from u to v in G and d I be an nonnegative integer. We assume that when a node u transmits, all nodes v such that d(u, v) ≤ d I are subject to the interference from u's transmission. We assume that all nodes of G have the same interference range d I . Two calls (s, r) and (s , r ) do not interfere if and only if d(s, r ) > d I and d(s , r) > d I . Otherwise calls interfere (or there is a collision). We will focus on the cases when d I ≤ 2. Note that, if d I > 0, the interference constraints include the fact that a node cannot simultaneously send and receive messages. On the other hand, if d I = 0, the only constraint is that a node cannot receive and send simultaneously, and it can send or receive at most one message per step.

These hypotheses are strong and under the assumption of a centralized view. Moreover the binary interference model is a simplified version of the reality, where the Signal-to-Noise-and-Interferences Ratio (the ratio of the received power from the source of the transmission to the sum of the thermic noise and the received powers of all other simultaneously transmitting nodes) has to be above a given threshold for a transmission to be successful. However, the values of the completion times that we obtain will give lower bounds on the corresponding real life values. Stated differently, if the value of the completion time Inria is fixed, then our results will give upper bounds on the maximum possible number of users ( or messages that can be transmitted) in the network.

Gathering and Personalized broadcasting Our goal is to design protocols that will efficiently, i.e., quickly, gather all messages to the base station BS subject to these interference constraints. More formally, let G = (V, E) be a connected symmetric digraph, BS ∈ V and and d I ≥ 0 be an integer. Each node in V \ BS is assigned a set (possibly empty) of messages that must be sent to BS. The gathering problem consists in computing a multi-hop schedule for each message to arrive the BS under the constraint that during any step any two calls do not interfere within the interference range d I . The completion time or makespan of the schedule is the number of steps used for all messages to reach BS. We are interested in computing the schedule with minimum makespan.

Actually, we will describe the gathering schedule by illustrating the schedule for the equivalent personalized broadcasting problem since this formulation allows us to use a simpler notation and simplify the proofs. In this problem, the base station BS has initially a set of personalized messages and they must be sent to their destinations, i.e., each message has a personalized destination in V , and possibly several messages may have the same destination. The problem is to find a multi-hop schedule for each message to reach its corresponding destination node under the same constraints as the gathering problem. The completion time or makespan of the schedule is the number of steps used for all messages to reach their destination and the problem aims at computing a schedule with minimum makespan. To see that these two problems are equivalent, from any personalized broadcasting schedule, we can always build a gathering schedule with the same makespan, and the other way around. Indeed, consider a personalized broadcasting schedule with makespan T . Any call (s, r) occurring at step k corresponds to a call (r, s) scheduled at step T + 1 -k in the corresponding gathering schedule. Indeed, as the digraph is symmetric, if two calls (s, r) and (s , r ) do not interfere, then d(s, r ) > d I and d(s , r) > d I , so the reverse calls are also compatible. Hence, if there is an (optimal) personalized broadcasting schedule from BS, then there exists an (optimal) solution for gathering at BS with the same makespan. The reverse also holds. Therefore, in the sequel, we consider the personalized broadcasting problem.

Related Work

Gathering problems like the one that we study in this paper have received much recent attention. The papers most closely related to our results are [START_REF] Bermond | Optimal time data gathering in wireless networks with omni-directional antennas[END_REF][START_REF] Bermond | Gathering with minimum completion time in sensor tree networks[END_REF][START_REF] Florens | Lower bounds on data collection time in sensory networks[END_REF][START_REF] Gargano | Optimally fast data gathering in sensor networks[END_REF][START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF][START_REF] Revah | Improved bounds for data-gathering time in sensor networks[END_REF]. Paper [START_REF] Florens | Lower bounds on data collection time in sensory networks[END_REF] firstly introduced the data gathering problem in a model for sensor networks similar to the one adopted in this paper. It deals with d I = 0 and gives optimal gathering schedules for trees. Optimal algorithms for star networks are given in [START_REF] Revah | Improved bounds for data-gathering time in sensor networks[END_REF]. Under the same hypothesis, an optimal algorithm for general networks is presented in [START_REF] Gargano | Optimally fast data gathering in sensor networks[END_REF] in the case each node has exactly one message to deliver. In [START_REF] Bermond | Gathering with minimum completion time in sensor tree networks[END_REF] (resp [START_REF] Bermond | Optimal time data gathering in wireless networks with omni-directional antennas[END_REF]) optimal gathering algorithms for tree networks in the same model considered in the present paper, are given when d I = 1 (resp.,d I ≥ 2).

In [START_REF] Bermond | Optimal time data gathering in wireless networks with omni-directional antennas[END_REF] it is also shown that the Gathering Problem is NP-complete if the process must be performed along the edges of a routing tree for d I ≥ 2 (otherwise the complexity is not determined). Furthermore, for d I ≥ 1 a simple (1 + 2 d I ) factor approximation algorithm is given for general networks. In slightly different settings, in particular the assumption of directional antennas, the problem has been proved NPhard in general networks [START_REF] Revah | Real-time data gathering in sensor networks[END_REF]. The case of open-grid where BS stands at a corner and no messages have destinations in the first row or first column, called axis in the following, is considered in [START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF], where a 1.5-approximation algorithm is presented.

Other related results can be found in [START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF][START_REF] Bermond | Hardness and approximation of gathering in static radio networks[END_REF][START_REF] Bermond | Optimal gathering in radio grids with interference[END_REF][START_REF] Bermond | Optimal gathering algorithms in multi-hop radio tree networks with interferences[END_REF][START_REF] Bonifaci | An approximation algorithm for the wireless gathering problem[END_REF] (see [START_REF] Bonifaci | Data gathering in wireless networks[END_REF] for a survey). In these articles data buffering is allowed at intermediate nodes, achieving a smaller makespan. In [START_REF] Bermond | Hardness and approximation of gathering in static radio networks[END_REF], a 4-approximation algorithm is given for any graph. In particular the case of grids is considered in [START_REF] Bermond | Optimal gathering in radio grids with interference[END_REF], but with exactly one message per node. Another related model can be found in [START_REF] Gomes | Bandwidth allocation in radio grid networks[END_REF], where steady-state (continuous) flow demands between each pair of nodes have to be satisfied, in particular, the authors also study the gathering in radio grid networks.

Our results

In this paper, we propose algorithms to solve the personalized broadcasting problem (and so the equivalent gathering problem) in a grid with the model described above (synchronous, no buffering, one message transmitted by step and binary asymmetric model interference with a parameter d I ). Initially all messages stand at the base station BS and each message has a particular destination node (possibly several messages may be sent to the same node). Our algorithms compute in linear time (in the number of messages) schedules with no calls interfering, with a makespan differing from the lower bound by a small additive constant. We first study the basic instance consisting of an open grid where no messages have destination on an axis, with a BS in the corner of the grid and with d I = 0. This is exactly the same case as that considered in [START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF]. In Section 2 we give a simple lower bound LB. Then in Section 3 we design for this basic instance a linear time algorithm with a makespan at most LB + 2 steps, so obtaining a +2approximation algorithm for the open grid, which greatly improves the multiplicative 1.5 approximation algorithm of [START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF] . Such an algorithm has already been given in the extended abstract [START_REF] Bermond | Minimum delay data gathering in radio networks[END_REF]; but the one given here is simpler and we can refine it to obtain for the basic instance a +1-approximation algorithm. Then we prove in Section 4 that the +2-approximation algorithm works also for a general grid where messages can have destinations on the axis again with BS in the corner and d I = 0. Then we consider in Section 5 the cases d I = 1 and 2. We give lower bounds LB c (1) (when BS is in the corner) and LB(2) and show how to use the +1-approximation algorithm given in Section 3 to design algorithms with a makespan at most LB c (1) + 3 when d I = 1 and BS is in the corner , and at most LB(2) + 4 when d I = 2; however the coordinates of the destinations have in both cases to be at least 2. In Section 6, we extend our results to the case where BS is in a general position in the grid. In addition, we point out that our algorithms are 2-approximation if the buffering is allowed, which improves the result of [START_REF] Bermond | Hardness and approximation of gathering in static radio networks[END_REF] in the case of grids with d I ≤ 2. Finally, we conclude the paper in Section 7. The main results are summarized in Table 1.

Interference

Additional hypothesis Performances without buffering with buffering d I = 0 +2-approximation no messages on axes +1-approximation

d I = 1
BS in a corner and no messages "close" to the axes (see Def. 2) +3-approx. ×1.5-approx. no messages at distance ≤ 1 from an axis ×1.5-approximation d I = 2 no messages at distance ≤ 1 from an axis +4-approx. ×2-approx.

Table 1: Performances of the algorithms designed in this paper. Our algorithms deal with the gathering and personalized broadcasting problems in a grid with arbitrary base station (unless stated otherwise). In this table, +c-approximation means that our algorithm achieves an optimal makespan up to an additive constant c. Similarly, ×c-approximation means that our algorithm achieves an optimal makespan up to an multiplicative constant c.

Notations and Lower bound

In the following, we consider a grid G = (V, E) with a particular node, the base station BS, also called the source. A node v is represented by its coordinates (x, y). The source BS has coordinates (0, 0). We Inria define the axis of the grid with respect to BS, as the set of nodes {(x, y) : x = 0} or {(x, y) : y = 0}.

The distance between two nodes u and v is the length of a shortest directed path in the grid and will be denoted by d(u, v). In particular, d(v, BS) = |x| + |y|.

We consider a set of M > 0 messages that must be sent from the source BS to some destination nodes. Let dest(m) ∈ V denote the destination of the message m. We use d(m) to denote the distance d(dest(m), BS). We suppose that the messages are ordered by non-increasing distance of their destination nodes, and we denote this ordered set

M = (m 1 , m 2 , • • • , m M ) where d(m 1 ) ≥ d(m 2 ) ≥ • • • ≥ d(m M ).
The input of all our algorithms is the number of messages. For simplicity we suppose that the grid is infinite; however it suffices to consider a grid slightly greater than the one containing all the destinations of messages. In particular our work does not include the case of the paths considered in [START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF][START_REF] Florens | Lower bounds on data collection time in sensory networks[END_REF][START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF].

We will use the name of open grid to mean that no messages have destination on an axis that is when all messages have destination nodes in the set {(x, y) : x = 0 and y = 0}.

Note that in our model the source can send at most one message per step. Given a set of messages that must be sent by the source, a broadcasting scheme consists in indicating for each message m the time at which the source sends the message m and the directed path followed by this message. More precisely a broadcasting scheme will be represented by an ordered sequence of messages S = (s 1 , • • • , s k ), where furthermore for each s i we give the directed path P i followed by s i and the time t i at which the source sends the message s i . The sequence is ordered in such a way message s i+1 is sent after message s i , that is we have t i+1 > t i .

As we suppose there is no buffering, a message m sent at step t m is received at step t m = l m +t m -1, where l m is the length of the directed path followed by the message m. In particular t m ≥ d(m)+t m -1. The completion time or makespan of a broadcasting scheme is the step where all the messages have arrived at their destinations. Its value is max m∈M l m + t m -1. In the next proposition we give a lower bound of the makespan: Proposition 1 Given an ordered sequence of messages M = (m 1 , m 2 , • • • , m M ) (i.e., by non-increasing distance), the makespan of any broadcasting scheme is greater than or equal to LB = max i≤M d(m i ) + i -1.

Proof. Consider any personalized broadcasting scheme. For i ≤ M , let t i be the step where the last message in (m 1 , m 2 , • • • , m i ) is sent; therefore t i ≥ i. This last message denoted m is received at step

t i ≥ d(m) + t i -1 ≥ d(m i ) + t i -1 ≥ d(m i ) + i -1 and for every i ≤ M , t i ≥ d(m i ) + i -1. So the makespan is at least LB = max i≤M d(m i ) + i -1.
Note that the proof uses only the fact that the source sends at most one message per step. If there are no interference constraints, in particular if a node can send and receive messages simultaneously, then the bound is achieved by the greedy algorithm where at step i the source sends the message m i of the ordered sequence M through a shortest directed path from BS to dest(m i ).

If there are interferences and d I > 0, we will design in Section 5 some better lower bounds. If d I = 0, then a node cannot send and receive simultaneously and it can send or receive at most one message per step. In this case, we will design in the next two sections linear time algorithms with a makespan at most LB + 2 in the grid with the base station in the corner and a makespan at most LB + 1 when furthermore there is no message with a destination node on the axis (open-grid). In case d I = 0 in open grid, our algorithms are simple in the sense that they use only very simple shortest directed paths and that BS never waits.

Examples. Let us remark that there exist configurations for which no gathering protocol can achieve better makespan than LB + 1. Figure 1(a) represents such a configuration. Indeed, in Figure 1(a), message m i has a destination node v i for i = 1, 2, 3 and LB = 7. However, to achieve the makespan LB = 7 for d I = 0, BS must send the message m 1 to v 1 at step 1 (because v 1 is at distance 7 from BS) and must send message m 2 to v 2 at step 2 (because the message starts after the first step and must be sent to the destination node at distance 6) and these messages should be sent along shortest directed paths. To avoid interferences, the only possibility is that BS sends the first message to node (0, 1), and the second one to the node (1, 0), otherwise the two directed paths will cross at some point. (A formal proof can be obtained from Fact 2 and 3 in Section 3.2.) But then, if we want to achieve the makespan of 7, BS has to send the message m 3 via node (0, 1) and it will reach v 3 at step 7; but the directed paths followed by m 2 and m 3 need to cross and at this crossing point m 3 arrives at a step where m 2 leaves and so the messages interfere. So BS has to wait one step and sends m 3 only at step 4. Then the makespan is 8 = LB + 1.

In addition, there are also examples in which BS has to wait for some steps after sending one message in order to reach the lower bound LB for d I = 0. Figure 1(b) represents such an example. To achieve the lower bound 7, BS has to send messages using shortest directed paths firstly to v 1 via (3, 0) and then consecutively sends messages to v 2 via (0, 4) and v 3 via (2, 0). If BS sends message m 4 at step 4, then m 4 will interfere with m 3 . But, to avoid this interference, BS can send message m 4 at step 5 and will reach v 4 at step 7.

There are also examples in which no schedule using only shortest directed paths achieves the optimal makespan1 . For instance, consider the grid with four messages to be sent to (0, 1), (0, 2), (0, 3) and (0, 4) (all on the first column) and let d I = 0. Clearly, sending all messages through shortest directed paths implies that BS sends messages every two steps. Therefore, it requires 7 steps. On the other hand, the following scheme has makespan 6: send the message to (0, 4) through the unique shortest directed path at step 1; send the message to (0, 3) at step 2 via nodes (1, 0), (1, 1), (1, 2)(1, 3); send the message to (0, 2) through the shortest directed path at step 3 and, finally, send the message to (0, 1) at step 4 via nodes (1, 0), [START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF][START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF]. Note that the optimal makespan is in this example LB + 2.

3 Basic instance:

d I = 0, open-grid,

and BS in the corner

In this section we study simple configurations called basic instances. A basic instance is a configuration where d I = 0, messages are sent in the open grid (no destinations on the axis) and BS is in the corner (node with degree 2 in the grid). We will see that we can find personalized broadcasting algorithms using a basic scheme, where each message is sent via a simple shortest directed path (with one horizontal and one vertical segment) and where the source sends a message at each step (it never waits) and achieving a makespan of LB + 1.

Basic schemes

A message is said to be sent horizontally to its destination v = (x, y) (x > 0, y > 0), if it goes first horizontally then vertically, that is if it follows the shortest directed path from BS to v passing through (x, 0). Correspondingly, the message is sent vertically to its destination v = (x, y), if it goes first vertically then horizontally, that is if it follows the shortest directed path from BS to v passing through (0, y) Definition 1 [basic scheme] A basic scheme is a broadcasting scheme where BS sends a message at each step alternating horizontal and vertical sendings. Therefore it is represented by an ordered sequence S = (s 1 , s 2 , . . . , s M ) of the M messages with the properties: message s i is sent at step i and furthermore s i is sent horizontally or vertically in such a way that if s i is sent horizontally (resp., vertically) then s i+1 is sent vertically (resp., horizontally).

Notation: Note that, as soon as we fix S and the sending direction D of the first or last message the directed paths used in the scheme are uniquely determined. Hence, the scheme is characterized by the sequence S and the direction D. We will use when needed the notation (S, f irst = D) to indicate a basic scheme where the first message is sent in direction D, where D = H (for horizontally) or D = V (for vertically) and the notation (S, last = D) when the last message is sent in direction D.

Interference of messages

Our aim is to design an admissible basic scheme in which the messages are broadcasted without any collisions. The following simple fact shows that we only need to take care of consecutive sendings. In the following, we say that two messages are consecutive if the source sends them consecutively (one at step t and the other at step t + 1) Fact 1 When d I = 0, in a basic scheme only consecutive messages may interfere.

Proof. Let the message m be sent at step t and the message m at step t ≥ t + 2. Let t + h (h ≥ 0) be a step such that the two messages have not reached their destinations. As we use shortest directed paths the message m is sent on an arc (u, v) with d(v, BS) = d(u, BS)+1 = t +h-t+1, while message m is sent on an arc

(u , v ) with d(v , BS) = d(u , BS)+1 = h+1. Therefore, d(u, v ) ≥ t -t-1 ≥ 1 > 0 = d I and d(u , v) ≥ t -t + 1 ≥ 3 > d I .
Let us now characterize the situations when two consecutive messages interfere in a basic scheme. For that we use the following notation: Notation: In the case d I = 0, if BS sends horizontally the message m at step t and sends vertically the message m at step t = t + 1, we will write (m, m ) ∈ HV if they do not interfere and (m, m ) / ∈ HV if they interfere. Similarly, if BS sends vertically the message m at step t and sends horizontally the message m at step t = t + 1, we will write (m, m ) ∈ V H if they do not interfere and (m, m ) / ∈ V H if they interfere. Proof. Suppose x ≥ x and y < y; then both messages go through the node (x, y ). The message m sent at step t has not reached its destination and so leaves the node (x, y ) at step t + x + y ; but the message m sent at step t + 1 arrives at node (x, y ) at step t + x + y and therefore the two messages interfere.

m m' BS (a) (m, m ) / ∈ HV BS m' m (b) (m, m ) / ∈ V H Figure 2: Cases of interferences
Conversely if x < x or y > y the two directed paths used for m and m do not cross and so the messages do not interfere. If x ≥ x and y = y, the two directed paths have node (x, y) in common ; but m has this node as final destination and arrives at step t + x + y -1 and message m arrives only at at step t + x + y and so the two messages do not interfere.

Similarly by exchanging H (horizontal) and V (vertical), x and y, we get

Fact 3 Let dest(m) = (x, y) and dest(m ) = (x , y ). Then • (m, m ) / ∈ V H if and only if {x < x and y ≥ y}, or equivalently • (m, m ) ∈ V H if and only if {x ≥ x or y < y}.
Figure 2 shows when there are interferences and also illustrates Fact 2 and 3.

Basic Lemmas

We now prove some simple but useful lemmas. Let dest(m) = (x, y) and dest(m ) = (x , y ).

Lemma 1 • If (m, m ) / ∈ HV , then (m, m ) ∈ V H. • If (m, m ) / ∈ V H, then (m, m ) ∈ HV .
Proof. By Fact 2, if (m, m ) / ∈ HV , then {x ≥ x and y < y} and any of these two properties implies by Fact 3 that (m, m ) ∈ V H. The second claim is obtained similarly.

Note that this lemma is enough to prove the multiplicative 3 2 approximation obtained in [START_REF] Revah | Improved algorithms for data-gathering time in sensor networks ii: Ring, tree and grid topologies[END_REF]. Indeed the source can send two messages every three steps, in the order of M. More precisely, BS sends any pair of messages m 2i-1 and m 2i consecutively by sending the first one horizontally and the second one vertically if (m 2i-1 , m 2i ) ∈ HV , otherwise sending the first one vertically and the second one horizontally if

(m 2i-1 , m 2i ) / ∈ HV (since this implies that (m 2i-1 , m 2i ) ∈ V H).
Then the source does not send anything during the third step. So we can send 2q messages in 3q steps. Such a scheme has makespan at most 3 2 LB.

Lemma 2 • If (m, m ) / ∈ HV , then (m , m) ∈ HV . • If (m, m ) / ∈ V H, then (m , m) ∈ V H.

Inria

Proof. By Fact 2, if (m, m ) / ∈ HV , then {x ≥ x and y < y}. However, y < y implies by Fact 2 that (m , m) ∈ HV ( {x < x or y ≥ y }). The second claim is obtained similarly.

Note that in general there is no equivalence in the lemmas. For example, (m, m ) ∈ HV does not imply (m , m) ∈ V H when x > x and y = y and vice versa (m , m) ∈ V H does not imply (m, m ) ∈ HV when x = x and y < y.

Lemma 3 • If (m, m ) ∈ HV and (m , m ) / ∈ V H, then (m, m ) ∈ HV . • If (m, m ) ∈ V H and (m , m ) / ∈ HV , then (m, m ) ∈ V H.
Proof. By Fact 2, (m, m ) ∈ HV implies either x < x or y ≥ y and by Fact 3, (m , m ) / ∈ V H implies {x < x and y ≥ y }. Therefore either x < x and so x < x or y ≥ y and so y ≥ y which is by Fact 2 equivalent to (m, m ) ∈ HV . The second claim is obtained similarly.

Lemma 4 • If (m, m ) / ∈ HV and (m, m ) / ∈ V H, then (m , m ) ∈ HV . • If (m, m ) / ∈ V H and (m, m ) / ∈ HV , then (m , m ) ∈ V H.
Proof. By Lemma 2 (m, m ) / ∈ HV implies (m , m) ∈ HV . Then we can apply the preceding Lemma 3 with m , m, m in this order to get the result. The second claim is obtained similarly.

Makespan can be approximated up to additive constant 2

Recall that M = (m 1 , . . . , m M ) is the set of messages ordered by non-increasing distance of their destination nodes. Throughout this paper, S S denotes the sequence obtained by the concatenation of two sequences S and S .

In [START_REF] Bermond | Minimum delay data gathering in radio networks[END_REF], we use a basic scheme to design an algorithm for broadcasting the messages in the basic instance with a makespan at most LB + 2. Exactly, we designed a linear-time (in the number of messages) algorithm, to compute an ordering S = (s

1 , • • • , s M ) of M = (m 1 , • • • , m M ) such that s i ∈ {m i-2 , m i-1 , m i , m i+1 ,
m i+2 } for any i ≤ M , and no two consecutive messages interfere.

We give here a different algorithm with similar properties, but easier to prove and which presents two improvements: it can be adapted to hold also when the destinations of the messages can be on the axes (i.e. for general grid) (see Section 4) and it can be refined to give in the basic instance a makespan at most LB + 1. We denote the algorithm by T woApprox[d I = 0, last = D](M); for an input sequence M of messages and a direction D ∈ {H, V }, it gives as output an ordered sequence S of the messages such that the basic scheme (S, last = D) has makespan at most LB + 2. Recall that D is the direction of the last sent message in S in Definition 1.

The algorithm T woApprox[d I = 0, last = D](M) for D = V is given in Figure 3. Case M = 2:

3 if (m 1 , m 2 ) ∈ HV return S = (m 1 , m 2 ) 4 else return S = (m 2 , m 1 ) 5 Case M > 2: 6 let O p = T woApprox[d I = 0, last = V ](m 1 , • • • , m M -2 ) 7 Case 1: if (p, m M -1 ) ∈ V H and (m M -1 , m M ) ∈ HV return O (p, m M -1 , m M ) 8 Case 2: if(p, m M -1 ) ∈ V H and (m M -1 , m M ) / ∈ HV return O (p, m M , m M -1 ) 9 Case 3: if(p, m M -1 ) / ∈ V H and (p, m M ) ∈ HV return O (m M -1 , p, m M ) 10 Case 4: if(p, m M -1 ) / ∈ V H and (p, m M ) / ∈ HV return O (p, m M , m M -1 )
end (i) the basic scheme(S, last = D) broadcasts the messages without collisions;

(ii) the last message is sent in direction D;

(iii) s i ∈ {m i-2 , m i-1 , m i , m i+1 , m i+2 } for any i ≤ M -1, and s M ∈ {m M -1 , m M }.
Proof. We prove the theorem for D = V (vertically). The case D = H (horizontally) can be proved symmetrically. The proof is by induction on M . If M = 1, the result holds obviously as we send m 1 vertically (line 1). If M = 2, either (m 1 , m 2 ) ∈ HV and S = (m 1 , m 2 ) satisfies all properties or (m 1 , m 2 ) / ∈ HV and by Lemma 2 (m 2 , m 1 ) ∈ HV and S = (m 2 , m 1 ) satisfies all properties .

If M > 2. Let O p = T woApprox[d I = 0, last = V ](m 1 , • • • , m M -2 ) be the sequence computed by the algorithm for (m 1 , m 2 , • • • , m M -2 )
. By the induction hypothesis, we may assume that O p satisfies properties (i), (ii) and (iii). So in particular p is sent vertically and p ∈ {m M -3 , m M -2 }. Now we prove that the sequence S = {s 1 , . . . , s M } satisfies properties (i), (ii) and (iii). Property (ii) is clearly satisfied. Property (iii) is also satisfied for s i ,

1 ≤ i ≤ M -3, as it is verified by induction in O; for s M -2 , as either s M -2 = p ∈ {m M -3 , m M -2 } or s M -2 = m M -1 ; for s M -1 , as either s M -1 = p ∈ {m M -3 , m M -2 } or s M -1 = m M -1 or s M -1 = m M and finally for s M , as s M ∈ {m M -1 , m M }.
For property (i) we consider the four cases of the algorithm (lines 7-10). For cases 1, 2 and 4, O p is by induction an admissible basic scheme.

In case 1 by hypothesis (p, m M -1 ) ∈ V H and (m M -1 , m M ) ∈ HV .

In case 2, Lemma 3 with p, m M -1 , m M in this order gives, as

(p, m M -1 ) ∈ V H and (m M -1 , m M ) / ∈ HV that (p, m M ) ∈ V H. Furthermore, by Lemma 2 (m M -1 , m M ) / ∈ HV implies (m M , m M -1 ) ∈ HV .
For case 4, by Lemma 1 (p, m M ) / ∈ HV implies (p, m M ) ∈ V H. Furthermore Lemma 4 applied with p, m M , m M -1 in this order implies (m M , m M -1 ) ∈ HV For case 3, (p, m M ) ∈ HV ; furthermore by Lemma 2 (p, m M -1 ) / ∈ V H implies (m M -1 , p) ∈ V H. It remains to verify that if q is the last message of O, (q, m M -1 ) ∈ HV . As O p is an admissible scheme we have (q, p) ∈ HV and since also (p, m M -1 ) / ∈ V H, by Lemma 3 applied with q, p, m M -1 in this order we get (q, m M -1 ) ∈ HV .

As corollary we get by property (iii) and definition of LB that the basic scheme (S, D) achieves a makespan at most LB + 2. We emphasize this result as a Theorem and note that in view of Example 1 it is the best possible for the algorithm.

Makespan can be approximated up to additive constant 1

In this subsection, we show how to improve Algorithm T woApprox[d I = 0, last = V ](M) in the basic instance (open grid with BS in the corner) to achieve makespan at most LB + 1. For that we will distinguish two cases according to the value of last term s M which can be either m M or m M -1 . In the later case, s M = m M -1 we will also maintain another ordered admissible sequence S of the M -1 messages (m 1 , • • • , m M -1 ) which can be completed in the induction step when S cannot be completed.

We denote the algorithm as OneApprox Case M > 2:

6 let O p = OneApprox[d I = 0, last = V ](m 1 , • • • , m M -2 ) and when p = m M -3 , let O be the ordering of {m 1 , • • • , m M -3 } satisfying (a')(b')(c')(d'). 7 Case 1: if (p, m M -1 ) ∈ V H and (m M -1 , m M ) ∈ HV return S = O (p, m M -1 , m M ) 8 Case 2: if (p, m M -1 ) ∈ V H and (m M -1 , m M ) / ∈ HV return S = O (p, m M , m M -1 ) and S = O (p, m M -1 ) 9 Case 3: if (p, m M -1 ) / ∈ V H and (m M -2 , m M ) ∈ HV 10 Case 3.1: if p = m M -2 return S = O (m M -1 , m M -2 , m M ) 11 Case 3.2: if p = m M -3 return S = O (m M -1 , m M -2 , m M ) 12 Case 4: if (p, m M -1 ) / ∈ V H and (m M -2 , m M ) / ∈ HV 13 Case 4.1: if p = m M -2 return S = O (m M -2 , m M , m M -1 ) and S = O (m M -1 , m M -2 ) 14 Case 4.2: if p = m M -3 return S = O (m M -3 , m M , m M -1 ) and S = O (m M -1 , m M -2 ) end
(c) s i ∈ {m i-1 , m i , m i+1 } for any i ≤ M -1, and s M ∈ {m M -1 , m M }. When s M = m M -1 , it also computes an ordering S = (s 1 , • • • , s M -1 ) of the messages (m 1 , • • • , m M -1 ) satisfying properties (a )-(d ). Let D = H if D = V and D = V if D = H.
(a') the scheme(S , last = D) broadcasts the messages without collisions;

(b') the last message is sent in direction D; Property (b) (resp., (b')) are clearly satisfied for S (resp.S ). Property (c) is also satisfied for s i ,

(c') s i ∈ {m i-1 , m i , m i+1 } for any i ≤ M -2, and s M -1 ∈ {m M -2 , m M -1 }. (d') (s M -1 , m M ) / ∈ DD and if s M -1 = m M -2 , (m M -2 , m M -1 ) / ∈ D D Proof.
1 ≤ i ≤ M -3 as it is verified by induction either in O or in case 3.2 in O . Furthermore, either s M -2 = p ∈ {m M -3 , m M -2 } or s M -2 = m M -1 in case 3. Similarly, s M -1 ∈ {m M -2 , m M -1 , m M } and s M ∈ {m M -1 , m M }. Hence, Property (c) is satisfied. Property (c') is also satisfied for s i , 1 ≤ i ≤ M -3, as it is verified by induction in O or for case 4.2 in O . Furthermore s M -2 ∈ {m M -3 , m M -2 , m M -1 } and s M -1 ∈ {m M -2 , m M -1 }. Hence, Property (c') is satisfied.
Now let us prove that S satisfies property (a) and S properties (a') and (d') in the six cases of the algorithm (lines 7-14).

In cases 1, 2, 3.1, 4.1 the hypothesis and sequence S are exactly the same as that given by Algorithm T woApprox[d I = 0, last = V ](M). Therefore, by the proof of Theorem 1, S satisfies property (a) and so the proof is completed for cases 1 and 3.1 as there are no sequences S .

In case 2, S satisfies (a') as by hypothesis (line 8) (p, m M -1 ) ∈ V H. Property (d') is also satisfied as s M -1 = m M -1 and by hypothesis (line 8) (m M -1 , m M ) / ∈ HV . In case 4.1 (p = m M -2 ), let q be the last element of O; (q, m M -2 ) ∈ HV as O p is admissible. By hypothesis (line 12), (m M -2 , m M -1 ) / ∈ V H and then by Lemma 3 applied with q, m M -2 , m M -1 in this order, we get (q, m M -1 ) ∈ HV ; furthermore, by Lemma As we have seen in Example 2, Algorithms OneApprox[d I = 0, last = V ](M) and OneApprox[d I = 0, last = H](M) are not always optimal since there are instances for which the optimal makespan equals LB while our algorithms only achieves LB + 1. However there are other cases where Algorithm OneApprox[d I = 0, last = V ](M) or Algorithm OneApprox[d I = 0, last = H](M) can be used to obtain an optimal makespan LB. The next theorem might appear as specific, but it includes the case where each node in a finite grid receives exactly one message (case considered in many papers in the literature, such as in [START_REF] Bermond | Optimal gathering in radio grids with interference[END_REF] for the grid with buffering is allowed).

2 , (m M -2 , m M -1 ) / ∈ V H implies (m M -1 , m M -2 ) ∈ V H.
(m M -3 , m M -1 ) / ∈ V H. • If p = m M -3 , by induction hypothesis (d') applied to O , we have (p , m M -2 ) / ∈ HV . Then -(m M -3 , m M -1 ) / ∈ V H implies by Fact 3: {x M -1 < x M -3 and y M -1 ≥ y M -3 } -(m M -3 , m M -2 ) / ∈ HV implies by Fact 2: {x M -2 ≥ x M -3 and y M -2 < y M -3 } So we have x M -1 < x M -3 ≤ x M -2 implying x M -1 < x M -2 and y M -1 ≥ y M -3 > y M -2 implying y M -1 > y M -2 . These conditions imply by Fact 3 that (m M -2 , m M -1 ) / ∈ V H. • If p = m M -4 , by induction hypothesis (d') applied to O , we have (p , m M -2 ) / ∈ HV and (m M -4 , m M -3 ) / ∈ V H. So -(m M -3 , m M -1 ) / ∈ V H implies by Fact 3: {x M -1 < x M -3 and y M -1 ≥ y M -3 } Inria -(m M -4 , m M -2 ) / ∈ HV implies by Fact 2: {x M -2 ≥ x M -4 and y M -2 < y M -4 } -(m M -4 , m M -3 ) / ∈ V H implies by Fact 3: {x M -3 < x M -4 and y M -3 ≥ y M -4 } So we have x M -1 < x M -3 < x M -4 ≤ x M -2 implying x M -1 < x M -2 and y M -1 ≥ y M -3 ≥ y M -4 > y M -2 implying y M -1 > y M -2 . These conditions imply by Fact 3 that (m M -2 , m M -1 ) / ∈ V H.
M -2 , m M , m M -1 in this order we get (m M , m M -1 ) ∈ HV . We claim that (m M -3 , m M -2 ) ∈ V H; indeed, if p = m M -3 , by induction hypothesis (d') applied to O , we have (m M -3 , m M -2 ) / ∈ HV and so (m M -3 , m M -2 ) ∈ V H. If p = m M -4 , by induction hypothesis (d') applied to O , we have (m M -4 , m M -2 ) / ∈ HV and (m M -4 , m M -3 ) / ∈ V H and so by Lemma 4 applied with m M -4 , m M -3 , m M -2 in this order we get (m M -3 , m M -2 ) ∈ V H. Now the property (m M -3 , m M -2 ) ∈ V H combined with the hypothesis line 12 (m M -2 , m M ) / ∈ HV gives by Lemma 3 applied with m M -3 , m M -2 , m M in this order (m M -3 , m M ) ∈ V H.
Theorem 5 Let M = (m 1 , m 2 , • • • , m M )
be an ordered sequence of messages (i.e., by decreasing distance), if the bound LB = max i≤M d(m i ) + i -1 is achieved for only one value of i, then we can design an algorithm with optimal makespan = LB .

Proof. Let k be the value for which LB is achieved that is . m 3 should be sent at step 3. If m 2 was sent at step 1 and so m 1 at step 2, then m 3 should be sent at step 3 via (1, 0) and will interfere with m 1 . Therefore, the only possibility is to send m 1 at step 1 via (0, 1), m 2 at step 2 via (1, 0) and m 3 at step 3 via (0, 1). But then at step 4, we cannot send any of m 4 , m 5 , m 6 without interference. So the source does no sending at step 4, but the last sent message will be sent at step 7 and the makespan will be d+2 = LB +1. However there exists a tricky schedule with makespan LB, but not with shortest directed paths routing. We sent m 1 vertically, m 2 horizontally, m 3 vertically but m 4 with a detour to introduce a delay of 2. More precisely, if v 4 = (x 4 , y 4 ), we send m 4 horizontally till (x 4 + 1, 0), then to (x 4 + 1, 1) and (x 4 , 1) (the detour) and then vertically till (x 4 , y 4 ). Finally we send m 6 vertically at step 5 and m 5 horizontally at step 6. m 4 has been delayed by two but the message arrives at time LB and there is no interference between the messages. In view of this example it seems difficult to characterize what are the instances for which the makespan is LB and those for which the instance is LB + 1. The complexity of determining the value of the minimum makespan is also open. Perhaps the problem would be simpler if we restrict ourselves to use only shortest directed path routings (or basic schemes). We will use this idea of detour in Section 5 to get efficient algorithms for d I ∈ {1, 2}.

d(m k ) + k -1 = LB and d(m i ) + i -1 < LB for i = k. We divide M = (m 1 , • • • , m M ) into two ordered subsequences M k = (m 1 , . . . , m k ) and M k = (m k+1 , . . . , m M ). So |M k | = k and |M k | = M -k. Let S V (resp.
4 Case d I = 0; general grid, and BS in the corner We will see in this section that, by generalizing the notion of basic scheme, Algorithm T woApprox[d I = 0, last = D](M) also achieves a makespan at most LB + 2 in the case of a general grid, that is when the destinations of the messages can be on one or both axes and with BS in the corner. First we have to extend the notions of horizontal sendings for a destination node on Y-axis and vertical sendings for a destination node on the X-axis. However the proof of the basic lemmas is more complicated as Lemma 3 is not fully valid in this case.

We will say that a message is sent "horizontally to reach the Y axis", denoted by H Y -sending, if the destination of m is on the Y axis, i.e., dest(m) = (0, y), and the message is sent first horizontally from BS to (1,0) then it follows the vertical directed path from (1, 0) till (1, y) and finally the horizontal arc ((1, y), (0, y)). Similarly a message is sent "vertically to reach the X axis", denoted by V X -sending, if the destination of m is on the X axis, i.e., dest(m) = (x, 0), and the message is sent first vertically from BS to (0,1) then it follows the horizontal directed path from (0, 1) till (x, 1) and finally the vertical arc ((x, 1), (x, 0)). Notations. Definition 1 of basic scheme in Section 3.1 is extended by allowing H Y (resp., V X )-sendings as horizontal (resp., vertical) sendings. For emphasis, we call it modified basic scheme. Similarly we will use the notation of Section 3.1 (m, m ) ∈ HV (resp., (m, m ) / ∈ HV ) when the message m is sent first horizontally including H Y -sending and the message m is sent at the step just after vertically including V X -sending , and if they do not interfere (resp., if they interfere). We define similarly (m, m ) ∈ V H (resp., (m, m ) / ∈ V H). Note that we cannot have an H Y -sending followed by a V X -sending (or a V X -sending followed by an H Y -sending) as there will be interference in [START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF][START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF]. Proposition 2 Let G be a grid with BS in the corner, d I = 1 and M = (m 1 , m 2 , • • • , m M ) be an ordered sequence of messages (i.e., by non-increasing distance), with all the destinations at distance at least 3 (d(m M ) ≥ 3), then the makespan of any broadcasting scheme is greater than or equal to

BS m' m m'' (a) (m, m ) / ∈ HV case 1; (m, m ) / ∈ HV case 2 BS m' m (b) (m, m ) / ∈ HV case 3 BS m' m m'' (c) (m, m ) / ∈ V H cases 1; (m, m ) / ∈ V H case 2 BS m' m (d) (m, m ) / ∈ V H case 3
LB c (1) = max i≤M d(m i ) + 3i/2 -2.
Proof. First we claim that if the source sends two messages in two concecutive steps t and t + 1, then it cannot send at step t + 2. Indeed suppose the source sends a message m at step t to (1, 0) (the case (0, 1) is identical). If at step t + 1 the source sends a message m , it can be sent only to (0, 1) and message m is forwarded to (2, 0) or (1, 1). If the source sends now a message m at step t + 2, either it is sent to (0, 1) and interferes with m or it is sent to (1, 0) and interferes with m (as d(m) ≥ 3 and the sender of m is at distance 1 from (1, 0)). Let t i be the step where the last message in (D): Finally let us also remark that there exist configurations for which no gathering protocol can achieve better makespan than LB c (1) + 1. Let dest(m 1 ) = v 1 = (x, y), with x + y = d, dest(m 2 ) = v 2 = (x, y -1) and dest(m 3 ) = v 3 = (x -1, y -2). To achieve a makespan of LB c (1) = d, m 1 should be sent at step 1 via a shortest directed path; m 2 should be sent at step 2 via a shortest directed path; and m 3 should be sent at step 4 via a shortest directed path. But, at step d, the sender of m 2 (either (x, y -2) or (x -1, y -1)) is at distance 1 from v 3 = dest(m 3 ) and so m 2 and m 3 interfere. Proof. Indeed if a source sends a message at some step the next message has to be sent at least d I steps after.

(m 1 , m 2 , • • • , m i ) is sent; therefore t i ≥ 3i/2 -1. This last message denoted m is received at step t i ≥ d(m) + t i -1 ≥ d(m i ) + t i -1 ≥ d(m i ) + 3i/2 -2 and for every i ≤ M , LB c (1) ≥ d(m i ) + 3i/2 -2.
Remark 3 For d I = 2, there exist configurations for which no gathering protocol can achieve a better makespan than LB(2) + 2. Let dest(m 1 ) = v 1 = (x, y), with x + y = d and dest(m 2 ) = v 2 = (x -1, y -1). Note that LB(2) = d. Let s 1 , s 2 be the sequence obtained by some algorithm ; to avoid Inria interferences s 1 being sent at step 1 , s 2 should be sent at step ≥ 3. If s 2 = m 1 , the makespan is at least d + 2; Furthermore, if m 1 is not sent via a shortest directed path again the makespan is at least d + 2. So s 1 = m 1 is sent at step 1 via a shortest directed path. At step d the sender of m 1 (either (x, y -1) or (x -1, y) is at distance 1 from v 2 . Therefore, if m 2 is sent at step 3 (resp., 4) it arrives at v 2 (resp.,at a neighbor of v 2 ) at step d and so m 2 interferes with m 1 . Thus, m 2 can be sent in the best case at step 5 and arrives at step d + 2. In all the cases, the makespan of any algorithm is LB(2) + 2.

Routing with -detours

To design the algorithms for d I ∈ {1, 2}, we will use the sequence S obtained by Algorithm OneApprox[d I = 0, f irst = D](M). First, as seen in the proof of lower bounds, the source will no more send a message at each step. Second, we need to send the messages via directed paths more complicated than horizontal or vertical sendings; however we will see that we can use relatively simple directed paths with at most 2 turns and simple detours. Let us define precisely such sendings.

Definition 4

We say that a message to be sent to node (x, y) is sent vertically with an -detour, if it follows the directed path from BS(0, 0) to (0, y + ), then from (0, y + ) to (x, y + ) and finally from (x, y + ) to (x, y). Similarly a message to be sent to node (x, y) is sent horizontally with a -detour, if it follows the directed path from BS(0, 0) to (x + , 0), then from (x + , 0) to (x + , y) and finally from (x + , y) to (x, y).

Note that = 0 corresponds to a message sent horizontally (or vertically) as defined earlier (in that case we will also say that the message is sent without detour). Note also that in the previous section we use directed paths with 1-detour but only to reach vertices on the axes which are now excluded, since we are in open grid. A message sent at step t with a -detour reaches its destination at step t + d(m) + 2 -1. We also note that the detours introduced here are slightly different from the one used in Example 3. They are simpler in the sense that they are doing only two turns and for the case = 1 (1-detour) going backward only at the last step.

We will design algorithms using the sequence obtained by Algorithm OneApprox[d I = 0, f irst = D](M) but we will have to send some of the messages with a 1-detour. We will first give some lemmas which characterize when two messages m and m interfere when d I = 1, but not interfere in the basic scheme that is when d I = 0, according to the detours of their sendings. For that the following fact which gives precisely the arcs used by the messages will be useful.

Fact 6

• If dest(m) = (x, y) and m is sent horizontally at step t with an -detour ( = 0 or 1) then it uses at step t + h the following arc case 1: ((h, 0), (h + 1, 0)) for 0 ≤ h < x + case 2:

((x + , h -(x + )), (x + , h + 1 -(x + )) for x + ≤ h < x + y + case 3: if = 1 ((x + 1, y), (x, y)) for h = x + y + 1 • If dest(m ) = (x , y
) and m is sent vertically with an -detour ( = 0 or 1) at step t , then it uses at step t + h the following arc case 1': ((0, h ), (0, h + 1)) for 0 ≤ h < y + case 2': ((h -(y + ), y + ), (h + 1 -(y + ), y + )) for y + ≤ h < x + y + case 3': if = 1 ((x , y + 1), (x , y )) for h = x + y + 1 each step, including the last step when the messages do a 1-detour, the distance of a sender to the base station increases by one). So we have only to care about s i and s i+1 . First consider the message s 2k+1 . Let s 2k+1 = m, with dest(m) = (x, y) and s 2k+2 = m , with dest(m ) = (x , y ). Message m is sent horizontally at step t = 3k + 1 without detour and m is sent vertically at step t = t + 1 = 3k + 2 with an -detour for = 2k+2 . Furthermore, by Theorem 3, we have (m, m ) ∈ HV . We conclude by Lemma 9 that s 2k+1 and s 2k+2 do not interfere. Now let us prove that s 2k+2 does not interfere with s 2k+3 . Let s 2k+2 = m with dest(m) = (x, y) and s 2k+3 = m with dest(m ) = (x , y ). Message m is sent vertically with an -detour, = 2k+2 at step t = 3k + 2 and m is sent horizontally at step t = t + 2 = 3k + 4. Furthermore by Theorem 3 (m, m ) ∈ V H and so {x ≥ x or y < y} by Fact 3. So we can apply Lemma 12. If {x ≤ x -1 and y = y -1}, we are in the case 00 of Lemma 12 and so if m and m were sent without detour they would interfere. Then by the algorithm we have to choose 2k+2 = 1, but now we are in the case 10 of Lemma 12 which implies no interference. (Case 11 never happens in the Theorem.) Otherwise we have {x > x -1 or y = y -1}; also we have = 0 according to the Theorem. By case 00 of Lemma 12, they do not interfere. The proof works because interferences in case 00 and 10 of Lemma 12 cannot appear simultaneously.

Remark 4 Note that we cannot relax the hypothesis that the messages satisfy y ≥ 2. Indeed if y = 1, we might have to do a 1-detour for m = s 2k+2 when x ≥ x as at any step t + h (2 ≤ h ≤ x) the sender of m is at distance 1 from the receiver of m = s 2k+3 (case 2-1' in the proof). So we have to send m vertically with a 1-detour; but at step t + x + 2 the sender of m (x , 0) is at distance 1 from the receiver of m (x , 1) (case 3-1' in the proof). A simple example is given with 3 messages m 1 , m 2 , m 3 whose destinations are respectively (5, 1), (4, 1), [START_REF] Bermond | Optimal time data gathering in wireless networks with omni-directional antennas[END_REF][START_REF] Bermond | Optimal gathering protocols on paths under interference constraints[END_REF]. Then OneApprox[d I = 0, last = H](M)gives the sequence (m 1 , m 3 , m 2 ), where m 3 = s 2 is sent vertically at step 2 and m 2 = s 3 is sent horizontally at step 3. Now, for d I = 1, m 2 is sent at step 4. If m 3 is sent without detour, it interferes with m 2 at step 4 and 5; otherwise if m 3 is sent with a 1-detour it interferes with m 2 at step 7.

By exchanging x and y, H and V, we also get that when the destination v = (x, y) of any message satisfies {x ≥ 2, y ≥ 1} (condition (1) of 1-open grid) we can adapt our algorithm to compute a generalscheme that broadcasts the messages without collisions for d I = 1 and where the first message is sent in direction V . Furthermore, if we are in a 2-open grid we can have a general-scheme where the direction of the first message is arbitrary.

Theorem 9 In the 1-open grid with BS in the corner and d I = 1, there exists a general-scheme achieving a makespan at most LB c (1) + 3.

Proof. Applying the Algorithm OneApprox[d I = 0, f irst = D](M), we get a ordered sequence S which satisfies the Property (c) of Theorem 3: m i ∈ {s i-1 , s i , s i+1 }. Consider parameters as in Theorem 8 in case of condition (2) of 1-open grid (the proof is similar for condition(1)). Recall that a message m sent at step t with an -detour reaches its destination at step d(m) + 2 + t -1. Then s 2k+1 reaches its destination (the worst case being s 2k+1 = m 2k sent without detour at step 3k + 1)

at step at most d(m 2k ) + 3k + 1 -1 = d(m 2k ) + 3(2k) 2 -2 + 2.
Similarly s 2k+2 reaches its destination (the worst cases being s 2k+2 = m 2k+1 sent with a 1-detour at step 3k + 2)

at step at most d(m 2k+1 ) + 2 + 3k + 2 -1 = d(m 2k+1 ) + 3k + 3 = d(m 2k+1 ) + 3(2k+1) 2 -2 + 3. So the makespan is at most max i≤M d(m i ) + 3i/2 + 1 = LB c (1) + 3.

General-scheme d

I = 2.
In this section, we present a linear-time (in the number of messages) algorithm that computes a generalscheme (Definition 5) broadcasting the messages without collisions for d I = 2 in a 2-open grid, and achieving a makespan up to 4 from the optimal.

As in the case d I = 1, the scheme we propose sends the messages in the same order as in S. However, BS sends one message every two steps (which is necessary when d I = 2). The difficulty here is to decide the detour that must be followed by each message, in order to avoid interference. Next algorithm, described in Figure 8, is dedicated to compute the sequence ( i ) i≤M of the detours. Recall that

D = H if D = V and D = V if D = H. Input: M = (m 1 , • • • , m M ) the set of messages, in a 2-
open grid, ordered in non-increasing distance order and the direction D of the first message.

Output: ε = ( 1 , 2 , . . . , M ) where i ∈ {0, 1} begin 1 Let (s 1 , • • • , s M ) =OneApprox[d I = 0, f irst = D](M) 2
Let t i = 2i -1, and

D i = D if i is odd and D i = D otherwise, for any 1 ≤ i ≤ M 3 Let start with i = 1 for 1 ≤ i ≤ M . 4 for i = M -1 to 1 5
if s i interferes with s i+1 in the general-scheme defined by (s i , t i , D i , i ) i≤M when d I = 2 then (we emphasis that we consider interferences with the current values of the ( i ) i≤M ) Then the general-scheme defined by the sequence (s i , t i , D i , i ) i≤M broadcasts the messages without collisions for d I = 2 and the first message is sent in direction D.

6 i ← 0 7 return ε = ( 1 , 2 , . . . , M ) end
Proof. We need to prove that any two messages do not interfere at any step. A message s i cannot interfere with a message s i+j , for j ≥ 2, sent at least 4 steps after. Indeed, at any step, the senders of two such messages are at distance at least 4. This is because, at each step including the last step when the messages do a 1-detour the distance of a sender to the base station increases by one. So we have only to show that s i does not interfere with s i+1 for any 1 ≤ i < M . For this purpose, we need the following claim that we will prove thanks to Lemma 10 and 12

Claim 3 For d I = 2, if s i sent with an i = 1-detour interferes with s i+1 , then if we send s i without detour, s i does not interfere with s i+1 .

Indeed suppose s i is sent horizontally (resp vertically). As the sequence S is obtained by Algorithm OneApprox[d I = 0, f irst = D](M), (s i , s i+1 ) ∈ HV (resp ∈ V H). So by Lemma 10 (resp. Lemma 12) we are in cases 10 if i+1 = 0 or in case 11 if i+1 = 1. First suppose that we are in case 10, i.e. {x ≥ x and y = y} (resp. {x = x and y ≥ y}). Then we are not in the case 00 of Lemma 10 (resp. Lemma 12). So if we send s i without detour, s i does not interfere with s i+1 . Now assume that we are in case 11, i.e. {x = x -1 and y = y -1} (resp. {x = x -1 and y = y -1}).

Inria

Then we are not in the case 01 of Lemma 10 (resp. Lemma 12). So if we send s i without detour, s i does not interfere with s i+1 . Now the algorithm Epsilon(M, f irst = D) was designed in such a way it gives either i = 1 in which case s i does not interfere with s i+1 or it gives i = 0 because s i sent with a 1 detour was interfering with s i+1 , but then by the claim s i sent without detour does not interfere with s i+1 .

Theorem 11 In the 2-open grid with BS in the corner and d I = 2, the general-scheme defined in Theorem 10 achieves a makespan at most LB(2) + 4.

Proof. By definition of the scheme, the messages are sent in the same order as computed by OneApprox[d I = 0, f irst = D](M). Therefore, by Property (c) of Theorem 3, s i ∈ {m i-1 , m i , m i+1 }. So the message s i arrives at its destination at step d(s

i )+2 i +t i -1 ≤ d(m i-1 )+2+2i-1-1 = d(m i-1 )+2(i-1-1)+4.
Then the result follows from the definition of LB(2).

Personalized Broadcasting in Grid with Arbitrary Base Station

In this section, we show how to use the algorithms proposed above to broadcast (or equivalently to gather) a set of personalized messages M, in a grid with a base station placed in an arbitrary node. More precisely, BS will still have coordinates (0, 0), but the coordinates of the other nodes are in Z. A grid with arbitrary base station is said to be an open-grid if no destination nodes are on the axes. More generally, a grid with arbitrary base station is said to be an 2-open-grid if no destination nodes are at distance at most 1 from any axis.

We divide the grid into four quadrants Q q , 1 ≤ q ≤ 4, where

Q 1 = {(x, y) such that x ≥ 0, y ≥ 0}, Q 2 = {(x, y) such that x ≤ 0, y ≥ 0}, Q 3 = {(x,
y) such that x ≤ 0, y ≤ 0}, and Q 4 = {(x, y) such that x ≥ 0, y ≤ 0}. Note that, BS belongs to all quadrants, and any other node on an axis belongs to two different quadrants.

Each quadrant can be considered itself as a grid with the BS in the corner. Therefore, we can extend all the definitions of the preceding sections, in particular the basic scheme and general-scheme by considering a move in Q 1 (resp., Q 2 , Q 3 , Q 4 ) as horizontal, if it is on the positive x-axis (reps. positive y-axis, negative x-axis, negative y-axis) and a vertical move as one on the other half-axis of the quadrant. Then, if we have a sequence of consecutive messages, still ordered by non-increasing distance to BS, and all in the same quadrant we can apply any of the preceding algorithms. Otherwise, we can extend the algorithms by splitting the sequence of messages into maximal subsequences, where all the messages are in the same quadrant and applying any of the algorithms to this subsequence. We have just to be careful that there is no interference between the last message of a subsequence and the first one of the next subsequence; fortunately we will take advantage of the fact that we can choose the direction of the first message of any subsequence. Proof. We partition the ordered set of messages into maximal subsequences, of messages in the same quadrant. That is M = M 1 M 2 . . . M j . . . M t , where all the messages in M j belong to the same quadrant and the messages of M j and M j+1 belong to different quadrants. Then, depending on the cases of the theorem, we apply Algorithms T woApprox[d I = 0, f irst = D](M), OneApprox[d I = 0, f irst = D](M), or the algorithms defined in Theorems 8 or 10 to each M j , in order to obtain a sequence S j . Now we define the value of D in the algorithms by induction. The direction of the first message of S 1 is arbitrary. Then the direction of the first message of S j+1 has to be chosen on an halfaxis different from that of the last message of S j , which is always possible as two quadrants have at most one half axis in common. For example, suppose the messages of M j belong to Q 1 and the last message of S j is sent vertically (i.e. on the positive y-axis) and that the messages of M j+1 belong to Q 2 , then the first message of S j+1 cannot be sent on the the positive y-axis (that is horizontally in Q 2 ), but should be sent to avoid interferences on the negative x-axis (that is vertically in Q 2 ). Otherwise if the last message of S j is sent horizontally (i.e. on the positive x-axis), we can sent the first message of S j+1 as we want (as the positive x-axis does not belong to Q 2 ); similarly if the messages of M j+1 belong to Q 3 we can send the first message of S j+1 as we want (as there are no half axes in common between Q 1 and Q 3 ). Finally, in the case d I = 2, we have to wait one step between the sending of the last message of S j and the first message of S j+1 . With these restrictions, we have no interferences between two consecutive messages inside the same S j by the correctness of the various algorithms; furthermore we choose the direction of the first message of S j+1 and we add in the case d I = 2 a waiting step in order to avoid interferences between the last message of S j and the first message of S j+1 . Unconsecutive messages are sent far apart to avoid interferences; indeed the distance between two senders is > d I + 1. Finally the values of the makespan follow from that of the respective algorithms.

Note that the values of LB (resp., LB(2)) are lower bounds for the case of an arbitrary position of BS. Therefore, we get the following corollary Corollary 2 There are linear-time (in the number of messages) algorithms that solve the gathering and the personalized broadcasting problems in any grid, achieving an optimal makespan up to an additive constant c where: However, for d I = 1, LB c is not a lower bound when BS is not in the corner; the best lower bound we know is LB. In fact this bound can be achieved in some cases. For example suppose that, in the ordered sequence M, the message m 4j+q belong to the quadrant Q q , then we send the messages m 4j+q horizontally in Q q that is on the positive x-axis for q = 1, on the positive y-axis for q = 2, on the negative x-axis for q = 3, and on the negative y-axis for q = 4. There is no interferences and the makespan is exactly LB. On the opposite, we conjecture that, when all the messages are in the same quadrant, we have a makespan differing of LB c (1) by a small constant so in that case our algorithm will give good approximation.

Remark 5 Note that when buffering is allowed at the intermediate nodes, LB is still a lower bound for the makespan of any personalized broadcasting or gathering scheme. All our algorithms get makespans at most -open grid respectively when buffering is allowed. For the special grid networks, this improves the result in [START_REF] Bermond | Hardness and approximation of gathering in static radio networks[END_REF], which gives a 4-approximation algorithm.

Inria 7 Conclusion and Further Works

In this article we give several algorithms for the personalized broadcasting and so the gathering problem in grids with arbitrary base station. For d I = 0 and d I = 2, our algorithms have makespans very close to the optimum, in fact, differing from the lower bound by some small additive constants. For d I = 1, we have also efficient algorithms, but only when the base station is in a corner. The general case seems to be difficult to solve and depending on the destinations of the messages. It will be nice to have additive approximations for d I ≥ 3; we try to generalize the ideas developed before by using detours with ≥ 2; doing so, we can avoid interferences between consecutive messages, but not with messages s i and s i+2 . Another challenging problem consists in determining the complexity of finding an optimal schedule and routing of messages for achieving the gathering in the minimum completion time or characterizing when the lower bound is achieved. Example 3 shows it might not be an easy problem. Determining if there is a polynomial algorithm to compute the makespan in the restricted case where messages should be sent via shortest directed paths seems also to be a challenging problem. Last but not least, a natural extension will be to consider the gathering problem for other network topologies.

  Configuration when the trivial lower bound cannot be achieved.

  BS has to wait for one step to achieve the trivial lower bound.

Figure 1 :

 1 Figure 1: Two particular configurations

Fact 2

 2 Let dest(m) = (x, y) and dest(m ) = (x , y ). Then • (m, m ) / ∈ HV if and only if {x ≥ x and y < y}, or equivalently • (m, m ) ∈ HV if and only if {x < x or y ≥ y}.

Remark 1 Example 1

 11 We emphasize the fact that the direction D ∈ {H, V } (horizontal or vertical) of the last sent message actually is a parameter of the algorithm. Although we only present the case for D = V in the following algorithm, the other case for D = H, algorithm T woApprox[d I = 0, last = H](M) can easily be obtained by symmetry. Given the parity of the number of messages to be sent, it also determines the direction of the first message and therefore we also get an algorithm T woApprox[d I = 0, f irst = D](M) with the same properties, but the first message is sent in direction D. Consider the example of Figure4(a). The destinations of the messages m i (1 ≤ i ≤ 6) are v 1 = (7, 3), v 2 = (7, 1), v 3 = (3, 3), v 4 = (2, 4), v 5 = (1, 5) and v 6 = (2, 2). Here LB = 10. Let us apply the Algorithm T woApprox[d I = 0, last = V ](M). First we apply the algorithm for m 1 , m 2 . As Input: M = (m 1 , • • • , m M ), the set of messages ordered in non-increasing distance order and the direction V of the last message. Output: S = (s 1 , • • • , s M ) an ordered sequence of the M messages satisfying (i), (ii) and (iii) (See in Theorem 1) begin 1 Case M = 1: return S = (m 1 ) 2

Figure 3 :Figure 4 :Theorem 1

 341 Figure 3: Algorithm T woApprox[d I = 0, last = V ](M)

Theorem 2

 2 In the basic instance, the basic scheme (S, D) obtained by the Algorithm T woApprox[d I = 0, last = D](M) achieves a makespan at most LB + 2.

Example 2 1 Case M = 1 :

 211 [d I = 0, last = D](M); for an ordered input sequence M of messages and the direction D ∈ {H, V } it gives as output an ordered sequence S of the messages such that the basic scheme (S, last = D) has makespan at most LB + 1. As we explain in Remark 1 for Algorithm T woApprox[d I = 0, last = D](M) we only present Algorithm OneApprox[d I = 0, last = V ](M) with the last message sent vertically in Figure 5. The Algorithm OneApprox[d I = 0, last = H](M) can easily be obtained by symmetry. We can also obtained algorithms with the first message sent in direction D. Consider again the Example of Figure 4(a) (see Example 1). Let us apply the Algorithm OneApprox[d I = 0, last = V ](M). First we apply the algorithm for m 1 , m 2 ; (m 1 , m 2 ) / ∈ HV , we are at line 4 and S = (m 2 , m 1 ) and S = (m 1 ). Then we consider m 3 , m 4 ; the value of p (line 6) is m 1 ; as (m 1 , m 3 ) / ∈ V H and (m 2 , m 4 ) ∈ HV , we are in case 3.2 line 11 (p = m M -3 ). So we get, as O = (m 1 ), S = (m 1 , m 3 , m 2 , m 4 ). We now apply the algorithm with m 5 , m 6 ; the value of p (line 6) is m 4 ; as (m 4 , m 5 ) / ∈ V H and (m 4 , m 6 ) / ∈ HV , we are in case 4.1 line 13. So we get S = (m 1 , m 3 , m 2 , m 4 , m 6 , m 5 ). The makespan of the algorithm is LB + 1 = 11 = d(m 5 ) + 5 achieved for s 6 = m 5 . But, if we apply to this example the Algorithm OneApprox[d I = 0, last = H](M), we get a makespan of 10. Indeed (m 1 , m 2 ) ∈ HV gives first S = (m 1 , m 2 ). Then as p = m 2 , (m 2 , m 3 ) ∈ HV and (m 3 , m 4 ) / ∈ V H, we are in case 2 line 8. So we get S = (m 1 , m 2 , m 4 , m 3 ) and S = (m 1 , m 2 , m 3 ). Finally, with p = m 3 , (m 3 , m 5 ) ∈ HV and (m 5 , m 6 ) ∈ V H we get (line 7 case 1) the final sequence S = (m 1 , m 2 , m 4 , m 3 , m 5 , m 6 ) with makespan 10 = LB. However there are sequences M such that both Algorithms OneApprox[d I = 0, last = V ](M) and OneApprox[d I = 0, last = H](M) give a makespan LB + 1. Consider the example of Figure 4(c). Like in Example 1, LB = 16; furthermore, for the messages m 1 , . . . , m 6 Algorithm OneApprox[d I = 0, last = V ](M) gives the sequence S V = (m 1 , m 3 , m 2 , m 4 , m 6 , m 5 ) with makespan 17 and Algorithm OneApprox[d I = 0, last = H](M) gives the sequence S H = (m 1 , m 2 , m 4 , m 3 , m 5 , m 6 ) with makespan 16. For the messages m 1 , . . . , m 6 , we get (similarly as in Example 1) by applying Algorithm OneApprox[d I = 0, last = V ](M) the sequence S V = (m 1 , m 2 , m 4 , m 3 , m 5 , m 6 ) with makespan 10 and by applying the Algorithm OneApprox[d I = 0, last = H](M) the sequence S H = (m 1 , m 3 , m 2 , m 4 , m 6 , m 5 ) with makespan 11 achieved for s 6 = m 5 . Now if we run the Algorithm Inria Input: M = (m 1 , • • • , m M ), the set of messages ordered in non-increasing distance order and the direction V of the last message. Output: S = (s 1 , • • • , s M ) an ordered sequence of M satisfying properties (a), (b) and (c) and, only when s M = m M -1 , an ordering S = (s 1 , • • • , s M -1 ) of the messages (m 1 , • • • , m M -1 ) satisfying properties (a'), (b') (c') and (d') (See in Theorem 3) begin return S = (m 1 ) 2 Case M = 2: 3 if (m 1 , m 2 ) ∈ HV return S = (m 1 , m 2 ) 4 else return S = (m 2 , m 1 ) and S = (m 1 ) 5

Figure 5 :Theorem 3

 53 Figure 5: Algorithm OneApprox[d I = 0, last = V ](M)(case when the last message is sent vertically)

  We prove the theorem for D = V . The case D = H can be proved symmetrically. The proof is by induction on M . If M = 1, the result holds obviously as we send m 1 vertically (line 1). If M = 2, either (m 1 , m 2 ) ∈ HV and S = (m 1 , m 2 ) satisfies all properties (a) (b) and (c) or (m 1 , m 2 ) / ∈ HV and by Lemma 2 (m 2 , m 1 ) ∈ HV and S = (m 2 , m 1 ) satisfies all properties (a) (b) and (c) and S = (m 1 ) satisfies all properties (a'), (b') (c') and (d'). Now, let M > 2 and let O p = OneApprox[d I = 0, last = V ](m 1 , • • • , m M -2 ) be the sequence computed by the algorithm for (m 1 , m 2 , • • • , m M -2 ). By the induction hypothesis, we may assume that O p satisfies properties (a), (b) and (c). In particular p is sent vertically and p ∈ {m M -3 , m M -2 }. We have also that, if p = m M -3 , O satisfies properties (a'), (b') (c') and (d').

  So, S satisfies Property (a') . Finally s M -1 = m M -2 and by hypothesis (line 12) (m M -2 , m M ) / ∈ HV and (m M -2 , m M -1 ) / ∈ V H and therefore S satisfies property (d'). The following claims will be useful to conclude the proof in cases 3.2 and 4.2. In these cases p = m M -3 and let p be the last element of O . By induction on O , and by property (c'), p ∈ {m M -4 , m M -3 }. Claim 1 : In cases 3.2 and 4.2, (m M -2 , m M -1 ) / ∈ V H Proof. By hypothesis (lines 9 and 12)

Claim 2 :

 2 In cases 3.2 and 4.2, (p , m M -1 ) ∈ HV . Proof. If p = m M -3 by hypothesis lines 9 and 12 (m M -3 , m M -1 ) / ∈ V H and by Lemma 1 (m M -3 , m M -1 ) ∈ HV . If p = m M -4 , by induction hypothesis (d') applied to O , (m M -4 , m M -3 ) / ∈ V H and so by Lemma 1 (m M -4 , m M -3 ) ∈ HV ; furthermore by hypothesis (m M -3 , m M -1 ) / ∈ V H and so by Lemma 3 applied with m M -4 , m M -3 , m M -1 in this order, we get (m M -4 , m M -1 ) ∈ HV . In case 3.2, by hypothesis (line 9) (m M -2 , m M ) ∈ HV ; by the claim 1 (m M -2 , m M -1 ) / ∈ V H and so by Lemma 2 (m M -1 , m M -2 ) ∈ V H; and by claim 2, (p , m M -1 ) ∈ HV . So the theorem is proved in case 3.2. Finally it remains to deal with the case 4.2. Let us first prove that S satisfies (a). By hypothesis line 12 (m M -2 , m M ) / ∈ HV and by the claim (m M -2 , m M -1 ) / ∈ V H and so by Lemma 4 applied with m

Finally, by claim 1 ,Theorem 4

 14 (m M -2 , m M -1 ) / ∈ V H and so by Lemma 2 (m M -1 , m M -2 ) ∈ V H. By claim 2, (p , m M -1 ) ∈ HV and so S satisfies Property (a'). S satisfies also Property (d') as (m M -2 , m M ) / ∈ HV by hypothesis and (m M -2 , m M -1 ) /∈ V H by claim 1. As corollary we get by property (c) and definition of LB that the basic scheme (S, last = D) achieves a makespan at most LB + 1. We emphasize this result as a Theorem and note that in view of Example 2 it is the best possible for the algorithm. In the basic instance, the basic scheme (S, last = D) obtained by the Algorithm OneApprox[d I = 0, last = D](M) achieves a makespan at most LB + 1.

  , S H ) be the sequence obtained by applying Algorithm OneApprox[d I = 0, last = V ](M k ) (resp., Algorithm

Figure 6 :Example 3

 63 Figure 6: Example for optimal schedule with not shortest directed path.

Figure 7 :Fact 4 5 . 1

 7451 Figure 7: Cases of interferences with destinations on the axis

Remark 2 (

 2 A): Obviously, this bound is valid for 1-open grid according to Definition 2. (B): This bound is valid for d I = 1 only when the source has a degree 2 (case BS in the corner of the grid). If BS is in a general position in the grid we have no better bound than LB. (C): One can check that the bound is still valid if at most one message has a destination at distance 1 or 2. But if two or more messages have such destinations (d(m M -1 ) ≤ 2), then the bound is no more valid. As an example, let dest(m i ) = v i , with v 1 = (1, 2), v 2 = (2, 1), v 3 = (1, 2) and v 4 = v 5 = (1, 1), then d(m 1 ) = d(m 2 ) = d(m 3 ) = 3 and d(m 4 ) = d(m 5 ) = 2 and LB c (1) = d(m 5 ) + 6 = 8. However we can achieve a makespan of 7 by sending m 4 horizontally at step 1, then m 1 vertically at step 2 and m 2 horizontally at step 3, then the source sends m 3 vertically at step 5 and m 5 horizontally at step 6. m 3 and m 5 reach their destinations at step 7.

For d I ≥ 2 ,Proposition 3

 23 we have the following lower bound. Let d I ≥ 2 and suppose we are in d I -opengrid. Let M = (m 1 , m 2 , • • • , m M ) be an ordered sequence of messages (i.e., by non-increasing distance), then the makespan of any broadcasting scheme is greater than or equal to LB(d I ) = max i≤M d(m i ) + (i -1)d I .

Figure 8 :

 8 Figure 8: Algorithm Epsilon(M, f irst = D)

Theorem 12

 12 Given a grid with any arbitrary base station BS, and M = (m 1 , m 2 , • • • , m M ) an ordered sequence of messages (i.e., by non-increasing distance), then there are linear-time algorithms which broadcast the messages without interferences, with makespan: • at most LB + 2 if d I = 0; • at most LB + 1 if d I = 0 in an open-grid; • at most LB c (1) + 3 if d I = 1 in a 2-open-grid; • at most LB(2) + 4 if d I = 2 in a 2-open-grid;

• c = 2

 2 when d I = 0; • c = 1 in open-grid when d I = 0; • c = 3 in 1-open-grid when d I = 1 and BS is a corner; • c = 4 in 2-open-grid when d I = 2.

3 2 LB + 3

 23 for d I = 1, since LB c (1) ≤ 3 2 LB and 2LB + 4 for d I = 2, since LB(2) ≤ 2LB. So we have almost 3 2 and 2-approximation algorithms for d I = 1 and d I = 2 in 2

RR n°8218

The authors would like to thanks Prof. Frédéric Guinand who raised this question.Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

OneApprox[d I = 0, last = H](M k )) to the sequence M k . The makespan is equal to LB; indeed if the sequence is (s 1 , . . . , s k ) the makespan is max i≤k d(s i ) + i -1. But we have s i ∈ {m i-1 , m i , m i+1 } for any i ≤ k -1, and so d(s i ) + i -1 ≤ d(m i-1 ) + (i -1) -1 + 1 ≤ LB (as d(m i-1 ) + (i -1) -1 < LB); we also have s k ∈ {m k-1 , m k } and so either d(s k ) = d(m k-1 ) + (k -1)

Suppose k > 1, then the destination of m k-1 is at the same distance of that of m k ; indeed if d(m k-1 ) > d(m k ), then d(m k-1 ) + k -2 ≥ d(m k ) + k -1 = LB and LB will also be achieved for k -1 contradicting the hypothesis. Consider the set D k of all the messages with destinations at the same distance as m k (so if k > 1 |D k | ≥ 2) and let m u (resp.,m ) be the uppermost vertex (resp., lowest vertex) of D k that is the vertex of D k with the highest y (resp., the lowest y); (in case there are many such messages with the property, i.e. they have the same destination node, we choose one of them).

Furthermore, we claim the existence of a basic scheme for M k , such that if the last message is sent vertically (resp., horizontally) it is sent to m u (resp.,to m ). Indeed, suppose we want the last message sent vertically to be m u it suffices to order the messages in M k such that the last one m k = m u ; then if we apply Algorithm OneApprox[d I = 0, last = V ](M k ) we get a sequence where s k ∈ {m k-1 , m k }. Either s k = m k = m u and we are done or s k = m k-1 and s k-1 = m u ; but in that case (s k-1 , s k ) ∈ HV implies, by Fact 2, that x k-1 < x u or y k-1 ≥ y u , where (x u , y u ) and (x k-1 , y k-1 ) are the destinations of m u and m k-1 . But m u , m k-1 ∈ D k and m u being the uppermost vertex, y k-1 ≤ y u and x k-1 ≥ x u . Therefore, s k-1 and s k have the same destination So we can interchange them. Similarly using Algorithm OneApprox[d I = 0, last = H](M k ) we can obtain an HV -scheme denoted S H with the last message sent horizontally being m .

If k=1, M k is reduced to one message m 1 and the claims are satisfied with m u = m = m 1 and S V = S H = m 1 . Now consider the sequence M k ; the lower bound is LB = max k<i≤M d(m i ) + i -k -1 < LB -k as LB is not achieved for any i = k. Let S H be the sequence obtained by applying Algorithm OneApprox[d I = 0, f irst = H](M k ) with the first element of S H sent horizontally and let s h be this first element. (Note that we obtain this algorithm from Algorithm OneApprox[d

Similarly Let S V be the sequence obtained by applying Algorithm OneApprox[d I = 0, f irst = V ](M k ) with the first element of S V sent vertically and let s v be this first element. In all the cases the makespan is at most LB + 1 ≤ LB -k. Now we consider the concatenation of the sequences S V S H and S H S V . We claim that one of these two sequences has no interferences. If the claim is true, then the theorem is proved as the makespan will be LB for the first k messages and LB + 1 + k ≤ LB for the last M -k messages. In what follows, let as usual (x u , y u ), (x l , y l ), (x h , y h ) and (x v , y v ) denote respectively the destinations of messages m u , m l , s h and s v . Now, suppose the claim is not true, that is (m u , s h ) / ∈ V H and (m , s v ) / ∈ HV . That implies by Fact 3 and Fact 2 that x h < x u and y h ≥ y u and x v ≥ x and y v < y . But we choose the destination of m u (resp.,m ) to be the uppermost one (resp., the lowest one) in D k . So, x u ≤ x l and y u ≥ y l . Therefore x h < x v and y h > y v which imply first that s h = s v and by Fact 3 and Fact 2 that (s v , s h ) / ∈ V H and (s h , s v ) / ∈ HV . Finally note that, by the property of Algorithm OneApprox[d I = 0, last = D](M), s h ∈ {m k+1 , m k+2 } and s v ∈ {m k+1 , m k+2 }; thus, as they are different, one of s h , s v is m k+1 and the other m k+2 . Suppose that s h = m k+1 and s v = m k+2 ; then in the sequence S V the first message is s v = m k+2 and from property (c) in Theorem 3, the second message is necessarily m k+1 = s h , but that implies (s v , s h ) ∈ V H a contradiction. The case s h = m k+2 and s v = m k+1 implies similarly in the sequence S H that (s h , s v ) ∈ HV , a contradiction. So the claim and the theorem are proved. Proof. First suppose dest(m) is on one of the axis. If, y = 0 there is no interference (4.4). If x = 0 and y > y message m arrives at its destination (0, y) at step y + 2, but message m leaves (0, y) at step y + 2 and so they interfere (4.2 and 4.1 with y > y). If x = 0 and y ≤ y, either x = 0 and the directed paths followed by the messages do not cross (4.5), or x > 0, but then message m leaves (1, y ) at step y + 2, while message m arrives at (1, y ) at step y + 2 and so they interfere (4.1 with y ≤ y).

Suppose now that dest(m) is not on one of the axis, that is x > 0 and y > 0. If x = 0, the directed paths followed by the messages do not cross (4.6). If y = 0, then either x < x and the messages do not interfere (4.7) or x ≥ x, and the directed paths cross at (x, 1) and there either y = 1 and the messages do not interfere (4.7) or y ≥ 2 , but then message m leaves (x, 1) at step x + 2, while message m arrives at (x, 1) at step x + 2 and so they interfere (4.3).

By exchanging x and y and also H and V we get: x > 0, y > 0, x = 0, and either x = 1 or y < y

Proof. If none of the destinations of m and m are on the axis, the result holds by Lemma 1. If at least one destination is on an axis, suppose that (m, m ) / ∈ HV . If conditions of Fact 4.1 or 4.2 are satisfied, then x = 0 but then by Fact 5.4 (m, m ) ∈ V H. If condition of Fact 4.3 is satisfied , so x > 0, y = 0 and y ≥ 2 which implies by Fact 5.6 that (m, m ) ∈ V H. The second claim is obtained similarly.

Similarly we get the generalization of Lemma 2.

However Lemma 3 is no more valid in its full generality.

Lemma 7 Let dest(m) = (x, y), dest(m ) = (x , y ) and dest(m ) = (x , y )

sending is used for m ), and y ≥ max(2, y + 1), and 0 The second claim is obtained similarly. We give the following useful corollary for the proof of the next theorem.

Proof. Indeed by the preceding lemma if (m, m ) / ∈ HV , then y = 0, x < x and so d(m ) < d(m ). We now show that Lemma 4 is still valid in general grid.

(iv) for any i ≤ M , if s i is a message sent H Y (resp., V X ) that is a message sent horizontally (resp., vertically) with destination on column 0 (resp., on line 0), then s i ∈ {m i , m i+1 , m i+2 } Proof. We prove the theorem for D = V . The case D = H can be proved symmetrically. The proof is by induction on M and follows the proof of Theorem 1. We have to verify the new property (iv) and property (i) when one of p, q, m M -1 , m M has its destination on one of the axis. Recall that q is the last message in O. We will denote dest(p) = (x p , y p ), dest(q) = (x q , y q ), dest(m M -1 ) = (x M -1 , y M -1 ) and dest(m M ) = (x M , y M ).

For property (i) the proof of Theorem 1 works if, when using Lemma 3, we are in a case where it is still valid, that is when Lemma 7 is valid. We use Lemma 3 to prove case 2 of the Algorithm T woApprox[d I = 0, last = V ](M) with p, m M -1 , m M in this order. The order on the messages implies d(m M -1 ) ≥ d(m M ) and so by Corollary 1, Lemma 7 is valid. We also use Lemma 3 to prove the case 3 of the algorithm with q, p, m M -1 in this order. The order on the messages implies d(p) ≥ d(m M -1 ) and so by Corollary 1, Lemma 7 is valid. Note that to prove case 4 of the algorithm we use Lemma 4 which is still valid (Lemma 8).

It remains to verify property (iv). In case 2 of the algorithm, we have to show that s M = m M -1 is not using V X -sending because we use induction for (m 1 , . . . , m M -2 ). So it is sufficient to prove y M -1 > 0. Indeed, by Fact 4, (m M -1 , m M ) / ∈ HV implies y M -1 > 0. In case 3 of the algorithm, to verify property (iv) we have to show that s M -1 = p is not using H Ysending because we use induction for (m 1 , . . . , m M -2 ). So it is sufficient to prove x p > 0. Indeed, by Fact 5, (p, m M -1 ) / ∈ V H implies x p > 0. In case 4 of the algorithm, to verify property (iv) we have to show that s M = m M -1 is not using V X -sending. Suppose it is not the case i.e. y M -1 = 0; as (p, m M -1 ) / ∈ V H, we have by Fact 5.2 y p = 0 and x M -1 > x p . But then d(p) < d(m M -1 ) contradicts the order of the messages.

As corollary we get by properties (iii) and (iv) and the definition of LB, that the modified basic scheme(S, last = D) achieves a makespan at most LB + 2. We emphasize this result as a Theorem and note that in view of Example 1 or the example given at the end of Section 2 it is the best possible. Proof. To prove that the two messages do not interfere, we will prove that at any step for any pair of messages sent but not arrived at destination, the distance between the sender of one and the receiver of the other is ≥ 2. Consider a step t+h = t +h where h = h-1 and 1 ≤ h < min{x+y, x +y +1+2 }. By Fact 6 we have to consider 6 cases. We label them as case i-j' if we are in case i for m and in case j' for m , i = 1, 2 and 1 ≤ j ≤ 3: case 1-1': 1 ≤ h < x and 0 ≤ h -1 < y + . Then, the distance between a sender and a receiver is at least 2h ≥ 2.

case 1-2': 1 ≤ h < x and y + ≤ h -1 < x + y + . Then, the distance between a sender and a receiver is at least 2(y + ) ≥ 2, as y ≥ 1.

Then, the distance between a sender and a receiver is at least h -x + y = 2y + 2 ≥ 4.

case 2-1': x ≤ h < x + y and 0 ≤ h -1 < y + . Then, the distance between a sender and a receiver is at least

But, the distance between a sender and a receiver is at least 2(x + (y + ) -h) ≥ 2 in both cases.

case 2-3': x ≤ h < x + y and = 1 h -1 = x + y + 1. Then, the distance between a sender and a receiver is at least |x -x|

The next lemma will be used partly for proving the correctness of algorithm for d I = 1 (since the last case in the lemma will not happen in the algorithm) and fully for the algorithm for d I = 2.

Lemma 10 Let G be an open-grid. Let dest(m) = (x, y) with x ≥ 2 and m be sent horizontally at step t with an -detour. Let dest(m ) = (x , y ) and m be sent vertically with an -detour at step t = t + 2. Let furthermore {x < x or y ≥ y} (i.e. (m, m ) ∈ HV in the basic scheme). Then, for d I = 1 or 2, m and m interfere if and only if case 00. = 0, = 0: x = x -1 and y ≤ y -1 case 01. = 0, = 1: x = x -1 and y ≤ y -2 case 10. = 1, = 0: x ≥ x and y = y case 11. = 1, = 1: x = x -1 and y = y -1 Proof. Consider a step t + h = t + h so h = h -2. By Fact 6 we have to consider 9 cases according the 3 possibilities for an arc used by m and the 3 possibilities for an arc used by m . We label them as case i-j' if we are in case i for m and in case j' for m , 1 ≤ i, j ≤ 3. We will prove that in all the cases, the distance of the sender and receiver of these two messages is either at most 1 or at least 3. So the interference happens in the same condition for d I = 1 and d I = 2. case 1-1': Then, the distance between a sender and a receiver is at least 2h -1 ≥ 3 as h = h -2 ≥ 0.

Inria case 1-2': Then, the distance between a sender and a receiver is at least 2(y + ) + 1 ≥ 3 as y ≥ 1. case 1-3': h = h +2 = x +y +3. The distance between a sender and a receiver is at least h-x +y = 2y + 3 ≥ 5, as y ≥ 1.

case 2-1': Then, the distance between a sender and a receiver is either |x

case 2-2': Then, the distance between a sender and a receiver is at least

Otherwise, y < y and by the hypothesis x < x.

, then the distance is ≥ 3. Otherwise when β = 0 (i.e. x = x -1) and = 0, we have a distance 1, achieved for h = x + y + + 1. More precisely when = 0, it is achieved with x = x -1 and y ≤ y -1, which corresponds to case 00. When = 1, we have already seen that the distance is 3, for y = y -1 (case α = 1); otherwise the distance is 1 with x = x -1 and y ≤ y -2 (case 01). We will have to define general-scheme by indicating not only the ordered sequence of messages S = (s 1 , • • • , s M ) sent by the source, but also by specifying for each s i the time t i at which the message s i is sent and the directed path followed by the message s i , in fact the direction D i and the i -detour used for sending it. More precisely, Definition 5 A general-scheme is defined as a sequence of M quadruples (s i , t i , D i , i ), where the ith message sent by the source is s i . This message is sent at step t i horizontally if D i = H (resp., vertically if D i = V ) with an i -detour.

Note that we will send the messages alternatively horizontally and vertically in our algorithm. Therefore, we have only to specify the direction of the first (or last) message. We will see in the next theorem that the sequence S obtained by the algorithm OneApprox[d I = 0, f irst = D](M) in Section 3 almost works when d I = 1. More precisely, we propose a scheme that sends the messages in the same order as in S. However, BS waits one step every three steps, i.e., the source sends two messages of the sequence S during two consecutive steps then stops sending for one step. Furthermore, a message must sometimes be sent with a detour to avoid interference. That is, the messages are sent without detours like in S, except that, if the first message is sent horizontally (if D = H), an even message s 2k+2 is sent vertically with a 1-detour if and only if without detour it would interfere with s 2k+3 . • for any i = 2k + 1, 0 ≤ k ≤ (M -1)/2 , let t i = 3k + 1 D i = H and i = 0,

• for any i = 2k + 2, 0 ≤ k < M/2 , let t i = 3k + 2, D i = V and 2k+2 = 0 if s 2k+2 does not interferes with s 2k+3 for d I = 1, otherwise 2k+2 = 1.

Then the general-scheme defined by the sequence (s i , t i , D i , i ) i≤M broadcasts the messages without collisions for d I = 1 and the first message is sent in direction H.

Proof.

To prove the theorem, we need to prove that any two messages do not interfere at any step in the general scheme with parameters (s i , t i , D i , i ). A message s i cannot interfere with a message s i+j for j ≥ 2 sent at least 3 steps after; indeed the senders of such two messages will be at distance at least 3 (at Inria