2377937
O(log n)-Localized Algorithms on the Coverage Problem in Heterogeneous Sensor Networks
In this paper, we study the maximum lifetime target coverage problem (MTC), which is to maximize the network lifetime while guaranteeing the complete coverage of all the targets. Many centralized algorithms have been proposed to solve this problem. A very few distributed versions have also been presented but none of them obtains a good approximation ratio. In this paper, we propose two O(log n) localized algorithms. In particular, we first reduce the MTC problem to the domatic number problem in directed graphs. This relation shows that a feasible solution to the domatic number problem is also a feasible solution to the MTC problem. We next prove the lower and upper bounds of this domatic number. Based on this proof, we present two O (log n)-localized algorithms to solve the MTC problem.
14497547
Improved construction for pooling design
Abstract
Pooling design is a mathematical tool with many applications in molecular biology, specially to reduce the number of tests for DNA library screening. In this note, we study construction of pooling design and present an improvement to a recent new construction given by Du et al. (J. Comput. Biol. 13:990–995, 2006).

2820764
On the construction of 2-connected virtual backbone in wireless networks
Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We show that CDSA has guaranteed quality by proving that the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that in practice, CDSA can build a 2-connected virtual backbone with only small overhead.
1931354
Coverage problems in wireless sensor networks: designs and analysis
One fundamental problem in wireless sensor networks is the coverage problem, which reflects the quality of service that can be provided by a particular sensor network. The coverage problem is defined from several points of view due to a variety of sensor networks and a wide-range of their applications. Several different designs and formulations of the coverage problem have been proposed. They are subject to various topics such as types of interest regions (areas versus targets) and different network constraints, such as fault tolerance and bandwidth limitation. In this paper, we survey the state-of-the-art coverage formulations with an objective of maximising network lifetime. In particular, we present an overview and analysis of the solutions proposed in recent research literature.
9475863
Optimization scheme for sensor coverage scheduling with bandwidth constraints
Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).
10134877
Greedy Approximation Algorithms
Greedy strategy is a simple and natural method in the design of approximation algorithms. This chapter presents greedy approximation algorithms for very broad classes of maximization problems and minimization problems and analyzes their approximation bounds. A number of applications of these greedy approximation algorithms are also described in this chapter. For many applications, the greedy approximation algorithm can achieve the best known approximation bound in a straightforward manner. For some applications, they have different formulations, and the corresponding greedy approximation algorithms have different approximation bounds. In addition, some applications can have better approximation algorithm than the greedy approximation algorithm.
6241423
OBFS: A File System for Object-Based Storage Devices
The object-based storage model, in which files are made up of o ne or more data objects stored on self-contained Object-Based Storage Devices (OSDs), is em erging as an architecture for distributed storage systems. The workload presented to the OSDs will be q uite different from that of generalpurpose file systems, yet many distributed file systems employ general-purpose file systems as their underlying file system. We present OBFS, a small and highly ef ficient file system designed for use in OSDs. Our experiments show that our user-level implement ation of OBFS outperforms Linux Ext2 and Ext3 by a factor of two or three, and while OBFS is 1/25 the size of XFS, it provides only slightly lower read performance and 10%‐40% higher write pe rformance.
8328656
A Variation Aware High Level Synthesis Framework
The worst-case delay/power of function units has been used in traditional high level synthesis to facilitate design space exploration. As technology scales to nanometer regime, the impact of process variations increases. The degree of variability encountered in the new process technologies makes worst-case analysis undesirable, because it may result in unexpected performance/power discrepancy or a pessimistic estimation, and may end up using excess resources to guarantee design constraints. In this paper, we propose a high level synthesis framework to take into account of the performance/power variation for function units. An effective metric called parametric yield, which is defined as the probability of the synthesized data flow graph (DFG) meeting the performance and power constraints, is used to guide scheduling, module selection, and resource sharing. An efficient performance/power yield perturbation computation method for DFG significantly improves the effectiveness of our yield driven high level synthesis algorithm. The experimental results show that our variation-aware synthesis framework achieves significant yield improvements, and has much faster (3X) runtime speed compared against previous approach.
61647385
On-chip Bus Thermal Analysis and Optimization
As technology scales, increasing clock rates, decreasing interconnect pitch, and the introduction of low-k dielectrics have made self-heating of the global interconnects an important issue in VLSI design. In this paper, we study the self-heating of on-chip buses and show that the thermal impact due to self-heating of on-chip buses increases as technology scales, thus motivating the need of finding solutions to mitigate this effect. Based on the theoretical analysis, we propose an irredundant bus encoding scheme for on-chip buses to tackle the thermal issue. Simulation results show that our encoding scheme is very efficient to reduce the on-chip bus temperature rise over substrate temperature, with much less overhead compared to other low power encoding schemes.
5172777
Using MEMS-based storage in computer systems---MEMS storage architectures
As an emerging nonvolatile secondary storage technology, MEMS-based storage exhibits several desirable properties including high performance, high storage volumic density, low power consumption, low entry cost, and small form factor. However, MEMS-based storage provides a limited amount of storage per device and is likely to be more expensive than magnetic disk. Systems designers will therefore need to make trade-offs to achieve well-balanced designs. We present an architecture in which MEMS devices are organized into MEMS storage enclosures with online spares. Such enclosures are proven to be highly reliable storage building bricks with no maintenance during their economic lifetimes. We also demonstrate the effectiveness of using MEMS as another layer in the storage hierarchy, bridging the cost and performance gap between MEMS storage and disk. We show that using MEMS as a disk cache can significantly improve system performance and cost-performance ratio.
6487057
Process-Variation-Aware Adaptive Cache Architecture and Management
Fabricating circuits that employ ever-smaller transistors leads to dramatic variations in critical process parameters. This in turn results in large variations in execution/access latencies of different hardware components. This situation is even more severe for memory components due to minimum-sized transistors used in their design. Current design methodologies that are tuned for the worst case scenarios are becoming increasingly pessimistic from the performance angle, and thus, may not be a viable option at all for future designs. This paper makes two contributions targeting on-chip data caches. First, it presents an adaptive cache management policy based on nonuniform cache access. Second, it proposes a latency compensation approach that employs several circuit-level techniques to change the access latency of select cache lines based on the criticalities of the load instructions that access them. Our experiments reveal that both these techniques can recover significant amount of the lost performance due to worst case designs.