Yoram Vadée-Le-Brun

Jonathan Rouzaud-Cornabas

Guillaume Beslon
email: guillaume.beslon@inria.fr

Epigenetic inheritance speeds up evolution of artificial organisms

DNA is not the sole medium by which parents transmit information to their offspring. Epigenetic inheritance, in particular, is based on the partial transmission of the cellular state of the parental cell to its descendants. Although the reality of epigenetic inheritance is now firmly established, whether it has an influence on the long term evolutionary process is still subject to debate.

To address this question, we used RAevol, an in silico experimental evolution platform, and defined 4 scenarios with static or dynamic environments and with or without epigenetic inheritance. Simulations in dynamic environments show that protein inheritance indeed increases the rate of evolution on the long term. But they also show that it impedes evolution in its very first stages. This negative effect can be explained by instabilities generated by the interference between the two inheritance mediums. On the opposite, the long term gain can be explained by protein inheritance reducing the constraints on the genetic regulation network.

Introduction

In biology, inheritance (or heredity) typically refers to the fact that offspring look more like their parents than like other random individuals. We call this kind of inheritance "phenotypic inheritance". Mendel, in 1866, established the first rules about phenotypic inheritance. In particular he established that some phenotypic traits are encapsulated in a physical "thing" he called allele and that can be transferred from a parent to its offspring. Then, the discovery of DNA structure gave more support to this idea and we began to call these things "genes". This leads to a subtle semantic switch, genetic inheritance progressively becoming the central dogma to explain any kind of phenotypic inheritance.

Although more and more evidence has accumulated against this dogma [START_REF] Danchin | Beyond DNA: integrating inclusive inheritance into an extended theory of evolution[END_REF], the notion of nongenetic inheritance (i.e., any kind of phenotypic inheritance which is not due to genetic inheritance) was considered as playing a minor role in the evolutionary dynamics of species until the work of [START_REF] Jablonka | The adaptive advantage of phenotypic memory in changing environments[END_REF]. Since then, the precise role of non-genetic inheritance in the evolutionary dynamics of species has been discussed extensively, in particular in the context of "epigenetic inheritance" which is a sub-set of non-genetic inheritance implying the physical transfer of molecular states from the parents to their offspring.

On the one hand, epigenetic inheritance could increase the fitness of the organisms that are able to transmit some molecular structures to their descendence. The main argument that backs this point of view is the fact that epigenetic inheritance allows for the transmission of an acquired phenotype. It can thus increase the mean fitness in case of rapid environmental change by eliminating the lag-time of the plastic response [START_REF] Jablonka | The adaptive advantage of phenotypic memory in changing environments[END_REF][START_REF] Lachmann | The inheritance of phenotypes: an adaptation to fluctuating environments[END_REF][START_REF] Bonduriansky | Nongenetic inheritance and its evolutionary implications[END_REF]. Moreover, as epigenetic inheritance provides heritable phenotypic variation, it creates the possibility to exploit "Stochastic Gene Expression" to survive and maybe adapt to a hostile environmental variation. Indeed, epigenetic inheritance can help transmitting random phenotypic variations that may be less sensitive to this specific environment and thus promote the evolution of new niche-exploitation strategies [START_REF] Bonduriansky | Nongenetic inheritance and its evolutionary implications[END_REF]. Such a behavior has been observed by [START_REF] Adam | Epigenetic inheritance based evolution of antibiotic resistance in bacteria[END_REF]: some E. coli strains become randomly resistant to an antibiotic and can survive and reproduce in this new environment by partially transmitting this resistance trait to their offspring. Finally, epigenetic inheritance allows to increase phenotypic variation by separating the effect of selection on the genotypes and the phenotypes. Indeed, increasing genetic variability could be dangerous because mutations are mostly deleterious and mutations are not reversible. Epigenetic inheritance enables transmission of the adaptive variations while keeping the mutational burden affordable. This can lead to a new strategy for species: when maladapted to an environment they can increase the stochasticity of their gene expression in order to increase their phenotypic variations. Doing so, they increase the probability of finding an adapted phenotype while still being able to transmit it vertically. This could then facilitate evolution toward a new optimum [START_REF] Pál | Plasticity, memory and the adaptive landscape of the genotype[END_REF][START_REF] Pál | Epigenetic inheritance and evolutionary adaptation. In Organelles, Genomes and Eukaryote Phylogeny: An Evolutionary Synthesis in the Age of Genomics[END_REF]. This effect could be enhanced by the ontogenesis in multicellular organisms but this is out of scope of our work.

On the other hand, epigenetic inheritance could decrease the rate of evolution. There are two main points supporting this idea: (i.) If the parent environment and the offspring environment are poorly correlated, non-genetic inheritance can be maladaptive. Indeed, the adaptive plastic response of the parent would interfere with the adaptive plastic response of the offspring in the new environment [START_REF] Bonduriansky | Nongenetic inheritance and its evolutionary implications[END_REF]. (ii.) Non-genetic inheritance is often transmitted with a probability k different of 0.5. This can alter the fair mendelian game and lead to either a maladaptive variation invading the population because of k > 0.5 or an adaptive variation lost because of k < 0.5 [START_REF] Pál | Epigenetic inheritance and evolutionary adaptation. In Organelles, Genomes and Eukaryote Phylogeny: An Evolutionary Synthesis in the Age of Genomics[END_REF].

Unfortunately, there are only few experimental claims in this debate. Most of these assumptions are based on thought experiments and cannot be experimentally studied. Actually, most of the authors still wonder whether epigenetic inheritance really plays a significant role in evolution on the long term. For instance, according to [START_REF] Pál | Epigenetic inheritance and evolutionary adaptation. In Organelles, Genomes and Eukaryote Phylogeny: An Evolutionary Synthesis in the Age of Genomics[END_REF]: "Although the role of epigenetic inheritance during development is generally accepted, it is much less clear whether heritable epigenetic variation can play a significant role during evolution".

To experimentally address this issue, we propose to use an in silico experimental evolution approach. By using an artificial life model, we are able to simulate evolution with and without epigenetic inheritance and to compare the outcomes. To this aim we used the RAevol model, developed in our team (Beslon et al., 2010a,b) to study the evolution of genetic regulation networks. We modified RAevol to allow for the vertical transmission of proteins from a parent to its offspring. In other words, in addition to transmitting its regulation network to its offspring (statically encoded on its genome), a parent also transmits the initial state of this network. Note that this represents only one of the various epigenetic inheritance mechanisms that exist in Nature (e.g. DNA methylation, chromatin structure, protein misfolding...). Furthermore, transmission of proteins is a weak epigenetic transmission because it is easily reversible in case of a plastic response. Nevertheless we show that this mechanisms is strong enough to observe a significant change in the evolutionary dynamics.

This paper is organized as follows: In the next sections, we briefly present the RAevol platform and the way epigenetic inheritance is implemented. We then present our experimental design followed by the results of the simulations which are then discussed. Finally, we conclude and describe our future research directions.

The Aevol -RAevol platform

Aevol is an in silico experimental evolution [START_REF] Hindré | New insights into bacterial adaptation through in vivo and in silico experimental evolution[END_REF][START_REF] Batut | In silico experimental evolution: a tool to test evolutionary scenarios[END_REF] or digital genetics [START_REF] Adami | Digital genetics: unravelling the genetic basis of evolution[END_REF] platform. It was designed to study how the evolutionary conditions shape the molecular structure of an evolving organism (e.g., DNA length, genes number, operonic structures...) due to direct and indirect selective pressures. In Aevol, a population of individuals evolves through a classical mutation-selection process. The specificity of Aevol lies in the genotype-to-phenotype mapping which finely models what is observed in bacteria. A circular double-stranded DNA sequence is transcribed into a set of mRNAs. These mRNAs are then parsed in search for Coding DNA Sequences (CDSs -the "genes") that are translated into proteins through an artificial genetic code. Finally, the proteins are combined to compute the individual's phenotype. Since it is technically impossible to simulate a realistic cellular model, we use a simplified representation. In Aevol the phenotype of an organism is an [0; 1] → [0; 1] mathematical function that represents its metabolism. The fitness is then directly computed by comparing the phenotype with a target function representing the environment. In computational words, Aevol organisms must fulfill a curve-fitting task by combining kernel functions (the proteins) translated from their genomes.

Aevol has been extensively described elsewhere and we refer the reader to previously published work for a complete description of the model and the results obtained so far [START_REF] Knibbe | A long-term evolutionary pressure on the amount of noncoding DNA[END_REF][START_REF] Knibbe | The topology of the protein network influences the dynamics of gene order: From systems biology to a systemic understanding of evolution[END_REF][START_REF] Parsons | Importance of the rearrangement rates on the organization of transcription[END_REF][START_REF] Batut | In silico experimental evolution: a tool to test evolutionary scenarios[END_REF][START_REF] Misevic | Shape matters: Lifecycle of cooperative patches promotes cooperation in bulky populations[END_REF].

RAevol is an extension of Aevol (Beslon et al., 2010a,b). It uses the same genome model and the same genetic code. However, in RAevol, proteins are able to act as transcription factors (TFs) beside their metabolic activity. When acting as a TF, a protein may up-or down-regulate the transcription of other genes, ultimately controlling the concentration of the proteins encoded by these genes. In other words, in RAevol, each individual owns a genetic regulation network that may dynamically modify its phenotype depending on the environmental conditions. Importantly, in RAevol, the phenotype of an organism is no longer a static function (as it is in Aevol). Rather, it becomes a dynamic function that can be evaluated (by comparing it to a target function) at different time steps during what can now be considered as the "life" of the individual.

Technically, RAevol extends Aevol by adding a "transcriptional regulatory code". In the model, the secondary structure of the proteins (i.e., their sequence of Amino-Acids) may contain small motifs that are able to virtually bind on DNA sequences with an affinity that depends on the matching between the motif and the DNA sequence 1 . If a protein is able to bind upstream or downstream from an mRNA promoter, then it respectively enhances or represses it. This results in an up-or down-regulation of the genes transcribed on this mRNA. Once the regulation network has been decoded from the genome, the transcription levels are used to parametrize a set of synthesis-degradation equations (one for each protein) and the dynamic of the network can be simulated step by step, enabling the computation of the dynamic phenotypic function during the life of the individual. In RAevol, the target phenotype may change during the life of the individual, either deterministically or randomly (Figure 1). The individual must then dynamically adapt to the current target by switching between different stable states of its regulation network. To this aim, evolution should optimize the "epigenetic landscape" encoded by the regulation network and create pathways between the different local minima associated to the target phenotypes.

All the details of the RAevol model can be found in (Beslon et al., 2010a,b). Classically, in RAevol, when an individual is created, all the proteins' concentrations are initialized at their basal levels (i.e., the level given by their promoter in the absence of regulation). For the needs of the present experiments, we have introduced a new option in the model: protein inheritance. When this option is selected, any new organism created in RAevol inherits its ancestor's genome (possibly mutated) but it also inherits its ancestor's proteins (i.e., the Amino-Acid sequences and the corresponding concentration values). Conversely, all the proteins encoded in the organism's genome are initialized at zero concentration. Then, due to the synthesis-degradation process, the inherited proteins are progressively degraded while the translated ones reach their steady state (see Figure 2,. If a given CDS has been correctly transmitted from the parent to the offspring (i.e., its coding sequence has not been altered by a mutation or a chromosomal rearrangement), this process results in a constant activity since the inherited protein is exactly replaced by the produced one. However, when a CDS undergoes a mutation, the offspring inherits a protein that it is not itself able to synthesize and produces a protein its parent was not able to produce. This may interfere with the regulation network convergence, hence altering the individual's phenotype. As a consequence, in case of protein inheritance, the fitness of an organism is not only determined by its genome but also by its inherited cytoplasmic material. Both inheritance processes may thus interfere and we can study experimentally how this interference can impact evolution.

Experimental design

As argued in [START_REF] Pál | Plasticity, memory and the adaptive landscape of the genotype[END_REF][START_REF] Jablonka | The adaptive advantage of phenotypic memory in changing environments[END_REF], the dynamic of the environment can be a crucial parameter for the contribution of epigenetic inheritance to evolution. Thus, in order to test whether epigenetic inheritance influences the evolutionary dynamics, we designed 2 series of scenarios. One will test the effect of protein inheritance in a variable environment and the other, in a constant environment.

In both scenarios the individuals live for 20 time steps (Figures 1 and2). However, in the constant environment, the environmental conditions are fixed along the whole evolutionary process. More precisely, the phenotypic target is the sum of four Gaussians regularly spread along the phenotypic axis. On the opposite, in the case of a variable environment, we designed three different environmental conditions that alternate randomly with a switching probability of 10% at each time step (including the first one). In each of these conditions, one of the four Gaussians is active while the three others are inactive (Figure 1). In such an environment individuals can adapt by plasticity since the same conditions are encountered regularly (though randomly). Moreover, since the birth condition of an individual has a 0.9 probability to be its parental one, protein inheritance may reduce the lag time of the plasticity response. We will thus be able to test the theory proposed by [START_REF] Jablonka | The adaptive advantage of phenotypic memory in changing environments[END_REF], to evaluate its contribution to evolution and to seek for additional mechanisms.

To summarize, we have four situations to simulate: variable environment with protein inheritance (V i ), variable environment without protein inheritance (V , control for V i scenarios), constant environment with protein inheritance (C i ) and constant environment without protein inheritance (C, control for C i scenarios).

For each scenario, we launched 4 independent simulations. In each simulation, a population of 1,000 individuals was let evolve for 300,000 generations under a mild mutation rate. All parameters were the same for all the simulations and were chosen according to previous experiments (Mutation rates: 5.10 -6 mut/bp/generation for all kinds of point mutations. Rearrangement rates: 5.10 -5 rearr/bp/generation for all kinds of rearrangements. Fitness proportionate selection. Selection coefficient: 750). Without epigenetic inheritance these parameters were known to lead to a medium complexity organisms with a good final fitness. In particular, they always lead to the emergence of a genetic regulation network as early as 50,000 generations. These parameters (and the relatively low number of repetitions) were chosen as a compromise between long enough evolution time and short enough computation time. Indeed, these simulations already last for more than 1 month on a 16core 3GHz computer. It is important to mention that there is still room for directional evolution after 300,000 generations but previous experiments have shown that the main tendencies are already observed at this stage with the used parameter set. Indeed, during preliminary tests, we ran similar simulations for 800,000 generations without observing dramatic changes in the last period.

Results

All 16 simulations resulted in the emergence of organisms of medium complexity with most genomes ranging from 2,000 to 3,000 bp and approximately 30 genes (Figures 3.a and 3.b). Moreover, all the individuals were able to regulate their transcription and to efficiently respond to the environment changes (in the case of scenarios V /V i ). Figures 2 and4 show the best final V i individual and its genetic regulation network. Note the very fast proteome reorganization after each environment variation (Figure 2, top-right panel).

As RAevol is a precise model of genome evolution, we are able to check whether protein inheritance has a major impact on the genome structure after 300,000 generations. As Figure 3 shows, there is no significant difference in neither the genome structure nor the genetic regulation network between scenarios with or without protein inheritance.

Conversely it is interesting to note that we do observe differences between scenarios C/C i and V /V i for the genome size (Figure 3.b) and average degree of the regulation network (Figure 3.c) but not for the number of genes (Figure 3.a). This strikingly contrasts with the classical hypothesis (see [START_REF] Casjens | The diverse and dynamic structure of bacterial genomes[END_REF] for example) that postulates that a link exists between the complexity of the environment and the size of the regulation network.

Here, the complexity of the environment is clearly higher for scenarios V /V i than for scenarios C/C i . However, the sizes of the regulation networks are similar (Figure 3 the mutation rates rather than the environmental complexity [START_REF] Beslon | Scaling laws in bacterial genomes: A side-effect of selection of mutational robustness[END_REF]. This observation raises very interesting questions regarding the origin of molecular complexity. Although no clear molecular difference was observed between the protein inheritance scenarios (C i /V i ) and their control (C/V ), Figure 3.d shows a slight difference between them in terms of the individuals' performances. Indeed, the comparison of the mean metabolic error 2 of each scenario 2 In Aevol/RAevol the adaptation of an individual is measured by its "metabolic error" i.e., the total difference between its phenotypic function and the target function. Note that the lower the shows us that scenarios V i and C i have lower metabolic error than scenarios V and C respectively (note that statistical accuracy cannot be reached with only 4 repetitions).

To understand this result, one can look at the evolution of metabolic error over time. Figure 5 clearly shows that protein inheritance accelerates the decrease of the metabolic error during the second phase of evolution (from 150,000 to 300,000 generations). However when looking qualitatively at the curves, we can notice that the evolutionary dynamic is clearly different with or without protein inheritance. In particular scenario C i is characterized by long stasis phases separated by avalanches of favorable mutations, a situation that is not observed for scenario C. On the opposite, scenario V i shows large fluctuations of metabolic error during the first phase of evolution (generation 0 to 50,000). These fluctuations initially slow-down evolution but scenario V i ultimately catch up with scenario V because of a more regular evolution from generations 50,000 to 300,000. We can thus propose the hypothesis that the effects of protein inheritance are different depending on the evolutionary phase. Indeed, it seems to have a negative impact during the first evolution period (i.e., when the network is being constructed by node recruitment) while its impact is clearly beneficial in the second period (i.e., when the network structure is mostly stable but when the links are being optimized).

This hypothesis is confirmed when observing the evolution of the mean relative advantage given by protein inheritance over time. Indeed, Figure 6 confirms that the impact of protein inheritance is different in a constant environment and in a variable environment and that protein inheritance influence shows strong variations along the evolutionary process. For scenarios C/C i , the advantage is slightly negative until generation 200,000 but with large fluctuations. Then it becomes stable and positive at almost 14%. This behavior is a direct consequence of the long evolutionary stasis phases metabolic error, the better the individual (contrary to the usual fitness measures). previously observed for scenario C i (Figure 5). Moreover these phases are separated by large drops in the metabolic errors. Thus the relative advantage/disadvantage of protein inheritance is driven by stochastic events (the beneficial mutation avalanches). Given the low number of repetitions, this results in the large fluctuations observed on figure 6.. For scenarios V /V i , we observe a huge disadvantage of protein inheritance that reaches -40% at generation 20,000. However this is rapidly compensated and protein inheritance becomes favorable as soon as generation 70,000. This is due to large fluctuations in the metabolic error in two repetitions of scenario V i (Figure 5). Once these fluctuations stop, all the simulations rapidly reach a higher fitness than in scenario V . Interestingly, similar fluctuations are observed for the evolution of the number of CDSs (Figure 7). This confirms that the negative impact of protein inheritance is linked to the process of node recruitment by the regulation network.

As shown previously, during the second phase of the evolutionary process, protein inheritance seems to favor evolution whatever the conditions. However the advantage it provides can be due either to some facilitating process that would accelerate evolution or to a more "mechanical" effect: As explained above, protein inheritance can directly decrease the metabolic error because it enables transmission of an acquired phenotype. This is likely to be favorable when there is a high probability that an offspring faces the same conditions as its parents. In our simulations, this effect is likely to play an important role since the probability for an individual to begin its life facing the same environment its parent ended its life with is 90% in scenarios V /V i and, obviously, 100% in scenarios C/C i .

In order to evaluate the contribution of this effect, we measured the proportion of metabolic error that is due to the delay between an individual initialization and the moment when its regulation network reaches its steady state, for all the possible environmental conditions. At generation 300,000 we found a relative advantage of 7.5% (resp. 0.5%) for scenario V i (resp C i ) over scenario V (resp C). Note that our estimation process overestimates the contribution of this effect since it does not take into account the possibility of an environmental switch immediately before or after the individual initialization ( i.e., the possibility that the environmental conditions change before the network reaches its steady state). As the mean relative metabolic error gain due to protein inheritance was 16,7% for scenarios V i /V and 14.4% for scenarios C i /C at generation 300,000, we can conclude that the final advantage observed for scenarios C i and V i is a combined effect of the direct transmission of an efficient acquired phenotype and of another yet to be discovered "facilitating" effect that accelerates fitness gain.

Discussion

We have presented two main results of our experiments. First, protein inheritance increases the long term fitness gain Figure 5: Evolution of the metabolic error of the best individual in scenarios C (red), C i (green), V (blue) and V i (cyan). For scenarios V and V i the environmental condition changes randomly. This create random variation of the metabolic error between generations even for a same individual. To avoid this effect each point of the curve is the mean value of the 1,000 previous generations.

during evolution for scenarios C/C i and V /V i . Second, it has a negative effect during the first phase of the simulations: it generates instability in scenario V i and clogging before fitness improvement for scenario C i 3 . In this section, we propose hypotheses to explain both observations. Protein inheritance leads to major evolution impediment in the first phase of the simulations (i.e., during the phase of gene acquisition and regulation network construction). This can be explained by a dynamic conflict between the two forms of inheritance that interact in the model. Indeed, the expression of a mutation does not follow the same timing for genetic inheritance and for protein inheritance. Indeed, if a non-silent mutation occurs at generation n, it leads to the emergence of a new phenotype at generation n+1. However this new genotype will be expressed in the epigenetic context transmitted from generation n (i.e., in an epigenetic context that does not include the mutation). Things are different at generation n + 2 where both the genetic inheritance and the epigenetic inheritance transmit the mutation. Depending on the genetic background and on the kind of mutation, this effect can be almost neutral but it can also have important consequences if the genetic and epigenetic contributions of the mutation are of opposed sign. A mutation with a positive genetic effect and a negative epigenetic effect could be beneficial at generation n + 1 (and thus be selected for) while being deleterious at generation n + 2. Similarly, a mutation 3 The scenarios C and Ci can be compared by measuring the standard deviation of the derivative of the fitness. We find that the standard deviation is twice higher in scenario Ci than in scenario C (3.7710 -7 vs. 1.6310 -7 ). The relative advantage is computed as the difference of metabolic error divided by the mean metabolic error between the scenarios with and without protein inheritance.

with a negative genetic effect and a positive epigenetic effect could be counter-selected at generation n + 1 while it would have been favorable later.

This mechanism is likely to have a different impact on scenario V i and C i . Indeed, for scenario C i , the target phenotype is constant and the genetic regulation network is not mandatory to survive (although it may be useful to finely tune the protein concentrations). Consequently, the interference between the two modes of selection adds noise to the evaluation function and may impede the fixation of favorable mutations but it is not severely detrimental. On the opposite, for scenario V i , the regulation network is mandatory to survive in the three conditions that alternate in the environment. Moreover, evolution must create some pathways in the epigenetic landscape for the individuals to be able to switch from one target to another. There is thus a permanent competition between two evolutionary strategies: evolving a complex network that is able to efficiently switch between the environmental conditions, or keeping the population polymorphic (i.e., to maintain subpopulations that only fit one of the environmental conditions). Given the switching probability, the regulation strategy is much more efficient but it is also much more affected by the interference between genetic inheritance and epigenetic inheritance since an efficient regulation network may be counterselected "simply" because it is not initialized in the correct basin of attraction. Ultimately, this delays the moment when the regulation strategy invades the population, resulting in large fluctuations of the metabolic error.

Interestingly, this effect is also likely to depend on the kind of mutations. Indeed, if a mutation only affects an existing regulation link or an existing CDS, the consequences on the epigenetic inheritance are likely to be mild (since there is only quantitative variations). On the opposite, if the mutation corresponds to the creation (respectively deletion) of a gene, this can have dramatic consequences since the mutation will add (respectively remove) a protein at generation n + 1. In such conditions, the interference between genetic and epigenetic inheritance is maximal. Indeed, a simple comparison between Figures 5 and7 clearly shows that the fluctuations of metabolic error occur simultaneously with large fluctuations of the number of genes. This could explain why epigenetic inheritance is negative in the first evolutionary phase (when many genes are acquired in a "few" generations) but positive in the second phase.

The positive effect of epigenetic inheritance on the long term is much more straightforward. First, as we have seen above, the advantage of epigenetic inheritance must be decomposed between a direct advantage (the transmission of the epigenetic memory reduces the lag phase when the environmental conditions of the parent and of the offspring are correlated -which is often the case in our simulation) and an indirect advantage that accelerates evolution. This indirect advantage is easily explained in terms of pathways in the epigenetic landscape. Indeed, in scenario V i , the epigenetic landscape must contain 3 pathways to enable switching between the different environmental conditions: 1 ↔ 2, 1 ↔ 3 and 2 ↔ 3 (each of them triggered by a signaling protein). However, in scenario V , the epigenetic landscape must contain 6 pathways: 1 ↔ 2, 1 ↔ 3, 2 ↔ 3 plus I → 1, I → 2 and I → 3 (I being the initial state of the regulation network). Consequently, the genetic network is much more constrained for the individuals in scenario V than for those in scenario V i . The situation is similar for individuals in scenario C that must evolve an epigenetic pathway from their initial state to their steady state while in scenario C i , individuals are always initialized at the steady state.

Conclusion and future work

In this paper, we experimentally addressed the question of the impact of non-genetic inheritance on evolution (i.e., whether it could accelerate or decrease the rate of evolution). To evaluate this question, we used an in-silico experimental evolution platform, RAevol, to test 4 scenarios: 2 with a static environment (C and C i ) and 2 with a dynamic one (V and V i ). For each, we launch 2 types of simulations: 2 with protein inheritance (C i and V i ) and 2 without (C and V ). Our simulations show that protein inheritance indeed increases the rate of evolution on the long term but that it can have a strong negative effect at the beginning of the evolutionary process by generating instability in V i scenario and clogging before fitness jumps for scenario C i . Finally, we discussed these results and proposed that the evolutionary consequences of protein inheritance are a complex composition of three mechanisms: (i.) interference between genetic and protein inheritance due to their different transmission delays. This creates noise in the selection process and may delay the emergence of an efficient regulation network; (ii.) epigenetic memory that reduces the lag time when parents and offspring environments are correlated and (iii.) simplification of the epigenetic landscape.

The former effect was shown to be strongly deleterious in our simulations but only at the beginning of the evolution. It is then rapidly compensated by the two latter, resulting in a long-term benefit of protein inheritance on the evolution of our artificial organisms.

To the best of our knowledge, this work is the first attempt to explore experimentally the question of the impact of epigenetic inheritance on evolutionary dynamic. We now need to validate statistically our results by running more experimentation and to test other environmental conditions to confirm our mechanistic hypothesis (e.g., by letting individuals evolve in an environment where variation is correlated with the reproduction).

Figure 1 :

 1 Figure 1: Example of a variable environment. The three environmental conditions are displayed respectively in blue, orange and red. They alternate randomly with a switching probability of 10% at each time step. Individuals lifeduration is constant, fixed to 20 time steps. Each condition is also characterized by a signaling protein that can trigger a plastic response.

Figure 2 :

 2 Figure 2: Example of an evolved Raevol individual after 300,000 generations in V i conditions (variable environment and epigenetic inheritance). A: genome and mRNAs (colors code for the basal transcription rate); B: genome and CDSs (colors indicate the function of the gene product); C: Regulation network (arrows indicate links between genes and mRNAs; colors indicate the weight of the link. Note the three external signals displayed at the bottom-left of the network); D: protein concentrations during the life of the individual (colors indicate the function of the protein). E: Dynamic phenotype of the individual (same color code as panels B and D; thin red lines indicate the target at each time step). This individual is born in condition 3. At time 7 the environment switches to condition 4 and at time 11 it switches to condition 1 (see Figure 1 for a detailed explanation). At each environmental change the regulation network modifies the transcription levels and thence protein concentrations, resulting in a phenotypic adaptation. Protein inheritance is clearly visible on panel D: 38 proteins are inherited (initialized at concentrations inherited from the ancestor but rapidly dropping to zero) and 38 are produced during the individual's life (initialized at concentration zero but rapidly reaching their steady-state).

  .a) although the connectivity is lower for scenarios C/C i (Figure 3.c). Moreover, the difference in molecular complexity observed here are orders of magnitude lower than what was previously observed in the same model when varying

Figure 3 :

 3 Figure 3: Comparison of the gene number, genome size, average degree of the regulation network and metabolic error of the best individual for the 4 scenarios at generation 300,000 (mean values of the 1000 last generations). Error bars show the standard deviation between the 4 simulations of a scenario. Red: scenario C, green: C i , blue: V , cyan: V i .

Figure 4 :

 4 Figure 4: Genetic regulation network of the best individual in scenario V i . Orange boxes represent genes; pink triangles represent the 3 signal proteins. Red (resp. green) arrows represent inhibition (resp. activation) links. Arrows weight represents the intensity of the link. For the sake of clarity, only links whose weight are at least 33% of that of the strongest link are represented.

Figure 6 :

 6 Figure6: Evolution of the relative advantage of the protein inheritance in scenarios V /V i (blue) and C/C i (red). The relative advantage is computed as the difference of metabolic error divided by the mean metabolic error between the scenarios with and without protein inheritance.

Figure 7 :

 7 Figure7: Evolution of the number of genes of the best individual in scenario V (blue) and V i (cyan). As for figure5, the curves have been smoothed.

More precisely, the affinity is computed thanks to a regulatory matrix that associates 4AA motifs

with 20 nucleotides-long sequences. This matrix is randomly drawn at the beginning of a simulation. Here the same matrix is used for all simulations.

Acknowledgements

We would like to warmly thank David P. Parsons for careful reading of the manuscript. This research has been supported by EU-FET grant EvoEvo (ICT-610427).

Availability

Aevol is available under GPL licencing at the project website: http://www.aevol.fr. RAevol is currently in betaversion and is available upon request from the authors.


Liang Zhou

Baoyu Zheng

Benoit Geller

Anne Wei

Shan Xu

Yajun Li

Cross Layer Rate Control, Medium Access Control and Routing Design in Cooperative VANET

Keywords: vehicular ad-hoc network, cooperative, medium access control, rate control, routing

In this paper, we address the rate control, the Medium Access Control (MAC) and the routing problem for cooperative Vehicular Ad-Hoc Network (VANET) in the framework of cross-layer design. At first, we introduce the cooperative communication conception to VANET, and propose an opportunistic cooperation strategy to improve the system performance. And then, we develop a cross-layer solution which consists of the link capacity detection with adjusting persistence probability at the MAC Layer, the flow rate control with the maximal utility at the Transport Layer and the routing design at the Network Layer. This proposal is designed in distributed manner in order to support a simple and efficient implementation for VANET. Furthermore, some practical issues, such as fairness and network cost, are presented for implementing the proposed solution and improving the system performance. Simulation results show that the proposed opportunistic cooperation strategy combined with joint control algorithm achieves the desired performance over VANET.

Introduction

Vehicular Ad-Hoc Network (VANET) is an emerging new type of wireless networks in which vehicles constitute the mobile nodes in the network. This kind of networks supports vehicle-to-vehicle and vehicle-to-gateway communications by providing a self-organized and multi-hop network. The main technical challenge for communication in VANET is the strong mobility of the nodes, high dynamic change of the topology, high variability in node density, and very short duration of the communication.

Let's first consider classic VANET with short-range communication. There are wireless gateways at regular intervals providing access to the rest of the Internet using infrastructure support. Given an average speed of 50 miles per hour and a gateway radio range of 500 meters, every vehicle with the transmission window connected to a fixed Internet access point has one minute at the most. Considering contention from other vehicles, there may not be enough bandwidth to allow each vehicle to access the Internet in the short time. From the above example, we can find that conventional client-server approach in the face of intermittent connectivity is not appropriate for VANET. Therefore, limited access to the Internet contrasts with the even increasing dependence on Internet service, which motivates a compelling application of cooperative network in the VANET. In this cooperative network, every node (vehicle) acts as a partner for other nodes in a multi-hop wireless scenario. Thus, cooperation at the network level can be resonated at the application level [START_REF] Nosratinia | Cooperative communication in Wireless Networks[END_REF].

In fact, the idea of cooperative networking is first proposed to handle "flash crowds" on the Internet, where end-hosts cooperate in order to improve the overall network performance. The gateway in our architecture would experience flash crowd arrival patterns. As we shall see, the strong mobility of the nodes in VANET coupled with the intermittent connectivity to the Internet provides an incentive for individual nodes to cooperate while accessing the Internet to achieve some level of seamless connectivity.

In recent years, some cooperative strategies for content delivery and sharing in VANET have been proposed. Among these, [START_REF] Nandan | Co-operative downloading in vehicular ad-hoc wireless networks[END_REF] proposes a "communication efficient" swarming protocol which uses a gossip mechanism that leverages the inherent broadcast nature of the wireless medium, and a piece-selection strategy that takes proximity into account in decisions to exchange pieces. However, there is no specific solution describing how to solve the data flow movement problem over this multiple hop network. In fact, since cooperative VANET is a classic multi-source-multi-path system, one of most challenge issues is the flow rate control: the Internet is based on an end-to-end paradigm, where the transport protocol (e.g. TCP) instances at the endpoints to detect overload conditions at intermediate nodes. When congestion occurs, the source reduces flow rate [START_REF] Yuan | A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks[END_REF]. However, in cooperative VANET the topology changes within seconds and the congested nodes might not be adjusted at all when the sources react to the congestion.

In this paper, we jointly formulate the rate control, medium access control and routing problem for cooperative VANET in the framework of the utility function optimization. The fundamental purpose is to decompose the utility function into a flow control problem which determines the total source rate, and a division problem which describes how to split the total rate among a set of least congested paths according to the link persistence probability. The main contributions of this research are showed as follows: Firstly, we introduce the cooperative communication conception to VANET, and propose an opportunistic cooperation strategy to improve the system performance. Secondly, we develop a cross-layer solution which consists of the link capacity detection with adjusting persistence probability at the MAC Layer, the flow rate control with the maximal utility function value at the Transport Layer and the routing at the Network Layer. Generally speaking, the realization of joint rate control, MAC control and routing for this specific cooperative VANET system is the highlight of this paper. Finally, some practical issues for implementing the proposed scheme and improving the VANET performance are presented.

The remainder of this paper is organized as follows. Section 2 introduces the opportunistic cooperation strategy for VANET. Based on the problem analysis, a joint optimal rate control, medium access control and routing algorithm is proposed in Section 3. In Section 4, some practical implementation issues for VANET are presented. Simulation result and discussion are given in Section 5, followed by related works in Section 6 and concluding remarks in Section 7.

Opportunistic Cooperation Strategy for VANET

The VANET system consists of a set of nodes communicating through bidirectional wireless links between each other with the 5.9 GHz Dedicated Short-Range Communication (DSRC) [4]. The DSRC link is compatible with IEEE 802.11a R/A (Roadside Applications) by the Standard Committee E17.51.

The basic opportunistic cooperation strategy in this research is described as follows: when a vehicle arrives in the range of the gateway ( g R ), it requests the gateway for the particular data. If the gateway has the data in its cache, it starts downloading from the Gateway while in g R (Figure 1(a)). When the vehicle gets out of the range of g R , it starts to find his partner by gossip its neighbors about content availability. If the wanted data exists in its neighbor and the neighbor can provide a satisfactory service, the neighbor transmits the data in the range of the vehicle

( v R ) (Figure 1(b)). If his
neighbor has the wanted data, but it can not provide satisfactory service, the neighbor seeks to relay for help (Figure 1(c)). Otherwise, the neighbor gossip to its neighbors and become the potential relay for this vehicle (figure 1(d)). In the context of Figure 1(b) and 1(c), it is important for a vehicle to decide whether employing a relay or not.

To resolve this problem, we focus on designing an Opportunistic Cooperation MAC (OC-MAC) protocol which is specially adapted to VANET.

Relay Employment

Since the throughput is one of the most important indexes for VANET, here, we choose it as the criterion of relay employment. That is, relay nodes will be used only when they can improve the throughput of the system. The throughput of the system T is defined as:

t P P T size f  (1)
t represents the transmission time of a frame (including the control frame and the data frame), size P is the size of each packet and f P represents the possibility of successful transmission of packet in one transmission.

NAV and TIMEOUT Setting

In the IEEE 802.11 standard, the original RTS and CTS frame have a duration field to indicate how long this transmission will use the channel and to keep other nodes in the BSS (Basic Service Set) silent during the transmission. The NAV at each station should be set by the value of duration field of the received frame. The node will also set a timeout clock to wait for the reply. For example, after the sender sends a RTS frame, it will set a timeout clock to wait for a CTS frame. If the CTS frame does not arrive in the regular time, the sender will retransmit another RTS frame.

In our OC-MAC protocol, the duration field in RTS frame

RTS

Duration includes the time required to transmit the data frame through direct transmission, three SIFS intervals, one CTS frame and one ACK frame (see equation ( 6)). The timeout of RTS frame RTS Timeout includes the time of two SIFS intervals, one RC frame and one CTS frame (see equation ( 7)).

ACK DATA CTS SIFS RTS T T T T Duration      3 (6) CTS RC SIFS RTS T T T Timeout     2 (7)
This duration field guarantees that a packet can be directly sent even if the relay node can not be used. The timeout clock guarantees that the sender will wait enough time for the RC and CTS frames. The duration field in RC frame RC Duration will be set according to the following equation:

ACK DATA CTS SIFS RC T T T T Duration       2 4 (8)
ACK DATA SIFS CTS T T T Duration      2 3 ( 9
) DATA SIFS CTS T T Timeout     2 3 ( 10
)
The NAV mechanism for OC-MAC is shown in Figure 3. The timeout set guarantees the destination node can receive the data frame transmitted by the relay node. For those nodes that can hear both RTS and CTS frames, they have to set their NAV according to the duration field. Once the CTS or ACK packet is captured, they might reset the NAV according to this new message. Since the relay node may be failed or direct transmission might be successful, the duration fields in the new packets may reserve less time.

If the data packet is successfully transmitted, every station proceeds to start a new cycle, shown in Figure 4. If the deliver of data packet is failed, the sender will start an exponential back-off to retransmit its data.

Comparison with Other Ad Hoc Routing Algorithms

Here we analyze our proposed OC-MAC protocol by comparing it with some ad hoc routings, such as the AODV (Ad hoc On-Demand Distance Vector) and OLSR (Optimized Link State Routing) protocols. AODV is a reactive routing protocol, in which it enables to build routes between nodes only as desired by source nodes. It maintains these routes as long as they are needed by the sources; In terms of OLSR, as it is a proactive routing protocol, each node exchanges the topology information regularly and the routes are always immediately available when needed. However, the topological changes may cause the flooding of the topological information in the network even if the "relay" technique is used in OLSR.

In fact, our proposed OC-MAC protocol is designed to cater to the characteristics of VANET. Firstly, AODV is not totally suitable any more as the topology of the VANET could be changed frequently. In OC-MAC protocol, we employ hop-by-hop strategy in which each node just knows its next hop. Although it may be could not guarantee the whole routing is optimal, it enables to provide an existed routing from source to destination under the condition of fast change environment, such as VANET;

Secondly, comparing to OLSR the ultimate destination node decides the routing, OC-MAC protocol chooses the routing locally in which the intermediate destination node decides whether a relay is employed or not. Therefore, the amount of topological information can be reduced, which is important for VANET.

Joint Optimal Control Algorithm

In the previous section, we introduce the opportunistic cooperation strategy for the VANET. In fact, very node in this cooperative network is possible to become the source, relay or destination, and this is a classic complex multi-source-multi-path system, therefore, it is much more difficult to control the network compared to the traditional non-cooperative system. In this section, we present a Joint Optimal Control (JOC) algorithm to jointly optimize rate control, medium access control and routing for the aforementioned cooperative VANET system based on the cross-layer design. [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF] be the vector of all path rates of all sources. Our objective is to choose rates

System Analysis

x so as to maximize the total utility

 S s s s x U ) ( :    S s s s x x U s ) ( max 0 (14) s s s i s n i i s s M x m x c Rx x x to subject s        , 0 , , 1 ,
However, in the cooperative system, each node or each link has a contention resolution protocol based on the transmission persistence probability. Let

q , ) (s L l out  . Consequently, link ) (s L l out 
transmits data with a probability

l s l q p p  
, which is called persistence probability of link l . Therefore, the data rate on path i , i s x , , is obtained as minimum rate of link in the path: With the above analysis, we can specify the cooperative wireless networks utility maximization with "contention" link:

       ) ( ) ( ] , 1 [ , ) 1 ( min ) ( , l N k k L m m l l N
   S s s s x x U s ) ( max 0 (16) 1 0 , , 0 , ) ( , 1

JOC Algorithm

In the case of multi-path flow control, many literatures have been proposed by introducing the variable of path price to maximum the total utility function of the system [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF][START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF][START_REF] Chen | Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks[END_REF]. In [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF], the author solves the optimal congestion control problem by taking the path price into consideration, and the optimal source rate * ,i s R of source s . The above equation suggests a way to adapt that the total source to congestion, but it does not specify the total rate should be split among the available paths. A naï ve approach is to simply split it evenly along paths that have the least current price. This algorithm, however, does not converge, e.g. when multiple paths have different path prices. Here, we can view the persistence probability as a special path price, and the distributed optimal s x at each source can be adjusted according to the persistence probability of each link. Similarly, the persistence probability is adjusted according to current s x . Intuitively, the expected result would allocate the "right" amount persistence probability to the "right" links to control the flow rate, which may then induce an increase in end-to-end throughput.

JOC Algorithm:

We assume that time is slotted, and the links are fixed within a time slot but independently change between different slots. During each time slot t , the following three updates are carried out simultaneously until convergence.

1) MAC: Each link l receives flow rates ) ( , t x i s for all paths i s R , that contain link l , and computes a new persistence probability

1 0 ) ( ) ( , ] 1 ) ( ) ( [ ) 1 (            l out l I from t L m m t L k k l s i s l l l p t p x R c t p t p    ( 17
)
l t is the transmitter node whose path contains link l , 0   ,and

             otherwise p p c x if l N k k L m m l l i i s l I to out , 1 ) 1 ( , 0 ) ( ) ( ,  . Informing new
To these paths which do not have the maximum persistence probability, path rate

) 1 ( ,  t x i s on path i s R , is:      ))] ( ) ( ( ) ( [ ) 1 ( , , , * t p t p t x t x r i s r s i s i s  , 0   (19)
To the any path j s R , that has the maximum persistence probability, we set its rate as:

         ] ) 1 ( ) 1 ( [ ) 1 ( ] , 1 [ , , j i n i i s s j s s t x t x t x ( 20
)
and then informs all the new flow rate ) 1 (

,  t x i s to links l contained in path i s R ,
3) Routing: Over the chosen link, sending an amount of bits for destination according to the rate determined by the rate control update. Note that, the persistence probability of the link depends on two aspects: one is the current flow rate relative to link capacity, while the other one is the current link affected by other vehicles. In the case of path rate, the rates on all paths that have less than the maximum persistence probability are reduced by an amount proportional to the absent probability, and the rate on the maximum probability path is increased, so that the new rates on all paths sum up to the new total source rate determined in the flow control decision.

Performance Evaluation

We first associate Lagrange multiplier for each of the constraints, and use the KKT optimality conditions for optimization [START_REF] Rockafellar | Monotone Operators and the Proximal Point Algorithm[END_REF][START_REF] Chiang | To layer or not to layer: balancing transport and physical layers in wirless multihop networks[END_REF], solving this problem is equivalent to satisfying the complementary slackness condition and finding the stationary points of the Lagrange.

) ( ) ( ) ) ( ( ) ( ) ) ( ( ) ( ) , , , ( 1 , 1
                          (21) where ] ,..., , [ 2 1 s      , T l ] ,..., , [ 2 1     
. By linearity of the differentiation operator, this can be decomposed into two separate maximization problems

     S s s s s s x x x x U x L   ) ( ) , ( max 0  ) ( )) 1 ( min ( ) ( ) ( ) , , ( max 1 ) ( ) ( ] , 1 [ 1 , 0
, l l l T l n i l N k k L m m l l N l s T l n i i s s P P c x p p p c c Rx P x P L s I to out i s s                        
The first maximization is already implicitly solved by the rate control mechanism for different s U in [11], while the second maximization still need to be solved which aims at allocating exactly the right persistence probability of each link to achieve the optimal rate. Here, we focus on the convergence of the persistence probability problem.

Because

           s I to out i s n i l N k l l l k L m m l l N l P x c p p p c P L 1 ) ( ) ( ] , 1 [ ] ) ( log )) 1 ( log( min ) ( , , where
l l p p log ~ .
In the appendix, we will show that the partial Lagrange is a strictly concave function of a logarithmically transformed probability vector. So we can decompose that

) ( log ] ) 1 ( ) 1 ( log[ ) ( log )) 1 ( log( min ) ( , ), ( ) ( ) ( 1 ) ( ) ( 1 ) ( ) ( ] , 1 [ ,                                s i s l l t k n N k k L m m t L n n n n i l N k k L m m l l n i l N k l l l k L m m l l N l P x R
Assuming              otherwise p p c x if l N k k L m m l l i i s l I to out , 1 ) 1 ( , 0 ) ( ) ( ,  , Taking the derivative of ) (P L P with respect to l p ~, we have                       ) ( ) ( , ) ( ) ( ) ( , 1 ) ( 1 ) 1 ( ) ( ) ( l out l I from l out I to out t L m m t L k k l s i s l t L m m k l N k k L m m l s i s l P l p p x R c p p p x R c P L   (23)
Coming back to the P solution space instead of P ~, it is easy to verify that the derivate of

) (P L P with respect to l p is           ) ( ) ( , 1 ) ( l out l I from t L m m t L k k l s i s l P l p p x R c P L  (24)
Therefore, the logarithmic change of variables simply scales each entry of the gradient by

) ( ) /( ) 1 ( ) ( : P L p P L p P l l P l l   
. We now use the gradient method [START_REF] Low | A duality model of TCP and queue management algorithms[END_REF],

with a constant step size , to maximize

) (P L P 1 0 ) ( ) ( , ] 1 ) ( ) ( [ ) ( ) ( ) 1 (               l out l I from t L m m t L k k l s i s l l P l l l p t p x R c

Extension: Some Practical Issues for Application

Fairness

Packets originating at vehicles outside the communication range of gateway must undergo several channel contentions to reach the gateway. Hence, they have disadvantages over the packets that travel shorter distance to the gateway. In addition, as stated previously, in the cooperation system, each vehicle may transmit both its own bits as well as some information for its partner, how to keep relative fairness between its own bits and bits is also a practical problem need to be solved.

In generic wireless network, the fairness strategy adopts the per-flow fairness, in which every flow has the equal "opportunity" to get the destination; however, this is impractical in VANET system. Here we can employ a content-based fairness strategy as described in [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF], and it is scalable and does not require maintenance of any state information beyond a time slot which is important in a network with a fast changing topology. As to the content-based fairness strategy, that is when each node receives the packets, it judges the packet content whether it has hold or not. If has, it will throw out the packet directly and inform his partner do not transmit after that moment. If not, it will receive the packet and adjust the flow rate and persistence probability as stated before.

In addition, utility functions can also be interpreted as the "knobs" to control the tradeoff between the fairness and efficiency. Different shapes of utility functions lead to different types of fairness defined in the economics literature. For example, a family of utility functions, parameterized by 0

 a , is proposed in [14]         otherwise x if x x U , lg 1 , ) 1 ( ) ( 1 1     (25) If we set 0  a
, utility maximization reduces to system throughput maximization. , then max-min fairness. To accommodate multi-class services and attain the desired tradeoff between efficiency and fairness, it is important that the utility maximization framework can handle general types of convex/concave utility functions.

Network Cost

In our system model, we have only considered the user utility. We can introduce a variable l  for each link l to represent the cost incurred by using the link to transmit flow to destination. Our objective is to maximize net-gain to strike a balance between vehicle utilities and network cost:

     L l l l S s s s c x U  ) ( (26)
Link cost l  can be a function of link state such as loss rate, or any other link metric.

Following the analysis described in Section 3, we can obtain similar cross layer MAC, rate control and routing algorithm as followings. Change the equation ( 19) into

      ))] ( ) ( ) ( ( ) ( [ ) 1 ( , , , , * t t p t p t x t x i s r i s r s i s i s   , 0   . ( 27
)
All the other steps in JOC algorithm remain the same.

The introduction of l  facilitates the implementation of many functionalities. For example, if it is an increasing function of link loss rate, we can do link-state-aware scheduling and avoid less reliable links. It can also help to improve performance in delay. In our original design, the flows find their way to destinations by moving in directions of increasing persistence probability. Thus, some data may take a long path to its destination, which could lead to significant delay for large network. By taking  proportional to the link length, we can align the nodes to route data in the direction of their destinations, and thus improve the performance in delay.

Simulation Results and Discussion

We conduct simulation experiments to study the performance of the proposed OC-MAC protocol and JOC scheme. First of all, we describe the simulation settings.

Secondly, we present the main simulation results where we show the objective performance results under different scenarios comparing to the competing methods.

Finally, we conclude this section based on the selected simulation results.

Simulation Settings

We implement the proposed scheme in Nab network simulator [15], which is a fast, flexible and scalable simulator for ad-hoc networks. We incorporate our mobility model, and traffic model into the simulator. The vehicle (node) arrival process at the access point follows a Poisson distribution with the average inter arrival time varying from 0.5 to 4 seconds. We consider only one direction of vehicle motion in the highway. The neighbor group is maintained among vehicles driving in the same direction. For simulation convenience, there are 5 original source vehicles distributed uniformly in the system, and all of the other vehicles want to download the data from the sources. We use slow fading Rayleigh channel with unit mean to simulate the wireless radio channel. The parameters used in the simulation are listed in Table 1. We modify the frame structure based on IEEE 802.11, and the new RTS frame is defined as Figure 5, in which the HA field represents the address of the relay node. When a node receives a RTS frame, it will compare this address to its own. If they are the same, it will send out a RC frame, which is defined as Figure 6. It should be noted that all the simulation results in this section have been obtained

using 300 runs in order to obtain statistically meaningful average values.

Selected Simulation Results and Discussions

At first, to demonstrate the effectiveness of our proposed OC-MAC strategy, we plot the throughput variation as the number of the nodes increases. The proposed OC-MAC is benchmarked against other three methods: 1) conventional client-server scheme (it uses IEEE 802.11 at the MAC layer, and the gateway is the only source). 2)

no-relay cooperation approach (it doest not use relay all the time). 3) always-relay cooperation approach (it uses relay all the time, if any). For notational convenience, we note the above three competing schemes as conventional, no-relay and always-relay, respectively. Figure 7 shows the performance comparison between our proposed OC-MAC and the other three competing schemes. The proposed OC-MAC method can be seen to achieve a higher performance in terms of throughput compared to the conventional client-server method. Obviously, this is due to the introduction of the cooperation. For the cooperative system, there are many possible sources to provide the information other nodes may be interested in. It should also be noted from this figure that the performance achieved by the proposed OC-MAC method is also super to the no-relay and always-relay cooperation method. Though proposed OC-MAC method achieves almost the same performance compared to the always-relay method when node number is small and the no-relay method when node number is large, however, on the whole, the proposed OC-MAC method always outperforms the above no-relay and always-relay methods. For example, when the node number is 10, the gaps between the proposed OC-MAC method with the no-relay method and always-relay method are 1.2 and 0 PPS respectively, while the node number is 30, the gaps are 0.1 and 0.5 PPS, respectively. We also observe that throughput decreases when the number of nodes in the network becomes larger, which is because the more nodes in the network, the higher possibility of the packets collision during a transmission. In addition, with more nodes in the network, the routing protocol needs more routing information exchange to maintain the routing table, so the traffic load increases and leads to the congestion of network. This is the main reason why we provide the joint control algorithm for this cooperative system.

Figure 8 shows the influence of the velocity of nodes on the throughput performance. With the increase of speed, the link quality deteriorates because the reception power decreases. Our proposed OC-MAC can achieve a satisfactory performance because relay nodes keep a copy of the data frame which increases the possibility of correct reception if it is necessary to employ the relay. Generally speaking, a relay node is used when the velocity is large and channel condition is not good. This rule can be easily concluded from this figure. In addition, we note that there is no distinct difference influence between the OC-MAC, the no-relay and always-relay when the velocity is more than 70mph, which is because both the relay and direction channels are not good for transmission in this case.

And then, we present some simulation results for JOC algorithm. The network with end-to-end paths and logic links is shown in Figure 9. Each of the three sources has its utility function parameterized by a as in (25). We assume that if the distance between the transmitter node and the receiver node is less than 2d (see Figure 9), the receiver node gets interfered from the transmitter node. For simplicity, we assume that all of the links capacities are identically and uniformly distributed over one unit.

Figure 10 shows the convergence of link persistence probabilities regulated by JOC algorithm for the case of 3  a with step-size 1 . 0     (Note: the initial persistence probability of each link is random distributed from 0 to 1; A, E and G are source nodes, while the C, D and F are destination nodes). Figure 11 shows the optimized source rates with each data point being the result of solving ( 16) for a given fairness parameter a . A number of interesting observations can be made from this graph. For example, since source 1 traverses more heavily interfered links, at the optimal rate allocation that maximizes the network utility, it is allocated the lowest data rate. However, as the value of a increases, the gap among the source decreases, improving fairness among sources.

Finally, to demonstrate the effectiveness of our proposed OC-MAC protocol combined with JOC algorithm for the cooperative VANET system, we plot the throughput curves at the node velocity equal to 40mph and 80mph, respectively. The proposed OC-MAC+JOC scheme is benchmarked against the scheme with only OC-MAC, in which it does not employ any control algorithm. The performance comparison is illustrated in Figure 12. The proposed OC-MAC+JOC method can be seen to achieve a higher performance in terms of throughput. When the velocity of the node is 40 mph and the number of the node ranges from 10 to 35, the average throughput using the proposed scheme is about 8.73 PPS while it is 8.12 PPS for the case of OC-MAC method, thus, around 0.6 PPS performance gain can be achieved on average using the proposed OC-MAC+JOC scheme. Similarly, when the velocity of the node is 80 mph, around 0.5 PPS performance gain can be achieved on the average.

Observations

Based on the selected objective and subjective simulation results described above, we conclude the following three main observations:

 Opportunistic cooperation strategy (OC-MAC protocol) can improve the throughput of the VANET system compared to the conventional IEEE 802.11 standard client-service system. In addition, it also outperforms the no-relay and always-relay approaches in terms of adaptability (please see Figure 7 and Figure 8).

 Joint optimal control algorithm actually can adjust flow rates at Transport layer according to the link persistence probability adjusted at the MAC layer. The simulation results support the previous theory analysis that the proposed JOC algorithm converges to the globally optimal solutions (please see Figure 10 and Figure 11).

 From the objective comparisons, it is clear that the proposed OC-MAC combined with JOC scheme outperforms the only OC-MAC method and can provide a satisfactory service for practical VANET system (please see Figure 12).

Related Works

For the single-source-single-path utility maximization problem, i.e., each vehicle has only one available path, had been extensively studied in the past, mainly in the context of Internet rate control (for example, [START_REF] Low | Optimization flow control-I: basic algorithm and convergence[END_REF][START_REF] Yaiche | A Game Theoretic Framework for Bandwidth Allocation and Pricing in Broadband Networks[END_REF] and the reference therein). In addition, single-source-multi-path utility maximization problem also had received much attention in many literatures (for example, [START_REF] Kelly | Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability[END_REF], [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF] and the reference therein).

[18] categorizes the solutions into primal algorithms and dual algorithms. Globe convergence of the primal algorithms is studied in [START_REF] Kelly | Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability[END_REF] for the case of when feedback delays are negligible and the oscillation problem of dual algorithm are discussed in [START_REF] Lin | Utility Maximization for Communication Networks with Multi-path Routing[END_REF]. In [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF], the authors propose two flow control algorithms for network with multiple paths between source-destination pair, both are distributed algorithms over the network to maximize aggregate source utility. In contrast to the abundance of methods proposed to deal with single source utility problem, little attention has been received on multi-source-multi-path problem. [START_REF] Wang | Optimal Flow Control and Routing in Multi-Path Networks[END_REF] studies utility maximization problem for communication networks where each vehicle can have multiple alternative paths and develops a distributed solution to this problem that was amenable to online implementation.

The work in [START_REF] Kelly | Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability[END_REF], [START_REF] Kunniyur | End-to-end congestion control schemes: Utility functions, random losses and ECN marks[END_REF], [START_REF] Low | Optimization flow control-I: basic algorithm and convergence[END_REF], [START_REF] Low | A duality model of TCP and queue management algorithms[END_REF] provides a utility-based optimization framework for Internet congestion control. The same framework has been applied to study the congestion control over ad hoc wireless networks (see, e.g., [START_REF] Yi | Hop-by-hop congestion control over a wireless multi-hop network[END_REF], [START_REF] Chen | Joint congestion control and media access control design for ad hoc wireless networks[END_REF]). [START_REF] Chen | Joint congestion control and media access control design for ad hoc wireless networks[END_REF] studies joint congestion control and media access control for ad hoc wireless network, and formulates rate allocation as a utility maximization problem with the constraints that arise from contention for channel access. [START_REF] Kodialam | Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem[END_REF] uses a similar model to study this problem by jointly routing the flows and scheduling the transmissions to determine the achievable rates in multi-hop wireless networks. To sum up, all these works focus on the interaction between link and network layers, and try to characterize the achievable rate region at network layer.

Cross-layer design in communication networks, especially in wireless networks, has attracted great attention recently (see, e.g. [START_REF] Shakkottai | Cross layer design for wireless networks[END_REF] for an overview). Our work belongs to the category of cross-layer design via dual decomposition in optimization framework. Other work that can be put into this category includes TCP/IP interaction in [START_REF] Li | Can TCP and shortest-path routing maximize utility?[END_REF], joint routing and resource allocation in [START_REF] Xiao | Simultaneous routing and resource allocation via dual decomposition[END_REF] and joint TCP and power control in [START_REF] Chiang | To layer or not to layer: balancing transport and physical layers in wirless multihop networks[END_REF]. The work on joint rate control, MAC and routing design is the first step to provide a unified framework for systematically carrying out cross-layer design. We will extend the framework to include other layers in the future.

Concluding Remarks

In this paper, we have been focusing on optimizing the rate control, medium access control and routing problem jointly for cooperative VANET. Firstly, we introduce the cooperative communication conception to VANET, and propose an opportunistic cooperation strategy to improve the system throughput. Secondly, we develop a cross-layer control algorithm by joint working at medium access control layer to adjust link persistence probability, at the transport layer to adjust flow rate and at the network layer to determine the routing. Furthermore, some practical issues for implementing the proposed algorithm and improving the system performance are

  When setting the duration field in the CTS frame, we have to check out if the RC frame has been received. If not, we can set the value by subtracting the time for a SIFS interval and a CTS frame. If RC frame is present, the duration in the CTSCTSDurationand timeout CTS Timeout should be set as below:

  of nodes whose transmissions cause interference to the receiver of link l , excluding the transmitter node of link, and ) (s L I from as the set of links whose transmissions get interfered from the transmission of node s , excluding the outgoing links from node s . Therefore, if the transmitter of link l and a node in ) (l N I to transmit data simultaneously, the transmission of link l fails. If node s and the transmitter of a link l in ) (s L I from transmit data simultaneously, the transmission of link l also fails. Assuming each s transmits data with a probability s p , when it determines to transit data, it chooses one of its outgoing paths with a probability

  l

H

  presented. The simulation results show that the effectiveness of the proposed opportunistic cooperation strategy combined with joint control algorithm for the cooperative VANET. is indeed negative definite: for all vectors v

2.2 The OC-MAC Protocol

	In our scheme, relay selection is based on instantaneous channel conditions in slow r calculate the possibilities f P and P [5]. With the transmission time of control frame
	fading environment, without requiring the knowledge of the topology. Meanwhile, the
	and data frame,	T and	T can be finally computed and compared to decide whether
			r
	overhead involved is minimal since the technique is based on signal strength
	to use a relay node or not. If a relay node is used, a confirm signature will be specified
	measurement of RTS and CTS packets. The transmission of these packets allows for
	f P can be calculated by the the estimation of the instantaneous wireless channel information j i h , from node i to in the CTS frame, which informs the sender the use of relay. Otherwise, a CTS frame
	BER (Bit Error Rate) and frame length as introduced in [5]. Without considering the node j , therefore, each node can establish a one hop routing table and choose will also be sent out but without a confirmation. In this situation, the sender will
	transmission time of SIFS (Short Inter Frame Space) slots in the IEEE 802.11 appropriate nodes for data relaying. delete this relay node from the table after the reception of CTS frame.
	network, the transmission time If a relay node R correctly receives the data frame, it senses the channel to see t can be defined as:
	t if there is an ACK frame. If so, that means the destination node t t  	(2) D has received the
						c		d
	cts D , it will first send rts t t   ( S has the data to transmit to a destination node c t data frame successfully, and the relay node Once a node R does not have to send the data frame
	the data to again. If an ACK frame is not heard in a two SIFS time, the relay node D if the connection is not failed. As the topology changes so fast and the R will send
	relay nodes are often used in VANET. Therefore, the data frame to the destination node D . If the destination node S also checks its relay table to D successfully
	where choose a relay with best channel condition if the table is not empty. ack data d t t t   . In addition, receives this data frame, it will send out an ACK frame to indicate a successful
	In the case of the relay node transmission. Figure 2 depicts this procedure. R is used,	S senses the channel first to see if it is
	idle for a DIFS (Distributed Inter-Frame Space) time according to IEEE 802.11
			t	t  '		t		(3)
	standard. When	d S has completed the required back-off procedure, a RTS frame will c s
	' d be sent, including the MAC address of the relay node, and this frame also reserves the ' c r t t t   (4)
	according to IEEE 802.11 standard, channel for NAV (Network Allocation Vector) duration. The potential relay node will rc cts rts c t t t t    ' ( rc t is the time of RC (Relay
	Confirmation)), check its own state to see if it can relay the information for the sender, if so, a RC ack data d t t t    2 ' .So the throughput of relay strategy r T can be
	expressed as: frame will be sent to the destination node in a SIFS time slot after received the RTS
	size P frame. Otherwise, it will just stay idle. f r P T 		1 ( 	f P	)	r P	size P	(5)
			t					t
			s						r
	P is the possibility of successful transmission through relay node. Relay is used only After hearing the RC frame, the destination node D will use the channel
	r
	when information T T r  , and this decision is made by the intermediate destination node. D S h , (from source to destination) and D R h , (from relay to destination) to

c t denotes the transmission time of control frames, where rts t is the time of RTS (Request To Send); cts t is the time of CTS (Clear To Send)).

d t represents the transmission time of data frame and ACK (acknowledgment) frame, s t (see equation (3)) denotes the transmission time when direct transmission is successful, and r t (see equation (4)) defines the transmission time when direct transmission is failed and relay is used,

Table 1

 1

	: Parameter Settings
	MAC header	272 bits
	PHY header	192 bits
	RTS	208 bits
	CTS	304 bits
	ACK	304 bits
	RS	160 bits
	Packet Size	1024 bits
	Data rate for MAC and PHY header	1M bps
	Slot time	20 us
	SIFS	10us

Acknowledgments

This work is supported by the International Project PRA-SI (financed by France and China government) under Grant No.SI04-03, and the Key Project of Nature Science Foundation of Jiangsu (China) under Grant BK2007729. What's more, we also thank the anonymous reviewers for insightful comments and suggestions.

Appendix: Proof of Strictly Concave Function

Proof:

Taking derivatives again, for each of the nonlinear


A Mathieu

P.-H Cournède

P De Reffye

The Influence of Photosynthesis on the Number of Metamers per Growth Unit in GreenLab Model

GreenLab Model is a functional-structural plant growth model that combines both organogenesis (at each cycle, new organs are created with respect to genetic rules) and photosynthesis (organs are filled with the biomass produced by the leaves photosynthesis). Our new developments of the model concern the retroaction of photosynthesis on organogenesis. We present here the first step towards the total representation of this retroaction, where the influence of available biomass on the number of metamers in new growth units us modelled. The theory is introduced and applied to a Corner model tree. Different interesting behaviours are pointed out.

Introduction

Functional-Structural Models (FSM) aim at controlling all sides of plant growth by combining organogenesis and photosynthesis. In our proportional allocation model (see [START_REF] Warren-Wilson | Control of Crop processes[END_REF]), organs play their true roles as sources and sinks for biomass during the development process, and the interaction between architecture and functioning is taken into account. A good review on the FSM is found in [START_REF] Sievänen | Components of a functional-structural tree model[END_REF]. Until now, few models exist with their corresponding simulation codes (de Reffye & al [START_REF] De Reffye | An Ecophysiological Model for Tree Growth and Tree Architecture[END_REF], Perttunen & al [START_REF] Jallas | Virtual cottons, the firstborn of the next generation of simulation model[END_REF], Jallas & al [START_REF] Perttunen | LIGNUM: a tree model based on simple structural units[END_REF]). Recently, de Reffye & al., see [START_REF] De Reffye | Choices in Botany and Mathematics for building efficient Dynamic Plant Growth Models: GreenLab Case In: PMA'03[END_REF], proposed a FSM in the form of a dynamical system, GreenLab based on simple relevant choices from both biological and mathematical point of views. The mathematical formalism introduced allows to implement optimization and control techniques for agronomic applications. In the previous version of the model, organogenesis was independent of photosynthesis: the number of new organs in the plant was strictly determined by genetic rules and did not vary with the production of the plant. In this paper, we present the first step towards modelling total retroaction between photosynthesis and organogenesis: the influence of available biomass on the number of metamers in new growth units is studied. For example, a beech tree in the sun can construct eleven new metamers per growth unit each year while the same tree in the shade creates two. We start by giving a new model for the growth cycle. It allows us to introduce the influence of photosynthesis on organogenesis. Then, for a simple case, a Corner model plant, we give the mathematical equations of the plant growth and study the behaviour of the system, from theoretical and numerical point of views.

Description of the model

Plant simulation

Plants are supposed to grow in cycles and their growth is simulated with an automaton. Plants are decomposed in basic elements:

-a metamer is an internode (elementary portion of an axis) which bears lateral organs (leaves, internodes, buds, fruits); -a growth unit is a succession of metamers set in place during a same growth cycle. The number of growth cycles since the appearance of the organ is its chronological age. The growth unit is supposed to be preformed in the bud. Once the number of metamers is determined, plants cannot construct new ones during the cycle (no neoformation is possible).

For the sake of clarity, we suppose that the organs reach their final size as soon as they appear (immediate expansion), and they only function during one cycle. This is the case of most leafy temperate trees. Secondary growth is also neglected (no layers). However, the model can easily be extended to the general case.

Photosynthesis model

In the photosynthesis model, the seed and the leaves are sources. Leaves, internodes, fruits and rings are sinks. Here, we do not consider the root system. From the seed, the plant constructs its first organs (following the organogenesis model). Then, during a cycle, the leaves make photosynthesis by utilizing carbon dioxide, light energy, and water. They produce the materials used for plant development. We consider a functional bud as an organ with a sink. A quantity of biomass is thus allocated to each bud, proportionally to its sink value and to the pool amount of biomass. Then, the number of organs in each bud is computed, and the matter is finally used to build them. These organs will appear in the plant at the beginning of the next cycle and so on.

We can sum up this functioning in several steps: 1. Calculation of the available biomass fabricated by the leaves during the cycle. 2. Calculation of the buds demand. 3. Calculation of the number of primordia in a bud, according to the ratio between biomass and demand. 4. Partitioning of the fresh matter between the future organs. 5. Breaking of the bud at the beginning of the cycle n+1. Later in the development of the tree, some buds may die if there is not enough matter. Indeed, the tree will choose whether to construct less metamers or to suppress buds. This study will be presented in a next paper.

Model Functioning

Mathematical model

We intend to equate this model of plant growth, and examine the different steps. We study a young seedling (unbranched) with only a terminal bud that is a Corner model. A single bud gives birth to a new growth unit at each cycle. We note o n k N , the number of organs o of physiological age k created at the beginning of cycle n. o p stands for the sink of an organ, (a for leaf, e for internode and m for metamer) and D b,n is the bud demand at n. a n is the number of leaves for a metamer. n Q is the biomass produced by the leaves during cycle n. Finally, we introduce the resistances 1 r and 2 r for photosynthesis functions.

Biomass and Demand

Here, we suppose that only the one-cycle old leaves are active. Each leaf produces biomass that will fill the pool of reserves according to an empirical non linear function depending on its surface S, on hidden parameters to assess r1, r2, and on an environmental parameter E .The empirical shape chosen here for the leaf functioning is

2 1 r S r E q n n + = .
Eventually, the total biomass production is

∑ ∑ + = = a n a n n r S r E q Q 2 1 .
The demand is a scalar product between the number of organs and their sinks. Here, the matter can only be allocated to the bud, and the demand is

BV n b p D 1 , =
.We choose now 1 1 = BV p .

Creation of metamers

According to the amount of matter allocated to the bud, we compute the number 1 + n u of new metamers in the bud. The corresponding biomass is finally used to build these metamers that appear at beginning of cycle n+ 1.

The whole available biomass allocated to the terminal bud:

n n b n BV BV Q D Q p q = = , 1
.

a) Determination of the number of metamers

We can compute how many metamers the bud will give birth to, with rules like:

) (

1 BV n q f u = + .
The function f has to satisfy some constraints: -The number of metamers in a growth unit is supposed to be bounded, the limit being a genetic datum of the plant. However, some trees may not have such limits. -The sizes of metamers are to be taken into consideration. A tree will tend to build a supplementary metamer only when the other ones have a big enough size.

We tested functions like b q

a q f BV k BV + = α ) ( 1 ) (
. Parameters are to be estimated to fit real trees.

b) Matter distribution

Once the number of metamers is determined, the matter is divided between them. Each leaf

gets 1 + = n m BV a a u p q p q
, and we can deduce volumes and dimensions from allometry rules. We assume that the leaf thickness e is constant and the surface: e q S a n n , = .

Finally, the total biomass produced by the tree is:

Results

We studied the variation of the number of metamers We can rewrite: We remark the number of metamers increases, the limit being 6.

B Q Au E u Q n n n n + = + + + 1 1 1 with ) ) ( ( ) ( 1 a Q round Q f u n n n α = = + . t
Parameters have a great influence on the plant behaviour. The more pertinent values for our study are a>0 and 0 1 > > α

. In this example, we have chosen 2 / 1 = α , a=1/2, E=1000, A=750, B=150, Q 0 =1; C=1/a=2; p a =p e =0.5; p BV =1.

Conclusion

We have presented the bases of a theoretical model describing the influence of photosynthesis on the number of metamers per growth unit. The model can be easily generalized to more complex cases. However, it needs to be fitted to real plants, which raise a problem of choice and adjustment of its parameters. How should we define them? For example, the sinks of the buds are very important to determine the numbers of metamers. Should they be linked to the organs demand in the growth unit? Likewise, to represent a maximum of the real plants, the decision rules must be very flexible. But, the more flexible they are, the more parameters they have and the harder it is to find their values. With some parameters, we can describe a plant whose number of metamers is periodic, and some chaos may even appear! Therefore, complementary studies (implying confrontation of the model to real plants, like beech tree) are in process in order to refine the choice and definition of the model parameters.