Exploiting mobility prediction for dependable service composition in wireless mobile ad hoc networks

Service-Oriented Architecture (SOA) is emerging as the next inevitable technology for application developments. One fundamental issue of SOA is service composition, i.e., to seamlessly compose distributed services into more complex applications. In the mobile environment, a service composition may face disruptions caused by the movement of both users and service providers. Thus, a dependable service composition is desired to handle the mobility in the environment. In this paper, we propose to achieve dependable service composition by taking the mobility prediction of the service providers into consideration. We exploit the fact that the service providers can predict their stay time in the current environment. However, some uncertainty may exist in the prediction such that a service provider may move out of the current environment earlier than the prediction. We use two models to characterize the uncertainty, a probability-free model and a probabilistic model. Our objective is to design dependable service composition under these two models such that the service composition solution can have the maximum tolerance to the uncertainty of the mobility prediction. We focus on the case of sequential service composition, prove the NP-hardness of the problem, then present heuristic algorithms, derive the upper and lower bounds of the problem. Simulation results have showcased the effectiveness of the heuristic algorithms. © 2008 IEEE.