Nathalie Mitton
email: nathalie.mitton@insa-lyon.fr

Anthony Busson
email: anthony.busson@ief.u-psud.fr

Eric Fleury
email: eric.fleury@inria.fr

Efficient Broadcasting in Self-Organizing Sensor Networks *

Keywords: sensor, multi-hop, wireless networks, self-organization, broadcasting, clustering, stochastic geometry

Multi-hop wireless networks (such as ad-hoc or sensor networks) consist in sets of mobile nodes without the support of a pre-existing fixed infrastructure. For scalability purpose, ad-hoc and sensor networks may both need to be organized into clusters and require efficient protocols to perform common global communication patterns like the broadcasting operation. During a broadcasting task, a source node needs to send a same message to all other nodes in the network. Some desired properties of a scalable broadcasting are energy and bandwidth efficiency, i.e., message retransmissions should be minimized. In this article, we present a scalable broadcasting schemes that takes advantages of the clustering structure. In this way, we only build one structure to perform both self-organization and broadcasting in clusters and in the whole network. It appears that our broadcasting scheme presents the best trade-off between the number of retransmissions and transmitters (for energy saving) and reliability, when compared to existing solutions.

Introduction

Multi-hop wireless networks (such as ad-hoc or sensor networks) consist of sets of mobile wireless nodes without the support of a pre-existing fixed infrastructure. They offer unique benefits for specific environments and applications as they can be quickly deployed. Each node acts as a router and may arbitrary appear or vanish. Protocols deployed in such dynamic contexts must adapt to frequent network topology changes.

No centralized administration entity is required to manage the different mobile hosts operations. Mobile hosts rely on battery power, which is a scarce resource. Moreover, wireless links have a significantly lower capacity than wired ones; they may be affected by several error sources that result in a degradation of the received signal. Ad-hoc networks and sensor networks are instances of multi-hop wireless networks. In adhoc networks, nodes are independent and may arbitrarily move at any time at different speeds. In sensor networks, nodes are more static and collect data they have to forward to specific sink nodes. For the purpose of scalability, ad-hoc and sensor networks may both need to be organized into clusters and require some protocols to perform common global communication patterns as the broadcasting task. An organization is needed to allow the scalability in terms of number of nodes or/and node density without generating too much traffic (for routing, for example) neither too much information to store or to compute. A common solution is to adopt a hierarchical organization by grouping nodes into "clusters" and bind them to a leader (cluster-head). Such an organization may allow the application of different routing schemes in and between clusters. In a broadcasting task, a source node needs to send a same message to all other nodes in the network. Such a functionality is needed, for example, when some queries about the measures (in sensor networks) or a node location (in ad hoc networks) need to be disseminated over the whole network or within a cluster. Furthermore, in all wireless networks, the broadcasting task is a fundamental mechanism used by either proactive or reactive routing protocols. The desired properties of a scalable broadcasting are thus reachability (every node must be touched by the broadcasting), energy and bandwidth efficiency (battery power and bandwidth are rare resources and must be saved as much as possible). The operation has to be designed in order to decrease the overhead as much as possible, while maintaining the maximal diffusion.

In this paper, we propose to take advantage of the characteristics of our previous wireless network clustered structure [START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF] in order to extend it to an efficient and scalable broadcasting structure. By using our purely distributed clustering algorithm, we build only one structure for both operations (organizing and broadcasting). We argue that both emissions and receptions consume energy. In order to maximize the lifetime of the network, one should minimize the number of relay nodes but also the number of receptions induced. We also provide a theoretical analysis of the broadcasting operation in such networks that show that the mean number of receptions per node can be expressed as the product of the degree of relay nodes time the probability for a node to be such a relay. Simulation results then allow us to illustrate our theoretical analysis and to evaluate the reliability of the different broadcasting schemes with regard to the number of the relays and their degree. Surprisingly, it appears that the more reliable protocols are not the ones with the greater number of transmitters but the ones which elect relays with a high degree. They also show that our broadcasting algorithm presents the best trade-off the best trade-off between the number of retransmissions and transmitters (for energy saving) and reliability, when compared to existing solutions.

The remainder of this paper is organized as follows. Section 2 presents some existing broadcasting solutions. Section 3 summarizes our previous work and highlights the fundamental characteristics of our cluster organization which might be useful for a broadcasting task. Section 4 presents the way we extend our cluster structure into a broadcasting structure and details our broadcasting scheme. Section 5 provides a theo-retical analysis of the broadcasting task using the stochastic geometry and the Palm distribution. Section 6 compares several broadcasting schemes by simulation and presents the results. Finally, we conclude and discuss possible future areas of investigation in Section 7.

Broadcasting in multi-hop wireless networks

The desired properties of a scalable broadcasting are reachability, energy and bandwidth efficiency. By reachability, we mean that a great proportion of nodes (more than 90%) receives the broadcast message. In this paper, we only consider reliability at the network layer, i.e., a broadcasting scheme is said reliable if every node connected to the source receives a broadcast packet in a collision free environment. As in a wireless environment, a node wastes energy when transmitting as well as receiving a packet [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF], the number of retransmissions and receptions should both be minimized. In this section, we focus on solutions proposed in the literature for network layer broadcasting schemes which are based on dominating sets and use omni-directional antennas.

The easiest way to broadcast a message over a network is the blind flooding, i.e., each node re-emits the message upon first reception of it. Obviously, this scheme engenders many collisions and wastes bandwidth and energy. Therefore, this broadcasting technique can not be envisaged over large scale or very dense networks. This gave birth to more intelligent broadcasting protocols which try to minimize the number of retransmissions by selecting a subset of relay nodes that are allowed to forward a message. This subset is called a dominating set. To obtain a reliable broadcasting scheme, each node in the network should be either in the dominating set (and is called a dominant or internal node) or neighboring at least one node in the dominating set. The main challenge is to find a connected dominating set (i.e., where the dominant nodes form a connected component) which minimizes the number of these transmitters as well as the number of copies of a same message received by a node. However, this problem is known to be NP-hard [START_REF] Garey | Computers and intractability : a guide to the theory of NP-completeness[END_REF]. I. Stojmenovic and J. Wu [START_REF] Stojmenovic | Broadcasting and activity scheduling in ad hoc networks[END_REF] have classified broadcasting schemes according to the kind of the dominating set they use: cluster-based, sourcedependent dominating set and source-independent dominating set.

In previous cluster-based [START_REF] Ephremides | A design concept for reliable mobile radio networks with frequency hoping signaling[END_REF][START_REF] Lin | Adaptive clustering for mobile wireless networks[END_REF] solutions, the idea is that every node which has the lowest Id or the highest degree (Linked Cluster Architecture (LCA) protocol) in its 1-neighborhood becomes a cluster-head. If a non-cluster-head node can hear more than one cluster-head among its neighbors, it becomes a gateway. The connected dominating set is thus composed of both the cluster-heads and the gateways. Some optimizations have been proposed to localize the maintenance process and avoid chain reactions which may occur in case of node mobility [START_REF] Chiang | Routing in clustered multihop, mobile wireless networks with fading channel[END_REF] or to limit the number of gateways [START_REF] Wu | Forward node set based broadcast in clustered mobile ad hoc networks[END_REF] (to reduce the size of the dominating set).

In solutions based on source-dependent dominating set [START_REF] Lim | Multicast tree construction and flooding in wireless ad hoc networks[END_REF][START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF], the sending node selects adjacent nodes that should relay the message. The set of relays of a node u is chosen to be minimal and such that each 2-hop neighbor of node u has at least one neighbor among the relays of u. A node u only needs information on its 2neighborhood to select its relays. When a broadcasting task is performed, a node u forwards a message received at first from a node v if and only if node v has chosen node u as one of its relays. Methods differ in details on how a node determines its relays. The most popular of them is the one based on the Multi-Point Relays (MPR) of OLSR [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF]. In OLSR, the MPR are also used for building routing tables and the MPR have thus a double use.

In solutions based on source-independent dominating set, the set of relay nodes is independent of the source node and thus it is the case of our proposal. Nodes decide by themselves whether they belong to the dominating set, as opposed to the sourcedependent schemes where relays are explicitly chosen by a node. Many solutions have been proposed. In every cases, nodes only need information of their 2-neighborhood. A simple and efficient algorithm, the NES (Neighbor Elimination-Based Scheme) of Wu and Li [START_REF] Wu | A dominating set based routing scheme in ad hoc wireless networks[END_REF], introduces the notion of intermediate nodes. A node is said intermediate if at least two of its neighbors are not direct neighbors. Two selection rules based on the 2-neighborhood topology are then introduced to reduce the number of intermediate nodes by "eliminating" some of them. The remaining ones become the relays. A node states whether it is relay according to a priority value which primarily was the node Id. Then, several variant solutions have been proposed to enhance this algorithm by using other priority values as e.g. the node degree or the remaining battery [START_REF] Dai | Distributed dominant pruning in ad hoc networks[END_REF][START_REF] Stojmenovic | Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[END_REF]. From it, several solutions have then been derived [START_REF] Cartigny | RNG relay subset flooding protocol in mobile ad-hoc networks[END_REF][START_REF] Stojmenovic | Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[END_REF]. In [START_REF] Stojmenovic | Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[END_REF], the authors also propose another kind of Neighbor Elimination Scheme which can be summed up by "Wait and See". Upon reception of a broadcast message, a node does not forward the message immediately but counts a random period of time. During this period it watches whether one of its neighbors forwards the message and if so, what are the nodes which receive the message. When the random period is expired, the node forwards the message if and only if some of its neighbors have not been covered by previous transmissions. An enhancement of this scheme has then been introduced in [START_REF] Cartigny | RNG relay subset flooding protocol in mobile ad-hoc networks[END_REF] by considering the Relative Neighborhood Graph (RNG) instead of the real graph. However, these latter Neighbor Elimination Schemes can not been classed in source-independent dominating set category as they are based on random numbers. Moreover, the transmitters change from one broadcasting task to another one and do not depend on the source neither. Wait and See protocols obviously obtain great results regarding the number of transmitter nodes and useless receptions but they also induce an important latency due to the random waiting periods.

Previous work and main objectives

In this section, we summarize our previous clustering approach on which our broadcasting scheme proposition relies. Only basis and features which are relevant for broadcasting are mentioned here. For more details or other characteristics of our clustering heuristic, please refer to [START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF][START_REF] Mitton | Efficient broadcasting in self-organizing multi-hop wireless network[END_REF][START_REF] Mitton | Self-stabilization in selforganized multihop wireless networks[END_REF]. For the sake of simplicity, let's first introduce some notations. We classically model a multi-hop wireless network, by a graph G = (V, E) where V is the set of mobile nodes (|V | = n) and e = (u, v) ∈ E represents a bidirectional wireless link between a pair of nodes u and v if and only if they are within communication range of each other. We note C(u) the cluster owning the node u and H(u) the cluster-head of this cluster. We note Γ 1 (u) the 1-neighborhood of node u, i.e., the set of nodes with which u shares a bidirectional link. δ(u) = |Γ 1 (u)| is the degree of u.

Our objectives for introducing our clustering algorithm were motivated by the fact that in a wireless environment, the less information exchanged or stored, the better. First, we wanted a cluster organization suitable for large scale multi-hop networks. That implies that the radius/diameter of clusters should not be fixed a priori but should be flexible radius and able to adapt to the different topologies. (The clustering schemes mentioned in Section 2 have a radius of 1, in [START_REF] Amis | Max-Min D-cluster formation in wireless ad hoc networks[END_REF][START_REF] Fernandess | k-clustering in wireless ad hoc networks[END_REF] the radius is set a priori.) Second, nodes should be able to set up purely local heuristics by using local information, gathered in their 2-neighborhood. (In [START_REF] Amis | Max-Min D-cluster formation in wireless ad hoc networks[END_REF], if the cluster radius is set to d, the nodes need to gather information up to d hops away before taking any decision.) Finally, we desired an organization robust and stable over node mobility. To satisfy all these requirements, we introduced a new metric called density. The notion of density characterizes the "relative" importance of a node in the network and within its neighborhood. The underlying idea is that this link density (noted ρ(u)) should smooth local changes down in Γ 1 (u) by considering the ratio between the number of links and the number of nodes in Γ 1 (u).

Definition 1 (density) The density of a node

u ∈ V is ρ(u) = |{e = (v, w) ∈ E | w ∈ {u} ∪ Γ 1 (u) and v ∈ Γ 1 (u)}| δ(u) .
Each node locally computes its density value and periodically broadcasts it locally to its 1-neighbors (e.g., using Hello packets). Each node is thus able to compare its own density value to its 1-neighbors' density and decides by itself whether it joins one of them (the one with the highest density value) or it wins and elects itself as clusterhead. In case of ties, the node with the lowest Id wins. In this way, two neighbors can not be both cluster-heads. By performing the joining process, we actually build directed acyclic graphs (DAG). A DAG is a directed graph that contains no cycles, i.e. a directed tree. The node with highest density value within its neighborhood becomes the root of the tree and thus the cluster-head of the cluster. If node u has joined node w, we can say that w is node u's parent (noted P(u) = w) in the clustering tree and that node u is a child of node w (noted u ∈ Ch(w)). A node's parent can also have joined another node and so on. A cluster then extends itself until it reaches another cluster. If no node has joined a node u (Ch(u) = ∅), u becomes a leaf. All the nodes belonging to a same tree belong to the same cluster. The clustering process builds clusters by building a spanning forest of the network in a distributed and local way as the decision criterion is only based on information regarding the 2-neighborhood of a node (gotten from HELLO packets locally and periodically broadcast).

Some characteristics of the clustering algorithm

This algorithm stabilizes when every node knows its correct cluster-head value. It has been proved by theory and simulation to self-stabilize within an expected low, constant and bounded time [START_REF] Mitton | Self-stabilization in selforganized multihop wireless networks[END_REF]. It has also been proved that a cluster-head is aware of an information sent by any node of its cluster in a low, constant and bounded time. The number of clusters built by this heuristic has been showed analytically and by simulation to tend toward a constant asymptote when the density of nodes in the network increases. Moreover, compared to other clustering schemes as DDR [START_REF] Nikaein | DDR-distributed dynamic routing algorithm for mobile ad hoc networks[END_REF] or Max-Min d cluster [START_REF] Amis | Max-Min D-cluster formation in wireless ad hoc networks[END_REF], our cluster organization has revealed to be more stable over node mobility and arrivals and to offer better behaviors over non-uniform topologies [START_REF] Mitton | Self-organization in large scale ad hoc networks[END_REF]

Objectives

As explained earlier, our clustering heuristic leads at the same time to the formation of a spanning forest. It appears attractive to use such a "nice" underlying clustering tree structure as a basis for the broadcasting task. This broadcasting scheme is dominating set-based where all non-leaf nodes (tree internal nodes) belong to the dominating set.

As mentioned in Table 1, a great proportion of nodes (about 75%) are actually leaves, therefore a broadcasting scheme based on this dominating set is expected to save many retransmissions. As the clustering trees form a spanning forest of the network, the set of all trees is a dominating set of the network but is not a connected dominating set as the trees are independent. So, to perform a reliable broadcasting task in the whole network, we need to connect these trees by electing some gateways between them. Our gateway selection process is described in Section 4.

As already mentioned, each node only needs to know its 2-neighborhood to choose its parents, and to know whether it has been chosen as parent by one of its neighbors, otherwise it is a leaf. Thus, the forwarding decision of a non-gateway node is based on local state information. Only the gateway selection can be qualified of quasi-local (according to the classification of [START_REF] Wu | Forward node set based broadcast in clustered mobile ad hoc networks[END_REF]) as only few nodes need information up to 4 hops away (tree depth). Thus, our broadcasting scheme does not induce a high costly maintenance. We propose to use this structure not only to perform a traditional broadcasting in the whole network but also for broadcasting constraint into a cluster only. This kind of task might be interesting for clustered architectures when, for example, a cluster-head needs to spread information only in its cluster like in sensor networks, for instance, where a base station may need to update devices or spread a query over them.

The eccentricity of a node is the greater distance in number of hops between itself and any other node in its cluster. We can see in Table 1 that the tree depth is pretty low and close to the optimal one (cluster-head eccentricity). This presents a good property for performing a broadcasting within our clusters. Indeed, none node is really far away from its cluster-head and can expect to receive quickly any information it would spread. Moreover, we computed the proportion of points closer to their cluster-head than any other one in Euclidean distance (Voronoi: Euclidean distance in Table 1) and in number of hops (Voronoi: # of hops in Table 1). Results show that a large proportion of nodes (more than 83%) lays in the Voronoi cell of their cluster-head whatever the process intensity. This characteristic is useful in terms of broadcasting efficiency as if the cluster-heads need to spread information over their own cluster, if most of the nodes are closer to the one which sends the information, we save bandwidth, energy and latency.

Our contribution

In this section, we first propose an algorithm for the gateway selection, then we detail the two kinds of broadcasting: within a cluster and in the whole network.

Gateway selection

A gateway between two neighboring clusters C(u) and C(v) is a pair of nodes x, y noted Gateway(C(u), C(v)) = x, y such that x ∈ C(u), y ∈ C(v) and x ∈ Γ 1 (y). For a given pair, we say that node x is the "gateway node" and that node y is the "mirror-gateway node" of the gateway. If C(u) and C(v) are two neighboring clusters, we note the gateway

Gateway(C(u), C(v)) = x = GW (C(u), C(v)), y = GW m(C(u), C(v)) , where GW (C(u), C(v)) is the gateway node and GW m(C(u), C(v)) is the mirror-gateway node. Note that GW (C(u), C(v)) ∈ C(u) and GW m(C(u), C(v)) ∈ C(v).
The gateways are directed gateways in the meaning that two neighboring clusters are linked by two gateways Gateway(C(u), C(v)) and Gateway(C(v), C(u)) which may be different.

To select a gateway between two clusters, we thus need to define a pair of nodes. Our selection algorithm runs in two steps. The first step allows each frontier node to locally choose its "mirror(s)" in the neighboring cluster(s). We call a node u a frontier node if at least one of its neighbors does not belong to the same cluster than u. A frontier node and its mirror then form an eligible pair. The second step selects the most appropriate pair as the gateway. The algorithm tries to promote the selection of internal nodes in order to minimize the size of the dominating set as these latter ones already belong to the relay set.

Moreover, in order to add reliability against link failures over these sensitive nodes, each gateway elects a back-up gateway within its neighborhood. This one will forward the message if and only if it does not hear the principal gateway transmitting it (Wait and See philosophy).

Mirror node selection

As seen in Section 3, as the density-based clustering algorithm uses the node Id as the last decision criterion, every node u might be aware in an expected bounded and low time, whether it exists among its neighbors a node v which does not belong to the same cluster than u. If so, node u is a frontier node and so becomes an eligible gateway node for Gateway(C(u), C(v)). Each frontier node u then selects its mirror node among its neighbors which do not belong to C(u). To do so, u first selects non-leaf nodes, i.e., internal nodes/transmitters in every case and chooses among them the node with the highest density value. If all nodes v ∈ Γ 1 (u) such that C(u) = C(v) are leaves, u chooses the node with the lowest degree in order to limit the useless receptions induced by an emission of a message by the mirror. In case of ties, the lowest Id decides. If u is a frontier node of the cluster C(v) (C(v) = C(u)), we note m(u, C(v)) the mirror node chosen by u in C(v). Note that if a node u is a frontier node for several clusters, it has to select a mirror for each cluster.

Algorithm 1 Mirror selection -RUN AT EACH FRONTIER NODE u, i.e., ∃v ∈ Γ 1 (u) s.t. C(v) = C(u)

Gateway selection

Once each frontier node has chosen its mirror, we have to choose the most appropriate pair as the gateway. Once a gateway node u is elected as

GW (C(u), C(x)), we have Gateway(C(u), C(v)) = GW (C(u), C(x)), mirror(GW (C(u), C(x)), C(x)) .
According to the taxonomy of [START_REF] Wu | Forward node set based broadcast in clustered mobile ad hoc networks[END_REF], this step is quasi-local whereas the first one is local.

The gateway selection we propose is distributed since a selection is performed at every level in the tree and tries to limit useless receptions by favoring internal nodes. Frontier nodes send their Id to their parent and indicate them whether they are leaves and whether they have a leaf as mirror. Each parent selects the best candidate among its children and sends the same information up to its own parent and so on, until reaching the cluster-head. The selection is thus semi-distributed as every internal node eliminates some candidates. In this way, only small size packets are forwarded from the frontier nodes to the cluster-head. As mentioned in Table 1, the mean degree of all the internal nodes (cluster-head included) is small and constant whatever the number of nodes, which induces a small and bounded number of messages at each level which is also bounded by a low constant [START_REF] Mitton | Self-stabilization in selforganized multihop wireless networks[END_REF].

Let's express that v belongs to the subtree rooted in u (noted v ∈ sT (u)) if u is the parent of node v or if the parent of node v is in the subtree rooted in u:

{v ∈ sT (u) ∩ Γ 1 (u)} ⇔ {v ∈ Ch(u)} or v ∈ sT (u) ∩ Γ1 (u) ⇔ {P(v) ∈ sT (u)}
Let say that C(x) is a neighboring cluster of the subtree sT (u) of an internal u iff C(x) = C(u) and ∃x ∈ C(x) and y ∈ sT (u) such that y ∈ Γ 1 (x). The best candidate choice is performed as follows. For each of the neighboring clusters C(x) of its subtree, an internal node u considers the set G of the candidate nodes (frontier nodes

) (G = {v ∈ sT (u) | ∃w ∈ Γ 1 (v) | C(w) = C(u)}).
Then, it selects among them the subset G ′ ⊂ G of internal nodes, still in order to limit the number of transmitter nodes. If G ′ is only composed of leaves, the selection is processed among all candidates of G. From there, u favors the nodes which mirror is a non-leaf node, then it uses either the density value (if remaining candidates are non-leaves) or degree (otherwise) to decide. At the end, in case of ties, the node with the lowest Id is elected as GW (C(u), C(x)). Note that, if C(u) and C(v) are two neighboring clusters, Gateway(C(u), C(v)) = Gateway(C(v), C(u)) in most cases.

Algorithm 2 Gateway selection RUN AT EACH INTERNAL NODE u

For each cluster C = C(u) for which ∃v ∈ sT (u) which is a frontier node do Gather the set G of candidate nodes:

G = {v ∈ sT (u) | ∃w ∈ Γ1(v) | C(w) = C}. Select G ′ ⊂ G the set of nodes v s.t. G ′ = G ∩ {v|Ch(v) = ∅}.
⊲ u first selects the set of the non-leaf nodes as they are transmitters in every case. if (G ′ = ∅) then ⊲ There are non-leaf candidates. u will favor the ones with a non-leaf mirror and/or the highest density.

Select G" ⊂ G ′ the set of nodes s.t. G" = G ′ ∩ {v|Ch(m(v, C)) = ∅}. if (G" = ∅) then Select F inalist ⊂ G" the set of nodes s.t. F inalist = {v|ρ(v) = max w∈G" ρ(w)} . ⊲ Internal Node↔Internal Node Gateway. else Select F inalist ⊂ G" the set of nodes s.t. F inalist = {v|ρ(v) = max w∈G ′ ρ(w)} .
⊲ Internal Node↔Leaf Gateway. end else ⊲ All candidates are leaves. u will favor the ones with a non-leaf mirror and/or the smallest degree.

Select G" ⊂ G the set of nodes s.t. G" = G ∩ {v|Ch(m(v, C)) = ∅}. if (G" = ∅) then Select F inalist ⊂ G" the set of nodes s.t. F inalist = {v|δ(v) = min w∈G" δ(w)} . ⊲ Leaf↔Internal Node Gateway.
else Select F inalist ⊂ G" the set of nodes s.t.

F inalist = {v|δ(v) = min w∈G ′ δ(w)} . ⊲ Leaf↔Leaf Gateway. end end if (F inalist = {v}) then W inner = v. else W inner = {v|Id(v) = min w∈F inalist Id(w)}.
⊲ There are ties. u elects the node with the lowest Id. end if (u = H(u)) then W inner becomes the final gateway node: Gateway(C(u), C) = W inner, m(W inner, C) else Send the W inner identity to P(u). end end do

Back-up gateway selection:

This selection is a purely distributed local process and it takes benefits from the locally broadcast feature offered by the wireless medium. When a frontier node sends information to its parents during the gateway selection process, every node in its neighborhood learns its condition (leaf, internal, border node, etc.). In this way, a gateway node knows in its neighborhood which node may act as a back-up gateway, without extra-message. It selects it by choosing a frontier node which has a mirror node different from its own one if possible. This back-up gateway acts as follows. Upon reception of a broadcast message, the back-up gateway triggers a timeout. If it has not heard the main gateway emitting when the timeout expires, the back-up gateway forwards the broadcast message. This back-up gateway thus does not add any useless receptions (as it emits only under some conditions) and adds some reliability in the broadcasting task. Moreover, it does not add any extra-cost since its selection is local and does not need any additional information.

This back-up gateway concept is similar to the one in "OSPF" 1 where there are back-up routers.

Broadcasting heuristic

A node u may need three kinds of broadcasting tasks:

• link-local broadcasting: broadcast to the 1-neighbors of u, no forwarding needed

• site-local broadcasting: broadcast to every node in the same cluster than u

• global broadcasting: broadcast to all the nodes in the network To distinguish between these three broadcasting tasks, we need the use of several broadcasting addresses in the packet 2 . When the broadcasting task is performed within a cluster C(u), the message is forwarded upon first reception by all the nonleaf nodes of C(u). When the broadcasting task is performed in the whole network, all the non-leaf nodes in the network forward the message as well as all gateways and mirror-gateway nodes, under some conditions. As our gateways are directed, a gateway node GW (C(u), C(w)) forwards the message only if it is coming from its own cluster C(u). A mirror-gateway node GW m(C(u), C(w)) forwards the message only if it is coming from the cluster C(u) for which it is a mirror. However, a mirror-gateway node GW m(C(u), C(w)) forwards a message coming from C(u) whatever the transmitter node in C(w) (which is not necessarily the gateway node GW (C(u), C(w)) for which it is the mirror).

Algorithm 3 Broadcasting algorithm

For all node u, upon reception of a broadcast packet P coming from node v ∈ Γ1(u) do ⊲ Node v is the previous hop and not necessary the broadcast source.

if (u receives P for the first time)

if global broadcasting if (Ch(u) = ∅) then Forward ⊲u is an internal node. else if ((C(u) = C(v)) and (u = GW (C(u), C(w))∀w ∈ V )) then Forward end ⊲ u is a

Theoretical broadcasting analysis

As we saw in Section 2, most of broadcasting protocols aim to reduce the number of transmitters, often by electing the highest degree nodes. The main goal is to minimize the global energy spent for transmission in the network during a broadcasting task. However, as studied in [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF], energy spent in receptions is not negligible since a wireless node spends almost the same amount of energy for receiving than for transmitting with the IEEE 802.11 MAC layer technology.

Therefore, in this section, we are interested in the analysis of the number of messages received by a typical node when a broadcasting task is performed.

We will consider that nodes are distributed in the plan according to a stationary Point Process of intensity λ that represents the nodes. In such processes, the intensity λ corresponds to the mean number of points per surface unit. Two points (x, y) of the Point Process are neighbors if and only if the Euclidean distance between x and y is lower than a fixed threshold, a given constant R (d(x, y) ≤ R). R denotes the radio range of the nodes. If Φ is a stationary Point Process of intensity λ, then Φ(S) represents the number of points of the Point Process Φ laying in the surface S. Let B(x, R) be the ball of radius R centered in node x and B ′ x be such that

B ′ x = B(x, R)\ {x}.
In Propositions 1 and 2, we express the mean number of receptions per node. This result will be used to compare the different algorithms. Proposition 1 holds for the model we consider in our simulations, which is described in Section 6.

The hypothesis of these propositions are thus directly checked with the model used in this paper. The second result expressed in Proposition 2 is the same than the first one but holds for more general random graphs. Let r be the mean number of receptions received at a node (relay or not). For the sack of clarity, the proofs are presented in Appendix.

Proposition 1 Let Φ be a stationary Point Process of intensity λ (λ > 0) distributed in the plan. Let Φ Relay be a thinning of Φ. The points of Φ Relay represent the relays. We suppose that Φ Relay is still a stationary Point Process of intensity λ Relay . We only consider nodes/points within an observation window W , which is a square of size L×L with L ∈ IR + . We have:

r = E o Φ Φ Relay (B ′ 0 ) = E o Φ Relay Φ(B ′ 0 ) P o Φ (0 ∈ Φ Relay ) = λ Relay λ E o Φ Relay Φ(B ′ 0 ) (1)
where

E o Φ Φ Relay (B ′ 0
) is the expectation (so the mean number) under palm probabilities w.r.t. the process Φ of the relay points in B ′ 0 .

This latter result may be interpreted as follows: the mean number of receptions per node is the product of the degree of a relay and of the probability for a node to be a relay (or equivalently the mean ratio of relays/nodes).

Proposition 2 Given a random graph G(V, E) and a set of relay nodes Relay ⊂ V , where • (i) the degree of the nodes are identically distributed,

• (ii) the degree of the relays in G are identically distributed,

• (iii) the number of receptions per node are identically distributed.

Then we have:

r = E δ(v 1 ) v 1 ∈ Relay P(v 1 ∈ Relay) (2)
In this equality, v 1 is a node arbitrarily chosen among the set of vertice in G (a typical node). The choice of v 1 has no impact since the probability to be a relay and the degree of nodes are equi-distributed. As in Proposition 1, the mean number of receptions per node is the product of the mean degree of the relays and the probability for a node to be a relay.

Discussion: In [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF], the authors show that the energy consumption of a broadcast transmission when using the IEEE 802.11 MAC layer technology, is approximately four times the cost of a reception by a node. In all broadcasting heuristics mentioned in Section 2, between 20% and 50% of the nodes are transmitters but each node receives the broadcast message between 5 and 10 times. Therefore, for a 100-node network, a broadcasting operation causes between 20 and 50 transmissions but also between 500 and 1000 receptions. The most costly part of a broadcasting in a 802.11 ad hoc network is then due to the induced receptions rather than the transmissions. This key observation may differ from one technology to another, but receptions still certainly consume an important part of the energy spent during a broadcasting. Moreover, a high number of receptions per node increases the collision probability and the bandwidth used. A node which receives 10 times the same packet cannot use the medium during these 10 transmissions. So, we are convinced that one of the main performance criteria for a protocol/heuristic used to broadcast a packet in an ad hoc network is the mean number of receptions per node.

In this Section, we have shown that this number of receptions is given as the product of the proportion of transmitters and the mean degree of the transmitters. Unfortunately, neither the degree of relays nor the proportion of relays can be analytically worked out yet for the considered algorithms but the blind flooding, for which the results are trivial. However, we evaluate these quantities by simulation in Section 6 in order to compare the behavior of the different broadcasting algorithms. We shall show that they minimize either the degree of the relays (as the MPR or NES heuristic) or the number of relays used (as our clustering algorithm). For instance, our heuristic based on the node density favors relays with high degree compared to the other heuristics while keeping a low number of receptions (the number of transmitters is then small). It has the advantage of minimizing both transmissions and receptions and so the global cost of the broadcasting. Moreover, such a relay selection is robust since a transmitter has a high degree: a link failure does not isolate the transmitters.

Simulation results

We first performed simulations in order to qualify the gateways elected and then to compare the broadcasting tasks performed with our clustering and gateway selection schemes to other existing heuristics. This section details the results. All the simulations follow the same model. We use a simulator we developed which assumes an ideal MAC layer. Nodes are randomly deployed using a Poisson Point Process in a (1+2R)×(1+ 2R) square with various levels of intensity λ. In such processes, λ represents the mean number of nodes per surface unit. Only the points within the square w of size 1 × 1 are taken into account to estimate the different quantities (mean degree, mean density, etc.). But in order to avoid side effects, the samples of Point Processes are generated in a larger window W . For instance, if we estimate the mean degree (δ) of nodes, we take the degree of the points in w to compute δ. If we do not consider the points of W , the points close to the edge within w would have a lower degree than the points close to the center, introducing a bias in the estimations. Both windows are shown in Figure 1. This technique is called "minus-sampling", a more detailed description can be found in [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]. The communication range R is set to 0.1 in all tests. In each case, each statistic is the average over 1000 simulations. When several algorithms are compared, they are compared with the same samples of the simulation model.

Gateways: election and utilization

If we consider two neighboring clusters C(u) and C(v), we may have four different types of gateways between them:

• Leaf↔Leaf gateways: GW (C(u), C(v)) and GW m(C(u), C(v)) are both leaves. This kind of gateway is the more costly as it adds two transmitter nodes and thus induces more receptions.

• Leaf↔Internal Node gateways: GW (C(u), C(v)) is a leaf and GW m(C(u), C(v)) an internal node. This kind of gateway adds only one transmitter node. It's the least popular, as shown later by simulations.

• Internal Node↔Leaf gateways: GW (C(u), C(v)) is an internal node and GW m(C(u), C(v)) a leaf. This kind of gateway adds only one transmitter node.

• Internal Node↔Internal Node gateways: GW (C(u), C(v)) and GW m(C(u), C(v)) are both internal nodes. This kind of gateway is the one we try to favor since it does not add any extra-cost since it does not add any transmitter neither induces any additional reception. But, as we will see, they unfortunately are the least popular ones.

Table 2 shows the mean number of gateways a cluster has to elect and maintain and the mean number of gateways used when a global broadcasting task is performed. As we can note, the number of gateways to elect is reasonable and remains almost constant while process intensity increases. This shows the good scalability feature of this heuristic. Nevertheless, this was predictable since, as we saw in Section 3, the number of clusters is constant from a certain amount of nodes, so is the mean number of neighboring clusters for a cluster and so the number of gateways to elect. Moreover, we also saw that the cluster topology was close to a Voronoi tessellation. Yet, in a Voronoi tessellation, a cell has 6 neighbors in average. This is actually the mean number of gateways a cluster has to elect. Figure 2(a) gives the proportion of each kind of gateways selected. We can note that the two less elected kinds of gateways are the Leaf↔Internal Node and Internal Node↔Internal Node gateways. This is due to the fact that, by construction, most of frontier nodes are leaves. This also explains the great proportion of other kinds of gateways since, as soon as there is an internal node as a frontier node, it is elected (and thus Internal Node↔Leaf gateways are preferred to Leaf↔Internal Node ones). The more sparse the network, the less chance to find internal nodes on borders. So, the proportion of Internal node↔Leaf gateways increases with the intensity process while the proportion of Leaf↔Leaf gateways decreases. When a global broadcasting task is performed, all the gateways are not necessary used since 2 neighboring clusters C(u) and C(v) are connected via 2 gateways Gateway(C(u), C(v)) and Gateway(C(v), C(u)) and in most cases, only one of them is used. As shown in Table 2, the number of gateways used per cluster is quite constant and remains pretty low, always comprised between 1 and 2. This means that generally, either the broadcasting enters a cluster and dies in it (in this case, it uses only one gateway), either it passes through it and thus uses two gateways (one to enter the cluster, one to leave it).

Figure 2(b) shows the proportion of each kind of gateways used when a global broadcasting operation is initiated. As we can see, most of them are the ones which add only one transmitter node. This is true even for low intensities of node when the rate of Leaf↔Leaf gateways elected was the highest. This shows that our algorithm can adapt and favor internal nodes naturally. As the mean number of gateways used is low and since we add only one transmitter node for each gateway, the induced cost is low as well.

Broadcasting performances

In order to evaluate our algorithm, we chose to compare it to some of the most representative broadcasting schemes seen in Section 2: blind flooding, LCA [START_REF] Lin | Adaptive clustering for mobile wireless networks[END_REF] (cluster-based schemes), Multi-Point Relay [START_REF] Qayyum | Multipoint relaying: An efficient technique for flooding in mobile wireless networks[END_REF] (source-dependent dominating set), the Neighbor Elimination-Based Scheme of Wu and Li [START_REF] Wu | A dominating set based routing scheme in ad hoc wireless networks[END_REF] (source-independent dominating set) and the Neighbor Elimination Scheme "Wait and See" of I. Stojmenovic, M. Seddigh and J. Zunic [START_REF] Stojmenovic | Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[END_REF] (random dominating set). As seen in Section 5, we try to compare them in terms of energy-efficiency, also taking into account the impact of the relay degree on these performances. Therefore, the significant characteristics we note are the proportion of nodes which need to re-emit the message (size of the dominating set) and their mean degree, as well as their impact over the mean number of copies of the broadcast message that a node receives (useless receptions). Moreover, we simulate two different variants of the Neighbor Elimination Scheme of Wu and Li: the original one [START_REF] Wu | A dominating set based routing scheme in ad hoc wireless networks[END_REF] where the node priority is the node Id, and a later version of it where the priority value is the node degree (plus Id to break ties) [START_REF] Dai | Distributed dominant pruning in ad hoc networks[END_REF], still in the aim to study the impact of the relay degree over the broadcasting performances. We also have a look at the latency (time needed for the last node to receive the broadcast packet initiated at the source). As the main goal is to limit energy consumption and bandwidth occupation in order to maximize the network lifetime, all these values have to be as low as possible. Moreover, we have to note that the latency of the NES-"Wait and See" protocol depends on the size of the window in which nodes randomly choose their backoff time. It is thus the protocol with the highest latency and we did not evaluate it.

The more transmitters and useless receptions, the more redundancy. Thus, when a broadcasting scheme induces many retransmissions, it is expensive in terms of energy but it is expected to be more reliable against link or node failures and/or mobility. Therefore, we also analyze the impact of both number of receptions per node and degree of the relays on the broadcasting robustness. In other words, we analyze the trade-off between redundancy and reliability against link failures.

Broadcasting over the whole network (global broadcasting)

Figure 3 shows the proportion of transmitters in the network as well as their degree in the graph, for the different broadcasting algorithms.

Figure 3(b) shows the degree of these relays. As in the blind flooding, every node is a transmitter, the mean degree of the relays actually is the mean degree of the nodes in the graph. We observe that the density-based relay selection maximizes the mean degree of the relays as opposed to the NES technique of Wu and Li for which the mean degree of transmitters is smaller than the mean degree of nodes. Since the mean node density value is almost proportional to the mean node degree [START_REF] Mitton | Analysis of the self-organization in wireless multi-hops networks[END_REF], density-based selection elects nodes with a high degree. Besides, note that the original NES of Wu and Li and the NES-"Wait and See" elects transmitters with the same degree value. We also note that the MPR selection elects transmitters without favoring nodes with small or high degree. NES-"Wait and See" selects relays with a degree lower than the mean value as, the more neighbors a node has, the more likely it is to hear one of them emitting before its backoff time is off. Moreover, as expected, since heuristics are based on it, LCA and NES-degree of Wu and Li also elect relays with a high degree.

Figure 3(a) plots the proportion of transmitter nodes in the network. As in blind flooding, every node forwards the message upon first reception of it, this proportion is equal to 1. We can note that the "Wait and See" heuristic is the one having the less transmitter nodes and thus spending the less energy for emissions. Our heuristic is very close to it. Also remark that the two variants of the NES protocol generate approximatively the same amount of transmitters.

Nevertheless, as seen in Section 5, the resulting number of receptions per node can not been deduced only from these results (proportion of transmitters and their degree) as it actually is the convolution of both of them. And, as one of the heuristics with the lowest number of transmitters also is the one with the highest relay degrees, we can not deduce from it whether useless receptions are minimized or not, and so it is for all heuristics. We can just suppose that the variant of the NES protocol based on the degree would cause more receptions on nodes than the original NES protocol as, for a same amount of transmitters, the degree of relays is higher.

Figure 4 shows the mean number of receptions per node of a single broadcast message.

As we can observe, when a global broadcasting task is initiated, the NES-"Wait and See" algorithm induces less receptions than other algorithms. Thus, it spends less energy and resources. Nevertheless, we can note that the results of our algorithm are very close to the "Wait and see" ones since the density-based generates only one additional reception in average per node. Moreover, as the "Wait and See" scheme is based on random counters, the latency induced is inevitably greater than the one induced by the density-based heuristic. Thus, also regarding the fact that the initial goal of density-based heuristic is clustering, we can estimate that the density-based algorithm results are pretty good. Moreover, as mentioned later, the NES-"Wait and See" scheme is much less reliable against link failures. Also remark that, as expected, the original NES protocol of Wu and Li causes less receptions than the variant based on the node degree.

Since in the MPR selection, the relays are selected in order to reach the 2neighborhood after two hops, the k-neighborhood of the source is reached within k hops. Under the assumption of an ideal MAC layer, MPR gives the optimal results in terms of latency (Number of hops). We thus compare our heuristic to the MPR one to measure how far we are from the optimal solution. We consider a time unit as a transmission step (i.e., 1 hop). Table 3 presents the results. Yet, we can note that, even if our algorithm is not optimal regarding the latency, results are very close to it. Figure 5 represents the propagation in time for a broadcast packet initiated at the cen-tered source at time 0. Cluster-heads appear in blue and the source in green. The color of other nodes depends on the time they receive the broadcast packet. The darker the color, the shorter the time.

Broadcasting within clusters (cluster broadcasting)

We now suppose that the broadcasting task is performed in each cluster, initiated at the cluster-heads. We thus have as many broadcastings as clusters.

We can see on Figure 6, that this time, our broadcasting algorithm is the one which best minimizes the proportion of transmitter nodes, even outperforming the NES "Wait and See" protocol (Figure 6(b)). Moreover, it also obtains the best results regarding the number of receptions (Figure 6(a)) with the NES "Wait and See" Scheme.

These results also confirm the analytical results claiming that the number of receptions on nodes can not be directly deduced from the proportion of transmitters. Indeed, for example, the density-based algorithm selects less relays with much higher degree than the "Wait and See" and finally, they both provide a similar amount of receptions per node.

Table 4 and Figure 7 present the results regarding the latency. We still compare our algorithm to the MPR protocol, without considering the "Wait and See" for which the latency is random as linked to the size of the backoff counter. Once again, we can observe that, even if our algorithm is not optimal, results are very close as, in average, a node in our algorithm needs only 0.5 step more than the optimal value to receive the packet. This also shows that, even if routes in trees, from the cluster-heads to other nodes, are not always the shortest ones, they are very close to them. In Table 5, we give the proportion of nodes which receive the first copy of the packet by their parent or by one of their children. This feature shows whether the message which is sent by the cluster-head follows the branches of the trees. Indeed, a node u always receives the message by its parent (as all non-leaf nodes forward the message) but it could have received it before from another way as paths are not always optimal. In this case, as we suppose an ideal MAC layer, the shortest route between u and its cluster-head is not found by following the route in the tree. We can thus see that routes are the shortest ones in number of hops for more than 70% of the cases. We can also observe, as the message progresses down the tree, that none of the nodes receives it the first from one of their children. 5: Proportion of nodes which receive the first copy of the packet by their parent or by one of their children.

Broadcasting and gateway reliability

After considering these results, we wonder about the reliability of all these protocols (still only considering the network layer) against link and/or node failures. Indeed, till now, we have only compared protocols regarding the energy saved by each of them, by limiting useless receptions on nodes and trying to minimize the size of the dominating set. However, the more transmitters, the more redundancy and so the more reliability. Therefore, is it really a good approach to minimize redundancy on nodes in an environment where wireless links are weak? Moreover, we wonder whether the degree of relay nodes has any impact over the reliability. For a same amount of receptions on nodes, is it better to have few transmitters with high degrees or more transmitters with low degrees? And, is the redundancy in terms of number of receptions really has an impact on reliability?

In order to evaluate this aspect of the broadcasting task, we apply a failure probability over links and measure the proportion of nodes still receiving the broadcast message. The simulation tests we performed, assume that the broadcasting task occurs before the nodes have recomputed anything e.g., their set of MPR-Selector nodes (MPR heuristic), their set of neighbors to eliminate (every NES scheme) or their parent in the clustering tree (density-based algorithm). As in the blind flooding, every node transmits the message upon first reception of it, nodes do not receive the message only if the network is disconnected. This failure model may seem not to be very realist as links can also fail because of congestion. Since the blind flooding, for example, induces more messages than any other protocol, more links fail. Nevertheless, the results of the blind flooding give an information about the network connectivity. However, link failures may also be due to node mobility. These moves are not instantly taken into account by the protocols and thus may introduce unexpected behaviors during a broadcasting operation.

Figure 8 shows the results for both kinds of broadcastings: in a cluster and in the whole network, for λ = 1000. Globally, the behavior of different heuristics is the same from one kind of broadcasting task to the other one, excepted the density-based heuristic. For example, the NES-"Wait and See" which was the best heuristic regarding the number of useless receptions and transmitters, is the least reliable one, whatever the kind of broadcasting.

Figure 8(a) considers a broadcasting in a cluster. Surprisingly, it does not appear that there is a link between the mean number of receptions per node, which can be seen as a kind of redundancy, and the robustness. For instance, we can note that even if the MPR heuristic induces more transmitters and useless receptions that the NES algorithms of Wu and Li, it is less reliable. This is due to the fact that in the MPR algorithm, a node will forward a broadcast message if and only if it has received the first from a node which has elected it as a MPR [START_REF] Busson | An analysis of the MPR selection in olsr and consequences[END_REF]. Another example is the densitybased heuristic where the number of receptions per node is small but which is one of the most robust.

It seems that protocols where the relays have a high degree tend to be more robust. Indeed, heuristics with high degree (NES-degree and Density based) are very robust and protocols with small degrees as MPR or the NES-"wait and see" present the worst behavior. However, the NES-Wu Li algorithm is an exception but its variant NES-degree (which increases the degree of the relays) is better in term of robustness. The redundancy in terms of number of receptions is thus very costly in terms of used bandwidth and energy consumption, as discussed in the previous Sections, but does not offer better performances in term of robustness.

Therefore, the density-based heuristic presents a good reliability against link failures when a broadcasting task is performed within a cluster. As it also minimizes both the proportion of transmitters and useless receptions on nodes, it constitutes the most efficient protocol since it is a trade-off between cost and reliability. Moreover, remind that a broadcasting operation in a cluster is performed in a quasi-optimal time.

Nevertheless, as we can notice on Figure 8(b), the density-based algorithm is much less reliable when used for performing a broadcasting task over the whole network. It is still better than the NES-"Wait and See" heuristic as a greater proportion of nodes still receives the message when links fail, but it is less reliable than the NES scheme of Wu and Li. This result, coupled with the fact that our heuristic well behaves when the broadcasting is confined in a cluster, shows that the weakest points in such a global broadcasting are the gateways which link the clusters. Indeed, if a cluster A can be reached only by cluster B and that the gateway from B to A fails, the whole cluster is isolated in the broadcasting operation. In order to add some reliability, it ought to be better to elect several gateways between all pairs of neighboring clusters. Electing more than one gateway does not add extra-cost as the gateway selection manages it without any additional message. Additional cost when using several gateways only appears when a global broadcasting task is performed and uses these multiple gateways. Indeed, this means additional transmitter nodes and thus additional receptions on nodes. Therefore, there is a trade-off to discuss between the cost of additional transmitters and useless receptions and the reliability of the protocol. In order to estimate this trade-off, we simulated a global broadcasting by using several gateways between clusters. We then compare with other heuristics regarding the redundancy, the transmitter ratio and the number of useless receptions. Results, given in Figure 9, clearly show that reliability is quickly improved with the addition of gateways, which confirm that they indeed are the sensitive points in the broadcasting task. As Figure 9(a) shows, electing three gateways between any pair of neighboring clusters is enough to obtain the same reliability than the NES schemes of Wu and Li. Moreover, as Figures 9(b) and 9(c) plot, with three gateways, the density-based algorithm still induces less useless receptions and transmitters than other ones (excepted the NES "Wait and See" scheme).

Conclusion and perspectives

We have proposed a broadcasting scheme over a clustered topology for multi-hop wireless networks. We can thus obtain a double-use structure with low cost, as the maintenance is local and quasi-local. The cost is bounded by the tree depth which is a low constant. Moreover, two kinds of broadcasting task may be performed over it since we can perform global broadcastings in the whole network as well as broadcastings confined inside a cluster. Our proposed algorithm offers better results than some existing broadcasting schemes. More precisely, it saves more retransmissions since the number of internal nodes selected is lower (for both global and cluster-confined broadcastings). Moreover, the number of duplicated packets received is also lower. Note that reducing both emissions and receptions is an important factor when designing energy aware broadcasting protocols. Future works will be dedicated to investigate robustness of clustering-based broadcasting protocol in presence of node and link failures. Preliminary results tend to show that the confined broadcasting is more robust that the global one and thus we investigate more deeply the impact of the choice and number of gateways between clusters.

We present here the proofs of Propositions 1 and 2.

Proof of Proposition 1 Since the Poisson Point Process is distributed in IR 2 , nodes of W may receive the broadcast message from nodes outside of W .

For a typical point, i.e., the point 0 under Palm probabilities, the mean number of receptions corresponds to the mean number of points of Φ Relay at distance less than R. If r is the mean number of receptions per node,

r = E o Φ Φ Relay (B ′ 0 )
where E o Φ is the expectation (so the mean number) under palm probabilities w.r.t. the process Φ of the relay points in B ′ 0 . According to the Mecke Formula (see [START_REF] Stoyan | Stochastic geometry and its applications[END_REF]), the total number of receptions Z received by all the nodes within W is

E W Φ Relay (B ′ x )Φ(dx) = λE o Φ Φ Relay (B ′ 0 )
By stationarity of the two Point Processes Φ and Φ Relay , we have,

E W Φ Relay (B ′ x )Φ(dx) = E W Φ(B ′ x )Φ Relay (dx)
The left hand side of the equality is the total number of receptions perceived by the nodes within W (relays can be outside) and the right hand side is the total number of receptions perceived by the whole points of Φ but generated by the relays standing in W . Applying the Mecke formula to both sides of the equality, we obtain:

λE o Φ Φ Relay (B ′ 0 ) = λ R E o Φ Relay Φ(B ′ 0 )
and so,

r = E o Φ Φ Relay (B ′ 0 ) = E o Φ Relay Φ(B ′ 0 ) P o Φ (0 ∈ Φ Relay ) = λ Relay λ E o Φ Relay Φ(B ′ 0 )
Remark 3 If we just consider points of W as relays and receivers, the total number of receptions becomes:

E W Φ Relay (B ′ x ∩ W )Φ(dx) = E W Φ(B ′ x ∩ W )Φ Relay (dx) = λ Relay W E o Φ Relay Φ(B ′ 0 ∩ (W -x)) dx = λ W E o Φ Φ Relay (B ′ 0 ∩ (W -x)) dx

Proof of Proposition 2

We define:

• N as the random variable which represents the number of vertice in G (N = |V |),

• for u ∈ G, δ R (u) as the number of relays in the neighborhood of u,

• r as the mean number of receptions per node,

• Z as the total number of receptions generated by the broadcasting.

We remind that, for u ∈ V , δ(u) is the number of neighbors of u (in other words the degree).

Only the relays forward the message, therefore, as links are bidirectional, the number of receptions at a node (relay or not) corresponds to the number of relays in its neighborhood. We have,

r = E[δ R (u)], ∀u ∈ V
where E[δ R (u)] is the expectation of the variable δ R (u) and corresponds to its mean value.

If the number of receptions is equi-distributed, we have In the last equalities, v 1 is a node arbitrary chosen among the set of vertice in G (a typical node), quantities being equi-distributed.

For

  each cluster C for which u is a frontier node: C = C(u) and ∃v ∈ Γ1(u) ∩ C, do Select S the set of nodes such that S = C ∩ {v | Γ1(u) | Ch(v) = ∅}. ⊲ u first selects the set of the non-leaf nodes as they are transmitters in every case. if (S = ∅) then Select S ′ the set of nodes such that S ′ = {v | v = maxw∈Sρ(w)}. ⊲ u collects internal nodes with the highest density in order to promote stability. else ⊲ All the possibly mirrors of u are leaves. S = {C ∩ Γ1(u)}. Select S ′ the set of nodes such that S ′ = {v | v = minw∈Sδ(w)}. ⊲ u collects the leaves with the lowest degree in order to minimize the receptions induced by adding this node to the relay set. end if (S ′ = {v}) then m(u, C) = v. ⊲ There are no ties. S ′ contains only one node: the mirror of u. else m(u, C) = v such that Id(v) = min w∈S ′ Id(w). ⊲ There are ties. u elects the node with the lowest Id. end end do

  gateway node and P is coming from its cluster. if ((C(u) = C(v)) and (u = GW m(C(v), C(u)))) then Forward end ⊲ P is coming from the cluster for which u is a mirror-gateway node. end else ⊲ It is question of a broadcasting within a cluster. ⊲ P is forwarded only by internal nodes of the considered cluster. if ((C(v) = C(u)) and (Ch(u) = ∅)) then Forward end end end end do

1 Figure 1 :

 11 Figure 1: Only points of w are taken into account to estimate the different quantities, but the Point Process is generated in the square W in order to avoid the side effects.

Figure 2 :

 2 Figure 2: Proportion of each kind of selected gateways and used gateways per cluster as a function of the process intensity.(+: Leaf↔Leaf; ×: Internal Node↔Leaf; * : Leaf↔Internal Node; : Internal Node↔Internal Node)

l v∈Relay where 1 l

 1 As we only have bidirectional links, Z can be written in two ways: v∈Relay = 1 if v ∈ Relay and 1 l v∈Relay = 0 otherwise.We take this last equality to compute E Z N , which actually is the mean value of Z N . We condition this quantity by the different values of N .(v i )1 l vi∈Relay ] P(N = k) = +∞ k=1 E δ(v 1 )1 l v1∈Relay N = k P(N = k) = E [δ(v 1 )1 l v1∈Relay ] = E δ(v 1 ) v 1 ∈ Relay P(v 1 ∈ Relay)

Figure 3 :

 3 Figure 3: Proportion of transmitter nodes (a) and their mean degree (b) as a function of the mean number of nodes for different algorithms.(+: Blind Flooding; ×: LCA; * : MPR; : NES -Wu Li; NES -Degree -Wu Li; ⊖ NES -Wait and See; • Densitybased)

Figure 4 :Figure 5 :Figure 6 :Figure 7 :

 4567 Figure 4: Number of receptions per node as a function of the number of nodes for different algorithms.(+: Blind Flooding; ×: LCA; * : MPR; : NES -Wu Li; NES -Degree Wu Li; ⊖ NES -Wait and See; • Density-based)

Table 1 :

 1 Some cluster and clustering tree characteristics.

	. Other

Table 2 :

 2 Number of gateways selected and used per cluster for a global broadcasting initiated at a randomly-chosen source as a function of the process intensity.

		500nodes 600nodes 700nodes 800nodes 900nodes 1000nodes
	#clusters	11.93	11.64	11.36	11.30	11.14	10.72
	#gw selected per cluster	5.86	6.02	6.16	6.20	6.22	6.26
	#gw used per cluster	1.76	1.74	1.73	1.76	1.68	1.66

Table 3 :

 3 Mean and Max time for receiving the message. "MAX" values represent the time needed for the last node to receive the packet. "MEAN" values represent the mean time a node needs to receive the broadcast packet.

		500 nodes	700 nodes	800 nodes	900 nodes	1000 nodes
		MEAN MAX MEAN MAX MEAN MAX MEAN MAX MEAN MAX
	MPR	5.13	8.97	4.88	8.40	4.88	8.40	4.81	8.23	4.78	8.07
	Density	6.31	11.05	6.22	10.78	6.24	10.95	6.15	10.66	6.19	10.74

Table 4 :

 4 Mean and Max time for receiving a cluster broadcast message. "MAX" values represent the time needed for every node to receive the packet at least once, "MEAN" values the mean time a node has to wait till the first reception of the packet.

		500 nodes	700 nodes	800 nodes	900 nodes	1000 nodes
		MEAN MAX MEAN MAX MEAN MAX MEAN MAX MEAN MAX
	MPR	1.76	4.71	1.78	4.85	1.81	4.83	1.81	4.80	1.82	5.00
	Density	1.80	5.08	1.83	5.38	1.87	5.29	1.87	5.50	1.88	5.30

http://www.faqs.org/ftp/rfc/pdf/rfc2328.txt.pdf

IPv6 addresses already use this concept of different broadcastings


Essia H Elhafsi

Nathalie Mitton
email: mitton@lifl.fr

David Simplot-Ryl
email: simplot-ryl@lifl.fr

Cost over Progress Based Energy Efficient Routing over Virtual Coordinates in Wireless Sensor Networks

We propose an energy efficient routing protocol, VCost, for sensor networks. We assume that nodes are unaware of their geographic location thus, VCost assigns virtual coordinates to nodes as follows. Based on the node hop count distances from a set of landmarks, our method computes a distance metric to obtain the node's virtual coordinates. VCost, then uses these coordinates to route packets from node u to node v, in its neighborhood, such that the ratio of the cost to send a message to v to the progress in the routing task towards the destination is minimized. Compared to existing algorithms that use virtual locations, our simulation shows that VCost improves significantly energy consumption and preserves the small percentage of successful routings.

Introduction

Sensor networks are specialized ad hoc networks composed of a large number of self organizing devices. They are used in a wide range of applications, such as monitoring, security, and data-gathering. These applications have two challenging issues in common i. e., energy savings and position-awareness. In this paper, we address these two key issues to efficiently deploy sensor networks.

Nodes, in sensor networks, rely on batteries with limited capacity, thus the most important criteria when designing communication protocols is to optimize their energy consumption to extend the life of the sensor device and extend the reliability of the underlying network. In this framework, routing protocols based on geographic information of the sensors have been proposed as a viable alternative to existing routing protocols for wireless ad hoc networks in order to reduce the overhead of maintaining routing tables in the sensors and to avoid the cost (energy consumption) of flooding and route discovery. However, such a solution requires that the sensors be aware of their geographic (physical) position which can be obtained by equipping all the sensors with costly global positioning system (GPS) devices. An approximate solution may be obtained by equipping only a few designated sensors (called landmarks) with GPS devices and let the remaining nodes infer their positions. However, even such an expensive alternative may not be a reliable solution since GPS reception might be obstructed by static obstacles i. e., nodes may be deployed indoors. A cheaper alternative is to consider the problem of inferring the locations of the nodes in sensor networks in which no node is aware of its physical position. Proposed solutions such as in [1, 2, 4, 6, 7] are aimed at routing by deriving and using virtual coordinates. However, none of the above cited papers consider or optimize the energy consumption in their proposed algorithms.

In this paper, we are interested in energy efficient routing in sensor networks where nodes are not aware of their physical locations. Xu et al., in [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF], compute the optimal transmission radius that minimizes the total power consumption for a routing task in sensor network. In this work, we extend this result and present an energy aware routing algorithm based on virtual coordinates. We compare the performance of our proposed method to the one of several geographic routing algorithms and show that our algorithm is efficient in terms of energy saving and hit rate (success rate of a message to reach its final destination).

The rest of the paper is organized as follows. In Section 2, we present a brief summary of existing geographic routing algorithms relevant to our work. In Section 3, we present our contribution, a cost efficient routing algorithm over virtual coordinates. In Section 4, we compare the performance of our proposed method to alternative routing algorithms presented in Section 2. Finally we conclude and present future work extensions.

Related Works

A sensor network is generally represented by a graph G = (V, E) where V is the set of nodes and E ⊆ V 2 is the set of edges which allow the available communications. If u and v are two nodes of the graph G, then the edge (u, v) belongs to E means that u is physically neighbor of v and thus it receives its messages. We denote by R the maximum transmission range of communication which is the same for all nodes in G. Let dist(u, v) be the Euclidean distance between u and v. The set E is then defined as follows:

E = {(u, v) ∈ V 2 | dist(u, v) ≤ R}.
We define the neighborhood set N (u) of a node u as:

N (u) = {v ∈ V | v = u ∧ (u, v) ∈ E}.
To route a packet from a given source s to a given destination d in G, the geographic location of the nodes are generally required. However, several geographic routing approaches that rely on virtual coordinates have been proposed. To define a virtual coordinate system, one of three options can be adopted. First, one can assume that nodes have knowledge of the position of their neighbors and based on this information a coordinate system can be defined. Second, one can equip a subset of nodes with a satellite receiver and use these nodes as landmarks. In this case, to infer the position of the remaining nodes, it suffices to know their distances relative to the landmarks. Several distance measures, such as the Euclidean and the Hamming distances, have been used in the literature. A Virtual Coordinate assignment (VCap) protocol is proposed in [2] as a third option when no location information is available.

In this work, we focus on the following routing algorithms: Most Forward Routing, Gradient landmark based routing, VCap Routing and Cost-over progress Routing.

• Most Forward Routing (MFR). In this greedy approach [START_REF] Takagi | Optimal tarnsmission ranges for randomly distributed packet radio terminals[END_REF], the source node forwards the message to exactly one of its neighbors that is closest to the destination. This is a simple localized algorithm however that does not guarantee delivery. There are several scenarios in which this greedy routing fails. For instance, if a node u is closer to the destination than any of its neighbors, or if two adjacent nodes are equally close to the destination and none of their neighbors is closer, then this approach can be trapped in a local minimum and the algorithm fails to find a path to the final destination. Thus the hit rate is very low. However, this algorithm works well in a dense graph.

• Gradient landmark based routing (Glider). In [4]

nodes are partitioned into tiles and a set of well dispersed nodes are identified as landmarks. Virtual coordinates are then given to each node based on their centered square-distance, otherwise known as the variance, from each landmark. Based on the virtual coordinate system, the distance between two nodes, the centered virtual distance is computed. In our work, we are only interested in Glider's virtual coordinate system, but for completeness we describe its routing scheme. A node first computes a sequence of tiles for the routing path. Then it uses gradient descent on the Euclidean distance function in the virtual coordinates towards the next tile in the path. This scheme does not guarantee delivery in the discrete case. Moreover, it is complex and requires a high communication overhead, i. e., storage of a view of the communication graph and node location that should be accessible by all nodes in the network.

• Virtual Coordinate assignment protocol (VCap). In [2] a system of virtual coordinates based on hop counts from three landmarks is proposed. Nodes are assigned a triplet of coordinates given as the number of hops the node is distant from each landmark. Then, nodes use a greedy routing, like MFR with the Hamming distance computed on these coordinates. Note that even though, an efficient coordinate system can be generated using three landmarks, a more accurate one can be established as the number of landmarks increases as we show in this work and as claimed in [1].

• Cost Over Progress routing. In [START_REF] Kuruvila | Progress and location based localized power aware routing for ad hoc sensor wireless networks[END_REF], a localized energyaware routing algorithm where nodes are equipped with GPS receivers is proposed. Each node makes a routing decision on the basis of its location, its neighbors and the destination. A node forwards the packet to the neighbor closer to the destination such that the ratio of the energy consumed to the progress made (measured as the reduction in distance to destination) is minimized. Generally, the energy consumed J, depends on the transmission range r and the overhead c that is due to signal processing and it is equal to J = r α +c if r = 0 and zero otherwise, α is a real constant greater than 1 and it represents the signal attenuation. In this work, we ignore the energy consumed due to signal emission. In [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF] the optimal transmission radius, r * , that minimizes the total power consumption for a routing task is computed and it is equal to:

r * = α c α-1 .

Cost over Progress over Virtual Coordinates

The framework of our proposition is similar to VCap. Several nodes, L 1 , , . . . , L k with k ≥ 3, in the network are distinguished as landmarks. An arbitrary node x knows its distance vector l(x) = (l 1 , . . . , l k ) where l i is the hopdistance between x and L i . From vector l(x), the node generates a so-called virtual coordinates c(x) = (x 1 , . . . , x m ) with m ≥ 2. Note that in general m ≤ k, in our study m = k. This computation function is denoted by Γ. We consider two Γ functions: the identity denoted by Γ id (x i = l i ) and the "centered virtual coordinates" used in [4] and denoted by Γ cvc (x i = l 2 iµ where µ = 1 k k i=1 l 2 i ). We suppose that each node x knows the virtual coordinates of each node in its neighborhood (N (x)).

To route a packet to destination d, a node extracts the virtual coordinates of d from the packet and chooses a forwarding node in its neighborhood. We propose to use "cost over progress" presented in [START_REF] Kuruvila | Progress and location based localized power aware routing for ad hoc sensor wireless networks[END_REF]. The idea is that the current node x chooses node y ∈ N (x) which minimizes cost(x,y) progress(x,y,d)

where cost(x, y) represents the "cost" of x to send the message to its neighbor y, and where progress(x, y, d) is the progress in the routing task. Basically, the progress can be expressed as the difference dist(x, d)dist(y, d) where dist(u, v) is the "distance" between nodes u and node v. For this protocol to work, the current node has to limit its choices to neighbors with positive progress.

In this paper, we consider two cost functions: cost 1 (x, y) = 1 when node x is not able to adapt its communication range and cost e (x, y) = |xy| α + c otherwise. The distance |xy| is the geographic distance between node x and node y.

For the distance function dist, we consider three different functions. The first one, called "Hamming distance", defined by dist h (x, y) = m i=1 |x iy i |. The second function, called "Euclidean distance", defined by dist e (x, y) = m i=1 (x iy i ) 2 . The last distance function is called "Square distance and it is simply defined by dist se (x, y) = dist e (x, y) 2 .

By Combining the functions Γ, the various distance metrics dist and the cost functions, we obtain a family of protocols. For instance, the triplet (Γ id , dist h , cost 1 ) corresponds to protocol VCap. For the other protocols, we consider the cost function cost e , which is omitted for clarity, and we use the following abbreviated notation for each protocol: VCost for (Γ id , dist h ), VeCost for (Γ id , dist e ), VseCost for (Γ id , dist se ), CVCCost for (Γ vcv , dist h ), CVCeCost for (Γ vcv , dist e ) and CVCseCost for (Γ vcv , dist se ).

Experimental Results

To eliminate the effect of the MAC layer on our results, we use our own C simulator that assumes an ideal MAC layer, i.e. no interferences and no packet collisions. The simulated network can be described as follows. Nodes are randomly deployed in a 1 × 1 square using a Poisson Point Process (node positions are independent) with different density (or mean number of nodes per surface unit) λ. We assume that these nodes have the same transmission range, R = 0.1, therefore, two nodes are connected by an edge if and only if their Euclidean distance is at most R (assuming a Unit Disk Graph [START_REF] Clark | Unit disk graphs[END_REF]). Finally, a set of landmarks (at least 2) is randomly selected from the network nodes.

We run the simulator using the routing algorithms described in Section 2 for the same samples of node distribution and study their performance under the family of protocols described in Section 3. The performance measures of interest in this work are the hit rate and the energy consumption. We also investigate the effect of the number of landmarks deployed on the behavior of the protocols.

• Hit rate. We define the success or hit rate as the proportion of time the routing is successful (a packet actually reaches its final destination). We compute the success rate achieved by all the cost over progress based routing protocols and the results obtained are found to be within a 95% confidence interval. In Figure 1, we plot the hit rate for two different values of λ. Clearly, the protocols using dist h as the distance function (Vcost and CVCCost) achieve a better hit rate than the alternatives, independently of the node distribution density λ. Therefore, we focus on these protocols and compare them to protocols using geographic distance (MFR and Cost-Progress Routing protocols) and to VCap (MFR using Hamming distance over hop count coordinates).

As Figures 2(a) and 2(b) show, our protocols achieve the same hit rate as VCap. Note that our results show that VCap achieves a lower hit rate than the results published in [2]. The reason for this difference is that our work is based on a more general framework i. e., we randomly select the landmarks from the network nodes compared to the more unrealistic scenario of VCap where the landmarks are positioned on a circle around the network nodes. Figure 2 also shows that for high values of λ, the hit rate is lower than for low values of λ which is not expected (dense networks should provide higher rate of routing success). However, our simulation results show that dense networks suffer from the redundant coordinate dilemma (high percentage of nodes with the same virtual coordinates), as Figure 3 shows. Clearly, as the number of landmarks increases, the number of nodes having the same coordinates decreases. This fact contributes to the low hit rate as we illustrate by the following example. Consider the source node A A=(

4. Illustration of failed routing due to the presence of nodes with the same virtual coordinates in the network.

in Figure 4, that is trying to send a packet to destination node E. Assuming a greedy routing policy, node A successfully sends the packet to node B since it is closer than itself to E; for the same reason, B sends the packet to node C. However, C does not send it to its (only) neighbor D, which has the same virtual coordinates as node B, since C is closer to E than D. Thus the routing fails and the packet never reaches its final destination.

• Energy consumption. To compare the performance of the various protocols in terms of energy efficiency, we compute the energy consumption only for successful routing paths. Figure 5 shows that VCost outperforms all the routing protocols that use dist h as a distance measure, CVCCost and MFR being the worst performing protocols. This conclusion is independent of the network density and the number of landmarks deployed (see Figures 5(a) and 5(b)).

To further understand this result, we compute for each protocol the routing path from a given source to a given destination (see Figure 6). Our results show that VCap and MFR take long edges in order to move as close as possible to the destination while Cost-Progress based routing and VCost try to minimize their energy consumption by following edges with length as close as possible to the optimal length. CVCCost on the other hand, follows very short and long edges in its route. It also has the tendency to follow paths with high number of hops compared to the other protocols. This fact makes it the worst protocol in terms of energy savings. • Effect of the number of landmarks on the performance measures. Figure 7 shows that for various values of λ, as the number of landmarks increases, the performance measures achieve better results. This is obviously due to the fact that adding landmarks improves the estimation of the virtual coordinates, as claimed in [1], and increases the percentage of unique virtual coordinates in the network. A drawback of increasing the number of landmarks however, is the increase of the prerouting complexity since the larger the number of deployed landmarks, the higher the dimensionality of the coordinates. Moreover, the routing protocol ends up with more paths to compute toward the landmarks in order to determine the virtual coordinates.

Figure 7 shows that our protocols achieve the best results compared to the other protocols independently of the number of landmarks.

Conclusion and Future Work

In this paper, we show how to introduce energy efficiency in position-based routing over virtual coordinates. We compare several routing protocols based on different methods to compute the virtual coordinates. We show through simulation that our protocol VCost improves significantly energy consumption and preserves the small percentage of successful routings. In our future work, we plan to test our protocol on more general networks (i. e., networks with obstacles) and to study the computation of virtual coordinates in order to increase both the success rate and the energy savings. Another interesting problem to consider is self-organization and election of landmarks.

  δ = 30, λ = 1000 1. Hit rate computed for different coordinate systems, distance evaluations and network density λ. δ is the average number of neighbors per node.

Figure 2 .

 2 Figure 2. Hit rate of the family of protocols using dist h .

Figure 3 .

 3 Figure 3. Number of nodes that have the same virtual coordinates computed for the family of protocols for various network density λ.

Figure 5 .

 5 Figure 5. Energy consumption of the family of protocols using dist h .

Figure 6 .

 6 Figure 6. Path followed between a pair of nodes by each protocol when λ = 1000. Landmarks are shown in red. In plots (a) and (b) we use geographic coordinates and in plots (c), (d) and (e) we use virtual coordinates.

Figure 7 .

 7 Figure 7. Hit rate and energy consumption of the family of protocols as a function of the average node degree, for 3 and 10 landmarks.

  These results are consistent for various values of network density λ and different source/destination pairs.

		1
									Cost Progress
										MFR
		0.9					VCost with 3 landmarks CVCCost with 3 landmarks
								VCAP with 3 landmarks
		0.8					VCost with 10 landmarks CVCCost with 10 landmarks
								VCAP with 10 landmarks
		0.7
	Success Rate	0.4 0.5 0.6
		0.3
		0.2
		0.1
		0
		14	16	18	20	22	24	26	28	30	32
					Mean number of neighbors
					(a) Hit Rate
		0.00055
									Cost Progress
										MFR
								VCost with 3 landmarks
		0.0005					CVCCost with 3 landmarks
								VCAP with 3 landmarks
								VCost with 10 landmarks
							CVCCost with 10 landmarks
		0.00045						VCAP with 10 landmarks
	Energy consumption	0.0003 0.00035 0.0004
		0.00025
		0.0002
		0.00015
		14	16	18	20	22	24	26	28	30	32
						Mean number of neighbors
				(b) Energy Consumption


F Burgy

Eric Catoire

E Constant

Mével

C Valentin

K Veyrinas

J Vabék

D Descamps

C Péjot

F Catoire

E Mével

Optics-Free Focusing and Application to Spectral Filtering of XUV Beam

Optics-free ffocusing and application to spectral filtering of XUV beam

Introduction

Ultrafast phenomena studies rely mainly on pump-probe experiments [START_REF] Marciniak | XUV excitation followed by ultrafast non-adiabatic relaxation in PAH molecules as a femto-astrochemistry experiment[END_REF]. XUV beam produced by high-order Harmonic Generation (HHG) are commonly used as a table-top source of attosecond pulses, allowing high temporal resolution. In order to perform XUV-pump-XUV-probe experiments and non-linear optics in the XUV range [START_REF] Makos | A 10-gigawatt attosecond source for non-linear XUV optics and XUVpump-XUV-probe studies[END_REF], the generation of intense XUV radiations becomes indispensable but remains a challenge. This can be done by increasing the energy, shortening the duration of the XUV pulse, or by controlling the focusing properties of the XUV beam which strongly depend on the harmonic order. Recently, we have demonstrated the possibility of generating harmonics as either diverging or converging beams showing the ability to control the XUV beam spatial properties [START_REF] Quintard | Opticsless focusing of XUV high-order harmonics[END_REF][START_REF] Veyrinas | Optics-free focusing down to micrometer spot size and spectral filtering of XUV harmonics[END_REF]. This so-called optics-free focusing results from the control of the XUV wavefront in the generating process. We propose to use this technique to control the spatio-temporal properties of the XUV beam.

First, spatial characteristics measurements of XUV beams by the technique of the spectrally resolved wavefront characterization of the XUV radiation are presented. This constitutes the direct measurement of coherent focusing. Second, as a consequence of coherent focusing, spectral filtering of harmonics without using any optics is demonstrated. Then we describe the theoretical model used to compare with experimental results. This model will allow the determination of the temporal structures of the XUV pulse.

Spatial characteristics measurements of XUV beam

The experimental setup has been described in details in [START_REF] Quintard | Opticsless focusing of XUV high-order harmonics[END_REF]. We used 9mJ of laser energy of the Terawatt Ti:sapphire laser system delivering 800-nm, 100-mJ, 40-fs pulses at a 10-Hz repetition rate. The infrared (IR) beam spatial quality is ensured by spatial filtering and wavefront optimization by a deformable mirror (ISP System), coupled to a wavefront sensor (Imagine Optic). The beam is then focused by a 2-m focal length spherical mirror leading to an 85 µm focused laser beam waist (peak intensity of 4 10 14 Wcm -2 at focus) in a gas jet of neon. The gas jet can be moved longitudinally over 15 cm around IR focus. Generated high-order harmonics are analyzed by an XUV spectrometer and the spatially resolved spectra are analyzed 2.9 m after the laser focus. A movable 140-µm-diameter pinhole can be inserted 37 cm after the IR focal plane to characterize the intensity profile and wavefront of each harmonic.

Characterization of radii of curvature for each dispersed harmonic beam has been performed using the SWORD (Spectral Wavefront Optical Reconstruction by Diffraction) technique [START_REF] Frumker | Frequency-resolved high-harmonic wavefront characterization[END_REF]. The measurement principle has been described in [START_REF] Veyrinas | Optics-free focusing down to micrometer spot size and spectral filtering of XUV harmonics[END_REF]. Fig. 1 presents the results of the SWORD measurement for harmonics H31, H39 and H47. Fitting the measured XUV intensity profiles (a) and reconstructed spatial phases (b) by Gaussian and quadratic functions, respectively, provides the beam size wq and the radius of curvature Rq of each harmonic at the pinhole plane. We find that the beam sizes and wavefront curvatures change with the harmonic order and gas jet position. We observe that the spatial profile is close to Gaussian profile and that the phase is quadratic. Under these conditions, we can infer that the XUV beam propagates like a Gaussian beam and retrieve both the size wq,0 and the position zq,0 of the waist of the considered harmonic order q, for each position of the gas jet. As pointed out in Veyrinas et al. [START_REF] Veyrinas | Optics-free focusing down to micrometer spot size and spectral filtering of XUV harmonics[END_REF], harmonic waist sizes and positions can be very different for different harmonic orders, depending on the gas jet positions. More precisely, we have determined that for a gas jet far before the IR focus (zjet = -40 mm), the waists are real and are positioned well after the IR focus, demonstrating convergent beams focused in a few micrometer size spots. On the contrary, XUV beams are divergent for zjet near the IR focus and waists can be virtual [START_REF] Veyrinas | Optics-free focusing down to micrometer spot size and spectral filtering of XUV harmonics[END_REF]. These measurements are in good qualitative agreement with the simulated results reported by Quintard et al. [START_REF] Quintard | Opticsless focusing of XUV high-order harmonics[END_REF] where harmonic optics-free focusing was demonstrated by means of the of the XUV beam spatial chirp induced by the spatial chirp of the IR.

Spectral filtering without any XUV optics

We demonstrate a direct application of the XUV beam properties controlled by performing XUV spectral filtering without using any XUV optics. This is realized by comparing the spatially-resolved HHG spectrum obtained with the pinhole centered on the pathway of the harmonic beam and the spectrum obtained without the pinhole. The transmittance (T) is then defined as the ratio of the HHG spectra after integrating over the vertical coordinate with and without pinhole. Assuming the generation in a thin medium (when the length of the generation medium is smaller than Rayleigh range of the fundamental laser beam), phase-matching effect can be treated separately. The spatial distribution of the XUV beam in far field is expressed by a Fraunhoffer integral where the source term is obtained by solving the Time-Dependent Schrödinger Equation (TDSE) [START_REF] Catoire | Complex structure of spatially resolved high-order-harmonic spectra[END_REF]. From this model, we determine the size of each harmonic beam on the pinhole and then calculate the transmittance through it as realized experimentally. Left panel in Fig. 2 displays the measured transmittance of harmonics H29 to H47 for zjet= -58, -36, -20 mm and clearly shows that the characteristics of this filter are fully tunable by adjusting the gas jet position with respect to the IR focus. Low-pass (black curve), high-pass (blue curve) and broadband (red curve) filters are obtained. In all cases, the high spectral selectivity and contrast ensure a proper selection of a group of harmonics. This can be compared to simulation results shown in right panel in Fig. 2 where transmittance as a function of harmonic order for zjet = -5, -10, -15, -20, and -25 mm is plotted. For large negative values of zjet, the transmittance increases with harmonic order as for zjet nearer to IR focus, the transmittance decreases with harmonic order. For intermediate jet positions, the transmittance presents a bell like shape ranging from 20% to 100 %. Theses curves can be compared with experimental data, showing an overall agreement. Finally, this spectral filtering is accompanied with a strong rejection of the IR fundamental beam (T<1 %) avoiding the use of metallic filters that usually reduce significantly the XUV signal. We point out here that the present approach does not require the use of any XUV optics and thus does not suffer from limitations inherent to this energy range and encountered with traditional optical technique. We further simulate the spatially resolved spectra and the temporal structure of attosecond pulses for the experimental conditions. On Fig. 3, the spatially resolved spectra for the case of gas jet position = -15 mm before IR focus with (b) and without (a) filtering are presented. The temporal profile of the XUV beam for different values of radii  in the case of free propagation (c) and with filtering (d) are also plotted. The first observation is the effective size reduction of the waist of harmonics. The waist of harmonics also presents much less fluctuations from one harmonic to the next. The radius  spans an intensity range which covers the full spatial evolution of the XUV beams. In Fig. 3d, we observe a much more regular evolution of the temporal profile with radius  as compared to the unfiltered case of Fig. 3c. In particular, for = 250 µm, a double hump appears in the temporal profiles in Fig. 3c due to the contribution of long trajectories which are not filtered in that case. We have demonstrated the same features for other gas jet positions, the main difference being essentially quantitative.

Conclusion

We have experimentally demonstrated spatial properties control of XUV harmonic beams as a function of generating medium positions relative to IR focus, and observed that optics-free focusing of high-order harmonics can be obtained in specific conditions. We have also demonstrated experimentally and theoretically adjustable XUV spectral filtering with high contrast without any resorting XUV optics. We have developed a model that shows that spatio-temporal structure homogeneity will also benefit from the filtering, leading to better control of the spatio-temporal structure of attosecond pulses.

Fig. 1 .

 1 Fig. 1. Measured intensity profile (dots) and Gaussian fit (line) (a) and reconstructed spatial phase (dots) and quadratic fit (line) (b) of harmonics H31 (blue), H39 (orange) and H47 (yellow), for zjet = -35 mm. We obtain wq = 309, 240, and 174 μm and Rq =363, 396, and 382 mm for harmonics H31, H39 and H47, respectively.

Fig. 2 .

 2 Fig. 2. Left panel: Measured transmittance of harmonics H29 to H47 for zjet=-58 (blue), -36 (red) and -20 mm (black). Right panel: Transmittance versus harmonic order for five gas jet positions computed with 1D-TDSE model.

Fig. 3 .

 3 Fig. 3. Spatially resolved spectra for free propagation (a) and with filtering (b) at 1m from IR focus. White lines correspond to radii at which temporal structures are depicted in (c) for free propagation and (d) with filtering.