269391
Integrated coverage and connectivity configuration in wireless sensor networks
An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.
15273314
Feedback control real-time scheduling in ORB middleware
Existing real-time ORB middleware standards such as RT-CORBA do not adequately address the challenges of 1) providing robust performance guarantees portably across different platforms, and 2) managing unpredictable workload. To overcome this limitation, we have developed software called FCS/nORB that integrates a Feedback Control real-lime Scheduling (FCS) service with the nORB small-footprint real-time ORB designed for networked embedded systems. FCS/nORB features feedback control loops that provide real-time performance guarantees by automatically adjusting the rate of remote method invocations transparently to an application. FCS/nORB thus enables real-time applications to be truly portable in terms of real-time performance as well as functionality, without the need for hand tuning. This paper presents the design, implementation, and evaluation of FCS/nORB. Our extensive experiments on a Linux testbed demonstrate that FCS can provide deadline miss ratio and utilization guarantees in face of changes in the platform and task execution times, while introducing a small amount of overhead.
631362
DEUCON: Decentralized End-to-End Utilization Control for Distributed Real-Time Systems
Many real-time systems must control their CPU utilizations in order to meet end-to-end deadlines and prevent overload. Utilization control is particularly challenging in distributed real-time systems with highly unpredictable workloads and a large number of end-to-end tasks and processors. This paper presents the decentralized end-to-end utilization control (DEUCON) algorithm, which can dynamically enforce the desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier works, DEUCON features a novel decentralized control structure that requires only localized coordination among neighbor processors. DEUCON is systematically designed based on advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to different processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide a scalable and robust utilization control for large-scale distributed real-time systems executing in unpredictable environments.
5719252
End-to-end utilization control in distributed real-time systems
An increasing number of distributed real-time systems face the critical challenge of providing end-to-end quality of service (QoS) guarantees in open and unpredictable environments. In particular, such systems often need to guarantee the CPU utilization on multiple processors in order to achieve overload protection and meet end-to-end deadlines while task execution times are unpredictable. While the recently developed feedback control real-time scheduling algorithms have shown promise, they cannot handle the common end-to-end task model in distributed systems where each task is comprised of a chain of subtasks distributed on multiple processors. We present the end-to-end utilization control (EUCON) algorithm that features a distributed feedback loop that dynamically enforces desired CPU utilization bounds on multiple processors based on online performance measurements EUCON is based on a model predictive control approach that models the utilization control problem on a distributed platform as a multivariable constrained optimization problem. A multiinput-multioutput model predictive controller is designed based on a difference equation model that describes the dynamic behavior of distributed real-time systems. Both control theoretic analysis and simulations demonstrate that EUCON can provide robust utilization guarantees even when task execution times deviate from the estimation or vary significantly at run-time.
1347401
Decentralized utilization control in distributed real-time systems
Many real-time systems must control their CPU utilizations in order to meet end-to-end deadlines and prevent overload. Utilization control is particularly challenging in distributed real-time systems with highly unpredictable workloads and a large number of end-to-end tasks and processors. This paper presents the decentralized end-to-end utilization control (DEUCON) algorithm that can dynamically enforce desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier work, DEUCON features a novel decentralized control structure that only requires localized coordination among neighbor processors. DEUCON is systematically designed based on recent advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to different processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide scalable and robust utilization control for large-scale distributed real-time systems executing in unpredictable environments
1945985
A Model of Visuospatial Working Memory in Prefrontal Cortex: Recurrent Network and Cellular Bistability
We report a computer simulation of the visuospatial delayed-response experiments of Funahashi et al. (1989), using a firing-rate model that combines intrinsic cellular bistability with the recurrent local network architecture of the neocortex. In our model, the visuospatial working memory is stored in the form of a continuum of network activity profiles that coexist with a spontaneous activity state. These neuronal firing patterns provide a population code for the cue position in a graded manner. We show that neuronal persistent activity and tuning curves of delay-period activity (memory fields) can be generated by an excitatory feedback circuit and recurrent synaptic inhibition. However, if the memory fields are constructed solely by network mechanisms, noise may induce a random drift over time in the encoded cue position, so that the working memory storage becomes unreliable. Furthermore, a “distraction” stimulus presented during the delay period produces a systematic shift in the encoded cue position. We found that the working memory performance can be rendered robust against noise and distraction stimuli if single neurons are endowed with cellular bistability (presumably due to intrinsic ion channel mechanisms) that is conditional and realized only with sustained synaptic inputs from the recurrent network. We discuss how cellular bistability at the single cell level may be detected by analysis of spike trains recorded during delay-period activity and how local modulation of intrinsic cell properties and/or synaptic transmission can alter the memory fields of individual neurons in the prefrontal cortex.
14053941
AnnoSearch: Image Auto-Annotation by Search
Although it has been studied for several years by computer vision and machine learning communities, image annotation is still far from practical. In this paper, we present AnnoSearch, a novel way to annotate images using search and data mining technologies. Leveraging the Web-scale images, we solve this problem in two-steps: 1) searching for semantically and visually similar images on the Web, 2) and mining annotations from them. Firstly, at least one accurate keyword is required to enable text-based search for a set of semantically similar images. Then content-based search is performed on this set to retrieve visually similar images. At last, annotations are mined from the descriptions (titles, URLs and surrounding texts) of these images. It worth highlighting that to ensure the efficiency, high dimensional visual features are mapped to hash codes which significantly speed up the content-based search process. Our proposed approach enables annotating with unlimited vocabulary, which is impossible for all existing approaches. Experimental results on real web images show the effectiveness and efficiency of the proposed algorithm.
14870178
An approach to topology synthesis of analog circuits using hierarchical blocks and symbolic analysis
This paper presents a method of design automation for analog circuits, focusing on topology generation and quick performance evaluation. First we describe mechanisms to generate circuit topologies with hierarchical blocks. Those blocks are specialized by adding terminal information. The connection between blocks is in compliance with a set of synthesis rules, which are extracted from typical schematics in the literature. Symbolic analysis has been used to select an appropriate topology quickly and to help the designer gain a better understanding of a circuit's behavior. Finally, experimental results show the creativity and efficiency of our method
36451114
Sensor Network Configuration Under Physical Attacks
Sensor networks typically operate in hostile outdoor environments. In such environments, sensor networks are highly susceptible to physical attacks that can result in physical node destructions. In this paper, we study the impacts of physical attacks on sensor network configuration. Lifetime is an important metric during configuration for many sensor applications. While lifetime is constrained by limited energies and has been addressed before, prior results cannot be directly applied in the presence of physical attacks. In this paper, we define a practical lifetime problem in sensor networks under a representative physical attack model that we define. We develop an anlytical approach to derive the minimum number and deployment plan of sensors to meet lifetime requirement under physical attacks. We make several observations in this paper. One of our important observations is the high sensitivity of lifetime to physical attacks highlighting the significance of our study.
3433910
Residual-Based Measurement of Peer and Link Lifetimes in Gnutella Networks
Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the paper by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultrapeer lifetimes in a network of 6.4 million users and 60 million links. Our experimental results show that ultrapeer lifetimes are Pareto with shape a alpha ap 1.1; however, link lifetimes exhibit much lighter tails with alpha ap 1.9.