NOTE: The Center for Mobile Computing is no longer active, and this web site represents a historical view of its activities from 1996-2008. Although there is still mobile-computing research underway at Dartmouth, we no longer update this web site. Please contact David Kotz with any inquiries about the CMC.


[About CMC] [Partners] [Projects] [Papers] [People] [News]


Solar System

Guanling Chen, Kazuhiro Minami, and David Kotz
November 2002

For more information, see the Solar page.

Overview

One of the goals of ubiquitous (or "pervasive") computing is to embed more computers into our daily environment, and yet make them less noticeable. To do so, applications in these "smart spaces" or "intelligent environments" use an enormous amount of information about the environment to adapt to the changing context in which they run. These applications need to know the location of people and of devices, the current weather or traffic conditions, the status of computational and human services, and so forth.

Our objective is to understand the nature of the system infrastructure required to support context-aware applications, in particular the techniques necessary to build flexible, scalable, and secure mechanisms for delivering context information to applications. Our approach is to design and build such an infrastructure, to measure its behavior under a variety of applications and loads, and to learn from the experience of real users and real application programmers. We believe that current approaches, however, do not have sufficient flexibility, scalability, or security.

We propose a middleware system, "Solar", to meet the challenge. In Solar we treat sensors of contextual data as information sources, whether they sense physical properties such as location, or computational properties such as network bandwidth. Information sources produce their data as events. An event publisher produces an event stream, and an event subscriber consumes an event stream.

Few applications want to work with the raw event streams published by sources. Applications need to filter, transform, merge, or aggregate event streams. Consider these examples. Filtering: a sensor publishes the temperature every 10 seconds while one application needs alerts only when the reading exceeds 90 degrees. Transformation: a location sensor provides coordinates, but the application needs a symbolic value ("Lobby"). Merging: an active-map application that displays the current location of all employees merges the readings from all location sensors. Aggregation: a reminder application wants to know when a user's calendar indicates it is time for a meeting and the user is not located in the meeting room.

An operator is an object that subscribes to and processes (filters, transforms, merges, or aggregates) one or more input event streams, and publishes another event stream. Since the inputs and output of an operator are all event streams, the operators can be connected recursively to form a directed acyclic graph, an event- flow graph that we call the operator graph. Solar guarantees that the graph is acyclic through its incremental construction, thus ensuring that no events are caught in a routing loop.

Our operator graph consists of three kinds of nodes: sources, operators, and applications. The sources subscribe to nothing, and wrap some form of context sensor. Operators are deterministic functions of their input events. They publish zero or more events only when they receive an input event. Applications are sinks of the graph. They subscribe to one or more event streams and react to incoming events (and possibly other stimuli, such as interactions with the user).

In our operator graph, a directed edge from node A to B represents that node B subscribes to the event stream published by node A. The operator graph may not be a tree because an operator may subscribe to multiple streams, and its published output stream may have more than one subscriber. In summary, the publishers in the graph are the sources and operators, and the subscribers in the graph are the operators and applications.

operator graph figure

This figure presents an example operator graph to show how the raw events from information sources flow through the operators to become directly usable by the applications. Circles represent publishers: S are sources, T are Transform operators, F are Filter operators, M are Merge operators, and A are Aggregation operators. Squares represent applications.

Suppose we have location-tracking sensors installed in each room and badges attached to people and devices. Each time a sensor detects a signal from a badge, it sends out an event containing the badge ID and the timestamp. In the figure these sources are labeled "Loc Sensor" with a room number; each has a transforming operator to map the badge ID to the object name associated with it.

The Building Locator operator subscribes to the current location of every object, based on the transformed and merged events that originate from the location sensors. It records the current location in its internal state. (We discuss stateful operators below.) It generates a "location change" event whenever it sees an object change location. This output event stream can be used by the Active Map application to display the objects' current location in real time. Another subscriber, Bob's Locator, filters for changes in Bob's location. Using this information, a Guide application running on Bob's PDA can display information related to his current location.

The operator 007 Monitor tracks the set of objects currently in Lab room 007. When a new object is sensed, it generates an "object entering" event. When an object has not been sensed in the past few sensor reports, this operator outputs an "object leaving" event. The filter 007 People emits events about people only, not devices. The application Lab Log subscribes to that event stream and records the events with timestamp for future reference.

If the 007 Equipment Alerter receives a "leaving" event for certain equipment, without receiving a "leaving" event for authorized personnel at about the same time, it publishes an alarm event that should be sent to the Lab administrator (Bob), whose Messenger application displays these alarms on his PDA. If there is nobody in the room with Bob, the Messenger beeps and displays the message. If there are other people in the room, the Messenger vibrates instead. Notice the Messenger subscribes to the 215 People operator (the dashed arrow) because Bob is in room 215 now. This subscription is dynamic and will change as Bob moves around.

There are several advantages of the Solar approach: First, applications receive events semantically closer to their needs than those produced by the sources. Second, due to the modular, object-oriented design we benefit from operator reusability, data abstraction, and maintainability. Third, due to the modular design this operator graph can be deployed across a network and achieve the benefits of parallelism and distribution. Fourth, since filters and aggregators can dramatically reduce traffic along the graph edges, they reduce inter-process (and often inter-host) communication requirements. Finally, by sharing the common operators and event streams the system can support more such applications and more users.

Security

In many environments it is important to limit access to sensor information, or derived information, to protect the security concerns of an organization or the privacy concerns of an individual. Most users, for example, are uncomfortable having their location tracked unless they can constrain the uses for that information. In Solar this challenge amounts to controlling access to event streams. In a large, dynamic operator graph, it is impossible for a system administrator to label operators by hand with access-control information. We have developed a way to derive access-control information for each event stream in a logically consistent way.

Our approach is inspired by recent work on information-flow models of access control. We tag publishers (and implicitly, the events they publish) with access-control lists (ACLs), and define rules by which these ACLs propagate through the operator graph. This automatic propagation allows us to avoid manual ACL construction for each publisher, and respects a discretionary model of information flow. The propagation rule is designed so that you may not receive events published by an operator, unless your principal is listed in the ACL of all of that operator's input stream and the ACL placed on the class of which that operator is an instance. This restrictive model respects the mandatory access-control model so often used in information-flow systems. To allow users to "declassify" information, e.g., by passing an event stream through a transformation operator that removes some of the more sensitive information from each event, Solar allows the user to add an ACL to the operator that expands access from that derived automatically. In the end, Solar strikes a compromise between mandatory and discretionary access control.

For more information, see the Solar page.