Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr.

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr.

A Topological Study of Chaotic Iterations. Application to Hash Functions

Keywords: Topological chaos, Chaotic iterations, Hash functions, Neural Networks

Chaotic iterations, a tool formerly used in distributed computing, has recently revealed various interesting properties of disorder leading to its use in the computer science security field. In this paper, a comprehensive study of its topological behavior is proposed. It is stated that, in addition to being chaotic as defined in the Devaney's formulation, this tool possesses the property of topological mixing. Additionally, its level of sensibility, expansivity, and topological entropy are evaluated. All of these properties lead to a complete unpredictable behavior for the chaotic iterations. As it only manipulates binary digits or integers, we show that it is possible to use it to produce truly chaotic computer programs. As an application example, a truly chaotic hash function is proposed in two versions. In the second version, an artificial neural network is used, which can be stated as chaotic according to Devaney.

INTRODUCTION

Chaotic iterations (CIs) were formerly a way to formalize distributed algorithms through mathematical tools [START_REF] Chazan | Chaotic relaxation. Linear algebra and its applications[END_REF]. By using these CIs, it was thus possible to study the convergence of synchronous or asynchronous programs over parallel, distributed, P2P, grid, or GPU platforms, in a view to solve linear and non-linear systems. We have proven at the IEEE World Congress on Computational Intelligence (WCCI '10) that CIs can behave chaotically, as it is defined by Devaney [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF]. These proofs have been improved and more detailed in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF]. In this paper, which is an extension of [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF], we notably enlarge the theoretical study of CIs, among other things by computing its topological entropy, to obtain a comprehensive evaluation of its topological behavior. This study leads us to the conclusion that the chaos of CIs is very intense and constitutes a useful tool to be used in the computer science security field.

Chaos in information security fields as digital watermarking [START_REF] Cong | A wavelet packets watermarking algorithm based on chaos encryption[END_REF][START_REF] Congxu | Chaos-based multipurpose image watermarking algorithm[END_REF], hash functions [START_REF] Wang | One-way hash function construction based on the extended chaotic maps switch[END_REF][START_REF] Xiao | Improving the security of a parallel keyed hash function based on chaotic maps[END_REF], or pseudo-random number generators, is often disputed. This is due to the fact that this use is almost always based on the conception of algorithms that only include "somewhere" some well-known chaotic real functions like logistic, tent, or Arnold's cat maps, to obtain a program supposed to express these chaotic properties [START_REF] Fei | A secure digital signature algorithm based on elliptic curve and chaotic mappings[END_REF][START_REF] Wu | A novel digital watermark algorithm based on chaotic maps[END_REF][START_REF] Song | Extracting information masked by chaos and contaminated with noise: Some considerations on the security of communication approaches using chaos[END_REF]. However, using such functions with other "obvious" parameters does not guarantee that the whole algorithm still remains chaotic. Such an assumption should at least be discussed. Moreover, even if the algorithm obtained by the inclusion of chaotic maps is itself proven to be chaotic, its implementation on a machine can lead to the fact that this chaotic nature is lost. This is due to the finite cardinality of the machine numbers set.

In this paper, as in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF], we do not simply integrate chaotic maps into algorithms hoping that the result remains chaotic. We conceive algorithms for computer security that we have mathematically proven to be chaotic, as it is defined in the Devaney's theory. We raise the question of their implementation, proving in doing so that it is possible to design both a chaotic algorithm and its associated chaotic computer program. The chaos theory we consider is taken from the mathematical topology. It encompasses the well-known Devaney's definition of chaos and the notions of expansivity, topological entropy, and topological mixing. These notions of unpredictability are the most established ones into the mathematical theory of chaos. Our fundamental study is motivated by the desire to produce chaotic programs in the area of information security.

The paper begins by introducing the theoretical foundation of this approach. On the one hand we recall the definition of Devaney's topological chaos and on the other hand the definition of discrete chaotic iterations. Although these definitions are distinct from each other, we establish a link between them by giving conditions under which chaotic discrete iterations generate a Devaney's topological chaos. This study is deepened by giving some qualitative and quantitative evaluations of the disorder generated by chaotic iterations. These evaluations are not present in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF][START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF]. We will focus in this paper on the notions of expansivity, topological mixing, and topological entropy. The proofs that the considered space is separated and compact have never been published before. Furthermore, the evaluation of the topological entropy is completely new. Then, because chaotic iterations are very suited for computer programming, this link allows us to generate programs in the computer science field that behave chaotically. This link was formerly presented in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF] with some errors that are corrected here.

After having studied the theoretical aspects of our approach we focus on the practical ones. The important question is how to preserve the topological chaos properties in a set of a finite number of states. This question is answered in Section 1.5, by manipulating only integers and considering the use of new data at each iteration.

The general algorithm based on our approach, formerly presented in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], is now explained in detail in Section 1.6. It is rewritten in the next section as an artificial neural network that can compute hash values while behaving chaotically. This new application is completely new and has never been published before.

The remainder of this paper is organized in the following way. In Section 1.2, the definitions of Devaney's chaos and discrete chaotic iterations are recalled. A link between these two notions is established and sufficient conditions to obtain Devaney's topological chaos from discrete chaotic iterations are given in Section 1.3. The chaotic behavior of CIs is deepened in Section 1.4, by studying some qualitative and quantitative properties of disorder. In Section 1.5, the question on how to preserve these chaotic properties into computers is answered. Then in Section 1.6 the general hash function scheme is given and illustrated, whereas in Section 1.7 it is applied to produce an artificial neural network able to hash some values in a chaotic manner. The paper ends by a conclusion section in which our contribution is summarized and planned future work is discussed.

BASIC RECALLS

This section is devoted to basic definitions and terminologies in the field of topological chaos and in the one of chaotic iterations.

Devaney's chaotic dynamical systems

In the sequel S n denotes the n th term of a sequence S and V i denotes the i th component of a vector V . f k = f • ... • f denotes the k th composition of a function f . Finally, the following notation is used: 1; N = {1, 2, . . . , N}.

Consider a topological space (X , τ) and a continuous function f : X → X .

Definition 1. f is said to be topologically transitive if, for any pair of open sets U,V ⊂ X , there exists k > 0 such that f k (U) ∩V ∅.

Definition 2. An element x is a periodic point for f of period n ∈ N * if f n (x) = x.
Definition 3. f is said to be regular on (X , τ) if the set of periodic points for f is dense in X : for any point x in X , any neighborhood of x contains at least one periodic point (without necessarily the same period).

Definition 4. f is said to be chaotic on (X , τ) if f is regular and topologically transitive.

The chaos property is strongly linked to the notion of "sensitivity", defined on a metric space (X , d) by: Definition 5. f has sensitive dependence on initial conditions if there exists δ > 0 such that, for any x ∈ X and any neighborhood V of x, there exist y ∈ V and n > 0 such that d ( f n (x), f n (y)) > δ .

δ is called the constant of sensitivity of f . Indeed, Banks et al. have proven in [START_REF] Banks | On devaney's definition of chaos[END_REF] that when f is chaotic and (X , d) is a metric space, then f has the property of sensitive dependence on initial conditions (this property was formerly an element of the definition of chaos). To sum up, quoting Devaney in [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], a chaotic dynamical system "is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or simplified into two subsystems which do not interact because of topological transitivity. And in the midst of this random behavior, we nevertheless have an element of regularity". Fundamentally different behaviors are consequently possible and occur in an unpredictable way.

Chaotic iterations

Let us consider a system with a finite number N ∈ N * of elements (or cells), so that each cell has a Boolean state. Having N Boolean values for these cells leads to the definition of a particular state of the system. A sequence which elements belong to 1; N is called a strategy. The set of all strategies is denoted by S. Definition 6. The set B denoting {0, 1}, let f : B N -→ B N be a function and S ∈ S be a strategy. The so-called chaotic iterations are defined by x 0 ∈ B N and

∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if S n i f (x n-1 ) S n if S n = i.
In other words, at the n th iteration, only the S n -th cell is "iterated". Note that in a more general formulation, S n can be a subset of components and f (x n-1 ) S n can be replaced by f (x k ) S n , where k < n, describing for example, delays transmission [START_REF] Robert | Discrete Iterations: A Metric Study[END_REF][START_REF] Guyeux | Le désordre des itérations chaotiques et leur utilité en sécurité informatique[END_REF]. Finally, let us remark that the term "chaotic", in the name of these iterations, has a priori no link with the mathematical theory of chaos, recalled above.

CHAOTIC ITERATIONS AS DEVANEY'S CHAOS

In this section is proven that chaotic iterations are a particular case of topological chaos, as it is defined in the Devaney's formulation'.

The new topological space

In this section we define a suitable metric space where chaotic iterations are continuous.

Defining the iteration function and the phase space

Let δ be the discrete Boolean metric, δ (x, y) = 0 ⇔ x = y. Given a function f , define the function:

F f : 1; N × B N -→ B N (k, E) -→ E j .δ (k, j) + f (E) k .δ (k, j) j∈ 1;N
, where + and . are the Boolean addition and product operations. Consider the phase space:

X = 1; N N × B N ,
and the map defined on X :

G f (S, E) = σ (S), F f (i(S), E) , (1.1)
where σ is the shift function defined by σ (S n ) n∈N ∈ S -→ (S n+1 ) n∈N ∈ S and i is the initial function i : (S n ) n∈N ∈ S -→ S 0 ∈ 1; N . Then the chaotic iterations defined in (1.2.2) can be described by the following iterations:

X 0 ∈ X X k+1 = G f (X k ).
With this formulation, a shift function appears as a component of chaotic iterations. The shift function is a famous example of a chaotic map [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF] but its presence is not sufficient enough to claim G f as chaotic. In the rest of this section we rigorously prove that under some hypotheses, chaotic iterations generate topological chaos. Furthermore, due to the suitability of chaotic iterations for computer programming [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF][START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF][START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF] we also have proven that this is true in the computer science field.

Cardinality of X

By comparing S and R, we have the following result.

Theorem 1. The phase space X has, at least, the cardinality of the continuum.

Proof. Let ϕ be the map which transforms a strategy into the binary representation of an element in [0, 1[, as follows. If the n th term of the strategy is 0, then the n th associated digit is 0. If this n th term is not equal to 0, then the associated digit is

1. With this construction, ϕ : 1; N N -→ [0, 1] is onto. But ]0, 1[ is isomorphic to R (x ∈]0, 1[ → tan(π(x -1 2 )
) is an isomorphism), so the cardinality of 1; N N is greater or equal to the cardinality of R. As a consequence, the cardinality of the Cartesian product X = 1; N N × B N is greater or equal to the cardinality of R.

Remark 1. This result is independent from the number of components of the system.

1.3.1.3 A new distance Let us define a new distance between two points X = (S, E),Y = ( Š, Ě) ∈ X by d(X,Y ) = d e (E, Ě) + d s (S, Š), where          d e (E, Ě) = N ∑ k=1 δ (E k , Ěk ), d s (S, Š) = 9 N ∞ ∑ k=1 |S k -Šk | 10 k .
This new distance has been introduced in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] to satisfy the following requirements.

• When the number of different cells between two systems is increasing, then their distance should increase too. • In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.

The distance presented above follows these recommendations. Indeed, if the floor value d(X,Y ) is equal to n, then the systems E, Ě differ in n cells. In addition, d(X,Y )d(X,Y ) is a measure of the differences between strategies S and Š. More precisely, this floating part is less than 10 -k if and only if the first k terms of the two strategies are equal. Moreover, if the k th digit is nonzero, then the k th terms of the two strategies are different.

Continuity of the iteration function

To prove that chaotic iterations are an example of topological chaos in the sense of Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], G f must be continuous in the metric space (X , d).

Theorem 2. G f is a continuous function.

Proof. We use the sequential continuity. Let (S n , E n ) n∈N be a sequence of the phase space X , which converges to (S, E). We will prove that G f (S n , E n ) n∈N converges to G f (S, E) . Let us recall that for all n, S n is a strategy, thus, we consider a sequence of strategies (i.e., a sequence of sequences). As d((S n , E n ); (S, E)) converges to 0, each distance d e (E n , E) and d s (S n , S) converges to 0. But d e (E n , E) is an integer, so ∃n 0 ∈ N, d e (E n , E) = 0 for any n n 0 .

In other words, there exists a threshold n 0 ∈ N after which no cell will change its state:

∃n 0 ∈ N, n n 0 ⇒ E n = E.
In addition, d s (S n , S) -→ 0, so ∃n 1 ∈ N, d s (S n , S) < 10 -1 for all indexes greater than or equal to n 1 . This means that for n n 1 , all the S n have the same first term, which is S 0 : ∀n n 1 , S n 0 = S 0 . Thus, after the max(n 0 , n 1 ) th term, states of E n and E are identical and strategies S n and S start with the same first term. Consequently, states of G f (S n , E n ) and G f (S, E) are equal, so, after the max(n 0 , n 1 ) th term, the distance d between these two points is strictly less than 1. We now prove that the distance between E) is strictly less than 1 after the max(n 0 , n 1 ) th term (same state).

G f (S n , E n ) and G f (S, E) is convergent to 0. Let ε > 0. • If ε 1, we see that distance between G f (S n , E n ) and G f (S,
• If ε < 1, then ∃k ∈ N, 10 -k ε > 10 -(k+1) . But d s (S n , S) converges to 0, so ∃n 2 ∈ N, ∀n n 2 , d s (S n , S) < 10 -(k+2) ,
thus after n 2 , the k + 2 first terms of S n and S are equal.

As a consequence, the k + 1 first entries of the strategies of G f (S n , E n ) and G f (S, E) are the same (G f is a shift of strategies) and due to the definition of d s , the floating part of the distance between (S n , E n ) and (S, E) is strictly less than 10 -(k+1) ε.

In conclusion,

∀ε > 0, ∃N 0 = max(n 0 , n 1 , n 2 ) ∈ N, ∀n N 0 , d G f (S n , E n ); G f (S, E) ε.
G f is consequently continuous.

In this section, we proved that chaotic iterations can be modeled as a dynamical system in a topological space. In the next section, we show that some chaotic iterations behave chaotically, as defined by Devaney's theory.

Discrete chaotic iterations as topological chaos

To prove that we are in the framework of Devaney's topological chaos, we have to find a Boolean function f such that G f satisfies the regularity, transitivity, and sensitivity conditions. We will prove that the vectorial logical negation

f 0 (x 1 , . . . , x N ) = (x 1 , . . . , x N ) (1.2)
is a suitable function.

Regularity

Firstly, let us prove that, Theorem 3. Periodic points of G f 0 are dense in X .

Proof. Let ( Š, Ě) ∈ X and ε > 0. We are looking for a periodic point ( S, E) satisfying d(( Š, Ě); ( S, E)) < ε. As ε can be strictly lesser than 1, we must choose E = Ě. Let us define k 0 (ε) = log 10 (ε) + 1 and consider the set

S Š,k 0 (ε) = S ∈ S/S k = Šk , ∀k k 0 (ε) . Then, ∀S ∈ S Š,k 0 (ε) , d((S, Ě); ( Š, Ě)) < ε. It remains to choose S ∈ S Š,k 0 (ε) such that ( S, E) = ( S, Ě) is a periodic point for G f 0 . Let J = i ∈ {1, ..., N}/E i Ěi , where (S, E) = G k 0 f 0 ( Š, Ě) ,
i 0 = card(J ), and j 1 < j 2 < ... < j i 0 the elements of J . Then, S ∈ S Š,k 0 (ε) defined by

• S k = Šk , if k k 0 (ε), • S k = j k-k 0 (ε) , if k ∈ {k 0 (ε) + 1, k 0 (ε) + 2, ..., k 0 (ε) + i 0 },
• and S k = S j , where j k 0 (ε)

+ i 0 is satisfying j ≡ k (mod k 0 (ε) + i 0 ), if k > k 0 (ε) + i 0 , is such that ( S, E) is a periodic point (of period k 0 (ε) + i 0 ), which is ε-close to ( Š, Ě).
As a conclusion, (X , G f 0 ) is regular.

Transitivity

Regarding the transitivity property of G f 0 , we can show that,

Theorem 4. (X , G f 0 ) is topologically transitive. Proof. Let us define E : X → B N , such that E (S, E) = E. Let B A = B(X A , r A ) and B B = B(X B , r B ) be two open balls of X , with X A = (S A , E A ) and X B = (S B , E B ). We are looking for X = ( S, E) in B A such that ∃n 0 ∈ N, G n 0 f 0 ( X) ∈ B B . X must be in B A and r A can be strictly lesser than 1, so E = E A . Let k 0 = log 10 (r A ) + 1 . Then ∀S ∈ S, if S k = S k A , ∀k k 0 , then (S, E) ∈ B A . Let ( Š, Ě) be equal to G k 0 f 0 (S A , E A ) and c 1 , ..., c k 1 denote the elements of the set {i ∈ 1, N / Ěi E (X B ) i }. So any point X of the set {(S, E A ) ∈ X /∀k k 0 , S k = S k A and ∀k ∈ 1, k 1 , S k 0 +k = c k } is satisfying X ∈ B A and E G k 0 +k 1 f 0 (X) = E B .
Lastly, let k 2 be log 10 (r B ) + 1. Then X = ( S, E) ∈ X defined by:

1. X = E A , 2. ∀k k 0 , S k = S k A , 3. ∀k ∈ 1, k 1 , S k 0 +k = c k , 4. ∀k ∈ N * , S k 0 +k 1 +k = S k B , is such that X ∈ B A and G k 0 +k 1 f 0 ( X) ∈ B B .
This fact concludes the proof of the theorem.

Devaney's Chaos

In conclusion, (X , G f 0 ) is topologically transitive and regular. Then we have the following result:

Theorem 5. G f 0 is a chaotic map on (X , d) in the sense of Devaney.
We have proven that the set C of the iterate functions f so that (X , G f ) is chaotic (according to the definition of Devaney), is a nonempty set. In future work, we will deepen the study of C , among other things, by computing its cardinality and characterizing this set.

TOPOLOGICAL PROPERTIES OF CHAOTIC ITERATIONS

In this section, some qualitative and quantitative topological properties for chaotic iterations with G f 0 will be studied in detail. These properties reinforce the chaotic behavior of the system.

Topological mixing

The topological mixing is a strong version of transitivity: Definition 7. A discrete dynamical system is said to be topologically mixing if and only if, for any couple of disjoint open set U,V ∅, n 0 ∈ N can be found so that ∀n n 0 , f n (U) ∩V ∅.

We have the result [START_REF] Guyeux | Chaotic iterations versus spreadspectrum: chaos and stego security[END_REF],

Theorem 6. (X , G f 0 ) is topologically mixing.
This result is an immediate consequence of the lemma below.

Lemma 1.

For any open ball B of X , an index n can be found such that G n f 0 (B) = X .

Proof. Let B = B((E, S), ε) be an open ball, which the radius can be considered as strictly less than 1. The elements of B all have the same state E and are such that an integer k (=log 10 (ε)) satisfies:

• all the strategies of B have the same k first terms, • after the index k, all values are possible.

Then, after k iterations, the new state of the system is G k f 0 (E, S) 1 and all the strategies are possibles (any point of the form (G k f 0 (E, S) 1 , Ŝ), with any Ŝ ∈ S, is reachable from B).

Let (E , S ) ∈ X . We will prove that any point of X is reachable from B. Indeed, let s i be the list of the different cells between G k f 0 (E, S) 1 and E , and |s| its size. The point ( Ě, Š) of B defined by:

• Ě = E, • Ši = S i , ∀i k, • Šk+i = s i , ∀i |s|, • ∀i ∈ N, S k+|s|+i = S i .
is such that G k+|s| f 0 ( Ě, Š) = (E , S ). This conclude the proof of the lemma.

Quantitative measures

General definitions

In Section 1.3.2.3 we have proven that discrete chaotic iterations produce a topological chaos by checking two qualitative properties, namely transitivity and regularity. This mathematical framework offers tools to measure this chaos quantitatively. The first of these measures is the constant of sensitivity defined in Definition 5. Intuitively, a function f having a constant sensitivity equal to δ implies that there exists points arbitrarily close to any point x, which eventually separate from x by at least δ under some iterations of f . This induces that an arbitrarily small error on an initial condition might be magnified upon iterations of f . Another important tool is defined below.

Definition 8. A function f is said to have the property of expansivity if

∃ε > 0, ∀x y, ∃n ∈ N, d( f n (x), f n (y)) ε.
Then, ε is the constant of expansivity of f . We also say that f is ε-expansive.

A function f has a constant of expansivity equal to ε if an arbitrarily small error on any initial condition is always magnified until ε.

Sensitivity

The sensitive dependence on the initial conditions has been shown as a consequence of the regularity and the transitivity of chaotic iterations. However, in the set of machine numbers, we have shown in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF] that the notion of regularity must be redefined. This is the reason why this sensitivity should be proven without using the result of Banks [START_REF] Banks | On devaney's definition of chaos[END_REF], to be sure that this dependence is preserved in practical use of chaotic iterations.

In addition, the constant of sensitivity will be obtained during this proof.

Theorem 7. (X , G f 0 ) has sensitive dependence on initial conditions and its constant of sensitivity is equal to N -1.

Proof. Let X = ( Š, Ě) ∈ X . We are looking for X = ( S, E) ∈ X such that d( X, X)

δ and ∃n 0 ∈ N, d G n 0 f 0 ( X); G n 0 f 0 ( X) N -1. Let k 0 be log 10 (δ ) + 1. So, if S ∈ {S ∈ S/∀k k 0 , S k = Šk }, then d (S, Ě), ( Š, Ě) δ . Let J = i ∈ 1, N / E G k 0 f 0 ( Š, Ě) i = E G k 0 +N f 0 ( Š, Ě) i and p = card (J ).
If p = N, then ( S, E) ∈ X defined by:

1. E = Ě, 2. ∀k k 0 , S k = Šk , 3. ∀k ∈ 1, N , S k 0 +k = k, 4. ∀k > k 0 + N, S k = 1. satisfies d(( S, E); ( Š, Ě)) < δ and ∀i ∈ 1, N , E G k 0 +N f 0 ( S; E) i E G k 0 +N f 0 ( Š; Ě) i
, so the result is obtained. Else, let j 1 < j 2 < ... < j p be the elements of J and j 0 J . Then X = ( E, S) ∈ X defined by

1. E = Ě, 2. ∀k k 0 , S k = Šk , 3. ∀k ∈ 1, p , S k 0 +k = j k , 4. ∀k ∈ N * , S k 0 +p+k = j 0 . is such that d( X, X) < δ . In addition, ∀i ∈ 1, p , E G k 0 +N f 0 ( X) j i E G k 0 +N f 0 ( X) j i , because: • ∀i ∈ 1, N , E G k 0 f 0 ( X) i = E G k 0 f 0 ( X) i , due to the definition of k 0 . • ∀i ∈ 1, p , j i ∈ J ⇒ E G k 0 +N f 0 ( X) j i = E G k 0 f 0 ( X) j i
, according to the definition of J .

• ∀i ∈ 1, p , j i appears exactly one time in S k 0 , S k 0 +1 , ..., S k 0 +N , so

E G k 0 +N f 0 ( X) j i E G k 0 f 0 ( X) j i . Lastly, ∀i ∈ 1, N \ { j 0 , j 1 , ..., j p }, E G k 0 +N f 0 ( X) i E G k 0 +N f 0 ( X) i , because: • ∀i ∈ 1, N , E G k 0 f 0 ( X) i = E G k 0 f 0 ( X) i , • i J ⇒ E G k 0 +N f 0 ( X) i E G k 0 f 0 ( X) i , • i { S k 0 , S k 0 +1 , ..., S k 0 +N } ⇒ E G k 0 +N f 0 ( X) i = E G k 0 f 0 ( X) i . So, in this case, ∀i ∈ 1, N \ { j 0 }, E G k 0 +N f 0 ( S; E) i E G k 0 +N f 0 ( Š; Ě)
i and the result of sensitivity is still obtained.

Expansivity

In this section we offer the proof that chaotic iterations are expansive [START_REF] Guyeux | Chaotic iterations versus spreadspectrum: chaos and stego security[END_REF] when f 0 is the update function: Theorem 8. (X , G f 0 ) is an expansive chaotic system. Its constant of expansivity is equal to 1.

Proof. If (S, E) ( Š; Ě), then:

• Either E Ě and so at least one cell is not in the same state in E and Ě. Consequently the distance between (S, E) and ( Š; Ě) is greater or equal to 1.

• Or E = Ě. So the strategies S and Š are not equal. Let n 0 be the first index such that the terms S and Š differ. Then ∀k

< n 0 , G n 0 f 0 (S, E) = G k f 0 ( Š, Ě), and G n 0 f 0 (S, E) G n 0 f 0 ( Š, Ě).
As E = Ě, the cell that has changed in E at the n 0 -th iterate is not the same than the cell that has changed in Ě, so the distance between G n 0 f 0 (S, E) and G n 0 f 0 ( Š, Ě) is greater or equal to 2.

So the expansivity property is established.

Remark 2. Expansivity is a kind of avalanche effect: any initial error is always magnified when iterating the system. Remark 3. (X , G f 0 ) is not A-expansive, for any A > 1: let us consider two points X = (E, S) and X = (E , S ) with the same strategy (S = S ) and only one different

cell (d e (E, E ) = 1). So, ∀n ∈ N, d e E G n f 0 (X) , E G n f 0 (X ) = 1.

Topological Entropy

Another important tool to measure the chaotic behavior of a dynamical system is the topological entropy, which is defined for compact topological spaces. Before studying the entropy of CIs, we must then check that (X , d) is compact.

Compacity Study

In this section, we will prove that (X , d) is a compact topological space, in order to study its topological entropy later. Firstly, as (X , d) is a metric space, it is separated.

It is however possible to give a direct proof of this result:

Theorem 9. (X , d) is a separated space.
Proof. Let (E, S) ( Ê, Ŝ) two points of X .

1. If E Ê, then the intersection between the two balls B (E, S), 1 2 and B ( Ê, Ŝ), 1 2 in empty. 2. Else, it exists k ∈ N such that S k Ŝk , then the balls B (E, S), 10 -(k+1) and B ( Ê, Ŝ), 10 -(k+1) can be chosen.

The sequential characterization of the compacity for metric spaces can now be used to obtain the following result.

Theorem 10. (X , d) is a compact metric space.

Proof. Let (E n , S n ) n∈N be a sequence of X .

1.

A state E ñ which appears an infinite number of time in this sequence can be found. Let

I = {(E n , S n ) E n = E ñ}.
For all (E, S) ∈ I, S n 0 ∈ 1, N , and I is an infinite set. Then k ∈ 1, N can be found such that an infinite number of strategies of I starts with k. Let n 0 be the smallest integer such that E n = E ñ and S n 0 = k. 2. The set I = {(E n , S n ) E n = E n 0 and S n 0 = S n 0 0 } is infinite, then one of the elements of 1, N will appear an infinite number of times in the S n 1 of I : let us call it l. Let n 1 be the smallest n such that (E n , S n ) ∈ I and S n 1 = l. 3. The set

I = {(E n , S n )|E n = E n 0 and S n 0 = S n 0 0 and S n 1 = S n 1 1 } is infinite, etc. Let l = E n 0 , S n k
k k∈N , then the subsequence (E n k , S n k ) converges to l.

Topological entropy

Let (X, d) be a compact metric space and f : X → X be a continuous map. For each natural number n, a new metric d n is defined on X by

d n (x, y) = max{d( f i (x), f i (y)) : 0 ≤ i < n}.
Given any ε > 0 and n 1, two points of X are ε-close with respect to this metric if their first n iterates are ε-close.

This metric allows one to distinguish in a neighborhood of an orbit the points that move away from each other during the iteration from the points that travel together. A subset E of X is said to be (n, ε)-separated if each pair of distinct points of E is at least ε apart in the metric d n . Denote by H(n, ε) the maximum cardinality of an (n, ε)-separated set, Definition 9. The topological entropy of the map f is defined by (see e.g. [START_REF] Adler | Topological entropy[END_REF] or [START_REF] Bowen | Entropy for group endomorphisms and homogeneous spaces[END_REF])

h( f ) = lim ε→0 lim sup n→∞ 1 n log H(n, ε) .
We have the result,

Theorem 11. Entropy of (X , G f ) is infinite. Proof. Let E, Ě ∈ B N such that ∃i 0 ∈ 1, N , E i 0 Ěi 0 . Then, ∀S, Š ∈ S , d((E, S); ( Ě, Š)) 1 But the cardinal c of S is infinite, then ∀n ∈ N, c > e n 2 .
Then for all n ∈ N, the maximal number H(n, 1) of (n, 1)-separated points is greater than or equal to e n 2 , so

h top (G f , 1) = lim 1 n log (H(n, 1)) > lim 1 n log e n 2 = lim (n) = +∞.
But h top (G f , ε) is an increasing function when ε is decreasing, then

h top G f = lim ε→0 h top (G f , ε) > h top (G f , 1) = +∞,
which concludes the evaluation of the topological entropy of G f .

We have proven that it is possible to find f , such that chaotic iterations generated by f can be described by a chaotic and entropic map on a topological space in the sense of Devaney. We have considered a finite set of states B N and a set S of strategies composed by an infinite number of infinite sequences. In the following section we will discuss the impact of these assumptions in the context of the finite set of machine numbers.

CHAOS IN A FINITE STATE MACHINE

Let us now explain how it is possible to have a true chaos in a finite state machine.

A program with a chaotic behavior

In the Section 1.3 we have proven that discrete chaotic iterations can be put in the field of discrete dynamical systems:

x 0 ∈ X x n+1 = G f (x n ),
where (X , d) is a metric space and G f is a continuous function. Thus, it becomes possible to study the topological behavior of those chaotic iterations. Precisely, it has been proven that if the iterate function is based on the vectorial logical negation f 0 , then chaotic iterations generate chaos according to Devaney. Therefore chaotic iterations, as Devaney's topological chaos, satisfy: sensitive dependence on the initial conditions, unpredictability, indecomposability, and uniform repartition. Additionally, G f 0 has been proven to be expansive and topologically mixing, and its topological entropy has been computed. Our intention is now to use these chaotic iterations that are highly unpredictable, to build programs in the computer science security field. Furthermore, we will give in Section 1.7 a link between CIs and artificial neural networks, thus it is possible to make them behave chaotically.

Up to now, most of computer programs presented as chaotic lose their chaotic properties while computing in the finite set of machine numbers. The algorithms that have been presented as chaotic usually act as follows. After having received its initial state, the machine works alone with no interaction with the outside world. Its outputs only depend on the different states of the machine. The main problem which prevents speaking about chaos in this particular situation is that when a finite state machine reaches a same internal state twice, the two future evolutions are identical. Such a machine always finishes by entering into a cycle while iterating. This highly predictable behavior cannot be set as chaotic, at least as expressed by Devaney. Some attempts to define a discrete notion of chaos have been proposed, but they are not completely satisfactory and are less recognized than the notions exposed in this paper.

The stated problem can be solved in the following way. The computer must generate an output O computed from its current state E and the current value of an input S, which changes at each iteration (Fig. 1.1). Therefore, it is possible that the machine presents the same state twice, but with two future evolutions completely different, depending on the values of the input. By doing so, we thus obtain a machine with a finite number of states, which can evolve in infinitely different ways, due to the new values provided by the input at each iteration. Thus such a machine can behave chaotically, as defined in the Devaney's formulation.

The practical case of finite strategies

It is worthwhile to notice that even if the set of machine numbers is finite, we deal in practice with the infinite set of strategies that have finite but unbounded lengths. Indeed, it is not necessary to store all of the terms of these strategies in the memory. Only its n th term (an integer less than or equal to N) has to be stored at the n th step, as it is illustrated in the following example. Let us suppose that a given text is input from the outside world into the computer character by character and that the current term of the strategy is computed from the ASCII code of the current stored character. Since the set of all possible texts of the outside world is infinite and the number of their characters is unbounded, we work with an infinite set of finite but unbounded strategies.

In the computer science framework, we also have to deal with a finite set of states of the form B N and as stated before an infinite set S of strategies. The sole difference with the theoretical study is that instead of being infinite the sequences of S are finite with unbounded length, as any reasonable program must obviously finish one day.

The proofs of continuity and transitivity stated previously are independent of the finiteness of the length of strategies (sequences of S). Sensitivity can be proven too in this situation (see Section 1.4.2.2). So even in the case of finite machine numbers, we have the two fundamental properties of chaos: sensitivity and transitivity, which respectively implies unpredictability and indecomposability (see [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], p.50). The regularity supposes that the sequences are of infinite lengths. To obtain the analogous of regularity in the context of finite sets, we can for example define a notion of periodic but finite sequences. Definition 10. A strategy S ∈ S is said to be periodic but finite if S is a finite sequence of length n and if there exists a divisor p of n, p n, such that ∀i n-p, S i = S i+p . A point (E, S) ∈ X is said to be periodic but finite, if its strategy S is periodic finite.

In this situation, (

(p=2) and (2, 2, 2) (p=1), are periodic but finite. This definition can be interpreted as the analogous of periodicity definition on finite strategies. Following the proof of regularity (Section 1.3.2.1), it can be proven that the set of periodic but finite points is dense on X , hence obtaining a desired element of regularity in finite sets, as quoted by Devaney ([13], p.50): "two points arbitrary close to each other could have completely different behaviors, the one could have a cyclic behavior as long as the system iterates while the trajectory of the second could 'visit' the whole phase space". It should be recalled that the regularity was introduced by Devaney in order to counteract the effects of transitivity: two points close to each other can have fundamentally different behaviors.

In the following we explain how to use chaotic iterations in the computer science security field, by using an illustrative example. In this sense, we show two different ways to compute chaotic hash functions, the second one using neural networks.

HASH FUNCTIONS WITH TOPOLOGICAL CHAOS PROPERTIES

In this section, a concrete example of a chaotic program is given in the computer science security field.

Introduction

The use of chaotic maps to generate hash algorithms has seen several developments in recent years. In [START_REF] Fei | A secure digital signature algorithm based on elliptic curve and chaotic mappings[END_REF] for example, a digital signature algorithm based on an elliptic curve and chaotic mapping is proposed to strengthen the security of an elliptic curve digital signature algorithm. Other examples of the generation of a hash function using chaotic maps can be found in, e.g., [START_REF] Wang | One-way hash function construction based on the extended chaotic maps switch[END_REF][START_REF] Xiao | Improving the security of a parallel keyed hash function based on chaotic maps[END_REF][START_REF] Peng | One way hash function construction based on twodimensional hyperchaotic mappings[END_REF]. Neural networks that have learned a continuous chaotic map have been proposed too in recent years [START_REF] Li | A novel hash algorithm construction based on chaotic neural network[END_REF], to achieve hash functions requirements. Note that using any chaotic map does not guarantee that the resulting hash function would behave chaotically too. To the best of our knowledge, this point is not discussed in these referenced papers, however it should be considered as important. We define in this section a new way to construct hash functions based on chaotic iterations. As a consequence of the theory presented before, the generated hash functions satisfy various topological chaos properties. Thus, properties required for hash functions are guaranteed by our approach. For example, the avalanche criterion is deduced from the expansivity property.

A chaotic hash function

In this section, we explain a new way to obtain a digest of a digital medium described by a binary sequence. It is based on chaotic iterations and satisfies various topological chaos properties. The hash value will be the last state of some chaotic iterations: the initial state X 0 , finite strategy S, and iterate function must then be defined.

The initial condition X 0 = (S, E) is composed by a N = 256 bits sequence E and a chaotic strategy S. In the following section, we describe detail how to obtain this initial condition from the original medium.

How to obtain E

The first step of our algorithm is to transform the message in a normalized 256 bits sequence E. To illustrate this step inspired by SHA-1, we state that our original text is: "The original text". Each character of this string is replaced by its ASCII code (on 7 bits). Then, we add a 1 at the end of this string. In the context of Subsection 1.6.2, N = 256, and E is the above obtained sequence of 256 bits: the given message has been compressed into a 256 binary string.

We now have the definitive length of our digest. Note that a lot of texts have the same normalized string. This is not a problem because the strategy we will build depends on the whole text too, in such a way that two different texts lead to two different strategies. Let us now build the strategy S.

How to choose S

To obtain the strategy S, an intermediate sequence (u n ) is constructed from D as follows:

• D is split into blocks of 8 bits. Then u n is the decimal value of the n th block.

• A circular rotation of one bit to the left is applied to D (the first bit of D is put on the end of D). Then the new string is split into blocks of 8 bits another time. The decimal values of those blocks are added to (u n ). • This operation is repeated again 6 times.

It is now possible to build the strategy S:

S 0 = u 0 , S n = (u n + 2 × S n-1 + n) (mod 256).
S will be highly dependent to the changes of the original text, because θ -→ 2θ (mod 1) is known to be chaotic as defined by Devaney's theory [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF].

How to construct the digest

To construct the digest, chaotic iterations are done with initial state X 0 ,

f : 1, 256 -→ 1, 256 (E 1 , . . . , E 256 ) -→ (E 1 , . . . , E 256 ),
as iterate function, and S for the chaotic strategy.

The result of those iterations is a 256 bits vector. Its components are taken 4 bits at a time and translated into hexadecimal numbers, to obtain the hash value:

63A88CB6AF0B18E3BE828F9BDA4596A6A13DFE38440AB9557DA1C0C6B1EDBDBD

To compare, if instead of using the text "The original text" we took "the original text", the hash function returns:

33E0DFB5BB1D88C924D2AF80B14FF5A7B1A3DEF9D0E831194BD814C8A3B948B3

In this paper, the generation of hash value is done with the vectorial Boolean negation f 0 defined in eq. (1.2). Nevertheless, the procedure remains general and can be applied with any function f such that G f is chaotic. In the following subsection, a complete example of the procedure is given. These examples give an illustration of the avalanche effect obtained by this algorithm. A more complete study of the properties possessed by the hash functions and resistance under collisions will be studied in a future work.

Application example

A CHAOTIC NEURAL NETWORK AS HASH FUNCTION

A hash function can be achieved in two stages: the compression of the message (mapping a binary sequence of any length n ∈ N into a message of a fixed length belonging into B N , for a given fixed length N ∈ N) and the hash of the compressed message [START_REF] Li | A novel hash algorithm construction based on chaotic neural network[END_REF]. As several compression functions have yet been proposed to achieve the first stage, we will only focus on the second stage and we will explain how to build a neural network that realize it. This neural network that hashes compressed messages will behave chaotically, as it is defined by the Devaney's theory.

Let us firstly explain how it is possible to build a neural network that behaves chaotically. Consider f : B N -→ N N and a MLP which recognize F f . That means, for all (k, x) ∈ 1; N × B N , the response of the output layer to the input (k, x) is F f (k, x). We thus connect the output layer to the input one as it is depicted in Figure 1.4, leading to a global recurrent artificial neural network (ANN) working as follows [START_REF] Bahi | Building a chaotic proved neural network[END_REF]:

• At the initialization stage, the ANN receives a Boolean vector x 0 ∈ B N as input state, and S 0 ∈ 1; N in its input integer channel i(). Thus, x 1 = F f (S 0 , x 0 ) ∈ B N is computed by the neural network. • This state x 1 is published as an output. Additionally, x 1 is sent back to the input layer, to act as Boolean state in the next iteration. • At iteration number n, the recurrent neural network receives the state x n ∈ B N from its output layer and i (S n ) ∈ 1; N from its input integer channel i(). It can thus calculate x n+1 = F f (i (S n ) , x n ) ∈ B N , which will be the new output of the network.

Obviously, this particular MLP produce exactly the same values than CIs with update function f . That is, such MLPs are equivalent to CIs with f as update function. However, the compression stage of the hash function presented in the previous section can be resumed to making chaotic iterations over the compressed message. As chaotic iterations can be obtained with a neural network, we can thus realize this stage with a (chaotic) neural network. Finally, it is important to remark that the proposed hash function can be implemented into a global neural network, as various compression neural networks can be found in the literature [START_REF] Matthew | Fast text compression with neural networks[END_REF][START_REF] Rudenko | Image compression based on the neural network art[END_REF][START_REF] Cramer | Video compression with random neural networks[END_REF]: we just have to replace our compression stage, inspired by SHA-X, with one of these compression ANN.

CONCLUSION

In this paper, a new approach to compute programs with a chaotic behavior is proposed. This approach is based on the well-known Devaney's topological chaos. The algorithms which are of iterative nature are based on the so-called chaotic iterations. This is achieved by establishing a link between the notions of topological chaos and chaotic iterations. Indeed, we are not interested in stable states of such iterations as it has always been the case in the literature, but in their unpredictable behavior. After a solid theoretical study, we consider the practical implementation of the proposed algorithms by evaluating the case of finite sets. We study the behavior of the induced computer programs proving that it is possible to design true chaotic computer programs.

An application is proposed in the area of information security: a new hash function is presented, the security in this case is guaranteed by the unpredictability of the behavior of the proposed algorithms. The algorithms derived from our approach satisfy important properties of topological chaos such as sensitivity to initial conditions, uniform repartition (as a result of the transitivity), unpredictability, expansivity, and topological mixing. Moreover, its topological entropy is infinite. The results expected in our study have been experimentally checked. The choices made in this first study are simple: compression function inspired by SHA-1, negation function for the iteration function, etc. The aim was not to find the best hash function, but to give simple illustrated examples to prove the feasibility in using the new kind of chaotic algorithms in computer science. Finally, we have shown how the mathematical framework of topological chaos offers interesting qualitative and qualitative tools to study the algorithms based on our approach.

In future work, we will investigate other choices of iteration functions and chaotic strategies. We will try to characterize transitive functions. Other properties induced by topological chaos will be explored and their interest in the information security framework will be deepened.

Fig. 1 . 1 A

 11 Fig. 1.1 A chaotic finite-state machine. At each iteration, a new value is taken from the outside world (S). It is used by f as input together with the current state (E).

  binary value (1111000) of the length of this string (120) is added, with another 1This string is inverted (the last bit is now the first one) and the two new substrings are concatenated. This gives: obtain a multiple of 512, by duplicating this string enough and truncating at the next multiple of 512. This string in which the whole original text is contained, is denoted by D.Finally, we split the new string into blocks of 256 bits and apply the exclusive-or function, obtaining a 256 bits sequence in a manner inspired by the SHA-X algorithms.

  Consider two black and white images of size 64 × 64 in Fig. 1.2, in which the pixel in position (40,40) has been changed. In this case, the hash function returns: (a) Original image. (b) Modified image.

Fig. 1 . 2

 12 Fig. 1.2 Hash of some black and white images.

Fig. 1 . 3

 13 Fig. 1.3 Hash of some grayscale level images.

Fig. 1 . 4 2 =

 142 Fig. 1.4 Example of global recurrent neural network modeling functionF f such that x n+1 = x n+1 1 , x n+1 2 = F f (i(S n ), (x n 1 , x n 2 ))

A Topological Study of Chaotic Iterations Application to Hash Functions


Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Maguy Medlej
email: maguy.medlej@univ-fcomte.fr

Frequency Filtering Approach for Data Aggregation in Periodic Sensor Networks

Keywords: periodic sensor networks, data aggregation, similarity functions, frequency filtering, optimization

This paper presents an energy-efficient technique for data aggregation in periodic sensor networks. We investigate the problem of finding all pairs of nodes generating similar data sets such that similarity between each pair of sets is above a threshold t. We provide a frequency filtering approach to solve this problem. Our experiments demonstrate that our algorithm existing prefix filtering methods in reducing energy consumption.

I. INTRODUCTION

In this paper we present a hierarchical multilevel data aggregation scheme for periodic sensor networks. It aims to optimize the volume of data transmitted thus saving energy consumption and reducing bandwidth on the network level. A first level in-sensor process is done by the nodes themselves. Instead of sending each sensor node's raw data to a base station, the data is cleaned periodically by the sensor node itself before sending it to an aggregator node for a second level of aggregation. At this level, we are interested in exploring a new part of the filtering aggregation problem, by focusing on identifying the similarity between data sets generated by neighboring nodes and sent to the same aggregator. Our objective is to identify similarities between near sensor nodes, and integrate their captured data into one record while preserving information integrity.

Most of the extant work [START_REF] Yu | Distributed data aggregation scheduling in wireless sensor networks[END_REF] has studied the data aggregation as the computation of statistical means and moments, as well as other cumulative quantities that summarize the data obtained by the network. Other works, are query based methods [START_REF] Xu | Processing window queries in wireless sensor networks[END_REF]. A query is generated at the sink and then broadcasted through the network. Some nodes are selected to process the query, while others propagate it, receive partial results, aggregate results, and send them back to the sink. Various algorithmic techniques have been proposed to allow efficient aggregation without increasing the message size [START_REF] Cormode | Holistic aggregates in a networked world: Distributed tracking of approximate quantiles[END_REF]. Some works, such as [START_REF] Chen | Adaptive data aggregation scheme in clustered wireless sensor networks[END_REF], use the clustering methods for aggregating data packets in each cluster separately. In [START_REF] Esnaashari | Data aggregation in sensor networks using learning automata[END_REF], a learning automaton-based data aggregation method in sensor networks is provided. In our previous work [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF], we have shown that existing prefix filtering methods are very complex and not suitable for sensor networks and we proposed a heuristic based on the frequency ordering. In this paper we provide a new prefix filtering method to study the sets similarity in sensor networks. We propose frequency filtering optimization technique, which exploits the ordering of measurements according to their frequencies. A frequency of a measure is defined by the number of occurrences of this measure in the set defined at the first aggregation level. We show through the result that our approach offers significant data reduction by eliminating innetwork redundancy and sending only necessary information to the sink.

The rest of the paper is organized as follows, Section II describes our periodic data aggregation scheme, the local aggregation level and our proposed frequency filtering techniques. Experimental results are given in Section III. Section IV concludes the paper with some directions to a future work.

II. PERIODIC DATA AGGREGATION

Our data aggregation method works in two phases, the first one at the nodes level, which we call local aggregation and the second at the aggregators level. At each period p each node sends its aggregated data set to its proper aggregator which subsequently aggregates all data sets coming from different sensor nodes and sends them to the sink.

A. Local aggregation

In periodic sensor networks, we consider that each sensor node i at each slot s takes a new measurement y is . Then node i forms a new set of captured measurements M i with period p, and sends it to the aggregator. It is likely that a sensor node takes the same (or very similar) measurements several times especially when s is too short. In this phase of aggregation, we are interested in identifying duplicate data measurements in order to reduce the size of the set M i . Therefore, to identify the similarity between two measures, we provide the two following definitions:

Definition 1 (link function): We define the link function between two measurements as:

link(y is1 , y is2 ) = 1 if y is1 -y is2 ≤ δ, 0 otherwise.
where δ is a threshold determined by the application. Furthermore, two measures are similar if and only if their link function is equal to 1.

978-1-4673-0269-2/12/$31.00 c 2012 IEEE Definition 2 (Measure's frequency): The frequency of a measurement y is is defined as the number of the subsequent occurrence of the same or similar (according to the link function) measurements in the same set. It is represented by f (y is ).

For each new sensed measurement (at each slot), a sensor node i searches for the similar measure already captured. If a similar measurement is found, it deletes the new one while incrementing the corresponding frequency by 1. For more details of this algorithm see [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF].

At the end of the period p, each node i will possess a local aggregated set M i . The second step is to send it to the aggregator which in his turn aggregates the data sets coming from different sensor nodes.

B. Frequency filtering aggregation

At this level of aggregation, each aggregator has received k sets of measurements and their frequencies. The idea here is to identify all pairs of sets whose similarities are above a given threshold t. For this reason we use a similarity function which measures the degree of similarity between the two sets and returns a value in [0, 1]. A higher similarity value indicates that the sets are more similar. Thus we can treat pairs of sets with high similarity value as duplicates and reduce the size of the final data set that will be sent to the sink. Researchers can find various similarity functions [START_REF] Sarawag | Efficient exact set-similarity joins. 32nd international conference on Very large data bases[END_REF]. The similarity function selection primarily depends on the application domain. In this paper we will focus on the Jaccard similarity, a commonly used function to define similarity between two sets M i and M j as:

J(Mi, Mj) ≥ t ⇔ |Mi ∩s Mj| ≥ α = t 1 + t .(|Mi| + |Mj|) (1)
where "∩ s " is a new function for overlapping defined as: Definition 3: Consider two sets of measurements M 1 and M 2 , then we define:

M 1 ∩ s M 2 = {(y 1 , y 2 ) ∈ M 1 × M 2/link(y 1 , y 2 ) = 1};
1) Sets similarity computation: In this section we provide techniques for computing the similarity between the received sets. A naïve method to compute the similarity of received data (sets) is to enumerate and compare every pair of sets. This method is obviously prohibitively expensive for large data sets (such the case of sensor networks), as total number of comparison is O(n 2 ).

To reduce the number of comparisons between sets a prefix filtering method has been proposed. Several approaches for traditional similarity join between sets are based on the prefix filtering principle [8] [6]. This method is based on the intuition that if all sets of measures are sorted by a global ordering, some fragments of them must share several common tokens with each other in order to meet the threshold similarity. An inverted index maps a given measurement m to a list of identifiers of sets that contain m i such that link(m i , m) = 1. After inverted indices for all measures in the set are built, we can scan each one, probe the indices using every measure in the set M , and obtain a set of candidates; merging these candidates together gives us their actual overlap with the current set M ; final results can be extracted by removing sets whose overlap with M is less than 1). This intuition is formalized by the following Lemma inspired from [START_REF] Chaudhuri | A primitive operator for similarity joins in data cleaning[END_REF]:

⌈ t 1+t .(|M i | + |M j |)⌉(Equation
Lemma 1: Consider two sets of sensor measures M i and M j , such that their elements are ordered by a global defined ordering. Let the p-pref ix be the first p elements of

M i . If |M i ∩ s M j | ≥ α, then the (|M i |-α+1)-pref ix of M i and the (|M j | -α + 1
)-pref ix of M j must share at least one element.

Proof: Lemma 1 can be proven similarly to the lemma of page 6 in [START_REF] Chaudhuri | A primitive operator for similarity joins in data cleaning[END_REF].

To ensure the prefix filtering based approach does not miss any similarity set result, as shown in Lemma 1 we need a prefix of length |M i | -⌈t.|M i |⌉ + 1 for every set M i [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF]. The prefix filtering algorithm for finding similarity sets takes as input a collection of datasets coming from different sensor nodes already sorted according to a defined ordering. It scans sequentially each set M i , selects the candidates that intersects with its prefix. Afterwards, M i and all its candidates will be verified against the jaccard similarity threshold to finally return the set of correct similar measurements sets. For more details of the prefix filtering algorithm refere to [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF].

Prefix filtering algorithm helps prune out unfeasible sets of measures, however, in practice the number of nonsimilar sets surviving after this technique is still quadratic growth [START_REF] Xiao | Efficient similarity joins for near duplicate detection[END_REF]. Following the prefix filtering, many optimization methods [START_REF] Xiao | Efficient similarity joins for near duplicate detection[END_REF], [START_REF] Xiao | Top-k set similarity joins[END_REF] were proposed to prune out further the unfeasible non-similar sets. A trade-off of these prefix filtering optimizations is that usually require more computational efforts which is unsuitable by heavy resources sensor networks. In our approach, we provide some optimizations for prefix filtering techniques based on measures frequency while taking into account this trade-off.

2) Frequency filtering approach: Let us introduce some definitions and notations which will be the basis of what follows. In periodic sensor networks, two data sets are similar if their measurements overlap with each other, and especially the ones having higher frequencies values.

Definition 4 (Ordering O): We define an ordering O which arranges the measurements of a given set by the decreasing order of their frequencies.

For two similar measures m i and m j such that link(m i , m j ) = 1, we denote f min (m i , m j ) = M in(f (m i ), f (m j )) the minimum value of the frequency of these measures.

Definition 5 (f s (M i , M j )): Consider two sets of measures M i and M j , we define

f s (M i , M j ) = Os(Mi,Mj ) k=1 (f min ((m i , m j ) ∈ M i ∩ s M j )).
In this paper, we consider that all sensor nodes operate with the same sampling rate, and every node captures τ measures with each period p. Thus we can deduce that for every received set M i from node i we have:

|Mi| k=1 (f (m k ∈ M i ) = τ .
Using the Jaccard similarity function, two sets M i and M j are similar if and only if: 1)). Supposing that the sets were sent to the aggregators without applying the first aggregation phase and without computing measures frequencies, thus we can observe that:

O s (M i , M j ) ≥ α where α = t 1+t .(|M i |+|M j |) (Equation (
|M i | = |M j | = τ and f s (M i , M j ) = O s (M i , M j ). (2)
Hence, from Equation (1) and Equation ( 2) we can deduce that:

M i and M j are similar iff: f s (M i , M j ) ≥ 2 × t × τ 1 + t . (3)
Lemma 1 states that the prefixes of two sets of measures must share at least one measure in order to satisfy the prefix filtering condition (P F C). Nevertheless, in sensor networks this condition is easily satisfied. In this section, we will present an extension of the prefix filtering technique making the P F C condition more difficult to be satisfied.

Lemma 2: Assume that all the measures in the sets M i and M j are ordered according to the global ordering O. Let the ppref ix be the first p elements of

M i . If f s (M i , M j ) ≥ 2×t×τ 1+t , then f s (p-M i , p-M j ) ≥ |p-Mi| k=1 (f (m k ∈ p-M i )) -1-t 1+t × τ . Proof:
We denote by p-M i the prefix of the set M i and r-M i the set of reminder measures where M i = {p-M i +r-M i }. We have:

f s (M i , M j ) = f s (p-M i , M j ) + f s (r-M i , M j ) = f s (p-M i , p-M j ) + f s (p-M i , r-M j ) + f s (r-M i , M j ) ∼ = f s (p-M i , p-M j ) + f s (r-M i , M j ) ≤ f s (p-M i , p-M j ) + |r-Mi| k=1 (f (m k ∈ r-M i ))
In the second line we can omit the term f s (p-M i , r-M j ) because we have assumed that it is negligible compared to the other terms in the equation. Indeed, if the two sets are similar then the measures having highest frequencies must be in the prefix set and not in the reminder, which means that the overlapping between the p-M i and r-M j is almost empty. From the above equations and equation (3)(similarity condition) we can deduce:

2 × t × τ 1 + t ≤ f s (p-M i , p-M j ) + |r-Mi| k=1 (f (m k ∈ r-M i )) (4)
From the following equation:

|p-Mi| k=1 (f (m k ∈ p-M i )) + |r-Mi| k=1 (f (m k ∈ r-M i )) = τ (5)
We obtain:

f s (p-M i , p-M j ) ≥ |p-Mi| k=1 (f (m k ∈ p-M i )) - 1 -t 1 + t × τ (6)
The lemma is proved. Algorithm 1 describes our method to find similar sets of measures based on the frequency filtering approach. It is a hybrid solution, where we integrate our frequency condition presented in Lemma 2 to the prefix filtering approach.

Algorithm 1 Frequency-filtering based algorithm.

Require: of measures' sets M = {M1, M2...Mn}, t, τ . Ensure: All pairs of sets (Mi, Mj), such that J(Mi, Mj)

≥ t. S ← ∅ Ii ← ∅ (1 ≤ i ≤ total number of measures) for each set Mi ∈ M do p ← |Mi| -⌈t × |Mi|⌉ + 1 F s ← empty map from set id to int sumF req ← 0 for k ← 1 to p do sumF req ← sumF req + f (m k ∈ p-Mi) end for for k ← 1 to p do w ← Mi[k] if (Iw s exists such that link(w, ws) = 1) then for each Measurement (Mj[l]), f (Mj[l]) ∈ Iw s do F s[Mj] ← F s[Mj] + fmin(Mi[k], Mj[l]) end for Iw s ← Iw s ∪

III. EXPERIMENTAL RESULTS

To evaluate our approach, we conducted multiple series of simulations using the discrete event simulator OM-NET++ [START_REF]OMNeT++[END_REF]. The objective of these simulations is to confirm that our frequency filtering technique can successfully achieve desirable results for data aggregation in periodic sensor networks. Therefore, in our simulations we used real readings collected from 45 sensor nodes deployed in the Intel Berkeley Research Lab [START_REF] Madden | [END_REF]. Every 31 seconds, sensors with weather boards were collecting humidity, temperature, light and voltage values. Each node senses an average of 90000 values of each measurement per day and per field. For the sake of simplicity, in this paper we are interested in one field of sensor measurements: the temperature 1 We performed several runs of the algorithms (an average of 15 runs).

In the first series of simulations, each node runs local aggregation with every new reading. Then, it generates an aggregated set composed of non-similar measurements assigned by their frequencies. We varied the threshold δ and the number 1 the others are done by the same manner We noticed the cardinality decreases when δ increases, which means that when we stretch the similarity constraint we eliminate more similar measurements. The goal of this stage is to reduce the number of measurements sent by nodes. The experimental results show that at least w reduced the sent set by 30%.

We compared the number of candidates (number of comparisons) generated respectively by our frequency filtering technique, the prefix filtering algorithm and the results obtained after applying the Jaccard similarity function. In these series of simulations we varied the parameter τ (the size of datasets) while fixing the threshold δ to 0.05. The obtained curves are shown in figures 1, 2 and 3. Observing the obtained result, we divide them into two groups according to τ . First, consider the results on small dataset where τ = 2.E + 03 as shown in figure 1. We notice that, when the similarity threshold increases from 0.7 to 0.9, the number of comparisons of the frequency filtering and the prefix filtering becomes closer. In the next step, consider another group of datasets with big size (τ = 4.E + 03 and τ = 6.E + 03). The obtained results are shown in 2 and 3. We observe that when the sets cardinality increases the number of candidates also increases.

IV. CONCLUSION AND FUTURE WORK

In this paper we proposed a new frequency filtering approach and several optimizations using sets similarity func-tions to find similar data sets generated by sensor nodes. The objective of our approach is to reduce the number of redundant data sent to the end user while preserving the data integrity. It was shown through simulations on real data measurements that our method reduces drastically the redundant sensor measures and outperforms the existing prefix filtering approaches. Thus, it saves energy and improves the overall network lifetime. A direction for future work is to develop a new suffix frequency filter algorithm beside the frequency filtering approach proposed in this paper. Our goal is to use additional filtering method that prunes erroneous candidates that survive after applying the prefix and frequency filtering technique.

Fig. 3 .Fig. 4 .

 34 Fig. 1. τ = 2.E + 03


Wahabou Abdou

Christelle Bloch

Damien Charlet

François Spies

Multi-Pareto-Ranking Evolutionary Algorithm

Keywords: Multiobjective optimization, genetic algorithm, Pareto ranking, multiple fronts

This paper proposes a new multi-objective genetic algorithm, called GAME, to solve constrained optimization problems. GAME uses an elitist archive, but it ranks the population in several Pareto fronts. Then, three types of fitness assignment methods are defined: the fitness of individuals depends on the front they belong to. The crowding distance is also used to preserve diversity. Selection is based on two steps: a Pareto front is first selected, before choosing an individual among the solutions it contains. The probability to choose a given front is computed using three parameters which are tuned using the design of experiments. The influence of the number of Pareto fronts is studied experimentally. Finally GAME's performance is assessed and compared with three other algorithms according to the conditions of the CEC 2009 competition.

Introduction

Many multi-objective evolutionary algorithms (MOEAs) use an elitist archive based on Pareto domination. The main difficulty of these MOEAs often lies in maintaining diversity. Thus, various solutions have been proposed as the crowding distance [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF], metrics based on diversity [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF] or specific definitions of fitness [START_REF] Eskandari | FastPGA: A dynamic population sizing approach for solving expensive multiobjective optimization problems[END_REF]. In the same way, the algorithm proposed in this paper, named Genetic Algorithm with Multiple parEto sets (GAME), rests on the concept of Pareto ranking. But it uses several Pareto fronts to rank individuals. Besides, the formula used to compute the fitness of individuals varies according to the set they belong to. Finally selection operators (for reproduction and for replacement) work in two steps: selecting one of the Pareto sets and selecting one individual in this set. The probability that each Pareto set is selected both depends on its rank and its size. Individuals belonging to the selected Pareto set are then compared using a fitness-based tournament. Defining various kinds of fitness depending on the non-domination rank preserves both quality and diversity. Section 2 quickly describes previous work related to this subject : some classical MOEAs based on Pareto archives, tuning parameters and managing constraints in such algorithms. Section 3 details the proposed algorithm itself. Section 4 first explains how the parameters used to define the selection probability of each Pareto front are tuned using the design of experiments. This section then experimentally studies the benefit obtained by using several Pareto fronts. Finally that section presents the experiments performed to validate this approach, particularly the algorithms compared with it in accordance with the CEC2009 competition conditions, and the assessment of GAME efficiency. Section 5 concludes by highlighting and gives the main prospects of this work.

2 Multi-objective evolutionary algorithms (MOEAs) in literature

Pareto-based MOEAs

Among several evolutionary algorithms which archive non-dominated solutions, we can cite Strength Pareto Evolutionary Algorithm 2 (SPEA2) [START_REF] Zitzler | Spea2: Improving the strength pareto evolutionary algorithm[END_REF] or a newer method such as the Fast Pareto Genetic Algorithm (FastPGA) [START_REF] Eskandari | FastPGA: A dynamic population sizing approach for solving expensive multiobjective optimization problems[END_REF].

SPEA2 is an elitist multi-objective evolutionary algorithm that relies on Pareto-based and archiving techniques. SPEA2 assigns a strength to each S solution of the current population and the archive. This strength represents the number of solutions dominated by S. The fitness of each solution equals the summation of the strength of solutions that it is dominated by. When two solutions have the same fitness value, they are discriminated according to a metric based on the density (an adaptation of the k-th nearest neighbor method) [START_REF] Silverman | Density estimation: for statistics and data analysis[END_REF].

FastPGA divides the solutions of the current population into two fronts (nondominated and dominated sets) using the Pareto dominance principles. The fitness of non-dominated solutions is calculated using the crowding distance proposed by Deb et al. [START_REF] Deb | Multi-objective Optimization Using Evolutionary Computation[END_REF]. For solutions in the dominated front, FastPGA uses an extension of SPEA2's fitness assignment method. Indeed, the fitness of each dominated solution equals the summation of the strength values of all the solutions it dominates minus the summation of the strength values of all the solutions by which it is dominated. This reduces the chances that two solutions may have the same value of fitness. FastPGA also uses a specific mechanism to regulate population size over generations.

Tuning of MOEA parameters

Evolutionary algorithms include several parameters the tuning of which is generally difficult. Their values might significantly impact the quality of the solutions provided by the algorithm. A high mutation probability for instance would favor diversity and limit the exploitation of zones where good solutions may have been found. The algorithm would then nearly behave like a random search strategy. Such parameters are often tuned empirically. But it is difficult to find values which are both suitable and robust (i.e. achieving good enough performance without being too sensitive to the tackled optimization problems). This approach often requires a great number of executions and the knowledge of a human decision-maker to select appropriate values. That is why, in recent years, several approaches have been proposed to design and/or tune EAs statistically in order to better guarantee their performance and/or robustness [START_REF] Hippolyte | Tuning an evolutionary algorithm with taguchi methods[END_REF] [2].

Constraint-handling in MOEAs

Some optimization problems include constraints associated with the search space (set of variables) or the objective space (set of objective functions). Only points that satisfy these constraints are considered as feasible solutions of the optimization problem. Michalewicz and Schoenauer [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] define the types of approaches to handle such constraints in EAs. There are methods that preserve solution feasibility whenever possible. They use some operators (crossover and mutation) which only create solutions belonging to the set of feasible solutions. There also exists methods that include a penalty function in the calculation of the fitness of each solution. This allows to weaken the fitness of solutions that violate constraints. Another approach to handle constraints combine evolutionary algorithms and other optimization methods. They may repeatly use EAs. For instance, Surry et al. [START_REF] Surry | A multi-objective approach to constrained optimisation of gas supply networks: The comoga method[END_REF] rank individuals according to both objective values and constraint violations, which amounts to adding some objectives to the problem.

The genetic algorithm proposed in this paper uses a penalty-based approach to manage the constraints (see section 3.1). In addition, this algorithm uses both the computation of several Pareto fronts like NSGA-II and a definition of fitness which is different for each front like SPEA 2. The proposed solution combines the advantages of these two famous algorithms. Nevertheless contrary to NSGA-II structuring the population in several Pareto fronts is not only used for the replacement selection, it also impacts the recombination process. These characteristics have led to the implementation of a new selection strategy that takes into account the multiplicity of fronts and the fitness functions that depend on rank of the front. The benefit related to the number of fronts and the tuning of this new selection process parameters have been studied statistically.

The following section describes the proposed algorithm while particularly detailing its main characteristics.

A multiple-Pareto-ranking genetic algorithm.

The proposed algorithm includes a wide-ranking process and a specific method of fitness assignment. The main goal of these operations is both to ensure a good exploration of the space search and the convergence toward the optimal solution(s). This algorithm is named Genetic Algorithm with Multiple parEto sets (GAME). It rests on a classical global scheme and is quite like other MOEAs developed in literature. Initial population is generated randomly. Individuals represent solutions which are made of several integer or float variables, using binary simulated encoding. This representation is quite classical [START_REF] Srinivas | Genetic algorithms: A survey[END_REF]: each variable is represented as a binary chain. The chain length (number of bits) depends on the wished precision. For instance, when representing a variable that takes values in the interval [0; 10], with a precision equals to 10 -2 , requires 10 bits. The chains 0000000000 and 1111111111 will respectively represent 0 and 10. 1,23 will be encoded as 0001111110.

Crossover and mutation operators are also commonly used in this kind of representation. They are 2-point crossover and bitflip mutation [START_REF] Deb | Multi-objective Optimization Using Evolutionary Computation[END_REF]. GAME also uses parallel , based on master-slave model [START_REF] Cantú-Paz | Efficient and Accurate Parallel Genetic Algorithms[END_REF].

Besides, GAME differs from well-known MOEAs in several ways. These differences deal with the following steps: the ranking of individuals, based on Pareto dominance (3.1), fitness assignment (3.2), and the associated selection strategies for both recombination and replacement (3.3).

Ranking

GAME uses the objective values computed at the evaluation step to rank individuals. This ranking is based on the principle of non-dominated sorting (Pareto dominance). Pareto solutions are those for which improvement in one objective implies the worsening of at least one other objective. All the non-dominated individuals are added to the first Pareto front P F 1 . This process is repeated successively three times with the remaining subset of individuals to build the second, the third and the fourth Pareto fronts (P F 2 , P F 3 and P F 4 ). Finally, the remaining subset solutions are gathered in the set of dominated solutions P F 5 .

When the problem has some constraints, they are handled during the construction of the Pareto fronts. GAME uses a penality-based method to take constraints intoaccount. In order to preserve the primacy of solutions which respect the limits, those which violate them are banned in the first Pareto front. However, when P F 1 is empty, solutions that do not satisfy the constraints can be accepted. This situation often occurs in the first generations. But it is quickly corrected as the solutions which respect the constraints have a higher probability of reproduction and thus transmit their characters to their offspring.

Fitness assignment

Since it is not obvious to compare two solutions in the same Pareto front (improvement in an objective is always to the detriment of at least one other), a fitness value is assigned to each solution.

The computation of the value of fitness depends on the Pareto rank of the solution. GAME distinguishes three types of fitness: one for the best solutions (the archive of non-dominated solutions and the first Pareto front), the second for the solutions of the second Pareto front and the third one for the other fronts. These fitness values are only used within the same front. The fitness of two individuals of different fronts cannot be compared. In this case, the comparison will only focus on the ranks of their respective fronts.

Fitness for the archive and the first Pareto front solutions. During the execution of GAME, the first Pareto front (P F 1 ) contains the best solutions of the current population. The archive of non-dominated solutions contains all the best solutions evaluated since the first generation. Note that a solution of P F 1 can dominate some solutions in the archive. These two sets represent solutions that are closest to the optimal solutions (P F * ). While trying to get closer to P F * , the algorithm must preserve diversity in the best solutions set. GAME assigns to the archived solutions and P F 1 a fitness based on the crowding distance [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] which is a diversity indicator. This indicator provides information on the distribution of solutions in the front. To avoid bias due to the sizes of ranges of the objective functions, GAME uses a normalized crowding distance.

Fitness for the second Pareto front solutions. The solutions of the second Pareto front (P F 2 ) are the second best set of solutions in a population. GAME favors solutions of the P F 2 that are closest to P F 1 . The convergence indicator used to measure the proximity of solutions of the two fronts is the Generational distance. Using this indicator as fitness enables the solutions of P F 2 that are closest to P F 1 to have a greater probability to be selected for recombination and/or replacement.

Fitness for the remaining solutions For solutions that do not belong to any of the three previous sets (archive of non-dominated solutions, first and second Pareto fronts), a new indicator is used to calculate the values of fitness. This is the gain (see Equation 1).

The gain of an -→ x i solution with respect to -→ x j in accordance with the f k objective function is called gain( -→ x i , -→ x j , k). It expresses the improvement provided by -→ x i in comparison to -→ x j in the selected function. The gain varies from -1 to 1.

A negative value indicates that the first solution is worse than the second one according to f k . A null gain means that both solutions are equivalent.

gain( - → x i , - → x j , k) = λ(f k ( - → x i ) -f k ( - → x j )) M ax(f k ( - → x i ), f k ( - → x j )) ( 1
)
where λ is a coefficient: 1 for a maximization problem; -1 for a minimization. The fitness of each individual is the sum of gains (for all objectives) compared to other solutions in the same front (see Equation 2).

f itness( - → x i ) = |P F | j=1 m k=1 gain( - → x i , - → x j , k) (2)
where |P F | is the Pareto front size and m the number of objectives functions.

Selection operator

To ensure both exploration and exploitation, a kind of fitness is associated to each Pareto front. This is actually a selection probability of the front. Indeed, GAME selects individuals in two steps. The first one consist in selecting a Pareto front within the five built. Then, a solution is chosen from those belonging to the front using a binary tournament selection.

The selection of Pareto fronts is based on a biased roulette wheel where the part of each front depends on both its rank and its cardinality. The probability of selection associated with each front is given by equation 3.

P (P F i ) = δ(P F i ) * |P F i | n i=1 [δ(P F i ) * |P F i |] (3)
where: P (P F i ) is the probability of selection associated with the i th Pareto front. |P F i | is the cardinality of P F i . n is the total number of Pareto fronts. δ(P F i ) indicates a priority level associated with each front (see Equation 4).

δ(P F i ) = a(n -i) + b (4)
The coefficients a and b must be carefully chosen to preserve diversity within the sets of solutions (successive populations and archive), while improving individuals over generations. These parameters may differ for recombination and replacement. Therefore, the coefficients associated with recombination selection are named a and b, whereas those used in replacement selection are a and b (see Section 4.1).

Using both δ(P F i ) and the cardinality ensures the selection of the best solutions, prevents the dominated solutions from having very low values of fitness and preserves the diversity of the successive populations.

The utility and the efficiency of the proposed ranking mode and selection process were experimentally validated. This experimentation first studied the tuning of a, b, a and b for a given number of Pareto fronts. Secondly, a preliminary test phase focused on the sensitivity of GAME to the used number of Pareto Fronts, for the tuned values of δ(P F i ).

It is worth noting that besides its specific characteristics, presented in this section, GAME uses a parallel evaluation process based on a master-slave model [START_REF] Cantú-Paz | Efficient and Accurate Parallel Genetic Algorithms[END_REF]. The parallelization allows GAME to tackle problems with complex objective functions or with objective functions requiring simulation to assess their values. A variant of GAME, named ESBEA, has been applied, for instance, to a constrained optimization problem containing four objective functions evaluated by simulation, in the field of ad hoc mobile communication networks [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF].

In this paper, the performance of GAME was assessed by comparison with previous results in literature. The following sections describe experimental conditions and summarize the main results.

Validation and experimental results

The experiments described in the following subsections aim at:

tuning the probabilities associated with Pareto sets; validating the interest to have multiple Pareto fronts;

assessing the performance of GAME compared with other methods presented in literature.

All experiments were performed on the optimization problems proposed in the CEC 2009 [START_REF] Zhang | Multiobjective optimization test instances for the cec 2009 special session and competition[END_REF] competition, more particularly bi-objective constrained problems, according to the experimental conditions defined in this competition. These problems are detailed in [START_REF] Zhang | Multiobjective optimization test instances for the cec 2009 special session and competition[END_REF].

GAME has been implemented using jMetal [START_REF] Durillo | jmetal: A java framework for multi-objective optimization[END_REF], a platform for the development, experimentation and study of metaheuristics. A population size equals to 100 and 300 generations were used to perform the 30,000 evaluations required for each execution in the CEC 2009 competition. Crossover rate and mutation rate were respectively equal to values recommended in literature: 0.8 and 1 N umber of variables (in order to limit the number of parameters in the parameter study and focus on those involved in the proposed mechanisms).

Tuning GAME's parameters

A parametric study based on the design of experiments (DOEs) has been performed to tune the priority assigned to each Pareto front built by GAME. DOEs permit to get a lot of information on parameters1 and study their influence, while carrying out a minimum of tests [START_REF] Box | Statistics for experimenters. Design, innovation, and discovery[END_REF].

The whole campain of tests has been based on JMP (9 Pro version)2 , a statistical software for expert data analysis, to create DOE and to analyze the provided results. This software has been used to create some test tables, in which each line corresponds to a given combination of the factors (in this case, a, b, a and b presented in Section 3.3) defining a given test. For each of these tests, two indicators (IGD and Maximum Spread [START_REF] Deb | Multi-objective Optimization Using Evolutionary Computation[END_REF]) have been used to measure the quality of the studied combination of parameters 3 .

This parameter tuning was performed with a number of Pareto fronts set at 5, by varying a, b, a and b between 0 and 10 (integer values). JMP has generated a partial DOE table consisting of 44 tests to be performed. The benchmark used for these tests was Constrained Problem 1.

Figure 1 shows the results returned by JMP. For IGD and Maximum Spread indicators, the first four curves show the variations of these indicators based on the values taken by each factor. The last column gives a desirability function (for each indicator) with values between 0 and 1. A desirability value of 1 indicates that the used parameter values enable to get the optimal level for the considered indicator. In this parameter tuning, the desirability according to the IGD decreases when the IGD reaches high values. That is the inverse of the Maximum Spread. The last row of curves shows the levels of desirability with respect to both the IGD and Maximum Spread indicators.

Based on these results, the best value of desirability is achieved when a = 6, b = 5, a = 5 and b = 4. To measure the benefits of multiple Pareto fronts, four versions of GAME are compared, using the values of δ(P F i ) tuned with JMP. The first version builds two Pareto fronts (like classical algorithms). This version will serve as a reference.

The other three versions build 3, 4 and 5 fronts. These values were chosen to study a steady increase of the number of fronts while limiting the duration of experimentations. They are compared to the "2 front" version in the constrained problem 1 of the CEC 2009 competition. The comparison focuses on convergence (IGD) and diversity (Maximum Spread ) indicators. Since the generation of the initial population of GAME does not use specific heuristics, individuals are created randomly. Therefore, the best of them often are of fair quality. This results in a relatively high value of the IGD in the first generations (see Figure 2). Fast enough, solutions that are better suited to the problem are produced (by recombination) and eliminate the worst individuals in the archive. This explains the sharp decrease in the IGD in the first 25 generations. Thereafter, the curves of the IGD continue to decline steadily but with a much lower slope. Beyond this behavior common to all scenarios, these results allow us to observe that the increase in the number of fronts improves the quality of final solutions in terms of proximity to the optimum. During the first few generations, the Maximum Spread has relatively high values (see Figure 3). This can be explained by the fact that the archive contains solutions that do not meet constraints. Indeed, the inclusion of such solutions stretches the front beyond the boundaries that are set by the constraints of the problem. The archive built by GAME is then refined, when solutions which respect the constraints and have good values of objective functions are found. This explains the drop in the Maximum Spread in the early generations. After the fall phase, the Maximum Spread is growing slightly. In addition, the slight variations in the curves of Maximum Spread over generations indicates that the archive is updated regularly. New non-dominated solutions are continually being discovered. If initially all scenarios have the same behavior, one can observe that after a few dozen generations, the impact of multiple fronts becomes substantial.

Performance assessment

The performance of GAME was assessed as if it had taken part in the CEC 2009 competition, in the "Constrained problems" category. This category includes biobjective problems where the two objectives are to be minimized. Each problem includes 10 real-valued decision variables. GAME was compared to the three algorithms which got the best results in this category, using the same experimental conditions and the same performance criterion:

for each constrained problem, 30 independent executions limited to 30,000 evaluations must be performed for each algorithm; then the mean value of IGD indicator (computed in the sets of final solutions for the 30 independent executions) must be used as comparison criterion. The IGD is to be minimized.

Table 1 provides, for the exhaustive list of bi-objective problems of the competition, the average of the IGD values obtained by the three compared algorithms: DMOEA-DD [START_REF] Liu | Performance assessment of dmoea-dd with cec 2009 moea competition test instances[END_REF], LiuLi [START_REF] Liu | The multiobjective evolutionary algorithm based on determined weight and sub-regional search[END_REF] and MTS [START_REF] Tseng | Multiple trajectory search for unconstrained/constrained multi-objective optimization[END_REF]. These results permitted these algorithms to respectively reach the first rank, the second rank and the third rank during the CEC 2009 competition.

DMOEAD-DD (Dynamical Multiobjective Evolutionary Algorithm -Domain Decomposition) improves DMOEA [START_REF] Zou | A new evolutionary algorithm for solving many-objective optimization problems[END_REF] that used an aggregated fitness function including the notion of Pareto dominance, entropy and density (based on crowding distance). In the improved variant, authors split the search space into several subsets. DMOEA computes Pareto fronts for each of them. Genetic operators permit information exchange between these subsets.

LiuLi (concatenation of the authors'name : Hai-Lin Liu and Xueqiang Li) splits the search space into sub-areas in order to reduce algorithm complexity. Genetic operations, particularly reproduction, are performed in a single sub-area. Information exchange between areas is based on children, because they may be assigned to other areas.

MTS (Multiple Trajectory Search) is an algorithm based on three local search methods. For each solution, MTS determines the method which corresponds to its neighborhood. This algorithm begins with a large search. The size of neighborhood is progressively reduced until it reaches a given minimal size. Then its size is set to its initial value and the regression re-starts. 1. Mean values of IGD returned by GAME and the algorithms which participated to CEC2009 competition Besides, GAME has been tested in the same conditions and the results it provided were added in table 1. This study shows that, globally, GAME reaches solutions which are quite close to the reference front. This results in low IGD values in table 1. Moreover, in a large majority of cases, GAME provides better results than those returned by the three best algorithms in the competition (in the "constrained problems" category).

Conclusion

To sum up, GAME is an elitist multi-objective genetic algorithm, based on the building of multiple Pareto fronts. This ranking strategy and the associated 2step selection provided gains both in terms of proximity with optimal solutions and in terms of diversity in the set of final solutions returned by GAME. Finally, using the experimental conditions of the CEC 2009 competition showed that it would have been quite well ranked in this competition, which constitutes a promising result. In addition, GAME uses a parallel evaluation procedure based on a master-slave model. Although this model allowed the reduction in terms of the duration of the experimentations in previous work in the field of mobile networks [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF]. Nevertheless, designing an asynchronous version of GAME would be very interesting. Such a version would no longer rely on an architecture where the master must wait until all the slaves have finished their task before building the next generation. Two other prospects are planned for this work. First, GAME should be applied in various real-life fields to test its sensitivity to the tackled problems more widely. This would permit to prove the genericity of the results provided in this paper. Besides, the authors are working on an adaptive version of GAME. This aims at making it more robust with regards to problem characteristics, rather than using statistically tuned parameters without varying the algorithm behavior during execution.

Fig. 1 .

 1 Fig. 1. Tuning the selection coefficients

  Fig. 2. IGD

Fig. 3 .

 3 Fig. 3. Maximum spread

In DOEs these parameters are called factors

http://www.jmp.com

The measured values are also called responses.


Achille Lerpiniere

Jean-François Caron

Validation of LS1

teaching and research institutions in France or abroad, or from public or private research centers.

The aim of this paper is to propose an efficient and accurate alternative to the computationally expensive three-dimensional finite element method (3D-FEM), for analyzing delaminated multilayered plates under classical loads. Many of the existing models deal with the analysis of multilayered structures only in the non-delaminated state.

The first part of the present study extends the application of a layerwise stress model, called the LS1 model, to delaminated multilayered plates subjected to mode I and/or II loads.

The analytical LS1 solutions are derived for general non-delaminated and delaminated multilayers and compared to 3D finite element solutions along with the results from the 2D-FEM code based on the LS1 (fig. 1). The comparison gives a good agreement between the LS1 and 3D-FE models except near singularities (free edges, crack tips,...).

In order to overcome this drawback, a refinement approach, called the refined LS1 [1], will be shortly presented. The comparison between the refined LS1 and 3D-FE models reveals an excellent agreement, even in the vicinity of singularities, in terms of interlaminar stresses and strain energy release rate.

An interfacial stress based criterion arising from an energy power-law [2] one by using the LS1 model [3] will be proposed. Mode separation will be analytically deduced from the interfacial stresses (tab. 1).

Fig. 1 .

 1 Fig. 1. Interfacial pullout for ADCB18 test specimen (MPa)

Validation du modèle LS1 pour la propagation d'un délaminage aux interfaces 0°/θ°V alidation of LS1 model for delamination propagation at 0°/θ° interfaces Achille Lerpiniere 1 , Jean-François Caron 2

	1 : Universite Paris-Est, Laboratoire Navier
	Ecole des Ponts ParisTech, IFSTTAR, CNRS
	6 av Blaise Pascal, 77455 Champs/Marne
	e-mail : achille.lerpiniere@polytechnique.edu
	2 : Universite Paris-Est, Laboratoire Navier
	Ecole des Ponts ParisTech, IFSTTAR, CNRS
	6 av Blaise Pascal, 77455 Champs/Marne
	e-mail : caron@enpc.fr

Tab. 1. Average experimental and finite element values for ADCB18 test specimen

Références