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