Louwanda Lakiss

Cassandre Kouvatas

Jean-Pierre Gilson

Valentin Valtchev

Svetlana Mintova

Christian Fernandez

Robert Bedard

Suheil Abdo

Jeffery Bricker

Bedard

Atomic-Insight into Zeolite Catalyst Forming-an Advanced NMR Study

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Forover 60 years, zeolites have been used in numerous industrial processes such as separation, purification, adsorption and catalysis. [START_REF] Rigutto | Zeolites in Hydrocarbon Processing[END_REF][START_REF] Kulprathipanja | Zeolites in Industrial Separation and Catalysis[END_REF][START_REF] Marcilly | Acido-Basic Catalysis : Application to Refining and Petrochemistry[END_REF][START_REF] Sheldon | Fine Chemicals through Heterogeneous Catalysis[END_REF][START_REF] Ennaert | Potential and Challenges of Zeolite Chemistry in the Catalytic Conversion of Biomass[END_REF][START_REF] Vermeiren | Impact of Zeolites on the Petroleum and Petrochemical Industry[END_REF] Industrial zeolite catalysts generally differ from their laboratory prototypes as they have to meet other requirements such as crushing strength, abrasion resistance, heat transfer, minimal pressure drop and diffusion resistance, deactivation rate and ease of regeneration. These requirements, in turn, determine the shape and form of the catalyst loaded in industrial reactors and add an important binding step in zeolitic catalyst and adsorbent manufacturing. Up to now, a limited number of studies investigated the impact of forming on the performance of zeolite catalysts. [START_REF] Hargreaves | A Survey of the Influence of Binders in Zeolite Catalysis[END_REF][START_REF] Mitchell | From Powder to Technical Body: The Undervalued Science of Catalyst Scale Up[END_REF][START_REF] Gleichmann | Manufacturing of Industrial Zeolite Molecular Sieves[END_REF][START_REF] Bingre | An Overview on Zeolite Shaping Technology and Solutions to Overcome Diffusion Limitations[END_REF][START_REF] Lakiss | Zeolites in a Good Shape: Catalyst Forming by Extrusion Modifies Their Performances[END_REF] During forming, zeolites are dispersed in inorganic matrices such as silica, alumina, clays, and selection of the appropriate forming process (extrusion, pelletizing, spray-drying, oil dropping) depends strongly on the process requirements described above. [START_REF] Mitchell | From Powder to Technical Body: The Undervalued Science of Catalyst Scale Up[END_REF] Silica and alumina remain the most commonly used binders due to their favorable cost to performance ratio and well-known efficacy. It is already recognized that they do not always act as inert diluents, and they might impact positively or negatively the catalytic performance of the shaped bodies, but published literature related to the understanding ofthe atomic-scale interactions that take place at the interface has been sparse.

Recently, Seghers et al. reported a significant improvement of catalyst lifetime upon forming in the Diels Alder reaction to prepare bicyclic norbornene scaffolds from cyclopentadiene and methyl acrylate. [START_REF] Seghers | Enhancing Zeolite Performance by Catalyst Shaping in a Mesoscale Continuous-Flow Diels-Alder Process[END_REF] Gascon et al. spray-dried ZSM-5/clay catalysts and showed that the nature of the clay modifies their acidity and affects the catalytic performances in the methanol-to-olefins (MTO) reaction, in particular, the alkene and arene selectivity. [START_REF] Shoinkhorova | Shaping of ZSM-5-Based Catalysts via Spray Drying: Effect on Methanol-to-Olefins Performance[END_REF] Michels et al. also investigated the impact of binding on hierarchical ZSM-5 catalysts onthe MTO reaction; in particular, they noticed that binding with attapulgite provided the highest catalyst stability and light olefin selectivity, but no correlation was observed between improved performance and acidity. [START_REF] Michels | Effects of Binders on the Performance of Shaped Hierarchical MFI Zeolites in Methanol-to-Hydrocarbons[END_REF] Numerous techniques such as Raman and infrared micro-spectroscopies, magnetic resonance imaging, Xray absorption, and diffraction microtomography (micro-CT) have been recently used to visualize shaped zeolite catalysts at the macro-and nano-scales with spatio temporal resolution. [START_REF] Espinosa-Alonso | Profiling Physicochemical Changes within Catalyst Bodies during Preparation: New Insights from Invasive and Noninvasive Microspectroscopic Studies[END_REF][START_REF] Bergwerff | Spatially Resolved Raman and UV-Visible-NIR Spectroscopy on the Preparation of Supported Catalyst Bodies: Controlling the Formation of H 2PMo11CoO405-inside A1 2O3 Pellets during Impregnation[END_REF][START_REF] Jacques | Dynamic X-Ray Diffraction Computed Tomography Reveals Real-Time Insight into Catalyst Active Phase Evolution[END_REF][START_REF] O'brien | Active Phase Evolution in Single Ni/Al 2O 3 Methanation Catalyst Bo ies Stu ie in Real Time Using Combine μ-XRD-CT an μ-Absorption-CT[END_REF] For instance, fluorescent nanoprobes were used to detect and identify the active phase (zeolite Y) in fluid catalytic cracking catalysts using confocal laser scanning microscopy (CLSM). [START_REF] Whiting | Visualizing Pore Architecture and Molecular Transport Boundaries in Catalyst Bodies with Fluorescent Nanoprobes[END_REF] Michels et al. followed an integrated approach to visualize hierarchical zeolite technical bodies by combining optical, X-ray, electron microscopy, and tomographic techniques. [START_REF] Mitchell | Visualization of Hierarchically Structured Zeolite Bodies from Macro to Nano Length Scales[END_REF] Although, these approaches are very useful to visualize the textural features and pores architecture of shaped catalysts, they do not provide atomic-level details of thezeolite binder interfacesuponforming.

Previously, we investigated the chemical interactions between a zeolite and its alumina binder by IR spectroscopy of adsorbed basic probes such as pyridine and CO. [START_REF] Lakiss | Zeolites in a Good Shape: Catalyst Forming by Extrusion Modifies Their Performances[END_REF] We demonstrated the formation of new acid sites after extrusion, reminiscent of amorphous silica-aluminas. The shaped extrudates also showed high catalytic performance in the dealkylation of 1,3,5-Triisopropylbenzene, a bulky molecule that diffuses only with great difficulty through the microporosity. Such a result indicates that the newly created catalytic sites are not located in the zeolite micropores but most probably near their external surface. We now report the use of advanced NMR techniques to selectively investigate the zeolite-binder interface of extrudates at the atomic level to probe the chemical nature of this interface, as well as the internuclear interactions that occur.

Classical Solid-State Magic Angle Spinning NMR (SS MAS NMR) is already a proven and powerful technique to provide such chemical and structural atomic level information. For instance, it discriminates between different crystallographic framework positions in zeolite frameworksand detects the presence of extraframework cations. Unfortunately, NMR is a bulk technique probing all atoms, and therefore, a dedicated analysis of the external surface of zeolites is impossible as the related signals are overwhelmed by those intheir internal surface. The recently developed Dynamic Nuclear Polarization (DNP) enhancement overcomes such a limitation and appears a potentially ideal technique to investigate chemistry at surfaces and interfaces.

DNP-enhanced MAS NMR is increasinglyused to enhance the sensitivity in solid-state MAS NMR. The studied solid is first impregnated with a free radical solution acting as a paramagnetic polarization agent (PA) and then cooled to a cryogenic temperature. The polarization of the unpaired electron of these radicals is then transferred directly by microwave irradiation to nuclei surrounding the PA, the so-called direct DNPenhanced MAS NMR. Such transfer can also be mediated by 1 H; in this case, the polarization of unpaired electrons is first transferred (from the solvent or the solid surface) to 1 H nuclei near the PA, then to other nuclei by classical Cross Polarization (CP) techniques. This so-called indirect DNP relies on transferring the 1 H polarization across the sample by spin diffusion. Lesage et al. used indirect DNP CP [START_REF] Shoinkhorova | Shaping of ZSM-5-Based Catalysts via Spray Drying: Effect on Methanol-to-Olefins Performance[END_REF] C{ 1 H} to detectorganic species grafted on the surface of nanoporous silica. [START_REF] Lesage | Surface Enhanced NMR Spectroscopy by Dynamic Nuclear Polarization[END_REF] Direct and indirect DNP were used in synthetic clays to distinguish between Si atoms close to the radicals from those further away from the surface by [START_REF] Rigutto | Zeolites in Hydrocarbon Processing[END_REF] H spin diffusion and CP. [START_REF] Lafon | Indirect and Direct29Si Dynamic Nuclear Polarization of Dispersed Nanoparticles[END_REF] Lee et al. demonstrated the selective enhancement of the first surface layer of γ-alumina catalysts by indirect DNP [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al{ 1 H} CP NMR. [START_REF] Lee | Primostrato Solid-State NMR Enhanced by Dynamic Nuclear Polarization: Pentacoor inate Al3+ Ions Are Only Locate at the Surface of Hy rate γ-Alumina[END_REF] Mais et al. observed surface pentahedral aluminum in gammaalumina by indirect DNP. [START_REF] Mais | Dynamic Nuclear Polarisation Enhanced Solid-State Nuclear Magnetic Resonance Stu ies of Surface Mo ification of ?-Alumina[END_REF] DNP NMR can also probe the porosity and nanostructure of materials based on the reduction of relaxation time of species near paramagnetic centers and spin diffusion. Schagnitweit et al. explored the combination of these effects to investigate the domain size of a component in an organic multicomponent mixture. [START_REF] Schlagnitweit | Nanostructure of Materials Determined by Relayed Paramagnetic Relaxation Enhancement[END_REF] Pinon et al. showed that DNP can probe the porosity of mesoporous silica materials via selective doping with paramagnetic species. [START_REF] Pinon | Measuring Nano-to Microstructures from Relayed Dynamic Nuclear Polarization NMR[END_REF] The demonstrated high sensitivity of DNP and its ability to probe surfaces selectively makes it a tool of choice to investigate the zeolite/alumina interface, accessible to bulky PA molecules, of shaped bodies in general and catalysts in particular.

Experimental section

Materials and Preparation

A Y zeolite with a Si/Al ratio of 2.3 (LZY-64 supplied by UOP) is used throughout this work. Zeolite/alumina extrudates (dry mass ratio of 30 wt% zeolite and 70 wt% binder) are prepared as described earlier: [START_REF] Lakiss | Zeolites in a Good Shape: Catalyst Forming by Extrusion Modifies Their Performances[END_REF] the zeolite powder, Methocel (F4M, Dow Chemicals), and alkali-free pseudo-boehmite (Catapal B) are mixed and homogenized. Deionized water is then added dropwise to the solid mixture to obtain dough ready for extrusion. The dough is then transferred to a hand extruder (Makin's USA Professional Ultimate Clay Gun Extruder, 1.6 mm diameter die) for forming. The green extrudates are dried at 323 K for 2 hours in a convection oven and thereafter transferred to a muffle oven forcalcination as follows: i) 363 K for 12 hours ii) 823 K for 4 hours with a heating rate of 5 K /min. The calcined extrudates are then gently crushed, sieved, and the 200-500 µm fraction retained. For comparative purposes, the pristine zeolite and pseudobohemiteare heated under identical conditions. The physico-chemical properties of the parent zeolite, alumina binder, and alumina/zeolite extrudates were already reported elsewhere. For indirect DNP, ramped CPMAS is used to transfer polarization from 1 H to [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al nuclei, under SPINAL64 1 H decoupling during the acquisition. [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] A low-power [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al radiofrequency field isused to ensure an efficient spinlocking of the quadrupolar nucleus, and thus the CP processes with a contact time of 0.7 ms. Recycle delays in the indirect [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al experiments are longer than 1.3 times TDNP measured in CP saturation-recovery experiments.

The DNP build-up times (TDNP) under microwave irradiation are measured ina saturation-recovery experiment, with a saturation pulse train before the variable polarization time (delay), followed by the ramped [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al{ 1 H}CP. Prior to all NMR experiments, the samples are partially dehydrated in a conventional oven at 473 K overnight.

Discussion

General Characterization

As described elsewhere [START_REF] Lakiss | Zeolites in a Good Shape: Catalyst Forming by Extrusion Modifies Their Performances[END_REF] zeolite Y/-Al2O3 extrudates were already characterized by multiple conventional techniques. While the crystallinity of the calcined zeolite Y and its derived extrudates determined by XRD decreased to about 70 % (Figure S1 in the Supporting information), the Brønsted acid sites (BAS) concentration in the extrudates wasslightly higher than in the parent zeolite. Furthermore, CO adsorption monitored by IR spectroscopy detected the presence of a new type of acid sites in addition to those of the pristine zeolite and alumina. The catalytic performance of the extrudates was evaluated in the dealkylation of 1,3,5 Tri-isopropyl benzene (TiPBz), a bulky reactant (kinetic diameter = 0.95 nm), reaching only the external and mesoporous zeolite surfaces (Figure S2 in the Supporting information). The extrudates were significantly more active than physical mixtures of identical amounts of zeolite and -Al2O3. The conclusion is, of course, that the additional acidity created during extrusion is located at the interface between the zeolite and its binder and not in the micropores of the zeolite.

In this study, the aim of the DNP enhanced MAS NMR experiments is to validate the previous conclusions and shed light on atomic level features of the zeolite-binder interface interactions, as the selected TEKPol radicals (kinetic diameter = 2 nm) used to generate the DNP signals do not penetrate the zeolite micropores (0.7 nm restricted openings of 1.13 nm supercages).

Inventory of aluminum sites

The aluminum sites located in the zeolite micropores and near PA's at the interface with the binder can be discriminated by comparing [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al MAS NMR with indirect { 1 H}- [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al DNP MAS NMR. Figure 1 shows the [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al NMR spectra of the extrudates after partial dehydration (Figure 1a), the pure zeolite powder (Figure 1b) and the γ-alumina binder (Figure 1c) treated under identical conditions. Three types of peak are present on the extrudates, namely: i) 0 ppm: octahedral Al belonging either to the alumina binder or extra-framework zeolite aluminum; they are also present in the spectra of the pure zeolite powder and alumina treated under identical conditions ii) 75 and 65 ppm: the first assigned to tetrahedral aluminum in γ-alumina and the second to tetrahedral aluminum in the zeolite framework [START_REF] Busca | Chapter Three -Structural, Surface, and Catalytic Properties of Aluminas[END_REF] iii) 38 ppm: this weak and broad signal corresponds to pentahedral or distorted tetrahedral aluminum species. A linear combination analysis of the three spectra is presented in Figure S3. Data of this analysis are reported in Table S1 and Table S2. The integrated intensities of the extrudate spectrum indicate a proportion of 74.4 % alumina and 25.6 % zeolite, which is quite close to the mass proportion in the mixture. [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al DNP-CP MAS NMR spectra with microwave ON (red) and OFF (black) of (a) pure γ-alumina, (b) pure Y zeolite powder and (c) zeolite Y/alumina extrudates. In 2a, the µ-wave off spectrum is recorded with less scans than the µ-wave on spectrum (32 vs 64), but the intensity adjusted (x2). An additional figure with the same amount of scan ( 16) is presented in SI (Figure S4). In Figure 2b , the µ-wave off spectrum is recorded with 4 times less scans than µ-wave on spectrum (64 versus 256), but the intensity is adjusted (x 4).

All spectra, with or without microwave irradiation, are similar, but their intensity increases under microwave irradiation, indicating a close proximity with the PA. The PA is too bulky to enter the zeolite microporosity, but the binder mesoporosity is accessible. The signal enhancement observed under microwave irradiation at 65 ppm on the pure zeolite (Figure 2b) should therefore correspond only to tetrahedrally coordinated aluminum located on its external surface. Likewise, as no peak appears around 0 ppm under microwave irradiation, all the octahedrally coordinated aluminum (EFAL) detected without microwave irradiation should be located in the zeolite microporosity. On the extrudate spectrum, under microwave irradiation (Figure 2c), the broad signal between 0-10 ppm belongs to octahedrally coordinated Al from the binder while the signals in the tetrahedral region (50-80 ppm) are attributed to Al IV from the binder (77 ppm) and the external surface of the zeolite (64 ppm), i.e., close to the zeolite/binder interface. Further information, such as the proximity of aluminum species, can be provided by measuring the DNP build-up time, TDNP.

Spatial insights on aluminum sites proximity

The proximity of the above aluminum species can providecomplementary information on the binder/zeolite interface by measuring their respective TDNPin an indirectDNP [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al{ 1 H} saturation recovery CP experiment.

x 4

x 2

The saturation recovery part of this experiment focuses on analyzingthe T1relaxation times asspecies close to the PA relax faster,i.e.,have lower T1,leading to a so-called paramagnetic relaxation enhancement. Thenet result for zeolites is thatthe TDNPof their [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al atomslocated on or near theirexternal surface is shorter than those in the micropores.

The TDNPtime constant depends on the DNP enhancement, quenching of the signal (loss due to the fast relaxation of species close to radicals), and spin diffusion,expressed in thefollowing stretched exponential function: [START_REF] Narayanan | Characterizing Nonexponential Spin-Lattice Relaxation in Solid-State NMR by Fitting to the Stretched Exponential[END_REF][START_REF] Peyron | The Modified Stretched-Exponential Model for Characterization of NMR Relaxation in Porous Media[END_REF][START_REF] Petrov | Parameterization of NMR Relaxation Curves in Terms of Logarithmic Moments of the Relaxation Time Distribution[END_REF] where I0 is the maximal signal intensity andβ the stretching coefficient.This function is characteristic of a distribution of relaxation times TDNP. The smaller β is, the wider the distribution.

The intensity for every aluminum peak is extracted from each slice of the indirect DNP [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al{ 1 H} saturation recovery CP experiment.The resulting build-up curves from the signal intensities are then fitted to extract the TDNPof each aluminum(Table 1).For the pure zeolite, the only TDNP isfor tetrahedral aluminum (2.0 s) as no octahedral aluminum is present on its external surface,vide supra. On thepure alumina, the TDNPof tetrahedral and octahedral aluminumare4.9 s and 4.3 s, respectively. On the zeolite Y/alumina extrudate,TDNPis 4.8 s and 5.5 s for tetrahedral and octahedral aluminum in the alumina binder and 6.9 s for the zeolitic tetrahedral aluminum. Thetetrahedral aluminum TDNPof the extruded zeolite is therefore about three times longer than in the pure zeolite powder,while thetetrahedral and octahedral TDNPof alumina in extrudates are not significantly affected.

This highlights a spatial organisation in the extrudates between zeolite (further from the surface, as a core) and -alumina (closer to the surface), in addition to the physical spatial proximity between the two phases. The emerging picture is that on the external surface of pure zeolite Y, only tetrahedral aluminum and Si are present, and in the extrudates, they interact with tetrahedral and octahedral aluminum from the alumina binder.The key question is the exact nature of the interaction at the zeolite/alumina interphase. Namely, which aluminum from the alumina (tetrahedral or octahedral) interacts with the zeolite external surface?A two-dimensional [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al-{ [START_REF] Narayanan | Characterizing Nonexponential Spin-Lattice Relaxation in Solid-State NMR by Fitting to the Stretched Exponential[END_REF] Si} J-HMQCMAS NMR experiment brings further insight. Nature of the zeolite-binder interface [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al-{ 29 Si} J-HMQC MAS NMR reveals scalar couplings (i.e., chemical bounds) between [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al and [START_REF] Narayanan | Characterizing Nonexponential Spin-Lattice Relaxation in Solid-State NMR by Fitting to the Stretched Exponential[END_REF] Si nuclei in a 2D correlation spectrum and can therefore bring important information to clarify the nature of the zeolite/binder interface provided enough sensitivity is achieved. Here, even at microwave OFF, the presence of radicals (decreasing the [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al relaxation times) associated with a low temperature (~ 100 K) and a high permanent field (18.8 T) provides enough sensitivity and is less time consumming, that would not have been possible at RT on a lower magnetic field spectrometer for reasonable experiment time. Figure 3 shows a correlation map between a tetrahedral zeolitic aluminum (65 ppm, viz. Figure 1a and Figure 1b) and a Q 4 silicon (-101 ppm), i.e. tetrahedral silicon bound to n aluminum atoms in zeolite Y. [START_REF] Narayanan | Characterizing Nonexponential Spin-Lattice Relaxation in Solid-State NMR by Fitting to the Stretched Exponential[END_REF] Si MAS NMR spectra are presented in SI (Figure S5a and Figure S5b). Both spectra display resonances in the region of Q4(nAl) species (i.e. tetraedral silicon, connected to n aluminum atoms). Another correlation appears between a tetrahedral aluminum from the alumina binder (75 ppm) and again a Q 4 silicon ( -100 ppm) in zeolite Y. The latter is due to an interaction between terminal zeolitic silanols with tetrahedral aluminum from the binder. This implies that tetrahedral aluminum from the binder are chemically bound to zeolitic silicon atoms. This confirm our previous hypothesis of a chemical reaction between the alumina binder and the zeolite, assumed to take place during the calcination when the pseudobohemite precursor is transformed in -Al2O3. [START_REF] Lakiss | Zeolites in a Good Shape: Catalyst Forming by Extrusion Modifies Their Performances[END_REF] This also agrees with the spatial organization proposed by the TDNP derived from the DNP 27 Al{ 1 H} saturation recovery CP experiments and the presence of an ASA (amorphous silica-alumina) phase at the zeolite binder interface. 11

Conclusion

We have demonstrated that zeolite catalyst forming is more than a physical mixture between a zeolite and a binder resulting in a well-dispersed zeolite active phase in, for instance, alumina. Indirect Al{ 1 H} DNP MAS NMR shows that the tetrahedral and octahedral aluminum in the -Al2O3 binder, all in close proximity with the PA agent, are polarized directly while only the zeolitic tetrahedral atoms located on the external surface of the crystals are polarized by a spin diffusion process, in line with their close proximity to the alumina. Moreover, [START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al-{ 29 Si} J-HMQC NMR explicitly indicates that tetrahedral aluminum from the binder reacts with zeolitic Si located on its external surface.

Tools now exist to monitor and control atomic level features during the forming process of catalysts. They clearly indicate that in this ubiquitous manufacturing step, controlled catalyst fine-tuning, as active site creation, can take place to optimize their performances further.

Such a study, on technical bodies formed by extrusion, can also be applied to other forming processes (spray-drying, oil-dropping, pelletizing…) with different binders (SiO2, AlPO4, clays…) and extended to noncatalytic processes such as adsorption on porous solids.

ASSOCIATED CONTENT

Supporting Information. XRD powder diffraction patterns of zeolite Y (normalized to 30 %) and extrudates, Y/Ext and the. Catalytic activity of pure zeolite Y, physical mixture of zeolite Y and -alumina (30 % wt zeolite Y and 70 % wt-alumina) and extrudates, Y/Ext. is available free of charge via the Internet at http://pubs.acs.org. *jean-pierre.gilson@ensicaen.fr

For Table of Contents Only

Figure 1 .Figure 2 .

 12 Figure1.[START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al MAS NMR spectra of (a) zeolite Y/alumina extrudates, (b) pure zeolite powder, (c) pure alumina. Spinning side bands are labelled with asterisks. The typical range observed for tetrahedral, pentahedral and octahedral aluminum sites is reminded on the top.

Figure 3 .

 3 Figure 3. 27 Al-{ 29 Si} J-HMQCspectra on dehydrated extrudates.

11 NMR Characterization DNP

  experiments are carried outon an 800MHz Bruker AvanceIII spectrometer operating at a Larmor Frequency of 800.13MHz ( 1 H), 208.49 MHz ( 27 Al) and 158.96 MHz ( 29 Si) equipped with a 9.7T gyrotron magnet to generate microwaves, operating at 263 MHz.TEKPol, the radical source diluted in a 1,1,2,2tetrachloroethane (TCE), is impregnated by incipient wetness for DNP experiments. The TEKPol concentration is 40-50 mmol/g of zeolite/binder composite. All samples are packed into 3.2 mm zirconium rotors, frozen ( ) inside a low-temperature 3.2 mm CPMAS probe head, and spun at 12 kHz under a flow of nitrogen.

Table 1 .

 1 Fitted build-up time (TDNP) and corresponding stretching coefficient (β) from indirect DNP[START_REF] Fung | An Improved Broadband Decoupling Sequence for Liquid Crystals and Solids[END_REF] Al NMR spectra, for each aluminum in pure Y zeolite,-Al2O3zeolite and Y/-Al2O3 extrudates. The calcination procedure is similar for all samples.

	TDNP /s	β

ACKNOWLEDGMENT

Honeywell UOP for funding and permission to publish. Financial support from the IR-RMN-THC Fr3050 CNRS grant is also gratefully acknowledged. We thank Dr. David Gajan for his technical support on the 800 MHz spectrometer and for very helpful discussions.

AUTHOR INFORMATION Corresponding Author

Author Contributions

The manuscript was written through contributions of all authors. All authors have given approval to the final version of the manuscript **These authors contributed equally.


Yann Busnel

Marin Bertier

Anne-Marie Kermarrec

On the Impact of the Mobility on Convergence Speed of Population Protocols

Keywords: Population protocols, Mobility model, Markov chain, Theoretical analysis, Stochastic process, Lower bound Protocoles de population, Modèle de mobilité, Chaîne de Markov, Analyse théorique, Processus stochastique, Borne inférieure

Population protocols provide theoretical foundations for mobile tiny device networks in which global behavior emerges from a set of simple interactions between anonymous agents. The works in this area mostly focus on studying the computational power of the model. Results hold as long as a fair scheduler, which governs the interactions between nodes, ensuring that all reachable system states may eventually happen.

This paper studies for the first time the impact of the agents' mobility model on the convergence speed of population protocols. We propose an augmented population protocol model where each edge of the interaction graph is weighted, representing the probability of two agents to interact. This models the behaviour of the scheduler with respect to various mobility models. We empirically show that mobility models do have a significant impact on the convergence speed of the protocols. In fact, we observe that the uniform distribution always provides the best convergence time. Such a model is representative of the well-known Random Way Point model used to evaluate most of mobile ad-hoc network protocols.

Finally, we formally prove that a uniform distribution of weights provides the lowest bound of average convergence speed for any population protocol. Therefore, this analysis reveals that the Random Way Point model, following this distribution, provides the best case scenari. This may question its relevance as the most representative model.

Introduction

Sensor networks are composed of tiny computation units able to communicate and collect data from their environment. This led to a whole class of applications, where sensors are embedded on human or animals, aiming at observing their behaviour or computing global properties. Such settings impose intermittent and arbitrary communications between sensors, which are specifically studied in the context of Delay Tolerant Network (DTN) [START_REF] Burleigh | Delay-tolerant networking: an approach to interplanetary internet[END_REF] and Population Protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]. Delay Tolerant Network may be seen as an evolution of Mobile Ad-hoc NETwork (MANET) [START_REF] Sesay | A survey on mobile ad hoc wireless network[END_REF]. In the DTN area, the challenge consists in designing distributed applications able to cope with the uncertainty on the connectivity and the dynamicity induced by the mobility. Population Protocols propose a formalism to study the convergence of distributed algorithms based on a succession of interactions between nodes. These two approaches are complementary. In this paper, we leverage these complementarities and propose an enriched population protocol model to deal with mobility patterns.

MANET and DTN Consider a network composed of mobile nodes equipped with wireless networking capabilities and able to communicate with each other only when they are within transmission range. A common DTN scenario considers a network suffering from frequent connectivity disruptions, making the topology only intermittently and partially connected. Most DTN algorithms propose probabilistic solutions, where the probabilities are strongly dependant on the mobility model. Many works in this area focus on establishing the correct mobility model to represent human's movement behaviours in order to determine how to optimize distributed algorithms.

Population protocols Population protocols, introduced in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], model the interactions between mobile agents with very limited power. Population protocols provide common theoretical foundations for distributed systems in which global behaviour emerges from a set of simple interaction between nodes. Population protocols consist of finite sets of states, inputs, outputs and a transition function. The set of possible node interactions is represented by a graph of interactions. An interaction represents the fact that two agents are sufficiently close for a sufficiently long time and interact by exchanging their local information.

The power of population protocols lies in the simplicity of the model. No specific assumption is made on the agents' synchrony, the system infrastructure or the order of the interactions. A scheduler which only assumption is to be fair guides the way the interaction actually takes place. A fair scheduler simply ensures that every possible evolution of the system may eventually happen.

On the impact of mobility Most of the works in population protocol focus on the computational power of such protocols [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF][START_REF] Angluin | Stably computable predicates are semilinear[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF][START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Delporte-Gallet | When birds die: Making population protocols fault-tolerant[END_REF]. No specific assumption is usually made on the model of interactions between agents. When a specific interaction model is considered, it is usually uniform [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF]. Yet, in reality, the mobility pattern of a set of mobile entities is not uniform. Although this has no impact on the actual power of the model and the asymptotic convergence, it is very likely that the convergence speed of such a system is impacted by the mobility patterns of agents. In mobile networks, it has been shown that mobility models strongly impact the outcome of a protocol [START_REF] Fribourg | Coupling and selfstabilization[END_REF]. As a consequence, characterizing realistic mobility models [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF] is an active area.

Contributions

In this paper, we study the impact of the agents' mobility model on the convergence speed of population protocols. To this end, we introduce MAPP (Mobility Applied to Population Protocol), a population protocol model augmented to take into account the probability distribution of agent interactions. To this end, to each edge of the interaction graph is assigned a weight reflecting the interaction frequency between the two agents linked by that edge.

We first empirically study the impact of various mobility models on the convergence speed of the most classical population protocols namely the or and sum modulo x operations. We integrate the mobility aspect of such networks along two lines: (i) the distribution of interactions (this is modelled by the weight on the interaction graph) and (ii) the distribution of pairwise inter-contact time 1 for a given distribution of interactions.

In the empirical study, we consider a uniform interaction distribution as well as a set of non-uniform mobility patterns identified by the mobile network community [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF]. We observe a significant impact of the mobility patterns on the speed of convergence. More specifically, a uniform distribution turns out to consistently achieve the best average convergence time.

We then formally prove that this uniform distribution of weights provides the lowest bound of the average number of steps to reach convergence in population protocols.

Finally, we also demonstrate that the Random Way Point mobility model, which is the most extensively used to evaluate mobile networks, infers a uniform distribution in MAPP. Interestingly enough, not only the Random Way Point model it recognized as non-realistic, but also we show that it actually provides the best-case scenario. This may lead to question the relevance of using such a model as a representative mobility model.

Roadmap

The rest of the paper is organized as follow. Section 2 provides the computation models of population protocols as well as MAPP, our extension of this model. In Section 3 and 4, we present respectively the empirical context and study of the impact of mobility on the convergence speed of a few traditional protocols (or and sum modulo 4). Section 5 presents the proof that the uniform distribution leads to the lowest bound in term of average number of step required to convergence in population protocols. Finally, in Section 6, we prove that the Random Way Point model can be modelled by a uniform distribution. We conclude and list some open issues in Section 7.

Computation models 2.1 Population protocols

The seminal population protocol model [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Aspnes | An introduction to population protocols[END_REF], considers a collection of agents with an associated input value. Pairwise interaction of agents is governed by a fair scheduler (cf. Section 2.3). An agent in this model is represented as a finite state machine, which state is updated upon interaction only. Updates are defined by a transition function δ. Agents compute an output value related to their current state. This value eventually converges to the expected correct output value.

More formally, a population protocol is composed of:

• an interaction graph Λ(Υ, Θ) where Υ represents a set of n ≥ 2 anonymous agents and Θ the set of all possible pairwise interactions between these agents. In the basic model,

Θ = {(υ, υ ) ∈ Υ 2 |υ = υ } (Λ is complete);
• a finite input alphabet Σ;

• a finite output alphabet Y ;

• a finite set of possible agent's states Q;

• an input function ι : Σ → Q mapping inputs to states;

• an output function ω : Q → Y mapping states to outputs;

• a transition relation δ :

Q × Q → Q × Q on pair of states.
In the following, we call (p, q) → (p , q ) a transition if [(p, q) → (p , q )] ∈ δ. A transition can occur between two agents' states only if these two agents have an interaction. The protocol is deterministic if δ is a function (i.e. at most one possible transition for each pair in Q 2 ). A configuration of the system corresponds to a mapping vector of all agents' states. As agents are anonymous, two agents with the same state are indistinguishable. Then, each configuration can be viewed as an unordered multiset of states. We denote C → C the fact that C can be obtained from C in one step (i.e. with only one transition for one existing interaction θ ∈ Θ). An execution of the protocol is a finite or infinite sequence of population configurations

C 0 , C 1 , C 2 , . . . such that ∀i, C i → C i+1 .
In brief, a population protocol stably computes a function f : Σ + → Y if ∀n ∈ N, ∀σ ∈ Σ n , every fair execution, with n agents initialized with the elements of σ, eventually stabilize to output f (σ) (i.e. output value of every agent eventually stabilizes to f (σ)).

Population protocols are able to compute any predicate of the Presburger arithmetic, namely the semilinear predicates [START_REF] Angluin | Stably computable predicates are semilinear[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF], and only these. In brief, a set

L ⊆ N k is linear if ∃v 0 , v 1 , . . . , v m ∈ N k such that L = {v 0 + κ 1 v 1 + . . . + κ m v m |κ 1 , . . . , κ m ∈ N}.
As a semilinear set is a union of linear sets, a semilinear predicate is defined as the one true precisely on a semilinear set. The MAPP extension affects only the interaction scheduler without jeopardizing its fairness, nor the computable predicates.

Illustrating protocols

In the following, we illustrate our results using some classical population protocols. Then, we introduce in this paragraph three of these.

Or operation This protocol is equivalent to an epidemic dissemination or a flooding operation. This simple protocol consists, for any agent with input 0, to output 1 as soon as it encounters an agent with input 1. More formally, Σ = Y = Q = {0, 1}. ι and ω correspond to the identity function and δ is the singleton {(0, 1) → (1, 1)}. All other transitions are defined to leave the pair of states unchanged.

Majority This operation consists in computing the majority of the set of agents. Consider two kinds of agents in the system (0 and 1, male and female for example) depicted by ⊥ 0 and ⊥ 1 . The majority output 1 (i.e. each agent ouputs 1 eventually) if the initial configuration contains a strict majority of ⊥ 1 and 0 otherwise. As counting anonymous objects in a distributed way is impossible, the idea of the protocol is to consider agent pairwise and observe if any agent remains "isolated". More formally, Σ = {⊥ 0 , ⊥ 1 } in which the first type of entity is represented by ⊥ 0 and the second one by ⊥ 1 . Y = {0, 1} and Q = {⊥ 0 , ⊥ 1 , 0, 1}. ι corresponds to the identity function and ω maps ⊥ 0 and 0 to 0 and ⊥ 1 and 1 to 1. δ contains the four following transitions: (⊥ 0 , ⊥ 1 ) → (0, 0), (⊥ 0 , 1) → (⊥ 0 , 0), (⊥ 1 , 0) → (⊥ 1 , 1), (0, 1) → (0, 0). All other transitions are defined to leave the pair of states unchanged.

Sum modulo 4 This protocol computes in a distributed manner the sum modulo 4 of all inputs picked in Σ = {0, 1, 2, 3} (as well Y is the same set than Σ). All the values can be collected by a single agent, which eventually stabilizes to the sum, modulo 4. In order to remove the yet computed input values, each agent's value becomes ⊥ labelled with the value of the eventually unique agent with a non-⊥ value. Then, we have Q = {0, 1, 2, 3, ⊥ 0 , ⊥ 1 , ⊥ 2 , ⊥ 3 }. Let ι corresponds to the identity function and

ω(v) = ω(⊥ v ) = v.
The only transition rules of δ, which do not leave the pair of states unchanged, are the following: ∀v, w ∈ {0, 1, 2, 3}, (v, w) → (v + w, ⊥ v+w ) and (v, ⊥ w ) → (v, ⊥ v ) in which the addition is made modulo 4.

Mobility Applied to Population Protocols

In order to formally study the impact of the mobility model on the convergence speed of protocols, we proposed an extension of this model.

Modeling the scheduler

In the population protocol model, a fair scheduler determines the order of interactions. This fairness assumption ensures that an attainable state can be effectively reached. More formally, considering a given configuration C, for all configuration C obtained from C with a single interaction of two agents (i.e. C → C ), if C appears infinitely often during the execution, then the configuration C must also appears infinitely often.

The main objective of our extension is to model the scheduler, to define its heuristics, while ensuring this fairness condition, and then capture mobility patterns. In Mobility Applied to Population Protocol (MAPP), a weight is assigned to all edges of the interaction graph, reflecting the probability for an interaction to happen at the next step of the execution between the agents connected by this edge. In the following, we extend the interaction graph definition as Λ(Υ, Θ) such that

∀θ ∈ Θ, ∃υ, υ ∈ Υ, υ = υ ∧ θ = υ p υ,υ ---→ υ .
We denote this probability p υ,υ or p θ . Obviously, we have θ∈Θ p θ ≤ 1. Without loss of generality, we can assume that θ∈Θ p θ = 1.

From a practical point of view, MAPP allows to model the choices of the scheduler during the execution of a given protocol. In fact, given a population in a configuration C, the scheduler chooses the protagonists of the following interaction according to the meeting probability of those agents.

On the relevance of this extension We must first check that our model verifies the fairness condition, imposed on the scheduler.

Lemma 1 For all schedulers following the probability distribution of a given MAPP, this scheduler also respects the fairness assumption.

INRIA

Proof. ∀θ ∈ Θ, if p θ > 0 then the probability that this interaction occurs instead any other is not null. Then, given two specific configurations C and C such that C → C with the interaction θ, the probability that this transition will be chosen by the scheduler is not null either. So, if C appears infinitely in the execution then C will also appears infinitely in the execution.

Conversely, if p θ = 0, without loss of generality, we can consider a restricted interaction graph such that θ / ∈ Θ. In this case, it cannot exist C → C with the interaction θ. Then, the scheduler does not break the fairness assumption.

Integration with related works

One of the main advantages of our extension consist in its easy integration among all variant models starting from the population protocols. In fact, our proposition are not decreasing the powerfulness of the initial models.

For instance, the computational power of former model are unchanged as for population protocol, it remains as semilinear predicates [START_REF] Angluin | Stably computable predicates are semilinear[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF]). Thus, any result according to the self-organization of these protocols [START_REF] Angluin | Self-stabilizing population protocols[END_REF] and to take into account failures [START_REF] Delporte-Gallet | When birds die: Making population protocols fault-tolerant[END_REF] remain valid.

Then, using MAPP, we can model most of the model which extend the population protocol one. Consequently, considering a restricted interaction graph [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] can be viewed as a MAPP with part of edges of interaction graph labeled by 0. As well, all result proposed in the context of random interactions [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Angluin | Fast computation by population protocols with a leader[END_REF] are valid for all MAPP set using an uniform distribution of probabilities of the graph's edges. Finally, different models introduced in [START_REF] Angluin | The computational power of population protocols[END_REF] concerning the model of one-way communications remain valid in a MAPP using an oriented graph.

Theoretical analysis of convergence

Many papers [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Angluin | Fast computation by population protocols with a leader[END_REF][START_REF] Angluin | Stably computable predicates are semilinear[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF][START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Delporte-Gallet | When birds die: Making population protocols fault-tolerant[END_REF][START_REF] Guerraoui | Even small birds are unique: Population protocols with identifiers[END_REF] have investigated the power of population protocols and its extensions. Yet, very few are concerned with the convergence speed (in population porotocol context, it corresponds to the average number of steps or the time needed to reach the stabilized configuration). MAPP provides a simple model to analyze theoretically the behaviour of the evolution of the system over time.

In this section, we present the method used to proceed these analyses. First, we introduce the necessary mathematic tools. Then, we show that it may be unfeasible to extract formal expressions, even for simple protocols and small populations. Finally, we introduce the method used to estimate the behavior of population according to a specific protocol.

Background definitions

Using MAPP, it is possible to model the behavior of the scheduler, and then, formally study the state evolution of a population. At each step, the scheduler chooses a specific pair of agents only according to the probability given in the interaction graph Λ. Obviously, the interaction chosen at a specific step is independent of the past choices. Therefore, a given MAPP can be seen as a Markov chain with a finite state space, as the number of agents and the size of Q (the set of possible state of an agent) are finite. Then, the transition probability distribution of the Markov chain can be represented by a stochastic matrix, in which the evolution of the system can be extracted a priori.

Effectively, the Markov chain describing the system evolution is composed of the set of all configurations of the given MAPP, and the set of transitions is directly extracted from the probability distribution available in the interaction graph.

From now, it is necessary to introduce the mathematical background used in our study. In the sequel, we consider T an ordering index set, such as the natural numbers N, the non-negative real numbers [0, +∞), or a subset of these. Elements t ∈ T can be thought of as "times". From this time notion, given a stochastic process, it is possible to infer the time corresponding to the happening of the system in a specific state. Consequently, we can define the expecting of this time, corresponding to a mean hitting time: Definition 1 (First hit time) Given a probability space (Ω, Σ, P r) and a measurable state space S, let X : Ω × T → S be a stochastic process, and let A be a measurable subset of the state space S. The first hit time

τ A : Ω → [0, +∞] is the random variable defined by τ A (ω) = inf{t ∈ T |X t (w) ∈ A}
Definition 2 (Mean and variance of hitting time) Given a state I and a set of first time hit times {τ i A } i∈{n∈N:n<N } , the mean hitting time corresponds to the expected value of τ A starting on state I:

E I (τ A ) = lim N →∞ 1 N • N i=1 τ i A
and the variance hitting time is defined by:

σ 2 I (τ A ) = lim N →∞ 1 N -1 • N i=1 (τ i A -E(τ A )) 2
In the following, convergence refers to the point at which the stationary state in the Markov chain associated to a MAPP is reached (i.e. the stable configuration of a given population). Thus, the term convergence speed represents the mean hitting time of the stationary distribution.

On the difficulty to analyze a simple example

Unfortunately, the number of configurations of a MAPP is growing exponentially according to the size of Q and Υ. More formally, Appendix A.1 presents the evolution analysis of a simple example and shows that the number of states of the Markov chain is

|Q| |Υ| (= |Q| n ).
While it might be useful and simple to understand precisely the evolution of a system with a small number of agents, it becomes impracticable to study it formally when n grows significantly. In that case, it is still interesting to study empirically these systems.

Estimation of stabilization time using Markov chain

For large systems, the mean hitting time formal calculation of the Markov chain associated with a given configuration of MAPP is prohibitively computational intensive. However, using probabilistic methods, it is possible to obtain some empirical results

INRIA

on the behavior of these protocols. Despite the growing size of the Markov chain, it is always feasible to compute the possible transitions from a given configuration, and their probability to happen. Thus, it is conceivable to estimate the followed path across a Markov chain using its probability distribution. Nevertheless, it remains the problem to determine how many steps are needed to converge to the stationary distribution, within an acceptable error margin. To achieve this task, by using the Ergodic Theorem2 and among a large number of samples, which simulate the evolution of the system before reaching the stationary distribution, the average number of step may represent a correct estimation of the mean hitting time of convergence.

In order to estimate precisely this mean convergence time and errors, we use the Markov Chain Monte Carlo (MCMC) method [START_REF] Berg | Markov Chain Monte Carlo Simulations and Their Statistical Analysis[END_REF]. A Monte Carlo method is a computational algorithm which relies on repeated random sampling to compute its results [START_REF] Metropolis | The monte carlo method[END_REF]. Similar methods have been used to extract some empirical result in order to conjecture formal outcomes [START_REF] Beauquier | Brief announcement: Computing automatically the stabilization time against the worst and the best schedulers[END_REF]. In fact, from the observation of the behaviour of a system in a large number of simulations, it is possible to extrapolate some common characteristics of all these executions. They permit to guide the following formal study.

In this paper, we denote the same way the theoretical mean hitting time and the estimated one with the Monte Carlo method (and respectively for the variance). Thus, in the MCMC method, we consider the same definitions of Section 3.1, but with a huge value of N instead of N → ∞. The potential error of estimation is given by a confidence interval. This represents, with a known error percentage, an interval supposed to host the theoretical value estimated. This definition leads that greater the N , smaller the interval. More formally, we have: Definition 3 (Confidence interval) Given a state I and a set of first time hit times {τ A } i∈{n∈N:n<N } , the confidence interval of the estimation is defined as follow:

              
with 5% of error:

E I (τ A ) -1.96 • σ I (τ A ) √ N , E I (τ A ) + 1.96 • σ I (τ A ) √ N with 1% of error: E I (τ A ) -2.5758 • σ I (τ A ) √ N , E I (τ A ) + 2.5758 • σ I (τ A ) √ N
4 Impact of mobility models on convergence

In this section, we study the influence of mobility model on convergence speed of population protocols, using several probability distributions in MAPP.

Sampling of probability distributions on Γ

In order to simplify the system context, and thus preserve the spirit of population protocols, in this section, we assume the unicity of out-weight distribution of υ (OWD). More formally, given an agent υ ∈ Υ, the OWD is defined by the following multiset:

P υ = {p υ,ψ |ψ ∈ Υ -{υ}}
, that contains all the interaction probabilities in which υ is involved. For a population of n agents, it is obvious that |P υ | = n -1. Thus,

For instance, consider a 100 agent population. Figure 1 presents, for any agent υ ∈ Υ, five different OWDs used in the stochastic samples of MCMC. Each of these OWD is equivalent to a density function, represented in a decreasing way. Then, given that θ∈Θ p θ = 1, the area located below each OWD curve is equal to 2 n (the interaction graph is assumed undirected). Moreover, we consider a complete interaction graph, in which potentially, each agent may interact with any other. More formally, we have ∀υ ∈ Υ, ∀p ∈ P υ , p = 0. The name of each OWD is given according to the striking resemblance with well-known probability distributions. Uniform Each agent in the population has the same probability to interact with any other agent; Pareto -Flat This distribution is related to each agent having a bias towards a few other agents; Normal -Flat In this distribution, each agent has a bias towards a group of agents and another one privileged relation with few agents (and therefore their group); Normal -2 friends In this OWD, each agent has a higher probability to interact with two specific other agents; Normal -1 friend In this OWD, each agent has a high probability to interact with one other agent.

As the interaction graph is considered as undirected, the two last OWD are symetric, i.e. if an agent a has a high probability to interact with another agent b, then b has the same high probability to interact with a.

Starting from these OWD, our empirical observations can be classified in two sets. First studies using discrete time, the topology impact of interaction graph. Secondly, we observed the impact of inter-contact time distribution model, in order to model continuous time.

Estimation in discrete time: Contact models

In the following, we study the impact of such mobility models on the convergence speed of two protocols (or and sum modulo 4).

INRIA

Let observe the impact of these OWDs and of graph characteristics on the mean convergence time, and so, on the convergence speed of protocols.

Complete Interaction Graph

Considering in first hand, a complete intergation graph, as in the former model. Each agent has then a not-null probability to interact with any other agent of the population. Formally, we have: ∀υ ∈ Υ, ∀p ∈ P υ , p > 0.

Figures 2, 3 and 4 depict, for each aforementioned OWD (cf. Figure 1), the average convergence speed in term of number of interactions required to reach stabilization. They represent respectivelly the impact of graph size, which varying from 0 to 100, for the or, majority and sum operations. To all of these average values is associated the confident interval with 1%-error.

We observe that the OWD has a significant impact on the convergence speed. We deep into detail for both of them.

First, the more biased the distribution, the greater the impact. It is especially verified for large graph on which the "flat" OWDs (uniform, Pareto and Normal) are usually greater than the ones with a small number of "friends". We also observe that the uniform distribution consistently leads to faster convergence, for any protocol and any population size. We come back on this observation with more details in Section ??.

Moreover, we observe that for small-size graphs, Normal-2 and *-Flat are equivalent. Moreover, as the number of agents increases, the distribution Normal-2 gets close to Normal-1. This evolution, observed consistently over all graphs, is exacerbated in Figure 4 due to the characteristics of the sum operation. Indeed, the order of interaction for the sum operation has a stronger impact: reaching the stationary distribution required several interactions for each pair of agents.

Finally, on the context of complete interaction graph, it is interesting to study the flushing coefficient of highest probabilities, defined below. In fact, usely, the generated graph are regular, i.e. higher probabilities are uniformly spread among the whole population. However, still respecting the OWD unicity assumption, it is possible to flush the graph in order to remove highly connected area of the graph, in term of high probability (i.e. kind of interaction group simulating social behavior). The flushing coefficient represents the probability to exchange two edges in the initial regular graph, and thus, make the graph more or less randomized. Figure 5 presents for non-uniform OWD the mean number of interaction required to reach the stationary system state for the or function, according to the flushing coefficient. It is obvious that the clustering coefficient (cf. next paragraph) of highest probability edges has no impact on the convergence speed.

Restricted Interaction Graph

We now consider the impact of characteristics of a restricted interaction graph (see Section 2.3.1). More formally, it boil down to relax the not-null hypothesis of of probabilities: ∀υ ∈ Υ, ∀p ∈ P υ , p ≥ 0. Moreover, for the same clarity reason, we still consider only the OWD unicity assumption. Thus, we obtain that ∀υ ∈ Υ, ∃p ∈ P, p = 0.

We only consider the or function in this sub-section. Indeed, the majority and sum modulo required specific topologies to converge. For instance, the sum modulo imply that the collecting agent has to interact with all the other agent in order to put the final value on. It is then trivial that this protocol cannot converge in the context of restricted interaction graph. Observations revealed above remains obviously valid in the context of restricted interaction graph. Two characteristics have a non-negligeable impact on the convergence speed of considered protocols: (1) the number of probability in the OWD equals to 0 and (2) the coefficient of clustering of the graph for a given OWD. Then, we focus in this section only on these two characteristics: graph emptyness rate and clustering coefficient.

The graph emptyness rate corresponding to the inverse of the density in term of edge quantity in any graph (i.e. it represents the ratio of void in a graph). In our context, the emptyness rate corresponds to the ratio of null probability edges.

Figure 6 depict for the various OWD, the average number of interactions in the or operation depending on the emptyness rate. These result are extracted from a 100 agent population on a regular graph. Despite a light impact for a low emptyness rate (complete graph to 40%), the consequences on convergence speed for high rate are significant. Even though this observation seems intuitive, ones can think that for a regular graph with an emptyness rate of 98% (i.e. a graph with a ring topology), the convergence speed have to be increased. On the contrary, for any given OWD (except "Normal -1 friend" in which an agent interact with almost only one specific other), the number of interaction required grows significantly and the differences are merging in a common behavior. This speaks certainly on the fact that all OWD have only two non-null probabilities, these last are then all equivalents to the uniform one.

In other hand, we consider the clustering coefficient (CC). Initially introduced in [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], it represents the rate of neighbors vertices which are also directly link by another edge. It is often correlated to the characteristic path length in a general graph G(V, E). In the following, we denote adj i the set containing all the successors of a vertex i in a graph. More formally, we have:

Definition 4 (Clustering coefficient) Let a vertex v ∈ V of a graph G(V, E). Given K = kv•(kv-1)

2

where

k v = |adj G (v)|, the clustering coefficient of vertex v is: C v = |{(x, y) ∈ E|x, y ∈ adj G (v)}| K .
Then, in global view, the clustering coefficient of graph

G is C G = v∈V C v |V | .
Definition 5 (Characteristic path length) Let a graph G(V, E). the shortest path lenght L v,v between v and v is the number of edges in the shortest path for v, v ∈ V 2 . Then, in global view, the characteristic path length of a graph G is define as follow:

L G = (v,v) ∈V 2 L v,v |V 2 | .
As the characteristic path coefficient is strongly correlated to the clustering coefficient [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], they have a similar impact on the convergence. Therefore, we do not consider the impact of the path coefficient impact in this paper.

Figure 7 presents, for each considered OWD, the convergence speed depending on the clustering coefficient in a 48 agent system and 8 edges, with a 83% emptyness rate. These values has been chosen regarding on sparseness values between the OWDs related by the previous observations. It is observable here that the clustering coefficient has an impact on the number of interactions required to converge, but conversely as the common knowledge, this impact remains slight.

INRIA

All these measure on graph characteristics have been conducted in discrete time. The convergence time has been then formulated in number of interactions required to reach the stationary distribution of the associated Markov chain. In this context, two interactions made in parallel is considered as sequential. This hypothesis is not more valid in the continuous time context. Observing the impact in this context is the aim of the next section.

Estimation in continuous time: Inter-contact models

While the contact model provides the probability for each agent to interact with other, it is not possible to directly infer the convergence time necessary to converge. Thus, for a continuous time environment, it is not sufficient to specify only the OWD, as this last does not reflect the frequency of such interactions. This frequency can be seen as the inter-contact frequency.

So, given a specific OWD, the number of steps to reach the stationary distribution remains the same, regardless of the contact and inter-contact duration. In this subsection, we estimate using stochastic simulation the convergence time in the continuous time domain, for several well-known distributions of inter-contact times.

In these experiments, we consider a complete interaction graph and the OWD unicity among the population. We use three of the extensively used inter-contact time distribution, extracted notably in [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Conan | Characterizing pairwise inter-contact patterns in delay tolerant networks[END_REF]: Exponential, Pareto (known also as Power-Law) and Log-Normal distributions. These distributions are formally defined respectively by the following function

λ • e -λx , k • x k m x k+1 et 1 xσ √ 2π e -(ln(x)-µ) 2 2σ 2
, with parameters λ > 0, x m > 0, k > 0, σ > 0 and -∞ < µ < ∞.

In order to measure separately the impact of contact and inter-contact duration, each simulation has been conducted first with atomic contact (i.e. one unique interaction for each contact of a given pair) and second, with uniform contact lenght (i.e. one interaction per second during the whole length of the contact, which duration is picked uniformly between 1 and 100 seconds). For each simulation, the settings of these distributions are comparable: the average inter-contact length is set to 15 minutes, and, in case of non-atomic contact, the maximum contact duration is set to 100 seconds. Two simulation sets has been conducted for different sizes of the population: one for the or and another for the majority primitive. Figures 8 and9 present the results obtained using these both sets in case of atomic contact, as Figures 10 and11 present the ones in case of uniform contact length. Each simulation set contains an estimated convergence date using MCMC in the continuous time domain, for the three aforementioned inter-contact distribution among OWD "Uniform", "Normal -Flat" et "Normal -2 friends".

The observation of these figures permit to obviously conclude on the strong impact of inter-contact distribution on convergence speed of a protocol, for a given population size. Moreover, it seems clear that on these examples, the duration of contact has a small influence on the convergence speed (cf. the aspect of Figures 8 and10, as well as the Figures 9 and11).

However, we can raise two singularities of these 4 figures. While the population size has a small influence on convergence time for inter-contact distribution in Pareto and LogNormal, this one has a strong impact for the exponential distribution. The almost constant execution time using the two first distributions can be explained by the multiplication of parallel interaction as the population growing. At contrary, the third distribution have an influence, in gain or loss, on convergence for very large scale population. This observation infers the second characteristic of these diagrams. This last concerns also only the exponential distribution. As the convergence time decrease according to the population growing for OWD "Uniform" and "Normal -Flat", it is increasing significantly in case of the OWD "Normal -2 friends" among a large graph. This arise from the unbalancing of contact probabilities, infer by the given OWD. On the other hand, undestanding why the fact that this disproportion do not have an influence in the context of Pareto inter-contact distribution remains open.

To put in a nutshell, the impact of the inter-contact model is meaningful but keeps the same order of magnitude and surprisingly, is independent to the duration of contact. Following these set of observation, we continuously observed that using an uniform OWD permit to reach the best average convergence time, for any graph configuration and using discrete or continuous time. Inspired by this conjecture, we propose to formalize and to prove this outcome, for any given configuration and any population protocol. We observed from the simulations that the mobility patterns of agents might have a significant impact on the convergence speed of population protocols. Yet, the uniform distribution consistently leads to obtain a better convergence speed than the other distributions. Although this seems natural for some operations (as for the sum operation in which all agents have to interact with each other several times to converge), it is actually counter-intuitive for some others like flooding. Indeed, for the or operation, by removing the unicity of OWDs hiterto used, one might think that a global OWD, in which the source agent is involved in almost all the interaction3 , converge faster than the uniform OWD.

In this section, we propose a theorem that rebuts this intuition. We prove that a uniform distribution of weights always achieves the best convergence speed, regardless of the considered operation in population protocols. That means that the uniform OWD corresponds to the lower bound of the mean hitting time (i.e. the average number of steps needed to reach the stabilized state of a population).

Theorem 2 For any function computable by a population protocol, the lower bound of the convergence speed is reach using an uniform OWD in MAPP.

Proof. Roughly speaking, in this proof, we first (i) characterize any predicate computable by a population protocol. Then, (ii) by characterizing how to compute them using combination of population protocol, we will infer that (iii) any population protocol owns a polynomial mean hitting time. Finally, we prove that (iv) any polynomial mean hitting time accept a lower bound for an uniform OWD.

Characterization of computable functions

In [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], Theorem 5 states that every predicate belonging to the Presburger arithmetic is stationary computable by a population protocol. This arithmetic fully characterize the wholeness of population protocols' computable function [START_REF] Angluin | Stably computable predicates are semilinear[END_REF]. Thus, these two domains of function share the same equivalence class.

First, consider a factorization of all Presburger arithmetic's predicate. Let Σ = {σ 1 , . . . , σ k } an arbitrary input alphabet, and A i , c, m integer constants such that m ≥ 2. Then, it has been shown that the entire Presburger arithmetic can be stationary computable using a combination of the following predicates on non-negative integers x 1 , . . . , x k :

• i a i x i < c; • i a i x i ≡ m c (i.e. i a i x i ≡ c modulo m);
• Any 2-place Boolean function ξ.

We present below the population protocols that compute each element of these last generator set of predicates. We prove that for any combination of this predicates, an uniform OWD in MAPP corresponds to the optimal convergence speed of this combination. Thus, any predicate of the Presbuger arithmetic, computed by combination of these population protocols, has an optimal convergence speed with the uniform OWD.

As this class of combination has the same equivalence class than population protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], it is obvious to conclude that if any combination of generator population protocols achieves an optimal convergence speed for a given OWD, this OWD will also be optimal for all the population protocols.

Generator population protocols' definition We first present both population protocols introduced in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] that compute the two first aforementioned predicates. Let s = max(|c| + 1, m, max i |a i |). In both protocols, the set of space Q is the set {0, 1} × {0, 1} × {u ∈ Z| -s ≤ u ≤ s}, and the associated function ι corresponds to

σ i → (1, 0, a i ).
The first bit of the state is denoted the leader bit and is used to elect an unique leader, which aggregates the value of the linear combination. The second bit is denoted the output bit which stores, for each agent, the output value computed by the last encounter leader. The third entry of a state is a counter used for collecting the linear combination of x i (left-hand side of the previous predicates). The output function ω simply maps (•, b, •) to b.

We now describe the transition rules for each of the two protocols (the correction of these protocol is proved in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]).

• Consider, for all integers u, u such that -s ≤ u, u ≤ s, the two following functions:

q(u, u ) = max(-s, min(s, u + u )) r(u, u ) = u + u -q(u, u ).
It is obvious that q(u, u ), r(u, u ) ∈ [-s, s] and that q(u, u )+r(u, u ) = u+u . We define b(u, u ) = 1 if q(u, u ) < c and 0 otherwise. The δ function is define as follow if at least or are equal to 1: ( , •, u), ( , •, u ) → (1, b(u, u ), q(u, u )), (0, b(u, u ), r(u, u )).

In the case where both and are null, the interaction has no effect.

• Consider now that b(u, u ) = 1 if u + u ≡ m c and 0 otherwise. The second protocol works using the following class of transition: ( , •, u), ( , •, u ) → (1, b(u, u ), (u + u ) mod m), (0, b(u, u ), 0). if at least or are equal to 1. Otherwise, when both and are null, the interaction has still no effect.

Inspired by the proof of Lemma 3 in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], we still need to present the computation of a boolean function ξ on two stationary computable predicates F and G. Let A (respectively B) a protocol that stationary computes F (respectively G); we assume that A and B share the same input set Σ. Consider the protocol C which stationary computes ξ(F, G) by parallel combination of A and B (the population runs protocols A and B in parallel and outputs the value of ξ applied to the outputs of the two computed predicates F and G).

More formally, let Q A and Q B the state set respectively of A and B. The set of states of C is defined as

Q C = Q A × Q B . The associated input map ι C corresponds to σ ∈ Σ → (ι A (σ), ι B (σ))
and the transition function is defined as δ C ((p 1 , p 2 ), (q 1 , q 2 )) = ((p 1 , p 2 ), (q 1 , q 2 )) with δ A (p 1 , q 1 ) = (p 1 , q 1 ) and δ B (p 2 , q 2 ) = (p 2 , q 2 ). Finally, the output map applies ξ to the both protocols' outputs: ω C ((q 1 , q 2 )) = ξ(ω A (q 1 ), ω B (q 2 )).

The convergence speed of C directly depends of the speed of A and B. In more details, the convergence speed of C is exactly the same than the lowest one between INRIA A and B. Without loss of generality, we assume that A has a mean hitting time lower than B. Then, the mean hitting time of C is the same than B. Thus, the optimal OWD distribution for B will be also optimal for C.

Intermediate summary Let get a general vision of the remaining part of this proof. We show below that the optimal distribution for each of the two aforementioned protocols is an uniform OWD. Thereby, using parallel combination, any predicate coming from Presburger arithmetic is stationary computable in an optimal mean hitting time with an uniform OWD. This extension result is given by the fact that any mean hitting time function is characterized by a polynomial function of p i .

Mean hitting time is polynomial Let P a protocol and M P its associated Markov chain. Let S the state corresponding to the stationary distribution. Considering an initial state I, we have to solve the following simultaneous equations, containing m = n(n-1) 2

variables:

   E I (τ S ) = f (p 1 , . . . p m ) pi p i = 1 = g(p 1 , . . . p m ) (2)
We define a path in M P by a sequence of states of M P : k 1 , k 2 , . . . , k s with s ∈ N\{0}. Let us define C s (I, S) the set of all paths from I to S with a length equals to s and in which S not appears but the last: C s (I, S) = Let q A,B the probability to go from A to B in the Markov chain M P . Thus, we have:

E I (τ S ) = s∈N\{0} s • c∈Cs(I,S) q I,k2 • q k2,k3 • . . . • q ks-1,S
In the Markov chain M P , every transition probability label only depends on the potential interaction which makes the system evolve from a state k to another state k , and, consequently, only depends on the sum of the p i corresponding to these interactions. Moreover, to analyze the advancement of the system state, the chain M P associated respectively to each of the both aforementioned protocols can be simplified to only take into account the first bit of the triplet state (the leader bit). Formally, let E be the states' set of M P where E = {0, 1} n for n agents in the population. As agents are anonymous, all states with the same distribution of the leader bits are clustered into a common meta-state in the resulting Markov chain. For each possible transition of δ, the number of leader bits, which are set to 1, cannot be increased. It can only be strictly decreased in case of both agent which act in the interaction own a 1 leader bit, or remain constant in case of one interacting agent owns a 1 leader bit, and the other owns a 0 leader bit. Thus, it exists two kinds of transitions in M P : ∀e, e ∈ E, q e,e =

                       P[i 1 → i 2 ] = p i1,i2 if    ∀j / ∈ {i 1 , i 2 }, e j = e j e i1 = e i2 = 1 e i1 = e i2 = 0 j =i0∧ej =1 P[j → i 0 ] (= p j,i0 ) if    ∀j = i 0 , e j = e j e i0 = 1 e i0 = 0 0 otherwise
Then, for any transition q in M P , q is a linear application of p i . This infers that E I (τ S ) and, by definition in Equation ( 2), the function f is a polynomial on p i .

On the lower-bound characterization To find the optimal distribution for p i ∈ ]0, 1[, we are looking for a minimization of f (p 1 , . . . , p m ), according to variables (p 1 , . . . , p m ), under the constraints of Equation (2): m i=1 p i = 1 (Moreover, by this constraint, it is possible to deduct p m from the other variables (p 1 , . . . , p m-1 )).

Consider an OWD in the interaction graph such that ∀p

i , p i > 0. Let D = {(p i ) 1≤i≤n ∈]0, 1[ n , n i=1 p i = 1}. It is an open subset of R n .
In topology, using the Taylor formula, we can argue that if a function in C 1 admits minima in an open set, the derivative is null at this point. Then, as f is a polynomial, f and its derivative of first order are continuous. So, f ∈ C 1 . Consequently, the minimal value of f on the closure of D is reached either on one of its limit point, or on a vector p * inside D such that ∇f (p * ) = 0 (∇ is the gradient of f and is defined as ∇f (p) = ∂f ∂p1 (p), . . . , ∂f ∂pm (p) . In the population protocol model, the interaction graph is complete and thus, ∀i ∈ {1, . . . , n}, p i = 0. So, the minimal value of f is reached on p * ∈ D if ∇(f )(p * ) = 0.

As the minimal value is reached on such a p * vector, using the weak Lagrangian principle, we can infer that ∇(g)(p * ) = 0. Beyond, by definition, g is a constant function. Thus, all partial derivatives of g are identical: ∀i, j ∈ 1, m , ∂f ∂pi (p * ) = ∂f ∂pj (p * ). Then, p * is the equidistributed point on D (i.e. ∀i, j ∈ 1, m , p i = p j ). Finally, for any given population protocol, the minimum of E I (τ S ) is reached for a uniform distribution of p i , i ∈ 1, m , namely, the uniform OWD.

From this theorem, we can conclude that, for any population protocol, it is impossible to have a mean convergence speed better than the one obtained using a totally uniform interaction graph.

On the relevance of the Random Way Point model

The Random Way Point mobility model is extensively used to evaluate mobile ad-hoc networks whereas often criticized for its lack of realism. In this section, we show that the uniform distribution of MAPP is actually equivalent to the random waypoint. Beyond the theoretical interest of this proof, our objective is to emphasize the fact that, while the use of the random way point model is often justified in an attempt to provide a neutral setting, this actually provides the best setting with respect to convergence time.

n . At the beginning of the experiment, each agent picks at random a destination point and a space velocity, according to law P pos and P vit respectively, common to all agents in the network. As a guideline, usually, the destination point distribution is uniform according to the given moving area and the space velocity is picked uniformly among a given interval. We show our result in a more general way and only assume that each sample is an independent ergodic system.

For every agent x, we define γ x (t) as the trajectory of this agent inside the moving area. This trajectory only depends of the sequence of pair (p

(i) x , v (i)
x ) i∈N * . As the spatial distribution of nodes is not uniform [START_REF] Bettstetter | The node distribution of the random waypoint mobility model for wireless ad hoc networks[END_REF] in case of using a reflecting random waypoint (bounded moving area -not a tore -and bouncing on side), we prove below that the contact probability for two agents is uniform (agents' moves are i.i.d.).

Let x, y two agents. Consider the following equation during a fixed period T that gives a formal expression of the temporal mean contact period:

1 T T 0 1 |γx(t)-γy(t)|≤ε (t) • dt. (3)
In this equation, 1 |γx(t)-γy(t)|≤ε (t) represents the indicator function which is defined as 1 if x and y are separated by a distance lower or equal to ε, and 0 otherwise. If Equation 3 tend toward a constant value completely independent of the (x, y) pair choice, then this constant is the same for any pair of agents in the system. Consider γ x (t) the generic trajectory probability law for a given agent x:

P x = ∞ i=1 p (i) x ⊗ ∞ i=1 v (i)
x .

Consider now the pair of trajectories (γ x , γ y ). This last is a random variable according to the law P x ⊗ P y . We can define the following system:

(p (i) x , v (i) x , p (i) y , v (i) y ) i∈N * , P x ⊗ P y , λ ⊗
where λ ⊗ is the invariant product Lebesgue measure. By definition, this system is a product of independent ergodic systems, and consequently, it is itself an ergodic system. Then, it is possible to apply the Ergodic Theorem on it (also named large numbers law which argues that the temporal mean converge toward the spatial mean).

Let us introduced the spatial mean as follow:

E[1 |γx-γy|≤ε ] = 1 |γx-γy|≤ε • dP x (γ x ) • dP y (γ y ) (4)
For a.e. 4 trajectories γ x and γ y , when T tends toward ∞, Equation 3 tends toward Equation 4. This last equation corresponds to an integral among all possible trajectories of x and y agents. So, this expression do not depend of x and y, but only of ε and of the trajectory probability laws P (These last are identical for every agents in the system).

In short, for any pair of agents, the average number of contact is the same. Then, every pair of agents has the same probability to come in contact at time t. This means that we can simulate the random waypoint model by using a uniform OWD in MAPP.

Conclusion

In this paper, we study the impact of the agents' mobility model on the convergence speed of population protocols. We introduced MAPP (Mobility Applied to Population Protocol), a population protocol model augmented to take into account the probability distribution of agent interactions. In this model, each edge of the interaction graph is weighted by a probability value reflecting the interaction frequency between the two agents linked by that edge.

We first empirically studied the significant impact of various mobility models on the convergence speed of two classical population protocols (or and sum modulo 4) and extracted some interesting bias according to the sociability and meeting models.

From the empirical study, we observed that the uniform interaction distribution turns out to consistently achieve the best average convergence time. We then formally proved that the uniform OWD provides the lowest bound of the average number of steps to reach convergence in population protocols.

Finally, we also demonstrated that the Random Way Point mobility model, which is the most extensively used to evaluate mobile networks, infers a uniform distribution in MAPP. Interestingly enough, not only the Random Way Point model is recognized as non-realistic, but we show that it actually provides the best-case scenario. This may lead to question the relevance of using such a model as a representative mobility model.

A Appendix

A.1 Impossibility of simple formula

In this appendix, we show that, even for a very simple context, it is prohibitively computational intensive to obtain a formal expression of the mean hitting time.

Let consider a very simple example: the Or operation for a generic MAPP. In this protocol, we have a minimum size of Q (here, |Q| = 2). Moreover, the Markov Chain is aperiodic as an "infected" agents cannot be heal. below, we show that, as simple this protocol is, the formal analysis of the convergence speed is not computable for arbitrary number of agents.

Let consider a very small population with only for 4 agents. Top of Figure 12 presents the interaction graph of this population. In order to simplify the context, we consider here that all agents share the same out-weight distribution (i.e each agent have exactly one edge weighted by p, another by p and a last by p ). Thus, agents are undistinguishable by their state but also by their out-weight distribution.

Then, the bottom part of Figure 12 represents the associated Markov chain M asociated to this population for the or protocol. Agents in state 0 are represent by white circle at contrary to black circle representing agents in state 1. To identify the different configurations, all state of the Markov chain has been labeled with an integer of [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Berg | Markov Chain Monte Carlo Simulations and Their Statistical Analysis[END_REF]. Finally, in order to present a finer graph, we do not represent the loop edges that keeps the population in the same state. All of this edges are labeled by 1 minus the sum of all out-edges probability labels:

p i,i = 1 -   j∈[1,i-1]∪[i+1,8] p i,j  
In the following, we will denote Adj i the set containing all the successors of a vertex i in a graph. Using stochastic analysis, by considering the starting point in state 1, we can directly extract the formal expression of the mean hitting time in that case:

E 1 (τ 8 ) = k∈Adj1 p 1,k • E 1 [t 1→k + t k→8 |1 → k] =   k∈Adj1 p 1,k • E 1 [t 1→k |1 → k]   +   k∈Adj1 p 1,k • E 1 [t k→8 |1 → k]   =   k∈Adj1 p 1,k   +   k∈Adj1 p 1,k • E k (τ 8 )   = 1 + k∈Adj1 p 1,k • E k (τ 8 )
We can extract the following equation:

E 1 (τ 8 ) = 2 + q∈{p,p ,p"} 2 • q • 3 -4 • q 1 -2 • q (5)
Let now consider the extension of this Markov chain to n agents, slightly represented in Figure 13. In this figure, we represent the state of the population by vectors INRIA

Figure 1 :

 1 Figure 1: Comparison of different OWDs for one anonymous agent in MAPP

Figure 2 :

 2 Figure 2: Average number of step and confidence interval according to the number of agents for the or protocol, among a complete interaction graph.

Figure 3 :

 3 Figure 3: Average number of step and confidence interval according to the number of agents for the majority protocol, among a complete interaction graph.

Figure 4 :

 4 Figure 4: Average number of step and confidence interval according to the number of agents for the sum modulo 4 protocol, among a complete interaction graph.

Figure 5 :

 5 Figure 5: Average number of step and confidence interval according to the flushing coefficient for the or protocol, among a complete interaction graph.

Figure 6 :

 6 Figure 6: Average number of step and confidence interval according to the emptyness rate for the or protocol, among a restricted graph of 100 agents.

Figure 7 :

 7 Figure 7: Average number of step and confidence interval according to the clustering coefficient for the or protocol, among a restricted graph of 48 agents.

Figure 8 :

 8 Figure 8: Average convergence time and confidence interval according to the number of agents for the or protocol with atomic contact.

Figure 9 :

 9 Figure 9: Average convergence time and confidence interval according to the number of agents for the majority protocol with atomic contact.

Figure 10 :

 10 Figure 10: Average convergence time and confidence interval according to the number of agents for the or protocol with uniform contact length.

Figure 11 :

 11 Figure 11: Average convergence time and confidence interval according to the number of agents for the majority protocol with uniform contact length.

{k 1 ,

 1 k 2 , . . . , k s |k 1 = I, k s = S, ∀i ∈ {1, . . . , s -1}, k i = S} So, it is possible to infer a formal expression of the mean hitting time: E I (τ S ) = s∈N\{0} c∈Cs(I,S) E I [τ S |c] • P[c] As the path in M P is determined for a specific c ∈ C s (I, S), we have E I [τ S |c] = s. Hence: E I (τ S ) = s∈N\{0} s • P[C s (I, S)]

INRIA Theorem 3

 3 The Random Way Point mobility model is equivalent to an uniform OWD in MAPP.Proof. The Random Way Point model can be formally defined as follows. Consider n mobile agents, with initial position p (0) 1 , . . . , p

RR n°6580

Note that Manet and DTN work usually focus only on inter-contact time property. INRIA

Also known as Large numbers law: Given a sample of independent and identically distributed random variables with a finite population mean, the average of these observations will eventually approach and stay close to the population mean.RR n°6580

For instance, consider the following distribution: one agent has a huge probability to interact with any other agent, and all other possible interactions have a tiny probability to happen.RR n°6580

a.e. means almost every: one says that a property holds almost everywhere if the set of elements for which the property does not hold is a null set, i.e. is a set with measure zero.RR n°6580

: : Proof. Each agent pick their state into Q. Then, if we consider the system state as a vector of each agent's state, it exist at most |Q| × • • • × |Q| possible states. In case of generic OWD, we cannot consider this vector as a multiset because the position of the agnet in the interaction graph is not independent. Then, we have |Q| |Υ| differents states, which any of them can corresponds to the initial system state. Then, the number of states of the Markov chain is |Q| |Υ| .

Contents