DDAPSO: Hybrid Discrete Dragonfly Algorithm and Particle Swarm Algorithm to Service Selection and Composition for the Internet of Things Applications

Nowadays, Internet of Things (IoT) is a hot spot for researchers and industries. It establishes the road for the development of new intelligent applications that may be used to provide unique and important services in a variety of fields, including smart cities/homes, transportation, healthcare monitoring, industrial automation, agriculture, etc. [1].

IoT is composed of many smart objects providing software services that abstract diverse functionalities (abstract service (AS)). Composite services (CS) are made up of these functionalities that can be combined to develop new applications, to meet complicated user needs and specific quality of service (QoS) requirements (such as response speed, throughput, availability, price, popularity, etc.).

Service-oriented architecture (SOA) encourages the development of complex applications by combining atomic services to deliver new functions that none of the services could give individually [2].

The word “concrete service” refers to a real service in this work, whereas an abstract service, also known as a class of services or tasks, defines the concrete service abstractly. There may be numerous physical services for each abstract service, each with the same functionality, but maybe varying in quality levels.

The composition method consists in generating a new service class by putting together existing classes in a plan or actions flow, and then determining the best bindings between these classes and their concrete services, also known as candidate services [3].

The QoS-aware service selection and composition (QoS-SC) problem is a combinatorial optimization problem that is also an NP-hard problem. Metaheuristics, such as bio-inspired algorithms, are commonly used to solve such types of problems. The goal of this research is to create a new hybrid bio-inspired algorithm “DDAPSO” to solve the QoS-SC problem. In DDAPSO two algorithms are coupled: The first one is a Discrete Dragonfly Algorithm (DDA) and the second one is a particle swarm optimization algorithm (PSO).

To conduct the evolutionary process, The proposed algorithm combines two phases: The first one is the exploration phase and uses a discrete version of the Dragonfly Algorithm (DDA) and the second one is the exploitation phase, which is considered as a local search strategy, and uses the particle swarm optimization algorithm (PSO). The exploitation phase improves on the findings of the exploration phase by looking deeper into the process of finding potential places in search space.

When there is no nearby dragonfly, the discrete dragonfly algorithm [4] uses the Levy flight technique to enhance random behavior in the exploitation phase. This could considerably improve the algorithm’s exploring process. However, the best personal solution of dragonflies is not used in the process. Due to this, DDA converges to the optimal solution very slowly and can become stuck in the local optima or perhaps be unable to find an optimal solution.

On another side, particle swarm optimization (PSO) [5] has been demonstrated in many prior works to discover the best solutions to a variety of problems. Since may rapidly converge to the optimal solution, it is a good candidate for the exploitation phase because it equated finding the optimal solution by exploiting the best solutions of the particles.

The subsequent parts of the paper are organized as follows. Section 2 introduces the related work. The QoS aware service in IoT and the Mathematical model for QSS are presented in section 3. In section 4, the proposed algorithm is presented in detail, including the solution schema and its fitness evaluation and the two phrases used in the algorithm. Section 5 analyses and discusses the experimental results. Finally, conclusions and future work are given in Section 6.

As stated in the introduction, QoS aware service selection and composition in IOT refers to the combination of relevant abstract services given by multiple service providers clustered together in order to serve the user request. Different services are required for the execution of these requests by the user. Workflow refers to the sequence of specialized services required to complete a task. Figure 1 shows the general schema of a workflow selection.

An example taken from [17] is about trip planning in the context of smart cities. A trip-planning application allows users to automatically design a trip to visit places of interest (PoIs) in the city using the IoT infrastructure. In this example the compound task (trip-planning) uses different primitive tasks or sub-services for booking local transportation based on time preference, weather conditions, person’s current location, nearest available cab, route-planning service, visiting hours of PoIs around the city and automatic payment service. For each of the sub-services evoked above, we can find multiple concretes services providers using IoT devices. The difference between these similar concrete services lies in their quality of services.

The availability of functionally similar services increases the complexity of selecting the best concrete services. So, our aim in this work is to propose an efficient method that can perform the selection of the best concrete services in terms of quality of service in order to satisfy the requirements of the end user.

Besides, the service selection and composition in the IoT architecture is depicted in Figure 2. The service composition of the IoT architecture is divided into five layers, the relationship between the five layers is that each layer receives as input the output of the previous layer, enriches it and feeds the following layer. This relationship is similar to that found between ISO layers in computer networks. The roles of each layer are given as follows:

• The perception layer which is composed of sensors and smart devices which are responsible of providing the service as data or processing resource.
• The service provided with perception layer is send to network layer which is responsible of transferring the service to the cloud layer.
• The cloud layer presents the database of all services and provides the different services by public or private cloud.
• The service selection and composition layer is responsible of selecting the best sub services and composing this later to achieve the global task.
• The application layer presents the interface where the end users can use the service or requests the service.

1.png

Figure 1. QoS aware service selection and composition [18]

2.png

Figure 2. QoS aware service composition in IOT

3.1 QoS model for service selection and composition

We identify seven QoS characteristics as the quality evaluation criteria of service according to domain application of IoT, based on various QoS attributes for services published by W3C working group.

(1) Execution time. The average time between when the user sends the request and when the server responds is the execution time of a service.

(2) Reliability. The percentage of service requests that are executed successfully is the reliability of a service. The ratio of successful executions to total number of services called is used to calculate it.

(3) Execution cost. is the price to pay (in terms of money) in order to exploit the service.

(4) Availability. During a certain time interval, the percentage of time that a service is available.

(5) Scalability. The IoT environment’s ability to be modified and changed in many conditions.

(6) Reputation. is a measure of its trustworthiness. It mainly depends on end user's experiences of using the services. A level of satisfaction for this QoS can be defined as “very high”, “high”, “normal”, “poor” or “very poor”. We can just use a ranking technique based on end user's experiences of using the services for calculating the reputation quality.

(7) Response Time. It’s the amount of time between when a user asks a service and when they get an answer.

The most extensively used service composition workflows are: (a) sequential, (b) Loop, (c) Parallel and (d) Switch as shown in Figure 3. The mathematical expressions used to calculate the value of each QoS for the different workflow are given in Table 1.

3.png

Figure 3. Workflows used in service composition

3.2 Mathematical model for QSC

In a service selection and compositions model, tasks are represented as T=t₁, t₂, t₃, ..., t_n and the workflow must be selected (sequential, Loop, Parallel and Switch).

Suppose that we have m atomic services given as S=s₁, s₂, s₃, ..., s_m with the same functionality but varying only in QoS. For each atomic service s_i, the QoS is expressed as t_i time, a_i availability, r_i reliability, and c_i cost. As a result, there are a lot of possibilities to allocate an atomic service from m services for n tasks.

The service composition approach should also satisfy the service level agreement (SLA), which is the level of service required from the service provider. SLA is a contract between a service provider and a consumer that ensures a minimum level of service is maintained. It guarantees levels of reliability, availability and responsiveness to systems and applications.

In other words, the service selection and composition algorithm’s input is:

• The task list T=t₁, t₂, t₃, ..., t_n;

• Their workflow;

• The set of atomic services S=s₁, s₂, s₃, ..., s_m for each task;

• The QoS for each atomic service s_i, i=1, ..., m as {t_i, a_i, r_i, c_i};

• SLA vector SL=(SLt, SLa, SLr, SLc) for QoS attribute requested by the user.

The results are the chosen atomic service for each job from a set of m atomic services that optimize QoS while meeting the SLA requirements.

We evaluate the fitness value of the service composition solution based on the QoS values of its selected atomic service for each task, as well as composite models (i.e. sequential, Loop, Parallel, and Switch) that specify the interconnection architecture between these atomic services (see Eq. (3) below).

Cost and benefit criteria can be used to categorize the characteristics of QoS. A larger value of a cost criterion corresponds to a lower quality (e.g. execution price or execution time). In contrast, a higher value of a benefit criterion corresponds to a higher quality (e.g., reliability and availability). The following relationship can be used to normalize QoS attributes:

• normalization of aggregate cost attributes (i.e. q_i $\in$ cost criteria):

$Q\left(q_{i}\right)=\left\{\begin{array}{l}\frac{\operatorname{agg}\left(\max \left(q_{i}\right)\right)-\operatorname{agg}\left(q_{i}\right)}{\operatorname{agg}\left(\max \left(q_{i}\right)\right)-\operatorname{agg}\left(\min \left(q_{i}\right)\right)} \\ 1, i f a g g\left(\max \left(q_{i}\right)\right)=\operatorname{agg}\left(\min \left(q_{i}\right)\right)\end{array}\right.$             (1)

• normalization of aggregate benefit attributes (i.e. q_i $\in$ benefit criteria):

$Q\left(q_{i}\right)=\left\{\begin{array}{l}\frac{\operatorname{agg}\left(q_{i}\right)-\operatorname{agg}\left(\min \left(q_{i}\right)\right)-}{\operatorname{agg}\left(\max \left(q_{i}\right)\right)-\operatorname{agg}\left(\min \left(q_{i}\right)\right)} \\ 1, i f a g g\left(\max \left(q_{i}\right)\right)=\operatorname{agg}\left(\min \left(q_{i}\right)\right)\end{array}\right.$                    (2)

In Eqns. (1) and (2):

• max(q_i) and min(q_i) denote the maximum and minimum possible values of the i^th QoS criterion for the selected service compositions, respectively,

• agg(max(q_t)) denotes the aggregated value of the i^th QoS criterion of selected service compositions.

The set of possible aggregation operations is: agg={sum, prod, avg, max and min}. Each QoS attribute can be applied based on the composite model and the relevant QoS parameter’s characteristic. For the sequential composite model, the sum operation (i.e. sum) is the aggregation operation of the QoS response time. We choose the sequential pattern in this study because the other three patterns, as described, can be easily transformed into the sequential pattern. The different aggregation operations for composition models are shown in Table 1 (sequential, Loop, Parallel and Switch).

If the user’s preference for the $\mathrm{i}^{\text {th }}$ QoS attribute is $\mathrm{w}_{\mathrm{i}} \in[0,1]$ such that $\sum_{\mathrm{i}=1}^{\mathrm{r}} \mathrm{w}_{\mathrm{i}}=1$, then the fitness value can be constrained by the following formula for r attributes of the composite service that satisfied users:

Fitness $=\sum_{i=1}^{r} Q\left(q_{i}\right) * w_{i}$       (3)

Table 1 show the different aggregation functions for QoS properties based on the different workflows used in this work.

In Table 1, t, c, a and r are the QoS attributes, n refers to the task number, j corresponds to j^th candidate service, and i corresponds to the i^th subtask. P_i stands for the conditional probability of the i^th task, and L is the iteration number.

Table 1. Aggregation functions for QoS properties based on the different workflows

The following materials, which include both hardware and software components, have been used to implement and analyze the Hybrid Discrete Dragonfly Algorithm and Particle Swarm Algorithm:

• Hardware: Windows OS with 2.9 GHz Intel core i3 processor and 8 GB of RAM.

• Software: Matlab version 18a.

To verify the effectiveness, efficiency, and superiority of DDAPSO algorithm, its performance is compared with five recent optimization algorithms using large-scale intances of service selection and composition problem. These optimization algorithms are: Multi-verse optimization algorithm (MVO) [19, 20], Genetic algorithm (GA) [21, 22], Discrete version of Dragonfly Algorithm (DDA) [4], Particle Swarm Optimization Algorithm (PSO) [5] and Artificial Bee Colony Optimization Algorithm (ABC) [23]. All algorithms’ parameter settings are shown in Table 3.

The above-mentioned references of the comparisons algorithms are used to choose these settings. Hence, these sources should be consulted for more information on the meaning and function of the parameters.

The population size for all algorithms was unified, the execution of all algorithms was performed 30 times, and each execution included 1000 iterations. Each repetition’s average fitness value, performance stability, and execution time has been correctly recorded.

Table 3. Parameters settings for different Algorithms

	Parameter Values
Algorithms	Pop size
MVO	30	Wep max	1
		Wep min	0.3
GA	30	Pc	0.6
		PM	0.01
DDA	30
PSO	30	Wmax	0.9
		Wmin	0.2
		C1	2
		C2	2
ABC	30	L	1
		NG	3
DDAPSO	30	Wmax	0.9
		Wmin	0.2
		C1	2
		C2	2

The experimental studies have been conducted using real datasets (Ver. 2.0) [24], which include 25 service selection and composition challenges. The datasets [24] contain about 2500 real tasks, each with nine QoS criteria. Cost, response time, availability, and dependability are the most effective QoS attributes that optimization algorithms use to solve the service selection and composition problem. With a total of 25 datasets, different scenarios were built with a number of tasks equal to 20, 40, 60, 80, and 100, and each task is composed of a number of concrete services equal to 200, 400, 600, 800, and 1000 as in Ref. [20].

Figures 7-10 represent the results of all algorithms in terms of the average solution where the scenarios have a workflow comprising 20, 40, 60, 80 and 100 abstract tasks and, each abstract task, comprising 200, 400, 600, 800, and 1000 concrete services. The average execution time is shown in Figure 9 for all algorithms.

We can observe from Figures 7 and 8 that for the average of the QoS fitness value, the proposed algorithm DDAPSO outperforms all the other algorithms for all scenarios. From Figure 8, where the number of concrete services is equal to 1000, the average of QoS fitness value obtained by DDAPSO is 5,27E-01, whereas that obtained by MVO, GA, DDA, PSO and ABC are 4,66E-01, 4,91E-01, 4,92E-01, 4,38E-01, 4,53E-01, respectively.

7.png

Figure 7. Comparison of results (scenario 1: the number of tasks n changes from 10 to 100, and the number of concrete services m varies from 10 to 100)

8.png

Figure 8. Comparison of results (scenario 2: the number of task n=20 and the number of concrete services m changes from 200 to 1000)

9.png

Figure 9. The quality of the optimal composite service obtained by the compared algorithms

10.png

Figure 10. Comparison of computation times (scenario 3: the number of tasks n=20 and the number of concrete services m varies from 200 to 1000)

The convergence curves of the different algorithms vs the number of function evaluations for QoS are shown in Figure 9 with the number of tasks equal to 100 and the number of micro services equal to 1000. The number of iterations is assumed to be the same as the number of tasks. The number of function evaluations in each iteration is equal to the number of individuals in a population, which is 30. Our experiments show that all algorithms suffer from stagnation, except the proposed algorithm DDPASO which succeeds to escape from stagnation.

Figure 10 shows the Computation time comparison in seconds of DDAPSO compared to the other five algorithms for a number of tasks n=20 and a number of concrete services m which varies from 200 to 1000 (the number of iterations is fixed to 100). As seen from Figure 5, the execution time of DDAPSO with respect to 1000 concrete services was 2,1 s, whereas the execution time of MVO, GA, DDA, PSO and ABC were 0,7558794, 0,594872, 3,0191281, 1,7630176 and 3,5550047 s, respectively. From Figure 10, we can observe that DDAPSO is in the DDAPSO is in the middle and presents average time of computation in comparison with the other algorithms.

Table 4 shows that DDAPSO obtains the best results for 25 out of 25 datasets, i.e. DDAPSO performed best on all datasets while MVO, GA, DDA, PSO, and ABC failed to provide any best solution.