Qi Wang
email: wangqi08@ict.ac.cn

Katia Jaffrès-Runser
email: katia.jaffres-runser@irit.fr

Claire Goursaud
email: claire.goursaud@insa-lyon.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

Deriving Pareto-optimal performance bounds for 1 and 2-relay wireless networks

Keywords: Multiobjective performance evaluation, fundamental bounds, wireless networks, random linear network coding, fountain codes

This work addresses the problem of deriving fundamental trade-off bounds for a 1-relay and a 2-relay wireless network when multiple performance criteria are of interest. It proposes a simple MultiObjective (MO) performance evaluation framework composed of a broadcast and interference-limited network model; capacity, delay and energy performance metrics and an associated MO optimization problem. Pareto optimal performance bounds between end-to-end delay and energy for a capacity-achieving network are given for 1-relay and 2-relay topologies and assessed through simulations. Moreover, we also show in this paper that these bounds are tight since they can be reached by simple practical coding strategies performed by the source and the relays. Two different types of network coding strategies are investigated. Practical performance bounds for both strategies are compared to the theoretical upper bound. Results confirm that the proposed upper bound on delay and energy performance is tight and can be reached with the proposed combined source and network coding strategies.

I. INTRODUCTION

Two main and complementary directions have driven research in wireless ad hoc networking. The first direction targets the design of efficient distributed protocols at all layers of the protocol stack: physical, medium access control (MAC), routing, and transport layers. Various techniques in the context of resource allocation (power control [START_REF] Wu | A multi-channel mac protocol with power control for multi-hop mobile ad hoc networks[END_REF], scheduling, frequency assignment,... ), coding (source coding [START_REF] Mackay | Fountain codes[END_REF], [START_REF] Luby | LT Codes[END_REF], network coding [START_REF] Ahlswede | Network information flow[END_REF], [START_REF] Ho | A random linear network coding approach to multicast[END_REF]), and routing (reactive routing [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF], proactive routing [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], opportunistic routing [START_REF] Jacquet | Opportunistic routing in wireless ad hoc networks: upper bounds for the packet propagation speed[END_REF], geographic routing [START_REF] Lukic | Greedy geographic routing algorithms in real environment[END_REF]... ). The second research direction targets the derivation of fundamental performance limits of wireless ad hoc networks (cf. [START_REF] Goldsmith | Beyond Shannon: The Quest for Fundamental Performance Limits of Wireless Ad Hoc Networks[END_REF] and the references herein). Both directions are clearly related since performance limits can provide insight into proper network design solutions and thus, help improving protocol performance. They provide as well upper bounds against which to compare the performance of existing protocols.

Initial research in both directions has concentrated on deriving upper bounds [START_REF] Toumpis | Capacity regions for wireless ad hoc networks[END_REF], [START_REF] Luo | Engineering Wireless Mesh Networks: Joint Scheduling, Routing, Power Control and Rate Adaptation[END_REF] and protocols maximizing network capacity [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF]. Yet, capacity achieving strategies and related bounds even for some simple network configurations are still to be found [START_REF] Goldsmith | Beyond Shannon: The Quest for Fundamental Performance Limits of Wireless Ad Hoc Networks[END_REF], [START_REF] Avestimehr | A Deterministic Approach to WIreless Relay Networks[END_REF]. With the introduction of new applica-tions (e.g. wireless sensor networks, vehicular networks, etc...), additional metrics and their impact on network capacity have become relevant. New studies on the trade-off between metrics implying energy consumption minimization [START_REF] Gorce | Energy, latency and capacity trade-offs in wireless multi-hop networks[END_REF], [START_REF] Zhang | Energy efficiency of opportunistic routing with unreliable links[END_REF], end to end delay minimization [START_REF] Comaniciu | On the capacity of mobile ad hoc networks with delay constraints[END_REF], [START_REF] Gorce | Energy, latency and capacity trade-offs in wireless multi-hop networks[END_REF] or reliability maximization [START_REF] Zhang | Energy efficiency of opportunistic routing with unreliable links[END_REF] have started. These trade-offs can be characterized with MultiObjective (MO) bounds. A 2-objective MO bound represents the relationship between two criteria f 1 and f 2 .

As considered by Goldsmith et al. in [START_REF] Goldsmith | Beyond Shannon: The Quest for Fundamental Performance Limits of Wireless Ad Hoc Networks[END_REF], a promising way towards achieving fundamental MO bounds in wireless ad hoc networks is to leverage "the broadcast features of wireless transmissions through generalized network coding, including cooperation and relaying". In our previous work [START_REF] Jaffres-Runser | A multiobjective performance evaluation framework for routing in wireless ad hoc networks[END_REF], [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF], we have proposed a framework composed of a cross-layer network model and a steady state performance evaluation model capturing capacity, delay and energy metrics. We have formulated an associated MO optimization problem whose resolution provides both the MO bound and MO Pareto-optimal network configurations. This framework has been designed to incorporate broadcast and interferencelimited channels and thus, is capable of deriving MO bounds for a layerless communication paradigm [START_REF] Goldsmith | Beyond Shannon: The Quest for Fundamental Performance Limits of Wireless Ad Hoc Networks[END_REF] that integrates generalized network coding, cooperation and relaying.

The purpose of this paper is to assess the quality of this MO bound through the derivation of a lower achievable MO bound. An achievable MO lower bound can be obtained with any distributed network strategy incorporating relaying, coding or cooperation decision. Our aim is to exhibit MO lower bounds that are as close as possible to our MO upper bound, validating the tightness of our MO bound and the efficiency of the network strategy (which is nothing else than a distributed network protocol). Proposed lower bounds are achieved using simple source and network coding algorithms. Looking at first for simple transmission and relaying strategies is motivated by their ease of deployment. Focusing on network coding is driven by the fact that it leverages the inherent broadcast nature of wireless propagation, phenomenon that is captured as well in the framework used to derive MO upper bounds. Investigated network strategies have sources transmitting a random linear fountain code and relays re-combining packet using different simple network coding strategies. Two dif-ferent network coding strategies are investigated. Practical performance bounds for both strategies are compared to the theoretical bound. Therefore, we focus on 1-relay and 2-relay topologies. Results clearly demonstrate the tightness of our upper MO bound compared to a combined source and network code.

This paper is organized as follows. Our network model is introduced in Section II. The considered MO optimization problem is presented in Section III and its derivation for 1relay and 2-relay cases in Section IV. Results are given in Section VI-B and coding strategies are discussed in Section VI. Finally, Section VII concludes the paper.

II. SYSTEM MODEL

The two following topologies of wireless ad hoc networks, illustrated in Fig. 1 are studied in depth in this paper:

• 1-relay topology • 2-relay or diamond topology Next, the framework for our study is introduced.

A. Protocol and network model

We assume a synchronized wireless ad hoc network where transmissions are time-multiplexed (the synchronization procedure is out of the scope of this paper). A frame of |T | time slots is repeated indefinitely. One or more packets can be transmitted in a time slot. In the rest of this paper, our examples assume that one packet is being sent in one time slot. A time epoch s is defined as the time needed to transmit one frame of |T | time slots.

1) Wireless channel model: For any time slot u ∈ T , there is an interference-limited channel between any two nodes i and j of the network. This channel is modeled by the probability of a packet to be correctly transmitted between i and j in time slot u. This probability is referred to as the channel probability and denoted p u ij in the following. It is computed assuming interference is modeled as an additive noise and for the medium access scheme presented hereafter. Its derivation is based on the distribution of the packet error rates (PER) originating from the statistics of nodes attempting emission in the same time slot. We refer the reader to [START_REF] Jaffres-Runser | A multiobjective performance evaluation framework for routing in wireless ad hoc networks[END_REF] [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF] to get the exact derivation of this channel probability.

X i p 1 ij p u ij τ u i τ 1 i τ |T | i Node j Node i p |T | ij X j

Fig. 2. Channel and node model

Each channel is assumed to be in a half-duplex mode, i.e. a node cannot transmit and receive a packet at the same time.

2) Network model: The considered 1-relay and 2-relay wireless networks are modeled by a finite weighted multiple edges complete graph K |V| = (V, E) with V the set of vertices and E the set of edges. Two vertices are linked by |T | edges representing orthogonal interference-limited channels as illustrated on Fig. 2. In this graph, an edge (i, j, u) represents the channel between nodes i and j in time slot u. Each edge is assigned a weight of p u ij . If the transmission between i and j on time slot u is not possible, p u ij = 0. For each node i ∈ V, -→ N i and ← -N i are the set of edges leaving from and going into i, respectively.

A unique flow with a source S continuously transmitting data to a destination D is defined. Source and destination nodes do not relay the information. Multi-hop transmissions are allowed and we model the other nodes as relay nodes R = V -S -D. We have N = |R| the number of relays in the network.

As said before, the network is synchronized. Depending on their time slot assignments, source and relays emit their packets at the beginning of their assigned time slots. We assume their packet emission lasts for the whole time slot duration. Nodes that are not emitting in a time slot can receive packets in this time slot. Important to our model is that all relays that aren't emitting are listening. If packet reception is possible in the current time slot, the packet is stored in its incoming buffer. In other words, in our graph K |V| , if any node i ∈ |V| emits a packet in time slot u, all edges leaving i in time slot u ((i, j, u) ∀j ∈ E) carry the same packet to their next hops j. As such, our model completely captures the broadcast property of the wireless medium.

We assume that relays have |T | incoming buffers and |T | outgoing buffers. All buffers are able to store the amount of packets transmitted in one time slot duration. In our examples, they can store one packet. We consider as well in our model that a relay can not differentiate packets: identical packets are indiscernible.

3) Medium access control for broadcast transmissions: We assume a very basic random channel access for all nodes sharing a time slot u: if a node i is willing to transmit its packet in time slot u in the next frame, it attempts it with probability τ u i . The packet is disregarded with probability 1-τ u i . There is no acknowledgment procedure. If the receiver can not decode the packet, it is definitively lost. Contrary to more elaborated medium access procedures, emission decisions of nodes are independent.

An emission is defined as the couple (i, u) ∈ V × T and represents the fact that node i is emitting in a time slot u. The emission rate τ u i is defined as the probability node i is emitting in time slot u. Thus, a node i transmitting at a rate of τ u i = 0.5 in time slot u will decide with probability 0.5 to transmit its previously received packet in time slot u in the upcoming frame. If this decision is successful, it will occupy time slot u of the next frame for its whole duration.

Having this, a vector of emission rates for a node i can be defined -→ r j ≤ ← -

τ i = τ 1 i . . . τ |T | i . Let τ = τ † 1 • • • τ † N † τ S p SD p RD p SR S D Relay R τ R τ S
r j , ∀j ∈ V (1)
with ← -

r j = u∈T (i,j)∈ --→ N u j τ u i p u ij
the average rate at which all the packets are coming into node j and -→ r j = v∈T τ v j the rate at which packets are being transmitted by node j.

In the case of equality, we have a strict flow conservation. Otherwise, | ←r j --→ r j | are dropped by node j as a consequence of a forwarding decision described in the next item. PROPERTY 2: Half duplex. A node j is able to receive a message on a time slot u if it is not transmitting on that same time slot. As a consequence, a τ is feasible if for each node of the network, the average number of time slots it spends transmitting and receiving sums up to a maximum value of one:

← - r u j + τ u j ≤ 1, ∀(j, u) ∈ V × T (2)
where ←r u j = (i,j)∈ --→ N u j τ u i p u ij stands for the incoming cumulative rate in time slot u.

We define Γ as the set of all feasible emission rate matrices. 4) Forwarding and scheduling decisions: Each node j will decide, with the forwarding probability x uv ij , to transmit on time slot v a packet coming from node i in the time slot u of the next frame. Thus, we can define a N |T |-by-|T | matrix giving all the forwarding probabilities relative to any node j of the network. It is given by

X j = X 1j • • • X N j †
where each matrix X ij provides the scheduling probabilities of a flow of packets coming from node i on its output times slots, depending on the time slot the packets are received on. We have

X ij =     x 11 ij • • • x 1|T | ij . . . . . . x |T |1 ij • • • x |T ||T | ij     .
The matrix of forwarding probabilities is related to the matrix of emission rates τ and the matrix of channel probabilities P with the following set of |A| equations

(i,j)∈ --→ N u j u∈T τ u i p u ij x uv ij = τ v j , ∀(j, v) ∈ A (3)
where τ u i p u ij is the probability that a packet sent by i on time slot u arrives in j. These equations are derived from the flow conservation property of (1). They strictly constrain the choices of forwarding probabilities.

The forwarding probabilities represent the decisions of the nodes to either (i) retransmit all the packets received or (ii) reduce the output rate by dropping or re-encoding them together. From now on, we will refer to the set of all forwarding probabilities of the complete network using a matrix

X = [X 1 . . . X N ] , X ∈ X of size N.|T |-by-N.|T |
where X is the set of all possible matrix instances.

III. MO OPTIMIZATION PROBLEM

A. Elementary criteria definition

This section defines for one source-destination flow optimization objectives related to reliability, capacity, end-to-end delay and energy consumption based on the aforementioned network and protocol model.

CAPACITY OBJECTIVE f C : It is defined as the average number of packets received by the destination per packet sent by S. If P is the set of all possible paths on K |V| between S and D, it is derived by summing the transmission success probability of a packet on each path. Formally:

f C = p∈P P (p) (4)
where P (p) is the transmission success probability of a packet on path p ∈ P. RELIABILITY OBJECTIVE f R : It is defined as the probability of a packet to arrive at the destination. It is equivalent to the success rate of a packet sent by the source. It differs from the capacity criterion because redundant packet copies that successfully arrive at the destination are not accounted for. More specifically, it is the probability that at least one copy arrives at D. Formally:

f R = 1 - p∈P 1 -P (p) (5)
DELAY OBJECTIVE f D : It is defined as the average delay a packet sent by the source needs to reach the destination, expressed in number of hops. Assuming that one hop introduces a delay of 1 unit, a h-hop transmission introduces a delay of h units. Having H(p) the length in hops of path p, the average end to end delay is computed by:

f D = p∈P H(p) • P (p) p∈P P (p) = p∈P H(p) • P (p) f C (6)
where the numerator provides the total delay of all paths and the denominator the number of copies received, in average. ENERGY OBJECTIVE f E : We consider as a first approximation that the main energy consumption factor is due to the emission of a packet. Thus, the energy criterion f E is defined as the average number of emissions performed by all nodes (source and relays) per packet sent by the source. This simple energy model will be improved in future works to account for idling, listening and receiving energy expenditure.

B. Capacity and reliability achieving criteria

We define as well two other types of criteria, naming reliability achieving and capacity achieving criteria. These objectives directly derive from the elementary objectives introduced earlier.

RELIABILITY ACHIEVING DELAY f r D AND ENERGY f r E : Reliability-achieving delay and energy criteria are defined as follows:

f r D = f D /f R (7) f r E = f E /f R (8)
They represent the delay and energy needed to reach a perfectly reliable transmission. For instance, if f C = 0.5, f r D = 2f D and f r E = 2f E , meaning that 2 times more packets have to be sent in average to reach perfect reliability at the cost of double delay and energy.

CAPACITY ACHIEVING DELAY f c D AND ENERGY f c E : Capacity-achieving delay and energy criteria are defined as follows:

f c D = f D / min(f C , 1) (9)
f c E = f E / min(f C , 1) (10)
Here, capacity achieving criteria f c D and f c E are obtained by dividing the value of f D and f E by min(f C , 1) respectively.

Capacity and reliability criteria are equal if the packet travels on a unique path between S and D. When more than one path connect S and D, these criteria are not equal anymore because several copies may reach D. More generally, f C upper bounds reliability:

f C ≥ f R .
If f R = 1, it implies that f C ≥ 1 but the converse is not true. For instance, if two paths with non-null transmission probabilities exist between S and D and if f C = 1, either zero, one or two copies of the original packet can be received at D, with a temporal average of 1 packet per frame. The cases where zero or two copies are received are not interesting of course. But we show in Section VI that this capacity criterion can be reached if relays perform network coding, introducing diversity into the packets they are relaying.

C. Pareto-optimal bound and solution set

The first goal of this paper is to derive the Paretooptimal performance bounds and the set of corresponding Pareto-optimal networking solutions of the considered network topologies with respect to given performance objectives.

1) Pareto-optimality: Formally, a Pareto-optimal solution set is composed of all the non-dominated solutions of the MO problem with respect to the performance metrics considered. The definition of dominance is: DEFINITION 1: A solution x dominates a solution y for a n-objective MO problem if x is at least as good as y for all the objectives and x is strictly better than y for at least one objective.

DEFINITION 2: A solution x ∈ S is Pareto-optimal if there is no other solution y ∈ S that dominates x.

Thus, the set of Pareto-optimal solutions is as follows:

S opt = {x ∈ S : ∀y ∈ S opt , y does not dominate x} [START_REF] Toumpis | Capacity regions for wireless ad hoc networks[END_REF] and the corresponding Pareto-optimal performance bound is:

B opt = {(f 1 (x), f 2 (x), . . . , f n (x)) ∀x ∈ S opt } (12)
with f 1 , f 2 , . . . f n the n arbitrary objective functions.

2) Solution set: Based on our network model, several parameters can be treated as optimization variables: the location of the N relays, the number of relays N , the transmission power of each relay, the number of time slots |T | and the forwarding probabilities represented by matrix X ∈ X . In this paper, considered variables are the location of the N relays and their respective forwarding probabilities. Location l of N relays can be chosen in a convex set l ∈ C N . For one network realization, the forwarding probabilities are chosen in the set X . Thus the complete search space is S = C N × X .

D. MO Optimization problem

Even if the forwarding probabilities are the main optimization variables, we have to derive the emission rate matrix to exactly compute the interference level in the network. As shown in [START_REF] Jaffres-Runser | A multiobjective performance evaluation framework for routing in wireless ad hoc networks[END_REF], the derivation of the emission rate matrix τ ∈ Γ knowing the forwarding probabilities X ∈ X is intractable. In a nutshell, to compute the emission rates of a node j knowing X, the incoming transmission probabilities p u ij have to be known as well. Yet, in order to compute the p u ij values, the emission rates of the nodes i ∈ V, i = j are needed, creating a circular dependency between the emission rates.

Thus, we have proposed a reverse approach in [START_REF] Jaffres-Runser | A multiobjective performance evaluation framework for routing in wireless ad hoc networks[END_REF] where the main optimization variable is switched to the set of feasible emission rate matrices Γ. From any feasible value τ ∈ Γ, it is straightforward to derive the channel probabilities since the activity of all nodes on each time slot is known.

Only instances of τ that meet the constraints relative to Property 1 and 2 are further considered as valid. Now that we have a valid τ , we can derive all the forwarding matrices X ∈ X that verify the constraints of equation [START_REF] Luby | LT Codes[END_REF]. There are |A| constraints, each one constraining the choice of the x uv ij for all nodes and time slots of the network with respect to τ . Let X τ be the subset of X that verifies (3) with respect to the emission rate matrix τ . Each solution X ∈ X τ can be evaluated according to

f C , f D , f R or f E .
In the rest of the paper, the following multiobjective optimization problem that concurrently maximizes capacity and minimizes end-to-end delay and overall energy consumption is solved:

[max f C (x), min f D (x), min f E (x)] T (13) s.t. x = (l, τ, X) ∈ C N × Γ × X τ
where l is the location vector of N relays, τ a feasible emission rate matrix and X a feasible forwarding matrix for τ . Additional constraints can be included in this MO problem depending on the type of analysis needed or to reduce the size of the search space. For instance, nodes can be assigned time slots beforehand. In this case, if channel u is not assigned to node i, the τ u i variable becomes a constant equal to zero. The τ u i = 0 constraint would then be added to the MO problem. 1) Multiobjective performance bounds: Three different types of bounds are investigated in this work, derived from the solution of the MO optimization problem defined in Eq. ( 13).

The first bound, referred to as B opt , is directly obtained by solving Eq. ( 13). It is defined as:

B opt = {(f C (x), f D (x), f E (x)) ∀x ∈ S opt }
where S opt is the corresponding Pareto-optimal solution set.

From B opt , the two following bounds are derived:

• The capacity-achieving upper bound:

B c = {(f c D (x), f c E (x)) ∀x ∈ S opt }
• The reliability-achieving lower bound:

B r = {(f r D (x), f r E (x)) ∀x ∈ S opt }
Both bounds are calculated by applying capacity and reliability achieving criteria to the solutions of S opt .

The MO problem of Eq. ( 13) optimizes the capacity criterion and not the reliability criterion. As presented earlier, the capacity criterion upper bounds the reliability criterion. The reliability-achieving bound B r is a feasible delay-energy performance bound obtained as relays forward packets according to the forwarding probabilities of the solutions of S. On the contrary, the capacity-achieving bound B c is an upper bound because it accounts for multiple copies. We show in Section VI that it is possible to reach the capacity-achieving bound using network coding, and that this bound is tight for the 1 and 2-relay networks.

These bounds are not Pareto-optimal with respect to

(f c D , f c E ) or (f r D , f r E ). From B c (resp. B r
) the set of nondominated solutions with respect to f c D and f c E (reps. f r D and f r E ) is selected. These sets are referred to as:

• B c opt , the Pareto capacity-achieving upper bound,

A. Study cases

For the two topologies presented in Fig. 1, five different study cases are considered and summarized in Table I. In all study cases, the source only emits packets on the first time slot with rate one: τ 1 S = 1 and ∀u = 1, τ u S = 0. Each study case defines which topology is assumed, how many time slots constitute a frame and which nodes are allowed to transmit in each time slot. The time slots assignments of study cases 1, 3 and 4 ensure no interference exists, while other study cases exhibit time slots with possible interference. For the 2-relay topology, transmissions between relays A and B are possible or not. If they are possible, packets may loop infinitely between A and B. All study cases are defined by introducing additional constraints into the MO optimization problem defined in [START_REF] Avestimehr | A Deterministic Approach to WIreless Relay Networks[END_REF]. For each study case, section IV-B defines the exact MO optimization problems solved.

B. Criteria for 1-relay and 2-relay topologies

For both topologies, the general multiobjective problem of (13) is considered. Expressions for the optimization criteria of each study case are detailed in this subsection.

1) 1-relay topology: For a 1-relay topology using |T | time slots, optimization objectives are defined as:

f C = τ 1 S p 1 SD + |T | u=1 τ 1 S p 1 SR x 1u SR p u RD ( 14
) f R = 1 -(1 -τ 1 S p 1 SD ) |T | u=1 1 -τ 1 S p 1 SR x 1u SR p u RD (15) f D = ( |T | u=1 2 • τ 1 S p 1 SR x 1u SR p u RD + τ 1 S .p 1 SD )/f C (16) f E = τ 1 S + |T | u=1 τ 1 S p 1 SR x 1u SR (17)
Briefly, f C adds the probability for a packet in arrive to D directly (i.e. τ 1 S p 1 SD ) and the probability for the same packet to arrive through the relay node for each available time slot. The reliability criterion equals the probability for at least one packet to arrive through any available path and time slot. The delay criterion sums the delays of all packets arriving through all possible paths and averages it with the value of f C . Finally, the energy criterion sums the number of emissions of the source and the relay, knowing the probability that the relay will receive and forward packets.

Study cases 1 and 2 are covered by the MO problem of (13) and objectives are given in Eq. ( 14) to [START_REF] Jaffres-Runser | A multiobjective performance evaluation framework for routing in wireless ad hoc networks[END_REF]. For study case 1, |T | = 2 times slots, S emits in time slot 1 and relay R in time slot 2. Additional constraint to MO problem ( 13) is τ 1 R = 0.

Thus, following (3), x 11 SR = 0 and x 12 SR = τ 2 R /(τ1 S .p 1 SR ). As such, the only variables in this problem are the location of the relay l R ∈ C and its forwarding probability x 12 SR ∈ [0, 1]. For study case 2, since there is only one time slot, a single variable x 11 SR is defined. It is directly related to τ 1 R following (3):

x 11 SR = τ 1 R /(τ 1 S p 1 SR ).
As such, the only variables in this problem are the location of the relay l R ∈ C and its forwarding probability x 11 SR ∈ [0, 1]. 2) 2-relay topology: Study cases 3 to 5 are covered by the MO problem of [START_REF] Avestimehr | A Deterministic Approach to WIreless Relay Networks[END_REF]. Objectives and additional constraints are defined hereafter.

For the interference free study cases 3 and 4, we have |T | = 3 time slots. S is still transmitting in time slot 1 while relays A and B are transmitting in time slot 2 and 3, respectively. Following from the slot allocation, only τ 2

A and τ 3 B are defined, other relay emission rates are set to 0. From Eq. ( 3), we deduce that only x 12 SA , x 13 SB , x 32 BA and x 23 AB are non zero variables. Moreover, an X ∈ X matrix is feasible if the 2 constraints on the forwarding probabilities originating from (3) are met:

τ 1 S .p 1 SA .x 12 SA + τ 3 B .p 3 BA .x 32 BA = τ 2 A τ 1 S .p 1 SB .x 13 SB + τ 2 A .p 2 AB .x 23 AB = τ 3 B Introducing the notation Q uv ij = p u ij x uv ij
, the optimization objectives are:

f C = τ 1 S .p 1 SD + τ 1 S 1 -Q 23 AB Q 32 BA .(E + F ) (18)
with

E = (Q 12 SA + Q 13 SB .Q 32 BA ).p 2 AD and F = (Q 13 SB + Q 12 SA .Q 23 AB ).p 3 BD . f D = 1 f C • [ τ 1 S (1 -Q 23 AB Q 32 BA ) 2 (A + B) + τ 1 S .p 1 SD ] (19)
with

A = p 2 AD [Q 13 SB .Q 32 BA (3 -Q 23 AB .Q 32 BA ) + 2Q 12 SA ] and B = p 3 BD [Q 12 SA .Q 23 AB (3 -Q 23 AB .Q 32 BA ) + 2Q 13 SB ]
.

f E = τ 1 S + τ 1 S 1 -Q 23 AB Q 32 BA (Q 12 SA + Q 13 SB .Q 32 BA +Q 12 SA .Q 23 AB + Q 13 SB ) (20)
Detailed derivation of these criteria are presented in the Appendix. These equations originate from infinite summations over all possible path lengths. Indeed, due to the loop, packets may travel up to an infinite number of hops in the network.

If Q 23 AB Q 32 BA < 1, the geometric serie of ratio Q 23 AB Q 32
BA with first term 1 converges and finite values for f C , f D and f E can be derived. Expressing f R as a function of this infinite sum is not possible and this criterion is evaluated through simulations when a loop exists between A and B.

Q 23 AB Q 32 BA may be equal to one if perfect links between A and B exist and

x 23 AB = x 32 BA = 1.
As such, we add the following constraint to the MO problem of (13) for study case 4:

∀X ∈ X if (p 2 AB = 1 ∧ p 3 BA = 1)
x 23 AB < 1 -∆ x 32 BA < 1 -∆ with an empirically chosen value of ∆ = 0.05.

For study cases 3 and 5, additional constraints that avoid relay A to forward packets from B and vice versa are defined:

x 23 AB = x 32 AB = 0 for case 3 and x 22 AB = x 22 AB = 0 for case 5. Only one-hop and two-hop transmissions are possible. f C , f D and f E can be deduced from ( 18), ( 19) and [START_REF] Fraboulet | Worldsens: development and prototyping tools for application specific wireless sensors networks[END_REF], respectively. In both study cases 3 and 5, it is possible as well to derive a closed form expression for f R :

f R = 1 -(1 -τ 1 S p 1 SD )(1 -τ 1 S p 1 SA x 12 SA p 2 AD ) ×(1 -τ 1 S p 1 SB x 13 SB p 3 BD ) (21)
Study cases 5 differs from 3 and 4 respectively by its time slot assignment. Indeed, A and B emit on the same slot 2. As such, aforementioned criteria are straightforward to adapt to this other time slot assignment.

C. Implementation

For most of the study cases, the distance between S and D is set to d SD = 620m such as having a direct transmission probability p 1 SD without interference near 0 (assuming a transmission power P T = 0.15mW and a pathloss exponent of 3). The set of Pareto optimal locations of relays is searched in a continuous square surface area C of size d SD × d SD meters as shown in Figure 3. When study cases where different |T | values are compared on the same figure, they are scaled to be comparable.

S D 620m C d SD = 620m
1) MO optimization: Theoretical Pareto-optimal solutions and bounds are obtained using the state of the art nondominated sorting genetic algorithm (NSGA-2) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. For NSGA-2, a population size of 300 solutions is used and a maximum number of 1000 generations. The crossover probability is set to 0.9.

For each study case, upper Pareto bounds B opt between capacity, delay and energy objectives are computed analytically by solving the corresponding MO optimization problem. Then, the capacity-achieving upper bound B c is calculated analytically. The reliability-achieving lower bound B r is calculated analytically for the no-loop study cases and empirically using simulations otherwise.

2) Simulations settings: To assess analytical results, both upper and lower bounds are compared with simulations obtained with the event-driven network simulator WSNet 1 [START_REF] Fraboulet | Worldsens: development and prototyping tools for application specific wireless sensors networks[END_REF]. Each upper Pareto bound solution is simulated with WSNet. For each solution, the location of the relays and their forwarding probabilities are known. These forwarding probabilities are used in simulation to decide whether to forward a packet upon its reception. If the decision of packet emission is not successful, the packet is disregarded. In our simulations, a perfect TDMA is implemented following the specifications of the study case of interest. S sends a packet every first time slot of every frame. Experiment is run for 10000 frames.

Simulated values fC , fD , fE , f c D and f c E are calculated from simulations as follows. fC is measured by the total number of packets N rx received at D (including copies) divided by the number of packets transmitted by S. fD is measured using the statistical distribution of the delays of the packets arrived over each possible distance measured in hops: P (h) = n(h)/N rx , where n(h) is the number of packets arrived in h hops at D. fD is then calculated with fD = hmax h=1 h • P (h), with h max the maximum number of hops of all packets collected at D. fE is the sum of the number of packets transmitted by the source and the relays divided by the number of packets sent by S.

Besides, for each study case we compute empirically the reliability objective f R . It measures the proportion of different packets arriving at D. It is a regular success rate (copies are disregarded). From fR , empirical reliability-achieving delay f r D = fD / fR and energy f r E = fE / fR objectives are defined.

V. RESULTS FOR CONSIDERED TOPOLOGIES

This section presents the bounds B opt , B c and B r computed analytically and by simulations for the study cases introduced earlier. We extract as well the B c opt and B r opt bounds representing the set of non-dominated solutions of B c and B r with respect to capacity-achieving and reliability-achieving criteria, respectively.

A first important conclusion is that in all figures, the analytical bounds and their simulated counterparts perfectly match, assessing our network model and criteria definitions. Table II gives the root mean square error (RMSE) between B opt and Bopt for all study cases.

RM SE = 1 Nopt N i=1 (f (i)-f (i)) 2 f (i) 2
where N opt is the total number of Pareto-optimal solutions in B opt . Values are really small, showing a quasi-perfect match between the model and simulations.

A. 1-relay Pareto bounds and sets

Study cases 1 and 2 are investigated for two configurations:

p 1 SD ≃ 0 (d SD = 620m) and p 1 SD ≃ 0.5 (d SD = 310m).
Bounds B opt , B c and B r are given in Figures 4 and5 for study cases 1 and in Figure 7 for study case 2.

Another important conclusion is that when the source is connected to D with a single path, there is a perfect match between B c and B r as expected. This is true for study cases 1 and 2 where p 1 SD ≃ 0 since only one path from S to D exists. When multiple copies arrive at the destination, f C and f R are different by definition, creating different bounds B c opt and B r .

Lastly, a clear compromise is visible: decreased energy is obtained at the price of an increase in delay. Solutions that consume less energy have the relay forward packets with a lower probability, creating less reliable communication. Less reliable solutions introduce an extended delay to achieve perfect capacity as shown by the increase in capacity or reliability-achieving delay. A detailed explanation of the results presented for study cases 1 and 2 is given hereafter. For p 1 SD ≃ 0, all bounds are given in Fig. 4. B opt is 0.5 0.6 0.7 0.8 0.9 1 1. presented in Fig. 4-(top). For this bound, the solution with lowest capacity (f C ≃ 0), lowest delay (f D = 2) and lowest energy (f E = 1) is experienced when the relay node is not contributing to the transmission. This is the case if the relay's forwarding probability x 12 SR is zero or if the relay is not covered by S (p 1 SR ≃ 0). Energy is minimized in this case since the relay never re-transmits packets. A delay of 2 is experienced because since p 1 SD = 0 and the path probability on the S -R -D path (τ 1 S p 1 SR x 12 SR p 2 RD ) is very small but not null, the few packets arriving have a delay of two. More generally, we can say that for any non zero value of τ 1 S p 1 SR x 12 SR p 2 RD , which is equal to f C , the delay is always equal to 2.

B c opt B r Br B c (fc>1) B c (fc<1) Bc (fc>1) Bc (fc<1)
For the Pareto-optimal solution with highest capacity (f C = 0.25), highest delay (f D = 2) and highest energy (f E = 1.5), the relay is located right in the middle of the [S, D] segment and forwarding all received packet (x 12 SR = 1). In this case, link probabilities between S and R and between R and D are maximized (p 1 SR ≃ 0.5 and p 2 RD ≃ 0.5), providing maximum energy consumption and capacity. Delay is still equal to two hops because each packet arrives on the S -R -D path. For the solutions that lie in between highest and lowest Pareto solutions, as f C is getting smaller, the relay is getting closer to D. In this case, the S -R link has a weaker link while the R -D link has a stronger link. f E is getting smaller as well because less packets are received by R. For p 1 SD ≃ 0.5, all bounds are given in Fig. 5. B opt is presented in Fig. 5-(top). In B opt , all solutions of the Pareto set have a perfect link between the relay and the destination (i.e. p 2 RD = 1). The lowest capacity (f C = 0.50), lowest delay (f D = 1.00) and lowest energy (f E = 1.00) solution of B opt is obtained for solutions where either p 1 SR = 0 or x 12 SR = 0. In this case, packets arrive though the direct link S -D, minimizing energy and delay since no 2-hop paths are used. The solution with highest capacity (f C = 1.50), delay (f D = 1.66) and energy (f E = 2.00) has x 12 SR = 1 and the relay is in the middle of the [S, D] segment, maximizing S-R and R-D link probabilities (p 1 SR = 1 and p 2 RD = 1). In this solution, two copies per sent packet are received, one on the direct path, the other on the relay path. All other solutions from the set S are as well included in the Pareto solution set S opt . Depending on the relay location and x 12 SR value, you get either high or low f C . For instance, a solution with a relay close to D and high x 12 SR has low capacity, delay and energy. A solution with a relay close to S will experience high performance if x 12 SR is high and low performance if x 12 SR is low. It shows that the most important variable is the location of the relay, and that the forwarding probability is secondary.

Similarly, the capacity-achieving and reliability-achieving bounds are shown in Fig. 5-(bottom), together with B c opt and B r opt . In this case, there is a clear unique Pareto-optimal point with f c D = 1.5 and f c E = 1.5. It is obtained for f C = 1. This Pareto-optimal point contains several solutions. One of these Pareto-optimal solutions is represented in Fig. 6-(top). All solutions with f C = 1 have a perfect R -D link to ensure the forwarded packet perfectly arrives in D. Thus, the relay is located closer to D than to S. The depicted solution has x 1 SR 2 = 1 and p 1 SR = 0.5. The other solutions have different relay locations and forwarding probability values that verify p 1 SR x 12 SR = 0.5 to have f C = 1. For p 1 SD ≃ 0, we recall that no packet is transmitted through the S -D link, meaning there are no duplicated packets. Thus f C = f R as seen in Fig. 4-(bottom). However, for p 1 SD ≃ 0.5, the same packet can be transmitted through two paths, creating a difference between reliability and capacity criteria as seen in Fig. 5-(bottom).

2) STUDY CASE 2: Transmissions are interference limited. When p 1 SD ≃ 0, no relay position ensures p SR = 0 and p RD = 0 simultaneously, thus no solution exists in this case. It is a direct consequence of interference between S and R.

When p 1 SD ≃ 0.5, B opt is presented in Fig. 7-(top). For solutions with the lowest capacity (f C ≃ 0.5042), lowest delay (f D = 1.0) and lowest energy (f E = 1.0), the relay doesn't participate in the communication and packets only arrive in D through the direct link S -D. This is again the case if R is out of reach for S or if x 11 SR = 0. There is only one solution with the highest capacity (f C = 0.75), highest delay (f D = 1.66) and highest energy (f E = 1.5). For this solution, the relay always forwards x 11 SR = 1 and its location is represented in Fig. 6-(bottom). Since R and S use the same time slot, interference reduces the maximum link probabilities on links S -R and R-D compared to the no-interference study case 1. Here, p 1 SR = 0.5, p 1 RD = 1 and p 1 SD = 0.25 and the maximum transmission rate of R is 0.5. Delay is higher than 1 because some packets arrive on the S -R -D path.

For the solutions different from the minimum and maximum values of the three criteria, f C decreases for solutions that have a lower forwarding probability. This decrease in x 11 SR is beneficial to p 1 SR and p 1 SD since R interferes less with S. These solutions have a relay located closer to D to get a perfect link with D. Since the relay is forwarding less, capacity, energy and delay decrease. Similarly, the capacity-achieving and reliability-achieving bounds are shown in Fig. 7 achieving bounds are different. Capacity-achieving represents the upper bound. Both bounds have the same Pareto-optimal point B c opt and B r opt , which is the lowest performance point on B opt . This single Pareto-optimal point has f c D = 1.98 and f c E = 1.98 with x 11 SR = 0. This is the point where the relay is not contributing, thus packets only arrive through the direct path and capacity and reliability coincide.

B. 2-relay Pareto bounds and sets

In the 2-relay topology study, all bounds are obtained for p 1 SD ≃ 0.

1) STUDY CASE 3 : All bounds are given in Fig. 8. The Pareto optimal bound B opt is represented in Fig. 8 between the upper capacity-achieving bound and the lower reliability achieving bound as represented in Fig. 8-(bottom), due to multi-path transmissions.

2) STUDY CASE 4 : The Pareto optimal bound B opt is represented in Fig. 10-(top). Similarly to the previous study cases, the solution with lowest capacity (f C ≃ 0), lowest delay (f D = 2.0) and lowest energy (f E = 1.0) doesn't use the relays.

The solution with the highest capacity (f C = 10.16), highest delay (f D = 21.00) and highest energy (f e = 21.15) has its two relays located around the middle of [S, D] with a forwarding probability x 12 SA = x 13 SB = 1. It is in the middle of [S, D] that p 1 SA and p 2 AD (reps. p 1 SB and p 2 BD ) are maximal and equal to 0.5. There is no interference and the channel between the relays is good with p 23 AB = p 32 BA = 1. The difference with study case 3 is that here, packets can be forwarded in the loop between A and B. Relays use the maximum forwarding probability between themselves with x 12 SA = x 13 SB = 0.95. For the other solutions, one relay (A) is located closer to 3) STUDY CASE 5: For study cases 5, the two relays share the same time slot and thus transmission is interferencelimited.

The Pareto optimal bound B opt is represented in Fig. 11-(top). This bound is the same as the bound observed for study case 1 with p 1 SD ≃ 0. For the solution with the highest capacity (f C = 0.254), highest delay (f D = 2.00) and highest energy (f E = 1.498), one of its relays is in the middle of [S, D] with a forwarding probability x 12 SA = 1 and p 1 SA = 0.5. The other relay is not participating in the transmission: it is either located far from S or x 12 SB = 0. It is the same maximum performance solution than the one observed in Fig. 4-(top) for study case 1. The same type of observation can be made for the solutions with lowest capacity (f C ≃ 0), lowest delay (f D = 2) and lowest energy (f E = 1), where neither relay A nor B are used.

Interference between the relays is clearly detrimental to the network performance since solutions with a single relay dominate solutions with two relays. There are no solutions in B opt with two active relays.

C. COMPARATIVE ANALYSIS

The purpose of this section is to compare the different Pareto-optimal capacity and reliability achieving bounds. First, results related to the case where transmission between S and D is possible half the time (p 1 SD = 0.5) is investigated. Second, results related to the case where transmission between S and D is almost impossible (p 1 SD ≃ 0) are analyzed. 1) Case p 1 SD = 0.5: When one out of two packets can be transmitted on the S -D path, two different 1-relay strategies have been compared. The first one assigns a different time slot to S and R (study case 1) and the other one assigns the same time slot (study case 2). Not surprisingly, the Pareto bounds B r opt and B c opt for the interference free case dominate the one for the interfered scenario.

What is interesting to note, is that for the study case 1, the capacity-achieving upper bound B c opt = (1.5, 1.5) dominates B r opt = (2, 2). If the relay is able to leverage copies to transmit information that hasn't arrived yet through the direct path to D, then, average delay could be better than 2 hops but no shorter than 1.5 hops. Similarly, energy could be smaller than 2 transmissions but no better than 1.5 transmissions. We will show in the next section VI that the combination of source and network coding is the mean to improve the reliability-achieving bound and get closer to the capacityachieving upper bound.

2) Case p 1 SD = 0: In this case, transmission is almost impossible between S and D. We have studied different study cases and we aim at comparing their performance. First, we have seen that optimizing the problem where the two relays use the same channel in study case 5 converges to a bound where only one relay is active. Thus, interference limited solutions are not surprisingly dominated by interference free solutions. The conclusion is that for bigger networks, optimizing their performance should be done in two steps. First, derive an interference free channel allocation if possible and second, optimize the node's forwarding decisions.

We compare the optimal upper and lower bounds B c opt and B r opt obtained for the interference-free study cases 1, 3 and 4 More reliable transmission are obtained when relays can be leveraged using our broadcast forwarding mode.

It is really interesting to look at the capacity-achieving bound B c opt for study case 4. Study case 4 is the only one where a loop exists between A and B in the network. For this case, lots of copies of the same packet arrive at D because of the loop. So if it is possible to leverage all these copies using network coding, the network performance can be greatly improved since B c opt dominates the bounds of all other study cases.

If B c opt can be reached, then the optimization of the network forwarding probabilities may be simplified. There is no need to introduce constraints that avoid the presence of loops in the network. With such a broadcast oriented forwarding mechanism, loops become beneficial for network performance if network coding is used. This is a major contribution of this study. Next, we provide a simple two-layered coding approach and show its benefits for the aforementioned study cases.

VI. TWO-LAYERED CODING SOLUTION TO REACH B c opt

In the previous section, we showed that if it is possible to spread the information in the redundant packets forwarded by the relays, it is possible to improve overall network performance. We will show in this section that it is possible to breach the gap between the reliability-achieving lower bound and the capacity-achieving upper bound. The strategy we propose to leverage the redundant packets in the transmission relies on two design strategies:

• the use of fountain codes to ensure end-to-end reliability,

• the use network coding to introduce diversity in the received packets. Introducing coding capabilities requires the introduction of an additional memory of size M which stores the last M packets received by a node.

A. Coding solution

K Fragments

Encoded Packets Fig. 13. Encoding procedure for RL code 1) Fountain Codes: Fountain codes are rateless erasure codes in the sense that a potentially limitless sequence of encoding packets can be generated from the source information. This flow is stopped by the destination when it has received enough packets to recover the information [START_REF] Mackay | Fountain codes[END_REF]. As a consequence, the major advantage of fountain codes is that they are not channel-dependent, thus the same coded information flow is inherently adapted to any channel types. Besides, these codes ensure perfect reliability on the link.

There exists several class of fountain codes. In this paper, we will consider the random linear fountain code(RL code) [START_REF] Mackay | Fountain codes[END_REF]. Indeed, this code requires only 1.6 additionnal overhead packets in average for decoding information with any K fragments. This is an obvious advantage in contrast to Luby Transform code (LT code) [START_REF] Luby | LT Codes[END_REF], where the overhead is higher and depends on K. Besides, the RL code is more XOR-friendly, and so better adapted to network coding schemes. However, the decoding process of RL code is computationally more complex than LT code, since it corresponds to solving a dense linear system of equations. The encoding and decoding computations cost grows as quadratic and cubic respectively with the number of packets encoded, but this scaling is not important if K is less than 1000 [START_REF] Mackay | Fountain codes[END_REF].

RL encoding algorithm: The information from source is first partitioned into K fragments with equal length as shown in Fig. 13. Each fragment is selected randomly with probability 1/2 to be XORed to create a new encoded packet. New packets are along those lines created in order to be transmitted until the information can be recovered at destination.

RL decoding algorithm: At destination, the received encoded packets are equivalent to equations forming a linear system (where the variables are the fragments). To recover the original information, the system must be full rank. The most efficient decoding algorithm for any random codes on an erasure channel is Maximum Likelihood decoding (MLdecoding), which solves linear equations and can be performed using Gaussian elimination.

2) Network coding strategies: Network coding is a technique which consists in combining (with XOR operation) packets at the relays. This introduces packet diversity at the destination as the received packets are more likely to be independent [START_REF] Apavatjrut | Toward increasing packet diversity for relaying lt fountain codes in wireless sensor networks[END_REF]. Two intra-flow coding strategies that follow Algorithm 1 are investigated to take advantage of the multiple copies traveling in the network. We show that the increase in packet diversity that is created is an efficient mean to distributively reach the theoretical upper MO bound. In these strategies, when a packet is received, it triggers with a probability x uv ij the emission of the XOR of some packets in buffer. The two proposed strategies differ in the way the packets to be XORed are selected.

CODING STRATEGY "R-XOR": the XOR operation is made between the lastly R received packets [START_REF] Apavatjrut | Toward increasing packet diversity for relaying lt fountain codes in wireless sensor networks[END_REF] as presented in Algorithm 2 considering M = R. CODING STRATEGY "RLNC": A binary Random Linear Network Coding (coding over F 2 ) [START_REF] Ho | A random linear network coding approach to multicast[END_REF] is performed. For each packet in a relay's buffer, the relay flips a coin to know whether tot add it or not in p out , as shown in Algorithm 3. It is the same as computing an RL code with the packets in memory of the relay. It makes sense to do it since we are sending RL encoded packets at the source. A memory of size of M = K is assumed with K the dimension of the RL code. The use of a fountain code at the sources guaranties reliability of the network transmission strategy. Following is the derivation of capacity-achieving delay and energy metrics in this context.

Capacity achieving delay: To be consistent with our empirical derivation of the capacity-achieving delay presented in Section IV-C, we derive f c D as following. We assume that when the coding process ends, the number of packets N T Xs that S has transmitted is derived by tracing the last packet that has triggererd the decoding at D. When coding is used, the capacity-achieving delay is given by:

f c D = hmax h=1 h • P (h) K NT Xs
with P (h) = n(h)/N rx the statistical distribution of the delays where n(h) is the number of packets arrived in h hops at D and h max the maximum number of hops of all packets collected at D. Here, K NT Xs is the equivalent of the capacity criterion when coding is used.

Capacity achieving energy: The energy consumption is measured by summing the total number of packets transmitted by the source N T Xs and the relays N T Xr divided by K for normalization. Thus, f c E can be computed as:

f c E = N T Xs + N r=1 N T Xr K
The distance between two bounds is measured using the Generational Distance (GD) metric defined as:

GD = 1 N opt   Nopt i=1 (d p i )   1/p
Where d i is the euclidian distance between the two geometrical points of coordinates

(f c D , f c E ) and ( f c D , f c E ) d i = (f c D (i) -f c D (i)) 2 + (f c E (i) -f c E (i)) 2
Here, we use p = 2. The smaller this metric is, the closer the solutions of lower and upper bounds are from each other.

C. Lower bound results

In this section, we investigate the performance of coding strategies for the study cases 1 (p 1 SD ≃ 0.5), 3 and 4 where there is a gap between the upper bound B c opt and the lower bound B r opt . Coding introduces an overhead composed of the additional packets needed to decode the encoded stream. The overhead is measure using the following criterion:

overhead = E K * 100 = 1 K (N r -K) * 100 (22)
where K is the number of initial fragments, E is the number of packets received in excess when using RL codes and N r is the number of packets received at D before decoding the initial fragments. The transmission of coding coefficients in the encoded packets is an additional overhead. In this paper, we consider that coefficients are coded over K bits and that the packet length P L is 2560 bytes. Thus the overhead related to coefficients is given by (P L -K)/P L. This overhead has been taken into account when empirical delay and energy metrics are derived. To analyze the performance of the network coding strategies "R-XOR" and "RLNC", we set K to 50, 10, and 500 respectively. Table III presents for each study case and coding strategy the values of the generational distance and the coding overhead of Eq. ( 22). As shown in Fig. 14, the plot shows that coding in this case doesn't improve much the lower bound. This rather negative result can be explained by two reasons. First, since p 1 SD ≃ 0.5, the reliability is already high (f r = 0.75), reducing the impact of coding. Second, the benefits of coding are here lost by the coding overhead and coefficient transmission. This can be deduced from the energy performance which is slightly worse than for the no coding case.

2) STUDY CASE 3: Considering K = 50, K = 100 and K = 500 for "R-XOR" and "RLNC" respectively, the lower bound results are shown in Fig. 15. In this scenario, network coding greatly improves the lower bound B r opt and provides bounds that are very close to the capacity-achieving upper bound.

Looking at the impact of K for the "R-XOR" strategies, it can be seen that with the increase of K, the coding bound gets closer to the upper bound. It makes sense since the code dimension increases and the number of overhead packets become more negligible compared to the size of the initial data. K has not exactly the same impact on the bound for "RLNC" strategies. This is due to the increase with K of the overhead due to the coefficient stored in the encoded packets. For K = 50 and K = 100, the coefficients represent 0.24% and 0.49% of the packet. Overhead due to coefficients being rather stable, the increase of K is beneficial for the same reasons than for "R-XOR" strategies. But for K = 500, coefficients use 2.46% of the encoded packet size. This drastic increase is reducing the benefit of using a higher dimension code. Thus, the best "RLNC" strategy is to use K = 100.

For the same dimension K, "RLNC" clearly outperforms "R-XOR" since its lower bound is closer to the upper bound B c opt . However, we can note that this improvement is obtained at the cost of bigger buffer at the relays.

3) STUDY CASE 4: Here, the bounds for K = 100 and K = 500 for "R-XOR" and "RLNC" strategies are derived on Fig. 16. Different from the study case 3, the increase of K is improving the coding lower bounds. Here, the code dimension has a positive impact on the higher number of copies received at the relay. We recall that in study case 4, a loop exists. Thus, the number of overhead packets in the coding solution is really smaller than the number of redundant packets in the no-coding lower bound.

Similarly to the study case 3, "RLNC" outperforms "R-XOR". The main result of this paper is that we have exhibited a coding strategy that provides a performance bound that is really close to the capacity-achieving upper bound B c opt . We can conclude that the capacity-achieving bound we have defined in this paper is a very tight bound on the multiobjective performance of the network. The simple source and network coding strategies presented in the paper are efficient for study cases where we can leverage path diversity. Studying the capacity-achieving bound is an efficient mean to characterize the Pareto-optimal performance with respect to delay and energy consumption for a network using a broadcast forwarding paradigm.

To better understand the coding impact for these coding strategies, we further look into the overhead compared to the ideal RL coding. In the ideal situation for RL code, the number of excess packets is equal to 1.611970 in our simulation environment. Thus, the overhead proportion for the ideal situation is equal to 3.2239%, 1.6120% and 0.3224% for K = 50, 100 and 500 respectively. The closer the overhead to the ideal RL coding is, the better the network coding strategy is efficient. The generational distance and overhead are shown in Table III.

Seen from this table, the best coding strategy for study case 1 (p 1 SD ≃ 0.5) is when adopting the RLNC strategy for K = 100 with the lowest value of generational distance equal to 0.6863. For the study case 3, the best coding strategy is also adopting the RLNC strategy for K = 100 with the lowest value of generational distance equal to 0.1152. However, for the study case 4, the best coding strategy is when adopting the RLNC strategy for K = 500 with the lowest value of generational distance equal to 1.57. This means that RLNC strategy gives results very close to the optimal theoretical bound. But considering the transmission of coding coefficients, the performance doesn't always increase with K.

VII. CONCLUSION

This paper has presented a flexible framework for evaluating the performance of simple wireless relay networks with respect to several performance criteria. It has been designed to account for the broadcast nature of wireless communications and for an accurate interference characterization for the network. This framework allows for the determination of two lower and upper Pareto bounds and their corresponding Pareto solutions. Network model and bounds for 1-relay and 2-relay networks have been assessed though simulations. We have shown that the upper MO bound provides a tight bound on the performance of network coding strategies. Thus, this work not only confirms the accuracy of our optimal theoretical bound, but also proposes a way of approaching it as close as wanted. This work will be extended to tackle problems where more relays belong to the network of interest. The problem will as well be formulated for the case where several concurrent flows transit in the network. APPENDIX This Appendix details the derivation of f C in Eq. ( 18), f D Eq. [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] and f E in Eq. ( 20) for the 2-relay cases.

A. Capacity criterion f C

f C is defined as the average number of packets received by the destination per packet sent by S. It is derived by adding the success probabilities of a packet arriving at D through all possible path as defined in Eq. (4). For example, for the direct path S-D, the success probability equals τ 1 S p 1 SD . For the relay path S -A -D, the capacity equals to τ 1 S Q 12 SA p 2 AD . Similarly, the success probability for other paths can be derived as shown in Table IV.

The sum of the success probabilities for all paths is the sum of the terms of the following infinite geometric series:

f C = τ 1 S p 1 SD + (E + F )(1 + Q 23 AB Q 32 BA + (Q 23 AB Q 32 BA ) 2 + +Q 23 AB Q 32 BA ) 3 + • • • + (Q 23 AB Q 32 BA ) n ) with E = (Q 12 SA + Q 13 SB Q 32 BA )p 2 AD and F = (Q 13 SB + Q 12 SA Q 23 AB )p 3 BD .
Here, τ 1 S (E +F ) is the first term of the series, and Q 23 AB Q 32 BA is the common ratio. As n goes to infinity, the absolute value of Q 23 AB Q 32 BA must be less than one for the series to converge. This is true since we add the constraint Q 23 AB ≤ 1 -∆ and Q 32 BA ≤ 1 -∆ (∆ = 0.05) in our MO problem. The sum then becomes:

f C = τ 1 S p 1 SD + τ 1 S 1 -Q 23 AB Q 32 BA (E + F ) TABLE V PATH ANALYSIS

TABLE VI PATH ANALYSIS FOR ENERGY BY RELAYS

Path

Energy per path S-D

f SD = 0 S-A-D f SAD = τ 1 S Q 12 SA S-B-D f SBD = τ 1 S Q 13 SB S-A-B-A-D f SABAD = τ 1 S Q 12 SA (Q 23 AB Q 32 BA ) S-B-A-B-D f SBABD = τ 1 S Q 13 SB (Q 32 BA Q 23 AB ) S-A-B-D f SABD = τ 1 S Q 12 SA Q 23 AB S-A-B-A-B-D f SABABD = τ 1 S Q 12 SA Q 23 AB (Q 32 BA .Q 23 AB ) S-B-A-D f SBAD = τ 1 S Q 13 SB Q 32 BA S-B-A-B-A-D f SBABAD = τ 1 S Q 13 SB Q 32 BA (Q 23 AB Q 32 BA ) . . . . . . .

B. Delay criterion f D

f D is defined as the average delay a packet sent by the source needs to reach the destination. It is calculated by summing the delays for all packets arriving through all possible paths and dividing the result by the number of copies f C as defined in Eq. [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF]. A similar path analysis is done for the delay computation in Table V. For example, for the direct path S-D, the packet arrives in D in one hop and the corresponding delay equals f SD = p 1 SD . For the relay path S -A -D, the packet takes two hops to arrive at D and thus the delay of the path equals to f SAD = 2Q 12 SA p 2 AD . The infinite sum of the delays of Table V is performed and provides a delay criterion of:

f D = 1 f C • [ τ 1 S (1 -Q 23 AB Q 32 BA ) 2 (A + B) + τ 1 S p 1 SD ] with A = p 2 AD [Q 13 SB Q 32 BA (3 -Q 23 AB Q 32 BA ) + 2Q 12 SA ] and B = p 3 BD [Q 12 SA Q 23 AB (3 -Q 23 AB Q 32 BA ) + 2Q 13 SB ]
. Again it originates from the summation of the terms of an infinite series.

C. Energy criterion f E

f E is defined as the average number of emissions done by all nodes per packet sent. It is derived by summing the probability for a relays to emit a packet per path and the probability for the source to emit a packet (which is equal to its rate τ 1 S ). Similarly, the energy consumed per paths is shown in Table VI for all possible paths. Again, the summation of the terms of an infinite geometric series leads to the following criterion:

f E = τ 1 S + τ 1 S 1 -Q 23 AB Q 32 BA (Q 12 SA + Q 13 SB Q 32 BA +Q 12 SA Q 23 AB + Q 13 SB )

Fig. 3 .

 3 Fig. 3. Relay location search space C

Fig. 4 .

 4 Fig. 4. STUDY CASE 1 with p 1 SD ≃ 0: Pareto-optimal bound Bopt (top). Capacity and reliability-achieving bounds B c and B r (middle) and their corresponding Pareto-optimal bounds B c opt and B r opt (bottom).

Fig. 5 .

 5 Fig. 5. STUDY CASE 1 with p 1 SD ≃ 0.5: Pareto-optimal bound Bopt (top). Capacity and reliability-achieving bounds (bottom).

Fig. 4 -

 4 (middle) represents B c and B r and Fig. 4-(bottom) their Pareto-optimal versions B c opt and B r opt . Since all packets arriving at D use the S -R -D path, f R and f C are equal and thus B c and B r match as expected. The solutions with a very high f c D are the ones where the S -R path is very low and thus, lots of retransmissions would be necessary to overcome the high packet loss probability. Pareto-optimal bounds (B c opt and B r opt ) are composed of the solutions concurrently minimizing f c D and f c E . These solutions have a forwarding probability x 12 SR = 1 and the relay is located in the very close neighborhood of the center of the [S, D] segment.

Fig. 6 .

 6 Fig. 6. Pareto-optimal solutions for study case 1 (p 1 SD ≃ 0.5) and 2 (top) and solution with maximum f C , f D and f E in study case 2, p 1 SD ≃ 0.5 (bottom).

12 SA = 1 and x 13 SB = 1 .Fig. 8 .

 121318 Fig. 8. STUDY CASE 3: Pareto-optimal bound Bopt (top). Capacity and reliability-achieving bounds B c and B r (middle) and their corresponding Pareto-optimal bounds B c opt and B r opt (bottom).

Fig. 9 . 4 S 1 SB = 0 and p 2 BD = 1 .

 94121 Fig. 9. Pareto-optimal solutions for study cases 3 and 4

Fig. 10 .

 10 Fig. 10. Study Case 4: Pareto-optimal bound Bopt (top). Capacity and reliability-achieving bounds B c and B r (middle) and their corresponding Pareto-optimal bounds B c opt and B r opt (bottom).

Fig. 11 .

 11 Fig. 11. Study Case 5: Pareto-optimal bound Bopt (top). Capacity and reliability-achieving bounds B c and B r (middle) and their corresponding Pareto-optimal bounds B c opt and B r opt (bottom).

for study case 4 B c opt for study case 4 B r opt for study case 3 B c opt for study case 3 B r opt for study case 1 B c opt for study case 1 Fig. 12 .

 44331112 Fig. 12. B c opt and B r opt for study cases 1, 3 and 4 where p SD ≃ 0

Algorithm 2 p

 2 new = combine(p, M EM ) p new = p; for each packet p k = p in M EM do p new = p new ⊕ p k ; end for return p new ;

Algorithm 3 p

 3 new = combine(p, memory) p new = p ; for each packet p k = p in M EM do Generate a random value p rand ∈ [0, 1]; if (p rand 0.5) then p new = p new ⊕ p k ; end if end for return p new ; B. Lower bounds with coding 1) Coding simulations setup: We consider a message divided into K fragments whose length is the size of a packet. Transmissions are time multiplexed where one packet can be transmitted in one time slot. Note that a frame of |T | time slots is repeated until the end of simulation. The source sends one RL encoded packet to D in the first time slot of each frame. Location of the relays and their forwarding probability from B opt are used. S ends the transmission of RL packets as soon as D can recover the original message and acknowledge the successful reception.

5 Fig. 14 . 5 1)

 5145 Fig. 14. NC lower bounds for 1-relay study case 1 and p 1 SD ≃ 0.5

Fig. 15 .

 15 Fig. 15. NC Lower bound for 2-relay study case 3.

for study case 4 B c opt for study case 4 Fig. 16 .

 4416 Fig. 16. NC Lower bound for 2-relay study case 4.

SB p 3 BDS 3 BDS 2 AD

 332 -A-B-A-D f SABAD = 4Q 12 SA (Q 23 AB .Q 32 BA )p 2 AD S-B-A-B-D f SBABD = 4Q 13 SB (Q 32 BA .Q 23 AB )p 3 BD S-A-B-D f SABD = 3Q 12 SA Q 23 AB p -A-B-A-B-D f SABABD = 5Q 12 SA Q 23 AB (Q 32 BA .Q 23 AB )p 3 BD S-B-A-D f SBAD = 3Q 13 SB Q 32 BA p

  Flow conservation. The sum rate of all outgoing links is lower or equal to the sum rate of all incoming links, i.e.

			Relay A
			τ A
	S	p SD p SA	p AB	p AD	D
		p SB	p BA	p BD
			τ B Relay B
	Fig. 1. 1-relay and 2-relay network topologies
	be the emission rate matrix. A particular instance of τ values
	is feasible if and only if the following Properties 1 and 2 hold
	for each node:
	PROPERTY 1:

  Algorithm 1 Intra flow network coding algorithmfor each relay node i do if relay node j received a packet p from i at time slot u then Store the packet p into FIFO memory of size M

	ij > 0 then if v x uv p xor = combine(p, FIFO);
	Generate a random value x ∈ [0, 1];
	for (v = 1; v |T |; v = v + 1) do
	if x uv ij	x then
	Transmit encoded packet p xor in time slot v;
	end if
	end for
	end if
	end if
	end for

http://wsnet.gforge.inria.fr/