QoS-aware service composition is aimed to maximize the global QoS of a composite service when selecting candidate services.In a context sensitive service execution environment in pervasive computing,the context information for service composition is not static:device,policy,and user constraints,and QoS requirements may change,new services may be deployed,old ones withdrawn,or existing ones change their QoS parameters.This results in the current service composition plan failing or its QoS degrading from the optimum.In this paper,a runtime self-optimizing service composition framework is proposed.An implementation of a prototype for this framework is presented,addressing the issues of reducing extra delay while increasing global QoS in service composition in a dynamic context environment.Three service re-plan algorithms are compared that can be used in dynamic context environment,i.e.,minimal-conflict hill-climbing repair genetic algorithm(MCHC-repair GA),an improved penalty-based GA,and our multi-population conflicts sorted repair genetic algorithm(MP-CS-repair GA),as well as three kinds of service composition mechanisms-with backup,without backup,and our context-aware service re-selection mechanisms.The results show that our MP-CS-repair GA and context-aware service re-selection method can reduce more extra delay while acquiring a higher global QoS for the composite service in a context sensitive environment.This context-aware service re-selection mechanism also shows some adaptability to different context change frequencies and user requirements for reducing computation cost in the self-optimizing process. QoS-aware service composition is aimed to maximize the global QoS of a composite service when selecting candidate services. In a context sensitive service execution environment in pervasive computing, the context information for service composition is not static: device, policy, and user constraints, and QoS requirements may change, new services may be deployed, old ones withdrawn, or existing ones change their QoS parameters. This results in the current service composition plan failing or its QoS degrading from the optimum. this paper, a runtime self-optimizing service composition framework is proposed. An implementation of a prototype for this framework is presented, addressing the issues of reducing extra delay while increasing global QoS in service composition in a dynamic context environment. Service re-plan algorithms are compared that can be used in dynamic context environment, ie, minimal-conflict hill-climbing repair genetic algorithm (MCHC-repair GA), an improved penalty-based GA, and our multi-population conflicts sorted repair genetic algorithm (MP-CS-repair GA), as well as three kinds of service composition mechanisms-with backup, without backup, and our context-aware service re-selection mechanisms. The results show that our MP-CS-repair GA and context-aware service re-selection method can reduce more extra delay while acquiring a higher global QoS for the composite service in a context sensitive environment. This context-aware service re-selection mechanism also shows some adaptability to different context change frequencies and user requirements for reducing computation cost in the self-optimizing process.