Mechanisms of Self-Organization in Pervasive
Computing
Nicola Bicocchi, Marco Mamei, Franco Zambonelli
In our opinion, such extreme specialization is transitory and
Abstract—The mass deployment of sensors and pervasive more general-purpose approaches are likely to emerge soon.
computing systems expected in the next few years, will require We think that future pervasive computing systems will be
novel approaches to program and gather information from such general purpose and users will be able to install and execute
systems. Suitable approaches will be general purpose, applications both on their private pervasive computing
independent of a specific scenario and sensor deployment, and
infrastructure (e.g., in smart home scenarios), and in publicly
able to adapt autonomically to different scales and to a number
of unforeseen circumstances. This paper focuses on the
available ones (e.g., citywide infrastructures offering tourist
requirements and issues of upcoming pervasive computing information and services) [JonG05,Sri06]. In our opinion, this
scenario, and surveys current research initiatives to deal with vision is motivated by the following considerations:
them. In particular researches addressing data retrieval and
aggregation, macro-programming, and data integration in 1. Advances in the manufacturing of pervasive computing
pervasive computing infrastructures will be detailed. Overall, the devices (e.g., wireless sensors) will dramatically increase
paper illustrates our ideas on collecting information from both their performance, both in terms of computational
sensor systems and Web resources and on linking them together capabilities and energy resources [Chu06].
in overlay knowledge network offering applications 2. Advances in energy-optimized and resource-optimized
comprehensive and understandable information about their
algorithms will provide efficient mechanisms to perform a
computational environment.
number of basic services (e.g., routing), thus lowering the
Index Terms—Pervasive computing, Sensor network, RFID “resource-constraint-pressure” even further [Jon01].
tags, Self-organization. 3. Specialization hinders application development from a
software engineering point of view. To create complex,
I. INTRODUCTION dynamic and flexible services, it is mandatory to rely on
general-purpose software infrastructures facilitating the
I n the near future, computer-based systems will be
embedded in all our everyday objects and in our everyday
environments. These systems will be typically
programming task [Zam04].
All the above considerations show that general-purpose
communication enabled, and capable of coordinating with pervasive systems will be feasible in the next future, and will
each other in the context of complex mobile distributed be required to offer advanced, flexible, robust and
applications. customizable services.
Current realizations of such scenarios, mainly in research labs, Given the extreme heterogeneity of future pervasive
focus on special purpose systems, tailored for a specific computing systems, their inherent dynamism and – most
application task. This specialization comes rather directly importantly – the incredible amount of data they will be able
from the extremely limited capabilities of pervasive devices, to produce, applications will have to autonomously adapt their
that impose to rule out ancillary and general properties for the behavior to different circumstances ranging from the scale of
sake of optimization. In sensor network scenarios, for the pervasive network, to the quantity and granularity of
example, in order to be compliant with the thin battery budget information that will be available.
of each sensor, applications rely on special purpose algorithms To achieve such a flexibility, applications will have to be
tailored for a specific sensors’ deployment and for a specific highly context-aware (to understand and meaningfully interact
set of data to be measured [WerL06]. with their environment) and, to this end, they will need to
access properly represented contextual information.
Manuscript received July 7, 2006. This work was supported in part by the
project CASCADAS (IST-027807) funded by the FET Program of the In this direction, a number of recent researches try to represent
European Commission. contextual information by relying on overlay knowledge
Nicola Bicocchi is with the Dipartimento di Scienze e Metodi networks [Jel05, MamZ05, NagM04, Zam04]. Overlay
dell’Ingegneria. Università di Modena e Reggio Emilia, Italy; e-mail: knowledge networks can be regarded as distributed data
mamei.marco@unimore.it
Marco Mamei is with the Dipartimento di Scienze e Metodi structures encoding specific aspects of the application
dell’Ingegneria. Università di Modena e Reggio Emilia, Italy; e-mail: components’ operational environment. Overlay knowledge
mamei.marco@unimore.it. networks are easily accessible by the components and provide
Franco Zambonelli is with the Dipartimento di Scienze e Metodi easy-to-use context information (i.e., the overlays are
dell’Ingegneria. Università di Modena e Reggio Emilia, Italy; e-mail:
franco.zambonelli@unimore.it.
specifically conceived to support their access and fruition).
41
The strength of these overlay knowledge networks is that they technologies, currently widespread in research labs and likely
can be accessed piecewise as the application components visit to impact soon the real world, are the workhorses of this
different places of the distributed environment. This lets the vision:
components to access the right information at the right
location. 1. Sensor networks consist of several micro sensors scattered
From our perspective, “classic” overlay networks such as across an environment that collect environmental data (e.g.
spanning tree and mesh data structures (i.e., routing sound and temperature), process data (e.g., compute
distributed data structures providing components with a average and aggregate values) and wirelessly transmit such
suitable application-specific view of the network) are data to other sensors or base stations. The wireless sensor
particular examples of the more general concept of overlay networks of the near future are envisioned to consist of
knowledge networks [Jel05, IntG00, MadF02]. hundreds to thousands of inexpensive wireless nodes, each
Overlay data structures such as fields and gradients with some computational power and sensing capability,
[MamZ05], used in a number of macro-programming operating in an unattended mode. They are intended for a
mechanisms [HadM06, NagM04], are another example of broad range of environmental sensing applications from
overlay knowledge network. vehicle tracking to habitat monitoring. The hardware
This paper is devoted to the above concepts and its main technologies for these networks (low cost processors,
contribution is twofold: miniature sensing and radio modules) are available today,
with further improvements in cost and capabilities
1. We will better illustrate the scenario of general purpose expected within the next decade [WerL06].
pervasive computing showing its evolution and 2. Radio Frequency Identification (RFID) tags are small
highlighting requirements and issues. In particular, we will wireless radio transceivers that can be attached
discuss how considering the system as composed of a unobtrusively to objects as small as a watch or a
“continuum” of sensors and devices, rather than a discrete toothbrush. Tags are extremely cheap and battery-free.
collection of them, may provide useful ideas and Thus, they do not have power-exhaustion problems. Each
abstractions to deal with general purpose pervasive tag is marked with a unique identifier and provided with a
computing scenarios. tiny memory allowing to store data. Suitable devices,
2. We will survey current research initiatives applying overlay called RFID readers access RFID tags by radio for read or
knowledge networks to several autonomic and self- write operations. The tags respond or store data
organizing pervasive computing applications. In particular, accordingly using power scavenged from the signal
we will discuss how overlay knowledge networks could be coming from the RFID reader [Wan06, MamZ05]. For
suitable to the general scenario depicted above. By means example, a mobile device detecting tagged objects nearby
of this survey, we will present how different research can build a sort of database of the objects available. This
fields, ranging from data mining to distributed systems, are could have several applications in inventory and ware
beginning to merge and complement each other to provide house management [LegT06].
viable solutions to these novel scenarios.
In our opinion, these relatively static and hard-coded
The rest of this paper will be organized as follows. Section 2 applications will be soon complemented by much more
details the upcoming scenario of pervasive computing and dynamic ones that will leverage sensors and RFID tags as a
sensor networks, and illustrates the current shift from special- general, publicly-available infrastructure to “interface” with
purpose and single-owner systems, to general-purpose and the physical world. Sensor data and RFID tags will be
public pervasive infrastructures. Section 3 discusses issues accessed by handheld devices we carry on everyday and will
and current approaches to program and gather information provide us with information such as crowded pubs nearby,
from pervasive distributed systems. In particular, it dynamically-computed bus time tables and customized and
emphasizes the important role of overlay knowledge network useful information about objects and products around
in the majority of the proposals. Finally, Section 4 concludes [MamQZ06, CurG05, Bor05, NatR06]. For example, RFID
the paper presenting some future research avenues in this area. tags will possibly host scripts that will enable to tell how the
data in it should be handled. This can enable forms of parasitic
II. SCENARIO computing (the script is executed when a reader in range
As pointed out in the introduction, pervasive computing powers up the tag) [Rie06]. In addition, RFID tags can be
scenarios are moving toward general-purpose and widely coupled with sensors. A reader can power up the sensor that
available infrastructures that will enable a wide range of novel takes a measure and returns it to the reader [Wan04].
applications. In this section we are going to present the current
setting of the scenario and its possible future evolution. 3. Localization technologies are key enablers for pervasive
computing applications. Several mechanisms and
A. Current Setting technologies are currently proposed both for outdoor and
Recent advances in manufacturing and wireless indoor localization [HigB01, Sat05]. Location in the
communication are leading to the vision of pervasive and physical world remains the primary contextual information
ubiquitous computing [But06, JonG05, Sri06]. The following for almost all pervasive computing applications.
4. The Web. Given the ever improving coverage and
42
bandwidth of wireless network technologies, all kind of yellow pages) [Cas06].
application scenarios could benefit from the ever
increasing information available on the Web. For example,
it is possible can find information about the small shop
round the corner and discover the menu and the price list Sever
of that nice restaurant you have seen in that little village a
few days ago. Still, the Web is missing connection with
the physical world and with your actual physical location.
So that a query as simple such as “where is the closest Base Station
Base Station RFID Reader
Chinese restaurant?” is something that current Web cannot
answer satisfactorily. There is a lot of work in this kind of
location-based services, but still some general purpose
architecture to implement the idea is missing [Esp01,
Eag05, HarK05].
Mote Sensor
On the basis of the above considerations, future pervasive Mote Sensor
infrastructures will be hosting several services and will Mote Sensor
integrate data from various sources, ranging from RFID,
sensor networks and Web resources (see Fig. 1). Users in this Figure 1. General pervasive architecture
scenario, will be able to access – via a number of handheld B. Future Vision
and wearable devices – several services dispersed in the
environment. The technologies described above could lead, in the next
future, to a scenario in which sensors, actuators, memory and
computational infrastructures will seamlessly wrap the real
x Users could query, either directly or via a proper base
world. This will allow to collect and handle data coming from
station, sensors in the environment to get various
an unpredictable number of devices (sensors and Web
information such as traffic reports, weather conditions, and
resources) that will produce a sort of enriched perception of
environmental parameters (e.g., temperature, light-
the world. With such an infrastructure in place, several
condition) [Bal06, Sri06].
interesting applications, in which users will be able to
x Users could join profile matching services and applications.
perceive the word beyond their five senses, will become
Profile matching applications consist of a sensor network
feasible. For example, while walking on a street, it will be
composed of the smart-phones of the persons joining the
possible to perceive (i.e., get real-time information) on how
application (note that a Bluetooth phone can be easily
much the restaurants nearby a crowded. In a similar way, it
regarded as a wireless sensor, in that it can provide various
will be always possible to “sense” where friends and relatives
data to other devices around). Such sensors will monitor
are located, so as to arrange for meeting on the fly.
their surrounding environment looking for nearby
From our perspective, there are two main streams of research
“compatible” persons and notify their users upon positive
fueling this vision:
matches. [Eag05].
x Users could benefit of a number of automated pervasive 1. Novel approaches are needed to provide human users and
services to complete economic transaction and acquire application components with “extra-sensory” information
information. For example, RFID allows the vision of without overloading their cognitive capabilities. With
cashier-free retailers where a user just enters a retailer, regard to human users, research on wearable computer is
takes what he needs and, when exiting, RFID readers developing mechanisms to enable a person to see (by
installed at the retailer door read the items being taken and means of suitable see-through visors) computer-generated
charge the customer credit card accordingly. RFID could images overlaid to the physical world. Such images can
also allow to store information where they will be most augment the word by providing additional information
useful. For example, information on goods and products [Dan06]. For example, they could show directions overlaid
could be stored in RFID tags stuck at that product [Bor05, to the actual environment, or provide personal information
NatR06]. overlaid to the person we are actually talking with. With
x Users could complement and integrate all the above data regard to application components, suitable software
and information by means of suitable Web resources. For infrastructures are needed to represent context information
example, a sensor network detecting some kind of in a way that will be easy for the components to
polluting agent could integrate collected data with a map understand and use [MamZ05].
showing nearby industrial implants to discover possible 2. It is fundamental to actually store and manage that
causes of the pollution, or in a map showing natural information at the infrastructure level. Research on RFID
reserves to predict dangerous effects [JRDMS]. Similarly, tags and sensors infrastructures, is a promising approach
a group of friends could decide to share with each other (complementary to the previous one) leading to this vision.
their actual GPS locations, and to display them on a map In this context, the idea is to store and later retrieve
which highlights pubs and bars (coming from Web-based information in the RFID tags and sensors that are likely to
43
populate (and saturate) our physical environment. Such an The resulting scenario is that of a hierarchy of an arbitrary
infrastructure could be used to enrich the world with number of overlays representing context information at
context information that could be retrieved properly different level of granularity. Application components,
[MamQZ06]. For example, the infrastructure would allow depending on their task, decide at which level to consider the
to store “virtual” post-it notes across an environment to be context. Lower-level information will be aggregated to the
found later on. proper level of abstraction. Higher-level information will be
possibly contextualized to that level, and all this information
It is rather clear that such a vision implies a huge amount of will be integrated together in coherent view supporting
information and data pervading the physical world that (given application tasks.
its scale) requires novel methodologies to be dealt with. In our Although the above description is at the level of modeling,
opinion, a paradigm leading to the development of proper and data aggregation, contextualization and integration
methodologies, in this context, could be based on the mechanisms could be realized via whatever approach, in
“continuum” abstraction [BeaB06]. Following this approach practice the model easily support a hierarchical architecture
the system is designed having in mind a continuum of data where higher-level servers collect and provide data at a certain
sources (rather than a discrete network of devices) and so the level of granularity. Adopting this viewpoint, at the top level
abstraction being realized have to scale to an arbitrary number of Fig. 2, we have globally accessible Internet server
of devices. Of course to deal with such kind of large scale providing worldwide aggregated information. At the lower
systems, autonomic and self-organization principles are layers, there are servers providing more and more specific
needed [Dob07]. This is because managing the system at a data (e.g., state-wide, city-wide, building-wide data). At the
fine-grained scale and addressing individual components will bottom-layer there are the individual sensors offering
not be feasible (with the continuum abstraction in mind, the extremely localized – but extremely detailed and up-to-date --
very concept of individual component tend to vanish), and so information.
autonomic and self-organization mechanisms – where Whatever the architecture, in order to realize the conceptual
individual components manage themselves -- have to be model in Fig. 2, it will be fundamental to rely on self-
introduced. organization and autonomic principles. In fact, to guarantee
In particular, we envision an architecture, like the one robustness and scalability, the overlay knowledge network
depicted in Fig. 2. There, a countless number of sensors will have to maintain its coherency despite network glitches,
(wireless mote sensors, RFID, smart phones, and yet-to-come sensors failures, the addition and removal of part of
devices) enrich the world with digital information. This layer knowledge and other kind of contingencies.
(represented as the bottom layer in Fig. 2) will be constituted
by a huge number of heterogeneous and dynamically varying
devices. The data at this basic level is at the finest possible
granularity, and because of that will be hardly manageable and
understandable by application components (i.e., too much
data, too sparse knowledge).
Overlay knowledge networks are distributed data structures
encoding specific aspects of the application components’
operational environment. Overlay knowledge networks are
easily accessible by the components and provide easy-to-use
context information [MamZ05]. These overlay knowledge
networks come into play to organize the data of the bottom
layer into higher-level and more semantically expressive
concepts. An example of this idea would be an overlay
knowledge network that aggregates the data produced in a
region of the underlying network to offer application
components a single aggregated value (e.g., the average)
representing the whole region. In other words, data produced
by the bottom sensors can be aggregated at different level of
abstractions. This aggregation produce discrete data elements
each one managing portions of the continuum sensor space. Figure 2. Continuum pervasive network with an arbitrary
These elements of the overlay knowledge network are number of overlays describing context at different
represented in the higher layers of Fig. 2 and the upward granularity
arrows represent the process of creating higher-level concepts
from low-level sensors. III. ISSUES AND CURRENT APPROACHES
This upward direction is not the only possible. In several Several new technologies and mechanisms are needed to
situation, overlay knowledge network need to integrate and fulfill the above vision and to create general purpose
contextualize high-level concepts to a lower layer using sensor pervasive applications. In particular, we think that the main
data. This integration is represented by the bottomward arrows challenge is to provide applications with suitable overlay
in Fig. 2.
44
knowledge networks to gather, understand and exploit context route the message towards the destination. When compared to
information at the proper level of abstraction for their local processing of data, wireless transmission is extremely
application task. If a suitable context-representation is expensive. Researchers at the University of California,
available, often the application task becomes easy, since estimate that sending a single bit over radio is at least three
application components see clearly from their context how to orders of magnitude more expensive than executing a single
achieve the task [MamZ05]. instruction [ShrP04]. Last but not least, this approach is very
From our perspective, there are three main research fields that sensitive to reading errors and sensors faults. If a node, broken
are fruitfully tackling the above problems by exploiting or malicious, produces fake data, there is no straightforward
overlay knowledge networks. way to filter it out.
To overcome the above problems, in-network filtering,
1. Data Retrieval and Aggregation comprises a number of processing and aggregation techniques can be used to
researches trying to get data from a distributed sensors in conserve the scarce energy resources and improve data
an efficient way. In this context, overlay knowledge quality. From the information sink point of view in network
networks are used to create the routing structures to collect data aggregation has two main advantages. The first one
and aggregate data. consist on a reduction of the potentially overwhelming data
2. Macro Programming deals with programming a streams produced by the sensors. The second one, due to the
distributed system without explicitly defining single activity of filtering and processing, is to reduce the complexity
entities activities, but letting a compiler or a distributed and the amount of data gathered letting further analysis more
middleware to translate high-level task into individual manageable. Probably, during the next few years, due to the
component activities in an automatic way. In this context, increase of the size and density of sensor networks these
overlay knowledge networks are used to create regions and advantages will quickly become determinant and every
areas in a distributed systems allowing to suitably application will use some mechanisms where some sort of “in
differentiate application execution disregarding individual network” aggregation will be implemented natively.
components’ activities.
3. Data Integration allows to integrate data from various
sources (Web services and pervasive sensors) to offer
application components an all-encompassing view of the
operational environment (context). In this context, overlay
knowledge networks are used to actually represent the
integrated view that will be provided to application
components.
In the next subsections we will present a survey of current
research initiatives in these areas, showing also how the
different areas themselves complements one another and
pursue from different perspective the same ultimate goals.
Figure 3. A spanning tree is created in the sensor network
A. Data Aggregation and Retrieval to route the collected data to a root node.
The main goal of a sensor network (and of the majority of
pervasive computing systems) is to collect data from the The work described in [Jel05] distinguishes reactive and
environment and to suitably present the data to application proactive protocols for computing aggregate functions in a
components. For this reason several researches try to devise sensor network.
mechanism to retrieve, collect and possibly aggregate data
form a sensor network. The most common approach to collect x Reactive protocols try to respond on demand to queries
data from the network consists in deploying data collector injected by nodes. If the answer is found in some region of
(i.e., sink) nodes which subscribe to some type of data flowing the network, it is routed directly to the issuer node (see
from sensing nodes about some particular phenomena. Once a Fig. 3). Examples of this approach are well described in
data collector is registered to the network, each node starts to [IntG00, MadF02].
periodically send data to it. For example there may be a sink x Proactive protocols continuously provide aggregated data
interested in receiving data from a particular region “A” using some function and aim to diffuse meaningful values
between 2pm and 6pm if the temperature in that zone exceed on every nodes in the networks in an adaptive way (see
50°. Each day, during the selected time frame, sensors which Fig. 4). “Adaptive” means that if sensed values change
detect temperatures over the selected threshold will send data over time, the output of the algorithm should track
to the sink. This is the simplest possible approach to retrieve variations reasonably quickly. Proactive protocols are
data but has several disadvantages. In general since different often useful when aggregation is used as a building block
sensor nodes detect the same phenomenon, it is likely that for completely decentralized solutions to complex tasks
there will be an high degree of redundancy in the data flowing [Jel05].
to the sink from different sources. Moreover each node
located between a source and sink has to spend energy to
45
The above computation of aggregate functions is a key
building block for many applications. In fact, aggregate data
can be regarded as a simplified view of the components
operational environment. Components may find simpler to
access the aggregate value rather than distill the individual
sensor readings.
Some examples of most used aggregated values are network
size, average load, average uptime, location and description of
hot spots, and so on. Local access to global information is
often very useful, if not indispensable for building
applications that are robust and adaptive. For example a fire
alarm system has to trigger an alarm if the average
temperature inside a building exceed a certain threshold or a Figure 4. A gossip algorithms is run by nodes to aggregate
distributed storage system has to know the overall free space data and report them back to an inquiring node.
over various device before processing a write() request. To
reach the goal of a local access to global network features we In the next paragraph we briefly highlight some general
have mainly two choices. examples of either reactive and proactive algorithm
applications.
x The first one consists of gathering on some sinks all the Data aggregation and retrieval is at the basis of a number of
(aggregated on not) sensor readings. After that we have to relevant application in the context of pervasive computing and
diffuse the global aggregated values into the overall sensor network. Currently the main application of sensor
network. This approach is simple and straightforward but networks is environmental monitoring. This application
has several serious limitations. The main one is the poor consist of deploying a suitable number of ad hoc wireless
scalability. In fact as the network size grows, the amount connected sensors in a region. Such devices periodically read
of data that the sink has to manage become quickly some environmental properties and route the acquired data
overwhelming. towards a base station that is in charge of gathering and
storing them. A good example of this kind application has
x On the other side we can use gossip based aggregations
been deployed on a natural reserve island in front of the
methods [Jel05]. Using this kind of algorithm local sensor
Maine coast [Pol06]. There a hundred of sensors collect data
readings are not to be convoyed to a sink, but can stay on
from the birds nest, monitoring their micro climate. The data
sensors. The core of these protocols is a simple gossip-
being collected are sent over the Internet and publicly
based communication scheme in which each node
available over the web.
periodically selects some other random node to
Another promising application, which has not yet been fully
communicate with. During this communication the nodes
developed, is object tracking. This activity consists of
update their local approximate values by performing some
recognize and subsequently track moving targets over a
aggregation specific and strictly local computation based
monitored field. To achieve this task sensors do not have to
on their previous approximate values. After some
collect massive amount of data to a central station for further
iterations the local approximate value converge to the
analysis, but the network have to process sensed information
global value. The main advantages of these methods are
and produce a simplified view of the physical world in which
that they are simple, scalable and provide local access to
the object being tracked is readily visible. This application has
global values without any additional burden.
been originally conceived in the military setting to drive
vehicles in un-trusted areas. A promising new approach of this
The last reported feature is really important in our vision. In a
application involves multi sensory tracking. With this
world full of sensors and actuators, users will need simple
mechanism the same phenomenon can be recognized by
(i.e., aggregated) representations of the area of the network
means of different sensory inputs. For example, a car reaching
where they will be immersed. Using traditional routing based
a blind spot in a camera network could be tracked using sound
aggregation algorithm, due to their inherent “reactive” nature,
sensors.
will require, for each query, the building of a dedicated tree
and to wait answers from an unknown number of sensors B. Macro Programming
(which will may be very high). Instead, using gossip based A key challenge in pervasive computing is to provide
algorithm, any user will be able to get, without any additional powerful programming models to facilitate the development
burden for the network, a simplified view of the area. of applications in dynamic and heterogeneous environments.
In general, the resulting aggregate value distributed across the One of the main conceptual difficulties is that we have direct
network becomes an instance of overlay knowledge network. control only on the agents’ local activities, while the
The overlay in fact extracts low level sensor reading to higher application task is often expressed at the global scale
level concepts (i.e. aggregate values). [Zam04]. Bridging the gap between local and global activities
is not easy, but it is possible: distributed algorithms for
autonomous sensor networks like the ones presented in the
previous subsection have been proposed and successfully
46
verified, routing protocols is MANET (in which devices a handle to) all the sensor in a given geographic region
coordinate to let packets flow from sources to destinations) (described e.g. by its latitude and longitude). A low-level
have already been widely used. The problem is still that the distributed middleware in then in charge to set-up suitable
above successful approaches are ad-hoc to a specific routing structures to actually address the proper sensors.
application domain and it is very difficult to generalize them Abstract Regions (AR) [NewA04] is another macro
to other scenarios. programming approach to define regions in a sensor network.
One promising research initiative in this direction is macro Rather than focusing on geographic regions like in Spatial
programming. The idea is to specify the global application Programming, AR focus on network regions (e.g., x-hop
tasks to be achieved and leaving to a compiler or a distributed neighbors, spanning tree and planar meshes). A high-level
middleware [HadM06, Nag02, NagM04] the tasks of mapping language allows to specify the network region, while low level
these global task into individual component activities. To algorithm create the actual routing structure to handle the
build these languages there are two fundamental challenges: proper nodes.
Regiment is a functional macro programming [WelN04]
x devise a global language suitable for a relevant class of language that generalize both the previous approaches.
applications Regiment allows to define regions in the network able to
x devise a set of distributed algorithms to map the language represent spatially distributed, time-varying collections of
into the component activities. node state. The programmer uses the language to express
interest in a group of nodes with some geographic, logical, or
The above two tasks aim at hiding from the programmer low topological relationship, such as all nodes within k radio hops
level details such as the heterogeneity and the scale of the of some anchor node. A distributed middleware is then in
underlying network. charge to map the regions into suitable sensor-level
In the last few years a number of research initiatives coordination protocols. Similar approaches to define regions
addressing macro programming have been proposed in several in a distributed system according to spatial and functional
application scenarios. characteristics have been presented in [BecH04]
In the Amorphous Computing project [Nag02], a macro- A more comprehensive survey of currently proposed macro-
programming language is used to control shape formation in a programming languages can be found in [HadM06].
reconfigurable sheet composed of thousands of identically- In general, all the reported macro-programming approaches
programmed, locally-interacting robotic agents. The desired uses suitable overlay knowledge networks to control the
global shape is specified at an “abstract” level as a folding distributed program. In most of the proposals, overlay
construction on a continuous sheet of paper (i.e., origami). knowledge networks are used to define the regions where the
This construction is then automatically compiled to produce components activities will be different. In Spatial
the program run by the identically-programmed agents. The Programming, for example, the overlay knowledge network is
global language allows to define the regions where the sheet represented by the data structure identifying the region where
has to fold, leaving to the compiler the identification of the data should be collected by the application.
low level action needed to actually reconfigure (i.e., bend) the To create complex, dynamic and flexible services, it is
robots. mandatory to rely on general-purpose software infrastructure
Similar approaches for the control of shape and motion in a facilitating the programming task. The ability to program a
modular robot (i.e. a collection of simple autonomous actuator distributed system without explicitly and directly defining
with few degrees of freedom connected with each other) have individual entities’ activities will be a fundamental asset in
been recently proposed [StoN04, WerB06]. In these this direction.
approaches a global description of the shape to be formed or C. Data Integration
of the gait to be followed is provided to the robot, either by
representing the shape in some coordinate frame, or by Pervasive computing applications will be naturally integrated
adopting a description functionally specifying how the robot with Web services and Internet resources. Not only Web
has to bend its actuators to move. Such a global description is services will be a natural technology to access pervasive
then compiled into low level messages and actions to drive applications remotely, but it could also provide further context
and coordinate the individual modules. information to the pervasive device. For example, sensors
TinyDB [MadF02] and Cougar [YaoG02] provide a high-level could get from the Internet the average temperature of the
SQL or XML-based query interface to sensor network data. region they are in, and compare their sensor readings with that
The query is expressed by means of a high-level language average. With this regard, we think that in the next future
indicating the data to be gathered in a declarative way. A application will integrate together data coming from the
compiler translates the query into the low-level sensor Internet and data coming from the real world (sensors) and
activities needed for the creation of the proper data collection actually merge it together in a coherent framework providing
and aggregation distributed algorithms. advanced context-aware applications.
Spatial Programming (SP) [Bor04] is a macro programming In this context, overlay knowledge networks are used to merge
approach to program a sensor network. This approach allows the collected data together, and to provide such data to
to define regions in the network adopting a high-level application components in a coherent view.
semantic. In SP, for example, it is possible to address (and get A number of recent projects from different research
communities (data mining, distributed systems, semantic Web,
47
Web services, etc.) are tackling the challenge of data user movements and have them displayed on the map of the
integration across multiple providers. visited place. Moreover, the support for RFID allows to access
One interesting research in this area is described in [PerP04]. likely-to-be-soon-available tourist information stored in RFID
The goal of this project is to develop a context-awareness tags attached to art-pieces. From the diary perspective, this
system to detect and infer domestic activities performed by the allows to store the visited art-pieces’ location together with
users. The proposed approach is to infer the activities of the their description on the journey map. In addition, our service
user on the basis of the objects he touches. For example, by could also provide with important logistic information. For
sensing that the user touches a “teapot”, some “teabags”, example, the action of reading the tag of the user’s car at a
“glasses” and “spoons”, the system can infer that the user’s certain location triggers a new car-placemark on Google Earth
action is “making tea”. This kind of knowledge could be of showing the actual position of the car. This allows the tourist
use in a number of smart-home scenarios. To implement such to easily recall where the car has been parked.
an idea, the system relies on RFID tags associated to (and Another service, allows multiple users to share their list of
identifying) everyday objects, and gloves integrated with placemarks and their current location. Again, this service can
RFID reader worn by the user. This allows the system to be employed in several scenarios, and we focused on
detect, rather naturally, what the user is touching. supporting a group of tourists cooperatively visiting a place.
This stream of data coming from pervasive devices requires Such a situation applies to a class of students or to a group of
models of activities to detect what the user is doing. Such boy-scouts, where each person can visit the place
models are automatically mined from the Web. In particular, independently, while keeping in touch and sharing
the system connects to specific “How to” sites, describing information with the other members. To this end the service
how to perform a specific activity, extracts the labels allows to share GPS data with other members and with the
associated to the object being used, and creates a Bayesian group leader (e.g., the teacher may be in need of monitoring
network describing probabilistically the objects involvement the location of all the students). Moreover, placemarks pointed
in the different activities. The model is finally, checked by one person may be shared across al the group. This can be
against the data coming form the RFID reader to infer the useful to share opinions or interesting sightings, but also to
activities being carried on. easily agree on some meeting points. For example, by sharing
In our opinion, this project is a perfect example of the fact that placemarks, all the users can spot a suitable place (e.g., a pub)
pervasive and Web resources complement each other, and by that is in the middle of them and agree to meet there (see
integrating them, it is possible to obtain novel and powerful Figure 5).
services. Other approaches in this direction, developed by other
Another relevant approach is presented in [Eag03]. The goal research groups, [PatL04] combine GPS data and maps to
of this work is to infer users context by capturing their speech. create a probabilistic model of the user activities. This
The voice of the user is record by a PDA carried on by the approach allows to the system to learn the user motion routine
user. The voice signal is sent over a wireless network to a (e.g., where does he go, where does he park the car, etc.) and
server that process the signal and transcribes the speech. The possibly to check anomalies against the learned trend.
server connects to a Web service called Concept Net [Liu04] file1.kml
that is based on a knowledge network describing common-
sense activities. Concept Net is, in fact, a huge repository of
commonsense sentences (e.g., you’d order food in a New Y ork C ity
restaurant) and a suitable API to access and mine the Ne w Yor k Cit y
repository.
-74.0 06393 ,40.7 14172 ,0
By providing ConceptNet with the speech transcription, the
service is able to infer the most likely context for the user. For
example, the speech: “Hi, today I’m going to have a
cheeseburger and a beer” would let ConceptNet infer that the
View KML on the Web. Reload
user context is “ordering food at a resturant”. Such the file to see any change
information is then sent back to the PDA for further actions.
Another interesting mechanism to combine sensor data and
Web information involves the usage of GPS as sensors and
Web-retrieved maps from open GIS-tool like Google Earth
(http://earth.google.com). In [Cas06], we describe two
services in this direction. A first service allows a user
equipped with a RFID reader and a GPS device to see his RFID Reader
actual location and past movements, and to dynamically create Figure 5. Integration of GPS data and Web maps.
Google Earth placemarks of the tagged objects being read
with the RFID reader at the right location. This service can be Finally, another source of information that researchers are
fruitfully employed in a number of situations. In particular, we trying to integrate is that coming from images widely
focused on the scenario in which a tourist wants to available and tagged by services like Flickr (www.flickr.com).
automatically build and maintain a diary of his journey. To The idea at the core of some recent researches is to try to
this end, the proposed service allows to keep track of all the match pictures taken from cameras with those available on the
48
Internet. This would allow to get information about objects information in a general way? How can we retrieve and access
without the need of tagging them artificially. For example, the such huge amount of knowledge? Which kind of autonomic
image of a tower taken by a camera phone could be matched algorithms should we enforce to add robustness and self-
against a data base of images to properly recognize it as the organization properties to those systems?
Pisa leaning tower [Jia06]. Our future research within the CASCADAS European project
All the above examples show rather clearly that the approach will try to address some of these questions.
of integrating resources and data from pervasive systems and
Web resources in a promising research avenue. REFERENCES
[Bal06] H. Balakrishnan, S. Madden, V. Bychkovsky, K. Chen, W. Daher, M.
IV. CONCLUSIONS Goraczko, H. Hu, B. Hull, A. Miu, E. Shih, "CarTel: A Mobile
Sensor Computing System", MIT CSAIL Report, 2006.
In this paper we presented our vision for next future pervasive [BeaB06] J. Beal, J. Bachrach, "Infrastructure for Engineered Emergence on
computing systems. In our opinion, these systems will be Sensor/Actuator Networks", IEEE Intelligent Systems, 21(2):10-
general purpose and users will be able to install and execute 19,2006
applications both on their private pervasive computing [BecH04] C. Becker, M. Handte, G. Schiele, K. Rothermel, “PCOM - A
Component System for Pervasive Computing”, IEEE
infrastructure (e.g., in smart home scenarios), and in publicly International Conference on Pervasive Computing and
available ones (e.g., citywide infrastructures offering tourist Communications, Orlando (FL) ,USA , 2004.
information and services). Given the extreme heterogeneity of [Bor04] C. Borcea, D. Iyer, P. Kang, A. Saxena, L. Iftode, "Spatial
this scenario, its inherent dynamism and – most importantly – Programming using Smart Messages: Design and
Implementation", International Conference on Distributed
the incredible amount of data the system will be able to Computing Systems, Tokio, Japan, 2004.
produce, applications will be required to match and comply [Bor05] G. Borriello, “RFID: Tagging the World”, Communication of the
those characteristics. Applications will have to autonomously ACM, ACM Press, 48(9):34-79, 2005.
adapt their behavior to different circumstances ranging from [But06] D. Butler, “2020 Computing: everything, everywhere”,
news@nature.com, 22 March 2006.
the scale of the pervasive network, to the privacy-level being [Cas06] G. Castelli, M. Mamei, A. Rosi, F. Zambonelli, “Browsing the
requested by the users. To achieve such a flexibility World: bridging pervasive computing and the Web”,
applications will have to be highly context-aware (to International Workshop on Ubiquitous Geographical Information
meaningfully interact with their environment) and autonomic. Services, Munster, Germany, 2006.
[Chu06] C. Park, P. Chou, Y. Sun, “A Wearable Wireless Sensor Platform
To this end, they will be able to gather relevant context for Interactive Art Performance”, IEEE International Conference
information both from the pervasive network sensing the on Pervasive Computing and Communications, Pisa, Italy, 2006.
environment and from global-accessible Internet services. We [CurG05] C. Curino, M. Giani, M. Giorgetta, A. Giusti, A. Murphy, G.
also introduced how considering the system as composed of a Picco, “TinyLIME: Bridging Mobile and Sensor Networks
through Middleware”. IEEE International Conference on
“continuum” of sensors and devices, rather than a discrete Pervasive Computing and Communications, Kauai Island, HW
collection of them, may provide useful ideas and abstractions (USA), 2005.
to deal with the above challenges. [Dan06] W. Daniel, T. Pintaric, F. Ledermann, S. Dieter, "Towards
In addition, we presented the key mechanisms and researches Massively Multi-User Augmented Reality on Handheld
Devices", International Conference on Pervasive Computing,
trying to fulfill the above vision: Munich, Germany, 2005.
[Dob07] S. Dobson, S. Denasiz, A. Fernandez, D. Gaiti, E. Gelenbe, F.
x Retrieve and aggregate data will provide developers with Massacci, P. Nixon, F. Saffre, N. Schmidt, F. Zambonelli, "A
advanced tools to get data from a distributed system in an Survey of Autonomic Communications", ACM Transactions on
Autonomous and Adaptive Systems, ACM Press, to appear,
efficient way. 2007.
x Macro Programming a distributed system deals with [Eag03] N. Eagle, P. Singh, and A. Pentland, “Common sense conversations:
programming a distributed system without explicitly understanding casual conversation using a common sense
defining single entities activities, but letting a compiler or database”. Workshop on Artificial Intelligence, Information
Access, and Mobile Computing, Acapulco, Mexico, 2003
distributed middleware to translate high-level task into [Eag05] N. Eagle and A. Pentland, "Social Serendipity: Mobilizing Social
individual component activities. This will allow Software", IEEE Pervasive Computing, IEEE CS Press, 4(2):28-
developers to design systems composed of a huge number 34, 2005.
of components that will be able to carry on complex [Esp01] F. Espinoza, P. Persson, A. Sandin, H. Nystrom, E. Cacciatore,
M. Bylund, "GeoNotes: Social and Navigational Aspects of
coordinated activities. Location-Based Information Systems", International Conference
x Integrate data gathered from various sources allows to offer on Ubiquitous Computing, Atlanta (GE), USA, 2001.
application components a coherent view of their context. [HadM06] S. Hadim, N. Mohamed,"Middleware Challenges and Approaches
for Wireless Sensor Networks", IEEE Distributed Systems
Online, 7(3), 2006.
In particular, we tried to present how the concept of overlay [HarK05] R. Hariharan, J. Krumm, E. Horvitz, "Web-Enhanced GPS",
knowledge networks may be at the basis of most of the International Workshop on Location and Context Awareness,
proposal, and how overlay knowledge network may represent Munich, Germany, 2005.
a framework to develop applications in future pervasive [HigB01] J. Hightower, G. Borriello, "Location Systems for Ubiquitous
Computing", IEEE Computer, IEEE CS Press, 34(8):57-66,
computing scenarios. 2001.
In our opinion, these researches are only at the beginning of [IntG00]C. Intanagonwiwat, R. Govindan and D. Estrin, “Directed diffusion:
addressing satisfactorily the requirements of future scenarios A scalable and robust communication paradigm for sensor
and several questions remain open: How to represent context
49
networks”, International Conference on Mobile Computing and [PatL04] D. Patterson, L. Liao, K. Gajos, M. Collier, N. Livic, K. Olson,
Networking, Rome, Italy, 2000. S. Wang, D. Fox, H. Kautz, “Opportunity Knocks: a System to
[Jel05] M. Jelasity, A. Montresor, O. Babaoglu, “Gossip-Based Aggregation Provide Cognitive Assistance with Transportation Services”,
in Large Dynamic Networks”, ACM Transaction on Computer International Conference on Ubiquitous Computing, Tokyo,
Systems, ACM Press, 23(3):219-252, 2005. Japan, 2004.
[Jia06] M. Jia, X. Fan, X. Xie, M. Li, W. Ma, "Photo-to-Search: Using [PerP04] M. Perkowitz, M. Philipose, D. Patterson, K. Fishkin. “Mining
Camera Phones to Inquire of the Surrounding World", Models of Human Activities from the Web”. International World
International Conference on Mobile Data Management, Nara, Wide Web Conference, New York (NY), USA, 2004.
Japan, 2006. [Pol06] J. Polastre, R. Szewcyk, A. Mainwaring, D. Culler, J. Anderson,
[Jon01] C. Jones, K. Sivalingam, P. Agrawal, J. Chen, "A Survey of "Analysis of Wireless Sensor Networks for Habitat Monitoring",
Energy Efficient Network Protocols for Wireless Networks", Wireless Sensor Networks, Kluwer Academic Publishers, 2004.
Wireless Networks, Kluwer Academic Publisher, 7(4):343-358, [Rie06] M. Rieback, B Crispo, A. Tanenbaum, “Is Your Cat Infected with a
2001. Computer Virus?”, IEEE International Conference on Pervasive
[JonG05] Q. Jones, S. Grandhi, “P3 Systems: Putting the Place Back into Computing and Communications, Pisa, Italy, 2006.
Social Networks”, IEEE Internet Computing, IEEE CS Press, [Sat05] I. Satoh, “A Location Model for Pervasive Computing
9(5):38-46, 2005. Environments”, Proceedings of IEEE International Conference
[JRDMS] James Reserve Data Management System, on Pervasive Computing and Communications, Kauai Island,
http://dms.jamesreserve.edu HW (USA), 2005.
[LegT06] C. Legner, F. Thiesse, “RFID-Based Facility Maintenance at [ShrP04] Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal
Frankfurt Airport”, IEEE Pervasive Computer, IEEE CS Press, and Subhash Suri, “Medians and Beyond: New Aggregation
5(1):34-39, 2006. Techniques for Sensor Networks,” ACM Conference on
[Liu04] H. Liu, P. Singh, "ConceptNet: A Practical Commonsense Embedded Networked Sensor Systems (SenSys 2004), 2004.
Reasoning Toolkit", BT Technology Journal, Kluwer Academic [Sri06] M. Srivastava, M. Hansen, J. Burke, A. Parker, S. Reddy, G.
Publishers, 22(4):211-226, 2004. Saurabh, M. Allman, V. Paxson, D. Estrin, “Wireless Urban
[MadF02] S. Madden, M. Franklin, J. Hellerstein, W. Hong. "TAG: A Tiny Sensing Systems”, CENS Technical Report #65 , 2006.
AGgregation Service for Ad-Hoc Sensor Networks", Symposium [StoN04] K. Stoy, R. Nagpal, "Self-Reconfiguration Using Directed Growth",
on Operatign Systems Design and Implementation, Boston (MA) International Symposium on Distributed Autonomous Robotic
,USA, 2002. Systems", Toulouse, France, 2004.
[MamQZ06] M. Mamei, R. Quaglieri, F. Zambonelli, “Making Tuple Spaces [Wan04] R. Want, “Enabling Ubiquitous Sensing with RFID”, IEEE
Physical with RFID Tags”, ACM Symposium on Applied Computer, IEEE CS Press, 37(4):84-86, 2004.
Computing, Dijon, France, 2006. [Wan06] R. Want, “An Introduction to RFID Technology”, IEEE
[MamZ05] M. Mamei, F. Zambonelli, “Physical Deployment of Digital Pervasive Computer, IEEE CS Press, 5(1):25-33, 2006.
Pheromones Through RFID Technology”, IEEE Swarm [WelN04] M. Welsh, R. Newton, "Region streams: functional
Intelligence Symposium, Pasadena (CA), USA, 2005. macroprogramming for sensor networks", International
[Nag02] R. Nagpal, "Programmable Self-Assembly Using Biologically- Workshop on Data Management for Sensor Networks, Toronto,
Inspired Multiagent Control", Joint Conference on Autonomous Canada, 2004.
Agents and Multi-Agent Systems, Bologna, Italy, 2002. [WerB06] J. Werfel, Y. Bar-Yam, D. Rus, R. Nagpal, "Distributed
[NagM04] R. Nagpal, M. Mamei, "Engineering Amorphous Computing construction by mobile robots with enhanced building blocks",
Systems", Methodologies and Software Engineering for Agent International Conference on Robotics and Automation, Orlando
Systems, Kluwer Academic Publishing, 2004. (FL), USA, 2006.
[NatR06] B. Nath, F. Reynolds, R. Want, “RFID Technology and [WerL06] G. Werner-Allen, K. Lorincz, M. Ruiz, O. Marcillo, J. Johnson,
Appliations”, IEEE Pervasive Computing 5(1):22-69, 2006. J. Lees, M. Welsh, “Deploying a Wireless Sensor Network on an
[NewA05] R. Newton, Arvind, M. Welsh, "Building up to Active Volcano.”, IEEE Internet Computing, IEEE CS Press,
Macroprogramming: An Intermediate Language for Sensor 10(2):18-25, 2006.
Networks", International Symposium on Information Processing [YaoG02] Y. Yao, J. Gehrke, "The Cougar approach to in-network query
in Sensor Networks, Los Angeles (CA), USA, 2005. processing in sensor networks", ACM Sigmod Record, ACM
Press, 31(3):9-19, 2002.
[Zam04]F. Zambonelli, V. Parunak, "Towards a Paradigm Change in
Computer Science and Software Engineering: a Synthesis", The
Knowledge Engineering Review, 18(4), 2004.
50