Keywords: réseaux sans fil, codage de réseau, diffusion, multi-sauts, coupe minimale, hypergraphe

Performance de la diffusion par codage de réseau dans les réseaux sans fil larges et homogènes

Résumé : Nous présentons un protocole efficace pour la diffusion dans les réseaux sans fil, utilisant le codage de réseaux: nous introduison une sélection de débit simple, et nous analysons sa perfromance (par le calcul de la coupe minimale). Par diffusion, nous entendons l'envoi de paquets de données d'une source unique à tous les autres noeuds du réseau, et notre métrique d'efficacité est le nombre de transmissions necessaires pour transmettre un packet de la source vers chacune des destinations. Nous traitons ce problème pour certain cas spéciaux de réseaux homogènes du plan euclidien: les réseaux sans fils organisés en treillis, et les graphes disque-unité denses. Nos résultats sont basés sur le principe simple de: "Débit supérieur pour les noeuds exceptionels, Débit identique pour les autres noeuds" (Increased Rate for Exceptional Nodes, Identical Rate for Other Nodes: IREN/IRON). Avec ce choix de débit, nous donnons la valeur du débit maximal de diffusion dans le réseau: notre résultat central est la preuve de la valeur de de la capacité de la coupe minimale pour de tels réseaux.

En particulier, nous demontrons que, pour nos scénarios, le codage de réseau a une performance qui dépasse celle qui puisse être obtenue sans codage de réseau.

Seminal work from Ahlswede, Cai, Li and Yeung [START_REF] Ahlswede | Network Information Flow[END_REF] has introduced the idea of network coding, where intermediate nodes are mixing information from different flows (different bits or different packets): one result was that, in the general case, network coding may achieve the maximum information-theoretic capacity for multicast. It is higher, in some cases, than what classical store-and-forward routing could achieve. One logical domain of application is wireless sensor networks, and indeed network coding has been used in wireless networks. In particular, some results include a generalization of the results in [START_REF] Ahlswede | Network Information Flow[END_REF]: when the loss rates and the capacity of the links are known and fixed, the maximal multicast capacity of the wireless network, can be computed, as shown in [START_REF] Gowaikar | On the capacity of wireless erasure networks[END_REF][START_REF] Dana | Capacity of Wireless Erasure Networks[END_REF]. Essentially, for one source, it is the min-cut of the network (see section 3.1) from the source to the destinations, as for wired networks [START_REF] Ahlswede | Network Information Flow[END_REF], but considering hypergraphs rather than graphs.

However in wireless sensor networks, a primary constraint is not necessarily the capacity of the wireless links: because of the limited battery of each node, the limiting factor is the cost of wireless transmissions. Hence a different focus is energy-efficiency, rather than the maximum achievable broadcast rate:

• given one source, minimize the total number of transmissions to achieve the broadcast to destination nodes.

With network coding, the problem turns out to be solvable in polynomial time: for the stated problem, [START_REF] Wu | Minimum-energy multicast in mobile ad hoc networks using network coding[END_REF][START_REF] Lun | Minimum-Cost Multicast over Coded Packet Networks[END_REF] describe methods to find the optimal transmission rate of each node with a linear program. Once the optimal rates are computed,the performance can be asymptotically achieved with distributed random linear coding for instance [START_REF] Ho | The Benefits of Coding over Routing in a Randomized Setting[END_REF][START_REF] Lun | On coding for reliable communication over packet networks[END_REF]. However, this does not necessarily provide direct insight about the optimal rates, or the optimal cost: those may be obtained by solving the linear program on instances of networks.

Another angle to tackle this problem, would be to explicitly specify the network coding protocol, based on some intuitive foresight, and be able to compute the performance ; for instance [START_REF] Fragouli | A Network Coding Approach to Energy Efficient Broadcasting[END_REF] starts with exhibiting an optimal algorithm for some simple regular networks.

In general specifying the network coding protocol reduces to specifying the transmission rates for each node [START_REF] Lun | Further Results on Coding for Reliable Communication over Packet Networks[END_REF]. Then the cost is known, and the central element for computing the performance is the estimation of the min-cut of the network. Some results exist about the expected value of the min-cut on some classes of networks: for instance [START_REF] Ramamoorthy | On the capacity of network coding for random networks[END_REF] explored the multicast capacity networks where a source which is two hop from the destinations, through a one network of relay nodes ; [START_REF] Aly | Bounds on the Network Coding Capacity for Wireless Random Networks[END_REF] studied the some classes of unit disk graphs in the plane.

Our approach in a similar spirit. For large-scale sensor networks, one assumption could be that the nodes are distributed in an homogeneous way, and a question would be: "Is there a simple near-optimal rate selection ?" Considering the results of min-cut estimates for random graphs [START_REF] Ramamoorthy | On the capacity of network coding for random networks[END_REF][START_REF] Aly | Bounds on the Network Coding Capacity for Wireless Random Networks[END_REF][START_REF] Costa | Dual Radio Networks: Capacity and Connectivity[END_REF], one intuition is that most nodes have similar neighborhood, hence the performance, when setting an identical rate for each node, deserves to be explored. This is the starting point of this paper, and we will focus on homogeneous networks, such as lattice graphs, or random geometric graphs:

1. We introduce a simple principle where most nodes have the same transmission rate:

IREN/IRON principle (Increased Rate for Exceptional Nodes, Identical Rate for Other Nodes).

2. We give a proof the min-cut for some lattice graphs (modelled as hypergraphs).

3. We deduce an estimate of the min-cut for unit disk hypergraphs. [START_REF] Wu | Minimum-energy multicast in mobile ad hoc networks using network coding[END_REF]. We show that this simple rate selection achieves "near optimal performance", in some classes of homogeneous networks, based on min-cut computation.

5. We illustrate the results obtained by simulations.

The rest of this paper is organized as follows: section 2 details the network model and related work; section 4 describes the main results (min-cut and near optimality) ; section 5 gives proofs of min-cut and section 7 concludes.

Network Model

In this article, we study the problem of broadcasting from one source to all nodes. We will assume an ideal wireless model, infinite capacity: lossless wireless transmissions without collisions or interferences. We also assume that every node has an infinite queue.

Our focus is on large-scale wireless sensor networks. Such networks have been modeled as unit disk graphs [START_REF] Clark | Unit disk graphs[END_REF] of the plane, where two nodes are neighbors whenever their distance is lower than a fixed radio range ; see figure 1(a) the principle of unit disk graphs.

An important assumption is that the wireless broadcast advantage is used: each transmission is overheard by several nodes. As a result the graph is in reality a (unit disk) hypergraph 1 : (it is slightly different from random geometric graphs [START_REF] Penrose | Random Geometric Graphs[END_REF] where links are independent). Precisely, the sensor networks considered will be:

Random unit disk graphs with nodes uniformly distributed (Fig. 1(a))

Unit disk graphs with nodes organized on a lattice (Fig. 1(b)), special case of the following:

Lattice sensor networks where the neighborhood of one node is not necessarily the set of nodes within disk like on Fig. 2(a), but may any arbitrary set R such as the one on Fig. 2(b).

Hence for lattice sensor networks, the set R is fixed for one origin node, and all the nodes of the lattice have a similar neighborhood by translation. For simplicity in later proofs, R must include the node itself ((0, 0) ∈ R). The following requirement should also be met: The starting point of network coding is the celebrated work from [START_REF] Ahlswede | Network Information Flow[END_REF], showing that coding in networks could achieve maximum broadcast capacity (given by the min-cut ), while in the general case, it is out of reach of traditional transmission methods (i.e. without network coding).

Requirement 1 {(-1, 0), (1, 0), (0, -1), (0, 1)} ⊂ R
It is possible to model the wireless network as an hypergraph, as done in this section. The benefits of using an hypergraph model, is that it models closely the wireless broadcast feature of wireless network, and that there exists a powerful generalization of the results of [START_REF] Ahlswede | Network Information Flow[END_REF] for network coding for normal graphs. It expresses the maximum broadcast capacity of the graph, when the rates C v are fixed:

The maximum broadcast (multicast) rate for a source s to all destinations, is given by the minimum of the maximum flow capacity from the source to every individual destination of the network, of the hypergraph [START_REF] Gowaikar | On the capacity of wireless erasure networks[END_REF][START_REF] Deb | Network Coding for Wireless Application: A Brief Tutorial[END_REF][START_REF] Dana | Capacity of Wireless Erasure Networks[END_REF] 2 . This is the max-flow which is also to be the min-cut.

Of course, this requires the definition of an hypergraph, in section 3.1.1, and of the max-flow/min-cut, in section 3.1.2.

Hypergraph Notation

Given any set of nodes in a network where the same transmission can reach several neighbors simultaneously, such as with wireless networks, it is possible to describe the connectivity graph as an (oriented) hypergraph, following the formalization used in [START_REF] Gowaikar | On the capacity of wireless erasure networks[END_REF][START_REF] Dana | Capacity of Wireless Erasure Networks[END_REF] and [START_REF] Deb | Network Coding for Wireless Application: A Brief Tutorial[END_REF].

An hypergraph is a graph where edges are replaced by hyperedges: instead of having one edge linking one head node to one tail node, an hyperedge links one head node to several tail nodes. Precisely, Following the formalization of [START_REF] Gowaikar | On the capacity of wireless erasure networks[END_REF][START_REF] Dana | Capacity of Wireless Erasure Networks[END_REF] and [START_REF] Deb | Network Coding for Wireless Application: A Brief Tutorial[END_REF], the hypergraph and its min-cut with respect to source s are defined as follows:

• Hypergraph: G = (V, H), with V and H defined as follows:

• Nodes: V = {v i , i = 1, . . . n}, set of vertices (nodes) of the graph (source is s ∈ V) • Hyperedge: h v = (v, H v ) where H v ⊂ V is the subset of nodes which are reached by one transmission of node v Hence H v is the set of neighbors of node v. • Set of hyperedges: H = {h v : v ∈ V} • Rate: Each node v emits on the hyperedge (v, H v ) with a fixed rate C v .

Min-cut of an Hypergraph

Let us consider the source s, and one of the multicast (broadcast) destinations t ∈ V.

A cut is a defined by a partition of the set of vertices V in two sets S, T such as s ∈ S and t ∈ T . Precisely, because it depends on s and t, it is an s-t cut.

Let Q(s, t) the set of the all the s-t cuts (S, T ). We denote ∆S, the set of nodes of S for which there is at least one node of T within range. Formally, ∆S is:

∆S {v ∈ S :

H v ∩ T = ∅} (1)
The capacity of the cut is defined as the maximum rate from the nodes in S to the nodes in T . That is, the capacity of the cut is:

C(S) v∈∆S C v (2)
It is the maximum rate that nodes in the set T taken as a whole, can receive from the nodes in the set S (also taken as a whole). Note that this expression differs from the capacity of a cut when the topology is not an hypergraph, but a graph with simple edges: here, if a node v ∈ ∆S can transmit to several nodes of T , its contribution to the capacity is counted only "once", because it is the same transmission (hyperedge), hence same information, that reaches the different nodes.

With this definition of an st cut, the st min-cut is the following:

The min-cut between the source s and the destination t is denoted C min (s, t), and is the minimum of the capacity of all the st cuts:

C min (s, t) min (S,T )∈Q(s,t) C(S) (3)
When multicasting, there are several destinations t for the same source s, hence the min-cut is the minimum of the st min-cuts for all t. When broadcasting to all nodes, the min-cut is the minimum for all nodes other than s, and we denote the broadcast min-cut C min (s):

C min (s) min t∈V\{s} C min (s, t) (4)
As indicated in section 3.1, C min (s) is the maximum broadcast rate with which the source s can transmit to all the nodes in the network.

Related Work

In general specifying the network coding protocol reduces to specifying the transmission rates for each node [START_REF] Lun | Further Results on Coding for Reliable Communication over Packet Networks[END_REF].For minimum-cost multicast, [START_REF] Lun | Minimum-Cost Multicast over Coded Packet Networks[END_REF] contains several methods (centralized or distributed), to compute the optimal rate selection.However This article is in the spirit of [START_REF] Fragouli | A Network Coding Approach to Energy Efficient Broadcasting[END_REF] which starts with exhibiting an energy-efficient algorithm for simple networks. The central element for computing the performance is the estimation of the min-cut of the network. We are inspired by the existing techniques and results about the expected value of the min-cut on some classes of networks: for instance [START_REF] Ramamoorthy | On the capacity of network coding for random networks[END_REF] explored the multicast capacity networks where a source is two hop from the destinations, through a network of relay nodes ; [START_REF] Aly | Bounds on the Network Coding Capacity for Wireless Random Networks[END_REF] studied some classes of random geometric graphs. Recently, [START_REF] Costa | Dual Radio Networks: Capacity and Connectivity[END_REF] gave bounds of the min-cut of dual radio networks.

Practical Implementation of Wireless Network Coding

It has been shown that a simple form of coding, linear coding [START_REF] Li | Linear network coding[END_REF], (using linear combinations of data symbols belonging to Galois fields F p -see also [START_REF] Koetter | An algebraic approach to network coding[END_REF]), is sufficient to achieve the bounds of [START_REF] Ahlswede | Network Information Flow[END_REF]. Furthermore, [START_REF] Ho | The Benefits of Coding over Routing in a Randomized Setting[END_REF] presented one method which does not require coordination of (the coding at) the nodes, by introducing random linear coding and by showing that sufficient field size results in high probability of success. With random linear coding, the coding inside the network is no longer predetermined, since it uses random coefficients for the linear combinations.

These works set the path to practical foundations, which are described for instance in [START_REF] Chou | Practical Network Coding[END_REF][START_REF] Lun | On coding for reliable communication over packet networks[END_REF], and that are used for the simulations given in this article, in section 6.

Vectors: second, the packets are equally sized and are divided into blocks of symbols over a field F p : content = (s 1 , s 2 , ..., s h ). As in [START_REF] Chou | Practical Network Coding[END_REF], the packets include a header which is the list of coefficients. Hence the packet format is actually a vector of the format: (g 1 , g 2 , . . . , g D ; s 1 , s 2 , . . . , s h ).

Transmission: at any point of time, a node of the network has a list of vectors, linear combinations of initial source packets. When the node transmits, it generates a random linear combination of the vectors v 0 , v 1 , ..., v k it currently has:

i α i v i (where the (α i ) are random coefficients of F p ), and transmit it by wireless broadcasting.

Decoding: once a node has received D linearly independent vectors, it is able to decode the D packets of the generation.

The performance of wireless network coding, when the topology is fixed, and when each node as a fixed rate is know. As shown in [START_REF] Gowaikar | On the capacity of wireless erasure networks[END_REF], it turns out to be the min-cut of the wireless network, exactly like for wired networks, except that in this case the wireless network is modelled as an hypergraph.

Similarly the random distributed network coding (see algorithm 1) introduced in [START_REF] Ho | The Benefits of Coding over Routing in a Randomized Setting[END_REF], can be used, and achieve the maximum given by the min-cut.

Moreover, although the algorithm 1 assumes exponential interarrival for the packets, it has been shown that any transmission process with an average rate also achieve optimal rate [START_REF] Deb | Network Coding for Wireless Application: A Brief Tutorial[END_REF][START_REF] Lun | Further Results on Coding for Reliable Communication over Packet Networks[END_REF]. As described in the introduction, our approach is to choose an intuitive transmission rate for the each node: essentially, the same rate for most nodes. The rate selection is described in section 4.3. Then, we determine the maximum broadcast rate that can be achieved to transmit from the source to every node in the network as the min-cut of the hypergraph, for both lattice graphs in section 4.4. And finally, from the expression of the cost in section 4.5, we deduce asymptotic optimality (section 4.6).

Further Definitions

Consider a network inside a square area such as the one on figure 4.2. We denote L the edge Figure 3: Sample of network inside a square length of square G containing the network. We define the border area as the area of fixed width W near the edge of that square, and border nodes as the nodes lying in that area. The area L × L of G is partitioned into: ∆G, the border, with area

A ∆G = 4W (L -W ) on figure 4.2, the hatched area ∆G G i , the "interior" G i G \ ∆G, with area A Gi = (L -2W ) 2
Let M be the "expected" number of neighbors of one node. For a lattice network, it is exactly the number of points in the neighborhood R minus one (see Fig. 2(a) and 2(b)): M = |R| -1. For a random disk unit graph with N nodes, the radio range for disk unit graph is denoted ρ. M is related to the density µ = N L 2 and range as follows: we will take M as the expected number of neighbors M = πρ 2 µ = πρ 2 N L 2 of a node which is not in the border area.

One requirement on W is that all nodes in the interior of the square G i , are out of range of the outside of the network. This is achieved by making W sufficiently large ; for unit disk graph for instance, if the radio range is ρ, then W = ρ satisfies this requirement ; for lattice disk, if R is included in the disk of radius ρ, W = ρ is also a good choice.

Rate Selection with IREN/IRON

The principle IREN/IRON amounts to setting the following transmission rates: IREN (Increased Rate for Exceptional Nodes): the rate of transmission is set to M , for the following nodes: the source, and all the border nodes (the "exceptional" nodes).

IRON (Identical Rate for Other Nodes): every other node, except the source and all the border nodes, transmits with rate 1.

Notice that these rates can be globally scaled by the same amount: the cost and the achieved broadcast rate would linearly increase, and the efficiency would be identical.

Rationale for IREN/IRON

.

There are some reasons for the above rate selection. The rationale is the following: we start by imagining an average transmission rate of 1 for mode nodes, the "IRON" part. Then most nodes will receive an average rate of M transmission from their neighbors. With or without network coding, this implies that the maximum achievable broadcast reception rate with this setting is upper-bounded by M . Now there are two additional issues: the source and the border nodes. For the first, in order to achieve a broadcast reception rate equal to M in the network, the source need to transmit at least with that rate, otherwise it would be a bottleneck.

For the second issue, nodes near the border, one can notice that they have smaller neighborhoods (less than M neighbors). Nevertheless, if they are connected to the network they have at least one neighbor: by setting a rate of M for that neighbor, they are guarantee to received a sufficient rate. Since, in large networks, border nodes represent a minority of nodes, this could have (and does have) limited impact on the efficiency.

After following the steps of the rationale, the main issue is determine whether this insights are sufficient for achieving broadcast rate of M . In this article, we prove that it is the case (see section 4.4) for lattice network, and asymptotically the case for dense unit disk graphs.

However note that this property is not true for general graphs, and that the rate selection hinted here is not absolutely optimal.

Performance: Min-Cut (Achievable Broadcast Rate)

The essence of our main result is the following: Property 1 The min-cut of a lattice graph with the rate selection IREN/IRON is exactly equal to C min = M (with M = |R| -1). See section 5.1 for the proof of this property in Th. 2.

For random unit disk graphs, by mapping the points to an imaginary lattice graph (embedded lattice), as an intermediary step, we are able to find bounds of the capacity of random unit disk graphs. This turns out to be much in the spirit of [START_REF] Costa | Dual Radio Networks: Capacity and Connectivity[END_REF].

INRIA

Near Optimal Broadcast with Network Coding in Large Homogeneous Wireless Networks13

Precisely we prove the following property: Property 2 The min-cut C min (s) of the source s of a random unit disk graph V, is bounded with the min-cut C (L) min (s L ) of some point of the embedded lattice s L as follows:

C min (s) ≥ m min C (L) min (s L )
where m min is a random variable related to the number of nodes of the graph mapped to one point of the lattice.

Refer to section 5.2.3, Th. 3 for details, the property is only quoted here to give this general implication: under some assumptions and definitions, is m min C (L) min (s L ) actually "close" to M . This is used to deduce an asymptotic result for unit disk graphs: Property 3 Assume a fixed range. For a sequence of random unit disk graphs (V i ), with sources s i , with size L → ∞ and with a density M → ∞ such as M = Ω(L θ ), for any fixed θ > 0, we have the following convergence in probability:

Cmin(s) M p → 1
This property is proved in section 5.2, Th. 5.

Performance: Transmission Cost Per Broadcast

Recall from section 1, that the metric for cost is the "number of (packet) transmissions per a (packet) broadcast from the source to the entire network".

The energy cost of broadcasting with IREN/IRON rate selection, can equivalently computed from the rates as the ratio of the number of transmissions per unit time to the number of packets broadcast into the network per unit time. Let us denote E cost this cost per broadcast. Notice that the number of packets broadcast per unit time with (adequate) network coding is the min-cut C min (s). Then E cost is deduced from the min-cut C min , from the border and interior the areas A ∆G , A Gi , the associated node rates (along with the rates of the nodes of in the border and in the interior) and the node density µ. For fixed W , M, L → ∞:

E cost = 1 C min µL 2 (1 + O( 1 L ) + 4M W L (1 + O( 1 L ))
For random unit disk graphsV, E cost is an expected valueE cost = E(E cost (V)), and µ = N L 2 . For a lattice, µ = 1.

Near Optimal Performance for Large Networks

The sections 4.4 and 4.5 gave the performance and cost with the IREN/IRON principle. As indicated previously, for a given (hyper)graph, the optimal rate selection, and the optimal (minimum-cost) total rate of the network may be computed with a linear program [START_REF] Lun | Minimum-Cost Multicast over Coded Packet Networks[END_REF]. The optimal cost is not immediately computed and in this section an indirect route is chosen, by using a bound.

Assume that every node has at most M max neighbors: one single transmission can provide information to M max nodes at most. Hence in order to broadcast 1 packet to all N nodes, at least E bound = N Mmax transmissions are necessary. This is compared to the E cost transmissions per packet broadcast. W.r.t. this bound, let the relative cost be: E rel-cost = Ecost E bound ≥ 1, We will prove that E rel-cost → 1 for some (sequences of) networks: 4.6.1 Lattice Graphs.

For lattice graphs, we will assume a constant range, hence a constant neighborhood definition set R, and a constant M , number of neighbors for any node which is not in the border.

The width of the border W is such as, the border includes all nodes that are at distance lower than 2 from the border. Since the size of the neighborhood is kept constant, the width of the border stays also constant. For lattice graphs, W and the neighborhood R are kept fixed (hence also M = |R| -1), whether it is a unit disk lattice graph or not), and only the size L of the network increases to infinity. The number of nodes is N = L 2 , and µ = 1. The maximum number of neighbors M max is exactly M max = M .

From section 4.5, and from property 1, we have:

E rel-cost = E cost M max N = = (1 + O( 1 L ) + 4M W L (1 + O( 1 L )) = 1 + O( 1 L )
4.6.2 Random Unit Disk Graphs.

For random unit disk graphs, first notice that an increase of the density M does not improve the relative cost E rel-cost (due to the cost of border nodes). Now consider a sequence of random graphs, as in property 3, with fixed radio range ρ, fixed border width W , size L → ∞ and with a density M → ∞ such as M = Ω(L θ ), for some arbitrary fixed θ > 0, with the additional constraint that θ < 1. We have:

E rel-cost = E cost M max N = = M C min M max M µL 2 N 1 + O( 1 L ) + 4M W L (1 + O( 1 L ))
Each of part of the product converges towards 1, either surely, or in probability: using property 3, we have the convergence of Cmin As a result we have:

E rel-cost p → 1
in probability, when L → ∞ 4.6.3 Near Optimality.

The asymptotic optimality is a consequence of the convergence of the cost bound E rel-cost towards 1. Since it is not possible to have a relative cost E rel-cost lower than 1, the rate selection IREN/IRON is asymptotically optimal for the two cases presented when L → ∞. Note that, this indirect proof is in fact a stronger statement than optimality of the rate selection in terms of energy-efficiency: it exhibits the fact that asymptotically (nearly) all the transmissions will be innovative for the receivers. Note that it is not the case in general, for a given instance of an hypergraph. It evidences the following remarkable fact for the large homogeneous networks considered: network coding may be achieving not only optimal efficiency, but also, asymptotically, perfect efficiency -achieving the information-theoretic bound for each transmission.

Proofs of the Achievable Capacity with Network Coding

In this section, we provide a formal proof for both property 1 and property 3 of section 4.4.

Proof for Lattice Graphs

Overview of the Proof

We first start with a proof for a lattice graph (such as the one Fig. 1(b)). Our objective is to compute prove Th. 2 (section 5.1.4), which indicates that for one source s, the min-cut C min of the lattice graph is M (with IREN/IRON).

In order to compute the global min-cut C min (s), we start with considering one destination node t in the network, and we will provide a bound the min-cut of the (hyper)-graph between s and t, that is, C min (s, t).

The proof proceeds as follows: we first link the capacity of the cut between nodes in S and nodes in T with the number of nodes in S which are neighbors of nodes in T . The number of these nodes decide the the capacity of the cut. Then we use the fact that the neighbors are obtained with a Minkowski sum. As a result, the inequality on on Minkowski sums could be applied to compute that number of neighbors. However with the effect of the border ∆L there are several special cases for applying the inequality, and each time, we prove that the capacity of the cut has the desired bound. The theorem will follow.

Preliminaries.

Let Γ be full, unbounded, integer lattice in n-dimensional space; it is the set Z n , where the lattice points are n-tuples of integers.

For lattice graphs, only points on the full lattice are relevant; therefore in this section, the notations L, L i , ∆L will be used, for the parts of the full lattice Γ that are in G, G i , ∆G respectively.Formally:

L = Γ ∩ G, L i = Γ ∩ G i , and∆L = Γ ∩ ∆G
The proof is based on the use of the Minkowski addition, and a specific property of discrete geometry (5) below. The Minkowski addition is a classical way to express the neighborhood of one area (for instance, see [START_REF] Lee | Polynomial/Rational Approximation of Minkowski Sum Boundary Curves[END_REF] and the figure 3(a), and figure 4 of that reference).

Given two sets A and B of R n , the Minkowski sum of the two sets A ⊕ B is defined as the set of all vector sums generated by all pairs of points in A and B, respectively:

A ⊕ B {a + b : a ∈ A, b ∈ B}
Consider a subset R of Γ, defining neighborhood, such as the ones on Fig. 2(a) and Fig. 2(b), with origin at the point (0, 0). We denote this set R as the lattice neighborhood definition set. Then the set of neighbors N (t) of one node t, with t itself, is:

N (t) ∪ {t} = {t} ⊕ R
This extends to the neighborhood of a set of points.

The neighbors of t are given with:

N (t) = ({t} ⊕ R) \ {t}
The rewriting of neighborhood in terms of Minkowski sum, has the advantage that several results of discrete geometry exists, including Brunn-Minkowski-Lysternik type inequalities.

The Brunn-Minkowski-Lysternik inequality gives a bound on the size of Minkowski sum of two compact sets of R n ; for integer lattice, there exist several integer variants, including the following one [START_REF] Gardner | A Brunn-Minkowski inequality for the integer lattice[END_REF]: for two subsets A, B of the integer lattice Z n ,

|A ⊕ B| ≥ |A| + |B| -1 (5)
where |X| represents the number of elements of a subset X of Z n

Bound on the capacity of one cut C(S).

Consider a lattice L and a source s. We start with the definition of C min (s, t) of (3): it requires considering the capacities of every s-t-cut S, T . Let C(S) be the capacity of such a s-t cut S, T ∈ Q(s, t).

We have the following lemma linking the capacity of the cut and the size of ∆S, the set of nodes of S which are neighbors of nodes of T Proof. With the definition in (2), we have:

C(S) = v∈∆S C v ⇒ C(S) ≥ v∈∆S 1, because with IREN/IRON, C v ≥ 1 ⇒ C(S) ≥ |∆S| which is the lemma. Lemma 2 If U ⊂ L i then U ⊕ R ⊂ L Proof:
The requirement on W in section 4.2 translates into: for any node x ∈ L i , {x}⊕R ⊂ L, hence the result.

Lemma 3 When the requirement 5.1.3 (in section 2) is met, for any two nodes U, V inside the border area, there exist a path using only points for the border area.

Proof: Recall that requirement for the set R which defines the neighborhood (requirement 1 in section 2) is the following:

The set R is a subset of Γ and should include the origin point (0, 0) as well as the 4 fours points which are immediate neighbors on the lattice: (1, 0), (0, 1), (-1, 0), (0, -1)

The requirement is that R should include the 4 immediate neighbors in the directions "left, right, up, and down". Since the border area is a connex area (using this reduced immediate neighborhood definition), the lemma follows.

Theorem 1 The capacity of one cut C(S) is such that:

C(S) ≥ M

Proof : There are three possible cases, either the set T has no common nodes with the border ∆L, or T includes all nodes of ∆L, or finally T includes only part of nodes in the border area. Formally:

|∆T | ≥ |R| -1 (6)
Recall that S and T form a partition of L ; and since ∆T is a subset of L, by definition without any point of of T , we have ∆T ⊂ S. Hence actually ∆T ⊂ ∆S (with the definition of ∆S in (2)). We can combine this fact with lemma 1, lemma 2, and (6), to get:

|C(S)| ≥ |R| -1 and the Th. 1 is proved for the first case.

Second case, ∆L ⊂ T : In this case, all the points of the border area are included in T , and as a consequence, the complementary set of points S has no nodes on the border, i.e. S ∩ ∆L = ∅. As a result S ⊂ L i .

We will show that a set S has equal or greater number of nodes which are neighbors of nodes in T than |R| -1. The method to prove it is similar with the method of the first case, but we consider neighborhood in the opposite way: we consider the nodes in S that are neighbors of nodes in T .

Let us denote S i the "interior" of S, that is, the set of nodes of S, which are not in within range of the set T Precisely: S i {x : x ∈ S and (x ⊕ R) ∩ T = ∅} By definition of ∆S in eq. ( 2), ∆S is the sets of nodes of S which are within range of the set T , and hence the subsets S i and ∆S form a partition of S Additionally, because S i ⊂ S and S ⊂ L i , we know with lemma 2 that S i ⊕ R ⊂ L. Since by definition of S, S i ⊕ R has no common element with T , and since S and T are a partition of L, the property follows:

3 S i ⊕ R ⊂ S (7)
Now there are two possibilities: either S i = ∅ or not.

• If S i = ∅, the implication is that S = ∆S, hence in particular, s ∈ ∆S. Going back to the definition of a cut in (2), we had:

C(S) = v∈∆S C v by definition, ⇒ C(S) ≥ C s because s ∈ ∆S ⇒ C(S) ≥ M because C s = M
with IREN/IRON. and the theorem 1 is proved for the second case, first possibility.

• Otherwise, S i = ∅. Starting from eq. 7, we had:

S i ⊕ R ⊂ S ⇒ |S| ≥ |S i ⊕ R|,
and as a result, with ineq. 5:

|S| ≥ |S i | + |R| -1 (8)
We had established that S i , ∆S was a partition of S,

hence ∆S = S \ S i ⇒ |∆S| ≥ |S| -|S i | ⇒ |∆S| ≥ |R| -1
Therefore with lemma 1, we deduce the capacity of the cut is such that: C(S) ≥ |R| -1 and the theorem 1 is proved for the second case, second possibility.

Third case: T ∩ ∆L = ∅ and ∆L ⊂ T : Again, since T and S are a partition of L, we deduce that S ∩ ∆L = ∅ ; hence both T and S have nodes in the border area ∆L.

Let us consider such nodes: u t ∈ T ∩ ∆L and u s ∈ S ∩ ∆L. With the lemma 2, there exist a path from u s to u t with only nodes in the border.

Let us start with u s , and iterate on the nodes of the path. Since u s is in S and u t is in T , we will ultimately find a node of the path u such that u is still in S and that its successor v in the path is not (is in T ). By definition of ∆S, u ∈ ∆S, and also u ∈ ∆L by property of the path.

Hence now, the contribution of u to the capacity of the cut C(S) can be used:

C(S) = v∈∆S C v (from def. 2) ⇒ C(S) ≥ C u , because u ∈ ∆S ⇒ C(S) ≥ M because C u = M
and the theorem 1 is proved for the third case.

Value of the Min-cut C min (s)

The results of the previous section immediately result in a property on the capacity of every s-t min-cut: Theorem 2 For any t ∈ L different from the source s:

C min (s, t) = M
; and as a result: C min (s) = M Proof: Let S min /T min be one cut with minimal capacity, one such as: C(S min ) = C min (s, t). Applying, the theorem 1, it appears that C(S min ) ≥ M , hence: C min (s, t) ≥ M Conversely let us consider a specific cut, S s = {s} and T s = L \ {s}. Obviously s has at least one neighbor, which has to be in T , hence ∆S = {s}. The capacity of the cut is C(S s ) = v∈∆S C v = C s = M and thus C min (s, t) ≤ M , and the theorem follows.

Proof of the Value of Min-Cut for Unit Disk Graphs

In this section, we will prove a probabilistic result on the min-cut, in the case of random unit disk graphs, using an virtual "embedded" lattice. The unit graph will be denoted V, whereas for the embedded lattice the notation of section 5 is used: L (along with ∆L and L i ). The elements of V are still called "nodes", but the elements of L are called "points" to emphasize the fact that they are virtual.

We will assume W > ρ (for instance W = 2ρ)

Embedded Lattice

Given the square area L × L, we start with fitting a rescaled lattice inside it, with a scaling factor r. Precisely, it is the intersection of square G and the set {(rx, ry) : (x, y) ∈ Z 2 }.

We will map the points of G to the closest point of the rescaled lattice L: Let us denote λ(x), the application which transforms a point u of the Euclidian space R 2 to its closest point of L. Formally, for u = (x, y)

∈ Z 2 , λ(x) (r⌊ x r + 1 2 ⌋, r⌊ y r + 1 2 ⌋)
For u ∈ L, λ -1 (u) is the set of nodes of V that are mapped to u. This area of R 2 which is mapped to a same point of the lattice, is a square r × r around that point. We choose r so that G fits exactly so that such squares are not truncated. This is achieved by taking the origin point of R 2 as the center of the square G, and by selecting r = 2k+1

L

where k is a positive integer.

Let u be a point of the lattice L, and let denote the m(u) the number of points of V that are mapped to u with g (they are in the square around u ; and m(u

) |λ -1 (u)|). Since V is a random graph, m(u) is a random variable.
Let us denote: m min min u∈L m(u) and m max max u∈L m(u)

Neighborhood of the Embedded Lattice

We start by defining the neighborhood R for the embedded lattice. The desired property is to have some relationship between neighborhood on the unit graph, and, after mapping, neighborhood on the embedded lattice.

For this, we choose R to be the points of the lattice inside a disk of radius ρ -2r:

R(r) = {(rx, ry) : (rx) 2 + (ry) 2 ≤ (ρ -2r) 2 ; (x, y) ∈ Z 2 }
The following lemma shows that we have the desired property.

Lemma 4 Let us consider two nodes of u, v of V that are mapped on the lattice L to u L and v L respectively:

• if u L and v L are neighbors on the lattice, them u and v are neighbors on the graph

V INRIA Proof: We have u -v ≤ u -u L + u L -v L + v L -v using triangle inequality of the Euclidian distance . . By definition of neighborhood on the lattice, u L -v L ∈ R(r), hence, u L -v L ≤ ρ -2r
Moreover since u L is the closest point on the lattice of u, and we have uu L ≤ √ 2 2 r (the length of the half-diagonal of a r × r square), which is implies uu L ≤ r. The same reasoning applies to v and v L at, and as a result:

u -v ≤ 2r+ u L -v L ≤ ρ.
Hence the lemma.

Lemma 5 |R(r)| ≤ π ρ 2 r 2
Proof: In a similar spirit to the mapping to the lattice, let us consider the square of size r × r around each point of R(r). Such squares are disjoint for different points of R(r) ; let us denote R (r) the union of all such squares of every point of R(r).

We have, for every point of u ∈ R (r): there exists a point v ∈ R(r) such that u is in the square around v. Then by a similar argument to lemma 4,

u -v ≤ √ 2 2 r ≤ r ; in addition v ≤ ρ -2r, from the definition of R(r). Therefore u ≤ ρ, hence R (r) is included in the disk of radius ρ. Therefore its area A( R (r)) verifies A( R (r)) ≤ πρ 2 .
In addition, by definition of R (r) as union of disjoint squares, we also have another expression of its area: A( R (r)) = |R(r)|r 2 . Using this equality with the previous inequality with A( R (r)) gives the result.

Lemma 6 |R(r)| = π ρ 2 r 2 + O( 1 r ) when r → 0, Proof:
We can rewrite the definition of R(r) as: R(r) = {(rx, ry) :

x 2 + y 2 ≤ ( ρ -2r r ) 2 ; (x, y) ∈ Z 2 } (9)
It is the number of points in |R(r)| is the number of lattice points within a circle of radius fixed around the origin (the "circle problem"). From [START_REF] Voss | Discrete Images, Objects, and Functions in Z n[END_REF]

p. 133, Gauß has shown that N c (d) = πd 2 + O(d) , for a circle of radius d, when d → ∞. Here d = ρ r -2, hence |R(r)| = π( ρ r ) 2 + O( 1 r
), and the lemma.

Relationship between Capacities of the Cuts of the Embedded Lattice and the Random Disk Unit Graph.

The idea here is to show that the relationship with a cut of the random unit graph, and a cut of the lattice graph.

Let us consider one source s ∈ V, one destination t ∈ V and the capacity of any S/T cut. Every node of S and T is then mapped to the nearest point of the embedded lattice. For the source, we denote: s L = λ(s).

An induced cut of the embedded lattice is constructed as follows:

The border area width W L is selected so as to be the greatest integer multiple of r which is smaller than W ; and r < Wρ, so that the requirement 5.1.3 of section 2 is met.

For any point of the lattice v L ∈ L, the rate C S L is the set with the point s L and with points of the lattice L, such as only nodes of S are mapped to them:

S L {s L } ∪ {u L : λ -1 (u L ) ⊂ S} (10)
T L is the set of the rest of points of L.

Note that t ∈ T L ; that all the points of the lattice, to which both points from S and T are mapped, those points are in T L ; and that the points to which no points are mapped are in S L : S L /T L is indeed a partition and a s Lt L cut.

Recall that definition of a cut in eq. 2, we have:

C(S) = v∈∆S C v and C (L) (S L ) = v∈∆SL C v
where ∆S and ∆S L are subsets of S and S L respectively.

We have the following relationship between these two sets: Lemma 7 Excluding s L and s, the nodes of V that are mapped to points of ∆S L , are in ∆S ; that is:

λ -1 (∆S L \ {s L }) ⊂ ∆S \ {s}
Proof: λ -1 (∆S L ) = ∪ uL∈∆SL λ -1 (u L ) hence it suffice to prove the property for λ -1 (u L ) for every u L ∈ ∆S L . Let us consider one such point u L ∈ ∆S L \ {s L }. By definition of ∆S L , there exists a point v L ∈ T L within range for L (that is: (u Lv L ) ∈ R(r)).

If λ -1 (u L ) = ∅, then the property λ -1 (u L ) ∈ ∆S \ {s} is verified. Hence let us consider the case where λ -1 (u L ) = ∅:

Since v L ∈ T L , by the definition of this set, there exists at least one node of T mapped to v L and thus: λ -1 (v L ) ∩ T = ∅. Now consider two points of these non-empty sets, u ∈ λ -1 (u L ) and v ∈ λ -1 (v L ) ∩ T :

• From lemma 4, we know that u and v are within range ( uv ≤ ρ).

• Recall that ∆S L ⊂ S L . By definition of S L , since u L is in S L , u must be in S.

• v ∈ T These three conditions imply that u ∈ ∆S. Also s is mapped to the unique λ(s) = s L , therefore u L = s L implies u = ∆S \ {s}. It follows that λ -1 (u L ) ⊂ ∆S \ {s}, and, as a consequence, the lemma.

It is now possible to use this subset of ∆S to prove the following lemma on relating the cut of V and its induced cut: Proof: First note that if m min = 0, the lemma is proved. Hence, in the rest of the proof, we can assume that this integer verifies m min ≥ 1.

In this case, notice that there are L 2 r 2 squares of size r × r, each with at least m min nodes, therefore the total number of nodes verifies: N ≥ L 2 r 2 m min , and then µ ≥ 1 r 2 m min by definition of µ. Combining this with lemma 5, we get:

|R(r)| ≤ πρ 2 µm min (11)
Now consider again the definition of a cut in eq. 2, that can be split in two parts, one without the source, with the source: In Th. 3, m min plays a central part. In this section, a probabilistic bound is given for the variation of m min .

C(S) = v∈∆S C v = v∈∆S\{s} C v + v∈∆S∩{s} C v With lemma 7,
We start with the following property on random variables: for a variable X which is the sum of n random variables X i , i.e. X = i=n i=1 X i , which are independant and identically distributed, we have the following inequality, which is a Chernoff bound [START_REF] Barbe | Probabilité Editions Espaces[END_REF]:

P r(X ≤ (1 -δ)E[X]) ≤ exp(- E[X]δ 2 2 ) ( 12
)
for 0 ≤ δ ≤ 1 Symetrically, a similar Chernoff bound exists for the upper tail [START_REF] Barbe | Probabilité Editions Espaces[END_REF]:

P r(X ≤ (1 + δ)E[X]) ≤ exp(- E[X]δ 2 4 ) (13)
Since V is a random graph, where points are uniformly distributed, for u L ∈ L, the number of points of V mapped to it, m(u L ), is random variable which is the sum of

N Bernoulli trials X v : m(u L ) = v∈V X v
where X v is the indicator variable, equal to 1 when v is mapped to u L , and equal to 0 otherwise.

INRIA

of the nodes which transmitted the packet. Note that the traditional methods need not to explicitly use a such a CDS (like in the case of MPR-flooding technique used in [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], which is self-pruning), although several efficient methods do (such as [START_REF] Wu | Efficient Broadcasting with Guaranteed Coverage in Mobile Ad Hoc Networks[END_REF]).

To compare network coding and IREN/IRON with traditionnal store-and-forward broadcast, we will proceed following the steps and the logic of [START_REF] Widmer | Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[END_REF], as section 4.5 also did: the metric for efficiency is the number of transmissions necessary to broadcast one packet to the entire network. In section 4.5, the relative cost E rel-cost was the ratio of the total number of transmissions to a bound of the a lower bound number necessary of transmissions

E bound = N Mmax .
Here, in homogeneous networks, M max ≈ M , hence in this section, we will use M instead of M max in the expression of the bound.

Then the expression of the relative cost

E rel-cost
E bound , can be re-interpreted as follows: from the point of view of a given node, it is the average ratio of the non-redundant packets received to the number of received packets.

For store-and-forward, "non-redundant packets" means "packets not already received". For network coding, it means "innovative packets" (the ones which that increase the dimension of the vector space of receivers).

We will compare the cost of broadcasting with Network Coding E With the argument of [START_REF] Widmer | Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[END_REF], in any CDS, except for the source, every node must be connected to another node of the CDS: therefore for any common neighbor, the transmission of the second node will be redundant with the transmissions of the first node. A bound on the number of transmission T (cds) can then be computed.

Simulation Scenario

In the simulations of this section, we used examples of lattice networks where R (lattice neighborhood definition set) is the four closer neighbors of the lattice).

Precisely R = {(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)}. The neighborhood of each node fits exactly the minimum requirement 1. This scenario of nodes on a grid with at most four neighbors corresponds to one scenario of [START_REF] Widmer | Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[END_REF] (except the lattice considered here is not a torus), and their bound on E (cds) rel-cost is 4 3 .

INRIA

The nodes are on lattice of width L = 70 (70 × 70) and the simulations were performed while increasing the size of generation (total number of broadcast packets), and the border width is W = 2.

The source s is chosen in the middle of the network.

In general all nodes have same constant transmission rate M 2 except the source and nodes which are near the border and have less than M neighbors. The source sends original packets at rate M , and the nodes near the border also send encoded packets at rate M .

For simplicity, the transmissions of nodes in the network are "synchronized", that is, if the transmission rate of one node v is C v , then the every transmission occurs periodically with a period equal to 1

Cv

The figure 4 shows the performance of E 3 )

The performance of B nc becomes better as the generation size increases. The reason that the larger generation size brings the better performance, is the following. At the beginning of the simulations, only the source has new packets, initially only the only transmissions that could bring novel informations are: transmissions from the source, then after that, transmissions from the immediate neighbors of the source, and so on. Hence there is a start-up duration, during which the transmission of nodes further from the source are less likely to bring innovative information to the nodes closer from the source. Similarily, at the end, a similar problem occurs: consider for instance one node which has all the packets from the sources ; then any transmission from a neighbor will bring non-innovative packets. This phenomem explains why efficiency decreases at the end.

This start-up and termination interval durations are independant on the generation size: hence, the efficiency increases together with the size of the generation.

From the figure, we can see confirm that, with our simulations settings, network coding (with IREN/IRON) will outperform any method based on CDS (hence on store and forwards). Notice that [START_REF] Widmer | Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[END_REF] established identical results for M = 4, but in a scenario where each node had one packet to transmit to every other node. Here we have a single source with several packets to broadcast.

In general, it is not difficult to see that the connectivity constraint gives a lower bound E (cds) rel-cost > 1. For instance, in a unit disk graph, two neighbors share a neighborhood area at least equal to ( 2π 3 -√

2 )ρ 2 , hence E 3 ≈ 1.6420 . . ., and as a result, one can expect broadcast with network coding and IREN/IRON to outperform CDS, when the generation size is sufficient, as illustrated by the simulations.

Efficiency with Increasing Density in Random Unit Disk Graphs

The previous simulations illustrated the performances on a lattice. For random unit disk graphs, our results have shown that the min-cut, the performance of broadcasting with network coding with IREN/IRON approaches the average number of neighbors in wireless networks as the density increases, that is, with Th. 5, Cmin m p → 1. Notice that for a given instance of a random graph, some efficiency is lost when because the min-cut is usually lower than M -unlike for lattices where IREN/IRON results exactly in C min = M .

To give an illustration of this convergence Cmin m p → 1, we computed the min-cut of random graphs with increasing density. To do so, we modeled oriented hypergraphs as oriented graphs, in the spirit of [START_REF] Wu | Minimum-energy multicast in mobile ad hoc networks using network coding[END_REF] (refer to the elementary graphs and also figure 2 of that reference).

Then, the min-cut was computed from the software library implementing the maxflow algorithm from [START_REF] Boykov | An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision[END_REF]. The optimizations for tree reuse from [START_REF] Kohli | Efficiently Solving Dynamic Markov Random Fields Using Graph Cuts[END_REF] were also used.

The network size is L = 1 × 1 ; the radio range ρ is such that it covers 1 25 of the network, that is ρ = 1 5 √ π ≈ 0.1128 . . .. We compute the min-cut increasing the network density M , from 125 to 400. As seen in figure 5, the min-cut increases exponentially as the networks become denser and the ratio Cmin M approaches to 1, as expected.

INRIA

We have presented a simple rate selection for network coding for large sensor networks. We computed the broadcast performance from the min-cut with networks modelled as hypergraphs. The central result is that selecting nearly the same rate for all nodes, achieves asymptotic optimality for the "homogeneous" networks that are presented, when the size of the networks becomes larger. This can be translated into the remarkable property: nearly every transmission becomes innovative for the receivers.

6. 2

 2 Efficiency with Increasing Density in Random Unit Disk Graphs . . . . . .

1

  by abuse of language, the term "unit disk graph" will be used in this article INRIA (a) Unit disk graph -neighbors of A are B and C since they are within range ρ (b) Lattice

Figure 1

 1 Figure 1: Network Models

Figure 2 :

 2 Figure 2: Examples of range for lattices

Algorithm 1 :

 1 Random Distributed Network Coding Nodes' scheduling: Poisson retransmission; the nodes retransmit linear 1.1 combinations of the vectors that they have, with an exponential interarrival INRIA 4 Our approach: IREN/IRON 4.1 Overview

→ 1 ,→ 1 .

 11 when L → ∞ and similarly with Th. 5 we have Mmax M p By definition N = µL 2 . Finally, M = Ω(L θ ) for θ < 1 implies that 4MW L → 0. INRIA Near Optimal Broadcast with Network Coding in Large Homogeneous Wireless Networks15

INRIA Lemma 1

 1 C(S) ≥ |∆S| (with ∆S defined in (1))

First

  case: T ∩ ∆L = ∅ Second case: ∆L ⊂ T Third case: T ∩ ∆L = ∅ and δL ⊂ T We will prove inequality of theorem 1 in all 3 cases. First case, T ∩ ∆L = ∅: With lemma 2, we know that T ⊕ R ⊂ L, hence we can effectively write the neighbors of nodes in T as a Minkowski addition (without getting points in Γ but out of L): ∆T (T ⊕ R) \ T It follows that: |∆T | ≥ |T ⊕ R| -|T | Now the inequality (5) can be used: |T ⊕ R| ≥ |T | + |R| -1 Hence we get: |∆T | ≥ |T | + |R| -1 -|T |, and therefore:

  vL is set according to IREN/IRON on the lattice: C (L) vL = |R(r)| -1 when v L is within the border area of width W L , and C (L) vL = 1 otherwise.

INRIALemma 8

 8 Near Optimal Broadcast with Network Coding in Large Homogeneous Wireless Networks23 The capacity C(S) of the cut S/T and the capacity of the induced cut C (L) (S L ) verify:C(S) ≥ m min C (L) (S L )

Theorem 3

 3 we know a subset of ∆S, hence: C(S) ≥ C interm. + C src with C interm. = v∈λ -1 (∆SL\{sL}) C v and C src = v∈∆S∩{s} C v • The first sum C interm. can be rewritten as: C interm. = vL∈∆SL\{sL} v∈λ -1 (vL) C v Let us consider all the nodes in the square area λ -1 (v L ), and their rates compared to the rate of v L : If C (L) vL = 1, then since IREN/IRON assigns only rates ≥ 1, we have C v ≥ C vL > 1, v L is a border node for L (and W L ), and C (L) vL must actually be |R(r)| -1.Since W L is chosen so that W L < W , we have also:λ -1 (v L ) is a set of border nodes of V. Their rate is C v = πρ 2 M by definition.From eq. 11, we haveC v ≥ m min |R(r)|, hence C v ≥ |R(r)|, and finally: C v ≥ C (L) vL As a result, in both cases, ∀v ∈ λ -1 (v L ), C v ≥ C (L)vL , and:v∈λ -1 (vL) C vL = |λ -1 (v L )|C (L) vL ≥ m min C (L) vL Hence C interm. (S) ≥ m min vL∈∆SL\{sL} C (L) vL• The second sum C src reduces to 0 or 1 term:If s L ∈ ∆S L , then ∆S L ∩ {s L } = {s L }.With the same reasoning as in the proof of lemma 7, necessarily s ∈ ∆S as well, and: ∆S ∩ {s} = {s}.C src = C s = πρ2 µ. As before, from eq. 11, we get C s ≥ m min |R(r)|, hence C src ≥ m min C (L) sL RR n 6188 Cédric Adjih, Song Yean Cho, Philippe Jacquet If s L / ∈ ∆S L , then ∆S L ∩ {s L } = ∅, and obviously vL∈∆SL∩{sL} C (L) vL = 0 In both cases, C src ≥ m min vL∈∆SL∩{sL} C (L) vLPutting together both inequalities for C interm. and C src , the result is:C(S) ≥ C interm. + C src ≥ m min vL∈∆SL\{sL} C (L) vL + m min vL∈∆SL∩{sL} C (L) vL Hence: C(S) ≥ m min vL∈∆SL C (L) vLThe right part of the inequality is actually the definition of the capacity of the s L -t L -cut, hence: C(S) ≥ m min C (L) (S L ), which is the lemma. The min-cut C min (s) of the graph V, verifies:C min (s) ≥ m min (|R(r)| -1)Proof: From lemma 8, any cut C(S) is lower bounded by m min C (L) (S L ). Since C (L) (S L ) is the capacity of a cut of a lattice with IREN/IRON, Th. 2 also indicates that: C (L) (S L ) ≥ C (L) min = |R(r)| -1. Hence the lower bound m min (|R(r)| -1) for any C(S), and as a result, for the min-cut C min (s) 5.2.4 Nodes of V Mapped to One Lattice Point.

N

  and with the one of any Connected Dominated Set E (cds) rel-cost . The following notations are used: : the total number of nodes M : the average number of neighbors G: the number of packets broadcast (generation size) T : the total number of transmissions

  and the bound on E (cds) rel-cost with N = 70 × 70 = 4900, M = 4 and G = 20, 40, 60, 80, 100.

Figure 4 :

 4 Figure 4: Performance of broadcast with NC and CDS with increasing generation size

Figure 5 :

 5 Figure 5: Performance when Increasing Density

RR n 6188

actually their results are more general INRIA

Alternatively the reader familiar with mathematical morphology[START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF] could notice that S i is the erosion of S by the structural element R. As a result S i ⊕ R is actually the opening of S, and the following property of the opening is known: S i ⊕ R ⊂ S (see[START_REF] Voss | Discrete Images, Objects, and Functions in Z n[END_REF] p.40).

For all v, E(X v ) = r 2 L 2 , and hence: E(m(u L )) = r 2 N L 2 = µr 2 . The m(u i ) are identically distributed for all u i ∈ L. By applying the Chernoff bounds [START_REF] Lun | Further Results on Coding for Reliable Communication over Packet Networks[END_REF] on this sum, we get:

for δ ∈]0, 1[. We can deduce a bound on the probabilities for the minimum m min of all m(u). For the points u i ∈ L, the event (m min ≤ K) implies the event m(u 1 ) ≤ K or m(u 2 ) ≤ K or ... m(u |L| ) ≤ K :

Now the different m(u i ) are identically distributed, but are not independent because their sum is exactly N ; but we can use the fact that for two events A and B, P r[A or B] ≤ P r[A] + P r[B], and then:

And it follows, with eq. 14:

r 2 , we have the following theorem 4:

The Th. 4 could be used with Th. 3, to get probabilistic bounds of the min-cut for an instance of a random graph.

Likewise, if we consider the maximum of m(u), m max min u∈L m(u), with the upper tail Chernoff bound, the same expression as in Th. 4 is true with δ ∈] -1, 0[.

Asymptotic Values of the Min-Cut of Unit-Disk Graphs.

Theorem 5 For a sequence of random unit disk graphs and associated source (V i , s i ∈ V i ), with fixed radio range ρ, fixed border area width W , with a size L i → ∞, and a density M = L θ with fixed θ > 0, we have the following limit of the min-cut C min (s i ):

RR n 6188

Proof: The starting point is Th. 4, which involves several variables: L, µ, δ, and r.The theorem is a result when the size of the network L → ∞ (so that the relative area of the border decreases). We also want:

µ → ∞ (that is: M → ∞): the density increases sufficiently fast, so that each square r × r receives more points and the Chernoff approximation becomes tighter.

δ → 0: this ensures m min converges to its average value as in Th. 4.

r → 0: in order to have |R(r)| converge to its limit of lemma 6.

By hypothesis, we already have µ = M πρ 2 = 1 πρ 2 L θ for some θ > 0. We propose the following settings:

In that case, using Th. 4, we have, for δ ∈]0, 1[:

The right side of the inequality converges towards 0 as L → ∞, hence this is a lower bound in probability for mmin µr 2 . For the upper bound, notice that m min is the minimum of the (m(u L ), u ∈ L), and µr 2 is exactly their average. The minimum cannot be greater than the average hence: We have:

)), from lemma 6.

INRIA

Near Optimal Broadcast with Network Coding in Large Homogeneous Wireless Networks27

Therefore the right side a p → 1 in probability. This gives an lower bound of Cmin M for L → ∞. Let us show that this lower bound is also an upper bound (in probability). Recall that the min-cut C min is lower than any cut, for instance one cut with only neighbors of a node t (T = {t}). Let us consider the node t ∈ V with the maximum number of neighbors M max , and hence C min ≤ M max

We have: the maximum number of neighbors M max is at most m max |R + (r)|, where R + (r) is similar to R(r), except considering squares of around within a point of the lattice with radius ρ + 2r. Like for |R(r)|, one can prove:

and like m min , one can show that mmax µr 2 p → 1 in probability. Collecting these properties, we get:

where the right side of the bounds : is such that mmax|R + (r)| M p → 1 in probability. Hence upper bound, and the theorem.

Simulations

The previous sections have focused on the asymptotic value of the min-cut for large networks. Then random linear network coding can achieve asymptotically the maximum capacity known as the min-cut, when running for an asymptotically infinit time.

In this section, we provide an illustration of the performance of network coding with simulations.

We performed the following types of simulations:

Performance comparison with store-and-forward bounds: the objective is to show that the performance of broadcasting with network coding with IREN/IRON may outperform what be achieved without network coding (the traditional store-and-forward broadcast), on some examples.

Min-cut comparison with the average number of neighbors: it illustrates the fact that when broadcasting with IREN/IRON the min-cut approaches the average number of neighbors in wireless networks as the density increases.

6.1 Comparison with Store-and-Forward

Metric for Comparison

For the broadcast of one packet to the entire network, any traditional broadcast method (non-network coding) is characterized by a Connected Dominating Set (CDS): it is the set


Mark D Williams-Wynn

Jamal El Abbadi

Alain Valtz

Elodie Kovacs

Céline Houriez

Paramespri Naidoo

Christophe Coquelet

Deresh Ramjugernath

Jamal El Abbadi

Experimental determination of the critical loci for R-23 + (n-propane or n-hexane) and R-116 + npropane binary mixtures

Keywords: Critical loci, R-23, R-116, n-propane, n-hexane, VLE

come

Experimental determination of the critical loci for R-23 + (n-propane or n-hexane) and R-116 + n-propane binary mixtures

Introduction

Supercritical fluids exhibit a number of physical properties that give them an advantage over conventional liquid solvents [1]. Most importantly, supercritical fluids have densities that are of a similar magnitude to conventional solvents. However, these densities can be varied substantially by altering the pressure and temperature of the fluid [2]. Carbon dioxide (CO 2 ) is by far the most commonly used supercritical solvent [1].

CO 2 is essentially a non-polar solvent, with a dipole moment of zero debye [3]. This inhibits the ability of CO 2 to dissolve polar components to any useful extent [2]. In addition to this, CO 2 does not exhibit very large capacities for solutes, translating into larger volumes of solvent being required to perform a separation. In order to overcome these problems, an alternative solvent or mixture of solvents must be used. The more commonly applied method is the addition of co-solvents to the CO 2 , in order to improve its ability to dissolve polar components [3]. Alternatively, the solvent can be replaced with a more polar solvent. This study continues a previous investigation into the use of trifluoromethane (R-23) and hexafluoroethane (R-116) as supercritical solvents [4].

In this study, the critical loci of three systems, R-23 + (n-propane or n-hexane) and R-116 + n-propane were measured using a critical point determination apparatus, and were compared to values either extrapolated using the method described by Ungerer et al. [START_REF] Ungerer | Applications of Molecular Simulation in the Oil and Gas Industry-Monte Carlo Methods[END_REF], or calculated using the method of Heidemann and Khalil [START_REF] Heidemann | [END_REF]. Ju et al. [7] measured several isotherms of the R-23 + n-propane system at temperatures of between T = (283.15 and 313.15) K. To supplement this data, several additional VLE isotherms were measured for the R-23 + npropane system using a static-analytic apparatus, and are reported in this work. Both the VLE measurements and the critical loci measurements were performed at the Centre for Thermodynamics of Processes (CTP).

VLE data for the R-116 + n-propane system were obtained from the work of Ramjugernath et al. [8]. For the R-23 + n-hexane system, the data of Williams-Wynn et al. [4] were used, and for the R-116 + n-hexane, the data that were reported by Ramjugernath et al. [9] were extrapolated to the critical point.

Experimental

Materials. The suppliers, CAS numbers and stated purities of the chemicals that were used in this study are listed in Table 1. The critical properties of the components are provided in Table 2.

Experimental Apparatus. Two different apparatus were used in this work. A static-analytic apparatus was used to measure the isothermal VLE data for the system R-23 + n-propane, and a critical point determination apparatus was used to measure the critical loci of the three systems.

Static-analytic apparatus. The static-analytic apparatus used in this study uses a capillary sampler (ROLSI TM ) [10] to sample the liquid and vapour phases. The equipment is similar to that depicted in Figure 1, which was used by Juntarachat et al. [11].

The equilibrium cell is submerged into a thermo-regulated liquid bath which is maintained at a constant temperature. The deviations of the temperature within the bath are less than 0.01 K. The temperature of the fluid inside the equilibrium cell is monitored by two platinum resistance thermometer probes (Pt100) connected to a data acquisition unit (HP34970A) [12].

The use of two probes enables any gradients within the cell to be quantified, and the average of the two measurements is used as the measured temperature. The Pt100 probes were calibrated against a 25 Ω reference platinum resistance thermometer (Hart Scientific). This Pt25 reference probe was calibrated by the -Laboratoire National d'Essais de Paris‖ based on the 1990 International Temperature Scale (ITS 90). The maximum error given by the calibration of the reference probes was estimated to be within 0.05 K.

The pressure is measured using one of two pressure transducers (DRUCK, 0 -3 MPa, 0 -30 MPa) installed on the apparatus. The choice of pressure transducer is dependent upon the maximum pressures generated by the system being characterised. The two pressure transducers are also connected to the data acquisition unit (HP34970A). The pressure transducers were calibrated against an automated pressure calibrator (GE Sensing, model PACE 5000). The pressure uncertainties from the transducers are estimated to be within 0.2 kPa for the -0 -3 MPa‖ pressure transducer and 0.6 kPa for the -0 -30 MPa‖ pressure transducer.

The compositions of the phases present within the cell are analysed with a gas chromatograph (VARIAN, model CP-3800), which is equipped with a thermal conductivity detector (TCD).

The analytical column within the gas chromatograph (GC) is a PORAPAK Q, 80/100 mesh (Silcosteel tube, length: 2m, diameter: 3.2mm, from Restek).

The response of the TCD is calibrated by introducing known amounts of each pure component into the gas chromatograph, using an automatic syringe. The calibration equation was fitted to relate the response of the TCD to the amount of the component introduced.

Critical point determination apparatus. The critical point determination apparatus that was commissioned by Soo et al. [13] at the CTP at Mines ParisTech was modified to measure the critical loci of the three systems. This apparatus was originally a dynamic-synthetic apparatus, but due to the large relative volatilities of the constituent components of the three systems, in particular the systems containing n-hexane, the apparatus was modified to perform static-synthetic measurements. A schematic drawing of this experimental apparatus is shown in Figure 2.

To enable the use of the apparatus of Soo et al. to perform static-synthetic measurements, the heat exchanger was removed from the line of fluid flow. Thus, the major sections of the apparatus are a volumetric press, a syringe pump and an equilibrium cell. A synthetic mixture is prepared in the volumetric press, VPr, by mixing known masses of the required components. The volumetric press is attached to an ISCO 260D syringe pump, SP. The contents of the volumetric press are forced into the syringe pump, by applying a pressure to the press from the pressure source, PS. The synthetic mixture is pumped from the syringe pump into the equilibrium cell, EC. A vacuum pump, VP, attached to the transfer line between the syringe pump and the equilibrium cell is used to evacuate the equilibrium cell or the syringe pump prior to either being filled with the synthetic mixture. The temperature of the syringe pump is maintained below the measurement temperature to ensure that no flashing occurs therein. This is performed with a jacket encasing the pump reservoir. The ethanol contained inside of this jacket is circulated from a constant temperature bath, WB, which ensures that the temperature remains constant.

The equilibrium cell is constructed of a sapphire tube, with an ID of 12.7 mm, and a length of 30.03 mm. This sapphire tube is enclosed on either end by titanium flanges. This gives the cell an internal volume of approximately 3.8 cm 3 . A dead volume of about 0.3 cm 3 (± 10%) is introduced by the static configuration of the cell. The equilibrium cell is housed within a France Etuves XU 125 air thermostat, AT, which is used to control the temperature of the cell. The contents of the equilibrium cell are observed through a window in the air thermostat wall. A lamp that is placed inside of the air thermostat provides sufficient illumination to observe the phase changes occurring within the cell.

The temperature of the contents of the cell are monitored with a platinum resistance temperature probe, TP, which is inserted into the cell, through the top flange. This Thus, all fluid that exits the cell must be in the vapour or supercritical phase. From the equilibrium cell, the fluid flows through a series of valves and is vented in a fume hood.

The temperature probe was calibrated against a 25 Ω Hart Scientific N° 1678 standard for the temperature range of T = (296.36 to 486.65) K. This standard was calibrated by the Laboratoire National d'Essais (Paris). The temperature standard calibration had a standard deviation of 0.039 K, and the correlation of the calibration of the Tinsley Precision Instruments probe introduced a further 0.02 K uncertainty. The pressure transducer was calibrated for the measurement of pressures of between (0 and 15.5) MPa, against a Druck PACE5000 pressure controller, which was certified by the Laboratoire National d'Essais (Paris) to have a standard deviation of 1×10 -3 MPa. The calibration correlation itself had an uncertainty of 3.9×10 -4 MPa.

Experimental Procedure.

Static-analytic apparatus. Initially, a vacuum is pulled in the equilibrium cell and the loading lines at ambient temperature. For binary measurements, two thermal presses are loaded with each pure component, and attached to the loading lines. The equilibrium cell is then lowered into the constant temperature bath.

When the equilibrium temperature is reached, an amount of approximately 5 cm 3 of the heavier component is introduced into the cell. The equilibrium temperature is deemed to have been reached when the two temperature probes give the same temperature reading (within limits of uncertainty) for at least 10 minutes. After loading, the vapour pressure of the pure component is measured at the equilibrium temperature [12].

After the vapour pressure has been measured, a small volume of the second component is introduced into the cell, and the mixture is allowed to equilibrate. For VLE measurements, equilibrium is assumed to be reached inside of the cell when the pressure does not change by more than 1 kPa for a period of at least 10 minutes, while stirring continuously [12]. Once equilibrium is attained, the conditions (pressure, temperature and compositions of the phases) are measured. Thereafter, a further small volume of the second component is added into the cell, and the process is repeated. This process is continued until such a time as successive equilibrium mixtures have provided sufficient co-existence points to cover the two-phase envelope. With the measurements at subcritical conditions (for both components), the two-phase envelope can be traversed in both directions, starting with either of the pure components.

For each equilibrium measurement, at least six samples of both the vapour and the liquid phases are taken using the ROLSI TM capillary sampler. These are analysed to verify the repeatability of the composition measurements. The criterion for the acceptance of the measured phase composition is that the range of the data points is less than the uncertainty due to the calibration of the gas chromatograph.

Critical point determination apparatus. The fluid to be measured is prepared in the volumetric press by the addition of known masses of each component. These masses are measured using a Mettler Toledo XP2004S balance with an uncertainty of 0.7 mg. When mixtures containing n-hexane were being synthesized, the n-hexane was degassed using a vacuum pump prior to being added to the cell. This degassing was performed at a pressures below the vapour pressure of n-hexane at the ambient temperature for approximately 10 minutes.

The prepared mixture is thereafter compressed to approximately 10 MPa in the volumetric press, using the pressure source (high pressure nitrogen). This pressurisation is to ensure that only a single (liquid) phase exists inside of the volumetric press. The liquid is then transferred into the syringe pump, where it is held at a temperature of T = 288 K. To begin the measurements, the cell is filled to approximately half of its volume with the mixture. The cell is then sealed, and the temperature of the air thermostat is increased. The loading of the cell to approximately half of its volume with the mixture was important, as otherwise, upon heating, the fluid could all become a vapour or all become a liquid prior to the critical locus conditions being attained. Were this the case, the phase transition into the supercritical region would not be visible.

The temperature and pressure at which the critical opalescence is observed is recorded, and thereafter the temperature is decreased, recording the conditions at which the critical opalescence occurs once again. This process is repeated twice before the cell is evacuated and a fresh portion of the same mixture is added into the cell. The maximum rate at which the temperature was allowed to change was limited to 0.3 K per minute, in order to prevent sizeable temperature gradients from developing within the cell, due to the poor circulation in the cell caused by no agitation of the cell contents. The mean temperature and pressure, from at least five repeated loadings, are reported as the measured critical locus.

Correlations

Subcritical data treatment. The subcritical VLE data was correlated with the Peng-Robinson equation of state (PR EOS) with the classical (van der Waals) mixing rule [14]. The models for each isotherm were fitted to the data using the direct (phi-phi) data regression approach in Aspen V8.4 [15] using a modified Barker's objective function (minimisation of the pressure and vapour phase composition deviations). The fit of the models to the experimental data were quantified with the mean relative deviations (MRDs) and the absolute average relative deviations (AARDs) for each isotherm [4].

Critical point determination. The composition and pressure at the critical point were extrapolated from the experimental data using the method that was proposed by Ungerer et al. [START_REF] Ungerer | Applications of Molecular Simulation in the Oil and Gas Industry-Monte Carlo Methods[END_REF]. This method uses the extended scaling laws to extrapolate to the critical point for a given isotherm for binary mixtures. The equations representing the extended scaling laws are given by Equations 1 and 2. This technique was further discussed by El Ahmar et al. [16]. y -x = 𝜆 1 𝑃 𝑐 -𝑃 + 𝜇 𝑃 𝑐 -𝑃 𝛽 (1)

y + 𝑥 2 -𝑥 𝑐 = 𝜆 2 𝑃 𝑐 -𝑃 (2)

Discussion

The isothermal vapour-liquid equilibrium (VLE) data of the R-23 + n-propane system were measured at temperatures of between T = (283.15 and 353.15) K, using the static-analytic apparatus. The VLE data are given in Tables 3 and4, and are plotted in Figure 5. The vapour pressures of both R-23 and n-propane were compared to literature data in Figures 3 and4. There was good agreement between the experimental data and that available in literature for R-23 [4,[17][18][START_REF] Hori | An Experimental Study of Thermodynamic Properties of Trifluoromethane[END_REF], with differences between the experimental data and the literature data of less than 0.3%, and for n-propane [7,8,[START_REF] Dong | [END_REF][21][22], with deviations of less than 0.5% between the experimental and the literature data. Due to the large volumes of vapour pressure data that were available for n-propane, several authors that provided data over the range of temperatures that were investigated in this study were utilised, rather than using the entire n-propane vapour pressure dataset. The T = (293.15 and 313.15) K isotherms were compared to the data that were measured by Ju et al. [7], which are also included in Figure 5.

Figure 6 provides an enlargement of the plot for compositions of R-23 between (0.7 and 1.0) mole fraction, to enable a better view of the fit of the models and extrapolated data to the measured data.

The temperature independent PR EOS model with classical (van der Waals) mixing rule was fitted to each isothermal set of VLE data. The temperature independent binary interaction parameters for the model are provided in Table 5. These parameters are also plotted against the temperature in Figure 7. There was a good fit of the models to the experimental data, with most of the MRDs and AARDs being below 2 %. A second order polynomial fitted to the parameters suggests a temperature dependence of the parameters that is not linear.

The critical loci that were measured using the critical locus determination apparatus for the systems of R-23 + n-propane, R-116 + n-propane, and R-23 + n-hexane, are reported alongside their uncertainties in Table 6. The critical loci extrapolated from subcritical VLE data for the R-23 + n-propane, and R-116 + n-propane [8] systems using the method of Ungerer et al. [START_REF] Ungerer | Applications of Molecular Simulation in the Oil and Gas Industry-Monte Carlo Methods[END_REF]16] are reported in Table 7. Redlich-Kister (RK) type correlations were fitted to the T-x and P-x projections of the critical locus curves for all three systems. The parameters for different order correlations used to depict the T-x projection of the critical locus curve are given in Table 8, alongside the MRDs. The order of the correlation was selected such that the deviation between the measured value and the correlated value was less than the experimental uncertainty. Table 9 lists the parameters for the correlations of the P-x projection. The correlations were better able to describe the T-x projection than the P-x projection, with the MRDs of less than 2% for temperature, but substantially higher for pressure. The mixture critical pressures were not well described even by a 4 th order polynomial for the R-23 + n-hexane system.

The P-x and T-P projections of the R-23 + n-propane critical locus curve are presented in Figures 8 and9, respectively. There is a fairly close agreement between the critical loci that were measured directly and those that were extrapolated from the VLE data. The RK type correlations are capable of providing a rough description of the critical locus curve, with the 3 rd order correlation possibly providing the closest fit. The 4 th order correlation was not suitable for this system. It behaved in a similar manner to how an over-specified model would be expected to behave. The vapour pressure data for R-23 and n-propane were plotted using the PR-MC [23] parameters reported by Williams-Wynn et al. [4] and Ramjugernath et al. [8], respectively. The inflection of the critical locus curve at a minimum pressure, and the subsequent crossing of the vapour pressure curve, near to the pure R-23 critical point (T = 299.07 K) is indicative of the negative azeotrope which occurs for the R-23 + n-propane system.

The P-x projection of the R-116 + n-propane critical locus curve was plotted on Figure 10 alongside the VLE data that were measured for this system by Ramjugernath et al. [8]. The data of Ramjugernath were extrapolated to the critical loci by using the technique of Ungerer et al. [START_REF] Ungerer | Applications of Molecular Simulation in the Oil and Gas Industry-Monte Carlo Methods[END_REF]. These critical loci are also included on Figure 10 alongside the RK-type correlation curves which were fitted to the experimental data. There was good agreement between the experimentally measured and the extrapolated critical loci. The T-P projection of the critical locus curve (Figure 11) confirms this excellent agreement. The first order correlation of the T-P curve is not capable of adequately describing the critical locus curve, however, the 2 nd order and higher correlations do provide good descriptions.

The P-x projection of the critical loci for the R-23 + n-hexane system measured directly with the critical point determination apparatus are plotted on Figure 12. The VLE data and the section of the critical locus curve that was calculated using the method of Heidemann and Khalil [START_REF] Heidemann | [END_REF] from the work of Williams-Wynn et al. [4] are also included on this plot. The RKtype correlations of the critical locus curve are also included in Figure 12. This P-x-y plot is enlarged for compositions of between (0.7 and 1.0) mole fraction in Figure 13. Figure 14 projects the critical locus curve for this system onto the T-P axis. The RK-type correlations were not capable of adequately describing the critical locus curve indicated by the experimental data. For this system, the mean relative deviation between the experimental data and the model was 9.2 %, whereas the maximum uncertainty of the measurements was 1.3 %. In addition, there were substantial differences between the experimentally measured critical loci and the extrapolated critical loci. This indicates that either the extrapolation technique is not sufficiently accurate, or, alternatively, the lack of stirring mechanism within the critical locus measurement apparatus translated into inaccuracies in the critical loci that were measured. The curve that was calculated from the thermodynamic models used by Williams-Wynn et al. [4], by the method of Heidemann and Khalil follows the extrapolated data fairly closely. This is because both techniques rely on the sub-critical co-existence data.

The R-23 + n-propane system does not appear to exhibit a three phase region, and therefore, based upon the T-P plot for this system, it would appear to be a van Konynenberg and Scott (VKS) [24] type I-A system. There is however, the possibility that the upper critical end point (UCEP) occurs at temperatures below those measured in this study. If this is the case, then the system would be a VKS type II-A system. The azeotrope that is present for this system lends to the addition of the ‗A' suffix. The R-23 + n-hexane system exhibits a three phase region, but also only a single critical curve traversing between the two pure component critical points. Thus this system is classified as a type II system. The R-116 + n-propane system exhibits similar characteristics to the R-23 + n-propane system, and is therefore also classified as either VKS type I-A or type II-A.

Conclusions

The isothermal VLE data for the R-23 + n-propane system were measured using a staticanalytic apparatus at temperatures of between T = (293.18 and 353.15) K. The PR EOS with classical mixing rules was used to model this experimental data independent of temperature.

A good description of the experimental data was achieved with this single parameter model.

It was, however, shown that the binary interaction parameters were not linearly dependent on temperature. Several critical loci were extrapolated from subcritical VLE data. These extrapolated loci were compared with measured critical loci. These measurements were performed using a ‗critical loci determination apparatus'. The extrapolated data and the experimental data showed close agreement. Critical loci were also measured using the apparatus for the systems of R-116 + n-propane and R-23 + n-hexane. The critical locus curves were modelled with Redlich-Kister type correlations, which were fitted to the experimental data. The correlations were capable of providing a good fit of the systems containing n-propane, however, with the system with n-hexane, they did not exhibit the same ability. Lastly, the critical locus curve, calculated from the thermodynamic model fitted to R- Uncertainties, calculated with k = 2 are as follows: a U(T) = 0.08 K, b U(P) = 0.0008 MPa, c U(x 1 ) = 0.008, d U(y 1 ) = 0.009, e U(x 1 ) = 0.009, f U(y 1 ) = 0.008. Uncertainties, calculated with k = 2 are as follows: a U(T) = 0.08 K, b U(P) = 0.001 MPa, c U(x 1 ) = 0.009, d U(y 1 ) = 0.009, e U(x 1 ) = 0.004, f U(y 1 ) = 0.005. g U(P) = 0.01 MPa This was modelled with an ‗RK-type' correlation: -, 1 st order; ---, 2 nd order; ⋅⋅⋅⋅, 3 rd order; -⋅ -⋅, 4 th order. Vapour pressure plots from the PR-MC EOS: , R-23 vapour pressure [4];

, n-propane vapour pressure [9]. Critical locus curve modelling with ‗RK-type' correlations; -, 1 st order; ---, 2 nd order; ⋅⋅⋅⋅⋅, 3 rd order; ⋅ -⋅ -, 4 th order. Sub-critical VLE data from the work of Williams-Wynn et al.

[4] at temperatures: Δ, T = 293.0 K; ×, T = 303.1 K; ○, T = 313.2 K.

  temperature probe, a Type 5187A probe supplied by Tinsley Precision Instruments, is positioned within the cell such that the tip is positioned along the central axis of the sapphire tube, extending approximately to the centre of the cell. The pressure of the fluid inside of the cell is measured with a Druck PTX 611 pressure transducer, PT, with a range of 0 to 16 MPa. This pressure transducer is maintained at a constant temperature by a West 6100 PID controller, TR, which controls the temperature of a heating cartridge housed with the pressure transducer at T = 373 K. The analogue signals from the temperature probe and the pressure transducer, obtained by an Agilent 34401A data acquisition unit, DAU, are converted into digital signals, and are logged on a PC, DAS. The fluid from the syringe pump enters into the equilibrium cell through ports machined into the bottom flange. The fluid exits the cell from a similar port machined into the top flange.

Figure 2 .

 2 Figure 2. Drawing of the critical point determination apparatus modified from the work of

Figure 5 .y 1 Figure 6 .

 516 Figure 5. Plot of the P-x-y data for the R23 (1) + n-propane (2) system, with the system critical locus curve. Experimental data at temperatures: , T = 293.18 K; ▲, T = 298.15 K; •, T = 313.15 K; , T = 323.15 K; +, T = 353.15 K. Data modelled with ──, PR EOS. Literature data from the work of Ju et al. [8] at given temperatures: □, T = 283.15 K; , T = 293.15 K; ×, T = 303.15 K; ○, T = 313.15 K. Critical point modelling: , extrapolated critical loci; , measured critical loci; ----, RK 4 th order correlation.

y 1 Figure 7 . 1 Figure 9 .

 1719 Figure 7. Plot of the temperature dependence of the binary interaction parameters for the PR

Figure 12 . 1 Figure 13 .

 12113 Figure 12. Plot of the critical locus curve for the R-23 (1) + n-hexane (2) system, alongside subcritical P-x-x-y data. Critical loci: , extrapolated; , measured (including error bars displaying the uncertainties); -, calculated (by the Heidemann and Khalil method). Modelling of critical locus curves with ‗RK-type' correlations: -, 1 st order; ---, 2 nd order; ⋅⋅⋅⋅⋅, 3 rd order; ⋅ -⋅ -, 4 th order;. Sub-critical VLE data from the work of Williams-Wynn et al. [4] at temperatures: Δ, T = 293.0 K; ×, T = 303.1 K; ○, T = 313.2 K.

1 Figure 14 .

 114 Figure 14. T-P projection of the critical locus curve of R-23 (1) + n-hexane (2). ○, experimental data with error bars; ×, critical loci extrapolated from subcritical VLE data; -, 1 st order RK correlation; ---, 2 nd order RK correlation; ⋅⋅⋅⋅, 3 rd order RK correlation, ⋅ -⋅ -, 4 th order RK correlation.

Table 1 .

 1 Chemical suppliers, CAS numbers and stated purities

			Supplier	CAS Number	Stated Purity
	Trifluoromethane, R23, CHF 3 a	Climalife	75-46-7	0.995 b
	Hexafluoroethane, R116, C 2 F 6 a	Air Liquide	76-16-4	0.99999 b
	n-Propane, C 3 H 8	a	Messer	74-98-6	0.99995 b
	n-Hexane, C 6 H 14		Sigma-Aldrich	110-54-3	0.99 c
	a Further purification of components was not undertaken.
	b volumetric (molar) basis
	c mass basis

23 + n-hexane VLE data by Williams-Wynn et al.

[4]

, by the technique of Heidemann and Khalil, was compared with the experimental and extrapolated data. The extrapolated data and the calculated data showed similar trends. This was presumably due to both originating from the reported VLE data. The (R-23 or R-116) + n-propane binary mixtures were both classified as either type I-A or II-A systems. The binary R-23 + n-hexane mixture was classified as a type II system.

Table 2 .

 2 Critical properties from literature data

		T c /K	P c /MPa	ω
	Trifluoromethane, R23, CHF 3 a	299.07 a	4.836 a	0.264 c
	Hexafluoroethane, R116, C 2 F 6	293.04 b	3.042 b	0.229 b
	n-Propane, C 3 H 8	369.95 b	4.246 b	0.152 b
	n-Hexane, C 6 H 14	507.40 b	3.014 b	0.301 c
	a Ref. [25]
	b Ref. [26]
	c Ref. [27]

Table 3 .

 3 P-x-y data for the R-23 (1) + n-propane (2) system at temperatures below the critical temperature of R-23.

		T = 293.18 K a				T = 298.15 K a
	P/MPa b	x 1	c	y 1	d	P/MPa b	x 1	e	y 1	f
	0.8368	0		0		0.9508	0		0
	1.3538	0.053	0.341	1.6831	0.075	0.387
	1.8594	0.120	0.508	3.0651	0.314	0.648
	2.8118	0.322	0.670	2.3621	0.170	0.550
	3.1979	0.453	0.717	3.6164	0.484	0.709
	3.6002	0.625	0.769	3.9604	0.610	0.747
	3.7345	0.687	0.792	4.2464	0.720	0.788
	3.9258	0.776	0.830	4.4949	0.819	0.841
	4.1419	0.906	0.915	4.5411	0.840	0.854
	4.1703	0.937	0.940	4.5644	0.850	0.862
	4.1769	0.948	0.949	4.6067	0.871	0.878
	4.1800	0.954	0.955	4.6287	0.883	0.888
	4.1774	-		0.955	4.6686	0.906	0.906
	4.1797	0.959	0.960	4.6944	0.927	0.927
	4.1819	0.966	0.967	4.7180	0.957	0.957
	4.1823	0.970	0.970	4.7191	0.964	0.964
	4.1821	0.974	0.974	4.7206	0.968	0.968
	4.1822	0.977	0.977	4.7184	-		0.962
	4.1805	0.982	0.982	4.7217	0.980	0.979
	4.1790	0.986	0.986	4.7208	0.988	0.988
	4.1787	0.992	0.991	4.7093	1		1
	4.1717	1		1

Table 4 .

 4 P-x-y data for the R-23 (1) + n-propane (2) system at temperatures above the critical temperature of R-23.

	T = 313.15 K a			T = 323.15 K a			T = 353.15 K a
	P/MPa b	x 1	c	y 1	d	P/MPa b	x 1	c	y 1	d	P/MPa b	x 1	e	y 1	f
	1.3801 g	0		0		1.7130	0		0		3.1354	0		0
	2.0388	0.057	0.274	2.2264	0.040	0.182	3.4204	0.018	0.048
	3.0674	0.173	0.481	2.4390	-		0.237	3.5010	0.025	0.063
	3.7409	0.278	0.558	2.4525	0.060	0.239	3.7949	0.046	0.104
	4.1408	0.354	0.592	2.8503	0.097	0.327	4.0015	0.062	0.133
	4.6054	0.460	0.623	3.1572	0.128	0.374	4.2831	0.085	0.163
	4.8038	0.512	0.629	3.5130	-		0.418	4.3708	0.092	0.170
	4.9324	0.550	0.630	3.5541	0.172	0.431	4.4198	0.096	0.173
	5.0006	0.576	0.623	4.0748	-		0.485	4.5218	0.105	0.182
						4.1810	0.257	0.491	4.6256	0.115	0.189
						4.4982	0.307	0.505	4.7208	0.125	0.195
						4.8326	0.366	0.523
						5.0287	0.406	0.530
						5.1504	0.437	0.527
						5.1895	0.447	0.523

Table 5 .

 5 Model results for the PR EOS with the van der Waals mixing rules for the system of R-23 (1) + n-propane (2).

	T / K

Table 6 .

 6 Experimental critical temperatures, T c, and pressures, P c , of binary mixtures as a function of the mole fractions, 𝑥 1,𝑐 , measured using the critical point determination apparatus.

	𝒙 𝟏,𝒄	U(𝒙 𝟏,𝒄 ) a	T c / K	U(T c ) a / K P c / MPa U(P c ) a / MPa
			R23 (1) + n-propane (2)
	0.071	0.005	364.2	0.6	4.61	0.05
	0.221	0.005	351.9	0.4	5.08	0.03
	0.325	0.004	342.0	0.6	5.32	0.02
	0.326	0.004	342.1	0.4	5.28	0.03
	0.434	0.003	331.3	0.6	5.37	0.05
	0.569	0.003	313.9	0.4	5.07	0.03
	0.624	0.002	311.3	0.5	4.97	0.02
	0.706	0.008	306.5	0.8	4.82	0.03
			R23 (1) + n-hexane (2)
	0.111	0.005	503.3	0.9	3.66	0.08
	0.320	0.004	486.9	0.7	5.34	0.08
	0.537	0.003	454.3	1.1	7.91	0.09
	0.661	0.002	427.8	0.2	9.18	0.12
	0.773	0.002	383.2	1.0	9.82	0.10
	0.860	0.002	343.0	0.9	7.98	0.04
	0.922	0.002	318.7	0.5	5.95	0.06
	0.944	0.002	310.8	0.3	5.41	0.03
			R116 (1) + n-propane (2)
	0.071	0.005	362.0	0.3	4.31	0.03
	0.179	0.005	348.2	0.1	4.26	0.04
	0.259	0.004	338.7	0.3	4.16	0.01
	0.411	0.003	323.4	0.2	3.85	0.02
	0.521	0.003	313.3	0.2	3.61	0.02
	0.752	0.002	298.5	0.2	3.17	0.01
	a The combined expanded uncertainties of composition, temperature and pressure are
	calculated using a coverage factor, k, equal to 2.

Table 7 .

 7 Critical temperatures, T c, and pressures, P c , of binary mixtures as a function of the mole fractions, extrapolated from sub-critical co-existence points by the Ungerer et al. extrapolated from the data provided by Ju et al.[7] and from the data measured in this study. b extrapolated from the work of Ramjugernath et al.[8].

	extrapolation technique.
		R23 + n-propane a			R116 + n-propane b
	𝒙 𝟏,𝒄	T c / K	P c /MPa	𝒙 𝟏,𝒄	T c / K	P c /MPa
	0.752	303.15	4.747	0.814	296.23	3.140
	0.601	313.15	4.978	0.585	308.21	3.456
	0.493	323.15	5.243	0.409	323.19	3.854
	0.192	353.15	5.103

a

Table 8 .

 8 Parameters (a n ) for the Redlich-Kister type correlation describing the T-x projection of the critical locus curves of the three systems, alongside the mean relative deviation (MRD) from each correlation.

	System	a 1	a 2	a 3	a 4	a 5	100×MRD
		-45.68	-65.50	-	-	-	1.777
	R-23 + n-propane	-41.79	-72.51	-41.56	-	-	1.087
		-41.79	-72.51	-41.56	-3.6 × 10 -4	-	1.087
		-65.43	-18.43	-	-	-	0.411
	R-116 + n-propane	-65.35	-20.20	-3.18	-	-	0.409
		-65.55	-9.67	-14.77	-49.04	-	0.268
		231.58	55.46	-	-	-	7.767
	R-23 + n-hexane	235.00 257.23	20.28 91.27	-124.13 -190.70	--256.13	--	5.177 1.707
		256.50	94.71	-189.22	-268.95	-9.66	1.608

Table 9 .

 9 Parameters (b n ) for the Redlich-Kister type correlation describing the P-x projection of the critical locus curves of the three systems, alongside the mean relative deviation (MRD) from each correlation. Flow diagram of the static-analytic apparatus, as was used by Juntarachat et al.

	System	b 1	b 2	b 3	b 4	b 5	100×MRD
		2.530	-3.763	-	-	-	7.059
	R-23 + n-propane	2.719	-4.238	-2.158	-	-	3.445
		2.761	-4.338	-2.443	-0.131	-	3.440
		0.045	-2.352	-	-	-	1.063
	R-116 + n-propane	0.028	-1.992	0.711	-	-	0.303
		0.026	-1.941	1.134	0.421	-	0.293
		14.575	13.863	-	-	-	43.944
	R-23 + n-hexane	14.081 16.218	21.337 23.607	10.423 -8.816	--23.610	--	31.608 22.563
		13.645	25.051	20.658	-23.086	-37.505	9.172

[11]

. EC: equilibrium cell; LV: loading valve; MS: magnetic stirrer; PP: platinum resistance thermometer probe; PT: pressure transducer; RT: temperature regulator; LB: liquid bath; TP: thermal press; C1: more volatile compound; C2: less volatile compound; V: valve; GC: gas chromatograph; LS: liquid sampler; VS: vapour sampler; SC: sample controlling; PC: personal computer; VP: vacuum pump.

Acknowledgement

This work was supported by the South African Research Chairs Initiative of the Department of Science and Technology of South Africa and the National Research Foundation. The authors also wish to acknowledge the Institut Carnot M.I.N.E.S. for their support in this study.