Martin Rosalie

Matthias R Brust

Grégoire Danoy

Serge Chaumette

Pascal Bouvry

Coverage Optimization with Connectivity Preservation for UAV Swarms applying Chaotic Dynamics

Keywords: cooperative UAV, multilevel swarm, mobility model, ant colony optimization, chaotic dynamics

Cooperative usage of multiple UAVs as a swarm can deliver high-quality surveillance performance. However, the communication capabilities within the UAV swarm must be maintained for local data propagation to swarm members in favor of achieving an efficient global behavior. In this paper, we address the problem of optimizing two adversary criteria for such a UAV swarm: (a) maximizing the area coverage, while (b) preserving network connectivity. Our approach, called CACOC 2 , solves the problem with a novel chaotic ant colony optimization approach, which combines an Ant Colony Optimization approach (ACO) with a chaotic dynamical system. CACOC 2 employs swarming behavior to obtain UAV clustering that result in maximized area coverage and preserved network connectivity. We show by extensive simulations how the size of the UAV swarm influences the coverage and connectivity. A metrics comparison chart shows the correlation of coverage and connectivity metrics.

I. INTRODUCTION

Advances in UAV technologies allow the development of new applications for both civilian and military domains. Highend UAVs are delivered with sophisticated on-board systems, extended flight autonomy, increased computing power, ad hoc networking capabilities, and with long-lasting batteries [START_REF] Hauert | Communicationbased leashing of real flying robots[END_REF]. These improvements make UAVs capable of being deployed as a flying ad hoc network potentially forming a cooperative swarm of UAVs [START_REF] Brust | VBCA: A virtual forces clustering algorithm for autonomous aerial drone systems[END_REF], [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF]. Advantages of a UAV swarm are for instance that the number of participating UAVs can be adapted as needed and the swarm behavior ensures the resilience of the swarm's communication network in case of hardware failure or harsh weather conditions.

A considerable amount of UAV swarm research focuses on how to deliver high surveillance performance while preserving resilient communication capabilities within the swarm [START_REF] Danoy | Connectivity stability in autonomous multi-level UAV swarms for wide area monitoring[END_REF], [START_REF] Messous | Network connectivity and area coverage for UAV fleet mobility model with energy constraint[END_REF], [START_REF] Yanmaz | Connectivity versus area coverage in unmanned aerial vehicle networks[END_REF]. This coverage optimization problem with connectivity preservation is tremendously important for UAV swarms because the coverage performance highly depends on the overall connectivity dynamics in the swarm. For instance, coverage area coordination and intruder detection notification can only be effectively executed if UAV connectivity is warranted. However, there is a trade-off between coverage and connectivity. For high coverage, the UAVs should intelligently explore the area, while a limited transmission range requires the UAVs to stay in each other's proximity. Therefore, the potential for the UAV swarm to obtain the maximum coverage performance decreases considerably when considering the connectivity requirements. With the UAVs capacity to move freely in the three-dimensional space, an often applied technique on how to obtain superior results for this coverage-connectivity problem is the design of proper mobility models that aim to maximize both criteria (e.g., [START_REF] Danoy | Connectivity stability in autonomous multi-level UAV swarms for wide area monitoring[END_REF]). In this work, we propose CACOC 2 (Chaotic Ant Colony Optimization for Coverage with Connectivity), which extends the single criteria Chaotic Ant Colony Optimization for Coverage (CACOC) [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF] with a swarming behavior to maintain more stable UAV clusters to deliver connectivity resilience within the swarm.

This work is organized as follows. In Section II, we report on related work and in Section III, we describe the original CACOC UAV mobility model and the novel extension for coverage and connectivity optimization, CACOC 2 . Section IV, provides the experimental setup and settings as well as a description of the metrics used. In Section V we report on the results obtained in the experiments, and we finally conclude our work in Section VI.

II. RELATED WORK

Area coverage optimization with connectivity preservation is a tremendously important problem because of its relevance in real-world applications. A commonly used approach to reach superior results for this problem is the design of mobility models that are concerned with coverage and connectivity.

Yanmaz [START_REF] Yanmaz | Connectivity versus area coverage in unmanned aerial vehicle networks[END_REF] proposes a connectivity-and coverageoptimized mobility model and measures the trade-off between connectivity and spatial coverage. The measure spatial coverage (areal coverage) is defined as the percentage of the sensed target area in a given amount of time, and connectivity is defined as the percentage time the UAVs are connected to a sink averaged for all UAVs.

Yanmaz et al. [START_REF] Yanmaz | A discrete stochastic process for coverage analysis of autonomous UAV networks[END_REF] study single-hop and multi-hop scenarios. Results show that if the network density is high enough, the coverage optimization has less impact on the good performance. However, if the network density is low, a combination of connectivity optimization and coverage optimization is advantageous. Yanmaz et al. [START_REF] Yanmaz | Area coverage with unmanned vehicles: A belief-based approach[END_REF] are interested in UAV movements such that they cover the entire area within a given time period. The introduced belief-based approach uses local information to execute its actions.

Hauert et al. [START_REF] Hauert | Communicationbased leashing of real flying robots[END_REF], [START_REF] Hauert | Ant-based swarming with positionless micro air vehicles for communication relay[END_REF] propose a purely communication-based approach to swarming. The authors use artificial evolution to design the mobility and mission model. A second approach deals with army-ant pheromone trails during foraging to be applied to the UAV swarm for the deployment, maintenance and, retraction of communication networks. The main objective is to cover and maintain connectivity between the base and the user.

Brust et al. [START_REF] Brust | VBCA: A virtual forces clustering algorithm for autonomous aerial drone systems[END_REF] propose VBCA, a virtual forces clustering algorithm, which imitates the VSEPR model from molecular geometry for the arrangement of UAVs in a clustered swarm. The UAV's position is determined by the distance and role of its neighboring UAVs. VBCA assigns the role of a clusterhead to one UAV. This central UAV acts as a connector influencing the entire topology of the network geometry while individual UAVs are only affected by their direct neighbors. VBCA is maximizing the volume coverage, while maintaining advanced connectivity within the clustered UAV swarm. Most approaches described in this section focus on areal coverage from a plane, i.e. UAVs are flying at a similar altitude. As an exception, VBCA [START_REF] Brust | VBCA: A virtual forces clustering algorithm for autonomous aerial drone systems[END_REF] deals with a volume coverage approach.

Messous et al. [START_REF] Messous | Network connectivity and area coverage for UAV fleet mobility model with energy constraint[END_REF] approach focus on the coverageconnectivity problem with a base station and additional energy constraints (alpha-based mobility model). The decision about the next movement takes into account communication constraints and remaining energy.

The decision making is based on value table where the number of neighbors, energy level and the hop count to the base station determine the next action.

In previous work we address the coverage problem of an area for a swarm of UAVs [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF]. Rosalie et al. [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF] propose to combine Ant Colony Optimization with chaotic dynamics to improve the coverage of a given area. However, in the described approach connectivity constraints are not considered. Table I summarizes the mobility models used as a method to optimize solutions for the UAV coverageconnectivity problem. We also classified CACOC 2 according to Table I to illustrate the fundamental differences of our approach to existing ones.

III. CHAOTIC MOBILITY MODELS

In this section, we first briefly summarize CACOC before describing CACOC 2 , which includes our extension to include connectivity constraints into the coverage optimization approach from CACOC. Both mobility models rely on Ant Colony Optimization (ACO) [START_REF] Dorigo | Ant colony optimization[END_REF] which aim at imitating the behavior of ants communicating in their colony with pheromones to accomplish complex tasks collaboratively. Ants deposit these pheromones to guide and inform the other members of the colony, this indirect communication process is also referred to as stigmergy. Formal abstractions of this model are used to solve a diversity of optimization problems [START_REF] Dorigo | Ant colony optimization[END_REF]. Since the pheromones are used to improve a solution, random initial solutions are used to initiate the optimization process. The main idea of CACOC [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF] is to take benefit from the structured chaotic dynamics instead of the traditionally used random process. To do so, the CROMM (Chaotic Rössler Mobility Model) is introduced [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF] as a fully deterministic mobility model dedicated replacing the random part of an ant colony algorithm.

The CROMM, CACOC and CACOC 2 mobility models are described in more details hereinafter. In all three models a UAV moves with a constant speed and starts to choose its direction at each step (left, ahead or right).

A. CROMM

The dynamical Rössler system [START_REF] Rössler | An equation for continuous chaos[END_REF] is a well-known Ordinary Differential Equations (ODE) system

   ẋ = -y -z ẏ = x + ay ż = b + z(x -c) (1)
producing chaotic dynamics: the solution is a chaotic attractor (Fig. 1 of [START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF]). From this attractor, we can extract a map (Fig. 1) describing the dynamical properties of the system (for details on the Rössler attractor, the Poincaré section used and the first return map properties see [START_REF] Rosalie | Templates and subtemplates of Rössler attractors from a bifurcation diagram[END_REF]). In CROMM, the first return map gives the direction of the each UAV: To initialize the system, we choose a different initial condition for each UAV to solve the Rössler system. Giving nonequal initial conditions leads to the same attractor as a solution and to the same first return map. However, the points constituting the return maps are not the same in terms of order of appearance.

0 1 0 1 R p R + p L L p R A R L A ρ n+1 ρ n period 1 period 2
Fig. 1. First return map of the Rössler attractor. This map indicates the UAV directions: L (left), A (ahead) and R (right).

B. CACOC

When there is no pheromone to guide the UAV, CACOC uses CROMM to obtain the direction of the UAVs. This permits to explore non-visited area. Otherwise, if there are some pheromones, the UAV chooses its next direction according to the total amount of pheromones sensed around him.

We proposed to use again the chaotic dynamic with the next value in the return map to make this choice. Thus, p L , p A and p R values are a percentage partition inversely proportional to the total amount of pheromones respectively sensed on the left, ahead or right:

• if ρ n < p R then direction is right; • if p R < ρ n < p R + p L then direction is left;
• else the direction is ahead. Thus, the return map values are used to choose the next direction for each step of the CACOC model (Fig. 1 describes the choice when there are some pheromones around the UAV). The use of pheromones permits to have a system resilient to UAVs failure or loss. If a UAV is out of the system, it will no more deposit pheromones.

C. CACOC 2

The principle of the "boid" movements has been introduced by Reynolds [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF]. Three rules reproduce the behavior of a bird in a swarm: collision avoidance, velocity matching, and flock centering. For CACOC 2 , we combine this model with the "boids" model [START_REF] Brust | A networked swarm model for uav deployment in the assessment of forest environments[END_REF]. As the UAVs have a constant speed, we will not use the velocity matching rule. The purpose of CACOC is to cover a wide area where the UAVs use repulsive pheromones to explore non-visited areas. We then decide to consider that CACOC is another way to implement the first rule of collision avoidance because the pheromones deposit prevents UAVs to move towards the same direction. Thus, we add the third rule of flock centering to force the UAVs to maintain connectivity. As the "boid" model operates with forces, our model only has two forces:

• f CACOC is a vector for the CACOC force giving a direction (L, R or A) that is translated as a vector; • f flock is a vector for the flock centering force computed with the average value of the last vector used for the other UAVs close to the UAV considered. We then add these two forces and normalize the obtained vector to have the vector d with the constant speed s:

d = s × f CACOC + f × f flock || f CACOC + f × f flock || 2 . ( 2
)
In this equation f is a parameter to evaluate the influence of the flocking force on the CACOC 2 model. We plan to variate this force f from 0.1 to 0.6 by a 0.1 step to calibrate our force model. The purpose is also to evaluate how this connectivity force influences the performance of CACOC 2 .

IV. EXPERIMENTS

In this section, we describe the experimental setup and explain the selection of the comprehensive set of metrics.

For the experiments, we have analyzed the parameters of the simulations described in Section II and crystallized the most common settings used to be chosen for our experiments. For instance, Yanmaz [START_REF] Yanmaz | Connectivity versus area coverage in unmanned aerial vehicle networks[END_REF] uses between 1 and 20 UAVs, while the chosen transmission ranges are 68 m, 126 m, 279 m, 500 m, 1000 m, 1500 m, and 2000 m with an area length of 4000 m. In comparison Yanmaz et al. [START_REF] Yanmaz | Area coverage with unmanned vehicles: A belief-based approach[END_REF] use between 1 to 40 UAVs, with a fixed transmission range of 500 m and squared simulation area with length 4000 m. Messous et al. [START_REF] Messous | Network connectivity and area coverage for UAV fleet mobility model with energy constraint[END_REF] vary the UAVs from 5, 10, 15, 20, 30, while the transmission range is 400 m and the environment is a 4000 m × 4000 m square area.

A. Experimental setup

The simulation area is a 4000 m × 4000 m square, divided into square cells of 10 m × 10 m. The UAVs have a constant speed of 10 m/s and all depart from the base station located in the middle of the bottom edge of the map, i.e., position (200, 0). At each simulation step, each UAV can conduct one of the following three actions: (1) ahead: the UAV keeps the same

right: the UAV turns right with -45 • angle. To prevent collisions between the UAVs, we assume that each of them has a different flight altitudes [START_REF] Kuiper | Mobility models for UAV group reconnaissance applications[END_REF]. The mobility model with varying parameters has been evaluated with a swarm of 10 and 20 autonomous UAVs equipped with wireless communication capabilities (Tab. II). We ran 30 independent simulations of 4000 steps to obtain significant results.

To evaluate the performance of the different models in terms of area coverage and network connectivity, the following metrics have been used: coverage and recent coverage ratio, fairness, the number of connected components, the size of the giant component, 2-connectivity of the giant component and edge-connectivity. All seven metrics are described in detail in the next section.

B. Metrics a) Coverage:

The coverage is the portion of the total area visited during the whole simulation. To have a representative value of the coverage, we choose the coverage value at the end of the simulation. It indicates how efficient the models are to visit the total area. We also want to evaluate their initial behavior while there is no guidelines for UAVs. We extract the slope of a linear regression (a × t) considering the 500 first steps.

b) Fairness of coverage: The fairness of the coverage measures if all cells are regularly and equally scanned. This is computed by the standard deviation of their respective number of scans [START_REF] Schleich | UAV fleet area coverage with network connectivity constraint[END_REF]. To evaluate the fairness during the whole simulation, we perform a linear regression (a × t + b) using the last 3500 steps. c) Recent coverage: This metric introduced in [START_REF] Danoy | Connectivity stability in autonomous multi-level UAV swarms for wide area monitoring[END_REF] represents the percentage of coverage during the last 100 iterations. These 100 steps correspond to the pheromones' evaporation time. We exclude the 100 first iterations of our simulation to compute the mean value of the recent coverage.

d) Giant component: The giant component of a network is the connected subgraph (component) with the largest number of nodes in a network. We measure the giant component size of a swarm to gain insight about the size and variation of the largest connected component of the moving UAV swarm. In a realistic scenario, UAVs will disconnect from the swarm core due to obstacles avoidance or other spontaneous maneuvers. This means that disconnections resulting in isolated UAVs can occur.

e) Number of components: A component is defined as an isolated (or disconnected) subgraph of the considered network. Our approach can result in disconnections of not only isolated UAVs but groups of UAV. Measuring the number of groups (also components) during the lifetime of the network does complement the understanding of the networks' dynamic behavior already given by the giant component.

f) k-edge-connectivity for the giant component: A network has connectivity k (or k-connectivity) if k is the size of the smallest subset of nodes such that the network becomes disconnected if the subset is deleted. We only calculate the 2-connectivity of the giant component because the frequent isolated nodes or components of the UAV swarm would have a negative and unreasonable influence of the k-connectivity measure. Thus, if the giant component is 2-connected we note 1, else we note 0. At the end of the simulation, we compute the average value of this metric to obtain the percentage of the simulation time when the giant component is 2-connected. g) Edge-connectivity: The purpose of this metrics is to evaluate how many edges can be removed to prevent this component to be disconnected. This is useful to evaluate how the swarm is resilient to communication issues. It comes as a complementary measure of the 2-connectivity to highlight the communication quality of the swarm.

V. RESULTS

The results obtained show the influence of the number of UAVs on the coverage and connectivity quality of the swarm. Summarizing the results, we produced a metrics-comparison chart which shows the correlation between specific metrics to each other. We discuss the connectivity metrics and afterward the coverage metrics. Figures 2, 3, 4 and5 show the box plot of the data for all the measured metrics and a smooth density estimation.

A. Connectivity metrics

We first describe the results contained in Fig. 2 and Fig. 3. Concerning the connected components, the experiments underline that for force equal to 0.4, 0.5, and 0.6, the number of connected components is very low: lower than two connected components for 10 and 20 UAVs. For these forces and 20 UAVs, the average value is close to one which means that the UAVs mainly remain connected. This is confirmed by the giant component metrics because the size of the giant component is in average equal to the number of UAVs for forces equal to 0.4, 0.5 and 0.6 for 20 UAVs. However, it is only the case for forces equal to 0.5 and 0.6 for 10 UAVs. On the other hand, when the force is equal to 0.1, the number of UAVs in the giant component corresponds to about 50% of the total number of UAVs deployed.

After discussing the size of the giant component, we will use the two last metrics to analyze its properties. First, the 2-connected components are inversely proportional to the number of connected components with a smaller standard deviation for the low forces (0.1 and 0.2). For forces equal to 0.5 and 0.6, we observe that the values are close to 1. It means that almost 100% of the time, the swarm is two-connected. Apparently, the value is similar for 10 or 20 UAVs. The edge connectivity of the giant component indicates how many communication links can be removed to maintain connectivity between the nodes of the components. This value remains very low for low force values: 0.1 and 0.2 and then it increases smoothly up to the 75% of the total number of UAVs for both (20 UAVs and 10 UAVs). For forces equal to 0.5 and 0.6 the edge connectivity of the giant component is higher than half of the number of UAVs. This means that our mobility model ensures a very resilient communication network when the force is above 0.4.

B. Coverage metrics

In this subsection, we analyze the coverage metrics depicted by Fig. 4 and Fig. 5. We first consider the percentage of total area covered after 4000 steps for an optimal model. In this theoretical case, we consider that for each step the UAV covers a not already visited cell of the area. Thus, for 10 UAVs, the optimal value for this metric is 25% of the total area (10 × 4000/(400 × 400) = 0.25). Thus, the average values of the results obtained here for 10 UAVs are in between 20% and 21% to the total coverage. On top of that, the force value has no impact on this metric. However, if we double the number of UAVs to 20, the optimal value is 50%. The average percentage result is around 37% for forces lower than 0.5 but it decreases to 35% when the force is stronger. The increase of UAVs does not seem to be efficient considering only this metric. From the value collected on the coverage ratio, we also compute the slope of coverage. Thus, there is a strong relation between the slope of coverage and coverage after 4000 steps. For this metric we can underline that for 20 UAVs, the best results are for forces equals to 0.2 and 0.3.

The recent coverage indicates how the area are recently visited (during 100 steps) by the UAVs. If we consider 10 UAVs, the optimal value is the following one: 10 UAVs for 100 steps are divided by the total number of covered area: 10 × 100/(400 × 400) = 0.00625. For a force equal to 0.1 the value is close to this optimal value, and it decreases slowly for the force 0.2 and 0.3. Then it decreases faster for the other forces. For 20 UAVs, the results are very similar to the previous one. The expected optimal value for recent coverage is 20 × 100/(400 × 400) = 0.0125 and the results are below 0.006. This means that the increase in the number of UAVs is not sufficient to reach better recent coverage regarding the optimal value of the corresponding number of UAVs. This result is confirmed by the fairness metrics for 20 UAVs where the fairness slope is higher for forces equal to 0.5 and 0.6. However, for 10 UAVs this fairness slope is almost the same.

C. Synthesis between coverage and connectivity metrics

Based on the previously presented results, our approach exhibits superior performance for 10 UAVs regarding recent coverage but does not produce similar results for 20 UAVs. Also, the best performing models on this from a coverage point of view are the models with forces equal to 0.1 and 0.2. We explain this phenomenon by the low force that might generate numerous components where UAVs come back on already visited areas before the evaporation time of the pheromones exceeds. As the pheromones are repulsive, they prevent UAVs to reach an already visited area. Conversely, as the force is strong, the UAVs remain connected and overlap their covered area. This behavior is confirmed by the connectivity metrics where the size of the giant component is almost equal to half of the number of UAVs while the average number of components is two. This splitting into two swarms is something that frequently happens when "boids" avoid obstacles.

The results also showed that the values for 20 UAVs do not reproduce the results for 10 UAVs (regarding their respective optimal values). This implies that although we can expect to have significant benefits in using a UAV swarm with a higher number of UAVs, beyond a certain threshold it does not further improve the overall performance.

VI. CONCLUSIONS

In this paper, we introduced the CACOC 2 mobility model for UAV swarms. CACOC 2 combines CACOC and a flocking model based on Reynolds "boids" where a flocking force is added to each CACOC direction choice. Our experimental results have permitted to calibrate the flocking force to have a mobility model combining coverage and connectivity constraints. Thus we have empirically defined the parameterization to obtain a mobility model efficient with 10 or 20 UAVs to cover a wide area with connectivity constraints. This parameter f permits to equilibrate the swarm behavior with acceptable coverage performances. In future works we plan to introduce CACOC 2 in a realistic UAV simulator to introduce the collision avoidance necessary for UAVs.

Fig. 3 .

 3 Fig. 3. Connectivity metrics for 20 UAVs.

Fig. 4 .

 4 Fig. 4. Coverage metrics for 10 UAVs.

TABLE I MOBILITY

 I MODELS PROPOSED FOR THE UAV COVERAGE-CONNECTIVITY PROBLEM.

	Mobility model	Reference
	Pheromone and clustering based connectivity Danoy et al, Rosalie et al. [4], [3]
	Virtual forces-based approach	Brust et al., Yanmaz, Messous et al. [6], [2], [5]
	First-order flight model	Hauert et al. [1], [7]
	Belief-based mobility model	Yanmaz et al. [8]
	Heuristic-based mobility model	Messous et al. [5]
	Pheromone and forces-based approach	CACOC 2 (our approach)

• if ρ n < 1/3 then direction is right;• if 1/3 < ρ n < 2/3 then direction is left;• else the direction is ahead. Such a partition provides a reasonable pattern for exploration[START_REF] Rosalie | From random process to chaotic behavior in swarms of UAVs[END_REF] including straight forward moves and large circular patterns (see Fig.1for period 1 (AAA) and 2 (RARARA) orbits).

ACKNOWLEDGMENTS

The experiments in this paper were using the HPC facilities of the University of Luxembourg [17] -see http://hpc.uni.lu.


Alexandre Veith
email: alexandre.veith@ufrgs.br

Da Silva

Julio C S Anjos
email: jcsanjos@inf.ufrgs.br

Edison Dos * De Freitas

Pignaton

Thomas J Lampoltshammer
email: thomas.lampoltshammer@donau-uni.ac.at

Claudio F Geyer
email: geyer@inf.ufrgs.br

Strategies for Big Data Analytics through Lambda Architectures in Volatile Environments

Keywords: Internet of Things (IoT), Scheduling, Batch processing, Stream processing, Cloud computing, Grid computing

Expectations regarding the future growth of Internet of Things (IoT)-related technologies are high. These expectations require the realization of a sustainable general purpose application framework that is capable to handle these kind of environments with their complexity in terms of heterogeneity and volatility. The paradigm of the Lambda architecture features key characteristics (such as, robustness, fault tolerance, scalability, generalization, extensibility, ad-hoc queries, minimal maintenance, and low-latency reads and updates) to cope with this complexity. The paper at hand suggest a basic set of strategies to handle the arising challenges regarding the volatility, heterogeneity, and desired low latency execution by reducing the overall system timing (scheduling, execution, monitoring, and faults recovery) as well as possible faults (churn, no answers to executions). The proposed strategies make use of services such as migration, replication, MapReduce simulation, and combined processing methods (batch-and streaming-based). Via these services, a distribution of tasks for the best balance of computational resources is achieved, while monitoring and management can be performed asynchronously in the background.

INTRODUCTION

The concept of the Internet of Things (IoT) can be described as the seamless fusion of virtual environments and contained objects with their real-world counterparts [START_REF] Uckelmann | An architectural approach towards the future internet of things[END_REF]. In return, this makes the creation of robust, flexible, and dynamic applications imperative, in order to handle heterogeneous and volatile environments. A major aspect in this regard is represented by the challenge to handle vast amounts of data, including all relevant processing steps, in particular data analytics. Due to this fact, the area of big data analytics has attracted high levels of attention of industry and academia alike. This fact is represented by the total increase of datadriven projects by 125% during the period 2014-2015. 1 So far, the majority of big data deployments were initially using batch processing-oriented approaches (i.e. the entire amount of data is gathered, stored, and afterwards processed step-by-step) [START_REF] Hu | Toward Scalable Systems for Big Data Analytics: A Technology Tutorial[END_REF]. However, batch processing has no support for low-latency scenarios. Thus, a new model called stream processing or oriented-to-events processing has witnessed a huge increase in volume and 1 IDGhttp://www.idgenterprise.com/ availability [START_REF] Tudoran | JetStream: Enabling High Performance Event Streaming Across Cloud Datacenters[END_REF]. The handled events are usually characterized by a small unit size (in the order of kilobytes), but have overwhelming collection rates, due to the continuous data flow. To overcome this issue, new stream processing frameworks have emerged, such as Apache Storm, Spark, Flink or S4.

Over time, stream processing and its associated processing engines have evolved up to the point of the introduction of the Lambda Architecture (LA) paradigm [START_REF] Marz | Big data : principles and best practices of scalable realtime data systems[END_REF]. Lambda Architectures are designed to handle vast amounts of data in conjunction with both batch and stream processing methods. While batch processing helps to reduce latency, to improve data transfer, to provide faulttolerance, as well as a comprehensive and accurate view upon the data, stream processing provides capabilities to deal with real-time data. Thus, the rise of LAs are directly related to the rapid growth of Big Data real-time analytics.

According to [START_REF] Ewen | Iterative parallel data processing with stratosphere: an inside look[END_REF], the Lambda Architecture paradigm is the starting point of the so-called 4 th Generation of Data Processing Engines that comprise several features regarding the design and implementation of processing engines for massive data, such as robustness, fault tolerance, low latency of reading and updating, scalability, generalization, extensibility, ad-hoc queries, and minimal maintenance. To achieve these properties, the architecture foresees a Big Data system to be constructed in several layers. [START_REF] Anjos | SMART: An Application Framework for Real Time Big Data Analysis on Heterogeneous Cloud Environments[END_REF] presented the SMART platform, which is a modular framework for Big Data analysis. SMART considers a large variety of data sources, such as distributed datasets and social networks, where there is a clear need for standardization. The Dispatcher module (DM) in the SMART platform is an orchestration system that needs several policies to the managing data and tasks. This paper aims at the improvement of the decision-making engine of the Dispatcher module based on the computational capacity of the machines via scheduling strategies and advanced execution setups regarding data streams to achieve an optimal distribution of tasks for the best balance of computational resources. This paper is structured as follows: Section 2 sets out the state-of-the-art for data-intensive computation, establishes the framework in this landscape, compares it to others and demonstrates how it works in relation to others considering heterogeneous infrastructures, hybrid infrastructures, and hybrid engines. Section 3 presents the SMART platform and its main modules. Section 4 details the Dispatcher Module and discusses the strategies required to overcome the environmental limitations of this module. Section 5 concludes the paper and reports opportunities for future work.

RELATED WORK

Heterogeneous Infrastructures

JetStream is a set of strategies for efficient transfers of events between cloud data centers [START_REF] Tudoran | JetStream: Enabling High Performance Event Streaming Across Cloud Datacenters[END_REF]. JetStream is self-adapting regarding streaming conditions. It aggregates the available bandwidth and enables the routing of data through cloud sites. The study by [START_REF] Tudoran | JetStream: Enabling High Performance Event Streaming Across Cloud Datacenters[END_REF] focuses on event transfers between inter-and intra-nodes. The authors propose an adaptive cloud batching in form of an algorithm that aggregates the streams in batches, resulting in latency reduction. However, it just considers the latency and not the volatility. The work concentrates on environments where the computational resources can break away unexpectedly and the scheduling policies must be adapted to it.

SMART [START_REF] Anjos | SMART: An Application Framework for Real Time Big Data Analysis on Heterogeneous Cloud Environments[END_REF] is a platform that offers an efficient architecture for Big Data analysis applications for small and medium-sized organizations. Its implementation considers heterogeneous data sources and aims at data analysis scenarios in geo-distributed environments, considers cost, fault tolerance, network overhead, I/O throughput, as well as the minimization of data transfers between computational resources. Yet, these parameters are not enough to work with volatile environments, especially regarding stream processing. To overcome these environment limitations, it is necessary incorporate information from physical components, such as memory, CPU speed, and storage. Thus, the overall capacity impacts the overall performance. In addition, regarding the volatility, replication must be incorporated as a fault control mechanism.

Similarly, [START_REF] Pham | CIRUS: an elastic cloud-based framework for Ubilytics[END_REF] purpose a generic, extensible, scalable, fine-grained, and re-configurable multi-cloud framework. It is based on a lightweight kernel and provides a hierarchical Domain Specific Language (DSL). The DSL allows for a fine-grained level of administration. However, the proposed solution does not control the workload at the nodes and possible faults, as the Deployment Manager is just an interface to set the devices and the Virtual Machines (VMs).

Hybrid Infrastructures

BIGhybrid summarizes the main features of a Hybrid MR environment based on the merge of two environments, namely a Cloud (MR-BlobSeer) environment and a Desktop Grid (BitDew-MapReduce) environment [START_REF] Anjos | BIGhybrid: a simulator for MapReduce applications in hybrid distributed infrastructures validated with the Grid5000 experimental platform[END_REF]. The Global Dispatcher located outside the Desktop Grid (DG) as well as of the cloud environment features middleware functionality for handling task assignments and input data from users. It is a distributed data storage system that manages policies for data splitting and distribution in batch applications such as MapReduce. The working principle is similar to the publish/subscribe service, where the system obtains data and publishes the computed results. This approach has several drawbacks, if applied to stream processing, due to delays regarding the processing of responses.

HybridMR is a model for the execution of MapReduce on hybrid computation environments (Cloud and DG) developed by [START_REF] Tang | HybridMR: a new approach for hybrid MapReduce combining desktop grid and cloud infrastructures[END_REF]. Two innovative solutions are proposed to enable such large-scale data-intensive computation: (i) HybridDFS, which is a hybrid distributed file system. HybridDFS features reliable distributed storage that alleviates the volatility of desktop PCs (i.e., fault tolerance and file replication mechanism); and (ii) a Node priority-based fair scheduling (NPBFS) algorithm has been developed to achieve both data storage balance and job assignment balance by assigning each node a priority through quantifying CPU speed, memory size, as well as input and output capacity. The NPBFS approach is very interesting because it uses some miscellaneous environment variables to schedule the tasks. Although regarding stream processing, its application is not possible due to the high flow latency. HybridMR just uses the flow rate to deploy the tasks, however, the rate does not consider particular task information.

Hybrid Engines

Apache Spark is a framework introduced by Zaharia et al. ( 2012) that uses resilient distributed datasets (RDDs) and enables efficient data reuse in a broad range of applications. RDDs are fault-tolerant, parallel data structures that are designed to allow users to keep intermediate results in memory, control their partitioning to optimize data placement, and manipulate them through a valuable set of operators. [START_REF] Liao | An enforcement of real time scheduling in Spark Streaming[END_REF] presented some scheduling inefficiencies related to the time window that constructs the RDD. The batch interval needs to be dynamically adjusted, so that fluctuations within the data rate can be handled in a production environment and the total delay of every event can be controlled within a certain range for real-time scenarios.

Apache Flink, initially developed by [START_REF] Alexandrov | The Stratosphere platform for big data analytics[END_REF], enables massively parallel in-situ data analytics, using a programming model based on second order functions. Today, Apache Flink is the state-of-the-art processing engine according to [START_REF] Ewen | Iterative parallel data processing with stratosphere: an inside look[END_REF]. The scheduling policies are designed to work at commodities environments (i.e., clusters and cloud). Commodities strategies do not work well with dynamic environments, as argued by [START_REF] Peng | R-Storm: Resource-Aware Scheduling in Storm[END_REF] and [START_REF] Eskandari | P-Scheduler: Adaptive Hierarchical in Apache Storm[END_REF]. It is essential for heterogeneous computing resources to acknowledge the surrounding environment.

Summingbird by [START_REF] Boykin | Summingbird: A Framework for Integrating Batch and Online MapReduce Computations[END_REF] integrates batch and online analysis with the aid of a hybrid processing model, where access can be provided efficiently and seamlessly for aggregations across of long time spans while maintaining up-to-date values with a minimal latency. However, Summingbird does not provide access to the Message Queue writing in Hadoop, it only has knowledge of that has been recorded. The scheduling policies are abstracted and the Hadoop and Storm systems handle the management. This section has presented actual research opportunities in relation to the combination of volatile and heterogeneous environments, as well as scheduling improvements. Currently, stream processing only has been performed in heterogeneous environments, while batch processing was reserved for volatile environments. Overall, processing engines do not deal well with heterogeneity and volatility. In fact, most engines were designed to run in clusters and cloud computing environment. This fact makes a Round Robin solution attractive for the scheduling policy. Nonetheless, in complex environments such as Desktop Grid it is not possible to efficiently employ it. The restrictions are related to the task and node heterogeneity, as well as to network bandwidth.

SMART ARCHITECTURE OVERVIEW

The following section provides a brief overview of the layered architecture that is required to deploy a SMARTbased environment. Figure 1 presents the required four main modules: Global Collector, Global Dispatcher, Core Engine, and Global Aggregator.

The Global Collector layer handles the management and coordination of the sensing modules. It is responsible for obtaining data from several sources and maintaining the data integrity mechanisms. The data integrity mechanisms filter possible noises in the hardware devices. The data is collected and serialized under a standard TCP/IP, which forms the communication stack for the Global Dispatcher.

In the Global Dispatcher, the data is decoupled from the lower layers in the message queue mechanism. It is put in a FIFO queue so that it can be distributed to severs in accordance to the availability of their resources in both Cloud/Multi-Cloud and Grid/Multi-Grid environments. The optimization layer analyses the volume of input data and employs the Decision Engine to make decisions about scheduling tasks and data through distinct environments. A simulation process implements an execution time prediction that will be used by the Decision Engine to improve the accuracy of the scheduling mechanism. The Core Engine must support hybrid systems, i.e., provision of streaming and batch computations at the same time. Thus, the Flink framework is an potential system that is worth considering. The MR-BitDew is another framework, which can improve computational performance, with the use of Volunteer Computing (VC) in a hybrid infrastructure. SMART allows computational resources to be taken from Cloud/Multi-Cloud, and Multi-Grid environments. A Client User API provides an easy method for users to submit their applications and indicate the data sources. The Client UI is a security interface that provides a single-user identification through an encrypted key. A key which is keep by the users is employed in the Encryption-Decryption Engine to ensure the data is safe. The intermediate results, processed in the Core Engine, are serialized for the Global Aggregator that must carry out the data consolidation. The Data Integration module supports the data integrity and data integration. The last phase of the data processing is designed to generate an iterative execution and provide the results of the consolidation. A Communication API is necessary to integrate the workers into a virtual network of data computation.

The Global Aggregator is a module that orchestrates the results of the aggregation and maintains the safety data mechanism for the end-users. The End-User Interface shows the information in a user-friendly way through a Central Monitoring system.

DISPATCHER MODULE DEPLOYMENT STRATEGIES

It is the main goal of this paper to overcome existing issues of the Global Dispatcher (GD) regarding data distribution in real time applications, via solutions presented by [START_REF] Righi | Rescheduling and Checkpointing As Strategies to Run Synchronous Parallel Programs on P2P Desktop Grids[END_REF]. This means that the Global Dispatcher will carry out the tasks of load balancing, and latency control (data stream processing and network bandwidth), provision of scalability, while reducing the costs for improvement of availability of resources. Additionally, it will monitor environmental behavior (network bandwidth, availability of processing capacity, time spent on completing tasks, churn and so on) for the Decision Engine. The role of the Decision Engine is to select the computing resources needed for carrying out a task. The task definition will be achieved by simulation, which will use BIGhybrid, and at the same time, to evaluate the environment for the re-scheduling processes (data placement and data movement). According to [START_REF] Delamare | SpeQuloS: A QoS Service for BoT Applications Using Best Effort Distributed Computing Infrastructures[END_REF], it is possible to achieve QoS in the GD by monitoring the task execution and dynamically provisioning external, stable, and powerful Cloud resources to support the GD. They employed different strategies (i.e, Completion Threshold, Assignment Threshold, and Execution Variance) to control the Cloud usage.

Similarly, the model will employ strategies to control the use of the environment. To this end, it will have control over the execution of the system jobs. First of all, it will asynchronously create batch views asynchronously in the background of the tasks and storage of the data nodes (logs). Then, it will create the stream views, in which the latest logs (nodes and tasks) will be collected for the control. The combination of views will achieve a performance gain due to the fact that most of the information required will already have been generated when it is needed.

The clustering data method and processing in small batches will be used to obtain low latency for the streambased processing [START_REF] Das | Adaptive Stream Processing Using Dynamic Batch Sizing[END_REF]). However, this method will be validated by conducting comparative studies to define the size of the batches and to determine if it will be the best technique for stream processing. This will involve validating the particular way of batching the streams (i.e., time-based, event-based, or hybrid form). Through the batch-sizing of stream processing, it will reduce the latency, make it easier for the processing flow (i.e., by processing simulations) and facilitate the scheduling and rescheduling of tasks and data. This feature will overcome the BIGhybrid simulator problem (it cannot work with streams because of the SimGrid restrictions).

Decision Strategies

The Decision Engine (DE) will make the decision about scheduling and re-scheduling and thus will be the main component in the Global Dispatcher. It will combine environmental data (task simulation, availability of resources, network availability, costs, aggregation time and so on) with the strategies (i.e. batch and stream) to decide where to allocate the task to (node or Cloud).

Figure 2 depicts the target scenarios, based on the type of strategies intended to obtain a Good or Best result in the load balancing. Differentials such as migration, elasticity, scheduling strategies, data aggregation and replication are highlighted in the model. Scenario i (part a, only the execution time) is the application (performing a set of tasks) without migration time, scheduling time, aggregation time or replication time. Scenario ii (part b) is the execution of the application and the scheduling (only to obtain the scheduling overhead). Scenario iii (parts c, d, e and f) involves the execution of all the services (migration, aggregation, scheduling and replication). In the part c, the migrations services are restricted, but still continue with the replication. In d, all the services will be operating, but with a strong impact on the time. e, the model will show the performance that is embodied in the strategies. If the time is lower than b this yields a Good Result. The f is the best scenario. The strategies at the scheduler reveal the best computing resources for execution. In this scenario, the performance will be greater than the a part, which is just the application of the execution (The Best Result). The reasons for applying this feature to the architecture are set out below:

• Migration: This generates considerable gains in dynamic, heterogeneous and large-scale environments.

Since there is a dynamic, the nodes might be in or out of the network (i.e., churn). This means that a certain task may be at an overload or a slow node, and there might be a machine that runs in less time (when the movements are counted). In this case, it is worth migrating the task; • Aggregation: Distributing the tasks belongs to the network and forms a part of a set; thus it will be necessary to group the results. The distribution will be able to obtain time and make use of the idle resources; • Replication: Replicating the task belongs to the network and means that it will be necessary to ensure the correct execution and reduce the time when a fault occurs. A fault generally occurs because of the volatile environment (Desktop Grid); • Computing Resource Rating: The rate will evaluate the resource data, network data and past execution data. This method assists in recognizing a good worker; • Time Estimation: Knowing the time before executing a task will make it easier to ensure a correct scheduling;

As discussed earlier in this paper, this work includes controls for monitoring and to provide decisions that will run asynchronously in the background. These controls combined to recent information (stream views) and historical information (batch views), will allow a hybrid control system. The result will enable settlements to be made safer and faster. In light of this, the following methods are combined:

• Batch-Based: The raw data stored in a distributed file system will be processed in a batch processing way; • Stream-Based: The recent data will be performed in near real-time fashion;

The combination of batch and stream strategies will be able to reduce the Dispatcher time. The work of De Francisci Morales and Bifet (2015) provides some evidence that there is a significant reduction with the result of this merge. The batch-based method can reduce the decisionmaking time and the management time and, in addition, can be used to the stream processing monitoring. However, all this must be in accordance with the Lambda Architecture paradigm.

At the same time, the BIGhybrid simulator could be employed to estimate an execution time. The BIGhybrid will use the computational resources found in the environment, such as hardware performance, network performance, and tasks costs. A weight rating of computing will be defined through the simulation to define some thresholds. The restriction will aid to control overhead levels of run time.

A batch method for the stream processing enables to overcome the limitations of BIGhybrid and adapting it to low latency processing.

Estimating an approximate execution time, will make the scheduling and re-scheduling easier, because this makes it possible to know when a task will probably end at a particular computing resource before it starts. Knowing the execution time and using its heuristics will help to make a more accurate task allocation. The heuristics should include an analysis of the entire environment. However, methods such as Complex Event Processing (CEP), Event Stream Processing (ESP), Directed Acyclic Graph (DAG), as well as Machine Learning are possible features that can assist in structuring the algorithm.

Thus, if the methods mentioned above (heuristics of scheduling/rescheduling, migration, aggregation, simulation, and replication) are employed as part of the strategies for reducing the application time (that are shown in Figure 3), the result is also the execution time reduction. The time reducing of methods and application might achieve either a Good or the Best Result as shown in Figure 2.

CONCLUSION AND FUTURE WORK

Stream processing applied to volatile and heterogeneous environments is currently a significant subject for research. This paper describes its degree of complexity as well as current trends committed towards this subject. In response to the challenges posed by this complexity, a solution has been proposed to improve this type of data processing.

The proposed solution will be applied at a complex infrastructure (i.e., geographical distributed) to study its issues and validate the model. The migration, scheduling (MapReduce simulation and heuristics), and replication features will treat the problems of its volatility, heterogeneity and dynamic. Furthermore, through the strategies to combine the desirable features, the proposed model will provide a Good or The Best Result on the scheduling settlements. Therefore, this work contributes towards a solution to volatile and heterogeneous environments for stream processing. It will extend the SMART project and address open challenges and issues such as data stream latency, network latency, management of the computational resource, and fault control. The decisions (heuristics) and the views about the execution method (batch-or streambased) will be a means of reducing the limitations of the system. The asynchronous and background executions will assist the required latency for performing stream processing.

Fig. 1 .

 1 Fig. 1. SMART Platform Overview

Fig. 2 .

 2 Fig. 2. Target ScenariosSome factors must be included in the strategies to overcome the problem of time constraints in the system and achieve the Best Result or a Good Result. These include the time to movement data and the task migrations, time to data aggregate when the data is shared between a) the computing resources, b) time estimated to execute a task, c) data placement and e) computing resource rating. In this way the overall execution time can be reduced and allow a simple fail control (volatile).

Fig. 3 .

 3 Fig. 3. Strategies for Reduction of Application Time