Sungeun Lee

Jackson W Sorensen

Robin L Walker

Joanne B Emerson

Graeme W Nicol

Christina Hazard
email: christina.hazard@ec-lyon.fr

Soil viral communities are structured by pH at local and global scales Running title: Viral communities are structured by soil pH

Viruses shape microbial community structures, impacting metabolic pathways and influencing biogeochemical cycles. Despite their importance, the influence of biotic and abiotic factors on viral community structures across environmental gradients in soil is relatively unknown compared to their prokaryotic hosts.

While soil pH strongly influences microbial community structure, it is unclear whether there is a similar influence on soil virus communities. In this study, prokaryotic and viral communities were characterized in soils sampled from the extremes of a long-term pH-manipulated soil gradient (pH 4.5 and 7.5), and viral populations were compared to those in a variety of soil ecosystems ranging in pH (4.0 -7.5). Prokaryotic and viral community structure were significantly influenced by soil pH at the local scale. Of 1,910 viral operational taxonomic units (vOTUs), 99% were restricted to pH 4.5 or 7.5 soil only. These were compared in gene sharing networks of populations from six other European and North American soil systems. A selection of viral clusters from acidic and neutral pH soils were more associated with those from the local gradient pH 4.5 or 7.5 soils, respectively. Results indicate that as with prokaryotes, soil pH is a factor structuring viral communities at the local and global scale.

Main

Viruses play a major role in controlling the abundance, structure and evolution of microbial communities through cell lysis and the release of nutrients and modulation of host cell metabolism during infection [START_REF] Pratama | The 'neglected' soil virome -potential role and impact[END_REF]. In soils, viruses are diverse [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF] and abundant [START_REF] Williamson | Viruses in Soil Ecosystems: An Unknown Quantity Within an Unexplored Territory[END_REF], likely infect the majority of bacteria and archaea, and have considerable potential to impact carbon sequestration, nutrient cycling and other ecosystem functions [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF][START_REF] Kuzyakov | Viruses in soil: Nano-scale undead drivers of microbial life, biogeochemical turnover and ecosystem functions[END_REF][START_REF] Trubl | Soil viruses are underexplored players in ecosystem carbon processing[END_REF]. Amongst the many knowledge gaps in soil viral ecology includes a basic understanding of the biotic and abiotic drivers of viral communities at both the local and global scale.

Host communities are likely the strongest factor for defining viral community structures with virus populations derived from infection of susceptible hosts. As with other environments, soil bacterial and viral community dynamics co-vary, with the susceptibility of hosts to infection from individual viruses varying over time [START_REF] Vos | Local adaptation of bacteriophages to their bacterial hosts in soil[END_REF] or viral community shifts occurring as an indirect result of nutrient input altering host community structure [7]. While the presence of specific hosts will influence the composition of virus communities, the host range of viruses may also play a role in defining whether their community dynamics vary to the same extent as prokaryotic communities over physicochemical gradients in soil [8]. Closely related host populations (e.g. of the same genus) may be adapted to growth under different conditions, resulting in niche differentiation and contrasting distribution across an ecological gradient (e.g. pH), but it is unclear whether narrow (e.g. single population) or broad (genus to phylum) host ranges of their associated viruses reduce the relative variation in virus community structure compared to prokaryotes. In addition, changes in soil physicochemical characteristics such as pH, temperature and moisture, may also directly impact the physical integrity and dispersal of viruses [9]. As soil pH is a major determinant of prokaryotic community structures at local and global scales [10,[START_REF] Ren | Identifying viruses from metagenomic data using deep learning[END_REF][START_REF] Paez-Espino | Nontargeted virus sequence discovery pipeline and virus clustering for metagenomic data[END_REF], it is possible that virus communities may also exhibit pH-influenced community structures at similar scales.

To examine the effect of soil pH on double-stranded DNA virus community structure at a local scale, triplicate soil samples were taken from pH 4.5 and 7.5 subplots of a well-characterized soil pH gradient. At this site, prokaryotic community structure has been shown to vary in response to pH [START_REF] Bushnell | BBTools software package[END_REF][START_REF] Roux | Minimum Information about an Uncultivated Virus Genome (MIUViG)[END_REF], and distinct virus populations infecting methylotrophic communities associated with contrasting soil pH have recently been observed [START_REF] Jang | Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by genesharing networks[END_REF]. Both nontargeted total community metagenome and virus-targeted virome libraries were prepared as previously described [START_REF] Jang | Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by genesharing networks[END_REF] for comparing prokaryotic and viral community structures. From all six soil samples, 908 and 763 million qualityfiltered metagenome and virome reads were obtained, respectively, with 9,928 metagenome and 13,533 virome contigs ≥10 kb produced after assembly. Of these, 105 and 7,684 contigs were predicted to be of viral origin from metagenomes and viromes, respectively, and clustered into 1,910 viral operational taxonomic units (vOTUs) (Supplementary Methods; Table S1). For characterizing prokaryotic community structures, reads were annotated and prokaryotic 16S rRNA gene fragments were extracted and classified into 2,312 OTUs (Supplementary Methods). Sequencing depth of each sample and sampling size of pH 4.5 and 7.5 soil was sufficient to capture vOTU richness, although further sequencing and sampling may have increased the number of 16S rRNA OTUs recovered (Fig. S1).

Of the metagenomic reads, 22.7% were taxonomically defined, with Actinobacteria (pH 4.5, 48 ± 1.5% (standard deviation); pH 7.5, 39 ± 0.5%) and Proteobacteria (pH 4.5, 27 ± 0.5%; pH 7.5, 33 ± 0.2%) dominating in both pH soils (Fig. 1a). Similar to other soil viral studies, only a small proportion of the prokaryotic viral community was taxonomically defined. Using a gene-sharing network [START_REF] Bland | CRISPR Recognition Tool (CRT): a tool for automatic detection of clustered regularly interspaced palindromic repeats[END_REF], 1.4% of viral contigs (7.0% of vOTUs) clustered with RefSeq genomes of Siphoviridae, Podoviridae and Myoviridae (Fig. 1a). Prokaryote hosts associated with viral contigs were predicted using both gene-sharing network and host-virus shared gene homology [START_REF] Shen | SeqKit: A Cross-Platform and Ultrafast Toolkit for FASTA/Q File Manipulation[END_REF], linking a total of 24.5% of viral contigs (29.1% of vOTUs) (Table S2). Consistent with the dominant prokaryotic taxa, the majority of predicted viral hosts for both pH soils were Actinobacteria (pH 4.5, 76.9 ± 0.003%; pH 7.5, 64.6 ± 0.002%) and Proteobacteria (pH 4.5, 18.5 ± 0.003%; pH 7.5, 30.2 ± 0.001%) (Fig. 1a and Table S2).

A high resolution analysis of the distribution of individual 16S rRNA

OTUs and vOTUs demonstrated distinct structures between pH 4.5. and 7.5 soils for both prokaryote and viral communities (Fig. 1b). Specifically, 38.6% of OTUs (pH 4.5 OTUs, 263; pH 7.5 OTUs, 630) and 99.0% of the vOTUs (pH 4.5 vOTUs, 524; pH 7.5 vOTUs, 1,361) were found in only one soil pH. While no significant differences in prokaryote alpha-diversity (Shannon, Simpson and richness) were observed, viral (virome) alpha-diversity was significantly greater in pH 7.5 compared to pH 4.5 soil (Student's t-test, p value <0.05) (Table S3).

As absorption of viruses to soil organic particles may decrease with increasing pH [START_REF] Al-Shayeb | Clades of huge phages from across Earth's ecosystems[END_REF], this could have contributed to the observed differences in alphadiversity despite a neutral pH buffer being used for extracting viral particles in both soils. Interestingly, the relative proportions of virus-encoded putative auxiliary metabolic genes (AMGs) identified in vOTUs were similar in both pH soils, indicating that pH did not select for distinct AMG composition across this pH gradient (Fig. S2).

While viromes produced 73x more assembled viral contigs than metagenomes, read mapping of individual virome and metagenome reads to all vOTUs demonstrated that both approaches produced distinct viral community profiles between soils (Fig. 1b). Interestingly, decreasing the breadth (length of contig covered by mapped reads) threshold (<75%) for defining vOTU detection disproportionately increased vOTU detection in metagenomes compared to viromes (Fig. S3). This suggests that the appropriate breadth thresholds for detection may be different in viromes compared to total metagenomes, with a cut-off ≥75% potentially too conservative for the total metagenomes. However, care should be taken before reducing breadth threshold in other datasets that do not have paired viromes to corroborate viral detection. Regardless, the same pH trends were observed for both viromes and metagenomes.

The distinct soil viromes from the gradient pH 4.5. and 7.5 soils were compared with those recovered from six other soil ecosystems varying in pH, soil type, land use and location and where viral contigs were predicted using the same tools and community standards (Table S4) [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF][START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF][START_REF] Kieft | VIBRANT: automated recovery, annotation and curation of microbial viruses, and evaluation of viral community function from genomic sequences[END_REF]. Specifically, using gene-sharing network analysis [START_REF] Kieft | VIBRANT: automated recovery, annotation and curation of microbial viruses, and evaluation of viral community function from genomic sequences[END_REF], the number of clusters containing vOTUs from these additional soils and the local gradient (pH 4.5 only, pH 7.5 only or both) were determined (Fig. 2, Table S5). On average, 31% of clusters were shared (range 1-62%) in pairwise comparisons between all soils (Fig. S4).

A clear trend was observed in comparison with the gradient soils (Fig. 2b) with shared viral clusters in acidic and neutral pH soils more associated with those from the local gradient pH 4.5 or 7.5 soils, respectively.

If individual viruses can infect multiple host populations at different soil pH, there would be a potential for virus community structures to be less distinct over an ecological gradient. However, analysis of samples from a continuous pH gradient demonstrated that, as with prokaryotic community structure, contrasting soil pH results in the selection for virus community structures that are at least as distinct as prokaryote host community structures. Comparison with soil samples of contrasting pH and land-use type also indicated that, as with prokaryote host communities, soil pH correlates with distinct patterns of virus community structures. For virus communities, reads from both viromes (V) and metagenomes (M)

were analyzed for each sample. Details of all methods used are provided in Supplementary Information.

Supplementary Information

Table of contents: 1. Supplementary Methods

Soil sampling, preparation and analysis of metagenome libraries

Virus prediction and community profiling

Virus-host linkage

Auxiliary metabolic genes

Statistical analyses

Network analysis of soil viral populations from various soil systems

Supplementary Tables and Figures

Supplementary References 1. Supplementary Methods

Soil sampling, preparation and analysis of metagenome libraries

Soil was collected from pH 4.5 and 7.5 subplots of a pH gradient that has been maintained since 1961 under an 8-year crop rotation (SRUC, Craibstone Estate, Aberdeen, Scotland; UK grid reference NJ872104) [START_REF] Pratama | The 'neglected' soil virome -potential role and impact[END_REF]. The soil is a podzol with sandy-loam texture and had supported the growth of potatoes the previous year. Three replicate soil samples were collected from the top 10 cm at 1 m intervals in January 2019. Soil pH (measured in water) were 4.2 ± 0.06 and 7.3 ± 0.04 for the pH 4.5 and 7.5 subplots respectively. Soil was sieved (2 mm mesh size) and stored at 4°C (<1 week) prior to preparing total soil metagenomes and viromes generated as previously described [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF]. For nontargeted metagenomes, genomic DNA was extracted from 0.5 g soil using a CTAB buffer phenol:chloroform: isoamyl alcohol bead-beating protocol [START_REF] Williamson | Viruses in Soil Ecosystems: An Unknown Quantity Within an Unexplored Territory[END_REF].

DNA from virus particles was extracted with the protocol of Trubl et al. [START_REF] Kuzyakov | Viruses in soil: Nano-scale undead drivers of microbial life, biogeochemical turnover and ecosystem functions[END_REF] with modifications (see [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF]). Library preparation and sequencing was performed at the Joint Genome Institute (JGI) as previously described [START_REF] Emerson | Host-linked soil viral ecology along a permafrost thaw gradient[END_REF]. De novo contig assembly of 125 to 322 million quality-controlled reads per metagenome (both non-targeted and virome) was performed using MetaSPAdes version 3.13.0 [START_REF] Trubl | Soil viruses are underexplored players in ecosystem carbon processing[END_REF].

Taxonomic annotation of metagenomic reads was performed using Kaiju version 1.7.0 [START_REF] Vos | Local adaptation of bacteriophages to their bacterial hosts in soil[END_REF] with the NCBI nr database (2020-05-25 release) for prokaryote phylum annotation. 16S rRNA gene fragments were extracted and classified from the non-targeted metagenomes using SortMeRNA [7] with the bacterial and archaeal SILVA database. The OTU map files obtained from SortMeRNA were converted to an OTU table using the make_otu_table.py function in QIIME (1.3.0 release) [8]. A heatmap of the relative abundance of OTUs was produced using the heatmaply R package [9] in R v3.6.0

Virus prediction and community profiling

Contigs of viral origin were predicted from contigs ≥10 kb from both nontargeted and virome metagenomes using VirSorter [10] and DeepVirFinder [START_REF] Ren | Identifying viruses from metagenomic data using deep learning[END_REF]. For VirSorter analysis, category-1 and -2 free virus categories were retained (representing "most confident" and "likely" virus predictions, respectively) together with category-4 and -5 prophage equivalents. For DeepVirFinder, contigs categorized with a score ≥0.9 and p-value ≤0.05 (representing "confident" virus predictions) [START_REF] Ren | Identifying viruses from metagenomic data using deep learning[END_REF] were retained. Viral contigs were clustered into virus operational taxonomic units (vOTUs) with self-hits of viral contigs from BLASTn analysis (e-value ≤1.0e-50, perc_identity ≥80) removed, and the output file parsed using specific cutoffs (global identity ≥95%, covered length ≥80% of the shorter contig; [START_REF] Paez-Espino | Nontargeted virus sequence discovery pipeline and virus clustering for metagenomic data[END_REF]) by using the command java Parse_BLAST [START_REF] Paez-Espino | Nontargeted virus sequence discovery pipeline and virus clustering for metagenomic data[END_REF]. Single linkage clustering was performed using the command SLC.pl. [START_REF] Paez-Espino | Nontargeted virus sequence discovery pipeline and virus clustering for metagenomic data[END_REF]. To determine the relative abundance of vOTUs, BBMap [START_REF] Bushnell | BBTools software package[END_REF] was used to align reads from each metagenome and virome back to indexed vOTUs with the detection threshold of ≥75% of the contig length, covered ≥1x by reads recruited at ≥90% average nucleotide identity [START_REF] Roux | Minimum Information about an Uncultivated Virus Genome (MIUViG)[END_REF]. The relative abundance of each vOTU in each metagenome and virome was calculated based on the length of sequence size and coverage. Abundance was expressed as normalized copies per million reads (CPM). This was calculated as follows: the read per kilobase (RPK) was divided by sequencelength (kb), RPK were summed and divided by 1 million to get a scaling factor, and RPK values were divided by the scaling factor to get the CPM. A heatmap of the relative abundance of vOTUs was produced using the heatmaply R package [9] in R v3.6.0. Taxonomic annotation of viral contigs and vOTUs was performed using vConTACT 2.0 [START_REF] Jang | Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by genesharing networks[END_REF] with the RefSeq prokaryote virus database (Release 94; 2019-05-13).

Virus-host linkage

Three approaches were used to predict virus-host linkages; linking viral protospacer and spacer sequences in clustered regularly interspaced short palindromic repeats (CRISPR) arrays, analysis of shared homologs between host and viral contigs, and gene-sharing network analysis. The CRISPR Recognition Tool (CRT) [START_REF] Bland | CRISPR Recognition Tool (CRT): a tool for automatic detection of clustered regularly interspaced palindromic repeats[END_REF] was used to identify CRISPR arrays from the metagenomes and spacer sequences were extracted using line commands and searched in vOTUs using the Seqkit locate function with 100% sequence identity and positive and negative strand search [START_REF] Shen | SeqKit: A Cross-Platform and Ultrafast Toolkit for FASTA/Q File Manipulation[END_REF]. However, as only two spacers were identified with exact matches to viral contigs, this approach was not considered further. A homolog-based approach was performed as previously described [START_REF] Al-Shayeb | Clades of huge phages from across Earth's ecosystems[END_REF] with a host predicted as the phylum with ≥ 3x shared homologs compared to the second most dominant phylum. Gene-sharing network analysis was conducted using vConTACT 2.0 [START_REF] Jang | Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by genesharing networks[END_REF] with the RefSeq prokaryote virus database (Release 94; 2019-05-13).

Auxiliary metabolic genes

To identify putative virus-encoded auxiliary metabolic genes (AMGs), gene prediction of vOTU contigs was performed using Prodigal v2.6.3 with meta option [START_REF] Hyatt | Prodigal: prokaryotic gene recognition and translation initiation site identification[END_REF], and putative AMG searches were conducted using VIBRANT [START_REF] Kieft | VIBRANT: automated recovery, annotation and curation of microbial viruses, and evaluation of viral community function from genomic sequences[END_REF] and DRAM-v [START_REF] Shaffer | DRAM for distilling microbial metabolism to automate the curation of microbiome function[END_REF], with all vOTUs passed to VirSorter2 using "--prep-for-dramv", and using a minimum auxiliary score threshold of 3 [START_REF] Guo | VirSorter2: a multi-classifier, expert-guided approach to detect diverse DNA and RNA viruses[END_REF]. AMGs predicted by both tools were manually curated. Putative AMGs at the end of contigs and annotated with multiple functional categories were removed. AMGs predicted using either VIBRANT and DRAM-v were categorized into 14 functional metabolism categories and visualized in a heatmap produced through the heatmaply R package [9] in R v3.6.0.

Statistical analyses

Unless otherwise noted, all statistical analyses were performed using the vegan package [START_REF] Oksanen | Community Ecology Package. R package version 2[END_REF] in R v3.6.0. vOTU and 16S rRNA OTU rarefaction and accumulation curves were calculated using the rarecurve and speccacum function respectively. Alpha-diversity indices, Shannon and Simpson indices were calculated using the diversity function, and richness calculated using specnumber. Significant differences in alpha-diversity between pH 4.5 and 7.5 soil was tested using Student's t-test or Wilcoxon-Mann-Whitney's test when variances were not homogenous according to Bartlett's test using the ggpubr R package [START_REF] Kassambara | ggplot2' Based Publication Ready Plots[END_REF]. Viral and prokaryote community structure of pH 4.5 and 7.5 soil were assessed with principal coordinates analysis using Bray-Curtis dissimilarities calculated using the metaMDS function with normalized vOTU and 16S rRNA OTU relative abundance tables. The impact of soil pH on viral community structure was tested using permutational multivariate analyses of variance (PERMANOVA) on Bray-Curtis dissimilarities with the adonis function.

Network analysis of soil viral populations from various soil systems

vOTUs from the gradient pH 4.5 and 7.5 soils with those from six other soil systems were used in the network analysis (Table S4). A gene-sharing network of vOTUs was produced using vConTACT 2.0 [START_REF] Jang | Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by genesharing networks[END_REF] with the RefSeq prokaryote virus database (Release 94; 2019-05-13).

For 'Agriculture site 2' (Table S4), the 7,749 vOTUs were produced as follows: in July and October of 2018, two soil samples were collected from each of 6 one-acre plots. The top 15 cm of soil was collected, sieved through an 8 mm mesh, and kept on ice until storage at -20C. For non-targeted metagenomes (n = 24), genomic DNA was extracted from 0.5 g soil using the PowerSoil Kit (Qiagen, Hilden, Germany), and for viromes (n = 18), virus-like particles were purified from 100 g soil and DNA extracted following the protocol described in Santos-Medellin et al. [START_REF] Santos-Medellin | Viromes outperform total metagenomes in revealing the spatiotemporal patterns of agricultural soil viral communities[END_REF]. Libraries were prepared using the DNA HyperPrep kit (Kapa Biosystems-Roche, Basel, Switzerland) and sequenced on a NovaSeq 6000 at the Technologies and Expression Analysis Core, UC Davis Genome Center. Read quality filtering, contig assembly and clustering, and viral contig identification and vOTU detection was performed as previously described [START_REF] Santos-Medellin | Viromes outperform total metagenomes in revealing the spatiotemporal patterns of agricultural soil viral communities[END_REF].

Supplementary Tables and Figures

  pH gradient was produced by the U.S. Department of Energy Joint Genome Institute, a DOE Office of Science User Facility, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231. The pH gradient experiment is funded through the Scottish Government RESAS 2016-2021 programme. The authors would like to thank Dr. Laurent Pouilloux for assistance with the Newton high performance computing cluster at École Centrale de Lyon. 'Agriculture 2' site data collection and analysis was predominantly funded by the UC Davis College of Agricultural and Environmental Sciences and Department of Plant Pathology (new lab startup to JBE) and also in part by USDA National Institute of Food and Agriculture (NIFA) Hatch project number CA-D-PPA-2464-H and USDA NIFA grant number 2021-67013-34815-0 to JBE. The authors thank Dr. Laura Zinke for collecting and processing the 'Agriculture 2' site samples. 11. Bahram M, Hildebrand F, Forslund SK, Anderson JL, Soudzilovskaia HA, Bodegom PM, et al. Structure and function of the global topsoil microbiome. Nature. 2018;560:233-237. 12. Lauber CL, Hamady M, Knight R, Fierer N. Pyrosequencing-based assessment of soil pH as a predictor of soil bacterial community structure at the continental scale. Appl Environ Microbiol. 2009;75:5111-5120. 13. Nicol GW, Leininger S, Schleper C, Prosser JI. The influence of soil pH on the diversity, abundance and transcriptional activity of ammonia oxidizing archaea and bacteria. Environ Microbiol. 2008;10:2966-78. 14. Bartram AK, Jiang X, Lynch MD, Masella AP, Nicol GW, Dushoff J, et al. Exploring links between pH and bacterial community composition in soils from the Craibstone Experimental Farm. FEMS Microbiol Ecol. 2014;87:403-15. 15. Lee S, Sieradzki ET, Nicolas AM, Walker RL, Firestone MK, et al. Methanederived carbon flows into host-virus networks at different trophic levels in soil. PNAS. 2021;10:e2105124118. 16. Jang HB, Bolduc B, Zablocki O, Kuhn JH, Roux S, Adriaenssens EM, et al. Taxonomic assignment of uncultivated prokaryotic virus genomes is enabled by gene-sharing networks. Nat. Biotechnol. 2019;37:632-639. 17. Al-Shayeb B, Sachdeva R, Chen LX, Ward F, Munk P, Devoto A, et al. Clades of huge phages from across Earth's ecosystems. Nature. 2020;578:425-431. 18. Sobsey MD, Dean CH, Knuckles ME, Wagner RA. Interactions and survival of enteric viruses in soil material. Appl Environ Microbiol. 1980;40:92-101. 19. ter Horst AM, Santos-Medellin C, Sorensen JW, Zinke LA, Wilson RM, Johnston ER, et al. Minnesota peat viromes reveal terrestrial and aquatic niche partitioning for local and global viral populations. Microbiome (in press). 20. Santos-Medellin C, Zinke LA, ter Horst AM, Gelardi DL, Parikh SJ, Emerson JB. Viromes outperform total metagenomes in revealing the spatiotemporal patterns of agricultural soil viral communities. ISME J. 2021;15:1956-1970.

6 )Fig. 1 :

 61 Fig. 1: Taxonomic composition and community structure of prokaryotic and

Gradient 4 . 5 ( 1 %Fig. 2 :

 4512 Fig. 2: Network analysis describing linkages of Gradient 4.5 and 7.5 vOTUs

Fig. S1 :

 S1 Fig. S1: Rarefaction and accumulation curves Fig. S2: Predicted AMGs Fig. S3: Effect of breadth thresholds for defining detection of vOTU contigs Fig. S4: Percent of shared viral clusters between soils

Fig. S1 :

 S1 Fig. S1: Rarefaction and accumulation curves for vOTUs in total metagenomes (pH 4.5, red; pH 7.5, blue; n=3) and viromes (pH 4.5, pink; pH 7.5, cyan; n=3) a) and c), and 16S rRNA OTUs in total metagenomes b) and d).

Fig. S2 :

 S2 Fig. S2: Metabolic category and function of auxiliary metabolic genes (AMGs) in vOTUs from gradient 4.5 and 7.5 soil. The number and relative proportion (based on annotated genes) are given for both VIBRANT and DRAM-v.

Fig. S3 :

 S3 Fig. S3: Effect of breadth (length of contig covered by mapped reads) thresholds for defining detection of vOTU contigs. Heatmaps present the normalized relative abundance of individual vOTUs in gradient pH 4.5 and 7.5 soil viromes (V) and metagenomes (M).

  Fig. S4: Percentage of viral clusters shared between soils based on the gene sharing network analysis.

3. Supplementary References 1 .

 1 Kemp JS, Paterson E, Gammack SM, Cresser MS, Killham K. Leaching of genetically modified Pseudomonas fluorescens through organic soils: influence of temperature, soil pH, and roots. Biol. Fert. Soils. 1992;13:218-224. 2. Lee S, Sieradzki ET, Nicolas AM, Walker RL, Firestone MK, et al. Methane-derived carbon flows into host-virus networks at different trophic levels in soil. PNAS USA. 2021;10:e2105124118. 3. Nicol GW, Prosser JI. Strategies to determine diversity, growth and activity of ammonia oxidising archaea in soil. Meth. Enzymol. 2011;496:3-34.

4 .

 4 Trubl G, Solonenko N, Chittick L, Solonenko SA, Rich VI, Sullivan MB. Optimization of viral suspension methods for carbon-rich soils along a permafrost thaw gradient. PeerJ. 2016;17:e1999. 5. Nurk S, Meleshko D, Korobeynikov A, Pevzner PA. metaSPAdes: a new versatile metagenomic assembler. Genome Res. 2017;27:824-834. 6. Menzel P, Ng KL, Krogh A. Fast and sensitive taxonomic classification for metagenomics with Kaiju. Nat. Commun. 2016;7:11257.

  100

Table S1 :

 S1 Number of predicted viruses

Table S2 :

 S2 Virus-host linkage prediction

Table S3 :

 S3 Alpha-diversity indices

Table S4 :

 S4 Details of sites, soils and vOTUs used in network analysis

Table S5 :

 S5 Summary results of gene sharing network analysis

Table S1 :

 S1 Number of viral contigs (VC) predicted from total metagenomes (M)

	and viromes (V) from contigs ≥10 kb using DeepVirFinder only (DVF), VirSorter
	only (VS), and those predicted by both tools (Both), and resulting number of
	viral operational taxonomic units (vOTUs).
		pH 4.5_1 pH 4.5_2 pH 4.5_3 pH 7.5_1 pH 7.5_2 pH 7.5_3
	Metagenomes			Number of predicted viral contigs
	Total contigs	3193	2081	3450	439	399	366
	DVF (0.9; 0.05)	22	22	29	2	1	3
	VS (cat1,2,4,5)	16	5	20	4	3	2
	Both	8	3	11	1	0	1
	Total M-VC	30	24	38	5	4	4
	Viromes			Number of predicted viral contigs
	Total contigs	1448	1130	1166	3212	2789	3788
	DVF (0.9; 0.05)	729	611	634	1746	1517	2064
	VS (cat1,2,4,5)	81	52	55	148	159	201
	Both	40	27	23	70	65	88
	Total V-VCs	770	636	666	1824	1611	2177
	vOTU			Number of vOTU
	DVF M-VCs	5	2	10	1	0	0
	VS M-VCs	1	0	3	1	0	1
	DVF V-VCs	161	133	195	368	322	619
	VS V-VCs	7	4	11	10	13	43
	Total vOTUs	174	139	219	380	335	663

Table S2 :

 S2 Virus-host linkage predicted from gene sharing network and gene homology analysis with viral contigs (VC) and vOTUs.

		Homologue-linked VCs	vConTACT 2.0-linked VCs	Total linked VCs	Homologue-linked vOTUs	vConTACT 2.0-linked vOTUs	Total linked vOTUs
	Predicted	pH 4.5	pH 7.5	pH 4.5	pH 7.5	pH 4.5	pH 7.5	pH 4.5	pH 7.5	pH 4.5	pH 7.5	pH 4.5
	host phylum	VCs	VCs	VCs	VCs	VCs	VCs	vOTU	vOTU	vOTU	vOTU	vOTU
	Actinobacteria	464	710	19	19	479 (77.6%) 727 (59.4%) 135	217	24	37	140 (77.7%) 220 (58.5%)
	Proteobacteria	102	378	0	0	108 (17.5%) 387 (31.6%) 27	129	9	51	28 (15.5%) 129 (34.3%)
	Acidobacteria	3	1	0	0	3 (0.4%)	1 (0.08%)	1	0	0	0	1 (0.5%)	0 (0%)
	Bacteriodetes		62	0	5	4 (0.6%)	66 (5.3%)	2	17	2	1	4 (2.2%)	18 (4.7%)
	Firmicutes	10	3	5	24	15 (2.4%)	27 (2.2%)	3	2	1	10	4 (2.2%)	5 (3.3%)
	Planctomycetes	1	7	0	0	1 (0.1%)	7 (0.5%)	1	2	0	0	1 (0.5%)	2 (1.3%)
	Candidatus Gottesmanbacteria	0	1	0	0	0 (0%)	1 (0.08%)	0	1	0	0	0 (0%)	1 (0.2%)
	Candidatus Moranbacteria	1	0	0	0	1 (0.1%)	0 (0%)	0	0	0	0	0 (0%)	0 (0%)
	Candidatus Schekmanbacteria	0	1	0	0	0 (0%)	1 (0.08%)	0	0	0	0	0 (0%)	0 (0%)
	Candidatus Woesebacteria	0	1	0	0	0 (0%)	1 (0.08%)	0	0	0	0	0 (0%)	0 (0%)
	Chloroflexi	4	3	0	0	4 (0.6%)	3 (0.2%)	1	0	0	0	1 (0.5%)	0 (0%)
	Thaumarcheaota	2	0	0	0	2 (0.3%)	0 (0%)	1	0	0	0	1 (0.5%)	0 (0%)
	Verrucomicrobia	0	2	0	0	0 (0%)	2 (0.1%)	0	1	0	0	0 (0%)	1 (0.2%)

Table S4 :

 S4 Details of sites, soils and viral populations (vOTUs) used in network analysis of viral communities.

	Site identity	Location	Coordinates	Soil type	pH	C (%)	N (%)	Number of vOTUs Reference
	Gradient pH 4.5 Scotland, UK	57°11'N,	podzol,	4.5 6.02	0.58	532 (this study)	Bartram et al. [26] (see for
			2°12'W	sandy loam					site description)
	Gradient pH 7.5				7.5 7.14	0.34	1,378 (this study)
	Peat	Minnesota, USA 18°18'N,	peat	4.0 5.80	0.95	5,006	ter Horst et al. [27]
			65°50'W
	Bog	Northern	68°21'N,	peat	4.1 43.18	0.80	703	Emerson et al. [28]
		Sweden	19°03'E
	Palsa			peat	4.2 35.07	1.17	794
	Fen			peat	5.9 37.59	1.34	334
	Agriculture 1	California, USA	38°32'08''N,	Yolo silt	6.9 1.10	0.12	4,065	Santos-Medellin et al. [25]
			121°46'22''W	loam
	Agriculture 2	California, USA	38°32'42''N,	Rincon silty	7.5 1.36	0.15	7,749 (this study)	Wolf et al. [29] (see for
			121°52'36'' W	clay loam					site description)

Table S3 :

 S3 Alpha-diversity indices calculated from normalized vOTU abundance (from viromes only) and normalized 16S rRNA OTU abundance. Values represent mean ± SD.

		Shannon	Simpson	Richness
	pH 4.5 vOTUs	5.71 ±0.012	0.99 ±0.0001	942.6 ±22.8
	pH 7.5 vOTUs	6.89 ±0.006	0.99 ±0.00005 1514.6 ±3.4
	pH 4.5 16S OTUs	6.15 ±0.01	0.99 ±0.00025 1273 ±62.6
	pH 7.5 16S OTUs	6.58 ±0.03	0.99 ±0.00044 1519 ±27.0

Table S5 :

 S5 Summary of gene sharing network analysis and the number of vOTUs in clusters from various soils shared with those from gradient pH 4.5 and 7.5 soils.

	Site identity	Number	Number of	Number of	Number of	Number of
		of nodes	singleton	vOTUs	vOTUs	vOTUs
		(vOTUs)	clusters	clustered	clustered	clustered
				with unique	with unique	with both
				gradient pH	gradient pH	gradient pH
				4.5 vOTUs	7.5 vOTUs	4.5 and 7.5
						vOTUs
	Gradient pH 4.5 467	9	189	0	84
	Gradient pH 7.5 1,272	24	0	590	105
	Peat	4,456	95	135	61	32
	Bog	646	4	46	16	8
	Palsa	640	16	25	35	11
	Fen	265	3	7	12	4
	Agriculture 1	3,843	44	48	272	69
	Agriculture 2	7,282	147	96	708	150
	RefSeq	2,568	101	9	28	8
	Total	18,871	443

Acknowledgments

This work was funded by an AXA Research Chair awarded to GWN. The sequencing data were generated under JGI Community Science Program proposal 503702 awarded to GWN and CH. The sequencing data from the soil

V_pH 4.5_1 V_pH 4.5_2 V_pH 4.5_3 M_pH 4.5_1 M_pH 4.5_2 M_pH 4.5_3 M_pH 7.5_1 M_pH 7.5_2 M_pH 7.5_3 V_pH 7.5_1 V_pH 7.5_2 V_pH 7.5_3 V_pH 4.5_1 V_pH 4.5_2 V_pH 4.5_3 M_pH 4.5_1 M_pH 4.5_2 M_pH 4.5_3 M_pH 7.5_1 M_pH 7.5_2 M_pH 7.5_3 V_pH 7.5_1 V_pH 7.5_2 V_pH 7.5_3

Data availability

Metagenome sequence reads are deposited in NCBI's GenBank under BioProject accession nos. PRJNA621436-PRJNA621447. Metagenome draft assemblies are accessible through the JGI Genome Portal (DOI: 10.25585/ 1487501). Assembled metagenome-derived 16S rRNA gene sequences are available at ftp://ftp-adn.ec-lyon.fr/. Metagenome sequence reads from 'Agriculture 2' site are available through NCBI BioProject PRJNA767554.

Competing Interests

The authors declare no competing interests.


Patient Ntumba

Nikolaos Georgantas

Vassilis Christophides
email: vassilis.christophides@ensea.fr

Efficient Scheduling of Streaming Operators for IoT Edge Analytics

Keywords: Cloud computing, Edge/Fog computing, IoT, data stream, continuous query, heuristic

Data stream processing and analytics (DSPA) applications are widely used to process the ever increasing amounts of data streams produced by highly geographical distributed data sources such as fixed and mobile IoT devices in order to extract valuable information in a timely manner for real-time actuation. To efficiently handle this ever increasing amount of data streams, the emerging Edge/Fog computing paradigms is used as the middle-tier between the Cloud and the IoT devices to process data streams closer to their sources and to reduce the network resource usage and network delay to reach the Cloud. In this paper, we account for the fact that both network resources and computational resources can be limited and shareable among multiple DSPA applications in the Edge-Fog-Cloud architecture, hence it is necessary to ensure their efficient usage. In this respect, we propose a resource-aware and time-efficient heuristic called SOO that identifies a good DSPA operator placement on the Edge-Fog-Cloud architecture towards optimizing the trade-off between the computational and network resource usage. Via thorough simulation experiments, we show that the solution provided by SOO is very close to the optimal one while the execution time is considerably reduced.

I. INTRODUCTION

Today, more and more data are delivered in real-time. Real-time data are not kept or stored, but are passed along to the end user as quickly as they are gathered. The time value of data is essential to many applications requiring real-time (or near real-time) control and automation such as smart transportation [START_REF] Lin | An edge computing based public vehicle system for smart transportation[END_REF], security [START_REF] Dangal | Towards industrial security through real-time analytics[END_REF], augmented or virtual reality [START_REF] Lv | Real-time image processing for augmented reality on mobile devices[END_REF]. Working with real-time data requires stream processing compared to batch processing of historical data. Data stream processing and analytics (DSPA) engines aim to continuously process unbounded data streams generated by multiple distributed sources to extract valuable information in timely manner via a series of continuous operators such as aggregation, filter, join, etc. [START_REF] Röger | A comprehensive survey on parallelization and elasticity in stream processing[END_REF].

DSPA applications are typically deployed in the Cloud in order to benefit from practically unlimited computational resources on demand. Such centralized solutions favor application availability but may suffer from network congestion and delay issues in case of highly dynamic data streams. Additionally, data propagation to the Cloud may compromise privacy of sensitive data. Recent breakthroughs in network technology allow to realize post-Cloud architectures in order to collect and process real-time data. 5G networks [START_REF] Li | 5G Internet of Things: A survey[END_REF] enable an increased network bandwidth capacity up to 10 Gbps, low-latency communications down to 1 ms, and a high connectivity density up to 1 million of IoT devices per km 2 . This enables IoT devices to transmit a greater number of data streams at high data rates. However, pushing such amount of real-time data systematically to the Cloud could definitely cause excessive stress on network resources and introduce network delays for real-time IoT applications.

In this respect, the solution lies in taking advantage of the emerging Edge/Fog computing paradigms [START_REF] Bittencourt | The internet of things, fog and cloud continuum: Integration and challenges[END_REF]. They introduce a middle-tier between the IoT devices and the Cloud, in order to extend computational resources close to IoT devices and hence to process data streams near their sources, consequently to reduce network consumption and network delay and to enforce data privacy. The Edge/Fog computing relies on geographical distributed heterogeneous nodes such as mobile or fixed IoT devices (e.g., camera, connected vehicle, smartphone, etc.), small data centers, routers, wireless base stations, etc. that come with stringent resource constraints in terms of limited computational resources (e.g., CPU, RAM, etc.) and limited power supply (e.g., rechargeable batteries, solar energy, etc.) that may have to be shared amongst several DSPA applications. However, the majority of research efforts related to Edge/Fog-based data stream processing focus on optimizing network resource usage and end-to-end network delay, while only ensuring that the capacity of Edge/Fog computational resources is not exceeded [START_REF] Brogi | QoS-aware deployment of IoT applications through the fog[END_REF]- [START_REF] Nardelli | Efficient operator placement for distributed data stream processing applications[END_REF]. Clearly, DSPA operators should also account for both the computational capacities available at the heterogeneous Edge/Fog nodes and the highly dynamic workloads related to the spatio-temporal dynamics of real data produced in the wild for multiple DSPA applications [START_REF] Hong | Resource management in fog/edge computing: a survey on architectures, infrastructure, and algorithms[END_REF]. Thus, to distribute computations of a DSPA application across the Edge/Fog and Cloud layers, we need to consider optimal tradeoffs between the management of network resources used to reach the Cloud (i.e., network bandwidth, network delay) and the management of computational resources (CPU, RAM) exploited at Edge/Fog nodes.

In this paper, we assume the Edge-Fog-Cloud architecture as a hierarchical wide area resource network shareable by several DSPA applications [START_REF] Bittencourt | The internet of things, fog and cloud continuum: Integration and challenges[END_REF]. As depicted in Figure 1, at the root of the hierarchy we consider a Cloud node providing computational and network resources on demand. Linked to Cloud node, a set of Fog nodes provide limited computational and network resources at the Fog layer [START_REF] Hu | Quantifying the impact of edge computing on mobile applications[END_REF]. We assume an overlay network based on the publishsubscribe protocol MQTT [START_REF] Katsikeas | Lightweight secure industrial IoT communications via the MQ telemetry transport protocol[END_REF] to transport data streams across the Edge-Fog-Cloud architecture. In this respect, we consider at the Edge mobile IoT devices (e.g., vehicles) per geographical area that produce and publish data at a certain rate (e.g., 4KB/s [START_REF] Xhafa | Evaluation of IoT stream processing at edge computing layer for semantic data enrichment[END_REF]) each one to the MQTT instance deployed on the closest Fog node via 5G antennas. We assume that these antennas enable high connectivity density and lossless communication for IoT devices. If a part of the DSPA application is deployed on this Fog node, the MQTT instance transfers these data to the Fog application part and expects the resulting output data back in order to send them to the MQTT instance deployed in the Cloud for further processing. Otherwise if no application part is deployed on the Fog node, the Fog MQTT instance transfers directly these data to the Cloud MQTT instance.

We consider for example a DSPA application for country wide traffic monitoring that gives periodically the traffic status per region [START_REF] Tiwari | Reconfigurable streaming for the mobile edge[END_REF]. This DSPA application aggregates and analyses the data streams (e.g., vehicle identifier, GPS-location, driving speed) produced by the moving vehicles in the different regions of a country. Given the varying number and the mobility of vehicles, data streams can be very dynamic in a geographical area.

The related problem consists in identifying the DSPA operator replication and placement scheme across heterogeneous Edge-Fog-Cloud resources in order to optimize the resource usage while satisfying the maximum resource usage constraints with respect to the evolution of the data stream rates. In this paper, we formulate the corresponding optimization problem and show that it is NP-hard.

In our previous work [START_REF] Ntumba | Scheduling Continuous Operators for IoT Edge Analytics[END_REF], we introduced a holistic cost model of both network (bandwidth, delay) and computational resources (CPU/RAM of nodes) and formulated the operator scheduling problem as a single objective optimization (SOO) problem of the combined resource cost, and further as an instance of integer linear programming (ILP) subject to inequality constraints. In this respect, we employed the CPLEX tool [START_REF] Studio-Cplex | Users manual-version 12 release 6[END_REF] to find an optimal solution. However, our SOO-CPLEX solution may incur a high execution time for large problem sizes due to the NP-hardness of the optimization problem. Hence, this solution is not appropriate for dynamic scheduling of DSPA operators in response to highly dynamic data streams.

In this paper, we introduce a heuristic solution, which we call SOO, to the streaming operator scheduling problem. SOO leverages the particularities of the problem in hand in order to reduce the execution time while achieving excellent optimality, both in best-case and worst-case executions.

We experimentally evaluate the operator scheduling achieved by SOO via simulation on iFogSim [START_REF] Gupta | iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments[END_REF] under different configurations of the Edge-Fog-Cloud architecture and numbers and rates of the data streams. In best-case execution, SOO finds the optimal solution (same as SOO-CPLEX) with a performance gain up to 63% in terms of execution time for the problem sizes that we experimented with. In worst-case execution, SOO approximates the optimal solution with up to 0.01% of approximation error, while reducing the execution time up to 55%.

The remainder of this paper is as follows: Section II introduces the system model as well as our modeling of the resource usage cost, and formulates the resource allocation problem. Section III presents the SOO scheduling algorithm. Section IV details the experimental evaluation. Finally, Sections V and VI present respectively the related work and the conclusion.

II. RESOURCE ALLOCATION PROBLEM

A. System model 1) DSPA application: is modeled as a directed acyclic graph of operators, denoted by G , where the vertices are the set of continuous operators and the edges are the set of data stream flowing between two operators [START_REF] Röger | A comprehensive survey on parallelization and elasticity in stream processing[END_REF]. G topology further includes the sources that produce the raw data streams Sj of rate |Sj| consumed by DSPA operators and sinks that capture the stream of the computed results. To cope with the infinite nature of data streams, we consider that continuous operators are executed in time windows ωx to process a finite set of data items arising within a time interval. Furthermore, we consider the following parameters: a) Operator selectivity (selx): is the ratio between the input and output data rate of an operator Ox.

b) Cumulated operator selectivity (cselx):: is the product of operator selectivity from a source to a target operator Ox following the topological order of operators in the application graph G. c) Edge data rate (λx,y): is the rate of data stream flow between two operators, from a source to an operator or from the application graph to a sink. This is calculated as the product of the cumulated operator selectivity of the upstream operator (or data source) and the rate of the raw data stream Sj: λx,y = cselx • |Sj|.

d) Edge-cut (ecj): used in graph theory, is the partitioning of the application graph into two disjoints subgraphs. Any edge-cut contains a set of edges that have one endpoint in each subgraph of the partition. Hence let |ecj| denotes the value (or rate) of an edge-cut ecj which is the sum of data rates of the edges crossing this edge-cut.

e) Minimum edge-cut: is the edge-cut that has the smallest value among all the edge-cuts in the application graph G. To calculate the minimum edge-cut we may rely on the Edmond-Karp algorithm [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF] that is proven to be efficient for dense graphs.

f) Operator data load (ρx): is the aggregation of the input data streams per time window ωx, we assume a specific window, ωx=1sec:

ρj = I i=1 ωj • λi,j (1)
Where I is the maximum number of upstream operators Ox producing data stream at rate λx,y towards the operator Oy.

g) Operator cost (cx): is the computational cost in terms of CPU and/or memory usage for an operator Ox to process a unitary data load ρx.

2) Edge-Fog-Cloud architecture: is abstracted as hierarchical wide-area resource network as depicted in Figure 1. The Edge layer consists of M IoT devices Ei, i = {1, ..., M } moving in N geographic areas, the Fog layer consist of N Fog nodes Fj, j = {1...N } where each Fog node Fj provides nearby computational service to the geographic area j. And one Cloud node C on the top of the hierarchy.

In this respect, we consider the following parameters: cmE i is the maximum CPU/memory of an Edge node Ei. The network link from an Edge node Ei to its nearest Fog node Fj is characterized by a network delay ndE i F j and the network bandwidth capacity nbEF j of all incoming links to the fog node Fj. cmF j is the maximum CPU/memory of a Fog node Fj. The network link from a Fog node Fj to the Cloud node C is characterized by a network delay ndF j C and the network bandwidth capacity nbF j C for all incoming links of the cloud node. Finally, cmC is the maximum CPU/memory of the Cloud node.

We consider also cmuE i , cmuF j and cmuC as the CPU/memory usage respectively on a Edge node Ei, a Fog node Fj and the Cloud node C; additionally nbuE i F j and nbuF j C are the network bandwidth usage on network links respectively from an Edge node Ei to a Fog node Fj and from a Fog node Fj to the Cloud node C.

Finally, we consider Sj as the sum of data streams arriving to a Fog nodes Fj and produced by mj(t) ≤ M IoT devices moving at a time t in a geographic area j. Given the above, at time t M = N j=1 mj(t).

B. Computational resource usage cost

Our cost model extends [START_REF] Donassolo | Fog based framework for IoT service provisioning[END_REF] in order to take into account the usage cost of computational resources shared by multiple DSPA applications. More precisely, we weight the usage of a computational resource by an individual application by the inverse of its computational capacity. The overall computational resource usage cost is:

cru = M i=1 cmuE i • 1 cmE i + N j=1 cmuF j • 1 cmF j + cmuC • 1 cmC ( 2
)
Where M is the total number of the Edge nodes Ei, N is the total number of the Fog nodes Fj, cmuE i , cmuF j and cmuC are the CPU/memory usage respectively on the Edge node Ei, the Fog node Fj and the Cloud node C. The more computational resources a node has the less is the cost for running a specific computation [START_REF] Li | Online workload allocation via fog-fog-cloud cooperation to reduce IoT task service delay[END_REF]. Thus, in the Cloud computational resources are practically infinite (cmC → ∞), so the weight is very small, practically zero ( 1cm C → 0). In the Fog, computational resources are limited, so the weight is higher ( 1 cm F j → 1) and the cost for using these resources is high, hence computational resources in the Fog should be used with parsimony as in addition they may have to be shared among multiple applications.

Similarly to [START_REF] Li | Online workload allocation via fog-fog-cloud cooperation to reduce IoT task service delay[END_REF], computational resources of IoT devices at the Edge are not used. An approach to account for mobile and fixed computational resources at the Edge will be addressed in our future work. Then, Formula (2) becomes:

cru = N j=1 cmuF j • 1 cmF j ( 3
)
cmuF j is the sum of the CPU/memory usage required by each operator of the subgraph Gmigj ∈ G, which is replicated on the Fog node Fj:

cmuF j = Ox∈Gmig j ρx • cx (4)

C. Network resource usage cost

We consider that modeling the Edge-to-Fog network as a localarea network (LAN) and the Fog-to-Cloud network as a wide-area network (WAN) as in [START_REF] Li | Online workload allocation via fog-fog-cloud cooperation to reduce IoT task service delay[END_REF] is too restrictive, since a Fog node may be located at shorter but still considerable distance from the Edge. Thus, in our cost model the Edge-Fog-Cloud architecture is considered as a hierarchical wide area resource network. Hence, two conflicting factors are involved: network bandwidth increases up the hierarchy, however also network delay increases up the hierarchy. In the literature [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF], [START_REF] Cardellini | Optimal operator placement for distributed stream processing applications[END_REF], concerning peer node networks, network delay is used as the only weight factor for differentiating network links. We additionally include network bandwidth as a weight factor: using network links of limited capacity with parsimony allows an efficient sharing among several DSPA applications.

Then, the overall network resource usage cost at time t is:

nru = N j=1 m j (t) i=1 nbuE i F j nbEF j • ndE i F j ndmin + N j=1 nbuF j C nbF C • ndF j C ndmin (5)
where mj(t) ≤ M is the number of the Edge nodes Ei sending data streams to their closest Fog node Fj at a time t, N is the number of the Fog nodes Fj. nbuE i F j and nbuF j C are the network bandwidth usages on the network links respectively from Ei to Fj and from Fj to the Cloud node C. ndmin is the minimum network delay in the resource network (ndmin = min i,j

{ndE i F j , ndF j C }).
As the Edge is much closer to the Fog, normally one of the Edge-to-Fog network links has the minimum network delay.

Given that no processing is done at the Edge, each entire raw data stream Sj produced at the Edge reaches the Fog anyway. Thus in Formula (5), the cost part concerning Edge-Fog network links is fixed (set as c constant). Furthermore, although the network delay on a wide-area network link can vary due to the condition of the underlying physical link that is shared by multiple data connections [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF], we assume that the network delays between each Fog node and the Cloud can be considered equal and that ndF j C and ndmin can be assigned statically calculated average values. Then, we can consider

nd F j C
nd min as a constant a. In this way Formula (5) becomes:

nru = c + a • N j=1 nbuF j C • 1 nbF C (6)
The network bandwidth effectively used on all the Fog-to-Cloud network links is defined as follows:

B = N j=1 nbuF j C (7)
While we considered Cloud computational resources as practically infinite in our resource cost model, we opt for considering Cloud network bandwidth as a resource the usage of which incurs a cost that should be taken into account. Indeed, Cloud providers rely on contracts with ISPs for network bandwidth. For distributed data intensive applications, the usage of the Cloud network bandwidth can be a bottleneck when sending huge volumes of data streams. Hence, for such applications the (monetary) cost charged by Cloud providers for network bandwidth usage can be much larger than the cost charged for computational resource usage. Thus, we assume an upper threshold Bmax of B which is set for a specific DSPA application.

D. Problem statement

The operator placement problem is a conflicting optimization problem, since minimizing the (overall Fog) computational resource usage cost, i.e., cru, implies placement of all operators of G in the Cloud, which results in low (zero) cru and high (overall Fog-to-Cloud) network resource usage cost, i.e., nru; while minimizing nru implies placement of all operators of G in the Fog, which results in high cru and low nru. Hence, there is a trade-off to address between the two metrics. Similarly to [START_REF] Ntumba | Scheduling Continuous Operators for IoT Edge Analytics[END_REF], we transform this conflicting optimization problem to a single-objective optimization (SOO) problem by applying weights to the different optimization metrics. As cru and nru are defined in different scales, we first normalize these two metrics by using the min-max scaling technique. Then, cru defined in Formula (3) is normalized as follows:

CRU = cru -crumin crumax -crumin ( 8
)
Where crumin is the minimum value set to 0 and crumax = N is the maximum value set to the number of Fog nodes.

Furthermore, we consider N RU as the normalized form of nru defined in Formula ( 6), where the constants c and a are eliminated.

Following from the above, we aim to minimize the overall resource usage cost RU defined as the weighted sum of CRU and N RU :

minimize RU = wc • CRU + wn • N RU (9)
subject to cmuF j ≤ cmF j j = {1, . . . , N },

B ≤ Bmax. (10)
Where wc ≥ 0 and wn ≥ 0 are respectively the weights for computational and network resource usage cost, which enable to specify a usage preference for one of the two types of resources over the other. In the rest of the paper, we consider that wc = wn = 1.

Equation ( 10) represents the computational resource usage (i.e., CPU/RAM usage) constraint for each individual Fog node (max available capacity). Similarly, Equation ( 11) is the constraint on the Fog to Cloud network bandwidth usage.

Finally, we consider the operator replicability constraint: an operator can be replicated on a Fog node if there is sense in applying its operation only to the local data stream. Otherwise, if this operation must be applied to the global data stream, the operator can only be deployed in the Cloud.

III. HEURISTIC SOLUTION

To solve our streaming operator scheduling problem, we need to search in the graph G the replication and migration point (edge-cut) ecj of each data stream Sj and Fog node Fj. The edge-cut ecj delimits the sub-graph Gmigj ∈ G to replicate and migrate on the corresponding Fog node Fj. Gmigj should satisfy the computational resource usage constraint in [START_REF] Hong | Resource management in fog/edge computing: a survey on architectures, infrastructure, and algorithms[END_REF] and the operator replicability constraint. On the other hand, the processed data streams Sj that will be transmitted on the Fog to Cloud network links should jointly satisfy the network bandwidth usage constraint [START_REF] Hu | Quantifying the impact of edge computing on mobile applications[END_REF].

We observe that, when selecting an edge-cut ecj as the replication and migration point of a data stream Sj and Fog node Fj, we can individually calculate the effect of this selection on the overall resource usage cost. Thus, we assume that the computational and network resource usage costs can be split for each individual data stream Sj as follows:

RU = N j=1 RUj, where RUj = CRUj + N RUj (12)
We consider RUj, CRUj and N RUj as respectively the contributions to RU , CRU , and N RU for processing a data stream Sj.

Considering our streaming operator scheduling problem with the objective of minimizing RU , given the values of RUj at each edgecut ecj and for all data streams Sj and Fog nodes Fj, under the global constraint of network bandwidth usage, our problem can be mapped to a 0/1 knapsack problem [START_REF] Salkin | The knapsack problem: a survey[END_REF], which is NP-hard.

To address this NP-hardness, our proposed heuristic solution called Single Objective Optimization (SOO) algorithm is inspired from BOSe [START_REF] Neophytou | Poweraware operator placement and broadcasting of continuous query results[END_REF]. SOO first applies a parallel search to generate a solution that attempts to minimize the overall resource usage cost RU by minimizing independently RUj for each data stream Sj. If this solution satisfies the constraint B ≤ Bmax, then the achieved RU is optimal. Otherwise the problem may not have a solution or, if a solution exists, finding the optimal solution is NP-hard.

Thus in a second step, SOO applies a greedy search that produces local optimal solutions to approximate the global optimal solution in a reasonable amount of time. In this respect, we first use the minimum edge-cut approach to identify the solution that minimizes N RU by minimizing independently N RUj for each data stream Sj. If the resulting Fog-to-Cloud bandwidth usage does not satisfy the constraint B ≤ Bmax, the problem has no solution. By relaxing accordingly the Bmax constraint, we may accept this last solution as the best possible one. On the other hand, if the constraint B ≤ Bmax is satisfied, SOO applies a greedy search to improve this solution by further reducing RU . We present the pseudo-code of our proposed SOO heuristic in Algorithm 1.

Algorithm 1: SOO

Input: G, application graph Input: Grep, subgraph of replicable operators of G Input: Bmax, upper threshold for bandwidth usage Input: Sraw, set of raw data streams S j 1 U pdated ← ∅, set of S j on which ∆RU is applied S j 2 M ← ∅, set of Gmig j , replicable subgraph per S j 3 RM ← ∅ set of edge-cuts ec j ∈ Grep per S j 4 RU ← 0, overall resource usage cost 5 B ← 0, Fog-to-Cloud network bandwidth usage 6 M ← RU minCut()

7 if B > Bmax then 8 Selected ← dataM inCut()

A. Parallel search

We use the function RUminCut, in which for each data stream Sj we identify Gsatj ⊆ Grep as the part of Grep that satisfies the computational resource constraint on the Fog node Fj receiving the data stream Sj. Then, we select the edge-cut ecj ∈ Gsatj that produces the minimum RUj. We set this edge-cut as the replication and migration point of Sj on the Fog node Fj. Then, we identify the candidate sub-graph Gmigj ⊆ Gsatj to replicate on Fog node Fj delimited by the identified edge-cut ecj. Once we identified Gmigj for all the data streams Sj, we calculate the resulting Fog-to-Cloud network bandwidth usage B and the overall resource usage cost RU . The pseudo code of RU minCut is presented in Algorithm 3.

B. Greedy search

1) dataMinCut: Similarly to RU minCut, for each data stream Sj, we pass by Grep ⊆ G and Gsatj ⊆ Grep for selecting, in this case, the minimum edge-cut ecj that produces the minimum N RUj. In this way, we identify the resulting candidate subgraph Gmigj ⊆ Gsatj delimited by the minimum edge-cut ecj. Then, we compute the overall N RU , RU and B. For space saving, we omit to present its pseudo-code.

2) edgeCutMove: Departing from the solution of dataM inCut and for each individual data stream Sj, any backward move of an edge-cut ecj in Gmigj will decrease CRUj (consequently also CRU ) while it will increase or decrease N RUj (consequently also N RU ).

For example, in Figure 2 we identify Gmig2 as the subgraph to replicate on the Fog at the minimum edge-cut ec3 for processing the stream S2. The possible edge-cut backward moves to consider are: ec2 1 , ec2 2 , ec2 3 and ec2 4 ; the contributions to RU are respectively RU2 1 , RU2 2 , RU2 3 , RU2 4 .

Fig. 2. Example of edge-cut move

Given the above, for any edge-cut backward move ecj on a data stream Sj, we assume the changes ∆CRU and ∆N RU respectively in CRU and N RU , where ∆CRU is in general negative and ∆N RU may be negative or positive. Thus, we can calculate the change in the resource usage cost RU as follows: ∆RU = ∆CRU + ∆N RU , and Formula ( 9) can be expressed as RU = RU + ∆RU .

The objective of the greedy search is first to identify all possible edge-cut backward moves, as described by the function edgeCutM ove presented in Algorithm 2, then to apply the edgecut moves that produce the smallest ∆RU < 0, while satisfying the constraint B ≤ Bmax. To apply the edge-cut moves, we retrieve ∆RUset, the result of edgeCutM ove, which is the set of ∆RU's, then we sort this set in increasing order. We pull from the top of the set the smallest ∆RU. If ∆RU is lower than 0, we apply its corresponding edge-cut move ecj k as the current replication and migration point of the data stream Sj, and Gmigj k as the current subgraph to deploy in the Fog, only if the constraint B ≤ Bmax is satisfied. Then, we pull from ∆RUset the next lowest ∆RU to continue improving RU , as long as the remaining ∆RUset is not empty or we do not yet encounter a ∆RU ≥ 0. It worth noting that we update at most once each data stream Sj with its best (lowest) ∆RU. The pseudo-code for applying the backward edge-cut moves is presented in Algorithm 1, lines 11-22.

IV. EVALUATIONS

We use the simulator tool iFogSim [START_REF] Gupta | iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments[END_REF] driven by realistic parameter settings that are proposed in [START_REF] De Souza | A throughput model for data stream processing on fog computing[END_REF]. As benchmarks, we consider: (i) SOO-CPLEX that produces optimal solutions, and (ii) RCS (Resource Constraint Satisfaction) as baseline approach [START_REF] Ntumba | Scheduling Continuous Operators for IoT Edge Analytics[END_REF]. RCS enhances pure Cloud-based stream processing by dynamically placing the streaming operators between the Fog and the Cloud in synergy with the evolution of IoT data stream rates. More specifically, assuming an initial deployment of all the operators in the Cloud, RCS minimally uses the Fog computational resources to satisfy the constraints B ≤ Bmax and B ≥ Bmin, where Bmin is a lower threshold of B that we add to avoid the oscillation of operator placement between the Fog and the Cloud. In this respect, we implement SOO, SOO-CPLEX and RCS in Java inside the simulator. To ensure that SOO-CPLEX produces the optimal solution, we set Find ec j in Gsat j with the minimum

RU j ← CRU j + N RU j 6 Find Gmig j ⊆ Gsat j delimited by ec j 7 RU ← RU + RU j 8 B ← B + |ec j | 9 M [j] ← Gmig j 10 RM [j] ← ec j 11
Keep and map ec j to RU j 12 return M the optimality gap (OG) to 0.0%. OG is a metric used by CPLEX to trade off between optimality and performance.

For our simulation experiments, we build a model of the TLC application (New York City Taxi and Limousine Commission rides) [START_REF] Silva | Investigating edge vs. cloud computing trade-offs for stream processing[END_REF]). The TLC application finds the busiest driver every two hours, where each vehicle emits at the end of a ride a data record containing driver identification, pick-up and drop-off times and locations. It comprises 5 operators and 1 sink as depicted in Figure 3. We also build a simulation model of the Edge-Fog-Cloud architecture presented in Figure 1, where we scale the numbers of Fog nodes and IoT devices.

We statically simulate the variability of the data stream rates arriving to the Fog nodes by selecting randomly (uniform distribution) 10 values of M (number of IoT devices) in the interval [5000, 50000], where each IoT device produces data at a rate of 4KB/s [START_REF] Xhafa | Evaluation of IoT stream processing at edge computing layer for semantic data enrichment[END_REF]. Then for each value of M, we set an interval [0, M ] in which we randomly (uniform distribution) set mj(t) IoT devices per geographical area j, so that the sum of mj(t) be equal to M. In this respect, each Fog node Fj receives data stream Sj at rate |Sj| = mj(t) × 4KB/s. We wish to have around 15 results of RU, CRU, and NRU for each value of M ∈ [5000, 50000] and to plot the average of these results per value of M. Hence, we repeat the splitting of each value of M per geographical area 15 times. In this respect, the total data rate reaching the Fog follows a random (uniform distribution) sequence of the 10 values of M ×4KB/s repeated 15 times. We feed this sequence to SOO, RCS and SOO-CPLEX. For RCS, we maintain the previous state of the DSPA application between the successive experiments. For SOO and SOO-CPLEX, each experiment is independent, since these two approaches calculate each time a new operator placement without taking into account the previous deployment state.

A. Parameter setting

We evaluate the performance of SOO against RCS and SOO-CPLEX in both best-case and worst-case executions of the SOO algorithm. Best-case execution is related to the set of experiments where SOO applies only RU minCut. Worst-case execution is related to the set of experiments where, additionally, SOO applies a greedy search including dataM inCut and edgeCutM ove.

We observed that SOO executes in the worst case only in a narrow subspace of parameter settings. We generate parameter settings inside and outside this subspace by proceeding as follows: assuming that the graph G of the DSPA application is a two-degree graph (as the one of Figure 3), we introduce the following two parameters: i) the cost of operator Oy for processing a unitary data load entering the graph, based on the cumulated selectivity of its upstream operator Ox: csel cy = cselx • cy, where cy is the cost of the operator Oy; and ii) the cumulated sum of such costs up to an operator Oy: sum csel cy = sum csel cx + csel cy. Table I shows the values of cselx and sum csel cx for the DSPA application of Figure 3. Given the formulas of CRU and N RU , we identify the following equilibrium, which represents a balance between the maximum CRU and N RU values over all possible edge-cuts selected as replication and migration points:

max Ox∈G (sum csel cx) N j=1 cmF j ≈ max Ox∈G (cselx) Bmax (13)
This equilibrium qualifies the case when, while moving from an edge-cut to another, network resources are replaced by computational resources of, more or less, equal cost. Then RU = CRU + N RU will be almost constant.

We have observed that, for a best-case execution of SOO, the Fog computational resources should be less costly (i.e., relatively more abundant) than the Cloud network resources. To do so, we increase cmF j for each Fog node Fj or decrease Bmax with respect to the equilibrium [START_REF] Xhafa | Evaluation of IoT stream processing at edge computing layer for semantic data enrichment[END_REF]. This ensures that RU minCut produces a solution where the constraint B ≤ Bmax is satisfied. Accordingly, we consider N=30 Fog nodes, and we set their computational capacity in terms of RAM so that 20% of the nodes have 256MB, 30% have 1GB and 50% have 2GB. Then we set Bmax = 125000KB/s (≈ 1Gbps).

For a worst-case execution of SOO, the Fog computational resources should be more costly (i.e., relatively less abundant) than the Cloud network resources. To this end, we decrease cmF j for each Fog node Fj or increase Bmax with respect to the equilibrium [START_REF] Xhafa | Evaluation of IoT stream processing at edge computing layer for semantic data enrichment[END_REF]. However, we cannot go very far away from the equilibrium, otherwise dataM inCut produces a solution where B > Bmax, i.e., there is no solution to the problem. Accordingly, we consider N=10 Fog nodes where all of them have 256MB of RAM, and we keep Bmax = 125000KB/s. Additionally for the baseline solution RCS, we set Bmin = 75000KB/s.

B. Evaluation results

1) Best-case execution: In this set of experiments, the Fog computational resources are relatively abundant and hence their usage is less costly than the usage of the Cloud network resources. As depicted in Figure 4, whatever the evolution of the number of IoT devices at the Edge and consequently the data stream rates reaching the Fog nodes, SOO performs like SOO-CPLEX, thus it finds the optimal RU thanks to RU minCut, for which the resulting solution satisfies directly the constraint B ≤ Bmax. When comparing to RCS, SOO outperforms it with a difference ratio that decreases from 43.96% to 2.48% with respect to the evolution of the number of IoT devices at the Edge. 6 show that SOO finds a balance between CRU and N RU in order to minimize RU . Given that RCS resorts minimally to the Fog resources, when M ≤ 20000 IoT devices the resulting data stream rate that reaches the Cloud through the Fog nodes is lower than Bmax, hence no processing is moved to the Fog and CRU is null, as depicted in Figure 5. When comparing to SOO, such cost can be considered as cost-efficient, but the counterpart in terms of N RU is very high, as depicted in Figure 6. However when M > 20000 IoT devices, CRU for RCS is monotonically increasing for satisfying the constraint B ≤ Bmax. Furthermore, we can see in Figure 5 that CRU values of SOO, SOO-CPLEX and RCS are very small, lower than 0.1. This is due to the specific computational requirements of the DSPA application (Figure 3) and the high capacities of the Fog computational resources.

2) Worst-case execution: In this set of experiments, the Fog computational resources are pretty limited, thus their usage is more costly than the usage of the Cloud bandwidth. As shown in Figure 7, the RU plots are steeper for RCS, SOO and SOO-CPLEX, with very small differences between them. More specifically, SOO achieves a lower RU compared to RCS with a decreasing difference ratio from 14.77% to 0.76%, following the increase in the number of IoT devices (M) at the Edge, which results in an increase of the data stream rates arriving to the Fog nodes. Furthermore, SOO achieves equal RU compared to SOO-CPLEX, for the experiments where M < 40000 IoT devices at the Edge. This corresponds to best-case execution for SOO, thus, SOO produces optimal results like SOO-CPLEX. On the other hand, when M is equal to 40000 and 45000 IoT devices, SOO-CPLEX outperforms SOO, with a small difference ratio up to 0.01%. This corresponds to worst-case execution for SOO, where SOO approximates the optimal solution. For SOO and SOO-CPLEX, Figure 8 and Figure 9 show that SOO achieves to balance between CRU and N RU to minimize the overall resource usage cost RU .

3) Scalability analysis: We assess the scalabilty of SOO against SOO-CPLEX in terms of execution time, i.e., the time it takes for either algorithm to find the best streaming operator placement, to rewrite the application graph based on this placement, and to deploy the resulting application graph between the Fog and Cloud. In this respect, we use as starting point the parameter settings for SOO worstcase execution with N = 10 Fog nodes, M = 40000 IoT devices and Bmax = 125000KB/s. To maintain the same ratio in parameter setting with respect to the equilibrium (13), we consider the scaling up ratio N N init , where Ninit = 10 Fog nodes, then we scale Bmax and M by multiplying their initial values with the scaling up ratio for each increase of N , where initially N = Ninit.

Besides the setting of SOO-CPLEX with OG = 0.0%, we additionally consider the setting of SOO-CPLEX with OG = 50% to enable SOO-CPLEX to balance between optimality and execution time. As depicted in Figure 10, for the different scaling up ratios, SOO has lower execution times, with a difference ratio ranging between 54% and 70%, compared to SOO-CPLEX with OG = 0%. Even when compared to SOO-CPLEX with OG = 50%, SOO has lower execution times with a difference ratio between 1% and 30%. In terms of the produced RU solution, Figure 11 shows that SOO fails to find the optimal solution compared to SOO-CPLEX with OG = 0%, but the approximation error is very small, ranging from 0.01% to 0.0003%, following the scaling-up ratio increase. On the other hand, when comparing to SOO-CPLEX with OG = 50%, SOO produces a better RU solution whatever the scaling-up ratio. V. RELATED WORK Algorithms [START_REF] Pietzuch | Network-aware operator placement for stream-processing systems[END_REF], [START_REF] Cardellini | Optimal operator placement for distributed stream processing applications[END_REF] solve the general resource allocation problem, where placement of operators is performed on peer resource nodes. These algorithms optimize some DSPA application performance metric (e.g. response time, availability, etc.) or some networkrelated metric (e.g. network bandwidth, network delay) and show a positive impact on application performance. Optimizing computational resource usage is not considered by these algorithms.

Neophytou et al. [START_REF] Neophytou | Poweraware operator placement and broadcasting of continuous query results[END_REF] propose the BOSe heuristic, which inspired our SOO heuristic. BOSe splits the processing load of continuous queries (CQs) between a central server and several mobile user devices in order to optimize the trade-off between data communication cost and data processing cost. These costs are expressed in terms of energy consumption of mobile devices. The results of the CQs take the form of individual data streams disseminated to the mobile devices over a shared broadcast medium. Similarly to SOO, BOSe relies on a greedy search of edge-cut moves to split the load of CQs. Unlike from SOO, in BOSe, moving an edge-cut of a data stream for a mobile user has an impact on the energy consumption of the other mobile users due to the broadcast medium; in SOO, dependency among streams is due to the shared Cloud bandwidth. Furthermore, BOSe does not consider a constraint on the computational resource usage of the mobile users, and it was not evaluated in terms of optimality.

Nardelli et al. [START_REF] Nardelli | Efficient operator placement for distributed data stream processing applications[END_REF] propose several heuristics to solve the operator placement problem with the objective to minimize response time, network resource usage, and to maximize the DSPA application availability. Some of these heuristics rely on meta-heuristics, such as tabu search, local search, etc. They use a penalty function that captures the cost of using a computing resource. However, this set of heuristics does not optimize the computational resource usage. Furthermore, Hiessl et al. [START_REF] Hiessl | Optimal placement of stream processing operators in the fog[END_REF] extend the operator placement problem of [START_REF] Nardelli | Efficient operator placement for distributed data stream processing applications[END_REF] by including the operator enactment cost and operator migration cost. However, this work does not consider the optimization of the computational resource usage, and it does not propose any efficient heuristic. It is worth noting these approaches address the operator placement problem formulated by Cardellini et al. in [START_REF] Cardellini | Optimal operator placement for distributed stream processing applications[END_REF] as an ILP problem and solved with CPLEX. This work also inspired our SOO-CPLEX solution.

Similarly to our approach, Planner [START_REF] Prosperi | Planner: cost-efficient execution plans placement for uniform stream analytics on edge and cloud[END_REF] introduces a heuristic for deploying DSPA applications between the Cloud and the Edge/Fog in order to minimize the network resource usage for reaching the Cloud. Planner relies on a minimum edge-cut algorithm to split separately each data stream processing path.

Compared with Planner, we account for the fact that not only the network resources to reach the Cloud but also the computational resources at the Edge/Fog are limited and shareable, thus it is necessary to ensure their efficient usage; hence we propose a more sophisticated resource model and algorithmic approach.

Finally, SpanEdge [START_REF] Sajjad | Spanedge: Towards unifying stream processing over central and near-the-edge data centers[END_REF] aims at reducing the response time and the network resource usage cost of data stream processing applications, however, it does not consider the computational resource usage. Additionally, it mainly proposes a software engineering approach, while it does not solve any instance of the operator placement problem.

VI. CONCLUSION

In this paper, we addressed the problem of scheduling streaming operators between Fog and Cloud nodes, in synergy with the variability of data stream rates produced at the Edge. We propose SOO, a resource-aware and time-efficient heuristic that takes into account the limited Fog computational resources, as well as congestion and delay issues on Fog-to-Cloud network resources. Evaluation results showed that SOO approximates the optimal resource usage cost solution while achieving excellent optimality, by managing the trade-off between the Fog computational resource usage cost and the Fog-to-Cloud network resource usage cost. Regarding scalability, SOO is timeefficient comparing to the optimal algorithmic solution, whatever the problem size. We are currently working on extending our problem formulation so as to take into account real-time response constraints of IoT applications. Additionally, as DSPA workloads may highly vary, we need to monitor at run-time the allocated resources and continuously schedule the deployment of DSPA computations over the Edge/Fog/Cloud.

Fig. 1 .

 1 Fig. 1. Edge-Fog-Cloud architecture example

9 ifB 17 M R[j] ← e jp 18 M [j] ← Gmig j k 19 B 20 RU ← RU + ∆ RU 21 U pdated ← U pdated ∪ S j 22 Pull

 9171819202122 ≤ Bmax then 10 ∆RUset ← edgeCutM ove(Selected, RM, M ) 11 Sort ∆RUset in increasing order 12 Pull ∆RU on top of ∆RUset 13 while ∆RU < 0 do 14 Get S j , e j k , Gmig j k corresponding to ∆ RU 15 ec j ← M R[j] 16 if B -|ec j | + |ec j k | ≤ Bmax and Updated.contains(S j ) == False then ← B -|ec j | + |ec j k | ∆RU on top of ∆RUset 23 Rewrite G to include all Gmig j (or Gmig jp ) ∈ M 24 Deploy the new G

Algorithm 2: edgeCutMove 1 5 Get 8 Get 4 Identify

 1584 Function edgeCutMove(Selected, RM, M, B): 2 ∆RUset ← ∅ 3 for S j ∈ Sraw do 4 ec j ← RM [j] RU j corresponding to edge-cut ec j 6 while ec j k is valid do 7 Gmig j ← M [j] Gmig j k ⊆ Gmig j delimited by ec j k 9 Compute cmu F j and normalize to CRU j 10 Compute nbu F j C and normalize to N RU j 11 RU jp ← CRU j k + N RU j k 12 ∆RU ← RU j k -RU j 13 ∆RUset ←∆RUset ∪∆RU 14 Keep and map ∆RU, S j , Gmig j k and ec j k 15 ec j ← ec j k 16 Get ec j k preceding ec j ∈ Gmig j 17 return ∆RUset Algorithm 3: SOO::RUminCut 1 Function RUminCut(Sraw, RM, M, RU, B, Grep): 2 for S j ∈ Sraw do 3Get Fog node F j to serve S j Gsat j ⊆ Grep while cmu F j ≤ cm F j 5

Fig. 3 .

 3 Fig. 3. DSPA application used in the evaluation

Fig. 4 .

 4 Fig. 4. Overall resource cost, N=30 Fog nodes while scaling the IoT devices

Figure 5

 5 Figure5and Figure6show that SOO finds a balance between CRU and N RU in order to minimize RU . Given that RCS resorts minimally to the Fog resources, when M ≤ 20000 IoT devices the resulting data stream rate that reaches the Cloud through the Fog nodes is lower than Bmax, hence no processing is moved to the Fog and CRU is null, as depicted in Figure5. When comparing to SOO, such cost can be considered as cost-efficient, but the counterpart in terms of N RU is very high, as depicted in Figure6. However when M > 20000 IoT devices, CRU for RCS is monotonically increasing for satisfying the constraint B ≤ Bmax.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Computational cost, N=30 Fog nodes while scaling the IoT devices

Fig. 7 .

 7 Fig. 7. Overall resource cost, N=10 Fog nodes while scaling the IoT devicesFigure 8 and Figure 9 show that, for RCS, CRU is null and constant and N RU monotonically increases when M ≤ 20000 IoT devices, since RCS has the preference of using the Cloud network bandwidth over the Fog computational resources when B ≤ Bmax. On the other hand, when M increases higher than 20000 IoT devices, CRU monotonically increases to ensure the constraint B ≤ Bmax.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Computational cost, N=10 Fog nodes while scaling the IoT devices

Fig. 10 .

 10 Fig. 10. execution time by by scaling N, Bmax and M

Fig. 11 .

 11 Fig. 11. Resource usage cost by scaling N, Bmax and M

TABLE I PARAMETERS

 I OF THE DSPA APPLICATION OF FIGURE3

	Operators	O 1	O 2	O 3	O 4	O 5
	cselx	0.8	0.96	0.672	0.9408 0.84672
	sum csel cx 1.5	2.78	4.412	5.6216 7.40912