3.1.1 Modelling space

There are two elementary types of spatial representations: geometric and symbolic. A geometric representation characterises a space with its geometric shapes and a set of coordinate points under a certain Cartesian coordinate reference system. A symbolic representation characterises a space with a human-friendly descriptive label. In the following, we focus on LOC8: a location model and extensible framework for programming with location, which was described conceptually in Ye et al. (Reference Ye, Coyle, Dobson and Nixon2007) and developed as a programming framework in Stevenson et al. (Reference Stevenson, Ye, Dobson and Nixon2010). LOC8 supports a comprehensive range of spatial representations and enables rich spatial queries including positioning, range, spatial relation, navigation, and semantic queries. LOC8 shares similar design principle with the other early established space models such as the Location Stack (Reference HightowerHightower et al., Reference Hightower, Brumitt and Borriello2002), the Aura project (Jiang & Steenkiste, Reference Jiang and Steenkiste2002), and the MiddleWhere (Ranganathan et al., Reference Ranganathan, Al-Muhtadi, Chetan, Campbell and Mickunas2004b). Here we take it as an example to illustrate the state of the art on the space modelling in pervasive computing.

LOC8 supports representing coordinate points in different coordinate reference systems, which can be a global standard like WGS84 or locally defined to simplify a region’s spatial representation. It borrows the simple linear conversion mechanism from Jiang’s model (Jiang & Steenkiste, Reference Jiang and Steenkiste2002) to support translating coordinate points from one reference system to another by rotating and moving the subject reference system towards the target system. On top of coordinates, LOC8 defines two-dimensional (2D) and 3D geometric shapes, which are further assigned with a symbolic label. Within LOC8, four spatial relationships are explored: containment, adjacency, connectedness, and overlap. The names suggest their meanings, and just to note that connectedness is a particular case of adjacency in which an entity can pass from a space to its adjacent space. It implies both the passage’s direction and the notion of an accessible distance between the related locations.

Beyond the above classic spatial representations, LOC8 also supports relative spatial representation to enable richer spatial queries: centre and compass. In the centre representation, a target location is a geometric area such as a circle or a cuboid, whose centre is a coordinate and whose edge or radius length is the specified distance. This is particularly useful in formulating an application of finding all the entities within a valid interaction range. The compass representation involves building a coordinate reference system whose origin is a coordinate and whose rotation matrix follows the standard compass direction. The description of a target location contains a distance to its origin; the horizontal angle to the target location, measured clockwise from north, and the angle of elevation from the horizontal plane. The compass representation is beneficial in precisely guiding an entity to navigate towards a target in a 3D space. This can help to address many positioning problems in pervasive computing applications; for example in the Cooperative Object Detection and Ranging system (Kranz & Rockl, Reference Kranz, Franz, Strang and Rockl2008) where cars are assumed to be installed with positioning and communication technologies, the compass representation can help to automatically detect the presence of the cars, predict the collision possibility, and send an early warning even when these two cars cannot see each other (Stevenson et al., Reference Stevenson, Ye, Dobson and Nixon2010).

LOC8 adopts a loosely coupled modelling technique that treats location information independently from other forms of context. This allows to treat all locatable objects in the same way, irrespective of their property structure and use by applications. In contrast, Nexus, an early open platform for a common augmented-world model (Hohl et al., Reference Hohl, Kubach, Leonhardi, Rothermel and Schwehm1999), distinguishes representations of the location of static real-world entities from virtual entities with which the real world is augmented.

3.1.2 Modelling data in space

In terms of representing context in space, there are generally two approaches: treating space as an attribute to describe data, nothing more than any other attribute; and considering space as a first-class concept managed by the infrastructure.

Most existing space models and context models adopt the first approach. For example, Cohen et al. (Reference Cohen, Lei, Castro, Davis and Purakayastha2002) propose a language called iQL to specify the composition of pervasive services. Location is included and injected by a service; for example, a badge advertisement service injects a coordinate point of a badge wearer, with which to find all the neighbour wearers, or a local business publishes its advertisement along with its zip code so as to locate all the users present in the designated area. In this way, it is the responsibility of sensors and services to inject and update the location data, while the infrastructure performs the matching in a passive or active manner.

The Intentional Naming System (INS) (Adjie-Winoto et al., Reference Adjie-Winoto, Schwartz, Balakrishnan and Lilley1999) supports applications in identifying resources by their properties rather than physical address. In the INS, resources are described using intentional names, a hierarchy of attribute/value pairs (called name specifiers) that describe the properties of the resource, spatial relations being one key descriptor. A name specifier has another name specifier as its parent, if its context is dependent on it (e.g. an identifier for the floor of a building is dependent on the building identifier). Resources advertise themselves to naming resolver components, which maintain a mapping between service description and physical address, while applications use name specifiers to describe the resources that they require. At runtime, a name resolver uses resource descriptions provided by the application to find matching services.

Based on the INS for resource discovery Solar is an infrastructure for collecting, processing, and disseminating context from ‘thousands of diverse sensors to hundreds of diverse applications running on thousands of devices’ (Chen et al., Reference Chen, Li and Kotz2004). Solar decomposes the context-aggregation process into modular and reusable operations, each of which is an object that subscribes to, processes one or more event streams, and publishes another event stream. Using an INS-like scheme, applications can specify the query using a tree of recursively connected operators (starting from sources and sinking in applications) to collect and aggregate context information. The result is a distributed directed acyclic graph (called an operator graph).

The above examples adopt an extrinsic approach to representing space, where spaces are named and used primarily as a means of explicitly identifying where an object is located. By contrast, some systems take an intrinsic view of space, where digital information is associated with physical objects, and their surrounding physical space and mobility is leveraged to support computing process. The spatial configuration of objects and their movements implicitly control an information system, and there is no explicit space representation beyond the local one implemented by the physical space itself (Banâtre et al., Reference Banâtre, Allard and Couderc2010). One way in which Banâtre et al. illustrate this concept is the example of a UbiBus system in which a token generated by a pedestrian while in the vicinity of a bus stop requests the next bus to stop as it approaches. It is the spatial configuration of the pedestrian, the bus stop and the bus which controls the token generation and stop requests.

Zambonelli et al. (Reference Zambonelli, Omicini, Anzengruber, Castelli, De Angelis, Di Marzo Serugendo, Dobson, Fernandez-Marquez, Ferscha, Mamei, Mariani, Molesini, Montagna, Nieminen, Pianini, Risoldi, Rosi, Stevenson, Viroli and Ye2015) adopt a biochemical approach where spatial computations are structured in terms of chemical-resembling reactions, each occurring in the precise physical point where the space is located, namely, where the device is deployed. They describe a coordination model that is equipped with space–time computing mechanisms, including reification of space–time information and a relocation service for annotations (Viroli & Stevenson, Reference Viroli and Damiani2012). Within the coordination model, all the entities (including software agents, sensors, or resources) are described in a uniform representation—a Live Semantic Annotation (LSA). LSAs continuously represent the state of their associated components and are connected to the domain in which the information can be produced, interpreted, and manipulated.

Here, space is again treated intrinsically. Each LSA carries one property holding one URI value representing the ID of the location. This property is not specified by the agent that injects an LSA, but rather created and maintained by the infrastructure. The value in this property indicates how a local space is shaped around the node that hosts the injecting agent, by locating nearby neighbours in this node’s vicinity such as their distance, connectivity, communication bandwidth, and the relative orientation in space. Reifying location into these LSAs enables dynamic behaviours; for example, a lower-level middleware service can be in charge of intercepting such LSAs before they are injected in the space, and relocating them to the proper neighbour, by an asynchronous request (Viroli & Stevenson, Reference Viroli and Damiani2012). The update and maintenance of reified locations is governed via eco law in the infrastructure, while eco law are a set of self-organising rules that manipulate LSA spaces.

3.2.1 Acquiring and organising local context

Not only is space a key context but it also serves well as an intuitive metaphor for non-spatial context. That is, context has a strong indication of locality, which can be interpreted as

• ∙ where the context is about; for example, the crowdedness of DisplayX01 is high;

• ∙ where the context is of; for example, Bob is in front of DisplayX01; and

• ∙ where the context is bound; for example, Bob’s preference is only bound to DisplayX01, which cannot be accessed by or spread to any other displays.

Even though existing in different interpretations, locality is the mechanism to relate different contextual information; that is, if two pieces of context are located in the same local space (in an absolute spatial term), or within a short range (in a relative spatial term), then they can be related. Hence, locality of context is well suited to organise context in physical locations (Bettini et al., Reference Bettini, Brdiczka, Henricksen, Indulska, Nicklas, Ranganathan and Riboni2010). As we look to design systems with the capacity to handle the ever increasing amount of data generated by myriad physical and Web resources, it becomes less likely that we choose to provide access globally through a centralised service. Although logically centralised services—although implemented on top of distributed systems—are the current architecture of choice (e.g. Google, Amazon, Facebook), there are a number of reasons that suggest they are not well matched for managing data in large-scale pervasive service ecosystems: (1) the amount of information being continuously generated is potentially overwhelming, presenting scalability challenges; (2) requiring more than just a store and query architecture, there is significant computational complexity in reasoning about what is happening in each local space from all the information available; and (3) in the vast majority of cases, information will only be relevant locally and only for a short period of time—it is likely that the majority of information generated will never be used. From the standpoint of efficient resource utilisation, it makes little sense to collect, process, and distribute data from a centralised service under these circumstances. All this said, there will likely remain a class of pervasive applications with data requirements such that a logically centralised service remains a viable implementation choice.

Early context-aware systems like Context Toolkit follow the above centralised solution, where all related context are centralised for decision making and service provision (Heer et al., Reference Heer, Newberger, Beckmann and Hong2003). Dey et al. (Reference Dey2002) later enhance the Context Toolkit as a distributed system that supports distributed feedback based on context acquired in different physical locations. Similarly, Remembrance Agent provides a service that examines users’ current location, identifies their nearby individuals, and uses such locality information to retrieve the most relevant context to the users’ current situation (Rhodes, Reference Rhodes1997). A neural network house learns occupants’ patterns of heating and lighting control for various locations in the house and uses this knowledge to predict user needs (Mozer, Reference Mozer1998).

All the above systems demonstrate how to acquire and gather context centring around a certain location, while Liquid is one of the very first attempts to deal with context-aware distributed queries towards a more general space-oriented manner (Heer et al., Reference Heer, Newberger, Beckmann and Hong2003). The system is built on top of Context Fabric (Hong, Reference Hong2002) that provides the abstraction of information spaces (called infospaces), which are logical storage units using the tuple space paradigm as context repositories for individual entities in an environment. Within Liquid, each query is organised into partitions that can be served at individual infospaces. For example, a query retrieval path of ‘location.occupant’ is designed to retrieve the location of people in the same room as the query issuer.

Liquid supports two operators to service spatial queries: local and external operators. The local operator is responsible for retrieving context data from the local infospace, where a Liquid node resides, and for monitoring the local infospaces for tuple insertions, deletions, and updates. In contrast, the external operators retrieve data from remote infospaces by querying other Liquid nodes. Result items will be streamed back and enqueued into the local operator through a callback from the network layer. These queries can benefit applications by providing augmented awareness within a space. For example, an application can provide resources (such as webpages or e-mails) for all the people currently in the same room as the query issuer. As people enter and exit the room, this result is automatically updated in this room. Also, when the query issuer moves from place to place, the query will be automatically rerouted to the correct infospaces for the new location.

3.2.2 Mediating interactions via locality

Locality is an important concept in coordination models where entities can interact via direct connections (Cabri et al., Reference Cabri, Leonardi and Zambonelli2000a). In the early attempts agents need to explicitly name their communication partners (Cabri et al., Reference Cabri, Leonardi and Zambonelli2000b). However, in pervasive computing applications, where agents can be dynamically created or removed from an environment, it is difficult to adopt such a spatially coupled model that requires the identification of the communication partners. Also, entities are supposed to be able to move and if they need to communicate directly on a wide scale, then they have to be localised.

The meeting-oriented coordination model attempts to address this spatial coupling problem by virtualising an abstract meeting point where agents can join, communicate, and synchronise with each other (White, Reference White1997). Meeting points are locally constrained in that a meeting takes place in a certain execution environment and only local agents can participate. The major drawback of this model, however, is that it enforces a strict temporal coupling; that is, in order to interact the agents must be at the same meeting point at the same time.

An alternative approach uses blackboard-based coordination, where interactions can occur via shared data spaces (called blackboards) (Nii, Reference Nii1986). Blackboards can be considered as a medium to store and provide access to locally published data and services; agents communicate by leaving messages without the need to know when and by whom the messages will be read. The Linda model (Gelernter, Reference Gelernter1985), which provides for a blackboard with associative matching for mediating component interactions through insertion and retrieval of tuple limits, provides the archetypal example. However, the scalability of blackboard approaches to large number of agents remains a concern (Viroli et al., Reference Viroli and Stevenson2011; Stevenson et al., Reference Stevenson, Pianini, Montagna, Viroli, Ye and Dobson2013a). Inspired by nature, TuCSoN (Omicini & Zambonelli, Reference Omicini and Zambonelli1999), MARS (Cabri et al., Reference Cabri, Leonardi and Zambonelli2000a), and chemical-inspired tuple space (Viroli et al., Reference Viroli and Stevenson2011) propose to specify policies inherent in the tuple space to control and manage interactions in a self-organising and self-composing way.

3.3.1 Location fusion of heterogeneous sensors

Concerning local fusion of heterogeneous sensors, most of the work in the area focusses on identifying the symbolic and meaningful place in which a user is located by using data coming from different positioning systems. This arises from the need to switch from a perspective in which the geographical position, say, from the GPS sensor, is the only raw contextual information available, to a perspective in which the place (e.g. office, home, or market) where the user is pinpointed is inferred, which corresponds to the physical and symbolic locations discussed in Section 3.1.1. This switch can be realised in many ways, one example being through fusing GPS information with that coming from co-located microphones (Azizyan & Choudhury, Reference Azizyan and Choudhury2009) or other environmental sensors (Jung et al., Reference Jung, Teixeira and Savvides2010). The need to considering place instead of position comes from a wish to enrich positions with semantic data (possibly also related to users’ activities), first discussed by Hightower (Reference Hightower2003), and further refined and enriched by Castelli et al. (Reference Castelli, Mamei, Rosi and Zambonelli2009) and Liao et al. (Reference Liao, Fox and Kautz2007) who realise various reasoning engines to semantically identify places visited on the base of temporal patterns, using probabilistic models and Bayesian networks, respectively.

More general approaches focus on sensorial data fusion at different levels, either for acquiring and making accessible all aspects of the local spatial context or for reasoning about the context at a fine-grained perspective in order to get a better understanding of currently happening situations and detecting inconsistencies. Early works consider simple data fusion as aggregation of logically related context data based on simple name transformation (Dey et al., Reference Dey, Mankoff, Abowd and Carter2001), possibly by adopting a common context specification language (Hong & Landay, Reference Hong and Landay2001). Also, more recent works exploit a similar approach, in which contextual data are represented at a high level with a common structure in order to promote the same management for data coming from diverse sources and to ease the data usage and reasoning (Bortenschlager et al., Reference Bortenschlager, Castelli, Rosi and Zambonelli2009).

Uncertainty lies at the heart of all descriptions of the sensing and fusion process. Probabilistic and knowledge models (or the combination of both) provide a powerful means of describing uncertainty and lead naturally into ideas of information fusion. Such models are often used to achieve context fusion at a finer-grained level. Ganti et al. (Reference Ganti, Srinivasan and Gacic2010) use lightweight Bayesian learning algorithms based on hidden Markov model when integrating data from the microphone and inertial sensors on the mobile phones in order to infer high-level human activities. Tran and Phung (Reference Tran and Phung2006) exploit the combination of multiple probabilistic techniques to reduce the number of model parameters to be taken into account when a large number of sensors are used in a smart home environment. Liu and Singh (Reference Liu and Singh2004) propose a promising approach of applying commonsense knowledge to better correlate information coming from different sensors (Mamei, Reference Mamei2010; Bicocchi et al., Reference Bicocchi, Lasagni and Zambonelli2012a). The idea is to use a database of commonsense semantic information in order to associate a comprehensive meaning (i.e. in the form of a word or a sentence) to multiple information (in the form of semantic tags) coming from a set of multiple heterogeneous sensors. Dempster–Shafer theory (Dempster, Reference Dempster1968; Shafer, Reference Shafer1976), a mathematical theory of evidence that provides the ability to combine evidence from different sources to arrive at a degree of belief in a proposition while preserving ignorance, has been applied to a wide range of sensor fusion tasks, spatial data included (Wu et al., Reference Wu, Siegel, Stiefelhagen and Yang2002; Zhang et al., Reference Zhang, Cao, Zhou and Guo2009; Mckeever et al., Reference Mckeever, Ye, Coyle, Bleakley and Dobson2010). Its application relies on expert knowledge to define an evidential reasoning hierarchy and quantify the accuracy of sensors. Consequently, its application is limited to domains in which experts can reasonably be expected to provide this knowledge.

3.3.2 Regional fusion of uniform sensors

Many works in the area of wireless sensor networks for mobile users are concerned with regional fusion of uniform sensors (Yick et al., Reference Yick, Mukherjee and Ghosal2008). Most of the approaches on sensor networks assume the presence of base stations to which sensed data should flow. In such situations, the basic solution is to have sensors build a tree rooted at the sink and supporting the routing of sensed data towards it (Polastre et al., Reference Polastre, Szewcyk, Mainwaring, Culler and Anderson2004), possibly performing limited forms of data fusion (e.g. averaging or max/min determination) as data from sensors climb the tree (Gehrke & Madden, Reference Gehrke and Madden2004), with the goal of reducing communications between sensors and thus, the energy costs. However, when mobile users wishing access surrounding sensorial information from their current location are involved, tree-based approaches can hardly apply as a general solution. In fact, the costs of building a tree on demand for many possible mobile users at various locations would be unbearable, and none of the many optimisations proposed (Kabaday & Julien, Reference Kabaday and Julien2007; Yang et al., Reference Yang, Ye and Sikdar2008) fully eradicates the identified flaws of tree-based approaches.

To accommodate the need of mobile users to achieve an understanding of the situation around, as sensed by different sensors dispersed around, one has to aggregate data in the sensor network (or in confined spatial regions of the network) such that queries by multiple and mobile users can be answered (Lotfinezhad et al., Reference Lotfinezhad, Liang and Sousa2008; Bicocchi et al., Reference Bicocchi, Mamei and Zambonelli2012b). This basically corresponds to fusing information about a specific aspect within a region so as to gather a more global understanding of a specific phenomena. For instance, in Sarkar et al. (Reference Sarkar, Zhu and Gao2007), each sensor in the environment can compute, at predefined communication and energy costs, aggregated information about sensorial information in its neighbourhood, and the aggregation functions can be concurrently computed for neighbourhoods of different sizes. However, the definition of the regions in which to produce aggregated data is mostly network driven, and does not take into account specific characteristics of the environment being monitored or of the phenomena being sensed. To overcome this limitation, Bicocchi et al. (Reference Bicocchi, Mamei and Zambonelli2012b) propose the virtual macro sensors approach to make a sensor network self-organise into regions characterised by similar sensing patterns, which helps to promote aggregation of data on a per-region basis, as if each region were monitored by a single macro sensor. Such an approach can be very effective in facilitating data collection in dense large-scale sensor networks, and as well as in identifying the regions in which specific situations take place.

Several research works in the area of middleware and programming languages for distributed sensor networks start recognising the need to support various forms of spatial aggregation of data (Mottola & Picco, Reference Mottola and Picco2011). They define suitable general-purpose primitives and language constructs (together with the supporting middleware infrastructures) to enable users to flexibly query the network and obtain information about individual sensor data and aggregated data related to specific spatial regions. Approaches such as logical neighbourhood (Mottola & Picco, Reference Mottola and Picco2006) and TeenyLIME (Costa et al., Reference Costa, Mottola, Murphy and Picco2007) can be considered as general tools to program and enforce regional fusion of contextual information.

As far as distributed data aggregation is concerned, although not always connected with spatial awareness, diffusive algorithms (Corradi et al., Reference Corradi, Leonardi and Zambonelli1999) and gossip-based aggregation algorithms (Jelasity et al., Reference Jelasity, Montresor and Babaoglu2005) are worth mentioning. Such approaches have been proposed as simple yet very effective approaches to compute and make available at each node of a network that aggregates values related to some global property of a network. When applied to nodes in spatial proximity relations (Dimakis et al., Reference Dimakis, Sarwate and Wainwright2006), such approaches can be indeed exploited as a means to achieve spatial fusion of contextual information. Interestingly, it has been recently shown that gossip-based aggregation algorithms can also be exploited to perform distributed learning of contextual information (Ormándi et al., Reference Ormándi, Hegedüs and Jelasity2013), by preventing the distribution of raw contextual information in respect of those privacy concerns.

3.4.1 Sharing contextual information proactively

Generally, the most intuitive way of sharing contextual information in a pervasive system is to proactively propagate among nodes. A naive process potentially involves a high bandwidth usage and a high volume of information stored at each node. Propagation can then take different forms, from pure flooding to more subtle forms of broadcasting aiming at reducing bandwidth. Additionally, information injected and propagated in the pervasive system can be outdated or no longer valid because of the environment dynamism. To overcome each of these disadvantages, three self-organising mechanisms have been proposed: spreading, aggregation, and evaporation.

Spreading mechanism. Contextual information often needs to be propagated so that remote nodes can perceive it beyond their local perception and thus increase their knowledge about the global state of the system. Spreading has been proposed as a primitive mechanism for a large number of self-organising complex mechanisms (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a), which is also alternatively called as information diffusion (Khelil et al., Reference Khelil, Becker, Tian and Rothermel2002), information or data dissemination (Sabbineni & Chakrabarty, Reference Sabbineni and Chakrabarty2005), flooding (Yi & Gerla, Reference Yi and Gerla2003), broadcast (Tseng et al., Reference Tseng, Ni, Chen and Sheu2002), or epidemic spreading (Khelil et al., Reference Khelil, Becker, Tian and Rothermel2002). In Reference BealBeal ,Reference Bealand Viroli (Reference Beal, Dulman, Usbeck, Viroli and Correll2014), a general purpose, reusable and self-stabilising building block ‘G’ for spreading is studied, used to propagate information outward a source and along a gradient-like data structure, with possibility of on-the-fly computation of information.

The propagation of information using broadcasting may result in serious redundancy, contention, and collisions (Tseng et al., Reference Tseng, Ni, Chen and Sheu2002). Many optimised spreading algorithms have been proposed in the literature, mainly focussed on reducing bandwidth usage. These algorithms range from pure flooding (Obraczka et al., Reference Obraczka, Viswanath and Tsudik2001), to probabilistic propagation (Eugster et al., Reference Eugster, Guerraoui, Handurukande, Kermarrec and Kouznetsov2003; Sasson et al., Reference Sasson, Cavin and Schiper2003), to dynamic probabilistic propagation (Zhang & Agrawal, Reference Zhang and Agrawal2005), to location-based propagation (Tseng et al., Reference Tseng, Ni, Chen and Sheu2002), and to hybrid propagation where algorithms are switched depending on contextual information (Fernandez-Marquez et al., Reference Fernandez-Marquez, Stevenson, Tchao, Ye, Di Marzo Serugendo and Dobson2014). Location-based propagation is a family of algorithms that take into account the position of neighbouring nodes in order to decide which nodes should re-send the information. The main goal is to reduce the number of nodes that re-send the information. Location-based approaches present very good results compared to pure and probabilistic propagation schemes, however, the computation carried on at each node is more complex, and relies on nodes providing their positions voluntarily and accurately. Location-based implementations can be extended by taking into account neighbouring nodes of two-hop distance, further optimising the reduction in the number of messages sent, but increasing dramatically the computation at each node.

Aggregation mechanism. Even though these optimised techniques mentioned above can help to reduce the bandwidth usage during spreading, we still need a mechanism to reduce the volume of information (e.g. information coming from a sensor sampling every minute, or information coming from several sources). The Aggregation mechanism (Gardelli et al., Reference Gardelli, Viroli and Omicini2007; Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a) as a way to reduce the amount of information in the system by synthesising meaningful information. Aggregation, also known as fusion (Niu & Varshney, Reference Niu and Varshney2005), locally applies a fusion operator to process the information and synthesises macro information. This fusion operator can take many forms, such as filtering, merging, aggregating, or transforming (Chen & KotzReference Chen and Kotz, ,Reference Chen and Kotz2002). Different aggregation strategies have been discussed in Section 3.3.2. Similarly to the case of G, in Reference BealBeal Reference Bealand Viroli (Reference Beal, Dulman, Usbeck, Viroli and Correll2014) a building block ‘C’ for collecting values into sources is proposed, in which information moves back to a source with progressive aggregation.

Evaporation mechanism. Even using aggregation, outdated, or no longer valid information can remain in the system, which could lead to a wrong contextual perception and thus misguiding the system decisions. The Evaporation mechanism (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a), also known as decay (Huebel et al., Reference Huebel, Hirche, Gusrialdi, Hatanaka, Fujita and Sawodny2008), temporal degradation function (Ye et al., Reference Ye, Dobson and McKeever2008), or freshness (Ranganathan et al., Reference Ranganathan, Al-Muhtadi, Chetan, Campbell and Mickunas2004a), has been proposed to deal with dynamic environments. Basically, the Evaporation progressively reduces the relevance of information. That is, recent information becomes more relevant than information processed some time ago. Additionally, evaporation can be directly used to remove no longer valid or updated information from the system.

3.4.2 Gathering distributed contextual information on request

The above three mechanisms such as Spreading, Aggregation, and Evaporation form the primitives for actively propagating distributed contextual information among a pervasive ecosystem. However, usually we do not need to actively propagate in the system. For example, when information is not relevant for a large number of users, when information is only useful at the time a user provides it, or when information is shared just with a subset of people interested. Following the example in Section 2, information such as the availability of advertisement and incoming events of a certain area would be specially interesting to users who are in the same area or nearby. Such a contextual information should be only spread to this subset of users.

Compared to the above proactively sharing approaches, gathering information on request presents advantages in dramatically reducing resource consumption such as memory and bandwidth. Gathering distributed contextual information requires two phases: (1) spreading the request in order to find the information at remote locations, (2) routing back the so-found information to the query node. Similarly to the above sub-section, we highlight the self-organising mechanisms useful for gathering distributed contextual information, either for spreading the request or for bringing back the results, which are Gradient, Dynamic Gradient, Chemotaxis, progressive in-network aggregation, and remote query and retrieval.

Gradient mechanism. The Gradient mechanism (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a) is to diffuse certain information together with additional metadata related to the distance of the gradient source (i.e. a type of hop count). Diffusing a gradient actually involves spreading information, incrementing a hop counter, and aggregating information when different routes reach an identical node. Once diffused in a geographic area, a gradient then provides additional useful information, such as the distance from the current node to the source of the gradient, direction towards or away from the gradient source, equipotential lines of distances from the source, and the shortest path towards the gradient source. Gradients take inspiration from nature, where they correspond to concentrations of substance. Gradients are a crucial mechanism in spatial awareness, and serve to form spatial structures, geographically dispersed but with a precise meaning. Indeed, by combining spreading and aggregation, gradients provide spatial information such as the shortest paths, distance, and directions to gradient’s source, which can also serve to route back information towards the source. Gradients are particularly useful for a query node when retrieving distributed contextual information. The query node becomes a gradient source and spreads a gradient whose main information is the requested query. Nodes answering the query then simply send the answer back along the paths built by the gradient towards the query node.

Dynamic Gradient mechanism. The Dynamic Gradient mechanism (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a), also called Active Gradient (Clement & Nagpal, Reference Clement and Nagpal2003), is a variant of the Gradient mechanism, where in addition to spreading and aggregation, evaporation also comes into play. In a mobile and dynamically changing environment, where nodes are constantly moving, appearing, and disappearing, a static gradient becomes quickly updated and cannot be used for routing information back to the gradient source. When the gradient information evaporates at the source node, the latter diffuses a new gradient structure. Dynamic Gradients are then particularly useful for spreading queries over mobile or dynamically changing infrastructure.

Chemotaxis mechanism. The Chemotaxis mechanism (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Montagna, Viroli and Arcos2012a) is about following up-hill, down-hill, or along equipotential lines a gradient previously established either by a given environment or engineered on purpose. Chemotaxis is a way to route back the information to the source of the gradient following the shortest path up-hill, thus answering the query.

Progressive In-Network Aggregation. In addition to Gradient and Chemotaxis described above, many different routing algorithms have been proposed in the literature, such as Ad-Hoc On-Demand Distance Vector (Perkins et al., Reference Perkins, Belding-Royer and Das2003), Dynamic Source Routing (Johnson & Maltz, Reference Johnson and Maltz1996), or Fisheye State Routing (Pei et al., Reference Pei, Gerla and Chen2000). Routing protocols are able to route information to a destination node. However, gathering distributed contextual information may involve thousands or even millions of pieces of data distributed among the nodes (e.g. calculating the average speed of cars driving in a city or specific road, or calculating the number of people attending a demonstration). Thus, it is not sufficient to route all data to the node interested in the information and let that node compute it. In order to gather a large amount of distributed data in a more efficient way in terms of energy, computation, and storage, in-network aggregation techniques have recently been proposed for the domain of wireless sensor networks: instead of sending all data to a destination node and letting this node compute (i.e. aggregate) the data, in-network aggregation provides the desired aggregation as a result of the distributed computation at intermediary nodes involved in the routing task (Fasolo et al., Reference Fasolo, Rossi, Widmer and Zorzi2007).

Even though in-network aggregation has been mainly analysed in the wireless sensor network domain, it will play a key role for distributed context perception in future pervasive ecosystems. They share constraints including low energy (most of the devices will be sensors, laptops, mobile phones, tablets, or smart watches), low computation power, and low storage capacity. Node mobility involves different concentration on nodes, segmentation, and frequent disconnections. In a pervasive ecosystem each node executes a different operating system, and has different hardware and different capabilities. This calls for an additional requirement related to a common middleware that allows transparent interactions between different nodes. A pervasive ecosystem is not designed for a specific goal, instead the system contains many applications with different purposes interacting among themselves. A major difference between the concept of aggregation in wireless sensor network (WSN) and pervasive ecosystems is that the aggregations in WSN are usually arithmetical or statistical aggregations such as minimum, maximum, average, or count. Aggregation in a pervasive ecosystem often involves reasoning, aggregation of functionalities and predictions, as discussed in Section 3.3.

Fernandez-Marquez et al. (Reference Fernandez-Marquez, Di Marzo Serugendo, Stevenson, Ye, Dobson and Zambonelli2012b) extend the general in-network aggregation and apply it to pervasive ecosystems, where a gradient is used both to propagate a query and to create a routing structure to bring the information back to the source node. Analogously to in-network aggregation, information is progressively aggregated at intermediary nodes, while it is being routed to the query node. Space plays a key role in this approach since data is gathered from nodes geographically dispersed across which gradients spread spatial information.

Remote Query and Retrieval. The combination of Gradient and Chemotaxis to query and retrieve information constitutes a mechanism on its own, termed Remote Query and Retrieval (Di Marzo Serugendo & Fernandez-Marquez, Reference Di Marzo Serugendo and Fernandez-Marquez2013). It employs progressive in-network aggregation when routing back information. It has been used for progressive self-aggregation of context information (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Stevenson, Ye, Dobson and Zambonelli2012b), progressive self-aggregation of situation information (Stevenson et al., Reference Stevenson, Fernandez-Marquez, Montagna, Rosi, Ye, Di Marzo Serugendo, Viroli, Dobson and Tchao2012), and semantic resource discovery (Stevenson et al., Reference Stevenson, Pianini, Montagna, Viroli, Ye and Dobson2013a).

Additionally, the mechanisms described above are also provided individually under the form of services, in an effort to separate concerns and to ease the engineering and development effort of self-aware spatial applications.

3.4.3 Distributed/decentralised situation recognition

The above two sub-sections discuss the case of sharing or gathering raw context information, possibly aggregating or evaporating it along the way to retain pertinent or up-to-date information. On the basis of context information, it becomes possible to reason and identify actual situations, that is from Bluetooth proximity signals identifying that a group of people are crowded in front of a display. Section 3.5 will discuss this issue in more detail, however, in relation to distribution and context perception and the above described mechanisms, we highlight here the case of distributed and decentralised situation recognition (Stevenson et al., Reference Stevenson, Fernandez-Marquez, Montagna, Rosi, Ye, Di Marzo Serugendo, Viroli, Dobson and Tchao2012).

As for context perception, a request, originating from an application, spreads throughout the network establishing a gradient. Typically, a sensor or a reasoner agent receiving the request evaluates whether its capability matches the request. If it matches, the sensor or reasoner agent either retrieves the matched data or starts reasoning and then encapsulates the result in a reply message that is sent back to the source according to the Chemotaxis mechanism. But if it does not match, the agent passes the request to the neighbouring node. To reduce communication cost, if there are more than one result matching the request, they are aggregated along the path back to the requester using the Aggregation mechanism. Aged information will be progressively discarded following the Evaporation mechanism. Inferred results are progressively aggregated while being sent back from sensors and reasoners to the application. Applications or reasoners need not know which reasoners or sensors are available in advance. The routes between an application and a reasoner or sensor are constructed based on the matching mechanism and the Gradient mechanism. Where the state of intermediate nodes along the transmission path changes due to failure or mobility, a dynamic gradient allows routing to automatically adapt when assuming a path remains open.

As an example of the above distributed situation recognition that combines both local and regional fusion of sensor data in a way that is decentralised and self-organising, consider a smart building containing a number of sensors and localised classifiers that determine whether or not a situation is occurring in the immediate proximity based only on spatially local sensor data. The left-hand side of Figure 2 illustrates this arrangement using one floor of a building. The spatial extent of each computational node is denoted by areas of different colours, with connections between nodes represented by grey bars. Distributed across this infrastructure are nodes containing location, calendar, and activity sensors, and four local situation classifiers that interpret this information.

Figure 2

(Left) The architectural layout of networked spaces in a building. (Right) An illustration of the in-network aggregation of situation classifications en route to a common destination

We consider the case where an application located on a mobile phone in the meeting room may request that this spatially local classification information be routed towards the node hosting the application. Adopting the biological communication metaphor, computational gradient structures extending from the nodes hosting the classifiers and the mobile phone application broadcast requests for sensor and classification information across the network, respectively, while Chemotaxis draws matched information towards the query origins. Using Dempster–Shafer theory as a fusion function, Aggregation is applied to integrate the classifications and their uncertainties en route to their destination (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Stevenson, Ye, Dobson and Zambonelli2012b). From this process, a global picture of the situation occurring emerges from the in-network generation of a consensus, calculated in a fully distributed fashion as data flows from its origins to its consumer. This is shown on the right-hand side of Figure 2.

Although this simple example considers a single floor of a building, the same concepts, interactions, and mechanisms can be employed at larger scales where the biological communication metaphor is applied.

3.5.1 Spatial computations

Spatial computing (Zambonelli & Mamei, Reference Zambonelli and Mamei2005; Reference BealBeal et al., Reference Beal and Viroli2013) amounts to conceive computations as occurring on a spatial substrate (a physical environment as the main example), and following the constraints that this space enacts typically in terms of topology of interactions between computing devices, as well as the timing aspects including speed/bandwidth of communications, rate of computations in each device, and so on. Situation awareness enters the picture of spatial computing precisely when the situation of interest becomes tightly dependent on (mutual) position of computations/data/events present in the network, and when actions to accordingly take are again expressed in terms of spatial computations. Various approaches surveyed by Reference BealBeal et al. (Reference Beal and Viroli2013) mostly depend on the language used to describe the spatial computation: functional approaches like Proto (Reference BealBeal Reference Beal& Bachrach, Reference Beal and Bachrach2006), rule-based like MGS (Giavitto & Spicher, Reference Giavitto and Spicher2008) and Self-Aware Pervasive Service Ecosystems (Zambonelli et al., Reference Zambonelli, Omicini, Anzengruber, Castelli, De Angelis, Di Marzo Serugendo, Dobson, Fernandez-Marquez, Ferscha, Mamei, Mariani, Molesini, Montagna, Nieminen, Pianini, Risoldi, Rosi, Stevenson, Viroli and Ye2015), Java-based like Tota (Mamei & Zambonelli, Reference Mamei and Zambonelli2008), and others featuring logic programming and process algebraic ones. A uniform way to view at how they work is to consider the paradigmatic case of the gradient data structure described in the previous section, generalise over it, and consider the notion of computational field as a first-class one. A computational field is simply a map from the network of devices to values of some data structure (Booleans, numbers, tuples, and directional vectors): other than a gradient, examples can include the field of values perceived by a homogeneously distributed set of sensors, the Boolean field of obstacles in a traffic area, and the field of directional vectors towards a POI—point of interest. Accordingly, it is key to conceive spatial computations as computational processes with the goal of creating certain computational fields (static or changing over time), possibly as a combination of existing ones by means of the constructs that the specific model/language supports. This is extremely useful in the context considered in this paper, since such computational fields can be considered as the global situation that emerges out of local interactions, out of which decisions concerning the robust and self-* provision of some service have to be taken.

3.5.2 Layering spatial computations

It is by the process of combination of basic computational fields that more structured ones can arise, providing useful services in the context of pervasive computing, or display ecosystems in particular. A series of work (Zambonelli & Mamei, Reference Zambonelli and Mamei2005; Reference BealBeal Reference Beal& Bachrach, Reference Beal and Bachrach2006; BealReference Beal, Reference Beal2010; Viroli & Damiani, Reference Viroli, Casadei, Montagna and Zambonelli2014) investigate the problem of identifying a minimal set of constructs for combining fields, typically including functional point-wise computation, repetition over time of a computation, extraction of values from neighbours, and restriction of computation in certain regions. As an example, a gradient structure can be achieved out of a source field, by iteratively applying repetition and extraction of neighbour values, and by suitably applying an additive point-wise function to make the field values increase with distance. Higher-level patterns can be devised accordingly as follows.

• ∙ By suitably preventing a gradient value from increasing over a certain level, at which point propagation is prevented, one can create a spatially bounded version of the gradient. This is useful when one wants to advertise a service in a limited portion of the network, or when a circular region around a centre has to be identified (e.g. to aggregate all its values).

• ∙ By creating a gradient out of multiple sources, and taking care that in a node only the value coming from the nearer source is retained, one can partition the network into as many regions as sources (by a so-called Voronoi partition): each region is identified by one source node (the one closest to its points), and its shape fully adapts to the position of others. One such pattern can be used to spatially divide a process or data throughout the network (Viroli & Stevenson, Reference Viroli and Damiani2012).

• ∙ By summing the two gradient structures created out of two nodes a to b, we obtain a field that has the minimum values precisely in the points in the shortest routes between them; by properly filtering and spatial expansion (again by a bounded gradient), one can devise the so-called channel pattern (Viroli & Damiani, Reference Viroli, Casadei, Montagna and Zambonelli2014), which is a region of the network connecting the two nodes, above which long-range communications can be spread. Alternatively, as of the display ecosystem scenario, such an area can be the one used to activate a steering service to guide people from a to b.

• ∙ An orthogonal problem is how we can control the actual area where the above fields spread: in fact, we might be in need of specifying that certain areas are forbidden, and the various gradients should try to circumvent it. This is achieved by simply blocking propagation in those areas (in a way actually similar to the bounded gradient) defined above. In crowd steering by display ecosystems, this can be useful to avoid certain areas when steering, for example due to some road construction.

3.5.3 Knowledge, space, and time with situation awareness

An advanced way of providing powerful situated awareness functions is based on the idea of constructing computational fields that reify or exploit not only spatial information, but also knowledge available in the networked environment (and how two knowledge items can match against each other), and timing of relevant events (either happened in past, happening right now, or expected to happen in the future). All such information can diffuse and re-aggregate so as to make the overall knowledge base and time information being available globally for intercepting the situation of interest.

The first example of this approach is developed by Montagna et al. (Reference Montagna, Viroli, Fernandez-Marquez, Di Marzo Serugendo and Zambonelli2013), aiming to guide people inside a museum towards their preferences, following the shortest and possibly quickest path using the pervasive ambient displays deployed in the museum. In this example, the gradient data structure is deviated so as to penalise areas where a certain situation arises. Accordingly, the overall gradient data structure become ‘aware’ of those situations, such that Chemotaxis can automatically take this into account when used to move data/agents towards the source. In particular, this is achieved by extending the notion of distance reified by the gradient in those areas; for example, by an additive amount of space. A paradigmatic example in the case of pervasive displays used to steer people is when some sensors on a display detect the present of a crowded area, one which we want to circumvent while suggesting a route towards the POI. Interestingly, in an open computational environment, judging what areas have to be a source of deviation, and whether a given user might be affected by it (and how), should be based on a semantic match between user preferences/profile and data available in the environment, for example, as produced by sensors. As an example, depending on a person profile, a steering service can or cannot take into consideration how crowded is a given area.

Another advanced example is to mix self-organisation and situation awareness in the context of computational fields (Stevenson et al., Reference Stevenson, Pianini, Montagna, Viroli, Ye and Dobson2013a), where discovering of resources in spatial settings exploit semantic information about such resources to properly aggregate them en route (Fernandez-Marquez et al., Reference Fernandez-Marquez, Di Marzo Serugendo, Stevenson, Ye, Dobson and Zambonelli2012b), so as to promote cooperation/competition. The basic idea is that many resources located in proximity of each other should cooperate making the whole area more appealing for the user seeking for a suitable target, while resources located far away from each other must compete, and the best one should be chosen. Accordingly, the user spreads a gradient data structure, such that information about the seek resources—in the form of a reply—can be gathered by Chemotaxis. However, as soon as two such replies reside in the same node, some degree of semantic match can activate a combination service that either drops one (competition) or aggregate them (collaboration). This can be shown to automatically select a route towards the most suitable area for the discovering at hand, computed in a fully distributed and context-aware way.

Self-organisation is also exploited by Montagna et al. (Reference Montagna, Pianini and Viroli2012) to make timing aspects enter the realm of situation awareness—relying on so-called ‘future awareness’. There, the gradient pattern is equipped with anticipative adaptation; namely, it can take advantage of the local availability of information about future events, once this has been provided by some component in charge of situation recognition (Ye et al., Reference Ye, McKeever, Coyle, Neely and Dobson2012). Such a knowledge is used in advance to stretch and deviate certain parts of a gradient structure so as to promote alternative paths that could be longer, but guarantee to eventually circumvent any forbidden area in the precise moment in time when they would not be available for transit. This pattern finds applications in the context of steering services (e.g. traffic control or crowd steering), which can rely on local predictions about future events to anticipate alternative routes that circumvent potential sources of jams. The anticipative gradient can be seen as a time-dependent computational field, obtained by functional combination of lower-level fields along with the field of ‘time passing’ that is trivially assumed to be available throughout the network. One such lower-level field is called wave, and is used to advertise the future events in just those points from which an agent moving at a given velocity could cross the future event area when it will be active—such field is time-dependent, as it shrinks down to the future event area as time passes. Another one is called shadow: it spreads from the POI and tags all the positions from which an agent would cross an obstacle area while moving towards POI. A special combination of these two fields create the anticipative gradient; it is a gradient that is identical to a standard one outside the intersection of shadow and wave, otherwise distance and orientation values in each node reflect the optimal path among the two following alternative: the one crossing the future event (and waiting behind it that it is over) and the one circumventing it.