  Service composition is a widely used method in ubiquitous computing that
enables accomplishing complex tasks required by users based on elementary
(hardware and software) services available in ubiquitous environments. To
ensure that users experience the best Quality of Service (QoS) with respect to
their quality needs, service composition has to be QoS-aware. Establishing
QoS-aware service compositions entails efficient service selection taking into
account the QoS requirements of users. A challenging issue towards this purpose
is to consider service selection under global QoS requirements (i.e.,
requirements imposed by the user on the whole task), which is of high
computational cost. This challenge is even more relevant when we consider the
dynamics, limited computational resources and timeliness constraints of
ubiquitous environments. To cope with the above challenge, we present QASSA, an
efficient service selection algorithm that provides the appropriate ground for
QoS-aware service composition in ubiquitous environments. QASSA formulates
service selection under global QoS requirements as a set-based optimisation
problem, and solves this problem by combining local and global selection
techniques. In particular, it introduces a novel way of using clustering
techniques to enable fine-grained management of trade-offs between QoS
objectives. QASSA further considers: (i) dependencies between services, (ii)
adaptation at run-time, and (iii) both centralised and distributed design
fashions. Results of experimental studies performed using real QoS data are
presented to illustrate the timeliness and optimality of QASSA.
