Towards a comprehensive approach to spontaneous self-composition in pervasive ecosystems Sara Montagna, Mirko Viroli, Danilo Pianini Jose Luis Fernandez-Marquez DEIS–Università di Bologna University of Geneva via Venezia 52, 47521 Cesena, Italy Route de Drize 7, CH-1227 Carouge, Switzerland Email: {sara.montagna, mirko.viroli, danilo,pianini}@unibo.it Email: joseluis.fernandez@unige.ch Abstract—Pervasive service ecosystems are emerging as a new II. S ELF -C OMPOSITION APPROACHES paradigm for understanding and designing future pervasive computing systems featuring high degrees of scale, openness, A software service represents a functionality that can be adaptivity and toleration of long-term evolution. A key issue provided on demand in order to create higher level software in this context is making certain patterns of behaviour emerge artifartefactsacts, such as applications or higher level services. without any supervision or design-time intention, and a primary example is the fully-spontaneous composition of services, possibly The notion of service allows applications to be easily devel- at multiple levels. We argue that this can be successfully achieved oped and to adapt by changing the different services, which only by a comprehensive approach exploiting together the main the application is composed by, at run-time. Self-composition ingredients proposed so far in literature: (i) existence of intel- of services involves the automatic discovery of new services ligent components finding proper (semantic) matches of service by composing available ones, the selection of services, the descriptions, (ii) use of distributed evolutionary techniques to dynamically select appropriate ways of composing services, plan to execute them (i.e. services execution order), and the and (iii) approaches in which rating quality of composition is adaptation of the composed service when new requirements solely based on their successful exploitation. This proposal is appear or a service disappears from the system. presented through an example of spontaneous composition in 1) Service Composition in SOA: The static character of crowd steering services. traditional composition approaches such as orchestration and I. I NTRODUCTION choreography has been recently challenged by so-called dy- Services are one of the main actors in pervasive and ubiq- namic service composition approaches, involving semantic uitous computing. Composing services is a big issue in these relations [5], and/or AI planning techniques to generate pro- contexts, providing new applications or high level services. cess automatically based on the specification of a problem Self-composition is even more challenging. [21]. Their basic goal is to analyse a description of the In literature some surveys and possible solutions have been services to compose and compute a composition satisfying proposed, but only few of them give concrete proposals for the structural/behaviour/ontological compliance of the result of design, implementation and evaluation of service composition. composition as can be deduced from information about the Moreover the composition of services is solved in a centralised composites. One of the main challenges of these approaches way, solution which hardly deal with the large-scale distributed is their limited scalability and the strong requirements they property of pervasive systems, or the composition is specified pose on the detail of service description. by the application developers, preventing the system to use 2) Evolutionary techniques: Evolutionary approaches such new services that appear at runtime. as those based on Genetics Algorithms (GA) have been In this paper we frame/situate the problem of self- proposed as well for service composition, such as in [7], composition in the framework of pervasive ecosystems, defin- motivated by the need of determining the services participating ing what a service is and what composing services means. in a composition that satisfies certain QoS constraints, which is We then propose an approach to perform self-composition of known to be a NP-Hard problem. More generally, evolutionary services and demonstrate our ideas showing how gradient - a approaches have been used in the field of autonomic comput- crucial service in pervasive system applications, in particular ing to establish the set of norms, policies or rules that drive for those ones used for crowd steering – can be composed the system to the desired emergent behaviour [15]. We observe with other services. In particular our discussion focuses on that this approach has a potential for service composition: the composition of gradient with services providing local in the same way as the genetic programming determine the levels of crowd, at the purpose of avoiding path crossing proper execution of functions and their parameters, it could overcrowded areas. This example is modelled in terms of “Live be used to find which services, their order of execution and Semantic Annotations” (LSAs) and eco-laws, that are the basic the parameters that its service should receive. components of a pervasive ecosystem [20], and preliminary 3) Competition-based approaches: In order to tackle the simulations, aimed at validating the approach, are run on top potentially high number of different compositions that can of A LCHEMIST [14]. arise in an open system, in [18] a mechanism of coordination reactions for networked tuple spaces is proposed, showing how it can be applied to support competition and composi- tion in a fully distributed setting—services opportunistically compose in those regions of the network where this results in a more competitive service. While all compositions can possibly take place, thanks to a positive/negative feedback only successful ones are meant to “survive” in the system, the others fading until becoming never actually selected. This is achieved by matching services with requests through a self-regulating dynamics inspired by prey-predator model of population dynamics [6], and by diffusing service tuples using a computational-field approach similar to the one presented in [12], [4]. III. A COMPREHENSIVE APPROACH FOR PERVASIVE ECOSYSTEMS As previous section emphasised, the issue of service compo- sition is becoming wider and wider, and is now encompassing new research areas. Among them – pervasive computing, Fig. 1. An architectural view of a pervasive ecosystem. autonomic computing, robotics – we here focus on pervasive computing, and in particular, on the framework of pervasive ecosystems [22]. There, we understand and design a very large and dense pervasive computing system as a sort of for the ecosystem, which is called (LSA); (LSA-space) the substrate in which humans, institutions, software systems and LSAs of each agent are reified in a distributed space (called devices, inject services of various kinds without an a-priori an “LSA-space”) acting as the fabric of the ecosystem, and are knowledge of the structure and behaviour of those already stored in the portion of it that reside in a specific computational available and those that will be injected later. Such services device; (LSA bonding) to make any agent act in a meaningful diffuse in the network, and are situated and context-aware in way with respect to the context in which it is situated, a the sense that they contextualise to (i.e., they will affect and be mechanisms based on bonds (i.e., a reference from one LSA affected by) the situation in each niche of it. In turn, while in to another) is introduced: it is only via a bond that an agent standard SOA a service is a centralised point of functionality, can inspect the state/interface of another agent and act accord- interacting with its clients by stateful protocols of message- ingly; (eco-law) while agents enact their individual behaviour passing actions, a service is here a more generalised concept: by observing their context and updating their LSAs, global it is any activity, triggered by the intention of some localised behaviour (i.e., global system coordination) is enacted by self- software agent, that flows in the system updating the spatial organising manipulation rules of the LSA-space, called eco- and temporal configuration of other services, and generating laws, executing deletion/update/movement/re-bonding actions a set of events ultimately perceived by the other agents in the applied to a small set of LSAs in the same locality in a system. Examples of such services include: the materialisation chemical-resembling style. of data produced by all sensors available around, routing Figure 1 shows an architectural view, based on the above services able to interconnect devices based on their physic abstractions, of a portion of an ecosystem featuring: two al, logical or social proximity, local/global advertisers of the smartphones (carried by people) and two public displays availability of some content, situation recommenders capturing forming a network of 4 computational nodes; a local LSA- relevant information about a context, and so on. Typical space and some agents running in each node (e.g., recommen- application scenarios include pervasive display ecosystems, dation agents, advertising agents, visualisation agents in dis- augmented social reality, and traffic control—the reader is plays, profile agents and sensor agents in smartphones); LSAs deferred to [22] for a more deeper description of them. through which agents manifest (in colour); additional LSAs A. Abstract architecture representing data, knowledge, and contextual information like the existence of neighbouring nodes (in white); bonds between In particular we here focus on the SAPERE framework LSAs; and a set of eco-laws executed by an underlying engine [19], an incarnation of the pervasive ecosystems paradigm working over the global LSA-space. based on the bio-chemical inspiration. This is based on the following abstractions: (LSA) the various software agents In a more general case, one should think at a very large living in the ecosystem (whether they run on smartphones, and mobile set of devices connected to each other based on sensors, actuators, displays, or any other computational device) proximity creating a distributed “space” – ideally a pervasive have a uniform representation exposing any information about continuum – where LSAs form spatial structures evolved over the agent (state, interface, goal, knowledge) that is pertinent time. B. A language of semantic chemistry same content of ?R plus additional constraints specified by any following triples. Inspired by the work in [20], we here present a language for • In place of each element of a triple one can use an expressing information as semantic annotations, and chemical- expression inside parenthesis, which the underlying en- resembling rules as declarative manipulations of those anno- gine should evaluate to a standard value. As an example, tations. We fully-ground it on frameworks and technologies (?V+5) has a meaning when variable ?V is bound to a for the Semantic Web, due to their support for openness and value n, in which case the whole expression yields the since they provide standard and well-accepted specification result of adding 5 to n. Also for expressions we rely on techniques. Namely, we inherit several syntactic and semantic SPARQL syntax. aspects of RDF (Resource Description Framework [2]) and • The object o of a triple “s p o” can be prepended by a the SPARQL (query languages for RDF [16]) for coding symbol “+”, “-”, or “=”. The former (which is assumed rules: the main advantage of this choice is that off the shelf by default when no symbol is prepended) means that the query engines (supporting execution of SPARQL queries and triple should exist, the second that it should not exist, and updates over RDF stores) and reasoners [17] can be used the latter that it should be the only one that exists for that to support scheduling and execution of rules locally—hence subject and predicate (s and p). directly leading to an implementation, though we shall not • When in a triple “s p o” we use a variable enclosed deepen this aspect in this paper. in square brackets [?V] in place of o, it means that In our framework, an annotation is a semantic tuple with ?V will be bound to a list of objects o0 . Then as usual, a unique, system-wide identifier, and a content (description). symbols “+”, “-”, or “=” can be prepended to mean that This is realised as an RDF-like set of multi-valued properties, the corresponding triples “s p o0 ” exist, should not exist, or equivalently, a set of triples “s p o” that consist of a should be exactly the list of triples for s and p. subject (a tuple-id), a predicate (the property name, a Uniform • For syntactic convenience, we also allow a pattern to Resource Identifier – URI) and an object (the assigned value, a consist solely of the source, meaning no further constraint literal or a URI). URIs are qualified by universally-accessible on its triples is imposed. namespaces (using syntax namespace:term), typically con- taining ontologies defining certain aspects of a domain. By The semantics of a rule is then simply understood as a adopting notation N3 [1], an annotation is e.g. pre/post-condition application. It consumes a set of reac- tant annotations matching left-hand side patterns and corre- id p v; q w1, w2, w3; r z1, z2 . spondingly produces a set of product annotations obtained where id is the annotation-id, property p is assigned only by applying the post-conditions expressed in the right-hand to value v, property q is assigned to values w1, w2, and w3, side patterns. As in [8] transition rules also obey a numeric and finally property r is assigned to values z1 and z2—we transformation rate r. Here it represents a Markovian rate in will often omit the trailing dot in an annotation. The main a continuous-time Markov chain (CTMC) system. Such a rate advantage of this structuring of annotations with respect to can be omitted, in which case it is assumed to be infinite, that syntactic tuples (sequences of values) is that it better scales is, the transition rule is executed with “as soon as possible” with complexity of descriptions – as will be clearer below, semantics. Execution of a transition rule amounts to atomically e.g., we will not need to remember the meaning of ith value removing reactant annotations from the space and inserting in a tuple, or mention variables for all tuple arguments when product annotations back. The formal semantics of this rule defining templates. language can be given by translation into SPARQL queries Following [8], rules are structured as chemical-resembling and updates, which we do not present here for the sake of reactions, using a language of patterns specifically in- space. troduced to tackle semantic annotations (and using con- Our framework handles topological aspects as follows. structs inspired to SPARQL [16]). A rule is of the kind First of all, each annotation carries a special property named “P+..+P --r--> Q+..+Q”. Elements P and Q are patterns of mid:#loc, associated to the id of the location where the annotations, namely, annotations decorated with the following annotation is currently stored. Secondly, as in [8], the se- extensions: mantics of rules dictate that all reactant annotations should reside in the same location l, whereas product annotations can • In place of each element of a triple one can use a reside in l or in any neighbour of it. Since it is stored in a variable ?V (matching any value) or an annotated variable property, the location of an annotation (and hence, annotation ?V(filter) where filter is a predicate expression movement and diffusion) can be handled symbolically like over ?V: an annotated variable can match any value that any other property. Finally, we shall also assume that in each makes the filter true. As an example, ?V(?V>5) is such location there are some annotations (of type mid:#neigh, that ?V can be substituted by any number greater than 5. called neighbour annotations) specifically maintained by the Concerning filters, one can rely on any filter expression underlying infrastructure to keep track of neighbours. For as defined in SPARQL. We sometimes also use as special instance, the following annotation filter for a subject ?T an expression of the kind “?T clones ?R”, meaning that annotation ?T should have the :id314 mid:type mid:#neigh; mid:#loc :loc117; mid:remote :loc118; mid:distance "11.4"; er Quorum Sensing Chemotaxis Morphogenesis Lay mid:orientation "north-east" Top expresses that in node :loc117 there is the perception of er Lay BIO-CORE neighbour node :loc118, in north-east direction and at es- Gradient dle timated distance 11.4 (e.g., meters). Mid IV. T HE SELF - COMPOSITION ISSUE IN PERVASIVE SERVICE er Lay Evaporation Aggregation Spreading ECOSYSTEMS tton Bo Pervasive ecosystems naturally call for a radical shift in the way software is architected and developed. The concept of “software system” per se loses there its standard meaning of Fig. 2. Self-organising patterns and their relationships. a monolithically designed/implemented/deployed artifact. It is rather a mash-up of services, and the development of a “new software system” simply translates into the development of we consider a museum with a set of rooms connected by additional services to be immersed in a scenario of existing corridors, whose floor is covered with a network of computa- ones, with the goal of composing with them and evolving their tional devices (called sensor nodes). These devices exchange functionalities, thus making software live in a sort of “eternal information with each other based on proximity, have sensors beta” state [11]. of various kinds, and hold information as LSAs (e.g., about The natural questions we have to answer in order to support exhibits currently active in the museum). Visitors exploring this vision are hence: what can make services compose if the museum are equipped with a smartphone device that they were not explicitly designed to do so? how can we holds their preferences. By interaction with sensor nodes, a decide “whether” and “how” two or more services should visitor can be guided towards rooms with a target matching compose? how can such decisions be continuously recon- his/her interest, thanks to signs dynamically appearing on the sidered depending on the actual (spatial/temporal context) in smartphone or on public displays. This system is based on a which the composition is deployed? can we make multi-level gradient service, a key brick of self-organisation mechanisms composition seemingly work as well? (see Figure 2) that is typically designed to provide optimal We refer to this problem as the self-composition problem paths to roam a distributed system even in the context of very for service ecosystems, where by “self-” we mean that the un- articulated environments (a building with rooms and corridors, derlying middleware makes sure that services tend to compose or a traffic scenario) and by dynamically adapting (namely, in order to form meaningful new services, in a way that users self-healing) to unpredicted situations such as sudden road of the ecosystems simply perceive only atomic and composite interruption [8], [9]. Gradient starts from a source LSA located services that are actually useful in practice. at an exhibition and spreads clones of it to all the nodes of We argue that this vision cannot be fulfilled by the above- the network by eco-laws of spreading and aggregation, basic mentioned approaches taken in isolation, but instead require building patterns as shown in Figure 2. In turn, as the gradient them to work altogether. Advanced (semantic) matching of is stabilised, in each node the minimum distance value is kept, services is key to decide whether two services deployed by so that the shortest path to the source is automatically (and third parties can be composed together. Evolutionary ap- dynamically) defined [14]. In this way, a person willing to proaches seem the only solution to the problem of finely reach a point of interest simply “binds” to a gradient LSA, and tuning the parameters used in the composition, preselecting, public/private displays show signs to guide her to the source. for instance, a subset of more promising compositions. And However, other services exist in the system, such as those finally, competition of different compositions based on their provided by the many sensors available around. Among them actual exploitation appears instead as the only viable approach we have the crowd detection service, enacted by the injection to measure the quality of a composition, hence promoting in each node on the floor of a crowd LSA reporting the crowd successful ones. On the other hand, understanding how they level sensed there (0 is no crowd, 1 is maximum crowd). can work together in a comprehensive framework is very Another service is the one that, given visitor preferences and difficult, and generally depends on the specific platform and profile, defines a set of other possible points (exhibitions, service model one adopts. toilets, refresh points) the user can found interesting or useful. This service can be an external agent that is able to process A. Self-Composition with Gradient service visitor information, for instance defining related exhibitions, To ground our discussion of requirements and possible solu- so as to provide, in the form of an LSA, a list of best points the tions, we here outline a paradigmatic example of composition user can pass by. Then we can have sensors for temperature, in service ecosystems. We consider a crowd steering scenario, weather forecast, accelerometers etc. More generally, being a based on the idea of guiding people towards locations hosting pervasive system an open system, new services may appear events of interest in a complex and dynamic environment in the system, and autonomously be composed with existing (using semantic matching with people’s interests) without any ones, without a predefined schema. Only those compositions supervision, namely, in a self-organised way. In particular, that create useful services will then survive. To exemplify the idea, in the following we describe two self-composition agent. If services are not locally available, contextualisation problem we envisioned. does not happen and the distance value does not change. For 1) Crowd composition: This self-composition problem fo- instance, contextualise gradient with the crowd level perceived cuses on making the gradient service automatically compose in each location at the purpose of discouraging paths crossing to the crowd detection service so that the estimated distance crowded areas. It means that distance should be increased to the source gets “penalised” in case of a high crowd value, and function δ looks like δ = k ∗ c where k is a function which implies that the path computed towards a point of parameter (see later how to define its values), and c is the local interest intrinsically takes into account situations of crowded crowd level. The resulting effect is that the gradient service is areas dynamically emerging in the environment, properly available in the system in different forms (the basic one and circumventing them. In particular what we expect to the the composite ones). middleware to automatically do is: decide to compose the gradient with crowd sensing instead of with other (irrelevant Feedback. Each gradient owns a property called “satisfac- sensors), and optimally tune how much crowd information tion”, representing the feedback of users on the quality of should affect the computation of optimal path. the service itself. It can for instance evaluate the length of 2) Ad-hoc path composition: If the gradient service is the path, the interest and so on: the higher the value is, tagged with the point of interests crossed, it can be composed the higher is the user satisfaction. Once people reach the with the list of “best points” defined for each user, so that, source, they should then provide their feedbacks in the form in case of intersection, such gradient gets “reinforced” for of LSAs with predefined properties —such as length, comfort, instance diminishing its value, which then implies that the beauty, interest. Marks for each property might be defined in direction it comes from has more chance to be chosen, and a predefined range. From there one agent – or an application paths which cross points interesting or useful for the user are specific eco-law modelling the aggregation pattern – can then likely to be followed. In particular what we expect to the be in charge to compute the satisfaction value as a function of middleware to automatically do is: decide to compose the all the marks given – for instance, the average. The LSA of gradient with the LSA representing the “best points”, and the correspondent gradient source is then modified by adding optimally tune to which extent information on preferences to the previous value of the satisfaction property the last should affect the computation of optimal path. computed. This updated value is then spread in the whole B. A prototype solution system autonomously as a result of gradient diffusion. Starting from a number of services available in those nodes where sources of gradient services are located – all reified by Choice. Users, once entering in the system, can probabilisti- an LSA that can be injected in different parts of the system cally choose among the set of gradients available, grounding but via chemotaxis reach gradient sources – the solution we such decision mainly on the distance and satisfaction values. propose is based on the following mechanisms: They will then follow the same composition for the whole path. Composition. Based on one or more “composition recom- mender” agents available in source nodes, all the available Evaporation. The satisfaction value can also be interpreted compositions are computed using techniques of advanced as the relevance value of the Evaporation pattern [8]. This matching of interface/behaviour/ontology. These are ranked parameter gets decreased until fading if not augmented by – according for instance to feedbacks from the users on the user positive feedbacks. Once it is equal to zero the composite composite service, as discussed later – and the description of a service can be removed. This mechanism ensures that no limited number of them is reified in the space in the form of a satisfactory compositions are decayed. set of LSAs. In the example of crowd steering proposed above, these compositions should result in a set of LSAs representing the source of different gradients, each one created composing Evolution If parameters are to be chosen for the composition the basic gradient with one or more services. We assume that – for instance parameter k in δ = k ∗ c, representing how the composition actuated, i.e. which services are composed and much the crowd level has to influence the distance value of the which parameters are used in the composition, is stored into field –, they can be tuned by agents implementing evolutionary a property of the gradient LSA, so that the same composition techniques. They are in charge to define the new population can be performed in all the locations of the system of parameters according to the fitness function that can be computed from the satisfaction value of the gradient itself. Contextualisation. From the source, composite gradients and the basic one, are diffused. In each location they are contextu- The emergent idea is that, after a transition period, system alised with the local value of those services they are composed makes available only those services that better fit user prefer- by. Contextualisations involving gradients normally result in a ences. For instance, for those users interested in quickly reach modification of the local value of distance according to a func- the sources, only those gradients that ensure the lowest arrival tion δ specified in the service or defined by the composition time should survive. V. A FORMAL MODEL FOR GRADIENT be extracted. This rule leaves the reactants unchanged, but SELF - COMPOSITIONS creates a clone of ?GRAD with type ctx instead of diff, to To describe how self-composition of gradients can be built be relocated at ?L and indicating orientation (with respect in the pervasive ecosystem framework outlined in Section III, to originating location) ?O and distance ?D+?D2. Note that we first introduce the implementation schema for gradients continuous application of this rule at rate ?R makes copies which we shall rely upon to formalise the self-composition of the gradient annotation to be created and diffused in all task in the specific example of crowd service exploitation. neighbours. An annotation is relocated with type ctx, which forbids A. The gradient service further application of rule [DIFF]. This is because we first need Our strategy for modelling gradient features: (i) a con- to aggregate all incoming annotations before a new diffusion is tinuous broadcast of information in each node as in [3], scheduled. To do so, rule [CTX] defers change of type from with latter information always overwriting previous one; (ii) ctx to diff, which happens at rate ?RC (contextualisation propagation of estimated distance, computed by summing the rate). contributions given by property mid:distance in neighbour One form of aggregation is due to rule [YOUNGEST], annotation; (iii) propagation with no horizon (it is easy to used to refresh gradients with new information. It takes two impose a distance bound to the propagation of information); annotations such that the values associated to the aggregation and (iv) after been sent to a neighbour, an annotation is subject property ?P are the same, and retains the one with bigger to a contextualisation phase (in which e.g. aggregations are sos:step. The idea is that sos:aggr prop holds the name executed) before being spread again. of a property ?P which is expected to contain some value(s) Such rules are reported in Figure 3 and are described in that should be identical in two annotations for them to be turn. Note that they refer to namespace mid for URIs related aggregated. For instance, it could be the unique id of a to middleware activities, and to sos for those concerning self- gradient source, so that we do not aggregate annotations organisation aspects. coming from difference sources—but more involved situations Rule [PUMP] is a transformation rule which takes a source can be programmed as exemplified in next section. annotation and creates a new annotation with distance set Rule [SHORTEST] is similar: it takes two annotations with to 0, used to start the spreading process. The source anno- same step (hence coming from the same gradient annotation as tation should feature property sos:type assigned to value generated by rule [PUMP]), and retains the one with shortest sos:source (we shall say the annotation is of type source distance only if, again, they have same content of aggregation for brevity), and it should also have some value assigned to property. properties sos:aggr prop (the name of the property holding Finally, rule [DECAY] is used to remove an annotation at a the value used to aggregate other annotations as described given decay rate ?RD. This is useful as a cleanup mechanism below), sos:step (an incremental value used to refresh in the case a gradient source is removed from the system— information), sos:r diff (diffusion rate) and sos:r ctx though it plays no crucial role in this paper and will be (contextualisation rate). This rules fires at diffusion rate ?R: neglected in next discussions. according to CTMC semantics, this means that as soon as For the above rules to properly work we need to synthesise a matching set of reactant annotations is found, actual ap- a well-structured source annotation, featuring all required plication of the rule is delayed of a time t randomly drawn properties and proper values for rates—namely, diffusion rate according to a negative exponential distribution of probability is to be chosen to keep the system sufficiently reactive to with average value 1/?R—namely, it is fired at frequency changes without bloating the system with undesired messages, ?R. The effect of firing this rule is twofold: it increases the and contextualisation rate should be significantly higher than value of property sos:step of the source annotation, and diffusion rate (at least one order of magnitude). For instance creates (by cloning the source) a new annotation ?GRAD of we could use the following source annotation: type sos:diff and sos:aggr (original type sos:source is removed), and declaring distance 0 and orientation here with :id314 mid:#loc :loc117; sos:type sos:source; respect to the source—these properties will be update as the sos:step "0"; sos:sourceid "341AB2" sos:aggr_prop sos:sourceid; annotation is spread around. Note that the right-hand side of a sos:r_diff "10"; sos:r_ctx "100" rule mentions only changes in annotations, without any need of repeating information provided in the left-hand side which B. Rules for Gradient Composition has not changed: this allows a simpler structuring of rules with respect to more syntactic approaches like the one in [14]. According to the self-composition prototype solution out- Rule [DIFF] is used to diffuse a cloned version ?GRAD1 of lined above, we now explain how it can be operationally sup- a gradient annotation ?GRAD in one neighbour. The gradient ported in the framework explained in Section III, particularly annotation should be of type diff, declare distance ?D from for the example of gradient composition with crowd level. As the source and have diffusion rate ?R. This rule has as further an assumption, we formalise recommender agent behaviours reactant a neighbour annotation, from which information about with eco-laws, as if they operate via eco-laws they inject in a neighbour ?L with orientation ?O and distance ?D2 can the node. These eco-laws specify composition patterns. Transition Rules for Gradients [PUMP]: An annotation of type source continuously injects the initial gradient annotation ?SOURCE sos:type sos:source; sos:aggr_prop ?P; sos:step ?T; sos:r_diff ?R; sos:r_ctx ?RC --?R--> ?SOURCE sos:step =(?T+1) + ?GRAD(?GRAD clones ?SOURCE) sos:type -sos:source sos:diff sos:aggr; sos:dist "0"; sos:orientation "here" [DIFF] A gradient annotation is cloned in a neighbour, with distance increased and updated orientation ?GRAD sos:type sos:diff; sos:dist ?D; sos:r_diff ?R + ?NEIGH mid:type mid:#neigh; mid:remote ?L; mid:orientation ?O; mid:distance ?D2 --?R--> ?GRAD + ?NEIGH + ?GRAD1(?GRAD1 clones ?GRAD) sos:type -sos:diff sos:ctx; sos:dist =(?D+?D2); sos:orientation =?O; mid:#loc ?L [CTX] A contextualising annotation is transformed back into an annotation to be diffused ?GRAD sos:type sos:ctx; sos:r_ctx ?RC --?RC-> ?GRAD sos:type sos:-ctx sos:diff; [YOUNGEST] Of two annotations to be aggregated based on property ?P, the one with newest information is kept ?ANN1 sos:type sos:aggr; sos:aggr_prop ?P; ?P =[?C]; sos:step ?T1 + ?ANN2 sos:type sos:aggr; sos:aggr_prop ?P2; ?P2 =[?C]; sos:step ?T2(?T2 ?ANN1 [SHORTEST] Of two annotations to be aggregated based on property ?P, the one with shortest distance from source is kept ?ANN1 sos:type sos:aggr; sos:aggr_prop ?P; ?P =[?C]; sos:dist ?D1; sos:step ?T + ?ANN2 sos:type sos:aggr; sos:aggr_prop ?P2; ?P2 =[?C]; sos:dist ?D2(?D2>=?D1); sos:step ?T ---> ?ANN1 [DECAY] An annotation decays ?GRA sos:type sos:diff; sos:r_dec ?RD --?RD-> 0 Fig. 3. Rules for gradients Eco-laws for gradient composition [COMPOSITION] The gradient source is composed with the crowd service ?SOURCE sos:type sos:source; scm:satisfaction ?S + ?CROWD scm:type crowd; crowd:level ?CL ---> ?SOURCE + ?CSOURCE(?CSOURCE clones ?SOURCE) scm:property sos:dist; scm:parameters scm:crowd_op ?CF; scm:crowd_op ?CF*?CL [CONTEXTUALISATION] If sensors perceive crowd, the gradient distance is augmented ?GRAD sos:type sos ctx; sos:dist ?D; scm:property sos:dist; scm:parameters scm:crowd_op scm:crowd_factor; scm:crowd_factor ?CF; scm:crowd_op ?CF*?CL + ?CROWD scm:type crowd; crowd:level ?CL ---> ?CROWD + ?GRAD sos:type -sos:ctx sos:diff; sos:dist =(?D+?CF*?CL) [FEEDBACK] Feedbacks are used to update the satisfaction values ?FEEDBACK scm:parameters scm:crowd_op; scm:feedback scm:velocity; scm:velocity ?V + ?GRAD scm:satisfaction ?S; scm:parameters scm:crowd_op ---> ?GRAD scm:satisfaction =(?S+?V) [EVAPORATION] The gradient satisfaction value gets decreased ?GRAD scm:satisfaction ?S; scm:factor_ev ?FE; scm:r_ev ?RE --?RE-> ?GRAD scm:satisfaction =(?FE*?S) [DECAY] If the gradient satisfaction value becomes zero that composition is removed ?GRAD scm:satisfaction "0"; ---> Fig. 4. Additional rules for composition of gradients. Rule [COMPOSITION] in Figure 4, is in charge of creating crowd level perceived by sensors in each location. It increases the source of the composite gradient. The new source owns the distance of those paths crossing crowded area, if the the same set of properties of the basic one, as soon as it refers coefficient has an opportune value. Rule [CONTEXTUALISA- to the same PoI, but it also defines which properties are to TION] applies the composition specified in scm:parameters, be modified as an effect of the composition – sos:dist –, in each location of the system. Rule [FEEDBACK] is used to and which are composition parameters – scm:parameters – , modify the satisfaction value of gradient, taking into account i.e. function – scm:crowd op – to be used for modifying the the velocity of the path chosen. It can be computed by distance value, and coefficient —scm:crowd factor. In this the system itself, or provided by the user. The value of preliminary example we adopt a simple linear function of the scm:satisfaction gets increased by scm:velocity value. 5 k=0 4.5 k = 0.25 k = 0.5 4 k = 0.75 k=1 3.5 Satisfaction value 3 2.5 2 1.5 1 0.5 0 0 200 400 600 800 1000 1200 1400 1600 1800 2000 Time Fig. 5. Satisfaction values for different compositions changing over time. Rules [EVAPORATION] and [DECAY] are finally used best path each gradient proposes. This feedback is computed to evaporate the scm:satisfaction value according to an by each user once reached the target, given the length of the evaporation factor scm:factor ev ?FE in the range of path and the distance walked. [0,1] and to remove the gradient composition in case of a The goal is to observe that, satisfaction values, initially the scm:satisfaction value equal to zero, or negative, ensuring same for each composition, dynamically change according to that only those compositions that compute fast paths will feedbacks from the users, and only best compositions survive. survive. In Figure 5 such process is shown for different values of parameter k. The composition that wins is the one with VI. T OWARDS SIMULATION OF GRADIENT k = 0.75, while the other compositions decay. SELF - COMPOSITIONS VII. C ONCLUSION We checked the correctness of the proposed self- composition solution by simulation, conducted using A L - In this paper we propose a prototype solution for self- CHEMIST [14], a prototype simulator extending the typical composition of services in pervasive systems. An illustrative engine of a stochastic simulator for chemical reactions with model, framed in the pervasive ecosystem framework, is given. the ability of expressing structured reactions (namely, where It reproduces the composition of gradient service with ser- chemicals can have a tuple-like structure and reactions apply vices, distributed in the system, providing crowd level. Early by matching) and of structuring the system as a mobile experiments have been performed for validating the approach, networked set of nodes. Apart from performance issues – A L - and even though only a little set of compositions have been CHEMIST scales better than other simulators like Repast [13] considered, first results are promising. due to optimised data structures used to schedule chemical-like Future works are devoted to: (i) introduce evolutionary reactions [10] – A LCHEMIST simplifies the task of producing techniques for varying parameter k; (i) consider gradient correct simulations since there is a small abstraction gap composition with other services, such the ones already men- between simulation code and the proposed rule language. tioned previously in Section IV-A; (iii) generalise the approach Results presented show early experiments on gradient com- towards self-composition of all the possible services available position with crowd level, where people dynamically enter in in a pervasive system. the system and begin to move towards the target ascending one of the different compositions available. Movement velocity ACKNOWLEDGMENT is constant in the system, except for crowded areas, where This work has been supported by the EU-FP7-FET Proactive it decreases according to the crowd level perceived: higher project SAPERE Self-aware Pervasive Service Ecosystems, crowd, slower velocity. In these early experiments, parameter under contract no.256873 k in function δ is not computed dynamically through an evolutionary algorithm but composition agents define a set of R EFERENCES possible values. A new composition corresponds at each value. [1] Notation3 (n3): A readable rdf syntax. http://www.w3.org/ Users chose one gradient randomly but considering also the TeamSubmission/n3/, 2011. associated satisfaction value that measures the velocity of the [2] RDF primer. http://www.w3.org/TR/rdf-primer/, 2011. [3] J. Beal. Flexible self-healing gradients. In S. Y. Shin and S. Ossowski, editors, Proceedings of the 2009 ACM Symposium on Applied Computing (SAC), Honolulu, Hawaii, USA, March 9-12, 2009, pages 1197–1201. ACM, 2009. [4] J. Beal and J. Bachrach. Infrastructure for engineered emergence on sensor/actuator networks. IEEE Intelligent Systems, 21(2):10–19, 2006. [5] M. Beek, A. Bucchiarone, and S. Gnesi. A survey on service com- position approaches: From industrial standards to formal methods. In Technical Report 2006TR-15, Istituto, pages 15–20. IEEE CS Press, 2006. [6] A. A. Berryman. The origins and evolution of predator-prey theory. Ecology, 73(5):1530–1535, October 1992. [7] G. Canfora, M. Di Penta, R. Esposito, and M. L. Villani. An approach for qos-aware service composition based on genetic algorithms. In Proceed- ings of the 2005 conference on Genetic and evolutionary computation, GECCO ’05, pages 1069–1075, New York, NY, USA, 2005. ACM. [8] J. L. Fernandez-Marquez, G. Di Marzo Serugendo, S. Montagna, M. Vi- roli, and J. L. Arcos. Description and composition of bio-inspired design patterns: a complete overview. Natural Computing, May 2012. Online First. [9] J. L. Fernandez-Marquez, G. Di Marzo Serurendo, and S. Montagna. Bio-core: Bio-inspired self-organising mechanisms core. (to appear). In 6th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems (Submitted), 2011. [10] M. A. Gibson and J. Bruck. Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A, 104:1876–1889, 2000. [11] R. Kazman and H.-M. Chen. The metropolis model a new logic for development of crowdsourced systems. Commun. ACM, 52:76–84, July 2009. [12] M. Mamei and F. Zambonelli. Programming pervasive and mobile computing applications: The tota approach. ACM Trans. Softw. Eng. Methodol., 18(4):1–56, 2009. [13] M. J. North, T. R. Howe, N. T. Collier, and J. R. Vos. A declarative model assembly infrastructure for verification and validation. In Ad- vancing Social Simulation: The First World Congress, pages 129–140. Springer Japan, 2007. [14] D. Pianini, S. Montagna, and M. Viroli. A chemical inspired simu- lation framework for pervasive services ecosystems. In M. Ganzha, L. Maciaszek, and M. Paprzycki, editors, Proceedings of the Federated Conference on Computer Science and Information Systems, pages 675– 682, Szczecin, Poland, 18-21 September 2011. IEEE Computer Society Press. [15] N. Salazar, J. A. Rodriguez-Aguilar, and J. L. Arcos. Robust coordi- nation in large convention spaces. AI Communications, 23(4):357–372, 2010. [16] A. Seaborne and S. Harris. SPARQL 1.1 query. W3C working draft, W3C, Oct. 2009. http://www.w3.org/TR/2009/WD-sparql11- query-20091022/. [17] E. Sirin, B. Parsia, B. C. Grau, A. Kalyanpur, and Y. Katz. Pellet: A practical OWL-DL reasoner. Web Semant., 5:51–53, June 2007. [18] M. Viroli. A self-organising approach to competition and composition of pervasive services. Technical Report SAPERE TR.WP2.2011.4, 2011. [19] M. Viroli, E. Nardini, G. Castelli, M. Mamei, and F. Zambonelli. A coordination approach to adaptive pervasive service ecosystems. In IEEE International Conferences on Self-Adaptive and Self-Organizing Systems – Workskop AWARE 2011, 2011. [20] M. Viroli, D. Pianini, S. Montagna, and G. Stevenson. Pervasive ecosystems: a coordination model based on semantic chemistry. In S. Ossowski, P. Lecca, C.-C. Hung, and J. Hong, editors, 27th Annual ACM Symposium on Applied Computing (SAC 2012), Riva del Garda, TN, Italy, 26-30 March 2012. ACM. [21] Z. Wu, A. Ranabahu, K. Gomadam, A. Sheth, and J. Miller. Automatic composition of semantic web services using process and data mediation. In Proc. of the 9th Intl. Conf. on Enterprise Information Systems, pages 453–461, 2007. [22] F. Zambonelli and M. Viroli. A survey on nature-inspired metaphors for pervasive service ecosystems. International Journal of Pervasive Computing and Communications, 7(3):186–204, 2011.