=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards a Comprehensive Approach to Spontaneous self-composition in Pervasive Ecosystems
|pdfUrl=https://ceur-ws.org/Vol-892/paper1.pdf
|volume=Vol-892
|dblpUrl=https://dblp.org/rec/conf/woa/MontagnaVPF12
}}
==Towards a Comprehensive Approach to Spontaneous self-composition in Pervasive Ecosystems==
https://ceur-ws.org/Vol-892/paper1.pdf
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.