Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Mobile phones, laptops, tablets locally connected to each other form huge computing and storage infrastructures, currently under-exploited, but available on motorways, city-centers, inside buildings, etc. Those infrastructures pave the way for a new category of services based on data propagation among devices, e.g. car traffic control service through propagation of data from one car to another, information dissemination in a crowd to better steer the crowd towards points of interest or emergency exits, and alternative communication infrastructures in case of environmental disasters. Such services are time-related: they may last just for a very short time for a specific purpose exploiting current contextual data, as well as space-related: these services have a meaning because the data they rely on or the data they spread is spatially distributed over a geographic area.

Traditional service-oriented approaches allow programmers to combine together into a new service diverse functionalities provided themselves under the form of services. Typical approaches involve Web services or rely on APIs mashups. Composition of services is generally foreseen at design-time, adaptation happens by choosing the actual services at run-time. Current service-oriented approaches are not suited for the new generation of services, working on smart environments or exploiting Internet of Things scenarios. They do not cope with the dynamicity involved by the underlying mobile and changing computing infrastructures, the spatiality of the considered data, or time-related issues. There is a need for a paradigm shift in the notion of services along two dimensions: (1) services make sense because they are spatially distributed, their functionality is provided as the result of the interactions among several entities, possibly distributed across several computational nodes; (2) services are built on demand, e.g. users can query diffused clouds of data in a smart city, to retrieve the closest vacant parking place, sensors, “things” and services spontaneously collaborate to provide the answer to the query. We call such services spatial edge services. This paper summarises our research works related to the notion of spatial services.

2 Spatial Edge Services

Spatial edge services are a new generation of services that exploit spatially distributed data, enable smart environments, or exploit Internet of Things (IoT) scenarios. This is a new category of decentralised services based on data propagation among mobile devices and where the functionality of the service is provided as the result of the collective interactions among multiple entities, involving processes and calculations taking place across several spatially (geographically) distributed computational entities (i.e. sensors, mobile or stationary computational nodes, actuators). Spatial edge services are built and composed on-demand. Spatial edge services are based on Spatial Computing [29]. Spatial computing thrives on decentralised computation, in a way similar to edge computing, fog computing or jungle computing, where computation is pushed at the edge of the network, away from centralised clouds, closer to end-users [23]. Spatial services bring an engineering dimension to spatial computing as they provide ready to use services that can be deployed on-demand over physical environments by higher-level services or applications. A spatial service is built dynamically through collaboration with other services [17]. Spatial edge services have time- and space-enabled capabilities: deposit data at geographic locations, retrieve data, aggregate data, provide information to users, evaporate information, or act on the environment. Geographically distributed data collectively provides a specific meaning (e.g. artificial gradient).

Bio-inspired mechanisms. Self-organisation, as exhibited by natural systems, provides an appealing approach to engineer spatial services where the functionality and coordination arises from the interactions among several autonomous entities; no central control is required; and some robustness properties and adaptation in dynamic large-scale environments are naturally provided. Self-organisation is achieved by the use of self-organising mechanisms [21] (Fig. 1), i.e., rules that autonomous entities employ to coordinate their behaviour, usually following information gathered from their local environment. One of the main ideas behind spatial service is to provide the above mechanisms under the form of services, ready to use by other services. Therefore, among spatial services, we distinguish on the one hand, Spatial User Services (like finding a vacant parking place), and Spatial System Services, those services that implement spatial self-organisation mechanisms like spreading or gradient for example.

Fig. 1.
figure 1

Self-organising mechanisms

Full size image
Fig. 2.
figure 2

Spatial services

Full size image

Spatial system services. [17] bring an engineering dimension to spatial computing as they provide ready to use services that can be deployed on-demand over physical environments by higher-level services or applications. Spatial system services are based on self-organising mechanisms [21], they are time- and space-related, work on a decentralised and autonomous manner, and are naturally robust to some environmental perturbations, even though not to any perturbation or environmental change [15]. Figure 1 depicts these self-organising mechanisms as well as their inter-relations (e.g. gossip uses spreading and aggregation).

Spatial user services are the services offered at the application level (for example the services offered by a smart city like help for parking, visually impaired visitor guided across a campus). They are provided through dynamic selection of underlying spatial system services. Figure 2 shows an example of such service, parking place sensors communicate with the nearest street lamp. Information about empty places spread, thanks to the Gradient system service among street lamps, until it reaches the user requesting that information.

Chemical-based coordination platform. Spatial services rely on the SAPERE coordination model that is built on chemical reactions and active shared tuple spaces [30] and its corresponding middleware [4]. Depending on their nature and location, objects are attached to diverse computational nodes (e.g. cars, smartphones, raspberry pi, etc.). Each computational node runs an instance of the coordination platform. Software agents run in the node and interact on behalf of objects (e.g. lamps, cameras, etc.), services, or applications with the coordination platform. They inject or retrieve information to/from the platform, and are sensitive to data present in the platform. Software agents also act on the objects (e.g. switch on/off a lamp, turn surveillance camera), update data spread by a spatial service, or provide a parking place location. Figure 3 depicts the case of a computational node, running an instance of the coordination platform. Computational nodes are connected through low-level connection mechanisms.

Fig. 3.
figure 3

Coordination model

Full size image

3 Design Patterns

Bio-inspired mechanisms. In biological systems, complex emergent behaviour can be achieved by letting agents follow a set of basic rules while having only partial knowledge of the environment. Typical bio-inspired self-organising mechanisms are those using stigmergy, like ant foraging for coordinating behaviour, schooling and flocking for coordinating movements, or gradients based systems [5, 18].

Bio-inspired design patterns. To ease the use of bio-inspired mechanisms and to apply them more systematically, a series of authors proposed descriptions of these mechanisms under the form of design patterns [1, 14, 22, 25, 27]. Results show that the bio-inspired decentralised approaches achieve better results (in terms of robustness, optimisation and adaptability) than more traditional approaches based on formal modelling. To ease engineering of artificial bio-inspired systems, we described a catalogue of bio-inspired mechanisms in terms of modular and reusable design patterns organised into different layers [21], shown on Fig. 1. The mechanisms presented are uniformly described and framed using a software design pattern structure identifying when and how to use each pattern, and describing the relationship between the different mechanisms and their respective boundaries. This catalogue of mechanisms is a step forward to engineering self-organising systems in a systematic way.

4 Suite of Spatial Services

Despite the interest in building self-organising systems, there is currently no established way of designing and programming self-organising systems or applications in a systematic way. Applications are developed in an ad-hoc manner and the functionality of the application is closely entangled with the underlying self-organising mechanism. To implement a crowd steering application using digital pheromones, in addition to programming the crowd steering application functionality it is also necessary to implement the behaviour of the digital pheromone itself. We then consider that for engineering self-organising systems it is important to separate the concerns at different levels: (1) Separate functionality of an application from the underlying mechanisms it uses; (2) Delegate underlying mechanisms and their non-functional, self-managing aspects to the underlying environment.

Self-organising mechanisms as services. In consequence, we propose that self-organising mechanisms (e.g. gradients, digital pheromone or gossip) be provided to higher-level services or applications as ready-to-use services. This involves the design and implementation of a computational environment that provides reliable low-level self-organising mechanisms in the form of services, reusable by applications. This allows the implementation of self-organising applications in a modular way, favours reuse of mechanisms by decoupling them from the application functionality and delegating responsibilities for them to the computational environment.

Core service. Following the relationship among self-organising mechanisms, Core services provided at the level of the infrastructure or computational environment are: Spreading, Aggregation, Evaporation, Static Gradients. Higher-level services, developed by re-using and extending low-level self-organising services provided by the infrastructure, are: Dynamic Gradients, Chemotaxis, Remote Query and Retrieval (a composed service that spreads a query using the Gradient or Dynamic Gradient service and uses the Chemotaxis service to bring back information from remote nodes [19]). We propose to program self-organising systems using services that implement self-organising mechanisms, abstracting away the implementation of those low-level mechanisms for the developer and favouring the re-use of code.

Higher-level services. At the lower level, the computational environment provides reliable “Core” services, i.e. low-level self-organising mechanisms and proposes them to higher-level services or to applications in the form of ready-to-use “services” (e.g. spreading or evaporation). The implementation of higher-level self-organising services (e.g. digital pheromone or dynamic gradient) uses and exploits those low-level services. Higher-level services are themselves ready to be used by actual applications. Finally, applications exploit both high-level and low-level self-organising services. Their implementation happens then in a modular way, reusing self-organising mechanisms, decoupling them from the application functionality, as shown in Fig. 4.

Fig. 4.
figure 4

Spatial services

Full size image

5 Coordination Models

Coordination models have proven useful for designing and implementing distributed systems. They are appealing for developing collective adaptive systems working in a decentralised manner, interacting with their local environment, since the shared tuple space on which they are based is a powerful paradigm to implement bio-inspired mechanisms (e.g. stigmergy). Coordination infrastructures provide the basic mechanisms and the necessary middleware to implement and deploy coordinated systems. Different categories of coordination models have been developed: chemically-inspired models work as rewrite systems, where states are interpreted as chemical substances, and where molecules represent the coordinated entities that interact according to some reaction rules [30]. Physics-based models, are instead inspired by the way physical masses and particles move and self-organise according to gravitational and electromagnetic fields [2, 26].

5.1 SAPERE

Our work derives from the SAPERE model [3], a coordination model for multi-agent pervasive systems inspired by chemical reactions. It is based on four main concepts: Live Semantic Annotations (LSAs), LSA Tuple Space, agents and eco-laws. LSA are tuples of types (name, value) used to store applications data. For example, a tuple of type (date, 04 / 04 / 1988) can be used to define a hypothetical date. LSAs belonging to a computing node are stored in a shared container named LSA Tuple Space. Each LSA is associated with an agent, an external entity that implements some domain-specific logic. For example, agents can represent sensors, services or general applications that want to interact with the LSA space - injecting or retrieving LSAs from the LSA space. Inside the shared container, tuples react in a virtual chemical way by using a predefined set of coordination rules named eco-laws, which can (i) instantiate relationships among LSAs (Bonding eco-law), (ii) aggregate them (Aggregate eco-law), (iii) delete them and (Decay eco-law) and (iv) spread them across remote LSA Tuples Spaces (Spreading eco-law). When a tuple is modified by an eco-law, its relative agent is notified. The implementation of the SAPERE model (Fig. 5(a)), named SAPERE middleware permitted the development of several kinds of real distributed self-adaptive and self-organising applications [30].

5.2 Logic-Based Chemical Coordination Model (LFCM)

A well-known difficulty with self-organising systems stems from the analysis, validation and verification (at design-time or run-time) of so-called emergent properties - i.e. properties that can be observed at a global level but that none of the interacting entities exhibit on its own. Few coordination models integrate features supporting the validation of emergent properties, none of them relying on the chemical metaphor. Recently we extended SAPERE and defined a coordination model based on logic inference named Logic Fragments Coordination Model (LFCM) [10] as well as its semantics [12] (Fig. 5(b)). Logic Fragments are combinations of logic programs defining interactions among agents distributed over the nodes of the system. They are able to accommodate various types of logics, ranging from classical up to many-valued paraconsistent ones. The logical formalisation makes it possible to express coordination in a rigorous and predictable way, both at design-time and run-time. Our logic-based coordination model allows agents to inject logic fragments into the shared space. An additional eco-law, the logic fragement eco-law interprets those fragments based on the current tuples in the tuple space (including neighbouring ones). Those fragments actually define on-the-fly ad hoc chemical reactions that apply on matching data tuples present in the system, removing tuples and producing new tuples, possibly producing also new logic fragments. Our model is defined independently of any specific logic, an actual instantiation and implementation of the model can use its own logic(s). We also defined a spatial language to verify graph-based spatial properties of self-organising systems [6], a multi-valued logic [7] and an approximate reasoning [13]. The language encapsulates Logic Fragments in statements that are evaluated in a distributed manner at run-time, involving several system entities at the same time. The corresponding middleware for two-valued logic is available. LFCM is composed of the following elements (Fig. 6):

  • Agents: autonomous entities representing applications, services and sensors.

  • Tuple space: shared space for all the agents running on the same node of the system. The Tuple Space stores information under the form of tuples, which can be passive (e.g. contextual-information, data input for service invocation, etc.) and active (logic fragments).

  • Logic fragments: combinations of logic programs manipulating passive data stored in the Tuple Space and introduced either by Agents or generated by other logic fragments. They can be injected, removed and copied among nodes of the system at run-time. We consider many-valued logics with true, false, unknown and inconsistent logical values.

Fig. 5.
figure 5

Coordination models

Full size image
Fig. 6.
figure 6

Components of the Logic Fragment Coordination Model. Green tuples represent passive data injected by Agents, red ones depict information generated by logic fragments. (Color figure online)

Full size image

LFCM combines the benefits of chemical-based coordination models and formal methods, offering a framework to rigorously design and implement self-organising systems. In the LFCM logical formulae are represented by combinations of logic programs, whereas the execution flow is controlled through predicates and operators defining how logic programs are interpreted and how data is manipulated through predicates (e.g. to create, aggregate, delete and spread information).

  • When designing complex coordination mechanisms, great emphasis is put on the definition of the logic part, enforcing a rigorous formalisation of the algorithm while hiding most of implementation details. In such a way, code of system units becomes an essential set of logical rules defining the behaviour of components with respect to the distributed state of the system. This aspect ensures that the set of spontaneous interactions taking place in the system is the one that is logically entailed from the rules.

  • The usage of logic programming to design system units makes it possible to adopt a uniform formal framework to specify, verify, synthesise system components. This is possible because pure logic can be used as a language for system specifications. When designing complex distributed systems these properties become extremely important because they can be exploited to enforce correctness at design-time.

  • Given that system components are encapsulated into combinations of logic programs, they can be easily added, removed and shared among nodes. This feature enables the installation and removal of ad-hoc coordination primitives on-the-fly.

  • By resorting to logic programming, interactions among components are driven by logic inference and system components can be considered as units performing formal reasoning processes on the distributed state of the system. By resorting to this feature, components can be exploited to evaluate distributed system properties at run-time [11].

6 Prototyping Platforms

TheOne-SAPERE. TheOne-SAPERE is a prototyping tool [20] that integrates the SAPERE middleware within The Opportunistic Network Environment (The One) simulator [24], allowing us to prototype and validate applications with realistic scenarios before deploying them. Indeed, it allows on the one hand to simulate a large number of computational nodes movements and their communications, placing them in various configurations allowing stochastic evaluation of parameters. On the other hand, each node is equipped with the actual SAPERE middleware (actual code), allowing to execute from within the simulation actual spatial system services (gradient, spreading, evaporation, etc.), thus providing actual results relating to spatial system services behaviour (Fig. 7). The corresponding video is available on-lineFootnote 1.

TheOne-LFCM. Following the above idea, we similarly developed a corresponding simulator, called TheOne-LFCM, involving the actual LFCM middleware in each simulated node.

Fig. 7.
figure 7

TheOne-SAPERE

Full size image

7 Developed Applications

We discuss here a series of applications actually deployed on tablets and smartphones. For more IoT applications, see [16].

Confidential channel. The Confidential Channel service [8] provides an encrypted channel for routing confidential communication between devices in a mobile ad-hoc network. The computational power and memory available in mobile devices, is increasing dramatically, and allows now the use of traditional encrypting techniques that some years ago were available only in wired computers, such as laptops or PCs. Therefore, the Secure Channel service uses RSA encryption on top of Dynamic Gradient and Chemotaxis services in order to ensure and maintain confidential communication and routing even in complex mobile networks. Using a Gradient service, node A sends a public key and a request for information. They are both propagated to all nodes in the network along with additional gradient information about the sender’s distance (e.g. number of hops). When the Gradient reaches node B, the latter retrieves the query and the public key. B encrypts the information using the received public key and sends back the encrypted information using the Chemotaxis service using the shortest available path. The gradient structure is updated periodically in order to deal with network’s topology changes. We subsequently developed a chat over the confidential channel.

SmartContent. This is a novel approach for content protection and privacy. Documents are active and context-aware documents that sense and analyse their current context, e.g. location, noise, neighbouring devices, social network, expiration time, etc. Based on user provided policies, they grant, deny or limit access and manipulation actions, or destroy themselves if necessary. The implementation leverages the SAPERE middleware. Context information (GPS location, camera picture, etc.) is provided as tuples in the SAPERE middleware. Specific agents, wrapping documents, enforce users’ policies. They are sensitive (bond) to context information relevant to the document they protect and enact when necessary the privacy policy (revealing or not the document) [9].

Context-aware data flows. The goal of this demonstration is to show-case self-organising context-aware data flows with a particular emphasis on the self-organising mechanisms [21] that are at the heart of it: (a) diffusion - propagates information among the nodes; (b) aggregation - allows the system to reduce the amount of information spread in the system or obtained from the environment; (c) evaporation - periodically decreases the relevance of the information in order to get rid of outdated information.

Fig. 8.
figure 8

Self-organising mechanisms - concepts

Full size image

In the first part of the demonstration, data flows of pictures spread, in a P2P fashion, from one tablet to the other. Data flows are sensitive to their context as follows: tapping tablets causes a new data flow to spread from one tablet to the neighbouring one (Fig. 8(a)); similarly swiping creates a new flow in the direction of the swipe; several flows meeting at the same time in the same tablet aggregate with each other. Here a simple aggregation is chosen, where one of the two flows is stopped (shown as an explosion in the demonstration) (Fig. 8(b)). Figure 8(c) shows an example of evaporation, with time data relevance fades away and ultimately information disappears. In the second part of the demonstration, data flows become services used to retrieve a friend in a crowd. A query first spreads from tablet to tablet following the gradient principle - a type of diffusion with a notion of distance [21]; once the message has reached the friend, the answer follows back the path created by the gradient. This demonstration has been featured at the ICT’13 Conference in Vilnius, the video is available hereFootnote 2.

Tracking mobile objects/runners - querying IoT. Runners are sensed along the racetrack and their positions spread continuously in order to provide a real-time tracking. A variety of devices (beacons), and nodes (raspberry pi and smartphones) are exchanging data using Bluetooth Low Energy (BLE) to track mobile objects in a peer-to-peer network. Let us consider that each runner is equipped with a small device that emits continuously a signal. We also deploy several nodes along the path sensing and relaying these signals. People in the crowd with a smartphone and an appropriate mobile application request informations about their favourite runners and receive a response in real-time. In other words, people track their favourite runners while they are running and follow their performance during the race.

Fig. 9.
figure 9

Tracking runners

Full size image

Each competitor runs with a beacon that emits a BLE signal. A beacon identifies a runner by communicating its runner identifier to its surrounding environment. Several nodes, running a SAPERE application built over the SAPERE middleware, are deployed along the path to sense BLE signals and compute their position in the race, their location on the map, and the time they have been running. Every node spreads received signals and people in the crowd interact across a peer-to-peer network to request information about their favourite runners (Fig. 9(a)). People track their favourite players while they are running and know about their performance live during the race (Fig. 9(b)). The information remains spatially available in the area only during the time when the event takes place. A complete description and full details can be found here [28].

Fig. 10.
figure 10

Warehouse and communicating shelf units.

Full size image

Assessing IoT properties on-the-fly. We show here how to resort to the Logic Fragment Coordination Model to design and implement a distributed monitoring spatial edge service for an industrial warehouse in order to avoid safety hazards arising from potential interactions among chemical compounds. The model of the warehouse system includes: Containers (e.g. tanks); Shelf units supporting the physical storage of containers in a particular point of the warehouse; Policies constraints on physical positions of containers implementing safety regulations (e.g. proximity relations among chemical compounds, etc.). Policies can be established, replaced or removed at run-time. By resorting to a many-valued logic, policies can be strongly violated, weakly violated, weakly accepted and strongly accepted. Our warehouse model is composed of 12 shelf units connected in a grid network; shelf units must be considered as autonomous agent entities, able to perform computations and communicate with each other (Fig. 10). The monitoring service triggers an alarm signal when one or several policies are violated on a particular shelf unit.

Whenever a policy is violated on a shelf unit, its associated logic fragment generates a tuple of type Alam(Rule), where Rule is the identifier of the policy. An additional logic fragment (controller of the system) aggregates all tuples of type Alarm(Rule), generating a tuple Alarm with a logical level that represents the level of criticality of the violated policies.

8 Future Works

Future works involve multiple paths: integrating learning aspects within agents, analysing QoS for each of the different spatial services involved in an application and their impact on each other, pursuing current efforts on privacy and security, actually building spatial services on demand, arising from existing services, sensors and actuators.