1 Introduction

Cloud computing has recently emerged as the new generation of distributed computing where its objective is to realize the idea of providing computational services as the fifth utility service after water, electricity, telephone and gas services [1]. In line with the needs of different areas of IT, the following three different types of services can be provided by cloud computing: IaaS (infrastructure as a service), PaaS (platform as a service) and SaaS (software as a service) [2, 3]. By inheriting several achievements such as pervasive computing, grid computing, service-oriented architecture and Web 2.0 from information technology, cloud computing has led to the development of new software engineering generation in which software application is provided as a SaaS on the Internet rather than as a package [4].

In a cloud environment, users can submit their requests for a software application service on the internet. In many cases, users might request complex services in a cloud environment which cannot be provided by a single service. Hence, under such circumstances, a user’s request has to be accomplished as a composite service; this composite service includes individual services which are constructed in advance [5, 6]. Due to the high inclination of numerous IT companies to provide cloud services, there are many candidates for each abstract service of each request workflow with the same functionality but differing in quality of service (QoS) attributes such as cost, response time and availability [7]. As a result, the service composition system should select those services among the concretes of the abstract services which have the highest quality. However, the global quality of selected services should not exceed the quality constraints specified by the users, documented in service level agreement (SLA) contracts [8–10]. Hence, QoS-aware service composition is a multi-constraint optimization problem (MCOP) which can be mapped into multi-dimensional multiple-choice knapsack problem (MMKP) [11–15].

In the cloud environment, composite services are produced on-the-fly based on users’ on-demand requests. Under these conditions, composing service within a very short time is the critical significance, i.e., there should be a trade-off between optimality and execution time. The QoS-aware service composition problem is known as an optimization problem with NP-hard characteristics. Consequently, some of the researchers have used genetic algorithm and other heuristic methods to find an optimal global solution [16–19]. However, regarding the inherent features of these algorithms, especially genetic algorithm, there are some problems. First, these algorithms select initial population from the search space randomly. In dynamic cloud environment, sometimes, the number of services increases remarkably [20–23], so the convergence speed of these algorithms is reduced, and service composition time increases [18, 24–27]. Second, since these heuristic algorithms can continue endlessly but by specifying a termination criterion usually to be restricted, so such execution led to the reduction of qualitative optimization of the selected composite service [18, 21, 26, 28].

For handling this problem, researchers have used different hybrid heuristic algorithms [23–25, 29–31]. Some researchers have used service clustering techniques to reduce the search space of the problem [30, 32–34]. However, in the related works, there are a few disadvantages. For example, in these works, clustering is repeated online for each new request. In regard to high growing number of cloud services, this massive time overhead could make the corresponding methods inefficient for real multi-cloud and public cloud environments. In the previous works, simple utility function and a hierarchical cluster selection method have been used [32, 33]. The QoS attributes are globally specified by the users per composite service, not individually per its concrete services. Hence, selection of appropriate clusters could not be guaranteed. Thus, because of inappropriate selection of the clusters, inefficient initial population will be generated; consequently, the inefficient initial population will decrease the optimality of the solutions and convergence of these methods.

In this paper, using a combination of genetic algorithm and data mining techniques, an efficient method is presented for dealing with the above-mentioned challenges. Our proposed method targeted all types of cloud, especially public clouds. The major contributions and the novelty of the present study are as follows:

  • Service clustering technique is used to reduce the search space of the problem which resulted in the reduction of the search time. Unlike previous works [30, 32, 34], in the proposed method, clustering is conducted at the beginning of system initialization, and it is repeated in the determined intervals based on a specific rate of service increase. Consequently, it leads to the reduction of computational overhead.

  • Other contribution of our work is that the association rule mining is used for selecting appropriate clusters based on semantic relations between clusters in composite services history. Such appropriate clusters will be the input of the genetic algorithm as the initial population. Simulation results show that our algorithm performs well in terms of solution feasibility, optimality and time complexity compared with other works.

The rest of the paper is organized as follows: In Sect. 2, we describe service composition problem formally and briefly review the related studies. In Sect. 3, a detailed account of the proposed genetic-based algorithm for service composition is given. In Sect. 4, the simulation of the proposed method is described, and the related experiments for verifying and analyzing it are elaborated. Finally, in Sect. 5, the conclusion of the study and directions for further research are mentioned.

2 Background and related works

The issue regarding service composition process is selecting an appropriate service among many similar services for executing a task and ultimately producing a composite service (Fig. 1). Inasmuch as service composition component is the core of supplying cloud applications, hence, due to its vital significance, there is an essential need for embedding a section in the middleware of cloud computing systems as the service composition unit. There are two general strategies for QoS-aware service composition: local service selection and global optimization of composite services [35–37]. Each of these strategies is briefly described below.

  • Local selection of a service: It is appropriate for distributed systems where centralized management is not practical. In this strategy, a service is selected from among candidate services for an abstract service regardless of other abstract services within a workflow. This strategy does not consider the global constraints specified by the user.

  • Global optimization of composite services: In this strategy, an appropriate service is not independently selected for an abstract service in the workflow. Rather, the selection is made with regard to concrete services chosen for all other abstract services of the workflow. The purpose of this method is to select the best concrete service for each of the abstract services so that a composite service with the highest quality within user-determined constraint framework can be obtained.

2.1 Service quality model

As shown in Eq. (1), the global quality of a composite service should be measured based upon the workflow structure of that composite service.

Fig. 1
figure 1

An example of a composite service

Full size image

In many previous studies [16, 32, 37], the following four pattern types are considered in the internal structure of composite services which are supported by business process execution language (BPEL) [17]:

  • Sequence: sequential execution of services.

  • AND: parallel execution of services.

  • Branch: branching or conditional execution of services.

  • Loop: repetitive execution of services.

Table 1 indicates the manner of measuring global values for QoS parameters in a composite service [32, 37].

Table 1 Method of calculating qualitative values
Full size table

2.2 Statement of the problem

In composing a service, the issue which should be considered is the selection of individual and atomic services with high-value qualitative parameters. Indeed, this issue should be taken into consideration so that the total parameters should not exceed the constraints specified by the users. Service composition issue can be formalized by Eqs. 1 and 2.

(1)
$$\begin{aligned}&\sum \nolimits _{{l=1}}^{p}\,{W}_\mathrm{l}=1 \end{aligned}$$
(2)

The workflow of a composite service is defined by the vector WF \(= ({T}_{1}, {T}_{2}, {\ldots }, {T}_{\mathrm{n}})\), and a candidate composite service is denoted by \(\hbox {CS}=({S}_{1}, {S}_{2}, {\ldots }, {S}_{\mathrm{n}})\), where \({T}_{{i}}\) refers to a task with an abstract service in the workflow and \({S}_{{i}}\) denotes a selected concrete service for the \({T}_{{i}}\) service in the candidate composite service. The qualitative constraints specified by the customer are represented by the vector \(\hbox {SLA}=(\hbox {SLA}_{1}, \hbox {SLA}_{2}, {\ldots }, \hbox {SLA}_{\mathrm{p}})\). In Eq. (1), \(\hbox {SLA}_{\mathrm{j}}\hbox {(CS)}\) function determines the value of the \({j}\mathrm{th}\) global qualitative parameter specified by user for the CS composite service. Also, \({Q}_{\mathrm{j}}\) (CS) function determines the \({j}\mathrm{th}\) qualitative parameter for the CS composite service, and \({W}_{\mathrm{L}}\) indicates the weight of the \({L}\mathrm{th}\) qualitative parameter. By taking Eqs. (1) and (2) into account, optimal composite service should be achieved.

2.3 Related works

Before the emergence of cloud computing, service composition was accomplished in service-oriented architecture (SOA) and grid environment. The SOA service composition is involved with the realization of a workflow using concrete services. Also, service composition is another term for resource scheduling in grid environment [16]. However, it should be pointed out that the first impression about service composition in cloud environment appears to be a combination of service composition in SOA and grid computing. It is a comprehensive process which includes the discovery and selection of software services which are deployed on infrastructure services. Such services are selected based on customers’ non-functional requirements and constraints specified through SLAs.

QoS-aware service composition is an optimization problem which has several potential solutions, and only some solutions are optimal. Furthermore, each of the studies reviewed in this section focused on one or more of the following criteria: SLA contract support, centralization or decentralization of the composition algorithm, automaticity of the composition process, consistency and compatibility and concentration on inherent features of cloud environment including economic aspects, longevity of composition, scalability, etc. Some of the related works, which are briefly overviewed below, tried to solve service composition optimization problem using classic algorithms [14]. In [37], a two-stage hybrid method was proposed in which global optimization was combined with local selection to benefit from the advantages of both methods. In this study, mixed integer programming (MIP) was used for decomposing global QoS constraints into local constraints, so that services can be selected both locally and in a parallel form. In [38], a two-stage method was used for optimal service composition so that services can be composed dynamically and reliably. In the first stage, culture genetic algorithm (CGA) was used for selecting the best service composition schemes. Then, global QoS constraints were decomposed into local constraints. In the second stage, proper concrete services for each of the workflow tasks were selected based on improved case-based reasoning. This group of algorithms just has aimed to solving service composition as optimization problem regardless of time complexity of algorithms.

Achieving an optimal solution within a short time has motivated researchers to use combinatorial algorithms [15, 39]. The proposed method in [8] produces composite services using QoS requirements in the cloud environment for service composition; the corresponding authors tried to produce composite services with appropriate qualitative attributes within acceptable time. In [40], genetic algorithm was used to compose services by taking customers’ qualitative requests and SLA constraints into consideration. Skyline notion was used in this algorithm to enhance composite service quality and convergence speed. Moreover, to overcome the time-consuming issue of service composition problem, the paper [18] proposed the use of genetic programming for web service composition, investigating three variations to ensure the creation of functionally correct solutions. It also optimized the composition according to their quality of service.

Particle swarm optimization (PSO) with integer array coding was used to solve the service composition problem in rational time [29]. To achieve this goal, the skyline operator with binary decision variables was used to eliminate improper services from the search space. The time complexity of these combinatorial algorithms is much better than the classic algorithms. However, their execution time is not acceptable for an increasing number of services yet [24–26]. Because of on-demand and on-the-fly form of service composition, it should be made a trade-off between optimal solution and composition time. But result evaluations show that with increasing the number of concrete services led to much more increasing of time complexity. To resolve this critical problem, some researchers applied local selection and global optimization together.

In [24], an improved merging genetic algorithm and ant colony algorithm was used for solving the time complexity of service composition. In first stage global optimal paths is found by genetic algorithm and in second stage globally optimal solution by running ant colony algorithm. In [41], researchers combined the optimized gravitational attraction search algorithm with the imperialist competitive algorithm to develop a new memetic algorithm. This algorithm was used for simultaneously obtaining response time and optimal or near-optimal execution cost to compose services in the cloud environment. In [42], Niche particle swarm optimization (NPSO) was used to achieve higher cognitive speed and find optimal composite service. Moreover, NPSO and intelligent multi-objective PSO were used to produce a set of Pareto optimal composite services by optimizing various objective functions simultaneously. A new proposed method in [31] combines two composition strategies to solve time and local optima issues of service composition problem. The global search process is performed by the genetic algorithm, which applies a novel roulette wheel selection to avoid premature convergence. To reduce the time complexity, the local search is done by the fruit fly optimization phase.

In [43], contextual data, such as geographical information, were used to identify similar neighbors for each requester. Then, QoS records of the similar neighbors were used to obtain more accurate prediction values. The basic rationale behind this study is that the users or services with similar service invocation context are more likely to receive similar QoS values. Due to publishing services on multiple clouds, an algorithm was proposed in [44] for cloud service composition which can compose services from different clouds. The algorithm selects the cloud with the maximum number of services which increases the feasibility of composition with minimal time overhead. The method proposed in [45] was intended to efficiently find a composition across multiple clouds. It included a greedy algorithm and ant colony optimization-based algorithm which was aimed at selecting feasible composite services using the minimum number of clouds that led to less computational time.In [46], a heuristic algorithm was implemented along with service clustering technique for grouping of similar services. This algorithm was capable to reduce the execution time and nearly promised the optimal result as well. Because of dynamic nature of the cloud environment, sometimes, the number of services increases remarkably [20–23]; consequently, these algorithms are not sufficiently effective in terms of convergence speed and optimality [18, 24–27].

Some other works have also used clustering techniques with heuristic algorithms to improve composition speed by reducing problem space. In [32], researchers first clustered all service classes. Then, they used quality utility function and a heuristic method to find a service close to the optimal service. In case a problem is observed and detected by continuous monitoring, alternative compositions can be used. Using the pre-built service clusters in [34], a method has been presented for selecting candidate service set with the effectively reduced searching space and semantic comparison complexity. It could obtain more optimal compositions by filtering services with the dynamically determined threshold based on the best composition QoS in the process of composition. In [30], authors have used clustering for categorizing the web services to find similar services. Then, an ant colony algorithm is applied for finding the best set of services.

As mentioned above, clustering technique is used for local selection in the previous works. However, none of these works has an efficient pattern to select service clusters for global optimization. There are two main problems in these works:

  • First, clustering is repeated online for each new request. In regard to high growing number of cloud services, this massive time overhead could make the corresponding methods inefficient for real multi-cloud and public cloud environments.

  • Second, in the previous works, simple utility function and a hierarchical cluster selection method. QoS attributes are globally specified by the users per composite service, not individually per its concrete services. Hence, selection of appropriate clusters could not be guaranteed. Because of inappropriate selection of the clusters, inefficient initial population will be generated; consequently, the inefficient initial population will decrease the optimality of the solutions and convergence of these methods.

In this paper, to solve the above-mentioned problems, we propose a new approach using genetic algorithm and data mining techniques toward service composition in cloud environment. Each abstract service is initially clustered. When a new request is received, appropriate service cluster is selected based on semantic relations between service clusters; semantic relation is extracted by association rule mining. After selecting the appropriate service clusters, as initial population, the genetic algorithm is used to find out optimal or near-optimal solutions (composite service) regarding the QoS constraints determined by users.

3 The proposed method

As discussed above, due to the rapid increase in the number of cloud services and cloud users, the previous combinatorial methods are not adequately efficient in the dynamic cloud environment. With regard to this research problem, unsupervised data mining techniques were used to propose a novel method. Clustering and association rules were used for local selection of services, and genetic algorithm was used to achieve a global optimal solution within the criteria announced by the user. Different phases of the proposed service composition method include pre-processing phase, contract-making phase, service composition and customer request execution phase and maintenance phase, each of which is described below.

3.1 Pre-processing phase

This phase includes the following four stages: normalization of the qualitative attributes of services, service clustering, clustering of users’ SLA and discovering association rules between users’ SLA clusters and service clusters. Algorithm 1 shows the pre-processing phase.

figure a

3.1.1 Normalization of qualitative attributes of services

The scales of qualitative attributes of services are different. As a case in point, in the experimental environment used in this study, while reliability index was between 0 and 1, response time was a figure which could vary from 100 to 3000 ms for each service. Consequently, measuring high-value attributes led to a bias against low-value attributes.

Thus, Eq. (3) is used to normalize all the attributes into a range from 0 to 1 [16, 26]. In this study, the high and low values for QoS attributes are obtained by searching for the minimum and maximum values for the intended QoS attributes among samples for each respective service [12, 25, 26]. Furthermore, when a new service is added, the related information should be updated.

$$\begin{aligned} q_{{S_{ij}}}^{l} =\left\{ {{\begin{array}{l} {\big (q_{{S_{ij}}}^{l} -\mathrm{Min}\big ( {q_{{S_{i}}}^l} \big ){\big /}\big ( {\mathrm{Max}\big ( {q_{{S_i}}^{l}} \big )-\mathrm{Min}\big ( {q_{{S_{i}}}^{l}} \big )} \big )\quad \text {for positive attributes}} \\ {\big ( {\mathrm{Max}\big ( {q_{{S_i}}^{l} } \big )-q_{{S_{ij}}}^l }\big ){\big /}\big ( {\mathrm{Max}\big ({q_{{S_i}}^{l}} \big )-\mathrm{Min}\big ( {q_{{S_{i}}}^l}\big )} \big )\quad \text {for negative attributes}}\\ \end{array} }} \right. \end{aligned}$$
(3)

In Eq. (3), \({q}_{{\mathrm{S}_{\mathrm{ij}}}}^\mathrm{l}\) refers to the lth qualitative attribute of the \({j}\mathrm{th}\) service from the \({i}\mathrm{th}\) abstract service. Also, \(\hbox {Min}({q}_{{\mathrm{S}_\mathrm{i}}}^\mathrm{l}\)) and \(\hbox {Max}({q}_{{\mathrm{S}_\mathrm{i}}}^\mathrm{l} )\) were the lowest and highest values of the lth qualitative attribute for the \({i}\mathrm{th}\) abstract service.

3.1.2 Service clustering

Regarding the hypothesis that users’ requests with identical requests and identical SLA contracts require similar service qualities, hence, we should classify concrete services of the abstract services in the cloud system. In public cloud systems and the systems which supply web services, announcements, interfaces and the qualitative attributes of the services are published by their providers on UDDI (universal description, discovery, and integration) registries [47]. In the system proposed in this study, the method for producing information functions in this way: service information is collected through UDDI registries, and clustering is applied on them. When a new service is discovered, it is added to the related similar cluster based on mapping. Whenever the development rate, i.e. the number of services, reaches the threshold which was specified by the managers, clustering is updated again.

For classifying concrete services in the proposed method, K-means algorithm was used which is simple, fast and efficient [48–50]. In this algorithm, after the number of clusters for each abstract service is determined and cluster centers are selected, services are clustered according to the minimal Euclidean distance between cluster centers and services. Distance is measured using the following equation:

$$\begin{aligned} \sqrt{\sum \nolimits _{{l}=1}^{k} \left( {q_{{C_{ij}}}^l -q_{{S_{ij}}}^l} \right) ^{2}} \end{aligned}$$
(4)

In this equation, \(q_{{C_{ij}}}^{l}\) denotes the value of \({l}\mathrm{th}\) qualitative attribute for the \(\hbox {j}th\) cluster center, and ith stands for abstract service. Thus, \(q_{{S_{ij}}}^{l}\) indicates the value of the \({l}\mathrm{th}\) qualitative attribute for the \({j}\mathrm{th}\) concrete service of the \({i}\mathrm{th}\) abstract service. In service clustering, weight was not considered for the qualitative attributes. Indeed, weight should be given according to users’ views for each request. However, if so, clustering has to be repeated per request. Consequently, it will impose excessive computing overhead and long execution time.

3.1.3 SLA clustering

In this system, content of users’ requests for composite services including operational and non-operational needs are processed. For meeting operational needs, a workflow is defined for executing the intended request. Nevertheless, regarding the non-operational need which includes the wanted qualitative features, an SLA contract is established with the user. Indeed, each request is translated into a workflow and an SLA contract and is stored in the database. At the outset of the establishment of the system, clustering is carried out based on the available records in its history. With the arrival of any new request, the record related to the respective cluster is mapped and is registered on it; whenever the development of the database grows at a particular rate which has been determined by the system managers, clusters are updated via the repetition of clustering. Clustering users’ requests is also carried out based on the similarity of the content of SLA contracts. K-means algorithm is also used here. SLA contracts are clustered through Eq. (5) according to the minimal Euclidean distance.

$$\begin{aligned} \sqrt{\sum \nolimits _{{l}=1}^{k} \left( {\mathrm{SLA}_{ci}^{l} -\mathrm{SLA}_{uj}^{l} } \right) ^{2}} \end{aligned}$$
(5)

In this equation, \(\mathrm{SLA}_{ci}^l\) refers to the \({l}\mathrm{th}\) qualitative attribute included within \({c}_{{i}}\) cluster center. Hence, \(\mathrm{SLA}_{uj}^l\) stands for the \({l}\mathrm{th}\) qualitative attribute of the \({j}\mathrm{th}\) request of the \({u}\mathrm{th}\) user.As discussed above, an identical weight was given to all the attributes.

3.1.4 Discovering association rules between contracts and cluster services

As mentioned before, the underlying rationale for the proposed method is that for accomplishing similar requests with similar qualitative needs, the services with similar qualitative attributes should be selected. In general, such services are included within the same cluster. For enhancing the efficiency of service composition, at first, we should determine the clusters from which services were selected for realizing previous composite services. Apriori association rule extraction algorithm was used on the history data of the composite services requested by users [48–50]. As a result, we could discover the related clusters of different abstract services. In this study, the term related service clusters refers to the clusters from which services have already been used for realizing the workflows of similar requests. In the next stage, for selecting a concrete service of a request, we only refer to the pre-specified clusters of the related requested abstract services in workflow. This operation has two significant results: first, service composition time decreases due to the reduced search space. Second, the compatibility between qualitative attributes and user’s requests increases because previously experienced service clusters are used. The example illustrated in Tables 2 and 3 shows the details about the extraction of association rules using the Apriori algorithm in our method. Table 2 contains part of a sample composite services history. In this table, Si_Cj is an ordered pair that Si shows an abstract service, and Cj shows the corresponding selected cluster. Also, Table 3 shows part of association rules extracted by Apriori algorithm through composition histories illustrated in Table 2.

3.2 Contract-making phase

In this phase, user request for a needed composite service, qualitative features and quality constraints specified by the customer are negotiated and determined. Then, they are registered in the form of an SLA contract in the system. The SLA obtained in this phase creates the foundation for the development of composite service. That is, composite service is produced based on supporting qualitative attributes which are registered in the SLA contract.

Table 2 Service composition history
Full size table
Table 3 Association rules
Full size table

In this system, there is a subsystem which monitors the implementation and performance of the contract. At any moment, it monitors the qualitative attributes of the service and records the changes. In case the service provider breaches the guaranteed service attributes, the customer should be compensated for the damages according to the contract. The operation of the SLA monitoring and maintenance system is presented in [51], and the adaptability model and the modification and revision of the qualitative loss of system services are demonstrated in [52, 53]. Also, in our system, after the configuration of the composite service and the beginning of its execution, SLA monitoring unit continuously examines the qualitative attributes of each of the services and compares them with their reference values which are stored in Service QoS database. If the service is impaired with regard to QoS, hence, selecting and replacing the appropriate alternative service lead to the desirable continuation of service based on SLA content which is stored in SLA database, and the shortcoming of the service provision is stored in the SLA violation database for compensation (Fig. 2).

3.3 Service composition

In this phase, service composition system maps the customer to the related cluster according to the values and contents of the SLA contract. Then, based on the service clusters related to that SLA cluster, the system develops the composite service for accomplishing customer’s request.

The first phase of the proposed method which includes the clustering of services and SLAs is passive. It is done at the beginning of system initialization. The clusters should be updated for increasing a certain number of services or SLA contracts. However, the other three phases are active which are once executed for each composite service request. Service composition phase includes two stages: finding appropriate service clusters and using genetic algorithm for global optimization. In first stage, local services are first selected. Local service selection includes mapping a user’s SLA contract into a similar SLA cluster. Then, service clusters used in the history of that cluster are extracted for instantiating each abstract service. In the second stage, genetic algorithm is implemented to find the globally optimal service composition. That is, services leading to the highest quality composition are selected from the determined clusters of abstract services. However, the final composite services should not exceed the quality constraints determined by the user. The steps of the proposed method are described as follows:

  1. 1.

    Finding appropriate service clusters: In this stage, user SLA is first mapped to an appropriate SLA cluster via mapping function. This procedure is accomplished based on the closest Euclidean distance between user SLA contract and the centers of the SLA clusters. After the specification of the related cluster, relevant association rules to that cluster are fetched. Then, using algorithm (2), the most useful service clusters are selected for realizing the workflow of the requested service. The process of finding appropriate clusters is shown in Fig. 3. Table 4 shows an example of which clusters is selected for a sample workflow by algorithm (2). Table 4 shows the results of execution of algorithm (2) to find appropriate clusters for a workflow shown in Fig. 4; this algorithm uses the association rules shown in Table 3. SLA of this request has been assigned to SLA cluster 0. Default cluster has been assigned for each abstract service that could not find any cluster for it using the algorithm.

  2. 2.

    Global optimization by the genetic algorithm: The primary focus of the method proposed in this paper is to reduce the execution time and enhance the coverage of users’ qualitative requirements. Time reduction is a result of search space reduction through service clustering. Coverage enhancement of users’ requests is related to fetching services from appropriate clusters. That is, services should be selected from clusters

Fig. 2
figure 2

SLA monitoring system

Full size image
Fig. 3
figure 3

Finding appropriate service clusters

Full size image

which have already been experienced. Clustering leads to the substantial reduction of the search space problem; however, the remarkable increase in the number of cloud environment services leads to an increase in the population of each service cluster. Hence, for performing the search within an acceptable time limit, the genetic algorithm was used for searching a solution with global optimization [54, 55]. Indeed, several heuristic methods, such as PSO, imperialist competitive algorithm, etc., have been proposed for finding an optimal solution. Each method has specific capabilities and features which are considered to be appropriate for a solving particular issues and problems. In different studies [27, 56, 57], researchers have demonstrated the efficiency and efficacy of the genetic algorithm in solving different optimization problems in comparison to other global optimization methods. The investigations indicated that the genetic algorithm had significantly better performance in terms of response optimality and convergence speed. As discussed above, there are two reasons and justifications for using the genetic algorithm. The first reason is that this algorithm has special features which make it suitable for solving the intended problem discussed in this study. It evolves solutions based on the population rather than the individual. For selecting an optimal solution, it operates only based on the fitness function with simple arithmetic expressions. Furthermore, it does not require complex calculations for producing the initial population which is simply produced based on probability. The second major justification for using this algorithm is that it has been extensively used by researchers in the past for solving the service composition problem. Previous studies have proved several advantages and the desired performance of the genetic algorithm in comparison with other methods [16, 40]. In this paper, the researchers demonstrated the merits of the novel combinatorial method in comparison with other methods.

Table 4 Selected clusters of workflow
Full size table

Different stages of the proposed method are illustrated in algorithm (3). After getting a user’s request and making an SLA contract, the suitable clusters for selecting the services required for the composite service are found through algorithm (2). Then, the first generation of the solutions is produced by randomly selecting specified number of individuals of the population from the clusters related to each abstract service. Next, the population of solutions evolves and develops by the genetic algorithm. This operation is done through a specific number of repetitions and through achieving optimal conditions. The required stages and components of the genetic algorithm for solving the intended problem are given below.

figure b
figure c

Gene and chromosome: In this problem, each gene stands for a selected concrete service for instantiating an abstract service. Also, infrastructure services are used for executing that service. A service can be indicated as \(\hbox {Genome}_{\mathrm{i}}=(S_{ij} ,Vm_{l},Net_{k},Db_{m})\) in which Vm, Net and Db as infrastructure services refer to virtual machine, network bandwidth and data storage, respectively, which are used for executing \({S}_{\mathrm{ij}}\) service. Each chromosome refers to an individual from the generation population which indicates a solution. Chromosome is a set of genes which is denoted by \(chrom_{n}=(genome_{1}, genome_{2}, {\ldots }genome_{m})\) in which m refers to the number of the abstract services of a workflow.

Fitness function: For solving the problem through the genetic algorithm, fitness degree should be used as a criterion for selecting an individual for the next generation of the population. In this method, fitness function specifies an individual’s fitness according to the highness of positive qualities and the lowness of negative qualities. Furthermore, this function satisfies the constraints specified by the user in measuring the value of fitness as formulated in Eq. (6).

$$\begin{aligned} \mathrm{fitness}\left( {C_\mathrm{n}}\right)= & {} \sum \limits _{l=1}^{p} W_l .\mathrm{NQ}_l \left( {\mathrm{CS}} \right) \end{aligned}$$
(6)
$$\begin{aligned} \mathrm{NQ}_{l} \left( {\mathrm{CS}} \right)= & {} \left\{ {{\begin{array}{l} {\frac{Q_{l} \left( {\mathrm{CS}} \right) -Q_l \left( {\mathrm{SLA}} \right) }{Q_l \left( {\mathrm{SLA}} \right) }\quad \mathrm{for\,\,negative\,\,attributes}} \\ {\frac{Q_l \left( {\mathrm{SLA}} \right) -Q_l \left( {\mathrm{CS}} \right) }{Q_l \left( {\mathrm{SLA}} \right) }\quad \mathrm{for \,\,positive\,\,attributes}} \\ \end{array} }} \right. \end{aligned}$$
(7)

In Eq. (6), \({C}_{\mathrm{n}}, {W}_{\mathrm{l}}\) and \(\hbox {NQ}_\mathrm{1}\hbox {(CS)}\) refer to chromosome, vector of the weights of qualitative attributes and the normalized value of the lth qualitative attribute of the composite service, respectively. Moreover, in Eq. (7), \({Q}_{1}\hbox {(CS)}\) and \({Q}_{1}\hbox {(SLA)}\) indicate the \({l}\mathrm{th}\) qualitative parameter of the composite service and the agreed value for the \({l}\mathrm{th}\) qualitative parameter of the composite service in the SLA contract, respectively.

Selection operator: Genetic evolutionary algorithm can lead us to producing the best generation if the best individuals from the current generations have more chance for going to the next generation. For doing so, roulette wheel algorithm was used for selecting the individuals. In this method, a cumulative probability is assigned to each individual with respect to its fitness value. Using this value, the selection chance of each individual is determined.

Crossover operator: For executing the crossover operator on a generation, at first, the current generation is randomly divided into two groups, i.e., father and mother. Then, using probability, a pair from the two sets is selected, and a random cut-off point is selected (Fig. 4). For producing a new pair as the children who inherit features from their parents, the genes above the cut-off point are repeated without any changes and the genes under it are exchanged with other genes. Then, the children’s chromosomes are added to the population list. Figure 5 depicts an example of the crossover operator in the proposed method. For the sake of simplification, only the concrete service of each gene was illustrated, but the infrastructure services were not included in the figure.

Fig. 4
figure 4

Workflow of composite service request

Full size image

Mutation operator: This operator was used for providing participation opportunity for the potential genes which could not participate in the initial generation of the population. This operator leads to the production of new generations without resulting in early convergence.

Fig. 5
figure 5

An example of crossover operator

Full size image

Consequently, evolution proceeds until an optimal or a near-optimal solution can be achieved. It selects a chromosome based on probability which is a concrete service of an abstract service and its infrastructure services. Then, the gene is randomly replaced with another gene (Fig. 6).

Execution and termination policy of the algorithm: The execution of this algorithm is repeated until the algorithm can satisfy the users’ constraints most optimally. While executing this algorithm, if an optimal response is not produced, the algorithm will be repeated until the convergence is obtained and a near-optimal response is produced. However, if the convergence is not achieved after the maximum number of repetitions, it can be argued that it is not feasible to construct an acceptable composite service within this system for the requested service.

3.4 Maintenance phase

In this phase, the selected composite service is executed and monitored. In case a problem occurs, the composite service will be repaired, recovered, recomposed and executed. We have considered an online explore unit in this system which searches service UDDIs over the public cloud systems. If a new service is found, based on distance from the cluster centers, it will be added to one of the related clusters. If a specific threshold is met, updating and reorganizing the database including service clusters, SLA clusters and association rules are done in an offline way. As a case in point, the experimental results reveled that when concrete services of an abstract service and SLAs increase for more than one percent, services and SLAs should be re-clustered. Also, in our experiments, when composite services grow for one percent, association rules should be re-extracted.

Fig. 6
figure 6

An example of mutation operator

Full size image

4 Simulations

4.1 Simulation environment

In this section, the characteristics of the simulation environment and the data used in the present study are described. The proposed method was simulated by VC#.net 2013 language. The hardware used for simulating the method was an Intel Core 2 Duo, 2.5 GHZ processor with 3 GB RAM memory, and the utilized operating system was Windows XP.

Table 5 Distribution of services on clusters
Full size table

Regarding the production of datasets, since there were not any benchmarked datasets, we used the QWS dataset in the simulation which was collected by Al-Masri and Quasay [58]. The QWS dataset has been frequently used by several researchers in this field such as [17, 18, 21]. It includes 10 qualitative attributes for 2506 web services. In fact, this dataset for testing the hypothesis of the study, i.e., the investigation of the impact of local selection via clustering on the improvement of service composition time complexity, we needed a dataset including much more services, we expanded the number of services to 10,000 services for which we used a controlled random generation methodology based on normal distribution. We selected three quality attributes of availability, response time and successability from QWS services and calculated price for them within the intervals of 5 to 100 dollar depending on three other qualities. Algorithm (4) has used for creating a service for the expanding of QWS. In this dataset, 10 types of abstract services were considered, each of which was clustered within 10 clusters by means of the K-means algorithm. The clusters are shown in Table 5. The set of used data included only web services (software). For infrastructure services (virtual machine, network bandwidth and database), three sets of services including 100 services and 4 above-mentioned attributes were randomly produced.

figure d
Table 6 Distribution of SLAs on clusters
Full size table

For the workflows, we designed 50 samples, ranging from simple (linear) samples to complex (including loop and parallel service execution) samples. However, since we could not find a real set for the SLA contracts and inasmuch as we did not get any results from communicating and corresponding with business companies which provide cloud services, an SLA dataset consisting of 2000 sample SLAs was randomly produced. It was clustered through K-means algorithm (Table 6).

The simulations were planned and carried out for testing and substantiating the following three hypotheses:

  • Hypothesis one: for realizing composite service requests with similar qualitative requirements included within identical SLA clusters, most services are selected from the same service clusters.

  • Hypothesis two: due to the search space reduction of the problem, the time complexity of the algorithm will be better than other algorithms.

  • Hypothesis three: since all similar and appropriate services of a request are clustered in a service cluster, the obtained fitness value is higher at a certain time or for a certain number of repetitions. Consequently, it results in a higher user satisfaction.

4.2 Experiments and evaluation of the results

For evaluating the advantages of the proposed method (CGA), it was analyzed and compared with service composition method with normal genetic algorithm NGA [16] and SCA [40] with skyline-based genetic algorithm. The efficiency of the proposed method was compared with the above-mentioned methods in terms of different parameters. The population size for all genetic algorithms was 500. The convergent criterion for all genetic algorithms was that the best fitness value does not improve over the last 100 iterations.

4.2.1 Distribution of service selection on clusters

This experiment was related to testing the first hypothesis. Indeed, if requests for identical composite services have similar SLA contracts, i.e. they are located within the same cluster, then the concrete services selected for producing those composite services will be placed in the same cluster. As a result, two workflows were produced, and the real service clusters of each abstract service were once clustered within five clusters and for the second time, they were clustered within ten clusters. The experiment was repeated for 100 times by randomly selecting SLA contracts from two different clusters. In this experiment, normal genetic algorithm was used without clustering. After selecting services, we specified which services belong to which clusters. As shown in Fig. 7a, b, this experiment indicated that in case the number of service clusters is assumed to be five, the absolute majority of the selected services will belong to one cluster. Nevertheless, as depicted in Fig. 7c, d, if there are ten clusters, the relative majority of selected services will be from one or two clusters. Our analysis shows that in a system with five clusters on average, 69 % of services are selected from a cluster and in a system with ten clusters on average, 60 % of services are selected from two clusters. These results confirm hypothesis one.

Fig. 7
figure 7

Distribution of selected services on clusters

Full size image

4.2.2 Time and speed of service composition

For testing the second hypothesis of the study, the researchers designed and implemented experiments so as to investigate and compare service composition time in the proposed method with those of the above-mentioned methods. Hence, the experiment was carried out on six different workflows and was repeated for ten times on each different workflow, and the average efficiency was computed for each of them. The same experiment was also implemented for SGA and NGA methods. As illustrated in Fig. 8, it can be observed that the average service composition time for the proposed method was less than those for the other methods. Although service composition time increases as the number of requested services in the workflows increases, the slope for the service composition time in the proposed method was less than those of the other methods. Moreover, it was found that service composition time of the proposed method did not have a regular linear growth. That is, when the number of abstract services increases significantly, slope of the figure does not increase accordingly. Indeed, this is attributed to the random nature of the genetic algorithm. Furthermore, the results indicate that the proposed method is a scalable method, and its efficiency does not decrease as the number of concrete services increases. Figure 9 indicates that the convergence speed of the proposed method is better than those of other two methods. Despite the fact that the number of repetitions for reaching a reply increases along with an increase in the number of abstract services in the workflow, the performance of the proposed method is better than that of the other two methods.

Fig. 8
figure 8

Service composition time

Full size image
Fig. 9
figure 9

Number of the repetitions of the genetic algorithm

Full size image

4.2.3 Optimality evaluation

For testing and substantiating the third hypothesis of the study, we designed experiments through which the fitness value of the selected solution of the proposed method can be analyzed and compared with those of the two other algorithms. This experiment was conducted within the same conditions of the preceding experiment. Figure 10 shows the results of this experiment. In addition to the high significance of speed in achieving a response, it should be noted that attaining a response with high optimality can enhance customer satisfaction. In other words, the result indicates that as the number of abstract services in the workflow increases, the efficiency of the proposed method does not decrease in terms of the optimality degree of the solutions.

It should be noted that some of the results of the NGA method implemented in this study which are reported in Figs. 8 and 9 are different from the results published in [16]. This diversity is attributed to the difference between range of data in our dataset and their dataset. Also, our fitness function is different from their function which may affect the results shown in Fig. 10.

Fig. 10
figure 10

Fitness value

Full size image

We compared the proposed method with other methods in terms of composition time, convergence speed and the degree of fitness of the produced composite service. Regarding the obtained average times for different methods in relation to the number of services, it was found that the average composition execution time for the proposed method was 343.62; however, the obtained values for the other methods were 656.25 and 637.87. Such a difference in average time between the proposed method and the other methods indicates the significant efficacy of the proposed method on optimizing composition time. Convergence speed was experimented and investigated with the number of repetitions. The average number of repetitions in the proposed method was 24, and in the other methods, it was 54 and 58, respectively. Indeed, the reason for clustering and selecting service clusters is the fitness with user request which is obtained from the association rules. These results indicate the superiority of the proposed method to other methods with regard to convergence speed. The average fitness value which was obtained for the composite services by the proposed method and the other two methods was 0.107, 0.06 and 0.077, respectively. These results indicate the superiority of the degree of optimality of the proposed method to the other methods. The reason for which is the accumulation of the population of similar services in clusters and the selection of appropriate clusters as the input of the genetic algorithm. Since the selection of the genetic algorithm population is carried out in a guided way rather than randomly, hence, the produced composite services have a high degree of optimality.

Fig. 11
figure 11

Feasibility

Full size image

4.2.4 Feasibility rate

In addition to optimality and convergence speed of the service composition algorithm, it can be argued that having a great chance of reaching a reasonable response in a method is also important. For examining and testing the proposed method with respect to the probability of success and feasibility, six workflows were defined. Then, the proposed method and the two other methods were tested for each workflow for 50 times under identical qualitative criteria. Figure 11 indicates that the feasibility of the proposed method is higher than that of SGA and NGA. The reason for this result is that the proposed method selects services from experienced clusters. Thus, success probability within a specific time or specific number of repetitions is significantly enhanced.

4.2.5 Impact of clustering population

The preceding experiments revealed that, due to search space reduction of the genetic algorithm, clustering can lead to the improvement of this algorithm in terms of service composition time, optimality, convergence speed and the degree of feasibility. The question arising at this point is that how many more clusters can we increase and how much can we reduce the space? Is there an intermediate point for the number of clusters? For finding answers to these questions, we designed an experiment in which concrete services of each abstract service were clustered within 0, 5, 10, 20 and 30 clusters in distinct datasets. Then, using six different workflows, the experiments were conducted on time, optimality and convergence speed of the dataset. As shown in Figs. 12 and 13, it can be observed that even in case the clustering number is low, the performance of the proposed method is better than the normal genetic algorithm. It should be pointed out that the efficiency is enhanced as the number of clusters increases. As a case in point, when there were 10 and 20 clusters for concrete services, service composition time and convergence speed of the proposed algorithm were better than the mode with 5 clusters. However, the performance of the algorithm decreased when there were 30 clusters. Thus, it should be highlighted that selecting an appropriate number of clusters has a remarkable impact on the efficiency of the algorithm. In contrast, as depicted in Fig. 14, the number of clusters has no significant impact on the fitness value of the solutions obtained by the proposed method.

Fig. 12
figure 12

Composition time for each clustering type each clustering

Full size image
Fig. 13
figure 13

Number of iterations for each clustering type

Full size image
Fig. 14
figure 14

Fitness values for each clustering type

Full size image

To evaluate the significance of clustering impact on the fitness values of solutions, we used the ANOVA (analysis of variance) as a statistical test. In this test, each group refers to a specific fitness values per different cluster numbers. Table 7 shows the results of ANOVA test. As Table x indicates, the obtained P value (0.04) and the obtained F ratio (2.87) confirm a significant difference between the composition time using different cluster numbers. Therefore, the null hypothesis is rejected, and hence, the clustering has significant impact on the composition time. The results shown in Table 7 confirms hypothesis x.

To show that use of clustering has significant impact on the fitness values of solutions, we used the ANOVA test. In this test, each group refers to a specific fitness values per different cluster numbers. Table 8 illustrates the results of ANOVA for groups of experimental data. As Table x indicates, the obtained P value (0.01) and the obtained F ration (3.68) confirm a significant difference between the fitness values of obtained solution with and without clustering. Therefore, the null hypothesis is rejected, and hence, the clustering has significant impact on the fitness values. The results shown in Table 8 confirm hypothesis x.

To evaluate the effects of number of clustering on the fitness values of the solutions, we used the ANOVA test; each group refers to a specific fitness value per different cluster numbers. As Table 9 shows, the obtained P value (0.89) and the obtained F ration (0.19) confirm a non-significant difference between the fitness values of different cluster numbers. Therefore, the null hypothesis is accepted, and hence, the number of clustering has not significant impact on the fitness values.

Table 7 ANOVA test for time complexity
Full size table
Table 8 ANOVA test for evaluating impact of clustering on fitness value
Full size table
Table 9 ANOVA test for evaluating impact of cluster numbers on fitness value
Full size table

5 Conclusion and directions for further research

In this paper, an attempt was made to identify the requirements of service composition based on SLA contract in cloud computing environments. Inasmuch as services have been remarkably enhanced in cloud environment and customers are concerned with the speed of requested service delivery as well as service quality, researchers in this study used data mining techniques such as clustering, association rules in service composition and genetic algorithm for reducing the search space of a problem. Based on the findings of the study, it can be concluded that these techniques can result in the reduction of service composition time and the enhancement of the optimality of compound services. Furthermore, the results of the study indicated that the proposed method is scalable; hence, it is highly appropriate for dynamic cloud environments. Nevertheless, in this study, sufficient attention was not given to fitness function which should be addressed in future studies. Although the total fitness value of a composite service is good, some qualitative features might sometimes bias other features which can reduce customer satisfaction. As a direction for further research, fuzzy logic might be used in the fitness function to handle this problem. Also, optimizing the clustering method might enhance the efficiency of the proposed method which should be addressed in further research.