Opportunistic service composition in dynamic ad hoc environments Christin Groba A thesis submitted to the University of Dublin, Trinity College in fulfillment of the requirements for the degree of Doctor of Philosophy (Computer Science) March 2013 Declaration I declare that this thesis has not been submitted as an exercise for a degree at this or any other university and it is entirely my own work. Christin Groba Dated: March 26, 2013 Permission to Lend and/or Copy I agree to deposit this thesis in the University’s open access institutional repository or allow the library to do so on my behalf, subject to Irish Copyright Legislation and Trin- ity College Library conditions of use and acknowledgement. Christin Groba Dated: March 26, 2013 Acknowledgements This thesis would not have been possible without the support and encouragement of many people for which they deserve thanks and recognition. First and foremost, I would like to thank my supervisor, Prof. Siobhán Clarke, for her guidance and scientific advice, patience and kind words, as well as for teaching me the beauty of precise and rigorous research. Thanks also to Lero, the Irish Software Engineering Research Centre, for giving me the opportunity to conduct research in Ireland among the first students of the Lero Graduate School. Many thanks goes to Serena Fritsch and Paula Hannon for their vivid discussions about service composition and to Stephan Weber for his insightful views on mobile ad hoc networks. I would also like to thank the members of my research group, DSG, for their support. In particular, thanks to Guoxian Yang, Luca Longo, and Mithileash Mohan for giving me their perspective on my research and for reminding me that there is a life besides the PhD. Many thanks also to Killian Levacher and Melanie Sherlock who are a constant source of inspiration always challenging me to think outside the box. Thank you to my parents who encouraged me to explore the world while grounding me in traditions and down-to-earth principles such that I always have a place to which I can return. Thank you to my sister Claudia who led by example and showed me that PhD can be done. Finally, Patrick, thank you for your constant support, love, and patience, and for being there all along. Christin Groba University of Dublin, Trinity College March 2013 vii Abstract Mobile and embedded devices capture, process, and exchange sensory data about their operating environment, making them suitable service providers for ubiquitous comput- ing. 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 rep- resent 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 topol- ogy 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. Ser- vice 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 ix 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 communi- cation solution to reduce the communication load on narrow wireless bandwidth. Evaluation of the protocol has been achieved using model-based verification and sim- ulation. Verification through automated model checking confirms that a formal speci- fication 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. x Publications Related to this Ph.D. 1. Groba, Christin and Clarke, Siobhán (2012). Towards in-network aggregation for people-centric sensing, Ninth International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous). 2. Groba, Christin and Clarke, Siobhán (2012). Synchronising service compositions in dynamic ad hoc environments, First International Conference on Mobile Services (MS), IEEE, pp. 56-63. 3. Groba, Christin and Clarke, Siobhán (2012). Towards Opportunistic Service Com- position in Dynamic Ad Hoc Environments, PhD Symposium at Ninth Inter- national Conference on Service Oriented Computing (ICSOC PhD Symposium), Springer, pp. 189–194. 4. Groba, Christin and Clarke, Siobhán (2011). Opportunistic composition of se- quentially connected services in mobile computing environments, Eighteenth In- ternational Conference on Web Services (ICWS), IEEE, pp. 17-24. (Best student paper award) 5. Groba, Christin and Clarke, Siobhán (2010). Web services on embedded systems - A performance study, Workshop at Eighth International Conference on Pervasive Computing (PERCOM Workshops), IEEE, pp. 726-731. 6. White, Jules and Clarke, Siobhán and Groba, Christin and Dougherty, Brian and Thompson, Chris and Schmidt, Douglas C. (2010). R&D challenges and solutions for mobile cyber-physical applications and supporting Internet services, Journal of Internet Services and Applications 1(1), pp. 45-56. (invited article) xi Contents Acknowledgements vii Abstract ix List of Tables xvii List of Figures xix Chapter 1 Introduction 1 1.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Existing solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Thesis approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Thesis contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Thesis scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Thesis structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 2 State of the art 15 2.1 Service discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Proactive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2 Demand-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Service allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 Schedule-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 xiii 2.2.3 Group-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.4 Goal-oriented . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Service invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.1 Broker-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2 Static fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.3 Dynamic activation . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Service flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 Concurrent data access . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.2 Conditional execution paths . . . . . . . . . . . . . . . . . . . . . . 29 2.4.3 Common meeting point . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.1 Tuplespaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.2 Content-based routing . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.3 Cross-layer design . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 3 Design 41 3.1 Design objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.1 Service composite . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.2 Service provision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.4 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3 Design decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.1 Service discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.2 Service allocation and invocation . . . . . . . . . . . . . . . . . . . 51 3.3.3 Service flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 xiv 3.3.4 Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4 Proposed solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.4.1 Service sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.2 Service flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.4.3 Cross-layer communication . . . . . . . . . . . . . . . . . . . . . . 76 3.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Chapter 4 Design verification 79 4.1 PROMELA and SPIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Service sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.1 Protocol abstractions . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.2 Modelling service sequences . . . . . . . . . . . . . . . . . . . . . . 81 4.2.3 Modelling communication . . . . . . . . . . . . . . . . . . . . . . . 82 4.2.4 Modelling participants . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.2.5 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 Service flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.1 Protocol abstractions . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3.2 Modelling service flows . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.3.3 Modelling communication . . . . . . . . . . . . . . . . . . . . . . . 89 4.3.4 Modelling participants . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.3.5 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.4 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Chapter 5 Implementation 97 5.1 Mobile composite participants . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.2 Composition protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.3 Composition messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.4 Directed broadcasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.5 Cross-layer approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.6 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 xv Chapter 6 Evaluation 107 6.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.1.1 General settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.1.2 Evaluation scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.1.3 Failure types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.1.4 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.1.5 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.1.6 Threats to validity . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6.2 Results and analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.2.1 Impact of service sequence length . . . . . . . . . . . . . . . . . . . 119 6.2.2 Impact of service flow structure . . . . . . . . . . . . . . . . . . . . 122 6.2.3 Impact of environment using a service sequence . . . . . . . . . . . 125 6.2.4 Impact of environment using a service flow . . . . . . . . . . . . . 131 6.3 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Chapter 7 Conclusion 139 7.1 Thesis summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 7.3 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.4 Final remark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Appendix A Verification with SPIN 147 Bibliography 151 xvi List of Tables 6.1 General simulator and composition settings . . . . . . . . . . . . . . . . . 108 6.2 Scenario-specific settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.3 Comparison of baselines and proposed protocol . . . . . . . . . . . . . . . 115 6.4 Result summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 xvii List of Figures 1.1 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Structure of the state of the art review . . . . . . . . . . . . . . . . . . . . 16 2.2 Summary of some composition solutions . . . . . . . . . . . . . . . . . . . 39 3.1 Design overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 Composite graph for audio classification . . . . . . . . . . . . . . . . . . . 45 3.3 Valid and invalid composites . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Dynamic service provision . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.5 Service allocation and invocation alternatives . . . . . . . . . . . . . . . . 52 3.6 Design decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.7 Protocol for service sequences . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.8 Scenario 1 Basic protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.9 Scenario 2 Proactive service announcement . . . . . . . . . . . . . . . . . 62 3.10 Scenario 3 Lost release . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.11 Protocol for service flows . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.12 Scenario 4 Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.13 Example complex service flow . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.14 Scenario 5 Service routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.15 Scenario 6 Reducing a sequence . . . . . . . . . . . . . . . . . . . . . . . . 74 3.16 Scenario 7 Reducing after a split . . . . . . . . . . . . . . . . . . . . . . . 75 3.17 Scenario 8 Reducing a service route . . . . . . . . . . . . . . . . . . . . . . 76 xix 4.1 Abstractions for the sequential PROMELA model . . . . . . . . . . . . . 82 4.2 Abstractions for the parallel PROMELA model . . . . . . . . . . . . . . . 88 4.3 Model of service flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.1 Implementation overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Mobile composite participants . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.3 Composition messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.4 Cross-layer approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.1 Service flow structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2 Pilot study for CiAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6.3 Failure ratio in scenario 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.4 Communication effort in scenario 1 . . . . . . . . . . . . . . . . . . . . . . 120 6.5 Response time in scenario 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.6 Failure ratio in scenario 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.7 Communication effort in scenario 2 . . . . . . . . . . . . . . . . . . . . . . 124 6.8 Response time in scenario 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.9 Failure ratio in scenario 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.10 Communication effort in scenario 3 . . . . . . . . . . . . . . . . . . . . . . 129 6.11 Response time in scenario 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.12 Failure ratio in scenario 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.13 Communication effort in scenario 4 . . . . . . . . . . . . . . . . . . . . . . 134 6.14 Response time in scenario 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 135 A.1 SPIN output for failed verification . . . . . . . . . . . . . . . . . . . . . . 148 A.2 SPIN output for sequential PROMELA model . . . . . . . . . . . . . . . . 149 A.3 SPIN output for parallel PROMELA model . . . . . . . . . . . . . . . . . 150 xx Chapter 1 Introduction Mobile and embedded devices have evolved from special purpose equipment to smart entities that can sense their environment, process sensory data, and communicate with nearby peers or servers on the Internet. Pervasive computing builds upon these capa- bilities to provide context-aware applications that, receptive to the user’s environment, point to relevant information or trigger necessary actions. In addition, smart device technology appears to lower the boundary for people to track and share their experi- ences. Already, millions of users capture pictures, news, comments and even physical achievements with their mobile phones and post them on social networking platforms. Novel applications tap this growing potential. People-centric sensing, for example, uses the sensing capabilities of mobile phones and the movement of their carriers to collect sensory data and to improve the micro- and macroscopic view of a city (Lane et al., 2010). Aggregating and classifying data from a variety of sources produces higher level context, which allows for more robust conclusions and a deeper insight into the situation of an individual, a group, or an entire community. The opportunities that arise from mobile sensing and the positive attitude of people towards sharing are not limited to the World Wide Web, but may also take effect in a user’s immediate surroundings as the following scenario shows: Adam uses the recording and processing capabilities of his smartphone to track his daily exposure to noise. Later, he correlates that with other health measures to better understand his stress levels. The phone samples, filters, 1 Chapter 1. Introduction classifies, and geo-tags audio data. However, being in Adam’s pocket, the phone is unable to record high-quality data and would benefit from cali- bration with another device. In our scenario, as a field engineer, Adam is about to meet a new customer. In this unfamiliar environment, his phone’s classifier software is not properly trained to categorise the noise. To make matters worse, the phone’s GPS unit malfunctions and fails to determine Adam’s position. As a result, the phone lacks the fundamental requirements for noise tracking and denies this service. However, Adam has heard of an innovative way of solving this issue and configured his phone to collaborate with nearby mobile phones that share their capabilities (Miluzzo et al., 2010). Adam’s phone forms an ad hoc network with Joe’s and Mary’s phones, who are walking next to Adam, and issues the noise tracking task as a request. By incorporating these other devices Adam’s phone increases the chances of covering all hardware and software requirements to complete the task. The collective effort of multiple mobile devices is required if no single device has enough resources to handle a complex task alone. In particular, a structured approach needs to be put in place to allocate and execute subtasks. Service-oriented computing provides for such an structured approach. It is based on the notion of a service that encapsulates software-based behaviour or an application component to make it discoverable, accessi- ble, and reusable over the communication network (Papazoglou and Heuvel, 2007). The composition of services creates new value-added functionality and involves a mechanism to specify, instantiate, and resolve complex service requests. Typically, the defined order and functionality of required sub-services guides the discovery, allocation, and invocation of suitable service providers. These service-oriented principles map to requirements in pervasive computing environments. Device capabilities like software components, locally stored data, and hardware resources can be modelled as services while service compos- ites represent complex sensing tasks that span across multiple data sources (Kalasapur et al., 2007; Chakraborty et al., 2004; Brønsted et al., 2010). In the scenario (cp. Figure 1.1), Mary’s phone encapsulates its microphone as an audio sampling service and the GPS unit as a geo-tagging service. Joe’s phone provides access to different functions of 2 Service composition Discover, allocate, invoke Geo-tagging service Feature classifier service Audio filter service Audio sampling service Adam Noise tracking request Joe Service offer Mary Service offer Fig. 1.1: Scenario Adam wants to track his exposure to noise but does not have the required capabilities available on his mobile phone. Joe and Mary offer their phones’ hardware and soft- ware capabilities as services. Service composition discovers, allocates, and invokes these services to satisfy Adam’s complex request. its audio software via an audio filtering service and a feature classification service. In addition, the phone offers an audio sampling service. Adam’s noise tracking task is a service composite that first requires two audio sampling services, then an audio filter- ing service, thereafter a feature classification service, and finally a geo-tagging service. Service composition is the mechanism that discovers Joe and Mary’s phone services, allocates them to Adam’s composite request, and invokes them to provide Adam with the result of that new value-added service. The focus on service composition in dynamic ad hoc networks distinguishes this the- sis from mashups based on the Web of Things (Guinard, 2010; Pintus et al., 2010) and service composition in sensor and context cloudlets (Loke, 2012), which rely on dedicated infrastructure to manage the access to smart entities. Dynamic ad hoc networks evolve spontaneously and on-demand. The absence of dedicated infrastructure requires poten- tial composite participants to organise network and service related operations among themselves. The physical size of mobile devices limits their locally available resources and communication range. Participants thus exchange messages either directly if they are in each other’s transmission range or indirectly via intermediaries that relay mes- 3 Chapter 1. Introduction 1. Transient network 2. Lack of composition infrastructure Establish network on demand Coordination and synchronisation Resend, re-connect, re-allocate 6. Failure recovery Backup providers, route maintenance 6. Failure prevention 3. Wireless communication 4. Mobility 5. Participation autonomy Packet loss Path loss Invocation rejection Interference and obstruction Instable routes and routing info Limited resources and local objectives Fig. 1.2: Challenges Service compositions in transient networks lack dedicated composition infrastructure and are likely to fail due to the unreliability of wireless communication and the instability that mobility and participation autonomy create. Failure prevention and recovery rely on further communication and expose the composition again to the dynamics of the environment. sages. Free of any obligations towards a unifying authority, service providers join, roam, and leave the network at any time. They engage in compositions spontaneously if this suits their residual load and objectives. 1.1 Challenges The dynamic nature of mobile ad hoc networks presents a significant challenge for the composition of complex service requests (Brønsted et al., 2010; Kalasapur et al., 2007). In particular, service composition faces (cp. Figure 1.2): • Challenge 1: Transient networks An ad hoc network may evolve only because a service request was raised and dis- solves after the request is completed. Pre-established knowledge about the service and network topology does not exist and a network is established by interaction (Chlamtac et al., 2003). This means, service providers are initially unaware of each other’s existence and find out about their neighbourhood only if co-located providers announce themselves or respond to a request. • Challenge 2: Lack of composition infrastructure Free from any managed infrastructure, a dynamic ad hoc network lacks a single 4 1.1. Challenges entity with global system view. In particular, there is no dedicated entity that acts as a proxy for service discovery, allocation, and invocation and composite participants must manage complex requests between themselves in a decentralised peer-to-peer manner (Gu and Nahrstedt, 2006). Decentralisation, however, implies additional coordination and synchronisation, especially if composite requests ex- tend beyond a sequential execution structure and contain parallel execution paths, so-called service flows1, that must be merged prior to returning the final result (Yildiz and Godart, 2007). • Challenge 3: Wireless communication Service composition, as well as building the service and network topology requires network and composite participants to communicate. In ad hoc networks, however, communication is wireless and inherently unreliable (Friedman et al., 2007). The exchange of messages via the radio medium is prone to interference and obstruction, which causes packet loss. • Challenge 4: Mobility Services are hosted on mobile devices. Network paths are likely to be lost when mobile service providers move because these frequent changes of the network topol- ogy are likely to break established routes and invalidate cached routing information (Chlamtac et al., 2003). • Challenge 5: Participation autonomy Service providers are not obliged to a higher authority. They may temporarily disable service provision and reject service invocation if this conflicts with local objectives or the availability of resources (Campbell et al., 2008). For example, although a provider has generally agreed to host a sensing service, it may only offer the service when in a certain location. • Challenge 6: Failure prevention versus recovery In complex service requests each constituent service is prone to packet loss, path loss, or service rejection and presents a potential source of failure for the entire 1In the following, the terms service flow and parallel service flow will be used interchangeably. 5 Chapter 1. Introduction composite. This makes it “very difficult to maintain a composed service for ex- tended periods of time” (Sen et al., 2004). Although routes can be repaired and services re-allocated (Jiang et al., 2009; Feng et al., 2007), failure recovery comes at the cost of further communication over error-prone network links and delays the final composition result. Preventive failure recovery assigns backup providers and keeps routes updated at all times to reduce the recovery delay (Gu and Nahrstedt, 2006; Prinz et al., 2008). These techniques are based on participants issuing heart beat messages to signal changes in the topology. For composition messages this periodic network traffic, however, presents a source for interference and communi- cation failure. Further, the resource-constraints of mobile service providers limit the number of composites they can handle simultaneously. If a provider is a backup for a service in one composite, it may not be available as a primary provider for an- other composite. Allocating one or more backup providers for each required service in addition to the primary provider may lead to temporary provider shortage. Considering the dynamics of mobile ad hoc environments and the complexity of service requests the question arises: How can composites efficiently adapt to their continuously evolving operating environments to reduce the likeliness of failure to occur? 1.2 Existing solutions In service-oriented computing, the need for more flexibility towards changes to the user requirements and operating environment has led to creating abstract composites during the design phase and finalising them by assigning service providers at runtime. This way, service providers can be dynamically selected or replaced based on their current availability and actual execution properties (Cardellini et al., 2009). Acquiring dynamic provider information, however, is a challenge. Many composition solutions (e.g., Park and Shin, 2008; Samimi and McKinley, 2008; Wang et al., 2004) assume a service overlay structure that monitors all providers and excludes those that are currently unavailable, incapable, and unwilling to serve a request. Establishing such a structure in advance and independent from a particular composite request eases service discovery but at the same time requires effort to build and maintain. A registry, 6 1.2. Existing solutions for example, that holds both static and dynamic provider information (Schuler et al., 2004), needs repeated updating to keep up with evolving system dynamics. Alternative strategies (Gu and Nahrstedt, 2006; Samimi and McKinley, 2008) reduce this overhead and register only static service descriptions. Once a particular service request is raised, the potential providers are contacted and examined for their current properties. Based on an already existing network, these techniques study their solution in isolation from networking and service discovery aspects. In highly dynamic environments this leads to increased overhead considering that a network emerges only because of a service request and dissolves after it has been satisfied. Decentralised composition management has been proposed for cross-organisational business processes (Martin et al., 2008; Fernández et al., 2010), peer-to-peer networks (Gu and Nahrstedt, 2006; Wang et al., 2004), hierarchical device networks (Kalasapur et al., 2007) as well as for mobile ad hoc networks (Sen et al., 2008). However, the lack of integration between the composition phases either increases the composite’s fail- ure probability or involves additional maintenance and monitoring overhead. Generally, composition solutions decouple service invocation from service discovery and allocation such that they do not invoke the first service until each required service has been assigned to a provider. In systems with moderate dynamics this ensures that a composition will not fail due to missing service providers. However, this benefit is limited if changes occur more frequently. Static allocations (Sen et al., 2008) are then nonetheless subject to failure because providers can change their availability after they have been assigned. Leaving the allocation flexible until the invocation of a service (Schuler et al., 2004; Prinz et al., 2008), is more sensitive to departing providers or the arrival of better perform- ing candidates, however, comes at additional maintenance and monitoring cost. The group of providers that is assigned to a service has to stay updated on the dynamics within the group and must observe the primary provider to compensate for its disconnec- tion. In addition, service providers may not have enough resources to engage in another composition simultaneously. Allocating multiple of these providers per required service over a longer period of time (i.e., until all the service’s predecessors have been invoked) decreases the overall availability of services. 7 Chapter 1. Introduction 1.3 Thesis approach A novel model for service composition, hereafter called opportunistic composition, is designed to reduce the failure probability of complex service requests in dynamic ad hoc environments. Based on valuable insights from existing solutions, it explores the possibility of re-organising the composition process to flexibly adapt to system dynamics. Assumptions For the environment in which service composite requests are issued, this thesis makes the following assumptions: 1. The operating environment of service composites is highly dynamic. Mobility and participation autonomy change operating conditions more quickly than it takes to fully allocate, verify, and execute a composite request. 2. The network does not rely on dedicated communication infrastructure. Service providers establish network links in an ad hoc manner and route a message to- wards its destination. In line with Chakraborty et al. (2005), this work views infrastructure-based architectures as a special case of infrastructure-less environ- ments. Stationary, resource-rich entities may relieve service providers from some of their duties but may not be accessible from all the devices at all times. Observation One of the key drivers for this research is the observation that the delay of the traditional composition process is a source for failure. The composition process contacts a service provider at least three times: first to locate and examine the provider, then to block its resources, finally to invoke service execution. With growing complexity of the composite in terms of path length, the delay between these interactions increases. For example, the invocation of a service provider must wait until all successor services have been allocated and all predecessor services have executed. Meanwhile, the provider may move on, disappear completely, or stop offering the service. Unaware of these changes, the composite believes the provider to be in the same place and state as before and fails to reach it again. Checking with potential service providers more frequently than the minimum three times may be a solution to become aware of changes but incurs more traffic and risks clogging the network that leads to communication failure. 8 1.4. Thesis contribution Hypothesis This thesis investigates how to reduce the delay between individual com- position phases in a communication efficient manner. It frames its hypothesis as follows: The longer the delay between composition phases, the more likely are changes in the operating environment to occur. The later the operating environment is explored to compose a complex service request, the less time there is for the system to change and to render composition decisions invalid. Basic idea The novel concept of opportunistic service composition bundles the discov- ery, allocation, and invocation for a required sub-service to decouple it from its position in the complex request. The model defers all interactions with service providers until they are indispensable for the composition to make progress. It searches and allocates a service provider when the corresponding sub-service is executed next. The approach is opportunistic because it starts executing the composite without having fully allocated all required services and thus does not know whether there is a provider for each service. Other approaches verify this up front but once they start, they have to deal with the same system dynamics in which a service provider present during verification may have moved or disappeared. It is important to notice that the objective of opportunistic ser- vice composition is to reduce failure. As it cannot prevent failure entirely, this approach is complementary to strategies that recover the composite after failure. 1.4 Thesis contribution This thesis investigates how complex tasks can be coordinated in dynamic ad hoc envi- ronments using service composition while accommodating for changes in the operating environment that otherwise would lead to failure. This research contributes to the body of knowledge by providing: Extensions to existing composition models Existing approaches to service com- position tend to decouple service invocation from service discovery and service allocation which introduces delays and increases the likelihood of composite failure in transient networks. This thesis describes a novel opportunistic composition approach to align the complexity of a service composite to its frequently changing operating environment. In- 9 Chapter 1. Introduction tegrating the composition phases and deferring allocation decisions to the latest possible moment, as proposed in this thesis, has not been previously investigated. Composing complex service requests in this manner allows for greater flexibility to adapt to available services and reduces the failure probability of composites. Extensions to support parallel service flows With the reorganisation of the com- position process, the proposed opportunistic approach requires additional means to sup- port composites with parallel execution paths. This thesis defines algorithms on how multiple composite participants agree on a common successor. Current solutions require continuous path updates while the proposed algorithms synchronise once at the end of a parallel path. Further, the thesis provides detailed information on how to reduce a com- posite during its execution to avoid resource allocation for redundant or obsolete parts. These techniques ensure a consistent way of managing service composites and support the specification and resource-efficient execution of conditional composite behaviour. Extensions to communication capabilities Currently, service composition is, as part of the top layer in the communication stack, isolated from the knowledge bases of lower layers which limits its awareness of the dynamic operating environment and risks sub-optimal composition choices. This thesis investigates how to utilize the broadcast nature of wireless radio for service composition and to enable composition actions that are aware of the surrounding network and service topology. The proposed cross-layer communication approach has not been previously examined for service composites and allows for communication-efficient service composition with less failure. 1.5 Thesis scope The proposed composition model enables mobile entities to fulfil complex tasks by col- laborating with peers in their vicinity. The model preserves participation autonomy as it considers only those service providers that actively commit to a request. However, the incentives for mobile service providers to share their capabilities are not studied. Different methods to encourage cooperation and the effectiveness of those can be found in (Li and Shen, 2012) and (Zhao et al., 2011). 10 1.6. Thesis structure Focusing on a novel way to organise service composition, this work is general in terms of how services and complex tasks are expressed. It does not assume a specific language (e.g., WSDL, BPEL, WS-CDL) to describe service offers and requests. Neither does it include particular concepts (e.g., ontologies) to classify services. The model applies syntactic matching to task descriptions that define the order and behaviour of required services but is well aware of more sophisticated approaches that allow for semantic matching (Nedos et al., 2009) and goal-oriented composition (El Falou et al., 2010). Locality of service provision is a key criterion for service allocation in mobile ad hoc networks because the more distant a service provider, the more expensive is communica- tion (Friedman et al., 2007). The design of the model supports locality needs by acting on demand and dynamically transferring the composition control. This way the vicin- ity of the current composition controller is naturally explored first. Provider allocation may consider further quality of service criteria if such provider information is available. Balancing multiple constraints, however, is not covered in this work, though has been studied, for example, by Zeng et al. (2004) and Cardellini et al. (2009). This work analyses the discovery, allocation, and invocation of composite services as well as the interfaces between those phases with the goal to reduce the high failure probability that mobile ad hoc environments entail. Failure recovery, in particular the cost of it, is considered for building an argument for opportunistic service composition. Recovery mechanisms themselves are not integrated in this work. However, as the pro- posed approach does not prevent failure, different recovery methods (e.g., Philips et al. 2010; Jiang et al. 2009; Feng et al. 2007) will need to be analysed to make the approach more reliable. 1.6 Thesis structure State of the art Chapter 2 analyses how state of the art composition solutions meet the challenges of highly dynamic pervasive computing environments. In particular, the study explores a) how dynamic provider information is discovered and kept up to date, b) how provider allocation is stabilised against frequent changes, c) how scarce provider resources are efficiently blocked, consumed, and released, d) how these concepts ex- 11 Chapter 1. Introduction tend to requests with parallel execution paths, and e) how messages among composite participants can be delivered efficiently. Design Chapter 3 returns to the challenges of service composition in highly dynamic environments outlined in Chapter 1 and describes the design objectives, system model, and design decisions of this thesis. Thereafter the chapter explains how the proposed protocol for opportunistic service composition addresses the design decisions in detail. Design verification Chapter 4 uses model checking to verify the correctness of the designed protocol with regard to the absence of deadlocks, the termination in a valid end state, and the correct number of allocated service providers. For this the chapter first introduces the modelling tools PROMELA and SPIN, then examines basic protocol features on basis of service sequences, and thereafter turns to the extensions that support composites with parallel execution paths. Implementation Chapter 5 describes the Java implementation of the designed and verified composition protocol. It explains how the integration with the network simulator Jist/SWANS enables mobility for composite participants. Then, the chapter highlights implementation details of the protocol and specifies the format of different composition messages. Details with regard to directed broadcasting and the cross-layered approach towards topology management complete the chapter. Evaluation Chapter 6 evaluates how well the novel composition approach achieves its objective of reducing composite failure. It first describes the experimental setup of the simulation-based study. The second part of the chapter presents and analyses the results showing that the proposed composition protocol is a suitable alternative to existing solutions for service composition in dynamic ad hoc environments. Conclusion Chapter 7 summarises the thesis and its achievements. It then discusses important findings with regard to the proposed composition protocol and highlights failure recovery and people-centric sensing as two potential areas for future work. A final remark provides a succinct wrap-up of this work. 12 1.7. Chapter summary 1.7 Chapter summary Mobile and embedded devices accompany people throughout the day and their processing and sensing capabilities support assisting us with information and actions that suit our current situation. Collaboration among such smart devices has the potential to achieve complex application requirements that a single device would fail to provide alone. The collective effort of multiple mobile peers can be modelled as a composition of services that mobile devices host and share. This thesis envisions service composition to occur spontaneously anytime and anywhere without the need for dedicated infrastructure to be in place. The network among potential service providers emerges on-demand and may dissolve after the composite request has been satisfied. The transient nature of these mobile ad hoc networks, however, exposes service com- posites to three main failure sources: packet loss due to the narrow wireless bandwidth, path loss due to the mobility of the providers, and service rejection due to dynamic provider participation. Further, service providers need to manage complex service re- quests among themselves and balance the cost of failure prevention and recovery. These challenges raise the question of how composites can efficiently adapt to their evolving operating environment. Existing approaches have led to dynamic composition strate- gies to accommodate for change. However, as the next chapter will discuss in detail, their lack of integration between the main composition phases increases either the failure probability or the overhead for failure prevention. This thesis builds on the hypothesis that the later the operating environment is explored to compose a complex service request, the less time there is for the system to change and to render composition decisions invalid. The following chapters describe how the novel model of opportunistic service composition reduces the delay between the phases of the composition process in a communication efficient manner to lower the composite failure in highly dynamic pervasive environments. 13 Chapter 2 State of the art Service composition has been widely used to manage intra- and inter-organisational processes in enterprise systems and on the Web. With technological advances such as embedding sensors in everyday objects, the possibility to create new value-added func- tionality from existing services becomes attractive for pervasive computing environments (Brønsted et al., 2010). However, in contrast to reliable, wired, and resource-abundant enterprise networks, pervasive systems face frequent topology changes, error-prone wire- less communication, and resource-constrained service providers. These differences in- troduce new challenges for service composition and limit the applicability of existing solutions. In particular, traditional centralised composition architectures with a single fixed coordinator suffer from a number of issues that make them inadequate for dynamic operating environments. As a hot spot for computation and communication (Ye, 2006) a static coordinator can run only a certain number of compositions concurrently which limits its scalability (Schuler et al., 2004; Balasooriya et al., 2008). In addition, com- posites that are distributed by nature and that model cross-organisational collaboration have to undergo unnecessary changes to map them to a centralised architecture (Martin et al., 2008; Zaplata et al., 2010). Further, centralised approaches lack the flexibility to cope with dynamic pervasive environments because they are designed for fixed network and service topologies (Chakraborty et al., 2004; Mostarda et al., 2010). The drawbacks of centralised architectures have led to decentralised strategies to han- dle a continuously evolving network of service providers. The following review analyses 15 Chapter 2. State of the art 2.1 Service discovery 2.2 Service allocation 2.3 Service invocation 2.4 Service flows 2.5 Communication Schedule-based Probing Group-based Goal-oriented Concurrent data access Conditional execution paths Common meeting point Broker-based Static fragmentation Dynamic activation Proactive Demand-based Tuplespaces Content-based routing Cross-layer design Fig. 2.1: Structure of state of the art review The review analyses the applicability of existing service composition solutions for dynamic ad hoc networks from the perspective of service discovery, allocation, and invocation as well as the support for service flows and the awareness of wireless ad communication. the applicability of these strategies for dynamic ad hoc networks. Figure 2.1 illustrates the structure of the analysis, which starts with service discovery and the question of how dynamic provider information is discovered and kept up-to-date (cp. Section 2.1). Next, it explores how service allocation is stabilised against frequent changes in the op- erating environment (cp. Section 2.2). Then, the analysis examines service invocation approaches and how scarce provider resources are efficiently blocked, consumed, and released (cp. Section 2.3). Thereafter, it studies service flow solutions and how they synchronise parallel execution paths (cp. Section 2.4). Finally, the analysis turns to wireless communication and how messages among composite participants can be deliv- ered efficiently (cp. Section 2.5). 2.1 Service discovery Many composition solutions (e.g., Schuhmann et al., 2013; Park and Shin, 2008; Samimi and McKinley, 2008; Wang et al., 2004) assume the existence of some kind of service registry, which locates service providers in the network. Implementing this assump- tion, however, represents a challenging research field in itself. Service discovery must enable networked entities to announce local capabilities as services and enquire about services of other entities despite frequent topology changes and varying communication characteristics (Ververidis and Polyzos, 2008). While recent surveys (Mian et al., 2009; 16 2.1. Service discovery Ververidis and Polyzos, 2008) demonstrate the maturity of service discovery in mobile ad hoc networks, this section adds a new perspective by analysing service composition solutions and by asking: How is the knowledge about available services kept up to date if provider information such as connectivity, load, and willingness to participate is dy- namic? Service discovery solutions fall into two categories when it comes to publishing service offerings: proactive and demand-based service announcements. 2.1.1 Proactive When service providers announce themselves proactively, they do so independently of a particular request and their announcements have to be cached and kept up to date. OSIRIS (Schuler et al., 2004) is a peer-to-peer infrastructure to support reliable and scalable process management in dynamic environments. In OSIRIS, a potential com- posite participant maintains a local cache for information it needs to fulfil a service. As the participant’s service can be part of a composite, the cache may store information about providers of a possible successor service. A centralised meta-data repository reg- isters all dynamic changes in the environment and replicates them by pushing relevant information to particular participants. OSIRIS is not readily applicable in dynamic ad hoc environments because these environments do not have dedicated infrastructure to host a centralised entity for information replication. Alternative approaches, like CiAN (Sen et al., 2008), group-based service discovery (Chakraborty et al., 2006), and dynamic service composition Kalasapur et al. (2007), do not require additional infrastructure as they found other ways to update cached provider information. CiAN (Sen et al., 2008) is a workflow engine to support modelling collaborative activities as structured tasks and accomplishing them in mobile ad hoc networks. In CiAN, participants synchronise locally cached service information as soon as they come into each other’s communication range (Sen et al., 2004). This way, knowledge about available services propagates from participant to participant. The initiator of a compos- ite request, however, must wait until a provider for all required services appears in the cache before it can continue to allocate the services. This delays the composition result, in particular, if the network of service providers has just started to emerge. Group-based service discovery (Chakraborty et al., 2006) is a service discovery ar- 17 Chapter 2. State of the art chitecture to allow for distributed, scalable, and adaptive service discovery in pervasive computing environments. Similarly to CiAN, it relies on local caching and participant- to-participant data dissemination. However, while CiAN needs to wait and see if a required service eventually appears in the local cache, this approach will actively search for it. Group-based service discovery selectively forwards a service request and uses the discovery route backwards to deliver a discovery response. This reduces the message overhead compared to simply flooding the network with a search request. A similar approach (Aguilera and López-de Ipiña, 2012) uses selective forwarding based on ser- vice groups and the time-to-live parameter of the communication protocol to reduce the overhead of creating a local service graph on each participant. Dynamic service composition, as proposed by Kalasapur et al. (2007), is a composi- tion mechanism for pervasive computing environments to provide service-related support for resource-poor devices and to assign available resources to user needs, even when an exact match does not exist. Its locality-aware hierarchical caching technique has the potential to further reduce the search overhead as it defines a parent-child relation over co-located devices. Resource-rich parent devices cache the announcements of neighbour- ing resource-poor devices as their children. If a required service is unavailable in the local cache, the search query travels the hierarchy upward to the parent that has greater overview. When there is a match, the parent replies with the physically closest option, otherwise it forwards the request to its own parent. Notwithstanding the search optimisations, the general issue with proactive service announcements is that, the more dynamic information the announcements include, the more maintenance and communication they require. On the other hand, the fewer dy- namic information they contain, the lower is the system’s ability to sense and adapt to changes. For example, if the load or objective of a provider changes, it may temporar- ily disable the provision of a particular service. However, since the service has been announced, the provider may receive service invocation requests which fail because the provider refuses processing them. Revoking the announcement may not avoid failure because of the dissemination delay in the network. Announcing dynamic changes more frequently incurs higher communication overhead and strains the narrow communication bandwidth which may lead to increased network failure. 18 2.1. Service discovery 2.1.2 Demand-based When potential composite participants announce service information on-demand (i.e., when there is a particular request), they reveal up-to-date data that do not need caching or maintenance. However, as demand-based service discovery incurs search delays, ex- isting solutions nonetheless ask providers to register to minimise the delay. Spidernet (Gu and Nahrstedt, 2006) is a service composition framework to provide for high quality and failure resilient service composite in peer-to-peer systems. In Spidernet, service providers announce only static service information proactively which are stored in distributed hash tables. Collecting dynamic information is left to the allocation phase that is triggered when there is a particular composite request. This avoids frequent and expensive table updates. Static service information is a prerequisite for creating a service overlay network that links available services based on whether they are connected by a network link. The overlay is later examined to find a service path that corresponds to the composite request. Logical service groups (Prinz et al., 2008) is a concept for dynamic service composi- tion in peer-to-peer systems to support the adaptation to peer arrivals or variations of their execution properties. It uses a decentralised publish-subscribe mechanism based on distributed hash tables to address the drawback of centralised information replication (cp. OSIRIS in Secion 2.1.1). Providers subscribe based on their service type with the corresponding administrating peer. They are notified when a request for that service type is published and may respond by publishing the static and dynamic details of their offer. The request initiator receives all published replies via the administrating peer. In contrast to Spidernet (Gu and Nahrstedt, 2006), the distributed hash tables do not register service descriptions. Rather, they support targeted multicast messaging. Generally, demand-based service announcement is communication-efficient because service providers reveal just enough dynamic information as required by a request and target it to a particular service consumer. In addition, the service consumer learns only about providers that have enough resources and are willing to execute a required service because otherwise these providers would not respond. This avoids service invocation rejections. However, the above solutions rely on a distributed provider registry that needs 19 Chapter 2. State of the art constant monitoring to replace failed parts. In networks that emerge and dissolve quickly such a registry needs to be established first and then needs to compensate instability which neutralises the communication efficiency. 2.1.3 Summary Dynamic provider information can be announced proactively or revealed on-demand. Proactive announcements do not need additional infrastructure which makes the ap- proach suitable for dynamic ad hoc networks. However, the approach requires high maintenance or risks service invocation rejection when service providers temporarily dis- able individual services due to changes of their system load or objectives. In solutions with demand-based announcements only available service providers respond to a ser- vice request which avoids service invocation rejection and repeated information updates. However, the solutions surveyed are based on an established peer structure that does not exist if a network among service providers emerges because a composite request was raised and dissolves after the request is complete. For dynamic ad hoc environments it may be more efficient to use demand-based service discovery without any pre-existing provider registry as the overhead of maintaining a peer structure may outweigh the bene- fit of information it contains. Instead, investigations on how to recognise service demand without explicit service requests may further improve demand-based service discovery. 2.2 Service allocation Service allocation examines ways of finding, for each required service, a suitable provider such that an abstract request description turns into an executable composite. Compos- ites in dynamic ad hoc environments face frequent changes in the network and service topology which may invalidate allocation decisions and cause their failure. This raises the question: How is the allocation of service providers stabilised against dynamics of the composite’s operating environment? The approaches reviewed in this section base their allocation decisions on schedule information, probing, provider groups, and high level goals to counteract composite failure. 20 2.2. Service allocation 2.2.1 Schedule-based One way to handle dynamic environments is to incorporate schedule information into the allocation process (Wang, Wang, Zheng, Xu and Yang, 2009; Sen et al., 2008). In service-oriented wireless sensor networks, for example, the sensor sleep schedule limits service availability and recovering from resulting disruptions consumes scarce energy. An approach to minimise re-allocation and to save energy derives the duration for which a provider is continuously available from its sleep schedule and services offerings (Wang, Wang, Zheng, Xu and Yang, 2009). From different feasible sets of providers, that steadily and collectively provide a composite, the base station chooses the set with minimum transmission cost and propagates the allocation in the network. Similarly, in leader-team scenarios (e.g., on a remote construction site) each service provider has a schedule containing its commitments in time and space. This can be used to allocate tasks such that team members encounter each other to exchange intermediate results and trigger the next step in a workflow (Sen et al., 2008). In both approaches, failure due to service unavailability is unlikely because changes are foreseeable and thus disruptions avoidable. Further, if service providers are mobile, their obligation towards their leader (Sen et al., 2007) or organisation (Catarci et al., 2008) steers their movement towards achieving a task or staying connected. However, the availability of schedule information and the obligation towards an au- thority are characteristics that apply only to a subset of dynamic ad hoc environments. Generally, service providers are autonomous and not obliged to disclose their schedules. Freely roaming the network, they rather spontaneously participate in a composite. 2.2.2 Probing Probing-based solutions gather dynamic provider information in a service overlay net- work to guide their allocation toward a stable composite. A service overlay network is a representation of available services that creates logical links between services if their providers are connected by a network route (Park and Shin, 2008). Multi-path solutions (Gu and Nahrstedt, 2006; Park and Shin, 2008; Samimi and McKinley, 2008; Wang, Xu, Qian and Lu, 2009) induce probe messages in a service 21 Chapter 2. State of the art overlay network to trace the characteristics of potential service candidates and identify multiple high-quality composition paths. Probing with resource-aware routing (Park and Shin, 2008) estimates, e.g., the residual energy, contention rate, and response time to avoid exhaustion and overload in the network. Pruning strategies reduce the over- head of probing that would otherwise span the entire overlay network. Spidernet (Gu and Nahrstedt, 2006) limits (e.g., based on the priority of the request) the total number of probe messages that is allowed for a composite and the number of duplicate service providers that should be probed. Dynamis (Samimi and McKinley, 2008), an algorithm for efficient probing in service overlays, applies selective forwarding whereby probe re- cipients forward probe messages only if the contained path is of higher quality (e.g., in terms of end-to-end delay, load balance, or security) once they add their service. In contrast, single-path solutions like sFlow (Wang et al., 2004) determine a single high quality path in the service overlay. sFlow is an allocation algorithm to provide resource-efficient and agile service composites. While exploring the service overlay, it allocates the most suitable provider in each hop and avoids the need for pruning strate- gies. sFlow applies multiple quality objectives, namely latency and bandwidth, and determines the shortest widest path from an allocated service provider to its successor. Exploring the service overlay network and constructing the optimal composition path en route aligns the allocation to dynamic provider properties. However, probing-based allocation is decoupled from service discovery and implies additional composition delays and communication overhead. 2.2.3 Group-based Group-based allocation solutions assign a set of providers to a required service and leave the allocation decision flexible until service invocation. OSIRIS (Schuler et al., 2004) notifies composite participants about the arrival or departure of possible providers for the subsequent service in the composite. Once the participant receives a service invocation request, it executes the service and only then allocates the subsequent provider from the set of candidates. Alternatively, a logical service group (Prinz et al., 2008) represents all available service providers for a particular service type. The group dynamically re-elects the 22 2.2. Service allocation group leader, who eventually executes the required service, if the current leader departs or another member with more suitable execution properties arrives. For a composite, the requesting peer starts with the last required service, creates a logical service group and assigns the leader role to the best performing peer in that group. In the same way, the group leader appoints the leader for its preceding service. A group subscribes to changes in their successor group to ensure it stays informed about leader re-elections. Group-based allocation flexibly adapts to dynamic service availability as it inte- grates better performing providers even if they arrive after the initial allocation. The proposed techniques, however, group service providers logically without imposing local- ity restrictions. This is at risk of increased communication cost because group members or consecutive providers can be scattered over the network. 2.2.4 Goal-oriented Goal-oriented allocation approaches create composites automatically to cater for un- predictable and evolving circumstances (Bucchiarone et al., 2012). Instead of abstract composite descriptions, requesting entities express their needs in terms of available input and expected output. The composition handles the actual construction of the request. For this, a service aggregation algorithm (Kalasapur et al., 2007; Wang, Xu, Qian and Lu, 2009) creates a graph of available services and links those that are semantically and syntactically compatible. Traversing the graph from input to output (Thomas et al., 2009) or in reverse (Wang, Xu, Qian and Lu, 2009) creates the actual composite request with the corresponding service providers. Other techniques employ an artificially intelligent (AI) planner (Madhusudan and Uttamsingh, 2006; Bidot et al., 2011; Pinto et al., 2012) and distribute the planning (El Falou et al., 2010) among multiple service agents to reduce the high number of possible service combinations. Agents first derive partial plans locally and a central coordinating agent merges those to a final plan. Goal-oriented allocation is highly flexible because goals rather than specific tasks are matched against currently available services. However, it relies on an up-to-date view of available services to generate a stable execution plan and reinforces the issues related to proactive service announcements and the need for their frequent updates (cp. Section 23 Chapter 2. State of the art 2.1.1). Further, it is not clear whether mobile devices have sufficient resources to handle the higher complexity and coordination effort that in particular AI techniques imply. 2.2.5 Summary Allocation solutions use schedule information, probing, provider groups, or goal-oriented composite creation to stabilise the allocation against frequent topology changes. Among these approaches, integrating schedule information in the allocation process is most effec- tive because changes are foreseeable and their negative impact can be avoided. However, in dynamic ad hoc environments such information is unlikely to be available because ser- vice providers are autonomous and not obliged to disclose their schedules. Goal-oriented automatic composite creation is highly flexible because it matches goals rather than specific tasks to available services. Its need for an up-to-date view of available services, however, requires providers to announce themselves proactively and reinforces the asso- ciated challenges that are discussed in Section 2.1.1. Group-based allocation is also very flexible towards changes because the final provider of a required service gets allocated only prior to its execution. However, the reviewed solutions do not impose locality re- strictions of service groups which increases the communication effort for managing the group. Probing-based techniques preserve the locality of allocations naturally because the service overlay network which they explore is based on physical network links. The drawback of probing is that it is decoupled from service discovery and introduces addi- tional composition delay and communication effort. With the flexibility of group-based allocations and the locality of probing techniques the question arises whether the benefits of both can be integrated in one approach. 2.3 Service invocation Service invocation ensures that one provider per required service is called for execution. In contrast to Internet-based service domains, mobile computing environments are at risk of exhaustion and invocation rejection sooner because mobile devices have fewer local resources available and depend on the objectives of their (human) carrier. This motivates the question: How are provider resources efficiently blocked, consumed, and 24 2.3. Service invocation released to maximise general provider availability and to maintain stable composites? Broker-based designs, static fragmentation, and dynamic activations are ways to invoke the required services of a composite and address the question from different perspectives. 2.3.1 Broker-based Broker-based composition approaches entrust a single entity, i.e., the broker, with the discovery, allocation, and invocation of required services. Solutions for nomadic networks place the broker on a reliable fixed node to ensure the composite does not disappear (Philips et al., 2010). Such a setup, however, implies long expensive routes or failure, if the fixed broker is not in vicinity of or disconnected from mobile service providers. In contrast, distributed dynamic brokers (Chakraborty et al., 2005) are part of the mobile ad hoc network and are dynamically selected. A requesting entity appoints its broker based on how well the broker connects to required services. The selection considers the broker’s local services, services in its neighbourhood, load, and energy to increase the composite’s flexibility towards topology changes. Brokers reduce the involvement of the service provider in the composition to a mini- mum. Unaware of whether its invocation context is a composite or basic service request, the provider does not need to participate in a lengthy allocation process or wait for pre- decessors to finish. It blocks local resources only for the duration of the service execution and releases them once it sends the service result back to the broker. However, above solutions do not explicitly obtain the provider’s commitment. They simply invoke the provider and assume it has sufficient resources and is willing to participate. Further, bro- kers are the destination for all intermediate results of the composite and prevent direct, possibly more localised, interaction among subsequent service providers. Finally, brokers may not be available in ad hoc networks that emerge and dissolve quickly because none of the participants has initially a sufficient overview of available services. 2.3.2 Static fragmentation Static fragmentation partitions a centralised composite description and deploys the com- posite fragments on previously selected service providers such that the providers can 25 Chapter 2. State of the art interact directly without a broker. Fragmentation techniques (Balasooriya et al., 2008; Fernández et al., 2010; Martin et al., 2008; Sen et al., 2008) are manifold but share a sim- ilar notion about fragment content which includes the service to execute and references to the input source and output destination of that service. Bond-Flow (Balasooriya et al., 2008), for example, is a middleware to provide dis- tributed coordination for collaborative applications. It distributes the complexity of the centralized composition logic over stateless web services and dynamically generates coordinator proxy objects to simplify the composite development. These proxies wrap a service with coordination logic as well as state and dependency information and en- force dependencies during execution. Composites that apply the chemical programming paradigm (Fernández et al., 2010; Fernández et al., 2012) use the metaphor of chemi- cal reaction rules to coordinate complex applications. They follow the same concept as Bond-Flow but formalise decentralised composite execution in terms of a higher-order chemical language. Another alternative to formalise the control flow among fragments are executable workflow networks (Martin et al., 2008) which is a process model to partition executable BPEL processes. CiAN (Sen et al., 2008) decouples the input and output dependencies of a fragment from the actual fragment provider to ease re-allocation. Fragments identify dependencies on other fragments via task numbers rather than provider addresses such that in case of a failure a provider can easily be replaced without notifying subsequent providers. In contrast to fully-decentralised but hard to validate solutions, a hybrid approach (Mostarda et al., 2010) compiles centralised composite descriptions into choreographed synchronised finite state machines and a skeleton that is operated by a central leader. A consensus protocol between the leader, its backups, and the local state machines allows for consistency among distributed participants and correct execution. Generally, static fragmentation has three drawbacks: First, all fragments are allo- cated at once and before the composite starts executing. This makes the composite insensitive to changes in the operating environment that occur during the allocation or invocation. Second, fragments block resources for all required services even those that do not get executed due to conditional paths or premature termination. Third, with the possibility of dead execution paths, a provider faces the challenge of determining when 26 2.3. Service invocation it is safe to uninstall a fragment and free up resources. Regarding the first drawback, group-based allocation approaches (Schuler et al., 2004; Prinz et al., 2008) are more receptive to the system dynamics as they postpone the final allocation decision to when the required service needs to be invoked. However, until then they block a number of service providers and minimise provider availability for other composite requests. 2.3.3 Dynamic activation The dynamic activation of service providers is an alternative approach to execute a composite in a decentralised manner and to block resources that are actually needed. One way to achieve this is to store task files in a centralised repository rather than on the allocated service provider (Ye, 2006). Service invocation signals activation and the invoked provider first fetches its task file according to which it then executes the assigned service and invokes the subsequent service provider. A technique based on dependency tables (Fdhila et al., 2009) may be used to partition the centralised composite description and generate task files instead of code fragments. Continuation-passing (Yu, 2009b) is the fully decentralised alternative that trans- fers the remainder of a composite along with the composition control from provider to provider. Continuation objects originate from programming languages and are a viable solution for composite execution as they reduce the accumulation of control context (Manolescu, 2002). Self-describing workflows (Atluri et al., 2007) detail how a service provider derives its execution part from the continuation and how it afterwards creates a new self-describing workflow for the remainder. Dynamic activation addresses the shortcomings of static fragmentation and activates service providers as the composite execution enfolds. However, the way existing ap- proaches (Ye, 2006; Atluri et al., 2007; Yu, 2009b) are organised, implies that service providers have been identified in an allocation process but have not yet been notified to reserve resources. The approaches assume that a service provider is always ready to serve and ignore the fact that changing load and objectives may negatively affect the availability of a provider. In addition, these solutions have not evaluated the suitability of dynamic activation in mobile ad hoc environments. 27 Chapter 2. State of the art 2.3.4 Summary Solutions to service invocation range from broker-based designs over static composite fragmentation to dynamic provider activation. Broker-based designs reduce the involve- ment of a service provider in a composite to a minimum because the broker handles all composition-related tasks and the provider only executes a required service. However, brokers prevent direct provider interaction and are unlikely to be available in transient networks where all participants initially have a limited view of available services. Static fragmentation provides for direct provider interaction and formalises the control flow among consecutive service providers. However, deployed prior to composite execution, static fragments are insensitive to system dynamics and allocate resources for conditional parts of the composite that do not get executed. Dynamic provider activation is an al- ternative for decentralised composite execution and blocks resources that are actually needed. However, none of the reviewed solutions explicitly confirms the availability a provider to execute a service. One the one hand, they may simply assume the provider is available for service invocation which increases composite failure because the load and objectives of a provider changes dynamically. On the other hand, the solutions may assume providers have been blocked during service discovery which would imply a long blocking period that minimises the general availability of service providers. Either way, these assumptions highlight a gap and the need to address it. 2.4 Service flows Service flows are service composites with parallel execution paths. This section refers to composites whose parallel execution paths merge in a single thread of control. For example, in the introductory scenario (cp. Figure 1.1 on page 3) Adam’s noise tracking composite contains an audio filter service that merges the results of two independent audio sampling services and then continues with a single feature classifier service. The filter service is a merge service and represents the common meeting point of the two parallel execution paths. Service flows may require the synchronisation of concurrent data access and may contain conditional execution paths. For example, Adam could have modelled his composite request such that a global variable holds the noise readings 28 2.4. Service flows and needs to be accessed by the two sampling services concurrently. In addition, he could have included a conditional path that integrates a third sampling service if it is available. As the complexity of composites increases, the challenges of managing concurrent data access, handling conditional execution paths, and identifying common meeting points arise. This motivates the question: How can service composites efficiently synchronise parallel execution paths despite frequent topology changes? 2.4.1 Concurrent data access Similar to multiple threads in a program, parallel paths of a service composite may access and modify the same global data object. Executing parallel paths without synchronisa- tion leads to inconsistency (Russell et al., 2005) and could produce wrong or undesired results (Zaplata et al., 2010). One solution is to reduce concurrent access to shared data during the design of the composite and otherwise define data classes from which an appropriate synchronisation strategy can be derived at runtime (Zaplata et al., 2010). Such a strategy may be based on a unique token for data access that only one path at a time can hold. The execution paths exchange the token by including it within control messages to reduce the synchronisation effort (Yu, 2009a). Alternatively, a centralised leader forwards the token to interleave parallel tasks and to synchronise the composite state immediately after the execution of each service (Mostarda et al., 2010). Among these solutions, avoiding concurrent data access seems most desirable as it does not incur any effort at runtime. Otherwise, passing data access tokens with control flow messages is more suitable for dynamic ad hoc networks than a centralised synchro- nisation solution because a central entity prevents from direct provider interaction. 2.4.2 Conditional execution paths Conditional execution paths allow for flexibility in modelling a composite request as intermediary results may change how the composite proceeds. However, a composite reveals only during its execution which parallel paths actually need to be merged into a single thread of control (Russell et al., 2006). A merge service must be prepared to receive a message from any possible path (Yu, 2009a). 29 Chapter 2. State of the art Static fragmentation approaches (cp. Section 2.3.2) pre-allocate all services in a com- posite and need to send an invalidation message along obsolete paths to release redundant service providers during composite execution. The concept of pattern replication (Fdhila and Godart, 2009) reduces this effort by creating composite partitions that, aligned to the control logic, disable entire successor partitions rather than individual services. For this solution to become effective, providers for a partition cannot be allocated until the partition is about to be invoked. However, the approach, as published, does not provide details on how the allocation and invocation of composite partitions is organised. Dynamic activation solutions (cp. Section 2.3.3) remove obsolete conditional paths in the remainder of the composite as the composite enfolds. Continuation passing, as proposed by Yu (2009a), initialises service providers with potential input dependencies from preceding services and needs to notify them if their path becomes obsolete. Self- describing workflows (Atluri et al., 2007) do not require additional notifications. How- ever, as this solution does not explicitly block resources on allocated service providers, which potentially leads to service invocation rejections, it is unclear how it would other- wise release them. Similarly, broker-based designs (cp. Section 2.3.1) also do not obtain the provider’s commitment prior to its invocation and thus do not specify how to release them when an execution path becomes obsolete. Generally, handling conditional execution paths depends on how service providers are allocated and when they block resources for service invocation. Service invocation solutions that do not block provider resources, do not need to release them if execution paths become obsolete but risk failure due to service invocation rejection. On the other hand, solutions that allocate providers prior to the execution of the composite require ad- ditional communication effort to release redundant service providers. Dynamic provider activation can potentially reduce this effort but needs to integrate an efficient way to block provider resources prior the invocation of a particular service to be applicable for dynamic ad hoc environments. 2.4.3 Common meeting point Parallel execution paths, that merge in a single service, need a common meeting point. Recent work on the dynamic execution of business process (Zaplata et al., 2010) acknowl- 30 2.4. Service flows edges the need for a defined synchronisation point that can be chosen at runtime. The following analysis first revisits allocation and invocation techniques and then reviews election and consensus protocols to investigate how a common provider for a merge service can be identified dynamically. 2.4.3.1 Service allocation and invocation In broker-based designs (cp. Section 2.3.1), a broker handles composition logic lo- cally and represents the common meeting point. It merges parallel service flows nat- urally without additional synchronisation effort. However, the availability of brokers in transient networks is unlikely because none of the participants have initially sufficient overview of available services that would qualify them as brokers. In static fragmentation solutions (cp. Section 2.3.2), the composite initiator finalises provider allocation. In particular, it selects the provider for the merge service and in- cludes the decision in the fragments for the predecessors of the merge service. While this avoids negotiation during execution, topology changes may render such early decisions less optimal by the time the merge service is invoked. Existing solutions for dynamic provider activation (Yu, 2009b; Atluri et al., 2007) allocate a merge service prior to composite execution and are similarly prone to changes. Group-based allocation is more flexible towards system changes as it finalises provider allocation during composite ex- ecution. However, among the existing solutions, only OSIRIS (Schuler et al., 2004) addresses service flows and requires a reliable and globally available synchronisation node, which may not exist in dynamic ad hoc networks. Among probing techniques, multi-path solutions (cp. Section 2.2.2) find, based on quality criteria, the optimal allocation for the composite which includes the optimal path between the merge service and its successors. However, confirming the final allocation decision with the selected service providers (Gu and Nahrstedt, 2006), introduces delays that may invalidate the optimum. A single-path solution (Wang et al., 2004) may con- firm the allocation in each hop, except from the merge service which is selected by the composite initiator when it assembles the allocated parallel paths. While this reduces the allocation delay, it compromises the allocation optimum because the initiator, due to its limited system view, does not know how well a merge candidate connects to all 31 Chapter 2. State of the art predecessors. Solutions in which the provider of a split service allocates the provider of the corresponding merge service (Yildiz and Godart, 2007) face the same issue. The split provider cannot foresee which yet-to-be-allocated service providers will actually interact with the merge service and how well they connect to their successor. The composition solutions reviewed up to this point are limited in their applicability for dynamic ad hoc networks. They either assume that a reliable or well-informed com- posite participant exists to represent the common meeting point. Or, they compromise the flexibility or locality of the merge allocation. A way to increase the allocation flexi- bility and locality is to enable the predecessors of the merge service to allocate a common provider during execution. This, however, involves two challenges (Yildiz and Godart, 2007). First, multiple service providers have to agree on the same merge provider at runtime. Second, these synchronisation partners are mutually unknown as they, too, are bound only prior to their invocation. The synchronisation algorithm, proposed by Yildiz and Godart (2007), addresses these challenges with continuous path updates. Parallel paths update each other about their next allocation decision such that final synchronisation partners are mutually known to run an agreement protocol. However, as the algorithm has not been evaluated in dynamic ad hoc networks, its communication overhead and suitability for mobile service providers is unclear. 2.4.3.2 Election and consensus protocols Election and consensus protocols for distributed systems relate to some extent to the problem of finding a common merge provider. Election protocols have to ensure that all participants in the network refer to the same new coordinator after the current one has disconnected (Park et al., 2009; Singh and Sharma, 2011). An election is led by a single decision maker who needs a global view of the system to consider the logical distance between each participant and the new coordinator (Higashi et al., 2011). Maintaining such a view is expensive and infeasible in true peer-to-peer networks (Gu and Nahrstedt, 2006). Further, identifying a common provider for a merge service involves only a subset of participants which can communicate in a more targeted way than through controlled network flooding (Park et al., 2009; Singh and Sharma, 2011). Consensus protocols achieve an agreement among agents if the opinion of all agents stabilises. Stochastic 32 2.4. Service flows consensus models (Roy et al., 2006) assume that agents are connected to each other and aware of all possible opinions. This thesis explores a communication-efficient way to establish such knowledge by mutually introducing synchronisation partners and revealing possible merge candidates. 2.4.4 Summary Service flows introduce the challenge of managing concurrent data access, conditional execution paths, and common meeting points. Avoiding concurrent data access in the design is desirable because it does not require synchronisation during execution. If this is not possible, exchanging data access token (Yu, 2009a) is a viable solution for dynamic ad hoc environments because these tokens can be integrated with composition control flow messages. For handling conditional execution paths, dynamic provider activation is a promising approach. It removes obsolete parts from the composite as it enfolds during execution and activates only required providers. However, existing solutions (Yu, 2009b; Atluri et al., 2007) do not specify when they confirm the commitment of the provider, block its resources for service invocation, and release provider resources in case a path becomes obsolete. Without such a strategy, the composite is prone to failure as the load and objectives change the provider availability dynamically. Solutions for finding a common meeting point tend to be of limited applicability for dynamic ad hoc networks. The reviewed techniques either assume reliable and well- informed entities or compromise on the flexibility and locality when allocating it dynam- ically. Among the existing solutions, the synchronisation algorithm, proposed by Yildiz and Godart (2007), is promising because it increases flexibility and locality. Parallel ex- ecution paths continuously exchange updates about their allocation decisions such that the final providers can run an agreement protocol about a common successor. However, as this algorithm has not been evaluated for dynamic ad hoc networks, its impact on mobile service providers and service composites is unclear. 33 Chapter 2. State of the art 2.5 Communication In dynamic ad hoc environments composite participants cannot rely on managed com- munication infrastructure and have to self-organise a network to collectively achieve a complex task. Their mobility and the nature of the wireless medium, however, make service composition challenging as network routes may change frequently and bandwidth is limited. This raises the question: How can service composition and ad hoc commu- nication be aligned to deliver messages among composite participants efficiently? The reviewed approaches address this question with tuplespaces, content-based routing, and cross-layer designs. 2.5.1 Tuplespaces Service invocation via tuplespaces (Martin et al., 2008; Fernández et al., 2010) enables composite participants to exchange messages while they may not be present in the net- work at the same time. They use a shared remotely-accessible container (i.e., a tu- plespace) to hold service allocations and control flow messages. If a control flow message arrives in a tuplespace and matches a service allocation, execution of the corresponding service provider is triggered. While allowing for timely decoupling, tuplespaces imply a strong spatial dependency because a service provider and a service consumer must refer to the same tuplespace to communicate. This is challenging in networks that lack dedicated infrastructure. LIME (Murphy et al., 2001), is a middleware to coordinate applications that are distributed among mobile hosts. It breaks a tuplespace in multiple tuplespaces and deploys them on mobile hosts. When two hosts come in each other’s communication range, their tuplespaces merge to one virtual space and increases the possibility for service allocations to meet and match control flow messages. However, the source and destination of a control flow message may never meet. CRUST (Artail et al., 2009), is an extension to LIME and offers clustering and routing capabilities for tuplespaces. It forwards tuples across tuplespaces to ensure that service allocations and control messages eventually meet. From the communication perspective, this approach converges with routing protocols for direct messaging in mobile ad hoc networks. 34 2.5. Communication 2.5.2 Content-based routing CiAN (Sen et al., 2008) presents a content-based publish-subscribe routing scheme to provide for interaction among composite participants despite a dynamic and fragmented network. It assigns a unique totally-ordered service id to each required service which service providers use to deliver their service result to their successor or to subscribe for service data from their predecessor. These messages are then relayed by intermediaries based on their service id. For example, an intermediary forwards a subscription if its own service id is between the id of the source and destination of the message and smaller than the last intermediary’s id. A message containing a service result is routed the same way, only in increasing manner. Eventually a subscription and a service result meet on one intermediary who dispatches the service result directly to its destination. The protocol is robust to topology changes because intermediaries store messages until they encounter a suitable router to forward the message. However, as service ids do not reflect location, a message may take a detour to reach its destination and requires more time and communication effort to be delivered. 2.5.3 Cross-layer design Cross-layer approaches combine service discovery with underlying routing mechanisms to exploit routing traffic (Ververidis and Polyzos, 2008). For example, a modified route request carries a service discovery request while periodic messages for route mainte- nance contain service announcements (Varshavsky et al., 2005). This is to reduce the communication overhead of otherwise separately operating layers. Group-based service discovery (Chakraborty et al., 2006), on the other hand, uses the backward route of a service request to deliver a service discovery response. This way, a new route and the associated overhead for route discovery is only necessary if the original route breaks. While these approaches show a benefit in terms of communication overhead they are limited to service discovery and do not investigate how the need for interaction during service allocation and invocation could be integrated with routing protocols. 35 Chapter 2. State of the art 2.5.4 Summary Communication approaches based on tuplespaces, content-based routing, and cross-layer designs all provide means to adapt to the dynamics and bandwidth constraints of dy- namic ad hoc networks. They differ, however, in their awareness of a message being sent as part of a service composition process. Tuplespaces support the interaction between composite participants that are not present at the same time. Their extensions for dy- namic networks, however, dispatch messages similarly to conventional routing protocols and regardless of their composition context. Content-based routing, as proposed by Sen et al. (2008), uses the order of required services in a composite to relay messages. While robust to topology changes, this approach may in