This page lists all of our papers that are relevant to the D'Agents project, and that were part of our involvement in the DARPA CoABS program. The papers are listed alphabetically.
The last update to this paper list was on Sat Jul 21 21:21:00 EDT 2007.
Abstract: We carry out a detailed analysis of a fuzzy version of Reid's classical multiple hypothesis tracking (MHT) algorithm. Our fuzzy version is based on well-known fuzzy feedback systems, but the fact that the system we describe is specialized for likelihood discrimination makes this study particularly novel. We discuss several techniques for rule activation. One of them, namely the sum-product, seems particularly useful for likelihood management and its linearity makes it tractable for further analysis. Our analysis is performed in two stages: 1) we demonstrate that, with appropriately chosen rules, our system can discriminate the correct hypothesis; and 2) the steady-state behavior with a constant input is characterized analytically. This enables us to establish the optimality of the sum-product method and it also gives a simple procedure to predict the system's behavior as a function of the rule base. We believe this fact can be used to devise a simple procedure for fine-tuning the rule base according to the system designer's needs. The application driving our fuzzy MHT implementation and analysis is the tracking of natural language text-based messages. This application is used as an example throughout the paper.
Copyright © 2002 by IEEE.
PDF
(417K)
URL: http://agent.cs.dartmouth.edu/papers/aja:fuzzy.pdf
Copyright © 2001 by the authors.
gzipped Postscript
(65K)
|
PDF
(92K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/aslam:position.ps.gz
Abstract: We present three scalable extensions of the star algorithm for information organization that use sampling. The star algorithm organizes a document collection into clusters that are naturally induced by the topic structure of collection, via a computationally efficient cover by dense subgraphs. We also provide supporting data from extensive experiments.
Copyright © 2000 by CID-CASIS.
gzipped Postscript
(145K)
|
PDF
(77K)
URL: http://agent.cs.dartmouth.edu/papers/aslam:scalable.ps.gz
Abstract: In this paper we examine the role of very simple and noisy sensors for the tracking problem. We propose a binary sensor model, where each sensor's value is converted reliably to one bit of information only: whether the object is moving toward the sensor or away from the sensor. We show that a network of binary sensors has geometric properties that can be used to develop a solution for tracking with binary sensors and present resulting algorithms and simulation experiments. We develop a particle filtering style algorithm for target tracking using such minimalist sensors. We present an analysis of fundamental tracking limitation under this sensor model, and show how this limitation can be overcome through the use of a single bit of proximity information at each sensor node. Our extensive simulations show low error that decreases with sensor density.
Copyright © 2003 by ACM.
PDF
(442K)
URL: http://doi.acm.org/10.1145/958491.958509
Abstract: The article surveys current technologies relevant to developing scientific applications on globally distributed networks. It reviews some networking and computing technologies that are having a significant impact, real or perceived, in the commercial computing world and might be valuable for future distributed scientific computing. In many cases, an unfortunate combination of technical inbreeding and aggressive marketing has created jargon and hyperbole barriers to understanding. So, presentations of these technologies too often use terminology potentially foreign to scientific computing people. That has been our experience at least. The article's goal is to remove some of these barriers. Developing scientific applications on globally distributed networks requires language support (Java, MPI, OpenMP), mechanisms for managing distributed computations and services (components and agents), and advanced networking technologies (IPv6, ATM).
Copyright © 1999 by IEEE.
PDF
(388K)
URL: http://agent.cs.dartmouth.edu/CoABS/papers/beckmann:horizons.pdf
Abstract: Many surveillance and sensing applications involve the detection of dynamic processes. Examples include battlefield situation awareness (where the processes are vehicles and troop movements), computer and network security (where the processes are worms and other types of attacks), and homeland security (where the processes are terrorist financing, planning, recruiting, and attack-execution activities). A Process Query System (PQS) is a novel and powerful software front-end to a database or real-time sensing infrastructure that allows users to define processes at a high level of abstraction and submit process definitions as queries. We describe a current working implementation that has been used for vehicle tracking using an acoustic sensor network and for computer worm detection.
Copyright © 2003 by IIIS.
PDF
(192K)
URL: http://agent.cs.dartmouth.edu/papers/berk:pqs.pdf
Abstract: Mobile agents are programs capable of migrating from one host machine to another. We propose that mobile agents purchase resource access rights from host machines thereby establishing a market for computational resources and giving agents a metric to evenly distribute themselves throughout the network. Market participation requires quantitative information about resource consumption to define demand and calculate utility.
We create a formal utility model to derive user-demand functions, allowing agents to efficiently plan expenditure and deal with price fluctuations. By quantifying demand and utility, resource owners can precisely set a value for a good. We simulate our model in a mobile agent scheduling environment and show how mobile agents may use server prices to distribute themselves evenly throughout a network.
Copyright © 1998 by the authors.
gzipped Postscript
(83K)
|
PDF
(480K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:demand.ps.gz
See also earlier version bredin:demand-tr.
Abstract: Mobile agents are programs capable of migrating from one host machine to another. We propose that mobile agents purchase resource access rights from host machines thereby establishing a market for computational resources and giving agents a metric to evenly distribute themselves throughout the network. Market participation requires quantitative information about resource consumption to define demand and calculate utility.
We create a formal utility model to derive user-demand functions, allowing agents to efficiently plan expenditure and deal with price fluctuations. By quantifying demand and utility, resource owners can precisely set a value for a good. We simulate our model in a mobile agent scheduling environment and show how mobile agents may use server prices to distribute themselves evenly throughout a network.
Copyright © 1998 by the authors.
gzipped Postscript
(101K)
|
PDF
(239K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR98-331/
See also later version bredin:demand.
Abstract: This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. From our game, we build a market-based CPU allocation policy and a strategy with which an agent may plan its expenditures for a multi-hop itinerary. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments and that our planning algorithm handles network delay gracefully.
Copyright © 2000 by ACM.
gzipped Postscript
(210K)
|
PDF
(266K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:game.ps.gz
See also earlier version bredin:game-tr.
Abstract: In traditional computational systems, resource owners have no incentive to subject themselves to additional risk and congestion associated with providing service to arbitrary agents, but there are applications that benefit from open environments. We argue for the use of markets to regulate agent systems. With market mechanisms, agents have the abilities to assess the cost of their actions, behave responsibly, and coordinate their resource usage both temporally and spatially.
We discuss our market structure and mechanisms we have developed to foster secure exchange between agents and hosts. Additionally, we believe that certain agent applications encourage repeated interactions that benefit both agents and hosts, giving further reason for hosts to fairly accommodate agents. We apply our ideas to create a resource-allocation policy for mobile-agent systems, from which we derive an algorithm for a mobile agent to plan its expenditure and travel. With perfect information, the algorithm guarantees the agent's optimal completion time.
We relax the assumptions underlying our algorithm design and simulate our planning algorithm and allocation policy to show that the policy prioritizes agents by endowment, handles bursty workloads, adapts to situations where network resources are overextended, and that delaying agents' actions does not catastrophically affect agents' performance.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(127K)
|
PDF
(386K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:game-book.ps.gz
Abstract: This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments.
Copyright © 1999 by the authors.
gzipped Postscript
(215K)
|
PDF
(234K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR99-360/
See also later version bredin:game.
Copyright © 2001 by the authors.
gzipped Postscript
(118K)
|
PDF
(155K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:info.ps.gz
Abstract: Mobile-agent systems allow applications to distribute their resource consumption across the network. By prioritizing applications and publishing the cost of actions, it is possible for applications to achieve faster performance than in an environment where resources are evenly shared. We enforce the costs of actions through markets where user applications bid for computation from host machines.
We represent applications as collections of mobile agents and introduce a distributed mechanism for allocating general computational priority to mobile agents. We derive a bidding strategy for an agent that plans expenditures given a budget and a series of tasks to complete. We also show that a unique Nash equilibrium exists between the agents under our allocation policy. We present simulation results to show that the use of our resource-allocation mechanism and expenditure-planning algorithm results in shorter mean job completion times compared to traditional mobile-agent resource allocation. We also observe that our resource-allocation policy adapts favorably to allocate overloaded resources to higher priority agents, and that agents are able to effectively plan expenditures even when faced with network delay and job-size estimation error.
Copyright © 2003 by Kluwer Academic Publishers.
PDF
(324K)
HTML
See also earlier version bredin:game.
Abstract: We propose a method for increasing incentives for sites to host arbitrary mobile agents in which mobile agents purchase their computing needs from host sites. We present a scalable market-based CPU allocation policy and an on-line algorithm that plans a mobile agent's expenditure over a multihop ordered itinerary. The algorithm chooses a set of sites at which to execute and computational priorities at each site to minimize execution time while preserving a prespecified budget constraint. We present simulation results of our algorithm to show that our allocation policy and planning algorithm scale well as more agents are added to the system.
Copyright © 1999 by the authors.
No online copy available.
See also earlier version bredin:lottery-tr.
Abstract: We propose a method for increasing incentives for sites to host arbitrary mobile agents in which mobile agents purchase their computing needs from host sites. We present a scalable market-based CPU allocation policy and an on-line algorithm that plans a mobile agent's expenditure over a multihop ordered itinerary. The algorithm chooses a set of sites at which to execute and computational priorities at each site to minimize execution time while preserving a prespecified budget constraint. We present simulation results of our algorithm to show that our allocation policy and planning algorithm scale well as more agents are added to the system.
Copyright © 1999 by the authors.
gzipped Postscript
(223K)
|
PDF
(441K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR99-345/
See also later version bredin:lottery.
Abstract: Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.
Copyright © 1998 by ACM.
gzipped Postscript
(157K)
|
PDF
(263K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:market.ps.gz
See also earlier version bredin:market-tr.
Abstract: Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.
Copyright © 1997 by the authors.
gzipped Postscript
(95K)
|
PDF
(224K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR97-326/
See also later version bredin:market.
Abstract: Mobile-agent systems have gained popularity in use because they ease the application design process by giving software engineers greater flexibility. Although the value of any network is dependent on both the number of users and the number of sites participating in the network, there is little motivation for systems to donate resources to arbitrary agents. We propose to remedy the problem by imposing an economic market on mobile-agent systems where agents purchase resources from host sites and sell services to users and other agents. Host sites accumulate revenues, which are distributed to users to be used to launch more agents. We argue for the use of markets to regulate mobile-agent systems and discuss open issues in implementing market-based mobile-agent systems.
Copyright © 1999 by the authors.
gzipped Postscript
(76K)
|
PDF
(86K)
|
HTML
Abstract: Mobile-agent systems allow user programs to autonomously relocate from one host site to another. This autonomy provides a powerful, flexible architecture on which to build distributed applications. The asynchronous, decentralized nature of mobile-agent systems makes them flexible, but also hinders their deployment. We argue that a market-based approach where agents buy computational resources from their hosts solves many problems faced by mobile-agent systems.
In our earlier work, we propose a policy for allocating general computational priority among agents posed as a competitive game for which we derive a unique computable Nash equilibrium. Here we improve on our earlier approach by implementing resource guarantees where mobile-agent hosts issue call options on computational resources. Call options allow an agent to reserve and guarantee the cost and time necessary to complete its itinerary before the agent begins execution.
We present an algorithm based upon the binomial options-pricing model that estimates future congestion to allow hosts to evaluate call options; methods for agents to measure the risk associated with their performance and compare their expected utility of competing in the computational spot market with utilizing resource options; and test our theory with simulations to show that option trade reduces variance in agent completion times.
Copyright © 2000 by Kluwer.
gzipped Postscript
(86K)
|
PDF
(161K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/bredin:risk.ps.gz
Abstract: Modern distributed systems scatter sensors, storage, and computation throughout the environment. Ideally these devices communicate and share resources, but there is seldom motivation for a device's owner to yield control to another user. We establish markets for computational resources to motivate principals to share resources with arbitrary users, to enforce priority in distributed systems, to provide flexible and rational limitations on the potential of an application, and to provide a lightweight structure to balance the workload over time and between devices. As proof of concept, we implement a structure software agents can use to discover and negotiate access to networked resources. The structure separates discovery, authentication, and consumption enforcement as separate orthogonal issues to give system designers flexibility.
Mobile agents represent informational and computational flow. We develop mechanisms that distributively allocate computation among mobile agents in two settings. The first models a situation where users collectively own networked computing resources and require priority enforcement. We extend the allocation mechanism to allow resource reservation to mitigate utility volatility. The second, more general model relaxes the ownership assumption. We apply our computational market to an open setting where a principal's chief concern is revenue maximization.
Our simulations compare the performance of market-based allocation policies to traditional policies and relate the cost of ownership and consumption separation. We observe that our markets effectively prioritize applications' performance, can operate under uncertainty and network delay, provide metrics to balance network load, and allow measurement of market-participation risk versus reservation-based computation.
In addition to allocation problems, we investigate resource selection to optimize execution time. The problem is NP-complete if the costs and latencies are constant. Both metrics' dependence on the chosen set complicates matters. We study how a greedy approach, a novel heuristic, and a shortest-constrained-path strategy perform in mobile-agent applications.
Market-based computational-resource allocation fertilizes applications where previously there was a dearth of motive for or means of cooperation. The rationale behind mobile-agent performance optimization is also useful for resource allocation in general distributed systems where an application has a sequence of dependent tasks or when data collection is expensive.
Copyright © 2001 by Jonathan L. Bredin.
gzipped Postscript
(436K)
|
PDF
(1409K)
URL: http://cmc.cs.dartmouth.edu/papers/bredin:thesis.pdf
See also later version bredin:thesis-tr.
Abstract: Modern distributed systems scatter sensors, storage, and computation throughout the environment. Ideally these devices communicate and share resources, but there is seldom motivation for a device's owner to yield control to another user. We establish markets for computational resources to motivate principals to share resources with arbitrary users, to enforce priority in distributed systems, to provide flexible and rational limitations on the potential of an application, and to provide a lightweight structure to balance the workload over time and between devices. As proof of concept, we implement a structure software agents can use to discover and negotiate access to networked resources. The structure separates discovery, authentication, and consumption enforcement as separate orthogonal issues to give system designers flexibility.
Mobile agents represent informational and computational flow. We develop mechanisms that distributively allocate computation among mobile agents in two settings. The first models a situation where users collectively own networked computing resources and require priority enforcement. We extend the allocation mechanism to allow resource reservation to mitigate utility volatility. The second, more general model relaxes the ownership assumption. We apply our computational market to an open setting where a principal's chief concern is revenue maximization.
Our simulations compare the performance of market-based allocation policies to traditional policies and relate the cost of ownership and consumption separation. We observe that our markets effectively prioritize applications' performance, can operate under uncertainty and network delay, provide metrics to balance network load, and allow measurement of market-participation risk versus reservation-based computation.
In addition to allocation problems, we investigate resource selection to optimize execution time. The problem is NP-complete if the costs and latencies are constant. Both metrics' dependence on the chosen set complicates matters. We study how a greedy approach, a novel heuristic, and a shortest-constrained-path strategy perform in mobile-agent applications.
Market-based computational-resource allocation fertilizes applications where previously there was a dearth of motive for or means of cooperation. The rationale behind mobile-agent performance optimization is also useful for resource allocation in general distributed systems where an application has a sequence of dependent tasks or when data collection is expensive.
Copyright © 2001 by Jonathan L. Bredin.
PDF
(1002K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-408/
See also earlier version bredin:thesis.
Abstract: A mobile agent is an executing program that can migrate during execution from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. Mobile agents are particularly attractive in distributed information-retrieval applications. By moving to the location of an information resource, the agent can search the resource locally, eliminating the transfer of intermediate results across the network and reducing end-to-end latency. In this chapter, we first discuss the strengths of mobile agents, and argue that although none of these strengths are unique to mobile agents, no competing technique shares all of them. Next, after surveying several representative mobile-agent systems, we examine one specific information-retrieval application, searching distributed collections of technical reports, and consider how mobile agents can be used to implement this application efficiently and easily. Then we spend the bulk of the chapter describing two planning services that allow mobile agents to deal with dynamic network environments and information resources: (1) planning algorithms that let an agent choose the best migration path through the network, given its current task and the current network conditions, and (2) planning algorithms that tell an agent how to observe a changing set of documents in a way that detects changes as soon as possible while minimizing overhead. Finally, we consider the types of errors that can occur when information from multiple sources is merged and filtered, and argue that the structure of a mobile-agent application determines the extent to which these errors affect the final result.
Copyright © 1999 by Springer-Verlag.
gzipped Postscript
(196K)
|
PDF
(419K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/brewington:IR.ps.gz
Abstract: Recent experiments and analysis suggest that there are about 800 million publicly-indexable web pages. However, unlike books in a traditional library, web pages continue to change even after they are initially published by their authors and indexed by search engines. This paper describes preliminary data on and statistical analysis of the frequency and nature of web page modifications. Using empirical models and a novel analytic metric of "up-to-dateness", we estimate the rate at which web search engines must re-index the web to remain current.
Copyright © 2000 by W3C.
HTML
Abstract: Because information depreciates over time, keeping Web pages current presents new design challenges. This article quantifies what "current" means for Web search engines and estimates how often they must reindex the Web to keep current with its changing pages and structure.
Most information-from a newspaper story to a temperature sensor measurement to a Web page-is dynamic. When monitoring an information source, when do our previous observations become stale and need refreshing? How can we schedule these refresh operations to satisfy a required level of currency without violating resource constraints-such as band-width or computing limitations on how much data can be observed in a given time?
The authors investigate the trade-offs involved in monitoring dynamic information sources and discuss the Web in detail, estimating how fast documents change and exploring what constitutes a "current" Web index. For a simple class of Web-monitoring systems-search engines-they combine their idea of currency with actual measured data to estimate revisit rates.
Copyright © 2000 by IEEE.
gzipped Postscript
(227K)
|
PDF
(417K)
|
HTML
Abstract: Many ``ubiquitous computing'' applications need a constant flow of information about their environment to be able to adapt to their changing context. To support these ``context-aware'' applications we propose a graph-based abstraction for collecting, aggregating, and disseminating context information. The abstraction models context information as events, produced by sources and flowing through a directed acyclic graph of event-processing operators and delivered to subscribing applications. Applications describe their desired event stream as a tree of operators that aggregate low-level context information published by existing sources into the high-level context information needed by the application. The operator graph is thus the dynamic combination of all applications' subscription trees.
In this paper, we motivate and describe our graph abstraction, and discuss a variety of critical design issues. We also sketch our Solar system, an implementation that represents one point in the design space for our graph abstraction.
Copyright © 2002 by IEEE.
gzipped Postscript
(314K)
|
PDF
(102K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:abstraction.ps.gz
See also earlier version chen:abstraction-tr.
Abstract: Many ``ubiquitous computing'' applications need a constant flow of information about their environment to be able to adapt to their changing context. To support these ``context-aware'' applications we propose a graph-based abstraction for collecting, aggregating, and disseminating context information. The abstraction models context information as events, produced by sources and flowing through a directed acyclic graph of event-processing operators and delivered to subscribing applications. Applications describe their desired event stream as a tree of operators that aggregate low-level context information published by existing sources into the high-level context information needed by the application. The operator graph is thus the dynamic combination of all applications' subscription trees.
In this paper, we motivate and describe our graph abstraction, and discuss a variety of critical design issues. We also sketch our Solar system, an implementation that represents one point in the design space for our graph abstraction.
Copyright © 2002 by the authors.
gzipped Postscript
(72K)
|
PDF
(89K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-420/
See also later version chen:abstraction.
Abstract: Ubiquitous-computing environments are heterogeneous and volatile in nature. Systems that support ubicomp applications must be self-managed, to reduce human intervention. In this paper, we present a general service that helps distributed software components to manage their dependencies. Our service proactively monitors the liveness of components and recovers them according to supplied policies. Our service also tracks the state of components, on behalf of their dependents, and may automatically select components for the dependent to use based on evaluations of customized functions. We believe that our approach is flexible and abstracts away many of the complexities encountered in ubicomp environments. In particular, we show how we applied the service to manage dependencies of context-fusion operators and present some experimental results.
Copyright © 2004 by IEEE.
PDF
(31K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:dependency.pdf
See also earlier version chen:dependency-tr.
Abstract: Ubiquitous-computing environments are heterogeneous and volatile in nature. Systems that support ubicomp applications must be self-managed, to reduce human intervention. In this paper, we present a general service that helps distributed software components to manage their dependencies. Our service proactively monitors the liveness of components and recovers them according to supplied policies. Our service also tracks the state of components, on behalf of their dependents, and may automatically select components for the dependent to use based on evaluations of customized functions. We believe that our approach is flexible and abstracts away many of the complexities encountered in ubicomp environments. In particular, we show how we applied the service to manage dependencies of context-fusion operators and present some experimental results.
Copyright © 2004 by the authors.
PDF
(101K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-495/
See also later version chen:dependency.
Abstract: In this paper we motivate a Context Fusion Network (CFN), an infrastructure model that allows context-aware applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information fusion graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. Multiple graphs by different applications inter-connect with each other to form a global graph. A key advantage of a CFN is re-usability, both at code-level and instance-level, facilitated by operator composition. We designed and implemented a distributed CFN system, Solar, which maps the logical operator graph representation onto a set of overlay hosts. In particular, Solar meets the challenges inherent to heterogeneous and volatile ubicomp environments. By abstracting most complexities into the infrastructure, we believe Solar facilitates both the development and deployment of context-aware applications. We present the operator composition model, basic services of the Solar overlay network, and programming support for the developers. We also discuss some applications built with Solar and the lessons we learned from our experience.
Copyright © 2004 by IEEE.
PDF
(103K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:fusenet.pdf
Abstract: This paper presents the ``Solar'' system framework that allows resources to advertise context-sensitive names and for applications to make context-sensitive name queries. The heart of our framework is a small specification language that allows composition of ``context-processing operators'' to calculate the desired context. Resources use the framework to register and applications use the framework to lookup context-sensitive name descriptions. The back-end system executes these operators and constantly updates the context values, adjusting advertised names and informing applications about changes. We report experimental results from a prototype, using a modified version of the Intentional Naming System (INS) as the core directory service.
Copyright © 2003 by IEEE.
gzipped Postscript
(343K)
|
PDF
(230K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:naming.pdf
Abstract: Reactive or proactive mobile applications require continuous monitoring of their physical and computational environment to make appropriate decisions in time. These applications need to monitor data streams produced by sensors and react to changes. When mobile sensors and applications are connected by low-bandwidth wireless networks, sensor data rates may overwhelm the capacity of network links or of the applications. In traditional networks and distributed systems, flow-control and congestion-control policies either drop data or force the sender to pause. When the data sender is sensing the physical environment, however, a pause is equivalent to dropping data. Arbitrary data drops are not necessarily acceptable to the reactive mobile applications receiving sensor data. Data distribution systems must support application-specific policies that selectively drop data objects when network or application buffers overflow.
In this paper we present a data-dissemination service, PACK, which allows applications to specify customized data-reduction policies. These policies define how to discard or summarize data flows wherever buffers overflow on the dissemination path, notably at the mobile hosts where applications often reside. The PACK service provides an overlay infrastructure to support mobile data sources and sinks, using application-specific data-reduction policies where necessary along the data path. We uniformly apply the data-stream ``packing'' abstraction to buffer overflow caused by network congestion, slow receivers, and the temporary disconnections caused by end-host mobility. We demonstrate the effectiveness of our approach with an application example and experimental measurements.
Copyright © 2004 by the authors.
PDF
(262K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-488/
See also later version chen:pack.
Abstract: Emerging pervasive computing technologies transform the way we live and work by embedding computation in our surrounding environment. To avoid increasing complexity, and allow the user to concentrate on her tasks, applications in a pervasive computing environment must automatically adapt to their changing phcontext, including the user state and the physical and computational environment in which they run. Solar is a middleware platform to help these ``context-aware'' applications aggregate desired context from heterogeneous sources and to locate environmental services depending on the current context. By moving most of the context computation into the infrastructure, Solar allows applications to run on thin mobile clients more effectively. By providing an open framework to enable dynamic injection of context processing modules, Solar shares these modules across many applications, reducing application development cost and network traffic. By distributing these modules across network nodes and reconfiguring the distribution at runtime, Solar achieves parallelism and online load balancing.
Copyright © 2002 by the authors.
gzipped Postscript
(192K)
|
PDF
(89K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:pervasive.pdf
See also earlier version chen:pervasive-tr.
Abstract: Emerging pervasive computing technologies transform the way we live and work by embedding computation in our surrounding environment. To avoid increasing complexity, and allow the user to concentrate on her tasks, applications must automatically adapt to their changing phcontext, the physical and computational environment in which they run. To support these ``context-aware'' applications we propose a graph-based abstraction for collecting, aggregating, and disseminating context information. The abstraction models context information as phevents, which are produced by phsources, flow through a directed acyclic graph of event-processing phoperators, and are delivered to subscribing applications. Applications describe their desired event stream as a tree of operators that aggregate low-level context information published by existing sources into the high-level context information needed by the application. The phoperator graph is thus the dynamic combination of all applications' subscription trees. In this paper, we motivate our graph abstraction by discussing several applications under development, sketch the architecture of our system (``Solar'') that implements our abstraction, report some early experimental results from the prototype, and outline issues for future research.
Copyright © 2002 by the authors.
gzipped Postscript
(284K)
|
PDF
(93K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-421/
See also later version chen:pervasive.
Abstract: As we embed more computers into our daily environment, ubiquitous computing promises to make them less noticeable and to avoid information overload. We see, however, few ubiquitous applications that are able to adapt to the dynamics of user, physical, and computational context. The challenge is to allow applications flexible access to these sources, and yet scale to thousands of devices and sensors. In this paper we introduce our proposed infrastructure, Solar. In Solar, information sources produce events. Applications may subscribe to interesting sources directly, or they may instantiate and subscribe to a tree of operators that filter, transform, merge and aggregate events. Applications use a subscription language to describe the tree, based on event streams registered in a context-sensitive naming hierarchy. Solar is flexible: modular operators can be composed to produce new event streams. Solar is scalable: it distributes operators across hosts called Planets, and it re-uses common subgraphs in the operator network.
Copyright © 2001 by the authors.
gzipped Postscript
(104K)
|
PDF
(94K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/chen:solar.ps.gz
Abstract: As we embed more computers into our daily environment, ubiquitous computing promises to make them less noticeable and help to prevent information overload. We see, however, few ubiquitous applications that are able to adapt to the dynamics of user, physical, and computational context. We believe that there are two challenges causing this lack of ubiquitous applications: there is no flexible and scalable way to support information collection and dissemination in a ubiquitous and mobile environment, and there is no general approach to building adaptive applications given heterogeneous contextual information. We propose a system infrastructure, Solar, to meet these challenges. Solar uses a subscription-based operator graph abstraction and allows dynamic composition of stackable operators to manage ubiquitous information sources. After developing a set of diverse adaptive applications, we expect to identify fundamental techniques for context-aware adaptation. Our expectation is that Solar's end-to-end support for information collection, dissemination, and utilization will make it easy to build adaptive applications for a ubiquitous mobile environment with many users and devices.
Copyright © 2001 by the authors.
gzipped Postscript
(174K)
|
PDF
(238K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-397/
Abstract: The complexity of developing context-aware pervasive-computing applications calls for distributed software infrastructures that assist applications to collect, aggregate, and disseminate contextual data. In this dissertation, we present a Context Fusion Network (CFN), called Solar, which is built with a scalable and self-organized service overlay. Solar is flexible and allows applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information flow graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. To manage application-specified operators on a set of overlay nodes called Planets, Solar provides several unique services such as application-level multicast with policy-driven data reduction to handle buffer overflow, context-sensitive resource discovery to handle environment dynamics, and proactive monitoring and recovery to handle common failures. Experimental results show that these services perform well on a typical DHT-based peer-to-peer routing substrate. In this dissertation, we also discuss experience, insights, and lessons learned from our quantitative analysis of the input sensors, a detailed case study of a Solar application, and development of other applications in different domains.
Copyright © 2004 by the author.
PDF
(2293K)
URL: http://cmc.cs.dartmouth.edu/papers/chen:thesis.pdf
See also later version chen:thesis-tr.
Abstract: The complexity of developing context-aware pervasive-computing applications calls for distributed software infrastructures that assist applications to collect, aggregate, and disseminate contextual data. In this dissertation, we present a Context Fusion Network (CFN), called Solar, which is built with a scalable and self-organized service overlay. Solar is flexible and allows applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information flow graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. To manage application-specified operators on a set of overlay nodes called Planets, Solar provides several unique services such as application-level multicast with policy-driven data reduction to handle buffer overflow, context-sensitive resource discovery to handle environment dynamics, and proactive monitoring and recovery to handle common failures. Experimental results show that these services perform well on a typical DHT-based peer-to-peer routing substrate. In this dissertation, we also discuss experience, insights, and lessons learned from our quantitative analysis of the input sensors, a detailed case study of a Solar application, and development of other applications in different domains.
Copyright © 2004 by the author.
PDF
(2594K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-514/
See also earlier version chen:thesis.
Abstract: A usable and efficient resource-management system has been created for use with D'Agents. The software dynamically negotiates a price rate for CPU time, using the competitive bids of mobile agents that offer currency in return for fast computation. The system allows mobile agents to plan their expenditures across many hosts while minimizing the time needed for their tasks. The ability to price CPU time opens the door for service owners to be compensated for the computation consumed by agents and provides an incentive for servers to allow anonymous agents. We discuss the theoretical background which makes a CPU market system possible and the performance of the D'Agents market system.
Copyright © 2000 by the authors.
gzipped Postscript
(71K)
|
PDF
(228K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-375/
Abstract: This paper introduces the application of a sensor network to navigate a flying robot. We have developed distributed algorithms and efficient geographic routing techniques to incrementally guide one or more robots to points of interest based on sensor gradient fields, or along paths defined in terms of Cartesian coordinates. These include a distributed robot-assisted localization algorithm, a distributed communication-assisted path computation algorithm for the robot and a distributed communication-assisted navigation algorithm to guide the robot. The robot itself is an integral part of the localization process which establishes the positions of sensors which are not known a priori. The sensor network is an integral part of the computation and storage of the robot's path. We use this system in a large-scale outdoor experiment with Mote sensors to guide an autonomous helicopter along a path encoded in the network. We also describe how a human can be guided using a simple handheld device that interfaces to this same environmental infrastructure.
Copyright © 2003 by Springer-Verlag.
PDF
(491K)
URL: http://cmc.cs.dartmouth.edu/papers/corke:flying.pdf
Abstract: In this paper we investigate a problem arising in decentralized registration of sensors. The application we consider involves a heterogeneous collection of sensors-- some sensors have on-board Global Positioning System (GPS) capabilities while others do not. All sensors have wireless communications capability but the wirele ss communication has limited effective range. Sensors can communicate only with other sensors that are within a fixed distance of each other. Sensors with GPS capability are self-registering. Sensors without GPS capability are less expensive and smaller but they must compute estimates of their location using estimates of the distances between themselves and other sensors within their radio range. GPS-less sensors may be several radio hops away from GPS-capable sensors so registration must be inferred transitively. Our approach to solving this registration problem involves minimizing a global potential or penalty function by using only local information, determined by the radio range, available to each sensor. The algorithm we derive is a special case of a more general methodology we have developed called "Emergence Engineering".
Copyright © 2003 by IEEE.
PDF
(128K)
URL: http://cmc.cs.dartmouth.edu/papers/crespi:registration.pdf
Abstract: In most working and proposed multiagent systems, the problem of identifying and locating agents that can provide specific services is a major problem of concern. A broker or matchmaker service is often proposed as a solution. These systems use keywords drawn from application domain ontologies to specify agent service, usually framed within some some sort of knowledge representation language . However, we believe that keywords and ontologies cannot be defined and interpreted precisely enough to make broking or matchmaking among agents sufficiently robust in a truly distributed, heterogeneous , multiagent computing environment. This creates matching conflicts between a client agents' requested functionality and a service agents' actual functionality . We propose a new form of interagent communication, called functional validation, specially designed to solve such matching conflicts. In this paper we introduce the functional validation concept, analyze the possible situations that can arise in validation problems and formalize the mathematical framework around which further work can be done.
Copyright © 1999 by AAAI Press.
gzipped Postscript
(856K)
|
PDF
(125K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:functional.ps.gz
Abstract: The development of the World Wide Web has changed the way that we think about information. Information on the web is distributed, updates are made asynchronously and resources come and go online without centralized control. Global networking will similarly change the way we think about and perform computation. Grid computing refers to computing in a distributed networked environment in which computing and data resources are located throughout a network. Grid computing is enabled by an infrastructure that allows users to locate computing resources and data products dynamically during a computation. In order to locate resources dynamically in a grid computation, a grid application program consults a broker or matchmaker agent that uses keywords and ontologies to specify grid services. However, we believe that keywords and ontologies cannot be defined or interpreted precisely enough to make brokering and matchmaking between agents sufficiently robust in a truly distributed, heterogeneous computing environment. To this end, we introduce the concept of functional validation. Functional validation goes beyond the symbolic negotiation level of brokering and matchmaking, to the level of validating actual functional performance of grid services. In this paper, we present the functional validation problem in grid computing and apply basic machine learning theory such as PAC learning and Chernoff bounds to solve the sample size problem that arises. Furthermore, in order to reduce network traffic and speedup the validation process, we describe the use of Dartmouth D'Agents technology to implement a general mobile functional validation agent system which can be integrated into a grid computing infrastructures as a standard grid service.
Copyright © 1999 by Allerton Conference.
gzipped Postscript
(132K)
|
PDF
(1361K)
URL: http://agent.cs.dartmouth.edu/papers/cybenko:grid.ps.gz
Abstract: National-scale critical infrastructure protection depends on many processes: intelligence gathering, analysis, interdiction, detection, response and recovery, to name a few. These processes are typically carried out by different individuals, agencies and industry sectors. Many new threats to national infrastructure are arising from the complex couplings that exist between advanced information technologies (telecommunications and internet), physical components (utilities), human services (health, law enforcement, emergency management) and commerce (financial services, logistics). Those threats arise and evolve at a rate governed by human intelligence and innovation, on internet timeor infrastructure protection must operate on the same time scale to be effective. To achieve this, a new approach to integrating, coordinating and managing infrastructure protection must be deployed. To this end, we describe the key ingredients of an Infrastructure Web. The Infrastructure Web is a web-like architecture for decentralized monitoring and managing critical national infrastructures.
gzipped Postscript (209K) | PDF (1122K)
URL: http://agent.cs.dartmouth.edu/CoABS/papers/cybenko:infrastructure-web.ps.gz
Copyright © 1999 by IFORS.
No online copy available.
Abstract: Mobile agents are programs that can migrate from machine to machine in a network of computers and have complete control over their movement. Since the performance space of mobile agents has not been characterized fully, assessing the effectiveness of using mobile agents over a traditional client/server approach currently requires implementing an agent system and running time-consuming experiments.
This report presents a simple mobile-agent simulation that can provide quick information on the performance and scalability of a generic information retrieval (IR) mobile-agent system under different network configurations. The simulation is built using the DaSSF and DaSSFNet frameworks, resulting in high performance and great configuration flexibility. This report also implements a real D'Agents mobile-agent IR system, measuring the performance of the system. A comparison of these real-world performance results and those given by the simulation suggest that the simulation has good accuracy in predicting the scalability of a mobile-agent system. Thus this report argues that simulation provides a good way to quickly assess the performance and scalability of an IR mobile-agent system under different network configurations.
Copyright © 2004 by the author.
PDF
(361K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2004-499/
Abstract: A mobile agent is an executing program that can migrate, at times of its own choosing, from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. In this chapter, we first make the case for mobile agents, discussing six strengths of mobile agents and the applications that benefit from these strengths. Although none of these strengths are unique to mobile agents, no competing technique shares all six. In other words, a mobile-agent system provides a single general framework in which a wide range of distributed applications can be implemented efficiently and easily. We then present a representative cross-section of current mobile-agent systems.
Copyright © 2002 by the authors.
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-365/
See also earlier version gray:motivation-tr.
Abstract: A mobile agent is an executing program that can migrate, at times of its own choosing, from machine to machine in a heterogeneous network. On each machine, the agent interacts with stationary service agents and other resources to accomplish its task. In this chapter, we first make the case for mobile agents, discussing six strengths of mobile agents and the applications that benefit from these strengths. Although none of these strengths are unique to mobile agents, no competing technique shares all six. In other words, a mobile-agent system provides a single general framework in which a wide range of distributed applications can be implemented efficiently and easily. We then present a representative cross-section of current mobile-agent systems.
Copyright © 2000 by the authors.
gzipped Postscript
(231K)
|
PDF
(405K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-365/
See also later version gray:motivation.
Abstract: Ideally soldiers in the field would have portable computing devices, which, connected with a wireless network, would provide access to military databases, terrain maps, and other soldiers. In this report and the associated invited talk, the author presents some routing and mobilecode technologies that have been developed to support soldiers in the field, as well as the highly intelligent network-sensing and planning agents that will be needed to fully solve the networking problems.
Copyright © 2000 by IEEE.
gzipped Postscript
(148K)
|
PDF
(711K)
URL: http://cmc.cs.dartmouth.edu/papers/gray:overview.ps.gz
Abstract: Building applications with mobile agents often reduces the bandwidth required for the application, and improves performance. The cost is increased server workload. There are, however, few studies of the scalability of mobile-agent systems. We present scalability experiments that compare four mobile-agent platforms with a traditional client/server approach. The four mobile-agent platforms have similar behavior, but their absolute performance varies with underlying implementation choices. Our experiments demonstrate the complex interaction between environmental, application, and system parameters.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(361K)
|
PDF
(325K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:scalability.ps.gz
See also earlier version gray:scalability-tr.
Abstract: Mobile agents are programs that can jump from host to host in the network, at times and to places of their own choosing. Many groups have developed mobile-agent software platforms, and several mobile-agent applications. Experiments show that mobile agents can, among other things, lead to faster applications, reduced bandwidth demands, or less dependence on a reliable network connection. There are few if any studies of the scalability of mobile-agent servers, particularly as the number of clients grows. We present some recent performance and scalability experiments that compare three mobile-agent platforms with each other and with a traditional client/server approach. The experiments show that mobile agents often outperform client/server solutions, but also demonstrate the deep interaction between environmental and application parameters. The three mobile-agent platforms have similar behavior but their absolute performance varies with underlying implementation choices.
Copyright © 2001 by the authors.
gzipped Postscript
(812K)
|
PDF
(1179K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-386/
See also later version gray:scalability.
Abstract: Mobile-agent systems must address three security issues: protecting an individual machine, protecting a group of machines, and protecting an agent. In this chapter, we discuss these three issues in the context of D'Agents, a mobile-agent system whose agents can be written in Tcl, Java and Scheme. (D'Agents was formerly known as Agent Tcl.) First we discuss mechanisms existing in D'Agents for protecting an individual machine: (1) cryptographic authentication of the agent's owner, (2) resource managers that make policy decisions based on the owner's identity, and (3) secure execution environments for each language that enforce the decisions of the resource managers. Then we discuss our planned market-based approach for protecting machine groups. Finally we consider several (partial) solutions for protecting an agent from a malicious machine.
Copyright © 1998 by Springer-Verlag.
gzipped Postscript
(267K)
|
PDF
(862K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:security-book.ps.gz
See also earlier version gray:security.
Abstract: D'Agents is a mobile-agent system that is used primarily for information-retrieval applications. In this paper, we first examine two such applications, where mobile agents greatly simplify the task of providing efficient but application-specific access to remote information resources. Then we describe the D'Agents system, which supports multiple languages, Tcl, Java and Scheme, and strong mobility for Tcl and Java. After considering the D'Agents implementation, we present some recent performance and scalability experiments that compare D'Agent mobile agents with traditional client/server approaches. The experiments show that mobile agents often outperform client/server solutions, but also demonstrate the deep interaction between environmental and application parameters. The mobile-agent performance space as a whole is complex, and significant additional experiments are needed to characterize it. Finally, after discussing current and future experiments, we explore the differences between D'Agents and other mobile-agent systems.
Copyright © 2002 by John Wiley \& Sons.
gzipped Postscript
(145K)
|
PDF
(492K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:spe.ps.gz
Abstract: Mobile agents are an increasingly popular paradigm and in recent years there has been a proliferation of mobile-agent systems. These systems are, however, largely incompatible with each other. In particular, agents cannot migrate to a host that runs a different mobile-agent system. Prior approaches to interoperability have tried to force agents to use a common API and so far none have succeeded. This goal led to our efforts to develop mechanisms that support dynamic runtime interoperability of mobile-agent systems. This paper describes the Grid Mobile-Agent System, which allows agents to migrate to different mobile-agent systems.
Copyright © 2002 by Springer-Verlag.
gzipped Postscript
(309K)
|
PDF
(80K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/grimstrup:gmas.pdf
Abstract: Mobile agents are an increasingly popular paradigm, and in recent years there has been a proliferation of mobile-agent systems. These systems are, however, largely incompatible with each other. In particular, agents cannot migrate to a host that runs a different mobile-agent system. Prior approaches to interoperability have tried to force agents to use a common API, and so far none have succeeded. Our goal, summarized in the catch phrase ``Write Once, Move Anywhere,'' led to our efforts to develop mechanisms that support dynamic runtime interoperability of mobile-agent systems. This paper describes the Grid Mobile-Agent System, which allows agents to migrate to different mobile-agent systems.
Copyright © 2001 by the authors.
gzipped Postscript
(135K)
|
PDF
(218K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-411/
Abstract: In order to achieve interoperability among heterogeneous systems, markup languages such as XML and DAML are being used to describe distributed systems and data. The ability to successfully interoperate based on semantic markup depends on the ability to create, use and manage shared ontologies of concepts and their interrelationships. Specifically, communicating systems in a networked environment have to achieve a certain level of semantic agreement for them to understand and process exchanged data. A challenging question is how deep the semantic agreement has to be in order to satisfy the communication needs in an environment. Additionally, what is the markup complexity resulting from pursuing that depth of semantic agreement? This paper introduces the concept of semantic depth and markup complexity and proposes models to measure the markup complexity. Furthermore, it is shown that markup complexity can be reduced by employing hierarchical ontologies after partitioning the domain into smaller sub-domains.
Copyright © 2003 by IEEE.
PDF
(275K)
URL: http://agent.cs.dartmouth.edu/papers/jiang:complexity.pdf
Copyright © 1999 by IFAC.
PDF
(1458K)
URL: http://agent.cs.dartmouth.edu/papers/jiang:convergence.pdf
Abstract: Interest in large-scale sensor networks for both civilian and military applications is burgeoning. The deployment of such networks will require new approaches in resource discovery, query processing and data routing. This paper presents a framework and some analytic results for query satisfaction and data routing in networks consisting of clients, sensors and data filtering/fusion servers. In this model, multiple clients pose queries that are satisfied by processing a set of sensor data streams through a set of filters or fuselets. Fuselets are lightweight data fusion algorithms that can be deployed in a network environment. The queries can have common subexpressions (sub-queries) that should be reused by multiple clients if possible and appropriate. Moreover, effective routing of data streams from sensors to clients requires routing the streams through network nodes that can implement the required filtering/fusion operations. We formulate these problems quantitatively and propose a dynamic programming based solution using sensor-fuselet location and performance tables. The framework is preliminary in that many details and variations are abstracted or ignored. However, at the end of the paper we discuss several directions that can be explored to make these preliminary results more relevant to real scenarios.
Copyright © 2002 by IEEE.
PDF
(183K)
URL: http://cmc.cs.dartmouth.edu/papers/cybenko:query-routing.pdf
Abstract: Recent advances in wireless communication and microelectronics have enabled the development of low-cost sensor devices leading to interest in large-scale sensor networks for military applications. Sensor networks consist of large numbers of networked sensors that can be dynamically deployed and used for tactical situational awareness. One critical challenge is how to dynamically integrate these sensor networks with information fusion processes to support real-time sensing, exploitation and decision-making in a rich tactical environment. In this paper, we describe our work on an extensible prototype to address the challenge. The prototype and its constituent technologies provide a proof-of-concept that demonstrates several fundamental new approaches for implementing next generation battlefield information systems. Many cutting-edge technologies are used to implement this system, including semantic web, web services, peer-to-peer network and content-based routing. This prototype system is able to dynamically integrate various distributed sensors and multi-level information fusion services into new applications and run them across a distributed network to support different mission goals. Agent technology plays a role in two fundamental ways: resources are described, located and tasked using semantic descriptions based on ontologies and semantic services; tracking, fusion and decision-making logic is implemented using agent objects and semantic descriptions as well.
Copyright © 2003 by SPIE.
PDF
(290K)
URL: http://agent.cs.dartmouth.edu/papers/jiang:tactical.pdf
Abstract: We develop a network of distributed mobile sensor systems as a solution to the emergency response problem. The mobile sensors are inside a building and they form a connected ad-hoc network. We discuss cooperative localization algorithms for these nodes. The sensors collect temperature data and run a distributed algorithm to assemble a temperature gradient. The mobile nodes are controlled to navigate using this temperature gradient. We also discuss how such networks can assist human users to find an exit. We have conducted an experiment to at a facility used to train firefighters to understand the environment and to test component technology. Results from experiments at this facility as well as simulations are presented here.
Copyright © 2003 by Sage Publications.
PDF
(384K)
URL: http://cmc.cs.dartmouth.edu/papers/kantor:team.pdf
Abstract: The field of mobile agents should shift its emphasis toward mobile code, in all its forms, rather than continue focusing on mobile agents. The development of modular components will help application designers take advantage of code mobility without having to rewrite their applications to fit in monolithic, mobile agent systems.
Copyright © 2002 by IEEE.
gzipped Postscript
(435K)
|
PDF
(488K)
|
HTML
See also earlier version kotz:dwta-tr.
Abstract: During a discussion in September 2000 the authors examined the future of research on mobile agents and mobile code. (A mobile agent is a running program that can move from host to host in network at times and to places of its own choosing.) In this paper we summarize and reflect on that discussion. It became clear that the field should shift its emphasis toward mobile code, in all its forms, rather than to continue its narrow focus on mobile agents. Furthermore, we encourage the development of modular components, so that application designers may take advantage of code mobility without needing to rewrite their application to fit in a monolithic mobile-agent system. There are many potential applications that may productively use mobile code, but there is no ``killer application'' for mobile agents. Finally, we note that although security is an important and challenging problem, there are many applications and environments with security requirements well within the capability of existing mobile-code and mobile-agent frameworks.
Copyright © 2002 by the authors.
gzipped Postscript
(1520K)
|
PDF
(205K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-415/
See also later version kotz:dwta.
Abstract: Use of the Internet has exploded in recent years with the appearance of the World-Wide Web. In this paper, we show how current technological trends necessarily lead to a system based substantially on mobile code, and in many cases, mobile agents. We discuss several technical and non-technical hurdles along the path to that eventuality. Finally, we predict that, within five years, nearly all major Internet sites will be capable of hosting and willing to host some form of mobile agents.
Copyright © 1999 by the authors.
gzipped Postscript
(113K)
|
PDF
(136K)
|
HTML
See also later version kotz:future2.
Abstract: Use of the Internet has exploded in recent years with the appearance of the World-Wide Web. In this paper, we show how current technological trends may lead to a system based substantially on mobile code, and in many cases, mobile agents. We discuss several technical and non-technical hurdles along the path to that eventuality. It seems likely that, within a few years, nearly all major Internet sites will be capable of hosting and willing to host some form of mobile code or mobile agents.
Copyright © 1999 by the authors.
gzipped Postscript
(109K)
|
PDF
(104K)
|
HTML
See also earlier version kotz:future.
Abstract: Wireless networks are an ideal environment for mobile agents, since their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources that they need to use. Furthermore, client-specific data transformations can be moved across the wireless link and run on a wired gateway server, reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents in a data-filtering application where numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from filtering experiments conducted during a U.S. Navy Fleet Battle Experiment (FBE) to explore the model's implications.
Copyright © 2002 by Kluwer Academic Publishers.
gzipped Postscript
(281K)
|
PDF
(270K)
URL: http://doi.acm.org/10.1145/506882.506889
See also earlier version kotz:model-tr2.
Abstract: Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from our own experiments to explore the model's implications.
Copyright © 2000 by ACM.
gzipped Postscript
(92K)
|
PDF
(201K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/kotz:model.ps.gz
See also earlier version kotz:model-tr.
See also later version kotz:model-tr2.
Abstract: Wireless networks are an ideal environment for mobile agents, because their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources they need to use. Furthermore, client-specific data transformations can be moved across the wireless link, and run on a wired gateway server, with the goal of reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents to support a data-filtering application, in which numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from our own experiments to explore the model's implications.
Copyright © 2000 by the authors.
gzipped Postscript
(309K)
|
PDF
(383K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-366/
See also later version kotz:model.
Abstract: Wireless networks are an ideal environment for mobile agents, since their mobility allows them to move across an unreliable link to reside on a wired host, next to or closer to the resources that they need to use. Furthermore, client-specific data transformations can be moved across the wireless link and run on a wired gateway server, reducing bandwidth demands. In this paper we examine the tradeoffs faced when deciding whether to use mobile agents in a data-filtering application where numerous wireless clients filter information from a large data stream arriving across the wired network. We develop an analytical model and use parameters from filtering experiments conducted during a U.S. Navy Fleet Battle Experiment (FBE) to explore the model's implications.
Copyright © 2000 by the authors.
gzipped Postscript
(102K)
|
PDF
(199K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-377/
See also earlier version kotz:model.
See also later version kotz:jmodel.
Abstract: In this paper, we introduce three new distributed routing algorithms in sensor networks: a distributed minimal power algorithm, a distributed max-min power algorithm, and the distributed max-min $zP_min$ power-aware algorithm. The first two algorithms are used to define the third, although they are very interesting and useful in their own right for applications where the optimization criterion is the minimum power, respectively the maximum residual power. By running those algorithms, the nodes in the network reduce the communication by adding a waiting time prior to each broadcast. In this way, some of the messages that travel along sub-optimal paths are suppressed. Only the messages that travel along the best paths end up being broadcast.
Copyright © 2003 by IEEE.
Postscript
gzipped Postscript
(78K)
|
PDF
(127K)
Abstract: An ad-hoc network is formed by a group of mobile hosts upon a wireless network interface. Previous research in communication in ad-hoc networks has concentrated on routing algorithms which are designed for fully connected networks. The traditional approach to communication in a disconnected ad-hoc network is to let the mobile computer wait for network reconnection passively. This method may lead to unacceptable transmission delays. We propose an approach that guarantees message transmission in minimal time. In this approach, mobile hosts actively modify their trajectories to transmit messages. We develop algorithms that minimize the trajectory modifications under two different assumptions: (a) the movements of all the nodes in the system are known and (b) the movements of the hosts in the system are not known.
Copyright © 2003 by Academic Press.
PDF
(230K)
URL: http://cmc.cs.dartmouth.edu/papers/li:jpdc.pdf
See also earlier version li:ad-hoc.
Abstract: A self-reconfiguring sensor network consists of many sensors that have the ability to self-configure by turning themselves on and off. This kind of self-reconfiguration results in power savings and extends the lifetime of the network. In this paper we present a formulation for the problem of adapting a sensor network to the environment and the task. We develop distributed algorithms for self-reconfiguring sensor networks that respond to tracking a target and directing a target through a region.
Copyright © 2003 by ACM.
PDF
(438K)
URL: http://doi.acm.org/10.1145/881978.881995
See also earlier version li:mobicom02poster.
Abstract: A self-reconfiguring sensor network consists of many sensors that have the ability to self-configure by turning themselves on and off. This kind of self-reconfiguration results in power savings and extends the lifetime of the network. In this paper we present a formulation for the problem of adapting a sensor network to the environment and the task. We develop distributed algorithms for self-reconfiguring sensor networks that respond to tracking a target and directing a target through a region.
Copyright © 2002 by ACM.
gzipped Postscript
(605K)
|
PDF
(438K)
URL: http://cmc.cs.dartmouth.edu/papers/li:mobicom02poster.ps.gz
See also later version li:mc2r03.
Abstract: An ad-hoc network is formed by a group of mobile hosts upon a wireless network interface. Previous research in communication in ad-hoc networks has concentrated on routing algorithms which are designed for fully connected networks. The traditional approach to communication in a disconnected ad-hoc network is to let the mobile computer wait for network reconnection passively. This method may lead to unacceptable transmission delays. We propose an approach that guarantees message transmission in minimal time. In this approach, mobile hosts actively modify their trajectories to transmit messages. We develop algorithms that minimize the trajectory modifications under two different assumptions: (a) the movements of all the nodes in the system are known and (b) the movements of the hosts in the system are not known.
Copyright © 2002 by IEEE.
gzipped Postscript
(91K)
|
PDF
(203K)
URL: http://cmc.cs.dartmouth.edu/papers/li:mobworkshop02.ps.gz
See also earlier version li:ad-hoc.
Abstract: We develop distributed algorithms for self-organizing sensor networks that respond to directing a target through a region. The sensor network models the danger levels sensed across its area and has the ability to adapt to changes. It represents the dangerous areas as obstacles. A protocol that combines the artificial potential field of the sensors with the goal location for the moving object guides the object incrementally across the network to the goal, while maintaining the safest distance to the danger areas. We give the analysis to the protocol and report on hardware experiments using a physical sensor network consisting of Mote sensors.
Copyright © 2003 by ACM.
gzipped Postscript
(3488K)
|
PDF
(862K)
URL: http://cmc.cs.dartmouth.edu/papers/li:navigation.ps.gz
Abstract: We develop distributed algorithms for self-reconfiguring sensor networks that respond to directing a target through a region. The sensor network models the danger levels sensed across its area and has the ability to adapt to changes. It represents the dangerous areas as obstacles. A protocol that combines the artificial potential field of the sensors with the goal location for the moving object guides the object incrementally across the network to the goal, while maintaining the safest distance to the danger areas. We report on hardware experiments using a physical sensor network consisting of Mote sensors.
Copyright © 2002 by the authors.
PDF
(381K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-435/
Abstract: This thesis considered the duality between two important issues in sensor network research: communication and mobility. We build on the infrastructure of power-aware communication and global clock synchronization and show the duality between communication and mobility can be achieved to enhance each other's quality and efficiency. First, sensor network provides a way to augment the environment for a variety of problems, including mobility-related problems such as robot navigation. By shifting some burden of the problem to the sensor network augmented environment, the new information embedded in the environment that can be obtained by a user on spot and in real time can help to solve problems more efficiently and realistically. Second, mobility can serve to achieve communication since mobility is very common in everyday life. It is useful to use the controlled mobility of the specialized communication nodes and free natural mobility to guarantee communication, reduce power consumption, and increase network capacity.
To build an infrastructure for sensor network, we focused on two problems: power-aware communication and clock synchronization. We gave several communication protocols to conserve the energy in sensor network communication, both on the scale of the whole network and on a single node. We showed that by carefully designed routing protocol and fine-tuned sleep/wakeup node schedule, much energy can be conserved. We also designed several protocols for global clock synchronization. The most interesting one is diffusion-based clock synchronization, which is a fault-tolerant and localized protocol.
The duality between communication and mobility was shown as follows. First, we showed that communication can be achieved by controlled mobility and natural mobility. We used active trajectory change to obtain guaranteed message delivery. Then we demonstrated that natural mobility can be used to help communication to conserve energy and overcome disconnection. Second, we showed in navigation application that communication can assist mobility. We gave communication protocols to support user guidance in a sensor network, refined the protocols by considering reducing network searching space, and explored a mobility coordination problem: task assignment in robotic network applications.
Copyright © 2004 by the author.
No online copy available.
Abstract: This paper discusses online power-aware routing in large wireless ad-hoc networks (especially sensor networks) for applications where the message sequence is not known. We seek to optimize the lifetime of the network. We show that online power-aware routing does not have a constant competitive ratio to the off-line optimal algorithm. We develop an approximation algorithm called $max$-$min$ $zP_min$ that has a good empirical competitive ratio. To ensure scalability, we introduce a second online algorithm for power-aware routing. This hierarchical algorithm is called zone-based routing. Our experiments show that its performance is quite good. Finally, we describe a distributed version of this algorithm that does not depend on any centralization.
Copyright © 2003 by Wiley Interscience.
PDF
(274K)
URL: http://cmc.cs.dartmouth.edu/papers/li:wcmc.pdf
See also earlier version li:power-aware.
Abstract: Pervasive-computing infrastructures necessarily collect a lot of context information to disseminate to their context-aware applications. Due to the personal or proprietary nature of much of this context information, however, the infrastructure must limit access to context information to authorized persons. In this paper we propose a new access-control mechanism for event-based context-distribution infrastructures. The core of our approach is based on a conservative information-flow model of access control, but users may express discretionary relaxation of the resulting access-control list (ACL) by specifying relaxation functions. This combination of automatic ACL derivation and user-specified ACL relaxation allows access control to be determined and enforced in a decentralized, distributed system with no central administrator or central policy maker. It also allows users to express their personal balance between functionality and privacy. Finally, our infrastructure allows access-control policies to depend on context-sensitive roles, allowing great flexibility.
We describe our approach in terms of a specific context-dissemination framework, the Solar system, although the same principles would apply to systems with similar properties.
Copyright © 2002 by the authors.
gzipped Postscript
(294K)
|
PDF
(141K)
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2002-422/
Abstract: This paper considers a sequencing problem which arises naturally in the scheduling of software agents. We are given n sites at which a certain task might be successfully performed. The probability of success is $p_i$ at the $i$th site and these probabilities are independent. Visiting site i and trying the task there requires time (or some other cost metric) $t_i$ whether successful or not. Latencies between sites $i$ and $j$ are $l_ij$, that is, the travel time between those two sites. Should the task be successfully completed at a site then any remaining sites do not need to be visited. The Travelling Agent Problem is to find the sequence which minimizes the expected time to complete the task. The general formulation of this problem is NP-Complete. However, if the latencies are constant we show that the problem can be solved in polynomial time by sorting the ratios $p_i/t_i$ according to decreasing value and visiting the sites in that order. This result then leads to an efficient algorithm when groups of sites form subnets in which latencies within a subnet are constant but can vary across subnets. We also study the case when there are deadlines for solving the problem in which case the goal is to maximize probability of success subject to satisfying the deadlines. Applications to mobile and intelligent agents are described.
Copyright © 2001 by Springer-Verlag.
gzipped Postscript
(71K)
|
PDF
(219K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:agent-plan.ps.gz