Elmar Nurmemmedov

Martin Castelnovo

Elizabeth Medina

Carlos Enrique Catalano

Alex Evilevitch
email: alexe@andrew.cmu.edu

Challenging packaging limits and infectivity of phage λ

Keywords: bacteriophage lambda, pressure, DNA packaging, terminase

The terminase motors of bacteriophages have been shown to be among the strongest active machines in the biomolecular world, being able to package several tens of kilobase pairs of viral genome into a capsid within minutes. Yet these motors are hindered at the end of the packaging process by the progressive build-up of a force resisting packaging associated with already packaged DNA. In this experimental work, we raise the issue of what sets the upper limit on the length of the genome that can be packaged by the terminase motor of phage λ and still yield infectious virions, and the conditions under which this can be efficiently performed. Using a packaging strategy developed in our laboratory of building phage λ from scratch, together with plaque assay monitoring, we have been able to show that the terminase motor of phage λ is able to produce infectious particles with up to 110% of the wild-type (WT) λ-DNA length. However, the phage production rate, and thus the infectivity, decreased exponentially with increasing DNA length, and was a factor of 10 3 lower for the 110% λ-DNA phage. Interestingly, our in vitro strategy was still efficient in fully packaging phages with DNA lengths as high as 114% of the WT length, but these viruses were unable to infect bacterial cells efficiently. Further, we demonstrated that the phage production rate is modulated by the presence of multivalent ionic 2 species. The biological consequences of these finding are discussed.

INTRODUCTION

Viruses are among the simplest biological organisms. They typically consist of a viral genome within a protein container, called a capsid, whose function is to protect the genome and to provide a specific strategy for the early steps of infection. Despite their simplicity, viruses exhibit extreme diversity and are highly prone to mutations. This limits the efficiency of current anti-viral therapies, which are often focused on the specificity of viral replication. The past decade has seen the emergence of a new interdisciplinary approach, called "Physical Virology", providing tremendous opportunities for the elucidation of the general physical mechanisms involved in virus development and infection. For example, in double-stranded (ds) DNA viruses, the genome is often hundreds of times longer than the dimensions of the capsid into which it is packaged, and this results in high internal pressure due to the repulsive negative charges on the densely packaged DNA. Indeed, high mechanical pressure in dsDNA bacterial viruses (phages) has recently been demonstrated [START_REF] Evilevitch | Osmotic pressure inhibition of DNA ejection from phage[END_REF][START_REF] Smith | The bacteriophage phi 29 portal motor can package DNA against a large internal force[END_REF]. During infection, the phage binds to the receptor on the bacterial cell surface and the pressure injects the genome into the cell, at least in part, while the empty capsid remains outside the cell. This initiates a series of events, eventually leading to hundreds of viral genomes, pre-assembled capsids and viral tails that are the direct precursors to the assembled, infectious virus. During phage assembly, a motor complex (the terminase enzyme), specifically recognizes viral DNA then binds to the portal complex situated at a unique vertex of the icosahedral capsid; the portal is a ring-like structure that provides a hole through which DNA enters the capsid during assembly and exits during infection [START_REF] Catalano | Virus DNA packaging: the strategy used by phage lambda. (Translated from eng)[END_REF][START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF][START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF][START_REF] Rao | The bacteriophage DNA packaging motor. (Translated from eng[END_REF]. The terminase motors, which utilize ATP hydrolysis to drive DNA into the capsid, are among the most powerful biological motors characterized to date [START_REF] Catalano | Virus DNA packaging: the strategy used by phage lambda. (Translated from eng)[END_REF][START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF][START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF][START_REF] Rao | The bacteriophage DNA packaging motor. (Translated from eng[END_REF]. For instance, the bacteriophage λ terminase motor packages DNA to near-crystalline density, which generates an internal pressure in excess of 20 atmospheres. Commensurate with this requirement, the λ terminase motor exerts forces greater than 50 piconewtons during the terminal stages of genome packaging [START_REF] Smith | The bacteriophage phi 29 portal motor can package DNA against a large internal force[END_REF][START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF][START_REF] Fuller | Ionic effects on viral DNA packaging and motor function in bacteriophage phi 29[END_REF][START_REF] Fuller | Single phage T4 DNA packaging motors exhibit large force generation, high velocity, and dynamic variability[END_REF][START_REF] Rickgauer | Portal motor velocity and internal force resisting viral DNA packaging in bacteriophage phi29[END_REF]. Similar features are observed in many bacteriophages and the eukaryotic herpes virus groups. In the latter case, genome packaging occurs in the nucleus of an infected cell, following a pathway that is remarkably similar to that of the phage system, i.e., a terminase motor specifically packages viral DNA into the interior of a pre-assembled procapsid through a unique portal vertex [START_REF] Cardone | Visualization of the herpes simplex virus portal in situ by cryoelectron tomography[END_REF][START_REF] Newcomb | Uncoating the herpes simplex virus genome[END_REF][START_REF] Booy | Liquid-crystalline, phage-like packing of encapsidated DNA in herpes simplex virus[END_REF].

Using phage λ, Evilevitch and co-workers provided the first experimental in vitro evidence that internal pressure, often greater than 50 atm, ejects viral DNA from the capsid into the host cell [START_REF] Evilevitch | Osmotic pressure inhibition of DNA ejection from phage[END_REF][START_REF] Grayson | The effect of genome length on ejection forces in bacteriophage lambda[END_REF]. Since the internal capsid pressure is mainly the result of electrostatic repulsion between neighboring DNA strands, we found that the pressure is markedly reduced in the presence of multivalent cations (due to the screening of negative charges on the DNA), since capsids are permeable to water and salts [START_REF] Evilevitch | Effects of Salt Concentrations and Bending Energy on the Extent of Ejection of Phage Genomes[END_REF]. Similar results have been observed in singlemolecule laser tweezer experiments [START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF]. Consistent with this, we also found that internal pressure increases strongly with increasing length of the DNA packaged into the capsid, as the negative charge density increases [START_REF] Grayson | The effect of genome length on ejection forces in bacteriophage lambda[END_REF]. This may explain the observation in vivo that a λ genome can only be 8.8 % longer than the wild-type λ genome and still yield an infectious virus in vivo (15). DNA packaging is used for molecular cloning in so-called cell extract "packaging kits", where non-viral genes are inserted into the phage chromosome, packaged in vitro, delivered and expressed in bacterial cells [START_REF] Hohn | Packaging recombinant DNA molecules into bacteriophage particles in vitro[END_REF]. This technique has played a revolutionary role in the development of molecular biology and nanotechnology [START_REF] Glick | Molecular Biotechnology[END_REF]. However, while powerful, the size of an inserted gene is limited by the force of the terminase motor and its capacity to package oversized genomes into the capsid interior. During the early steps of the packaging process, the repulsive force exerted by the packaged DNA is smaller than the packaging force generated by the terminase motor. However, as the length of packaged DNA increases, repulsive forces increase and eventually exceed the maximum force that the motor can generate. Thus, the efficiency of viral packaging and virion synthesis are strongly dependent on the DNA length, ionic strength conditions, and types of cations included in the reaction mixture. Mg 2+ and spermidine 3+ can stabilize condensed DNA by reducing DNA-DNA repulsion. This may influence the rate of packaging and thus the number of successful packaging events. To our knowledge, no systematic or quantitative in vitro measurements have been made to explore the dependence of viral infectivity on the length of the packaged genome and the salt concentration, and the consequences for both controlled laboratory viral assembly (e.g. genetic engineering) and in vivo virus assembly. Indeed, this is not possible in the commercially available packaging kits that utilize crude cell extracts.

Catalano and co-workers recently developed an in vitro virus assembly system in which an infectious virus was assembled from purified components in a rigorously defined biochemical reaction mixture [START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF]. This allows detailed and quantitative interrogation of each step of the assembly pathway and manipulation of the reaction conditions in a strictly controlled manner. In this work, we exploit this system to investigate the correlation between the internal genome pressure, governed by both the genome length and ionic conditions, and virus infectivity. Our goal was to determine the maximum length of the packaged DNA in phage λ by packaging oversized DNA, relative to the wild-type (WT) λ genome length of 48,502 bp, under various ionic strength conditions. The length of DNA was systematically varied by incorporation of nonspecific plasmid DNA into the WT λ genome, and the packaging rate and efficiency were determined by several in vitro and in vivo assays. The results of these studies are discussed with respect to viral genome packaging in vivo and molecular cloning in vitro.

RESULTS

We constructed three oversized phage λ chromosomes: 51,206 bp (105%), 53,892 bp (110%) and 55,340 bp (114%) long, relative to the WT λ-genome length of 48,520 bp (corresponding to 100%), as described in Materials and Methods section. Briefly, we inserted linearized bacterial plasmids of defined lengths into the XbaI-digested λ chromosome (XbaI is a unique restriction site located at bp 24,511 of the λ sequence), without disturbing essential λ genes (Figure 1). The inserts contain two markers that allow detection of viral DNA entry into the host cell; lacZ for blue-clear bacterial colony detection, and ampR for ampicillin resistance (Figure 2). The oversized λ genomes were used as packaging substrates in our defined in vitro virus assembly system, as described previously [START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF]. The packaging buffer contained 20 mM Tris-HCl, pH 7.5, 4.5 mM MgCl 2 and 2 mM spermidine 3+ (buffer 0), which is optimal for the assembly of an infectious virus using a WT (100%) λ genome [START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF]. As anticipated, infection of E. coli JM83 cells (ampR -, lacZ -) with the in vitro assembled WT virus did not afford any bacterial colonies when plated on ampicillin-containing plates, because the WT genome does not contain the ampR gene. We next examined particle assembly and the infectivity of viruses assembled with each of the oversized genomes. As before, the genomes were used as packaging substrates in our in vitro virus assembly system, and E. coli JM83 was infected with the in vitro assembled virus. Successful packaging of the oversized genome into the procapsid, addition of a viral tail, and subsequent injection of the viral DNA into the host cell by the infectious assembled virus was indicated by the presence of blue colonies (lacZ) that grow in the presence of ampicillin (ampR) (Figure 2). The data presented in Table 1 demonstrate that oversized genomes up to 114% of the WT genome length can be successfully packaged in vitro, and that the virus is able to inject the oversized DNA into the host cell to render them ampicillin-resistant. Importantly, control experiments, in which ATP was omitted from the virus assembly reaction, and thus cannot package DNA, did not yield any colonies on ampicillin-containing plates, indicating that virus particle assembly is required for DNA entry into the cell. Finally, we investigated whether salt concentration affected in vitro virus assembly or infectivity, as follows. Each of the genomes was used as packaging substrate, as described above, except that spermidine was omitted from the reaction (buffer 1), or the concentration of Mg 2+ was reduced to 2 mM (buffer 2). (The terminase packaging motor has a strict divalent metal requirement, which precluded the complete omission of Mg 2+ from the reaction mixture ( 5)). All the oversized genomes could be packaged into infectious viruses in vitro under all buffer conditions examined (see below).

While the above results demonstrate that oversized genomes can be assembled into infectious viruses in vitro, they do not address the question of whether the oversized genomes can be replicated and packaged into infectious viruses in vivo. To directly address this question, we turned to a standard viral plaque assay. Each of the genomes was used to assemble an infectious virus, as described above. The in vitro assembled virus was then used to infect E. coli LE392 cells, and the number of infectious virus particles quantified by plating on a bacterial lawn [START_REF] Maniatis | Molecular Cloning A Laboratory Manual[END_REF]. Each of the observed plaques results from the infection of a single cell with a virus particle [START_REF] Maniatis | Molecular Cloning A Laboratory Manual[END_REF], and provides a direct method of quantifying the number of infectious virus particles in the assembly mixture. Further, the injected genome must be competent for multiple rounds of replication and infectious virus particle assembly within the host cell for a plaque to be visible. Thus, the generation of a viral plaque requires that the genome is competent for the assembly of an infectious virus both in vitro and in vivo.

The data presented in Table 1 demonstrate that the 105% and 110% oversized genomes provide a functional substrate for DNA replication and virus development in vivo, as evidenced by the appearance of viral plaques on the bacterial lawn. In contrast, the 114% genome substrate failed to yield visible plaques, despite the fact that the elongated genome can be packaged and subsequently delivered to the cell in vitro (Table 1). This indicates that a 114% long λ genome can be packaged under defined reaction conditions in vitro, but that the cellular cytoplasm does not provide an environment conducive to the assembly of an infectious virus with this genome, at least over the multiple infection cycles required to visualize a plaque. We have thus identified the limit of λ genome length that can be efficiently packaged in vivo.

While the number of plaques reflects the efficiency of virus assembly in vitro, the size of the viral plaque is related to the rate of virus particle assembly in vivo -the faster (more efficiently) the virus replicates in vivo, the larger the plaque. Figure 3 shows a direct comparison between the 100% and 110% λ genome phages plated on the same LE392 plate, which clearly demonstrates a significant difference in plaque size. As all other factors remain unchanged, and since genome packaging is the rate-limiting step in the concerted viral assembly process [START_REF]Lambda II[END_REF], we interpret the dramatic reduction in viral replication rate as a reflection of a decrease in the rate of genome packaging in vivo. This observation is however not trivial because there are more factors contributing to the plaque size at a given time.

The above interpretation assumes that the input genome was faithfully replicated and packaged in vivo to yield infectious, over-packaged virions. We considered the possibility that the oversized genomes were successfully packaged in vitro and injected into the host cell, but the duplex length was somehow shortened during replication in vivo to generate a viable virus. To directly examine this possibility, the DNA was extracted from the plaques derived from packaging the 105% and 110% oversized genomes. The size of the virion DNA was confirmed with pulsed-field gel electrophoresis, and Figure 4 shows that the input genome is faithfully replicated and packaged into infectious virus particles in vivo.

We next quantified the efficiency of virus assembly in vitro as a function of genome length. For these studies we utilized our standard reaction buffer 0 (20 mM Tris-HCl pH 7.5, 2 mM spermidine and 4.5 mM MgCl 2 ), and the assembly reaction was allowed to proceed for 2 hours to ensure that it had reached completion. Virus assembly was quantified by plaque assay.

The plates were incubated for 12 hours at 37°C, sufficient for the plaques to appear. As can be seen in Figure 5 (red dashed line), the number of plaques, and thus the efficiency of packaging, shows an exponential decrease with increasing packaged λ-DNA length. The number of assembled virions decreased exponentially by a factor of 100 for 5% extra packaged DNA length, relative to the WT. The titer fell by 1000 times when the λ-DNA length was increased from 100% to 110%, and would presumably be 10,000 times lower for the 114% λ-DNA sample.

The latter would reduce the transfection efficiency to less than that required for detection by the plaque assay. Similar relative drop in the packaging efficiency was also found for in vivo packaging in ref. (15), when increasing λ-DNA length from 105% to 108.8%. However, the initial drop in the efficiency when going from 100% to 105% λ-DNA length was smaller than in the present study. This is explained by the fact that salt conditions cannot be controlled in an in vivo packaging process unlike in our in vitro packaging study. As we have shown here, packaging efficiency will have a strong ionic dependence for smaller variation in the packaged DNA length around 100% WT λ-DNA length (see also discussion below).

Finally, we quantified the effect of salt concentration on the efficiency of virus assembly in vitro. Specifically, we decreased the concentrations of spermidine 3+ (Figure 5, green dashed line) and Mg 2+ (Figure 5, blue dashed line) independently, to ensure that any observed effect was the result of a counterion-induced decrease in DNA-DNA repulsion, rather than the effect of a specific salt on the viral protein assembly during packaging. In both cases, decreasing the counterion concentration significantly decreased the yield of infectious viruses in vitro, with spermidine exhibiting slightly stronger effects (Figure 5).

DISCUSSION

We have examined the assembly of an infectious λ virus in vitro under rigorously defined conditions, and have demonstrated that both the rate and extent of particle assembly are strongly affected by the length of the genome substrate. We have further demonstrated that while very large DNA duplexes (114% of WT genome length) can be packaged into a particle and efficiently delivered to a host cell in vitro, there is a more stringent limit on virus development in vivo. What limits the efficiency of packaging over-sized genomes?

Effect of DNA length on the packaging efficiency and viral infectivity.

There is an exponential decrease in the yield of infectious viral particles assembled in vitro as a function of genome length. The only variable in the assembly reaction is the length of the DNA used as a packaging substrate, and we suggest two reasonable explanations of this finding. First, it might reflect differences in the rate of assembly of the packaging motor complex. The reactions are initiated by terminase, which must bind to the DNA, and the binary complex must then bind to the procapsid to initiate packaging. It is unlikely that a change in the genome length would affect the activation of the packaging motor once assembled. We consider, however, that the ratelimiting step in packaging initiation is related to the free diffusion of the DNA coil in the solution in order to first find a terminase and a free procapsid. From classical polymer physics it can be estimated that the change in diffusion coefficient for two different DNA lengths, L WT and L, scales as

€ D(L) ≈ D(L WT ) L WT /L ( ) ν
, where the exponent of polymer statistics is

€ ν = 1/2 or 3/5
for an ideal Gaussian chain or a swollen chain [START_REF] Doi | The theory of polymer dynamics[END_REF]. As a consequence, we anticipate a reduction of only 5% in the diffusion coefficient of the DNA coil when its length is increased from the WT length to 110% of the WT length. This modest change in diffusion coefficient is unlikely to be responsible for the large decrease in virus assembly (of the order of 10 3 ) observed in our experiments.

An alternative explanation is that the observed decrease in the rate and extent of infectious particle assembly reflect a significant increase in the time required to package the oversized duplex, and a decrease in the efficiency of particle completion in the face of an overpackaged capsid, respectively (Figure 1). As we argue below, this exponential decay is related to the dynamic properties of the terminase packaging motor under an external load (i.e. the external load does not arise from the motor itself).

The mechanical properties of viral packaging motors have been characterized experimentally as a dynamic intrinsic property of the motor, regardless of DNA filling inside the capsid. The origin of this exponential behavior is intimately related to the decrease in power stroke efficiency of the terminase motor under an opposing external load [START_REF] Jülicher | Modeling molecular motors[END_REF] and the increased frequency of slips of the DNA as it is being packaged at higher loading forces [START_REF] Smith | The bacteriophage phi 29 portal motor can package DNA against a large internal force[END_REF]. The equations require an irreversible step, which is the case here because cos-cleavage of λ-DNA is irreversible.

In the absence of an external load, it has also been observed that packaging rate slows down dramatically after the first 30% of the WT λ-genome has been packaged. This is the signature of the internal force build-up that resists active packaging by the motor, arising from the DNA confinement in the capsid. Slowing of the packaging rate is qualitatively described by a similar relation between velocity and force

€ v(L) ≈ v 0 exp - F int (L)δ kT % & ' ( ) *
, where L is the packaged length and (L) is the internal force associated with the confinement of DNA of length L within the capsid. Therefore, we used this relation to estimate the average time, T(L), required to package DNA of length L,

€ F int
€ T(L) = dx 1 L ∫ exp F int (x)δ kT $ % & ' ( ) v 0 .
For DNA around the same length as that of WT (48.5kb) or larger, Fuller et al. [START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF] showed that the internal force is large (25 pN at 90% of WT DNA length). Assuming, for the sake of simplicity, that the relation between the internal force and the genome length is linear above the WT DNA length in the range addressed in our experiments, the average time required to package a length L, that is larger than the WT length L WT , scales roughly as suggested both by the experimental results of Fuller et al. [START_REF] Fuller | Measurements of single DNA molecule packaging dynamics in bacteriophage lambda reveal high forces, high motor processivity, and capsid transformations[END_REF] and by DNA packaging models, such as the inverse spool model [START_REF] Kindt | DNA packaging and ejection forces in bacteriophage[END_REF][START_REF] Tzlil | Forces and pressures in DNA packaging and release from viral capsids[END_REF][START_REF] Purohit | Mechanics of DNA packaging in viruses[END_REF][START_REF] Purohit | Forces during bacteriophage DNA packaging and ejection[END_REF]:

€ T(L) ≅ T L WT ( ) + kT exp A(L -L WT )δ kT % & ' ( ) * Av 0 δ (Eq. 1)
where A is the coefficient of the linear relationship between the internal force and the genome length. The dynamic properties of the terminase motor therefore predict an exponential increase in the time required to fully package oversized genomes. As a consequence, the rate of virus assembly € J(L) = 1/T(L) will decay exponentially with the genome length. This conclusion implicitly assumes that the rate-limiting step for the production of N viruses is the assembly rate, such that € N(L) ≈ J(L )T exp , where € T exp is the duration of the packaging experiment. Provided that the incubation time for in vitro phage packaging and assembly was 2 hours for all samples, and that the assembly components and enzymes retain their activity during this time period, exponential decay in the production rate leads to the exponential decay of the number of assembled, infectious phage particles, in agreement with the experimental results presented here.

Infinitely long packaging times may not even be feasible in vivo as cells may run out of ATP required for packaging, and/or the packaging enzymes and viral DNA may be degraded. Indeed, the decrease in plaque size as a function of genome size indicates that the rate of particle assembly is also dramatically slower in vivo. Thus, a change in the packaged DNA length of even a few percent, accompanied by an increase in the internal pressure, will have dramatic consequences for viral reproduction and the spread of infection, decreasing by several orders of magnitude.

Effect of salt on DNA packaging. The data presented here provide further information on the influence of ionic species on the efficiency of virus assembly under rigorously defined conditions. Our results are consistent with recent single-molecule laser tweezer studies showing that polyamines and Mg 2+ decrease the internal force resisting packaging [START_REF] Fuller | Ionic effects on viral DNA packaging and motor function in bacteriophage phi 29[END_REF]. Moreover, the single-molecule packaging rate is systematically faster in the presence of multivalent ions, at least when packaging a unit-length WT genome. The consequence of this observation is that the time required to package DNA up to WT genome length should be shorter in the presence of multivalent ions. Our data indicate that the time required to package DNA beyond its WT length, up to 110% of the natural genome, depends strongly on a combination of the dynamic properties of the motor and the force resisting packaging. Examination of Fuller's measurements [START_REF] Fuller | Ionic effects on viral DNA packaging and motor function in bacteriophage phi 29[END_REF] suggests that the relation between the internal force and packaged DNA length around the WT length is still linear and is only slightly dependent on the ionic conditions. Therefore, the previous scaling estimation of the time required for packaging of oversized λ-DNA can be reproduced.

These two observations lead to the following conclusion: the initial packaging of DNA up to WT genome length is faster in the presence of multivalent ions, but the duration of the later stages of packaging beyond the WT genome length should still increase exponentially with genome length. As a consequence, our approach predicts that the addition of multivalent ions will increase the phage production rate at constant genome length, while maintaining approximately the same exponential decay with increasing genome length. This matches our experimental data qualitatively (Figure 5) and further confirms our interpretation of the overpackaging data. Thus, the phage production rate is increased with more efficient cation induced reduction of DNA-DNA repulsive force resisting packaging. This is achieved by higher cation charge (as can be seen by comparing spermidine 3+ and Mg 2+ , both naturally present in the E. coli cytoplasm) or an increase in the overall ionic strength (Figure 5). Ionic strength values, I, for all three buffers were 13.5 mM, 18 mM and 25.5 mM, respectively, excluding the contribution from the Tris buffer.

It is interesting to note that with increasing DNA length, the effect of salt on the packaging efficiency becomes weaker. It can be seen in Figure 5 that the addition of 2 mM spermidine 3+ (with 4.5 mM Mg 2+ in both buffers 0 and 1) increases the titer by ≈20 times for 100% λ-DNA length, but only by ≈8 times for 110% λ-DNA packaging. In Figure 5, it can be seen that increasing the ionic strength from 13.5 mM (buffer 1) to 18 mM (buffer 2), increases the titer by ≈1.5 times for 100% λ-DNA but there is no titer change for 110% λ-DNA. Thus, the phage titer curves at different ionic conditions shown in Figure 5 are converging with increasing DNA length. 1 This observation is consistent with well-documented observations using osmotic stress experiments [START_REF] Leikin | Measured entropy and enthalpy of hydration as a function of distance between DNA double helices[END_REF][START_REF] Parsegian | Water near intracellular surfaces[END_REF][START_REF] Rau | Direct measurement of temperature-dependent solvation forces between DNA double helices[END_REF], where it was shown that DNA-DNA interactions in dense hexagonal phases of DNA (similar to DNA densities in overpackaged phage λ) are dominated by the hydration forces and have little dependency on the identity of the salt. Furthermore, high DNA packaging densities lead to several times higher counter-ion concentration at the interior of the capsid, compared to the bulk, making the internal forces less sensitive to the external ion content [START_REF] Nevsten | Chemical mapping of DNA and counter-ion content inside phage by energy-filtered TEM[END_REF][START_REF] Li | Osmotic pressure and packaging structure of caged DNA[END_REF]. 1 It should be noted that y-axis, showing pfu/mL, is plotted on a log-scale, making the lines look essentially parallel. However, the differences in phage titer described above between different buffers at various DNA lengths are significant as all 3 exponential curves are asymptotically approaching zero.

CONCLUSIONS

Elegant studies by Feiss co-workers (15) have demonstrated that genomes as long as 1.08 could be packaged from di-lysogens in vivo, which sets an upper limit on productive virus development in the cell. The goal of this work was to (i) define the physical limit of DNA that can be inserted into a capsid by the terminase motor and (ii) to elucidate the role of the internal genome pressure on virion synthesis and viral infectivity. These studies take advantage of biochemically defined in vitro virus assembly assay recently developed in the Catalano lab. The genome pressure was varied by changing two parameters: DNA length and salt condition in the virus packaging-assembly buffer. The key to these measurements was our recently developed system for the in vitro assembly of infectious phage λ, using individually purified components in a rigorously defined biochemical assay [START_REF] Gaussier | Building a virus from scratch: assembly of an infectious virus using purified components in a rigorously defined biochemical assay system[END_REF]. For the first time, we were able to quantitatively measure a dramatic reduction in the phage production rate associated with the packaging of DNA longer than the WT genome in the phage λ capsid. These measurements reveal important biological implications. The first is that it is possible to package DNA up to 114% of the WT genome length for phage λ. Moreover, by using different ionic conditions, we demonstrated that overpackaging is a rather robust feature.

The results of our investigations have implications with respect to the presence and the origin of a maximum length of DNA that can be packaged within a viral capsid. Indeed, we found that longer DNA than WT genome length can be packaged. However, the rate of packaging, and thus the number of phages produced in a given time, decreases exponentially with increasing genome length. More precisely, a 1% increase in the length of the packaged genome above WT, leads to ten-fold decrease in the viral titer. Moreover, since salt decreases the internal pressure, adding extra salt increases the titer. With higher packaging density (above 110% of WT λ-DNA) the hydration force dominates the DNA-DNA interaction and the pressure is only weakly affected by the addition of counterions, making the packaging rate essentially insensitive to salt conditions. As a consequence, we found that the maximum length of DNA that could be packaged is not limited by the salt conditions of the virus assembly environment.

Instead, it is limited by the maximum force that the terminase motor can exert. Remarkably, we also found that maximum length of DNA that can be packaged in vivo is between 110 and 114% of WT λ-DNA, however the packaging efficiency was very low.

These observations illustrate that the dynamics of the viral packaging motor is exponentially dependent on the genome length. The motor packaging rate approaches zero asymptotically as the internal pressure increases. Thus, there is no mechanical limit on the length of DNA that can be packaged (assuming that the capsid can withstand any force). This has interesting implications on DNA packaging by the "headful" phages. These viruses initiate packaging at a specific "pac" site in the concatemer, but package longer than unit length duplexes (102-104% genome length). The mechanism that defines the downstream cut site remains unclear, but slowing of the terminase packaging motor certainly plays a major role.

Indeed, a simple model is that upon packaging a headful of DNA, the terminase motor slows to essentially zero as the pressure of the packaged DNA overcomes the power of the motor. This provides time for the slow endonuclease activity of terminase to cut the duplex to complete the packaging process.

In the case of unit-length genome packaging viruses such as λ, the packaging time becomes infinitely long as DNA length exceeds WT, preventing viruses from assembling within reasonable time (or at all) to complete their replication cycle. This suggests that the length of the packaged genome has been evolutionarily optimized to packaging densities where the effect of salt on the motor efficiency is minimized, making packaging more robust and less prone to changes in the cellular environment. Most importantly, these findings demonstrate that slight changes in the internal pressure induced by variation in the DNA length, will have fatal consequences for virus synthesis and the spread of infectious particles. This was demonstrated by the dramatic reduction in the number (efficiency) and size (rate) of plaques. These observations strengthen the role of internal pressure in the infectivity process, in agreement with several in vivo studies [START_REF] Koster | Influence of internal capsid pressure on viral infection by phage lambda[END_REF][START_REF] Paepe | Viruses' life history: towards a mechanistic basis of a trade-off between survival and reproduction among phages[END_REF]. This study also suggests new strategies for interfering with viral infectivity through small changes in the internal genome pressure in the case of motor-packaged DNA viruses.

At the same time, the fact that overpackaging is possible in various environments might be considered as a potential evolutionary advantage: as phage λ would therefore have the ability to modulate its genome length, since both its terminase motor characteristics and its host (the bacteria) are capable of packaging a genome larger than the WT length. More precisely, our finding of an effective upper limit for packaging of the oversized 114% WT DNA means that modulation of genome length is possible up to an extra length of 6.8 kb. Considering that the typical average size of a gene is of the order of 1 kb, phage λ therefore has the ability to increase its genome by at least or two genes. This is a remarkable feature with respect to the adaptation of the virus to its environment.

Based on recent results obtained in our studies [START_REF] Ivanovska | Internal DNA pressure modifies stability of WT phage[END_REF][START_REF] Evilevitch | Effects of salts on internal DNA pressure and mechanical properties of phage capsids. (Translated from eng[END_REF] and those at other labs (4), on the physical properties of phage λ, we speculate that λ WT length is the optimal result of a balance between a large number of genes, in order to function properly, a long genome length in order to be able to efficiently initiate passive ejection of the genome into the host bacteria, and a genome length short enough that efficient virus production is compatible with the time frame of the cell cycle.

MATERIALS AND METHODS

Construction of oversized phage λ chromosomes. Oversized phage λ chromosomes, 105%, 110% and 114% of the length of the wild type, were constructed by insertion of linearized bacterial plasmids of defined length into the XbaI-digested λ chromosome. XbaI is a unique restriction site that is located at 24511 base pairs in an inert gene that seemingly does not affect phage replication. 200 µg of λ DNA (dam -dcm -) was digested with 20 units XbaI at 37 ºC during a period of 12 hours. Digested λ DNA was treated with calf intestinal alkaline phosphatase at 37 ºC for 5 hours. The λ DNA was then purified using a phenol-chloroform purification technique.

Bacterial plasmid pUC19 (Amp R and LacZ + , 2686 base pairs) was used for construction of the 105% and 110% λ chromosomes. Firstly, it was made compatible for the ligation with the digested λ DNA. An adaptor was inserted into its unique PscI site. The adaptor (5'-CATGGCTAGCAACCTAGGAAACTAGT-3' and 5'-CATGACTAGTTTCCTAGGTT GCTAGC -3') carries three restriction sites (NheI, AvrII and SpeI), all of which produce sticky ends compatible with those of XbaI. Thus, modified-pUC19 was generated. This was consequently used for the construction of double-pUC19, which is basically two fused copies of the same plasmid. Modified-pUC19 was digested with NheI, purified from 0.8% agarose gel and ligated with itself. Ligation products, amplified in E. coli, were enzymatically linearized and separated on 0.8% agarose gel electrophoresis. The DNA fragment corresponding to twice the size of pUC19 was extracted, purified and circularized with T4 DNA ligase. Thus double-pUC19

(5372 base pairs) was created. For the construction of the 114% λ chromosome, plasmid pSV-bgalactosidase (Amp R and LacZ + , 6820 base pairs) was used. This plasmid has a unique XbaI site, which is conveniently located in an inert region.

was used for in vivo assays. Positive controls were similarly prepared using wild-type DNA.

In vivo assays using E. coli

In order to test our viral assembly system, we performed phenol-chloroform extraction of DNA from the packaged viral heads (directly after the packaging step). Extracted DNA was separated on 0.8% agarose gel for qualitative determination. However, this approach was successful only for the wild-type phage, as the DNA yield from the overpackaged phages was too low to be detected at this stage. Therefore, we performed two complimentary in vivo tests.

Blue-clear screening was performed in order to confirm the integration of the plasmid DNA into the phage λ chromosome. Assembled phages were used to infect E. coli JM83 (AmpR - LacZ -), grown to an OD 600 of 1.0 in LB medium supplemented with 10 mM MgSO 4 and 0.2% (w/v) maltose. Infected cells were spread on LB agar plates containing 100 µg/ml ampicillin, 40 µg/ml X-gal and 0.5 mM IPTG (isopropyl β-D-1-thiogalactopyranoside). Plates were incubated at 37 ºC for 12 hours. E. coli JM83 infected with overpackaged phage λ yielded blue colonies, whereas E. coli JM83 infected with the wild-type phage λ did not yield any colonies. This in vivo test clearly demonstrated that the presence of phage-delivered Amp R and LacZ genes provides E. coli JM83 with ampicillin resistance and blue pigmentation. It is thus an indicator of the successful construction of oversized phage λ chromosomes.

Plaque assay was performed for quantitative determination of packaging efficiency and in vivo infectivity of the overpackaged phages. Assembled phages were diluted 10, 100 and 500 times and mixed with 100 µl E. coli LE392, which was grown to an OD 600 of 1.0 in LB medium supplemented with 10 mM MgSO 4 and 0.2% (w/v) maltose. Infected cells were spread on LB agar plates. The plates were incubated at 37 ºC for 12 hours. Pulsed-field gel electrophoresis was used to visualize the DNA and assess the difference in size, using CHEF DR II electrophoresis equipment (Bio-Rad). Purified DNA samples were loaded into 1% agarose gel. The gel was run for 26.5 hours in 0.5x TBE buffer using the following conditions: initial switch of 2.9 seconds, final switch of 4.5 seconds and voltage of 6 V/cm. The gel was later stained with SYBR Gold nucleic acid dye and visualized under 302 nm UV. We observed a clear size difference between wild-type, 105% and 110% λ DNA bands.

DNA saturation experiments:

The amount of DNA used for the assembly of overpackaged λ phages affected the final yield, i.e. the number of plaques, as was previously shown [START_REF] Evilevitch | Osmotic pressure inhibition of DNA ejection from phage[END_REF].

Therefore, we had to establish saturation levels for 105% and 110% DNA empirically. Since the ligation product used as packaging substrate was mixture of various DNA products, including the oversized DNA product, we used weight units (µg) of total DNA used for saturation level experiments. We designed phage assembly experiments (as described above) where various weight units, between 3 and 40 µg, of DNA substrate were used. Packaging buffer 0 was used for this experiment. These phages were subsequently used for plaque assay, as described above.

Plaque numbers were counted and used to estimate the DNA load per packaging reaction that would ensure the oversaturation of packaging mixture with the DNA substrate. These saturation levels were later used in further experiments for the determination of the dependence of packaging efficiency on the ionic strength.

  experimentally at the single molecule level during the past decade[START_REF] Smith | The bacteriophage phi 29 portal motor can package DNA against a large internal force[END_REF]. Using laser tweezer techniques, it has been shown for phage λ (4) and for phage φ29[START_REF] Chemla | Mechanism of force generation of a viral DNA packaging motor[END_REF], that if an external load challenges the active packaging process of the terminase motor, the leading order relation between the packaging rate v and this external load F scales as € v ≈ v 0 expthe measured velocity in the absence of the load, and € δ is the step size of the motor, k is Boltzmann's constant and T is the temperature. Note that this relation has been established

Figure 1 :

 1 Figure 1: Over-sized phage λ chromosomes of length 105%, 110% and were built by insertion of linearized bacterial plasmids of defined length into the XbaI-digested λ chromosome.All plasmids contained Amp R and LacZ genes providing ampicillin resistance and blue pigmentation upon infection of E.coli JM83. It is an indicator of successful construction and packaging of oversized phage λ chromosomes in vitro. In parallel, efficiency of the in vivo phage assembly after the bacterial cell infection is monitored by plaque assay, revealing the number of assembled and infectious phage particles determined by the number of plaques per plate.

Figure 2 :

 2 Figure2: Blue-clear screening was performed in order to confirm integration of the plasmid DNA into the phage λ chromosome. Assembled phages were used to infect E.coli JM83 (AmpR - LacZ -). Infected cells were spread on LB-agar plates. E.coli JM83 infected with overpackaged phage λ yielded blue colonies, whereas E.coli JM83 infected with wild-type phage λ did not yield any colonies. This in vitro assembly test clearly demonstrated that presence of phagedelivered Amp R and LacZ genes provides ampicillin resistance and blue pigmentation to E.coli JM83 (Petri dish photo is shown next to the cartoon). Plaque assay was performed as a quantitative test of the virion assembly efficiency in vivo. Assembled phages were mixed with E.coli LE392. Infected cells were spread on LB-agar plates and after 12 hours incubation at 37 °C plaques could be observed (Petri dish photo is shown next to the cartoon).

Figure 3 :

 3 Figure 3: Plaque assay for WT (100%) and 110% λ-DNA phages on E. coli LE392 plate, illustrating large plaques for 100% DNA phage and small plaques for 110% DNA phage.

Figure 4 :

 4 Figure 4: Pulsed-field gel electrophoresis of DNA extracted from plaques carrying oversized λ genomes.

Figure 5 :

 5 Figure 5: Efficiency of packaging monitored by plaque assay. pfu/mL is plotted on a log-scale versus % of packaged DNA length (100% corresponds to the wild-type λ-DNA length).

ACKNOWLEDGMENTS: We would like to thank William Gelbart and Charles Knobler for fruitful discussions and inspiration, Lars-Olof Hedén for tremendous help with the microbiological part of this project, and John Pettersson for technical help. This work was supported by Carl Trygger's Foundation grant to AE and the Swedish Research Council (VR) grant to AE (grant # 2008-726).

In order to construct the 105%, and 114% λ chromosomes, 50 µg of each of the modified-pUC19, double-pUC19 and pSV-β-galactosidase plasmids were digested separately with 10 units of SpeI (for modified-pUC19 and double-pUC19) and XbaI (for pSV-βgalactosidase) at 37 ºC over the course of 12 hours. DNA was subsequently separated on 0.8% agarose gel electrophoresis, and fragments corresponding to 2686, 5372 and 6820 base pairs were extracted and purified. Ligation reactions were subsequently performed with XbaI-digested and dephosphorylated λ DNA. 0.8 µg of λ DNA was used per 50 µl of ligation reaction, into which 1 unit of T4 DNA ligase was introduced. A molar ratio of 1:8 (1 for λ DNA, 8 for plasmid) was employed. Reactions were performed at 16 °C for 12 hours. Ligation was accompanied by four negative control reactions, in which the reaction components were sequentially removed: 1) no plasmid insert, 2) no T4 ligase, 3) no λ DNA, and 4) no λ DNA and no T4 ligase. The phenol-chloroform-purified total DNA product from ligation reactions was used as packaging substrate.

Assembly of oversized λ-DNA phages. Phage λ was built from scratch from its recombinantly produced protein components in a two-step process. In comparison to the initially described method (1), we have slightly modified this process in terms of DNA and packaging buffer. In the packaging step, the following viral components were sequentially mixed in [START_REF] Purohit | Mechanics of DNA packaging in viruses[END_REF] The quantities of DNA used for this step were empirically determined (as described below).

After incubation for 2 hours at 25 ºC, the packaging process was considered complete.

Prior to the subsequent assembly step, the viral tail segment was constructed by mixing 417 µM gpFII, 413 µM gpW and 320 nM tail in 10 µl reaction, with 20 mM Tris-HCl pH 7.5, 2 mM spermidine, 3 mM MgCl 2 , 7 mM β-mercaptoethanol and 25 mM potassium glutamate. This mixture was then added to the packaged viral shells from the previous step and incubated for 2 hours at 37 ºC. This step resulted in a fully infective phage. Subsequently, the complete λ phage


Virgile Garcia
email: virgile.garcia@inrialpes.fr

Chung Shue Chen
email: chungshue.chen@alcatel-lucent.com

Nikolai Lebedev
email: lebedev@cpe.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

Self-Optimized Precoding and Power Control in Cellular Networks

Keywords: Mobile cellular networks, interference management, precoding, power control, Gibbs sampler, self-optimization

In this paper, we propose an autonomous radio resource allocation and optimization scheme that chooses the transmit power and precoding vector among codebooks for multiple antennas transmitters to improve spectral and power efficiency and provide user fairness. Network self-optimization is an essential feature for supporting the cell densification in future wireless cellular systems. The proposed self-optimization is inspired by Gibbs sampler. We show that it can be implemented in a distributed manner and nevertheless achieves systemwide optimization which improves network throughput, power utilization efficiency, and overall service fairness. In addition, we extend the work and include power pricing to parametrize and enhance energy efficiency further. Simulation results show that the proposed scheme can outperform today's default modes of operation in network throughput, energy efficiency, and user fairness.

I. INTRODUCTION

Today, it is commonly anticipated that cellular networks will further evolve to denser and smaller cells, with a strong spatial frequency reuse, possibly with the whole spectrum resource made available within each cell (reuse 1) [START_REF] Necker | Towards frequency reuse 1 cellular FDM/TDM systems[END_REF]. Systems such as LTE and LTE-Advanced [START_REF]3rd Generation Partnership Project. 3GPP-LTE (Long Term Evolution)[END_REF] intend to use small cells in urban environment to create local coverage to maximize spatial reuse and support rapidly increasing data traffic. However, a dense deployment of base stations (BS) with shorter coverage range will bring new challenges to inter-cell interference management (especially at the cell boundaries) and its complexity.

Such networks are characterized by an increasing number of distributed infrastructure elements and the unpredictability of the base station and user patterns. Self-organization and selfoptimization networks (SON) becomes necessary in order to prevent a huge increase of planning and optimization tasks [START_REF]Next Generation Mobile Networks Group[END_REF]. Autonomic management and configuration is highly desirable in practice to reduce the system's capital and operational expenditure (CAPEX/OPEX) [START_REF] Schmelz | Self-organisation in wireless networks -use cases and their interrelations[END_REF].

Radio resource management (RRM) has the fundamental role of sharing power and resource slots among users to satisfy their service requirements. Therefore, in this context, an efficient mechanism should allow a base station or the transmitter to decide and conduct operations in a distributed manner following the resource allocation policy, taking interference into account and automatically adapting to the interaction of neighbor cells.

It is well known that optimizing system throughput and fairness through parameters such as transmit power, precoding vector (when several transmit antennas are available) and channel allocation is very effective in many wireless systems including mobile cellular networks. However, the optimization of multi-cell system over interfering links often leads to non-convex optimization problems. The design of efficient algorithms operating in a distributed manner and ensuring global optimality in these networks is always very challenging [START_REF] Chiang | Power control in wireless cellular networks[END_REF]Chap. 7.5].

In this paper, we propose a distributed algorithm performing self-optimization for cellular networks (e.g., LTE and femtocell), focusing on multiple transmit antenna power control and precoding. The objectives are to improve spectral efficiency, user fairness, and also power utilization efficiency. The proposed solution is inspired by Gibbs sampler (see e.g., [START_REF] Brémaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF]). It is an extension of the work in [START_REF] Chen | Self-optimization in mobile cellular networks: power control and user association[END_REF] which only takes into account user association and power control, and is limited to single antenna systems. In this paper, we generalize the Gibbs sampler to include multiple transmit antennas and precoding. Furthermore, we present an extended cost function, considering power pricing, to parametrize the power efficiency of the system. Results show that the solution can be implemented in a distributed manner and nevertheless improves systemwide spectrum utilization efficiency. Finally, we investigate the power and spectrum efficiency trade-off which can be achieved for different purposes.

The rest of the paper is organized as follows. Section II presents the system model and problem formulation. Section III describes the proposed solution. Section IV compares this solution to other approaches with numerical studies. This work is concluded in section V.

II. SYSTEM MODEL

We here consider that downlink and uplink channels are orthogonal. This paper deals with the downlink resource sharing problem. We consider a reuse-1 mobile cellular network with a set of base stations B serving a set of users U.

We first assume each user u is associated to the base station b u ∈ B that has the smallest pathloss, which can be determined from the pilots, for example. LTE and LTE-A systems divide the available bandwidth into multiple orthogonal resource blocks (RB). In each cell, a single user is allocated per RB, from a pure local decision. For the sake of simplicity, we focus in this paper on a given RB simultaneously used by all BS. Therefore, for this RB, this is equivalent to a single resource full-reuse system. Note that this approach is suboptimal and a more complete optimization could be achieved by a joint optimization of the RB selection, power control, and precoder. The more general case considering multiple-resource allocation is a subject of on-going work. In this paper, we will only focus on the power and precoder optimization.

N t antennas are assumed at base stations and single antenna at users. At user u, served by a BS b u , the received signal is given by:

y u = P u l bu,u h bu,u w u x u + v∈U ,v =u P v l bv ,u h bv ,u w v x v + z u (1)
where P u denotes the transmission power used by b u to u, x u is the transmitted symbol for user u, z u is the receiver noise at u, considered white and Gaussian with variance N u , l bu,u denotes the distance dependent path loss, including shadowing, common to all antenna links, from b u to u, h bu,u ∈ C 1×Nt denotes the specific channel state on the N t links, and w u ∈ C Nt×1 denotes the unitary precoding vector used at the BS. Assuming coherent detection at receivers, the signalto-interference-plus-noise ratio (SINR) can be expressed as:

SINR u P u l bu,u |h bu,u w u | 2 N u + v∈U ,v =u P v l bv ,u |h bv ,u w v | 2 . (2)
In (2), we consider that adjacent-channel interference is negligible compared to co-channel interference.

Considering that some Channel State Information (CSI) are known at transmitter side, base stations can use transmit precoding vectors, to improve user signal quality. The details of information required will be discussed in sub-section III-B.

Our work aims at achieving a global optimization of the network, in terms of user fairness, network throughput and power consumption, using appropriate precoding and power allocation to balance active signals and interference.

A. Problem Formulation

To achieve this goal, we choose the harmonic-mean fairness, applied on user SINRs, for mathematical convenience (see below). Note that this fairness is an surrogate of the notion of minimal potential delay fairness proposed in [START_REF] Massoulié | Bandwidth sharing: objectives and algorithms[END_REF]. We call E the global energy, the cost function to be minimized, following the terminology of Gibbs sampler, which is given by:

E u∈U 1 SINR u . (3)
The optimization aims at finding a configuration, also referred to as a state, of precoding vectors w u and power allocation P u for all u, which minimizes E.

This cost function provides by itself a fairness constraint since a user with a low SINR will lead to a high penalty (and vice versa). Meanwhile, it will balance the interference generated from a BS to other users, since for example increasing the power for a user will increase its SINR but decrease the SINRs of others.

Following [START_REF]3rd Generation Partnership Project. 3GPP-LTE (Long Term Evolution)[END_REF], the global energy E can be written as:

E = u∈U N u + v∈U ,v =u P v l bv ,u |h bv ,u w v | 2 P u l bu,u |h bu,u w u | 2 = {u,v}⊆U P v l bv,u |h bv ,u w v | 2 P u l bu,u |h bu,u w u | 2 + P u l bu,v |h bu,v w u | 2 P v l bv ,v |h bv ,v w v | 2 + u∈U N u P u l bu,u |h bu,u w u | 2 . ( 4
)
The above minimization problem is clearly non-convex, with a high combinatorial complexity and is in general not possible to solve analytically for large networks.

It is observed that E derives from a potential function V (V) [START_REF] Brémaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF] as follows: for all subsets V ⊆ U, (4) can be expressed as:

E = V⊆U V (V), (5)
where the potential function V (•) has the following form:

                     V (V) = N u P u l bu,u |h bu,u w u | 2 if V = {u}, V (V) = P v l bv ,u |h bv ,v w v | 2 P u l bu,u |h bu,u w u | 2 + Pul bu,v |h bu,v wu| 2 Pv l bv ,v |h bv ,v wv | 2 if V = {u, v}, V (V) = 0 if |V| ≥ 3, (6)
where |V| denotes the cardinality of V.

A global energy which derives from the above potential function satisfying the condition that V (V) = 0 for |V| ≥ 3 is amenable to a distributed optimization by Gibbs sampler with the following local energy [START_REF] Chen | Self-optimization in mobile cellular networks: power control and user association[END_REF] at each u:

E u = u∈V ,V⊆U V (V). (7)
Following the above definition of V (•) and ( 7), we have:

E u = N u + v =u P v l bv ,u |h bv ,u w v | 2 P u l bu,u |h bu,u w u | 2 =1/SINRu + v =u P u l bu,v |h bu,v w u | 2 P v l bv,v |h bv ,u w v | 2 . ( 8
)
Eq.( 8) can be decomposed in two parts, one favoring the user u ("selfish") and one evaluating the impact of u's transmission on the rest of the network ("altruistic"). Note that the selfish term 1/SINR u is directly linked to the performance of user u. On the other hand, the "altruistic" part of the local energy measures the interference generated on other users, i.e., v = u, compared to the power of signal received from their own base stations. The optimization then has a trade-off to perform among all the users.

B. Extension to Power Price

Intuitively, one can guess that this optimization will balance the transmit powers used at BS, and so an overall power reduction (compared to the maximum power) will be observed. This phenomenon is due to the fact of the selfish and altruistic parts in (8): a high transmit power level for a given user will interfere too much the neighbouring users while a too low power will not provide this user high enough SINR. Numerical studies in Section IV will illustrate the power consumption aspects.

Notice that the minimization of (3) does not offer a direct control and optimization of the power utilization efficiency of the system. We therefore generalize (3) so as to explicitly relate the transmission power consumption, by introducing the following power pricing setup:

E p u∈U 1 SINR u + u∈U λ u P u , (9)
where λ u is the price parameter for each user. Note that ( 9) is equivalent to (3) when λ u = 0, ∀u. Without loss of generality, we consider in the following that all transmissions have an identical pricing, i.e., λ u = λ, ∀u. A high value of λ favors low power consumptions but will decrease the throughputs. Notice that one can see that cost functions which explicitly maximize power efficiency in a way such as min u Pu SINRu could tend to a zero capacity for all the users and so are not practical.

Following the same reasoning as in sub-section II-A, the local energy with power pricing is expressible as:

E p u = N u + v =u P v l bv,u |h bv ,u w v | 2 P u l bu,u |h bu,u w u | 2 + v =u P u l bu,v |h bu,v w u | 2 P v l bv ,v |h bv ,u w v | 2 + λP u . (10)

III. SELF OPTIMIZATION BY GIBBS SAMPLER

The following presents the system setup and optimization procedure. Note that this is a distributed algorithm that has to be performed for each mobile independently. The minimization of E can be conducted by Gibbs sampler on a graph of the network defined below:

• The set of nodes of the graph is the set of users, denoted by u ∈ U. • Each node is given a state variable s belonging to a finite set S. Here, the state of a node is the transmit power allocated to it, P u and the precoding vector used, w u .

• The set of neighbors of a node u in the graph is the set of all users v = u such that the power of the signal received at u from a base station of v is above a specific threshold, say θ (for practical consideration, we assume that it is the same for all). Note that for practical reason, power level is discretized in such a way that P u ∈ {P min , . . . , P max }. Precoding vectors are N t -dimensional, complex unitary vectors. A sampling of this subspace has to be made in order to reduce the high number of potential vectors and so to create a codebook. Some codebooks already exist, such as the Grassmannian Subspace Packing [START_REF] Love | Grassmannian beamforming for multiple-input multiple-output wireless systems[END_REF] that is optimally sampled. Initial setup is a random precoding vector and maximum power.

A. Gibbs Sampler

In the following, we describe the distributed algorithm.

• Each coordinator BS separately triggers a state transition for its user u, using a local random timer. This transition is based on the local energy E u . It selects a state with a probability which is proportional to exp(-E u (s ∈ S)/T ), where T is a parameter called the temperature and S refers to the finite set of allowable choices. A transition occurs by which the state of this user is updated iteratively. • The dynamics by the above state transitions will drive the network to a steady state which is the Gibbs distribution associated with the global energy E and temperature T , and has the following distribution:

π T (s, u ∈ U) = c • e -E(s)/T ,
with c a normalizing constant. • This distribution will put more mass on low energy (i.e., low cost) configurations. When T → 0 in a proper way (e.g., in logarithmic scale), the distribution π T (•) will converge to a Dirac mass at the optimal state of minimal cost if it is unique.

B. Information Exchange

To compute the probability distribution exp(-E u (s)/T ) for a Gibbs sampler, we need to evaluate E u (s) for each s ∈ S. Some measurements and information exchanges between neighbouring base stations and users are required. Following the explicit definition in (8), we consider that for evaluating the first term, a user u will estimate the following data and report to its coordinator BS:

• the receiver noise: N u ,

• the received interference: v =u P v l bv ,u |h bv ,u w v | 2 , that can be measured directly at the mobile, and • the pathloss l bu,u and link gain h bu,u . For evaluating the second term in [START_REF] Massoulié | Bandwidth sharing: objectives and algorithms[END_REF], all users v = u estimate the following information and report to their coordinator BS, which then shares the information to the coordinator BS of u via the back-haul (usually wired) network:

• the received signal power from its serving BS b v :

P v l bv ,v |h bv ,v w v | 2
, which is a scalar, and

• the pathloss l bu,v and link gain h bu,v . Note that the pathloss and link gains from a BS b to a user u can be obtained using pilots signals or by feeding back the received power to b: since b knows the transmit power used, it can deduce the actual link gain and pathloss.

C. Convergence

It is worth noting that the setting of temperature T in the algorithm will impact the limiting distribution of the system. There is a trade-off between the convergence time and strict optimality of the limiting distribution. For a fixed topology (i.e., base station, user population, signal attenuation), it is known [6, pp. 311-313] that if one decreases T properly for example in a logarithmic scale, the network will be guided into a state of minimal energy, regardless of the initial configuration. In this paper, we set T = T 0 / ln(1 + t), where t is time. Section IV will illustrate the convergence with numerical examples.

IV. SIMULATION AND NUMERICAL RESULTS

A performance investigation of the proposed solution is conducted below. We simulated a cellular network, composed of 61 cells (5-tiers), on the classical hexagonal grid layout. To avoid border effects, we only take the 19 center (tier 1, 2 and 3) cells into account to compute the system performance metrics. We focus on a given downlink RB. On this resource, each cell is serving a mobile, randomly located inside the cell. h b,u 's re complex circular Gaussian random variable vectors.

We consider that the channels are fixed during the simulation. This is not a strong assumption for pathloss and shadowing variation, since scheduling can be updated every 1 ms in LTE (if all required information have been exchanged); For the channel states h however, a practical implementation would have to take the channel coherence [START_REF] Huang | Limited feedback beamforming over temporally-correlated channels[END_REF] time into account to tune appropriately the optimization (i.e., cooling temperature, scheduling, feedback frequency, etc.) so that convergence and stability is ensured. This simplification is made to evaluate the approach at a first glance. Dynamic channel and algorithm adaptation will be a part of future work.

The system performance is evaluated in terms of:

• Spectral efficiency (bps/Hz) : S = u log 2 (1 + SINR u ),

• Global power efficiency (bps/Hz/W) : R = S/ u P u ,

• Fairness: using Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer systems[END_REF]. Fig. 1, Fig. 2 and Fig. 3 show the simulation results obtained for these three metrics, respectively and using λ = 0. The simulation parameters are provided in Table I. The presented results are averaged over 500 runs of the simulations with 1000 iterations each.

We propose here the comparison between the following methods:

• Optimization by Gibbs sampling, as detailed previously,

TABLE I SIMULATION PARAMETERS

• No precoding (i.e., ∀u, w bu,u = [1 1 1 1]/2), P u = P max , considered as a baseline, used when no CSI is known, to exploit transmit diversity. The Deterministic optimization can be seen as a simplification of the Gibbs sampling, by only focusing the allocation choice on the instantaneous and best local solution. When T → 0, a Gibbs sampler will act in a similar way. Note that for a large network with many minimum points, this greedy approach may only converge to a local minimum and consequently yields sub-optimal solution.

Simulation result shows that the system spectral efficiency (Fig. 1) and so the network throughput obtained performs inbetween those of the selfish SINR maximization and the baseline. On the other hand, the difference between the Gibbs (original) optimization and the deterministic (greedy) one is not significant.

At the same time, the total power consumed has dropped from 379.1 Watts (for Selfish and base-line methods) to 52.4 Watts and 64.6 Watts by the Gibbs and the greedy one, respectively. This is reflected in Fig. 2 by a substantial increase in power efficiency. The Gibbs optimization (the original one) outperforms all the other methods presented here.

Minimizing [START_REF]Next Generation Mobile Networks Group[END_REF], by definition, also improves the fairness among the users of the system (see Fig. 3). Recall that Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer systems[END_REF] is bounded by 0 and 1, where 1 means perfect equality. The result of Gibbs optimization shows that the cells manage to overcome high interference and do not allocate power in a selfish way. Fig. 3 shows that both the Gibbs and deterministic optimizations outperform the Selfish and baseline approaches.

It is observed that the convergence of the proposed algorithm, in the present network, appears in around one hundred iterations, starting from a random precoding vector and maximum power. Considering LTE scheduling update time, this convergence is fast enough to compensate shadowing variation.

In addition, we also show in Fig. 4 the impact of the power pricing λ in terms of spectral efficiency and power efficiency. There is a clear trade-off between the power efficiency and spectral efficiency. It is observed that the capacity increase is logarithmic with respect to the power consumption; the less power consumed the higher power efficiency is achieved. For instance, comparing the results when λ = 0 and λ = 10, the spectral efficiency drops by 48% while the power efficiency is increased by more than 10 times. (Note that the fairness index slightly decreases from 0.86 to 0.78 when λ increases from 0 to 10. Due to a lack of space, we do not include the figure here.) One can see that tuning λ is therefore a critical parameter that has to be chosen, in order to make power efficient cellular network deployments.

V. CONCLUSION

In this paper, we proposed a distributed algorithm that accomplishes the joint optimization of power allocation and transmit precoding vector, in order to improve the network spectral and power efficiency, as well as fairness among the users. Based on Gibbs sampler, the proposed solution is implementable in a distributed manner and nevertheless achieves global optimization of the proposed cost function. Its operation simplicity and automation is desirable for the objective of network self-optimization in LTE-like systems. Meanwhile, the power pricing allows to parametrize the system performance, balancing the spectrum and power efficiency, and so is the key to power efficient deployment.

ACKNOWLEDGEMENT

We would like to thank Franc ¸ois Baccelli (TREC, INRIA-ENS), Laurent Roullet (Alcatel-Lucent Bell Labs) and Vinod Kumar (Alcatel-Lucent Bell Labs) for their valuable discussions and great support to this work. This work has been

Fig. 1 .

 1 Fig. 1. Global spectral efficiency (bps/Hz)

Fig. 2 .

 2 Fig. 2. Global power efficiency (bps/Hz/W)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Fairness (Jain's index)

•

  Deterministic optimization: each user chooses the state that minimizes its local energy iteratively,• Selfish SINR u maximization: ∀u, w bu,u = h H bu,u and P u = P max ,

	Parameter	Value
	Number of antennas Nt	4
	Initial temperature T 0	0.01
	Inter-site distance	1000 meters
	Noise power (inc. noise figure) Nu	-95 dBm
	Pathloss (dB) [12], d in meter	-15.3 -37.6 log 10 (d)
	Shadowing standard dev.	8 dB
	Neighbor threshold θ	Nu -3dB
	Precoding codebook	[9], 16 vectors
	Power set (P min , Pmax, step)	(-19dBm, 43dBm, 2dB)


Giang Truong
email: le-truong.giang@isep.fr

Olivier Le

Matthieu Hermant
email: matthieu.manceny@isep.fr

Renaud Manceny

Pawlak

Dynamic Adaptation through Event Reconfiguration

Keywords: Adaptive systems, rule-based programming, event-based programming, reconfiguration

We introduce a new programming language called INI, which eases the development of self-adaptive software. INI combines both rulebased and event-based programming paradigms, by allowing the definitions of rules that can be triggered by events. Besides a convenient language-level support for synchronization, the key point with INI events is that they come with a configuration layer, which is set up through input parameters passed to the events when created. Additionally, events can be stopped, reconfigured, and restarted at runtime by the program itself. Ultimately, this re-configuration can be triggered by other events, thus allowing the program to adapt to new operational environments.

Introduction

The role of software in our society has become more and more important and to satisfy higher demands from customers, software systems must become more "versatile, flexible, resilient, dependable, robust, energy-efficient, recoverable, customizable, configurable, and self-optimizing" [START_REF]Software Engineering for Self-Adaptive Systems[END_REF]. However, developing and maintaining software systems is hard and resource-consuming because they are operating in an environment that is not well defined or predictable. Consequently, software systems need a new and innovative approach for evolving and running. Currently, one of the most promising approaches to achieve such properties is building self-adaptation and self-management mechanisms [START_REF] Müller | Towards self-adaptive software-intensive systems[END_REF].

In recent years, with the development of autonomic computing, software engineering researchers have been motivated to pay more attention to design and develop self-adaptive software systems. Basically, adaptive software comes with the assumption of dynamic environment while non-adaptive software does not [START_REF] Yoo | An adaptive software framework based on service composition[END_REF]. By using rules explicitly or implicitly, most self-adaptive software can choose reactions to monitored events happening during execution [START_REF] Wang | Towards a rule model for self-adaptive software[END_REF]. Therefore, one of the current research trends is to develop a programming language to easily R. Meersman, T. Dillon, and P. Herrero (Eds.): OTM 2011 Workshops, LNCS 7046, pp. 637-646, 2011. c Springer-Verlag Berlin Heidelberg 2011 express and capture those changes so that the systems can modify their behavior at runtime. In this paper, we introduce a new programming language called INI, which we designed to assess rule-based and event-based oriented programming. In INI, we allow programmers to define events, which need to be captured and monitored. Events are usually executed asynchronously but can synchronize on other events with intuitive language constructs. Moreover, events can be reconfigured at runtime through a well-defined reconfiguration mechanism. As a result, when something happens during execution, INI program can capture and adapt to these changes automatically by reconfiguring its events.

The rest of this paper is organized as follows. In Section 2, we give an overview of related work. In Section 3, we discuss events in INI, including its syntax, builtin events and user-defined events. Events synchronization and reconfiguration are shown in Section 4. In that section, we also demonstrate the capabilities of INI in handling variabilities in the operational environment with a small example. Finally, some conclusions and future work are presented in Section 5.

Related Work

A general overview of research and problems on self-adaptive software can be found in [START_REF] Laddaga | Self adaptive software problems and projects[END_REF][START_REF] Salehie | Self-adaptive software: Landscape and research challenges[END_REF]. The key aspect of self-adaptive software is that code behavior is evaluated or tested at runtime, which may lead to a run-time change in behavior [START_REF] Laddaga | Self adaptive software problems and projects[END_REF]. As a result, the run-time code should contain the following mechanisms:

-A mechanism to detect changes during execution -A mechanism to switch algorithms and operations due to these above changes Laddaga [START_REF] Laddaga | Self adaptive software problems and projects[END_REF] discussed two useful paradigms for utilizing self-adaptive software. One of these is the planning paradigm, and the other is the control paradigm. In [START_REF] Wang | Towards a rule model for self-adaptive software[END_REF], Wang proposed a Rule Model for self-adaptive software, which includes three key concepts (event, parameter, and rule). In Wang's paper, rules were used to adjust software's behavior at runtime. Psaier et al. [START_REF] Psaier | A programming model for self-adaptive open enterprise systems[END_REF] presented a middleware for programming and adapting complex service-oriented systems. Their approach was based on monitoring and real-time intervention to regulate interactions based on behavior policies.

Cheng et al. [START_REF] Cheng | Architecture-based self-adaptation in the presence of multiple objectives[END_REF] introduced a new language of adaptation, which ultimate aim is to automate human tasks in system management to achieve high-level stakeholder objectives. They claimed that such a language is "expressive enough to describe human expertise and comes with the flexibility and robustness to capture complex and potentially dynamic preferences".

In our work, we develop INI by combining both rule-based and event-based programming styles. INI takes inspirations from existing rule-based languages [START_REF] Cirstea | TomML: A Rule Language for Structured Data[END_REF], and event-based programming similarly to the work above. With rule-based programming, an action is executed only if its guard is evaluated to true in the context of the function. With event-based programming, we allow programmers to write their own events to capture and monitor changes happening during execution. Moreover, we fully support events synchronization and reconfiguration. Although several event-based programming languages have been proposed so far [START_REF] Fischer | Tasks: language support for event-driven programming[END_REF][START_REF] Kamina | Eventcj: a context-oriented programming language with declarative event-based context transition[END_REF], their support for writing self-adaptive software are limited. To our knowledge, no languages support event reconfiguration at runtime. The key feature of INI compared to all the languages we have studied is that events are dynamically reconfigurable. This feature allows INI programs to automatically reconfigure themselves to adapt to changes in the environment.

Programming with INI

The interpreter of INI is currently implemented in Java and runs on a JVM, but INI's syntax and semantics are not Java's ones. Each INI program contains functions, in which the starting point is the function main. All functions are written with rules in combination with event expressions. Each rule is defined explicitly with a guard and an action. The guard triggers the evaluation of the action when evaluated to true in the context of the function. Along with rules, programmers can use events in INI to capture changes when their programs are running. In this paper, we focus on event-triggered rules since we use them as the main mechanism for self-adaptation.

Events in INI

Built-in event kind

Meaning @init()

The @init event is invoked when the function starts evaluating. @end() On the contrary to the @init event, the @end event is triggered when no more event can be applied and when the function is about to return. @every[time:Integer]() The @every event occurs periodically as specified by its input parameter (in milliseconds).

@update[variable:T]

The @update event is invoked when a specific (oldValue:T,newValue:T) variable is changed during execution.

An event is defined as something happening during the execution of the program, which should be monitored and handled. Events in INI can be understood at three different levels: the event kind corresponds to the class/type of the event; the event instance (event for short) corresponds to the definition of an eventtriggered rule in the INI program; the event thread corresponds to the execution of an event instance. By convention, event kinds start with @ and can take input and output parameters. Input parameters can be understood as configuration parameters to tune the event execution. Output parameters are passed to the action. These parameters may be optional. Syntactically, each event (instance) is written as below. Optionally, an event can also be bound to an id, so that other parts of the program can refer to it. To allow programmers to write code more easily and conveniently, INI comes with some common built-in event kinds such as @init, @end, @every, @update. The meanings of these events are given in Table 1. For example, the following code creates an @every instance called e, which increments v every second. The @update instance u triggers the action (event handler) that prints out the v variable value when it changes, i.e. every second.

e: @every [ time =1000]() { v = v + 1 } u: @update [ variable =v ]( oldv , newv ) { println ("v=" + newv ) }
Beyond built-in events, we also allow programmers to write their own event kinds in Java or in C and integrate them into an INI program as explained in the next section.

Example

In this section, we discuss a sample INI program, written in an event-driven style. In our example, we use a video camera to detect the movement of a ball, get its positions in space periodically, and save them into a CSV file.

To do so, we first need to define a new event kind to detect the ball and send its position to the program when detected. Our event has one input parameter called frequency. This parameter is applied to set how long the event should sleep between two image detections (time unit is in milliseconds). Besides, we have three output parameters (r,x,y), which are the radius and coordinates of the detected ball in the captured image. In Java, we need to subclass the ini.event.Event class to define the behavior of our new event kind as shown in the code below. In the BallDetection class, the method eval will be upcalled by the INI evaluator when the program uses our event. It creates a thread that sleeps accordingly to the event configuration (line 10), detects the ball using the OpenCV library (line 13) [START_REF] Garage | OpenCV[END_REF] and write the results in output parameters to be passed to the INI program (lines 15-17). The event-triggered action, also called event thread, is executed at line 19 using the execute method provided by the API, which by default runs asynchronously. Finally, the method terminate is overridden to stop the event: INI upcalls this method when the program exits or forces the event to shutdown. To understand more about built-in events in INI and how to write user-defined events, interested readers may refer to INI Language Reference Documentation [START_REF] Pawlak | INI Online[END_REF].

1 import " lib_io . ini " 2 @ballDetection [ frequency : Integer ]( Float , Integer , Integer ) In Figure 1, we write the actual INI program, which binds our Java userdefined to the @ballDetection event kind (lines 2-3). In the @init event, we define a variable f, which indicates the CSV file we want to store data in after collecting the ball positions over time. In INI, all variables are global within the function where they are defined. This means that f can be accessed anywhere in the function main. In our program, the @ballDetection event is triggered periodically, i.e. each millisecond. If a ball is detected, we check whether the CSV file exists or not (line 9). If the file does not exist, we create a new one and write the header. Finally, we write the data to the file (line 15), including the time when the ball was detected and its position.

Events Synchronization and Reconfiguration

The event reconfiguration mechanism is developed in INI so that we can modify the input parameters (configuration) of the event-triggered rules at runtime. For example, an event can be notified for a change in the environment and decide to reconfigure another event to adapt the program to the new environment. However, to achieve safe reconfiguration, synchronization among events is also essential. In this section, we first explain event synchronization, and then discuss event reconfiguration, which we illustrate using our ball-detection example.

Events Synchronization

Except for the @init and @end events, most INI events are executed asynchronously by default. From an implementation perspective, it means that each event handler runs in its own thread, potentially simultaneously to other events. In many cases, a given event e0 may want to synchronize to other events e1, ..., eN, which means that the synchronizing event e0 must wait for all the target event threads to be terminated before running. For instance, it can be used to ensure that a shared variable accessed both for reading and writing has a consistent state, or also to ensure that all event threads have terminated before reconfiguring the associated event-triggered rule. Thus, INI provides a specific language construct: the symbol $ along with the list of identifiers of target events with which we want to synchronize. For example, the following code ensures that the above discussed event e0 synchronizes N target events. $(e1 ,e2 ,... , eN ) e0 : @eventKind [...](...) { < action > } Note that one of the target events can also be synchronized with e0. Crosssynchronization of events means that their executions are mutually exclusive. We now precisely define the semantics of synchronization in INI.

To implement synchronization in INI, we use one lock and one count variable associated with each event. The lock is an instance of java.util.concurrent. locks.ReentrantLock and is used to avoid concurrent execution when required. We use the functions lock (blocking), tryLock (non-blocking and returns true of false depending on whether the locking was successful or not), and unlock. For more details, refer to the Java document of the methods of the same names in the ReentrantLock class [START_REF]Oracle: Java SE 6 Documentation[END_REF]. The count variable holds the number of threads currently executing for the associated event. We use the following notation: for an event e i , we call l i its associated lock and count i its associated thread counting variable.

Let (e 1 , e 2 , ..., e N ) be the list of target events with which e 0 synchronizes. To execute the event e 0 in INI, we apply Algorithm 1, which also applies to any event execution in the INI system. We can see that the execution of events Algorithm 1 Our algorithm to execute e 0 synchronized with (e 1 , e 2 , ...e n ) 1: repeat 2:

allLocked := true 3: lock(l0) 4:

for i := 1 to N step 1 do 5:

if ¬ tryLock(li) then 6:

allLocked := false 7:

for i := 1 to i - wait-until counti = 0 18: end for 19: count0 := count0 + 1 20: for i := 1 to N step 1 do 21: unlock(li) 22: end for 23: unlock(l0) 24: eval(e0) 25: count0 := count0 -1 includes four steps. First, e 0 locks its own lock and tries to lock all target events (lines 1-15). When all events are locked, the event e 0 needs to wait until all other events are terminated (lines 16-18). The wait-until mechanism in our algorithm is currently implemented with Java monitors and thread notification. Next, the number of threads executing for event e 0 is incremented and locks for all events are released (lines 19-23). Finally, the event can be actually evaluated and when it is terminated, the number of running threads for it is decremented (lines 24-25).

1

Example Using Synchronization

Let us take again our example shown in Figure 1. Assuming that after we collect data about positions of a ball in space, we need to upload the CSV file to an FTP server. To do this, we create a new @every event as shown in Figure 2. Inside this event, first, we compress data and then upload the compressed file. Since we collect data periodically, we use a timestamp (line 4) to distinguish data at different time. By default, the two events @ballDetection and @every will be executed asynchronously. However, it is essential that when we collect data (@ballDetection), the uploading process (@every) should not happen and vice versa. In other words, these two events need to be mutually exclusive. To ensure this, the programmer needs to modify the program at lines 7 of Figure 1 and 3 of Figure 2 by naming the two events and use their identifiers to cross-synchronize them, as it is shown in the following code:

$(e) b: @ballDetection [ frequency = 1]( r ,x ,y) { ... $(b) e: @every [ time = 5000](){ ...

Event Reconfiguration

In this section, we will demonstrate the capabilities of INI in handling changes happening in the environment though the event-reconfiguration mechanism. Event reconfiguration consists of changing the values of the eventtriggered rule input parameters. Programmers can call the built-in function reconfigure(eventId, [inputParam1=value1, inputParam2=value2,...]) to reconfigure their events. Moreover, we also allow programmers to stop and restart events with the built-in functions stop event(eventId) and restart event(eventId). Typically, it is required to stop an event before reconfiguring it.

Let us now consider that our ball-detection example of Section 3 runs in an embedded environment where the power is supplied by a battery. One way to take into account this new constraint is to adapt the data-collection frequency to the power level. First, we add a new user-defined event kind called @powerAlarm, which notifies the program each time the power level passes a given threshold both ways, when charging or discharging. This event has one input parameter named threshold, and one output parameter named currentLevel, which tells us if the level is currently lower or greater than the threshold. When the program below is running, if it detects that the power-level is lower than 50% (configured line 1), it stops the event b:@ballDetection (line 4), then changes the value of its input parameter (i.e., frequency) to 1000 (line 5), and finally restarts it (line 6). Conversely, if the power goes over the threshold the value for the parameter frequency is set again to 1 (lines 8 -10). The event @powerAlarm is synchronized with events b:@ballDetection and e:@every as specified by $(b,e) at line 1 in order to avoid unfinished detection or upload jobs to be stopped. Finally in the following code, we show how to add a second @powerAlarm instance that stops all other events when the threshold goes below 10%.

Conclusion and Future Work

In this paper, we introduce a new language called INI, which can be used to write self-adaptive software through events synchronization and reconfiguration mechanisms. Programs written in INI may dynamically change their behavior or improve their operation depending on dynamic operational conditions of the environment. With the example that we used along the paper to demonstrate the capabilities of INI, we can see that using INI to write new event-driven rules does not require too much effort. The programmers can capture the changes during execution by writing their own user-defined events and then define suitable actions for them. The changes necessary to take into account new constraints can thus be localized and encapsulated within some rules, which implies code maintainability and robustness with regard to changes.

For future work, we will improve INI so that it can handle changes in environment more efficiently. For example, as stated in [START_REF] Cheng | Architecture-based self-adaptation in the presence of multiple objectives[END_REF], we need a mechanism to handle failure during adaptation execution. If a failure happens when our systems try to adapt to the environment, it is essential to recover from that failure. Besides, we will define formal semantics for validating and verifying useful

  id : @eventKind [ inputParam1 = value1 , inputParam2 = value2 , ...] ( outputParam1 , outputParam2 , ...) { <action > }

1 2 Thread ballDetectionThread ; 3 @ 4 ( 5 @ 9 /

 23459 public class BallDetection extends ini . event . Event { Override public void eval ( final IniEval eval ) { ballDetectionThread = new Thread () { Override public void run () { 6 / Sleep as long as the configuration indicates 10 sleep ( getInContext (). get (" frequency ") 11 . getNumber (). longValue ()); 12 // Use OpenCV to detect the ball 13 ...

14 //@

 14 Write data to output parameters 15 variables . put ( outParameters . get (0) , r ); 16 variables . put ( outParameters . get (1) , x ); 17 variables . put ( outParameters . get (2) , y ); Override public void terminate () {...} 26 }

3 => 5 @ 6 / 7 @Fig. 1 .

 35671 Fig. 1. A sample INI program with event-driven style

2 // 9 }Fig. 2 .

 292 Fig. 2. An event used to upload collected data

2 // 3 $

 23 Adapt the ball detection frequency at the 50% threshold (b ,e) p: @powerAlarm [ threshold = 0.5]( currentLevel ) {

1 $ 5 } 6 }

 156 (b ,e ) @powerAlarm [ threshold = 0.1]( currentLevel ) { 2 case { 3 currentLevel < threshold { stop_events ([b , e , p ]) } 4 default { restart_events ([b , e , p ]) }

Table 1 .

 1 Some built-in events in INI

properties of INI programs and prove the soundness of its type system. Finally, we also have a plan to perform more case studies to evaluate the capabilities of INI.