Qi Wang

Claire Goursaud

Katia Jaffrès-Runser

Jean-Marie Gorce

Fundamental limits of wireless ad hoc networks: lower MO bounds

Keywords: Multi-objective optimization, performance evaluation framework, coding strategies, fountain code, RL code, network coding, multi-hop networks

, Pareto-optimal performance bounds and network parameters have been derived for a 1-relay and 2-relay network within a MultiObjective(MO) performance evaluation framework. We show in this report that these bounds are tight since they can be reached by simple practical coding strategies performed by the source and the relays. Such strategies constitute achievable lower MO performance bounds on the real MO performance limits. More precisely, we adopt a coding strategy where the source transmits a random linear fountain code which is coupled to a network coding strategy performed by the relays. Two different network coding strategies are investigated. Practical performance bounds for both strategies are compared to the theoretical bound. We show that the theoretical bound is tight: generational distance between the practical and theoretical bound for the best strategy is only of 0.0042.

Bornes inférieures pour la recherche des performances multi-critères d'un réseau ad hoc sans fil

Résumé :

Ce rapport s'intéresse à la caractérisation des performances en limite d'un point de vue multiobjectif des transmissions dans un réseau sans fil ad hoc multi-saut. Les critères de performance considérés sont la capacité ou la robustesse de la transmission, le délai de bout en bout et la consommation énergétique. L'objet de cette étude est de déterminer les meilleurs compromis possibles entre ces critères en ajustant les décisions de transmission (sélection des canaux de transmissions et des relais). Dans nos précédents travaux présentés dans le rapport [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF], nous avons proposé un modèle de réseau et une modélisation du problème d'optimisation multicritère qui nous a permis de dériver les limites de performance Pareto-optimales et les paramètres réseau pour un réseau 1-et 2relais. Ces limites en performance Pareto-optimales sont des bornes supérieures.

L'objectif de ce rapport est de que ces bornes supérieures sont serrés, car elles peuvent être atteintes à l'aide de simples stratégies de codage effectuées par la source et les relais. Ces stratégies constituent des bornes inférieures réalisables. Nous présentons des résultats où la source émet un code source linéaire aléatoire couplé à une stratégie de codage réseau effectuée par des relais. Deux différentes stratégies de codage réseau sont étudiées et comparées à la borne supérieure théorique obtenue par le modèle d'évaluation de performances multicritère. Nous montrons que la borne théorique est serrée : la distance générationnelle entre la borne théorique et pratique pour la meilleure stratégie est seulement de 0,0042.

Mots-clés : limites fondamentales, capacité, délai, énergie, réseau sans-fil, borne inférieure, borne multicritère, code fontaine, code RL

Introduction

Two main yet complementary directions have driven research 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 multichannel mac protocol with power control for multi-hop mobile ad hoc networks[END_REF], scheduling, frequency assignment,... ), coding (source coding [START_REF] Luby | Proc. The 43rd IEEE Symposium on Foundations of Computer Science (FOCS)[END_REF][START_REF] David | Fountain codes[END_REF], network coding [START_REF] Ahlswede | Network information flow[END_REF], [START_REF] Ho | A random linear network coding approach to multicast. Information Theory[END_REF]), and routing (reactive routing [START_REF] Perkins | Ad hoc On-demand Distance Vector Routing[END_REF], proactive routing [4], 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] Luo | Engineering Wireless Mesh Networks: Joint Scheduling, Routing, Power Control and Rate Adaptation[END_REF][START_REF] Toumpis | Capacity regions for wireless ad hoc networks[END_REF] and protocols maximizing network capacity [4,[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 [3,[START_REF] Goldsmith | Beyond Shannon: The Quest for Fundamental Performance Limits of Wireless Ad Hoc Networks[END_REF]. With the introduction of new applications (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 2objective 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 | 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 interference-limited 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 different network coding strategies are investigated. Practical performance bounds for both strategies are compared to the theoretical bound. Theoretical bound is really tight: generational distance between the practical and theoretical bound for the best strategy is only of 0.0042. This paper is organized as follows. First, Section 2 summarizes the MO performance evaluation framework presented in [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF]. The energy/delay MO bounds obtained for capacity achieving 1-relay and 2-relay transmissions are presented in Section 3. Section 4 presents the network strategies considered to derive our MO lower bounds. Finally, both upper and MO lower bounds are compared in Section 5 and 6 concludes the paper.

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

Network model

We assume a synchronized network where transmissions are time-multiplexed. A frame of |T | time slots is repeated indefinitely. One or more packets (or symbols) 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. 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 symbol or 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 models interference as an additive noise and is computed considering the distribution of the bit error rates (BER) or the packet error rates (PER) as shown hereafter. Notations are summarized in Table 1.

A wireless ad hoc network is modeled in this work 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. 1. 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 . 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.

A The network is synchronized. Depending on their time slot assignments, sources and relays emit their symbols (or packets) at the beginning of their assigned time slots. Nodes emitting in the same time slot may interfere, reducing reception probability of their emitted data. Nodes that are not emitting in a time slot can receive symbols (or packets) in this time slot. We assume that relays have an incoming buffer and |T | outgoing buffers. All buffers are able to store the amount of symbols (or packets) transmitted in one time slot duration.

In our examples, they can store one packet. A relay receiving a packet has to decide if it will discard it or in which slot of the next frame it will send it. We consider as well in our model that a relay can not differentiate packets: identical packets are indiscernible.

Emission rate

In our model, 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. Thus, we define τ u i as the emission rate of node i in time slot u. It is normalized by its maximum transmission rate and thus its value belongs to the interval [0, 1]. Emission rate τ u i can be interpreted as the the emitting probability for node i in time slot u. For example, if a node i with τ u i = 0.5, it means node i will decide with probability 0.5 to transmit a packet in time slot u in the upcoming frame. Note that the emission rate of destinations is zero.

Here, τ u i varies according to the decisions of node i on time slot u. For instance, if a node decides to drop one packet out of two received on a same time slot u, the emission rate on channel u would become half the rate at which it received packets on the same time slot. Similarly, a node may transmit one packet every two received packets on time slot u because it is applying a coding scheme for which two packets are combined into a single transmitted packet though network coding. All in all, a relay is capable of modifying its emission rates to combat transmission errors.

As mentioned in [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF], a set of τ u i values for all nodes and time slots is valid if flow conservation at a each node is guarantied and half duplex transmissions are possible. The last property translates into the fact that each node has enough time to transmit and receive in any time slot.

An emission

(i, u) ∈ V × T is said to be active if τ u i > 0. As a consequence, the set of active emissions A is given by A = {(i, u) ∈ V × T | τ u i > 0}.
Similarly, the set A u refers to the set of active emissions restricted to slot u. We have

A u = {(i, v) ∈ V × T |τ u i > 0, v = u}

Channel probability

The channel between node i and j in time slot u is characterized by the channel probability p u ij , which is a function of the statistical distribution of the Signal to Noise and Interference Ratio (SINR) at the location of the destination node j. In this paper, we consider that the transmissions are packetized thus channel probability is modeled using an average Packet Error Rate (PER).

We assume that there is no medium access mechanism and that emissions are totally independent. Within a time slot u, channel access is purely randomized and depends on the emission probabilities of the active nodes. Thus, on edge (i, j, u), the set of interferers present is random. In order to derive an average channel probability over time, we compute the average power of interference on the edge over time. Therefore we have to enumerate all possible configurations where active nodes interfere with the emitter i. These configurations are designated as interfering sets.

Interfering sets We recall that A u is the set of active emissions in time slot u. An interfering set I u ij for edge (i, j, u) belongs to the set of all possible interfering sets L u ij on this edge. L u ij is the power set P(A u -{i}), i.e. the set of all subsets of A u -{i}. Because of the half-duplex constraint, the receiver j is kept in the set A u -{i}. Thus, the channel probability computation accounts for the interfering sets where j is active. If j is active, the SINR is very low and transmission on the edge (i, j, u) is impossible.

Inria

Channel probability derivation Equation (1) details the derivation of the channel probability p u ij as the average of the PER experienced for all possible interfering sets l ∈ L u ij on edge (i, j, u) referred to as P ER l :

p u ij = l∈L u ij [1 -P ER l ] .P l (1)
where P ER l = P ER(γ l ), l ∈ L u ij and γ l is the SINR experienced on the edge (i, j, u) when the nodes of the interfering set l are active.

P l is the probability for nodes of the interfering set l to be active and create interference on (i, j, u). More specifically, it is the probability that the nodes of the interfering set l are transmitting concurrently and the others are not:

P l = k∈l τ u k • m∈{A u \l} (1 -τ u m ) (2)
In ( 2), k∈l τ u k gives the probability that the active nodes of the interfering set l are transmitting and the other product the probability that the {|A u \ l}| other active nodes are not.

SINR SINR between nodes i and j in time slot u is defined by

γ u ij = P T •aij N0+I u ij
where I u ij is the interference power on the edge (i, j, u) and N 0 the noise power density. We have I u ij = k∈I u ij P T • a kj with a ij the attenuation due to propagation effects between nodes i and j for a simple isotropic model. All nodes use the same power P T .

Packet error rate (PER) For a specific value of SINR γ, the packet error rate P ER is computed with

P ER(γ) = 1 -[1 -BER(γ)]
N b where N b is the number of bits of a data packet and BER(γ) is the bit error rate for the specified SINR per bit γ which depends on the physical layer technology and the statistics of the channel. Results are given for an AWGN channel and a BPSK modulation without coding where BER(γ) = 0.5 * erfc( √ γ).

Forwarding and scheduling decisions

The forwarding and scheduling decision is represented by the probability x uv ij of a node j to transmit on time slot v a packet coming from node i on time slot u, which is related to the emission rates and the channel probabilities 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 ensure a flow conservation and strictly constrain the choices of forwarding probabilities.

The forwarding probabilities represent the decisions of the nodes to either (i) retransmit all the packets or symbols received or (ii) reduce the output rate by dropping or re-encoding them together.

MO optimization problem

In this section, we briefly present the MO optimization problem we solve to extract the Pareto-optimal bound and corresponding network parameters for performance criteria relative to capacity, delay and energy. A Pareto optimal set is composed of the non-dominated solutions of the solution space with respect to the performance metrics considered in the MO problem. The definition of dominance is as follows:

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.

Solution and search space

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 number of time slots |T | and the forwarding probabilities represented by matrix X ∈ X . In this work, considered variables are the location of the N relays and their respective forwarding probabilities. Location of relays are chosen in a convex set C. For one network realization, the set of all forwarding probabilities are chosen in a set X . Thus the complete search space is S = C N × X .

Let f C , f D and f E be the performance criteria relative to capacity, delay and energy, respectively. Capacity is maximized, while energy and delay are minimized. Our goal is to solve the following multiobjective optimization problem by finding the set of Pareto-optimal solutions S opt defined by:

S opt = {x ∈ S | ∀x ∈ S opt , ∀y ∈ S c opt , x ≻ y} (4)
where S opt ∪ S c opt = S and notation x ≻ y means that x strictly dominates y.

Optimization criteria

A brief description of the criteria considered in this work is given here. For conciseness purposes, we do not describe their derivation and refer the reader to [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF] for further details. Their computation relies on the definition of a transition matrix which is composed of the probabilities for a flow of packets to be retransmitted by the nodes of the network which is inspired by the theory of discrete absorbing Markov chains. The values are obtained for a steady state of the network and give for one single source-destination flow.

Redundancy, capacity and robustness With our steady state computation, the number f of packets received at the destination for one original packet sent by the source can be easily derived. Due to wireless broadcast emissions, several copies of the original packet may reach the destination. The number of copies depends on the transmission decisions of the relays which can not discriminate packets in our model. Therefore, we can say • if f < 1, f can be interpreted as a reliability criterion defined as the probability to get one packet at the destination.

• if f ≥ 1, there may be at most f different packets. Consequently, f provides both an upper bound on the network capacity and redundancy (which Inria is equal to f -1 in our case). Thus, a general expression of the real capacity f C for the flow is given by

f C = min(1, f )
This bound is exact if there exists a practical transmission scheme where all packets received at the destination are different. This may be possible if an optimal network coding strategy is found where all received packets are linearly independent combinations of the original flow.

Delay criterion Assuming that a relay introduces a delay of 1 unit, a h-hop transmission introduces a delay of h -1 units. Let p(H = h) be the probability for a transmission to destination D to be done in h hops. Consequently, the average end to end delay is computed by the infinite sum:

f D = ∞ h=1 (h -1) • p(H = h)
Note that the direct transmission has a path length of 1, and thus a contribution of zero to this delay criterion.

Energy criterion

We consider in this model that the main energy is consumed by emission of a packet. Thus, the energy criterion f E is computed by counting the number of packets transmitted by the source and the relays in the network.

Delay energy Pareto bounds

Our MO optimization goal is to concurrently capacity-achieving delay and energy metrics. Here, capacity achieving criteria f * D and f * E are obtained by respectively dividing f D and f E by f C = min(f, 1). It permits to incorporate the effect of limited capacity on delay and energy in our analysis. For example, if f = 0.5, f * D = 2f D and f * E = 2f E which means that 2 times more packets have to be sent in average to reach perfect capacity which incurs double delay and energy. Theoretical Pareto-optimal solutions and bounds are obtained using non-dominated sorting genetic algorithm (NSGA-2) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. To assess our network model, we simulate the Pareto-optimal solutions using the event-driven network simulator WSNet [START_REF] Wsnet | Worldsens simulator[END_REF].

2-relay network

Different from [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF], we concentrate on the 2-relay network where no link exists between A and B. This choice has been made to analyze first our model and network coding strategies when no loop exists in the network which is usually detrimental to network coding. Of course, further work will investigate this aspect. The core of this paper is to see our coding strategies create lower MO performance bounds that are close to the theoretical MO upper bound. If the gap between both bounds is low, the MO upper bound is tight.

As shown in Fig. 2, |T | = 3 times slots, the source is transmitting in time slot 1, and relay A and B are transmitting in time slot 2 and 3, respectively. Propagation and physical layer parameters are illustrated in Table 2. The distance between S and D is 620 meters and the direct transmission is near 0. The set of Pareto optimal locations of relays is searched in a continuous rectangular surface area of size 620*620 square meters located in-between S and D.

Theoretical criteria for 2-relay network

The theoretical criteria are derived analytically as follows [START_REF] Jaffres-Runser | Fundamental limits of wireless ad hoc networks: upper MO bounds[END_REF]:

     f C = min[τ 1 S .(p 1 SD + p 1 SA .x 12 SA .p 2 AD + p 1 SB .x 13 SB .p 3 BD ), 1] f D = τ 1 S .(p 1 SA .x 12 SA .p 2 AD + p 1 SB .x 13 SB .p 3 BD ) f E = τ 1 S .( 1
+ (p 1 SA .x 12 SA + p 1 SB .x 13 SB )) (5)
Inria Thus, the capacity achieving f * D and f * E can be obtained by dividing the value of f D and f E by min(f, 1). For NSGA-2, we use a population of size 100 and generations of number 1000. The crossover probability is set at 0.9.

Simulated criteria values

Each Pareto-optimal solution of the MO upper bound is simulated with WS-Net. For each solution, we know the location of the relay and its forwarding probabilities which represent its decisions to broadcast a packet or not on any time slot if a packet is received. In our simulations, we implement the perfect TDMA which is given in the 2-relay example. S sends a packet every first time slot of every frame.

Four performance criteria are extracted from the simulations:

• f s is measured by the total number of packets N rx received at D (including copies) divided by the number of packets transmitted by the source.

• f s R measures the number of different packets arriving at D (copies are disregarded).

• f s D is the average transmission duration of the packets received at D. It 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. f D is then calculated with

f s D = ∞ h=1 (h -1

).P (h).

In this calculation, we consider similarly to our model that a transmission on a path of h hops introduces a delay of h -1 units.

• f s E is the sum of the number of packets transmitted by the source and the relays.

In Fig. 3, we plot each Pareto-optimal solution in the subspace defined by delay and energy criteria. Since both criteria are minimized, dominating solutions are the ones located the closest to point (0, 0).

Two different bounds are represented in Fig. 3: an upper and a MO lower bound on the capacity achieving delay and energy trade off. The theoretical MO upper bound is derived with our theoretical framework and assessed through simulations using f s D /f s and f s E /f s . Clearly, simulation results match theoretical solutions.

The second bound, which is dominated by the first bound, constitutes a MO lower bound on the delay energy trade-off. This bound is obtained when the network uses a pure relaying strategy defined by our forwarding probabilities x uv ij . In this pure relaying strategy, the destination is not interested in the numerous copies but only in the unique packets it receives. This MO lower bound is obtained by plotting the values of f s D /f s R , where f s R is nothing but the source destination transmission success rate computed by simulations. As seen on this plot, the gap between lower and MO upper bounds is important. With the pure relaying strategies, the copies created by broadcast transmissions are considered as redundant and unnecessary packets. However, as said earlier, it is possible to mitigate losses on the channel using network coding. Information is diversified among the various copies being broadcast in the network. The main intuition is that a network transmission strategy that leverages network coding would provide a tighter MO lower bound. That is why we investigate a combined solution where fountain codes and network coding are mixed together.

Network strategies

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. Indeed, the major advantage of fountain codes is that they are not channeldependent, thus the same coded information flow is inherently adapted to any channel types. Indeed, the coding process ends as soon as the destination has received enough packets [START_REF] David | Fountain codes[END_REF]. The required amount of received packets is equal to or only slightly larger than the number of initial information.

In ideal situation, the random linear fountain code(RL code) [START_REF] David | Fountain codes[END_REF] requires only 1.6 overhead packets in average for decoding information with any K fragments. That is an obvious advantage in contrast to Luby Transform code (LT code) [START_REF] Luby | Proc. The 43rd IEEE Symposium on Foundations of Computer Science (FOCS)[END_REF], where the overhead is higher and depends on K. 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] David | Fountain codes[END_REF].

In this paper, we focus on the relaying strategies decreasing the redundancy, so the more light-weight and XOR-friendly RL code will be considered. The Inria encoding and decoding processes for RL code are described as follows.

Encoding algorithm

The information from source is first partitioned into K fragments with equal length when being sent to destination, as shown in Fig. 4. Each fragment is selected uniformly 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. When the destination receives enough encoded packets, the decoding process will be started. These encoded packets are equivalent to equations forming a linear system of equations and the goal is to obtain a system of full rank in order to recover the original information. The most efficient decoding algorithm for any random codes on an erasure channel is Maximum Likelihood decoding (ML-decoding), which solves linear equations and can be performed using Gaussian elimination. The ML-decoding provides small error probability of decoding, however its complexity can grow rapidly with both N (number of received packets) and K (code length), in the order of O(NK) [2].

K Fragments

Coding strategies

In this section, we propose to adopt combined fountain and Network Coding strategies to reach the upper MO bound. A source S transmits a RL encoded flow to a destination D through the 2-relays network as shown in Fig. 2. The following coding strategies are investigated to exploit the multiple copies and increase packet diversity to reach the 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 the buffer. The two proposed strategies differ from the way of selecting the packets to be XORed, as described below:

Coding Strategy 1: XOR combination of R last packets [2]: The XOR is made between the latest received R packets in their buffer, as shown in Algorithm 1.

Algorithm 1 XOR combination of R last packets

for each relay node i do if relay node i received a packet p from j at time slot u then Store the packet p into FIFO buffer of size R Generate a random value x ∈ [0, 1];

for t = 1; t |T |; t + + do if x ut ij
x then for each packet p k = p in the buffer do p xor = p ⊕ p k ; p = p xor ; end for Transmit that encoded packet p using time slot t; Break; end if end for end if end for Coding Strategy 2: Binary Random Linear Network Coding (coding over F 2 ) [START_REF] Ho | A random linear network coding approach to multicast. Information Theory[END_REF]: For each packet in relay's buffer, the relay flips a coin to know whether it combines it or not in the sent packet, as shown in Algorithm 2. It is like doing an RL code on the packets in the buffer of a relay. It makes sense to do it since we are sending RL encoded packets at the source. A buffer size of K is assumed with K the dimension of the RL code.

Simulation Results

In this section, we focus on the previously described 2-relays network to investigate the performance for different coding strategies by using WSNet. Our aim is to evaluate if the previous coding strategies can make a full use of the redundancy and increase the packet diversity to get closer to upper MO bound. The overhead for each coding strategy is also investigated.

Simulation settings

We consider a message divided into K fragments whose length is the size of a packet and 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 linearly combines these fragments at random following an RL code and sends one encoded packet to D in the first time slot of each frame. We extract the location of the relays and their forwarding probability from each Pareto optimal solution of the MO upper bound. S will end to send the RL encoded as soon as D can recover the original message and acknowledge the successful reception.

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.

Simulated criteria for coding strategies

Capacity achieving delay f * D only depends on the time the last packet that has triggered decoding at D has spent in the network before arriving at D. We assume when the coding process ends, the number of packets that S transmits is N T Xs and the last packet arrived has arrived in h hops at D. Then f * D can be derived as f * D = N T Xs -1 + h -1 K Here, the reason why we divided by K is that we can derive average delay for one packet so as to be consistent with the no-coding scheme.

Capacity achieving energy

The energy consumption is measured by summation of the total number of packets transmitted by the source N T Xs and the

RR n°7905

f * E = N T Xs + N r=1 N T Xr K
To shorten our simulation duration and still show the performance of our coding strategies, only one Pareto-optimal solution out of 4 are uniformly selected on the upper MO bound. Thus, we evaluate the efficiency of our coding strategies over 25 sets of locations and forwarding probabilities instead of 100 solutions in the model. The experiments are repeated a 1000 times and criteria are averaged over these 1000 instances. Propagation and physical layer parameters are illustrated in Table 2. Distance between the solutions of upper and lower bounds are measured by the generational distance.

Generational Distance (GD)

This metric was proposed by Van Veldhuizen and Lamont [START_REF] Van Veldhuizen | Evolutionary computation and convergence to a pareto front[END_REF]. The generational distance measures the distance between a set of n solutions and the theoretical Pareto front (which is in our case the MO upper bound). It is defined by:

GD = 1 N opt   Nopt i=1 (d p i )   1/p
with p = 2 because we consider 2 criteria in this problem. Here d i is the euclidian distance between the two geometrical points of coordinates (f th D , f th E ) and (f sim D , f sim E )

d i = (f th D (i) -f sim D (i)) 2 + (f th E (i) -f sim 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.

Since the performance of a fountain code is determined by the number of overhead packets required to decode the original message, the overhead will also be investigated in our paper. The overhead, expressed in percentage, measures the coding efficiency when using different coding strategies. It can be derived as

overhead = 1 K (E) * 100 = 1 K (N r -K) * 100
where K is the number of fragments, E is the number of excess packets when using RL codes and N r is the number of packets received at D.

Simulation results

RL code

To analyze the performance of RL code and the effect of K on f * D and f * E , we set K to 50, 100 and 500 respectively. As shown in Fig. 5, the plot highlights that using coding only at the source does not improve the performances, we even get worse results than the no-coding lower MO bound. The reason is that RL allows to guarantee the information reception but does not counter the path loss. Even worse, because of the overhead of code, the performance may be no better than the no-coding lower MO bound. However, as K increased, the performance is getting better, which makes sense since we increase the code dimension and the number of overhead packets become more and more negligible regards to the overall information.

Coding Strategy 1

To investigate the performance of coding strategy 1, we consider the RL code with K = 500 performed at the source and set the XOR combination with R=4, 6 and 8 respectively performed at relays. Seen from Fig. 6, the performance increased with the increase of R. That is more packets are combined together, the closer the bounds reaches the upper MO bound. However, as we increase R to 8, there is significant increase compared to R = 6 cases.

Coding Strategy 2

Considering K = 100 and 500 for RL code at source and relays respectively, the results of coding strategy 2 is shown in Fig. 7. Compared with the coding strategy 1, we can see the bounds are much closer to the upper MO bound. However, we can note that this improvment is obtained at the cost of bigger buffer in the relays. 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 3. Seen from this table, the best coding strategy is when adopting the coding strategy 2 for K = 500 with the lowest value of generational distance Inria and overhead equal to 0.0042 and 0.4252% respectively. This means that this strategy gives results very close to the optimal theoretical bound. Due to the time simulation constraints, we did not investigate higher K. However, thanks to the analysis of Fig. 5, we can deduce that the higher K is, the closer to the bound we will be.

Conclusion

In this paper, we have proposed to adopt a combination of fountain code and network coding to reach the Pareto-optimal performance bounds. Two proposed coding strategies are investigated for a specific multi-hop network. Practical performance bounds for both strategies are compared to the upper bound. They constitute two achievable lower bounds on the capacity achieving energy and delay trade-off. The results show that the upper bound is tight: generational distance between the lower and upper bound for the RLNC coding strategy is only of 0.0042 for the lowest coding overhead of 0.4252%. Thus, this work not only further confirms the accuracy of our optimal theoretical bound, but also proposes a practical way of approaching it really closely. Future work will concentrate on tackling bigger network instances, where interference becomes a really limitating factor. In parallel, we will investigate coding techniques defined for higher finite field dimensions.

Figure 1 :

 1 Figure 1: Network model

Figure 2 : 2 -

 22 Figure 2: 2-Relay network

  from simulation Upper MO Bound from model Lower MO bound from simulation Lower MO bound from model

Figure 3 :

 3 Figure 3: Lower and MO upper bound results.

Figure 4 :

 4 Figure 4: Encoding procedure for RL code

Inria

Figure 5 :

 5 Figure 5: RL code results.

Figure 7 :

 7 Figure 7: RLNC Coding Strategy 2.

  set of sources O and destinations D is defined. A source S o ∈ O, o ∈ {1, .., |O|} can emit a flow of data to a single destination D d ∈ D, d ∈ {1, .., |D|} or to several ones. We make the assumption that source and destination nodes do not relay the information. Sources only emit packets and destinations only

	Table 1: Main notations for the network model Set of nodes and set of edges V ; E O ; R ; D Set of source, destination and relay nodes
	N		Number of relay nodes
	T i ; -→ N u	←-i N u	Set of time slots in a frame Set of outgoing and incom-ing edges at node i on slot
			u
	p u ij	Channel probability on edge
			(i, j) for time slot u
	τ u i	Emission rate of node i in
			time slot u
	x uv ij	Forwarding	probability:
			Probability of j to forward
			in time slot v a packet
			received from i in time slot
			u
	f C , f D , f E Capacity, delay and energy
			criteria
	receive packets. Multi-hop transmissions are allowed and we model the other
	nodes as relay nodes R = V -O -D. We have N = |R| the number of relays in the network.
				Inria

Table 2 :

 2 Propagation and physical layer parameters

	Parameter values
	Packet length	2560Bytes
	Transmission Power 0.151mW
	Bandwidth	1Mbps
	Pathloss exponent	3
	Antenna gains	G T = G R = 1
	N 0 Carry frequency	-192dBm/Hz 2.4GHz
	Channel Model	AWGN
	Modulation	BPSK
	relays N T Xr divided by K. Thus, f * E can be computed as

  Figure 6: Coding Strategy 1 results obtained for RL code with K=500.

	4.6
	4.5
	4.4
	4.3
	4.2
	E
	f *
	4.1
	4
	3.9
								Upper MO Bound
	3.8						No coding lower MO bound NC lower bound, xor 4 packets
							NC lower bound, xor 6 packets
	3.7						NC lower bound, xor 8 packets
	2.9	3	3.1	3.2			3.3	3.4		3.5	3.6
					* f	D
	4.15
								Upper MO Bound
							NC lower bound, xor 8 packet, K=100
	4.1						NC lower bound, xor 8 packet, K=500 NC lower bound, RLNC, K=100
							NC lower bound, RLNC, K=500
	4.05
	4
	3.95
	E
	f *
	3.9
	3.85
	3.8
	3.75
	3.7
	2.9	2.95	3	3.05	3.1	3.15	3.2	3.25	3.3
					f *	D

Table 3 :

 3 The generational distance and overhead for different coding strategies

	Coding Strategies	GD	Overhead (%)
	RL code	K=50 K=100	0.1522 17.8838 0.1371 16.2841
	Only	K=500	0.1251 14.8788
	RL Code & K=500 R = 4 0.0129 1.5662
	Strategy 1	K=500 R = 6 0.0083 0.8470 K=500 R = 8 0.0071 0.7278
	RL Code & K=100	0.0197 2.1148
	Strategy 2	K=500	0.0042 0.4252

  Simulation settings . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1.1 Simulated criteria for coding strategies . . . . . . . . . . . 15 5.1.2 Generational Distance (GD) . . . . . . . . . . . . . . . . . 16 5.1.3 Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2.1 RL code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2.2 Coding Strategy 1 . . . . . . . . . . . . . . . . . . . . . . 17 5.2.3 Coding Strategy 2 . . . . . . . . . . . . . . . . . . . . . . 18

	5 Simulation Results	14
	5.1 6 Conclusion	19

Inria

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES

Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

RR n°7905

Acknowledgments

This work was supported in part by the Marie Curie IOF Action of the European Community's Sixth Framework Program (DistMO4WNet project). This article only reflects the authors' views and the European Community are liable for any use that may be made of the information contained herein.