Web services constitute a distributed computing infrastructure made up of many different interacting application modules trying to communicate over private or public networks to virtually form a single logical system (Papazoglou, 2008). As reusable components, Web services are meant to be combined to meet business needs for enterprise applications (Rosen, Lublinsky et al., 2008). With the growing number of Web services, a significant number of functionally similar services are provided, making service composition more challenging, which demands efficient and personalized composition optimization techniques for service requesters.
A number of optimization methods for composing services have been developed, aiming at achieving a composite service with the best user desired Quality of Service (QoS), which could be divided into two categories. On one hand, in some works (Zeng, Benatallah et al., 2004; Al-Masri, Mahmoud et al., 2008; Yu, Zhang et al., 2007), Web services are selected depending on a predefined objective function. In this case, a weighting mechanism is leveraged where users express preferences over different quality parameters as numeric weights. The composite service gaining the highest value is selected and returned to the user. As it's a rather challenging task for users to transform their preferences into numeric weights, some researchers have tried solving the problem using the dominance relationship between services in Benouaret, Benslimane et al. (2011), Yu and Bouguettaya (2011) and Alrifai, Skoutas et al. (2010) (also called skyline (Alrifai, Skoutas et al., 2010), full skyline (Lin, Yuan et al., 2007) or free skyline (Chan, Jagadish et al., 2007)). With the dominance relationship between services, for a task, only skyline services are selected for further composition, reducing the number of candidate services.
Given a set of d-dimensional points, a point p is said to dominate another point q if it is better than or equal to q in all dimensions and better than q in at least one, denoted as . The skyline points are the subset of points that are not dominated by other points (Chan, Jagadish et al., 2007). In a scenario of composing services with skyline technique, given a predefined task schema, skyline services are selected for each task and composed into a composite service. Here is an example of composing services using skyline in Figure 1:
Figure 1. An example of skyline-based service composition
Example 1: Consider the example shown in Figure 1. Here, t1, t2 and t3 denote three tasks in a task schema. There are three candidate services for each task and the following tuples represent their QoS values which comprise three dimensions respectively. The tuples in red rectangles are skyline services.
In this example, through the skyline technique (e.g., , ), we can reduce the number of candidate services. Nevertheless, with the increasing number of Web services and the “curse of dimensionality” (Lin, Yuan et al., 2007), full skyline is not practically useful (Alrifai, Skoutas et al., 2010; Lin, Yuan et al., 2007). Moreover, users may have various preferences which may also constantly change over time. In view of these challenges, an optimization method for top-k composite services is proposed in this paper, combined with preference-aware service dominance, a multi-index based skyline computation algorithm and a dominant number-aware service ranking for global optimization.