|
2000 USENIX Annual Technical Conference   
[Technical Index]
Location-Aware Scheduling With Minimal Infrastructure3John Heidemann (USC/ISI), Dhaval Shah (Noika)
Abstract:
Mobile computers often benefit from software
which adapts to their location.
For example, a computer might be backed up when at the office,
or the default printer might always be a nearby one.
In many existing systems, location-triggered actions
are only possible for specific applications
or with special infrastructure.
This paper describes lcron,
a system which supports user-configurable
actions triggered on change in location
or other events common to mobile computers.
Key features of lcron are its use of existing clues for location information
and mapping low-level location information into user-sensible terms.
Lcron uses a number of existing sources of location such as
network connection and base station ID,
allowing it to work without
special hardware or GPS receivers.
We map sources of low-level information such as
IP address and latitude/longitude
into user-meaningful logical locations.
We describe the design, implementation and our experiences with this system.
1. Introduction
Laptop computers are widely used today at home, at the office, and on the road. With such computers, location-aware programs could simplify a number of common tasks. Reminders can be sent to a user when a location is reached (``feed the cat when you get home''). Location-aware queueing is easy (``print this job when I'm at work''). System defaults can be updated when a location is reached (``print to the printer in room 232 when I'm at work''). Replicated or cached data can be refreshed when convenient (``back up my hard disk when I have a good network connection''). One of the reasons location-aware software has seen relatively little use is the perception that it requires special hardware or software. Pioneering work with the Xerox PARCTAB [Schilit94a] and the ORL Active Badge system [Want92b] took place in the context of office-wide wireless infrared networks which provide location information. These and other systems [Welling97a,Beadle97b,Brown97a] proposed new frameworks for location-reactive software. Lack of general-purpose location-aware software is surprising given the wide availability of portable computers and the increasing availability of wireless networking. Although some specialized applications such as mail and printing include some location awareness (perhaps queueing messages or print jobs until a network or server becomes available), these servers are usually custom designed. As a result they may have duplicative or limited detection mechanisms and rarely support user-controlled detection and actions. This paper examines a system which uses widely available hardware sources of location and existing software interfaces to provide user-configurable, location-triggered actions. We use wired (typically Ethernet) attachment points, but we also can use wireless base-station identifiers or GPS if available. We support easy user configuration by mapping low-level sources of location into user-meaningful tags and by expanding existing mechanisms to specify events in time to also specify events in space. Our model for general events is based on the cron and at programs widely used in Unix and recently available in Microsoft Windows with packages such as the Norton Program Scheduler and Microsoft System Agents. We believe that there is substantial benefit to adding a notion of location to user-configurable scheduling. The main contribution of this paper are experiences with what kinds of high-level location information are relevant to mobile users, and how we can generate this information from widely available, low-level sources. In the examples above, concepts such as ``work'', ``home'' and ``fast network'' may not directly correspond to sources of physical geographic location such as GPS. The triggered-event model we describe is actually more general, supporting actions triggered on arbitrary events such as current power status. Finally, we describe our experiences using this tool. Although we see location awareness as the primary application for our work, location is actually one instance of more general event awareness. In addition to location, laptop users often wish to respond to other system events such as power constraints (``power is low, so shut down the wireless network and don't scan for viruses now''). Other events may arise from the interaction of systems (``remind me to ask `what's new' when I next meet a particular colleague''). Our system generalizes to support actions triggered from arbitrary events such as these. In a broader sense, we see this paper as one step in understanding the question raised by the Dataman project at Rutgers: ``what if location were a first-class operating-system concept, much as time is now?'' [Imielinski94a].
|
We have also modified xcron's at program to provide a similar event specification. Users can schedule jobs ``at 8pm @home''.
Our primary source of location information is network connectivity. We examined GPS receivers as an additional source of information, but most location-aware applications we wanted to schedule depended on network connectivity, so GPS receiver cost, size, and power requirements limited its use. We also map battery power into lcron as an example non-location events.
To sense network location we measure what networks are currently configured and map either the gateway host or the network IP address and mask to a user-sensible location (as described in the next section). Currently we sense network attachments with the ``netstat -rn'' command. Hosts with dynamically assigned IP addresses (with DHCP, for example) may not have stable addresses, so we primarily use gateway addresses to identify location.
We can detect location changes both by polling and triggered notification. Triggered notification avoids the delay and constant (if low) overhead of polling. We use triggering as our primary means of detecting discrete locations. Over time we have used two ways to detect change in our system (a laptop running the RedHat distribution of Linux). Originally we detected change to network connectivity with a one-line addition to the PCCard- and PPP-configuration scripts that are used with our system. This line informs cron of location change after a new network is started. More recently (since RedHat 6.0) we have used the operating system's built-in ability to signal jobs when the network changes.
We also implement polling as a secondary mechanism to detect location changes. To implement polling, a non-location-specific cron job periodically checks the system's location, noticing and acting on any changes. The polling interval can be selected to trade off responsiveness and overhead; by default we poll every 10 minutes. Polling is required for events which are continuous in value, such as GPS data and battery power. Polling is disabled if continuous events are not needed and triggering is possible.
We recently added support to detect power transitions (between AC and battery power) as an event. Ric Faith and Avery Pennarun's apm daemon triggers a program when power mode changes. We wrote a small stub that maps these events in to lcron events. Support for different classes of events like this motivates support for the ability to ``and'' events together (when powered and network connected).
In addition to specifying which actions are triggered in response to particular events, users should also be able to specify how location is defined. As discussed in Section 4, system-measured location information is not always appropriate for direct user consumption. Lcron therefore employs a mapping function from system to user locations.
We have experimented with two ways to implement this mapping. Originally mapping was done with a short Perl program which filters raw locations into user-sensible ones. We chose to implement mapping as a program rather than through a table to increase flexibility. Networks might map gateway names into locations, while GPS data might be mapped based on physical proximity or more detailed topological understanding.
Since currently these capabilities are not widely used, we have replaced it with a table driven mapping (from gateway to logical name) that is easier to configure. Figure 2 shows a sample mapping and illustrates that in some cases multiple low-level locations may map to the same logical location (ppp, in this case). Since mapping is user-dependent we plan on a simple tool which associates the current system location (based on one or more low-level criteria) with a user location.
Lcron has been used by a few researchers at ISI since January 1998. Our users have different levels of network connectivity. At the low-end, one user's laptop attaches to a single network. At the other end, one user regularly uses four networks in three different physical locations (ISI, USC, and home). This section briefly describes our experiences developing and using lcron.
In Section 2 we described and classified a number of location-dependent tasks. We have considered lcron for four classes of day-to-day tasks:
We currently use lcron for first three tasks on a daily basis. We have also experimented with user-interface teleporting (automatically bringing up a copy of running applications on a nearby display).
None of these applications are new: file-replication [Kistler92a,Heidemann92a], automatic system configuration [Bowman90b,Weiser93a,Schilit93a], location-specific alarms [Weiser93a,Schilit93a], and teleporting [Richardson94a] have been experimented with before. The advantage of lcron is that now these applications can be easily deployed by users without the need for any extensive supporting infrastructure.
A common and effective use of lcron is for file replication and e-mail transfer. Since e-mail is often timely, it is helpful to immediately send or fetch queued messages upon connection. In addition, periodic e-mail retrieval is easily configurable with lcron. User-customization is helpful here; the importance of timely e-mail delivery can be weighed against battery constraints (when connected by a wireless network) and tolls (when connected from home via a metered service). This level of configuration would be difficult or impossible with the simpler retrieval models of most typical e-mail packages.
File replication poses similar problems. Automatic file backup is important to a safe environment. Lcron triggers this backup periodically when connected to a fast network.
For both e-mail and file backup we had previously employed customized systems of polling. To avoid draining laptop power we previously polled for the laptop from a server machine. Although functional, this system was not easy to change and required configuration on multiple machines. Replacing this system with lcron simplified configuration and concentrated it on the laptop under user control. As a result of these simplifications we automated cases that before were not considered important enough to justify the effort (for example, occational but automatic retreival of mail from secondary mailboxes), or were not feasible (immediately fetching mail on connection).
Examples of location-dependent system configuration are selecting a default printer and telephone dialing. We wrote a small program which changes the definition of a particular printer entry when the laptop arrives at a new location. Users can thus set their default printer to the printer called ``nearest'' to print to a location-dependent nearby printer. Similarly different locations have different context for telephone dialing (area codes, handling of extensions, and telephone interface). Our telephone auto-dialer supports these options; lcron allows us to automatically select between them as we do for printers. Other location-dependent tasks similar to these can be completed automatically using lcron.
A third example application we experimented with is a location-based notification service. Users can record ``reminder messages'' which are sent as e-mail when a given location or time is reached. In other cases delayed actions have proven useful (for example, downloading a file when next connected to the net).
We also experimented with teleporting in lcron. First done in the VNC system [Richardson94a], teleporting is the idea that a user's existing applications should move transparently to the nearest, most capable display. We have experimented both with VNC teleporting and a weaker form where new sessions of a set of applications are automatically begun on a nearby display when a network connection is made. Both have been useful, although automatic teleporting is not always desirable (for example, when the laptop is only briefly connected to send and receive mail).
From our experiments with lcron the primary benefit is the automation of day-to-day tasks that were difficult or not warranted beforehand. In some cases of e-mail retrieval lcron replaced manual requests. In others it replaced older, less capable and more complicated retrieval mechanisms based on application-specific polling. Finally, the simplicity of lcron configuration supported additional uses. Prior arrangements required configuration on multiple machines to avoid polling from the power-constrained laptop; lcron simplified configuration by allowing all configuration to take place on the laptop.
Lcron was developed under SunOS and several versions of RedHat Linux. Based on xcron, it inherits that system's portability. Our primary platform has been loptops running various versions of RedHat Linux. Other than small OS changes to collect location formation are specific to RedHat Linux, the core of lcron is portable to any Unix platform.
In early versions of RedHat Linux, small changes to the base operating system's network configuration scripts are required to allow lcron to avoid polling. We made 4 lines of modification to RedHat Linux's PCCard and PPP scripts (no other OS changes were required). These are not necessary with more recent versions (since RedHat 6.0).
We found one hardware limitation: we detect network configuration based on PCCard insertion and removal. One laptop included a built-in Ethernet adaptor that lacked these events. Polling the network for carrier can work around this problem; another approach would be to modify the network driver to allow an application to detect changes in the Ethernet carrier.
Our experiences with lcron development suggest that it should be easily portable to other versions of Unix. Periodic polling (perhaps at 5 minute intervals) can be used to detect network change, but we expect that direct detection with small changes will often be a possible optimization.
Lcron builds on three areas of related work. First, groups such as the Dataman project, Xerox PARC, and and the Olivetti and Oracle Research Lab have looked at general ways location awareness changes system behavior. Second, a number of groups have looked at how to modify actions to consider location information. Finally, several special purpose systems have developed custom approaches to watch for location changes.
Our work was inspired by the Dataman project's question of ``how would system software change if location were a first-class operating-system concept'' [Imielinski94a]. The Dataman project has looked at how mobility affects network transport (mobile IP) and multicast (geographic messaging). We apply their proposition in a very real sense by considering the use of location in existing approaches to task scheduling.
Xerox PARC's work in ubiquitous computing [Weiser93a] through systems such as the PARCTAB [Want95a] pioneered location-aware computing. Their work in context-aware computing described systems similar in function to lcron [Schilit93a,Schilit94a]. Lcron builds upon this work by describing how multiple, commonly available of location information (such as network connections and GPS information) can be mapped to user-relevant locations.
|
Schilit, Adams, and Want classify context-aware computing along two axes (see Figure 2 from [Schilit94a]) based on whether the task at hand is performing information retrieval or command execution and whether it is done manually or automatically. By this classification lcron is automatic (not manual) and supports commands (not information), thus falling into the ``context-triggered actions'' quadrant. However, we have shown how context-triggered actions in lcron allows us to implement contextual commands (for example, printing to the nearest printer) and automatic contextual reconfiguration (for example, by automatically replicating data), thus providing some support for some kinds of context-aware applications which are not directly supported. We believe that the final quadrant (manual information retrieval) is best solved with other work such as location-aware web-browsers [Acharya95b,Voelker95a].
Location dependent information such as nearest restaurant, availability of space in the nearest parking lot or local weather information can best be retrieved on-demand by location-aware web-browsers. On the contrary lcron mainly targets those location dependent tasks whose timely execution on location change is important for proper functioning of the system. However lcron could also be used for automatic information retrieval by scheduling an information retrieval task to be executed at different locations. Lcron thus gives users explicit control over the nature and contents of location-dependent information to be retrieved in contrast to the limited set of information available to the users of location-aware web browser.
There are several directions for future work. Our primary sources of location come from network attachments; additional experience with other sources would be helpful. Exposing the cells of a cellular network might be attractive since that information is already available. Wider use of GPS information would also be useful.
Improvements in mapping arbitrary events into lcron would also be helpful. We are currently developing and experimenting with mapping changes in power consumption to events; more experience here would be helpful.
Currently lcron focuses on one variable: what happens as the system changes state by moving around or losing power. Some location-aware applications have more sophisticated requirements. For example, reminders could be triggered when two people are co-located assumes multiple moving objects, or actions triggered when at a location and AC-powered. Work in active badges suggests that these kinds of interactions can be provided by periodically broadcasting presence information to the local area. Refinement of this idea in lcron remains future work.
Lcron currently uses a table-driven approach to specify event triggers. This tabular approach is easy for users but can limit specification flexibility. For example, it's easy to take actions at particular times if connected, but not easy to schedule a job at a connection and then at regular intervals after that time. Whether the limitations of this fairly rigid structure is a problem in many situations remains to be seen. We work around this problem with hourly polling through a helper program. Possibly a better solution is to specify events triggers through a programming language (as we map from system to user locations) and to use a front-end to construct program statements for simple cases.
We have described lcron, a system supporting user-configurable actions in response to location- and event-triggers. It has two key features: first, it uses existing sources of information, such as wired and wireless networking information, to determine location. Second, its approach at mapping these low-level sources of location and other events to user-sensible terms. Our experiences with lcron suggest that it achieves its goal of simplifying user-triggered actions in response to location changes and other events, and that this simplification allows much broader automation of location-triggered actions than alternatives.
The authors thank Geoff Kuenning development of xcron, support for integrating lcron and discussions of lcron-related issues. We would also like to thank Ramesh Govindan, Joseph Bannister and the anonymous reviewers for careful readings and suggestions to improve this paper.
We plan to make the software developed as part of this paper publicly available. Please contact the authors for current status.
2
[Acharya95b] Arup Acharya, B. R. Badrinath, Tomasz Imielinski, and Julio C. Navas. A WWW-based location-dependent information service for mobile clients. At https://www.cs.rutgers.edu/ navas/dataman/papers/loc_dep_mosaic/Overview.html, July 1995.
[Beadle97b] H.P.W. Beadle, G.Q. Maguire, Jr., and M.T. Smith. Using location and environment awareness in mobile communications. In Proceedings of the EEE/IEEE International Conference on Information, Communications, and Signal Processing, pages 1781-1785, Singapore, September 1997. IEEE.
[Bowman90b] Mic Bowman, Larry L. Peterson, and Andrey Yeatts. Univers: An attribute-based name server. Software-Practice and Experience, 20(4):403--424, April 1990.
[Brown97a] P. J. Brown, J. D. Bovey, and X. Chen. Context-aware applications: from the laboratory to the marketplace. IEEE Personal Communications Magazine, 4(5):58-64, October 1997.
[Heidemann92a] John S. Heidemann, Thomas W. Page, Jr., Richard G. Guy, and Gerald J. Popek. Primarily disconnected operation: Experiences with Ficus. In Proceedings of the Second Workshop on Management of Replicated Data, pages 2-5. University of California, Los Angeles, IEEE, November 1992.
[Imielinski94a] Tomasz Imielinski and B. R. Badrinath. Wireless mobile computing: Challenges in data management. Communications of the ACM, 37(10):18-28, October 1994.
[Kistler92a] James J. Kistler and Mahadev Satyanarayanan. Disconnected operation in the Coda file system. ACM Transactions on Computer Systems, 10(1):3-25, 1992.
[Kuenning97g] Geoff Kuenning. Experiences with an extended cron daemon. Unpublished manuscript, November 1997.
[Perkins96a] C. Perkins. IP mobility support. RFC 2002, Internet Request For Comments, October 1996.
[Richardson94a] Tristan Richardson, Frazer Bennett, Glenford Mapp, and Andy Hopper. Teleporting in an X window system environment. IEEE Personal Communications Magazine, 1(3):6-12, July 1994.
[Schilit94a] B. Schilit, N. Adams, and R. Want. Context-aware computing applications. In Proceedings of the Workshop on Mobile Computing Systems and Applications, pages 85-90, Santa Cruz, CA, USA, December 1994. IEEE.
[Schilit93a] Bill Schilit, Marvin Theimer, and Brent Welch. Customizing mobile applications. In Proceedings of the USENIX Symposium on Mobile and Location-Independent Computing, pages 129-138, Cambridge, MA, USA, August 1993. USENIX.
[Voelker95a] Geoffrey M. Voelker and Brian N. Bershad. Mobisaic: An information system for a mobile wireless computing environment. In Proceedings of the Workshop on Mobile Computing Systems and Applications, pages 185-190, Santa Cruz, CA, USA, December 1995. IEEE.
[Want92b] Roy Want, Andy Hopper, Veronica Falcao, and Jonathon Gibbons. The active badge location system. ACM Transactions on Information Systems, 10(1):91-102, January 1992.
[Want95a] Roy Want, Bill N. Schilit, Norman I. Adams, Rich Gold, Karin Petersen, David Goldberg, John R. Ellis, and Mark Weiser. An overview of the ParcTab ubiquitous computing experiment. IEEE Personal Communications Magazine, 2(6):28-43, December 1995.
[Weiser93a] Mark Weiser. Some computer science problems in ubiquitous computing. Communications of the ACM, 36(7):75-84, July 1993.
[Welling97a]
Girish Welling and B. R. Badrinath.
A framework for environment aware applications.
In Proceedings of the 17th International Conference on
Distributed Computing Systems, pages 384-391, Baltimore, Maryland, May
1997. IEEE.
This paper was originally published in the
Proceedings of the 2000 USENIX Annual Technical Conference,
June 18-23, 2000, San Diego, California, USA
Last changed: 7 Feb 2002 ml |
|