=Paper=
{{Paper
|id=None
|storemode=property
|title=A Simulation Framework for Pervasive Services Ecosystems
|pdfUrl=https://ceur-ws.org/Vol-741/ID15_PianiniViroliMontagna.pdf
|volume=Vol-741
|dblpUrl=https://dblp.org/rec/conf/woa/PianiniVM11
}}
==A Simulation Framework for Pervasive Services Ecosystems==
https://ceur-ws.org/Vol-741/ID15_PianiniViroliMontagna.pdf
A Simulation Framework for Pervasive Services
Ecosystems
Danilo Pianini Mirko Viroli Sara Montagna
DEIS–Università di Bologna DEIS–Università di Bologna DEIS–Università di Bologna
via Venezia 52, 47521 Cesena, Italy via Venezia 52, 47521 Cesena, Italy via Venezia 52, 47521 Cesena, Italy
Email: danilo.pianini@unibo.it Email: mirko.viroli@unibo.it Email: sara.montagna@unibo.it
Abstract—This paper grounds on the SAPERE project (Self- works propose ad-hoc solutions to specific problems in specific
Aware PERvasive Service Ecosystems), which aims at proposing areas, and lack generality.
a multi-agent framework for pervasive computing, based on the The SAPERE project (“Self-adaptive Pervasive Service
idea of making each agent (service, device, human) manifest
its existence in the ecosystem by a Live Semantic Annotation Ecosystems”) addresses the issues related to spatiality, spon-
(LSA), and of coordinating agent activities by a small and fixed taneous and opportunistic coordination, self-adaptation and
set of so-called eco-laws—sort of chemical-like reactions over self-management, in a uniform way by means of a truly
patterns of LSAs. System dynamics in SAPERE is complex self-adaptive pervasive substrate; this is a space bringing
because of opennes and due to the self-* requirements imposed to life an ecosystem of individuals, namely, of pervasive
by the pervasive computing setting: a simulation framework
is hence needed for what-if analysis prior to deployment. In services, devices, and humans. These are coordinated in a self-
this paper we present a prototype simulator we are developing, organising way by basic laws (called eco-laws), which evolve
tested on a crowd steering scenario. Due to the role of chemical- the population of individuals in the system, thus modelling
like dynamics, this is based on a variation of an existing SSA diverse mechanisms of coordination, communication, and in-
(Stochastic Simulation Algorithm), suitable tailored to the specific teraction. Technically, such eco-laws are structured as sort of
features of SAPERE, including dynamicity of network topology,
pattern-based application of eco-laws, and temporal triggers. chemical reactions, working on the “interface annotation” of
components residing in neighbouring localities—called LSA
I. I NTRODUCTION AND M OTIVATION (Live Semantic Annotation).
In this context models and simulation can be useful in
The increasing evolution of pervasive computing is promot- supporting the design of pervasive systems. They give the
ing the emergence of decentralised and complex infrastructures possibility to experiment the idea of exploiting bio-inspired
for pervasive services composed by new communication de- ecological mechanisms, showing through simulation the over-
vices (e.g. mobile phones, PDA’s, smart sensors, laptops). Such all behaviour of a system designed on top of eco-laws, as
infrastructures include traditional services with dynamic and well as to elaborate what-if scenarios. To capture the whole
autonomous context adaptation (e.g., public displays show- complexity of the SAPERE approach the model has to support
ing information tailored to bystanders), as well as innova- the abstraction of (i) highly dynamic environment composed of
tive services for better interacting with the physical world different, mobile, communicating nodes and (ii) autonomous
(e.g., people coordinating through their PDAs). The common agents. They might be programmable through a set of chemical
languages and software infrastructures are often inadequate rules.
to face requirements of scalability, openness, adaptivity and On one hand the adoption of the Agent-based Models
self-organisation typical of pervasive systems. In order to (ABM) [15] seems to be quite natural as soon as the pervasive
better handle these scenarios, a paradigm shift towards agent system itself is engineered adopting the agent paradigm. There
world is receiving more and more attention in the scientific are several works which apply this approach in different con-
community. They support the realisation of distributed and texts, from social systems (see, e.g., [3]) to biological systems
eventually communicating environments where different kind [18], [4]. An ABM grounds around autonomous and possibly
of autonomous entities, the agents, are located. Agents can heterogeneous agents that can be situated in an environment.
sense and change the environment and can interact with other They carry out the most appropriate line of action, possibly
agents. In particular one of the research topics about agents interacting with other agents as well as the environment itself.
regards coordination, namely the way they can produce, con- The agent behaviour is modelled through a set of rules which
sume and exchange information inside the pervasive system. describe how the agent behaves according to environmental
Different approaches were proposed in the area of coor- conditions. These rules can be of different types, according to
dination models and middlewares for pervasive computing the specific model / architecture: from the simple reactive rules
scenarios: they try to account for issues related to spatiality – specifying how the agent must react to environmental stimuli
[16], [20], spontaneous and opportunistic coordination [2], or perceptions – or pro-active —specifying how the agent must
[9], self-adaptation and self-management [23]; however, most behave with respect to its goals and tasks [31]. Therefore ABM
does not normally provide a way to define the behavioural The usual way chemical systems are studied is through dif-
rules in terms of chemical laws. In ABM the environment ferential equations describing how the concentration of each
is also a first class abstraction whose structure, topology and molecule continuously varies with time. In such a description
dynamic can be explicitly modelled. To develop and simulate the system evolution caused by a reaction is modelled through
ABMs different simulation frameworks have been developed, a continuous variable – the concentration – while it is an event
such as MASON [14], [28], Repast [21], [26], NetLogo [30], that changes a discrete variable—the number of molecules in
[24], [32] and Swarm [27]. the system. This approximation is largely acceptable in most
On the other hand considering pure chemical simulators systems, where millions of molecules of each kind are involved
with stochastic extension, such as BioPEPA [7] and BetaWB simultaneously, but it’s no longer accurate when only few
[8], helps for explicitly model the eco-laws. In this field few molecules are present inside the system. In order to correctly
simulators allow to define a multi-compartment topology [1], represent this situation, a stochastic model has been proposed
and to the best of our knowledge no one provides facilities in [11]. The whole system is described through a single master
to move them inside an external environment. Moreover, all equation that calculates the probability that at a given time
compartments are subject to the same set of laws, which are t the concentration of a reactant Xi is equal to a number
chemical reactions. Ki . Solving this equation is infeasible for every non-trivial
To take the best of both approaches we developed a brand problem, but its evolution can be analysed through stochastic
new simulation framework, called A LCHEMIST, meant to face model checking [6], [12], running series of Monte Carlo
natively the model requirements. It implements an optimised simulations each one describing a possible path, exploiting the
version of the Gillespie’s SSA, namely the Next Reaction useful property that the probability for the simulation to run
Method [10], extended with the possibility to have dynamic through a specific path is the probability of the path itself. This
reactions, i.e. reactions that can be added or removed once the kind of description considers the whole system as a CTMC, in
simulation runs. which the rate of the transaction representing the i-th reaction
A notable application of the proposed approach is in crowd is the propensity function ai .
steering applications, in which a crowd is guided in a pervasive In [11], two algorithms are proposed in order to correctly
computing scenario depending on unforeseen events, such simulate a stochastic path of a chemical system. Those algo-
as the occurrence of critical events (i.e. alarms) and the rithms were successively improved, but every algorithm, even
dynamic formation of jams. We exemplify the approach in the optimized versions, relies on the idea that the system can
a crowd evacuation scenario, providing its set of eco-laws and be simulated by effectively executing the reactions one by one
validating it via simulation of the associated Continuos-Time and changing the system status accordingly. Every algorithm
Markov Chain (CTMC) model. follows four main steps:
The remainder of this paper is organised as follows: Sec- 1) select the next reaction µ to be executed;
tion II presents details about the computational model we 2) calculate the time of occurrence of µ according to an
defined and the simulator engine, Section III reports the exponential time distribution and make it the current
application of the simulator in a crowd steering scenario and simulation time;
Section IV provides concluding remarks and discusses future 3) change the environment status in order to reflect this
works. execution;
II. E NGINE A RCHITECTURE 4) update the propensities of the reactions.
The known techniques differ in the implementation of first and
In this section we first introduce how to model a chemical
fourth steps. We will briefly present them and then justify our
system in both deterministic and stochastic ways, then we
choice for the engine.
show the known algorithms for stochastic simulation and our 1) Direct Method: The direct method was first proposed in
choices for a full featured high performance engine. [11]. It chooses the nextPreaction to be executed by throwing
A. Stochastic Simulation Algorithms a random number r 6 i ai and selecting Pµthe first reaction
A chemical system can be modelled as a single space µ which verifies the property that r > i=0 ai . After the
filled with molecules that may interact through a number execution of µ, it updates propensities for each reaction.
of reactions describing how they combine. The instantaneous 2) Optimized Direct Method: The direct method can be
speed of a reaction is called propensity and depends on the optimised as proposed in [10] and [29] by introducing a binary
kinetic rate of the reaction and on the concentrations of all the search tree and a dependency graph. The former allows to
reagents involved. For a reaction i with k reactants, j products, choose the next reaction µ to be executed in logarithmic time,
stoichiometric coefficients of the i-th reaction expressed as ni the latter to update only the propensities of those reactions in
and rate r of the form: which concentration of regents is modified by the execution
of µ.
r
n0 R0 + n1 R1 + . . . + nk Rk −
→ m0 P0 + m1 P1 + . . . mj Pj 3) Composition-Rejection Method: In [25] a constant time
method relying on composition-rejection algorithm is pro-
The propensity ai is defined as in equation 1:
posed. The separation between the number of reactions R and
ai = r · R0n0 · R1n1 · . . . · Rknk (1) the computational complexity of the algorithm is obtained by
splitting the whole set of reactions into G groups, and then 2.0
arguing that G does not depend (or depends loosely) by R. 4 4
It may rely on a dependency graph in order to improve the
update phase. 3.7 7.3
2 1 2 1
4) First Reaction: The First Reaction Method is the dual
form of the Direct Method, and was proposed first in [11]. The
key idea is to calculate immediately the time of occurrence for 5.5 4.2 8.9 9.1
1 0 0 0 1 0 0 0
each reaction and select the next one using the lowest time.
It is demonstrably the same of the Direct Method both in
soundness and in time complexity. 10.1 inf
0 0 0 0
5) Next Reaction: The Next Reaction Method is an opti-
mised form of the First Reaction Method first proposed in [10]. Fig. 1. Indexed Priority Queue extended with children count per branch
It relies on an Indexed Priority Queue (IPQ) in order to smartly
sort the reactions by time, has constant time in the selection
phase since the root of the IPQ is always the next reaction to
execute. This algorithm requires the calculation of the times Third, we want to deal with events whose occurrence time
for each reaction at every update, but a dependency graph can does not follow an exponential law, for instance triggers,
be used, and the random re-usage is justified, speeding up namely events which happen at a specific time regardless
consistently the times recalculation. the previous evolution of the system. A simple example of
simulation requiring triggers could be the simulation of a
failure of a server in a cloud computing system: who writes the
B. Computational Model
simulation has to set the failure event at a specific time, then
Before start discussing about our engine, we describe the run multiple simulations in order to understand how the system
computational model we propose in order to close the gap will react. Another usage of triggers appears when considering
between the SAPERE world and the chemical simulators. In the possibility to interact with a running simulation pausing
fact, these requirements will influence some aspects of the it and, exploiting triggers, interact with the environment in
engine itself. its current status, then resume the simulation. Even if this
Our model improves the classic model of chemical reactions approach is not useful when the goal is to check the properties
in three main directions, introducing the concepts of envi- of a model, it could be very handy when exploring and
ronments, nodes and neighbourhoods; extending the concept testing it for the first times, because it allows the user to
of classical chemical reaction as a set of conditions whose have an immediate feeling on how his model reacts to some
validity may cause the execution of a set of actions and modifications.
supporting time fixed events.
First, in the classic chemical model, the environment is a C. Dynamic engine
single compartment that contains the molecules. This descrip- Given the model we want to simulate described in Sec-
tion is pretty far from the world we want to model, which tion II-B and the algorithms presented in Section II-A, we can
is a pervasive service ecosystem. The natural extension is argue that no existing algorithm as-is is appropriate to allow
to consider many compartments (nodes) placed in a space our simulations. In particular, no algorithm provides facilities
(environment) which is responsible of linking them. Depend- to add and remove reactions dynamically, and moreover it
ing on the specific environment, nodes can be dynamically appears to be hard to inject the concept of trigger in direct
added, moved or removed. A neighbourhood is consequently method or its optimizations because they lack the possibility
a structure which contains a node “centre” and a list of all to choose the next reaction to execute considering immediately
linked compartments. its time of occurrence. Our choice for the engine algorithm
Second, in classical chemical model, a reaction lists a to extend was then restricted between the First Reaction
number of reactant molecules which, combined, produce a set and the Next Reaction. The latter is an optimization of the
of product molecules. This kind of description is too strict former, offers a lower computational complexity in every case
for our purposes. A more generic concept is to consider a and consequently can achieve higher performance. Our work
reaction as a set of conditions about the environment which, had the primary goal to extend Next Reaction providing the
when matched, may allow the execution of a set of actions. A possibility to add and remove reactions dynamically, since to
condition is a function which associates a boolean to each the best of our knowledge no work in this sense have been
status of the environment, an action is a procedure which ever made. In order to add this support, it is a mandatory
modifies it. The propensity function can no longer be simply task to provide methods to add and remove reactions from the
the product of the reaction rate with the concentrations of the indexed priority queue and the dependency graph.
reactants, but needs a more generic definition too: propensity 1) Dynamic Indexed Priority Queue: A key property of the
in our model is a function of the reaction rate, the conditions original Indexed Priority Queue proposed in [10] is that the
and the environment status. swap procedure used to update the data structure does not
Core Engine
changes the balancing of the tree, ensuring optimal update
times in every situation. This feature was easily achieved
Reaction Manager Reporting System
because no new nodes were ever added neither old ones were
removed from the structure, as a consequence, once the tree
Simulation Flow Interactive UI
is created balanced no event can occur to change its topology.
This is no longer the case, and we have to provide a small
extension to the structure in order to manage the balancing. Dependency Graph Environment
Our idea is, for each node, to keep track of the number of
children per branch, having in such way the possibility to keep
the tree balanced when adding nodes. In figure 1 we show how
the same IPQ drawn in [10] would appear with our extension. Language Parser
In the following algorithms, the procedure UPDATE_AUX(n) Environment Instantiator
is the same described in [10]. Given this data structure, the
procedure to add a new node n is the following:
IF root does not exists XML Bytecode
n is the new root
ELSE
c <- root
WHILE c has two children Application-specific Alchemist Bytecode Compiler
IF c.right < c.left
dir <- right
ELSE
dir <- left Environment description in application-specific language
next <- dir children
add 1 to count of c.dir
c <- next Fig. 2. A LCHEMIST architecture. Elements drawn with continuous lines
IF c has no left child indicates components common for every scenario and already developed,
n becomes left child of c those with dotted lines are extension-specific components which have to be
set count of left nodes of c to 1 developed with the specific application in mind.
ELSE
n is right child of c
set count of right nodes of c to 1
UPDATE_AUX(n)
• r1’s output context is global OR
The removal procedure for a node n is the following: • r2’s input context is global OR
• r1’s output context and r2’s input context are both
c <- root
WHILE c is not a leaf neighborhood and the node which r1 belongs to is
IF c.left > c.right a neighbour of the node which r2 belongs.
c <- c.left
ELSE Given this handy function, we can assert that a dependency
c <- c.right exists between the execution of a reaction r1 and another
IF c != n
swap c and n
reaction r2 if mayInfluence(r1,r2) is true and at least
delete n a molecule whose concentration is modified by r1 is among
UPDATE_AUX(c) those influencing r2.
ELSE
remove n Adding a new reaction implies to verify its dependencies
against every reaction of the system. In case there is a depen-
Using the two procedures described above, the topology of dency, it must be added to the graph. Removing a reaction r
the whole tree is constrained to remain balanced despite the requires to delete all dependencies in which r is involved both
dynamic addition and removal of reactions. as influencing and influenced. Moreover, in case of change
2) Dynamic Dependency Graph: Since we want to support of the system topology which, a dependencies check among
natively and efficiently the multiple compartments, we defined reactions belonging to nodes with modified neighbourhood is
three contexts (also called scopes): local, neighborhood needed. It can be performed by scanning them, calculating
and global. Each reaction has an input context and an output the dependencies with the reactions belonging to new neigh-
context, meaning respectively where data influencing the rate bours and deleting those with nodes which are no longer in
calculus is located and and where the modifications to the neighbourhood.
environment are made.
The first issue to address is to evaluate if two reactions may D. Engine architecture
influence each other, considering their contexts. We introduce The whole framework has been designed to be fully modular
a boolean procedure called mayInfluence(r1, r2) that and extensible. The whole engine or parts of it can be re-
operates on two reactions and returns a true value if: implemented without touching anything in the model, and
• r1 and r2 are both on the same node OR on the other hand the model can be extended and modify
without messing with engine. This modularity will make it In the SAPERE flavour, all the information exchanged is
easy to make some experiments with other engines, such as in form of Live Semantic Annotations, and the rules are
Composition-Rejection. expressed in form of eco-laws. An LSA is simply modelled as
The framework was effectively developed using Java. Being a tuple hv1 , . . . , vn i (ordered sequence) of typed values, which
performances a critical issue for a simulator, we compared could be for example numbers, strings or structured types.
some common languages in order to evaluate their perfor- Although in the SAPERE framework LSAs are semantic an-
mance level. Surprisingly, Java performance are at same level notations, expressing information with same expressiveness of
of compiled languages such as C/C++ [5], [22]. The Java lan- standard frameworks like RDF, we here consider a simplified
guage was consequently chosen because of the excellent trade notation. There are three forms of LSAs used in this scenario:
off among performances, easy portability and maintainability
of the code, plus the support for concurrent programming hsource, type, max, anni
at language level. The COLT Java library [13] provided us hgrad, type, value, max, anni
the mathematical function we need. In particular, it offers a hinfo, type, value, tstampi
fast and reliable random number generation algorithm, the so A source LSA is used for gradient sources: type indicates
called Mersenne Twister [17]. the type of gradient (fire, exit, and crowd); max is the
As shown in figure 2, at the current status of development gradient’s maximum value; and ann is the annealing factor—
the simulations are written in a specific XML language which its purpose will be described later, along with eco-laws. A
is interpreted in order to produce an instance of an environ- gradient LSA is used for individual values in a gradient:
ment. Once the environment is created, no further interpreta- value indicates the individual value; and the other parameters
tion of the code is needed in order to run the simulation. This are like in the source LSAs. Finally, an info LSA is used for
XML code is not meant to be directly exploited by users, but local values (e.g., not part of a gradient)—parameters are like
it represents a way to describe environments in a machine- in the source and gradient LSAs. The tstamp reflects the time
friendly way and is a formalisation of the generic model of of creation of the LSA.
A LCHEMIST. The idea behind this choice is that A LCHEMIST The sources of the gradients are injected by sensors when an
is flexible enough to be used in various contexts, each one exit, a fire or a number of persons is perceived, with the val-
requiring a sightly different instantiation of the model and its ues hsource, exit, Me, Aei and hsource, fire, Mf, Afi. For
own language. It’s up to the extensor to write a translation the crowding information, we may assume that sensors are
module from its personalised language to the A LCHEMIST calibrated so as to locally inject an LSA indicating the level of
XML. crowding, i.e. the number of persons. The crowding LSA will
look like hsource, crowd, Mc, Aci and is periodically updated
III. C ASE STUDY by the sensor.
We propose a crowd evacuation scenario as a case study. An eco-law is a chemical-resembling reaction working over
Imagine a museum with a large room, whose floor is covered patterns of LSAs. One such pattern P is basically an LSA
with a sensor network, and an external corridor with two exits. which may have some variable in place of one or more
A number of visitors are inside the main room, each one arguments of a tuple, and as usual an LSA L is said to match
equipped with a PDA that can guide the visitor towards the exit the pattern P if there exists a substitution of variables which
in case of emergency. Sensors may perceive the presence of applied to P gives L. In Figure 3, the eco-laws for our case
doors, fires and persons. When an emergency appears, PDAs study are given.
must show the direction towards an exit, along a safe path. The As sources are established, gradients are built by the first
system has to be resilient to changes or unpredicted situations, two rules in Figure 3. The former, given a source, initiates its
in particular the safe path must consider: gradient; the latter, when a node contains a gradient LSA,
• distance: it should tend to lead to the nearest exit; spreads it to a neighbouring node with an increased value
• fire: it should tend to stay away from fire; proportional to the distance between sensors indicated by the
• crowd: it should tend to avoid overcrowded paths. variable #D. As a consequence of these laws, each node
will carry a grad LSA indicating the topological distance
A. A SAPERE model from the source. When the spread values reach the maximum
The environment models the network of sensors. Each vale M , the gradient becomes a plateau. The spreading eco-
sensor is a node of the network. PDAs are agents dynamically law above may produce duplicate values in locations (due to
linked with the nearest sensors – the neighbours are the sensors multiple sources, multiple paths to a source, or even diffusion
inside a certain radius r, parameter of the model – from which of multiple LSAs over time). Thus, the third eco-law retains
they can retrieve data in order to suggest visitors where to go. only the minimum distance. Finally, we have to address the
Visitors are agents which tend to follow the advices of the dynamism of the scenario where people move, fires extinguish,
PDA. They can move of discrete steps inside the environment, exits may be blocked, crowds form and dissolve. If a gradient
but there must be a physical limit in the minimum distance source vanishes, the diffused values should increase (e.g., the
between them, since two visitors can’t be in the same place distance to exit increases if the nearest exit is no longer
at the same time. available). This is the purpose of the annealing parameter in
R
hsource, T, M, Ai 7−−init
−→ hsource, T, M, Ai, hgrad, T, 0, M, Ai
R s
hgrad, T, V, M, Ai 7−−→ hgrad, T, V, M, Ai, +hgrad, T, min(V +#D, M ), M, Ai
hgrad, T, V, M, Ai, hgrad, T, W, M, Ai → hgrad, T, min(V, W ), M, Ai
Rann (A)
hgrad, T, V, M, Ai 7−−−−−−→ hgrad, T, V +1, M, Ai
R
hgrad, exit, E, Me, Aei, 7−−att
−→ hgrad, exit, E, Me, Aei, hgrad, fire, F, Mf , Af i,
hgrad, fire, F, Mf , Af i, hinfo, crowd, CR, TS i,
hinfo, crowd, CR, TS i hinfo, attr, (Me − E)/(1 + (Mf − F ) + k × (Mc − C)), #T i
hinfo, attr, A, TS i, hinfo, attr, A2 , TS +T i → hinfo, attr, A2 , TS +T i
Rdisp (∆)
hinfo, escape, Li, hinfo, attr, A, T Si, 7−−−−−−→ hinfo, escape, #Oi, hinfo, attr, A, T Si,
+hinfo, attr, A+∆, T S2i +hinfo, attr, A + ∆, T S2i
Fig. 3. Eco laws.
...
...
...
Fig. 4. Alchemist XML code snipped of the case study, with the translation of the first eco-law.
the gradient LSAs: it defines the rate of fourth eco-law, which value automatically attached to each node by fifth eco-law.
continuously tends to level up gradient values, encouraging Coefficient k (tuned by simulation) is used to weight the
the replacement of old values by more current ones. The Rann effect on crowding on attractiveness. As gradients evolve, older
rate is directly proportional to A. When a fire is put out, for attractiveness LSAs are replaced with newer ones with seventh
example, this eco-law will gradually raise the fire gradient to eco-law (T is assumed positive).
the point where it reaches the maximum, indicating no fire.
Annealing may introduce a burden on the system, therefore Each location contains by default an LSA of the form
high annealing values should only be used for gradients that hinfo, escape, L, TS i, where L is the direction to be sug-
have to change often or quickly. gested by the PDA. In principle, the neighbour with the highest
attractiveness should be chosen, but a more resilient solution
Based on exit distance, fire distance and crowding, a is to tie the markovian rate of eco-laws to the attractiveness of
location can be ranked as more or less “attractive” to be neighbours, so that the highest probability is to point the best
part of an escape path. This is done via an attractiveness neighbour, with a possibility to point a less-than-optimal (but
800
50
700
100
225
600
500
Time exit [sec]
400
300
200
100
Fig. 5. A simulation run of the reference exposition: three snapshots of the
0
A LCHEMIST graphic reporting module with this simulation 0 0.1 0.2 0.3 0.4 0.5
k
0.6 0.7 0.8 0.9 1
Fig. 6. Results of the k parameter analysis.
still attractive) neighbour, as described by the last eco-law. The
rate is proportional to the difference in attractiveness between
the node and its neighbour (∆). The higher the ∆, the higher
the rate. Note that ∆ is a positive value, hence A + ∆ implies
that the last eco-law only considers neighbours with a higher
attractiveness, i.e., the PDA will not point away from the exit.
The proposed architecture is intrinsically able to dynami-
cally adapt to unexpected events (like node failures, network
isolation, exits suddenly unavailable, crowd formation, and so
on) while maintaining its functionality.
More details about the model of the case study are given in
[19].
B. Simulator configuration
The behaviour of each agent is programmed according to the
eco-laws coordination model explained in Figure 3. We here Fig. 7. Gradients for the snaphots in Figure 5. Concentration is the gradient
present simulations conducted over an exposition structured as value normalised to its maximum value.
shown in Figure 5, where three snapshots of a simulation run
are reported: all the people in the room start moving towards
one of the two exists (located at the ends of the corridor) feature is exploited to optimize the parameter k, finding out
because of the fire in the top-right corner of the room. Note how to fix it in the fifth reaction of Figure 3 in order to grant
in third snapshot that a person is walking in the middle of the a low exit time in different cases. We tested it with 50, 100
corridor, for she was suggested to go to a farther exit because and 225 visitors. Results are shown in Figure 6.
of the corridor jam at the bottom-right. Rooms and corridors Figure 7 shows the gradients of exit, fire, crowding and at-
are covered by a grid of locations hosting sensors, one per tractiveness (one per column) corresponding to the simulation
meter in the room, one per two meters in the corridor: such steps of Figure 5 (one step per row). At t = 0, gradients
locations are the infrastructure nodes where LSAs are reified. are level; with time, the gradient self-modify—it is easy to
The maximum values for the gradients are set to: Me = 30, see the exits, fire and crowds in the respective gradients. The
Mf = 3, Mc = 20. The PDA of each person is modelled as crowding gradient in the third column changes dynamically
a mobile node, able to perceive the attractiveness gradient in during simulation according to the movement of people. The
the nearest sensor locations: accordingly, the person moves in last column shows the attractiveness gradient, computed from
the suggested direction. the other three gradients. Note how the second snapshot shows
Each eco-law in Figure 3 is modeled inside the simulator an attractiveness “hole” in the middle of the room and in the
as a reaction. The behaviour of visitors is a reaction too, corridor due to crowding.
featuring a special action in which the behaviour of the visitors
is expressed. IV. C ONCLUSION
Through this scenario many innovative aspects of A L - In the SAPERE metaphor, the ideal level of abstraction
CHEMIST can be stressed: we have mobile compartments, a to reach in order to easily and correctly model and simulate
triggers (which are exploited in order to set up fire), dynami- pervasive systems stands between the ABM and biochemistry-
cally changing neighbourhoods and a pretty rich scenario with oriented simulators. In this work we shown the A LCHEMIST
up to 316 nodes moving inside and exiting an environment simulation framework, meant to fully support this way to think
with physical obstacles. pervasive systems. This framework embraces the SAPERE
vision and allows to approach the simulation of agent systems
C. Parameter tuning and simulation results in a new flavour, describing the system in terms of reaction-
A LCHEMIST offers full support to run concurrently multiple like laws and having consequently the possibility to rely on all
simulations in order to tune parameters. In this scenario this the work already made about CTMC. We shown a case study
whose complexity overcomes the expressiveness possibility of [16] M. Mamei and F. Zambonelli. Programming pervasive and mobile
classical biochemistry-oriented simulation frameworks, and we computing applications: The tota approach. ACM Trans. Softw. Eng.
Methodol., 18(4):1–56, 2009.
analysed it exploiting the same CTMC mathematical support. [17] M. Matsumoto and T. Nishimura. Mersenne twister: A 623-
Perspectives for the immediate future include a comparison dimensionally equidistributed uniform pseudo-random number genera-
in terms of performance and expressiveness with the ABM tor. ACM Trans. Model. Comput. Simul., 8(1):3–30, 1998.
[18] S. Montagna, N. Donati, and A. Omicini. An agent-based model for
simulation frameworks, such as Repast and NetLogo, and the the pattern formation in Drosophila Melanogaster. In H. Fellermann,
analysis, modelling and simulation of further scenarios, with M. Dörr, M. M. Hanczyc, L. Ladegaard Laursen, S. Maurer, D. Merkle,
different types of complexity so to stress the potentialities of P.-A. Monnard, K. Stoy, and S. Rasmussen, editors, Artificial Life XII,
chapter 21, pages 110–117. The MIT Press, Cambridge, MA, USA,
A LCHEMIST. Future work are also devoted to theoretically 2010. Proceedings of the 12th International Conference on the Synthesis
compare the CTMC model with the Discrete Event Simulation and Simulation of Living Systems, 19-23 Aug. 2010, Odense, Denmark.
approach at the simulation, normally adopted in the ABM [19] S. Montagna, M. Viroli, M. Risoldi, D. Pianini, and G. Di Marzo Seru-
gendo. Self-organising pervasive ecosystems: A crowd evacuation
simulators. example. 29-30 September 2011. Submitted at the 3rd International
Workshop on Software Engineering for Resilient Systems.
ACKNOWLEDGMENT [20] A. L. Murphy, G. P. Picco, and G.-C. Roman. Lime: A model and
middleware supporting mobility of hosts and agents. ACM Trans. on
This work has been supported by the EU-FP7-FET Proactive Software Engineering and Methodology, 15(3):279–328, 2006.
project SAPERE Self-aware Pervasive Service Ecosystems, [21] M. J. North, T. R. Howe, N. T. Collier, and J. R. Vos. A declarative
under contract no.256873 model assembly infrastructure for verification and validation. In S. Taka-
hashi, D. Sallach, and J. Rouchier, editors, Advancing Social Simulation:
The First World Congress, pages 129–140. Springer Japan, 2007.
R EFERENCES [22] B. Oancea, I. G. Rosca, T. Andrei, and A. I. Iacob. Evaluating java
[1] R. Alves, F. Antunes, and A. Salvador. Tools for kinetic modeling performance for linear algebra numerical computations. Procedia CS,
of biochemical networks. Nature Biotechnology, 24(6):667–672, June 3:474–478, 2011.
2006. [23] P. V. Roy, S. Haridi, A. Reinefeld, J.-B. Stefany, R. Yap, and T. Coupaye.
[2] M. Autili, P. Benedetto, and P. Inverardi. Context-aware adaptive Self-management for large-scale distributed systems: an overview of the
services: The plastic approach. In FASE ’09 Proceedings, pages 124– selfman project. In Formal Methods for Components and Objects, LNCS
139, Berlin, Heidelberg, 2009. Springer-Verlag. No. 5382, pages 153–178. Springer Verlag, 2008.
[3] S. Bandini, S. Manzoni, and G. Vizzari. Crowd Behavior Modeling: [24] E. Sklar. Netlogo, a multi-agent simulation environment. Artificial Life,
From Cellular Automata to Multi-Agent Systems. In A. M. Uhrmacher 13(3):303–311, 2007.
and D. Weyns, editors, Multi-Agent Systems: Simulation and Appli- [25] A. Slepoy, A. P. Thompson, and S. J. Plimpton. A constant-time kinetic
cations, Computational Analysis, Synthesis, and Design of Dynamic monte carlo algorithm for simulation of large biochemical reaction
Systems, chapter 13, pages 389–418. CRC Press, June 2009. networks. The Journal of Chemical Physics, 128(20):205101, 2008.
[4] G. Beurier, F. Michel, and J. Ferber. A morphogenesis model for [26] R. D. Team. http://repast.sourceforge.net/. Repast home page.
multiagent embryogeny. In L. M. Rocha, L. S. Yaeger, M. A. Bedau, [27] S. D. Team. http://www.swarm.org/index.php/Main Page. Swarm home
D. Floreano, R. L. Goldstone, and A. Vespignani, editors, Artificial Life page.
X: Proceedings of the Tenth International Conference on the Simulation [28] G. M. University. http://www.cs.gmu.edu/\∼eclab/projects/mason/.
and Synthesis of Living Systems, pages 84–90. MIT Press, Cambridge, MASON home page.
MA, 2006. [29] C. Versari and N. Busi. Efficient stochastic simulation of biological
[5] J. M. Bull, L. A. Smith, C. Ball, L. Pottage, and R. Freeman. systems with multiple variable volumes. Electr. Notes Theor. Comput.
Benchmarking java against c and fortran for scientific applications. Sci., 194(3):165–180, 2008.
Concurrency and Computation: Practice and Experience, 15(3-5):417– [30] U. Wilensky and CCL. http://ccl.northwestern.edu/netlogo/index.shtml.
430, 2003. NetLogo home page.
[6] M. Casadei and M. Viroli. A framework to specify and verify computa- [31] M. Wooldridge. An Introduction to MultiAgent Systems. John Wiley &
tional fields for pervasive systems. ACM Transactions on Autonomous Sons, 1st edition, June 2002.
and Adaptive Systems, 2010. [32] S. Yildirim, G. L. Dam, and J. C. Houk. The mind agents in netlogo
[7] F. Ciocchetta and M. L. Guerriero. Modelling biological compartments 3.1. In SpringSim (2), pages 137–143, 2007.
in Bio-PEPA. Electronic Notes in Theoretical Computer Science,
227:77–95, 2009.
[8] L. Dematté, C. Priami, A. Romanel, and O. Soyer. Evolving blenx
programs to simulate the evolution of biological networks. Theoretical
Computer Science, 408(1):83–96, 2008.
[9] C.-L. Fok, G.-C. Roman, and C. Lu. Enhanced coordination in sensor
networks through flexible service provisioning. In J. Field and V. T.
Vasconcelos, editors, Proceedings of COORDINATION 2009, volume
5521 of LNCS, pages 66–85. Springer-Verlag, 2009.
[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] D. T. Gillespie. Exact stochastic simulation of coupled chemical reac-
tions. The Journal of Physical Chemistry, 81(25):2340–2361, December
1977.
[12] T. Hérault, R. Lassaigne, F. Magniette, and S. Peyronnet. Approximate
probabilistic model checking. In VMCAI, pages 73–84, 2004.
[13] W. Hoschek. The Colt Distribution: Open Source Libraries for High
Performance Scientific and Technical Computing in Java. Geneva, 2004.
[14] S. Luke, C. Cioffi-Revilla, L. Panait, K. Sullivan, and G. C. Balan.
Mason: A multiagent simulation environment. Simulation, 81(7):517–
527, 2005.
[15] C. M. Macal and M. J. North. Tutorial on agent-based modelling and
simulation. Journal of Simulation, 4:151–162, 2010.