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

Xiaole Fang
email: xiaole.fang@univ-fcomte.fr

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

An optimization technique on pseudorandom generators based on chaotic iterations

Keywords: Internet security, Pseudorandom Sequences, Statistical Tests, Discrete Chaotic Iterations, Topological Chaos

Internet communication systems involving cryptography and data hiding often require billions of random numbers. In addition to the speed of the algorithm, the quality of the pseudo-random number generator and the ease of its implementation are common practical aspects. In this work we will discuss how to improve the quality of random numbers independently from their generation algorithm. We propose an additional implementation technique in order to take advantage of some chaotic properties. The statistical quality of our solution stems from some well-defined discrete chaotic iterations that satisfy the reputed Devaney's definition of chaos, namely the chaotic iterations technique. Pursuing recent researches published in the previous International Conference on Evolving Internet (Internet 09, 10, and 11), three methods to build pseudorandom generators by using chaotic iterations are recalled. Using standard criteria named NIST and DieHARD (some famous batteries of tests), we will show that the proposed technique can improve the statistical properties of a large variety of defective pseudorandom generators, and that the issues raised by statistical tests decrease when the power of chaotic iterations increase.

I. INTRODUCTION

Chaos has recently attracted more and more interests from researchers in the fields of mathematics, physics, and computer engineering, among other things due to its connection with randomness and complexity [START_REF] Behnia | A novel dynamic model of pseudo random number generator[END_REF], [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF]. In particular, various research works have recently regarded the possibility to use chaos in random number generation for Internet security. Indeed, the security of data exchanged through the Internet is highly dependent from the quality of the pseudorandom number generators (PRNGs) used into its protocols. These PRNGs are everywhere in any secure Internet communication: in the keys generation of any asymmetric cryptosystem, in the production of any keystream (symmetric cryptosystem), the generation of nonce, in the keys for keyed hash functions, and so on.

Numerous pseudorandom number generators already exist, but they are either secure but slow, or fast but insecure. This is why the idea to mix secure and fast PRNGs, to take benefits from their respective qualities, has emerged these last years [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], [1]. Chaotic dynamical systems appear as good candidates to achieve this mixture for optimization. Indeed, chaotic systems have many advantages as unpredictability or disorder-like, which are required in building complex sequences [START_REF] Hu | A true random number generator based on mouse movement and chaotic cryptography[END_REF], [START_REF] De Micco | Randomizing nonlinear maps via symbolic dynamics[END_REF]. This is why chaos has been applied to secure optical communications [START_REF] Larger | Nonlinear dynamics Optoelectronic chaos[END_REF]. But chaotic systems of real-number or infinite bit representation realized in finite computing precision lead to short cycle length, non-ideal distribution, and other deflation of this kind. This is the reason of that chaotic systems on an infinite space of integers have been looked for these last years, leading to the proposition to use chaotic iterations (CIs) techniques to reach the desired goals. More precisely, we have proposed in INTERNET 2009 [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF] to mix two given PRNGs by using chaotic iterations, being some particular kind of discrete iterations of a vectorial Boolean function. This first proposal has been improved in INTERNET 2010 [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF] and INTERNET 2011 [START_REF] Bahi | Class of trustworthy pseudo random number generators[END_REF], to obtain a new family of statistically perfect and fast PRNGs. A short overview of these previous researches is given thereafter.

In [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], CIs have been proven to be a suitable tool for fast computing iterative algorithms on integers satisfying the topological chaotic property, as it has been defined by Devaney [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF]. A first way to mix two given generators by using these chaotic iterations, called Old CIPRNGs, has been proposed in Internet 09 [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF] and further investigated in [START_REF] Bahi | A pseudo random numbers generator based on chaotic iterations. application to watermarking[END_REF], [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF], [START_REF] Bahi | Improving random number generators by chaotic iterations. application in data hiding[END_REF]. It was chaotic and able to pass the most stringent batteries of tests, even if the inputted generators were defective. This claim has been verified experimentally, by evaluating the scores of the logistic map, XORshift, and ISAAC generators through these batteries, when considering them alone or after chaotic iterations. Then, in [START_REF] Wang | Randomness quality of CI chaotic generators. application to internet security[END_REF], a new version of this family has been proposed. This "New CIPRNG" family uses a decimation of strategies leading to the improvement of both speed and statistical qualities. Finally, efficient implementations on GPU using a last family called Xor CIPRNG have been designed in [START_REF] Bahi | Efficient and cryptographically secure generation of chaotic pseudorandom numbers on gpu[END_REF], showing that a very large quantity of pseudorandom numbers can be generated per second (about 20 Gsamples/s).

In this paper, the statistical analysis of the three methods mentioned above are carried out systematically, and the results are discussed. Indeed PRNGs are often based on modular arithmetic, logical operations like bitwise exclusive or (XOR), and on circular shifts of bit vectors. However the security level of some PRNGs of this kind has been revealed inadequate by today's standards. Since different biased generators can possibly have their own side effects when inputted into our mixed generators, it is normal to enlarge the set of tested inputted PRNGs, to determine if the observed improvement still remains. We will thus show in this research work that the intended statistical improvement is really effective for all of these most famous generators.

The remainder of this paper is organized in the following way. In Section II, some basic definitions concerning chaotic iterations are recalled. Then, four major classes of general PRNGs are presented in Section III. Section IV is devoted to two famous statistical tests suites. In Section V, various tests are passed with a goal to achieve a statistical comparison between our CIPRNGs and other existing generators. The paper ends with a conclusion and intended future work.

II. CHAOTIC ITERATIONS APPLIED TO PRNGS

In this section, we describe the CIPRNG implementation techniques that can improve the statistical properties of any generator. They all are based on CIs, which are defined below.

A. Notations

S n → the n th term of a sequence S = (S 1 , S 2 , . . .)

v i → the i th component of a vector v = (v 1 , . . . , v n ) f k → k th composition

B. Chaotic iterations

Definition 1 The set B denoting {0, 1}, let f : B N -→ B N be an "iteration" function and S ∈ S be a chaotic strategy. Then, 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. (1)
In other words, at the n th iteration, only the S n -th cell is "iterated".

C. The CIPRNG family 1) Old CIPRNG: Let N = 4. Some chaotic iterations are fulfilled to generate a sequence (x n ) n∈N ∈ B 4 N of Boolean vectors: the successive states of the iterated system. Some of these vectors are randomly extracted and their components constitute our pseudorandom bit flow [START_REF] Bahi | A novel pseudo-random generator based on discrete chaotic iterations[END_REF]. Chaotic iterations are realized as follows. Initial state x 0 ∈ B 4 is a Boolean vector taken as a seed and chaotic strategy (S n ) n∈N ∈ 1, 4 N is constructed with PRNG 2 . Lastly, iterate function f is the vectorial Boolean negation. At each iteration, only the S n -th component of state x n is updated. Finally, some x n are selected by a sequence m n , provided by a second generator PRNG 1 , as the pseudorandom bit sequence of our generator.

The basic design procedure of the Old CI generator is summed up in Algorithm 1. The internal state is x, the output array is r. a and b are those computed by PRNG 1 and PRNG 2 .

Input: the internal state x (an array of 4-bit words) Output: an array r of 4-bit words 1: a ← PRNG 1 (); 2: m ← a mod 2 + 13; 3: while i = 0, . . . , m do x S ← x S ; 7: end while 8: r ← x; 9: return r; Algorithm 1: An arbitrary round of the old CI generator

2) New CIPRNG: The New CI generator is designed by the following process [START_REF] Guyeux | An improved watermarking algorithm for internet applications[END_REF]. First of all, some chaotic iterations have to be done to generate a sequence (x n ) n∈N ∈ B 32 N of Boolean vectors, which are the successive states of the iterated system. Some of these vectors will be randomly extracted and our pseudo-random bit flow will be constituted by their components. Such chaotic iterations are realized as follows. Initial state x 0 ∈ B 32 is a Boolean vector taken as a seed and chaotic strategy (S n ) n∈N ∈ 1, 32 N is an irregular decimation of PRNG 2 sequence, as described in Algorithm 2.

Another time, at each iteration, only the S n -th component of state x n is updated, as follows:

x n i = x n-1 i if i S n , else x n i = x n-1 i .
Finally, some x n are selected by a sequence m n as the pseudo-random bit sequence of our generator.

(m n ) n∈N ∈ M N is computed from PRNG 1 , where M ⊂ N * is a finite nonempty set of integers.
The basic design procedure of the New CI generator is summarized in Algorithm 2. The internal state is x, the output state is r. a and b are those computed by the two input PRNGs. Lastly, the value g 1 (a) is an integer defined as in Eq. 2.

m n = g 1 (y n ) =                        0 if 0 y n < C 0 32 , 1 if C 0 32 y n < 1 i=0 C i 32 , 2 if 1 i=0 C i 32 y n < 2 i=0 C i 32 , . . . . . . N if N-1 i=0 C i 32 y n < 1.
(

) 2
Input: the internal state x (32 bits) Output: a state r of 32 bits 1: for i = 0, . . . , N do

else if d S = 1 then 14: k ← k + 1; 15:
end if 16: end while 17: r ← x; 18: return r; Algorithm 2: An arbitrary round of the new CI generator 3) Xor CIPRNG: Instead of updating only one cell at each iteration as Old CI and New CI, we can try to choose a subset of components and to update them together. Such an attempt leads to a kind of merger of the two random sequences. When the updating function is the vectorial negation, this algorithm can be rewritten as follows [START_REF] Bahi | Efficient and cryptographically secure generation of chaotic pseudorandom numbers on gpu[END_REF]: The single basic component presented in Eq. 15 is of ordinary use as a good elementary brick in various PRNGs. It corresponds to the discrete dynamical system in chaotic iterations.

x 0 ∈ 0, 2 N -1 , S ∈ 0, 2 N -1 N ∀n ∈ N * , x n = x n-1 ⊕ S n , (3)

III. ABOUT SOME WELL-KNOWN PRNGS

A. Introduction

Knowing that there is no universal generator, it is strongly recommended to test a stochastic application with a large set of different PRNGs [START_REF] David | Urng: A portable optimization technique for software applications requiring pseudo-random numbers[END_REF]. They can be classified in four major classes: linear generators, lagged generators, inversive generators, and mix generators:

• Linear generators, defined by a linear recurrence, are the most commonly analyzed and utilized generators. The main linear generators are LCGs and MLCG. • Lagged generators have a general recursive formula that use various previously computed terms in the determination of the new sequence value. • Inversive congruential generators form a recent class of generators that are based on the principle of congruential inversion.

• Mixed generators result from the need for sequences of better and better quality, or at least longer periods. This has led to mix different types of PRNGs, as follows:

x i = y i ⊕ z i For instance, inversive generators are very interesting for verifying simulation results obtained with a linear congruential generator (LCG), because their internal structure and correlation behavior strongly differs from what LCGs produce. Since these generators have revealed several issues, some scientists refrain from using them. In what follows, chaotic properties will be added to these PRNGs, leading to noticeable improvements observed by statistical test. Let us firstly explain with more details the generators studied in this research work (for a synthetic view, see Fig. 1).

B. Details of some Existing Generators

Here are the modules of PRNGs we have chosen to experiment.

1) LCG: This PRNG implements either the simple or the combined linear congruency generator (LCGs). The simple LCG is defined by the recurrence:

x n = (ax n-1 + c) mod m (4)
where a, c, and x 0 must be, among other things, non-negative and less than m [START_REF] Simard | Testu01: A software library in ansi c for empirical testing of random number generators. software users guide[END_REF]. In what follows, 2LCGs and 3LCGs refer as two (resp. three) combinations of such LCGs. For further details, see [START_REF] Ecuyer | Efficient and portable combined random number generators[END_REF].

2) MRG: This module implements multiple recursive generators (MRGs), based on a linear recurrence of order k, modulo m [START_REF] Simard | Testu01: A software library in ansi c for empirical testing of random number generators. software users guide[END_REF]:

x n = (a 1 x n-1 + ... + a k x n-k ) mod m (5)
Combination of two MRGs (referred as 2MRGs) is also be used in this paper.

3) UCARRY: Generators based on linear recurrences with carry are implemented in this module. This includes the addwith-carry (AWC) generator, based on the recurrence:

x n = (x n-r + x n-s + c n-1 ) mod m, c n = (x n-r + x n-s + c n-1 )/m, (6)
the SWB generator, having the recurrence:

x n = (x n-r -x n-s -c n-1 ) mod m, c n = 1 if (x i-r -x i-s -c i-1 ) < 0 0 else, (7)
and the SWC generator designed by R. Couture, which is based on the following recurrence:

x n = (a 1 x n-1 ⊕ ... ⊕ a r x n-r ⊕ c n-1 ) mod 2 w , c n = (a 1 x n-1 ⊕ ... ⊕ a r x n-r ⊕ c n-1 ) / 2 w . (8)
4) GFSR: This module implements the generalized feedback shift register (GFSR) generator, that is:

x n = x n-r ⊕ x n-k (9)
5) INV: Finally, this module implements the nonlinear inversive generator, as defined in [START_REF] Simard | Testu01: A software library in ansi c for empirical testing of random number generators. software users guide[END_REF], which is:

x n = (a 1 + a 2 /z n-1 ) mod m if z n-1 0 a 1 if z n-1 = 0. ( 10
)
IV. STATISTICAL TESTS Considering the properties of binary random sequences, various statistical tests can be designed to evaluate the assertion that the sequence is generated by a perfectly random source. We have performed some statistical tests for the CIPRNGs proposed here. These tests include NIST suite [18] and DieHARD battery of tests [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF]. For completeness and for reference, we give in the following subsection a brief description of each of the aforementioned tests.

A. NIST statistical tests suite

Among the numerous standard tests for pseudorandomness, a convincing way to show the randomness of the produced sequences is to confront them to the NIST (National Institute of Standards and Technology) statistical tests, being an up-to-date tests suite proposed by the Information Technology Laboratory (ITL). A new version of the Statistical tests suite has been released in August 11, 2010.

The NIST tests suite SP 800-22 is a statistical package consisting of 15 tests. They were developed to test the randomness of binary sequences produced by hardware or software based cryptographic pseudorandom number generators. These tests focus on a variety of different types of nonrandomness that could exist in a sequence.

For each statistical test, a set of Pvalues (corresponding to the set of sequences) is produced. The interpretation of empirical results can be conducted in various ways. In this paper, the examination of the distribution of P-values to check for uniformity (Pvalue T ) is used. The distribution of Pvalues is examined to ensure uniformity. If P-value T 0.0001, then the sequences can be considered to be uniformly distributed.

In our experiments, 100 sequences (s = 100), each with 1,000,000-bit long, are generated and tested. If the Pvalue T of any test is smaller than 0.0001, the sequences are considered to be not good enough and the generating algorithm is not suitable for usage.

B. DieHARD battery of tests

The DieHARD battery of tests has been the most sophisticated standard for over a decade. Because of the stringent requirements in the DieHARD tests suite, a generator passing this battery of tests can be considered good as a rule of thumb.

The DieHARD battery of tests consists of 18 different independent statistical tests. This collection of tests is based on assessing the randomness of bits comprising 32-bit integers obtained from a random number generator. Each test requires 2 23 32-bit integers in order to run the full set of tests. Most of the tests in DieHARD return a Pvalue, which should be uniform on [0, 1) if the input file contains truly independent random bits. These Pvalues are obtained by P = F(X), where F is the assumed distribution of the sample random variable X (often normal). But that assumed F is just an asymptotic approximation, for which the fit will be worst in the tails. Thus occasional Pvalues near 0 or 1, such as 0.0012 or 0.9983, can occur. An individual test is considered to be failed if the Pvalue approaches 1 closely, for example P > 0.9999.

V. RESULTS AND DISCUSSION

Table I shows the results on the batteries recalled above, indicating that almost all the PRNGs cannot pass all their tests. In other words, the statistical quality of these PRNGs cannot fulfill the up-to-date standards presented previously. We will show that the CIPRNG can solve this issue.

To illustrate the effects of this CIPRNG in detail, experiments will be divided in three parts:

1) Single CIPRNG: The PRNGs involved in CI computing are of the same category. 2) Mixed CIPRNG: Two different types of PRNGs are mixed during the chaotic iterations process. 3) Multiple CIPRNG: The generator is obtained by repeating the composition of the iteration function as follows: x 0 ∈ B N , and ∀n ∈ N * , ∀i ∈ 1; N ,

x n i = x n-1 i if S n i ∀ j ∈ 1; m , f m (x n-1 ) S nm+ j if S nm+ j = i.
(11) m is called the functional power. We have performed statistical analysis of each of the aforementioned CIPRNGs. The results are reproduced in Tables I and II. The scores written in boldface indicate that all the tests have been passed successfully, whereas an asterisk "*" means that the considered passing rate has been improved.

A. Tests based on the Single CIPRNG

The statistical tests results of the PRNGs using the single CIPRNG method are given in Table II. We can observe that, except for the Xor CIPRNG, all of the CIPRNGs have passed the 15 tests of the NIST battery and the 18 tests of the DieHARD one. Moreover, considering these scores, we can deduce that both the single Old CIPRNG and the single New CIPRNG are relatively steadier than the single Xor CIPRNG approach, when applying them to different PRNGs. However, the Xor CIPRNG is obviously the fastest approach to generate a CI random sequence, and it still improves the statistical properties relative to each generator taken alone, although the test values are not as good as desired.

Therefore, all of these three ways are interesting, for different reasons, in the production of pseudorandom numbers and, on the whole, the single CIPRNG method can be considered to adapt to or improve all kinds of PRNGs.

To have a realization of the Xor CIPRNG that can pass all the tests embedded into the NIST battery, the Xor CIPRNG with multiple functional powers are investigated in Section V-C.

B. Tests based on the Mixed CIPRNG

To compare the previous approach with the CIPRNG design that uses a Mixed CIPRNG, we have taken into account the same inputted generators than in the previous section. These inputted couples (PRNG 1 , PRNG 2 ) of PRNGs are used in the Mixed approach as follows:

x 0 ∈ 0, 2 N -1 , S ∈ 0, 2 N -1 N ∀n ∈ N * , x n = x n-1 ⊕ PRNG 1 ⊕ PRNG 2 , (12)
With this Mixed CIPRNG approach, both the Old CIPRNG and New CIPRNG continue to pass all the NIST and DieHARD suites. In addition, we can see that the PRNGs using a Xor CIPRNG approach can pass more tests than previously. The main reason of this success is that the Mixed Xor CIPRNG has a longer period. Indeed, let n P be the period of a PRNG P, then the period deduced from the single Xor CIPRNG approach is obviously equal to:

n S XORCI = n P if x 0 = x n P 2n P if x 0 x n P . (13)
Let us now denote by n P1 and n P2 the periods of respectively the PRNG 1 and PRNG 2 generators, then the period of the Mixed Xor CIPRNG will be:

n XXORCI = LCM(n P1 , n P2 ) if x 0 = x LCM(n P1 ,n P2 ) 2LCM(n P1 , n P2 ) if x 0 x LCM(n P1 ,n P2 ) . (14)
In Table III, we only show the results for the Mixed CIPRNGs that cannot pass all DieHARD suites (the NIST tests are all passed). It demonstrates that Mixed Xor CIPRNG involving LCG, MRG, LCG2, LCG3, MRG2, or INV cannot pass the two following tests, namely the "Matrix Rank 32x32" and the "COUNT-THE-1's" tests contained into the DieHARD battery. Let us recall their definitions:

• Matrix Rank 32x32. A random 32x32 binary matrix is formed, each row having a 32-bit random vector. Its rank is an integer that ranges from 0 to 32. Ranks less than 29 must be rare, and their occurences must be pooled with those of rank 29. To achieve the test, ranks of 40,000 such random matrices are obtained, and a chisquare test is performed on counts for ranks 32,31,30 and for ranks ≤ 29. There are 5 5 possible 5-letter words, and from a string of 256,000 (over-lapping) 5-letter words, counts are made on the frequencies for each word. The quadratic form in the weak inverse of the covariance matrix of the cell counts provides a chisquare test: Q5-Q4, the difference of the naive Pearson sums of (OBS -EXP) 2 /EXP on counts for 5-and 4-letter cell counts. The reason of these fails is that the output of LCG, LCG2, LCG3, MRG, and MRG2 under the experiments are in 31bit. Compare with the Single CIPRNG, using different PRNGs to build CIPRNG seems more efficient in improving random number quality (mixed Xor CI can 100% pass NIST, but single cannot).

C. Tests based on the Multiple CIPRNG

Until now, the combination of at most two input PRNGs has been investigated. We now regard the possibility to use a larger number of generators to improve the statistics of the generated pseudorandom numbers, leading to the multiple functional power approach. For the CIPRNGs which have already pass both the NIST and DieHARD suites with 2 inputted PRNGs (all the Old and New CIPRNGs, and some of the Xor CIPRNGs), it is not meaningful to consider their adaption of this multiple CIPRNG method, hence only the Multiple Xor CIPRNGs, having the following form, will be investigated.

x 0 ∈ 0, 2 N -1 , S ∈ 0, 2 N -1 N ∀n ∈ N * , x n = x n-1 ⊕ S nm ⊕ S nm+1 . . . ⊕ S nm+m-1 , (15)
The question is now to determine the value of the threshold m (the functional power) making the multiple CIPRNG being able to pass the whole NIST battery. Such a question is answered in Table IV.

D. Results Summary

We can summarize the obtained results as follows.

1) The CIPRNG method is able to improve the statistical properties of a large variety of PRNGs. 2) Using different PRNGs in the CIPRNG approach is better than considering several instances of one unique PRNG.

3) The statistical quality of the outputs increases with the functional power m.

VI. CONCLUSION AND FUTURE WORK

In this paper, we first have formalized the CI methods that has been already presented in previous Internet conferences. These CI methods are based on iterations that have been topologically proven as chaotic. Then 10 usual PRNGs covering all kinds of generators have been applied, and the NIST and DieHARD batteries have been tested. Analyses show that PRNGs using the CIPRNG methods do not only inherit the chaotic properties of the CI iterations, they also have improvements of their statistics. This is why CIPRNG techniques should be considered as post-treatments on pseudorandom number generators to improve both their randomness and security.

In future work, we will try to enlarge this study, by considering a larger variety of tests. The CIPRNG's chaotic behavior will be deepened by using some specific tools provided by the mathematical theory of chaos. Finally, a large variety of Internet usages, as cryptography and data hiding, will be considered for applications.

  of a function f strategy → a sequence which elements belong in 1; N S → the set of all strategies C k n → the binomial coefficient n k = n! k!(n-k)! ⊕ → bitwise exclusive or and → the usual shift operators (X, d) → a metric space LCM(a, b)→ the least common multiple of a and b

  end for 4: a ← PRNG 1 (); 5: m ← f (a); 6: k ← m; 7: while i = 0, . . . , k do 8: b ← PRNG 2 () mod N;

Figure 1 :

 1 Figure 1: Ontological class hierarchy of PRNGs

Table I :

 I • COUNT-THE-1's TEST Consider the file under test as a stream of bytes (four per 2 bit integer). Each byte can contain from 0 to 8 1's, with probabilities NIST and DieHARD tests suite passing rates for PRNGs without CI

	Types of PRNGs	Linear PRNGs		Lagged PRNGs		ICG PRNGs	Mixed PRNGs
	X X T ests X	X X PRNG X X X	LCG	MRG	AWC	SWB	SWC	GFSR	INV	LCG2	LCG3	MRG2
	NIST		11/15	14/15	15/15	15/15	14/15	14/15	14/15	14/15	14/15	14/15
	DieHARD	16/18	16/18	15/18	16/18	18/18	16/18	16/18	16/18	16/18	16/18

Table II :

 II NIST and DieHARD tests suite passing rates for PRNGs with CI

	Types of PRNGs	Linear PRNGs		Lagged PRNGs		ICG PRNGs		Mixed PRNGs
	h h h h h h h h h h h T ests S ingle CIPRNG	LCG	MRG	AWC	SWB	SWC	GFSR	INV	LCG2	LCG3	MRG2
	Old CIPRNG
	NIST	15/15 *	15/15 *	15/15	15/15	15/15 *	15/15 *	15/15 *	15/15 *	15/15 *	15/15
	DieHARD	18/18 *	18/18 *	18/18 *	18/18 *	18/18	18/18 *	18/18 *	18/18 *	18/18 *	18/18 *
	New CIPRNG
	NIST	15/15 *	15/15 *	15/15	15/15	15/15 *	15/15 *	15/15 *	15/15 *	15/15 *	15/15
	DieHARD	18/18 *	18/18 *	18/18 *	18/18 *	18/18	18/18 *	18/18 *	18/18 *	18/18 *	18/18 *
	Xor CIPRNG
	NIST	14/15*	15/15 *	15/15	15/15	14/15	15/15 *	14/15	15/15 *	15/15 *	15/15
	DieHARD	16/18	16/18	17/18*	18/18 *	18/18	18/18 *	16/18	16/18	16/18	16/18
	1,8,28,56,70,56,28,8,1 over 256. Now let the stream of
	bytes provide a string of overlapping 5-letter words,
	each "letter" taking values A,B,C,D,E. The letters are
	determined by the number of 1's in a byte: 0,1, or 2 yield
	A, 3 yields B, 4 yields C, 5 yields D and 6,7, or 8 yield E.
	Thus we have a monkey at a typewriter hitting five keys
	with various probabilities (37,56,70,56,37 over 256).

Table III :

 III Scores of mixed Xor CIPRNGs when considering the DieHARD battery ````````P

	RNG 1	PRNG 0	LCG	MRG		INV	LCG2	LCG3	MRG2
	LCG	H	H	16/18	16/18	16/18	16/18	16/18
			H H
	MRG	16/18	H	H	16/18	16/18	16/18	16/18
					H H
	INV	16/18	16/18	H	H	16/18	16/18	16/18
							H H
	LCG2	16/18	16/18	16/18	H	H	16/18	16/18
									H H
	LCG3	16/18	16/18	16/18	16/18	H	H	16/18
									H H
	MRG2	16/18	16/18	16/18	16/18	16/18	H	H
									H H

Table IV :

 IV Functional power m making it possible to pass the whole NIST battery

	Inputted PRNG	LCG	MRG	SWC	GFSR	INV	LCG2	LCG3	MRG2
	Threshold value m	19	7	2	1	11	9	3	4


Christopher Gomez
email: christopher.gomez@canterbury.ac.nz

Structure-from-Motion and Wavelet Decomposition for outcrop analysis

published or not. The documents may come

Hence information from one sample could be extended to long transects and show large/progressive horizontal variations that can't be easily identified from manual work.

Introduction

Outcrops are arguably one of the most important sources of data to study the subsurface geology and the geomorphology of volcanic environments.

Outcrop analysis is essentialfor instance for calibrating several non-destructive methods, such as ground-penetrating radar (GPR), in volcanic environments where data collection can be challenging (Abrams and Sigurdsson, 2007;Cassidy et al., 2009;Courtland et al., 2012;Finizola et al., 2010;Gomez and Lavigne, 2009;Gomez et al., 2008Gomez et al., , 2009Gomez et al., , 2012;;Gomez-Ortiz et al., 2006;Khan et al., 2007). Giaccio et al., 2002).

Despite being a

One potential direction that can be explored is the analysis ofoutcrop surface texture (or surface roughness), which can bea key proxy for environmental processes. This is particularly true in the field of agriculture where surface roughness gives indications on wind deflation, runoff and water absorption, even playing an important part in soil biota and gas exchanges (Vidal Vazquez et al., 2005). Geologists have also used variations of surface texture to characterize different volcanic deposits (Bretaret al., 2013) and the mechanisms of rock fragmentation (Tatone and Grasselli, 2009).Surface texture also controls electromagnetic scattering on a surface and therefore plays an important role in remote sensing interpretation (Beckmann and Spizzichino, 1987). In this paper, we add to the recent research on using remotesensing techniques for outcrop analysis.

Here we explore the question of whether cost-effective remote sensing data acquisition can be used to accurately describe surface texture of volcanic outcrops.

We Robson, 2012;Verhoeven,et al., 2012).

In

Location

Japan is a volcanic archipelago that seats on the Pacific Ring of Fire and it is arguably one of the most tectonically and volcanically active regions in the world.

Numazawa Volcano is located on the main island of Japan, Honshu, in the western part of Fukushima prefecture and about 50 km from the volcanic front defined by Sugimura (Sugimura, 1960;Yamamoto, 2007;Kataoka et al., 2008). Numazawa

Volcano has developed on the edge of the

Method

For the present study, a sandy to gravely

Haar-wavelet decomposition as a tool to study micro-variations

The vertical topography derived from The second algorithm tested with a relative success is the RMS:

[( 1 𝐿 𝑍(𝑥 𝐿 0 ) 2 𝑑𝑥] 1/2

  photogrammetry based algorithms could help extend the analysis potential from one localized control pointwhere the researcher can sample, measure and describe an outcrop -to a larger area.

  et al., 2013) and terrestrial laser scanning, to describe millimeter to centimeter scale features (Bellianet al., 2005)..Despite important gains in descriptive potential, exploration using these RS techniques has been relatively sparse, most probably because the technical and financial aspects are still prohibitive, and the great majority deals with sub-horizontal surfaces rather than sub-vertical ones (e.g. Heritage and Milan, 2009). Moreover, the contributionsto datedeal mostly with data acquisition and handling rather than obtaining parameters from which one could derive indicators on the nature of the studied materialin an automated manner (e.g.

  order to numerically study the variations of a surface from an ideal general shape, a series of tools are available, spanning from descriptive statistical indicators to more complex fractal-based (Bretard, et al., 2013) and wavelet-based analysis (Gomez, 2012) allowing measures at various scales (Gomez, 2013).During the last 10 years, the use of wavelet analysis in earthsciences has increased concomitantly with the increasing availability of numerical data. It has especially benefited from the study of time-series for the determination of different frequencies and momentums (e.g. Andreoet al., 2006; Partal andKüçük2006; Rossi et al., 2009). Analyses of space-scale data with wavelet -although more scarce in earth-sciencesare also on the rise (e.g. Audet andMareschal, 2007; Booth et al., 2009; Lashermeset al.,2007), eventually following the influence of research in medical imagery, which has been widely using wavelet for topographical analysis for instance (e.g. Langenbucheret al., 2002). Wavelets allow the decomposition of a signal into a set of approximations, which is hierarchically organized in a combination of different scales. Wavelet analyses use a short-term duration wave as a kernel function in an integral transform. There are several types of wavelet, which are named after their inventors: e.g. Morlet wavelet, Meyer wavelet. Based on the shape of the series/function that needs to be analyzed, the appropriate mother wavelet is scaled and translated (is a well-fitted tool for separating spectral components of topography (i.e. working on different scales of a single object), because it gives both the spatial and the spectral resolution.

  Uwaigusa caldera complex(Yamamoto and Komazawa, 2004) to reach a present altitude of 1100 m a.s.l. A 2 km wide and ~100 m deep lake has formed withinthe caldera .Chronologically, thevolcaniclastic deposits generated by Numazawa volcano are:the 110 k.a. Sibahara pyroclastic deposits; the 71 k.aMukuresawa lava dome; the 45 k.aMizunuma pyroclasticflow deposits; the Sozan lava dome of 43 k.a; the Maeyama lava dome of 20 k.a and the Numazawako eruption of 5 k.a (Yamamoto, 2007).Kataoka et al. (2008) have described in details the Numazawako eruption and the geomorphic impacts around the volcano, including the flood terraces in the Tadami river, from which the material used in the present contribution has been extracted (Cf. Fig. 9 in Kataoka et al., 2008). The 290 cm high x 85 cm wide outcrop-peel was extracted from hyperconcentrated-flow deposits with multiple inversely graded bed sets, rich in rounded pumices. The matrix is dominated by coarse sand to pebble size material. The peel is part of a 15 m thick unit that lied on top of debris-flow deposits.

Fig. 3

 3 photographs were taken to maximize the overlap such that features of the outcrop were captured by multiple photographs.

  Fig. 4 Detrending using wavelet.Transformation of the surface 'topography' obtained from Structure From Motion. (a) Orthophotograph constructed from Structure from Motion; (b) Surface variation, the 0 being the perfect vertical; (c) Surface extraction of the vertical transect at the centre of the outcrop; (d) 'topographic' general trend as extracted by Haar wavelet decomposition (Level 7 of a 7 scales decomposition); (e) Combination of the 4 lowest level of wavelet decomposition minus the main trend at level 7 (e = L1+L2+L3+L4-L7). One will note that (b) is only coded to 280 cm height as the upper part also includes the wood

Fig. 5

 5 Fig. 5 Wavelet decomposition of the outcrop at level 1 (out of a 7 levels decomposition using a Haar mother-wavelet). As the lowest level reacts to the shortest variations in space, thisanalysis was performed to detect the microvariations (this lowest level is often considered as the 'white-noise' in signal processing).

  It calculates the root mean square of the squared variation values from an ideal surfacein the present case the detrended surface roughness. The result of the RMS shows the ability of the algorithm to detect and individualize local variations, due here to the presence of the centimeter-scale clast inclusions (Fig. 7-1&2), but it also detects quick variations such as the edge of a layer slightly protruding from the rest of the outcrop (Fig. 7-3).

Fig. 6

 6 Fig. 6 Arithmetic average roughness (R a ) extracted using a 2cm x 2cm moving average detrending, which reduces the effects of large variation on the outcrop. (a & c) R a of coarse sand units; (b & d) R a of coarser sand with gravels and centimetric clasts inclusions; (e) R a of coarse sand with several vertical erosional rill remnants. It is interesting to note that R a did not react to these variations (one will note that the scales of a,c and e are the same but b and d differ in order to display the variations at different scales).

Fig. 7

 7 Fig. 7 RMS or square root of the square of local variation from the entire detrended surface. This index allows finding elements that protrude locally from the surrounding, such as isolated gravels in finer material, etc. The profile (a) is the reconstructed photograph using textured SfM-MVS; the profile (b) is the surface microtopography from an idea vertical; profile (c) is the dvar. On the three profiles box 1,2 and 3 have been drawn for regions of interests (see the text for full comments on these boxes).

Acknowledgement

The authors are in debt to two anonymous reviewers for their role in improving the manuscript and to the editor for a prompt and thoughtful handling of the manuscript.

Abrams, J., Sigurdsson, H., 2007. Characterization of pyroclastic fall and flow deposits from the 1815 eruption of Tambora volcano, Indonesia using ground-penetrating radar. Journal of Volcanology and Geothermal Research 161, 352-361. Andreo, B., Jimenez, P., Duran, J.J., Carrasco, F., Vadillo, I., Mangin, A., 2006.Climatic and hydrological variations during the last 117-166 years in the south of the Iberian Peninsula, from spectral and correlation analysis and continuous wavelet analysis. Journal of Hydrology 324,[24][25][26][27][28][29][30][31][32][33][34][35][36][37][38][39] AgisoftPhotoscan-PRO Users Manual, 2012. http://downloads.agisoft.ru/pdf/photoscan-pro_0_9_0_en.pdf -accessed in November 2012. Audet, P., Mareschal, J-C., 2007. Wavelet analysis of Finizola, A., Ricci, T., Delana, R., Cabusson, S.B., Rossi, M., Praticelli, N., Giocoli, A. Romano, G., Delcher, E., Suski, B., Revil, A., Menny, P., Di Gangi, F., Letort, J., Peltier, A., Villasante-Marcos, V., Douillet, G., Avard, G., Lelli, M.,


Jacques M Bahi

Abdallah Makhoul

Maguy Medlej

An Optimized In-Network Aggregation Scheme for Data Collection in Periodic Sensor Networks

In-network data aggregation is considered an effective technique for conserving energy communication in wireless sensor networks. It consists in eliminating the inherent redundancy in raw data collected from the sensor nodes. Prior works on data aggregation protocols have focused on the measurement data redundancy. In this paper, our goal in addition of reducing measures redundancy is to identify near duplicate nodes that generate similar data sets. We consider a tree based bi-level periodic data aggregation approach implemented on the source node and on the aggregator levels. 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 propose a new frequency filtering approach and several optimizations using sets similarity functions to solve this problem. To evaluate the performance of the proposed filtering method, experiments on real sensor data have been conducted. The obtained results show that our approach offers significant data reduction by eliminating in network redundancy and outperforms existing filtering techniques.

Introduction

Data collection from sensor networks can be made on demand or by data streaming. The first category is done by bi-directional dialogs between the sensor nodes and the base station. A request for data is sent from the end user via the sink to the sensor nodes which, in return, send back the data to the user via multi hop communications. On the other side, in data streaming, data flows primarily from the sensor node to the sink. In this category we distinguish the periodic sampling and the event driven data models. In this paper we are interested in "periodic sampling" data model in sensor networks, where the acquisition of sensor data from a number of remote sensor nodes are forwarded to the gateway on a periodic basis. This data model is appropriate for applications where certain conditions or processes need to be monitored constantly, such as the temperature in a conditioned space or pressure in a process pipeline. There are couple of important design considerations associated with the periodic sampling data model. The most critical design issue is the phase relation among multiple sensor nodes. If two neighbor nodes operate with identical or similar sampling rates, redundant packets from the two nodes are likely to happen repeatedly. It is essential for sensor networks to be able to detect and clean redundant transfered data from the nodes to the sink. In-network data aggregation has been proven as an effective technique for eliminating redundancy and forwarding only the extracted information from the raw data. Furthermore, by doing so data aggregation can often reduce the communication cost and extend the whole network lifetime.

In this paper we present a hierarchical multilevel data aggregation scheme aiming 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.

In this paper, we provide a new prefix filtering method to study the sets similarity in sensor networks. We propose frequency filtering optimization techniques, 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. Furthermore, we provide a new optimization method for early termination of sets similarity computing. To evaluate our approach we conducted extensive experimental study using real data measurements. The obtained results compared to the existing algorithms show the effectiveness of our method which significantly reduces the number of duplicate data.

The rest of the paper is organized as follows, Section 2 gives an overview on related works reported on data aggregation in sensor networks. Section 3 describes our periodic data aggregation scheme. The local aggregation level is presented in section 4. Review on similarity functions and our proposed frequency filtering techniques are presented in Section 5. Experimental results are given in Section 6. Section 7 concludes the paper with some directions to a future work.

Previous Data Aggregation Work

Data aggregation in wireless sensor networks has been well studied in recent years [START_REF] Yu | Distributed data aggregation scheduling in wireless sensor networks[END_REF] [2] [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF]. It means computing and transmitting partially aggregated data to the end user rather than transmitting raw data in networks to reduce the energy consumption [START_REF] Sharaf | Tina: A scheme for temporal coherency-aware in-network aggregation[END_REF]. There are vast amount of extant works on in-network data aggregation in the literature. Some of the methods reported recently are query based methods [5] [6]. A query is generated at the sink and then broadcasted through the network. Some nodes just 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] Cormode | Prolonging the lifetime of wireless sensor networks via unequal clustering[END_REF] [9] [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. Among these methods, the LEACH protocol [11] [12]. In [START_REF] Lee | Data aggregation for wireless sensor networks using self-organizing map[END_REF], the authors propose a self-organizing method for aggregating data based on the architecture CODA (Cluster-based self-Organizing Data Aggregation), based on the Kohonen Self-Organizing Map to aggregate sensor data in cluster. In a first step before deployment, the nodes are trained to have the ability to classify the sensor data. Thus, it increases the quality of data and reduces data traffic as well as energy-conserving. An adaptive data aggregation (ADA) scheme for clustered sensor networks has been proposed in [START_REF] Chen | Adaptive data aggregation scheme in clustered wireless sensor networks[END_REF]. In this scheme, a time based as well as spatial aggregation degrees are introduced. They are controlled by the reporting frequency at sensor nodes and by the aggregation ratio at cluster heads (CHs) respectively. The function of the ADA scheme is mainly performed at the sink node, with a little function at CHs and sensor nodes.

In a tree based network as our presented work, sensor nodes are organized into a tree where data aggregation is performed at aggregators along the tree to arrive to the sink. Tree based data aggregation approaches are suitable for in-network data aggregation. The authors in [START_REF] Prakash | Tree-ondag for data aggregation in sensor networks[END_REF] [START_REF] Fan | Dynamic forwarding over tree-on-dag for scalable data aggregation in sensor networks[END_REF], have proposed Tree on DAG (ToD) for data aggregation, a semistructured approach that uses Dynamic Forwarding on an implicitly constructed structure composed of multiple shortest path trees to support network scalability. The key principle behind ToD was that adjacent nodes in a graph will have low stretch in one of these trees in ToD, thus resulting in early aggregation of packets.

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 propose two optimization techniques based on frequency filtering extention which can be integrated with our previous prefix method [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF] to find similar data sets efficiently. Furthermore we provide a new and faster technique for sets similarity computation.

Periodic Data Aggregation

Due to resource restricted sensor nodes, it is important to minimize the amount of data transmission among sensor networks so that the average network lifetime and the overall bandwidth utilization are improved. To reduce the amount of sending data, an aggregation approach can be applied along the path from sensors to the sink. Sensor nodes collect information from the region of interest and send it to aggregators. Each aggregator then condenses the data prior to sending it on.

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.

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 locally 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.

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 ).

Using the notations defined above the local aggregation algorithm is done as follows [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF]. 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, else it adds the new measure to the set and initialize its frequency to 1. At the end of the period p, each node i will possess a local aggregated set M i and send it to its aggregator.

Duplicate data sets 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.

Similarity Functions

A variety of similarity functions have been used in the literature such as overlap threshold, Jaccard similarity and Cosine similarity [START_REF] Bayardo | Scaling up all pairs similarity search. 16th international[END_REF][START_REF] Sarawag | Efficient exact set-similarity joins. 32nd international conference on Very large data bases[END_REF][START_REF] Chaudhuri | A primitive operator for similarity joins in data cleaning[END_REF]. We denote |M i | as the number of elements (measures) in the set M i . The following functions can be used to measure the similarity between two sets of measurements M i and M j :

Overlap similarity:

O(M i , M j ) = |M i ∩ M j | Jaccard similarity: J(M i , M j ) = |Mi∩Mj | |Mi∪Mj | Cosine similarity: C(M i , M j ) = |Mi∩Mj | √ |Mi|×|Mj |
Dice similarity:

D(M i , M j ) = 2×|Mi∩Mj | |Mi|+|Mj |
All these functions are commutative and can be transformed to the Overlap similarity easily. For instance, we can present the Jaccard similarity function as follows:

J(M i , M j ) = O(M i , M j ) |M i | + |M j | -O(M i , M j )
In our approach, we will focus on the Jaccard similarity. It is one of the most widely accepted function because it can support many other similarity functions [START_REF] Sarawag | Efficient exact set-similarity joins. 32nd international conference on Very large data bases[END_REF]. In our application, two given sets M i and M j are considered similar if and only if:

J(M i , M j ) ≥ t
where t is a threshold given by the application itself. This equation can be transformed as:

J(M i , M j ) ≥ t ⇔ O(M i , M j ) ≥ α (1)
where, α

= t 1+t .(|M i | + |M j |).
In order to study the similarity functions for data aggregation in sensor networks, we define a new function for overlapping "∩ s " between two sets of measurements as follows:

Definition 3 (Overlap function). 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 such that link(y 1 , y 2 ) = 1}; and O s (M 1 , M 2 ) = |M 1 ∩ s M 2 |.
To evaluate the similarity between two sets we obtain:

J(Mi, Mj) ≥ t ⇔ |Mi ∩s Mj| ≥ α = t 1 + t .(|Mi| + |Mj|) (2)

Sets similarity computation

In this section we provide techniques for computing the similarity between the received sets. A naïve solution to find all similar 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 [START_REF] Bayardo | Scaling up all pairs similarity search. 16th international[END_REF] [17] [3]. 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]: 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 .

⌈ t 1+t .(|M i | + |M j |)⌉(Equation
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 algorithm for finding similarity sets based on prefix filtering technique is given in Algorithm 1. It 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. end for 23: end for 24: return S Prefix filtering algorithm helps prune out unfeasible sets of measures, however, in practice the number of non-similar 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] [19] 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 opti-mizations for prefix filtering techniques based on measures frequency while taking into account this trade-off.

Frequency filtering approach

In this section, we present our frequency filtering method based on prefix extension. We begin by introducing 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: 2)). 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 ). (3)
Hence, from Equation (2) and Equation (3) we can deduce that:

M i and M j are similar iff:

f s (M i , M j ) ≥ 2 × t × τ 1 + t . (4)
Frequency filter principle 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 p-pref 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 almost empty. From the above equations and equation ( 4)(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 )) (5)
From the following equation:

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

f s (p-M i , p-M j ) ≥ |p-Mi| k=1 (f (m k ∈ p-M i )) - 1 -t 1 + t × τ ( 7
)
The lemma is proved.

Algorithm 2 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 presented in Algorithm 1.

Jaccard similarity computation

Although filtering approaches reduce the number of comparisons between the received sets of measures, the number of candidate sets surviving after this phase is still non negligible. Furthermore, the computation of the jaccard similarity between two candidates sets can be very complex, especially when it comes to sensor networks where measures' sets can have ten hundreds or thousands elements. Therefore, to continue filtering out further candidate sets we propose a new frequency filtering constraint in the verification phase. In doing so, we can also reduce the overhead of the jaccard similarity computation.

Algorithm 2 Frequency-filtering based algorithm.

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

Replace line 5 in Algorithm 1 with -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 Replace line 10 in Algorithm 1 with

-F s[Mj] ← F s[Mj] + fmin(Mi[k], Mj[l])
Replace line 18 in Algorithm 1 with

-for each Mj such that F s[Mj] > sumF req -1-t 1+t × τ do
Assume that we want to compute the similarity between two sets M i and M j . Then, these sets are similar if they satisfy the overlap condition f s (M i , M j ) ≥ 2×t×τ 1+t . We also assume that a measure m ∈ M i divides M i into two partitions: one partition containing all the measures having frequencies higher than f (m) including m denoted by h-M i and the second l-M i containing all the measures having frequencies less than f (m). Similarly, we assume that any measure in M j divides it in two partitions h-M j and l-M j . The idea of dividing the sets is to find a measure where at this position a similarity upper bound is estimated and checked against the similarity threshold. As soon as the check is failed we can stop the overlap computing early. This hypothesis is formalized by the following lemma:

Lemma 3. Assume that |M i | < |M j |
and all measures in M i are ordered according to the global ordering O. M i and M j are similar ⇒ for any m ∈ M i dividing M i into h-M i and l-M i we have:

f s (h-M i , M j ) ≥ 2×t×τ 1+t - |l-Mi| k=1 (f (m k ∈ l-M i )).
Proof. M i and M j are similar

⇒ f s (M i , M j ) ≥ 2 × t × τ 1 + t (8)
⇒ f s (h-M i , M j ) + f s (l-M i , M j ) ≥ 2 × t × τ 1 + t (9) ⇒ f s (h-M i , M j ) ≥ 2 × t × τ 1 + t -f s (l-M i , M j ) (10)
Then we have:

f s (l-M i , M j ) ≤ min( |l-Mi| k=1 (f (m k )), |Mj | k=1 (f (m k ))) (11)
≤ min(

|l-Mi| k=1 (f (m k ∈ l-M i )), τ ) (12)
≤ |l-Mi| k=1 (f (m k ∈ l-M i )) (13)
From equations ( 10) and ( 13) we can deduce that:

f s (h-M i , M j ) ≥ 2 × t × τ 1 + t - |l-Mi| k=1 (f (m k ∈ l-M i )).
The lemma is proved.

The algorithm of overlap computation is given in Algorithm 3 In this algorithm, we used two kinds of measures ordering depending on the sets sizes. The first one according to the global ordering O (M i in the above algorithm) and the second is sorted in increasing order of the measures to accelerate a measure search1 .

Experimental Results

To evaluate our approach, we conducted multiple series of simulations using the discrete event simulator OMNET++ [START_REF]OMNeT++[END_REF]. The objective of these simulations is to confirm that our prefix frequency filtering (PFF) 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 [21]. Every 31 seconds, sensors with weather boards were collecting humidity, temperature, light and voltage values. For the sake of simplicity, in this paper we are interested in one field of sensor measurements: the temperature 2 . We performed several runs of the algorithms (an average of 15 runs). In each experimental run, we generated a network of 46 nodes corresponding to those was deployed in the Intel Berkeley Lab. Each node then reads periodically real measures saved in a file while applying the first aggregation algorithm. At the end of this step, each node sends its set of measures/frequencies to an aggregator node which in his turn applies prefix and filtering algorithms to theses sets. Furthermore, we compare our approach to the ToD protocol proposed in [START_REF] Prakash | Tree-ondag for data aggregation in sensor networks[END_REF] [START_REF] Fan | Dynamic forwarding over tree-on-dag for scalable data aggregation in sensor networks[END_REF]. As our real data sensor network consists of 46 nodes, we use ToD in a one dimensional Network as explained in [START_REF] Fan | Dynamic forwarding over tree-on-dag for scalable data aggregation in sensor networks[END_REF] and we only divide the network into two F-cluster.

We evaluated the performance of the protocols using the following parameters: a) the number of sensor measurements taken by all nodes during a period τ , and b) the threshold of the Jaccard similarity function t. The threshold δ is fixed to 0.07. The aggregation function used for the ToD protocol is the same used in our approach (PFF) based on the link function (cf section 4). We employ four metrics in our simulations:

-The number of candidate sets generated after applying the prefix filtering approach [START_REF] Bahi | Data aggregation for periodic sensor networks using sets similarity functions[END_REF],

the frequency filtering algorithms with optimizations (PFF) and the final result (the real number of duplicate sets); -Percentage of received measures: It represents how effective a protocol is in aggregating data. It is the number of measures received by the sink over the number of measures taken by all nodes. -Data accuracy: represents the measures loss rate. It is a evaluate of measures taken by the source nodes and did not received at the base station (sink). It is defined also as the aggregation error. -Overall energy dissipation: is the total energy dissipation of the entire network. To evaluate the energy consumption of our approach we used the same radio model as discussed in [21].

Prefix frequency filtering optimizations

In this section we compared the number of candidates (number of comparisons) generated respectively by our frequency filtering technique (PFF), the prefix filtering algorithm and the results obtained after applying the Jaccard similarity function. We fixed the number of the total measuremtns taken by all the nodes during a period to τ = 8.E + 04. The obtained result is 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. We can also see that our frequency filtering technique (PFF) outperforms the prefix filtering methods in all cases. Moreover, the number of candidates generated by all the algorithms is far bigger than the results number. This is to prove that under this circumstance, applying early termination algorithm is very effective (Algorithm 3).

Percentage of received measures and data accuracy

Figure 2 shows the percentage of received measures over the total number taken by all nodes for the temperature field. These experiments permit to show how well aggregation protocols do aggregation and reduce redundant measures. PFF performs better than ToD in terms of data aggregation because of it is ability to compare sets of data instead of single packets. In other words, PFF reduces the number of redundant data traveling into the networks better than TOD especially when the number of readings increase (the case of periodic networks). We also notice that, the percentage of received packets remains almost unchangeable while increasing the sensor readings.

Figure 3 depicts the resulsts of the aggregation error. This metric is an important performance index, and the high measures loss rate will impact the use of the data greatly. The obtained results show that the two protocols have good performance regarding the aggregation error. As expected, when we increase the threshold t of the similarity function we reduce the measures loss rate. For instance, we can notice that PFF outperforms ToD in terms of data accuracy for t = 0.9.

Overall energy dissipation

The overall energy dissipation is the total energy consumption of the entire network. Figure 4 shows the results for total energy consumption obtained while varying the total number of sensor readings. The figure shows that the overall energy dissipation for different protocols increases as the number of readings increases. We notice that ToD consumes not too much, but does not scale well as the number of readings increases. For all the values of the threshold t tested, PFF always outperforms the ToD protocol in total energy dissipation. This is because, the packet-packet comparison used in ToD instead of data sets in PFF generates more transmissions in the network, furthermore, the packet construction in ToD contains additional required for the aggregation which is not the case in PFF.

Conclusion and future work

In this paper we proposed a tree based bi-level model for data aggregation in periodic sensor networks: Local aggregation and Frequency filtering aggregation. In the first one we provided an aggregator for simple captured measurements based on a link similarity function while in the second level our objective is to detect and aggregate multiple data sets generated by different neighboring nodes. We proposed a new frequency filtering approach and several optimizations using sets similarity functions to find similar data sets. 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.

We have two major directions for our future work. The first direction seeks to adapt our proposed method to take into account reactive periodic sensor networks, where sensor nodes operate with different sampling rate. In periodic applications the dynamics of the monitored condition or process can slow down or speed up; and to save more energy the sensor node can adapt its sampling rates to the changing dynamics of the condition or process. The second direction 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. 4 .

 4 Fig. 4. Total energy dissipation

Algorithm 1

 1 Prefix-filtering based algorithm. Set of measures' sets M {M1, M2...Mn}, and a threshold t. Ensure: All pairs of sets (Mi, Mj), such that J(Mi, Mj) ≥ t.

	11:	end for
	12:	Iw s ← Iw s ∪ {Mi}
	13:	else
	14:	create Iw
	15:	Iw ← Iw ∪ {Mi}
	16:	end if
	17:	end for
	18:	for each Mj such that X[Mj] > 0 do
	19:	if Os(Mi, Mj) ≥ α then
	20:	(S ← {(Mi, Mj)})
	21:	end if
	22:

Require:

1: S ← ∅ 2: Ii ← ∅ (1 ≤ i ≤ total number of measures) 3: for each set Mi ∈ M do 4: p ← |Mi| -⌈t × |Mi|⌉ + 1 5:

X ← empty map from set id to int 6:

for k ← 1 to p do 7:

w ← Mi[k] 8:

if (Iw s exists such that link(w, ws) = 1) then 9:

for each Measurement (Mj[l]), f (Mj[l]) ∈ Iw s do 10: X[Mj] ← X[Mj] + 1

in our experiments we used the binary search