Fred Jendrzejewski

Alain Bernard

Killian Mueller

Patrick Cheinet

Vincent Josse

Marie Piraud

Luca Pezzé

Laurent Sanchez-Palencia

Alain Aspect

Philippe Bouyer

K Müller

Three-dimensional localization of ultracold atoms in an optical disordered potential

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Anderson localization (AL) was proposed more than 50 years ago [1] to understand how disorder can lead to the total cancellation of conduction in certain materials. It is a purely quantum, one-particle effect, which can be interpreted as due to interference between the various amplitudes associated with the scattering paths of a matter wave propagating among impurities [2]. Anderson localization is predicted to strongly depend on the dimension [3]. In the three-dimensional (3D) case, a mobility edge is predicted, which corresponds to an energy threshold separating localized from extended states. Determining the precise behavior of the mobility edge remains a challenge for numerical simulations, microscopic theory and experiments [2]. The quest for AL has been pursued not only in condensed matter physics [4], but also in wave physics [START_REF] Van Tiggelen | Diffuse waves in complex media[END_REF]: for instance with light waves [6][7][8][9], microwaves [10,11] and acoustic waves [12]. Following theoretical proposals [13][14][15][16][17][18], recent experiments [19,20] have shown that ultracold atoms in optical disorder constitute a remarkable system to study 1D localization [21][22][START_REF]The related phenomenon of dynamical localization, i.e. localization in the p-space, has also been observed and studied with cold atoms realizing 'kicked rotors[END_REF]. Here, we report a study of 3D localization of ultracold atoms suspended against gravity, and released in a 3D optical disordered potential with short correlation lengths in all directions. We observe density profiles composed of a steady localized part and a diffusive part. Our observations are compatible with the self-consistent theory of AL [START_REF] Vollhardt | Electronic Phase Transitions[END_REF], taking into account the specific features of the experiment, and in particular the broad energy distribution of the atoms placed in the disordered potential. The localization we observe cannot be interpreted as trapping of particles with energy below the classical percolation threshold.

Our scheme (Fig. 1a) is a generalization of the one that allowed us to demonstrate AL in 1D [15,19]. It involves a dilute Bose-Einstein condensate (BEC) with several 10 4 atoms of 87 Rb, initially in a shallow quasi-isotropic Gaussian optical trap, released and suddenly submitted to an optical disordered potential generated by a laser speckle [START_REF][END_REF]. The atoms, in the |F = 2, m F = -2 hyperfine state of the ground electronic state, are suspended by a magnetic gradient that compensates gravity (the residual component of the magnetic potential is isotropic and repulsive, of the form -mω 2 r 2 /2, with ω = 7 s -1 ). In the experiments reported here, we observe a uniform loss of atoms, with a decay constant of ∼ 5 s, which we compensate by rescaling all profiles to a fixed total number of atoms. In the absence of disordered potential, we observe the free ballistic expansion of the BEC, induced by the initial interaction energy, as well as the expansion of the thermal wings. This allows us to determine the maximum velocity v max ∼ 0.5 mm/s in the expanding BEC (corresponding to a chemical potential of the trapped BEC µ in = 3mv 2 max /4 of the order of µ in /h ≃ 40 Hz, where m is the mass of the atom, and h the Planck constant). A Gaussian fit to the velocity distribution in the wings yields a rms velocity of ∼ 0.3 mm/s, i.e. a temperature of T ∼ 1 nK (k B T /h ∼ 20 Hz, where k B is the Boltzmann constant). The condensed fraction is ∼ 55% ± 5% of the total number of atoms.

The optical disordered potential is switched on, in less than 100µs, at time t i = 50 ms after release, i.e. in a situation where residual atom-atom interaction energy is small compared to the disorder amplitude V R (∼ 10 Hz compared to 100 -1000 Hz. As shown in ref. 26, a well controlled disordered potential can be obtained using the speckle field realized by passing a far detuned laser beam through a diffusive plate [START_REF] Goodman | Speckle Phenomena in Optics: Theory and Applications[END_REF]. In order to create a 3D disorder with a small correlation length along any direction of space, we cross two coherent orthogonal speckle fields (see Fig. 1a). They have the same polarization (along the y-axis), which yields an interference pattern sketched in Fig. 1b. The laser has a wavelength of 532 nm, detuned far below the 87 Rb resonance at 780 nm, so that the disordered potential is positive or null at any point. More precisely, the disorder has the single-point probability distribution P(V ) = V R exp(-V /V R ), maximum at V = 0, and of average value equal to its standard deviation V R (hereafter denoted the "amplitude"), which can be varied up to V R /h = 1.1 kHz. Figure 1c shows cuts of the autocorrelation function of the disorder.

A 3D Gaussian fit of this autocorrelation function yields standard rms radii of 0.11 µm, 0.27 µm and 0.08 µm, along the main axes (axis y and the two bisecting lines of x -z), with thus a maximum anisotropy factor of 3. Their geometric average provides the characteristic correlation length σ R ≃ 0.13 µm. The corresponding correlation energy [17] E R = 2 /mσ 2 R is larger than the disorder amplitude used in the experiment (E R /h ≃ 6.5 kHz, to be compared to V R /h ∼ 0.1 -1.1 kHz), so that we work in the quantum disorder regime, which does not support bound states in local minima of the disordered potentials.

We study how the expansion of the released atomic cloud is affected when we apply the speckle potential, for several values of the disorder amplitude V R . Figure 1d shows the observed column density ñ(y, z, t) = dx n(x, y, z, t) [where n(x, y, z, t) is the atomic density of the expanding cloud], for two different values of the disorder amplitude V R . For the small value (V R /h = 135 Hz) the behaviour is essentially diffusive, as can be checked by observing that at long enough times the rms widths ∆y and ∆z increase as (t -t i ) 1/2 , and the column density in the center, ñ(y = 0, z = 0, t), decreases as (t -t i ) -1 . For the large value of the disorder amplitude (V R /h = 680 Hz), the observed density distribution (see also cuts of the column density along y and z in Fig. 2) is the sum of two contributions with weights of the same order of magnitude: (i) a steady localized part, which is the replica of the initial profile ñi (y, z), i.e. the BEC and its thermal wings at t = t i ; (ii) an evolving diffusive part.

More precisely, we have found that we can decompose the observed column density as

ñ(y, z, t) = f loc × ñi (y, z) + ñD (y, z, t) (1)
where f loc is the localized fraction, and ñD (y, z, t) is the diffusive contribution. This decomposition is consistent with the observation that in the long time limit, the column density at the center evolves as ñ(0, 0, t)/ñ i (0, 0) = f loc + A/(t -t i ), as shown in the inset of Fig. 3. We can then determine f loc as the vertical axis intercept of the plot of ñ(0, 0, t)/ñ i (0, 0) versus 1/(t -t i ). Figure 3 shows the result of that simple analysis of the data, carried out for different values of V R . We find a localized fraction starting from zero for vanishing disorder, then increasing with V R , and reaching a nearly saturating value of ∼ 22% at V R /h ∼ 400 Hz.

As explained in the following, we interpret the localized and diffusive contributions as due to atomic energy components below and above the mobility edge E c , respectively.

In order to compare the experimental results with theory and check whether they are consistent with AL, we use quantum transport theory, taking into account the specific features of our experiment: i) the broad spatial extension of the atomic gas at the initial time t i ; ii) its energy distribution induced by the sudden application of the disordered potential at time t i ; iii) the anisotropy of the 3D speckle potential. We write the spatial density of the atomic gas as [15,16,18]

n(r, t) = dr i dE D i (r i , E)P (r -r i , t -t i |E) , (2)
where D i (r, E) represents the semi-classical joint position-energy density just after the time t i when the speckle potential is switched on, and P (rr i , t -t i |E) is the (anisotropic) probability of quantum diffusion, i.e. the probability distribution that a particle of energy E, placed in point r i at time t i , is found in r at t. The distribution D i (r, E) depends on both the initial expansion of the atomic gas for 0 < t < t i , and the disordered potential at t = t + i . In the experiment, the sudden application of the disordered potential (in ∼ 100µs) at time t i hardly affects the density profile, n i (r), but dramatically broadens the energy distribution

since the disorder is strong (V 2 R /E R ≫ µ in ).
We thus assume separation of the position and energy variables, i.e. we write D i (r, E) = n i (r) × f i (E). The initial density profile n i (r) is determined from fits to the measured density profile at time t i (see Fig. 2). The energy distribution f i (E), averaged over the disorder, is calculated from direct numerical diagonalization of the noninteracting Hamiltonian for various realizations of the disordered potential (see Methods). We find that f i (E) is peaked around energy V R (the average value of the disordered potential) with a half width at half maximum, ranging from ∼ 10Hz×h

(for V R /h = 135Hz) to ∼ 100Hz×h (for V R /h = 1088Hz).
The quantity P (r ′ , t ′ |E), whose character changes from localized to extended at the mobility edge E c , plays the central role in AL. We calculate it, for our 3D speckle potential, in the framework of the self-consistent approach [START_REF] Vollhardt | Electronic Phase Transitions[END_REF]: The incoherent (Boltzmann) diffusion tensor is first evaluated in the on-shell Born approximation, using quantum transport theory adapted to disordered potentials with non-isotropic correlation functions [START_REF] Wölfle | [END_REF], hence generalizing the approach of ref. This provides an equation for the dynamic, quantum corrected diffusion tensor, D * (E, Ω), which is finally solved self-consistently in the long time limit (Ω → 0).

In the localization regime (E < E c ), P (r ′ , t ′ |E) is a static, anisotropic, exponentially localized function with localization lengths L u loc (E) along the transport main axes (axis y and the two bisecting lines of x-z). We find that L u loc (E) is smaller than 5µm, except in a narrow energy window ∆E close to the mobility edge E c where it diverges (e.g. ∆E/h ∼ 20Hz for V R /h = 680Hz). Since the localization lengths are smaller than the imaging resolution (5µm) and the initial size of the atomic gas (Thomas-Fermi radius of the BEC ∼ 25 µm) for almost all energy components, we can safely use

P (r ′ |E) ≃ δ(r ′ ) in equation (2) for E < E c .
This yields a stationary profile, which is simply a replica of the initial profile ñi (y, z) with a weight of f loc = Ec -∞ dE f i (E). We identify it with the first term in equation ( 1) and can then compare the measured values of f loc with the result of the theoretical calculation.

Due to the narrow width of the energy distribution (see above), the calculated value of f loc is very sensitive to any approximation in the theoretical calculations (e.g. on f i (E) or E c ) and uncertainty on experimental parameters (in particular the amplitude V R and the details of the disordered potential) and we found quantitative discrepancies between experimental values and ab initio calculations of f loc . As shown in Fig. 3, however, a fair agreement is obtained by introducing heuristically an energy shift equal to +3.35V 2 R /E R (i.e. ∼ 240 Hz×h for V R /h = 680 Hz) on the numerically calculated energy distribution.

In the diffusion regime (E > E c ), P (r ′ , t ′ |E) is an anisotropic Gaussian function of timedependent rms widths 2D u * (E)t along the transport main axes. When incorporated into equation ( 2), these components yield a contribution to the profile that evolves in time. We identify it with the second term in equation (1), whose value at the center vanishes in the long time limit. In addition, the expansion with time of that diffusive part allows us to make another comparison between experimental and theoretical results. As shown in the inset of Fig. 4, we find that the experimentally measured rms sizes ∆u, along the u ∈ {y, z} axes, vary according to ∆u(t) 2 = ∆u(t i ) 2 + 2 D u (t -t i ). This allows us to determine "average" diffusion coefficients, D u , which are plotted in Fig. 4 versus the disorder amplitude V R .

We can then compare them to the theoretical values for the average quantum corrected diffusion coefficients, D u * = dE f i (E)D u * (E). Note that while axis y is a transport main axis, axis z is the diagonal between two main axes, so that D z * (E) is the half sum of the diffusion coefficients along these two main axes. As shown in Fig. 4, we find a fair agreement between experimental data and theoretical calculations. In particular, the anisotropy of the diffusion tensor is well reproduced. Note that the theoretical calculations do not involve any free parameter, apart from the heuristic energy shift (+3.35V 2 R /E R ) discussed above. The fair agreement between theory and experiment allows us to interpret the behavior of f loc (Fig. 3) and D u (Fig. 4), as resulting from the competition of two effects, when V R increases. On the one hand, for each energy component, the incoherent (Boltzmann) mean free path l B (E), and thus the diffusion coefficient D u * (E), decrease. According to the Ioffe-Regel criterion for localization [29], k E l B (E)

1 (where k E = √ 2mE/ is the typical particle wavevector at energy E), the mobility edge E c then increases, so that f loc increases. This effect dominates for weak disorder (V R 400 Hz). On the other hand, the energy distribution broadens and populates higher energy components. This latter effect approximately compensates the former one for stronger disorder (V R 500 Hz). Hence, the localized fraction reaches a plateau of about f loc ≃ 22%, while the average diffusion coefficient stops decreasing when it reaches a value of about D y,z ≃ 3 -6 × ( /3m).

The experimental results presented here show a clear evidence that when a large enough disordered potential is applied to an expanding 3D BEC, a fraction of the atoms (up to 22%) gets localized. It is then natural to ask whether it corresponds to 3D AL. To address that question, we rely on various theoretical arguments. Firstly, our observations are incom-patible with classical localization of particles with an energy below the classical percolation threshold, which is less than 10 -2 V R for our 3D speckle: the fraction of the atoms with a lower energy is negligible (see Methods). Actually, in our situation of quantum disorder, the effective percolation threshold may even be lower, as trapping near potential minima is forbidden. Secondly, our quantitative measurements of the localized fraction are consistent with a scenario based on the self-consistent theory of Anderson localization, applied to the exact experimental situation. We obtain a good quantitative agreement, provided we take into account the strong modification of the atoms energy distribution when the disordered potential is applied, as calculated numerically and displaced by a heuristic shift. A large fraction of the atoms have then an energy above the theoretical value of the mobility edge E c . The calculation is however too sensitive to uncertainties in the experimental parameters, and to approximations in the calculation, to permit a fully quantitative test of the theory.

In order to test precisely theories of 3D AL, a major experimental improvement would be a method to release, in the disordered potential, a sample of atoms with a narrow energy distribution, controlled at will, and experimentally measurable. It would then be possible to explore the localization transition, in particular to measure the exact value of E c , and to determine critical exponents. A further major change in the experiment will be the control of interactions between the atoms, since the effect of interactions on AL is an open problem of major interest, in particular in 3D [4,22].

It will also be important to clarify the status of the energy shift, which has been introduced heuristically. On one hand, its simple form (∝ V 2 R ) suggests that it may be partially due to some disregarded term at Born order, for instance the shift of energy states, which is not taken into account in the on-shell approximation of the self-consistent theory of AL, but which might be significant [30]. On the other hand, the above form of the shift may be too simple, as suggested by the discrepancy with experimental data obtained for the highest values of V R in Fig. 3, and the search of a more elaborated form may lead to a better understanding of the localization phenomenon we have observed.

cussions. This research was supported by the European Research Council (FP7/2007-2013 Grant Agreement No. 256294), the Agence Nationale de la Recherche (ANR-08-blan-0016-01), the Ministère de l'Enseignement Supérieur et de la Recherche, the Délégation Générale de l'Armement, the Triangle de la Physique and the Institut Francilien de Recherche sur les Atomes Froids. We acknowledge the use of the computing facility cluster GMPCS of the LUMAT federation (FR LUMAT 2764)

METHODS

Energy distribution

Since the initial chemical potential of the BEC (µ in ) and the thermal energy (k B T ) are smaller than the disorder parameters, the energy distribution can be approximated by f i (E) ≃ A(k = 0, E), where A(k, E) = k|δ(E -H)|k is the spectral function of the disordered medium, with H = -2 ∇ 2 /2m+ V (r) the noninteracting Hamiltonian associated to a realization of the disordered potential V (r). In order to calculate A(k = 0, E), we decompose the operator δ(E -H) onto the energy eigenbasis, as obtained by direct numerical diagonalization of the hamiltonian H. The numerical results are obtained in a box of linear length ∼ 15λ and of grid step ∼ 0.2λ (λ = 532nm is the laser wavelength). The disorder average is performed over 100 realizations of V (r), with the parameters of the 3D speckle potential used in the experiments.

Percolation.

The percolation threshold, E p , is the energy such that all classical particles of energy E < E p are trapped in finite-size allowed regions. We have numerically evaluated the percolation threshold of the 3D speckle potential used in the experiment. Using various values of the grid step, the numerical calculations provide an upper bound for the percolation threshold, E p ≤ 4(1)×10 -3 V R . Note that, above E p , the fraction of classical trapping regions quickly decreases and, according to our numerical calculations, it essentially vanishes for E ≥ 8(1)×10 -3 V R . Taking into account the energy distribution f i (E) calculated numerically, with or without the heuristic energy shift (see text), we find that the fraction of classically The corresponding quantum-corrected average diffusion coefficients, D u * , obtained from the selfconsistent theory of localization are shown as solid cyan (y) and purple (z) lines.

  17

  . The terms corresponding to the quantum interference between the various diffusing paths are then incorporated in the form of the Cooperon contribution.

FIG. 1 .

 1 FIG. 1. Experimental set up. (a) A dilute Bose-Einstein Condensate (BEC) of ultra-cold 87 Rb atoms, initially trapped by the red-detuned crossed laser beams, is released and submitted to a repulsive disordered potential realized by the optical speckle field produced by two crossed, blue-detuned, coherent laser beams along the x-and z-axes, passed through diffusive plates. The (paramagnetic) atoms are suspended against gravity by a magnetic field gradient (produced by the yellow coils), and the expansion of the atomic cloud can be observed for times as long as 8s. (b) Representation (false colors) of the disordered potential in the x = 0, y = 0, and z = 0 planes. (c) Plots of the 3D autocorrelation function of the disordered potential in the x = 0, y = 0, and z = 0 planes (the equal level lines represent levels separated by 14% of the maximum value). The correlation radii are 0.11 µm, 0.27 µm and 0.08 µm, along the main axes (axis y and the two bisecting lines of x -z). (d) 3D expansion of the atomic cloud for two values of the disorder amplitude. The plots show column density, rescaled to the same maximum, in the y -z plane,as observed by fluorescence imaging along the x-axis at various delays after application of the disorder. For small disorder (V R /h = 135 Hz), we observe an essentially diffusive expansion. For larger disorder (V R /h = 680 Hz), a significant fraction of atoms is localized: in the center, the localized atoms emerge in the form of a steady peak, which is a replica of the initial density profile of the BEC.

FIG. 2 .

 2 FIG.2. Density profiles: experiment vs. theory. The figure shows cuts of the column density profiles along y [ñ(y, 0, t), left column] and z [ñ(0, z, t), right column], imaged at various delays after application of the disorder, in a situation of significant localization (V R /h = 680 Hz). The black dots are the experimental data. The solid gray lines in the upper panels are fits to the experimental data at the initial time t i , of the theoretical profile of a BEC in the Thomas-Fermi regime for the optical Gaussian trap, plus the thermal fraction. This fitted total profile, multiplied by the theoretical localized fraction f loc (see text and purple line in Fig.3), yields the red profiles, describing the localized contribution. Adding the theoretically determined diffusive part, we obtain the green profiles, corresponding to the complete equation(2).

FIG. 3 .FIG. 4 .

 34 FIG. 3. Localized fraction.The inset shows experimental data for the ratio of the column density in the center to its initial value, ñ(0, 0, t)/ñ i (0, 0), versus the inverse time delay after switching on the disorder, 1/(t -t i ) (blue points), together with a linear fit at long times (dashed blue line), for V R /h = 680Hz. The intercept of this fit with the vertical axis provides the localized fraction, f loc (red point). The main panel shows the values of f loc obtained by this procedure as a function of the disorder amplitude V R (red points with errorbars). The solid purple line shows the results of the theoretical calculation, including the heuristic energy shift +3.35V 2 R /E R on the energy distribution (see text).

ACKNOWLEDGEMENTS

We thank S. Seidel and V. Volchkov for experimental contributions, M. Besbes for assistance on numerical calculations, and T. Giamarchi and B. van Tiggelen for useful dis-


Maxime Crochemore

Szilárd Zsolt

Fazekas 3⋆

Costas Iliopoulos

Inuka Jayasekera

Number of occurrences of powers in strings

We show a Θ(n log n) bound on the maximal number of occurrences of primitively-rooted k-th powers occurring in a string of length n for any integer k, k ≥ 2. We also show a Θ(n 2 ) bound on the maximal number of primitively-rooted powers with fractional exponent e, 1 < e < 2, occurring in a string of length n. This result holds obviously for their maximal number of occurrences. The first result contrasts with the linear number of occurrences of maximal repetitions of exponent at least 2.

Introduction

The subject of this paper is the evaluation of the number of powers in strings. This is one of the most fundamental topics in combinatorics on words not only for its own combinatorial aspects considered since the beginning of last century by the precursor A. Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF], but also because it is related to lossless text compression, string representation, and analysis of molecular biological sequences, to quote a few applications. These applications often require fast algorithms to locate repetitions because either the amount of data to be treated is huge or their flow is to be analysed on the fly, but their design and complexity analysis depends on the type of repetitions considered and on their bounds.

A repetition is a string composed of the concatenation of several copies of another string whose length is called a period. The exponent of a string is informally the number of copies and is defined as the ratio between the length of the string and its smallest period. This means that the repeated string, called the root, is primitive (it is not itself a nontrivial integer power). We consider two types of strings: integer powers-those having an integer exponent at least 2, and fractional powers-those having a fractional exponent between 1 and 2. For both of them we consider their maximal number in a given string as well as their maximal number of occurrences.

It is known that all the occurrences of integer powers in a string of length n can be computed in time O(n log n) (see three different methods in [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF], [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF], and [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]). Indeed these algorithms are optimal because the number of occurrences of squares (powers of exponent 2) can be of the order of n log n [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF].

The computation of occurrences of fractional powers with exponent at least 2 has been designed initially by Main [START_REF] Main | Detecting leftmost maximal periodicities[END_REF] who restricted the question to the detection of their leftmost maximal occurrences only. Eventually the notion of runsmaximal occurrences of fractional powers with exponent at least 2-introduced by Iliopoulos et al. [START_REF] Iliopoulos | A characterization of the squares in a Fibonacci string[END_REF] for Fibonacci words, led to a linear-time algorithm for locating all of them on a fixed-sized alphabet. The algorithm, by Kolpakov and Kucherov [9,[START_REF] Kolpakov | On maximal repetitions in words[END_REF], is an extension of Main's algorithm but their fundamental contribution is the linear number of runs in a string. They proved that the number of runs in a string of length n is at most cn, could not provide any value for the constant c, but conjectured that c = 1. Rytter [START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF] proved that c ≤ 5, then c ≤ 3.44 in [START_REF] Rytter | The number of runs in a string[END_REF], Puglisi et al. [START_REF] Puglisi | How many runs can a string contain?[END_REF] that c ≤ 3.48, Crochemore and Ilie [START_REF] Crochemore | Maximal repetitions in strings[END_REF] that c ≤ 1.6, and Giraud [START_REF] Giraud | Not so many runs in strings[END_REF] that c ≤ 1.5. The best value computed so far is c = 1.029 [START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF] (see the Web page http://www.csd.uwo.ca/ ilie/runs.html). Franek et al. showed a lower bound of 0.927...n in [START_REF] Franek | The maximum number of runs in a string[END_REF], which was improved to 0.944565n by Matsubara et al. in [START_REF] Kusano | New lower bounds for the maximum number of runs in a string[END_REF] and to 0.944575n by Puglisi and Simpson. (see the Web page http://www.shino.ecei.tohoku.ac.jp/runs/). These lower bounds also point in the direction of Kolpakov and Kucherov's conjecture.

Runs capture all the repetitions in a string but without discriminating among them according to their exponent. For example, the number of runs is not easily related to the number of occurrences of squares. This is why we consider an orthogonal approach here. We count and bound the maximal number of repetitions having a fixed exponent, either an integer larger than 1 or a fractional number between 1 and 2. We also bound the number of occurrences of these repetitions.

After introducing the notations and basic definitions in the next section, Section 3 deals with fractional powers with exponent between 1 and 2. It is shown that the maximum number of primitively-rooted powers with a given exponent e, 1 < e < 2, in a string can be quadratic as well of course as their maximum number of occurrences. In Section 4, we consider primitively-rooted integer powers and show that the maximum number of occurrences of powers of a given exponent k, k ≥ 2, is Θ(n log n). This latter result contrasts with the linear number of such powers. We also present an efficient algorithm for constructing the strings in question.

Preliminaries

In this section we introduce the notation and recall some basic results that will be used throughout the paper. All results stated in this section are reported from [START_REF] Lothaire | Applied Combinatorics on Words[END_REF]. An alphabet A is a finite non-empty set. We call the elements of A letters. The set of all finite words over A is A * , which is a monoid with concatenation (juxtaposition), where the unit element is ǫ, the empty word, whereas the set of non-empty words is A + = A * -ǫ. The length of a word w is denoted by |w|; |ǫ| = 0. Without loss of generality, we can assume that our alphabet is ordered and hence we have an ordering on words. The one we will use is called the lexicographical order and is defined by the following relation:

x ≤ y ⇔ (xisapref ixof y or (x = uavandy = ubwanda < b))
where a, b ∈ A and u, v, w ∈ A * .

For words u, v, w ∈ A * , with w = uv, we say that u is a prefix and v is a suffix of w. For a word w and an integer n ≥ 0, the n-th power of w is defined inductively as w 0 = ǫ, w n = ww n-1 . Extending this definition we can talk about non-integer powers too. Take n = k l > 1 with gcd(k, l) = 1. We say that a word w is an n-power if both of the following conditions apply:

-|w| = m • k for some integer m > 0, -m • l is a period of w.
The prefix of length m • l of w is a root of w. When w = ǫ, w 3 is called a cube, with root w. A word w is called primitive if there is no word u and integer p ≥ 2 such that w = u p . We say that w ′ is a conjugate of w if there exist u, v ∈ A * such that w = uv and w ′ = vu. A Lyndon word is a (primitive) word which is the lexicographically smallest among its conjugates.

Let uv be a primitive word such that vu forms a Lyndon word and v is nonempty. In the cube (uv) 3 , we call central Lyndon position the position |uvu| For two non-empty words u and v it is known that uv = vu implies u, v ∈ z + for some z ∈ A * , therefore every word has a unique Lyndon position.

If a word w can be written as w = uv = vz, for some words u, v, z ∈ A + , then we say that w is bordered (v is a border of w). If a word w is bordered, then there exists u ∈ A + , v ∈ A * such that w = uvu, that is, a bordered word w always has a border of length at most half the length of w. Moreover, it is easy to see that a bordered word uvu cannot be a Lyndon word, because then either uuv (if u < v) or vuu (if v < u) is lexicographically smaller than uvu.

A bound on repeats with exponent e, 1 < e < 2

In this section, we show that the maximal number of distinct repetitions with exponent e, 1 < e < 2, is lower bounded by Θ(n 2 ). We do this by looking at the number of such repetitions that can start at a position in words of the form a k ba k e-1 -1 , where k is any positive integer such that c|k, where e = c+d d and gcd(c + d, d) = 1. First we consider an example with e = 3 2 and k = 9, i.e. w = a 9 ba 17 (see Fig 1). At the first position in this word, we can have 5 repetitions of exponent 3 2 , namely a 9 ba 5 , a 9 ba 8 , a 9 ba 11 , a 9 ba 14 and a 9 ba 17 . Moving on to the second position, we have only 4 repetitions of exponent 3 2 , namely a 8 ba 6 , a 8 ba 9 , a 8 ba 12 and a 8 ba 15 . In the third position also, we have the repetitions a 7 ba 7 , a 7 ba 10 and a 7 ba 13 . However, now we have one extra repetition as we can also have a 7 ba 4 . It is clear that at every other position in the word, as we get closer to the occurrence of b, we have an extra repetition. The numbers of primitively-rooted repetitions of exponent 3 2 at each position are 5, 4, 4, 3, 3, 2, 2, 1, 1 (see Fig. 1). The total number of repetitions can now be summed up to ((5 * 6)/2) + (((5 -1) * 5)/2) = 25. We generalise this example in the next theorem.

Theorem 1. The maximal number of distinct repetitions of exponent e, with 1 < e < 2, in a word of length n is Θ(n 2 ).

Proof. The upper bound is trivial because no factor of the string can be counted twice as an e-power for given e, so let us turn to proving the lower bound. We shall count the number of repetitions starting at each position in a word. For an exponent e, 1 < e < 2, we consider a word, w, formed as shown in Fig. 2. Here, we concatenate a repetition of exponent, e, with root a k b and a a a a a a a a a a b a a a a a a a a a a a a a a a a a For e-powers starting at the first position, the end positions can be (k+1)(e-1), (k + 1)(e -1) + (c + d), (k + 1)(e -1) + 2 • (c + d), etc. From here we get that the number of e-powers starting at the first position is

|w| -(k + 1)(e -1) c + d + 1 = k • e e-1 -(k + 1)(e -1) c + d + 1
Substituting c+d d for e in the formula above we get that the number of e-powers starting at the first position is:

k • d -c d • c - 1 d + 1
This formula proves useful because by substituting k -i for k and taking the integer part of the result (since we are talking about the number of occurrences) we get the number of e-powers starting at position i + 1. Now let us sum up the number of e-power occurrences starting at any one of the first k positions:

k i=1 ⌊i • d -c d • c - 1 d + 1⌋
For any positive n its integer part ⌊n⌋ is greater or equal than n -1. As we are trying to give a lower bound to the number of occurrences, it is alright to subtract 1 from the formula instead of taking its integer part:

k i=1 i • d -c d • c - 1 d = k • (k + 1) • d -c 2d • c - k d
This means that the number of e-powers in our string is quadratic in k. At the same time the length of the string, as we mentioned in the beginning, is k • e e-1 , so for a given e, the number of e-powers in a string of length n is Θ(n 2 ). It is easy to see that every occurrence of an e-power in this string is unique and this concludes the proof.

⊓ ⊔

A bound on primitively-rooted cubes

After considering powers between 1 and 2, we have look at powers greater than 2. First, we show that it is possible to construct strings of length n, which have Ω(n log n) occurrences of cubes. We can extend the method to all integer powers greater than 2, and this, together with the O(n log n) upper bound implied by the number of squares (see [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF]) leads us to the Θ(n log n) bound. Finally, we will prove that the sum of all occurrences of powers at least 2 (including non-integer exponents) is quadratic.

Lemma 1. The maximal number of primitively-rooted cubes in a word of length n is Θ(n log n).

Proof. Let us suppose there are two primitively-rooted cubes (uv) 3 and (xy) 3 in w such that their central Lyndon positions uvu.vuv and xyx.yxy are the same. First let us look at the case where the cubes have to be of different length.

Without loss of generality we can assume |uv| < |xy|. In this case vu is at the same time a prefix and suffix of yx. Hence, yx is bordered and cannot be a Lyndon word contradicting the assumption that x.y is a Lyndon position.

This proves that should there be more cubes which have their central Lyndon position identical, they all have to be of the same length. Naturally, the first and last position of a word cannot be central Lyndon to any cube and this gives us the bound n -2 if we disregard cubes of the same length which have their central Lyndon positions at the same place (see Fig. 3). It is easy to see, that because of the periodicity theorem the only string of length n, for which n -2 different positions are central Lyndon ones to some cube, is a n . Now take the word a 4k+3 . According to our previous argument it has at most 4k + 1 cubes. However, if we change a's into b's at positions k + 1,2k + 2 and 3k + 3 we get that the number of primitively-rooted cubes in this word is 4k + 1 -9 + (k + 1) = 5k -7. This is because by introducing each b we lose three cubes but in the end we gain another k + 1 cubes of the form (a j ba k-j ) 3 with 0 ≤ j ≤ k (see Fig. 4). Note that these latter cubes all have their central Lyndon position after the first b (assuming a < b).

We introduced three b's in the previous step but of course we can repeat the procedure for the four block of a's delimited by these b's and then in turn for the new, smaller blocks of a's that result and so on. In the second step, however, we need to introduce 12 b's -that is, 3 for each of the 4 blocks of a's -not to disrupt the cubes of length 3k + 3. This way we lose 12 • 3 = 36 cubes and we gain (⌊(k -3)/4⌋ + 1) • 4 new ones. Performing the introduction of b's until the number of cubes we lose in a step becomes greater or equal to the ones we gain, gives us a string with the maximal possible number of cubes for its length. If k equals 4j, 4j + 1 or 4j + 2 for some j then according to the formula above the number of cubes we gain is 4j. Note that if k = 4j + 3 than the number of cubes we gain in the second step is 4j + 4 = k + 1, i.e. the same as in the first step. However, together with the delimiting b's introduced before we would get a big cube which is not primitively-rooted anymore, so we need to move the newly introduced b's 1, 2 and 3 positions to the left, respectively. This gives us that in this case too the number of newly formed cubes will be 4j. The smallest length at which introducing the b's does not induce less cubes is 35 that is with k = 8. Summarizing the points above we get that for a string of length n the maximum increase in the number of cubes for the ith (i > 1) consecutive application of our procedure is:

(n -3) 4 -9 • 4 i-1
To be able to sum these increases we have to know the number of steps performed. This is given by solving for i the equation:

n -3 4 = 9 • 4 i-1
From here we get that the number of steps performed is #steps = ⌊log 4 n-3

9 ⌋, where by ⌊x⌋ we mean the integer part of x. Hence the number of cubes for length n ≥ 39 is:

n -2 + 1 + #steps i=1 n -3 4 -9 • 4 i-1 = n -1 + (n -3)⌊log 4 (n-3) 9 ⌋ 4 - 9(1 -4 ⌊log 4 n-3 9 ⌋ ) -3 = n + 2 + (n -3)⌊log 4 (n-3) 9 ⌋ 4 -3 • 4 ⌊log 4 n-3 9 ⌋
The plus one after n -2 comes from the first application of the insertion of b's where we get (n -3)/4 + 1 cubes instead of (n -3)/4. For strings shorter than 39 therefore the count is one less.

⊓ ⊔

Since the first paragraph of the proof is valid for any integer power, we can extend the proof by giving the construction of the strings that prove the lower bound in general for a string of length n and power k (see Fig. 4).

The algorithm above produces strings which have O(n log n) occurrences of k-th powers. Note, that if we perform the procedure the other way around, we only need O(log n) cycles and we can eliminate the recursion: Theorem 2. Algorithm ConstructStrings2 (see Fig. 4) produces a string of length n that has Ω(n log n) occurrences of primitively-rooted cubes.

Algorithm ConstructStrings1 (n, k) Input: n ≥ 0, k ≥ 0 Output: A string which proves the lower bound of the number of occurrences of integer powers. 1. ℓ = n 2. string = a ℓ 3. power(1, ℓ) 4. Procedure: power( start, end)

5. ℓ = end -start 6. if ℓ < k 3 + k 2 + k 7.
then return 8.

else

string[start + ⌊ℓ/(k + 1)⌋] = b 9. string[start + 2 • ⌊ℓ/(k + 1)⌋] = b 10. . . . 11. string[start + k • ⌊ell/(k + 1)⌋] = b 12.
for i ←0 to k 13.

power

(start + i • ℓ/(k + 1), start + (i + 1) • ℓ/(k + 1)) Algorithm ConstructStrings2 (n, k) Input: n ≥ 0, k ≥ 0
Output: A string which proves the lower bound of the number of occurrences of integer powers.

1. ℓ = n 2. while ℓ ≥ k 3 + k 2 + 3k + 2 3. do ℓ= ℓ-k k+1 4. string = (a k 2 +1 + b) k + a (k+1)•ℓ-k 3 -k 5. delimiter = b 6. while length(string) * (k + 1) + k < n 7.
do string = (string + delimiter) k + string 8.

if delimiter = b 9.

then delimiter = a 10.

else delimiter = b 11.

( * changing the delimiter is needed to stay primitive * ) 12. string = string + a n-length(string) Proof. Before entering the second while loop, the length of string and the number of k-th power occurrences in it are both c = (k + 1) • ℓ + k. Now we will show by induction on i that after the i-th iteration of the second while loop the length of string will be (k + 1) i • (c + 1) -1 and the number of occurrences of k-th powers will be (k + 1) i • c + i • (k + 1) i-1 (c + 1). Note that if the length of string was m and the number of k-th power occurrences was p after the previous cycle, then concatenating k + 1 copies of string delimited by k copies of delimiter we get (k + 1) • p + m + 1 powers in the new string, which will have length (k + 1) • m + k. Therefore, after the first cycle the length of string will be

(k + 1) • c + k = (k + 1) • c + (k + 1) -1 = (k + 1) 1 • (c + 1) -1
At the same time the number of k-th powers will be

(k + 1) • c + c + 1 = (k + 1) 1 • c + 1 • (k + 1) 0 • (c + 1)
so our statement holds for i = 1. Now suppose it is true for some i ≥ 1. From here we get that for i + 1 the length of string will be:

(k + 1) • ((k + 1) i • (c + 1) -1) + k = (k + 1) i+1 • (c + 1) -1
whereas the number of k-th powers is:

(k + 1) • ((k + 1) i • c + i • (k + 1) i-1 • (c + 1)) + ((k + 1) i • (c + 1) -1) + 1 = (k + 1) i+1 • c + i • (k + 1) i • (c + 1) + (k + 1) i • (c + 1) = (k + 1) i+1 • c + (i + 1) • (k + 1) i (c + 1)
Now let us look at the running time of the algorithm. In the first while loop we divide the actual length by k + 1 and we do it until it becomes smaller than k 3 + k 2 + k therefore we perform O(log n) cycles. The second while loop has the same number of cycles, with one string concatenation performed in each cycle, hence substituting log n for i in the formula above concludes the proof.

⊓ ⊔ Corollary 1. In a string of length n the maximal number of primitively-rooted k-th powers, for a given integer k ≥ 2, is Θ(n log n).

Proof. We know from [START_REF] Crochemore | Squares, cubes and time-space efficient stringsearching[END_REF] that the maximal number of occurrences of primitivelyrooted squares in a word of length n is O(n log n). This implies that the number of primitively-rooted greater integer powers also have an O(n log n) upper bound, while in Theorem 2 we showed the lower bound Ω(n log n). ⊓ ⊔ Remark 1. The first part of the proof is directly applicable to runs so we have that in a string of length n the number of runs of length at least 3p -1, where p is the (smallest) period of the run is at most n -2. Unfortunately we cannot apply the proof directly for runs shorter than that because we need the same string on both sides of the central Lyndon position.

We have seen that the number of k-th powers for a given k(≥ 2) in a string of length n is Θ(n log n), but what happens if we sum up the occurrences of k-th powers for all k ≥ 2? Remark 2. The upper bound of the sum of all occurrences of k-th powers with primitive root, where k ≥ 2, in a word w with |w| = n is n•(n-1)

2

. Moreover, the bound is sharp.

Proof. First consider the word a n , for some n > 0. Clearly, taking any substring a k , with 2 ≤ k ≤ n, we get a k-th power, so the number of powers greater or equal to two is given by the number of contiguous substrings of length at least two, that is n•(n-1)

2

. Now we will show that this is the upper bound. Let us suppose that any two positions i and j in the string delimit a k-th power with k ≥ 2, just like in the example above. We need to prove that the same string cannot be considered a k 1 -th power and a k 2 -th power at the same time, with k 1 , k 2 ≥ 2 and k 1 = k 2 . Suppose the contrary, that is there are 1 ≤ m < ℓ ≤ j-i 2 so that both m and ℓ are periods of w[i, j]. Since j -i > m + ℓ -gcd(m, ℓ) the periodicity lemma tells us that w[i, j] has a period p smaller than m with p|m and p|ℓ, and this, in turn, means w[i, i + ℓ] is not primitive.

⊓ ⊔ Theorem 3. The number of distinct k-th powers, for a fixed integer k ≥ 3, in a string of length n is at most n k-2 . Proof. We will show the upper bound by considering the last occurrences of every k-th power. The proof is split into two parts. We will prove the statement for cubes by considering their starting positions while for higher exponents we will look at their root positions (see below).

Let us start with the case k = 3. Suppose the last occurrence of two different cubes u 3 and v 3 with |u| < |v| start at the same position i in the string. By a simple argument we will arrive at a contradiction by looking at the two cases shown in Figure 5.

First let us look at the case when |u 3 | ≤ |v 2 |. In this case there is another occurrence of u 3 starting at position i + |v| contradicting our assumption of the previous occurrence being the last. Now we are left to treat the case when |v 2 | < |u 3 | < |v 3 |. The overlap between the two cubes in this case is at least 2 • |v| which is greater than |v| + |u| and from this, Fine and Wilf's theorem tells us it has a period of length gcd(|u|, |v|). Therefore, there exists some w such that u = w m and v = w n , for some integers m < n. It is easy to see then that in |w 3n | the last occurrence of |w 3m | starts at position i + 3 • (m -n) • |w| contradicting our assumption again. We showed that there can be no two different cubes which have their last occurrence starting at the same position. This implies the bound n for higher distinct powers as well. However, we can prove something stronger, as we claim in the theorem. To achieve that result, we will look at r oot positions. In a power u k starting at position i, with the smallest period of u being p, we will call position i + p the second root position, i + 2p the third root position and so on. We show that for the last occurrences of two 4-th powers u starting at position i and v 4 starting at position j, the following positions cannot coincide:

1. the second root position of u and the second root position of v:

-if 3|u| < 2|v| then u 4 occurs at i + |v|, contradiction; -if 2|v| ≤ 3|u| then according to Fine and Wilf's theorem v has period k • p, for some k and then u 4 occurs at i + p, contradiction. 2. the second root position of u and the third root position of v:

-if 3|u| ≤ |v| then u 4 occurs at i + |v|, contradiction; -if |v| < 3|u| ≤ 2|v| then again Fine and Wilf's theorem gives us u 4 occurring at i + p, contradiction; -if 2|v| < 3|u|: if this is the case then similarly as before u and v are powers of the same word and hence v 4 occurs at j + p, contradiction; 3. the second root position of v and the third root position of u:

-if 3|u| < |v| then u 4 occurs at i + |v|, contradiction; -if |v| ≤ 3|u| then u 4 occurs at i + p, contradiction. 4. the third root position of u and the third root position of v:

-if 2|u| ≤ |v| then u 4 occurs at i + |v|, contradiction; -if |v| < 2|u| then u 4 occurs at i + p.

We can apply the same argument for 5-th powers looking at the second, third and fourth root positions and so on for greater powers as well, getting the desired bound.

Conclusion

In conclusion, we have proven the following bounds on repetitions in words:

(i) The maximal number of distinct repetitions of exponent, e, with 1 < e < 2, in a word of length n is Θ(n 2 ). (ii) The maximal number of primitively-rooted k-th powers in a word of length n is Ω(n log n).

We have also described an O(m log n) algorithm which can be used to construct strings to illustrate these bounds. Here O(m) is the time complexity of concatenating two strings of length n.

  k e-1 -1 , where k is any positive integer such that c|k, where e = c+d d and gcd(c+d, d) = 1. (e -1)|k. length of our string is k • e e-1 .

Fig. 1 . 17 a 1 Fig. 2 .

 11712 Fig. 1. Repetitions of exponent 1.5 in a 9 ba 17

Fig. 4 .

 4 Fig. 4. Cubes of word a k ba k ba k ba k

4 4 |u 3 | < |v 2 |v 2 | < |u 3 | < |v 3 Fig. 5 .

 44322335 Fig. 5. Cubes u 3 and v 3 beginning at the same position i.

⋆ Supported by grant no. AP2004-6969 from the Spanish Ministry of Science and Education of Spain. Partially supported by grant. no. MTM 63422 from the Ministry of Science and Education of Spain. ⋆⋆ Supported by a DTA Award from EPSRC


Sylvain Cherrier

Yacine M Ghamri-Doudane

Stéphane Lohier

Gilles Roussel

Services Collaboration in Wireless Sensor and Actuator Networks: Orchestration versus Choreography

Keywords: Machine-To-Machine, Choreography, Orchestration, Wireless Sensor and Actuators Network, Services Oriented Architecture

Wireless Sensor and Actuator Networks (WSAN) and permanent connections to the Internet converge to be an emerging and promising field: Machine-To-Machine (M2M) services. To take advantages of this new field, hardware and software infrastructure compliance must be verified. Services expected by M2M alter the organization of WSAN. The software design in this area can be divided into two main categories: a centralized approach (Orchestration) where a monolithic application collects data and sends orders, and a distributed approach (Choreography) in which nodes offer and use services in a collaborative way. In this paper, we study the impact of these two architectures over WSAN. First, a mathematical analysis shows the improvement offered by choreography, thanks to the use of shorter paths between nodes. Then, an application experiments these two architectural designs to measure the impact on a real testbed. Both the theoretical mathematical analysis and the real platform experiment gives better results for the Choreography in terms of network reliability and path length. Our work quantifies the benefits obtained and provides histograms and numerical results.

I. INTRODUCTION

The world of sensors, actuators and "smart objects" is subject to strong constraints: very limited energy, low throughput rates, restricted processing power and memory space, etc. However the small contribution provided by each node is useful, and can help dealing with user's needs. Part of this ability to process information is primarily used to organize the network. At first glance, applications using this type of "smart objects" are organized around a central node called the sink. All information is uploaded to the sink, which is the link between the inside network and the world. The sink is unique: it often has boundless energy and a much better processing power. When merging into the wider world of M2M universal exchanges and interactions between objects, the use of WSN changes. From M2M perspective, WSAN is no more a redundant array of multiple similar sensors responsible for carrying out many measures of the same physical quantity. WSAN is rather a highly varied collection of small specialized objects, very different and complementary, responsible for coordinating actions or measures. From that point of view, the whole behaviour is modified. Data flows change from a "many-to-one" kind to a "one-to-one" node's communication, directly between sensors and actuators. Data types, message frequencies and uses become more heterogeneous. The sink role is reduced to a simple gateway to the wide Internet. Giving each component universal access from and to the Internet was the first step. The next step is the definition of new types of software designs that take into account WSAN constraints (i.e. mainly optimizing the network's lifetime) and M2M needs. The first architectural approach inherited from WSN (Orchestration) is centralized: a unique application, responsible for offering access and control to users, is located somewhere outside the WSAN, behind the sink. It gathers all the data collected. After processing them, the central application deduces actions to perform. Orders are then transmitted to the actuators present in the network. This centralized approach involves a specific traffic pattern in the network. The paths from nodes to sink (and sink to each node) are massively used, leading to congestion and high energy consumption. The other approach advocates a distributed application logic instead of the centralized one, when application characteristics allow its implementation. This approach, also known as Choreography, tries to process data and to give decisionmaking to the nodes themselves. Each node holds a part of the application, and executes some process over the data. Small interacting parts of the application are distributed over the network. Computing is performed inside the network, and communications can often be better disseminated over the network. When it is possible, decisions are made at node's level, no need to send information to any central application.

In this paper, we perform a thorough study of the impact on the network performance of these two different software designs for M2M over such a WSAN structure. Services Choreography and Orchestration solutions are compared in terms of network traffic loads and communication path length to determine the impacts of each approach regarding a more efficient and responsive design. The reminder is organized as follows: first, we present the related works and the background (Section II) attached to our approach. Our mathematical analysis is described in Section III, while Section IV focuses on testbed experiments and results. Finally, concluding remarks and future research directions are given.

II. BACKGROUND AND RELATED WORK

WSAN and M2M can be classified into multiple classes. One of them is "data-centric", which means that several sensors of the same type collect data from their environment. This is for example used in building or environment monitoring. In that case, users are mainly interested in values. Data are sent to the sink, or the sink looks for the value of a physical measurement [START_REF] Watteyne | from manet to ietf roll standardization: A paradigm shift in wsn routing protocols[END_REF]. To save energy, a cluster oriented solution can be adapted, because physically adjacent sensors detect approximately the same value, the same event, at the same time. Here, compression algorithm and data aggregation are the effective solution. But building M2M by the integration of WSAN in a superset leads to a different view of its use. M2M is made up of interactions between an eclectic collection of multiple objects to give the user a digital vision and use of his environment. Previous views of WSN presented in [START_REF] Kuorilehto | A survey of application distribution in wireless sensor networks[END_REF] such as "WSN performing a specific task", or "sending messages not to individual nodes but to geographical location or regions" may not apply to WSAN when put inside the M2M realm. Multiple components with highly diversified characteristics (a mix of heterogeneous sensors and actuators) are working together. Tilting from a "sensing" to an "interacting" vision, WSAN (as part of M2M) is more "event-centric" than "datacentric". This direct interaction between sensors and actuators is also called "coordination" [START_REF] Akyildiz | Wireless sensor and actor networks: research challenges[END_REF]. In this paper, the authors described the direct "sensor-actuator" communication as "Automated Architecture", while the usual mode is called "semi-Automated Architecture" because it needs a central controller, on the sink or beyond. Owing to industrial improvements, processing capabilities of smart objects increase, and the implementation of full Internet protocols suite becomes possible [START_REF] Dunkels | Making TCP/IP viable for wireless sensor networks[END_REF]. Therefore, at application level, considering the whole WSAN as a Service Oriented Architecture (SOA) makes sense [START_REF] Shelby | Embedded web services[END_REF]. Hence, in a services approach, the "semi-Automated Architecture" can be seen as a Services Orchestration, and "Automated Architecture" is implemented by a Services Choreography. The main difficulty for a real distributed application lies in the heterogeneity, especially in WSAN where hardware, Operating Systems and languages are various. Such diversity is opposed to a distributed organization of the software [START_REF] Alkazemi | towards a framework for engineering software development of sensor nodes in wireless sensor networks[END_REF], because "the source code of a node is tangled and tightly coupled", "Middleware interface and its composing components are not precisely identified", and "WSN codes development is done in an ad-hoc manner". This orientation towards services collaboration rather than basic hardware coding releases the coupling between devices (such as in "Message-Oriented Middleware" presented in [START_REF] Hadim | Middleware: Middleware challenges and approaches for wireless sensor networks[END_REF]). It also offers an easy way (when feasible) to design collaborative applications between nodes [START_REF] Barros | Standards for web service choreography and orchestration: Status and perspectives[END_REF]. But this new organization forces us to think about new perspectives and issues in managing this highly constrained network. "Many protocols and algorithms have been proposed for WSNs [but] they may not be well-suited for the unique features and application requirements of WSANs" [START_REF] Akyildiz | Wireless sensor and actor networks: research challenges[END_REF]. Furthermore, in "semi-Automated Architecture" (the traditional WSN application design, that we call in our services point of view an Orchestration), communication latency are not minimized and "transmitting the sensing data to the sink usually causes fast energy depletion of nodes which are around the sink" [START_REF] Nayak | Wireless sensor and actuator networks: algorithms and protocols for scalable coordination and data communication[END_REF]. We are interested here in quantifying the effects of these two architectural designs.

III. PROBLEM STATEMENT

A. Choreography and Orchestration

In the case of hierarchical networks of organizations, most protocols build solutions in tree form. Considering our network as a tree (see Figure 1), it is possible to evaluate the impact of application's design on this architecture. The way each node sees and uses the WSAN depends on that design. For example, consider an application build following an Orchestrated design. If node 9 is a sensor, and node 13 an actuator, the user may want node 13 to react to events detected by node 9. In that case, node 9 has a specific vision of the network (see Figure 2). Each message goes to node 2, then to the sink. After its trip through the outside network in direction of the central application, a second message containing the decided action comes back, relayed by the sink, going through node 2 to node 7, and then to node 13, its destination. The path from node 9 to node 13 is five Figure 2. From application perspective, the node is seen as the root of a new tree. Here, the path from node 9 to node 13, as seen by node 9 in a Choreography (left), or in an Orchestration (right) hops long. Note that node 2 is solicited twice: a first time on the way up to the sink, and a second time when the action message comes back. All the network's components behaviour is driven by the central application. All data must go to the sink, to be forwarded to the application, and then an action comes back in the network. In a Choreography, the global application is designed as a direct collaboration between nodes. In that architecture, the limited processing capacity of each node may be used to compute data closer to where it has been sensed, instead of being sent to a central application. Processing data consumes less energy than transmitting it (12.7 times less on a TelosB, 2.5 times less on a MicaZ1 ). Avoiding a hop and its transmission is always a good idea, especially if it is to relieve a node that is already overloaded (R2 in our example). In Choreography, a node sends information directly to an (or some) other node(s), and not to a central decision point. The logic of the application is distributed, and spread over the network. The decision about the action to take is made directly on nodes. Depending on the application's design, node's view of the global network is different. In a Choreography, as shown in Figure 2, the path from node 13 to node 9 is made of 3 hops. The message is delivered more quickly, with less risk of getting lost. Node 2 has only one message to transmit. Collision risks decrease. In Orchestration, the same needs of communication between nodes involve higher number of hops (Figure 2).

B. The vision from application layer

WSAN are characterized by their strong constraints (energy, memory, throughput), but also by the advantage of having a processing power, however small it may be. The way these objects are used and interact is also a new domain. It's interesting to take advantage of the local processing power to relieve the entire network, because it results in less energy consumption and lower radio traffic. In our study, we adopt the perspective of the programmer, and our approach is based on services. We do not evaluate here the appropriateness of the proposed network organization, but rather the consequences of the two application's design approach. We consider our network as a tree of nodes to represent the standard organization inside a WSAN. Although there may be nuances in each solutions proposed, this simplification has no impact on experiment's validity, because Choreography is more likely to get benefits of improvements provided by various network routing protocols. It is clear that Choreography uses some shorter ways in many cases (in facts, to all nodes that are on the path to the sink, or connected to that path, see Figure 2). All the other nodes are at the same distance in the two organizations. Our study focuses on qualifying and quantifying the consequences of that design's choice in terms of path length, network reliability and possible deductions we can make about network lifetime.

IV. MATHEMATICAL APPROACH OF PATH LENGTH CALCULATION

A. Best and worst cases

Our mathematical approach is mainly based on the calculation of the path length when two nodes try to communicate. Each path in the tree presented in Figure 1 can be considered in two ways, Choreography or Orchestration, changing the vision from each node (Figure 2). This characterization depends on the software design running in the node. A mathematical analysis gives the best and the worst case shown in Figure 3. All nodes are numbered from the sink (0) to the last node (n). Path length is the distance between a node i and a node j. In the first place, let's study the linear model of Figure 3(A), where node 7 is only accessible through node 6, which is accessible from node 5, etc. By adding the length of all possible paths (i.e. for all i and j), and dividing by the number of all possible couples (i , j), we get the average path length µ ( n) for n nodes (we divide by two not to count the path from i to j plus the path from j to i). This formula can be simplified in

µ ( n) = 2 n(n -1) n-1 i=1 n j=i+1 distance i,j
µ ( n) = 2 |P | P distance i,j
with P = set of possible couples of n nodes

In the case of Orchestration, the path goes from node i to the sink (node 0), and then back from node 0 to j. The distance between two nodes i and j is equal to (i + j).

µ o (n) = 2 |P | P (i + j) = n + 1 (1)
Considering Choreography, the distance between two nodes i and j is the shortest path in the tree, and equals (j -i).

µ c (n) = 2 |P | P (j -i) = 1 3 (n + 1) (2)
After simplification, the average path length between two nodes in a linear structure of n nodes is n + 1 in the case of Orchestration. For a Choreography, the average path length is 1/3(n+1). In the best case, a Choreographed architecture reduces the average path length by 3. Figure 3 (B) shows a one hop tree. In that case, the path length between two nodes is always 2 hops. There is no difference between Choreography and Orchestration. This is the worst case, in which Choreography is strictly equal to Orchestration, and brings no improvement. So, the best case is encountered when the tree is very thin, and each node has no sibling. On the contrary, a onehop tree is the worst case, giving a strict equality between Choreography and Orchestration. However, Choreography always offers shorter average path length, except in the worst case scenario where both designs are equivalent.

B. Our probabilistic model for the general case

To study the general case, we have randomly positioned nodes on a square (Figure 4) with the sink (the root) in the Comparison between Choregraphy and Orchestration for a reduced height and very wide tree (depth 3). centre. The radio range is set through a radius parameter. We use Unit Disk Graph (UDG) to simulate the accessibility of each node. Any node at a distance less than this value is considered accessible, otherwise inaccessible. The sink starts to find reachable nodes. These nodes try to reach other nodes, and so on (Figure 4). The resulted tree is analysed when used by Orchestration and by Choreography. The simulation gives the distribution of numbers of paths by length for each design. Figures 5, 6 and7 show our results when comparing these two designs, depending on nodes density, number of nodes, and the three following parameters : Tree Maximum Height (THmax), Internal Nodes Maximum number (INmax) and Nodes Maximum number (Nmax). These parameters are used to build different types of trees. They correspond for example to the parameters Lmax, Rmax and Cmax used in ZigBee [START_REF]Zigbee alliance[END_REF]. All simulations are based on an area containing 100 nodes. For each graph, we vary the three parameters (THmax, INmax and Nmax) to build the structure of the tree. Then, we count the length of each path from each node to all other nodes. This is done according to Orchestrated architecture (via the sink) and then to Choreographed architecture (using the shortest path in the tree). Each analysis is the averaged distribution of a set of 1000 tests. The average of 10 analyses is plotted on Figures 5, 6 and7.

C. Results given by the probabilistic model

Our first result (Figure 5) represents the distribution of paths length for a reduced height and wide tree (a 3 maximum height tree, with 20 children maximum by node, of which 6 are internal nodes maximum). Even with these values that do not favour the Choreography, path length is generally and significantly shorter than in Orchestration. It results in a shorter response time, a reduction of total energy consumption, and a smaller risk of information loss for a non-reliable network such as WSAN. Our second plot (Figure 6) is the path length distribution calculated using usual parameters values than can be found in the literature [START_REF]Zigbee alliance[END_REF] (THmax=3, INmax=6, Nmax=20). The resulting tree is less compacted than the first one, because each level has fewer internal nodes. Our calculations show a significant increase in the number of paths of maximum length in the Orchestration case. The last graph (Figure 7) shows the differences when the network configuration parameters are favourable to Choreography: important tree height, few internal nodes and leaves at each level. Once more, the Choreography is a more efficient organization. Finally, the 10 analyses we conducted allowed us to obtain the average path length standard deviation of our various simulations. In facts, these standard deviation values are so low that we could not even plot them on the graphs. They mostly represent less than 1% of the number of paths, showing that there is very little variation between different estimates.

Finally, Table I gives the compatibility of our results while comparing the two models: the "best and worst cases" vs "general case". Results given by the general case are positioned between the extreme cases. As the tree height increases, the path length gains from the Choreography are becoming more pronounced. They are accentuated by a small number of internal nodes, reaching a reduction by nearly 2 in the case presented on Figure 7.

To sum up with the mathematical analysis, we have shown that for any kind of tree, the Choreography is always a better choice. Compared to an Orchestrated architecture, the gain in terms of path length vary from 1 to 3 times better. The improvement depends on the characteristics of the given network topology and the nodes involved in the communication.

V. TESTBED EXPERIMENTS AND RESULTS

A. TestBed description

To experiment these two architectures with a real implementation, we developed specific software on Contiki [START_REF] Dunkels | Contiki-a lightweight and flexible operating system for tiny networked sensors. local computer networks[END_REF]. Contiki is a Free Software operating system for different sensors hardware, such as TelosB, MicaZ2 or Sensinode3 devices. Contiki comes with Cooja, a network simulator connecting emulating TelosB devices running Contiki. The choice of Cooja instead of other network simulators, such as NS-2 or NS-3, is motivated by the fact that we wanted to see the real effects of an architectural design over a running implementation. Launching our tests over a testbed gives a better view for evaluating the real consequences of a design. Contiki uses an implementation of 6LowPan, and a routing protocol called RPL, in charge of building the routing paths (i.e. the tree). The programmer does not provide any parameter for that tree, and has no control over it (see Figure 8 and9). In addition, the tree may be rebuilt dynamically if needed. The retrieved data from Contiki are: number of sent, received and forwarded IP packets. These data show the entire network activity (including both our application and network inner requirements). Our application enables us to obtain the number of messages that have been successfully received. In this paper, the word packets is used to mean the whole network activity whereas messages refers to application layer.

B. Description of the experiment

Our mathematical analysis attempted to exhaustively enumerate all possible paths in the tree according to the two architectures in order to deduce profiles of path lengths. Theses analyses examines the impact when we vary the tree shape. But on a testbed, the programmer has no control over the building of the tree. In addition, replicating the exhaustive communication from node to node of our mathematical study is not representative of a real M2M application. To test the impact of the application design on any wireless network, we performed the following program: each node chooses only one recipient to simulate the interaction between a sensor and an actuator. Once the actuator chosen, each node sends 30 messages. Our test consists in counting the number of messages actually arrived on the destination (an application layer view), and the number of IP packets that were sent or routed by each router at each level of the tree (a network view). Results are achieved using both architectures: either by sending directly to the recipient (Choreography) or through the sink (Orchestration). The operating mode of this test provides a view of the benefits of the Choreography without having particularly promoted it. Indeed, the random choice of the actuator and the dynamic changes of the tree in 6LoWPAN (see Figure 8 and9) give an overview of the design effects. We developed 3 softwares in Contiky 2.5:

• For each node -A Choreography client/server: While listening to others, this program sends data directly to only one node.

-An Orchestration client/server: Only listening and sending to the sink. Messages contain the id of the real destination's node.

• On the sink -A normal sink: we use code given in Contiki's rpludp example (being the tree root). -An Orchestrated sink: this sink analyses each received message, and relays it to its final destination. It plays two roles: the sink, and the central application. We use 21 nodes plus a sink. According to our preliminary tests, this seems to be enough to have significant results. Nodes are positioned randomly. Experiments are run 100 times for each architecture. The only differences is the way of transmitting messages: through the sink for Orchestration, and using the shortest path for Choreography.

C. Testbed's first result : nodes activity by level

We made numerous tests to eliminate insignificant results. The design of our test is to regularly change the randomized couple sensor-actuator (in order to respect the diversity of realities, there is no evidence that a sensor and an actuator are neighbours in the tree). We eliminated the first results of the list because they were likely to be distorted by the construction of the tree. We kept about thirty results in the middle of the experiment. To identify the major trends, we grouped these measures into three classes corresponding to loading rates of top level routers (i.e. nodes 16, 7 and 3 in Figure 8). Classes are: low, average and high top level activity. On the graph, we also give the overall reliability of the network observed for each class. Our first graph (Figure 10) shows the Orchestration results. Each bar represents the average number of IP packets forwarded by all nodes at a given level. This chart shows activity at each level, and how data traffic is mainly concentrated on high level nodes. In comparison, the deeper in the tree a node is, the less it is requested. From level 3, traffic becomes insignificant. This graph gives another interesting value: the percentage of application messages that reached their destination. The reliability of the application increases when network activity decreases on top level nodes. Because all application messages cross the network towards the sink in the Orchestration design, the whole network reliability is highly correlated with the high load of these nodes. The more top level nodes are loaded, the less reliable the network is. Furthermore, even if the saturation level is not reached, we find that the design of Orchestration implies high activity mainly on these top level elements, consuming quickly their energy. There is little network activity at level 2, and almost not deeper. A Choreography shows a different profile (see Figure 11). With the same 3 classes of average network activity at top level nodes, the forwarding effort is spread over different tree levels. Low level nodes are more used. Figure 11 shows that levels 2, 3 and 4 handle more packets, while traffic on top level decreases. So we have a better activity distribution among the network, and reliability is obviously improved compared to the Orchestration.

D. Testbed's global view: activity and network reliability

Reading raw results (before average) shows significant differences on the percentage of application messages reaching their destination. We focus on any possible link between the first level transmissions and the overall reliability of the network. The way of designing applications has a strong impact on network reliability and activity distribution. Figures 12 and13 plot the percentage of packets that reached their destination compared to the activity of the top level nodes. The network is stressed with important data rates, leading to significant packet losses. In the case of Orchestration, top level nodes activity is strongly linked to network reliability, and their overload leads to a degradation of the entire network accessibility. A global trend can be Figure 11.

In a Choreography, there is non negligible chance that a message reaches its destination without crossing all tree levels.

Figure 12. The more first level is overload, the less reliable is the network. Orchestration saturates top level nodes. deduced from Figure 12. The little variations are due to few tree modification during the experiment (Figures 8 and9). On the contrary, in the Choreography, the correlation does not appear so clearly (Figure 13). Traffic is better distributed within the network. The top level nodes are not involved in all communications. Network reliability reaches higher values, and is less dependent on top level nodes activity. These two graphs show clearly how application's design impacts the network. For the same purpose, choosing to collect information and to take decision outside the network Figure 13. In a Choreography, there is no correlation between reliability and first level activity. The network works better, more depending on destination of the messages rather than their number.

(Orchestration) mainly affects top level nodes, and results in a higher energy consumption that eventually forces the choice of another path (by rebuilding the tree), quickly running all combinations out of energy, causing a total halt of the network. In contrast, obviously designing the same application as a Choreography spreads the network activity most randomly. Various nodes are involved, the network is more reliable and has longer lifetime.

VI. CONCLUSION

By integrating M2M paradigm, the characteristics of WSAN have changed: more different and various type of nodes, heterogeneous flows over the network, variable contents and sending frequencies. All these aspects lead to an organizational transformation from "many-to-one" to "one-to-one', and finally different expectations from users. Exchanges in M2M are more diffuse. Network transmissions frequency is irregular and subject to bursts. In this paper, we first use probabilistic models to show how the design of an application has an impact on the average length of paths. Our results show that the choreography (when it can be implemented) may propose paths of length up to 3 times shorter than an orchestrated design of the same application. Different distributions of the path length are presented. Then, the information collected during our testbed experiment shows measures of the real impact. When application's design is orchestrated, it leads to an overload of top level nodes that is hardly managed by the network. By relieving them of a non negligible part of the traffic, choreography improves network quality and reduces power consumption at top level nodes, whose role in the overall accessibility is crucial. And the choreography never gets worse results than the orchestration in terms of path length. M2M applications over WSAN benefit from the use of choreography, as distributed software optimizes the longevity and reliability of the whole network. In the future, we will continue to explore the pros and cons of such applications design on wireless network based on highly constrained devices with a perspective of M2M oriented approach.

Figure 1 .

 1 Figure 1. A network represented as a tree. For example, path length between node N9 and N13 is: 1) in a Choreography : 3 hops (R2-R7-N13) 2) in an Orchestration : 5 hops (R2-Sink-R2-R7-N13)

Figure 3 .

 3 Figure 3. Extreme cases in Orchestration/Choreography comparison

Figure 4 .

 4 Figure 4. Algorithm used to build the tree. The sink (S) searches its neighbours, which in turn look for their neighbours, and so on.

Figure 5 .

 5 Figure 5.Comparison between Choregraphy and Orchestration for a reduced height and very wide tree (depth 3).

Figure 6 .

 6 Figure 6. Comparison between Choreography and Orchestration for usual values given in ZigBee presentation.

Figure 7 .

 7 Figure 7. A favorable case for Choreography.

Figure 8 .

 8 Figure 8. Tree given by Contiki during Orchestration experiment #50. High level routers are 16, 7 and 13.

Figure 9 .

 9 Figure 9. Orchestration experiment #60: node 16 is no more a router. Node 18 is now in charge of node 22 and 6. 13 becomes more important.

Figure 10 .

 10 Figure 10. In an Orchestration, top level routers are heavily used because all data must travel to the sink, and come back to actuators.

Table I THEORETICAL

 I AVERAGE PATH LENGTHS ACCORDING TO THE

		APPLICATION DESIGN
		A n nodes network	Orch.	Average path length Chor. Ratio C./O.
		Worst Case (THmax=0)	2	2	100%
	.	THmax=3 INmax=3 Nmax=10 THmax=3 INmax=6 Nmax=20	6.96 6.85	5.67 4.90	81 % 72 %
		THmax=3 INmax=10 Nmax=20	6.36	4.53	71 %
		THmax=10 INmax=3 Nmax=5	16.40	8.59	52 %
		Best case (THmax=n)	(n+1)	1/3(n+1)	33 %

See data sheet on MemSic WebSite (http://www.memsic.com/)

From Memsic http://www.memsic.com/

From Sensinode http://www.sensinode.com/

ACKNOWLEDGMENT

The authors would like to thank Cyril Nicaud for his expertise on trees, distributions and for the mathematical formulation of the problem.