Maik Miguel Prudêncio

Joerg Lehmann

Dr Maik J Lehmann
email: maik.lehmann@med.uni-heidelberg.de

Illuminating the host -how RNAi screens shed light on host-pathogen interactions

Keywords: RNA interference, host-pathogen interactions, high-throughput screening, siRNA High-throughput screening / Host-pathogen interactions / RNA interference ER, endoplasmic reticulum, HCV, hepatitis C virus, HIV, human immunodeficiency virus, mRNA, messenger RNA, RNAi, RNA interference, siRNA, small interfering RNA, VSV-G, vesicular stomatitis virus G-protein, RNA interference, hostpathogen interactions, RNAi, RNA interference, mRNA, messenger RNA, HIV, Human Immunodeficiency Virus, VSV-G, Vesicular Stomatitis Virus G-protein, SV40, Simian Virus 40, PTGS, Posttranscriptional Gene Silencing, siRNA, small interfering RNA, dsRNA, double stranded RNA, WNV, West Nile Fever Virus

WNV, West Nile virus

Over millions of years pathogens have coevolved with their respective hosts utilizing host cell functions for survival and replication. Despite remarkable progress in developing antibiotics and vaccination strategies in the last century, infectious diseases still remain a severe threat to human health. Meanwhile, genomic research offers a new era of data-generating platforms that will dramatically enhance our knowledge of pathogens and the diseases they cause. Improvements in gene knockdown studies by RNA interference (RNAi) combined with recent developments in instrumentation and image analysis enable the use of high-

Introduction

Pathogen infections represent a major health risk causing millions of deaths each year. By exploiting host cellular machineries, pathogens have evolved to master successful host cell infection and cell-to-cell spread. Most of the host cell proteins utilized by pathogens, however, have not been identified yet. After sequencing the human genome [START_REF]International Human Genome Sequencing Consortium, Finishing the euchromatic sequence of the human genome[END_REF] a new era in investigating biological processes and gene regulations has begun, enabling the elucidation of cellular gene functions involved in pathogen infections. RNA interference (RNAi) has been widely used to study lossof-function phenotypes by specifically down-modulating gene expression. RNAi was first described in plants as post-transcriptional gene silencing [START_REF] Jorgensen | Altered gene expression in plants due to trans interactions between homologous genes[END_REF], but also observed in fungi and worms [START_REF] Fagard | AGO1, QDE-2, and RDE-1 are related proteins required for post-transcriptional gene silencing in plants, quelling in fungi, and RNA interference in animals[END_REF][START_REF] Romano | Quelling: Transient inactivation of gene expression in Neurospora crassa by transformation with homologous sequences[END_REF] and later identified in animal cells in trypanosomes [START_REF] Ngo | Double-stranded RNA induces mRNA degradation in Trypanosoma brucei[END_REF] and in the nematode Caenorhabditis elegans [START_REF] Fire | Potent and specific genetic interference by double-stranded RNA in Caenorhabditis elegans[END_REF], when the introduction of long doublestranded RNA (dsRNA) led to the degradation of homologous mRNA. Further interest in RNAi was raised by the observation that gene silencing also occurred in mammalian cells [START_REF] Elbashir | Duplexes of 21nucleotide RNAs mediate RNA interference in cultured mammalian cells[END_REF]. RNAi has been identified as an evolutionarily conserved process in which long dsRNAs are cleaved into short RNA duplexes of [START_REF] Shakibaei | Dual interaction of the malaria circumsporozoite protein with the low density lipoprotein receptor-related protein (LRP) and heparan sulfate proteoglycans[END_REF][START_REF] Sinnis | Remnant lipoproteins inhibit malaria sporozoite invasion of hepatocytes[END_REF][START_REF] Manning | The protein kinase complement of the human genome[END_REF] nucleotides in length, termed small interfering RNAs (siRNAs), a process mediated 3 by the RNase III-like enzyme Dicer. Processed siRNAs are directed to the RNAinduced silencing complex (RISC) where one strand of the siRNA serves as a guide sequence for the recognition of the homologous target mRNA, resulting in mRNA cleavage (for further information see [START_REF] Dykxhoorn | The silent revolution: RNA interference as basic biology, research tool, and therapeutic[END_REF]). The observation that RNAi can be initiated by the introduction of chemically synthesized siRNAs revolutionized biomedical research and therapy. In recent years researchers started to investigate the regulation of gene expression using siRNAs and explored the potential therapeutic use of RNAi.

For a systematic analysis of gene functions in cells at a genome-wide scale, platforms for high-throughput screening approaches had to be developed. So far, several genome-wide siRNA-based screens have been performed, but only a few studies investigating gene functions during pathogen infections are known to date.

RNAi screens to identify host genes involved in parasitic infections

So far, reports on the use of RNAi to identify host factors that influence parasitic infections are restricted to a small number of studies, in which specific groups of genes were targeted. These focused on infection by Plasmodium, the causative agent of malaria, a parasite whose complex life cycle involves two obligate hosts: the invertebrate host and the vertebrate host (reviewed in [START_REF] Prudencio | The silent path to thousands of merozoites: The Plasmodium liver stage[END_REF][START_REF] Silvie | Interactions of the malaria parasite and its mammalian host[END_REF]).

The invertebrate host

Female Anopheles mosquitoes are the vectors of malaria transmission and Plasmodium's invertebrate host, where the sexual replication of the parasite occurs.

Although no large-scale RNAi screens of Anopheles have been reported, a number of RNAi-based studies aimed at identifying factors from this host that are important Anopheles mosquitoes was first reported by Blandin et al. [11]. This technique was employed to evaluate the role of the anti-microbial peptide defensin in the antibacterial and anti-parasitic responses in A. gambiae. Later on it was successfully applied to identify factors that regulate development of the rodent malaria parasite P. berghei in the mosquito host. RNAi depletion of a complement-like thioestercontaining protein, TEP1, and a leucine-rich repeat protein, LRIM1, significantly increased the number of developing oocysts even in fully susceptible mosquitoes, whereas knockdown of two genes encoding C-type lectins induced strong melanization response to P. berghei [START_REF] Blandin | Complement-like protein TEP1 is a determinant of vectorial capacity in the malaria vector Anopheles gambiae[END_REF][START_REF] Osta | Effects of mosquito genes on Plasmodium development[END_REF]. Melanization is a unique immune response system in Arthropods that involves the production and deposition of melanin pigments on invading pathogens and parasites [START_REF] Christensen | Melanization immune responses in mosquito vectors[END_REF]. dsRNA-mediated gene silencing was later used to assess the roles of a selected set of 21 genes belonging to the CLIPA and CLIPB subfamilies of genes encoding serine proteases, potentially involved in innate immunity, in the melanization of P. berghei ookinetes [START_REF] Volz | A genetic module regulates the melanization response of Anopheles to Plasmodium[END_REF]. The authors showed that, whereas most CLIPBs promote melanization, several CLIPAs seem to play contrasting roles in this process. More recently, Brandt et al. [START_REF] Brandt | Use of a Drosophila model to identify genes regulating Plasmodium growth in the mosquito[END_REF] used Drosophila as a surrogate mosquito to identify host factors required for the growth of the avian malaria parasite P. gallinaceum. Five A. gambiae homologs of the 18 D. melanogaster loss-of-function mutants showing impaired parasite growth were then targeted by injection of appropriate dsRNA molecules. Subsequent assessment of P. berghei growth in A. gambiae mosquitoes showed that knockdown of the expression of four of these five genes led to altered parasite growth phenotypes. It should, however, be noted that while knockdown of two of these genes led to a decrease in parasite load in the mosquito, that of the other two had the opposite effect. Nevertheless, these studies highlight the potential of RNAi to identify and define the roles of genes from mosquito vectors of infection, which may constitute valid intervention targets against the spread of disease. Importantly, injection of dsRNA into A. gambiae mosquitoes has also been employed to compare the mosquito's melanization response to P. falciparum, the deadliest of all human malaria parasite species, to the one mounted against the rodent parasite P. berghei [START_REF] Dong | Anopheles gambiae immune responses to human and rodent Plasmodium parasite species[END_REF][START_REF] Michel | Increased melanizing activity in Anopheles gambiae does not affect development of Plasmodium falciparum[END_REF]. These studies suggested that both universal and Plasmodium species-specific responses occur in the mosquito [START_REF] Dong | Anopheles gambiae immune responses to human and rodent Plasmodium parasite species[END_REF], and that the human malaria parasite may have evolved specific immune evasion strategies [START_REF] Michel | Increased melanizing activity in Anopheles gambiae does not affect development of Plasmodium falciparum[END_REF].

The relatively small number of RNAi-targeted genes in these studies reveals the difficulties of employing this in vivo RNAi strategy to large numbers of target genes.

In this context, an informed pre-selection of the genes to be assessed by RNAi, either through bioinformatics- [START_REF] Volz | A genetic module regulates the melanization response of Anopheles to Plasmodium[END_REF] or microarray-based analysis [START_REF] Dong | Anopheles gambiae immune responses to human and rodent Plasmodium parasite species[END_REF] or by carrying out a previous forward genetic screen [START_REF] Brandt | Use of a Drosophila model to identify genes regulating Plasmodium growth in the mosquito[END_REF] should be considered.

The vertebrate host

Following injection into their mammalian host, Plasmodium parasites undergo an outstanding asexual replication phase inside liver cells, which results in the release of newly formed parasites into the blood stream, where they infect erythrocytes and cause the symptoms of disease. Given their anucleated nature, red blood cells are not easily amenable to RNAi studies. However, in vitro RNAi was recently used for the first time to identify vertebrate host factors that influence Plasmodium infection of liver cells [START_REF] Rodrigues | Host scavenger receptor SR-BI plays a dual role in the establishment of malaria parasite liver infection[END_REF][START_REF] Prudencio | Kinome-wide RNAi screen implicates at least 5 host hepatocyte kinases in Plasmodium sporozoite infection[END_REF]. Both these studies employed siRNAs to modulate gene expression levels and used high-content, high-throughput fluorescence microscopy to assess the effect of gene knockdown on infection of the human hepatoma cell line, Huh7, by P. berghei parasites (Fig. 1). These medium-to-large-scale RNAi screens focused on two groups of genes whose implication on infection was previously suggested or was likely in view of available data. In Rodrigues et al. [START_REF] Rodrigues | Host scavenger receptor SR-BI plays a dual role in the establishment of malaria parasite liver infection[END_REF], the authors followed up a reported link between hepatocyte invasion by Plasmodium and apolipoprotein clearance in the liver [START_REF] Shakibaei | Dual interaction of the malaria circumsporozoite protein with the low density lipoprotein receptor-related protein (LRP) and heparan sulfate proteoglycans[END_REF][START_REF] Sinnis | Remnant lipoproteins inhibit malaria sporozoite invasion of hepatocytes[END_REF] and used RNAi to establish whether or not this reflected the involvement of a host lipoprotein receptor in the infection process. A total of 53 genes expressed in the liver and annotated as having validated or putative roles in lipoprotein assembly, binding, or uptake were targeted, from which the scavenger receptor class B type I (SRBI) emerged as the strongest modulator of infection. In the same report, the authors show evidence that SRBI is not only implicated in the invasion of host cells by the parasite, but also in the latter's intracellular development process that follows. The establishment of the importance of SRBI during infection confirms the validity and relevance of the RNAi approach used. Prudêncio et al. [START_REF] Prudencio | Kinome-wide RNAi screen implicates at least 5 host hepatocyte kinases in Plasmodium sporozoite infection[END_REF] took an unbiased approach to investigate the role of host signaling pathways during infection by Plasmodium. RNAi was used to selectively silence the expression of 727 genes encoding proteins with known or putative kinase activity, as well as kinase-interacting proteins, thereby covering the entire annotated kinome [START_REF] Manning | The protein kinase complement of the human genome[END_REF]. This three-step screen employed increasingly stringent selection criteria, and resulted in a list of five "hits" whose influence on infection was consistently observed. One of the genes identified, MET, is, in fact, the first host signaling molecule to have previously been implicated in Plasmodium liver infection [START_REF] Carrolo | Hepatocyte growth factor and its receptor are required for malaria infection[END_REF][START_REF] Leiriao | HGF/MET signalling protects Plasmodium-infected host cells from apoptosis[END_REF]. One other protein identified in this screen, the atypical PKCζ, was shown by the authors to influence the early stages of Plasmodium infection of hepatocytes, once again lending support to the RNAi-based strategy employed to assess the role of an informed selection of genes on malaria liver infection [START_REF] Prudencio | Kinome-wide RNAi screen implicates at least 5 host hepatocyte kinases in Plasmodium sporozoite infection[END_REF]. Importantly, both these reports made use of a novel method to silence genes in the living animal by employing siRNA molecules formulated in liposomal nanoparticles to confirm the relevance of selected target genes in the context of infection of a rodent model of malaria [START_REF] Rodrigues | Host scavenger receptor SR-BI plays a dual role in the establishment of malaria parasite liver infection[END_REF][START_REF] Prudencio | Kinome-wide RNAi screen implicates at least 5 host hepatocyte kinases in Plasmodium sporozoite infection[END_REF]. This novel class of lipid-like delivery molecules, termed lipidoids, can be formulated with siRNAs to facilitate high levels of specific silencing of endogenous gene transcripts in mice, rats and nonhuman primates [START_REF] Akinc | A combinatorial library of lipid-like materials for delivery of RNAi therapeutics[END_REF]. Mammalian in vivo RNAi thus emerges as a tool of outstanding potential to evaluate the importance of carefully selected genes in a physiological context of malaria infection.

((Fig. 1))

The process of liver cell infection by Plasmodium comprises two consecutive steps: invasion of the cells by the parasites and intracellular development of the latter [START_REF] Silvie | Interactions of the malaria parasite and its mammalian host[END_REF].

Since the screening approach outlined in Fig. 1 contains information not only about parasite number but also about their size, cell invasion and parasite development can be independently assessed for each of the conditions tested with this setup.

Moreover, in addition to allowing the normalization of infection levels, actin and nuclei staining of the host cells provide information about whether the RNAi treatment affected cell proliferation/morphology [START_REF] Rodrigues | Host scavenger receptor SR-BI plays a dual role in the establishment of malaria parasite liver infection[END_REF][START_REF] Prudencio | Kinome-wide RNAi screen implicates at least 5 host hepatocyte kinases in Plasmodium sporozoite infection[END_REF]. High-content image-based RNAi screening thus constitutes a powerful technique to identify and study mammalian host factors that play a role during hepatocyte infection by Plasmodium.

Nevertheless, other approaches may be envisaged to assess infection following RNAi-mediated knockdown of gene expression, such as flow cytometry-based assays [27]. In the case of malaria hepatic infection, flow cytometry presents the advantage that it allows the specific monitoring of the early events of cell invasion by the parasite by analyzing cells at early time points after infection, which cannot be achieved by a high-throughput, automated analysis of image data. However, unlike microscopy, flow cytometry depends on the availability of a transgenic fluorescent pathogen, which may, in some cases, constitute a limitation. Finally, the desired readout content should also be taken into consideration. Through a selection of appropriate stainings, flow cytometry may provide simultaneous data about various cellular features. However, if information about cellular or sub-cellular morphology is required this may be better achieved by an image-based approach.

RNAi screens to identify host factors involved in bacterial infections

Bacterial infections have been the focus of a significant number of RNAi-based screens targeting host genes (Table 1). The amenability of Drosophila cells to RNAi [START_REF] Clemens | Use of double-stranded RNA interference in Drosophila cell lines to dissect signal transduction pathways[END_REF][START_REF] Boutros | Genome-wide RNAi analysis of growth and viability in Drosophila cells[END_REF] has made them important tools in several large-scale screens to identify host factors that influence bacterial pathogenesis. D. melanogaster macrophage-like Schneider 2 (S2 or SL2) cells were used for RNAi screening for the first time in a flow cytometry-based study that employed 1000 random dsRNAs. The authors identified 34 Drosophila gene products involved in phagocytosis of FITC-labeled Escherichia coli and Staphylococcus aureus [START_REF] Ramet | Functional genomic analysis of phagocytosis and identification of a Drosophila receptor for E. coli[END_REF]. Besides proteins that participate in, among other processes, vesicle transport and actin cytoskeleton regulation, a cell surface receptor, the peptidoglycan recognition protein LC (PGRP-LC), was shown to be involved in phagocytosis of Gram-negative but not Gram-positive bacteria [START_REF] Ramet | Functional genomic analysis of phagocytosis and identification of a Drosophila receptor for E. coli[END_REF].

Later, two seminal image-based screens took a genome-wide RNAi approach to study infection of Drosophila cells by GFP-expressing bacteria of the obligatory intracellular species Listeria monocytogenes [START_REF] Agaisse | Genome-wide RNAi screen for host factors required for intracellular bacterial infection[END_REF] and Mycobacterium fortuitum [START_REF] Philips | Drosophila RNAi screen reveals CD36 family member required for mycobacterial infection[END_REF].

In both of these reports approximately 21 300 dsRNAs targeting >95% of the annotated Drosophila genome were used, and the resulting infection phenotypes screened 7216 genes to identify host pathways that control compartmentalization of L. monocytogenes [START_REF] Cheng | Use of RNA interference in Drosophila S2 cells to identify host pathways controlling compartmentalization of an intracellular pathogen[END_REF]. These studies identified a large number of Drosophila genes whose knockdown had an effect on bacterial infection. Their corresponding gene products span a wide array of cellular functions, including vesicular trafficking, cytoskeletal organization and lipid metabolism. Whereas several of the host factors identified, such as Rab5 (Fig. 2), were shown to influence infection by both L. monocytogenes and M. fortuitum, some dsRNAs decreased infection of only one of the two pathogens [START_REF] Agaisse | Genome-wide RNAi screen for host factors required for intracellular bacterial infection[END_REF]. Interestingly, Philips et al. [START_REF] Philips | Drosophila RNAi screen reveals CD36 family member required for mycobacterial infection[END_REF] showed that uptake of not only M. fortuitum but also of E. coli and S. aureus is strongly influenced by SR-BI, a molecule that has also been implicated in infection by hepatitis C virus (HCV) [START_REF] Scarselli | The human scavenger receptor class B type I is a novel candidate receptor for the hepatitis C virus[END_REF],

as well as other bacteria like Salmonella typhimurium and L. monocytogenes [START_REF] Vishnyakova | CLA-1 and its splicing variant CLA-2 mediate bacterial adhesion and cytosolic bacterial invasion in mammalian cells[END_REF],

and Plasmodium parasites [START_REF] Rodrigues | Host scavenger receptor SR-BI plays a dual role in the establishment of malaria parasite liver infection[END_REF].

((Table 1))((Fig. 2)) Bacterial pathogens often replicate inside an intracellular vacuolar compartment, whose formation involves recruitment and trafficking of membrane material between the endoplasmic reticulum (ER) and Golgi. The maturation of such a replicative compartment with ER-like properties is known to involve the bacterial Type 4 secretion system and fusion with membranes that contain ER-resident proteins, but it is thought that bacteria also exploit host pathways for intracellular replication [START_REF] Celli | Brucella evades macrophage killing via VirB-dependent sustained interactions with the endoplasmic reticulum[END_REF][START_REF] Chen | Legionella effectors that promote nonlytic release from protozoa[END_REF]. However, the molecular mechanisms employed by bacteria to secure this replicative niche remain poorly understood. Two recent RNAi screens specifically addressed this issue by knocking down the expression of genes involved in secretory pathways, endocytic transport and ER-associated processes and monitoring the subsequent outcome of infection by Legionella pneumophila [START_REF] Dorer | RNA interference analysis of Legionella in Drosophila cells: Exploitation of early secretory apparatus dynamics[END_REF] and Brucella spp. bacterium is fed by distinct pathways of the secretory system. The observation that combinations of knockdowns of various ER-Golgi transport proteins were necessary to impair L. pneumophila replication is in agreement with the notion that multiple and redundant host secretory pathways may be exploited during infection by this pathogen [START_REF] Chen | Legionella effectors that promote nonlytic release from protozoa[END_REF][START_REF] Luo | Multiple substrates of the Legionella pneumophila Dot/Icm system identified by interbacterial protein transfer[END_REF]. In contrast, the single down-modulation of the expression of Cdc48/p97, involved in ER-associated ubiquitination and targeting of unfolded proteins to the proteasome, caused defective replication of the bacteria. Importantly, this result was confirmed by RNAi-mediated knockdown of expression of human Cdc48/p97 in HEK 293 cells, indicating that this complex is required for intracellular replication in mammalian cells [START_REF] Dorer | RNA interference analysis of Legionella in Drosophila cells: Exploitation of early secretory apparatus dynamics[END_REF]. The Brucella study identified 52 host factors whose expression knockdown influences infection by this bacterium [START_REF] Qin | RNAi screen of endoplasmic reticulum-associated host factors reveals a role for IRE1alpha in supporting Brucella replication[END_REF]. Fourteen of these factors were shown by various RNAi screens to also mediate infection by other bacterial pathogens [31-33, 38, 41, 42]. Among the genes whose involvement in infection had not been previously reported, the authors concentrated their efforts on IRE1. This signaling molecule is involved in the regulation of the host cell's unfolded protein response, which, in turn, is associated with enhanced expression of genes encoding proteins that participate in ER-associated degradation [START_REF] Friedlander | A regulatory link between ER-associated protein degradation and the unfolded-protein response[END_REF]. The authors showed that Brucella replication in IRE1α -/-mouse embryonic fibroblasts (MEFs) is significantly lower than in wild-type MEFs, thereby confirming the importance of this host factor in Brucella replication in mammalian cells [START_REF] Qin | RNAi screen of endoplasmic reticulum-associated host factors reveals a role for IRE1alpha in supporting Brucella replication[END_REF].

Chlamydia species are obligate intracellular bacteria that cause a wide range of infections in humans. Two large scale RNAi screens were carried out to identify host factors that influence infection of Drosophila S2 cells by C. caviae [START_REF] Derre | RNAi screen in Drosophila cells reveals the involvement of the Tom complex in Chlamydia infection[END_REF] and C. trachomatis [START_REF] Elwell | RNA interference screen identifies Abl kinase and PDGFR signaling in Chlamydia trachomatis entry[END_REF]. Both screens were based on high-throughput microscopy assessments of infection levels following staining with a Chlamydia-specific FITC- It is interesting to notice that, despite the similarities of the systems and experimental approaches employed, while Derré et al. [START_REF] Derre | RNAi screen in Drosophila cells reveals the involvement of the Tom complex in Chlamydia infection[END_REF] targeted approximately 16 000 genes and identified 54 factors whose depletion leads to a decrease in infection, Elwell et al. [START_REF] Elwell | RNA interference screen identifies Abl kinase and PDGFR signaling in Chlamydia trachomatis entry[END_REF] screened about 7200 genes and report an effect on infection for 266 of them. Rather than reflecting actual differences between the two infection and screening setups, this about tenfold difference in "hit rates" likely reflects the distinct criteria chosen by the authors for candidate gene selection.

Both authors selected groups of genes for further confirmation of their role in infection. Derré et al. [START_REF] Derre | RNAi screen in Drosophila cells reveals the involvement of the Tom complex in Chlamydia infection[END_REF] highlighted the importance of the multiprotein Tim-Tom complex (involved in the mitochondrial import of nuclear-encoded proteins) in the Chlamydia infection process and the specificity of Tom40 and Tom22 on the infection of mammalian cells by C. caviae but not by Listeria or C. trachomatis. The report by Elwell et al. [START_REF] Elwell | RNA interference screen identifies Abl kinase and PDGFR signaling in Chlamydia trachomatis entry[END_REF] gives particular emphasis to signaling molecules for which a decrease in expression influenced bacterial uptake by the host cells, most notably those belonging to the PDGFR and Abl kinase signal transduction pathways, which are frequently involved in Rac-dependent cytoskeletal rearrangements. A sister report from the same laboratory focused on about 80 Drosophila genes that regulate the actin cytoskeleton and assessed the effects of the RNAi-mediated knockdown of their expression in terms of the ability of Pseudomonas aeruginosa to enter Drosophila S2 cells [START_REF] Pielage | RNAi screen reveals an Abl kinase-dependent host cell pathway involved in Pseudomonas aeruginosa internalization[END_REF], as monitored by the previously described method of counting colony-forming units following the eukaryotic cell lysis [START_REF] Kazmierczak | Rho GTPase activity modulates Pseudomonas aeruginosa internalization by epithelial cells[END_REF]. The authors found that down-modulation of the expression of several components of the Abl signaling pathway, including Abl, its target Crk, and the p21-activated kinase, Pak1, regulates host cell entry by Ps. aeruginosa.

Signaling molecules were the focus of another study that aimed at identifying host kinases that could be used as targets against the intracellular growth of S. [START_REF] Kuijl | Intracellular bacterial growth is controlled by a kinase network around PKB/AKT1[END_REF]. The authors used a combined imagebased RNAi and kinase inhibitor screening strategy to elucidate signaling pathways that influence infection by these intracellular pathogens. An siRNA library was used to target 779 genes covering the entire kinome and kinase-associated or kinaseregulatory proteins, and infection of the human breast cancer cell line MCF7 by GFP-expressing S. typhimurium was monitored by high-throughput automated microscopy. A reproducible decrease in S. typhimurium growth was observed following down-modulation of ten of the targeted kinases, which were found to cluster around the AKT1 signaling network. Interestingly, none of these were identified by the genome-wide screens that focused on infection of Drosophila macrophage-like cells by L. monocytogenes or M. fortuitum [START_REF] Agaisse | Genome-wide RNAi screen for host factors required for intracellular bacterial infection[END_REF][START_REF] Philips | Drosophila RNAi screen reveals CD36 family member required for mycobacterial infection[END_REF]. While this may be the result of pathogen-specific host responses, it may also reflect differences arising from the type of host cells employed in these studies, an aspect that should always be carefully considered when undertaking an RNAi-based screening approach. If the amenability of Drosophila cells to RNAi-mediated gene expression knockdown and the availability of dsRNA libraries for this system make it an attractive model to identify and study host factors that influence bacterial infection, the use of a mammalian-derived cell line may provide useful information in a more relevant context of infection.

RNAi screens to identify host factors that influence viral infections

Viruses differ from many other pathogens in that they fully depend on the host cell machinery for their replication. In the past, classical virology focused on the virus itself, ignoring cellular functions and complex biological processes in the cell as an essential part of the viral life cycle. Recently, screening approaches have become In a hallmark study Pelkmans and coworkers [START_REF] Pelkmans | Genome-wide analysis of human kinases in clathrin-and caveolae/raft-mediated endocytosis[END_REF] used vesicular stomatitis virus (VSV) and simian virus 40 (SV40) as probes in an siRNA-based high-throughput screening approach to explore the functions of human kinases in different endocytic entry pathways. VSV enters cells via clathrin-mediated endocytosis into early and late endosomes, while SV40 is transported to the ER upon caveolae-mediated endocytosis via caveosomes. A total of 210 kinases involved in endocytosis have been uncovered, several of which were not previously known to play a direct mechanistic role in endocytosis. Interestingly, high selectivity for one of the two entry routes was observed and some kinases were shown to have a positive effect on one endocytic route at the expense of the other, suggesting that clathrin-and caveolae-mediated endocytosis are strongly coordinated. Furthermore, many of the kinases shown to play an essential role in endocytosis also function in various signaling pathways, as in the case of p38MAPK, arguing for a controlled interplay between signaling and endocytosis [START_REF] Pelkmans | Genome-wide analysis of human kinases in clathrin-and caveolae/raft-mediated endocytosis[END_REF].

In a recent genome-wide RNAi study, 305 host proteins were identified as influencing infection by WNV [START_REF] Krishnan | RNA interference screen for human genes associated with West Nile virus infection[END_REF]. Here, 283 proteins facilitated WNV infection (host susceptibility factors), while 22 host proteins were found to reduce WNV infection (host resistance factors). Functional clustering of the host genes revealed a wide variety of cellular processes and pathways required for successful infection [START_REF] Krishnan | RNA interference screen for human genes associated with West Nile virus infection[END_REF]. The assay was performed by infection of gene-silenced HeLa cells with WNV, followed by a microscopy-based quantification of infected cells 24 h later. The RNAi vATPase, endosomal transport regulators and IRF3 [START_REF] Chu | Infectious entry of West Nile virus occurs through a clathrin-mediated endocytic pathway[END_REF][START_REF] Krishnan | Rab 5 is required for the cellular entry of dengue and West Nile viruses[END_REF][START_REF] Davis | 3'-terminal stem-loop of West Nile virus Formatted: Font: Italic Formatted: Font: Italic Deleted: Deleted: Deleted: -Deleted: Deleted: Deleted: -Deleted: -Deleted: -Deleted: -Deleted: Deleted: Deleted: -Deleted: Deleted: Deleted: -genomic RNA facilitates viral minus-strand RNA synthesis[END_REF][START_REF] Emara | Interaction of TIA-1/TIAR with West Nile and dengue virus products in infected cells interferes with stress granule formation and processing body assembly[END_REF][START_REF] Hirsch | The Src family kinase c-Yes is required for maturation of West Nile virus particles[END_REF][START_REF] Mackenzie | Cholesterol manipulation by West Nile virus perturbs the cellular immune response[END_REF][START_REF] Fredericksen | The host response to West Nile virus infection limits viral spread through the activation of the interferon regulatory factor 3 pathway[END_REF], but also identified 294 novel interaction partners of WNV. Among the host susceptibility factors, RNAbinding proteins, ubiquitination-related proteins such as the ubiquitin ligase CBLL1, transcription factors, C-type lectins and protocadherins like PCDHB5 were detected, while the monocarboxylic acid transporter MCT4 was identified as a strong host resistance factor [START_REF] Krishnan | RNA interference screen for human genes associated with West Nile virus infection[END_REF]. The study also revealed that silencing of 36% of the host factors exploited by WNV also reduced infection by Dengue Virus, a related flavivirus, suggesting both overlapping and unique interaction networks with their host.

Using a genome-wide screen in Drosophila, more than 100 previously unrecognized host proteins required by influenza virus were identified, demonstrating the feasibility and value of using Drosophila RNAi screening to elucidate novel host factors [START_REF] Hao | Drosophila RNAi screen identifies host genes important for influenza virus replication[END_REF]. Since Drosophila cells do not express the cognate receptor for human influenza virus, cells were infected with VSV glycoprotein (VSV-G)-pseudotyped influenza virus particles. Having screened over 13 000 genes, the human homologues RNA viruses. This study suggests another direction for antiviral drug discovery by modulating the host cell's ribosome activity [START_REF] Cherry | Genome-wide RNAi screen reveals a specific sensitivity of IRES-containing RNA viruses to host translation inhibition[END_REF].

Recently, three genome-wide RNAi screens on host genes required for the replication of HIV-1 were reported (Table 2). The first screen to be published was performed in cultured human HeLa cells expressing CD4 as the essential receptor for HIV-1 entry [START_REF] Brass | Identification of host proteins required for HIV infection through a functional genomic screen[END_REF]. The goal was to identify host proteins involved in early events of infection such as virus entry, uncoating, reverse transcription, integration and viral gene expression as well as factors needed for late stages in infection such as viral assembly and release. Considering more than 21 000 genes, Brass et al. [START_REF] Brass | Identification of host proteins required for HIV infection through a functional genomic screen[END_REF] identified 273 host factors required for HIV-1 replication. Preliminary characterization of three of the genes revealed previously unknown functions: Rab6, which is involved in the retrograde transport from endosomes to the Golgi and from the Golgi to the ER, was shown to be important for virus entry. Transportin-3 (TNPO3), important for the import of multiple proteins into the nucleus, revealed a function after reverse transcription but prior to integration and the depletion of the mediator complex Med28 specifically affected the reverse transcription of HIV-1 genes. Of the 273 genes, 237 had not previously been identified as important for HIV-1 infection. In a second study by König et al. [START_REF] Konig | Global analysis of hostpathogen interactions that regulate early-stage HIV-1 replication[END_REF], the investigators performed a genome-wide RNAi screen by infecting human 293T cells with replication-defective pseudotyped HIV-1 particles bearing the VSV-G instead of HIV-1 envelope proteins.

VSV-G-pseudotyped particles facilitate virus infection as viral particle

internalization is mediated by the cellular endocytic machinery, while wild-type HIV-1 is internalized predominantly by fusion at the plasma membrane. Thus, host factors involved in HIV envelope-mediated entry and fusion could not be scored, whereas early events from uncoating up to integration were elucidated. By applying a diverse setup of analytical methods at a genome-wide scale, including yeast-two- [START_REF] Konig | Global analysis of hostpathogen interactions that regulate early-stage HIV-1 replication[END_REF] compiled a list of more than 2400 potential host genes required by HIV-1. Finally, the number of selected host factors was narrowed down by a series of filters removing genes that affected the replication of control viruses or genes known to be associated with cell death. Following this selection process, 295 genes were scored as cellular host factors important for HIV-1 replication, including cytoskeletal proteins (most likely involved in the intracellular transport of the viral reverse transcription complex), protein complexes that regulate ubiquitin conjugation (possibly required for virus uncoating), nucleic acid binding proteins (presumably interacting with the viral reverse transcriptase), factors involved in RNA splicing and, surprisingly, proteins related to DNA-damage response. Remarkably, in this study 55 factors were mapped to specific steps in the HIV-1 life cycle [START_REF] Konig | Global analysis of hostpathogen interactions that regulate early-stage HIV-1 replication[END_REF]. The genome-wide RNAi screen on HIV-1 carried out by Zhou et al. [START_REF] Zhou | Genome-scale RNAi screen for host factors required for HIV replication[END_REF] was set up to determine host factors involved in all stages of virus infection from virus entry to release and viral cell-to-cell spread. In total, 390 genes were identified and confirmed as playing an important role in the HIV-1 replication cycle. After screening in silico against databases containing information on expression levels of over 11 000 genes in diverse tissues (including activated T cells and macrophages as the two predominant cellular targets of HIV-1) only 232 genes remained to be considered as host factors for HIV-1. As with the other screens, all identified genes could be grouped into different functional classes including virus entry, mitochondrial functions or energy metabolism. In addition, the mediator complex and the NF-κB signaling pathway were identified as being involved in the pathogenesis of HIV-1. Although each of these three screens identified about 300 cellular host factors exploited by HIV-1, a comparison between the identified host genes revealed only three validated genes in common, i.e., Med 6 and Med 7, two subunits of the mediator complex, as well as RELA, a binding partner of NF-κB. The severe discrepancy between the results obtained is intriguing, but may be explained by the different conditions of the three screens, such as using different cell lines, different siRNA libraries and different virus strains. Moreover, siRNA treatment times were different and infection periods varied, suggesting that each screen detected a subset of genes involved in a specific stage of infection. The fact that many host factors uncovered by the three genome-wide screens have been independently identified in the past, like the nuclear import factor TNPO3/Transportin SR2 [START_REF] Luban | HIV-1 infection: Going nuclear with TNPO3/Transportin-SR2 and integrase[END_REF][START_REF] Christ | Transportin-SR2 imports HIV into the nucleus[END_REF], cyclinT1 [START_REF] Wei | A novel CDK9-associated C-type cyclin interacts directly with HIV-1 Tat and mediates its high-affinity, loop-specific binding to TAR RNA[END_REF] or factors involved in the NF-κB signaling pathway [START_REF] Griffin | Activation of HIV gene expression during monocyte differentiation by induction of NFkappa B[END_REF], indicates that all three screening approaches reveal gene lists of enormous interest for future exploration.

((Table 2)) Among other viruses, HCV remains a severe threat to human health. HCV infects 3% of the world's population establishing a chronic infection in 70-80% of exposed humans, leading to liver failure or hepatocellular carcinoma. Thus, identifying cellular cofactors of the HCV life cycle might lead to novel targets for anti-HCV therapies. Using a genome-wide siRNA library, Tai et al. [START_REF] Tai | A functional genomic screen identifies cellular cofactors of hepatitis C virus replication[END_REF] recently identified 96 human genes that support HCV replication in a Huh7/Rep-Feo replicon cell line [START_REF] Tanabe | Synergistic inhibition of intracellular hepatitis C virus replication by combination of ribavirin and interferon-alpha[END_REF][START_REF] Kim | A cell-based, highthroughput screen for small molecule regulators of hepatitis C virus replication[END_REF] measuring luciferase activity 72 h after siRNA treatment. Among these genes, 27 were found to be involved in lipid metabolism, membrane biogenesis, sorting and trafficking, supporting previous observations that HCV, like other positive-strand RNA viruses, replicates on altered host membranes, also described as "membranous webs" [START_REF] Egger | Expression of hepatitis C virus proteins induces distinct membrane alterations including a candidate viral replication complex[END_REF][START_REF] Gosert | Identification of the hepatitis C virus RNA replication complex in Huh-7 cells harboring subgenomic replicons[END_REF]. Furthermore, 6 genes were identified as being associated with the cellular RNA machinery, including SERBP1, HNRPAB and NOP5/NOP58. A highranking hit in the study by Tai et silencing is well tolerated in cultured cells [START_REF] Tai | A functional genomic screen identifies cellular cofactors of hepatitis C virus replication[END_REF]. In addition, the COPI vesicle coat complex and hepcidin, a peptide hormone regulating iron homeostasis [START_REF] Nemeth | Hepcidin regulates cellular iron efflux by binding to ferroportin and inducing its internalization[END_REF], were shown to affect HCV replication. Previous RNAi studies have identified several host cell factors involved in HCV replication by applying limited siRNA libraries targeting about 4000 [START_REF] Ng | Identification of host genes involved in hepatitis C virus replication by small interfering RNA technology[END_REF], 510 [START_REF] Supekova | Identification of human kinases involved in hepatitis C virus replication by small interference RNA library screening[END_REF] and 62 genes [START_REF] Randall | Cellular cofactors affecting hepatitis C virus infection and replication[END_REF], respectively. There was little overlap between the results of these three screens and the study by Tai et al. [START_REF] Tai | A functional genomic screen identifies cellular cofactors of hepatitis C virus replication[END_REF].

Remarkably, only 1 gene out of 11 top ranked hits from the three prior screens could be reconfirmed by Tai and coworkers when re-tested [START_REF] Tai | A functional genomic screen identifies cellular cofactors of hepatitis C virus replication[END_REF]. The reasons for the discrepancies might be the same as discussed for HIV-1 above. Importantly, studies based on a HCV replicon model only allow identification of host cofactors involved in replication. Thus, in future, fully infectious, cell-culture-adapted HCV strains will have to be used to explore other aspects of the HCV life cycle, such as entry, uncoating and assembly.

Conclusion

Host factors have been emerging as promising targets for intervention strategies against infections by various pathogens [START_REF] Cunha-Rodrigues | Antimalarial drugs -host targets (re)visited[END_REF][START_REF] Lebeis | Aligning antimicrobial drug discovery with complex and redundant host-pathogen interactions[END_REF]. In this context, RNAi-based screening approaches, combined with bioinformatic analysis methods, have become powerful tools to study overall gene functions, and have been successfully applied to identify genes involved in pathogen replication. Although the functions of several host genes during infection have already been elucidated, the search for host factors that play a role during pathogen invasion and multiplication is far from complete.

The identities of host cell factors identified by RNAi-based screens seem to depend strongly on the assay conditions and readouts chosen, suggesting that further genes any doubt, all pathogen-related RNAi screens performed so far are of great interest, shedding light on a large number of previously unknown gene functions and identifying novel host cellular pathways utilized by pathogens. However, the cells used in these studies were often chosen for experimental convenience and do not always represent physiological targets for the pathogens under study, making it advisable to confirm the importance of the genes identified in a physiologically more relevant system [START_REF] Medema | Optimizing RNA interference for application in mammalian cells[END_REF][START_REF] Echeverri | High-throughput RNAi screening in cultured cells: A user's guide[END_REF]. Moreover, genes whose functions are redundant with those of other genes might not be detected, as siRNA-mediated knockdown will only deplete a single gene product at a time. This indicates the need for future combinatorial approaches employing several siRNAs targeting different genes at the same time. Furthermore, to prevent the detection of false-positive hits due to offtarget effects, several siRNAs targeting different regions of a given mRNA must yield similar phenotypes, which also has to be shown to result from successful gene knockdown [78]. On the other hand, false-negative results might also become an obstacle if siRNAs are not efficient enough in silencing their target mRNAs or if the gene product is so stable that a loss-of-function phenotype cannot be monitored even though the respective siRNA is fully functional. Thus, the efficacy of the siRNAs used has to be confirmed either at the mRNA level (by using quantitative RT-PCR to determine gene expression levels) or at the protein level (by employing Western blotting, in the case that the corresponding antibody is available) [79]. Furthermore, the validation of hit information by alternative screening techniques and/or targeted assays such as the use of blocking antibodies and inhibitors should always be sought.

A close scrutiny of the reported RNAi screens to identify host factors involved in pathogen infections reveals that the selection criteria for "hit" definition vary considerably between different studies. This, in conjunction with overall

4 during

 4 Plasmodium infection have been carried out and are worth mentioning in the context of this review. Gene silencing through direct injection of dsRNA into adult

  were evaluated by a high-throughput automated microscopy-based analysis of bacterial GFP readouts. Another fluorescence microscopy-based RNAi study

[ 39 ]

 39 . These screens employed 73 and 240 dsRNAs, respectively, and infection was assessed by fluorescence microscopy following immunostaining of the bacteria. The Deleted: -with L. pneumophila indicated that the replication vacuole of this

Deleted: 10 - 12 typhimurium

 1012 and Mycobacterium spp.

  investigating host cell functions exploited by viruses for their replication. To date only a few RNAi screens, on a small number of viruses, have been reported, including studies on human immunodeficiency virus (HIV-1), influenza virus, HCV and West Nile virus (WNV), the causative agent of the mosquito-borne West Nile fever.

Formatted:

  Font: Italic Formatted: Font: Italic Formatted: Font color: Black Deleted: more and more Deleted: hepatitis C virus ( host factors that had already been previously characterized, like

  of ATP6V0D1, COX6A1 and NXF1 as well as mitochondrial electron transporter complexes III and IV were shown to have key functions in the replication of H5N1 and H1N1 influenza A virus. Many RNA viruses, like HCV or rhinovirus, utilize internal ribosomal entry sites (IRES) for translation. To elucidate host factors required for IRES-dependent translation and viral replication, Cherry et al. [57] performed a genome-wide RNAi screen in Drosophila cells infected with Drosophila C virus (DCV). The authors reported the identification of 66 ribosomal proteins that specifically inhibited DCV replication, when they were depleted, without any effect on non-IRES-containing

Formatted

Formatted

  al. was the phosphatidylinositol 4-kinase PI4KA, whose function in mammalian cells has not been well defined to date. Previous studies, however, already revealed a direct function of PI4KA in HCV replication . PI4KA appears to be an attractive target for anti-HCV therapeutics as PI4KA

  by additional screens with different experimental setups. Without

  question of how to validate potential hits, makes the gene lists obtained by different screening approaches hard to compare. Thus, selection criteria need to be standardized, at least for screens focused on similar pathogens and employing similar experimental setups. Nevertheless, siRNA screens offer large sets of promising data, allowing the exploration of the life cycle of a pathogen as well as the definition of targets for novel therapeutic approaches. As more data will be generated in the future by further RNAi screening-based studies, it will become increasingly necessary to establish widely accessible databases containing information about all host genes implicated in pathogen replication.We thank Elena Levashina, Mário Ramirez and Maria M. Mota as well asNigel Brown, Kathleen Börner and Johannes Hermle for critical reading of the manuscript. M.P. is a holder of a Ciência 2007 position of the Portuguese Ministry of Science and is supported by FCT Grant PTDC/BIA-BCM/71920/2006. M.J.L. is supported by the Sonderforschungsbereich 638 (Dynamics of macromolecular complexes in biosynthetic transport). This work was performed in the scope of the FP6 BioMalPar Network of Excellence and supported by the cluster of excellence CellNetworks at the University of Heidelberg. ((Funded by: • FCT • DFG • Cluster of excellence CellNetworks, University of Heidelberg)) The authors have declared no conflict of interest. 8 References Formatted: Font: Not Bold Formatted: Font: Not Italic Formatted: Bullets and Numbering Formatted: Font: (Default) Times New Roman, Italic, English (U.K.) Formatted: Font: Italic, English (U.K.) Prudencio, M., Rodrigues, C. D., Ataide, R., Mota, M. M., Dissecting in vitro host cell infection by Plasmodium sporozoites using flow cytometry. Cell Echeverri, C. J., Beachy, P. A., Baum, B., Boutros, M. et al., Minimizing the risk of reporting false positives in large-scale RNAi screens. Nat. Methods 2006, 3, 777-779. [79] Smith, C., Sharpening the tools of RNA interference. Nat. Methods 2006, 3, 475-486.

Figure 1 .

 1 Figure 1. Experimental setup for high-throughput, high-content, RNAi-based screening of host factors involved in Plasmodium liver infection. Host cells are transfected with siRNAs 24 h after seeding and infected 48 h later with Plasmodium sporozoites freshly extracted from the salivary glands of female Anopheles mosquitoes. At 24 h after infection, cells are fixed and stained for parasite (green), actin (red) and nuclei (blue) and imaged by immunofluorescence microscopy.Infection is quantified and normalized following automated image acquisition and analysis.

Figure 2 .

 2 Figure 2. Effect of dsRNA-mediated knockdown of Drosophila Rab5 expression on infection by M. fortuitum (A) and L. monocytogenes (B). Bacteria are shown in green, actin in red and nuclei in blue. Adapted with permission from Philips et al. [32] (A) and Agaisse et al. [31] (B).

Formatted 31 Table 1 .

 311 RNAi-based screens to identify host factors involved in bacterial infections a) VT, vesicle transport; CO, cytoskeletal organization; CSR, cell surface receptor; ST, signal transduction; CC, cell cycle; LM, lipid metabolism; Tr, transcription.

Table 2 .

 2 RNAi-based screens to identify host factors involved in HIV-1 replication

	Virus	Host cells	Number of investigated genes	Time of siRNA treatment	Infection time	Readout	Number of host factors identified	Reference
	HIV-1 (IIIB)	HeLa derived TZM cells (CD4 + , β-gal reporter)	21 121 genome-wide	72 h	Part 1: 48 h Part 2: 24 h	Part 1: p24 stain activity Part 2: β-gal	273	58
	VSV-G pseudotyped HIV-1 luc vector	293T	19 628 genome-wide	48 h	24 h	Luciferase activity	295	59
	HIV-1 (HXB2)	HeLa P4/R5 cells (CD4 + , β-gal reporter)	19 707 genome-wide	24 h	48 h and 96 h	β-gal activity	232	60

Wiley-VCH Biotechnology Journal


Florian Hechner
email: hechner@math.unistra.fr

Bernard Heinkel
email: heinkel@math.unistra.fr

A quasimartingale characterization of p-stable type Banach spaces

Keywords: AMS Subject Classification: 46B09, 60B12, 60G48 Marcinkiewicz-Zygmund Law of Large Numbers, Quasimartingales, Type of a Banach space, Stable type of a Banach space

We characterize Banach spaces B of stable-type p (1 < p < 2) by the property that for every sequence (Xi) of B-valued random variables, independent, centered and fulfilling some integrability assumption, the sequence X 1 +•••+Xn n 1/p is a quasimartingale.

Introduction

"How to characterize the regularity of a Banach space (B, • ) by the fact that a kind of classical strong law of large numbers (SLLN) holds for B-valued random variables (r.v.)?" is a well know problem. Two kinds of regular Banach spaces -the spaces of Rademacher type p and the spaces of stable type phave been nicely characterized in that way (see chapter 9 in [START_REF] Ledoux | Probability in Banach spaces[END_REF]).

Here our goal will be to show that the SLLN characterization of spaces of stable type p (1 < p < 2) can be made more precise in supposing that the "normalized sums" obeying the SLLN have even a quasimartingale behaviour.

To begin with, we recall some definitions.

In the sequel, (B, • ) will be a real separable Banach space, equipped with its Borel σ-field B. A B-valued r.v. X is a measurable function defined on a probability space (Ω, T , P) with values in (B, B). Such a r.v. is said to be (strongly) integrable if E X < +∞ and ∀f ∈ B ′ , Ef (X) = 0; this is denoted by E(X) = 0.

Let p 1 be given. The weak-ℓ p norm of a sequence a := (a 1 , . . . , a n ) of real numbers is defined as follows : a p,∞ := sup t>0 (t p Card(i :

|a i | > t)) 1 p = n sup k=1 a * k k 1/p ,
where (a * 1 , . . . , a * n ) denotes the non-increasing rearrangement of the sequence (|a 1 |, . . . , |a n |).

Let now (ε k ) be a sequence of independent Rademacher random variables that is

P(ε k = 1) = P(ε k = -1) = 1
2 . Rademacher type p spaces and stable type p spaces are defined as follows :

Definition 1. 1. Let 1 < p < 2. The Banach space (B, • ) is of Rademacher type p if
there exists a constant c(p) > 0 such that for every finite sequence (x i ) in B :

E n i=1 ε i x i p 1 p c(p) n i=1 x i p 1 p . 2. Let 1 p 2.
The Banach space (B, • ) is of stable type p if there exists a constant C(p) > 0 such that for every finite sequence (x i ) in B :

E n i=1 ε i x i C(p) ( x 1 , . . . , x n ) p,∞ .
Remark 2.

If (B, •

) is of stable type p, then there exists q > p, such that (B, • ) is also of stable type q [5].

If (B, •

) is of stable type p, it is also of Rademacher type p [START_REF] Pisier | Type des espaces normés[END_REF].

3. The above definition of stable type is not the classical one (which involves standard stable r.v.), but an equivalent statement (see for instance [START_REF] Ledoux | Probability in Banach spaces[END_REF], proposition 9.12) which will be used in our proofs.

Remark 3. Let (B, • ) be a Banach space and 1 p 2. If B is of (Rademacher) type p, there exists a constant c(p) such that for every finite sequence (X i ) with

X i ∈ L p : E n i=1 X i p c(p) n i=1 E X i p . (1)
The stable type p has been characterized in terms of Marcinkiewicz-Zygmund like SLLN : Theorem 4 (Maurey-Pisier [START_REF] Maurey | Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach[END_REF]). Let 1 < p < 2. The following two properties are equivalent :

1. (B, • ) is of stable type p.
2. For every bounded sequence (x i ) in B, the sequence

1 n 1/p n k=1 ε k x k converges a.s. to 0.
Theorem 5 (Woyczynski [START_REF] Woyczyński | On Marcinkiewicz-Zygmund law of large numbers in Banach spaces and related rates of convergence[END_REF]). Let 1 < p < 2. The following two properties are equivalent :

1. (B, • ) is of stable type p.
2. For every sequence (X i ) of independent, strongly centered B-valued r.v.

for which there exists a nonnegative r.v. ξ with Eξ p < +∞ such that :

∃c > 0, ∀t > 0, ∀i ∈ N * , P( X i > t) cP(ξ > t),
the sequence Sn n 1/p converges a.s. to 0, where, as usual,

S n := X 1 + • • • + X n .
In this paper, we will prove a result in the same spirit as Woyczynski's result, but in which the SLLN behaviour of the sequence Sn n 1/p is even a quasimartingale behaviour.

A quasimartingale characterization of spaces

of stable type p.

We start this section by defining the quasimartingale behaviour of Sn n 1/p : Definition 6. Let (X k ) be a sequence of independent, strongly centered (B,

• )-valued r.v. Denote S n := X 1 + • • • + X n and F n := σ(X 1 , . . . , X n ). Let p ∈]1, 2[. The sequence Sn n 1/p , F n , or simplier Sn n 1/p , is a quasimartingale if : +∞ n=1 E E S n+1 (n + 1) 1/p - S n n 1/p F n < +∞. ( 2
)
Remark 7. Since the r.v. (X k ) are independent and centered, condition (2) is equivalent to :

+∞ n=1 E S n n 1+1/p < +∞.
Now we are able to state our characterization of spaces of stable type p (1 < p < 2) :

Theorem 8. Let 1 < p < 2.
The following two properties are equivalent :

1. B is a stable type p space; 2. For every sequence (X n ) of independent, strongly centered r.v., such that +∞ 0

g 1/p (t)dt < +∞, ( 3
)
where ∀t > 0, g(t) := sup

n 1 P( X n > t), Sn n 1/p is a quasimartingale. Remark 9.
1. Condition (3) is not surprising : indeed, in the i.i.d. case, it can be written :

+∞ 0 P 1/p ( X > t)dt < +∞, (4)
which condition is necessary for Sn n 1/p being a quasimartingale in every Banach space B (see [START_REF] Hechner | The Marcinkiewicz-Zygmund LLN in Banach spaces: a generalized martingale approach[END_REF], proposition 3). [START_REF] Marcus | Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes[END_REF] implies that E X p < +∞ (see [START_REF] Hechner | The Marcinkiewicz-Zygmund LLN in Banach spaces: a generalized martingale approach[END_REF], remark 4).

Property

3. There exists a small class of r.v. X such that E X p < +∞ and for which (4) does not hold (see example 1 in [START_REF] Hechner | The Marcinkiewicz-Zygmund LLN in Banach spaces: a generalized martingale approach[END_REF]).

So -comparing theorems 5 and 8 -one sees that the price to pay for getting a quasimartingale behaviour for Sn n 1/p instead of a simple a.s. convergence to 0, is to sharpen a little bit the hypothesis Eξ p < +∞ of theorem 5.

Proof.

In the sequel, c k will denote positive constants which precise value does not matter.

Let us show the implication 1 =⇒ 2. First consider the special case where there exists M > 0 such that : ∀t > M, g(t) = 0. Then ∀k, X k M a.s. The space B being of Rademacher type q for some q > p by comments 1) and 2) following definition 1, and using relation ( 1), one has : (

E S n n 1+1/p c(q) n 1+1/p n k=1 E X k q 1 q c(q)M n 1 q n 1+
Now define v n := inf t > 0|g(t) 1 n . It follows from the definition of g and ( 5) that :

v n n 1/p and g(v n ) 1 n .
For every n ∈ N * and k = 1, . . . , n, one considers the following centered r.v. (by symmetry) :

U n,k := X k 1 ( X k vn) and V n,k := X k 1 ( X k >vn) ,
and the associated sums :

A n := n k=1 U n,k n 1+ 1 p and B n := n k=1 V n,k n 1+ 1 p .
For showing that the series having general terms E Sn n 1+ 1 p converges, one will show that :

+∞ n=1 E A n < +∞ (6)
and

+∞ n=1 E B n < +∞. (7)
We first prove [START_REF] Métivier | Semimartingales. A course on stochastic processes[END_REF]. By remark 1. following definition 1, there exists q > p such that (B, • ) is also q-stable. Now suppose that the r.v. X k are defined on a probability space (Ω, T , P) and consider (ε k ) a sequence of independent Rademacher r.v. defined on another probability space (Ω ′ , T ′ , P ′ ). By symmetry, one has :

E A n = Ω Ω ′ 1 n 1+ 1 p n k=1 ε k (ω ′ )U n,k (ω) dP ′ (ω ′ ) dP(ω).
By application of the definition of the stable type q, one obtains :

E A n C(q) n 1+ 1 p E ( ( U n,1 , . . . , U n,n ) q,∞ ) .
For bounding the tails of the weak-ℓ p norm of a sequence of positive, independent r.v., we will use the following classical result due to Marcus Pisier [4] :

Lemma 10. For positive valued, independent r.v. ξ 1 , . . . , ξ n , one has :

∀q 1, ∀u > 0, P ( (ξ 1 , . . . ξ n ) q,∞ > u) 2e u q ∆(ξ 1 , . . . , ξ n ), (8)
where ∆(ξ 1 , . . . , ξ n ) = sup t>0 t q n k=1 P(ξ k > t) .

For simplicity, denote ∆ n the quantity ∆( U n,1 , . . . , U n,n ), and notice that by application of lemma 10 :

E ( ( U n,1 , . . . , U n,n ) q,∞ ) = +∞ 0 P ( ( U n,1 , . . . , U n,n ) q,∞ > u) du ∆ 1 q n + +∞ ∆ 1 q n 2e u q ∆ n du c 2 ∆ 1 q n
So the proof of ( 6) reduces to the following lemma :

Lemma 11. +∞ n=1 ∆ 1 q n n 1+ 1 p < +∞

Proof of lemma 11 :

One first notices that :

∆ n sup t vn t q n k=1 P( X k > t) sup t vn nt q g(t) n vn 0 g 1 q (u)du q ,
the last inequality following from the fact that g is decreasing.

For concluding the proof of lemma 11 it remains to check that the series with general term a n :=

1 n 1+ 1 p -1 q vn 0 g 1 q (u)du converges. First observe that : +∞ n=1 a n +∞ n=1 1 n 1+ 1 p -1 q n j=0 vj+1 vj g 1 q (u)du,
where v 0 := 0, and then exchange the summations in n and j :

+∞ n=1 a n c 3   v 1 + +∞ j=1 1 j 1 p -1 q vj+1 vj g 1 q (u)du   , so, by the definition of v j+1 : +∞ n=1 a n c 4 v 1 + +∞ 0 g 1 p (u)du ,
which concludes the proof of lemma 11. Now we are going to prove [START_REF] Pisier | Type des espaces normés[END_REF]. First notice the following chain of inequalities :

E B n n k=1 E V n,k n 1+ 1 p = n k=1 +∞ 0 P V n,k n 1+ 1 p > u du n k=1 v n n 1+ 1 p P( X k > v n ) + n n 1+ 1 p +∞ vn g(u)du nv n n 1+ 1 p g(v n ) + 1 n 1 p +∞ vn g(u)du v n n 1+ 1 p + 1 n 1 p +∞ vn g(u)du.
Therefore, for proving [START_REF] Pisier | Type des espaces normés[END_REF], it suffices to check that condition (3) implies the convergence of the two series with general terms vn Lemma 12.

If (3) is fulfilled, then +∞ n=1 vn n 1+ 1 p < +∞.
Proof of lemma 12 : For j ∈ N * , one denotes t j := vj +vj+1 2

. Then :

+∞ 0 g 1 p (u)du +∞ j=1 tj vj g 1 p (t)dt +∞ j=1 1 (j + 1) 1 p v j+1 -v j 2 . (9)
Now observe that :

n-1 j=1 1 (j + 1) 1 p (v j+1 -v j ) = - v 1 2 1 p + n-1 j=2 v j 1 j 1 p - 1 (j + 1) 1 p + v n n 1 p (10)
As : For completing the proof of the implication 1 =⇒ 2 of theorem 8, it remains to check : Lemma 13. is a quasimartingale, then :

v n 2 g 1 p (v n )

Under (3), one has

+∞ n=1 E T n n 1+ 1 p < +∞. ( 11
)
By Jensen's inequality :

∀N ∈ N * , +∞ n=N E T n n 1+ 1 p E T N +∞ n=N 1 n 1+ 1 p c 8 E T N N 1 p , so by (11), lim n→+∞ E T n n 1 p = 0. ( 12
)
By the conditionnal version of Jensen's inequality :

∀n ∈ N * , E ( T n+1 |G n ) T n , (13) so :
N n=1

E E T n+1

(n + 1)

1 p - T n n 1 p G n N n=1 E E T n+1 -T n (n + 1) 1 p G n +c 9 N n=1 E T n n 1+ 1 p
and by (13) :

N n=1 E E T n+1 (n + 1) 1 p - T n n 1 p G n E T N +1 (N + 1) 1 p + c 10 N n=1 E T n n 1+ 1 p .
Finaly, by ( 11) and ( 12), the sequence

Tn n 1+ 1 p is a positive quasimartingale.
Therefore, thanks to theorem 9.4 in [START_REF] Métivier | Semimartingales. A course on stochastic processes[END_REF], it converges a.s. to a limit, which, by ( 12) is necessary 0. This concludes the proof of proposition 14.

Let us now come back to the proof of the implication (2) =⇒(1) of theorem 8.

Let (ε k ) be a sequence of independent Rademacher r.v. and (x k ) be a bounded sequence of elements in B. Defining M := sup x k , X k := ε k x k , one gets :

∀t > M, g(t) = sup 3 What happens when p = 1?

It is natural to wonder if the spaces of stable type 1 (see [START_REF] Hechner | Kolmogorov's law of large numbers and generalized martingales[END_REF] for the definition of stable type 1) also admit a "quasimartingale characterization ". In fact it is the case, by theorem 6 in [START_REF] Hechner | Kolmogorov's law of large numbers and generalized martingales[END_REF], which can be reformulated as follows :

Theorem 15. Let B be a Banach space. The following two properties are equivalent :

1. B is of stable type 1.

2. For every sequence (X n ) of independent, strongly centered r.v., such that +∞ 0 g(t)dt < +∞, (

where ∀t > 0, g(t) := sup

n 1 P( X n ln(1 + X n ) > t),
Sn n is a quasimartingale.

,

  it follows from (9) and (10) that the series having general term vn n

1 p 1 p

 11 By exchanging the summations in n and j, one gets : (u)du.Let us now show the converse implication 2 =⇒ 1 of theorem 8. We first show a general property which is of independent interest : Proposition 14. Let (Y n ) be a sequence of independent strongly centered r.v. with values in a general Banach space (B, • ). Denote by T n the sum Y 1 + . . . + Y n and by G n the σ-field σ(Y 1 , . . . , Y n ). If Tn n 1 p , G n is a quasimartingale, then Tn n converges a.s. to 0. Proof of proposition 14 : As noticed earlier, if Tn n 1 p

ε

  k x k is a quasimartingale, which by proposition 14 converges a.s. to 0. The p-stability of the space (B, • ) then follows from theorem 4.

  converges, one will split each r.v. X 1 , . . . , X n involved in the sum S n into two parts U n,k and V n,k by truncating X k at a suitable level v n .For defining v n , one first notices that, g being decreasing, one has :

					1
					p
	and the series having general terms E Sn n 1+ 1 p	converges.
	From now we suppose that ∀t > 0, g(t) > 0.
	By a classical symmetrization argument it suffices to consider the case of
	symmetrically distributed r.v. (X k ). For showing that under condition (3) the
	series having general term E Sn n 1+ 1 p
	sup	t p g(t)	+∞	g	1 p (x)dx
	t>0	0

p < +∞.

Furthermore, multiplying the X k by a suitable constant if necessary, one can suppose without loss of generality that : sup t>0 t p g(t) 1.


Tom Leclerc
email: tom.leclerc@loria.fr

Laurent Ciarletta
email: laurent.ciarletta@loria.fr

André Schaff
email: andre.schaff@loria.fr

A Stable Linked Structure Flooding for Mobile Ad Hoc Networks with Fault Recovery

Efficient message dissemination in ad hoc networks can be fostered by exploiting stable (sub-)structures. By efficient we mean low network resource usage regarding reachability. In this paper we build a hierarchical protocol. We first create single-hop clusters among stableconnected devices. On top of those clusters, we further determine intercluster relays (ICR), finally providing an overall stable-connected structure. Our proposed stable linked structure flooding (SLSF) protocol efficiently disseminates data among stable nodes. Additional fault recovery mechanisms are employed to compensate for local intermittent node failures if needed. The experiments show that our approach increases flooding performances with a low bandwidth usage. Furthermore SLSF remains very efficient with or without the fault recovery mechanism that provides robustness.

Introduction

Mobile ad hoc networks are composed of a collection of devices that communicate with each other over a wireless medium [START_REF] Dousse | Connectivity in ad-hoc and hybrid networks[END_REF]. Such a network can be formed spontaneously whenever devices are in transmission range. Potential applications of such networks can be found in traffic scenarios, environmental observations, ubiquitous Internet access, and in search and rescue scenarios as described in detail in [START_REF] Santi | Topology control in wireless ad hoc and sensor networks[END_REF]. However, since joining and leaving of nodes occurs dynamically, the network topology changes frequently. Our solution starts by building local groups of one-hop stable-connected devices in a self-organizing manner. Moreover, the approach we introduced in [START_REF] Leclerc | SLSF: stable linked structure flooding for mobile ad hoc networks[END_REF] aims at discovering stable connections between groups, thus creating bigger stable-linked network structures. We exploit the stable-linked structures within the network topology to streamline information exchange and to minimize the overhead. The local one-hop groups are built using the NLWCA clustering protocol [START_REF] Andronache | Nlwca node and link weighted clustering algorithm for backbone-assisted mobile ad hoc networks[END_REF]. As in WCPD [START_REF] Andronache | Hytrace backbone-assisted path discovery in hybrid networks[END_REF] specific beacon formats are used to detect nearby stable-connected clusters. Furthermore, to create bigger stable-connected structures we present Inter-Cluster Relays (ICR). Finally, to add robustness, a fault recovery protocol is employed to compensate for local intermittent node failures. Fault recovery can be selectively enabled/disabled on per-packet basis.

The remainder of this paper is organized as follows. The next Section 2 sets the context and presents the related work for this paper. Section 3 describes the building blocks of our SLSF protocol. In Section 4 we evaluate our approach and present the simulation results. We conclude our paper and present the future work in section 5.

Context & Related Work

NLWCA & WCPD

The Weighted Cluster-based Path Discovery protocol (WCPD) is designed to take advantage of the cluster topology built by the Node and Link Weighted Clustering Algorithm (NLWCA) in order to provide path discovery and broadcast mechanisms in mobile ad hoc networks. NLWCA organizes ad hoc networks in one-hop clusters (Figure 1) by using only information available locally. Each device elects exactly one device as its clusterhead (CH), i.e. the neighbor with the highest weight. So far, a topological chain can be formed by so called sub-head nodes. A sub-head is a node that elects a neighbor node as CH but at the same time is elected as CH by some other one-hop neighbor nodes. However, sub-heads can lead to more than three hops between a source CH and its nearby CHs which could lead to a complex communication protocol. To obtain strict one-hop clusters, thus simplifying the protocol, a rule was added to the original NLWCA algorithm: a node that already elected a foreign node as CH is not eligible to be elected by another node as CH. From a graph theory point of view, one-hop clusters form a dominating set.

The main goal of NLWCA is to avoid superfluous re-organization of the clusters, particularly when clusters cross each other. To achieve this, NLWCA assigns weights to the links between the own node and the network neighbor nodes. This weight is used to keep track of the connection stability to the onehop network neighbors. When a link weight reaches a given stability threshold it is considered stable and the device is called stable neighbor device. The CH is elected only from the set of stable neighbors which avoids the re-organization of the topology when two clusters are crossing for a short period of time.

WCPD, on top of NLWCA, discovers nearby stable-connected clusters in a pro-active fashion. For the nearby CHs discovery algorithm, WCPD uses the beacon to detect devices in communication range. NLWCA and WCPD combined provide to each node, through the beacon (Figure 2), following information about each stable one-hop neighbor: its weight, its CH ID, the ID set of discovered CHs and their respective path length.

The WCPD broadcasting algorithm is simple: the broadcast source node sends the message to the CH, which stores the ID of the message and broadcasts it to the one-hop neighborhood. After that, it sends it to all nearby CHs by multihop unicast. The inter-cluster destination nodes repeat the procedure except that the message source clusters are omitted from further forwarding. Additionally, the information about the ID of the broadcast messages and their sources is stored for a given period of time to avoid superfluous re-sending of the message.

OLSR

The Optimized Link State Routing Protocol (OLSR) [START_REF]Optimized link state routing protocol (olsr)[END_REF] is a well known routing protocol designed for ad hoc networks. It is a proactive protocol; hence it periodically exchanges topology information with other nodes of the network. One-hop neighborhood and two-hop neighborhood are discovered using Hello Messages (similar to beacons). The multipoint relay (MPR) nodes are calculated by selecting the smallest one-hop neighborhood set needed to reach every two-hop neighbor node. The topology control information is only forwarded by the nodes which are selected as MPR. Every node then has a routing table containing the shortest path to every node of the network. OLSR enables optimized flooding of the network by building a tree-like topology for every node from a source (Figure 3). Therefore, MPR selection constructs an optimal connected dominating set [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF]. For this reason OLSR is our benchmark reference in Section 4.

Related Work

In ad hoc networks forwarding strategies should be employed to avoid broadcast storms (i.e. a message forwarded by all the nodes in the network). As depicted in [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF], broadcast storms can be counter-measured using several schemes i.e. probabilistic, counter-based, distance-based, location-based and cluster-based. We use the latter scheme, cluster-based, since it is the only one based on network topology information. The cluster architecture we use solely relies on locally available information whereas [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF] proposes a clustering technique where the CH is elected after an explicit message exchange among the neighbors.

The Zone Routing Protocol (ZRP) [START_REF] Haas | The zone routing protocol (zrp) for ad hoc networks[END_REF] combines proactive routing inside a zone using bordercast and on-demand routing outside. A node, sending a message, checks if the destination is in its zone, if not it bordercasts the message to its gateway nodes. Those nodes repeat the same process until the destination is reached. As every zone is centered on the current node the ZRP dissemination results in plain bordercasting a message ahead its destination. To route inside a zone, ZRP needs k-hop information (k>1), which results in scalability issues similar to OLSR.

In [START_REF] Foroozan | A high performance cluster-based broadcasting algorithm for wireless ad hoc networks based on a novel gateway selection approach[END_REF], the authors construct elected clusters based on beacon information which provides the number of neighbors and their stability represented by the number of beacons received. This approach is similar to NLWCA but does not rely on both a link weight and a node weight. Thus NLWCA has more flexibility in terms of cluster selection. Another similarity to our approach is the forwarding node selection (named gateway selection). The main differences is that our approach requires no message exchange except the payload broadcast itself for gateway selection. The comparison will not be further analyzed since to our knowledge the gateway selection process is insufficiently described.

Many ad hoc protocols use the selection of forwarding nodes to reduce redundant messages. In [START_REF] Peng | Ahbp: An efficient broadcast protocol for mobile ad hoc networks[END_REF] and [START_REF] Lou | Double-covered broadcast (dcb): a simple reliable broadcast algorithm in manets[END_REF] broadcast relay gateways are selected with 2-hop knowledge. However we chose the already described OLSR protocol because of its popularity in ad hoc networks and Mesh networks, and also because it is the only one proved to optimize coverage of 2-hop nodes through MPRs [START_REF]Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models[END_REF]. MPRs build optimal connected dominating sets [START_REF] Adjih | Computing connected dominated sets with multipoint relays[END_REF]. We take advantage of this property to build paths among the (not-connected) dominating sets built by the NLWCA clustering algorithm. Many other approaches that construct distributed connected dominating sets exist [START_REF] Wu | On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks[END_REF][START_REF] Blum | Connected dominating set in sensor networks and manets[END_REF]. However, our goal is not to create connected dominating sets, but to disseminate information over the stable structure built by NLWCA, using ICRs between the CHs to optimize nearby-cluster-paths. Thus, as a result of our structure, we have connected dominating sets, but only between a CH and its nearby CHs.

SLSF

NLWCA and WCPD provide a stable-connected cluster architecture, however the broadcasting algorithm of WCPD needs many improvement on reachability performances compared to OLSR which performs very well on reachability but lacks in scalability and uses a lot of bandwidth [START_REF] Leclerc | Olsr and wcpd as basis for service discovery in manets[END_REF]. Our SLSF (Stable Linked Structure Flooding) protocol replaces the inefficient broadcasting mechanism of WCPD with the ICR mechanism. SLSF combines the advantages of all the protocols NLWCA, WCPD and OLSR: scalability, stability, reachability, while keeping the drawbacks low (i.e. the bandwidth usage). SLSF forms a first level of hierarchy with a dominating set using NLWCA. Considering the dominant nodes of the underlying level (NLWCA), it forms an optimal connected dominating set with the ICR mechanism. The first level reduces the network to its dominant nodes and the second level insures shortest-path connectivity and minimal relay nodes among dominant nodes of the first level.

SLSF -Inter-Cluster Relay

Multiple paths to reach a given CH requires choosing one path prior to another. We use a next-hop selection inspired by the MultiPoint Relay (MPR) mechanism of OLSR to select the forwarding neighbors. We name Inter-Cluster-Relays (ICR) the nodes selected as next-hop. The goal of ICR is to reach all nearby CHs with the minimal set of 1-hop neighbors while optimizing the hop-count. The ICR nodes are calculated by selecting the smallest one-hop neighborhood set (directly connected nodes) needed to reach every nearby CH. ICR selection remains straightforward because the possible inter-cluster configurations are restricted by the underlying one-hop cluster topology (examples on Figure 6). SLSF, on top of NLWCA, discovers the nearby clusters (similar to WCPD) by reading the neighbor beacons. The improvement and novelty relies on the ICR selection which avoids superfluous network communication overhead without any additional message exchange. SLSF keeps the last beacon of every onehop neighbor in cache. Hence every node has the following information locally available about each stable 1-hop neighbor: its weigth, its CH ID, the ID set of discovered CHs and their respective path length. ICR selection occurs as follows:

i. Select as ICR, neighbors that are the only one reaching a given nearby CH. ii. Remove the now covered clusters from the list. iii. Remove for every neighbor from the announced CH-list the entries with a worse hop count than the best one (i.e. keep only shortest path entries).

1. Calculate the cluster reachability for every one-hop neighbor (i.e. number of foreign CHs the neighbor announces in its beacon). 2. Select the neighbor with the best reachability. 3. Else if equivalent: select the neighbor with the highest weight. 4. Else if equivalent: select the node with the biggest IP address. 5. Remove the now covered clusters from the list. 6. While there is a not-covered CH, go back to 1.

3-hop Inter-cluster case. NLWCA builds one-hop clusters, thus it permits up to three hops (two slave nodes) between CHs. ICR selection with two hops (one slave node) between CHs (Figure 6b) is straight selection by the CH, however an additional hop (Figure 6d) requires additional attention.

A further hop involves an additional forward of the message to reach the nearby CH. For example on Figure 6d, the source CH2 designates a node as ICR (here the blue slave neighbor of CH2). The designated ICR has to make a choice between one of the two (orange) slaves of CH1. This choice is computed by using ICR selection using the list containing only 1 hop distant(from the blue slave: here the orange CH) clusterheads.

When to select ICR nodes? ICR selection is done based on events. Every time a change in the stable neighborhood that influences the ICR calculation occurs, the ICR selection is re-calculated. Thus broadcasting or forwarding a message using ICRs is immediate: replace the ICR set in the message with the one locally pre-calculated. Further detail on broadcasting in SLSF in section 3.2.

ICR:

The big picture. To highlight the gain of ICR selection, Figure 4 shows an example with 5 clusters where the message source CH S sends a broadcast. The broadcast of S will have the format shown on figure 5.

On reception of this broadcast only nodes 1, 2 and 3 will forward the message, while the other neighboring nodes process the message silently. Note that node 1 selects 4 and 5 as ICR according to section 3.1 "3-hop Inter-cluster case". We see that ICR selection reduces a lot the number of forwarding nodes. As an example, on Figure 4 there are 23 nodes in the network and only 10 nodes (including the CHs) are emitting to reach all the nodes in the network. Every CH will emit the message once in order for their slave to receive it and if necessary include their local ICR selection for further forwarding in the network (see section 3.2). In comparison, there would be 15 nodes forwarding the message using OLSR. This is due to OLSR using only 2-hop information while SLSF uses 1-hop cluster information which represent information from up to 3-hops away. While 3-hop knowledge usually increases the amount of information to collect using clusters reduces drastically the nodes to keep track of for ICR selection.

SLSF -Broadcast

At this point, every communication occurs between one cluster and its nearby clusters. To enable communication with foreign clusters, we propose a simple broadcast mechanism. A more sophisticated foreign cluster-broadcast mechanism would be out of scope for this paper.

Our broadcast mechanism is simple now that we only need to deal at cluster level. A node willing to broadcast a message through the network will, unless it is its own CH, send it to its CH. The original message contains the source address, a corresponding sequence number and of course the payload data. The CH puts its own address as last crossed CH and adds a corresponding sequence number to the message. Finally it forwards it to all its nearby CHs using the ICR mechanism. On reception the nearby CHs replace the last crossed CH address with their own and replace the corresponding sequence number. The ICR (excluding from selection the cluster the message came from) set is also updated. To avoid superfluous re-sending of the message SLSF stores information about the ID of messages and their sources for a given period of time.

As an example, on Figure 7 the node 1 sends a message passing (as 1 is a slave) the message to CH9, which then uses the ICR mechanism for the dissemination. Note that node 7 is in the "3-hop inter-cluster case" (section 3.1). The message reaches all the nodes in the network following the path depicted on Figure 8.

SLSF -Fault-recovery

The goal of fault-recovery is to be able to transmit the message even if the ICR path fails without having the source to re-emit the message. To do so we propose two mechanisms, the first is the acknowledgement mechanism, enabling broadcasts to be acknowledged by nearby CHs and the second is the delayed transmission detecting transmission errors and handling them.

Acknowledgment mechanism

The following acknowledgement mechanism has two advantages. The first, for which it was actually designed, is permitting a delayed transmission to compensate local intermittent node failures. The second is classic acknowledgment of messages but only between adjacent CHs as opposed to acknowledgements from one end of the network to the other. The classic cluster-to-cluster acknowledgement is a consequence of the initial design. Further consideration of end-to-end acknowledgements would be out of scope for this paper but is an open interest for future work.

Our acknowledgement mechanism works using sequence numbers. Every node puts inside its beacon sequence numbers to acknowledge messages. However, only CHs acknowledge the messages while inter-cluster nodes forward merely the acknowledgement information coming from nearby CHs to their neighborhood. As consequence, beacons of CHs have a different format than inter-cluster node beacons. Following is an example illustrating how the acknowledgement mechanism works. Using Figure 1 as reference, we suppose node 9 sends a broadcast with sequence number N9. Nodes 1, 2 and 3 receive the message. Only node 3 will forward it to its neighborhood as it is designated ICR, since it is the only inter-cluster node. Node 1 and 2 process silently the message without forwarding it. CH8 receives the message from node 3, processes the messages, and puts in its beacon the acknowledged sequence number N9 for CH9. Beacon of CH8 contains now its weight, its CH-address (here its own), its nearby CHs with the corresponding hop count and the acknowledged sequence number. So, the SLSF beacon (Figure 9a) is only extended with one sequence number (Figure 9b).

Node 3 reads the CH8 beacon (Figure 9b) and includes in its beacon the new sequence number acknowledged by CH8 for the message source CH9. In order to reduce the beacon size for inter-cluster nodes, we compact acknowledgment information into the basic SLSF beacon by just adding sequence numbers in the right order and place. If we consider the basic SLSF beacon (Figure 10a) for the slave node 3 we integrate additionally inside the beacon the information that CH8 acknowledges sequence number N9 for CH9 and that CH9 acknowledges N8 for CH8 (Figure 10b). Note the inversion of the sequence numbers compared to the beacon of CH 8.

To really point out this inversion an example where three nearby clusters are inter-connected is necessary (Figure 11).In this example, node 3 is connected to three clusters. As a matter of fact, node 3 will forward any message exchange between those clusters. The beacon of node 3 has to contain all the acknowledgement information for the three CHs. The basic SLSF beacon of node 3 of Figure 11 is shown in Figure 12. Node 3's beacon contains its own clusterhead, CH5, and two nearby CHs, CH1 and CH6, on 1 and 2 hop distance respectively. Now we consider we want the following information into that beacon, like for instance after some broadcasts were sent (Nx corresponds to the acknowledged sequence number): CH1 acknowledges N5 for CH5 and N6 for CH 6 ⇔ CH1=[CH5/N5, CH6/N6] CH5 acknowledges N1 for CH1 and N6 for CH 6 ⇔ CH5=[CH1/N1, CH6/N6] CH6 acknowledges N5 for CH5 and N1 for CH 1 ⇔ CH6=[CH5/N5, CH1/N1] The original SLSF beacon already contains the three CH-addresses (typically the IP addresses of the CHs); the own CH-address and two nearby CH-addresses. First sort all the acknowledgements CH-addresses in ascending order. For example CH6=[CH5/N5, CH1/N1] is sorted as CH6=[CH1/N1, CH5/N5]. For each CH-address in the beacon attach the corresponding sequence numbers and omit the superfluous CH-addresses inside the list, as shown on Figure 13. Doing so, putting in the right order the right sequence numbers, results in a new beacon with all the needed information just by adding the needed sequence numbers without additional addresses.

The constructed beacon (Figure 13) is received by the neighbors. For instance CH1 can reads in the beacon [N5,N6] and by ordering the announced CHs (CH1, CH5, CH6) and omitting itself (CH5, CH6) it can read that CH5 acknowledges N5 and CH6 acknowledges N6.

The presented acknowledgement mechanism permits acknowledgements between a cluster and its nearby clusters. While the acknowledgements of the CHs using beacons are straightforward, the inter-cluster beacons of the nodes are constructed using inversion and re-ordering to avoid redundant information inside the beacon and still enabling the source cluster to distinguish which cluster acknowledges which messages without any other message exchange than beacons.

Delayed transmission mechanism

The ICR selection enables the communication among nearby clusters in an optimized way. To keep the inter-cluster communication reliable in case the selected ICR path failed, we introduce a delayed transmission mechanism. Thus, we have an immediate communication path formed by the ICRs and we keep a backup, although delayed, path in case of failures.

Delayed transmission occurs as follows: If a broadcasted message is emitted from a source, all neighbor nodes NOT selected as ICR in the message will keep the message in cache and only in case of a failure transmit the message. While the ICR nodes forward the messages, the nodes pending for delayed transmission observe the neighboring beacons for acknowledgements of nearby CHs. On reception of a pending acknowledgement, the delayed transmission is aborted. If the pending time for delayed transmission times out, the message is broadcasted to all neighbors with the retransmitted flag set. Nodes that already received the message will discard it silently while others forward it immediately. The message arrives at destination in case of failure without re-emission of the message from the source. Thus, having only nodes that did not try forwarding the message yet, effectively (re)transmitting the message.

Following discusses the delay chosen for timeout to occur. If we consider the beacon-interval as bI, the number of nodes the message already passed through as hopCount and 4 the maximal number of hops for a message to go back and forth from the first slave to a cluster on (maximal) 2-hop distance. Then the transmission delay td is calculated as follows: td = ( 4 hopCount )×bI. If the beaconinterval is 1 second and the hopcount is 1 then the transmission delay is set to 4 seconds. If the hopcount is 2 then the transmission delay is set to 2 seconds.

Simulation & Results

To evaluate the performances of our SLSF protocol, we implemented the three protocols (OLSR, NLWCA/WCPD and SLSF) on top of the JANE simulator [START_REF] Gorgen | Jane-the java ad hoc network development environment[END_REF] and performed several simulations. For those experiments we used the Restricted Random Way Point mobility model [START_REF] Blažević | Self organized terminode routing[END_REF], whereby the devices move along defined streets on the map of Luxembourg City for 1000 seconds. For each device the speed was randomly varied between [0.5;1.5] units/s with a transmission range of 25 units. For each experiment 10 different random distribution seeds were used in order to feature results from different topologies and movement setups. For the used mobile environment where nodes move with low (walking) speeds between 1.8 and 5.4 km/h the NLWCA link-stability threshold is set on 2 [START_REF] Andronache | Nlwca node and link weighted clustering algorithm for backbone-assisted mobile ad hoc networks[END_REF].

Simulations were done to determine the bandwidth used by the protocols in order to build the topologies and the information dissemination performance of broadcasting on top of the different topologies. Then we compared the efficiency of the protocols and finally made a static evaluation to compare information dissemination solely on MPR and ICR performances.

OLSR exchanges the sets of one-hop neighbor nodes with every node in communication range. Similar to OLSR, SLSF exchanges the list of the discovered nearby-CHs with the one-hop neighbor nodes. For our experiments we distinguished two different SLSF configurations. the first is SLSF without fault recovery referred as SLSF-R (minus fault recovery), thus only ICR selection with basic SLSF beacon (same format as the WCPD beacon, thus same bandwidth usage). The second is the full SLSF protocol with ICR selection and fault-recovery mechanism with added sequence numbers in the beacon. To find out the network load produced during this phase, the size of the exchanged data sets were tracked every second of the simulation: for OLSR the size of the one-hop neighbor sets, for SLSF-R and WCPD the size of the discovered CHs and for SLSF additionally to the discovered CHs the sequence numbers.

In order to monitor the information dissemination performance (Reachability) a node was chosen to broadcast a message every 10 seconds during different simulation runs. The number of sent messages (i.e. broadcasts and unicasts) during the dissemination and the number of reached network nodes were tracked.

As shown in Figure 14, OLSR uses a higher bandwidth in both sparser (100 nodes) and denser networks (300 nodes). This was expected since OLSR is exchanging the set of one-hop neighbors, while SLSF only exchanges the set of locally discovered nearby CHs which is a fractional amount of the total number of nodes. SLSF-R uses exactly the same bandwidth (80% less than OLSR) as WCPD since they share the same beacon structure. SLSF uses more bandwidth than SLSF-R, as sequence numbers were added to the beacon, but still uses about 40% less bandwidth than OLSR. The dissemination performance results (Figure 15, NOTE: periodicity in curves is induced by the smoothing) show that SLSF performs the best for all densities. For 300 nodes SLSF performs only slightly better than OLSR, but uses on average 10 to 15% less forwarders with 40% less bandwidth usage. WCPD performs the worst and uses accordingly lesser forwarding nodes. Whereas SLSF-R uses approximately the same amount of forwarders than WCPD, it reaches from 10% to 20% more nodes. This is the pure gain of ICR selection which optimizes the forwarding nodes.

Subsequently we calculated a "quality-cost" ratio extracted from the results of Figures 14 and15. We calculated the percentage of nodes reached, divided by the bandwidth used. We see in Figure 16 that SLSF and SLSF-R are in average two to three times more efficient than OLSR. The poor performances of WCPD highlight the need for improvement that SLSF brings.

SLSF relies on stable structures built by NLWCA: only nodes considered as stable will receive the message. So finally, to compare the performances on equal levels, we experimented OLSR and SLSF in a static scenario where all nodes are considered stable connected. The experiments where done on a 300x300 units surface with 100 to 300 nodes randomly positioned using 100 different topology seeds. Again, the number of forwarding and receiving nodes using MPR and ICR selection where tracked. The results on Figure 17 show that SLSF outperforms OLSR in terms of ratio of forwarding nodes over receiving nodes. With increasing density on average with OLSR about 85% of the receivers are also forwarders, whereas in SLSF this amount decreases from 60% towards 30%.

Conclusion & Future Work

This paper proposes SLSF, a flooding protocol which selects Inter-Cluster Relays to optimize the communication among the stable-connected cluster architecture. To deal with intermittent message loss we added a fault recovery mechanism that can be selectively enabled on a per-packet basis.

The goal of the ICR (Inter-Cluster Relay) selection is to reach all nearby clusterheads with the minimal set of 1-hop neighbors while optimizing the hopcount. ICR selection on top of the stable-cluster architecture reduces substan-tially the number of forwarding nodes. Generally, SLSF performs well in high density networks while keeping the used bandwidth very low.

Currently we consider using SLSF as basis for Zerconf [19] (a service discovery protocol) in simulation and real world experiments.

As future work we plan to evaluate the performances using various mobility models and topology settings and also assess the results, in the context of the French National Research Project SARAH, deploying a large scale ad hoc network inside a museum.

Fig. 1 .

 1 Fig. 1. Example of two clusters built by NLWCA.

Fig. 2 .

 2 Fig. 2. NLWCA+WCPD Beacon. Fig. 3. OLSR topology from one source.

Fig. 4 .

 4 Fig. 4. ICR selection with 5 clusters.

Fig. 5 .

 5 Fig. 5. Format of a broadcast message with payload.

Fig. 6 .

 6 Fig. 6. Inter-cluster configuration examples where 1 and 2 are clusterheads.

Fig. 7 .

 7 Fig. 7. Foreign-cluster broadcast -Format of a message sent from node 1.

Fig. 8 .

 8 Fig. 8. Foreign-cluster broadcast -Path of a message sent from node 1.

Fig. 9 .

 9 Fig. 9. CH8 Beacon: (a)SLSF, (b)SLSF with fault recovery.

Fig. 10 .

 10 Fig. 10. Node 3 Beacon: (a)SLSF, (b)SLSF with fault recovery.

Fig. 11 .

 11 Fig. 11. Three clusters example.

Fig. 12 .

 12 Fig. 12. Node 3 SLSF beacon.

Fig. 13 .

 13 Fig. 13. Node 3 SLSF beacon with fault recovery .

Fig. 14 .Fig. 15 .

 1415 Fig. 14. Bandwidth used in order to build the topology for 100, 200 and 300 nodes Fig. 15. Overall number of sent messages and node receivers for 100 and 300 nodes. (smoothed with a polynomial equation of the 16th grade for visibility sake).

Fig. 16 .

 16 Fig. 16. Efficiency of Bandwidth usage for 100 and 300 nodes Fig. 17. Static scenario with 100 to 300 nodes

.

  Fig. 17. Static scenario with 100 to 300 nodes