4668328
CoCoA: Coordinated Cooperative Localization for Mobile Multi-Robot Ad Hoc Networks
Mobile robot teams are particularly suited to applications where infrastructure is unavailable or damaged since they can be used to quickly form an infrastructure-less mobile ad hoc network performing tasks in a distributed manner. In such deployment scenarios, localization of individual robots is essential for enabling many applications. In this paper, we propose CoCoA, Coordinated Cooperative localization for mobile multi-robot Ad Hoc Networks, that is low-cost, quickly deployable, energy-efficient, and provides reasonable accuracy for the applications. In CoCoA, only a subset of the robots in the mobile robot team are equipped with external localization devices (e.g. GPS, laser rangers, vision sensors). Subsequently, while robots perform their tasks, they cooperate to help localize each other without requiring static landmarks to be deployed. In addition, CoCoA coordinates the localization operations of robots to reduce energy consumption. Using detailed simulations and localization models calibrated from experimental data, we find that CoCoA is effective in reducing energy consumption while providing good localization accuracy.
9215156
Energy management using buffer memory for streaming data
This work presents a new approach for energy management by inserting data buffers. The buffers are managed using the concept of inventory control by treating energy as cost and computation as production. The data stored in the buffers are considered as merchandise. Our method provides a mathematical framework to develop general strategies managing the energy consumption in computers. The approach can solve a wide range of problems. For example, it can calculate the needed buffer sizes to achieve optimal energy savings. It can derive the conditions when a standby state saves energy. The method also shows the effect of load balancing on energy conservation and can handle the variations of data rates. We use sensor networks as case studies and demonstrate more than 20% energy savings.
15594355
Replacing Failed Sensor Nodes by Mobile Robots
Sensor replacement is important for sensor networks to provide continuous sensing services. Existing approaches relocate redundant nodes to fill the holes created by failed sensors and require all or most sensor nodes to have mobility. However, mobility equipment is expensive while technology trends are scaling sensors to be smaller and cheaper. In this paper, we propose to use a small number of mobile robots to replace failed sensors in a large-scale static sensor network. We study algorithms for detecting and reporting sensor failures and coordinating the movement of robots that minimize the motion energy of mobile robots and the messaging overhead incurred to the sensor network. A manager receives failure reports and determines which robot to handle a failure. We study three algorithms: a centralized manager algorithm, a fixed distributed manager algorithm, and a dynamic distributed manager algorithm. Our simulations show that: (a) The centralized and the dynamic distributed algorithms have lower motion overhead than the fixed distributed algorithm. (b) The centralized algorithm is less scalable than the two distributed manager algorithms. (c) The two distributed algorithms have higher messaging cost than the centralized algorithm. Hence, the optimal choice of the coordination algorithm depends on the specific scenarios and objectives being optimized.
7685891
Quantitative comparison of power management algorithms
Dynamic power management saves power by shutting down idle devices. Several management algorithms have been proposed and demonstrated to be effective in certain applications. We quantitatively compare the power saving and performance impact of these algorithms on hard disks of a desktop and notebook computers. This paper has three contributions. First, we build a framework in Windows NT to implement power managers running realistic workloads and directly interacting with users. Second, we define performance degradation that reflects user perception. Finally, we compare power saving and performance of existing algorithms and analyze the difference.
2733921
Joint power management of memory and disk
The paper presents a scheme to combine memory and power management for achieving better energy reduction. Our method periodically adjusts the size of physical memory and the timeout value to shut down a hard disk for reducing the average power consumption. We use Pareto distributions to model the distributions of idle time. The parameters of the distributions are adjusted at run-time for calculating the corresponding timeout value of the disk power management. The memory size is changed based on the inclusion property to predict the number of disk accesses at different memory sizes. Experimental results show more than 50% energy savings compared to a 2-competitive fixed-timeout method.
161273
Dynamic power management for streaming data
This paper presents a method that uses data buffers to smoothen request variations and to create long idleness for power management. This method considers the power consumed by the buffers and assigns an energy penalty for buffer underflow. Our approach provides analytic formulas for calculating the optimal buffer sizes and the amount of data to store in the buffers. We use video prefetching as a case study and obtain power savings of more than 74% for MPEG-1 and 34% for MPEG-2 videos.
6121809
Tree-like counterexamples in model checking
Counter examples for specification violations provide engineers with important debugging information. Although counterexamples are considered one of the main advantages of model checking, state-of the art model checkers are restricted to relatively simple counterexamples, and surprisingly little research effort has been put into counterexamples. In this paper, we introduce a new general framework for counterexamples. The paper has three main contributions: (i) We determine the general form of ACTL counterexamples. To this end, we investigate the notion of counterexample and show that a large class of temporal logics beyond ACTL admits counterexamples with a simple tree-like transition relation. We show that the existence of tree-like counterexamples is related to a universal fragment of extended branching time logic based on w-regular temporal operators. (ii) We present new symbolic algorithms to generate tree-like counterexamples for ACTL specifications. (iii) Based on tree-like counterexamples we extend the abstraction refinement methodology developed recently by Clarke et al. (CAV'2000) to full ACTL. This demonstrates the conceptual simplicity and elegance of tree-like counterexamples.
5344006
Min/max on-chip inductance models and delay metrics
This paper proposes an analytical inductance extraction model for characterizing min/max values of typical on-chip global intercon-nect structures, and a corresponding delay metric that can be used to provide RLC delay prediction from physical geometries. The model extraction and analysis is efficient enough to be used within optimization and physical design exploration loops. The analytical min/max inductance approximations also provide insight into the effects caused by inductances.
1552056
Pama: a Fast String Matching Algorithm
String matching is a fundamental operation in computer science, and its performance has great impact on many applications including database query, text processing, DNA and protein sequence analysis. In this paper, we propose a fast string matching algorithm, PAMA (PAttern MAtching). The shift rule used by PAMA not only subsumes both the bad character rule and the good suffix rule employed by the well-known Boyer-Moore algorithm, but also employs an additional key observation to enable faster shifting during the string matching process. Theoretically, we prove that from the same alignment, the next shift of PAMA will be at least as much as that of the Boyer-Moore algorithm. Experimentally, we show that PAMA indeed significantly outperforms the original Boyer-Moore algorithm in almost all cases, and outperforms other Boyer-Moore variants such as Tuned-BM, Turbo-BM and Horspool for long patterns (length ≥ 128) or for small alphabets (size < 8).
11276211
PDC: Pattern discovery with confidence in DNA sequences
Pattern discovery in DNA sequences is one of the most challenging tasks in molecular biology and computer science. The main goal of pattern discovery in DNA sequences is to identify sequences of important biological function hidden in the huge amounts of genomic sequences. Several methods and techniques have been proposed and implemented in this field. However, in order to reduce computational time and complexity, most of them either focus on finding short DNA patterns or require explicit specification of pattern lengths in advance. Scientists need to find longer patterns without specifying pattern lengths in advance and still have good performance.In this paper, we propose a pattern discovery algorithm called Pattern Discovery with Confidence (PDC). Based on biological studies, we propose a new measurement system that can identify overrepresented patterns inside DNA sequences. Using this measurement, PDC algorithm can narrow the search space by checking dependency along the pattern, thus extending the pattern as long as possible without the need to restrict or specify the length of a pattern in advance. Experimental tests demonstrate that this approach can find long, interesting patterns within a reasonable computation time.
158009
Threshold optimization algorithm for weak signal in distributed-sensor fusion system
Distributed order statistics constant false alarm rate (OS-CFAR) detection techniques are important for nonstationary observation with varying weak narrowband random signals. However, it is very difficult to choose system parameters to obtain optimal threshold values at the fusion center because of the nonlinear property of distributed OS-CFAR detection system. This paper provides a novel solution based on an effective and flexible genetic algorithm. Using this approach, all system parameters are directly coded in decimal chromosomes and they can be optimized simultaneously. Furthermore, we also derive the more general model by implementing the K fusion rules. The simulation results show that applying the proposed approach one can achieve comparable performances with the reported methods and results.