A separate page has the same paper list sorted alphabetically.
This page lists all of our papers that are relevant to the ActComm project. The papers are listed in original order.
The last update to this paper list was on Tue Aug 10 14:29:35 EDT 2004.
Abstract: This paper deals with tracking based on natural language messages. Of particular interest are messages generated by multiple human observers over extended periods of time. The tracking problem is to associate messages that are about the same object or phenomenon, create the most probable tracks based on those associations and finally make inferences about the situation. A key technical innovation of this work is the use of mature radar signal processing tracking methods, originally used for correlating radar sensor reports, in the domain of natural language processing and understanding for tracking applications. We believe that our results can be useful in several applications that involve tracking and correlation of natural language reports based on text semantics. Such applications include: 1) military situation awareness using human observations (such as land vehicle tracking); 2) maintenance planning using text-based reports; 3) analysis of computer intrusion detection reports; 4) customer service monitoring and tracking.
In this paper we describe our present implementation, called TextTrack. It uses the multiple hypothesis tracking (MHT) paradigm developed for multiple object tracking. TextTrack has a simple natural language frontend which does rudimentary parsing and analysis of short messages or reports. Messages are then assembled into maximum likelihood tracks as computed by an MHT algorithm. These tracks can be analyzed to estimate, for example, an entity's identity. We develop both Bayesian maximum likelihood and fuzzy logic approaches to the problem. In addition to presenting the basic ideas behind our system, we also develop analytic convergence results for one tracking scenario under very weak assumptions.
Copyright © 1997 by the authors.
No online copy available.
Abstract: We present and analyze the off-line star algorithm for clustering static information systems and the on-line star algorithm for clustering dynamic information systems. These algorithms organize a document collection into a number of clusters that is naturally induced by the collection via a computationally efficient cover by dense subgraphs. We further show a lower bound on the accuracy of the clusters produced by these algorithms as well as demonstrate that these algorithms are efficient (running times roughly linear in the size of the problem). Finally, we provide data from a number of experiments.
Copyright © 1999 by the authors.
Postscript
(2443K)
|
gzipped Postscript
(246K)
|
compressed Postscript
(356K)
|
PDF
(1231K)
URL: http://agent.cs.dartmouth.edu/papers/aslam:clustering.ps.gz
Abstract: In this paper we present a system for static and dynamic information organization and show our evaluations of this system on TREC data. We introduce the off-line and on-line star clustering algorithms for information organization. Our evaluation experiments show that the off-line star algorithm outperforms the single link and average link clustering algorithms. Since the star algorithm is also highly efficient and simple to implement, we advocate its use for tasks that require clustering, such as information organization, browsing, filtering, routing, topic tracking, and new topic detection.
Postscript (410K) | gzipped Postscript (167K) | compressed Postscript (207K) | PDF (287K)
URL: http://agent.cs.dartmouth.edu/papers/aslam:organization.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.
Postscript
(1137K)
|
gzipped Postscript
(145K)
|
compressed Postscript
(233K)
|
PDF
(390K)
URL: http://agent.cs.dartmouth.edu/papers/aslam:scalable.ps.gz
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.
No online copy available.
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.
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)
URL: http://ipsapp008.lwwonline.com/content/getfile/4476/22/2/abstract.htm
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.
Postscript
(460K)
|
gzipped Postscript
(157K)
|
compressed Postscript
(200K)
|
PDF
(149K)
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.
Postscript
(153K)
|
gzipped Postscript
(76K)
|
compressed Postscript
(87K)
|
PDF
(67K)
|
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.
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.
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.
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
(633K)
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 the authors.
gzipped Postscript
See also earlier version brewington:jdynamic.
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.
URL: http://csdl.computer.org/comp/mags/co/2000/05/r5052abs.htm
Abstract: This thesis proposal deals with optimal observation of large collections of changing objects. These objects can change at random times, so we cannot know the state of objects for times at which they are unobserved. The goal of an observer is to maintain acceptably accurate state estimates while minimizing observational cost. In the thesis work, our goals are to (1) create models for this type of system, (2) show how these models can be empirically constructed by actually observing real systems, and (3) develop efficient algorithms for the optimal allocation of observation resources within this framework. An example of this type of optimization arises in the observation of World Wide Web (WWW) documents by web search engines and related web software applications. Our initial results include (1) developing statistical models for such systems; (2) collection of empirical data about how web documents change; and (3) development of finite-horizon algorithms for maximizing an index's accuracy. Although the algorithms presented are intended for optimizing the recency of document indices, they are general enough to be applied to any dynamic collection of objects. The work is important and novel in that it takes proper account of the cost of observing, a concept that is crucial to monitoring problems in many communications systems.
Copyright © 1998 by Brian Brewington.
Postscript
(584K)
|
gzipped Postscript
(137K)
|
compressed Postscript
(179K)
|
PDF
(328K)
URL: http://agent.cs.dartmouth.edu/papers/brewington:observe.ps.gz
Abstract: Many modern information management tasks consist of an observer that must maintain current knowledge of a collection of changing information. The goal of this observer is to maintain acceptably accurate state estimates given limited observation resources, such as bandwidth, time, and storage. Good examples of such ``observation problems'' are found in any situation where bandwidth is limited and old observations become less useful over time. Two such examples are maintaining a search engine's index of the World Wide Web (WWW) and automated monitoring of multiple sensors. This thesis addresses the general observation problem by (1) devising a formal framework of what it means to be ``up-to-date'', (2) gathering empirical data about the web that allows us to apply this framework to an important setting, and (3) presenting algorithms for scheduling revisits to optimize formal performance measures. One year's worth of web page observations are analyzed to show how quickly and in what ways web pages change. The observations are used to estimate the distribution of web page change rates. Using this data as a model of the web we present and benchmark an algorithm for optimizing the observation of a set of web documents such that fewer changes go unnoticed. Our experiments on real search engines show that between 40 and 50% of results returned have been altered at least once since the search engine last observed them. Our algorithm can theoretically reduce these figures to between 36 and 44%, assuming that existing search engines currently use simple round-robin re-indexing strategies. These methods benefit the ``overworked'' observer much more than the one with ample bandwidth, and are general enough to be of use in a wide variety of monitoring tasks.
Copyright © 2000 by Brian Brewington.
Postscript
(16594K)
|
gzipped Postscript
(2683K)
|
compressed Postscript
(3871K)
|
PDF
(6518K)
URL: http://actcomm.dartmouth.edu/papers/brewington:thesis.ps.gz
Abstract: Most current computer applications are insensitive to changing conditions. With the growing demand for wireless. satellite, and other highly volatile computer communications networks, however, applications that are robust in the presence of network volatility must be designed and built. Network-robust applications are of great interest in military situations today, and we expect that interest to grow in industrial and eventually consumer environments as well. Mobile agents are one way to realize such applications, especially when used in a wireless environment. This article discusses issues and results related to the problem of making computer applications network-aware and reactive to changing network conditions. It contains a short overview of our work on mobile agents as well as a tutorial on network sensing from the agent perspective. Some prototypes of network-sensing systems and network aware mobile-agent applications are presented.
Copyright © 1998 by IEEE.
HTML
Abstract: This thesis presents some extensions to Mobile IP designed to better adapt this protocol to wireless networks. Specifically, the foreign-agent selection process is studied in depth and several selection criteria are proposed and implemented as extensions to an existing Mobile IP software package.
Wireless computer networks bring many advantages to those environments where network connectivity is required subject to constraints such as flexibility, affordability, and scalability. Wireless Local Area Networks (LANs) can be quickly installed in cases where traditional networks are not a feasible option for reasons like deployment time, cost, etc. Mobile IP is a protocol that provides support for roaming of computers between different networks. Each Mobile IP-enabled computer (mobile node) has a fixed home agent on its original network that keeps track of the mobile node's location at all times. The protocol specifies several different mechanisms for the mobile node to keep its home agent updated about its location every time it moves to another network. One of those mechanisms requires the mobile node to select a temporary gateway computer (foreign agent) at the visited network; this computer will serve as the mobile node's default router to the rest of the network and will forward location updates to the mobile node's home agent. In a wireless networking environment, mobile nodes will likely encounter situations in which there are several candidates from which to select a foreign agent. However, the Mobile IP protocol does not specify policies to use in such cases. The extensions developed in this thesis approach this problem. Performance measurements of Mobile IP-enabled wireless LANs using these extensions are also presented and analyzed. In terms of throughput for TCP bulk data transfer, compared to the throughput achieved from using the original Mobile IP implementation, these Mobile IP extensions led to a performance improvement of up to 20\% under certain scenarios.
Copyright © 1998 by Wilmer Caripe.
Postscript
(5592K)
|
gzipped Postscript
(1288K)
|
compressed Postscript
(1809K)
|
PDF
(729K)
URL: http://agent.cs.dartmouth.edu/papers/caripe:mobileip.pdf
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: 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: 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/
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: 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.
URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2000-375/
Abstract: The advances in sensing devices and integrated circuit technology have allowed for the development of easily "reconfigurable smart sensor" products. Primarily utilizing commercial off-the-shelf (COTS) components, we have developed reconfigurable smart sensor, consisting of a microprocessor, GPS receiver, RF transceiver, and sensor. The standard serial control interface allows for ease of interchangeability for upgrades in RF transmission schemes as well as customizing the sensing device (i.e. temperature, video images, IR, motion, Ethernet) per application. The result is a flexible module capable of gathering sensor data, local processing, and forwarding compressed information to a central location via other module.
In this paper, we present our system infrastructure design and a cost function based geographical self-routing algorithm for networking reconfigurable smart sensors. The algorithm allows for the sensors to automatically negotiate in a geographical radial topology relative to a central location, utilizing other sensors as routes or hops for forwarding information to this central location. A number of these sensors are deployed in the field and performance measurements for routing times are analyzed and presented.
Copyright © 2000 by SPIE.
gzipped Postscript
Abstract: Recent advances in sensing devices and integrated circuit technology have allowed for the development of easily "reconfigurable smart sensor" products for the application of Distributed Sensor Networks. Primarily utilizing commercial off-the-shelf (COTS) components, I have developed Reconfigurable smart sensors, consisting of a microprocessor, GPS receiver, RF transceiver, and temperature sensor. The result is a flexible module capable of gathering sensor data and forwarding compressed information to a central location via other modules.
In this Thesis, I will present a new paradigm with relaxed requirements for ad hoc sensor network routing protocols called Statistically Accurate Sensor Networks (SASN). Using the guidelines of a SASN, an innovative self-routing algorithm called Best Effort multi-Hop Geographical Routing (BEHGR), will be proposed for the purpose of networking wireless sensors. In BEHGR, geographical positioning information is utilized to dynamically route packets to a central location in a ``best effort" manner. Using the reconfigurable smart sensors as a real time test bed, I have deployed and tested the BEHGR protocol in the field. The infrastructure design for these sensor modules, as well as performance measurements for data throughput and data currentness of the BEHGR protocol are presented and analyzed.
Copyright © 2001 by Michael G. Corr.
gzipped Postscript
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.
Postscript
(2899K)
|
gzipped Postscript
(856K)
|
compressed Postscript
(941K)
|
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
No online copy available.
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.
No online copy available.
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: 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.
Postscript
(1031K)
|
gzipped Postscript
(267K)
|
compressed Postscript
(347K)
|
PDF
(293K)
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.
Postscript
(578K)
|
gzipped Postscript
(199K)
|
compressed Postscript
(257K)
|
PDF
(718K)
URL: http://www.cs.dartmouth.edu/~dfk/papers/gray:spe.ps.gz
Copyright © 1999 by IFAC.
PDF
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.
Postscript
(237K)
|
gzipped Postscript
(113K)
|
compressed Postscript
(133K)
|
PDF
(92K)
|
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.
Postscript
(228K)
|
gzipped Postscript
(109K)
|
compressed Postscript
(127K)
|
PDF
(92K)
|
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.
Postscript
(335K)
|
gzipped Postscript
(91K)
|
compressed Postscript
(146K)
|
PDF
(167K)
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: An ad-hoc network is formed by a group of mobile hosts upon a wireless network interface. Previous research in this area has concentrated on routing algorithms which are designed for fully connected networks. The usual way to deal with a disconnected ad-hoc network is to let the mobile computer wait the network reconnection passively, which may lead to unacceptable transmission delays. In this paper, 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 these modifications under two different assumptions: (a) the movements of all the nodes in the system and known and (b) the movements of the hosts in the system are not known.
Copyright © 2000 by ACM.
gzipped Postscript
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
Abstract: This paper discusses online power-aware routing in large sensor networks. We seek to optimize the lifetime of the network. We develop an approximation algorithm called max-min $zP_min$ that has a good empirical competitive ratio. To ensure scalability, we introduce a hierarchical algorithm, which is called zone-based routing.
Copyright © 2001 by the authors.
gzipped Postscript
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
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.
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
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
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
Abstract: This paper discusses online power-aware routing in large wireless ad-hoc 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.
Copyright © 2001 by ACM.
gzipped Postscript
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.
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
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.
Postscript
(229K)
|
gzipped Postscript
(71K)
|
compressed Postscript
(93K)
|
PDF
(219K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:agent-plan.ps.gz
Abstract: Mobile agents have received much attention recently as a way to efficiently access distributed resources in a low bandwidth network. Planning allows mobile agents to make the best use of the available resources. This thesis studies several planning problems that arise in mobile agent information retrieval and data-mining applications. The general description of the planning problems is as follows: We are given sites at which a certain task might be successfully performed. Each site has an independent probability of success associated with it. Visiting a site and trying the task there requires time (or some other cost matrix) regardless of whether the task is completed successfully or not. Latencies between sites, that is, the travel time between those two sites also have to be taken into account. If the task is successfully completed at a site then the remaining sites need not be visited. The planning problems involve finding the best sequence of sites to be visited, which minimizes the expected time to complete the task. We name the problems Traveling Agent Problems due to their analogy with the Traveling Salesman Problem. This Traveling Agent Problem is $NP$-complete in the general formulation. However, in this thesis a polynomial-time algorithm has been successfully developed to solve the problem by adding a realistic assumption to it. The assumption enforces the fact that the network consists of subnetworks where latencies between machines in the same subnetwork are constant while latencies between machines located in different subnetworks vary. Different versions of the Traveling Agent Problem are considered: (1) single agent problems, (2) multiple agent problems (multiple agents cooperate to complete the same task) and (3) deadline problems (single or multiple agents need to complete a task without violating a deadline constraint at each location in the network). Polynomial and pseudo-polynomial algorithms for these problems have been developed in this thesis. In addition to the theory and algorithm development for the various Traveling Agent Problems, a planning system that uses these algorithms was implemented. Descriptions of the mobile agent planning system with its supporting components such as network sensing system, directory service system, and clustering system, are also given in this thesis.
Copyright © 1998 by Katsuhiro Moizumi.
Postscript
(2438K)
|
gzipped Postscript
(578K)
|
compressed Postscript
(814K)
|
PDF
(1035K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:thesis.ps.gz
Copyright © 1997 by the authors.
Postscript
(382K)
|
gzipped Postscript
(84K)
|
compressed Postscript
(120K)
|
PDF
(199K)
URL: http://agent.cs.dartmouth.edu/papers/moizumi:uncertainty.ps.gz
Abstract: Interest in and development of mobile agent software systems has burgeoned in the past five years. Code mobility has many attractive attributes for performance and dynamic deployment of new distributed computing and information management applications. An active message is a datagram encapsulated as a mobile agent. The agent is persistent in the network, moving from node to node under its own internal routing logic and control at the application layer.
Active messages are particularly attractive in networks that have very unreliable links such as wireless networks in which the nodes are mobile. Such networks experience frequent link failures and other changes in topology. Active messages allow data to propagate between nodes that may never have viable TCP/IP type connections.
In spite of the growing implementation interest in mobile agents and active messaging, there are essentially no analytic models or results dealing with their performance. This paper presents a simple model for active messages in a network with frequent link failures. Using this model, we develop expressions for the expected delivery time of an active message along one path as well as expected delivery time for duplicated messages traversing disjoint paths between source and destination nodes.
Copyright © 1999 by Allerton Conference.
Postscript
(514K)
|
gzipped Postscript
(103K)
|
compressed Postscript
(140K)
|
PDF
(196K)
URL: http://agent.cs.dartmouth.edu/papers/okino:active.ps.gz
Abstract: Developing code for the execution of a distributed, dynamic workflow requires significant effort and hence it becomes necessary to build tools that enable the creation and execution of such workflows. Compelling arguments have been made for the implementation of workflow management systems using mobile agents. Mobile agents are autonomous pieces of code that can migrate under their own control from one machine to another within a heterogeneous network. Mission-flow Constructor (MfC) is a workflow management system built on the D'Agents mobile agent system. Like its predecessor Mobile Agent Construction Environment (MACE), MfC uses the concept of visual languages and further abstracts the process of building a workflow. Agents generated by MfC are small and migrate only once. These agents hence make more optimal use of network resources than those generated by MACE. MfC generated agents also use improved communication means and incorporate some basic fault tolerance mechanisms. A set of primitive constructs that encapsulate commonly used topologies has been defined to make easier the process of workflow definition. A workflow specified using the GUI and associated annotation process is compiled to a set of D'Agents agents by making use of the visual depiction and the code fragments that define the individual modules. MfC then launches these agents to execute the various tasks associated with the workflow specified by the user.
Copyright © 2000 by Shankar Sundaram.
gzipped Postscript
gzipped Postscript (109K) | compressed Postscript (159K) | PDF (216K)
Postscript (1398K) | gzipped Postscript (212K) | compressed Postscript (346K) | PDF (413K)
Postscript (1628K) | gzipped Postscript (469K) | compressed Postscript (600K) | PDF (3172K)
Postscript (223K) | gzipped Postscript (62K) | compressed Postscript (85K) | PDF (207K)
Postscript (205K) | gzipped Postscript (57K) | compressed Postscript (79K) | PDF (191K)
gzipped Postscript (112K) | compressed Postscript (177K) | PDF (254K)
Postscript (501K) | gzipped Postscript (148K) | compressed Postscript (239K) | PDF (711K)
No online copy available.
No online copy available.
gzipped Postscript (38K) | compressed Postscript (50K) | PDF (147K)
No online copy available.
Abstract: In this work we have designed explicit rate-based flow controllers for ABR (Available Bit Rate) sources in a communication network. The goal is to share the available capacity "fairly" among many sources while maintaining queue length at a bottleneck node at a desired level. This problem is first formulated as a stochastic control problem, and then converted to an equivalent decentralized team problem. In this reformulation, each member of the team has access to different information, but yet minimizes a common objective function that encapsulates several quality-of-service requirements. In the framework of the team problem, rate-control mechanisms have been developed, which stabilize the queue length at a bottleneck node, even though different sources may experience different round-trip delays to this node. Various appealing robustness properties of the solution have been illustrated through simulation experiments, among which is robustness with respect to unknown and variable delays.
No online copy available.
Postscript (832K) | gzipped Postscript (174K) | compressed Postscript (224K) | PDF (425K)
No online copy available.
No online copy available.
Postscript (278K) | gzipped Postscript (111K) | compressed Postscript (136K) | PDF (256K)
No online copy available.
Abstract: Coordinating agent behavior in agent ensembles is a key challenge for distributed AI. The authors describe a programming model that supports multiagent ensembles, and they present their Java-based prototype system, AgentFoundry.
URL: http://computer.org/intelligent/ex1999/x2038abs.htm
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.
Postscript (3029K) | gzipped Postscript (322K) | compressed Postscript (489K) | PDF (533K)