Opportunistic service composition in dynamic ad hoc environments

Abstract

Mobile and embedded devices capture, process, and exchange sensory data about their operating environment, making them suitable service providers for ubiquitous computing. In particular, composing services that are hosted on different devices creates new value-added functionality and supports context-aware applications e.g., for smart public spaces. This thesis explores service composition in dynamic ad hoc networks which represent a very dynamic form of ubiquitous computing environments. Service providers may join, roam, or leave the network and offer services only as appropriate to their own objectives and resource capacity. Mobility and participation autonomy, however, change the network and service topology frequently. They impose a high failure probability on composites because network links are likely to break and service offers may become unavailable. Although network routes are repairable and service allocations can be re-assigned, failure recovery comes at the cost of delay and additional communication. Preventive measures such as keeping backups for service providers and network routes, on the other hand, incur additional monitoring and maintenance overhead regardless of whether failure occurs or not. Service provision through service composites, therefore, faces the challenging question of how to efficiently adapt to a continuously evolving operating environment. Research in service-oriented computing has led to dynamic strategies for service discovery, allocation, and invocation to accommodate for changes at runtime. Common to these strategies is their reliance on a pre-established service overlay structure or the allocation of all required services at once. While in advance service registry facilitates the discovery process, its maintenance overhead increases as more dynamic provider information needs to be captured and made available. Allocating services all at once allows for verifying whether the composite will execute to completion. However, by the time a particular service is invoked, the dynamics of the system may have rendered early allocation decisions invalid and cause failure. Techniques that finalise the allocation decision only prior to invoking the service are more flexible, but involve monitoring overhead and allocate more resources than the composite actually needs. This thesis presents opportunistic service composition as an alternative to support the flexible implementation of complex service requests in highly dynamic environments. The novel composition model bundles and defers all interactions with a service provider until the required sub-service needs to be invoked. It interleaves service discovery and composite allocation with provider invocation to minimise the window for change to negatively impact the composite. The proposed composition protocol supports service sequences and parallel service flows. The approach lets service providers control their involvement to support participation autonomy, defines an explicit resource blocking mechanism to address provider resource-constraints, and devises a cross-layer communication solution to reduce the communication load on narrow wireless bandwidth. Evaluation of the protocol has been achieved using model-based verification and simulation. Verification through automated model checking confirms that a formal specification of the designed composition protocol does not deadlock, terminates in a valid end state, and adequately covers all required sub-services in both sequential and parallel service composites. The verified model has also been implemented and integrated with a simulator for mobile ad hoc networks. The simulation-based evaluation assesses the performance of opportunistic service composition in comparison to more conventional baselines. It quantifies how the interplay of service discovery, allocation, and invocation affects the failure probability of composites in mobile ad hoc settings. The results of this study demonstrate that the opportunistic approach generally achieves its design objective to decrease failure in a communication-aware manner and at the same time reveal the limits of these benefits with regard to request complexity, network density, and service demand.