Gaspard Delebecq
email: gaspard.delebecq@gmail.com

Dominique Davoult

Marie-Andrée Janquin

Valeria Luz

Dominique Oppliger

Jean-Claude Menu

François Dauvin

Gevaert

• Luz

Valeria Oppliger

Dominique Menu

Jean-Claude Dauvin

François Gevaert

-M.-A Janquin -F

-D Menu

L V Oppliger

J.-C Dauvin

J.-C Dauvin

Photosynthetic response to light and temperature in Laminaria digitata gametophytes from two French populations

Keywords: Phaeophyceae, Photosynthesis, Xanthophyll Cycle, Stress, Phenotypic Plasticity, English Channel

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

Introduction

Kelps are major structural components of the cold temperate and boreal coastal communities [START_REF] Lüning | Seaweeds: their environment, biogeography and ecophysiology[END_REF]. They form a highly productive habitat [START_REF] Mann | Seaweeds: their productivity and strategy for growth. The role of large marine algae in coastal productivity is far more important than has been suspected[END_REF] that harbours a rich biodiversity [START_REF] Christie | Species distribution and habitat exploitation of fauna associated with kelp (Laminaria hyperborea) along the Norwegian Coast[END_REF]. The ecological role of kelp is threatened by their expected vulnerability to changes in the physical environment caused by rapid climate change (Wernberg et al., 2011a;[START_REF] Raybaud | Decline in kelp in West Europe and climate[END_REF] or extreme events [START_REF] Wernberg | An extreme climatic event alters marine ecosystem structure in a global biodiversity hotspot[END_REF], especially near range edges, where populations are at the front line of environmental change [START_REF] Wernberg | Seaweed communities in retreat from ocean warming[END_REF].

The persistence of kelp forests mainly depends on the recruitment, growth, competition and the physiological tolerance to environmental factors of the microscopic stages [START_REF] Reed | The effects of canopy shading on algal recruitment and growth in a giant kelp forest[END_REF]Ladah & Zertruche-Gonzales, 2007;[START_REF] Matson | Effects of ocean temperature on the southern range limits of two understory kelps, Pterygophora californica and Eisenia arborea, at multpiple life-stages[END_REF], which are the crucial phases of the complex heteromorphic life cycle of kelp [START_REF] Sauvageau | Sur la sexualite heterogamique d'une Laminaire (Sacchoriza bulbosa)[END_REF]. Gametophytes and embryonic sporophytes can delay their development and reproduction for several months [START_REF] Carney | A multispecies laboratory assessment of rapid sporophyte recruitment from delayed kelp gametophytes[END_REF] until favourable conditions occur and therefore promote rapid recruitment in the best conditions [START_REF] Edwards | The role of alternate life-history stages of a marine macroalga: a seed bank analogue?[END_REF].

Kelp microscopic stages are subject to environmental conditions that differ from those experienced by the macroscopic sporophytes [START_REF] Reed | The effects of canopy shading on algal recruitment and growth in a giant kelp forest[END_REF][START_REF] Martinez | Selective mortality on haploid and diploid microscopic stages of Lessonia nigrescens Bory (Phaeophyta, Laminariales)[END_REF] and can therefore have different physiological optima and tolerance levels [START_REF] Hanelt | Photoinhibition and recovery after high light stress in different developmental and life-history stages of Laminaria saccharina (Phaeophyceae)[END_REF][START_REF] Altamirano | High light stress in the Kelp Ecklonia cava[END_REF][START_REF] Matson | Effects of ocean temperature on the southern range limits of two understory kelps, Pterygophora californica and Eisenia arborea, at multpiple life-stages[END_REF]. Even under similar environmental conditions, the response of haploid stages differs from those of diploid stages among various taxa of macroalgae [START_REF] Roleda | Susceptibility of spores of different ploidy levels from Antarctic Gigartina skottsbergii (Gigartinales, Rhodophyta) to ultraviolet radiation[END_REF][START_REF] Wang | Differential expression of rubisco in sporophytes and gametophytes of some marine macroalgae[END_REF]. Hence, in the context of environmental change, enhancing the understanding of the physiological tolerance of kelp must incorporate the study of their multiple lifestages, including their microscopic phases [START_REF] Harley | Effects of climate change on global seaweed communities[END_REF][START_REF] Wernberg | A decade of climate change experiments on marine organisms: procedures, patterns and problems[END_REF].

Among the potentially adverse environmental conditions, light and temperature can greatly affect the development and survival of microscopic stages and their vulnerability generally determines the ecological success of the species [START_REF] Bartsch | The genus Laminaria sensu lato: recent insights and developments[END_REF].

Extremely high light has been shown to be adverse for the development and viability of post-settlement stages (gametophytes and embryonic sporophytes) [START_REF] Lüning | Light and temperature demands for growth and reproduction of laminarian gametophytes in Southern and Central California[END_REF]Fetjek et al., 2011). Likewise, extreme high temperature events (such as El Niño events) have been shown to affect the reproductive success of gametophytes (Ladah & Zertruche-Gonzales, 2007;[START_REF] Oppliger | Temperature effects on gametophyte life-history traits and geographic distribution of two cryptic kelp species[END_REF].

The photosynthetic apparatus is one of the main targets of these abiotic stressors [START_REF] Walters | Towards an understanding of photosynthetic acclimation[END_REF]. Rapid fluctuation of light and temperature can cause disruptive stresses [START_REF] Davison | Stress tolerance in intertidal seaweeds[END_REF] and affect the survival of kelp gametophytes. Drastic and rapid changes in light exposure and temperature are frequently experienced within a single day [START_REF] Gevaert | Laminaria saccharina photosynthesis measured in situ: photoinhibition and xanthophyll cycle during a tidal cycle[END_REF][START_REF] Delebecq | In situ photosynthetic performance of Laminaria digitata (Phaeophyceae) during spring tides in Northern Brittany[END_REF] and especially during sunny spring tides.

Therefore, the ability to withstand stressful conditions and to recover from them is crucial for preventing damage to the photosynthetic apparatus and maintaining sufficient photosynthetic performance. After the onset of stressful conditions, the regulation of energy absorption and utilization is essential [START_REF] Raven | Adaptation, acclimation and regulation in algal photosynthesis[END_REF].

Photoinhibition is the down-regulation of photosynthesis, whose extent is determined by the balance between the rate of photodamage and the rate of repair of photosystem II (PSII) [START_REF] Takahashi | How do environmental stresses accelerate photoinhibition?[END_REF]. Photoinhibition has been observed in the field on macroscopic sporophyte stages [START_REF] Gevaert | Laminaria saccharina photosynthesis measured in situ: photoinhibition and xanthophyll cycle during a tidal cycle[END_REF][START_REF] Delebecq | In situ photosynthetic performance of Laminaria digitata (Phaeophyceae) during spring tides in Northern Brittany[END_REF], in the laboratory on zoospores [START_REF] Roleda | Photosynthetic response of Arctic kelp zoospores exposed to radiation and thermal stress[END_REF] and in the gametophytic and embryonic sporophyte stages of kelp [START_REF] Hanelt | Photoinhibition and recovery after high light stress in different developmental and life-history stages of Laminaria saccharina (Phaeophyceae)[END_REF][START_REF] Altamirano | High light stress in the Kelp Ecklonia cava[END_REF]. Factors other than light, such as temperature, can accelerate photoinhibition by altering the PSII repair mechanisms [START_REF] Takahashi | How do environmental stresses accelerate photoinhibition?[END_REF]. Toxic active derivatives of oxygen (oxygen radicals), byproducts of photosynthesis, can also be over-produced under adverse environmental conditions (when exceeding the scavenging potential of cells) and can alter the biological integrity of cells [START_REF] Ledford | Singlet oxygen and photo-oxidative stress management in plants and algae[END_REF]Allakverdiev et al., 2008).

To cope with excess light, energy is dissipated in the form of heat to rapidly regulate light harvesting; this mechanism is widespread in photoautotrophs [START_REF] Raven | Adaptation, acclimation and regulation in algal photosynthesis[END_REF]. Increased thermal energy dissipation of excess light involves the xanthophyll cycle in brown algae, which plays a major role in the fast-dynamic acclimation to change in light, temperature and desiccation in macroscopic sporophytes (Fernandez-Marin et al., 2011). However, the implication of xanthophyll cycle in the photoprotection process in kelp gametophytes has only been mentioned [START_REF] Hanelt | Photoinhibition and recovery after high light stress in different developmental and life-history stages of Laminaria saccharina (Phaeophyceae)[END_REF][START_REF] Altamirano | High light stress in the Kelp Ecklonia cava[END_REF], without being clearly demonstrated.

Laminaria digitata Hudson Lamouroux (1813), a kelp species of high ecological and economical value, has been shown to be retreating from several sites along the French coasts [START_REF] Arzel | Les laminaires sur les côtes bretonnes[END_REF][START_REF] Davoult | Environmental factors and commercial harvesting:exploring possible links behind the decline of the kelp Laminaria digitata in Brittany, France[END_REF], sparking research to determine the reasons for this decline. Physical stress and environmental changes may contribute to a reduction in the fitness of the gametophytic developmental stages of L. digitata. In this study, we tested the sensitivity of L. digitata gametophytes to changing photon flux density and temperature. The investigations were carried out on two populations of L. digitata along the French coast of the English Channel inhabiting contrasting environmental conditions [START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF]. The differences in local environmental conditions may result in different sensitivities among the populations that need to be taken into account in understanding the effect of environmental factors on organisms. In this study, we also measured the role of the xanthophyll cycle in the non-photochemical quenching in gametophytes of L. digitata in response to excess light.

Materials and Methods

Study site

A complete description of the two sites and environmental conditions during experiments is given in [START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF]; consequently, we describe only the main characteristics of both sites here. We collected the seaweed material from two populations of L. digitata, growing in the upper subtidal zone (0-1 m) of a rocky shore in Roscoff (48°5'N, 3°6'W) and in Wissant (50°5'N, 1°4'E), located in the western and eastern part of the English Channel, respectively. The sites were selected for their large kelp stands and also for their contrasting environmental conditions. Light attenuation (m -1 ) of photosynthetically active radiation (400-700 nm) ranged from 0.09 to 0.57 m - 1 in Roscoff and from 0.19 to 0.96 m -1 in Wissant [START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF] due to high turbidity in the eastern English Channel. Seawater surface temperature displays high seasonal variation at both sites, with a slightly broader annual temperature range in Wissant, from 5°C in winter to 20°C in summer, than in Roscoff, from 8°C in winter to 17°C in summer, due to the influence of the North Atlantic Ocean and depth of the continental shelf. Environmental conditions in the two sites at the time of collection and 1 month prior to sampling are given in Table 1.

Sampling and culture conditions

Fertile sporophytes of L. digitata were collected at low tide in November 2008 in Roscoff, and in February 2009 in Wissant. L. digitata is reproductive most of the year in Roscoff, but the main spore/gamete release events generally occur in August-September and November-December in Northern Brittany [START_REF] Arzel | Les laminaires sur les côtes bretonnes[END_REF]. In Wissant, L. digitata is reproductive at the end of winter and throughout spring. Mature sori were cut, cleaned, and dried at 10°C and in the dark for several hours. Sori were subsequently washed with distilled water and sterile seawater, and placed in 50 mL Falcon tubes (BD Biosciences, San Jose, CA, USA), filled with sterile Provasoli enriched seawater (PES) [START_REF] Provasoli | Media and prospects for the cultivation of marine algae Cultures and Collections of Algae[END_REF], and maintained overnight in the dark on a rotary shaking table to induce zoospore release. Zoospores in suspension were checked with inverted-light microscope to ensure that zoospores were viable, before being placed in Petri dishes (BD Falcon, Franklin Lakes, NJ, USA). Zoospores were allowed to settle and developing gametophytes were cultured in thermostatic chamber at 10°C under an irradiance of 35 µmol photons m -2 s -1 (photon flux density, PFD, 400-700 nm), produced by fluorescent tubes (L8W/840, cool white, Osram, Germany) in a light:dark cycle 12:12 h. PFD was measured with a cosine-corrected quantum sensor (Li-192SA, LiCor, Lincoln, Nebraska, USA), connected to a data logger (Li 1400, LiCor, Lincoln, Nebraska, USA).

The medium was changed once a week. Experiments started approximately after 1 month of cultivation when the density was high enough for fluorescence measurements.

The density of the gametophytes was 4711 ± 1140 ind m -2 for Roscoff (43 ± 3% cover) and 3600 ± 691 ind m -2 for Wissant (41 ± 7% cover). Gametophytes were composed of few cells and arranged as homogenous thick layers at the bottom of the Petri dishes.

Gametophytes were isolated from three different parents at each site (n = 3) and were cultivated separately to ensure independent replicates.

Oxygen production

Dark respiration (R d ) and net oxygen production (NP) was measured polarographically at culture temperature (10°C), using a water-jacket thermostatic DW2/2 chamber combined with a "Clark-type" oxygen electrode and a computer-interfaced box CB1 (Hansatech Instruments, Kings Lynn, Norfolk, UK). The gametophytes were first detached from the substrate and resuspended several days prior to the experiment.

Detaching gametophytes from their substrate does not affect their growth, their photosynthetic performance or their respiration [START_REF] Fain | Effects of light and temperature on net photosynthesis and dark respiration of gametophytes and embryonic sporophytes of Macrocystis pyrifera[END_REF]. The gametophytes were held 12 h in the dark prior to the experiment, and then placed in the measurement chamber filled with 2 mL of PES and mixed with a magnetic stirrer. To prevent oxygen saturation, a quarter of the medium was renewed after each light step.

To do so, a silk filtering mesh was used to retain the gametophytes in the media.

Respiration was measured in the dark, and gametophytes then underwent lightincreasing steps of 20 min each (13 light steps, ranging from 2.5 to 500 µmol photons m -2 s -1 ) using a halogen lamp (KL 2500 LCD, Schott, Germany) with a daylight cut-off filter (Schott, Germany). R d , NP and gross oxygen production (GP) rates were calculated based on fresh weight (FW, µmol O 2 g FW -1 h -1 ) and chlorophyll a content (chl a, µmol O 2 nmoles chl a -1 h -1 ,). FW was measured after collecting gametophytes on a silk filtering mesh that had previously been weighed.

Fluorescence

In vivo chl a fluorescence of the photosystem II (PSII) of gametophytes was measured using an underwater fluorometer (diving PAM; Heinz Walz, Effeltrich, Germany). The optimal quantum yield (F v /F m ) of PSII [START_REF] Genty | The relationship between the quantum yield of photosynthetic electron transport and quenching of chlorophyll fluorescence[END_REF], a measure of the maximum efficiency of PSII, was measured using a 0.8 s saturating pulse (2500 µmol photons m -2 s -1 ) of white light. We calculated the relative F v /F m ratio (rel. F v /F m ) by dividing all data by the initial value measured at the beginning of the experiment in the dark.

The effective quantum yield of PSII (ф PSII ), the efficiency of PSII photochemistry, was measured using a custom-made clip for Petri dishes to ensure a constant distance of 5 mm between the probe and the sample. The ф PSII was calculated according to [START_REF] Genty | The relationship between the quantum yield of photosynthetic electron transport and quenching of chlorophyll fluorescence[END_REF] and used to estimate the linear electron transport rate (relative electron transport rate, rETR) [START_REF] Gevaert | Laminaria saccharina photosynthesis measured in situ: photoinhibition and xanthophyll cycle during a tidal cycle[END_REF], an estimator of photosynthesis.

Non-photochemical quenching (NPQ) indicates thermal dissipation of excess light in the PSII antennae, a photoprotective mechanism. We assumed that a stable NPQ level is reached after a 10-min illumination period, as shown in several microalgal species [START_REF] Casper-Lindley | Fluorescence quenching in four unicellular algae with different light-harvesting and xanthophyll-cycle pigments[END_REF]. F m ' values measured under very weak irradiance were higher than F m values measured after dark-adaptation; therefore NPQ values were computed using the higher F m ' value instead of F m (Serodio et al., 2005).

rETR and NPQ were measured on gametophytes at the end of each light-increasing step of 10 min each (12 light steps, ranging from 2.5 to 250 µmol photons m -2 s -1 ). The NPQ value measured under the maximal irradiance is referred to as NPQ 250 .

P-I curves, rETR-I

The light-saturated maximum rate of GP (P max ), the light-saturated maximum rate of relative electron transfer (rETR max ), the light-limited initial slope (α), and the saturation onset irradiance level (I k ) were calculated by plotting computed oxygen production rates and rETR against irradiance. P max represents the maximal oxygen production, including all photosynthetic processes, while rETR max is an estimation of the linear electron transfer in PSII, an indication of the overall photosynthetic capacity. Data were fitted using the model of [START_REF] Eilers | A model for the relationship between light intensity and the rate of photosynthesis in phytoplankton[END_REF] to each replicate with a least-square regression, using the Simplex method in the Statistica computer package (Statsoft, Tulsa, OK, USA).

Response to high irradiance

To study high light stress, the settled gametophytes in a Petri dish filled with PES at cultivation temperature were exposed to 500 µmol photons m -2 s -1 for 2 h, and then, to dim light (10 µmol photons m -2 s -1 ) to allow recovery. F v /F m , ф PSII , rETR and NPQ were measured every 30 min. Samples for pigment analyses were simultaneously collected at the start of the experiment, at the end of the light stress, and 2 h after the return to dim light. Gametophytes were detached from the substrate and the gametophyte suspension was filtered on a 20 µm silk filtering mesh and subsequently deep-frozen in liquid nitrogen for further pigment analyses.

Response to temperature

First, rETR-I curves were constructed for gametophytes acclimated 4 h at four different temperatures (5°C, 10°C, 15°C and 20°C) controlled by a thermo fluid circulator bath.

During acclimation, F v /F m was measured hourly. Then, gametophytes underwent a progressive increase and decrease temperatures (2°C every 15 min) with an initial temperature set at 10°C. F v /F m was measured at the end of each temperature step.

Pigment analysis

Pigment contents of gametophytes were extracted by sonication and grinding in a cold mortar with methanol and methylene chloride. Extracts were centrifuged and supernatants were collected and dry-evaporated under nitrogen. Salt contents of the extracts were removed and the organic phase was evaporated and dissolved in methanol for injection. Pigment analysis was performed by high performance liquid chromatography (HPLC) (Beckman, system Gold, 126) with a reverse-phase column (C 18 Allure, Restek). Separation was performed with a solvent delivery profile adapted from [START_REF] Arsalane | Influence of the pool size of the xanthophyll cycle on the effect of light stress in a Diatom: competition between photoprotection and photoinhibition[END_REF]. Pigment contents were quantified using specific absorption

Statistical analyses

Student's t-test (t) (with Welch correction) was used to test for the difference between means of the photosynthetic parameters (P max , rETR max , α et I k ), the F v /F m , NPQ values and pigment contents after the dataset was tested for normality using the Shapiro-Wilk test [START_REF] Shapiro | An analysis of variance test for normality (complete samples)[END_REF]. Response to light or temperature was fitted and response parameters were compared using Student's t-test. The DR response was compared within sites using a t-test for paired samples (t (p) ) after checking the data for normality.

Adjustment of P values for multiple testing was done using the Holm method. The effect of temperature on the response parameters of light-response curves was analysed using a PERMANOVA [START_REF]A new method for non-parametric multivariate analysis of variance[END_REF] in the vegan package of R software. Post hoc power analysis (1-β) were performed on non significant results using G*Power software which automatically determine the effect size [START_REF] Faul | G*Power 3: A flexible statistical power analysis program for the social, behavorial and biomedical sciences[END_REF]. All experimental units had three replicates (n = 3).

Results

Comparison of the photosynthetic activity between the two sites

Gametophytes from the two sites showed differences in their photosynthetic parameters (Fig. 1). When normalized to chl a, P max(chla) values, the light-saturated maximal gross oxygen production values, were higher in Roscoff than in Wissant (t = 8.0, Holmadjusted P = 0.003), with 0.27 ± 0.01 µmol O 2 . nmoles chl a -1 h -1 in Wissant, and 0.95 ± 0.15 µmol O 2 nmoles chl a -1 h -1 in Roscoff (Fig. 1 C). rETR max values (22.74 ± 5.37 µmol e -m -2 s -1 in Wissant and 15.90 ± 0.77 µmol e -m -2 s -1 in Roscoff), the lightsaturated maximal electron transfer rates, and P max(FW) on a FW basis (56.47 ± 13.18

µmol O 2 g FW -1 h -1 in Wissant and 38.33 ± 1.12 µmol O 2 g FW -1 h -1 in Roscoff),were not significantly different between two sites (t = 2.9, Holm-adjusted P = 0.133 for rETR max ; t = 2.8, Holm-adjusted P = 0.142 for P max(FW) values) (Fig. 1 A-B), likely due to low statistical power resulting from small sample sizes (0.39 for rETR max and 0.32 for

P max(FW) ).
The same pattern appeared for the ascending slope under light limitation (α values).

α (chla) values were significantly higher in Roscoff than in Wissant (respectively 0.005 ± 0.001 in Wissant and 0.023 ± 0.002 in Roscoff) (t = 13.9, Holm-adjusted P = 0.001) when expressed on a chl a basis, whereas no differences were observed when expressed in electron transport rates or when expressed on a FW basis (respectively 0.37 ± 0.06 in Wissant and 0.40 ± 0.03 in Roscoff; t = 0.68 , Holm-adjusted P = 0.534 for α (rETR) and 1.15 ± 0.17 in Wissant and 0.99 ± 0.09 in Roscoff t = 1.39, Holm-adjusted P = 0.305 for α (FW) ) which can also result from very low statistical power (respectively 0.09 and 0.19).

Considering the light saturation parameter (I k ), no significant differences were found between the two sites but the low statistical powers suggest that there were not enough replication to resolve the differences (t = 1.95, Holm-adjusted P = 0.245 and 1-β = 0.30

for Ik (rETR) , t = 1.77, Holm-adjusted P = 0.152 and 1-β = 0.28 for Ik (FW) and t = 1.13, Holm-adjusted P = 0.322 and 1-β = 0.14 for Ik (chla) ). Despite this lack of significant Despite high irradiance (500 µmol photons m -2 s -1 ) in comparison with the culture conditions, there was no decrease in oxygen production observed.

Comparison of pigment contents

Pigment contents were similar at both sites (Table 2) except for chl c and violaxanthin contents, which were higher in Wissant than in Roscoff (t = 4.69, Holm-adjusted P = 0.047 for chl c and t = 4.26, Holm-adjusted P = 0.047 for violaxanthin). When expressed on a total pigment content basis, no differences were observed in chl a contents in both sites, but chl a contents were slightly lower in Wissant and statistical power was low (0.33). Therefore higher ΣXC:chl a pigment ratio may have been expected in Wissant, but the lack of significant difference is believed to be the result of a low statistical power (0.53).

When chl a contents were expressed per unit fresh weight (respectively 47.74 ± 6.63 nmoles g FW -1 in Roscoff and 155.95 ± 38.22 nmoles g FW -1 in Wissant), they were significantly higher in Wissant (t = 4.83, Holm-adjusted P = 0.036).

Comparison of photoprotective capacities

NPQ was measured along with rETR (Fig. 2). NPQ values after prolonged darkness (12 h, corresponding to the end of the dark period of culture conditions) were higher than those under weak irradiances. Maximal F m ' values were reached under an average irradiance of 20 µmol photons m -2 s -1 in Roscoff, and 50 µmol photons m -2 s -1 in Wissant.

NPQ progressively developed with increasing irradiance. Maximal NPQ values (NPQ 250 ) were reached at the highest applied irradiance (250 µmol photons m -2 s -1 ) and these values were significantly higher in gametophytes from Roscoff than in gametophytes from Wissant (t = 3.5, Holm-adjusted P = 0.047), with NPQ 250 values of 3.80 ± 0.42 in Roscoff and of 2.37 ± 0.56 in Wissant.

Intrinsic efficiency of PSII was altered in both populations, as indicated by the strong decline of rel. F v /F m values (Fig. 3 A) when gametophytes were exposed to 500 µmol photons m -2 s -1 for 2 h. It reached a constant level, decreasing by 70% of the initial F v /F m value after 2 h in both populations. In dim light, F v /F m recovered at a level within 5% of the initial F v /F m value after 1.5 h in Roscoff and after 4 h in Wissant.

During light stress, there was an increase in DR in gametophytes from Roscoff and from Wissant, corresponding to the progressive de-epoxidation of violaxanthin into antheraxanthin and zeaxanthin (t (p) = 7.9, Holm-adjusted P = 0.025 for gametophytes from Wissant and t (p) = 8.9, Holm-adjusted P = 0.025 for gametophytes from Roscoff) (Fig. 3 The sensitivity of F v /F m to temperature was tested on a broad range of temperature (Fig. 5). At 10°C, F v /F m values in the dark were 0.52 ± 0.09 in Roscoff and 0.53 ± 0.06 in Wissant. With the progressive increase in temperature (from 10°C to 32°C), the rel.

F v /F m declined for temperatures greater than 20°C. There were no differences between sites in the response parameters from the regression analysis.

Discussion

Microscopic stages are thought to be the hardiest life-cycle stages of kelp (tom Dieck 1993). They form a seed bank which persists through stressful environmental conditions and ensures the persistence of species when unfavourable conditions occur, as it may happen during unusual heat waves (Ladah & Zertuche-Gonzales, 2007[START_REF] Bartsch | Prevailing surface temperature inhibit summer reproduction of the kelp Laminaria digitata at Helgoland (North Sea)[END_REF]. Therefore, a great tolerance of L. digitata gametophytes to stressful environmental conditions is essential. In this study, we tested their physiological tolerance to irradiation and temperature stress in two populations with different environmental conditions along the French coast. The main result of the present study is that gametophytes of L. digitata were highly resistant to the irradiation and temperature treatments that might be locally encountered in the field. It is reinforced by the fact that sori were sampled during months when irradiation and temperature stress are not prevalent: their temperature and irradiation resistance may be even higher during summer.

We set out to study the incidence of high light stress on the photosynthesis of L. digitata gametophytes. Our results demonstrate that gametophytes can cope with prolonged high irradiance stress, confirming the great potential for high light tolerance in kelp gametophytes [START_REF] Iizumi | Temperature dependence of photosynthesis-irradiation (P-I) relationship of gametophytes of Laminaria religiosa Miyabe[END_REF][START_REF] Hanelt | Photoinhibition and recovery after high light stress in different developmental and life-history stages of Laminaria saccharina (Phaeophyceae)[END_REF][START_REF] Altamirano | High light stress in the Kelp Ecklonia cava[END_REF].

This tolerance arises from the efficient thermal dissipation of excess light (NPQ) and, mainly, through the formation of antheraxanthin and zeaxanthin, which induce the conformational change in the light harvesting complexes (LHC) II [START_REF] Jahns | The role of xanthophylls cycle and of lutein in the photoprotection of photosystem II[END_REF]. This zeaxanthin-dependent quenching is a slow component of NPQ, and Garcia- [START_REF] Garcia-Mendoza | The giant kelp Macrocystis pyrifera presents a different nonphotochemical quenching control than higher plants[END_REF]. Therefore, our study confirms that this efficient reversible conversion between violaxanthin, antheraxanthin and zeaxanthin in gametophytes (previously suggested by [START_REF] Hanelt | Photoinhibition and recovery after high light stress in different developmental and life-history stages of Laminaria saccharina (Phaeophyceae)[END_REF][START_REF] Altamirano | High light stress in the Kelp Ecklonia cava[END_REF]) is a widespread mechanism of fast-dynamic acclimation to abiotic stress in macroalgae (Fernandez-Marin et al., 2011).

Mendoza
Another possible mechanism protecting L. digitata gametophytes from rapid light fluctuations is the maintenance of NPQ in the dark, a mechanism previously observed in microphytobenthos [START_REF] Serôdio | Non-photochemical quenching of chlorophyll fluorescence and operation of the xanthophyll cycle in estuarine microphytobenthos[END_REF] and in several phytoplankton species [START_REF] Casper-Lindley | Fluorescence quenching in four unicellular algae with different light-harvesting and xanthophyll-cycle pigments[END_REF][START_REF] Cruz | Impact of chlororespiration on non-photochemical quenching of chlorophyll fluorescence and on the regulation of the diadinoxanthin cycle in the diatom Thalassiosira pseudonana[END_REF]. In Pelvetia canaliculata, the NPQ of chl a fluorescence in the dark depends on the activation of violaxanthin de-epoxidase (Fernandez-Marin et al., 2011), which is triggered by acidification of the lumen due to metabolic activity in the dark [START_REF] Cruz | Impact of chlororespiration on non-photochemical quenching of chlorophyll fluorescence and on the regulation of the diadinoxanthin cycle in the diatom Thalassiosira pseudonana[END_REF]. This activation may thus sustain ATP synthase activity [START_REF] Casper-Lindley | Fluorescence quenching in four unicellular algae with different light-harvesting and xanthophyll-cycle pigments[END_REF][START_REF] Serôdio | Non-photochemical quenching of chlorophyll fluorescence and operation of the xanthophyll cycle in estuarine microphytobenthos[END_REF], and prevent the formation of oxygen radicals. NPQ in the dark may therefore represent a type of sustained photoprotection, maintaining a dissipative state through pre-formed zeaxanthin or antheraxanthin, as observed here.

Acclimation to higher irradiances than the culture irradiance used in this experiment and/or an intermittent light exposure may have also provided a higher tolerance to the two-hour light stress of 500 µmol photons m -2 s -1 [START_REF] Han | Effect of photon irradiance and photoperiod on young sporophytes of four species of the Laminariales[END_REF][START_REF] Lavaud | Influence of the diadinoxanthin pool size on photoprotection in the marine planktonic diatom Phaeodactylum tricornutum[END_REF]. Along the French coast of the English Channel, irradiance of 500 µmol photons m -2 s -1 and more can be recorded during spring and summer low spring tides [START_REF] Gevaert | Laminaria saccharina photosynthesis measured in situ: photoinhibition and xanthophyll cycle during a tidal cycle[END_REF][START_REF] Delebecq | In situ photosynthetic performance of Laminaria digitata (Phaeophyceae) during spring tides in Northern Brittany[END_REF][START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF], but actual incident irradiances are generally deeply attenuated by the sporophyte canopy [START_REF] Gerard | The light environment in a giant kelp forest: influence of Macrocystis pyrifera on spatial and temporal variability[END_REF] which may hypothesized that gametophytes display a great tolerance to high light.

This study also highlighted that the photosynthetic performance of L. digitata gametophytes were not negatively affected by short-term fluctuations in water temperature as it may be locally encountered in the field during periods of low tide.

Gametophyte PSIIessential for the whole photochemistry process [START_REF] Havaux | Temperature-dependent adjustment of the thermal stability of the photosystem II in vivo: possible involvement of xanthophyllcycle pigments[END_REF][START_REF] Roleda | Photosynthetic response of Arctic kelp zoospores exposed to radiation and thermal stress[END_REF] shows high resistance to the temperatures currently encountered in the field. Increased temperature promotes electron transfer via the PSII through an increase in thylakoid membrane fluidity [START_REF] Havaux | Temperature-dependent adjustment of the thermal stability of the photosystem II in vivo: possible involvement of xanthophyllcycle pigments[END_REF] and results in an increase in maximum relative electron transfer rates (rETR max ) and in the onset of saturation parameters (I k ), as observed here. An increase in gross oxygen production with temperature can therefore be expected up to an optimum [START_REF] Sukenik | Light-saturated photosynthesis -limitation of electron transport or carbon fixation?[END_REF], since the relationship electron transport rate and gross oxygen production is robust, provided that the temperature changes are not extremes [START_REF] Morris | Influence of temperature on the relationship between oxygen-and fluorescence-based estimates of photosynthetic parameters in a marine benthic diatom (Cylindrotheca closterium)[END_REF].

Above an optimal temperature (above 20°C in this study), a complex set of inactivation and denaturation occur in thylakoïd, accompanied by the generation of elevated levels of reactive oxygen species which reduces photosynthetic capacity [START_REF] Sharkey | Effects of moderate heat stress on photosynthesis: importance of thylakoid reactions, rubisco deactivation, reactive oxygen species, and thermotolerance provided by isoprene[END_REF][START_REF] Allakhverdiev | Heat stress: an overview of molecular responses in photosynthesis[END_REF] and also the ability to cope with high light stress [START_REF] Roleda | Photosynthetic response of Arctic kelp zoospores exposed to radiation and thermal stress[END_REF]. Superoptimal temperature also promotes electron-consuming processes (such as cyclic electron transfer) and dark respiration [START_REF] Fain | Effects of light and temperature on net photosynthesis and dark respiration of gametophytes and embryonic sporophytes of Macrocystis pyrifera[END_REF][START_REF] Sharkey | Effects of moderate heat stress on photosynthesis: importance of thylakoid reactions, rubisco deactivation, reactive oxygen species, and thermotolerance provided by isoprene[END_REF][START_REF] Henkel | Thermal ecophysiology of gametophytes cultured from invasive Undaria pinnatifida (Harvey) Suringar in coastal California harbors[END_REF] which can result in negative net photosynthesis.

However, short-term temperature responses do not provide insight into long-term individual survival with regard to temperature: temperature optima for photosynthesis can be several degrees higher than temperature optima for survival and growth [START_REF] Davison | Environmental effects on algal photosynthesis: temperature[END_REF] as it is not possible to evaluate the extent of sublethal stress.

Concerning L. digitata gametophytes, tom Diek (1993) showed that they were able to survive 8 weeks at 23°C, demonstrating that gametophytes are moderately resistant to temperature extremes that are rarely encountered across its geographic range. Moreover, there is seasonal acclimation of the temperature response of gametophytes [START_REF] Lee | Seasonal light and temperature interaction effects on development of Laminaria saccharina (Phaeophyta) gametophytes and juveniles sporophytes[END_REF] and temperature resistance of PSII may be even higher in gametophytes sampled in warmer months or acclimated to higher temperatures [START_REF] Mohring | Environmental influences on kelp performance across the reproductive period: an ecological trade-off between gametophyte survival and growth?[END_REF].

The two sites from which gametophytes were obtained were known to display different seasonal range of abiotic conditions [START_REF] Berx | Climatology of surface and near-bed temperature and salinity on the North-West European continental shelf for 1971-2000[END_REF][START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF], and a strong photoacclimation to local environmental conditions of sporophytes of L. digitata from the two same sites was previously highlighted [START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF].Here, we found some differences in the physiological characteristics of gametophytes between the two sites, however the small replication did not exhibit the full physiological diversity of the populations investigated, and replication was clearly not sufficient to resolve the differences as indicated by the very low statistical power of our analysis (never exceeding 53%). Moreover, results in the present study are confounded by the different environmental conditions at the time of sampling in the two sites (Table 1) that may influence the physiological response of gametophyte even after one month cultivation under lab conditions, depending on the time-scale of acclimation to new light and temperature treatments. More information on seasonal changes that can occur in the gametophytes from Roscoff and Wissant would be necessary for a more complete picture of the gametophyte response in the English Channel taking into account the variation of the whole set of past and present environmental conditions, and to test if the photosynthetic characteristics measured in sporophytes may be conserved in gametophytes.

The higher chl a concentrations and fucoxanthin contents in gametophytes from Wissant may suggest a greater light-harvesting efficiency and a higher density of reaction centres [START_REF] Gerard | Ecotypic differentiation in light-related traits of the kelp Laminaria saccharina[END_REF], which generally result in higher photosynthetic rates.

Although maximal photosynthetic rates (rETR max and P maxFW ) in Wissant were not significantly different from those in Roscoff, it is believed to result of low statistical power, as indicated by the differences observed in P maxchla . Hence, P maxchla was higher in Roscoff than in Wissant, indicating less efficient light use per chl a molecule in the gametophytes from Wissant. This difference may be due to the self-shading of the LHC, i.e. the fact that light absorption do not increase despite a higher pigment concentration [START_REF] Falkowski | Aquatic photosynthesis[END_REF]. Daily underwater irradiances were shown to be similar in both sites at the time of sampling [START_REF] Delebecq | Influence of local environmental conditions on the seasonal acclimation process and the daily integrated production rates of Laminaria digitata (Phaeophyta) in the English Channel[END_REF]. As thermal acclimation is known to induce change in photoacclimation status [START_REF] Machalek | Thermal acclimation and photoacclimation of photosynthesis in the brown alga Laminaria saccharina[END_REF], those differences in photosynthetic characteristics may be partly due to the lower sea surface temperature in Wissant at the time of sampling (Table 1), if initial temperature encountered in the field still influence gametophyte's response to light, even after one month cultivation.

Then, the larger violaxanthin content in Wissant may compensate for the large antenna size (higher fucoxanthin contents) which is known to decrease the probability of encounters between violaxanthin and violaxanthin de-epoxidase and the speed of deepoxidation under high light (Garcia-Mendoza & Colomba-Palotta, 2007). It may also be due to the faster changing light conditions imposed by higher light attenuation in Wissant. Violaxanthin is also involved in the response to other abiotic stressors [START_REF] Havaux | Temperature-dependent adjustment of the thermal stability of the photosystem II in vivo: possible involvement of xanthophyllcycle pigments[END_REF]Fernandez-Marin et al., 2011). Thus, a larger pool of violaxanthin may help gametophytes from Wissant to cope with other abiotic stressors not tested in this study.

We found no differences in the temperature response of the two sites with respect to the resistance of PSII quantum efficiency and increasing temperature. We expected that the wider temperature range encountered in Wissant may have induced a difference in thermostability of PSII. The small difference in temperature range may have not been sufficient to produce detectable differences. Moreover, at the time of sampling, temperature was lower in Wissant (5°C) than in Roscoff (12°C) and this difference may have influenced the photosynthetic response of gametophytes in our study [START_REF] Lee | Seasonal light and temperature interaction effects on development of Laminaria saccharina (Phaeophyta) gametophytes and juveniles sporophytes[END_REF][START_REF] Mohring | Environmental influences on kelp performance across the reproductive period: an ecological trade-off between gametophyte survival and growth?[END_REF]. Beside thermal conditions and sampling time, the low replication size of our experiments may have been not sufficient to draw a well supported conclusion on the lack of difference between the two sites.

Regarding the temperature response of gametophytes, [START_REF] Bolton | Optimal growth and maximal survival temperatures of Atlantic Laminaria species (Phaeophyta) in culture[END_REF] suggested that Laminaria species may show sufficient phenotypic plasticity to adjust to the temperature range along its distribution and is not composed of differentiated temperature-adapted ecotypes throughout its range. However, notwithstanding similar growth patterns, physiological differences in the response to temperature may nevertheless occur among populations of perennial brown seaweeds [START_REF] Henkel | Thermal ecophysiology of gametophytes cultured from invasive Undaria pinnatifida (Harvey) Suringar in coastal California harbors[END_REF][START_REF] Staehr | Physiological responses of Ecklonia radiata (Laminariales) to a latitudinal gradient in ocean temperature[END_REF]. In order to test for difference in temperature response of the L. digitata's populations along the French coast, further experiments need to compare gametophytes from (1) the two sites at different times of the year during their respective sporulation periods [START_REF] Mohring | Environmental influences on kelp performance across the reproductive period: an ecological trade-off between gametophyte survival and growth?[END_REF] and (2) sites with more contrasting temperature ranges [START_REF] Staehr | Physiological responses of Ecklonia radiata (Laminariales) to a latitudinal gradient in ocean temperature[END_REF]. More generally, investigating the joint effect of light and temperature requires a multifactorial experiment [START_REF] Fredersdorf | Interactive effects of radiation, temperature and salinity on different life history stages of the Arctic kelp Alaria esculenta (Phaeophyceae)[END_REF].

Gametophytes appeared to be resistant to the light and temperature conditions currently experienced in the field. Regarding vulnerability to environmental conditions, physiological studies on the interactive effects of multiple abiotic stressors are required to improve our understanding of the microscopic stages in kelp [START_REF] Fredersdorf | Interactive effects of radiation, temperature and salinity on different life history stages of the Arctic kelp Alaria esculenta (Phaeophyceae)[END_REF]. For instance, desiccation tolerance [START_REF] Contreras-Porcia | Seaweeds early development: detrimental effects of desiccation and attenuation by algal extracts[END_REF], ultraviolet radiation [START_REF] Roleda | Exposure to ultraviolet radiation delays photosynthetic recovery in Arctic kelp zoospres[END_REF] and burial in sediment deposition [START_REF] Roleda | Storm-generated sediment deposition on rocky shores: Simulating burial effects on the physiology and morphology of Saccharina latissima sporophytes[END_REF] all affect microscopic stages. While the southern geographic range-limit of L. digitata is thought to be set by inhibition of reproduction, as it was observed by [START_REF] Bartsch | Prevailing surface temperature inhibit summer reproduction of the kelp Laminaria digitata at Helgoland (North Sea)[END_REF] when temperature reaches 18°C, survival of microscopic stages remains essential to cope with unusual stressful conditions. There is also an important need to obtain more information on the persistence of these stages in the field. It could help in defining which environmental conditions are really encountered in the field by the different microscopic developmental stages. Despite the present study failed to report local variation in the physiological response of L. digitata, it remains essential to take into account local variation in predicting the impact of fast-changing conditions in coastal areas.

Figures legends

Fig. 1 Photosynthesis-irradiance curves (P-I curves) of gametophytes in L. digitata from Wissant (□) and Roscoff (•) (n = 3), expressed as (A) relative electron transport rate (rETR, µmol e -m -2 s -1 ), (B) gross oxygen production on a fresh weight basis (GP, µmol O 2 g FW -1 h -1 ) and (C) gross oxygen production per unit chl a (GP, µmol O 2 nmoles chl a - 1 h -1 ). Gametophytes acclimated at 5°C, 10°C, 15°C and 20°C exposed to increasing irradiance at the temperature of acclimation. Photosynthetic parameters (α, rETR max and I k ) were calculated using the model of [START_REF] Eilers | A model for the relationship between light intensity and the rate of photosynthesis in phytoplankton[END_REF].

  coefficients and normalised to the total pigment content. The conversion of violaxanthin into antheraxanthin and zeaxanthin was estimated by calculating the de-epoxidation ratio (DR): DR = (antheraxanthin + zeaxanthin) / (violaxanthin + antheraxanthin + zeaxanthin) Total chl a concentrations were normalised to the FW of samples. Fucoxanthin and chl c pigment concentrations normalised to chl a (moles per 100 mol of chl a) were pooled, and referred to as the antenna pigment pool. Violaxanthin, antheraxanthin and zeaxanthin concentrations normalised to chl a were pooled, referred to as the xanthophyll cycle pool.

  B). The increase in intrinsic efficiency of PSII under dim light was accompanied by a decrease in the DR values in gametophytes from Roscoff (t (p) = 11.6, Holmadjusted P = 0.022), indicating the reconversion of zeaxanthin and antheraxanthin into violaxanthin. In spite of the difference in the absolute values of DR measured at both sites after 2 h of strong illumination, the percent increase in DR was similar at both sites with an increase of 160% of the initial DR values. There was no significant decrease in DR values in Wissant after 2 h under dim light.Comparison of the response to temperatureIncreasing the temperature resulted in a decrease in α values in Wissant (Fig.4 A), and an increase in rETR max and I k values for both sites (respectively Fig. 4 B and 4 C) (Table 3). NPQ 250 was calculated at the end of each rETR-E curves (Fig. 4 D). When exposed to 20°C, there was a slight decrease in the NPQ 250 values, in comparison with the values reached at 10°C.

  & Colombo-Pallota (2007) have shown that kelp may lack the fast energy or pH-dependent quenching. However, the large xanthophyll cycle pigment pool may accelerate NPQ development and thus compensate for this lack. Under dim light, epoxidation of zeaxanthin and antheraxanthin was virtually complete in less than 1 h. The slowly relaxing component of photoinhibition generally corresponds to the progressive re-activation of PSII or possibly to a conformational change of the LHC, and probably the aggregation if LHC due to zeaxanthin binding (Garcia-Mendoza &

Fig. 2

 2 Fig. 2 NPQ of gametophytes in L. digitata from Wissant (□) and Roscoff (•) (n = 3)

Fig. 3

 3 Fig.3(A) Relative optimal quantum yield (rel. F v /F m ) and (B) de-epoxidation ratio of

Fig. 4

 4 Fig. 4 Photosynthetic parameters (α (A), rETR max (B) and I k (C)) and maximal NPQ

Fig. 5

 5 Fig. 5 Relative optimal quantum yield (rel. F v /F m ) of gametophytes in L. digitata from

Table 1

 1 Environmental conditions in the two sites at the time of collection and 1 month prior to sampling. Environmental data were provided by T. Carriou from the Station Biologique de Roscoff and the Somlit network.

		Roscoff		Wissant
		Time of collection	1 month prior	Time of collection	1 month prior
	Daylenght (hh:mm)	09:13	10:51	09:30	08:50
	Daily surface irradiance	4.13	11.12	5.45	8.04
	(mol photons. m -2 . j -1 )
	Light attenuation of PAR	0.21	0.20 ± 0.01	0.34	0.37 ± 0.06
	(m -1 )
	Sea Surface Temperature	12.8	13.4 ± 0.8	5.1	5.3 ± 0.4
	(°C)
	Salinity	35.2	35.2 ± 0.0	34.5	34.5 ± 0.1
	Dissolved NO 3 (µmol. L -1 )	8.00	6.83 ± 1.07	13.62	13.42 ± 0.34
	Dissolved PO 4 (µmol. L -1 )	0.49	0.45 ± 0.05	0.40	0.46 ± 0.07

Table 3

 3 Results of multivariate PERMANOVA analysis to test for differences in 795 temperature and sites. Data were normalised and dissimilarities calculated as Euclidian 796 distances. P-values were calculated from 999 permutations of the residuals under the 797 reduced model. Significant results (P < 0.05) are highlighted in bold.

	798
	799
			df	Mean squares	Pseudo-F	P (perm)
	α	Site	1	0.0052	1.5444	0.237
		Temperature	3	0.0307	9.0127	0.009
		Site x Temperature	1	0.0001	0.0058	0.928
		Residual	20	0.0034
	I k	Site	1	745.0	2.742	0.100
		Temperature	3	20189.3	76.516	0.001
		Site x Temperature	1	423.8	1.560	0.211
		Residual	20	271.7
	rETR max	Site	1	15.35	0.717	0.417
		Temperature	3	1122.24	52.420	0.001
		Site x Temperature	1	22.51	1.051	0.321
		Residual	20	21.41
	NPQ max	Site	1	11.2083	11.21	0.001
		Temperature	3	12.0839	12.08	0.001
		Site x Temperature	1	0.0335	0.03	0.080
		Residual	20	0.5527	0.55
	800

Acknowledgments

We would like to thank the BEDIM Team of the Station Biologique de Roscoff and especially M. Valero and C. Destombe for their valuable support and also for receiving, and providing seaweed material. We also thank the Service Mer et Observation at the Station Biologique de Roscoff and A. Migné for their valuable support during field sampling. We greatly thank Marie Cachera for her help in statistical analyses. This study was funded by the Agence Nationale de la Recherche (ANR ECOKELP). We thank the three reviewers for their remarks and advice that helped to improve the manuscript.


Mohamed Hadded
email: mohamed.haddad@ensi.rnu.tn

Rachid Zagrouba
email: rachid.zagrouba@cristal.rnu.tn

Anis Laouiti
email: anis.laouiti@telecom-sudparis.eu

Paul Muhlethaler
email: paul.muhlethaler@inria.fr

Leila Azouz Saidane
email: leila.saidane@ensi.rnu.tn

A Multi-Objective Genetic Algorithm-Based Adaptive Weighted Clustering Protocol in VANET

Keywords: VANET, Cluster Protocol, Ad hoc Networks, Multi-Objective Optimization, Pareto Front, NSGA-II, MOPSO, MODE

Vehicular Ad hoc NETworks (VANETs) are a major component recently used in the development of Intelligent Transportation Systems (ITSs). VANETs have a highly dynamic and portioned network topology due to the constant and rapid movement of vehicles. Currently, clustering algorithms are widely used as the control schemes to make VANET topology less dynamic for Medium Access Control (MAC), routing and security protocols. An efficient clustering algorithm must take into account all the necessary information related to node mobility. In this paper, we propose an Adaptive Weighted Clustering Protocol (AWCP), specially designed for vehicular networks, which takes the highway ID, direction of vehicles, position, speed and the number of neighboring vehicles into account in order to enhance the stability of the network topology. However, the multiple control parameters of our AWCP, make parameter tuning a nontrivial problem. In order to optimize the protocol, we define a multi-objective problem whose inputs are the AWCP's parameters and whose objectives are: providing stable cluster structures, maximizing data delivery rate, and reducing the clustering overhead. We address this multi-objective problem with the Nondominated Sorted Genetic Algorithm version 2 (NSGA-II). We evaluate and compare its performance with other multi-objective optimization techniques: Multi-objective Particle Swarm Optimization (MOPSO) and Multi-objective Differential Evolution (MODE). The experiments reveal that NSGA-II improves the results of MOPSO and MODE in terms of spacing, spread, ratio of non-dominated solutions, and inverse generational distance, which are the performance metrics used for comparison.

I. INTRODUCTION

Vehicular Ad hoc NETworks (VANETs) were deployed to make communication between a set of vehicles possible using ad hoc wireless devices. Nowadays, these networks are used for a wide range of applications which can be divided into the following three categories: safety services, traffic management and user-oriented services. Vehicle To Vehicle communication (V2V) enables each vehicle to provide a warning in real time when a critical event is predicted. The warning message can be either through a seat vibration, tone or visual display or combinations of these indicators. Moreover, in order to make V2V communication work, the FCC (Federal Communication Commission) [1] has established a wireless protocol similar to WiFi, called Dedicated Short Range Communications or DSRC [START_REF]The FCC DSRC (Dedicated Short Range Communications[END_REF]. The DSRC radio technology is defined in the frequency band of 5.9 GHz with a total bandwidth of 75 MHz. This band is divided into 7 channels of 10 MHz for each one. These channels comprise one Control CHannel (CCH) reserved for the exchange of periodic and high priority messages and 6 Service CHannels (SCHs) dedicated to data transmission.

Due to high vehicle mobility, supporting network connection introduces a high communication overhead for exchanging and updating the topology information [START_REF] Tonguz | Broadcasting in VANET[END_REF]. For instance, in a flat-topology network, each vehicle is required to periodically maintain its own connectivity to other one hop neighboring vehicles. Without using expensive components such as central points, establishing of a hierarchical clustering structure within the network can reduce the relative mobility between neighboring vehicles, and communication overhead [START_REF] Rawashdeh | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF]. The clustering allows the formation of organized groups used to coordinate the channel access [START_REF] Hadded | An Adaptive TDMA Slot Assignment Strategy in Vehicular Ad Hoc Networks[END_REF], to simplify routing [START_REF] Song | A cluster-based directional routing protocol in vanet[END_REF], and security [START_REF] Devi | A Cluster Based Authentic Vehicular Environment for Simple Highway Communication[END_REF]. However, the main issue for clustering protocols in VANETs is ensuring topology stability which motivates the need for an efficient clustering protocol that takes into account many mobility metrics to form stable clusters, and also maintains the current cluster structure with less overhead. In this paper we propose a multi-metrics based Adaptive Weighted Clustering Protocol (AWCP) that takes advantage of the geographic information of vehicles. The main contributions of the paper are listed below:

• We propose a clustering protocol based on the WCA algorithm [START_REF] Chatterjee | WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[END_REF] for VANETs in which a vehicle only considers neighbors moving on the same highway and in the same direction, and ignores other broadcast messages.

• We define a solution vector of real and integer variables that can be fine tuned to obtain an efficient AWCP configuration.

• We formulate the parameter tuning problem of the AWCP protocol as a Multi-Ojective Linear Programming MOLP and we propose an optimization strategy in which the Non-dominated Sorting Genetic Algorithm, version 2 (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] is combined with a ns2 simulator to solve the MOLP problem.

• We use realistic VANET mobility scenarios taken from the metropolitan area of Tunis (Tunisia), in order to find and validate the best optimal configuration.

The rest of the paper is organized as follows. In Section 2, we present related work. Section 3 presents our clustering protocol called AWCP. Section 4 describes the AWCP Quality of Service (QoS) problem and identifies the AWCP parameters and performance criteria. Section 5 describes the optimization methodology which consists in combining an NSGA-II and a network simulator to determine the optimal parameters of AWCP. Section 6 shows the simulation results and the performance evaluation. Finally, conclusions and future work are reported in Section 7.

II. RELATED WORK

Several studies focus on developing clustering protocols for VANET, most of which are based on Mobile Ad hoc NETwork (MANET) clustering techniques. However, none of the protocols proposed takes highways ID into consideration when forming clusters formation in VANETs. As a result, these protocols do not create a stable clustering architecture. Some of these proposed protocols are described below.

In [START_REF] Almalag | Using Traffic Flow for Cluster Formation in Vehicular Ad-hoc Networks[END_REF], the authors propose a lane-based clustering algorithm designed to extend the cluster lifetime and reduce the communication overhead. The cluster head is selected based on the lane where most of the vehicles will flow. The authors suppose that each vehicle knows its exact lane on the road via a lane detection system and an in-depth digital street map that includes lane information. A Lane Weight (LW) metric is applied for each traffic flow in order to select the most stable cluster head. The clustering algorithm involves only the cluster formation phase where all vehicles are assumed to follow a steady roadway and does not involve a cluster maintenance phase where the vehicles change their directions or lanes. A Multi-Head Clustering Algorithm was proposed in [START_REF] Lo | A Multi-Head Clustering Algorithm in Vehicular Ad Hoc Networks[END_REF]. This algorithm intends to create stable clusters and reduce re-clustering overhead by supporting single and multiple cluster heads. In the cluster head election phase, all vehicles that are in communication range of each other are organized into clusters and one vehicle for each cluster is elected to act as a Master Cluster Head (MCH). Then, some cluster members from a cluster are selected to be Slave Cluster Heads (SCHs). In order to form stable clusters, the authors have imposed that all the vehicles in a cluster are moving in the same direction. The authors proposed in [START_REF] Rawashdeh | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF] a multi-metric algorithm for cluster head elections suitable for highway area with the aim of achieving better results for network stability as well as decreasing the dynamic nature of VANETs. In addition to the position and the direction, this algorithm uses a speed difference metric as a new parameter to increase the cluster lifetime. The vehicles that are moving at high speed are regrouped into one cluster while the vehicles moving at low speed are grouped into another cluster. Several other clustering algorithms designed for MANETs are also used in VANETs and are frequently employed for comparison with other VANET clustering protocols. For instance, the Lowest-ID clustering algorithm [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF] is based on electing a node with the smallest ID as a cluster head, where each node has a fixed ID. The Weighted Clustering Algorithm (WCA) [START_REF] Chatterjee | WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[END_REF] elects a node to act as a cluster head based on a combined weight which includes its average speed, and battery-life, the number of its neighbors and their average. However, the behavior of these clustering protocols is highly influenced by small changes in the set of their config-uration parameters such as cluster size, hello interval, election interval, timeout interval, etc.). Moreover, the authors do not provide guidelines to tune and optimize them for various mobility scenarios. Therefore, finding the best setting of parameters for optimally configuring these protocols is a major issue. Several mono-and multi-objective optimization algorithm based approaches have been proposed in the literature for optimally configuring communication protocols in VANETs and MANET networks. For instance, Garcìa-Nieto et al. have used different meta-heuristic algorithms to optimize the QoS of the AODV protocol [START_REF] Garcìa-Nieto | Automatic parameter tuning with metaheuristics of the AODV routing protocol for vehicular ad-hoc networks[END_REF] and a file transfer protocol [START_REF] Garcìa-Nieto | Automatic tuning of communication protocols for vehicular ad hoc networks using metaheuristics[END_REF] in realistic VANET scenarios. In [START_REF] Abdou | Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks[END_REF] and [START_REF] Pérez Pérez | Multi-objective Algorithms to Optimize Broadcasting Parameters in Mobile Ad-hoc Networks[END_REF], different multi-objective optimization algorithms are proposed to find an optimal parameter set for broadcasting methods in MANETs. Recently, Iturriaga et al. [START_REF] Iturriaga | A Parallel Multi-objective Local Search for AEDB Protocol Tuning[END_REF] presented a novel parallel multi-objective local search to optimize the energy efficient broadcasting algorithm by maximizing the coverage and minimizing the energy, the broadcasting time and the network resources. In this study, we propose a cluster protocol named AWCP specifically designed for VANET which takes mobility information into account in order to provide stable clusters with a long lifetime. In addition, due to the high number of possible configurations, we define a multi-objective optimization problem where we apply the non-dominated sorted genetic algorithm NSGA-II to find the optimal values of the parameters of the AWCP protocol.

III. THE ADAPTIVE WEIGHTED CLUSTERING PROTOCOL

AWCP is an improvement of the WCA [START_REF] Chatterjee | WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[END_REF] protocol which classifies vehicles into groups based on their highway ID and direction. Since the clusters with vehicles which are moving in different directions and with different highway IDs are unstable, we impose that all the vehicles in a cluster have the same highway ID and the same direction.

A. System Model

Our algorithm is based on the assumption that each vehicle in a VANET can know its highway ID (see Figure 1) via a digital road map and a positioning system, e.g. GPS (Global Positioning System) or a GALLILEO receiver that also allows it to obtain an accurate real-time three-dimensional geographic position (latitude, longitude and altitude), direction, speed and exact time. In the following sections, we describe how AWCP elects a cluster head and maintains a stable cluster structure able to mitigate the VANET issues related to network connection and to reduce the relative mobility between neighboring vehicles with less communication overhead.

B. Cluster Head Election

Initially, all vehicles are in the Undecided State (US). To divide the network into clusters, each vehicle changes its state to Cluster Head Candidate (CHC) and it starts to broadcast a HELLO message periodically for each interval Hello Interval containing all of the necessary information (highway ID, direction, position, speed) to its One-Hop neighbors (OH).

In order to form stable clusters, each vehicle only considers neighbors moving on the same highway and in the same direction, and ignores broadcasts from other vehicles. Upon reception of a HELLO message from all one-hop neighbors, Fig. 1. VANET mobility scenario taken from the metropolitan area of Tunis each vehicle i will calculate its current weight W i using (1). We have defined the election function W i based on the function defined in [START_REF] Chatterjee | WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[END_REF]. The most stable vehicle that can act as a Cluster Head (CH) is a vehicle which has the minimum average distance to the other vehicles in the cluster, the closest speed to the average speed and the maximum number of neighboring vehicles.

W i = w 1 * D i + w 2 * |ν i -∆ i | -w 3 * N i (1)
Where D i = ( ∑ j∈OHj dist(j, i))/N i is the average distance between vehicle i and its one-hop neighbors

(OH i ), ν i is the speed of vehicle i, ∆ i = ( ∑ j∈OHi ν i )/N i
is the average speed of the vehicles, and N i is the number of one-hop neighbors of vehicle i. The corresponding weight factors are such that ∑ 3 i=1 w i = 1. Then, each node i will periodically broadcast an election beacon for each interval Election Interval containing all of the necessary information for the CH election algorithm. The election beacon for vehicle i contains its: ID, CH-ID which indicates the ID of the CH to which the node is attached, Highway ID, direction, and current Weight. Node i then announces itself as a CH by assigning its own ID to the ID field of the election beacon. When a vehicle i receives beacons, from its one-hop neighbors, it sorts its neighbor list OH i according to the weights received in the beacons, and then it executes the cluster head election algorithm to change its status from CH to Cluster Member (CM), Cluster Gateway (CG) or remain CH. Figure 2 shows an example of 1-hop clusters formation on two highways by applying our cluster protocol. The vehicle i that has the minimum value of W i is elected as the CH. Then, all vehicles that are within transmission range of the CH become CMs or CGs and are not allowed to participate in another cluster head election procedure. The CH election algorithm terminates once all the vehicles either become a CH, CM or a CG. Algorithm 1 outlines the details of the CH nodes' election. It is executed by each vehicle i having at least one neighboring vehicle. In Algorithm 1, i, j, and x represent three vehicles which are moving in the same highway and on the same direction and are participating in the CH election process, while S i is the current state of vehicle i. In addition, Cluster Size is the size of the cluster, ITJ Interval is the time interval for a CH vehicle to broadcast the Invite-To-Join (ITJ) message, PRE Interval is the time interval for a CM to signal its presence to its CH, while CH Timeout Interval is the time interval for a vehicle to elect itself as a CH, if it did not receive or broadcast any messages or any ITJ messages during this period.

C. Cluster maintenance

In VANETs, a vehicle can join or leave a cluster at any time. These two operations will have only local effects on the topology of the cluster if the vehicle is a CM. However, if the vehicle is the CH, it must hand over the responsibility to one of the very close cluster members before leaving the cluster. The first reason for that is to maintain the cluster structure even if the current CH leaves. The second reason is to avoid using the re-clustering algorithm and thus no re-clustering overhead is generated when the CH leaves the cluster. Then, the current CH will order the CM to switch to CH and switch its own state to CM.

1) Join a Cluster:

The cluster head periodically broadcasts an ITJ messages to its one-hop neighbors. Once a US or CHC vehicle receives an ITJ message, and if it wishes to join the cluster, it will check the received signal strength. The US or CHC vehicle will consider the ITJ message to be valid if its signal strength is greater than the predefined threshold denoted by Pr Threshold. When receiving a valid ITJ message, the vehicle sends a Request-To-Join (RTJ) message including the vehicle's highway ID, position, speed and direction. When the CH receives the RTJ message, it checks the direction of the requesting vehicle and, if it is in the same highway and moving in the same direction, the CH sends an acknowledgment (ACK) including its ID number. After the reception of the ACK, the corresponding vehicle becomes a CM of this cluster. Once a US vehicle becomes a CM, it is not allowed to participate in another cluster head election procedure. If a CM receives an ITJ message from another neighboring CH moving on the same highway and in the same direction, the vehicle will switch from the CM state to the CG state.

2) Leaving a Cluster: A vehicle remains in the CM state as long as it receives an ITJ message from its CH every ITJ Interval. When the CM vehicle does not receive an ITJ message from its CH during CH Timeout Interval, it considers that it has lost contact with the CH and thus switches its state to CHC. Each CH updates a timestamp field for each CM based on the PRE-MSG messages received. The CH removes a CM from its cluster members list if the difference between the current time and the last time stamp of the PRE-MSG message received from it is greater than CM Timeout Interval. The CH end if 45: end while will change its state to CHC, if its list of cluster members is empty.

3) Merging two or three clusters: When two or three CHs moving on the same highway and in the same direction receive an ITJ messages from each other with a signal strength greater than the predefined threshold Pr Threshold, only one of them will keep its CH responsibility while the others will switch to a CM. The CG between clusters becomes CM of the new cluster, and each CM whose CH has become a CM will remain a CM if it receives an ITJ message from the new CH, and will switch to CHC otherwise. The selection of a cluster head for merging clusters is done based on the weight W i .

IV. AWCP PARAMETERS AND PERFORMACE CRITERIA

The performance of AWCP depends on the selection of the parameter settings that determine its behavior. For instance, the detection of topological changes can be adjusted by changing the Hello Interval parameter. We have defined a solution vector of real variables that can be fine tuned by using an optimization technique with the aim of obtaining QoS efficient AWCP configuration. Table I shows the parameters of AWCP and their variation ranges. These parameters are four timers, four counters and three weighting factors. The variation ranges of the four timers and the first two counters are set based on the clustering protocols proposed in the literature. The Cluster Size is the maximum number of vehicles in the cluster which should be less than (R * l) * 2/(w+d), where R, l, w and d are respectively the transmission range, the number of road lanes, the standard length of the vehicles which is about 3m and the safety distance. P min is the received signal strength where the distance between two vehicles is equal to the safety distance, where P max is the received signal strength where the distance between two vehicles is equal to 3 * R/4. A given AWCP configuration is evaluated based on three of the most widely used QoS metrics in this area [START_REF] Rawashdeh | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF]: The Average Cluster Lifetime (ACL), which is the average time period from the moment when a vehicle becomes a CH, CM or CG to the time when it changes its state. The Control Packet Overhead (CPO), which is the rate of AWCP control packets used to form and maintain the cluster structures. And finally, the Packet Delivery Ratio (PDR), which is the ratio of the number of data packets that are correctly delivered to their destinations. Figure 3 shows the values of the three optimized objectives for different AWCP configurations. From this figure, it is clear that the performance of AWCP depends on the choice of the tuning parameters. Due to the conflicting nature of the objective functions and the large size of the search space, AWCP parameter tuning is an NP-hard problem due to the huge number of possible configurations [START_REF] Toutouh | Green OLSR in VANETs with Differential Evolution[END_REF]. Hence, we formulated AWCP parameter tuning as a multi-objective problem and we have proposed an optimization tool which consists in combining a non-dominated sorting genetic algorithm, version 2 (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] and a network simulator ns2 to determine optimal parameters of AWCP.

V. NSGA-II BASED APPROACH FOR AWCP OPTIMIZATION

A. Overview of NSGA-II

Optimizing a group of conflicting objective functions is no simple task. For simplicity, we assume that all objective functions should be minimized. In fact, the multiplication of some objective functions by -1 allows one to transform a maximization to minimization. Thus, the Multi-objective Optimization Problem (MOP) can be formulated as follows:

(M OP ) { min f k ( -→ x ), k = 1, . . . , m s.t lower(x i ) ≤ x i ≤ upper(x i ), i = 1, . .

. , n

The vector -→ x = (x 1 , . . . , x n ) T ∈ S is the vector of n decision variables. The lower(x i ) and upper(x i ) are respectively the lower and upper bounds of the variable x i . These bounds define the decision space S. Let a minimization MOP be a solution -→ x i ∈ S which dominates the solution -→ x j ∈ S (it is denoted by -→ x i ≺ -→ x j ) if the following conditions are satisfied:

i) f k ( -→ x i )) ≤ f k ( -→ x j ) ∀ k ∈ {1, . . . , m} ii) ∃ k ∈ {1, . . . , m} such that f k ( - → x i ) < f k ( - → x j )
The set of optimal solutions is composed of the non-dominated vectors, often called the Pareto front and also denoted

P F * = { -→ x ∈ S | - → x ′ ∈ X, - → x ′ ≺ -→ x }.
In other words, the Pareto front is the set of compromise solutions. The goal of the multiobjective optimization is to find the Pareto front for a given problem. The NSGA-II algorithm [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF] is often used to solve the multi-objective optimization problem. This method is a multi-objective version of the genetic algorithm in which the solutions explored are classified into Pareto-optimal fronts.

B. Proposed approach

The proposed approach is based on the NSGA-optimization tool, a network simulator and the ns2-trace analyzer (see Figure 4). These three modules cooperate to determine the optimal AWCP configuration in different mobility scenarios. Firstly, the optimization tool generates a set of possible parameters which are transmitted to the network simulator. Thereafter, the simulations are launched and the trace file is built. This file is passed on to the third module (trace analyzer) which computes the values of the fitness functions. The calculated objective values are then transmitted to the optimization tool which evaluates and ranks the solutions according to these values. Then, the optimization tool runs its operations to regenerate another set of possible solutions. This process starts again, until the stop criterion is reached. Below, we describe the NSGA-II based optimization tool. Child ← crossover(P c , parents)

P Itr+1 ← P Itr+1 ∪ F i 19: i ← i + 1 20:
end while

21:

ranking(F i , crowding distance)

22:

Itr ← Itr + 1

23:

P Itr ← P Itr ∪ {N -|P Itr | f irst solutions in F i } 24: end while NSGA-II begins from an initial population (P) made up of solution vectors called "individuals". At each iteration, an auxiliary population Q is formed by applying the crossover and mutation operators (lines 7 to 13). Then, both the current (P) and the new population (Q) are merged together to form one set of solutions R, which will be sorted according to the non-domination and crowded comparison (line 15). For more details, one can see [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. Finally, only the best individuals in R can be included in the next generation and will participate in the production step while the other individuals are deleted (lines 17 to 23). These steps are repeated until the maximum number of iterations is reached.

Each individual i in iteration l is encoded as a multi- dimensional vector -→ x i itr=l = (x i 1 , . . . , x i n ) T .
Each gene that encodes one AWCP parameter is defined by its type (real, integer), bounds and its precision p. The initial population P Itr=0 = { -→ x i Itr=0 , . . . , -→ x N Itr=0 } is generated by randomly choosing the value of each gene in its variation range (lower(x i ), upper(x i )).

-→ x i j,Itr=0 = lower(x i )+rand[0, 1] * (upper(x i )-lower(x i )) i = 1, . . . , n and j = 1, . . . , N

Where N is the population size, n is the vector's dimension. Thereafter, the initial population is used by the circulated genetic operators to create a new population.

The crossover operator is one of the main parts of NSGA-II. The input of this operator consists of two solution vectors (known as parents), while the output is two child vectors, which have certain features from both parents [START_REF] Hadded | Hybridization of genetic algorithms and tabu search approach for reconstructing convex binary images from discrete orthogonal projections[END_REF] (see Figure 5). Because all the genes in each solution vector of the population are within their given intervals, the resulting vector should satisfy the formulated constraints in Section V. The two most used types of crossover operators are two-point crossover and uniform crossover. In this study, we found that the NSGA-II using uniform crossover outperforms the NSGA-II using two-point crossover in terms of the obtained children quality. In uniform crossover operator, a crossover mask -→ x = (x i ) T ∈ {0, 1} n is randomly computed, which determines from which parent vector each gene will inherit. Then, each gene i will be assigned to the first parent if x i = 1, otherwise it will be assigned to the second parent. After recombination, the mutation operator is applied to randomly change some genes in an individual. This operator serves as a strategy to prevent solutions from being trapped in local optima. After mutation, if one or more of the genes in any new individual j are outside of their ranges, the individual -→ x j is repaired according to the flowing rule:

(x j i ) 1≤i≤n =      lower(x i ) + x j i +lower(xi) 2 if x j i < lower(x i ) lower(x i ) + x j i -upper(xi) 2 if x j i > upper(x i ) x j i otherwise
Since the crossover and the mutation operator generate a list of new solution vectors, a set of ns-2 simulations are launched to compute the objective values.

VI. SIMULATION RESULTS AND PERFORMANCE EVALUATION

We carried out a set of experiments to prove the ability of NSGA-II coupled with the ns2 simulator to provide optimal performances, as well as its ability to fine tune the optimal values of the AWCP parameters. The optimization tool was implemented in Java while the simulation phase was carried out by running ns-2.34. Moreover, all our experiments were conducted using 2 desktop computers Intel Core i5 3.2GHz with 4 Gb of memory and O.S. Linux Ubuntu 12.04. In order to achieve the best optimal behavior of the AWCP protocol, several experiments on various VANET scenarios were necessary. In this section, we present the set of VANET scenarios used to obtain efficient QoS AWCP parameters and the experimental validation.

A. VANET scenarios

We generated a realistic VANET environment by selecting a real highway area from a digital map which took into account road directions, road intersection, highway bridges, and traffic rules. Figure 1 shows a metropolitan area from the Map of Tunis of size 4 km × 4 km exported form OpenStreetMap (OSM) and edited using Java OpenStreetMap Editor (JOSM). Then SUMO [START_REF] Krajzewicz | The open source traffic simulation package SUMO[END_REF] and MOVE [START_REF] Karnadi | Rapid generation of realistic mobility models for VANET[END_REF] were used respectively to generate vehicle traffic scenarios and to simulate the area with vehicular traffic. To generate vehicular traffic by MOVE and SUMO, we defined for each direction a vehicle flow which described a swarm of vehicles. The parameters of each vehicle flow consisted of the maximum number of vehicles, the starting road and destination of the flow, the time to start and end the flow and the probabilities of turning to different directions at each junction (0.4 to go straight, 0.3 to turn left and 0.3 to turn right). Then the traffic traces generated by MOVE were used in the ns2 simulations. All the tests were performed on different VANET scenarios taking into account different vehicle densities and data loads: Low, Medium, High and Very High. The features of the VANET scenarios and the simulation parameters used in our experiments are summarized in Tables II andIII.

B. NSGA-II Results Analysis

This section presents and analyses the results of applying NSGA-II for the AWCP tuning problem. For these results, the size of the initial population was 30 individuals, the number of generations was fixed to 40, the crossover probability was 0.9, whilst the mutation probability was fixed to 0.1. We perform 30 independent runs of the NSGA-II algorithm in which the candidate individuals were evaluated by running the simulation in the High scenario. The computational time for each run was 37618.95 seconds (about 10.45 hours) with a deviation of 6.78 (about 13 days for 30 independent runs). After the experimentation, we identified a set of Pareto optimal solutions of size τ = 79 by gathering all the non-dominated solutions found in the 30 independent runs. These solutions give different degrees of trade-offs between three QoS metrics and they are bounded by a so-called ideal objective vector z ideal which contains the optimal value for each separate objective.

(z ideal j ) 1≤j≤k = min f j ( -→ x i ) ; i = 1, . . . , τ
Table IV shows the solutions that give the best values for each AWCP QoS metric, which are the maximum ACL (max-ACL), maximum PDR (max-PDR), and minimum CPO (min-CPO), and the average values of the τ non-dominated solutions obtained on the Pareto front. As shown in this table, in our case the ideal vector has three values : 94.06, 91.39, 3.82. Moreover, the Euclidean distance of each solution in the non-dominated set to the ideal objective vector is calculated and the solution with the smallest Euclidean distance is selected (min-EUDT). We can note that the closet configuration to the ideal objective

C. NSGA-II Results Validation

In this section we present the results obtained by other multi-objective optimization approaches: Multi-Objective Differential Evolution (MODE) and Multi-Objective Particle Swarm Optimization (MOPSO) which are the most recently used to optimize communication in ad hoc networks presented in [START_REF] Yetgin | Multi-objective routing optimization using evolutionary algorithms[END_REF] and [START_REF] Ali | Energy-efcient clustering in mobile adhoc networks using multi-objective particle swarm optimization[END_REF], respectively. The parameter settings of these optimization algorithms are shown in Table V. To demonstrate the distribution of non-dominated individuals on the objective space for each Multi-Objective Evolutionary Algorithm (MOEA), we have considered the two scenarios S1 and S3 as illustrative scenarios. Figure 9 depicts the Paretofront obtained by gathering all the non-dominated solutions found in the 30 independent runs corresponding to these scenarios. The figure 9 shows that for scenario S1, NSGA-II offers 36.24% and 36.36% more non-dominated solutions than MOPSO and MODE, respectively. For the Scenario S3, it offers 38.24% and 54.41% more non-dominated solution than MOPSO and MODE, respectively. In addition, we note from the figure 9 that MODE has significantly failed to attain a wide non-dominated set both as well as it gives a poor distribution of non-dominated points. Although MOPSO has attain a small Pareto front compared to NSGA-II, it shows its ability to find a well-diversified non-dominated solutions set.

In order to compare better the performance of different MOEAs, we evaluate the Pareto fronts (P F ) obtained by the three approaches in terms of spacing, spread, generation distance, Ratio of non dominated solutions, and computational time metrics. The goal from this comparison is to demonstrate the effectiveness of NSGA-II on different VANET scenarios. Table VI presents the average (and the standard deviation) of the four metrics as well as the computational time taken by each MOEA over 15 independent runs. This table shows that the NSGA-II is significantly better than the other two MOEAs in terms of both sparsity, spacing, inverse generational distance and the ratio of non-dominated solutions. The average number of non-dominated solutions found by NSGA-II in the 15 independent runs is 80.49%, 85.16%, 83.61% and 86.56% for the S1, S2, S3 and S4 scenarios, respectively. Therefore, the NSGA-II algorithm provides a wide range of non-dominated solutions in every run, whilst MOPSO and MODE give a small number of solutions along the Pareto front. Table VI also shows that all the MOEOs take almost the same computational time. This is due to the fact that all the algorithms have the same number of fitness function evaluations. It can be seen that the Pareto fronts obtained by NSGA-II are the best regarding the spacing and spread metrics on all the test scenarios except for the S4 scenario, where MOPSO is the best in terms of the spread metric. The lowest spacing in scenario S3 is found by NSGA-II with 51.7364.81% respectively better compared to MODE and MOPSO, and the largest spread is also found by NSGA-II (38% better, on average). Thus, the Pareto front solutions obtained by NSGA-II are better distributed with respect to the MODE and MOPSO. Similarly, in terms of inverse generational distance, NSGA-II had the best performance (both in terms of average value and standard deviation). Therefore, with respect to the performance metrics used for comparison, we can conclude that NSGA-II is the most suitable for the AWCP tuning problem. Moreover, the results show that MOPSO and MODE are both the second best with respect to spread, spacing metrics and inverse generational distance, and they are clearly the worst ones in terms of the ratio of non-dominated solutions VII. CONCLUSION Because of the rapidly changing topology and the lack of infrastructure, it is very challenging to deploy clustering methods in vehicular networks. In this paper, we focus on designing an adaptive and optimized clustering algorithm for vehicular networks, called AWCP, that takes into consideration the highway ID, direction, position, and speed information, in order to maximize cluster stability. However, due to the high number of feasible configurations of AWCP and the conflicting nature of its performance metrics, we defined a multi-objective optimization problem where the non-dominated sorted genetic algorithm NSGA-II is coupled with the ns2 simulator to find the optimal parameter values for the AWCP QoS metrics. The NSGA-II optimized configuration is validated by comparing it with the optimized MODE and MOSPO configurations on realistic VANET scenarios taken from the metropolitan area of Tunis (Tunisia). The experimental results show that the NSGA-II algorithm obtains well-distributed solutions over the Pareto front and presents the best results in terms of performance metrics. Thus, NSGA-II algorithm is more suitable for the AWCP parameter tuning problem.

Since the computational time required to perform 15 independent runs for all MOEAs in the S4 scenario is about 32 days, a parallel version of MOEAs running on multiple processors would allow larger populations and more generations to be used in this multi-objective optimization method while reducing the computational time required for very large scale VANET scenarios. Moreover, channel efficiency in VANETs could be improved by the development of a crosslayer architecture (MAC/AWCP) in which each cluster head is responsible for assigning bandwidth to all the members of its cluster.

Fig. 2 .

 2 Fig. 2. Example of 1-hop cluster formation on two highways

Fig. 3 .

 3 Fig. 3. Distribution of solutions on the objective space.

Fig. 4 .

 4 Fig. 4. NSGA-II based approach for AWCP optimization

Fig. 5 .

 5 Fig. 5. Uniform crossover operator example

Fig. 6 .

 6 Fig. 6. 3D Pareto fronts returned by the NSGA-II, MOPSO and MODE algorithms for the S1 and S3 VANET scenario.

  Algorithm 1 Cluster head election 1: S i ← CHC 2: OH i ← ∅ 3: i initializes timer 1 4: while timer 1 ! = 0 do

	5:	Upon reception of election beacon form vehicle j,
		vehicle i will check:
	6:	if j is traveling in the same highway and in the
		direction then
	7:	Receive and store W j value
	8:	else
	9:	Do nothing
	10:	end if
	11: end while
	12: while OH i ! = 0 and S i == CHC do
	13:	The vehicle i sorts its OH i list
	14:	v ← head of OH i
	15:	if (i == v) then
	16:	S i ←CH
	17:	for every ITJ Interval second do
	18:	Vehicle i broadcasts an ITJ message
	19:	end for
	20:	i initializes timer 2
	21:	while timer 2 ! = 0 do
	22:	if i receives an RTJ from another vehicle x
		then
	23:	if The current number of CM vehicles <
		Cluster Size then
	24:	i will send an ACK message to x
	25:	end if
	26:	end if
	27:	end while
	28:	else
	29:	i sends an RTJ message to v
	30:	i initializes timer 3
	31:	while timer 3 ! = 0 do
	32:	if i receives an ACK from v then
	33:	S i ←CM
	34:	CH -ID ← v
	35:	for every PRE Interval second do
	36:	i Sends a presence message to its CH v
	37:	end for
	38:	else
	39:	if i remains in the US or in the CHC state
		more than CH Timeout Interval seconds then
	40:	S i ←CH
	41:	end if
	42:	end if
	43:	end while
	44:

TABLE I .

 I AWCP PARAMETERS

	Parameter	Type	Lower bound	Upper bound
	Hello Interval	R	0.5	15
	Election Interval	R	0.5	15
	ITJ Interval	R	1	15
	PRE Interval	R	1	15
	CH Timeout Interval	R	2	45
	CM Timeout Interval	R	3	45
	Cluster Size	Z	1	(R * l) * 2/(w + d)
	Pr Threshold	R	Pmin	Pmax
	Distance Weight factor (w1)	R	0	1
	Speed Weight factor (w2)	R	0	1 -w2
	Neig Weight factor (w3)	R	0	1 -(w1 + w2)

R

  Itr ← P Itr ∪ {Q Itr }

	10:	E ← mutation(P m , Child)
	11:	compute objective values(Child)
	12:	Q Itr ← Q Itr ∪ {Child}
	13:	end while
	14: 15: 16:	R Itr = P Itr+1 ← {∅}; i ← 0 ∪ r i=1 F i and F 1 < F 2 < . . . < F r
	17:

while (|P Itr+1 | + |F i | < N ) do 18:

TABLE II .

 II VANETs scenarios

	Scenario	Number of vehicles	Number of CBR sources
	Low (S1)	25	5
	Medium (S2)	50	15
	High (S3)	100	25
	Very High (S4)	150	35

TABLE III .

 III Simulation parameters in ns-2 W 1 = 0.716, W 2 = 0.204, and W 3 = 0.07.

		ITJ Interval=7.23, PRE Interval=9.16, Pr Threshold= 7.23E-
		16, CH Timeout Interval=12.75, CM Timeout Interval=12.7,
		Cluster Size=50,
	Parameter	Value/Protocol
	Simulation area	4000 × 4000 m 2
	Simulation time	100 s
	Vehicle speed	120 -150 km/h
	Propagation model	T wo Ray Ground
	Medium Capacity	6 M bps
	PHY/MAC Layer	IEEE 802.11p
	Transmission range	1000 m
	Transport Layer	U DP
	CBR Packet Size	512 bytes
	CBR Time	60 s
	vector (min-EUDT) presents the best trade-off between the
	three QoS metrics, since the min-EUDT configuration gives
	the best objective values for each QoS metric. The max-ACL
	configurations achieve a high cluster lifetime and have a high
	packet delivery performance but the clusters are formed and
	maintained with an excessive overhead (12.68%). The config-
	uration that optimizes the PDR metric, max-PDR, delivers an
	important amount of data packets. However, it decreases the
	performance of the AWCP protocol in terms of ACL (79.71s).
	The configuration that creates clusters with the least overhead
	min-CPO, produces a significant reduction in the performance
	of AWCP in terms of ACL (45.81%) and it delivers a low
	packet delivery ratio although it has the advantage of fewer
	control messages.
	The min-EUDT AWCP configuration found by NSGA-
	II which is the most balanced setting of parameters on the
	Pareto front is Hello Interval=0.78, Election Interval=0.16,

TABLE IV .

 IV NSGA-II simulation results and optimized configuration

	Configuration	ACL	PDR	CPO	EUDT
	max-ACL	94.06 s	89.05%	12.68%	9.16
	max-PDR	79.71 s	91.39%	7.15%	14.73
	min-CPO	45.81 s	87.46%	3.82%	48.41
	NSGA-II avg	72.75 s	86.92%	6.69%	21.97
	min-EUDT	90.02 s	88.54%	6.72%	5.73

TABLE V .

 V Parameter settings of the optimization algorithms

	Algorithm	Parameter	Symbol	Value
		Local Coefficient	φ1	2.0
	MOPSO	Social Coefficient	φ1	2.0
		Inertia Weigh	w	0.5
	MODE	Crossover Probability	Cr	0.9
		Mutation Factor	µ	0.1

TABLE VI .

 VI PERFORMANCE COMPARISON OF THE THREE MOEAS FOR THE S1, S2, S3 AND S4 SCENARIOS.

	VANET	MOEA	Spacing	Spread	Generational Distance	Ratio of Non-dom. Indiv.	Avg. Time (s)
	Scenario		Average	Std. Dev.	Average	Std. Dev.	Average	Std. Dev.	Average	Std. Dev.	Average	Std. Dev.
		NSGA-II	4.1488621	1.3715102	65.0951358	17.3889108	5.4757908	1.1102958	0.8049462	0.0290881	13713.756	9.20882786
	S1	MOPSO	8.7738382	5.6501962	64.6906121	16.7276727	7.8873787	1.9542785	0.3394872	0.0228335	13708.753	1.51590429
		MODE	5.5034728	3.7037692	41.0385453	9.0122561	9.0198743	1.0459045	0.3220513	0.0815812	13708.639	1.70916315
		NSGA-II	3.5356077	1.3941248	83.3691357	2.8631863	2.9250822	0.3464823	0.8516129	0.0378871	20371.083	15.42677131
	S2	MOPSO	5.7282304	3.0834036	50.3591101	17.6705328	4.5397505	0.7974481	0.3374359	0.0382301	20376.685	25.94725339
		MODE	6.0314481	2.8167532	53.7266384	4.8251813	4.1714498	0.5173664	0.3353846	0.0400279	20364.989	2.21522568
		NSGA-II	2.6947245	0.4488186	63.2152538	11.0507805	3.19493041	0.57833724	0.8361291	0.0454713	37621.929	8.78654352
	S3	MOPSO	4.0882696	4.6216437	31.3271774	13.0102878	6.20288319	1.54514337	0.4446154	0.0210351	37620.885	12.34745823
		MODE	4.4441424	2.1440006	47.0680982	10.9674119	4.85431004	0.48675559	0.4047009	0.0710477	37622.237	10.24696221
		NSGA-II	2.9067278	0.4680387	56.3595601	13.9051238	4.0720004	1.1753562	0.8655913	0.0248012	61609.096	54.65601793
	S4	MOPSO	3.7250376	0.5563667	51.0215217	23.5176434	6.4324167	2.4138273	0.3632479	0.0162842	61639.846	62.56871982
		MODE	6.9208905	1.4750501	68.4428346	3.5243498	4.7408295	0.5201619	0.4170941	0.0415301	61636.257	47.27448427
	A bold font indicates the best metric value.