Mamoudou Sangare

Sharut Gupta

Samia Bouzefrane

Soumya Banerjee

Paul Muhlethaler

Mamoudou Sangaré

Exploring the forecasting approach

Keywords: Gaussian mixture model, Support vector machine, Support vector classifier, Hybrid model, Traffic accident forecasting, Accident severity

HAL is

INTRODUCTION

It is a regrettable fact that the number of road traffic accidents continues to rise, largely due to rapid urban growth and the ever-increasing density of vehicles in cities and surrounding areas. According to statistics from World Health Organization, each year approximately 1.25 million people lose their lives in road traffic accidents worldwide, which means that one person is killed every 25 seconds. The statistics predict that road accidents will grow by 65% and will become the fifth greatest cause of fatalities by 2030. However, with emerging sensor devices and the IoT, it has become feasible to configure future vehicles with safety sensors to prevent many of these accidents.

Therefore, recent research has been orchestrated to investigate the state-of the-art of vehicle safety analysis in Vehicular ad-hoc networks (VANETs) while including the issue of road accidents. It has become clear that certain driving safety [START_REF] Jeong | Early detection of sudden pedestrian crossing for safe driving during summer nights[END_REF] and road safety issues involve various dimensions and parameters. For example, in driving safety analysis, the style and behavior of drivers must be studied to investigate unorthodox driving style and neighboring conditions are sensed and analyzed in order to provide intelligent support for the drivers. However, the major constraints of such analyses are the absence of substantial data sets and a precise means of identifying the neighboring conditions without incorporating additional sensors.

Another aspect of road safety analysis involves the effect on road safety from external parameters, including the road surface, geometry, traffic flow, weather conditions and both drivers' and pedestrians' behavior. Despite considerable research efforts, it has not been possible to provide the most deterministic and computationally intelligent model [START_REF] Dong | An Improved Deep Learning Model for Traffic Crash Prediction[END_REF] to predict the exact context of road accidents due to unbalanced data instances at various levels. Accident prediction is one of the most crucial aspects of road safety where precautionary measures are taken to avoid an accident before it occurs.

Therefore, it is important to investigate the accident-prone areas of cities and the effect of external factors in order to be able to forecast the safety level of roads with appropriate granularity. There are huge variations in road traffic accidents in terms of the extremity of the accident and the damage to people and their property, which is also referred to as accident severity [START_REF]Highway Safety Manual[END_REF]. It is necessary to investigate the relationship between traffic accident severity and related risk factors such as the traffic volume, the driver's age, maximum possible speed, geometrical factors like the type of vehicle, distance from the nearest intersection, details of intersections etc. and environmental features such as weather conditions, lighting conditions, type of road, etc. Previous studies in this area are broadly classified into two categories: statistical modeling and machine learning modeling.

Initially, accident severity analysis for traffic accident forecasting was primarily carried out using statistical techniques [START_REF] Chen | A multinomial logit modelbayesian network hybrid approach for driver injury severity analyses in rear-end crashes[END_REF][START_REF] Chen | Hierarchical Bayesian random intercept model-based cross-level interaction decomposition for truck driver injury severity investigations[END_REF][START_REF] Liu | How big data serves for freight safety management at highway-rail grade crossings: a spatial approach fused with path analysis[END_REF][START_REF] Lord | The statistical analysis of crash-frequency data: A review and assessment of methodological alternatives[END_REF][START_REF] Wu | Exploratory multinomial logit model-based driver injury severity analyses forteenage and adult drivers in intersection-related crashes[END_REF]. Statistical models are favored over machine learning models due to their solid theoretical base and strong mathematical formulation [START_REF] Tang | Crash injury severity analysis using a two-layer Stacking framework[END_REF]. Gaussian Mixture Models (GMMs) are the most common, and they have been successfully used in a wide variety of fields, such as voice recognition systems, video image processing, and pattern classification. In studies related to traffic flow and accidents, GMMs have been repeatedly used to model raw time-to-collision (TTC) samples for traffic safety prediction [START_REF] Jin | Assessment of Expressway Traffic Safety Using Gaussian Mixture Model based on Time to Collision[END_REF][START_REF] Jin | Short-term traffic safety forecasting using Gaussian mixture model and Kalman filter[END_REF], severity detection of traffic accidents along with Hidden Markov models [START_REF] Akoz | Severity detection of traffic accidents at intersections based on vehicle motion analysis and multiphase linear regression[END_REF] and in traffic flow forecasting [START_REF] Sun | A Bayesian Network Approach to Traffic Flow Forecasting[END_REF]. However, these models assume some inherent properties about the data patterns like the assumption of risk factors influencing accident severity linearly, which might not always be the case [START_REF] Mahalel | A note on accident risk[END_REF][START_REF] Hauer | Estimation of safety at signalized intersections[END_REF] and hence they inevitably induce inaccurate results.

Machine learning models on the other hand [START_REF] Tang | Lane-changes prediction based on adaptive fuzzy neural network[END_REF], are highly adaptable with no or very few assumptions about the input features and offer higher flexibility to outliers, as well as inaccurate and missing data. Popular machine-learning models applied to traffic accident related studies include Decision Trees [START_REF] Oa | Extracting decision rules from police accident reports through decision trees[END_REF][START_REF] Abelln | Analysis of traffic accident severity using decision rules via decision trees[END_REF], Support Vector Machines (SVMs) and Support Vector Classifiers (SVCs) [START_REF] Dong | Support vector machine in crash prediction at the level of traffic analysis zones: assessing the spatial proximity effects[END_REF][START_REF] Li | Using support vector machine models for crash injury severity analysis[END_REF][START_REF] Iranitalab | Comparison of four statistical and machine learning methods for crash severity prediction[END_REF], K-means clustering [START_REF] Anderson | Kernel density estimation and k-means clustering to profile road accident hotspots[END_REF][START_REF] Mauro | Using a K-means clustering algorithm to examine patterns of vehicle crashes in before-after analysis[END_REF], Artificial Neural Networks (ANNs) [START_REF] Abdelwahab | Development of artificial neural network models to predict driver injury severity in traffic accidents at signalized intersections[END_REF][START_REF] Delen | Identifying significant predictors of injury severity in traffic accidents using a series of artificial neural networks[END_REF][START_REF] Zeng | A stable and optimized neural network model for crash injury severity prediction[END_REF] etc. Of these models, Support Vector Machines have been increasingly used in traffic related studies to address traffic flow prediction [START_REF] Cheu | Forecasting of shared-use vehicle trips using neural networks and support vector machines[END_REF][START_REF] Huang | Intersection traffic flow forecasting based on -GSVR with a new hybrid evolutionary algorithm[END_REF][START_REF] Wei | An adaptive-margin support vector regression for short-term traffic flow forecast[END_REF][START_REF] Yu | Urban Road Traffic Condition Pattern Recognition Based on Support Vector Machine[END_REF], crash frequency analysis [START_REF] Li | Predicting motor vehicle crashes using Support Vector Machine models[END_REF][START_REF] Ren | Traffic safety forecasting method by particle swarm optimization and support vector machine[END_REF][START_REF] Surez Snchez | Prediction of work-related accidents according to working conditions using support vector machines[END_REF][START_REF] Yu | Utilizing support vector machine in real-time crash risk evaluation[END_REF], and to analyze accident severity in a crash [START_REF] Li | Using support vector machine models for crash injury severity analysis[END_REF][START_REF] Guo | Pedestrian detection for intelligent transportation systems combining AdaBoost algorithm and support vector machine[END_REF][START_REF] Yu | Analyzing crash injury severity for a mountainous freeway incorporating real-time traffic and weather data[END_REF]. The major drawback of machine-learning models is their performance as a 'black-box' which leads to unclear inference of the function that correlates the input variables with the target class [START_REF] Chen | Investigating driver injury severity patterns in rollover crashes using support vector machine models[END_REF].

The purpose of this study is to combine the Gaussian Mixture Model from statistical modeling and the Support Vector Classifier from machine-learning modeling to overcome the disadvantages of one model by the advantages of the other and hence improve the overall accuracy. Favored by its innate discriminative power, even in the case of non-linearly separable classes using kernels, the SVM presents an attractive way of enhancing the baseline generative model (GMM) [START_REF] Bourouba | SMOTE: Synthetic Minority Over-sampling Technique[END_REF]. Hence the GMM serves as a parametric basis for the Support Vector Classifier. Since SVCs perform poorly on unbalanced data and cannot select relevant attributes with respect to the target variable, data pre-processing using re-sampling techniques and feature importance ranking methods are applied.

The rest of the paper is organized as follows: Section 2 introduces specific and recent related research on road safety prediction incorporating various levels of machine learning and intelligent algorithms. The third section gives a brief explanation about the dataset used. Section 4 contains a comprehensive description of the model construction mechanism along with model specifications, followed by the details of the various models used. Section 4.1.1 presents the data pre-processing and balancing techniques used in the proposed model. In Section 5, the results are given with a comparison with the baseline model and data analysis is performed to strengthen the claims of the paper. Finally, the last section concludes the paper with a brief summary of the research limitations and the overall research effort.

Review of the literature

In this section we review road safety prediction methods that incorporate various levels of machine learning and intelligent algorithms. Then, we analyze the advantages and drawbacks of various methods, and formulate the missing value problem, which is a substantial challenge in this area of research.

For traffic flow forecasting, various machine learning methods have been employed. The most prominent among these are: Autoregressive Integrated Moving Average (ARIMA) which belongs to time series categories [START_REF] Van Der | Combining Kohonen maps with Arima time series models to forecast traffic flow[END_REF]; probabilistic graphical models, such as Bayesian Network [66], Markov Chains [START_REF] Huang | A short-term traffic flow forecasting method based on Markov chain and grey Verhulst model[END_REF], and Markov Random Fields (MRFs) [START_REF] Shuai | An online approach based on locally weighted learning for short-term traffic flow prediction[END_REF]; and nonparametric approaches, such as Artificial Neural Networks (ANNs) [START_REF] Huang | A short-term traffic flow forecasting method based on Markov chain and grey Verhulst model[END_REF], Support Vector Regression (SVR) [START_REF] Castro-Neto | Online-SVR for short-term traffic flow prediction under typical and atypical traffic conditions[END_REF] , and Locally Weighted Learning (LWL) [START_REF] Shuai | An online approach based on locally weighted learning for short-term traffic flow prediction[END_REF] . However, as seen in the literature, there are multiple reasons for fluctuation in the traffic flow. In addition to that, the patterns in the data are multimodal. These multimodal properties make it difficult to learn. Moreover, for these shallow network approaches to be able to model complex mapping, they require a high dimensional space. A high dimensional space request leads to the requirement of a huge amount of annotated data. Therefore, in the high-dimensional space the overfitting problem becomes acute. In order to overcome this issue, we use a multilayer nonlinear structure since deep learning approaches have a strong ability to express multi-model patterns in data using a reduced number of dimensions. An ANN (Artificial Neural Network) [START_REF] Chang | Analysis of freeway accident frequencies: negative binomial regression versus artificial neural network[END_REF] is a type of network in machine learning that has been widely used for road incident prediction in different environments (freeway, highway, urban and non-urban roads, etc.) in order to minimize injury and loss of life on the roads.

An ANN aims to reproduce and simulate human behavior and cognitive functions. It uses a network of nodes, often called neurons, that contain configurable weights and these weights can be trained to produce a desired output [START_REF] Pan | Development of a global road safety performance function using deep neural networks[END_REF]. Many kinds of pattern recognition problems can be solved by configuring the layers and the weights of the network. Today, machine-learning techniques have found different applications in a number of fields. These include road safety where they have been used for collision detection. As an illustration, in the study presented in [START_REF] Chang | Analysis of freeway accident frequencies: negative binomial regression versus artificial neural network[END_REF] by Chang, an ANN is implemented to predict collisions on a National Freeway in Taiwan. Road features were used as input in their model and it is claimed that the model accepted those features and provided the number of collisions as output. However, the ANN model has many local minimums, which makes it difficult to find the global optimum solution. This highlights the fact that, even though ANN models are easy to understand, the solution covered by their weights space is non-convex. This is one of its drawbacks. Another shortcoming of an ANN is that it is supervised-based learning and therefore the model requires training data, which limits its applicability in real-world situations. In order to overcome these issues, back propagation (BP) such as Bayesian regularization has been proposed. Although it has been found that Bayesian regularization has led to great improvements, it still requires training data, again making its applicability in the real world limited.

Bayesian Networks (BNs) have also become very popular in traffic prediction as they allow multiple inputs of data to be taken into account. It is known to have applications that can take many forms. It has been pointed out that the inputs of BNs sometimes show less relativity than is the case for neural networks [60][61]. This specific characteristic of BNs offers more possibilities for combining different prediction factors.

Research has revealed that, for traffic prediction, there is no single method that is the best for every situation. Thus, in traffic forecasting, researchers are constantly trying to combine different models. It has been observed that almost all the research undertaken in using hybrid models (HMs) for traffic prediction yield greater prediction accuracy than when a single model is used [62][63]. Jiaming Xie and Yi-King Choi conducted research on designing and implementing a hybrid model that can forecast the traffic flow in the city of Hong Kong by using historical and realtime data. The question that arises here is how one can balance the importance of historical data and real data. This is because it obvious that the traffic situation changes over time and that continuous changes make the traffic status dynamic [START_REF] Xie | Hybrid traffic prediction scheme for intelligent transportation systems based on historical and real-time data[END_REF].

As no single model can be suitable for prediction in all situations, the main objective of this research is to build a prediction model that combines two approaches (the Gaussian mixture model and support vector classifiers) in order to predict traffic accidents. The improvement in terms of accuracy is very notable compared to other models. The development of Intelligent Transportation Systems (ITSs) and other applications to improve driving comfort have been motivated by the continuing increase in road traffic accidents.

In order to make these applications feasible, a communication network, the so-called vehicular adhoc network (VANET) was developed. In such a network, vehicles are equipped with wireless devices that allow them to communicate. ITS services are provided to the end users by VANETs that transfer data and safety messages. By using wireless standards such as Dedicated Short-Range Communication (DSRC) and Wireless Access in Vehicular Environments (WAVE), VANETs can provide wireless communication between moving vehicles. Essentially, there are three units involved in vehicle communication: Application Units (AUs), On Board Units (OBUs) and Roadside Units (RSUs). By employing wireless standards like IEEE 802.11p [START_REF] Xie | Hybrid traffic prediction scheme for intelligent transportation systems based on historical and real-time data[END_REF], communication between OBUs and AUs with RSUs can be possible, as shown in Figure 1.

 Application Units (AUs) -These are smart devices that provide safety applications. They use OBUs to communicate with RSUs. As chips are getting smaller and smaller, these units may be isolated or they may be integrated with OBUs as a single unit. The connection mode of AUs to the OBUs can be done through a wired or wireless connection.

 On Board Units (OBUs) -These are generally installed onboard the vehicles, and their main task is to provide communication between other OBUs and RSUs. In terms of composition, they are made up of devices such as Resource Command Processors (RCP). These resources include a user interface and read/write memory. They also have a specialized interface to connect to other OBUs and a network device for short-range wireless communication based on IEEE 802.11p radio technology. In addition, these units are used for IP mobility management, congestion control, wireless data access, reliable message transfer, data security and geographical routing.

 Roadside Units (RSUs) -These are considered to be fixed nodes that act as a router to provide services to the moving vehicles. RSUs are set up as rigid units at the side of the road in such a way as to maintain coverage and connectivity to all the vehicles. They are the source of radio wave propagation between RSUs and OBUs. The main function of RSUs is to increase the communication range of the Ad Hoc network. They do so by sharing information with OBUs and by sending the information to other RSUs. RSUs work as an information source and provide Internet connectivity to the OBUs. RSUs can be connected to the Internet via a gateway. VANETs provide the radio interface required by vehicles (wireless transceivers based on IEEE 802.11p, which operate on the dedicated short-range communication (DSRC) band) to communicate with each other using vehicle-to-vehicle (V2V) or vehicle-to-infrastructure (V2I) and offer a wide variety of applications for ITSs.

As the aim of this work is to derive analytics for the prediction of road accidents, it is important to include a data acquisition mechanism (see Figure 2) and inter-process communication between vehicles on the road. For a standard use case, we consider a segment of a densely populated city road where this type of acquisition model can be placed. To formulate such a model, the physical components of the VANETs can be one of the parameters. However, the inter-process communication protocol of 5G and beyond can establish a more reliable process exchange mechanism. In conventional usage, a Message Application Programming Interface (MAPI) is suitable for use cases to collect and to propagate the data for a particular segment of road. In this paper, certain realistic scenarios are considered to formulate the data acquisition and the message passing mechanism. Four layers are involved in the overall system flow for message passing and broadcasting:

 Application layer (message wrapping mechanism)  Transport layer (with handshaking between the sender and the receiver)  Network layer (message distribution mechanism)  Physical layer (connection and devices)

Thanks to these layers, the system can collect on-road data to pass them towards a nearest cloud center or adjacent vehicle, so that the neighboring vehicle can receive an alert containing several features.

The format of the message is: 1. transaction ID, 2. previous transactions ID, if any 3. sender ID 4. reputation ID (this number will present the reputation or likelihood of a given vehicle to have an accident) 5. receiver ID 6. message content (message text, location, direction of sender vehicle) 7. message type (this information will deliver the warning or the prediction of the message after using a hybrid analytical algorithm such as intersection movement, tendency for forward collision, deviation from the lane, extreme conditions of the road surface and other relevant features). As well as all these message fields, each message will be followed by the action requested. For example, the action requested indicates the message from the sender vehicle to all receivers for a particular alert if the adjacent vehicle could change lane abruptly. Similarly, if a vehicle accelerates more than normal, despite the traffic congestion on the road, then there will be an alert message for other neighboring vehicles.

All these features of message access and distribution can be implemented in a traffic environment simulator (SIMO) which can be deployed by another event-based simulator like OMNET++. However, since the objective of our work is to analyze the action requested by the given message distribution format, we did not use these kinds of simulation tools. I. Mathematical symbols

Mathematical symbols at glance Symbols used in the

Dataset description

The dataset was obtained from data.govt.uk [START_REF]Road Safety Data[END_REF] which is a United Kingdom Government project providing open source data published by central government, local authorities and public bodies. The road traffic accident database for the year of 2017 was used in this research. These dataset files provide detailed road safety data about the environmental, physical, geometrical, geographical and personal information related to accidents as shown in Table II. The data points correspond only to those accidents where information was reported to the police or the authorities. The dataset was compiled from the information recorded in the STATS19 accident reporting form. The entire dataset is mainly composed of three main categories: accident, vehicle and casualty data. The accident variables have 31 features including the weather conditions, lighting, time, day of the week, number of vehicles involved, etc. The Vehicle-Driver database consists of 22 features such as the age of the vehicle, sex and age of the driver, etc. and the casualty dataset contains 15 feature variables such as the type of victim, sex of the casualty, age of the casualty, etc.

Accident variables Vehicle and driver variables Casualty variables

Index The output class or accident severity is divided into 3 categories, namely "no injury in the accident" encoded as 1, "non-incapacitating injury in the accident" encoded as 2 and" incapacitating injury in the accident" encoded as 3. The detailed encoding of every variable is listed in Table III.

Research Methodology

Algorithm description

This section presents the models used in this study for traffic accident forecasting. As mentioned above, the accident data including vehicle, casualty and drivers' features are collected from data.govt.uk. These higher dimensional features are then preprocessed to remove any kind of erroneous entries and balance the dataset. Moreover, if the dataset has a highly unequal distribution of the number of data points corresponding to each class, the SVC model tends to predict every data sample as the majority class. In order to achieve an unbiased performance, it is necessary to balance the dataset with respect to the output class.

Since the dataset is high dimensional, dimensionality reduction techniques must also be used. Furthermore, like Bayesian network (BN) models [START_REF] Zhanga | A multinomial logit model-Bayesian network hybrid approach for driver injury severity analyses in rear-end crashes[END_REF], SVMs lack the ability to automatically select the relevant features. Feature or attribute selection helps to target both above-mentioned disadvantages. Variable importance ranking methods are deployed and the data are further cleaned. This processed dataset is then used as input to the Gaussian Mixture Model [START_REF] Bilmes | A gentle tutorial on the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models[END_REF], [20] and [START_REF] Jain | Statistical pattern recognition: a review[END_REF] which estimates the parameters of the various Gaussians mixture using expectation maximization. Out of all the parameters i.e. the mean, variance and the mixing probability, the vector of means is adapted and used as input to the SVC model [START_REF] Bourouba | Novel Approach in Speaker Identification using SVM and GMM[END_REF]. The SVC treats the accident severity modeling as a classification problem i.e. the accident data is classified into various categories based on the severity classes. This trained hybrid model is then evaluated with respect to the performance metrics and sensitivity analysis is performed. The model is also compared to the baseline GMM model and the results are reported. A brief description of the hybrid algorithm is shown in Figure 3.

Data pre-processing

A considerable amount of missing and erroneous data were recorded and hence data preprocessing was performed prior to the application of the hybrid model. One can either remove the examples with erroneous data or remove the attributes with corrupted data. For the former, data processing was carried out using the Filter Examples operator of the RapidMiner Studio [START_REF] Mierswa | science,machine learning, RapidMiner Studio (9.1[END_REF] software. 1This operator filters out the data entries according to the conditions specified by the user. Removing the attributes with corrupted data is achieved with the help of the Select Attributes operator in RapidMiner. The Filter Examples operator reduces the number of data entries in a dataset, but it has no effect on the number of attributes. On the other hand, the Select Attributes operator chooses the attributes with no missing or corrupted values and has no effect on the number of examples in the example set.

Data Re-sampling

The dataset used consists of 2044 data points for Class 1 accidents, 21098 data points for Class 2, and 93321 data points for Class 3, as shown in the form of a distribution curve in Figure 4. This accounts for the severe imbalance in the data, causing the prediction results to be skewed significantly in favor of the majority class. This causes poor classification rates on minor classes and extreme biasing towards the majority class. In addition, it is also possible that the classifier predicts everything as a major class and ignores the minor class. To tackle this issue, one must use re-sampling techniques to balance the data. We used the Synthetic Minority Oversampling (SMOTE) [START_REF] Bourouba | SMOTE: Synthetic Minority Over-sampling Technique[END_REF] up-sampling technique, which works by creating synthetic observations based upon the existing minority observations.

Feature/Attribute selection

In machine learning and statistics, feature selection or attribute selection is the process of selecting a subset of features that are used to build the model. It is performed to get rid of any unnecessary, irrelevant, or redundant features from the dataset, consequently resulting in improving the accuracy of the model. This also leads to better interpretability of the underlying relationship between input variables and the target class. In this study, feature relevance analysis was carried out using the RapidMiner studio. The Weight by Tree Importance operator was used to find the relevant features. The weights of the attributes are calculated by analyzing the split points of a Random Forest model. Each node of each tree is visited, and the benefit created by the respective split is retrieved, which is further summed per attribute. The importance ranking is done by calculating the mean benefit over all the trees. This approach was implemented following the idea from the seminal work by [START_REF] Menze | A comparison of random forest and its Gini importance with standard chemometric methods for the feature selection and classification of spectral data[END_REF] [START_REF] Menze | A comparison of random forest and its Gini importance with standard chemometric methods for the feature selection and classification of spectral data[END_REF]. The higher the weight of the attributes is, the greater is their relevance. The Information Gain method was used to find the weights by the tree importance operator. Information Gain (IG) measures how much information a feature gives us about the class which is the entropy of the distribution before the split minus the entropy of the distribution after it. Mathematically, the information gain is given by the equation below:

IG = E(p) -w * E(c) (1)
where IG is information gain, E is entropy, p is parent node, c stands for children and w corresponds to the average of the weights.

Gaussian Mixture Model

Accident severity data can be formulated as a weighted sum of K-component Gaussian distributions:

𝑝(𝑥 𝜆 ⁄ ) = ∑ 𝑤 𝑖 𝑘 𝑖=1 𝑁 𝑖 (𝑥) (2)
where x is a d-dimensional vector, 𝑁 𝑖 (𝑥) are the component multivariate Gaussian densities and wi is the mixing proportion or the mixture weights with ∑ 𝑤 𝑖 𝑘 𝑖=1

= 1 Each component multivariate Gaussian density function is given by

𝑁 𝑖 (𝑥) = 1 ((2𝛱) 𝑑 2 |𝛴 𝑖 | -1 2 ⁄ ) 𝑒 1 2 (𝑥-𝜇 𝑖 ) 𝑡 𝛴 𝑖 -1 (𝑥-𝜇 𝑖 ) (3)
with 𝜇 𝑖 , 𝛴 𝑖 as the mean vector and the Co-variance matrix respectively. The above-mentioned parameters, namely 𝑤 𝑖 , 𝜇 𝑖 and 𝛴 𝑖 , are represented by 𝜆 = (𝑤 𝑖 , 𝜇 𝑖 , 𝛴 𝑖 ) ∀𝑖 = 1,2,3, . . . , 𝐾 )

The maximization of the likelihood function in Equation 5 is achieved by using the Expectation-Maximization (EM) algorithm. In the expectation (E) step, a function for the expectation of the loglikelihood is constructed while in the maximization (M) step, model parameters like the mean, variance and the mixing probability are estimated by the maximizing function found in the E step. After simplification, the formulas obtained performed at each E-M step are:

E

GMM and Traffic prediction

The observations (x) including features like weather conditions, lighting conditions, age of the driver, distance from junction etc., are assumed to be a mixture of three Gaussians (λ) which correspond to the three accident classes. Hence, our objective is to find a model that maximizes the posterior probability:

𝑚𝑎𝑥 1≤𝑘≤𝐾 𝑝(𝜆 𝑘 𝑥 ⁄ ), (11)
which by Bayes's rule is:

𝑚𝑎𝑥 1≤𝑘≤𝐾 𝑝(𝜆 𝑘 𝑥 ⁄ )𝑝(𝜆 𝑘 ) 𝑝(𝑥) . ( 12
)
Assuming all the Gaussians to be equally likely and taking the log, we have our likelihood function as:

𝑚𝑎𝑥 1≤𝑘≤𝐾 ∑ 𝑙𝑜𝑔𝑝 𝑀 𝑗=1 (𝑥 𝑗 𝜆 𝑘 ⁄ ) (13)
which is further reduced to (6) and solved using expectation maximization.

Support vector classification

A support vector classifier or SVC is a discriminative model that makes decisions by constructing an optimal hyperplane or a line among linearly or non-linearly separable classes [START_REF] Suykens | Least squares support vector machine classifiers[END_REF].

Figure 6: Concept of optimal hyper-plane

For linear support vector classifiers on the data (𝑥 𝑖 , 𝑦 𝑖 ) with i=1,2...n, the classification function is represented as:

𝑓(𝑥) = 𝑤 𝑇 (𝑥) + 𝑏 (14)
The margin according to Figure 6 is given by

|𝑤 𝑇 (𝑥)+𝑏| ‖𝑤‖ | 𝑤 𝑇 (𝑥)+𝑏=1 + |𝑤 𝑇 (𝑥)+𝑏| ‖𝑤‖ | 𝑤 𝑇 (𝑥)+𝑏=-1 = 2 𝑤 ( 15
)
Since 𝑤 𝑇 (𝑥) + 𝑏 = ±1 for the support vectors.

Maximizing the margin (the minimum distance of the hyperplane from these points), the problem can be formulated as follows: 𝑚𝑖𝑛 The solution for the optimal w turns out to be a linear combination of support vectors i.e. which satisfy 𝑦 𝑖 (𝑥 𝑖 𝑤 + 𝑏) = 1.

In the case of a non-linearly separable dataset, no hyperplane exists that satisfies the abovementioned constraints. In that case, a new model is introduced [13] :

𝑚𝑖𝑛 1 2 ‖w‖ 2 + 𝐶 ∑ 𝜉 𝑖 𝑛 𝑖=1 𝑠. 𝑡. 𝑦 𝑖 (𝑥 𝑖 𝑤 + 𝑏) ⩾ 1 -𝜉 𝑖 𝑖 = 1,2, . . . , 𝑛 (17)
𝜉 𝑖 ⩾ 0, 𝑖 = 1,2, . . . , 𝑛
where ξi is a non-negative factor called the slack variable responsible for allowing the functional value of certain samples to be negative. The factor 'C' is used to penalize the outliers and expresses the degree to which they are not acceptable.

The solution for the optimal w is a linear combination of all points (∑ 𝛼 𝑖 𝑖=1 𝑦 𝑖 𝑥 𝑖 ) in the feature space that have ξi > 0 and lie on the margin (𝛼 𝑖 ≠ 0) and hence the classification function becomes:

𝑓(𝑥) = 𝑠𝑖𝑔𝑛[(∑ 𝛼 𝑖 𝑛 𝑖=1 𝑦 𝑖 𝑥 𝑖 ) 𝑇 𝑥 + 𝑏] (18)
= 𝑠𝑖𝑔𝑛[∑ 𝛼 𝑖 𝑛 𝑖=1

𝑦 𝑖 ⟨𝑥 𝑖 , 𝑥⟩ + 𝑏] The non-linear classifier can be extended using the kernel function (K) satisfying Mercer's condition to map the input features to a higher dimensional space where it is linearly separable [START_REF] Friedman | The elements of statistical learning[END_REF], as represented in Figure 7. Then all the inner products are replaced with the kernel function and hence the classification function becomes, This method [START_REF] Bishop | Pattern recognition and machine learning[END_REF] considers N classifiers where N is the number of classes and trains the i th classifier with all other examples considering the instances of the i th class as positive and all other instances as negative labels.

𝑓(𝑥) = 𝑠𝑖𝑔𝑛[∑ 𝛼

One-against-one method:

This method [START_REF] Knerr | Single-layer learning revisited: a step-wise procedure for building and training a neural network[END_REF] constructs N (N -1)/2 classifiers and trains the i th classifier with every j th classifier considering the instances of the i th classifier as positive and those of the j th classifier as negative.

The Need for a Hybrid Model

Since research has shown that no single method is best for every situation in traffic prediction, building hybrid models (HMs) is an approach that combines different methods that could produce better results than any of those methods applied individually.

In this paper, the need for HMs is justified using a statistical modeling method i.e., a Gaussian Mixture Model (GMM) and a machine learning modeling scheme i.e., the Support Vector Classifier (SVC). As the baseline generative model (GMM) could only classify with maximum likelihood, the SVM presents an attractive way of enhancing it. This is because of the SVM's innate discriminative power, even in the case of non-linearly separable classes using kernels. However, SVCs also perform poorly on unbalanced data. Hence the GMM serves as a parametric basis for the support vector classifier. Therefore, in this work, the use of a hybrid model (HM) was needed in order to overcome the disadvantages of one model by the advantages of the other and hence to improve the accuracy.

DISCUSSION OF RESULTS

Data pre-processing results

Erroneous and missing data entries were removed using the RapidMiner Studio. The data was reduced from 178918 examples and 69 attributes to 116463 examples and 69 attributes, removing all the missing values. By removing the attributes with missing values, the number of features was reduced from 69 to 62. The variables and the number of missing values are listed in Table IV

Data Re-sampling results

The imbalanced dataset is balanced using SMOTE from the 'imblearn' module of python. This is an upsampling technique which balances the data by increasing the number of data points for the minority class. After applying SMOTE on our dataset, we received a total of 279,963 samples with 93,170 samples from Class 1, 93,756 samples from Class 2 and 93,037 from Class 3, as listed in Table V.

Feature selection results

The variable importance ranking based on the three accident severity levels was conducted using the RapidMiner Studio. Weight by the tree importance ranking operator was used after applying the Random forest model on the processed data. In addition to this, the information gain method was used to find weights using tree importance. In this, the variable with the largest score is normalized to 1 and the scores of all the others are calculated with respect to the best performing variable.

The results obtained are shown below in Table VI and Figure 8. It can be seen that among all the variables, Intensity of the fatality is the most related to accident severity with a score of 1. The location attributes like Location Northing OSGR, Latitude, Location Easting OSGR, Longitude follow in the list. The Pedestrian Road Maintenance Worker variable was of the least importance with a score of 0.0. Surprisingly, weather conditions had a relevance of 4.2%, which is quite insignificant. Factors like maximum velocity possible, day of the week, vehicles involved in the accident, date, etc. contributed significantly with a score above 20%. Features like details of intersection, location of intersection, kind of road, lighting conditions, age of the casualty, etc., also turn out to be quite important to the hybrid model. All features varying from environmental, physical, geometrical, geographical and historical were included in the top features ranked using this technique. The results obtained are in accordance with one's personal experience and knowledge about the risk factors related to accidents.

Hybrid Gaussian mixture model and support vector classifier results

After data pre-processing and re-sampling, 120,00data samples with 39.996 samples from Class 1, 39,998 samples from Class 2, and 40,006 samples from Class 3 were used as input to the Gaussian mixture model. The top 25 features according to the variable importance ranking results were chosen as features of the input data entries. The data were fitted with a mixture of three Gaussians which correspond to the three accident severity classes. Moreover, principal component analysis (PCA) was applied to visualize the results in 2 dimensions. The results with clustering based on the predictions by the Gaussian mixture model are shown in Figure 9. The mean matrices obtained for all three classes are also listed in Table VII. These results suggest that for a particular class of accident severity, the mean vector is the average value of the observed features. To interpret these results, let us consider an example: if a person is driving at a longitude of -0.527 and has a speed of nearly 48.2 km/hr., then he/she is very likely to have an accident of Class 1 severity, i.e. a no-injury accident. On the other hand, a person traveling at a longitude of 0.743 with a speed of 90.7 km/hr. has very high chance of having an accident of Class 3 severity, i.e. an incapacitating injury. Similarly, with respect to the day of the week, the mean value observed rounded to the nearest integer for Classes 1, 2 and 3 are 4, 3 and 7 respectively. This implies that accidents of the highest severity or fatal accidents are likely to occur on Saturdays. One possible reason for this could be that on Saturdays, there are more cars and more drivers are impaired by alcohol due to weekend celebrations and parties than on any other day. These results are fairly consistent with one's personal experience and logical reasoning.

It is also observed that some values in the mean vectors of Classes 2 and 3 are very close to each other. The reason for this is the uneven distribution of the values inside every feature. For example, the feature, 'Lighting' has 126,049 datat points corresponding to daylight while only 1,123 and 10,314 for darkness light unlit and darkness -no lighting respectively. Thus, daylight itself accounts for 70.45% of the example set, which is a very high number. This sub-skewing of data leads to biasing in favor of the majority class.

The overall accuracy of the Gaussian Mixture Model was 64.68%. These 3 mean vectors were used as input to the support vector classifier. For such a large dataset with 120,000 examples, 3 data points for training would be insufficient and would lead to overfitting. As a result, we used some extra data points alongside the mean vectors for the purpose of training the support vector classifier and further decreasing the testing data. Had there been more classes of accident severity in the dataset, one could have directly used the mean vectors as input for the SVC and hence improve the model performance, like the technique applied in text-independent speaker identification using both SVM and GMM. [START_REF] Bourouba | Novel Approach in Speaker Identification using SVM and GMM[END_REF].

The SVC with radial basis function produced a total accuracy of 84.35%. Precision recall and the F1-score were calculated to quantify the performance of our classifier. In order to compute these parameters, 4 performance metrics given below are evaluated from the confusion metric:  Precision (P): This is defined as the ratio of correctly predicted positive observations to the total predicted positive observations. We then have:

𝑇𝑃 𝑇𝑃+𝐹𝑃 -Macro precision: Precision found by calculating metrics for each label, and then finding their un-weighted mean.

-Micro precision: Precision found by calculating metrics globally by counting the total number of true positives, false negatives and false positives.

 Recall (Sensitivity) (R): Recall is the ratio of correctly predicted positive observations to the all positive observations in actual class, which means: 𝑇𝑃 𝑇𝑃+𝐹𝑁 -Macro Recall: Recall found by calculating metrics for each label, and then finding their un-weighted mean.

-Micro Recall: Recall found by calculating metrics globally by counting the total number of true positives, false negatives and false positives.

 F1 score: F1 Score is the weighted average of Precision and Recall and is used to combine precision and recall in a single metric as in the following: Figure 10 shows the confusion matrix obtained with the hybrid model. As can be observed, there is a clear separation between accidents without any injury (Class 1) and accidents with injury (Classes 2 and 3). Most of the confusion occurs between non-incapacitating injury accident and incapacitating injury accidents. Furthermore, the ROC (Receiver Operating Characteristics) curve and AUC/AUROC (Area Under the Receiver Operating Characteristics) were determined using the above parameters. ROC is a probability curve with TPR (y) plotted against the FPR (x) which is FP/TN+FP. The area under the ROC curve quantifies the model's ability to identify the classes correctly and distinguish between them [START_REF] Bourouba | SMOTE: Synthetic Minority Over-sampling Technique[END_REF]. The AUC-ROC curve for this model is shown in Figure 11. The AUC values for Classes 1, 2 and 3 are 0.99, 0.97 and 0.97 respectively. These values are very close to 1 and reflect the good discriminative power of the classifier. Similarly to AUC-ROC, an area under precision/recall curve (AUC-PR) can also be calculated to show the tradeoff between precision and recall as a function of varying a decision threshold. The higher the area under the curve is, the higher are the values of precision and recall, where high precision relates to a low false positive rate, and high recall relates to a low false negative rate [START_REF] Davis | The relationship between Precision-Recall and ROC curves[END_REF].

For the hybrid model, the AUC-PR curve micro averaged over all classes is shown in Figure 12. The AUC-PR curves for each class represented over the iso-F1 curves are plotted in Figure 13 where an iso-F1 curve is a curve containing all the points in the precision-recall space whose F1 scores are the same.

CONCLUSIONS

Road traffic accidents have become a major cause of injury and death. With increasing urbanization and growing populations, the volume of vehicles has increased exponentially. As a result, traffic accident forecasting, and the identification of accident-prone areas can help reduce the risks of traffic accidents and improve overall life expectancy. The data about the circumstances of personal injury in road accidents, the types of vehicles involved, and the consequential casualties were obtained from data.govt.uk [START_REF]Road Safety Data[END_REF]. The output or the accident severity class was divided into three major categories namely: no injury in the accident, a non-incapacitating injury in the accident and an incapacitating injury in the accident. In this paper, a hybrid classifier was proposed which combines the descriptive strength of the baseline Gaussian Mixture Model (GMM) with the high-performance classification capabilities of the Support Vector Classifier (SVC). A new approach was introduced using the mean vectors obtained from the GMM model as input to the SVC. The model was supported with data pre-processing and re-sampling to convert the data points into suitable form and avoid any kind of biasing in the results. Feature importance ranking was also performed to choose relevant attributes with respect to accident severity. This hybrid model successfully took advantage of both models and obtained a better accuracy than the baseline GMM model. The radial basis kernel outperformed the linear kernel by achieving an accuracy of 85.53%. Data analytics performed including the area under the receiver operating characteristics curve (AUC-ROC) and the area under the precision/recall curve (AUC-PR) indicates the successful application of this model in traffic accident forecasting.

Although a significant improvement in accuracy has been observed, this study has several limitations. The first concerns the dataset used. This research is based on a road traffic accident dataset from the year 2017 which contains very few data samples for the no injury and nonincapacitating injury types of accident. The data was unbalanced not just with respect to the output class but also with respect to the sub features of various attributes. Moreover, aggregating the accident severity into just three categories limits the scope of the study and the results obtained. The greater the number of severity classes, the less is the amount of extra training data required to feed into the SVC to avoid overfitting. Thus, datasets with enough records corresponding to each class are desirable and should be used for in further studies. The second limitation concerns the dependence of the SVC model on parameters and attribute selection. In this study, the performance of SVC relies heavily on the feature selection results and the mean vectors obtained from the GMM. In order to improve the accuracy of the support vector classifier, other approaches like particle swarm optimization (PSO), ant colony optimization, genetic algorithms, etc. could be used for effective parameter selection. In addition to this, more kernels like the polynomial kernel and the sigmoid kernel could be tested in order to improve future model performances.

Figure 1 :

 1 Figure 1: Vehicular ad-hoc networks architecture and message broadcasting scenario

Figure 2 :

 2 Figure2: Traffic-data-acquisition -using-different-detectors[START_REF] Qinglu | Traffic Condition On-line Estimation Using Multi-source Data[END_REF]

  matrix of the Gaussian components λ Set of tuples of model parameters 𝑤 𝑖 , 𝜇 𝑖 , 𝛴 𝑖 M Number of training examples L(x/λ) Log likelihood Symbols used in the support vector classifier Symbols Semantics (𝑥 𝑖 , 𝑦 𝑖 )

Figure 3 .

 3 Figure 3. Algorithm description

Figure .

 . Figure. Accident severity class distribution

Figure 5 :

 5 Figure 5: Gaussian mixture model with K=3 Given the M training vectors 𝑥 = (𝑥 1, 𝑥 2, 𝑥 3,... , 𝑥 𝑀 ), the GMMs are trained with parameter evaluation using Maximum Likelihood (ML) estimation. Assuming all the training vectors are independent, the likelihood function and the log likelihood function turn out to be

1 2‖w‖ 2

 12 𝑠. 𝑡. 𝑦 𝑖 (𝑥 𝑖 𝑤 + 𝑏) ⩾ 1[START_REF] Bishop | Pattern recognition and machine learning[END_REF]

3 .Figure 7

 37 Figure 7. Kernel trick

Figure 9 .

 9 Figure 9. Gaussian mixture modelling results



  True Positives (TP) -These are the examples with 'yes' as their actual class as well as the class predicted by the model.  True Negatives (TN) -These are the examples with 'no' as their actual class as well as the class predicted by the model.  False Positives (FP) -These are the examples with 'no' as their actual class but are predicted as 'yes' by the model.  False Negatives (FN) -These are the examples with 'yes' as their actual class but are predicted as 'no' by the model.

Figure 11 .

 11 Figure 11. ROC curve for the accident dataset

Figure 12 .Figure 13 .

 1213 Figure 12. AUC-PR curve micro averaged over all classes for the accident dataset

Table II .

 II Dataset variables

	of the crash
	Police Force
	Accident Severity
	Vehicles involved
	number of victims involved	Index of the crash
	Date	Vehicle Id code
	Day of the Week	Kind of vehicle
	Time	Towing and Articulation	Index of the crash
	Longitude	Vehicle Maneuver	Vehicle Id code
	Latitude	Position of vehicle	Casualty Id code
	District of Local Authority	Location of intersection	Type of victim
	Local Highway Authority	Skidding and Overturning	Gender of victim
	1st Road Class	Hit Object in Carriageway	Age of victim
	1st Road Number	Vehicle Leaving Carriageway	Age Band of victim
	Kind of roadway	Hit Object off Carriageway	Intensity of the fatality
	maximum velocity possible	1st Point of Impact	Position of the pedestrian
	Details of intersection	Was Vehicle Left Hand Drive	Motion of the pedestrian
	Traffic control at intersection	Journey Purpose of Driver	Position of victim in car
	2nd Road Class	Gender of the Driver	Position of victim in Bus or coach
	2nd Road Number	Age of the Driver	Type of fatality
	Pedestrian Crossing-Human Control	Age band of the Driver	Casualty IMD Decile
	Pedestrian Crossing-Physical Facilities	Motor power	Location of victim's home
	Lighting	Vehicle fuel type
	Road conditions	Age of the vehicle
	road surface conditions	Rider IMD Decile
	Special characteristics of accident	Rider Home Area Type
	location
	Carriageway Hazards
	Type of area
	Police attention

Table III .

 III Variable description

step: Posterior probability estimation

	𝑝(𝑖 𝑥 𝑖 ⁄ , 𝜆) =	𝑤 𝑖 𝑁 𝑖 (𝑥 𝑗 ) 𝑤 𝑙 𝑁 𝑙 (𝑥 𝑗 ) 𝑙=1 ∑ 𝐾	(6)
	M Step: Updating the parameters
	𝑤 𝑖 = 𝜇 𝑖 = ∑ 𝑀 1 𝑀 𝑗=1 (𝑖 𝑥 𝑗 ,𝜆 ∑ 𝑝 𝑀 𝑗=1 (𝑖 𝑥 𝑗 ⁄ , 𝜆) 𝑝 ⁄ )𝑥 𝑗 ∑ 𝑝 𝑀 𝑗=1 (𝑖 𝑥 𝑗 ⁄ ,𝜆)		(8) (9)
	𝛴 𝑖 =	∑ 𝑀 𝑗=1 (𝑖 𝑥 𝑗 ,𝜆 𝑝 ⁄ ∑ 𝑝 𝑀 𝑗=1 (𝑖 𝑥 𝑗 ⁄ ,𝜆) )𝑥 𝑗	2	-𝜇 𝑖	2	(10)

Table IV :

 IV below. Attributes with missing and erroneous values

	Variable name	Number of missing values
	Index of the crash	53701
	LSOA of crash location	17736
	Longitude	59
	Latitude	59
	Location Easting OSGR	35
	Location Northing OSGR	35
	Time	3

Accident severity class Training samples before SMOTE Training samples after SMOTE

	Class 1	2,044	93,170
	Class 2	21,098	93,756
	Class 3	93,321	93,037
		Table V: Data re-sampling results

  , 162471.58, 51.35, -0.53, 502646.61, 381.98, 460.20, 3.60, 4.03, 44.59, 48.21, 3.11, 1.10, 3.13, 5.64, 1.32, 0.42, 4.34, 0.60, 305.99, 1708.36, 40.26, 2.19, 1.15, 0.62] Class 2 [2.43, 119903.62, 50.98, -1.17, 458311.88, 400.35, 497.09, 3.12, 44.00, 55.88, 3.40, 0.99, 2.06, 7.31, 1.36, 0.22, 5.66, 0.48, 0.00, 1733.54, 43.35, 3.42, 1.53, 1.19] Class 3 [2.59, 159126.65, 51.30, 0.74, 591387.43, 234.60, 537.71, 2.85, 7.29, 46.00, 90.77, 2.94, 1.17, 3.98, 7.41, 1.29, 0.34, 4.70, 0.48, 8.20, 1643.93, 35.72, 2.79, 0.88, 1.13] Table VII. Mean vectors using Gaussian mixture model

	Variable			Score	Variable		Score	Variable	Score
	Intensity of the	1	Age of victim		0.092	Did a Police Officer attend scene	0.042
	fatality							of accident?
	Location northing	0.699	Lighting		0.091	Type of area	0.036
	OSGR latitude
	Latitude			0.693	Location of intersection	0.086	Hit object off carriage way	0.029
	Longitude		0.661	Location of victim's house	0.078	Type of fatality	0.027
	Location easting	0.654	Kind of road		0.075	Vehicle Id code x	0.023
	OSGR
	Date			0.439	Age band of victim		0.073	Gender of the driver	0.021
	1 st Road Number	0.385	Kind of road		0.069	Rider home area type	0.018
	District of local	0.317	Skidding and overturning Figure 8: Variable importance score distribution 0.067 Vehicle Id code y	0.018
	authority
	Vehicles involved Day of week Accident Mean matrix 0.288 0.262 class Area of police 0.222 Class 1 [2.5	Carriageway hazards Road surface conditions 2 nd road class	0.067 0.063 0.063	Casualty Id code Special characteristics of accident location Gender of victim	0.017 0.016 0.014
	responsible
	Maximum velocity	0.21	Vehicle IMD Decile	0.062	Position of the pedestrian	0.012
	possible
	Number of victims	0.21	1 st point of impact		0.06	Hit object in Carriageway	0.011
	involved
	Details		of	0.175	Causalty IMD Decile	0.055	Propulsion code	0.011
	intersection
	1 st Road Class		0.129	Age band of the driver	0.052	Towing and articulation	0.01
	Age	of	the	0.12	Journey purpose of driver	0.052	Position of victim in Bus/Coach	0.01
	vehicle?
	Age of the driver	0.117	Type of victim		0.051	Position of vehicle	0.01
	Traffic control at	0.113	Pedestrian	crossing-	0.05	Motion of the pedestrian	0.009
	intersection			physical facilities
	Rider IMD Decile	0.11	Vehicle Manoeuvre	0.049	Was vehicle left hand drive?	0.005
	Vehicle	leaving	0.109	Pedestrian crossing-human	0.046	Pedestrian road maintenance	0
	carriageway			control			worker
	2 nd Road Number	0.108	Position of victim in car	0.045
	Motor power (CC) 0.106	Weather conditions		0.042
					Table VI. Variable relevance scores

Table VIII .

 VIII Confusion metricSubsequently, the performance estimation parameters are defined as  Accuracy (A): This is defined as the ratio of the number of correctly predicted examples over the total number of examples. Hence, we have :

		Predicted Negative	Predicted Positive
	Actual Negative	TN	FP
	Actual Positive	FN	TP

𝑇𝑃+𝑇𝑁 𝑇𝑃+𝐹𝑃+𝐹𝑁+𝑇𝑁

Table IX

 IX

. RBF kernel performance metrics Figure 10. Confusion matrix for accident dataset

The data were obtained from data.govt.uk[START_REF]Road Safety Data[END_REF]. The variable names have been changed, keeping the semantics same as before.[START_REF] Jeong | Early detection of sudden pedestrian crossing for safe driving during summer nights[END_REF] Rapidminer is an open source statistical and data mining tool.


Karima Oukf
email: karima.oukfif@gmail.com

] 674x

Fares Battou

Samia Bouzefrane

Budget-aware performance optimization of workows in multiple data center clouds

Keywords: Workow, Multiple data centers cloud, Makespan Optimization, Budget distribution, HEFT

Users pay to use resources in cloud systems which makes them more demanding on performance and costs. Optimizing the response time of the applications and meeting user's budget needs are therefore critical requirements when scheduling applications. The approach presented in this work is a scheduling based-HEFT algorithm, which aims to optimize the makespan of tasks workow that is constrained by the budget. For this, we propose a new budget distribution strategy named Estimated task budget that we integrate in our budget-aware HEFT algorithm. We use a multiple datacenters cloud as a real platform model, where data transfer costs are considered. The results obtained by our algorithm relative to recent work, show an improvement of makespan in the case of a restricted budget, without exceeding the given budget.

Introduction

Cloud platforms have become the trend for running applications. The cloud-computing paradigm has revolutionized the way of assessing computing resources by proposing a highly versatile availability of resources through a pay-as-you-go model. These features have enabled users to migrate their applications to cloud platforms. Workows are examples of scientic applications which involve a higher performance-computing environment to be executed and cloud platforms oer huge opportunities to solve them. A workow is a popular model for representing scientic computing, including complicated simulation and precise analysis of massive data [START_REF] Lu | A review of cost and makespan-aware workow scheduling in clouds[END_REF]. Scheduling workows, considered as NP-hard [START_REF] Brucker | Scheduling algorithms[END_REF] problem, still remains a fundamental issue in cloud computing although it has been widely studied over the years [START_REF] Oukf | Energy-aware dpso algorithm for workow scheduling on computational grids[END_REF][START_REF] Oukf | Workow scheduling with data transfer optimisation and enhancement of reliability in cloud data centres[END_REF]. During workows scheduling in the cloud, both cloud providers and users are most involved with the makespan and monetary costs criteria. Makespan refers to the completion time of the entire workow and the price that users need to pay due to the usage of cloud resources is the monetary cost. In cloud computing, resources of dierent capabilities at dierent prices are provided. Normally, faster computing resources are more expensive than slower ones. Thus, dierent scheduling strategies of a workow using dierent resources may result in dierent makespan and dierent monetary cost. Therefore, the problem of workow scheduling in the cloud requires both time and cost constraints to be satised [START_REF] Wu | Workow scheduling in cloud: a survey[END_REF].

These two criteria have conicting objectives, and it is important to suggest a trade-o between them. This trade-o inuences the dierent scheduling objectives, which include reducing costs while meeting the deadline, optimizing makespan while meeting the budget, or achieving the deadline and budget as a more exible objective [START_REF] Lu | A review of cost and makespan-aware workow scheduling in clouds[END_REF].

In this work, we focus on optimizing makespan while meeting the budget constraint. The intuition behind this strategy is to nish a workow at a given budget as soon as possible. The objective is to minimize makespan under budget restrictions. Several authors have worked on this issue in single data center clouds, as detailed in the related work section. In this work, we are dealing with the same problem in the context of multiple data centers clouds. Indeed, currently cloud providers have tens of thousands of servers for providing sucient computing resources for applications. These resources are deployed in multiple data centers.

We propose a budget-aware HEFT algorithm for performance optimization of workows in IaaS multiple data centers cloud. Our goal is to optimize the makespan and meeting the budget while scheduling workows. For this, we propose a novel budget distribution approach based on estimating task features.

The rest of this paper is organized as follows. Section 2 gives an overview of the related work, followed by our budget-aware scheduling algorithm formalization in sections 3. The proposed scheduling algorithm based on HEFT is outlined and evaluated in Sections 4 and 5 respectively. Finally, Section 6 summarizes the results and concludes the paper.

Related Work

It is generally accepted that the problem of workows scheduling upon distributed systems is NPhard [START_REF] Brucker | Scheduling algorithms[END_REF]. In this mind, heuristic and meta-heuristic strategies are used to generate high-quality and approximate solutions with polynomial time complexity. Makespan and cost still remain the most relevant criteria to optimize while scheduling workows in clouds. Several approaches have been proposed to optimize makespan, cost or both. Work such as [START_REF] Verma | Cost-time ecient scheduling plan for executing workows in the cloud[END_REF] and [START_REF] Ghafouri | Time-cost ecient scheduling algorithms for executing workow in infrastructure as a service clouds[END_REF] proposed budget and deadline constrained heuristics based upon Heterogeneous Earliest Finish Time (HEFT) to schedule workow over cloud resources. The proposed heuristics present a benecial trade-o between execution time and execution cost under given constraints.

A list multiobjective optimization technique is designed by [START_REF] Han | Cost and makespan scheduling of workows in clouds using list multiobjective optimization technique[END_REF] to minimize monetary costs for deadline constrained workows in cloud environments. The authors select the non-dominated solutions by combining the quick non-dominated sorting approach with the crowding distance.

In [START_REF] Arabnejad | Budget and deadline aware e-science workow scheduling in clouds[END_REF][START_REF] Zhou | Budget-deadline constrained approach for scientic workows scheduling in a cloud environment[END_REF], the authors focus on budget and deadline aware workow scheduling. Their idea presented in [START_REF] Arabnejad | Budget and deadline aware e-science workow scheduling in clouds[END_REF] is to satisfy both budget and deadline constraints while introducing a tunable cost-time trade o over heterogeneous instances. In [START_REF] Zhou | Budget-deadline constrained approach for scientic workows scheduling in a cloud environment[END_REF] a workow scheduling algorithm to nd a feasible solution for a workow that meets budget and deadline constraints is proposed. Based on the execution cost of the task on the slowest resources and the optimistic spare budget, the algorithm generates the task optimistic available budget. Then, it builds the set of suitable resources according to the task's optimistic available budget to control the range of resources selection, and thus controls the task execution cost.

Many studies have addressed the issue of scheduling workows eectively given budget constraints. In order to achieve this goal, many works apply budget distribution strategies for workow scheduling in the cloud. A budget distribution strategy consists of assigning a sub-budget for each task of the workow.

The algorithm presented by [START_REF] Zheng | Budget-deadline constrained workow planning for admission control[END_REF] is an extension of the HEFT heuristic except for the selection phase (task-ressource assignment). The algorithm distributes the budget to all tasks in proportion to their average execution time on the available resources. Then, the resource chosen is the one that allows the task to be accomplished early at a cost not greater than its allocated sub-budget.

The authors in [START_REF] Arabnejad | Budget distribution strategies for scientic workow scheduling in commercial clouds[END_REF] propose a workow partitioning that focuses on the dependency structure inherent to workow tasks. The partitioning leads to several levels each containing independent tasks. Several methods are introduced to distribute the global budget over these levels. According to the authors, the most eective strategy is the so-called 'All-in' which places the entire budget on the entry-level. Thus any remainders are trickled down to later levels. In our work, we implemented this strategy for comparison purposes.

In [START_REF] Rodriguez | Budget-driven scheduling of scientic workows in iaas clouds with ne-grained billing periods[END_REF] authors propose a scheduling algorithm whose objective is to optimize a workow's execution time under a budget constraint. Their approach focuses on ner-grained pricing schemes that provide users with more exibility and the ability to reduce the inherent wastage that results from coarser-grained ones. Their approach partitions the DAG into a bag of tasks prior to its execution and then distributes the budget over the tasks. The drawback of their clustering phase is the parallelism limitation because of grouping several dependent tasks of workow at the same level, which leads to the performance degradation of the workow.

The authors in [START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] extended the two well-known algorithms, MIN-MIN [START_REF] Tracy D Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF] and HEFT [START_REF] Haluk Topcuoglu | Performance-eective and low-complexity task scheduling for heterogeneous computing[END_REF] to budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous. In addition, they improved these versions with rened ones that aim to re-schedule some tasks on faster VMs.

In [START_REF] K Kalyan Chakravarthi | Budget aware scheduling algorithm for workow applications in iaas clouds[END_REF], the authors proposed a normalization-based budget for constraint workow scheduling algorithm. Their algorithm controls the resource selection phase of each task according to the available budget, thereby increasing the probability of the 'best' resource selection.

All of these studies deal with the workfow scheduling problem in a single data center cloud and eliminate or underestimate data transfer costs, unlike today's cloud providers that rely on multiple data centers. The cost model used in previous studies did not consider the charge of data transfers in the cloud although most cloud providers charge for the actual data storage depending on the amount of data being stored. Moreover, we propose a new way of distributing the budget over the workow tasks dened based on estimating their characteristics.

In this paper, we assume a multiple data centers cloud platforms that provide for workow applications heterogeneous resources under budget and we consider a charged peer-to-peer transfer mode instead of resorting external global storage.

Problem Formalization

This section begins by detailing the application and the platform models, then we formalize the workow scheduling problem. The aim of our scheduling heuristic is to nd a schedule S for the workow (w) with a minimum makespan while respecting the budget.

Application model

A scientic workow application (w) is modeled as a DAG (Directed Acyclic Graph):

G = (V, E),
where V is a set of n vertices representing tasks t i (1 i n), and E is a set of directed edges. An edge e(i, j) ∈ E corresponds to a dependence constraint between task t i and t j , in which t i is an immediate parent task of t j , and t j the immediate child task of t i . A child task cannot be executed until all of its parent tasks are completed. A task with no parent tasks is called an entry task and a task with no children tasks is called an exit task. The data matrix, with n×n dimensions, represents the data volume exchanged between tasks.

Cloud resource model

We consider platforms dened by an IaaS cloud where computer resources (instances) can be deployed on dierent data centers. During this section, we use the time model that species the data transfer times between data centers that we detailed in our previous work [START_REF] Oukf | Workow scheduling with data transfer optimisation and enhancement of reliability in cloud data centres[END_REF]. Then we present a cost model that takes into account the costs of the instances as well as those of the transferred data.

Time model In IaaS clouds, computer resources are instantiated as Virtual Machines (V M s) which are deployed on dierent data centers. Typically, cloud providers oer multiple types of V M ; V M = vm 1 , vm 2 , ..., vm q is the set of V M s with heterogenous processing capacity.

The estimated execution time of the task t i in a V M of type vm p is dened by the computing time (CT (t i , vm p )).

The transfer time T T (i,j) (see equation ( 1)) taken to transfer data from task t i (executed on vm p lodged in data center DC a ) to task t j (executed on vm k lodged in data center DC b ) corresponds to an edge (i, j) ∈ E in the application graph (DAG).

T T (i,j) = data ij T ransf er rate (p,k) (1)
The transfer time T T (i,j) is proportional to the size of the output data data ij produced by task t i and transferred to t j , and is inversely proportional to the heterogeneous transfer rates or the bandwidths T ransf er rate (p,k) when the tasks are executed on dierent data centers.

We note that when two communicated tasks are executed on the same V M , the transfer time is equal to zero and when they are executed on dierent V M s that are lodged in the same data center also the transfer time is neglected. Thereby, the total computing time T CT (t i , vm p ) of a task in a V M is computed as shown in Equation [START_REF] Arabnejad | Budget and deadline aware e-science workow scheduling in clouds[END_REF].

In this equation, m refers to the number of parent tasks of t i (predecessors). The boolean s m is equal to 0 if t i and t j run on the same virtual machine (p = k) or to 1 otherwise. Besides, the value r m is equal to 1 to indicate that the VMs can be hosted in dierent datacenters.

T CT (t i , vm p ) = CT (t i , vm p ) + m j=1 s m .r m .T T (j,i) (2)
In the formula (2) the product s m × r m indicates the inclusion of data transfer times between the V M s according to the following two cases:

1. Transfer time between V M s in the same datacenter is neglected:

r m = 1 if DC a = DC b 0, else 2.
Transfer time between V M s in the same datacenter is not neglected:

r m = 1 , then s m × r m = s m
In order to calculate the makespan, which refers to the total execution time T CT (w) of all the tasks of the workow, it is necessary to dene for each task these two attributes EST (t i , vm p ) (Earliest Start Time) and EF T (t i , vm p ) (Earliest Finish Time) as following:

The EST (t i , vm p ) of the task t i on the machine vm p , is calculated according to the following recursive procedure: If the task has no parent tasks, then EST (t i , vm p ) = 0, otherwise the task can start executing as soon as its parent tasks are nished and their output data is transferred. However, if the resource is occupied by another task at this point, the execution of the task t i should be delayed until this virtual machine vm p is free again.

The procedure (3) calculates the value of EST (t i , vm p ):

EST (t i , vm p ) = 0, if t i has no parent tasks max{avail[vm p ], max t k ∈pred(ti) {EF T (t k , vm q )}}, else (3)
Where: pred(t i ) is the set of immediate predecessors of the task t i (parents of t i ), avail[vm p ] is the next instant time when the resource vm p will be ready or available for task execution.

To determine EST (t i , vm p ), the maximum value between avail[vm p and max t k ∈pred(ti) {EF T (t k , vm q )} is selected, where avail[vm p ] is the maximum completion time of previous tasks of t i on the same virtual machine vm p . The value avail[vm p ] guarantees that a virtual machine processes one task at a time, while max t k ∈pred(ti) {EF T (t k , vm q )} guarantees that a child task starts after all of its parents have nished their execution.

The EF T (t i , vm p ) of the task t i on the machine vm p is given by the following equation:

EF T (t i , vm p ) = EST (t i , vm p ) + T CT (t i , vm p ) (4)
The makespan or the total computing time T CT (w) of the workow is dened by the equation [START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF], and which corresponds to the completion time of the last task in the workow.

T CT (w) = max{EF T (t i , vm p )} [START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] Cost model To deal with the pay-as-you-go cost model of the cloud, we need to incorporate the budget constraint in our approach.

The total cost of the whole workow execution is the sum of the cost due to the execution of all its tasks in the platform.

The cost due to the execution of a task on a given VM vm p is dened by the equation ( 6) and the cost of data transfers for this task is given by the equation [START_REF] Fahringer | Askalon: a tool set for cluster and grid computing[END_REF].

Cost(t i , vm p ) = CT (t i , vm p ) × U C vmp (6) T rcost(t i ) = m i=j data ij × r m × U C data (7)
Where U C vmp is the per time unit cost for using the vm p , U C data is the unit cost for transferring data and m the number of successor tasks of t i . In the equation [START_REF] Fahringer | Askalon: a tool set for cluster and grid computing[END_REF], data ij refers to the data transferred from t i to t j . The boolean r m indicates if the data transfers are achieved in the same datacenter (r m = 0) thereby the data transfers fees are eliminated, or within dierent ones (r m = 1). The cost for a task is then given by the equation [START_REF] Ghafouri | Time-cost ecient scheduling algorithms for executing workow in infrastructure as a service clouds[END_REF].

Cost(t i ) = Cost(t i , vm p ) + T rcost(t i ) (8)
Altogether, we give the total cost for the workow execution as [START_REF] Han | Cost and makespan scheduling of workows in clouds using list multiobjective optimization technique[END_REF]:

Cost(w) = n i=1 Cost(t i ) (9)
Objective Given a budget B, our objective is to nd the schedule that minimizes the makespan while the budget is respected, namely: min{T CT (w)} while Cost(w) ≤ B. In this section, we will rst describe the HEFT algorithm, then we propose a new budget distribution approach named Estimated task budget. Afterward, we present the Budget-aware HEFT heuristic for scheduling workows with budget constraints in multiple datacenter cloud. HEFT heuristic is one of the most popular list-based scheduling algorithms. It determines the scheduling of a DAG in a heterogeneous environment in order to minimize the makespan of the application. HEFT is integrated into important projects like ASKALON project [START_REF] Fahringer | Askalon: a tool set for cluster and grid computing[END_REF] to provide scheduling for a quantum chemistry application.

HEFT Algorithm

HEFT is a well-established list scheduling algorithm that prioritizes a workow task with a higher rank. It determines the rank value for each task, based on the average execution time and the average communication time between the resources of two successive tasks. The HEFT algorithm orders the tasks on the dierent resources in a given order based on a value of a rank attribute. Ranks in HEFT are calculated based on the estimated average computation and communication times of the tasks. Indeed, the tasks are sorted according to their scheduling priorities, which are based on the increasing rank (upward rank, noted rank u ). The value rank u is the maximum distance of a task from the DAG output task. The rank of a task is dened recursively as follows:

rank u (t i ) = CT (t exit ), if t i = t exit CT (t i ) + max tj ∈succ(ti) {T T (i,j) , rank u (t j )}, else (10)
Where:

succ(t i ) is the set of immediate successors of task t i . CT (t i ) the average cost of running the task t i . T T (i,j) is the average cost of the communications of the edge (i, j).

This rank is calculated for all the tasks of the DAG starting with the exit task. The exit task has as rank only the average of the computation times on the dierent resources since it has no successor tasks.

The HEFT algorithm works in two phases; (i) The prioritization phase during which the priorities of all tasks are calculated using rank u . Next, a list of tasks is generated by sorting the tasks according to their decreasing rank (priorities). (ii) The resource selection phase during which the tasks are assigned to computing resources which minimize their (Finish Time). The time F T (t i , vm p ) of a task i on a computational resource vm p corresponds to the time at which the task nishes its execution, that is to say, the time of its start time ST (t i , vm p ) (Start Time) added to the time of its execution.

The HEFT algorithm proceeds according to the algorithm (1).

Algorithm 1: HEFT algorithm Data: W : workow, P F : platform ; Result: S: a schedule; 1 begin 2 Calculate the rank for all the tasks by traversing the DAG upwards from the exit tasks according to the equation ( 10); 3 Sort the tasks in a list following the rank in descending order ; 4 while there are unscheduled tasks in the list do [START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] Select the rst task ti in the task list; 6 foreach vmp with p = 1..V M do 7

Calculate F T (ti, vmp) ; 8

Assign the task ti to the machine vmp such that F T (ti, vmp) is minimum ; 9 end 10 end 11 end Before detailing our algorithm, we explain the new budget distribution strategy that we designed for our budget-aware HEFT scheduling algorithm.

Budget Distribution

The main of budget distribution is to scatter the provided budget (B) to the workow tasks. Each task receives a fragment of this budget. Several methods of budget distribution have been proposed. Example of recent strategies we quote [START_REF] Arabnejad | Budget distribution strategies for scientic workow scheduling in commercial clouds[END_REF][START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] cited in the related work section. In this work, we propose a novel budget distribution strategy for our budget-aware scheduling algorithm, the Estimated Task Budget. With the Estimated Task Budget (ETB) strategy, we estimate the budget required for each task according to the costs of its processing time and the costs of the data transfers that it needs. This estimation is much closer to the specic needs of each task than any other fair approach. The ETB approach better reects the needs of the tasks when the workow is running in multiple data centers clouds. This is possible by also estimating the costs of transfers made between datacenters, which are not always free. Therefore, the initial budget used to cover the total execution of a workow w can be distributed to the workow tasks according to the features of each of them. We propose to estimate the proportional budget B(t i ) reserved for a task t i using the equation [START_REF] Oukf | Energy-aware dpso algorithm for workow scheduling on computational grids[END_REF].

B(t i ) = CT (t i ) n i=1 CT (t i ) × U C vmp + m j=1 data ji (x,y)∈E data (xy) × U C data (11)
For each ready task, we calculate the corresponding sub-budget B(t i ) of the initial budget (B) in proportion to the entire workow. The rst summand in the equation ( 11) concerns the unit cost of an instance by the ratio of the average computing time of a given task to the overall computing time of the workow. The second summand represents the unit transfer cost by the ratio of the required data of a given task t i to the total data to be transferred in the workow.

Any unused fraction of the budget consumed when assigning previous tasks is recovered by the algorithm. For this purpose, the algorithm uses the variable B remain which is initialized to zero for entry tasks but reclaims any remaining budget in previous assignments for the other tasks.

Budget-aware HEFT Algorithm

In this subsection, we present a budget-aware HEFT algorithm to allow its execution on workows in multi-datacenter cloud platforms with budget constraints. We call this algorithm B -HEF T .

Initially, the HEFT heuristic [START_REF] Haluk Topcuoglu | Performance-eective and low-complexity task scheduling for heterogeneous computing[END_REF] is presented to schedule a task graph on a set of heterogeneous processors. The adaptation of the HEFT heuristic, for the execution of workow on platforms such as multi-datacenters clouds with budget constraint, requires rethinking the stage of instance selection to a given task (or the assignment of tasks to VMs phase).

Using the proposed time model described in section 3.2, we adapted the HEFT heuristic to the multi-datacenter cloud model. Moreover, we use the Estimated task budget for distributing the global budget over the workow tasks.

The B -HEF T is described by the following algorithm (2). Our algorithm started by sorting the tasks in a list following the rank u in descending order (lines 2 and 3). Initially, for each task t i in the ordered list, our algorithm aects the cheapest V M in the platform P F (lines 7 and 8) as the best V M , which does not necessarily provide the minimum earliest nish time for this task. The EF T (t i , vm p ) is obtained using the equation (4)(line 9). The algorithm calculates the share of the budget for each task using the proposed Estimation task budget (line 10). In addition, the algorithm recovers any part of the remaining budget from previous tasks (line [START_REF] Oukf | Energy-aware dpso algorithm for workow scheduling on computational grids[END_REF]. From line 12 to line 19, the algorithm calculates the EF T (t i , vm p ) according to the equation ( 4) with each VM vm p . Then, the task cost is generated using equation [START_REF] Ghafouri | Time-cost ecient scheduling algorithms for executing workow in infrastructure as a service clouds[END_REF]. The B-HEFT algorithm veries the nish time, checks if the budget B(t i ) is not exceeded, and updates the minimal nish time and the best vm if it's necessary. Afterward, the algorithm evaluates the remaining budget by subtracting its real cost from its own reserved budget. Finally, the algorithm returns the best vm for the task (line 19).

Evaluation and Results

In this section, we present the experiments carried out to evaluate the performance of the proposed approach.

To assess the performance of our approach, we tested the algorithms with workows generated based on the characteristics of two well-known real workow applications, Montage and CyberShake, from two dierent scientic elds.

Algorithm 2: B-HEFT algorithm

Data: W :workow, P F : platform, B: Budget; Result: S: a schedule; 1 begin 2 Calculate the rank for all the tasks according to the equation ( 10); 3 Sort the tasks in a list following the rank in descending order ; 4 while there are unscheduled tasks in the list do [START_REF] Caniou | Budget-aware scheduling algorithms for scientic workows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] Select the rst task ti in the task list; The CyberShake workow is a data-intensive application of seismology used to describe earthquakes by generating synthetic seismograms. The Montage workow is used in astronomy for generating mosaics personalized from the sky using a set of input images. Most of its tasks are I/O intensive. These workows are generated by WorkowGenerator 4 tool. The structure of the small workows are shown by Fig. 1.

We modeled an IaaS provider platform with a platform of three data centers with 125 MBps as Bandwidth and $0.055 per GB as data transfer cost. In each data center, three types of VMs can be allocated. Their characteristics (CPU power and cost) are similar to the c4 compute-optimized instance types oered by Amazon EC2. The congurations of the VM type used are shown in Table [START_REF] Arabnejad | Budget distribution strategies for scientic workow scheduling in commercial clouds[END_REF].

In the experiments, dierent budget intervals were employed. We assume that the minimum budget (B min ) for running the workow equals the cost of running all tasks on the single cheapest VM. We establish four dierent budget intervals based on this minimum budget as indicated in equation ( 12), then we use the rounding to an integer value for B. B = α B min where 0 < α < 5 [START_REF] Oukf | Workow scheduling with data transfer optimisation and enhancement of reliability in cloud data centres[END_REF] 4 https://conuence.pegasus.isi.edu/display/pegasus/WorkowGenerator We assessed dierent workows to compare performance with respect to workow size. We used 25, 50 and 100 tasks for Montage workow and used 30, 50 and 100 tasks for CyberShake workow.

To aord a baseline comparison, we implemented a 'uniform' distribution as a basic strategy and an adapted version of the 'All-in' distribution proposed in [START_REF] Arabnejad | Budget distribution strategies for scientic workow scheduling in commercial clouds[END_REF].

The uniform distribution strategy operates blindly, sharing the budget provided over the set of tasks by equal sharing. Except for the number of tasks, no other information concerning the workow structure or task characteristics is considered. With the 'All-in' distribution strategy, the total budget is assigned to the rst level. After serving all tasks at this level, any remaining budget is trickled to the next level. Since our B-HEFT algorithm does not perform level building preprocessing, we implement an 'All-in' version based on the ordered list of tasks instead of levels. In this case, the total budget is given for the rst ready task in the workow. Then after serving this rst task, the remaining budget will be devoted to the next ready task in the list, and so on.

Montage workow

Fig. 2 shows the makespan achieved for Montage workow using dierent budgets. With the different sizes of Montage workow, our algorithm, plotted as 'Estimated' for Estimated task budget shows identical makespan as 'All-in' approach. Both 'Estimated' and 'All-in' perform better than the 'Uniform' strategy. This is due to the fact that when 'uniform' equitably distributes a restricted budget (B=1, B=2 for Montage-25 for example) between all the tasks, the share of each becomes insucient. Then the algorithm assigns the tasks to the cheap instances, thus increasing the makespan (since the cheap instances are also slow). We point out the power of our algorithm to improve makespan compared to 'All-in' using a minimal budget.

In fact, our algorithm, using the 'Estimated' approach for sharing the budget, distributes for each task a sucient sub-budget which is close to its real cost. On the other hand, 'All-in' is more generous with the rst tasks of the workow (starting with the input tasks) by assigning them the maximum budget, therefore being able to run on faster instances. Unfortunately for the last tasks, if the budget is not sucient, they run on slow instances which lengthens the makespan. The costs recorded for Montage workow based on dierent budgets are shown in Fig. 3. The costs recorded by our strategy are very close to those obtained by the 'All-in' case. The 'Uniform' strategy got reduced costs for the restricted budgets because it assigns the tasks to the cheap instances in this case to the detriment of the makespan. These benets are visible in particular for signicant sizes workows like Montage with tasks sizes 50 and 100 (gure 3 (b) and (c)). In most cases, the three strategies meet the budget.

CyberShake workow

Fig. 4 shows the makespan achieved for CyberShake workow using dierent budgets. With Cy-berShake, our approach also achieves makespan identical to those obtained by 'All-in' with relaxed budgets, but rather better in the case of a restricted budget for all the CyberShake task sizes (Fig. 4 (a),(b) and (c)).

The makespan obtained by 'Uniform' is high compared to 'Estimated' and 'All-in' especially in with restricted budgets. Note that in the case of CyberShake with 100 tasks, 'Uniform' fails to optimize the makespan even with a relaxed budget (Fig. 4) (c)). Our approach achieves performances identical to those obtained by the 'All-in' strategy with relaxed budgets, but rather better in the case of a restricted budget.

As shown in Fig. 5, the results of CyberShake workow regarding the costs are plotted. The costs realized by our approach are very close to those obtained by 'All-in' except for the workow of size 100. In this case, 'All-in' behaves better compared to our approach. This is due eventually to the fact that the estimated values of the task's characteristics are not suciently accurate when dealing with a large number of tasks.

With the 'Uniform' strategy, the tasks costs are reduced. But in reality, the approach is unable to oer sucient budgets for tasks with restricted budgets. It just runs them on cheap instances without actually meeting the task's needs. When oering a relaxed budget, 'Uniform' recorded costs as high as these of the other two approaches. In this paper, we presented a budget-aware HEFT algorithm for optimizing makespan when meeting the budget. The budget-aware algorithm is based on an estimated task budget which calculates the budget share required for each task in the workow. We target as a platform the multi-datacenter clouds so that the costs of data transfers between data centers are considered. We evaluated the makespan and costs using two real-world workows with budget scenarios. Our approach shows identical makespan as 'All-in' distribution strategy but surpasses it in the case of restricted budgets. The 'Uniform' approach is far from being competitive with our algorithm by recording slower makespan. This makes the power of our algorithm to improve makespan with a minimal budget. In most cases, our algorithm behaves as an 'All-in' approach, without exceeding budget constraints.

Future work will focus on extending the experimental tests with large scale workows. Other more precise performance metrics will be used to better assess the proposed algorithm.

4

  Budget-aware HEFT Based Scheduling algorithm

Fig. 1 :

 1 Fig. 1: Structure of the small scientic workows

Fig. 2 :

 2 Fig. 2: Makespan for Montage workows grouped by Budget

Fig. 3 :Fig. 4 :

 34 Fig. 3: Cost for Montage workows grouped by Budget

Fig. 5 :

 5 Fig. 5: Cost for CyberShake workows grouped by Budget

  6 // initialization: BestV M as the cheapest V M ; 7 U Cvm = min{U Cvm p } with p = 1..V M ; 8

		BestV M = vm;
	9	Calculate EF T (ti, BestV M ) according to the equation (4) ;
	10	Calculate B(ti) according to the equation (11) ;
	11	B(ti) = B(ti) + Bremain;
	12	foreach vmp with p = 1..V M do
	13	Calculate EF T (ti, vmp) according to the equation (4) ;
	14	Calculate Cost(ti) according to the equation (8) ;
	15	if ((EF T (ti, vmp) < EF T (ti, BestV M )) and (cost(ti) ≤ B(ti))) then
	16	EF T (ti, BestV M ) = EF T (ti, vmp) ;
	17	BestV M = vmp ;
	18	Bremain = B(ti) -cost(ti)
	19	end
	20	Assign ti to BestV M ;
	21	end
	22	end
	23 end

Table 1 :

 1 Type and prices of VMs

	VM type Name vCPU Price per Seconde ($)
	1	small	2	0.0045
	2	medium 4	0.009
	3	large	8	0.018