Marta Galera Martinez

Doan Pham
email: doan.phamminh@mines-albi.fr

Elsa Weiss-Hortala

Ange Nzihou

Patrick Sharrock

Marta Galera Martínez

Synthesis, characterization, and thermo-mechanical properties of copper-loaded apatitic calcium phosphates

Keywords: apatite, copper, ionic exchange, incipient wetness impregnation, thermo-mechanical analysis

come

Introduction

Calcium hydroxyapatite (Ca-HA), with the stoichiometric formula Ca 10 (PO 4 ) 6 (OH) 2 , belongs to apatitic family. This mineral has the advantage of thermal stability, insolubility in water, high stability under reducing and oxidizing conditions, and to be able to accept many ions into its structure. [START_REF] Marchat | Adsorption and incorporation of cadmium into a calcium hydroxyapatite[END_REF][START_REF] Sheha | Sorption behavior of Zn(II) ions on synthesized hydroxyapatites[END_REF] Thus, Ca-HA-based materials can be used in a wide variety of applications such as biomaterial engineering [START_REF] Lazic | The effect of temperature on the properties of hydroxyapatite precipitated from calcium hydroxide and phosphoric acid[END_REF]; chromatography column fillers for the analysis of proteins [START_REF] Shepard | Discoloration of ceramic hydroxyapatite used for protein chromatography[END_REF]; treatment processes to remove toxic heavy metals from contaminated soils [START_REF] Boisson | Evaluation of hydroxyapatite as a metal immobilizing soil additive for the remediation of polluted soils. Part 1. Influence of hydroxyapatite on metal exchangeability in soil, plant growth and plant metal accumulation[END_REF]; wastewater [START_REF] Fernane | Sorption of cadmium and copper ions on natural and synthetic hydroxylapatite particles[END_REF][START_REF] Baillez | Removal of aqueous lead ions by hydroxyapatites: equilibria and kinetic processes[END_REF]; fly ashes [START_REF] Nzihou | Calcium phosphate stabilization of fly ash with chloride extraction[END_REF]; backfill for nuclear waste repositories [START_REF] Moore | Sorption of plutonium(VI) by hydroxyapatite[END_REF]; and catalysis. [START_REF] Solhy | Efficient synthesis of chalcone derivatives catalyzed by re-usable hydroxyapatite[END_REF][START_REF] Resende | Effects of anion substitution on the acid properties of hydroxyapatite[END_REF] In heterogeneous catalysis, Ca-HA-based materials can be used in a wide range of reactions. [START_REF] Ya-Ping | Complete hydrogenation of quinoline over hydroxyapatite supported ruthenium catalyst[END_REF][START_REF] Liptáková | Direct synthesis of phenol from benzene over hydroxyapatite catalysts[END_REF][START_REF] Boukha | Methane dry reforming on Ni loaded hydroxyapatite and fiuoroapatite[END_REF][START_REF] Wuyts | A heterogeneous Ruhydroxyapatite catalyst for mild racemization of alcohols[END_REF][START_REF] Masuyama | Environmentally-benign palladium(II)-exchanged hydroxyapatite-catalyzed allylic alkylation of allyl methyl carbonate in water[END_REF] Ca-HA can catalyze itself different chemical reactions, thanks to its interesting physico-chemical properties, particularly the presence of both acidic and basic sites on its surface. [START_REF] Tsuchida | Reaction of ethanol over hydroxyapatite affected by Ca/P ratio of catalyst[END_REF] It can also be used as a support for the dispersion of other active phases, which are usually metals or metal oxides. [START_REF] Boukha | Methane dry reforming on Ni loaded hydroxyapatite and fiuoroapatite[END_REF][START_REF] Venugopal | Hydroxyapatite as a novel support for gold and ruthenium catalysts: behaviour in the water gas shift reaction[END_REF][START_REF] Cheikhi | Direct synthesis of methyl isobutyl ketone in gas-phase reaction over palladium-loaded hydroxyapatite[END_REF] With specific surface areas up to 100 m 2 g À1 , the deposition of the metal or metal oxide on the surface of Ca-HA can be carried out by classical methods such as incipient wetness impregnation (IWI). [START_REF] Achchar | New apatite-based supports prepared by industrial phosphoric acid for HDS catalyst synthesis[END_REF] Small clusters of metal or metal oxide are expected to form on the surface of the support. In addition, the excellent cationic exchange capacity of Ca-HA offers a particular route for the insertion of different divalent cations on its surface. In this case, it could be assumed that the active metal exists in cationic form, so at atomic scale. Thus, different physico-chemical, and therefore catalytic, properties of the composite might be expected, depending on the preparation method used.

We report in this paper the physico-chemical properties of copper-doped Ca-HA composites, which were prepared by two different routes, namely, ion exchange (IE) and IWI. Different characterization methods were used in order to understand the deposition and/or incorporation of copper on the surface of Ca-HA. This helps to optimize, in the next step, the use of copper-doped Ca-HA composites in the appropriate catalytic applications, since copper-based catalysts are found to be active in different catalytic processes. [START_REF] Rajeev | Thermal decomposition studies. Part 19. Kinetics and mechanism of thermal decomposition of copper ammonium chromate precursor to copper chromite catalyst and correlation of surface parameters of the catalyst with propellant burning rate[END_REF][START_REF] Masuyama | Hydroxyapatite-supported copper(II)-catalyzed azide -alkyne [3+2] cycloaddition with neither reducing agents nor bases in water[END_REF] 2. Materials and methods

Preparation of apatitic calcium phosphates powder

Calcium carbonate powder (98 wt.%, Fisher Scientific) and orthophosphoric acid (85 wt.% in water, Merck) were used as received for the preparation of apatitic calcium phosphate. The choice of these starting reactants was based on their wide availability and low cost in comparison with classical reactants, such as calcium nitrate, calcium chloride, and alkali orthophosphate salts which require extensive washing of the resulting alkali salts from the calcium phosphate precipitate to obtain a pure product. In fact, in the previous work, Pham Minh et al. [START_REF] Pham Minh | Apatitic calcium phosphates: synthesis, characterization and reactivity in the removal of lead(II) from aqueous solution[END_REF] showed that apatitic calcium phosphates starting from calcium carbonate and orthophosphoric acid had the same reactivity as Ca-HA synthesized from water soluble reactants, for the removal of lead(II) in an aqueous solution.

For the synthesis of Ca-HA, 100 g of calcium carbonate and 400 g of deionized water were introduced into a 1.2 L Pyrex batch reactor. Afterwards, 69.2 g of orthophosphoric acid (density of 1.71 g mL À1 ) was pumped at the rate of 1 mL min À1 . The homogeneity of the reaction mixture was assured by a two-blade mixer (400 rpm). The reaction was kept at ambient conditions for 48 h. After 48 h, the product was filtered and dried overnight at 105 °C in an isotherm oven, then calcined at 400 °C for 2 h to avoid all further evolution of the solid. The resulting solid powder was labeled CaP-ini, which was used for all further preparation of copper-doped apatitic calcium phosphates.

Copper deposition

Using IE, 7.5 g of CaP-ini were put into 300 mL of copper nitrate trihydrate (Cu(NO 3 ) 2 •3H 2 O, >95 wt.%, Fisher Scientific) solution of know concentration under stirring at 350 rpm. After 4 h of contact, the suspension was filtered and the resulting solid was washed with permuted water and dried overnight at 105 °C. Using IWI, the required amount of Cu(NO 3 ) 2 •3H 2 O was dissolved in a volume of permuted water adapted to wet the outer and pore surfaces of CaP-ini. This solution was then added dropwise to 10 g of CaP-ini at ambient temperature. At the completion of the addition, the powder was damp. Afterwards, the resulting solid was dried overnight at 105 °C. For both methods used, a half of dried solid was then calcined at 400 °C for 2 h. In all cases, the concentration of copper nitrate solution was adjusted to have the theoretical contents of copper of 2 and 20 wt.% considering the deposition of copper on CaP-ini particles to be total. Samples were designated according to: (i) the method of preparation (IE or IWI); (ii) the theoretical percentage of Cu (2 or 20 wt.%); and (iii) the thermal treatment (DRY: only dried at 105 °C (or uncalcined); or CAL: calcined at 400 °C). For example, CaP-IE-2-DRY corresponds to the solid prepared by IE method for obtaining theoretically 2 wt.% of copper, which was only dried at 105 °C.

Characterizations

The contents of Cu in the powders were obtained by inductively coupled plasma-atomic emission spectrometry analysis (ICP-AES) using a HORIBA Jobin Yvon Ultima 2 following dissolution of samples in a mixture of HCl and HNO 3 acids. Thermogravimetry analysis (TG) was performed using a TA Instrument SDT Q600 analyzer. Weighed portions of powder sample ranged from 20 to 25 mg. The analysis was carried out in the temperatures ranged from 25 to 1000 °C with a heating rate of 5 °C min À1 under the air flow rate of 100 mL min À1 . Thermo-mechanical analysis (TMA) was carried out in a Setaram Setsys 16/18 with 5 g of constant load on the powder sample under air atmosphere with the heating rate of 10 °C min À1 . X-ray diffraction (XRD) measurements were performed using a Phillips Panalytical X'pert Pro MPD diffractometer with Cu-Kα (1.543 Å) radiation source at 45 kV and 40 mA. The identification of crystalline phases was carried out by comparison with JCPDS database. Fourier transform infrared spectroscopy (FTIR) was carried out using a Shimadzu 8400S spectrophotometer. The specific surface area was determined by nitrogen adsorption at 77 K using a Micromeritics Gemini Vacprep 061 with the BET model (S BET ), and the true density was measured by helium pycnometry (Micromeritics, Accupyc 1330). Scanning electron microscopy (SEM) observation was carried out with a Philips XL30 FEG microscope.

Results

Copper deposition

The contents of copper in the uncalcined and calcined solid products are reported in Figure 1. For the samples prepared by IE, the contents of copper analyzed by ICP-AES technique were of 1.43 and 2.22 wt.% for CaP-IE-2-DRY and CaP-IE-20-DRY samples, respectively. Those of the corresponding calcined samples, CaP-IE-2-CAL and CaP-IE-20-CAL, were nearly similar, indicating that no mass change occurred during the calcination step. These results suggested that the ionic exchange (IE) between copper(II) and Ca(II) might approach the equilibrium and this method did not allow the deposition of higher contents of copper on CaP-ini. Similar results were found by Jemal et al. [START_REF] Jemal | NO reduction with NH 3 under oxidizing atmosphere on copper loaded hydroxyapatite[END_REF] for Ca-HA synthesized from soluble reactants ((NH 4 ) 2 HPO 4 and Ca(NO 3 ) 2 ), with copper dosages of 0-2.98 wt.%.

For the solid samples prepared by IWI, the copper contents were of 1.55 and 8.89 wt.% for the uncalcined samples (CaP-IWI-2-DRY and CaP-IWI-20-DRY), respectively, and 2.04 and 13.48 wt.% for calcined samples (CaP-IWI-2-CAL and CaP-IWI-20-CAL), respectively. So, larger amounts of copper could be deposited by this way on the CaP-ini support. The change in the content of copper after calcination step is discussed in Section 3.3 (thermal analysis).

XRD

Figure 2 shows the XRD patterns of CaP-ini and the samples prepared by IE. CaP-ini, which was previously calcined at 400 °C, showed only diffraction peaks of the remaining calcium carbonate and poorly crystallized Ca-HA. For both uncalcined and calcined IE samples, no significant changes could be observed in comparison with the pattern of CaP-ini, despite the deposition of copper of 1.43-2.22 wt.%. This deposition did not lead to detectable changes in the apatitic structure due to poor resolution of the d-spacings in low crystallinity solids. The content of copper-doped Ca-HA could be also insufficient to be observed by XRD analysis. Similar results were observed by Jemal et al. [START_REF] Jemal | NO reduction with NH 3 under oxidizing atmosphere on copper loaded hydroxyapatite[END_REF].

XRD patterns of CaP-ini and samples prepared by IWI are presented in Figure 3. Both CaP-IWI-2-DRY and CaP-IWI-2-CAL samples had similar XRD patterns in comparison to that of CaP-ini. Only the remaining calcium carbonate and poorly crystallized Ca-HA were detected in these samples. This suggested that for the deposition of a theoretical content of copper of 2 wt.% by IWI, a cationic exchange might have taken place which led to the replacement of calcium(II) by copper(II). Consequently, copper(II) cations were inserted in the apatitic structure of Ca-HA and therefore were not transformed into other copper compounds under air calcinations, as observed for the samples prepared by IE method (Figure 2).

The change was distinct for CaP-IWI-20-DRY and CaP-IWI-20-CAL samples. Firstly, only trace amounts of the remaining calcium carbonate were observed. This indicated that the contact of CaP-ini with concentrated copper nitrate solution (initial pH of 2.1) led to the dissolution of calcium carbonate by acid attack, as observed previously. [START_REF] Pham Minh | Apatitic calcium phosphates: synthesis, characterization and reactivity in the removal of lead(II) from aqueous solution[END_REF] Secondly, copper(II) hydroxynitrate (Cu 2 (OH) 3 NO 3 ) was found as the principal crystalline phase of deposited copper in CaP-IWI-20-DRY. This phase was formed by the thermal decomposition of copper nitrate under air drying at 105 °C. [START_REF] Morozov | Thermal decomposition of Cu(NO 3 ) 2 •3H 2 O at reduced pressures[END_REF] The calcination under air atmosphere at 400 °C led to the transformation of copper(II) hydroxynitrate into tenorite (CuO). [START_REF] Morozov | Thermal decomposition of Cu(NO 3 ) 2 •3H 2 O at reduced pressures[END_REF] Finally, Ca-HA was the principal calcium phosphate found in these samples.

Thermogravimetry analysis

Thermal behavior of the solid products was investigated using TG. Figure 4 shows the derivative thermogravimetry (DTG) curves of the copper-doped samples, in comparison with that of the initial support (CaP-ini). All samples prepared by IE (Figure 4(A) and (C)) showed similar DTG curves compared to that of CaP-ini. In fact, in the temperature range of 25-400 °C, there was only a slight weight loss at about 100 °C, which corresponded to the removal of surface moisture. This explained that the calcination at 400 °C had no effect on CaP-IE-2-DRY, as observed in XRD analysis. The next slight weight loss at 400-470 °C was attributed to the dehydration of dicalcium phosphate anhydrous (DCPA, CaHPO 4 ) to form calcium pyrophosphate (Ca 2 P 2 O 7 ). [START_REF] Pham Minh | Synthesis of calcium hydroxyapatite from calcium carbonate and different orthophosphate sources: a comparative study[END_REF] This weight loss was not intense, indicating the presence of small amounts of DCPA. The major weight loss at 600-710 °C corresponded to the decarbonation of the remaining calcium carbonate, present in CaP-ini. [START_REF] Pham Minh | Apatitic calcium phosphates: synthesis, characterization and reactivity in the removal of lead(II) from aqueous solution[END_REF] The last weight loss at 720-820 °C could be attributed to the decarbonation of calcium carbonate apatite (CAP). [START_REF] Pham Minh | Apatitic calcium phosphates: synthesis, characterization and reactivity in the removal of lead(II) from aqueous solution[END_REF] However, the partial replacement of calcium(II) by copper(II) caused a slight displacement in the DTG max (temperature at maximum DTG signals) of this peak from 786 to 754 °C in both cases (Figure 4(A) and (C)).

The thermal behaviors of the samples prepared by IWI method were much more different from each other. For CaP-IWI-2-DRY sample (Figure 4(B)), an intense peak at about 40-90 °C was observed, which must be due to the dehydration of the hydrated copper salts, which was previously impregnated on CaP-ini support. [START_REF] Morozov | Thermal decomposition of Cu(NO 3 ) 2 •3H 2 O at reduced pressures[END_REF] Although the content of aqueous solvent used in the IWI method was low, cationic exchange took place which caused the displacement of DTG max of CAP decarbonation, as observed previously. The remaining calcium carbonate seemed to be stable for this sample meaning that acid attack did not significantly take place. Its intensity decreased in comparison with that of CaP-ini support, because of the deposition of copper salt, which increased the total weight of the solid. A new peak appeared at 300-440 °C which could be attributed to the decomposition of nitrate anions (NO À 3 ). [START_REF] Ghose | Studies on the thermal decomposition of Cu(NO 3 ) 2 •3H 2 O[END_REF] In fact, IWI led to the deposition of nitrate anions on the surface of CaP-ini and under thermal effect, these anions decomposed into nitrogen dioxide (NO 2 ) and oxygen (O 2 ).

For CaP-IWI-20-DRY sample (Figure 4(B)), the strong DTG signal at 40-90 °C indicated the presence of hydrated copper salts. During acid attack of the concentrated solution of copper nitrate (pH of 2.1), the decarbonation of the remaining calcium carbonate and CAP took place and there were only trace amounts of carbonate left after drying. Three net DTG signals were observed, with DTG max at 222, 395 and 457 °C. They were the characteristic peaks for the thermal decomposition of copper(II) hydroxynitrate (Cu 2 (OH) 3 NO 3 ), [START_REF] Ghose | Studies on the thermal decomposition of Cu(NO 3 ) 2 •3H 2 O[END_REF] which confirmed again the XRD results (Figure 3). This explained also the change in the content of copper before and after calcinations step, observed by ICP-AES analysis in Figure 1.

Figure 4(D) shows the DTG curves of calcined IWI samples. The calcination at 400 °C allowed all dehydration reactions and the decomposition of nitrate and copper salts. Thus, only weak DTG signals of the decarbonation of remaining calcium carbonate and CAP were observed.

FTIR

FTIR spectra of CaP-ini and samples prepared by IE are shown in Figure 5. All spectra were similar to each other, before and after copper deposition and calcination at 400 °C. The asymmetrical stretching (ν 3 ) and bending (ν 4 ) modes of PO 3À 4 were observed at 1088 and 1024, and 598 and 560 cm À1 , respectively. The band at 960 cm À1 was assigned to the PO 3À 4 symmetric stretching mode (ν 1 ). These peaks are characteristics for PO 3À 4 groups present in an apatitic structure. [START_REF] Pham Minh | One-step synthesis of calcium hydroxyapatite from calcium carbonate and orthophosphoric acid under moderate conditions[END_REF] Two peaks at wavenumbers of 1420 and 880 cm À1 were attributed to the remaining calcium carbonate, which had only low intensities, despite its high contents in these samples as observed in Figure 4. In fact, previous study showed that the remaining calcium carbonate was usually covered by calcium phosphate layers [START_REF] Verwilghen | Convenient conversion of calcium carbonate to hydroxyapatite at ambient pressure[END_REF] and therefore was only partially exposed to IR light. Carbonate groups inserted in CAP structure were characterized by the bi-modal peak at 1454/1405 cm À1 , which confirmed the results of TG analysis. This bi-modal peak is characteristic for B-type CAP wherein PO 3À 4 groups were replaced by CO 2À 3 groups. [START_REF] Lafon | Processing of AB-type carbonated hydroxyapatite Ca 10Àx( PO 4 ) 6Àx (CO 3 ) x (OH) 2ÀxÀ2y (CO 3 ) y ceramics with controlled composition[END_REF] Figure 6 shows FTIR spectra of samples prepared by IWI. Uncalcined samples had the stretching of OH À groups around 3500 cm À1 . The shoulder at about 3400 cm À1 and the peak at 1650 cm À1 could be attributed to the stretching and bending modes of molecular water in hydrated copper salts. Classical bands of apatitic PO 3À 4 groups at the wavenumbers of 1088, 1024, 960, 598, 560 cm À1 were also observed for the CaP-IWI-2-DRY sample. In comparison with the CaP-ini support, the CaP-IWI-2-DRY sample had two other peaks at 1417 and 1350 cm À1 , which are attributed to the N-O bond vibration of nitrate groups. [START_REF] Da Cunha | Reaction pathways for reduction of nitrate ions on platinum, rhodium, and platinum-rhodium alloy electrodes[END_REF][START_REF] Chaika | The mechanism of electroreduction of nitrate ions on a hybrid electrode nanodispersed copper-MK-40 membrane[END_REF] On the other hand, the IR spectrum of CaP-IWI-20-DRY was completely different from those of CaP-ini and CaP-IWI-2-DRY. With high content of copper nitrate salts, it was possible that the initial calcium phosphate particles of CaP-ini support were covered by copper nitrate layers. Thus, different bands (1417, 1350, 1026 cm À1 ) of copper(II) hydroxynitrate could be observed, [START_REF] Niu | A new route to copper nitrate hydroxide microcrystals[END_REF] which was in good agreement with XRD results. The band at 1026 cm À1 illustrated the bending vibration of Cu-O-H and those at 1417 and 1350 cm À1 corresponded to nitrate groups.

For calcined IWI samples, copper(II) hydroxynitrate was decomposed into copper oxide (Figure 3). Thus, apatitic calcium phosphates, remaining calcium carbonate and copper oxide were the main components of these samples. Their IR spectra were similar to that of CaP-ini. Bands of HO À , PO 3À 4 and CO 2À 3 groups, present in Ca-HA, CAP and remaining calcium carbonate, were observed and correspond to those already discussed above. Copper oxide did not show IR bands, as expected for metal oxides.

Specific surface area (S BET ), true density, and SEM analyses

The specific surface area (S BET ) and true density (d) of the solids before and after copper deposition are reported in Table 1. For IE samples, the addition of copper to CaP-ini support did not lead to any notable change of S BET . On the other hand, a slight increase of true density was observed. This change might be due to the substitution of Ca 2+ by Cu 2+ , wherein the atomic weight of copper (63.546) is higher than that of calcium (40.078). For dry IWI samples, strong decrease of both true density and S BET were observed. In fact, adsorption-desorption isotherm showed that CaP-ini support was a porous material with the porous volume equal to 0.25 cm 3 g À1 . We propose that the solidification of large Cu(NO 3 ) 2 •3H 2 O salt deposits led to the clogging of pores, resulting in an inaccessibility to pores, and therefore to the decrease of density and S BET . Following air calcination, the copper precursor was decomposed into copper oxide. This opened and freed the pores of the support which explained the true density and S BET of calcined IWI samples compared to those of uncalcined IWI samples.

To enhance the arguments above for S BET and true density results, SEM observations were performed for all solid products and some results are illustrated in Figure 7. CaP-ini support had particle sizes varying in wide range from 100 nm to 100 μm (Figure 7(A2)). At higher magnification (Figure 7(A1)), the surface of particles seemed to be compact and particles of sheet-like structure could be observed which are usually attributed to dicalcium phosphate dihydrate (DCPD, CaHPO 4 •2H 2 O) and dicalcium phosphate anhydrate (DCPA, CaHPO 4 ). [START_REF] Pham Minh | Synthesis of calcium hydroxyapatite from calcium carbonate and different orthophosphate sources: a comparative study[END_REF] Similar results were obtained for the solid products synthesized by IE or by IWI with the theoretical value of copper content of 2 wt.%. Therefore, these results were not illustrated. Distinct changes were observed for CaP-IWI-20-DRY (Figure 7(B1) and (B2)) and CaP-IWI-20-CAL (Figure 7(C1) and (C2)) samples. There was no notable change in particle sizes before and after calcination (Figure 7(B1) and (B2), respectively) compared to CaP-ini support (Figure 7(A1)). However, layers of copper precursor could be clearly observed for the uncalcined sample (B1). After calcination, particles of copper oxide could be also easily observed which had strong contrast (arrows).

TMA analysis

Catalytic processes using Ca-HA and metal-loaded Ca-HA are usually performed at high temperature. For example, water gas shift reaction was carried out using Au-and Ru-loaded Ca-HA at 100-400 °C. [START_REF] Venugopal | Hydroxyapatite as a novel support for gold and ruthenium catalysts: behaviour in the water gas shift reaction[END_REF] Oxidative coupling of methane was performed on a lead containing Ca-HA at 650-800 °C. [START_REF] Park | Preparation of Pb-substituted hydroxyapatite catalyst and use in oxidative coupling of methane[END_REF] The reaction temperature is well known as an important parameter for the activity and selectivity of a catalyst. Knowledge of the thermomechanical behavior of Ca-HA based materials helps to better understand and design the appropriate catalytic reactor, and therefore to anticipate the effective use of Ca-HA-based materials in high temperature catalytic processes.

Figure 8 shows the TMA curves of CaP-ini support and copper-loaded Ca-HA with the theoretical value of copper content of 20 wt.%. Below 550 °C, the shrinkage was nearly negligible for all samples, except a small shrinkage of À1% at about 110-180 °C for CaP-IWI-20-DRY sample. This must be due to the dehydration of copper precursor present in this sample. CaP-ini support and two samples prepared by IE (Figure 8(A)) had a small dilatation (<1.6%) between 550 and 830 °C. Then, strong shrinkages took place during the temperature rise from 830 to 1000 °C and the isothermal time at 1000 °C. After the isothermal time of 60 min at 1000 °C, shrinkage of À9.8% was observed for CaP-ini. CaP-IE-20-DRY and CaP-IE-20-CAL samples showed higher shrinkages, which were of 18.8 and 21.3%, respectively (Figure 8(A)). CaP-IWI-20-DRY and CaP-IWI-20-CAL samples had no dilatation in the temperatures range of 550-830 °C and their shrinkages were similar to that of CaP-ini support at the temperature higher than 830 °C (Figure 8(B)).

Generally, thermal shrinkage is due to chemical reactions resulting in the formation of gas products or denser solid components and to the sintering phenomenon. [START_REF] Pham Minh | Thermal behavior of apatitic calcium phosphates synthesized from calcium carbonate and orthophosphoric acid or potassium dihydrogen orthophosphate[END_REF] Figure 8(A) highlighted that the insertion of copper(II) in the apatitic structure of CaP-ini enhanced the thermal shrinkage. A reorganization of copper(II)-containing Ca-HA might take place to form denser solid phases, and/or the presence of copper(II) might promote the sintering of calcium phosphates present in CaP-ini. Supplementary characterizations are needed to better understand the role of copper(II) in this case. On the other hand, the deposition of copper oxide particles (CuO) on the surface of CaP-ini had no notable influence on its thermal shrinkage in the temperature range used.

Conclusions

Copper-loaded apatitic calcium phosphate was synthesized using IE and IWI methods. In the samples prepared by IE, copper(II) replaced calcium(II) leading to the displacement of the thermal decomposition of carbonate-containing apatite (CAP) to lower temperatures. For the exchange conditions used, the content of copper-loaded by IE method seemed to be limited at about 2.2 wt.% despite a higher quantity of copper cations available for the exchange (theoretical value of 20 wt.%). The air calcination at 400 °C seemed to have no effect on the state and structure of components of IE samples.

The deposition of copper by IWI led to the formation of different solid products as a function of the quantity of copper precursor. For a theoretical value of 2 wt.% of copper loading, IE took place and seemed to be more important compared to the deposition of copper precursor molecules, which is expected for this method of preparation. Thus, XRD characterization of the corresponding calcined product did not show the presence of copper oxide. SEM observation did not also reveal the presence of copper oxide particles for this calcined sample. When higher copper content was loaded (theoretical value of 20 wt.%), the deposition of copper precursor salts dominated and copper oxide resulted in the corresponding calcined product.

TMA of the solid products was also performed. The deposition of copper oxide particles did not lead to the notable change of thermal shrinkage compared to the initial support. On the other hand, the insertion of copper(II) into the apatitic structure of the initial support accelerated the thermal shrinkage. These results will be considered for our future works on the use of copper-loaded apatitic calcium phosphates in high temperature catalytic processes, in particular the thermo-conversion of methane and carbon dioxide.

Figure 1 .

 1 Figure 1. Copper contents of the solid products obtained by ICP-AES analysis.

Figure 2 .

 2 Figure 2. XRD patterns of samples prepared by IE; (▪) calcite (CaCO 3 ); ( ⁄ ) calcium hydroxyapatite (Ca 10 (PO 4 ) 6 (OH) 2 ).

Figure 3 .

 3 Figure 3. XRD patterns of samples prepared by IWI; (▪) calcite (CaCO 3 ); ( ⁄ ) calcium hydroxyapatite (Ca 10 (PO 4 ) 6 (OH) 2 ); (I) copper(II) hydroxynitrate (Cu 2 (OH) 3 NO 3 ); () tenorite (CuO).

Figure 4 .

 4 Figure 4. DTG curves of calcined (A and B) and uncalcined (C and D) samples, in comparison with that of CaP-ini.

Figure 5 .

 5 Figure 5. IR spectra of the initial support (CaP-ini) and samples prepared by IE.

Figure 6 .

 6 Figure 6. FTIR spectra of the initial support (CaP-ini) and samples prepared by IWI.

Figure 7 .

 7 Figure 7. SEM images of CaP-ini support (A1, A2), CaP-IWI-20-DRY (B1, B2), and CaP-IWI-20-CAL (C1, C2) samples.

Figure 8 .

 8 Figure 8. TMA analysis of IE (A) and IWI (B) samples prepared at the theoretical copper content of 20 wt.%, compared to that of the initial support (CaP-ini). Thermal shrinkage is defined as (L -L o )/L o or ΔL/L o , where L o is the initial length of sample and L is the length of sample measured at temperature T or time t.

Table 1 .

 1 Specific surface area (S BET ) and true density (d) of the solids prepared by IE and IWI.

	Solid	S BET /m 2 g À1	d/g cm À3
	CaP-ini	29	2.820
	CaP-IE-2-DRY	33	3.016
	CaP-IE-2-CAL	31	3.021
	CaP-IE-20-DRY	33	3.010
	CaP-IE-20-CAL	33	3.060
	CaP-IWI-2-DRY	27	2.223
	CaP-IWI-2-CAL	31	3.069
	CaP-IWI-20-DRY	9	2.041
	CaP-IWI-20-CAL	23	3.449

Acknowledgments

The authors thank gratefully their colleagues at the RAPSODEE center, Christine Rolland, Nathalie Lyczko, for their technical help.


Imen Mahjri

Amine Dhraief

Abdelfettah Belghith

Khalil Drira

Hassan Mathkour

A GPS-less Framework for Localization and Coverage Maintenance in Wireless Sensor Networks

Keywords: WSNs, integrated localization and sensing coverage, GPS, transmission range

Sensing coverage is a fundamental issue for Wireless Sensor Networks (WSNs). Several coverage configuration protocols have been developed; most of them presume the availability of precise knowledge about each node location via GPS receivers. However, equipping each sensor node with a GPS is very expensive in terms of both energy and cost. On the other hand, several GPS-less localization algorithms that aim at obtaining nodes locations with a low cost have been proposed. Although their deep correlation, sensing coverage and localization have long been treated separately. In this paper, we analyze, design and evaluate a novel integrated framework providing both localization and coverage guarantees for WSNs. We integrate the well known Coverage Configuration Protocol CCP with an improved version of the localization algorithm AT-Dist. We enhanced the original specification of AT-Dist in order to guarantee the necessary localization accuracy required by CCP. In our proposed framework, a few number of nodes are assumed to know their exact positions and dynamically vary their transmission ranges. The remaining sensors positions are derived, as accurately as possible, using this little initial location information. All nodes positions (exact and derived) are then used as an input for the coverage module. Extensive simulation results show that, even with a very low anchors density, our proposal reaches the same performance and efficiency as the ideal CCP based on complete and precise knowledge of sensors coordinates.

Introduction

Wireless sensor networks (WSNs) are an active research and commercial area of interest [START_REF] Misra | Guide to wireless sensor networks[END_REF]. A WSN usually consists of a large number of small, low-cost sensor nodes that cooperate with each other to monitor the physical word. Applications of wireless sensor networks are virtually limitless. They include among others, industrial control and monitoring, target tracking and surveillance, home automation and health care. This diversity of applications and domains gives rise to many important issues and requirements that need to be effectively treated during the design of WSN protocols. Sensing coverage and localization are two of the most fundamental and challenging problems in wireless sensor networks.

Sensing coverage reflects how well a sensor network is able to monitor or track a given field of interest. It is considered as one of the most critical measures of performance or service quality offered by a WSN [START_REF] Zhou | Multiobjective coverage control strategy for energy-efficient wireless sensor networks[END_REF]. So far, several sensing coverage protocols have been proposed [START_REF] Wang | Coverage problems in sensor networks: A survey[END_REF]. Throughout the diversity of research works in this topic, major interests focused purely on the coverage problem under the restrictive assumption that each deployed node is equipped with a GPS receiver that provides it with its precise location. However, in a real life situation, adding a GPS receiver to each deployed node is infeasible and nonpractical for several reasons. First, in a dense network with a large number of nodes, the manufacturing cost of GPS modules is very significant. Moreover, the size of a GPS receiver may be very large for many applications using extremely small sensor devises. Lastly, the power consumption caused by the GPS receiver impact severly the battery lifetime, which is inherently contradictory to the nature of sensor nodes. An alternative solution to GPS is consequently highly needed.

In the meanwhile, several localization algorithms have been proposed to enable sensor nodes to autonomously determine their positions without relying on GPS capabilities [START_REF] Biaz | A survey and comparison on localisation algorithms for wireless ad hoc networks[END_REF]. Such algorithms enable sensor nodes to estimate their positions with some degree of precision. Typically, a small number of nodes, called anchors, know their own locations by either human intervention or GPS devices. The remaining majority of nodes, called unknowns, ignore their positions. Based on anchor nodes information, localization algorithms attempt to derive the locations of as many unknown nodes as possible.

In spite of the tight relation between them, sensing coverage and localization protocols have been discussed and evaluated separately. In this paper, we present the design and analysis of a novel framework which treats both sensing coverage and localization in a synchronized way. With this integration, the sensing coverage algorithm will no longer depend on GPS services. We particularly choose to integrate the well-known coverage maintenance protocol CCP [START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF] with an improved version of the localization algorithm AT-Dist [START_REF] Saad | At-dist: A distributed method for localization with high accuracy in sensor networks[END_REF]. The original specification of AT-Dist is modified in order to guarantee the necessary localization accuracy required by CCP. Notably, we assume that anchor nodes are able to dynamically increase their transmission range in order to ameliorate positions estimation.

The remainder of the paper is structured as follows. Section 2 reviews related works on sensing coverage and localization in wireless sensor networks. Section 3 gives a detailed description of the Coverage Configuration Protocol CCP and presents some recommendations on how to appropriately set its different parameters. Section 4 explains the Distance Based Approximation Technique AT-Dist. Section 5 describes and studies the performance of the enhanced version of AT-Dist, describes the proposed framework, studies its performance, discusses its potential security threats and shows how to deal with them. Section 6 concludes the paper.

Related Works

In the following section, we first detail the sensing coverage strategies in wireless sensors networks. Then, we give an overview of localization algorithms.

Sensing Coverage

Sensing coverage quantifies how well an area of interest is covered by the deployment of a given sensor network. In the literature, the coverage problem has been formulated in various ways. A location in an area A is said to be covered by a sensor si if it is within the sensing range of si. A location in A is said to be k-covered if it is covered by at least k (k ≥ 1) sensors. Depending on the coverage objectives and applications, coverage techniques can be classified into three types: point (target) coverage, barrier coverage, and area coverage.

Point Coverage

In the point coverage problem, the objective is to cover a set of discrete points (targets). This type of coverage is mainly used in military applications. In a friendly and an accessible environment, a set of sensor nodes can be deterministically placed to cover the target points. In this way, the objective of a deterministic node placement is to find the minimum number of sensors to be deployed and determine their locations such that the envisioned target points are covered. Several works have focused on the planning of sensor positioning [START_REF] Altınel | Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks[END_REF][START_REF] Kar | Node placement for connected coverage in sensor networks[END_REF][START_REF] Wang | Efficient point coverage in wireless sensor networks[END_REF]. [START_REF] Kar | Node placement for connected coverage in sensor networks[END_REF] proposed a spanning tree-based algorithm that calculates the optimal nodes placement while maintaining the connectivity of the deployed sensors. First, the algorithm constructs the spanning tree over the set of targets, and then consecutively chooses sensors' locations on the tree (the vertices or along the edges) that guarantees both coverage and connectivity at each step. In [START_REF] Altınel | Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks[END_REF][START_REF] Wang | Efficient point coverage in wireless sensor networks[END_REF], optimization techniques are used to model and solve the node placement problem. In a harsh and a hard-access environment, the only way to deploy a sensor network is through randomly scattering a large number of sensor nodes. For example sensors can be dropped from a plane. In such a deployment, a target point may be unnecessarily covered by more than one single sensor node. In order to reduce the energy consumption and consequently the sensor network lifetime, it would be interesting to switch off the unnecessary nodes. The sensors can be divided into a collection of disjoint sets such that every set can satisfy the coverage requirement. These sets are then successively activated one by one. The objective of this approach is to maximize the number of disjoint sets. [START_REF] Cardei | Improving wireless sensor network lifetime through power aware organization[END_REF] presented a theoretical analysis for this approach and then proposed a heuristic for the disjoint set covers computation based on a mixed integer programming formulation.

Barrier Coverage

The concept of barrier coverage was firstly discussed by [START_REF] Gage | Command control for many-robot systems[END_REF] in the context of robotic sensors. The objective of barrier coverage is to minimize the probability of undetected penetrations across the sensor field. In [START_REF] Huang | Coverage and exposure paths in wireless sensor networks[END_REF][START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF][START_REF] Mehta | Optimal coverage paths in ad-hoc sensor networks[END_REF], the problem of finding penetration paths is studied. A penetration path is a trajectory spanning from one side to the opposite side of the sensor field. For example, given a deployed network, a defender needs to recognize the path along which an intruder may not be detected and take its appropriate measures. In [START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF], based on computational geometry and Voronoi diagrams, the authors proposed polynomial algorithms to find the maximal breach path and the maximal support path. On the maximal breach path the chance of detecting an intruder is minimized, however on the maximal support path the chance of detecting an intruder is maximized. In [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF][START_REF] Liu | Strong barrier coverage of wireless sensor networks[END_REF][START_REF] Balister | Reliable density estimates for coverage and connectivity in thin strips of finite length[END_REF], the authors studied the concept of k-barrier coverage of a belt region. A belt region is k-barrier covered if any crossing path intersects with the sensing areas of at least k distinct sensors. [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF] proposed an efficient algorithm that determines whether a region is k-barrier covered and established a deterministic deployment pattern to achieve k-barrier coverage. [START_REF] Balister | Reliable density estimates for coverage and connectivity in thin strips of finite length[END_REF] introduced new techniques to derive reliable density estimates for achieving barrier coverage.

Area Coverage

The most studied coverage problem is the area coverage problem where the whole area of interest has to be covered. Several works have focused on the area coverage problem. [START_REF] Bai | Low-connectivity and full-coverage three dimensional wireless sensor networks[END_REF][START_REF] Franceschetti | A geometric theorem for wireless network design optimization[END_REF] addressed the problem of determining the critical sensor density for complete area coverage. The critical sensor density gives an estimation of the minimum number of sensors required to achieve the coverage of the entire region. [START_REF] Franceschetti | A geometric theorem for wireless network design optimization[END_REF] presented a grid strategy to find the number of disks required to cover a given area. [START_REF] Bai | Low-connectivity and full-coverage three dimensional wireless sensor networks[END_REF] designed a set of optimal placement patterns to achieve both coverage and connectivity in 3D sensor networks. Other works addressed the sensor activity scheduling problem [START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF][START_REF] Slijepcevic | Power efficient organization of wireless sensor networks[END_REF][START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF][START_REF] Zhang | Maintaining sensing coverage and connectivity in large sensor networks[END_REF]. In random sensor deployments, the number of deployed nodes is much higher than needed. An energy efficient mechanism in such a redundant deployment is to schedule the activation and deactivation of sensor nodes, allowing redundant node to sleep as long as possible. In [START_REF] Slijepcevic | Power efficient organization of wireless sensor networks[END_REF], the authors proposed to divide the sensors into disjoint sets, such that every set fully covers the monitored area, and then successively activated these sets. The authors of [START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF][START_REF] Tian | A coverage-preserving node scheduling scheme for large wireless sensor networks[END_REF][START_REF] Zhang | Maintaining sensing coverage and connectivity in large sensor networks[END_REF] proposed distributed and localized node scheduling algorithms. In such algorithms each node decides upon its state based on its neighbours states and locations. Although the three aforementioned coverage strategies have different objectives (covering a point, a hole area or a path), they all make the same assumptions on the available information about the sensor network. They mainly assume that sensor nodes have their exact geographic location information through on board GPS receivers. The positions of sensor nodes are consequently a basic input for sensing coverage algorithms.

Localization Techniques

The assumption that all the deployed nodes are provided with GPS supplying them with their exact locations, is often unwarranted. Instead, localization techniques may be used to discover nodes positions. In localization algorithms, a few number of anchor nodes are generally assumed to know their own coordinates (through manual configuration or GPS for instance) and other nodes' coordinates are derived based on these anchor nodes and some particular node localization techniques. Based on their computational organization and the information required for the positions estimation, localization algorithms can be classified into two ways: centralized vs. distributed or range-based vs. range-free.

Centralized vs. Distributed Localization

Centralized localization algorithms are designed to run on a sufficiently powerful central base station. First, the base station collects the environmental information from the different sensor nodes. Then, based on the collected information, it computes the position of each sensor node and feed them back to respective nodes. Centralized algorithms eliminate the problem of nodes' computational limitations; whereas they introduce a large communication cost due to transporting data to and from the base station. Hence, centralized algorithms are only suitable for small networks. The Multidimensional Scaling-MAP (MDS-MAP) [START_REF] Shang | Localization from mere connectivity[END_REF] and the Semi-Definite Programming (SDP) [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF] are two popular centralized localization algorithms. In contrast, distributed algorithms are designed to run on each node. Sensor nodes use inter-nodes communications to get their positions in the network. Due to the lack of global information, distributed localization is usually less accurate than the centralized one but it considerably reduces communication costs. The Approximate Point in Triangulation (APIT) [START_REF] Niculescu | Ad hoc positioning system (aps)[END_REF] and the Distance Vector Hop (DV-Hop) [START_REF] He | Range-free localization schemes for large scale sensor networks[END_REF] are representative proposals in this category.

Range-based vs. Range-free Localization

Range-based algorithms use internodes distances or angles to estimate nodes' positions. They use special measurements such as the time of arrival (TOA) [START_REF] Parkinson | Progress In Astronautics and Aeronautics: Global Positioning System: Theory and Applications[END_REF], the angle of arrival (AOA) [START_REF] Niculescu | Ad hoc positioning system (aps) using aoa[END_REF] and the received signal strength (RSS) [START_REF] Parkinson | Progress In Astronautics and Aeronautics: Global Positioning System: Theory and Applications[END_REF] to calculate the distance or angle separating two sensors. RSS-based techniques depend on the fact that the radio signal strength attenuates with distance. With the radio attenuation information, a receiving node is able to calculate its distance to the transmitting node. In the TOA-based ranging techniques, the distance separating a receiver from a sender is calculated through multiplying the propagation time by the speed of the signal. AOA-based techniques typically rely on the use of radio or microphone arrays to estimate the angle separating the receiver from the transmitter. The Ad Hoc Positioning System using Angle of Arrival (APS-AOA) [START_REF] Niculescu | Ad hoc positioning system (aps) using aoa[END_REF] and the Distance based Approximation Technique (AT-Dist) [START_REF] Saad | At-dist: A distributed method for localization with high accuracy in sensor networks[END_REF] are examples of range-based localization algorithms. Range-free localization algorithms make no assumption about the availability of inter-nodes distances or angles to estimate locations. They instead rely on topology and connectivity information assuming an isotropic network where the hop count between nodes is proportional to their distance. The Centroid [START_REF] Bulusu | Gps-less low-cost outdoor localization for very small devices[END_REF] and the Convex Position Estimation (CPE) algorithm [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF] are examples of range-free localization algorithms. Because of the absence of range information, the positions estimations obtained by the rangefree algorithms are usually less accurate than those obtained by the range-based algorithms. However, on the other hand, range-based techniques are generally more complex.

The Coverage Configuration Protocol

The Coverage Configuration Protocol CCP is a distributed area coverage protocol for dense wireless sensor networks [START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF]. It achieves energy conservation by scheduling redundant nodes to sleep while still preserving the sensing coverage of the entire monitored area. In this section, we give a detailed description of CCP. We first present the K-coverage eligibility algorithm. This algorithm allows a sensor node to autonomously evaluate its eligibility to be in the active state. Then, we describe the state transition of CCP. We finally analyze the impact of the different CCP timers on the algorithm performance and give some recommendations on how to set them appropriately.

The K-Coverage Eligibility Algorithm

The K-coverage eligibility algorithm is the algorithm that enables a node to decide upon its state: ACTIVE or SLEEP. Given a requested coverage degree K, a node can be in the SLEEP mode if every location within its coverage range is already K-covered by its neighbouring active nodes. For example, in Fig. 1, for K=1, the node S4 can be in the SLEEP mode since its sensing zone is already 1-covered by the active nodes S1, S2 and S3. In [START_REF] Xing | Integrated coverage and connectivity configuration for energy conservation in sensor networks[END_REF] the authors have proved the following theorem:

Theorem 1: A convex region A is K-covered by a set of nodes if [START_REF] Misra | Guide to wireless sensor networks[END_REF] it contains intersection points between nodes sensing circles or between nodes sensing circles and A's boundary;(2) all these intersection points are at least K-covered.

Theorem 1 enables the transformation of the problem of determining the coverage degree of a hole region to the easier problem of determining the coverage degrees of the intersection points within this same region. A sensor is consequently ineligible to turn active if all the intersection points inside its sensing circle are at least K-covered. In Fig. 1, for K=1, node S4 is ineligible to be in the ACTIVE mode because all the intersection points inside its sensing zone are already 1-covered by the other active nodes in its neighbourhood: the intersection point I23 is covered by the active sensor S1, the intersection point I13 is covered by the active sensor S2 and the intersection point I12 is covered by the active sensor S3. In order to find all the intersection points inside its sensing range and check its eligibility, each sensor node needs the location information about all its active sensing neighbours. Therefore, each active node periodically broadcasts messages including its location information.

The CCP State Machine

Nodes running CCP have mainly three operation states: ACTIVE, SLEEP and LISTEN. Each node uses the K-coverage eligibility algorithm to determine its eligibility and dynamically switches its state when its eligibility changes. All nodes are initially in the ACTIVE state. An active node periodically advertises its location and evaluates its eligibility. When a zone exceeds the required coverage degree due to a high density, redundant active nodes will find themselves ineligible and turn into the SLEEP state. A sleeping node periodically wakes up and enters the LISTEN state. During the LISTEN state, a node collects information about its sensing neighbours, re-evaluates its eligibility and decides whether to return to SLEEP mode or to turn into the ACTIVE state. Over time, some nodes may die and create coverage voids. In this situation, some neighbouring nodes in the SLEEP state will find themselves eligible and turn into the ACTIVE mode to cover these voids. As these decisions are done in a distributed way, there could be incompatible state transitions in the neighbourhood. For example, several nodes in the LISTEN state may simultaneously decide to become ACTIVE to cover the same void leading to an unnecessarily redundant coverage. Moreover, several neighbouring active nodes may simultaneously decide to switch to the SLEEP state. In this case, each node will mistakenly believe that its neighbours are still active covering its sensing zone. The coverage degree will consequently decrease below the required level. Two intermediate states JOIN and WITHDRAW are considered to prevent simultaneous transitions from LISTEN to ACTIVE and from ACTIVE to SLEEP, respectively. We describe in the following the detailed state transition rules. Fig. 2

CCP Timers

The choice of the values of the timers Tw, Tj , Tl, Ts and Th significantly influences the performance of CCP. In the following, we detail the impact of these timers on CCP.

 Withdraw timer (Tw) and join timer (Tj): the withdraw timer and the join timer should be both randomized in order to avoid contention between several nodes deciding to join or withdraw. Each node randomly and uniformly chooses these timers from the interval [0, max w T ] and [0,  Listen timer (Tl ): the listen timer should be long enough to collect messages from neighbouring nodes. Among messages, HELLO messages are the most crucial for the K-coverage eligibility algorithm execution. Tl should consequently be set as, Tl=c × Th, where c ≥ 1 is a constant.

 Sleep timer (Ts): with a large sleep timer, coverage voids may appear in the network. These voids can't be promptly covered due to the extended hibernation of nodes. However, a long sleep timer would conserve nodes energy and consequently increase the network lifetime. With a short sleep timer, the network topology can be very dynamic which may disturb nodes from providing application requirements. Moreover, a shorter sleep duration induces less energy conservation.

 Hello timer (Th): the hello timer affects CCP execution time. A short hello timer enables nodes to rapidly collect neighbours information and decide upon their states. However, a short hello timer means a frequent HELLO messages broadcasting and consequently a high communication overhead.

The Distance Based Approximation Technique

The Distance Based Approximation Technique AT-Dist is a distributed, distance based localization algorithm. AT-Dist assumes that all sensor nodes have an identical transmission range R and that each node is able to compute its distances to its neighbours when it receives signals. Nodes running AT-Dist first use the distance estimation technique Sum-Dist to estimate distances to anchors and then approximate their positions using this distance information. In this section we give a detailed description of AT-Dist.

Sum-Dist

In Sum-Dist every anchor broadcasts a message including its identity, coordinates, and a path length set to zero. Each receiving node calculates the range from the sender (via RSS or TOA), adds it to the path length and broadcasts the message. Hence, each unknown node in the network can obtain a distance estimation and the position of every anchor. Obviously, only the shortest distance will be conserved. If i1,i2,• • •, in are the intermediate nodes from the anchor a to the unknown node u, then the estimated distance au d ˆ between a and u is:

u i i i ai au n d d d d     ... ˆ2 1 1 (1)
Where d ˆ represents the estimated distance returned by Sum-Dist. For example, in Fig. 3

Positions Estimation

For each anchor a, an unknown node u draws one or two circles:

 If u and a are neighbours, then u deduces that it is on the circle centred in a and of radius dau.

 If u and a are not neighbours then u deduces that it is not inside the circle centred in a and of radius R. In addition, u knows the estimated distance au d ˆ. Since

  2 2 2 ) ( ) ( ) ( ) ( ) , ( ua a i a i i i u a u d y y x x y x Z              (2)   2 2 2 2 ) ( ) ( ) ( ) ( ) , ( ua a i a i i i u a u d y y x x R y x Z               (3) ) ( ) ( u u u Z Z Z       (4)
An example is displayed in Fig. 4. The unknown node X first uses SumDist to estimate the distances

Integrated Localization and Coverage Configuration

In this section, we first describe and study the performance of a new version of AT-Dist. Unlike the original version of AT-Dist which assumes that all sensor nodes have an identical transmission range R, we consider that anchor nodes have a different transmission range than that of unknown nodes. Then, we present our proposed framework: we describe a simple yet an efficient approach for integrating the new version of AT-Dist with CCP to provide both localization and sensing coverage. After, we study the performance of the proposed framework and compare it with the ideal classical case where all nodes are supposed to be equipped with military GPS receivers providing them with their precise coordinates. We finally discuss the security threats that may affect the proposed framework and show how to deal with them.

AT-Dist With Variable Anchors Range

We propose here to study the performance of AT-Dist under a new specification. Unlike the original specification of AT-Dist [START_REF] Saad | At-dist: A distributed method for localization with high accuracy in sensor networks[END_REF], we consider two different transmission ranges Ra and Ru. Ra is the anchors transmission range and is identical among all anchors. Ru is the unknown nodes transmission range and is identical among all unknowns. Thus, the expression of in Eq(3) becomes:

  2 2 2 2 ) ( ) ( ) ( ) ( ) , ( ua a i a i a i i u a u d y y x x R y x Z               (5)
Our simulations are performed using the OMNET++ simulator. We use a square area of 100m × 100m, where 200 nodes are randomly placed using a uniform distribution. Among nodes, we randomly select α anchors with α varying from 2 to 40 which corresponds to a percentage of anchors varying from 1% to 20% respectively. The unknown nodes transmission range Ru is fixed to 14m. Furthermore, we propose to set the anchors transmission range Ra respectively to 14, 20, 30 and 40m. Each scenario is performed 100 times in order to obtain a small variance.

We consider the following metrics:

 The average localization error: the average localization error is the sum of the localization errors of all nodes divided by the total number of nodes. Localization errors are normalized to the unknown nodes transmission range Ru. For example an error of 0.5 means that a distance of half Ru separates the real and the estimated position.

 The required number of anchors: the required number of anchors is the minimum number of anchors required to reach a given average localization error.

Fig. 5 portrays the average localization error as a function of the anchors used and for different anchor transmission range Ra . There are four curves representing respectively the average localization error when Ra is equal to 14, 20, 30 and 40m. On the horizontal axis we vary the number of anchors α from 2 to 40. This figure shows that, for the same Ra , the average localization error decreases as the number of anchors increases. For example, for Ra=20m, the average localization error is of 0.82Ru in a network containing 6 anchors, it decreases to reach 0.37Ru in a network containing 12 anchors and 0.16Ru in a network containing 24 anchors. This figure also shows that, for the same number of anchors, the average localization error decreases as the anchors transmission range Ra increases. For instance, for a number of anchors equals to 10, the average localization error is of 0.61Ru with Ra=14m and it drops to 0.14Ru with Ra=40m.

Moreover, when comparing two different curves in Fig. 5, for example the curve for Ra=20m and Ra=40m, we notice that increasing the anchors transmission range has a stronger improvement effect on the average localization error than increasing the number of anchors. For Ra=20m and with 16 anchors the average localization error is of 0.25Ru. When doubling the transmission range (i.e., Ra=40m) and dividing the number of anchors by 2 (i.e.,8 anchors), we reach an improved localization error of 0.20Ru . This result is expected because the anchors density

Surface Area R D a a     
, linearly increases with the number of anchors and squarely increases with the transmission range.

It is also interesting to note that after a certain critical density DC, the average localization error is slightly improved. If we consider the results for Ra=40m, we notice that the error rate is barely improved after α=18. Similarly, if we consider the results for Ra=30m, we notice that the average error merely decreases after α=32. The critical density is consequently 0432 . 9 100 100 30 32 100 100

40 18            C D
In Fig. 6, we plot the required number of anchors to reach a certain error bound under different anchors communication ranges (Ra=14, 20, 30 and 40m) and different error bounds (Ω=0.05Ru, 0.1Ru, 0.2Ru and 0.4Ru). As expected, for the same error bound Ω, the required number of anchors decreases as the anchors communication range increases. For example, to reach an average localization error less than or equal to Ω=0.1Ru, we require 48 anchors with a communication range Ra=14m, 35 anchors with a communication range Ra=20m, 31 anchors with a communication range Ra=30m and only 13 anchors with a communication range Ra=40m.

The Framework Description

The proposed framework [START_REF] Mahjri | The Coverage Configuration Protocol under AT-Dist Localization[END_REF] consists in inserting the localization phase just before the scheduling phase. The localization and the scheduling phases are synchronized in a way that active nodes do not participate in the scheduling process until all deployed nodes are well localized. Fig. 7 describes the design of the proposed framework. In the beginning (phase 0), a large number of nodes are randomly dispersed over the area of interest where only a small number of nodes (anchors) are aware of their positions. Then, the localization algorithm is executed (phase 1). At the end of the localization phase, all the deployed sensors are aware of their positions. After that, the scheduling process is applied (phase 2). At the end the scheduling phase, the redundant sensors are set to the sleep mode while the remaining ones stay active to provide a continuous service (phase 3). In static sensor networks, the process periodically turns back to phase 2 and another set of active nodes is chosen. In the case of mobile sensor networks, the process periodically (each Tp) turns back to phase 0 in order to first re-localize sensors and then choose a new set of active nodes. Tp depends on the mobility of the sensor network. In a highly mobile sensor network, Tp should be set to a small value in order to have a fresh and accurate localization. In this paper, we assume that all sensor nodes are static. The proper setting of Tp is left to a future work.  The number of active nodes: the number of active nodes is the number of on-duty nodes that the coverage protocol selects to maintain coverage. The lower the number of on-duty nodes is, the better is the ability of the algorithm to conserve energy and consequently to prolong the network lifetime.

 The coverage ratio: the coverage ratio is the ratio of the covered area to the total monitored area. The coverage is measured as follow: we divide the monitored area into small grids. A grid is considered covered if its centre is covered. The coverage ratio is hence defined as the ratio of the number of covered grids to the total number of grids. A coverage ratio close to 1 indicates the good capacity of the coverage maintenance protocol to preserve the entire area coverage.

 The achieved coverage degree: the achieved coverage degree is the average coverage degree of all grids. The coverage degree of a given grid is the number of active nodes covering it. An achieved coverage degree much larger than the required coverage degree K indicates an unnecessary coverage redundancy.

The number of selected active nodes, the coverage ratio and the achieved coverage degree are recorded after the scheduling process is completed. Next, we study the effects of varying the number of anchors as well as the anchors transmission range Raon these metrics.

In Fig. 8, we plot the number of active nodes that CCP selects to maintain coverage under each of the two localization techniques GPS and ATDist. Three curves are provided. The curve labeled CCP + GPS represents the number of selected active nodes when each deployed node is supposed to be equipped with a GPS. The curves labeled CCP + AT-Dist represent the number of selected active nodes by the proposed framework (when AT-Dist is used to localize nodes). In this case, the number of anchors is varied from 2 to 40. In the curve CCP + AT-Dist (Ra=30m), during the localization phase, anchor nodes increase their transmission range Ra from 14m to 30m in order to ameliorate the positions estimations and then go back to the initial transmission range (i.e., 14m) during the scheduling phase. From this figure, we can see that the use of AT-Dist for localization instead of the GPS leads to an increase in the number of active nodes. This increase is especially observed when AT-Dist uses a small number of anchors. With GPS localization, CCP selects 94 active nodes to maintain the region coverage. With AT-Dist localization, for Ra=30m, CCP selects 135 nodes when 2 anchors are used, that is 40 nodes more than with GPS localization. The number of active nodes decreases continuously to reach 95 with 28 anchors. This figure also shows that the number of active nodes under AT-Dist localization with Ra=14 is greater than that obtained with Ra=30m. The increase in the number of active nodes is therefore due to the localization errors induced by AT-Dist. Indeed, the lower is the number of anchors or the anchors transmission range, the poorer are the localization algorithm position estimations. It is important to notice that for Ra=30m and above α=28, which corresponds to anchors density of 7.9 and an average error of 0.07Ru (Fig. 5), the number of active nodes using AT-Dist localization is almost the same as that obtained using GPS. This means that, under AT-Dist localization and with an average error less or equal to 0.07Ru , CCP selects the same number of active nodes than with GPS localization. This result is consistent with the results obtained in papers [START_REF] Dhraief | A performance evaluation of the coverage configuration protocol under location errors, irregular sensing patterns, and a noisy channel[END_REF] and [START_REF] Dhraief | A performance evaluation of the coverage configuration protocol and its applicability to precision agriculture[END_REF] where it has been proved that, after a certain bound, localization errors lead to an increase in the number of active nodes. 9 plots the coverage ratio provided by CCP under each of the two localization techniques AT-Dist and GPS. From this figure, we notice that CCP is able to provide a good coverage ratio under both AT-Dist and GPS. It keeps a coverage ratio close to 99%. Localization errors have a negligible effect on the coverage ratio. Even with 2 anchors, when the position prediction of AT-Dist is not very precise, the coverage ratio decreases by less than 0.6% in comparison to that obtained by using GPS localization. This result can be explained by the fact that, when CCP uses AT-Dist with a low number of anchors, the number of selected active nodes is more than the necessary (Fig. 8). These redundant active nodes will further cover the monitored area. On the other hand, when CCP uses AT-Dist with an enough high number of anchors, AT-Dist provides sufficiently accurate positions that enable CCP to select the necessary and the exact set of active nodes guaranteeing the monitored area coverage.

Fig. 10 depicts the achieved coverage degree. From this figure, we can see that the achieved coverage degree using AT-Dist is greater than that using the GPS and this degree decreases as the number of anchors α or the anchors transmission range Ra increases. When CCP uses GPS it achieves a coverage degree equals to 2.69, however when it uses AT-Dist with Ra=30m it achieves a coverage degree equals to 3.83 with 2 anchors and 2.72 with 28 anchors. This result conforms to the result obtained in Fig. 8. Indeed, when the number of selected active nodes increases the achieved coverage degree increases accordingly. In summary, the key results of our experiments are (1) The proposed framework performs well in terms of coverage ratio. It guarantees a coverage ratio close to 99% even with a very low anchors density (2) Beyond a density of anchors of 7.9, the proposed framework can select the same necessary and exact set of active nodes as that selected when GPS localization is used. This density can be easily reached either by increasing the number of anchors or idealy by just increasing the anchors transmission during the localization phase.

Security Threats

In our simulations, we have supposed that sensor nodes are deployed in a trusted environment. However, wireless sensor networks are sometimes deployed in harsh and unattended environments, thereby exposing the localization process to several security attacks that may distort the location estimations. An attacker can jam, inject false data and spy on communication. For example, an attacker can erroneously alter the hop counts and the range measurements of the received localization messages or even mimic anchor nodes and broadcast fake locations. In such an untrusted environment, we propose the use of SecAT-Dist [START_REF] Abdelkarim | Secat-dist: A novel secure at-dist localization scheme for wireless sensor networks[END_REF] the secure version of AT-Dist. SecAT-Dist has the same general localization principle than AT-dist. It secures the localization process by using a lightweight security scheme that combines a RC4-based hash function enabling the authentication of the received location messages and a symmetric encryption system protecting the location information from being selfishly and erroneously altered.

Conclusion

Most sensing coverage protocols consider the nodes coordinates as a basic input. Nevertheless, in large sensor networks, straightforward solution of embedding a GPS receiver into each sensor node is not feasible. Coverage algorithms can alternatively rely on localization algorithms. In fact, such algorithms are cost effective, easily to deploy and can operate in various environments.

In this paper, we proposed an integrated localization and area coverage configuration protocol. In sharp contrast to several existing approaches that addressed the two problems separately, we designed a novel framework where we integrated an improved version of the localization algorithm AT-Dist with the coverage maintenance algorithm CCP. With this unification, CCP will no longer rely on GPS to localize sensors. AT-Dist will self-localize the sensor network and supply CCP with the needed location information. To study the efficiency of the proposed framework, we compared it with the ideal classic situation where each networked sensor is equipped with a military GPS providing it with its precise coordinates. Simulation results proved the effectiveness of the framework to provide guaranteed coverage and localization. Indeed, beyond a certain anchors density, the proposed framework reaches the same performance as the ideal case (i.e., each deployed node is aware of its accurate position). To reach this density with a low number of anchors, we proposed to let anchors increase their transmission range during the localization phase and then go back to their initial transmission range during the scheduling phase. Moreover, we addressed the security threats that may encounter the framework in an untrusted environment and proposed the use of a secure version of AT-Dist in order to deal with such threats. Our study indicates that coverage protocols are able to perform very well with the help of even a simple localization algorithm. Localization algorithms can indeed be an excellent and useful alternative to GPS localization. It is consequently appropriate and beneficial to integrate localization and coverage protocols. Integrating these protocols helps to avoid the impracticality and the inaccessibility of the GPS service.

Fig. 1 .

 1 Fig. 1. An example of 1-coverage eligibility

Fig. 2 .

 2 Fig. 2. The coverage configuration protocol state diagram

  represent the maximal values of the withdraw and join timers, have to be set according to the network density. In particular, in dense networks the values of max w T and max j T should be increased to provide nodes with enough time to collect the WITHDRAW or JOIN messages from their crowded neighbourhood.

Fig. 3 .

 3 Fig. 3. Principle of distance estimation in Sum-Dist

  u deduces that it is inside the circle centred in a and of radius au d ˆ.The intersection of these circles provides a zone Zu containing u. The unknown node u estimates its position as the centroid of this zone.If we note:  the set of anchors  non-neighbour anchors for an unknown node u   the set of all possible coordinates in the network For each unknown node u, Zu is obtained as follow:

  d ˆ to the different anchors A, B and C. A, B and C are not neighbours of X, X is consequently not inside circles centered respectively at A, B, C and of radius R but it is inside circles of radius XA d ˆ, XB d ˆ and XC d ˆ. The correlation of these information defines the red hatched area ZX . X estimates its location as the center of gravity of ZX .

Fig. 4 .

 4 Fig. 4. Principle of the localization process in AT-Dis

Fig. 5 .

 5 Fig. 5. Average localization error under different number of anchors α for different anchors transmission ranges Ra

Fig. 6 .

 6 Fig. 6. Required number of anchors under different anchors communication ranges and different error bounds

Fig. 7 .

 7 Fig. 7. Integrated framework for localization and coverage maintenance

Fig. 8 .

 8 Fig. 8. Number of active nodes under the two localization techniques GPS and AT-Dist

Fig.

  Fig.9plots the coverage ratio provided by CCP under each of the two localization techniques AT-Dist and GPS. From this figure, we notice that CCP is able to provide a good coverage ratio under both AT-Dist and GPS. It keeps a coverage ratio close to 99%. Localization errors have a negligible effect on the coverage ratio. Even with 2 anchors, when the position prediction of AT-Dist is not very precise, the coverage ratio decreases by less than 0.6% in comparison to that obtained by using GPS localization. This result can be explained by the fact that, when CCP uses AT-Dist with a low number of anchors, the number of selected active nodes is more than the necessary (Fig.8). These redundant active nodes will further cover the monitored area. On the other hand, when CCP uses AT-Dist with an enough high number of anchors, AT-Dist provides sufficiently accurate positions that enable CCP to select the necessary and the exact set of active nodes guaranteeing the monitored area coverage.Fig.10depicts the achieved coverage degree. From this figure, we can see that the achieved coverage degree using AT-Dist is greater than that using the GPS and this degree decreases as the number of anchors α or the anchors transmission range Ra increases. When CCP uses GPS it achieves a coverage degree equals to 2.69, however when it uses AT-Dist with Ra=30m it achieves a coverage degree equals to 3.83 with 2 anchors and 2.72 with 28 anchors. This result conforms to the result obtained in Fig.8. Indeed, when the number of selected active nodes increases the achieved coverage degree increases accordingly.

Fig. 9 .

 9 Fig. 9. Coverage Ratio under the two localization techniques GPS and AT-Dist

Fig. 10 .

 10 Fig. 10. Coverage degree under the two localization techniques GPS and AT-Dist

  portrays the CCP finite state machine.  ACTIVE State: in the ACTIVE state, the sensor node senses its surrounding environment and transmits information or messages. Moreover, it periodically broadcasts (each Th ) HELLO messages. When the ACTIVE node receives a HELLO or JOIN message, it evaluates its eligibility to remain active. If it is a redundant node, it starts a withdraw timer Tw and moves to the WITHDRAW state.  WITHDRAW State: on receiving a WITHDRAW message, the sensor node evaluates its eligibility. If it is no longer ineligible, it cancels the withdraw timer and goes back to the ACTIVE state. If Tw expires and the sensor node is yet ineligible, it broadcasts a WITHDRAW message, starts a sleep timer Ts and switches the SLEEP state. LISTEN State: on receiving a HELLO, JOIN or WITHDRAW message from a neighbour, the eligibility algorithm is executed. If the node is eligible, it starts a join timer Tj and moves to the JOIN state. Otherwise, on expiration of the listen timer, it sets Ts and goes back to the SLEEP state.  JOIN State: when a HELLO or JOIN message is received, the sensor node evaluates its eligibility. If it becomes ineligible, it cancels the join timer Tj, sets a sleep timer Ts, and goes back to the SLEEP state. If Tj expires and the sensor node is yet eligible, it broadcasts a JOIN message and moves to the ACTIVE state.

 SLEEP State: in the SLEEP state, the node turns off its radio to con serve energy. When the sleep timer expires, the node turns on its radio, starts a listen timer Tl, and switches to the LISTEN state.




Pierre Boutillier
email: pierreboutillier@hms.harvard.edu

Ferdinanda Camporesi
email: camporesi@ens.fr

Jean Coquet
email: coquet.jean@gmail.com

Jérôme Feret
email: feret@ens.fr

Kim Quyên Lý

Nathalie Théret

Pierre Vignet
email: pierre.vignet@inria.fr

Nathalie Theret
email: nathalie.theret@univ-rennes1.fr

KaSa: A Static Analyzer for Kappa

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

PSfrag replacements k PSfrag replacements kp

Introduction

Kappa may be used to describe systems of mechanistic interactions between proteins by the means of site-graph rewriting rules. Each node in graphs denotes an instance of a protein equipped with a kind and a finite set of identified sites. Rules may bind/unbind sites pair-wisely to establish/break links between proteins. Some sites may also have an internal state in order to specify if they are phosphorylated, methylated, and so on, so forth. We give, in Fig. 1, two examples of rules in Kappa. Kappa is context-free: only the information that matters for a given interaction to happen has to be mentioned in rules. This feature is crucial to scale up to the size of large models. Thus Kappa provides the opportunity to design arbitrarily sophisticated models. These models may involve proteins with multiple phosphorylation sites, scaffolds, concurrency for shared resources, different time-and concentration scales, large variabilities in the kinds of molecular compounds, and non-linear feed-back loops. In general, we want to understand how the collective behavior of proteins may emerge from the mechanistic interactions between individual proteins. Yet, there are no modeling wizards and before investigating the long term behavior of a model, it is worth wondering whether the implementation matches faithfully our modeling assumptions. In the case of models written by others, extracting quickly some basic properties about models is also helpful to understand what the models are doing.

This motivates the use of formal methods. KaSa is a static analyzer that abstracts the set of reachable states of models, and then uses this information to collect insightful properties. In particular, KaSa may warn about rules that may never be applied, about potential definitive transformations of proteins and about the potential formation of unbounded molecular compounds. Lastly, KaSa detects the potential influences (activation/inhibition relation) between rules.

In this paper, we illustrate the main features of KaSa on a model of the extracellular activation of the transforming growth factor TGF-b, a protein which controls cell homeostasis in normal tissue, but promotes the development of fibrosis and cancer [START_REF] Horiguchi | Matrix control of transforming growth factor-β function[END_REF]. There has been a nice interplay between the design of the static analysis and the one of this model. On the first hand, KaSa has been helpful to curate the model, on the second hand, we have extended KaSa to cope with new properties of interest that we have identified during the modeling process.

Technical description

Development. The development of KaSa has started in 2006, as a follow up of Complx, a static analyzer that had been designed by Plectix BioSystems (Cambridge, MA, USA). KaSa is now around 68,000 lines of OCaml [START_REF] Leroy | The ocaml system[END_REF] (excluding the front-end). It offers 53 command-line options. Jérôme Feret (2010-present) and Kim Quyên Lý (2015-2017) have been being the main developers.

Distribution. KaSa belongs to the Kappa modeling platform, which is completely open source www.kappalanguage.org. KaSa is partially integrated within the Kappa user interface, In particular, all the functionalities that are described in this paper, but local traces, are available on the fly while editing a model.

The development of the modeling platform is hosted on github https:// github.com/Kappa-Dev/KaSim. An app is provided for MacOs and Windows. The nightly-builds of the development version may be downloaded at https:// tools.kappalanguage.org/nightly-builds/. The modeling platform is also available as an opam package. With a properly installed opam, the instruction opam pin add --dev KaSim will compile all necessary dependencies as well as the current master branch of the git repository.

The manual may be consulted online at: https://tools.kappalanguage. org/docs/KaSim-manual-master/KaSim_manual.htm (see Chp. 6).

Main functionalities

Now we browse the main functionalities of KaSa.

Note that the results computed by KaSa depend all on the choice of the initial state, or more precisely on the set of the proteins and molecular compounds that may be present in the initial state independently of their concentration. KaSa is purely qualitative: its results depend neither on rule rates, nor on initial concentrations.

Reachability analysis. The cornerstone of KaSa is its reachability analysis. KaSa performs a mutual induction over some families of patterns, so as to prove that some of them may never occur in reachable states. Three families of patterns are considered [START_REF] Feret | Reachability analysis via orthogonal sets of patterns[END_REF]. The first one detects relations among the state of sites within each protein instance. The second one targets the relations between the state of sites in the proteins that are directly linked. The third one focuses on detecting whether or not a protein may be bound twice to the same instance of a protein. KaSa outputs a list of refinement lemmas. Each one consists in a precondition, that is a pattern, and a post-condition, that is a list of refinements of this pattern. The formal meaning of a refinement lemma is that whenever an instance of the ] Fig. 2. Two refinement lemmas. (left) When TGFB1 is in its latent form, its site a is necessarily free. (right) When TGFB1 has its two sites bound, it is bound twice to the same instance of the protein THSBS1 . In each of these refinement lemmas, the refinement list is made of a single element. In more complicated cases, there maybe a choice of several patterns for refining the precondition.

precondition is found in a reachable state, this instance may be extended to an instance of a pattern in the post-condition. In Fig. 2, we give some of the properties that are found in our case study. The analysis infers that in its latent form, TGFB1 has always its site a (in pink) free. KaSa also detects that TGFB1 may be bound twice to the same instance of the protein THBS1 , but never to different instances simultaneously.

Dead rule detection.

A rule the left hand side of which is in contradiction with the refinement lemmas cannot be applied whatever the evolution of the system is. There may be various reasons for this. Sometimes, several names have been used to denote the same protein. Sometimes, proteins have structural invariants that prevents the application of a rule. In our case study, dead rules have helped in identifying some missing parts in models, hence blocking the signaling pathways. The model has been completed after having consulted the literature.

Influences among rules. Rules may have a positive or a negative influence on each others. There is a positive (resp. negative) influence when an application of a given rule may potentially create (resp. remove) an instance of the left hand side of another rule. Influences provide an overview of the causality of the model.

We give an example in Fig. 3. We consider a protein with two phosphorylation sites. The left site may be freely phosphorylated and dephosphorylated, whereas the right site may get phosphorylated only when the left one is already phosphorylated. Thus the phosphorylation of the left site has a positive influence on the phosphorylation of the right one, while the dephosphorylation of the left site has a negative influence on the phosphorylation of the right one, as indicated in the influence map. This notion of influence is similar to the one that is used in Gene regulatory tools such as GinSIM [START_REF] Naldi | Logical modelling of regulatory networks with ginsim 2.3[END_REF] or reaction networks tools such as Biocham [START_REF] Fages | From reaction models to influence graphs and back: A theorem[END_REF], except that, in Kappa, influences describe to which extent rules may influence each other, and not whether the variation of concentration of each molecular compound may influence the concentration of the other ones.

Since there are many rules, we use a hierarchy of abstractions to avoid the brute force approach which may not scale to large models. Firstly, we compute indirect influences. Indirect influences focus on the states of sites independently. There is a positive indirect influence whenever a rule may take a site into a state that is required by another rule to apply. Secondly, we compute direct influ- ences. Direct influences are obtained by filtering indirect influences by checking that both rules have compatible requirements about their context of application. Thirdly, we refine direct influences further, by checking that the unifying context of both rules cannot be proved unreachable by our reachability analysis.

Local transition systems. It is sometimes useful to understand how a protein may go from one configuration to another. Thus KaSa computes a transition system for each kind of proteins of the model [START_REF] Feret | Local traces: an over-approximation of the behaviour of the proteins in rule-based models[END_REF]. This abstraction completely ignores the context of the protein: the behavior of each protein is described independently without considering the state of the proteins it is attached to. Local traces do not intend to provide information about the collective behavior of proteins (i. e. their concentration): instead it focus on each protein individually.

Non weakly reversible transitions. Most mechanisms may be reverted in one or more steps of computation. This is crucial so that resources may be used several times (for instance an enzyme is expected to activate several instances of its substrate, thus it has to detach from it). However modelers often see signaling as cascades of interactions that push forward the signal.

Tarjan's strongly connected components decomposition algorithm is useful to detect which computation steps will never be reverted. Often, non weakly reversible transitions come from missing mechanisms and the model has to be completed. Sometimes, they come from a definitive degradation of a protein. In this case, the property is helpful to understand the behavior of this protein.

In the first versions of our case study, most rules about unbinding were missing. Our analysis has detected that corresponding binding steps were definitive and the model had to be completed accordingly. Once this done, all the remaining definitive transitions are related to the activation of the proteins TGFB1 , MMP2 , and MMP14 , which is an irreversible process. In Fig. 4 Detection of unbounded polymers. Knowing which complexes may grow arbitrarily is important. Some models may assemble macro-molecules. But sometimes the presence of unbounded polymers is a side-effect of the lack of specification of the potential conflicts between protein interactions. Unbounded polymers may only arise whenever a sequence of proteins may be repeated indefinitely in a reachable molecular compound. Such a sequence necessarily matches with a cycle in the oriented graph in which nodes are the different kinds of bonds between proteins (each kind bond is considered twice, one for each direction) and the edges connect two (oriented) bonds if the target of the first bond and the source of the second one are two different sites in a same kind of protein. We also use Tarjan's algorithm to detect these cycles.

This feature is available at two accuracy levels. At syntactic level, every kind of bonds occurring in the initial state or in the right hand side of a rule is considered. A more precise analysis is obtained by filtering out the pairs of bonds for which the corresponding pattern is proved unreachable.

In our case study, KaSa detects a large strongly collected component related to the formation of the Fibronectin matrix (which may indeed grow arbitrarily).

Benchmarks

We apply KaSa to several Kappa models (e. g. see Fig. 5). The first eight models are translations in Kappa of some of the models which are provided with the BNGL distribution [START_REF] Blinov | Bionetgen: software for rule-based modeling of signal transduction based on the interactions of molecular domains[END_REF]. The models 'machine' and 'ensemble' are two versions of the MAPK signaling pathways published by Eric Deeds and Ryan Suderman [START_REF] Suderman | Machines vs. ensembles: effective mapk signaling through heterogeneous sets of protein complexes[END_REF]. Both versions of the model 'korkut' describe the Ras signaling pathways. They have been assembled by John Bachman and Benjamin Gyori (Sorger lab, Big-Mechanisms DARPA Project), following a three steps procedure [START_REF] Gyori | From word models to executable models of signaling networks using automated assembly[END_REF]: automatic natural language processing, automatic assembling into Kappa, and human curation. We analyze two versions of the model of the extracellular matrix of the protein TGF-b that we have used to illustrate the different functionalities of KaSa. The assembling has been done by hand, by inspection of the literature and its curation has been assisted by KaSa. Lastly, we analyze two versions of the Wnt signaling pathway, written by Héctor F. Medina Abarca (Fontana Lab, Big-Mechanisms DARPA Project). This model has also been assembled by hand by inspection of the literature. Some scripts have been used to refine the kinetics of rules according to some contextual information about the proteins.

For each model, we give the number of constraints, of detected dead rules, of detected non weakly reversible transitions, of the rules that are involved in those transitions, of potential influence relation (in each accuracy mode), of strongly connected components that may occur in polymers (in both modes). Then, we give the CPU time used for each of these functionalities. The last column gives the CPU time of the whole analysis, with all functionalities set to the maximal accuracy level. It is worth noting that the CPU time required to compute the direct influence map, is sometimes longer than the one to compute the indirect one. Indeed, dumping an imprecise result may take longer than filtering this result thanks to a more costly but more accurate analysis.

Fig. 1 .

 1 Fig. 1. Two rules. (left) Two proteins may bind. (right) The protein on the left may phosphorylate the right site of the protein on the right.

Fig. 3 .Fig. 4 .

 34 Fig.3. Four rules (left) and the corresponding influence map (right). In rule r p , the right site may be phosphorylated only if the left site is. As a consequence the rule ru inhibits the rule r p , and the rule rp activates the rule r p .

  , we give a local trace associated to the protein MMP2 . Benchmarks (performed on a MacBook Pro, 3.3 Ghz intel Core). For each model, we provide the number of rules, information about what has been discovered by KaSa and about analysis time.

	model							Number of										Analysis time (second)
		rules	constraints	dead rules	non weakly reversible transitions	reversible transitions	rules with non weakly	indirect influences	direct influences	realisable influences	(Syntactic)	strongly connected components	(Realisable)	strongly connected components	edges per scc in average (Syntactic)	edges per scc in average (Realisable)	reachability analysis	influence map (Indirect)	influence map (Direct)	influence map (Realisable)	polymer detection (Syntactic)	polymer detection (Realisable)	non weakly reversible transitions	local traces	all-in-one (at maxiaml accuracy)
	egfr net	39 17	0	0	0	764	280 280	0	0 N/A N/A 0.02 0.04 0.02 0.04 0.02 0.02 0.03 0.02 0.05
	fceri fyn	46 21	0	8	8	758	304 304	1	0	8 N/A 0.04 0.05 0.03 0.10 0.04 0.04 0.06 0.04 0.10
	fceri fyn lig	48 21	0	8	8	760	306 306	1	0	8 N/A 0.04 0.05 0.03 0.09 0.04 0.05 0.06 0.05 0.10
	fceri fyn trimer	362 22 36 96	96	59971 7405 6763	1	0	10 N/A 0.53 4.63 0.66 2.15 0.54 0.54 0.58 0.54 2.24
	fceri fyn gamma2	59 21	0	0	0	1464	518 518	1	0	8 N/A 0.06 0.10 0.04 0.15 0.06 0.06 0.08 0.06 0.16
	fceri fyn ji	36 16	0	0	0	536	231 231	1	0	8 N/A 0.03 0.02 0.01 0.06 0.03 0.03 0.05 0.03 0.07
	fceri fyn lyn 745	40 18	2	2	2	620	255 243	1	0	8 N/A 0.04 0.04 0.02 0.07 0.04 0.04 0.05 0.04 0.08
	fceri fyn trimer	192 19	0	0	0	21557 2536 2536	1	0	10 N/A 0.24 1.60 0.24 0.81 0.24 0.24 0.27 0.24 0.86
	machine	220 72	7	17	10	5319 2873 2735	0	0 N/A N/A 0.77 0.13 0.10 1.05 0.76 0.77 0.97 0.77 1.22
	ensemble	233 86	0	1	1	4841 2936 2936	0	0 N/A N/A 0.62 0.15 0.13 0.82 0.61 0.63 0.91 0.62 1.14
	korkut (2017/01/13) 3916 1289 1610 2016 2016 75563 75563 39280 1	1	131 131 14 2.49 2.71 16 14 14 14 14 18
	korkut (2017/02/06) 5750 2571 884 1397 1397 81412 75472 55101 1	1 2693 2687 94 4.01 4.16 94 96 115 99 114 119
	TGF (V19)	97 107 10 153 53	3471 3009 2631	1	1	78 74 0.24 0.09 0.09 0.47 0.23 0.25 0.37 0.25 0.63
	TGF (2018/04/19) 292 112 0 314 28	6040 5504 5504	1	1	108 108 0.89 0.18 0.19 1.36 0.86 0.90 1.25 0.92 1.73
	BigWnt (2015/12/28) 356 134 1 833 14	5974 5271 5264	1	1	49 49 3.99 0.16 0.16 4.47 3.98 3.96 125 4.00 127
	BigWnt (2017/03/22) 1486 182 12 61	16 1091187 38110 37958 1	1	84 80 15 26 5.15 25 15 15 260 15 286
	Fig. 5.

This material is based upon works partially sponsored by ANR (Chair of Excellence AbstractCell), the Defense Advanced Research Projects Agency (DARPA) and the U. S. Army Research Office under grant number W911NF-14-1-0367, and by the ITMO Plan Cancer 2014 (TGFSysBio project). The views, opinions, and/or findings contained in this article are those of the authors and should not be interpreted as representing the official views or policies, either expressed or implied, of ANR, DARPA, the U. S. Department of Defense, or ITMO.