E D Andjel

⇤⇤ L F Gray
email: gray@math.umn.edu

EXTREME PATHS IN ORIENTED 2D PERCOLATION

Keywords: Oriented percolation, extreme paths, inequalities. 2010 Mathematics Subject Classification: Primary 60K35 Secondary 60J10

 in the context of the contact process in continuous time. As discussed here, it also holds for several related models, including the discrete time contact process and two dimensional site percolation. Among the consequences are a natural monotonicity in the probability of percolation between di↵erent sites and a somewhat counter-intuitive correlation inequality.

Introduction

The main goal of this paper is to give complete proofs of a result originally presented in [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF]. The result was stated for the continuous time contact process in [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF], but its proof is missing in the literature. In that paper some interesting consequences are given which we believe justify the writing of the proof here. In the present paper we work in the context of oriented two dimensional percolation which is equivalent to a discrete time version of the contact process. In the latter part of this paper we discuss how our results apply to other models, and derive some consequences following the ideas of [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF].

Two dimensional oriented bond percolation is studied in [START_REF] Durrett | Oriented percolation in two dimensions[END_REF], where some of its most ⇤ Postal address: 39 Rue Joliot Curie,13453 Marseille, France. Email address: andjel@impa.br important properties are proved. To introduce the model, let ⇤ = {(x, y) : x, y 2 Z, y 0, x + y 2 2Z} .

Then, draw oriented edges from each point (m, n) in ⇤ to (m + 1, n + 1) and to (m 1, n + 1). In the percolation literature, the points in ⇤ and the edges between them are often called sites and bonds, respectively. In this paper we focus on oriented bond percolation, and thus we suppose that the edges are open independently of each other, and that each edge is open with probability p 2 (0, 1).

It is an easy matter to adapt the proof here to oriented site percolation, in which the points, rather than the edges, are open with probability p, independently of each other. And either by using the so-called "graphical construction" of continuous time interacting particle systems, or by taking limits of discrete time contact processes, our methods can also be applied to various versions of the continuous time contact process in one dimension. For more about such extensions, see our discussion in Section 3.

A path ⇡ in ⇤ is a sequence (x 0 , y 0 ), . . . , (x n , y n ) of points in ⇤ such that for all 0  i < n, |x i+1 x i | = 1 and y i+1 y i = 1. The edges joining (x i , y i ) to (x i+1 , y i+1 ) for 0  i  n 1 will be called the edges of ⇡. We say that a path is open if all its edges are open. (In site percolation, a path is open if all its points are open.) For any n 2 N 0 let L n = {(x, n) 2 ⇤}. Let 0  m < n and let A and B be subsets of L m and L n respectively. A path from A to B is any path starting in some point in A and finishing at some point in B. A path ⇡ from a point in L m to a point in L n will be identified with the function ⇡ : [m, n] \ Z ! Z determined by: (⇡(j), j) is a point in the path ⇡ for all m  j  n.

Given two paths ⇡ 1 and ⇡ 2 from L m to L n we say that ⇡ 1 is to the left of ⇡ 2 (or that ⇡ 2 is to the right of ⇡ 1 ) and write

⇡ 1  ⇡ 2 (or ⇡ 2 ⇡ 1 ) if ⇡ 1 (j)  ⇡ 2 (j) for
all m  j  n. This creates a partial order between paths from L m to L n . If the inequality is replaced by strict inequality, then we say that ⇡ 1 is strictly to the left of ⇡ 2 (or ⇡ 2 is strictly to the right of ⇡ 1 ).

We find it useful to extend the notions "strictly to the left" and "strictly to the right" to subsets of ⇤. Let P 1 : ⇤ ! Z be the projection on the first coordinate:

P 1 ((x, y)) = x.
And in the usual fashion, extend this function to sets ⇤ 0 ⇢ ⇤:

P (⇤ 0 ) = {P 1 ((x, y)) : (x, y) 2 ⇤ 0 }.
For G a subset of ⇤, we denote by `(G) the set of all points (j, k) 2 ⇤ such that j < inf P 1 (G \ L k ), and we denote by r(G) the set of points (j, k) 2 ⇤ such that j > sup P 1 (G \ L k ). (Here by convention, sup ; = 1 and inf ; = 1.) Thus, `(G) (r(G)) is the set of all points in ⇤ that are strictly to the left

(right) of G. If G, G 0 are subsets of ⇤, we say that G is strictly to the left of G 0 or, equivalently, G 0 is strictly to the right of G, if G ⇢ `(G 0 ), or equivalently if G 0 ⇢ r(G).
And if ⇡ is a path, then we say that ⇡ is strictly to the left of G (strictly to the right of G) if the set of points in ⇡ is strictly to the left of G (strictly to the right of G). The notation `(•) and r(•) introduced here also applies to paths, thinking of them as sets.

For example, a path ⇡ is strictly to the left of a set G if and only if G ⇢ r(⇡). Please note that this terminology and notation are consistent with our earlier definition of one path being strictly to the left of another path, but that they now also apply to paths that do not necessarily start on the same level L m or end on the same level L n .

We also extend these notions to edges: we say that an edge e is to the left (right) of a path if each of the endpoints of e is either on or strictly to the left (right) of . If in addition, at least one of these endpoints is strictly to the left (right) of , we say that e is strictly to the left (right) of . Note that this di↵ers slightly from our definitions of "strictly to the left" for paths or sets, because we do not require the whole edge to be strictly to the left of a path and one of its endpoints may belong to the path.

Let ⇤ 0 ⇢ ⇤. Note that, if A ⇢ L m and B ⇢ L n are finite and there is at least one path from A to B contained in ⇤ 0 , then there is a unique path from A to B contained in ⇤ 0 which is to the left of all paths from A to B contained in ⇤ 0 . This is called the that there is at least one open path from A to B in ⇤ 0 . In all these notations the subscript ⇤ 0 will be omitted if ⇤ 0 is the whole set ⇤, and when either A or B is a singleton, say {(x, y)}, we will often write (x, y) rather than {(x, y)}.

Let 0  m < n, let A and B be finite subsets of L m and L n respectively such that (A, B) is nonempty, and let µ and ⌫ be probability measures on (A, B). We say that µ is stochastically to the left of ⌫ and write µ  ⌫ if for any increasing function on (A, B) we have

Z (A,B) ( )dµ( )  Z (A,B) ( )d⌫( ).
We can now state our version of the main result in [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF]:

Theorem 1. Let 0  m < n, let A and B be finite subsets of L m and L n respectively and let ⇤ 0 and G be subsets of ⇤.

If ⇤ 0 \`(G) (A, B) is nonempty, we have µ ⇤ 0 \`(G) (A, B)  µ ⇤ 0 (A, B) and ⌫ ⇤ 0 \`(G) (A, B)  ⌫ ⇤ 0 (A, B). And if ⇤ 0 \r(G) (A, B) is nonempty, we have µ ⇤ 0 \r(G) (A, B) µ ⇤ 0 (A, B) and ⌫ ⇤ 0 \r(G) (A, B) ⌫ ⇤ 0 (A, B).
This result has the following immediate corollary:

Corollary 1. Let m < n, let ⇤ 0 be a subset of ⇤, let A and B be finite subsets of L m and L n respectively such that ⇤ 0 (A, B) is nonempty and suppose A 0 is a finite subset of L m that is strictly to the right of A. Then, µ ⇤ 0 (A [ A 0 , B) µ ⇤ 0 (A, B) and

⌫ ⇤ 0 (A [ A 0 , B) ⌫ ⇤ 0 (A, B). Moreover, if B 0 is a finite subset of L n that is strictly to the right of B, then µ ⇤ 0 (A, B [ B 0 ) µ ⇤ 0 (A, B) and ⌫ ⇤ 0 (A, B [ B 0 ) ⌫ ⇤ 0 (A, B). If,
instead A 0 is strictly to the left of A ( B 0 is strictly to the left of B ) then the first two (last two) inequalities are reversed.

The di↵erent parts of the corollary follow from the theorem by making appropriate choices of the sets A, B, G. For example, for the first part of the corollary, replace A in the theorem by A [ A 0 and let G = A 0 . As an immediate consequence of this corollary we get:

Corollary 2. Assume that m, n, ⇤ 0 , A and B are as in Corollary 1. If A 0 is a subset of L m strictly to the right of A and ⇤ 0 (A 0 , B) is nonempty, then µ ⇤ 0 (A 0 , B) µ ⇤ 0 (A, B)
and

⌫ ⇤ 0 (A 0 , B) ⌫ ⇤ 0 (A, B). Similarly, if B 0 is a finite subset of L n strictly to the right of B and ⇤ 0 (A, B 0 ) is nonempty, then µ ⇤ 0 (A, B 0 ) µ ⇤ 0 (A, B) and ⌫ ⇤ 0 (A, B 0 ) ⌫ ⇤ 0 (A, B) .
Each of the four inequalities of this corollary is obtained applying twice Corollary 1. For example to obtain the first of these inequalities write:

µ ⇤ 0 (A 0 , B) µ ⇤ 0 (A [ A 0 , B) µ ⇤ 0 (A, B).
In Section 2, we give a proof of our main theorem, based on a Markov chain that was introduced in [START_REF] Van Den Berg | Proof of a conjecture of N. Konno for 1D contact process[END_REF]. In that paper, the Markov Chain was used to prove that the one dimensional nearest neighbor contact process satisfies the following property: Starting from a deterministic configuration ⌘ 0 and conditioning on the event

⌘ t (0) = 1, the collection of random variables {1 ⌘ t (x) : x < 0} [ {⌘ t (x) :
x > 0} is positively associated. Finally, in the last two sections, we discuss extensions to other models and derive some consequences and applications of the theorem and its corollaries following the ideas of [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF].

Proof of Theorem 1

In this section we give a proof of Theorem 1, based on a Markov Chain introduced in [START_REF] Van Den Berg | Proof of a conjecture of N. Konno for 1D contact process[END_REF]. Without loss of generality, we assume that m = 0 and we let A and B be finite subsets of L 0 and L n respectively, such that ⇤ 0 (A, B) 6 = ;. Then, we let E be a finite set of oriented edges in ⇤ 0 containing at least one path from A to B and we let S = {0, 1} E . Each element ⌘ of S determines the state of the edges in E in the natural way:

e 2 E is open (closed) for ⌘ if ⌘(e) = 1 (⌘(e) = 0
). Now, we only consider paths whose edges are in E and we let T be the subset of S consisting of the elements for which there is an open path from A to B. For ⌘ 2 T , we let `(⌘) ( r (⌘)) be the leftmost (rightmost) open path from A to B under configuration ⌘. We let (S) be the -algebra of all subsets of S and we let P p be the product probability measure on (S) whose marginals are Bernoulli with parameter p. On the probability space (S, (S), P p ), we define for each e 2 E a random variable X e by means of X e (⌘) = ⌘(e).

Given a path from A to B whose edges are in E, we let r ( ) be the -algebra generated by {X e : e is to the right of } and we let 0 r ( ) be the -algebra generated by {X e : e is strictly to the right of } . Similarly we let `( ) be the -algebra generated by {X e : e is to the left of } and we let 0 `( ) be the -algebra generated by {X e : e is strictly to the left of }. We now note that the event { `= } is `( )measurable. Since the -algebras `( ) and 0 r ( ) are independent, this implies that Proof. We show that if the initial state of the chain ⌘ 0 is chosen according to the distribution P p (•|T ), then ⌘ 1/2 has the same distribution. A similar argument will then show that ⌘ 1 has the same distribution as ⌘ 1/2 . Let be an arbitrary path in

E (A, B) and let S = {⌘ 2 T : `(⌘) = }.
Then (S :

2 E (A, B)) is a partition of T and P p (•|T ) is a convex combination of the measures (P p (•|S )) 2 E (A,B)
. Therefore, it su ces to show that if ⌘ 0 is distributed according to some P p (•|S ) then ⌘ 1/2 is also distributed according to that measure.

But this is an immediate consequence of the way we obtain ⌘ Proof of Theorem 1. We only prove the first inequality, since the other proofs are similar. Let E be the set of edges belonging to paths in ⇤ 0 (A, B) and let E `(G) be the set of edges belonging to paths in ⇤ 0 \`(G) (A, B). We let T 1 be the subset of elements of {0, 1} E for which there exists an open path from A to B and we let T 2 be the subset of elements of {0, 1} E `(G) for which there exists an open path from A to B. We now construct a Markov Chain in

X = {(⌘, ⇠) 2 T 1 ⇥ T 2 : `(⌘) `(⇠), r (⌘) r (⇠)}
whose first and second marginals are as the Markov Chains associated to E and to E `(G) respectively. This is done as follows: Assume (⌘ 0 , ⇠ 0 ) 2 X, then let {Y e :

e strictly to the right of `(⇠)} be a collection of i.i.d Bernoulli random variables of parameter p. First note that by definition of X, `(⌘) `(⇠), then define ⌘ 1/2 and ⇠ 1/2 as follows:

⌘ 1/2 (e) = ⌘ 0 (e) for all e to the left of `(⌘ 0 ), ⌘ 1/2 (e) = Y e for all e strictly to the right of `(⌘ 0 ), ⇠ 1/2 (e) = ⇠ 0 (e) for all e to the left of `(⇠ 0 ), ⇠ 1/2 (e) = Y e for all e strictly to the right of `(⇠ 0 ).

After that note that (⌘ 1/2 , ⇠ 1/2 ) 2 X and let {Z e : e strictly to the left of r (⌘)} be collection of i.i.d Bernoulli random variables of parameter p which is independent of the random variables Y e . Finally, define ⌘ 1 and ⇠ 1 as follows:

⌘ 1 (e) = ⌘ 1/2 (e)
for all e to the right of r (⌘ 1/2 ), ⌘ 1 (e) = Z e for all e strictly to the left of r (⌘ 1/2 ), ⇠ 1 (e) = ⇠ 1/2 (e) for all e to the right of r (⇠ 1/2 ), ⇠ 1 (e) = Z e for all e strictly to the left of r (⇠ 1/2 ).

We can now complete our proof: let be an increasing function on E (A, B) and let (⌘ 0 , ⇠ 0 ) be an element of X. Then (⌘ n , ⇠ n ) 2 X a.s. 8n. Therefore,

( `(⌘ n )) ( `(⇠ n ))a.s. 8n.
Hence,

E( ( `(⌘ n ))) E( ( `(⇠ n ))) 8n.
Now, taking limits as n goes to infinity and applying Corollary 3 to both sides of the inequality we get µ ⇤ 0 (A, B) µ ⇤ 0 \`(G) (A, B).

Generalizations and extensions of Theorem 1

We first discuss generalizations of the oriented bond percolation model that do not require any change in our proof of the main results, then we consider oriented site percolation and the contact process and after that we mention an extension of these results which require a quite di↵erent proof.

It is easy to check that we never made any use of the assumption that all of the bonds have the same probability of being open. In fact, we could assign a di↵erent probability to each bond, and the proofs will continue to work without any changes.

It may seem that this is an uninteresting generalization, but we will see that it turns out to be relevant when we use percolation models to approximate the continuous time contact process.

We now turn to oriented site percolation. Let ⇤ = {(x, y) : x, y 2 Z, y 0} . The case where a = 0 and b = 1 is equivalent to the standard oriented site percolation in Z 2 , where there are two bonds per site. Not surprisingly, our proofs of the main result can be modified in a routine way to cover this case.

Once the case a = 0, b = 1 is handled, it is quite routine to further modify the proof to cover arbitrary a  0 < b, which is to say that our main result holds for finite range oriented site percolation in 2 dimensions. This highlights a significant di↵erence between oriented bond percolation and oriented site percolation. In oriented bond percolation, the leftmost and rightmost paths may not even exist when there is the possibility that bonds cross one another, as will be the case when b a > 1. But in oriented site percolation, leftmost and rightmost paths always exist, for any choice of a, b.

Finally, we briefly discuss the contact process. By treating the y-coordinate in ⇤ as the time variable, one can obtain various versions of the discrete time contact process from oriented percolation. The standard model is equivalent to oriented site percolation. Variations on this model can be obtained from oriented bond percolation, and also by looking at mixed models in which both the sites and the bonds can be open or closed. Not surprisingly, our main results applies to many mixed percolation models, and hence to many di↵erent discrete time contact processes.

One way to extend our results to the continuous time contact process is to approximate continuous time with discrete time. This method works easiest for the one-sided nearest neighbor contact process. Then we could use the oriented bond percolation model that is the setting for most of this paper, but it is perhaps more natural to do oriented bond percolation on an equivalent graph: the set of sites is ⇤ and the oriented bonds are those that correspond to a = 0 and b = 1. That is, two oriented bonds emerge from each site (x, y), a "vertical" bond connecting it to the site (x, y + 1) and a "contact" bond connecting it to (x + 1, y + 1).

With this setup, we can approximate the continuous time one-sided contact process by letting the contact bonds be open with small probability h > 0 and letting the vertical bonds be open with probability 1 "h, where " 0 is a parameter of the model. Then letting h # 0 and rescaling time by a factor of h produces the continuoustime model. This shows why it can be desirable to allow the bonds to have di↵erent

probabilities of being open.

One can use a similar approximation method for the two-sided nearest neighbor contact process. In this case, we use the graph ⇤ that is the setting for the bulk of this paper, but we add additional oriented "vertical bonds" that connect each site (x, y) 2 ⇤ to the site (x, y + 2). Then by assigning appropriate probabilities to the bonds (di↵erent for the vertical bonds than for the diagonal bonds), one obtains a percolation model that depends on a parameter h, and this model converges to the two-sided nearest neighbor contact process as h ! 0. See [START_REF] Andjel | An inequality for oriented 2-D percolation[END_REF] for further details. The bottom line is that the results in this paper all apply to one the one-sided and two-sided contact processes in continuous time.

Finally, the assumption of independence between bonds may be weakened. Keeping the independence for bonds emerging from di↵erent sites but allowing the two bonds emerging from the same site to be dependent, our main results still hold. But when the bonds emerging from the same site are negatively correlated, Theorem 1 requires a completely di↵erent proof. This proof uses a rather intricate inductive argument, that was hinted at in [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF], rather than the Markov Chain of Section 2. For details of this proof we refer the reader to [START_REF] Andjel | Extreme paths in oriented 2D percolation[END_REF].

Applications of Theorem 1

One reason for our interest in extreme paths is that they provide us with a useful way to analyze various conditional probabilities, and with the help of Theorem 1, we are able to make comparisons that go beyond the usual correlation inequalities that are familiar in percolation theory. The results in this section apply to the more general models discussed in the previous section, except that Corollaries 5, 6, 7 and 8 require translation invariance, so that all of the bond (or site) probabilities must be the same.

In this section we adopt the following notations: Given 0  m  n, a fixed subset ⇤ 0 of ⇤ and finite subsets A and B of L m and L n respectively, we let H = {there exists an opent path from A to B in ⇤ 0 }.

Then, if F is another event such that P (F \H) > 0, we let µ F ⇤ 0 (A, B) be the distribution of the leftmost open path from A to B in ⇤ 0 given the event F \ H. The same notation will apply to the distributions of rightmost paths where ⌫ will substitute for µ.

We will rely on a key fact about extreme paths. It is that if is a path, the event that is a rightmost (leftmost) open path is measurable with respect to the states of the bonds that are to the right (left) of and hence this event is independent of the states of the bonds that are strictly to the left (right) of .

The following result and its proof show how we use this fact in conjunction with Theorem 1 to compare several di↵erent conditional probabilities. Lemma 1. Let n > 0, let A be a finite subset of L 0 and let B 1 , B 2 , B 3 be finite subsets and we have

E('( ) | H 2 ) = P (H 1 | H 2 ) and E('( ) | H 2 \ H c 3 ) = P (H 1 | H 2 \ H c 3 ) .
Assume 1 and 2 are possible values of such that 1  2 . Then, for i = 1, 2 we have

P (H 1 |H 2 \ { = i }) = P (A [ i ! B 1 ),
where

{A [ i ! B 1 } is the event occurring i↵ there is an open path from A [ i to B 1 . Since {A [ 2 ! B 1 } ⇢ {A [ 1 ! B 1 },
the function '( ) is decreasing with respect to the partial ordering on paths, so the first inequality in (1) now follows from (3). The second inequality in (1) follows immediately from the first inequality and the fact that the middle expression in ( 3) is a convex combination of the first and third expressions.

To prove (2), we first use Corollary 2 to get:

⌫(A, B 2 )  ⌫(A, B 3 ) .
Now (2) follows, in the same way that (1) followed from (3).

To prove the last part of the lemma, we note that by Corollary 2,

⌫((x, 0), B 2 )  ⌫((x + 2, 0), B 2 )
for all x such that there exist paths from (x, 0) and (x + 2, 0) to B 2 . The last part of the lemma is now proved in the same way that (1) and ( 2) were proved.

The first inequality in (1) may seem counterintuitive. We know that the occurence of a "negative" event like H c 3 makes a "positive" event like H 1 less likely to occur. But the first inequality says informally that once H 2 occurs, the additional occurrence of the negative event H c 3 makes H 1 more likely to occur. Here is another way to state this result: Corollary 4. Let H 1 , H 2 , H 3 be as in Lemma 1. Then given H 2 , the events H 1 and H 3 are conditionally negatively correlated.

Proof. The proof is elementary, using the second inequality in Lemma 1:

P (H 1 \ H 3 | H 2 ) = P (H 1 \ H 2 \ H 3 ) P (H 2 ) = P (H 1 \ H 2 \ H 3 ) P (H 2 \ H 3 ) P (H 3 | H 2 ) = P (H 1 | H 2 \ H 3 )P (H 3 | H 2 )  P (H 1 | H 2 )P (H 3 | H 2 ) .
Here is another application of Lemma 1. It is a rather natural monotonicity involving certain percolation probabilities. It is somewhat surprising that its proof seems to require the consequences of something as sophisticated as Theorem 1. We note that this result clearly depends on some translation invariance, so it requires all of the bond probabilities (or site probabilities in the case of oriented site percolation) to be the same. A di↵erent proof of this result is given in [START_REF] Andjel | An inequality for oriented 2-D percolation[END_REF], but we believe the one given here is more natural and easier to follow.

Corollary 5. Let 0  m < n and let x, y be integers such that (x, m) 2 L m and (y, n) 2 L n . Let A x,y be the event that there is an open path from (x, m) to (y, n).

Then P (A x,y ) is nonincreasing in |x y|.

Proof. Because of the natural symmetries built into the percolation model, we may assume without loss of generality that m = 0, x = 0 and y 0. The obvious inductive argument reduces the proof to showing that

P (A 0,y ) P (A 0,y+2 ) , (4)
where we may assume that y is such that there exists at least one path from (0, 0) to (n, y + 2). Since y 0, this assumption implies that there also exists at least one path from (0, 0) to (n, y).

Under these circumstances, to prove (4), it is enough to prove that

P (A 0,y | A 0,y+2 ) P (A 0,y+2 | A 0,y ) (5)
since the numerators in the expressions for the two conditional probabilities in (5) are the same and since the denominators in these expressions are the two sides of (4) (in reverse order).

To prove [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF], we first use left-right symmetry and then translation invariance to get

P (A 0,y+2 | A 0,y ) = P (A 0, y 2 | A 0, y ) = P (A 2y+2, y | A 2y+2, y+2 ) .
Since we assumed that y 0, the last part of Lemma 1 gives us

P (A 2y+2, y | A 2y+2, y+2 )  P (A 0,y | A 0,y+2 )
proving [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF], and thus (4). Note that our assumptions about y ensure that all of the relevant events in these applications of Lemma 1 have positive probability, as required by the hypotheses of that lemma.

For our last results we adopt the following notation: For (k, n) 2 ⇤ we let X(k, n)

be the indicator function of the event {(0, 0) ! (k, n)}, and if is a path in ⇤ we let X (k, n) be the indicator function of the event { ! (k, n)}.

Corollary 6. Let y 2 Z and n 2 N be such that (y, n) 2 ⇤ and n  y  n 2. Then for any k 2 N and any increasing function

f : {0, 1} k ! R, we have E ⇣ f (X(y + 2, n), . . . , X(y + 2k, n))|X(y, n) = 1 ⌘ E ⇣ f (X(y + 4, n), . . . , X(y + 2k + 2, n))|X(y + 2, n) = 1 ⌘ .
Proof. On the event {X(y, n) = 1} we let be the leftmost open path from (0, 0) to (y, n). Then,

E ⇣ f (X(y + 2, n), . . . , X(y + 2k, n))|X(y, n) = 1 ⌘ = R E ⇣ f (X(y + 2, n), . . . , X(y + 2k, n))| = ⌘ dµ((0, 0), (y, n))( ) = R E ⇣ f (X (y + 2, n), . . . , X (y + 2k, n)) ⌘ dµ((0, 0), (y, n))( ), (6)
where for the second equality we used the fact that conditioning on the event { = } does not change the distribution of the state of the bonds strictly to the right of .

Similarly,

E ⇣ f (X(y + 4, n), . . . , X(y + 2k + 2, n))|X(y + 2, n) = 1 ⌘ = R E ⇣ f (X(y + 4, n), . . . , X(y + 2k + 2, n))| = ⌘ dµ((0, 0), (y + 2, n))( ) = R E ⇣ f (X (y + 4, n), . . . , X (y + 2k + 2, n)) ⌘ dµ((0, 0), (y + 2, n))( ) = R E ⇣ f (X (y + 2, n), . . . , X (y + 2k, n)) ⌘ dµ(( 2, 0), (y, n))( ), (7)
where the last equality follows from translation invariance. But by the first inequality of Corollary 2, µ(( 2, 0), (y, n))  µ((0, 0), (y, n)), and the corollary follows from the fact that

F ( ) = E ⇣ f (X (y + 2, n), . . . , X (y + 2k, n))
⌘ is an increasing function on the set ({( 2, 0), (0, 0)}, {(y, n)}).

Corollary 7. Let x 2 N 0 and n 2 N be such that (x, n) 2 ⇤ and let a 1 , . . . , a k be an increasing sequence of elements of 2N 0 . Then,

P (X(x + a 1 , n) = 1, . . . , X(x + a k , n) = 1) P (X(x + a 1 + 2, n) = 1, . . . , X(x + a k + 2, n) = 1). Proof. Write P (X(x + a 1 , n) = 1, . . . , X(x + a k , n) = 1) = P (X(x + a 2 , n) = 1, . . . , X(x + a k , n) = 1|X(x + a 1 , n) = 1) P (X(x + a 1 , n) = 1) (8)
and

P (X(x + a 1 + 2, n) = 1, . . . , X(x + a k + 2, n) = 1) = P (X(x + a 2 + 2, n) = 1, . . . , X(x + a k + 2, n) = 1|X(x + a 1 + 2, n) = 1) P (X(x + a 1 + 2, n) = 1). (9)
Now we only need to show that the right hand side of (8) is greater than or equal to the right hand side of (9), but this follows immediately from Corollaries 5 and 6 .

Remark: Of course, unlike Corollary 6, this last result is false if we do not assume that x 0. It falls short of proving that under the same hypothesis the random vector (X(x + a 1 , n), . . . , X(x + a k , n)) is stochastically above (X(x + a 1 + 2, n), . . . , X(x + a k + 2, n)) but we conjecture that this is also true.

Our last application generalizes Corollary 5.

Corollary 8. Let 0  m < n, let k 2 N and let x, y be integers such that (x, m) 2 L m and (y, n) 2 L n . Let A x,y,k be the event that there is an open path from (x, m) to {(y 2k, n), . . . , (y + 2k, n)}. Then P (A x,y,k ) is nonincreasing in |x y|.

Proof. As in the proof of Corollary 5, we may assume without loss of generality that m = 0, x = 0 and y 0 and an obvious inductive argument reduces the proof to showing that P (A 0,y,k ) P (A 0,y+2,k ).

(

) 10
This inequality is trivial if there are no paths from (0, 0) to (y + 2k + 2, n). Hence, we may assume that

|y + 2k + 2|  n. (11)
Now, (10) will follow from P (A 0,y,k \ A c 0,y+2,k ) P (A c 0,y,k \ A 0,y+2,k ).

(

) 12
This last inequality is equivalent to: P (X(y 2k, n) = 1, X(y 2k + 2, n) = 0, . . . , X(y + 2k + 2, n) = 0) P (X(y + 2 + 2k, n) = 1, X(y + 2k, n) = 0, . . . , X(y 2k, n) = 0).

The left and right hand sides of this inequality can be written respectively as P (X(y 2k + 2, n) = 0, . . . , X(y + 2k + 2, n) = 0|X(y 2k, n) = 1) P (X(y 2k, n) = 1) ( Remark: We did not find a way to complete the proof of Theorem 5 in [START_REF] Gray | Is the contact process dead? Lectures in Appli[END_REF] which

remains as an open problem.

  leftmost path from A to B in ⇤ 0 . And, if there is an open path from A to B contained in ⇤ 0 , then there is a unique open path from A to B contained in ⇤ 0 which is to the left of all open paths from A to B contained in ⇤ 0 . This path will be called the leftmost open path from A to B in ⇤ 0 . Similarly, we define the rightmost path and rightmost open path from A to B in ⇤ 0 . Given a subset ⇤ 0 of ⇤, 0  m < n 2 N and two finite subsets A and B of L m and L n respectively, ⇤ 0 (A, B) will denote the set of paths from A to B contained in ⇤ 0 . If this set is non-empty, then µ ⇤ 0 (A, B) (⌫ ⇤ 0 (A, B)) will denote the conditional distribution of the leftmost (rightmost) open path from A to B contained in ⇤ 0 given

  under the conditional measure P p (•| `= ) the distribution of the state of the bonds which are strictly to the right of remains a Bernoulli product measure of parameter p. Similarly, under the conditional measure P p (•| r = ) the distribution of the state of the bonds which are strictly to the left of remains a Bernoulli product measure of parameter p. We now define a Markov Chain on T. Its transition mechanism is given in two steps. For a given initial state ⌘ 0 2 T , first we choose ⌘ 1/2 2 T by letting ⌘ 1/2 (e) = ⌘ 0 (e) for all e to the left of `(⌘ 0 ) (this includes the edges on `(⌘ 0 )) and for the other elements of E we let ⌘ 1/2 (e) be independent Bernoulli random variables with parameter p. Once we have determined ⌘ 1/2 we let ⌘ 1 (e) = ⌘ 1/2 (e) for all e to the right of r (⌘ 1/2 ) ( this includes the edges on r (⌘ 1/2 )) and for the other elements of E we let ⌘ 1 (e) be independent Bernoulli random variables with parameter p which are also independent of the random variables used to determine ⌘ 1/2 . In the sequel we will need to consider this Markov Chain for di↵erent sets E. We will call it the Markov Chain associated to E. Besides this, we extend the notation of the previous sections by letting E (A, B) be the set of paths from A to B whose edges are in E. Proposition 1. (van den Berg, Häggström, Kahn) The measure P p (•|T ) is invariant for the Markov chain.

Corollary 3 .

 3 1/2 from ⌘ 0 and the already observed fact that the under the conditional measure P p (•| `= ) the distribution of the state of the bonds which are strictly to the right of remains a Bernoulli product measure of parameter p.. Since the Markov Chain associated to E is obviously irreducible and aperiodic we deduce from this proposition the following: From any initial distribution, the Markov Chain associated to E converges to P p (•|T ).

Fix integers a  0

 0 < b, and for each (x, y) 2 ⇤, introduce oriented bonds from (x, y) to (x+k, y +1) for a  k  b. All of the bonds are open. The sites are open independently of each other, with probability p 2 (0, 1) (we could also allow di↵erent probabilities for di↵erent sites). Paths are defined in the obvious way, and open paths are paths in which all of the sites are open.

andP

  (X(y + 2k, n) = 0, . . . , X(y 2k, n) = 0|X(y + 2 + 2k, n) = 1) P (X(y + 2 + 2k, n) = 1).(15)Hence, the corollary will follow from:P (X(y 2k, n) = 1) P (X(y + 2 + 2k, n) = 1)(16)andP (X(y 2k + 2, n) = 0, . . . , X(y + 2k + 2, n) = 0|X(y 2k, n) = 1) P (X(y + 2k, n) = 0, . . . , X(y 2k, n) = 0|X(y + 2 + 2k, n) = 1). (17)Now, (16) follows from Corollary 5 and our assumption on y, hence it remains to prove (17). To do so, first note that by symmetry the right hand side of (17) is equal toP (X( y 2k, n) = 0, . . . , X( y + 2k, n) = 0|X( y 2 2k, n) = 1). (18)Proceeding as in proof of Corollary 7 and recalling (11) we see that this is equal toZ P ⇣ X ( y 2k, n) = 0, . . . , X ( y + 2k, n) = 0 ⌘ dµ((0, 0), ( y 2 2k, n))( ),which by translation invariance is equal toZ P ⇣ X (y 2k + 2, n) = 0, . . . , X (y + 2k + 2, n) = 0 ⌘ dµ((2y + 2, 0), (y 2k, n))( ).Since the left hand side of (17) is equal toZ P ⇣ X (y 2k + 2, n) = 0, . . . , X (y + 2k + 2, n) = 0 ⌘ dµ((0, 0), (y 2k, n))( ),the result follows from Corollary 2, our assumption on y and the fact that P ⇣ X (y 2k + 2, n) = 0, . . . , X (y + 2k + 2, n) = 0 ⌘ is a decreasing function of on the set ({(0, 0), (2y + 2, 0)}, {(y 2k, n)}).

Acknowledgments: We thank the referee's careful reading and helpful comments. This paper was written while the first author was visiting IMPA and was supported first by Capes and then by Cnpq.

of L n . Suppose that B 1 is strictly to the left of B 2 and that B 2 is strictly to the left of B 3 . For i = 1, 2, 3, define the events H i = {there exists an open path from A to B i }.

If the events H 2 and H 3 have nonzero probability, then

and

Furthermore, if A consists of a single site (x, 0), then

x for all x such that the event H 2 has positive probability.

Proof. We begin by proving the following inequality:

The event H c 3 is the disjoint union of events of the form { = '}, where is the random set of all edges that are contained in open paths that end in B 3 . The left side of (3) is a convex combination of the measures ⌫ { ='} (A, B 2 ), and for each ',

, where G is the set that contains the endpoints of the edges in '. The inequality in (3) now follows from Theorem 1.

We now use (3) to prove the first inequality in [START_REF] Andjel | Extreme paths in oriented 2D percolation[END_REF]. Let be the rightmost open path from A to B 2 , assuming that such a path exists, which is the same as assuming that H 2 occurs. The left side of (3) is the conditional distribution of given H 2 \ H c This statement about the edges left of also holds true given the event H 2 \ H c 3 \ { = } because of the assumption that B 3 is strictly to the right of B 2 . In either case, whether or not there is an open path from A [ to B 1 is determined in the same way by the openness of the edges that are strictly to the left of . Thus, there is a function ' on the set of all paths from A to B 2 such that


Ait Fayçal

Matthieu Aoudia
email: matthieu.gautier@irisa.fr

Olivier Gautier
email: olivier.berder@irisa.fr

Berder

Fuzzy Power Management for Energy Harvesting Wireless Sensor Nodes

Power management is an important issue in the design of Energy Harvesting Wireless Sensor Networks (EH-WSNs). In this kind of networks, each Energy Harvesting Node (EH-node) must dynamically adapt its performance in order to avoid power failures while maintaining a good quality of service. The power management policy is implemented on each node by a Power Manager (PM). Designing a PM is challenging because the harvested energy is time varying, and the amount of energy that will be harvested in the future is hard to predict. In this work, we present Fuzzyman, a novel PM based on fuzzy control theory. Because of the unpredictability of the harvested energy, fuzzy control theory constitutes an appropriate framework to tackle the problem of designing PM for EH-nodes. We evaluate the performance of Fuzzyman by comparing it to a state of the art approach via extensive trace-driven network simulations. Results show that Fuzzyman achieves more efficient utilization of the harvested energy.

I. INTRODUCTION

Sensors that constitute typical Wireless Sensor Networks (WSNs) are powered by individual batteries of limited capacity, and maximizing the lifetime of such systems is a perennial issue. Indeed, when the stored energy is exhausted, refilling the energy could be expensive or impossible if the network is dense or if the nodes are deployed in harsh environments. A more viable solution is to equip each node with at least one energy harvester, and to allow the sensors to be entirely powered by the energy harvested in their environments [START_REF] Kansal | Power Management in Energy Harvesting Sensor Networks[END_REF]- [START_REF] Le | Power Manager with PID Controller in Energy Harvesting Wireless Sensor Networks[END_REF]. If the nodes perpetually operate in an Energy Neutral state [START_REF] Kansal | Power Management in Energy Harvesting Sensor Networks[END_REF], i.e. the amount of energy consumed never exceeds the amount of energy harvested over a long period of time, it is possible to significantly extend the lifetime of the network if the harvested energy is persistent.

If energy harvesting technologies enable the exploitation of renewable energy sources, a big challenge is the time-varying behavior of the harvested energy. Drained periods during which almost no energy is available can occur, for example during nighttime if solar energy is harvested. Therefore, in order to maintain a good quality of service during long periods, dynamic performance adaptation must be done using power management policies, implemented on each node by a PM. Many power management schemes were proposed in the last years, and they can be classified based on their requirement of predicted information about the amount of energy that can be harvested in the future, i.e. prediction-based and model-free.

As the name implies, prediction-based schemes require that an energy predictor [START_REF] Piorno | Prediction and Management in Energy Harvested Wireless Sensor Nodes[END_REF] supplies the PM with predictions of the energy that can be harvested in the future. The first PM using the prediction-based approach was introduced in 2007 by Kansal et al. [START_REF] Kansal | Power Management in Energy Harvesting Sensor Networks[END_REF]. In their approach, the energy source is assumed to be pseudo-periodic, and an exponentially weighted moving average filter is used to predict the future amount of harvested energy. Then, the duty-cycle is computed by taking into account the difference between predicted and observed energy inputs. Castagnetti et al. introduced the Closed-Loop PM (CL-PM) in [START_REF] Castagnetti | A framework for modeling and simulating energy harvesting WSN nodes with efficient power management policies[END_REF], which uses two distinct energy management strategies, one for periods during which environmental energy is available, and one for periods during which the harvested energy is below a fixed threshold, referred to as Zero Energy Interval (ZEI). The durations of ZEI are learned, in order to allow CL-PM to adjust the duty-cycle so that the node will not run into a power failure before the end of the non-harvesting interval. Le et al. proposed Wake up Variation Reduction PM (WVR-PM) in [START_REF] Le | Energy-Efficient Power Manager and MAC Protocol for Multi-Hop Wireless Sensor Networks Powered by Periodic Energy Harvesting Sources[END_REF], a variation of CL-PM. The authors proposed an improvement that allows the node to store more energy when environmental energy is available for ZEI periods, in order to achieve similar quality of service during ZEI periods as when environmental energy is available. Moreover, WVR-PM does not require an additional sensor in order to approximate the harvested energy.

The amount of energy that a sensor can harvest shows large fluctuations and is hard to predict. As a consequence, energy predictors suffer from significant errors, which incur overuse or underuse of the harvested energy. Therefore, modelfree schemes were proposed. These schemes do not require any prediction or model of the energy source in their power management strategies. The first model-free scheme was LQ-Tracker, introduced by Vigorito et al. in [START_REF] Vigorito | Adaptive Control of Duty Cycling in Energy-Harvesting Wireless Sensor Networks[END_REF]. LQ-Tracker uses Linear-Quadratic Tracking, a technique from adaptive control theory, in order to adapt the duty-cycle considering only the state of charge of the energy storage device. Similarly, Le et al. proposed to use a Proportional Integral Derivative (PID) controller in [START_REF] Le | Power Manager with PID Controller in Energy Harvesting Wireless Sensor Networks[END_REF]. With P-FREEN [START_REF] Peng | Prediction free energy neutral power management for energy harvesting wireless sensor nodes[END_REF], Peng et al. proposed a PM that maximizes the duty-cycle of a sensor node in the presence of battery storage inefficiencies. The authors formulated the average duty-cycle maximization problem as a non-linear programming problem. As solving this kind of problem directly is computationally intense, they proposed a set of budget assigning principles that maximizes the dutycycle by only using the current observed energy harvesting rate and the residual energy.

Fuzzy control theory aims to extend the existing conventional control system techniques and methods for a class of ill-modeled systems, i.e. fuzzy systems [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems[END_REF]. Because of the unstable and hard to predict behavior of the harvested energy, EH-nodes are usually hard to model systems. Therefore, fuzzy control theory constitutes an appropriate framework to design PM for EH-nodes. Accordingly, we propose in this work Fuzzyman, a PM for EH-nodes that relies on fuzzy control theory. Our contributions to the research on EH-WSNs are the following:

' Designing Fuzzyman, a PM for EH-nodes that is based on fuzzy control theory. To the best of our knowledge, this is the first work that uses this approach to tackle the problem of designing PM for EH-nodes. ' Tuning Fuzzyman in the case of EH-nodes powered by indoor ambient light using exhaustive trace-driven network simulations. ' Implementing and evaluating Fuzzyman and P-FREEN [START_REF] Peng | Prediction free energy neutral power management for energy harvesting wireless sensor nodes[END_REF], a state of the art model-free PM that outperforms the reference scheme proposed by Kansal et al. [START_REF] Kansal | Power Management in Energy Harvesting Sensor Networks[END_REF], in the context of indoor ambient light energy harvesting using exhaustive trace-driven network simulations.

The rest of the paper is organized as follows. Section II presents Fuzzyman design. In Section III, the parameterization of Fuzzyman is discussed. The simulations results are presented in Section IV, and the paper concludes in Section V.

II. DESIGNING FUZZYMAN

A. System Model and Notations

Two methods currently exist to handle the harvested energy: harvest-store-use [START_REF] Sudevalayam | Energy Harvesting Sensor Nodes: Survey and Implications[END_REF] and harvest-use (store) [START_REF] Peng | Throughput optimal energy neutral management for energy harvesting wireless sensor networks[END_REF]. The first one consists of storing all the harvested energy and powering the node from the energy storage device only. However, due to energy storage inefficiencies, only a fraction of the harvested energy can be stored into energy storage devices, and this method therefore incurs important energy waste. This led to the proposal of the harvest-use (store) mechanism. The basic idea is to power the node directly from the harvested energy, and to store only the surplus of harvested energy. The node will draw energy from the energy storage device if the harvested energy is not sufficient. In this paper, we adopt the harvest-use (store) mechanism.

The time is divided into equal length time slots of duration T . The energy storage device is assumed to have a finite capacity denoted E max S . The hardware failing threshold is denoted E f ail S , i.e. if the residual energy falls below this threshold, a power failure arises. The leakage power and the power conversion efficiency are assumed to be constant and are denoted P L and η P p0, 1s respectively. The amount of energy required to ensure the desired minimum quality of service for one time slot is denoted E min B . When the node is in energetic distress i.e. in a high risk to run into a power failure, it goes into energetic distress state and the amount of energy required to ensure minimal operation for one time slot in this state is denoted

E eds B such that E eds B ă E min B .

B. Fuzzyman global architecture

The task of Fuzzyman is to compute the energy budget e B rks that the node should use during the slot k regarding the residual energy at the end of the previous time slot e S rk ´1s and the energy harvested during the previous time slot e H rk ´1s. Therefore, Fuzzyman is executed at the end of every time slot. As a fuzzy logic controller [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems[END_REF], Fuzzyman is made of three units: the fuzzification unit, the inference engine, and the defuzzification unit as shown by Fig. 1. The fuzzification module is the input terminal. Its job is to transform the physical inputs into fuzzy sets compatible with the inference engine. A fuzzy set consists of an interval for the range of the input value and an associate normalized membership function describing the degree of the confidence of the input belonging to this range. The inference engine is the core of the controller. It is responsible for creating the control actions in fuzzy terms. Finally, the defuzzification unit maps the controller outputs to a physical value that can be accepted by the node. In the rest of this section, these three modules are described in detail.

C. Fuzzification of the Controller Inputs

The first module of Fuzzyman is the fuzzification unit, which converts each input physical value, i.e. e S rk ´1s and e H rk ´1s, into fuzzy sets.

Harvested Energy Fuzzification: To describe the harvested energy physical value e H ě 0, two fuzzy sets named "WEAK" and "STRONG" are considered. They are associated to the fol-lowing normalized membership functions, shown by Fig. 2a:

µ weak pxq " $ ' ' & ' ' % 1, if x ď E weak H ´x`E strong H E strong H ´Eweak H , if E weak H ă x ă E strong H 0, if x ě E strong H (1) µstrongpxq " $ ' ' & ' ' % 0, if x ď E weak H x´E weak H E strong H ´Eweak H , if E weak H ă x ă E strong H 1, if x ě E strong H (2)
where E weak H is equal to the amount of energy required to ensure the minimum quality of service for one time slot, when the power conversion efficiency and the leakage are taken into account, i.e.:

E weak H " E min B η `PL T. (3)
Thus, if the source is fully "WEAK", then the amount of harvested energy is not enough to provide the minimum energy budget

E min B . E strong H
is the threshold at which the harvested energy is considered to be fully "STRONG".

Residual Energy Fuzzification: Three fuzzy sets are used to describe the residual energy e S , which is within the range r0, E max S s. These fuzzy sets, named "FAIL", "EMPTY" and "FULL", are associated to the following membership functions, shown by Fig. 2b:

µ f ail pxq " $ ' ' & ' ' % 1, if x ď E f ail S ´x`E empty S E empty S ´Efail S , if E f ail S ă x ă E empty S 0, if x ě E empty S (4) µemptypxq " $ ' ' ' ' & ' ' ' ' % 0, if x ď E f ail S x´E f ail S E empty S ´Efail S , if E f ail S ă x ď E empty S fK pxq, if E empty S ă x ă E f ull S 0, if x ě E f ull S ( 5
)
µ f ull pxq " $ ' & ' % 0, if x ď E empty S 1 ´fK pxq, if E empty S ă x ă E f ull S 1, if x ě E f ull S (6)
where

f K pxq " ˜´x `Efull S E f ull S ´Eempty S ¸K , (7)
and K ě 0 controls the shapes of the membership functions µ f ull and µ empty . The higher K is, the faster µ f ull tends to 1 and µ empty tends to 0 when the residual energy increases. Therefore, choosing high values of K makes Fuzzyman more tolerant about the fullness of the energy storage device. We denote E R the amount of energy that is needed to be reserved in order for the node to ensure the minimum quality of service when no harvested energy is available.

D. Inference Engine

The task of the inference engine is to create the control actions in fuzzy terms according to the fuzzy inputs provided by the fuzzification module. The inference engine strategy is described by a set of 6 fuzzy IF-THEN rules R i with i P t1 . . . 6u shown by the TABLE I. For each slot k, the output of the rule i is denoted e i B rks. The output of the rules R 2 and R 3 are given by [START_REF] Piorno | Prediction and Management in Energy Harvested Wireless Sensor Nodes[END_REF], and the rule R 6 output is the energy budget used at the previous slot.

e H e S FAIL EMPTY FULL STRONG E eds B (R 1 ) (8) (R 2 ) ( 8
) (R 3 ) WEAK E eds B (R 4 ) E min B (R 5 ) e B rk ´1s (R 6 )
In [START_REF] Piorno | Prediction and Management in Energy Harvested Wireless Sensor Nodes[END_REF], it is assumed that the energy harvesting rates for two consecutive time slots are similar. This assumption is reasonable for sufficiently small time slot duration. Energy prediction schemes can be used for better estimation of the energy harvesting rate in near future [START_REF] Piorno | Prediction and Management in Energy Harvested Wireless Sensor Nodes[END_REF].

All rules contain the fuzzy logic AND operation, and share the following multi-input single-output form: "IF (e S rk ´1s is X i S ) AND (e H rk ´1s is X i H ) THEN e B rks is e i B rks", where the phrase "x is X" is an abbreviation for the complete statement "x belongs to the fuzzy set X with a membership value µ X pxq", X i S can be either FAIL, EMPTY or FULL and X i H can be either STRONG or WEAK. It is important to notice that up to four rules can be activated at one run of Fuzzyman. The power strategy implemented by TABLE I corresponds to five different scenarios:

1) R 1 and R 4 : If the residual energy is FAIL, then the node is in energy distress. In that case, the energy budget is set to E eds B . 2) R 5 : If the amount of harvested energy is WEAK and the energy storage device is EMPTY, then the energy budget is set to the amount of energy required to ensure minimum quality of service, i.e. E min B . 3) R 6 : If the amount of harvested energy is WEAK and the energy storage device is FULL, then the energy budget is unchanged. 4) R 2 : If the amount of harvested energy is STRONG and the energy storage device is not yet fully charged, i.e. µ f ull pe S rk ´1sq ă 1, then part of the harvested energy is used to power the node, while the rest is stored. The fraction of the harvested energy used to power the node will be at least E min B , and depends on µ f ull as shown by [START_REF] Piorno | Prediction and Management in Energy Harvested Wireless Sensor Nodes[END_REF]. Therefore, K controls the energy allocation policy of Fuzzyman. 5) R 3 : If the amount of harvested energy is STRONG and the energy storage device is fully charged, i.e.

µ f ull pe S rk ´1sq " 1, then only the amount of energy required to compensate for the leakage is stored, while the rest is used to power the node, thus minimizing the risk of energy waste. The fuzzy AND operator is implemented by the min function [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems[END_REF]. The activation value µ i R rks ě 0 for each rule R i is defined by:

µ i R rks " min ! µ X i S pe S rk ´1sq , µ X i H pe H rk ´1sq ) . (9)
The rule R i is activated if its activation value is strictly positive. If the rule is not activated, then its output value e i B rks is simply set to 0. At every run of Fuzzyman, at least one rule is activated, and thus:

6 ÿ i"1 µ i R rks ą 0. ( 10
)
The activation value of each rule is interpreted as the membership value of the energy budget to the output of the rule. The importance of K can be seen here. Indeed, the K parameter controls the membership functions of the FULL and EMPTY fuzzy sets, and therefore impacts the activation values of the rules. The highest K is, the more tolerant is Fuzzyman about the fullness of the energy storage device, and therefore the less prudent it is. In Section III, the choice of the adequate value of K in the context of indoor ambient light harvesting is considered.

E. Defuzzification of the Energy Budget

The last unit of Fuzzyman is the defuzzification unit, which computes a physical value of the energy budget from the outputs of the inference engine. The "center-of-gravity" is the most common formula [START_REF] Chen | Introduction to Fuzzy Sets, Fuzzy Logic, and Fuzzy Control Systems[END_REF] to perform defuzzification. Thus, the physical value of the energy budget is computed by: e B rks "

ř 6 i"1 µ i R rkse i B rks ř 6 i"1 µ i R rks , (11)
which can always be computed according to [START_REF] Peng | Throughput optimal energy neutral management for energy harvesting wireless sensor networks[END_REF]. Finally, the algorithm of Fuzzyman is shown by Algorithm 1. The complexity of the proposed algorithm is Op1q, and incurs very few computations and memory overhead. Therefore, it is well-adapted to wireless sensor nodes.

Algorithm 1 Fuzzyman algorithm

Input: e S rk ´1s, e H rk ´1s i Ð 1 while i ď 6 do

µ i R rks Ð mintµ X i S pe S rk ´1sq, µ X i H pe H rk ´1squ if µ i R rks ą 0 then Set e i B rks according to TABLE I else e i B rks Ð 0 i Ð i `1 e B rks Ð ř 6 i"1 µ i R rkse i B rks ř 6 i"1 µ i R rks return e B rks

III. TUNING FUZZYMAN

The K parameter is the control parameter of Fuzzyman. Choosing K inappropriately may lead to power failures or energy waste. The adequate value of K depends on both the energy source and the energy storage device capacity E max S . We focus on the PowWow platform [START_REF]PowWow: Power Optimized Hardware and Software FrameWork for Wireless Motes[END_REF], which embeds a 0.9 F supercapacitor. Moreover, EH-nodes powered by indoor ambient light are considered in this work. Ambient light is the most common and mature among the different forms of energy harvesting. Indoor ambient light is usually a diurnal energy source, and the typical illumination level varies from 1 W/m 2 [START_REF] Paradiso | Energy scavenging for mobile and wireless electronics[END_REF] to 10 W/m 2 [START_REF] Mathúna | Energy scavenging for long-term deployable wireless sensor networks[END_REF]. Simulations are used to find the adequate value of K when the PowWow platform is used and when indoor ambient light is harvested.

A. Simulation setup

Simulations were done using GreenCastalia [START_REF] Benedetti | GreenCastalia: An Energyharvesting-enabled Framework for the Castalia Simulator[END_REF], an opensource energy harvesting simulation framework for the Castalia/OMNeT++ simulator [START_REF] Boulis | Castalia: Revealing Pitfalls in Designing Distributed Algorithms in WSN[END_REF]. The simulated network consists of one sink that uses batteries as energy supply, and four EH-nodes powered by solar cells. The solar panel area is set to 28 cm 2 , and the panel efficiency to 15%, which is a realistic value regarding current photovoltaic technologies [START_REF] Green | Solar cell efficiency tables (version 45)[END_REF]. The simulated platform embeds a TI CC1000 radio chip, which consumes 22.2 mW in receive state, 80.1 mW in transmit state and 0.0006 mW in sleep state. Because we want to evaluate the performance of the PM, only the energy waste due to energy storage device saturation i.e. harvested energy that cannot be stored because the energy storage device is full, is considered. Therefore, the power conversion efficiency η is set to 1 and the leakage power P L is set to 0 W. Moreover, T is set to 300 s, and each simulation last 31 days (simulated time).

The energy consumption of the EH-node is controlled by duty-cycling [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF]. As communication is usually the most consuming task, the idea of duty-cycling is to allow the node to switch its radio between the sleep state and the active state according to a schedule. At each wake up, the sensor node performs a measurement and sends the so obtained value to the sink. Environmental power sources provide energy that varies with time and space, leading to decoupled and individual duty-cycle among EH-nodes. This makes synchronous MAC protocols unsuitable to EH-WSNs as they require synchronized duty-cycle [START_REF] Fafoutis | Analytical comparison of MAC schemes for Energy Harvesting -Wireless Sensor Networks[END_REF]. In [START_REF] Aoudia | GRAPMAN: Gradual Power Manager for Consistent Throughput of Energy Harvesting Wireless Sensor Nodes[END_REF], we have shown that a simple CSMA/CA MAC protocol leads to lower energy consumption than the TMAC protocol that Castalia proposes. Therefore, this protocol is used in this work. E min B is set to 0.0221 J which corresponds to a minimal wake up frequency of 1{60 Hz.

B. Energy traces

GreenCastalia needs energy traces in order to simulate the harvested energy. In our previous work [START_REF] Aoudia | GRAPMAN: Gradual Power Manager for Consistent Throughput of Energy Harvesting Wireless Sensor Nodes[END_REF], a trace generation algorithm that generates diurnal traces was proposed. The purpose of the trace generation algorithm is to evaluate PMs in regards to energy source characteristics that influence significantly their behaviors, and which can be set by the user

C. Simulations results

Two metrics are considered for the choice of K: the downtime ratio D R corresponding to the ratio of time spent in the power failure state, and the energy utilization efficiency ξ, defined as the ratio of the total energy used by the node over the total energy harvested. This metric is similar to the harvested energy utilization introduced in [START_REF] Peng | Prediction free energy neutral power management for energy harvesting wireless sensor nodes[END_REF].

Fig. 3 and Fig. 4 show respectively ξ and D R for values of K ranging from 0 to 10. We can see that for values of K higher than 0.4, the energy efficiency is higher than 0.99 for the four scenarios, while for smaller values of K the energy efficiency is significantly lower when P AV G " 10 W/m 2 . These results reveal that using low values of K can prevent Fuzzyman from taking advantage of all the harvested energy. Nonetheless, using too high values of K causes Fuzzyman to incur power failures. Indeed, Fig. 4 shows that for values of K greater than 1.1 the downtime ratio stop being null and increases rapidly. According to these results, K " 1.1 is the value that maximizes ξ while achieving a null downtime ratio for the four traces introduced in Section III-B. Therefore, this value of K is chosen for the evaluation of Fuzzyman presented in Section IV. Fig. 2 shows the membership functions when K " 1.1.

IV. EVALUATING FUZZYMAN

We compare Fuzzyman to P-FREEN [START_REF] Peng | Prediction free energy neutral power management for energy harvesting wireless sensor nodes[END_REF], a state of the art model-free PM that outperforms the reference scheme proposed by Kansal et al. [START_REF] Kansal | Power Management in Energy Harvesting Sensor Networks[END_REF]. The simulation setup is the same as in Section III-A. Simulations were done with energy traces generated by the model introduced in Section III-B. Two metrics in addition to D R and ξ are considered: the wasted energy E W ST , i.e. the harvested energy that could not be stored because the energy storage device was full, and the average energy budget Ď E B . Simulations were run for values of P AV G ranging from 1 W/m 2 to 10 W/m 2 , and values of σ D ranging from 0.1 to 0.4. Both Fuzzyman and P-FREEN achieve downtime ratio lower than 0.2 % in all the simulation scenarios. Therefore, we focus on the energy utilization efficiency, the wasted energy and the average energy budget in the rest of this section. Fig. 5 exposes the impact of P AV G and σ D on ξ. If ξ is similar for both PMs when P AV G " 1 W/m 2 , Fuzzyman outperforms P-FREEN for higher values of P AV G . σ D has no impact on the performance of the PMs, whereas high values of P AV G lead to lower values of ξ for P-FREEN, but do not influence the performance of Fuzzyman. As we will see below, these results are explained by the larger waste of energy incurred by P-FREEN. Fig. 6 shows the wasted energy E W ST when P AV G and σ D vary. As we can see, Fuzzyman incurs significantly less energy waste than P-FREEN. As previously, σ D does not impact the performance of the PMs. When P AV G increases, the amount of wasted energy increases when P-FREEN is used, but stays low when Fuzzyman is used. This result explains the values of ξ exposed by Fig. 5.

In order to evaluate the impact of the more efficient harvested energy management achieved by Fuzzyman, the average packet rate Ď P R is considered. Fig. 7 shows the impact of P AV G and σ D on Ď P R . If the average energy budget is similar for both PMs for low values of P AV G , Fuzzyman outperforms P-FREEN for high values of P AV G . Moreover, the advantage of Fuzzyman over P-FREEN increases when P AV G increases. Indeed, Fuzzyman achieves up to 25% higher Ď P R than P-FREEN (when P AV G " 10 mW and σ D " 0.4).

V. CONCLUSION

This paper presents the design and evaluation of Fuzzyman, a novel PM for EH-nodes based on fuzzy control theory. Fuzzyman is able to provide high harvested energy utilization efficiency, while avoiding power failures. This work presents the evaluation of Fuzzyman when compared to P-FREEN, a state of the art PM. Using extensive trace driven network simulations, we have shown that Fuzzyman outperforms P-FREEN in terms of harvested energy utilization efficiency. In our future work, we intend to implement Fuzzyman on real hardware platforms.

Fig. 1 :

 1 Fig. 1: Global architecture of Fuzzyman.

Fig. 2 :

 2 Fig. 2: Membership functions used by the fuzzification module.

  reserved sufficient energy E R . E empty S indicates that all the reserved energy E R was used up. Thus, E R " E f ull S ´Eempty S . Having E empty S ą E min S avoids power failure when all the reserved energy has been used. When the amount of residual energy falls below E empty S , the node enters the energy distress state. Finally, having E f ull S ă E max S avoids wasting energy by overflow of the storage device.

P 2 Fig. 3 :

 23 Fig. 3: Energy utilization efficiency ξ as a function of K.

Fig. 4 :

 4 Fig. 4: Downtime ratio DR as a function of K.

Fig. 5 :

 5 Fig. 5: Energy utilization efficiency ξ as a function of PAV G for different values of σD.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Wasted energy EW ST as a function of PAV G for different values of σD.

TABLE I :

 I Rule base used by the inference engine.

	e i B rks " E min B	μfull
	pe S rk ´1sq ˆeH rk ´1s	´Emin

B η

´PL T ˙η.


Mai-Thanh Tran
email: mai-thanh.tran@irisa.fr

Matthieu Gautier
email: matthieu.gautier@irisa.fr

Emmanuel Casseau
email: emmanuel.casseau@irisa.fr

On the FPGA-based implementation of a flexible waveform from a high-level description: Application to LTE FFT case study

Keywords: High-Level Synthesis, Software Defined Radio, FPGA, LTE, Hardware implementation, Design flow

The Field Programmable Gate Array (FPGA) technology is expected to play a key role in the development of Software Defined Radio (SDR) platforms. To this aim, leveraging the nascent High-Level Synthesis (HLS) tools, a design flow from high-level specifications to Register-Transfer Level (RTL) description can be thought to generate processing blocks that can be reconfigured at run-time. Based on such a flow, this paper describes the architectural exploration of a Fast Fourier Transform (FFT) for Long Term Evolution (LTE) standard. Synthesis results show the tradeoff between reconfiguration time and area that can be achieved with such an approach.

Introduction

Advanced wireless communication standards are designed with various requirements in terms of data transmission rate, spectral efficiency and multiple channel bandwidths. To fulfil these requirements, many configurations of the waveform (PHY layer) features are allowed such as the number of antennas, the coding rate, the modulation scheme or the number of subcarriers in the case of Orthogonal Frequency Division Multiplexing (OFDM) modulation. In such a context, new needs of PHY layer implementation appear while the hardware implementation has to change from one configuration to one another in a short time, refereed to as run-time flexibility in this document.

An emergent technology that answers these new needs is Software Defined Radio (SDR) that allows both flexibility and fast prototyping capabilities from a high-level description [START_REF]Software-defined radio: Basics and evolution to cognitive radio[END_REF]. However, when implementing the processing on Digital Signal Processors (DSP), SDR suffers from important power consumption and limited performance as compared to dedicated hardware fabrics. FPGA-based SDR is an old paradigm [START_REF] Cummings | FPGA in the Software Radio[END_REF] offering a good tradeoff between reconfiguration capability and processing power. Fast prototyping capability of an FPGA-based SDR is achieved by leveraging High-Level Synthesis (HLS) principles and tools to generate Register-Transfer Level (RTL) descriptions from high-level specifications [START_REF] Ouedraogo | Frame-based Modeling for Automatic Synthesis of FPGA-Software Defined Radio[END_REF]. However, the issue of run-time flexibility is still opened. This paper discusses the FPGA-based implementation of a run-time hardware reconfiguration of a flexible waveform from its high-level description. The proposed methodology mainly aims at analyzing the performance of using a multi-mode processing block with control signals or Dynamic Partial Reconfiguration (DPR) to provide flexibility.

In this paper, the example of LTE standard is addressed. Among many configurations, this standard specifies that the computation of an OFDM symbol can be performed over several numbers of subcarriers among {128, 256, 512, 1024, 1536, 2048} and one symbol has a duration of 66.67 µs [START_REF] Yang | Power and Area Minimization of Reconfigurable FFT Processors: A 3GPP-LTE Example[END_REF]. Because Fast Fourier Transforms (FFTs) are used to compute the OFDM symbols, this paper discusses the FPGA implementation of a flexible FFT function that can operate with the different configurations of the LTE standard.

The main contributions of this paper are:

-To implement run-time reconfiguration from a high-level description of a processing block, -To propose a flexible FFT implementation that covers the LTE configuration modes, -To perform Design Space Exploration (DSE) of the proposed implementations using HLS capabilities.

The paper is organized as follows. A discussion over related works is given in Section 2. The flow to design a reconfigurable component from its high-level description is introduced in Section 3. Section 4 discusses the implementation of the flexible FFT for LTE purpose. RTL synthesis results and DPR performance for different reconfigurations are given in Section 5. Finally, conclusions and perspectives are drawn in Section 6.

Related works

Several proposals attempted to meet the flexibility requirements of an SDR by using software-based approaches. Indeed, software gives an abstraction level that enables more control over the hardware-based approaches. Two complementary approaches have been proposed namely, the SDR-specific languages to design the waveform [START_REF] Willink | The Waveform Description Language: Moving from Implementation to Specification[END_REF][16] [START_REF]GNU Radio: The free and open software radio ecosystem[END_REF] and the SDR middleware to provide the building environment [START_REF] Jianxin | The Software Communication Architecture: Evolutions and Trends[END_REF] [START_REF] Gelonch | P-HAL: a Middleware for SDR applications[END_REF]. They both take advantage of the abstraction level given by the software to achieve both compile-time and run-time flexibility.

Our proposal aims at keeping a high specification level while addressing FPGA platforms. To this end, HLS turns out to be a good candidate to achieve such a high abstraction level. The recent development of HLS tools allows the consideration of components described in C/C++ languages. It raises the abstraction level compared to hardware languages like VHDL and Verilog dedicated to RTL-based architectures. HLS fast prototyping capability enables the compile-time flexibility of an FPGA-based SDR [START_REF] Ouedraogo | A frame-based Domain-Specific Language for rapid prototyping of FPGA-based Software-Defined Radios[END_REF].

There are two kinds of works that address the run-time flexibility of a FPGAbased SDR. The firsts propose to design multi-mode RTL components with control signals to switch between the different modes [START_REF] Casseau | Design of Multi-Mode Application-Specific Cores Based on High-Level Synthesis[END_REF]. The others are based on DPR. Run-time DPR, refereed to as Hardware reconfiguration in the following, is the ability to reconfigure part of the FPGA (e.g. a functionality at the hardware level) while the rest of the FPGA continues to work. It is a research topic since the 90s [START_REF] Lemoine | Run time reconfiguration of FPGA for scanning genomic databases[END_REF] and it is now commonly used in FPGAs, since Xilinx and Altera provide such circuits [START_REF]Partial Reconfiguration User Guide[END_REF] [START_REF]Increasing Design Functionality with Partial and Dynamic Reconfiguration in 28nm FPGAs, Altera white paper[END_REF]. The main advantages of the Hardware reconfiguration are to add hardware flexibility and to reuse hardware area, allowing power consumption and production cost reductions.

Based on the proposed methodology, a flexible FFT is proposed in this paper for LTE specifications. Hundreds of architectures for 128-to 2048-point FFT has been proposed by varying the degree of parallelism and the radix factorization [START_REF] Pitkanen | Low-power application-specific processor for FFT computations[END_REF] [START_REF] Chen | Hardware Efficient Mixed Radix-25/16/9 FFT for LTE Systems. Very Large Scale Integration[END_REF]. These implementations are optimized in terms of speed, memory used and hardware logic requirements. A reconfigurable FFT for which algorithmic modifications allow the reuse of the resources while switching form one FFT to one another can be found in [START_REF] Yang | Power and Area Minimization of Reconfigurable FFT Processors: A 3GPP-LTE Example[END_REF]. While all of these components are described at the RTL level so require very good skills in hardware design, our approach aims at providing a FFT design methodology from a high-level description to jointly achieve fast DSE and run-time reconfiguration.

SDreconf: Design Flow for Software Defined Reconfiguration

As mentioned in Section 2, there are different ways to achieve a flexible processing block while implementing it onto a FPGA. The first one is to design a multi-mode processing block and the second one is to use DPR (Hardware reconfiguration). In our approach, a multi-mode processing block can be described using dedicated algorithmic modifications of the processing block (Algorithmic reconfiguration) or with an automatic generation using a HLS encapsulation (Software reconfiguration). The goal of our design flow is to choose or combine these reconfigurations while describing the processing block at a high-level of description. This work is based on one commercially available HLS tool: Vi-vadoHLS from Xilinx. It produces a RTL description of an application from its C-like specification. This section details the ways towards the generation of a flexible block.

Software reconfiguration: This reconfiguration uses HLS encapsulation to generate a Multi mode block. The method uses the different modes of a block and generates a Multi mode block with a control input to switch between the modes. Algorithm 1 describes this encapsulation in the case of two modes block A and block B. The advantages of this method are its simplicity, the rapid prototyping capability provided by HLS and the short reconfiguration time (one clock cycle). However, Algorithm 1 Software reconfiguration for the automatic generation of a multimode processing block. the resources can be important in that case. Actually the HLS tool does not share the resources efficiently although the modes are timewize mutually exclusive.

Hardware reconfiguration:

In dynamic partial reconfiguration, the FPGA is divided into several regions being static (the areas that are not modified) or reconfigurable (the reconfigurable partitions). Each mode has its own partial bitstream. The partial bitstreams are stored in a memory and a software processor controls which partial bitstream is loaded into the reconfigurable partition at a particular time. The reconfigurable partition size must cover the area of the largest mode. Figure 1 shows the example of the Hardware reconfiguration of two modes block A and block B. The two modes are processed separately using first HLS and then RTL synthesis to generate two partial bitstreams. Part of this flow can be automated, at least to have an estimation of the performance. The main advantage is that the modes share the same area. The drawback is the reconfiguration time that depends on the size of the partial bitstream.

Algorithmic reconfiguration: For this kind of reconfiguration, the designer has to hand-code a dedicated processing block being intrinsically flexible. Signals are used to control the modes. Algorithmic optimizations should be done so that the HLS tool can share the resources between the modes. Fig. 2 shows the design tradeoff between the resources and the reconfiguration time when the three kinds of reconfiguration are considered. Algorithmic reconfiguration is used to decrease the resources compared to Software reconfiguration and to decrease the reconfiguration time compared to Hardware reconfiguration. It provides the best performance in term of resources/reconfiguration time tradeoff. However, depending on the processing blocks, time to code the algorithmic reconfiguration can be important compared to Software reconfiguration. Based on these three kinds of reconfiguration, the design flow used in this work is shown in Fig. 3. The different modes of a processing block can be provided by hand-coding or using a HLS tool to generate different versions of a processing block by modifying synthesis constraints like throughput, latency, data size, etc. Such tools make it easy to explore a set of solutions via DSE [START_REF] Le Moullec | Algorithmic-level specification and characterization of embedded multimedia applications with design trotter[END_REF][20][9] considering a given architecture. In Fig. 3, Performance constraints are user-defined constraints such as resources/area, reconfiguration time, throughput or latency. The Performance analysis compares the performance of the three paths to the user-defined constraints. The basic idea is to first analyze the performance of the Software reconfiguration and Hardware reconfiguration paths and to use the Algorithmic reconfiguration if the Performance constraints are not met.

We have experimented this design flow with the rapid prototyping of a flexible FFT. An architecture exploration was performed allowing the comparison of the three kinds of reconfiguration.

Building a flexible FFT

In this section, a flexible FFT is designed using the proposed approach. Addressing LTE standard, the resulting FFT component should have six modes corresponding to these FFT sizes: {128, 256, 512, 1024, 1536, 2048}. To introduce the different kinds of reconfiguration, preliminary results are first given in Sections 4.1 and 4.2 with the design of a flexible FFT with two sizes: {128, 2048}. This design is based on two hand-coded FFT functions using the radix-2 Decimation-In-Time (DIT) algorithm which is the simplest and most common form of the Cooley-Tukey algorithm [START_REF] Cooley | Mathematics of Computation, chapter An algorithm for the machine calculation of complex Fourier series[END_REF].

Experimental tools and setup: Vivado HLS 2013.3 is used for the high-level synthesis. DPR is setup with PlanAhead 14.6. The xc6vlx240tff1156 FPGA is targeted from Virtex 6 family as ML605 evaluation board will be used for future demonstration. Syntheses are based on a 100 MHz clock frequency.

Software reconfiguration

First, two functions for 128-and 2048-point FFTs have been hand-coded and synthesized separately (Block FFT128( ) and Block FFT2048( ) respectively). Then the FFT with 2 modes (128/2048) has been designed using Software reconfiguration: using Algorithm 1, a function Two Mode Block( ) is generated from Block FFT128( ) and Block FFT2048( ). Table 1 shows the synthesis results and the latency (in number of clock cycles) of the three processing blocks. The resources are given with logical components such as the number of BRAM, DSP slices, LUT and FF. As expected, Block FFT2048( ) requires more resources than Block FFT128( ): the number of BRAM to store cos and sin coefficients and input data is twofold and the number of DSP slices is 4 times more.

Except for the number of BRAM, Table 1 shows that the resources used by Two Mode Block( ) are (a little bit less than) the sum of the resources used by the two FFT blocks when synthesized separately. The HLS tool does not share the resources between the two functions although they are not executed at the same time. In this case, from the resources point of view, Software reconfiguration appears not to be an efficient solution to implement a flexible block. Latency is similar to mono-mode blocks.

Hardware reconfiguration

The two functions Block FFT128( ) and Block FFT2048( ) are now used for Hardware reconfiguration. In Xilinx's FPGAs [START_REF]Partial Reconfiguration User Guide[END_REF], the functions to be dynamically placed are mapped into an area called a reconfigurable partition. Generally speaking, a partition has a rectangle shape and uses resources according to this area even if they are not needed. Two partitions have been first generated using PlanAhead tool: one for the FFT 128 only and one for the FFT 2048 only. Table 2 shows the resources used by these partitions. Bitstream sizes are also given. Because FFT 128's partition uses less logical components than FFT 2048's one, it is smaller than FFT 2048's one. The reconfiguration time depends on the bitstream size so the reconfiguration time for FFT 128 is smaller than FFT 2048's one. Reconfiguration time is computed from PRCC tool (Partial Reconfiguration Cost Calculator) from Technical University of Crete [START_REF] Papadimitriou | Partial Reconfiguration Cost Calculator[END_REF] assuming that the reconfiguration controller is an on-chip MicroBlaze processor1 . For comparison, Table 2 also shows the resources needed by FFT 128 and FFT 2048 when they are placed as static logic (i.e. not as a reconfigurable module, so resources needed are same as in Table 1).

To perform the DPR of the 2 functions, a third partition called FFT 128/2048 in Table 2 has been defined. In this case, the two functions are placed on the same partition, i.e. on the same area of the FPGA. For each type of logical component, the resources used by this partition are based on the more costly case. In our case, FFT 2048 partition always needs the largest number of resources whatever the kind of logical component. Thus the resulting FFT 128/2048 partition is based on the FFT 2048 partition. Reconfigurable partition's latency is equal to the latency of the function when synthesized alone onto a static region. The hardware reconfiguration needs 32.9 ms to switch from one mode to the other one whereas only one clock cycle is required with Software reconfiguration. It means many OFDM symbols will be lost in practice when changing the mode with hardware reconfiguration.

Algorithmic reconfiguration

The FFT for LTE standard should have six modes: {128, 256, 512, 1024, 1536, 2048}.

Based on the previous results, a Software reconfiguration will generate a huge component as the resources are not shared. Hardware reconfiguration makes resource sharing possible but may require a long reconfiguration time. In this section, we first present a power-of-two point FFT for algorithmic reconfiguration to share the resources between its different modes. Then, a FFT 1536 function is presented. Sharing the resources of these 2 functions is discussed.

Power-of-two point FFT for algorithmic reconfiguration: The power-of-two point FFT has 5 modes {128, 256, 512, 1024, 2048}. A dedicated control signal is used to decide the mode and the HLS tool deals with the FFT size as a variable. Indeed, as presenting in Algorithm 2, FFT size and FFT stages are calculated based on the control signal value. When FFT size and FFT stages are determined, a standard three-loop structure for the FFT based on radix-2 is computed. The first loop determines the stage. The second loop chooses butterflies with the same twiddle factor at each stage. Last loop computes all the chosen butterflies. This algorithmic reconfiguration generates a Block FFTpow2() function with only one main FFT core for the five different modes. With this function, the resources should be approximately the ones used by the largest FFT (i.e. 2048).

1536-point FFT: By applying the Cooley-Tukey algorithm [START_REF] Cooley | Mathematics of Computation, chapter An algorithm for the machine calculation of complex Fourier series[END_REF] for a FFT size of 1536, the Block FFT1536( ) function can be generated using three Block FFT512( ) functions and one radix-3 function [START_REF]Software Optimization of DFTs and IDFTs Using the StarCore SC3850 DSP Core[END_REF] as shown in Fig 4 .  First, the 1536 inputs of the FFT are split into three parts. Those parts are computed as three 512-point FFTs independently. Then, while the first part is kept as it is, the second and the third ones are multiplied by twiddles factors. Last, the radix-3 function is applied to compute the final results.

Resource sharing may theoretically be done between Block FFT512( ) functions of the 1536-point FFT and the power-of-two point FFT because they are Algorithm 2 Algorithmic reconfiguration for the power-of-two point FFT.

function Block FFTpow2(inputs, outputs, control) 0 ≤ control ≤ 4 FFT size max = 2048 FFT stages max = 11 FFT size = FFT size max >> control FFT size = FFT size max 2 control FFT stages= FFT stages max -control Bit reverse( ) re-range the order of bits before calculating for i = 0 to FFT stages do Calculate index( ) choose the stage, prepare for possible twiddles for j = 0 to FFT size/2 do Computing twiddles( ) determine coefficients for radix 2 for k = 0 to FFT size/2 do Radix 2(inputs, outputs) end function both based on the radix-2 algorithm. On the contrary, the Block Radix3( ) function is based on radix-3 thus it can not share resources.

Performance results

This section presents the architectural exploration of a flexible FFT for LTE standard. First, design space will be explored for the function Block FFTpow2(). Then, the combination between Block FFTpow2( ) and Block FFT1536( ) will be addressed using Software and Hardware reconfigurations.

Design space exploration of the power-of-two point FFT

In order to generate a flexible FFT that respects the design constraints (area, latency, throughput, . . .), HLS allows the DSE of a processing block by using compilation directives. This part presents the DSE of the function Block FFTpow2(). Several directives are made available on a typical HLS tool (e.g. memory mapping, pipeline, loop unrolling, inlining, . . .). They make it possible to optimize the design for area or latency. In this study, because of the loop structures and the data dependencies of the FFT, loop unrolling is used. Loop unrolling reduces the total loop iterations by duplicating (with a factor U) the loop body so that we can tradeoff between area and latency. Figure 5 shows the latency of Block FFTpow2( ) processing block as a function of the number of DSP slices. In practice, four multi-mode components have been generated by varying the unroll factor U. Each component is characterized by its numbers of DSP slices. The number of DSP slices increases with the unroll factor while the latency decreases with the unroll factor. One's can see a floor effect appears in Figure 5. Due to the BRAM accesses (read and write data from/to memory) that reach their bounds for U=4, increasing the number of DSP resources is not useful in practice. The same behavior is also obtained for the number of LUT and FF. Thus U=4 seems to be a good tradeoff between number of resources and latency.

Proposed flexible FFT implementations for LTE standard

Performance of the multi-mode FFT with software reconfiguration: Software reconfiguration is applied first to design the FFT with 6 modes for LTE. Using Algorithm 1, a Multi Mode Block LTE( ) function is generated from the two functions Block FFTpow2( ) and Block FFT1536( ). Table 3 shows the synthesis results and latency (in number of clock cycles) of the three processing blocks. U=4 is used for Block FFTpow2( ). The resources used by Multi Mode Block LTE( ) are almost the sum of the resources used by Block FFTpow2( ) and Block FFT1536( ) when synthesized separately. As observed in Section 4.1, the HLS tool does not share the resources between the two functions even if they are not executed at the same time.

Performance of the multi-mode FFT with hardware reconfiguration: Hardware reconfiguration is now applied on the two functions Block FFTpow2( ) and Block FFT1536( ). Two partitions are first generated: one for the power-of-two point FFT only and one for the FFT 1536 only. Then, a partition is finally created for the DPR of the 2 FFTs. Table 4 shows the synthesis results. The partition for FFT 1536 is smaller than the power-of-two point FFT's one. Actually, number of BRAMs is greater but function Block FFT1536( ) uses less DSP slices than Block FFTpow2( ) so that its area is smaller. Thus, when combining the 2 FFTs into one partition, the resulting partition is based on power-of-two point FFT's partition. Compared with Software reconfiguration, the multi-mode FFT based on hardware reconfiguration uses less resources (BRAM and DSP are the more area costly logical components). When the FFT size has to be modified but is still a power of two, in both cases only one clock cycle is required to reconfigure. However, 32.9 ms are required to reconfigure when switching from a 1536-point FFT and a power-of-two point FFT (or vice versa) with hardware reconguration whereas only one clock cycle is required with Software reconfiguration.

Conclusion

This paper presents a methodology for the implementation of run-time reconfiguration in the context of FPGA-based SDR. The proposed design flow allows the exploration between dynamic partial reconfiguration and control signal based multi-mode design. This architectural tradeoff relies upon HLS and its associated design optimizations. A flexible FFT for LTE standard is implemented as a case study. The proposed component combines both DPR (to deal with FFT size of 1536) and algorithmic reconfiguration (when FFT size is a power of two). Synthesis results show the tradeoff that could be achieved between the reconfiguration time and the FPGA resource utilization. Future work is to explore the implementation of other processing functions and the automation of the design flow.

Fig. 1 .

 1 Fig. 1. Design approach based on hardware reconfiguration.

Fig. 2 .

 2 Fig. 2. Tradeoff between resources and reconfiguration time for the different reconfigurations.

Fig. 3 .

 3 Fig. 3. Design flow for Software Defined Reconfiguration.

Fig. 4 .

 4 Fig. 4. Functional description of Block FFT1536( ) function.

Fig. 5 .

 5 Fig. 5. DSE of Block FFTpow2( ) function.

Table 1 .

 1 Performance of Software reconfiguration for a FFT with 2 modes (128/2048).

	Processing block	Block FFT128( ) Block FFT2048( ) Two Mode Block( )
	BRAM	6	12	12
	DSP	17	65	82
	LUT	1017	2522	3459
	FF	862	2443	3241
	Latency	5362	72410	5491/72411

Table 2 .

 2 Performance for Hardware reconfiguration of a FFT with 2 modes (128/2048).

Table 3 .

 3 Performance of a FFT for LTE standard with Software reconfiguration.

	Processing block	Block FFTpow2( ) Block FFT1536( ) Multi Mode Block LTE( )
	BRAM	12	14	26
	DSP	65	40	103
	LUT	2553	3054	5256
	FF	2497	2010	4299
	Latency	cf. Fig.5 -U=4	52198	cf. Fig.5/52198

Table 4 .

 4 Performance of a FFT for LTE standard with Hardware reconfiguration.

Higher throughput up to 400 MBytes/s may be reached using a dedicated controller so that reconfiguration time can be reduced.