Jean-Charles Faugère

Pierre-Jean Spaenlehauer

Jules Svartz

Sparse Gröbner Bases: the Unmixed Case

Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amounts to computing in a semigroup algebra, i.e. an algebra generated by a subset of Laurent monomials. In order to solve symbolically sparse systems, we introduce sparse Gröbner bases, an analog of classical Gröbner bases for semigroup algebras, and we propose sparse variants of the F 5 and FGLM algorithms to compute them. Our prototype "proof-of-concept" implementation shows large speed-ups (more than 100 for some examples) compared to optimized (classical) Gröbner bases software. Moreover, in the case where the generating subset of monomials corresponds to the points with integer coordinates in a normal lattice polytope P ⊂ R n and under regularity assumptions, we prove complexity bounds which depend on the combinatorial properties of P. These bounds yield new estimates on the complexity of solving 0-dim systems where all polynomials share the same Newton polytope (unmixed case). For instance, we generalize the bound min(n 1 , n 2 ) + 1 on the maximal degree in a Gröbner basis of a 0-dim. bilinear system with blocks of variables of sizes (n 1 , n 2 ) to the multilinear case: n imax(n i ) + 1. We also propose a variant of Fröberg's conjecture which allows us to estimate the complexity of solving overdetermined sparse systems.

Introduction

Context and problem statement. Many polynomial systems or systems of Laurent polynomials arising in applications do not have a dense monomial structure (e.g multihomogeneous systems, fewnomials, systems invariant under the action of a linear group,. . . ). The development of toric geometry during the 70s/80s has led to toric (or sparse) elimination theory [START_REF] Sturmfels | Sparse elimination theory[END_REF], a framework designed to study and exploit algorithmically these monomial structures.

Central objects in toric geometry are semigroup algebras (also called toric rings). If S ⊂ Z n is an affine semigroup (see Def. 2.1), then the semigroup algebra k[S] is the set of finite sums s∈S a s X s , where X is a formal symbol, k is a field, a s ∈ k and s ∈ S. Semigroup algebras are isomorphic to subalgebras of k[X ±1 1 , . . . , X ±1 n ] generated by a finite subset of monomials.

Our motivation is to propose fast algorithms to solve symbolically systems whose support lie in one of the following classes of semigroups: semigroups constructed from the points with integer coordinates in a normal lattice polytope P ⊂ R n (in that case, the algorithms we propose are well-suited for unmixed systems: the Newton polytopes of the input polynomials are all equal to P) or semigroups generated by a scattered set of monomials (fewnomial systems).

Main results. Given a 0-dim. system of Laurent polynomials f 1 = • • • = f m = 0 and a finite subset M ⊂ Z n such that each polynomial belongs to the subalgebra generated by

{X α 1 1 • • • X αn n | α ∈ M},
we associate to M two affine semigroups: S M ⊂ Z n generated by M and S (h) M ⊂ Z n+1 generated by {(α, 1) ∈ Z n+1 | α ∈ M}. Under the assumption that S M contains zero but no nonzero pairs (s 1 , s 2 ) ∈ S 2 M s.t. s 1 + s 2 = 0, our solving strategy proceeds by combining a sparse variant in the homogeneous algebra k[S (h) M ] of the MatrixF5 algorithm and a sparse variant in k[S M ] of the FGLM algorithm. We define a notion of sparse Gröbner basis (Def. 3.1) that is computed by the sparse-MatrixF5 algorithm if we know a bound on its maximal degree (this maximal degree is called the witness degree of the system). An important feature of sparse GBs is that their definition depends only on the ambient semigroup algebra and not on an embedding in a polynomial algebra. In this sense, they differ conceptually from SAGBI bases, even though the sparse-FGLM algorithm has similarities with the SAGBI-FGLM algorithm proposed in [START_REF] Faugère | Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases[END_REF]. In the special case S M = N n , sparse Gröbner bases in k[S M ] are classical Gröbner bases, and sparse-FGLM is the usual FGLM algorithm.

At the end of the solving process, we obtain a rational parametrisation of the form

Q(T ) = 0 and ∀α ∈ M \ {0}, X α 1 1 • • • X αn n -Q α (T ) = 0
where Q ∈ k[T ] is a univariate polynomial, and for all α ∈ M, Q α ∈ k(T ) is a rational function. Consequently, the solutions of the input sparse system can be expressed in terms of the roots of the univariate polynomial Q by inverting a monomial map. The next main result addresses the question of the complexity of this solving process when M is given as the set P ∩ Z n , where P ⊂ R n is a lattice polytope of dimension n. It turns out that the complexities of sparse-MatrixF5 and sparse-FGLM algorithms depend mainly on intrinsic combinatorial properties of P:

• the normalized volume vol(P) ∈ N;

• the Castelnuovo-Mumford regularity reg(k[S (h)

P∩Z n ]) = n + 1ℓ where ℓ is the smallest integer such that the intersection of Z n with the interior of ℓ • P is nonempty;

• the Ehrhart polynomial HP P (ℓ) which equals the cardinality of (ℓ • P) ∩ Z n for ℓ ∈ N.

We use as indicator of the complexity the witness degree which bounds the maximal "sparse degree" (corresponding to an N-grading on k[S (h)

P∩Z n ]) in a reduced sparse Gröbner basis. More precisely, we obtain the following complexity estimates: Theorem 1.1. Let P ⊂ R n be a normal lattice polytope of dimension n with one vertex at 0 ∈ Z n , (d 1 , . . . , d n ) be a sequence of positive integers and

(f 1 , . . . , f n ) be a regular se- quence of Laurent polynomials in k[X ±1 1 , . . . , X ±1 n ] n , such that the support of f i is included in {X s 1 1 • • • X sn n | s ∈ (d i • P) ∩ Z n }. Then a sparse GB of the ideal f 1 , . . . , f n ⊂ k[S P∩Z n ] can be computed within O (n HP P (d wit ) ω )
arithmetic operations in k, where ω < 2.373 is a feasible exponent for the matrix multiplication and Direct consequences of these formulas allow us to derive new complexity bounds for solving regular multi-homogeneous systems. We show that the witness degree of a regular system of n multi-homogeneous polynomials of multi-degree (d 1 , . . . , d p ) w.r.t. blocks of variables of sizes (n 1 , . . . , n p ) (with n i = n) is bounded by n+2-max i∈{1,...,p} (⌈(n i +1)/d i ⌉) (which generalizes the bound min(n 1 , n 2 ) + 1 in the bilinear case [START_REF] Faugère | Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity[END_REF]). We also propose a variant of Fröberg's conjecture for sparse systems and a notion of semi-regularity, which yield complexity estimates for solving sparse overdetermined systems.

d wit ≤ reg(k[P]) + 1 + n j=1 (d j -1). Moreover, if 0 is a simple vertex of P ( i.
We have implemented in C a prototype of the sparse-MatrixF5 algorithm, that runs several times faster than the original F 5 algorithm in the FGb software. For instance, we report speed-up ratios greater than 100 for instances of overdetermined bihomogeneous systems. The implementation also works well for fewnomial systems (although this case is not covered by our complexity analysis).

Related works. Computational aspects of toric geometry and Gröbner bases are investigated in [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF]. In particular, [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF]Subroutine 11.18] gives an algorithm to compute syzygies of monomials in toric rings, which is an important routine for critical-pairs based algorithms.

Other approaches have been designed to take advantage of the sparse structure in Gröbner bases computations. For instance, the Slim Gröbner bases in [START_REF] Brickenstein | Slimgb: Gröbner bases with slim polynomials[END_REF] describes strategies to avoid increasing the number of monomials during computations. This approach improves practical computations, but does not lead to new asymptotic complexity bounds for classes of sparse systems.

The sparse structure and the connection with toric geometry have also been incorporated to the theory of resultants, and a vast literature has been written on this topic, see e.g. [START_REF] Canny | An efficient algorithm for the sparse mixed resultant[END_REF][START_REF] Canny | A subdivision-based algorithm for the sparse resultant[END_REF][START_REF] Emiris | Toric resultants and applications to geometric modelling[END_REF][START_REF] Emiris | Symbolic and numeric methods for exploiting structure in constructing resultant matrices[END_REF]. In particular, mixed monomials structures are well-understood in this context. Although we do not know how to extend the algorithms proposed in this paper to mixed structures, Gröbner-type algorithms enjoy the property of extending without any modification to the overdetermined case.

Perspectives. Our approach is for the moment limited to unmixed systems: all input polynomials have to lie in the same semigroup algebra. A possible extension of this work would be the generalization to mixed systems (where the algorithms would depend on the Newton polytope of each of the polynomials of the system). Some results seem to indicate that such a generalization may be possible: for instance, under genericity assumptions, mixed monomial bases of quotient algebras are explicitly described in [START_REF] Pedersen | Mixed monomial bases[END_REF]. Also, a bound on the witness degree and the complexity analysis is for the moment restricted to the polytopal case. Merging the approach in this paper with a Buchberger's type approach such as [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF]Algo. 11.17] could lead to a termination criterion of the sparse-MatrixF5 algorithm in the non-regular cases and for positive dimensional systems. Finally, finding complexity bounds which explain the efficiency of the sparse Gröbner bases approach for fewnomial systems (see Table 3) remains an open problem.

Organisation of the paper. We recall in Section 2 the background material on semigroup algebras and convex geometry that will be used throughout this paper. Section 3 introduces sparse Gröbner bases and describes a general solving process for sparse systems. The main algorithms are described in Section 4 and their complexities are analyzed in Section 5. Finally, we describe in Section 6 some results that are direct consequences of this new framework and experimental results in Section 7.

Acknowledgements. We are grateful to Kaie Kubjas, Guillaume Moroz and Bernd Sturmfels for helpful discussions and for pointing out important references. This work was partly done while the second author was supported and hosted by the Max Planck Institute for Mathematics (Bonn, Germany). This work was partly supported by the HPAC grant of the French National Research Agency (HPAC ANR-11-BS02-013).

Preliminaries and notations

In this paper, the basic algebraic objects corresponding to monomials in classical polynomial rings are affine semigroups. We always consider them embedded in Z n . We refer the reader to [START_REF] Cox | Toric varieties[END_REF][START_REF] Fulton | Introduction to Toric Varieties[END_REF][START_REF] Miller | Combinatorial commutative algebra[END_REF] for a more detailed presentation of this background material. First, we describe the main notations that will be used throughout the paper: Definition 2.1. An affine semigroup S is a finitely-generated additive subsemigroup of Z n for some n ∈ N containing 0 ∈ Z n and no nonzero invertible element ( i.e. for all s, s ′ ∈ S \ {0}, s + s ′ = 0). Any affine semigroup has a unique minimal set of generators, called the Hilbert basis of S and denoted by Hilb(S). Let gp(S) denote the smallest subgroup of Z n containing S. Then S is called normal if S = {q ∈ gp(S) | ∃c ∈ N, c • q ∈ S}. For a field k, we let k[S] denote the associated semigroup algebra of finite formal sums s∈S a s X s where

a s ∈ k. An element X s ∈ k[S] is called a monomial.
We use the letter M to denote a finite subset of Z n such that 0 ∈ M and the semigroup S M generated by M contains no nonzero invertible element. Also, we let S (h)

M denote the affine semigroup generated by {(α, 1) | α ∈ M} ⊂ Z n+1 . The semigroup algebra k[S (h) M ] is homogeneous ( i.e.
N-graded and generated by degree 1 elements): the degree of a monomial

X (s 1 ,...,sn,d) is d ∈ N. The vector space of homogeneous elements of degree d ∈ N in k[S (h) M ] is denoted by k[S (h) M ] d .
Depending on the articles on this topic, the condition "S contains no invertible element" is not always included in the definition of an affine semigroup. However, this is a necessary condition for the algorithms we propose in this paper. Also, the term "Hilbert basis" is sometimes reserved for affine semigroups of the form C ∩ Z n where C is a rational cone (see e.g. [START_REF] Miller | Combinatorial commutative algebra[END_REF]Prop. 7.15] and the discussion after this statement). We always assume implicitely that gp(S) ⊂ Z n is a full rank lattice (this does not lose any generality since this case can be reached by embedding S in a lower dimensional

Z n ′ ). Note that k[N n ] is the classical polynomial ring k[X 1 , . . . , X n ].
Semigroup algebras are integral domains [START_REF] Miller | Combinatorial commutative algebra[END_REF]Thm. 7.4] of Krull dimension n and play an important role in toric geometry: they are precisely the coordinate rings of affine toric varieties.

The normality of the semigroup S is an important property which implies that k[S] is Cohen-Macaulay by a theorem by Hochster [START_REF] Hochster | Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes[END_REF]. An important feature of normal affine semigroups is that they can be represented by the intersection of Z n with a pointed rational polyhedral cone (also called strongly convex rational polyhedral cone [25, Sec 1.1]). Definition 2.2. A cone C ⊂ R n is a convex subset of R n stable by multiplication by R + , the set of non-negative real numbers. The dimension dim(C ) of a cone C is the dimension of the linear subspace spanned by C . A cone is called pointed if it does not contain any line. A pointed cone of dimension 1 is called a ray. A ray is called rational if it contains a point in Z n . A rational polyhedral cone is the convex hull of a finite number of rational rays. Pointed rational polyhedral cones will be abbreviated PRPC.

We shall use PRPCs in Section 3 to define admissible monomial orderings in semigroup algebras. We now recall the definition of simplicial affine semigroups, for which we will be able to derive tight complexity bounds for the sparse-FGLM algorithm (Section 5). Definition 2.3. An affine semigroup S ⊂ Z n is called simplicial if the convex hull of R + S is a simplicial PRPC, i.e. the convex hull of n linearly independant rays.

Another important family of objects are projective toric varieties. Their homogeneous coordinate rings are associated to a lattice polytope, which we shall assume to be normal in order to ensure that the coordinate ring is Cohen-Macaulay. As in the classical case, homogeneity is a central concept to analyze the complexity of Gröbner bases algorithms. All lattice polytopes will be assumed to be full dimensional. Definition 2.4. A lattice polytope P ⊂ R n is the convex hull of a finite number of points in Z n . Its normalized volume, i.e. n! times its Euclidean volume, is denoted by vol(P) ∈ N. To a lattice polytope P ⊂ R n is associated an affine semigroup S (h)

P∩Z n ⊂ Z n+1 generated by {(α, 1) | α ∈ P ∩ Z n }. The polytope P is called normal if S (h)
P∩Z n is a normal semigroup. The associated semigroup algebra is called a polytopal algebra and abbreviated k[P].

If P ⊂ R n is a lattice polytope containing 0 as a vertex, then k[P] = k[S (h)
P∩Z n ] (Def. 2.1). Moreover, if P is normal, then so is S P∩Z n [8, Prop. 2.17]. Also, note that if P ′ is a translation of P, then the homogeneous algebras k[P] and k[P ′ ] are isomorphic. Consequently, we shall assume w.l.o.g. in the sequel that one of the vertices of P is the origin, so that M = P ∩ Z n verifies the assumptions of Def. 2.1. We also introduce a few more notations for lattice polytopes: Notation 2.5. The number of lattice points in a polytope P ⊂ R n ( i.e. the cardinality of P ∩ Z n ) is denoted by #P. The Minkowsky sum of two lattice polytopes P 1 , P 2 ⊂ R n is the lattice polytope {p 1 + p 2 | p 1 ∈ P 1 , p 2 ∈ P 2 }. For all ℓ ∈ N we write ℓ • P for the Minkowski sum P + • • • + P with ℓ summands. For n ∈ N, we let ∆ n ⊂ R n denote the standard simplex, namely the convex hull of 0 and of the points e i ∈ R n whose entries are zero except for the ith coefficient which is equal to 1. For P 1 ⊂ R i ,P 2 ⊂ R j we write P 1 × P 2 ⊂ R i+j for the lattice polytope whose points are

{(p 1 , p 2 ) | p 1 ∈ P 1 , p 2 ∈ P 2 }.
Next, we recall several useful classical properties of polytopal algebras. We refer to [24, Ch. 12] for a detailed presentation of the connections between Ehrhart theory and computational commutative algebra. Then the Hilbert series of the polytopal algebra k[P], namely

HS k[P] (t) = d∈N dim k (k[P] d )t d
is equal to HS P and there exists a polynomial Q ∈ Z[t] with non-negative coefficients such that We let reg(k[P]) denote the Castelnuovo-Mumford regularity of k[P]. The Castenuovo-Mumford regularity of a graded module is an important measure of its "complexity": it is related to the degrees where its local cohomology modules vanish. We refer to [START_REF] Brodmann | Local cohomology: an algebraic introduction with geometric applications[END_REF]Ch. 15] for a more detailed presentation. The following classical proposition relates the regularity with a combinatorial property of the polytope P and with the degree of the numerator of HS P :

HS P (t) = Q(t) (1 -t) n+1 , deg(Q) ≤ n.

Sparse Gröbner bases

In this section, we show that classical Gröbner bases algorithms extend to the context of semigroup algebras. First, we need to extend the notion of admissible monomial ordering and of Gröbner bases. We recall that the monomials of a semigroup algebra k[S] are the elements X s for s ∈ S. • it is compatible with the internal law of S: for any s 1 , s 2 , s 3 ∈ S, X s 1 ≺ X s 2 ⇒ X s 1 +s 3 ≺ X s 2 +s 3 ;

• for any s ∈ S \ {0}, X 0 ≺ X s .
For a fixed admissible ordering ≺ and for any element f ∈ k[S], we let LM(f ) denote its leading monomial. Similarly, for any ideal I ⊂ k[S], LM(I) denotes the ideal generated by

{LM(f ) | f ∈ I}. A finite subset G ⊂ I is called a sparse Gröbner basis (abbreviated sGB) of I with respect to ≺ if the set {LM(g) | g ∈ G} generates LM(I) in k[S].
Note that admissible orderings exist for any semigroup algebra: the convex hull of a semigroup S ⊂ Z n is a PRPC C ⊂ R n (this is a consequence of the fact that there is no nonconstant invertible monomial in k[S]). Now one can pick n independant linear forms (ℓ 1 , . . . , ℓ n ) with integer coefficients in the dual cone C * = {linear forms ℓ : R n → R | ∀x ∈ C , ℓ(x) ≥ 0}, and set X s 1 ≺ X s 2 if and only if the vector (ℓ 1 (s 1 ), . . . , ℓ n (s 1 )) is smaller than (ℓ 1 (s 2 ), . . . , ℓ n (s 2 )) for a classical admissible ordering on N n .

Note that the assumption that k[S] contains no nonconstant invertible monomial is a necessary and sufficient condition for the existence of an admissible ordering.

We describe now an algorithmic framework to solve sparse systems of Laurent polynomials. Let M ⊂ Z n be a finite subset verifying the assumptions of Definition 2.1, and

f 1 , . . . , f m ∈ k[X ±1
1 , . . . , X ±1 n ] be Laurent polynomials such that the supports of the

f i are included in {X α 1 1 • • • X αn n | α ∈ S M }.
Note that translating M amounts to multiplying the Laurent polynomials by Laurent monomials: this does not change the set of solutions of the system in the torus k \ {0}

n .

Assuming that the system

f 1 = • • • = f m = 0 has finitely-many solutions in (k \ {0}
) n , we proceed as follows:

1. homogenize (f 1 , . . . , f m ) via Def.-Prop. 3.3 (note that the homogenization depends on the choice of the (not necessarily minimal) generating set M;

2. compute a sparse Gröbner basis w.r.t. a graded ordering of the homogeneous ideal

I = f (h) 1 , . . . , f (h) m ⊂ k[S (h)
M ] by using a variant of F 4 /F 5 algorithm (Algo. 1).

3. dehomogenize the output to obtain a sGB of the ideal f 1 , . . . , f m ⊂ k[S M ] (Prop. 3.5);

4. use a sparse variant of FGLM to obtain a 0-dim. triangular system (hence containing a univariate polynomial) whose solutions are the image of the toric solutions of

f 1 = • • • = f m = 0 by monomial maps (Algo. 2);
5. compute the non-zero roots of the univariate polynomial and invert the monomial map to get the solutions.

We focus on the four first steps of this process. The fifth step involves computing the roots of a univariate polynomial, for which dedicated techniques exist and depend on the field k. It also involves inverting a monomial map, which can be achieved by solving a consistent linear system of # Hilb(S M ) equations in n unknowns.

In the sequel of this section, we investigate the behavior of sparse Gröbner bases under homogenization and dehomogeneization (Steps 1 and 3). We refer the reader to [8, Ch. 2] for geometrical aspects of projective toric varieties and their affine charts. If M verifies the assumptions of Def. 2.1, then there is a canonical dehomogenization map: Definition 3.2. With the notations of Def. 2.1, there is a dehomogeneization morphism χ M defined by

χ M : k[S (h) M ] → k[S M ] X (s,d) → X s Definition-Proposition 3.3. With the notations of Def. 2.1, for any f ∈ k[S M ], we call degree of f , the number deg(f ) = min{d ∈ N | χ -1 M (f ) ∩ k[S (h) M ] d = ∅}. Moreover the set χ -1 M (f ) ∩ k[S (h) M ] deg(f ) contains a unique element, called the homogenization of f . Proof. The only statement to prove is that χ -1 M (f ) ∩ k[S (h) M ] deg(f ) contains a unique element. Let f (h) 1 , f (h) 2 ∈ χ -1 M (f )∩k[S (h) M ] deg(f ) . Then χ M (f (h) 1 -f (h) 2 ) = 0, which implies f (h) 1 = f (h)
2 . The next step is to prove that dehomogenizing a homogeneous Gröbner basis (with respect to a graded ordering) gives a Gröbner basis of the dehomogenized ideal. Proof. First, notice that χ M commutes with leading monomials on homogeneous components of k[S

X (s 1 ,d 1 ) ≺ X (s 2 ,d 2 ) ⇔ d 1 < d 2 or d 1 = d 2 and X s 1 ≺ ′ X s 2
(h) M ]: for any f ∈ k[S (h) M ] d , χ M (LM(f )) = LM(χ M (f )). Let f ∈ χ M (I)
and f (h) ∈ I be a homogeneous polynomial such that f is equal to χ M (f (h) ). Consequently, there exists g ∈ G such that LM(g) divides LM(f (h) ). Applying χ M , we obtain that LM(χ M (g)) divides LM(χ M (f (h) )) = LM(f ). Therefore χ M (G) is a sGB of χ M (I) for the associated ordering.

Algorithms

Sparse-MatrixF5 algorithm

As pointed out in [START_REF] Lazard | Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations[END_REF], classical Gröbner bases algorithms are related to linear algebra via the Macaulay matrices. Since k[S (h) M ] is generated by elements of degree 1, the following proposition shows that similar matrices can be constructed in the case of semigroup algebras:

for i = 1 to m do case d i > d: M d,i := M d,i-1 ; case d i = d: M d,i :=add new row f i to M d,i-1 ; case d i < d: add new row X (s,d-d i ) f i to M d,i-1 for all monomials X (s,d-d i ) ∈ k[S (h) M ] d-d i that are not in LM(G i-1 ) ; Compute the row echelon form M d,i of M d,i ; Add to G i all rows of M d,i not top reducible by G i ; return G m

Sparse-FGLM algorithm

The FGLM algorithm and its variants might be seen as a tool to change the representation of a 0-dimensional ideal. It relies on the notion of normal form relative to an ideal I.

* ) n = V ar (ϕ -1 (I)) ∩ (k * ) r
, where ψ : k n → k r is the map x → (x p 1 , . . . , x pr ). Also, we would like to point out that Algorithm 2 does not depend on the support of the input sparse system, but only on the ambient semigroup S M . The main principle of Algorithm 2 is similar to the original FGLM Algorithm [START_REF] Faugère | Efficient Computation of Zerodimensional Gröbner Bases by Change of Ordering[END_REF]: we consider the monomials in k[H 1 , . . . , H r ] in increasing order until we obtain sufficiently many linear relations between their normal forms. The only difference is that the computations of the normal forms are performed in k[S] (using a previously computed sparse Gröbner basis) via the morphism ϕ. For solving sparse systems, we choose the lexicographical ordering for ≺ H . Theorem 4.7. Algorithm Sparse-FGLM is correct: it computes the reduced GB of the ideal

Algorithm 2: Sparse-FGLM Input : -a normal form NF: k[S] → k[S] of a 0-dim ideal I -a monomial ordering ≺ H on k[H 1 , . . . , H r ] -a monomial map ϕ : k[H 1 , . . . , H r ] → k[S] Output: A Gröbner basis in k[H 1 , . . . , H r ] w.r.t. ≺ H L := [1]; //list of monomials in k[H 1 , . . . , H r ] E := [ ]; //staircase for the new ordering ≺ H V := [ ]; //V = NF(ϕ(S)) G := [ ]; //The Gröbner basis in k[H 1 , . . . , H r ] while L = [ ] do m := L[1]; and Remove m from L; v := NF(ϕ(m)); (1) e
:= #E ; if v ∈ Span k (V ) then ∃ (λ i ) ∈ k e such that v = e i=1 λ i • V i ; (2)
G := G ∪ m - s i=1 λ i • E i ;
Remove from L the elements top-reducible by G. else

E := E ∪ [m]; V := RowEchelon(V ∪ [v]); (3)
L := Sort(L ∪ [H i m | i = 1, . . . , r] , ≺ H ); Remove from L duplicate elements; Return G; ϕ -1 (I) ⊂ k[H 1 , . . . , H r ] with respect to ≺ H .
Proof. Let G = (g 1 , . . . , g µ ) be the output of Algo. 2. Set m i = LM(g i ). First, we prove that G ⊂ ϕ -1 (I). Notice that each g i is of the form m iq, where ϕ(q) = NF(ϕ(m i )). Consequently, NF(ϕ(g i )) = 0 and hence g i ∈ ϕ -1 (I). Next, let h ∈ k[H] be a polynomial such that LM(h) / ∈ LM(G) . Up to reducing its nonleading monomials by G, we can assume w.l.o.g. that all its monomials do not belong to LM(G) . Therefore, the normal forms of the images by ϕ of all the monomials in the support of h are linearly independent in k[S]/I (otherwise the linear relation would have been detected by Algo. 2), which means that NF(ϕ(h)) = 0 and hence h / ∈ ϕ -1 (I), which proves that G is a Gröbner basis of ϕ -1 (I). The proof that G is reduced is similar.

Complexity

This section is devoted to the complexity of Algorithms 1 and 2 when the input is a homogeneous regular sequence. In the case of polytopal algebras, the complexity bounds of Theorems 5.3 and 5.4 depend mainly on the intrinsic combinatorial properties of the defining polytope.

Complexity model. All the complexity bounds count the number of arithmetic operations {+, ×, -, ÷} in k; each of them is counted with unit cost. It is not our goal to take into account operations in the semigroup S.

The first goal is to bound d wit (see DefProp. 4.4) via the Hilbert series of k[S]/I. For regular sequences, this Hilbert series can be computed by the following classical formula: Proposition 5.1. Let P be a normal lattice polytope, f 1 , . . . , f p ∈ k[P] be a homogeneous regular sequence of homogeneous polynomials of respective degrees (d 1 , . . . , d p ) and

I = f 1 , . . . , f p ⊂ k[P]. Then HS k[P]/I (t) = HS P (t) • p i=1 (1 -t d i ).
Proof. See e.g. [START_REF] Eisenbud | Commutative Algebra: with a view toward algebraic geometry[END_REF]Exercise 21.17b].

The next lemma gives an explicit bound for the witness degree of regular sequences in a normal polytopal algebra: Proof. Once the r matrices of size δ×δ representing the multiplications by p i in the canonical monomial basis of k[S]/I are known, Step (1) in Algorithm 2 can be achieved in O(δ 2 ) as in the classical FGLM Algorithm [START_REF] Faugère | Efficient Computation of Zerodimensional Gröbner Bases by Change of Ordering[END_REF]. Steps (2) and (3) are done by linear algebra as in [START_REF] Faugère | Efficient Computation of Zerodimensional Gröbner Bases by Change of Ordering[END_REF], which leads to a total complexity of O(r • δ 3 ) since the same analysis holds. It remains to prove that the multiplication matrices can be constructed in O(r • δ 3 ) operations (this is a consequence of [START_REF] Faugère | Efficient Computation of Zerodimensional Gröbner Bases by Change of Ordering[END_REF]Prop. 2.1] in the classical case). Since k[S] is Cohen-Macaulay and S is simplicial, we obtain by [START_REF] Rosales | On Cohen-Macaulay and Gorenstein simplicial affine semigroups[END_REF]Thm. 1.1] that for any two distinct p i , p j ∈ Hilb(S) and for any s ∈ S, if sp i and sp j are in S then sp ip j ∈ S. With this extra property, the proof of [15, Prop. 2.1] extends to semigroup algebras. If the input system is a regular sequence of Laurent polynomials, then δ can be bounded by the mixed volume of their Newton polytopes by Kushnirenko-Bernstein's Theorem [START_REF] Bernstein | The number of roots of a system of equations[END_REF].

6 Dense, multi-homogeneous and overdetermined systems

In this section, we specialize Theorems 5.3 and 5.4 to several semigroups to obtain new results on the complexity of solving inhomogeneous systems with classical GB algorithms (P is the standard simplex), multi-homogeneous systems (P is a product of simplices) and we state a variant of Fröberg's conjecture for overdetermined sparse systems. Inhomogeneous dense systems. If P = ∆ n is the standard simplex in R n , then computations of a sparse Gröbner basis in the cone over ∆ n correspond to classical Gröbner bases computations using the so-called "sugar strategy" introduced in [START_REF] Giovini | One sugar cube, please" or selection strategies in the Buchberger algorithm[END_REF]. The following corollary shows that specializing Theorems 5.3 and 5.4 with P = ∆ n recovers the usual complexity estimates for Gröbner bases computations Corollary 6.1. Let f 1 , . . . , f n be a regular sequence of polynomials of respective degrees

(d 1 , . . . , d n ) in k[∆ n ].
Then the complexity of computing a classical Gröbner basis of f 1 , . . . , f n with respect to a graded monomial ordering is bounded by

O n n + d wit n ω ,
where d wit ≤ 1 + n i=1 (d i -1). In particular, notice that if f 1 , . . . , f n are inhomogeneous polynomials in k[X 1 , . . . , X n ], then their homogeneous counterparts in k[∆ n ] form a regular sequence if and only if their "classical homogenization" form a regular sequence.

Multi-homogeneous systems. Another class of polynomials appearing frequently in applications are multi-homogeneous systems. A polynomial of multi-degree (d 1 , . . . , d ℓ ) w.r.t. a partition of the variables in blocks of sizes (n 1 , . . . , n ℓ ) is a polynomial whose Newton polytope is included in d

1 ∆ n 1 × • • • × d ℓ ∆ n ℓ .
In that case, the associated polytope is a product of simplices, which allows us to state the following complexity theorem: Theorem 6.2. Let f 1 , . . . , f n be a regular sequence of polynomials of multi-degree (d 1 , . . . , d ℓ ) w.r.t. a partition of the variables in blocks of sizes (n 1 , . . . , n ℓ ) (with n 1 +• • •+n ℓ = n). Then the combined complexity of Steps (1) to (4) of the solving process in Section 3 is bounded by O (n HP P (d wit ) ω + n vol(P) 3 ) , where

P = d 1 ∆ n 1 × • • • × d ℓ ∆ n ℓ , d wit ≤ n + 2 -max i∈{1,...,ℓ} (⌈(n i + 1)/d i ⌉), HP P (d wit ) = n 1 +d wit •d 1 n 1 • • • n ℓ +d wit •d ℓ n ℓ ,
]) = n + 1 -max(⌈(n 1 + 1)/d 1 ⌉, . . . , ⌈(n ℓ + 1)/d ℓ ⌉). Since the f 1 , . . . , f n have degree 1 in k[P], we get d wit ≤ reg(k[P]) + 1.
Finally, notice that the unnormalized volume of d∆ q ∈ R q is d q /q!. Consequently, the unnormalized volume of P is ℓ i=1 d n i i /n i !. Normalizing the volume amounts to multiplying this value by n!, which yields the formula for vol(P) and equals the multi-homogeneous Bézout number. The number of solutions (counted with multiplicity) is classically bounded by this value and hence δ ≤ vol(P).

Finally, we state a variant of Fröberg's conjecture [START_REF] Fröberg | An inequality for Hilbert series of graded algebras[END_REF] in the sparse framework, leading to a notion of "sparse semi-regularity". It provides a bound on the witness degree of generic overdetermined sparse systems: this conjecture can be used to adjust the parameter D of Algorithm 1.

HS C[P]/ f 1 ,...,fm (t) = HS P (t) m i=1 (1 -t d i ) + ,
where [ ] + means truncating the series expansion at its first nonpositive coefficient. Systems for which this equality holds are called semi-regular. The witness degree of a semi-regular sequence is bounded above by the index of the first zero coefficient in the series expansion of HS C[P]/ f 1 ,...,fm (t).

(n x , n y , m) sp-MatrixF5 FGb-F5 Speed-up (2,29,

Experimental results

In this section, we estimate the speed-up that one can expect for solving sparse systems or systems of Laurent polynomials via sparse Gröbner bases computations, compared to classical Gröbner bases algorithms. The same linear algebra routines are used in the compared implementations. Consequently, the speed-up reflects the differences between the characteristics (size, sparseness,. . . ) of the matrices that have to be reduced. Workstation. All experiments have been conducted on a 2.6GHz IntelCore i7.

We compare sparse-MatrixF5 (abbreviated sp-MatrixF5) with the implementation of the F 5 algorithm in the FGb library. We report more detailed experimental results on a benchmarks' webpage 1 . In all these experiments, the base field k is the finite field GF(65521). All tests are done with overdetermined systems with one rational solution in GF(65521) n . The goal is to recover this solution. In that case, the FGLM algorithm is not necessary since the sparse Gröbner basis describes explicitly the image of the solution by a monomial map. In several settings, we report the speed-up obtained with our prototype implementation.

Bilinear systems. In Table 1, we focus on overdetermined bilinear systems. For (n x , n y , m) ∈ N 3 , we generate a system of m polynomials with support ∆ nx × ∆ ny uniformly at random in the set of such systems which have at least one solution in GF(65521) nx+ny .

Systems of bidegree (2, 1). In Table 2, we report the performances on overdetermined systems with support 2∆ nx × ∆ ny . Note that we obtain important speed-ups when n x < n y (more than 19000 for (n x , n y , m) = [START_REF] Brickenstein | Slimgb: Gröbner bases with slim polynomials[END_REF][START_REF] Ehrhart | Sur les polyèdres rationnels homothétiques à n dimensions[END_REF][START_REF] Miller | Combinatorial commutative algebra[END_REF]).

Fewnomial systems. In Table 3, we report performances on fewnomial systems. The complexity analysis in Section 5 do not apply to this context because the semigroup algebra in which we compute is not normal. However, the correctness of the algorithms still holds. The systems are generated as follows: for (n, t, m) ∈ N 3 we pick t monomials of degree 2 in n variables uniformly at random and we generate a system of m polynomials with this support in GF(65521)[X 1 , . . . , X n ] with random coefficients such that there is at least one solution in GF(65521) n . The computations are done w.r.t. the semigroup generated by the t monomials. Note that for some specific instances, the speed-up factor can be as high as 16800.

(n x , n y , m) sp-MatrixF5 FGb-F5 Speed-up [START_REF] Bardet | On the complexity of the F5 Gröbner basis algorithm[END_REF]34,36) 0

  e. a vertex which is the intersection of n facets), then the sparse-FGLM algorithm executes at most O   HP P (1) vol(P)

Proposition 2 . 6 .

 26 Let P ⊂ R n be a lattice polytope. For d ∈ N, we let HP P ∈ Q[d] denote the Ehrhart polynomial of P, i.e. HP P (d) = #(d • P). Also, let HS P (t) ∈ Z[[t]] denote the generating series HS P (t) = d∈N HP P (d)t d .

  Proof. The fact that the map HP P : d → #(d • P) is polynomial is a classical result by Ehrhart[START_REF] Ehrhart | Sur les polyèdres rationnels homothétiques à n dimensions[END_REF]. The second statement HS P = HS k[P] follows from the definition of k[P]. The last statement is Stanley's non-negativity theorem [28, Thm. 2.1].

Proposition 2 . 7 .

 27 Let P be a normal lattice polytope. The regularity reg(k[P]) equals nℓ + 1, where ℓ is the smallest integer such that ℓ • P contains an integer point in its interior. Moreover, with the same notations as in Proposition 2.6, deg(Q) = reg(k[P]). Proof. The first claim follows from [5, Sec. 5.4]. To prove the second claim, we use the partial fraction expansion of HS P which is of the form n+1 ℓ=n+1-deg(Q) a ℓ (1-t) ℓ with a n+1-deg(Q) = 0. Then we obtain the equality HP P (d) = n+1 ℓ=n+1-deg(Q) a ℓ (ℓ-1)! ℓ-1 j=1 (d + j), and hence d = ndeg(Q) + 1 is the smallest positive integer such that HP P (-d) = 0. The Ehrhart-MacDonald reciprocity [23] concludes the proof.

Definition 3 . 1 .

 31 Let S be an affine semigroup. A total ordering on the monomials of k[S] is called admissible if

Definition 3 . 4 .

 34 An admissible monomial ordering ≺ on k[S (h) M ] is called graded if there exists an associated ordering ≺ ′ on k[S M ] such that

Proposition 3 . 5 .

 35 Let G be an homogeneous sGB of an homogeneous ideal I ⊂ k[S (h) M ] with respect to a graded ordering. Then χ M (G) is a sGB of χ M (I) with respect to the associated ordering on k[S M ].

Proposition 4 . 1 .

 41 Any monomial of degree d in k[S (h) M ] is equal to a product of a monomial of degree d -1 by a monomial of degree 1. With the notations of Def. 2.1, k[S (h) M ] has the following property: for any f 1 ∈ k[S (h) M ] d , and for all ℓ ≥ d, there exists f 2 ∈ k[S (h) M ] ℓ s.t. χ M (f 1 ) = χ M (f 2 ). This leads to the following definition of a D-Gröbner basis: Definition 4.2. Let I ⊂ k[S (h) M ] be a homogeneous ideal and ≺ be an admissible monomial ordering on k[S M ]. Then a finite subset G ⊂ I is called a D-sGB of I if for any homogeneous polynomial f ∈ I with deg(f ) ≤ D, there exists g ∈ G such that LM(g) divides LM(f ). Note that for any D ∈ N there always exists a homogeneous D-sGB of I. A D-sGB of I can be deduced from a row echelon basis of the k-vector space I ∩ k[S (h) M ] D , and can be computed via the Macaulay matrix: Algorithm 1: sparse-MatrixF5 Input : Homogeneous f 1 , . . . , f m ∈ k[S (h) M ] of resp. degrees (d 1 , . . . , d m ), a graded monomial ordering ≺ on k[S (h) M ], a maximal degree D Output: a D-Gröbner basis of f 1 , . . . , f m w.r.t. ≺ for i = 1 to m do G i := ∅ ; for d = 1 to D do M d,0 := ∅, M d,0 := ∅;

  A normal form relative to I is a k-linear map NF : k[S] → k[S] whose kernel is ker(NF) = I. It sends every coset of I to the same representative, allowing effective computations in the ring k[S]/I. One important feature of a sparse Gröbner basis is that it provides a normal form and an algorithm to compute it by successive reductions of leading monomials. Let (p 1 , . . . , p r ) be the Hilbert basis of a semigroup S ⊂ Z n . Given new indeterminates H = {H 1 , . . . , H r }, any monomial in k[S] is the image of a monomial in k[H] via the morphism ϕ : k[H 1 , . . . , H r ] → k[S] defined by ϕ(H i ) = X p i . Given an admissible monomial ordering ≺ H on the ring k[H 1 , . . . , H r ], an ideal I ⊂ k[S] and a normal form relative to I (given for instance by a sparse Gröbner basis of I), Algorithm 2 computes a Gröbner basis of ϕ -1 (I). Note that ψ V ar(I) ∩ (k

Lemma 5 . 2 .Theorem 5 . 4 .

 5254 Let P ⊂ R n be a normal lattice polytope and f 1 , . . . , f n be a homogeneous regular sequence in k[P] of degrees (d 1 , . . . , d n ). Then any reg(k[P]) + 1 + n j=1 (d j -1) -sGB of the ideal I = f 1 , . . . , f n is a sGB of I. In other words d wit ≤ reg(k[P]) + 1 + n j=1 (d j -1). Set δ = dim k (k[S]/I) and let r be the cardinality of the Hilbert basis of S. If the input normal form is computed via a reduced sGB of I ⊂ k[S] (for some monomial ordering), S is a simplicial affine semigroup (see Def. 2.3) and k[S] is Cohen-Macaulay, then Algorithm 2 computes the Gröbner basis G with at most O(r • δ 3 ) operations in k.

Conjecture 6 . 3 .

 63 Let P ⊂ R n be a normal lattice polytope, (d 1 , . . . , d m ) ∈ N m be a sequence of integers with m > n. If f 1 , . . . , f m ∈ C[P] are generic homogeneous polynomials of respective degrees (d 1 , . . . , d m ), then

  Applying Theorems 5.3 and 5.4 with P equal tod 1 ∆ n 1 × • • • × d ℓ ∆ n ℓyields the complexity bound in terms of d wit , # Hilb(S P∩Z n ) and δ. First, notice that the semigroup generated by P ∩ Z n is N n , and hence # Hilb(S P∩Z n ) = n. Next, β(d 1 ∆ n 1 × • • • × d ℓ ∆ n ℓ )has an interior lattice point if and only if for all i, βd i ∆ n i has an interior lattice point, i.e. βd

	and vol(P) =	n n 1 ,...,n ℓ	ℓ i=1 d n i i .
	Proof.

i > n i . The smallest β that verifies this condition is max(⌈(n 1 + 1)/d 1 ⌉, . . . , ⌈(n ℓ + 1)/d ℓ ⌉). By Prop. 2.7, reg(k[P

Table 1 :

 1 Overdetermined bilinear systems in (n x , n y ) variables and m equations

	40)	0.12s	5.2s	43
	(2,39,53)	0.49s	36.7s	74
	(2,49,65)	1.53s	298.5s	195
	(2,59,78)	4.63s	852.3s	184
	(6,19,52)	1.10s	25.2s	22
	(6,21,56)	2.13s	51.5s	24
	(6,27,71)	7.07s	236.0s	33

Table 2 :

 2 Systems in (n x , n y ) variables of bidegree (2, 1) and m equations

		.2s	395.1s	1975
	(1,39,41)	0.45s	1641s	3646
	(1,44,46)	0.75s	3168.8s	4225
	(2,15,25)	0.09s	410.1s	4556
	(2,17,27)	0.15s	1894.7s	12631
	(2,19,30)	0.4s	5866.1s	14665
	(3,10,24)	0.15s	2937.7s	19584
	(10,4,50)	23.1s	1687.3s	73
	(11,5,66)	155.1s	6265.8s	40
	(12,6,86)	872.2s	27093.3s	31
	(n, t, m)	sp-MatrixF5 FGb-F5 Speed-up
	(80,240,221)	0.10s	54.5s	545
	(80, 240, 223)	0.08s	16.3s	203
	(150, 450, 434)	0.24s	161.2s	671
	(300, 900, 881)	4.56s	11301.0s	2478
	(120, 240, 233)	0.01s	16.8s	16800
	(40, 160, 128)	0.21s	5.93s	28
	(60, 240, 211)	0.55s	29.04s	52

Table 3 :

 3 Fewnomials systems

http://www-polsys.lip6.fr/ ~jcf/Software/benchssparse.html

). Rows are indexed by the products X (s,d-deg(f i )) • f i where X (s,d-deg

Columns are indexed by monomials of degree d and are sorted in decreasing order w.r.t. an admissible monomial ordering. The entry at the intersection of the row X (s,d-deg(f i )) • f i and the column

By a slight abuse of notation, we identify implicitely a row in the Macaulay matrix of degree d with the corresponding polynomial in k[S (h) M ] d . The relation between the Macaulay matrix and a D-sGB is given by:

M ] be homogeneous polynomials, ≺ a graded monomial ordering, and for d ∈ N, let G d be the set of polynomials corresponding to the rows of the reduced row echelon form of the Macaulay matrix in degree d of f 1 , . . . f m . Then we have for any

As in the original F 5 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF], many lines are reduced to 0 during row-echelon form computations of Macaulay matrices. The F 5 criterion [START_REF] Eder | A survey on signature-based Gröbner basis computations[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF][1, Prop. 6] extends without any major difficulty in this context and identifies all reductions to zero when the input system is a regular sequence in k[S (h) M ]: Lemma 4.5 (F 5 -criterion). With the notations of Algorithm 1, if m is the leading monomial of a row in M d-d i ,i-1 then the polynomial mf i belongs to the vector space

A direct consequence of this lemma is:

Proof. With the notations of Algo. 1 A direct induction on d and i with Lemma 4.5 shows that the row span of M d,i is equal to the row span of the Macaulay matrix in degree d of (f 1 , . . . , f i ). DefProp. 4.4 concludes the proof.

In practice, the choice of the parameter D in Algorithm 1 is driven by the explicit bounds on the witness degree that we shall derive in Section 5.

Proof. By Prop. 5.1 and with the notations of Prop. 2.6, the Hilbert series of k[P]/I is equal to

where

. Now, notice that the Hilbert series of k[P]/I is equal to that of k[P]/ LM(I). Therefore HP k

Consequently, minimal generators of LM(I) and hence minimal homogeneous Gröbner bases of I have degree at most deg(K(t)) + 2 = reg(k[P]) + 1 + n j=1 (d j -1). Now that we have an upper bound for the witness degree, we can estimate the cost of computing a sGB by reducing the Macaulay matrix in degree d wit (although sparse-MatrixF5 is a much faster way to compute a sGB in practice, it is not easy to bound precisely its complexity). Note that reg(k[P]) in the following theorem can be deduced from Prop. 2.7.


Han Yan
email: han.yan@irisa.frhan.yan

Bernard Cousin
email: bernard.cousin@irisa.frhan.yan

Cédric Gueguen
email: cedric.gueguen@irisa.frhan.yan

Jean-Paul Vuichard
email: jeanpaul.vuichard@orange.com

Refined Overlay Power Management in the Home Environment

Keywords: Home network, Energy saving, Green networking, Overlay control network, Low Power

The reduction of power consumption plays a key role in numerous environmental and economic issues. Since home network appliances are widely used, residential power consumption makes up a large part of global energy consumption. These home appliances are not only interconnected with each other to provide collaborative services, but are also integrally turned on to contribute to these collaborative services. Faced with this situation, we propose a refined overlay power management system in which appliances can be partially turned on depending on the services, and can be turned on at the moment they are required. In addition, user activities are critical information for the service launch, and so the proposed system has the capacity to learn information about the collaborative service in order to provide efficient power management.

I. INTRODUCTION

In the last decade, many home network devices with exploding power consumption have appeared in our homes. A home network is a complex environment which contains several different types of devices, such as a Set-Top Box (STB), Home GateWay (HGW), workstation, laptop, power line communication plugs and so on, with different kinds of connections, such as Wifi, Ethernet and Powerline communication [START_REF] Rose | Home networks: a standards perspective[END_REF].

Energy saving is recognized as a key issue in global warming and climate change. According to the recent report of the European Commission, Eurostat, there are three dominant energy consumption categories: transport, household and industry. Household energy consumption increased to 26.7% [START_REF] Eurostat | Consumption of energy[END_REF] of total energy consumption in 2010 and this category of energy consumption is greater than industry energy consumption. Furthermore, the price of electricity is constantly increasing, with European residential electricity prices increasing on average 2% faster than inflation in 2012. The largest price increases from 2012 to 2013 were observed in Romania (26%) and in Estonia (23%) [START_REF]European residential energy pricing report 2013[END_REF]. It is therefore crucial to reduce energy consumption in home environments.

One challenge is that, in home environments, there has been a proliferation of connected devices and the number of connected devices has led to a sharp increase in energy consumption in the home. With a large number of different kinds of appliances in a home network, such as HGW, STB, network attached storage, computer, etc., household energy saving should take these different connected appliances and their different usages into account.

In the literature, several techniques have been proposed to reduce energy consumption at the device level. Using dynamic power management [START_REF] Benini | A survey of design techniques for system-level dynamic power management[END_REF] [START_REF] Chung | Dynamic power management for non-stationary service requests[END_REF], devices can be switched to a lower power mode when the service demand is reduced. In addition, several algorithms have been proposed to minimize the energy consumption of device components. For instance, Maruti proposed a method that reduces the power supply when there is less traffic over Ethernet links [START_REF] Maruti | Dynamic ethernet link shutdown for energy conservation on ethernet links[END_REF], and there are other proposals which aim to control the memory in order to be more power efficient [START_REF] Khargharia | An adaptive interleaving technique for memory performance-per-watt management[END_REF] [START_REF] Fan | Memory controller policies for dram power management[END_REF]. It is not sufficient, however, to save energy only at the level of each individual device. The power statuses of home devices are interdependent. For example, when all family devices are not operational or not in use, it can be concluded that the home gateway does not need to provide a local network, and its Ethernet and WiFi components can be turned off. The activity or power status of one appliance is not independent information; this information can be used to manage other appliances. Consequently, our solution provides a collaborative system to control the power status of home connected devices at the network level and the power states of functional blocks in these collaborative devices at the device level.

In earlier works, Youn-Kwae Jeong et al. proposed a solution that controls home network devices by reconfiguring the power control element (PCE). Their proposed solution only supplies power to the devices and the functional elements that are related to requested services [START_REF] Jeong | A network level power management for home network devices[END_REF]. In their approach, all functional elements are turned on at the beginning of the service, despite the fact that early functional modules are not needed at that time. The UPnP AV use case [START_REF] Ritchie | UPnP AV Architecture:1, The UPnP forum Std[END_REF] can be a good example to explain why there is a time lapse between requested functional blocks in one service: the user controls the home devices with an UPnP Control Point (smart-phone, iPad or other Tablet) and wants to watch a film on his UPnP Media Renderer (STB). This film is saved on his UPnP Media Server (PC). For this service, the content directory functional block on the UPnP Media Server is needed at the beginning of the service. The decoder functional block on the UPnP Media Renderer is required later by the service. Another challenge is that user satisfaction is an important factor in the home network energy control system. There are two important and relevant user parameters: energy cost and waiting delay. In the literature, PCE power management focuses on the energy cost saving solution without considering user satisfaction. In addition to these energy saving management prototypes, there is an increasing interest in taking into the consideration the waiting delay of each solution, because users need to know the impact of the waiting delay on their service experience before choosing an energy efficient solution. Moreover, different users have different requirements: some prefer to be more energy efficient, some do not want their service experience to be affected, and some want both. Therefore, measuring the delay is important information when proposing a power management solution.

A final challenge is that, in order to be power-efficient and reactive to user demand, the solution should be able to control any device at any time. This requires an always-on connection. In order to ensure power management, the solution proposed by Youn-Kwae Jeong et al. needs a permanent connection (Ethernet or WiFi) which is said to consume more than 1 Watt. Unlike earlier power management solutions which need to maintain a WiFi connection or an Ethernet connection, in our former works [START_REF] Yan | Green Home Network based on an Overlay Energy Control Network[END_REF] [12], we proposed a low power overlay network for the centralized monitoring and control of home network devices by using the following technologies: ZigBee [START_REF] Farahani | ZigBee Wireless Networks and Transceivers[END_REF], UPnP network [START_REF]UPnP Low Power Architecture, The UPnP forum Std[END_REF], 6LowPan [START_REF] Hui | Extending ip to low-power, wireless personal area networks[END_REF], and Bluetooth low energy [START_REF] Mackensen | Bluetooth low energy (ble) based wireless sensors[END_REF]. These can be considered for an infrastructure of a green overlay control network. Home connected appliances can nowadays be turned on by a command from Wakeup on USB [START_REF] Flannery | Method and apparatus of providing power management a self-powered universal serial bus (usb) device[END_REF] or Wake on LAN (WoL) [START_REF] Ryu | Method and apparatus for controlling power of computer system using wake up lan (local area network) signal[END_REF]. The main contributions of our refined overlay user-aware efficient power management are: 1) Control of the appliances based on the analysis of the collaborative services which require different functional blocks in different devices. This model helps users to achieve more efficient energy consumption management.

2) Delay measurement based on each service demand. This helps to evaluate the impact of the home network user on the QoS. 3) The uses of an overlay power management network which could be implemented using specific lower power LAN technology, if available.

The rest of the paper is organized as follows. Section II. describes our refined overlay power management. Section III. presents the service pattern, the power consumption model and the delay model. Section IV. presents the setup of the simulation. Section V. analyzes the results of the simulation. Section VI. draws conclusions from our work.

II. THE PROPOSED REFINED OVERLAY ENERGY CONTROL POWER MANAGEMENT

In this section, we detail the refined overlay control system which is composed of the power management; the low energy overlay control network; and the refined home network connected devices. Based on this system, we propose two solutions: the Refined Overlay Power Management and the Refined Overlay Auto Learning power management.

A. The refined overlay control system

The proposed system has a power management which controls the functional blocks of devices by sending control messages over a low power overlay network as shown in Fig. 1 (below).

1) Power management:

The power management comprises a database and a decision algorithm entity. The database is used to store records of user habits when they use the services. When the service is requested for the first time, the database gathers the information relating to the user request services in order to learn the habits of this family and the information relating to the family user reaction. According to the information that is collected by the system, the power management makes the decisions to control the device with fine granularity. The granularity of the control is said to be fine because the control can turn on/off the functional blocks which are necessary for the collaborative service at the point at which they are requested. We assume each home network collaborative service involves one or more devices which cooperate together in order to meet the service demand of the family. 2) Refined network connect devices: In our proposal, we do not only assume that collaborative services involve several devices, but also that each device is refined into one or more functional blocks. At the function level, devices are used as the Functional Blocks (FB) which are needed in different services. In Fig. 1 (above), FB 1, 2, 3 in device 1 and FB 1, 2, 3, 4 in device 2 are requested in service 1. We note that the FB 2 is shared by two services.

Taking the same example of the UPnP AV use case, the user uses his UPnP Control Point (tablet) to search for a film which is saved on the UPnP Media Server (PC) in order to watch it on the UPnP Media Renderer (STB). In order to search for the film, the user firstly needs the connection between PC and his tablet to be guaranteed by the HGW. Then, when the user has found the film saved on the PC, the STB should be turned on in order to play the film. The STB provides its display interface block, video stream decoder block, authentication block and the connection block, and the HGW assures the connection block during the entire service. This typical UPnP AV use case requires different connected devices to participate at different points in the service. When the user decides to start the service, according to the information saved about this service, the power management sends control messages to each device as they are required. The request moment information can be pre-saved by the user or the device manufacturer in the power management, or by a process of auto-learning in the power management. With the refined system, only the required components are turned on, and the components which are no longer needed when the service is terminated are turned off.

3) Low energy communication overlay network: On each home network device, we propose an overlay low energy network by considering the characteristics of the device. The control message can be sent via ZigBee, Bluetooth Low Energy (BLE) or a UPnP low consumption network, depending on the capacity of the device. For example, it is possible that a new generation tablet will be equipped with BLE instead of having to add a ZigBee dongle to this tablet. The power consumption of a ZigBee module or BLE chipset is about a few milliwatts, which is much less than that of an Ethernet or WiFi network card which consume about 1.5 Watt. In our system, we assume that the refined power control messages will be sent by a ZigBee or BLE module in order to ensure a low-power and always-on network.

B. Refined Overlay Power Management & Refined Overlay Auto-Learning Power management

Our first proposition is the Refined Overlay Power Management (ROPM). Based on refined power control management, this proposal takes into consideration the fact that the refined power management system already has pre loaded information about the different services. The information indicates an average time lapse of each functional block for each service. The time lapse D time-lapse of a device functional block for a service is the time between the beginning of the service until the time when the functional block is requested. This average time lapse is a average value of user behavior for this service, and it cannot be exactly the same as user behavior. Indeed, the ROPM algorithm may turn on the functional blocks early or late. If the ROPM turns the functional blocks on early, the functional blocks will stay on until actually needed. Otherwise, if the control decision is too late compared to the actual need, the functional blocks will be turned on immediately after the ROPM detects the request by using technologies like tsocks. Tsocks is a library which transparently enables interception of outgoing messages. If the ROPM detects that the functional blocks are required, it will turn the functional blocks on immediately and ignore the decision which is too late.

Our second proposed solution is the Refined Overlay Auto-Learning power management (ROAL). It is not always possible to assume that the power management has an existing and perfect knowledge of user behaviors or device and service usages. Thus, it is difficult to predict the time when a functional block should be turned on. Therefore, we propose the Refined Overlay Auto-Learning power management (ROAL), which is able to learn when to turn the functional blocks on. When a service is launched for the first time, the ROAL turns on all the functional blocks which are necessary for the first service launch. During service execution, the ROAL gathers the information of when the functional blocks are actually requested, compares this gathered value to the saved information relating to former executions of this service, and calculates the average time lapse for each functional block: D AL-time-lapse . ENERGY AND DELAY MODELS In this section, we describe our service and device patterns and the models of our energy and delay calculations.

A. Service and function block patterns

A typical collaborative service pattern, which occurs repeatedly, within two devices is shown in Fig. 2 (below). Our notation is in TABLE 1. In Fig. 2 there are two instances of this service pattern (k = 1 to 2). Each service instance requires four Functional Blocks F B(j = 1 to 4) of device i = 1, and for device i = 2, the service requires three of its F B(j = 1 to 3). The moment t request (i, j, k) defines that F B(i, j) has been requested in the k t h service instance. The duration D utilization (i, j, k) defines the utilization duration of F B(i, j) in the k t h service instance. The duration D time-lapse (i, j, k) defines the interval time between the request of the F B(i, j) required later and the beginning of the k t h service. The inter arrival time between k t hand (k + 1) t hservice instances is defined as D ser-inter-arrival (k).

Fig. 2. A service pattern example

We assume that the duration of the service inter arrival follows an exponential distribution, the mean value of which is D service-inter-arrival (k) as described in formula (1) (below). In formula (2), the real value of each D time-lapse (i, j, k) follows an exponential distribution, the standard deviation of which is 1 λ0(i,j,k) and the mean value of which is D time-lapse (i, j, k) . The standard deviation

1 λ0(i,j,k)
describes user behavior which may turn on the F B(i, j) more or less early or late around the time of the 1 λ0(i,j,k) in the k t h service, with a standard deviation 1 λ0 . The duration of the utilization of each functional block also follows an exponential distribution, the mean value of which is D utilization (i, j, k) as described in formula [START_REF]European residential energy pricing report 2013[END_REF].

D ser-inter-arrival (k) = exp( 1
D service-inter-arrival (k) ) (1)
D time-lapse (i, j, k) = t request (i = 1, j, k) -t request (i, j, k) = exp(λ 0 (i, j, k)) - 1 λ 0 (i, j, k) + D time-lapse (i, j, k) (2)
D utilization (i, j, k) = exp( 1
D utilization (i, j, k) ) (3)
Fig. 3.(a) shows the FB pattern during the service. The t dec-on (i, j, k) is the moment that FB(i,j) receives a decision to be turned on. The D starting (i, j)defines the necessary starting time before F B(i, j) is operational. The t available (i, j, k) is the moment that F B(i, j) is available in the service(k). If the moment t available (i, j, k) comes before the t request (i, j, k), this means that F B(i, j) has a period of no activity where D no-activity (i, j, k) = t request (i, j, k)t available (i, j, k). On the contrary, as shown in Fig. 3.(b), if the t request (i, j, k) comes before the moment t available (i, j, k), F B(i, j) will start the service execution immediately upon becoming available without having a no-activity period. The duration of utilization of F B(i, j) in service(k) is the duration of utilization D utilization (i, j, k) as explained in the service pattern.

B. Energy and delay models

The energy consumption of service(k) can be calculated using the following formula (4):

E(k) = N b d n i=1 N b f d j=1 P F B (i, j) × D on (i, j, k) (4)
Where the D on (i, j, k) is the on duration of the functional block in formula [START_REF] Chung | Dynamic power management for non-stationary service requests[END_REF], which is composed of the starting duration, the utilization duration and the no-activity duration which may be 0 in the event that service request t request (i, j, k) is earlier than the FB being available at t available (i, j, k), as explained in the FB pattern.

D on (i, j, k) = t pm dec-on (i, j, k) -t pm dec-of f (i, j, k) (5)
The Delay(k) is the total waiting time for the service(k), described in formula [START_REF] Maruti | Dynamic ethernet link shutdown for energy conservation on ethernet links[END_REF]. There are two cases: if the F B(i, j) is available ( t available (i, j, k)) before the arrival of the service request t request (i, j, k), there is no waiting time for the user.

Thus, the delay is nil in this case. Otherwise, if the service request arrives before the FB is available, the waiting time is the period from the t request (i, j, k) to the t available (i, j, k).

The delay is the difference between these two moments.

Delay(k) = N b d n i=1 N b f d j=1 { 0, t request (i, j, k) < t available (i, j, k) t request (i, j, k) -t available (i, j, k), else (6)
After modeling our service patterns, function block patterns, and energy and delay calculations, we will apply our ROPM and ROAL propositions and other power management systems to the model.

IV. POWER MANAGEMENT MODELING

In this section, we firstly describe our two propositions and two usual solutions as comparisons.

A. User control power management

We assume that without the help of technology, users control all their home network devices manually and individually for energy saving: they turn the device on when they need it and they turn the device off at the end of the utilization. The main inconveniences are that the user needs to wait for the functional block starting time (which includes component lighting time, booting time, etc.) and that when the device is turned on, all included F B(1 to N b d F B ) are turned on integrally. Formula (7) defines the decision of turning on the F B(i, j) in service(k) made by the user control power management.

t user-control dec-on (i, j, k) = t request (i, j, k) (7)
The service is requested at the same moment that the user decides to turn the device on. Since F B(i, j) is always available after the service request, the duration D on (i, j, k) of the F B(i, j) is composed of D starting and D utilization . At the end of the service, the user will turn off the device manually. The main inconvenience is that it is not automatic and could be tedious for users. Secondly, users may not think ahead and therefore have to wait for the starting time of each FB before using them. Our proposition does not have these two major drawbacks.

B. PCE power management

The PCE power management will not turn on all the functional blocks of a device integrally, but all blocks that are required are turned on at the beginning of the service. Formula (8) defines the PCE decision to turn on all necessary F B(i, j) at the beginning of the service.

t pce dec-on (i, j, k) = t request (i = 1, j, k) (8)
Fig. 4 (below) shows that the PCE power management turns on both device 1 and device 2 at the beginning of the service. So F B(i = 2, j) in device 2 stays in a no-activity state until it is actually requested. The only delay of the PCE power management is the starting time when device 1 is turned on.

C. ROPM & ROAL power management

Based on the same service pattern, we model our two propositions, namely ROPM and ROAL. The ROPM has knowledge of the average D time-lapse of the functional blocks that are required later, while the ROAL learns the time lapse D AL-time-lapse of the functional blocks that are required later in the service execution, described in formula [START_REF] Jeong | A network level power management for home network devices[END_REF]. Formula ( 10) describes that at the beginning of the service, F B(i, j) that are required first are turned on upon the request t request (i, j, k). If the refined power management does not detect a request of FB(i,j)required later, it will turn on F B(i, j) required later at the moment that power management has knowledge ( D time-lapse (i, j, k) ) or D AL-time-lapse (i, j, k)) as opposed to at the beginning of this service (t request (i = 1, j, k)). The D time-lapse (i, j, k) calculates in formula (2). However, if the power management detects a request for any F B(i, j) required later, it will be turned on immediately.

D AL-shif t-time (i, j, k) = N bs k=1 D time-lapse (i, j, k) N b s (9) t ROP M/ROAL dec-on (i, j, k) =                t request (i = 1) ROP M + D shif t-time(i,j,k) -D starting , t request (i) is not detected t ROAL request (i = 1) + D AL-shif t-time(i,j,k) -D starting , t request (i) is not detected t ROP M/ROAL request (i, j, k), Decision is late or i = 1:
(10) Fig. 5 shows that our proposition (ROPM or ROAL) decides to turn the second device on in advance. In this case, device 2 is on without executing any activity. Fig. 6 shows that our proposition (ROPM or ROAL) decides to turn on the second device too late. When the ROPM or ROAL detects that device 2 is needed immediately, device 2 is turned on at the moment that the request is detected. The delay for device 2 is the starting time of device 2. Since device 2 is turned on afterwards, it finishes its task later than the service expectation.

V. SETUP OF SIMULATIONS AND ANALYSIS OF RESULTS

In this section, we firstly present the simulation setup and then the analysis of the results obtained.

A. Setup of simulations

In order to accurately measure power consumption and the waiting delay of each power management, we implemented a typical home network, which was capable of executing II. We compare our propositions using User control and PCE power managements:

User control power management: We take a user who is mindful of energy conservation. This user turns on each device when its service is needed, and turns off each device when the service is no longer required. PCE: The service is started with all necessary power control elements on at the beginning of the service. They will be turned off when the user finishes using the functional blocks.

ROPM: Based on the pre-saved knowledge of user habits, the functional blocks of each device in the service will be turned on immediately before the FB is needed.

ROAL: The required functional blocks are turned on when the service is requested for the first time. The ROAL learns the value of D AL-time-lapse of each functional block during the service execution. After obtaining this information, the functional blocks will be controlled as in the ROPM.

B. Analysis of results

In this section, we analyze the three sets of simulation results: The first study shows that the power management ROAL is able to learn an approximate accurate time laps:D AL-time-lapse (i, j, k), when the simulation lasts for a long time. The second study shows the energy efficiency and delay impact of each power management system, when increasing the average time lapse and standard deviation of

TABLE II SIMULATION SETUP Notation Value N b d n =2 N b f d =10 D service-in-arrival (k) = 5000 s D utilisation (i, j, k) = 1000 s D starting (i, j, k) = 100 s P F B (i, j, k)
= 10 watt Simulationrepetitionsf oreachexperiment = 10 runs user habits. The third study shows the energy efficiency and delay impact when decreasing the standard deviation of user habits with a fixed average time lapse.

1) Simulation time limit:

The present study was designed to demonstrate that the ROAL can learn an accurate time lapse, when the simulation duration is long enough. The simulation time limit varies from 10 hours to 500 hours, with steps of 10 hours. We carried out 10 runs for each different simulation time limit. In Fig. 7, each point on the line red is the value of D AL-time-lapse that the ROAL learned at the end of each simulation. When the simulation lasts for only 10 hours, the D AL-time-lapse (i, j, k) is far from the D time-lapse (i, j, k) and the result of each run varies considerably, from 2300 seconds to 7000 seconds. However, when the simulation duration increases to about 200 hours, the ROAL obtains an accurate value of the D AL-time-lapse The result of the study indicates that if the ROAL has a sufficient learning period duration (200 hours, less than one week), it can learn an accurate value of time lapse of user habits. Since this value will impact the t ROP M/ROAL dec-on (i, j, k) when the simulation limit time is increased, the power consumption and waiting delay of the ROAL power management will be impacted as shown in Fig. 8 and Fig. 9.

Fig. 8 and Fig. 9 show the average energy consumption and the average delay per service when the simulation duration is varied. In Fig. 8, when the simulation lasts for just 10 hours, the ROAL has an energy consumption value between the PCE and the ROPM. Without an accurate D AL-time-lapse ,the ROAL turned the device on in advance. Therefore, the ROAL has a higher energy consumption when the simulation lasts for a short duration. Until the simulations last for more than 200 hours, the average energy consumption is almost the same as the ROPM. In Fig. 9, when the simulation lasts for only 10 hours, the ROAL has a waiting delay value between the PCE and the ROPM. Because the ROAL does not have enough time to learn the accurate time lapse, the D AL-time-lapse is lower than the user habit. In cases where the functional blocks which are required later are frequently turned on in advance, there is no delay if they are already available before the service request arrives. Therefore, the delay of the ROAL approaches From this study, we can conclude that when the simulation lasts long enough, the ROAL may obtain approximate time lapse information D AL-time-lapse on which the pre-saved D time-lapse is in the ROPM, and the ROAL has the same energy saving performance and waiting delay as the ROPM once the information relating to the average D time-lapse has been obtained.

2) Energy consumption and waiting delay by varying time lapse: In this scenario, the time lapse is varied from 0 to 5000 seconds, in steps of 100 seconds and with a standard deviation 1 λ0 = D time-lapse . As explained in Section III, the D time-lapse is follows an exponential process as in formula [START_REF] Eurostat | Consumption of energy[END_REF]. When standard deviation 1 λ0 = D time-lapse , the formulae can be simplified as in formula [START_REF] Yan | Green Home Network based on an Overlay Energy Control Network[END_REF]. This means that the generated user habits have a mean value of D time-lapse , but the difference between the generated time lapse and the average value will increase with the increase of the standard deviation. The simulation time limit is set at 40 hours. This is a simulation time limit for which the ROAL has not learned an accurate time lapse. Thus, we still have a difference between the ROPM and ROAL decisions.

D time-lapse (i) = exp( 1
D time-lapse (i, j, k) ) (11)
In Fig. 10, we can see that the energy consumption of the user control power management is almost stable because the devices are turned on integrally when the service requirements arrive and the devices are turned off integrally when the services are terminated. Therefore, the energy consumption of the user control power management corresponds to the service utilization. The energy consumption of the PCE power management increases continuously, since the PCE turns on all participating functional blocks from the beginning of the service. The more the D time-lapse increases, the more energy the functional blocks consume in the no-activity period. So, with the PCE, the total energy consumption in one service increases as the D time-lapse increases. The ROPM consumes less energy compared to the PCE because, once one service begins, those functional blocks that are not necessary will not be launched at the beginning of the service. They are launched at the time that is pre-saved in the power management. Since the average time lapse D time-lapse is fixed, it is possible that one F B(i, j) is turned on earlier. The ROAL consumes less energy compared to the PCE and slightly more energy compared to the ROPM. Unlike the ROPM, the ROAL does not have the knowledge when the functional blocks required later are requested by the service. The ROAL power management begins like the PCE and turns on all functional blocks. The more times the ROAL carries out the service, the more accurately it can learn the mean value of the D time-lapse if the average user behavior does not change. Here, during a 40-hour simulation launch time, the ROAL learns to turn on the functional blocks required later at a time that is closer to the real time lapse but which is still not accurate enough. In this scenario, the ROPM and the ROAL have a 35.24% and 41.85% energy gain respectively, compared to the PCE power management. The ROPM and the ROAL can reach 37.11% and 43.51% energy gain respectively, compared to the user control power management. Therefore, the PCE has the smallest delay and it is impossible to have a smaller delay, unless the functional blocks are never turned off. The PCE could be seen has an ideal form of management from the point of view of the delay, but it is the least advantageous from the power saving point of view (cf. Fig. 10). The ROPM has a greater waiting delay than the PCE. At the beginning of the service, there is always a waiting delay for the functional blocks that are used first. However, the functional blocks that are used later are turned on according to the predicted usual user behavior. If the functional blocks are turned on early, there is no generated delay. In contrast, it is also possible that the decision to turn on is later than the functional block requirements. When the ROPM detects the requirements of functional blocks, it turns the functional blocks on immediately. In this late decision case, the ROPM generates an extra delay compared to the PCE. The ROAL has a smaller waiting delay than the ROPM because the ROAL has an inaccurate learned time lapse which is earlier than user habit. There is a greater likelihood that the ROAL will turn F B(i, j) on earlier than the average service request. If F B(i, j) is available before the request, there is no waiting delay for the user. The result of this study indicates that the ROPM is the most energy efficient system and has a smaller delay than the user control power management, but a greater delay than the ROAL and the PCE. The ROAL is second in terms of energy efficiency but has a smaller delay compared to the ROPM.

3) Energy consumption and waiting delay by varying standard deviation : In this section we set the D time-lapse at 5000 seconds and decrease the standard deviation

1 λ0(i,j,k)
of the requirements of functional blocks which follows an exponential distribution as in formula [START_REF] Yan | Hope: Home power efficiency system for a green network[END_REF]. In this section we fix the D shif t-time at 5000 seconds and vary the standard deviation λ 0 of the requirements of functional blocks which follows an exponential distribution. D time-lapse (i) = exp(λ 0 (i, j, k)i) -1 λ 0 (i, j, k) + 5000 [START_REF] Yan | Hope: Home power efficiency system for a green network[END_REF] When the standard deviation 1 λ0(i,j,k) is decreased, the user habits for turning on the functional blocks needed later gets increasingly closer to D time-lapse = 5000 . The standard deviation of the time lapse decreases from 500 to 0 seconds with steps of 10 seconds. In Fig. 12, the energy consumption of the four power management systems are stable. The power consumption of the user control power management depends on the utilization of the device where the average value is fixed. Thus, the power consumption of the user control power management will remain stable. The PCE power consumption stays stable because the power-on duration of F B(i, j) which corresponds to utilization and time lapse is stable. The decision of the ROPM power management takes into account the value of D time-lapse and the ROAL takes into account the value of D AL-time-lapse . These two values will not change when the standard deviation is varied. Consequently, functional blocks are turned on based on fixed values in the ROPM and ROAL and the energy consumption stays stable as the last point D time-lapse = 5000 in Fig. 10. Regarding the delay shown in Fig. 13, we can see that the delay of the user control and PCE power management systems stay stable. The ROPM and ROAL delay decreases when the standard deviation is decreased. Since the standard deviation decreases, this means that the user behavior is approaching the pre-loaded time lapse or learned time lapse. The prediction of our power managements decision could be more accurate. Thus, the power management systems have a smaller delay impact. We can draw from this study that standard deviation is an important user habit which could have an impact on the delay. In this paper, we propose two power management systems based on refined overlay power management: the ROPM and ROAL. Our two propositions are based on the services analysis by controlling the functional blocks. The ROPM is energy efficient with the help of the pre-saved user behavior information. The ROAL is able to obtain approximate user behavior information following a learning period and it has a facility for the implementation in the home network. The simulation results has shown that ROAL provides a same level of energy efficiency comparing with ROPM. The ROPM and ROAL can reach 37.11% and 43.51% energy gain respectively. Therefore, after analyzing the impact of the standard deviation on the delay, our future research will explore the auto-learning of the standard deviation of the user behavior probability distribution in order to retrieve the trade-off between waiting delay and energy efficiency.

Fig. 1 .

 1 Fig. 1. Home refined network service management

Fig. 3 .

 3 Fig. 3. Functional block pattern

Fig. 4 .

 4 Fig. 4. PCE power management controls a collaborative service

Fig. 5 .Fig. 6 .

 56 Fig. 5. Device 2 is available afterwards via ROPM & ROAL control

Fig. 7 .

 7 Fig. 7. ROAL progress the knowledge on the time lapse by increasing the simulation time that of the PCE. When the simulation lasts for more than 200

Fig. 8 .Fig. 9 .

 89 Fig. 8. Energy consumption per service by increasing simulation duration

Fig. 10 .

 10 Fig. 10. Energy consumption while changing Duration of shift time Fig. 11 shows the average waiting delay for each service. The user control power management turns on the devices when the service request arrives. Thus, there is always a waiting delay in the starting time before the device becomes available. The PCE has the smallest waiting delay because all of the

Fig. 11 .

 11 Fig. 11. Energy consumption while changing Duration of shift time

Fig. 12 .

 12 Fig. 12. Energy consumption when standard deviation is changed

Fig. 13 .

 13 Fig. 13. Delay when standard deviation is changed


Han Yan

Fabrice Fontaine

Olivier Bouchet

Jean-Paul Vuichard

Jean-Philippe Javaudin

Maryline Lebouc

Marie-Helene Hamon

Cedric Gueguen

Bernard Cousin

HOPE: HOme Power Efficiency System for a Green Network

Keywords: Efficient energy saving, Green networking, ZigBee, UPnP Low Power, UPnP Audio Video, Heterogeneous network, Convergence layer, Green path selection, Digital home

A home network represents an increasingly large portion of a household's electrical consumption due to the increasing number of digital home devices and the increasing complexity of the underlying communication infrastructure. Limiting a home network's power consumption is a priority for large institutions as witnessed by evolving regulation, and a priority for individual consumers wishing to reduce their electric bills. In this demonstration, we proposed a solution that aims at reducing power consumption at both the device and network level. At the device level, our system can turn the devices off when they are not in operation and quickly turn them on when they are needed. At the network level, the solution is based on a new convergence layer denoted inter-MAC, which provides a common infrastructure to the different home network paths. In particular, the inter-MAC can be used to choose a greener path. Our solution on both levels is compatible and complementary to home network energy saving.

I. INTRODUCTION

In the last decade, there has been a proliferation of connected devices in the home environment. The number of connected devices has led to a sharp increase in energy consumption. A home network [START_REF] Rose | Home networks: a standards perspective[END_REF] is a complex environment which can contain several different types of devices: Set-Top Box (STB), Home GateWay (HGW), network attached storage (NAS), laptop, power line communication (PLC) plugs and so on; which are interconnected with different kinds of connections: Wi-Fi, Ethernet and power line communication. These home network devices represent an increasingly large portion of a homes electric consumption, which in turn generates greater carbon emissions and the costs consumers more.

For these two reasons, environmental and economical, it is essential to provide an effective means of reducing power consumption, which is also transparent for the user. To do so, we propose a technical solution on two levels. The first device level solution uses an overlay control network which switches existing devices on or off according to their usage. The second network level solution allows for selecting the least amount of energy to be consumed or least radiating a data path among the available links (Wi-Fi, Ethernet, PLC etc.).

These two phases are compatible and could be combined into a single offering. The standardization process is underway, with initial contributions proposed by standards bodies (HGI [2], IEEE P1905 [3]).

II. SYSTEM ARCHITECTURE

Our HOPE system proposes two solutions for energy saving. The solution at the device level could change the power levels of each device depending on its usage in a simple network. Since our home network connections are becoming increasingly complex, one device could accommodate several connections. This is why the second solution works at the network level: it selects the greener path.

A. The device-level system

The device-level system for reducing power consumption is based on an energy control layer overlaying the home network. This energy control layer can turn off the devices or switch the devices to a very low power consumption mode when they are not in operation. Moreover, the system can automatically wake up the devices when the user needs them. During this process, all energy control messages are sent on a low-power consumption network like ZigBee [START_REF]Zigbee Specifications[END_REF] or by using a low-power consumption protocol like UPnP Low Power [START_REF]UPnP Low Power Architecture, UPnP Forum Std[END_REF].

All the different home network devices are considered HOPE nodes in our system. As shown in Fig. 1, a HOPE system is composed of two kinds of functional blocks: service blocks and low power consumption connection blocks. Service functional blocks intercept the service request required by the actual device, and then send this request through the low power consumption control layer. In our demonstration, the system is able to satisfy basic services such as an IPTV or Internet connection. Furthermore, there are several enriched multimedia services, such as audio/video sharing, which are implemented by UPnP AV [START_REF]UPnP Audio Video Architecture, UPnP Forum Std[END_REF], which demonstrates the efficiency of our energy saving system for collaborative services. Since these sharing services are collaborative services, the actual device requires more than a network connection service on the HGW: it also requires turning on a second device and activating the audio/video sharing services on the second device.

B. The network-level system

The proposed network-level system for reducing power consumption is based on a technology-independent layer, called an inter-MAC, from the Omega project [7], [START_REF] Suraci | Convergence in home gigabit networks: Implementation of the inter-mac layer as a pluggable kernel module[END_REF].

This inter-MAC convergence layer is positioned above the different MAC layer of the different technologies. The inter-MAC layer is composed of three functional planes (Fig. 2): the control plane, the data plane and the management plane. The data plane is responsible for frame forwarding. The control plane is responsible for short-term decisions related to the establishment and release of paths and the processing of upper layer requests. It is divided into several engines: QoS, Monitoring, Inter-MAC Adapter and Green Path Selection. The green path selection protocol takes into account the following three metrics: Available bandwidth, energy consumption, and radio frequency. More technical details are presented in [START_REF] Bouchet | Inter-mac green path selection for heterogeneous networks[END_REF].

III. DESCRIPTION OF DEMONSTRATIONS

In the first part of our demonstration shown in Fig. 3, the HOPE system aims to maintain the devices in a low-power consumption state when the devices are not in use. Meanwhile, if the devices are required by a service, it can be woken up by our HOPE system. For example, in the IPTV scenario, a user wants to watch IPTV on his STB. The STB is connected to the HGW through a pair of PLC plugs. When the user turns the STB on to watch IPTV, the requirement of establishing a network connection through the PLC plugs is intercepted by our system. The PLC plugs are woken up and a network connection for the IPTV service is established. When the user turns the STB off, the PLC plugs are also turned off since the connection from the HGW to the STB is not needed.

Several scenarios are presented in this section to demonstrate the efficiency of our system on enriched services.

Fig. 4 represents a heterogeneous home network configuration with Ethernet, PLC and WiFi links. The second part of our demonstration contains 4 mini PCs, which play the role of extenders; they implement the green path selection protocol. The end devices (including a PC, NAS, TV, tablet and mobile phone) are connected to these extenders. The Home Gateway connects the home network to the Internet. The idea is to highlight energy consumption reduction while maintaining satisfactory QoS for different flows, due to the green path selection protocol introduced in section II. Users can benefit from enriched home multimedia services and efficiently manage their power consumption. Our future work will study the reduction of power consumption combining both the device component level and the network level in different services in order to further reduce the total power consumption of the home network.

Fig. 1 .

 1 Fig. 1. Device-level HOPE node architecture

Fig. 2 .

 2 Fig. 2. Network-level HOPE inter-MAC architecture

Fig. 3 .

 3 Fig. 3. Device-level HOPE demonstration

Fig. 4 .

 4 Fig. 4. Network level HOPE demonstration

ACKNOWLEDGMENT

This work was supported by the French government in the framework of the FUI10 Econhome project.