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.