Vehicle to Vehicle Services Service oriented architecture for pervasive computing systems with emphasis on vehicle to vehicle applications
Jeppe Brønsted
PhD Dissertation
Department of Computer Science University of Aarhus Denmark
Vehicle to Vehicle Services Service oriented architecture for pervasive computing systems with emphasis on vehicle to vehicle applications
A Dissertation Presented to the Faculty of Science of the University of Aarhus in Partial Fulfillment of the Requirements for the PhD Degree
by Jeppe Brønsted August,
A
As computing devices, sensors, and actuators pervade our surroundings, new applications emerge with accompanying research challenges. In the transportation domain vehicles are being linked by wireless communication and equipped with an array of sensors and actuators that make is possible to provide location aware infotainment, increase safety, and lessen environmental strain. is dissertation is about service oriented architecture for pervasive computing with an emphasis on vehicle to vehicle applications. If devices are exposed as services, applications can be created by composing a set of services and governing the flow of data among them. In pervasive computing, composing services is, however, not the whole story. To fully realize their potential, applications must also deal with challenges such as device heterogeneity, context awareness, openendedness, and resilience to dynamism in network connectivity, mobility, and availability of services. e dissertation consists of two parts. Part I gives an overview of service oriented architecture for pervasive computing systems and describes the contributions of the publications listed in part II. We investigate architecture for vehicular technology applications by looking at network architecture, middleware architecture, and the interplay between the architecture and the business model. Data dissemination in vehicular networks is investigated by looking at different dissemination models and protocols, and by describing how data dissemination protocols can be evaluated. Service composition mechanisms for pervasive computing are categorized and we discuss how the characteristics of pervasive computing can be supported by service composition mechanisms. Finally, we investigate how to make pervasive computing systems capable of being noticed and understood by letting the user open up the system for inspection in breakdown situations.
i
A
I wish to thank all the people that in some way or another have contributed to the creation of this dissertation. Most importantly, I wish to thank my advisor, Klaus Marius Hansen, for insightful and engaged guidance and for keeping me on track while at the same time giving me freedom and peace to work. In addition, I also thank the people I have worked professionally with to create papers and software: Mads Ingstrup, David Fors, Erik Grönvall, Lars Kristensen, Toke Eskildsen, and Rolf orup. I thank Boris Magnusson for a interesting stay at Lunds Tekniska Högskola. I thank Daimi for being a great place to study and work and Secale for giving me food for thought. My thanks also goes to LIWAS ApS, ISIS Katrinebjerg Software, the PalCom project, and BRICS International PhD School for sponsoring my PhD studies. Finally, a I thank Clara, Linus, and especially Solveig for making it possible to complete a PhD while living a wonderful family life.
Jeppe Brønsted Århus, August .
iii
C
Abstract
i
Acknowledgements
iii
Contents
v
List of Figures
ix
List of Tables
xi
I
Overview
Introduction . Pervasive Computing . . . . . . . Vehicle to Vehicle Applications . Software Architecture . . . . . . . Service Oriented Architecture . . Contributions . . . . . . . . . . . Research Approach . . . . . . . . Research Context . . . . . . . . . Outline . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Architecture in Vehicular Technology Applications . Vehicular Technology Applications . . . . . . . . . . . . . . . . . . Architectural Choices . . . . . . . . . . . . . . . . . . . . . . . . . Data Dissemination in Vehicle to Vehicle Networks . Delivery Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . Protocol Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Service Composition . A Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Service Composition Model . . . . . . . . . . . . . . . . . . . . . . Categorization Framework . . . . . . . . . . . . . . . . . . . . . . v
Contents
. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Palpability in Pervasive Computing . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II Publications
An Infrastructure for a Traffic Warning System . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Main Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . Prototype : Basic Wireless Inter-Unit Communication . . . . . . . Prototype : e OSVM Platform and Application Level Features . Prototype : Initial Deployment . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . .
Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zone Dissemination Protocols . . . . . . . . . . . . . . . . . . . Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . Conclusions and Future Work . . . . . . . . . . . . . . . . . . . Algorithm Primitives . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . .
. . . . .
A Uniform Publish-Subscribe Infrastructure . Introduction . . . . . . . . . . . . . . . . . Related Work . . . . . . . . . . . . . . . . PSI - a Publish-Subscribe Infrastructure . . PSI in the LIWAS System . . . . . . . . . Discussion . . . . . . . . . . . . . . . . . Palpability support demonstrated . Introduction . . . . . . . . . . . Active Surfaces . . . . . . . . . Implementation . . . . . . . . . Evaluation . . . . . . . . . . . . Conclusions and Future Work
. . . . . vi
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
Contents
Handling membership dynamicity in service composition . Introduction . . . . . . . . . . . . . . . . . . . . . . . Related Work . . . . . . . . . . . . . . . . . . . . . . e PalCom Open Architecture . . . . . . . . . . . . e Site Sticks Scenarios . . . . . . . . . . . . . . . . Handling Membership Dynamicity . . . . . . . . . . Decentralized Interpretation . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Issues in Service Composition for Pervasive Computing . Introduction . . . . . . . . . . . . . . . . . . . . . . Indicators for Characteristics . . . . . . . . . . . . . Characteristic/Indicator Dependencies . . . . . . . . Discussion . . . . . . . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . . .
. . . .
Service Oriented Architecture for Inter-vehicle Applications . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . VANET Characteristics . . . . . . . . . . . . . . . . . . Why Use VANETs? . . . . . . . . . . . . . . . . . . . . Service Oriented Architecture . . . . . . . . . . . . . . . A Business Case . . . . . . . . . . . . . . . . . . . . . . . Requirements on SOA Infrastructure . . . . . . . . . . Bibliography
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
vii
L F
. Contribution Map . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. Conceptual Architecture Overview . . . . . . . . . . . . . . . . . . . . Delivery Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Service composition model . . . . . . . . . . . . . . . . . . . . . . . . . GasPrices script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Deployment diagram for the abstract LIWAS system architecture. Environment for prototype experiments. . . . . . . . . . . . . . Stationary - Mobile Communication at km/h. . . . . . . . . . Mobile - Mobile Communication at km/h. . . . . . . . . . . Relative speed of km/h. . . . . . . . . . . . . . . . . . . . . Stationary - Mobile at km/h. . . . . . . . . . . . . . . . . . . Platform and user interface for prototype . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . . . . . . . .
e Zone Flooding Protocol. . . . . . . . . . . . . e Zone Diffusion Protocol. . . . . . . . . . . . e simulation scenario. . . . . . . . . . . . . . . e Information Distance metric. . . . . . . . . . Medium velocity, nodes. . . . . . . . . . . . . Medium velocity, nodes. . . . . . . . . . . . . Low velocity, nodes. . . . . . . . . . . . . . . High velocity, nodes. . . . . . . . . . . . . . . Low velocity, nodes. . . . . . . . . . . . . . . Low velocity, nodes. . . . . . . . . . . . . . . Low velocity, nodes. . . . . . . . . . . . . . . High velocity, nodes. . . . . . . . . . . . . . . Pareto optimal solutions. High velocity, nodes.
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. LIWAS operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Infrastructure deployment diagram . . . . . . . . . . . . . . . . . . . ix
List of Figures
. . . . .
Topic hierarchy . . . Publish . . . . . . . Subscribe . . . . . . Gateway example . . LIWAS deployment
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . . .
Tiles . . . . . . . . . . . . . . . Hardware . . . . . . . . . . . . Catch . . . . . . . . . . . . . . Scrabble . . . . . . . . . . . . . Puzzle . . . . . . . . . . . . . . PalCom layered runtime system Simulation framework . . . . . Services in the puzzle game . . . Puzzle assembly script . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . .
Geotagger script . . . . . . . . . Site Sticks . . . . . . . . . . . . . SiteSticks script . . . . . . . . . . Mean command propagation time
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. A general model of the elements in service composition. . . . . . . . . . Value chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example operation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
L T
. Research approaches used . . . . . . . . . . . . . . . . . . . . . . . . . Vehicle technology applications . . . . . . . . . . . . . . . . . . . . . . Network architecture characteristics . . . . . . . . . . . . . . . . . . . . Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Methods and Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . Characteristic/Category Dependencies . . . . . . . . . . . . . . . . . . Categorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Categorization of Service Composition Mechanisms . . . . . . . . . . . Stationary-mobile communication. . . . . . . . . . . . . . . . . . . . . Mobile-mobile communication. . . . . . . . . . . . . . . . . . . . . . . Feasible update sizes in different scenarios. . . . . . . . . . . . . . . . . . . .
Mobility classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulation parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . Lowest Awareness Percentage requirement to choose Zone Flooding. . Maximum packets sent allowance requiring Zone Diffusion to be chosen.
. Experimental user study . . . . . . . . . . . . . . . . . . . . . . . . . . Characteristic/Indicator Dependencies . . . . . . . . . . . . . . . . . . Categorization of Service Composition Mechanisms . . . . . . . . . .
xi
P I
O
C Ո
I
As computing devices, sensors, and actuators pervade our surroundings, new applications emerge with accompanying research challenges. In the transportation domain vehicles are being linked by wireless communication and equipped with an array of sensors and actuators that make is possible to provide location aware infotainment, increase safety, and lessen environmental strain. e highly dynamic vehicular environment, however, poses significant challenges to application developers. Vehicles driving in opposite directions are only in communication range for a few seconds. Furthermore, in sparse traffic, there is poor network connectivity and dense traffic challenges the scalability of algorithms. Enabling communication among vehicles requires optimized protocols that exploit properties of the communicated data and the mobility of vehicles. Each vehicle can contain a plethora of devices, sensors, and actuators that are provided by a multitude of manufacturers and connecting them in applications is no simple task. Each device can possibly be part of multiple applications and some applications might place requirement on the quality of the service provided by a device. is dissertation is about service oriented architecture for pervasive computing with an emphasis on vehicle to vehicle applications. If devices are exposed as services, applications can be created by composing a set of services and governing the flow of data among them. In pervasive computing, composing services is, however, not the whole story. To fully realize their potential, applications must also deal with challenges such as device heterogeneity, context awareness, openendedness, and resilience to dynamism in network connectivity, mobility, and availability of services. e research question we seek to explore in this dissertation is the following reformulation of the above:
How can service oriented architecture be used to structure applications in a way that alleviates the challenges of pervasive computing and in particular vehicle to vehicle applications? e papers presented in part II documents our efforts in illuminating various aspects of how to use services in vehicular applications.
Chapter . Introduction
In the following sections, we describe the background for the research conducted (section .–.). Following that, in section . we shortly describe the contributions of the papers in part II. In section ., we describe the research approach used in this dissertation and in section ., we describe the context the research has been conducted in. Finally, in section . we give an outline of the rest of the dissertation. .
P C
As formulated by Weiser in [] ubiquitous computing is about integrating computers seamlessly into the world in such a way that they disappear in use. When everyday objects are enhanced with computing and communication capabilities, new applications are made possible that will enhance peoples’ lives with increased productivity, comfort, and security. From a technical perspective, pervasive computing challenges the way we build systems by significantly changing the basic assumptions that can be made, and by setting new requirements. Here we divide the challenges into heterogeneity, dynamicity, context awareness, and openendedness
Heterogeneity Applications of pervasive computing often consist of heterogeneous devices ranging from embedded sensor nodes to servers on the Internet. e devices can have varying resources with respect to computational capacity, available memory, power, communication bandwidth, and latency. Not only is it a challenge to construct middleware that can run on resource constrained devices, it is also a challenge to take full benefit from the resource rich nodes. Pervasive computing middleware should not be limited by the least common denominator with respect to resources, but should take advantage of all devices in the system. Devices can also be based on heterogeneous system architectures and operating systems and this complicates the process of maintaining a deployment. Dynamicity A system designer can not always assume that a device is connected to the network, that it has a particular location, or that nearby devices are available. In pervasive computing environments, there is not always a fixed network that devices can use for communication. If wireless communication such as infrared light or radio is used, links are unreliable. If devices are also mobile, they can move in and out of communication range. Mobility can also cause the network topology to change, forcing network protocols to be adaptive. Ad-hoc communication protocols such as Ad hoc On-Demand Distance Vector Routing (AODV) [], Dynamic Source Routing Protocol (DSR) [], and Optimized Link State Routing Protocol (OLSR) [] go a long way in maintaining network connectivity in spite of unreliable links and changing topology, but developers have to take into account that situations with no connectivity will most likely occur. ¹In this dissertation, we use the terms ubiquitous computing and pervasive computing interchangeably.
.. Vehicle to Vehicle Applications
Context awareness A pervasive computing application should be sensitive to the users context in a way that hides details when possible but exposes them when necessary. If, e.g., a device with a required functionality disappears, it should be replaced with a similar device or, in case no such device exists, the user should be notified. Schilit et al. [] categorizes context awareness according to whether the task at hand is getting information or carrying out a command, and whether it is effected manually or automatically. For example, automatic-command corresponds to the automatic execution of an action due to changes in the context, whereas the manual-information category is about providing context information on request e.g. by delimiting a list of printers by using information about the users location.
Openendedness One particular instance of context sensitivity is to adapt application functionality to new purposes due to changes in the user context. For example, a navigation system could be altered to be part of a fleet management system by adding a device with a General Packet Radio Service (GPRS) [] connection to the vehicle. With respect to openendedness, the user plays a central role because it can be hard for the system to automatically detect changes in what the user wants to do. In the above example, the user could, e.g., also use the GPRS connection to receive tourist information about the area he is driving in. If the user is involved in specifying what he wants to do, it is necessary that he has a basic understanding of which devices can be connected and how to do it. Whether it is done by downloading an application matching his requirements from the Internet or by connecting boxes in a Graphical User Interface (GUI), it is important that the user not only understands what is happening under normal operation, but also that he is able to resolve the contingencies that might occur. . V V A In recent years the adoption of distributed systems in vehicles have increased significantly by the introduction of Global Positioning System (GPS) [] navigation, fleet management systems, speed camera notification systems [], TMC [] traffic information notification systems, etc. One example is the OnStar system [] in which a cell phone and a GPS system are connected to the vehicle bus to provide a wide range of services ranging from remote engine diagnostics to automatic geotagged emergency calls. e system has currently over million subscribers and processes more than calls every month. A common point of commercial systems is that most use wide-range radio technology for communication. Only a few, if any, rely on vehicular ad-hoc networks (VANETs) using short-range communication. In research however, VANETs have been studied extensively [] and is one of the main application areas for mobile ad-hoc networks (MANETs) in general. Vehicular ad-hoc networks consisting of nodes communicating by using shortrange wireless radios are characterized by having a high degree of variability in node
Chapter . Introduction
mobility and node density. e mobility pattern of vehicles is heavily influenced by the layout of roads and the current traffic situation. Normally, on highways approaching vehicles will only be within transmission range for a few seconds depending on antenna and propagation conditions. However, if traffic congestion occurs, vehicles driving in the same direction can be within range for hours. In addition, traffic congestion also imposes a dense network topology with a lot of nodes simultaneously in transmission range. In contrary, sparse traffic conditions are typical in rural areas. While these characteristics make it complicated to implement applications that utilize VANETs for communication, VANETs are nevertheless necessary because the alternative, wide range cellular communication, has a set of disadvantages that may negatively influence an applications ability to provide its services. First of all, currently cellular technology provides significantly lower bandwidth on node-tonode communication. Wireless communication has the property that the nodes in range share the communication capacity of the medium, and the larger range a signal has, the more nodes have to share the bandwidth. is is not necessarily a problem if the node density is low (e.g. in rural areas), but in areas where the node density is high, severe constraints are put on the communication bandwidth. Secondly, the coverage provided by cellular systems is limited in some regions. Note however that this may change in time. ird, cellular communication links typically have high latency. Finally, using cellular communication usually entails some form of paid subscription. ese disadvantages have the effect that some applications cannot be realized using cellular communication. e literature provides a wealth of examples. E.g. systems that warns about hazardous driving conditions such as ice (cf. chap. ), roadwork, traffic congestion [], vehicle collision avoidance systems [], etc. To realize the full potential of these applications, short-range wireless communication must be used. In spite of the reasons for using short-range communication mentioned above, we are not aware of any commercial applications employing it. One factor is that systems relying on short-range wireless communication are typically more complex in design, implementation, evaluation, and deployment. If the application can be realized without short-range communication, it is most likely a cheaper solution, but as we argued above, this is not always possible. Another factor is that a lot of the applications mentioned above require a critical mass to work optimally. One example could be a system providing warnings about icy roads. Vehicles equipped with the system disseminate warning messages to approaching vehicles. If not enough nodes are equipped with the system, there is a high probability that messages will not reach the approaching vehicles. Furthermore, only vehicles equipped with the system will receive warnings. In this dissertation, we mainly focus on protocols and architectures for applications employing vehicle to vehicle networks.
.. Software Architecture
. S A An important concern in realizing large computing systems is the software architecture of the system. Bass et al. [, p. ] defines software architecture as follows:
e software architecture of a program or computing system is the structure or structures of the system, which comprise software elements, the externally visible properties of those elements, and the relationships among them. When a software architecture is created for a system, it is important to ensure that a set of concerns are balanced. Besides the functional requirements that describe what the system is supposed to do, a set of orthogonal quality requirements restricts the systems behavior with respect to properties such as availability, modifiability, performance, security, testability, and usability. Some of these properties are inversely connected in the sense that improving support for one adversely affects the other. For example, one way to improve protocol performance is to make cross-layer optimizations, which is bad for modifiability because it makes the code less modular. Bass et al. [] presents a set of tactics that can be used to enhance support for specific quality requirements. E.g., heartbeats can be used to monitor a service to enhance availability by detecting faults early and thus making it possible to resolve the fault before it becomes a failure. At a level higher, an architectural style [] is a set of rules that governs the design of the architecture. Having an architectural style makes it easier to consistently maintain a system because it enhances the systems conceptual integrity. Some styles are better suited for particular purposes than other. Since the choice of selecting an architectural style is made before an application or system is implemented, clues to what style to choose are useful. Architectural decisions made at this point are highly influential on the resulting system and the process of creating it. If a bad decision is made at an early stage it can prove to be the difference between success and failure. e choice of a particular architectural style is no guarantee for success in itself and therefore details on how the style should be applied are at least as important as clues to what style to use. . S O A In this dissertation, we investigate the use of a particular architectural style, Service Oriented Architecture. In Oasis’ Reference Model for Service Oriented Architecture [] it is stated that:
Service Oriented Architecture (SOA) is a paradigm for organizing and utilizing distributed capabilities that may be under the control of different ownership domains. In SOA, the needs of entities are met by capabilities provided by other entities. At the most abstract level, a capability can be seen as the ability to affect the world in
Chapter . Introduction
some way. In a software system this usually amounts to performing a computation, doing a transaction, reading a sensor, activating an actuator, etc. - all the things that can be performed or initialized from software. Correspondingly, a need is the desire to affect the world in some way. To match needs and capabilities in a software system, the needing entity must, directly or indirectly, be able to communicate with the entity providing the capability. e software counterpart of a capability is a service, which we define as follows:
A service is a unit of runtime software accessible by others. A service encapsulates a piece of functionality and offers it to the world in such a way that the user of a service not necessarily has to be in control of the service. In other words, the entity using a service does not have to belong to the same company or organization as the entity providing the service. is property makes SOA suited for pervasive computing because making a wealth of different devices cooperate is a prerequisite for pervasive applications. SOA makes it possible to cleanly organize the devices in a pervasive computing application in a consistent and structured manner. To enable service oriented architecture in a system, a service infrastructure is needed. e complexity of such an infrastructure can range from protocols enabling primitive service invocation to advanced frameworks with semantic service descriptions and error handling. Furthermore, the act of using a set of services to form an application can be supported at multiple levels. Perhaps, the simplest approach is to invoke services directly from source code in the application. A better option is to use a service composition mechanism to compose the service into an application. In chapter , we discuss issues in service composition for pervasive computing. .
C
In the following, we shortly describe the contributions of the papers in Part II in chronological order. Figure . maps the papers into each of the previous background topics.
An Infrastructure for a Traffic Warning System (Chap. ) is paper presents our results on requirements identification, design, and prototyping of an Infrastructure for a traffic warning system. e infrastructure combines communication via mobile phones with communication based on the principles of ad-hoc networking, and it supports units in being updated during operation. A set of prototypes realizing various aspects of the infrastructure is presented along with associated experimental results that demonstrate the main functionalities of the communication infrastructure, and have led to the initial deployment of LIWAS units.
.. Contributions
Pervasive Computing Software Architecture Service Oriented Architecture Service Composition Handling membership dynamicity in service composition for ubiquitous computing
A survey of service composition mechanisms in pervasive computing
Vehicle to vehicle applications An Infrastructure for a Traffic Warning System Service oriented architecture for intervehicle applications
A Uniform publish subscribe infrastructure for communication in wireless mobile environments
Specification and Performance Evaluation of two zone dissemination protocols
Palpability support demonstrated
Figure .: Contribution Map
Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks (Chap. ) Here, we present two candidates for data dissemination protocols: a zone flooding protocol and a zone diffusion protocol. e two protocols combine ideas from sensor networks and geocasting to ensure that data is aggregated and distributed only in a bounded geographical area. We present a comparative simulation study of the two protocols evaluating their relative performance using conventional metrics (such as network load) as well as application-specific metrics (such as awareness). e simulation study has been conducted using the Network Simulator (NS-) and has highlighted key properties of the two protocols that can be used as a basis for selecting the most appropriate protocol. A Uniform Publish-Subscribe Infrastructure (Chap. ) In this paper, we present PSI, a uniform publish-subscribe based infrastructure, for communication in wireless mobile environments. In PSI the application is divided into software components that each handles a well defined part of the functionality and communicates with other components using the publish-subscribe paradigm. From a components perspective it makes no difference where the receivers of a message are located - in the same process, in another process on the same node, or in a process on a remote node. All communication is handled uniformly. By showing how the infrastructure is used in a concrete instance, we argue that it hides the complexity of low level network programming and presents a clean and understandable abstraction over communication to the application programmer. Palpability support demonstrated (Chap. ) In this paper, we demonstrate how palpability can be supported in a prototype of the rehabilitation concept Active Surfaces in which children assemble floating tiles into meaningful configurations. Services on the tiles have been developed using a framework that allows them to be combined into assemblies. e support for palpability is shown by examples of use
Chapter . Introduction
scenarios from the work of the therapist who can inspect and alter the runtime state of the tiles to change their configuration and cope with breakdown situations. e prototype implementation runs on a standard PC simulating the network layer and a first reference implementation has been made on the target embedded platform.
Handling membership dynamicity in service composition (Chap. ) In this paper, we show how the PalCom service composition language can be extended to support service composites with dynamic membership and present a decentralized implementation. Preliminary user studies indicate that the extensions are easily understandable and simulations of application scenarios show that the performance of the implementation is appropriate for ubiquitous computing applications. Issues in Service Composition for Pervasive Computing (Chap. ) Composition of services, i.e. providing new services by combining existing ones, is an idea pervading and thus important to pervasive computing. However, compared to other areas of computer science, pervasive computing technologies are more openended, context aware, dynamic, heterogeneous, often use networked sensors and actuators, and present new challenges to usability. ese six characteristics pose requirements to the design of service composition mechanisms that are unique to pervasive computing. We catalogued the technologies that in one form or another can be said to support service composition for pervasive computing, and describe their variation points. ese variation points in the design of existing composition mechanisms are important indicators for how well the resulting composites are able to cope with and exhibit the six key characteristics of pervasive computing. Our assessment of the selected technologies indicate that there is a need for more research into providing appropriate security for composites; into managing the contingencies which arise naturally in a pervasive computing environments; and for doing more thorough evaluation of the technologies, both with respect to utility and performance. Service Oriented Architecture for Inter-vehicle Applications (Chap. ) In this paper, we claim that to maximize the number of nodes participating in vehicle to vehicle applications, it is important that corporations and organizations cooperate to merge their user bases so that they each reach the critical mass of participating nodes required to realize the full potential of the systems. We show how service oriented architecture can be used to by split applications up in services and sharing them across different ownership domains in a way that provides value for all stakeholders. From a business case for a set of applications, we deduce technical requirements for a service infrastructure for VANETs. .
R A
We use March and Smiths framework for research in information technology [] to describe our research approach. In the paper, the terms information technology
.. Research Approach
research and computer science are used interchangeably. First, we briefly describe the framework. One perspective on computer science is that is a combination of the approaches used in natural and design sciences. According to March and Smith “natural science aims at understanding and explaining phenomena”, whereas “design sciences aims at developing ways to achieve human goals”. e basic activities in design science is to build and evaluate, whereas natural science is often viewed as consisting of making theories and justifying them. In computer science, the objects investigated are typically artifacts created or built by man as opposed to, e.g., in physics where natural phenomena are studied. To determine the performance of an artifact it is evaluated by using appropriate metrics. To explain the performance observed, theories are developed that describe the artifact and its relation to the environment. Finally, the theories must be justified by using analytical or experimental approaches, depending on the nature of the artifact. March and Smith states that these four research activities - building, evaluating, theorizing, and justifying - can be applied to four kinds of research outputs: constructs, models, methods, and instances. Constructs or concepts are used to describe a domain, models express relationships among concepts, methods describe processes (e.g. algorithms), and instances are realizations of artifacts. For example, consider the paper describing two zone dissemination protocols in chapter . e research behind the paper consisted of building two method s (protocols) for data dissemination in vehicular ad-hoc networks and evaluating their performance using metrics such as, e.g., network load. It was conjectured that the protocols were robust to changing conditions in the network environment and this theory was justified by analyzing simulation results for a range of different network environments. e research documented in part II have been conducted using several of the activities and outputs described above. In the matrix formed by crossing the activity and output axes (table .) we have inserted the contributions according to what have been used. e numbers in the table correspond to chapters in part II.
Construct Model Method Instantiation
Build , , ,,
Evaluate
eorize
Justify
, , , , ,
Table .: Research approaches used As can be seen from the table, most of the research effort has been on building and evaluating instances and methods ( papers). is indicates that the research have been mainly engineering oriented using methods from design science. Although theories have been developed and justified, most of these theories are
Chapter . Introduction
about artifacts created by the author ( papers). e only exception is the survey (Chap. ), which investigates work by other authors. e lack of “Construct” research outputs indicates that focus primarily has been on dealing with more practical issues and only secondly on forming constructs and concepts. .
R C
e research presented in this dissertation has been conducted as part of the LIWAS and PalCom research projects. Although the foci of the projects are somewhat different, both deal with pervasive computing challenges such as mobility, dynamicity, and context awareness by using service oriented architecture. e LIfe WArning System (LIWAS) is a traffic warning system being developed in a research collaboration between ISIS Katrinebjerg at University of [] and LIWAS ApS []. e LIWAS system is based on sensors that are capable of determining whether the surface of the road is dry or covered with water, snow, or ice. A LIWAS sensor consists of a collection of sensors that are collectively used to classify the state of the road. e concrete sensor configuration can be adapted to match requirements to classification accuracy and manufacturing cost. A vehicle equipped with a LIWAS sensor can inform the driver about the state of the road being passed and hereby help the driver take precautions according to the current road conditions. In addition to intra-vehicle communication, the vision is to use wireless communication to disseminate information to other vehicles and road authorities. In the EU funded IST project PalCom [] a conceptual framework and an open architecture have been developed for ‘palpable computing’. Palpable computing is a new perspective on pervasive computing in which some of the traditional pervasive computing tenets such as invisibility and composition have been complemented with visibility and decomposition. e concept has been formed based on the observation that when applied in real settings, pervasive computing systems tend to become hard to understand for users. For example, in normal use the system should be invisible and not interfere with the present task. However, when a breakdown occurs the user should be able to inspect the system to determine the reason and, if possible, resolve the situation. A collection of tools to be used in palpable computing application have also been developed and used in real life scenarios developed in cooperation with end users. .
O
e rest of part I is structured as follows. In the next chapter, we analyze architecture for vehicular technology applications by analyzing the variability in applications and discuss important architectural choices. Following that, we describe data dissemination in vehicle to vehicle networks in chapter . In chapter , we look at service composition for the realization of service oriented architecture. In
.. Outline
chapter , we discuss palpability in pervasive computing and, finally, in chapter we conclude the dissertation by summarizing the contributions made and give directions for future work.
C Ո
A V T A
In the domain of vehicular technology applications, there is a great variation in requirements for applications. Consider, e.g., a system for automatically notifying the emergency dispatch centre in case of an airbag deployment and a system for allowing vehicles to automatically drive in a platoon. While loss of life can be a consequence in the case of a system failure for both applications, the requirements for communication latency, bandwidth, and coverage differ significantly. A latency of seconds is inconsequential for the automatic emergency notification system, whereas a latency of two seconds in a platooning system can easily cause a crash. e communication channel of the automatic notification system only has to carry a few kilobytes of information in the event of a crash, whereas in the platooning system each vehicle potentially sends and receives position and direction updates continuously. Finally, while the automatic notification system has to be able to contact an emergency dispatch centre no matter where the vehicles is located, the platooning system can easily operate disconnected from the Internet and other wide area networks. e requirements for a system guide the architect in making choices in the design of the architecture. For example, the low latency requirement in the platooning system tells the architect that he should not rely on cellular communication, because with cellular communication there is typically a high latency. In this chapter, we look at the architects choices with respect to network architecture, middleware architecture, and business model interplay. e network architecture has a major impact on which communication requirements can be satisfied. e selection of one network architecture over another can easily make it impossible to realize the system in a way that satisfies the requirements for communication. For example, if communication is based on GPRS connections, position updates cannot be sent multiple times per second as required in a platooning application. Network architecture is described in detail in section ... e middleware architecture affects how complicated a system will be to implement and maintain. Vehicular technology applications often consist of a wide range of sensors, actuators, and communication interfaces that use different protocols for communication making it hard to maintain a consistent view on the middleware architecture. Furthermore, since some of these protocols employ information only
Chapter . Architecture in Vehicular Technology Applications
available in the application layer for routing, a strict layered architecture is infeasible. We will elaborate further on this in section ... Finally, there is a strong connection between the choice of architecture and the choice of business model. Some architectures rule out some business models and vice versa. For example, applications based on ad-hoc networks depend on a large user base, which, in turn, depends on the business model. is will be further described in section ... As mentioned above, the architectural choices are guided by system requirements. To get a clear understanding of what is required for a vehicular technology application, we first taxonomize a representative range of applications (section .). Following that, we describe each of the architectural choices in detail and how they have been investigated in the contributions in part II. .
V T A
In this section, a range of vehicular technology applications are taxonomized according to a set of criteria relevant for the design of the architecture and communication protocols supporting such applications. e criterion for selecting the applications is that they should involve multiple communicating vehicles. e vehicles can communicate among themselves and/or with one or more servers on the Internet. We do not consider vehicle-local systems such as adaptive headlights, smart airbags, adaptive cruise control [], anti-lock braking systems, radar based collision detection, etc. Each of the applications below should be seen as a representative of a class of applications with similar properties.
Infotainment Infotainment systems provide information and/or entertainment to the driver possibly depending on his current location and context. e driver could, e.g., request information about nearby restaurants or tourist information. Google maps [] is an example of a service providing location dependent information. Neighborhood notification One example of a neighborhood notification system could be a system for notifying a driver about gas prices in the area he is driving in. e information provided should depend on the vehicles location, destination, and the amount of gas left. Finally, the driver should be able to specify preferences with respect to particular gas station chains. In [] such an application is described along with a proposed architecture, implementation, and evaluation. While in some ways similar to infotainment systems, neighborhood notification systems distinguish themselves by delivering more dynamic data concerning phenomena in the general neighborhood of the driver. For example, gas prices usually change several times over a day. Other applications with similar properties include systems for notification about speed traps [] and available parking spots [].
.. Vehicular Technology Applications
Context sensitive navigation Navigation systems have been in common use for several years but only recently have information about the users context been used for navigation. In several commercial systems [, ], the route calculated to the destination is depending on the current traffic situation in the environment. Information about the current traffic is usually obtained from the Traffic Message Channel (TMC) [] over the FM band. Not only information about traffic congestion or roadwork is useful but also the configuration of the vehicles. If, e.g., a vehicle is equipped with snow tires it can safely use routes that include slippery sections. Fleet management systems are typically used by a companies with large fleets of vehicles to optimize logistics by, e.g., dispatching the nearest vehicle to a customer or by distributing vehicles evenly over a region to minimize dispatch time. Examples including taxi companies [], package delivery services, law enforcement authorities. Fleet management systems are typically also used to gather statistics about the fleet operation for billing and productivity analysis. Platooning A suggested solution to the problem of ever-increasing traffic density in cities is to let vehicles move together in a platoon with only a few meters apart [, ]. When a vehicle brakes, the following vehicles automatically adjust their velocities. It has been suggested that the capacity of roads can increased by – by using this technique and that traffic safety can be improved because data suggests that human error accounts for up to of all accidents []. Furthermore, significant fuels savings due to draught effects can be achieved - especially for large vehicles []. Collision detection applications [] try to avoid accidents by alerting the driver before hazardous situations occur. Vehicles exchange data about velocity and direction and continuously try to predict dangerous situations. While similar to platooning, the focus of collision detection systems is to alert the driver but not necessarily to control the vehicle. Collision detection systems based on inter vehicle communication have the advantage over vehicle-local systems (using radars, ultrasound, etc.) that they can monitor traffic outside the range of sensors which can be necessary to avoid pile-up accidents on highways. Some systems provide an audible alert seconds before a crash while more advanced systems visualize the traffic ahead is a display in the vehicle []. Road state notification Collision detection systems communicate information about vehicle location. In contrast, road state notification systems inform the driver about properties of driving environment. It can be information about relatively static phenomena such road work or potholes in the road [] but can also concern more dynamic properties such as traffic congestion [] or whether the road is wet or icy (see chapter ). Information about the state of the road can be used to increase
Chapter . Architecture in Vehicular Technology Applications
safety but can also be used for input to context sensitive navigation systems. In some cases not only notifications about the occurrence of a phenomenon is of interest but also notifications about the absence of the phenomenon. If, for example, a driver has received no notification about ice on the road ahead, it can mean either that the road is safe or that no vehicle with an ice sensor has traversed the area recently.
Automatic emergency notification One of the features of the OnStar system [] is to automatically alert the emergency centre when an accident occurs. When the airbags are deployed, information about the vehicles location (using input from a GPS device) and the force of the impact (using accelerometers) are sent to a call centre which in turn tries to contact the vehicle and possibly dispatches emergency vehicles. Other systems in the same category include remote door unlocking and remote engine diagnostics. ..
Taxonomy
In table ., we have classified the applications with respect to a set of categories of architectural importance that have been selected by looking at the variability of the applications described in the previous section. Below we introduce each of the categories and give examples for each of the possible values. In section ., we describe how the categories affect architectural choices. Note that the values in table . are independent of choice of architecture and protocols. Scenario/Application Infotainment Neighborhood notification Context sensitive navigation Fleet management Platooning Collision detection Road state notification Automatic emergeny notification
Criticality Convenience Convenience Convenience Convenience Safety of Life Safety of Life Safety Safety of Life
Penetration sensitivity Data sources Data sources Data sources Included vehicles Included vehicles All vehicles Sensing vehicles Single vehicle
Relevance decrease Temporal Spatial Days/None 1 km + Hours 100 m Hours 100 m Minutes km Milliseconds m Milliseconds 100 m Hours 100 m Seconds 100 m
Communication Pattern Data exchanged Sporadic Sporadic ~100 bytes Sporadic ~1 KB Periodic ~100 bytes Periodic ~100 bytes Periodic ~100 bytes Periodic ~100 bytes Sporadic ~100 bytes
Table .: Vehicle technology applications
Criticality A strong determinant for the design of architecture and protocols is the consequence of a system failure. In some applications, such as, e.g., infotainment or navigation systems, failure only amounts to inconvenience, whereas in road state notification systems the safety of drivers can be at stake. Even worse, a failure in a platooning system can be life threatening. Penetration sensitivity Some applications are sensitive to user adoption in the sense that they will only achieve optimal functionality when a large user base reached. Until then, the application will be only partially functional. We classify the applications according to how many users will have to adopt the system before it is fully
.. Vehicular Technology Applications
functional. For example, a gas price notification service is only useful if the majority of gas stations provide price information for the system. Likewise, a collision detection system base on inter-vehicle communication can only be trusted if the majority of drivers have the system installed. For a fleet management system to be functional, vehicles in the fleet have to have the system installed. To some degree, the penetration sensitivity of a system will also depend on the chosen architecture and protocols. An ad-hoc network supported system will need more users than a system relying on an infrastructured network. In table ., we only account for the penetration sensitivity inherent to the application. For example, regardless of architecture and protocols, a platooning system requires that all vehicles in the platoon have the system installed.
Spatial and temporal relevance decrease Inspired by Xu et al. [] we classify the data communicated in vehicular applications according to the spatial and temporal properties of the object they describe. Xu et al. observed [] that for most vehicular technology applications, the relevance of information about an object in the environment decreases with the distance, in time and space, to the object. If, e.g., a vehicle is located in Århus, the location of a gas station in Copenhagen is less important than the location of a gas station in Århus. Similarly, the date for the effectuation of a new traffic law is more important if it is tomorrow than if it were forty years ago. To some degree this is dependent on the actual application, but for the applications listed here, the observation holds. For the applications mentioned here, there is a lot of variability in the how fast the relevance decreases with time and distance to the origin of the data. Xu et al. expresses this in a relevance function, which is a linear combination of the distance in time and space to the object weighed by two parameters, α and β . In table ., we only estimate the magnitude of how long it takes for data to go from maximum relevance to negligible relevance. For example, the relevancy of a gas price at a particular gas station decreases to almost nothing in hours - because most likely the price will change in that time interval. Similarly, in a collision detection system, information about other vehicles is uninteresting outside a range of a few hundred meters. Communication pattern e pattern of communication in an application details when communication is done. Some applications, e.g. collision detection systems, periodically send information to other parties in the system, whereas other applications only sporadically send information on the occurrence of events. For example, in a gas price notification system, prices are only requested in the event of low fuel. If the fuel tank is full there is no need to request information. Since the temporal relevance decrease describes approximately how long it takes for data to become irrelevant, the temporal relevance decrease figure is a good estimate for a required communication frequency for the applications that rely on periodic communication.
Chapter . Architecture in Vehicular Technology Applications
Data exchanged Every time communication is performed in the network, an amount of data is exchanged. For example, when a vehicle in a fleet management systems updates its position on the server it does so by sending the server its GPS coordinates along with auxiliary information. e exact amount of data exchanged depends on the choice of data representation. e amounts listed in table . are approximate upper bounds. .
A C
In the following, we describe in detail architectural choices with respect to network architecture, middleware architecture, and business model interplay. Additionally, we describe how they have been investigated in the contributions in part II. In figure ., a conceptual overview of architecture for vehicular technology applications inspired by [] can be seen. Arrows in the figure denote influences. e network architecture determines the structure of the network that is used for communication in the system. e middleware architecture structures how the developer can access the network when implementing the application logic. e business model influences the architect that designs the architecture and the network and middleware architectures affect the choice of business model.
Architect(s)
Architecture Architects's Influences Application Layer Business Model ...
Middleware Architecture Network Architecture
System
Figure .: Conceptual Architecture Overview
..
Network Architecture
In vehicular technology applications, vehicles can communicate with each other by using long range wireless communication such as, e.g., GPRS, by using a vehicular ad-hoc network, or by using a combination of the two. e choice of network architecture is important because it affects almost all aspects of the application. Most likely, if a wrong decision is made, everything has to be reimplemented. In the following, we describe the network architectures and in table ., we summarize
.. Architectural Choices
their characteristics. Long range infrastructure-based wireless communication, such as e.g. GPRS, typically relies on a cellular infrastructure in which a geographic area is divided into regions called cells [, chap. ]. In each cell, a transceiver, called a basestation, is responsible for connecting the nodes (such as, e.g., handsets) in the cell to the network. Since all nodes in a cell share the bandwidth of the communication medium, the scalability of a cellular system is limited. e larger the cells are, the more nodes will be in range and the lower the bandwidth will be. e base-stations typically communicate with other base-stations and network services by using wired technology. When a node, A, communicates with another node, B, inside the network, the information exchanged has to travel first to the base-station in A s cell, then to a server, then to the base-station in Bs cell, and then finally to B. e physical distance traveled can be hundreds of kilometers and since the signal is limited by the speed of light, high latency can occur. A cell network is administered by a network operator that controls who have access to its services which usually involves some kind of paid subscription. e coverage of cell networks is usually good. Currently, Global System for Mobile Communications (GSM) is usable in most of Europe []. e complexity of implementing a vehicular technology application using infrastructure-based communication is low because the communication form resembles traditional TCP/IP style communication. An example of use of infrastructure-based communication in a vehicular setting is the OnStar system [] mentioned in the introduction. In vehicular ad-hoc networks, there is no static infrastructure. Instead, vehicles communicate directly using short range radio. For communication with nodes outside transmission, range intermediate nodes act as routers and forwards messages. Since the transmission range of the signals is short, typically only a few nodes have to compete for the available capacity and therefore bandwidth can be high. e physical distance traveled by messages is typically short which means that the latency can be very low. Since no infrastructure has to be maintained, communication in VANETs can in principle be free, however there is only network coverage when other nodes are close by. VANET protocols are often very complex compared with traditional TCP/IP communication because the protocols have to cope with a very dynamic environment. In chapter the different types of VANET protocols are described in detail. While only a few commercial systems [] use VANETs for communication, a lot of research has been done in the area []. Finally, for some applications it can be necessary to choose a hybrid solution where both cellular networks and VANETs are used [, , ]. For example, if it is decided that a VANET should be used, there can be a bootstrapping problem. Early on, there will only be a few nodes and therefore very poor coverage. Coverage will only increase with the number of users, but the number of users will only increase if the coverage is suitable. erefore, it can be necessary to include infrastructure-based communication to bootstrap the process. In table . we summarize the characteristics of the two forms of wireless communication. Looking at the taxonomy presented in section .., all of the categories are
Chapter . Architecture in Vehicular Technology Applications
Cellular networks Vehicular ad-hoc networks
Bandwidth Low High
Latency High Low
Cost Subscription None
Coverage Good Limited
Complexity Low High
Table .: Network architecture characteristics
relevant for the choice of network architecture except the penetration sensitivity. Although the penetration sensitivity is affected by which network architecture is chosen, the opposite is not the case. If a disconnection in the application amounts to a failure, the criticality of the application determines the requirement for coverage. If the consequence of a disconnection is loss of safety or loss of life, an infrastructure based or a hybrid network should be used since they provide the best coverage. Temporal and spatial relevance decrease determine the latency requirement of the application. If data become irrelevant after a short period of time, the latency has to be low. Similarly, if the data become irrelevant outside a small range of the origin of the data, latency should be low because it can be expected that vehicles will move outside the range quickly. e communication pattern and the amount of data exchanged together with temporal and spatial relevance decrease determine the bandwidth requirement. If the pattern is periodic and the temporal and/or spatial relevance decrease are low, the bandwidth requirement is high. Similarly, if data is only exchanged sporadically and the temporal and spatial relevance decrease are high, there is only a low requirement on bandwidth.
Contributions In chapter , the paper An Infrastructure for a Traffic Warning System analyses the LIWAS application described in section . and identifies functional and architectural requirements. e functional requirements amounts to collecting measurements from the sensor, converting sensor values into road classifications, and disseminating classification to other nodes in the system. Since measurements arrive at a rate of times per second and consist of data about temperature, humidity, dew point, light reflection, etc. there is a significant load on the system. e classifications have to be delivered to nearby vehicles and to a backend server. From an architectural perspective, the system should be scalable, modifiable, and available. e vision behind the system is that, over time, it should be installed in the majority of vehicles and therefore it is crucial that the network infrastructure scales from a few vehicles to thousands of vehicles. Since the system enhances the safety of drivers, the availability of the system should be high - even when there are only a few units in operation. Finally, we observed that for a distributed system of this magnitude it is important to be able to modify the system after deployment. e requirements led to the design of an architecture for the system that uses a hybrid network architecture. e rationale behind this decision is that with the amount of data to be distributed, using only infrastructure-based communication is infeasible. Conversely, a requirement for making the system work with only a few nodes requires that a VANET cannot be used alone. To make the infrastructure
.. Architectural Choices
based communication cope with the amount of data, a policy for when to disseminate messages was developed. e architecture was evaluated by experimenting with three prototypes, each realizing key aspects of the architecture. e first prototype investigated the feasibility of transmitting the required amount of data from vehicle to vehicle using wireless LAN. e second prototype implemented classification, communication, and maintenance on top of a embedded virtual machine running SmallTalk byte code. To ensure that the platform provided suitable performance, the communication experiments were repeated. A protocol for distributing software updates in the VANET was developed and evaluated. e first two prototypes only experimented with vehicle to vehicle communication, but the third prototype also included an SMS connection for uploading classifications to a back end server.
.. Middleware Architecture In vehicular technology applications, multiple communication protocols are often used simultaneously. Sensors and actuators are typically connected via a serial connection such as e.g. CAN-bus [], RS-, Universal Serial Bus (USB), or the Bluetooth serial profile []. Vehicles can be connected to servers through the GSM network by using GPRS or SMS, or by using other long range wireless networking technologies such as WiMAX, UMTS, or CDMA. Unidirectional connections from servers to vehicles are possible via TMC. Vehicles are connected to each other using VANET protocols, which come in a wide range of flavors (cf. chapter ). Some VANET protocols can be used for general purposes (e.g. AODV [], DSR [], and OLSR []), but in some cases it is necessary to use protocols optimized for specific applications (e.g. [, , ]). As a consequence of the wide range of protocols, it is important that the middleware architecture makes the protocol functionality available to the developer in a consistent and understandable manner, and that the protocol suite is easy to maintain. Here, we consider middleware to be the software that act as a bridge between the operating system and applications to hide the complexity of network and distributed systems programming to the programmer. Understandability can be achieved by using clean middleware abstractions that hide complexity when possible and expose it when needed. It is not merely a question of designing a suitable API because the selected abstractions should reflect how things work instead of just presenting an interface. Otherwise, the consequence can be that abstractions break down when faults occur. If, for example, the middleware offers a socket to the programmer for communication in a wireless ad-hoc network, it can be problematic if some of the links, due to interference or differences in transmission power, are asymmetrical. is can cause the underlying protocol not work as expected or maybe even not at all. Here, a better fit would be an abstraction that better matches the properties of the network. With respect to maintainability, connections to sensors and servers can use tra
Chapter . Architecture in Vehicular Technology Applications
ditional layered middleware architectures, but protocols for inter-vehicle communication should not use a strictly layered architecture for at least two reasons. First, inter-vehicular communication protocols are often position based (cf. chapter ) implying that they use location information for routing. Hereby, the network layer (cf. the ISO/OSI model []) has to have access to information not available from its surrounding layers and thus have to break the layering principle. Secondly, when aggregation is used in dissemination of data, application level information is used for routing information. In [], it is suggested to a staircase approach in which all protocol layers can interact via a publish/subscribe based Information Connector. In connection with the taxonomy in table ., one factor influencing the middleware architecture is criticality. If the criticality of the application is high, it is important that the system can be maintained without first shutting it down. Another factor is the communication pattern and the amount of data exchanged. For applications where large amounts of data are exchanged, it is important that the performance of the middleware is suitable. One of the lessons learned in implementing the three prototypes (cf. chapter ) was that for the simultaneous operation of the various protocols, another protocol architecture was needed. Since information about the road should be disseminated though multiple communication media, it might be a good idea to decouple the part of the system producing data and the parts of the system consuming data.
Contributions In the paper A Uniform Publish-Subscribe Infrastructure for Communication in Wireless Mobile Environments in chapter , decoupling is achieved by separating the system into loosely coupled components that communicate using a set of publish-subscribe [] based busses that are linked via gateway components. Each bus encapsulates a communication scope. For example, in LIWAS, there would be three busses: a bus for local host communication, a bus for WiFi communication, and a bus for GPRS communication. e gateway components linking the busses are controlled by publishing gateway commands that specify which messages should be relayed and in what direction. All inter-component communication is handled uniformly regardless of whether components reside on the same host or not. Hereby, it is transparent for a sensor component whether the information it produces is used locally or on a remote host or both. In the paper, we demonstrate how a fleet management system can be implemented using the architecture without deploying code on the vehicles. e architecture was used in a set of prototype deployments in Aarhus Airport and at Abildskou rutebiler - a local coach company. e protocols described in chapter can be simultaneously deployed by implementing them in separate components. While the applications described all reside in the vehicular domain, the architecture can also be used in other domains. e basic communication abstraction provided, sending messages, can be used as a building block in more complex protocols. However, the gateways and busses have currently no support for prioritization of messages, which makes the infrastructure unsuitable for applications with
.. Architectural Choices
hard realtime requirements such as platooning and collision avoidance systems. Understandability is supported by using the same communication mechanism consistently throughout the system. When the busses have been implemented, the developer can express protocols in terms of publishing and subscribing. A challenge in developing VANET protocols is that testing and evaluating protocols in real life is very expensive and time consuming. An alternative is to use a network simulator such as e.g. NS- []. However, the use of simulation has some drawbacks. First of all, it is hard to simulate the physical properties of the communication medium and the OS protocol stack. Secondly, the protocols typically have to be developed specifically to the simulation framework. is means that the implementation evaluated will be another than the one deployed. e publishsubscribe infrastructure can be used to help alleviate the second problem. If a bus is developed for the network simulator, a real protocol implementation can interact with a simulated network and thus the confidence in the conformance between the simulator implementation and the real implementations can be enhanced. Maintainability is supported mainly in the decoupling provided by separating the system into components and letting them communicate via publish-subscribe. Each component is deployed as a separate binary library and can be added an removed at runtime without the system has to be restarted. Hereby, the deployment of software updates does not necessarily affect system availability. e loose coupling also means that changes to the system in many cases can be isolated to specific components which increases maintainability. Since all communication goes through a bus it is easy to monitor the communication among the components in the running system to locate errors quickly. Before a component can publish events with a particular topic, it first has to notify the bus by advertising the topic. Similarly, a component has to ask the bus to subscribe to a topic before any messages are received. Hereby publishing and subscribing are explicit actions and this makes it possible to deduce communication dependencies among components at runtime by inspecting advertising and subscription actions. is can be used to predict which components that will potentially malfunction if a particular component is stopped.
.. Business Model Implications In this context, we use the term business model to denote a model for conducting business. Chesbrough and Rosenbloom [] define the functions of a business model to be to identify and articulate value proposition, market segment, value chain, cost structure, profit potential, value network, and competitive strategy. Here, we primarily look at value proposition and value network. e value proposition is the value created for the user by the application. It can, e.g, be in the form of cost reductions or in the form of new possibilities and solutions. An example could be the cost reduction due to optimized vehicle routing in a fleet management solution, or the increased safety for a user of a collision warning system. e value network consists of the company behind the application, suppli
Chapter . Architecture in Vehicular Technology Applications
ers, customers, and third parties, and describes how value flows in the application domain. For some applications, the value proposition for customers increase when considered as part of a value network as opposed to viewing it in isolation. For example, a significant part of the value provided by a phone network operator to a user originates from the users ability to contact customers of competing operators. For some vehicular applications, there is an intricate interplay between the business model of the application and the software architecture. A chosen architecture can place limitations on the choice of business model and a selected business model can have implications on the design of the architecture (see figure .). If only infrastructure-based communication is used, there are only few constraints on the business model. However, when a VANET is used, there can be several problems that stem from the fact that the VANET will only function optimally with a significant user base. e first problem to overcome is the bootstrapping problem mentioned in section ... Initially, the value proposition of the application to the vehicle owner is limited because the system is not yet fully functional. is implies that there has to be some extra motivational factor if the vehicle owner is to buy the system. Secondly, there is a risk of fragmentation in the sense that, as competing companies introduce new applications, no single application will reach the critical mass of users reachequired for optimal functionality. erefore, it is essential that the role played by the application in the value network is so that there is a value proposition even if the application does not dominate the market. It should be noted that if all vehicles are controlled by the same organization, such as e.g. fleet management and platooning systems, bootstrapping and fragmentation are not necessarily problematic because the organization can simply install the system in the required amount of vehicles. If the chosen business model assumes that the company providing the application has complete control over the system, it might not be a good idea to use a solution based solely on VANET communication because the vehicles may be unreachable from the Internet most of the time. is makes it complicated to control access to the system and monitor usage for billing purposes. With respect to the taxonomy presented in table ., the business model is highly dependent on the penetration sensitivity. If the sensitivity is high, it is crucial that market dominance can be achieved or that competing companies can partake in the application to provide the required penetration ratio.
Contributions In chapter the paper Service Oriented Architecture for Inter-vehicle Applications presents a business model for the provision of information about the environment to drivers. Four categories of players in a value network with associated value propositions are identified. e four categories are: Sensor manufacturers that manufacture and sell hardware and software for sensing information about the environment. Data providers use the sensor hardware and software to gather data that is sold to presentation providers. Presentation providers sell software for presenting the data to drivers and subscriptions for getting access to the data. Data
.. Architectural Choices
consumers subscribe to information from the presentation providers that enhance comfort and security. Bootstrapping in the business model is handled by letting both drivers and independent parties provide data for the system using both infrastructure based and VANET communication. Besides having access to information about the environment, the data providers are also motivated by selling access to the information to the presentation providers - that in turn resells the information to data consumers. To avoid fragmentation of the market, we suggest that the exchange of information in the network should be based on standards. Since the business model is not based on a single company trying to dominate the market, individual players are motivated to expand the network. e players agree by contract to relay information from other players.
C Ո
D D V V N
In the previous chapter, we gave a range of examples of vehicular technology applications with varying requirements for communication. We discussed different designs of network and middleware architecture. In this chapter we look into different types of protocols for realizing communication. A first consideration is what type of communication is needed for a given application. Some applications require point-to-point communication whereas geographic broadcast is necessary in other applications. In section ., we describe the different delivery models relevant for vehicular technology applications. For each of these models, we motivate their use in vehicular technology applications and give examples of implementing protocols. In designing a protocol for a vehicular environment, it is important to be able to evaluate the protocol. is can however be difficult because it is a costly and slow process to set up a real network consisting of vehicles driving in a realistic environment. Alternately, emulation or simulation can be used. In section ., we described different methods and metrics for evaluation of protocols for vehicular environments. Finally, in section ., we describe our contributions with respect to data dissemination in vehicular networks. . D M For the range of applications described in section ., the requirements for communication vary. Not only in terms of quality parameters such as bandwidth, latency, coverage, etc., but also in the basic mode of operation. Some applications only require traditional point to point communication, while others require group communication. In this section we will describe five basic delivery models. e four of them, unicast, multicast, geocast, and publish-subscribe, are traditional in that they deliver a message from a sender to a set of receivers. In the last delivery model, datacentric delivery, there is no explicit receiver and the information communicated can be modified over time. In figure ., an overview of the delivery models can be seen. e interpretation of the relative vertical alignment of the delivery models in the figure is that a model,
Chapter . Data Dissemination in Vehicle to Vehicle Networks
A, is above a model, B , if A is a more general delivery model than B . For example, the multicast model can be considered more general than the unicast model because, in the multicast model, messages are delivered to a set of nodes (instead of just a single node). In the following, we describe each of the delivery models and give examples of implementing protocols.
Topic-based publish-subscribe
Multicast
Geocast
Data-centric delivery
Generality
Content-based publish-subscribe
Unicast
Figure .: Delivery Models
..
Unicast
Unicast is the most basic delivery model in which a message is sent from a sender and delivered to a single receiver. is communication form is used widely in the Internet and other places and is generic in the sense that a protocol implementing unicast can be used to implement other protocols that provide more advanced features such as reliability, congestion control, stream abstractions, etc. For vehicular applications, unicast protocols are useful when there is only a single receiver of a message and the identity of the receiver is known. is is, for example, the case in a fleet management system where the addresses of the participating vehicles and the server are all known. If no explicit address of the receiver is known, a name service, such as e.g. Domain Name System (DNS) [], has to be available. To realize a unicast protocol in a vehicular ad-hoc network, all vehicles have to act as routers and forward messages hop by hop. Routes in the network are volatile because vehicles constantly move in and out of range of each other, and therefore the strategy for finding and maintaining routes is important. Some protocols proactively find routes to other nodes before communication is initiated (e.g., Destination-Sequenced Distance-Vector routing DSDV [] and Optimized Link
.. Delivery Models
State routing OLSR []) while others reactively find them when needed (e.g., Ad hoc On-Demand Distance Vector routing AODV [] and Dynamic Source Routing DSR []). Finally, some protocols use geographic information to route messages (Greedy Perimeter Stateless Routing GPSR []). A prerequisite for this is that vehicles can determine their own position and that the location of the receiver of a message can be determined by querying a location service. In infrastructure-based networks, routes are easier to maintain because the infrastructure is static and thus it is easier to provide unicast protocols.
.. Multicast In the multicast delivery model, a message is sent to a set of receivers instead of just a single receiver. Since the set containing a single node is also a set, the multicast delivery model can be seen as a generalization of the unicast delivery model. Broadcast can be considered a special case of multicast in which messages are delivered to the set of all nodes. Typically, the set of receivers are specified by means of a multicast group address. is is the case in the Internet where a subset of the address space is reserved for multicast addresses. Here, nodes can state their interest in receiving messages sent to the group by joining the group by using the Internet Group Management Protocol (IGMP) [] for IPv or the Internet Control Message Protocol (ICMP) for IPv []. In vehicular applications, multicast protocols can, e.g., be used to find routes in unicast protocols (e.g. AODV []) and to implement a service discovery service. Another use could be to dispatch emergency information to other vehicles in a road state notification system. A simple way of realizing a multicast protocol in a VANET is first to implement a broadcasting protocol and then let nodes ignore messages to addresses they have no interest in. One way to implement a broadcasting protocol is to use a technique known as flooding. In flooding, a node initializes a broadcast by sending out a message to all of its one hop neighbors. ese nodes, in turn, forward the message to all of their neighbors and eventually all nodes in the network will receive the message. Flooding has the disadvantage that it potentially generates a lot of redundant traffic. In [], Ni et al. present several techniques to resolve this problem ranging from using back-off schemes based on counters, distance, location, and clusters, to using probabilistic forwarding. Broadcasting can also be implemented by using epidemic protocols []. Epidemic protocols emulate the spread of an infectious disease in a population. Every time a node receives a packet, it makes a probabilistic decision about which neighbors the node should forward the packet to. Epidemic protocols are, like the spread of diseases, robust to poor network conditions. An alternative to using broadcast is to form a multicast distribution tree [, pp. ]. is approach is well suited for infrastructure-based networks, but less suited for VANETs because if a link breaks, the tree has to be reformed. e mul
Chapter . Data Dissemination in Vehicle to Vehicle Networks
ticast tree can be made more robust by adding redundant links and thus converting it to a mesh [].
..
Geocast
In the geocast delivery model, messages can be sent to a location and whoever is present at that location will receive the message. A location can be either a specific point or an area. As mentioned in section .., if a location service is available, a geocasting protocol can be used to implement the unicast delivery model by first looking up the location of the destination node and then geocasting to that location. A geocasting protocol can, for example, be used to disseminate information about the state of the road at a particular location to the vehicles approaching that location. It can be sent either from nodes inside the destination region, but also from remote locations, e.g. a server. e realization of a geocasting protocol for a VANET can be divided into two steps. First, the message has to reach a node inside the destination area, and second, the message has to be distributed to all other nodes in the destination area. If a location service is a available that maps a location to a node identifier, a unicast protocol can be used to reach the destination area. Otherwise, a geographic routing protocol, such as e.g. GPSR [], can be used. Once inside the destination area a localized flooding protocol, where messages are only forwarded inside the destination area, can be used []. To provide geocasting in an infrastructure-based network, a location service is needed to provide information about the location of base stations, cell towers, etc. is information can be used to reach the base-station closest to the destination area and from here the message can be broadcasted directly to the receivers in if the transmission range is sufficient or flooding can be used as above. e location service can easily be maintained because the infrastructure is static.
..
Publish-Subscribe
In the publish-subscribe delivery model [], nodes can express interest in messages by subscribing to them. When a message matching the subscription is published, the subscribing node(s) will receive it. Here we consider two kinds of publishsubscribe: topic-based and content-based . In topic-based publish-subscribe, topics are semantic labels that are attached to messages when they are published. Messages are delivered to all nodes subscribing to the topic. In some variants, topics are arranged in a hierarchy, so that a subscription to a topic is automatically also a subscription to all sub-topics. In content-based publish-subscribe, nodes subscribe by providing a message predicate. For example, the predicate: ¹In [], a third kind, type-based publish-subscribe, is also described, but in this context we consider it a special case of content-based publish-subscribe.
.. Delivery Models
resource = 'gas' & price < 12.0 & provider = 'Shell'
matches all messages where the resource field is gas, the price is less than twelve, and the provider is Shell. When a message is published, it is evaluated against all predicates and delivered to the nodes with matching predicates. Since a subscription to a topic can be seen as a predicate, topic-based publish-subscribe can be seen as a special case of content-based publish-subscribe. Expressing the subscription in a predicate allows the subscriber to tailor the subscription precisely to his needs and hereby potentially save resources. Topicbased publish-subscribe has the benefit that the node(s) handling the distribution of messages do not have to be able to interpret the contents of messages as long as the topic can be read. One example of applicability in vehicular applications is the gas price notification system described in section .. Using content-based publish-subscribe, the driver could subscribe to gas prices below a certain threshold at gas stations along the route to his destination. e predicate would contain the threshold and a specification of a region close to the route. A simple way to implement a publish-subscribe system on top of a infrastructurebased network is to let a server manage subscriptions, publications, and event dissemination. When a node subscribes, it notifies a server that stores subscription information for all nodes in the system. When a message is published, it is sent to the server that determines who the message should be delivered to. e scalability of this centralized implementation is, however, limited because the server has to communicate directly with each of the subscribers for any given message. One optimization option for topic-based publish-subscribe is to create a multicast group for each topic by using the techniques described in section ... In a content-based publish-subscribe system, a subscription forwarding scheme [] can be used. First, the network graph is overlaid with a spanning tree. en, when a node subscribes by giving a predicate, the predicate is stored in all nodes on the path to the root of the tree. When a message is published, it is first forwarded to the root, and from there to the subtrees with matching predicates. In a VANET, it is not feasible to use a centralized solution because it cannot be assumed that vehicles are connected to the server at all times. Nor is a treebased solution optimal because the tree has to be reformed every time a link breaks. In [], Leontiadis and Mascolo present a decentralized alternative. e solution exploits the mobility pattern of vehicles and the observation that roads leading to the location a message concerns will most likely contain vehicles interested in the message. When a message is published, a number of replicas are created and distributed to a set of carrier vehicles, which are responsible for relaying the message to interested vehicles. e main idea of the contribution lies in the selection of carriers. e carriers are selected so that there is a carrier on each road leading to the location the message is about. Furthermore, the carriers are as far as possible from the location, within a maximum radius. Simulations show that after approximately five minutes, almost of the subscribing vehicles within a km radius receive
Chapter . Data Dissemination in Vehicle to Vehicle Networks
a published message. In [], Costa and Picco use a combination of subscription forwarding and probabilistic techniques for realizing a content-based publish-subscribe system for mobile ad-hoc networks. When a node subscribes by giving a predicate, the subscription is forwarded to all other nodes within a limited radius ϕ. When a message is published, it is propagated by using the subscription information stored and by selecting random neighbors. Every time a published message is received by a node, the message is forwarded to a percentage, τ , of its neighbors. e neighbors to forward to are selected by primarily looking at the stored subscription information and secondly, if the τ ratio has not been reached, by selecting random neighbors. Loops are avoided by using sequence numbers as in AODV [].
..
Delivery Model Addressing
Common to the first four delivery models is that, from an abstract point of view, they all use addressing for determining who should receive a message. e form of addressing distinguishes the delivery models and can therefore be used to classify them. In table ., we divide addressing along two axes.
Point Set
Identifier Unicast Multicast
Location Geocast Geocast
Topic Topic-based pub-sub Hierarchical Topic-based pub-sub
Predicate N/A Content-based pub-sub
Table .: Addressing e first axis concerns the nature of what is being addressed. An identifier is simply a name for the entity that should receive a message. If the address is a location, entities present at the location should receive the message. If the address is a topic, the message should be delivered to whoever have expressed interest in that topic. And, finally, for content-based publish-subscribe it can be said that messages are implicitly addressed to the predicates over them that evaluates to true. e second axis denotes the multiplicity of what is being addressed. A point is a single value and a set is a collection of values in the domain of addresses. Models where addresses are sets are more general than models addressing points, and this is also reflected in figure .. Note that in content-based publish-subscribe, it makes no sense to address a single predicate because there exists no message for which only a single true predicate exists.
..
Data-centric Delivery
For some applications, it is not possible to honor the communication requirements by only using general purpose protocols. Sometimes, it is necessary to specialize the communication protocols to a specific application and exploit characteristics of the data to optimize performance. In the data-centric delivery model, focus is not on
.. Protocol Evaluation
providing generic end-to-end delivery of messages as in the previous node-centric models, but rather on disseminating data among a set of hosts in the most efficient manner relative to the specific application requirements. Data-centric protocols are often used to disseminate information about phenomena in a geographic area. Since often the relevance of data about a phenomenon decreases with the distance to the phenomenon (cf. section ..), dissemination can be optimized by aggregating data about remote areas. In [], Nadeem et al. describes the TrafficView system where in-vehicle displays present drivers with a view of the traffic in front of the vehicle. In each vehicle, information about other vehicles is stored in records. e records are broadcasted periodically to other vehicles. To optimize performance, multiple records can be aggregated into a single record containing average values. e paper presents two algorithms for choosing which records to aggregate. . P E In developing protocols for vehicular technology applications, it is crucial that designers and developers can evaluate design decisions. If communication is based on infrastructure-based networks, it is relatively simple to run tests and measure performance because the infrastructure is static. In VANETs, however, it can be costly and time consuming to conduct experiments with hundreds of thousands of vehicles moving around. An alternative is to use analytic methods or to simulate parts of the system. In section .., we describe different methods for evaluation of VANET protocols. Orthogonal to the method of evaluation is the choice of metric. A wide range of performance parameters can be of interest ranging from general purpose metrics such as throughput, latency, and medium utilization, to application specific metrics such as awareness percentage and warning distance. In section .., we discuss the choice of metric. Finally, in section .., we present an overview of the different types of methods and metrics.
.. Method In this section, we describe four types of evaluation. Real life experiments, experiments with emulation, simulation, and analytical methods. e methods differ in the amount of resources required to perform them, and the confidence in the results obtained. Although we describe the methods in separation, they are often used in conjunction. We round the section off with a discussion about mobility models.
Real life experiments e problem with evaluation of VANET protocols is that the most realistic results are very expensive to obtain in terms of time and money. For complete confidence in the evaluation results, one would have to orchestrate hundreds or thousands of vehicles to move around in a realistic pattern. Furthermore, if the protocol is changed in any way, the experiments have to be repeated to deter
Chapter . Data Dissemination in Vehicle to Vehicle Networks
mine the effect of the change. In most situations, this kind of full scale evaluation is simply infeasible. An alternative is to setup a simplified scenario and only evaluate a subset of the system. is could for example be done by limiting the number of nodes as in [] where the DSR [] unicast routing protocol is evaluated in a network consisting of five vehicles and two stationary nodes. e mobility of the nodes is controlled manually, guided by differential GPS receivers. Another example is the MiNT-m testbed [] for mobile ad-hoc networks where a set of mobile robots can be programmed to move around in a predetermined pattern. Although this method of evaluation is resource consuming, the results obtained have a high likelihood of being in correspondence with reality.
Emulation e goal of emulation is to construct a piece of software that behaves exactly as what is being emulated. Often a physical entity is emulated, giving the benefits of working with software instead of hardware. For evaluation of VANET protocols it can be useful to emulate at least two parts of the system: the mobility of the nodes and the hardware platform. In the ORBIT testbed [], nodes are laid out in a by grid. e nodes are all connected through ethernet and each have a WLAN interface. Mobility is emulated by means of virtual nodes that migrate from hardware node to hardware node. is form of virtual mobility has the benefit that the rest of the system is very close to the real system. For example, the physical aspects of the wireless interface are preserved. By emulating the hardware platform, it is possible to run multiple network nodes on a single computer. is greatly reduces the work of installing software, replacing batteries, checking hardware, etc. Another motivation for emulating hardware is that the software evaluated is the same as the software that will be deployed. In TOSSIM [], applications built on top of the TinyOS operating system can be simulated with a high level of detail. TinyOS is a operating system for sensor networks where each hardware resource is encapsulated in a fine grained component. In TOSSIM most of these components, e.g. Analog-to-Digital converters, the clock, the EEPROM, etc., are emulated. e only exception is the radio hardware, which is not emulated to increase the scalability of the simulator. Hereby, thousands of nodes can be emulated on s single PC. Simulation While emulation provides reliable results and can evaluate protocols in large networks, it can be an unattractive solution in some situations. First of all, an emulator might not always be available for the type of network or platform a protocol is being developed for and it is a very complex task to implement a good emulator. Secondly, running large experiments on an emulated platform can be very time consuming due to the amount of details that has to be simulated in software. is is not necessarily a problem for the final evaluation of a protocol, but during development it prohibits iterative incremental protocol development.
.. Protocol Evaluation
An alternative is to make a simplified model of some parts of the system. For example, it can be useful to make a graph abstraction of the network. Instead of simulating physical radio propagation effects, the network can be modeled as a graph where nodes are either connected or not connected. is makes it impossible to estimate factors such as e.g. packet collision, but it is still possible to evaluate the functionality of algorithms. In the Sinalgo simulation framework [], routing protocols can be developed in Java and simulated with thousands of nodes. Instead of implementing the full network stack, Sinalgo provides the developer with a message passing view of the network and focuses on fast prototype development. e widely used network simulator NS- [] provides a more detailed implementation of the network stack and allows for simulation of a wide array of protocols ranging from satellite networks to mobile ad-hoc networks.
Analytical methods In the earliest phases of protocol development, it can be useful to rely on analytical methods for determining protocol properties. Formal arguments typically require an abstract view of the network which can introduce uncertainties. On the other hand, results obtained by formal methods will not depend on any particular implementation and is thus not susceptible to bugs in protocol or simulation code. Furthermore, formal methods can be used to prove properties about protocols while experimentation can only observe them. For example, in [] different techniques for limiting the amount of redundant transmissions in a flooding protocol are evaluated. e authors analyze the schemes by looking at the geographic area each node’s transmission covers and how much these areas overlap. e arguments are based on a simplified model of radio transmission: if a node a transmits a message then a node b will receive it if, and only if, the distance from a to b is less than the transmission range. is implies that the area covered area by a’s transmission is a disc with a radius equal to the transmission range. In reality, the shape of the area depends on the radio hardware, and there is not an exact boundary for when the message will be received and when it will not be received. Mobility models If mobility is simulated in the evaluation of a VANET protocol, it is important to consider the choice of mobility model that will determine how vehicles move throughout the evaluation. It has been shown that evaluation results can be highly dependent on the chosen mobility model []. Traditionally, mobile adhoc network protocols have been evaluated using simplified mobility models such random direction and random waypoint []. However, a defining characteristic of vehicular environments is the particular kind of constrained mobility and therefore more accurate models are needed for the evaluation of VANET protocols. e optimal solution would be to use traces of real traffic situations, but unfortunately, no such traces for large scale networks are currently available. A common approach is to let a traffic simulator generate vehicle movement and feed the result into the network simulator. Traffic simulators can be divided into macroscopic
Chapter . Data Dissemination in Vehicle to Vehicle Networks
and microscopic simulators. Macroscopic simulators consider aggregate properties of the traffic such as traffic density and flow, whereas microscopic simulators model each vehicle in separation taking into account the vehicles destination and the movement of nearby vehicles. For example, in [], a microscopic traffic simulator was used to generate a mobility trace for a road map of part of Switzerland. e AODV [] and GPSR [] routing protocols were evaluated using the trace and a random way-point mobility model and significant differences were observed. For some types of protocols, it is not enough to generate movement traces before evaluation. If, e.g., a protocol for a collision warning system is evaluated, it is possible that the communication in the network will affect the mobility of vehicles. If a driver receives a collision warning, it is reasonable to assume that he will hit the brakes causing vehicles driving behind him to brake as well. In [] this is addressed by integrating the traffic simulator with the network simulator providing two-way interaction at runtime.
..
Metrics
Here we divide metrics into general purpose metrics that apply to a wide range of protocols and application specific metrics that measure properties relevant to a particular application or a family of applications. When developing general purpose protocols, such e.g. unicast or multicast protocols, it is relevant to evaluate them using general purpose metrics such as throughput, latency, and medium utilization. is illuminates important properties of the protocols and enables easy comparison with other protocols implementing the same delivery model. It can, however, be harder to estimate how well a particular protocol is suited for a concrete application. When the suitability of a protocol is evaluated for a particular application, it is relevant to look at application specific metrics. For example, for a collision warning system, an important parameter is how long in advance the driver gets notified about a potential collision. e results obtained using application specific metrics show, with a high degree of confidence, how suited a protocol is for at particular application, but provides no insight to how other protocols would perform for that particular application or how usable the protocol would be for other applications. For data-centric protocols, it is often necessary to use application specific metrics because the protocol is application specific.
..
Evaluation Classification
In table . an overview of the methods and metrics for evaluation of VANET protocols can be seen. Each entry in the table corresponds to a approach to protocol evaluation. Methods are ordered according to the amount of resources required to perform them and according how realistic the evaluation is. e metrics are ordered according to general applicability of the results and to the closeness to a concrete application. Consider for example, the lower right corner: analytical methods us
.. Contributions
ing general purpose metrics. is type of evaluation requires few resources, but has low realism because it relies on a simplified model. e results are of general applicability, but are relatively far from a concrete application. Method Metric
Real life experiments
Emulation
Simulation
Analytical methods
Application specific General purpose
Table .: Methods and Metrics Protocols should be evaluated using multiple types of evaluation because each type has its strengths and weaknesses. Early on in the development process when the design space is open, it is important with many iterations and therefore the evaluation method should not require a lot of resources. But as the design gets more detailed, more realistic evaluation is required. e selection of metrics depends to some degree on the purpose of developing the protocol. For business oriented protocol development, it is important to reach the upper left corner in table . at some stage because the successful operation of the application is crucial for financial success. For basic research, it is more important that the results have general applicability. An exception is the datacentric protocols for which application specific metrics should be used. . C In chapter , the paper Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks presents a comparative simulation study of two protocols for dissemination of data in a traffic warning system. In the traffic warning system, each vehicle continuously senses the condition of the road at its current location and forwards the information to other nodes. e protocols were designed to be light-weight and robust to changes in network density and node mobility. e first protocol, zone flooding, implements the geocast delivery model described in section .., with the limitation that the sender node has to be inside the geocast destination area. e protocol is a variant of simple flooding where message forwarding is limited by three rules. Firstly, each message will only be forwarded at maximum n times. Messages contain a hop-count field that is decremented every time the message is forwarded. When the hop-count reaches zero, the message will no longer be forwarded. Secondly, sequence lists (as used in AODV []) ensure that all nodes will forward any particular message at most once. Finally, each message contains a destination region outside which the message will never be forwarded. To realize the traffic warning system, each node periodically initiates a flooding with information about the road at its current location.
Chapter . Data Dissemination in Vehicle to Vehicle Networks
e second protocol, zone diffusion, is a data-centric dissemination protocol (cf. section ..) in which each node maintains an environment representation (ER) containing the state the road in the neighborhood of the node. e ER is periodically broadcasted to other nodes. When a node receives an ER from another node, the received ER is merged into the local one. If the ERs contain contradicting values, a policy determines which value will be used. e protocols were evaluated by simulating traffic scenarios based on the microscopic Freeway [] mobility model. Traffic traces were generated for a straight section of road, meters long and meters wide, with vehicles moving in both directions. To evaluate the protocols robustness to changing network mobility and density, three classes of mobility were simulated: low velocity, medium, and high velocity. In addition, the node count of the traces varied from to . e simulations were conducted using the network simulator NS- [] with varying broadcasting intervals. Performance was measured using general purpose and application specific metrics (cf. section ..). We measured the amount of packets sent, received, and dropped to estimate network load. In addition, we measured the awareness percentage - the fraction of vehicles receiving information about a particular area before entering the area. e protocols proved both to have suitable performance for the traffic warning system. e zone flooding protocol generally achieves better awareness percentage than the zone diffusion protocol, but the zone diffusion protocol achieves reasonable awareness percentage at a much lower network utilization. To identify the best protocol with respect to network load and awareness percentage over all combinations of mobility and network densities, we analyzed the simulation results using multi-objective optimization. It was found that if an awareness percentage of . was acceptable then the zone diffusion protocol should always be used. e fact that an awareness percentage of at least . was achieved in all the simulated scenarios using the zone diffusion protocol indicates that the protocol is robust with respect to varying traffic mobility and density.
²cf. section ..
C Ո
S C
While the previous chapter focused on enabling communication in vehicular networks, we now take a broader perspective and consider using service composition for realizing service oriented architecture. As described in the introduction in chapter , we consider the goal of service oriented architecture to be to match needs with capabilities. While this can be done in a number of ways, we here focus on using service composition mechanisms. In the next section, we motivate the use of service composition by presenting an application scenario. Following that, we present a general model of service composition. Based on the model, we present a framework for categorization of service composition mechanisms in section ., and finally in section ., we describe our contributions relating to service composition for pervasive computing. . A S e following scenario motivates the use of service composition in pervasive computing. An overview of the scenario is presented in figure . Consider a driver on his way to a faraway destination. He knows that before reaching his target, he has to stop for gas somewhere along the way. To minimize the total cost of his journey, he is interested in knowing which gas station in the neighborhood of his route provides the cheapest gas. A server on the Internet provides information about gas prices at different gas stations in the area, but has no knowledge about the location of the gas stations. However, a location service can, given a specification of an area, return the names of the gas stations in that area. An example of a location service could, e.g., by the Google Maps service []. If he were to complete the task manually, he would have to go through the following steps: . Enter his destination into the navigation system in his vehicle and in return get some specification of the neighborhood of his route. . Query the location service for the names of gas stations near his route. . Query the gas price server for prices at the gas stations returned by the location service
Chapter . Service Composition
92:10.12 95:10.52 98:11.02 92:10.12 95:10.52 98:11.02
GAS 4. Get gas
1. Enter destination 2. Get gas stations near route
3. Get gas prices
Internet
Navigation System Location service
Gas price server
Figure .: Scenario
. Select the gas station with the lowest price and go to the station to refuel his car. Finding the lowest gas prices along the route to a destination is an attractive service for many users and therefore it makes sense to implement a system providing the service. Such a system can be realized in at least two ways. A simple solution would be to implement the steps described above in an application running on the navigation system. e application would invoke each of the entailed services and use the results returned as input for the service in the next step. is solution has, however, at least two drawbacks. Firstly, the system is bound to a particular set of services, and if a service has to be replaced, the application has to be reimplemented. Secondly, it could be that the application could be used as part of another application. For example, if the driver has to take a detour to reach the gas station, he might be interested in notifying people at his destination of his delayed arrival. If this new application is to be realized, the application would have to be rewritten. A more flexible solution would be to use a service composition framework to compose the application from the services in the scenario. From a conceptual point of view, it makes sense to consider the application as a composition of services and using a service composition framework can significantly reduce the effort required to implement the application. Instead of hardcoding the logic of the system, a specification describes how the service composition is constructed. Depending on the composition framework used, there can be support for replacing services at runtime and to expose the service composition as a service in itself making it possible for it
.. Service Composition Model
to be part of other applications. . S C M In this section, we describe a model for composition of services in pervasive computing. e purpose of the model is to identify a set of central concepts and their mutual relation to provide a vocabulary for the discussion of service composition in the following sections. e model consists of services, the specifying actor, the composite specification, and the composite, which will each be described in the following. In figure ., an overview of the model can be seen.
Composite Service Specifies
Specification
Service
Instatiated Service
Specifying Actor
Optionals
Figure .: Service composition model
Services A service is the basic means of providing a programmatic interface to a capability. While the capability might be anything ranging from a temperature sensor to a banking system, the service is a piece of software that makes it possible to access that capability. In the introduction in section ., we defined a service as follows: A service is a unit of runtime software accessible by others. Note that a prerequisite for being able to access a service is that the address of the service is known. If the address it not to be hardcoded into the composite, a service discovery mechanism has to be available []. In the scenario in section ., the navigation system, the location service, and the gas price server are all services. e capability provided by the navigation system is the ability to return a route from the current location to a destination. e location service has the capability to return a list of identities and matching locations of all entities of a particular type within a specified area, and the gas price server has the capability to return the gas prices at a specified gas station.
Chapter . Service Composition
Specifying actor e specifying actor is the entity that specifies the composite. is can, e.g., involve constructing code, interacting with a user interface, or physically connecting hardware. e specifying actor takes the initiative to create the composite for the first time. It might not be the same entity that eventually will end up using the composite. e motive behind initiating the creation of the composite can vary from convenience to profit. In the scenario above, there are several options for specifying actors. One candidate could be the navigation system provider. By creating the composite, the navigation system provider adds value to his product. Another option is the driver that creates the composite to solve his concrete problem. In addition, the location service provider, the gas server provider, and the gas station owner could have interest in creating the composite. Specification e composite specification describes how the composite should look and behave at runtime. e specification can take on different forms, but typically contains information about which services should be part of the composite and how they should interact. e specification can also contain additional information such as, e.g., procedures for handling unexpected situations, requirements for quality of service, etc. A specification for a composite realizing the scenario above could, e.g., contain a list of identities if the services involved in the scenario, and a script detailing the logic in the application. Composite e composite is the instantiation of the composite specification and therefore consists of a set of services matching the services in the specification and some running management code handling the functionality in the composite that is not part of the services. e tasks of the management code include governing the interaction among the services, handling unexpected situations, ensuring quality of service requirements are satisfied, etc. In the scenario above, the composite would contain all the necessary services and the management code. e management code could, e.g., run on a server on the Internet or on the navigation system. .
C F
In this section, we describe a categorization framework for service composition mechanisms for pervasive computing based on the work in the paper presented in chapter and its previous version []. Here, we use the framework to describe the variability in service composition mechanisms in the literature and as a frame for the description of the contributions in the following section. e categorization framework consists on nine categories that illuminate different aspects of service composition mechanisms. e categories were selected by surveying a set of service composition mechanism and identifying their variation
.. Categorization Framework
points. Below, we describe each of the categories by using the model introduced in the previous section and give examples of the possible values by referring to the literature. In table . in chapter , an overview of how a range of service composition mechanisms from the literature relate to the framework is presented. For convenience, the table is also listed at the end of this chapter as table ..
Specified by denotes the type of specifying actor. e mechanism used for specifying the composite can be aimed at developers as a tool for constructing general applications, or it can be aimed at the user to let him tailor an application for his particular needs. If a developer specifies the composite he can only try to anticipate what services will be available at runtime, whereas if the user specifies the composite he can design the composite from the available services and compose services and devices in new unanticipated ways as in [, ]. Since a developer can be seen as a particular kind of user, technologies that support user specified composites also support developer specified composites. For example, consider the scenario in figure .. If the driver specifies the composite, naturally, the composition mechanism should support user specified composites, whereas if the navigation system provider specifies the composite, it is enough that the composition mechanism supports developer specified composites. In Service Composition for Mobile Environments (SCfME) [], which encompasses protocols for service composition in mobile ad hoc network environments, the composition is specified by application developers through a DAML description [] of a “Description-level Service Flow” (DSF) in which sequences of services may be described. Another example is ICrafter [] in which users, operating through a GUI, may combine services from different devices and have an aggregated user interface generated. With UbiDev [], an application developer supplies an ontology, classifiers, and user interfaces for services in an application. e classifiers map resources on devices into concepts in the ontology. A service is then defined as an atomic action that transforms an input resource yielding a new resource as output. Services are constrained by the concept (from the ontology) that it accepts as argument, and the concept it produces as output. Specified at e specifying actor can specify the composite at development time, before the composition framework is up and running, or at runtime. Note that if the composite is specified before runtime, it implies that it is done by a developer since the user, at that time, has no way of interacting with the system. If the composite can be specified at runtime, there is no need for restarting the composition framework. If the driver in the scenario in figure . is the specifying actor, then the composition mechanism has to support runtime specified composites. In contrast, if the composite is specified by the navigation system provider, the composition mecha
Chapter . Service Composition
nism only has to support development time specification. Both ICrafter and SCfME provide for runtime composition specification. In ICrafter, users may explore services available at runtime through the GUI of a general purpose Interface Manager (IM) service. With the interface of the IM the available services can be explored and a subset selected. An aggregate interface is then requested for the selected set of services. In SCfME an application developer may supply new DSFs at runtime and have these bound dynamically to an “Execution-Level Service Flow” (ESF) containing references to actual services. UbiDev is more static in the sense that an ontology and corresponding classifiers need to be provided prior to deploying the application. To change the possible service compositions, either the ontology or the classifiers need to be changed, something that appears only to be possible at development time.
Specified in e specification can be specified by providing source code, configurations, or interacting with a tool. If the composite is specified by user interaction, an underlying representation has to be available to make the specification persistent. Since the driver in the scenario in figure . cannot be expected to be able to create source code or configuration files, the composition mechanism used has to provide a graphical user interface if the driver specifies the composite. A navigation system provider specifying the composite might not be interested in letting other parties modify the composite and could therefore be motivated to use a composition mechanism where composites are specified in source code. Finally, a motivation for using a composition mechanism where composites are specified in a configuration, could be that it is clear to see which services are used and how. If, e.g., the composite is specified by the location service provider and downloaded by the driver from the Internet, the driver could be assured that the composite behaves as specified and has no malicious behavior just by looking at the configuration. In ICrafter, the composition is specified by interacting with a tool in which services are rendered. Services are described with a SDL (Service Description Language) that includes a simple type system oriented towards UI generation. In SCfME, the service composition is described via a configuration (a DAML XML document) and in UbiDev the specification is partly programmatic since application developers need to supply classifiers. Level e services in the composite specification can be represented as instances, types, or implicitly. In the case of instances, a particular service is bound to the composite by e.g. an URN []. If the services are specified by types there can be several candidates for each service specified. Finally, if the user instead of specifying how services are connected, requests a task from the framework that has to be resolved into a composition of services, we regard the services as being specified implicitly. If the driver in the scenario in figure . specifies the composite using a GUI, conceptually, there can be at least two ways to do this. Firstly, the GUI can let the
.. Categorization Framework
him construct the composite taking as outset the currently available services in a prototype-based programming [] approach. Hereby, the services are specified at the level of instances. Secondly, the GUI can let the driver specify what his goal is, e.g. by using concepts in an ontology. An example could be some visual representation of the statement: “Get lowest gas price near route to Bob”. e statement would then be parsed and matched against the available services. Finally, an example of type-level composite specification could be the navigation system provider using source code to include the any available location service in the composite. With respect to the level of description, SCfME is characteristic of an approach in which the composition is described at a type level and resolved at runtime by the service composition implementation to an instance level. ICrafter, on the other hand, operates only on an instance level in that it is specific services that users select for inclusion in the composite. Finally, UbiDev operates on an implicit level based on the ontology and classifiers specified. One example is a generic messaging service, document_to_display that can be adapted to the context by UbiDev. If the user context is a personal phone, UbiDev will compose the services ascii_to_wav, wav_to_adpcm, and adpcm_to_voice to provide the document_to_display service.
Quality of Service (QoS) requirements Some composition mechanisms support specifying quality of service requirements in the composite specification. If, for instance, the services are specified as types the selection of the actual instances can be guided by the quality of service requirement specification. One example of a quality of service requirements in the composite in the scenario in figure ., could be that the driver, for protection of privacy, might not want the location service to store his location, but if no such location service is available, he is ready to settle for a normal location service. In the Amigo service composition mechanism [], services are described as semantic Web services (using OWL-S []) in which atomic processes have QoS attributes with values obtained from runtime measurements. An example of a QoS requirement would be that latency should be less than a threshold. At runtime, an abstract specification of a composite service is matched against possible realizations, the latencies for the realizations are calculated, and the best composition is chosen (also subject to other constraints) []. Contingencies Unforeseen conditions can be handled at different levels. e trivial option is to have no support for contingencies at all. A slightly more advanced solution is to detect the contingency and alert the user, and a natural extension of this approach is to resolve the contingency automatically. It should be noted that in some cases, it is impossible to resolve contingencies automatically and in these situations, the user should be in the loop. An example on a contingency in the scenario in figure . could be that an accident occurs somewhere on the route from the driver to his destination forcing the navigation system to recalculate the route. Since the gas price information is no
Chapter . Service Composition
longer valid for the new route, something should be done to correct the situation. If the composition mechanism has no support for detection of contingencies, the driver will potentially miss the gas station and run out of gas. If the composition mechanism detects the contingency, it can either notify the driver about the problem or try to resolve the situation by recalculating the cheapest gas station along his new route. As an example, in SCfME the state of the execution of a composition is checkpointed by sending partial results back to the service requester. If the Composition Manager fails, the service requester is notified and may create a new concrete ESF based on the original abstract DSF and its latest checkpoint and finds a new composition manager. In UbiDev, since the composition is implicit and dynamic, contingencies such as partial failures will be handled automatically as classifiers find new ways of realizing compositions.
Resource use Since many devices for pervasive computing have limited resources, it is relevant to look at resource use. We divide composition mechanisms into what kind of system the composition mechanism requires. One type is a server platform and another is a typical PDA. A third category would be a smaller sensor/actuator platform such as Motes (http://www.tinyos.net/). If the navigation system in the scenario in figure . is comparable with a PDA platform, the composition mechanism should be able to run on PDA-type systems. For the scenario, it is not a problem if the composite is coordinated from a server on the Internet. A number of solutions apply semantic Web technology (e.g., SCfME and Amigo), which means that at least parts of the middleware will not scale to low-end devices. Other than that, most service composition mechanisms seem to aim at PDA-type devices and only DSCiPC [] integrates sensor/actuator platforms. Infrastructure In pervasive computing environments, services might not be connected at all times. Devices may enter and leave a given network and therefore it is important whether the composite has to have a fixed connection during operation or whether devices can enter and leave on an ad hoc basis. When the vehicle in the scenario in figure . queries the Internet servers for information about locations and gas prices it is necessary that the navigation system in online and thus connected to an infrastructured network and hereby the scenario places no requirements on which infrastructures the composition mechanism should support. On the other hand, if the location information and gas prices where provided by other vehicles instead of Internet servers, it would be a prerequisite that the composition mechanism supported ad-hoc networks. In SCfME, devices are peers and communicate via ad hoc protocols. In particular, a Group-based Service Routing (GSR) on-demand protocol in which the route is constructed during service discovery is used for routing service invocations.
.. Contributions
In contrast, ICrafter assumes a fixed infrastructure in which a global communication infrastructure resembling a tuplespace may be constructed.
Topology Some of the mechanisms require a central node to act as a coordinator for the composite and thereby impose a centralized structure on that composite, whereas other mechanisms allows for a decentralized structure. SCfME is decentralized in that after an ESF is created, any node in the system can be used as a Composition Manager that handles the execution of the composition. e Composition Manager may be dynamically changed during the execution. Based on finite state automata for individual OWL-S processes, the Amigo service composition mechanism builds a global finite state automaton for all services. In this sense, the Amigo service composition mechanism relies on a central component. . C In this section, we describe our contributions relating to service composition for pervasive computing.
.. Service Composition for Pervasive Computing e paper Issues in Service Composition for Pervasive Computing in chapter analyzes the use of service composition for pervasive computing applications. With the goal of investigating what is required for a service composition mechanism for pervasive computing, we identified a set of characteristics of pervasive computing technologies. As described in the introduction in chapter , pervasive computing technologies are characterized by being openended, context aware, dynamic, and heterogeneous. Furthermore, they may incorporate networked sensors and actuators and present new challenges to usability. For a service composition mechanism to be usable in a pervasive computing setting, the composites created by the mechanism should be able to exhibit these characteristics. If, for example, the composition mechanism only runs on PC scale systems, the mechanism is not suited for pervasive computing. While some of these characteristics can be supported from the level of services, in the paper we only consider the support provided by the composition mechanism. In the following, we shortly summarize the conclusions of the paper with respect to each of the characteristics.
Openendedness It is often the case that applications of pervasive computing need to be repurposed to match new user requirements or changes in the context. To some degree, changes in the context can be resolved automatically, but if the users requirements change, it can be hard for the system adapt. To take changes in user requirements into consideration, we claim that the user should be in the loop. It
Chapter . Service Composition
should thus be possible for the user to (re)specify the composite at runtime.
Context awareness e support for context awareness can be divided according to when it is provided. Before the composite is instantiated, support can be provided by selecting the services to participate in the composite based on context information. For this to be possible, there should be room for selection in the declaration of the services in the composite specification. If types are used to declare the services in the specification or if the services are declared implicitly, there can be several choices for each role in the composite. But if the services are declared by specifying instances, multiple choices has to be available for each role in the composite. e selection of which services should be part of the composite at runtime can e.g. be guided by quality of service specifications. At runtime, context awareness can be supported by providing support for contingency handling. If the composition mechanism only support the detection of contingencies, it should be possible for the user to resolve the contingency manually by, e.g., respecifying the composite at runtime.
Dynamicity Dynamicity in which services are available can be supported by providing contingency handling. In case of a fault, a replacement service should be found and/or the user should be notified. In some applications, any node can enter or leave the network at any time. Under these circumstances, the topology should be decentralized in case the contingency handling node leaves. Dynamicity in the quality of service provided can be supported by allowing for quality of service requirements in the composite specification. If, for example, the communication bandwidth to a service drops below a certain level because of noise in the communication channel, the composite mechanism could try to find a replacement service.
Heterogeneous devices Since it can be expected that pervasive computing applications will consists of heterogeneous devices, the composition mechanism should be designed to distribute the responsibility of managing the composite based on device capabilities. Nodes can be heterogeneous in terms of computation capability, memory availability, communication capability, power availability, mobility, user interface, etc. and therefore it is important that the composite is instantiated considering the available context. Optimally, the responsibility of managing the composite should be distributed among the most capable nodes, considering the concrete requirements a particular management task has. If, e.g., service descriptions are stored in a central registry, the node hosting the registry should have high availability and should be able to handle a high number of requests. Similarly, if the user can interact with a composite management interface, the interface should be located in close proximity to the user and on a device with suitable IO capability.
.. Contributions
Networked embedded sensors and actuators A prerequisite for including embedded nodes in a composite is that the composition mechanism is designed so that the resource requirements for the embedded nodes are suitable. Typically, this implies that not all nodes are equal in the composite with respect to monitoring connections, forwarding service invocations, etc., and therefore a centralized, or at least not completely decentralized, topology is preferable. If the topology is completely decentralized, all devices must have a representation (or at least a part of ) the composite specification, which makes it important that the composite is specified in a compact form. An xml configuration is typically more cumbersome than compiled source. Usability e usability of a composite is to a large degree determined by how the user interacts with the composite. An important parameter here is the design of the user interface, but here we do not consider the user interface of the service composite to be part of the composition mechanism and will therefore not discuss this further. One aspect of usability is that if the user specifies the composite, he can adapt the application to his concrete needs. If a tool is available for specification of the composite, he is better of than if the composite has to be specified in a configuration file or in source code. It can be argued that it is easier for the user if he only has to express his intention and let the composition mechanism translate his intentions to a concrete composite. By using this approach there is, however, gap between the users understanding of the composite and the concrete layout of the composite. During normal operation, this is not a problem, but if contingencies arise and the user has to resolve the situation, the composition mechanism has to be able to express the problem in terms understandable by the user - and here the gap might be a problem. Relation to the categorization framework By using the categorization framework presented in section . as an outset, we analyzed the relation between the characteristics and the categories in the framework. In table ., an overview of the dependencies can be seen. As can be seen in the table, there is not a one to one relation ship between the characteristics of pervasive computing and the categories in the framework. Table . can be used together with table . to get an overview of how pervasive computing characteristics are supported in current service composition mechanisms in table .. .. Dynamic Membership Composites e paper Handling membership dynamicity in service composition in chapter , investigates the problem of handling composites where the set of participating services in the composite varies over time. An example could be a chat application that dy
x
x x
x
x x x
x x x
x x
Topology
x
Infrastructure
Contingencies
x x
Resource use
QoS requirements
Specified at x
Level
Context Awareness Networked Embedded Sensors and Actuators Heterogeneous Devices Dynamicity Openendedness Usability
Specified in
Specified by
Chapter . Service Composition
x
x x
Table .: Characteristic/Category Dependencies
namically expands as users arrive. A set of users could be carrying mobile devices and when a group of users meet, they can use the application to chat. It can be problematic to realize this application using traditional composition mechanisms, because it is unknown when the composite is created which services will eventually be part of the composite. Furthermore, the nature of the application is that users leave and join on an ad-hoc basis implying that none of the mobile devices should host the composite by itself. It is trivial to express the application in source code using programming abstractions such as collections, etc., but if the user should be able to compose the application, using source code is not an option. In the paper, we present an extension of the PalCom assembly script language [] that makes it possible to specify composites with varying member sets. In the following, we first describe the PalCom assembly script language and following that, we describe our extensions.
e PalCom assembly script language In the PalCom architecture, device functionality is encapsulated in services that can be remotely discovered and invoked. Each service has a set of commands that can be either in-going or out-going. In-going commands are similar to asynchronous methods with an optional number of parameters. ey can be invoked from other services or by the user. Out-going commands make it possible for the services to provide output. e output can be used as input for in-going commands or can be presented directly to the user. e output has an optional number of parameters. An example could be a service acting as an interface for a lamp. e service could have two in-going commands on and off and an out-going command state that is invoked every time the state of the lamp is changed. Services and commands are composed in assemblies described by assembly scripts where services and devices are declared along with a description of which commands are connected. Variables that can hold state can also be declared. e gas price scenario in figure . can be implemented by the assembly script listed in figure .. Lines – declare which devices take part in the assembly. Note that a unique name (URN) is given for each of the devices. Similarly,
.. Contributions
assembly GasPrices { devices { nav_system = urn:palcom://garmin-street-pilot-c580-AE3C; lshost = urn:palcom://location.service.com; gphost = urn:palcom://gas.prices.com; } services { ui on nav_system = /navigavtion_ui; gas_price_display on nav_system = /gas_price_display; location_service on lshost = /location_service; gas_prices on gphost = /gas_prices; } connections { ... } script { variables {} eventhandler { when destination_entered from ui on nav_system { send get_route(thisevent.destination) to ui on nav_system; } when route_found from ui on nav_system { send lookup("gas station", thisevent.route) to location_service on lshost; } when found from location_service on lshost { send get_prices(thisevent.entities_found) to gas_prices on gphost; } when return_prices from gas_prices on gphost { send display_cheapest(thisevent.prices) to gas_price_display on nav_system; } } } }
Figure .: GasPrices script
lines – declare the services in the assembly. In line –, the flow of events through the assembly is described. E.g., lines – specify that when the outgoing route_found command from the navigation systems’ ui service is invoked, the location_servive’s lookup command on the location server (lshost) is invoked. e script in figure . can be created by using a text editor or by the user by interacting with a tool.
Extensions e extensions of the assembly script language we propose can be divided into two parts: selection is about selecting which devices should participate in the assembly and naming deals with how to represent the services and devices in the specification of the flow of events. We describe selection in the next paragraph and naming in the following paragraph. Given a set of nodes we need a method for selecting those that should be part of the assembly. In the unextended version of the scripts, this is done using URNs but for assemblies with dynamic membership this is, as mentioned previously, not enough. Instead, we propose to use a simple wildcard pattern on the device URN so that a single line in the device declaration part of the script (lines – in figure .)
Chapter . Service Composition
can declare multiple devices. Lines not including a wildcard character (‘*’) will be interpreted as before. As an example, the line: chat_device = urn:palcom://pda*
matches all devices with a URN with the prefix urn:palcom://pda. Hereby, all the chat clients in a chat application can be declared in a single line. With the extension mentioned above, each line in the device and service declaration parts of the script potentially declares multiple devices/services and associates a name. is name is used in the eventhandler part of the script to specify the flow of events. We extend the semantics of the eventhandler part so that the line: when message_typed from chat on chat_device {
is used when the out-going command message_typed is invoked on any chat_device. In the case that chat_device only denotes a single device, the interpretation is unaltered. Similarly, the interpretation of the invoke part of the eventhandler is changed so that the line: send display_message(thisevent.message) to chat on chat_device;
will invoke the display_message in-going command on all the devices denoted by chat_device. Again, if chat_device only denotes a single device, the interpretation is unaltered. To allow for local flow of events on devices declared with a wildcard, the keyword ‘local’ can be inserted into the send statement to denote that only services on the same device are invoked. Assume for example that chat_device is declared using a wildcard and the eventhandler includes the following lines: when message_typed from chat on chat_device { send local display_message(thisevent.message) to chat on chat_device; }
en, when the message_typed command is invoked on a device, the display_message command will only be invoked on the same device. e modifications above all have the property that if no device is declared using a wildcard, then there are no modifications of the interpretation of the assembly scripts. is implies that the changes are backwards compatible. In the paper, we argue that the extended script language is expressive enough for realistic applications by demonstrating its use in an application scenario developed in cooperation with end-users. A preliminary user study indicates that the language is suited for pervasive computing applications, that it is not hard to understand, and that it is only mildly complicated to use. In addition to the script language extensions, we have implemented a decentralized interpretation engine for the language. Experiments showed that the performance of the engine is appropriate for pervasive computing applications.
.. Contributions
Using the framework described in section ., we have categorized the standard PalCom service composition mechanism and the extended script language running on the decentralized implementation. In table ., the result can be seen. Category Specified by Specified at Specified in Level QoS reqs. Contingencies Resource use Infrastructure Topology
Standard End-user Runtime Configuration Instances No Automatic PDA Ad Hoc Centralized
Extended End-user Runtime Configuration Types No No PDA Ad Hoc Decentralized
Table .: Categorization e two mechanisms differ in the following ways. In the standard composition mechanism, services are specified at the level of instances whereas in the extended composition mechanism services are specified by declaring sets of URNs. Since a wildcard expression do not denote a single instance but rather a set of instances, we have classified the extended composition mechanism as specifying services at the level of types. e standard PalCom composition mechanism has automatic contingency management whereas the extended composition mechanism currently has no support for contingencies. Finally, the standard PalCom composition mechanism relies on a centralized topology whereas the extended composition mechanism runs decentralized.
Chapter . Service Composition
System Amigo [109, 148] Aura [56, 141] Daidalos [160] DSCiPC [79] DSD [8] GAIA [135] ICrafter [130] Obje [41] one.world [62,63] Ozone (WSAMI) [75] PalCom [145] Paths [86] QuAMobile [2] SCfME [32] SpeakEasy [40, 42, 115] TCE [100, 101] UbiDev [94]
Composite Specification Specified by Specified at End-users Runtime End-users Runtime Unknown Runtime App. Devs Runtime App. Devs Dev. time App. Devs Dev. time End-users Runtime End-users Runtime App. Devs Runtime App. Devs Dev. time End-users Runtime App. Devs Runtime App. Devs Runtime App. Devs Runtime End-users Runtime End-users Runtime App. Devs Dev. time Specified in End-User int. End-User int. Configuration Configuration Configuration Configuration End-User int. End-User int. Source Code Source Code Configuration Configuration Configuration Configuration End-User int. End-User int. Source Code
Level Implicit Types Types Implicit Instances, Implicit Types Instances Instances Instances Types Instances Implicit Types Types Instances Instances Implicit
QoS req. Yes Yes Yes Yes Yes No No No No Yes No No Yes No No No No
Runtime Contingencies Automatic Automatic Runtime Automatic Automatic Automatic None Detection Detection None Automatic None Automatic Detection Detection None Automatic
Resource use PDA+Server PDA+Server Unknown PDA+Mote J2SE PDA+Server PDA PDA J2SE PDA PDA PDA PDA+Server PDA PDA PDA PDA+Server
Deployment Infrastructure Fixed Ad Hoc Unknown Ad Hoc Ad Hoc Fixed Fixed Ad Hoc Ad Hoc Ad Hoc Ad hoc Fixed Ad Hoc Ad hoc Ad Hoc Ad Hoc Ad Hoc
Table .: Categorization of Service Composition Mechanisms
Topology Centralized Centralized Centralized Decentralized Decentralized Centralized Centralized Decentralized Decentralized Decentralized Centralized Centralized Unknown Decentralized Decentralized Centralized Centralized
Evaluation Sce. perf. Example Example Ex., Perf. Example Example Example Example Sce., Usab., Perf. Ex., Perf. Scenario Scenario Scenario, Perf. Performance Ex., Usab. Example Example
C Ո
P P C
Palpable computing is a new perspective on pervasive computing, in which traditional pervasive computing challenges such as invisibility and composition are complemented with visibility and deconstruction []. e concept has been formed based on the observation that when applied in real settings, pervasive computing systems tend to become hard to understand for users. For example, in normal use the system should be invisible and not interfere with the present task. However, when a breakdown occurs the user should be able to inspect the system to determine the reason and, if possible, resolve the situation. Consider the gas price notification application described in section .. Assume that the application is part of the navigation system. When first started, the navigation system queries the driver for his fuel preferences and subsequently uses the information in the selection of gas stations. A problem might occur when the driver installs the navigation system in a new car. Since the navigation system has no knowledge of it being transferred, it will still select gas stations based on the old cars fuel preferences. e driver can have a hard time detecting that the system leads him to gas stations with suboptimal prices, but if he does so it can be even harder for him to determine the reason. If he was able to inspect the system to discover the logic in the application and the current state, it would be much easier for him find the reason behind the malfunction and correct it. Techniques such as self-reconfiguration, error detection, and fault tolerance should also be used, but they will never be perfect and therefore, as a supplement, there has to be a way for the user to take over control of the system. Palpable computing is a product of the PalCom project described in section .. . C e paper Palpability support demonstrated in chapter describes how palpability can be achieved in a rehabilitation scenario by using service composition to compose applications and expose the structure of applications to the user on demand. In the following, we describe the rehabilitation scenario and the associated applications. Following that in section .., we summarize how palpability is achieved and finally, in section .., we describe how the scenario can be realized by using
Chapter . Palpability in Pervasive Computing
the extended script language described in the previous chapter (section ..).
..
e Active Surfaces Scenario
e Active Surfaces [] concept provides support for physical-functional and cognitive rehabilitation in a swimming pool setting. e concept has been developed using participatory design techniques in corporation with therapists and patients. rough analysis of the rehabilitation practice a number of different games have been developed in which children assemble floating tiles into meaningful configurations (see figure .).
Figure .: Tiles Each of the tiles is a resource constrained embedded system that communicates using only a low bandwidth short-range infrared interface on each of its four side. Two tiles can only communicate if they are placed next to each other within a few centimeters. e only output from the system available to the user is a set of light emitting diodes along the edges of the tiles. On the face of each tile is a replaceable plastic cover. ree games have been developed for the tiles. • One where the goal is to ‘catch’ a blinking tile by touching it with another tile. • A scrapple-like game where each tile has a letter on the cover and words should be formed by moving the tiles around • A picture puzzle where each cover is a piece of the puzzle.
.. Contributions
.. Palpability Palpability is achieved in the games by implementing them using the PalCom assembly script language described in the previous chapter and the PalCom service framework []. is enables the therapist to inspect the inner workings of the games in case of break down situations. rough interaction with the assemblies, the therapist can inspect and change the configurations of the tiles. is way, she can adapt the therapeutic activity in the middle of an exercise, and the visibility given by the assemblies helps her to cope with unexpected breakdown situations. For example, in the puzzle game, the difficulty can be varied by changing the type of feedback. If no feedback is given before the correct solution is obtained, the game can be too hard for some children. If, however, feedback is provided each time a piece of the puzzle is placed correctly, the game is easier. e therapist can change the type of feedback by modifying the assembly. is can, e.g., be done by attaching a tile to a computer and modifying the assembly in an interactive way. If this is a task often performed by the therapist, she can create a new assembly that can be used to change the other assemblies.
.. Implementation Using the Extended Script Language e extended PalCom assembly script language, described in the previous chapter, can be used to implement the puzzle game more naturally than the approach used in the paper in chapter . Actually, the Active Surface scenario was one of the conditions prompting the development of the extended script language. In the puzzle script described in chapter (figure .), each tile has its own unique assembly script that describes its part of the whole. While these scripts are very similar, they differ in an important way: the device declaration part of each script is unique. Having almost identical assembly scripts on all the nodes has a set of downsides. First, each newly arriving tile has to be programmed with the script. Secondly, if the script is updated to a new game, all the tiles have to receive their own new script and finally, the way the nodes communicate with each other rely on a basic broadcast mechanism in the PalCom framework and this circumvents the assembly mechanism. As an alternative, the extended assembly script language described in the previous chapter in section .. can be used to implement the puzzle game. By using the wildcard mechanism, all nodes can use the same script. Furthermore, they can communicate with each other by using the assembly script mechanisms without talking directly to the lower layers of the PalCom communication stack. While the extended script language is strong enough to implement the puzzle game, it should be noted that the current decentralized interpretation engine for the assembly scripts has to be optimized to be usable for implementing the game. In the current implementation, when invoking commands on a set of services declared with a wildcard, it is done by making a unicast connection to each of them and then invoking the commands in sequence. is solution will, however, not work on
Chapter . Palpability in Pervasive Computing
the tiles because the bandwidth is too limited. Enabling unicast requires that, at some level in the communication stack, each tile keeps track of which of the other tiles it can reach. Maintaining this information generates too much traffic for the bandwidth limited infrared links. A better approach, that would be more suitable for the puzzle game, would be to create a multicast group (cf. section ..) for each of the declarations containing a wildcard. If multicast is implemented by filtering broadcast messages, no bookkeeping for which nodes are available is necessary.
C Ո
C
roughout this dissertation, we have approached service oriented architecture for pervasive computing from different angles by looking at the architecture of vehicular technology applications, data dissemination models, service composition for pervasive computing, and by investigating palpability in pervasive computing systems. Together with the contributions of the papers in part II, these angles constitute a step towards using service oriented architecture to alleviate the challenges of pervasive computing and in particular vehicular applications. In the following, we summarize the contributions made and present directions for future work. . S C More specifically the contributions can be summarized as follows: • We investigated architecture in vehicular technology applications from three different perspectives. ) Looking at a concrete application, we identified functional and architectural requirements that let to the design of an architecture that was evaluated though a series of prototypes. ) We presented a uniform publish-subscribe communication infrastructure for component based architectures that hides the complexity of low-level network programming and presents a clean and understandable abstraction over communication to the application programmer. ) We made a connection between business aspects and software architecture by presenting a business model for the provision of information about the environment to drivers. • We presented an overview of data dissemination protocols and their evaluation and presented two lightweight and robust zone dissemination protocols based on flooding and data aggregation. • We presented a model and a categorization framework for service composition in pervasive computing that was used to analyze how the characteristics of pervasive computing can be support by service composition. We described how to extend the PalCom assembly script language to support service composition with dynamic membership and presented a decentralized interpretation engine.
Chapter . Conclusion
• We demonstrated how palpability can be supported in a prototype of the Active Surfaces concept by using service composition to open up the system to the user in breakdown situations. .
F W
e contributions made in this dissertation open up for future work in a variety of directions. Since the focus in the dissertation have been relatively broad, a natural direction would be to dig deeper into each of the topics investigated to gain further insights into how service oriented architecture can be used to deal with the challenges of pervasive computing. In each of the papers in part II, we have given directions for future work. In the following section we describe a few of these. A natural extension of the Zone Diffusion protocol described in chapter , would be to let the structure of the environment representation (ER) reflect the spatial relevance decrease (cf. section ..) of the data communicated. is could, e.g., be done by making the cells in the ER larger towards the edges. is would make sure that less relevant data take up less space in the ER and thereby information about a larger area could be contained in the ER. An interesting tool for the extended assembly script language presented in chapter and used (unextended) in chapter would be a graphical user interface for creation of assembly scripts and interaction with running assemblies. e interface should be designed for end-users with limited previous experience with programming and should be used to explore the feasibility of end-user general purpose programming. One way to connect the contributions presented in this dissertation would be to implement a framework supporting service oriented architecture, tailored for vehicular networks. In section .., we motivated the use for such a framework as, among other things, a solution to the bootstrapping and fragmentation problems. In realizing such a framework, there is a set of challenges which we describe in the following. Traditionally, service frameworks rely on unicast communication between nodes, but in vehicular networks, this assumption is unsuitable because the mobility of vehicles makes is necessary to optimize the protocols used to the vehicular environment and exploit application level information when routing messages. Instead, we propose to use the publish-subscribe model for communication. In section .., we proposed a middleware architecture where the publish-subscribe paradigm was used to present a clean abstraction over communication to the developer. While, arguably, there is a long way from a publish-subscribe mechanism to a service framework, service invocation can, at a primitive level, be seen as sending a message from the service consumer to the service provider, and thus the publish-subscribe framework could be used as outset to the realization of a service framework for vehicular applications. To realize some of the applications described in section ., it is necessary to allow for composites with dynamic membership. It should, for example, be possible
.. Future Work
to create a composite where when a certain condition occurs, services will be invoked on all neighboring vehicles. In the road state notification system, this could, e.g., be used to disseminate a warning about a pothole. e script language presented in section .. could be extended to allowing a more detailed specification of sets of nodes. In the current version, at set of nodes is declared by specifying a wildcard expression. While this may be at the expense of usability, it might be necessary to give the language enough expressive power to realize relevant vehicular applications. A natural addition to such a framework would be a suite of tools for evaluating composite services. Part of this suite should be traditional network simulation tools and mobility models. Since what is tested is service composites, models for service use [] would also have to be available.
.. Security and Privacy Two topics of interest that remains largely untouched by this dissertation are security and privacy. In the following, we discuss different issues in relation to providing security and privacy in vehicular networks and provide references to the literature. Security and privacy are important in vehicular applications for a variety of reasons. For a large part of the applications described in section . the consequence of service unavailability is loss of safety (cf. table .), and therefore security is crucial. For example, in a platooning system, a malicious attacker could inject false messages to cause collisions among the vehicles in the platoon. For paid services, it is important that non-paying drivers are not able to benefit from any information intercepted and that the paying driver can assume that the data received originates from the service provider and have not been altered. Furthermore, payment transactions should be possible. With respect to privacy, location information is sensitive and it should not be easy to log information about other vehicles’ location. In infrastructure-based vehicular networks, the security and privacy issues resemble those that can be found in traditional networks. In VANETs, however, traditional solutions to security and privacy issues can often not be used because of the the special characteristics of the environment. For example, in a VANET there is no central authority that can be reached by all nodes. However, until recently [], security and privacy in VANETs have received only little attention in the literature. A starting point for future work in security could be the observation that, for some applications, security can be achieved by only using ad-hoc communication when strictly needed. One example could be a navigation system provider that sells road state notifications to customers. e information could, e.g., be generated by the navigation systems mounted in the vehicles of the customers and disseminated using a VANET. To avoid using the insecure communication channel for sending payment information, the navigation system provider could, e.g., use GPRS for the payment transaction. is requires however, that the customer does not buy information on a notification-by-notification basis, but that some kind of subscription
Chapter . Conclusion
is involved. To avoid that non-paying drivers have access to the information, the information could be encrypted by the navigation system and keys could be updated regularly using the GPRS connection. A service oriented framework for vehicular applications, such as the one mentioned above, should include a security architecture. In the literature, several suggestions have been given to secure communication in VANETs. In [], Parno and Perrig identify challenges for providing security and privacy in VANETs. ey suggest the use of a set of security primitives as building blocks in secure applications. e primitives include authenticated localization of message origin, an anonymization service for providing anonymous identities, and secure aggregation techniques for aggregation of data in the network. In [], Raya and Hubaux provide a detailed threat analysis of VANETs and present a security architecture based on digital signatures. e architecture provides authentication but no confidentiality because the authors argue that this is not necessary for safety applications.
P II
P
C Ո
A I T W S Jeppe Brønsted, Klaus Marius Hansen, Lars Michael Kristensen Abstract e LIWAS Traffic Warning System aims at providing early warning to vehicles about road conditions, such as whether the road is slippery. e LIWAS system is currently being developed and consists of two main parts: sensors for determining the state of the road and a communication infrastructure supporting inter-vehicle communication. is paper presents our results on requirements identification, design, and prototyping of the infrastructure. e infrastructure combines communication via mobile phones with communication based on the principles of ad-hoc networking, and it supports units in being updated during operation. e presented prototypes and associated experimental results demonstrate the main functionalities of the communication infrastructure, and have led to the initial deployment of LIWAS units.
. I Traffic warning and information systems is a promising application area for adhoc networking [] and pervasive computing []. Several research projects are currently concerned with the development of inter- and intra-vehicle communication infrastructures to enable such systems. Examples of this include the Virtual City Protocol [], CarNet [], FleetNet [], INVENT [], and TrafficView []. ese projects cover a broad spectrum ranging from application software to network protocols and data-link layer technologies. e LIfe WArning System (LIWAS) is a traffic warning system being developed in a research collaboration between ISIS Katrinebjerg at University of Aarhus [] and LIWAS Aps []. e LIWAS system is based on sensors that are capable of determining whether the surface of the road is dry or covered with water, snow, or ice. A LIWAS sensor consists of a collection of sensors, and it is the input from these sensors that are collectively used to classify the state of the road. A vehicle equipped with a LIWAS sensor is able to inform the driver about the Published as: Jeppe Brønsted, Klaus Marius Hansen, and Lars Michael Kristensen. An Infrastructure for a Traffic Warning System. In Proceedings for the IEEE International Conference on Pervasive Services, pages –, . Acceptance rate:
Chapter . An Infrastructure for a Traffic Warning System
state of the road being passed. is can help the driver take precautions according to the current road conditions. In addition to this intra-vehicle communication, the vision is to use wireless communication between vehicles to support vehicles equipped with the LIWAS system to inform each other about the state of the road being approached. To support this vision, inter-vehicle communication of roadstate information is required. Stationary LIWAS sensors may also be deployed as part of, e.g., road-signs. e design and implementation of an infrastructure enabling the LIWAS system present several challenges. In early stages there will only be few LIWAS units, i.e., vehicles and road-signs equipped with the LIWAS system. is means that an infrastructure based on ad-hoc networking and wireless communication directly between the LIWAS units will be insufficient. e infrastructure must support a gradual deployment of LIWAS units which suggests that the infrastructure should encompass a back-end network such as GSM or GPRS that can provide acceptable coverage from the very beginning. A centralised architecture may, however, lead to scalability problems in the long-term as the number of LIWAS units increases. We have therefore developed a hybrid infrastructure that combines the use of ad-hoc networking and a back-end infrastructure. Another main challenge is the testing and deployment of software and hardware implementing the infrastructure. A large-scale realistic evaluation of the LIWAS infrastructure prior to deployment would require orchestration of hundreds of vehicles and is therefore not realistic in practice. is means that, e.g., the scalability of the communication protocols cannot be precisely judged until after the deployment of the LIWAS system has commenced. As a consequence, it is of great interest to explore the use of techniques that make it possible to remotely update running software in already deployed LIWAS units. In this paper, we explain how we have used the OSVM platform (formerly known as Resilient []) when prototyping the infrastructure to enable experiments with performing run-time updates of the software in the LIWAS units. e capability of being able to update the LIWAS system when deployed is not only useful for the software implementing the protocols used in the infrastructure, but also for the software implementing the classification algorithm determining the state of the road from the measurements made by the sensors. e contribution of this paper is twofold. e first contribution is to present an infrastructure supporting the LIWAS system. e second contribution is to present the first set of prototypes realising the key aspects of the infrastructure. ese prototypes have led to the initial deployment of the LIWAS system. e infrastructure is presented in the context of the LIWAS system, but since the infrastructure is independent of the concrete measurements made by the sensors, we consider the infrastructure applicable also for other types of traffic warning systems, such as systems informing about queues, delays, and road works. Similarly, our experiences obtained in the course of developing and evaluating the prototypes are of general relevance to practitioners in the field. e technical aspects of the sensor system are out of scope of this paper.
.. Main Requirements
e rest of the paper is structured as follows. Section . gives a detailed account of the requirements identified for the LIWAS infrastructure, and Section . presents the designed architecture. Sections .-. present the three prototypes that have been implemented to demonstrate a proof-of-concept. Section . concludes the paper by summarising the results and discussing future work items. . M R e envisioned functionality of the LIWAS system requires some basic properties of the system architecture. is section discusses the main requirements that have been identified. e requirements have been derived directly from the way that the LIWAS system is supposed to work, and from deployment and maintenance of the LIWAS system.
Measurement collection is the process of getting measurements from the sensors to a computation platform at an appropriate rate. e requirement is to do up to measurements per second which corresponds to one measurement per meter while driving at km/h. Measurement processing is required to transform measurements into road classifications, i.e., determining whether the road is icy or covered with snow or water. Measurements have physical characteristics such as surface reflection, temperature and dew point, and are not directly linked to the road being slippery. e measurements have to be combined into road classifications that must be computed in real-time as measurements are received from the sensors. Classification dissemination deals with sending classifications of road state to other LIWAS units. A central feature of the LIWAS system is the ability to warn drivers of icy conditions and therefore communication between LIWAS units must be supported. Furthermore, such warnings must be received in due time. is is a key requirement to the communication infrastructure. Scalability. e infrastructure is required to scale from a few LIWAS units to thousands of LIWAS units in the total system. In general, the more LIWAS units that are added to the network, the larger the geographical area for which road state information is available. Availability. As a traffic warning system, it is important that the system is continuously available and provide up-to-date information to the users. e probability that a user (driver) misses a warning increases when the downtime of the system increases or up-to-date information is not provided. Availability also refers to the dissemination of classifications even in situations in which the distribution of ve
Chapter . An Infrastructure for a Traffic Warning System
hicles is sparse, i.e., when there are few LIWAS units in operation. Supporting a gradual deployment of LIWAS units is important in achieving availability.
Modifiability. e LIWAS system is a large and complex distributed system in which it is arguably impossible to produce a system that will not need modifications after it has been deployed. Since high availability is important, it is essential to support modifiability, and desirable to support this at runtime, i.e., be able to update the LIWAS units while they are running. e updates must be distributed via the communication infrastructure. .
S A
is section describes the architecture of the LIWAS system that has been designed to support the requirements discussed in Section .. Figure . shows a Unified Modelling Language (UML) deployment diagram for the abstract LIWAS system architecture. is architecture is an instantiation of the more general Ex Hoc infrastructure developed in the LIWAS project []. It consists of three types of nodes. Wireless inter-unit link
:Unit
Backend: Server
:Communication System :Management
:Dissemination
backend-link :Classification
:Communication
:Java VM :DOM WLAN web service
:OSVM
External Service
sensor link Legend: UML dependency Computational Node
:Sensor System
Component
Object
communication link
Figure .: Deployment diagram for the abstract LIWAS system architecture.
Units that may be either stationary or mobile. ese Units contain a Sensor System that senses the environment and a Communication System that handles measurements from the Sensor System. e Classification object is responsible for taking measurements from DOM (Domain Object Model) and compute road classifications (e.g., wet, slippery, dry). e Communication object is responsible for communication with other Units and with the Backend. e DOM is responsible for maintaining a current view of the environment of the vehicle in terms of, e.g., recent sensor measurements and recent classifications. e DOM data is used by both the
.. System Architecture
Classification and Communication objects. OSVM is the platform on which the objects in the Units are implemented.
A backend server that handles Management of Units and Dissemination of classifications and updates via the back-end infrastructure. Depending on whether Units are mobile or stationary, their communication to the backend may use different network technologies. External services that use data from the Backend Server through a web service interface. An External Service may, e.g., be a web server providing road state classifications based on information received from the LIWAS units. e architecture relies on the three kinds of communication links. e sensor link is a short-range link used to send the measurements from the Sensor System to the Communication System. e wireless inter-unit link is a medium-range link used for wireless communication between LIWAS units. e backend-link is longrange link used for communication with the back-end infrastructure. In the following we briefly discuss the system architecture in the context of the main requirements identified in Section ..
Measurement and collection and processing A central component of the Communication System is the OSVM platform []. e OSVM platform consists of a small virtual machine running Smalltalk []. e virtual machine runs in KB, and combined with libraries and system software written in Smalltalk it runs in less than KB. Experiments have shown that the Communication System is able to handle the soft real-time requirements on measurement collection and processing when running on an embedded platform based on ARM and Intel processors. A critical part in the Communication System is the classification algorithm. It is currently implemented using standard linear discrimination and pattern recognition. is means that classification can be done in constant time. A further presentation of the classification algorithm is beyond the scope of this paper. Modifiability e LIWAS system supports modifiability through the use of the OSVM platform and the Management part of the Backend. e OSVM system supports modifiability that makes it possible to change Smalltalk classes in a running and deployed system. Since most of the OSVM platform is written in Smalltalk (including the scheduler and device drivers) it is possible to update most aspects of the system. e ability to do runtime software updates gives rise to a host of possibilities. In [], three basic kinds of updates are described: corrective - malfunctioning code is corrected, perfective - functionality is enhanced, adaptive - the code is adapted to run in a changed environment. Updates of all three types
Chapter . An Infrastructure for a Traffic Warning System
are important in the LIWAS system. We will give examples of perfective updates later.
Scalability e communication from mobile units to the Backend Server does not contain all road state classifications, but is subject to a policy that determines when classifications are to be sent. For the communication between units using the wireless inter-unit link, we distinguish between data dissemination and management distribution. e concept of management distribution covers distribution of data which is not directly linked to the sensors. An example of this is program updates. e data dissemination is time-critical and most frequent and thus most important for achieving scalability. With our current communication protocol, the payload of one message is able to fit within one User Datagram Protocol (UDP) packet. Availability e Sensor System is designed to do minimal processing and thus be highly robust and available. e majority of processing is done in the Communication System, which being built on OSVM is running on a small and stable core. .
P : B W I-U C
e purpose of the first prototype was to experiment with the practical use of WiFi in the form of IEEE .b ad-hoc mode for implementing the wireless inter-unit communication between vehicles, and between vehicles and road-signs. e LIWAS units were represented by laptops running Linux Redhat and each equipped with a D-Link Air DWL- Wireless PCMCIA Card configured to operate in ad-hoc mode. Operating the wireless network card in ad-hoc mode means that direct communication between the network cards is possible without the use of base stations. e first prototype did not involve the OSVM platform since the focus was on data link-layer communication and obtaining some practical experiences concerning the amount of data that can be exchanged between vehicles and road-signs at different speeds. Figure . provides an overview of the physical environment in which the experiments were conducted. e experiments were done on a high-way consisting of two separated lanes A and B. e distance between the two lanes was approximately meters. A stationary LIWAS unit was represented by a laptop on a bridge crossing the highway. e mobile LIWAS units (M and M) were represented by cars with a laptop inside, passing the bridge at different speeds. e communication protocol used in the prototype periodically broadcasted an UDP packet with a payload of bytes. In the experiments ms were used as the period for packet transmission. Since the purpose of the prototype was to investigate the amount of information that can be exchanged between the LIWAS units using .b ad-hoc communication, the specific payload was not of importance and simply contained a sequence number identifying the packet. e LIWAS
.. Prototype : Basic Wireless Inter-Unit Communication
Bridge Lane A
M2
S M1
Lane B
Figure .: Environment for prototype experiments.
units wrote statistics on the packets received to a log file which could then be used to determine the number of packets received by the units and the time the packets were received.
.. Stationary-Mobile Communication e first set of experiments considered the communication between a stationary LIWAS unit (i.e., a road sign) and a mobile LIWAS unit. Figure . show the results of one of the experiments. e figure shows the number packets received by the stationary and mobile unit as a function of time when the mobile unit approaches the bridge at a speed of km/h. e same setup was also investigated when the mobile units approached the road-sign at speeds of km/h and km/h yielding a similar picture as shown in Fig. .. ree experiments were conducted for each vehicle speed. Time corresponds to the time when the first packet was received by one of the units. e figure also depicts the theoretical maximum of received packets given the fixed periodic transmission rate of packet per ms. It can be seen in Fig. . that the mobile unit received a total of approximately packets in seconds. e stationary unit received approximately packets in seconds. e seconds is the time that the mobile unit is within transmission range of the stationary unit (i.e., capable of receiving packets), whereas the seconds is the time that the stationary unit is within transmission range of the mobile unit. Table . summarises the results on the received packets for the three different vehicle speeds ( km/h, km/h, and km/h). e Received columns give the total number of packets received by the Stationary and the Mobile unit, respectively. e figure in parentheses after the number of packets received gives the percentage of received packets compared to the theoretical maximum at packet/ ms. e Time columns give the time interval in seconds where packets were received by the unit. It can be seen that (in general) the number of packets exchanged decreases as the speed increases. is is expected, since the units will be within transmission range of each other for a shorter period of time. ere are, however, exceptions to
Chapter . An Infrastructure for a Traffic Warning System
Mobile unit Stationary unit Maximum
1200
1000
Packets
800
600
400
200
0 0
5000
10000
15000 Time (msecs)
20000
25000
Figure .: Stationary - Mobile Communication at km/h.
Exp
Speed km/h
Stationary unit Received Time (.) . (.) . (.) . (.) . (.) . (.) . (.) . (.) . (.) .
Mobile unit Received Time (.) . (.) . (.) . (.) . (.) . (.) . (.) . (.) . (.) .
Table .: Stationary-mobile communication.
this general pattern. For instance in the third experiment with km/h, only packets were received by the mobile unit which is the lowest number of packets received by the mobile unit in all experiments. e cause of these variations is most likely the presence of other vehicles and objects on the road which affects the propagation of the radio signals, in particular in cases where they obstruct the line-of-sight between the mobile unit and the stationary unit. e difference in the amount of time that packets are received by the two units demonstrates that the communication links are asymmetric.
..
Inter-Vehicle Communication
e second set of experiments investigated was inter-vehicle communication. In these experiments, two cars (mobile unit and ) were approaching each other from opposite directions on the highway (see Fig. .). Figure . shows the total number of packets received by the two LIWAS units at a speed of km/h. It
.. Prototype : Basic Wireless Inter-Unit Communication
500
Mobile unit 1 Mobile unit 2 Maximum
450 400 350
Packets
300 250 200 150 100 50 0 0
1000
2000
3000 Time (msecs)
4000
5000
6000
Figure .: Mobile - Mobile Communication at km/h.
Exp
Speed
Mobile unit Received (.) (.) (.) (.) (.) (.) (.) (.) (.)
Time . . . . . . . . .
Speed
Mobile unit Received (.) (.) (.) (.) (.) (.) (.) (.) (.)
Time . . . . . . . . .
Table .: Mobile-mobile communication.
can be seen that the time in which packets can be exchanged is much smaller than in the previous experiments with stationary-mobile communication. e reason is that the vehicles are approaching each other from opposite directions which means that a speed of km/h for each vehicle corresponds to a relative speed of km/h. e behaviour for speeds of km/h and km/h were similar to what is depicted in Fig. .. Table . summarises the statistics on the received packets at different vehicle speeds. Because of other traffic on the highway, it was not possible for mobile unit to drive at the intended speed in all the experiments. e results in the table show again that in general, the number of packets exchanged decreases when the speed is increased. e worst-case occurred in the third experiment at km/h where mobile unit received only packets and mobile unit received only packets. e development of prototype and the associated experiments demonstrated that .b ad-hoc communication could be used as a basis for communication between vehicles, and between vehicles and road-signs. e number of packets
Chapter . An Infrastructure for a Traffic Warning System
exchanged was more than sufficient to exchange information about the state of road as this requires only a few bytes of information. e experiments showed that it is fair to assume that - packets can be exchanged between vehicles and road-signs when they are within transmission range. Furthermorethe experiments demonstrated that physical phenomena such as other vehicles on the road have a much higher impact on the amount of data exchanged than the speed of the mobile units. In [] the authors experiments with IEEE .b in vehicular environments in different propagation and mobility scenarios. Data are logged using GPS to determine distance between nodes and relative and absolute velocity. It is concluded that the relative and absolute velocities of the nodes affect the throughput. e data supporting this conclusion is however for varying distances. It can therefore, in our oppinion, not be determined that the effect on the throughput is due to velocity or distance. e authors of [] also experiment with .b in vehicular environments, but here the focus is on infrastructure mode and not on ad-hoc mode. General conclusions on propagation of radio signals from moving nodes are made. It is concluded that effects due to shadowing dramatically affects the performance. .
P : T OSVM P A L F
e purpose of the second prototype was to introduce the OSVM platform and implement several of the application level features of LIWAS: classification of measurements, dissemination of classifications, and communication and application of software updates. e source code implementing the second prototype was written in Smalltalk, compiled to bytecode and executed on the OSVM virtual machine. e second prototype was based on the same hardware platform as prototype .
..
e Software Update Protocol
Software updates on the OSVM platform consists of a set of bytecode arrays one for each Smalltalk class to be updated. e total size of an update is generally larger than the Maximum Transfer Unit (MTU) of the WiFi medium and therefore a simple update protocol was designed for transmitting software updates. e update protocol is designed so that it enables one-to-many reliable communication and can be classified as a variant of reliable broadcast. An update of N bytes is sent in k fragments each of consisting of n bytes such that n(k − 1) < N ≤ nk . e fragments are sent in sequence repeatedly so when the sender has sent fragments 1 to k it starts over again. No acknowledgements are included in the protocol. Each packet contains an update identifier, the total size N , payload size, a sequence number, and a fragment of the update (payload). Including N in each packet makes it possible for the receiver to reserve buffer space for the whole update upon reception of the first fragment, and to determine when the complete update has been received. When a receiver has successfully received an update, it applies
.. Prototype : e OSVM Platform and Application Level Features
180
Feasible update size
160
140
Needed packets
120
100
80
60
40
20
0 0
20
40 60 Number of fragments (k)
80
100
Figure .: Relative speed of km/h.
the update. e update can optionally include code that returns an acknowledgement to the sender. e update protocol has the property that if a fragment is lost, the receiver has to wait until it is transmitted again. is retransmitted fragment might again be lost and so on. We would like to investigate how large an update it is feasible to transmit in different scenarios. To get a first realistic measure of these figures we used communication traces from the experiments performed with prototype . In the experiments with prototype , each UDP packet contained a sequence number that made it possible to identify precisely which packets were lost. For each of the traces we have computed how many UDP packets it takes to transmit an update consisting of k fragments. Each UDP packet contains a fragment of bytes and bytes of control information. is makes each UDP packet carry a payload of bytes. Figure . shows the required number of packets for successful transmission of an update as a function of the number of fragments (k ) in the update for one of the traces. It can be seen that the function is discontinuous indicating that for some values of k it was not possible to successfully transmit an update consisting of k fragments. ere are a number of peaks in the graphs. ey correspond to cases where packets with the same sequence number are repeatedly lost. e figure of interest is the largest value of k where the update is successfully received and where it is successfully received for all smaller values of k . is point is indicated by the + in Figure ., and is referred to as the feasible update size. We have computed the corresponding feasible update size for each of the communication traces obtained with prototype assuming that each packet carries a fragment size of bytes. Table . shows the minimum, average, and maximum feasible update size for all communication traces. e results are listed according to the relative speed in km/h between the two LIWAS units - no distinction is made between mobile-mobile and mobile-stationary experiments. A general tendency is that the feasible update size decreases as the relative speed increases.
Chapter . An Infrastructure for a Traffic Warning System
Relative Speed
Minimum bytes , , , , , ,
Average bytes , , , , , ,
Maximum bytes , , , , , ,
Table .: Feasible update sizes in different scenarios.
e extent to which these figures are adequate is of course highly dependent on what needs to be updated. To investigate this issue we designed two updates each representing different types of updates. Both can be classified as perfective updates as they enhance the functionality of the system. e first update was made to demonstrate that is is possible to use updates to diagnose the infrastructure. When executed it measures the amount of free memory and broadcasts the result for a fixed period. e amount of free memory is an indicator of how loaded the unit is. e other update displays a text on the display of the LIWAS unit when executed. is could be used by a stationary unit to notify all passing units about an accident ahead or for commercial purposes. e size of the heap measuring code is bytes and the size of the message displaying code is bytes. Since the results obtained with the traces from prototype show that in all scenarios it was possible to transmit an update of size ,, it can be concluded that the available bandwidth is more than sufficient for representative updates.
..
Classification
Prior to the development of the second prototype an initial version of the Sensor System and a classification algorithm were developed and tested separately. To estimate the load placed on the LIWAS unit by the classification and communication parts of the system architecture in conjunction, the implementation of the classification algorithm was included in prototype . Since the Sensor System was not available for integration in the second prototype, randomly generated measurements were used to emulate the Sensor System in the prototype.
..
Communication
e communication part of the system architecture was implemented in prototype using broadcast of UDP packets and was responsible for sending and receiving classifications and software updates. A set of experiments was conducted to evaluate the prototype. For compara
.. Prototype : Initial Deployment
Mobile unit Stationary unit Maximum
1200
1000
Packets
800
600
400
200
0 0
5000
10000 15000 Time (msecs)
20000
25000
Figure .: Stationary - Mobile at km/h.
bility, the experiments performed with the first prototype were repeated with the second prototype. e LIWAS units were broadcasting and receiving road classifications, each classification in a single UDP packet. As in the experiments with the first prototype, packets were transmitted every ms. Along with this, one of the LIWAS units was continuously transmitting a software update, each fragment in an UDP packet. e other unit listened for the update and applied it. Figure . shows the number of classifications received by a unit as a function of time in milliseconds in one of the experiments. When comparing the results with the results from the experiments performed on prototype (see Figure .), no significant change is observed. e general picture is that the values from the experiments performed on prototype are slightly lower but that can be attributed to the fact that both classifications and software updates were transmitted. e results from the experiments with prototype was confirmed and it can be concluded that using OSVM as the underlying platform for the units of the LIWAS system is feasible. In each experiment the software update was successfully sent, received, and applied. is demonstrates the feasibility of software updates, and confirms the initial off-line experiments with the update protocol. Furthermore, the second prototype demonstrates that the Communication and Classification parts of the system architecture works and can operate jointly with the software update mechanism. . P : I D e purpose of the third prototype was to switch from laptops to a more compact hardware platform suited for being mounted inside vehicles, to integrate the actual sensor system, and to add the backend communication link. Furthermore, the aim was to make an initial deployment of the resulting prototype inside a set of trucks
Chapter . An Infrastructure for a Traffic Warning System
that would be running in continuous operation for several months. e LIWAS unit in the third prototype was based on a Compaq iPAQ running Familiar Linux ... Compared to the laptops used in earlier prototypes, the iPAQ has a size that enables it to be mounted inside a vehicle. Furthermore, since various GPS based navigation systems already exist for the iPAQ platform, the platform is not new to the vehicular environment and accessories such as a mounting kits and power supplies are standard equipment. e iPAQ was connected to the actual sensor system by means of an EIA- connection. e backend communication link was provided by a GSM mobile handset connected to the iPAQ using Bluetooth. e iPAQ used has built-in WiFi communication capabilities constituting the wireless inter-unit link. e software developed for the prototype units was moved unmodified to the Linux/iPAQ platform since the OSVM virtual machine is also available for this architecture. e only exception to this was that instead of randomly generated measurements, the prototype unit was receiving measurements from the actual sensor system. An addition to the prototype software was the implementation of the backend link using SMS messages. SMS is currently the only reliable communication link that provides coverage for most of Europe. e bandwidth is severely limited implying that not all classifications can be sent to the backend server. We chose to send classifications periodically, but the sending of SMSs will be subject to a more subtle policy in future versions. e backend server was implemented using a Windows PC connected to a Nokia GSM Connectivity Terminal and set up to run a Java program receiving SMSs from the LIWAS unit. A graphical user interface was developed to warn the driver of hazardous road conditions and to enable the driver to provide feedback to the system. In situations where the driver disagrees with the road classification provided by the system, it was possible to press a button having the effect that the current measurements, the computed classification, the driver’s classification, and a timestamp was logged to a file on the iPAQ for later evaluation of the classification algorithm. Figure . shows the user interface which is based on a traffic light metaphor where red indicates slippery road conditions. e prototype unit was deployed in the first truck in January and will run in continuous operation for several months. e truck is owned by a truck company that operates routes in northern Scandinavia, an area in which environmental conditions are sufficiently diverse to provide a good testbed for the LIWAS system. Since only one unit is deployed at the time of writing the disseminating of classifications using the wireless inter-unit link is not currently used. However in the near future two copies of the prototype LIWAS unit will be manufactured and installed in trucks operated by the same company. is will enable inter-vehicle classification interchange between the trucks when driving in convoy. In conclusion, the third prototype implements all parts of the system architecture except the external service part and thus provides a proof-of-concept validating the system architecture.
.. Conclusion
Figure .: Platform and user interface for prototype .
. C In this paper we have presented an infrastructure for the LIWAS traffic warning system. We have identified important requirements and proposed a solution. Although presented in the LIWAS context, the infrastructure applies to other traffic information systems as well. e main features of the infrastructure is the combination of different communication technologies enabling communication in dense and sparse networks, and the support for modifiability of the software while the system is in operation. is in turn means that the infrastructure supports gradual deployment. e system architecture on which the infrastructure is based has been validated by the development of three prototypes covering the key aspects of architecture. e development of the prototypes has led to the initial deployment of a first LIWAS unit that will be duplicated in three copies and evaluated by continuous operation in northern Scandinavia over the next months. During the prototyping process a lot of experiences were gathered that applies to other practitioners in the field of ad-hoc networking and embedded systems. ey can roughly be divided into two categories: validation experiences and platform experiences. e prototypes developed validates the basic functionality of the architecture, but has limitations in terms of evaluating the scalability. We are therefore currently investigating the use of simulation and emulation models for further evaluation of the infrastructure. e use of simulation models and emulation makes it possible to investigate scenarios with hundreds of LIWAS units which is not feasible with the prototypes presented in this paper. Simulation and emulation, however, rely on making abstractions, e.g., with respect to physical characteristics of communication and in our view, a combination of prototypes, simulation, and emulation is required to conduct a proper evaluation of the class of systems considered in this paper. Several hardware platforms were considered during the project including lap
Chapter . An Infrastructure for a Traffic Warning System
tops, the Intrinsic CerfCube, and the Compaq iPAQ. In our view, the iPAQ platform is currently the best prototyping platform as it is a compact device, provides a display, and has good I/O capabilities in terms of a serial interface, Bluetooth, and WiFi. e work on the LIWAS system currently continues based on the experiences and continuous feedback obtained from the deployment of the third prototype. Some main areas for future work are the communication protocols used for dissemination of classification and software updates, in particular when to use the backend system and when to use direct wireless communication between the units. For the dissemination of classification one key aspect is how to ensure that the units receive up-to-date information in due time. An important aspect of software updates is management and version control. .
A
We would like to thank Toke Eskildsen and Rolf Ehrenreich orup for their help in developing the LIWAS prototypes and LIWAS ApS for their cooperaton. e work described in this paper has been supported by ISIS Katrinebjerg Software and the Danish Natural Science Research Council.
C Ո
S P E T Z D P V A- N Jeppe Brønsted and Lars Michael Kristensen Abstract Vehicular ad-hoc networks is an emerging research area focussing on communication infrastructures that support vehicles and road-signs in distributing road-state data such as information about hazardous road conditions ahead, approaching emergency vehicles, and traffic delays. Vehicular ad-hoc networks combine the areas of sensor networks (data acquisition) with mobile ad-hoc networks (highly dynamic topology and lack of pre-existing infrastructure). One of the main challenges of vehicular ad-hoc networks is the data dissemination protocols capable of distributing road-state information among vehicles. is paper presents two candidates for dissemination protocols: a zone flooding protocol and a zone diffusion protocol. e two protocols combine ideas from sensor networks and geocasting to ensure that data is aggregated and distributed only in a bounded geographical area. We present a comparative simulation study of the two protocols evaluating their relative performance using conventional metrics (such as network load) as well as application-specific metrics (such as awareness). e simulation study has been conducted using the Network Simulator (NS-) and has highlighted key properties of the two protocols that can be used as a basis for selecting the most appropriate protocol.
. I Ad-hoc wireless communication among vehicles enables a multitude of applications ranging from improved traffic safety to road maintenance and high-speed tolling, and promises to significantly change the transportation sector in near future [, ]. e new applications rely on the acquisition and processing of sensor data Published as: Jeppe Brønsted and Lars Michael Kristensen. Specification and Performance Evaluation of Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks. In Proceedings of the th Annual Simulation Symposium, pages –, Los Alamitos, CA, USA, . IEEE Computer Society. Acceptance rate:
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
and the dissemination of data via infrastructure-less wireless communication. e area of vehicular ad-hoc networks thereby combines the areas of sensor networks and ad-hoc communication. A main challenge of vehicular ad-hoc networks is the protocols for dissemination of sensor data among vehicles. Information about a phenomenon observed by the sensors must reliably reach the vehicles that may be affected by this phenomenon in due time, so that drivers can react without creating dangerous situations. Furthermore, the protocols must be able to handle high vehicle density and mobility and at the same time be robust to sparse network connectivity. Previous work [] has shown that the performance of advanced dissemination protocols [, ] is highly sensitive to the parameters chosen and to the traffic scenarios. ese advanced dissemination protocols typically improve performance by exploiting properties of the environment that may not always be available. e effect is that these protocols have good performance under some conditions, but poor performance under other conditions. One way to avoid this is reduce the assumptions about the environment and use light-weight protocols (both in terms of protocol complexity, parameters, and internal state) which provide reasonable performance in all traffic scenarios. ese light-weight protocols will never reach the high performance of the advanced protocols when these operate under optimal conditions, but will perform reasonably under most conditions arising in practise. Furthermore, light-weight protocols typically use less computational resources and are easier to implement. e work presented in this paper has been developed in the context of the LIWAS research project[]. e LIfe WArning System (LIWAS) is a traffic warning system for informing drivers about hazardous driving conditions such as ice, water, and snow on the road being approached. LIWAS units are embedded systems with sensors capable of measuring a wide range of physical phenomena such as light reflection, air temperature, and dew point. LIWAS units are mounted on vehicles and alongside roads to detect the condition of the road. e sensed data is combined into road classifications and distributed to other LIWAS units to provide information to drivers. It is not only information about where a road is icy that is distributed, but also information about where the road is not icy. A driver can thus be certain about whether the road ahead is safe before initiating an overtaking. e communication infrastructure supporting the LIWAS system can be realized in many ways ranging from a centralized architecture based on, e.g., GSM or GPRS networks combined with Web servers [] to a decentralized architecture based on ad-hoc networking and multi-hop communication between vehicles. e two architectures have their pros and cons. e centralised architecture has an advantage in coverage, but a potential problem with scalability. e decentralized architecture has an advantage in scalability, but may have a potential problem when the density of the vehicles equipped with LIWAS units is low. In this paper we focus on protocols suited for the decentralised architecture. e contribution of this paper is twofold. e first contribution is the specification of two protocols for data dissemination in vehicular ad-hoc networks. A
.. Related Work
Zone Flooding (ZF) protocol and a Zone Diffusion (ZD) protocol. ey are both designed to be light-weight protocols, robust to varying network density and mobility. e ZF protocol is a variant of flooding and constitutes a very simple protocol while the ZD protocol exploits properties of the data to optimize data dissemination by means of aggregation. Both protocols can be used for the LIWAS system, but also for other traffic information systems dealing with information about the road and/or vehicles. e second contribution is a comparative simulation study evaluating the protocols through simulation of various mobility scenarios. e comparison is done in terms of conventional metrics such as network load and through application specific metrics that expose properties relevant to applications using the data dissemination protocols. e simulations have been conducted using the network simulator NS- []. e rest of the paper is structured as follows. Section . provides a brief survey and comparison of related work. Section . contains the specifications of the two zone dissemination protocols. Section . presents the simulation model and defines the performance metrics. Section . presents the evaluation results for the two protocols. Finally, in section . we sum up the conclusions and discuss future work. . R W Several protocols for data dissemination in vehicular ad-hoc networks can be found in the literature. ey can roughly be divided into three categories: unicast, flooding, and diffusion. Traditional ad-hoc network routing protocols [] or position based routing protocols [, ] can be used to establish general unicast communication in a vehicular ad-hoc network. A service discovery mechanism is then required to let nodes know where to get the needed information [, ]. ere is, however, an overhead in maintaining the service discovery mechanism, neighbour lists, and routing tables that introduces latency and diminished network capacity making this method infeasible for most safety critical applications. e other two methods (flooding and diffusion) rely on the observation that the importance of sensed information about a particular location decreases with the distance to that location. Data therefore only needs to be disseminated in the vicinity of its origin. is is the case for most safety applications, but not for e.g. infotainment [] or environmental applications, where all data comes from or is collected at a central location. Flooding can be used to disseminate data in a certain area which can be determined in different ways. e work presented in [] and [] uses hop-count to limit forwarding of packets whereas in [] the area is implicitly defined by an application specific interest rate function. Before a node forwards a received packet it uses the interest rate function to determine whether the amount of interest its neighbours have in the packet is above a certain threshold. Geocasting[] assumes
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
that nodes can determine their geographical location (e.g. using a GPS device[]) and stop forwarding when packets leave a predetermined geographical area. is method is used in our Zone Flooding protocol described in the next section. A general problem with flooding protocols is that they tend to have a lot of redundant transmissions which causes several problems []. is can be remedied by letting the nodes attempt to estimate whether a potential retransmission will be redundant [, ] or by lowering the transmission power []. In the Zone Flooding protocol we limit the amount of redundant transmissions by ensuring that a node transmits a packet at most once. More advanced mechanisms have been left out to keep the protocol light-weight. Another method for dissemination of information in the neighbourhood of a source is to use a technique known as diffusion [, ]. Each node maintains a view of its surroundings and periodically broadcasts that view. Each time a view is received that view is aggregated with the local one. We use this approach in the Zone Diffusion protocol. In [] the authors compare different aggregation algorithms using application specific metrics similar to ours, but do not try to estimate the relationship between network load and protocol performance as we do. In [] the amount of sensed data is small compared to our scenarios making frugal use of network capacity less important. .
Z D P
As pointed out in the previous section both our protocols rely on the observation that the relevance of information about the road at some location decreases with the distance to that location.
..
e Zone Flooding Protocol
e Zone Flooding protocol is a variant of basic flooding with three modifications to limit the dissemination of packets. It can be seen as a special case of floodingbased geocasting [] in the sense that the source is located inside the geocast zone. Traditionally the problem with flooding-based protocols [] is that they congest the network with hordes of packets. To alleviate this problem we use several techniques to limit the forwarding of packets. A hop-count is embedded in every packet and decremented when the packet is forwarded. When the hop-count reaches zero the packet is discarded. is has the effect that the packet only reaches nodes in the part of the network that is within a certain hop-count radius from the originator of the packet. It is, however, possible that nodes near the originator forward a packet multiple times. To avoid that a node forwards a packet more than once, we use sequence lists as in [, ] to detect whether a packet has been received before. Packets should only be forwarded upon the first reception. Each node maintains a sequence number that is incremented every time a new packet is created by the node. e sequence number is embedded in every packet originating from the node. Every node also
.. Zone Dissemination Protocols
maintains a sequence list, mapping other nodes to their last known sequence number. When a packet is received the sequence number for the originator is updated. If the sequence number contained in the packet is the same or lower than the sequence number in the sequence list, the packet has been received before and should thus not be forwarded. If the sequence number in the packet is strictly lower than the one in the sequence list, the packet being received must have been overtaken. If, however, the sequence number in the packet is greater than the sequence number in the sequence list it is known that the packet is being received for the first time and therefore should be forwarded. e amount of memory used by this mechanism can be limited by for each entry in the sequence list noting the time at which the last packet was received. When a packet is received multiple times it always happens inside a short period of time. A copy of a packet can in practise only be delayed shortly because when a packet is received by an intermediate node it is either dropped or forwarded immediately. erefore, the sequence list can be cleaned up periodically by removing the oldest entries. To further limit the dissemination of packets the concept of a flooding zone is introduced. In every packet a flooding zone is embedded specifying a geographic destination area. In the current implementation of the protocol the flooding zone is a rectangle, but other shapes are possible. When a node receives a packet it checks (e.g. using a GPS device) whether its current position is inside the flooding zone and discards the packet if that is not the case. e effect is that packets are only delivered to nodes in a certain geographical area. Figure . illustrates the operation of the Zone Flooding protocol. e white source node broadcasts a packet that is forwarded by other nodes until it reaches a node outside the flooding zone.
i ng od Flo
n Zo
e
Tra
ns
s mi s
ion
g ran
e
Source Node Transmission
Figure .: e Zone Flooding Protocol. When limiting the forwarding of packets by using the flooding zone, the hopcount limitation almost never gets effectuated because packets move out of the
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
flooding zone before they reach the hop-count limit. However, since nodes are constantly moving, it is possible (albeit unlikely) that a packet would be forwarded infinitely inside the zone provided that new nodes keep entering the zone at an appropriate rate. Hop-count is therefore necessary to ensure correctness of the protocol. To summarise, the techniques described above limits the forwarding of packets in three ways: No packets will reach nodes outside a certain hop-count radius from the source, no packets will be forwarded more than once by each node, and no packets will be forwarded by nodes outside the flooding zone. e pseudo code for the Zone Flooding protocol can be found in algorithms .. and .. and consists of two parts: _ and . e primitives used are described in appendix .. _ is called when the system is started and is called every time a packet is received. Algorithm ..: _(bcastInterval) whiletrue classification ← _() pos ← _() zone ← _(pos) seqNumber ← seqNumber + 1 do packet ← _(classification, zone, seqNumber) ( packet ) (bcastInterval)
Algorithm ..: (packet) if packet.hopcount ≤ 0 then return senderSeqNumber ← _(packet.sender) if senderSeqNumber ≤ packet.seqNumber then return pos ← _() if _(packet.zone, pos) then return _(packet.sender) ← packet.seqNumber _(packet) (packet) return
.. Zone Dissemination Protocols
.. e Zone Diffusion Protocol e Zone Diffusion protocol is based on data aggregation which is a commonly used technique in sensor networks [, , ]. Each node maintains an environment representation (ER) representing the surrounding environment. e ER is updated every time data arrives from the sensors. To disseminate data the ER is periodically broadcasted. When an ER is received from another node it is aggregated with the local ER by merging the information in the received ER that intersects with the area covered by the local ER. Contrary to the Zone Flooding protocol, packets are never forwarded. However, data about the local environment is indirectly forwarded to other nodes since nodes periodically broadcasts their ER. e protocol is thus datacentric as opposed to node-centric. e ER is divided into cells of equal size each representing an atomic part of the road. When a node receives information concerning a cell it already has information about, the information is combined according to a data combination policy. One policy could be to make a conservative estimate: if one node thinks the cell is dry and another node classifies it as icy then the cell is to be considered icy. Other policies are also possible. e actual choice of policy is, however, out of the scope of this paper. In the implementation of the protocol we just store in each cell whether the node has received information about that cell at all and so the protocol can accommodate different policies depending on the specific application. Figure . illustrates the operation of the Zone Diffusion protocol. Node A sends it’s ER (depicted over it with a white car in it) to node B. Node B aggregates the received ER with its own and thus learns about icy cells up ahead (marked with “ICY” in bold font and capital letters). e pseudo code for the Zone Diffusion protocol consists of three parts _, _, and given in algorithms .., .., and ... _ and _ is called when the system is started and is called every time a packet is received. _ ensures that the ER is continuously updated with road classifications from the sensor of the vehicle. _ periodically broadcasts the ER and handles incoming ERs from other nodes, compares them with the local one, and combines the intersecting cells.
Algorithm ..: _() whiletrue classification ← _() do c ← _() ER.at(c) ←(ER.at(c), classification)
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
ER of node B
dry
ICY
icy
ER of node A
icy
dry dry
dry
ICY
icy B
icy
A
icy ICY
Local classification Received classification Transmission Node A Node B
Figure .: e Zone Diffusion Protocol.
Algorithm ..: _(bcastInterval) while{true (ER) do (bcastInterval)
Algorithm ..: (packet)
commonCells ← _(ER, packet.ER) for each { c ∈ commonCells ER.at(c) ← (ER.at(c), do packet.ER.at(c)) return
.
S M
To evaluate the protocols simulations have been conducted using the discrete event simulator NS- []. e setup has been chosen so that it resembles a realistic scenario for the LIWAS system - a straight section of a road, meters long and meters wide, with vehicles moving in both directions. An overview of the
.. Simulation Model
road scenario is shown in figure .. Ideally the scenario would just consist of two lanes of vehicles entering the road section at the one end, and leaving it at the other. However in NS- [] it is not possible to add or remove nodes once the simulation has started. e ideal situation is obtained by turning the nodes around and resetting them at both ends of the road section thereby making them behave as new nodes. ree classes of mobility, low velocity, medium velocity, and high velocity, each corresponding to a typical traffic situation, were generated using the FreeWay tool []. For each class the node velocity changes randomly every seconds according to a Gaussian distribution having the effect that overtaking occurs once in a while. e average node velocity and the velocity variance corresponding to the mobility classes are listed in table .. Each node is equipped with an IEEE . radio operating in broadcast mode meaning that there is no channel reservation or acknowledgements. e transmission range is set to meters and the bandwidth is Mbit/s. We use the two-rayground radio propagation model that comes with the NS- simulator. Each simulation was run for seconds of simulation time with , , and nodes. e two protocols were each simulated with broadcast intervals ranging from . second to seconds. For the Zone Flooding protocol the size of the flooding zone is set to by meters, the packet size is set to bytes, and the hop-count is . As mentioned in section .., the hop-count only ensures that packets will not travel infinitely inside the flooding zone. To enable comparison, the environment representation for the Zone Diffusion protocol is set to have the same size as the flooding zone for the Zone Flooding protocol. Each cell in the environment representation is by meters and can hold one of values. e packet size is bytes which is enough to hold information about cells and some additional auxiliary information. Table . provides an overview of the simulation parameters.
.. Performance Metrics e protocols have been evaluated both in terms of general protocol performance metrics and in terms of application specific performance metrics. To estimate the load placed on the network by the protocols we record the amount of packets sent, received, and dropped. ese figures can be measured in any network and thus enables comparison with protocols not related to traffic warning systems. It should be noted that for connection-oriented protocols the limitation of dropped packets is typically handled by a MAC layer protocol. is implies that direct comparison with connection-oriented protocols is not appropriate. Besides the general metrics, the protocols have been evaluated according to traffic warning system specific metrics. One goal of a traffic warning system is to provide information to drivers about the road ahead and the two application specific metrics investigated relate to this goal. First we will intuitively introduce
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
the concepts of Information Distance and Awareness Percentage, and then we will go into further details about how the figures are determined. Information Distance When a node learns something about a phenomenon further up the road for the first time, the Information Distance is the distance from the current position to that phenomenon. Awareness Percentage For a particular location, the Awareness Percentage is the fraction of nodes passing the location that had information about the location before entering it. To determine the Information Distance and the Awareness Percentage the simulation area is divided into by meters sectors. Every sector represents an atomic part of the road; if a sensor somewhere inside the sector classifies the road as being dry, the whole sector counts as being dry. is mimics the fact that if a sensor at some point classifies the road as being dry, there is a high probability that the area around the sensor will be dry as well. Each time a node receives information about a sector that is has no previous information about, the distance to that sector is the Information Distance. Only information from sectors that the node will eventually enter is counted. In figure . information about sector travels from node B to node A - either directly by forwarding of packets in the Zone Flooding protocol or indirectly travelling from one ER to the next in the Zone Diffusion protocol. When node A receives the information, the distance from itself to sector is the Information Distance. It is assumed that the vehicles continuously measures the road implying that if a node knows nothing about a sector immediately before entering it, it will learn something about the sector the instance it enters it, implying that the Information Distance in that situation is . e Information Distance is a measure of what warning distance the driver of the vehicle can expect. Let N be the set of nodes and S be the set of sectors. Because the simulation area only consists of a straight section of a road a node n enters a sector s at most once per simulation (recall that nodes are treated as new nodes when they turn at the end of the road). is allows us to define the set of events ES ⊂ N × S so that if node n enters sector s some time during the simulation S then (n, s) ∈ ES . e point pS (n, s) is the position of node n when it first got information about sector s in S - either receiving it in a packet or measuring it on the road. e function pS is partially defined on the set N × S . For each event (n, s) ∈ ES we define the Information Distance (ID) to be: ID(n, s) = the shortest distance from pS (n, s) to a point in s e Awareness Percentage for a sector is the fraction of Information Distances that are above and is therefore only defined on the set of sectors that at some time during the simulation contains a node. is means that if for a sector s :
.. Performance Evaluation
{n | (n, s) ∈ ES } ̸= ∅, then we define the Awareness Percentage (AP) to be: AP (s) =
|{n | ID(n, s) > 0}| |{n | (n, s) ∈ ES }|
. P E is section presents the performance evaluation of the protocols. e network load, Awareness Percentage, and Information Distance of the protocols obtained from the simulations are analysed and at the end we sum up conclusions concerning the choice of protocol and parameters.
.. Network Load Figure . shows packet statistics for the medium velocity mobility class with nodes. e number of packets sent, received, and dropped is shown as a function of the number of broadcasts per second. For a single packet transmission the number of received packets is the number of nodes in range that receives the packet whereas the number of dropped packets is the number of nodes in range that due to signal interference do not receive the packet. Each number displayed in the graph is a sum over all transmissions in a simulation run. erefore, as can be seen in figure ., the number of received packets is larger than the number of sent packets. Both axes are scaled logarithmically implying that exponential functions are shown as straight lines. e curves for packets sent, received and dropped for the Zone Flooding protocol in the interval . to . broadcasts per second are straight lines and therefore exponential functions. e base of the exponential functions is one and therefore there is a linear relation between the number of broadcasts per second and the number of packets sent, received, and dropped. An explanation of this is that when the number of broadcasts per second is low the probability that separate floodings will interfere is low. If a packet originating from a particular flooding is dropped, it is most likely because it collides with another packet from the same flooding. erefore, when the number of broadcasts per second increases with a constant, the number of packets sent, received, and dropped increases proportionally. When the number of broadcasts per second exceeds . the Zone Flooding protocol changes behaviour. Instead of being linear, the number of packets sent, received, and dropped are approximately constant. is indicates that separate floodings start to interfere. Even though more floodings are initiated the amount of packets sent, received, and dropped remains almost constant. e interference between separate floodings causes packets to be dropped and since a node has to receive a packet before it can forward it, the number of nodes that sends packets originating from a particular flooding decreases. When fewer packets are sent, fewer packets get dropped. As mentioned, the figures remain approximately constant and that means that the average number of receivers per flooding decreases
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
approximately as fast the number of broadcasts per second increases. Hereby, the protocol continues to have reasonable performance in spite of increased network load and thus the effect resembles a crude form of congestion containment. e Zone Diffusion protocol has no forwarding of packets and the number of sent packets therefore only depends on the number of broadcasts per second. At more than broadcasts per second an increased number of dropped packets can be observed indicating that the network has reached its maximum capacity. e number of received packets decreases accordingly as a consequence. With less than . broadcasts per second the number of packets sent, received, and dropped for the Zone Flooding protocol are about a factor larger than the corresponding numbers for the Zone Diffusion protocol. e packet statistics for the other mobility classes are similar although as the node count increases the number of broadcasts per second for which the protocols change behaviour decreases. To summarise, the network load of the Zone Flooding protocol is linear in the number of broadcasts per second until a certain threshold after which it is constant. e network load of the Zone Diffusion protocol is linear for all broadcasts per second and is a factor less than the network load of the Zone Flooding protocol when the number of broadcasts per second is low.
..
Awareness Percentage
As described in section .., the Awareness Percentage is associated with a sector, and the sector for which the Awareness Percentage is considered in the rest of the paper is the one in the centre of the road section. is sector is chosen because flooding zones and ERs centred at this sector are fully contained in the simulation area and thus the boundaries of the scenario have no effect on the Awareness Percentage of this sector. Figure . shows the Awareness Percentage for the two protocols as a function of the number of broadcasts per second in the medium velocity mobility class with nodes. When comparing the protocols’ Awareness Percentage for a given number of broadcasts per second the Zone Flooding protocol outperforms the Zone Diffusion protocol in most cases. As mentioned in the previous section the Zone Flooding protocol sends about a factor more packets than the Zone Diffusion protocol when the network is not congested and therefore much more information can be exchanged. In figure . it can be seen that the difference between the two protocols is not always as significant as in figure .. e Awareness Percentage that the protocols are able to achieve remain fairly constant across most velocity classes and node densities, indicating that the protocols are indeed robust to varying network density and mobility. To investigate the advantage the Zone Flooding protocol has by using more network capacity than the Zone Diffusion protocol, we investigate how the protocols perform in terms of Awareness Percentage versus number of packets sent
.. Performance Evaluation
(instead of number of broadcasts per second). As seen in figure . the Zone Diffusion protocol achieves good performance using significantly fewer packets than the Zone Flooding protocol implying that there is a trade-off between high Awareness Percentage and low network utilisation. Where high Awareness Percentage is the primary goal, the Zone Flooding protocol should be used and when low network utilisation is the goal the Zone Diffusion protocol is to be preferred. ere are a few exceptions to this pattern as can be seen in figure .. In some scenarios the Zone Diffusion protocol performs better for any number of packets sent and thus no trade-off is present. e circumstances for which there is a tradeoff will be further discussed in section ... In summary the Zone Flooding protocol uses more network capacity than the Zone Diffusion protocol and thereby achieves better Awareness Percentage in most cases. Zone Diffusion provides reasonable performance using less network capacity and therefore there is a trade-off between Awareness Percentage and network utilisation.
.. Information Distance As was the case with the Awareness Percentage, the Information Distance is measured at the sector in the centre of the road section. e Information Distance for the centre sector is specified as an average over all Information Distances for that sector together with a confidence interval of . Assuming that the Information Distances for the sector is distributed according to the Gaussian distribution, the confidence interval is the range in which the actual average (as opposed to the average of the point samples) is located with a probability of . In figure . the average Information Distance is shown as a function of the number of broadcasts per second for the low velocity mobility class with nodes. When comparing the average Information Distance obtained for the two protocols at corresponding broadcasts per second two issues are evident. Firstly, with less than one broadcasts per second the Zone Flooding protocol always achieves the largest average information distance. As was the case with Awareness Percentage this can be explained by the difference in sent packets. Secondly, when the number of broadcasts per second is greater than one, the average Information Distance for the Zone Flooding protocol decreases and the Zone Diffusion protocol becomes superior. In section .. we saw that the number of nodes that receive a particular flooding decreases as the network gets congested. Combined with the fact that the average Information Distance decreases as the network gets congested, we conclude that the nodes that receives a particular flooding in a congested network are the nodes located closest to the origin of the flooding. In other words, when the network gets congested the area of dissemination decreases in size. Figure . and . shows the average Information Distance as a function of the number of packets sent. When comparing the two protocols, the behaviour from section .. is repeated. In some cases there is a trade-off between a large information distance and low network utilisation while in most cases the Zone
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
Diffusion protocol outperforms the Zone Flooding protocol. e Information Distance the protocols achieves remains fairly constant across varying mobility classes and node densities, as was the case with the Awareness Percentage,
..
Zone Flooding versus Zone Diffusion
In the previous sections we saw that in some cases there is a trade-off between Awareness Percentage (and Information Distance) and network utilisation. e Zone Flooding protocol achieves better performance than the Zone Diffusion protocol by using more network capacity. is section further explores in which scenarios the trade-off is present and what effect is has on the choice of protocol and parameters. e following analysis considers high Awareness Percentage and low network utilisation as goals. e analysis could easily be extended with the average Information Distance as a goal parameter, but that has been left out due to space limitations. For a given scenario the problem of choosing a protocol and the number of broadcasts per second such that the Awareness Percentage is maximised and the number of sent packets is minimised can be categorised as a multi-objective optimisation problem. Each candidate solution consists of a pair (protocol, broadcasts per second) with an affiliated Awareness Percentage and a number of sent packets. To identify optimal solutions we use the concept of Pareto optimality []. A solution is Pareto optimal if all other solutions that are better according to one goal parameter is worse according to the other. Pareto optimality can be defined as follows. Let s be a solution in the solution space S = {ZF, ZD} × {0.017, ..., 100} and P S(s) be the number of packets sent for s and AP (s) be the Awareness Percentage for s. en a solution s ∈ S is Pareto optimal if ∀t ∈ S : P S(t) < P S(s) ⇒ AP (t) < AP (s) ∧ AP (t) > AP (s) ⇒ P S(t) > P S(s)
For each scenario (node count, traffic speed) the set of solutions have been plotted and the Pareto optimal solutions have been connected to form a Pareto curve. Figure . shows the Pareto curve for the high velocity mobility class with nodes. For each solution on the Pareto curve the corresponding protocol (ZD for Zone Diffusion and ZF for Zone Flooding) and the number of broadcasts per second have been noted. As an example it can be seen in figure . that the Zone Flooding protocol with . broadcasts per second (ZD, .) is a Pareto optimal solution for the high velocity mobility class with nodes. Since AP(ZD, .) = . and PS(ZD, .) = we know that any solution that has more than . Awareness ¹Note that these values specifies the number of broadcasts per second while the values in table . specifies the broadcast interval (seconds/broadcast).
.. Performance Evaluation
Percentage sends more than packets and any solution that sends less than packet has less than . Awareness Percentage. For all mobility classes and nodes densities, it is the case that the Pareto curves are monotone in the sense that the first half of the solutions (the one with the lowest Awareness Percentage) includes the Zone Diffusion protocol and the other half includes the Zone Flooding protocol. is means that if the Awareness Percentage is the primary optimisation factor, then the Zone Flooding protocol should be used whereas if low network load is the prime consideration the Zone Diffusion protocol should be used. However, it is usually not the case that one of the factors is the primary. Usually, there are certain demands for Awareness and limitations on network utilisation. To analyse this question in detail we have determined which is the lowest Awareness requirement for which the Zone Flooding protocol would be best, and similarly, which is the highest packets sent allowance for which the Zone Diffusion protocol should be used. ese figures have been derived from the Pareto curves and are listed in tables . and .. e node density is specified as the average number of nodes per square meter in the scenarios. Since we are not aware of theoretical results [] that allow us to characterise the broadcast capacity of a mobile ad-hoc network, we use packets sent per square meter per second as a measure of network load in table .. As an example we see in table . that for the medium velocity mobility class with a node density of . nodes/m2 the lowest Awareness Percentage requirement that would require us to choose the Zone Flooding protocol is . - if we can settle with anything less the Zone Diffusion protocol should be used. Similarly, we see in table . that if we in the medium velocity mobility class with . nodes/m2 can settle with anything worse than . packets/m2 /sec sent the Zone Flooding protocol should be used. In a few cases (the slow scenarios with . and . nodes/m2 ) all the Pareto optimal solutions include the Zone Diffusion protocol. In these cases the Zone Flooding protocol should never be used. e corresponding entries in the tables are marked with None and All. Table . indicates that the Awareness requirement weakens (excluding the (fast, .) scenario) as the number of nodes increases. When turning to the values in table . we again see that the packet requirement weakens as node count increases. A general conclusion is that the Zone Flooding protocol achieves the best Awareness Percentage in all but a few cases, and the Zone Diffusion protocol sends fewest packets. Furthermore the two goal functions - Awareness Percentage and the number of packets sent - are inversely connected; optimising one lowers the other and vice versa. However, the Pareto graphs and the associated tables above allows us to conclude that if we can settle with an Awareness Percentage of . in worst case the Zone Diffusion protocol should always - no matter what scenario - be used. A similar conclusion cannot be drawn regarding the number of packets sent since, as we saw before, sometimes the Zone Flooding protocol should never be used. If we however, limit ourselves to only consider the medium and high velocity scenarios
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
we see that if we can accept that our protocol uses . packets/m2 /sec in worst case then the Zone Flooding protocol should always be used. .
C F W
In this paper we presented two light-weight protocols for data dissemination in vehicular ad-hoc networks. e protocols only rely on the assumption that the relevance of information about a particular phenomenon decreases with the distance to that phenomenon and can therefore be used in typical vehicular ad-hoc network applications. To be able to evaluate the performance of the protocols we defined general metrics that measure the load placed on the network by the protocols and domain specific metrics that characterise how the data is disseminated. e domain specific metrics have general applicability in the area of data dissemination protocols for vehicular ad-hoc networks. In the evaluation of the protocols, we concluded that the protocols are robust to changes in network density and mobility. e Zone Flooding protocol generally achieves better Awareness Percentage and Information Distance than the Zone Diffusion protocol, but the Zone Diffusion protocol achieves reasonable performance at a much lower network utilisation. In most mobility classes and node densities, there is a trade-off between Awareness Percentage and network utilisation. An analysis of the trade-off revealed that in most applications (where an Awareness Percentage of . is acceptable) the Zone Diffusion protocols should be used. By a crude form of congestion containment, the Zone Flooding protocol adaptively decreases the size of the area in which data is disseminated when the networks gets congested. e Zone Diffusion protocol could be improved by adding congestion control - either by limiting the dissemination area or by decreasing the number of broadcasts per second. As mentioned earlier, the relevance of information decreases with the distance to the source. Some data dissemination protocols [, ] reflect this by letting the information resolution decrease with the distance from the originating node. e Zone Diffusion protocol could be extended with such a mechanism. Based on the evaluation results presented in this paper, the Zone Diffusion protocol will be implemented as part of the general communication infrastructure for the LIWAS system[]. Once implemented, the conclusions of this paper can be validated by real world experiments. .
A P
.. Algorithm Primitives
le ck Tra
ng
th
20
00
m
ran ion iss m m s 0 n 10 Tra
10
ge
m
Figure .: e simulation scenario.
Class Low Medium High
Average velocity m/s(km/h) m/s(km/h) m/s(km/h)
Variance
Table .: Mobility classes.
General parameters MAC protocol IEEE . Propagation model Two ray ground Transmission range m Simulation duration secs Broadcast interval [. .. ] secs Node count , ,
Zone Flooding parameters Flooding zone size m × m Packet size bytes Hop-count Zone Diffusion parameters ER size m × m Packet size bytes Cell size × m
Table .: Simulation parameters.
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
B Se
n atio orm Inf
Se
r cto
ta dis
r cto
nce
Se
r cto
3
2
Node A
A cto Se
4
Node B
r1
Information
Figure .: e Information Distance metric.
1e+008
1e+007
Packets
1e+006
100000
10000
Zone Diffusion- Sent Zone Diffusion - Received Zone Diffusion - Dropped Zone Flooding - Sent Zone Flooding - Received Zone Flooding - Dropped
1000
100 0.01
0.1
1 Broadcasts per second
10
Figure .: Medium velocity, nodes.
100
.. Algorithm Primitives
100
Awareness Percentage
95
90
85
80
75 Zone Diffusion Zone Flooding 70 0.01
0.1
1 Broadcasts per second
10
Figure .: Medium velocity, nodes.
100
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
100
95
Awareness Percentage
90
85
80
75
70
65
60 Zone Diffusion Zone Flooding 55 0.01
0.1
1 Broadcasts per second
10
Figure .: Low velocity, nodes.
100
.. Algorithm Primitives
100
90
Awareness Percentage
80
70
60
50
40 Zone Diffusion Zone Flooding 30 100
1000
10000 100000 Packets Sent
1e+006
1e+007
Figure .: High velocity, nodes.
100
Awareness Percentage
95
90
85
80
Zone Diffusion Zone Flooding 75 100
1000
10000 100000 Packets Sent
1e+006
Figure .: Low velocity, nodes.
1e+007
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
750 700 650
Information Distance
600 550 500 450 400 350 300 Zone Diffusion Zone Flooding 250 0.01
0.1
1 Broadcasts per second
10
Figure .: Low velocity, nodes.
100
.. Algorithm Primitives
750 700 650
Information Distance
600 550 500 450 400 350 300 Zone Diffusion Zone Flooding 250 100
1000
10000 100000 Packets Sent
1e+006
1e+007
Figure .: Low velocity, nodes.
900
800
Information Distance
700
600
500
400
300
200 Zone Diffusion Zone Flooding 100 100
1000
10000 100000 Packets Sent
1e+006
Figure .: High velocity, nodes.
1e+007
Chapter . Two Zone Dissemination Protocols for Vehicular Ad-hoc Networks
1e+007 Pareto curve Non pareto optimal solutions
Packets Sent
1e+006
(ZF 3.12)(ZF 1.78)
100000
(ZD 0.31)
10000
(ZD 0.17) (ZD 0.1) (ZD 0.05) (ZD 0.03)
1000 (ZD 0.01)
100 30
40
50
60 70 80 Awareness Percentage
90
100
Figure .: Pareto optimal solutions. High velocity, nodes.
Node density/Mobility . . .
Low None None .
Medium . . .
High . . .
Table .: Lowest Awareness Percentage requirement to choose Zone Flooding.
Node density/Mobility . . .
Low All All .
Medium . . .
High . . .
Table .: Maximum packets sent allowance requiring Zone Diffusion to be chosen.
.. Algorithm Primitives
Primitive Description Broadcasts the argument _ Returns a collection of cells that exists in both environment representations _ Given a packet it decrements the hop-count of the packet _ Returns the current cell _ Returns a classification of the road _ Returns the current position Returns true if the given position is outside the given zone _ _ Constructs a new packet containing the arguments. _ Given a position it returns a zone having the position at its centre e given classifications are combined and return according to the combination policy _ Given a node identity, it returns the stored sequence number for that node. If no sequence number is stored, infinity is returned Waits for a given interval packet A data structure for a Zone Flooding packet containing fields: hopcount (an integer) seqNumber (an integer) classification (an integer) zone (a zone represented by two corners) ER A data structure for an ER. Maps cells to classifications (ER.at(pos))
C Ո
A U P-S I C W M E Jeppe Brønsted, Klaus Marius Hansen, Rolf orup Abstract In near future the transportation sector will be communication enabled. Devices in vehicles will be able to communicate and thus make a new range of services possible. However, heterogeneous communication capabilities and vehicle mobility complicates the art of designing and implementing these new systems and therefore it is important to have communication middleware that hides the complexity of low level network programming and presents a clean and understandable abstraction over communication to the application programmer. It has previously been shown that the publish-subscribe messaging paradigm provides a good communication abstraction for wireless networks of mobile nodes. In this paper we present PSI, a uniform publish-subscribe based infrastructure, for communication in wireless mobile environments. In PSI the application is divided into software components that each handles a well defined part of the functionality and communicate with other components using the publish-subscribe paradigm. From a components perspective it makes no difference where the receivers of a message are located - in the same process, in another process on the same node, or in a process on a remote node. All communication is handled uniformly. By showing how the infrastructure is used in a concrete instance we argue that it meets the requirements for middleware stated above and provides a good programming model for distributed systems in mobile environments.
. I In distributed systems programming where involved parties communicate in heterogeneous ways a common problem is how to separate communication logic from Published as: Jeppe Brønsted, Klaus Marius Hansen, and Rolf orup. A Uniform Publish-Subscribe Infrastructure for Communication in Wireless Mobile Environments. In th International Conference on ITS Telecommunications Proceedings, pages –, June . Acceptance rate: A previous version was published as a workshop paper: Jeppe Brønsted, Klaus Marius Hansen, and Rolf orup. A Uniform Publish-Subscribe Infrastructure for Communication in Wireless Mobile Environments. In Proceedings of the rd MiNEMA Workshop, February
Chapter . A Uniform Publish-Subscribe Infrastructure
application logic. ere is a need for middleware that handles the communication part of the system in a way that lets the programmer focus on developing the application. When communication in distributed systems is established by wireless multi-hop ad-hoc networking, connections are often unreliable and not well suited for connection-oriented communication []. Systems are better supported by message-oriented communication. e exchange of messages can be seen as a common denominator for all communication media and is therefore a natural candidate for a communication atom from which higher level abstractions can be developed. To exchange messages it has previously been shown that publish-subscribe is a feasible and well-suited communication paradigm for mobile environments [, , ] providing decoupling in time, space, and flow []. In this paper we introduce the PSI publish-subscribe infrastructure for communication in mobile environments. PSI supports a model for distributed systems programming where the functionality is divided into independent software components that communicate using the publish-subscribe messaging paradigm not only for inter node communication but also for communication internally on the nodes. In fact we discourage letting components communicate directly without using messages. Messages are distributed using buses. Multiple buses can coexist in the system delivering messages in different scopes. Buses are linked by special Gateway components that are configured to relay messages from bus to bus. Using the same communication abstraction internally on the nodes and externally between the nodes provides a uniform approach to communication in wireless mobile environments. We demonstrate the use of PSI in a distributed system consisting of mobile nodes and show how PSI can be used not only to structure the system in a uniform way but also how to achieve high-level multi-hop communication between nodes. e work presented in this paper has been developed in the context of the LIWAS research project[]. e LIfe WArning System (LIWAS) is a traffic warning system for informing drivers about hazardous driving conditions such as ice, water, and snow on the road being approached. e operation of the LIWAS system can be seen in figure .. LIWAS units are embedded systems with sensors capable of measuring a wide range of physical phenomena such as light reflection, air temperature, and dew point. e units are mounted on cars and alongside roads to detect the condition of the road. e sensed data is collected from the sensor mounted on vehicle A using a serial connection and combined into a classification of the state of the road and presented to the driver on a PDA. From the PDA the classification is distributed to other drivers and to road authorities - using ., GSM, or similar wireless communication technology - to improve traffic safety and optimize road maintenance. It is not only information about where a road is icy that is distributed, but also information about where the road is not icy. A driver can thus be certain about whether the road ahead is safe e.g. before initiating an overtaking. Communication capabilities may vary from unit to unit depending on what hardware is present. e rest of the paper is structured as follows. e section following this presents
.. Related Work
RS-232
A
802.11 GSM
Figure .: LIWAS operation
related work. In section . we describe PSI and its elements. Section . demonstrates the use of PSI in the LIWAS system and in section . we discus the properties of PSI and outline future work. . R W Using publish-subscribe for universal inter-process communication was introduced in []. In each process a IPC daemon handles publications and subscriptions. e IPC daemon coordinates with other IPC daemons so that they agree on subscriptions and publications which makes the system sensitive to node and communication link failures. In PSI there is no coordination among components about subscriptions and publications. ese are handled by the buses which, depending on their implementation, delivers messages in different scopes and with different levels of service. Furthermore in [] the communicating entities are processes as opposed to components in PSI - limiting the flexibility in how implementation can be divided into components. In [] the concept of a bus to handle distribution of events was introduced. Ethernet broadcast is used to broadcast events on the local area network and information routers, corresponding to Gateways, relay events from LAN to LAN. e design goal of the information routers is to create the illusion of a single, large bus. e
Chapter . A Uniform Publish-Subscribe Infrastructure
information routers determine, based on information about subscriptions, when to relay events. In a wireless settings we cannot assume that the Gateways are able to determine this. Our approach is instead to explicitly let the Gateways know (by publishing events) which events should be relayed and thereby also gain more flexibility in where events should go. In [] the bus concept introduced in [] was extended to event channels providing different levels of service. Each event is tagged with a list of attributes containing the functional and quality requirements the event should be delivered according to. While this provides fine grained control over quality of service, the mechanism is possibly too heavy to be used for intra process communication. While we use message-oriented communication between components some systems use message-oriented communication at an even lower level. In TinyOS[] the notion of components resemble that of traditional objects and all communication between components is message oriented. At compile time a component graph specifies between which components messages can flow. is implies that the communication structure is static and thus cannot be modified at runtime. [] also uses message-oriented communication at the object level. A virtual machine makes sure that systems can be modified at runtime. In both [] and [] events are not only used for communication, but also for iteration. e threading model is based on the assumption that objects will only perform quick tasks and then immediately return control to the scheduler enabling fast context switching. An object simulates loops by sending messages to itself after which the control is immediately handed over to the scheduler. e scheduler will then let other threads run and in turn return control to the object when the time has come to process the message. While this solution is certainly an alternative to ours, the programming model forces the programmer to give attention to low level threading issues such as e.g. how much code can be executed before control should be handed over to scheduler. is approach is well-suited for very resource-limited devices, i.e. bit micro controllers with a few kilobytes of RAM, but for PDA-class systems it is our opinion that the programmers attention should be spent on higher level issues. .
PSI - P-S I
On an abstract level PSI consists of components, events, buses, and gateways, that combined provide uniform message-oriented communication. e intent of the infrastructure is to support the development and deployment of mobile, wireless systems. In the infrastructure, runtime components are the communicating entities that exchange messages in the form of events. Events are exchanged through buses according to the publish-subscribe messaging paradigm[]. To send an event, a component publishes it on a bus from which other components can receive it, provided they have notified the bus of their interest in the event by subscribing to it. To make events travel from one bus to other buses, special components called gateways
.. PSI - a Publish-Subscribe Infrastructure
link two buses by relaying events in a controlled manner. An example of a gateway could be one linking local host communication with a local area network in order for multiple hosts to communicate using publish/subscribe. An example deployment diagram of the infrastructure can be seen in figure .. Each element of the figure will be described in detail shortly.
Host Component
Component
Gateway
Bus
Bus
Figure .: Infrastructure deployment diagram As can be seen in figure . the mechanism for communication internally on nodes and externally between nodes is the same. Seen from a components perspective it is transparent whether communicating partners are on the same node or on other nodes. Besides providing a simple and elegant conceptual model of communication it decouples the communication technology from the functionality that uses it which has several benefits: Any information an internal component produces can be made available to external components and vice versa - without modifying the component originating the information. Furthermore, it can be remotely configured which events should leave a node. An example of this will be given in section ... Traditionally, when debugging a distributed system, one approach is to monitor communication between nodes. If the system uses a heterogeneous set of communication protocols and technologies this can be difficult. Communication interception and analysis tools has to be developed for each protocol and technology. In our infrastructure all communication is done by buses and therefore analysis can be done easily. Only one event sniffer per bus has to be implemented to see what information is exchanged. e system can be dynamically configured to adapt to varying communication capabilities. A component could monitor the state of network interfaces and choose the one that is best for a particular purpose. When a WiFi connection to the Internet is available, it is usually preferable to a slow and expensive GPRS connection. When the WiFi connection at a later time becomes unavailable the GPRS connection should be used again.
Chapter . A Uniform Publish-Subscribe Infrastructure
A drawback of using the same method of communication internally on nodes and externally between nodes is that there is a performance drawback when all communicating parties are located on the same node in comparison with ordinary procedure calls. However, we state that the benefits from the increased flexibility outweigh the penalties induced by the performance overhead. e infrastructure is implemented on top of the .NET Framework[] using IP for communication and can run on PDAs as well as PCs. A Java version of the system is under development.
..
Components
We define a component as unit of software that is responsible for a well defined part of the intended system functionality and that has well-defined dependencies only []. Separating the functionality into distinct components has many wellproven benefits among which one of the most important is separation of concerns. In our component model, each component is defined in a .NET assembly and can be loaded and run dynamically at runtime. Much like the JAR-based component model of OSGi for Java [], a special activator class in the assembly is responsible for initializing the component. e activator receives a handle to the communication bus and all further communication is done through this bus. A component may run in a separate thread, but does not need to. Components operate independently in the sense that if one component fails, other components will not fail directly as a consequence. is means that intercomponent communication should be designed so that, e.g., if some component relies on a GPS component that fails, it should not itself fail, but rather stop functioning until the GPS component recovers or another component providing similar functionality is loaded, and then start functioning again.
..
Events
Traditionally publish-subscribe systems can be divided into topic-based and contentbased systems. e difference lies in the flexibility in describing what kinds of events a component can subscribe to. In content based systems the component specifies an event predicate that defines which events the component subscribes to. e predicate can be of almost any form. In topic-based systems, which to a large extent can be seen as a specialized version of the content-based, each event is sent to a (hierarchical) topic which components may subscribe to. e component will receive all events that are sent to the topics it subscribes to. Our system is topic-based for several reasons. Most importantly, better performance of the bus can be achieved in a topic-based system because the bus only needs to interpret the topic of an event to determine who should receive it. In contentbased systems, the bus has to be able to make a semantic interpretation of the whole event before it can determine the appropriate subscribers to send the event to. An
.. PSI - a Publish-Subscribe Infrastructure
other reason for using topic-based publish/subscribe is that new data formats may be introduced without altering the bus. is is harder to do in a content-based system because along with the new format, the interpretation must be specified. To be able to flexibly categorize events, each topic consists of a sequence of subtopics. e subtopics are organized in a tree so that each node corresponds to a topic. When a component subscribes to a node, t, in the tree, it will receive all events that have a topic corresponding to a node in the subtree rooted at t. In figure . a subset of the topics in the LIWAS system is shown. A component subscribing to Measurement.RoadSensor would receive all events published with the topics Measurement.RoadSensor, Measurement.RoadSensor.Simulated, and Measurement.RoadSensor.v. Each subtopic is identified by a byte which allows a compact representation of the event and allows fast interpretation of the topic.
Measurement
RoadSensor Simulated
Classification
GPS
Dissemination
Positioned
EnvRep
V1
Figure .: Topic hierarchy
.. Buses Each time an event is published on a bus, the bus is responsible for delivering the event to the nodes or components that subscribe to it on that bus. Our infrastructure does not mandate any specific form of communication technology for buses, but in the LIWAS system we use IP-based communication to deliver events. IP communication is used in LIWAS for two reasons. Firstly, almost any programming API and platform supports IP communication and thus the infrastructure can effortlessly be integrated in most systems. is means e.g. that a .NET component can subscribe to events published by a Java component and vice versa. Secondly, when one process is interested in receiving some but not all events from a bus, the operating system can be used to filter out the uninteresting events in a simple yet powerful manner. is will be described later. When a bus is created it is specified to which IP address events should be sent and at which IP address events will arrive. When a bus is used for internal communication between components on a single node, the bus will send events to the localhost multicast address ... and listen for events at localhost .... If more than one receiver should be able to receive an event, the send address must be a multicast address. e operation of the bus can be seen if figure . and .. To be able to publish events of a specific topic, a component first has to Advertise
Chapter . A Uniform Publish-Subscribe Infrastructure
a Component
a Bus Advertise(topic)
new
a Publisher new
a Socket
Publish(event) UdpSend(datagram)
Figure .: Publish
the bus, i.e., notify that it wishes to publish events of a certain topic. Enforcing this makes it possible for the bus to determine who publishes what. e bus in turn returns a Publisher -object that can be used to publish events. Each time the component publishes an event using the Publisher, the Publisher will wrap the event in a UDP datagram and send it to a predefined port number depending on the topic. In the current implementation this port number is a constant offset plus the identifier of the first subtopic. is means that if e.g. a component is interested in events of the topic Measurement it only has to listen to the port associated with Measurement. All other events will be filtered out by the operating system (since they will be sent to other ports). To share sockets, only one Publisher is created for each port number used, implying that the next time a component advertises the same topic no Publisher will be created. Instead the already existing Publisher will be returned. Figure . describes what happens when a component subscribes to a topic.
a Component
a Bus Subscribe(topic,this) new(c) a Listener
new
Receive
loop
Handle(event)
Figure .: Subscribe
a Socket
.. PSI - a Publish-Subscribe Infrastructure
When a component subscribes to a topic, it specifies a component to be notified when an event arrives (itself in the figure). e bus creates a Listener associated with the component (c in the figure) that in turn creates a socket for receiving UDP datagrams on the port number that corresponds to the topic. e Listener waits for incoming datagrams in a new thread. As was the case when publishing, only one Listener is created for each port number used. Each time a datagram arrives, the Listener notifies the components associated with it. As mentioned previously, the bus can be used for communication both internally on a node and with other nodes. e only difference is the IP addresses specified for receiving and sending events. As an example, an . WiFi radio in ad-hoc mode could be used to publish events to other nodes in the vicinity. How this can be used to establish multi-hop inter node communication will be shown in section .. Traditionally in publish-subscribe systems the bus guarantees that published events will reach all subscribers. Clearly we cannot make such a guarantee when communicating wirelessly. However, in the case where all communication is done inside a node, the operating system will provide a high guarantee that events are delivered.
.. Gateways As can be seen in figure ., gateways are a special kind of component with two buses associated and that have the responsibility of relaying events published on one bus to the other bus and vice versa. e operation of the gateway is controlled by publishing events containing gateway commands specifying which events should be relayed. A command consists of a topic and whether the relaying should go from one bus to the other, or the other way around. An example use of gateways could be the following: We wish to log the location of a set of mobile nodes on a central server. On each node is a GPS component that publishes events containing the location of the node. e locations should be sent by a GPRS connection to the server and logged. A deployment diagram of the example is shown in figure.. To control the communication with the server, a gateway component is created on each node. e gateway is attached to the internal bus and a bus is created that sends events to the IP address of the server and receives events at the IP address of the GPRS interface. Similarly on the server side, a gateway is created that listens for events on the IP address of the server’s Ethernet network interface card. If the IP addresses of the node’s GPRS interfaces are on the same subnet, the subnet multicast address can be used for publishing events - otherwise a multicast service should be used. Another alternative is only to use one way communication - from the nodes to the server. In the example, the gateways of mobile nodes can be configured either locally or from the server by publishing the event: {Measurement.GPS, internal-to-GPRS} with the topic Gateway.GPRS. If the gateways are configured from the server, the
Chapter . A Uniform Publish-Subscribe Infrastructure
Node
Server GPS
Gateway
Logger
Bus
Gateway
Bus
GPRS
Ethernet
Bus
Figure .: Gateway example
logging of locations in the example is completely transparent seen from the mobile nodes (excluding their gateways). Gateways can also be used to enable wireless ad-hoc communication between nodes as we will see in the next section. To use communication technologies that do not use IP (e.g., SMS) a specialized version of the gateways can be implemented. PSI poses no constraints on how buses and gateways are connected and therefore care must be taken when configuring the gateways to avoid cycling events. .
PSI LIWAS S
In this section we exemplify the use of PSI in the LIWAS system. As mentioned in section . the LIWAS system consists of nodes equipped with sensors that determine the state of the road. e information is communicated to other nodes to warn drivers about hazardous driving conditions. In figure . a deployment view of a LIWAS node is shown. It consists of a PDA, a road sensor and a GPS [] unit. e PDA is connected to the road sensor by a serial RS- link and to the GPS unit via a Bluetooth [] link, and the PDA communicates with other LIWAS nodes via a .b connection in adhoc mode. On the PDA a set of components handles various parts of the system. As the system is implemented using PSI all inter component communication goes through a central bus, but to avoid cluttering the bus has been left out in the figure . e arrows between the components show dependency relations among the components. e event-hierarchy used is the one shown in figure .. e functionality of each of the components is described below. For each component it is described which event topics they publish and subscribe to.
.. PSI in the LIWAS System
RoadSensor e RoadSensor receives sensor readings from the road-sensor and publishes events with the topic Measurement.RoadSensor on the bus. e events contain values for e.g. air temperature, humidity, and dew point.
GPSSensor e GPSSensor receives location strings from the GPS unit and publishes Measurement.GPS events.
Classifier e Classifier is responsible for transforming measurements which are physical in nature into classifications, such as dry, wet, icy, that are semantic interpretations of the measurements. It is currently implemented using standard linear discrimination analysis and pattern recognition. e classifications are published in events with the topic Classification. e Classifier subscribes to Measurement.RoadSensor and Measurement.GPS.
WiFi Gateway e WiFi Gateway component is a gateway as described in section ... It links the internal bus with the .b device in ad-hoc mode so that events can be relayed from the internal bus to other nodes in range by broadcasting them on the
LIWAS Node PDA UserInterface
Dissemination
Classifier
RoadSensor
GPSSensor
RS 232
Bluetooth
Sensor System
GPS
WiFi Gateway
Figure .: LIWAS deployment
802.11b
Chapter . A Uniform Publish-Subscribe Infrastructure
WiFi interface, and events received on the WiFi interface can be relayed on the internal bus.
Dissemination e Dissemination component handles the distribution of road classifications to other nodes by use of the Zone Diffusion protocol[] which can be described as follows. e Dissemination component maintains in memory a environment representation representing the surroundings of the node. e component subscribes to Classification and each time a classification is received the environment representation is updated. e environment representation is periodically published with the topic Dissemination.EnvRep. e WiFi Gateway is configured to relay events with the topic Dissemination.EnvRep both from the internal bus to the WiFi interface and vice versa. e Dissemination component also subscribes to Dissemination.EnvRep and each time an event is received, the received environment representation is aggregated with the local one. Every time new information is learned in the aggregation process a corresponding classification is published using with topic Classification.Positioned. e Zone Diffusion protocol differs from traditional multi-hop ad-hoc routing protocols in that no messages are sent over more than one hop explicitly. Instead, classifications travel from environment representation to environment representation and can thus reach nodes many hops away.
UserInterface e UserInterface presents the LIWAS system to the user by showing classifications on a map. e UserInterface subscribes to Classification and therefore receives all classifications published by the Classifier and Dissemination. A prototype of the system has been implemented and is currently deployed at an airport near Aarhus, Denmark. e deployment includes only one node and therefore the communication parts of the system have been replaced by logging facilities. .
D
Besides providing a clean an understandable abstraction over communication to the application programmer PSI provides support for a set of architectural qualities[] that are important to a wide range of applications namely availability, modifiability and testability. In the following we list the qualities along with descriptions of how they are supported. High availability is supported by having a loose coupling between components. If one component fails other components will not automatically fail as a consequence. An example could be the UserInterface component from figure .. Since the UserInterface receives classifications from both the Classifier and the Dissemination component it will continue to be available if Classifier or Dissemination
.. Discussion
fails. Another feature providing support for high availability is the loading of components at runtime. is makes it e.g. possible to add a new dissemination protocol at runtime without shutting down the system. Another benefit of having a loose coupling between components is that changes to the system will typically only include a few components thus supporting high modifiability. e incorporation of a new type of communication link into the system e.g. GPRS would only require a gateway component to be implemented and configured to relay the appropriate events. We plan to further support high availability and modifiability by implementing a component that allows other components to be downloaded from a remote node. is would ease the process of updating software on already deployed nodes. A major problem in programming distributed systems consisting of wirelessly connected mobile nodes is to test protocols and collective behavior without orchestrating hundreds of nodes. Testability is supported in PSI by making it possible to replace components with simulated ones and having explicit control over inter node communication. It is future work to make a simulation tool that emulates GPS components and WiFi gateways according to a simulation scenario. In this paper we demonstrated how PSI can be used to structure a distributed system consisting of wirelessly connected mobile nodes. We saw how inter component communication is easily facilitated by using the bus and how multi-hop communication can be implemented using gateways. It is clear that the benefits of PSI comes at a price, but, other than just observing that a relatively complex system can be implemented on top of it to run on resources constrained devices such as e.g. PDAs, it is future work to accurately estimate the performance penalty imposed by the infrastructure. A e authors would like to thank Toke Eskildsen for implementing large parts of the system, Lars Kristensen for valuable input on the infrastructure, LIWAS ApS for their corporation and the MiNEMA network for valuable feedback.
¹http://www.minema.di.fc.ul.pt/
C Ո
P Jeppe Brønsted, Erik Grönvall and David Fors Abstract In ubiquitous computing, as more and more devices are embedded into the environment, there is a risk that the user loses the understanding of the system. In normal use this is not always a problem, but when breakdowns occur it is crucial that the user understands the system to be able to handle the situation. e concept of palpable computing, introduced by the PalCom project, denotes systems which support such understandability. In PalCom, a set of prototype scenarios provide input for an open software architecture and a conceptual framework for palpable computing. One of these prototype scenarios is based on the Active Surfaces concept in which therapists rehabilitate physically and mentally impaired children by means of an activity that stimulates the children both physically and cognitively. In this paper we demonstrate how palpability can be supported in a prototype of the Active Surfaces. Services on the tiles have been developed using the PalCom service framework that allows them to be combined into PalCom assemblies. e support for palpability is shown by examples of use scenarios from the work of the therapist who can inspect and alter the runtime state of the tiles to change their configuration and cope with breakdown situations. e prototype implementation runs on a standard PC simulating the network layer and a first reference implementation has been made on the target embedded platform.
. I Palpable computing is a new perspective on ubiquitous computing, in which traditional ubiquitous computing challenges such as invisibility and composition are complemented with visibility and deconstruction. e concept has been formed based on the observation that when applied in real settings, ubiquitous computing systems tend to become hard to understand for users. Mark Weiser painted a vision of systems being ‘physically invisible’ and that these systems also mentally (as Published as: Jeppe Brønsted, Erik Grönvall, and David Fors. Palpability Support Demonstrated. In Proceedings of Embedded and Ubiquitous Computing, volume of LNCS, pages –, Taipei, Taiwan, December . Springer. Acceptance rate:
Chapter . Palpability support demonstrated
maybe physically) could disappear through use. Dr. Weiser describes the concept well as follows; “Whenever people learn something sufficiently well they cease to be aware of it.” and “e most profound technologies are those that disappear” []. is implies not only that as we learn to master a technology, we move the use (or perception) of it from a foreground to a background cue [], but also that a technology that has the capacity to allow the user to interact with or through it as a background process is a more thoughtful, intense or reflective technology. As part of the ubiquitous conceptual framework and closely related to the work regarding foreground and background cues is the notion of ‘calm technology’ []. Calm technology as described by Weiser and Brown regards how technology can move from the centre of our attention out to the periphery, and between those two states as required by the situation at hand. e vision of calm technology is that technology should not overload us with information or require an ongoing ‘active’ mental activity. Weiser and Brown argues that this can be reached in two ways; ) Allowing the technology (or information) to move between the centre to the periphery of our attention (and between these two states) and ) by enhancing our peripheral reach. is is done by allowing more data to enter the periphery cues. As described in their paper, a video conference could be an example of technology that enhance the peripheral reach in respect to an ordinary telephone call where the users cannot use facial and body expressions as part of their communication []. In many ways, ubiquitous systems tries to embed the notion of ’ready at hand’, meaning that these highly distributed, networked systems and devices should adapt to the current needs of the user or users. In normal use the system should be invisible and not interfere with the present task. However, when a breakdown occurs the user should be able to inspect the system to determine the reason and, if possible, resolve the situation. If the system is composed of multiple devices, it should be possible to replace malfunctioning devices with new ones without having to recompile or restart the system. We do not claim that techniques such as self-reconfiguration, error detection and fault tolerance should not be used. We make the observation that such mechanisms will never be perfect and that we therefore, as a supplement, need a way to handle the situations where the mechanisms are imperfect. Palpable computing is researched in the EU IST project PalCom []. e main output of the project is a conceptual framework for palpable computing, an open architecture supporting palpable computing, and a collection of tools to be used in development of palpable computing applications. A part of the work in the project deals with developing palpable computing prototypes using participatory design to provide input to the conceptual framework and the design of the open architecture. e Active Surfaces [] concept provides support for physical-functional and cognitive rehabilitation in a swimming pool setting. e concept has been developed using participatory design techniques in corporation with therapists and patients. rough analysis of the rehabilitation practice an activity (i.e. a number of different games) has been developed in which children assemble floating tiles into meaningful configurations. Each of the tiles is a resource constrained embedded
.. Active Surfaces
system that communicates using only a low bandwidth short-range infrared link. e only output available to the user is a set of light emitting diodes and therefore the game is an example of a ubiquitous computing system where it is essential that the physical and functional characteristics are such that palpability can emerge during use. For the software on the tiles, support for palpability is achieved by adhering to the PalCom open architecture [], and by building on the PalCom service framework []. Services developed using the framework can be combined into PalCom assemblies, which coordinate the services and provide support for inspection, deconstruction and reconstruction. rough interaction with the assemblies, the therapist can inspect and change the configurations of the tiles. is way, she can adapt the therapeutic activity in the middle of an exercise, and the visibility given by the assemblies helps her cope with unexpected breakdown situations. e rest of the paper is structured as follows. In the next section we describe the Active Surfaces concept and the physical and functional aspects of the prototype. Section . presents the PalCom software architecture and demonstrates how it can be used to support palpability in the implementation of the prototype. In Section . scenarios from therapist work are presented, together with an evaluation of how the prototype supports palpable qualities. Section . sums up conclusions and presents future work. . A S Active Surfaces is a concept developed for rehabilitation practitioners being a support for physical-functional and cognitive rehabilitation treatments in a swimming pool setting. erapists working in cognitive and physical rehabilitation with disabled patients usually experience their job as challenging and demanding. Every time the therapist starts a treatment she has to define a specific program and ad hoc solutions with the aim of designing a rehabilitation intervention that could adapt to the individual patients’ needs. us, the work of the therapist is mainly characterized by creativity both in designing engaging activities and suitable tools. e lack of integration of physical and cognitive rehabilitation represents a constraint for current rehabilitation practice. e cognitive tasks are usually too static and children may lose attention. On the other hand, motor rehabilitation is very demanding at a physical level and is based on repetitive sequences of actions: patients often perceive them as tiring and not engaging. Here the Active Surfaces allow an integration of these two therapeutic goals with the activity. Water as such is an interesting context from the activity perspective; Water creates a safe context where impaired people can move autonomously relying on the added support to the body, something they cannot do elsewhere. Apart from this, water also poses specific and interesting research issues both for the development of digital technologies and for the therapeutic practice. e work has been driven following a co-evolutionary method [, ]. e approach integrates participatory design with creative concept design, using dif
Chapter . Palpability support demonstrated
ferent typologies of scenarios for converging ideas into solutions. e concept and project has been developed together with children affected by different impairments undergoing therapeutic activities in the swimming pool, their parents, trainers and therapists at the swimming pool and at the ‘Le Scotte’ hospital in Siena, Italy. e early phases of the fieldwork have been devoted to understand the activity, to define requirements, and to collect best practices. On this basis, the concept of the Active Surfaces has been developed, capitalizing on participatory design activities and creative workshops together with Traveling Architect [] and Future Lab [] sessions.
..
e Prototype
Figure .: Tiles e prototype consists of a set of floating tiles (figure .) that can be connected to each other to form a network. e tiles support multiple games by having a simple composable physical appearance and multi-purpose programmable hardware. On each of the tiles’ four sides magnets are placed to make the tiles “snap” together when they are in close vicinity. On the top of the tile is a replaceable plastic cover also held in place by magnets. e image on the cover depends on the game. On each side of the tiles light emitting diodes (LEDs) provide visual feedback to the user. Inside each tile an embedded system uses infrared light to communicate with and detect the presence of other tiles. Two tiles can only communicate if they are close to each other. Figure . shows an overview of the hardware components in the tiles. e main computational unit is the UNC module, which is an ARM-based embedded system running uClinux[] at MHz with approx
.. Active Surfaces
imately MB ram. e UNC module communicates with a sideboard using a Tile
UNC20
RS-232
DLP (IR ports, IR Modulator, LED controller, LEDs)
Figure .: Hardware serial connection. e sideboard is responsible for controlling the infrared communication and the LEDs. e bandwidth of the infrared communication is approximately bits per second.
.. Games e tiles support multiple games and in the following we describe a few suggestions. To change the current game the therapist connects the tile to a PDA running PalCom software. Since the PDA is not suited for a wet environment this should be done prior to the training activity. A lot of games can be imagined for the Active Surfaces. However, for a game to be appropriate for the tiles it should support both physical and cognitive rehabilitation while at the same time be implementable on the resource-constrained devices. Furthermore, to be able to help a wide range of patients the set of games should be of varying difficulty, both on the physical and on the cognitive level. Finally, the games should be open ended and configurable so that they can be adapted and customized to each rehabilitation session. In this section we describe three games with different properties with respect to physical and cognitive rehabilitation. e first game, catch, is meant to only require simple cognitive effort but challenges the patients reflexes, speed, and coordination. e second game, scrabble, has the requirement that the patient should be able to form words out of letters. e last game, puzzle, is a traditional puzzle game in which an image is created by assembling the tiles in a specific pattern.
Catch In the catch game the therapist aligns a set of tiles and gives another tile to the patient (at the bottom in figure .). When the game is started the point of the game is for the patient to try to catch the light by approaching her tile to the glowing tile within a certain timeframe. If she succeeds another random tile will light up (not hers) and she tries to catch that one. When she eventually fails to catch the
Chapter . Palpability support demonstrated
Figure .: Catch
light before the time limit her tile will blink how many lights she caught. e game can be adapted to the patient by configuring the length of the timeframe.
Scrabble In the scrabble game each tile has a letter on the surface. e patient uses the tiles to create words. When a tile is part of a word it lights up on all four sides. Each tile should be aware of what letter it has on the face. e memory requirement for the game depends on the number of tiles and on which letters the tiles have. As an example at least English words can be generated from letters on the tiles in figure . . Since this number grows exponentially with the number of tiles it is not feasible to store all possible combinations on each tile. Instead, only the valid words for a particular tile-letter configuration should be uploaded to the tiles. e letter configuration should therefore be uploaded along with the game before the training activity.
H CARD T
H C ARD T
Figure .: Scrabble
¹a, ad, at, act, arc, art, cad, car, cat, had, hat, rat, tad, tar, arch, card, cart, char, chat, dart, hard, hart, chard, and chart
.. Implementation
Puzzle In the puzzle game the face of each tile is part of a larger image (see figure .). Initially the tiles are spread in a random pattern after which the patient starts to solve the puzzle. As the game progresses the patient gets continuous feedback from the LEDs. When two tiles are connected correctly the corresponding sides light up (fig. .a). When all of a tile’s neighbors are correct all sides of that tile light up (fig. .b), and finally when the puzzle is solved the outline of the solution lights up (fig. .c).
(a)
(b)
(c)
Figure .: Puzzle During the session the therapist can change the faces of the tiles to make a new puzzle. To reprogram the tiles a special assembler tile is used. e assembler tile has the same physical appearance as the other tiles, but also has a button. To make the tiles remember the new solution they are arranged in the solution pattern and the assembler tile is put next to one of the tiles and the button is pressed. After this, the tiles will remember the new solution and can be scattered randomly again. is way of programming the tiles by showing them the correct solution has some similarities with programming by example [] and physical programming []. e LED feedback can be configured by the therapist to alter the difficulty level of the game. It is, e.g., easier to solve the puzzle if all the outer edges of the final solution will light up as the game is started. e different game types described above all have different game rules. ese rules defines the base of a game. Apart from them, different behavior can be configured to support the game rules and the activity. is can for example be different output to the end-user to aid in accomplishing the task, i.e. the game. is configuration can be physical and logical. . I In this section we demonstrate how the PalCom software architecture and runtime system can be used to implement the Active Surfaces prototype in a way that supports palpability. We describe the PalCom runtime system (section ..) and a simulation framework that can be used to experiment with the tiles on a standard PC (section ..). e top layer of the runtime system is the application layer in
Chapter . Palpability support demonstrated
which applications are built by composing services (section ..) into assemblies (section ..). Finally, in section .., the implementation of the puzzle game is described.
..
PalCom Runtime System Application Layer
Manual & task-driven Assembly Construction Runtime Components
Services
Assemblies
Middleware Management
Service Management
GUI/Display (opt.)
Assembly Management
Persistency (opt.)
Resource Mgt.
Storage (opt.)
Contingency Mgt.
Runtime Environment Core
Introspection
Communication
Discovery
Process & Thread Runtime Engine
Base Pal-VM
J-libs
J-Base or
JRE
Java VM (JVM)
Execution Platform
Operating System (opt.) Hardware
Figure .: PalCom layered runtime system e PalCom runtime system (see figure .) consists of four layers: the execution platform, the runtime environment, the middleware management layer, and the application layer. e execution platform consists of hardware and optionally an operating system. Presently multiple hardware platforms are supported including the UNC [] and standard PCs. e runtime environment consists of standard libraries and a runtime engine which can be Sun’s Java VM or the PalVM [], which is a compact virtual machine specially designed for embedded systems for ubiquitous computing. If the hardware platform is the UNC only the Pal-VM is supported. e middleware management layer consists of managers handling resources, services, assemblies, and contingencies. For further description of the middleware managers we refer to []. At the time of writing, the memory footprint of the middleware management layer is too big to fit into the memory
.. Implementation
of the UNC (app. MB). erefore, concurrently with the development of the hardware for the tiles and the optimization of the middleware management layer, the software for the tiles has been developed to run on a standard PC with simulated infrared communication, on top of Sun’s Java VM. When the middleware management layer fits into the memory of the UNC, the implementation of the prototype should be able to run unaltered on the UNC.
.. Simulation Framework To ease the development of game logic and software for the tiles a simulation framework (figure .) has been developed. Having a simulator available makes it possible to develop software and hardware in parallel and high level tools that are not available for the embedded platform can be used for debugging and profiling. Furthermore, testing involving repeated rearrangement of the tiles is much easier done using a mouse in a graphical user interface than physically moving the actual tiles around. e simulator consists of a model of the swimming pool as a medium for infrared communication and a graphical user interface for manipulating the physical location of the tiles. e user interface is connected with the pool model so that when a tile is moved in the user interface, the pool model is updated accordingly.
:Tile MAL
:Tile MAL
:Tile MAL
:Tile MAL
:PoolModel
Figure .: Simulation framework e model of the pool is also used in the medium abstraction layer of each of the tiles. When a tile sends a message, the medium abstraction layer of the tile accesses the pool model to determine which tiles the tile is connected to (if any) and delivers the message accordingly. From an application developer’s perspective it is transparent whether the simulation framework or the physical hardware is used. e only part of the middleware that interacts with the simulation framework is the media abstraction layer and therefore system behavior experienced on the simulator is likely to be similar on the embedded platform.
.. Services e software implementing the functionality of the tiles is divided into services using the PalCom service framework []. As described in [] a PalCom service is
Chapter . Palpability support demonstrated
an entity that ) contains a number of runtime components, ) is discoverable, and ) can be invoked remotely. e interaction with the service is done using an explicitly defined service interface. A PalCom service has a set of commands, in-going or out-going, that optionally can be grouped. An in-going command specifies a point of entry to the service that is similar to a traditional interface except that invocation of the command is done in an asynchronous manner and that no results are returned. Outgoing commands specify what in-going commands the service invokes. Both in-going and outgoing commands have types specified by MIME [] strings. We adopt the UML lollipop interface notation for commands - provided interface (“closed lollipop”) for in-going commands and required interface (“open lollipop”) for outgoing commands. PalCom services can be bound or unbound. Bound services are tied to the hardware device on which they run, and typically expose functionality in the hardware for remote use. Unbound services, on the other hand, are not tied to the hardware and can thus be moved to and installed on new devices. We use a UML stereotype <> for unbound services.
..
Assemblies
Services are connected by means of assemblies. e assembly is PalCom’s mechanism for service coordination, central in the project’s approach to support for construction and deconstruction of palpable systems. A system that is constructed using assemblies can be inspected in a service browser [], making its inner structure visible at a certain level. is gives better understanding of the system, and is particularly important when a system breaks down. Furthermore, the assembly concept targets construction of systems from services that were not originally created for cooperation with each other. By inspecting the interfaces of a set of services, it is possible to construct an assembly that combines them. Service composition has previously been used to implement ubiquitous computing applications []. Assemblies are defined by assembly scripts that can be loaded at runtime by interacting with an assembly manager (see figure .). When an assembly is loaded the assembly manager makes the appropriate connections and governs the flow of service invocations. We use the nesting mechanism in UML for assemblies. One goal of the implementation of the tiles has been to make it possible to replace the game logic easily without rebooting the devices. is is done using assemblies. A set of basic services encapsulates the basic hardware functionality of the tiles and each game is implemented as one or more unbound services that can be connected to these services. e basic services of the tiles are a LED service controlling the LEDs, a Connectivity service detecting the presence of neighbor tiles, and a Touch service receiving input from the button if one is present (as is the case for the assembler tile in the puzzle game). e combination of the assembly and the unbound services for the game logic can be replaced when switching to another game. At present only the puzzle game has been implemented. e split in functionality between an assembly and an unbound service is nor
.. Implementation
mal for a PalCom system. e assembly captures the coordination logic between services, while the services perform most of the calculations. For adding behavior to a set of services without programming a new service it is possible to express some calculation in assembly scripts, but the assembly script language is intended to be much simpler than the general-purpose programming languages normally used for implementing services. erefore, complex calculations are implemented in unbound services that are incorporated when constructing an assembly. Finding the right level of sophistication in the assembly script language, and how much should be delegated to unbound services is a challenge that is under active research in the project.
.. e Puzzle Game As described in [] each of the tiles can be in one of three states: sideHappy, localHappy, or globalHappy. e states correspond to the types of feedback given by the tiles in the game. In figure ., the top-right tile is sideHappy in figure .a, localHappy in figure .b, and globalHappy in figure .c. ree rules determine which state a tile is in: . A tile is sideHappy if it has less than four correct sides. . It is localHappy if it has four correct sides but at least one of the other tiles are sideHappy. is means that the tile has found its place in the puzzle, but the complete puzzle is not solved. . If no tile is sideHappy then all tiles are globalHappy. e puzzle is solved. As can be seen from these simple rules, the game has a notion of global state, namely, whether there is at least one sideHappy node. is information is used by the tiles to distinguish whether the tile is localHappy or globalHappy. If a tile has less than four correct sides it does not need this information (because of rule ). e global state is maintained by handling two situations: e first situation occurs when a tile observes that it has four correct sides instead of three. It then broadcasts (by using the publish-subscribe mechanism of the communication model) a challenge to the other nodes requiring any sideHappy nodes to reply immediately (also with a broadcast). If no responses are received within a certain timeframe it is concluded that there are no sideHappy nodes and that the node therefore instead of being sideHappy should be globalHappy. If a response is received the node should be localHappy. When a localHappy node receives a challenge it treats it as if it was originating from itself - the node sets a timer and waits for responses. It is assumed that the solution of the puzzle is connected and includes all nodes and therefore it cannot be the case that no nodes are sideHappy in a proper subset of all the nodes. ²We define a correct side of a tile to be a side that has a correct neighbor or has no neighbor and should have no neighbor according to the solution.
Chapter . Palpability support demonstrated
erefore, if there is a sideHappy node there is a path from that node to the node that initiated the challenge. e second situation, inverse to the first one, occurs when a node observes that it has three correct sides instead of four. e new state of the node is now sideHappy. If the node was globalHappy before the other nodes are unaware that the node is now sideHappy, and therefore a message is broadcasted specifying so. If the node was localHappy before, it can assume that there is at least one sideHappy node in the graph it is connected to. e above paragraphs describe how the global state is maintained. Alternately, this could be done using the two-phase commit (PC) protocol. e PC protocol uses, however, a lot more communication and since the inter-node communication bandwidth is approximately bits/second the protocol has been deemed inappropriate.
:AssemblerTile
:Tile
PuzzleConfAsm
PuzzleAsm
Touch
Connectivity <>
IR
<>
Configure
Puzzle <>
HappyCoord
IR
LED
Figure .: Services in the puzzle game Figure . shows an UML deployment diagram outlining the structure of the implementation. In the puzzle game there are two types of tiles - the normal tiles and the assembler tile. e normal tiles communicate with each other and with the assembler tile using IR communication. In the normal tiles the PuzzleAsm assembly (listed in figure .) connects the basic services to the unbound services handling the game logic. e Puzzle service receives connectivity events from the Connectivity service (line – in figure .) and determines the local state of the tile. is information is sent to the LED service (line –) and to the Coord service (line –) that coordinates the global state using the algorithm specified above. If all tiles are correctly aligned the Coord service notifies the LED service (line –). e assembler tile contains a Configure service with the responsibility of initiating and configuring the game and the PuzzleConfAsm assembly to connect it to the basic services.
.. Evaluation
assembly PuzzleAsm { devices { device = urn:palcom://Tile_1; } services { Connectivity on device = Connectivity; Puzzle on device = Puzzle; HappyCoord on device = HappyCoord; LED on device = LED; } connections { Connectivity -> this; Puzzle -> this; HappyCoord -> this; LED -> this; } script { when connectivityUpdate from Connectivity { send connectivityUpdated(thisevent.param) to Puzzle; } when localHappy from Puzzle { send setled('1 1 1 1') to LED; } when sideHappy from Puzzle { send setled(thisevent.sides) to LED; } when localHappy from Puzzle { send localHappy() to HappyCoord; } when sideHappy from Puzzle { send sideHappy() to HappyCoord; } when globalHappy from HappyCoord { send setled('2 2 2 2') to LED; } } }
Figure .: Puzzle assembly script
. E We argue that a system can be designed to have some palpable behavior from an activity perspective in the sense that the system is easily perceivable and allows for spontaneous interaction. During normal use it can be very hard for a user to perceive the difference between a system running a palpable framework or not. But if a breakdown occurs, these systems lose all their palpable qualities if the qualities only were implemented ‘in the interface’. On the other hand, a system can run the palpable framework, without a user perceiving any palpability in the use of the system. If the system is not designed to communicate its palpability to the users, palpability will not be perceived by the users. But finally, if combined, a much higher level of palpability can be reached within a system. Palpability is not only about internal structure of the software, it is also about communication and interaction.
Chapter . Palpability support demonstrated
In Active Surfaces, as in other distributed systems that are characterized by a high level of configurability and limited output capability, the contingencies that might occur over time is of special interest and have to be dealt with. Especially those that can occur in a multi-user environment. Multi-user not only with respect to the number of users, but also with respect to different kinds of users. e challenge here is to allow these users to be in control [], a key challenge in ubiquitous computing addressed by Palpable computing. We will try to visualize this point with a simple scenario.
One day two therapists work at the swimming pool. During the day different children arrive to start their sessions. One of the therapists uses the assembler tile to program and then configure tiles to take part in the therapeutic activity concerning one of the children. She makes a puzzle game with stable and blinking light feedback to indicate the different states of the system. While she is at lunch, her colleague takes tiles to use with another child. By mistake, she includes one of the tiles configured in the ‘first’ game. As the first therapist returns after lunch, she tries to continue the activity. Now one of the tiles acts in a strange way, or not at all. As the second therapist now has finished her work, the first therapist cannot consult her to realize that she might have altered the game. As the first therapist perceives the situation, the Active Surfaces worked before lunch, and now they do not. In distributed and resource constrained systems, many error situations can occur and normally it can be hard for a user to find the reason behind a problem or a mismatch. e assembler tile introduced before in this paper, can, besides being used in the therapeutic activity, also be used as an inspection tool. e therapist can utilize the IR communication protocol to inspect the running services within each tile. rough the inspection the therapist can understand what services and assemblies are running, how they are configured and detect whether there are resource problems that have to be solved. e therapist starts to inspect the game service, and realizes immediately that the tile configuration has been altered. It was not a system error. e therapist reconfigures the tile and can carry on the activity in the swimming pool. e Active Surfaces system has been developed together with the users (mainly therapists) of the system. e use of the Participatory Design [] method including different iterations of mock-ups, prototypes and Wizard of Oz [] sessions indicate that end-users can perceive and control the Active Surfaces as described above. Further full-scale trials have to be carried out to fully support this claim. e simple scenario demonstrates the need for inspection and user control. Here the therapist initially perceives the behavioral mismatch as a bug or error in the system. In reality all components behave as they should, but one of the tiles have been reconfigured without the knowledge of the current user. It is an example of an error occurring over time in one of the distributed components, even when the system should have been idle. e user must be provided with tools that allow
.. Conclusions and Future Work
him to understand or ‘look inside’ the system to overcome the mismatch. It is important that the user understands that this is not an error; it is a misconfiguration that can be overcome. . C F W In this paper we have described the implementation of the Active Surfaces prototype, which is used in physical and cognitive rehabilitation work. We have shown in an example scenario how palpable qualities in a system can be valuable when the system behaves in unexpected ways. In those situations, it is beneficial for the user to have a system that is built as a set of services combined into assemblies. Palpable system allows for inspection, so errors and misconfigurations can be located and corrected by end users. e Active Surfaces prototype has been implemented in a distributed, embedded system, executing in a set of floating tiles, and in a simulation framework running on a standard PC. Experiences gained during the work on the prototype provide input to the on-going development of the PalCom assembly concept. e prototype implementation has helped concretize requirements for supporting more powerful coordination logic, including coordination based on broadcast communication. e structure of the tile games calls for assemblies that span over multiple physical devices, and for decentralized assemblies that do not require particular devices always to be present. When assembly descriptions can express such behavior, less coordination logic has to be delegated to unbound services.
Acknowledgements anks to Laura Cardosi, parents and children for their open-minded collaboration and continuous support during fieldwork and participatory design. We also would like to thank our colleagues at our universities, especially Alessandro Pollini, Patrizia Marti, Alessia Rullo, Boris Magnusson, Jacob Frølund, Henrik Gammelmark, and Mie Schou Olsen. e research was part of the European IST project PalCom.
C Ո
H Jeppe Brønsted and Klaus Marius Hansen Abstract In ubiquitous computing, as more and more devices are introduced into the environment, new applications are made possible that exploit device capabilities in new ways. Currently, however, there is a mismatch between the effort involved in implementing these applications and the benefit they provide. A proposed solution is to use a service oriented architecture and implement applications as composite services. As long as the set of services that constitute the composite is static, traditional techniques can be used to specify the composite. In this paper we show how the PalCom service composition language can be extended to support service composites with dynamic membership and present a decentralized implementation. Preliminary user studies indicate that the extensions are easily understandable and simulations of application scenarios show that the performance of the implementation is appropriate for ubiquitous computing applications.
. I As more and more devices are introduced into our daily lives the vision of ubiquitous computing approaches realization. Devices interact in new ways to provide services supporting users in home and work situations that were not possible until recently. Currently, services incorporating multiple devices are typically implemented by device manufacturers to add increased value into their products and thus the possible applications are limited by what devices a particular company manufactures. Even when manufacturers cooperate to make their devices communicate using, e.g., Published as: Jeppe Brønsted and Klaus Marius Hansen. Handling membership dynamicity in service composition for ubiquitous computing. Accepted for publication in: International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, UBICOMM ’ , . Acceptance rate: A previous version was published as a workshop paper: Jeppe Brønsted and Klaus Marius Hansen. Handling membership dynamicity in service composition for ubiquitous computing. In Proceedings of the th MiNEMA Workshop, Magdeburg, Germany, September
Chapter . Handling membership dynamicity in service composition
open standards it is hard to predict which services the users want and which devices to combine. Furthermore, if a given service involves a particular set of devices, the service will only be available to users having that particular set of devices. Consider the following geotagger example mentioned in []: A user has a GPS device, a digital camera, a mobile phone with GPRS, and a home server. When pictures are taken they are automatically tagged with positional information from the GPS and uploaded to the server using the mobile phone.
In this application its not clear which manufacturer would implement the application since all the devices involved can be used for multiple purposes and should, e.g., the phone manufacturer decide to implement the service, it would only be of use to the subset of customers having the particular relevant device constellation. Another issue with applications consisting of multiple devices interacting is that if a fault occurs, it can be hard to determine the cause. In the above example, the GPS device could run out of battery and unless the application has been designed with that particular contingency in mind, the user has to check each of the devices to resolve the situation. Another problem could be that the GPS device is configured to send messages in a format that is not understood by the application. In this case the user is probably even worse off because all devices will appear to be working correctly. If device capabilities are exposed through service interfaces, anyone with access to the interfaces can, in principle, develop applications exploiting the devices and thus the manufacturers will not have to try to anticipate every combination a particular device might be involved in. To achieve maximum interoperability the manufacturers have to agree on a format for service specifications or at least make available the formats used. Whether the manufacturers are interested in this is not the topic of this paper but if a standard was agreed upon the utility of the devices would be enhanced. When users compose services into applications, it is problematic to handle composites with a varying number of members. An example could be a chat application that dynamically includes new devices as they arrive. If the application was expressed in source code, this would typically be handled by collections and specialized logic specifying how the composite evolves over time. Since source code is not understandable by end users in general, we do not consider this to be an option. e contribution of this paper is twofold. Firstly, we present an extension of the PalCom assembly script language that makes it possible to specify assemblies in which the member set varies over time. We demonstrate that the extended language is expressive enough for realistic applications by showing how a prototype scenario from the PalCom project can be implemented. A preliminary user study indicates that the language extension is suited for ubiquitous computing applications, that it is not hard to understand, and that it is only mildly complicated to use. Secondly, we present an implementation of a decentralized interpretation engine. Experiments
.. Related Work
show that the performance of the engine is appropriate for ubiquitous computing applications. e rest of the paper is structured as follows. e following section describes related work. In section . we briefly describe the PalCom architecture and the mechanism available for composing services into applications. In section . we present the prototype scenario and the problems involved in realizing it using traditional techniques. In section . we describe the extensions for handling membership dynamicity, describe how the prototype scenario can be realized using the extended assembly scripts, and present results from the user study. Section . presents the implementation and performance experiments and, finally, section . concludes the paper and presents future directions. . R W Service composition have previously been used to implement applications for ubiquitous computing environments []. Service orientation alone will not solve the problem of creating services exploiting the particular device set a user has. If applications are implemented by developers using a service composition framework [, , ] it is hard for the user to control which services are used, how they are connected, and how they interact. Another option is to let the user try to specify the task he wants to solve in an abstract way and let the middleware determine how services should be composed [, ]. is has the benefit that the user does not have to know which services are offered by the devices but only has to be able to specify the task to be solved. On the other hand, if a failure occurs, it can be hard for the user to find the error because the user’s understanding of the system is rooted in the abstract task specification. A third option is to let the user experiment with devices and services and manually compose the application [, , ]. is requires that the composition language or tool is sufficiently understandable and at the same time complex enough to make it possible to express useful applications. In [] a composite with a varying member set can be defined using an LDAP query over service properties, but here the flow of service invocations is specified in source code. To the best of our knowledge, none of the previous approaches deal with user-defined composites with varying member sets. Both centralized [, , ] and decentralized [] algorithms have been used to govern the flow of service invocations in the composite. . T PC O A In the PalCom project [] an open architecture [] has been developed that supports users and application developers in making more understandable applications. Using the architecture and the runtime system, applications can be built by composing services through scripts []. e scripts can be defined by application developers or by users interacting with a service browser []. Services can be composed at runtime and the internal structure of the composite can be opened
Chapter . Handling membership dynamicity in service composition
up and inspected in case of a failure or a misconfiguration. Being able to inspect the running system supports users in understanding how the application works and determine in which part of the system a failure is located. e composite can be altered at runtime by replacing services with alternates to resolve failures or to adapt the application to changing network conditions. e design of the architecture and the scripting language has been guided by requirements arising from a set of prototype scenarios developed in cooperation with users using participatory design techniques. e scenarios cover a broad range of application areas including support for major incidents, on site work by landscape architects, and rehabilitation of children with Downs syndrome. e scenarios have in common that they exploit combinations of digital devices to better support work situations and that they do not assume that a fixed network infrastructure is in place. In PalCom, composite services called assemblies consist of simple event-based scripts that declare services and devices and describe the flow of events through the assembly. is is an easily understandable way of composing services and handles static situations with few devices well. However, the script language has currently no support for composites where the set of members varies over time. Furthermore, a URN [] for each of the involved services must be known when the composite is created. is implies that it is, e.g., not possible to specify a composite that will dynamically include new devices of a particular type as they arrive.
..
PalCom Assemblies
In the PalCom architecture device functionality is encapsulated in services that can be remotely discovered and invoked. Each service has a set of commands that can be either in-going or out-going. In-going commands are similar to asynchronous methods with an optional number of parameters. ey can be invoked from other services or by the user. Out-going commands makes it possible for the services to provide output. e output can be used as input for in-going commands or can be presented directly to the user. e output has an optional number of parameters. An example could be a service acting as an interface for a lamp. e service would have two in-going commands on and off and an out-going command state that is invoked every time the state of the lamp is changed. Services and commands are composed in assemblies described by assembly scripts where services and devices are declared along with a description of which commands are connected. Variables that can hold state can also be declared. e example given in the introduction can be implemented by the assembly script listed in figure .. Lines – declare which devices take part in the assembly. Note that a unique name (URN) is given for each of the devices. Similarly, lines – declare the services in the assembly. In line – the flow of events through the assembly is described. E.g., lines – specify that when the out-going photo_taken command from the camera’s photo service is invoked, the tagger service’s tag_photo command on the mobile phone is invoked. In line a variable is declared with a MIME-type [] and in line a value is assigned to
.. e Site Sticks Scenarios
assembly GeoTagger { devices { gps = urn:palcom://gps; camera = urn:palcom://camera server = urn:palcom://server; mobile = urn:palcom://mobile; } services { gps on gps = /gps; photo on camera = /photo; tagger on mobile = /tagger; photo_db on server = /photo_db; } connections { ... } script { variables { text/nmea-0183 gpsCoord; } eventhandler { when position from gps on gps { gpsCoord = thisevent.NMEA-0183; } when photo_taken from photo on camera { send tag_photo(thisevent.Image, gpsCoord) to tagger on mobile; } when photo_tagged from tagger on mobile { send store_photo(thisevent.Image) to photo_db on server; } } } }
Figure .: Geotagger script
it. e script in figure . can be created by using a text editor or by the user by interacting with a tool. . T S S S Since the users are involved in creating the assembly scripts, an important design goal is that the script language is as simple as possible. One could easily use a general programming language to implement the assemblies, but this would defeat the goals of simplicity and understandability. e assembly script language has to be as simple as possible while at the same time powerful enough to support relevant scenarios. In this section we present the PalCom scenario Site Sticks [] where a composite service with a dynamic member set is required for realization. e scenario has been developed in cooperation with landscape architects from Edinburgh. When landscape architects try to visualize how a project will blend into the landscape at a building site, a typical approach is to place marker sticks that represent the shape of buildings, roads, gardens, etc. as outlined in the digital building
Chapter . Handling membership dynamicity in service composition
plans. Looking at a site with hundreds of sticks (see e.g. figure .) it can be hard to figure out which sticks represent a particular building. e challenge is to visualize the digital design combined with the physical reality.
Figure .: Site Sticks In the site sticks scenario, each stick is equipped with an embedded system with wireless communication. When the stick is placed in the ground, the position and role in the design is registered in the stick using a GPS device and a PDA. Later, when the architect wishes to visualize a particular part of the design, he can select the part on the PDA and the corresponding sticks will light up with a distinct color. e initial placement and the registration will not be dealt with in this paper. From a conceptual point of view it is natural to express the application that makes a subset of the sticks light up as a composite service consisting of the sticks and a PDA. However, the scripting language presented in section .. provides only limited support for the description of the assembly. One limitation is that the script will be big because all devices and services have to be declared explicitly. Another is, that the assembly cannot be expanded to include more sticks without changing the script. In the following section we propose extensions to the assembly scripts that will make it possible to express the application described more naturally. .
H M D
e extensions of the assembly scripts we propose can be divided into two parts: Selection is about selecting which devices should participate in the assembly and
.. Handling Membership Dynamicity
naming deals with how to represent the services and devices in the specification of the flow of events. .. Selection Given a set of nodes we need a method for selecting those that should be part of the assembly. In the unextended version of the scripts this is done using URNs but for assemblies with dynamic membership this is, as mentioned previously, not enough. Instead, we propose to use a simple wildcard pattern on the device URN so that a single line in the device declaration part of the script (lines – in figure .) can declare multiple devices. Lines not including a wildcard character (‘*’) will be interpreted as before. As an example, the line: stick = urn:PalCom://stick*
matches all devices with a URN with the prefix urn:PalCom://stick. Hereby, all the sticks in the site sticks scenario can be declared in a single line. While wildcards provides an easily understandable way of specifying a lot of devices, it has the drawback that semantic information has to be encoded in the device URN. In situations where devices with similar URNs have different service sets, it can be a problem only to include a subset of the devices in the assembly. erefore, as an additional method for selection, we also use the information already present in the service declaration part of the script (lines – in figure .) to exclude irrelevant devices. For example, line in figure .: photo_db on server = /photo_db;
declares that all devices matching the declaration of server must have a photo_db service. If a device has a URN that matches the server declaration but does not have a photo_db service, the device is not included in the assembly.
.. Naming With the extension mentioned above, each line in the device and service declaration parts of the script potentially declares multiple devices/services and associates a name. is name is used in the eventhandler part of the script to specify the flow of events. We extend the semantics of the eventhandler part so that the line: when photo_tagged from tagger on mobile {
is used when the out-going command photo_tagged is invoked on any mobile device. In the case that mobile only denotes a single device, the interpretation is unaltered. Similarly, the interpretation of the invoke part of the eventhandler is changed so that the line:
Chapter . Handling membership dynamicity in service composition
send store_photo(thisevent.Image) to photo_db on server;
will invoke the store_photo in-going command on all the devices denoted by server. Again, if server only denotes a single device, the interpretation is unaltered. To allow for local flow of events on devices declared with a wildcard, the keyword ‘local’ can be inserted into the send statement to denote that only services on the same device are invoked. Assume for example that my-device is declared using a wildcard and the eventhandler includes the following lines: when my-out-command from my-service-a on my-device { send local my-in-command() to my-service-b on my-device; }
en, when the my-out-command is invoked on a particular device, the my-in-command will only be invoked on the same device. e modifications above all have the property that if no device is declared using a wildcard, then there is no modifications of the interpretation of the assembly scripts. is implies that the changes are backwards compatible.
..
Implementation of the Site Sticks Scenario
We claim that the mechanisms for selection and naming described above can be used to implement the site sticks scenario in a simple and natural way. When placed in the ground, each of the sticks are assigned a set of group identifiers corresponding to their role in the building plan. Assume all sticks are equipped with two services, led and group. e led service has a single in-going command set that will turn the light on the stick on or off. e group service has an in-going command is-part-of and two out-going commands, true and false . If is-part-of is invoked with a building identifier that the stick represents a part of, the true command is invoked - otherwise the false command is invoked. e PDA has a stick-gui service where the user can specify which part of the building plan he wants to see. e stick-gui service has a single out-going command group-selected that will be invoked with a group identifier when the user selects a building. Given the services and devices described above, the site sticks scenario can be implemented by the script in figure .. Line declares the sticks using a wildcard. Lines – forwards the user specified building ID to the sticks and if the stick represents part of the building specified, the stick will be told to blink in lines – - otherwise it will be told to turn of in lines –.
.. Handling Membership Dynamicity
assembly SiteSticks { this = global-service-name; devices { stick = urn:palcom://Stick*; pda = urn:palcom://PocketLoox; } services { led on stick = /led; group on stick = /group; stick-gui on pda = /stick-gui; } connections { ... } script { eventhandler { when group-selected from stick-gui on pda { send is-part-of(thisevent.GroupId) to group on stick; } when true from group on stick { send local set('on') to led on stick; } when false from group on stick { send local set('off') to led on stick; } } } }
Figure .: SiteSticks script
e script in figure . expresses the site sticks application in a natural way because it only contains a representation of the physical elements of the application (the sticks and the PDA), the base functionality of these elements (the led service, the group service, and the PDA gui service), and the connections among these functionalities (the eventhandler script).
.. User Study A primary design goal behind the wildcard mechanism is to support assemblies with dynamic membership without making the mechanism too complicated to use. To evaluate the suitability, understandability, and complexity of the wildcard mechanism we conducted an experimental user study with participants. First, the participants were introduced to the PalCom framework and assembly scripts through a PowerPoint presentation and a demonstration. en, each participant used assembly scripts to solve a set of problems. Afterwards, the participants filled out a questionnaire . e results are summarized in table .. As can be seen, all respondents estimated the understandability of the wildcard extension to be of neutral understand¹Presentation, questionnaire and complete result set can be accessed at or by contacting the author
dk/~jb/PalComEvaluation
http://www.daimi.au.
Chapter . Handling membership dynamicity in service composition
ability or easy to understand. of replied that it is not complicated or mildly complicated to use the extension, and of replied that the wildcard extension is suited or very suited for making dynamic composites from ubiquitous computing devices. While further studies are required to increase the confidence in the results, the experimental study indicates that users find the wildcard extension not hard to understand, that it is only mildly complicated to use, and that it is suited for ubiquitous computing applications. How understandable is the wildcard extension?
How complicated is it to the use the wildcard extension?a
Not understandable Hard to understand Neutral understandability Easy to understand Very easy to understand
Not complicated Mildly complicated Complicated Fairly complicated Very complicated
a
How suited is the wildcard mechanism for making dynamic composites from ubiquitous computing devices?a Very unsuited Unsuited Neutral suitability Suited Very suited
Only participants responded to this question
Table .: Experimental user study .
D I
One way to interpret the assembly scripts is to let a central node handle the eventhandler part (e.g. lines – in figure .) of the scripts. Every time an outgoing command is invoked, a message is sent to the central node, which then determines which in-going commands should be invoked. As long as the assemblies only include a few nodes all connected to the same network, centralized interpretation is a viable option. However, for assemblies like the site sticks assembly it is not a good idea because the group service’s invocation of the led service (lines – in figure .) would have to go through the central node. erefore, we argue, it is necessary to interpret the scripts in a decentralized manner. Unlike its centralized counterpart, decentralized interpretation requires that all nodes are able to interpret parts of the scripts and this excludes a class of devices with very limited resources. An alternative to completely decentralized interpretation is to relieve some nodes of the interpretation responsibility. is, however, requires a method for selecting the nodes taking over the responsibility and has been left as future work. Two steps are required to interpret an assembly script in a decentralized manner on a set of nodes. Firstly, the script needs to be distributed to a subset of nodes (possibly all), and secondly some nodes have to make the out-command events propagate into in-going command events. In the following we present some of the design considerations behind our implementation.
.. Decentralized Interpretation
Distribution Clearly, a node should have a representation of the script (or at least a part of the script) to be able to interpret the script. Since the set of participating nodes can vary over time, it cannot be assumed that all nodes are present when the script is first executed and therefore the network should continuously be monitored to include newly arriving nodes. To avoid that the assembly stops working if a single node disappears, we let all nodes monitor the network.
Event propagation Decentralized interpretation is implemented by letting each node handle a part (possibly empty) of the eventhandler script. is amounts to invoking in-going commands when out-going commands are invoked by the services. When the member set of an assembly varies over time it is important that the interpretation responsibility is divided in such a way that nodes leaving the network have as little influence as possible on the execution of the assembly. is means that if an out-command on node N should result in the invocation of an in-command on node N, the responsibility of handling this event transformation should be placed on N or N. Hereby, that part of the assembly only fails if N or N fails. We divide the handling of each eventhandler part of a script according to the following simple rule: An eventhandler clause should be handled by the node originating the out-going command in the clause. As an example, the eventhandler clause in line – in figure . is handled by the pda node because the outgoing command invocation comes from the pda. Similarly, lines – should be handled by each of the sticks. Using this rule, all invocations with local scope will only result in intra node communication. is is not, in general, guaranteed with centralized interpretation. .. Performance To estimate the time for a command to successfully propagate from the PDA to the sticks in the site sticks scenario, we simulated the scenario on a set of PCs. PCs, connected through Ethernet, were each running a number of Java virtual machines. e scenario was simulated with to nodes implying that one to six Java virtual machines were running on each PC. For each node count commands were sent periodically every two seconds for a period of seconds. For every command sent, we measured the propagation time. In figure . the mean command propagation time along with confidence intervals are shown. As can be seen in the figure, the mean propagation time increases approximately linearly with the number of nodes. In all the experiments, the mean propagation time was below milliseconds, which is appropriate for the scenario.
Chapter . Handling membership dynamicity in service composition
Figure .: Mean command propagation time
.
C
In this paper we investigated the problem of handling composite services with dynamic membership. We presented extensions of the PalCom assembly scripts that make it possible to specify composites with dynamic member sets and showed how a prototype scenario from the domain of landscape architects could be implemented using the proposed extensions. e idea behind the language is a basic case construct that specifies the flow of service invocations. A visual representation of the language might further support the user in understanding the scripts. A preliminary user study indicates that the language extension is suited for ubiquitous computing applications, that it is not hard to understand, and that it is only mildly complicated to use, but further studies are needed to increase the confidence in the results. We presented an implementation of a decentralized interpretation engine and experiments showed that the performance of the engine is appropriate for ubiquitous computing applications. e suggested decentralized interpretation requires that all participating nodes are able to interpret the script and that can be a problem for very resource constrained devices. More powerful devices acting as proxies for the limited devices could be one way of handling this. In contrast to its centralized counterpart, the decentralized interpretation has the potential to scale better since no node has the sole responsibility for all communication in the assembly.
.. Conclusion
A e author acknowledges the work done by the participants of the PalCom project to develop prototype scenarios and design and implement the PalCom open architecture and associated tools. e work presented in this paper has been supported by ISIS Katrinebjerg (http://www.isis.alexandra.dk) and by PalCom [].
C Ո
I S C P C Jeppe Brønsted, Klaus Marius Hansen, and Mads Ingstrup Abstract Composition of services, i.e. providing new services by combining existing ones, is an idea pervading and thus important to pervasive computing. However, compared to other areas of computer science, pervasive computing technologies are more openended, context aware, dynamic, heterogeneous, often use networked sensors and actuators, and present new challenges to usability. ese six characteristics pose requirements to the design of service composition mechanisms that are unique to pervasive computing. We catalogued the technologies that in one form or another can be said to support service composition for pervasive computing, and describe their variation points. ese variation points in the design of existing composition mechanisms are important indicators for how well the resulting composites are able to cope with and exhibit the six key characteristics of pervasive computing. Our assessment of the selected technologies indicate that there is a need for more research into providing appropriate security for composites; into managing the contingencies which arise naturally in a pervasive computing environments; and for doing more thorough evaluation of the technologies, both with respect to utility and performance.
. I e ability to seamlessly compose the services from various devices in a more or less ad-hoc manner is a frequently emphasized feature of ubiquitous computing (cf. e.g. [, , ]). Given the abundant mention of this feature in visions and scenarios, one would expect a sizeable body of research and development work dedicated to its realization. However, in practice we have found far fewer cases than expected where service composition for ubiquitous computing has been a main focus of research efforts. By “main focus” we mean that actually designing, implementing and evaluating a composition technology has been a main part of the contribution Under submission. A previous version was published as a workshop paper: Jeppe Brønsted, Klaus Marius Hansen, and Mads Ingstrup. A Survey of Service Composition Mechanisms in Ubiquitous Computing. In UbiComp Workshop proceedings, pages –, . Second Workshop on Requirements and Solutions for Pervasive Software Infrastructures (RSPSI)
Chapter . Issues in Service Composition for Pervasive Computing
of the work. With that said, however, work has been carried out in the area. In this paper we take a look at this work and draw out the experiences and lessons it holds for continued development of the field. ere are two primary reasons that prompted us to do this work. Firstly, we believe, with our colleagues whose work we survey, that there is a real need for good composition mechanisms. is need arises on a variety of temporal scales, including, for instance, the user on fieldwork who is prompted by immediate circumstance to compose a set of services that allows a display on a GPS device to temporarily replace a broken one on an otherwise functional cell-phone. Or the administrator who needs to tailor commercially acquired services to the needs of people in his or her particular organization. Towards the goal of developing a good service composition mechanism, our contribution is to help understand what “good” might mean when talking about service composition for ubiquitous computing, or rather to give an account of advantages and disadvantages of various approaches and identify areas that need further attention from the research community. Secondly, we wish to support the claim of service composition for ubiquitous computing as an area of study in itself. Composition is a natural concept around which to structure ubiquitous systems and individuate parts of it that are suitably subject to e.g. contingency management, application, or storing, as witnessed by its frequent use as a new and more open-ended replacement for the traditional application concept of desktop computers. When a composition of services is utilized as a unit of application, deployment, storing, or adaptation it becomes a natural frame for addressing systemic issues such as performance, usability, security, etc. which are not determined by any particular service, but largely by the system architecture—how services are combined. is makes service composition a viable topic of research in itself. Some service composition and related techniques exist in computer science, but the composition of services in a pervasive computing environment poses new challenges. Pervasive computing technologies are characterized by being openended, context aware, dynamic, heterogeneous, and they may incorporate networked sensors and actuators. Furthermore, they present new challenges to usability. While any given application of pervasive computing does not necessarily exhibit all these traits, several of them are more and more often found at the same time. is means, first, that existing composition technologies are often not adequate(see section ..) and that, second, there is a research challenge in understanding how to do service composition in a pervasive computing environment.
Dynamicity includes changing availability of services and network connectivity. In a pervasive environment, a given service in a composite may become unavailable and need replacement. e logic for discovering and inserting a replacement service cannot be located in any of the constituent services, because they may become unavailable. erefore, contingency management is a concern for the composition mechanism.
.. Introduction
Context awareness. A Service composite can be context aware either if it is itself sensitive to changes in context or if its constituent services are context aware. A service composite may itself be context aware if the set of composed services varies with changes in context. A commonly used example of such a service is one for printing, which is often selected based on location. Heterogeneity has several dimensions. e amount of resources available for computation, storage and communication varies a lot from device to device. In terms of mobility, devices embedded in buildings are highly static while personal devices or those built into vehicles may be highly mobile. Largely orthogonal to these other dimensions of heterogeneity is the middleware and information models that devices are equipped with and its embedded services therefore rely on. is kind of heterogeneity is an important concern because it may hinder interoperability. Networked sensors and actuators are in many cases used in pervasive computing systems, often to retrieve context information or for more application specific purposes of sensing and control. Usability. In applications of pervasive computing, new models of interaction are needed because a desktop-based computer interface structured with distinct applications is no longer always available nor practical. Instead, the “applications” of pervasive computing may be composites of services targeted towards supporting particular user tasks, perhaps composed and recomposed by users themselves according to their individual and changing circumstances of engaging with pervasive technology. Although the traditional view is that usability is first and foremost determined by the user interface of systems, there are several ways in which the architecture may strongly influence the usability of a system, e.g. the support for undo functionality []. Likewise, we find that certain features at technical level are key to supporting a model of use envisioned for pervasive computing. Openendedness. Traditional systems and applications tend to have a fairly well defined application and problem domain. is is often not the case for devices and services that make up a pervasive system. us a cell phone, while certainly designed to be used as a telephone, is being used for broad variety of other purposes, including payment, navigation, music playback, and photography. A move from mobile technology to pervasive technology requires techniques that are able to cope not just with the openendedness of how devices like cell phones are used in isolation, but with the ways in which they are combined to achieve additional value. is challenge is what service composition for pervasive computing seeks to address. ese characteristics have implications for service composition, but not in a straightforward way. Because a composite of services depends on other services
Chapter . Issues in Service Composition for Pervasive Computing
for realizing its behavior, its properties depend to some degree recursively on the properties of its constituent services. If, for instance, one wishes a given composition to have new functionality that can often be achieved either in the logic of the composed service or by modification or replacement of a constituent service. erefore, the design of a service composition mechanism is a stronger determinant of the qualitative than of the functional properties of the service compositions, and it is with the qualitative aspects our main focus in this paper lies.
..
What Makes Service Composition in Pervasive Computing Special?
Service composition (also know as “service federation” or “service orchestration”) has arguably been an issue since the advent of the service concept in distributed computing. Several different technologies provide service composition mechanisms:
(Web) Service technology A range of composition mechanisms is available for web services including BPEL, OWL-S, and Web Components []. BPEL supports composition through the specification of processes that combine services (partners) in a procedurally specified workflow. With Web Components [], services are components that may, e.g., be reused and specialized. Furthermore, a Web Component may encapsulate compositional logic in the form of sequential, parallel, conditional, or iterative compositions. Further solutions in the web service area include using π -calculus and Petri nets to specify composition []. Agent technology A basic tenet of agent-based system is that agents should be social, i.e., an agent should be able to interact with other agents to solve problems []. Abstractly, Agent Interaction Protocols can be modeled, e.g., with UML interaction diagrams through Agent UML []. Concretely, the JADE agent middleware [] supports interaction protocols as specified by the Foundation for Intelligent Physical Agents’ (FIPA’s) Agent Communication Language []. Middleware technology CORBA is a widely used middleware also for embedded systems. CORBA does not inherently support composition []. However, two specifications provide some support: the CORBA configuration specification [] describes assemblies which may package components and connect components whereas the IDLScript extension [] allows for dynamic scripting of CORBA server objects and thus for a form of service composition. As noted by [], a technical solution to service composition needs at to consider at least . Planning involving discovery of candidate services and checking of composability and performance. e desired dynamicity and openendedness of per
.. Indicators for Characteristics
vasive computing puts demands on this phase. In particular, discovery at runtime should preferably be supported. . Definition involving the actual generation of the specification of service composition. e heterogeneity and openendedness of pervasive computing means that definitions may have to take into account different, possibly a priori unknown, service classes. . Implementation of the composite service bindings. In pervasive computing, dynamicity and context awareness means that the runtime of a service composition needs to be highly dynamic. Web service composition, for instance, which do support building distributed systems, is not appropriate because it cannot adequately cope with high degrees of dynamism [], and it cannot run on very small devices, so coping with heterogeneity in device size requires workarounds. e special requirements for pervasive computing in the three phases of service composition are not well supported by the three technologies. Web services, agents, and CORBA may be (and are) used as middleware for pervasive computing, but specialized solutions need to be considered for service composition in order to provide support for pervasive computing. . I C Looking at a range of service composition mechanisms, we identified a set of variation points that serve as indicators for the support for each of the characteristics described in the introduction. e service composition mechanisms were selected according to the following criteria: • We only considered architectures that enable composition of services. We defined a service to be a unit of runtime software accessible by others. • A composite is a grouping of services interacting with certain purpose • e technologies should be targeted towards ubiquitous computing. As a minimum, this means the range of devices the technology works with is not limited to desktop PCs, and that it allows for distributed deployment of the composed services. Other constraints such as on prominence, availability of technical documentation and adequate evaluation has played a role albeit we have not used strict selection criteria on these issues. For the sake of simplifying the description of the indicators, a general model of the process of composing services is depicted in figure .. e following features of the model are used as variation points in the technologies catalogued. Table . shows the technologies catalogued. In the description below the indicators are in italics.
Chapter . Issues in Service Composition for Pervasive Computing
A composite is specified by a specifying actor (end-user or developer). e composite is specified at development time or runtime and it can be specified in a configuration file, in source code or directly through end-user interaction. In the specification, the level at which a service is specified may be instances, types or implicit specification. e specification sometimes allow for expression of quality of service requirements, though the expressiveness varies a lot. At runtime, the composition mechanism has a resource use suited for a class of devices (a PDA, a Desktop PC, or both, for the surveyed technologies). For a service composite, there may be support for managing contingencies at runtime. e composite may rely on a fixed or ad-hoc infrastructure and have either centralized or decentralized topology.
Composite Service Specifies
Specification
Service
Instatiated Service
Specifying Actor
Optionals
Figure .: A general model of the elements in service composition.
.
C/I D
Each of the characteristics presented in the introduction are affected by one or more of the indicators from the previous section. In the following, we describe how the characteristics depend on the indicators and give examples of technologies that provide good support for the characteristics and thus are suited for service composition for pervasive computing. Since some characteristics have overlapping indicators, we present an overview in table ..
..
Context Awareness
For a pervasive computing system to be context aware, it should be able to respond to changes in context by providing information or executing commands. If the constituent services themselves are context aware, the system as a whole will also exhibit context awareness. Here, we only focus on context awareness provided by the composite. We divide the support for context awareness according to when it is provided. Before the composite is instantiated, support for context awareness can be provided by selecting the services to participate in the composite based on context information. Hereby, a composite specification can result in different composites according
x
x x
x
x x x
x x x
x x
Topology
x
Infrastructure
Contingencies
x x
Resource use
QoS requirements
Specified in
x
Level
Context Awareness Networked Embedded Sensors and Actuators Heterogeneous Devices Dynamicity Openendedness Usability
Specified at
Specified by
.. Characteristic/Indicator Dependencies
x
x x
Table .: Characteristic/Indicator Dependencies
to which circumstances it is instantiated under. e level of the specification of the participating services determines the set from which the services should be selected. If, e.g., the services are specified by listing instances the room for selection is small. e selection of the participating services can be determined by specifying quality of service requirements or by selecting the services among the candidates that best match type or functionality constraints. At runtime, context awareness can be supported by providing contingency handling. If the composition mechanism only supports detection of contingencies, it is important that the composite can be modified or re-specified at runtime. Amigo, DSCiPC, DSD, and Paths are predisposed for supporting context awareness because they all have the features of using implicit specification of a composition, and because they do so at runtime. e use of implicit specification means that they are able to resolve an abstract specification to a concrete composition of services. If the context of a concrete service composite changes such that it is no longer an appropriate resolution of its abstract specification, then it would take a mere re-activation of the resolution process to arrive at another concrete composite that is appropriate to the changed context. Having the composite specified at runtime ensures that such resolution can indeed be performed at runtime. Composites realized in Amigo, DSCiPC, or DSD can automatically resolve contingencies at runtime and since these technologies also allows for quality of service requirements in the composite specification, the set of context changes the composite can react to also includes quality of service parameters.
.. Networked Embedded Sensors and Actuators A prerequisite for including embedded nodes in a composite is that the composition mechanism is designed so that the resource requirements for the embedded nodes are suitable. Typically, this implies that not all nodes are equal in the composite with respect to monitoring connections, forwarding service invocations, etc., and therefore a centralized, or at least not completely decentralized, topology is preferable. If
Chapter . Issues in Service Composition for Pervasive Computing
the topology is completely decentralized, all devices must have a representation (or at least a part of ) the composite specification, which makes it important that the composite is specified in a compact form. An xml configuration is typically more cumbersome than compiled source. Of the technologies listed in table . the only service composition mechanism that directly includes embedded nodes in composites is DSCiPC. Here, the nodes are divided into a four-leveled hierarchy according to their resource availability. e powerful nodes are responsible for service discovery, composition etc., whereas low level sensors and actuators depend on other nodes to act as proxies. of the remaining technologies only support PDA-like devices and can thus only include embedded nodes by presenting their interfaces through services developed for the purpose. of these rely on a decentralized topology making it important that the composite specification is compact. e remaining two technologies require a JSE virtual machine on each node, which significantly limits the set of nodes that can participate in the composite.
..
Heterogeneous Devices
Since it can be expected that pervasive computing applications will consist of heterogeneous devices, the composition mechanism should be designed to distribute responsibilities in the composite based on device capabilities. It is not necessarily good that the resource use of the composite mechanism is low, because this typically implies that the functionality of the composite will be limited by the least capable node. Rather, heavy tasks should be delegated to powerful nodes. is also implies that a completely decentralized topology is not desirable. Nodes can be heterogeneous in terms of computation capability, memory availability, communication capability, power availability, mobility, user interface, etc. and therefore it is important that the composite is instantiated considering the available context. Optimally, the responsibility of managing the composite should be distributed among the most capable nodes, considering the concrete requirements a particular management task has. If, e.g., service descriptions are stored in a central registry, the node hosting the registry should have high availability and should be able to handle a high number of requests. Similarly, if the user can interact with a composite management interface, the interface should be located in close proximity to the user and on a device with suitable IO capability. As mentioned above, DSCiPC distributes the management tasks according to which class a device belongs to and have multiple versions of the middleware, each suited for the particular device type. Because different devices and services may rely on different interaction and information models, interoperability is an important and difficult challenge for service composition in pervasive environments. Speakeasy is based on a thorough analysis of this, and relies in its design on three key principles to further interoperability. First, a small set of fixed and domain independent interfaces help ensure interoperability by “not requiring each party engaged in an interaction to have prior domain
.. Characteristic/Indicator Dependencies
specific knowledge of every entity it may encounter.” [, p. ]. Secondly, the use of mobile code ensures that the set of fixed interfaces can acquire new behavior as appropriate. Finally, “users are the ultimate arbiters of whether an interaction among compatible entities occurs.” [, same, p. ].
.. Dynamicity Software is more dynamic the more modifications can be done at runtime instead of development time. For service composition, a key indicator for dynamicity is when and in what form the composite is specified. We see in table . that in of the technologies we have looked at, the composites are specified at runtime. Further, in of the technologies the composite is specified in either end-user interaction or in a configuration file. e odd combination of values for these features is found is one.world, in which composites are specified in source code, but at runtime. e services in one.world are applications which are programmed in source code. An application operates within and is contained in an environment. Environments can be nested, and composites can be specified across nested environments. An outer environment can intercept all of the communications of an environment nested within it, and can therefore to some degree reconfigure composites specified across its nested environments at runtime. In principle this allows a tool to handle composition at runtime, but there is to our knowledge no such tool available in one.world. Dynamic service availability can be supported by providing contingency handling. In case of a fault, a replacement service should be found and/or the user should be notified. In some applications, any node can enter or leave the network at any time. Under these circumstances, the topology should be decentralized in case the contingency handling node leaves, and the requirements for infrastructure should only be ad-hoc. Since we argued in section .. that a completely decentralized topology can result in unsuitable resource requirements for embedded nodes, there is possibly a tradeoff between the support for low end devices and contingency handling. Quality of service requirements in the composite specification is necessary to handle dynamism in network bandwidth, latency, and throughput.
.. Openendedness In traditional systems, applications are closed and cannot be modified. is is in contrast to pervasive computing environments where it cannot be expected that the purpose and functionality of a composite application remains the same for the lifetime of its constituent parts. It is often the case that applications of pervasive computing need to be repurposed to match new user requirement or changes in the context. When applications are structured in service composites, these need to be changeable, preferable at runtime. To some degree, changes in context can be resolved automatically (cf. section ..) but new user requirements are more
Chapter . Issues in Service Composition for Pervasive Computing
complicated to react to. Here, it is necessary that the user is in the loop, because the system typically has no way of knowing of the new requirements. If the composite can be specified by the end user, as it is the case for of technologies in table ., the user actively takes part in communicating the application requirements to the composition mechanism. Specification by the end user implies that the composite is specified at runtime. Of the technologies, PalCom is the only one that does not let the composite be specified in end-user interaction. In PalCom, the user has to make a configuration file specifying the composite.
..
Usability
Our main criteria for assessing the usability of a composition mechanism is whether the composite services built with a given mechanism suit the users optimally given what services are available for composition. A strong determinant of this is how the service composites come to exist. Another is whether a composite, once created, can adapt (or be adapted) to change of circumstance, such as due to contingent availability of services and resources or changes in users’ intentions with the composition. We discuss the first issue below and the second in the next paragraph. Regarding the first, we may question whether developer-specified, users-specified, or e.g. automatic synthesis based on interpretation of high-level sentences [] leaves the user better off. e PalCom assembly concept is based on an elaborate conception of this issue. It is held that autonomic, perhaps AI-based, composition or developer-specified composition based on anticipation of the user’s needs are fine in so far as the resulting composite does what the user wants it to. However these approaches are for a variety of reasons not flawless and complete enough to work consistently and so they need to be supplemented by architecture and tool support that empowers the user to create composites or modify existing ones to suit their purpose. [] us the way a composite service is specified is influential on usability by deciding whether the users can specify composite services themselves (specified by), whether they can do so at runtime (specified at ), and how it is done (specified in). Only of the surveyed technologies enable end-users to specify composite services. Lack of support for end user composition appears in several cases to be due to the focus of the research project in question rather than a fundamental constraint of the architecture it produces: In of the remaining composition mechanisms the composite is specified in a configuration file and at runtime. ese are arguably only a composition tool away from supporting end-user composition, albeit the configuration file format may be more or less constraining depending on its level of support for scripting. In general, the considered composition mechanisms may be geared more towards the user or the developer. In ICrafter, for instance, the composition is explicit mainly in the tools used by the user, rather than at the architectural level. Speakeasy, in contrast, does not provide tools for the end user to do composition,
.. Discussion
but consists of a more general framework that developers can use in their applications. . D Quite a few service composition mechanisms exist of which we have only reported on a subset, although we believe that subset to be representative. In doing so, however, it has been characteristic that no papers have focused mainly on service composition. Our analysis suggests that there are indeed both opportunities and reasons for doing so. In particular, service composition is entangled with several complex features such as service discovery and matching, contingency management, and reconfiguration. erefore, it provides a good frame around which to explore those features and their interrelation. is, however, is an area where further research is needed: the surveyed technologies only begin to scratch the surface of contingency management and efficient resource management. Likewise, more work is needed to explore the relationship between manual and autonomic execution of functionality. Concerning the notion of service composition, we found very limited signs of research that leveraged the result of previous research in the area. Such leverage is arguably easier to achieve with a common conceptualization of the research area, and we consider this survey of issues a step towards that in addition to providing an overview. Most of the technologies presented are evaluated by demonstrating that the composition mechanism can be used to implement various ubiquitous computing applications. Example applications invented by applications developers typically demonstrate a wide range of features whereas application scenarios developed in cooperation with users, have emphasis on posing relevant challenges. In some of the projects, it is evaluated how usable the composition mechanism is for users and/or developers, and, finally, some projects present measurements of various performance parameters. We note that only of the technologies have used scenario-based evaluation. is means that for most of the technologies, there is weak empirical support to a claim that the technology works in realistic settings. e six characteristics that have been our locus of analysis constitute only a subset of the qualities that may be important in a particular application of pervasive technology. We looked at these because they emphasize the design challenges of composition mechanisms that are peculiar to pervasive computing. However, a concrete design of a composition mechanism involves tradeoffs between these qualities and efficiency and security. Concerning efficiency, a specification working at the level of types (or is implicit) must use additional resources on instantiation (cf. figure ..) compared to an instance-based specification. For this tradeoff of the surveyed technologies have chosen the more flexible but poorer performing solution of type-based or implicit service specification. However, lack of performance data prevents a quantitative assessment of that performance penalty.
Chapter . Issues in Service Composition for Pervasive Computing
System Amigo [109, 148] Aura [56, 141] Daidalos [160] DSCiPC [79] DSD [8] GAIA [135] ICrafter [130] Obje [41] one.world [62,63] Ozone (WSAMI) [75] PalCom [145] Paths [86] QuAMobile [2] SCfME [32] SpeakEasy [40, 42, 115] TCE [100, 101] UbiDev [94]
Composite Specification Specified by Specified at End-users Runtime End-users Runtime Unknown Runtime App. Devs Runtime App. Devs Dev. time App. Devs Dev. time End-users Runtime End-users Runtime App. Devs Runtime App. Devs Dev. time End-users Runtime App. Devs Runtime App. Devs Runtime App. Devs Runtime End-users Runtime End-users Runtime App. Devs Dev. time Specified in End-User int. End-User int. Configuration Configuration Configuration Configuration End-User int. End-User int. Source Code Source Code Configuration Configuration Configuration Configuration End-User int. End-User int. Source Code
Level Implicit Types Types Implicit Instances, Implicit Types Instances Instances Instances Types Instances Implicit Types Types Instances Instances Implicit
QoS req. Yes Yes Yes Yes Yes No No No No Yes No No Yes No No No No
Runtime Contingencies Automatic Automatic Runtime Automatic Automatic Automatic None Detection Detection None Automatic None Automatic Detection Detection None Automatic
Resource use PDA+Server PDA+Server Unknown PDA+Mote J2SE PDA+Server PDA PDA J2SE PDA PDA PDA PDA+Server PDA PDA PDA PDA+Server
Deployment Infrastructure Fixed Ad Hoc Unknown Ad Hoc Ad Hoc Fixed Fixed Ad Hoc Ad Hoc Ad Hoc Ad hoc Fixed Ad Hoc Ad hoc Ad Hoc Ad Hoc Ad Hoc
Table .: Categorization of Service Composition Mechanisms
Topology Centralized Centralized Centralized Decentralized Decentralized Centralized Centralized Decentralized Decentralized Decentralized Centralized Centralized Unknown Decentralized Decentralized Centralized Centralized
Evaluation Sce. perf. Example Example Ex., Perf. Example Example Example Example Sce., Usab., Perf. Ex., Perf. Scenario Scenario Scenario, Perf. Performance Ex., Usab. Example Example
.. Discussion
Further towards favoring the dynamicity/adaptability end of the dynamicityperformance tradeoff, the specification of composites may support quality-of-service requirements which implies a more complex and therefore costlier instantiation (cf. figure .) step. In addition to this, of the technologies have some support for monitoring QoS at runtime. is enables detection of non-compliance with a QoS requirement which can initiate reconfiguration to ensure better reliability, but again at a cost of increased resource consumption. It is notable that only one of the surveyed technologies appears to scale to lowend devices such as sensor motes even though this may certainly be relevant. Although it seems plausible that a tradeoff exists between security and several of the other qualities we have considered, we have no data to support that claim. at is because we found very few examples where security had been considered in the design of the composition mechanism. In of the surveyed technologies have support for quality of service requirements in the composite specification and some of these technologies explicitly state that security requirements can be specified as QoS requirements. For instance, in the QoS model in Amigo [, ] security is represented by three boolean parameters: confidentiality, integrity, and non-repudiation. A e research presented in this paper has been partly funded by the EU projects “PalCom” (IST-; http://www.ist-palcom.org) and “Hydra” (IST-; http://www.hydra.eu.com).
C Ո
S O A I- A Jeppe Brønsted, Klaus Marius Hansen Abstract A requirement for the mass-market adoption of co-operative applications for vehicular ad-hoc networks is that the IT and communication infrastructure supports concurrent deployment of independent services and applications that cooperate across organizational and commercial boundaries. In this paper, we demonstrate how a Service Oriented Architecture (SOA ) can provide value for all stakeholders and from a business case we deduce technical requirements for a service infrastructure for VANETs.
. I In recent years, the adoption of distributed systems in vehicles have increased significantly by the introduction of GPS-navigation systems, fleet management systems, speed camera notification systems, TMC traffic information notification systems, etc. One example is the OnStar system in which a cell phone and a GPS system are connected to the vehicle bus to provide a wide range of services ranging from remote engine diagnostics to automatic geo-tagged emergency calls. e system has currently over million subscribers and processes more than calls every month. A common point of the systems mentioned above is that most use wide-range radio technology for communication. Only a few, if any, rely on vehicular ad-hoc networks (VANETs) using short-range communication. We conjecture that this is due, at least partly, to the fact that most applications utilizing VANETs require a critical mass of participating nodes to function optimal. If multiple corporations and organizations each try to independently establish the required user-base of their systems they will most likely fail. Published as: Jeppe Brønsted and Klaus Marius Hansen. Service Oriented Architecture for Inter-vehicle Applications. Accepted for publication in Proceedings of the th World Congress on Intelligent Transortation Systems, ¹http://www.onstar.com
Chapter . Service Oriented Architecture for Inter-vehicle Applications
In this paper, we claim that to maximize the number of nodes participating in the systems, it is important that corporations and organizations cooperate to merge their user bases so that they each reach the critical mass of participating nodes required to realize the full potential of the systems. We show how service oriented architecture can be used to by split applications up in services and sharing them across different ownership domains in a way that provides value for all stakeholders. From a business case for a set of applications, we deduce technical requirements for a service infrastructure for VANETs. A supplement to using SOA could be to, as suggested in [], extend the userbase by motivating drivers to invest in wireless equipment by offering infrastructurebased services such e.g. car-to-home date exchange. In [] a taxi radio dispatch application scenario based on mobile ad-hoc networking is presented including an analysis of both technical and financial feasibility. In the scenario, the critical mass of participating nodes (taxis) is reached by an initial investment by the taxi company. e rest of the paper is structured as follows. In the following section, we describe the characteristics of VANETs followed by a motivation for the use of VANETs for intelligent vehicle systems. Section . introduces service oriented architecture. e business case and the requirements for a service infrastructure are presented in section . and .. .
VANET C
Vehicular ad-hoc networks consisting of nodes communicating by using shortrange wireless radios are characterized by having a high degree of variability in node mobility and node density. Normally, on highways approaching vehicles will only be within transmission range for a few seconds, depending on antenna and propagation conditions. However, if traffic congestion occurs, vehicles driving in the same direction can be within range for hours. While driving in populated areas, vehicles will be within range for most of the time, but in rural areas, the traffic density can be very low. While these characteristics make it complicated to implement applications that utilize VANETs for communication, VANETs are nevertheless necessary for several reasons. .
W U VANET
One reason for using short-range wireless communication is that it can be used for proximity detection - if a node overhears a broadcast it can be certain that the broadcasting node is within a short range. A more important reason is that the alternative, wide range cellular communication, has a set of downsides that may negatively influence an applications ability to provide its services. First of all, currently cellular technology provides significantly lower bandwidth on node-to-node communication. Wide range communication have the property
.. Service Oriented Architecture
that the nodes in range share the communication capacity of the medium, and the larger range a signal has, the more nodes have to share the bandwidth. is is not necessarily a problem if the node density is low (e.g. in rural areas), but in areas where the node density is high, severe constraints are put on the communication bandwidth. Secondly, the coverage provided by cellular systems is limited in some regions. Note however that this may change in time. Finally, using cellular communication usually entails some form of paid subscription. ese downsides have the effect that some applications cannot be realized using cellular communication. e literature provides a wealth of examples. E.g. systems that warn about hazardous driving condition such as ice, roadwork, traffic congestion, road tolling systems, vehicle collision avoidance systems, etc. To realize the full potential of these applications, short-range wireless communication must to be used. In spite of the reasons for using short-range communication mentioned above, only a few, if any, commercial applications employ it. One factor is that systems relying on short-range wireless communication are typically more complex in design, implementation, evaluation, and deployment. If the application can be realized without short-range communication, it is most likely a cheaper solution, but as we argued above, this is not always possible. Another factor is that a lot of the applications mentioned above require a critical mass to work optimal. One example could be a system providing warnings about icy roads. Vehicles equipped with the system disseminate warning messages to approaching vehicles. If not enough nodes are equipped with the system, there is a high probability that messages will not reach the approaching vehicles. Furthermore, only vehicles equipped with the system will receive warnings. To reach the critical mass for a system, it is important that commercial players and organizations cooperate to include as many nodes as possible into the system. If the system is closed and based solely on proprietary protocols most likely only a small subset of the market will join in. . S O A A way to enable cooperation among corporations and organizations is to open up systems and make capabilities available to be included as parts of other systems by using a service oriented architecture. Service Oriented Architecture (SOA ) is a paradigm for organizing and utilizing distributed capabilities that may be under the control of different ownership domains []. In SOA, the needs of entities are met by capabilities provided by other entities. In the example mentioned above, at least four capabilities can be identified; the ability to detect ice, the ability to determine the position of the icy spot, the ability to disseminate a warning in a particular region (the approaching vehicles), and the ability to alert the driver. Clearly, some of these capabilities could be useful as parts of other systems and furthermore the ice warning systems functionality will not any
Chapter . Service Oriented Architecture for Inter-vehicle Applications
longer solely depend on its own market penetration but rather on the availability of a set of services that also could be used by other systems. For example, the ice warning system could use the same warning dissemination service as a traffic congestion notification system uses. .
A B C
Service orientation from a technology perspective is however not enough. e fact that corporations and organizations can match capabilities with needs across organizational and commercial boundaries does not necessarily imply that they will actually do so. Without the proper incentive for stakeholders in the system nothing will happen. To demonstrate how a service oriented architecture can be used to more quickly reach the critical mass for a system we present a business case for implementing a set of applications with value propositions for the key players. e applications all share a common goal; to provide drivers with valuable information about the environment. e drivers can subscribe to different types of data, such as information about the condition of the road, traffic congestion, gas prizes, etc. that originate from various sources. e drivers are notified through a navigation system or PDA that also is used to disseminate data to other vehicles. We divide the players into three categories. In each category, there can be independent players. For each of the categories, we present examples of who would be in that category. An overview is shown in figure .. Sensor manufacturers sell sensors or software for detecting different kinds of information about vehicles and the environment. is could, e.g., be an ice sensor manufacturer or a company that makes software that can detect traffic congestion by correlating a vehicle’s current velocity with the velocity allowed at the vehicle’s current location. Data providers are individuals or organizations collecting data using the sensors and/or software provided by the sensor manufactures. One example is a road assistance company with ice sensors installed or individuals with the traffic congestion software installed. Presentation providers are companies delivering equipment or software for displaying data in vehicles. One example could a navigation system provider that delivers stand-alone systems or software that can run on a PDA. Data consumers are the individuals or organizations interested in the data provided by the data providers. is could, e.g. be drivers or road authorities. e flow of money between the stakeholders is also shown in figure .. e data providers buy sensors or software from the sensor manufacturers and sells access to the collected data to the presentation providers. e presentation providers
.. Requirements on SOA Infrastructure
Sensor manufacturer Ice sensor Manufacturer
Presentation providers Traffic congestion software prov.
Navigation system provider
Buys data access
Buys sensors/software Data providers Road Assistance Company
Subscribes to data categories Data consumers
Idividual driver
Idividual Driver
Money
Figure .: Value chain
offer subscriptions for data to their customers (the data consumers) and hereby add value to their products (the navigation system or PDA) and generate continuous revenue from the subscription. Because the data is disseminated through the VANET, it is important that the presentation providers by contract agree to disseminate information received from all nodes - both the nodes that have installed the software or navigation system provided but also data received from competitor systems. An agreement such as this is beneficial to all parties because without it data would not be properly disseminated and no value would be added. In figure ., an example of the operation of such a system can be seen. e purple van in the bottom left corner observes an icy area and disseminates the information to the other vehicles and the road authorities using a combination of short range (WLAN) and long range (GSM) wireless communication. Installed in the van is an ice sensor bought form a sensor manufacturer. e van belongs to a company that has a contract with a navigation system provider (presentation provider) to deliver information to the navigation system providers customers. ese customers subscribe to the information. . R SOA I Before a service oriented architecture can be realized in a VANET environment, a set of technical challenges have to be addressed. First, since data should only be available for the entities paying for it, it should be possible to encrypt the data. is could, e.g. be done by the data providers by using a private key. e presentation providers could then buy matching keys for a set of services and sell the information to subscribers. If the keys are time-limited, they have to be updated by connecting to the Internet.
Chapter . Service Oriented Architecture for Inter-vehicle Applications
Road Authorities
ICE!
WLAN
GSM
Data provider
Data consumer
Figure .: Example operation
In the example in figure ., the van company would sell access to the data it collects by selling the decryption keys that will unlock the data. e van company distributes the information collected using short range and wide range wireless communication. e navigation system provider buys keys from the van company and distributes them, using a GSM connection, to those of their customers that subscribe to the data. e customers that do not subscribe to the data will not have access to it, but their navigations system will still relay data to other vehicles. Secondly, data have to travel from the nodes that detect it to the nodes that consume it. To make sure that data arrives in due time, VANET data dissemination protocols, such as e.g. [, , ], should be used. ese protocols typically exploit properties of the data communicated to optimize routing. Since we argued above that encryption should be used, it is a challenge to construct protocols that can exploit properties of encrypted data. It is a requirement that the encryption used allows for optimized routing. Finally, since the SOA infrastructure should be used for multiple applications, it is important that it is open-ended in the sense that it should be possible to add new applications to the system during operation. It should, for example, be possible for new players to enter the market.
B
[]
Speed trap information system, September . US Patent ,,.
[]
Sten L Amundsen and Frank Eliassen. A resource and context model for mobile middleware. Personal and Ubiquitous Computing, . published online first.
[]
Jacob R. Andersen, Lars Bak, Steffen Grarup, Kasper V. Lund, Toke Eskildsen, Klaus Marius Hansen, and Mads Torgersen. Design, Implementation, and Evaluation of the Resilient Smalltalk Embedded Platform. In Proceedings of the th European Smalltalk User Group Conference, .
[]
Anupriyaa Ankolekar, Mark Burstein, Jerry R. Hobbs, Ora Lassila, David Martin, Drew McDermott, Sheila A. McIlraith, Srini Narayanan, Massimo Paolucci, Terry Payne, and Katia Sycara. DAML-S: Web service description for the Semantic Web. In Proceedings of the First International Semantic Web Conference (ISWC ), volume of LNCS, pages –. SpringerVerlag, .
[]
Sèbastien Baehni, Chirdeep Singh Chhabra, and Rachid Guerraoui. Frugal Event Dissemination in a Mobile Environment. In Proceedings of ACM/IFIP/USENIX th International Middleware Conference, .
[]
Fan Bai, Narayanan Sadagopan, and Ahmed Helmy. IMPORTANT: A framework to systematically analyze the impact of Mobility on Performance of RouTing protocols for Adhoc NeTworks. In Proceedings of IEEE INFOCOM, pages –, .
[]
Vince Barabba, Chet Huber, Fred Cooke, Nick Pudar, Jim Smith, and Mark Paich. A Multimethod Approach for Creating New Business Models: e General Motors OnStar Project. Interfaces, ():, .
[]
Luciano Baresi, Elisabetta Di Nitto, Carlo Ghezzi, and Sam Guinea. A framework for the deployment of adaptable web service compositions. Service Oriented Computing and Applications, ():–, April .
[]
Len Bass, Paul Clements, and Rick Kazman. Software Architecture in Practise. Addison-Wesley, nd edition, .
BIBLIOGRAPHY
[] B. Bauer, J.P. Mueller, and J. Odell. Agent UML: A Formalism for Specifying Multiagent Software Systems. In Proceedings of the First International Workshop on Agent-Oriented Software Engineering (AOSE ), number in LNCS, pages –. Springer. [] F. Bellifemine, A. Poggi, and G. Rimassa. Developing multi-agent systems with JADE. In Proceedings of the th International Workshop on Agent eories Architectures and Languages, number in LNCS. [] Pierpaolo Bergamo, Daniela Maniezzo, Kung Yao, Matteo Cesana, Giovanni Pau, Mario Gerla, and Don Whiteman. IEEE. Wireless Network under Aggressive Mobility Scenarios. In Proceedings from the th Annual International Telemetering Conference, . [] Richard Bogenberger, Wolfgang Kellerer, Timo Kosch, omas Reicher, Christian Schwingenschlögl, Peter Sties, and Matthias Wagner. Virtual City Portal - A Multi-Network Personal Information System for Automobile Users. In IEEE/ITG International Workshop on Multiradio Multimedia Communications, . [] Linda Briesemeister. Group Membership and Communication in Highly Mobile Ad Hoc Networks. PhD thesis, Technical University of Berlin, School of Electrical Engineering and Computer Sciences, Berlin, November . [] Linda Briesemeister and Günter Hommel. Integrating Simple yet Robust protocol Layers for Wireless Ad Hoc Inter-vehicle Communications. In Proceedings of Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS), pages –, . [] Jeppe Brønsted, Erik Grönvall, and David Fors. Palpability Support Demonstrated. In Proceedings of Embedded and Ubiquitous Computing, volume of LNCS, pages –, Taipei, Taiwan, December . Springer. Acceptance rate: . [] Jeppe Brønsted and Klaus Marius Hansen. Handling membership dynamicity in service composition for ubiquitous computing. In Proceedings of the th MiNEMA Workshop, Magdeburg, Germany, September . [] Jeppe Brønsted and Klaus Marius Hansen. Handling membership dynamicity in service composition for ubiquitous computing. Accepted for publication in: International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, UBICOMM ’ , . Acceptance rate: . [] Jeppe Brønsted and Klaus Marius Hansen. Service Oriented Architecture for Inter-vehicle Applications. Accepted for publication in Proceedings of the th World Congress on Intelligent Transortation Systems, .
[] Jeppe Brønsted, Klaus Marius Hansen, and Mads Ingstrup. A Survey of Service Composition Mechanisms in Ubiquitous Computing. In UbiComp Workshop proceedings, pages –, . Second Workshop on Requirements and Solutions for Pervasive Software Infrastructures (RSPSI). [] Jeppe Brønsted, Klaus Marius Hansen, and Lars Michael Kristensen. An Infrastructure for a Traffic Warning System. In Proceedings for the IEEE International Conference on Pervasive Services, pages –, . Acceptance rate: . [] Jeppe Brønsted, Klaus Marius Hansen, and Rolf orup. A Uniform Publish-Subscribe Infrastructure for Communication in Wireless Mobile Environments. In th International Conference on ITS Telecommunications Proceedings, pages –, June . Acceptance rate: . [] Jeppe Brønsted, Klaus Marius Hansen, and Rolf orup. A Uniform Publish-Subscribe Infrastructure for Communication in Wireless Mobile Environments. In Proceedings of the rd MiNEMA Workshop, February . [] Jeppe Brønsted and Lars Michael Kristensen. Specification and Performance Evaluation of Two Zone Dissemination Protocols for Vehicular Adhoc Networks. In Proceedings of the th Annual Simulation Symposium, pages –, Los Alamitos, CA, USA, . IEEE Computer Society. Acceptance rate: . [] Monika Büscher, Margit Kristensen, and Preben Mogensen. Making the future palpable: Notes from a major incident Future Laboratory. In Proceedings of the th International Conference on Information Systems for Crisis Response and Management (ISCRAM), May . [] William Buxton. Integrating the Periphery and Context: A New Model of Telematics. In Proceedings of Graphics Interface, pages –, . [] Jain Cai and David J. Goodman. General packet radio service in GSM. Communications Magazine, IEEE, ():–, Oct . [] T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing, ():–, . [] A. Carzaniga, D.S. Rosenblum, and A.L. Wolf. Design and evaluation of a wide-area event notification service. Foundations of Intrusion Tolerant Systems, [Organically Assured and Survivable Information Systems], pages –, . [] Yair Censor. Pareto Optimality in Multiobjective Problems. Applied Mathematics and Optimization, ():–, Mar .
BIBLIOGRAPHY
[] Humberto Cervantes and Richard S. Hall. Automating Service Dependency Management in a Service-Oriented Component Model. In Proceedings of ICSE CBSE Workshop, May . [] Dipanjan Chakraborty, Anupam Joshi, Tim Finin, and Yelena Yesha. Service Composition for Mobile Environments. Mobile Networks and Applications, ():–, August . [] H. Chesbrough and R.S. Rosenbloom. e role of the business model in capturing value from innovation: evidence from Xerox Corporation’s technology spin-off companies. Industrial and Corporate Change, ():–, . [] T. Clausen and P. Jacquet. Optimized Link State Routing Protocol (OLSR). http://www.ietf.org/rfc/rfc3626.txt, . RFC . [] A. Conta and S. Deering. Internet Control Message Protocol (ICMPv) for the Internet Protocol Version (IPv) Specification, . RFC . [] Aino Vonge Corry, Klaus Marius Hansen, and David Svensson. Traveling Architects – A New Way of Herding Cats. In Quality of Software Architectures, pages –, . [] Paolo Costa and Gian Pietro Picco. Semi-probabilistic content-based publish-subscribe. In Proceegins of the th IEEE International Conference on Distributed Computing Systems (ICDCS’), pages –, Los Alamitos, CA, USA, . IEEE Computer Society. [] P. De, A. Raniwala, R. Krishnan, K. Tatavarthi, J. Modi, N.A. Syed, S. Sharma, and T. Chiueh. MiNT-m: an autonomous mobile wireless experimentation platform. Proceedings of the th international conference on Mobile systems, applications and services, pages –, . [] Christophe Dony, Jacques Malenfant, and Pierre Cointe. Prototype-based languages: from a new taxonomy to constructive proposals and their validation. In OOPSLA ’: conference proceedings on Object-oriented programming systems, languages, and applications, pages –, New York, NY, USA, . ACM. [] W. Keith Edwards, Mark W. Newman, Jana Sedivy, and Shahram Izadi. Challenge: recombinant computing and the speakeasy approach. In MobiCom ’: Proceedings of the th annual international conference on Mobile computing and networking, pages –, New York, USA, . ACM Press.
[] W. Keith Edwards, Mark W. Newman, Jana Z. Sedivy, and Trevor F. Smith. Bringing Network Effects to Pervasive Spaces. IEEE Pervasive Computing, ():–, . [] W. Keith Edwards, Mark W. Newman, Jana Z. Sedivy, Trevor F Smith, Dirk Balfanz, D. K. Smetters, H. Chi Wong, and Shahram Izadi. Using speakeasy for ad hoc peer-to-peer collaboration. In CSCW ’: Proceedings of the ACM conference on Computer supported cooperative work, pages –, New York, NY, USA, . ACM Press. [] Stephan Eichler, Christoph Schroth, and Jörg Eberspächer. Car-to-Car Communication. In Proceedings of the VDE Kongress – Innovations for Europe, . [] R. L. Erdmann and A. S. Neal. Laboratory vs. field experimentation in human factors–an evaluation of an experimental self-service airline ticket vendor. Human Factors, ():–, December . [] J. Eriksson, L. Girod, B. Hull, R. Newton, S. Madden, and H. Balakrishnan. e Pothole Patrol: Using a Mobile Sensor Network for Road Surface Monitoring. In Proceedings of the th international conference on Mobile systems, applications and services, MobiSys, pages –, New York, USA, June . ACM Press. [] Patrick . Eugster, Pascal A. Felber, Rachid Guerraoui, and Anne-Marie Kermarrec. e Many Faces of Publish/Subscribe. ACM Comput. Surv., ():–, . [] W. Fenner. Internet Group Management Protocol, Version . ietf.org/rfc/rfc2236.txt, . RFC .
http://www.
[] Andreas Festag, Holger Fussler, Hannes Hartenstein, Amardeo Sarma, and Ralf Schmitz. Fleetnet:Bringing Car-to-car Communication into the Real World. In Proceedings of the th World Congress on ITS, . [] FIPA. FIPA Abstract Architecture Specification. Technical Report SCL, Foundation for Intelligent Physical Agents, . [] B. Fleming. Automotive Safety and Convenience Electronics. Vehicular Technology Magazine, IEEE, ():–, March . [] Walter J. Franz, Hannes Hartenstein, and Bernd Bochow. Internet on the Road via Inter-Vehicle Communications. In Proc. of Workshop der Informatik :Mobile Communications over Wireless LAN, .
BIBLIOGRAPHY
[] Keita Fujii and Tatsuya Suda. Dynamic Service Composition Using Semantic Information. In Proceedings of the nd International Conference on Service Oriented Computing, New York, New York, U.S.A, November . ACM. [] Holger Füssler, Martin Mauve, Hannes Hartenstein, Dieter Vollmer, and Michael Käsemann. A Comparison of Routing Strategies for Vehicular AdHoc Networks. In Proceedings of MOBICOM, . Student Poster. [] Holger Füßler, Marc Torrent-Moreno, Matthias Transier, Andreas Festag, and Hannes Hartenstein. oughts on a Protocol Architecture for Vehicular Ad-hoc Networks. In Proceeding of the nd International Workshop on Intelligent Transportation, pages –, . [] Benoit Garbinato, Rachid Guerraoui, Jarle Hulaas, Ole Lehrmann Madsen, Maxime Monod, and Jesper Honig Spring. Mobile Computing with Frugal Objects . Technical report, EPFL I&C, . [] David Garlan, Dan Siewiorek, Asim Smailagic, and Peter Steenkiste. Project Aura: toward distraction-free pervasive computing. IEEE Pervasive Computing, ():–, . [] O. Gehring and H. Fritz. Practical results of a longitudinal control concept for truck platooning with vehicle to vehicle communication. In Prooceedings of IEEE Conference on Intelligent Transportation System, pages –, Nov . [] Shahram Ghandeharizade, Shyam Kapadia, and Bhaskar Krishnamachari. PAVAN: a policy framework for content availabilty in vehicular ad-hoc networks. In VANET ’: Proceedings of the st ACM international workshop on Vehicular ad hoc networks, pages –, New York, NY, USA, . ACM Press. [] Carlo Ghezzi, Mehdi Jazayeri, and Dino Mandrioli. Fundamentals of Software Engineering. Prentice-Hall, . [] Adele Goldberg and David Robson. Robson: Smalltalk-: e Language and Its Implementation. Addison-Wesley, . [] Joan Greenbaum and Moten Kyng. Design at work: cooperative design of computer systems. Lawrence Erlbaum Associates, Inc. Mahwah, NJ, USA, . [] Robert Grimm. One. world: Experiences with a Pervasive Computing Architecture. IEEE Pervasive Computing, ():–, . [] Robert Grimm, Janet Davis, Eric Lemar, Adam Macbeth, Steven Swanson, omas Anderson, Brian Bershad, Gaetano Borriello, Steven Gribble, and
David Wetherall. System support for pervasive applications. ACM Trans. Comput. Syst., ():–, . [] Erik Grönvall, Patrizia Marti, Alessandro Pollini, and Alessia Rullo. Active surfaces: a novel concept for end-user composition. In NordiCHI ’: Proceedings of the th Nordic conference on Human-computer interaction, pages –, New York, NY, USA, . ACM Press. [] Erik Grönvall, Alessandro Pollini, Alessia Rullo, and David Svensson. Designing game logics for dynamic Active Surfaces. Presented at MUIA : third international workshop on mobile and ubiquitous information access, . [] Piyush Gupta and P. R. Kumar. e capacity of wireless networks. IEEE Transactions of Information eory, ():–, . [] Klaus Marius Hansen, Lars M. Kristensen, Toke Eskildsen, KennethDaniel Nielsen, Rolf E. orup, Jack Fridthjof, Ulrik Merrild, and Jørn Eskildsen. e Ex Hoc Infrastructure Framework - Enhancing Traffic Safety through LIfe WArning Systems, . [] Uwe Hansmann, Lothar Merk, Martin S. Nicklous, and omas Stober. Pervasive Computing. Springer, . [] J.K. Hedrick, M. Tomizuka, and P. Varaiya. Control issues in automated highway systems. Control Systems Magazine, IEEE, ():–, Dec . [] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. System Architecture Directions for Networked Sensors. In Proceedings of the th international conference on Architectural support for programming languages and operating systems, volume , pages –, New York, NY, USA, . ACM Press. [] Gavin Holland and Nitin Vaidya. Analysis of TCP performance over mobile ad hoc networks. Wireless Networks, (/):–, . [] Elgan Huang, Wenjun Hu, Jon Crowcroft, and Ian Wassell. Towards commercial mobile ad hoc network applications: a radio dispatch system. Proceedings of the th ACM international symposium on Mobile ad hoc networking and computing, pages –, . [] Yongqiang Huang and Hector Garcia-Molina. Publish/Subscribe in a Mobile Environment. Wireless Networks, ():–, November . [] Mads Ingstrup. Towards distributed declarative architectural reflection. PhD thesis, University of Aarhus, .
BIBLIOGRAPHY
[] Valerie Issarny, Daniele Sacchetti, Ferda Tartanoglu, Francoise Sailhan, Rafik Chibout, Nicole Levy, and Angel Talamona. Developing Ambient Intelligence Systems: A Solution based on Web Services. Automated Software Engineering, ():+, . [] N.R. Jennings, K. Sycara, and M. Wooldridge. A Roadmap of Agent Research and Development. Autonomous Agents and Multi-Agent Systems, ():–, . [] Bonnie E. John and Len Bass. Usability and software architecture. Behaviour & Information Technology, ():–, . [] David B Johnson and David A Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Imielinski and Korth, editors, Mobile Computing, volume , chapter , pages –. Kluwer Academic Publishers, . [] Swaroop Kalasapur, Mohan Kumar, and Behrooz A. Shirazi. Dynamic Service Composition in Pervasive Computing. Parallel and Distributed Systems, IEEE Transactions on, ():–, . [] H.A. Karimi and J.T. Lockhart. Gps-based tracking systems for taxi cab fleet operations. In Proceedings of the IEEE-IEE Vehicle Navigation and Information Systems Conference, pages –, Oct . [] Brad Karp and H. T. Kung. Gpsr: greedy perimeter stateless routing for wireless networks. In MobiCom ’: Proceedings of the th annual international conference on Mobile computing and networking, pages –, New York, NY, USA, . ACM. [] Young-Bae Ko and Nitin H. Vaidya. Flooding-based Geocasting Protocols for Mobile Ad Hoc Networks. Mobile Networks and Applications, :–, . [] Birgitta König-Ries, Michael Klein, and Tobias Breyer. Activity-based user modeling in wireless networks. Mob. Netw. Appl., ():–, . [] Timo Kosch, Christian Schwingenschlögl, and Li Ai. Information Dissemination in Multihop Inter-Vehicle Networks. In Proceedings of the International Conference on Intelligent Transportation Systems, pages –, . [] Lars M Kristensen and Kenneth-Daniel Nielsen. On the Application of Zone Flooding in a Traffic Warning System. Technical report, Department of Computer Science, Univerity of Aarhus, . [] Emre Kıcıman and Armando Fox. Using Dynamic Mediation to Integrate COTS Entities in a Ubiquitous Computing Environment. In Proceedings of HUC , number in LNCS, pages –, .
[] Hermann Rohling Lars Wischhof, André Ebner. SOTIS - A SelfOrganizing Traffic Information System. In Proceedings of the IEEE Vehicular Technology Conference Spring, volume , pages –, April . [] Alfred Leick. GPS Satellite Surveying. John Wiley and Sons, . [] Ilias Leontiadis and Cecilia Mascolo. Opportunistic spatio-temporal dissemination system for vehicular networks. In MobiOpp ’: Proceedings of the st international MobiSys workshop on Mobile opportunistic networking, pages –, New York, NY, USA, . ACM Press. [] Philip Levis, Nelson Lee, Matt Welsh, and David Culler. Tossim: accurate and scalable simulation of entire tinyos applications. In SenSys ’: Proceedings of the st international conference on Embedded networked sensor systems, pages –, New York, NY, USA, . ACM. [] Fan Li and Yu Wang. Routing in vehicular ad hoc networks: A survey. Vehicular Technology Magazine, IEEE, ():–, June . [] Matthew MacKenzie, Ken Laskey, Francis McCabe, Peter F Brown, and Rebekah Metz. Reference Model for Service Oriented Architecture .. Technical report, OASIS, August . [] Samuel Madden, Michael J. Franklin, Joseph Hellerstein, and Wei Hong. TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks. In Proceedings of the Fifth Symposium on Operating Systems Design and implementation, pages –, . [] S. Maffioletti, MS Kouadri, and B. Hirsbrunner. Automatic resource and service management for ubiquitous computing environments. Pervasive Computing and Communications Workshops, . Proceedings of the Second IEEE Annual Conference on, pages –, . [] David A. Maltz, Josh Broch, and David B. Johnson. Experiences Designing and Building a MultiHop Wireless Ad Hoc Network Testbed. Technical report, School of Computer Science,Carnegie Mellon University, . [] S.T. March and G.F. Smith. Design and natural science research on information technology. Decision Support Systems, ():–, . [] Patrizia Marti and Claudio Moderini. Creative design in safety critical systems. In Proceedings of ECCE , September . [] Patrizia Marti and Antonio Rizzo. Levels of design: from usability to experience. In Proceedings of HCI International, July .
BIBLIOGRAPHY
[] David Martin, Massimo Paolucci, Sheila McIlraith, Mark Burstein, Drew McDermott, Deborah McGuinness, Bijan Parsia, Terry Payne, Marta Sabou, Monika Solanki, Naveen Srinivasan, and Katia Sycara. Bringing Semantics to Web Services: e OWL-S Approach. Proceedings of the First International Workshop on Semantic Web Services and Web Process Composition (SWSWPC ), pages –, . [] Ryusuke Masuoka, Yannis Labrou, Bijan Parsia, and Evren Sirin. Ontologyenabled pervasive computing applications. IEEE Intelligent Systems, ():–, . [] Ryusuke Masuoka, Bijan Parsia, and Yannis Labrou. Task Computing – e Semantic Web Meets Pervasive Computing. e Semantic Web - ISWC , /:–, . [] Martin Mauve, Jörg Widmer, and Hannes Hartenstein. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network Magazine, . [] René Meier, Jörg Kaiser, Barbara Hughes, Christiano Brudna, and Vinny Cahill. An Event Model for Real-Time Systems in Mobile Environments. In Proceedings of Workshop on Software Technologies for Future Embedded & Ubiquitous Computing Systems (WSTFEUS), . [] Lachlan B Michael. Adaptive Layered Data Structure for Inter-Vehicle Communication in Ad-Hoc Communication Networks. In Proceedings of the th World Congress on Intelligent Transportation Systems, . [] N. Milanovic and M. Malek. Current solutions for Web service composition. Internet Computing, IEEE, ():–, . [] R. Moats. URN Syntax. RFC .
http://www.ietf.org/rfc/rfc2141.txt,
[] P. Mockapetris. Domain names - concepts and facilities. org/rfc/rfc1034.txt, . RFC .
.
http://www.ietf.
[] Prasant Mohapatra, Chao Gui, and Jian Li. Group communications in mobile ad hoc networks. Computer, ():–, . [] Sonia Ben Mokhtar, Jinshan Liu, Nikolaos Georgantas, and Valérie Issarny. QoS-aware dynamic service composition in ambient intelligence environments. In Proceedings of the th IEEE/ACM international Conference on Automated software engineering, pages –, New York, NY, USA, . ACM.
[] Jaime Montemayor, Allison Druin, Allison Farber, Sante Simms, Wayne Churaman, and Allison D’Amour. Physical programming: designing tools for children to create physical interactive environments. In CHI ’: Proceedings of the SIGCHI conference on Human factors in computing systems, pages –, New York, NY, USA, . ACM Press. [] Robert Morris, John Janotti, Frans Kaashoek, Jinyang Li, and Douglas Decouto. CarNet: A Scalable Ad Hoc Wireless Network System. In Proceedings og the th ACM SIGOPS, pages –, . [] Brad A. Myers. Visual programming, programming by example, and program visualization: a taxonomy. SIGCHI Bull., ():–, . [] Tamer Nadeem, Sasan Dashtinezhad, Chunyuan Liao, and Liviu Iftode. TrafficView: A Scalable Traffic Monitoring System. In Proceedings of the IEEE International Conference on Mobile Data Management, pages –, January . [] Valery Naumov, Rainer Baumann, and omas Gross. An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces. In MobiHoc ’: Proceedings of the th ACM international symposium on Mobile ad hoc networking and computing, pages –, New York, NY, USA, . ACM. [] Mark W. Newman, Jana Z. Sedivy, Christine M. Neuwirth, W. Keith Edwards, Jason I. Hong, Shahram Izadi, Karen Marcelo, Trevor F. Smith, Jana Sedivy, and Mark Newman. Designing for serendipity: supporting end-user configuration of ubiquitous computing environments. In DIS ’: Proceedings of the conference on Designing interactive systems, pages –, New York, NY, USA, . ACM Press. [] Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang-Ping Sheu. e Broadcast Storm Problem in a Mobile Ad Hoc Network. In Proceedings of the th annual ACM/IEEE international conference on Mobile computing and networking, pages –, New York, NY, USA, . ACM. [] Brian Oki, Manfred Pfluegl, Alex Siegel, and Dale Skeen. e Information Bus® - An Architecture for Extensible Distributed Systems. In SOSP ’: Proceedings of the fourteenth ACM symposium on Operating systems principles, pages –, New York, NY, USA, . ACM Press. [] OMG. CORBA Scripting Language Specification. formal/--, Object Management Group, .
Technical Report
[] OMG. Deployment and Configuration of Component-based Distributed Applications Specification. Technical Report Formal/--, Object Management Group, .
BIBLIOGRAPHY
[] OMG. Common Object Request Broker Architecture (CORBA) Specification, Version .. Part : CORBA Component Model. Technical Report formal/--, Object Management Group, . [] PalCom. PalCom External Report no : Deliverable (..): Palpability - a conceptual framework for palpable computing. Technical report, PalCom Project IST-, . [] PalCom. PalCom External Report no : Deliverable (..): PalCom Open Architecture. Technical report, PalCom Project IST-, . [] PalCom. PalCom External Report no : Deliverable (..): End-User Composition: Software support for assemblies. Technical report, PalCom Project IST-, . [] Ramu Panayappan, Jayini Mukul Trivedi, Ahren Studer, and Adrian Perrig. VANET-based approach for parking space availability. In VANET ’: Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks, pages –, New York, NY, USA, . ACM. [] B. Parno and A. Perrig. Challenges in securing vehicular networks. In Proceedings of HotNets-IV, . [] C. Perkins, E. Belding-Royer, and D. Das. Ad hoc On-Demand Distance Vector (AODV) Routing. http://www.ietf.org/rfc/rfc3561.txt, . RFC . [] C.E. Perkins. Ad Hoc Networking. Addison-Wesley, . [] C.E. Perkins and P. Bhagwat. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. Proceedings of the conference on Communications architectures, protocols and applications, pages –, . [] Dewayne E. Perry and Alexander L. Wolf. Foundations for the study of software architecture. SIGSOFT Softw. Eng. Notes, ():–, . [] Shankar R. Ponnekanti, Brian Lee, Armando Fox, Pat Hanrahan, and Terry Winograd. ICrafter: A Service Framework for Ubiquitous Computing Environments. Proceedings of Ubicomp, , . [] Ragunathan Rajkumar, Mike Gagliard, and Liu Sha. e Real-Time Publisher/Subscriber Inter-Process Communication Model for Distributed Real-Time Systems: Design and Implementation. In Proceedings of RealTime Technology and Applications Symposium, pages –, May . [] M. Raya. e security of vehicular ad hoc networks. In Proceedings of the rd ACM workshop on Security of ad hoc and sensor networks, pages –. ACM Press New York, NY, USA, .
[] D. Raychaudhuri, I. Seskar, M. Ott, S. Ganu, K. Ramachandran, H. Kremo, R. Siracusa, H. Liu, and M. Singh. Overview of the orbit radio grid testbed for evaluation of next-generation wireless network protocols. In Proceeding of IEEE Wireless Communications and Networking Conference, pages –, . [] Robert Bosch GmbH. CAN Specification Version ., Sep . [] Manuel Román, Brian Ziebart, and Roy H. Campbell. Dynamic Application Composition: Customizing the Behavior of an Active Space. In PERCOM ’: Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, page , Washington, DC, USA, . IEEE Computer Society. [] Bill Schilit, Norman Adams, and Roy Want. Context-aware computing applications. In IEEE Workshop on Mobile Computing Systems and Applications, pages –, Dec . [] Ulrik Pagh Schultz, Erik Corry, and Kasper V. Lund. Virtual Machines for Ambient Computing: Virtual Machines for Ambient Computing: A Palpable Computing Perspective. Presented at Object Technology for Ambient Intelligence Workshop, ECOOP, . [] B. Schunemann, K. Massow, and I. Radusch. A Novel Approach for Realistic Emulation of Vehicle--X Communication Applications. In Proceedings of IEEE Vehicular Technology Conference, pages –, . [] Jatinder Pal Singh, Nicholas Bambos, Bhaskar Srinivasan, and Detlef Clawin. Wireless LAN Performance Under Varied Stress Conditions in Vehicular Traffic Scenarios. In Vehicular Technology Conference. VTC Fall, vol. , . [] Martin Skafte. Geographically Based Services in Cellular Networks. Master’s thesis, University of Aarhus, Computer Science Department, . in danish. [] João Pedro Sousa, Vahe Poladian, David Garlan, Bradley Schmerl, and Mary Shaw. Task-based adaptation for ubiquitous computing. IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, ():–, . [] Eduardo Souto, Germano Guimarães, Glauco Vasconcelos, Mardoqueu Vieira, Nelson Rosa, Carlos Ferraz, and Judith Kelner. Mires: a Publish/Subscribe Middleware for Sensor Networks. Personal and Ubiquitous Computing, pages –, Nov . [] William Stallings. Data and Computer Communications. Prentice Hall, sixth edition edition, .
BIBLIOGRAPHY
[] David Svensson. PalCom Working Note : Service framework. Technical report, PalCom Project IST-, . [] David Svensson, Görel Hedin, and Boris Magnusson. Pervasive applications through scripted assemblies of services. In Proceedings of IEEE International Conference on Pervasive Services, pages –, . [] Clemens Szyperski. Component Software – Beyond Object-Oriented Programming. Addison-Wesley/ACM Press, . [] e OSGi Alliance. OSGi Service Platform Core Specification. Release , . [] Mathieu Vallee, Fano Ramparany, and Laurent Vercouter. Flexible Composition of Smart Device Services. In e International Conference on Pervasive Systems and Computing (PSC-), Las Vegas, Nevada, USA., June, pages –, . [] Proceedings of e First ACM International Workshop on Vehicular Networks, . [] Proceedings of e Second ACM International Workshop on Vehicular Networks, . [] Werner Vogels, Robbert van Renesse, and Ken Birman. e power of epidemics: robust communication for large-scale distributed systems. SIGCOMM Comput. Commun. Rev., ():–, . [] Mark Weiser. e Computer for the Twenty-First Century. Scientific American, ():–, . [] Mark Weiser. e computer for the st century. SIGMOBILE Mob. Comput. Commun. Rev., ():–, . [] Mark Weiser and John Seely Brown. Designing Calm Technology. PowerGrid Journal, . [] Brad Williams and Tracy Camp. Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages –, . [] Hao Wu and Michael Hunter Richard Fujimoto, Randall Gunsler. MDDV: A Mobility-Centric Data Dissemination Algorithm for Vehicular Networks. In Proceedings of e First ACM International Workshop in Vehicular Networks , pages –, . [] Bo Xu, A. Ouksel, and O. Wolfson. Opportunistic resource exchange in inter-vehicle ad-hoc networks. In Proceedings of IEEE International Conference on Mobile Data Management, pages –, .
[] J. Yang and M.P. Papazoglou. Web Component: A Substrate for Web Service Reuse and Composition. Proceedings of the th International Conference on Advanced Information Systems Engineering (CAiSE’), Toronto, Canada, pages –, . [] X. Yang, L. Liu, N.H. Vaidya, and F. Zhao. A vehicle-to-vehicle communication protocol for cooperative collision warning. In Proceedings of e First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, pages –, Aug. . [] Yuping Yang, Fiona Mahon, M. Howard Williams, and Tom Pfeifer. Context-Aware Dynamic Personalised Service Re-composition in a Pervasive Service Environment. In Proceedings of Ubiquitous Intelligence and Computing, volume of LNCS, pages –. Springer, . [] Mark D. Yarvis, W. Steven Conner, Lakshman Krishnamurthy, Jasmeet Chhabra, Brent Elliott, and Alan Mainwaring. Real-world experiences with an interactive ad hoc sensor network. In Proceedings of the International Workshop on Ad Hoc Networking, pages –, . [] Jijun Yin, Tamer ElBatt, Gavin Yeung, Bo Ryu, Stephen Habermas, Hariharan Krishnan, and Timothy Talty. Performance evaluation of safety applications over DSRC vehicular ad hoc networks. In VANET ’: Proceedings of the st ACM international workshop on Vehicular ad hoc networks, pages –, New York, NY, USA, . ACM. [] F. Zhu, M.W. Mutka, and L.M. Ni. Service discovery in pervasive computing environments. Pervasive Computing, IEEE, ():–, Oct.-Dec. . [] H. Zimmermann. OSI Reference Model–e ISO Model of Architecture for Open Systems Interconnection. Communications, IEEE Transactions on, ():–, Apr . [] Esmertec - OSVM product description. http://www.esmertec.com/solutions/M2M/OSVM/.
[] European GSM coverage. http://www.coveragemaps.com/gsmposter_europe.htm.
[] Garmin TMC navigation systems. http://www8.garmin.com/traffic/fm/index.jsp.
[] Google Maps. http://maps.google.com.
[] INVENT. http://www.invent-online.de.
BIBLIOGRAPHY
[] ISIS Katrinebjerg. http://www.isis.alexandra.dk/english/.
[] LIWAS: Life warning systems. http://www.liwas.dk. [] Mesh Dynamics. http://www.meshdynamics.com/FAQ_4455.html.
[] Microsoft .NET Framework Home. http://msdn.microsoft.com/netframework/.
[] MIME Media Types. http://www.iana.org/assignments/media-types/.
[] OnStar. http://www.onstar.com.
[] PalCom - making computing palpable. http://www.ist-palcom.org. [] PalCom: On Site. http://www.ist-palcom.org/application-areas/on-site/.
[] RDS-TMC: What is it all about? http://www.rds.org.uk/episode/rdstmcbrochure.htm.
[] Sinalgo. http://dcg.ethz.ch/projects/sinalgo/.
[] Specification of the Bluetooth System, v.. https://www.bluetooth.org/. [] e Network Simulator. http://www.isi.edu/nsnam/ns/.
[] TomTom GO T datasheet. http://www.tomtom.com/lib/doc/GO920Tdatasheet.pdf.
[] uClinux. http://www.uclinux.org/.
[] UNC. http://www.unc20.net/.