Despite advances in hardware acceleration, implementing AI on mobile devices is difficult when tight real-time latency bounds have to be met without compromising accuracy. A simple solution is edge offload: using a low-latency wireless network to perform the AI on a nearby cloudlet. This approach also avoids the software engineering effort of downsizing cloud-based AI. In this paper, we experimentally compare on-device and offloaded AI execution by introducing a set of new benchmarks for computer vision tasks. The results show that edge offload is Pareto-optimal across accuracy and latency. It also greatly reduces on-device energy usage.

A long-standing concern with GPS-based location sensing is its vulnerability to satellite signal loss. This may arise from adversarial attacks or natural causes such as urban canyons. Today, there are no real alternatives to GPS for providing absolute global coordinates. We address this concern by introducing TerraSLAM, a new global positioning system that uses a 3D GIS model to bridge relative and absolute coordinate systems, thereby enhancing visual SLAM to function as a global positioning solution. TerraSLAM offers localization accuracy and efficiency comparable to GPS-RTK even in GPS-denied settings. Extensive evaluation on drone localization scenarios shows that TerraSLAM achieves an average global positioning accuracy of 0.21m and a 99th percentile within 0.67m, outperforming advanced GPS solutions by over 70% (0.72m) and 80% (3.62m). Additionally, when integrated with ORB-SLAM3, the localization latency per frame is 16.7ms, achieving a 60% reduction compared to the baseline of 41.3ms. Code is available at https://github.com/cmusatyalab/TerraSLAM.

We present a benchmark-driven experimental study of autonomous drone agility relative to edge offload pipeline attributes. This pipeline includes a monocular gimbal-actuated on-drone camera, hardware RTSP video encoding, 4G LTE wireless network transmission, and computer vision processing on a ground-based GPU-equipped cloudlet. Our parameterized and reproducible agility benchmarks stress the OODA (“Observe, Orient, Decide, Act”) loop of the drone on obstacle avoidance and object tracking tasks. We characterize the latency and throughput of components of this OODA loop through software profiling, and identify opportunities for optimization.

Fully autonomous flight by low-cost, lightweight commercial off-the-shelf (COTS) drones could transform many use cases involving real-time computer vision. We show how such autonomy can be achieved using edge computing from a flight platform costing less than $800, and composed of a 320 g COTS drone with a 26 g COTS wearable device as payload. In spite of the extreme austerity of this platform and thermal limits on its LTE transmission, the system is able perform tasks such as detecting and then tracking a target. It is also able to visually navigate around obstacles. Such capabilities are only found on heavier and more expensive drones today.

A severe bandwidth mismatch between incoming sensor data rate and wireless backhaul bandwidth often exists on unmanned probes when collecting new training data for machine learning (ML). To overcome this mismatch, we describe a self-improving ML-based transmission system called Hawk. Starting from a weak model that is trained on just a few examples, it seamlessly pipelines semi-supervised learning, active learning, and transfer learning, with asynchronous bandwidth-sensitive data transmission to a distant human for labeling. When a significant number of true positives (TPs) have been labeled, Hawk trains an improved model to replace the old model. This iterative workflow, called Live Learning, continues until a sufficient number of TPs have been collected. For very rare events on challenging datasets, and bandwidths as low as 12 kbps, a team of 7 probes using Hawk discovers up to 87% of the TPs that could have been discovered via full preview, transmission and labeling of all mission data. Hawk also uses diversity sampling and few-shot learning.

Summary Wearable Cognitive Assistance (WCA) amplifies human cognition in real time through a wearable device and low‐latency wireless access to edge computing infrastructure. It is inspired by, and broadens, the metaphor of GPS navigation tools that provide real‐time step‐by‐step guidance, with prompt error detection and correction. WCA applications are likely to be transformative in education, health care, industrial troubleshooting, manufacturing, assisted driving, and sports training. Today, WCA application development is difficult and slow, requiring skills in areas such as machine learning and computer vision that are not widespread among software developers. This paper describesAjalon,an authoring toolchain for WCA applications that reduces the skill and effort needed at each step of the development pipeline. Our evaluation shows that Ajalon significantly reduces the effort needed to create new WCA applications.

The visual fog paradigm envisions tens of thousands of heterogeneous, camera-enabled edge devices distributed across the Internet, providing live sensing for a myriad of different visual processing applications. The scale, computational demands, and bandwidth needed for visual computing pipelines necessitates offloading intelligently to distributed computing infrastructure, including the cloud, Internet gateway devices, and the edge devices themselves. This paper focuses on the visual fog scheduling problem of assigning the visual computing tasks to various devices to optimize network utilization. We first prove this problem is NP-complete, and then formulate a practical, efficient solution. We demonstrate sub-minute computation time to optimally schedule 20,000 tasks across over 7,000 devices, and just 7-minute execution time to place 60,000 tasks across 20,000 devices, showing our approach is ready to meet the scale challenges introduced by visual fog.

We show how to build the components of a privacy-aware, live video analytics ecosystem from the bottom up, starting with OpenFace, our new open-source face recognition system that approaches state-of-the-art accuracy. Integrating OpenFace with interframe tracking, we build RTFace, a mechanism for denaturing video streams that selectively blurs faces according to specified policies at full frame rates. This enables privacy management for live video analytics while providing a secure approach for handling retrospective policy exceptions. Finally, we present a scalable, privacy-aware architecture for large camera networks using RTFace and show how it can be an enabler for a vibrant ecosystem and marketplace of privacy-aware video streams and analytics services.

We present OpenFace, our new open-source face recognition system that approaches state-of-the-art accuracy. Integrating OpenFace with inter-frame tracking, we build RTFace, a mechanism for denaturing video streams that selectively blurs faces according to specified policies at full frame rates. This enables privacy management for live video analytics while providing a secure approach for handling retrospective policy exceptions. Finally, we present a scalable, privacy-aware architecture for large camera networks using RTFace.

Accurate, up-to-date maps of transient traffic and hazards are invaluable to drivers, city managers, and the emerging class of self-driving vehicles. We present LiveMap, a scalable, automated system for acquiring, curating, and disseminating detailed, continually-updated road conditions in a region. LiveMap leverages in-vehicle cameras, sensors, and processors to crowd-source hazard detection without human intervention. We build a real-time simulation framework that allows a mix of real and simulated components to be tested together at scale. We demonstrate that LiveMap can work well at city scales within the limits of today's cellular network bandwidth. We also show the feasibility of accurate, in-vehicle, computer-vision-based hazard detection.

We describe the architecture and prototype implementation of an assistive system based on Google Glass devices for users in cognitive decline. It combines the first-person image capture and sensing capabilities of Glass with remote processing to perform real-time scene interpretation. The system architecture is multi-tiered. It offers tight end-to-end latency bounds on compute-intensive operations, while addressing concerns such as limited battery capacity and limited processing capability of wearable devices. The system gracefully degrades services in the face of network failures and unavailability of distant architectural tiers.

The convergence of mobile computing and cloud computing enables new multimedia applications that are both resource-intensive and interaction-intensive. For these applications, end-to-end network bandwidth and latency matter greatly when cloud resources are used to augment the computational power and battery life of a mobile device. We first present quantitative evidence that this crucial design consideration to meet interactive performance criteria limits data center consolidation. We then describe an architectural solution that is a seamless extension of today's cloud computing infrastructure.

Cloud offload is an important technique in mobile computing. VM-based cloudlets have been proposed as offload sites for the resource-intensive and latency-sensitive computations typically associated with mobile multimedia applications. Since cloud offload relies on precisely-configured back-end software, it is difficult to support at global scale across cloudlets in multiple domains. To address this problem, we describe just-in-time (JIT) provisioning of cloudlets under the control of an associated mobile device. Using a suite of five representative mobile applications, we demonstrate a prototype system that is capable of provisioning a cloudlet with a non-trivial VM image in 10 seconds. This speed is achieved through dynamic VM synthesis and a series of optimizations to aggressively reduce transfer costs and startup latency.

We propose a scalable Internet system for continuous collection of crowd-sourced video from devices such as Google Glass. Our hybrid cloud architecture, GigaSight, is effectively a Content Delivery Network (CDN) in reverse. It achieves scalability by decentralizing the collection infrastructure using cloudlets based on virtual machines~(VMs). Based on time, location, and content, privacy sensitive information is automatically removed from the video. This process, which we refer to as denaturing, is executed in a user-specific VM on the cloudlet. Users can perform content-based searches on the total catalog of denatured videos. Our experiments reveal the bottlenecks for video upload, denaturing, indexing, and content-based search. They also provide insight on how parameters such as frame rate and resolution impact scalability.

Vision-based prop-free pointing detection is challenging both from an algorithmic and a systems standpoint. From a computer vision perspective, accurately determining where multiple users are pointing is difficult in cluttered environments with dynamic scene content. Standard approaches relying on appearance models or background subtraction to segment users operate poorly in this domain. We propose a method that focuses on motion analysis to detect pointing gestures and robustly estimate the pointing direction. Our algorithm is self-initializing; as the user points, we analyze the observed motion from two cameras and infer rotation centers that best explain the observed motion. From these, we group pixel-level flow into dominant pointing vectors that each originate from a rotation center and merge across views to obtain 3D pointing vectors. However, our proposed algorithm is computationally expensive, posing systems challenges even with current computing infrastructure. We achieve interactive speeds by exploiting coarse-grained parallelization over a cluster of computers. In unconstrained environments, we obtain an average angular precision of 2.7°.

Interactive perception applications, such as gesture recognition and vision-based user interfaces, process high-data rate streams with compute intensive computer vision and machine learning algorithms. These applications can be represented as data flow graphs comprising several processing stages. Such applications require low latency to be interactive so that the results are immediately available to the user. To achieve low latency, we exploit the inherent coarse grained task and data parallelism of these applications by running them on clusters of machines. This paper addresses an important problem that arises: how to place the stages of these applications on machines to minimize the latency, and in particular, how to adjust an existing schedule in response to changes in the operating conditions (perturbations) while minimizing the disruption in the existing placement (churn). To this end, we propose four incremental placement heuristics which use the HEFT scheduling algorithm as their primary building block. Through simulations and experiments on a real implementation, using diverse workloads and a range of perturbation scenarios, we demonstrate that dynamic adjustment of the schedule can improve latency by as much as 36%, while producing little churn.

Various research efforts have focused on scaling modular robotic systems up to millions of cooperating devices. However, such efforts have been hampered by the lack of prototype hardware in such quantities and the unavailability of accurate and highly scalable simulations. This paper describes a simulation framework for such systems, which can model the execution of distributed software and the physical interaction between modules. We develop a scalable, multithreaded version of an off-the-shelf physics engine, and create a software execution engine that can efficiently harness hundreds of cores in a cluster of commodity machines. Our approach is shown to run 108x faster than a previous scalable simulator, and permit simulations with over 20 million modules.

Resource constrained mobile devices need to leverage computation on nearby servers to run responsive applications that recognize objects, people, or gestures from real-time video. The two key questions that impact performance are what computation to offload, and how to structure the parallelism across the mobile device and server. To answer these questions, we develop and evaluate three interactive perceptual applications. We find that offloading and parallelism choices should be dynamic, even for a given application, as performance depends on scene complexity as well as environmental factors such as the network and device capabilities. To this end we develop Odessa, a novel, lightweight, runtime that automatically and adaptively makes offloading and parallelism decisions for mobile interactive perception applications. Our evaluation shows that the incremental greedy strategy of Odessa converges to an operating point that is close to an ideal offline partitioning. It provides more than a 3x improvement in application performance over partitioning suggested by domain experts. Odessa works well across a variety of execution environments, and is agile to changes in the network, device and application inputs.

In this article, we formalize locally distributed predicates , a concept previously introduced to address specific challenges associated with modular robotics and distributed debugging. A locally distributed predicate (LDP) is a novel construction for representing and detecting distributed properties in sparse-topology systems. Our previous work on LDPs presented empirical validation; here we show a formal model for two variants of the LDP algorithm, LDP-Basic and LDP-Snapshot, and establish performance bounds for these variants. We prove that LDP-Basic can detect strong stable predicates, that LDP-Snapshot can detect all stable predicates, and discuss their applicability to various distributed programming domains and to spatial computing in general. LDP detection in bounded-degree networks is shown to be scale-free, making the approach particularly attractive for specific topologies, even though LDPs are less efficient than snapshot algorithms in general distributed systems.

It is of great importance to protect rapidly-spreading and widely-used small mobile devices like smartphones and PocketPCs from energy-depletion attacks by monitoring software (processes) and hardware (especially, battery) resources. The ability to use these devices for on- and/or off-job functions, and even for medical emergencies or disaster recovery is often dictated by their limited battery capacity. However, traditional malware detection systems and antivirus solutions based on matching signatures are limited to detection of only known malware, and hence, cannot deal with battery-depletion attacks. To meet this challenge, we propose to develop, implement, and evaluate a comprehensive framework, called MODELZ, that MOnitors, DEtects, and anaLyZes energy-greedy anomalies on small mobile devices. MODELZ comprises 1) a charge flow meter that allows infrequent sampling of energy consumption without losing accuracy, 2) a power monitor, in coordination with the charge flow meter, that samples and builds a power-consumption history, and 3) a data analyzer that generates a power signature from the power-consumption history. To generate a power signature, we devise and apply light-weighted, effective noise filtering and data compression, reducing the detection overhead significantly. The similarities between power signatures are measured by the χ2-distance and used to lower both false-positive and false-negative detection rates. Our experimental results on an HP iPAQ running the Windows Mobile OS have shown that MODELZ achieves significant (up to 95 percent) storage-savings without losing detection accuracy, and a 99 percent true-positive rate in differentiating legitimate programs from suspicious ones while the monitoring consumes 50 percent less energy than the case of keeping the Bluetooth radio turned on.

Video understanding is a computationally challenging task that is critical not only for traditionally throughput-oriented applications such as search but also latency-sensitive interactive applications such as surveillance, gaming, videoconferencing, and vision-based user interfaces. Enabling these types of video processing applications will require not only new algorithms and techniques, but new runtime systems that optimize latency as well as throughput. In this paper, we present a runtime system called Sprout that achieves low latency by exploiting the parallelism inherent in video understanding applications. We demonstrate the utility of our system on an activity recognition application that employs a robust new descriptor called MoSIFT, which explicitly augments appearance features with motion information. MoSIFT outperforms previous recognition techniques, but like other state-of-the-art techniques, it is computationally expensive -- a sequential implementation runs 100 times slower than real time. We describe the implementation of the activity recognition application on Sprout, and show that it can accurately recognize activities at full frame rate (25 fps) and low latency on a challenging airport surveillance video corpus.

LDP (Locally Distributed Predicates) is a distributed, high-level language for programming modular reconfigurable robot systems (MRRs). In this paper we present the implementation of two motion-planning algorithms in LDP, and analyze both their performance and ease of implementation. We present multiple variations of one planner, including a novel resource allocation algorithm. We then draw conclusions about both the utility of the motion-planning algorithms and the suitability of LDP to the problem space. Our experiments suggest that metamodule-based planning approaches have a cost in time and/or energy terms, but that the cost can be worth paying in exchange for the additional generality and separation-of-concerns offered by these techniques. The particular tradeoff for a given system will depend upon its goals and the details of the underlying modules.

A critical problem in implementing interactive perception applications is the considerable computational cost of current computer vision and machine learning algorithms, which typically run one to two orders of magnitude too slowly to be used interactively. Fortunately, many of these algorithms exhibit coarse-grained task and data parallelism that can be exploited across machines. The SLIPstream project focuses on building a highly-parallel runtime system called Sprout that can harness the computing power of a cluster to execute perception applications with low latency. This paper makes the case for using clusters for perception applications, describes the architecture of the Sprout runtime, and presents two compute-intensive yet interactive applications.

We present a high-level language for programming modular robotic systems, based on locally distributed predicates (LDP), which are distributed conditions that hold for a connected subensemble of the robotic system. An LDP program is a collection of LDPs with associated actions which are triggered on any subensemble that matches the predicate. The result is a reactive programming language which efficiently and concisely supports ensemble-level programming. We demonstrate the utility of LDP by implementing three common, but diverse, modular robotic tasks.

In this paper we develop a theory of metamodules and an associated distributed asynchronous planner which generalizes previous work on metamodules for lattice-based modular robotic systems. All extant modular robotic systems have some form of non-holonomic motion constraints. This has prompted many researchers to look to metamodules, i.e., groups of modules that act as a unit, as a way to reduce motion constraints and the complexity of planning. However, previous metamodule designs have been specific to a particular modular robot. By analyzing the constraints found in modular robotic systems we develop a holonomic metamodule which has two important properties: (1) it can be used as the basic unit of an efficient planner and (2) it can be instantiated by a wide variety of different underlying modular robots, e.g., modular robot arms, expanding cubes, hex-packed spheres, etc. Using a series of transformations we show that our practical metamodule system has a provably complete planner. Finally, our approach allows the task of shape transformation to be separated into a planning task and a resource allocation task. We implement our planner for two different metamodule systems and show that the time to completion scales linearly with the diameter of the ensemble.

Tightly-coupled multi-agent systems such as modular robots frequently exhibit properties of interest that span multiple modules. These properties cannot easily be detected from any single module, though they might readily be detected by combining the knowledge of multiple modules. Testing for distributed conditions is especially important in debugging or verifying the correctness of software for modular robots. We have developed a technique we call distributed watchpoint triggers which can efficiently recognize such distributed conditions. Our watchpoint description language can handle a variety of temporal, spatial, and logical properties spanning multiple robots. This paper presents that language, describes our fully-distributed, online mechanism for detecting distributed conditions in a running system, and evaluates the performance of our implementation. We found that the performance of the system is highly dependent on the program being debugged, scales linearly with ensemble size, and is small enough to make the system practical in all but the worst case scenarios

Creatively misquoting Thomas Hobbes, the process of software debugging is nasty, brutish, and all too long. This holds all the more true in robotics, which frequently involves concurrency, extensive nondeterminisism, event-driven components, complex state machines, and difficult platform limitations. Inspired by the challenges we have encountered while attempting to debug software on simulated ensembles of tens of thousands of modular robots, we have developed a new debugging tool particularly suited to the characteristics of highly parallel, event- and state-driven robotics software. Our state capture and introspection system also provides data that may be used in higher-level debugging tools as well. We report on the design of this promising debugging system, and on our experiences with it so far.

This paper presents Meld, a programming language for modular robots, i.e., for independently executing robots where inter-robot communication is limited to immediate neighbors. Meld is a declarative language, based on P2, a logicprogramming language originally designed for programming overlay networks. By using logic programming, the code for an ensemble of robots can be written from a global perspective, as opposed to a large collection of independent robot views. This greatly simplifies the thought process needed for programming large ensembles. Initial experience shows that this also leads to a considerable reduction in code size and complexity. An initial implementation of Meld has been completed and has been used to demonstrate its effectiveness in the Claytronics simulator. Early results indicate that Meld programs are considerably more concise (more than 20× shorter) than programs written in C++, while running nearly as efficiently.

One of the primary impediments to building ensembles of modular robots is the complexity and number of mechanical mechanisms used to construct the individual modules. As part of the Claytronics project - which aims to build very large ensembles of modular robots - we investigate how to simplify each module by eliminating moving parts and reducing the number of mechanical mechanisms on each robot by using force-at-a-distance actuators. Additionally, we are also investigating the feasibility of using these unary actuators to improve docking performance, implement intermodule adhesion, power transfer, communication, and sensing. In this paper we describe our most recent results in the magnetic domain, including our first design sufficiently robust to operate reliably in groups greater than two modules. Our work should be seen as an extension of systems such as Fracta [9], and a contrasting line of inquiry to several other researchers' prior efforts that have used magnetic latching to attach modules to one another but relied upon a powered hinge [10] or telescoping mechanism [12] within each module to facilitate self-reconfiguration.

We describe a novel shape formation algorithm for ensembles of 2-dimensional lattice-arrayed modular robots, based on the manipulation of regularly shaped voids within the lattice ("holes"). The algorithm is massively parallel and fully distributed. Constructing a goal shape requires time proportional only to the complexity of the desired target geometry. Construction of the shape by the modules requires no global communication nor broadcast floods after distribution of the target shape. Results in simulation show 97.3% shape compliance in ensembles of approximately 60,000 modules, and we believe that the algorithm will generalize to 3D and scale to handle millions of modules

This paper presents a novel application of modular robotic technology. Many researchers expect manufacturing technology will allow robot modules to be built at smaller and smaller scales, but movement and actuation are increasingly difficult as dimensions shrink. We describe an application - a 3D fax machine - which exploits inter-module communication and computation without requiring self-reconfiguration. As a result, this application may be feasible sooner than applications which depend upon modules being able to move themselves. In our new approach to 3D faxing, a large number of submillimeter robot modules form an intelligent "clay" which can be reshaped via the external application of mechanical forces. This clay can act as a novel input device, using intermodule localization techniques to acquire the shape of a 3D object by casting. We describe software for such digital clay. We also describe how, when equipped with simple inter-module latches, such clay can be used as a 3D output device. Finally, we evaluate results from simulations which test how well our approach can replicate particular objects

This demonstration presents a novel mechanism for the electronic acquisition of shapes of arbitrary objects, and the the remote reproduction of these shapes: in essence a 3D fax machine. Our approach is based on Claytronics, a form of intelligent matter or "smart clay" composed of thousands of tiny particles, each of which is a small electronic device capable of sensing, computation, communication, and actuation. For our purposes, this Claytronic material is treated as a network of thousands to millions of communicating sensor nodes that must work cooperatively to determine the shape of an object. We demonstrate the highly scalable software we have designed to permit such intelligent "clay" be used as both the input and output stages of a 3D fax machine through physics-based simulations.

This paper examines how computation can be mapped across the nodes of a distributed search system to effectively utilize available resources. We specifically address computationally intensive search of complex data, such as content-based retrieval of digital images or sounds, where sophisticated algorithms must be evaluated on the objects of interest. Since these problems require significant computation, we distribute the search over a collection of compute nodes, such as active storage devices, intermediate processors and host computers. A key challenge with mapping the desired computation to the available resources is that the most efficient distribution depends on several factors: relative power and number of compute nodes; network bandwidth between the compute nodes; the cost of evaluating query predicates; and the selectivity of the given query. This wide range of variables renders manual partitioning of the computation infeasible, particularly since some of the parameters (e.g., available network bandwidth) can change during the course of a search. This paper proposes several techniques for dynamic partitioning of computation, and demonstrates that they can significantly improve efficiency for distributed search applications.

Robot photographers have appeared in a variety of novelty settings over the past few years and typically have exploited rudimentary image-content-based approaches to identifying potential photographic subjects. These approaches are primarily limited to human subjects and further progress along content-based lines is hamstrung by slow progress on the general computer vision problem. In this paper, we present a mobile robot system which solves the group-picture-framing problem without requiring content-based methods. The system finds photographic subjects based on measurements of motion parallax obtained via optical flow during robot movements. Our method requires only sufficient contrast to permit reasonably accurate sparse optical flow field estimation and is completely independent of any content-based image heuristics. The result is a working mobile robot system that can correctly photograph human and non-human subjects in a variety of posed-subject situations, and produce well-framed, cropped images for printing on standard-sized photo paper.

This paper describes a novel approach to powering a radical type of microrobot. Our long-term aim is to enable the construction of ensembles of millions of coordinated near-spherical, submillimeter microrobots. Both the large number of potential simultaneous neighbors of each robot (12) and the difficulty of fine actuation at such small scales preclude the use of complex connectors previously developed in many modular robotics efforts. Instead, we propose to leverage multirobot cooperation to simplify the mechanics of modular robot docking. In our approach, the robots actively cooperate to route virtual power busses (both supply and ground) to all the robots in the ensemble using only unary (single conductor) electrical connectors between robots. A unary connector allows for larger tolerances in engagement angle, simplifies robot manufacture, speeds reconfiguration, and maximizes the proportion of the connector surface area useful for carrying current. The algorithms we present permit a robot ensemble to efficiently harvest and distribute power from sources discovered in the environment and/or carried by the ensemble. We evaluate these algorithms in a variety of simulated deployment conditions and report on the impact of hardware defects, limited on-board power storage, and the ensemble-environment interface.

Most current sensor network research explores the use of extremely simple sensors on small devices called motes and focuses on over-coming the resource constraints of these devices. In contrast, our research explores the challenges of multimedia sensors and is motivated by the fact that multimedia devices, such as cameras, are rapidly becoming inexpensive, yet their use in a sensor network presents a number of unique challenges. For example, the data rates involved with multimedia sensors are orders of magnitude greater than those for sensor motes and this data cannot easily be processed by traditional sensor network techniques that focus on scalar data. In addition, the richness of the data generated by multimedia sensors makes them useful for a wide variety of applications. This paper presents an overview of IRISNET, a sensor network architecture that enables the creation of a planetary-scale infrastructure of multimedia sensors that can be shared by a large number of applications. To ensure the efficient collection of sensor readings, IRISNET enables the application-specific processing of sensor feeds on the significant computation resources that are typically attached to multimedia sensors. IRISNET enables the storage of sensor readings close to their source by providing a convenient and extensible distributed XML database infrastructure. Finally, IRISNET provides a number of multimedia processing primitives that enable the effective processing of sensor feeds in-network and at-sensor.

We propose a demonstration of extremely scalable modular robotics algorithms developed as part of the Claytronics Project (http://www-2.cs.cmu.edu/~claytronics/), as well as a demonstration of proof-of-concept prototypes. Our effort envisions multi-million-module robot ensembles able to morph into three-dimensional scenes, eventually with sufficient fidelity so as to convince a human observer the scenes are real. Although this work is potentially revolutionary in the sense that it holds out the possibility of radically altering the relationship between computation, humans, and the physical world, many of the research questions involved are similar in flavor to more mainstream systems research, albeit larger in scale. For instance, as in sensor networks, each robot will incorporate sensing, computation, and communications components. However, unlike most sensor networks each robot will also include mechanisms for actuation and motion. Many of the key challenges in this project involve coordination and communication of sensing and actuation across such large ensembles of independent units.

There is an increasing prevalence of interactive Web sessions in the Internet. These are mostly short-lived TCP connections that are delay-sensitive and have transfer times dominated by TCP backoffs, if any, during connection establishment. Unfortunately, arrivals of such connections at a server tend to be bursty, and can trigger multiple retransmissions, resulting in long average client-perceived delays. Traditional traffic control mechanisms, such as token bucket filters, are designed to complement admission control mechanisms, by regulating throughput, bounding service times, and protecting systems from overload. However, they cannot control connection-establishment delays, and thus, do not provide effective control of client-perceived delays. We first present the surprising discovery of a resynchronization property of retransmitted requests that exacerbates client-perceived delays when traditional control mechanisms are used. Then, we introduce a novel, multistage filtering scheme called Abacus Filters (AFs) that limits the client-perceived delay while maximizing server throughput even in the case of bursty connection arrivals. Analysis of delay-control properties of various filtering mechanisms is presented, along with a detailed performance evaluation. AFs are shown to provide tight delay control and better complement traditional admission control policies.

In recent years, there has been a rapid and wide spread of non-traditional computing platforms, especially mobile and portable computing devices. As applications become increasingly sophisticated and processing power increases, the most serious limitation on these devices is the available battery life. Dynamic Voltage Scaling (DVS) has been a key technique in exploiting the hardware characteristics of processors to reduce energy dissipation by lowering the supply voltage and operating frequency. The DVS algorithms are shown to be able to make dramatic energy savings while providing the necessary peak computation power in general-purpose systems. However, for a large class of applications in embedded real-time systems like cellular phones and camcorders, the variable operating frequency interferes with their deadline guarantee mechanisms, and DVS in this context, despite its growing importance, is largely overlooked/under-developed. To provide real-time guarantees, DVS must consider deadlines and periodicity of real-time tasks, requiring integration with the real-time scheduler. In this paper, we present a class of novel algorithms called real-time DVS (RT-DVS) that modify the OS's real-time scheduler and task management service to provide significant energy savings while maintaining real-time deadline guarantees. We show through simulations and a working prototype implementation that these RT-DVS algorithms closely approach the theoretical lower bound on energy consumption, and can easily reduce energy consumption 20% to 40% in an embedded real-time system.

EMERALDS (Extensible Microkernel for Embedded, ReAL-time, Distributed Systems) is a real-time microkernel designed for small-memory embedded applications. These applications must run on slow (15-25MHz) processors with just 32-128 kbytes of memory, either to keep production costs down in mass-produced systems or to keep weight and power consumption low. To be feasible for such applications, the OS must not only be small in size (less than 20 kbytes), but also have low-overhead kernel services. Unlike commercial embedded OSs which rely on carefully-crafted code to achieve efficiency, EMERALDS takes the approach of re-designing the basic OS services of task scheduling, synchronization, communication, and system call mechanism by using characteristics found in small-memory embedded systems, such as small code size and a priori knowledge of task execution and communication patterns. With these new schemes, the overheads of various OS services are reduced 20-40% without compromising any OS functionality.